5.3 What are Semaphores?
| A semaphore is a synchronization mechanism that can be used to manage synchronization relationships and implement the access policies. A semaphore is a special kind of variable that can only be accessed by very specific operations. The semaphore is used to help threads and processes synchronize access to shared modifiable memory or manage access to a device or other resource. The semaphore is used as a key to access the resource. This key can only be owned by one process or thread at a time. Whichever task owns the key or semaphore locks the resource for its exclusive use. Locking the resource causes any other task that wishes to use the resource to wait until the resource has been unlocked, making it available again. Once unlocked, the next task waiting for the semaphore is given the semaphore, thus accessing the resource. The next task is determined by the scheduling policy in effect for that thread or process. 5.3.1 Semaphore OperationsAs mentioned earlier, a semaphore can only be accessed by specific operations like an object. There are two operations that can be performed on a semaphore. The P() operation is a decrement operation and the V() operation is an increment operation. If Mutex is the semaphore, then here are the logical implementations of the P(Mutex) and V(Mutex) operations: P(Mutex) if(Mutex > 0) { Mutex--; } else { Block on Mutex; } V(Mutex) if(Blocked on Mutex N processes) { pass on Mutex; } else{ Mutex++; } The actual implementation will be system dependent. These operations are indivisible, meaning once the operation is in progress, it cannot be preempted. If several tasks attempt to make a call to the P() operation, only one task will be allowed to proceed. If the Mutex has already been decremented, then the task will block and be placed in a queue. The V() operation is called by the task that has the Mutex . If other tasks are waiting on the Mutex , it is given to the next task in the queue. If no tasks are waiting, then the Mutex is incremented. Semaphore operations can go by other names :
The value of the semaphore will depend on the type of semaphore it is. There are several types of semaphores. A binary semaphore will have the value 0 or 1. A counting semaphore will have some non-negative integer value. The POSIX standard defines several types of semaphores. These semaphores are used by processes or threads. Table 5-1 lists the types of semaphores. The table also lists some of their basic operations. Table 5-1. Semaphore Types Defined by the POSIX Standard and Their Use by Threads and/or Processes
Any operating system that is compliant with the Single UNIX Specification or POSIX Standard will supply an implementation of these semaphores. They are a part of the libpthread library and the functions are declared in the pthread.h header. 5.3.2 Mutex SemaphoresThe POSIX standard defines a mutex semaphore used by threads and processes of type pthread_mutex_t . This mutex provides the basic operations necessary to make it a practical synchronization mechanism:
Table 5-2 lists the pthread_mutex_t functions that are used to perform these basic operations. The initialization process allocates memory required to hold the mutex semaphore and give the memory some initial values. For a binary semaphore, its initial value will be 0 or 1. If it's a counting semaphore, its initial value is a non-negative number that represents the number of resources available. It can be used to represent the request limit a program is capable of processing in a single session. Unlike regular variables, there is no guarantee that the initialization operation of a mutex will occur. After calling the initialization operation, take precautions to ensure that the mutex was initialized (i.e., checking the return value or checking the errno value). The system shall fail to create the mutex if the space set aside for mutexes has been used, the number of allowable semaphores will be exceeded, the named semaphore already exists, or there is some other memory allocation problem. Table 5-2. pthread_mutex_t Functions
Similar to a thread, the Pthread mutex has an attribute object that encapsulates all the attributes of the mutex. This mutex attribute will be discussed later. It can be passed to the initialization function, creating a mutex with attributes of those set in the mutex object. If no attribute object is used, the mutex will be intialized with default values. The pthread_mutex_t is initialized as unlocked and private. A private mutex is shared between threads of the same process. A shared mutex is shared between threads of multiple processes. If default attributes are to be used, the mutex can be initialized statically for statically allocated mutex objects by using the macro: pthread_mutext Mutex = PTHREAD_MUTEX_INITIALIZER; This method uses less overhead but performs no error checking. A mutex can be owned or unowned. The request ownership operation grants ownership of the mutex to the calling process or thread. Once the mutex is owned, the thread or process has exclusive access to the resource. If there is any attempt to own the mutex (by calling this operation) by any other processes or threads, they are blocked until the mutex is made available. Releasing the mutex causes the next process or thread that has blocked on this mutex to unblock and obtain ownership of the mutex. With pthread_mutex_lock() , the thread granted ownership of a given mutex is the only thread that can release the mutex. A timed version of this function is also available. In that case, if the mutex is owned the process or thread will wait for some specified period of time. If the mutex is not released in that time interval, the process or thread will continue executing. The try ownership operation tests the mutex to see if it is already owned. If owned, the function returns some value indicating that. The advantage of this operation is the thread or process is not blocked if the mutex is owned. It will be able to continue executing. If the mutex is not owned, then ownership is granted. The destruction operation frees the memory associated with the mutex. The memory cannot be destroyed or closed if it is owned or a thread or process is waiting for the mutex. 5.3.2.1 Using the Mutex Attribute ObjectThe pthread_mutex_t has an attribute object used in a similar way as the thread attribute. The attribute object encapsulates all the attributes of a mutex object. Once initialized, it can be used by multiple mutex objects when passed to the pthread_mutex_init() function. The mutex attribute defines several functions used to set these attributes: priority ceiling, protocol, and type. These functions and other attribute functions are listed in Table 5-3 with a brief description. Table 5-3. pthread_mutex_t Attribute Object Functions
The most interesting of the attributes is setting whether the mutex will be private or shared. Private mutexes are only shared among threads of the same process. It can be declared as global or a handle can be passed between threads. Shared mutexes are used by any threads that have access to the memory in which the mutex is located. This includes threads of different processes. Figure 5-5 contrasts the idea of private and shared mutexes between different processes. If threads of different processes are to share a mutex, it must be allocated in memory shared between processes. POSIX defines several functions used to allocate shared memory between objects using memory-mapped files and shared memory objects. Mutexes between processes can be used to protect critical sections that access files, pipes, shared memory, and devices. Figure 5-5. Private and shared mutexes. 5.3.2.2 Using Mutex Semaphores to Manage Critical SectionsMutexes can be used to manage critical sections of processes and threads in order to control race conditions. Mutexes avoid race conditions by serializing access to the critical section. Example 5.1 shows two threads. Mutexes are used to protect their critical sections. Example 5.1 Using mutexes to protect critical sections of threads. // ... pthread_t ThreadA,ThreadB; pthread_mutex_t Mutex; pthread_mutexattr_t MutexAttr; void *task1(void *X) { pthread_mutex_lock(&Mutex); // critical section of code pthread_mutex_unlock(&Mutex); return(0); } void *task2(void *X) { pthread_mutex_lock(&Mutex); // critical section of code pthread_mutex_unlock(&Mutex); return(0); } int main(void) { //... pthread_mutexattr_init(&MutexAttr); pthread_mutex_init(&Mutex,&MutexAttr); //set mutex attributes pthread_create(&ThreadA,NULL,task1,NULL); pthread_create(&ThreadB,NULL,task2,NULL); //... return(0); } In Example 5.1, ThreadA and ThreadB have critical sections protected by their use of Mutex . Example 5.2 shows how mutexes can be used to protect the critical sections of currently executing processes. Example 5.2 Mutexes used to protect critical sections. //... int Rt; pthread_mutex_t Mutex1; pthread_mutexattr_t MutexAttr; int main(void) { //... pthread_mutexattr_init(&MutexAttr); pthread_mutexattr_setpshared(&MutexAttr, PTHREAD_PROCESS_SHARED); pthread_mutex_init(&Mutex1,&MutexAttr); if((Rt = fork()) == 0){ // child process pthread_mutex_lock(&Mutex1); //critical section pthread_mutex_unlock(&Mutex1); } else{ // parent process pthread_mutex_lock(&Mutex1); //critical section pthread_mutex_unlock(&Mutex1); } //... return(0); } In Example 5.2, it is important to note that the mutex has been initialized as shared by calling: pthread_mutexattr_setpshared(&MutexAttr,PTHREAD_PROCESS_SHARED); This allows Mutex to be shared by threads of different processes. Once fork() is called, the child process and parent process can protect their critical section with Mutex . Their critical sections will contain some resource shared by both processes. 5.3.3 Read “Write LocksMutex semaphores are used to manage a critical section by serializing entry to that section. Only one thread or process is permitted to enter the critical section at a time. With read-write locks , multiple threads are allowed to enter the critical section if they are to read the shared memory only. Therefore, any number of threads can own a read-write lock for reading. But if multiple threads are to write or modify the shared memory, only one thread is given access. No other threads are allowed to enter the critical section if one thread is given exclusive access to write to the shared memory. This can be used when applications more often read data than write data. If the application has multiple threads, mutex exclusion can be extreme. The performance of the application can benefit by allowing multiple reads. The POSIX standard defines a read-write lock of type pthread_rwlock_t . Similar to mutex semaphores, the read-write locks have the same operations. Table 5-4 lists the read-write lock operations. The difference between regular mutexes and read-write mutexes is their locking request operations. Instead of one locking operation there are two: pthread_rwlock_rdlock() pthread_rwlock_wrlock() pthread_rwlock_rdlock() obtains a read-lock and pthread_rwlock_wrlock() obtains a write lock. If a thread requests a read lock, it is granted the lock as long as there are no threads that hold a write lock. If so, the calling thread is blocked. If a thread request a write lock, it is granted as long as there are no threads that hold a read lock or a write lock. If so, the calling thread is blocked. The read-write lock is of type pthread_rwlock_t . This type also has an attribute object that encapsulates its attributes. The attribute functions are listed in Table 5-5. Table 5-4. Read “Write Lock Operations
The pthread_rwlock_t can be private between threads or shared between threads or different processes. 5.3.3.1 Using Read-Write Locks to Implement Access PolicyRead-write locks can be used to implement an access policy, namely CREW. Several tasks can be granted concurrent reads but only one task is granted write access. Using read-write locks will not permit concurrent reads to occur with the exclusive write. Example 5.3 contains tasks using read-write locks to protect critical sections. Table 5-5. Attribute Object Functions for pthread_rwlock_t
Example 5.3 Threads using read-write locks. //... pthread_t ThreadA,ThreadB,ThreadC,ThreadD; pthread_rwlock_t RWLock; void *producer1(void *X) { pthread_rwlock_wrlock(&RWLock); //critical section pthread_rwlock_unlock(&RWLock); return(0); } void *producer2(void *X) { pthread_rwlock_wrlock(&RWLock); //critical section pthread_rwlock_unlock(&RWLock); } void *consumer1(void *X) { pthread_rwlock_rdlock(&RWLock); //critical section pthread_rwlock_unlock(&RWLock); return(0); } void *consumer2(void *X) { pthread_rwlock_rdlock(&RWLock); //critical section pthread_rwlock_unlock(&RWLock); return(0); } int main(void) { pthread_rwlock_init(&RWLock,NULL); //set mutex attributes pthread_create(&ThreadA,NULL,producer1,NULL); pthread_create(&ThreadB,NULL,consumer1,NULL); pthread_create(&ThreadC,NULL,producer2,NULL); pthread_create(&ThreadD,NULL,consumer2,NULL); //... return(0); } In Example 5.3, four threads are created. Two threads are producers , ThreadA and ThreadC , and two threads are consumers, ThreadB and ThreadD . All the threads have a critical section and each section is protected with the read “write lock RWLock . As mentioned, ThreadB and ThreadD can enter their critical sections concurrently or serially but neither thread can enter their critical sections if either ThreadA or ThreadC is in theirs. ThreadA and ThreadC cannot enter their critical sections concurrently. Table 5-6 shows part of the decision table for Example 5.3. Table 5-6. Part of the Decision Table for Example 5.3
5.3.4 Condition VariablesA condition variable is a semaphore used to signal an event has occurred. One or more processes or threads can wait for the signal sent by other processes or threads once the event has taken place. Some make a distinction between condition variables and the mutex semaphores discussed. The purpose of the mutex semaphore and read “write locks is to synchronize data access whereas condition variables are typically used to synchronize the sequence of operations. W. Richard Stevens, in his book UNIX Network Programming , states it best: "Mutexes are for locking and cannot be used for waiting ." In Program 4.6, our consumer thread contained a busy loop: 15 while(TextFiles.empty()) 16 {} The consumer thread looped until there were items in the TextFiles queue. This can be replaced by a condition variable. The producer can signal the consumer that items have been inserted into the queue. The consumer can wait until it receives the signal then continue to process the queue. The condition variable is of type pthread_cond_t . These are the types of operations it can perform:
The initialize and destroy operations work in a similar manner as the other mutexes. Table 5-7 lists the functions for the pthread_cond_t that implement these operations. Table 5-7. Functions for the pthread_cond_t that Implement Condition Variables Operations
Condition variables are used in conjunction with mutexes. If a thread or process attempts to lock a mutex, we know that it will block until the mutex is released. Once unblocked, it obtains the mutex then continues. If a condition variable is used, it must be associated with a mutex. //... pthread_mutex_lock(&Mutex); pthread_cond_wait(&EventMutex,&Mutex); //... pthread_mutex_unlock(&Mutex); A task attempts to lock a mutex. If the mutex is already locked then the task will block. Once unblocked, the task will release the mutex, Mutex , while it waits on the signal for the condition variable, EventMutex . If the mutex is not locked, it will release the mutex and wait indefinitely. With a timed wait, the task will only wait for a specified period of time. If the time expires before the task is signaled, the function will return an error. It will then reacquire the mutex. The signal operation causes a task to signal to another thread or process that an event has occurred. If a task is waiting for that condition variable, it will be unblocked and given the mutex. If there are several tasks waiting for the condition variable, only one will be unblocked. The tasks will be waiting in a queue and unblocked according to the scheduling policy. The broadcast operation signals all the task waiting for the condition variable. If multiple tasks are unblocked, the tasks shall compete for the ownership of the mutex according to a scheduling policy. In contrast to the wait operation, the signaling task is not required to own the mutex, although it is recommended. The condition variable also has an attribute object. Table 5-8 lists the functions of the attribute object with a brief description. 5.3.4.1 Using Condition Variables to Manage Synchronization RelationshipsThe condition variable can be used to implement the synchronization relationships mentioned earlier: start-to-start (SS), finish-to-start (FS), start-to-finish (SF), and finish-to-finish (FF). These relationships can exist between threads of the same processes or different processes. Examples 5.4 and 5.5 contain examples of how to implement an FS and FF synchronization relationship. There are two mutexes used in each example. One mutex is used to synchronize access to the shared data and the other mutex is used to synchronize execution of code. Example 5.4 FS synchronization relationship between two threads. //... float Number; pthread_t ThreadA,ThreadB; pthread_mutex_t Mutex,EventMutex; pthread_cond_t Event; void *worker1(void *X) { for(int Count = 1;Count < 100;Count++){ pthread_mutex_lock(&Mutex); Number++; pthread_mutex_unlock(&Mutex); cout << "worker1: number is " << Number << endl; if(Number == 50){ pthread_cond_signal(&Event); } } cout << "worker 1 done" << endl; return(0); } void *worker2(void *X) { pthread_mutex_lock(&EventMutex); pthread_cond_wait(&Event,&EventMutex); pthread_mutex_unlock(&EventMutex); for(int Count = 1;Count < 50;Count++){ pthread_mutex_lock(&Mutex); Number = Number + 20; pthread_mutex_unlock(&Mutex); cout << "worker2: number is " << Number << endl; } cout << "worker 2 done" << endl; return(0); } int main(int argc, char *argv[]) { pthread_mutex_init(&Mutex,NULL); pthread_mutex_init(&EventMutex,NULL); pthread_cond_init(&Event,NULL); pthread_create(&ThreadA,NULL,worker1,NULL); pthread_create(&ThreadB,NULL,worker2,NULL); //... return(0); } Table 5-8. Functions of the Attribute Object for the Condition Variable of Type pthread_cond_t
In Example 5.4, the FS synchronization relationship is implemented. ThreadA cannot finish until ThreadB starts. ThreadA signals to ThreadB once Number has a value of 50 . It can now continue execution until finished. ThreadB cannot start its computation until it gets a signal from ThreadA . ThreadB uses the EventMutex with the condition variable Event . Mutex is used to synchronize write access to the shared data Number . A task can use several mutexes to synchronize different critical sections and synchronize different events. Example 5.5 contains an implementation of a FF synchronization relationship. Example 5.5 FF synchronization relationship between two threads. //... float Number; pthread_t ThreadA,ThreadB; pthread_mutex_t Mutex,EventMutex; pthread_cond_t Event; void *worker1(void *X) { for(int Count = 1;Count < 10;Count++){ pthread_mutex_lock(&Mutex); Number++; pthread_mutex_unlock(&Mutex); cout << "worker1: number is " << Number << endl; } pthread_mutex_lock(&EventMutex); cout << "worker1 done now waiting " << endl; pthread_cond_wait(&Event,&EventMutex); pthread_mutex_unlock(&EventMutex); return(0); } void *worker2(void *X) { for(int Count = 1;Count < 100;Count++){ pthread_mutex_lock(&Mutex); Number = Number * 2; pthread_mutex_unlock(&Mutex); cout << "worker2: number is " << Number << endl; } pthread_cond_signal(&Event); cout << "worker2 done now signalling " << endl; return(0); } int main(int argc, char *argv[]) { pthread_mutex_init(&Mutex,NULL); pthread_mutex_init(&EventMutex,NULL); pthread_cond_init(&Event,NULL); pthread_create(&ThreadA,NULL,worker1,NULL); pthread_create(&ThreadB,NULL,worker2,NULL); //... return(0); } In Example 5.5, ThreadA cannot finish until ThreadB finishes. ThreadA must iterate through the loop 10 times, where ThreadB must iterate through the loop only 100 times. ThreadA will complete its iterations before ThreadB but will wait until ThreadB signals that it is done. SS and SF can be implemented in a similar manner. These techniques can easily be used to synchronize order of execution between processes.  |
EAN: 2147483647
Pages: 133