Question

int compare_and_swap(int *value, int expected, int new_value) {
int temp = *value;
if ( *value == expected ) *value = new_value;
return temp;
}

Suppose that a machine has an atomic compare_and_swap() instruction that sets the value to new_value only if the expression ( *value == expected ) is true. Regardless, compare_and_swap() always returns the original value of the variable value.

Using the compare__and_swap() instruction, give a mutual-exclusion solution to the n-process critical section problem. Use only the shared variable lock.

int lock = 0; /* shared variable - initialized to 0 */
do {
/*Fill this section*/
} while ( true );

Please answer me. I'll give you a thumbs up!

Answer 1

int compare_and_swap(int *value, int expected, int new_value) {
    int temp = *value;
    if ( *value == expected ) 
        *value = new_value;
    return temp;
}

int lock=0; /* lock is a shared variable - initialized to 0 */

do{
   //main logic that will forces mutual-exclusion amongst processes
   while (compare_and_swap(&lock, 0, 1) != 0) ;//it's a trap!!
   
   /* This is our critical section area in which a process will access or modify a shared resource*/
   
   /* now after a process completes its task in critical section then it will make the value of shared variable lock as 0 so that other process can go into 
      critical section */
   
   lock = 0;
   /* remainder code */
}
while (true);

Code Explainations:

As we know that a critical section is that area of our code in which we access or modify the shared resources.

So a critical section must be implemented in such a way that it should support the mutual-exclusion machenism

Now we can implement the critical section in either or two way : one is using Software Solution and other is by using Hardware Solution.

We can implement critical section using Peterson's Solution as a software solution or can use Semaphores to implement it.

We can implement Hardware Solution using compare_and_swap() instruction.

A compare_and_swap() instruction will be an atomic machine instruction.

Working of compare_and_swap() instruction:

Here we are mainly focused to achieve Mutual Exclusion to the n-processes means at a time only one process is allowed to enter into the critical section.

for that we have implemented the compare_and_swap() function which will simply swap the shared variable lock based on some criteria.

Here initially our lock is set to 0.

Let's say Process P1 wants to go into the critical section,so first it will have to call compare_and_swap() instruction just to make sure the mutual exclusion amongst the processes ensures.

Now as we called compare_and_swap(int *value,int expected,int new_value),

we have provided:

&lock--->*value,0---->expected,1---->new_value

now compare_and_swap() will work as follow:

1. temp will hold the value of lock.
2. we will check if the value of lock is equal to expected value or not if it is.then make assign the new_value to the value and finally return the temp.
3. but if it is not we just simply return the value of temp.

Here when the first process P1 has called compare_and_swap(int *value,int expected,int new_value),in while loop it return 0 as that time lock was set as 0.

now while loop condition become false and P1 enters into the critical section.

now let's assume that another process P2 wants to go in critical section by context-switching the P1,

so P2 also have to call compare_and_swap(int *value,int expected,int new_value), but this time compare_and_swap(int *value,int expected,int new_value), will return 1 as the value of lock was set 1 by P1.

So now P2 has to wait until P1 again make the lock as 0.

Once P1 completed it's execution it will make lock as 0 and now P2 can go into critical section by making the value of lock as 1 so that no other process can come in critical section while P2 doing it's taks there.

So we can see here for any number of processes say P1,P2,P3.....Pn are there at a time only one process is allowed to go into critical section.

All other processes has to perform busy-waiting.

So this solution will ensure us the Mutual-Exclution amongst n-processes.