비선점형 스케줄링 기법

1. FIFO(FCFS) - First In First Out

FIFO 스케줄링은 먼저 도착한 순서대로 CPU를 할당하는 가장 간단한 스케줄링 기법입니다. 프로세스들이 대기열에 도착한 순서대로 실행되기 때문에 공정한 처리가 가능합니다. 하지만 프로세스의 실행시간이 다양한 경우, 실행시간이 긴 프로세스가 먼저 도착하게 되면 평균 대기시간이 증가하고, 이러한 현상을 "Convoy Effect"라고 합니다.

Convoy Effect 예시: P1(실행시간 20), P2(실행시간 5), P3(실행시간 10) 대기시간: P1(0), P2(20), P3(25) 평균 대기시간: (0 + 20 + 25) / 3 = 15

2. SJF(Shortest Job First)

SJF 스케줄링은 실행시간이 가장 짧은 프로세스에게 CPU를 할당하는 기법입니다. 이는 평균 대기시간을 최소화하여 처리 성능을 향상시키는 최적의 스케줄링 기법입니다. 하지만 실행시간이 긴 프로세스가 무한정 기다리는 "기아(Starvation)" 문제가 발생할 수 있습니다.

Starvation 예시: P1(실행시간 5), P2(실행시간 20), P3(실행시간 10) P1이 먼저 실행되고, P2가 도착했지만 P1의 실행이 끝나지 않아 P2는 기다림 P3가 도착했지만 P2의 실행이 끝나지 않아 P3도 기다림

3. HRN(HRRN) - Highest Response Ratio Next

HRN 스케줄링은 SJF 스케줄링의 기아 문제를 해결하기 위해 도입된 기법입니다. 대기시간과 실행시간의 비율을 계산하여 우선순위를 결정합니다. 대기시간이 길어질수록 우선순위가 높아지기 때문에 기아 문제를 완화할 수 있습니다.

4. 우선순위(Priority)

우선순위 기법은 프로세스들에게 우선순위를 부여하여 높은 우선순위를 가진 프로세스를 먼저 실행하는 기법입니다. 선점형 우선순위 기법은 실행 중인 프로세스의 우선순위가 더 높은 프로세스에게 CPU를 빼앗기는 것이 가능하며, 비선점형 우선순위 기법은 대기 상태에 있는 프로세스들끼리만 우선순위를 비교합니다.

우선순위 기법은 중요한 작업에 높은 우선순위를 부여하여 중요 작업이 빠르게 처리되도록 하는데 유용합니다. 하지만 낮은 우선순위를 갖는 프로세스가 무한정 기다리는 "기아(Starvation)" 문제가 발생할 수 있습니다.

선점형 스케줄링 기법

1. RR(Round-Robin)

RR 스케줄링은 시분할 시스템에서 주로 사용되는 선점형 스케줄링 기법입니다. 각 프로세스에게 고정된 시간(타임 슬라이스)을 할당하고, 할당된 시간이 지나면 다른 프로세스에게 CPU를 넘겨주는 방식입니다. 각 프로세스는 순환하며 실행되기 때문에 응답시간이 빠르고 공정한 처리가 가능합니다. 단점은 프로세스에 할당된 시간이 너무 길거나 짧을 경우, 오버헤드가 발생할 수 있습니다.

2. SRT(Shortest Remaining Time)

SRT 스케줄링은 SJF 스케줄링의 선점형 버전으로, 현재 실행중인 프로세스의 남은 실행시간과 대기열에 도착한 프로세스의 실행시간을 비교하여 짧은 실행시간을 요구하는 프로세스에게 CPU를 할당하는 방식입니다. 선점형 SJF라고도 불리며, 각 프로세스마다 남은 실행시간을 계속 추적해야 하므로 오버헤드가 발생할 수 있습니다.

3. MLQ(Multi Level Queue) - 다단계 큐 스케줄링

MLQ 스케줄링은 프로세스들을 특정 그룹으로 분리하여 각 그룹마다 독자적인 Queue를 이용해 스케줄링하는 기법입니다. 프로세스의 특성과 종류에 따라 여러 단계로 분할할 수 있으며, 전면작업(Foreground Task)과 후면작업(Background Task)으로 구분할 수 있습니다.