Bird
Raised Fist0
Interview Prepoperating-systemseasyAmazonTCSInfosysCognizant

File Allocation Methods - Contiguous, Linked, Indexed

Choose your preparation mode3 modes available
▶
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.
📊
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.
Step 1/12
·Active fill★Answer cell
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/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

  1. Step 1: Understand the role of PCB

    The PCB stores the CPU register states and other process information needed to resume execution later.
  2. 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.
  3. Step 3: MMU role

    The MMU handles memory address translation, unrelated to register saving.
  4. Final Answer:

    Option D -> Option D
  5. 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

  1. Step 1: Understand FIFO Eviction Policy

    FIFO evicts the oldest loaded page, not the least recently used.
  2. 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.
  3. Final Answer:

    Option A -> Option A
  4. 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

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

Solution

  1. Step 1: Classic solution assumes fixed buffer size

    Semaphore 'empty' initialized once to buffer size; dynamic resizing breaks this assumption.
  2. Step 2: Adjusting semaphore counts

    When buffer grows, 'empty' semaphore must be incremented atomically to reflect new slots; otherwise, producers may block unnecessarily.
  3. 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.
  4. Final Answer:

    Option B -> Option B
  5. Quick Check:

    Dynamic buffer size requires careful semaphore count updates [OK]
Hint: Dynamic buffer size requires dynamic semaphore adjustment
Common Mistakes:
  • 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

Solution

  1. Step 1: Identify cross-machine synchronization needs

    Local mutexes cannot synchronize across machines.
  2. Step 2: Evaluate distributed synchronization primitives

    Distributed lock services provide mutual exclusion across processes/machines.
  3. Step 3: Binary semaphore vs counting semaphore

    Binary semaphore (or mutex) semantics needed for mutual exclusion; counting semaphore allows multiple concurrent accesses, unsuitable if exclusive access required.
  4. Step 4: Spinlocks impractical across network due to busy-wait and latency

  5. Final Answer:

    Option A -> Option A
  6. Quick Check:

    Distributed binary semaphore or lock service enforces mutual exclusion across machines.
Hint: Distributed mutual exclusion requires distributed lock (binary semaphore), not local mutex or counting semaphore.
Common Mistakes:
  • Assuming local mutexes work across machines
  • Choosing counting semaphore for exclusive access
  • Using spinlocks in distributed environment
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard