💡 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.
Step 1/10
·Active fill★Answer cell
Transitionnew → ready pid:1 - Process initialized and ready
1
ready
Ready Queue
1
Waiting Queue
empty
🖥CPUidlet=0
Transitionready → running pid:1 - Process started execution
1
running
Ready Queue
empty
Waiting Queue
empty
🖥CPU1t=1
idle
Transitionrunning → running pid:1 - Working set updated with page 1
1
running
Ready Queue
empty
Waiting Queue
empty
🖥CPU1t=2
1
Transitionrunning → running pid:1 - Page fault on page 2, loaded into frame
1
running
Ready Queue
empty
Waiting Queue
empty
🖥CPU1t=3
1
Transitionrunning → running pid:1 - Working set updated with page 2
1
running
Ready Queue
empty
Waiting Queue
empty
🖥CPU1t=4
1
Transitionrunning → running pid:1 - Pages 3 and 4 loaded into frames
1
running
Ready Queue
empty
Waiting Queue
empty
🖥CPU1t=6
1
Transitionrunning → running pid:1 - Thrashing detected due to working set size > frames
1
running
Ready Queue
empty
Waiting Queue
empty
🖥CPU1t=7
1
Transitionrunning → waiting pid:1 - Process suspended to prevent thrashing
1
waiting
Ready Queue
empty
Waiting Queue
1 (memory frames)
🖥CPUidlet=8
1
Transitionwaiting → ready pid:1 - Process resumed with sufficient frames
1
ready
Ready Queue
1
Waiting Queue
empty
🖥CPUidlet=9
idle
Transitionready → 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/5)
1. Trace the sequence of checks the Banker's Algorithm performs when a process requests additional resources. Which step occurs immediately after verifying the request does not exceed the process's declared maximum need?
easy
A. The algorithm preempts resources from other processes to fulfill the request.
B. The algorithm immediately grants the request without further checks.
C. The algorithm simulates allocation and checks if the system remains in a safe state.
D. The algorithm checks if the requested resources are currently available in the system.
Solution
Step 1: Recall the Banker's Algorithm request sequence
First, it checks if the request is within the process's maximum declared need.
Step 2: Next step after need check
The algorithm then verifies if the requested resources are available in the system's current available pool.
Step 3: Subsequent steps
If available, it simulates allocation and checks for safe state, but this occurs after availability check.
Final Answer:
Option D -> Option D
Quick Check:
Availability check precedes simulation to avoid unnecessary computation.
Hint: Request ≤ Need -> check availability -> simulate safe state [OK]
Common Mistakes:
Assuming simulation happens before availability check
Believing requests are granted immediately after need check
Thinking preemption is part of Banker's Algorithm
2. Given a disk with pending requests at tracks 10, 22, 20, 2, and 40, and the disk head currently at track 15 moving towards higher track numbers, trace the order in which SCAN will service these requests.
easy
A. 22, 20, 10, 2, 40
B. 20, 22, 40, 2, 10
C. 20, 22, 40, 10, 2
D. 10, 20, 22, 40, 2
Solution
Step 1: Identify head direction and requests
Head at 15 moving up; requests: 2, 10, 20, 22, 40.
Step 2: SCAN moves towards higher tracks first
It services requests in ascending order from current position: 20, 22, 40.
Step 3: After reaching the highest request, SCAN reverses direction
Then it services remaining requests in descending order: 10, 2.
Final Answer:
Option C -> Option C
Quick Check:
20, 22, 40, 10, 2 correctly reflects SCAN's elevator movement servicing requests in one direction then reversing.
Hint: SCAN goes up servicing requests, then reverses down
Common Mistakes:
Assuming SCAN skips requests on the return trip
Mixing up order of requests on the return trip
Confusing SCAN with C-SCAN which only moves in one direction
3. In a Unix-like file system, which component is primarily responsible for mapping a file name to its data blocks on disk?
easy
A. The inode, which stores metadata and pointers to data blocks
B. The data block itself, which contains the file's content and its name
C. The superblock, which manages overall file system metadata
D. The directory entry, which contains the file name and a pointer to the inode
Solution
Step 1: Understand the role of directory entries in file name resolution
Directory entries map file names to inode numbers, acting as the bridge between human-readable names and inode metadata.
Step 2: Clarify inode responsibilities
Inodes store metadata and pointers to data blocks but do not contain file names.
Step 3: Differentiate superblock and data blocks
The superblock manages file system-wide metadata, not individual file mappings; data blocks store file content, not names.
4. In a multi-threaded system, which scenario best describes when starvation occurs?
easy
A. Two or more processes wait indefinitely for each other to release resources.
B. A low-priority process never gets CPU time because higher-priority processes keep running.
C. Processes continuously change states without making progress due to resource contention.
D. A process is blocked waiting for I/O to complete.
Solution
Step 1: Identify starvation characteristics
Starvation happens when a process is perpetually denied access to resources due to scheduling policies favoring others, typically higher-priority processes.
Step 2: Analyze each option
A low-priority process never gets CPU time because higher-priority processes keep running correctly describes starvation as a low-priority process being indefinitely postponed. Two or more processes wait indefinitely for each other to release resources describes deadlock, where processes wait on each other. Processes continuously change states without making progress due to resource contention describes livelock, where processes are active but not progressing. A process is blocked waiting for I/O to complete is normal blocking, not starvation.
Final Answer:
Option B -> Option B
Quick Check:
Starvation involves indefinite postponement due to priority, matching a low-priority process never getting CPU time because higher-priority processes keep running.
Hint: Starvation = low priority starved of CPU time
Common Mistakes:
Confusing starvation with deadlock
Thinking livelock is the same as starvation
5. Which of the following statements about Peterson's algorithm is INCORRECT?
medium
A. It can be extended straightforwardly to more than two processes
B. It guarantees mutual exclusion between two processes
C. It ensures progress and bounded waiting
D. It does not require special hardware instructions
Solution
Step 1: Verify correctness of each statement
Options A, C, and D are true properties of Peterson's algorithm.
Step 2: Identify incorrect statement
It can be extended straightforwardly to more than two processes is incorrect because Peterson's algorithm is specifically designed for two processes and does not extend easily to multiple processes.
Final Answer:
Option A -> Option A
Quick Check:
Peterson's algorithm is a two-process solution only.
Hint: Peterson's = two-process only, no hardware needed, guarantees progress
Common Mistakes:
Assuming easy extension to multiple processes
Confusing bounded waiting with starvation
Believing hardware instructions are required
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.