Chico CSCI 372 - Critical Sections and Semaphores

Unformatted text preview:

Critical Sections and SemaphoresProtecting CSNon-Atomic Operationstest-and-set/swapBusy-Wait SemaphoresWaiting List SemaphoresMotivation for ‘and’ Syncronization‘and’ Syncronization‘and’ Syncronization ImplementationWhy Wake All Processes on Signal?POSIX.1b SemaphoresPOSIX.1b Semaphore VariablesPOSIX.1b Semaphore DeclarationSemaphore Operationssem_initsem_destroysem_wait and sem_trywaitsem_postsem_getvalueUnnamed Semaphore ExampleNamed Semaphoressem_opensem_open oflag parametersem_closesem_unlinkNamed Semaphore Example – (top)Named Semaphore Example – (bottom)System V SemaphoresPosix vs System V SemaphoresSemaphore SetsSemaphore Sets (Cont)Semaphore CreationIPC_PRIVATERandom KeyGenerate Key from ftoksemopstruct sembufsem_opset_sembuf_structSemaphore – Example 1struct sembuf – Example 1Semaphore – Ex 2 (1)Semaphore – Ex 2 (2)Semaphore – Ex 2 (3)Semaphore – Ex 2 (4)Semaphore – Example 3struct sembuf – Example 2Create and Set Semaphore (top)Create and Set Semaphore (bottom)semctlImportant Commandssemnum Paramaterinitialize _sem_elementremove_semaphoreCommand Prompt Semaphore Opssemop_restartsem_wait_restartCritical Sections and Semaphores•A critical section is code that contains access to shared resources that can accessed by multiple processes.• Critical sections can be managed with semaphores• This chapter describes POSIX.1b semaphores and System V semaphoresProtecting CS• Mutual Exclusion – Only one process is in CS at a time• Progress – If no process is in CS, a process that wishes to can get in• Bounded Wait – No process can be postponed indefinitely (starved)Non-Atomic OperationsImplementations of: c++;and c–– ;r1 = c; r2 = c;r1 = r1 + 1; r2 = r2 – 1;c = r1; c = r2;c = 6;Process A Process B…; c++; … …; c ––; … At the end of processes A and B we expect c to be incremented and decremented so the final value is 6.However, if process A is interrupted after completing the instruction r1 = c; and process B executes to completion, c = 5 at the end of B and it is set to 7 after A finishestest-and-set/swap• Test-and-Set and Swap are routines implemented in hardware to coordinate lower level critical sections such as the implementing of a semaphore counter• Review section 8.1 if you are unfamiliar with these operationsBusy-Wait Semaphoreswait – while (*s <= 0) noop;(*s)––;signal – (*s)++;*s = 1;Process A Process Bwait(&s); wait(&s);c++; c––;signal(&s); signal(&s);• Busy-wait implementations waste CPU cycles• One process can starve the othersWaiting List Semaphoreswait – if (sp->value > 0)sp->value ––;else {<block the current process and add it to waiting list sp->list> signal – if (sp->list != NULL)<remove process at head of semaphore queue and place it in ready queue>elsesp->value++;Motivation for ‘and’ Syncronization*A = 1; *B = 1;Process 1 Process 2 Process 3wait(&A); wait(&A); wait(&B);<use resource A> wait(&B); <use resource B>signal(&A); <use resources A and B> signal(&B);signal(&B);signal(&A);‘and’ Syncronization*A = 1; *B = 1;Process 1 Process 2 Process 3wait(&A); wait(&A, &B); wait(&B);<use resource A> <use resources A and B> <use resource B>signal(&A); signal(&A, &B); signal(&B);wait(&A, &B) denotes simultaneous wait on A and B. The semaphores A and B are decremented only if both of them can decremented without blocking‘and’ SyncronizationImplementationwait – if ((ap->value > 0) && (bp->value > 0)) {(ap->value)--;(bp->value)--;}elseif (ap->value <= 0)<add current process to ap->list>else<add current process to bp->list><block process and reset pc to beginning of wait>signal – ap->value++;<move all processes on ap->list to ready queue>bp->value++;<move all processes on bp->list to ready queue>Why Wake All Processes on Signal?Process 1 Process 2 Process 3a1: wait(&A,&B); a2: wait(&B,&C); a3: signal(&B,&C);b1: <critical section> b2: <critical section> c1: signal(&A,&B); c2: signal(&B,&C);Assume a1 is executed followed by a2, the semaphore queues are:A: process 1B: process 1, process 2C: process 2Then, if a3 is executed and the signal only wakes up the first process in each queue, the semaphore queues are:A: process 1B: process 2C:Now process 1 holds B while blocking on A. Process 2 cannot proceed until process 1 gets A. This defeats the purpose of ‘and’ synchronizationPOSIX.1b Semaphores• POSIX.1b standard was adopted in 1993• Since they are new, POSIX semaphores may not be available in all operating systems – even those that claim to be POSIX.1 compliant• An implementation supports POSIX semaphores if _POSIX_SEMAPHORES is defined in unistd.h – It is defined there on the ect-unix machinesPOSIX.1b Semaphore Variables• Semaphore variable is of type sem_t• Atomic operations for initializing, incrementing and decrementing value• Unnamed semaphores – Can be used by a single process or by children of a process that created it• Named semaphores – Can be used by all processes• Unnamed semaphores are similar in operation to pipes, and named semaphores are similar to named pipesPOSIX.1b Semaphore Declaration#include <semaphore.h>sem_t sem;• sem is a semaphore variable• POSIX.1b does not specify underlying type of sem_t• One possibility is for it to act like a file descriptor that points to a local table and the table entries point to entries in a system file tableSemaphore OperationsSYNOPSIS#include <semaphore.h>int sem_init (sem_t *sem, int pshared, unsigned int value);int sem_destroy (sem_t *sem);int sem_wait (sem_t *sem);int sem_try (sem_t *sem);int sem_post (sem_t *sem);int sem_getvalue (sem_t *sem, int *sval);POSIX.1b• All semaphore functions return –1 and set errno on error• It is uncertain what semaphore functions return on success, but usually 0• _POSIX_SEMAPHORES may be defined but system may NOT support POSIX.1b semaphores• POSIX.1b semaphores are counting semaphoressem_init• Initializes semaphore to value parameter• If the value of pshared is non-zero, the semaphore can be used between processes (the process that initializes it and by children of that process)• If the value of pshared is zero, the semaphore can only be used by threads of a single process•Think of sem as referring to a semaphore rather than being the semaphore itselfsem_destroy• Destroys a previously initialized semaphore• If sem_destroy attempts to destroy a semaphore that is being used by another process, it may return –1 and


View Full Document

Chico CSCI 372 - Critical Sections and Semaphores

Download Critical Sections and 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 Critical Sections and 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 Critical Sections and 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?