Scheduling: Scheduling Processes

Think about scheduling.

CPU scheduling은 시스템의 CPU core에서 어떤 프로세스를 실행할 지 선택하는 효율성의 문제입니다. Busy system에서는 실행할 준비가 된 프로세스들이 CPU core보다 더 많이 존재할 수 있으므로, 시스템 커널은 어떤 프로세스들이 CPU에서 동작하기로 예정되어 있는지, 어떤 프로세스들이 ready queue로 들어가 나중에 실행될지 평가해야합니다.

멀티스레드와 여러개의 코어가 있는 CPU에서는 문제가 더 복잡해지므로 설명을 위해 여기서는 무시하도록 하겠습니다.

원어민이 아닌 사람들이 일반적으로 헷갈리는 것은 Time이 두 가지 뜻을 가지고 있다는 것입니다. Time은 clock과 context의 경과에 모두 사용될 수 있습니다. 예를 들어, "The arrival time of the first process was 9:00am" 처럼 시간으로 사용될 수도 있고 "The running time of the algorithm is 3 seconds." 처럼 경과 시간에 사용될 수도 있습니다.

How is scheduling measured and which scheduler is best?

스케쥴링은 시스템의 성능, 그중 특히 대기 시간과 처리량에 큰 영향을 영향을 미칩니다. 처리량(throughput)은 시스템값에 의해서 측정될 수 있습니다. 예를 들어 I/O throughput의 경우 1초에 몇 바이트가 쓰여졌는지, 또는 unit time에 몇개의 작은 프로세스들이 실행될 수 있는지, 또는 높은 레벨의 추상화를 사용해(고객의 수를 기록하는 등의) 분당 얼마나 동작하는지와 같이 측정합니다. 대기 시간(latency)은 반응 시간(프로세스가 response를 보내기 전까지 걸린 시간) 또는 대기 시간, turnaround time(task가 종료될 때 까지 걸린 시간)등을 통해 측정됩니다. 다른 스케쥴러는 다른 최적화를 제공해 사용 목적에 맞을 수도, 맞지 않을 수도 있습니다. 죽, 모든 환경과 목표에 최적화된 스케쥴러는 존재하지 않습니다. 예를 들면 가장 금방 끝나는 일을 먼저 하도록 스케쥴링 된 경우에는 대기 시간을 줄일 수 있겠지만 UI와 같은 interactive environment(대화형 환경)에서는 처리량을 좀 희생하더라도 response time을 줄이는 것이 더 적합합니다. FCFS(First come, First served)는 공정해 보이고 구현이 쉽지만, convoy effect가 발생해 오랜 시간이 걸리는 프로세스가 왔을 경우 그 프로세스가 CPU를 돌려줄 때까지 계속 기다려야 합니다.

What is arrival time?

arrival time은 프로세스가 Ready queue에 처음 도착해 실행 준비가 되었을 때 까지의 시간입니다. 만약 CPU가 idle이라면, arrival time은 실행의 start time과 같을 것입니다.

What is preemption?

비선점 프로세스는 CPU를 더 이상 사용할 수 없을 때까지 동작합니다. 예를 들어 다음과 같은 상황에서 CPU로부터 프로세스를 제거해 CPU가 예정된 다른 프로세스의 동작을 할 수 있게 합니다: 프로세스가 signal에 의해 종료되었을 때, 동기화 인자를 기다리는 동작으로 blocking되었을 때, 정상적으로 종료되었을 때. 그러므로 일단 프로세스가 schedule되었다면 더 높은 우선순위의 프로세스가 ready queue에 들어와도 하던 일을 계속 진행합니다.

선점 프로세스는 ready queue에 더 적합한(우선순위가 높은) 프로세스가 들어온다면 그 즉시 기존 프로세스를 제거합니다. 예를 들면 가장 짧은 일을 먼저 하는 스케쥴러가 t=0에서 P1과 P2 2개의 프로세스가 들어왔다고 생각해봅시다. P1은 10ms, P2는 20ms의 execution time을 가지고 있습니다. 이 경우 P1이 수행됩니다. P1이 즉시 5ms가 걸리는 새로운 프로세스 P3를 만들어 ready queue에 들어갑니다. 비선점이라면 P3는 10ms 이후에(P1이 종료된 후에) 실행되겠지만, 선점에서는 P1이 즉시 CPU로부터 떨어져 ready queue에 돌아가고, P3가 대신 실행될 것입니다.

