Q1 Explain LRU page replacement algorithm by taking suitable example.

(Explanation - 3Marks, Example - 3Marks)

ANS Least Recently Used (LRU) Algorithm:
Counter implementation:-Every page entry has a counter; every time page is referenced
through this entry; copy the clock into the counter.
When a page needs to be changed, look at the counters to determine which are to change.
Stack implementation – keep a stack of page numbers in a double link form:
LRU replacement associates with each page the time of that page‟s last use. When a page
must be replaced, LRU chooses the page that has not been used for the longest period of
time.
Example: - total available frames:-3

Initially, reference 7, 0, 1 are store inside the three free frames. When the reference to page 4
occurs, LRU replacement checks for existing pages inside the frames for their last access. From
the three frames in the memory, page 7 was used least recently. Thus, the LRU algorithm
replaces page 7, not knowing that page 7 is about to be used. Advantage: Less number of
faults as compared to FIFO
Q2 Explain static and dynamic memory partioning with advantages and drawback. (Explanation-
static & dynamic 1Mark each, any one Advantage and disadvantage 1 Mark each for each type)
ANS Static Memory
Static Memory Partitioning Main memory is divided into multiple partitions of fixed size at the
time of system generation. A process may be loaded into a partition of equal size or greater
size. Partitions can be of equal size or unequal size

Advantages:
1)Simple to implement
2) It requires minimal operating system software and processing overhead as
 partitions are fixed at the time of system generation.
Disadvantages:
1) Memory wastage
2) Inefficient use of memory due to internal fragmentation.
3) Maximum number of active processes is fixed.
Dynamic Memory
Dynamic Memory partitioning When a process enters in main memory, it is allocated exact
size that is required by that process. So in this method, partitions can vary in size depending on
memory space required by a process entering in main memory. Operating system maintains a
table indicating which parts of memory are available and which are occupied. When new
process arrives and it needs space, system searches for available memory space in main
memory. If it is available then memory is allocated to the process by creating a partition in
memory. Like this depending on size of process and available memory, partitions take place in
main memory.
Process of memory allocation:-

Total memory size is 64 M .From this 8 M partition is occupied by operating system and
remaining can be partitioned as per the size of processes
Advantages:
No internal fragmentation, More efficient use of main memory.
Disadvantages:
It suffers from external fragmentation, It needs compaction
Q3 Explain concept of page replacement with suitable diagram.
(Explanation-3Marks, Diagram- 3Marks) [Note:-explanation with any algorithm such as
FIFO,Optimal,LRU shall be considered]
ANS Basic Page Replacement:
Page replacement takes the following approach. If no frame is free, we find one that is not
currently being used and free it. We can free a frame by writing its contents to swap space
and changing the page table (and all other tables) to indicate that the page is no longer in
memory. We can now use the free frame to hold the page for which the process faulted.
We modify the page-fault service routine to include page replacement:
1. Find the location of the desired page on the disk.
2. Find a free frame:
 a. If there is free frame, use it.
b. If there is no free frame, use a page-replacement algorithm to select a victim frame.
c. Write the victim frame to the dis; change the page and frame tables accordingly.
3. Read the desired page into the newly freed frame; change the page and frame
tables.
4. Restart the user process.
Notice that, if no frame are free, two page transfers (one out and one in) are
required. This situation effectively doubles the page-fault service time and
increases the effective access time accordingly

Q4 Explain Bit map free-space management technique.

