Synchronization Primitive - SemaphoresCS241 AdministrativeDiscussionDiscussionTest and Set Instruction Usage of Test_And_Set for Mutual ExclusionSemaphore ConceptDefinition of Semaphore Primitives (Counting Semaphore)Definition of Binary Semaphore PrimitivesMutual Exclusion Using SemaphoresExercise – Exam QuestionImplementation of Semaphores in POSIXUnnamed Semaphores Ch 14 pp 491-501Sharing Semaphoressem_init can fail!!!Initialization ExampleSemaphore OperationsSemaphore OperationsSemaphore OperationsSummaryCS 241 Spring 2007System Programming1Synchronization 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 supportcould 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!6Usage 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 Primitivesstruct 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 Questionprocess 1 executeswhile(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_tAtomic 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