CIS 4307: Threads II

[Condition Variables], [Conditional Critical Regions], [Producer-Consumer with Protected Buffer], [Dining Philosophers], [Copying a file], [Some standard ways of using threads

We have already studied monitors. Here we see how to implement monitors that are going to be shared by threads using locks and condition variables. First we examine the commands we need for using condition variables.

Condition Variables

Here are the basic commands for using conditions.

    #include <pthread.h>
    int pthread_cond_init(pthread_cond_t * cond, const pthread_cond_attr *attr);
	 Initialization of cond. Usually attr is initialized to 
	 the default, pthread_condattr_default.

    #include <pthread.h>
    int pthread_cond_wait(pthread_cond_t * cond, pthread_mutex_t * mutex);
	 When this command is executed the executing thread, which must be
	 holding the specified mutes, it goes to sleep
	 on cond and simultaneously unlocks mutex, thus allowing another
	 thread to execute past a lock on mutex. 

    #include <pthread.h>
    int pthread_cond_timedwait(pthread_cond_t * cond, pthread_mutex_t * mutex, 
		   const struct timespec *abstime);
	 Same as the wait command, but now we have an absolute time
	 so that the thread will never wait for more than timeout.

    #include <pthread.h>
    int pthread_cond_signal(pthread_cond_t * cond);
	 This command is null when no thread is asleep on cond. Otherwise
	 a thread is released from cond. When a thread is released
	 from waiting on a condition variable, it is set to wait on the 
	 mutex associated to the condition variable. This mutex remains locked 
	 until unlockied by the thread executing the signal call.

    #include <pthread.h>
    int pthread_cond_broadcast(pthread_cond_t * cond);
	 This is like signal, but now all threads waiting on the condition
	 are released and compete for the mutex lock. That is, they are 
	 all but one (the one who gets the lock) queued at the lock operation 
	 of the mutex.

    #include <pthread.h>
    int pthread_cond_destroy(pthread_cond_t * cond);
	 It destroys the state associated to the condition variable
	 without releasing its space.
 

Conditional Critical Regions

Using condition variables and mutexes we can implement Conditional Critical Regions. These are atomic operation of the form

WHEN predicate DO action

which means that the action will be executed in mutual exclusion only when the predicate is true (a predicate is an expression that is either true or false). Assuming that mutex is a lock variable and condition is a condition variable, this can be done with

    pthread_mutex_lock(mutex);	// We enter and lock
    while (not predicate)      // while the predicate is not true
       pthread_cond_wait(condition, mutex); // we sleep and open the lock.
    // At this point the predicate is true.
    action;
    pthread_cond_signal(condition); // After the action we signal to see
			 // if some other operation needs to enter
			 // or to continue
    pthread_mutex_unlock(mutex);  // We unlock and exit. This unlock 
			 // is null if the lock is currently held
			 // by the thread released by signal.
 

Note that if 5 threads are waiting on a condition at the time we signal that condition, then only one of these threads is released. It will check its predicate and, if false, it will go back to sleep opening the lock but without waking up another waiting thread. If we want all 5 threads to have a chance to check their predicates then we have to insert the appropriate signal commands or we have to use the pthread_cond_broadcast command which wakes up all threads currently waiting on a condition.

Here is an implementation of readers-and-writers locks due to Kleiman, Shah, and Smaalders: rwl.h and rwl.c.

Producer and Consumer communicating through a Protected Buffer

In this simple example the producer will rush ahead inserting items into the buffer while the consumer takes out a few items. Then the buffer becomes full and the producer and consumer will take turns inserting one item and extracting one item.

Note that in the protected buffer case we have one lock, one condition, and two predicates, pqueuefull and pqueueempty. In all other monitor problems we will have exactly one lock, any number of conditions, and any number of predicates. For example in the case of the Dining Philosophers we could use a condition per philosopher and a single predicate: The current Philosopher is hungry and its neighbors are not eating.

Here we see a "professional level" implementation of protected buffers [but as is does not compile cleanly].

Dining Philosophers

Copying a file

Some standard ways of using threads

• Master and Slaves: A number of activities can be done concurrently. So the program, the master, creates threads to do them, the slaves, and waits for them to complete their work and exit (the master recognises it by using pthread_join), then the master continues.
• Pipeline: We need to perform repeatedly a sequence of independent activities each outputting the input of the next activity. This is the pipeline with corresponding to the various activities. We can implement each stage with a thread.
• Workpile: We have a pile of things to do. Each thing can be done independently of the others. We have a pool of threads available to do the work. Then threads go to the pile, get an element and do it. As result of doing an element new elements may be added to the pile.

  An alternative way of processing the workpile goes as follows. There is a manager of the workpile. In a loop it retrieves an element from the workpile and creates a thread to take care of it. This thread will die when it is done with this element.

  A workpile with pool of threads is more efficient than a workpile with a manager, but it may run into deadlock if one is not careful [imagine that we use a protected bounded buffer to keep track of tickets of the work that needs to be done. Then it is possibile that all the workers try to put a new ticked in an already full buffer].