Overview

The purpose of this assignment is to become familiar with the problems involved in synchronizing process access to shared resources; specifically, the coordination of process' critical sections. The UNIX IPC package, in the form of shared memory and semaphores, will be investigated and used as the mechanism for controlling process synchronization.

Activities

• Work your way through the following exercises, demonstrating your knowledge of the material by answering the numbered questions.

• Submit a detailed lab report (one per group). Include:

  • the answers to the numbered questions
  • your final source code
  • output from a sample run

• Complete the programming assignment (Producer/Consumer Bounded Buffer) individually

POSIX Shared Memory Segments

In the previous lab you were introduced to System V IPC facilities: shared memory segments, message queues, and semaphores.

Since System V ("system five") APIs have been around much earlier (since 1980s), many Unix-based system support it. However, newer POSIX implementation provides easier APIs to interact with. Nevertheless, they both work using the same principles.

The following table compares the system calls for shared memory management in System V vs. POSIX

Task	System V	POSIX
Create shared memory	shmget	shm_open
Set memory size	shmget	ftruncate
Attach shared mem to pointer	shmat	mmap
Detach shared mem from pointer	shmdt	munmap
Remove shared memory	shmctl	shm_unlink

Browse its man page to see more details about these new system calls:

man shm_overview     # to see the general description of all the functions
man mmap             # to see the details of a specific system call

Unlike System V facilities which require you use ipcs and ipcrm to inspect and manage the IPC objects, newer POSIX counterpart implements these facilities as a (special) file under /dev/shm. Hence you can manage them (list, remove, rename, etc.) using normal filesystem commands: ls, rm, mv, chmod, etc.

Sample Program 1

[Gist]

