Overview

The purpose of this lab is to introduce multi-threaded programming; in particular the mechanisms for thread creation, management, communication and termination. It examines the first essential element of any thread system, execution context (the remaining two elements being scheduling and synchronization).

The documentation refers to the POSIX pthreads API, a standardized run-time library that implements threads. See the online documentation (i.e. man pages) for additional details on the syntax and operation of the library calls described in this lab.

Activities

• This lab is intended as a group project
• The programming assignment at the end should be completed individually
• Submit your lab report including your source code and sample output files.
• Be prepared to demonstrate your program.

Resources

• Reference your class notes and the textbook for basic thread programming concepts.
• See the online documentation (man pages) for additional details on the syntax and operation of thread management calls.

Thread Creation and Execution

A traditional process in a UNIX system is simply a single-threaded program. It has a single thread (or path) of execution, known as the initial thread, that begins by executing main().

Like processes, all threads (with the exception of the initial one executing main()) are spawned from an existing thread. However, unlike a child process which continues execution to the next instruction after fork(), a new thread has to start at a new function, as if it is making a function call. Hence the third argument in the pthread_create() below. The syntax of the library routine that creates a thread is given below:

int pthread_create (
  pthread_t* tid,               // threadid (returned by the function)
  const pthread_attr_t* _attr_  // optional attributes
  void* (*_start_) (void*),     // address of function to execute
  void* _arg_);                 // argument passed to the "start" function

• This call creates a new thread running the user-defined function named start.
• The start() function is passed a single argument arg, of type void*, and returns a value of the same type.

Any optional attributes (e.g. scheduling policy) may be set at creation time. The identifier of the newly created thread is returned in tid. After completion of this function call, the newly created thread will begin executing the function start(), using the argument(s) provided by arg. As usual, the return value of the function call is a status indicator;where a non-zero value means the function failed.

The sample program below demonstrates simple thread creation. Default values are used for the attributes. The function does not take any arguments. Note the use of error-checking for all function calls.

Sample Program 1

[Gist]

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

The pthread_create signature dictates that the thread function do_greeting() take and return an untyped pointer (pointer to void). This design allows the thread function to take and return any type of data (including an array or structure).

Try the following operations and answer the numbered questions:

• start up a terminal session, which provides you with the UNIX command line interface.

• compile and run the C version of Sample Program 1. You will need to link in the pthreads library (i.e. you must compile with -lpthread).

  clang -Wall laa04_a.c -lpthread

1. describe your results (which may not be what you expected).

   WARNING

   To help you understand the thread concept, the above program is intentionally designed to have a bug.

• try inserting a 2-second sleep() into the main() function (after successful thread creation); compile and re-run.

2. again, describe your results and explain your observations.

Thread Suspension and Termination

Similar to UNIX processes, threads have the equivalent of the wait() and exit() system calls:

For process	For thread	Description
wait()	pthread_join()	Block thread
exit()	pthread_exit()	Terminate thread
N/A	pthread_detach()	Detach thread

To instruct a thread to block while waiting for another thread to complete, use the pthread_join() function. This function is also the mechanism used to get a return value from a thread. The function prototype:

int pthread_join (pthread_t thread1, void **value_ptr);

TIP

• Notice that the second argument is a pointer to a pointer variable.
• Unlike wait() whose intent is for a parent process to wait for the completion of its child process, pthread_join() can be called from any thread, i.e. any thread can join on (and hence wait for) any other thread.

This function specifies that the calling thread should block and wait for thread1 to complete execution. The value returned by thread1 will be accessible via the argument value_ptr. In addition to explicitly joining, threads may also use semaphores,conditional waits and other synchronization mechanisms to keep track of when other threads exit.

TIP

Recall that a terminating child process temporarily turns into a "zombie" process until its parent invokes wait(). A similar situation may happen to a terminating thread; when a (joinable) thread is not joined (by another thread) it turns into a "zombie" thread.

Missing the .join() call on a joinable thread in the C++11 code will trigger a runtime exception.

Detached Threads

Sometimes main ("parent") threads have ongoing work to perform, for example, functioning as a work dispatcher. Instead of waiting for a "child" (background) thread to complete and block on pthread_join(), a "parent" can specify that it does not require a return value or any explicit synchronization with a "child" thread. To do this, the parent thread uses the pthread_detach() function. Alternatively, a (child) thread can also detach itself. After the call to detach, there is no thread waiting for the child — it executes independently until termination. The prototype for this function is as follows:

