<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small">Hi Jaromir, Hi Craig, Hi All,</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Dec 28, 2021 at 3:32 PM Eliot Miranda <<a href="mailto:eliot.miranda@gmail.com">eliot.miranda@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div style="font-size:small"><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Dec 28, 2021 at 2:15 PM Eliot Miranda <<a href="mailto:eliot.miranda@gmail.com" target="_blank">eliot.miranda@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div style="font-size:small"><br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Dec 28, 2021 at 1:53 PM <<a href="mailto:mail@jaromir.net" target="_blank">mail@jaromir.net</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">Hi Eliot, all,<br>
<br>
this example shows Mutex's critical section can be entered multiple times:<br></blockquote><div><br></div><div style="font-size:small">I know. suspend is broken. Please read my previous message fully and carefully. If I implement the second alternative then the example works correctly. In the siulator I get:</div><div style="font-size:small"><br></div><div style="font-size:small">{a Semaphore(a Process(75019) in [] in [] in UndefinedObject>>DoIt) .</div> a Mutex(a Process(59775) in Mutex>>critical:) .<br> a Process(75019) in [] in [] in UndefinedObject>>DoIt . false .<br> a Process(59775) in Mutex>>critical: . false}</div></div></blockquote><div><br></div><div style="font-size:small">However, this comes at the cost of finding that the new terminate is broken. If suspend does not remove a process from its list then a process terminated while waiting on a Semaphore remains on that semaphore. So terminate must not only ensure that any critical sections are released, but that the process is removed from its list, if that list is a condition variable. IMO this should happen very early on in terminate. I'm running the second alternative but I have to filter out unrunnable processes in signal et al since suspend no longer removes from the list.</div></div></div></blockquote><div><br></div><div class="gmail_default" style="font-size:small">Having thought about it for a couple of days I now think that the second alternative is the only rational approach. This is that suspend always removes a process from whatever list it is on, but if the list is not its run queue, the process is backed up one bytecode to the send that invoked the wait. Hence if the process resumes it immediately progresses into the wait again, leaving it exactly where it was if it hadn't been suspended.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">Craig I hear your concern, but being able to (especially accidentally) suspend a process and resume it and find it has progressed beyond whatever condition variable it was waiting on is entirely unacceptable.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">My first alternative, that suspend does not remove a process from its list if a condition variable, breaks the existing code base. For example a typical pattern at start up is to suspend the old version of a process waiting on a semaphore (e.g. the finalizationProcess) and start up a new one. The first alternative leaves the old process waiting on the semaphore.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">Digression: VisualWorks also implements the second choice, but it isn't obvious. HPS, the VisualWorks VM, can only run jitted code; it has no interpreter. So backing up the pc to before the send is really difficult to implement; it introducers arbitrarily many suspension points since the send of the wait/enterCriticalSection et al can be preceded by an arbitrary expression. Instead, one additional suspension point is introduced, complementing after a send, at a backward jump, and at method entry (after frame build, before executing the first bytecode). Here primitives can be in one of two states, uncommitted, and committed. Uncommitted primitives after primitives in progress. One can't actually see this state. A committed primitive has a frame/context allocated for its execution. A committed primitive may have completed (e.g. an FFI call is in progress, waiting for a result) or is yet to start. So HPS can back up a committed primitive wait to the committed but uncompleted state. Hence resuming reenters the wait state. This is ok, but complex.</div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small">In Cog we have an interpreter and can easily convert a machine3 code frame in to an interpreted frame, so backing up the process to the send that invoked the wait/enterCriticalSection etc is fine. I'll have a go at this asap.</div><div class="gmail_default" style="font-size:small"><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><div style="font-size:small"><br></div><div style="font-size:small"><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<br>
| s p1 p2 p3 m |<br>
s := Semaphore new.<br>
m := Mutex new.<br>
p1 := [m critical: [s wait]] newProcess.<br>
p1 resume.<br>
p2 := [m critical: [s wait]] newProcess.<br>
p2 resume.<br>
Processor yield.<br>
{ p1. p1 suspend. p2. p2 suspend }.<br>
p1 resume. p2 resume.<br>
Processor yield.<br>
{ s. m. p1. p1 isTerminated. p2. p2 isTerminated. m isOwned. m instVarNamed: 'owner' }.<br>
p3 := [m critical: [s wait]] newProcess.<br>
p3 resume.<br>
Processor yield.<br>
{ s. m. p1. p1 isTerminated. p2. p2 isBlocked. p3. p3 isBlocked. m isOwned. m instVarNamed: 'owner' }.<br>
<br>
I've just added a third process to your last example; p3 really enters the critical section and takes m's ownership despite the fact p2 is already waiting inside m's critical section - because p2 managed to enter m withour taking m's ownership.<br>
<br>
Now we could repeat the procedure and keep adding processes inside the critical section indefinitely :) So I guess this really is a bug.<br>
<br>
Best,<br>
<br>
~~~<br>
^[^ Jaromir<br>
<br>
Sent from Squeak Inbox Talk<br>
<br>
On 2021-12-28T20:07:25+01:00, <a href="mailto:mail@jaromir.net" target="_blank">mail@jaromir.net</a> wrote:<br>
<br>
> Hi Eliot,<br>
> <br>
> Thanks! Please see my comments below, it seems to me there may be a bug in the Mutex.<br>
> <br>
> ~~~<br>
> ^[^ Jaromir<br>
> <br>
> Sent from Squeak Inbox Talk<br>
> <br>
> On 2021-12-27T14:55:22-08:00, eliot.miranda at <a href="http://gmail.com" rel="noreferrer" target="_blank">gmail.com</a> wrote:<br>
> <br>
> > Hi Jaromir,<br>
> > <br>
> > On Mon, Dec 27, 2021 at 2:52 AM <mail at <a href="http://jaromir.net" rel="noreferrer" target="_blank">jaromir.net</a>> wrote:<br>
> > <br>
> > > Hi all,<br>
> > ><br>
> > > What is the desirable semantics of resuming a previously suspended process?<br>
> > ><br>
> > <br>
> > That a process continue exactly as it had if it had not been suspended in<br>
> > the first place. In this regard our suspend is hopelessly broken for<br>
> > processes that are waiting on condition variables. See below.<br>
> > <br>
> > <br>
> > ><br>
> > > #resume's comment says: "Allow the process that the receiver represents to<br>
> > > continue. Put the receiver in *line to become the activeProcess*."<br>
> > ><br>
> > > The side-effect of this is that a terminating process can get resumed<br>
> > > (unless suspendedContext is set to nil - see test KernelTests-jar.417 /<br>
> > > Inbox - which has the unfortunate side-effect of #isTerminated answer true<br>
> > > during termination).<br>
> > ><br>
> > <br>
> > But a process that is terminating should not be resumable. This should be<br>
> > a non-issue. If a process is terminating itself then it is the active<br>
> > process, it has nil as its suspendedContext, and Processor<br>
> > activeProcess resume always produces an error.. Any process that is not<br>
> > terminating itself can be made to fail by having the machinery set the<br>
> > suspendedContext to nil.<br>
> > <br>
> <br>
> Yes agreed, but unfortunately that's precisely what is not happening in the current and previous #terminate and what I'm proposing in Kernel-jar.1437 - to set the suspendedContext to nil during termination, even before calling #releaseCriticalSection.<br>
> <br>
> > <br>
> > > A similar side-effect: a process originally waiting on a semaphore and<br>
> > > then suspended can be resumed into the runnable state and get scheduled,<br>
> > > effectively escaping the semaphore wait.<br>
> > ><br>
> > <br>
> > Right, This is the bug. So for example<br>
> > | s p |<br>
> > s *:=* Semaphore new.<br>
> > p *:=* [s wait] newProcess.<br>
> > p resume.<br>
> > Processor yield.<br>
> > { p. p suspend }<br>
> > <br>
> > answers an Array of process p that is past the wait, and the semaphore, s.<br>
> > And<br>
> > <br>
> > | s p |<br>
> > s *:=* Semaphore new.<br>
> > p *:=* [s wait] newProcess.<br>
> > p resume.<br>
> > Processor yield.<br>
> > p suspend; resume.<br>
> > Processor yield.<br>
> > p isTerminated<br>
> > <br>
> > answers true, whereas in both cases the process should remain waiting on<br>
> > the semaphore.<br>
> > <br>
> > ><br>
> > > Is this an expected behavior or a bug?<br>
> > ><br>
> > <br>
> > IMO it is a dreadful bug.<br>
> > <br>
> > > If a bug, should a suspended process somehow remember its previous state<br>
> > > and/or queue and return to the same one if resumed?<br>
> > ><br>
> > <br>
> > IMO the primitive should back up the process to the<br>
> > wait/primitiveEnterCriticalSection. This is trivial to implement in the<br>
> > image, but is potentially non-atomic. It is perhaps tricky to implement in<br>
> > the VM, but will be atomic.<br>
> > <br>
> > Sorry if I'm missing something :)<br>
> > ><br>
> > <br>
> > You're not missing anything :-) Here's another example that answers two<br>
> > processes which should both block but if resumed both make progress.<br>
> > <br>
> > | s p1 p2 m |<br>
> > s *:=* Semaphore new.<br>
> > m *:=* Mutex new.<br>
> > p1 *:=* [m critical: [s wait]] newProcess.<br>
> > p1 resume.<br>
> > p2 *:=* [m critical: [s wait]] newProcess.<br>
> > p2 resume.<br>
> > Processor yield.<br>
> > { p1. p1 suspend. p2. p2 suspend }<br>
> > <br>
> > p1 enters the mutex's critical section, becoming the mutex's owner. p2 then<br>
> > blocks attempting to enter m's critical section. Let's resume these two,<br>
> > and examine the semaphore and mutex:<br>
> > <br>
> > | s p1 p2 m |<br>
> > s *:=* Semaphore new.<br>
> > m *:=* Mutex new.<br>
> > p1 *:=* [m critical: [s wait]] newProcess.<br>
> > p1 resume.<br>
> > p2 *:=* [m critical: [s wait]] newProcess.<br>
> > p2 resume.<br>
> > Processor yield.<br>
> > { p1. p1 suspend. p2. p2 suspend }.<br>
> > p1 resume. p2 resume.<br>
> > Processor yield.<br>
> > { s. m. p1. p1 isTerminated. p2. p2 isTerminated }<br>
> > <br>
> > In this case the end result for p2 is accidentally correct. It ends up<br>
> > waiting on s within m's critical section. But p1 ends up terminated. IMO<br>
> > the correct result is that p1 remains waiting on s, and is still the owner<br>
> > of m, and p2 remains blocked trying to take ownership of m.<br>
> > <br>
> <br>
> Perfect example! My naive expectation was when a process inside a critical section gets suspended the Mutex gets unlocked but that's apparently wrong :)<br>
> <br>
> But still, there's something wrong with the example: If p1 resumes it releases m's ownership and terminates, then p2 takes over and proceeds inside the critical section and gets blocked at the semaphore. I'd expect p2 would become the owner of the Mutex m BUT it's not! There's no owner while p2 is sitting at the semaphore. Try:<br>
> <br>
> | s p1 p2 m |<br>
> s := Semaphore new.<br>
> m := Mutex new.<br>
> p1 := [m critical: [s wait]] newProcess.<br>
> p1 resume.<br>
> p2 := [m critical: [s wait]] newProcess.<br>
> p2 resume.<br>
> Processor yield.<br>
> { p1. p1 suspend. p2. p2 suspend }.<br>
> p1 resume. p2 resume.<br>
> Processor yield.<br>
> { s. m. p1. p1 isTerminated. p2. p2 isTerminated. m isOwned. m instVarNamed: 'owner' }<br>
> <br>
> It seems to me that when p2 gets suspended it is stopped somewhere inside #primitiveEnterCriticalSection before the owner is set and when it gets resumed it is placed into the runnable queue with the pc pointing right behind the primitive and so when it runs it just continues inside #critical and get blocked at the semaphore, all without having the ownership.<br>
> <br>
> Is this interpretation right? It would mean Mutex's critical section can be entered twice via this mechanism...<br>
> <br>
> Cuis does set the ownership to p2 in this example.<br>
> <br>
> Thanks again,<br>
> <br>
> Jaromir<br>
> > <br>
> > ><br>
> > > Best,<br>
> > > ~~~<br>
> > > ^[^ Jaromir<br>
> > ><br>
> > > Sent from Squeak Inbox Talk<br>
> > ><br>
> > <br>
> > _,,,^..^,,,_<br>
> > best, Eliot<br>
> > -------------- next part --------------<br>
> > An HTML attachment was scrubbed...<br>
> > URL: <<a href="http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20211227/8719df13/attachment.html" rel="noreferrer" target="_blank">http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20211227/8719df13/attachment.html</a>><br>
> > <br>
> ><br>
> <br>
> <br>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr"><div dir="ltr"><div><span style="font-size:small;border-collapse:separate"><div>_,,,^..^,,,_<br></div><div>best, Eliot</div></span></div></div></div></div>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr"><div dir="ltr"><div><span style="font-size:small;border-collapse:separate"><div>_,,,^..^,,,_<br></div><div>best, Eliot</div></span></div></div></div></div>
</blockquote></div><br clear="all"><div><br></div>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><span style="font-size:small;border-collapse:separate"><div>_,,,^..^,,,_<br></div><div>best, Eliot</div></span></div></div></div></div>