[M3devel] pthread scheduling fairness of Signal

[Rodney M. Bates]

On 06/30/2015 01:37 AM, Jay K wrote:
> 1) This sounds good.
> 2) Can you please apply your analysis to the Win32 version also?
>

It looks to me like these matters are entirely delegated to windows-supplied library routines
EnterCriticalSection, LeaveCriticalSection, SetEvent, and WaitForMultipleObjects.

>
> Tangentially, I've said both of these before:
>
>
> 3) I'd really like to layer the pthread and Win32
> versions over a common interface.
>
>
> 4) Possibly make it much thinner, if Modula-3 semantics
> are close enough to pthread/win32+cv.
>
>
>   - Jay
>
>
>
>  > Date: Mon, 29 Jun 2015 19:18:41 -0500
>  > From: rodney_bates at lcwb.coop
>  > To: hosking at purdue.edu; mika at async.caltech.edu; m3devel at elegosoft.com
>  > Subject: Re: [M3devel] pthread scheduling fairness of Signal
>  >
>  >
>  >
>  > On 06/29/2015 08:53 AM, Antony Hosking wrote:
>  > >
>  > >> On Jun 29, 2015, at 9:40 AM, Rodney M. Bates <rodney_bates at lcwb.coop> wrote:
>  > >>
>  > >>
>  > >>
>  > >> On 06/28/2015 01:16 PM, Antony Hosking wrote:
>  > >>> It mirrors the user-level threads information as far as I recall.
>  > >>>
>  > >>
>  > >> Do you think that was intentional in the original user-level implementation?
>  > >> It seems like an open invitation to starvation. And it seems even more
>  > >> important for condition variables than mutexen. (hush, spell checker!)
>  > >
>  > > Perhaps take a look at the original user-level implementation to confirm.
>  > > I agree that ideally it would be FIFO. Feel free to think on what is needed to do that.
>  > >
>  >
>  > I looked at ThreadPosix.m3, and indeed it is the same way: FIFO for awakening
>  > Mutex waiters and LIFO for Condition waiters.
>  >
>  > Also, in both thread implementations, the FIFO wakeup is O(n) for a single wakeup.
>  > (n=# of waiting threads.) I think n will most often be quite small, but occasionally,
>  > maybe not, and if/when high thread counts do occur, it would be a good time for things
>  > to be fast.
>  >
>  > It would be quite easy to make both cases FIFO and O(1). No synchronization
>  > changes, just change a few lines of code while holding the same locks that are already
>  > being held.
>  >
>  > If nobody objects, I think I will try this.
>  >
>  > >>
>  > >> Mika's high-volume thread tester continuously churns out
>  > >> "Thread <n> appears starved or deadlocked" messages by the hundreds.
>  > >>
>  > >>> Sent from my iPad
>  > >>>
>  > >>>> On Jun 28, 2015, at 1:58 PM, Rodney M. Bates <rodney_bates at lcwb.coop> wrote:
>  > >>>>
>  > >>>> In vetting ThreadPThread in conjunction with the formsedit assertion failure, I
>  > >>>> notice that threads waiting on an M3 MUTEX are awakened in FIFO order, but those
>  > >>>> waiting on an M3 Condition variable are awakened LIFO by Signal. Is this really
>  > >>>> what we want?
>  > >>>> --
>  > >>>> Rodney Bates
>  > >>>> rodney.m.bates at acm.org
>  > >>>
>  > >>
>  > >> --
>  > >> Rodney Bates
>  > >> rodney.m.bates at acm.org
>  > >
>  > >
>  >
>  > --
>  > Rodney Bates
>  > rodney.m.bates at acm.org

-- 
Rodney Bates
rodney.m.bates at acm.org