CO2017
All candidates
Midsummer Examinations 2014
DO NOT OPEN THE QUESTION PAPER UNTIL INSTRUCTED TO DO SO BY THE
CHIEF INVIGILATOR
Department Computer Science
Module Code CO2017
Module Title Operating Systems, Networks, and Distributed Systems
Exam Duration Three hours
CHECK YOU HAVE THE CORRECT QUESTION PAPER
Number of Pages 9
Number of Questions 13
Instructions to Candidates This paper contains two parts, Part A and Part B.
Attempt all of Part A.
There are three questions in Part B. All questions from Part B may be at-
tempted but only the best two answers will be taken into account.
Part A is worth 40 marks. Each of the questions in Part B is worth 30 marks.
For this exam you are allowed to use the following
Calculators Not permitted
Books/Statutes Not permitted
Additional Stationery Not required
Page 1 of 9
CO2017
All candidates
Part A.
Briefly answer the questions below.
1. What does it mean for a process to be blocked on an I/O event? Give an example. What
will the next state of such a process be? [4 marks]
2. A bounded buffer is a data structure that could be used to share data between two
threads:
Consumer thread remove integers from the bounded buffer (unless the buffer is empty);
Producer thread will add integers to the bounded buffer (unless the buffer is full).
In this context explain the concepts of
(a) mutual exclusion; and
(b) critical region.
[5 marks]
3. Suppose that there are 2 threads, P and Q. Each consists of sequential atomic steps as
shown:
P: p1; p2; p3; p4;
Q: q1;q2;q3;
Suppose the threads are executed concurrently. Calculate how many different interleav-
ings are possible, and give at least 3 distinct examples. [3 marks]
4. In a virtual memory system, what is the page table? Include an outline of the data struc-
ture and its typical content. [5 marks]
5. At a given moment, a variable partition memory system has gaps in memory of the
following sizes, in the order given:
15K 30K 25K 20K 40K
A process of size 18K is to be loaded. Which hole size would be selected, using
(a) a best fit policy
(b) a first fit policy
(c) a worst fit policy
[3 marks]
6. What is triple modular redundancy? Briefly define code rate and Hamming distance
between valid codes and show what they are for triple modular redundancy. [4 marks]
Page 2 of 9
CO2017
All candidates
7. Consider the following sequence of bits that have been received at the data-link layer as
the contents of a single frame. They were encoded using two-dimensional even parity .
Assume that at most one bit was sent in error.
11011011
01110010
11100111
00110011
01110101
10010011
11000110
01111101
Determine whether there actually was an error, and if so where. Briefly justify your answer.
[3 marks]
8. Suppose that there are two files, A and B stored on a disk, occupying blocks as follows:
A 1,10,5,12
B 2,3,4,11
Sketch how this would be represented using a linked-list allocation scheme. [5 marks]
9. In the physical layer of a network, what is Manchester encoding, and why is it an im-
provement over a system that simply transmits distinct voltages for zero and one bits?
[3 marks]
10. Explain what double buffering is in an I/O system. Use diagrams to illustrate why it is an
improvement over single buffering. [5 marks]
Page 3 of 9
CO2017
All candidates
Part B.
1. (a) The following jobs arrive in the ready queue at the time specified in the rightmost
column; the middle column gives the estimated running time of each job.
Job Estimated running time (ms) Arrival time (ms)
1 9 0
2 1 1
3 6 3
4 2 6
Give the order in which these jobs will be scheduled under both
i. Shortest Remaining Time First (SRTF)
ii. Round-Robin (RR) with quantum 5 ms
scheduling policies. Calculate the completion and waiting times for each job. Assume
that the duration of a context switch can be ignored. [10 marks]
(b) Consider processes P1, P2, P3 and P4 running on a machine that has resources A,
B, C and D available in the following total amounts:
A B C D
4 2 4 3
Suppose that the currently held resources are
Held A B C D
P1 0 0 3 1
P2 0 1 0 0
P3 4 0 0 1
P4 0 0 0 1
and the requested resources are
Req A B C D
P1 2 1 0 1
P2 2 2 0 1
P3 0 1 1 0
P4 3 2 1 2
Demonstrate how Dijkstra’s Banker’s deadlock detection algorithm works using
the example above. Specify the order in which the processes will run and/or the point
at which deadlock is found to be inevitable; write the vector of available resources
after each step. [10 marks]
(c) A concurrent program Nondeterminism involving resource sharing among pro-
cesses is shown in Figure 1. It is built using the classes Thread1, Thread2 and
Semaphore defined in Figures 2, 3 and 4 respectively.
Assume that in the methods of the shared object, assignments, such as x++, x =
x * 4, and x = x + 3, etc. are treated as single atomic operations. You may
also assume that no exceptions are thrown in the Wait() method.
What are the possible final values of variable x when the program is executed?
Briefly explain how you arrived at your answer. [10 marks]
Page 4 of 9
CO2017
All candidates
1 public class Nondeterminism {
2 private int x = 0;
3 public void task1() { x = x + 4; }
4 public void task2() { x++; }
5 public void task3() { x = x * 3; }
6
7 public static void main(String[] args) {
8 Nondeterminism nD = new Nondeterminism();
9 Semaphore s1 = new Semaphore(1);
10 Semaphore s2 = new Semaphore(0);
11
12 Thread1 t1 = new Thread1(nD,s1,s2);
13 Thread2 t2 = new Thread2(nD,s1,s2);
14 t1.start();
15 t2.start();
16 nD.task3();
17 }
18 }
Figure 1: Nondeterminism class
1 class Thread1 extends Thread {
2 Nondeterminism nd;
3 Semaphore sem1;
4 Semaphore sem2;
5
6 public Thread1(Nondeterminism ND, Semaphore s1, Semaphore s2)
7 { nd = ND; sem1 = s1; sem2 = s2; }
8
9 public void run() {
10 sem1.Wait();
11 nd.task1();
12 sem2.Signal();
13 sem1.Signal();
14 }
15 }
Figure 2: Thread1 class
Page 5 of 9
CO2017
All candidates
1 class Thread2 extends Thread {
2 Nondeterminism nd;
3 Semaphore sem1;
4 Semaphore sem2;
5
6 public Thread2(Nondeterminism ND, Semaphore s1, Semaphore s2)
7 { nd = ND; sem1 = s1; sem2 = s2; }
8
9 public void run() {
10 sem2.Wait();
11 sem1.Wait();
12 nd.task2();
13 sem1.Signal();
14 }
15 }
Figure 3: Thread2 class
1 class Semaphore {
2 private int value;
3 public Semaphore (int init) { value = init; }
4
5 public synchronized void Signal() {
6 if (value == 0) this.notify();
7 ++value;
8 }
9
10 public synchronized void Wait() throws InterruptedException {
11 while (value == 0) this.wait();
12 –value;
13 }
14 }
Figure 4: Semaphore class
Page 6 of 9
CO2017
All candidates
2. (a) Consider a Virtual Memory system with 20 pages, numbered 0 to 19, and with 5
page frames, numbered 0 to 4 available. Initially all page frames are empty.
Suppose that page requests arrive in the following order:
1,2,0,5,9,10,5,1,3,8,5,16,1,2,5,14
i. Using a simple First In First Out (FIFO) page replacement algorithm how many
page faults would occur? Which pages would be loaded into the page frames at
each step? [5 marks]
ii. Using a Clock Replacement algorithm, how many page faults would occur?
Which pages would be loaded into the page frames at each step, and what
would the state of the “clock” be? [5 marks]
(b) Briefly explain how a UNIX style file system implements directories and files. Your
explanation should include an outline of the purpose and structure of i-nodes.
[6 marks]
(c) With the aid of a short example, explain how byte stuffing can be used in the data-
link layer to identify frames of data that can contain any possible byte sequence. For
simplicity of the explanation, you may assume that all the data to be transmitted can
be represented by single decimal digits. [5 marks]
(d) Consider the following 7-bit sequences that have been received in the data-link layer.
They are Hamming (7,4) encoded, using even parity, and you may assume that they
have at most a single bit error. In each case, determine what the transmitted data
(not including the parity bits) was, and justify your answer.
i. 0111101
ii. 1101001
iii. 1011101
[9 marks]
Page 7 of 9
CO2017
All candidates
..B.
A
.
C
. D.
E
.
F
.
2
.
3
.
8
.
3
.
9
.
4
.
2
.
1
Figure 5: Network and link costs
1 public class QuoteGenerator {
2 public QuoteGenerator() { … }
3 public String GetQuote() {
4 // This might take some time…
5 }
6 }
Figure 6: Outline of QuoteGenerator
3. (a) Consider using a tablet device connected using Wi-Fi to domestic broadband, and
running a web browser to look up train time-table information on a railway company’s
web site.
i. Identify the layers of the TCP/IP protocol used on the Internet. [4 marks]
ii. For each layer, identify the protocol(s) that could typically be used.
[4 marks]
iii. List at least 2 different types of physical media that would be used in the con-
nection. [2 marks]
(b) Trace the operation of Dijkstra’s algorithm by explaining how it would find the least
expensive route from A to F in the network illustrated in Figure 5, where the numbers
represent the cost of sending a packet along that edge. For each iteration give the
working node and for each node specify the cost of the shortest path computed so
far, its predecessor and status.
[10 marks]
(c) Write a Java QuoteServer class that implements a “quotation server” satisfying
Page 8 of 9
CO2017
All candidates
the following specification.
• The server should listen on port 1234;
• when a client connects it should create a handler thread, and then continue
waiting for connections;
• the server should continue to run indefinitely;
• the handler thread should use the QuoteGenerator class (described in Fig-
ure 6) to get a String and send it back to the client.
Appropriate exceptions should be handled. Only the server side is required. You do
not need to implement the QuoteGenerator class. [10 marks]
END OF PAPER Page 9 of 9