Processes and Threads
Group Work
This assignment can be completed individually or in pairs. If you want to work in a pair find a
partner from your class. INB students can only pair with other INB students and the same applies
for INN students.
Due Date
Friday Week 8 – 16/9/2011
Weighting
20% of the final grade
Objectives
• Implement a project in the C language on Linux using the Make build system.
• Implement safe concurrent access to shared memory using POSIX Threads in C.
• Understand the synchronisation primitives made available via the POSIX Threads library.
• Understand and implement the Producer/Consumer pattern.
Submission
This assignment is to be submitted via the OAS system. Students who complete the assignment in
pairs only need to submit one assignment per pair.
http://www.student.qut.edu.au/about/faculties-institutes-and-divisions/faculties/scitech/online-
assessment-system
The submitted zip archive (assign1.zip) needs to contain
• the source code implementing the assignment.
• a makefile to build the source code.
• a report in Word 2003 (.doc) or Portable Document Format (.pdf).
Source code
• The source code can be contained in single or multiple files.
• The makefile needs to generate a binary called terminal so that the command 'make clean
&& make && ./terminal' will recompile the source from scratch and run the program.
The report must contain
• a statement of completeness indicating the tasks attempted and any deviations from the
specifications or known bugs.
• a description of the data structures, threads and how they interact.
• a short description of how to run the program.
• an answer for Task 2 (INN365 students only).Task 1 – A Shipping Terminal Simulation
This task is to be completed by both INB and INN students.
Your tasks is to implement a shipping terminal simulation. The terminal contains a wharf with 10
berths where the ships are unloaded. The ships arrive by seaway and dock at the first available
berth. After unloading, the ships depart via the same seaway. Only one ship can travel in the seaway
at any given time. This is illustrated in the diagram below.
The simulation will be implemented in the C programming language using POSIX Threads on the
Linux operating system. This is the same environment used during the weekly practicals. You will
have acquired all the necessary knowledge and skills to complete the assignment by attending all
the lectures and practicals, and completing the associated reading from the text book.
The program is to run in a terminal reading input from STDIN and writing output to STDOUT.
You may choose to use any data structure to represent the wharf such as an array or linked list.
Concurrent access to this shared data must be synchronised using POSIX Threads synchronisation
primitives such as a mutex and condition variables, or a mutex and semaphores.
Your program will consist of four threads.
1. The main thread that spawns all others threads.
2. An arrival thread (producer) that simulates ships arriving to the terminal.
3. A departure thread (consumer) that simulates ships leaving the terminal.
4. A monitor thread that accepts input from the keyboard.
The main thread starts the program and displays the initial banner. It creates three other threads as
listed above and waits for them to terminate.
The arrival thread generates new ships and berths them at the wharf. If the wharf is full, the arrival
thread will print 'The wharf is full.' and block until there is a free berth. The arrival thread does not
continually generate new ships. At each attempt there is a 60 percent chance that a new ship arrives.
After each attempt the thread sleeps for half a second. Ships are identified by a six digit code such
as 'HQ1864' consisting of two upper case character and four numbers. These identifiers are
generated randomly.
The departure thread removes ships at random from the wharf. If the wharf is empty, the departure
thread will print 'The wharf is empty.' and block until there is a new ship to remove. The departure
thread does not continually remove ships. At each attempt there is a 40 percent chance that a ship
departs. After each attempt the thread sleeps for half a second.The monitor thread reads input from the keyboard. Valid inputs include 'p', 'P', 'q' and 'Q'.
Characters that only differ by case are considered the same. For example, 'p' and 'P' issue the same
command. The input 'p' indicates that the current state of the wharf needs to be printed to the screen.
When printing the state, each berth in the wharf must be listed with its current state such as
'HQ1864' or 'Empty'. The input 'q' indicates that the simulation has terminated. Note that the
simulation must end gracefully without calling exit() or killing the threads.
Example Output
Welcome to the shipping terminal simulator.
Press p or P followed by return to display the state of the wharf.
Press q or Q followed by return to terminate the simulation.
Press return to start the simulation.
The wharf is empty.
Ship HQ1864 docked in berth 1.
p
Wharf status:
1: HQ1864 (docked for 1.14 seconds)
2: Empty
3: Empty
4: Empty
5: Empty
6: Empty
7: Empty
8: Empty
9: Empty
10: Empty
Ship XJ2384 docked in berth 2.
Ship HQ1864 departed berth 1 and stayed 3.37 seconds.
Ship QR8293 docked in berth 1.
Ship AB7520 docked in berth 3.
Ship UI2741 docked in berth 4.
Ship VT6522 docked in berth 5.
Ship HJ4728 docked in berth 6.
Ship MD5671 docked in berth 7.
Ship KF4587 docked in berth 8.
Ship SW2893 docked in berth 9.
Ship NP1276 docked in berth 10.
The wharf is full.
q
The simulation has terminated.Task 2 – The Critical-section Problem
This task is only for INN365 students. You do not need to attempt this task if you are an INB365
student.
The first known correct software solution to the critical-section problem for n processes with a
lower bound on waiting of n - 1 turns was presented by Eisenberg and McGuire. The processes
share the following variables,
enum pstate {idle, want_in, in_cs};
pstate flag[n];
int turn;
where, “want_in” denotes the process is ready, “in_cs” means the process is in its critical section,
and “idle” means idle state. All the elements of flag are initially idle; the initial value of turn is
immaterial (between 0 and n - 1). The structure of process Pi is shown in Table 1.
(a) Give a brief explanation of what the algorithm does to ensure mutual exclusion.
(b) Prove that the algorithm satisfies all three requirements for the critical-section problem.
do {
while (TRUE) {
flag[i] = want_in;
j = turn;
while (j! = i) {
if (flag[j] != idle)
j = turn;
else
j = (j+1) % n;
}
flag[i] = in_cs;
j = 0;
while ((j<n) && (j==i || flag[j] != in_cs))
j++;
if ((j>=n) && (turn == i || flag[turn] == idle))
break;
}
// Critical section
j = (turn + 1) % n;
while (flag[j] == idle)
j = (j + 1) % n;
turn = j;
flag[i] = idle;
// Remainder section
} while (TRUE)
Table 1. The structure of process Pi