Threads

This is a multi-threading system for the Z80 processor. It is mainly aimed at the TI-86 graphing calculator. However, it should work on any Z80-based computer, such as the TI-83(+), TI-84+, etc., with little or no change.

Goals

The goals of this library are:

Small code size and data use
Fast code execution
Simple design

Some of these goals can be at odds with each other. For example, fast execution could make the code larger and use more memory for data, because faster and more sophisticated algorithms generally need more code and data.

What am I to do? In particular, if I use a linked list to manage threads, my solution could be scaleable, possibly up to hundreds of threads with little problem. However, this requires more overhead in memory (e.g., memory allocation) and code (e.g., walking the list) than a simple fixed-size array.

Since my target use for these routines is in small programs with only several threads or less, I decided to use simple and small (albeit not scaleable) algorithms and data structures. For small programs, the constant overhead of a complicated algorithm outweighs the run-time of a brute-force algorithm.

To illustrate the difference this simplicity can make, my old cooperative threading library takes about 500 bytes (the exact figure escapes me) with all functions included. In contrast, my new threading library takes, as of this writing, 340 bytes. It even has all of the functionality of the old one, where it makes sense (it doesn't "suspend" threads the same way, so that's a little different).

My new library also has a cleaner method of suspending (sleeping) and unsuspending (waking) threads. This alone affects the speed at which a threaded program runs. In the old version, a thread would "suspend", meaning it would simply yield. The thread will be run again the next time around, so it has to check for a condition and suspend again if that condition is not met. In the new library, a thread "sleeps" on an event. Only when another thread "wakes" every thread sleeping on the event does the sleeping thread resume. It still must check for a condition and sleep again if it is not met, but this check happens only when the event actually occurs.

The meaning of "event" is slightly different than its usual meaning. In this threading library, an "event" is usually just a pointer (an address) to an object, and a thread can wait for something to happen to that object by calling th_sleep(&object). When something does happen to that object, a thread (usually) will call th_wake(&object), which will tell sleeping threads that something happened to that object. Those threads can then check for a condition and will possibly sleep on the object again.

One use of sleeping on events is a semaphore. When a thread wants to lock a semaphore, the thread sleeps on it while it is locked. If the semaphore is free, the thread locks it. When a thread frees a locked semaphore, it wakes every thread sleeping on it to tell them it's free. If multiple threads are waiting for the same semaphore, the first to run will get it, and the rest will have to wait longer.

Progress

I've implemented the following functions:

th_create(code, stack, argument): Creates a thread starting at code using stack. The thread will be given the one argument when it runs. The thread is ready to run when this returns.
th_cancel(thread): Cancels a running thread. The thread will not run anymore when this returns.
th_exit(status): Exits the current thread with an exit status. If this is the last thread, the program terminates.
th_join(thread): Waits for thread to end and returns its exit status.
th_sleep(event): Sleeps on event.
th_wake(event): Wakes up all threads that are sleeping on event.
th_yield(): Lets other threads run.
setjmp(jmp_buf): Saves the current execution context to jmp_buf and returns with carry clear (or carry set if it returns via longjmp; see longjmp, below).
longjmp(jmp_buf): Restores the execution context from jmp_buf and returns to the last point the context was saved with setjmp.
exit(status): Exits the program with status as its return value.

History

I started writing multi-threading routines for the TI-86 calculator some time during 2002 or 2003 (likely the end of 2002). Initially, I tried multi-threading without separate stacks (I did not understand the need for multiple stacks). Needless to say, it didn't work well. Then I figured out this problem and wrote a cooperative multi-threading library that uses a linked list to manage threads. I was learning how threads worked as I was writing it, so the library uses funky semantics for suspending threads. Some time later another person released his own preemptive multi-threading libary. Not to be outdone, I quickly modified my library to be preemptive as well. It didn't require a lot of changes, which is always a good thing. It still uses a linked list for threads, though.

On Sunday, November 19, 2006, I was designing a VT100 emulator that uses threads for a few functions. I was considering using protothreads, or a variation thereof for Z80 assembly. I even wrote a rudimentary version in Z80, but I figured that they would be difficult to use in a Z80 assembly program (they were designed for use in C, after all).

That same day, I wrote out some pseudo-code for a new threading library. When I had access to my computer, I wrote and debugged it in C in less than two hours. The C code doesn't actually switch threads because I couldn't figure out how to portably switch stacks in C.

The next day (Monday) I transliterated the core routines into Z80 assembly. I changed a test program (from the previous multi-threading libraries) to work with this one, then I ran it. It failed because the setjmp routine had one small (or big, depending on how you look at it) bug. After I fixed the bug, the code worked! Eureka!

On Tuesday (2006-11-21), I added and tested the rest of the routines. I still have a little more to clean up, optimize, and test before I feel comfortable unleashing it to the world. :D

Update (2007-04-30): I still haven't unleashed this to the world, but it's getting Real Close Now. I fixed some bugs and added a numthreads variable to keep track of the number of threads (so it can exit the program when numthreads = 0). I also added an argument that is passed to the thread when it starts. This is more consistent with POSIX threads.

Update (2007-05-02): I released th at ti-news.net.