[OS(운영체제)] CPU 스케줄링(CPU Scheduling)

1. CPU Scheduling

정의 : 어떤 프로세스를 다음으로 실행을 할 것인지에 대한 방식

 

다음에 어떤 프로세스를 실행을 해야하는지는 여러 가지 지표를 통해서 선택이 되어야 한다.

• Minimize trunaroung time : 작업 소요 시간
• Minimize response time : 최초 실행 시간 
• Minimize waiting time : process 대기하는 queue에서 많은 시간을 사용하지 않아야 한다.
• Maximize throughput : 처리율이 최대로 나와야 한다.
• Maximize resource utilization : 디바이스 활용을 최대화
• Minimize overhead : context switch를 최소화해야 한다.
• Maximize fairness : 같은 양의 CPU 리소스를 활용해야 한다.

2. Scheduling type

2.1 FIFO 

처음 들어온 프로세스가 제일 먼저 처리되는 가장 기본적인 방식이다.   Non-preemptive 방식으로 작동한다. (Non-preemptive: 비선점형은 위의 결정 시점 중 1번과 4번의 상황에서만 스케줄링이 발생한다. 어떤 프로세스가 CPU를 할당받으면 그 프로세스가 종료되거나 IO request가 발생하여 자발적으로 대기 상태로 들어갈 때까지 계속 실행된다)

 

그리고 모든 프로세스는 동등하게 작동하면 starvation이 필요하지 않다.

 

단점

Convoy effect : 평균적인 turnaround time이 커지는 문제가 발생한다. 그 이유는 처리 시간이 적게 걸리는 작업도 앞에 처리 시간이 오래 걸리는 작업 때문에 멈춰있는 시간이 많이 발생하기 때문이다.

 

2.2 SJF(Shortest Job First)

말 그대로 가장 처리 시간이 적게 걸리는 작업을 처리한다. 다른 방식보다 가장 최적의 turnaround time을 가지고 있고 Non-preemptive 방식이다.

 

단점

하지만 가장 적게 걸리는 작업을 처리를 하더라도 요청이 도착하는 시간이 다르기 때문에 결국에는 starve가 발생한다.

 

 

• FIFO vs SJF

아래의 그림처럼 SJF는 적게 걸리는 작업이 먼저 들어오는 게 아니라면 결국에는 starve 시간이 발생한다.

2.3 STCF(Shortest Time-to-Completion First)

작업은 동시에 수행되지 않는걸 기본으로 하고, 새로운 작업이 도착하면 실행 중인 작업보다 빨리 끝난다면 이전 수행 중인 작업을 멈추고 도착한 작업을 먼저 수행한다. 대표적인 Preempt 방식이다.

단점

하지만 이런 방식은 작업의 잦은 변화가 일어날 수 있음으로 overhead가 높아질 수 있다.

 

2.4 RR(Round Robin)

이 방식은 queue를 circular FIFO queue 방식으로 처리를 한다. 각각의 작업은 time slice가 존재해서 시간 단위로 작업을 처리한다. 하지만 이런 time slice는 크기에 민감하게 작동하며 너무 작으면 context switch가 자주 발생해서 overhead가 많아지고 너무 길게 하면 responsive가 적어진다. Preemptive방식이라 현재 진행 중인 프로세스를 interrupt가 가능하며 멈추는 시간이 존재하지 않는다.

• SJF vs RR

그림에서 보이듯인 turnaround 시간은 조금 더 걸리지 몰라도 response 시간이 줄어드는 걸 볼 수 있다.

 

3. Priority Scheduling

모든 작업에 대한 우선순위는 지정이 되어있다. 그래서 이제까지 설명했던 방식들이 작업의 우선순위에 따라서 작업을 처리한다. 그래서 가장 우선순위가 높게 설정된 작업을 하는 게 SJF를 예로 드는 게 가능하고 RR, FIFO는 모두 같은 우선순위를 가진다.

 

하지만 이런 방식에도 높은 우선순위의 작업만이 들어오면 계속 starvation이 발생하는 문제도 있다.

 

• Incorporating I/O

사진에서 처럼 I/O를 처리하는 동안 다른 작업을 처리하는 방식으로 CPU에서만 작업을 하는 것이 아닌 모습을 보인다.

3.1 MLFQ(MUlti-Level Feedback Queue

• priority 가 서로 다른 queue를 구성하는 특징을 가진다.

먼저 MLFQ를 적용하기 위해서는 몇 가지 규칙이 존재한다.

 

규칙 1 : Priority(A) > Priority(B), A runs 

규칙 2 : Priority(A) = Priority(B), A & B run in RR

 

규칙 1, 규칙 2를 사용한다면 먼저 각각의 queue는 priority가 다르기 때문에 우선순위가 높은 queue의 작업을 우선적으로 처리합니다. 그리고 2번째 규칙에 따라서 우선순위가 같다면 RR 방식으로 작업을 처리한다. 하지만 여기서의 문제는 Interactive 한 작업은 짧은 response 시간을 가지고 있어야 하고 CPU-intensive 한 작업은 CPU를 많이 사용을 해야 한다. 그런데 이런 상황에서 우선순위가 다르게 된다면 높은 우선순위의 작업만을 진행을 하기 때문에 상황에 따라 우선순위를 다르게 해주어야 한다.

 

규칙 3 : 일단 요청이 들어오면 가장 높은 priority에 넣는다.

규칙 4a : 작업이 실행될 때 time slice를 모두 사용하면 우선순위를 줄인다

규칙 4b :  작업이 time slice를 모두 사용하지 않고 CPU를 포기하면 우선순위는 그대로 둔다.

 

하지만 이런 방식에도 문제는 발생한다. 먼저 c의 작업처럼 interactive 한 작업이 많다면 많이 걸리는 A 작업 이 starve 하는 현상이 일어난다. 그리고 악의적 사용자가 스케줄러에 조작이 가능할 수 있으며 우선순위에 따라 다른 동작의 특성이 바뀔 위험이 있다.

 

그래서 규칙 5번이 등장하게 되었다.

 

규칙 5 : 일정 시간이 지나게 된다면 작업을 가장 높은 우선순위 queue로 옮긴다.

 

하지만 여기서 문제가 하나 발생하는데 better accounting으로 불리며 이는 일정 time slice보다 작은 작업이 들어와서 CPU처리를 포기하지 않는 것처럼 보이게 한다면 계속 같은 우선순위에 머무는 문제가 발생한다.

 

그래서 규칙 4a, 4b를 개정하여 통합된 규칙이 등장한다.

 

규칙 4: 우선순위에 상관없이 작업이 모든 우선순위에서 time slice를 다 사용하면 우선순위를 줄인다.

 

 

4. MLFQ: Summary

그럼 지금까지 규칙들을 마지막으로 정리해 보았다.

 

• 규칙 1 : 우선순위가 높은 프로세스들을 먼저 수행한다.
• 규칙 2 : 작업들이 같은 우선순위를 갖는다면 RR로 수행한다.
• 규칙 3 : 새로운 프로세스가 시스템에 들어가면 가장 높은 우선순위를 부여한다.
• 규칙 4 : 작업은 모든 우선순위에서 주어진 time slice를 모두 사용하면 우선순위가 감소한다.
• 규칙 5 : 일정 시간 후 시스템의 모든 작업을 우선순위가 가장 높은 큐로 이동한다.