ANS Frequently, the free-space list is implemented as a bit map or bit vector. Each block is
represented by a 1 bit. If the block is free, the bit is 0; if the block is allocated, the bit is
1. For example, consider a disk where blocks 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25,
26, and 27 are free, and the rest of the blocks are allocated. The free-space bit map
would be:
11000011000000111001111110001111…
The main advantage of this approach is that it is relatively simple and efficient to find n
consecutive free blocks on the disk. Unfortunately, bit vectors are inefficient unless the
entire vector is kept in memory for most accesses. Keeping it main memory is possible
for smaller disks such as on microcomputers, but not for larger ones.
Q5 Differentiate between paging and segmentation. (any six points
ANS

Q6 Explain any two file allocation methods with the help of diagram
ANS 1. Contiguous Allocation
The contiguous allocation method requires each file to occupy a set of contiguous
address on the disk. Disk addresses define a linear ordering on the disk. With this
ordering, accessing block b+1 after block b normally requires no head movement.
Contiguous allocation of a file is defined by the disk address and the length of the first
block. 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.
Advantages of Contiguous File Allocation Method:
1. Supports both sequential and direct access methods.
2. Contiguous allocation is the best form of allocation for
sequential files. Multiple blocks can be brought in at a time to
improve I/O performance for sequential processing.
3. It is also easy to retrieve a single block from a file. For
example, if a file starts at block ‘n’ and the ith block of the file
is wanted, its location on secondary storage is simply n + i.
4. Reading all blocks belonging to each file is very fast.
5. Provides good performance.
Disadvantages of Contiguous File Allocation Method:
1. Suffers from external fragmentation.
2. Very difficult to find contiguous blocks of space for new files.
3. Also with pre-allocation, it is necessary to declare the size of
the file at the time of creation which many a times is difficult to
estimate.
4. Compaction may be required and it can be very expensive
2. linked Allocation:-
In this method, each file occupies disk blocks scattered anywhere on the
disk. It is a linked list of allocated blocks. When space has to be allocated to the file,
any free block can be used from the disk and system makes an entry in directory.
Directory entry for allocated file contains file name, a pointer to the first allocated
block and last allocated block of the file. The file pointer is initialized to nil value to
indicate empty file. A write to a file, causes search of free block. After getting free
block data is written to the file and that block is linked to the end of the file. To read
the file, read blocks by following the pointers from block to block starting with block
address specified in the directory entry.
For example, a file of five blocks starting with block 9 and continue with block
16,then block 1,then block 10 an finally block 25.each allocated block contains a
pointer to the next block

(b) Linked allocation

The problems in contiguous allocation can be traced directly to the requirement that the
spaces be
allocated contiguously and that the files that need these spaces are of different sizes. These
requirements can be avoided by using linked allocation.
In linked allocation, each file is a linked list of disk blocks. The directory contains a pointer to
the
first and (optionally the last) block of the file. For example, a file of 5 blocks which starts at
block
4, might continue at block 7, then block 16, block 10, and finally block 27. Each block contains
a
pointer to the next block and the last block contains a NIL pointer. The value -1 may be used
for
NIL to differentiate it from block 0.
With linked allocation, each directory entry has a pointer to the first disk block of the file. This
pointer is initialized to nil (the end-of-list pointer value) to signify an empty file. A write to a
file
removes the first free block and writes to that block. This new block is then linked to the end
of
the file. To read a file, the pointers are just followed from block to block.There is no external
fragmentation with linked allocation. Any free block can be used to satisfy a
request. Notice also that there is no need to declare the size of a file when that file is created.
A
file can continue to grow as long as there are free blocks.
Linked allocation, does have disadvantages, however. The major problem is that it is inefficient
to
support direct-access; it is effective only for sequential-access files. To find the ith block of a
file, it must start at the beginning of that file and follow the pointers until the ith block is
reached.
Note that each access to a pointer requires a disk read.
Another severe problem is reliability. A bug in OS or disk hardware failure might result in
pointers being lost and damaged. The effect of which could be picking up a wrong pointer and
linking it to a free block or into another file
Q7 What is partitioning? Explain concept of variable memory partitioning with example.
(Description of partitioning- 2 Marks, Concept of variable partitioning- 3 Marks, Example with
Diagram - 3 Marks)
ANS Partitioning is part of Memory Management System. A new magnetic disk is a blank slate: it is
just a platter of a magnetic recording material. Before a disk can store data, it must be divided
into
sectors that the disk controller can read and write, this is called low level or physical
formatting.
Partitioning types: fixed partition (static partitions) and variable partition (dynamic partitions).
• Partition main memory into a set of non-overlapping memory regions called partitions.
Variable partitioning:-
When a process enters in main memory, it is allocated exact size that is required by that
process.
So in this method, partitions can vary in size depending on memory space required by a
process
entering in main memory. Operating system maintains a table indicating which parts of
memory
are available and which are occupied. When new process arrives and it needs space, system
searches for available memory space in main memory. If it is available then memory is
allocated
to the process by creating a partition in memory. Like this depending on size of process and
available memory, partitions take place in main memory.
For example:-Consider following table with process and memory space

Total memory size is 64 M .From this 8 M partition is occupied by operating system and
remaining can be partitioned as per the size of processes.
Fig a: - the operating system is loaded in the memory. The entire remaining space is free.
Fig b: - process p 1 is loaded with 20 M memory size as space is available in memory. So
loading
process p1 create one partition in memory.
Fig c: - process p 2 is loaded with 14 M memory size as space is available in memory. So
loading
process p 2 creates one more partition in memory with 14 M size.
Fig d: - process p 3 is loaded with 18 M memory size as space is available in memory. So
loading
process p 3 creates one more partition in memory.
Fig e & f: - consider Process P 2 is currently blocked. After some time process P 4 with high
priority is ready for execution with memory of 8M.the existing free space is less than the
required
space. With priority scheduling, suppose P 2 is having less priority over P4 then system
 performs
swapping of process P2 and process P 4.in this case, space occupied by process P2 is released
i.e.
14 M and P 4 occupies 8 M in that free space as shown in fig f.
Fig g: - Process P1 completes its job and then it releases its occupied space of 20 M.
Fig h:-Process P2 can be loaded again in the memory in the free partition released by process P
1.but P 2 requires only 20 M, so the free space of 20 M is divided into two partitions of 14 M
occupied by P2 and 6 M free space.
Q8 Consider the following page reference string-1,2,3,4,5,6,7,8,7,8,9,7,8,9,5,4,5. How many page
faults occur for FIFO replacement algorithm assuming 3 frames?
ANS

(* indicates page hit)

Page fault 12 Page hit 08
Q9 ) State and describe different memory management technique. (State two techniques – 1
Mark, Description of Fixed partitioning – 1 ½ Marks, Description of Variable partitioning – 1 ½
Marks)
ANS Memory management techniques:
1) Fixed Partitioning
2) Variable partitioning
1) Fixed Partitioning
Main memory is divided into multiple partitions of fixed size at the time of system generation.
A
process may be loaded into a partition of equal size or greater size. Partitions can be of equal
size
or unequal size.
Main memory is divided into equal size partitions. Any process with less or equal size can be
loaded in any available partition. If all partitions are full and no process is in ready or running
state then the operating system can swap a process out of any partition and load in any other
process. Main memory can be also divided into multiple partitions of unequal size. Each
process
can be loaded into the smallest partition within which the process will fit
 2) Variable partitioning:-
