UB CSE 421 - Concurrency, Mutual Exclusion and Synchronization (43 pages)

Previewing pages 1, 2, 3, 20, 21, 22, 41, 42, 43 of 43 page document View the full content.
View Full Document

Concurrency, Mutual Exclusion and Synchronization



Previewing pages 1, 2, 3, 20, 21, 22, 41, 42, 43 of actual document.

View the full content.
View Full Document
View Full Document

Concurrency, Mutual Exclusion and Synchronization

135 views


Pages:
43
School:
University at Buffalo, The State University of New York
Course:
Cse 421 - Introduction to Operating Systems
Introduction to Operating Systems Documents
Unformatted text preview:

Concurrency Mutual Exclusion and Synchronization B Ramamurthy CSE421 01 14 19 B Ramamurthy 1 Introduction An important and fundamental feature in modern operating systems is concurrent execution of processes threads This feature is essential for the realization of multiprogramming multiprocessing distributed systems and client server model of computation Concurrency encompasses many design issues including communication and synchronization among processes sharing of and contention for resources In this discussion we will look at the various design issues problems and the wide variety of solutions available 01 14 19 B Ramamurthy 2 Topics for discussion The principles of concurrency Interactions among processes Mutual exclusion problem Mutual exclusion solutions Software approaches Dekker s and Peterson s Hardware support test and set atomic operation OS solution semaphores PL solution monitors Distributed OS solution message passing Reader writer problem 01 14 19 B Ramamurthy 3 Principles of Concurrency 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 01 14 19 B Ramamurthy 4 Concurrency contd 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 in buffer critical resource one process shared code critical region 01 14 19 B Ramamurthy 5 Interactions among processes In a multi process application these are the various degrees of interaction 1 Competing processes Processes themselves do not share anything But OS has to share the system resources among these processes competing for system resources such as disk file or printer Co operating processes Results of one or more processes may be needed for another process 2 Co operation by sharing Example Sharing of an IO buffer Concept of critical section indirect 3 Co operation by communication Example typically no data sharing but co ordination thru synchronization becomes essential in certain applications direct 01 14 19 B Ramamurthy 6 Interactions contd Among the three kinds of interactions indicated by 1 2 and 3 above 1 is at the system level potential problems deadlock and starvation 2 is at the process level significant problem is in realizing mutual exclusion 3 is more a synchronization problem We will study mutual exclusion here and defer deadlock starvation and synchronization for a later time 01 14 19 B Ramamurthy 7 Mutual exclusion problem Successful use of concurrency among processes requires the ability to define critical sections and enforce mutual exclusion Critical section is that part of the process code that affects the shared resource Mutual exclusion in the use of a shared resource is provided by making its access mutually exclusive among the processes that share the resource This is also known as the Critical Section CS problem 01 14 19 B Ramamurthy 8 Mutual exclusion Any facility that provides mutual exclusion should meet these requirements 1 No assumption regarding the relative speeds of the processes 2 A process is in its CS for a finite time only 3 Only one process allowed in the CS 4 Process requesting access to CS should not wait indefinitely 5 A process waiting to enter CS cannot be blocking a process in CS or any other processes 01 14 19 B Ramamurthy 9 Software solution 1 Process 0 while turn 0 do nothing busy waiting Critical Section turn 1 Problems Strict alternation Busy Waiting 01 14 19 Process 1 while turn 1 do nothing busy waiting Critical Section turn 0 B Ramamurthy 10 Software solution 2 PROCESS 0 flag 0 TRUE while flag 1 do nothing CRITICAL SECTION flag 0 FALSE PROBLEM Potential for deadlock if one of the processes fail within CS 01 14 19 PROCESS 1 flag 1 TRUE while flag 0 do nothing CRITICAL SECTION flag 1 FALSE B Ramamurthy 11 Dekker s solution Solution 1 cared about just mutual exclusion only one key to the lock solution Solution 2 cared about fairness and mutual exclusion But could result in deadlock There are variations of this which could result in starvation none entering the CS or one of them monopolizing the CS A correct solution that combines turn and flag array was designed by Dekker We will study this next 01 14 19 B Ramamurthy 12 Features of Dekker s flag n n 0 1 indicates desire to enter CS by process n turn n indicates that it is process n s turn Process 0 flag 0 1 NOT flag 1 enter CS flag 0 1 flag 1 1 turn 1 then wait for turn 0 after making flag 0 0 letting the other one go Go through Fig 5 3 01 14 19 B Ramamurthy 13 Peterson s algorithm Global array variable flag indicates position of each process with reference to mutual exclusion Global variable turn resolves simultaneity conflicts Advantage of Peterson s over Dekker s Simple proof Easily extendible to n processes exam question Go through Fig 5 4 01 14 19 B Ramamurthy 14 Hardware Support On an uniprocessor machine disable interrupts Solution in multiprocessor configurations Access to a memory location excludes any other access to the same location simultaneously How to implement single instruction or atomic test and set instructions Two common instructions Test and set Exchange 01 14 19 B Ramamurthy 15 Hardware support contd Function for Test and Set instruction bool testSet bool i test if i 0 set i 1 return 1 else return 0 0 FALSE 1 TRUE 01 14 19 B Ramamurthy 16 Test and Set usage while NOT testSet lock do nothing CS lock 0 RS 01 14 19 B Ramamurthy 17 Exchange void exchange int R int Mem int Temp temp Mem Mem R R temp 01 14 19 B Ramamurthy 18 Usage of Exchange key 1 do exchange key lock until key 0 CS lock 0 RS Read advantages and disadvantages on page 216 01 14 19 B Ramamurthy 19 Semaphores Think about a semaphore ADT class Counting semaphore binary semaphore Attributes semaphore value Functions init wait signal Support provided by OS Considered an OS resource a limited number available a limited number of instances objects of semaphore class is allowed Can easily implement mutual exclusion among any number of processes 01 14 19 B Ramamurthy 20 wait S wait S S value S value 1 if S value 0 add this process P


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Concurrency, Mutual Exclusion and Synchronization and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Concurrency, Mutual Exclusion and Synchronization and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?