5 ms·

Nice overview. Windows 1-3 used "non-premptive" or "cooperative" scheduling, which is why any process could hang the system. That method does have its uses th

Nice overview. Windows 1-3 used "non-premptive" or "cooperative" scheduling, which is why any process could hang the system. That method does have its uses though. I once wrote a micro kernel for MSP430 that did it that way too. As long as you can guarantee that a task will complete within a specified time, it's a good lightweight solution.

0xbadcafebee 5y ago
I remember when the Linux kernel's preemptible patches were introduced. It already had preemptible userspace, but the kernel wasn't, leading to lots of latency issues. Once they hacked up SMP support to add preempting, things were so much smoother
slaymaker1907 5y ago
It's very useful as a tool, though I think the ideal is a mix of both. You can do cooperative for the happy path and have an interrupt if something goes wrong with a thread not yielding. The main disadvantage is that single threaded plus fully cooperative makes avoiding races a lot easier.
addaon 5y ago
There's an intermediate point between pre-emptive and cooperative that I've found useful. For the lack of a better name let's call it "you-better-cooperate". Suppose a real-time system using cooperative scheduling where well-behaved tasks yield within a guaranteed time window. Suppose also a system that has the ability to launch and restart processes for example in the case of error. In such a system, a poorly-behaved process can hang the system because it doesn't yield. Introducing pre-emption to such a system avoids the potential hangs, but (a) adds the complexity of pre-emption; (b) only gets exercised in the case that you're already in a failure state (process failed to yield); and (c) allows processes in a known failure state to continue. Instead, when a process is scheduled, set a timer interrupt for a time period after its guaranteed yield. When the process yields, cancel that timer (or re-schedule it for the next process). If the timer fires, just kill and restart the non-yielding process. In a limited set of cases, this is a simpler, more robust, and equally powerful system compared to both full pre-emption and cooperation.
- booboofixer 5y ago
  If i'm understanding this correctly, then the difference between pre-emptive scheduling and the intermediate you described would be that in the pre-emptive scheduling case, a poorly-behaved process would be forced to give up the CPU and then be scheduled to run again at some point in the future (in a failure state) whereas, in the intermediate solution, a poorly-behaved process would be killed and restarted. Is that correct? If so, wouldn't this make matters worse if the poorly-behaved process is guaranteed to hang? Is killing a process and restarting it worse or better than context-switching repeatedly?
  - addaon 5y ago
    Yes, correct. Killing a process and restarting it is /often/ better than context switching repeatedly, but not always. Pro: It puts the process into a known state. Con: It removes the opportunity for slow forward progress. In the case where the process has been designed to have fixed latency, then slow forward progress is roughly as scary as memory corruption -- something is horribly wrong and you don't know if you're observing a minor symptom of a major problem. Balancing the pro/con there can be interesting, but the system level pro puts a pretty heavy thumb on the scales. In the intermediate approach, because there's no real pre-emption a whole class of race conditions can't exist. This can be pretty big for ease of system analysis.
    - ir193 5y ago
      how about a bookmark and yield mechanism(in PL level maybe), theb process can continue slow forward process when switched back
- MrYellowP 5y ago
  A real time operating system can, by definition, not be cooperative. Definitely not a hard one and a soft one most likely not either, simply because it can not guarantee that it will process the interrupt quickly enough to be qualified as RTOS. https://en.wikipedia.org/wiki/Real-time_operating_system https://en.wikipedia.org/wiki/Real-time_operating_system When you set a timer, which stops the running task to switch "to somewhere else", then it's not cooperative. Can you elaborate?
traverseda 5y ago
Reminds me of await/async. With micropython you can get a nice little cooperative multiprocessing operating system going on a micro-controller!
inamberclad 5y ago
Yep, this is what the Apollo AGC did. Each process had to yield every 20 ms or so.
boondaburrah 5y ago
I had a scanner that became much more stable running on a Mac OS 9 machine than a Windows machine simply because the scanning software could "hang" the mac and monopolize the SCSI port with exact timing.
dev_tty01 5y ago
Classic MacOS did the same thing. Basically, all GUI processes call GetNextEvent() at the head of the event loop. In 1985 Andy Hertzfeld wrote Switcher which used the GetNextEvent() entry point to pause an app and allow another app to run until the next call. Hertzfeld got the idea from the DOS utility Memory Shift. https://www.folklore.org/StoryView.py?project=Macintosh&story=Switcher.txt https://www.folklore.org/StoryView.py?project=Macintosh&stor... With well behaved apps it worked remarkably well. Apple brought it into the OS as MultiFinder.
phendrenad2 5y ago
This is how RTOSs work on microcontrollers that don't have a supervisor mode. A hardware timer interrupts each process and the interrupt handler switches which process is active. However, there's nothing stopping one process from disabling interrupts for some critical activity (like bit-banging some serial output) and then forgetting to re-enable them.

