Operating System 5 - CPU Scheduling

 Multiprogramming : 단일 프로세서 시스템에서 여러 개의 프로세스를 매니징 = interleaving으로 운영
multiprocessing : 멀티 프로세서 시스템에서 여러 개의 프로세스를 매니징 = overlapping으로 운영
distributed processing : 독립된 컴퓨터 노드 사이에서 통신하며 여러 개의 프로세스를 관리 = IPC 사용

Multi programing의 핵심은 scheduling. 언제라도 어떤 프로세스를 실행할 수 있게 하여 CPU 사용률을 최대화 하는 것.

CPU-I/O burst Cycle
일반적으로 프로세스는 CPU를 많이 사용하는 시간과 I/O를 많이 사용하는 시간으로 구성된다. 이들은 주로 번갈아가며 나타나며 각각을 CPU burst time, I/O burst time이라 한다. 단 프로세스의 시작과 끝은 반드시 CPU burst에 의해 점유된다.

일반적인 CPU사용에 있어서 길고 적은 수의 CPU burst 보다 짧고 여러 개로 구성된 CPU burst가 있는 경우가 훨씬 많다. 따라서 I/O burst를 가지는 것들을 적절히 섞어 주어야 최대의 퍼포먼스를 낼 수 있다.

Type of Processor scheduling
Queuing delay를 최소화하기 위해 큐를 매니징하는 것. 응답시간, 처리량, 프로세스의 효율성 등의 요소를 고려하여 적절한 프로세스를 할당하여 수행하게 하는 것.

- Long-term scheduling : 프로세스가 생성되어 메인 메모리로 들어갈 때 수행
- mid term scheduling : 프로세스가 suspend 되는 swap 타임에 수행 (secondary storage)
- short-term scheduling : 프로세스가 실제 dispatch 되어 돌아갈 때 수행 (main memory)
- I/O scheduling : CPU 기반 스케쥴링 방법이 아니라 I/O 관련한 스케쥴링

위의 두 종류는 multiprogramming의 정도와 관련이 있다. (프로세스의 수)
long term은 새로운 프로세스가 생겼을 때, batch que에 있는 해당 프로세스를 ready queue에 추가할 지 말지를 결정하게 된다. (New->ready/suspend) mid term은 swapping을 할 때, 메인 메모리에 프로세스를 더 추가할 지 말지 결정한다. (suspend -> ready/suspend)short term은 ready que에서 당장 다음 번에 실행될 프로세스가 무엇인지 결정한다. (ready -> running)

Long-Term Scheduler
이는 multiprogramming의 수를 관리하는 것이다. processor의 idle time이 threshold(degree)를 넘어가게 되면 새로운 프로세스를 ready queue에 추가하는 식으로 운영된다. 그리고 시스템의 쾌적한 작동을 위해 생성 가능한 프로세스의 수를 제한하는 역할도 한다.

새로운 프로세스를 추가할 때 어느 프로세스를 선택할 지 결정하는 알고리즘은 First come first served(FCFS), priority, 예상시간, I/O requirement 등 여러 가지가 있다.

Mid-Term Scheduling
이는 swapping function의 한 부분이다. 특정 시간 동안 활동하지 않은 것, 낮은 우선순위를 가지는 것, page fault가 자주 발생하는 것, 많은 메모리를 차지하는 것 등의 프로세스를 swap 하여 성능 개선을 꾀한다. 이는 multiprogramming의 degree를 줄이는 역할을 한다.

swap-in의 경우, 메모리에 빈공간이 있을 때, 혹은 unblock된 프로세스가 있을 때 이들을 다시 ready queue로 넣어주게 되며 이는 degree를 증가시키는 작업이 된다.

다만 이런 활동들은 근본적으로 degree를 조절하는 역할을 하지 어느 것이 수행될 지 직접적으로 선택하지는 않으므로 부가적인 활동이 된다.

Short-Term Scheduling (CPU scheduling)
상기 두 종류에 비해 훨씬 빈번히 사용되어 다음에 어떤 프로세스를 실행할 지 fine-grained decision(세부 조건에 따른 판단)을 내리는 역할을 한다.

- CPU scheduler : 다음에 실행될 프로세스를 선택하고 CPU의 core를 할당해주는 역할을 한다. FIFO que, priority que, tree, linked list 등 다양한 종류의 큐를 구성하고 사용할 수 있다.

Preemptive & Nonpreemptive(선점과 비선점)
scheduling 알고리즘이 언제 수행될 지 지정하는 두 가지 방법.

- 비선점 : 어떤 프로세스가 실행되고 있다면, 그것이 끝날 때 까지, 혹은 I/O 등의 self block이 걸릴 때 까지 수행한다.
- 선점 : 어떤 프로세스가 수행되고 있더라도 우선순위가 더 높은 새로운 것이 도달하면 인터럽트가 걸려 ready queue로 보내지게 된다. 또, CPU 내부 clock의 주기적인 interrupt에 의해서도 교체될 수 있다.

