Final Exam answer papers will be available with Chet Frost, CSE Department, Room 3157, AP&M for inspection (only) by students enrolled in the course during the third week in Winter 99, (jan 24th - jan 28th 2000). Request, if any, regarding evaluation may be made in writing or by email to the TA Allen Chu before jan 31, 2000.
Max = 98, Min = 22, Avg = 57.3
cse120 Operating Systems Fall 99 Final Exam
----------------------------------------------
Tuesday December 14, 3pm to 5pm WLH 2111
ANSWER KEY
----------
Name: (please print)
ucsd id No.
Answer all questions. Exam is closed book.
Write your answers in the space indicated and
provided for with each question.
Write legibly. Avoid Overwriting. Write with pen only.
Do not write on the reverse side.
Keep rough work separate and do not submit it.
Rough work is not evaluated.
For rough work separate blank sheets are provided.
Q. No marks Q.No. marks
---------------- ----------------
1 15 11 2
2 6 12 2
3 4 13 6
4 2 14 2
5 6 15 2
6 20 16 2
7 16 17 2
8 8 18 5
9 3 19 5
10 2
Total (out of 110) :
PAGE 1
(there are 11 pages PAGE 1 to PAGE 11)
___________________________________________________________________________
Question 1:
Measurements of a certain system have shown that a process runs, on the
average, for time T before blocking for Input/Output. Process switch
requires time S which is overhead. For round robin scheduling with quantum
Q, give a formula for the cpu efficiency in each of the following cases:
(a) Q=infinity (b) Q>T (c) S<Q<T (d) Q=S (e) Q nearly 0
Answer:
cpu efficiency is useful cpu time/total cpu time, i.e. sum of cpu
useful time and cpu overhead in switching processes.
For (a) and (b) a process runs for T and a switch occurs when it gets
blocked. Efficiency is T/(T+S)
In (c), since Q<T, each run of T requires T/Q process switches, resulting
in overhead of ST/Q and therefore, the efficiency is T/(T+(ST/Q)) which is
Q/(Q+S).
For (d), take Q for S in (c) and we get Q/(Q+Q) which is 50%
For (e), the efficiency goes to 0 as Q goes to 0
---------------------------------------------------------------------------
Question 2:
Consider the following preemptive priority scheduling algorithm based on
dynamically changing priorities. Larger priority number or value means
higher priority. When a process is waiting for cpu, that is, it is ready
and not running, its priority changes at a rate A; when it is running its
priority changes at a rate B. All processes are assigned priority 0 when
they first enter the ready queue. A and B can be set to give different
scheduling policies. What policy do we have when
(a) B>A>0 and (b) A<B<0
Answer:
(a) FCFS (b) LIFO (Last in First Out)
---------------------------------------------------------------------------
Question 3:
Three processes A,B,C arrive for execution at the times indicated. Their
execution times are also indicated. Using non-preemptive scheduling, and
noting that all decisions are based on the information we have at the time
a decision is made,
(a) What is the average turnaround time with FCFS?
(b) What is the average turnaround time with SJF?
Process A B C
Arrival time 0 0.4 1
Exec time 8 4 1
Answer:
(a) 10.53 (b) 9.53
---------------------------------------------------------------------------
Question 4:
The page reference string for a process has length z with n distinct pages
occurring in it. The process is run with m page frames which are initially
empty. For any replacement policy,
(a) what is a lower bound on the number of page faults?
(b) what is an upper bound on the number of page faults?
Answer: (a) n - all pages in reference string must page in
(b) z - every page in ref string causes a fault
(worst case m=1)
----------------------------------------------------------------------------
Question 5:
In a paging system of memory management, cpu cycle time is 1 microsec. It
takes an additional microsec to access a page other than the current page.
Page size is 1000 words, and the page device is a drum that runs at 3000
revolutions per minute and transfers 1 million words per sec. the following
statistical measurements were obtained from the system:
1% of instructions accessed a page other than the current page.
Of the instructions that accessed another page, 80% accessed a page already
in memory.
When a page had to be brought in, the replaced page was modified 50% of the
time.
Calculate the effective instruction time (cpu cycle time). Assume the
system is running only one process and that the cpu is idle during drum
transfers.
Answer:
effective access time in microsec is
0.99 x 1 + 0.008 x 2 + 0.002 x ( 10000 + 1000) + 0.001 x ( 10000 + 1000)
each term corresponds to current page access, another page access
without page fault, another page access with page fault, and the time for
writing out modified pages on replacement.
The expression calculates to 34 microsec.
--------------------------------------------------------------------------
Question 6:
Consider the following two program fragments:
char a [100] [100];
/* code A */
for (j=0, j<100; j++)
{ for (i=0; i<100; i++)
a[i][j] = 'Z'; }
/* code B */
for (i=0; i<100, i++)
{ for (j=0; j<100, j++)
a[i][j] = 'Z'; }
a[0][0] is at location 100 in a paged memory system with page size 100.
With three page frames, how many page faults occur with (i) code A and (ii)
code B. Assume LRU replacement and that out of the three frames one is taken
by the code page which stays in memory throughout.
Answer:
The array a needs 100 pages and is stored in the order
a[0][0], a[0][1], ... a[0][99] in page 1,
a[1][0], a[1][1], ... a[1][99] in page 2, ....
a[99][0], ........... a[99][99] in page 100.
For code A, the page reference string is 0,1,0,2, .. 0,99 for one iteration
of the outer for loop and repeats 100 times. The number of page faults is
10,000.
For code B, the page reference string is 0,1 for the first iteration of the
outer loop, 0,2 for the second iteration and so on upto 0,99 for the 100th
iteration of the outer loop -- the page of a is used with no page faults in
the inner loop. The number of page faults is 100.
------------------------------------------------------------------------------
Question 7:
A disk drive has 5000 cylinders, numbered 0 to 4999. The drive is serving a
request at cylinder 143 currently and the previous request was at 125. The
disk I/O queue, in FIFO order, is
86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130
Starting from the current head position, what is the total distance (in
cylinders) that the disk arm moves to satisfy all the pending requests, for
each of the following scheduling methods? Show the order of service of the
requests for each case.
(a) FCFS (b) SSTF (c) SCAN (d) C-SCAN
Answer:
a 143, 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130 -- 7081
b 143, 130, 86, 913, 948, 1022, 1470, 1509, 1750, 1774 -- 1745
c 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 130, 86 -- 3319
d 143, 913, 948, 1022, 1470, 1509, 1750, 1774, 86, 130 -- 3363
-------------------------------------------------------------------
Question 8:
A unix i-node has 10 disk addresses for data blocks, as well as addresses of
single, double and triple indirect blocks. If each of these indirect blocks
hold 256 disk addresses, what is the size of the largest file? Assume each
disk block is 1K bytes size.
Answer:
i-node holds 10 addresses -- 10k
Single indirect block holds 256 addresses -- 256k
Double indirect block leads to 256x256=65536 addresses -- 65536k
Triple indirect -- 65536x256=16777216 blocks -- 16777216k
Total is 10 + 2**8 + 2**16 + 2**24 blocks of 1k bytes each,
16,843,018 blocks -- 16 Gigabytes approximately.
-------------------------------------------------------------------------
Question 9:
A password may become known to others. Suggest a simple method for
detecting that such an event has occured.
Answer:
Whenever a user logs in, the system prints the last time the user logged on
the system.
---------------------------------------------------------------------------
Question 10:
What is Belady's Anomaly?
Answer:
We expect the number of page faults for a reference string to decrease as
the number of frames available to the process increases but this is not so
in all cases.
---------------------------------------------------------------------------
Question 11:
What property of a replacement policy ensures that Belady's Anomaly does
not occur? State the property.
Answer: Stack Property.
A replacement policy has the stack property if, for any reference string R,
the memory state (the set of pages in memory) with j frames, say M(j,R) is
a subset of M(i,R) for i>j
---------------------------------------------------------------------------
Question 12:
In a ring protection system, level 0 has the greatest access to objects and
level n (n>0) has fewer access rights. The access rights of a process
(program running) at a particular level in the ring structure are viewed as
set of capabilities of that process. What is the relationship between the
capabilities at level j denoted as Dj and at level i (Di) to an object?
Answer:
For i>j, Di is a subset of Dj
----------------------------------------------------------------------------
Question 13:
State how unix file operation(s) can be used to implement (a) sequential
(b) random and (c) indexed-using-key accesses to the contents of a file.
Answer:
(a) provided in unix read and write
(b) by using lseek
(c) by using an index table ( key, position ) and lseek
----------------------------------------------------------------------------
Question 14:
(a) Why are operations on Input/Output Devices asynchronous?, and
(b) how is it synchronised with the program performing the I/O?
Answer:
(a) Input/output devices are slow and by asynchronous operations, the cpu is
not tied up and can be used for other processes, thus improving cpu
efficiency and thruput.
(b) By interrupts from I/O device on completion of operation or by polling by
cpu.
------------------------------------------------------------------------------
Question 15:
What is the purpose of interleaving file blocks on the tracks of a disk?
Answer:
Interleaving allows the controller to process a block and get the next
block for sequential access without the rotational delay (latency).
------------------------------------------------------------------------------
Question 16:
Why are real and not virtual addresses used by I/O channels in systems with
paging?
Answer:
During I/O transfers, if page faults occur, the service time will result in
buffer overrun (and loss of data) on the I/O controller/Channel.
Therefore, the I/O buffers have to be fixed in real memory and there is no
gain using virtual addresses and incurring address translation.
-------------------------------------------------------------------------------
Question 17:
The LRU replacement policy is practical to implement for file cache but
needs to be approximated for paging. Why?
Answer:
The information to be maintained and updated for the file blocks/pages in
memory, namely, the most recent time of access, is feasible for file cache.
For paging, the updating is required for every memory reference and this
adds considerable overhead making it impractical.
-------------------------------------------------------------------------------
Question 18:
Four processes P, Q, R, and S form a system of producers and consumers with
the following structure:
P-Q : producer-consumer
P-R : producer-consumer
Q-S : producer-consumer
R-S : producer-consumer
Can the system Deadlock? State Yes or No. Briefly explain.
Answer:
YES. Q waits for P (all P-Q buffers are empty)
P waits for R (all P-R buffers are full)
R waits for S (all R-S buffers are full)
and, S waits for Q (all Q-S buffers are full) which is a cycle.
-------------------------------------------------------------------------------
Question 19:
Consider a system with 5 processes and four resources. The state is given
by C (current allocation matrix), R (maximum resources needed matrix),
and A (vector of free resources).
C R
0 0 1 2 0 0 1 2 A = [ 1 5 2 0 ]
1 0 0 0 1 7 5 0
1 3 5 4 2 3 5 6
0 6 3 2 0 6 5 2
0 0 1 4 0 6 5 6
(a) Is the system in a safe state?
(b) If process 2 makes a request for (0 4 2 0) can it be granted?
Answer:
(a) YES. From the given state processes can finish in the order process 1,
process 3 or 4 next, and the rest.
(b) If request of process 2 is granted, A will become [ 1 1 0 0 ] and row 2
in C will be (1 4 2 0). This is a safe state and the request of process 2
can be granted.
THE END OF ANSWER KEY
---------------------------------------------------------------------------