0xbadcafebee 5y ago

I remember when the Linux kernel's preemptible patches were introduced. It already had preemptible userspace, but the kernel wasn't, leading to lots of latency issues. Once they hacked up SMP support to add preempting, things were so much smoother

slaymaker1907 5y ago

It's very useful as a tool, though I think the ideal is a mix of both. You can do cooperative for the happy path and have an interrupt if something goes wrong with a thread not yielding. The main disadvantage is that single threaded plus fully cooperative makes avoiding races a lot easier.

addaon 5y ago

There's an intermediate point between pre-emptive and cooperative that I've found useful. For the lack of a better name let's call it "you-better-cooperate". Suppose a real-time system using cooperative scheduling where well-behaved tasks yield within a guaranteed time window. Suppose also a system that has the ability to launch and restart processes for example in the case of error. In such a system, a poorly-behaved process can hang the system because it doesn't yield. Introducing pre-emption to such a system avoids the potential hangs, but (a) adds the complexity of pre-emption; (b) only gets exercised in the case that you're already in a failure state (process failed to yield); and (c) allows processes in a known failure state to continue. Instead, when a process is scheduled, set a timer interrupt for a time period after its guaranteed yield. When the process yields, cancel that timer (or re-schedule it for the next process). If the timer fires, just kill and restart the non-yielding process. In a limited set of cases, this is a simpler, more robust, and equally powerful system compared to both full pre-emption and cooperation.

booboofixer 5y ago
If i'm understanding this correctly, then the difference between pre-emptive scheduling and the intermediate you described would be that in the pre-emptive scheduling case, a poorly-behaved process would be forced to give up the CPU and then be scheduled to run again at some point in the future (in a failure state) whereas, in the intermediate solution, a poorly-behaved process would be killed and restarted. Is that correct? If so, wouldn't this make matters worse if the poorly-behaved process is guaranteed to hang? Is killing a process and restarting it worse or better than context-switching repeatedly?
- addaon 5y ago
  Yes, correct. Killing a process and restarting it is /often/ better than context switching repeatedly, but not always. Pro: It puts the process into a known state. Con: It removes the opportunity for slow forward progress. In the case where the process has been designed to have fixed latency, then slow forward progress is roughly as scary as memory corruption -- something is horribly wrong and you don't know if you're observing a minor symptom of a major problem. Balancing the pro/con there can be interesting, but the system level pro puts a pretty heavy thumb on the scales. In the intermediate approach, because there's no real pre-emption a whole class of race conditions can't exist. This can be pretty big for ease of system analysis.
  - ir193 5y ago
    how about a bookmark and yield mechanism(in PL level maybe), theb process can continue slow forward process when switched back
MrYellowP 5y ago
A real time operating system can, by definition, not be cooperative. Definitely not a hard one and a soft one most likely not either, simply because it can not guarantee that it will process the interrupt quickly enough to be qualified as RTOS. https://en.wikipedia.org/wiki/Real-time_operating_system https://en.wikipedia.org/wiki/Real-time_operating_system When you set a timer, which stops the running task to switch "to somewhere else", then it's not cooperative. Can you elaborate?

traverseda 5y ago

Reminds me of await/async. With micropython you can get a nice little cooperative multiprocessing operating system going on a micro-controller!

inamberclad 5y ago

Yep, this is what the Apollo AGC did. Each process had to yield every 20 ms or so.

boondaburrah 5y ago

I had a scanner that became much more stable running on a Mac OS 9 machine than a Windows machine simply because the scanning software could "hang" the mac and monopolize the SCSI port with exact timing.

dev_tty01 5y ago

Classic MacOS did the same thing. Basically, all GUI processes call GetNextEvent() at the head of the event loop. In 1985 Andy Hertzfeld wrote Switcher which used the GetNextEvent() entry point to pause an app and allow another app to run until the next call. Hertzfeld got the idea from the DOS utility Memory Shift. https://www.folklore.org/StoryView.py?project=Macintosh&story=Switcher.txt https://www.folklore.org/StoryView.py?project=Macintosh&stor... With well behaved apps it worked remarkably well. Apple brought it into the OS as MultiFinder.

phendrenad2 5y ago

This is how RTOSs work on microcontrollers that don't have a supervisor mode. A hardware timer interrupts each process and the interrupt handler switches which process is active. However, there's nothing stopping one process from disabling interrupts for some critical activity (like bit-banging some serial output) and then forgetting to re-enable them.