When a process enters in main memory, it is allocated exact size that is required by that
process.
So in this method, partitions can vary in size depending on memory space required by a
process
entering in main memory. Operating system maintains a table indicating which parts of
memory
are available and which are occupied. When new process arrives and it needs space, system
searches for available memory space in main memory. If it is available then memory is
allocated
to the process by creating a partition in memory. Like this depending on size of process and
available memory, partitions take place in main memory.
For example:-Consider following table with process and memory space

10 Explain LRU page replacement algorithm for following reference string. 7 0 1 2 0 3 0 4 2 3 0 3 2

1 2 0 1 7 0 1 Calculate the page fault.
ans
LRU:
1) The Least Recently Used (LRU) page replacement policy
replaces the page that has not been used for the longest
 period of time.
2) LRU replacement associates with each page the time of that
page's last use.
3) When a page must be replaced, LRU chooses the page that has
not been used for the longest period of time.
4) The LRU policy is often used as a page-replacement algorithm
and is considered to be good.
5)An LRU page-replacement algorithm may require substantial
hardware assistance.
Counters:
• In the simplest case, we associate with each page-table entry a
time-of-use field and add to the CPU a logical clock or counter.
• The clock is incremented for every memory reference.
• Whenever a reference to a page is made, the contents of the
clock register are copied to the time-of-use field in the pagetable entry for that page.
• In this way, we always have the "time" of the last reference to
each page. We replace the page with the smallest time value.
Stack:
• Another approach to implementing LRU replacement is to keep
a stack of page numbers.
• Whenever a page is referenced, it is removed from the stack
and put on the top.
• In this way, the most recently used page is always at the top of
the stack and the least recently used page is always at the
bottom.
Reference String: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
(Frame size have not mentioned in question so assume frame size as 3
or 4)
LRU: Assume frame size=3

