程序代写代做代考 algorithm Java exam.dvi
exam.dvi
Midsummer Examinations 2011
CO2017
No. of Pages: 7
No. of Questions: 7
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. Process Mangement.
(a) What is the difference between a program and a process? [3 marks]
(b) What is the difference between preemptive and non-preemptive scheduling?
[3 marks]
(c) Why is access in turns not a very good idea for interprocess communication? Briefly
explain your answer. [4 marks]
2. Memory Management.
(a) What is segmentation? [3 marks]
(b) Describe the best fit algorithm. What is its main disadvantage? [3 marks]
(c) Describe the Not Recently Used algorithm. [4 marks]
3. File Management
(a) What are the main advantages and the main disadvantage of linked list allocation
compared to the contiguous one? [3 marks]
(b) How does the file allocation table overcome the disadvantage of the linked list allo-
cation? [3 marks]
(c) Describe the purpose and structure of the I-node. [2 marks]
(d) Why is using I-nodes better than using file allocation tables. [2 marks]
4. Networks.
(a) Let the word 10110 be the result of the error correcting parity encoding with the parity
bit being the last one. Is the encoding correct? Explain your answer. [3 marks]
(b) What is acknowledged connectionless service? [3 marks]
(c) Describe the idea of routing by flooding. What is its disadvantage? [4 marks]
Section B
5. (a) Consider three processes Pr1, Pr2, and Pr3 with respective durations 10,20,25 mil-
liseconds. Draw the diagram of CPU usage under the Round-Robin scheduling algo-
rithm with the quantum time equal 5 milliseconds. Assume that all processes start at
the same time and that the context switch duration is negligibly small. [5 marks]
(b) In Peterson’s algorithm (the part to be performed before accessing a shared re-
source) a process declares its interest in accessing the resource and then gener-
ously states that the current turn is of the other process. If these two operations are
swapped then the resulting algorithm does not establish a valid interprocess commu-
nication because the two processes can access the shared resource simultaneously.
Show a scenario of how this can happen. [10 marks]
Continued . . .
3 CO2017
(c) Assume that two processes want to access the same resource. In order to do this,
they use a shared variable lock, initially equal 0, and proceed in the following way
(both processes execute the same algorithm).
while ( lock == 1){;}
lock = 1;
Access the resource
lock = 0;
Demonstrate that this is not a good method of interprocess communication. Hint—
Show a scenario under which processes executing this algorithm can access a re-
source simultaneously. [15 marks]
6. Consider the Java program implementing the Readers-Writers protocol (see the Appendix).
(a) Suppose that the function EndReading() does not run noti f y(). What will be the
effect for the whole program? Explain your answer. [6 marks]
(b) Suppose that the function WriteContent() does not contain the while-loop with
wait() inside. What will be the effect for the whole program? Explain your answer.
[6 marks]
(c) Suppose that the function ReadContent() is made synchronized. What will be the
effect for the whole program? Explain your answer. [6 marks]
(d) Suppose that readers do not execute StartReading() before executing ReadContent().
What will be the effect for the whole program? Explain your answer. [6 marks]
(e) Write down a scenario where a reader reads the same content twice. [6 marks]
7. (a) The following sequence is transmitted using the stuffing bit protocol (no additional
error correcting or detecting encoding has been used):
01111110 1111101000000 01111110 1111100000 01111110
What is the original sequence?
Although not required, you are strongly encouraged to present the decoding steps
so in case you make a mistake in a digit, you will be able to still get most of the marks
since the grader will see that you understand the idea. [7 marks]
(b) Consider transmitting 4-bit message 0011 using 7-bit Hamming code. Assume that
during the transmission any bit of your choice has been flipped (for example, the
message becomes 1011). Demonstrate how the additional bits of the Hamming code
help to correct this error. [9 marks]
(c) Consider a communication graph for nodes a,b,c,d,e, f where the numbers repre-
sent delays of the respective connections. For the given graph, compose a distance
vector routing table for each node.
Continued . . .
4 CO2017
a
b
c
d
e
f
10
10
10
10
10
30
40
30
[7 marks]
(d) Assume that in the communication graph from part (c) we want to transmit a message
from a to f . Show how this path can be found using only the data vector routing
tables. [7 marks]
Continued . . .
5 CO2017
Appendix: JavaProgram for Question 6 (3 pages)
/*The main thread for readers and writers*/
class MainReadWrite
{
public static void main(String args[])
{
RWStorage st=new RWStorage();
Reader rt1= new Reader(st);
Reader rt2= new Reader(st);
Writer wt1=new Writer(st);
}
}
/*The reader class*/
class Reader implements Runnable
{ RWStorage stor;
int MyContent;
Thread t;
public Reader(RWStorage st)
{
stor=st;
MyContent=0;
t=new Thread(this);
t.start();
}
public void run()
{ int i=0;
for(i=0;i<10;i++)
{
stor.StartReading();
MyContent=stor.ReadContent();
System.out.println("The content is "+MyContent);
stor.EndReading();
}
}
}
Continued . . .
6 CO2017
/*The writer class*/
class Writer implements Runnable
{ RWStorage stor;
Thread t;
public Writer(RWStorage st)
{
stor=st;
t=new Thread(this);
t.start();
}
public void run()
{ int i=0;
for(i=0;i<10;i++)
{
System.out.println("Content to be written "+i);
stor.WriteContent(i);
}
}
}
class RWStorage
{
int NumReaders;
int content;
public RWStorage()
{
NumReaders=0;
content=0;
}
synchronized public void WriteContent(int NewContent)
{
while (NumReaders>0)
{
try {
wait();
Continued . . .
7 CO2017
}
catch (InterruptedException e)
{
System.out.println(“Something wrong happens with writing”);
}
}
System.out.println(“A writer has just entered”);
content=NewContent;
System.out.println(“A writer is about to leave”);
}
public int ReadContent()
{
return content;
}
synchronized public void StartReading()
{
NumReaders++;
System.out.println(“A reader has just entered,
currently there are “+NumReaders+” in the system”);
}
synchronized public void EndReading()
{
System.out.println(“A reader is about to leave,
there will be “+(NumReaders-1)+” Readers in the system “);
NumReaders–;
if (NumReaders==0)
{
notify();
}
}
}
