Managing Critical Resources in Concurrent Processes

Slide Note
Embed
Share

Concurrent processes can enhance performance but require careful handling of critical resources to prevent inconsistency. Utilizing semaphores for mutual exclusion and synchronization can help control access to shared resources. This article discusses the principles of concurrency, issues with interleaving processes, and the implementation of semaphores to manage critical sections in n processes effectively.


Uploaded on Oct 05, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Critical Section and Critical Resources 1 B. RAMAMURTHY Amrita-UB-MSES-CSE524-2016-5

  2. Issues in Concurrency 2 Concurrent processes /threads help in improving performance However when they share resources, it is required that the access to the resource is protected from inconsistency and incorrect states. These shared resources are called critical resources and the code accessing the resource is called the critical section. The access to the resource needs to be mutually exclusive among concurrent processes. Semaphores are kernel level primitives to help implement mutual exclusion. Amrita-UB-MSES-CSE524-2016-5

  3. Principles of Concurrency Pag e 3 Interleaving and overlapping the execution of processes. Consider two processes P1 and P2 executing the function echo: { input (in, keyboard); out = in; output (out, display); } Amrita-UB-MSES-CSE524-2016-5

  4. ...Concurrency (contd.) Pag e 4 P1 invokes echo, after it inputs into in , gets interrupted (switched). P2 invokes echo, inputs into in and completes the execution and exits. When P1 returns in is overwritten and gone. Result: first ch is lost and second ch is written twice. This type of situation is even more probable in multiprocessing systems where real concurrency is realizable thru multiple processes executing on multiple processors. Solution: Controlled access to shared resource Protect the shared resource : inbuffer; critical resource one process/shared code. critical region Amrita-UB-MSES-CSE524-2016-5

  5. Semaphores Pag e 5 Semaphore is kernel level primitive for realizing mutual exclusion. Attributes: semaphore value, Operations on semaphore: init, wait, signal Considered an kernel resource, a limited number available: a limited number of instances (objects) of semaphore is allowed. Can easily implement mutual exclusion among any number of processes. Can also be used for synchronization. Amrita-UB-MSES-CSE524-2016-5

  6. Critical Section of n Processes Pag e 6 Shared data: Semaphore mutex; //initially mutex = 1 Process Pi: do { mutex.wait(); critical section mutex.signal(); remainder section } while (1); Amrita-UB-MSES-CSE524-2016-5

  7. Semaphore Implementation Pag e 7 Define a semaphore as a class: class Semaphore { int value; // semaphore value ProcessQueue L; // process queue //operations wait() signal() } In addition, two simple utility operations: block() suspends the process that invokes it. Wakeup() resumes the execution of a blocked process P. Amrita-UB-MSES-CSE524-2016-5

  8. Semantics of wait and signal Pag e 8 Semaphore operations now defined as S.wait(): S.value--; if (S.value < 0) { } add this process to S.L; block(); // block a process S.signal(): S.value++; if (S.value <= 0) { remove a process P from S.L; wakeup(); // wake a process } Amrita-UB-MSES-CSE524-2016-5

  9. Semaphores for CS Pag e 9 Semaphore is initialized to 1. The first process that executes a wait() will be able to immediately enter the critical section (CS). (S.wait() makes S value zero.) Now other processes wanting to enter the CS will each execute the wait() thus decrementing the value of S, and will get blocked on S. (If at any time value of S is negative, its absolute value gives the number of processes waiting blocked. ) When a process in CS departs, it executes S.signal() which increments the value of S, and will wake up any one of the processes blocked. The queue could be FIFO or priority queue. Amrita-UB-MSES-CSE524-2016-5

  10. Two Types of Semaphores Pag e 10 Counting semaphore integer value can range over an unrestricted domain. Binary semaphore integer value can range only between 0 and 1; can be simpler to implement. ex: nachos Can implement a counting semaphore using a binary semaphore. Amrita-UB-MSES-CSE524-2016-5

  11. Semaphore for Synchronization Pag e 11 Execute B in Pj only after A executed in Pi Use semaphore flag initialized to 0 Code: Pi A flag.signal() Pj flag.wait() B Amrita-UB-MSES-CSE524-2016-5

  12. Classical Problems of Synchronization e 12 Pag Bounded-Buffer Problem Readers and Writers Problem Dining-Philosophers Problem Amrita-UB-MSES-CSE524-2016-5

  13. Producer/Consumer problem Pag e 13 Producer repeat produce item v; b[in] = v; in = in + 1; forever; Consumer repeat while (in <= out) nop; w = b[out]; out = out + 1; consume w; forever; Amrita-UB-MSES-CSE524-2016-5

  14. Solution for P/C using Semaphores Pag e 14 Producer repeat produce item v; MUTEX.wait(); b[in] = v; in = in + 1; MUTEX.signal(); forever; Consumer repeat while (in <= out) nop; MUTEX.wait(); w = b[out]; out = out + 1; MUTEX.signal(); consume w; forever; Ans: Consumer will busy-wait at the while statement. What if Producer is slow or late? Amrita-UB-MSES-CSE524-2016-5

  15. P/C: improved solution Pag e 15 Producer repeat produce item v; MUTEX.wait(); b[in] = v; in = in + 1; MUTEX.signal(); AVAIL.signal(); forever; Consumer repeat AVAIL.wait(); MUTEX.wait(); w = b[out]; out = out + 1; MUTEX.signal(); consume w; forever; What will be the initial values of MUTEX and AVAIL? ANS: Initially MUTEX = 1, AVAIL = 0. Amrita-UB-MSES-CSE524-2016-5

  16. P/C problem: Bounded buffer Pag e 16 Producer repeat produce item v; while((in+1)%n == out) NOP; b[in] = v; in = ( in + 1)% n; forever; How to enforce bufsize? Consumer repeat while (in == out) NOP; w = b[out]; out = (out + 1)%n; consume w; forever; ANS: Using another counting semaphore. Amrita-UB-MSES-CSE524-2016-5

  17. P/C: Bounded Buffer solution Pag e 17 Producer repeat produce item v; BUFSIZE.wait(); MUTEX.wait(); b[in] = v; in = (in + 1)%n; MUTEX.signal(); AVAIL.signal(); forever; What is the initial value of BUFSIZE? Consumer repeat AVAIL.wait(); MUTEX.wait(); w = b[out]; out = (out + 1)%n; MUTEX.signal(); BUFSIZE.signal(); consume w; forever; ANS: size of the bounded buffer. Amrita-UB-MSES-CSE524-2016-5

  18. Semaphores - comments Pag e 18 Intuitively easy to use. wait() and signal() are to be implemented as atomic operations. Difficulties: signal() and wait() may be exchanged inadvertently by the programmer. This may result in deadlock or violation of mutual exclusion. signal() and wait() may be left out. Related wait() and signal() may be scattered all over the code among the processes. Amrita-UB-MSES-CSE524-2016-5

Related


More Related Content