Recap 1 Threads multiple threads of execution in a single process implementation uses difficulties IPC race conditions Critical Regions 3 4 2002 No two processes in their critical regions at once No assumptions about speed or number of processors No process outside its critical region can block another No process waits forever to enter its critical region Moran OS Lecture 4 1 Recap 2 Strict Alteration Peterson s Solution Test and Set 3 4 2002 Moran OS Lecture 4 2 Semaphores 1 assume we have two operations P and V such that P semaphore critical section V semaphore non critical section satisfies the constraints we set out before A binary semaphore abstracts the TAS or test and set constraint we had before 3 4 2002 Moran OS Lecture 4 3 Semaphores 2 A binary semaphore has two states assume we will call them open and closed then if we can make the following atomic we win P semaphore while semaphore CLOSED semaphore CLOSED V semaphore semaphore OPEN 3 4 2002 Moran OS Lecture 4 4 Semaphores 3 For any number of processes this solution works Most modern operating systems provide a semaphore abstraction The typical way of implementing binary semaphores is with a queue when you do a P if the semaphore is held by another process you are put on a queue Each V operation simply wakes the first process on the queue up if there is one 3 4 2002 Moran OS Lecture 4 5 Semaphores 4 We can extend binary semaphores to what are called counting semaphores Counting semaphores take on non negative integer values P semaphore while semaphore 0 semaphore V semaphore semaphore The body of P is atomic Counting semaphores turn out to be surprisingly useful 3 4 2002 Moran OS Lecture 4 6 Producer Consumer 1 Also called Bounded Buffer Two kinds of processes Producers put things in a buffer Consumers remove things from buffer Producers must be aware of a full buffer condition Consumers must be aware of the case when there is nothing in the buffer empty buffer condition 3 4 2002 Moran OS Lecture 4 7 Producer Consumer 2 Assume we can have at most MAX items in the buffer sem1 MAX counting semaphore sem2 0 counting semaphore sem3 OPEN binary semaphore Producer Consumer while TRUE P sem1 P sem3 add item V sem3 V sem2 while TRUE P sem2 P sem3 remove item V sem3 V sem1 The P sem1 V sem2 gives us bounded alteration of processes Note if MAX 1 we have strict alteration 3 4 2002 Moran OS Lecture 4 8 Dining Philosophers Dijkstra proposed this classic problem 5 philosophers are sitting at a round table they have plates of spaghetti in front of them There are 5 forks on the table one between each plate A philosopher needs two forks in order to eat Each philosopher sits thinking for a while gets hungry and tries to eat Obvious solution is to pickup the right fork and then pickup the left fork results in deadlock Solution that uses a big lock around everything serializes things bad The code in the book is worth looking at 3 4 2002 Moran OS Lecture 4 9 Readers and Writers 1 Two kinds of processes Readers Writers We allow multiple readers at one time We do not allow multiple writers at one time We do not allow writers and readers at the same time This is a common problem in databases 3 4 2002 Moran OS Lecture 4 10 Readers and Writers 2 Reader Writer P lock1 readct if readct 1 P dblock V lock1 read db read the db P lock1 readct if readct 0 V dblock V lock1 P dblock write db V dblock 3 4 2002 Moran OS Lecture 4 11 Readers and Writers 3 This solution allows multiple readers but we have the risk that the writer will never get to run One solution is to add locks such that once there is a writer waiting no more readers are allowed in until the writer has written These sorts of tricks are surprisingly hard to get right dead locks and race conditions abound 3 4 2002 Moran OS Lecture 4 12 Scheduling 1 Scheduling the processor or scheduling which job should run next Schedulers should try to meet the following objectives Fairness each process gets a fair amount of the processor Efficiency maximize the amount of usage the CPU gets Response Time minimize the response times for interactive users Turnaround minimize time it takes to finish processes Throughput maximize the number of processes run per unit time Degrade gracefully and predictably under high load conditions in other words we need to be able to predict how much hardware we need interestingly enough Linux is much worse than NT for predictability under high load conditions Repeatable Doesn t allow cheating These are not all achievable at the same time 3 4 2002 Moran OS Lecture 4 13 Scheduling 2 Preemptive scheduling is when the processor can interrupt one process to schedule another Non preemptive scheduling is what it sounds like Scheduling algorithms we will talk about 3 4 2002 FCFS Round Robin Round Robin with penalties Processor Sharing Shortest Job First Preemptive Shortest Job First Priority Scheduling Priority with multiple queues Other multi queue schemes Various Real Time scheduling algorithms Moran OS Lecture 4 14 FCFS First Come First Served Also called FIFO first in first out Keep a queue of processes run the one on the queue until it is done and then run the next one Non preemptive The simplest scheduling policy early systems used this 3 4 2002 Moran OS Lecture 4 15 Round Robin Preemptive scheduling policy Important question is how long each process gets to run for this is called the quantum q How it works a running process gets q time units to run when the timer goes off the process gets preempted the process gets moved to the ready queue the next process in the ready queue gets to run as q gets large the Round Robin looks like FCFS as q gets very small we get processor sharing There are many issues involved in choosing how big or small to make q small q makes the system responsive but wastes resources large q makes the system more efficient but less responsive 3 4 2002 Moran OS Lecture 4 16 Round Robin with Penalties Like Round Robin but we can reduce the quantum q of a process for various reasons including using all of its CPU time consistently We can also increase the number of occurrences of a process in the list this would give the process multiple chances to run i e increase the amount of CPU it got 3 4 2002 Moran OS Lecture 4 17 Processor Sharing Each of N processes thinks it has all of a machine 1 N as fast as the actual machine Actually implemented by the CDC 6600 Imagine RR scheduling with a very short time quantum 3 4 2002 Moran OS Lecture 4 18 Shortest Job