Paging vs Segmentation - Address Translation

▶

Steps

setup

Initialize Segment Table and Page Table

The system initializes the segment table and page table with predefined entries for segment 1 and its pages.

💡 Setting up tables is essential because address translation depends on these mappings from virtual to physical memory.

Line:

segment_table = {1: {'base': 0x1000, 'limit': 0x2000, 'page_table': {0: 0x10, 1: 0x11}}}

💡 The segment table entry for segment 1 points to a base physical address and a page table mapping virtual pages to physical frames.

setup

Start Address Translation Process

The AddressTranslator process starts running to translate the virtual address Segment 1, Offset 0x1A3.

💡 Starting the process simulates the CPU beginning the translation operation.

Line:

running_process = address_translator

💡 The CPU is now actively performing the translation steps.

compare

Lookup Segment Table Entry

The process looks up segment 1 in the segment table to find its base address and page table.

💡 Segment table lookup is the first step in address translation to verify segment validity and get page table info.

Line:

segment_entry = segment_table.get(segment_number)

💡 The segment exists and has a base and page table, so translation can proceed.

compare

Check Offset Within Segment Limit

The process checks if the offset 0x1A3 is within the segment limit to ensure valid access.

💡 Validating the offset prevents illegal memory access outside the segment boundary.

Line:

if offset < segment_entry['limit']:

💡 The offset is valid, so translation can continue.

fill_cells

Calculate Virtual Page Number and Page Offset

The process calculates the virtual page number and offset within the page from the segment offset.

💡 Paging divides the segment offset into page number and offset to locate the physical frame.

Line:

page_number = offset // page_size
page_offset = offset % page_size

💡 The virtual address is split into page number and offset for page table lookup.

compare

Lookup Page Table Entry

The process looks up the page table entry for the calculated virtual page number to find the physical frame number.

💡 Page table lookup maps virtual pages to physical frames, completing the paging step.

Line:

frame_number = segment_entry['page_table'].get(page_number)

💡 The page exists and maps to a physical frame, so translation can continue.

insert

Calculate Physical Address

The process calculates the final physical address by combining the frame number and page offset.

💡 Combining frame number and offset gives the exact physical memory location.

Line:

physical_address = (frame_number * page_size) + page_offset

💡 Physical address is computed, completing the translation.

compare

Check for Page Fault

The process checks if the frame number is valid; if not, a page fault would occur.

💡 Page faults happen when the page is not in physical memory, requiring loading from disk.

Line:

if frame_number is None:

💡 No page fault means translation can complete successfully.

reconstruct

Return Physical Address

The process returns the calculated physical address as the result of the translation.

💡 Returning the physical address completes the translation process for the CPU.

Line:

return physical_address

💡 The virtual address is successfully translated to a physical address.

prune

Idle CPU After Completion

No processes remain to run, so the CPU is idle after completing the translation.

💡 The CPU idles when no active processes remain, marking the end of this translation task.

Line:

cpu_idle()

💡 The system is ready for the next task after translation finishes.

page_size = 0x1000  # 4KB pages
segment_table = {1: {'base': 0x1000, 'limit': 0x2000, 'page_table': {0: 0x10, 1: 0x11}}}  # STEP 1

def translate_address(segment_number, offset):  # STEP 2
    segment_entry = segment_table.get(segment_number)  # STEP 3
    if segment_entry is None:
        raise Exception('Segment not found')
    if offset >= segment_entry['limit']:  # STEP 4
        raise Exception('Offset out of segment limit')
    page_number = offset // page_size  # STEP 5
    page_offset = offset % page_size  # STEP 5
    frame_number = segment_entry['page_table'].get(page_number)  # STEP 6
    if frame_number is None:  # STEP 8
        raise Exception('Page fault')
    physical_address = (frame_number * page_size) + page_offset  # STEP 7
    return physical_address  # STEP 9

# Example call
physical_addr = translate_address(1, 0x1A3)  # STEP 2 start

📊

Paging vs Segmentation - Address Translation - Watch the Algorithm Execute, Step by Step

Watching each step of address translation helps you understand how virtual memory maps to physical memory, clarifying the roles of segments and pages without needing to read dense code.

Transition new → ready pid:1 - Initialization complete

1

ready

burst: 10

Ready Queue

1

Waiting Queue

empty

🖥CPUidlet=0

Transition ready → running pid:1 - Process scheduled

1

running

burst: 10

Ready Queue

empty

Waiting Queue

empty

🖥CPU1t=1

1

Transition running → running pid:1 - Segment table lookup

1

running

burst: 9

Ready Queue

empty

Waiting Queue

empty

🖥CPU1t=2

1

Transition running → running pid:1 - Offset validation

1

running

burst: 8

Ready Queue

empty

Waiting Queue

empty

🖥CPU1t=3

1

Transition running → running pid:1 - Calculate page number and offset

1

running

burst: 7

Ready Queue

empty

Waiting Queue

empty

🖥CPU1t=4

1

Transition running → running pid:1 - Page table lookup

1

running

burst: 6

Ready Queue

empty

Waiting Queue

empty

🖥CPU1t=5

1

Transition running → running pid:1 - Calculate physical address

1

running

burst: 5

Ready Queue

empty

Waiting Queue

empty

🖥CPU1t=6

1

Transition running → running pid:1 - Page fault check

1

running

burst: 4

Ready Queue

empty

Waiting Queue

empty

🖥CPU1t=7

1

Transition running → terminated pid:1 - Translation complete

