스케줄러
프로세스를 스케줄링하기 위한 Queue는 아래와 같이 세가지가 존재한다.
- Job Queue: 현재 시스템 내에 있는 모든 프로세스의 집합
- Ready Queue: 현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스의 집합
- Device Queue: Device I/O 작업을 대기하고 있는 프로세스의 집합
각각의 Queue에 프로세스들을 넣고 빼주는 스케줄러에도 크게 세가지 종류가 존재한다.
장기 스케줄러 (Long-term scheduler / job scheduler)
메모리는 한정되어 있는데 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리(일반적으로 디스크)에 임시 저장된다. 이 pool에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 Ready Queue로 보낼 지 결정하는 역할을 한다.
- 메모리와 디스크 사이의 스케줄링을 담당
- 프로세스에 메모리 및 각종 리소스를 할당 (admit)
- degree of Multiprogramming (DOM) 제어 (실행중인 프로세스의 수 제어)
- 프로세스의 상태 new -> ready (메모리 할당)
cf. 메모리에 프로그램이 너무 많이 올라가도, 너무 적게 올라가도 성능이 좋지 않은 것이다. 참고로 time sharing system 에서는 장기 스케줄러가 없다. 그냥 곧바로 메모리에 올라가 ready 상태가 된다.
cf. 작업들이 시스템 내에 들어오는 것을 승인하는 것이기 때문에 승인 스케줄링(Admission scheduling)이라고도 한다.
단기 스케줄러 (Short-term scheduler / CPU scheduler)
- CPU와 메모리 사이의 스케줄링을 담당
- Ready Queue에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정
- 프로세스에 CPU를 할당 (scheduler dispatch)
- 프로세스의 상태: Ready -> Running -> Waiting -> Ready
- 보통 매 100ms마다 수행되는데, 수행되는 텀이 짧기 때문에 단기 스케줄러
중기 스케줄러 (Medium-term scheduler / Swapper)
- 메모리의 공간 확보를 위해 프로세스를 통째로 메모리에서 디스크로 쫒아냄 (swapping)
- 프로세스에게서 메모리 할당을 해제 (deallocate)
- degree of Multiprogramming (DOM) 제어
- 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러
- 프로세스의 상태: Ready -> Suspended
Process State - Suspended (Stopped)
외부적인 이유로 프로세스의 수행이 정지된 상태로 메모리에서 내려간 상태를 의미한다. 프로세스가 전부 swap out 된다. blocked 상태는 다른 I/O 작업을 기다리는 상태이기 때문에 스스로 Ready State로 돌아갈 수 있지만, 이 상태에서는 외부적인 이유로 suspendeing 되었기 때문에 스스로 돌아갈 수 없다.
Swapping: Swap out, Swap in 을 하는 행위
Swap out: 프로세스를 메모리에서 디스크로 쫒아내는 행위
Swap in: Swap out한 프로세스를 다시 메모리로 load 하는 행위
비선점형과 선점형 스케줄링
스케줄링 적용 시점에 따라 비선점형과 선점형 2가지로 구분된다.
비선점형 스케줄링 (Non-preemptive Scheduling)
어떤 프로세스가 CPU를 할당받으면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때까지 계속 실행되도록 보장한다. 순서대로 처리되는 공정성이 있고 다음에 처리해야 할 프로세스와 관계없이 응답시간을 예상할 수 있다. 선점 방식보다 스케줄러 호출 빈도도 낮고 문맥 교환에 의한 오버헤드가 적다.
일괄 처리 시스템에 적합하며, CPU 사용시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로 처리율이 떨어질 수 있다는 단점이 있다.
비선점 스케줄링 종류
- FCFS 스케줄링 (First Come First Served Scheduling)
- SJF 스케줄링 (Shortest Job First Scheduling)
- HRRN 스케줄링 (Highest Response Ratio Next Scheduling)
선점형 스케줄링 (Preemptive Scheduling)
어떤 프로세스가 CPU를 할당받아 실행 중에 있어도 다른 프로세스가 실행중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있다. 모든 프로세스에게 CPU 사용시간을 동일하게 부여할 수 있다. 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하여 긴급한 프로세서를 제어할 수 있다. 운영체제가 프로세서 자원을 선점하고 있다가 각 프로세스의 요청이 있을 때 특정 요건들을 기준으로 자원을 배분하는 방식이다.
선점 스케줄링 종류
- RR 스케줄링 (Round Robin Scheduling)
- SRTF 스케줄링 (Shortest Remaining-Time First Scheduling)
- 다단계 큐 스케줄링 (Multilevel Queue Scheduling)
- 다단계 피드백 큐 스케줄링 (Multilevel Feedback Queue Scheduling)
- RM 스케줄링 (Rate Monotonic Scheduling)
- EDF 스케줄링 (Earliest Deadline First Scheduling)
CPU 스케줄러
FCFS (First Come First Served)
특징
- 먼저 자원을 요청한 프로세스에게 자원을 할당해주는 방식. 즉, 순서대로 처리한다.
- 비선점형 스케줄링
프로세스가 일단 CPU를 할당받으면 CPU burst가 완료될 때까지 CPU를 반환하지 않는다. 할당되었던 CPU가 반환될 때만 스케줄링이 이루어진다.
문제점
- convoy effect
소요시간이 긴 프로세스가 먼저 도달하여 효율성을 낮추는 현상이 발생한다.
SJF (Shortest Job First)
특징
- 프로세스의 CPU burst time(CPU 사용 시간)이 짧은 프로세스에게 먼저 할당하는 방식이다.
- 비선점형 스케줄링
문제점
- starvation (기아 현상)
효율성을 추구하는게 가장 중요하지만 특정 프로세스가 지나치게 차별받으면 안되는 것이다. 이 스케줄링은 극단적으로 CPU 사용이 짧은 job 을 선호한다. 그래서 사용시간이 긴 프로세스는 거의 영원히 CPU를 할당받을 수 없다.
SRTF (Shortest Remaining Time First)
특징
- SJF와 비슷하나, 새로운 프로세스의 CPU burst time이 현재 실행중인 프로세스보다 짧으면 새로운 프로세스를 먼저 실행한다.
- 새로운 프로세스가 도착할 때마다 CPU burst time을 확인하여 context switch 할 지 판단한다.
- 선점형 스케줄링
문제점
- starvation
- 새로운 프로세스가 도달할 때마다 스케줄링을 다시하기 때문에 CPU burst time(CPU 사용 시간)을 측정할 수 없다.
Priority Scheduling
특징
- 우선순위가 높은 프로세스에게 CPU를 할당하는 스케줄링. 우선순위란 정수로 표현되고, 숫자가 작을수록 우선순위가 높다.
- 선점형 스케줄링 방식
더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU를 선점한다. - 비선접형 스케줄링 방식
더 높은 우선순위의 프로세스가 도착하면 Ready Queue의 Head에 넣는다.
문제점
- starvation
- 무기한 봉쇄 (Indefinite blocking)
실행 준비는 되어있으나 CPU를 사용하지 못하는 프로세스를 CPU가 무기한 대기시키는 상태
해결책
- aging
아무리 우선순위가 낮은 프로세스라도 오래 기다리면 우선순위를 높여준다.
RR (Round Robin)
특징
- 현대적인 CPU 스케줄링
- 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 갖게 된다.
- 할당 시간이 지나면 프로세스는 선점당하고 Ready Queue의 제일 뒤에 가서 다시 줄을 선다.
- CPU 사용시간이 랜덤한 프로세스들이 섞여 있을 경우에 효율적
RR이 가능한 이유는 프로세스의 context를 save할 수 있기 때문이다.
장점
Response time이 빨라진다.
n개의 프로세스가 Ready Queue에 있고 할당시간이 q(time quantum)인 경우 각 프로세스는 q 단위로 CPU 시간의 1/n을 얻는다. 즉, 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.- 프로세스가 기다리는 시간이 CPU를 사용할 만큼 증가한다. 공정한 스케줄링이라고 할 수 있다.
주의할 점
설정한 time quantum이 너무 커지면 FCFS와 같아진다. 또 너무 작아지면 스케줄링 알고리즘의 목적에는 이상적이지만 잦은 context switch로 overhead가 발생한다. 그렇기 때문에 적당한 time quantum을 설정하는 것이 중요하다.
출처
https://github.com/JaeYeopHan/Interview_Question_for_Beginner/blob/master/OS/README.md#스케줄러
https://ko.wikipedia.org/wiki/스케줄링_(컴퓨팅)
https://jhnyang.tistory.com/372
