Thrashing - Working Set Model & Prevention

▶

Steps

setup

Initialize Process and Memory Frames

The OS initializes the process with a fixed number of frames and sets the working set window size. The process is marked ready to run.

💡 Initialization sets the baseline for tracking pages and detecting thrashing.

Line:

process = Process(pid=1, frames=4)
working_set_window = 5
process.state = 'ready'

💡 The process starts with a fixed frame allocation and a working set window to monitor page usage.

traverse

Start Process Execution and Load First Page

The process starts running and references its first page, which is loaded into a free frame.

💡 Loading pages on demand is key to managing memory efficiently.

Line:

running_process = ready_queue.pop(0)
load_page(process, page=1)

💡 Page faults cause pages to be loaded, affecting the working set.

fill_cells

Update Working Set with Page 1

The working set window is updated to include page 1, marking it as recently used.

💡 Tracking recent pages helps detect thrashing by monitoring working set size.

Line:

working_set.add(page=1)

💡 The working set reflects pages actively used in the recent window.

compare

Process References Page 2 - Page Fault Occurs

The process references page 2, which is not in frames, causing a page fault and loading page 2.

💡 Page faults increase memory pressure and can lead to thrashing if frequent.

Line:

if page not in frames:
    load_page(page=2)

💡 Page faults cause working set to grow, potentially exceeding frame allocation.

fill_cells

Update Working Set with Page 2

Page 2 is added to the working set window, increasing the working set size.

💡 Working set size reflects current memory demand of the process.

Line:

working_set.add(page=2)

💡 Working set grows as new pages are referenced.

fill_cells

Process References Pages 3 and 4, Filling Frames

Pages 3 and 4 are referenced sequentially, each causing page faults and filling the remaining frames.

💡 Filling frames with working set pages is normal but can lead to thrashing if exceeded.

Line:

for page in [3,4]:
    if page not in frames:
        load_page(page)

💡 Working set now occupies all allocated frames.

compare

Process References Page 5 - Thrashing Detected

Referencing page 5 causes a page fault but no free frames remain, triggering thrashing detection.

💡 Thrashing occurs when working set size exceeds allocated frames, causing excessive page faults.

Line:

if working_set.size > frames:
    detect_thrashing()

💡 Thrashing detection triggers prevention mechanisms.

prune

Apply Thrashing Prevention by Reducing Multiprogramming

The OS reduces the degree of multiprogramming by suspending the process to free frames and prevent thrashing.

💡 Reducing multiprogramming frees frames to accommodate the working set.

Line:

if thrashing_detected:
    suspend_process(process)

💡 Suspending processes is a key thrashing prevention strategy.

expand

Frames Freed and Process Resumed

After freeing frames by suspending other processes, the suspended process is resumed with enough frames for its working set.

💡 Resuming processes with adequate frames prevents thrashing recurrence.

Line:

resume_process(process)
allocate_frames(process, working_set.size)

💡 Adjusting frame allocation based on working set size stabilizes performance.

traverse

Process Runs Smoothly Without Thrashing

The process runs with its working set fully in frames, avoiding page faults and thrashing.

💡 Stable execution occurs when working set fits in allocated frames.

Line:

run_process(process)

💡 Thrashing prevention ensures efficient memory usage and process performance.

class Process:
    def __init__(self, pid, frames):
        self.pid = pid
        self.frames = frames
        self.state = 'new'
        self.working_set = set()

# STEP 1: Initialize process
process = Process(pid=1, frames=4)  # STEP 1
working_set_window = 5  # STEP 1
process.state = 'ready'  # STEP 1

# STEP 2: Start execution
ready_queue = [process.pid]
running_process = ready_queue.pop(0)  # STEP 2
process.state = 'running'  # STEP 2

# STEP 3: Load first page
page = 1
if page not in process.working_set:
    process.working_set.add(page)  # STEP 3

# STEP 4: Reference page 2
page = 2
if page not in process.working_set:
    process.working_set.add(page)  # STEP 5

