- Forward


Semaphores
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Review
Back SMYC Forward
  • Process:
    • An instance of a program execution
  • Interprocess Communication:
    • Processes can exchange data in a variety of different ways
    • Processes often need to coordinate their activities
Some Other Coordination Mechanisms
Back SMYC Forward
  • Signals:
    • Can be used to notify a process that an event has occurred
  • Files:
    • File locks can be used for limited kinds of coordination
  • Pipes and FIFOs:
    • Are generally used to exchange information but their blocking and signaling behavior can be used for limited kinds of coordination
Basics
Back SMYC Forward
  • Definition:
    • A semaphore is a kernel-maintained non-negative integer that can be operated on by processes using system calls
  • Operations:
    • Setting the value
    • Increasing the value by 1
    • Blocking until the value can be decreased by 1
What Does A Semaphore Mean?
Back SMYC Forward
  • In And Of Itself:
    • It has no specific meaning
  • In Context:
    • Meaning is given to the semaphore based on the by the coordination protocol that uses it
Why Use Semaphores?
Back SMYC Forward
  • Flexibility:
    • Many synchronization protocols can be implemented using semaphores
  • Simplicity:
    • It is relatively easy to prove the correctness of a synchronization protocol implemented using semaphores
  • Portability:
    • Though the syntax may vary from system to system, the mechanism has been implemented on many systems (though we will only consider the POSIX implementation)
Types of POSIX Semaphores
Back SMYC Forward
  • Unnamed:
    • Reside in a region of shared memory
  • Named:
    • Have an associated name and hence can easily be used by unrelated processes
Opening a Named Semaphore: sem_open() sem_open
Back SMYC Forward
sem_t *sem_open(const char *name, int oflag, /* mode_t mode, unsigned value */)
Purpose:
Initialize and open a named semaphore
Details:
name The name of the semaphore
oflag A flag that controls the opening (see below)
mode O_RDONLY, O_WRONLY, or O_RDWR (required iff O_CREAT is set)
value Required only O_CREAT is set
Return The handle for the semaphore on success; SEM_FAILED on error
#include <semaphore.h> semaphore.h

O_CREAT is used to create a semaphore. O_CREAT & O_EXCL is used to create a semaphore but fail if it already exists.

Semaphore Names
Back SMYC Forward
  • Convention:
    • An initial slash followed by one or more non-slash characters
  • Length:
    • Limited to NAME_MAX - 4 characters
Semaphore Handles
Back SMYC Forward
  • Type:
    • A pointer to a sem_t value
  • An Important Restruction:
    • Operations should not be performed on a copy of the pointer (but a child can use the "inherited" references)
Closing a Semaphore: sem_close() sem_close
Back SMYC Forward
int sem_close(sem_t *sem)
Purpose:
Terminate the association between a semaphore and a process (releasing any resources and and decreasing the reference count)
Details:
sem The handle to the semaphore
Return 0 on success; -1 on error
#include <semaphore.h> semaphore.h

Note that sem_close() does not delete the semaphore.

Deleting a Named Semaphore: sem_unlink() sem_unlink
Back SMYC Forward
int sem_unlink(const char *name)
Purpose:
Removes a semaphore and marks it for destruction (once all processes close it)
Details:
name The name of the semaphore
Return 0 on success; -1 on error
#include <semaphore.h> semaphore.h
Persistence of Named Semaphores
Back SMYC Forward
  • Remember:
    • Named semaphores have kernel persistence
  • Implications:
    • You MUST remember to unlink named semaphores
  • Getting a List of Semaphores:
    • ls -l /dev/shm/sem.*
Decrement Operation: sem_wait() sem_wait
Back SMYC Forward
int sem_wait(sem_t *sem)
Purpose:
Attempt to decrease the value of a semaphore by 1 (blocking until it is possible to do so)
Details:
sem A pointer to the semaphore
Return 0 on success; -1 on error
#include <semaphore.h> semaphore.h
Decrement Operation (cont.)
Back SMYC Forward
  • Normal Flow:
    • Decrements the semaphore by 1 and returns immediately if the semaphore has a value greater than 0
    • Otherwise blocks until the value rises above 0 (at which point the semaphore is decremented and the function returns)
  • If Interrupted by a Signal Handler:
    • The function fails with the error EINTR (regardless of whther the SA_RESTART flag was used when the signal handler was installed/established)
Variants of sem_wait()
Back SMYC Forward
  • sem_trywait() sem_trywait
    • If the value of the semaphore is 0 it fails immediately with the error EAGAIN
  • sem_timedwait() sem_timedwait
    • Allows for a limit on the amount of time the call will block
Increment Operation: sem_post() sem_post
Back SMYC Forward
int sem_post(sem_t *sem)
Purpose:
Increase the value of a semaphore by 1 (causing one process that is blocking to stop doing so)
Details:
sem A pointer to the semaphore
Return 0 on success; -1 on error
#include <semaphore.h> semaphore.h
Building Programs which Use Semaphores
Back SMYC Forward
  • Compiling:
    • As before
  • Linking:
    • -pthread
Semaphores for Sequencing
Back SMYC Forward
unixexamples/semaphores/sequence.c
 
An Example of "Alerting" with a Semaphore
Back SMYC Forward
unixexamples/semaphores/taxs1.c
 

Note: The "sender" transmits one bit of information (as in the similar examples that used signals and pipes) by either incrementing the semaphore or not.

Complicating the "Alerting" Example
Back SMYC Forward
  • Recall:
    • In the discussion of signals we made the example more complicated by giving the child another (long) task that the parent did not have to wait for
    • We were unable to create a coordination protocol for this problem
  • The Advantage of Semaphores:
    • The are more flexible than wait()
Complicating the "Alerting" Problem (cont.)
Back SMYC Forward
unixexamples/semaphores/taxs2.c
 

Note: One semaphore is being used to satisfy the sequencing constraint and another is being used for "alerting".

Semaphores for Satisfying Mutual Exclusion
Back SMYC Forward
unixexamples/semaphores/mutex.c
 

Note: The semaphore is initialized to 1 so that whichever process checks first can "enter".

There's Always More to Learn
Back -