Scheduling Algorithms
- First-Come, First-Served (FCFS) Scheduling
- Shortest-Job-First (SJF) Scheduling
- Priority Scheduling
- Round-Robin (RR) Scheduling
- Multilevel Queue Scheduling
- Multilevel Feedback Queue Scheduling
FCFS Scheduling 선착순
The process that requests the CPU first is allocated the CPU first.
CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당합니다.
Non-preemptive Scheduling.
Simple to write and understand.
The implementation can be easily managed with a FIFO queue.
구현은 FIFO queue을 통해 쉽게 관리할 수 있습니다.
Average waiting time is often quite long.
평균 대기 시간은 종종 꽤 깁니다.
Particularly troublesome for time-sharing systems.
특히 시간 공유 시스템에 문제가 있습니다.
Example of FCFS Scheduling
Suppose that the processes arrive in the order: P1 , P2 , P3 The Gantt Chart for the schedule is:
Waiting time for P1 = 0; P2 = 24; P3 = 27
Average waiting time: (0 + 24 + 27) / 3 = 17
Convoy Effect
Suppose that the processes arrive in the order P2 , P3 , P1 .
The Gantt chart for the schedule is:
Waiting time for P1=6; P2=0 ;P3=3
Average waiting time: (6 + 0 + 3) / 3 = 3 <- much better !
Convoy effect (consider the CPU-I/O burst cycle)
- After a process with long CPU bursts (CPU-bound) moves to an I/O queue, all the processes with short CPU bursts (I/O-bound) execute quickly and move back to the I/O queue
-> results in lower CPU utilization.
CPU 버스트(CPU 바운드)가 긴 프로세스가 I/O 대기열로 이동하면 CPU 버스트(I/O 바운드)가 짧은 모든 프로세스가 빠르게 실행되어 다시 I/O 대기열로 이동합니다.
-> CPU 사용률이 낮아집니다.
- All the I/O processes wait in the ready queue until a CPU-bound process is done
-> results in lower device utilization.
모든 I/O 프로세스는 CPU 바운드 프로세스가 완료될 때까지 대기열에 대기합니다.
-> 장치 사용률이 낮아집니다.
Shortest-Job-First (SJF) Scheduling
Associate with each process the length of its next CPU burst.
각 프로세스와 다음 CPU 버스트의 길이를 연결합니다.
- Use these lengths to schedule the process with the shortest time.
Two schemes
- Non-preemptive
once CPU given to the process it cannot be preempted until completes its CPU burst.
프로세스에 제공된 CPU는 CPU 버스트를 완료할 때까지 우선할 수 없습니다.
- Preemptive
if a new process arrives with CPU burst length less than remaining time of current executing process, preempt. This scheme is know as the Shortest Remaining Time First (SRTF).
CPU 버스트 길이가 현재 실행 프로세스의 남은 시간보다 짧은 새 프로세스가 도착하면 다음을 수행합니다. 이 체계를 SRTF(최단 남은 시간 우선)라고 합니다.
SJF is optimal in that it gives minimum average waiting time for a given set of processes.
SJF는 주어진 공정 집합에 대한 최소 평균 대기 시간을 제공한다는 점에서 최적입니다.
- Moving a short process before a long one decreases the waiting time of the short processes more than it increases the waiting time of the long process.
- The difficulty is knowing the length of the next CPU request
-> can ask the user or estimate !
Example of Non-Preemptive SJF
Example of Preemptive SJF
Determining Next CPU Burst Length
- Can only estimate the length.
- Can be done by using the length of previous CPU bursts, using exponential averaging.
Examples of Exponential Averaging
Prediction of Next CPU Burst Length
