Simple Task Manager Idea

[SpyderTL]

So, I've started working on my first Task Manager, and I thought that I'd share my first idea for a simple round-robin task manager.

So, as a base design, I'm using the PIC timer IRQ 0 handler to switch from one task to the next. During a task switch, I'm pushing the CPU state to the stack (registers, flags, etc.), then swapping to the next task's stack, and pulling the CPU state from the new stack, and returning from the interrupt. (After acknowledging the PIC timer, of course.)

This is currently working with two tasks, and I'm storing the "sleeping" task's stack pointer in a fixed memory location.

So my next plan is to add multiple threads, and I was planning on using a dynamically sized list of addresses to store the stack pointers. But I've been thinking about trying a different approach, and "linking" the tasks together in a ring by storing the "next" task stack pointer at the top of the "sleeping" task stacks. For the currently running task, the "next" task will be stored in the fixed memory location mentioned above.

So the switch logic would be 1) push CPU state to stack, 2) get the "next" task stack pointer from fixed memory address and push it to the stack, 3) set SP to the "next" task stack pointer address, 4) pull the new "next" task stack pointer from the stack and store it in memory, 5) pull CPU state from stack, and return from the interrupt.

Assuming I can figure out the sequence of getting a new task into the ring, this should make for a stable task ring that I can use to run a large number of tasks. I could even have multiple rings to support different "priority levels", and/or multiple processors. You could even store even more information on the top of the stack, like task status, sleep time, etc.

Do you guys see any problems with this general approach? Is anyone else doing this in their system, and how well does it work?

Edit: It occurs to me now that the value stored for the "next" task stack pointer will be incorrect by the time that it rolls back around if the stack changes, so I think that I'll need to also store the "previous" task stack pointer in a fixed memory location, so that I can flip back and update the next task stack pointer to the new "current" task stack pointer address.

[embryo]

I could even have multiple rings to support different "priority levels", and/or multiple processors. You could even store even more information on the top of the stack, like task status, sleep time, etc.

For all the information above to be useful there should be some method (procedure) which is able to handle a logic behind the data. It means task switch code should be a bit more complex than just push and pull operations. So, I suggest you to create a method, which will be responsible for handling all required actions (except push and pull). And next there is an obvious idea of a class (code and data in one place), which can couple together a switch logic and all required information. And may be after switch requirements will grow it would be practical to create even more classes under some package with the common goal of the task switch.

[iansjack]

From what I understand, you are describing the "classic" way of handling tasks - linked lists of processes with a pointer to the running task. I would store the whole process structure in the linked list - register values, priorities, etc. You need to save and restore a lot of things when switching tasks.

You might find it useful to read some books abot OS design as there are well-tested algorithms for common probems like this.

[Brendan]

Hi,

Some general notes...

I strongly recommend that you implement some kind of a "switch_to_task(task_ID)" function and make sure it works correctly before you write any code to determine which task to switch to when. This will become important later (when you decide to have task priorities); because when a higher priority task unblocks often you want it to preempt the currently running (lower priority) task immediately, and you can call the "switch_to_task(task_ID)" directly to achieve that (without any of the overhead involved in deciding which task to switch to when).

I also strongly recommend that you implement some kind of "find_task_to_switch_to(void)" function. This function does not care about "when", and does not do task switches itself (instead it uses the "switch_to_task(task_ID)" function). This is important because it's used every time the currently running task blocks (for e.g. if a task calls "sleep()" you need to find a different task to run). It also gives you a central place to change your scheduling algorithm (and you will want to do that sooner or later) that isn't complicated by unnecessary stuff (like timers and the low level details of switching tasks).

The timer IRQ may just call the "find_task_to_switch_to(void)" regularly (after waking up any sleeping tasks that should be woken). Of course on real systems, there are typically very few CPU bound tasks, and therefore most task switches are caused by tasks blocking and unblocking where the timer isn't involved at all. For this reason it's probably a good idea for the timer IRQ handler to check if a task switch has already happened recently and avoid calling "find_task_to_switch_to(void)" if it has. If you don't do this, then the scheduler may do a task switch for any other reason, and before that task has had a chance to get anything done the timer IRQ will fire and cause a second/unnecessary task switch.

