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.
💡 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.
Transitionrunning → running pid:I - allocate index block 8
C
terminated
L
terminated
I
running
Ready Queue
empty
Waiting Queue
empty
🖥CPUIt=10
C
L
I
Transitionrunning → 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/5)
1. Which component is primarily responsible for saving and restoring CPU registers during a context switch?
easy
A. The Interrupt Handler
B. The CPU scheduler
C. The Memory Management Unit (MMU)
D. The Process Control Block (PCB)
Solution
Step 1: Understand the role of PCB
The PCB stores the CPU register states and other process information needed to resume execution later.
Step 2: Differentiate from scheduler and interrupt handler
The scheduler decides which process runs next but does not save registers; the interrupt handler triggers context switches but does not save registers itself.
Step 3: MMU role
The MMU handles memory address translation, unrelated to register saving.
Final Answer:
Option D -> Option D
Quick Check:
PCB contains saved CPU state -> correct component for saving/restoring registers.
Hint: PCB = process snapshot including CPU registers [OK]
Common Mistakes:
Confusing scheduler with register saving
Assuming interrupt handler saves registers
Thinking MMU handles CPU state
2. Which of the following statements about the FIFO page replacement algorithm is INCORRECT?
medium
A. FIFO always evicts the least recently used page
B. FIFO can suffer from Belady's anomaly where increasing frames increases page faults
C. FIFO is simple to implement with a queue data structure
D. FIFO does not consider how frequently or recently a page was accessed
Solution
Step 1: Understand FIFO Eviction Policy
FIFO evicts the oldest loaded page, not the least recently used.
Step 2: Evaluate Each Option
FIFO can suffer from Belady's anomaly where increasing frames increases page faults is correct; Belady's anomaly can occur with FIFO. FIFO always evicts the least recently used page is incorrect; FIFO does not track recency of use. FIFO is simple to implement with a queue data structure is correct; FIFO uses a queue for eviction order. FIFO does not consider how frequently or recently a page was accessed is correct; FIFO ignores frequency and recency.
Final Answer:
Option A -> Option A
Quick Check:
FIFO evicts by arrival order, not usage recency.
Hint: FIFO evicts oldest loaded page, not least recently used [OK]
Common Mistakes:
Confusing FIFO with LRU eviction criteria
Assuming FIFO tracks page usage
Believing FIFO cannot have anomalies
3. 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
Step 1: Understand mutex ownership
Mutex enforces strict ownership; only the locking thread can unlock.
Step 2: Counting semaphore behavior
Counting semaphores track resource count but do not enforce ownership.
Step 3: Consequences of no ownership
Any thread can signal (release) the semaphore, risking synchronization errors.
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.
Final Answer:
Option A -> Option A
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
4. If the buffer size in a producer-consumer system is increased dynamically at runtime, which challenge arises that the classic semaphore-based solution does NOT handle well?
hard
A. Consumers must signal the 'empty' semaphore twice per consumed item
B. The 'empty' semaphore count must be adjusted atomically to reflect new buffer slots
C. Producers will never block because buffer is always large enough
D. Mutex locks become ineffective with dynamic buffer sizes
Semaphore 'empty' initialized once to buffer size; dynamic resizing breaks this assumption.
Step 2: Adjusting semaphore counts
When buffer grows, 'empty' semaphore must be incremented atomically to reflect new slots; otherwise, producers may block unnecessarily.
Step 3: Why other options are incorrect
Consumers must signal the 'empty' semaphore twice per consumed item is false; consumers do not signal 'empty' twice. Mutex locks become ineffective with dynamic buffer sizes is false; mutex still protects critical section regardless of size. Producers will never block because buffer is always large enough is false; producers can still block if buffer is full.
Assuming fixed semaphore counts suffice for dynamic buffers
Thinking mutex depends on buffer size
Misunderstanding producer blocking conditions
5. In a scenario where a mutex-protected resource must be accessed by multiple processes (not threads) across different machines, which synchronization primitive and approach is most appropriate, and why?
hard
A. Use a binary semaphore implemented via a distributed lock service to enforce mutual exclusion across processes
B. Use a distributed counting semaphore to limit concurrent access across machines
C. Use a local mutex on each machine, since mutexes enforce ownership and prevent race conditions
D. Use spinlocks on each machine to busy-wait until the resource is free