Sync. problem

[AlbaLed]

The basic structure of a processes with a critical section is shown below

while (TRUE)
{
enter_cs();
critical section
leave_cs();
rest of loop
}

Which of the following definitions of enter_cs and leave_cs provide a
solution to the mutual exclusion problem for two processes, P0 and P1?

[color=Red]Case 1.[/color]

int	turn = 0;

[color=brown]enter_cs()[/color]
{
while (turn == procno)
	;
}

[color=Blue]leave_cs()[/color]
{
turn = procno;
}

[color=Red]Case 2.[/color]

bool	in_crit_sect[2] = {FALSE, FALSE};

[color=brown]enter_cs()[/color]
{
while (in_crit_sect[otherprocno])
	;
in_crit_sect[procno] = TRUE;
}

[color=Blue]leave_cs()[/color]
{
in_crit_sect[procno] = FALSE;
}

[color=Red]Case 3.[/color]

bool	want_crit_sect[2] = {FALSE, FALSE};

[color=brown]enter_cs()[/color]
{
want_crit_sect[procno] = TRUE;
while (want_crit_sect[otherprocno])
	;
}

[color=Blue]leave_cs()[/color]
{
want_crit_sect[procno] = FALSE;
}

[color=Red]Case 4.[/color]

bool	want_crit_sect[2] = {FALSE, FALSE};
int	turn = 0;

[color=brown]enter_cs()[/color]
{
want_crit_sect[procno] = TRUE;
turn = procno;
while (want_crit_sect[otherprocno] && turn == procno)
	;
}

[color=Blue]leave_cs()[/color]
{
want_crit_sect[procno] = FALSE;
}

 

 

 

2. What are the relative advantages and disadvantages of using

semaphores and monitors for implementing process synchronization?

 

 

Taken from links in "sticky" thead

[wood]

Nice post!

 

Case 4?

[AlbaLed]

Why wood, I know this is in many books but can you actually post what properties a synching mechanism should satisfy??

[wood]

I am not sure how to put it in terms of properties. I basically visualize a small test case for each one of them and bingo!

 

Let me try anyway. Basically, you need two things for mutual exclusion of two processes.

 

(1) One process must initialize its intent of getting into the CS.

 

(2) One process must get into the CS just if it is its turn to do so.

 

(1) is needed to "queue" the processes willing to get into the CS. (2) is needed to actually decide which one should go next.

 

If you implement just (2)-Case 1 or (1)-Case 3, you might easily get with two processes inside your CS.

 

Case 4: even if two processes get into enter_cs() at the same time, they will both set their intent to true and the value of turn set by one process will be overwritten by the other process. The turn value will then be used to determine which process get into the CS first.

 

Case 4 is basically Peterson's algorithm, right?

 

Wood

[Vinay]

none of them will work

 

i think you made sum typo in case 4 or may be its delibrate. if its as shown thn case 4 can also be not correct

[wood]

Vinay,

 

Case 4 is definitely G.L. Patterson's algorithm (see Modern Operating Systems by Tanenbaum, section 2.2 Inteprocess Communication / Peterson's Solution). There's no typo there and it works fine.

 

Wood

[AlbaLed]

Don't know the algorithm by its name but I've seen it everywhere.

A mutual exclusion mechanism should guarantee the following

 

1. Correctnes (duhh, only 1 process should be in the crit. sect. at one time)

2. Bounded waiting, no process should wait forever to enter its critical section (starvation)

3. Progress, if no process is in the CS and other processes want to enter their CS then one of them should succseed in entering its CS (no deadlocks can occur)

 

This can be used as a guide to test and algo., you can stop one process inbetween any two instruction and start the other where you left off (if running on a single cpu), and check whether any of the above is broken. Try it with other cases and you'll see what I mean.

Even-eventhough informal your description made some points, but I think you forgot the deadlock part.

[wood]

Great AlbaLed.

 

Curiosity:

 

How are semaphores and monitors used in distributed systems?

 

 

 

[AlbaLed]

We'll have to find out about that, hang on

[wood]

Hint: it's a tricky one... :D

[AlbaLed]

Using those particular mutex mechanisms or achieving mutual exclusion???

[wood]

Well, whatever you think they (semaphores and monitors) might be useful for!! :D

[AlbaLed]

Here is what I found out

 

3 methods

 

1. Centralized mutex

