스케줄러
프로세스의 흐름
장기 스케줄러(Long-term scheduler)
메모리는 한정되어 있는데 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리(일반적으로 디스크)에 임시로 저장한다. 이 pool에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 ready queue로 보낼지 결정하는 역할을 한다.
- new(디스크)->ready(메모리)로 갈 프로세스를 스케줄링
- 프로세스에 memory 및 각종 리소스를 할당
- degree of Multiprogramming 제어
단기 스케줄러(Short-term scheduler or CPU scheduler)
- CPU와 메모리 사이(ready->running->waiting->ready)의 스케줄링을 담당
- Ready Queue에 있는 프로세스 중 어떤 프로세스를 running 시킬지 결정
Ready Queue에 있는 프로세스 중 "어떤 프로세스를 running 시킬지까지만" 단기 스케줄러가 결정하고 실제 프로세스에 CPU를 할당하는 것은 "Dispatcher"가 수행함!
중기 스케줄러(Mid-term scheduler or Swapper)
- 여유공간(메모리)를 마련하기 위해서 프로세스를 통째로 메모리에서 디스크로 쫓아냄(Swapping)
- 프로세스에게서 memeory를 할당 해제(ready->suspended)
- 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절
suspended(stopped) : 외부적인 이유로 프로세스가 메모리에서 디스크로 내려간 상태(swap out), 스스로 event를 기다리는 waiting 상태와 달리 외부적인 요인으로 인해 정지 되었기 때문에 스스로 다시 동작할 수 없다.
CPU 스케줄러
Ready Queue에 있는 프로세스들을 스케줄링하는 스케줄러(ready -> new)
선점형(preemptive) vs 비선점형(non-preemptive)
프로세스의 흐름
CPU 스케줄링에 사용되는 두가지 방식으로,
비선점형 방식은 임의의 프로세스가 CPU를 할당 받으면 해당 프로세스가 종료(terminated)될 때까지 CPU를 점유하는데 반해,
선점형 방식은 어떤 프로세스가 CPU를 할당 받더라도 우선순위가 더 높은 프로세스가 ready queue에 들어오거나 입출력이나 이벤트 대기, time out이 발생하는 경우 프로세스가 종료되지 않아도 다른 프로세스에 의해 CPU를 선점당할 수 있다(다른 프로세스에게 CPU를 넘겨주고 대기 상태가 된다).
Priority Schduling(우선 순위 스케줄링)
우선순위가 가장 높은 프로세스에게 CPU 를 할당하는 스케줄링이다. 우선순위란 정수로 표현하게 되고 작은 숫자가 우선순위가 높다.
Starvation(기아 현상)
우선 순위 스케줄링 방식에서 우선 순위가 낮은 프로세스가 우선 순위가 높은 프로세스에게 계속 밀려 CPU의 할당을 받지 못하는 현상
-> aging을 통해 해결 가능
aging
ready queue에서 오래 대기한 만큼 해당 프로세스의 우선순위를 높여주는 것
스케줄링 알고리즘
FCFS(First Come Fisrt Served)
특징
- 선입선출 방식 #FIFO
- 비선점형 스케줄링
문제점
- 소요시간이 긴 프로세스가 CPU를 차지하고 있는 경우 다른 프로세스들이 수행되지 못한다.
SJF(Shortest Job First)
특징
- ready queue에 존재하는 프로세스 중 가장 CPU Burst Time이 짧은 프로세스에게 CPU 할당
- 비선점형 스케줄링
CPU Burst Time : CPU를 할당 I/O가 일어나기 전까지 CPU를 사용하는 시간
문제점
- starvation 발생 가능
SRTF(Shortest Remaining Time First)
특징
- 새로운 프로세스가 도착할 때마다 각 프로세스의 남은 CPU Burst Time이 짧은 순으로 우선순위를 부여한다.
- 선점형 스케줄링
문제점
- starvation 발생 가능
- 새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU Burst Time을 측정할 수 없다.
SRTF는 SJF의 preemptive 방식이다
RR(Round Robin)
특징
- 각 프로세스는 동일한 크기의 time quantum(할당시간)을 갖게 된다.
- time-out 당하는 경우 ready queue의 맨 뒤로 가서 대기한다.
- CPU 사용시간이 랜덤한 프로세스들이 섞여있을 경우 효율적이다.
문제점
- time quantum이 너무 커지면 FCFS와 같아진다.