Which scheduler suffer from starvation?

우선 순위 형식을 사용하는 모든 스케쥴러는 starvation을 겪을 수 있습니다. 미리 도착한 프로세스들이 CPU에 할당되지 못하는 경우가 발생할 수 있기 때문입니다. 예를 들면 SJF(Shortest Job First)에서 수행시간이 긴 작업은 시스템이 계속해서 짧은 일을 보내오면 영원히 수행될 수 없습니다.

Why might a process (or thread) be placed on the ready queue?

프로세스는 CPU가 사용할 수 있을 때 ready queue에 들어갑니다. 아래와 같은 경우입니다.

• read로 block되어 있던 프로세스가 저장소나 소켓에서 읽어오는 것이 끝나 데이터가 사용 가능해진 경우
• 새로운 프로세스가 생성되어 시작할 준비가 되었을 때
• synchronization primitive(condition variable, semaphore, mutex lock)에 의해 block되어 있던 프로세스가 사용 가능한 상태가 되었을 때
• 프로세스가 system call을 기다리며 block되고 있지만 signal이 전달되어 signal handler가 동작할 필요가 있을 때

스레드를 고려하면 비슷한 예가 더 생길 것입니다.

Measures of Efficiency

start_time 은 프로세스의 시작 시간(CPU가 작업을 시작한 시간)이고, end_time은 프로세스가 끝나는 시간(CPU가 프로세스를 끝낸 시간)입니다. run_time은 CPU time이 얼마나 필요한지에 대한 총 합계이고, arrival_time은 프로세스가 scheduler에 들어온 시간입니다.(CPU가 아직 작업을 시작하지 않음)

What is 'turnaround time'?

프로세스가 도착해서 끝날 때까지의 총 시간입니다.

turnaround_time = end_time - arrival_time

What is 'response time'?

프로세스가 도착하고 CPU가 실제로 작업을 시작하기까기 걸린 총 지연 시간을 의미합니다.

response_time = start_time - arrival_time

What is 'wait time'?

Wait time은 프로세스가 ready queue에 있는 총 시간입니다. Ready queue에 있는 초기 대기 시간만이 wait time이라고 생각하는 실수를 저지르기 쉽지만, 그것은 wait time의 일부입니다.

만약 I/O가 없이 CPU를 많이 사용하는 프로세스가 7분의 CPU time을 필요로 하지만 작업을 완료하는데 9분의 시간이 걸렸다면 이 프로세스가 ready queue에 2분의 시간을 보냈다고 생각할 수 있습니다. 이 2분은 프로그램이 동작할 준비가 되었지만 CPU가 할당되지 않은 경우입니다. 언제 이 일이 waiting한 건지는 상관 없지, wait time은 2분입니다.

wait_time = (end_time - arrival_time) - run_time

What is the Convoy Effect?

Convoy Effect는 I/O 집약적인 프로세스가 계속적으로 쌓여 CPU 집약적인 프로그램이 끝나기를 기다리고 있는 상태를 의미합니다. 이것은 매우 적은 CPU 사용량이 필요한 프로세스조차 I/O 퍼포먼스가 나쁘게 만듭니다.

CPU가 현재 CPU 집약적인 일을 분배받았다고 생각해봅시다. 이 때 I/O 집약적인 프로세스들이 ready queue에 존재합니다. ready queue에 있는 이러한 프로세스들은 약간의 CPU time만이 필요하지만 CPU 집약적인 프로세스가 CPU로부터 떨어지기를 기다려야 하므로 더 이상 진행되지 못합니다. 하지만 아주 가끔 CPU가 사용 가능한 상태가 되면(FCFS 스케쥴러의 경우를 예로 들면 프로세스가 I/O request로 인해 block되는 경우) I/O intensive 프로세스들이 CPU need를 채워 빠르게 처리할 수 있습니다. 그리고 나서 다시 CPU 집약적인 프로세스가 CPU에 할당됩니다. 그러므로 전체 시스템의 전체적인 I/O 효율이 나빠지게 합니다.

이러한 현상은 주로 FCFS(First Come Fisrt Served) 스케쥴러에서 이야기되지만, 긴 time quantum인 경우 round robin 스케쥴러에서도 나타날 수 있습니다.