int pthread_detach (pthread_t thread1);

with thread1 representing the identity of the detached thread.

TIP

• When a joinable thread terminates, it will turn into a "zombie" until another thread join it.
• When a detached thread terminates, it will not turn into a "zombie".
• A thread MUST be either joined or detached

The pthread_exit() function causes the calling thread to terminate. Resources are recovered, and a value is returned to the joining thread (if one exists). This "handshake" is similar to how exit code passed by a child via exit(__) is returned/passed to its parent who calls wait(___). To stop its execution, a thread may explicitly call pthread_exit() or it may simply return from its start function.

WARNING

• Invoking pthread_exit() from a thread will terminate only the calling thread
• Invoking exit() from a thread will terminate the entire process

Although it is not strictly required by the system for a C program that you use either join() or detach(), it is good practice because non-detached threads which have exited but have not been joined are equivalent to zombie processes (i.e. their resources cannot be fully recovered). C++11 thread class enforces this policy by throwing an exception of missed one of these calls. Okay, read the this paragraph again, and make a good habit of implementing it.

The sample program below is a functioning multi-threaded program that uses the library functions described above. It may not behave exactly as you might expect. Note: for a simple change of pace, the sample program is written in C++ instead of C (just substitute g++ for gcc as your compiler).

Sample Program 2

[Gist]

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

The C++ version demonstrates a feature that is not directly supported in C: thread functions with multiple arguments. Mimicking this feature in C requires more work:

• you have to pass the address of a structure to the thread function
• inside the thread function, you must typecast the input argument from the untyped pointer to a pointer to the structure

Sample 2 includes some element of randomness to the program that will produce different output every time you run the program. It also shows an example of passing an input argument into two instances of the same the thread function. To avoid sharing conflict, in the C sample each instance is passed a different argument (count1 and count2). The C++ sample passes these values directly as an argument to the thread function.

Before coming up with a conclusion to answer each of the following questions below, you should run the program several times. You may also want to experiment with the following:

• changing the constant 30 and 50 to an extremely bigger number (in the order of hundred thousands).
• changing the two string "Hello" and "World" to longer strings that are easy to identify which thread prints the string.

Try the following operations and answer the numbered questions:

• compile and run Sample Program 2 (both C and C++)

  clang   -Wall            lab04_b.c -lpthread
  clang++ -Wall -std=c++11 lab04_b.cpp -lpthread
  # Try g++ if clang++ does not compile
  # g++ -Wall -std=c++11 lab04_b.cpp -lpthread

3. report your results. Is the output of the program what you would have expected? Describe what causes the observed formatting.

• insert a one-second sleep() into the loop in the do_greeting2() function. Compile and run the modified program.

4. report your results again. Explain why they are different from the results seen in question 3.

• run the modified program again. In another terminal window, examine process state via ps using appropriately chosen options in order to view thread details. Hint: threads are also call light weight processes (LWP)s. Browse the man page of ps and search for "LWP".

5. based on your observations: does pthreads under Linux use the 1-to-1 or the many-to-many thread mapping model? Justify your answer.

Thread Communication

There are two methods used by threaded programs to communicate:

• Use shared memory: global data or dynamically allocated in heap.
• Pass thread-specific information as an argument to each individual thread.

For this purpose, we can use the second method of communication: via the argument value (void *) passed to a thread's start function. The following sample program uses shared memory for communication; it also demonstrates the mechanism of thread-specific arguments to pass each thread unique information.

Sample Program 3

[Gist]

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

Try the following operations and answer the numbered questions:

6. compile the sample programs (both the C and C++) and run it multiple times (you may see some variation between runs). Choose one particular sample run. Describe, trace, and explain the output of the program, i.e. why they differ from one run to another.
7. Explain in your own words how the thread-specific (not shared) data is communicated to the child threads.

Extra Credit: Lab Programming Assignment (Multi-threaded File Server)

