[Concurrent Programming] "passing the condition"

[fault]

Howdy,

Anybody out there know what the term "passing the condition" means? I'm just a little confused about it all and an elaboration on the idea behind would be good. In particular, here's the pseudo code we've been studying that revolves around it. It's based on the Shortest-Job-Next Allocation problem.

monitor SJN {

 ?bool free = true; # invariant: turn ordered by time && (free -> turn is empty)
 ?condition_variable turn; # signaled when resource available

 ?# request the resource
 ?procedure request(int time) {
 ? ?if (free)
 ? ? ?free = false;
 ? ?else
 ? ? ?wait(turn, time);
 ?}

 ?# release the resource
 ?procedure release() {
 ? ?if(empty(turn)) # are there processes waiting on the CV 'turn'?
 ? ? ?free = true;
 ? ?else
 ? ? ?signal(turn);
 ?}

}

I'm confused about this because consider the case where we're done usingrelease()d decide to release() it.

If there are no proceempty()n the CV (ie.true will return true and the if block will be executed), then we set:

free = true;

Then we don't need to signal. That makes sense.

But coare case where there are processes blocked on the CV?! (ie. those processes are sleeping waiting for it and need to be woken up by the process finishing with the rsignal(turn) calling <empty()).

Well, empty() would return false and the else block would be executed. Here the code says:

signal(turn);

But we haven't reset free yet? So how could another process request the resource and successfully get it? Won't it just be put to sleewait()it'll call wait())since free is still false?

Any clarification would be great.

Edited August 24, 2005 by fault

[Andareed]

If process B calls request(), and free = false, then it will call wait(). Say process A was using the resource and is now done. It calls signal(). I'm assuming this call will wake up process B, and B will start executing after wait(), and completely avoid the free check.

In short, any new processes are just going to wait() until until free = true. When a process is done with a resource, it checks to see if anyone is waiting. If they are, it wakes them up; the resource would be "switched", so it would wrong to set free = true. On the other hand, if no processes are waiting, then free = true is correct.

There are a few races conditions in the code, but I don't know the context/assumptions this code is running under.

[THE BAT]

  Andareed said:

There are a few races conditions in the code, but I don't know the context/assumptions this code is running under.

586424643[/snapback]

yes

and it something belong to OS, with more Complex condition than this.

[fault]

  Andareed said:

If process B calls request(), and free = false, then it will call wait(). Say process A was using the resource and is now done. It calls signal(). I'm assuming this call will wake up process B, and B will start executing after wait(), and completely avoid the free check.

586424643[/snapback]

Ohhh, god damn - that's so obvious, how did I miss that? :pinch: Makes perfect sense. Cheers.

  Andareed said:

In short, any new processes are just going to wait() until until free = true. When a process is done with a resource, it checks to see if anyone is waiting. If they are, it wakes them up; the resource would be "switched", so it would wrong to set free = true. On the other hand, if no processes are waiting, then free = true is correct.

586424643[/snapback]

Ah, I see - hence the term "passing the condition"... it's all clear now.

  Andareed said:

There are a few races conditions in the code, but I don't know the context/assumptions this code is running under.

586424643[/snapback]

There are? Where! :wacko:

Another question, is "passing the baton" the same as "passing the condition"? Cheers.

[Andareed]

Suppose process A and B both call request (while it is free). It's possible (due to pre-emptive context switching), that A will execute "if (free)" (which evaluates to true), and then is pre-empted by B. Then B runs, and also executes "if (free)", and then "free = false;". B will claim it owns the condition. Now say B is pre-empted, and A runs. A will run execute "free = false" too, and will also claim that it owns the condition.

There's a similar issue when calling empty().

If you aren't dealing pre-emptive scheduling (i.e., a thread runs until it calls a function that blocks, e.g., wait()), then there is no race condition.