Lab 6: Synchronization with Shared Memory and Semaphores

Goals: This laboratory exercise provides practice with shared memory and process synchronization in Linux, focusing on the Bounded Buffer problem.

Collaboration: You will complete this lab in teams of 2 to 3 as assigned by the instructor.  You may, as always, consult with your classmates on issues of design and debugging.

Steps for This Lab

Experiments with shared memory

1. Copy ~davisjan/csc/213/examples/bounded-buffer-1.c to your account, compile it, and run it a few times.  Describe the output you get.  Review the source code and explain briefly how the output is produced.
2. Remove the sleep statement from the child process, rerun bounded-buffer-1.c, and explain the output produced.
3. Restore the sleep statement to the child process, and remove it from the parent process.  Again, rerun bounded-buffer-1.c, and explain the output produced.
4. Rather than rely upon sleep statements to synchronize the two processes, consider the use of busy-waiting.  In this approach, when the value stored in shared memory is -1, then the parent is allowed to write the next value.  When the value is not -1, the child will read it.
1. Initialize the value stored in shared memory to -1 before the fork operation.  (Why must this be done before the fork?)
2. Replace the sleep statement for the parent with a while statement that waits until the shared memory contains the value -1. When this condition occurs, the parent may write the next square into the shared memory.
3. Replace the sleep statement for the child with a while statement that waits until the shared memory does not contain the value -1.  When this condition occurs, the child may read the next square from the shared memory.  At the end of the child's loop, the value in shared memory should be reset to -1.  (Why?)
5. Copy ~davisjan/csc/213/examples/bounded-buffer-2.c to your account.  Compile it, run it a few times, and review the code to make sure you understand how it works.
6. Explain whether bounded-buffer-2.c will work when there are multiple readers or when there are multiple writers.  In each case, if the code would work, explain why.  If the code would not work, give a timing sequence involving the several readers and/or writers showing what would go wrong.

Experiments with semaphores

7. Copy ~davisjan/csc/213/examples/bounded-buffer-3.c to your account.  Compile it, run it a few times, and review it to be sure you understand how it works.
8. Use the ideas of semaphores, as implemented in bounded-buffer-3.c, in place of the busy-waits in Step 4 to handle the synchronization of the reader and the writer process from bounded-buffer-1.c. Your final program should neither busy-wait nor use sleep statements.
9. With this use of semaphores, explain whether your code in Step 8 will work when there are multiple readers or when there are multiple writers.  In each case, if the code would work, explain why.  If the code would not work, give a timing sequence involving the several readers and/or writers showing what would go wrong.

Experiments with multiple readers and multiple writers

10. Copy ~davisjan/csc/213/examples/bounded-buffer-4.c to your account, compile it, and run it.
11. This program contains a third semaphore, mutex.  Explain the purpose of this semaphore. Specifically, if the mutex semaphore were omitted, give a timing sequence involving the several readers and/or writers should what might go wrong.
12. Program ~davisjan/csc/213/examples/bounded-buffer-4.c prevents any reader from working at the same time as any writer. Assuming that the buffer contains several locations, however, writing to one buffer location should not interfere with reading from another.  That is, the critical section for readers is not the same as the critical section for writers.  Remove the mutex semaphore and add additional semaphores, as needed, so that some reader could work concurrently with some writer (assuming the buffer was neither empty nor completely full---so that both reading and writing make sense.)

A simple pipeline program

Consider the following problem.  A program is to be written to print all numbers between 1 and 1000 (inclusive) that are not (evenly) divisible by either 2 or 3.

The problem is to be solved using three processes (P0, P1, P2) and two one-integer buffers (B0 and B1) as follows:

1. P0 is to generate the integers from 1 to 1000 and write them to B0 one at a time.  After writing 1000 to the buffer, P0 writes the sentinel 0 in the buffer and terminates.
2. P1 is to read successive integers from B0.   If the value is 0, P1 writes the value 0 to B1 and terminates.   If the value is not divisible by 2, the value is written to B1.  Otherwise the value is ignored.
3. P2 is to read successive integers from B1.  If the value is 0, P2 terminates (ensuring that any necessary clean up is done).  If the value is not divisible by 3, it is printed to the screen.  Otherwise, the value is ignored.

13. Write a program to implement P0, P1, and P2 as separate processes.  B0 and B1 are buffers in shared memory.  Use semaphores to coordinate processing.  Access to B0 should be independent of access to B1; for example, P0 could be writing into B0 while P1 is writing into B1.

Work to be Turned In

• Commentary for steps 1-3, 4a, 4c, 6, 9, and 11.
• Programs for steps 4, 8, 12, and 13.  Follow the instructions for submitting programs.
• All is due Tuesdsay, 9 October.

Janet Davis (davisjan@cs.grinnell.edu)