CPU 스케줄링 알고리즘

CPU가 하나의 프로세스 작업이 끝나면 그 다음 프로세스 작업을 수행해야 한다. 이때 작업을 선택하는 알고리즘을 CPU 스케줄링 알고리즘이라 한다.

 

1. Preemptive VS Non-preemptive (선점 vs 비선점)

 

• Preemptive의 경우 프로세스가 CPU를 점유하고 있는 동안 I/O 요청이나 인터럽트가 발생한 것도 아니고 모든 작업을 끝내지도 않았는데, 다른 프로세스가 해당 CPU를 강제로 점유할 수 있는 경우를 말한다. 즉 프로세스가 정상적으로 수행중인데 다른 프로세스가 CPU를 강제로 점유해서 실행할 수 있는 것을 말한다.
• Non-Preemptive의 경우 한 프로세스가 CPU를 점유 했다면, I/O요청이나 인터럽트가 발생 또는 프로세스가 종료 될 때 까지 다른 프로세스가 CPU를 점유하지 못하는 것을 말한다.

 

2. 스케줄링 기준 척도

1. CPU 이용률 : CPU가 수행되는 비율을 말한다.
2. Throughput (처리율) : 단위 시간당 처리하는 작업의 수를 말한다.
3. Turnaround Time (반환시간) : 프로세스의 처음 시작 시간 부터 모든 작업을 끝내고 종료하는데 걸린 시간. CPU, waiting, I/O등 모든 시간이 포함. 반환시간은 빠를 수록 좋다.
4. Waiting Time (대기시간) : CPU를 점유하기 위해 Ready Queue에서 기다린 시간을 말한다.
5. Response Time (응답시간) : 일반적으로 대화형 시스템에서 입력에 대한 반응 시간을 말한다.

 

3. CPU  스케줄링 알고리즘

알고리즘에 대해 공부하기 전에 CPU를 사용한 시간은 burst time이라 한다.. 알아두자.

 

3-1 Non-Preemptive 스케줄링

• 한 프로세스가 CPU를 할당 받으면 다른 프로세스는 CPU를 점유하지 못한다.
• 짧은 작업을 수행하는 프로세스가 긴 작업이 종료될 때 까지 기다려야 하는 경우 발생.
• 모든 프로세스들에게 공정하고 응답시간이 예측 가능하다.

FCFS

• 먼저온 프로세스가 CPU를 점유하는 방식 즉 큐에 먼저 도착하는 순서대로 CPU 할당.
• 단순하고 많이 사용하지만 모든 부분에서 효율적이진 않는다. 실행 시간이 짧은게 뒤로 갈 경우 평균 대기시간이 길어지게 된다.

SJF

• 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행하는 알고리즘
• FCFS 보다 평균 대기 시간 감소, 짧은 작업을 처리할 때 유리하다.

 

process	burst time
p1	6
p2	10
p3	8
p4	4

위의 경우 일때 FCFS 알고리즘을 사용한다면 AverageWaitingTime (AWT) = (0+6+16+24) / 4 의 값을 가진다.

그러나 burst time이 작은 순서대로 SJF 알고리즘을 사용 한다면 0+4+10+20/4 의 값을 가지는 것을 볼 수 있다.

 

SJF 알고리즘을 사용하는것이 이상적인 것 처럼 보이나 현실적으로 실제 환경에선 프로세스의 burst time을 알 수 없다. 측정한 시간을 예측해서 사용하는 것은 오히려 오버헤드가 늘어나는 모습을 보임으로 잘 사용되지 않는다.

 

3-2 Preemtive 스케줄링

Priority

우선순위가 높은 프로세스가 먼저 선택되는 스케줄링 알고리즘이다. 운영체제에서 일반적으로 우선순위는 정수값으로 나타낸다.

작은 값이 우선순위가 높다.

 

우선 순위를 정하는 방법

 

• 내부적 방식 : time limit, I/O to CPU burst(I/O작업은 긴, CPU작업은 짧은 프로세스 우선), Memory Requirement 등
• 외부적 방식 : amount of funds being paid, political factors 등.

 

