Important Questions

Unit 3:

Q)Define page fault. Explain in detail about FIFO, LRU and Optimal page
replacement algorithms using the page reference string: 5, 6, 7, 5, 9, 8 2, 1, 0, 4, 2, 4,
5, 2, 1, 0,5, 4. Use 3 frames for memory. Analyse the number of page faults for each
algorithm.(#paper)

Page Fault

A page fault occurs when a program tries to access a page that is not currently in
memory. The operating system then has to fetch the requested page from the disk and
load it into memory. If the memory is full, a page replacement algorithm decides
which page to replace.

Page Replacement Algorithms

1. FIFO (First-In, First-Out)

FIFO is the simplest page replacement algorithm. It replaces the oldest page in
memory (the one that has been there the longest).

Steps:

1. Start with an empty memory of 3 frames.

2. For each page reference:
o If the page is not in memory, a page fault occurs.
o If the memory is full, replace the oldest page in memory.

Page Reference String: 5, 6, 7, 5, 9, 8, 2, 1, 0, 4, 2, 4, 5, 2, 1, 0, 5, 4

Step Page Reference Frames Page Fault?

1 5 [5, -, -] Yes
2 6 [5, 6, -] Yes
3 7 [5, 6, 7] Yes
4 5 [5, 6, 7] No
5 9 [9, 6, 7] Yes
6 8 [9, 8, 7] Yes
7 2 [9, 8, 2] Yes
8 1 [1, 8, 2] Yes
9 0 [1, 0, 2] Yes
Step Page Reference Frames Page Fault?

10 4 [1, 0, 4] Yes
11 2 [2, 0, 4] Yes
12 4 [2, 0, 4] No
13 5 [2, 5, 4] Yes
14 2 [2, 5, 4] No
15 1 [2, 5, 1] Yes
16 0 [0, 5, 1] Yes
17 5 [0, 5, 1] No
18 4 [0, 5, 4] Yes

Total Page Faults: 13

2. LRU (Least Recently Used)

LRU replaces the page that has not been used for the longest period of time.

Steps:

1. Start with an empty memory of 3 frames.

2. For each page reference:
o If the page is not in memory, a page fault occurs.
o If the memory is full, replace the page that has not been used for the
longest time.

Page Reference String: 5, 6, 7, 5, 9, 8, 2, 1, 0, 4, 2, 4, 5, 2, 1, 0, 5, 4

Step Page Reference Frames Page Fault?

1 5 [5, -, -] Yes
2 6 [5, 6, -] Yes
3 7 [5, 6, 7] Yes
4 5 [5, 6, 7] No
5 9 [9, 6, 7] Yes
6 8 [9, 8, 7] Yes
7 2 [2, 8, 7] Yes
8 1 [2, 1, 7] Yes
9 0 [2, 1, 0] Yes
10 4 [4, 1, 0] Yes
11 2 [4, 1, 2] Yes
12 4 [4, 1, 2] No
13 5 [5, 1, 2] Yes
Step Page Reference Frames Page Fault?
14 2 [5, 1, 2] No
15 1 [5, 1, 2] No
16 0 [0, 1, 2] Yes
17 5 [0, 1, 5] Yes
18 4 [0, 1, 4] Yes

Total Page Faults: 14

3. Optimal Page Replacement

The optimal algorithm replaces the page that will not be used for the longest period of
time in the future.

Steps:

1. Start with an empty memory of 3 frames.

2. For each page reference:
o If the page is not in memory, a page fault occurs.
o If the memory is full, replace the page that will not be used for the
longest time in the future.

Page Reference String: 5, 6, 7, 5, 9, 8, 2, 1, 0, 4, 2, 4, 5, 2, 1, 0, 5, 4

Step Page Reference Frames Page Fault?

1 5 [5, -, -] Yes
2 6 [5, 6, -] Yes
3 7 [5, 6, 7] Yes
4 5 [5, 6, 7] No
5 9 [9, 6, 7] Yes
6 8 [9, 8, 7] Yes
7 2 [9, 8, 2] Yes
8 1 [1, 8, 2] Yes
9 0 [1, 0, 2] Yes
10 4 [4, 0, 2] Yes
11 2 [4, 0, 2] No
12 4 [4, 0, 2] No
13 5 [5, 0, 2] Yes
14 2 [5, 0, 2] No
15 1 [5, 0, 1] Yes
16 0 [5, 0, 1] No
17 5 [5, 0, 1] No
Step Page Reference Frames Page Fault?
18 4 [5, 4, 1] Yes

Total Page Faults: 11

Summary of Page Faults:

 FIFO: 13 page faults

 LRU: 14 page faults
 Optimal: 11 page faults

The Optimal page replacement algorithm yields the fewest page faults, as expected,
since it has the advantage of knowing future references. LRU generally performs
better than FIFO in most cases, but in this particular sequence, LRU resulted in
slightly more page faults.

Unit 4:

Q) Discuss in detail about file access and allocation methods and its advantages and
disadvantages.(#paper)

File Access Methods

File access methods define how data is read from and written to files. There are three
primary methods:

1. Sequential Access

Sequential access means data is processed in order, one record after another. This
method is suitable for applications that need to process data in a linear sequence, such
as text editors and compilers.

Advantages:

 Simple to implement.
 Efficient for processing large amounts of data sequentially.

Disadvantages:

 Inefficient for random access to data.

 Inflexible for applications that require frequent updates to the data.

2. Direct Access
Direct access (or random access) allows data to be read or written in any order. This
method is suitable for applications that require fast access to specific records, such as
databases.

Advantages:

 Fast access to any part of the file.

 Efficient for applications that require frequent read/write operations on
specific data points.

Disadvantages:

 More complex to implement.

 Requires additional data structures to maintain indices for fast access.

3. Indexed Access

Indexed access uses an index to keep track of the locations of data within a file. The
index is used to quickly locate and access specific records. This method combines
aspects of both sequential and direct access.

Advantages:

 Fast access to specific records.

 Efficient for large files where direct access is needed frequently.

Disadvantages:

 More complex to implement.

 Additional overhead to maintain the index.
 Extra storage required for the index.

File Allocation Methods

File allocation methods determine how disk space is allocated to files. There are three
main methods:

1. Contiguous Allocation

In contiguous allocation, each file occupies a set of contiguous blocks on the disk.
This method is simple and supports both sequential and direct access.

Advantages:

 Simple to implement.
 Efficient for sequential access.
 Supports direct access with minimal overhead.

Disadvantages:
  Can lead to fragmentation, making it difficult to find contiguous space for new
files.
 May require periodic defragmentation.
 Hard to predict the size of the file in advance, leading to possible waste of
space or need for reallocation.

2. Linked Allocation

In linked allocation, each file is a linked list of disk blocks, where each block contains
a pointer to the next block. This method eliminates fragmentation issues seen in
contiguous allocation.

Advantages:

 No external fragmentation.
 Easy to grow files incrementally.

Disadvantages:

 Inefficient for direct access because it requires traversing the linked list.
 Additional overhead for storing pointers.
 Increased risk of data corruption if a pointer is lost or damaged.

3. Indexed Allocation

In indexed allocation, each file has an index block, which contains pointers to all the
data blocks of the file. This method supports both sequential and direct access
efficiently.

Advantages:

 Supports direct access efficiently.

 Reduces external fragmentation.
 Can handle files of varying sizes easily.

Disadvantages:

 Requires additional storage for the index block.

 Potential for wasted space if the index block is not fully utilized.
 More complex to implement.

Analysis of Advantages and Disadvantages

Sequential Access:

 Advantages: Simplicity, efficiency for large, linear data processing.

 Disadvantages: Inefficient for random access, inflexible for frequent updates.

Direct Access:
  Advantages: Fast random access, suitable for databases.
 Disadvantages: Complexity, need for additional data structures.

Indexed Access:

 Advantages: Fast specific record access, efficient for large files.

 Disadvantages: Complexity, overhead for index maintenance.

Contiguous Allocation:

 Advantages: Simplicity, efficiency for sequential and direct access.

 Disadvantages: Fragmentation, space prediction challenges.

Linked Allocation:

 Advantages: No external fragmentation, easy incremental growth.

 Disadvantages: Inefficiency for direct access, pointer overhead, corruption
risk.

Indexed Allocation:

 Advantages: Efficient direct access, handles varying file sizes well.

 Disadvantages: Index block storage overhead, potential wasted space,
complexity.

Q) Discuss in detail about SSTF, SCAN, CSCAN and CLOOK disk scheduling
algorithm to minimize the seek time for a given set of disk I/O requests? #(paper)

