스케줄링 기법

핵심 Keyword

1. 스케줄링 기법 (비선점 스케줄링 / 선점 스케줄링)

2. FCFS(FIFO), SJH, HRN, 기한부, 우선순위 

3. 선점 우선순위, SRT, Round Robin, 다단계 큐(MQ), 다단계 피드백 큐(MFQ)

---

스케줄링 기법

비선점 스케줄링 (Non-preemptive)
: 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법입니다. 
[ FCFS(FIFO), SJH, HRN, 기한부, 우선순위 등 ]

선점 스케줄링 (Preemptive)
: 하나의 프로세스가 CPU를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법입니다. 
[ 선점 우선순위, SRT, Round Robin, 다단계 큐(MQ), 다단계 피드백 큐(MFQ) 등 ]

 

비선점 스케줄링

FCFS(First Come First Service) = FIFO(First In First Out)
: 준비상태 큐에 도착한 순서에 따라 차례로 CPU를 할당하는 기법입니다. 

SJF(Shortest Job First)
: 준비상태 큐에서 기다리고 있는 프로세스들 중에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법입니다. 

HRN(Highest Response-ratiod Next)
: 실행 시간이 긴 프로세스에 불리한 SJF 기법을 보완하기 위한 것으로, 대기 시간과 서비스(실행) 시간을 이용하는 기법입니다. (대기시간 + 서비스시간) / 서비스 시간 을 계산하여 우선순위를 부과하며 그 숫자가 높은 것부터 낮은 순으로 우선순위가 부여됩니다. 

기한부(Deadline)
: 프로세스에게 일정한 시간을 주어 그 시간 안에 프로세스를 완료하도록 하는 기법입니다. 프로세스가 제한된 시간 안에 완료되지 않을 경우 제거되거나 처음부터 다시 실행해야 합니다. 

우선순위(Priority)
: 준비상태 큐에서 기다리는 각 프로세스마다 우선순위를 부여하여 그 중 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법입니다. 우선순위가 동일할 경우 FCFS 기법으로 CPU를 할당합니다. 이때 우선순위는 시스템에 의해 자동으로 결정되기도 하고, 외부 사항에 의해 결정되기도 합니다. 내부적 우선순위는 시간제한, 기억장치 요구, 개방된 파일 수, 평균 입&출력 실행 시간 등으로 결정됩니다. 외부적 우선순위는 작업을 지원하는 정책, 부서 등이 있습니다. 

 

선점 스케줄링

선점 우선순위
: 준비상태 큐이 프로세스들 중에서 우선순위가 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법입니다. 

SRT (Shortest Remaining Time)
: 비선점 스케줄링인 SJF 기법을 선정 형태로 변경한 기법으로, 선점 SJF 기법이라고도 합니다. 현재 실행중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의 실행 시간을 비교하여 가장 짧은 실행 시간을 요구하는 프로세스에게 CPU를 할당합니다. 

RR(Round Robin)
: 시분할 시스템(Time Sharing System)을 위해 고안된 방식으로, FCFS 알고리즘을 선점(Preemptive) 형태로 변형한 기법입니다. FCFS 기법과 같이 준비상태 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당받지만 각 프로세스는 시간 할당량(Time Slice, Quantum) 동안만 실행한 후 실행이 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고 준비상태 큐의 가장 뒤로 배치됩니다. 

다단계 큐 (MQ; Multi-level Queue)
: 프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 준비상태 큐를 사용하는 기법입니다. 

다단계 피드백 큐 (MFQ; Multi-level Feedback Queue)
: 특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비상태 큐로 이동할 수 없는 다단계 큐 기법을 준비상태 큐 사이를 이동할 수 있도록 개선한 기법입니다.