TWiki> CS361fall13 Web>Homework9 (revision 4)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(). Ensure that every incoming request is eventually served, all threads are working when there are requests waiting to be served, and no threads are working (using CPU) when there are no requests to be served. Don't worry about coordinating which worker thread gets which request - just make sure wait_for_service_request() doesn't return before the request has been fetched by a worker, and that wait_for_request() doesn't return before a request is ready to be processed.

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. You must ensure that group() is never called twice in a row by a thread of the same type.

Worker Threads 3 (worker3.c)

In the third version, 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)

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 read() or write(). To make the best use of this new technology, design a synchronization scheme that obeys the following rules:

- no more than 8 concurrent read() operations or 8 write() operations - no concurrent mixing of read()/write() operations - if there are both reads and writes waiting, always run the bigger group.

Turn-in instructions

Do not edit the files named *_test.c, and do not use any built-in synchronization operator other than semaphores.

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.

Edit | Attach | Print version | History: r8 | r6 < r5 < r4 < r3 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r4 - 2013-11-11 - 05:08:53 - Main.jakob
Copyright 2016 The Board of Trustees
of the University of
Helping Women Faculty Advance
Funded by NSF