Exams › GATE › Technical

Consider the procedure below for the Producer-Consumer problem which uses semaphores: semaphore $n = 0$; semaphore $s = 1$; void producer() { while(true) { produce(); semWait(s); addToBuffer(); semSignal(s); semSignal(n); } } void consumer() { while(true) { semWait(s); semWait(n); removeFromBuffer(); semSignal(s); consume(); } } Which one of the following is TRUE?

1. The producer will be able to add an item to the buffer, but the consumer can never consume it.
2. The consumer will remove no more than one item from the buffer.
3. Deadlock occurs if the consumer succeeds in acquiring semaphore s when the buffer is empty.
4. The starting value for the semaphore n must be 1 and not 0 for deadlock-free operation.

Correct answer: The producer will be able to add an item to the buffer, but the consumer can never consume it.

Solution

The consumer first acquires the mutex semaphore `s` and then waits on `n`. If `n=0`, the consumer blocks while still holding `s`, preventing the producer from entering the critical section to add an item. Thus the producer can add at most one item only if it gets the mutex first; otherwise the system can deadlock and the consumer cannot consume the item.

Related GATE Technical questions

• Which of the following statements about threads is/are TRUE?
• Which of the following process state transitions is/are NOT possible?
• Consider the following two threads T1 and T2 that update two shared variables a and b. Assume that initially a = b = 1. Though context switching between threads can happen at any time, each statement of T1 or T2 is executed atomically without interruption. T1: \[ a = a + 1;\] \[ b = b + 1;\] T2: \[ b = 2b;\] \[ a = 2a;\] Which one of the following options lists all the possible combinations of values of a and b after both T1 and T2 finish execution?
• Consider a demand paging memory management system with a 32-bit logical address, 20-bit physical address, and page size of 2048 bytes. Assuming that the memory is byte-addressable, what is the maximum number of entries in the page table?
• A computer has two processors, M1 and M2. Four processes P1, P2, P3, and P4 have CPU bursts of 20, 16, 25, and 10 milliseconds, respectively, and arrive at the same time. The scheduler uses non-preemptive priority scheduling, with priorities decided as follows: - M1 uses the priority order P1 > P3 > P2 > P4, i.e., P1 has the highest and P4 the lowest priority. - M2 uses the priority order P2 > P3 > P4 > P1, i.e., P2 has the highest and P1 the lowest priority. A process $P_i$ is scheduled to a processor $M_k$ if the processor is free and no other process $P_j$ is waiting with higher priority. At any given point in time, a process can be allocated to any one of the free processors without violating the execution priority rules. Ignore context-switch time. What will be the average waiting time of the processes in milliseconds?
• Group 1 contains some CPU scheduling algorithms and Group 2 contains some applications. Match entries in Group 1 to entries in Group 2. Group 1 P. Gang Scheduling Q. Rate Monotonic Scheduling R. Fair Share Scheduling Group 2 1. Guaranteed Scheduling 2. Real-time Scheduling 3. Thread Scheduling

⚔️ Practice GATE Technical free + battle 1v1 →