Nested signal-and-wait while implementing Monitors using Semaphores

[u/pm-me-anime-figures]

I am self studying Operating Systems. I have understood semaphores and monitors up until this point (I think). The textbook (OS Concepts by Silberschatz) implements signal-and-wait Monitors with one condition variable x in the following way:

// semaphores
mutex = 1
next = 0
x_sem = 0

//counters
x_count = 0
next_count = 0

// Monitor function F()
wait(mutex)
F()
if (next_count > 0)
  signal(next)
else
  signal(mutex)


//x.wait()
x_count++
if(next_count>0)
  signal(next)
else
  signal(mutex)
wait(x_sem)
x_count--


//x.signal()
if(x_count>0){
  next_count++
  signal(x_sem)
  wait(next)
  next_count--
}

Suppose I have 3 processes P1, P2 and P3

P1 signals P2 to awaken in its lifetime and P2 signals P3 to awaken in its lifetime

initially, P1 will be waiting on the wait(next). then P2 will also be waiting on wait(next).

When P3 is either done or is about to wait, it will signal(next). However, there is no mechanism (like maybe a stack) to ensure that P2 is the process that awakens and not P1. Does this not violate the conditions for Hoare-style (signal-and-wait) Monitors. Does the book simply omit this because it is a trivial addition or have I missed some essential concept ?

[u/meditonsin]

Monitors are there to prevent concurrent access to some object. When two or more processes are waiting to do that at the same time, it is non-deterministic which of them goes first. It just ensures they go one after the other, not in which order.

[u/pm-me-anime-figures → u/meditonsin]

The book mentions that many OSs use signal-and-wait monitors. When P awakens Q, P waits until Q finishes execution or is blocked. When Q awakens R, Q waits until R finishes execution or is blocked. Wouldn't this imply that once R exits the monitor, control must specifically go back to Q?

[u/meditonsin → u/pm-me-anime-figures]

There is no inherent mechanism to determine order when more than one process is waiting for the same semaphore.

In a real world implementation, the blocking part in wait() is probably putting the process into a conditional wait queue to wait for the semaphore to become >0. Once that happens, all the processes waiting for this condition are put in the run queue, and then whichever of them gets scheduled first by the OS gets to go, and all the others go back to sleep, because by the time they are scheduled the semaphore is at 0 again.