SEN362 Operating Systems Lecture Notes Week 5 PDF

SEN362 Operating Systems Ass. Prof. Dr. Ahmed El-Hadad K-7505 [email protected] Week 05 Chapter 5 Concurrency: Mutual Exclusion and Operating Systems: Synchronization...

SEN362 Operating Systems Ass. Prof. Dr. Ahmed El-Hadad K-7505 [email protected] Week 05 Chapter 5 Concurrency: Mutual Exclusion and Operating Systems: Synchronization Internals and Design Principles Ninth Edition, Global Edition By William Stallings Stallings, W. (2017). Operating systems: Internals and design principles, global edition. 2 Pearson Education Limited.  Multiple Processes Operating System design is concerned with the management of processes and threads: Multiprogramming The management of multiple processes within a uniprocessor system Multiprocessing The management of multiple processes within a multiprocessor Distributed Processing The management of multiple processes executing on multiple, distributed computer systems The recent proliferation of clusters is a prime example of this type of system. 3  Concurrency Arises in Three Different Contexts: Multiple Applications Structured Invented to Applications allow Operating processing System time to be Extension of Structure shared among modular active design and OS applications structured themselves programming implemented as a set of processes or threads 4 Table 5.1 Some Key Terms Related to Concurren cy 5  Mutual Exclusion: Software Approaches Software approaches can be implemented for concurrent processes that execute on a single-processor or a multiprocessor machine with shared main memory These approaches usually assume elementary mutual exclusion at the memory access level Simultaneous accesses (reading and/or writing) to the same location in main memory are serialized by some sort of memory arbiter, although the order of access granting is not specified ahead of time Beyond this, no support in the hardware, operating system, or programming language is assumed Dijkstra reported an algorithm for mutual exclusion for two processes, designed by the Dutch mathematician Dekker Following Dijkstra, we develop the solution in stages 6  Principles of Concurrency Interleaving and overlapping Can be viewed as examples of concurrent processing Both present the same problems Uniprocessor – the relative speed of execution of processes cannot be predicted Depends on activities of other processes The way the OS handles interrupts Scheduling policies of the OS 7  Difficulties of Concurrency Sharing of global resources Difficult for the OS to manage the allocation of resources optimally Difficult to locate programming errors as results are not deterministic and reproducible 8  Race Condition Occurs when multiple processes or threads read and write data items The final result depends on the order of execution The “loser” of the race is the process that updates last and will determine the final value of the variable 9  Operating System Concerns Design and management issues raised by the existence of concurrency: The OS must: Be able to keep track of various processes Allocate and de-allocate resources for each active process Protect the data and physical resources of each process against unintended interference by other processes The functioning of a process, and the output it produces, must be independent of the speed at which its execution is carried out relative to An dthe speed of other concurrent processes 10 Table 5.2 Process Interactio n 11  Resource Competition Concurrent processes come into conflict when they are competing for use of the same resource  For example: I/O devices, memory, processor time, clock In the case of competing processes three control problems must be faced: The need for mutual exclusion Deadlock Starvation 12  Cooperation Among Processes by Sharing Because data are held on resources Processes may (devices, use and update memory), the Thus the control problems Covers processes the shared data processes must The control of mutual that interact with without reference cooperate to mechanisms exclusion, other processes to other ensure that the must ensure the deadlock, and without being processes, but data they share integrity of the starvation are explicitly aware know that other are properly shared data again present of them processes may managed have access to The only difference is the same data that data items may be accessed in two different modes, reading and writing, and only writing operations must be mutually exclusive 13  Cooperation Among Processes by Communication The various processes participate in a common effort that links all of the processes The communication provides a way to synchronize, or coordinate, the various activities Typically, communication can be characterized as consisting of messages of some sort Primitives for sending and receiving messages may be provided as part of the programming language or provided by the OS kernel Mutual exclusion is not a control requirement for this sort of cooperation 14  Requirements for Mutual Exclusion Any facility or capability that is to provide support for mutual exclusion should meet the following requirements: Mutual exclusion must be enforced: only one process at a time is allowed into its critical section, among all processes that have critical sections for the same resource or shared object A process that halts must do so without interfering with other processes It must not be possible for a process requiring access to a critical section to be delayed indefinitely: no deadlock or starvation When no process is in a critical section, any process that request entry to its critical section must be permitted to enter without delay No assumptions are made about relative process speeds or number of processes A process remains inside its critical section for a finite time only 15  Mutual Exclusion: Hardware Support  Interrupt Disabling  Disadvantages:  In a uniprocessor system, concurrent processes cannot have  The efficiency of execution overlapped execution; they can could be noticeably only be interleaved degraded because the  A process will continue to run until processor is limited in its it invokes an OS service or until it ability to interleave is interrupted processes  Therefore, to guarantee mutual  This approach will not work exclusion, it is sufficient to in a multiprocessor prevent a process from being architecture interrupted  This capability can be provided in 16 the form of primitives defined by  Mutual Exclusion: Hardware Support Compare & Swap Instruction Also called a “compare and exchange instruction” A compare is made between a memory value and a test value If the values are the same a swap occurs Carried out atomically (not subject to interruption) 17  Special Machine Instruction: Advantages Applicable to any number of processes on either a single processor or multiple processors sharing main memory Simple and easy to verify It can be used to support multiple critical sections; each critical section can be defined by its own variable 18  Special Machine Instruction: Disadvantages Busy-waiting is employed Thus while a process is waiting for access to a critical section it continues to consume processor time Starvation is possible When a process leaves a critical section and more than one process is waiting, the selection of a waiting process is arbitrary; some process could indefinitely be denied access Deadlock is possible 19  Table 5.3 Common Concurren cy Mechanis ms 20  Semaphor e A variable that There is no way to has an integer value upon which inspect or manipulate only three semaphores other than operations are these three operations defined: 1) A semaphore may be initialized to a nonnegative integer value 2) The semWait operation decrements the semaphore value 3) The semSignal operation increments the 21  Consequences There is no way to know which There is no way to You don’t know process will know before a whether another continue process process is waiting immediately on a decrements a so the number of uniprocessor semaphore unblocked system when two whether it will processes may be processes are block or not zero or one running concurrently 22  Strong/Weak Semaphores A queue is used to hold processes waiting on the semaphore Strong Semaphores The process that has been blocked the longest is released from the queue first (FIFO) Weak Semaphores The order in which processes are removed from the queue is not specified 23  Producer/Consumer Problem General One or more producers are generating data Stateme and placing these in a buffer nt: A single consumer is taking items out of the buffer one at a time Only one producer or consumer may access the buffer at any one time The Ensure that the producer won’t try to Problem: add data into the buffer if its full, and that the consumer won’t try to remove data from an empty buffer 24  Monitors Programming language construct that provides equivalent functionality to that of semaphores and is easier to control Implemented in a number of programming languages Concurrent Pascal, Pascal-Plus, Modula-2, Modula-3, Java Has also been implemented as a program library Software module consisting of one or more procedures, an initialization sequence, and local data 25 Monitor Characteristics Local data variables are accessible only by the monitor’s procedures and not by any external procedure Process enters monitor by invoking one of its procedures Only one process may be executing in the monitor at a time 26  Summary Mutual exclusion: software approaches Dekker’s algorithm Monitors Peterson’s algorithm Monitor with signal Alternate model of monitors Principles of concurrency with notify and broadcast Race condition OS concerns Message passing Process interaction Synchronization Requirements for mutual exclusion Addressing Message format Mutual exclusion: hardware support Interrupt disabling Queueing discipline Special machine instructions Mutual exclusion Semaphores Readers/writers problem Mutual exclusion Readers have priority Producer/consumer problem Writers have priority Implementation of semaphores 27