OSDev.org

I read a few topics about Cooperative Multitasking(CM) on OSDev.
The final word about CM was that it was much worse than Preemptive Multitasking(PM), because in case of CM, a wrongly written task can drag the whole OS down since it won't call the task-switching function (e.g. PAUSE in FORTH).
I am developing an OS that has CM, and I can kill tasks by pressing Ctrl-C. The only drawback is that it requires human interaction, but it would be possible to add a timer that kills the current task if it has been running for e.g. 2 seconds.

In my opinion the current general opinion about CM is not completely correct.
There are many good points of a CM (e.g. context-swiching is easy/simple/fast compared to that of PM).

EDIT: it is an advantage of CM, that the OS will know e.g. after 2 seconds that the task is in a forever loop.
It wouldn't be this easy in case of PM.


----------------------------------------------------------
FORTH Operating System
https://sites.google.com/site/forthoperatingsystem/

Yes, or like a timer that interrupts the task like 20 times per second.

You have to support interrupts, interrupts have to keep the state of the running process intack. Context switching is nothing but loading a different state that what was interrupted. In my OS that happens when the scheduler updates virtual memory mappings. The OS always stores and restores interrupted state from a fixed address (just as your CM kernel will do).

If you are into that sort of things, you can enforce a watchdog call that has to occur after every second of processor time.. Don't see how that's different..

Checking every 2 seconds if there has been a task-switch is not the same as doing context-switch in the timer-irq 1000 times per second.
In case of a task in forever loop, the OS calls the task-switcher (PAUSE in Forth) after the 2 seconds.
I think it is completely different from PM but I can be wrong

EDIT: it is FORTH, so it would work well because of the stacks (parameter, return and float). Those get switched during the task switch.

Hi,



Most tasks are either CPU bound (e.g. do massive amounts of processing) or IO bound (e.g. spending most of their time waiting for a keypress or packet or something). For CPU bound tasks cooperative scheduling is completely broken (because they don't release the CPU), and for IO bound tasks cooperative scheduling is completely broken (when the OS is under load, the amount of time between "whatever task was waiting for has occurred" and "task actually gets CPU time" is far too long, causing severe latency problems for GUI, networking, etc).

In my opinion, for a well designed scheduler the goal is to ensure that all CPUs are doing the most important work at any time. If a scheduler fails to do that, then CPUs do unimportant work when they should be doing important work. How you define "important" is up to you, but regardless of how its defined it requires pre-emption.

Also note that while it might be simpler for a kernel to support cooperative scheduling, it's only simpler because all the complexity got shifted to user-space. Given that there's typically many applications and only one kernel, shifting complexity into all of the applications means that "simpler kernel" ends up making the system as a whole significantly more complex.


Cheers,

Brendan

Thanks, Brendan. I will think it over.
Another thing is that my OS runs on just one CPU(or core), so I have no idea how CM would perform if it run on several cores.
I am not even sure if I could do it (or if it is possible).

The problem with using time-outs to close hung programs in CM is that it relies on precisely the same interrupt mechanism that you are trying to avoid. Anyway, no matter how you handle interprocess scheduling, on an x86 system, you will still need to handle interrupts, in order to communicate with the peripheral hardware. Given that the mechanism needed to handle pre-emptive multitasking has to be there anyway, cooperative multitasking makes little sense.

Aside from this, the real issue with CM is trust. The system has to be able to trust that the user program does not hang, and that it is well-behaved (i.e., it regularly returns to the scheduler). The only really feasible approach to this is that used in Oberon: enforcing the context switch policy inside the compiler or interpreter. Note that a) this ran on specific hardware (or on a simulated p-machine, for the PC version) that was designed not to have any interrupt system, and so could work entirely through polling, and b) this can still fail if the program hangs for some other reason.

Cooperative multitasking doesn't make a lot of sense in the kernel, but in a userspace application it can be pretty effective. For something like an event-based network server you might have a single event loop thread implementing CM for handling requests, which eliminates a lot of error-prone and expensive synchronization, and then use threads for any heavy computation. It also makes sense in games, where you might use CM as a way to describe processes that happen over several frames.

