crtical - section problem Flashcards
(18 cards)
what does concurrent access to shared data lead to
data inconsistency
what does maintaining data consist of
mechanisms to ensure orderly execution of coperating process
Finite buffer shared by producer and consumer , what problems does this lead to
Classic Problem: Finite buffer shared by producer and consumer
Producer produces a stream of items and puts them into
buffer
Consumer takes out stream of items
Have to deal with producers waiting for consumers when buffer is
full, and consumers waiting for producers when buffer is empty
write code for producer in buffer
while (true) {
/* produce an item and put in nextProduced */
while (count == BUFFER_SIZE); // wait if buffer full
buffer [in] = nextProduced; // store new item
in = (in + 1) % BUFFER_SIZE; // increment IN pointer.
count++; // Increment counter
}
write code for consumer in buffer
while (true) {
while (count == 0) ; // do nothing
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
count–;
/* consume the item in nextConsumed */
}
how can count++ be compile as
could be compiled as a sequence of CPU
instructions
register1 = count
register1 = register1 + 1
count = register1
what else can count– be compiled as
could be compiled as a sequence of CPU
instructions:
register2 = count
register2 = register2 - 1
count = register2
what problem could occur when count++ and count– (producer and consumer) are executed at the same time
race condition
what is the solution criteria to critical section problem
Solution to protect against concurrent modification of data in the critical section with the following criteri
mutual exclusion
progress
bounded waiting
what is mutual exclusion
if process Pi is in its critical section
(i.e. where shared variables could be altered inconsistently),
then no other processes can be in this critical section
what is progress
no process outside of the critical section (i.e. in the
remainder section) should block a process waiting to enter.
what is bounded waiting
Bounded Waiting - A bound must exist on the number of
times that other processes are allowed to enter the critical
section after a process has made a request to enter its critical
section and before that request is granted (i.e. it must be fair,
so one poor process is not always waiting behind the others
what are the assumptions to the solution Criteria to Critical-Section Problem
Assume that each process executes at a nonzero speed.
No assumption concerning relative speed of the N processes
what is the peterson’s solution
Two process solution.
Assume that the CPU’s register LOAD and STORE
instructions are atomic (not realistic on modern CPUs,
educational example).
The two processes share two variables:
int turn;
Boolean wants in[2];
The variable turn indicates whose turn it is to enter the
critical section.
The wants in array is used to indicate if a process is ready to
enter the critical section. wants in[i] = true implies that
process Pi is ready
what does the variable turn show in peterson’s solution
The variable turn indicates whose turn it is to enter the
critical section
variable wants_in in peterson’s solution
The wants in array is used to indicate if a process is ready to
enter the critical section. wants in[i] = true implies that
process Pi is ready
peterson’s algorithm for process P_I
do {
wants_in[i] = TRUE; // I want access…
turn = j; // but, please, you go first
while (wants_in[j] && turn == j); // if you are waiting and it is
// your turn, I will wait.
[critical section]
wants_in[i] = FALSE; // I no longer want access.
[remainder section]
} while (TRUE);
how does the peterson algorithm acheive fairness
When both processes are interested, they achieve fairness through
the turn variable, which causes their access to alternate
