• 0

[Concurrent Programming] "passing the condition"


Question

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 by fault

4 answers to this question

Recommended Posts

  • 0

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.

  • 0
  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.

  • 0
  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.

  • 0

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.

This topic is now closed to further replies.
  • Recently Browsing   0 members

    • No registered users viewing this page.
  • Posts

    • Save 15% on the Insta360 Link 2 4K Webcam, now available at the lowest price by Taras Buria Insta360 is known for its high-quality 360-cameras, but the company also offers high-end webcams for those who want to elevate their video calls or streaming. Right now, the Insta360 Link 2 4K webcam is available at a new all-time low price, saving you 15% off the standard MSRP. The Insta360 Link 2 is not your standard 4K webcam. This camera is mounted on a two-axis gimbal that physically pans and tilts to follow you as you move around the room. You can also set boundaries to prevent the camera from capturing certain areas and control it with gestures for a hands-free experience. The camera itself has a large 1/2" 4K sensor that captures more light and details with HDR and low-light mode support. A larger sensor also means a more natural bokeh effect. Built-in microphones support voice focus and voice suppression, and the camera can balance your voice with background music. Other features include additional modes, such as whiteboard mode, DeskView mode, portrait mode, and privacy mode. The latter tilts the camera down after 10 seconds of inactivity (you can also push it down manually). The Insta360 Link 2 is also remotely operated with a dedicated phone app, plus its desktop software lets you adjust features like background, filters, and more. Insta360 Link 2 4K Webcam - $169.99 | 15% off on Amazon US Insta360 Link 2 4K Webcam Tripod Bundle - $195 | 15% off on Amazon US This Amazon deal is US-specific and not available in other regions unless specified. If you don't like it or want to look at more options, check out the Amazon US deals page here. Get Prime (SNAP), Prime Video, Audible Plus or Kindle / Music Unlimited. Free for 30 days. As an Amazon Associate, we earn from qualifying purchases.
    • RIP Jonathan Joss aka John Redcorn https://www.nbcnews.com/news/us-news/jonathan-joss-king-hill-voice-actor-killed-san-antonio-shooting-rcna210437
    • This will happen regardless what simply because people are upgrading their gear.
    • Rest in Peace, Loretta.  😢
    • Well, so did Lt. O'Reilly... but, we had to go there. 😂
  • Recent Achievements

    • Week One Done
      Nullun earned a badge
      Week One Done
    • First Post
      sultangris earned a badge
      First Post
    • Reacting Well
      sultangris earned a badge
      Reacting Well
    • First Post
      ClarkB earned a badge
      First Post
    • Week One Done
      Epaminombas earned a badge
      Week One Done
  • Popular Contributors

    1. 1
      +primortal
      160
    2. 2
      ATLien_0
      124
    3. 3
      Xenon
      120
    4. 4
      snowy owl
      109
    5. 5
      +Edouard
      97
  • Tell a friend

    Love Neowin? Tell a friend!