# STEP 6: Reference pages 3 and 4
for page in [3,4]:
    if page not in process.working_set:
        process.working_set.add(page)  # STEP 6

# STEP 7: Reference page 5 triggers thrashing
page = 5
if page not in process.working_set:
    process.working_set.add(page)  # STEP 7
if len(process.working_set) > process.frames:
    thrashing_detected = True  # STEP 7

# STEP 8: Suspend process to prevent thrashing
if thrashing_detected:
    process.state = 'waiting'  # STEP 8

# STEP 9: Resume process with adjusted frames
process.frames = len(process.working_set)  # STEP 9
process.state = 'ready'  # STEP 9
ready_queue.append(process.pid)  # STEP 9

# STEP 10: Process runs smoothly
running_process = ready_queue.pop(0)  # STEP 10
process.state = 'running'  # STEP 10

📊

Thrashing - Working Set Model & Prevention - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how the working set model dynamically manages memory to prevent thrashing, which is difficult to grasp from code alone.

Transition new → ready pid:1 - Process initialized and ready

1

ready

Ready Queue

1

Waiting Queue

empty

🖥CPUidlet=0

Transition ready → running pid:1 - Process started execution

1

running

Ready Queue

empty

Waiting Queue

empty

🖥CPU1t=1

idle

Transition running → running pid:1 - Working set updated with page 1

1

running

Ready Queue

empty

Waiting Queue

empty

🖥CPU1t=2

1

Transition running → running pid:1 - Page fault on page 2, loaded into frame

1

running

Ready Queue

empty

Waiting Queue

empty

🖥CPU1t=3

1

Transition running → running pid:1 - Working set updated with page 2

1

running

Ready Queue

empty

Waiting Queue

empty

🖥CPU1t=4

1

Transition running → running pid:1 - Pages 3 and 4 loaded into frames

1

running

Ready Queue

empty

Waiting Queue

empty

🖥CPU1t=6

1

Transition running → running pid:1 - Thrashing detected due to working set size > frames

1

running

Ready Queue

empty

Waiting Queue

empty

🖥CPU1t=7

1

Transition running → waiting pid:1 - Process suspended to prevent thrashing

1

waiting

Ready Queue

empty

Waiting Queue

1 (memory frames)

🖥CPUidlet=8

1

Transition waiting → ready pid:1 - Process resumed with sufficient frames

1

ready

Ready Queue

1

Waiting Queue

empty

🖥CPUidlet=9

idle

Transition ready → running pid:1 - Process resumed and running without thrashing

1

running

Ready Queue

empty

Waiting Queue

empty

🖥CPU1t=10

1

Key Takeaways

✓ The working set model dynamically tracks the set of pages a process actively uses to detect thrashing.

This dynamic tracking is hard to visualize from code alone but is clear when watching the working set update step-by-step.

✓ Thrashing is detected when the working set size exceeds the allocated frames, causing excessive page faults.

Understanding this threshold is easier when you see the working set size compared to frame allocation visually.

✓ Thrashing prevention involves suspending processes and adjusting frame allocation to match the working set size.

The decision to suspend and resume processes with adjusted frames is clearer when you observe the state transitions and queue changes.

Practice

1. In which scenario is the Banker's Algorithm most appropriately applied in an operating system?

easy

A. When the system needs to detect deadlocks after they occur by analyzing resource allocation graphs.

B. When the system schedules processes based on priority without considering resource constraints.

C. When the system must avoid deadlocks by preemptively checking if resource allocation keeps the system in a safe state.

D. When the system uses a first-come, first-served approach to allocate resources without any safety checks.

Solution

1. Step 1: Understand the purpose of Banker's Algorithm

   The Banker's Algorithm is designed to avoid deadlocks by ensuring that resource allocation requests do not lead the system into an unsafe state.

2. Step 2: Analyze each option

   A describes deadlock detection, which is reactive, not proactive like Banker's Algorithm.
   B describes scheduling without resource safety checks, which is unrelated.
   C correctly identifies deadlock avoidance by simulating allocations to maintain safe states.
   D ignores resource safety and deadlock avoidance, focusing on naive allocation.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Banker's Algorithm is a deadlock avoidance method, not detection or naive scheduling.

