CODEWITHSUNDEEP
multithreadingprocessoperating-systemlockingmutex
nickackerman42
nickackerman42

Reputation: 515

Why does a simplification of Peterson's Algorithm using a single 'turn' variable not provide process synchronization?

I'm reading "Operating System Concepts" and trying to make sense of Peterson's Solution (on page 208), an algorithm for ensuring two processes sharing memory do not access the shared resource at the same time (potentially creating a race condition).

In Peterson's Solution, there are two shared variables that help with synchronization: "boolean flag[2]" and "int turn". "flag[i]" indicates whether a particular process is trying to enter its "critical section," the section where it accesses shared data. "turn" contains one of the two processes' indexes (0 or 1) and indicates which process' turn it is to access the shared data.

Peterson's algorithm (for process i, where the other process is denoted by j) is below:

do {
    #set flag to say I'm trying to run
    flag[i] = true
    #let the other process have a turn
    turn = j
    while(flag[j] == true && turn == j);

    #enter critical section

    flag[i] = false

    #do non-critial remaining stuff

} while (true);

Why does the following simplification of Peterson's algorithm not also provide process synchronization? If I understand why not, I believe it will help me understand Peterson's algorithm.

#initialize turn to i or j
do {
    while(turn == j);

    #enter critical section

    turn = j;

    #do non-critial remaining stuff

} while (true);

In this simplified algorithm, it seems to me that a given process i will continue while looping until the other process j finishes its critical section, at which point j will set "turn = i", allowing i to begin. Why does this algorithm not achieve process synchronization?

Upvotes: 3

Views: 1564

Answers (1)

Sumeet
Sumeet

Reputation: 8292

Because there is a chance of starvation in the simplified version.

As you mentioned:

j finishes its critical section, at which point j will set "turn = i", allowing i to begin.

Ok, now say Process i finishes and will set turn = j . Now if Process i, again wants to enter critical section, it cannot enter as turn = j. The only way for Process i to be able to enter Critical Section is Process j again enters Critical Section and sets turn = i.

So, as you see the simplified version requires that the processes must enter critical section in strict alternation, otherwise it will lead to starvation.

Upvotes: 4

Related Questions