How Does Test-and-Set Ensure Mutual Exclusion?

TL;DR

Test-and-set ensures mutual exclusion by atomically reading a shared Boolean lock and setting it to true, preventing pre-emption between those operations. A process receiving false enters the critical section, while a process receiving true remains in the while loop until the lock is released. The lock starts as false and is reset after the critical section.

Transcript

Dear students, welcome to Gate Smashers. In today's video I'm going to explain Test and Set instruction. So look, in process synchronization to resolve problem in critical section next method we use Test and Set instruction. So in the last video I told you about lock variable. So lock variable works fine, but what is the problem here? The problem I... Read More

Key Insights

• A separate lock check and assignment cannot guarantee mutual exclusion because pre-emption may occur between the two instructions. If one process checks a false lock but pauses before setting it, another process can also observe false and advance toward the same critical section.
• The root problem with the basic lock-variable approach is the gap between testing the lock and changing its value. Multiple processes can pass the test during that gap, later set the lock to the same value, and enter the critical section concurrently.
• Test-and-set is a special hardware instruction that combines testing a lock and setting it into one atomic instruction. Because those tasks cannot be separated by pre-emption, another process cannot observe the lock between the test and the update.
• The test-and-set function receives the lock address through call by reference. A pointer named target refers to the shared Boolean lock, allowing the function to inspect and modify the original lock rather than operate on an independent copied value.
• The return value of test-and-set is the lock value that existed before the instruction set the lock to true. The function stores the old value in a Boolean variable, updates the referenced target to true, and then returns the stored value.
• A false return value allows a process to enter the critical section. False means the lock was previously free, although the same atomic instruction has already changed it to true so that later processes cannot enter simultaneously.
• A true return value keeps a process inside the while loop. True indicates that another process already holds the lock, and the empty loop prevents the waiting process from reaching the critical section while that condition continues.
• The test-and-set approach satisfies mutual exclusion and progress as presented in the lesson. Mutual exclusion follows from the atomic lock operation, while progress means that when the critical section is empty, a process wanting to enter can do so without being stopped.

Questions & Answers

Q: Why does a basic lock variable fail to ensure mutual exclusion?

A basic lock variable fails because checking whether the lock is free and setting it to occupied are separate instructions. A process may observe that the lock equals zero and then be pre-empted before assigning one. Another process can also observe zero, assign one, and enter. When the first process resumes, it assigns one and enters too, so mutual exclusion is lost.

Q: How does test-and-set prevent the lock-variable race?

Test-and-set prevents the race by combining the lock test and the lock update into one atomic instruction. The operation reads the existing Boolean value, saves it, sets the referenced lock to true, and returns the saved value. Since pre-emption cannot occur between testing and setting, two processes cannot both pass through the vulnerable gap found in the basic lock-variable method.

Q: What does the test-and-set function return?

The test-and-set function returns the Boolean value held by the lock before the function changed it to true. It first copies the value referenced by the target pointer into a Boolean variable, then assigns true to the referenced target, and finally returns the copied value. Therefore, the return describes whether the lock was already occupied when the operation began.

Q: How does a process enter the critical section with test-and-set?

A process calls test-and-set with the address of a Boolean lock that is initially false. The operation saves false, sets the lock to true, and returns false. Because the returned value makes the while condition false, the process leaves the loop and enters the critical section. The lock is already true before entry, preventing another process from following it.

Q: What happens when a second process calls test-and-set?

When a second process calls test-and-set while the first process is in the critical section, the shared lock is already true. The function saves true, writes true to the lock again, and returns true. A true while condition keeps the second process trapped in the empty loop, so it cannot enter the critical section at the same time as the first process.

Q: Why is the lock passed by reference to test-and-set?

The lock is passed by reference so the test-and-set function can work with the original shared Boolean variable. The caller supplies the lock address, and the target pointer refers to that location. Reading through the pointer obtains the current lock value, while assigning through it changes the shared lock to true. This lets every process observe the same synchronization state.

Q: When is the lock reset after entering the critical section?

The lock is reset to false after the process completes its critical section. The presented structure places the test-and-set while loop before the critical section and the false assignment after it. Resetting the lock indicates that the critical section is empty again, allowing a waiting or newly arriving process to receive false from a later test-and-set call and proceed.

Q: Which synchronization requirements does test-and-set satisfy here?

The test-and-set method satisfies mutual exclusion and progress in the explanation. Mutual exclusion is achieved because testing and setting the lock form one atomic instruction, eliminating pre-emption between them. Progress is achieved because when the critical section is empty and the lock is false, a process that wants to enter receives false and can move directly into the critical section.

Summary & Key Takeaways

• A basic lock variable fails when checking the lock and setting it occur as separate instructions. A process can check that the lock is free and then be pre-empted before setting it. Another process can perform the same check, allowing both processes to enter the critical section and violating mutual exclusion.

• The test-and-set instruction combines checking the current lock value and setting the lock to true into one atomic operation. Its function saves the old Boolean value, changes the referenced lock to true, and returns the saved value. Atomic execution prevents pre-emption from separating the test and update steps.

• When the lock is initially false, the first process receives false from test-and-set, exits the while condition, and enters the critical section. A later process receives true and repeatedly executes the empty while loop. After the active process finishes, it sets the lock to false so another process can proceed.