CMPS 272 Final, Fall 1995

SAECO NN Urorasy ol LIBRARY OF EMER ab fre Department of Mathematics fripbe MATH 272 Cree ay Operating Systems VAR at Final-Fall1995 \ Time 2 Hours Ahmad Nasri Assume that the UNIX commands have the prompt Licifer> eh ‘ (A,B) General (12 + 15 = 27points) ae A. Answer by True or False each of the follwing questions: 1 In locking protocol, if a transaction T; can read and write to.an item Q, then T; has obtained a shared lock on Q. 2 In time-based protocols, if a a transaction TS(T;)- <Ww- timestamp(Q), a read operation by T; is rolled back. . A distributed system where processors share a memory is called a tightly coupled system. In a script C shell, expr$var-name is used to ‘perform arithmetic operations on numbers. Processes may never get deadlocked in a system with non preemptive re- sources In virtual memory, the page size should be large to minimize internal frag- mentation A system with one instance only per a resource type is unsafe if a cycle exists. The long term scheduler is invoked when the degree of multiprogramming i is reached. In a real-time system, fast response is desirable but, not required. One way to reduce the context switch time is to overlap ‘swapping and pro- gram execution. 11 The page Stealer swaps out memory pages that are no: longer part of the working set of a process. 12 Ina file system, the Device Directory describes the logical, properties of files. =B. Comp lete each of the following: 1 Setting the actual address used by each nonrelocatable address of a program is called: 2 The time needed to switch from one job to another is called: 3 The difference between an interupt and a trap is: oo on] ao ca CS wo bet Beer a Soe geet oe CPR REST 4 Two advantages of distributed systems are: PRA RY | 5 Given a UNIX. session consisting of the following commands: Lucifer> cat *.* > silly] & Lucifer> cp *. «> silly’ 2 &° the following command resumes the first command: 6 The output of the following command is: Lucifer> cpio -it < devicefiles 7 Using the following session on a Unix OS: Lucifer> who | sort 1 i , _ ‘ rare gaat wi. good tty03 Jan 26 12:50 ~~ notgood tty06 Jan 26:12:30 .- silly console J an 26 11:40 . sleepy ttyO2 = jan 26:07:20 .. complete the commands below to list the user sleepy: Lucifer> who | 8 To To print the third and the first fields (in that order) of each selected line of silly, the following awk command is used ; 9 The following command: Lucifer> cp /home/jenny/memo . © a 10 If silly is a shell script, all users can execute it if we change ‘the mode of silly 3 by the following command: 4 & (C) Job Scheduling (15 points) Coe ¢ (C.1) Consider the following set of processes with their arrival, processing time, * and their priorities: a job Arrival Time Processing Time © Priority * A 0 4. 2 i B 1 1002 4 4 Cc 2 ‘3 a) ‘ D 3 100 ' ey i a. Draw a Gantt chart to illustrate the execution ofsthese jobs using a preemptive priority scheduling algorithm. A large value means higher priority. b. What is the average waiting time over all jobs? c, What is the turnaround time of each jobs if an aging technique is used where each non-executing process gets its priority increased by 1 after each interval of time. PRR. 3 ae sees aly oa (D) Process Syncronization (20 points) (D.1) In the implementation of the conditional-region construct, assume that a process po and p; are waiting behind second-délay (p, is at the head of the queue) and ps3 is attempting to execute the instruction wait(first-delay). Aassume that semaphores are used without busy waiting and that no other processes are accessing the region, answer each of the following questions: (i) Give the value of each of first-delay, second-delay, first-count, and second-count, just after p3 executed the instruction watt/(first-delay) successfully. Answer: first-delay second-delay Answer: first-count second-count (ii) Assume that the condition B becomes true for p2 only, what are the values of the semaphores and count’ of (i), just after po execute S. Answer: first-delay ' second-delay . Answer: first-count second-count _ (iii) If the condition B becomes true for all processes, indicate the order in which the processes leave the region. Tew ut Sane eS Consider a system with three printers that can be: allocated to processes with one condition to keep one printer free ‘at least. Write a monitor AllocatePrinters to coordinate the use of these printers. Explain how to modify your solution if the system has two lazer printers and one dot matrix printer where one lazer printer is to be left free at all time. x & s oon ceria (E) Deadlocks (18 points) te (E.1) Show that a deadlock cannot occur in a system of r resources and p processes where each processes p; cannot use more than r régources. The sum of all maximum needs is less than r +p and the resourees can be released and reserved only one at a time. _ (E.2) Consider a system with 4 resources (rj)i<4. of instances 6, 7, 11, and 12, respectively. The following tables show a snapshot-of the cuurent allocation and the maximum needs of the processes: ' ; . Allocation . Maximum Process fi m2 73 T4 «TI rq T3: T4 1 0012 . 0 0 1. 2 2 20 00 : 238 7:-6° 0 3 00 3 4 = 6 6 5: 6 4 0 38 3 2 2 0 6 5 2 a. Give the vector available ane the matrix Need and use the Safety algorithm to determine if the system is in a safe state. ca oa See SRR Diet OR b. If ps issues a request of (0,1,0,0), can that request be granted? If not indicate the processes that are deadlocked. of at aeait SSE ge eee Srey lipemic Oe ret ae etna tih ot BR ase ue (F) Memory Management (8 points) sek, (F.1) Assume that the logical address space is mapped.to a physical adress space of n locations per a frame starting from frame’. Given a logical address I (starting from 0) answer each of the following : using: the contents of the associated page tabe 7}: a. To which logical page | belongs? Answer: b. To which frame / belongs? Answer: c. Find an expression of the physical address of I Answer: om ga cae f . UE ei oe aay ats te zee (E) Virtual Memory (12 points) ~ oo (E.1) Assume that a 2-D array B[1..10,1..10] is stored contiguously in a memory that can contain five elements per a frame starting at frame 1. What is the reference string generated by the following piece of code : For i := 1 to 10 do For j := 1 to 10 do Bij,i] := 0 (Z.2) A process references 5 pages (p;)1<i<s in the following order: Poy P1yP2y P35 Pos Piy Pas Po PisP2; Ps, Ps Find the number of page faults in each of the Least Recently, Used and Optimal algorithms starting with an empty memory of 3 frames. Good Work Pevics i gag ey RS Re Re GIRS Ske ce SE ee Sw ih i eS ag AGRE FB i an