New version page

SMU CSE 7343 - Process Scheduling

Upgrade to remove ads
Upgrade to remove ads
Unformatted text preview:

CSE 5343/7343 Fall 2006PROCESS SCHEDULINGProfessor Margaret H. DunhamDepartment of Computer Science and EngineeringSouthern Methodist UniversityDallas, Texas 75275(214) 768-3087fax: (214) 768-3085email: [email protected]: http://www.seas.smu.edu/∼mhdOctober 10, 20061PROCESS SCHEDULING• Which process should get the CPU next?• Long Term– switch between new and ready states– MP level– Pick new Process (FCFS, Priority)– Create PCB (Allocate memory, read in pro-gram)– Primarily batch– Executes infrequently• Intermediate Level– Temporarily suspending and activating pro-cesses• Short Term– Which processor gets which process?– Dispatcher - Gives control of CPU to selectedprocess– Executes frequently2PREEMPTIVE/NONPREEMPTIVE SCHEDULING• Nonpreemptive– Process keeps CPU until it decides to give itup– Give up at I/O or SVC or termination (Whenit chooses)– Fair treatment– Response times more predictable– Simple• Preemptive– CPU can be taken away– High priority processes require rapid atten-tion– Overhead high3MEASURING CPU SCHEDULING PERFORMANCE• Response Time - Time to first response• Turnaround Time - Total elapsed time includingI/O• Normalized Turnaround - Turnaround dividedby run time• Throughput - Number of processes per unit time• Waiting Time - Time in ready queue• For multiples processes you need the average value• CPU Utilization4SCHEDULING CONSIDERATIONS• Availability of limited resources• Program needed resources• Priority• User specified requirements (deadline)• I/O or CPU Bound (balance resource usage)• Variance of response times• Minimize average response time• Minimize maximum response time• Maximize throughput• Avoid starvation5SCHEDULING ALGORITHMS• FCFS (nonpreemptive)• SJF (nonpreemptive)• SPN (nonpreemptive)• SRT (preemptive)• HRRN (nonpreemptive)• Priority (preemptive and nonpreemptive)• Round-Robin (preemptive)• Multilevel Queue• Multilevel Feedback Queue• Example (No I/O, Context Switch time is 0, Sup-pose quantum = 0.5 where applicable):Process Arrival Runtime1 10.00 2.02 10.10 1.03 10.25 .256TIME SLICE• Program gives up CPU at predefined service time• Avoids Convoy effect• How Choose?– Large - approaches FCFS– Small - frequent context switches (May causethrashing)– Maximum Wait Time = (N-1)*quantum– Typical values 10-100 milliseconds7FCFS (FIFO)• Simplest - Nonpreemptive• FIFO Queue - Ordered according to time processarrives• Convoy Effect• Poor response time; Large variance• Example:1011 12 1 1.25WaitingRunningPR1PR2PR3Process Turnaround Normalized Turnaround12 122.9 2.933 12Average 2.63 5.38SHORTEST JOB FIRST (SJF)• Schedule process with shortest CPU burst (total)time• Nonpreemptive• Queue ordered according to CPU burst time• Minimum average waiting time1011 12 1 1.25WaitingRunningPR1PR2PR3Process Turnaround Normalized Turnaround12 12 3.15 3.1532 8Average 2.38 4.059SHORTEST PROCESS NEXT (SPN)• Schedules based on prediction of next run time• Nonpreemptive• How do you know CPU time? (Burst time)– Programmer estimate– Historical– Similar processes– Average of past bursts• Suppose bursts are T1,T2, ..., Tn.WhatisTn+1?– Sn+1= Tn– Sn+1=ni=1Ti/n– Sn+1= αTn+(1− α)Snwhere 0 ≤ α ≤ 1∗ Exponential Smoothing∗ Older times have the least weight10SHORTEST REMAINING TIME (SRT)• Preemptive version of SJF,SPN• Schedules process with shortest burst time• Queue ordered according to burst time• Example (Burst time assumed to be time to com-pletion. Process allowed to continue if shortesttime.):1011 12 1 1.25WaitingRunningPR1PR2PR3Process Turnaround Normalized Turnaround1 3.25 1.6252 1.65 1.653.5 2Average 1.8 1.75811HIGHEST RESPONSE RATIO NEXT (HRRN)• Schedules process with largestRatio R =(w + s)/s• Nonpreemptive• Queue ordered ???• Extreme overhead12PRIORITY• Schedule process with highest priority (lowestnumber)• Priorities 0 (best) .... n(worst)• Preemptive and nonpreemptive versions• Queue ordered according to priorities of processes• Internal(system)/External(user)• Static/Dynamic• Aging - Longer process in system, higher priority.Avoids starvation.13PRIORITY EXAMPLE• Assume priorities are 1,3,2 and nonpreemption:1011 12 1 1.25WaitingRunningPR1PR2PR3Process Turnaround Normalized Turnaround12 12 3.15 3.1532 8Average 2.38 4.0514ROUND ROBIN (RR)• Preemptive version of FCFS• Queue ordered according to time process arrives• Each process allocated a time slice (quantum)• Popular in time-sharing systems• Example:1011 12 1 1.25WaitingRunningPR1PR2PR3Process Turnaround Normalized Turnaround1 3.25 1.6252 2.15 2.1531 4Average 2.133 2.59215IMPACT OF VARYING TIME SLICES• This table seems to indicate you want quantumas small as possible. Is this really true?RR(∞) RR(1) RR(.5) RR(.25)CPU Util 100 100 100 100Throughput .92 .92 .92 .92Ave Turn 2.63 2.38 2.133 1.967Ave Wait 1.55 1.3 1.05 .883Ave Norm 5.3 3.84 2.592 1.92516MULTILEVEL QUEUE• Multiple queues for scheduling• Priority among queues• Multilevel Feedback Queue– Multilevel queues– Processes move among the


View Full Document
Download Process Scheduling
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Process Scheduling and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Process Scheduling 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?