Operating Systems: Virtualization, Concurrency & Persistence/

...

/

Exercise

Exercise

Enhance your understanding by getting hands-on practice ​with this exercise on semaphores!

We'll cover the following...

In this exercise, we’ll use semaphores to solve some well-known concurrency problems. Many of these are taken from Downey’s excellent “Little Book of Semaphores", which does a good job of pulling together a number of classic problems as well as introducing a few new variants; interested readers should check out the Little Book for more fun.

How to run?

Included in this exercise are a number of skeletal code fragments, which you can fill out to solve various synchronization problems. Check them out!

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include "common_threads.h"

//
// Your code goes in the structure and functions below
//

typedef struct __rwlock_t {
} rwlock_t;


void rwlock_init(rwlock_t *rw) {
}

void rwlock_acquire_readlock(rwlock_t *rw) {
}

void rwlock_release_readlock(rwlock_t *rw) {
}

void rwlock_acquire_writelock(rwlock_t *rw) {
}

void rwlock_release_writelock(rwlock_t *rw) {
}

//
// Don't change the code below (just use it!)
// 

int loops;
int value = 0;

rwlock_t lock;

void *reader(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
	rwlock_acquire_readlock(&lock);
	printf("read %d\n", value);
	rwlock_release_readlock(&lock);
    }
    return NULL;
}

void *writer(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
	rwlock_acquire_writelock(&lock);
	value++;
	printf("write %d\n", value);
	rwlock_release_writelock(&lock);
    }
    return NULL;
}

int main(int argc, char *argv[]) {
    assert(argc == 4);
    int num_readers = atoi(argv[1]);
    int num_writers = atoi(argv[2]);
    loops = atoi(argv[3]);

    pthread_t pr[num_readers], pw[num_writers];

    rwlock_init(&lock);

    printf("begin\n");

    int i;
    for (i = 0; i < num_readers; i++)
	Pthread_create(&pr[i], NULL, reader, NULL);
    for (i = 0; i < num_writers; i++)
	Pthread_create(&pw[i], NULL, writer, NULL);

    for (i = 0; i < num_readers; i++)
	Pthread_join(pr[i], NULL);
    for (i = 0; i < num_writers; i++)
	Pthread_join(pw[i], NULL);

    printf("end: value %d\n", value);

    return 0;
}

To compile any one of them (say, one called foo.c):

prompt> gcc -o foo foo.c -Wall -pthread

And then, to run it:

prompt> ./foo

(maybe with some optional arguments)

Each of the following questions provides a code skeleton; your job is to fill in the code to make it work given semaphores. You will be using native semaphores. Good luck!

Questions

  1. The first problem is just to implement and test a solution to the fork/join problem, as described in the text. Even though this solution is described in the text, the act of typing it in on your own is worthwhile; even Bach would rewrite Vivaldi, allowing one soon-to-be master to learn from an existing one. See fork-join.c for details. Add the call sleep(1) to the child to ensure it is working.

  2. Let’s now generalize this a bit by investigating the rendezvous problem. The problem is as follows: you have two threads, each of which is about to enter the rendezvous point in the code. Neither should exit this part of the code before the other enters it. Consider using two semaphores for this task, and see rendezvous.c for details.

  3. Now go one step further by implementing a general solution to barrier synchronization. Assume there are ...