[운영체제] 스케줄러(Scheduler)

스케줄러(Scheduler)

- 한정적인 메모리를 여러 프로세스가 효율적으로 사용할 수 있도록 다음 실행 시간에 실행할 수 있는 프로세스 중에 하나를 선택하는 역할

 

1) Scheduling Queues

- 프로세스를 관리하는 큐

 

(1) Job Queue(batch queue)

- 시스템 안의 모든 프로세스의 집합

 

(2) Ready Queue

- ready 상태의 메인메모리 안에 상주하는 모든 프로세스의 집합

 

(3) Device Queue

- I/O 장치 사용을 대기하는 프로세스들의 집합

 

2) 스케줄러 종류

(1) 장기 스케줄러(Long-term scheduler) / 잡 스케줄러(Job scheduler)

- degree of multiprogramming 제어

- 디스크와 메모리 사이의 스케줄링 담당

- 어떤 프로세스에 메모리를 할당할여 ready queue로 보낼지 결정하는 역할

 

(2) 단기 스케줄러(Short-term scheduler) / CPU 스케줄러(CPU scheduler)

- 메모리와 CPU 사이의 스케줄링 담당

- 어떤 프로세스를 running 상태로 전환 시킬지 결정하는 역할

 

(3) 중기 스케줄러(Mid-term scheduler) / 스와퍼(Swapper)

- degree of multiprogramming 제어

- 여유 공간을 마련하기 위해 프로세스를 통째로 메모리에서 디스크로 쫓아내는 역할(swap in/ swap out)

 

 

스케줄링 알고리즘(Scheduler Algorithm)

1) FCFS(First Come First Served)

- 비선점형 스케줄링 방식

- 먼저 도착한 프로세스가 CPU를 먼저 할당

- 큐를 이용해 쉽게 구현 가능

- 콘보이 현상 발생 가능

 

! 콘보이 현상(Convoy Effect)

- burst time 이 긴 프로세스가 먼저 도착해 다른 프로세스의 실행 시간이 전부 늦춰져 효율을 떨어뜨리는 현상

 

2) SJF(Shortest Job First)

- 비선점형 스케줄링 방식

- burst time이 짧은 프로세스가 먼저 CPU를 할당

- Starvation 발생 가능

 

! 기아 현상(Starvation)

- 계속해서 우선순위가 높은 프로세스(burst time이 짧은)가 먼저 실행되어 먼저 도착했어도 우선순위가 낮은 프로세스(burst time이 긴)가 게속해서 CPU를 할당받지 못하는 현상

 

3) SRT(Shortest Remaining Time First)

- 선점형 스케줄링 방식

- 남은 burst time이 더 짧은 프로세스에 CPU를 할당

- Starvation 발생 가능

 

4) 우선순위 스케줄링(Priority Scheduling)

- 선점과 비선점 두가지 방식에 모두 적용 가능

- 우선순위가 높은 프로세스에 CPU를 먼저 할당

- 기아 현상과 무기한 봉쇄가 발생할 수 있으며 에이징 기법을 통해 해결

 

! 에이징 기법(Aging)

- 먼저 도착한 프로세스가 나이를 계속 먹으며 우선순위가 올라가는 기법

 

5) 라운드 로빈(RR, Round Robin)

- 선점형 스케줄링 방식

- 프로세스에 동일한 할당 시간(Time Quantum)만큼 순서대로 계속 CPU를 할당

- 응답시간이 빠르며, 모든 프로세스가 공정하게 CPU를 할당받을 수 있음을 보장

- 단, CPU 할당 시간(Time Quantum)이 길 경우, FCFS랑 같아짐

 

6) 다단계 큐(Multilevel Queue)

- 선점 방식

- Background에서 돌아가는 프로세스와 Foreground의 프로세스에 다른 알고리즘을 적용하는 방식

- 큐 사이에 서로 다른 CPU 할당 시간(Time Quantum)을 적용

- Backgounrd 프로세스에는 FCFS, Foreground는 RR 알고리즘 적용

 

7) 다단계 피드백 큐(Multilevel Feedback Queue)

- 프로세스가 큐 사이를 이동 가능

- 각 큐에 서로 다른 CPU 할당 시간(Time Quantume)을 적용함으로써, 프로세스가 해당 시간 동안 작업을 다 처리하지 못했다면, 점점 긴 Time Quantum을 할당해주는 큐로 이동

- 우선순위는 Time Quantum이 짧은 큐가 높은

- Starvation이 발생 가능하며 Aging으로 해결 가능

 

 

선점과 비선점 스케줄링 알고리즘

1) 비선점(Nonpreemptive) : FCFS, SJF

(+) 모든 프로세스에 대한 공정한 처리

(+) 문맥교환으로 인한 오버헤드가 적음

(-) burst time이 긴 프로세스에 의해 burst time이 짧은 프로세스가 기다리는 현상이 생길 수 있음

 

2) 선점(Preemptive) : SRT, RR, Priority Scheduling, Multilevel Scheduling

(+) 우선순위가 높은 프로세스에 빠른 응답시간 보장

(-) 프로세스간 문맥교환이 자주 발생

(-) Starvation 발생 가능

 

 

Dispatch Latency와 Context Switching

1) Dispatch Latency

- 스케줄러가 선택한 프로세스를 CPU에 할당하는 요소를 Dispatcher라고 함

- Dispatcher가 하나의 프로세스를 중단하고, 다른 프로세스를 실행하기까지 소요하는 시간

 

2) Context Switching

- 인터럽트로 인해 다음 우선순위의 프로세스가 실행되어야 할 때, 기존의 상태(Context)를 저장하고, 다음 프로세스를 수행할 수 있도록 PCB로부터 상태(Context)를 레지스터에 적재하는 작업

 

 

좋은 스케줄링 방식 판단 기준

- CPU utilization

- Throughput

- Turnaround time

- Waiting time

- response time