- 프로세스들은 각 큐들을 오가며 수행됨
- job queue : 현재 시스템 내에 있는 모든 프로세스의 집합
- ready queue : 현재 메모리 내에 있으면서 CPU를 잡아서 실행되기를 기다리는 프로세스의 집합
- device queue : I/O 장치의 처리를 기다리는 프로세스의 집합
- long-term scheduler (장기 스케줄러 = job scheduler)
- 어떤 프로세스에게 메모리를 할당할지 결정 (new -> ready)
- degree of multiprogramming을 제어 (메모리에 몇 개의 프로그램이 동시에 올라가는지)
- short-term scheduler (단기 스케줄러 = CPU scheduler)
- 어떤 프로세스에게 CPU를 줄지 결정 (ready -> running)
- medium-term scheduler (중기 스케쥴러 = swapper)
- 어떤 프로세스에게서 메모리를 뺏아가 디스크로 내쫓을지 결정
- degree of multiprogramming을 제어
- I/O bound process : CPU burst는 적고 I/O burst가 많은 작업 ex) 사용자와 인터렉티브한 프로그램
- CPU bound process : CPU burst가 많고 I/O burst가 적은 작업 ex) 과학 계산용 프로그램
- 컴퓨터 안에는 이러한 여러 종류의 프로세스가 섞여있기 때문에 CPU 스케쥴링이 필요함
- I/O bound process는 사용자와 인터렉티브하기 때문에 적절한 시간 내에 응답을 해야함 -> CPU를 우선적으로 할당!
- ready queue에 있는 프로세스들 중에서 어떤 프로세스에게 CPU를 줄지 결정하는 매커니즘
- 이슈1) 어떤 프로세스에게 CPU를 줄 것인가
- 이슈2) CPU를 할당하고 나면 해당 프로세스가 계속 쓰게할 것인가(non-preemptive) 중간에 뺏어올 수도 있는가(preemptive)
- CPU scheduler
- ready 상태의 프로세스 중에서 CPU 제어권을 넘거줄 프로세스를 선택
- 커널 안에서 스케쥴링을 하는 코드
- Dispatcher
- 스케쥴러에 의해 선택된 프로세스에게 CPU 제어권을 넘겨줌 (context switching!)
- 커널 안에서 CPU 제어권을 넘겨주는 코드
- FCFS (First Come First Serve)
- 먼저 온 순서대로 CPU를 할당 / non preemptive
- 단점) convoy effect : CPU burst time이 긴 프로세스가 먼저 온다면 전체적인 waiting time이 길어짐
- SJF (Shortest Job First)
- CPU burst time이 가장 짧은 프로세스에게 CPU를 할당 / non preemptive
- 단점) starvation : CPU burst time이 짧은 프로세스를 선호하기 때문에 긴 프로세스는 무한정 기다림
- SRTF (Shortest Remain Time First)
- 남은 CPU burst time이 가장 짧은 프로세스에게 CPU를 할당 / preemptive
- 단점) starvation : CPU burst time이 짧은 프로세스를 선호하기 때문에 긴 프로세스는 무한정 기다림
- Priority Scheduling
- 우선순위가 제일 높은 프로세스에게 CPU를 할당 / preemptive, non preemptive
- 단점) starvation : 우선순위가 낮은 프로세스는 무한정 기다림
- 해결책) aging : 시간이 흐를때마다 프로세스의 우선순위를 증가시킴
- Round Robin
- 모든 프로세스에게 동일한 크기의 할당 시간(time quantum, q)만큼 CPU를 할당
- 할당 시간이 지나면 프로세스는 CPU를 뺏기고 ready queue로 이동
- 장점) responsse time이 짧음 / waiting time과 CPU burst time이 비례
- q가 커지면 FCFS, q가 작아지면 context switch 오버헤드가 큼
- CPU burst time이 섞여있을때 효율적