인강 5) CPU 스케쥴링

강의 url www.kocw.or.kr/home/search/kemView.do?kemId=1226304

1) CPU 스케줄링과 디스패처가 필요한 이유와 개념에 대해 알아본다.
2) CPU 스케줄링의 여러가지 알고리즘에 대해 알아본다.
3) CPU 스케줄링의 여러가지 알고리즘 중 멀티레벨 큐와 멀티레벨 피드백 큐에 대해 알아본다.

프로세스의 사이클

- 프로세스의 상태를 ready, running, blocked(=wait), suspended blocked, suspended ready 으로 5가지로 나눌 수 있다. CPU와의 관계로 Burst time 개념으로 단순화 하였을 때 다음 그림과 같이 표현할 수 있다.

프로세스는 크게 CPU를 쓰거나, I/O를 쓰거나로 생애 주기를 구분할 수 있다.

- 프로세스는 연산할 때 CPU를 필요로 하고, device를 제어할 땐 I/O가 필요한데 어떤 burst time이 필요한지는 프로세스의 목적마다 다르다. 따라서, I/O burst time 또는 CPU burst time 중 어떤 것이 오래 걸리는 가에 중점을 두기보다는 어떠한 스케쥴링으로 burst time을 분배하는가에 중점을 둘 필요가 있다. CPU burst time을 연속적으로 한 번에 모두 할당해주며 I/O burst time을 추후에 실행할 지, CPU burst time 중 I/O burst time을 중간 중간 마다 할당해주어 연속적인 CPU 작업 시간을 낮출 것인지에 관한 것이다.

CPU burst time의 분포

이는 일반적인 프로세스를 기반한 통계를 도식화한 그래프로 생각된다. I/O bound job과 CPU bound job은 지수분포로 양극화 되어있다.

- CPU의 역할이 많이 필요한 job을 CPU bound job, I/O의 역할이 많이 필요한 job를 I/O bound job이라고 한다. 여기서 job 키워드는 모두 process로 치환 가능하다. 일반적으로 사용자들이 사용하는 process는 사용자의 입력 -> 연산 -> 기계의 출력으로 이루어지는데, 이를 I/O bound job으로 볼 수 있다.
- I/O bound job, CPU bound job 중 CPU를 어느 job에게 먼저 줘야할까? 이에 대한 대답은, 여러 process가 존재할 때 어떤 process에 먼저 CPU를 줄 것인지, 얼마만큼의 시간동안 할당할 것인지 등의 결정하는 CPU 스케쥴링이 대답이 될 수 있다. CPU 스케쥴링은 동일한 성격을 띄는 프로세스가 혼재한다면 큰 토픽이 되지 않을 수도 있었다. 그러나 그래프에서 볼 수 있듯이 둘 다 선형적으로 쓰이는 process보다는 I/O bound job, CPU bound job으로 나뉘기 때문에 큰 이슈이다. 예로, I/O bound job은 CPU를 조금만 쓰면 되는데, 큰 연산을 하는 CPU bound job이 CPU를 본인 job이 끝날때까지 붙잡고 있다면, job은 계속계속 밀릴 수 있기 때문이다. 이로 인해, I/O bound job은 선행되어야하는 CPU job이 완료되지 않아 I/O 작업을 못하면서 시스템의 I/O device resource도 유휴하는 상황이 발생할 수 있다. 이를 해소하기 위해, CPU bound job이 CPU를 사용하는 도중에 제한적인 몇 세컨드 또는 밀리세컨드의 양보를 통해 I/O bound job에게 CPU를 잠깐만 주면 해소할 수 있을 것이다. 결과적으로, CPU 스케쥴링의 목적은 CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용하는데에 있다.

CPU Scheduler & Dispatcher

