Scheduling
Ready 상태에 있는 프로세스들 중 언제, 어떤 프로세스에게 CPU를 할당시킬 것인지 정하는 것
Scheduling을 통해 여러 프로세스를 왔다갔다하며 CPU를 최대로 활용할 수 있다.
scheduling은 Kernel Thread에서 실행된다.
Preemptive vs Non-Preemptive (선점형, 비 선점형 )
Preemptive: 스케줄러에 의해 실행 중인 프로세스의 CPU 할당을 헤제할 수 있다.
Non Preemptive: 프로세스가 작업을 마치고 릴리스될 때까지 CPU 할당을 유지한다.
CPU 스케줄링 결정
- Running -> waiting (I/O 발생)
- runnging -> ready (다른 프로세스 할당)
- waiting -> ready (I/O가 끝남)
- terminates
1, 4 = Non preemptive = 실행 중이지 않기 때문에 선점이 필요없다.
2, 3 = preemptive or Non preemptive = 실행 중에 할당을 바꾸기 때문에 선점이 필요하다.
Context Switch
실행 중인 프로세스의 CPU 할당을 바꾸는 것
Scheduler에 의해 스위칭 대상이 결정되고, 디스패처에 의해 스위칭 된다.
Scheduling 고려사항
CPU Utilization: CPU가 놀지않게 최대한으로 사용해야한다.
Throughput: 단위 시간당 완료되는 프로세스의 수
Turnaround time: 프로세스가 도착한 시간부터 완료된 시간, 즉 하나의 프로세스를 처리하는데 걸리는 시간
waiting time: 프로세스가 Ready Queue에 있는 총 시간
Response time: 사용자가 작업을 요청한 후 첫 번째 응답을 받는 시간, 즉 사용자가 느끼는 지연 시간
Scheduling 방법
FCFS: First Come First Served
- 먼저 요청한 프로세스를 무조건 먼저 처리
- 먼저 실행한 프로세스의 실행 시간이 길다면 뒤에 있는 프로세스는 너무 오래 기다려야함 (대기 시간 이슈)
SJF: Shortest Job First
- 실행 시간이 가장 짧은 프로세스 먼저 처리
- 짧은 작업을 먼저 하므로 total process waiting time이 줄어듬
- 긴 프로세스가 있는 상황에 짧은 프로세스가 계속해서 들어온다면, 처리시간이 오래 걸리는 작업은 무한 대기를 할 수도 있다.
SRTF: shotest remaining time frist
- 남은 시간이 가장 작은 프로세스가 CPU를 선점하여 Preemptive로 처리.
RR: Round Robin
- 하나의 작업을 다 하는 것이 아닌 작업을 일정 시간 단위로 쪼개서 실행하는 시분할 처리
- 시간을 쪼개서 일정 시간(time quantum) 마다 프로세스를 전환하므로 preemptive이다.
- time quantum을 너무 작게 나누면 잦은 context switching에 의한 오버헤드가 크고, 너무 크게 나누면 FCFS에 가까워진다.
Priority-based: RR에 우선순위를 추가해서 사용
- RR 방식도 SJF처럼 starvation 문제가 발생할 수 있기 때문에 aging 방법을 사용
- 할당을 못 받는 시간이 지속됨에 따라 우선순위를 높여줘서 언젠가는 꼭 실행될 수 있도록 하는 방법
MLQ: Multi Level Queue
- 우선순위 별로 ready queue를 따로 주는 방법
- 우선순위가 가장 높은 큐에 작업이 계속 들어오면 하위 우선순위를 가진 큐에 있는 프로세스들이 Starvation 상태가 될 수 있다.
MLFQ: Multi Level Feedback Queue
- quantum을 주고 할당받은 quantum 시간이 지나면 작업이 남아도 다음 큐로 이동하여 starvation 문제 해결
Real Time OS에서의 Scheduling
soft realtime: 작업의 조금 놓쳐도 괜찮다.
hard realtime: 작업을 반드시 deadline 안에 처리해야한다.