운영체제 - CPU 스케줄링 2, 3

스케줄링 알고리즘

highest priority를 가진 프로세스에게 CPU를 할당한다.
두 가지 방식이 존재한다.
- NonPreemptive
  - 우선 순위가 더 높은 프로세스가 들어와도 선점당하지 않는다.
- Preemptive
  - 우선 순위가 더 높은 프로세스가 도착 시 선점당한다.
SJF도 일종의 priority schduling이라 할 수 있다.(우선순서 = 다음 CPU burst 예측 시간)
약점
- Starvation
  - 우선 순위가 낮은 프로세스는 영원히 실행이 안 될 수가 있다.
- 해결책
  - Aging : 시간에 따라 프로세스의 우선 순위를 증가시켜준다.

각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가진다.
할당 시간이 지나면 CPU 선점을 빼앗긴다. 선점당한 후 Ready Queue의 제일 뒤에 가서 다시 줄을 선다.
Ready Queue에 N개의 프로세스가 존재하고 할당 시간이 Q인 경우, 어떤 프로세스도 (N-1) * Q 이상 기다리지 않는다.
Performance
- Q가 크면 : FCFS
- Q가 작으면 : context switch가 너무 자주 일어나 오버헤드가 커진다.
- 일반적으로 SJF보다 average turnaround time이 길지만 response time은 더 짧다.

Ready Queue를 여러 개로 분할
- foreground (interactive)
- background (batch - no human interaction)
각 큐는 독립적인 스케줄링 알고리즘을 가진다.
- foreground - RR
- background - FCFS
큐에 대한 스케줄링 필요
- foreground에 완전한 우선순위를 부여
  - background의 starvation이 발생할 수 있다.
- Time slice
  - 각 큐에 CPU time을 적절한 비율로 할당한다.
  - background의 starvation 문제를 해결할 수 있다.
  - 예를 들어 80%는 foreground의 RR에, 20%는 background의 FCFS에 할당