Shortest Seek Time First (SSTF)

Description:

 SSTF selects the disk I/O request that is closest to the current position of the
read/write head, minimizing the seek time for each request.
 This algorithm works similarly to the Shortest Job First (SJF) scheduling in
CPU scheduling.

Advantages:

 Reduces the average seek time compared to the First-Come, First-Served

(FCFS) algorithm.
 Provides good performance in terms of seek time for most workloads.

Disadvantages:

 Can cause starvation, especially for requests that are far from the current head
position, as closer requests are continuously prioritized.
 Performance can degrade in the case of heavily skewed request distributions.
Example:

Assume the disk head is initially at track 50, and there are requests for tracks 45, 20,
35, 75, and 85.

1. Current position: 50
2. Nearest request: 45
3. Next nearest: 35
4. Next nearest: 20
5. Next nearest: 75
6. Next nearest: 85

The order of servicing will be: 50 → 45 → 35 → 20 → 75 → 85.

(another example)

SCAN (Elevator Algorithm)

Description:

 SCAN moves the disk arm towards one end of the disk, servicing all requests
along the way, and then reverses direction at the end.
 It operates like an elevator, moving in one direction until the end, then
reversing.

Advantages:
  Provides a more uniform wait time compared to SSTF.
 Prevents starvation, as all requests are eventually serviced when the head
