<html><body><div style="color:#000; background-color:#fff; font-family:times new roman, new york, times, serif;font-size:12pt"><br><div id="yiv1190869783"><div><div style="color:#000;background-color:#fff;font-family:times new roman, new york, times, serif;font-size:12pt;"><div id="yiv1190869783yui_3_2_0_34_133623272320248"><span id="yiv1190869783yui_3_2_0_34_133623272320280">Hi Armin:</span><span><br></span></div><div id="yiv1190869783yui_3_2_0_34_133623272320248"><span id="yiv1190869783yui_3_2_0_34_133623272320288"><br></span></div><div id="yiv1190869783yui_3_2_0_34_133623272320248"><span id="yiv1190869783yui_3_2_0_34_133623272320293">Thanks for the explanation. Sorry for taking so long to respond. This is a challenging post. Comments below:<br></span></div><div id="yiv1190869783yui_3_2_0_34_133623272320248"><span style="font-size:12pt;" id="yiv1190869783yui_3_2_0_34_1336232723202250"><br></span></div><div
id="yiv1190869783yui_3_2_0_34_1336232723202207"><br id="yiv1190869783yui_3_2_0_34_133623272320251"></div> <div style="font-family:times new roman, new york, times, serif;font-size:12pt;" id="yiv1190869783yui_3_2_0_34_133623272320256" class="yiv1190869783yui_3_2_0_34_133623272320254"> <div style="font-family:times new roman, new york, times, serif;font-size:12pt;" class="yiv1190869783yui_3_2_0_34_133623272320261" id="yiv1190869783yui_3_2_0_34_1336232723202100"> <div dir="ltr"> <font id="yiv1190869783yui_3_2_0_34_1336232723202206" face="Arial" size="2"> <hr size="1"> <b><span style="font-weight:bold;" id="yiv1190869783yui_3_2_0_34_1336232723202203">From:</span></b> Armin Rigo <arigo@tunes.org><br> <b><span style="font-weight:bold;" id="yiv1190869783yui_3_2_0_34_1336232723202198">To:</span></b> Andrew Francis <andrewfr_ice@yahoo.com> <br><b><span style="font-weight:bold;" id="yiv1190869783yui_3_2_0_34_1336232723202193">Cc:</span></b> Py Py
Developer Mailing List <pypy-dev@python.org> <br> <b><span style="font-weight:bold;" id="yiv1190869783yui_3_2_0_34_1336232723202188">Sent:</span></b> Thursday, April 19, 2012 3:37 PM<br> <b><span style="font-weight:bold;" id="yiv1190869783yui_3_2_0_34_1336232723202183">Subject:</span></b> Re: Question about stm_descriptor_init(), tasklets and OS threads<br> </font> </div> <br>
Hi Andrew,<br><br>On Thu, Apr 19, 2012 at 19:43, Andrew Francis <<a rel="nofollow" ymailto="mailto:andrewfr_ice@yahoo.com" target="_blank" href="mailto:andrewfr_ice@yahoo.com">andrewfr_ice@yahoo.com</a>> wrote:<br><br></div><div style="font-family:times new roman, new york, times, serif;font-size:12pt;" class="yiv1190869783yui_3_2_0_34_133623272320261" id="yiv1190869783yui_3_2_0_34_1336232723202100">AF> I am trying to understand enough to get into a position to attempt an<br>AF> integration.<br><br>>I believe you are trying to approach the problem from the bottom-most<br>>level up --- which is a fine way to approach problems; but in this<br>>case, you are missing that there are still a few levels between were<br>>you got so far and the destination, which is the <a rel="nofollow" target="_blank" href="http://stackless.py">stackless.py</a> module<br>>in pure Python.<br><br>Yes Armin, you are right: I am not treating the
transaction module as a black-box. <br>I'll try to think more abstractly.<br></div><div style="font-family:times new roman, new york, times, serif;font-size:12pt;" class="yiv1190869783yui_3_2_0_34_133623272320261" id="yiv1190869783yui_3_2_0_34_1336232723202100"><br></div><div style="font-family:times new roman, new york, times, serif;font-size:12pt;" class="yiv1190869783yui_3_2_0_34_133623272320261" id="yiv1190869783yui_3_2_0_34_1336232723202100">>Let us try to approach it top-down instead, because there are far less<br>>levels to dig through. The plan is to make any existing<br>>stackless-using program work on multiple cores. Take a random<br>>existing stackless example, and start to work by editing the
pure<br>>Python lib_pypy/stackless.py (or, at first, writing a new version from<br>>scratch, copying parts of the original). The idea is to use the<br>>"transaction" module. The goal would be to not use the _squeue, which<br>>is a deque of pending tasklets, but instead to add pending tasklets<br>>with transaction.add(callback). Note how the notion of tasklets in<br>>the _squeue (which offers some specific order) is replaced by the<br>>notion of which callbacks have been added. See below for what is in<br>>each callback.<br><br>>The transaction.run() would occur in the main program, directly called<br>>by stackless.schedule(). So the callbacks are all invoked in the main<br>>program too; in fact all the "transaction" dispatching is done in the<br>>main program, and only scheduling new tasklets can occur anywhere.<br><br>I see the transaction module and the scheduler's operation to be
orthogonal. <br></div><div style="font-family:times new roman, new york, times, serif;font-size:12pt;" class="yiv1190869783yui_3_2_0_34_133623272320261" id="yiv1190869783yui_3_2_0_34_1336232723202100"><br>It has been my contention that the Stackless scheduler (at least in cooperative mode)<br>is a rather dumb mechanism. The scheduler is dumb in the sense that there really isn't much<br>scheduling priority smarts in it. Rather scheduling/priority decisions resides in the tasklet <span style="font-size:12pt;" id="yiv1190869783yui_3_2_0_34_1336232723202349"><br>and the </span><span style="font-size:12pt;" id="yiv1190869783yui_3_2_0_34_1336232723202354">channels. <br><br>(Some side notes: 1) in the original Plan9 literature, the scheduler is opaque. 2) View the<br>scheduler as being re-entrant rather than an distinct process.)<br><br>This division actually makes Stackless quite flexible. For instance, when I implemented<br>select(), </span><span
style="font-size:12pt;" id="yiv1190869783yui_3_2_0_34_1336232723202411">a new mechanism was introduced: a chanop (this comes straight out of the<br>Plan9/Go implementation). Later, chanops were generalized into guards.</span> Guards serve as <br>the building blocks complex mechanisms such as channels and join patterns. The scheduler<br>was not touched. Also join patterns implement a trivial form of all-or-nothing semantics <br>(but there is no retry).<br><br>Based on what you have said, I strongly suspect the transaction module could be integrated into <br>Stackless (via stackless.py) in a similar fashion. In short, one does not touch the scheduler. <br>However the transaction module would use the scheduler.<br><br>>The callbacks would just contain a switch to the tasklet. When the<br>>tasklet comes back, if it is not finished, re-add() it. This is all.<br><br>Side note - in a way, this is how the non-preemptive scheduler works.
However<br>this is C based Stackless Python.<br><br>>You have to make sure that all tasklet.switch()es internally go back<br>>to the main program, and not directly to another tasklet. This should<br>>ensure
that the duration of every transaction is exactly the time in a<br>>tasklet between two calls to switch().<br><br>I am having problems understanding this passage. Perhaps I view<br>transactions and context switching as orthogonal. Yes the transaction <br>module's control of context switching could be a part of a strategy <br>for ensuring atomicity. Yes context switching creates opportunities for <br>conflict/contention (this is what causes race conditions). However<br>SME schemes can handle OS context switches.<br><br>>You have to make sure that all tasklet.switch()es internally go back<br>>to the main program, and not directly to another tasklet. <br><br>What is the main programme doing that makes it so special?<br>Is it some sort of synchronizer (a la Nancy Lynch's IO Automata model)?<br><br>As a side note, I recall reading in previous posts that the underlying ability<br>to jump directly to a tasklet makes pickling
difficult.<br><br>Also doesn't a main programme sort of suggests a generator/trampoline approach to <br>scheduling that wasn't necessary with tasklets and tasklets running over greenlets?<br><br>Maybe it is the way yield() is used in AME that causing me a bit of mental confusion?<br><br>>This should ensure
that the duration of every transaction is exactly the time in a<br>
>tasklet between two calls to switch().<br><br>This implies that context switches demarcate transaction boundaries. Context switches <br>in Stackless are very common. For instance channel operations often trigger a context <br>switch. Programmes voluntarily call schedule() to give other tasklets a chance to execute.<br><br>So in the case of:<br><br>def transfer(toAccount, fromAccount, amount):<br> # start of transaction<br> fromAccount.withdraw(amount)<br> stackless.schedule()<br> toAccount.deposit(amount)<br> #finish transaction<br><br>What would happen? In a normal Stackless Python programme, all other things being equal, the<br>stackless.schedule() opens up the door for race conditions and contention. Remove the stackless.schedule()<br>and that tasklet would operate very much like a transaction. I would suspect that if there was a
transaction <br>module present, in case of contention, it would about and re-try transfer(). Am I right in assuming this?<br><br>if we could imagine transfer() under the hood doing something like:<br><br>def transfer(toAccount, fromAccount, amount):<br> transaction.start() # NOTE THIS IS INVISIBLE TO THE PROGRAMMER!!!<br><br>it would not be difficult for the transaction module, if it sees another transaction in progress that would cause contention, to block transfer() by calling say, schedule_remove() and readding transfer() when appropriate.<br><br>>Of course, this can all be written and tested against<br>>"<a rel="nofollow" target="_blank" href="http://transaction.py">transaction.py</a>", the pure Python emulator. Once it is nicely<br>>working, you are done. You just have to wait for a<br>>continuation-capable version of pypy-stm; running the same program on<br>>it, you'll get
multi-core usage.<br><br>Once again, thank you for your response. I may be still unsure of some aspects. However I believe integration<br>ought to be much cleaner - no hacking/replacing the scheduler. <br><br>Cheers,<br>Andrew<br><br><br><br><br><br><br> </div> </div> </div></div></div></div></body></html>