辅导CSC3021、C++，Java编程辅导

日期：2022-11-10 07:13

ASSIGNMENT 2
CSC3021 Concurrent Programming 2022-2023
Submit by 5:59 pm on Monday 7th November 2022
Question 1: Mutual Exclusion [20 marks]
Consider the following program intended to solve the mutual exclusion
problem for the case of two processes. The processes are indexed by the
variable i, which can take the values 0 or 1.
Answer following questions and provide a proof for each:
(i) Does the algorithm uphold the mutual exclusion property?
(ii) Is the algorithm free of deadlock?
Hint: it may help to explicitly write out the code for P0 and P1, by setting the
variable i to 0 and 1 in process P0 and P1, respectively.
Question 2: Haunted House [20 marks]
A haunted house is visited by ghosts, witches and black cats. Each of these
actors is represented by a process that repeatedly enters and exits the house.
The ghosts, witches and black cats have to follow these rules:
? Witches and black cats only enter together. One cat remains in the
house for each witch present; otherwise cats may leave at any time.
? Ghosts do not enter when a witch is inside the house, but they can
remain in the house if a witch enters.
? There can be at most 3 ghosts in the house at any moment in time.
Process Pi
P1: while( true ) {
P2: non-critical-section;
P3: flag[i] = 1;
P4: while( turn == 1 – i ) {
P5: while( flag[1-i] == 1 ) { }
P6: turn = i;
P7: }
P8: critical-section;
P9: flag[i] = 0;}
}
end Pi;
int flag[2] := {0, 0}
int turn := 0 or 1
2
Write process definitions for the ghosts, witches and black cats such that the
above constraints are satisfied, and no additional constraints on concurrency
are introduced. You may assume the following process structure:
Semaphore and variable declarations…
Process
Ghost[1..G]
while(true){
//is entering
…
//has entered
…
//is leaving
…
//has left
…
}
End Visitor
Process
Witch[1..W]
while(true){
//is entering
…
//has entered
…
//is leaving
…
//has left
…
}
End Winnie
Process
BlackCat[1..B]
while(true){
//is entering
…
//has entered
…
//is leaving
…
//has left
…
}
End Pumpkin
You may use semaphore variables and integer variables. You do not need to
consider starvation issues but your code must be free of deadlock.
Ensure your hand-in contains pseudo-code that is clear to read and
unambiguous.