11 List free space management techniques? Describe any one in detail.

ans 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 four approaches by using which, the free blocks in
the disk are managed.
1)Bit Vector
2)Linked List
3) Grouping
4)Counting
Bit Vector:
• The free-space list is implemented as a bit map or bit vector.
• Each block is represented by 1 bit. If the block is free, the bit is 1; if the block is
allocated, the bit is 0.
• For example, consider a disk where blocks
• 2, 3, 4, 5, 8, 9, 10, 11, 12, 13 are free and the rest of the blocks are allocated.
• The free-space bit map would be : 0011110011111100

12 List free space management techniques? Describe any one in detail.

ans 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 four approaches by using which, the free blocks in
the disk are managed.
• Bit Vector
• Linked List
• Grouping
• Counting
Bit Vector:
• The free-space list is implemented as a bit map or bit vector.
• Each block is represented by 1 bit. If the block is free, the bit is
1; if the block is allocated, the bit is 0.
• For example, consider a disk where blocks
• 2, 3, 4, 5, 8, 9, 10, 11, 12, 13 are free and the rest of the blocks
are allocated.
• The free-space bit map would be : 0011110011111100
0=Free block
1= Allocated block The main advantage of this approach is its relative simplicity and its
efficiency in finding the first free block or n consecutive free blocks on the disk.
Linked List
• In this approach, the free disk blocks are linked together i.e. a
free block contains a pointer to the next free block.
• The block number of the very first disk block is stored at a
separate location on disk and is also cached in memory.
• In this approach, link all the disk blocks together, keeping a
pointer to the first free block.
• This block contains a pointer to the next free disk block, and so
on.
 Chapter NO 6 FILE MANAGEMENT
Q1 Describe the sequential file access method.and direct access method
Most programming languages provide two different ways to access data stored in a file i.e.
information. When it is used, this information must be accessed and read into computer
memory. The information in the file can be accessed in several ways
Sequential Access Method:
The simplest access method is sequential access. 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).

If you want to read a piece of data that is stored at the very end of the file, you have to read all
of the data that comes before it-you cannot jump directly to the desired data. This is similar to
the way cassette tape players work. If you want to listen to the last song on a cassette tape,
you have to either fast-forward over all of the songs that come before it or listen to them
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.
A relative block number is an index relative to the beginning of the file.
Thus, the first relative block of the file is 0, the next is 1, and so on, even though the
actual absolute disk address of the block may be 14703 for the first block and 3192
for the second. When you work with a direct access file (which is also known as a
random access file), you can jump directly to any piece of data in the file without
reading the data that comes before it. This is similar to the way a CD player or an
MP3 player works. You can jump directly to any song that you want to listen to.
Sequential access files are easy to work with, and you can use them to gain an
 understanding of basic file operations.

2 Enlist different file allocation methods? Explain contiguous allocation method in detail
Ans From the user’s point of view, a file is an abstract data type. It can be created,
opened, written, read, closed and deleted without any real concern for its
implementation. The implementation of a file is a problem for the operating
system.
The main problem is how to allocate space to these files so that disk space is
effectively utilized and files can be quickly accessed.
Three major methods of allocating disk space are in wide use:
• Contiguous
• Linked
• Indexed
Contiguous Allocation
• 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.
 Advantages of Contiguous File Allocation Method:
