<Process scheduling>
다음에 실행할 프로세스는 어떤 것인지를 결정하는 과정이다. 다수의 프로세스가 존재하는 경우, OS의 프로세스 관리 목표를 극대화하기 위해서 프로세스를 스케줄링을 한다.
Fairness(공정성) : 모든 프로세스가 CPU 시간을 공평하게 받을 수 있도록 스케줄링한다.
Maximum Waiting Time(처리량) : 시스템이 단위 시간당 최대 프로세스를 처리할 수 있도록 한다.
Minimum Waiting Time(대기 시간 최소화) : 프로세스가 CPU를 기다리는 시간을 최소화하여 응답 시간을 향상시킨다.
Minimum Response Time(응답 시간 최소화) : 사용자가 프로그램을 실행할 때 시스템이 즉각적으로 응답하도록 한다.
Optimal Resource Utilization(자원 활용 최적화) : CPU, 메모리 등의 시스템 자원을 효율적으로 활용하여 시스템 성능을 극대화한다.
<Scheduling Queue>
프로세스들을 관리하기 위해선 줄을 세울 수 있는 공간이 필요하다. 아래의 큐잉 다이어그램을 보면서 살펴 보자.
Job Queue : OS가 관리하는 모든 프로세스를 포함한다.
Ready Queue : 일단 프로세스가 시스템에 들어가면 Ready Queue에 들어가 준비 상태가 되어 CPU 코어에서 실행되기를 기다린다. 이 큐는 일반적으로 연결 리스트로 저장되며 Ready Queue 헤더에는 리스트의 첫 번째 PCB에 대한 포인터가 저장되고 각 PCB에는 Ready Queue의 다음 PCB를 가리키는 포인터 필드가 포함된다.
Wait Queue : 프로세스에 CPU 코어가 할당되면 프로세스는 잠시 동안 실행되어 결국 종료되거나 인터럽트 혹은 I/O 요청의 완료와 같은 특정 Event가 발생할 때까지 기다린다. 프로세스가 디스크와 같은 장치에 I/O 요청을 한다고 가정한다면, 장치는 프로세서보다 상당히 느리게 실행되므로 프로세스는 I/O가 사용 가능할 때까지 기다려야 한다. 이처럼 I/O 완료와 같은 특정 Event가 발생하기를 기다리는 프로세스는 Wait Queue에 삽입된다.
<Scheduling Algorithm>
Turnaround Time(TAT) : 프로세스가 생성된 후, 실행을 끝마치기까지 걸린 시간. 다시 말하자면, 프로세스가 Ready Queue에 들어간 순간부터 Workload가 완료될 때까지의 시간을 말한다.
그렇다면 TAT를 최소화하기 위해서는 어떠한 스케줄링이 필요할까? 다소 비현실적이지만 다음 5가지 가정을 상정하고 각각의 가정들을 소거해가면서 알아보자.
가정 1 : 각 작업들은 동일한 양의 시간 동안 실행된다.
가정 2 : 모든 작업들은 동시에 생성된다.
가정 3 : 일단 작업이 시작하면, 각 작업들은 완료할 때까지 실행한다.
가정 4 : 모든 작업들은 CPU만 사용한다. (I/O는 X)
가정 5 : 각 작업들의 실행 시간은 이미 알고 있다.
이제 각 스케줄링 알고리즘의 TAT를 계산해보고 프로세스들을 처리하는 데 적합한지 판단해보자.
1. First Come, First Served (FCFS) 방식
먼저 온 녀석부터 처리하는 매우 간단한 방식이다. 시스템에 총 세 프로세스가 존재하고 모두 10초의 실행 시간을 가진다고 해보자. 그리고 세 프로세스는 동시에 생성되었고 큐에는 A, B, C 순으로 적재되었다고 해보자.
평균 TAT를 계산해보면, (10 + 20 + 30) / 3 = 20초가 나온다. 과연 최선의 방식일까? 현실에서는 모든 프로세스들이 같은 실행 시간을 가지기는 어렵다. 가정 1을 제거하고 조금 다른 예시를 들어보자. 만약 시스템에 A는 100초, B와 C는 10초의 실행 시간을 가졌다고 하면?
평균 TAT는 (100 + 110 + 120) / 3 = 110초로 굉장히 길어지는 것을 확인할 수 있다. 이렇게 A처럼 시간이 오래 걸리는 프로세스가 CPU를 일단 차지해버리면 다른 모든 프로세스들은 그 프로세스가 CPU를 내놓을 때까지 기다려야 하는데, 이것을 Convoy Effect(호위 상태)라고 한다. 그럼 어떻게 해야 개선할 수 있을까?
2. Shortest Job First (SJF) 방식
실행 시간이 짧은 녀석부터 처리하는 방식이다. Convoy Effect를 해결할 수 있는 가장 간단한 방법이다.
평균 TAT를 계산해보면, (10 + 20 + 120) / 3 = 50초로 굉장히 짧아진 것을 확인할 수 있다. 나쁘지 않다. 하지만 알다시피 모든 프로세스들이 동시에 생성되지는 않는다. 이제 가정 2가 제거되고 시스템에 A는 100초, B와 C는 10초의 실행 시간을 가지고 A가 먼저 생성되고 10초 후에 B와 C가 생성되었다고 한다면 어떻게 될까?
평균 TAT = {100 + (100 - 10) + (120 - 10)} / 3 = 103.333초가 나온다. 이론적으로는 최적이나 실제 문제에서는 그렇지 않다. 더 실제적인 방식은 없을까?
3. Shortest Time-to-Completion First (STCF) 방식
STCF는 새로운 작업이 들어올 때마다 남은 실행 시간이 가장 짧은 작업을 우선하는 선점형(Preemptive) 스케줄링 방식이다.
※선점형 스케줄링 : 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식
※비선점형 스케줄링 : 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식
가정 3을 제거하고 다시 예시를 들어보자. A는 100초, B와 C는 10초의 실행 시간을 가지며, A가 먼저 생성되었고 10초 후에 B, C가 생성되었으나 STCF에 따라, A의 실행은 B와 C가 생성된 시점에 선점된다.
평균 TAT의 계산은 {(120 - 0) + (20 - 10) + (30 - 10)} / 3 = 50초이다. 보다시피 훨씬 줄어든 것을 확인할 수 있다. 하지만, 모든 시스템에서 총 처리 시간(TAT)만이 최선의 기준이 아닐 수 있다. 예를 들어 Interactive System에서 필요한 것은 시스템의 빠른 반응이며 Timesharing을 실현하기 위해서는 여러 프로세스들이 동시에 실행되는 듯한 착각이 필요하다. 따라서 다음은 Response Time도 고려해서 스케줄링 알고리즘에 적용해보자.
Response Time : 프로세스가 생성된 후 처음 실행되기까지 걸린 시간
Response Time을 극대화하기 위해서는 어떠한 스케줄링이 적합할까? STCF 방식으로도 충분할까?
아까 STCF 방식으로 TAT를 알아봤던 조건 그대로 이번엔 Response Time 관점으로 살펴보자.
평균 Response Time = {0 + 0 + (20 - 10)} / 3 = 3.333초이다. STCF에서는 동시에 작업이 생성되어도, 밀려난 경우에 실행 중인 전체 작업 실행을 기다려야 한다. 위의 경우에 평균 응답 시간은 낮아 보일지 모르지만, C의 입장에서는 10초를 기다려야 하므로 C의 기분은 썩 좋아 보이진 않는다. 만약 키보드를 타이핑하는데 글자가 나오기까지 10초가 걸린다면 답답하지 않을까? 아래의 스케줄링 방식과 비교해보자.
4. Round-Robin (RR) 방식
실행 중인 작업을 다 마치지 않았어도, 주어진 기회 시간(Time Slice)이 만료되면 다른 작업으로 전환(switching)하는 스케줄링 방식
시스템에 실행 시간이 5초인 A, B, C 프로세스가 존재한다고 가정해보자. 이 프로세스들은 동시에 생성되었다. 각각 SJF와 RR 방식으로 평균 Response Time을 계산해보자.
SJF의 경우 (0 + 5 + 10) / 3 = 5초이고, 1초의 Time Slice 조건을 갖는 RR 방식에서는 (0 + 1 + 2) / 3 = 1초이다. 보다시피 RR 방식의 성능에 영향을 끼치는 것은 Time Slice의 길이인 것을 알 수 있다. 그러면 길이가 짧으면 짧을수록 무조건 좋은 걸까? Time Slice의 길이가 짧으면 시스템을 바쁘게 만든다. 위의 RR 방식에서의 평균 TAT를 계산해보면 (13 + 14 + 15) / 3 = 14초인데, TAT만을 본다면 RR 방식은 그리 좋지 않은 선택일 수 있다. 그러나 Time Slice를 잘 정한다면, 일반적인 경우에 빠른 응답시간과 공평성(fairness)을 제공할 수 있다. 반면, SJF와 STCF는 좋은 TAT를 제공하지만 응답시간 측면에서는 불리하다. 이제 마지막으로 가정 4와 가정 5를 완화해보자.
5. Incorporating I/O 방식
CPU가 I/O 작업을 기다리는 동안 다른 프로세스를 실행하여 CPU와 다른 장치(주로 I/O 장치)간의 효율적인 활용을 촉진하는 방식
가정 4를 제거한다면, 실제 시스템의 프로세스는 I/O 처리를 요구할 수 있다. I/O 처리 요구 시 프로세스는 Block되어 Waiting 상태가 된다. 만약 시스템에 50ms의 CPU 시간을 요구하는 프로세스 A와 B가 존재한다고 해보자. A는 10ms마다 I/O를 요청(I/O 처리 시간은 10ms으로 가정)하고, B는 I/O 요청없이 CPU만을 50ms만큼 사용한다. 스케줄러는 A, B순으로 실행한다.
보다시피 프로세스 A가 I/O 완료를 기다리는 동안 CPU를 활용하지 못하는 문제가 발생한다. 이 문제를 해소하기 위해 Incorporating I/O 방식으로 I/O 시간을 Overlap하면 된다. 아래 그림을 확인하자.
