CSSE7610
Concurrency: Theory and Practice
SEMESTER TWO FINAL EXAMINATION 2021
INSTRUCTIONS
1. This examination paper contains FIVE (5) questions and comprises SEVEN (7)
pages.
2. There are 50 marks in total.
3. Answer all questions. The marks for each question are indicated at the beginning of
each question.
4. Write your answers on blank pages. At the end of the exam, scan or take photos of
all your pages, combine them into a single PDF file and upload to the Blackboard
assignment link.
Question 1 (15 marks)
The algorithm below attempts to solve the critical section problem for two threads, p
and q. Remember the assumption of the critical section problem that the critical section
must progress, and the non-critical section need not progress.
Solving critical section problem
enum{N, P, Q}
integer g1 ← N, g2 ← N
p q
loop forever loop forever
p1: non-critical section q1: non-critical section
p2: g1 ← P q2: g1 ← Q
p3: if g2 ̸= N goto p2 q3: if g2 ̸= N goto q2
p4: g2 ← P q4: g2 ← Q
p5: if g1 ̸= P q5: if g1 ̸= Q
p6: if g2 ̸= P goto p2 q6: if g2 ̸= Q goto q2
p7: critical section q7: critical section
p8: g2 ← N q8: g2 ← N
(i) Prove that the algorithm ensures mutual exclusion. If you require any invariants in
your proof, they must appear as lemmas and also be proved.
(6 marks)
(ii) Is the following formula an invariant: p6∧ (g1 = P)⇒ ¬(q4∨ q5∨ q7). If yes, prove
it; otherwise, give a fragment of the state diagram as a counterexample
(4 marks)
(iii) Use Linear Temporal Logic (LTL) to state the starvation freedom in this algorithm.
Does the algorithm satisfy this property? If yes, prove it; otherwise, give a fragment
of the state diagram as a counterexample.
(5 marks)
2
Question 2 (10 marks)
(Spaghetti Sauce Chefs Problem) Consider a scenario with three chef processes and
one supplier process. Each chef loops forever, first waiting for ingredients and then making
spaghetti sauce. The ingredients are meat, oil and salt. One of the chefs has infinite amount
of meat, another has infinite amount of oil and the third has infinite amount of salt. The
supplier has infinite amount of all three ingredients.
The supplier repeatedly places two different ingredients at random on the table. The
chef who has the complementary ingredient then picks up them and makes sauce. For
example, if the supplier puts out meat and salt, the chef who has the oil will pick up both
ingredients.
(i) First, assume the supplier notifies the chef who has the complementary ingredient.
Solve this synchronisation problem with semaphores. Any semaphore used must be a
weak semaphore, i.e., the processes blocked on the semaphore are in a set, not a
queue. Use language-independent notation. Clearly state your assumptions if any.
(4 marks)
(ii) Now, the following restriction is imposed: the supplier does not notify the chef
who has the complementary ingredient. Solve this problem with semaphores. Any
semaphore used must be a weak semaphore, i.e., the processes blocked on the
semaphore are in a set, not a queue. Use language-independent notation. Your
solution must be deadlock-free. Clearly state your assumptions if any.
(6 marks)
3
Question 3 (13 marks)
To conduct a sum operation, Alice writes a multithreading program to run multiple threads
to conduct the calculation at the same time. Please read the following Java pseudo-code
and answer the following questions.
1 // Java code for thread execution
2 public class Multithreading {
3 class Control {
4 public volatile int total = 0;
5 }
6
7 final Control control = new Control();
8
9 Class T implements Runnable {
10 @Override
11 //thread function
12 public void run()
13 {
14 int i = 0;
15 //sum calculation
16 for (i = 0; i < 20000; i++) {
17 control.total++;
18 }
19 }
20
21 public static void main(String[] args) throws Interrupted Exception
22 {
23 try{
24 int n = 6;
25 for (int i = 0; i < n; i++) {
26 Multithreading object = new Multithreading();
27 ...
28 object.start();
29 }
30 System.out.println("The final result of total is " + control.total);
31 }
32 }
33 }
34 }
1. How many threads are created in this multithreading program?
(2 marks)
2. Will the variable total (on line 30) be printed out correctly?
4
(3 marks)
3. Explain the reason why it can be printed out correctly/incorrectly. If the final result
of variable total is incorrect, please write a pseudo-code to correct the code.
Note that you do not have to give the detailed implementation of wait()/waitC(),
signal()/signalC()
(8 marks)
5
Question 4 (12 marks)
Danielle is writing a concurrent program to operate a shared linked list data structure. To
achieve mutual exclusion, she selects to use fine-grained synchronization to synchronize
the access to objects. By following the standard implementation of fine-grained
synchronisation as we introduced in the lecture, Danielle implements the data structure
of each node and function add() as below. Unfortunately, she implements an incorrect
hashcode generator which causes the hashcode of each node to not be unique.
1 // Data structure of each node
2 public class Node
3 T item;
4 int key;
5 Node
6 }
1 // Standard fine-grained sychronization – add
2 public boolean add (T item){
3 Node
4 int key = item.hashCode();
5 head.lock();
6 try {
7 pred = head; curr = pred.next;
8 curr.lock();
9 try {
10 while (curr.key < key) {
11 pred.unlock();
12 pred = curr; curr = curr.next;
13 curr.lock();
14 }
15 if(key == cyrr.key) {
16 return false;
17 }
18 Node
19 pred.next = newNode;
20 newNode.next = curr;
21 return true;
22 }
23 finally {
24 curr.unlock();
25 }
26 }
27 finally {
28 pred.unlock();
29 }
30 }
6
Please help Danielle fix this issue by answering the following questions.
1. Please explain what issue might be caused if the hashcode of each node is not unique.
(2 marks)
2. Please modify the data structure and the add() function to resolve this issue.
(7 marks)
3. Referring to your modification, please explain why the issue is solved.
(3 marks)
Question 5 (0 marks)
Please specify any assumptions you have made in completing this examination and which
questions those assumptions relate to. You may also include queries you may have made
with respect to a particular question, should you have been able to ‘raise your hand’ in an
examination room.
END OF PAPER
7