Chapter 5 Mutual Exclusion and Synchronization 5.1 Principles of Concurrency ·5.2 Mutua|EXc| usion .5. 3 Semaphores ·54 Monitors 5.5 Message Passing 5.6 Readers /writers problem .5. Summary
2 Chapter 5 Mutual Exclusion and Synchronization • 5.1 Principles of Concurrency • 5.2 Mutual Exclusion • 5.3 Semaphores • 5.4 Monitors • 5.5 Message Passing • 5.6 Readers/Writers Problem • 5.7 Summary
5.3 Semaphores .5.3 1 What is semaphore? 5.3.2 Two Uses of semaphores 5.3.3 Producer/consumer problem 5.3.4 Implement of Semaphores 5.3.5 Semaphore in UNIX
3 5.3 Semaphores • 5.3.1 What is semaphore? • 5.3.2 Two Uses of Semaphores • 5.3.3 Producer/Consumer Problem • 5.3.4 Implement of Semaphores 5.3.5 Semaphore in UNIX
5.3. 1 What is semaphore?(1/ 10) Mutual exclusion d2> ECg / Sif DrDo=S. if arDe >o √
5.3.1 What is semaphore?(1/10) • Mutual exclusion 4
5.3. 1 What is semaphore?(2/ 10) Synchronization a facility that enforces mutual exclusion and event ordering(必须按规定的先后顺序) Common synchronization mechanism Semaphore, Binary semaphore, Mutex, Condition variable, Monitor, Event flags, Messages Asynchronization??
5.3.1 What is semaphore?(2/10) • Synchronization • A facility that enforces mutual exclusion and event ordering(必须按规定的先后顺序). • Common synchronization mechanism: • Semaphore, Binary semaphore, Mutex, Condition variable, Monitor, Event flags, Messages • Asynchronization?? 5
5.3. 1 What is semaphore? (3/10) ⑨8:12 57,500 e●巴V °四图 52,500 /阕图 6,625 常185000 XP750
5.3.1 What is semaphore?(3/10) 6
5.3.1 What is semaphore? (4/10) Semaphore is a ty pe of generalized lock Defined by dijkstra in the last 60s Main synchronization primitives used in UNIX
5.3.1 What is semaphore?(4/10) • Semaphore is a type of generalized lock • Defined by Dijkstra in the last 60s • Main synchronization primitives used in UNIX 7
5.3.1 What is semaphore? (5/10) Semaphores have a non-negative integer value, and support two operations PO: an atomic operation that waits for semaphore to become positive, then decrement it by 1 VO: an atomic operation that increments semaphore by 1 and wakes up a waiting thread at Po, if any · Features: Only operations are PO and vo Cannot read or write semaphore values Except at the initialization times Operations are atomic A sleeping thread at po cannot miss a wakeup from Vo
5.3.1 What is semaphore?(5/10) • Semaphores have a non-negative integer value, and support two operations • P(): an atomic operation that waits for semaphore to become positive, then decrement it by 1 • V(): an atomic operation that increments semaphore by 1 and wakes up a waiting thread at P(), if any. • Features: • Only operations are P() and V() • Cannot read or write semaphore values • Except at the initialization times • Operations are atomic • A sleeping thread at P() cannot miss a wakeup from V() 8
5.3.1 What is semaphore? (6/10 Semaphore Primitives(原语,原子操作) struct semaphore t int count: crueueType queue void semWait(semaphore s) s. count if(s count 0) place this process in s queue b⊥ ck this process void semsigmal ( semaphore s) s. count++i if (s count <= 0) remove a process p from squeue; place process p on ready list Figure 5.3 A Definition of Semaphore Primitives
5.3.1 What is semaphore?(6/10） • Semaphore Primitives(原语，原子操作) 9 P V
5.3.1 What is semaphore? (7/10 Binary Semaphore(二元信号量) a binary semaphore is initialized to 1 PO waits until the value is 1 · Then set it to0 VO sets the value to 1 Wakes up a thread waiting at PO, if any
5.3.1 What is semaphore?(7/10） • Binary Semaphore(二元信号量) • A binary semaphore is initialized to 1 • P() waits until the value is 1 • Then set it to 0 • V() sets the value to 1 • Wakes up a thread waiting at P(), if any 10
5.3.1 What is semaphore? (8/10 Binary semaphore primitives struct binary semaphore enum (zero, one) value; crueueType queue void semwaitB(binary semaphore s) if(s value = 1) s, value o else place this process in s queue block this process; void semsignalB (semaphore s) if(s queue. is empty() s. value 1 else remove a process p from s queue place process p on ready listi Figure 5.4 A Definition of Binary Semaphore Primitives
5.3.1 What is semaphore?(8/10） • Binary Semaphore Primitives 11 P V