Bird
Raised Fist0
Interview Prepoperating-systemshardGoogleAmazonSwiggyZepto

Thrashing - Working Set Model & Prevention

Choose your preparation mode3 modes available
▶
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.
📊
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
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/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

  1. Step 1: Recall the Banker's Algorithm request sequence

    First, it checks if the request is within the process's maximum declared need.
  2. Step 2: Next step after need check

    The algorithm then verifies if the requested resources are available in the system's current available pool.
  3. Step 3: Subsequent steps

    If available, it simulates allocation and checks for safe state, but this occurs after availability check.
  4. Final Answer:

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

  1. Step 1: Identify head direction and requests

    Head at 15 moving up; requests: 2, 10, 20, 22, 40.
  2. Step 2: SCAN moves towards higher tracks first

    It services requests in ascending order from current position: 20, 22, 40.
  3. Step 3: After reaching the highest request, SCAN reverses direction

    Then it services remaining requests in descending order: 10, 2.
  4. Final Answer:

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

  1. 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.
  2. Step 2: Clarify inode responsibilities

    Inodes store metadata and pointers to data blocks but do not contain file names.
  3. 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. Final Answer:

    Option D -> Option D
  5. Quick Check:

    Directory entries handle name-to-inode mapping [OK]
Hint: Directory entries map names -> inodes; inodes map data blocks
Common Mistakes:
  • Confusing inode as containing file names
  • Assuming data blocks store file names
  • Believing superblock handles file name mappings
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

  1. 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.
  2. 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.
  3. Final Answer:

    Option B -> Option B
  4. 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

  1. Step 1: Verify correctness of each statement

    Options A, C, and D are true properties of Peterson's algorithm.
  2. 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.
  3. Final Answer:

    Option A -> Option A
  4. 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 unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard