💡 Indirect blocks store pointers to data blocks, extending the inode's reach.
fill_cells
Assign data blocks via single indirect pointer
Data blocks 6 through 14 are assigned through the single indirect block, filling its pointers to these blocks.
💡 Single indirect blocks hold pointers to data blocks beyond direct pointers' capacity.
Line:for i in range(NUM_DIRECT_POINTERS, blocks_needed):
inode.single_indirect.pointers[i - NUM_DIRECT_POINTERS] = allocate_data_block()
💡 Indirect blocks allow the inode to reference many more data blocks efficiently.
fill_cells
Finalize inode metadata with total blocks
The inode's file size metadata is updated to reflect the total number of blocks assigned (15 blocks).
💡 Updating metadata ensures the file system knows the file's actual size.
Line:inode.file_size = blocks_needed * BLOCK_SIZE
💡 Metadata must be consistent with the block pointers assigned.
setup
Complete inode initialization
The inode initialization process completes, and the inode is ready with metadata and block pointers assigned.
💡 Completing initialization means the inode can now be used by the file system to access file data.
Line:return inode
💡 The inode is now fully prepared to represent the file on disk.
class Inode:
def __init__(self):
self.file_size = 0 # STEP 2
self.owner_uid = None # STEP 2
self.direct_blocks = [None] * 6 # STEP 3
self.single_indirect = None # STEP 7
self.double_indirect = None
self.triple_indirect = None
def initialize_metadata(self):
self.file_size = 0 # STEP 2
self.owner_uid = get_current_user_id() # STEP 2
def allocate_data_block():
# Returns a new data block number
pass
def allocate_indirect_block():
# Returns a new indirect block structure
return IndirectBlock()
class IndirectBlock:
def __init__(self):
self.pointers = [None] * 9 # example size
def create_inode_with_blocks(blocks_needed):
inode = Inode() # STEP 1
inode.initialize_metadata() # STEP 2
# Assign direct blocks
for i in range(6): # STEP 5
inode.direct_blocks[i] = allocate_data_block() # STEP 4 and 5
if blocks_needed > 6: # STEP 6
inode.single_indirect = allocate_indirect_block() # STEP 7
for i in range(6, blocks_needed): # STEP 8
inode.single_indirect.pointers[i - 6] = allocate_data_block()
inode.file_size = blocks_needed * 4096 # STEP 9
return inode # STEP 10
📊
Inode Structure - File Metadata & Block Pointers - Watch the Algorithm Execute, Step by Step
Watching this step-by-step helps you understand how file metadata and block pointers are organized and linked in an inode, which is fundamental for file system operations.
✓ Inodes store both file metadata and pointers to data blocks, enabling efficient file system access.
This insight is hard to see from code alone because the linkage between metadata and pointers is conceptual and structural.
✓ Direct pointers are used first for fast access, and indirect pointers extend the file size capacity by adding levels of indirection.
Visualizing pointer assignment order clarifies why indirect pointers exist and how they expand addressing.
✓ The decision to use indirect pointers depends on the file size exceeding direct pointer capacity, illustrating a key branching in inode design.
Seeing this decision step helps concretely understand when and why the inode structure changes.
Practice
(1/5)
1. When a timer interrupt triggers a context switch, what is the correct sequence of events that occur internally before the next process runs?
easy
A. Scheduler selects next process -> Save current CPU registers -> Load next process PCB registers -> Resume execution
B. Save current CPU registers to PCB -> Load next process PCB registers -> Scheduler selects next process -> Resume execution
C. Save current CPU registers to PCB -> Scheduler selects next process -> Load next process PCB registers -> Resume execution
D. Load next process PCB registers -> Save current CPU registers -> Scheduler selects next process -> Resume execution
Solution
Step 1: Save current process state
Before switching, CPU registers of the current process must be saved to its PCB.
Step 2: Scheduler decision
After saving, the scheduler selects the next process to run.
Step 3: Load next process state
The CPU registers of the selected process are loaded from its PCB.
Step 4: Resume execution
The CPU resumes execution with the new process context.
Final Answer:
Option C -> Option C
Quick Check:
Saving registers before scheduler decision and loading registers after is the correct order.
Hint: Save first, then schedule, then load -> context switch order [OK]
Common Mistakes:
Selecting next process before saving current registers
Loading next process registers before scheduler decision
Mixing order of save/load and scheduling
2. Trace the sequence of page faults when using the FIFO algorithm with 3 frames for the reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. How many page faults occur?
Hint: FIFO faults count equals number of unique pages plus evictions [OK]
Common Mistakes:
Counting hits as faults
Misordering evictions in FIFO
Forgetting to update frames after eviction
3. Which of the following statements about the five-state process model is INCORRECT?
medium
A. The New state represents a process that is being created but not yet ready to run
B. The Waiting state is used when a process is blocked for I/O completion
C. A process in the Terminated state can be moved back to Ready state if needed
D. The Running state means the process is currently executing on the CPU
Solution
Step 1: Review each statement
A, B, and D correctly describe standard process states. C incorrectly states that a Terminated process can return to Ready, which violates the model.
Step 2: Understand Terminated state
Terminated means process execution is complete; it cannot be restarted or moved back.
Final Answer:
Option C -> Option C
Quick Check:
Terminated processes cannot be revived in the five-state model [OK]
Hint: Terminated means final; no return to Ready [OK]
Common Mistakes:
Thinking Terminated processes can be restarted
Confusing Waiting with Ready state
Misunderstanding New state as Ready
4. If a system uses LRU page replacement but the reference string exhibits a cyclic pattern larger than the number of frames, what is the expected impact on page faults compared to FIFO?
hard
A. LRU will have fewer page faults because it always evicts the least recently used page
B. LRU will perform optimally and minimize page faults in cyclic patterns
C. LRU will have more page faults than FIFO because it keeps evicting pages that will be needed soon
D. LRU and FIFO will have similar page fault rates due to cyclic references exceeding frame count
Solution
Step 1: Understand cyclic reference pattern larger than frames
Pages are referenced in a cycle longer than available frames, causing repeated evictions.
Step 2: Analyze LRU vs FIFO behavior
Both algorithms will evict pages that will be needed soon because the working set exceeds frame count. LRU's advantage diminishes as no page stays long enough to be reused before eviction.
Step 3: Evaluate options
LRU will have fewer page faults because it always evicts the least recently used page is false; LRU advantage is lost in cyclic patterns larger than frames. LRU will perform optimally and minimize page faults in cyclic patterns is false; both have similar fault rates in this scenario. LRU will have more page faults than FIFO because it keeps evicting pages that will be needed soon is false; LRU does not necessarily have more faults than FIFO here. LRU and FIFO will have similar page fault rates due to cyclic references exceeding frame count is true; LRU and FIFO have similar fault rates due to cyclic references exceeding frame count.
Final Answer:
Option D -> Option D
Quick Check:
When working set > frames, LRU and FIFO fault rates converge.
Hint: LRU loses advantage when working set exceeds frames [OK]
Common Mistakes:
Assuming LRU always outperforms FIFO
Believing cyclic patterns favor LRU
Thinking LRU is optimal in all cases
5. If a system uses segmentation with paging (paged segmentation), what is a key challenge in address translation that differs from pure paging or pure segmentation?
hard
A. The need to first translate segment number to a page table, then translate page number to frame number
B. The inability to handle variable-sized segments due to fixed page sizes
C. The elimination of external fragmentation but increased internal fragmentation
D. The requirement that all segments must be the same size
Solution
Step 1: Understand paged segmentation
Address translation involves two steps: segment table lookup to get page table base, then page table lookup to get frame.
Step 2: Analyze The need to first translate segment number to a page table, then translate page number to frame number
This correctly describes the two-level translation process.
Step 3: Analyze The inability to handle variable-sized segments due to fixed page sizes
Variable-sized segments are handled by paging within segments; this option is incorrect.
Step 4: Analyze The elimination of external fragmentation but increased internal fragmentation
Fragmentation trade-offs are more complex; this option oversimplifies and is incorrect.
Step 5: Analyze The requirement that all segments must be the same size