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 AdministrativeSMP2 Quiz on Monday, 2/12/07Read Chapter 5.3 in Stallings Book and Chapter 14 in R&R3DiscussionIn uni-processorConcurrent processes cannot be overlapped, only interleavedProcess runs until it invokes system call, or is interruptedTo 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?4DiscussionIn multi-processorsSeveral processors share memoryProcessors behave independently in a peer relationshipInterrupt disabling will not workWe need hardware support The hardware support is based on execution of multiple instructions atomicallyAtomic 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 introduceSpecial Variable : Semaphore sPrimitives: semSignal(s) – transmit signal via semaphore ssemWait(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