Page Fault Calculation: FIFO and LRU

Given Data

• Reference string: 4, 7, 6, 1, 7, 6, 1, 2, 7, 2
• Number of frames: 3

1. FIFO (First In First Out)

Replace the oldest loaded page when frames are full.

FIFO Page Faults = 6, Hits = 4

2. LRU (Least Recently Used)

Replace the page not used for the longest time.

Let me recheck LRU at ref = 2 (step 8).

After processing 4,7,6,1,7,6,1 the recency order is: 1 (MRU), 6, 7 (LRU). On fault for page 2, replace 7 (LRU).

Frames now: 1, 6, 2. Recency: 2, 1, 6.

Recheck step 9 (ref = 7): recency order is 2 (MRU), 1, 6 (LRU). Replace 6 (LRU).

Frames now: 1, 2, 7. Recency: 7, 2, 1.

Corrected LRU trace:

LRU Page Faults = 6, Hits = 4

Summary

Both FIFO and LRU produce 6 page faults for this reference string with 3 frames.

Priority Scheduling (Non-Preemptive) - Average WT and TAT

Step 1 - Extract: Given Data

Priority 1 = highest. Assume non-preemptive priority scheduling.

Step 2 - Solve

Execution Order

• t = 0: Only A available → A runs 0 to 3.
• t = 3: Ready = B (P3), C (P2), D (P1). Highest priority = D → D runs 3 to 5.
• t = 5: Ready = B (P3), C (P2). Higher priority = C → C runs 5 to 9.
• t = 9: Only B remains → B runs 9 to 11.

Gantt Chart

| A | D |  C  | B |
0   3   5     9  11

Completion, Turnaround, Waiting Times

TAT = CT − AT, WT = TAT − BT

Averages

$$\text{Avg TAT} = \frac{3 + 9 + 6 + 2}{4} = \frac{20}{4} = 5 \text{ ms}$$

$$\text{Avg WT} = \frac{0 + 7 + 2 + 0}{4} = \frac{9}{4} = 2.25 \text{ ms}$$

Final Result

Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process. No process can proceed, release, or be preempted. --- For a deadlock...

File Allocation Techniques: Contiguous and Linked List

1. Contiguous Allocation

In contiguous allocation, each file is stored as a contiguous run of disk blocks on the disk. The directory entry for each file records the starting block address and the length of the file.

Example:

• On a disk with 1-KB blocks, a 50-KB file is allocated 50 consecutive blocks.
• On a disk with 4-KB blocks, the same file would need 25 consecutive blocks.
• Each file begins at the start of a new block; any wasted space occurs only at the end of the last block.

Advantages

• Simple to implement -- the directory only needs to store the start address and length.
• Excellent read performance -- since blocks are consecutive, sequential and random access are both fast (minimal disk seeks).

Disadvantages

• External fragmentation -- over time, free space becomes scattered in small pieces, making it difficult to find a large contiguous area for new files.
• Difficult to extend files -- if a file needs to grow, there may be no free space immediately after its last block.
• Difficult to find space for new files when free blocks are fragmented.

2. Linked List Allocation

In linked list allocation, each file is stored as a linked list of disk blocks. The first word of each block is used as a pointer to the next block, and the remaining space in the block holds actual data.

Block 4        Block 7        Block 2        Block 9
[ptr=7|data]-->[ptr=2|data]-->[ptr=9|data]-->[EOF|data]

The directory entry stores only the address of the first block of the file; the chain of pointers leads to all subsequent blocks.

Variant: FAT (File Allocation Table)

• The pointers are moved out of the data blocks and stored in a separate table called the FAT.
• The entire block becomes available for data.
• The FAT is used as a linked list; the directory entry contains the block number of the first block, and the FAT is looked up to find the next block until a special end-of-file (EOF) value is reached.

Advantages

• Solves all problems of contiguous allocation -- no external fragmentation, files can grow easily by linking new blocks anywhere on disk.
• No need for compaction of free space.

Disadvantages

• Only efficient for sequential access -- random access is excessively slow because to reach block n, all n-1 preceding blocks must be traversed.
• Space overhead for pointers -- each block loses some bytes to store the next-block pointer.
• Each block access may require a disk seek, increasing access time.

