程序代写代做代考 algorithm Midsummer Examinations 2012
Midsummer Examinations 2012
CO2017
No. of Pages: 5
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 Management.
(a) Which type of scheduling (preemptive or non-preemptive) requires clock interrupts?
Explain your answer. [3 marks]
(b) What is the difference between a deadlock and a non-safe state? [3 marks]
(c) Suppose that the operating system uses Round-Robin scheduling where the duration
of a quantum is the same as the time required for a context switch. What is the
negative effect of such a setting? [4 marks]
2. Memory Management.
(a) Why do multitasking operating systems never allow user programs to write to partic-
ular memory addresses like 1000? [3 marks]
(b) The implementation of the Least Recently Used algorithm requires a register count-
ing instructions from the invocation of the operating system. Suppose this register
has 64 bits. Why is overflow not a problem? [3 marks]
(c) Describe the optimal paging algorithm. [2 marks]
(d) Why is it impossible to implement such an algorithm in a real operating system?
[1 mark]
(e) What is the use of such an algorithm? [1 mark]
3. File Management
(a) What are the two disadvantages of contiguous file allocation? [3 marks]
(b) Suppose an operating system wants to open a file. In order to do this, it has to load
the first block of the file to the memory. Where does the OS get information about
the location of this first block? [3 marks]
(c) In this question we consider file allocation using I-nodes. Suppose the number of
blocks of some file is much greater than the number of entries of one I-node. Suggest
a way to overcome this limitation. [4 marks]
4. Networks.
(a) What is the purpose of framing in the data link layer? [2 marks]
(b) What is the purpose of error correction codes in the data link layer? [1 mark]
(c) Why is redundancy needed to implement framing? [2 marks]
(d) Why is redundancy needed to implement error correction? [1 mark]
(e) Describe the method of distance vector routing. [3 marks]
(f) What is the main difference between distance vector routing and routing by flooding?
[1 mark]
Continued . . .
3 CO2017
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 al-
gorithm with the quantum time of 5 milliseconds. Assume that the processes start
at 0,5,10 milliseconds, respectively, and that the duration of a context switch is 1
millisecond. [5 marks]
(b) Suppose that a 4 bits word has been encoded using the Hamming code and sent
over an unreliable channel that can distort at most 1 bit. The word received by the
receiver is 1111101. What is the original word? Explain your answer. [5 marks]
(c) Suppose that we want to transfer a short sequence (frame) of decimal digits. To
denote the end of the frame we use the stuffing byte protocol. For the purpose of
this protocol we agree that digit 9 will be used to denote the end of the frame and
digit 8 will be used as the control byte. Suppose the receiver gets the message
8889888988899. What is the original message? Explain your answer. [5 marks]
(d) Create a scheduling scenario according to the Shortest Job First (SJF) policy for 6
processes Pr1, . . . ,Pr6 with the respective arrival times 0,5,10,15,20,25 that has
the effect that process Pr2 runs last. (Hint: think what should be the duration of
Pr2 compared to the rest of the processes.) Draw the CPU usage diagram of these
processes to demonstrate the correctness of your answer. [5 marks]
(e) Consider the algorithm in the appendix. It manages 3 threads accessing a shared
resource. Each thread performs the respective StartAccess function before access-
ing the resource and EndAccess function at the end of the access. This algorithm is
an attempt to generalize Peterson’s algorithm to 3 threads. However, this generalisa-
tion is not correct. In particular it enables 2 processes to simultaneously access the
shared resource. Show a scenario of such improper access. (Hint: consider what
will be true when a StartAccess function finishes.) [10 marks]
6. (a) Give a description of the Least Recently Used (LRU) Algorithm of paging that is used
for management of virtual memory [5 marks]
(b) Assume that the RAM contains 8 pages numbered from 1 to 8 and the following se-
quence of page requests occurs: 1,2,3,4,5,6,7,8,7,6,5,4,3,2,1,3,5,7,2,4,6,8.
After that page 9 is requested, which causes a page fault. Which page will be re-
moved from the RAM according to the LRU algorithm? [5 marks]
(c) The Least Frequently Used (LFU) algorithm counts for each page the number of
references and, when a page fault occurs, removes from the RAM the page that has
been referenced the least number of times. Assume that a page fault occurs after the
following sequence of requests: 1,1,1,1,1,2,3,4,5,5,6,6,6,7,7,8,8. Which page
will be removed from the main memory (ties can be broken arbitrarily)? [5 marks]
(d) Let us consider a modification of the LRU algorithm that can be called k-LRU where k
is some integer number. In this algorithm the numbers of the k most recently refer-
enced pages are maintained and when a page fault occurs, the algorithm removes
from the RAM an arbitrary page that is not one of these k pages. For the sake of
simplicity, let us give k a particular value: assume k = 10. One way to implement
Continued . . .
4 CO2017
this algorithm is to maintain these 10 pages in a chronologically sorted array. That
is, the first item of this array contains the most recently referenced page, the next
one contains the second most recent and so on. Suppose the content of the array is
12,11,10,3,4,5,6,7,8,9.
• Suppose, a page request for page 2 arrives. So, page 2 should get into the array
and one of the above pages removed. What will be the content of the array after
the inclusion of 2. Why? [3 marks]
• Suppose page 4 is referenced. How will be the content of the array be modified
as a result of this request? [3 marks]
• Give a pseudocode of an algorithm that updates the above array in case the
current request is for a page appearing in this array. [3 marks]
• Suppose that there are 100 pages in RAM, and a page fault occurs. Which page
will be removed from the RAM? Explain your answer. [3 marks]
• In which sense is the 10-LRU algorithm much more efficient that the LRU algo-
rithm? (Hint: the total number of pages in the RAM can be much larger than 10.)
[3 marks]
7. (a) Describe the Banker’s algorithm for detection of deadlocks in case that there are
multiple units of the same resource. [5 marks]
(b) Give an example of input for the Banker’s algorithm (in the form of matrices) for 3
processes and 3 resources where the algorithm will recognise a deadlock. Demon-
strate that by running the algorithm on this input. [10 marks]
(c) Give the definition of a livelock. [2 marks]
(d) Give an example of a livelock by providing a pseudocode of 2 processes competing
for 2 resources and pointing out where each thread should be interrupted in order to
cause a livelock. Explain your answer. (Hint: the order in which the second process
requests the resources should be the opposite to that the first process does).
[8 marks]
(e) What is starvation (in terms of processes in an operating system, of course)?
[2 marks]
(f) Which of the scheduling policies we learned during the classes can potentially allow
starvation? Why? [3 marks]
Continued . . .
5 CO2017
Appendix: algorithms for threads for question 5 (e)
Algorithm for Thread 1
StartAccess1()
{ interested[1]=true;
turn=2;
while( ((turn==2) AND (interested[2]==true)) OR
((turn==3) AND (interested[3]==true)))
{ ;} /* just do waiting*/
}
EndAccess1()
{ interested[1]=false; }
Algorithm for Thread 2
StartAccess2()
{ interested[2]=true;
turn=3;
while( ((turn==1) AND (interested[1]==true)) OR
((turn==3) AND (interested[3]==true)))
{ ;} /* just do waiting*/
}
EndAccess2()
{ interested[2]=false; }
Algorithm for Thread 3
StartAccess3()
{ interested[3]=true;
turn=1;
while( ((turn==1) AND (interested[1]==true)) OR
((turn==2) AND (interested[2]==true)))
{ ;} /* just do waiting*/
}
EndAccess3()
{ interested[3]=false; }
