스케줄러
시스템이 실행하고자 할 때 프로세서(CPU)를 프로그램에 할당하는 과정
- Job Queue: 현재 시스템 내에 있는 모든 프로세스
- Ready Queue: 현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스 집합
- Device Queue: Device I/O 작업을 대기하고 있는 프로세스 집합
장기 스케줄러(Long-term scheduler or job scheduler)
한정된 메모리에 많은 프로세스들이 한꺼번에 메모리에 올라왔을 때, 대용량 메모리(디스크)에 임시로 저장. 어떤 프로세스에 메모리를 할당하여 Ready Queue에 보내는지 결정
- 메모리와 디스크 사이에 스케줄링 담당
- 프로세스에 메모리를 할당(admit)
- degree of Multiprogramming 제어(실행중인 프로세스 수 제어)
- 프로세스 상태: new → ready
cf) 메모리에 프로그램이 너무 많이 올라가도, 너무 적게 올라가도 성능이 좋지 않은 것이다. time sharing system에는 장기 스케줄러가 존재하지 X 따라서 곧바로 메모리에 올라가 ready 상태가 된다.
단기 스케줄러(Short-term schduler or CPU scheduler)
: CPU와 메모리 사이의 스케줄링을 담당
- Ready Queue에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정
- 프로세스에 CPU를 할당
- CPU와 메모리 사이(ready→running→waiting→ready)의 스케줄링 담당
Ready Queue에 있는 프로세스 중 “어떤 프로세스를 running 시키지?”를 단기 스케줄러가 담당. 실제 프로세스에 CPU를 할당하는 것은 “Dispatcher”가 수행
중기 스케줄러(Mid-term Scheduler or Swaaper)
- 여유 공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄 (swapping)
- 프로세스에게서 memory 를 deallocate
- degree of Multiprogramming 제어
- 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라가는 것을 조절하는 스케줄러.
- 프로세스의 상태: ready -> suspended
Suspended
: 외부적인 이유로프로세스가 메모리에서 디스크로 내려간 상태(swap out)
스스로 event를 기다리는 waiting 상태와 달리 외부적인 요인으로 정지되었기 때문에 스스로 다시 동작할 수 없다.
CPU 스케줄링
CPU 하나는 동시에 여러 개의 프로세스를 처리할 수 없기 때문에, 한 순간에 어떤 프로세스가 CPU를 사용할 수 있게 하는지 결정하는 정책이다.
→ CPU를 효율적이고 잘 사용하도록 하기
- Batch Sysytem: 가능하면 많은 일을 수행하도록 하는 것. 시간보다 처리량(throughout)이 중요
- Interactive System: 빠른 응답 시간, 적은 대기 시간.
- Real-Time System: deadline안에 수행되도록 하는 것.
스케줄링이 일어나는 시점
- 실행(running) → 대기(waiting) : 비선점
- 실행(running) → 준비(ready) : 선점(인터럽트 발생)
- 대기(waiting) → 준비(ready) : 선점(입출력 종료될 때)
- 종료(terminated) : 비선점
선점(Preemptive) 스케줄링
한 프로세스가 CPU를 차지하고 있을 때, 다른 프로세스가 현재 진행중인 프로세스를 중단하고 CPU를 차지할 수 있는 방법
긴급을 요하는 우선 순위를 갖는 시분할 처리, 실시간 처리에 유용
비선점(Non-Preemptive) 스케줄링
한 프로세스가 CPU를 차지하고 있을 때, 프로세스가 종료하거나 대기상태로 전환해 CPU를 해제할 때 까지 CPU를 점유하는 방법
모든 프로세스에 대해 공정한 처리가 가능하지만 긴급 응답에는 좋지 못하다. 짧은 작업이 긴 작업이 끝날 때 까지 기다려야 하는 문제점(Convoy Effect)이 발생할 수 있다.
*Convoy Effect : 하나의 큰 프로세스가 자원을 오랫동안 점유하여 작은 프로세스들이 자원을 할당받지 못하는 문제
CPU 스케줄링 종류
비선점 스케줄링
- FCFS(First Come, First Served)
: 큐에 도착한 순서대로 CPU 할당
- 구현 간단
- Convoy Effect 발생할 수 있음
- SJF(Shorted Jop First)
: 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행
- FCFS보다 평균 대기 시간 감소, 짧은 작업에 유리
- Starvation이 생길 수 있다. → Aging으로 해결
*Starvation: 우선 순위가 작거나 처리시간이 긴 프로세스가 자원을 계속 할당받지 못하는 문제
*Aging: Ready Queue에 있는 프로세스에 나이를 부여. 얼마나 오래 기다렸는가를 고려하여 처리가 긴 프로세스임에도 길다면 자원을 할당.
선점 스케줄링
- Priority Scheduling
: Ready Queue에서 우선순위가 높은 프로세스 먼저 CPU를 할당받는 방법
- 우선순위가 낮은 프로세스는 Starvation 생길 수 있음.
- Aging으로 해결
- Round Robin
: 프로세스가 자원을 할당받고 동작할 시간을 할당받는 방식. Ready Queue가 원형 큐로 설계되어서 시간을 다 쓰면 OS가 인터럽트를 걸어 현재 PCB가 큐의 가장 뒤로 이동하는 방식
- 모든 프로세스가 공정하게 시간을 할당받아서 Starvation 발생X
- 시간을 너무 짧게 할당하면 Context Switching이 자주 발생해 오버헤드 발생
- SRTF(Shortest Remaining Time First)
: SJF와 동일하지만 현재 작업할 프로세스보다 시간이 짧은 프로세스가 들어오면 새로운 스케줄링된다.
- MLQ(MultiLevel-Queue)
: 여러 종류의 Ready Queue로 구분하여 각 Ready Queue마다 독자적인 스케줄링 알고리즘을 사용하여 CPU할당.
- MFQ(Multilevel Feedback Queue)
: MLQ 스케줄링보다 더 고도화된 알고리즘으로, MLQ에서 Starvation이 생길 수 있는 점을 보완한 스케줄링 기법.
- 우선순위가 높은 프로세스에게 RR방식으로 CPU 할당
- time quantum안에 끝나면 우선 순위 높은대로 유지
- time quantum안에 끝내지 못하면 다음 Queue로 전달.
