Scheduling algorithms Flashcards
FCFS
Schedule in order of arrival
Eval FCFS
- Wait time : Highly dependent on arrival times
(example - arrival in reverse order) - Convoy effect : later processes held up behind long running first process (CPU / IO bound explanation)
- Simple but not robust to different arrival distributions/ processes
SJF
- Assume length of next cpu burst known for any process
- Schedule in order of next cpu burst length
- Use FCFS to break ties
Walk through eg of SJF and eval
example - wait times, average wait time calc
- SJF is optimal wrt avg wait time
- “what might go wrong” - silherschatz
SRTF
- Preemptive version of SJF
- Preempt running process if new process arrives w CPU burst shorter than remaining time of current process.
Eval SRTF
example - calc wait, avg wait, note preemption
- Not optimal in face of new runnable processes arriving - why???
- Costly context switches - thrashing
- Future burst lengths uncertain
Predicting burst lengths
1 Necessary in both SJF and SRTF to have estimate of next cpu burst length
2 Exponential averaging of past CPU burst lengths (formula - recursion Tn+1 = atn + 1-a Tn with a between 0,1.) Interpretation of different alpha values : discount rate for discounting past burst lengths relative to most recent burst length.
Eval : predicting burst lengths
1 Choice of alpha / discount rate - history irrelevant high alpha, etc
2 Exponential averaging good predictor only if variance in cpu burst times is small
3 Consideration of load ????? s133
Round robin
- Preemptive … why
- Time sharing systems …. why
- How:
- Define time slice - fixed - 10 to 100 ms
- Process at front of ready queue given CPU for <1 time quantum
- When time elapses - preemption, appended to ready queue
Round robin - evaluate
- Fair : each process gets an equal proportion of CPU time
- Live : no process waits longer than (n-1)q time units before receiving the CPU
- Usually longer turnaround time than SRTF
- Shorter average RESPONSE time compared to SRTF
- Optimal q? Too large = FCFS, too small = thrashing (high context switch overhead)
Priority scheduling
- Associate integer priority with each process
- allocate COU to highest priority process in ready queue (may be lowest priority value)
- Can get preemptive and non preemptive variants eg SJF sets priority to be inverse of predicted next CPU burst duration
Tie breaking
- Problem: if two processes have the same priority, which gets CPU
- Possibility 1: Round robin - allocate a time slice to each process in turn.
- Problem 1: Biased towards CPU intensive jobs (why?????????????)
- Solution : per process quantum based on CPU usage
- Solution2: just ignore the problem
Starvation
Arguably the biggest problem with static priority systems,
a low priority process is not guaranteed to run - ever
Dynamic priority scheduling
- Aim: prevent starvation
- How : use same scheduling algorithm but allow priorities to change over time
- How 2:
Process has STATIC base priority, dynamic effective priority. - If the process is starved for say k seconds, increase the effective priority
- Once process runs, reset effective priority to static base priority
Example of Computed priority and eval
Dijkstra THE
- Timeslots t, t+1
- In each time slot, t, measure the CPU use of process j : u_j
- Priority for process in the next time slot is a function of the past history of priorities and CPU usage
- ???? Penalises CPU bound supports IO bound???
- Once considered impractical ( memory required to store history of priorities and CPU usage, overhead of recomputing on each time slice, and possibility that the function itself may be intensive to compute). Now considered acceptable.