Priority 방식도 SJF와 마찬가지로 비선점, 선점 방식 모두 사용이 가능하지만 Starvation (기아) 문제가 발생한다.

CPU의 점유를 오랜시간 동안 하지 못하는 현상으로, 우선순위가 매우 낮은 프로세스가 아주 오랜시간 동안 Ready Queue에서 대기하고 있어 CPU를 점유하지 못하게 된다.

실제 컴퓨터 환경에서는 새로운 프로세스가 자주 Ready Queue에 들어오기 때문에 위의 문제가 발생할 수 있다.

 

기아현상을 해결하기 위한 방법으로 Aging이 존재한다. 이 방식의 경우 Ready Queue에서 기다리는 동안 일정 시간이 지나면 우선순위를 일정량 높여주는 방법이다. 이 방식을 사용한다면 우선순위가 매우 낮은 프로세스라 하더라도, 기다리는 시간이 길어질 수록 우선순위도 계속 높아지므로 수행될 가능성이 커진다.

 

Round-Robin

원 모양으로 모든 프로세스가 돌아가며 스케줄링 하는 방법. 시분할 시스템에서 주로 사용하는 방식이다. 일정 시간을 정하여 하나의 프로세스가 이 시간동안 수행하고 다시 대기 상태로 돌아간다. 그리고 다음 프로세스 역시 같은 시간동안 수행한 후 대기한다. 이러한 작업을 모든 프로세스가 돌아가며 하며, 마지막 프로세스가 끝나면 다시 처음으로 돌아와 반복한다. 일정시간을 Time Quantum(Time Slice)라 부른다. 기본적으로 Preemtive 방식이다. 한 프로세스가 종료되기 전에 Time Quantum이 끝나면 다른 프로세스로 CPU가 넘어가기 때문이다.

위 예시에서 RoundRobin의 AWT를 구하는 공식은 6+4+7/3 이다.

위의 예시를 통해 보더라도 RR 방식은 Time Quantum 크기에 따라 AWT와 같은 스케줄링 척도가 바뀌는 걸 볼 수 있다.

Round Robin 방식은 Time Quantum에 매우 의존적인 방식이다. 그러다 Time Quantum이 무한에 가깝게 설정한다면 FCFS와 동일하게 동작한다. 반대로 0에 가깝게 설정한다면 Switch Overhead가 급증하여 비효율 적이다. 일반적으로 10 ~ 100 msec으로 정한다.

 

Process Group

프로세스는 기준에 따라 여러 그룹으로 나눌 수 있다.

• System Processes : 운영체제 커널 수준의 프로세스
• Interactive Processes : 유저 수준의 대화형 프로세스
• Interactive editing Processes
• Batch Processes :  대화형 프로세스의 반대로 일정량을 한 번에 처리하는 프로세스 ex) Compiler
• Student Processes

 

Multi Level Queue

위와 같이 여러 성격에 따라 프로세스 그룹을 나눌 수 있다. 이를 하나의 큐를 사용하는 것은 비효율적이라 판단하여 각 그룹에 따라 여러개의 큐를 두어 사용하는 방법을 Multi Level Queue 방식이다.

먼저 큐마다 우선순위를 지정하여 사용하거나 큐마다 CPU할당 시간을 다르게 주는 등 큐마다 다른 스케줄링 방식을 사용할 수도 있다.

 

Multi Level Feedback Queue

Multi Level Queue와 비슷한 방식이지만 모든 프로세스는 가장 위의 큐에서 CPU 점유를 대기하고 이상태로 진행하다가 시간이 너무 오래 걸린다면 아래의 큐로 프로세스를 옮겨 대기시간을 조정하는 방식이다. 

우선 순위 큐를 사용하는 상황에서 우선 순위가 낮은 아래 큐에 있는 프로세스에서 기아 현상이 발생하면 우선순위가 높은 위의 큐로 옮길 수도 있다.