程序代写代做代考 file system concurrency distributed system algorithm Java CO2017

CO2017
All candidates

Midsummer Examinations 2015

DO NOT OPEN THE QUESTION PAPER UNTIL INSTRUCTED TO DO SO BY THE
CHIEF INVIGILATOR

Department Computer Science

Module Code CO2017

Module Title Operating Systems, Networks, and Distributed Systems

Exam Duration Three hours

CHECK YOU HAVE THE CORRECT QUESTION PAPER

Number of Pages 7

Number of Questions 6

Instructions to Candidates Attempt all questions. Full marks may be obtained only if all questions are
answered.

For this exam you are allowed to use the following

Calculators Not permitted

Books/Statutes Not permitted

Additional Stationery Not required

Page 1 of 7

CO2017
All candidates

1. Scheduling and the dispatcher

(a) What is the distinction between a program and a process? [2 marks]

(b) Give an example of a type of system where a non-preemptive scheduler would be
appropriate, briefly explaining the reason. [3 marks]

(c) 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)
A 10 0
B 5 1
C 2 5
D 2 8

Give the order in which these jobs will be scheduled under the following policies

i. First Come First Served (FCFS)
ii. Shortest Job First (SJF)

Calculate the completion and waiting times for each job. You may assume that the
duration of a context switch can be ignored. [10 marks]

2. Threads & concurrency in Java

Consider the (outline) code in Figure 1. The code is supposed to be a very simple sim-
ulation of a bank account shared between two people, one of whom only ever deposits
money, and the other only ever withdraws money.

You may ignore the possibility of Exceptions for this question.

(a) Explain what an interleaving is, using examples from the code. You should include
and identify at least one undesirable interleaving. [4 marks]

(b) Identify the critical sections of code, and explain what this means. [4 marks]

(c) Show how you could enforce mutual exclusion of the critical section. [6 marks]

(d) The bank would like to prevent the balance from ever dropping below zero. Show
how you could implement a guard to enforce this restriction. [6 marks]

Page 2 of 7

CO2017
All candidates

1 public class Account {
2 private int balance;
3 public Account(int initial) { balance = initial; }
4 public int getBalance() { return balance; }
5 public void deposit(int d) { balance=balance+d; }
6 public void withdraw(int w) { balance=balance-w; }
7 }
8

9 public class Spender extends Thread {
10 private Account acc;
11 public Spender(Account a) { acc=a; }
12 public void run() {
13 for (int i=0; i<100; ++i) { 14 acc.withdraw(500+i); 15 System.out.println("Spent "+(500+i)); 16 Thread.sleep(1000); 17 } 18 } 19 } 20 21 public class Saver extends Thread { 22 private Account acc; 23 public Saver(Account a) { acc=a; } 24 public void run() { 25 for (int i=0; i<100; ++i) { 26 acc.deposit(400+i); 27 System.out.println("Deposit "+(400+i)); 28 Thread.sleep(1100); 29 } 30 } 31 32 public class Test { 33 public static void main(String[] args) { 34 Account ac1 = new Account(1000); 35 Spender sp = new Spender(ac1); 36 Saver sv = new Saver(ac1); 37 sp.start(); sv.start(); 38 while (true) { 39 System.out.println("Balance is: "+acc1.getBalance()); 40 Thread.sleep(2000); 41 } 42 } 43 } Figure 1: Outline bank account simulation code Page 3 of 7 CO2017 All candidates 3. Memory management (a) What is the memory hierarchy? Explain why it makes the identification of a working set so desirable. [5 marks] (b) Compare swapping in a direct memory model with page swapping in a virtual memory system. [5 marks] (c) Consider a Virtual Memory system with 20 pages, numbered 0 to 19, and with 5 page frames available, numbered 0 to 4. Initially all page frames are empty. Suppose that page requests arrive in the following order: 1,2,11,6,9,5,11,2,3,15,2,11,1,6,17,2 i. Using a Not Recently Used (NRU) page replacement algorithm how many page faults would occur? Which pages would be loaded into which page frames at each step? [5 marks] ii. Using a Least Recently Used (LRU) page replacement algorithm, how many page faults would occur? Which pages would be loaded into which page frames at each step? [5 marks] 4. File system (a) Suppose you have a file called myfile.dat on a UNIX style filesystem implemented using inodes with the following properties: Name: myfile.dat Size: 1Mb Created: 2015-02-15T10:43:10 Modified: 2015-02-15T15:04:55 Owner: abc1 Group: user Mode: 0640 The file system has a block size of 1K, and block addresses require 4 bytes. De- scribe, with the aid of diagram(s) where appropriate, what the structure of the inode for myfile.dat would be. [12 marks] (b) Suppose you have a pair of 1Tb disk drives, and you want to maximise the speed and space available to your applications. Describe how you would use RAID to achieve this, and any disadvantages that might result. [5 marks] Page 4 of 7 CO2017 All candidates 5. Physical & data link layers (a) In a multi-layer communications model, such as TCP/IP or ISO OSI: i. explain the difference between a protocol and a service; and [3 marks] ii. give two examples of real protocols in use at different levels in the TCP/IP model. [2 marks] (b) Suppose that the following stream of bits has been received at the physical layer using triple modular redundancy . 11000001 11110000 11101100 What was the original bit stream? [2 marks] (c) At the data link layer, suppose that the following stream of bits (4 bytes) is to be transmitted as a single frame using bit stuffing. 11011111 01111110 01000100 10100011 Show the bit-stream that would actually be transmitted, using the sequence 01111110 as the frame delimiter. [3 marks] Page 5 of 7 CO2017 All candidates 6. Network layer and socket programming B A D C E 2 5 8 3 2 2 Figure 2: Network and link costs (a) Trace the operation of Dijkstra’s path algorithm by explaining how it would find the least expensive route from A to E in the network illustrated in Figure 2, 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 com- puted so far, its predecessor and status. [10 marks] Page 6 of 7 CO2017 All candidates 1 Scanner console = new Scanner(System.in); 2 Scanner lineTok; 3 4 int num = -1; 5 while (num != 0) { 6 System.out.print("Enter a number: "); 7 lineTok = new Scanner(console.nextLine()); 8 num = lineTok.nextInt(); 9 10 System.out.printf("The user input %n\n",num); 11 12 lineTok.close(); 13 } 14 console.close(); Figure 3: Non-networked code that repeatedly inputs an integer from the user. (b) Consider the outline code in Figure 3. Extend the code so that it: • opens a connection to a server running on host server.org on port 1234; • repeatedly: – sends the integer input by the user to the server; – receives a response from the server and prints it out; You do not need to write a complete program, and you may assume that both the user and server always provide suitable values (you do not need to handle error conditions, or exceptions). [8 marks] END OF PAPER Page 7 of 7