[OS-09] 프로세스 스케줄링

1. 스케줄링의 개요

• 스케줄링은 프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에 할당하는 작업을 의미

- 작업 스케줄링(Job Scheduling)

• 어떤 프로세스가 시스템의 자원을 차지할 수 있는지를 결정하여 준비상태로 큐로 보내는 작업을 의미
• 작업 스케줄러(Job Scheduler)에 의해 수행

- 프로세서 스케줄링(Processor Scheduling)

• 프로세스가 실행되기 위해 CPU를 할당받는 시기와 특정 프로세스를 지정하는 작
• 프로세서 스케줄러(Processor Scheduler)에 의해 프로세서 스케줄링 및 문맥 교환이 수행됨

* 프로세서 스케줄러

• 하나의 프로세스를 준비(ready) 상태에서 실행(run) 상태로 전이시킴

2. 스케줄링의 목적

• 처리율 증가
• CPU 이용률 증가
• 오버헤드 최소화
• 응답 시간 최소화
• 반환시간 최소화
• 대기시간 최소화
• 모든 작업에 대해 공평성을 유지해야 하며, 경과시간의 예측이 가능해야 함

3. 비선점 스케줄링 기법의 종류

• 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법
• 모든 프로세스에 대한 요구를 공정하게 처리
• 프로세스 응답 시간 예측이 용이
• 중요한 작업이 중요하지 않은 작업을 기다리는 경우가 발생할 수 있음
• 비선점 스케줄링 종류에는 FIFO, SJF, 우선순위, HRN, 기한부 등의 알고리즘이 있음
• 대화형 시스템에 부적합

- FIFO(First In First Out) = FCFS(First Come First Service)

• 가장 간단한 방식이고 비선점 방식의 스케줄링
• 중요하지 않은 작업이 중요한 작업을 기다리게 할 수 있음
• 대화식 시스템에 부적합

프로세스 번호	P1	P2	P3
실행 시간	20	4	6

<결과>

프로세스 번호	P1	P2	P3	평균
실행 시간	20	4	6	30/3
대기 시간	0	20	24	44/3
반환 시간	20	24	30	74/3

---

- SJF(Shortest Job First)

• 준비상태 큐에서 기다리고 있는 프로세스들 중에서 실행시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법
• 가장 적은 평균 대기 시간을 제공하는 최적 알고리즘
• 실행시간이 긴 프로세스는 실행 시간이 짧은 프로세에게 할당 순위가 밀려 무한 연기 상태가 발생가능

프로세스 번호	P1	P2	P3
실행 시간	20	4	6

<결과>

프로세스 번호	P1	P2	P3	평균
실행 시간	4	6	20	30/3
대기 시간	0	4	10	14/3
반환 시간	4	10	30	44/3

---

- HRN(Highest Response-ratio Next)

• 실행시간이 긴 프로세스에 불리한 SJF 기법을 보완하기 위한 것으로 대기 시간과 서비스 시간을 이용하는 기법
• 우선순위를 계산하여 그 숫자가 가장 높은 것부터 낮은 순으로 우선순위가 부여
• 우선순위 계산식 = 대기시간 + 서비스 시간 / 서비스 시간
• 우선순위 계산 예

작업	대기 시간	서비스 시간
A	5	5
B	10	6
C	15	7
D	20	8

• A : (5 + 5) / 5 = 2
• B : (10 + 6) / 6 = 2.67
• C : (15 + 7) / 7 = 3.14
• D : (20 +8) / 8 = 3.5
• 우선순위가 가장 높은 것은 D 

---

- 기한부(Deadline)

• 프로세스에게 일정한 시간을 주어 그 시간 안에 프로세스를 완료하도록 하는 기법
• 프로세스가 제한된 시간 안에 완료되지 않을 경우 제거되거나 처음부터 다시 실행
• 기한부 스케줄링에 필요한 집약적 자원관리는 많은 오버헤드를 일으킬 수 있음
• 사용자는 그 작업에 필요한 자원에 관한 정확한 정보를 시스템에 제시하여야 함

---

- 우선순위(Priority)

• 준비상태 큐에서 기다리는 각 프로세스마다 우선순위를 부여하여 그중 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법
• 우선순위가 동일할 경우 FCFS 기법으로 CPU를 할당
• 가장 낮은 순위를 부여받은 프로세스는 무한 연기 또는 기아 상태(aging)가 발생할 수 있음

* 에이징(Aging) 기법

• 프로세스가 자원을 기다리고 있는 시간에 비례하여 우선순위를 부여함으로써 무한 연기 문제를 방지

4. 선점 스케줄링 기법의 종류

• 하나의 프로세스가 CPU를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법
• 우선순위가 높은 프로세스를 빠르게 처리할 수 있음
• 주로 빠른 응답 시간을 요구하는 대화식 시분할 시스템에서 사용
• 선점 스케줄링의 종류에는 SRT, Round Robin, 선점 우선순위, 다단계 큐, 다단계 피드백 큐 등

- SRT(Shortest Remaining Time)

• 비선점 스케줄링인 SJF 기법을 선점 형태로 변경한 기법
• 현재 실행 중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의 실행 시간을 비교하여 가장 짧은 실행시간을 요구하는 프로세스에게 CPU를 할당하는 기법으로 시분할 시스템에 유용
• 실행 시간을 추적해야 하므로 오버헤드가 증가함

---

- RR(Round Robin)

• 시분할 시스템을 위해 고안된 방식으로 FIFO기법을 선점 형태로 변형한 기법
• 할당되는 시간이 클 경우 FIFO 기법과 같아짐
• 할당되는 시간이 작은 경우 문맥 교환 및 오버헤드가 자주 발생
• 프로세스들이 배당 시간 내에 작업되지 못하면 준비상태 큐의 맨뒤로 이동
• 시스템이 사용자에게 적합한 응답 시간을 제공해 주는 대화식 시스템에 유용

---

- 선점 우선순위

• 준비상태 큐의 프로세스들 중에서 우선순위가 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법

---

- 다단계 큐(MQ, Multi-level Queue)

• 프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 준비상태 큐를 사용하는 기법
• 프로세스가 특정 그룹의 준비상태 큐에 들어갈 경우 다른 준비상태 큐로 이동할 수 없음
• 하위 준비 상태 큐에 있는 프로세스를 실행하는 도중이라도 상위 준비상태 큐에 프로세스가 들어오면 상위 프로세스에게 CPU를 할당해야 함

---

- 다단계 피드백 큐(MFQ, Multi-level Feedback Queue)

• 특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비 상태 큐로 이동할 수 없는 다단계 큐 기법을 준비상태 큐 사이를 이동할 수 있도록 개선한 기법

- CPU 스케줄링 특성 중 대화형 시스템에서 가장 중요한 인자

• 반응 시간(response time)

- CPU 스케줄링을 평가하는 기준

• 처리량(throughput)
• 대기시간(watiting time)
• 균형 있는 자원 이용