Suppose a computer has atomic fetch and increment (FAI)instruction that also ret
ID: 3616456 • Letter: S
Question
Suppose a computer has atomic fetch and increment (FAI)instruction that also returns the new value of the variableafter the increment: int FAI (int &var) = < var = var+1; return var; > Using FAI, develop a pseudocode solution to the criticalsection problem for n processes. Don’t worry about the “eventual entry”property. Try to make your solution as cache efficient as possible (in the sense of minimisingcoherence traffic). Describe clearly how your solution works and why it is correct andefficient. [You can also assume atomic reads and writes and asequentially consistent model of shared memory. You should also assume that the program runswith an integer type which can store arbitrarily large positive or negativevalues. In other words, there is no issue about “wrapping around” wheninteger arithmetic would otherwise overflow.]Suppose a computer has atomic fetch and increment (FAI)instruction that also returns the new value of the variableafter the increment: int FAI (int &var) = < var = var+1; return var; > Using FAI, develop a pseudocode solution to the criticalsection problem for n processes. Don’t worry about the “eventual entry”property. Try to make your solution as cache efficient as possible (in the sense of minimisingcoherence traffic). Describe clearly how your solution works and why it is correct andefficient. [You can also assume atomic reads and writes and asequentially consistent model of shared memory. You should also assume that the program runswith an integer type which can store arbitrarily large positive or negativevalues. In other words, there is no issue about “wrapping around” wheninteger arithmetic would otherwise overflow.]
Explanation / Answer
1. Mutual Exclusion: if Pi is executing in oneof its critical sections, no Pj,j i isexecuting in its critical sections.
2. Progress: a process operating outside of its criticalsection cannot prevent other processes from entering theirs;processes attempting to enter their critical sectionssimultaneously must decide which process enters eventually and.
3. Bounded Waiting: a process attempting to enter itscritical region will be able to do so eventually.
Assumptions:
No assumptions made about relative speed of processes
No process may remain in its critical section indefinitely.
If a memory operation (read or write) is atomic then cannot beinterrupted. For now, we do not assume indivisible RMW cycles.
FAI solution to Critical Section problem for nprocesses:
{
int myTicket;
myTicket = FAI(nextTicket); // FAI meansFeatch and Increment.It is a special mechine instruction.
while (myTicket != serving);
}
mutexend()
{
++serving;
}
The proof of correctness:
Mutual exclusion may be contradiction.
Assume that no process plays with control variables.
The Progress of the critical section problem by inspection,there's no involvement from processes operating outside theirCritical Sections.
Bounded waiting is my Ticket at most n more thanserving.
I hope this is helpful foryou......
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.