Discussion
Consider the following proposed solution for the critical section problem. There are \(n\) processes: \(P_{0} \ldots P_{n-1}\). In the code, function pmax returns an integer not smaller than any of its arguments. For all \(i\), t[i] is initialized to zero.
Code for \(P_{i}\):
do {
c[i]=1; t[i] = pmax(t[0],...,t[n-1])+1; c[i]=0;
for every j \(\ne\) i in {0,...,n-1} {
while (c[j]);
while (t[j] != 0 && t[j]\(\lt\)=t[i]);
}
Critical Section;
t[i]=0;
Remainder Section;
} while (true);
Which one of the following is TRUE about the above solution?
Answer: A
The true statement is At most one process can be in the critical section at any time.
This is a simplified bakery algorithm. A process picks a ticket larger than every current ticket, and before entering waits for each other process that is choosing a ticket (c[j]) and for each process holding a nonzero ticket no larger than its own. Two processes can never both pass the second wait for each other, because each would need the other's ticket to be zero or strictly larger. So mutual exclusion holds.
The other properties fail. Two processes can compute pmax at the same moment and get equal tickets. Then each sees t[j] equal to t[i], satisfies t[j] \(\lt\)= t[i], and waits for the other forever: a deadlock. That breaks deadlock-freedom and progress. The real bakery algorithm avoids this by breaking ties with process ids, which this version omits; with processes able to deadlock, bounded waiting is not guaranteed either.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development