Question

1- Consider the following resource allocation graph and check whether it contains deadlock or not? Justify your answer in detail.

2- Consider the following page reference string:

4, 6, 7, 8, 6, 7, 8, 4, 6, 4, 4, 7, 5, 8

Assuming demand paging with three frames, how many page faults would occur for the following replacement algorithms? illustrate your work.

1. FIFO replacement.
2. LRU replacement.

3- What is swapping? explain the terms "swap in" and "swap out" with a neat diagram. Explain under which circumstances page faults occur and how they are resolved by the operating system.

Answer 1

Solution

Q1) The resource allocation graph contains a deadlock .

The reason for the deadlock is

Process P1 holding one instance of resource R2 requests for resource R1 held by process P2.

Process P2 holding resource R1 and one instance of resource R2 is requesting for resource R3 held by process P3.

Process P3 holding resource R3 is requesting resource R2 held by process P1 and P2.

Hence there is a cycle and there exists a deadlock as one process holding one resource is waiting for another resource held by another process which in turn is waiting for a resource held by another process (cycle goes on).

Q2)

FIFO : PAGE FAULTS =9

LRU : PAGE FAULTS = 9

Q3) Swapping is a memory management scheme in which any process can be temporarily swapped from main memory to secondary memory so that the main memory can be made available for other processes.

Swap in means to take the program from Hard disk and again bring them to the Main memory.

Swap out means to take the program from Main memory and to bring them in Hard disk.

#Occurance of page fault

A page fault occurs when the access to a page that has not been brought into main memory takes place. Verification is done by the operating system on the memory access, if found invalid aborts the program. If it is valid a free frame is located and I/O requested to read the needed page into the free frame.

#Handling of page faults by the OS

The kernel is traped by the computer hardware and program counter is saved on the stack.

CPU registers saves the current instruction state

To save the general registers and other volatile information an assembly program is started to keep the OS from destroying it.

Operating system finds the occurance of the page fault and tries to find out which virtual page is needed.

Operating system finds that a page fault has occurred and tries to find out which virtual page is needed.

Some times hardware register contains this required information. If not, the operating system must retrieve PC, fetch instruction and find out what it was doing when the fault occurred.

Once virtual address which caused page fault is known, system checks to see if address is valid and checks if there is no protection access problem.

If the virtual address is valid, the system checks to see if a page frame is free.

If no frames are free, the page replacement algorithm is run to remove a page.

If frame selected is dirty, page is scheduled for transfer to disk, context switch takes place, fault process is suspended and another process is made to run until disk transfer is completed.

As soon as page frame is clean, operating system looks up disk address where needed page is, schedules disk operation to bring it in.When disk interrupt indicates page has arrived, page tables are updated to reflect its position, and frame marked as being in normal state.

Faulting instruction is backed up to state it had when it began and PC is reset. Faulting is scheduled, operating system returns to routine that called it.

Assembly Routine reloads register and other state information, returns to user space to continue execution.