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 Process Control Block (PCB) primarily used during the process state transitions in the five-state model?

easy

A. When a process moves from New to Ready state to store initial process information

B. When a process is terminated to delete all its data from memory

C. When a process is in the Ready state to execute instructions directly

D. When a process moves from Running to Waiting state to save CPU registers and state

Solution

1. Step 1: Understand the role of PCB during state transitions

   The PCB stores the process state, CPU registers, and scheduling information during context switches.

2. Step 2: Analyze each option

   A: PCB is created at process creation but its primary use is during context switches, not just at New to Ready.
   B: PCB is involved in termination but mainly to release resources; it is not primarily used to delete data.
   C: Processes in Ready state do not execute instructions directly; they wait for CPU allocation.
   D: Correct. When a process moves from Running to Waiting, the PCB saves CPU registers and state for resumption.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   PCB is essential for saving CPU state during Running to Waiting transitions [OK]

Hint: PCB saves CPU state during Running to Waiting transitions [OK]

Common Mistakes:

• Thinking PCB is only used at process creation
• Assuming Ready state processes execute instructions
• Believing PCB is deleted immediately at termination

2. You are designing a web server that must handle thousands of simultaneous client requests efficiently. Which approach is most suitable to maximize resource sharing and minimize overhead?

easy

A. Use multiple threads within a single process to handle client requests concurrently

B. Use multiple processes with shared memory segments for communication

C. Use a single-threaded process with blocking I/O for all requests

D. Use multiple processes, each handling a single client request independently

Solution

1. Step 1: Understand resource sharing in threads

   Threads within the same process share memory and resources, allowing efficient communication and lower overhead compared to processes.

2. Step 2: Compare overhead of context switching

   Thread context switching is lighter than process context switching, making threads better for high concurrency.

3. Step 3: Evaluate options

   Use multiple processes, each handling a single client request independently uses processes, which have higher overhead and less efficient resource sharing. Use a single-threaded process with blocking I/O for all requests is single-threaded and blocks, limiting concurrency. Use multiple processes with shared memory segments for communication adds complexity with shared memory and still has process overhead.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Threads maximize resource sharing and minimize overhead for concurrent tasks [OK]

Hint: Threads share memory; processes isolate resources [OK]

Common Mistakes:

• Assuming processes are always better for concurrency
• Ignoring context switching overhead differences
• Believing shared memory between processes is as simple as threads

3. Which of the following statements about the 'Mutual Exclusion' condition in deadlock is INCORRECT?

medium

A. Mutual exclusion means that at least one resource must be held in a non-shareable mode.

B. Mutual exclusion can be eliminated for all resources to prevent deadlock.

C. Mutual exclusion is necessary for deadlock but not sufficient alone.

D. Mutual exclusion applies only to resources that cannot be simultaneously used by multiple processes.

Solution

1. Step 1: Understand mutual exclusion

   It requires that some resources be non-shareable, meaning only one process can use them at a time.

2. Step 2: Analyze why eliminating mutual exclusion for all resources is impractical

   Eliminating mutual exclusion for all resources is impossible because some resources (like printers) inherently cannot be shared.

3. Step 3: Evaluate other options

   Mutual exclusion means that at least one resource must be held in a non-shareable mode correctly defines mutual exclusion. Mutual exclusion is necessary for deadlock but not sufficient alone correctly states it is necessary but not sufficient. Mutual exclusion applies only to resources that cannot be simultaneously used by multiple processes correctly limits mutual exclusion to non-shareable resources.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Mutual exclusion cannot be eliminated for all resources; some must be exclusive.

Hint: Mutual exclusion is about non-shareable resources, which can't all be made shareable [OK]

Common Mistakes:

• Thinking mutual exclusion can be removed entirely
• Confusing necessity with sufficiency
• Misapplying mutual exclusion to shareable resources

4. Which of the following statements about processes and threads is INCORRECT?

medium

A. Threads within the same process share the same memory space

B. Context switching between threads is more expensive than between processes

C. Processes have separate memory spaces and do not share resources by default

D. Threads can communicate more efficiently than processes due to shared memory

Solution

1. Step 1: Verify thread memory sharing

   Threads share memory within a process, so Threads within the same process share the same memory space is correct.

2. Step 2: Verify process isolation

   Processes have separate memory spaces, so Processes have separate memory spaces and do not share resources by default is correct.

3. Step 3: Compare context switching costs

   Thread context switching is lighter and faster than process switching, so Context switching between threads is more expensive than between processes is incorrect.

4. Step 4: Confirm communication efficiency

   Threads communicate efficiently via shared memory, so Threads can communicate more efficiently than processes due to shared memory is correct.

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   Thread context switches are cheaper than process context switches [OK]

Hint: Thread switches cheaper than process switches [OK]

Common Mistakes:

• Assuming process context switches are cheaper
• Confusing memory sharing between threads and processes
• Believing threads cannot communicate efficiently

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

1. Step 1: Understand cyclic reference pattern larger than frames

   Pages are referenced in a cycle longer than available frames, causing repeated evictions.

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

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

4. Final Answer:

   Option D -> Option D

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