代写CSC3021、C++，Java编程代写

日期：2022-11-09 09:04

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.