Search code examples
operating-systemsynchronizationcritical-sectionthread-synchronization

Process synchronization - Critical section

I am studying for my final in OS. Currently on process sync chapter. Our book is offering the following algorithm to deal with Critical Section. It claims that the algorithm solves the problem of starvation and offers bounded wait. Here is the pseudocode

var flag: array [0..1] of Boolean;
Turn: 0..1;

Repeat
    flag[i] := true;
    turn := j;
    while (flag[j] and turn=j) do no-op;
       critical section
    flag[i] := false;
       remainder section
until false;

From my understanding, starvation occurs when a process is in its Critical Section and another process needs an access to it, but the first process won't finish. So the second process has to wait forever. I remember from CPU scheduling that implementing aging in the algorithm, for example, would solve starvation. But I don't see how that would happen here.

Am I wrong? Is there something that I'm not seeing here? Thank you.

Solution

  • imagine that we have 2 processes: 1 and 2, process1 wants to go to the CS: Let's start with the first process:

    Repeat
    flag[1] := true;
    turn := 2;

    I want to explain the "while" in your code:

    1. if falg[2] was equal to true: it means that the the process2 has already ran the blow line of it's code

      flag[2] := true;

    2. but another question: did process2 run the next line? I mean: did it ran: "turn := 1;" ? if yes: it means that both of them want to enter to CS at the same time.

    which one should go to CS first?

    if the turn value is equal to number 2 it means that process1 ran the "turn:=2" code after process2, because turn variable is the value process1 set it means that process2 ran it earlier, so it's process2 turn. the n while process2 is in CS we do nothing

    while (flag[2] and turn=j) do no-op;
       critical section
    flag[i] := false;
       remainder section
until false;

    process2 was in CSand process1 was waiting, process2 false his flag exactly after finishing his CS section. So process1 will go to CS.

    Does Starvation Happen In This Solution?

    Starvation is a resource management problem where a process does not get the resources it needs for a long time (maybe unlimited) because the resources are being allocated to other processes. But at this solution process2 cant get the resource again, because it set's its flag to value 0, and it should run "flag[2]=1" again to enter the CS, but process1 is in CS at that time, and process2 should wait FOR getting into CS.

    What Happens When One Process Don't Finnish it's CS?

    if process2 can't finish CS, process1 will wait for ever,But There is no solution for this one when we say that a solution don't have starvation, we don't mean this situation. we mean if both processes work correctly and don't have any problem in there critical section code, NOW THE STARVATION WONT HAPPEN

    How The Algorithm Works?

    there are two people, they want to enter to a room, this room is CS.
    both should up there flag, to tell that we want to enter the CS
    But, only one person can enter
    they both have one ticket, on their ticket a number has written. this number is the id of another person.
    there is a packet that has space just for ticket.
    when person1 want to enter, he should put his ticket there.
    so now there is a ticket with number "2"
    at this time person2 will come
    he must put his ticket on that packet, because there isn't any space. he will put it on the first ticket
    So now when you look at the packet, you just see the second ticket
    on the second ticket the number 1 has written
    So, person1 can enter.
    and he cant enter again because person2 is standing in front of the door and when person1 came out its flag will be false (after the cs his flag will be false) and the while (for the person2) will stop so he can enter

    if it's not clear tell me, I will explain more