Comparison Summary

A lock variable is a shared variable used to control access to a critical region. It is one of the software-based approaches to achieving mutual exclusion with busy waiting. --- A single shared variable called the lock is maintained, ini...

Priority Scheduling (Non-Preemptive) - Average WT and TAT

Step 1 - Extract: Given Data

Priority 1 = highest. Assume non-preemptive priority scheduling.

Step 2 - Solve

Execution Order

• t = 0: Only A available → A runs 0 to 3.
• t = 3: Ready = B (P3), C (P2), D (P1). Highest priority = D → D runs 3 to 5.
• t = 5: Ready = B (P3), C (P2). Higher priority = C → C runs 5 to 9.
• t = 9: Only B remains → B runs 9 to 11.

Gantt Chart

| A | D |  C  | B |
0   3   5     9  11

Completion, Turnaround, Waiting Times

TAT = CT − AT, WT = TAT − BT

Averages

$$\text{Avg TAT} = \frac{3 + 9 + 6 + 2}{4} = \frac{20}{4} = 5 \text{ ms}$$

$$\text{Avg WT} = \frac{0 + 7 + 2 + 0}{4} = \frac{9}{4} = 2.25 \text{ ms}$$

Final Result

Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process. No process can proceed, release, or be preempted. --- For a deadlock...

Page Fault Calculation: FIFO and LRU

Given Data

• Reference string: 4, 7, 6, 1, 7, 6, 1, 2, 7, 2
• Number of frames: 3

1. FIFO (First In First Out)

Replace the oldest loaded page when frames are full.

FIFO Page Faults = 6, Hits = 4

2. LRU (Least Recently Used)

Replace the page not used for the longest time.

Let me recheck LRU at ref = 2 (step 8).

After processing 4,7,6,1,7,6,1 the recency order is: 1 (MRU), 6, 7 (LRU). On fault for page 2, replace 7 (LRU).

Frames now: 1, 6, 2. Recency: 2, 1, 6.

Recheck step 9 (ref = 7): recency order is 2 (MRU), 1, 6 (LRU). Replace 6 (LRU).

Frames now: 1, 2, 7. Recency: 7, 2, 1.

Corrected LRU trace:

LRU Page Faults = 6, Hits = 4

Summary

Both FIFO and LRU produce 6 page faults for this reference string with 3 frames.

File Allocation Techniques: Contiguous and Linked List

1. Contiguous Allocation

In contiguous allocation, each file is stored as a contiguous run of disk blocks on the disk. The directory entry for each file records the starting block address and the length of the file.

Example:

• On a disk with 1-KB blocks, a 50-KB file is allocated 50 consecutive blocks.
• On a disk with 4-KB blocks, the same file would need 25 consecutive blocks.
• Each file begins at the start of a new block; any wasted space occurs only at the end of the last block.

Advantages

• Simple to implement -- the directory only needs to store the start address and length.
• Excellent read performance -- since blocks are consecutive, sequential and random access are both fast (minimal disk seeks).

Disadvantages

• External fragmentation -- over time, free space becomes scattered in small pieces, making it difficult to find a large contiguous area for new files.
• Difficult to extend files -- if a file needs to grow, there may be no free space immediately after its last block.
• Difficult to find space for new files when free blocks are fragmented.

2. Linked List Allocation

In linked list allocation, each file is stored as a linked list of disk blocks. The first word of each block is used as a pointer to the next block, and the remaining space in the block holds actual data.

Block 4        Block 7        Block 2        Block 9
[ptr=7|data]-->[ptr=2|data]-->[ptr=9|data]-->[EOF|data]

The directory entry stores only the address of the first block of the file; the chain of pointers leads to all subsequent blocks.

Variant: FAT (File Allocation Table)

• The pointers are moved out of the data blocks and stored in a separate table called the FAT.
• The entire block becomes available for data.
• The FAT is used as a linked list; the directory entry contains the block number of the first block, and the FAT is looked up to find the next block until a special end-of-file (EOF) value is reached.

Advantages

• Solves all problems of contiguous allocation -- no external fragmentation, files can grow easily by linking new blocks anywhere on disk.
• No need for compaction of free space.