선점 방식은 비선점 방식에 비해 오버헤드가 크게 발생할 수 있지만 특정 프로세스가 프로세서를 오랫동안 독점하는 것을 막을 수 있다.

Dispatcher
하나의 프로세스에서 다른 프로세스로 전환시키는 동작을 수행하는 것. 이 dispatch가 실행될 때 dispatch latency가 발생하여 시스템 성능의 저하를 일으킬 수 있다.

스케쥴링 알고리즘의 평가 척도
CPU 활용도, Throughput(단위 시간 당 처리하는 프로세스 수), Turnaround time(처리시간 - 한 프로세스가 완료되는데 걸린 시간), waiting time(ready queue에서 순수하게 대기한 시간), response time(반응 시간 - 유저들에게 딜레이되지 않고 보여줄 수 있는 정도)

waiting time 이 줄어들면 turnaround time도 같이 줄어든다. (후자에 전자가 포함되므로) 그리고 단위시간당 처리하는 throughput도 올라간다.


따라서 Max cpu util, max throughput, min turnaround time, min waiting time, min response time이 되어야 최적화 된 알고리즘이다.

Scheduling algorithm

1. FCFS scheduling
가장 간단한 비선점 스케쥴링 방법. cpu를 가장 먼저 신청한 프로세스가 가장 먼저 코어를 할당 받아 실행되고 그 프로세스가 끝나면 FIFO que의 그 다음 프로세스가 실행되게 된다.

단, 이 방법은 CPU burst time이 긴 프로세스가 먼저 들어와 있을 경우 전체 waiting time이 길어진다는 단점이 있다. (하나의 CPU bound와 여러 개의 I/O bound 프로세스가 있을 경우) 이를 convoy effect라 한다.

위와 같은 이유로 FCFS는 CPU bound process가 많은 것을 더 선호한다. 그러나 앞서 살펴본 것 처럼 짧은 CPU burst와 긴 I/O를 가지는 I/O bound process가 일반적으로 더 많으므로 이는 별로 좋은 방법이 아니다.

2. SJF scheduling (Shortest-Job-First or Shortest Process Next)
다음 번에 CPU burst가 가장 짧은 것을 수행하는 비선점 방식. 따라서 convoy effect를 거의 없앨 수 있다. 만약 실행시간이 동일한 프로세스가 두 개 있다면, 먼저 들어온 것 부터 처리한다.

average waiting time을 최소화시켜주므로 일반적으로 optimal 하다고 할 수 있다. 짧은 것들은 긴 것보다 먼저 수행되므로 긴 대기 시간을 가질 필요가 없고, 긴 것들은 자신의 실행 시간에 비해 짧은 것들만 기다리면 되므로 전체 평균이 줄어든다. 이를 통해 response time을 개선할 수 있다.

단, ready queue에 대기 중인 프로세스들의 CPU burst를 정확하게 측정할 수 없다는 것이 이 방법의 가장 큰 단점이다. 따라서 각 프로세스가 얼마나 걸릴 지 예측하여 진행한다.
또한 Long CPU burst를 가지는 프로세스가 많을 경우, 각 프로세스는 기다리는 시간이 더 길어질 수도 있다. (starvation for longer processes)
그리고 비선점 방식이기 때문에 여전히 시분할 방식을 사용할 수 없다. (context switch 없음)

- Approximate SJF CPU burst
각 프로세스의 CPU burst는 이전과 비슷할 것이라고 예측하는 방식을 사용한다. 이를 계산하는 공식은 이전 CPU burst 들의 exponential average로 사용한다.

Tn+1 = a * tn + (1-a)Tn
(Tn+1 : 다음 CPU burst 예측값, tn : n번째의 실제 CPU burst 값, Tn : 이전 burst 예측값, 맨 처음에는 초기값으로 주어짐, 0<a<1 : 과거와 현재의 가중치 값)
만약 a=0이면 추측값이 모두 초기값과 같아지므로 FIFO와 동일하게 된다. a=1이라면 과거 값은 고려하지 않고 가장 최신 값만 고려하게 된다.
이를 확장하면 여러 개의 과거값을 모두 고려하는 대신, 그들의 계수는 지수승으로 늘어나 효과가 적어지는 방식을 고려할 수 있다.

이런 approximation을 사용하려면 과거의 실행 시간을 모두 기록해야 하므로 오버헤드가 발생한다.

3. SRTF scheduling (Shortest Remaining Time first)
위 방법의 선점 방식으로 작동한다. 나머지는 모두 동일하여 가장 짧은 것이 들어올 경우, 그것이 먼저 실행되고, 나머지 짧은 순으로 진행되는 방식이다. 따라서 항상 가장 짧은 수행시간을 가지는 프로세스를 먼저 실행할 수 있게 된다.