changes direction.

Disadvantages:

 Longer seek times for requests at the extreme ends if the head is currently
servicing the opposite end.
 Might result in less optimal seek times for middle requests compared to SSTF.

Example:

Assume the disk head is initially at track 50, moving towards track 0, and there are
requests for tracks 45, 20, 35, 75, and 85.

1. Current position: 50
2. Next: 45
3. Next: 35
4. Next: 20
5. Reverse direction
6. Next: 75
7. Next: 85

The order of servicing will be: 50 → 45 → 35 → 20 → 0 → 75 → 85.

(another example)
Circular SCAN (CSCAN)

Description:

 CSCAN is a variant of SCAN. The disk arm moves in one direction, servicing
requests until it reaches the end, then it jumps back to the beginning without
servicing any requests and starts again.
 This ensures a more uniform wait time, as each request is treated equally
regardless of position.

Advantages:

 Provides more uniform wait times compared to SCAN, especially in systems

with a heavy load of requests.
 Reduces the wait time for requests at the start of the disk after a wrap-around.

Disadvantages:

 Slightly longer average seek times compared to SCAN due to the jump back to
the beginning.

Example:

Assume the disk head is initially at track 50, moving towards track 0, and there are
requests for tracks 45, 20, 35, 75, and 85.

1. Current position: 50
2. Next: 45
3. Next: 35
4. Next: 20
5. Jump to the end
6. Next: 75
7. Next: 85

The order of servicing will be: 50 → 45 → 35 → 20 → 0 → 75 → 85.

(another example)
Circular LOOK (CLOOK)

Description:

 CLOOK is a variant of CSCAN. The disk arm moves in one direction,

servicing requests until it reaches the end of the last request in that direction,
then jumps back to the first request in the other direction.
 Unlike CSCAN, it does not move to the physical end of the disk but only to
the last request.

Advantages:

 More efficient than CSCAN as it avoids the unnecessary seek to the physical