Typically you have some sort of structure for each task (e.g. a "thread control block") that keeps track of various things, like how much CPU time it has consumed, who its parent process is, an area for saving its FPU/MMX/SSE/AVX state, the thread's kernel stack, etc. It's a good idea to include a "next" field in this structure (and possibly a "previous" field, if you actually need it). That way it's easy to create "linked lists of thread control blocks" and other things that your scheduler (and IPC, and file IO, etc) will need.

For round-robin, you only need a singly linked list (e.g. you don't need a "previous"). Please note that there will be "ready to run" threads, and one "running" thread. When a task is given CPU time it stops being "ready to run" (and is taken off of the start of the linked list) and becomes "running". When a task stops using CPU time it stops being "running" and becomes "ready to run" (and is put back onto the linked list at the end).

Be warned that round-robin is extremely bad for latency. For example, if you've got one important task (e.g. a GUI or application that needs to respond to a mouse click or key press ASAP, or almost anything that uses networking and needs to respond to packet/s fast) plus 50 other "less important" tasks that don't matter so much, then that important task may have to wait for "50 * time slice" seconds before it gets any CPU time. It can (and will) make your applications and networking seem "unusable and sluggish" under load.

Note: it is possible to avoid "unusable and sluggish under load" by placing tasks at the start of the "ready to run" linked list when they are unblocked. This is a tempting mistake. If you do this tasks will abuse it by doing something like "sleep(0)" to get put back at the start of the list and hog 100% of all CPU time.

For sleeping threads, it's possibly best to have one linked list for each "time bucket". For example, if your timer IRQ occurs every 10 ms, then you might have 1024 buckets and do "bucket = (wake_time / 10ms) % 1024" to determine which bucket to put the thread in. Every 10 ms you'd take the list from the next bucket, iterate through it and for each task on the linked list either put it back in the bucket or wake it up. This is relatively simple (no messy sorting or trees or anything). For this you can do it with singly linked lists; however, if it's possible for the time delay to be cancelled (which is likely) then you need a way to remove a task from a linked list, and with only a singly linked list you'd have to search the linked list to do that. For this reason (cancelling time delays) you'd probably want a doubly linked list (and a "previous" field in the "thread control block").

Note: later on if you decide to go "tickless" you'd be able to keep most of the code, but (instead of waking tasks up every 10 ms) you'd sort the tasks that should be woken up in the next 10 ms (and only those tasks) and then set your timer to fire when the "soonest" is due to be woken up. This helps avoid sorting overhead, especially for networking where a lot of time-outs are used (and are nearly always cancelled before you bother doing any sorting).


Cheers,

Brendan

[SpyderTL]

Okay, let's say that I want to write a simple, "working" task switcher / round-robin scheduler in as few lines/instructions as possible.

By pushing all of the "sleeping" task information that I need (next task stack pointer) onto the tasks stack before switching, I don't technically need a full list of tasks, or a separate linked list of task information. All I would need is a temporary storage area to put the next task stack pointer while the task is running. (And maybe the previous task SP for the reason mentioned above.)

There is also a special case where there is only one task running where you don't want to update the previous task's next pointer, because it has already been updated.

My question is, does anyone see a reason that this would not work, and has anyone tried this approach?

[alexfru]

You have already been told that this is a very general and common way to implement a task manager. It's been done numerous times and must work.

Indeed, saving most of the context on the stack (with push instructions or equivalent) and only storing the stack pointer is sufficient in simple cases. However, as the system becomes more complete, you'll need to store various bits of data associated with every task, not just the stack pointer. Consider the following:
- task ID
- parent task ID and the like
- task address space, e.g. CR3 (if each can have its own)
- task priority and related stuff
- task privileges
- task resources (e.g. current directory, file handles, language)
- etc
You will want to access these bits of data in a convenient way and so instead of just storing the stack pointer in some kind of a list, you'd need at least one structure containing the above info (possibly as pointers to other structures) and the stack pointer. And you'd store the pointer to this structure where you're now planning to store xSP.

Other things to consider:
- there must always be at least one runnable task in the system so the system has some code to run (it can't run nothing) when there are no other tasks or all are blocked and can't run
- if you decide to support priorities or something related to them, read up on starvation, deadlocks/livelocks (+discovery and prevention), priority inversion and fairness as things aren't as simple as they might seem at first