The thing that makes these examples work is that you control all the "threads" so you don't have to worry about trust or accidental runaway threads.

I handle interrupts in my OS (not to mention that I have a timer with PIT and I can wake up sleeping tasks with it by changing their state in the data-structures of the tasks).
I save the contents of the registers to the stack with pushad and restore everything with popad.
At the end of the interrupt the task that was running before the interrupt will continue to run.
The stack is not switched in the interrupt as in the real scheduler (PAUSE).
I am still experimenting with my OS, but so far it has been working well.

Traditionally FORTH OSs are CMs and there are interrupts in those embedded systems as well.

This also answers to Rusky.

I can't confirm what Brendan said, because my OS is still a baby, but he is probably right.
On the other hand CM and interrupts work well together according to my experience.
I haven't emphasized it that I do CM with FORTH, and in FORTH words(i.e. small programs) communicate via stacks (parameter-, return-, float-stack).
In the timer-interrupt I watch for Ctrl-C keypress too and simply switch those three stacks by changing a few pointers (Ctrl-C sets the state of the current task to UNUSED to be exact).
It works well.

Maybe CM performs worse in non-FORTH OSs, I don't know.

Multi-core is still a problem, though, because in FORTH the dictionary should be accessed by only one task at a time (i.e. a task has to finish changing the dictionary, there can't be a task-switch in the middle, otherwise, the dictionary would be corrupted).

Hi,



For a single task (where scheduler becomes mostly irrelevant), for single-CPU (where things are far simpler), for a very limited number of simple devices (e.g. keyboard and text mode, where you don't have to worry about things like processing millions of pixels ASAP or handling a several thousand packets per second), without power management (where you shift and/or postpone work to reduce heat and/or increase battery life), without any advanced features like full virtual memory management (with memory mapped files, swap space, copy on write, etc) or prioritised IO (where you re-order things like disk reads/writes to improve performance for important things), and without any security (e.g. any user can trash anything); everything can seem like it works well regardless of how bad it is.

It's not until (e.g.) you're watching a movie in one window while writing a letter in another window while processing a lot of data in the background while the computer is handing HTTP/FTP/DHCP/whatever requests from all over the network while 7 of your 8 CPUs are unused/being wasted that you discover that one of the fundamental pieces of the OS has severe design flaws and the only way to get acceptable performance is to break behaviour that all existing software depends on.

And really, it's the "break behaviour that all existing software depends on" that you'd want worry about - it's the sort of thing that (in severe cases) can completely destroy many years of work. E.g. you change the way scheduling is done and realise file IO and GUI needs to be modified to work properly with the new scheduling, and then realise all the applications depend on the old scheduling, old file IO and old GUI, and then realise it's quicker/easier to rewrite all the applications.



For pre-emption; you'd just postpone task switches while the dictionary is being modified.

For multi-core there's other problems; like making sure other CPUs aren't reading from the dictionary while its being modified; and making sure that other CPUs (that were waiting while a modification were being done) see something consistent when the modification is completed. The thing I'd worry about the most is scalability (e.g. most CPUs wasting most of their time waiting to access the dictionary). I'd expect in a system like this (where all CPUs require frequent access to the same "globally shared but modified" data) that using 2 CPUs will only make things 50% faster than single CPU (and not twice as fast), and using 4 CPUs will only make things 10% faster than 2 CPUs (and not twice as fast), and using 8 CPUs will actually give worse performance than using 4 CPUs.

To make performance tolerable on modern (multi-core) computers, I'd avoid "frequent access to the same globally shared but modified data" completely by giving each CPU its own separate dictionary. However; this would mean each CPU is more like a separate computer; where different tasks running on different CPUs communicate with something more like networking than function calls; and this type of thing requires software designed specifically for "isolated pieces that communicate" to be effective.


Cheers,

Brendan

I might add that this is a fairly good description of the problems which arose in the most successful system to date to use CM, namely the original MacOS. While Multifinder ran in user space for years, it eventually became impossible to continue in that manner as both hardware and software began to change.

To add another viewpoint on this, I'm currently changing my OS rewrite over to being mostly cooperatively scheduled. The logic goes as follows:

- All non-batch systems have an event loop. Nearly all interesting applications are event loops on top of logic.
- All tasks can be split into constituent pieces, with implicit parallellization advantages (think futures / continuations). At any point in this you can instead do something else; the state is kept in something other than the stack.
- Given that you do this, you do not need a single thread. You don't even need a main entry point that does not return, or that's special somehow, other than having some mechanism to guarantee that your application isn't unloaded until it's done.
- Assuming that you have everything converted to giving you more or less futures instead of blocking, you can solve just about everything by attaching a continuation and doing your work there. This then means that the thing you're doing in any bit of code is sending requests and attaching continuations to be run when the requests complete. Whether it's a local request, RPC, waiting for disk block reads or waiting for the user to type a character is irrelevant - it's something you can attach a continuation to.
- Now that there are no threads and no blocking operations left, you don't need to preempt anything - just priority-schedule the rest cooperatively and you're pretty much done.

So that's the direction I'm in now. Currently the kernel itself halts and runs any pending task after interrupt. Interrupts can also create new tasks (which leads to interesting algorithms for that data structure - but that's a solved problem). The shell starts, registers itself for keyboard input and then returns. When a key is pressed, it processes it and decides what to do next, and then returns again. There's no need for the shell itself to have a thread, and so it doesn't.

This also leads to the very interesting result that while I'm using C++ RAII as much as I can - wrt stack-based ownership - I still have really small stacks everywhere that I have one to speak of, as no threads build up on a stack and no big tasks will create a big stack.

If anybody's interested in doing this as well I can recommend not doing it - there are so many new things in the context of everything-async that I'm hitting that I'm happy to be pretty familiar with driver development & osdev in general. I don't have a lot of time to work on it (kids) but that's OK as I often have to think for a few days about how to solve some details. Of course, unless you're really interested, in which case I wish you good luck

Or you use a dictionary per task. In general, preemptively multitasking OSs give the kernel its own runtime environment, and then give each task its own copy of the runtime environment.



Giving each task the illusion that it owns the whole computer was much of the motivation behind the initial development of such concepts as preemptive multitasking and virtual memory, so once again, don't just do one dictionary per core, do one dictionary per task.

In fact, I'd argue that an OS without preemption (especially if data that can influence the scheduler is globally accessible to applications due to missing/incomplete memory protection) is not a true multitasking system, and is more of a combination thread library / hardware access library for bare metal applications than it is an actual OS.

Interesting opinions.

I would like to summerize the positive aspects of CM:
- very fast context-switch
- no need for synchronization, since a task calls task-switching when it is the best for it (the control is not taken away in the middle of processing e.g. two DWORDs)

The negative ones are:
- CPU-bound, IO-bound tasks by Brendan, which I can't contest because my OS is still a baby. Although, I believe the problem of a task waiting for an IO in CM is similar to that of PM. A task can call a context-switch in CM if the IO hasn't arrived yet (but it is also up to the IO the task is waiting for)
- not real multitasking environment (well, it is called multitasking)
- Instead of synchronization, a task-switch (i.e. PAUSE) need to be called by every task at least once
- Problems with interrupts (I believe this is not a problem, FORTH systems are traditionally CMs and have interrupts. I also haven't had problems with it)
- [not CM but FORTH-related:] running a CM on several CPUs (cores)!? (does using a dictionary per CPU (or core) works fine? I don't know.
(or dictionary per task)

context switch itself is independent to which time sharing model you use.
I suppose you meant less context switch for CM, but then a preemptive model allowing thread to give up its time would be equally less switching for most situations.


Not true if there is concurrent threads on multiple cores.