Mutual Exclusion and Synchronization s Principles of concurrency Mutual Exclusion: Software approaches and hardware Support. ☆ Semaphores、 Monitors、 Message passing Tradition question: Producer/Consumer, Readers/Writers Problem PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Mutual Exclusion and Synchronization ❖ Principles of concurrency. ❖ Mutual Exclusion: Software approaches and Hardware Support. ❖ Semaphores、Monitors、Message Passing. ❖ Tradition question: Producer/Consumer、Readers/Writers Problem
Difficulties Arise in Concurrency s Types: interleaving and overlapping The sharing of global resources is fraught with e It is difficult for the os to manage the allocation of resources optimally It is difficult to locate a programming error because results are typically not reproducible. PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Difficulties Arise in Concurrency ❖Types: interleaving and overlapping. ❖The sharing of global resources is fraught with peril. ❖It is difficult for the OS to manage the allocation of resources optimally. ❖It is difficult to locate a programming error, because results are typically not reproducible
Sharing can lead to problems Process p1 Process P2 input (in, keyboard) input(in, keyboard) out:=in out: =in output (out, display output (out, display) So, it is necessary to protect shared global variables PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Sharing can lead to problems Process P1 . input (in, keyboard) . out:=in output (out, display) . . Process P2 . input (in, keyboard) . out:=in output (out, display) . . So, it is necessary to protect shared global variables
Problems of concurrent Resource competition: How to allocate the resource and how to mutual exclusion access the critical resources 令 Execution sequence .o Communication cooperation PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Problems of Concurrent ❖ Resource competition: How to allocate the resource, and how to mutual exclusion access the critical resources. ❖ Execution sequence. ❖ Communication cooperation
Process Interaction(tables1) Processes unaware of each other: os needs to be concerned about competition for resources. Exp. Two independent applications may both want access to the same disk or file or printer s Processes indirectly aware of each other(e.g, shared object): The processes share access to some object such as wo buffer Processes directly aware of each other: Communicate with each other by name. PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Process Interaction (table5.1) ❖ Processes unaware of each other: OS needs to be concerned about competition for resources. Exp. Two independent applications may both want access to the same disk or file or printer. ❖ Processes indirectly aware of each other(e.g., shared object): The processes share access to some object such as I/O buffer. ❖ Processes directly aware of each other: Communicate with each other by name
小 Mutual Exclusion(P193) B Critical resource: Only one process can access it at a time Critical section: the portion of the program that uses critical resource entry section critical secion exit section PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Mutual Exclusion(P193) ❖ Critical resource: Only one process can access it at a time. ❖ Critical section：the portion of the program that uses critical resource. entry section critical section exit section
P194,fig5.1 Program mutualexclusion Begin(main progra Const n-.; * num of processes) parbegin Procedure P(i: integer) Begin p2; repea enter critical(r) png aren : pa End exit critical(R orever End PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING P194，fig5.1 Program mutualexclusion Const n-…; (*num of processes) Procedure P(i:integer) Begin repeat enter critical(R) ; exit critical(R) forever End; Begin(*main program*) parbegin p1; p2; … pn; parend End
Deadlock and Starvation(P194) Deadlock Exp. Two processes Pl, P2, both request to resource riv R2. At a time: PI gets R2 and p2 gets rl, in the meantime pl requests RI and p2 requests r2 s Then pi and p2 wait for each other forever -deadlock. ☆ Starvation Pl always communication with P2, p3 is starved PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Deadlock and Starvation(P194) ❖ Deadlock ٭ Exp. Two processes P1、P2, both request to resource R1、 R2. At a time: ٭ P1 gets R2 and P2 gets R1, in the meantime P1 requests R1 and P2 requests R2 ٭ Then P1 and P2 wait for each other forever ---deadlock. ❖ Starvation ٭ P1 always communication with P2, p3 is starved
Cooperation among Processes by Sharing(p195) ☆ Data integrity s Reading and writing, and only writing operations must be exclusive Data coherence: a=b no longer holds P1:a:=a+1 a:=a+1 b:=b+1 b:=2b P2:b:=2*b b:=b+1 a:=2a a:=2*a PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Cooperation among Processes by Sharing(p195) ❖ Data integrity ٭ Reading and writing, and only writing operations must be exclusive. ❖ Data coherence: a=b no longer holds P1: a:=a+1 b:=b+1 P2: b:=2*b a:=2*a a:=a+1 b:=2*b b:=b+1 a:=2*a
Cooperation among Processes by Communication Synchronize: The processes send and receive data between each other coordinately. PROCESSES AND SCHEDULING
PROCESSES AND SCHEDULING Cooperation among Processes by Communication ❖ Synchronize: The processes send and receive data between each other coordinately