Ch 6 Synchronization - Mac 2024.pdf

Chapter 6: Synchronization Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013  Chapter 6: Synchronization Tools OBJECTIVES 6.1 Background To present th...

Chapter 6: Synchronization Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013  Chapter 6: Synchronization Tools OBJECTIVES 6.1 Background To present the concept of process synchronization. 6.2 The Critical-Section Problem To introduce the critical-section problem, whose solutions can be used to ensure the consistency of shared data To present both software and hardware solutions of the critical- section problem To examine several classical process-synchronization problems To explore several tools that are used to solve process synchronization problems Operating System Concepts – 9th Edition 6.2 Silberschatz, Galvin and Gagne ©2013  6.1 Background Concurrent access: accessing of the same data at the same time by more than one process, thus: Concurrent access to shared data may result in data inconsistency Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes Race Condition: problem in concurrent execution The synchronization mechanism is usually provided by both hardware and the operating system Illustration of the problem – The producer-Consumer problem. Basic assumption – load and store instructions are atomic. Operating System Concepts – 9th Edition 6.3 Silberschatz, Galvin and Gagne ©2013  6.1 Background (Illustration of the problem ) Illustration of the problem (Scenario): Here's how the producer-consumer problem plays out in this scenario: In this scenario, the Producers (Bakers): shelves act as a buffer ✓ Bakers work in the bakery, baking various types of or a shared resource goods. between the producers and consumers. ✓ Once the goods are baked, they are placed on the Bakers produce goods shelves for sale. and place them on the shelves, Consumers (Customers): and consumers take goods from the shelves. ✓ Customers visit the bakery to purchase baked goods. However, there can be issues if the shelves ✓ They select the items they want to buy from the become empty or shelves. overloaded ✓ Once they make their selections, they purchase the goods and take them home Operating System Concepts – 9th Edition 6.4 Silberschatz, Galvin and Gagne ©2013  6.1 Background Why a Race Condition Occurs? Two processes may be :  executing simultaneously, and  trying to access the same global variable. 6.5 5 Silberschatz, Galvin and Gagne ©2013 Operating System Concepts – 9th Edition  Race Condition - Definition Def 1: A situation whereby at least two processes perform some operations on shared data and the outcome depends on the order of data access. Result of process must be independent of the speed of execution of other concurrent processes; Depend on the control / data synchronization mechanisms. Def 2: A situation whereby multiple threads access a data item without coordination in a multithreaded application. possibly causing inconsistent results (depending on which thread reaches the data item first). * (Multithread normally access / used shared variables) _______________________________________________________________________________ Silberschatz, A., Galvin, P.B., and Gagne, G. Operating System Concepts (9th Edition). John Wiley & Sons: Asia. (2014) Page 255. 6.6 6 Silberschatz, Galvin and Gagne ©2013 Operating System Concepts – 9th Edition  Solution to Race Condition Ensure that only one process at a time can manipulate the shared variable (e.g. Counter) Therefore process synchronization is needed. means coordinating the activities of two or more processes. Synchronization is necessary to ensure that interdependent code is executed in the proper sequence. 6.7 7 Galvin and Gagne ©2013 Silberschatz, Operating System Concepts – 9th Edition  Race Condition (Cont.) How do we solve the race condition? We need to make sure that: The execution of counter = counter + 1 is executed as an “atomic” action. That is, while it is being executed, no other instruction can be executed concurrently. Similarly for counter = counter - 1 The ability to execute an instruction, or a number of instructions, atomically is crucial for being able to solve many of the synchronization problems. Operating System Concepts – 9th Edition 6.8 Silberschatz, Galvin and Gagne ©2013  6.2 Critical Section Problem Scenario 1 Operating System Concepts – 9th Edition 6.9 Silberschatz, Galvin and Gagne ©2013  6.2 Critical Section Problem Scenario 2 Operating System Concepts – 9th Edition 6.10 Silberschatz, Galvin and Gagne ©2013  6.2 Critical Section Problem Consider system of n processes {p0, p1, … pn-1} Each process has critical section segment of code Process may be changing common variables, updating table, writing file, etc When one process in critical section, no other may be in its critical section Critical section problem is to design protocol to solve this Each process must ask permission to enter critical section in entry section, may follow critical section with exit Pastry section, then remainder section display Operating System Concepts – 9th Edition 5.11 Silberschatz, Galvin and Gagne ©2013  Solution to Critical-Section Problem Must satisfy the following three requirements: 1. Mutual Exclusion - If process Pi is executing in its critical section, then no other processes can be executing in their critical sections Example (Banking) In a banking system, let's consider a database that manages customer accounts, allowing multiple users to deposit, withdraw, or transfer funds simultaneously. The database is a shared resource, and each transaction (e.g., a fund transfer between two accounts) represents a process that needs access to the critical section. The critical section in this context is a specific part of the database that handles account balances. When a bank employee or customer initiates a fund transfer, the system must ensure that no other process can simultaneously modify the same account balances. This is critical to prevent data inconsistency or corruption Operating System Concepts – 9th Edition 6.12 Silberschatz, Galvin and Gagne ©2013  Solution to Critical-Section Problem 2) Progress - If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely. Example (printing) The printer is the critical section. Only one print job can be processed at a time, so any other print jobs must wait in the print queue. The print queue is responsible for managing the order in which print jobs are processed. The principle of Progress implies that if no print job is currently being processed (the critical section is free), but there are jobs in the print queue, one of those jobs must be allowed to enter the critical section and get printed. It cannot be postponed indefinitely, or else users would experience frustration, leading to inefficiency and decreased productivity. Operating System Concepts – 9th Edition 6.13 Silberschatz, Galvin and Gagne ©2013  Solution to Critical-Section Problem 3. Bounded Waiting - A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted Example (reading from Disk) In a typical multi-threaded operating system, many processes may need to read from or write to a shared disk. The disk represents a critical section because only one process can read from or write to it at a time without causing data inconsistency or corruption. When a process requests disk access, it joins a queue managed by the operating system's disk scheduler. The key concept of bounded waiting is ensuring that no process is postponed indefinitely while waiting to access the disk Operating System Concepts – 9th Edition 6.14 Silberschatz, Galvin and Gagne ©2013  End of Chapter 6 Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013