Q.2 Attempt any THREE.

a. Explain Banker’s Algorithm for deadlock prevention.

Banker's algorithm calculates resources allocated, required and available before allocating resources to
any process to avoid deadlock. It contains two matrices on a dynamic basis. Matrix A contains resources
allocated to different processes at a given time. Matrix B maintains the resources which are still required
by different processes at the same time. F: Free resources
Algorithm :
Step 1:
When a process requests for a resource, the OS allocates it on a trial basis.
Step 2:
After trial allocation, the OS updates all the matrices and vectors. This updating can be done by the OS in
a separate work area in the memory.
Step 3:
It compares F vector with each row of matrix B on a vector to vector basis.
Step 4:
If F is smaller than each of the row in Matrix B i.e. even if all free resources are allocated to any process
in Matrix B and not a single process can completes its task then OS concludes that the system is in
unstable state.
Step 5:
If F is greater than any row for a process in Matrix B the OS allocates all required resources for that
process on a trial basis. It assumes that after completion of process, it will release all the recourses
allocated to it. These resources can be added to the free vector.
Step 6:
After execution of a process, it removes the row indicating executed process from both matrices.
Step 7: This algorithm will repeat the procedure step 3 for each process from the matrices and finds
that all processes can complete execution without entering unsafe state. For each request for any

c. What are different free space management techniques? Describe any one in detail.

A file system is responsible to allocate the free blocks to the file therefore it has to keep track of
all the free blocks present in the disk. There are mainly two approaches by using which, the free
blocks in the disk are managed. Following are the free space management technique: 1) Bitmap
2) Linked List 3) Grouping
Bit Vector The first method that we will discuss is the bit vector method. Also known as the bit
map, this is the most frequently used method to implement the free space list. In this method,
each block in the hard disk is represented by a bit (either 0 or 1). If a block has a bit 0 means
that the block is allocated to a file, and if a block has a bit 1 means that the block is not
allocated to any file, i.e., the block is free. For example, consider a disk having 16 blocks where
block numbers 2, 3, 4, 5, 8, 9, 10, 11, 12, and 13 are free, and the rest of the blocks, i.e., block
numbers 0, 1, 6, 7, 14 and 15 are allocated to some files. The bit vector for this disk will look like
this
f. What are different file allocation methods. Explain any one in detail with suitable example.
The contiguous allocation method requires each file to occupy a set of contiguous addresses on
the disk. Disk addresses define a linear ordering on the disk. Contiguous allocation of a file is
defined by the disk address of the first block and its length. If the file is ‘n’ blocks long and starts
at location ‘b’, then it occupies blocks b, b+1, b+2, - - - - - b+n-1. The directory entry for each file
indicates the address of the starting block and the length of the area allocated for this file. •
Contiguous allocation supports both sequential and direct access. • For direct access to block ‘i’
of a file, which starts at block ‘b’, we can immediately access block b+i. The difficulty with
contiguous allocation is finding space for a new file. • For direct access to block ‘i’ of a file,
which starts at block ‘b’, we can immediately access block b+i. • The difficulty with contiguous
allocation is finding space for a new file. • If file to be created are ‘n’ blocks long, we must
search free space list for ‘n’ free contiguous blocks.

g. With neat diagram, explain file access methods.

There are two method to access file: 1. Sequential access 2. Direct access 1. Sequential Access
Method: Information in the file is processed in order, one record after the other. This mode of
access is by far the beginning current position most common; for example, editors and
compilers usually access files in this fashion. Reads and writes make up the bulk of the
operations on a file.  A read operation read next reads the next portion of the file and
automatically advances a file pointer, which tracks the I/O location.  Similarly, the write
operation write next appends to the end of the file and advances to the end of the newly
written material (the new end of file)

Direct Access Method: A file is made up of fixed-length logical records that allow programs to
read and write records rapidly in no particular order. Thus, we may read block 14, then read
block 53, and then write block 7. There are no restrictions on the order of reading or writing for
a direct-access file. The direct-access method is based on a disk model of a file, since disks allow
random access to any file block. Direct-access files are of great use for immediate access to
large amounts of information. Databases are often of this type. For the direct-access method,
the file operations must be modified to include the block number as a parameter. The block
number provided by the user to the OS is normally a relative block number.
 h. What is Virtual memory? Explain Paging and Segmentation.
Virtual memory is the separation of user logical memory from physical memory. This separation
allows an extremely large virtual memory to be provided for programmers when only a smaller
physical memory is available. Virtual memory makes the task of programming much easier,
because the programmer no longer needs to worry about the amount of physical memory
available, or about what code can be placed in overlays, but can concentrate instead on the
problem to be programmed. On systems which support virtual memory, overlays have virtually
disappeared
Paging:
Paging refers to the transfer of memory pages from physical memory to disk and vice versa.
Virtual memory uses a technique called demand paging for its implementation. Logical address
space of a process can be noncontiguous; process is allocated physical memory whenever the
latter is available
Divide physical memory into fixed-sized blocks called frames (size is power of 2, between 512
bytes and 8192 bytes) Divide logical memory into blocks of same size called pages .
Page fault:
When the process executes and accessed the pages that are present into memory, execution
proceeds normally. But if the process tries to access a page which is marked invalid, then it
causes a page fault trap. This trap occurs because operating system has failed to bring the
desired page into memory. The main functions of paging are performed when a program tries
to access pages that do not currently reside in the RAM. This situation is known as page fault.
The OS must take control and handle the page
fault.
Segmentation is a memory management scheme that permits dividing logical address space
into multiple segments.

d. Explain Page Replacement Algorithms with their advantages and disadvantages.

i. Describe Optimal and FIFO Page Replacement algorithm with example.
j. Write a note on-
LRU Page Replacement Algorithm
Same answer consider for d,j,f

LRU (Least Recently Used) Page Replacement

 Concept: Replaces the page that hasn't been used for the longest time.
 Usage: Tracks the recent usage of pages and removes the least recently used page.
 Pros: Often reduces page faults since frequently used pages are kept longer.
 Cons: Harder to implement due to tracking recent usage history.
 Example: If pages in memory are used in the order 2, 3, 1, 4, and now 5 needs to be loaded, it will replace page 2 (the least
recently used).

2. Optimal Page Replacement

 Concept: Replaces the page that won't be needed for the longest time in the future.
 Usage: Requires future knowledge of page requests, so it’s theoretical but useful as a
benchmark.
 Pros: Yields the lowest possible page faults (best performance).
 Cons: Impossible to implement in practice since future requests are unknown.
 Example: If pages 2, 3, 1, and 4 are in memory and 5 is needed, it would replace the
page that will be used furthest in the future.

3. FIFO (First-In-First-Out) Page Replacement

 Concept: Replaces the oldest page in memory (the one loaded first).
 Usage: Works on a queue system, where the first page in is the first page out.
 Pros: Simple to implement, no need for usage tracking.
 Cons: Can lead to high page faults as it doesn’t consider usage frequency.
 Example: If pages are loaded in order as 1, 2, 3, and 4, and page 5 needs to be loaded,
it replaces page 1 (the oldest one).

Summary of Key Differences

 LRU: Based on the last use time of pages.

 Optimal: Based on future page requests.
 FIFO: Based on the order pages were loaded in.