Operating Systems: Three Easy Pieces Ch. 7
Low-level mechanisms of running processes
- Series of scheduling policies (disciplines)
Number of simplifying assumptions → workload
*The assumption of the chapter
- Each job runs for the same amount of time
- All jobs arrive at the same time
- All jobs only use the CPU (no I/O)
- The run-time of each job is known
- Scheduling Metrics
- turnaround time: the time at which the job completes minus the time at which the job arrived in the system
- T = completion - arrival
- It is a performance metric
- Fairness
- turnaround time: the time at which the job completes minus the time at which the job arrived in the system
- FIFO (First in, First out)
- First Come, First Served
- Simple, but convoy effect → where a number of relatively-short potential consumers of a resource get queued behind a heavyweight resource consumer
- Shortest Job First
- Optimal scheduling algorithm
- Can’t handle the short job that arrive late
- Shortest Time-to-Completion First
- Preemptive scheduler
- Called a Preemptive Shortest job First
- What about the response time?
- Preemptive scheduler
- Response time
- Time from when the job arrives in a system to the first time it is scheduled
- The methods above are not suitable for response time, so…
- Round Robin
- use time slice
- But, the cost of context switching will dominate overall performance
- Also, have the wrong time around metric
- There is a trade-off between the performance and response time
- I.O devices
- Job initiate I.O request, block waiting for I.O completion
- The scheduler schedule another job on the CPU at that time
- Allows Overlap, with the CPU being used by one process while waiting for the I.O of another process to complete
- Summary
- runs the shortest job remaining and optimizes turnaround time
- optimize response time using job slicing