운영체제: CPU 스케줄링

CPU라는 하드웨어 자원을 여러 프로세스들이 효율적으로 사용하기 위해, 스케줄링 과정이 필요하다. 다음에 실행할 프로세스를 선택하는 알고리즘을 통해 스케줄링을 하게 된다. 상황에 따라 효율적인 CPU 스케줄링이 오히려 성능 감소를 야기 할 수 도 있다.

 

Scheduling Critria

CPU 스케줄링의 효율성을 판단하는 기준은 다음과 같다.

• CPU Utilizaiton

• Throughput

• Turnarround Time

• Wating Time

• Response Time

 

Preemptive VS Non-Preemptive

다양한 CPU 스케줄링을 알기에 앞서 선점(Preemptive), 비선점(Non-Preemptive) 방식에 대한 이해가 필요하다.

 

Preemptive

선점은 말그대로 특정 프로세스가 CPU를 점유하는 동안 다른 프로세스가 CPU를 점유하여 CPU 사용을 선점당하는 것을 의미한다. 이는 CPU 점유가 필요한 프로세스에 의해 기존에 CPU를 점유하는 프로세스를 강제로 중단시키는 것을 말한다.

 

Non-Preemeptive

비선점은 선점과 달리 특정 프로세스가 CPU를 점유하는 경우, 인터럽트 또는 프로세스가 종료될때까지 다른 프로세스는 CPU를 점유하지 못한다.

 

 

CPU Scheduling Algoritms

프로세스의 도착 순서, 작업의 크기, 선점, 비선점 등 다양한 기준을 통해 다음에 사용할 프로세스를 선택하는 알고리즘들이 있다.

 

FCFS(First-Come, First-Served)

해당 알고리즘은 FIFO와 같은 방식으로 가장 먼저 작업을 요청한 프로세스 부터 처리되는 방식이다.

 

Process	Burst Time (msec)
P1	24
P2	3
P3	3

표와 같이 P1 - P3 순으로 프로세스가 도착한 경우 P1 부터 순차적으로 처리되게 된며, FCFS는 비선점 방식을 사용하기에 프로세스가 작업을 종료할 때 까지 다른 프로세스는 선점할 수 없다.

 

위의 예시를 FCFS로 스케줄링 하면, CPU 스케줄링을 판단하는 기준 중 Waiting Time이 커져 효율적이지 못한것을 알 수 있다. P1 - P3의 Wating Time은 각각 0, 24, 27로 Average Wating Time은 17msec가 된다. 즉, 작업 시간이 가장 긴 프로세스를 우선적으로 처리하게 되면 이후의 프로세스의 Wating Time이 길어지는 Convoy Effect가 발생한다.

 

SJF(Shortest-Job-First)

해당 알고리즘은 이름에서도 알 수 있듯이 작업 시간이 가장 짧은 프로세스를 우선적으로 선택하는 방식이다.

 

Process	Burst Time (msec)
P1	6
P2	8
P3	7
P4	3

도착 시간은 모두 동일하다고 생각할 때 표와 같은 작업 시간을 가지는 경우, SJF는 P4 - P1 - P3 - P2 순으로 실행할 프로세스를 선택하게 된다. 이 때 P1 - P4의 Wating Time은 3, 16, 9, 0으로 평균 Average Wating Time은 7msec가 된다. 이를 FCFS로 처리할 경우, Average Wating Time은 10.25msec이다.

 

하지만 이 방식은 현실에서는 사용할 수 없다. 왜냐하면 특정 프로세스가 작업하는데 걸리는 시간을 판단하는 것은 다소 어렵기 때문이다. 이와 같은 과정을 위해 작업하는데 걸리는 시간을 판단하여야 하는데 이는 오버헤드가 된다.

 

Priority

해당 알고리즘은 우선순위가 높은 프로세스를 먼저 선택하는 방식이다. 만약 1 - 10의 우선순위가 있다면 Linux에서는 숫자가 작을 수록 높은 우선순위를 가진다

 

Process	Burst Time (msec)	Priority
P1	10	3
P2	1	1
P3	2	4
P4	1	5
P5	5	2

우선순위에 따라 스케줄링 할 경우 P2 - P5 - P1 - P3 - P4 순으로 처리된다. 이 때 P1 - P5의 Wating Time은 6, 0, 16, 18, 1로 Average Wating Time은 8.2msec가 된다.

 

Starvation & Aging

우선순위에 따라 스케줄링을 할 경우 Starvation(기아) 상태가 발생하게 된다.

예를 들어, 우선순위 5인 프로세스가 있고 새로 작업을 요청하는 프로세스의 우선순위가 5보다 높은 경우 해당 프로세스는 작업을 처리하지 못하게 된다. 이를 기아 상태라고 한다.

 

이를 막기 위해, Wating 시간이 길어지면 우선순위를 높이는 Aging을 사용하여 기아가 발생하지 않도록 한다.

 

RR(Round-Robin)

해당 방식은 모든 프로세스가 동일한 작업시간(Time Slice)을 사용하는 하는 방식을 말한다. 예를 들어 최대 작업 시간이 3ms라고 한다면 프로세스는 3ms 만큼 작업을 하고 선점되어 다른 프로세스가 사용할 수 있도록 한다.

 

Process	Burst Time (msec)
P1	24
P2	3
P3	3

표와 같은 상황에서 Time Slice가 4mesc일 경우 P1 - P3의 Wating Time은 6 + 4 + 7이며 Average Wating Time은 5.66msec가 된다. 하지만 Time Slice가 짧아지거나 길어질 경우 Average Wating Time은 바뀌게 된다. 만약 Time Slice가 크다면 FCFS와 유사할 것이고, 너무 짧을 경우 Context Switchig의 오버헤드가 증가하여 효율적이지 않게 된다. 이에 적적한 Time Slice를 설정하는 것이 중요하다.