A typical server program (apached, sshd, vmware-hostd, ...) spawns multiple copies of its own processes. For instance, the parent web server process behaves like a "dispatcher" that receives a request from a client, dispatches a "worker" process to satisfy the request. By spawning a new worker process, the parent process resumes accepting new requests from other clients, while the worker processes proceed to service their assigned request (potentially blocking while fetching web pages from the disk).

To see a live example of other programs that use this strategy on your own machine, type the following command in EOS and look for parent and child processes with the same name.

# pstree --show-pids --show-parents --unicode | less
ps -fg

The same design technique can be implemented using a multi-threaded program, i.e the parent server receives a new request connection from a client, spawn a new worker thread to service the assigned requests while the main thread in the parent server continues to receive subsequent connection requests.

This mini-programming assignment simulates the thread execution manifested by a file server process.

Program Specifications

Develop a multi-threaded program in C or C++ with the following specifications.

Main thread

The main thread should:

• input a string from the user (simulating the name of a file to access)

• spawn a worker thread and communicate to it the filename entered by the user

• detach the thread

• immediately repeat the input/spawn sequence (i.e. prepare to accept a new file request)

• It should continue to execute until terminated by the user (^C). At that point, your program should print out basic statistics

  • total number of file requests received/serviced

  WARNING

  Be sure to handle the possibility of getting an error in your system calls (library calls) due to signal interruption. Refer to a previous lab how to use the global variable errno to check error code of system/library calls, especially the EINTR error code.

When terminated, your program should cleanup as appropriate and shutdown gracefully. In addition to being correct, your program should be efficient and should execute in parallel. Remember that threads share data — as a rule, all multi-threaded programs should be carefully scrutinized for potential race conditions or "data clobbering" (one thread overwrites shared data used by another).

Worker Threads

Each Worker thread should:

• obtain the simulated filename from the dispatcher

• sleep for a certain amount of time, simulating the time spent performing a file access:

  • with 80% probability, sleep for 1 second. This simulates the scenario that the Worker thread has found the desired file in the disk cache and serves it up quickly.

  • with 20% probability, sleep for 7-10 seconds (randomly). This simulates the scenario that the worker thread has not found the requested file in the disk cache and must wait while it is read in from the hard drive.

  • wake up, print a diagnostic message that includes the name of the file accessed, terminate

It's ok if the display looks somewhat "messy"; that shows true concurrency is occurring.

IMPORTANT

Recall that the goal of using multiple processes or multiple threads is to allow several tasks within an application to run concurrently. Your simulated file server must be designed to handle concurrent requests

• The main thread shall continue accepting new requests without waiting for all the current worker threads to complete.
• Also be aware of the risk of overwriting shared data by the main thread. Carefully design your program so the (most recent) user input does not overwrite the filenames referenced by the worker threads.

WARNING

• Be sure to test your simulated file server with high volume of requests to demonstrate the correctness of your concurrent design. Type in the file names in rapid successions (instead of waiting to type the next filename until the current request completes). Your concurrent threads should not clobber each other's data.
• Be sure to run valgrind on your program to verify no memory leak

Grading Rubrics

Grading Item	Point
Main thread accepts filename	1
Spawn worker thread	1
Pass a copy of filename to worker thread (no filename clobbering)	1
Detach worker thread	1
Worker thread sleep 1 sec with 80% probability	1
Worker thread sleep randomly between 7-10 seconds with 20% prob	1
Worker thread print information about "file retrieval"	1
Main thread prints the total number of requests	1
Concurrent execution between the main thread and all the worker threads	2
Exit gracefully on Ctrl-C	1

Mistake/Bug	Penalty Point
Compiler warning/error	-1 (per violation)
Memory leak	-1 (per violation)

Extra Credits

1. (2 pts) Upon termination, report the average file access time.
2. (2 pts) Upon Ctrl-C, the parent stops accepting new requests, and postpone its own termination until all the worker threads complete their file access operation

TIP

• In order to enable the main thread reading user input to be interrupted, it is highly recommended that you setup the signal handler using sigaction().

• When writing your code for calculating this number, recall the classroom discussion of concurrent access to a (shared) data object. To correctly accumulate the individual thread time values, you will need to ensure that the summation operation is exclusive (i.e. one at a time), so that executing threads do not overwrite each other.

  Hint: this process is called "mutual exclusion" and the object needed to implement it is called a "mutex".

3. (3 pts) Implement a Rust version of the multi-threaded file server