CPU 스케줄링
스케줄링이란?
목적
프로세스가 항상 CPU를 사용하는 것은 아니다. 한 프로세스를 실행 가능한 시점까지 실행하고, I/O 등 CPU를 사용하지 않는 작업을 할 때는 다른 프로세스를 실행한다면 CPU 사용 효율을 높일 수 있다. (빠른 응답시간 / 적은 대기시간)
즉, 스케줄링이란 다중 프로그래밍의 목적인 CPU 이용률을 최대화하기 위해 준비 완료 큐에 있는 프로세스에게 어떤 기준으로 CPU를 할당할 것인지를 결정하는 방법이다.
- 공평성 : 모든 프로세스가 공평하게 작업하도록 한다.
- 효율성 : 놀고있는 자원이 생기지 않도록 한다.
- 안정성 : 중요 프로세스가 먼저 작동하도록 배정
- 확장성 : 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치
- 반응 시간 보장 : 적절한 시간 내에 프로세스에 응답 해야 한다.
- 무한 연기 방지 : 작업이 무한히 연기 되는 것을 방지
최신 운영체제에서는 실질적으로 프로세스가 아니라 커널 수준 스레드를 스케줄 한다.
프로세스 스케줄링 발생 시점
- 프로세스가 실행 상태(running)에서 대기 상태(waiting)으로 전환될 때
ex) I/O 요청에 의한 대기 - 프로세스가 실행 상태(running)에서 준비 상태(ready)로 전환될 때
ex) 타이머 인터럽트가 발생했을 때 - 프로세스가 대기 상태(waiting)에서 준비 상태(ready)로 전환될 때
ex) I/O 종료 시 - 프로세스가 종료되었을 때(terminated)
스케줄링 적용 시점에 따라 2가지로 구분할 수 있다.
✅ 비선점 스케줄링(nonpreemptive) : 어떤 프로세스가 CPU를 할당 받으면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때까지 계속 실행되도록 보장한다. 종류로는 FIFO, SJF, 우선순위, HRN, 기한부 등이 있다.
장점 :
- 일괄 처리 시스템에 적합하며 순서대로 처리되는 공정성이 있고 응답 시간을 예측이 용이하다.
- 문맥 교환에 의한 오버헤드가 비교적 적다.
단점
- 장기간 CPU 독점으로 인해 처리율이 떨어질 수 있다.
✅ 선점 스케줄링(preemptive) :
하나의 프로세스가 CPU를 차지하고 있을 때, 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식이다. 종류로는 SRT, 선점 우선순위, Round Robin, 다단계 큐 등이 있다.
장점
- 시분할 시스템에서 주로 사용되며 우선순위가 높은 프로세스를 빠르게 처리할 수 있다.
단점
- 프로세스 간 공유 자원에 대한 문제가 발생할 수 있다.
- 처리 시간을 예측하기 힘들고 높은 우선순위 프로세스들이 계속 들어오는 경우 오버헤드를 초래한다.
프로세스를 스케줄링하기 위한 Queue 에는 세 가지 종류가 존재한다.
- Job Queue : 현재 시스템 내에 있는 모든 프로세스의 집합 (주 메모리에 존재)
- Ready Queue : 현재 메모리 내에 있으면서 CPU 를 잡아서 실행되기를 기다리는 프로세스의 집합 (연결 리스트로 저장)
- Device Queue : Device I/O 작업을 대기하고 있는 프로세스의 집합
각각의 Queue 에 프로세스들을 넣고 빼주는 스케줄러에도 크게 세 가지 종류가 존재한다.
유형
장기 스케줄러(Long-term scheduler or job scheduler)
메모리와 디스크 사이에 스케쥴링을 담당한다.
한정된 메모리에 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 디스크에 임시로 저장된다. 이 pool 에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 ready queue 로 보낼지 결정하는 역할을 한다. (new -> ready상태로 전이)
+) 시분할 시스템에서는 장기 스케줄러가 없다. 그냥 곧바로 메모리에 올라가 ready 상태가 된다.
단기스케줄러(Short-term scheduler or CPU scheduler)
CPU 와 메모리 사이의 스케줄링을 담당한다.
Ready Queue 에 존재하는 프로세스 중 어떤 프로세스에 CPU 를 할당(scheduler dispatch)할지 결정한다. (ready -> running -> waiting -> ready)
중기스케줄러(Medium-term scheduler or Swapper)
가상메모리 체제에서 너무 많은 프로세스가 적재되면 하드디스크 입출력의 과다와 CPU경쟁이 심해져 시스템이 거의 멈추는 Trashing 현상을 방지하기 위해,
메모리에 올라간 프로세스 수를 조절하기위해 메모리 상의 프로세스를 통째로 디스크로 쫒아내는 swap out을 하고, 시간이 흘러 메모리에 여유가 생기면 swap-in 한다.
swap out되는 프로세스는 ready, waiting상태이며 ready상태보단 waiting상태가 당장 cpu를 할당받을 가능성이 낮기 때문에 우선적으로 swap out됩니다.
+) CPU가 할당되어 실행 중인 주기를 CPU 버스트(CPU Burst), 입/출력이 이루어지는 주기를 I/O 버스트(I/O Burst)라 부른다.
