File Allocation Methods - Contiguous, Linked, Indexed

▶

Steps

setup

Initialize Disk and Allocation Processes

The disk is initialized with 10 free blocks. Three allocation processes are created for Contiguous, Linked, and Indexed methods, all ready to start allocation.

💡 Setting up the disk and allocation tasks is essential to simulate how each method will allocate blocks independently.

Line:

disk = [free]*10
processes = [Contiguous, Linked, Indexed]
for p in processes: p.state = 'ready'

💡 The system is ready to allocate the file using three different methods in parallel.

setup

Start Contiguous Allocation Process

The Contiguous Allocation process starts running to find a contiguous block of 4 free blocks on the disk.

💡 Contiguous allocation requires a continuous sequence of free blocks, so the process searches the disk from the start.

Line:

active_process = processes[0]  # Contiguous
active_process.state = 'running'

💡 The algorithm begins by scanning the disk for a contiguous free space large enough for the file.

compare

Contiguous Allocation: Check blocks 0 to 3

The Contiguous Allocation process checks blocks 0 to 3 to see if they are all free to allocate the file contiguously.

💡 This step verifies if the first 4 blocks are free, which is necessary for contiguous allocation.

Line:

if all(disk[i] == free for i in range(start, start+file_size)):
    allocate blocks

💡 Contiguous allocation requires a continuous free segment; this check confirms availability.

insert

Contiguous Allocation: Allocate blocks 0 to 3

Since blocks 0 to 3 are free, the Contiguous Allocation process marks these blocks as allocated to the file.

💡 Allocating contiguous blocks means the file occupies a continuous segment, simplifying access but requiring large free space.

Line:

for i in range(start, start+file_size):
    disk[i] = allocated_to_file
process.state = 'terminated'

💡 Contiguous allocation is efficient for sequential access but can cause fragmentation.

setup

Start Linked Allocation Process

The Linked Allocation process begins running to allocate 4 blocks anywhere on the disk, linking them via pointers.

💡 Linked allocation allows non-contiguous blocks but requires pointers to link blocks, enabling flexible allocation.

Line:

active_process = processes[1]  # Linked
active_process.state = 'running'

💡 Linked allocation can use scattered free blocks, avoiding fragmentation issues of contiguous allocation.

traverse

Linked Allocation: Find first free block (block 4)

The linked allocation process scans the disk to find the first free block to allocate to the file.

💡 Linked allocation can allocate blocks anywhere; it finds free blocks one by one and links them.

Line:

for i in range(len(disk)):
    if disk[i] == free:
        allocate block i

💡 Linked allocation does not require contiguous blocks, so it can start allocating from any free block.

traverse

Linked Allocation: Find next free block (block 5)

The process continues scanning to find the next free block to link after block 4.

💡 Each allocated block points to the next, so the process must find and link all required blocks.

Line:

for i in range(last_allocated+1, len(disk)):
    if disk[i] == free:
        allocate block i and link

💡 Linked allocation builds a chain of blocks, allowing flexible placement but requiring pointer management.

insert

Linked Allocation: Allocate blocks 6 and 7 similarly

The process finds blocks 6 and 7 free and allocates them, linking each to the previous block.

💡 The linked allocation continues until all 4 blocks are allocated and linked.

Line:

allocate block 6 and link
allocate block 7 and link
process.state = 'terminated'

💡 Linked allocation completes when all file blocks are allocated and linked, allowing scattered storage.

setup

Start Indexed Allocation Process

The Indexed Allocation process starts running to allocate 4 blocks and an index block that holds pointers to these blocks.

💡 Indexed allocation uses an index block to store pointers to all file blocks, allowing direct access.

Line:

active_process = processes[2]  # Indexed
active_process.state = 'running'

💡 Indexed allocation separates data blocks from the index block, enabling efficient random access.

insert

Indexed Allocation: Allocate index block (block 8)

The process finds block 8 free and allocates it as the index block to store pointers to the file's data blocks.

💡 The index block is crucial as it holds addresses of all allocated data blocks for direct access.

