CPU Scheduling

CPU & I/O Burst

프로그램 실행은 결국 CPU로 작업하는 단계와 I/O 작업을 하는 단계를 연속해서 지나가는 과정이다. 여기서 CPU burst는 CPU가 기계어를 해석하고 있는 단계, I/O하는 단계를 I/O burst라고 부른다. 프로그램별로 burst의 간격은 다르다. 주로 사람과 ineract하는 프로그램이 위처럼 버스트가 번갈아 등장한다. 연산량을 많이 필요로하는 작업은 CPU Burst의 간격이 넓어지게된다. 만약 I/O를 길게 쓰는 프로그램이 있다면 I/O bound job(process) 라 부르고 , CPU를 길게 쓰는 프로그램을 CPU bound job(process)이라고 부른다.

 

이 때 Burst Time 종류에 따라 CPU 우선권이 다르게 주어진다. I/O bound job 과 CPU bound job 중 운영체제는 I/O bound job에게 먼저 CPU 사용 우선권을 주게된다. I/O bound job 에게 CPU를 먼저 할당해야 오래걸리는 I/O 작업을 하러 떠남으로서 더 효율적으로 프로세스 관리가 이루어지게 되기 때문이다. 또한 I/O bound job은 사람과 interaction 하는 작업이기 때문에 최대한 먼저 결과물을 전달해주어야한다. 하지만 현실에서는 I/O bound, CPU bound가 무작위로 들어오기 때문에 I/O buond 작업을 먼더 처리함을 원칙으로 하되 효율적인 처리를 위해서 스케쥴링이 필요해진다.

 

---

 CPU scheduler

CPU스케쥴러는 레디 상태 프로세스중 어떤 녀석에세 CPU를 효율적으로 내줄지 결정하는 코드로 운영체제의 코드중 일부코드이다. 이렇게 스케줄러가 어떤 프로세스가 CPU를 사용할지 결정하면, Dispatcher는 실제로 그 프로세스를 CPU에 할당하는 역할을 수행한다. 즉 디스패처의 주요 기능은 문맥교환이라고 볼 수 있다.

 

CPU스케쥴러와 디스패쳐에 의한 프로세스 상태변화는 아래 4가지 경우와 그 이외의 경우로 분류할 수 있다.

1. Running -> Blocked (예: I/O 요청하는 시스템 콜)
2. Running -> Ready (예: 할당시간 만료로 timer inerrupt)
3. Blocked -> Ready (예: I/O 완료후 인터럽트)
4. Terminated

• 1~4 스케쥴링은 강제로 빼앗지 않고 자진 CPU 제어권을 반납하는 nonpreemptive scheduling (비선점형)
• 1~4 에 해당하지 않는 모든 스케쥴링은 강제로 빼았는 preemptive scheduling (선점형)

---

스케쥴링 알고리즘

CPU 스케쥴링 알고리즘을 고려할 때  성능 척도의 기준은 5가지이다. (1,2은 시스템의 입장, 3,4,5는 클라이언트 입장) 

1. CPU 이용률 (CPU utilization) - CPU 가 일한 시간/전체시간 비율
2. 처리량 (Throughput) - 주어진 시간동안 작업 처리량
3. 소요시간, 반환시간 (Turnaround time) - CPU를 점유하기 시작해서 다쓰고 나간시간
4. 대기시간 (Waiting time) - ready상태에서 기다리는 시간(인터럽트 걸려서 다시 줄서는 시간이 있어 여러차례 발생)
5. 응답시간 (Repsonse time) - ready큐에 들어와서 처음으로 CPU를 얻은 시간 (찐으로 처음 CPU얻기까지 단 한번 발생)

FCFS(First-Come-First-Served)는 먼저 도착한 프로세스에게 가장 먼저 CPU 제어권을 준다. 이러한 선착순대로 처리하는 방법(FCFS)는 non-preemptive(비선점형)한 스케쥴링이다. 하지만 만약 앞선 프로세스의 작업량이 많고 뒤이은 프로세스의 작업량이 적은 경우 매우 비효율적인 스케쥴링이 될 수 있다. 이러한 FCFS처럼 순서에 따라 성능차이가 나는 것을 Convoy effect라고 부른다.  (Convoy effect: 긴 프로세스가 앞에 도착하는 바람에 뒤에 짧은 프로세스가 오래기다리는 현상)

 

SJF(Shortest Job First)는 짧은 작업량을 먼저 처리할 수 있도록 CPU 제어권을 넘기는 알고리즘으로 Convoy effect를 고려한 방법이라고 할 수 있다. SJG는 대기시간의 관점에서 보았을 때 가장 최적화된 방법이라고 볼 수 있다. 만약 한 프로세스에게 CPU 제어권을 넘겼는데 더 짧은 작업량의 프로세스가 온다면 일단 제어권을  가지고 있는 프로세스의 작업 마무리는 기다려 준다 -> non-preemptive 만약 대기큐에서 더 짧은 프로세스가 온다면 이 프로세스를 우선순위를 앞에다 둔다 -> preemptive.

 

하지만 SJF는 사실상 최적화된 방법임에도 치명적인 두 가지 약점이 있다. 가장 먼저 Starvation 문제가 있다. 계속해서 작업량이 적은 프로세스가 새치기를 할경우 뒤에있던 프로세스가 영원히 처리되지 않을 수도 있다. 두번째는 CPU burst time에 대한 파악이 정확하지 않다는 문제이다. 운영체제는 각 프로세스의 CPU 작업량을 인풋 데이터나 브런치, 과거의 CPU burst(exponential reveraging)등을 종합하여 추정할 뿐이다. 따라서 만약 짧다고 생각해서 CPU 제어권을 넘겼는데 알고보니 CPU작업량을 많이 차지하는 녀석이라면 문제가 될 수 있다.

 

Priority Scheduling 은 우선순위가 높은 프로세스에게 CPU 제어권을 넘긴다. SJF도 일종의 Priority Scheduling이라고 볼 수 있다. 이때 SJF는 Priority를 CPU burst time 예측으로 매긴다. 따라서 Priority Scheduling 도 Starvation 이라는 문제점을 가지고 있다. Priority Scheduling에서는 Starvation의 문제 해결방안으로 Aging을 사용하고 있다. Aging이란 큐에 머물러있는 시간에 따라 프로세스의 우선순위를 높여주는 방법이다.

 

Round Robin 스케쥴링은 프로세스에게 CPU를 넘길 때 timer을 사용해서 점유시간을 미리 설정해놓는 방식이다. 일정시간이 지나면 인터럽트가 걸려 운영체제에게 다시 CPU가 넘어간다. 이때 할당시간을 time quantum 이라 부른다. 현대 운영체제 프로그램에서 가장 많이 쓰이는 알고리즘이다. 한 가지 단점은 일반적으로 SJF보다 프로세스당 평균적으로 작업 끝내는 시간이 길어진다는 것이다. 따라서 RR은 비슷한 동일한 작업들이 있을 때보다 짧은 작업, 긴 작업 섞여있있을 때 써야 효율적이다.

---

https://core.ewha.ac.kr/publicview/C0101020140325134428879622?vmode=f

반효경 [운영체제] 9. Process Management 2