3.4 CPU Scheduling Algorithm

CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘

CPU Scheduling Algorithms

3.4 CPU 스케줄링 알고리즘

CPU 스케줄링의 개요

CPU 스케줄링이란 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당하는 것을 말합니다. CPU 스케줄링 알고리즘은 CPU 이용률을 높이고, 주어진 시간에 많은 일을 할 수 있게 하며, 준비 큐(ready queue)에 있는 프로세스를 적절하게 선택하여 효율적으로 실행하는 것을 목표로 합니다.

CPU 스케줄링 알고리즘의 분류

CPU 스케줄링 알고리즘은 크게 **비선점형(non-preemptive)**과 **선점형(preemptive)**으로 나눌 수 있습니다.

비선점형 방식

비선점형 방식은 프로세스가 스스로 CPU 소유권을 포기하지 않는 방식입니다. 이는 경계로 프로세스를 중지하지 않으므로, 컨텍스트 스위칭으로 인한 부하가 적습니다. 주요 비선점형 알고리즘은 다음과 같습니다:

1. FCFS(First Come First Served): 가장 먼저 온 프로세스를 가장 먼저 처리하는 알고리즘입니다. 이 방식의 단점은 오래 실행되는 프로세스 때문에 다른 프로세스들이 오래 기다리는 **운반 효과(convoy effect)**가 발생할 수 있다는 점입니다.

2. SJF(Shortest Job First): 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘입니다. 그러나, SJF 알고리즘은 실행 시간이 긴 프로세스가 실행되지 않는 기아(starvation) 현상을 유발할 수 있습니다.

3. 우선순위(Priority): 프로세스에 우선순위를 부여하여 우선순위가 높은 프로세스를 먼저 실행합니다. 우선순위가 낮은 프로세스는 기아 현상이 발생할 수 있기 때문에 **노화(aging)**를 사용하여 시간이 지남에 따라 우선순위를 높여줍니다.

선점형 방식

선점형 방식은 현재 실행 중인 프로세스를 중단시켜 다른 프로세스에게 CPU를 할당하는 방식입니다. 주요 선점형 알고리즘은 다음과 같습니다:

1. 라운드 로빈(Round Robin, RR): 각 프로세스에 동일한 할당 시간을 주고, 할당 시간이 지나면 다음 프로세스를 실행합니다. 할당 시간이 짧을수록 응답 시간이 빨라지지만, 컨텍스트 스위칭의 오버헤드가 증가할 수 있습니다.

2. SRF(Shortest Remaining Time First): 실행 중인 프로세스와 준비 큐에 있는 프로세스를 비교하여 남은 실행 시간이 가장 짧은 프로세스를 먼저 실행합니다. 이는 SJF의 선점형 버전입니다.

3. 다단계 큐(Multilevel Queue): 준비 큐를 여러 개의 큐로 나누어, 각 큐에 속한 프로세스를 특정 스케줄링 알고리즘을 사용하여 처리합니다. 예를 들어, 시스템 프로세스는 높은 우선순위 큐에서 FCFS로, 사용자 프로세스는 낮은 우선순위 큐에서 라운드 로빈으로 처리하는 방식입니다.

비선점형 알고리즘의 상세 설명

FCFS (First Come First Served)

FCFS는 가장 먼저 도착한 프로세스를 가장 먼저 처리하는 방식입니다. 이 방식은 이해하기 쉽고 구현이 간단하지만, 운반 효과로 인해 대기 시간이 길어질 수 있습니다.

+------------------+
| 프로세스 도착 순서  |
| A -> B -> C      |
+------------------+
| CPU 실행 순서     |
| A -> B -> C      |
+------------------+

SJF (Shortest Job First)

SJF는 실행 시간이 가장 짧은 프로세스를 먼저 실행합니다. 이 방식은 평균 대기 시간을 최소화할 수 있지만, 실행 시간이 긴 프로세스는 기아 상태에 빠질 수 있습니다.

+-------------------------+
| 프로세스 실행 시간         |
| A (5) -> B (2) -> C (1) |
+-------------------------+
| CPU 실행 순서            |
| C -> B -> A             |
+-------------------------+

우선순위 스케줄링

우선순위 스케줄링은 각 프로세스에 우선순위를 부여하여 높은 우선순위의 프로세스를 먼저 실행합니다. 우선순위가 낮은 프로세스는 기아 상태에 빠질 수 있기 때문에, 노화 기법을 사용하여 시간이 지남에 따라 우선순위를 높여줍니다.

+-------------------------+
| 프로세스 우선순위          |
| A (1) -> B (3) -> C (2) |
+-------------------------+
| CPU 실행 순서            |
| A -> C -> B             |
+-------------------------+

선점형 알고리즘의 상세 설명

라운드 로빈 (Round Robin)

라운드 로빈은 각 프로세스에 동일한 할당 시간을 주고, 할당 시간이 지나면 다음 프로세스를 실행합니다. 이 방식은 응답 시간을 개선할 수 있지만, 할당 시간이 너무 짧으면 컨텍스트 스위칭 오버헤드가 증가할 수 있습니다.

+--------------------------------+
| 프로세스 할당 시간                |
| A (2) -> B (2) -> C (2)        |
+--------------------------------+
| CPU 실행 순서                   |
| A -> B -> C -> A -> B -> C ... |
+--------------------------------+

SRF (Shortest Remaining Time First)

SRF는 남은 실행 시간이 가장 짧은 프로세스를 먼저 실행합니다. 이는 SJF의 선점형 버전으로, 중간에 더 짧은 작업이 들어오면 현재 실행 중인 작업을 중단하고 더 짧은 작업을 먼저 실행합니다.

+--------------------------+
| 프로세스 남은 시간          |
| A (5) -> B (2) -> C (1)  |
+--------------------------+
| CPU 실행 순서             |
| C -> B -> A              |
+---------------------------+

다단계 큐 (Multilevel Queue)

다단계 큐는 준비 큐를 여러 개의 큐로 나누고, 각 큐에 속한 프로세스를 특정 스케줄링 알고리즘으로 처리합니다. 예를 들어, 시스템 프로세스는 높은 우선순위 큐에서 FCFS로, 사용자 프로세스는 낮은 우선순위 큐에서 라운드 로빈으로 처리하는 방식입니다.

+------------------------+
| 큐 구성                 |
| 시스템 프로세스: FCFS    |
| 상호작용적 프로세스: SJF  |
| 배치 프로세스: RR        |
+------------------------+

결론

CPU 스케줄링 알고리즘은 CPU 자원을 효율적으로 분배하여 시스템 성능을 최적화하는 중요한 역할을 합니다. 비선점형 알고리즘과 선점형 알고리즘 각각의 장단점을 이해하고, 적절한 상황에서 사용하는 것이 중요합니다. 이를 통해 시스템의 응답 시간, 처리량, 대기 시간을 최적화할 수 있습니다.