Line:

index_block = find_free_block()
disk[index_block] = index_block_marker

💡 Allocating a dedicated index block separates metadata from data, improving access speed.

insert

Indexed Allocation: Allocate data blocks 9, 1, 2, 3

The process allocates blocks 9, 1, 2, and 3 as data blocks and stores their pointers in the index block.

💡 Data blocks can be anywhere; the index block keeps track of their locations for direct access.

Line:

for block in data_blocks:
    disk[block] = allocated_to_file
    index_block_pointers.append(block)
process.state = 'terminated'

💡 Indexed allocation allows flexible block placement with fast access via the index block.

reconstruct

All Allocation Processes Completed

All three allocation methods have completed allocating the file blocks. The disk now shows allocated blocks for each method.

💡 This final step summarizes the allocation results for comparison and understanding.

Line:

return allocation_results

💡 Each allocation method has different block assignments and pointer structures, illustrating their trade-offs.

disk = ['free'] * 10  # STEP 1

# STEP 2
processes = ['Contiguous', 'Linked', 'Indexed']
states = {'Contiguous': 'ready', 'Linked': 'ready', 'Indexed': 'ready'}

# STEP 3
# Contiguous Allocation
start = 0
file_size = 4
if all(disk[i] == 'free' for i in range(start, start + file_size)):
    # STEP 4
    for i in range(start, start + file_size):
        disk[i] = 'allocated_contiguous'
    states['Contiguous'] = 'terminated'

# STEP 5
# Linked Allocation
states['Linked'] = 'running'
linked_blocks = []
for i in range(len(disk)):
    if disk[i] == 'free' and len(linked_blocks) < file_size:
        # STEP 6-8
        disk[i] = 'allocated_linked'
        linked_blocks.append(i)
if len(linked_blocks) == file_size:
    states['Linked'] = 'terminated'

# STEP 9
# Indexed Allocation
states['Indexed'] = 'running'
index_block = None
for i in range(len(disk)):
    if disk[i] == 'free':
        # STEP 10
        index_block = i
        disk[i] = 'index_block'
        break

data_blocks = []
for i in range(len(disk)):
    if disk[i] == 'free' and len(data_blocks) < file_size:
        # STEP 11
        disk[i] = 'allocated_indexed'
        data_blocks.append(i)
if len(data_blocks) == file_size:
    states['Indexed'] = 'terminated'

# STEP 12
allocation_results = {
    'Contiguous': list(range(start, start + file_size)),
    'Linked': linked_blocks,
    'Indexed': {'index_block': index_block, 'data_blocks': data_blocks}
}
return allocation_results

📊

File Allocation Methods - Contiguous, Linked, Indexed - Watch the Algorithm Execute, Step by Step

Watching the allocation process step-by-step reveals how each method manages disk space and file access differently, which is hard to grasp from code alone.

C

ready

L

ready

I

ready

Ready Queue

CLI

Waiting Queue

empty

🖥CPUidlet=0

Transition ready → running pid:C - start contiguous allocation

C

running

L

ready

I

ready

Ready Queue

LI

Waiting Queue

empty

🖥CPUCt=1

C

Transition running → running pid:C - check contiguous blocks 0-3

C

running

L

ready

I

ready

Ready Queue

LI

Waiting Queue

empty

🖥CPUCt=2

C

Transition running → terminated pid:C - allocated contiguous blocks 0-3

C

terminated

L

ready

I

ready

Ready Queue

LI

Waiting Queue

empty

🖥CPUCt=3

C

Transition ready → running pid:L - start linked allocation

C

terminated

L

running

I

ready

Ready Queue

I

Waiting Queue

empty

🖥CPULt=4

C

L

Transition running → running pid:L - allocate first free block 4

C

terminated

L

running

I

ready

Ready Queue

I

Waiting Queue

empty

🖥CPULt=5

C

L

Transition running → running pid:L - allocate and link block 5

C

terminated

L

running

I

ready

Ready Queue

I

Waiting Queue

empty

🖥CPULt=6