1

terminated

burst: 0

Ready Queue

empty

Waiting Queue

empty

🖥CPUidlet=8

1

Transition terminated → idle - No active processes

Ready Queue

empty

Waiting Queue

empty

🖥CPUidlet=9

1

idle

Key Takeaways

✓ Address translation combines segmentation and paging by first validating the segment and then mapping pages within it.

This layered approach is hard to grasp from code alone but becomes clear when you see each lookup and calculation step.

✓ Offset validation against segment limit prevents illegal memory access, a critical safety check.

Visualizing this check shows why segmentation protects memory boundaries.

✓ Page faults are detected during page table lookup, showing when the system must load pages from disk.

Seeing the decision point for page faults clarifies how virtual memory handles missing pages.

Practice

1. In which scenario is the Dining Philosophers problem a suitable model to analyze system behavior?

easy

A. When processes communicate via message passing without shared resources

B. When multiple processes compete for multiple identical resources without any ordering

C. When a single process requires exclusive access to a single resource

D. When multiple processes compete for multiple shared resources arranged in a circular wait pattern

Solution

1. Step 1: Identify the resource allocation pattern

   The Dining Philosophers problem models processes (philosophers) competing for shared resources (forks) arranged in a circular manner, leading to potential circular wait and deadlock.

2. Step 2: Analyze each option

   When multiple processes compete for multiple shared resources arranged in a circular wait pattern correctly describes competition with a circular wait pattern, which is essential for the Dining Philosophers problem; When multiple processes compete for multiple identical resources without any ordering lacks the circular wait pattern; When a single process requires exclusive access to a single resource is a trivial single resource case; When processes communicate via message passing without shared resources involves no shared resources, so no deadlock from resource contention.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only When multiple processes compete for multiple shared resources arranged in a circular wait pattern captures the circular wait condition essential to the Dining Philosophers problem.

Hint: Dining Philosophers = circular wait over shared resources [OK]

Common Mistakes:

• Confusing any resource competition with circular wait
• Assuming single resource contention models the problem
• Ignoring the circular dependency aspect

2. Trace the sequence of process execution in preemptive SJF scheduling when the following processes arrive: P1(Arrival=0, Burst=8), P2(Arrival=1, Burst=4), P3(Arrival=2, Burst=2). Which process runs at time 3?

easy

A. P2

B. P1

C. P3

D. CPU is idle

Solution

1. Step 1: At time 0

   Only P1 has arrived, so P1 starts running.

2. Step 2: At time 1

   P2 arrives with burst 4, which is less than P1's remaining 7, so preemption occurs and P2 runs.

3. Step 3: At time 2

   P3 arrives with burst 2, less than P2's remaining 3, so preemption occurs and P3 runs.

4. Step 4: At time 3

   P3 has run 1 unit (remaining 1), P2 and P1 are waiting. Since P3 has the shortest remaining time, it continues running.

5. Final Answer:

   Option C -> Option C

6. Quick Check:

   At time 3, the shortest remaining burst is P3's 1 unit, so P3 runs.

Hint: At each arrival, pick the process with the shortest remaining burst [OK]

Common Mistakes:

• Not preempting when a shorter job arrives
• Assuming the first process continues until completion

3. Why does increasing the frequency of context switches beyond a certain point degrade overall system performance?

medium

A. Because saving and restoring CPU registers is a costly operation that consumes CPU cycles

B. Because the scheduler runs out of processes to schedule

C. Because the MMU has to reload page tables more frequently

D. Because the CPU cache is flushed automatically on every context switch

Solution

1. Step 1: Identify overhead of context switch

   Saving/restoring CPU registers and PCB updates consume CPU time, causing overhead.

2. Step 2: Scheduler availability

   The scheduler can always select processes; running out is not a cause of performance degradation.

3. Step 3: MMU and page tables

   MMU page table reloads happen on address space switches, but not necessarily on every context switch.

4. Step 4: CPU cache behavior

   CPU cache is not flushed automatically on every context switch; cache invalidation is more complex.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Context switch overhead is mainly CPU cycles spent saving/restoring registers.

Hint: More switches -> more register save/restore overhead -> slower system [OK]

Common Mistakes:

• Believing scheduler runs out of processes
• Assuming MMU reloads page tables every switch
• Thinking CPU cache flushes on every context switch

4. If a process requests resources that would keep the system in a safe state but the system is currently in an unsafe state, what does the Banker's Algorithm do and why?

hard

A. It denies the request because the system must always remain in a safe state, and starting from an unsafe state invalidates the algorithm's assumptions.

B. It restarts the system to reset resource allocations and ensure safety.

C. It preempts resources from other processes to restore a safe state before granting the request.

D. It grants the request because the immediate allocation is safe, ignoring the current unsafe state.

Solution

1. Step 1: Recall Banker's Algorithm assumptions

   The algorithm assumes the system starts in a safe state to guarantee deadlock avoidance.

2. Step 2: Analyze the scenario

   If the system is already unsafe, granting requests--even if individually safe--cannot guarantee overall safety.

3. Step 3: Evaluate options

   A ignores the unsafe starting state.
   B and C describe actions outside the algorithm's scope.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Banker's Algorithm cannot recover from unsafe states; it only avoids entering them.

Hint: Banker's Algorithm requires starting safe state to function correctly [OK]

Common Mistakes:

• Assuming safe requests can fix unsafe states
• Believing the algorithm preempts resources
• Thinking system restarts are part of the algorithm

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