stackless/microthread merge

[Will Ware]

At IPC8, I got the chance to talk to Christian Tismer, the author
of Stackless Python, about the possibility of using it as the basis
for implementing microthreads. (This is desirable because his
hacking of ceval.c was much tidier and better thought-out than mine.)
He suggested that with a stackless build, it should be possible to
implement microthreads entirely in Python.

It is, with one caveat: My earlier implementation looked to the
user like pre-emptive task-switching, which I accomplished by stepping
Python's VM a few opcodes at a time. If I resist the temptation to do
damage in ceval.c, task-switching must be explicit in the user's Python
code, esp. in potentially infinite loops that might block all other
threads. For the time being I regard that as a reasonable price for
leaving all the really hard work to Christian.

For Unix/Linux folks who have been looking for Stackless Python and
finding only Windows versions, I have posted a source tree at
ftp://ftp.std.com/pub/wware/spc152.tgz. It builds on my SunOS box at
work, and appears to work there. I make no other promises for it.

Anyway, on to the microthreads. (The stuff with semaphores is still
badly broken, please ignore it. Thank you.)

====================================================================

"""
Return of the Undead Microthreads
Will Ware, Leap Day 2000

This is an implementation of microthreads built on top of Stackless
Python, which is really the right way to do it. There is one remaining
glitch: task switching is not pre-emptive. Functions must explicitly
yield the processor by calling the "step" method of their threads, and
any infinite loop that doesn't yield will block all the other threads.

In the earlier implementation of microthreads, I dove into ceval.c and
effectively played with "ticker" (actually wastefully invented my own
roughly equivalent counter) and that gave me apparently pre-emptive
task-switching. Stackless Python is so thoroughly inscrutable that I
don't dare to try that now.
"""

import continuation

ZombieError = 'zombie microthread error'
NeverHappensError = 'I believe this never really happens'

class Thread:
    def __init__(self, func, *args, **kw):
        self.func = func
        self.args = args
        self.kw = kw
        self.done = 0
        self.killed = 0
	self.future = self._start

    def _start(self, dummy=None):
        if not self.killed:
            try:
                apply(self.func, (self,) + self.args, self.kw)
                raise ZombieError
            finally:
		if self.killed:
		    raise NeverHappensError
		# Do we really need this??
		# hold = self.func, self.args
		# self.__dict__.clear()
		# self.func, self.args = hold
		self.killed = 1

    def step(self):
        if self.killed:
	    raise ZombieError
	future = self.future
	self.future = continuation.caller()
        future()

class Swarm:
    # a bunch of threads
    def __init__(self):
	self.threadlist = [ ]

    def _one_step(self):
	first = self.threadlist[0]
	self.threadlist = self.threadlist[1:]
	try:
	    first.step()
	    self.threadlist.append(first)
	except ZombieError:
	    pass
    def step(self, n=1):
	while 1:
	    if n <= 0:
		return 1
	    if len(self.threadlist) == 0:
		return 0
	    self._one_step()
	    n = n - 1
    def finish(self):
	while self.step(100):
	    pass

class Blockable:
    def __init__(self, swarm):
	self.swarm = swarm
	self.wakelist = [ ]
    def block(self, thread):
	self.wakelist.append(thread)
	print thread, 'blocked'
	# make the swarm ignore this thread til it wakes again
	raise ZombieError
    def awaken(self, n=1):
	# use n = -1 to awaken everybody who is asleep
	while n != 0 and len(self.wakelist) > 0:
	    z = self.wakelist[0]
	    print z, 'awoken'
	    self.wakelist = self.wakelist[1:]
	    self.swarm.threadlist.append(z)
	    n = n - 1

class Semaphore(Blockable):
    def __init__(self, swarm, n=1):
	Blockable.__init__(self, swarm)
	self.count = n
    def claim(self, thread):
	if self.count < 0:
	    raise 'OUCH!'
	if self.count == 0:
	    self.block(thread)
	self.count = self.count - 1
	thread.step()
    def release(self):
	if self.count == 0:
	    self.awaken()
	self.count = self.count + 1

# # # # # # # # # # # # # #

import random

def factorialTest():
    sw = Swarm()
    for i in range(40):

	def factorial(th, n):
	    prod = 1L
	    for i in range(2, n):
		prod = prod * i
		th.step()
	    print n, prod

	th = Thread(factorial, int(100 * random.random()))
	sw.threadlist.append(th)
    sw.finish()

""" Semaphores obviously need a lot of work, but this is a rough
idea of what to do. Currently, blocked threads terminate prematurely
and I dunno why. """

def semaphoreTest():
    sw = Swarm()
    sem = Semaphore(sw)
    N = 5
    class IdThread(Thread):
	def __init__(self,func,sem,letter):
	    Thread.__init__(self,func,sem)
	    self.letter = letter
	def __repr__(self):
	    return '<Thread %s>' % self.letter
	def _start(self, dummy=None):
	    if not self.killed:
		try:
		    apply(self.func, (self,) + self.args, self.kw)
		    raise ZombieError
		finally:
		    print self, 'terminating'
		    self.killed = 1
    def task(th, sem):
	for i in range(6):
	    print th, i, 'claiming'
	    sem.claim(th)
	    print th, i, 'got it'
	    sem.release()
	    print th, i, 'released it'
    for i in range(N):
	th = IdThread(task, sem, chr(ord('A') + i))
	sw.threadlist.append(th)
    sw.finish()

if __name__ == '__main__':
    factorialTest()

======================================================================
-- 
 - - - - - - - - - - - - - - - - - - - - - - - -
Resistance is futile. Capacitance is efficacious.
Will Ware	email:    wware @ world.std.com