[바미] CPU 스케줄링 알고리즘

안녕하세요. 오늘은 CPU 스케줄링 알고리즘에 대해 알아보도록 하겠습니다.

CPU 스케줄링 알고리즘은 운영 체제의 핵심 기능 중 하나로, 여러 프로세스들이 CPU를 효율적으로 사용할 수 있도록 CPU 시간을 할당하는 방법입니다.

---

FCFS (First-Come, First-Served)

FCFS는 가장 단순한 CPU 스케줄링 알고리즘으로, 먼저 도착한 프로세스가 먼저 실행됩니다.

줄을 서는 방식과 비슷하여, 먼저 줄을 선 사람이 먼저 서비스를 받습니다.

특징

• 비선점형 스케줄링 : 현재 실행 중인 프로세스가 자발적으로 CPU를 놓을 때까지 실행됩니다.
• 공정성: 먼저 도착한 프로세스가 먼저 실행되므로 공정합니다.
• 간단함: 구현이 매우 간단합니다.

장단점

• 장점: 구현이 매우 간단하며, 공정합니다.
• 단점: Convoy effect(호위 효과)가 발생할 수 있습니다. 즉, 긴 작업이 짧은 작업들을 기다리게 만들어 전체 대기 시간이 길어질 수 있습니다.

예제

프로세스들이 다음과 같은 순서로 도착한다고 가정해보겠습니다.

• P1 (도착 시간: 0, 실행 시간: 5)
• P2 (도착 시간: 1, 실행 시간: 3)
• P3 (도착 시간: 2, 실행 시간: 8)

이 때 스케줄링 순서는 P1 -> P2 -> P3 입니다.

 

SJF(Shortest Job First)

SJF는 가장 짧은 실행 시간을 가진 프로세스를 먼저 실행하는 스케줄링 알고리즘입니다.
즉, 프로세스의 실행 시간이 짧을수록 우선적으로 실행됩니다.

특징

• 비선점형 스케줄링: 현재 실행 중인 프로세스가 자발적으로 CPU를 놓을 때까지 실행됩니다.

장단점

• 장점: 평균 대기 시간이 최소화됩니다.
• 단점: 실행 시간이 짧은 프로세스를 예측하기 어렵고, Starvation(기아) 문제가 발생할 수 있습니다.
  즉, 긴 작업이 계속 뒤로 밀릴 수 있습니다.

예제

프로세스들이 다음과 같은 순서로 도착한다고 예를 들어 보겠습니다.

• P1 (도착 시간: 0, 실행 시간: 6)
• P2 (도착 시간: 1, 실행 시간: 8)
• P3 (도착 시간: 2, 실행 시간: 7)
• P4 (도착 시간: 3, 실행 시간: 3)

스케줄링 순서는 P4 -> P1 -> P3 -> P2 입니다.

SRF (Shortest Remaining Time First) 또는 SRTF (Shortest Remaining Time First)

SRF는 SJF의 선점형 버전으로, 현재 남은 실행 시간이 가장 짧은 프로세스를 먼저 실행합니다.
새로운 프로세스가 도착하면 현재 실행 중인 프로세스와 남은 실행 시간을 비교하여 남은 시간이 더 짧은 프로세스로 교체합니다.

특징

• 선점형 스케줄링: 새로운 프로세스가 도착하면 즉시 스케줄링이 재평가됩니다.

장단점

• 장점: SJF와 같은 이점을 가지면서 평균 대기 시간을 더욱 최소화할 수 있습니다.
• 단점: 잦은 문맥 전환(Context Switch)이 발생하여 오버헤드가 증가할 수 있습니다. 또한 Starvation(기아) 문제가 여전히 발생할 수 있습니다.

예제

프로세스들이 다음과 같은 순서로 도착한다고 가정해보겠습니다.

• P1 (도착 시간: 0, 실행 시간: 8)
• P2 (도착 시간: 1, 실행 시간: 4)
• P3 (도착 시간: 2, 실행 시간: 9)
• P4 (도착 시간: 3, 실행 시간: 5)

스케줄링 순서는 도착 시간과 남은 실행 시간에 따라 계속 변경됩니다. 예를 들어, P1이 실행되다가 P2가 도착하면 P2로 전환됩니다.

 

 

RR (Round Robin)

RR는 각 프로세스에 동일한 시간 할당량(Time Quantum)을 순서대로 부여하는 스케줄링 알고리즘입니다.
시간 할당량이 지나면 프로세스는 대기열의 맨 뒤로 이동하고, 다음 프로세스가 실행됩니다.

특징

• 선점형 스케줄링: 일정 시간 동안만 프로세스가 실행되고, 이후 대기열로 돌아갑니다.

장단점

• 장점: 공정하고, 모든 프로세스가 일정 시간 안에 실행될 수 있도록 보장합니다.
• 단점: 시간 할당량이 너무 크면 FCFS와 비슷해지고, 너무 작으면 문맥 전환 오버헤드가 증가합니다.

예제

프로세스들이 다음과 같은 순서로 도착한다고 가정해보겠습니다.

• P1 (도착 시간: 0, 실행 시간: 4)
• P2 (도착 시간: 1, 실행 시간: 3)
• P3 (도착 시간: 2, 실행 시간: 2)
• P4 (도착 시간: 3, 실행 시간: 1)

시간 할당량이 2라고 가정하면, 스케줄링 순서는 P1 (2초) -> P2 (2초) -> P3 (2초) -> P4 (1초) -> P1 (남은 시간: 2초) -> P2 (남은 시간: 1초) -> P3 (남은 시간: 0초) -> P1 (남은 시간: 0초) -> P2 (남은 시간: 0초) 입니다.

 

---

요약

1. FCFS (First-Come, First-Served):
   • 가장 먼저 도착한 프로세스를 먼저 실행.
   • 단순하지만 긴 작업이 짧은 작업을 기다리게 할 수 있음.
2. SJF (Shortest Job First):
   • 실행 시간이 가장 짧은 프로세스를 먼저 실행.
   • 평균 대기 시간을 최소화하지만 기아 문제가 발생할 수 있음.
3. SRF (Shortest Remaining Time First) 또는 SRTF:
   • 남은 실행 시간이 가장 짧은 프로세스를 먼저 실행.
   • SJF보다 더 나은 대기 시간을 제공하지만 잦은 문맥 전환이 발생할 수 있음.
4. RR (Round Robin):
   • 모든 프로세스에 동일한 시간 할당량을 순서대로 부여.
   • 공정하고 모든 프로세스가 실행될 수 있지만, 시간 할당량의 크기가 성능에 큰 영향을 미침.