程序代写代做代考 file system Java cache algorithm concurrency 1

1

CO2017 Examination — Draft Questions and Solutions

This copy generated 4th May 2016.

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

Version 1

Candidates All candidates

Department Computer Science

Examination Session Midsummer Examinations 2015

Time allowed Three hours

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

Calculators No

Books/statutes No

Own Books/statutes/notes No

Additional Stationery No

Number of questions 6

2

Question 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 appro-
priate, 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]

3

Answer — total marks for this question: 15

(a) (Bookwork) A program is an executable: code. A process is a program that is actively be-
ing executed on a system — includes the state of the program: memory state (heap,
swap), process counter (next instruction), process owner, associated resources (open
files, devices)

(b) Simple systems with limited multi-tasking ambitions. E.g. strictly batch processing system;
systems with single user single process; systems with limited memory/cpu capacity limits
the benefits of more pre-emptive scheduling.

(c) • FCFS
Time Running Queue Complete(waiting) Comments

0 A
1 A B
5 A B,C
8 A B,C,D
10 B C,D A(0)
15 C D B(9)
17 D C(10)
19 D(9)

• SJF
Time Running Queue Complete(waiting) Comments

0 A
1 A B
5 A C,B
8 A C,D,B
10 C D,B A(0)
12 D B C(5)
14 B D(4)
19 B(13)

4

Question 2.

Threads & concurrency in Java

Consider the (outline) code in Figure 1. The code is supposed to be a very simple simulation
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]

