Semaphore-Hw

Semaphore HW Problems

A select few that were interesting.

Barrier

Make a barrier struct and implementation that enforces that all threads must get to the barrier point before any proceed past it.

// If done correctly, each child should print their "before" message
// before either prints their "after" message. Test by adding sleep(1)
// calls in various locations.

// You likely need two semaphores to do this correctly, and some
// other integers to track things.

typedef struct __barrier_t {
    sem_t phase_1;
    sem_t lock;
    int finished;
    int num_threads;
} barrier_t;


// the single barrier we are using for this program
barrier_t b;

void barrier_init(barrier_t *b, int num_threads) {
    sem_init(&b->phase_1, 0, 0); // condition var
    sem_init(&b->lock, 0, 1); // mutex
    b->finished = 0;
    b->num_threads = num_threads;
}

void barrier(barrier_t *b) {
    sem_wait(&b->lock);
    b->finished++;
    sem_post(&b->lock);
    while (b->finished < b-> num_threads) {
        sem_wait(&b->phase_1);
    }
    sem_post(&b->phase_1);
}

//
// XXX: don't change below here (just run it!)
//
typedef struct __tinfo_t {
    int thread_id;
} tinfo_t;

void *child(void *arg) {
    tinfo_t *t = (tinfo_t *) arg;
    printf("child %d: before\n", t->thread_id);
    barrier(&b);
    printf("child %d: after\n", t->thread_id);
    return NULL;
}


// run with a single argument indicating the number of
// threads you wish to create (1 or more)
int main(int argc, char *argv[]) {
    assert(argc == 2);
    int num_threads = atoi(argv[1]);
    assert(num_threads > 0);

    pthread_t p[num_threads];
    tinfo_t t[num_threads];

    printf("parent: begin\n");
    barrier_init(&b, num_threads);

    int i;
    for (i = 0; i < num_threads; i++) {
	t[i].thread_id = i;
	Pthread_create(&p[i], NULL, child, &t[i]);
    }

    for (i = 0; i < num_threads; i++)
	Pthread_join(p[i], NULL);

    printf("parent: end\n");
    return 0;
}

Reader Writer Lock

Make a basic RwLock as described in Chapter 31.

typedef struct __rwlock_t {
    sem_t lock;
    sem_t writelock;
    int readers;
} rwlock_t;


void rwlock_init(rwlock_t *rw) {
    sem_init(&rw->lock, 0, 1);
    sem_init(&rw->writelock, 0, 1);
    rw->readers = 0;
}

void rwlock_acquire_readlock(rwlock_t *rw) {
    // enter crit section
    sem_wait(&rw->lock);

    rw->readers++;
    // if this is the first (current) reader,
    // then make sure we wait for any writers to finish!
    if (rw->readers == 1)
        sem_wait(&rw->writelock);

    // exit crit section
    sem_post(&rw->lock);
}

void rwlock_release_readlock(rwlock_t *rw) {
    // enter crit section
    sem_wait(&rw->lock);

    rw->readers--;
    // if this is the last (current) reader,
    // then make sure we wake any writers
    if (rw->readers == 0)
        sem_post(&rw->writelock);

    // exit crit section
    sem_post(&rw->lock);
}

void rwlock_acquire_writelock(rwlock_t *rw) {
    sem_wait(&rw->writelock);
}

void rwlock_release_writelock(rwlock_t *rw) {
    sem_post(&rw->writelock);
}

Reader Writer Lock without Starvation

Now improve it so that readers don't starve writers.

typedef struct __rwlock_t {
    sem_t lock_1;
    sem_t lock_2;
    sem_t writelock;
    sem_t readlock;
    int readers; // num active readers
    int writers; // num waiting writers
} rwlock_t;


void rwlock_init(rwlock_t *rw) {
    sem_init(&rw->lock_1, 0, 1);
    sem_init(&rw->lock_2, 0, 1);
    sem_init(&rw->writelock, 0, 1);
    // NEW: condition var for new reader
    sem_init(&rw->readlock, 0, 0);
    rw->readers = 0;
    rw->writers = 0;
}

void rwlock_acquire_readlock(rwlock_t *rw) {
    // NEW: let writers go first
    while (rw->writers > 0) {
        printf("waiting until %d writers go\n", rw->writers);
        sem_wait(&rw->readlock);
    }
    sem_post(&rw->readlock);

    // enter crit section
    sem_wait(&rw->lock_1);

    rw->readers++;
    // if this is the first (current) reader,
    // then make sure we wait for any writers to finish!
    if (rw->readers == 1)
        sem_wait(&rw->writelock);

    // exit crit section
    sem_post(&rw->lock_1);
}

void rwlock_release_readlock(rwlock_t *rw) {
    // enter crit section
    sem_wait(&rw->lock_1);

    rw->readers--;
    // if this is the last (current) reader,
    // then make sure we wake any writers
    if (rw->readers == 0)
        sem_post(&rw->writelock);

    // exit crit section
    sem_post(&rw->lock_1);
}

void rwlock_acquire_writelock(rwlock_t *rw) {
    // NEW: track new writer requested
    sem_wait(&rw->lock_2);
    rw->writers++;
    sem_post(&rw->lock_2);

    sem_wait(&rw->writelock);
}

void rwlock_release_writelock(rwlock_t *rw) {
    // NEW: track writer finished, signal to others waiting on less writers
    sem_wait(&rw->lock_2);
    rw->writers--;
    sem_post(&rw->writelock);
    sem_post(&rw->readlock);
    sem_post(&rw->lock_2);
}