CISC 3320 Exam2 Prof. Cox

NAME:

1.(10 pts) Consider a blocked file allocation.

a) What is the difference between a linked allocation and the use of an index.

b) How do the linked allocation and the use of an index affect both sequential and direct record access?

c) What is the problem of disk fragmentation and how does it occur? What does defragmentation do?

CISC 3320 Exam2 Prof. Cox

2.(10 pts) a) You are given 4 processes in a batch system that all arrive at time 0 with the following CPU burst times:

P1 : 35, P2: 25, P3: 13, P4: 22. Assuming there is no context switch overhead, draw a time line chart

(Gantt chart) showing when each process executes under each of the following scheduling algorithms:

SJN (Shortest Job Next).

Round Robin with a quantum of 10.

b) What is the difference between preemptive and non-preemptive scheduling?

CISC 3320 Exam2 Prof. Cox

3.(10 pts a) (10 pts) What is an interrupt? 

 b) What I/O technique did interrupts replace? 

 c) What is the advantage of interrupts over the older method? 

 d) Explain one method of transferring control to an interrupt handler and back. 

CISC 3320 Exam2 Prof. Cox

4.(15 pts) a) Identify the four necessary conditions for deadlock to occur.

b) For each of these four conditions describe an operating system policy that prevents that condition.

c) Recall that a resource graph contains a directed edge from a resource node to a process node if the

process holds that resource and a directed edge from a process node to a resource node if the process

is requesting and waiting on that resource. Draw a resource graph with at least two processes and two

resources that is in a deadlocked state. Explain how two of the four policies you described in part b)

either prevents or removes this deadlock.

CISC 3320 Exam2 Prof. Cox

5.(15 pts) Recall the Bankers Algorithm for deadlock avoidance with multiple resources. Use the Bankers

Algorithm to determine whether the following state is SAFE. Show all work.

Existing Resources=5 Tape drives, 4 Printers, 4 CD ROMS )

Resources assigned (possessed)

Process	Tape drives	Printers	CD ROMS
A	3	1	1
B	1	1	0
C	1	1	1

Resources still needed

Process	Tape drives	Printers	CD ROMS
A	1	1	0
B	0	1	1
C	3	1	0

CISC 3320 Exam2 Prof. Cox

6.(10 pts) Explain how the following contiguous memory allocation policies work:

a) First Fit

b) Best Fit

c) Next Fit

d) Worst Fit

CISC 3320 Exam2 Prof. Cox

7.(15 pts) a) Explain how a demand paging system works with virtual memory. Describe what is stored in the

page table and how a virtual address gets translated into an actual memory address.

b) If the number of page frames is very large this can create a problem. Explain what a TLB is and

how it helps with this problem.

c) What causes a page fault? What does the operating system do in this case?

d) Briefly explain how each of the following page replacement algorithms work:

I) FIFO

II) Clock (Second Chance)

CISC 3320 Exam2 Prof. Cox

8. (15 pts )a) Explain seek time and rotational latency. Which can be controlled by disk scheduling algorithms, and why?

b) FCFS, SSTF, and C-SCAN are three different algorithms for accessing information stored on a disk. Explain the advantages and disadvantages of each.

c) For each algorithm, show the order in which each of the following disk I/O requests (listed by track number) will be handled: 25, 22, 110, 54, 12, 132, 60. Assume that the read/write head is currently servicing track 40 and has recently finished servicing track 50, and that the tracks are numbered 1 to 150.

d) Based on your answer to part b, which of the three algorithms is best? Why?