TWiki> CS361fall13 Web>Homework9 (2013-11-15, Main.jakob)EditAttach

Synchronization using Semaphores

In this homework, we solve several synchronization problems using standard semaphores. The homework template, available at svn:// contains skeleton solutions, as well as a number of test-cases. A correct solution passes every test case. Plus, except where noted, your solution must have no loops: for, while, goto or recursive!

To run the tests, type make test in your turn-in folder.

Mutual exclusion (mutex.c)

This is a warm-up exercise.

Reusable Barrier (barrier.c)

This is the problem we discussed in class at some length. Implement first a disposable barrier, then a reusable barrier using semaphores.

Worker Threads 1 (worker1.c)

Here the scenario is a multi-threaded web server. To avoid the overhead of thread creation, and the risk of overloading the CPU, threads are created on startup only. As requests come in, they are served by existing threads as they become available.

Implement the functions wait_for_service() and wait_for_request(). Each function should call pair() once, and synchronize with the other threads such that for every two calls to pair(), there is one worker and one browser. Ordering between the two is not important.

Worker Threads 2 (worker2.c)

In this version, the server has two types of threads - front-end threads that communicate with the remote browser and apply templates to produce the final HTML document, and back-end threads that perform computational tasks and deliver raw content to the front-end thread.

Threads call the functions front_ready() and back_ready() when they have finished processing the last request. These in turn call group() to create a grouping of front/back end threads for the next request.

Every request requires two back-end threads and one front-end. A correct solution must make sure that every group has two back-ends and one front-end. That is, if we print out the thread type for every call to group() and divide the resulting list into groups of three, every group should have two back-ends and one front-end.

Alternating workloads (alternating.c) (5 bonus points)

A new type of storage has been released that offers very fast read and write speeds. However, switching between reading and writing is somewhat slow. Your application has two types of threads - readers and writers. When they are ready to read or write, the call, read_ready() and write_ready(), which in turn call do_read() or do_write(). To make the best use of this new technology, design a synchronization scheme that obeys the following rules:

  • no concurrent mixing of read()/write() operations
  • switch from writing to reading when the number of waiting readers exceed the number of running writers, and vice versa.

Turn-in instructions

Do not edit the files named *_test.c, and do not use any built-in synchronization operator other than semaphores. Feel free to build and use your own operators out of semaphores though.

This is the same as every previous homework. Make sure you run make test on your solution, on your Amazon EC2 VM, before committing your final version.

Topic revision: r8 - 2013-11-15 - 16:45:46 - Main.jakob
Copyright 2016 The Board of Trustees
of the University of
Helping Women Faculty Advance
Funded by NSF