1
CO2017 Examination — Draft Questions and Solutions
This copy generated 4th May 2016.
Title of paper CO2017 — Operating Systems, Networks, and Dis-
tributed Systems
Version 1
Candidates All candidates
Department Computer Science
Examination Session Midsummer Examinations 2015
Time allowed Three hours
Instructions Attempt all questions. Full marks may be obtained
only if all questions are answered.
Calculators No
Books/statutes No
Own Books/statutes/notes No
Additional Stationery No
Number of questions 6
2
Question 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 appro-
priate, 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]
3
Answer — total marks for this question: 15
(a) (Bookwork) A program is an executable: code. A process is a program that is actively be-
ing executed on a system — includes the state of the program: memory state (heap,
swap), process counter (next instruction), process owner, associated resources (open
files, devices)
(b) Simple systems with limited multi-tasking ambitions. E.g. strictly batch processing system;
systems with single user single process; systems with limited memory/cpu capacity limits
the benefits of more pre-emptive scheduling.
(c) • FCFS
Time Running Queue Complete(waiting) Comments
0 A
1 A B
5 A B,C
8 A B,C,D
10 B C,D A(0)
15 C D B(9)
17 D C(10)
19 D(9)
• SJF
Time Running Queue Complete(waiting) Comments
0 A
1 A B
5 A C,B
8 A C,D,B
10 C D,B A(0)
12 D B C(5)
14 B D(4)
19 B(13)
4
Question 2.
Threads & concurrency in Java
Consider the (outline) code in Figure 1. The code is supposed to be a very simple simulation
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]
5
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
6
Answer — total marks for this question: 20
(a) (Interleaving) Statements in concurrent threads will execute in non-deterministic sequence.
Key observation is that balance = balance+X may not be atomic.
OK interleaving:
balance Spender Saver
1000
acc.withdraw(501)
balance-501 (499)
acc.deposit(401)
499 balance=
balance+401 (900)
900 balance=
Undesirable interleaving:
balance Spender Saver
1000
acc.withdraw(501)
balance-501 (499)
acc.deposit(401)
balance+401 (1401)
499 balance=
1401 balance=
(b) balance is the critical resource, and any code that changes it is a critical section. Only
one thread at a time should be executing code in critical sections.
Code in deposit method (line 5) is critical.
Code in withdraw method (line 6) is critical.
(c) Simplest method is to make the deposit and withdraw methods syncronized.
In Java this implements a monitor which automatically ensures mutual exclusion (amongst
threads accessing a particular instance).
public synchronized void deposit(int d) {balance+=d;}
public synchronized void withdraw(int w) {balance-=w;}
(d) Pattern is
while (! safe) { wait(); }
Do Critical Stuff
notifyAll();
So, in this case need to modify withdraw method to wait until balance is positive:
public syncronized void withdraw(int w) {
while (balance-w<0) {wait();}
balance -= w;
7
notifyAll();
}
8
Question 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]
9
Answer — total marks for this question: 20
(a) (Bookwork) Memory hierarchy describes inverse speed/size relationship between different
types of memory, and their proximity to the processor.
So, processor registers are at one extreme, and are very small, but very fast. Hierarchy
goes up through levels of on-processor cache, to traditional dynamic RAM, and then on to
2ndary storage.
There is generally an order of magnitude (or more) difference in speed and size between
levels in the hierarchy.
Working set is the set of VM pages that are being used by an active process. Want to
avoid the very significant time penalty of having to swap them out/in to/from swap storage
on disk.
(b) (Bookwork) Swapping in a direct memory model swaps the entire process memory as a
single chunk. Memory is allocated for the process as a whole, and so when the process
swaps out, the entire allocated memory needs to be swapped to 2ndary storage.
Virtual memory system divides a process’s memory into pages of uniform, relatively small
size (e.g. 4K). Only the pages that are actively being used need to be stored in real memory
(page frames).
This means a much more fine grained approach can be applied. Only relatively small
amounts of data need to be moved to/from 2ndary storage when swapping occurs.
(c) i. NRU
1,2,11,6,9,5,11,2,3,15,14,2,11,1,6,17,2
Use 1/0 subscript to indicate recently used (referenced).
0 1 2 3 4 next
11 21 111 61 91 5
10 20 110 60 90 5
51 20 110 60 90 11
51 20 111 60 90 2
51 21 111 60 90 3
51 21 111 31 90 15
51 21 111 31 151 14
50 20 110 30 150 14
141 20 110 30 150 2
141 21 110 30 150 11
141 21 111 30 150 1
141 21 111 11 150 6
141 21 111 11 61 17
140 20 110 10 60 17
171 20 110 10 60 2
171 21 110 10 60
5 initial + 7 subsequent page faults
10
ii. LRU
1,2,11,6,9,5,11,2,3,15,14,2,11,1,6,17,2
Use subscript to indicate time of last reference.
0 1 2 3 4 next
11 22 113 64 95 5
56 22 113 64 95 11
56 22 117 64 95 2
56 28 117 64 95 3
56 28 117 39 95 15
56 28 117 39 1510 2
56 211 117 39 1510 11
56 211 1112 39 1510 1
113 211 1112 39 1510 6
113 211 1112 614 1510 17
113 211 1112 614 1715 2
113 216 1112 614 1715
5 initial + 6 subsequent page faults
11
Question 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. Describe, 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]
12
Answer — total marks for this question: 17
(a) 1K blocks, and 4 byte block addresses mean that 1 block can hold 256 block addresses.
Also a 1Mb file is going to need 1024 blocks.
First 12 blocks can be included in the inode. Next 256 blocks can be stored in the first
(single) indirect block. Then use first four double indirect block links to link to 3 more single
indirect blocks, giving 768 more block addresses, only 756 of which are needed. No triple
indirect blocks are needed.
Something like this:
bigfile.dat
abc1
users
0644
2015-02-15T10:43:10
2015-02-15T15:04:55
0
inode
name
owner
group
mode
creation
modified
direct link 1
direct link 2
direct link 12
indirect link 1
indirect link 2
indirect link 3
block 1
block 2
block 12
single
indirect block
1
2
256
b 2,1
b 2,2
b 2,3
0
0
double
indirect block
1
2
3
4
256
block 2,1
1
2
256
block 2,2
1
2
256
0
0
block 2,3
1
2
217
218
256
block 13
block 14
block 268
block 269
block 270
block 525
block 526
block 527
block 782
block 783
block 784
block 1000
(b) (Bookwork) Describe RAID0 with striping.
One mark for mentioning RAID0; up to three more marks for describing striping, ideally
with a diagram to illustrate ; and one for describing danger that a single error on either disk
can result in total data loss.
13
Question 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]
14
Answer — total marks for this question: 10
(a) Essentially bookwork
i. A protocol operates between peers at the same level in the multi-level model. A layer
provides a service to next higher layer on the same host; and uses the service of the
next lower layer.
ii. Example protocols: Manchester or similar at physical level; sliding window at data;
TCP protocol used to transfer data at the transport layer; http protocol at the applic-
ation layer.
(b) 1 0 1 1 0 1 1 0
(c) 01111110 11011111 00111110 10010001 00101000 11 01111110
15
Question 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 rep-
resent 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 prede-
cessor and status. [10 marks]
16
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]
17
Answer — total marks for this question: 18
(a)
Node Cost Predecessor Status
Working node: A
A 0 Permanent
B 5 A Temp
C 2 A Temp
D ∞ A Temp
E ∞ A Temp
Working node: C
A 0 Permanent
B 5 A Temp
C 2 A Permanent
D 5 C Temp
E ∞ A Temp
Working node: B
A 0 Permanent
B 5 A Permanent
C 2 A Permanent
D 5 C Temp
E 13 B Temp
Working Node: D
A 0 Permanent
B 5 A Permanent
C 2 A Permanent
D 5 C Permanent
E 7 D Temp
Working Node: E
A 0 Permanent
B 5 A Permanent
C 2 A Permanent
D 5 C Permanent
E 7 D Permanent
Path is ACDE
(b) Socket server = new Socket("server.org", 1234);
System.out.println("Connected to " + server.getInetAddress());
BufferedReader rdr = new
BufferedReader(new InputStreamReader(server.getInputStream(),
"UTF-8"));
Writer out = new OutputStreamWriter(server.getOutputStream());
Scanner console = new Scanner(System.in);
Scanner lineTok;
18
int num = -1;
while (num != 0) {
System.out.print("Enter a number: ");
lineTok = new Scanner(console.nextLine());
num = lineTok.nextInt();
out.write(num + "\r\r");
out.flush();
String response = rdr.readLine();
System.out.printf("Response: %s\n",response);
lineTok.close();
}
console.close();
server.close();