- CPU Scheduler는 어떤 Process 에게 CPU를 넘겨줄지 결정하는 역할을 하며, Dispatcher는 Scheduler에 의해 이루어진 의사결정에 따라 선택된 Process에게 CPU의 제어권을 넘기는 역할을 한다. 이 과정에서 Context Switch가 발생한다.
- CPU Scheduler와 Dispacther는 이름에 맞는 해당 역할을 하는 운영체제의 코드 일부 부분이다. 
- CPU 스케쥴링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있다.
- 전제 1) CPU의 제어권을 얻게되면 Process의 상태는 ready -> running으로 넘어간다.
- 1) "전제 1"에서 Running Process가 I/O의 Job이 필요하여 I/O를 요청하는 시스템 콜을 날리며 Running에서 Blocked Queue로 진입하여 blocked가 된 경우.
- 2) "전제 1"에서 Running Process가 할당시간 만료로 Timer Interrupt를 통해 Process로 부터 CPU 제어권을 가져올 경우.
- 3) "1"에서 Blocked 된 Process가 I/O job이 완료되어 Interrupt를 통해 Ready로 넘어온 경우. 이 경우, Process의 중요도에 따라 Ready Queue에 대기시키지 않고 CPU의 제어권을 우선적으로 할당 해 줄 경우.
- 4) Running Process가 Terminate할 경우.
 Process Scheduler는 CPU를 넘겨줄 임의의 Process를 의사결정해야한다. 추가적으로, 위 4가지 경우는 크게 두 가지로 나뉘는데 nonpreemptive(비강제적), preemptive(강제적)로 나뉜다. 1번과 4번 경우는 프로세스의 동작에 따라 CPU 제어권을 자진해서 반납하는 경우로 nonpreemptive에 해당하며, 2번과 3번의 경우는 preemptive에 해당한다.

Sceduling Criteria, Performance Index of CPU scheduler

스케쥴러의 성능 척도

- CPU utilization(이용률) : 전체 시간 중에서 CPU가 작업을 수행한 시간
- Throughput(처리량) : 단위시간 당 프로세스의 작업이 완료된 수
- Turnaround time(소요시간, 반환시간) : 특정 process의 실행 시간
- Waiting time(대기 시간) : 한 process가 ready queue에서 대기한 총 시간
- Response time(응답 시간) : request를 날렸을 때 첫 response를 제공받을 때 까지 걸린 시간 (time-sharing environment), CPU의 제어권을 요청하였을 때 최초로 CPU를 얻을 때까지 걸린 시간. 프로세스가 생성되고 나서 최초로 CPU를 얻은 시간과는 개념이 다르므로 유념하자. 여기서 "최초"라는 단어에 조금 주목해야하는데, 항상 CPU의 제어권을 빼앗길 수 있는 것이기 때문에 "최초"라는 단어가 유효하다. 어떤 이유던지 CPU 제어권을 내주거나 빼앗긴, 다음에 다시 CPU를 얻으러 오는 것은 관심사항이 아니다. "최초"의 시간에만 관심을 가진다.

CPU는 비싼 자원으로, CPU의 이용률이 높을수록 좋다. 그리고 처리량은 높을 수록 좋고, 시간 요소는 모두 작을수록 좋다.

Scheduling Algorithm