C

L

Transition running → terminated pid:L - allocated and linked blocks 6 and 7

C

terminated

L

terminated

I

ready

Ready Queue

I

Waiting Queue

empty

🖥CPULt=8

C

L

Transition ready → running pid:I - start indexed allocation

C

terminated

L

terminated

I

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUIt=9

C

L

I

Transition running → running pid:I - allocate index block 8

C

terminated

L

terminated

I

running

Ready Queue

empty

Waiting Queue

empty

🖥CPUIt=10

C

L

I

Transition running → terminated pid:I - allocated data blocks and updated index block

C

terminated

L

terminated

I

terminated

Ready Queue

empty

Waiting Queue

empty

🖥CPUIt=14

C

L

I

C

terminated

L

terminated

I

terminated

Ready Queue

empty

Waiting Queue

empty

🖥CPUidlet=14

C

L

I

Key Takeaways

✓ Contiguous allocation requires finding a continuous free block segment, which is simple but prone to fragmentation.

This is hard to see from code alone because the search and allocation happen in a loop without explicit visualization of block continuity.

✓ Linked allocation allows scattered blocks linked by pointers, providing flexibility but requiring pointer management.

The chain of pointers is difficult to visualize in code, but the step-by-step linking clarifies how blocks are connected.

✓ Indexed allocation uses a dedicated index block to store pointers to all data blocks, enabling direct access and flexible allocation.

Understanding the separation of index and data blocks is easier when seeing the allocation of the index block and data blocks distinctly.

Practice

1. In which scenario is Round Robin scheduling with a fixed time quantum most appropriate compared to First-Come-First-Serve or Priority scheduling?

easy

A. When processes have highly variable CPU burst times and fairness among all processes is required

B. When all processes have identical priorities and long CPU bursts

C. When minimizing average turnaround time is the only goal

D. When processes have strict deadlines and real-time constraints

Solution

1. Step 1: Understand Round Robin's fairness goal

   Round Robin scheduling is designed to allocate CPU time slices fairly among all processes, especially when burst times vary widely.

2. Step 2: Analyze other options

   When all processes have identical priorities and long CPU bursts is less suitable because identical priorities and long bursts favor FCFS or SJF for efficiency, not fairness. When minimizing average turnaround time is the only goal ignores fairness and focuses only on turnaround time, which RR does not optimize. When processes have strict deadlines and real-time constraints requires real-time guarantees, which RR cannot provide due to its time slicing.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   RR is best when fairness and responsiveness matter, especially with variable burst times.

Hint: RR = fairness with variable bursts

Common Mistakes:

• Assuming RR always minimizes turnaround time
• Believing RR suits real-time deadlines
• Confusing RR with priority-based scheduling

2. In which scenario is a Translation Lookaside Buffer (TLB) most beneficial for system performance?

easy

A. When the system uses a single-level page table with very few page faults

B. When virtual memory accesses exhibit high temporal locality of page references

C. When the system has a very small physical memory and no paging

D. When all memory accesses are sequential and predictable

Solution

1. Step 1: Understand TLB purpose

   The TLB caches recent virtual-to-physical address translations to speed up address translation.

2. Step 2: Analyze each option

   A: High temporal locality means repeated accesses to the same pages, so TLB hits are frequent, improving performance.
   B: Single-level page tables are fast, but TLB benefits more when page tables are large.
   C: Small physical memory with no paging reduces need for TLB since address translation is trivial.
   D: Sequential accesses may not reuse the same pages quickly, reducing TLB hit rate.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   TLB effectiveness depends on locality of reference, which is captured by when virtual memory accesses exhibit high temporal locality of page references.

Hint: TLB shines when recent translations are reused quickly [OK]

Common Mistakes:

• Assuming TLB is always beneficial regardless of access pattern
• Confusing physical memory size with TLB usefulness

3. Which of the following statements about memory compaction is INCORRECT?

medium

A. Compaction can be performed without halting all running processes

B. Compaction does not affect internal fragmentation

C. Compaction requires additional CPU overhead and may cause temporary performance degradation

