4Legs_Archives

배경 메모리는 현대 컴퓨터 시스템 동작의 주축이다. 메모리는 각자의 주소를 가진 대용량의 바이트(byte) 배열과도 같다. CPU는 메모리로부터 Program counter에 대응하는 연산을 fetch하며, 이 연산들은 특정 메모리 주소에 대한 추가적인 load, store가 필요할 수 있다. 전형적인 연산-실행 순환 과정(Instruction-Execution Cycle)은 다음과 같다. 1. 연산이 메모리로부터 fetch된다. 2. 해당 연산은 decode되어 다른 피연산자를 메모리로부터 fetch할 수도 있다. 3. 연산이 피연산자에 대해 실행되면, 결과는 다시 메모리에 저장(store)된다. 메모리 단위는 그저 메모리 주소들의 연속일 뿐이며, 그 주소들이 어떻게 생성되었는지나 어떻게 사용되는지는 ..

정의 세마포어를 통해 구현한 대기 큐는 둘 이상의 프로세스가 현재 대기 중인 프로세스에서만 발생할 수 있는 이벤트를 기다리는 상황이 발생할 수 있다. 그림에서 P0은 P1이 signal(Q)를 실행하기 전까진 wait(Q) 문장에서 계속 대기한다. 마찬가지로 P1도 P0이 signal(S)를 실행하기 전까진 wait(S) 문장에서 계속 대기한다. 두 프로세스 모두 결국 signal() 문장을 실행할 수 없기 때문에, 두 프로세스 모두 무한히 대기하게 된다. 이러한 상황을 교착 상태(Deadlock)라 한다. 즉, 한 프로세스가 요구하는 자원을 대기 중인 다른 프로세스가 가지고 있는(hold) 경우를 말한다. 용어 Request : 프로세스가 해당 자원을 요청한다. 만약 자원을 요청한 프로세스가 그 즉시 ..

Peterson's Soultion Critical-Section Problem을 소프트웨어 기반의 간단한 구조로 해결하는 Peterson's Solution을 알아보자. 현대의 하드웨어에서는 동작할 확신을 가질 수 없지만, Critical-Section Problem 해결의 알고리즘적 기초를 제공했다는 것에 그 의의가 있다. Peterson's Solution은 Critical Section과 Remainder Section을 실행하는 두 프로세스에 한해 동작한다. 두 프로세스를 P0, P1이라 하자. Peterson's Solution은 두 프로세스들이 다음 데이터를 공유하도록 한다. turn 변수는 Critical Section에 들어갈 프로세스가 현재 누구 차례인지를 나타낸다. 만약 turn이 i..

Producer-Consumer Problem 다음 두 코드를 보자. Producer 코드는 buffer 한 칸에 문자를 쓰고 버퍼의 다음 칸으로 이동하고 counter를 증가시킨다. Consumer 코드는 counter 값이 0이 될 때까지 buffer 한 칸의 문자를 읽고, counter 값을 감소시킨 후 버퍼의 다음 칸으로 이동한다. 이 두 코드는 각자 실행할 경우 잘 동작하지만, 동시에 실행시켰을 때에는 잘 작동하지 않을 수 있다. 각 코드가 공유하는 counter 변수를 조작하는 과정에서 문제가 발생하는데, counter를 조작하는 구문을 다음과 같이 풀어 쓸 수 있다. (이는 low-level에서 해당 구문이 동작하는 순서와 같음) 동시에 실행되는 counter++ 구문과 counter-- 구..

Priority Scheduling 각 프로세스에 우선도 값을 부여하여, 우선도 값이 높은 프로세스를 CPU에 우선 할당하는 알고리즘이다. (즉, SJF도 Burst Time이 짧은 프로세스가 높은 우선도를 갖는 Priority Scheduling의 한 경우로 볼 수 있다.) 동일한 우선도에 대해서는 FCFS 알고리즘을 적용한다. 우선도는 정의하기 나름이다. 1이라는 우선도가 3이라는 우선도에 비해 낮을 수도 있고, 높을 수도 있다. (참고한 교재 『Operating System Concepts』 에서는 낮은 숫자를 높은 우선도로 두었다.) 우선도는 내부적 또는 외부적으로 정의될 수 있다. 내부적으로 정의된 우선도는 프로세스의 우선도를 계산하기 위해 측정 가능한 양을 사용한다. 시간 제한이나, 메모리 요..

