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.1 Principles of Concurrency .5.1.0 What is concurrency .5.1.1 A Simple example ·5.1.2 Race condition 5.1.3 Operating System Concerns 5.1. 4 Process Interaction 5.1.5 Requirements for Mutual Exclusion
5.1 Principles of Concurrency • 5.1.0 What is concurrency • 5.1.1 A Simple Example • 5.1.2 Race Condition • 5.1.3 Operating System Concerns • 5.1.4 Process Interaction • 5.1.5 Requirements for Mutual Exclusion 3
5.1.0 What is concurrency (1/5) Operating System design is concerned with the management of processes and threads Multiprogramming multiple processes within a uniprocessor system Multiprocessing multiple processes within a multiprocessor Distributed processing multiple processes within distributed computer systems, such as clusters
5.1.0 What is concurrency(1/5) • Operating System design is concerned with the management of processes and threads: • Multiprogramming • multiple processes within a uniprocessor system • Multiprocessing • multiple processes within a multiprocessor • Distributed Processing • multiple processes within distributed computer systems, such as clusters 4
5.1.0 What is concurrency (2/5) Concurrency The execution of two or more process simultaneously
5.1.0 What is concurrency(2/5) • Concurrency • The execution of two or more process simultaneously. 5
5.1.0 What is concurrency (3/5) Concurrent and Parallel Programming Concurren Twe Queues C~c-q「a 吴吴吴天是奚呈玉玉 uu.cs Coe -fece Facties 長菜王玉王买买是 天天吴头天玉 Concurrent: 2 queues and 1 coffee machine Parallel: 2 queues and 2 coffee machines
5.1.0 What is concurrency(3/5) • Concurrent and Parallel Programming • Concurrent: 2 queues and 1 coffee machine • Parallel: 2 queues and 2 coffee machines 6
5.1.0 What is concurrency(4/5) Difficulties of Concurrency Sharing of variables Optimal management of resource allocation Locating programming errors(cannot reproduce) because of following facts relative speed of execution of processes is not predictable system interrupts are not predictable scheduling policies may vary
5.1.0 What is concurrency(4/5) • Difficulties of Concurrency • Sharing of variables • Optimal management of resource allocation • Locating programming errors (cannot reproduce) • because of following facts: • relative speed of execution of processes is not predictable. • system interrupts are not predictable • scheduling policies may vary 7
5.1.0 What is concurrency(5/5 Table 5.1 Some Key Terms Related to Concurrency atomic operation A sequence of one or more statements that appears to be indivisible; that is, no other process can see an intermediate state or interrupt the operation critical section a section of code within a process that requires access to shared resources and that must not be executed while another process is in a corresponding section of code deadlock A situation in which two or more processes are unable to proceed because each is waiting for one of the others to do something livelock A situation in which two or more processes continuously change their states in response to changes in the other process(es) without doing any useful work mutual exclusion The requirement that when one process is in a critical section that accesses shared resources, no other process may be in a critical section that accesses any of those shared resources. race condition A situation in which multiple threads or processes read and write a shared data item and the final result depends on the relative timing of their execution starvation A situation in which a runnable process is overlooked indefinitely by the scheduler; although it is able to proceed, it is never chosen
8 5.1.0 What is concurrency(5/5)
5.1 Principles of concurrent 5.1.0 What is concurrency 5.1.1 A Simple Example of shared variable ·5.1.2 Race condition 5.1.3 Operating System Concerns 5.1. 4 Process Interaction 5.1.5 Requirements for Mutual Exclusion
5.1 Principles of Concurrency • 5.1.0 What is concurrency • 5.1.1 A Simple Example of shared variable • 5.1.2 Race Condition • 5.1.3 Operating System Concerns • 5.1.4 Process Interaction • 5.1.5 Requirements for Mutual Exclusion 9
5.1.1 A Simple Example( 1/4 Consider the following procedure echo which is global to all applications char chin chou void echo chin getchar shout chin putchar(chou)
10 5.1.1 A Simple Example（1/4) • Consider the following procedure echo • which is global to all applications char chin, chout; void echo() { chin = getchar(); chout = chin; putchar(chout); }
5.1.1 A Simple Example( 2/4 Uniprocessor Process p1 Process p2 chin getchar(ix chou chini chin getchar()iY putchar(chou)i ch。ut=chin; putchar(chou)i
11 5.1.1 A Simple Example（2/4) . chin = getchar(); chout = chin; . putchar(chout); . . . Process P2 . . . chin = getchar(); . chout = chin; putchar(chout); . Process P1 . Uniprocessor: Y X