程序代写代做代考 file system Java scheme data structure algorithm 1

CO2017 Examination — Draft Questions and Solutions

This copy generated 4th June 2014.

Title of paper CO2017 — Operating Systems, Networks, and Dis-
tributed Systems

Candidates All candidates

Department Computer Science

Examination Session Midsummer Examinations 2014

Time allowed Three hours

Instructions 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 attempted 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.

Calculators NOT PERMITTED

Books/statutes NOT PERMITTED

Additional Stationery Not required

Number of questions 13

Briefly answer the questions below.

Question 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]

Answer — total marks for this question: 4

Process cannot proceed in a RUNNING state as it is waiting for some I/O to complete, e.g. wait-
ing for a file to be read in from 2nd-ary storage. When I/O is complete, process will move to
READY state and re-enter the run queue.

Question 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]

Answer — total marks for this question: 5

Bounded buffer is data structure managed by a few variables and add and remove methods.
add and remove both need to update the data structure, but must not do so at the same
time, or buffer will end up in unpredictable/inconsistent state. The methods are therefore critical
regions, and mutual exclusion ensures that only one at a time can be modifying the shared data
structure.

Question 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 interleavings are
possible, and give at least 3 distinct examples. [3 marks]

Answer — total marks for this question: 3

Student should make some attempt to simplify the ratio.

C4+34 =
7!

4!3!
=

5040
144

=
7.6.5
3.2.1

= 7.5 = 35

p1;q1; p2;q2; p3;q3; p4;

p1;q1;q2;q3; p2; p3; p4;

q1;q2; p1;q3; p2;q3; p4;

etc.

Question 4.

In a virtual memory system, what is the page table? Include an outline of the data structure and
its typical content. [5 marks]

Answer — total marks for this question: 5

Page table relates virtual pages of memory to physical page frames.

present/absent is the virtual page currently loaded in a physical page frame? If so, include the
address of the physical page frame.

dirty bit has the page been modified since it was loaded?

referenced bit has the page been accessed (recently)

Question 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

[3 marks]

Answer — total marks for this question: 3

(a) 20K

(b) 30K

Question 6.

What is triple modular redundancy? Briefly define code rate and Hamming distance be-
tween valid codes and show what they are for triple modular redundancy. [4 marks]

Answer — total marks for this question: 4

Repeat each bit three times. Can detect & correct all single bit errors. Can detect all double bit
errors.

Code rate is ratio of redundancy data to content. It is 1/3 for TMR.

Hamming distance is number of bit flips required to change one valid code word to a different
valid code word: 3 for TMR.

Question 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]

Answer — total marks for this question: 3

5th row, 3rd column is flipped. Row 5 parity should be 0. Col 3 parity should be 0.

Question 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]

Answer — total marks for this question: 5

File A file descriptor has a pointer to block 1.

File B file descriptor has a pointer to block 2.

N.B, this is content of blocks (not a FAT)

Equivalent diagram with blocks and arrows for pointers would be preferable.

block no. pointer block data
1 10 . . .
2 3 . . .
3 4 . . .
4 11 . . .
5 12 . . .
6 . . . .
7 . . . .
8 . . . .
9 . . . .

10 5 . . .
11 null . . .
12 null . . .

Question 9.

In the physical layer of a network, what is Manchester encoding, and why is it an improvement
over a system that simply transmits distinct voltages for zero and one bits? [3 marks]

Answer — total marks for this question: 3

Diagram of Manchester encoding goes here…

Want to have a voltage transition in every clock cycle so that both 1 and 0 bits are clearly distinct
from a dropped line.

Question 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]

Answer — total marks for this question: 5

(Assuming buffered input here; obviously output would be OK too.) 1st buffer can be emptied to
process while 2nd buffer is filling from input device. Then reverse the process when 2nd buffer
is full. Means that the input device has no idle time while it waits for the process to empty the
buffer.

Question 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 ex-
ample 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]

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

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

(c) A concurrent program Nondeterminism involving resource sharing among processes
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]

Answer — total marks for this question: 30

(a) The jobs are executed as follows:

Time Running J Queue Comments
0 1 (1,9) J1 arrives
1 2 (2,1) (1,8) J2 arrives, interrupts J1
2 1 (1,8) J2 complete
3 3 (3,6) (1,7) J3 arrives, interrupts J1
6 4 (4,2) (3,3) (1,7) J4 arrives, interrupts J3
8 3 (3,3) (1,7) J4 complete, J3 running
11 1 (1,7) J3 complete, J1 running
18 – – J1 complete

