<br><br><div class="gmail_quote">On Sun, Sep 20, 2009 at 3:35 PM, Igor Stasenko <span dir="ltr"><<a href="mailto:siguctua@gmail.com">siguctua@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div><div></div><div class="h5"><br>
2009/9/21 Joshua Gargus <<a href="mailto:schwa@fastmail.us">schwa@fastmail.us</a>>:<br>
><br>
> Igor Stasenko wrote:<br>
>><br>
>> 2009/9/21 Joshua Gargus <<a href="mailto:schwa@fastmail.us">schwa@fastmail.us</a>>:<br>
>><br>
>>> Eliot Miranda wrote:<br>
>>><br>
>>>> ------------------------------------------------------------------------<br>
>>>><br>
>>>><br>
>>>><br>
>>>> On Sun, Sep 20, 2009 at 1:00 PM, Eliot Miranda<br>
>>>> <<a href="mailto:eliot.miranda@gmail.com">eliot.miranda@gmail.com</a> <mailto:<a href="mailto:eliot.miranda@gmail.com">eliot.miranda@gmail.com</a>>> wrote:<br>
>>>><br>
>>>> Instead we can use three variables per index to implement an<br>
>>>> exclusion-free solution, thusly:<br>
>>>><br>
>>>> typedef struct { int lock; // accessed via e.g. XCHG to protect<br>
>>>> signalRequest<br>
>>>> int requests;<br>
>>>> int responses;<br>
>>>> } ExternalSignalRequest;<br>
>>>><br>
>>>> ExternalSignalRequest *externalSignalRequests;<br>
>>>> int checkExternalSignalRequests;<br>
>>>><br>
>>>> void<br>
>>>> requestSignal(int i)<br>
>>>> {<br>
>>>> while (!lock(&externalSignalRequests[i].lock))<br>
>>>> usleep(1);<br>
>>>><br>
>>>> ++externalSignalRequests[i].requests;<br>
>>>><br>
>>>> unlock(&externalSignalRequests[i].lock);<br>
>>>><br>
>>>> checkExternalSignalRequests = 1;<br>
>>>> forceInterruptCheck(); // set a flag to cause the VM to<br>
>>>> check for interrupts; in the stack VM this is stackLimit :=<br>
>>>> (usqInt)-1;<br>
>>>> }<br>
>>>><br>
>>>><br>
>>>> The VM responds in checkEvents:<br>
>>>><br>
>>>> if (checkExternalSignalRequests)<br>
>>>> for (i = 0; i < numExternalSemaphores; i++)<br>
>>>> while (externalSignalRequests[i]. responses<br>
>>>> != externalSignalRequests[i]. requests) {<br>
>>>> signalSemaphoreWithIndex(i);<br>
>>>> externalSignalRequests[i]. responses;<br>
>>>> }<br>
>>>><br>
>>>><br>
>>> Am I correct that ExternalSignalRequest.reponses is never reset to zero,<br>
>>> instead eventually wrapping around? That worried me for a minute, but I<br>
>>> see that it doesn't matter. Neeto.<br>
>>><br>
>>><br>
>><br>
>> Nope, it does resets the counters.. see signalExternalSemaphores method.<br>
>><br>
><br>
> I was responding to Eliot's proposal, not the existing code. If I<br>
> understand properly, he's proposing to maintain a per-semaphore count of<br>
> signal requests/responses, so there would be no<br>
> "semaphoresToSignalCountA/B".<br>
><br>
</div></div>Ah.. sorry for not reading carefully..<br>
In proposed scenario i don't like 1 (one) thing, that checkForInterrupts will<br>
spend a linear amount of time to check what semaphores need to be signaled<br>
instead of spending linear amount of time to signal semaphores which<br>
is to be signaled:<br>
<div class="im"><br>
for (i = 0; i < numExternalSemaphores; i++)<br>
<br>
</div>means, that if you having 1000 external semaphores, and only 1 of them<br>
signaled currently, you have to<br>
loop through all of them, inevitably :(<br></blockquote><div><br></div><div>Yes, that caused a twinge. Bit with a separate lock we can maintain high and low tides, e.g.</div><div><br></div><div><span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; border-collapse: collapse; "><div>
typedef struct { int lock; // accessed via e.g. XCHG to protect signalRequest</div><div> int requests;</div><div> int responses;</div><div> } ExternalSignalRequest;</div>
<div><br></div><div>ExternalSignalRequest *externalSignalRequests;</div><div>int checkExternalSignalRequests;</div><div>int tideLock = 0;</div><div>int useTideA = 1;</div><div>int lowTideA = (unsigned)-1 >> 1, highTideA = 0;</div>
<div>int lowTideB = (unsigned)-1 >> 1, highTideB = 0;</div><div><br></div><div>void</div><div>requestSignal(int i)</div><div>{</div><div> while (!lock(& tideLock))</div><div><div> usleep(1);</div>
<div><br></div></div><div> if (useTideA) {</div><div> if (lowTideA > i) lowTideA = i;</div><div> if (highTideA < i) highTideA = i);</div><div> }</div><div> else {</div><div><div>
if (lowTideB > i) lowTideB = i;</div><div> if (highTideB < i) highTideB = i);</div><div> }</div></div><div> </div><div> while (!lock(&externalSignalRequests[i].lock))</div><div>
usleep(1);</div><div><br></div><div> ++externalSignalRequests[i].requests;</div><div><br></div><div> unlock(&externalSignalRequests[i].lock);</div><div><br></div><div> checkExternalSignalRequests = 1;</div>
<div> forceInterruptCheck(); // set a flag to cause the VM to check for interrupts; in the stack VM this is stackLimit := (usqInt)-1;</div><div>}</div><div> </div><div><br></div><div>The VM responds in checkEvents:</div>
<div><br></div><div> if (checkExternalSignalRequests) {</div><div> checkExternalSignalRequests = 0; // forgot this in my first email</div><div> if (useTideA) {</div><div> useTideA = 0;</div><div> for (i = lowTideA; i < highTideA; i++)</div>
<div> while (externalSignalRequests[i]. responses != externalSignalRequests[i]. requests) {</div><div> signalSemaphoreWithIndex(i);</div><div> externalSignalRequests[i]. responses;</div>
<div> }</div><div> lowTideA = (unsigned)-1 >> 1, highTideA = 0;</div><div> }</div><div> else {</div><div> useTideA = 1;</div><div> for (i = lowTideB; i < highTideB; i++)</div>
<div> while (externalSignalRequests[i]. responses != externalSignalRequests[i]. requests) {</div><div> signalSemaphoreWithIndex(i);</div><div> externalSignalRequests[i]. responses;</div>
<div> }</div><div> lowTideB = (unsigned)-1 >> 1, highTideB = 0;</div><div> }</div></span></div><div> </div><div>and we should make <span class="Apple-style-span" style="font-family: arial, sans-serif; font-size: 13px; border-collapse: collapse; ">lowTideA = (unsigned)-1 >> 1, highTideA = 0; a macro, to avoid the duplication.</span></div>
<div><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;">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.</span></font></div>
<div><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;"><br></span></font></div><div><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;"><br>
</span></font></div><div><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;">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.</span></font></div>
<div><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;"><br></span></font></div><div><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;"><br>
</span></font></div><div><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;">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 :/</span></font></div>
<div><font class="Apple-style-span" face="arial, sans-serif"><span class="Apple-style-span" style="border-collapse: collapse;"><br></span></font></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<br>
> Cheers,<br>
<div><div></div><div class="h5">> Josh<br>
><br>
><br>
<br>
<br>
<br>
--<br>
Best regards,<br>
Igor Stasenko AKA sig.<br>
</div></div></blockquote></div><br>