The basic unit of scheduling is a thread. A thread is really nothing more than a kernel stack. All thread data block lives in the beginning of the stack space (like in Linux). The stack-pointer of inactive stacks is the first field of the thread data. Stacks are switched directly with a cpu_switch_task(old,new) function. Initially thought about setjmp()/longjmp() but thought that was just extra complexity.
The threads are completely kernel-level things; the datablock contains no fields for any userlevel stuff (except pointer to process). When a trap/interrupt occurs from userspace, the ESP is set (by hardware) to the end (bottom) of the kernel threads stack, the entry-code allocates from stack an user_registers structure by pushing the registers, and passes a pointer as argument to whatever C function was registered with the trap.
On return to userspace, the registers are popped again from the stack, or a specially requested area; the initial user_registers can be anywhere in stack when the thread first enters userspace.
Thread datablocks are linked directly into queues, and queues themselves are basic doubly-linked lists. There are two types of queues: the general thread_queue type, and timer's internal queues. Each thread can be queued (at one time) in one normal queue, and one timer-queue. More of the timers later.
Scheduler itself is basic FIFO priority scheduler; there's one thread_queue per priority level, and on scheduler_run(), the first thread from the highest-priority (non-empty) queue is removed from the queue, and it's stack switched to current. Scheduler keeps track of current threads with a array (one pointer per CPU). After switching stack, the (new) thread's status field is read, and returned as the result of the scheduler_run() call.
Similarly, semaphores contain a queue (could be extended to have priorities too, but I thought that's unnecessary), into which threads are inserted before calling scheduler_run(). Semaphores are the only thing (internally anyway) you can wait on. If one wants to wait for multiple objects, then those multiple objects can be redirected to post() on a single semaphore.
There are two complications to this basic model: interruptions and timers. The interruptions are simple: simply check if the thread is queued somewhere (in a wait-queue). If so, then the thread is removed from that queue, and inserted into the correct runqueue, and it's status is set to ERROR_INTERRUPTED.
Timers act the same but they are managed from timer interrupts. Each thread has a "fire time" (if the timer is active) and when the current "ticktime" is the same as the "fire time", the thread is interrupted (with ERROR_TIMER instead). A reschedule is forced if the priority is higher.
Now, by using double-linked list for the queues (no need for malloc though, because a threads is only in 1+1 queues), all operations are constant time, except timer interrupt handler. To make timer interrupt handling fast, there's a circular buffer of timer queues (currently 256). When a timer is set, the thread is put in timer_queue[fireoff % no_queues]. On each timer interrupt, ticktime is incremented, queue[ticktime % no_queues] is checked, and all threads with fireoff == ticktime are interrupted. The rest are simply skipped and left in the queue.
Now, while the above scheme does not make timer really constant time, it's quite efficient in any case. As long as all timers are shorter than no_queues * length_of_tick, the handler is linear in threads to be released! Obviously can't do better than that. For longer timers, we take a hit because we need to skip them, but at least they are distributed into the queues. This doesn't sound that great, but consider: my left of tick is 10ms -> with 256 queues, timers of less than 2.56 seconds cause no penalty!
I think I'm quite happy with this one. Oh, and sorry for the long post.