J1: completion at 18; wait time of 9
J2: completion at 2; wait time of 0
J3: completion at 11; wait time of 2
J4: completion at 8; wait time of 0

ii.

Time Running Run Queue Comments
0 1 (1,9) J1 arrives
1 1 (1,8), (2,1) J2 arrives
3 1 (1,7), (2,1) (3,6) J3 arrives
5 2 (2,1), (3,6) (1,4) quantum
6 3 (3,6), (1,4) (4,2) J2 complete; J4 arrives
11 1 (1,4), (4,2) (3,1) quantum
15 4 (4,2), (3,1) J1 complete
17 3 (3,1) J4 complete
18 – – J3 complete

J1: completion at 15; wait time of 6
J2: completion at 6; wait time of 4
J3: completion at 18; wait time of 9
J4: completion at 17; wait time of 9

(b) The initial Avail resource vector is

A B C D
0 1 1 0

Initially all process are unmarked.

Note that Req(P3)≤ Avail. So P3 can run and release its resources. We mark P3 and add
its resources to Avail

A B C D
4 1 1 1

Note that Req(P1)≤ Avail. So P1 can run and release its resources. We mark P1 and add
its resources to Avail

A B C D
4 1 4 2

But now neither Req(P2)≤ Avail nor Req(P4)≤ Avail so deadlock has occurred.

The use of the semaphores ensures that the statement in t2 cannot be executed before
t1 is executed. However, either t1 or the task3() in the main process can go first.
And if t1 goes first, either t2 or task3() in the main process can follow.

The possible interleavings are as follows:

i. If the interleaving is t1 ⇒ t2 ⇒ task3() in the main process, finally x == 15.
ii. If the interleaving is t1 ⇒ task3() in the main process ⇒ t2, finally x == 13.
iii. If the interleaving is task3() in the main process ⇒ t1 ⇒ t2, finally x = 5.

Question 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 expla-
nation 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]

Answer — total marks for this question: 30

(a) Page fault counting

Students might forget the first 5 page faults as the initially empty page frames fill
up. . . .

i. Requests come in this order

1,2,0,5,9,10,5,1,3,8,5,16,1,2,5,14

Page frame contents follow this sequence (page faults indicated by bold), next page
request shown:

[ 1,2,0,5,9 ] 10

[ 10,2,0,5,9] 5

[10,2,0,5,9] 1

[10,1,0,5,9] 3

[10,1,3,5,9] 8

[10,1,3,8,9] 5

[10,1,3,8,5] 16

[16,1,3,8,5] 1

[16,1,3,8,5] 2

[16,2,3,8,5] 5

[16,2,3,8,5] 14

[16,2,14,8,5] –

Total of 5+8 page faults.

ii. Requests come in this order

1,2,0,5,9,10,5,1,3,8,5,16,1,2,5,14

Page frames contents follow this sequence, with corresponding clock state.
Frames Next page Clock status

Bold for page fault Bold for current clock hand
[ 1,2,0,5,9 ] 10 [1,1,1,1,1]

. . . go round the clock

[ 1,2,0,5,9 ] 10 [0,0,0,0,0]

[ 10,2,0,5,9] 5 [1,0,0,0,0]

[ 10,2,0,5,9] 1 [1,0,0,1,0]

[10,1,0,5,9] 3 [1,1,0,1,0]

[10,1,3,5,9] 8 [1,1,1,1,0]

[10,1,3,5,8] 5 [1,1,1,0,1]

[10,1,3,5,8] 16 [1,1,1,1,1]

. . . go round the clock

[10,1,3,5,8] 16 [0,0,0,0,0]

[16,1,3,5,8] 1 [1,0,0,0,0]

[16,1,3,5,8] 2 [1,1,0,0,0]

[16,1,2,5,8] 5 [1,0,1,0,0]

[16,1,2,5,8] 14 [1,0,1,1,0]

[16,1,2,5,14] [1,0,1,0,0]
5+7 page faults.

(b) Directory is an association of file(or directory) names to i-nodes, by i-node number. I-nodes
are stored in a table, referenced by i-node number. There is a special root (/) directory.
I-node contains file meta-data (creation date, permissions, /etc), plus direct links to first
blocks of a file’s data, plus (for large files) indirect links to blocks containing further links to
the file’s data.

(c) (using values 0-9 as representatives of real bytes. . . ) Need to identify a special delimiter
byte (e.g. 0), and an escape/control byte (e.g. 1).

