[Stackless] Algorithm for Stackless Scheduler

Alberto Ganesh Barbati AlbertoBarbati at libero.it
Wed Nov 12 17:43:39 CET 2008


Jeff Senn ha scritto:
>
> Calling chan.receive/send() can remove the current tasklet from runnables
>   if nothing is "waiting at the other end" (the NEXT tasklet in runnables
>   is continued).
> 
>   OR (depending on the channel preference) continue in the caller
>   (inserting the sender/receiver at the "other end" onto runnables)
>   or rotate the head of runnables to the sender/receiver and pick up there.
> 

<disclaimer>I admit I didn't look at the Stackless code</disclaimer>

The "OR" step is not totally clear to me. If there is a tasklet "waiting
at the other end" such tasklet is necessarily blocked and so it's not in
runnables list. With "rotate and pick up from there" you mean it's added
at the end of the list and then the list is rotated? According to this
test program, it isn't so:

	from stackless import *

	ch = channel()

	def sender():
		print "before send"
		ch.send(None)
		print "after send"
		
	def receiver():
		print "before receive"
		ch.receive()
		print "after receive"
		
	def other():
		print "other"
		

	tasklet(receiver)()
	tasklet(sender)()
	tasklet(other)()

the output of this program is

	before receive     #1
	before send        #2
	after receive      #3
	other              #4
	after send         #5

After #1, the receiver tasklet blocks and is removed from the runnables
list. After #2, the call to send() adds the receiver tasklet back to
runnables list and immediately passes control to it (as shown by line
#3). However, #4 and #5 shows that the receiver tasklet is inserted
*before* the "other" tasklet.  In other words, the runnable list is:

 start: [receiver, sender, other]
 after receive(): [sender, other]
 after send(): [receiver, other, sender]

notice that an add at either end of the list followed by a rotation can
not transform [sender, other] into [receiver, other, sender].

It looks more as if receiver replaced sender at the beginning of the
list, while sender is moved to the end.

So, according to my experience, the send() algorithm is something like:

* if balance() >= 0: the tasklet blocks and is removed from the
runnables list

* if balance() < 0:

  * if preference() >= 0 (prefer sender or don't prefer anything): the
tasklet keeps running, one of the blocked receiver tasklets is added at
the end of the runnables list

  * if preference() < 0 (prefer receiver): the tasklet is moved to the
end of the runnables list. One of the blocked receiver tasklets is
inserted *at the beginning* of the runnables list and control passes
immediately to it.

Similarly for receive():

* if balance() <= 0: the tasklet blocks and is removed from the
runnables list

* if balance() > 0:

  * if preference() <= 0 (prefer receiver or don't prefer anything): the
tasklet keeps running, one of the blocked sender tasklets is added at
the end of the runnables list

  * if preference() > 0 (prefer sender): the tasklet is moved to the end
of the runnables list. One of the blocked sender tasklets is inserted
*at the beginning* of the runnables list and control passes immediately
to it.

Just my two eurocent,

Ganesh





More information about the Stackless mailing list