CO2017 Examination — Solutions
This copy generated 25th March 2013.
Title of paper CO2017 — Operating Systems, Networks, and Dis-
tributed Systems
Examination Session Midsummer Examinations 2013
Time allowed Three hours (3 hrs)
Instructions This paper contains two sections, Section A and
Section B.
Attempt all of Section A.
There are three questions in Section B. All questions
from Section B may be attempted but only the best
two answers will be taken into account.
Section A is worth 40 marks. Each of the questions in
Section B is worth 30 marks.
No calculator is allowed
Number of questions 4
1
Section A
2
Answer to question 1
(a) A non-preemptive scheduling algorithm lets a process run until it finishes or blocks on I/O
or waiting for another process. A preemptive scheduling algorithm allows a process to
run for a specified amount of time and requires a clock interrupt. The First Come First
Served policy is non-preemptive. Round Robin is a preemptive scheduling algorithm since
it requires clock interrupts.
(b) i. blocked
ii. ready
(c) In a concurrent program, multiple processes/threads may share a resource or object. The
region inside each concurrent process that accesses or updates the shared resource is
called critical region with respect to the shared resource. In order to avoid multiple updat-
ings of the shared resource at the same time, processes/threads must mutually exclude
each other from entering their critical sections at the same time.
(d) SRTF is a preemptive version of SJF in which the scheduler chooses the process having
the shortest remaining time. The advantage of this algorithm is that new short jobs are
finished quicker.
(e) i. Job 2 is completed second.
ii. Job 3 arrives in the ready queue at 4ms, that is, after job 1 is completed and job 2
has already started. Since SJF is non-preemptive, job 3 is executed only after job 2
is completed, so the start time for job 3 is 21ms. Hence the waiting time is 17ms.
iii. The waiting time of job 3 under SRTF policy is 0ms. When job 3 arrives in the ready
queue job 2 is interrupted.
(f) A thread is an independent sequence of execution within a program. Sometimes it is
called a lightweight process.
Differences:
• A thread itself is not a program and cannot run on its own. It runs within a program
• A thread is usually created and/or controlled by a process
(g) The resource is associated with a shared variable turn, that can be either 1 or 2. One
process can access the resource when turn is 1, the other when turn is 2. When it’s not
its turn, each process is busy waiting. The disadvantage of this approach is that a process
can be blocked even if the other process is not interested in accessing the resource.
(h) A page fault occurs when a program accesses a page that is mapped in the virtual ad-
dress space, but not loaded in physical memory. Page faults are handled by the memory
management unit. For the second part, the students might describe for example the Least
Frequently Used replacement algorithm.
(i) i. 15K
ii. 20K
3
iii. 40K
(j) A possible answer is the parity bit encoding. Full marks are given only if a brief justification
is included.
(k) The first sequence of bits was sent correctly because the number of 1s is even and at most
one bit was sent in error.
(l) Contiguous allocation assigns contiguous blocks of memory to a file. Advantages:
i. Simple to implement: needs to store the first block address and its length.
ii. The read/write heads have to move very little.
iii. Resilient to disk faults: damage to a single block results in only localised loss of data
iv. Allows easy random access.
Disadvantages:
i. Need to “guess” the size of the file when it is first created
ii. Fragmentation: as files are deleted, holes appear.
(m) Mutual exclusion, hold and wait, no preemption, circular wait. Full marks are given only
when short explanations are inlcuded.
(n) Bookwork:
• The Transmission Control Protocol (TCP) is a connection-oriented protocol, pro-
viding a reliable service over an unreliable internetwork; it is designed to adapt to
variations in network conditions, and to deal with various sorts of errors.
• The User Data Protocol (UDP) is a very simple connectionless protocol, which ba-
sically just adds a transport header to IP; it is suitable for client-server applications
involving a single request and single response.
4
Section B
5
Answer to question 2
(a) The jobs are executed as follows:
Job Start time Completion/Interrupt time Comments
1 0 1 Job 2 arrives
Job 1 has 9ms left, so is interrupted
2 1 2 Job 4 arrives,
Job 2 has 2ms left, so continues
2 2 4 Job 2 completed, Job 1, 3, 4 ready
4 4 6 Job 4 completed
Jobs 1,3 ready
3 6 11 Job 3 completed, Job 1 ready
1 11 20 Job 1 completed
(b) Bookwork.
(c) Although put and get are synchronized nothing prevents the players to get the same card
from the table. Similarly, the dealer may release the next card before the current one has
been removed.
(d) A possible solution is:
class Card{
private int n = 0; // strores the value of the last dealt card
private boolean cardSet = false; // cardSet is true if a new card is ready
public synchronized void put(int k){
while (cardSet)
try{
wait();
} catch (InterruptedException e){}
this.n = k;
System.out.println(“The card is ” + n);
cardSet = true;
notifyAll();
}
public synchronized int get(){
while(!cardSet)
try {
wait();
} catch (InterruptedException e){}
cardSet = false;
notify();
return n;
}
}
6
(e) The main thread pauses it’s execution until the threads d, p1 and p2 have finished their
execution. In the absence of join() the winner may be announced before the game has
actually finished.
7
Answer to question 3
(a) Bookwork.
(b) To compute the original message, remove the delimiter byte 01111110 and the flag bit 0
occuring after every five 1s. We get 011111011111100011110011110000
(c) Bookwork.
(d) The 7-bit Hamming code is 0011001. The bits are indexed from 1 to 7. The parity bits
are those bits indexed by 1,2 and 4. The data bits are indexed by 3,5,6,7. Students will
receive 1 mark for correctly specifying the data bits and 1 mark for each correct parity bit.
(e) If one bit is erroneously sent, it affects exactly the parity bits corresponding to its binary
representation. In this example, the parity bits indexed by 1, 2 and 4 are wrong. Hence
the bit in error is the one indexed by 1+ 2+ 4 = 7. To retrieve the original message, we
have to select the content bits (with indexes not a power of 2) and to swap the bit in error.
Hence the original sequence is 01101.
(f) A possible solution:
import java.io.*;
import java.net.*;
/**
* Simple client for receiving a message from a server.
*/
public class SimpleClient {
public static void main(String[] args) throws IOException {
BufferedReader input = null;
Socket s = null;
try {
s = new Socket(“localhost”, 1234);
input = new BufferedReader(new InputStreamReader(s.getInputStream()));
} catch (UnknownHostException e) {
System.err.println(“Can’t find localhost.”);
System.exit(1);
} catch (IOException e) {
System.err.println(“Couldn’t get I/O for ”
+ “the connection to localhost.”);
System.exit(1);
}
String answer = input.readLine();
System.out.println(answer);
input.close();
s.close();
8
System.exit(0);
}
}
9
Answer to question 4
(a) The progress is as follows, where bond italic font means a page fault.
Page Reference Sequence: 1 2 3 4 1 3 5 6 7 3 1 3 7 5
Memory: 1 1 1 4 4 4 4 6 6 6 1 1 1 1
– 2 2 2 1 1 1 1 7 7 7 7 7 5
– – 3 3 3 3 5 5 5 3 3 3 3 3
There are 11 page faults.
(b) The first part of the question is bookwork. The initial available resource vector is
1 1 1 1
Initially all process are unmarked. We can run the first process since the first row of the
request matrix is (pointwise) less than the available resource vector. After process one
finishes its execution it releases all the resources. We mark p1 and the available resource
vector becomes
1 2 1 2
We have two unmarked processes: p2 and p3. Of these, we can only run p2. We mark p2
and the available resource vector becomes
1 3 1 2
Finally we mark p3 and all the existing resources become available. No deadlock is
present.
10
(c)
Node Cost Predecessor Status
Working node: A
A 0 Permanent
B 3 A Temporary
C ∞ A Temporary
D 9 A Temporary
E ∞ A Temporary
Working node: B
A 0 Permanent
B 3 A Permanent
C 5 B Temporary
D 9 A Temporary
E 11 B Temporary
Working node: C
A 0 Permanent
B 3 A Permanent
C 5 B Permanent
D 8 C Temporary
E 11 B Temporary
Working node: D
A 0 Permanent
B 3 A Permanent
C 5 B Permanent
D 8 C Permanent
E 9 D Temporary
Working node: E
A 0 Permanent
B 3 A Permanent
C 5 B Permanent
D 8 C Permanent
E 9 D Permanent
So the best route is A–B–C–D–E with a total cost of 9.
(d) Bookwork.
(e) The state is safe. The sequence of allocations that allows all processes to complete is the
following:
Process Has Max
A 0 3
B 2 6
C 1 7
Free: 4
11
Process Has Max
A 0 3
B 6 6
C 1 7
Free: 0
Process Has Max
A 0 3
B 0 –
C 1 7
Free: 6
Process Has Max
A 3 3
B 0 –
C 1 7
Free: 3
Process Has Max
A 0 –
B 0 –
C 1 7
Free: 6
Process Has Max
A 0 –
B 0 –
C 7 7
Free: 0