Concurrency, Synchronization & Deadlock — Practice

Question 1

Name the three requirements of a correct critical-section solution and state which one a solution admitting nobody satisfies.

Accepted Answer

Mutual exclusion, progress and bounded waiting. A solution admitting nobody satisfies mutual exclusion but violates progress.

Question 2

A counting semaphore is initialised to 3. After 5 wait operations and 1 signal, what is its value and how many threads are blocked?

Accepted Answer

The value is 3 minus 5 plus 1, which is negative 1, so one thread is blocked, since the magnitude of a negative value counts blocked threads.

Question 3

List the four necessary conditions for deadlock.

Accepted Answer

Mutual exclusion, hold and wait, no preemption, and circular wait, all holding simultaneously.

Question 4

Four processes each need a maximum of 3 units of one resource type. What is the smallest total that guarantees no deadlock?

Accepted Answer

Worst case has each holding 2 units, a total of 8, with all blocked. One more unit lets a process finish, so 4 times 2 plus 1, which is 9.

Question 5

Exhibit the deadlock when a bounded-buffer producer executes wait(mutex) before wait(empty).

Accepted Answer

With the buffer full, the producer acquires the mutex then blocks on empty. A consumer passes wait(full) but blocks on the mutex the producer holds. The producer waits for a slot only the consumer can free and the consumer waits for the mutex only the producer can release.

Question 6

Map each of the three dining-philosophers fixes onto the deadlock condition it denies.

Accepted Answer

Allowing at most four at the table prevents the circular wait from completing. Picking up both forks atomically denies hold and wait. Making one philosopher take the right fork first denies circular wait by breaking the symmetry of the ordering.

Question 7

Why does the naive readers-writers solution starve writers, and what does the standard fix cost?

Accepted Answer

A continuous stream of arriving readers keeps the reader count above zero, so a waiting writer never sees it reach zero. Writer preference blocks new readers once a writer waits, which fixes writer starvation but can starve readers instead; a fair queue in arrival order costs some read concurrency.

Question 8

Resources A, B, C total 10, 5, 7. Allocations are P0 (0,1,0), P1 (2,0,0), P2 (3,0,2), P3 (2,1,1), P4 (0,0,2) with maximums (7,5,3), (3,2,2), (9,0,2), (2,2,2), (4,3,3). Is the state safe?

Accepted Answer

Available is (3,3,2). Needs are (7,4,3), (1,2,2), (6,0,0), (0,1,1), (4,3,1). P1 fits, giving (5,3,2); P3 fits, giving (7,4,3); P4 fits, giving (7,4,5); P0 fits, giving (7,5,5); P2 fits. The state is safe with sequence P1, P3, P4, P0, P2.

Question 9

In that state, P1 requests (1,0,2). Apply the banker's algorithm and decide.

Accepted Answer

The request is within P1's need (1,2,2) and within available (3,3,2). Pretend granting gives available (2,3,0) with P1's need (0,2,0). P1 then fits and releases, giving (5,3,2), after which P3, P4, P0 and P2 all complete in turn. The state is safe, so the request is granted.

Question 10

Explain why a cycle in a resource allocation graph guarantees deadlock only with single-instance resources.

Accepted Answer

With one instance, an assignment edge names the unique holder, so every waiter in the cycle depends on another member and nobody outside can release the resource. With several instances, a waiter may be satisfied by an instance held by a process outside the cycle, which can finish and dissolve the cycle without any member acting.

Practice — Concurrency, Synchronization & Deadlock

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities