Bird
Raised Fist0
Interview Prepoperating-systemsmediumGoogleAmazonFlipkartSwiggy

Critical Section Problem - Requirements & Peterson's Solution

Choose your preparation mode3 modes available
▶
Steps
setup

Initialize shared variables

Both processes start with their flags set to False, indicating neither wants to enter the critical section. The turn variable is initialized to 0 arbitrarily.

💡 Initialization ensures no process is in or requesting the critical section at the start, setting a clean state for synchronization.
Line:flag = [False, False] turn = 0
💡 The flags and turn variables are the core shared state controlling access to the critical section.
📊
Critical Section Problem - Requirements & Peterson's Solution - Watch the Algorithm Execute, Step by Step
Watching the algorithm step-by-step reveals how mutual exclusion is enforced by simple shared variables and busy waiting, which is hard to grasp from code alone.
Step 1/13
·Active fill★Answer cell
0
ready
1
ready
Ready Queue
01
Waiting Queue
empty
🖥CPUidlet=0
Transition ready → running pid:0 - Process 0 starts entering critical section
0
running
1
ready
Ready Queue
1
Waiting Queue
empty
🖥CPU0t=1
Transition running → running pid:0 - Process 0 sets turn to 1
0
running
1
ready
Ready Queue
1
Waiting Queue
empty
🖥CPU0t=2
Transition running → running pid:0 - Process 0 passes busy wait condition
0
running
1
ready
Ready Queue
1
Waiting Queue
empty
🖥CPU0t=3
Transition running → running pid:0 - Process 0 executes critical section
0
running
1
ready
Ready Queue
1
Waiting Queue
empty
🖥CPU0t=4
Transition ready → running pid:1 - Process 1 starts entering critical section
0
running
1
running
Ready Queue
0
Waiting Queue
empty
🖥CPU1t=5
0
Transition running → running pid:1 - Process 1 sets turn to 0
0
running
1
running
Ready Queue
0
Waiting Queue
empty
🖥CPU1t=6
0
Transition running → waiting pid:1 - Process 1 busy waits
0
running
1
waiting
Ready Queue
empty
Waiting Queue
1 (flag[0] == False or turn != 0)
🖥CPU0t=7
0
Transition running → ready pid:0 - Process 0 leaves critical section
0
ready
1
waiting
Ready Queue
0
Waiting Queue
1 (flag[0] == False or turn != 0)
🖥CPU0t=8
0
Transition waiting → running pid:1 - Process 1 exits busy wait
0
ready
1
running
Ready Queue
0
Waiting Queue
empty
🖥CPU1t=9
0
Transition running → running pid:1 - Process 1 executes critical section
0
ready
1
running
Ready Queue
0
Waiting Queue
empty
🖥CPU1t=10
0
Transition running → ready pid:1 - Process 1 leaves critical section
0
ready
1
ready
Ready Queue
01
Waiting Queue
empty
🖥CPU1t=11
0
1
0
ready
1
ready
Ready Queue
01
Waiting Queue
empty
🖥CPUidlet=12
0
1

Key Takeaways

✓ Peterson's algorithm uses two shared variables (flags and turn) to enforce mutual exclusion without hardware support.

This insight is hard to see from code alone because the interplay of flags and turn is subtle and timing-dependent.

✓ The busy wait loop blocks a process only if the other process wants to enter and has priority, ensuring fairness and preventing deadlock.

Seeing the busy wait condition evaluated step-by-step clarifies how the algorithm avoids simultaneous critical section entry.

✓ Resetting the flag after leaving the critical section signals other processes to proceed, enabling progress and bounded waiting.

The importance of resetting flags is often overlooked in code but is critical for correct synchronization.

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. In which scenario is the SSTF (Shortest Seek Time First) disk scheduling algorithm most appropriate compared to SCAN or C-SCAN?
easy
A. When minimizing average seek time is the highest priority and starvation is acceptable
B. When fairness and avoiding starvation are more important than minimizing seek time
C. When the disk requests are uniformly distributed and the workload is heavy
D. When the disk head movement must always proceed in one direction only

Solution

  1. Step 1: Understand SSTF's goal

    SSTF selects the closest request to the current head position to minimize seek time.
  2. Step 2: Consider starvation risk

    SSTF can cause starvation for requests far from the current head position because it always picks the nearest request.
  3. Step 3: Compare with SCAN and C-SCAN

    SCAN and C-SCAN move the head in a fixed direction to provide fairness and avoid starvation, sacrificing some seek time efficiency.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    When minimizing average seek time is the highest priority and starvation is acceptable correctly identifies SSTF's strength and its tradeoff with starvation risk.
Hint: SSTF = fastest seek but can starve distant requests
Common Mistakes:
  • Assuming SSTF always avoids starvation
  • Believing SCAN/C-SCAN minimize seek time better than SSTF
  • Confusing uniform distribution with SSTF suitability
3. Which of the following statements about the five-state process model is INCORRECT?
medium
A. The New state represents a process that is being created but not yet ready to run
B. The Waiting state is used when a process is blocked for I/O completion
C. A process in the Terminated state can be moved back to Ready state if needed
D. The Running state means the process is currently executing on the CPU

Solution

  1. Step 1: Review each statement

    A, B, and D correctly describe standard process states.
    C incorrectly states that a Terminated process can return to Ready, which violates the model.
  2. Step 2: Understand Terminated state

    Terminated means process execution is complete; it cannot be restarted or moved back.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Terminated processes cannot be revived in the five-state model [OK]
Hint: Terminated means final; no return to Ready [OK]
Common Mistakes:
  • Thinking Terminated processes can be restarted
  • Confusing Waiting with Ready state
  • Misunderstanding New state as Ready
4. Why is it generally not advisable to use a counting semaphore as a mutex replacement for protecting a critical section?
medium
A. Because counting semaphores do not enforce ownership, leading to potential release by non-owner threads
B. Because counting semaphores have higher overhead due to maintaining a count variable
C. Because counting semaphores cannot block threads when the count is zero
D. Because counting semaphores allow only one thread at a time, making them equivalent to mutexes

Solution

  1. Step 1: Understand mutex ownership

    Mutex enforces strict ownership; only the locking thread can unlock.
  2. Step 2: Counting semaphore behavior

    Counting semaphores track resource count but do not enforce ownership.
  3. Step 3: Consequences of no ownership

    Any thread can signal (release) the semaphore, risking synchronization errors.
  4. Step 4: Why other options are incorrect

    B is true but not the main reason; C is false--semaphores do block; D is false--counting semaphores allow multiple threads.
  5. Final Answer:

    Option A -> Option A
  6. Quick Check:

    Ownership enforcement is key difference; counting semaphores lack it.
Hint: Mutex ownership vs semaphore count: ownership prevents misuse.
Common Mistakes:
  • Confusing blocking behavior of semaphores
  • Assuming counting semaphore overhead is prohibitive
  • Believing counting semaphore is equivalent to mutex
5. Suppose a file system uses indexed allocation with a single-level index block. What happens when a file grows beyond the capacity of the index block, and how can this limitation be addressed?
hard
A. The file cannot grow further; to support larger files, multi-level or combined index schemes must be used
B. The file system automatically converts the file to contiguous allocation to accommodate growth
C. The index block dynamically expands by linking to additional index blocks without performance penalty
D. The file system switches to linked allocation for that file to handle the extra blocks

Solution

  1. Step 1: Understand single-level index block capacity

    A single-level index block can only hold pointers to a fixed number of blocks.
  2. Step 2: What if file grows beyond index block capacity?

    The single index block cannot hold more pointers, so the file cannot grow further under this scheme.
  3. Step 3: Analyze the file cannot grow further; to support larger files, multi-level or combined index schemes must be used

    Correct: multi-level or combined index schemes (e.g., multi-level indexing, inode structures) are used to support larger files.
  4. Step 4: Analyze the file system automatically converts the file to contiguous allocation to accommodate growth

    File systems do not convert allocation methods automatically; contiguous allocation is inflexible for growth.
  5. Step 5: Analyze the index block dynamically expands by linking to additional index blocks without performance penalty

    Index blocks do not dynamically expand by linking; multi-level indexing is a designed solution.
  6. Step 6: Analyze the file system switches to linked allocation for that file to handle the extra blocks

    File systems do not switch allocation methods on the fly; allocation method is fixed per file.
  7. Final Answer:

    Option A -> Option A
  8. Quick Check:

    Single-level index block limits file size; multi-level indexing needed for large files.
Hint: Single-level index block -> fixed max file size; multi-level indexing needed [OK]
Common Mistakes:
  • Believing index blocks can dynamically expand
  • Thinking allocation methods switch automatically
  • Assuming contiguous allocation can handle dynamic growth easily
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