Midsummer Examinations 2013
CO2017
No. of Pages: 9
No. of Questions: 4
Subject COMPUTER SCIENCE
Title of paper CO2017 — OPERATING SYSTEMS, NETWORKS, AND DIS-
TRIBUTED SYSTEMS
Time allowed Three hours (3 hrs)
Instructions to candidates
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 at-
tempted 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
Continued . . .
2 CO2017
Section A
1. Briefly answer the questions below.
(a) Explain the notions of preemptive or non-preemptive scheduling policies and give
one example of each (justify your answers.) [2 marks]
(b) Assume a process is currently running. Describe the next state of the process if
i. an I/O interrupt occurs.
ii. a clock interrupt occurs. [4 marks]
(c) Describe the concepts of mutual exclusion and critical region. [2 marks]
(d) Briefly describe the Shortest Remaining Time First (SRTF) scheduling policy and
state its advantages over the Shortest Job First (SJF) policy. [1 mark]
(e) 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
1 1 0
2 20 1
3 1 4
4 2 2
i. State which job will be completed second under the Shortest Job First (SJF)
policy.
ii. Compute the waiting time for job 3 when the Shortest Job First (SJF) policy is
used. Briefly explain your answer.
iii. Compute the waiting time for job 3 when the Shortest Remaining Time First
(SRTF) policy is used. Briefly explain your answer. [6 marks]
(f) Explain what a thread is and describe how it differs from a heavyweight process.
[2 marks]
(g) Briefly describe the access in turns algorithm for mutual exclusion of two processes
and explain its main disadvantage. [2 marks]
(h) Explain the concept of page fault and describe a page replacement algorithm.
[3 marks]
(i) A variable partition memory system has at some point in time holes of the following
sizes, in the order given:
10K 20K 40K 15K 30K.
A process of size 14K is to be loaded. Which hole size would be selected, using
i. a best fit policy
ii. a first fit policy
iii. a worst fit policy [6 marks]
(j) Give an example of an encoding that can detect a single bit error, but is not error-
correcting. [1 mark]
Continued . . .
3 CO2017
(k) Consider the following sequences of bits that have been transmitted using the parity
bit encoding. Assume that for each sequence at most one bit was sent in error. State
which sequence was sent correctly.
i. 01100101
ii. 01100100
iii. 01100001 [3 marks]
(l) Explain the concept of contiguous file allocation and state its advantages and disad-
vantages. [3 marks]
(m) State the four conditions that must hold in order for a deadlock to occur and briefly
explain their meanings. [2 marks]
(n) Briefly describe the purpose of the Transmission Control Protocol (TCP) and the User
Data Protocol (UDP). [3 marks]
Continued . . .
4 CO2017
Section B
2. (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
1 10 0
2 3 1
3 5 4
4 2 2
Give the order in which these jobs will be scheduled under the Shortest Remaining
Time First scheduling policy. Calculate the completion and interrupt times for each
job. Assume that the duration of a context switch can be ignored. [5 marks]
(b) Briefly describe Peterson’s solution for mutual exclusion. A short paragraph in En-
glish is enough, but you may include pseudo-code if you wish. [5 marks]
(c) Consider the following two-player game involving a deck of cards numbered from 1
to 52. A dealer places the cards on a table in ascending order of their number, one
after the other. Each of the two players takes exactly 26 cards. The following rules
should be observed.
i. Each card can be retrieved by exactly one player.
ii. The dealer has to wait for the current card to be removed from the table before
placing the next one.
iii. Each player computes the sum of the values of the cards he took. After all
the cards are distributed, the player with the smaller sum is announced as the
winner. A draw is possible.
Consider the following code:
1 class Card{
2 private int n = 0; // strores the value of the last dealt card
3
4 public synchronized void put(int k){
5 this.n = k;
6 System.out.println(“The card is “+n);
7 }
8
9 public synchronized int get(){
10 return n;
11 }
12 }
13
14 class Dealer extends Thread {
15 Card c;
16
Continued . . .
5 CO2017
17 public Dealer(Card c) { this.c =c; }
18
19 public void run(){
20 for(int i=1; i<=52; i++){
21 c.put(i);
22 }
23 }
24 }
25
26 class Player extends Thread {
27 private Card c;
28 private int sum = 0;
29 private String name = new String();
30
31 public Player(Card c, String n) {
32 this.c =c;
33 this.name = n;
34 }
35
36 public void run(){
37 for(int i=1; i<=26; i++) {
38 int tmp = c.get();
39 System.out.println("Player " + name + " got card "+tmp);
40 sum += tmp;
41 }
42 }
43
44 public int getSum(){
45 return sum;
46 }
47
48 }
49
50 public class Game {
51 public static void main(String[] args){
52 Card card = new Card();
53 Dealer d = new Dealer(card);
54 Player p1 = new Player(card, "1");
55 Player p2 = new Player(card, "2");
56 d.start();
57 p1.start();
58 p2.start();
59
60 try{
61 d.join();
62 p1.join();
Continued . . .
6 CO2017
63 p2.join();
64 if (p1.getSum()
69 System.out.println(“Player 2 wins.”);
70 }
71 else {
72 System.out.println(“Draw.”);
73 }
74 }
75 } catch(InterruptedException e) {}
76 }
77 }
i. Explain why the above implementation is incorrect and state which of the rules
of the game are not observed. [5 marks]
ii. Change the code of the Card class from the above code so that all the rules of
the game are observed. Briefly explain why your solution observes the rules of
the game. [10 marks]
iii. Explain the role of the join() methods on lines 61-63 above and describe the
behaviour of the program in their absence. [5 marks]
Continued . . .
7 CO2017
3. (a) State the four layers of the TCP/IP reference model. [2 marks]
(b) The following sequence was transmitted using the stuffing bit protocol
01111110 01111100 11111010 00111100 01111110 11110000 01111110
Write the original sequence and justify your answer. [5 marks]
(c) Explain the role of the network layer and describe the type of services that it can
provide to the transport layer. [2 marks]
(d) Write the 7-bit Hamming code used for transmitting the 4-bit sequence 1001. Specify
the parity bits and the data bits. [5 marks]
(e) Explain why the Hamming code can correct single-bit errors and illustrate this using
the following example. Suppose the Hamming code 010011111 was received and at
most one bit was sent erroneously. Write the original sequence of bits. [6 marks]
(f) Write a Java program implementing a client that connects to a server. Suppose the
server is running on localhost and is listening on port 1234. If the connection is
successful, the server sends a string message to the client. The latter reads the
message and prints it on the standard output. Appropriate exceptions should be
handled. Only the client side is required. [10 marks]
Continued . . .
8 CO2017
4. (a) Consider the following page reference sequence in a virtual paging system
1, 2, 3, 4, 1, 3, 5, 6, 7, 3, 1, 3, 7, 5
Give the number of page faults that would occur for the FIFO replacement algorithm,
assuming that the memory has three page frames? Write down which page is loaded
in the physical memory at each step. Assume that all the frames are initially empty.
[5 marks]
(b) Consider three processes p1, p2, p3 that request several instances of the resources
r1, r2, r3, r4. The existence resource vector is
2 3 1 3
Suppose that the current allocation matrix of resources is
0 1 0 1
0 1 0 0
1 0 0 1
and the request matrix is
1 0 0 1
0 2 0 0
1 3 1 2
Explain how Banker’s deadlock detection algorithm works and illustrate this using
the example above. Specify the order in which the processes will run and write the
vector of available resources after each step.
[10 marks]
(c) Trace the operation of Dijkstra’s algorithm by explaining how it would find the least
expensive route from A to E in the network illustrated below, 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. [7 marks]
B
A
C
D
E
2
3
8
3
9
6
1
Continued . . .
9 CO2017
(d) Explain the routing technique known as flooding in the network layer of the computer
networks. [3 marks]
(e) Consider three processes A, B and C that require several instances of a resource.
Assume that 7 instances of the resource exist and consider the following state:
Process Has Max
A 0 3
B 2 6
C 1 7
The middle column indicates how many resources each process already has. The
last column specifies how many instances each process needs in order to be com-
pleted.
Specify whether the state above is safe or not. If yes, give a sequence of allocations
that allows all processes to complete. [5 marks]