단점은 위와 동일하게 측정에 의한 오버헤드 발생과 긴 프로세스의 기아 문제이다.

4. RR(Round Robin) Scheduling
FCFS를 선점 방식으로 작동하는 방법. ready queue를 원형 큐로 구성하고, 각 프로세스를 약 10~100 밀리초의 time quantum, time slice로 분리하여 돌아가며 실행하는 방식이다.  

즉, ready 큐에 입력된 프로세스들을 매우 짧은 기간 동안 돌아가며 수행하게 된다. 이 때 만약 남은 프로세스가 1 time quantum 보다 작다면, 해당 프로세스가 완료되고 종료되며 cpu를 자동으로 반납하게 되고, 만약 1 time quantum 보다 크다면 내부 타이머에 의해 interrupt 되고 ready큐의 맨 뒤로 보내지며 CPU는 그 다음 프로세스를 실행하게 된다. (context switch occurs)

이 방법은 SJF 방법보다 긴 waiting time을 가지지만 response 측면에서는 훨씬 좋은 퍼포먼스를 보이게 된다. (시간을 쪼개어 실행하므로 응답 속도 향상)
또한 time quantum을 어떻게 쪼개느냐에 따라서도 성능이 크게 변한다. 만약 이 interval이 크다면 FCFS와 비슷해지고, 너무 작다면 context switch의 오버헤드가 커지게 된다. (context switch에 걸리는 시간보다는 반드시 커야 한다. 아니면 본말전도가 되므로) 따라서 10~100 밀리 세컨드의 fraction을 가지는 것이 (context switch가 보통 10 micro sec) 이상적이다.

경험적으로 전체 프로세스 중 80% 정도의 CPU burst가 time quantum 보다 작을 때 가장 최적(가장 짧은 waiting time)이라고 알려져 있다. (100%이면 FCFS)
5. Priority Scheduling
각 프로세스들이 우선순위에 따라 숫자를 부여받고, 해당 값이 작은 것 부터 먼저 수행되게 하는 방법. 동일한 우선순위를 가지는 프로세스들은 FCFS로 해소한다. SJF는 이 우선순위의 기준을 CPU burst가 낮은 것으로 잡은 우선순위 스케쥴링의 일종으로 볼 수 있다.

전체적인 속도는 SJF보다 느리다. 다만 이 방법은 빠른 속도로 처리하는 것보다 우선순위가 높은 것을 먼저 처리하여 안정성을 챙기고, 필요한 서비스를 제 때 제공하려는 목적을 우선하는 스케쥴링 방식이다.

이 방식은 선점/비선점 모두 가능하다. 그러나 이 방법 역시 낮은 우선순위를 가지는 프로세스의 경우 오랫동안 기다려야 하며, 만약 우선순위가 높은 것이 계속 들어올 경우 무한정 기다려야 할 수도 있다는 단점을 가지고 있다. (starvation problem을 여전히 가짐)

이를 해결하기 위해 Aging 기법을 사용할 수 있다. 이는 어떤 프로세스가 대기 중이라면 일정 시간이 지날 때마다 priority를 증가시키는 것으로 대기 시간이 지나치게 길어지는 경우를 방지할 수 있다.

6. Priority & Round Robin
이는 상기 두 방법을 합친 형태의 스케쥴링 방식으로 가장 높은 우선순위의 프로세스를 실행하되 같은 우선순위를 가지는 것들은 FCFS가 아니라 RR 방식을 이용해 결정하는 것이다.

7. Multi leveled queue
많은 프로세스를 관리할 경우 각 우선순위 마다 큐를 만들어 하나를 완료한 뒤에 전체 프로세스를 다시 서치할 필요 없이 높은 우선순위의 큐부터 차례로 확인하는 방식을 사용해 더 효율적인 스케쥴링을 할 수도 있다.
또한 각 큐마다 다른 스케쥴링 방식을 적용하여 더 다양하고 효율적인 스케쥴링을 할 수도 있다.

- Multi level Feedback Queue
그러나 이 방법 역시 여전히 starvation problem이 있으므로 앞서와 동일하게 aging 기법을 통해 해소할 수 있다. 이 경우에는 언제 다음 우선순위의 큐로 프로세스를 올릴 것인 지, 그 프로세스를 올리기 위해 위에서 내려야 할 큐가 있는지 등을 고려하여 실행된다. (Upgrade/ demote method for process)

일례로, 입력된 프로세스를 먼저 RR 방식으로 실행하고, 끝나지 않았다면 좀 더 긴 interval의 RR 방식의 큐로 내리고, 그래도 끝나지 않았다면 FCFS 방식의 큐로 하강할 수 있다. 반대로, FCFS에서 우선순위가 낮아 오랫동안 실행되지 않는다면 다시 윗 단계의 큐로 올릴 수도 있는 것이다.