Got another one that I\'m struggling with, any assistance would be appreciated.
ID: 3883017 • Letter: G
Question
Got another one that I'm struggling with, any assistance would be appreciated.
(a) Given the following solution for the critical section problem for two processes (the code is for processes P1 and P2), show why it does not satisfy the mutual exclusion requirement. Here, unlock is a shared variable initialized to FALSE, and key is a local variable. The atomic operation is Swap. do { key = FALSE: unlock = TRUE: while (key = = FALSE) Swap(&unlock;, &key;): // Critical section unlock = FASLE: // Remainder section } (b) Suppose your friend implemented the instruction TestAndSet instruction in software instead of hardware. Explain its impact/effect to the critical section with the following solution? /* // critical section solution: */ do { while (TestAndSetLock (&lock;): // do nothing //critical section lock = FALSE: // reminder section } while (TRUE): /* // Code for TestAndSet: */ boolean TestAndSet (Boolean * target) { boolean rv = *target: *target = TRUE: return rv: }Explanation / Answer
When for process P1 lock is false it will enter into the loop.
while (TestAndSet(lock));
will call the TestAndSet(lock) method and will do nothing till it results true.
Lock value i.e., false is passed to target variable of TestAndSet method definition.
And will set it to true.
If during that period process P2 will execute the while (TestAndSet(lock));
Then, it will restrict it to enter into the critical section because the lock value is made true by the process P1. Because the statement while (TestAndSet(lock)); is if true do nothing.
do
{
key = true;
while(key == true)
swap(unlock, key);
//Critical Section
unlock = false;
//Remainder Section
}while(1);
Inside the infinite loop key for the process Pi is set to true.
Then while(key == true) results true.
Swap function is called with false and true value.
In swap function x will hold the value of unlock i.e., false and y will store the value of key i.e., true.
These are reference variables. So, whatever changes will be done in the function in variable x and y, will change the value of unlock and key.
Inside the function x will become true i.e., unlock becomes true and y becomes false i.e., key will become false.
Now while(key == true) becomes false. So, it will enter into the critical section.
If inside the loop we will make the, unlock to true, there is a change that more than one process will enter into the critical section.
Because it is the, unlock which prevents the other process to enter into the critical section when one process is execution its critical section.
void swap(Boolean &x, Boolean &y)
{
boolean t = x;
x = y;
y = t;
}
The instruction is executed atomically. Thus, if two TestAndSet instructions are executed simultaneously they will be executed sequentially in some arbitrary order.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.