Q1. Which one of the following statements correctly identifies an issue with the snippet of Go code below?
A. It incorrectly uses channels as they only accept integer values
B. It incorrectly uses the go keyword in this context
C. It will produce a deadlock
D. It incorrectly uses channels bidirectionally, which is illegal in Go
E. None of the above statements correctly identify and issue with the code snippet
Page 3 of 18 Turn Over/. . .
Q2. Which one of the following statements about deadlock is NOT a necessary condition for it to occur?
A. Mutual Exclusion Condition: The resources involved are non-shareable
B. Must share all resources condition: The resources involved are shareable
C. Hold and Wait Condition: Requesting process hold already, resources while waiting for requested resources
D. No-Preemptive Condition: Resources already allocated to a process cannot be preempted
E. Circular Wait Condition: The processes in the system form a circular list or chain where each process in the list is waiting for a resource held by the next
process in the list
Q3. Which of the following statements about concurrent computing is INCORRECT?
A. A semaphore, in its most basic form, is a protected Boolean variable
B. The test-and-set operation is executed atomically
C. The main disadvantage of spinlocks is that they require busy waiting
D. A semaphore can be accessed from multiple threads
E. None of the above (all of the above choices, A through to D are CORRECT)
Page 4 of 18
Q4. Which of the following statements about processes must hold for a process P to be termed ‘safe’ with respect to a specification S?
C. traces(S) ⊆ traces(P)
D. traces(P) ⊇ traces(S)
E. None of the above (none of the choices, A through D, are correct)
Q5. Which of the following statements about processes must hold for a process P to be termed ‘deadlock-free’ with respect to a specification S?
A. (P ⊑F S)∧(P ⊑T S) B. (P ⊑F S)∨(P ⊑T S) C. P ⊑F S
E. None of the above (none of the choices, A through D, are correct)
Q6. Which of the following statements about concurrent computing is INCORRECT?
A. Peterson’s Algorithm is designed to solve the critical section problem using
busy-waiting.
B. A potential bug arising from using a binary sempahore to protect a critical section is that its value could be incremented by a thread which is not currently executing the critical section
C. A race condition is caused by potentially concurrent operations on a shared memory location, of which at least one is a write operation
D. Mutexes are primarily used to ensure fairness: so that any thread has a fair chance of entering the critical section
E. None of the above (all of the above choices, A through to D are CORRECT)
Page 5 of 18 Turn Over/. . .
Q7. Consider a CSP process:
coin → change → STOP {coin,change}||{coin,ticket} coin → ticket → STOP
Which of the following sets describes its (the process’s) traces?
A. {<>,< coin >,< coin,change >,< coin,change,STOP >,< coin,ticket >,
< coin,ticket,STOP >}
B. {<>, < coin >, < coin, change >, < coin, ticket >}
C. {<>, < coin >, < coin, change >, < coin, change, ticket >, < coin, ticket >, < coin, ticket, change >}
D. {<>, < coin >, < coin, coin >, < coin, change >, < coin, change, ticket >, < coin, ticket >, < coin, ticket, change >}
E. None of the above (none of the choices, A through D, are correct) [2 marks]
Q8. Consider the following finite state machines.
Which of them are divergent (given the initial state is coloured black)? A. 1), 2), 3), 4)
E. None of them are divergent
Page 6 of 18
Q9. What is the failure set for the finite state machine illustrated below where the initial state is coloured black (note that N0 represents the natural numbers including 0)?
A. {(
∪(< a, b, c >n⌢< a >, X) | n ∈ N0 ∧ X ⊆ {a, c}} ∪(< a, b, c >n⌢< a, b >, X) | n ∈ N0 ∧ X ⊆ {a, b, c}}
B. {(
∪(< a, b, c >n⌢< a >, X) | n ∈ N0 ∧ X ⊆ {a, c}} ∪(< a, b, c >n⌢< a, b >, X) | n ∈ N0 ∧ X ⊆ {a, b}}
C. {(
D. {(
∪(< a, b, c >n⌢< a, b >, X) | n ∈ N0 ∧ X ⊆ {a, b}} ∪{(< a, b, c >n⌢< a, b, c >, X) | n ∈ N0 ∧ X ⊆ {b, c}}
E. None of the above are correct
Page 7 of 18
Turn Over/. . .
Q10. ConsideraCSPprocess,PUPIL,withthealphabetP ={yr1,yr2,pass,fail,leave} and the process definition:
PUPIL = yr1 → (pass → FINALY EAR | f ail → PUPIL)
FINALYEAR = yr2 → (pass → leave → STOP | f ail → FINALY EAR)
All pupils have generous guardians who provide a gift every time a pupil successfully completesayear. ProcessGUARDIANhasalphabet,G={pass,gift}andtheprocess definition:
GUARDIAN = pass → gif t → GUARDIAN
How many states has P UP IL P ||G GUARDIAN? A. 14
E. None of the above
Page 8 of 18
Q11. The figure below will be used for the next 2 questions. Consider the producer consumer problem with a buffer of size 5, as well as the following three C-style code fragments where the top box represents initialisation and the bottom left and bottom right boxes represent the producer and consumer, respectively, running in a separate threads:
Given that the sem post function increments the semaphore’s value and the sem wait function decrements it, which of the following initialisations of the three constants, x1,x2,x3, turns the given code into a correct implementation ?
A. x1=1,x2=0,x3=5
B. x1=1,x2=5,x3=0
C. x1=0,x2=0,x3=5
D. x1=5,x2=1,x3=0
E. None of the above (none of the choices, A through D are correct)
Q12. Consider once again the producer consumer problem as described in the previous ques- tion. Note the arrow for the producer thread indicating that that thread (the producer) is waiting at err = sem wait(sem data lock). Also note the arrow for the consumer, indicating that this thread is currently executing the doSomethingElse function. If the buffer currently contains 0 items of work and has 5 spaces free, what are the current val- ues for sem1, sem2 and sem data lock, given both current threads stage of execution and that these are the only 2 threads that access the buffer ?
A. sem1=1,sem2=4,sem data lock=0
Page 9 of 18 Turn Over/Qu. continues . . .
B. sem1=0,sem2=5,sem data lock=1
C. sem1=2,sem2=3,sem data lock=0
D. sem1=0,sem2=3,sem data lock=0
E. None of the above (none of the choices, A through D are correct)
Page 10 of 18
Q13. The Petri net below represents a binary semaphore. It’s markings may be described in theform(InputA , CriticalA , OutputA, Semaphore, InputB , CriticalB, OutputB).
Which of the ing correctly?
following markings would indicate that the semaphore is not function-
E. None of the above – all markings are approporiate
1, 0, 0, 1, 0, 0)
0, 1, 0, 0, 1, 0)
0, 1, 1, 1, 0, 0)
1, 0, 1, 1, 0, 0)
Page 11 of 18
Turn Over/. . .
Q14. Consider the producer consumer problem with a buffer of size BUFFSIZE, as well as the following three C-style code fragments where the top box represents initialisation and the bottom left and bottom right boxes represent the producer and consumer, respec- tively, running in a separate threads:
Which of the following substitutions (from the top code fragment box) for the variables,
lockA, lockB, lockC, lockD, lockE, lockF, condA, condB, condC, condD, predicateA, predicateB, turns the given code into an correct implementation?
A. lockA=lockC=lockE = lock1
lockB=lockD=lockF = lock2
condA=condD = cond3, condB=condC = cond4
predicateA = (gNumSpace ¿ 0), predicateB = (gNumWorkItems ¿ 0)
B. lockA=lockB=lockC=lockD=lockE=lockF = lock2
condA=condD = cond2, condB=condC = cond3
predicateA = (gNumSpace ¿ 0), predicateB = (gNumWorkItems ¿ 0)
C. lockA=lockB=lockC=lockD=lockE=lockF = lock1
condA=condD = cond1, condB=condC = cond2
predicateA = (gNumWorkItems ¿ 0), predicateB = (gNumSpace ¿ 0)
D. lockA=lockB=lockC=lockD=lockE=lockF = lock2
condA=condB = cond2, condC=condD = cond1
predicateA = (gNumSpace ¿ 0), predicateB = (gNumWorkItems ¿ 0)
Page 12 of 18 Qu. continues . . .
Q15. Consider the constants C1,…,C14 as well as the following two C-style code fragments running in a separate thread each:
Which of the following initialisations of the ten constants turns the given code into a correct implementation of Peterson’s Algorithm?
A. C1=C3=C7=C8=C11=C13=0 and C2=C4=C5=C6=C9=C10=C12=C14=1 B. C1=C3=C5=C6=C7=C8=C11=C12=0 and C2=C4=C9=C10=C13=C14=1 C. C1=C7=C8=C10=C11=C13=0 and C2=C3=C4=C5=C6=C9=C12=C14=1 D. C1=C3=C6=C11=C14=0 and C2=C4=C5=C7=C8=C9=C10=C12=C13=1 E. None of the above (none of the choices, A through D, are correct)
E. None of the above (none of the choices, A through D, are correct)
Page 13 of 18 Turn Over/. . .