florida The Pthread Library and Thread Synchronization questions

COP 4610Homework 5
The Pthread Library and Thread Synchronization (Ch. 5)
Instructor: Dr. Ionut Cardei
This homework has several easy questions plus 2 programming problems.
Submission Instructions

Write the answers in a new Word file named h5.doc, in the order given in this document. At the
end, convert this file to PDF format and upload the PDF file and the source files on Canvas.

Write your name at the beginning of this new file.

Write a heading identifying each problem number before writing the answer.

Develop all programs in C or C++, as required, on the Linux VM you installed for Homework 0.
Solutions in other languages or for another operating system are not accepted and will receive
ZERO CREDIT.

Make sure the solutions’ source code in document h5.doc is properly indented and with meaningful
comments. Syntax highlighting is not required, although it makes the code more readable. In
general you should want the grader to have no trouble reading your code. Check out
http://hilite.me/.

Following the source code for each coding problem, paste in h5.doc a screenshot showing your
program output in the shell window. The screenshot should include the entire Linux VM guest
window. There is no need to include your entire Windows (host OS) desktop.

Convert file h5.doc to PDF. Upload the h5.pdf document on Canvas by clicking on the homework
link.

Also upload the source C/C++ files (with extensions .c, .cc, .c++) for the programming problems.
Read the pthreads tutorial at: https://computing.llnl.gov/tutorials/pthreads/
Compile your programs with the -lpthread option to link with the pthread library:
gcc -o program program.c -lpthread
(assuming here the program’s source name is ‘program.c’ and the executable’s name is ‘program’)
Grading Rubric:
For each programming problem its points are split according to this:
50%: algorithm and synchronization:

correct synchronization: no race conditions, no deadlock, no starvation, no busy waiting

correct result computed by the program and correct program behavior

followed all program requirements
20%: coding:

correct use of the pthread API




no compilation errors
no runtime errors
proper error checking for API calls when errors are possible.
checking for incorrect program input parameters: terminal input or command line arguments
passed to main(argc, argv), where specified
15%: programming style, as seen in the book code examples:

proper indentation

clear code and no obfuscation

meaningful and non-trivial comments explaining key parts of the programs

meaningful variable, parameter and function identifiers

