Chapter 8 Flashcards
(28 cards)
Give three examples of deadlocks not related to computer systems.
Traffic intersection with cars from 4 directions entering simultaneously. Two people walking toward each other in narrow hallway both stepping same direction. Two ships in narrow canal approaching from opposite ends.
What is an unsafe state that could still complete without deadlock?
System where total resource demand exceeds available resources but current sequence of thread completions exists that avoids deadlock. Unsafe means potential for deadlock exists.
How do you determine if system is in safe state using banker’s algorithm?
Calculate Need matrix (Max - Allocation). Find thread that can complete with available resources. Simulate completion and repeat until all threads complete or no thread can proceed.
What happens when T1 requests (0,4,2,0) in banker’s algorithm?
Check if request ≤ Available resources. Temporarily grant request and test if resulting state is safe using safety algorithm. Grant only if safe state maintained.
How does containment compare to total ordering for deadlock prevention?
Containment: Single higher-order lock F must be acquired before any other locks A-E. Total ordering: All threads acquire locks in same predetermined order. Both prevent circular wait.
Why does safe-state detection require O(m*n²) operations?
For each of n threads check if it can complete (O(m) for resource comparison). May need to check all n threads up to n times in worst case. m resources × n² thread checks.
Can system detect thread starvation?
Yes - track how long each thread waits for resources. If wait time exceeds threshold thread is starving. Solution: aging or priority boosting for long-waiting threads.
Can deadlock occur with resource preemption policy described?
No deadlock cannot occur. Preemption breaks hold-and-wait condition. Resources taken from blocked threads and given to requesting threads preventing circular wait.
Can thread be blocked indefinitely with preemption policy?
Yes - thread can be repeatedly preempted by new requests never getting chance to complete. Solution needs fairness mechanism or aging.
Is deadlock possible with single-threaded process?
Yes if process can block on itself. Example: process sends message to itself and waits for reply. No other process to handle the message creating self-deadlock.
What creates deadlock in two-thread mutex example?
Thread1 locks first_mutex then waits for second_mutex. Thread2 locks second_mutex then waits for first_mutex. Creates circular wait dependency.
How does CPU scheduler contribute to mutex deadlock?
Scheduler determines when threads run. If Thread1 acquires first lock then gets preempted allowing Thread2 to acquire second lock deadlock occurs when threads resume.
How to identify deadlock in resource allocation graphs?
Look for cycles in graph. If cycle exists with single-instance resources deadlock exists. With multiple instances cycle necessary but not sufficient condition.
What is simple rule for dining philosophers with central chopsticks?
Allow philosopher to pick up chopstick only if total chopsticks in use < n-1 where n is number of philosophers. Ensures at least one philosopher can always get two chopsticks.
How to prevent bridge deadlock with semaphores?
Use mutex for bridge access and counter for direction. Allow cars in same direction to share bridge but block opposite direction until bridge empty. Prevents head-on collision.
What are four necessary conditions for deadlock?
Mutual exclusion: resources cannot be shared. Hold and wait: process holds resources while waiting for others. No preemption: resources cannot be forcibly taken. Circular wait: circular chain of waiting processes.
How does banker’s algorithm work?
Simulate resource allocation to see if safe state exists. Calculate remaining need for each process. Find process that can complete with available resources. Repeat until all complete or deadlock detected.
What is difference between safe and unsafe states?
Safe state: sequence exists where all processes can complete. Unsafe state: no such sequence exists potential for deadlock. Unsafe doesn’t guarantee deadlock but makes it possible.
How to calculate Need matrix in banker’s algorithm?
Need[i][j] = Max[i][j] - Allocation[i][j]. Represents remaining resources each process needs to complete execution.
What is deadlock detection vs prevention vs avoidance?
Detection: Allow deadlock then detect and recover. Prevention: Eliminate one of four necessary conditions. Avoidance: Dynamically examine resource allocation state (like banker’s algorithm).
How does resource allocation graph show deadlock?
Processes are circles resources are squares. Arrow from process to resource means request. Arrow from resource to process means allocation. Cycle indicates potential deadlock.
What is wait-for graph?
Simplified resource allocation graph showing only process dependencies. Process Pi waits for Pj. Cycle in wait-for graph indicates deadlock in single-instance resource systems.
How to recover from deadlock?
Process termination: abort all deadlocked processes or abort one at a time. Resource preemption: select victim preempt resources rollback process to safe state.
What factors determine victim selection for deadlock recovery?
Priority of process. How long process has been running and how much longer to completion. How many resources process has used. How many more resources needed.
