프로세스 스케줄링

학습 목표

1. 프로세스 스케줄링의 개요와 정책을 이해한다.

2. 스케줄링 성능평가 기준을 이해한다.

3. 다양한 스케줄링 기법을 이해한다.

 

3.1 프로세스 스케줄링

- 스케줄링 : 여러 가지 작업의 처리순서를 결정하는 것을 의미

- 프로세스 스케줄링 : 주어진 프로세스가 여러 개인 경우, 어떤 순서대로 처리할지를 운영체제가 결정하는 것

 

3.1.1 스케줄링 단계

1) 상위 단계 스케줄링 = 장기 스케줄링

- 시스템에 들어와 작업 큐에서 선택하여 프로세스를 생성한 후 프로세스 준비 큐에 전달하는 역할

- 선택 기준 : 입출력 중심 작업과 연산 중심 작업을 균형 있게 선택하도록 작업순서를 결정

- 선택 기준 이유 : 시스템 자원을 효율적으로 이용하기위해

- 예시 : 많은 입출력 작업을 연속적으로 선택하면 입출력장치는 바쁘고 CPU는 대기에 많은 시간 허비

많은 연산 작업을 선택하면 CPU는 바쁘고 입출력장지는 사용하지 않아서 시스템 자원 사용이 비효율적.

 

2) 하위단계 스케줄링 = 단기 스케줄링

- 작업 큐에 있는 프로세스를 선택하여 사용 가능한 CPU를 할당하는 역할이다.

-스케줄링의 수행 주체는 디스패처이다.

-이 스케줄링은 빈번하게 발생하므로 디스패처는 메모리에 늘 상주해야 한다.

 

3) 중간단계 스케줄링 = 중기 스케줄링

-프로세스를 일시적으로 메모리에서 제거하여 중지시키거나 중지된 프로세스를 다시 활성화 시키는 역할

-시스템의 단기적인 부하를 조절한다.

 

3.1.2 스케줄링의 목표

1) 공정성

- 모든 프로세스가 적정 수준에서 CPU 작업을 할 수 있게 하는 것

 

2) 균형성

- 시스템의 자원들이 충분히 활용될 수 있게 하는 것

 

운영체제 유형별 스케줄링 목표

1)일괄처리 운영체제 

- 처리량 극대화

- 반환시간 최소화

- CPU 활용 극대화

 

2) 시분할 스케줄링

- 빠른 응답시간

- 과다한 대기시간 방지

 

3) 실시간 운영체제

- 처리기한 맞추기

 

3.1.3 스케줄링 정책

1) 선점 스케줄링 정책(PREEMPTIVE SCHEDULING POLICY)

- 실행 중인 프로세스에 인터럽트를 걸고 다른 프로세스에 CPU를 할당할 수 있는 방식

- 높은 우선순위를 먼저 처리해야 하는 경우 유용하다.

- 단점

: 오버헤드가 발생한다.

: CPU의 모든 레지스터와 기타 운영체제에 따라 요구되는 프로세스의 상태를 문맥(context)이라고 하는데, 프로세스가 종료되지 않은 상태에서 선점 방식에 따라 CPU가 다른 프로세스에 할당되려면 문맥 교환이 필요하다.

: 문맥 교환이랑 CPU가 현재 실행하고 있는 프로세스의 문맥을 프로세스 제어 블록에 저장하고, 다른 프로세스의 프로세스 제어 블록으로부터 문맥을 복원하는 작업이다. 

: 문맥 교환에도 시간과 자원이 사용되기 때문에 고려할 필요가 있다.

 

2) 비선점 스케줄링 정책(NONPREEMPTIVE SCHEDULING POLICY)

- 실행 중인 프로세스를 바로 준비상태로 전이시킬 수 없는 방식.

- CPU를 할당받아 실행이 시작된 프로세스는 대기상태나 종료상태로 전이될 때까지 계속 실행상태에 있는다.

- 강제적인 문맥 교환이 없어 오버헤드가 없다.

- 대신 시간이 오래걸린다. 따라서 실행시간이 짧은 프로세스가 오래 기다리게 되는 경우가 발생한다.

 

3.1.4 스케줄링의 평가 기준

1) 평균대기시간

- 각 프로세스가 수행이 완료될 때까지 준비 큐에서 기다리는 시간의 합의 평균값

 

2) 평균반환시간

- 각 프로세스가 생성된 시점(준비 큐에 들어온 시점)부터 수행이 완료된 시점까지의 소요시간의 평균값

 

3.2 스케줄링 알고리즘

 

3.2.1 FCFS 스케줄링(First-Come First-Served)

- 비선점 방식 중 가장 간단하다.

- 프로세스는 준비 큐에 도착한 순서에 따라 디스패치되며, 일단 CPU를 차지하면 수행이 완료된 후 다음이 수행된다.

- 따라서 시분할 운영체제나 실시간 운영체제에는 적합하지 않다.

- 예시

: 프로세스 A, B, C, D -> CPU 사이클 3, 2, 4, 1 이면

A의 대기시간은 0, 반환시간은 3,

B의 대기시간은 3, 반환시간은 5

C의 대기시간은 5, 반환시간은 9

D의 대기시간은 9, 반환시간은 10

평균대기시간은 (0+3+5+9) / 4 = 4.25

평균반환시가은 (3+5+9+10) / 4 = 6.75

- FCFS 스케줄링은 프로세스들의 도착순서에 따라 평균반환시간이 크게 변하는 단점도 있다.

 

FCFS 스케줄링 알고리즘에서 도착시간과 실행시간으로 계산하기

프로세스	A	B	C	D
도착시간	0	1	3	5
CPU 사이클	3	2	4	1

위와 같은 도착시간과 실행시간이 있을 때 

A는 시각 0에 도착하여 3에 종료했으므로 반환시간은 3이고 대기시간은 0이다.

B는 시각 1에 도착하여 A가 끝나는 시각인 3에 디스패치되었으므로 대기시간은 3 - 1 = 2이고 1에 도착해서 5에 끝났으므로 반환시간은 4이다.
C의 대기시간은 2이고 반환시간은 6이다.
D의 대기시간은 4이고 반환시간은 5이다.

따라서 평균대기시간은 (0+2+2+4) / 4 = 2이고 평균반환시간은 4.5이다.

 

3.2.2 SJF 스케줄링(Shortest Job First)

- 준비 큐에서 기다리는 프로세스 중 실행시간이 가장 짧다고 예상되는 것을 먼저 실행하는 비선점 방식 알고리즘이다.

- 실행예정시간을 사용자의 추정치에 의존해서 실제와 다를 수 있다.

- 비선점이기에 FCFS처럼 시분할이나 실시간 운영체제에는 적합하지 않다.

 

3.2.3 SRT 스케줄링(Shortest Remaining Time)

- SJF의 선점 방식 버전

- 준비 큐에서 기다리는 프로세스 중 남은 실행시간이 가장 짧다고 예상되는 것을 먼저 디스패치하는 알고리즘이다.

- 만약 준비 큐에 새로 들어온 프로세스의 예상실행시간이 실행 중인 것의 남은 시간보다 짧다면, 새로 들어온 프로세스가 즉시 디스패치된다.

- SJF 스케줄링보다 평균대기시간이나 평균반환시간에서 효율적이다.

- 하지만 선점을 위한 문맥 교환때문에 오버헤드가 더 크다.