correct use of {,}, (, ), [, ].
15%: screenshot
IMPORTANT NOTE ON ACADEMIC MISCONDUCT:
Keep in mind that copying code from the internet or from a colleague constitutes academic misconduct.
It is quite easier for the grader to identify code copied from the web or other students.
Submit your own work.
Participate on the Homework 5 Q&A Forum. Posting non-trivial questions/answers also counts towards
the Participation points.
=========================================================================
1. – 30 points
Answer these questions:
a) On a single-CPU system, under what circumstances does a multithreaded program using
kernel threads provide better performance (such as faster execution time) compared to a singlethreaded solution (that does not use asynchronous or event-based programming) ?
Explain with general principles.
Give TWO example applications.
b) A new operating system provides a synchronization API and a library for user-level programs (i.e.
like the pthread) for which the mutex lock and unlock operation are implemented with test_and_set
like this:
void mutex_lock(mutex* plock) {
while (test_and_set(plock)) {
};
}
void mutex_unlock(mutex* plock) {
*plock = false;
}
Is this implementation of mutex synchronization correct for use in general purpose user-level
applications?
What could go wrong ?
It helps to think of an example application, like the bounded-buffer problem or the dining philosophers.
c) On a running Linux kernel (version > 2.6) at some point the thread_info.preempt_count
field for a kernel task we call A is equal to 2. (Linux kernel synchronization is discussed in the
textbook).
Answer these questions:
c1) Is task A currently preemptable? Explain.
c2) What is new value of thread_info.preempt_count field for task A after it acquires a
new lock ? Explain.
c3) What is the condition for kernel task A to be safely interruptible ?
c4) Assuming that all locks held by task A are spinlocks, how many CPUs are on that computer ?
2. M-Section – 35 %
We define an m-section to be a sequence of code that can be run concurrently by maximum m threads.
There are n threads in a process. Each thread executes a thread function doWork() that calls
doCriticalWork() in an infinite loop. Function doCriticalWork() requires that at most m threads run it
concurrently. The enter() and leave() functions are used to limit the number of threads within the msection to a maximum of m and are the only functions that deal with synchronization. The pseudo-code
algorithm for the thread function is this:
void doWork(…) {
while (true) {
enter(…);
// limit access to m threads
// execute m-section
doCriticalWork(…);
leave(…);
// run by max. m threads
// leave m-section
// do more work
}
}
Function enter() returns immediately only if there are less than m threads in the m-section. Otherwise,
the calling thread will be blocked. A thread calls leave() to indicate it has finished the m-section. If
there was another thread blocked (in enter()) waiting to enter the m-section, that thread will now be
resumed and allowed to continue, since there are now less than m threads remaining in the m-section.
a) Write a C program called msection-sem.c using the pthread library that implements the algorithm
above. For the enter() and leave() functions use only one shared semaphore for synchronization. This is
actually very easy if you know how a counting semaphore works. Write the enter() and leave()
functions so that they are reusable, i.e. not depending on global variables. Declare any necessary shared
and global variables as needed and also specify the parameters for the three functions.
Declare M as a global integer variable and hard-code its value to 3. The doCriticalWork() function
within the m-section must print the current thread id and the number of threads currently in the msection to the terminal using printf(). The main() function should create and start N=10 threads that call
doWork().
Use the pthread library and the POSIX semaphore API from the semaphore.h header file.
Include a screenshot with the program running.
b) Write a C program called msection-condvar.c using the pthread library that implements the
algorithm above. The enter() and leave() functions must use only one condition variable and one or
more mutexes for synchronization. Do not use semaphores. Write the enter() and leave() functions so
that they are reusable, i.e. not depending on global variables. Declare any necessary shared and global
variables as needed and also specify the parameters for the three functions.
Declare M as a global integer variable and hard-code its value to 3. The doCriticalWork() function
within the m-section must print to the terminal using printf() the current thread id and the number of
threads currently in the m-section. The main() function should create and start N=10 threads that call
doWork().
Use the pthread library and the API declared in the pthread.h header file.
Include a screenshot with the program running.
3. Barrier – 35%
a) Implement a barrier for pthreads in C++ using pthread condition variables and mutexes in a file
called barrier.cc.
Consider a process with N running threads. During their execution, all threads call repeatedly the
barrier’s wait() method. For the 1st, 2nd, …, (N-1)th call, the wait() function blocks (suspends) the calling
thread. The Nth thread that calls this function will unblock all suspended threads and then will return.
All threads that were previously blocked in wait() will now return from wait() and will resume their
execution. They will continue until their next call to the barrier’s wait() method.
In effect, the slowest thread will determine the overall progress of the application.
Note that the identity and type of thread are irrelevant in deciding to suspend it or “raise” the barrier in
wait(): only the Nth call to wait() will resume all processes, while all other call to wait() will suspend
the caller thread.
Here is an illustration of a barrier from the Intro to Parallel Computing guide from LLNL:
(Analogy: imagine a real-world barrier on a highway. Cars that arrive at the barrier have to stop and
wait for the barrier to be raised. For each Nth car that arrives, the barrier is raised and all N cars waiting
can now proceed. Right after the last car passes, the barrier is lowered again.)
A barrier is useful to control a group of threads so they all proceed in sync at specific points in the
program.
Here is how a barrier object may be used:
// the main thread:
// barrier object declared as a global variable, to be accessible from all threads:
Barrier barrier(N);
// assume N was defined as an int somewhere
// child threads run this thread function or similar:
void* thread_fun(void* param) {
while (not_exit) {
// thread runs in a loop
// do some work
barrier.wait();
// suspend all calling threads until the Nth thread makes the call,
//
after which all threads will resume and return from wait
// do some more work
}
}
The Barrier class must have at least a public constructor, a destructor, and a method wait(), as seen in
the following class skeleton:
class Barrier {
public:
Barrier(int n);
~Barrier();
// n is the number of threads (N)
// destructor: cleanup, destroy mutex, condvar, etc.
void wait();
// …
may need a condition variable, a mutex, and some other attributes
};
A Barrier object must encapsulate all the necessary synchronization objects (mutex and condition
variable, etc.) to do its job. Use the principle of encapsulation and keep the instance variables private.
Do not use global variables.
b)
Write a thread function in file barrier.cc that demonstrates in a meaningful way how your Barrier object
works. It should look like the code in function thread_fun above.
Run the program and include in the h5.pdf file a screenshot with the terminal with the program’s
output.
Important:






Did you write your name on file h5.pdf ?
Did you read the grading rubric ?
Did you write the solutions to the homework problems in the correct order?
Is your code nicely indented, with meaningful comments, and readable ?
Did you include a screenshot for each coding problem ?
Did you upload the source files for problems 2 and 4, too ?