Disadvantages

• Only efficient for sequential access -- random access is excessively slow because to reach block n, all n-1 preceding blocks must be traversed.
• Space overhead for pointers -- each block loses some bytes to store the next-block pointer.
• Each block access may require a disk seek, increasing access time.

Comparison Summary

A lock variable is a shared variable used to control access to a critical region. It is one of the software-based approaches to achieving mutual exclusion with busy waiting. --- A single shared variable called the lock is maintained, ini...

Disk Scheduling Algorithms - Verified Solution

Given Data

• Request Queue: 35, 70, 45, 15, 65, 20, 80, 90, 75, 130
• Track range: 0 to 150
• Initial head position: 30
• Direction: Outward (toward higher tracks)

Sorted requests: 15, 20, 35, 45, 65, 70, 75, 80, 90, 130

1. SCAN

Head moves outward to 150, then reverses to service lower requests.

Order: 30 → 35 → 45 → 65 → 70 → 75 → 80 → 90 → 130 → 150 → 20 → 15

Total distance = (150 − 30) + (150 − 15) = 120 + 135 = 255 tracks

2. C-SCAN

Head moves outward to 150, jumps to 0, then continues servicing.

Order: 30 → 35 → ... → 130 → 150 → 0 → 15 → 20

Total = (150 − 30) + (150 − 0) + (20 − 0) = 120 + 150 + 20 = 290 tracks

(Equivalently, summing the individual steps: 5+10+20+5+5+5+10+40+20+150+15+5 = 290.)

3. LOOK

Head moves outward only to the last request (130), then reverses.

Order: 30 → 35 → ... → 130 → 20 → 15

Total = (130 − 30) + (130 − 15) = 100 + 115 = 215 tracks

4. C-LOOK

Head moves outward to last request (130), jumps to lowest request (15), continues outward.

Order: 30 → 35 → ... → 130 → 15 → 20

Total = (130 − 30) + (130 − 15) + (20 − 15) = 100 + 115 + 5 = 220 tracks

Summary

Short Notes: Virtual Memory and Race Condition

a. Virtual Memory (2.5 marks)

Virtual Memory is a memory management technique in which the operating system uses a portion of the hard disk as an extension of RAM, thereby increasing the effective size of usable memory beyond the physical RAM available.

Key Concepts:

• When the kernel needs memory for a new process but RAM is full, it writes the contents of a currently unused block of memory to the hard disk. This process is called swapping out.
• When the original contents are needed again, they are read back into memory (swapped in).
• The portion of the hard disk used for this purpose is called swap space.

Working Mechanism:

1. A segment number is used to find the segment descriptor.
2. A check is made whether the segment's page table is in memory; if not, a segment fault occurs.
3. The page table entry for the requested virtual page is examined; if the page is not in memory, a page fault is triggered.
4. If the page is in memory, the main memory address is extracted from the page table entry.
5. The offset is added to the page origin to give the final main memory address, and the read/write takes place.

Advantages and Disadvantages:

In Linux, swap space can be a swap partition (faster) or a swap file within the normal file system.

b. Race Condition (2.5 marks)

A Race Condition is a situation that occurs when two or more processes (or threads) read or write some shared data concurrently, and the final result depends on the precise order in which the processes execute.

Key Points:

• Race conditions typically occur inside a critical section, where multiple threads access shared resources.
• The result of execution differs according to the order in which threads or processes run, making the output unpredictable and incorrect.

Example Scenario:

• Two processes share a common variable (e.g., a counter).
• Process A reads the value, and before it writes back the updated value, Process B also reads the same old value.
• Both processes write their result, and one update is lost, producing an incorrect final value.

Illustration:

Shared variable: count = 5

Process A: reads count (5), computes count+1 = 6
Process B: reads count (5), computes count+1 = 6   <-- reads before A writes
Process A: writes count = 6
Process B: writes count = 6   <-- should be 7, but is 6 (incorrect!)

Prevention:

Race conditions can be prevented using synchronization mechanisms such as:

• Mutex locks
• Semaphores
• TSL (Test and Set Lock) instruction -- a shared lock variable is set to 1 before entering the critical section and reset to 0 after leaving, ensuring mutual exclusion.