end of the disk.
 Provides more uniform wait times similar to CSCAN.

Disadvantages:

 Slightly more complex to implement compared to SCAN and CSCAN.

 May still result in slightly longer seek times compared to SSTF.

Example:

Assume the disk head is initially at track 50, moving towards track 0, and there are
requests for tracks 45, 20, 35, 75, and 85.

1. Current position: 50
 2. Next: 45
3. Next: 35
4. Next: 20
5. Jump to the first request in the other direction
6. Next: 75
7. Next: 85

The order of servicing will be: 50 → 45 → 35 → 20 → 75 → 85.

(another example)

Summary

Each disk scheduling algorithm has its advantages and disadvantages, and the choice
of algorithm can significantly affect the performance of a system depending on the
specific workload and access patterns.

 SSTF offers the shortest average seek time but can cause starvation.
 SCAN provides a more uniform wait time but may lead to longer seek times
for some requests.
 CSCAN ensures more uniform wait times across all requests but has slightly
longer average seek times due to the jump back to the beginning.
 CLOOK optimizes CSCAN by only moving to the last request in each
direction, reducing unnecessary seeks.

Q) Consider the following example: A disk has 200 tracks (numbered from 0 to 199).
The disk head is currently at track 53 and moving towards track 199. The queue of
pending requests in FIFO order is: 94, 179, 66, 123, 11, 144, 71. Calculate the total
seek distance (number of tracks) the disk head will travel to complete all requests.
#(paper)

To calculate the total seek distance for each disk scheduling algorithm, we'll go
through the pending requests and compute the distances traveled by the disk head.
The disk head is initially at track 53 and moving towards track 199.

Given Data:

 Number of tracks: 200 (0 to 199)

 Initial head position: 53
 Direction: Towards track 199
 Pending requests (FIFO order): 94, 179, 66, 123, 11, 144, 71

1. Shortest Seek Time First (SSTF)

The disk head will always move to the closest request next.

Steps:

1. Current position: 53
2. Nearest request: 66 (distance = 66 - 53 = 13)
3. Nearest request: 71 (distance = 71 - 66 = 5)
4. Nearest request: 94 (distance = 94 - 71 = 23)
5. Nearest request: 123 (distance = 123 - 94 = 29)
6. Nearest request: 144 (distance = 144 - 123 = 21)
7. Nearest request: 179 (distance = 179 - 144 = 35)
8. Nearest request: 11 (distance = 179 - 11 = 168)

Total Seek Distance:

13+5+23+29+21+35+168=29413 + 5 + 23 + 29 + 21 + 35 + 168 =
29413+5+23+29+21+35+168=294

2. SCAN (Elevator Algorithm)

The disk head moves towards the end of the disk (track 199) servicing requests along
the way, then reverses direction.

Steps:

1. Current position: 53
2. Service: 66 (distance = 66 - 53 = 13)
3. Service: 71 (distance = 71 - 66 = 5)
4. Service: 94 (distance = 94 - 71 = 23)
5. Service: 123 (distance = 123 - 94 = 29)
6. Service: 144 (distance = 144 - 123 = 21)
7. Service: 179 (distance = 179 - 144 = 35)
8. Move to the end of the disk (track 199) (distance = 199 - 179 = 20)
 9. Reverse direction, service: 11 (distance = 199 - 11 = 188)

Total Seek Distance:

13+5+23+29+21+35+20+188=33413 + 5 + 23 + 29 + 21 + 35 + 20 + 188 =
33413+5+23+29+21+35+20+188=334

3. Circular SCAN (CSCAN)

The disk head moves towards the end of the disk (track 199), services requests, then
jumps back to the beginning and services remaining requests.

Steps:

1. Current position: 53
2. Service: 66 (distance = 66 - 53 = 13)
3. Service: 71 (distance = 71 - 66 = 5)
4. Service: 94 (distance = 94 - 71 = 23)
5. Service: 123 (distance = 123 - 94 = 29)
6. Service: 144 (distance = 144 - 123 = 21)
7. Service: 179 (distance = 179 - 144 = 35)
8. Move to the end of the disk (track 199) (distance = 199 - 179 = 20)
9. Jump to the beginning of the disk (track 0) (distance = 199 - 0 = 199)
10. Service: 11 (distance = 11 - 0 = 11)

Total Seek Distance:

13+5+23+29+21+35+20+199+11=35613 + 5 + 23 + 29 + 21 + 35 + 20 + 199 + 11 =
35613+5+23+29+21+35+20+199+11=356

4. Circular LOOK (CLOOK)

The disk head moves towards the end servicing requests, then jumps to the first
request in the opposite direction and continues servicing.

Steps:

1. Current position: 53
2. Service: 66 (distance = 66 - 53 = 13)
3. Service: 71 (distance = 71 - 66 = 5)
4. Service: 94 (distance = 94 - 71 = 23)
5. Service: 123 (distance = 123 - 94 = 29)
6. Service: 144 (distance = 144 - 123 = 21)
7. Service: 179 (distance = 179 - 144 = 35)
8. Jump to the first request in the opposite direction, service: 11 (distance = 179 -
11 = 168)

Total Seek Distance:

13+5+23+29+21+35+168=29413 + 5 + 23 + 29 + 21 + 35 + 168 =
29413+5+23+29+21+35+168=294

Summary

 SSTF Total Seek Distance: 294

 SCAN Total Seek Distance: 334
 CSCAN Total Seek Distance: 356
 CLOOK Total Seek Distance: 294

In this case, both SSTF and CLOOK provide the minimum total seek distance of 294
tracks.

Q) Explain the importance of free-space management. What techniques are used to

track free space? (#paper)

The Importance of Free-Space Management

Free-space management is crucial for the effective operation of a file system. It

ensures that the disk space is utilized efficiently, which is vital for maintaining the
performance, reliability, and longevity of the storage system. Here are the key reasons
why free-space management is important:

1. Efficient Disk Utilization:

o Ensures optimal use of available storage space.
o Minimizes wasted space, allowing more data to be stored.
2. Performance Optimization:
o Speeds up file creation and extension by quickly identifying free
blocks.
o Reduces the time spent searching for free space during file operations.
3. Fragmentation Reduction:
o Helps in allocating contiguous blocks, reducing fragmentation.
o Fragmentation can slow down file access and degrade system
performance over time.
4. Reliability and Consistency:
o Maintains accurate records of free and allocated space, preventing data
corruption.
o Ensures that the file system remains consistent and reliable, even after
crashes or power failures.
5. Scalability:
o Supports the management of large volumes of data and numerous files.
o Adapts to dynamic changes in storage requirements, such as the
addition or deletion of files.

1) Bit Vector

Frequently, 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, 17,
18, 25, 26, and 27 are free and the rest of the blocks are allocated. The free-
space bit map would be

001111001111110001100000011100000 ...

 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.

2) Linked List :-

 Another approach to free-space management is to link together all the free

disk blocks, keeping a pointer to the first free block in a special location on the
disk and caching it in memory.
 This first block contains a pointer to the next free disk block, and so on.
 n the example in which blocks 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26,
and 27 were free and the rest of the blocks were allocated. In this situation, we
would keep a pointer to block 2 as the first free block. Block 2 would contain
a pointer to block 3, which would point to block 4, which would point to block
5, which would point to block 8, and so on.
 This scheme is not efficient; to traverse the list, we must read each block,
which requires substantial I/O time.

 3) Grouping

A modification of the free-list approach stores the addresses of n free blocks in

the first free block. The first n−1 of these blocks are actually free. The last
block contains the addresses of another n free blocks, and so on. The addresses
 of a large number of free blocks can now be found quickly, unlike the
situation when the standard linked-list approach is used.

 4) Counting

Rather than keeping a list of n free disk addresses, we can keep the address of
the first free block and the number (n) of free contiguous blocks that