- FCFS ( First Come First Served ) : 대표적인 nonpreemptive scheduling으로, 먼저 도착한 process의 CPU사용이 끝날 때 CPU의 제어권을 넘겨 준다. **Convoy Effect : CPU burst time이 짧은 Process가 CPU burst time이 긴 것 뒤에서 오래 기다리는 현상이 있다. Convoy : 호송
- SJF ( Shortest Job First ) : CPU Burst Time이 가장 짧은 Process에게 CPU의 제어권을 전달한다. SJF는 최적의 방법론이다. 최적의 방법론임은 주어진 프로세스들에 대해 minimum average wating time을 제시하기 때문이다. SJF는 nonpreemptive 와 preemptive이 scheme으로 사용가능하다. nonpreemptive는 해당 Process의 CPU burst time을 모두 기다린 다음 CPU 제어권을 가져오는 방법이다. preemptive의 방법론은 만약 ready queue의 임의의 새 Process가 들어온 경우, 새 프로세스의 남은 CPU burst 시간Remaining CPU burst time이 현재 CPU의 제어권을 가지고 있는 프로세스의 것보다 짧다면 CPU 제어권을 현재의 것으로부터 가져오는 것이다. 이를 Shortest remaining time first(SRTF)라고 부르기도 한다. 앞에서 SJF가 최적의 방법이라고 적었던 것은, SRTF의 경우를 말하는 것이다. **Starvation : 먼저 arrival한 CPU burst time이 긴 process는 새로 도착하는 짧은 burst time을 가진 process에게 영원히 CPU의 제어권을 받지 못한다. 언젠가는 long job에게도 CPU의 제어권을 받아야한다. **How to determine CPU burst time? : process의 CPU burst time을 어떻게 예측할 수 있는가, if/switch condition, while/for loop 등의 code로 인해 CPU burst time을 결정하기가 어렵다. 임의의 process가 CPU burst time을 얼마나 쓸지 예측은 과거에 해당 process가 얼마나 burst time을 썼는지 정보를 전제로하여 추론하는 방법이 있다. 지수평활법exponential averaging을 활용한다. 음, Operation Research 뒤로 오랜만에 듣는구만...

s_i를 예측값, x_i를 실제 수행시간으로 보면된다. 인터넷 강의에서는 x_(t-i)로 표현하였다. 자세한 것은 나중에 시간과 여력이 될 때 볼 것이다. 수식의 전체적인 의미는 최근의 수행 시간을 비중을 높게, 이전의 예측 시간을 비중을 점진적으로 낮게 보아 그 다음 수행시간 예측을 연산하는 것이다.

- Priority Scheduling : 우선순위가 높은 process에게 CPU의 제어권을 준다. SJF 또한 일종의 priority scheduling 이다. process의 남은 시간이 우선 순위로 본 것과 같다. 그로 인해 **Starvation 문제점을 가지고 있다. (어떠한 방식으로 priority를 제공하든 간에...) 이러한 해결책으로 **Aging 개념을 도입하여, 오래 기다린 process의 우선순위를 높여주는 방법론을 제시한다. 교수님의 여담으로, 한국 사회에서 경로 우대를 운영체제에서도 적용이 된다. 나이가 드신 분들께 화장실을 먼저 양보하는 것처럼... 나이가 들면 장의 활동이 편치 않기때문에... 
- Round Robin (RR) : timer interrupt와 큰 연관이 있다. timer interrupt가 interrupt를 걸어 운영체제가 CPU 제어권을 다음 process에게 넘겨준다. preemptive 방식인데, Round Robin은 그러한 동작 방식 중에서 CPU의 제어권을 필요로 하는 모든 process는 동일한 크기의 CPU 제어권 시간(할당 시간, time quantum)을 가지게끔 제공하는 방식을 뜻한다. 임의의 n개의 process가 있고 q 만큼의 할당 시간을 가질 때, 어떠한 process도 (n-1)*q 시간 이내에 CPU 제어권을 한 번은 갖게 됨을 보장한다. 즉, response time이 짧다. Round Robind의 q가 큰 경우 큰 흐름상 FCFS가 된다. 그리고, q가 작은 경우 context switch overhead가 크다는 단점이 있다. 그리고 모든 Process가 CPU burst time이 거의 동일한homogeneous 경우, 굳이 모든 process가 조금씩의 시간동안 CPU의 제어권을 받아가며 context switch하다 모든 process가 동일한 exit time을 갖게 되므로 긴, average turnaround time을 가지며 좋은 효과를 가진다고 볼 수는 없다. CPU burst time이 거의 다른heterogeneous인 경우, long job, short job 모두 합리적으로 CPU 제어권을 갖는데에 의의가 있다.

