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

Condition Variables, as defined in the Pthreads package, can be used to implement simple forms of monitors. As you recall, a condition variable is used within a monitor to allow a process to sleep when unable to carry out an intended monitor operation. For example if a producer tries to put a new element in the buffer while the buffer is full, it will have to wait until some space becomes available. The wait takes place on a condition variable. When the wait is executed the buffer's mutex is opened to allow some other thread to get into the monitor, or a thread already in the monitor and ready to run, if it exists, is allowed to run.

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

Here we see a solution to the problem of implementing a Producer and Consumer communicating through a protected Buffer in this directory. [compiled with cc -o pqueuepmain pqueuepmain.c pqueuep.c queuep.c -threads
or
gcc -Wall -o pqueuepmain pqueuepmain.c pqueuep.c queuep.c -lpthread
]

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

You all have seen the Dining Philosopher problem. Here you see a solution using threads and condition variables. It does not suffer of deadlocks, but there is the danger of livelocks. The code is in this directory.

Copying a file

The obvious way to copy a file "source.dat" to a file "target.dat" is to read a buffer from one and to write it to the other. An alternative way, taking advantage of overlap between read and write operations when using two buffers, is in terms of threads and conditional critical regions. Here is the code of this program.

Some standard ways of using threads

Here are some standard ways of using threads:

ingargio@joda.cis.temple.edu