1. Supports both sequential and direct access methods.
2. Contiguous allocation is the best form of allocation for
sequential files. Multiple blocks can be brought in at a time to
improve I/O performance for sequential processing.
3. It is also easy to retrieve a single block from a file. For
example, if a file starts at block ‘n’ and the ith block of the file
is wanted, its location on secondary storage is simply n + i.
4. Reading all blocks belonging to each file is very fast.
5. Provides good performance.
Disadvantages of Contiguous File Allocation Method:
1. Suffers from external fragmentation.
2. Very difficult to find contiguous blocks of space for new files.
3. Also with pre-allocation, it is necessary to declare the size of
the file at the time of creation which many a times is difficult to
estimate.
4. Compaction may be required and it can be very expensive
3 List and explain any four attributes of file
Ans File attributes:
• Name: The symbolic file name is the only information kept in human readable form.
• Identifier: File system gives a unique tag or number that identifies file within file
system and which is used to refer files internally.
• Type: This information is needed for those systems that support different types.
• Location: This information is a pointer to a device and to the location of the file on
that device.
• Size: The current size of the file (in bytes, words or blocks) and possibly the maximum
allowed size are included in this attribute.
• Protection: Access control information determines that who can do reading, writing,
executing and so on.
• Time, Date and User Identification: This information may be kept for creation, Last
modification and last use. These data can be useful for protection, security and usage
monitoring.
4 Explain any six file operations performed by OS
ANS Creating a file: Two steps are necessary to create a file. First space in the file system must be
 found for the file. Second an entry for the new file must be made in the directory. The
directory entry records the name of the file and the location in the file system.
Writing a file: To write a file, we make a system call specifying both the name of the
file and the information to be written to the file. Given the name of the file, the system
searches the directory to find the location of file then the write pointer must be updated
whenever a write occurs
Reading a file: To read from a file, we use a system call that specifies the name of the
file and where (in memory) the next block of the file should be put. System needs to
keep a read pointer to location in the file where the next read is to take place. Once the
read has taken place, the read pointer is updated.
Repositioning within a file: The directory is searched for the appropriate entry, and
the current file position is set to a given value. Repositioning within a file does not
need to involve any actual I/O. This file operation is also known as a file seeks.
Deleting a file: To delete a file, we search the directory for the named file. Having
found the associated directory entry, we release all file space and erase the directory
entry.
Truncating a file: Instead of deleting a file and then recreate it, this function allows all
attributes to remain unchanged but for the file to be reset to length zero. User wants to
erase the contents of the file.
Other common operations include appending new information to the end of an existing
file, and renaming an existing file.
5 Explain FIFO (First in First out) page replacement algorithm for reference string
7012030423103.
Ans First-In-First-Out (FIFO) Algorithm: A FIFO replacement associates with each page the time
when that page was bought into memory. When the page must be replaced, the oldest page is
chosen. It maintains a FIFO queue to hold all pages in memory. We replace the page at the
head of the queue. When a page is brought into the memory, we insert it at the tail of the
queue. Reference string: Consider three frames are available.
6

7 Describe the concept of virtual memory with suitable example.

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. Example: For example, a 16M program can run on a 4M machine by
carefully choosing which 4M to keep in memory at each instant, with pieces of the program
being swapped between disk and memory as needed.
 8 Explain file structure with example
Ans Files can be structured in any of serval ways. Three common possibilities are depicted in fig.
The file in fig is an unstructured sequence of bytes. In this model, a file is a sequence of fixed-
length records, each with some internal structure. The third kind of file structure is shown in
fig. In this organization, a file consists of a tree of records, not necessarily all the same length,
each containing a key field in a fixed position in the record.

9 Explain two level Directory Structure with suitable diagram

Ans Two level directory:
The standard solution to limitations of single-level directory is to create a separate
directory for each user. In the two-level directory structure, each user has his own user
file directory (UFD). The UFDs have similar structures, but each lists only the files of a
single user. When a user job starts or a user logs in, the system's master file directory
(MFD) is searched. The MFD is indexed by user name or account number, and each
entry points to the UFD for that user.
Advantages:
i) Path name
ii) Can have the same file name for different user
iii) Efficient searching
Disadvantages:
No grouping capability