스케줄링 알고리즘 CPU 스케줄링 알고리즘은 준비 큐에 있는 프로세스들에 대해 어떤 프로세스를 CPU에 할당할지 결정한다. 각 알고리즘들을 살펴보자. FCFS (First-Come, First-Served) 가장 단순한 알고리즘으로, CPU의 사용을 먼저 요청한 프로세스가 먼저 할당되도록 동작하는 비선점 알고리즘이다. FIFO(First-In, First-Out) 자료구조인 큐(Queue)를 통하여 쉽게 구현할 수 있다는 장점을 갖는다. 하지만, 다음과 같은 상황에서 FCFS의 단점이 드러난다. 위의 예시에서 Burst Time은 프로세스가 CPU를 사용하는 시간이라 생각하면 된다. 이 상황에서 FCFS를 적용한다면, CPU는 P1, P2, P3 순서로 CPU를 할당하게 된다. 하지만 P1의 Burst ..

CPU 스케줄링 (CPU Scheduling) 단일 프로세서 시스템에서는, 한 번에 단 하나의 프로세스만 실행될 수 있다. 다른 모든 프로세스들은 CPU가 사용 가능해지고 자신이 다시 스케줄링될 때까지 반드시 기다려야만 하는 것이다. 멀티프로그래밍 시스템에서는 CPU 사용을 최대화하기 항상 몇 개의 프로세스들이 돌아가고 있다. 하지만 프로세스는 일반적으로 입출력 요청 등이 들어오면 그 요청이 완료될 때까지 대기해야 한다. 만약 컴퓨터 시스템이 CPU를 단순히 idle상태로 존재하도록 둔다면, 요청이 끝나길 기다리는 동안 아무것도 하지 않는 것이다. 이 때의 대기 시간은 그저 낭비될 뿐이다. 따라서 멀티프로그래밍 시스템은 이 필연적인 대기 시간을 효율적으로 사용하려 한다. 실행 중인 프로세스가 대기해야 할..

스레드 라이브러리 (Thread Libraries) 스레드 라이브러리는 프로그래머에게 스레드를 생성하고 관리하는 API를 제공한다. 스레드 라이브러리의 구현은 2가지로 나뉘는데, 1. 모든 라이브러리를 커널의 지원 없이 사용자 공간에 제공한다. 이는 라이브러리의 함수를 호출하는 것이 곧 시스템 콜이 아닌 사용자 공간의 지역 함수를 호출한다는 것이라는 의미이다. 2. 운영체제에 의해 직접 지원되는 커널 수준의 라이브러리를 구현한다. 이는 라이브러리의 함수 호출이 곧 시스템 콜임을 의미한다. Pthreads (POSIX Standard) 스레드의 생성과 동기화에 대한 API를 정의한 것이다. (Specification, not an Implementation) C언어에서 pthread.h 헤더 파일을 inc..

스레드 (Thread) 웹 서버가 페이지, 이미지, 사운드 등의 클라이언트 요청을 처리하는 상황을 생각해 보자. 사용량이 많은 웹 서버는 수천, 수만 명의 사용자들의 수많은 요청을 연속적으로 받게 될 것이다. 하지만 만약 웹 서버가 한 번에 단 하나의 요청만 처리할 수 있다면, 사용자들은 간단한 요청 하나에도 많은 시간을 기다리며 불편을 토로할 것이다. 이러한 상황을 해결하는 방법으로는 각 요청마다 요청을 처리하는 프로세스를 두는 것을 들 수 있다. 서버가 요청을 받으면, 서버는 요청을 처리하는 프로세스를 생성하여 받은 요청에 대한 적절한 서비스를 제공한다. 하지만 수천, 수만 개의 요청에 대해 각각 프로세스를 생성하는 데에는 시간 자원의 낭비가 심해질 것이다. 그렇다면 프로세스 하나가 마치 여러 개의 ..

프로세스의 생성 한 프로세스는 실행되는 도중 프로세스 생성 시스템 콜을 통해 새로운 프로세스들을 생성할 수 있다. 다른 프로세스를 생성하는 프로세스를 부모 프로세스(Parent Process)라 하고, 다른 프로세스에 의해 생성된 프로세스를 자식 프로세스(Child Process)라 한다. 프로세스의 부모-자식 관계들은 트리의 형태로 나타나게 된다. 대부분의 운영체제에서는 프로세스들을 구별하기 위해 각 프로세스들에게 유일성을 가진 정수 PID(Process Identifier)를 부여한다. 일반적으로, 프로세스는 CPU time, 메모리, 파일, 입출력 장치 등의 자원이 필요하다. 따라서 어떤 프로세스가 다른 프로세스를 하나 생성하면, 생성된 프로세스는 운영체제로부터 직접 자원을 제공받거나 부모 프로세스..