Computer Sci.

오늘 살펴볼 문제는 백준 1655번 문제이다. https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다. www.acmicpc.net 나는 처음에 이 문제를 정말 단순하게 직관적으로 접근했었다. N개의 입력값을 받아서 하나씩 ArrayList에 받고 그 때마다 정렬을 한 뒤 i/2 번째 원소를 찾아서 출력하면 되지 않나? 라고 접근해서 풀었고 시간초과가 나왔다. 이는 당연한게 시간 복잡도가 O(N*N*logN)..

오늘은 동기화를 공부한 내용에 대해서 정리 해 보려고 한다. 프로세스 간 통신 프로세스는 시스템 내에서 독립적으로 실행 되기도 하고, 데이터를 주고받으며 협업하기도 한다. 프로세스가 다른 프로세스와 데이터를 주고받는 프로세스간 통신(IPC)에는 같은 컴퓨터 내에 있는 프로세스 뿐만 아니라 네트워크로 연결된 다른 컴퓨터에 있는 프로세스와의 통신도 포함된다. 프로세스간 통신에는 크게 세 가지가 있다. 프로세스 내부 데이터 통신 하나의 프로세스 내에 2개 이상의 스레드가 존재하는 경우의 통신이다. 프로세스 내부의 스레드는 전역 변수나 파일을 이용하여 데이터를 주고받는다. 전역 변수를 이용한 통신 : 전역 변수를 이용한 통신은 공동으로 관리하는 메모리를 사용하여 데이터를 주고 받는 것이다. 데이터를 보내는 쪽에..

이번에는 쓰레드에 대해서 공부한 내용을 정리해 보려고 한다. 지난 포스팅에서 프로세스에 대해서 정리를 한 적이 있었다. 프로세스는 스케줄링의 단위로서 실행 단위(Execution unit)이다. 또한 소유하고 있는 자원에 대한 보호(Protection domain) 개념을 가지고 있기도 하다. 지금까지는 하나의 실행 흐름을 가지고 실행중인 프로그램에 대해서만 다루었기 때문에 프로세스만 가지고 설명이 가능했다. 하지만 프로세스의 처리 속도가 점점 빨라져야 할 필요성에 맞추어, 하나의 프로세스가 수행해야 할 여러 작업들을 나누어 수행할 수 있는 설계가 필요해졌고, 이에 생겨난 개념이 쓰레드(Thread)이다. 쓰레드는 프로세스 내의 실행 흐름이다. 이 역시 실행 단위(Execution unit)으로 볼 수 ..

오랜만에 운영체제 공부를 다시 시작하게 되었다. 이번에는 CPU 스케줄링에 대해 정리해 보려고 한다. CPU 스케줄링이란? CPU 스케줄링은 프로세스가 작업을 수행할 때, 언제 어떤 프로세스에 CPU를 할당할지를 결정하는 작업이다. 기본적으로 멀티프로그래밍과 시분할에 기반한다. 메모리 내에 실행 준비된 프로세스 중 하나를 선택하여 CPU를 할당한다. 한정된 CPU 및 I/O장치 등의 시스템 자원을 가지고 최고의 성능을 내야 하고, 따라서 자원을 언제 어떻게 할당할지를 결정하는 문제는 정말 중요하다. CPU 스케줄링의 목표는 CPU를 최대로 활용하는 것, 즉 idle을 최소화 하는 것이다. 참고로 이 때 time quantum은 커널이 CPU를 쓰는 시간에 포함하지 않는다. CPU 스케줄링의 결정은 다음 ..

오늘은 프로세스에 대해서 공부해 본다. 프로그램과 프로세스 소스코드 (.c file) : 프로그램이 수행하고자 하는 작업이 프로그래밍 언어로 표현 컴파일러 (compiler) : 사람이 이해할 수 있는 프로그래밍 언어로 작성된 소스코드를 컴퓨터(CPU)가 이해할 수 있는 기계어로 표현된 오브젝트 파일로 변환 오브젝트 (.o file) : 컴퓨터가 이해할 수 있는 기계어로 구성된 파일. 자체로는 수행이 이루어지지 못함. 프로세스로 변환되기 위한 정보가 삽입되어야 함. 상대 주소로 표현 링커 (linker) : 관련된 여러 오브젝트 파일들과 라이브러리들을 연결하여 메모리로 로드될 수 있는 하나의 실행파일만 작성 실행파일 (.exe) : 특정한 환경(OS)에서 수행될 수 있는 파일. 프로세스로의 변환을 위한 ..

오늘도 운영체제 구조, 특히 그 중에서도 디자인 관점에서 공부를 해 보려고 한다. 프로세스 관리(Process Management) 프로세스는 실행중인 프로그램을 의미한다. 프로그램은 파일 형태로 존재하는 수동적 상태(Passive Entity)이며, 프로세스는 프로그램 카운터를 가지는 능동적 상태(Active Entity)이다. 싱글 스레드 프로세스는 1개의 프로그램 카운터를, 멀티 스레드 프로세스는 스레드당 1개의 카운터를 가진다. ※프로그램 카운터(Program Counter)란? 프로그램 카운터(Program counter, PC)는 마이크로프로세서(CPU) 내부에 있는 레지스터 중의 하나로서, 다음에 실행될 명령어의 주소를 가지고 있어 실행할 기계어 코드의 위치를 지정한다. 때문에 명령어 포인터..

이번 포스팅 부터는 운영체제를 다루어 보려고 한다. 그 첫번째 순서는 운영체제의 구조이다. 운영체제란 무엇인가? 전 세계에서 가장 많이 쓰이는 운영체제 교과서인 Abraham Silberschatz의 교재에는 다음과 같이 운영체제를 설명하고 있다. An operating system is a program that manages a computer’s hardware. It also provides a basis for application programs and acts as an intermediary between the computer user and the computer hardware. 여기에 나와있는 것처럼 운영체제는 컴퓨터의 하드웨어를 관리하면서 하드웨어를 손쉽게 그리고 효율적으로 사용할..

이번 포스팅에서는 그래프 자료구조에 대해서 공부해 본다. 그래프 그래프(Graph)는 노드(node)와 그 노드를 연결하는 간선(edge)을 하나로 모아놓은 자료구조이다. 즉, 연결되어 있는 객체 간의 관계를 표현할 수 있다. 예를 들면 지하철에서 다른 역으로 가는 최단 경로를 찾아주는 서비스도 그래프 알고리즘을 사용한다. 그래프의 한 종류로 트리 자료구조가 있는데 그래프와 트리의 차이는 다음과 같다. 그래프 관련 용어를 정리하면 다음과 같다. 먼저 정점과 간선의 연결 관계에서 방향성을 가지는 지를 가지고 나누어 볼 수 있다. 방향성이 없는 그래프를 무향 그래프(Undirected Graph)라 하고, 방향성이 포함되어 있는 그래프를 유향 그래프(Directed Graph)라고 한다. 무향 그래프에서 각..