[M3devel] pthread scheduling fairness of Signal

[Rodney M. Bates]

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