<div dir="ltr">Hi Ben,<br><div class="gmail_extra"><br><br><div class="gmail_quote">On Wed, Mar 26, 2014 at 7:04 AM, Ben Coman <span dir="ltr"><<a href="mailto:btc@openinworld.com" target="_blank">btc@openinworld.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><u></u>
<div bgcolor="#ffffff" text="#000000"><div class="">
Eliot Miranda wrote:
<blockquote type="cite">
<div dir="ltr"><br>
<div class="gmail_extra"><br>
<br>
<div class="gmail_quote">On Tue, Mar 25, 2014 at 10:21 AM, Eliot
Miranda <span dir="ltr"><<a href="mailto:eliot.miranda@gmail.com" target="_blank">eliot.miranda@gmail.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);margin:0pt 0pt 0pt 0.8ex;padding-left:1ex">
<div dir="auto">
<div>Hi Igor,</div>
<div><br>
</div>
<div><br>
</div>
<div> you have a point but I disagree. The scheduler is defined
in the implementation section of the blue book. It could be more
explicit, but the blue book scheduler is a known and simple system. In
my threading work I've made sure to preserve its semantics (cooperative
within priorities, preemptive across priorities, thread switch at
activation of non-primitive sends and backward branches). The only
serious bug I know of (that preempting sends a process to the back of
its run-queue) was addressed in Cog and the VW VM. We can and should
write up the semantics, but they're not undefined, they're simple and
they do work.<br>
</div>
</div>
</blockquote>
<div> </div>
<div>Oops. I lie. There is a serious bug with
Semaphore>>critical: and the like. There's a suspension point
after signal and before block evaluation that can result in deadlock if
a higher priority process signals the semaphore. Since the higher
priority process is running the lower priority process never makes
progress to run the ensure block or cvlear the flag or whatever it
needs to do, and hence the system deadlocks. This requires thought ;-)
So I do know of one outstanding bug.</div>
</div>
</div>
</div>
</blockquote></div>
My grasp of concurrency controls hasn't been tested in 20 years, so
naively I would say: If a lower priority process "L" holds** a
semaphore when the higher priority process "H" signals the semaphore,
temporarily raise the priority of the "L", or temporarily lower the
priority of "H". Is there something simple that I missing?<br></div></blockquote><div><br></div><div>There are a couple of obvious solutions. One is to avoid the suspension point somehow, another is adding priority inversion. Adding priority inversion to the scheduler is a significant change which would increase complexity. You yourself have glossed over detail by saying "temporarily". I've glossed over a lot with "somehow". How would these "temporarily"s and "somehow"s be implemented? Your design sketches are appreciated.</div>
<div><br></div><div>cc'ing vm-dev and squeak dev lists. this is an important discussion.</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div bgcolor="#ffffff" text="#000000">
<br>
cheers -ben<div><div class="h5"><br>
<br>
<blockquote type="cite">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
<blockquote class="gmail_quote" style="border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);margin:0pt 0pt 0pt 0.8ex;padding-left:1ex">
<div dir="auto">
<div><br>
Eliot (phone)</div>
<div>
<div>
<div><br>
On Mar 25, 2014, at 10:11 AM, Igor Stasenko <<a href="mailto:siguctua@gmail.com" target="_blank">siguctua@gmail.com</a>>
wrote:<br>
<br>
</div>
<blockquote type="cite">
<div>
<div dir="ltr"><br>
<div class="gmail_extra"><br>
<br>
<div class="gmail_quote">On 25 March 2014 17:31, Eliot Miranda <span dir="ltr"><<a href="mailto:eliot.miranda@gmail.com" target="_blank">eliot.miranda@gmail.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);margin:0pt 0pt 0pt 0.8ex;padding-left:1ex">
<div dir="ltr">Hi Igor,
<div class="gmail_extra"><br>
<br>
<div class="gmail_quote">
<div>
<div>On Tue, Mar 25, 2014 at 5:05 AM, Igor Stasenko <span dir="ltr"><<a href="mailto:siguctua@gmail.com" target="_blank">siguctua@gmail.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);margin:0pt 0pt 0pt 0.8ex;padding-left:1ex">
<div dir="ltr"><br>
<div class="gmail_extra">
<div>
<div><br>
<br>
<div class="gmail_quote">On 24 March 2014 22:54, <a href="mailto:phil@highoctane.be" target="_blank">phil@highoctane.be</a>
<span dir="ltr"><<a href="mailto:phil@highoctane.be" target="_blank">phil@highoctane.be</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);margin:0pt 0pt 0pt 0.8ex;padding-left:1ex">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div>
<div>On Mon, Mar 24, 2014 at 8:23 PM, Alexandre Bergel <span dir="ltr"><<a href="mailto:alexandre.bergel@me.com" target="_blank">alexandre.bergel@me.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);margin:0px 0px 0px 0.8ex;padding-left:1ex">>>
I am working on a memory model for expandable collection in Pharo.
Currently, OrderedCollection, Dictionary and other expandable
collections use a internal array to store their data. My new collection
library recycle these array instead of letting the garbage collector
dispose them. I simply insert the arrays in an ordered collection when
an array is not necessary anymore. And I remove one when I need one.<br>
><br>
> Hm, is that really going to be worth the trouble?<br>
<br>
This technique reduces the consumption of about 15% of memory.<br>
<br>
>> At the end, #add: and #remove: are performed on these polls
of arrays. I haven’t been able to spot any problem regarding
concurrency and I made no effort in preventing them. I have a simple
global collection and each call site of "OrderedCollection new” can
pick an element of my global collection.<br>
>><br>
>> I have the impression that I simply need to guard the access
to the global poll, which is basically guarding #add: #remove: and
#includes:<br>
><br>
> One of the AtomicCollections might be the right things for you?<br>
<br>
I will have a look at it.<br>
<br>
>> What is funny, is that I did not care at all about
multi-threading and concurrency, and I have not spotted any problem so
far.<br>
><br>
> There isn’t any ‘multi-threading’ like in Java, you got a much
more control version: cooperative on the same priority, preemptive
between priorities.<br>
> So, I am not surprised. And well, these operations are likely not
to be problematic when they are racy, except when the underling data
structure could get into an inconsistent state itself. The overall
operations (adding/removing/searing) are racy on the application level
anyway.<br>
><br>
> However, much more interesting would be to know what kind of
benefit do you see for such reuse?<br>
> And especially, with Spur around the corner, will it still pay off
then? Or is it an application-specific optimization?<br>
<br>
I am exploring a new design of the collection library of Pharo. Not all
the (academic) ideas will be worth porting into the mainstream of
Pharo. But some of them yes.<br>
<br>
Thanks for all your help guys! You’re great!<br>
<br>
Cheers,<br>
Alexandre<br>
<span><font color="#888888"><br>
--<br>
_,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:<br>
Alexandre Bergel <a href="http://www.bergel.eu" target="_blank">http://www.bergel.eu</a><br>
^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.<br>
<br>
<br>
<br>
</font></span></blockquote>
<div><br>
</div>
</div>
</div>
<div>An interesting method I stumbled upon which may help
in understanding how these things do work. </div>
<div><br>
</div>
<div>BlockClosure>>valueUnpreemptively</div>
<div>
<span> </span>"Evaluate the receiver (block),
without the possibility of preemption by higher priority processes. Use
this facility VERY sparingly!"</div>
<div><span> </span>"Think about using
Block>>valueUninterruptably first, and think about using
Semaphore>>critical: before that, and think about redesigning
your application even before that! </div>
<div><span> </span>After you've done all that
thinking, go right ahead and use it..."</div>
<div><span> </span>| activeProcess oldPriority
result semaphore |</div>
<div><span> </span>activeProcess := Processor
activeProcess.</div>
<div><span> </span>oldPriority := activeProcess
priority.</div>
<div><span> </span>activeProcess priority:
Processor highestPriority.</div>
<div><span> </span>result := self ensure:
[activeProcess priority: oldPriority]. </div>
</div>
<br>
</div>
</div>
</blockquote>
</div>
<br>
</div>
</div>
I would not recommend you to use this method for anything.<br>
</div>
<div class="gmail_extra">This method heavily relies on how
process scheduler works, and in case of any changes, it may break
everything.<br>
</div>
<div class="gmail_extra">For the sake of programming, one
shall never assume there is a way to "stop the world while i busy doing
something".</div>
</div>
</blockquote>
<div><br>
</div>
</div>
</div>
<div>Really? Surely any system as interactive as Smalltalk can
benefit from a stop-the-rest-of-the-world scheduling facility, and
surely packaging it as BlockClosure>>valueUnpreemptively would be
a convenient way of doing so. Surely the right attitude for an
implementor of a threading system for Smalltalk would be "Sure, I can
implement that, even in a truly concurrent, multi-processor
environment". It may take some doing but it's an important facility to
have. It shouldn't be abused, but when you need it, you need it.</div>
<span><font color="#888888">
</font></span></div>
<span><font color="#888888">
<div><br>
</div>
</font></span></div>
</div>
</blockquote>
<div><br>
There should be hard guarantees from VM to do it. Right now there's
none. That's my point.<br>
Like special primitive(s) for disabling interrupts/scheduling and
enabling it back again.<br>
</div>
<div>Let us be realistic: the above implementation is based on
insider's knowledge how scheduling works, lacking any notion of
contract between VM and image.<br>
</div>
<div>Right now it just based on implementation detail rather than
on guaranteed and well defined semantic. <br>
</div>
<div> <br>
</div>
It is no doubt, sometimes you may need such hammer to stop the world. <br>
And it is no doubt (to me) that one should avoid using it unless it is
impossible to do otherwise.<br>
<br>
</div>
<div class="gmail_quote">
<div> </div>
<blockquote class="gmail_quote" style="border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);margin:0pt 0pt 0pt 0.8ex;padding-left:1ex">
<div dir="ltr">
<div class="gmail_extra"><span><font color="#888888">
<div></div>
-- <br>
best,
<div>Eliot</div>
</font></span></div>
</div>
</blockquote>
</div>
<br>
<br clear="all">
<br>
-- <br>
Best regards,<br>
Igor Stasenko.
</div>
</div>
</div>
</blockquote>
</div>
</div>
</div>
</blockquote>
</div>
<br>
<br clear="all">
<div><br>
</div>
-- <br>
best,
<div>Eliot</div>
</div>
</div>
</blockquote>
<br>
</div></div></div>
</blockquote></div><br><br clear="all"><div><br></div>-- <br>best,<div>Eliot</div>
</div></div>