운영체제 2
컴퓨터는 여러 개의 프로세스를 수행해야 합니다. 이때 컴퓨터는 다양한 연산(프로세스)을 동시에 수행하는 것처럼 보입니다. 그런데 하나의 CPU를 가진 컴퓨터 시스템은, 어떤 시점 t0에서 한가지의 연산밖에 수행하지 못합니다. 그러면 어떻게 동시에 수행하는 것처럼 보일까요? 프로세스와 쓰레드를 이용해 그렇게 구현할 수 있습니다.(가상화 등) 프로세스는 실행하는 주체로, 자원을 할당받습니다. 단, 여기서 운영체제는 프로세스가 아닌 code data임에 유의합니다. 쓰레드는 프로세스의 각각의 실행 흐름을 의미합니다. 프로그램이 구동되는 모습을 멀리서 살펴보면 이 프로그램들이 동시에 실행되고 있는 것 처럼 보입니다.(병행시행) 하지만 시간을 나누어 더 세부적으로 살펴보면 아주 짧게 조금씩 번갈아가면서 실행되고 있는 모습을 볼 수 있습니다. CPU가 하나라면 한 순간에 하나의 프로세스를 실행합니다. CPU의 개수가 늘어날수록 동시에 실행할 수 있는 프로세스의 수가 늘어날 수 있습니다. 만약 A, B, C ..로 여러 개의 프로세스가 있고, A프로세스의 시작 지점은 5000번지라고 가정합시다. 만약 A프로세스가 실행된다면 PC(프로그램 카운터)는 5000번지를 가리킬 것이고, 그 다음부터 차례대로 계속해 나갈 것입니다. 이 과정에서 일정 시간이 지나면 타이머 인터럽트가 발생하게 됩니다. 그러면 타이머 인터럽트 서비스 루틴으로 넘어가 스케줄링을 합니다. 다음에 실행할 프로세스를 선택하게 되고, 문맥 저장(다음에 실행할 A프로세스의 주소)을 한 후 B프로세스 C프로세스 혹은 자기 자신까지도 다시 선택해 순차적으로 진행할 수 있습니다. 만약 타이머 인터럽트 서비스 루틴이 아니고 I/O 시스템 호출 등이 발생한다면, 이를 처리하는 시간동안 스케줄링을 하여 다른 프로세스가 실행될 수 있게 합니다. 이런 것이 반복되면 병행 시행을 구현할 수 있습니다.
프로세스 생성
리눅스 운영체제와 같은 경우 부팅을 하게 되면 최초의 프로세스가 만들어지게 됩니다. 그 프로세스(부모)가 다른 나머지 프로세스(자식)들을 만들어서 프로세스를 수행하게 됩니다. 예를 들면 GUI에서 아이콘을 클릭해 프로세스를 생성한다고 할 때, GUI(부모) -> 어떤 프로세스(자식) 이러한 관계가 Tree처럼 만들어집니다.
프로세스 종료
모든 프로그램의 마지막에는 exit를 호출하게 되어있습니다. 프로그램을 종료하게 되면 시스템 호출을 보내 운영체제에서 해당 프로그램을 종료하도록 하는데, 자원의 반환 등으로 이 과정이 금방 이루어지지는 않습니다. 때문에 이미 종료 요청을 보내 더 이상 사용하지 않는 프로세스임에도 계속 남아있는 경우가 있습니다. 이러한 프로세스를 좀비 프로세스라고 합니다. 일반적으로 exit가 이루어지는 경우는 0을 반환하면서 종료하는 Normal exit과 0이 아닌 값을 반환하면서 종료하는 Error exit가 있습니다. 또 다른 프로세스의 신호에 의해서 종료되는 경우도 있습니다. 운영체제가 직접 해당 프로세스를 종료하는 경우가 있는데, 0으로 나누거나 메모리 엑세스가 불가능한 등 CPU가 해당 연산을 수행할 수 없는 경우입니다.
프로세스 상태
위에서 살펴본 것처럼 프로세스는 실행하는 중(Running)과 실행 대기중(Ready)로 나눌 수 있습니다. 그리고 그 두개의 상태가 순환하면서 프로세스는 실행되는 것처럼 보입니다. 그런데 프로세스가 I/O 시스템 호출 등으로 Running 상태가 될 수 없고 기다리는 상태라면, 현재 실행중이지도 않고 실행이 불가능한 상태가 필요합니다. 이러한 상태를 Blocked라고 합니다. 만약 입출력이 끝난다면 이 프로세스는 다시 Ready가 될 것입니다.
프로세서는 레디 큐에 위치한 프로세스들(현재 Ready 상태인 프로세스들이 모여 있음)중 하나를 Dispatch하여 실행하고, 타임아웃이 되면 다시 레디 큐에 집어넣습니다. 그러나 I/O와 같이 대기해야하는 이벤트가 발생하면 Block 큐, 혹은 이벤트 큐 (이 큐는 이벤트마다 존재합니다.) 에 집어넣습니다. 만약 이 이벤트가 끝나면 다시 레디 큐에 집어넣습니다. 또한 프로세스는 Admit되어 실행될 때까지 자원을 할당받는 등의 과정이 있는데, 이때 프로세스의 상태를 New라고 합니다. 마찬가지로 프로세스가 종료될 때 상태를 Exit 혹은 좀비상태라고 합니다. Suspend 상태는 사용자가 의도적으로 프로세스를 멈추게 한 상태입니다. Ready상태에서 Suspend상태가 되도록(Ready/Suspend) 할 수 있고, Blocked상태에서 Suspend상태가 되도록(Blocked/Suspend)할 수도 있습니다. Suspend상태에서 Activate를 하면 각각의 원래 상태로 돌아갑니다. New상태에서 Admit을 해 Ready/Suspend상태로 갈지 Ready로 갈지는 운영체제에 따라 조금씩 다릅니다. 그러면 Suspend상태는 왜 필요할까요? 우선 사용자가 그렇게 요구할 수 있습니다. 또한 운영체제가 Suspend상태로 만들 수 있는데, 예를 들면 시스템에 부하가 너무 심해 일부 프로세스를 잠시 중단시키고 그 자원을 가져다 쓰는 경우가 있습니다. 운영체제 내부에는 프로세스 테이블이라는 것이 존재합니다. 리눅스에서는 task_struct라고도 합니다. 프로세스 관리를 위한 자료구조, 메모리 관리를 위한 자료구조, 파일 관리를 위한 자료구조가 정의되어 있습니다.
멀티프로그래밍
교재에 있던 그림을 참고하면, 메모리에 적재한 프로세스의 수를 x축, CPU의 사용률을 y축으로 하여 I/O대기율에 따른 그래프를 볼 수 있습니다. 사용자 입장에서는 CPU사용률이 100%에 가까울수록 좋을 것입니다. 시간대비 효율적으로 연산을 수행할 수 있기 때문입니다. 그런데 그래프에서는 I/O대기율이 낮은 프로세스에 반해 높은 프로세스일수록 CPU 사용률이 많이 떨어지는 것을 볼 수 있습니다. 우리가 사용하는 GUI인터페이스나 한글 프로그램과 같은 것들은 다양한 방법으로 들어오는 사용자의 입력을 항상 기다려야 하기 때문에 I/O대기시간이 매우 깁니다. 그래서 CPU사용률을 높이기 위해 멀티프로그래밍이라는 개념이 제시되었고 사용되고 있습니다. 메모리에 적재한 프로세스의 수가 많으면 많을수록 좋겠지만 메모리의 한계로 무한정 적재할 수는 없습니다.
쓰레드
쓰레드는 보통 실행의 흐름이라고 번역을 하곤 합니다. 기존에는 프로세스라는 개념만 있었습니다. 이때 각각의 프로세스에는 실행의 흐름이 하나뿐이었습니다. 그런데 실행의 흐름을 여러 개로 나누고 싶었기 때문에, 쓰레드라는 개념이 제시되었습니다. 예를 들면 웹 브라우저를 사용할 때 배너와 사용자의 입출력 부분, 스크롤 등은 서로 다른 실행의 흐름으로 사용자에게 보여야 하는데 여러 개의 프로세스로 이를 구현하기는 매우 어려울 것입니다. 쓰레드에게 각각의 역할을 전담시켜 이러한 문제를 해결할 수 있습니다. 또한 복잡한 연산은 여러 개의 프로세서로 나누어 수행하면 더 빠르게 결과를 구할 수 있는데, 실행의 흐름 하나를 가진 프로세스로는 두 개의 프로세서에 나누어 수행할 수 없습니다. 만약 그렇게 하고 싶다면 프로세스를 분리해서 작업해야 하고, 각 프로세스의 값들을 공유하기도 어렵습니다. 그런데 쓰레드의 개념을 이용하면 이러한 과정을 더욱 쉽게 처리할 수 있습니다. 한 프로세스 안에 있기 때문에 자원을 공유할 수도 있기 때문입니다. 또한 프로세스와 별개로 쓰레드에도 필요한 자료구조가 있는데 상태와 프로그램 카운터를 저장합니다. 프로그램 카운터가 따로 있기 때문에 레지스터와 스택도 쓰레드별로 가지게 됩니다. 이때 각각 쓰레드마다 스택이 따로 있다는 점에 유의해야 하는데, 스택에는 로컬 변수를 저장하기 때문입니다. 다중 쓰레드가 적용된 프로세스의 경우 모든 쓰레드가 종료되고 나서 프로세스가 종료됩니다. 당연하게도, 옛날의 운영체제는 다중 쓰레드를 지원하지 않았습니다. 그래서 일종의 트릭으로 사용자가 택한 방법(유저 레벨 쓰레드 패키지)이 프로세스 안에 작은 운영체제 역할을 하는 스케줄러를 포함하고 여러 개의 쓰레드를 사용하는 것입니다. 이렇게 하면 커널 레벨에서는 그저 프로세스를 번갈아서 실행할 뿐입니다. 그러나 이러한 방법에는 제약이 많습니다. 예를 들면 어떤 쓰레드가 I/O 입출력이 발생하면 blocked상태가 되어야 하는데 운영체제는 프로세스만 알기 때문에 모든 프로세스를 blocked상태로 만들면 지연 시간이 매우 길어집니다. 이 때문에 non-blocking 시스템으로 만들어야 하는 등의 제약이 있습니다. 또한 프로세스 A, B에 여러 쓰레드들이 있다고 하면, A의 특정 쓰레드와 B의 특정 쓰레드를 번갈아 가면서 수행할 수 없습니다. 지금은 커널 레벨에서 쓰레드를 지원합니다. 운영체제가 프로세스 테이블뿐 아니라 쓰레드 테이블도 가지고 있습니다. 그래서 스케줄링을 쓰레드 테이블을 기준으로 합니다. 물론 유저 레벨 쓰레드 패키지와 커널 레벨의 쓰레드를 모두 이용할 수 있습니다. 프로세스 하나는 쓰레드보다 비용이 높기 때문에(특히 유저 레벨 쓰레드는 매우 쌉니다) 이런 방법을 사용할 수도 있습니다. 쓰레드라는 개념이 처음 도입되었을 때 여러 문제점들이 있었는데 그 중 하나는 변수의 공유입니다. 예를 들어 c언어에 있는 errorno는 글로벌변수로 하나 선언되어 있습니다. 그런데 한 쓰레드가 다른 쓰레드의 errorno값을 overwritten하는 경우가 생기게 됩니다. 이를 방지하고자 각 쓰레드에는 글로벌 변수를 따로 가지도록 설계합니다. 이전에 보았던 것처럼 각 쓰레드는 스택을 가지고 있는데, 그 스택이 글로벌 변수들을 가리키는 방식입니다.
Race Condition
여러 개의 프로세스를 실행할 때, 프로세스가 같은 위치에 접근해 값을 변경하려고 시도한다면 프로세스가 어떻게 스케줄링 되었는지에 따라 결과값이 다를 것입니다. 즉 입력된 값이 같아도, 출력 결과가 다를 수 있습니다. 이러한 상황이 Race Condition이고, 컴퓨터 시스템에서는 이러한 상황이 절대로 나와서는 안됩니다.
Critical Regions (임계 구역)
그래서 이러한 가능성을 없애기 위해 생긴 조건들이 있습니다. 이 조건을 모두 만족해야 합니다.
- 우선 CPU의 개수나 속도가 결과에 영향을 받아서는 안됩니다.
- 공유 자원에 동시에 접근하면 안됩니다. (상호 배제. Mutual Exclusion)
- 공유 자원 Critical Section에 아무 프로세스가 없으면 접근할 수 있어야 합니다. (Progress)
- 기다리면 언젠가는 공유 자원에 접근할 수 있어야 합니다. (우선순위에 한없이 밀리면 안됨) (Bounded Waiting)
그러면 이 Mutual Exclusion을 어떻게 구현할 수 있을까요? 이를 구현하기 위한 여러가지 방법들이 있습니다.
Disabling interrupts
여러 프로세스를 사용할 때 Race Condition이 발생하는 이유 자체가 임계 구역에 접근하는 도중 인터럽트가 발생하고, 다른 프로세스가 이를 사용하는 경우였기 때문에 임계 구역에 있을 때에는 인터럽트가 발생하지 않도록 하여 해결할 수 있습니다. 그러나 이 해결 방식은 CPU가 하나일때만 효과가 있을 것입니다. CPU가 여러 개이면 다른 CPU에서 임계 구역에 접근할 수도 있기 때문입니다.
Strict alternation
프로세스 i와 j가 있다고 할 때, 두 프로세스가 모두 while 루프를 돌면서 turn값을 검사합니다. turn값에는 임계 구역에 들어가도 좋은 프로세스가 할당되어 있는데, 프로세스 i가 실행되고 turn역시 i라면 임계구역에 접근합니다. 과정이 끝나고 나면, turn값을 j로 변경해 j가 접근할 수 있도록 합니다. 얼핏 보기에는 문제가 없어 보이지만 큰 문제가 있습니다. 만약 turn은 j인 상황에서 j는 더 이상 임계 구역에 접근할 필요가 없고 i만 계속 접근을 시도한다면 계속 아무 일도 일어나지 않게 됩니다. 즉 Critical Regions에서 Progress와 Bounded Waiting을 만족하지 않게 됩니다.
Dekker’s Solution
turn변수 외에도 flag변수를 사용합니다. 이 플래그는 ‘사용자가 들어가려고 하는지?’에 대한 값을 저장합니다. 만약 다른 사용자의 플래그가 모두 FALSE라면 지금 사용자는 turn값과 관계없이 임계 구역에 접근해도 되기 때문입니다. 이렇게 되면 아까 Strict alternation에서는 만족하지 못했던 Progress가 만족하게 됩니다. 만약 두 프로세스의 flag가 모두 TRUE(둘다 접근 시도)라면 turn으로 지목받지 못한 프로세스의 flag를 FALSE로 바꾸어 turn으로 지목된 프로세스가 실행될 수 있도록 합니다. 그 프로세스가 끝나고 나서 turn을 상대 프로세스로 바꾸고, 지목받지 못헀던 프로세스도 실행할 수 있도록 합니다. 따라서 상호 배제도 만족하게 됩니다.
Peterson’s Solution
이 방식은 데커의 방식과 비슷하지만 더 간단하게 기술되어 있습니다. 그러나 어떻게 작성하는지에 따라 상호 배제가 이루어지지 않을 수 있기 때문에 유의해야 합니다. 임계 구역에 접근하려고 할 때 우선 각각의 flag를 TRUE로 만들고, turn을 자기 자신으로 합니다. 이 방식에서 turn은 ‘지목된 프로세스가 양보’하게 됩니다. 그래서 두 프로세스가 거의 동시에 접근했더라도 turn은 i혹은 j를 가지고 있는데, turn값이 만약 i라면 프로세스 j가 먼저 임계 구역에 접근합니다. 그리고 접근이 끝나면 flag[j]를 FALSE로 만들어 i가 임계구역에 접근할 수 있도록 합니다. 만약 turn이 임계구역 접근 후에 바꾸도록 설계했다면, 임계 구역에 동시에 접근할 수도 있기 때문에(상호 배제를 불만족함) 유의해야합니다. 이런 알고리즘을 사용하더라도 우리가 얻고싶은 결과를 제대로 얻지 못하는 경우가 있을 수 있습니다. 현대의 컴퓨팅은 매우 복잡하기 때문에, 파이프라이닝이나 슈퍼스칼라등의 영향으로 결과를 예측하기 어려울 수 있습니다. 그래서 필요하다면 mfence라는 명령어를 이용해 메모리를 완전히 업데이트 후 진행하는 등의 방법을 모색할 수 있습니다.
Bakery Algorithm (분산 환경에서 실제로 사용하는 알고리즘)
두개, 세개 이상의 프로세스에 대한 해결책을 다루는 알고리즘입니다. 실제로 빵집의 이용자가 번호표를 받는 것과 같은 방식을 취합니다. 각각의 프로세스는 현재까지 다른 프로세스가 받은 번호의 최대 + 1한 만큼의 번호를 할당 받고, 그 번호의 순서대로 임계 구역에 접근합니다. 그런데 여기서 번호를 할당 받는 동안에 인터럽트가 발생할 수 있기 때문에, 같은 번호를 할당 받는 경우가 분명히 존재할 것입니다. 그럴 때에는 프로세스의 번호가 낮은 순서대로 처리합니다. (a,b) < (c,d) 는 (a<c) or ((a==c)&&(b<d))입니다.
TSL Instruction
이전까지의 알고리즘은 임계 구역에 대해 소프트웨어로 구현한 해결책이라면 TSL 방식은 하드웨어로 구현한 해결책입니다. 임계 구역에 접근하려고 할 때 LOCK변수의 값을 REGISTER에 가져오고, LOCK을 1로 변경합니다. 이때 REGISTER의 값이 1이라면 이미 누군가가 접근중이라는 의미이므로 임계 구역의 접근을 다시 시도합니다. 그런데 LOCK변수의 값을 REGISTER에 가져오고 LOCK의 값을 바꾼다는 것이 한 번에 연산 가능하지 않습니다. 그래서 Atomic한 연산을 구현하기 위해서 LOCK pin이 추가됩니다. 어떤 CPU가 LOCK 메모리에 접근할 때 LOCK pin에 신호를 보내 다른 CPU가 메모리에 접근할 수 없도록 합니다. CPU에 따라 TSL명령어나 MOVE/XCHG명령어를 사용합니다. TSL명령어는 더 간단하게 임계 구역 접근을 위해 만든 명령어입니다.
Producer – Consumer Problem
생산자는 어떤 데이터를 큐에 계속 넣는 행위를 하는 프로세스이고, 소비자는 어떤 데이터를 계속 꺼내 쓰는 프로세스입니다. 큐의 크기가 N이라고 가정하면, 생산자가 N까지의 데이터를 다 넣어서 더 이상 넣을 공간이 없을 때 생산자는 sleep상태에 들어갑니다. 만약 소비자가 하나를 꺼내왔는데 count의 값이 N-1이라면 자기가 꺼낸 것이 가장 마지막의 것이라는 의미이므로 (즉, 생산자가 sleep 상태일수도 있으므로) 생산자를 깨워줍니다. 반대의 상황도 마찬가지로 count가 0이어서 소비자가 더 이상 꺼낼 것이 없다면 sleep상태에 들어갑니다. 만약 생산자가 하나를 넣었는데 count의 값이 1이라면 빈 상태에서 처음으로 넣었다는 의미이므로 (즉, 소비자가 sleep 상태일수도 있으므로) 소비자를 깨워줍니다. 이 과정을 반복합니다. 만약 sleep을 요청한다면 앞에서 다뤘던 내용처럼 해당 쓰레드를 이벤트 큐에 넣고, wakeup을 요청한다면 이벤트 큐에서 레디 큐로 옮깁니다. 그런데 여기서도 문제가 생깁니다. 생산자와 소비자가 번갈아가면서 수행된다는 전제 조건도 없고, 생산자가 하는 일과 소비자가 하는 일이 모두 Atomic하지 않아서 상호 배제가 만족하지 않는 등의 문제가 발생할 수 있습니다.
Semaphores
생산자 소비자의 그런 문제점을 해결하기 위해, 두 가지 연산(Up, Down)으로 상호 배제와 동기화를 만족하는 아이디어를 제시했습니다. 두 연산은 Atomic하고, High-level연산입니다. 또한 운영체제 시스템 상에서 구현되어 있습니다. Semaphores는 정의에 따라 count가 모든 정수의 값이 가능한 방법과 count가 0이상의 값만을 가지는 방법이 있습니다. Count를 모든 정수의 값이 가능하도록 할 경우 down을 시행할 시 count를 1 감소시키고 count가 0보다 작으면 해당 프로세스를 sleep시킵니다. Up을 시행할 시 count를 1 증가시키고 count가 0보다 작거나 같으면 해당 프로세스를 wakeup합니다. 즉, count의 초기값이 0이라면 count가 음수일 때의 수는 sleep상태의 프로세스 수입니다. Count를 0이상의 값만을 가지게 할 경우 down을 시행할 시 count가 0보다 클 때에만 count를 1 감소시키고 만약 count가 0이었다면 해당 프로세스를 sleep시킵니다. Up을 시행할 시 sleep상태의 프로세스가 만약 있다면 프로세스 하나를 ready상태로 보냅니다. 만약 잠든 프로세스가 없다면 count를 1 증가시킵니다. Semaphore로 구현한 생산자/소비자 문제 우선 아이템의 개수를 가리키는 n과 임계 구역에 들어갈 수 있는 프로세스의 수 mutex, 비어있는 공간의 개수 e가 있습니다. 각각 append와 take를 시행하기 전에 mutex를 down시켜 상호 배제를 구현합니다. (down연산은 Atomic하기 때문에 둘 중에 하나가 우선적으로 시행되고, 나머지는 mutex의 값이 0이므로 sleep하게 됩니다.) 생산자는 아이템을 만들고, e를 0까지 down하고, n을 N까지 up시키는 연산을 반복합니다. 소비자는 n을 0까지 down하고, e를 N까지 up하고, 아이템을 가져오는 연산을 반복합니다. 각각의 변수가 최소/최대값에 도달하면 sleep하게 되고, 다른 프로세스에 의해 wakeup합니다. 이 연산들은 모두 Atomic하기 때문에 race condition이 일어나지 않고 수행됩니다.
Priority Inversion
만약 프로세스가 T1, T2, T3로 세 가지가 있고, 우선순위는 T1>T2>T3순이라고 할 때 T3가 먼저 접근하다가 T2를 사용하게 되면 T1이 T2때문에 기다리게 되는 경우가 생깁니다. 이러한 경우가 우선순위 역전이고, 이를 해결하기 위해 T3가 먼저 접근하다가 T1이 접근을 시도할 때, T3에게 T1의 우선순위를 상속합니다. 이렇게 되면 T3가 T2보다 우선순위가 높아지므로 우선순위 역전이 발생하지 않습니다.
Mutexes
어셈블리어로 만들어져 있는 mutex연산은 상호 배제를 구현할 때 복잡한 up down보다 간단하게 하기 위해 만들어졌습니다. MUTEX는 공유 변수이고 앞에서 봤던 TSL과 거의 동일하게 진행합니다. 만약 REGISTER의 값이 0이라면(자기가 LOCK을 걸었음) 임계 구역에 접근하도록 하고, REGISTER의 값이 1이라면(다른 누군가가 이미 LOCK을 걸었음) thread_yield(잠시 쉼)합니다. 운영체제를 기반으로 동작하는 것이 아니라 쓰레드들 간 자체적으로 구현되어 있는 것이므로 보다 효율적일 수 있습니다. 다만 Mutexes는 상호 배제만 제공할 뿐 동기화는 제공하지 않으므로 condition변수를 이용해 이를 구현합니다. condition변수는 sleep과 wakeup을 하는 매개체가 되어 작동합니다.
Monitors
위에서 살펴본 것처럼 Semaphore에서 up과 down연산은 결국에는 그 수가 맞아야 프로그램이 제대로 동작합니다. 그러나 시스템은 굉장히 복잡하게 설계되어 있기 때문에 그 수가 맞지 않을 수도 있습니다. 그래서 동기화와 같은 것들을 ‘사용자가 아니라 컴파일러 수준에서 맞췄으면 좋겠다’라는 생각이 들어 Monitor라는 개념이 생기게 되었습니다. Monitor 객체를 컴파일러가 만들게 되는데, 이 객체 안에는 각종 변수들과 producer과 consumer이 존재합니다. 각각의 절차들을 컴파일러가 임의적으로 동시에 수행할 수 없게 합니다. 즉, 상호 배제가 원천적으로 이루어지므로 사용자 입장에서는 두 절차가 동시에 수행될 때를 고려할 필요가 없는 것입니다. 다만 Monitor의 단점은 컴파일러가 수행해야 하는 작업이 더 복잡해진다는 것입니다. 예를 들어 어떤 프로세스가 작업하다가 중간에 sleep상태일 때, 다른 프로세스가 Monitor에 들어와 작업할 수 있고, 그 프로세스가 sleep상태의 프로세스를 wakeup시킬 수 있습니다. 이 때 Monitor에는 두개의 프로세스가 들어올 수 없으므로 이것에 대한 처리가 필요합니다.
Hoare’s Monitor
이 방식은 어떤 프로세스(P1)가 다른 프로세스(P2)를 깨우면, 즉시 깨워진 프로세스의 작업을 수행하고 그것을 마친 뒤 깨운 프로세스의 작업을 수행합니다. 왜 그런 방식을 취하냐면, 만약 P1이 프로세스를 깨운 후 그대로 작업을 마친다면, P2가 깨어나는 조건을 해칠 수도 있기 때문입니다. 이는 프로그램이 동작하는 논리에 맞지 않습니다.
Lampson & Redell’s Monitor
이 방식은 Hoare의 주장과 반대로 동작합니다. P1이 P2를 깨우면, 일단 P1을 마치고 P2를 작업하는 방식입니다. 효율성 측면에서 그렇게 동작하는 것이 유리합니다. 그러나 Hoare가 주장했던 것처럼 P2가 wakeup되는 조건이 훼손될 수 있을 것 같습니다. 이 때는 조건을 if가 아닌 while로 처리하면서 해결합니다. 깨어나면 다시 조건을 판별해 에러가 날 가능성을 없애기 때문입니다.
Lock-free Data Structure
앞에서 구현했던 TSL등의 방식으로 작업을 Atomic하게 구현하지만, 그 연산이 많아질수록 lock신호가 굉장히 많아져 성능이 나빠질 수 있습니다. 따라서 많은 자료구조를 Lock-free형태로 구현하고자 하는데, 이를 위해 CAS명령어를 사용할 수 있습니다. CAS명령어는 인자1(현재 주소)과 인자2(불러왔던 주소)가 같은지를 비교하고, 같으면 인자3과 인자1을 교환합니다. 만약 현재 주소와 불러왔던 주소가 같으면 작업 사이에 다른 프로세스의 개입이 없었다고 간주하고 정상적으로 수행합니다. 만약 현재 주소와 불러왔던 주소가 다르면 CAS를 수행하기 전에 다른 프로세스에 의해 값이 바뀌었다는 것을 의미하므로 다시 시도합니다. 다만 주소를 이용해 다른 프로세스가 접근했는지(접근중인지)를 판별하기 때문에, 만약 다른 프로세스가 접근중이지만 주소를 바꾸지 않았다면 ABA문제가 발생하게 됩니다.
Message Passing
이제는 생산자, 소비자뿐 아니라 메시지를 주고받는 형태의 send receive를 알아봅시다. 일단 sender와 receiver는 각각 기다릴수도, 기다리지 않을 수도 있습니다. 그런데 리시버는 보통 기다리는 것이 일반적입니다. 만약 기다리지 않는다고 해도 딱히 할 일이 없기 때문입니다. Blocking send, blocking receive의 경우 send는 메시지를 보낸 후 receive가 메시지를 전달받을 때까지 기다리고, receive는 메시지를 받을 때까지 기다립니다. Nonblocking send, blocking receive의 경우 send는 메시지를 보내고 기다리지 않습니다. 이러한 형태가 우리가 메시지를 주고받는다고 생각했을 때 가장 일반적이겠습니다. Nonblocking send, nonblocking receive의 경우 receive도 기다리지 않을 수 있습니다. 하지만 만약 send를 nonblocking하게 만들면 메시지를 누군가가 가지고 있어야 합니다. 메시지를 저장하는 큐가 필요하고, 유한한 저장 공간을 사용하게 됩니다.
Addressing
우선 각각의 주소로 보내려 할 때, 이 주소를 프로세스의 번호로 사용할 수 있다고 생각할 수 있습니다. 그러나 프로세스의 번호는 프로세스가 실행될 때 운영체제에서 임의로 정해주는 것이기 때문에 주소를 지정하고 싶은 프로세스가 몇 번인지 알아내는 것이 불가능합니다. 그래서 mailbox라는 번호를 지정한 큐를 사용하게 됩니다. Send가 10번과 같은 특정 번호의 큐에 보내면, receiver도 10번 큐에서 메시지를 가져가면 됩니다. 이는 인터넷 통신에서 포트가 동작하는 것처럼 1 to 1, n to 1, n to n, 1 to n이 모두 가능합니다.
많은 운영체제가 프로세스들 간 메시지를 주고받을 수 있도록 기능을 제공합니다. Semaphore를 이용해서 메시지 패싱을 구현할 수도 있고, 자바에서는 Monitor기능을 이용해 이를 구현할수도 있습니다.
Barriers
배리어 연산은 여러개의 프로세스가 동작할 때, 각 프로세스가 다른 프로세스들이 특정 지점까지 모두 완료될때까지 기다리도록 하는 것입니다. 쓰레드 조인이 필요하거나, 다수의 쓰레드가 행렬의 일부를 계산하는 등의 경우에서 필요합니다.
오랫동안 CPU를 점유하는 CPU-bound process와 짧은 CPU 사용과 대부분의 시간을 I/O대기에 할애하는 I/O-bound process가 있습니다. 우리가 자주 사용하는 웹브라우저, word등의 프로그램은 모두 I/O-bound process입니다. 프로세스의 우선순위를 정할 때, CPU-bound와 I/O-bound중 어떤 프로세스에 우선순위를 더 높게 주어야 더 효율적으로 시스템이 작동할까요? 정답은 I/O-bound입니다. 그 이유는 I/O-bound는 대기 시간이 길기 때문에 기다리는 동안 CPU-bound 프로세스를 수행하면 됩니다. 만약 CPU-bound가 우선순위가 더 높다면 I/O-bound는 불필요한 대기 시간이 더 생기게 됩니다. (활용도가 떨어집니다.)
Scheduling
Scheduling은 세가지로 나눠질 수 있습니다. (혹은 I/O를 포함한 네가지) 우선 프로세스를 만들고자 할 때 운영체제에서 Long-term scheduling을 수행합니다. 이 때도 스케줄링을 하므로 만약 시스템의 혼잡도가 높다면 프로세스를 바로 만들지 못할 수도 있습니다. Medium-term scheduling은 Ready나 Blocked상태의 프로세스를 Suspend할 때 사용됩니다. 마찬가지로 시스템의 혼잡도가 높다면 자원을 확보하기 위해 수행합니다. 유닉스는 이 스케줄링을 Swapper라고 합니다. Short-term scheduling은 Ready상태를 Running으로 보냅니다. 앞에서 논의했던 대부준의 스케줄링이 이 스케줄링에 해당합니다.
스케줄링 알고리즘은 Batch, Interactive, Real time 으로 크게 세가지로 나눌 수 있습니다. Batch는 예전 중대형 컴퓨터에서 사용하던 방식으로, 큰 작업을 하나씩 통째로 가져와 수행합니다. 현재에도 은행과 같은 곳에서 통계값을 내거나 할 때 사용됩니다. Interactive는 번갈아가면서 수행하는 것입니다. Real time은 실시간이므로, 일정 시간(deadline)안에는 꼭 응답을 해야 합니다.
우선 모든 스케줄링 알고리즘은 프로세스에게 공평한 몫(우선순위도 고려)의 CPU 사용 시간을 주어야 합니다. (Fairness) 또한 사용자가 설계한 대로 동작해야 합니다. (Policy enforcement) 모든 시스템이 busy하게 사용되어야 합니다. (Balance)
이때 각 스케줄링 알고리즘별로 목표가 조금씩 다른데, Batch의 경우 Throughput이 굉장히 중요합니다. Throughput이란 시간 당 처리량인데, 이 Throughput이 높아야 합니다. 다음으로 Turnaround time을 줄여야 합니다. Turnaround time은 작업을 제출한 시간부터 끝날 때까지의 시간인데, 이 Turnaround time을 줄여야 합니다. 또 CPU 사용량이 높아야 합니다.
Interactive systems는 Response time이 좋아야 합니다. Response time이 좋으려면 그만큼 자주 번갈아 가면서 실행해야 하는데, Throughput을 중시하는 Batch와는 반대입니다. 또한 사용자의 기대치에 맞게 동작해야 합니다. 예를 들어 Sun OS의 스케줄러의 경우 사용자 입출력을 받는 경우 우선순위를 아주 높게 주어 사용자의 기대치에 맞게 동작하도록 했습니다.
Real-time은 deadline이 존재하고, 그 deadline을 만족시키는 것이 가장 중요합니다. 무조건 만족시켜야 하는 hard real-time과 deadline을 만족시키는 것이 권장되는(퀄리티를 위해) soft real-time이 있습니다. 또한 예측 가능해야 합니다.
Batch System의 스케쥴링
First-come first-served (FCFS)
FCFS는 먼저 온 순서대로 처리하는 간단한 알고리즘입니다. 그런데 먼저 도착한 프로세스의 CPU 사용 시간이 길고 나중에 도착한 CPU 사용 시간이 짧은 경우, 나중에 도착한 프로세스는 불필요한 대기 시간이 길어지므로 Turnaround time이 좋지 않습니다.
Shortest Job First
FCFS의 Turnaround time이 좋지 않다는 점을 개선하기 위해, 도착한 프로세스 중 가장 CPU 사용 시간이 짧은 프로세스를 우선적으로 수행합니다. 따라서 FCFS보다 Turnaround time이 더 좋습니다. 이때 이 방식은 non-preemptive하기 때문에 실행 중 잠시 중단하지는 않습니다.
Short Remaining Time Next
Shortest Job First를 preemptive하게 수행하는 방식입니다. 때문에 각 time(주기)별로 도착한 프로세스들의 남아있는 CPU 사용시간을 비교해 그 시간이 가장 짧은 프로세스를 우선적으로 수행합니다. 이 방식을 이용하면 Shortest Job First보다도 더 짧은 평균 Turnaround time을 기대할 수 있습니다.
Highest Response Ratio Next
바로 앞의 Short Remaining Time Next의 경우 매우 긴 프로세스가 먼저 들어오고, 중간에 짧은 프로세스가 계속해서 들어오면 매우 긴 프로세스가 계속해서 밀릴 수 있습니다.(starvation) 그래서 프로세스가 기다린 시간도 고려해야 하는데, Response Ratio라는 것을 정의해 다음 실행할 프로세스의 기준으로 사용합니다. Response Ratio는 (기다린 시간 + 남은 실행시간)/(남은 실행시간) 입니다. 처음에는 남은 실행시간을 기준으로 수행되겠지만, 기다린 시간이 길어지면 길어질수록 그 프로세스에 대해서도 우선순위가 높아질 것입니다.
Interactive Systems의 스케줄링
Round-robin scheduling
Time quantum을 기준으로 번갈아 가면서 수행합니다. 프로세스를 수행한 지 Time quantum만큼의 시간이 지나면 그 프로세스를 큐의 맨 끝에 놓고 다음 프로세스를 수행하는 방식입니다. 여기서 time quantum을 어느 정도로 해야 하는지 생각해야 합니다. Time quantum이 짧으면 응답 속도는 빨라질 수 있지만, 스케줄링 오버헤드(문맥교환과 같은 비용)가 커집니다. Time quantum은 프로세스가 입력을 요구하는 시간보다 조금 더 긴게 이상적입니다. 왜냐하면 time quantum이 입력을 요구하는 시간보다 짧을 경우 프로세스가 실행 중 한번 멈추고, 다른 프로세스를 모두 실행하고 다시 돌아와 입력을 요구하기 때문입니다.
Virtual Round-Robin
I/O를 수행한 프로세스들은 Ready Queue가 아니라 Auxiliary Queue로 들어갑니다. 프로세서가 다음에 수행할 프로세스를 고를 때 Ready Queue보다 Auxiliary Queue를 더 우선적으로 고릅니다. 이 방식을 이용하면 I/O이벤트가 발생하면서 time quantum을 모두 쓰지 못하고 손해를 본 프로세스들에게 그 만큼의 시간을 공평하게 할당할 수 있습니다.
Priority Scheduling
우선순위마다 큐(Ready queue처럼)를 다르게 만들어서 우선순위가 높은 큐부터 Round-Robin을 수행하는 것입니다.
Multilevel Feedback Queue
앞에서 논의했던 것처럼 I/O bound 프로세스가 CPU bound 프로세스보다 우선순위가 더 높은 것이 효율적입니다. 따라서 I/O bound 프로세스가 더 높은 우선순위 큐에 위치해야 합니다. Multilevel Feedback Queue는 이를 어떻게 구현하는지를 보여줍니다. 만약 어떤 프로세스가 입출력 없이 CPU만 사용하다가 마치면 우선순위가 더 낮은 큐에 들어가게 됩니다. 만약 입출력이 발생했다면 그 프로세스는 blocked되어 돌아올 때 다시 우선순위의 최상단에 위치하게 됩니다. 다만 이 방식에도 우선순위가 낮은 프로세스는 계속 실행하지 못하는 starvation이 발생할 수 있습니다. 그래서 기다린 시간이 길어지면 우선 순위를 높이는 aging mechanism이 필요합니다.
Short Process Next
실행 시간이 가장 짧을 것 같은 프로세스를 우선적으로 수행합니다. Batch 스케줄링에서도 비슷한 알고리즘을 다뤘습니다. 이때 실행 시간은 이전에 수행했던 데이터를 기준으로 정하게 됩니다. 만약 산술 평균만으로 실행 시간을 예측하게 된다면 사용자의 패턴이 바뀔 때 유동적으로 실행 시간이 변하지 않습니다.(과거에 많은 데이터가 있을 수 있기 때문입니다.) 따라서 마지막 사용 시간에 가중치 a를 할당하는 Exponential Averaging을 사용합니다. 이렇게 하면 사용자의 변화하는 패턴에 적응을 더 빠르게 할 수 있습니다.
Guaranteed Scheduling
N개의 프로세스가 있다면, 각 프로세스마다 딱 1/N씩 만큼의 시간을 할당해 완전히 공평하게 나누는 방식입니다. 이와 유사하게 리눅스에는 Fair Share Scheduling이 있습니다.
Lottery Scheduling
각 프로세스에 복권을 부여하고(부여한 복권의 수는 우선순위와 비슷합니다.) 모든 복권을 추첨해 당첨된 프로세스를 실행하는 방식입니다. 프로세스마다 복권을 교환해 실행 비율을 조절하는 것도 가능합니다.
Fair-share Scheduling
용어 그대로 공평한 몫으로 나눌 수 있도록 합니다. 만약 1번 사용자가 2개의 프로세스를 사용하고, 2번 사용자가 1개의 프로세스를 사용했을 때 각 프로세스에 1/N만큼의 시간을 할당하면 사용자 입장에서는 공평하지 않습니다. 사용하는 프로세스의 수가 다르기 때문입니다. 이렇게 생각했을 때, 각 사용자는 프로세스를 최대한 많이 만들어서 실행하는 것이 유리합니다. 그래서 이 방식에서는 각 프로세스를 사용자(그룹)으로 나누어 공평하게 시간을 나누고, 그 그룹 안에서도 시간을 공평하게 나누어 프로세스를 수행합니다. 어떤 사용자가 프로세스를 많이 만들어도 그 사용자에게 할당된 시간 이상은 갖지 못합니다.
Scheduling Mechanism vs. Scheduling Policy
유닉스와 같은 운영체제를 개발할 때 스케줄링 메커니즘과 스케줄링 정책을 구분해야 합니다. 커널은 기본적인 다양한 스케줄링 메커니즘을 가지고 있어야 하고, 어떤 스케줄링 정책을 내놓으면 그에 맞게 동작하고, 변환이 자유로워야 합니다.
Traditional Unix Scheduling
Multilevel feedback queue를 사용했고, 한번 실행하면 우선순위가 떨어지고, 기다린 만큼 우선순위가 올라가는 방식입니다. 따라서 매번 우선순위를 다시 계산하는데, 각 프로세스별로 nice라는 값이 있습니다. 시스템 관리자는 nice값을 조절할 수 있고 이 nice가 낮을수록 우선 순위는 높아집니다. 하지만 일반 사용자는 nice값을 낮출 수는 없지만 이 값을 높여 프로세스를 더 가끔 수행되게 할 수 있습니다. 각 주기에서, 프로세스의 Priority는 이전 주기의 Priority에 CPU Count의 1/2을 더한 값으로 산정합니다. 이렇게 하면 실행할 때 우선순위가 낮아지고, 기다릴 때 우선순위가 높아질 수 있습니다.
BSD and SVR3 Scheduling
SVR3는 오리지널 유닉스 시스템 기반입니다. 마찬가지로 1/2씩 나누어 스케줄링을 합니다. 프로세스의 수가 적을 때는 cpu count가 구분될 수 있는데 프로세스가 많은 경우 cpu count가 금방 0이 되어버려 프로세스마다 기다린 정도가 구분되지 않습니다. 따라서 BSD에서는 decay의 정의를 약간 변경합니다. Decay = (2실행가능 프로세스의 수)/(2실행가능 프로세스의 수+1) 이렇게 하면 실행가능 프로세스의 수가 많을수록 decay가 1에 가까워져서 cpu count가 천천히 줄게 됩니다.
Linux Scheduling
리눅스 스케줄링에는 real-time 쓰레드를 위한 스케줄링 클래스(우선순위가 높음) 와 기타 쓰레드를 위한 스케줄링 클래스(우선순위가 낮음) 를 가지고 있습니다.
O(1) : Linux SCHED_OTHER Scheduling
알고리즘이나 자료구조 시간에 봤듯, O(1)은 시간 복잡도가 상수로 어떤 인풋이 들어와도 처리하는 시간이 동일한 알고리즘을 뜻합니다. 또한 그만큼 효율적이라는 의미입니다. 이전에 살펴보았던 유닉스의 스케줄링 알고리즘은 CPU-bound와 I/O-bound의 우선순위를 각각 다르게 부여하기 위해, 또 그것을 구현하기 위해 복잡한 알고리즘을 사용했습니다. 그렇기 때문에 스케줄링 오버헤드가 굉장히 큽니다. 이 O(1)도 마찬가지로 I/O-bound 프로세스에게 더 높은 우선순위를 부여합니다. 실행할 쓰레드들은 active queue의 0부터 시작하는 일정 번호에 들어있습니다. 0번 큐부터 탐색해 만약 그 번호의 큐의 값이 1이라면 쓰레드가 존재한다는 의미이고 그 쓰레드를 timeslice만큼 실행합니다. 실행하고 나면 expired queue에 할당하고 active queue가 비게 되면(모든 쓰레드들을 한 번씩 실행하면) expired queue를 active queue로 사용합니다. 만약 실행한 쓰레드가 인터액티브 태스크라면 다시 active queue에 넣어 금방 다시 실행되게끔 합니다. Active queue에서 expired queue로 전환할 때 새로운 타임 슬라이스를 계산하게 되는데, 실행시간 대비 휴면시간 비율과 nice값에 비례합니다. 하지만 O(1)에도 문제가 있는데 우선 nice값이 차이나는 정도가 timeslice가 차이나는 정도와 비례하지 않습니다. 타이머 인터럽트를 기반으로 스케줄링 하는 것이기 때문에, timeslice를 timertick보다 더 정밀하게 설정할 수 없습니다. 인터액티브 프로세스가 너무 자주 실행될 수 있습니다.
CFS
O(1)을 개선하기 위해 새롭게 만들어진 스케줄러로, nice값에 비례해 weight를 할당하고, 그 weight에 비례해 timeslice를 할당합니다. Weight 테이블을 이용해 nice값의 차이와 weight의 차이가 비례하도록 했기 때문에, nice값의 차이와 timeslice의 차이는 비례합니다. 또한 timeslice가 정밀하지 않다는 점을 해결하기 위해 virtual runtime 개념을 도입합니다. 두 프로세스의 실제 수행 시간에 scale factor를 곱하면 두 값은 같아야 합니다. 하지만 문맥교환 주기에 따라 그렇지 않을 수 있습니다. 만약 두개의 virtual runtime이 다르다면 덜 수행한 프로세스의 시간을 보상합니다. 모든 태스크에는 virtual runtime이 있고, 항상 균등하게 유지하려고 합니다. 따라서 이 값은 계속 증가할 수밖에 없습니다.
UNIX SVR4 Scheduling
160개의 우선순위 큐가 있고, 클래스를 세 개 (Real time, Kernel, Time-shared)로 나누어 구분합니다. 프로세스가 실행하다가 중간에 시스템을 호출하고 리턴할 때, 리턴하기 직전에 스케줄링을 수행합니다. 그런데 real time과 같은 프로세스에는 이 시간 때문에 반응 속도가 떨어질 수 있습니다. 따라서 리턴하기 직전 뿐만 아니라 중간에 여러 개의 스케줄링을 할 포인트(preemption points)를 만들었습니다.
Windows Scheduling
윈도우즈 운영체제는 32개의 우선 순위를 가지고 있습니다. 마찬가지로 preemptive scheduling입니다. 프로세스에 base priority를 부여하고, 각각의 쓰레드가 base priority를 기준으로 우선 순위가 동적으로 변화하면서 동작합니다.
Dining Philosophers Problem
동기화 문제를 보여주는 예제로, 철학자는 원형 테이블에 앉아 식사를 하려고 합니다. 음식의 양 옆에는 포크가 있고, 철학자는 양손으로 두 개의 포크를 들어야 식사를 할 수 있습니다. 만약 모든 철학자가 거의 동시에 왼쪽에 있는 포크를 집었다면, 다음으로 오른쪽에 있는 포크를 집어야 하는데 아무도 집을 수 없습니다. 결국 아무도 식사를 하지 못하게 되는 상황이 발생할 수 있습니다.(deadlock) 이러한 문제를 해결하기 위한 방법으로는 홀수 번째 철학자는 왼쪽 포크 먼저, 짝수 번째 철학자는 오른쪽 포크 먼저 집도록 해 처음에 집기 시작할 때 충돌이 발생하도록 합니다. 먼저 집은 철학자는 식사를 할 수 있을 것입니다. 어떤 철학자가 식사를 하지 않았고 양 옆의 철학자가 식사를 하는 중이 아니라면 식사를 하도록 합니다. 만약 그렇지 않으면 철학자는 잠시 쉴 것이고, 양 옆의 철학자의 식사가 끝난 후 그 철학자를 깨워줄 것입니다.(가능하다면)
Readers and Writers Problem
데이터베이스 같은 곳에서 많이 발생합니다. Reader는 여러명이 동시에 접근하는 것이 가능하지만, writer가 접근하고 있을 때에는 불가능합니다. Reader가 접근할 때마다 카운터를 증가시켜 첫 번째 reader라면 db를 가져오고(가져올 수 있을 때까지 대기), 작업을 마칠 때마다 카운터를 감소시켜 마지막 reader라면 db를 반납합니다. Writer는 단순히 db를 가져오고(가져올 수 있을 때까지 대기), 작업을 마친 후 db를 반납합니다. 다만 이러한 방식의 문제는 writer가 starvation할 수 있습니다. Writer는 대기하고 있을 때, reader가 계속해서 접근하면 writer는 아무것도 할 수가 없습니다. 이를 해결하기 위해서는 현재 대기하고 있는 writer가 들어온 이후로 진입하는 reader를 차단함으로써 가능합니다. 이 때는 writer가 reader보다 더 우선적으로 수행된다고 볼 수 있습니다.