COMS20008 COMPUTER SYSTEMS A
Mock paper
TIME ALLOWED: 2 Hours
This paper contains 25 questions, all of which are used for assessment; the maximum for this paper is 44.
1. Please make sure you read the instructions on the answer sheet.
2. Only the answer sheet will be marked, the empty pages at the back of the exam are only used for your calculations.
3. When selecting answers, make clear, horizontal m arks within the two sets of brack- ets, making sure that the contained letter is struck through.
4. Avoid marking the answer sheet outside specified areas.
5. Do not crease, dog-ear or otherwise damage the answer sheet.
6. Please note that the first part of this paper (Q1 to Q13, total weighting 22 marks) relates to unit material delivered for concurrent computing (Sion’s bit) second part (Q14 to Q25, total weighting 22 marks) of the paper to distributed computing material (Matt’s bit).
Page 2 of 17
Q1. Which one of the following statements correctly identifies an issue with the snippet of Go code below?
A. It incorrectly uses channels as the value received is not assigned to anything B. It incorrectly uses the go keyword in this context
C. It will produce a deadlock
D. It may not reach the fmt.Printf statement in the 1st goroutine
E. None of the above statements correctly identify and issue with the code snippet
Page 3 of 17 Turn Over/. . .
Q2. Which of the following statements about concurrent computing is INCORRECT?
A. The test-and-set operation is executed atomically
B. Mutual exclusion for Critical Sections in multi-threaded systems cannot be im- plemented in software without a test and set operation that allows for atomi- cally reading and writing a memory location in one operation
C. The main disadvantage of spinlocks is that they require busy waiting
D. A semaphore, in its most basic form, is a protected integer variable
E. A semaphore can be accessed from multiple threads
Q3. Which of the following statements about concurrent computing is INCORRECT?
A. A Critical Section is a code fragment that interacts with a shared resource and
should not be executed by more than one thread at any one time.
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. Mutexes are primarily used to ensure fairness: so that any thread has a fair chance of entering the critical section
D. A race condition is caused by potentially concurrent operations on a shared memory location, of which at least one is a write operation
E. None of the above (all of the above choices, A through to D are CORRECT)
Page 4 of 17
Q4. Which one of the following statements about deadlock is NOT a necessary condition for it to occur??
A. Must hold all resources condition: Each agent must request all its required resources at once
B. Mutual Exclusion Condition: The resources involved are non-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
Q5. Which of the following, CSP themed, statements is INCORRECT?
A. A sequence of zero or more events exhibited after the start of a process is
known as a trace in CSP
B. A CSP failure is a pair consisting of a refusal and a trace
C. A CSP process is divergent if it can perform an infinite sequence of τ events
D. For a process P to be termed safe with respect to a specification S: traces(P) ⊇ traces(S)
E. Sets of CSP traces are prefix closed
Q6. ConsideraCSPprocessP =a→(a→(b→P))whereα(P)={a,b}andN0 repre- sents the natural numbers including 0. Which of the following sets describes traces(P)?
A. {< a,a,b >m⌢< a > |m ∈ N0}∪{< a,a,b >n⌢< a,a > |n ∈ N0}∪{<>}
B. {
C. {< a >⌢< a,b,a >m |m ∈ N0}∪{< a,a >⌢< b,a,a >n |n ∈ N0}∪{< a,a,b >p |p ∈ N0}
D. {< a >⌢< a,b,a >m |m ∈ N0}∪{< b,a,a >n⌢< b,a > |n ∈ N0}∪{< a,a,b >p |p ∈ N0}
E. None of the above
Page 5 of 17 Turn Over/. . .
Q7. Given the following process:
a → ST OP □ a → b → ST OP
What are its stable failures?
A. {(<>,X)|X⊆{b}}
∪{(< a >, X) | X ⊆ {a, b}} ∪{(< a, b >, X) | X ⊆ {a, b}}
B. {(<>,X)|X⊆{b}}
∪{(< a >, X) | X ⊆ {a}} ∪{(< a, b >, X) | X ⊆ {a, b}}
C. {(<>,X)|X⊆{a,b}} ∪{(< a >, X) | X ⊆ {b}} ∪{(< a, b >, X) | X ⊆ {}}
D. {(<>,X)|X⊆{a}}
∪{(< a >, X) | X ⊆ {b}} ∪{(< a, b >, X) | X ⊆ {a, b}}
E. None of the above (none of the choices, A through D, are CORRECT)
Q8. Consider the CSP processes: P = a → (b → (d → P ))
Q = b → (d → (c → (e → Q)))
How many states does the resulting CSP process R = P {a,b,d}||{b,c,d,e} Q have? A. 5
E. None of the above
Page 6 of 17
Q9. The figure below will be used for the next 2 questions. Consider the producer consumer problem with a buffer of size 20, 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=20,x3=0
B. x1=1,x2=0,x3=20
C. x1=0,x2=0,x3=20
D. x1=20,x2=1,x3=0
E. None of the above (none of the choices, A through D are CORRECT)
Page 7 of 17 Turn Over/. . .
Q10. 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 currently executing the doSomethingElse function. Also note the arrow for the con- sumer, indicating that this thread is currently executing the doSomethingElse function. If the buffer currently contains 0 items of work and has 20 spaces free, what are the current values 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=0,sem2=18,sem data lock=0
B. sem1=1,sem2=19,sem data lock=1
C. sem1=0,sem2=20,sem data lock=0
D. sem1=2,sem2=18,sem data lock=0
E. None of the above (none of the choices, A through D are CORRECT)
Q11. Which of the following is both bounded and live?
A. A B. B C. C D. D E. E
Page 8 of 17
Q12. 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 a 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 = lock1
condA=condD = cond1, condB=condC = cond2
predicateA = (gNumWorkItems ¿ 0), predicateB = (gNumSpace ¿ 0)
C. lockA=lockB=lockC=lockD=lockE=lockF = lock2
condA=condB = cond2, condC=condD = cond3
predicateA = (gNumSpace ¿ 0), predicateB = (gNumWorkItems ¿ 0)
D. lockA=lockB=lockC=lockD=lockE=lockF = lock2
condA=condD = cond3, condB=condC = cond4
predicateA = (gNumSpace ¿ 0), predicateB = (gNumWorkItems ¿ 0)
Page 9 of 17 Turn Over/Qu. continues . . .
E. None of the above (none of the choices, A through D, are correct)
Q13. Consider twelve constants C1,…,C12 as well as the following two C-style code frag- ments running in a separate thread each:
Which of the following initialisations of the twelve constants turns the given code into a correct implementation of Peterson’s Algorithm?
A. C0=C2=C6=C9=C11=0 and C1=C3=C4=C5=C7=C8=C10=1 B. C0=C2=C4=C5=C6=C9=C10=0 and C1=C3=C7=C8=C11=1 C. C0=C6=C8=C9=C11=0 and C1=C2=C3=C4=C5=C7=C10=1 D. C0=C2=C5=C9=0 and C1=C3=C4=C6=C7=C8=C10=C11=1 E. None of the above
Page 10 of 17
Q14. Which of the following can be said to be accurate about packet-switched and circuit- switched networks?
A. Circuit-switching creates a dedicated connection between two endpoints.
B. Packets forming parts of the same message can arrive via different routes in a packet-switched network.
C. Circuit-switching reserves a certain amount of bandwidth for the duration of communication.
D. Packet-switching makes more efficient use of bandwidth than circuit-switching.
E. All of the above.
Q15. Which of the below protocols is a stateless transport-layer protocol? A. HTTP
B. FTP C. UDP D. TCP E. IP
Q16. You are developing a new kind of SSH client for your business. For testing purposes during development, you have been told to try and connect to an ordinary sshd instance running at 192.168.10.13 with its usual default settings. Which of the following lines of Go code might appear in your client?
A. client, err := net.Dial(”tcp”, ”127.0.0.1:8030”)
B. client, err := net.Dial(”tcp”, ”192.168.10.13:22”)
C. client, err := net.Listen(”tcp”, ”:8030”)
D. client, err := net.Listen(”tcp”, ”192.168.10.13:8030”) E. client, err := net.Listen(”tcp”, ”192.168.10.13:22”)
Page 11 of 17 Turn Over/. . .
Q17. Which of the following are valid Length field values for a UDP datagram header?
A. All of them. B. (1) and (2). C. (3).
E. None of them.
(1) 65,535 (2) 65,500 (3) 1
Q18. One drawback of a distributed shared memory system is:
A. Processes can have non-overlapping lifetimes while communicating via shared
B. It is not possible to directly modify a shared counter.
C. The full state of one process needs to constantly be communicated to all other processes.
D. Programmers have a less clear picture of which actions can cause communi- cation delays.
E. There is no way to synchronise processes, meaning all algorithms running under DSM must first elect a leader to order activity.
Page 12 of 17
Q19. You’re working on building a publish-subscribe system using RPC. You’ve encountered a bug somewhere in the code below – for some reason, your subscription requests don’t seem to be working, but you’re not seeing any error messages.
1 2 3 4 5 6 7 8 9
10 11 12 13 14
type Broker struct {}
func (b ∗Broker) subscribe(req Subscription , res ∗StatusReport) (err error) { topicmx . RLock ()
ch := topics[req.Topic]
topicmx . RUnlock ()
client , err := rpc.Dial(”tcp”, req.WorkerAddress)
if err == nil {
go subscriber loop(ch, client , req.Callback)
return err
On which line is the bug? A. 3
B. 5 C. 7 D. 9 E. 13
Page 13 of 17
Turn Over/. . .
Q20. Looking at the network topology in the below graph, imagine building a spanning tree using the synchronous single-initiator flooding algorithm. Which initial root node produces the ’shortest’ tree, with the smallest maximum depth?
A. 6 B. 11 C. 9 D. 1 E. 10
Page 14 of 17
Q21. Which of the cuts in the time-space diagram below would be inconsistent or consistent?
A. C1 consistent, C2 consistent.
B. C1 consistent, C2 inconsistent. C. C1 inconsistent, C2 consistent. D. C1 inconsistent, C2 inconsistent. E. None of the above.
Q22. As part of writing a simple client-server message-passing program that sends a value to the server for storage, the below procedures need to be called.
1. connection.Write 2. listener.Accept 3. net.Dial
4. net.Listen
5. connection.Close
Which of the options below describes the order in which these steps need to be performed? A. 1,2,3,4,5,
B. 2,4,5,3,1
C. 3,4,2,1,5,
D. 2,4,3,1,5
E. None of the above.
Page 15 of 17
Turn Over/. . .
Q23. Assume each point on the time-space graph below is an event, and each arrow repre- sents communication from one process to another. What is the value of a vector clock at process p1 at the point X in the diagram?
A. [5,5,2,4] B. [3,4,2,4] C. [4,5,2,4] D. [4,5,2,5] E. [5,5,2,3]
Page 16 of 17
Q24. In a naive attempt at recording the combined state of two bank accounts in a distributed system, a programmer has synced two machines using an improved version of the NTP time protocol. They’re confident that the two machines’ clocks can be no more than 2 nanoseconds apart, and so think they can just sum up local account values to get a global accounts total.
Look at the below diagram of the system. Assuming the marked time-points are each 1 nanosecond apart, what is the maximum error of their global total from the true value in the system at any point in this period?
A. £0 B. £20 C. £200 D. £220 E. £420
Q25. Assuming that we can deploy Lamport et al.’s synchronous solution for Byzantine fault tolerance, which of the values below is the closest upper bound on the number of messages that would be sent in total to arrive at consensus between 13 processes?
C. 67,108,864 D. 2,197
Page 17 of 17 END OF PAPER