Chapters 1-10Midterm ReviewAnnouncementsMidtermPotential Topics for MidtermPotential Topics for MidtermSemaphoresSemaphoresClassic Synchronization ProblemsBounded Buffer Producer/Consumer ProblemThe Readers/Writers ProblemDining Philosophers ProblemMonitors and Condition VariablesNecessary Conditions for DeadlockDeadlock PreventionDeadlock AvoidanceDeadlock AvoidanceWhat is a Process?Multiple ProcessesContext SwitchingThreadsSchedulerScheduling PoliciesSignalsStacks and Frames: Entering a FunctionStacks and Frames: Exiting a FunctionThe von Neumann ArchitectureProcessor ModesSystem Call Using the trap InstructionInterrupt-driven I/O OperationOperating System ArchitectureLinking Multiple Object Files Into an ExecutableLinker Resolves Unknown SymbolsLinker Relocates AddressesSample Types of ProblemsSample Types of ProblemsSample Types of ProblemsSample Types of ProblemsChapters 1-10Midterm ReviewCSCI 3753Operating Systems, Spring 2005Professor Rick HanAnnouncements• Solutions to HW#1 - HW #3 already online, HW #4 by 3 pm• Midterm Review slides online by tomorrow a.m.• All previous lectures online, except last Thursday's (by tonight)• Extended office hours Wednesday 5-6 pm• Normal OH: Tues & Wed 2-3 pm• Extended TA office hours Tuesday• Programming Assignment #2 due Thursday March 17, before Spring BreakProf. Rick Han, University of Colorado at BoulderMidterm• Midterm March 10• Chapter 1 Through Chapter 10 Deadlock• Excluding...• 75 minutes•In class• Closed book, I'll give you what's needed, e.g. algorithms• Calculator OK• 3-4 multipart questions (multiple sections a, b, c, d)• likely all short-answer questions• Look over first, then spend about 20 minutes for each long questionProf. Rick Han, University of Colorado at BoulderPotential Topics for Midterm• List is not all-inclusive; some topics may appear on midterm not listed here• How does ___ work? Why is it used? Under what conditions does it apply/not apply?• Work backwards• Start with the slides, then supplement with the book• Chapters 8-10 Synchronization and Deadlock• probably 2 problems• Chapters 6-7 Processes, Threads, and Scheduling• probably 1 problem• Chapters 3-5 Hardware, Device Management• probably 1 problemProf. Rick Han, University of Colorado at BoulderPotential Topics for Midterm• Synchronization– Critical sections– Race conditions– Atomic operations– Mutual exclusion– Spinlocks– disabling interrupts– TestandSet()Prof. Rick Han, University of Colorado at BoulderSemaphores• Pseudo-code for classic semaphore– its value can’t go below zero, i.e. classic semaphore is non-negativeProf. Rick Han, University of Colorado at BoulderP(S) {while(S<=0){wait or no op;}S--;}V(S) {S++;}atomic“atomic”P() is “atomic” in the sense that it tests S atomically, and if S<=0, then theprocess calling P() will relinquish control. Otherwise, the process continuesforward and decrements S atomically. See Next Slide for implementation.Semaphores• Synchronization– Binary semaphores as mutex locks– Counting semaphores– Deadlock examples with semaphoresProf. Rick Han, University of Colorado at BoulderClassic Synchronization Problems• Bounded Buffer Producer-Consumer Problem• Readers-Writers Problem– First Readers Problem• Dining Philosophers Problem• These are not just abstract problems– They are representative of several classes of synchronization problems commonly encountered when trying to synchronize access to shared resources among multiple processesProf. Rick Han, University of Colorado at BoulderBounded Buffer Producer/Consumer Problem• Pool of n buffers, each capable of holding 1 item• producer takes an empty buffer and produces a full buffer• consumer takes a full buffer and produces an empty bufferEmpty PoolProducerProducerConsumerConsumerProf. Rick Han, University of Colorado at BoulderFull PoolGraphic © Pearson textbook slidesThe Readers/Writers Problem• There are several writer processes that want to write to a shared object, e.g. a file, and also several reader processes that want to read from the same shared object• Want to synchronize accessWritersW1W2ReadersR1R2Sharedobject,e.g. fileReaders can sharewith any other readerbut not a writera writer must haveexclusive accessProf. Rick Han, University of Colorado at BoulderThe “First Readers/Writers Problem”: no reader is kept waiting unless a writeralready has seized the shared object. We will implement this in the next slides.Dining Philosophers Problem• N philosophers seated around a circular table– There is one chopstick between each philosopher– A philosopher must pick up its two nearest chopsticks in order to eat– A philosopher must pick up first one chopstick, then the second one, not both at once• Devise an algorithm for allocating these limited resources (chopsticks) among several processes (philosophers) in a manner that is– deadlock-free, and– starvation-freeP5P4P3P2P1Prof. Rick Han, University of Colorado at BoulderMonitors and Condition VariablesProf. Rick Han, University of Colorado at Boulder• Declare a monitor as follows (looks somewhat like a C++ class):monitor monitor_name {// shared local variablesfunction f1(...) {...}...function fN(...) {...}init_code(...) {...}}• A monitor ensures that only 1 process/thread at a time can be active within a monitor– simplifies programming, no need to explicitly synchronize• Implicitly, the monitor defines a mutexlocksemaphore mutex = 1;• Implicitly, the monitor also defines essentially mutual exclusion around each function– Each function’s critical code is surrounded as follows:function fj(...) {P(mutex)// critical codeV(mutex)}• The monitor’s local variables can only be accessed by local monitor functions• Each function in the monitor can only access variables declared locally within the monitor and its parametersNecessary Conditions for Deadlock• Deadlock can arise if the following 4 conditions hold simultaneously:1. Mutual exclusion• at least 1 resource is held in a non-sharable mode. Other requesting processes must wait until the resource is released2. Hold and wait• a process may hold a resource while request (and waiting for) another one3. No preemption• resources cannot be preempted and can only be released by the process holding it, after the process is finished. No OS intervention is allowed. A process cannot withdraw its request.4. Circular wait• A