A)

A solution to avoid race conditions is to use a tool offered by most operating systems: semaphores. A semaphore is a special integer variable that is used for controlling access to shared resources. The PThread library defines a Semaphore object in semaphore.h. There are 3 types of operations defined on a semaphore:

Initialization: In C, this is done by calling the sem_init function. For example the following initializes a shared semaphore (called mutex) to 1.

sem_t mutex = sem_init(&mutex, 0, 1);

Decrement and Wait: The value of the semaphore is decremented and if its value becomes negative, then the thread is blocked. This can be done by calling:

sem_wait(&mutex);

Increment and Signal: The value of the semaphore is incremented and if its value becomes negative or equal to zero, then a thread that was blocked is unblocked.In Java, this can be done by calling:

sem_post(&mutex);

Binary semaphores are simply semaphores that can take on the values 0 and 1.

Modify the file rc.c:

#include

#include

#include //compile and link with -pthread

#include

int global = 0;

sem_t mutex;

void *inc( void *ptr ) {

int i;

for(i = 0; i < 9000000; i++){

sem_wait(&mutex);

global++;

sem_post(&mutex);

}

}

void *dec( void *ptr ) {

int i;

for(i = 0; i < 9000000; i++){

sem_wait(&mutex);

global--;

sem_post(&mutex);

}

}

int main() {

pthread_t thread1, thread2;

sem_init(&mutex, 0, 1);

pthread_create( &thread1, NULL, inc, NULL);

pthread_create( &thread2, NULL, dec, NULL);

pthread_join( thread1, NULL);

pthread_join( thread2, NULL);

sem_destroy(&mutex);

printf("Final global = %d ", global);

exit(0);

}

Compile the program again:

student@Ubuntu:~/labs/lab3$ gcc -pthread rc.c -o rc

Run the program several times again:

student@Ubuntu:~ /labs/lab3 $ ./rc

What are the possible outputs this time? Explain in detail how the use of semaphores guarantees that the critical sections:

global++

global--

wont be accessed concurrently by the two threads.

B)

Using counting semaphores can simplify thread synchronization, in particular, when some resource that has multiple instances.

In the following example, 16 concurrent threads (executing the run function) attempt to access 4 virtual printers. We use a counting semaphore initialized to 4 in order to represent the number of available printers.

Each thread will do the following, forever:

Try and obtain an available printer

Sleep for a random number of seconds (This simulates using the printer.)

Release the printer

Sleep for a random number of seconds (This simulates other actions of a typical thread before needing the printer again.)

Threads will simply be use Decrement and Wait before accessing a printer and Increment and Signal when they have finished using a printer.

Create the file: counting_semaphore.c

#include

#include

#include //compile and link with -pthread

#include

const int NUM_THREADS = 16;

const int NUM_PRINTERS = 4;

sem_t s;

void *run( void *ptr ) {

int tid = (int) pthread_self();

int value;

while(1){

printf("%d needs a printer now! ", tid);

sem_getvalue(&s, &value);

printf("\tsemaphore value = %d ", value);

sem_wait(&s);

printf("%d is printing now! ", tid);

usleep(rand() % 1000);

printf("%d is done printing! ", tid);

sem_getvalue(&s, &value);

printf("\tsemaphore value = %d ", value);

sem_post(&s);

printf("%d is doing something else... ", tid);

usleep(rand() % 1000);

}

}

int main() {

pthread_t threads[NUM_THREADS];

sem_init(&s, 0, NUM_PRINTERS);

srand(time(NULL));

int i;

for(i = 0; i < NUM_THREADS; i++){

pthread_create( &threads[i], NULL, run, NULL);

}

for(i = 0; i < NUM_THREADS; i++){

pthread_join( threads[i], NULL);

}

exit(0);

}

Compile the file:

student@Ubuntu:~/labs/lab3$ gcc

Run the counting_semaphore program for a few seconds. Then press <Ctrl+ C> to stop the program:

student@Ubuntu:~ /labs/lab3 $ ./cs

Copy and paste the output below. Check the output for any inconsistency.

C)

Semaphores can be difficult to use. A monitor is a mechanism offered by programming languages to control access to shared data. A monitor is a module that encapsulates:

Shared data

Procedures that operate on the shared data. Those procedures execute with mutual exclusion, that is, only one thread may be executing a procedure at a time.

Condition variables: represents a condition that must be true for threads to continue execution. Three operations are defined for conditions:

Wait(condition): The current thread is put on a waiting queue if the condition is false.

Signal(condition): A thread that was waiting on this condition is awoken.

Broadcast(condition): All the threads that were waiting on this condition are awoken.