follow the first block. Each entry in the free-space list then consists of a disk
address and a count.

Q) File Implementation:

File System Implementation

File system implementation involves organizing, managing, and accessing data on a

storage device. It encompasses various techniques and data structures to efficiently
store, retrieve, and manage files.

Access Methods

Access methods determine how data is read from and written to files. There are three
primary methods:

1. Sequential Access:
o Data is accessed in a linear sequence.
o Suitable for applications like text editors and compilers.
o Advantages: Simple to implement, efficient for sequential processing.
o Disadvantages: Inefficient for random access.
2. Direct Access:
o Data can be accessed in any order using an index or offset.
o Suitable for databases and systems requiring fast access to specific
records.
o Advantages: Fast random access.
o Disadvantages: More complex to implement, requires additional data
structures.
3. Indexed Access:
o Uses an index to locate data blocks.
o Combines aspects of both sequential and direct access.
o Advantages: Fast access to specific records.
o Disadvantages: Additional overhead to maintain the index.

File System Structure

The file system structure defines how files and directories are organized and
managed. Common structures include:
 1. Single-Level Directory:
o All files are contained in a single directory.
o Simple but not scalable for many files.
2. Two-Level Directory:
o Separate directories for each user.
o Better organization but still limited scalability.
3. Tree-Structured Directory:
o Hierarchical organization with directories and subdirectories.
o Scalable and flexible for complex file systems.
4. Acyclic-Graph Directory:
o Allows sharing of files and directories.
o Avoids duplication but more complex to manage.
5. General Graph Directory:
o Allows links between directories, potentially creating cycles.
o Provides maximum flexibility but requires cycle detection and
handling.

Directory Implementation

Directory implementation involves managing the organization and access to files

within a directory structure. Key methods include:

1. Linear List:
o A simple list of file names with pointers to their data blocks.
o Advantages: Simple to implement.
o Disadvantages: Slow for large directories due to linear search times.
2. Hash Table:
o Uses a hash function to map file names to their locations.
o Advantages: Faster access compared to linear lists.
o Disadvantages: Potential for hash collisions, more complex to
implement.
3. Tree Structures:
o Organize directories in a hierarchical manner.
o Advantages: Efficient for large directories, supports hierarchical
searches.
o Disadvantages: More complex to implement and manage.

Allocation Methods

Allocation methods determine how disk space is assigned to files. Common methods
include:

1. Contiguous Allocation:
o Files are stored in contiguous blocks of disk space.
o Advantages: Simple, supports sequential and direct access.
o Disadvantages: Fragmentation, space prediction challenges.
2. Linked Allocation:
o Files are stored as linked lists of disk blocks.
o Advantages: No external fragmentation, easy incremental growth.
o Disadvantages: Inefficient for direct access, pointer overhead.
 3. Indexed Allocation:
o Files use an index block to keep track of all data blocks.
o Advantages: Efficient direct access, handles varying file sizes well.
o Disadvantages: Index block storage overhead, complexity.

Free-Space Management

Free-space management is crucial for maintaining efficient disk utilization.

Techniques include:

1. Bitmaps (Bit Vectors):

o Use bits to represent free and allocated blocks.
o Advantages: Simple, efficient space usage.
o Disadvantages: Searching for free space can be time-consuming.
2. Linked Lists:
o Use pointers to link free blocks together.
o Advantages: Simple, easy to manage.
o Disadvantages: Inefficient for random access, pointer overhead.
3. Grouping:
o Group leaders contain pointers to free blocks.
o Advantages: Reduces the number of pointers needed.
o Disadvantages: More complex than simple linked lists.
4. Counting:
o Track the starting address and count of contiguous free blocks.
o Advantages: Efficient for managing large contiguous spaces.
o Disadvantages: Less efficient for non-contiguous space management.

File Operations

File operations include the actions that can be performed on files, such as:

 Create a file
 Writing a file
 Reading a file
 Repositioning within a file
 Deleting a file
 Truncating a file