Adv Operating Systems
Adv Operating Systems CS 4210
Popular in Course
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 4210 at Georgia Institute of Technology - Main Campus taught by Ada Gavrilovska in Fall. Since its upload, it has received 11 views. For similar materials see /class/234013/cs-4210-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.
Reviews for Adv Operating Systems
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 11/02/15
Advanced Synchronization 0 Bloom paper online Chapter 6 from Silbersohatz slides have many illustrative examples Support for Critical Section Hardware support Some hardware instructions are provided to support the programmer eg testampset and swap instructions Operating System Support Operating system supports for the declaration of data structures and also operations on those data structures eg semaphores High Level Language Support Language provides support for data structures and operations on them to help with synchronization e g critical regions monitors serializers etc Synchronization Building Blocks Most synchronization on symmetric multiprocessors is based on an atomic test and set instruction in hardware we need to do a load and store atomically Example tryagain ldstub address gt register compare register 0 branchequal gotit call gotosleep jump tryagain gotit return sttub load and store unsigned byte SPARC Other kinds of atomic primitives at the hardware level may be even more powerful eg compareandswapmm reg reg2 if mmregl mmreg2 Limits on lowlevel mechanism no abstraction and modularity ie a process that uses a semaphore has to know which other processes use the semaphore and how these processes use the semaphore a process cannot be written in isolation errorprone change order or omit lockunlock signalwait dif cult to verify correctness Higherlevel constructs Language Support monitors serlializers path eXperssions conditional critical regions RWlocks mainly programming languages targeted for concurrent programming and object oriented languages Concurrent Pascal Path Pascal Concurrent C Java Modula Ada Mesa Eiffel use constructs provided by language and trust compiler to translate them data structures need to be created for queues counts locks etc lockunlock and signalwait primitives will be invoked on the right muteXsemaphorecondition variables at the lowest level these will most likely translate to testampset atomic instructions or OSsupported semaphores Requirements of Synch Mech modularity separation of resource and its access operations and synchronizer and its mechanisms expressive power specifying the needed constraints exclusion and priority constrains in terms of relevant information ease of use composing a set of constraints for complex synch schemes modifiability changing the constraints if needed correctness safety net against inadvertent user errors Basic Mechanisms muteX lock condition variables semaphores Proposed in 1969 by Dijkstra for process synchronization Cooperating Sequential Processes PS While S lt 0 do nothing busy wait S S 1 VS S S 1 InitSemS Count S Count enables mutual exclusion process synch Semaphore concept Integer variable with initial nonnegative value Two atomic operations wait signal not the UNIX signalO call p amp V proberen amp verhogen up and down etc wait wait for semaphore to become positive then decrement by 1 signal increment semaphore by 1 Semaphore Without busywait struct sem value int L list of processes S InitSemS Count SVa1ue Count OS support block wakeup P and V atomic PS SVa1ue SVa1ue 1 if SVa1ue lt O add T to SL block VS SVa1ue SVa1ue 1 if SVa1ue lt0 select a T from SL wakeupT Mutual exclusion using semaphores Use wait and signal like lock and unlock bracket critical sections in the same manner Semaphore value should never be greater than 1 This is a binary semaphore Depends on correct order of calls by programmer All muteX problems apply deadlock What should the initial value be Resource counting A counting semaphore can take on arbitrary positive values maX value usually system dependent but tunable General idea initialize semaphore value to of resources wait acquire resource signal relinquish resource when all resources are taken wait will well wait Default semaphore type is usually counting easy to make it a muteX Monitors Monitors are a synchronization mechanism Where the shared data are encapsulated with the locks required to access them Variablesdata local to a monitor cannot be directly accessed om outside the data can only be accessed through the locked code monname epl ep2 epn entry point epl entry point ep2 all ep s are mutually exclusive multiple threads inside the monitor yes but only one active others waiting on an event Monitors Silberschatz textbook 67 example of Monitor implementation with semaphores structure for each condition X actions for XWait and Xsignal Process a Process b Condition ariablewa1t gt Queue for each conditional variable Only one process at a given time Variable 39 Designing a Monitor When a process is active inside a monitor other processes get queued up Queuing up done by operation wait Dequeuing by signal Queuingdequeuing up more than 1 reason possible Eg waiting for a reader to depart waiting for a writer to finish Condition variable may be associated with wait and signal Eg OKtoreadwait OKtoreadsignal Queues generally FIFO priorities may be implemented with a parameter signaling threads immediately relinquish control of the monitor in original de nition this means they cannot signal multiple condition variables at the same time Monitorstyle programming With mutexes and condition variables you can implement any critical section CSenter controlled code CSeXitO void CSenter void CSeXitO Lockm Lockm While condition change shared data Waitc m to re ect outofCS change shared data broadcast signal as needed to re ect inCS broadcast signal as needed ReadersWriter example structure monitor Condition OKtoread OKtowrite int readercount data decls void StartRead void StartWrite void FinishRead void FinishWrite Reader s Priority Monitors readers writers monitor begin the monitor readercount integer busy boolean OKtoread OKtowrite condition procedure StartRead begin if busy then OKtoreadwait readercount readercount l OKtoreadsignal all readers can start end StartRead procedure EndRead begin readercount readercount 1 if readercount 0 then OKtowritesignal end EndRead Reader s Priority Monitors procedure StartWrite begin if busy OR readcount 0 then OKtowritewait busy true end StartWrite procedure EndWrite begin busy false if OKtoreadqueue then OKtoreadsignal else OKtowritesignal end EndWrite begin initialization readercount O busy false end end readers writers ReadersWriters Monitors Reader StartRead ReadFile EndRead Writer StartWrite WriteFile EndWrite Monitors Drawbacks Only one active process inside a monitor no concurrency Previous example File NOT inside monitor to allow concurrency gt Responsibility of readers and writers to ensure proper synchronization Nested monitor calls can lead to deadlocks Consider monitors X and Y with procedures A and B Let XA call YB and viceversa A process P calls XA process Q calls YB P is blocked on YB and Q is blocked on XA Responsibility of valid programs shifts to programmers dif cult to validate correctness lowlevel explicit signalling needed no connection between abstract condition and signalling signaller has to choose which queue to signal explicit priorities USC embed resource in mon e g access to bbuffer problem all ops mutually exclusive resource outside mon permission to access inside mon does not prevent resource being called directly monitors vs semaphores exercise implement one using the other scorecard for monitor modularity and correctness low ease of use modi ability eXpr power OK Monitors in Java keyword synchronized can be used to identify monitor regions statements methods etc compiler generates monitorenter and monitoreXit bytecodes when monitor region is statements within a method JVM acquires and releases lock to corresponding object or class locks are recursive single condition variable associated with object that has monitor notifyO semantic is SignalandContinue ie have to verify that indeed the condition is true Example pseudocode import Utilities import Synchronization class BoundedBuffer extends MyObject private int size 0 private double buf null private int front 0 rear 0 count 0 public BoundedBufferint size thissize size buf new doublesize public synchronized void depositdouble data if count size wait bufrear data rear rearl size count if count notify public synchronized double fetch double result if count wait result buffront front frontl size count if count size l notify return result ProducerConcumer Bounded Buffer with Monitor Monitor PBBuffer b BBuffer This is an unprotected bounded buffer count Integer empty full condition procedure Init begin initempty initfull initb count 0 end procedure EnqueueI Item begin if count BufferSizeb then waitfull BufferSize returns the maximum size of b count Enqueueb I signalempty end procedure DequeueI out Item begin if count 0 then waitempty count Dequeueb I signalfull end Dining Philosophers Problem this solution is not fair Monitor DiningPhilosophers HMNY constant integer the number of philosophers HMNYl constant integer HMNY 1 state arrayO HMNYl of thinking hungry eating thinking thinking self arrayO HMNY of condition We assume self39s conditions are initialized function LeftK O HMNYl return 0 HMNYl is This is an operation only used within the monitor begin return Kl mod HMNY end function RightK O HMNYl return 0 HMNYl is This is an operation only used within the monitor begin return K l mod HMNY end procedure TestK O HMNYl This is an operation only used within the monitor begin if stateLeftK eating and stateK hungry and stateRightK eating then stateK eating signalselfK end procedure PickupI O HMNYl begin stateI hungry TestI if stateI eating then waitselfI end procedure PutDownI O HMNYl begin stateI thinking TestLeftI TestRightI end Each philosopher Pi will execute a simple loop loop think DiningPhilosophersPiCkUpi eat DiningPhilosophersPutDowni forever Semaphore with Monitor MONITOR monSemaphore PROCEDURE monv VAR BEGIN semvalue INTEGER IF EMPTYnotbusy THEN notbusy CONDITION semvalue semvalue 1 PROCEDURE monP ELSE BEGIN SIGNALCnotbusy IF semvalue 0 THEN END WAITCnotbusy BEGIN initialization code ELSE semvalue 1 semvalue I SGmValue 39 1 END of monSemaphore END monitor Serializers Serializers was a mechanism proposed in 1979 to overcome some of the monitors shortcomings more automatic highlevel mechanism basic structure is similar to monitors Data types queue takes place of CVs but there is no signal op the wait is replaced by enqueue crowd operations enqueue queuename until ltpredicategt join crowdname then ltstmtsgt implicitly relinquishes control of serializer emptycrowdname or queuename resource access CI S enqueue ltpri0ritygtltqnamegt until ltc0nditi0ngt joincrowd ltcr0wdgt then ltb0dygt end Multiple active processes Only 1 active process serializer vs monitor difference from monitor resource ops can be inside the serializer no explicit signaling explicit enqueuing on queues automatic thread resumption dequeue Serializers are similar to monitors with two main differences they allow concurrency they have an automatic signalling mechanism A serializer allows access to a resource without mutual exclusion although the resource is inside the serializer built in priorities threads on queue when condition true threads leaving crowd threads entering crowd Operation semantics enqueue is like Wait only the Signal happens automatically when condition is true the thread is at the head of the queue and some other thread leaves the serializer joincrowd leaves the serializer executes a block without mutual exclusion but returns to the serializer when the block nishes Use of Serializers Usual sequence of events for a thread enter serializer enqueue waiting for event if needed dequeue automatic join crowd to start using resource leave crowd automatic eXit serializer Reader s Priority Serializers Readerwriter serializer var readq queue writeq queue rcrowd crowd wcrowd crowd db database procedure readkkey var data datatype begin enqueue readq until emptywcrowd joincrowd rcrowd then data read dbdbkey end return data end read procedure writekkey datadatatype begin enqueuewriteq until emptyrcrowd AND emptywcrowd AND emptyreadq joincrowd wcrowd then write dbdbkey data end end write ReadersWriters in Serializers Weak reader s priority enqueuewriteq until emptywcrowd AND emptyrcrowd A writer does not wait until readq becomes empty Writer s priority enqueuewriteq until emptywcrowd AND emptyrcrowd enqueuereadq until emptywcrowd AND emptywriteq Serializers Drawbacks More complex may be less ef cient More work to be done by serializers crowd complex data structure stores identity of processes queue count semaphore predicate Assumes automatic signaling feature test conditions of every process at the head of every queue every time a process comes out of a serializer Though it automatic signalling helps in avoiding deadlocks and race conditions Serializers pros and cons FWos clean and powerful model addresses monitors drawbacks allows concurrency of encapsulated resources automatic signaling simplifies programming Cons more complex so less efficient automatic signaling requires testing conditions every time possession of serializer is relinquished scorecard for serializer modularity and correctness high ease of use high modi ability OK expr power OK ef ciency low Path Expressions Path expressions are declarative speci cations of allowed behaviors of a concurrent program synchronization is a mere sideeffect of ordering the executions of operations on a resource To implement path expressions a runtime system path controller for each instance of shared resource is needed to check the validity of orderings it keeps track of operation start and end it blocks threads if their execution of an operation Will violate the path expression important automatically unblocks when execution can go on Path expressions do not cause the operations to be executed and do not determine who executes the operations Path Expressions sync for data abstraction part of de nition path expression speci es allowed orderings syntax path 8 end S is an expression whose variables are the operations on the resource and the operators are sequencing selection concurrency pathend repetition unsynch access to ops not in path Operator semantic sequencing defines a obliged sequencing order between operations no concurrency between operations selection means only one of the operations can be executed at a time the order of executions does not matter concurrency means any number of instances of the embraced operations can be executing at a time example path read write end multiple readers or single writer priority 39 HOHG path expression does not cause op invocation several path expressions in a module the ordering has to be consistent with all paths after a legal execution another legal execution may follow path open read close end sequentially one after the other no mention of WHO executes the op in path expr path A end a sequence of As the path between path and end can be repeated path A end concurrent As path ABC end the nth B can start only after n As have nished any C will be preceded by zero or n concurrent AB Where all As and Bs have nished path A BC end the nth B can start independent of how many As have started or nished before it all the As and Bs that have started have to complete before a C is allowed to go ReadersWriter basic path read write end Writes and reads interleaved at least 1 read path write read end path a b 0 end path a b 0 end path a b end path a b end path a b end path ab 0 end path a bc end Usage Each path expression is associated with a single resource Path expressions are used encapsulated with the operations for a resource class file path write read end void write int read Path Expressions in Path Pascal Path Pascal extension of Pascal that includes directives for specifying Path Expressions and uses Object Encapsulations and Processes to specify priorities may need to introduce arti cial operations in Bloom s paper not just readwrite but 33 CC start readwrite readwrite Readers priority weak path read write end e herseveralreadsH axyr e Writer s priority path write end path startread startwrite write end path startread read write end 3rd expression no reader can execute startread when a writer is writing 211d expression a writer can start a write when a writer is writing or when a reader is reading startread cannot be concurrent with startwrite however read can 1St expression only one reader at a time A CS for up to 2 concurrent threads path requestenter exit doenter end means these are mutually exclusive path enter end means that instances are exclusive path wait release doenter doenter end count 0 private wait release requestenter if count gt 2 wait doenter count public enter requestenter doenter exit count release ProducerConsumer Problem CONST nbuf 5 TYPE bufrange l5 ring OBJECT PATH nbuf1put lget END VAR buffer ARRAY bufrange OF CHAR inp outp bufrange ENTRY PROCEDURE put X CHAR BEGIN inp imp MOD nbuf l bufferinp x END ENTRY FUNCTION get CHAR BEGIN outp outp MOD nbuf 1 get bufferoutp END INIT BEGIN inp nbuf outp nbuf END END end of OBJECT VAR buf ring C CHAR BEGIN bufput39a39 c bufget END Dining philosopher Problem CONST nphilopophers 5 maxindex 4 nphilopophers 1 TYPE diner Omaxindex VAR i integer table OBJECT PATH maxindexstarteating stopeating END VAR fork ARRAY diner OF OBJECT PATH 1pickup putdown END ENTRY PROCEDURE pickup BEGIN END ENTRY PROCEDURE putdown BEGIN END END ENTRY PROCEDURE starteatingno diner BEGIN forknopickup forknol MOD nphilsopherspickup END ENTRY PROCEDURE stopeatingno diner BEGIN forknoputdown forknol MOD nphilsophersputdown END END table PROCESS philsopher mynum diner BEGIN REPEAT delayrandseed tablestarteatingmynum delayrandseed tablestopeatingmynum UNTIL FALSE END main BEGIN FOR i TO maxindex DO philsopheri END Comments on Path Expressions Path expressions can be complex they may require the addition of arti cial operations it is not clear that a speci cation is correct when it spans several different resources each with its own path expressions and operations depending on each other But the speci cations are declarative and centralized ie there is no need to look through the code to nd the synchronization primitives For synchronization on a single resource path expressions may be ne scorecard expressive power modularity high priority constraints low correctness depends ReaderWriter Locks Abstraction in Java MS NET other places Manages read and write locks so you don t have to Also handles scheduling of blocked threads Java implements WriterPreference ReaderPreference classes which implement ReadWriteLock interface RWLocks Bracket critical sections as with normal mutexes You say whether you re locking for read or write it does the right thing Downgradeupgrade reduce overhead when switching from read to write priority over those with no locks when upgrading Very useful for caches or anywhere readers gtgt writers Java Swing GUI threads etc For small critical sections it may be overkill need larger CS to get benefit of concurrent readers Conditional Critical Regions Silverschatz textbook 66 and implementation with semaphores var v shared t region v when Condition do Statements the developer does not have to program the semaphore or alternate synchronization explicitly the compiler automatically plugs in the synchronization code using prede ned libraries once done carefully reduces likelihood of mistakes in designing the delicate synchronization code Synchronization support for concurrency problems using programming languages monitors shared memory support Concurrent Pascal Hansen Modula Wirth Mesa Xerox uC Buhr Emerald Raj path expressions shared memory support Path Pascal Habermann and Campbell message passing nonshared memory support CSP Communicating Sequential Processes Hoare serializers Eifel RPCrendezvous nonshared memory support Ada for rendezvous Deadlocks Silberschatz Ch 7 also Priority Inversion Problems The Deadlock Problem A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set Example System has 2 disk drives P1 and P2 each hold one disk drive and each needs another one Example semaphores A and B initialized to 1 P0 P1 wait A waitB wait B waitA Deadlock Characterization Deadlock can arise if four conditions hold simultaneously Mutual exclusion only one process at a time can use a resource Hold and wait a process holding at least one resource is waiting to acquire additional resources held by other processes No preemption a resource can be released only voluntarily by the process holding it after that process has completed its task Circular wait there exists a set P0 P1 P0 of waiting processes such that PO is waiting for a resource that is held by P1 P1 is waiting for a resource that is held by P Pn1 is waiting for a resource that is held by P and PO is waiting for a resource that is held by P0 Example of a Resource Allocation Graph Resource Allocation Graph With A Deadlock Graph With A Cycle But No Deadlock Basic Facts If graph contains no cycles gt no deadlock If graph contains a cycle gt if only one instance per resource type then deadlock if several instances per resource type possibility of deadlock Methods for Handling Deadlocks Ensure that the system will never enter a deadlock state Allow the system to enter a deadlock state and then recover Ignore the problem and pretend that deadlocks never occur in the system used by most operating systems including UNIX the Ostrich Algorithm Deadlock Prevention Restrain the ways request can be made Mutual Exclusion not required for sharable resources must hold for nonsharable resources Hold and Wait must guarantee that whenever a process requests a resource it does not hold any other resources Require process to request and be allocated all its resources before it begins execution or allow process to request resources only when the process has none Low resource utilization starvation possible Deadlock Prevention Cont No Preemption If a process that is holding some resources requests another resource that cannot be immediately allocated to it then all resources currently being held are released Preempted resources are added to the list of resources for which the process is waiting Process will be restarted only when it can regain its old resources as well as the new ones that it is reques ng how do you preempt a robot movement Circular Wait impose a total ordering of all resource types and require that each process requests resources in an increasing order of enumeration Deadlock Avoidance Requires that the system has some additional a priori information available Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need The deadlockavoidance algorithm dynamically examines the resourceallocation state to ensure that there can never be a circularwait condition Resourceallocation state is defined by the number of available and allocated resources and the maximum demands of the processes ResourceAllocation Graph single resource instance version of Bankers Algorithm Dijkstra multiinstance version similar objective keep system in safe state 5 1 Unsafe State In Resource Allocation Graph F32 Deadlock Detection Allow system to enter deadlock state Detection algorithm Recovery scheme DetectionAlgorithm Usage When and how often to invoke depends on How often a deadlock is likely to occur How many processes will need to be rolled back one for each disjoint cycle If detection algorithm is invoked arbitrarily there may be many cycles in the resource graph and so we would not be able to tell which of the many deadlocked processes caused the deadlock Recovery from Deadlock Process Termination Abort all deadlocked processes Abort one process at a time until the deadlock cycle is eliminated In which order should we choose to abort Priority of the process How long process has computed and how much longer to completion Resources the process has used Resources process needs to complete How many processes will need to be terminated ls process interactive or batch Recovery from Deadlock Resource Preemption Selecting a victim minimize cost again considerfactors Rollback return to some safe state restart process for that state need logging facilitymechanism Starvation same process may always be picked as victim include number of rollback in cost factor Priority Inversion Locking can have complex interactions with pnon es Example low priority thread A locks mutex M medium priority thread B runs for long high priority thread C waits on M Problem B will complete before C will ever get to run because B has priority over A and C waits on a resource that A has even worse C may have a time deadline to complete deadline may expire and C may determine system problem deadlock etc and restart What really happened on Mars Pathfinder contained an quotinformation busquot which you can think of as a shared memory area used for passing information between different components of the spacecraft A bus management task ran frequently with high priority to move certain kinds of data in and out of the information bus Access to the bus was synchronized with mutual exclusion ocks mutexes The meteorological data gathering task ran as an infrequent low priority thread and used the information bus to publish its data When publishing its data it would acquire a mutex do writes to the bus and release the mutex If an interrupt caused the information bus thread to be scheduled while this mutex was held and if the information bus thread then attempted to acquire this same mutex in order to retrieve published data this would cause it to block on the mutex waiting until the meteorological thread released the mutex before it could continue The spacecraft also contained a communications task that ran with medium priority Most of the time this combination worked fine However very infrequently it was possible for an interrupt to occur that caused the medium priority communications task to be scheduled during the short interval while the high priority information bus thread was blocked waiting for the low priority meteorological data thread In this case the longrunning communications task having higher priority than the meteorological task would prevent it from running consequently preventing the blocked information bus task from running After some time had passed a watchdog timer would go off notice that the data bus task had not been executed for some time conclude that something had gone drastically wrong and initiate a total system reset A Distributed Object Model for the Java System Ann Wolrath Roger Riggs and Jim Waldo Communication mechanism are key in distributed systems need a good model sockets can be complicated to encodedecode messages RCP procedure calls but in Java method invocations on objects CORBA assumes heterogeneous platforms so uses IDLs to generate language neutral objects that don t match Java object model but in Java already have homogeneous JVM Java model Remote Method Invocation on remote objects for Java and JVM Goal Language integration Enable distributed computing and communication but maintain language speci c Java obiect semantics as much as possible similar interfaces as if object local preserve some behavior keep it simple eXpose exceptions related to distributed interaction Goal System Integration Use safety runtime class loading security garbage collection already provided by JVM Support different invocation semantics unicast multicast like with Subcontracts in Spring Support different reference semantics persistent nonpersistent references to remote objects Multiple transports for pair of endpoints UDP TCP like in Network Objects Language Integration Distributed Object Model Java Object model Object Interface declare a set of methods for Java object Without implementation Method Invocation primitive type passed by value object passed by reference Distributed Object model Remote object object Whose methods can be accessed from another address space Remote interface an interface that declares the methods of a remote object throws Remote Exception to deal With different failure models Remote Implementation export object implementation to RMI runtime Remote Server RMI nonremote object passed by value remote object passed by reference RMI Interfaces and Classes Interfaces Classes Remote ect on RemoteException Client stub UnicastRemoteObject extension implementation RMI details Remote reference type client stubs have same remote interface as the remote object therefore Java treats them as objects with same type Remote method invocation same syntax but exceptions have to be caught exception tells only that something happened More details Some semantics have to change client has a reference to remote object methods of class Object equal hashCode don t involve a remote call so can operate on reference some methods don t make sense e g cannot use waitnotify for syncronization Registry for locating objects System Architecture Stubs I Skeleton RMI System Remote Reference layer Transport Stub Skeleton layer client proxy and server dispatcher Remote reference layer invocation and reference semantics Transport layer actual connection setup and management Pickling Used for object transmission across address spaces Stubsskelethons marshaldemarshal pickled streams When marshalling remote object marshal stream embeds URL info of the stub code On demarshalling marshal stream loads stub code if it s not available locally