1. CPU Scheduling?
CPU 스케줄링은 다중 프로세스 시스템에서 CPU를 효율적으로 할당하고 관리하기 위한 방법과 정책을 결정하는 작업입니다.
2. CPU Scheduler, Dispatcher
CPU Scheduler
ready queue에 존재하는 process 중 하나를 선택
Dispatcher?
CPU Scheduler에 의해 선택된 Process에게 CPU를 할당
즉, CPU Scheduler를 통해 ready queue에서 Scheduling을 기다리는 process 중 하나를 선택하고, 해당 Process에게 Dispatcher가 CPU를 할당하는 것을 통해 Scheduling이 실행된다.
Dispatch latency는 프로세스나 스레드가 실행 대기 큐에서 선택되어 CPU를 사용할 수 있는 상태로 전환될 때까지 걸리는 시간입니다.
3. Scheduling Criteria
서로 다른 CPU Scheduling 방식을 비교하기 위한 기준을 말한다.
-
CPU utilization(CPU 이용률)
CPU를 가능한 바쁘게 유지할 수 있는 정도
최대화가 목표 -
Throughtput(처리율)
시간 당위당 처리를 완료하는 프로세스 수
최대화가 목표 -
Turnaround Time
프로세스가 시작해서 끝날 때 까지 걸리는 시간
최소화가 목표 -
Waiting Time
프로세스가 Ready queue에서 대기한 시간의 총합
최소화가 목표 -
Response Time
요청 후 응답이 오기까지 걸린 시간
최소화가 목표
4. FCFS(First-Come First-Served) = FIFO(First Input First Out)
- 스케줄링 타입 : 비선점
- 기아 발생 가능성 : X
(but 스레드가 오류로 인해 무한 루프 실행 시 생길 수 O) - 알고리즘 : 먼저 도착한 스레드 먼저 스케줄링
- 성능 이슈 :
a. 처리율 낮음
b. Convoy Effect
(CPU Burst time이 긴 thread가 CPU를 오래 사용하면 늦게 도착한 CPU Burst Time이 짧은 thread는 오래 대기하게 됨.)
- FCFS Scheduling
-
Waiting Time
=> P1 = 0, P2 = 24, P3 = 27
Average waiting time = (0+24+27)/3 = 17 -
Turnaround Time
=> P1 = 24, P2 = 27, P3 = 30
Average Turnaround Time = (24+27+30) / 3 = 27
Q. 그럼 더 좋은 Scheduling 정책을 위해 FCFS의 문제를 해결하는 방법은 무엇이 있을까? => Shortest Job First
