프로세스 스케줄링

프로세스 스케줄링의 개요

프로세스 스케줄링(Process Scheduling)의 개념

• 프로세스의 생성 및 실행에 필요한 시스템의 자원을 해당 프로세스에 할당하는 작업
• 다중 프로그래밍 운영체제에서 자원의 성능을 향상시키고 효율적인 프로세서의 관리를 위해 작업 순서를 결정하는 것

프로세스 스케줄링의 목적

• 모든 작업들에 대한 공평성 유지, 단위 시간당 처리량 최대화, 응답 시간 및 반환 시간 최소화, 운영체제의 오버헤드 최소화

바람직한 스케줄링 정책

• CPU 이용을 최대화, 응답 시간 및 반환 시간 최소화, 대기 시간 최소화

 

프로세스 스케줄링 기법

비선점(Non-Preemptive) 스케줄링

• 한 프로세스가 일단 CPU를 할당받으면 다른 프로세스가 CPU를 강제로 빼앗을 수 없고, 사용이 끝날 때까지 기다리는 방식
• 모든 프로세스들에 대한 요구를 공정히 처리하여 응답 시간의 예측이 용이함
• CPU의 사용 시간이 짧은 프로세스들이 사용 시간이 긴 프로세스들로 인하여 오래 기다리는 경우가 발생할 수 있음

FIFO (First In First Out)	- 준비 상태 큐에 도착한 순서대로 CPU를 할당하는 기법 - FCFS(First Come First Service)라고도 함 예) FIFO 스케줄링에서 다음과 같은 3개의 작업에 대하여 모든 작업들의 평균 대기 시간 및 평균 반환 시간은? - 실행 순서 : P1 → P2 → P3 - 대기 시간 : P1(0), P2(10), P3(40) - 평균 대기 시간 : (0 + 10 + 40) / 3 = 16.66 - 반환 시간 : P1(13), P2(10), P3(50) - 평균 반환 시간 : (13 + 45 + 50) / 3 = 36
SJF (Shortest Job First)	- 준비 상태 큐에서 기다리고 있는 프로세스들 중에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 스케줄링 기법 - 평균 대기 시간을 최소화함 예) SJF 스케줄링에서 다음과 같이 4개의 작업이 준배 상태 큐에 있을 때 모든 작업들의 평균 대기시간 및 평균 반환 시간은? - 실행 순서 : P2 → P1 → P4 → P3 - 대기 시간 : P2(0), P1(3), P2(9), P4(16) - 평균 대기시간 : (0 + 3 + 9 + 16) / 4 = 7 - 반환 시간 : P2(3), P1(9), P4(16), P3(24) - 평균 반환 시간 : (3 + 9 + 16 + 24) / 4 = 13
HRN (Highest Response -ratio Next)	- 어떤 작업이 서비스받을 시간과 그 작업이 서비스를 기다린 시간으로 결정되는 우선순위에 따라 CPU를 할당하는 기법 - 우선순위 계산식 = (대기 시간 + 서비스를 받을 시간) / 서비스를 받을 시간 예) HRN 방식으로 스케줄링할 경우, 입력된 작업이 다음과 같을 때 처리되는 작업 순서는?
우선순위 (Priority)	- 준비 상태 큐에서 대기하는 프로세스에게 부여된 우선순위가 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법 - 우선순위가 낮은 프로세스는 무한 정지(Indefinite Blocking)가 발생할 수 있으며, 에이징(Aging) 기법으로 이를 해결할 수 있음

 

선점(Preemptive) 스케줄링

• 한 프로세스가 CPU를 할당받아 실행 중이라도 우선순위가 높은 다른 프로세스가 CPU를 강제적으로 빼앗을 수 있는 방식
• 긴급하고 높은 우선순위의 프로세스들이 빠르게 처리될 수 있음
• 선점을 위한 시간 배당에 대한 인터럽트용 타이머 클럭(Clock)이 필요함
• 온라인 응용에 적합한 스케줄링

RR (Round Robin)	- 주어진 시간 할당량(Time Slice) 안에 작업을 마치지 않으면 준비 상태 큐의 가장 뒤로 배치됨 - 시분할 시스템(Time-sharing System)을 위해 고안된 방식 - 시간 할당량이 커지만 FCFS 스케줄링과 같은 효과를 얻을 수 있음 - 시간 할당이 작아지면 프로세스 문맥 교환이 자주 일어남
SRT (Shortest Remaining Time)	- 작업이 끝나기까지의 실행시간 추정치가 가장 작은 작업을 먼저 실행시키는 기법 - FIFO 기법보다 평균 대기 시간이 감소됨 - 작업 시간이 큰 경우 오랫동안 대기하여야 함
다단계 큐 (Multi-Level Queue)	프로세스들을 우선순위에 따라 상위, 중위, 하위 단계의 단계별 준비 상태 큐를 배치하는 기법
다단계 피드백 큐 (Multi-Level Feedback Queue)	각 준비 상태 큐마다 부여된 시간 할당량 안에 완료하지 못한 프로세스는 다음 단계의 준비 상태 큐로 이동하는 기법