CSCE 313 Lecture 7

« previous | Tuesday, February 7, 2012 | next »

Scheduling

A good scheduler should maximize CPU utilization and throughput, yet minimize turnaround, waiting, and response times

turnaround time: time interval from submission of job until its completion
waiting time: the total amount of time spent in ready queue during execution
response time: the amount of time from submission of job until its first response
normalized turnaround time: ratio of turnaround time to service time (amount of time spent in processor)

FCFS: first-come-first-served; append new jobs to the end of the queue; CPU dequeues from front.; very simple, but worst-case waiting time; convoy effect: many other processes may wait for one big process to finish
SPN/SJF: shortest process next / shortest job first; minimizes waiting time (used in long-term scheduling) and maximizes average throughput
SRT: shortest remaining time
Priority Scheduling: schedule most important jobs first; Unbound blocking leads to starvation, so increase priority over time with aging
RR: round-robin; basic implementation of time-sharing; FIFO queue to store tasks; CPU context-switch after time quantum; This actually defines context switching overhead.; increases wait time for longer processes, but reduces average response time; turnaround time varies with time quantum
MLFQ: multilevel feedback queue scheduling
Multiprocessor Scheduling

Round-Robin with 3 processes:

_____________________________ |P1|P2|P3|P1|P2|P3|P1|P1|...| 0 2 2 2 2 2 2 30