[Vm-dev] Why isn't signalSemaphoreWithIndex() thread-safe?

[Eliot Miranda]

On Sun, Sep 20, 2009 at 3:35 PM, Igor Stasenko <siguctua at gmail.com> wrote:

>
> 2009/9/21 Joshua Gargus <schwa at fastmail.us>:
> >
> > Igor Stasenko wrote:
> >>
> >> 2009/9/21 Joshua Gargus <schwa at fastmail.us>:
> >>
> >>> Eliot Miranda wrote:
> >>>
> >>>>
> ------------------------------------------------------------------------
> >>>>
> >>>>
> >>>>
> >>>> On Sun, Sep 20, 2009 at 1:00 PM, Eliot Miranda
> >>>> <eliot.miranda at gmail.com <mailto:eliot.miranda at gmail.com>> wrote:
> >>>>
> >>>>      Instead we can use three variables per index to implement an
> >>>>     exclusion-free solution, thusly:
> >>>>
> >>>>     typedef struct { int lock; // accessed via e.g. XCHG to protect
> >>>>     signalRequest
> >>>>                            int requests;
> >>>>                            int responses;
> >>>>                } ExternalSignalRequest;
> >>>>
> >>>>     ExternalSignalRequest *externalSignalRequests;
> >>>>     int checkExternalSignalRequests;
> >>>>
> >>>>     void
> >>>>     requestSignal(int i)
> >>>>     {
> >>>>            while (!lock(&externalSignalRequests[i].lock))
> >>>>                  usleep(1);
> >>>>
> >>>>            ++externalSignalRequests[i].requests;
> >>>>
> >>>>             unlock(&externalSignalRequests[i].lock);
> >>>>
> >>>>             checkExternalSignalRequests = 1;
> >>>>             forceInterruptCheck();  // set a flag to cause the VM to
> >>>>     check for interrupts; in the stack VM this is stackLimit :=
> >>>>     (usqInt)-1;
> >>>>     }
> >>>>
> >>>>
> >>>>     The VM responds in checkEvents:
> >>>>
> >>>>         if (checkExternalSignalRequests)
> >>>>             for (i = 0; i < numExternalSemaphores; i++)
> >>>>                 while (externalSignalRequests[i]. responses
> >>>>     != externalSignalRequests[i]. requests) {
> >>>>                     signalSemaphoreWithIndex(i);
> >>>>                     externalSignalRequests[i]. responses;
> >>>>                 }
> >>>>
> >>>>
> >>> Am I correct that ExternalSignalRequest.reponses is never reset to
> zero,
> >>> instead eventually wrapping around?  That worried me for a minute, but
> I
> >>> see that it doesn't matter.  Neeto.
> >>>
> >>>
> >>
> >> Nope, it does resets the counters.. see signalExternalSemaphores
>  method.
> >>
> >
> > I was responding to Eliot's proposal, not the existing code.  If I
> > understand properly, he's proposing to maintain a per-semaphore count of
> > signal requests/responses, so there would be no
> > "semaphoresToSignalCountA/B".
> >
> Ah.. sorry for not reading carefully..
> In proposed scenario i don't like 1 (one) thing, that checkForInterrupts
> will
> spend a linear amount of time to check what semaphores need to be signaled
> instead of spending linear amount of time to signal semaphores which
> is to be signaled:
>
>     for (i = 0; i < numExternalSemaphores; i++)
>
> means, that if you having 1000 external semaphores, and only 1 of them
> signaled currently, you have to
> loop through all of them, inevitably :(
>

Yes, that caused a twinge.  Bit with a separate lock we can maintain high
and low tides, e.g.

typedef struct { int lock; // accessed via e.g. XCHG to protect
signalRequest
                       int requests;
                       int responses;
           } ExternalSignalRequest;

ExternalSignalRequest *externalSignalRequests;
int checkExternalSignalRequests;
int tideLock = 0;
int useTideA = 1;
int lowTideA = (unsigned)-1 >> 1, highTideA = 0;
int lowTideB = (unsigned)-1 >> 1, highTideB = 0;

void
requestSignal(int i)
{
       while (!lock(& tideLock))
             usleep(1);

       if (useTideA) {
            if (lowTideA > i) lowTideA = i;
            if (highTideA < i) highTideA = i);
       }
       else {
            if (lowTideB > i) lowTideB = i;
            if (highTideB < i) highTideB = i);
       }

       while (!lock(&externalSignalRequests[i].lock))
             usleep(1);

       ++externalSignalRequests[i].requests;

        unlock(&externalSignalRequests[i].lock);

        checkExternalSignalRequests = 1;
        forceInterruptCheck();  // set a flag to cause the VM to check for
interrupts; in the stack VM this is stackLimit := (usqInt)-1;
}


The VM responds in checkEvents:

    if (checkExternalSignalRequests) {
      checkExternalSignalRequests = 0; // forgot this in my first email
      if (useTideA) {
        useTideA = 0;
        for (i = lowTideA; i < highTideA; i++)
            while (externalSignalRequests[i]. responses
!= externalSignalRequests[i]. requests) {
                signalSemaphoreWithIndex(i);
                externalSignalRequests[i]. responses;
            }
            lowTideA = (unsigned)-1 >> 1, highTideA = 0;
      }
      else  {
        useTideA = 1;
        for (i = lowTideB; i < highTideB; i++)
            while (externalSignalRequests[i]. responses
!= externalSignalRequests[i]. requests) {
                signalSemaphoreWithIndex(i);
                externalSignalRequests[i]. responses;
            }
        lowTideB = (unsigned)-1 >> 1, highTideB = 0;
      }

and we should make lowTideA = (unsigned)-1 >> 1, highTideA = 0; a macro, to
avoid the duplication.
Most of the time the low and high tides will get set to the same thing
because very likely most of the time only one semaphore will get signalled.


Note that I did the moral equivalent of this with the processor scheduler's
queue in both VW and in the Cog Squeak VMs and it speeds up
wakeHighestPriority a lot.  The idea is to maintain in a variable the
highest runnable priority, which is increased whenever a process is added to
the runnable queue and is of higher priority than the high tide, and reduced
in wakeHighestPriority to that of the first process found.  This avoids
wakeHighestPriority testing 50 odd empty lists on the typical pass through
runnable processes from 100 down to user priority.


We're getting close to the end of a release cycle so I expect we'll release
the Stack Cog VM soon thereafter.  Sorry for the wait so far :/


> > Cheers,
> > Josh
> >
> >
>
>
>
> --
> Best regards,
> Igor Stasenko AKA sig.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20090920/2ad797e5/attachment-0001.htm