API rate limit exceeded for 100.28.66.163. (But here's the good news: Authenticated requests get a higher rate limit. Check out the documentation for more details.)

TIP

The above program runs differently depending how it is invoked from the command line.

• Compile the above sample program twice, first as a "reader" then as a "writer". Be sure to include the librt library, otherwise you will see undefined references on the shm_* functions.

  clang -Wall posix-shm.c -lrt -o reader
  clang -Wall posix-shm.c -lrt -o writer

First run the program as a writer (but don't run the reader yet) and enter a short sentence at the prompt

1. From the command line, enter id command to inspect your account details (uid, gid, groups, etc). What is your UID?
2. Inspect the shared memory details by running ls -l /dev/shm. What is the name and size of your shared memory?

Run the program as a reader and observe the output.

Synchronization Across Multiple Threads

As mentioned in class and in your textbook, concurrent access to shared data presents users with an instance of the Critical Section problem. Recall the main issues involved with process synchronization while studying the following program:

Sample Program 2

[Gist]

API rate limit exceeded for 100.28.66.163. (But here's the good news: Authenticated requests get a higher rate limit. Check out the documentation for more details.)

Perform the following operations and answer the questions:

• Study the sample programs, both versions (C and C++) perform the same task

• Add the necessary code to implement the three TODO items

  • you will need to adjust the function heading for main() and insert code to grab the argument to be stored into the variable loop.

3. What exactly does Sample Program 2 intend to do (i.e. who is responsible for what operations)?
4. Given that, what is the program's expected output?

• compile Sample Program 2
• run the program with increasing loop values, starting from small (e.g. 1000, 10000) to a much larger value (100000, 1000000, ...). For each loop value, run the program multiple times until you observe interesting and unexpected results.

5. Describe the output of Sample 2 as the loop values increase
6. Describe precisely what is happening to produce the observed interesting output.

TIP

Your answer should tie in to the concepts discussed in Chapter 5 — Process Synchronization.

POSIX Semaphores

This lab concerns itself primarily with mechanisms for controlling access to shared resources; specifically, it introduces semaphores. Like shared memory, semaphores are a kernel resource and follow the familiar resource usage pattern: request, use, release. You will also find two variants of implementation: System V and POSIX. The general introduction of POSIX semaphore can be found in sem_overview(7):

man sem_overview

and you will find two variations: named and unnamed semaphores.

• Named semaphores are stored semi permanently in the file system (tmpfs) under /dev/shm and therefore can be referenced using its "filename" and accessed by multiple processes. Hence, accessing the semaphore requires the "open" and "close" calls. Any files under tmpfs are removed at boot time.
• Unnamed semaphores are referenced only by its pointer initialized via sem_init. When an unnamed semaphore is shared among threads of one process, the semaphore gets destroyed when the creating process terminates. On the contrary, when an unnamed semaphore is shared among multiple processes, it must be stored in a shared memory accessible to these processes. Hence the later type is semi permanent.

Task	System V	POSIX (named)	POSIX (unnamed)
Create semaphore	semget	sem_open	sem_init
Decrement value	sem_op	sem_wait	sem_wait
Increment value	sem_op	sem_post	sem_post
Release semaphore	N/A	sem_close	N/A
Remove semaphore	semctl	sem_unlink	sem_destroy

The POSIX call sem_wait() is equivalent to Dijkstra's wait()/down() operation and sem_post() is equivalent to Dijkstra's signal()/up() operation.

The code snippet below demonstrates how to use of these system calls on unnamed semaphores:

sem_t mtx;

// Request (called once)
sem_init(&mtx,
  0, /* Process share mode (0:for threads  non-zero:for processes */
  1  /* initial value */);

// Use (wait and post, called as many times as needed)
sem_wait(&mtx);

/* critical section code here */

sem_post(&mtx);

// Release (called once)
sem_destroy(&mtx);

TIP

The share mode controls the accessibility of the semaphore

• Zero: the semaphore is accessible only to a single process and multiple threads within that process
• Non-zero: the semaphore is accessible across multiple processes

Read the man pages of sem_init (and sem_wait, sem_post, sem_destroy) to find out the more details on these system calls and which header file(s) to include in your code. Remember to use the thread library (-lpthread) when compiling your code.

7. Modify the C version of Sample 2 by adding necessary binary POSIX semaphore (mutex) to correct the issue with concurrent swapping the array contents. Remember to attach the updated source file(s) in your lab report.

IMPORTANT

Carefully place your semaphore operations to allow each swapping operation inside the loop of both main and swapper threads to run concurrently while avoiding race conditions.

C++11 Mutexes

C++11 provides classes that support concurrency and synchronization. Using these classes, it is a trivial to declare and use binary semaphores (mutexes).

#include <mutex>

// Declare and initialize automatically
std::mutex mtx;

mtx.lock();
// Critical section goes here
mtx.unlock();

// Automatic destruction when your program terminates

8. Modify the C++ version of Sample 2 and use C++11 mutex to synchronize the swapping operations. Remember to specify the compiler option -std=c++11 and library option -lpthread to compile your code.

   TIP

   Be sure both threads (main and swapper) use the same mutex!

Synchronization Across Multiple Processes

The following program is similar to Sample 2 above, but it runs two concurrent processes.

Sample Program 3

[Gist]

API rate limit exceeded for 100.28.66.163. (But here's the good news: Authenticated requests get a higher rate limit. Check out the documentation for more details.)

9. Modify Sample 3 and use POSIX binary semaphore to avoid the race conditions in swapping of the array contents.

   • Add a new field of type sem_t in shared_info. This is required to make the semaphore accessible from the shared memory segment.
   • When calling sem_init to initialize the semaphore be sure to pass a non-zero value to its second argument so the semaphore is usable across process boundary.

Programming Assignment (Producer-Consumer)

Write a multi-threaded C (or C++) program that implements a semaphore-based solution to the Producer-Consumer (Bounded Buffer) Problem. The sketch of the semaphore-based solution to this problem can be found in your textbook (Section 5.7.1) as well as in page 60+ The Little Book of Semaphores by Allen Downey.

General requirements

1. The program should have three threads (not processes):

   • The main (default) thread that initializes all the necessary variables, semaphores and also launches two new worker threads below
   • One thread for the producer that "produces" random integers between 1000-9000
   • One thread for the consumer

2. Use POSIX Semaphores (not System V semaphores)

3. The program should parse three integer arguments from the command line (in the following order)

   • Buffer size
   • Producer sleep time (in milliseconds)
   • Consumer sleep time (in milliseconds)

   # buffer size 20,  avg producer sleep 400 ms, avg consumer sleep 1200 ms
   ./a.out 20 400 1200

   The sleep time will be used by C usleep() or C++ sleep_for() inside the worker loop.

4. After launching the new threads, the main thread will repeatedly take one of the following user "commands" from the keyboard to adjust the sleep time of the worker threads.

User input	Action
a	Increase producer sleep time by 250 ms
z	Decrease producer sleep time by 250 ms
s	Increase consumer sleep time by 250 ms
x	Decrease consumer sleep time by 250 ms
q	Prepare to stop

IMPORTANT

Please stick with these five input characters/strings to make it easier for your instructor to run and test your program.

Changing the sleep time allows you to observe the concurrent interactions between the producer and the consumer when they run at different relative speed.

5. Upon receiving the "q" input

   • The main thread will break its loop and join the two threads
   • The producer thread should break out of its loop
   • The consumer thread should continue to run until all the items in the buffer are consumed and then it breaks out of the loop

6. Output format

   • The producer/consumer output should include the 4-digit random integer and the bin number
   • The consumer output should be tabbed out to make it easier to check the correctness of output
   • Output from one "worker" does not get mixed up with the other's (remember that your threads can be interrupted anywhere anytime even in the middle of its print statement)

Sample Output

The following sample output with buffer size 10

Put 1000 into bin  0
                      Get 1000 from bin 0
Put 2052 into bin  1
                      Get 2052 from bin 1
Put 7045 into bin  2
                      Get 7045 from bin 2
Put 4669 into bin  3
Put 5262 into bin  4
                      Get 4669 from bin 3
Put 2751 into bin  5
                      Get 5262 from bin 4
Put 1376 into bin  6
                      Get 2751 from bin 5
Put 6431 into bin  7
Put 6435 into bin  8
                      Get 1376 from bin 6
Put 8478 into bin  9
                      Get 6431 from bin 7
Put 4068 into bin  0
Put 5155 into bin  1
                      Get 6435 from bin 8
Put 7648 into bin  2
                      Get 8478 from bin 9
Put 1276 into bin  3
q
Preparing to quit
                      Get 4068 from bin 0
Put 1427 into bin  4
End of producer
                      Get 5155 from bin 1
                      Get 7648 from bin 2
                      Get 1276 from bin 3
                      Get 1427 from bin 4
                      End of consumer
End of main

Grading Rubrics

Grading Item	Point
Necessary initialization/setup in main thread	1
POSIX semaphores setup and initialization	2
Correct use of semaphores throughout the code	3
Adjust sleep time in main thread	1
Correct sleep time in producer/consumer	1
Producer creates random items in the correct range	1
Producer places items in the right bin	1
Output format follow specs	1
Consumer retrieves items from the right bin	1
Immediate stop of production	1
Consumer stops after retrieving items in buffer	1
Semaphore cleanup after use	1

The same penalty points (compiler warning, memory leaks, code style, code comments) as used in previous assignments will apply.

Extra Credit Options

You have several options to earn more points on this exercise. You may implement one or more of the options below.

Option 1: C++11 (3 pts)

Implement the Producer/Consumer solution using C++11 mutex and condition_variable (to implement "counting semaphore")

Option 2: GUI (4 pts)

Use a GUI frontend to visualize the producer, consumer, and the shared buffer update. You can either

• Use a GUI library which is compatible with C or C++, or
• Write the GUI frontend in a language of your choice and design it to communicate with the C/C++ "backed" using pipe(s) or shared memory.
• Rewrite both the producer/consumer backend logic and the GUI frontend in a language of your choice

Option 3: Rust (4 pts)

Implement Sample 3 in Rust.

Explore the shared_mem crate for managing shared memory. Unlike the libc crate (used in previous lab) that provides unsafe functions (shm___) for managing shared memory segments, the shared_mem crate provides safe functions that comply with Rust borrow checker algorithm.

Refer to the "basic" example linked from the documentation page and learn how to create a shared memory which is automatically protected by a Mutex. Specifically, the mutex/semaphore is builtin into shared memory access.

Then, re-implement Sample Program 3 in Rust using this crate.