CO2017
All candidates
Midsummer Examinations 2015
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 7
Number of Questions 6
Instructions to Candidates Attempt all questions. Full marks may be obtained only if all questions are
answered.
For this exam you are allowed to use the following
Calculators Not permitted
Books/Statutes Not permitted
Additional Stationery Not required
Page 1 of 7
CO2017
All candidates
1. Scheduling and the dispatcher
(a) What is the distinction between a program and a process? [2 marks]
(b) Give an example of a type of system where a non-preemptive scheduler would be
appropriate, briefly explaining the reason. [3 marks]
(c) 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)
A 10 0
B 5 1
C 2 5
D 2 8
Give the order in which these jobs will be scheduled under the following policies
i. First Come First Served (FCFS)
ii. Shortest Job First (SJF)
Calculate the completion and waiting times for each job. You may assume that the
duration of a context switch can be ignored. [10 marks]
2. Threads & concurrency in Java
Consider the (outline) code in Figure 1. The code is supposed to be a very simple sim-
ulation of a bank account shared between two people, one of whom only ever deposits
money, and the other only ever withdraws money.
You may ignore the possibility of Exceptions for this question.
(a) Explain what an interleaving is, using examples from the code. You should include
and identify at least one undesirable interleaving. [4 marks]
(b) Identify the critical sections of code, and explain what this means. [4 marks]
(c) Show how you could enforce mutual exclusion of the critical section. [6 marks]
(d) The bank would like to prevent the balance from ever dropping below zero. Show
how you could implement a guard to enforce this restriction. [6 marks]
Page 2 of 7
CO2017
All candidates
1 public class Account {
2 private int balance;
3 public Account(int initial) { balance = initial; }
4 public int getBalance() { return balance; }
5 public void deposit(int d) { balance=balance+d; }
6 public void withdraw(int w) { balance=balance-w; }
7 }
8
9 public class Spender extends Thread {
10 private Account acc;
11 public Spender(Account a) { acc=a; }
12 public void run() {
13 for (int i=0; i<100; ++i) {
14 acc.withdraw(500+i);
15 System.out.println("Spent "+(500+i));
16 Thread.sleep(1000);
17 }
18 }
19 }
20
21 public class Saver extends Thread {
22 private Account acc;
23 public Saver(Account a) { acc=a; }
24 public void run() {
25 for (int i=0; i<100; ++i) {
26 acc.deposit(400+i);
27 System.out.println("Deposit "+(400+i));
28 Thread.sleep(1100);
29 }
30 }
31
32 public class Test {
33 public static void main(String[] args) {
34 Account ac1 = new Account(1000);
35 Spender sp = new Spender(ac1);
36 Saver sv = new Saver(ac1);
37 sp.start(); sv.start();
38 while (true) {
39 System.out.println("Balance is: "+acc1.getBalance());
40 Thread.sleep(2000);
41 }
42 }
43 }
Figure 1: Outline bank account simulation code
Page 3 of 7
CO2017
All candidates
3. Memory management
(a) What is the memory hierarchy? Explain why it makes the identification of a working
set so desirable. [5 marks]
(b) Compare swapping in a direct memory model with page swapping in a virtual
memory system. [5 marks]
(c) Consider a Virtual Memory system with 20 pages, numbered 0 to 19, and with 5
page frames available, numbered 0 to 4. Initially all page frames are empty.
Suppose that page requests arrive in the following order:
1,2,11,6,9,5,11,2,3,15,2,11,1,6,17,2
i. Using a Not Recently Used (NRU) page replacement algorithm how many page
faults would occur? Which pages would be loaded into which page frames at
each step? [5 marks]
ii. Using a Least Recently Used (LRU) page replacement algorithm, how many
page faults would occur? Which pages would be loaded into which page frames
at each step? [5 marks]
4. File system
(a) Suppose you have a file called myfile.dat on a UNIX style filesystem implemented
using inodes with the following properties:
Name: myfile.dat
Size: 1Mb
Created: 2015-02-15T10:43:10
Modified: 2015-02-15T15:04:55
Owner: abc1
Group: user
Mode: 0640
The file system has a block size of 1K, and block addresses require 4 bytes. De-
scribe, with the aid of diagram(s) where appropriate, what the structure of the inode
for myfile.dat would be. [12 marks]
(b) Suppose you have a pair of 1Tb disk drives, and you want to maximise the speed and
space available to your applications. Describe how you would use RAID to achieve
this, and any disadvantages that might result. [5 marks]
Page 4 of 7
CO2017
All candidates
5. Physical & data link layers
(a) In a multi-layer communications model, such as TCP/IP or ISO OSI:
i. explain the difference between a protocol and a service; and [3 marks]
ii. give two examples of real protocols in use at different levels in the TCP/IP model.
[2 marks]
(b) Suppose that the following stream of bits has been received at the physical layer
using triple modular redundancy .
11000001 11110000 11101100
What was the original bit stream? [2 marks]
(c) At the data link layer, suppose that the following stream of bits (4 bytes) is to be
transmitted as a single frame using bit stuffing.
11011111 01111110 01000100 10100011
Show the bit-stream that would actually be transmitted, using the sequence 01111110
as the frame delimiter. [3 marks]
Page 5 of 7
CO2017
All candidates
6. Network layer and socket programming
B
A
D
C
E
2
5
8
3
2
2
Figure 2: Network and link costs
(a) Trace the operation of Dijkstra’s path algorithm by explaining how it would find the
least expensive route from A to E in the network illustrated in Figure 2, 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 com-
puted so far, its predecessor and status. [10 marks]
Page 6 of 7
CO2017
All candidates
1 Scanner console = new Scanner(System.in);
2 Scanner lineTok;
3
4 int num = -1;
5 while (num != 0) {
6 System.out.print("Enter a number: ");
7 lineTok = new Scanner(console.nextLine());
8 num = lineTok.nextInt();
9
10 System.out.printf("The user input %n\n",num);
11
12 lineTok.close();
13 }
14 console.close();
Figure 3: Non-networked code that repeatedly inputs an integer from the user.
(b) Consider the outline code in Figure 3.
Extend the code so that it:
• opens a connection to a server running on host server.org on port 1234;
• repeatedly:
– sends the integer input by the user to the server;
– receives a response from the server and prints it out;
You do not need to write a complete program, and you may assume that both the
user and server always provide suitable values (you do not need to handle error
conditions, or exceptions). [8 marks]
END OF PAPER Page 7 of 7