5

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 6 Answer — total marks for this question: 20 (a) (Interleaving) Statements in concurrent threads will execute in non-deterministic sequence. Key observation is that balance = balance+X may not be atomic. OK interleaving: balance Spender Saver 1000 acc.withdraw(501) balance-501 (499) acc.deposit(401) 499 balance= balance+401 (900) 900 balance= Undesirable interleaving: balance Spender Saver 1000 acc.withdraw(501) balance-501 (499) acc.deposit(401) balance+401 (1401) 499 balance= 1401 balance= (b) balance is the critical resource, and any code that changes it is a critical section. Only one thread at a time should be executing code in critical sections. Code in deposit method (line 5) is critical. Code in withdraw method (line 6) is critical. (c) Simplest method is to make the deposit and withdraw methods syncronized. In Java this implements a monitor which automatically ensures mutual exclusion (amongst threads accessing a particular instance). public synchronized void deposit(int d) {balance+=d;} public synchronized void withdraw(int w) {balance-=w;} (d) Pattern is while (! safe) { wait(); } Do Critical Stuff notifyAll(); So, in this case need to modify withdraw method to wait until balance is positive: public syncronized void withdraw(int w) { while (balance-w<0) {wait();} balance -= w; 7 notifyAll(); } 8 Question 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] 9 Answer — total marks for this question: 20 (a) (Bookwork) Memory hierarchy describes inverse speed/size relationship between different types of memory, and their proximity to the processor. So, processor registers are at one extreme, and are very small, but very fast. Hierarchy goes up through levels of on-processor cache, to traditional dynamic RAM, and then on to 2ndary storage. There is generally an order of magnitude (or more) difference in speed and size between levels in the hierarchy. Working set is the set of VM pages that are being used by an active process. Want to avoid the very significant time penalty of having to swap them out/in to/from swap storage on disk. (b) (Bookwork) Swapping in a direct memory model swaps the entire process memory as a single chunk. Memory is allocated for the process as a whole, and so when the process swaps out, the entire allocated memory needs to be swapped to 2ndary storage. Virtual memory system divides a process’s memory into pages of uniform, relatively small size (e.g. 4K). Only the pages that are actively being used need to be stored in real memory (page frames). This means a much more fine grained approach can be applied. Only relatively small amounts of data need to be moved to/from 2ndary storage when swapping occurs. (c) i. NRU 1,2,11,6,9,5,11,2,3,15,14,2,11,1,6,17,2 Use 1/0 subscript to indicate recently used (referenced). 0 1 2 3 4 next 11 21 111 61 91 5 10 20 110 60 90 5 51 20 110 60 90 11 51 20 111 60 90 2 51 21 111 60 90 3 51 21 111 31 90 15 51 21 111 31 151 14 50 20 110 30 150 14 141 20 110 30 150 2 141 21 110 30 150 11 141 21 111 30 150 1 141 21 111 11 150 6 141 21 111 11 61 17 140 20 110 10 60 17 171 20 110 10 60 2 171 21 110 10 60 5 initial + 7 subsequent page faults 10 ii. LRU 1,2,11,6,9,5,11,2,3,15,14,2,11,1,6,17,2 Use subscript to indicate time of last reference. 0 1 2 3 4 next 11 22 113 64 95 5 56 22 113 64 95 11 56 22 117 64 95 2 56 28 117 64 95 3 56 28 117 39 95 15 56 28 117 39 1510 2 56 211 117 39 1510 11 56 211 1112 39 1510 1 113 211 1112 39 1510 6 113 211 1112 614 1510 17 113 211 1112 614 1715 2 113 216 1112 614 1715 5 initial + 6 subsequent page faults 11 Question 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. Describe, 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] 12 Answer — total marks for this question: 17 (a) 1K blocks, and 4 byte block addresses mean that 1 block can hold 256 block addresses. Also a 1Mb file is going to need 1024 blocks. First 12 blocks can be included in the inode. Next 256 blocks can be stored in the first (single) indirect block. Then use first four double indirect block links to link to 3 more single indirect blocks, giving 768 more block addresses, only 756 of which are needed. No triple indirect blocks are needed. Something like this: bigfile.dat abc1 users 0644 2015-02-15T10:43:10 2015-02-15T15:04:55 0 inode name owner group mode creation modified direct link 1 direct link 2 direct link 12 indirect link 1 indirect link 2 indirect link 3 block 1 block 2 block 12 single indirect block 1 2 256 b 2,1 b 2,2 b 2,3 0 0 double indirect block 1 2 3 4 256 block 2,1 1 2 256 block 2,2 1 2 256 0 0 block 2,3 1 2 217 218 256 block 13 block 14 block 268 block 269 block 270 block 525 block 526 block 527 block 782 block 783 block 784 block 1000 (b) (Bookwork) Describe RAID0 with striping. One mark for mentioning RAID0; up to three more marks for describing striping, ideally with a diagram to illustrate ; and one for describing danger that a single error on either disk can result in total data loss. 13 Question 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] 14 Answer — total marks for this question: 10 (a) Essentially bookwork i. A protocol operates between peers at the same level in the multi-level model. A layer provides a service to next higher layer on the same host; and uses the service of the next lower layer. ii. Example protocols: Manchester or similar at physical level; sliding window at data; TCP protocol used to transfer data at the transport layer; http protocol at the applic- ation layer. (b) 1 0 1 1 0 1 1 0 (c) 01111110 11011111 00111110 10010001 00101000 11 01111110 15 Question 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 rep- resent 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 prede- cessor and status. [10 marks] 16 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] 17 Answer — total marks for this question: 18 (a) Node Cost Predecessor Status Working node: A A 0 Permanent B 5 A Temp C 2 A Temp D ∞ A Temp E ∞ A Temp Working node: C A 0 Permanent B 5 A Temp C 2 A Permanent D 5 C Temp E ∞ A Temp Working node: B A 0 Permanent B 5 A Permanent C 2 A Permanent D 5 C Temp E 13 B Temp Working Node: D A 0 Permanent B 5 A Permanent C 2 A Permanent D 5 C Permanent E 7 D Temp Working Node: E A 0 Permanent B 5 A Permanent C 2 A Permanent D 5 C Permanent E 7 D Permanent Path is ACDE (b) Socket server = new Socket("server.org", 1234); System.out.println("Connected to " + server.getInetAddress()); BufferedReader rdr = new BufferedReader(new InputStreamReader(server.getInputStream(), "UTF-8")); Writer out = new OutputStreamWriter(server.getOutputStream()); Scanner console = new Scanner(System.in); Scanner lineTok; 18 int num = -1; while (num != 0) { System.out.print("Enter a number: "); lineTok = new Scanner(console.nextLine()); num = lineTok.nextInt(); out.write(num + "\r\r"); out.flush(); String response = rdr.readLine(); System.out.printf("Response: %s\n",response); lineTok.close(); } console.close(); server.close();