Chico CSCI 372 - Critical Sections and Semaphores

Unformatted text preview:

Critical Sections and SemaphoresProtecting CSNon-Atomic Operationstest-and-set/swapBusy-Wait SemaphoresWaiting List SemaphoresPOSIX.SEM SemaphoresPOSIX.SEM Semaphore VariablesPOSIX.SEM 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)Critical 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.SEM• semaphores and POSIX.XSIsemaphoresProtecting 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++;POSIX.SEM Semaphores•POSIX.SEM standard was adopted in 1993• Since they are new, POSIX.SEM semaphores may not be available in all operating systems – even those that claim to be POSIX.SEM compliant• An implementation supports POSIX semaphores if _POSIX_SEMAPHORES is defined in unistd.h• It is defined there on the ect-unix machinesPOSIX.SEM 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.SEM Semaphore Declaration#include <semaphore.h>sem_t sem;• sem is a semaphore variable•POSIX.SEM 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.SEM• 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.SEM semaphores•POSIX.SEM 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 set errno to EBUSY – Unfortunately, the specifications do not require that the system detect thissem_wait and sem_trywait• sem_wait is a standard semaphore wait operation• If the semaphore value is 0, sem_wait blocks until it can successfully decrement value or when interrupted such as by SIGINT• sem_trywait is similar to sem_wait except instead of blocking on 0, it returns –1 and sets errno to EAGAINsem_post• sem_post increments the semaphore value and is the classical semaphore signal operation• sem_post must be async_signal_safe and may be invoked from a signal handlersem_getvalue• Allows the user to examine the value of a named or unnamed semaphore• Sets the integer referenced by sval to the value of the semaphore• If there are processes waiting for the semaphore, POSIX.1b allows setting sval to either 0 or a negative number whose absolute value is equal to the number of waiting processes – ambiguity!• Returns 0 on success and –1 and sets errno on errorUnnamed Semaphore Example#include <semaphore.h>…void main();{…if (sem_init(&my_lock, 1, 1) {perror(“could not initialize my_lock semaphore);…for (i = 1; i < n; ++i)if (childpid = fork()) break;…if (sem_wait (&my_lock) == – 1) {perror (“semaphore invalid); exit (1); }Critical Sectionif (sem_post (&my_lock) == – 1) {perror (“semaphore done”); exit(1); }…}Named Semaphores• Named semaphores can synchronize processes that do not have common ancestors• Have a name, user ID, group ID and permissions just like files do•POSIX.SEM does not require name to appear in file system nor does it specify consequences of having two processes refer to same name• If name begins with a slash (/), two processes (or threads) open the same semaphoresem_openSYNOPSIS#include <semaphore.h>sem_t *sem_open(const char *name, int oflag);sem_t *sem_open(const char *namd, int oflag, mode_t mode, unsigned int value);POSIX.SEM• sem_open establishes a connection between a named semaphore and a sem_t value• sem_open returns a pointer identifying the semaphoresem_open oflag parameter• oflag determines whether sem_open access a previously defined semaphore or creates a new one• If oflag is 0 the semaphore is previously defined


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?