D. Compaction reduces external fragmentation by relocating allocated memory blocks

Solution

1. Step 1: Understand compaction process

   Compaction moves allocated blocks to create contiguous free memory, reducing external fragmentation (A correct).

2. Step 2: Analyze process halting

   Compaction usually requires pausing processes to safely move memory (D incorrect).

3. Step 3: Consider overhead and fragmentation

   Compaction adds CPU overhead and can degrade performance temporarily (C correct); it does not affect internal fragmentation (B correct).

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Compaction generally requires halting processes [OK]

Hint: Compaction = pause + move blocks -> reduce external fragmentation [OK]

Common Mistakes:

• Assuming compaction is transparent to running processes
• Confusing internal and external fragmentation effects
• Underestimating compaction overhead

4. Why is it generally not advisable to use a counting semaphore as a mutex replacement for protecting a critical section?

medium

A. Because counting semaphores do not enforce ownership, leading to potential release by non-owner threads

B. Because counting semaphores have higher overhead due to maintaining a count variable

C. Because counting semaphores cannot block threads when the count is zero

D. Because counting semaphores allow only one thread at a time, making them equivalent to mutexes

Solution

1. Step 1: Understand mutex ownership

   Mutex enforces strict ownership; only the locking thread can unlock.

2. Step 2: Counting semaphore behavior

   Counting semaphores track resource count but do not enforce ownership.

3. Step 3: Consequences of no ownership

   Any thread can signal (release) the semaphore, risking synchronization errors.

4. Step 4: Why other options are incorrect

   B is true but not the main reason; C is false--semaphores do block; D is false--counting semaphores allow multiple threads.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Ownership enforcement is key difference; counting semaphores lack it.

Hint: Mutex ownership vs semaphore count: ownership prevents misuse.

Common Mistakes:

• Confusing blocking behavior of semaphores
• Assuming counting semaphore overhead is prohibitive
• Believing counting semaphore is equivalent to mutex

5. Suppose a disk scheduler uses C-SCAN but the disk head speed varies dynamically, sometimes moving faster or slower between tracks. How does this affect the fairness and average wait time guarantees of C-SCAN, and what modification could mitigate this issue?

hard

A. Variable head speed causes starvation in C-SCAN; switching to SSTF is the best mitigation.

B. Variable head speed does not affect C-SCAN fairness since it always services requests in one direction; no modification is needed.

C. Variable head speed improves average wait time by allowing faster servicing of distant requests; no modification is necessary.

D. Variable head speed breaks C-SCAN's uniform wait time guarantee; adding a dynamic priority queue based on estimated seek time can mitigate this.

Solution

1. Step 1: Understand C-SCAN fairness assumptions

   C-SCAN assumes uniform head movement speed to provide uniform wait times.

2. Step 2: Impact of variable head speed

   Variable speed causes some requests to wait longer, breaking fairness and uniform wait time guarantees.

3. Step 3: Mitigation strategies

   Introducing a dynamic priority queue that accounts for estimated seek time can help balance servicing order and restore fairness.

4. Step 4: Evaluate other options

   Variable head speed does not affect C-SCAN fairness since it always services requests in one direction; no modification is needed. ignores the impact of speed variation; Variable head speed causes starvation in C-SCAN; switching to SSTF is the best mitigation. incorrectly claims starvation occurs and suggests SSTF, which can worsen starvation; Variable head speed improves average wait time by allowing faster servicing of distant requests; no modification is necessary. incorrectly claims variable speed improves wait times.

5. Final Answer:

   Option D -> Option D

6. Quick Check:

   Variable head speed breaks C-SCAN's uniform wait time guarantee; adding a dynamic priority queue based on estimated seek time can mitigate this. correctly identifies the problem and a plausible mitigation.

Hint: C-SCAN fairness depends on constant head speed; variable speed needs dynamic adjustments

Common Mistakes:

• Assuming C-SCAN fairness is speed-independent
• Confusing starvation with fairness degradation
• Believing variable speed always improves performance