Process Scheduling Flashcards
What are the goals of process scheduling?
Main goal is to Maximize CPU utilization.
Secondary Goals:
- Fairness
- Throughput
- predictability
- Low overhead
- Priorities
- Efficient utilization of other resources held by processes
- Quick response time
- graceful degradation
When does the OS have an opportunity for a context switch?
- When a process blocks for I/O (preemptive, nonpreemtive)
- When a process ends (preemptive, nonpreemptive)
- When a process switches from blocked to ready (preemptive)
- When a process’ turn on the CPU ends and it returns to the ready state (preemptive)
Assume that a process Pi arrives at time Ai, runs on the CPU for time Ti and enters the Exit queue at time Ei.
- What is the CPU utilization?
- How do we define the throughput of the CPU?
- What is the turnaround time for Pi?
- What is the normalized turnaround time for Pi?
- What is the waiting time for Pi?
- What is the response time for Pi?
- CPU utilization: (time CPU is in use) / total time
- Throughput: number of processes completed per unit of time
- Turnaround time: Ei-Ai
- Normalized turnaround time: (Ei-Ai)/Ti
- Waiting time: Ei - Ai - Ti
- Response time: time between time slices for the process
The performance of the CPU has three primary considerations - the maximum (worst-case) performance, average performance, and the variance of the performance (how much it deviates from the predicted performance). Which is considered most often, and why?
In general, we consider the average performance of the CPU. Unless the variance is large, there is no reason to consider it as a measure of performance. In addition, maximum cases are generally rare, making them comparatively uninformative.
Given the following, how do we estimate the burst time of a process?
Ti = estimated burst time ti = actual burst time a = tuning parameter.
We estimate the burst time as follows:
T(i+1) = ati + (1-a)Ti
Name four basic scheduling algorithms.
Most Important:
- First Come First Served (FCFS)
- Round Robin
- Shortest Remaining Time First (SRTF)
- Priority Queue
Other possibilities:
- Fixed Schedule
- Shortest Job First (SJF)
How does First Come First Served work?
First process in is first get CPU time
- Simplest algorithm - inherently nonpreemptive
- use a FIFO queue for ready queue
- processes run till they are completed
What are the cons of First Come First Serve (FCFS)?
- Bad for throughput, wait time, predictability, priorities,
resource use, turnaround time, degradation - can be subject to queuing theory (impacts throughput and waiting time)
- Suffers from convoy effect where small processes pile up behind large ones
What are the pros of First Come First Serve (FCFS)?
- good for fairness
- low overhead
What is Round Robin scheduling?
- Handle processes in their order of arrival into the ready
queue, but only allow a limited time on the CPU (CPU time allowed called time slice or time quantum)
Choice of time slice is the tricky part.
- Too large becomes first come first serve.
- small: with n processes each process thinks it has it’s own CPU running at 1/n the regular speed
- Tiny: spend more time doing context switches then running processes
- Ideal: each CPU burst fits into one time slice
What are some round robin variants?
- Allow each process to have time slice size based on priority
- Allow a process to appear more than once in a round robin cycle.
What are advantages to Round Robin?
- Fair
- Predictable
- low overhead
- degrades well
What are disadvantages to Round Robin?
- Doesn’t handle priorities well.
- Doesn’t balance resource usage
what is Shortest Job First (SJF)?
- Nonpreemptive schedule
- Each process knows the size of it’s CPU burst
- Give the CPU the process with the shortest “next burst”
- Provably minimizes average waiting time across all nonpreemptive schedules
- Implemented with priority queue, sorted list, or heap
Shortest Job First Advantages
Throughput, overhead, minimum wait time, minimum turnaround time.
