DOC PREVIEW
UB CSE 321 - XinuSemaphoresOct24

This preview shows page 1-2-3-19-20-38-39-40 out of 40 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 40 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Slide 1ConcurrencyPrinciples of Concurrency...Concurrency (contd.)Interactions among processesInteractions ...(contd.)Mutual exclusion problemSoftware Solutions: Algorithm 1Algorithm 2Algorithm 3SemaphoresCritical Section of n ProcessesSemaphore ImplementationSemantics of wait and signalSemaphores for CSTwo Types of SemaphoresSemaphore for SynchronizationClassical Problems of SynchronizationProducer/Consumer problemSolution for P/C using SemaphoresP/C: improved solutionP/C problem: Bounded bufferP/C: Bounded Buffer solutionSemaphores - commentsXinu Resources & Critical ResourcesCritical sections and SemaphoresSemaphoresSemaphores in exinuSemaphores in exinu (contd.)Definition of Semaphores functionsSemaphore: newsem contd.Semaphore: wait(…)Semaphore: wait()Semaphore: signal()Semaphore: usageProblem 1Problem 1: multi-tasksProblem 1Problem 2Task flowXinu Semaphores01/13/2019 Page 2Concurrency•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/13/2019 Page 3Principles 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/13/2019 Page 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/13/2019 Page 5Interactions 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/13/2019 Page 6Interactions ...(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 and synchronization here, and defer deadlock, and starvation for a later time.01/13/2019 Page 7Mutual 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/13/2019 Page 8Software Solutions: Algorithm 1•Process 0•...•while turn != 0 do• nothing;•// busy waiting•< Critical Section>•turn = 1;•...Problems : Strict alternation, Busy Waiting•Process 1•...•while turn != 1 do• nothing;•// busy waiting•< Critical Section>•turn = 0;•...01/13/2019 Page 9Algorithm 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.•PROCESS 1•...•flag[1] = TRUE;•while flag[0] do nothing;•<CRITICAL SECTION>•flag[1] = FALSE;01/13/2019 Page 10Algorithm 3•Combined shared variables of algorithms 1 and 2.•Process Pido {flag [i]:= true;turn = j;while (flag [j] and turn = j) ;critical sectionflag [i] = false;remainder section} while (1);•Solves the critical-section problem for two processes.01/13/2019 Page 11Semaphores •Think about a semaphore as a class•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/13/2019 Page 12Critical Section of n Processes•Shared data: Semaphore mutex; //initially mutex = 1•Process Pi: do { mutex.wait(); critical section mutex.signal(); remainder section} while (1);01/13/2019 Page 13Semaphore Implementation•Define a semaphore as a class:class Semaphore{ int value; // semaphore value ProcessQueue L; // process queue //operationswait()signal()}•In addition, two simple utility operations:–block() suspends the process that invokes it.–Wakeup() resumes the execution of a blocked process P.01/13/2019 Page 14Semantics of wait and signal•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}01/13/2019 Page 15 Semaphores for CS•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


View Full Document

UB CSE 321 - XinuSemaphoresOct24

Documents in this Course
Anomaly1

Anomaly1

48 pages

ProcSept9

ProcSept9

17 pages

LecSept2

LecSept2

30 pages

CRCNov23

CRCNov23

14 pages

Load more
Download XinuSemaphoresOct24
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view XinuSemaphoresOct24 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 XinuSemaphoresOct24 2 2 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?