DOC PREVIEW
U of I CS 241 - Synchronization Primitive - Semaphores

This preview shows page 1-2-20-21 out of 21 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 21 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 21 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 21 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 21 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 21 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Synchronization Primitive - SemaphoresCS241 AdministrativeDiscussionSlide 4Test and Set InstructionUsage of Test_And_Set for Mutual ExclusionSemaphore ConceptDefinition of Semaphore Primitives (Counting Semaphore)Definition of Binary Semaphore PrimitivesMutual Exclusion Using SemaphoresSlide 11Exercise – Exam QuestionImplementation of Semaphores in POSIXUnnamed Semaphores Ch 14 pp 491-501Sharing Semaphoressem_init can fail!!!Initialization ExampleSemaphore OperationsSlide 19Slide 20SummaryCS 241 Spring 2007System Programming 1Synchronization Primitive - SemaphoresLecture 11Klara Nahrstedt2CS241 AdministrativeSMP2 Quiz on Monday, 2/12/07Read Chapter 5.3 in Stallings Book and Chapter 14 in R&R3DiscussionIn uni-processorConcurrent processes cannot be overlapped, only interleavedProcess runs until it invokes system call, or is interruptedTo guarantee mutual exclusion, hardware support could help by allowing disabling interruptsWhile(true) { /* disable interrupts */ /* critical section */ /* enable interrupts */ /* remainder */}What’s the problem with this solution?4DiscussionIn multi-processorsSeveral processors share memoryProcessors behave independently in a peer relationshipInterrupt disabling will not workWe need hardware support The hardware support is based on execution of multiple instructions atomicallyAtomic execution of a set of instructions means that these instructions are treated as a single step that cannot be interrupted5Test and Set Instructionboolean Test_And_Set(boolean* lock) atomic { boolean initial; initial = *lock; *lock = true; return initial;}pseudo-code!6 Usage of Test_And_Set for Mutual ExclusionPi{ while(1) { while(Test_And_Set(lock)) { }; /* Critical Section */ lock =0; /* remainder */} }Void main (){ lock = 0; parbegin(P1,…,Pn);}Busy Waiting Issue !!!7Semaphore ConceptFundamental Principle: two or more processes want to cooperate by means of simple signalsFor signaling introduceSpecial Variable : Semaphore sPrimitives: semSignal(s) – transmit signal via semaphore ssemWait(s) – receive signal via semaphore sPrimitives semSignal and semWait must be ATOMIC!!!Note: Different notation is used for semSignal and semWait (P for semWait, V for semSignal, ‘wait’ for semWait, ‘signal’ for semSignal)8Definition of Semaphore Primitives (Counting Semaphore)struct semaphore{int count;queueType queue; };void semWait(semaphore s){s.count--;if (s.count < 0){ place this process in s.queue; block this process;}} void semSignal(semaphore s){s.count++;if (s.count ≤ 0){remove a process P from s.queue; place process P on ready list; }}9Definition of Binary Semaphore Primitives struct binary_semaphore { enum {0,1} value; queueType queue; };void semWaitB(binary_semaphore s){if (s.value == 1)s.value = 0; else{ place this process in s.queue; block this process;}} void semSignalB(binary_semaphore s) {if (s.queue is empty()) s.value = 1;else{ remove a process P from s.queue; place process P on ready list; }}10Mutual Exclusion Using Semaphoressemaphore s = 1; Pi{while(1) { semWait(s); /* Critical Section */ semSignal(s); /* remainder */}}Pi{ while(1) { while(Test_And_Set(lock)) { }; /* Critical Section */ lock =0; /* remainder */} }lock = 0;11Value of SemaphorelockQueueAsemWait(lock)01semWait(lock)BB-1semSignal(lock)0semSignal(lock)1Process Process Critical RegionNormal ExecutionBlocked onsemaphore lock12Exercise – Exam Question process 1 executes while(1) { semWait(S);a;semSignal(Q); } process 2 executeswhile(1) {semWait(Q);b;semSignal(S); }Consider 2 processes sharing two semaphores S and Q to protect critical variables ‘a’ and ‘b’. What happens in the pseudocode ifSemaphores S and Q are initialized to 1 (or 0)?13Implementation of Semaphores in POSIXPOSIX:SEM semaphore is variable of type sem_t Atomic Operations: int sem_init(sem_t *sem, int pshared, unsigned value);int sem_destroy(sem_t *sem);int sem_post(sem_t *sem);Int sem_trywait(sem_t *sem);Int sem_wait(sem_t *sem);Use <semaphore.h>14Unnamed Semaphores Ch 14 pp 491-501#include <semaphore.h>Sem_t sem;You cannot make a copy of a semaphore variable!!!#include <semaphore.h>int sem_init(sem_t *sem, int pshared, unsigned value);pshared == 0 only threads of process creating semaphore can use semaphore.15Sharing SemaphoresSharing semaphores between threads within a process is easy, use pshared==0Forking a process creates copies of any semaphore it has… this does not share the semaphoreMaking pshared non zero allows any process that can access the semaphore to use it. This places the semaphore in global environment.16sem_init can fail!!!In unsuccessful, sem_init returns -1 and sets errno.Value > sem_value_maxResources exhaustedInsufficient privilegesEINVALENOSPCEPERMcauseerrno17Initialization Examplesem_t semA;if (sem_init(&semA, 0, 1) == -1) perror(“Failed to initialize semaphore semA”);18Semaphore Operations#include <semaphore.h>int sem_destroy(sem_t *sem);Destroying a semaphore that’s been destroyed gives undefined result. Destroying a semaphore on which a thread is blocked gives undefined results.19Semaphore Operations#include <semaphore.h>int sem_post(sem_t *sem); signal safecan be used in signal handlersif unsuccessful, returns -1 and sets errnoerrno == EINVAL if semaphore doesnt exist20Semaphore Operationsint sem_trywait(sem_t *sem);doesn’t blockreturns -1 and errno==EAGAIN if semaphore zerocan be interrupted by signal – errno == EINTRint sem_wait(sem_t *sem);blocks if semaphore zerocan be interrupted by signal – errno == EINTR21Summary SemaphoresSemaphore implementationPOSIX SemaphoreProgramming with semaphoresS: Chapter 5 pp 215-227, RR:Chapter 14


View Full Document

U of I CS 241 - Synchronization Primitive - Semaphores

Documents in this Course
Process

Process

28 pages

Files

Files

37 pages

File I/O

File I/O

52 pages

C Basics

C Basics

69 pages

Memory

Memory

23 pages

Threads

Threads

14 pages

Lecture

Lecture

55 pages

C Basics

C Basics

24 pages

Signals

Signals

27 pages

Memory

Memory

45 pages

Threads

Threads

47 pages

Threads

Threads

28 pages

LECTURE

LECTURE

45 pages

Threads

Threads

30 pages

Threads

Threads

55 pages

Files

Files

37 pages

SIGNALS

SIGNALS

22 pages

Files

Files

37 pages

Threads

Threads

14 pages

Threads

Threads

13 pages

Load more
Download Synchronization Primitive - Semaphores
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 Synchronization Primitive - Semaphores 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 Synchronization Primitive - Semaphores 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?