Question 1

Which of the following concurrency control protocols ensure both conflict serializability and freedom from deadlock?
I. 2-phase locking
II. Time-stamp ordering

Accepted Answer

II only. Time-stamp ordering guarantees conflict serializability by assigning timestamps to transactions, ensuring that they are executed in a consistent order, while also preventing deadlocks by not allowing transactions to wait for each other. In contrast, 2-phase locking can lead to deadlocks despite ensuring serializability.

Question 2

Consider the methods used by processes P1 and P2 for accessing their critical sections whenever needed, as given below. The initial values of shared boolean variables S1 and S2 are randomly assigned.

Method used by P1
while (S1 == S2);
Critical Section
S1 = S2;

Method used by P2
while (S

Accepted Answer

Mutual exclusion but not progress. The methods used by P1 and P2 ensure that only one process can enter its critical section at a time, achieving mutual exclusion. However, if both processes are waiting for the other to leave its critical section, they can end up in a deadlock situation, which means progress is not guaranteed.

Question 3

A system uses FIFO policy for page replacement. It has 4 page frames with no pages loaded to begin with. The system first accesses 100 distinct pages in some order and then accesses the same 100 pages but now in the reverse order. How many page faults will occur?

Accepted Answer

196. In a FIFO page replacement policy with 4 frames, the first 4 distinct pages accessed will cause page faults, totaling 4. As the system accesses the next 96 distinct pages, each will also cause a page fault until the frames are filled. When accessing the same pages in reverse order, the first 4 will cause faults again, leading to a total of 196 page faults.

GATE Technical: CS questions with solutions

Questions