- Multilevel Queue : Ready queue를 여러개로 분할하는 방식으로, 각 queue를 독립적인 스케쥴링 알고리즘으로 제시하고, 큐에 대한 스케쥴링이 별도로 필요로한다. 예로, queue를 크게 두 가지 방식인 foreground (interactive), background(batch - no human interaction)으로 나눌 수 있다. foreground queue에는 RR로, background queue에는 FCFS로 제시한다. 그리고 그 전체적인 queue에서 process를 가져와 CPU 제어권을 제공하는 방식이 주어질 수 있다는 것이다. CPU의 제어권을 주는 방식은 foreground queue의 Process를 모두 완료한다음 background queue의 Process에게 CPU의 제어권을 줄 수 있다. 또는 foreground queue에 가중치를 조금 더 주고 background queue에 가중치를 덜 주는 방식도 있다. 이러한 방식은 조금 더 어려운 내용이다. 그래서 강의에서는 queue에 대한 자세한 스케쥴링은 다루지 않으신 듯하다.
- Multilevel Feedback Queue : 앞서 설명한 Multilevel Queue 방법에서는, queue 내부의 각 각의 process는 해당 level의 queue의 rule에만 의존한다. 그러나 이 방식은 임의의 process가 임의의 A queue에 있다가 특정 로직에 따라, 예를 들어 한번이라도 CPU 제어권을 가졌다는 이벤트가 있을 경우, 임의의 B queue로 이동하여 해당 queue의 rule을 따르게 되는 방식이다.

- 이 외에도, Processor가 여러개인 환경에서도 Scheduling을 수행하는 방식이 있다. 이 방식은 훨씬 복잡해진 내용이다.
- 여러개의 Processor가 동일한 수행능력을 가진 경우 : Queue에 한줄로 세운다음 각 Processor가 알아서 꺼내가는 방법이 있다. 하지만, 임의의 process가 반드시 특정 processor에게 처리되어야 할 때의 케이스는 복잡해질 수 있다. 뒤에 글은 너무 길며 사족이다. 읽지 않아도 된다. 교수님은 여기서 잠깐 예제를 드시는데, 교수님이 머리를 자르러 미용실에 들렀을 때 헤어 디자이너가 여러명이 있는 예에 대해서 다루신다. 특정 디자이너에게 자르고 싶은 경우가 바로 이 예다. 본인은 머리를 자르는 텀이 긴데, 일반적으로 아무 디자이너에게 자르지만 몇 번 자르다가 디자이너의 스타일이 마음에 들면 지정 디자이너로 선정한다고 한다. 그런데 텀이 길다보니 몇 번 찾아가다가, 일 년이 조금 넘으면 바뀐다고 한다. 헤어 디자이너 직종 자체가 매우 힘든 직업으로, 몇 번 미용실(직장)을 옮기다가 헤어 디자이너 직종을 그만두는 경우가 허다하다고 한다. 어쩌면 헤어디자이너가 어느 미용실로 옮겨갔는지, 헤어 디자이너 등록하는 서비스가 있으면 좋을 듯 하다. 좋은 디자이너가 있다면 금방 소문이 나서 그 미용실이 잘 될 것이기 때문이다. 그런데 software 직종도 마찬가지일 것이다. 프로그래밍을 잘하고 소프트웨어 개발에 일가견이 있다면, 도전적인 프로젝트를 하다가 망했다고 하더라도, 금방 새로운 프로젝트에 의기투합하여 인볼빙 될 수 있는 것이다. 요즘의 직장개념은 정년까지 있는 개념이 아닌, 조건이 더 좋으면 옮기기도 하는게 일반화가 되어있기 때문에, 몸 값을 올리는 게 중요한게 아니라 실력을 올리는게 중요한 것이다. 실력을 올리면, 개발직을 하다가 잠시 그만 뒀다 하더라도, 또 여러군데에서 오라고 하는게 삶이다. 사족은 여기까지인데, 2017년 강의 내용이지만 2022년에도 공감이 가는 내용이라 적어보았다.
- Load Sharing : Load balance라고도 하는데, 일부 Processor에게 과도하게 process가 몰리지 않도록 하는 메커니즘이다. 각 Processor마다 각 각의 Queue를 두게 하는 방법 또는 공동의 Queue를 두어 공평하게 process를 가져가게 하는 방법이 있다. 두 경우 모두 운이 없어, 특정 CPU에게 CPU burst time이 높은 CPU bound job이 몰릴 수도 있다. 이러한 문제를 해결하는 방법은 이 강의에서 다룰 영역의 바깥에 위치하고 있다. 복잡한 문제이다. 어쩌면, 화장실 한 줄로 서느냐 여러줄로 서느냐의 문제인데, 요새는 사회적으로 한 줄 서기를 추천하는 것 같다.
- Symmetric Multiprocessing (SMP) : 모든 Processor가 동일한 권한을 가지고 각자 알아서 scheduling을 수행함.
- Asymmetric Multiprocessing : 하나의 Processor가 우수한 권한을 가지고 다른 Processor의 scheduling을 추가적으로 제어함.

- Real-Time scheduling : Real-Time system은 Time sharing system과 다르게 process에 dead line이 존재하는 경우다. 크게 Hard Real-time system과 Soft Real-time computing이 있다. Hard Real-time system은 dead line을 넘길경우 큰 failure이기 때문에 엄격히 dead line을 지킨다. 모든 process에 대한 dead line을 지키기 위해, 위에서 설명한 모든 scheduling, Online Scheduling(process가 도착함에 따라 process의 CPU 제어권이 결정되는 scheduling)보다는 offline scheduling을 수행한다. offline scheduling이란 임의의 프로세스가 언제 어떻게 CPU의 제어권을 가져갈 것인지에 대해 이미 결정되어 있는 것이다. 어떠한 process가 언제 도착할 것인지 이미 OS에서 알고 있고 대비하는 것이다. 그래서 보통 Real-time system에서는 process들이 특정 주기적으로 꾸준히 실행되는 경우가 많다. 그리고 Soft real-time computing은 그보다 조금 더 완화된 경우인데, 예로 스트리밍 서비스가 있다. 초당 몇 프레임을 처리해야하는 경우, 지키지 않은 경우 사용자의 불편 정도를 초래하는 경우이다. processor가 초당 몇 프레임을 연산한다음 휴식하는 주기를 가지게 되는데, 그러한 스케쥴링에서도 주기를 찾을 수 있는 것이다. 여러분이 사용하는 동영상 스트리밍은 일부 지연 현상이 발생하는데 그 경우 deadline을 지키지 못 한 예다. 윈도우즈나 리눅스가 여러 프로그램을 사용하면서 동영상을 보면 끊길 수도 있다. 일반적으로 여러분이 사용하는 OS는 time sharing system인데 그 내부에서 real-time 동작을 수행하는 것이라, real-time computing이 키워드로 맞다. 동영상 플레이어 프로세스의 priority를 높여 deadline을 지키도록 유도할 수 있다. 

- Thread Scheduling : User level thread 이냐, kernel level thread이냐에 따라 scheduling의 주체가 결정된다. 만약 kernel 단에서 thread의 존재를 아는 경우, kernel이 단기 스케쥴러를 통해 특정 thread에 CPU 제어권을 줄 수 있다. 그게 아니라면 kernel은 겉 process(해당 thread를 포함하는 process)에 CPU 제어권을 주고, 해당 process는 User level 수준에서 thread library를 활용하여 특정 thread에 CPU 제어권을 줄 수 있다.

Algorithm Evaluation

- 위 알고리즘들의 성능을 평가하는데에 대기 행렬 모델Queueing models(OR 외의 과목에서는 오랜만이다. lambda, arrival rate, service rate...) 또는 Implementation & measurement (실제 구현 및 측정), Simulation 등을 사용할 수 있다.