Monitors are closely related to object-oriented programming. However, it is possible to implement monitors in the C language by using locks and conditions from the PThread library.

The Readers/Writers problem

The Readers/Writers problem is described as follows: A data set is shared among a number of concurrent threads of two types:

Readers: only read the data set; they do not perform any updates on it.

Writers: can both read and write the data set.

How do you synchronize access to the data in such a way that:

Multiple readers are allowed to read the data set at a time,

But only one single writer is allowed to update the data set at a time?

The reader/writer problem can be solved using locks (mutexes) and conditions. In the following program, the main function starts 10 readers threads (executing the read() function), and 10 writer threads (executing the write() function) . The program has 2 global variables, activeReadersNumber and activeWritersNumber.

Readers will continuously do the following:

Prepare for reading by using a lock and a condition

Sleep for a random number of seconds (simulates reading)

Execute post-reading operations

Sleep for a random number of seconds (simulates other actions of a typical thread before needing to read again)

Writers will continuously do the following:

Prepare for writing by using a lock and a condition

Sleep for a random number of seconds (simulates writing)

Execute post-reading operations

Sleep for a random number of seconds (simulates other actions of a typical thread before needing to write again)

Create the program reader_writers.c:

#include

#include

#include //compile and link with -pthread

const int NUM_READERS_WRITERS = 10;

pthread_cond_t cond; //condition

pthread_mutex_t mutex; //lock, a.k.a. mutex

int activeWritersNumber;

int activeReadersNumber;

void *read( void *ptr ) {

int tid = (int) pthread_self();

int value;

while(1){

printf( "\tReader %d wants to read! ", tid);

pthread_mutex_lock(&mutex);

while(activeWritersNumber > 0){

printf("\tReader %d is waiting... ", tid);

pthread_cond_wait(&cond, &mutex);

}

++activeReadersNumber;

pthread_mutex_unlock(&mutex);

printf("\tReader %d is reading! ", tid);

printf("Number of active readers: %d, number of active writers: %d ", activeReadersNumber, activeWritersNumber );

usleep(rand() % 1000);

pthread_mutex_lock(&mutex);

--activeReadersNumber;

printf("\tReader %d has finished reading. ", tid);

printf("Number of active readers: %d, number of active writers: %d ", activeReadersNumber, activeWritersNumber );

if(activeReadersNumber == 0){

pthread_cond_signal(&cond);

printf("\tReader %d was the last reader. Notifying one waiting writer.", tid);

}

pthread_mutex_unlock(&mutex);

usleep(rand() % 1000);

}

}

void *write( void *ptr ) {

int tid = (int) pthread_self();

int value;

while(1){

printf("\t\t\tWriter %d wants to write! ", tid);

pthread_mutex_lock(&mutex);

while(activeReadersNumber > 0 || activeWritersNumber > 0 ){

printf("\t\t\tWriter %d is waiting... ", tid);

pthread_cond_wait(&cond, &mutex);

}

++activeWritersNumber;

pthread_mutex_unlock(&mutex);

printf("\t\t\tWriter %d is writing! ", tid);

printf("Number of active readers: %d, number of active writers: %d ", activeReadersNumber, activeWritersNumber );

usleep(rand() % 1000);

pthread_mutex_lock(&mutex);

--activeWritersNumber;

printf("\t\t\tWriter %d has finished writing. Notifying waiting readers and writers. ",tid);

printf("Number of active readers: %d, number of active writers: %d ", activeReadersNumber, activeWritersNumber );

pthread_cond_signal(&cond);

pthread_mutex_unlock(&mutex);

usleep(rand() % 1000); }

}

int main() {

pthread_t readers[NUM_READERS_WRITERS];

pthread_t writers[NUM_READERS_WRITERS];

activeWritersNumber = 0;

activeReadersNumber = 0;

pthread_mutex_init(&mutex, NULL);

pthread_cond_init(&cond, NULL);

srand(time(NULL));

int i;

for(i = 0; i < NUM_READERS_WRITERS; i++){

pthread_create( &readers[i], NULL, read, NULL);

pthread_create( &writers[i], NULL, write, NULL);

}

for(i = 0; i < NUM_READERS_WRITERS; i++){

pthread_join( readers[i], NULL);

pthread_join( writers[i], NULL);

}

exit(0);

}

Compile the program:

student@Ubuntu:~/labs/lab3$ gcc -pthread reader_writers.c -o rw

Run the reader_writers program for a few seconds. Then press <Ctrl+ C> to stop the program:

student@Ubuntu:~ /labs/lab3 $ ./rw

Copy and paste the output below. Check the output. Any problem noticeable? (Hint: starvation is a problem encountered where a process is perpetually denied necessary resources.)