Hint: Banker's Algorithm = proactive deadlock avoidance via safe state checks [OK]

Common Mistakes:

• Confusing deadlock detection with avoidance
• Assuming Banker's Algorithm schedules processes
• Believing it works without resource safety checks

2. Consider two processes P0 and P1 using Peterson's algorithm. If both processes simultaneously set their flags to true and set turn to the other process, what happens next in terms of entry to the critical section?

easy

A. Both processes enter the critical section simultaneously, causing a race condition

B. The process whose turn variable was set last enters the critical section first

C. One process waits while the other enters the critical section, ensuring mutual exclusion

D. Both processes wait indefinitely, causing a deadlock

Solution

1. Step 1: Understand Peterson's turn variable role

   When both processes set their flags and turn, the turn variable decides who waits.

2. Step 2: Mutual exclusion enforcement

   The process whose turn it is not will wait until the other finishes, ensuring only one enters the critical section.

3. Step 3: Deadlock and race condition avoidance

   Peterson's algorithm prevents both deadlock and simultaneous entry.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Mutual exclusion is guaranteed by the turn variable and flags.

Hint: Turn variable breaks ties, ensuring one process waits

Common Mistakes:

• Believing both can enter critical section simultaneously
• Thinking the last to set turn always goes first
• Assuming deadlock can occur here

3. Which trade-off is a key limitation of using a global waiter (arbitrator) to prevent deadlock in the Dining Philosophers problem?

medium

A. It simplifies resource allocation but introduces a single point of failure and potential bottleneck

B. It increases concurrency but risks livelock under high contention

C. It eliminates deadlock but can cause starvation due to unfair scheduling

D. It guarantees fairness but requires complex priority inheritance mechanisms

Solution

1. Step 1: Understand the global waiter approach

   A global waiter serializes fork acquisition requests to prevent circular wait.

2. Step 2: Analyze trade-offs

   This centralization simplifies deadlock prevention but creates a single point of failure and can bottleneck performance.

3. Step 3: Evaluate other options

   It increases concurrency but risks livelock under high contention is incorrect as concurrency is reduced; It eliminates deadlock but can cause starvation due to unfair scheduling is incorrect because starvation is not guaranteed; It guarantees fairness but requires complex priority inheritance mechanisms is incorrect as priority inheritance is unrelated here.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Centralized control trades deadlock prevention for potential bottleneck and failure risk.

Hint: Global waiter = deadlock-free but centralized bottleneck [OK]

Common Mistakes:

• Confusing starvation with deadlock prevention
• Assuming increased concurrency with global waiter
• Misattributing priority inheritance to this solution

4. Which of the following statements about linked file allocation is INCORRECT?

medium

A. Linked allocation eliminates external fragmentation by allowing non-contiguous storage

B. Linked allocation supports efficient direct access to any block in the file

C. Each file block contains a pointer to the next block in the chain

D. Linked allocation requires only the starting block address to access the entire file

Solution

1. Step 1: Recall linked allocation properties

   Linked allocation stores file blocks non-contiguously with pointers linking blocks sequentially.

2. Step 2: Analyze linked allocation eliminates external fragmentation by allowing non-contiguous storage

   Correct: linked allocation avoids external fragmentation by allowing scattered blocks.

3. Step 3: Analyze linked allocation supports efficient direct access to any block in the file

   Incorrect: linked allocation does not support efficient direct access; it requires sequential traversal.

4. Step 4: Analyze each file block contains a pointer to the next block in the chain

   Correct: each block contains a pointer to the next.

5. Step 5: Analyze linked allocation requires only the starting block address to access the entire file

   Correct: only the starting block address is needed to traverse the file.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   Linked allocation -> no efficient direct access, only sequential traversal.

Hint: Linked allocation -> sequential access only, no direct access [OK]

Common Mistakes:

• Assuming linked allocation supports direct access
• Confusing external fragmentation with internal fragmentation

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