one system acts as the "mutex master"(mm). A process cannot enter its CS unless it receives approval from mm, mm proceses requests using fcfs for example.

 

2. Distributed mutex

If one proc. want to enter CS, it sends out a timestamped message containing, pID and CS name. It enters CS upon approval from all other systems. Upon receiving a request, a system sends out an approval note iff it is not waiting to enter that particular CS or if the timestamp of the request is lower than its request for this CS. Otherwise it does send out a permission denied note. Timers can be used to determine if a node is down, if nothing is heard from it.

 

3. Token passing

Wait untill token comes than enter CS, when done release token

 

am I in stratosphere?

[Vinay]

hmmm well if you guys have galvin, thn algorithm 3 under "2 process solutions" in process synchronisation chapter looks like this algo apart frm difference at 2 places. heres the algo:

 

flag[0]=flag[1]=false

turn=0..1

 

now your algo has procno nd otherprocno (i,j)

 

flag=true;

turn=j; ---- heres one difference

while(flag[j] and trun=j) do noop; ---- heres another one

critical section

flag=false

remainder section

 

 

[wood]

Most likely!! :D

 

Anyway... Great job AlbaLed in finding these topics!! You've certainly implemented a hash table in your brain... in less than seconds you can find any answer! ;)

 

I was looking for something a little simpler such as: "semaphores and monitors cannot be used in distributed systems since their basic logic requires that the processes/threads share a common memory. Therefore, to implement the concept of mutual exclusion in distributed systems, some mechanism utilizing message passing is needed (all your three cases are specific techniques using message passing)."

 

Wood

[Vinay]

anyway guys gr8 discussion my head is spinning its been 18 hrs tht I have been awake :-|, now goin to get some sleep, ciya

[wood]

now your algo has procno nd otherprocno (i,j)

 

flag=true;

turn=j; ---- heres one difference

while(flag[j] and trun=j) do noop; ---- heres another one

critical section

flag=false

remainder section

 

Vinay, there's no difference between the two algos. The only difference is on the value of turn and its check. The idea is to set the value of turn to something and then check for that same value to see if nobody changed since you last set. If you set it to i, j, k, l, m, n, o, or p, it doesn't matter right? As long as you check for the same value on the while loop.

 

Wood

[AlbaLed]

wood message passing can be used even on uniproc, machines to ensure mutex, but not efficiently, on my OS class I had a hwk assingment to do just that, on xinu tho :), Vinay, get some rest before you hit this stuff again an again, with that rate you've got another 160 hrs to go, lol

[wood]

AlbaLed, true...! They can be used on uniproc! I never said the contrary.

[AlbaLed]

was just pointing it out, did not mean it as a "you said the contrary" response

[Vinay]

u mean

while (want_crit_sect[otherprocno] && turn == procno) ;

and

while(flag[j] and trun=j) do noop;

 

are same when procno is standing for I and otherprocno for j

 

if you substitute thm in first you get

while (want_crit_sect[j] && turn == i) ;

 

may be I m wrong but I also tried executing tht code.

if both p0 and p1 set thr flags true and thr turn to their ids thn both will not run.

[wood]

Got it... sorry about the misinterpretation. My head is spinning now... Signing off.

 

Wood

[Vinay]

wood no place for sorry among friends :-)

 

can anybody please analyse the piece of code for case 4 and dry run it for 2 sample processes?

anybody?

[AlbaLed]

flag=true;

turn=j; ---- heres one difference

while(flag[j] and trun=j) do noop; ---- heres another one

critical section

flag=false

remainder section

 

Vinay this code is the same as the case 4, the only difference is that each process is saying it's the others turn. Processes cannot be deadlocked because turn can only have one value. The trick in the above code is that for process 1 i=0, j =1, and for process 2 i=1, j=0. think of j=other, i=myself.

Keep in mind that turn and the flag array are global vars.

 

The coding of case 4 is some what strange, maybe the guy who wrote it wanted to make it fairer or harder for his/her students. One process does not enter CS if the other process has already made a request, but if the other process set the turn variable after this process set it i.e. in current process turn=otherprocno, then this process will enter its CS. In general if a tie occurs turn is used to break the tie, because it can have only one value.

 

Does that help!?

[Vinay]

thnx :-)

but this code is ambiguous, as far as I know turn is used to assign process no. of the current process.