[Daily morning study] CPU 스케줄링 알고리즘 (FIFO, SJF, Round Robin)
#daily morning study
CPU 스케줄링 알고리즘
CPU 스케줄링은 운영체제가 프로세스에게 CPU를 할당하는 방법을 말합니다. CPU 스케줄링 알고리즘의 주요 목적은 시스템의 자원을 효율적으로 사용하고, 프로세스의 응답 시간을 최소화하며, 시스템의 전체적인 성능을 향상시키는 것입니다.
이 문서에서는 FIFO, SJF 및 Round Robin 스케줄링 알고리즘에 대해 다루겠습니다.
1. FIFO (First In, First Out)
FIFO는 가장 간단한 스케줄링 알고리즘 중 하나로, 먼저 도착한 프로세스가 먼저 CPU를 할당받습니다.
특징
- 대기 시간: 고정적이며, 대기 시간이 길어질 수 있음.
- 공정성: 모든 프로세스가 먼저 도착한 순서로 처리되므로 공정한 방식.
- 비효율성: 주로 긴 프로세스가 CPU를 독점하게 되므로 짧은 프로세스의 대기 시간이 늘어날 수 있음 (젖혀주기 문제).
예시
프로세스가 다음과 같이 도착했다고 가정해 보겠습니다.
| 프로세스 | 도착 시간 | 실행 시간 |
|---|---|---|
| P1 | 0 | 4 |
| P2 | 1 | 3 |
| P3 | 2 | 1 |
할당 순서는 P1 -> P2 -> P3가 됩니다.
시간 흐름: 0 1 2 3 4 5 6 7
CPU 할당: P1 P1 P1 P1 P2 P2 P2 P3
2. SJF (Shortest Job First)
SJF는 가장 짧은 실행 시간을 가진 프로세스가 먼저 CPU를 할당받는 방식입니다. 이 알고리즘은 평균 대기 시간을 최소화 한다는 장점이 있습니다.
특징
- 효율성: 짧은 프로세스가 우선 처리되어 대기 시간이 최소화될 수 있음.
- 공정성 문제: 긴 프로세스는 계속 미뤄질 수 있으며, 기아 문제가 발생할 수 있음.
- 비선형성: 프로세스의 실행 시간을 미리 알고 있어야 함.
예시
다음의 프로세스를 기준으로 SJF 알고리즘을 적용해보겠습니다.
| 프로세스 | 도착 시간 | 실행 시간 |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
여기서는 P2(4)를 먼저 처리하고 P4(5), P1(8), P3(9)의 순서로 진행됩니다.
시간 흐름: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
CPU 할당: P2 P2 P2 P2 P4 P4 P1 P1 P1 P1 P1 P1 P1 P3 P3 P3 P3 P3
3. Round Robin (RR)
Round Robin 알고리즘은 각 프로세스에 동일한 시간 할당량(타임 슬라이스)을 주고, 주어진 시간이 지나면 다음 프로세스로 전환하는 방식입니다. 이는 다수의 사용자에게 공정하게 시스템 자원을 배분하려는 목적을 가지고 있습니다.
특징
- 응답 시간: 대화형 시스템에 적합하여 빠른 응답 시간을 제공.
- 공정성: 모든 프로세스에 동일한 CPU의 기회를 제공.
- 기아 문제 해결: 모든 프로세스가 주기적으로 CPU를 사용할 수 있음.
예시
다음 프로세스를 Round Robin 알고리즘으로 처리해 보겠습니다. 타임 슬라이스를 2로 설정해봅시다.
| 프로세스 | 도착 시간 | 실행 시간 |
|---|---|---|
| P1 | 0 | 5 |
| P2 | 1 | 3 |
| P3 | 2 | 8 |
프로세스를 처리하는 순서는 다음과 같습니다.
시간 흐름: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
CPU 할당: P1 P1 P2 P2 P3 P3 P1 P1 P3 P3 P3 P3
P1, P2, P3의 순으로 업그레이드하며 타임슬라이스 2초씩 CPU 사용.
결론
CPU 스케줄링 알고리즘은 다양한 시스템 요구에 따라 적절하게 선택되어야 합니다. FIFO는 간단하지만 성능이 좋지 않을 수 있으며, SJF는 효율적이지만 기아 문제를 유발할 수 있습니다. Round Robin은 공정성을 유지하면서 대화형 시스템에 적합한 성능을 제공합니다. 각 알고리즘의 특성을 이해하고 활용하여 최적의 성능을 이끌어 내는 것이 중요합니다.
