Please enable JavaScript.
Coggle requires JavaScript to display documents.
471 - part 2 - Coggle Diagram
471 - part 2
critical section problem
solutions to critical section problem
software level solutions
peterson's solution
assumptions:
load and store instructions are atomic
atomic
an instruction that cannot be interrupted
code for pi
flag[i]=true // tells pj that pi wants to enter its critical section
turn=j sets turn to enter cs to pj, if each process set its turn to itself, it would violate mutual exclusion
while(flag[j] && turn==j) this while will only succeed if another process wants to enter its cs and it is its turn the ; at the end means nothing will happen until the while is false, aka when pj is neither in its CS or is about to enter its CS, meaning its safe for pi to enter its CS
flag[i] = false indicates to pj that pi is no longer interested in entering its CS
code for pj
do
{
flag[j] = TRUE; // Pj wants to enter its CS //
turn = i // It is other process’s turn //
while (flag[i] && turn == i); // Checks if Pi wants to enter its CS and it is Pi’s turn, the ; at the end means nothing will happen until the while is false //
//critical section
flag[j] = FALSE; // Pj does not want to enter its CS //
}
while(TRUE); //: at end of while loop means nothing will happen when true
do
{
flag[i] = TRUE; // Pi wants to enter its CS //
turn = j; // It is other process’s turn //
while (flag[j] && turn == j); // Checks if Pj wants to enter its CS and it is Pj’s turn, the ; at the end means nothing will happen until the while is false //
//critical section
flag[i] = FALSE; // Pi does not want to enter its CS //
}
while(TRUE); //: at end of while loop means nothing will happen when true
mutual exclusion: if pi is in its cs, then flag[i] = true, if pj is executing its entry section, it will set turn to i, since flag[i] will not be set to false until pi is out of its critical section, pj has to wait
progress
if only pi wants to enter its cs, then it will set turn to j, but flag[j] will be false, allowing pi entry if both are executing entry simultaneously, turn will allow whichever process executes last to enter its cs
bounded waiting
if pi is in its cs, that means flag[i] = true, if pj wants to enter its cs, turn will = i, and flag[j] = true, and once the exit section of pi is executed, flag[i] will be false, allowing pj to enter its cs
drawbacks:
spinlock
keeps exeucting while loop, making it inefficient
it disables interrupts, meaning it can miss important events
semaphores
types
binary
aka
mutex
counting
drawbacks
possible deadlock
possible starvation
an integer variable that, once initialized, is only accessed throught two atomic operations: wait() and signal(), each semaphore is associated with a queue of waiting processes
wait()
decrement, block until semaphore is open
when called by process/thread, if semaphore is open, the process/thread is allowed to continue, if semaphore is closed, the thread/process is blocked in the queue
signal()
increment, allows another thread to enter
opens the semaphore, if a thread/process is waiting in queue, it is unblocked, if none are waiting, the signal is remembered for the next thread
monitors
mutexes
advantages:
block waiters
dont disable interrupts inside the CS
condition variables
entry and exit section
exit section
code where process obtains permission to access critical section
flag[i] = FALSE; // Pi does not want to enter its CS //
}
while(TRUE);
entry section
code where process obtains permission to access critical section
do
{
flag[i] = TRUE; // Pi wants to enter its CS //
turn = j; // It is other process’s turn //
while (flag[j] && turn == j); // Checks if Pj wants to enter its CS and it is Pj’s turn //
hardware solutions
special instructions
TestAndSet
boolean TestAndSet (boolean *target){
boolean rv = *target;
*target = TRUE;
return rv;}
test memory word and set value
swap
void Swap (boolean *a, boolean *b){
boolean temp= *a;
*a= b;
*b = temp;}
swap contents of two memory words
all meet requirements of progress, mutual exclusion, and bounded waiting
critical section
area of code that may be changing variables shared between processes
//critical section
three requirements to solve critical section problem
mutual exclusion
if a process Pi is executing its critical section, no other process can execute its critical sections involving the same shared variables
progress
if no process is executing its critical sections and a process has made a request to enter its critical section, a process must be selected to enter its critical section next at some point
bounded waiting
after a process has made a request to enter its critical section, before that request is granted, the number of times that other processes are allowed to enter their critical sections is limited
definition
the critical section problem is to design a protocol that processes can use to cooperate
the three classic problems of synchronization
bounded-buffer problem
a set of resource buffers are shared by producer and consumer threads, if they insert and remove resources at the same time or at different rates, the number of items in the buffer can be wrong
producer thread
inserts resources into the buffer set
consumer thread
removes resources from the buffer set
aka
producer-consumer problem
readers-writers problem
data set is shared among a number of concurrent reader and writer processes, a system must be created where readers cant access shared set when writers are accessing it, only one writer can access the shared data at a time, and multiple readers can access the shared data at the same time
reader processes
can only read the data set, cant insert/remove items
writer processes
can insert or remove items from the data set
dining philosophers problem
important difference between machine-level instructions and source-language level instructions
machine level instructions are atomic or uninterruptable
source-language instructions are interruptible