Problem 5: Describe how the compare_and_swap() instruction can be used to provid
ID: 3705115 • Letter: P
Question
Problem 5: Describe how the compare_and_swap() instruction can be used to provide mutual exclusion that satisfies the bounded-waiting requirement. Consider how to implement a mutex lock using an atomic hardware instruction. Assume that the following structure defining the mutex lock is available: a) b) typedef struct int available; lock; where (available0) indicates the lock is available; a value of 1 indicates the lock is unavailable. Using this struct, illustrate how the following functions may be implemented using the test_and_set() and compare_and_swap() instructions void acquire(lock *mutex) void release(lock *mutex) Be sure to include any initialization that may be necessary. c) Show how to implement the wait() and signal() semaphore operations in multiprocessor environments using test and set() waiting. instruction. The solution should exhibit minimal busyExplanation / Answer
1. Bounded waiting problem is a critical section problem.Each process has a critical section code segment.When a process is in execution of its critical section no other process can be in its critical section.Mutuaal exclusion,progress,bounded waiting are solutions to the critical section probelm.In bounded waiting, a bound is set for the number of times taht the other processes have to enter their critical sections after a process has made a request to enter its critical section and before that the request is granted.Mutual exclusion says that if a process is executing its critical section no other process has to be in its critical section.In compare and swap method it execute atomically.This method will return the original value of passed parameter "value".Definition is like this,
int comapre_and_swap(int *value,int expected,int new_value)
{
int temp = *value;
int(*value==expected)
*value = new_value;
return temp;
}
In this code ,only if value is equal to expected then set variable value the value of passed parameter new_value .swap is take place under this condition.
set shared integer lock is initialized as 0.then solution will be,
do
{
while(compare_and_swap(&lock,0,1)!=0); /*do nothing*
/*critical section*/
lock = 0;
/*remainder section*/
}while(true);
In bounded buffer problem,the struction of producer process is,
do
{
/*produce an item in next*/
.......................................
wait(empty);
wait(mutex);
/*add next produced to buffer*/
................................................
signal(mutex);
signal(full);
}while(true);
structure of consumer process is,
do
{
wait(full);
wait(mutex);
/*remove an item from buffer*/
..............................
signal(mutex);
signal(empty);
/*consume an item in next*/
}while(true);
compare and swap problem can used to provide mutual exclusion that satisfies bounded waiting requirement.
2. Hardware solutions are available to solve critical section problem.The basic idea is locking that means protecting critical regions using locks.Modern machines provide atomic hardware solutions.Atomic means non interruptable .It either test memory word and set value or swap contents of two memory words.These are the two solutions for critical section problem using hardware.
do
{
acquire lock
critical section
release lock
remainder section
}while(true);
In test and set method,
boolean test_and_set(boolean *target)
{
boolean rv = *target;
*target = TRUE;
return rv;
}
This will exectued atomically and returns teh original value of passed parametr.Here set new value of passed parameter to TRUE.
shared boolean variable lock, initized to FALSE.the solution will be
do
{
while(test_and_set(&lock));
/*do nothing*/
/*critical section*/
lock = false;
/*remainder section*/
}while(true);
Mutex locks are used as software solutions for critical section problem.Protect critical section by first acquire() a lock tehn release() the lock.The boolean variable is indicate if the lock is available or not.Calls to aquire and release methods are must be atomic.
acquire()
{
while(!avialble); /* busy wait*/
available = false;
}
release()
{
available = true;
}
do
{
acquire lock
critical section
release lock
remainder section
}while(true);
c. semaphore is a synchronization tool taht provides more ways to synchronize processes activities.Semaphore is an integer variable.BAsic operations are wait() and signal() it also called by P() and V().
wait(s)
{
while(s<=0);
//busy wait
s--;
}
signal(s)
{
s++;
}
With each semaphore there is an associated waiting queue.Each entry in a waiting queue has two data items vale and pointer.value is a type of integer and ponitet is pointing to next record in the list.Two operations are block and wakeup.Block will place the process invoking the operation on teh appropriate waiting queue.Wakeup will remove one of the processes in the waiting queue and place it in the ready queue.
typedef struct
{
int value;
struct process *list;
}semaphore;
wait(semaphore *s)
{
s->value--;
if(s->value<0)
add this process to s->list;
block();
}
}
signal(semaphore *s)
{
s->value++;
if(s->value<=0)
{
remove a process p from s->list;
wakeup(p);
}
}
}
Implementation using no busy waiting is