• Each frame will begin and end with a delimiter byte.
• To include the delimiter byte as data within the frame, precede it with an escape byte.
• To include the escape byte in the frame, precede it with an escape byte.

E.g, if the data to be transmitted is 543120068, then it would actually be transmitted as
05431121010680. There is a 0 at each end, and each 0 or 1 in the data is preceded by a
1.

(d) Notes on Hamming (not required in student answer, but if correct explanation is given in
support of faulty calculation, then some credit should be given)

The parity bits are those bits indexed by 1,2 and 4. The data bits are indexed
by 3,5,6,7. Students need to identify which parity bits are incorrect, and hence
which bit is incorrect, and then extract the corrected original data.

If one bit is erroneously sent, it affects exactly the parity bits corresponding to
its position in binary representation.

Consider each of the three parity groups:

i. 0111101: wrong parity
0111101: wrong parity
0111101: wrong parity
parity error in group 1,2 & 4; so error is in bit 7
Original data 1100

ii. 1101001: OK parity
1101001: OK parity
1101001: OK parity
No parity errors
Original data 0001

iii. 1011101: OK parity
1011101: OK parity
1011101: wrong parity
parity error in group 4; error was only in a parity bit
Original data 1101

..B.

. D.

.
9

Figure 5: Network and link costs

Question 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 connection.
[2 marks]

(b) Trace the operation of Dijkstra’s algorithm by explaining how it would find the least expen-
sive 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]

• 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;

1 public class QuoteGenerator {
2 public QuoteGenerator() { … }
3 public String GetQuote() {
4 // This might take some time…
5 }
6 }

Figure 6: Outline of QuoteGenerator

• the handler thread should use the QuoteGenerator class (described in Figure 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]

Answer — total marks for this question: 30

(a) TCP/IP.

i. Application Layer, Transport layer, Internet/network layer, link/physical layer

ii. HTTP, TCP, IP, WiFi/ethernet

iii. radio waves, copper cable, fibre optic, satellite uplink

(b)
Node Cost Predecessor Status

Working node: A
A 0 Permanent
B 3 A Temporary
C ∞ A Temporary
D 9 A Temporary
E ∞ A Temporary
F ∞ A Temporary

Working node: B
A 0 Permanent
B 3 A Permanent
C 5 B Temporary
D 9 A Temporary
E ∞ A Temporary
F 11 B Temporary

Working node: C
A 0 Permanent
B 3 A Permanent
C 5 B Permanent
D 8 C Temporary
E 7 C Temporary
F 9 C Temporary

Working node: E (lowest total of Temporary nodes)
A 0 Permanent
B 3 A Permanent
C 5 B Permanent
D 8 C Temporary
E 7 C Permanent
F 8 E Temporary

Working node: D
A 0 Permanent
B 3 A Permanent
C 5 B Permanent
D 8 C Permanent
E 7 C Permanent
F 8 E Temporary

Working node: F
A 0 Permanent
B 3 A Permanent
C 5 B Permanent
D 8 C Permanent
E 7 C Permanent
F 8 E Permanent

So the best route is A–B–C–E–F with a total cost of 8.

Algorithm can stop after making Node E permanent, as both

• there is a route to the F (final) node; AND
• there are no temporary nodes with a smaller cost than the cost already on F.

import java.io.*;
import java.net.*;

class QuoteGenerator {
QuoteGenerator() {
}
public String getQuote() {

return new String(“Hello”);
}

}

class Handler extends Thread {
Socket client;
QuoteGenerator quoteGen;
public Handler (Socket cl, QuoteGenerator qg) {

client = cl;
quoteGen = qg;

}
public void run() {

String quote = quoteGen.getQuote();
try {

OutputStream out = client.getOutputStream();

byte buff[] = quote.getBytes();
out.write(buff);
// OR
//OutputStream out = client.getOutputStream();
//out.writeUTF(quote);

} catch (IOException e) {e.printStackTrace();}
}

}

public class QuoteServer extends Thread {
public void run() {

int port=1234;
try {

ServerSocket server = new ServerSocket(port);
QuoteGenerator qGen = new QuoteGenerator();
while (true) {

Socket client = server.accept();
// create and start a handler
Handler h = new Handler(client,qGen);

h.start();
}

} catch (IOException e) { e.printStackTrace(); }
}
public static void main(String[] args) {

QuoteServer server = new QuoteServer();
server.start(); }

}

Published by admin

Leave a Reply Cancel reply