Lecture 8 Scheduling Deadlock CSE 120 Principles of Operating Systems Alex C Snoeren HW 2 Due NOW Scheduling The scheduler aka dispatcher is the module that manipulates the queues moving jobs to and fro The scheduling algorithm determines which jobs are chosen to run next and what queues they wait on In general the scheduler runs When a job switches states running waiting etc When an interrupt occurs When a job is created or terminated We ll discuss scheduling algorithms in two contexts A preemptive scheduler can interrupt a running job A non preemptive scheduler waits for running job to block CSE 120 Lecture 8 Scheduling and Deadlock 2 Priority Scheduling Priority Scheduling Choose next job based on priority Airline checkin for first class passengers Problem Can implement SJF priority 1 expected CPU burst Also can be either preemptive or non preemptive This is what you re implementing in Nachos in Project 1 Starvation low priority jobs can wait indefinitely Solution Age processes Increase priority as a function of waiting time Decrease priority as a function of CPU consumption CSE 120 Lecture 8 Scheduling and Deadlock 3 Combining Algorithms Scheduling algorithms can be combined Have multiple queues Use a different algorithm for each queue Move processes among queues Example Multiple level feedback queues MLFQ Multiple queues representing different job types Interactive CPU bound batch system etc Queues have priorities jobs on same queue scheduled RR Jobs can move among queues based upon execution history Feedback Switch from interactive to CPU bound behavior CSE 120 Lecture 8 Scheduling and Deadlock 4 Unix Scheduler The canonical Unix scheduler uses a MLFQ 3 4 classes spanning 170 priority levels Priority scheduling across queues RR within a queue Timesharing first 60 priorities System next 40 priorities Real time next 60 priorities Interrupt next 10 Solaris The process with the highest priority always runs Processes with the same priority are scheduled RR Processes dynamically change priority Increases over time if process blocks before end of quantum Decreases over time if process uses entire quantum CSE 120 Lecture 8 Scheduling and Deadlock 5 Motivation of Unix Scheduler The idea behind the Unix scheduler is to reward interactive processes over CPU hogs Interactive processes shell editor etc typically run using short CPU bursts Want to minimize response time They do not finish quantum before waiting for more input Time from keystroke putting process on ready queue to executing keystroke handler process running Don t want editor to wait until CPU hog finishes quantum This policy delays execution of CPU bound jobs But that s ok CSE 120 Lecture 8 Scheduling and Deadlock 6 Scheduling Summary Scheduler dispatcher is the module that gets invoked when a context switch needs to happen Scheduling algorithm determines which process runs where processes are placed on queues Many potential goals of scheduling algorithms Various algorithms to meet these goals Utilization throughput wait time response time etc FCFS FIFO SJF Priority RR Can combine algorithms Multiple level feedback queues Unix example CSE 120 Lecture 8 Scheduling and Deadlock 7 Deadlock Processes that acquire multiple resources are dependent on those resources What if one process tries to allocate a resource that a second process holds and vice versa E g locks semaphores monitors etc Neither can ever make progress Dining philosphers problem from Homework 2 We call this situation deadlock and we ll look at Definition and conditions necessary for deadlock Representation of deadlock conditions Approaches to dealing with deadlock CSE 120 Lecture 8 Scheduling and Deadlock 8 Deadlock Definition Deadlock is a problem that can arise When processes compete for access to limited resources When processes are incorrectly synchronized Definition Deadlock exists among a set of processes if every process is waiting for an event that can be caused only by another process in the set Process 1 Process 2 lockA Acquire lockB Acquire lockB Acquire lockA Acquire CSE 120 Lecture 8 Scheduling and Deadlock 9 Conditions for Deadlock Deadlock can exist if and only if four conditions hold 1 Mutual exclusion At least one resource must be held in a non sharable mode I e only one instance 2 Hold and wait There must be one process holding one resource and waiting for another resource 3 No preemption Resources cannot be preempted I e critical sections cannot be aborted externally 4 Circular wait There must exist a set of processes P1 P2 P3 Pn such that P1 is waiting for a resource held by P2 P2 is waiting for P3 and Pn for P1 CSE 120 Lecture 8 Scheduling and Deadlock 10 Resource Allocation Graph Deadlock can be described using a resource allocation graph RAG The RAG consists of sets of vertices P P1 P2 Pn of processes and R R1 R2 Rm resources A directed edge from a process to a resource Pi Ri implies that Pi has requested Rj A directed edge from a resource to a process Ri Pi implies that Rj has been acquired by Pi Each resource has a fixed number of units If the graph has no cycles deadlock cannot exist If the graph has a cycle deadlock may exist CSE 120 Lecture 8 Scheduling and Deadlock 11 RAG Example A cycle and deadlock CSE 120 Lecture 8 Scheduling and Deadlock Same cycle but no deadlock Why 12 Dealing With Deadlock There are four ways to deal with deadlock Ignore it Prevention Make it impossible for deadlock to happen Avoidance How lucky do you feel Control allocation of resources Detection and recovery Look for a cycle in dependencies CSE 120 Lecture 8 Scheduling and Deadlock 13 Deadlock Prevention Prevent at least one condition from happening Mutual exclusion Hold and wait Process cannot hold one resource when requesting another Process requests releases all needed resources at once Preemption Make resources sharable not generally practical OS can preempt resource costly Circular wait Impose an ordering numbering on the resources and request them in order popular implementation technique CSE 120 Lecture 8 Scheduling and Deadlock 14 Deadlock Avoidance Avoidance Provide information in advance about what resources will be needed by processes to guarantee that deadlock will not happen System only grants resource requests if it knows that the process can obtain all resources it needs in future requests Avoids circularities wait dependencies Tough Hard to determine all resources needed in advance Good theoretical problem not as practical to use CSE 120
View Full Document
Unlocking...