In summary, race conditions arise due to uncontrolled concurrent access to shared data, and must be carefully managed to ensure correctness of programs.

Memory Allocation: First Fit, Next Fit, Best Fit

Step 1 - Given Data

Holes in memory order:

Successive requests: (a) 10 MB, (b) 10 MB.

Step 2 - Solve

First Fit

Allocates the first hole large enough, scanning from the start each time.

(a) 10 MB: Hole 1 (15 MB) $\ge 10$ → allocate. Hole 1 leftover $= 15 - 10 = 5$ MB.

(b) 10 MB: Scan from start: Hole 1 (5) ✗, Hole 2 (2) ✗, Hole 3 (10) $\ge 10$ → allocate. Leftover $= 0$ MB.

Result: (a) Hole 1, (b) Hole 3.

Next Fit

Like First Fit but resumes scanning from the position of the last allocation.

(a) 10 MB: Start at Hole 1 (15) → allocate. Pointer at Hole 1, leftover 5 MB.

(b) 10 MB: Resume from Hole 1: (5) ✗, Hole 2 (2) ✗, Hole 3 (10) → allocate. Pointer at Hole 3.

Result: (a) Hole 1, (b) Hole 3.

(Since scanning resumes at the last hole which is now too small, next fit gives the same result as first fit here.)

Best Fit

Allocates the smallest hole that is large enough.

(a) 10 MB: Candidates $\ge 10$: Hole 1 (15, leftover 5), Hole 3 (10, leftover 0), Hole 6 (20, leftover 10). Smallest sufficient = Hole 3 (exact fit). Leftover 0 MB.

(b) 10 MB: Remaining candidates $\ge 10$: Hole 1 (15, leftover 5), Hole 6 (20, leftover 10). Smallest = Hole 1. Leftover 5 MB.

Result: (a) Hole 3, (b) Hole 1.

Final Comparison

File Structures

A file structure defines how data is organized and stored within a file. Different types of files have different internal structures depending on their purpose and the programs that use them.

Different File Structures

1. Regular Files (User Files)

Regular files contain user information. They are the most common type of file and are generally of two subtypes:

a) ASCII Files

• Consist of lines of text.
• Each line is terminated by a carriage return or newline character.
• Can be displayed and printed directly.
• Can be created and edited by any ordinary text editor.
• Example: .txt files, source code files.

b) Binary Files

• Consist of a sequence of bytes only.
• They have some internal structure known only to the programs that use them.
• Cannot be read directly as plain text.
• Example: Executable files (compiled programs), object files.

2. Directory Files

• These are system files used for maintaining the structure of the file system.
• A directory file keeps track of the files contained within it, storing their names, identifiers, and locations.
• They form the hierarchical tree structure of the file system.

3. Character Special Files

• Related to Input/Output (I/O) operations of the computer.
• Used to model serial I/O devices such as terminals, printers, and network interfaces.
• They do not store data permanently; instead, they represent device streams.

Summary Table

Conclusion

Different file structures serve different purposes in an operating system. Regular files (ASCII and binary) store user data, directory files organize the file system hierarchy, and character special files provide an interface to hardware I/O devices. Understanding these structures is essential for effective file system management.

• Total tracks: 200 (numbered 0 to 199) - Request queue (in order): 45, 48, 29, 17, 80, 150, 28, 188 - Initial head position: 100 --- Direct Memory Access (DMA) is an I/O technique in which a dedicated hardware controller transfers data ...

The system maintains a free space list to keep track of disk blocks not allocated to any file or directory. The two main approaches are: 1. Bitmap (Bit Vector) 2. Linked List --- In the linked list approach, all free disk blocks are link...

Segmentation is a memory management technique in which memory is divided into variable size parts. Each part is known as a segment, which can be allocated to a process. The details about each segment are stored in a table called the segm...

--- A microkernel is a minimalist kernel design where only the most essential OS functions are kept in kernel (privileged) mode, and all other services are moved to user space as separate processes. - Basic inter-process communication (I...

Inter-Process Communication (IPC) refers to a mechanism where the operating system allows various processes to communicate with each other, synchronize their actions, and manage shared data. It allows a specific program to handle many us...