Operating Systems: CPU Scheduling
cs.uic.edu
cs.uic.edu
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.
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?
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.
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?
As an example of such a system, consider a bare metal BLDC motor driver. You may statically schedule a sequence of tasks -- read current sensors, read commands, adjust PWM hardware registers, read temperature sensors, change state on temperature error, loop. Suppose that the 'read temperature sensors' task can fail to meet its analytic time budget because the I2C hardware can get into a weird state and just not return. (Suppose further that this isn't hypothetical...) Then having a kill-and-reset-on-timeout feature for the temperature sensor task is an obvious and reasonable workaround to give an improved system. That feature can be added to the temperature sensor task; or, it can be added as a general feature to the round robin scheduler in the way I described.
Hope that's a helpful description of what I was trying to explain! I'm not in any way saying this is a general solution or a universal replacement for a real RTOS; rather that it's a pattern I've ended up re-deriving a time or two that I find interesting.
You said; "When you set a timer, which stops the running task to switch "to somewhere else", then it's not cooperative." You are correct. The OS does not require the cooperation of the task in order to suspend it and start/resume a different task. A non-cooperative OS does not require the task to either make a system call (such as waiting on I/O) or to finish. It will preempt the running task according to the scheduler rules. Typically a scheduler will receive periodic interrupts so that it can assess which task should be made active. On real-time systems without much processing headroom, the context switching between tasks can take up a significant percentage of CPU time, which is why I went with cooperative multitasking on the (25MHz) MSP430 micro-controller.
Tasks in those two scheduling tasks will basically never be preempted by a lower priority task nor a task in any other scheduling class. However the system has an overall percentage limit on how much of the cpu tasks in these classes may consume. If they consume more than this limit, they will be preempted and non-RT tasks will run "for a while" before heading back to RT tasks.
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.
https://ailtonbsj.github.io/cpu-scheduling-simulator/
https://ailtonbsj.github.io/cpu-scheduling-simulator/old.htm...
There was an article posted here a while back that challenged the notion that 100% utilization is a desirable goal:
https://blog.danslimmon.com/2015/07/09/when-efficiency-hurts...
Honestly, I don't see the point of all these instructors making their own summaries of the same book. I think that all these summaries condense the material to the point they're barely more than PowerPoint lists.
Can someone that learns better using this format explain why?
My colleagues from other universities here do exactly what you say, they do their own summary which is an effort I also don't understand.
The only moment when I felt I needed to do my own slides was with the pandemic online courses that refrained me from using the whiteboards in the amphitheater. But in the end the graphical tablet saved me from that.
Users could buy CPU time and grant portions of it to other users in the system (say, their employees) via keys, who could in turn grant resources to other users/ subprocesses recursively, resulting in a metering tree.
The programming language Joule, which was inspired by it, used this system too: http://www.erights.org/history/joule/MANUAL.BK8.pdf
The Sel4 and Genode operating systems as well
The overall question is to decide who (user, process, ...) has which permissions (read, write, execute, share, revoke,...) on which resources (processes, memory, files,...). Capability based systems provide a finer grained solution to this problem than the classical UNIX access control list with interesting trade-offs.
As an example, privilege escalation exploits can be avoided with a capability based OS. This is also known as the "confused deputy problem". Imagine you're on a server and get billed for each ms of runtime that a compiler uses. You provide an input (e.g. main.c) to the compiler, and an output location (e.g. out.a). The compiler runs, writes out.a, and appends a line to a bookkeeping file. The problem is that the compiler has privileged access to the bookkeeping file and every write it does is in this privileged mode. Therefore, you can provide as output file the location of the bookkeeping file and overwrite it with the compiled binary.
On a capability based system, the compiler has one (privileged) capability to write to the bookkeeping file, and the user not only provides an output location, but also a capability to write to the requested location. The compiler then uses the corresponding capability for each write and this guarantees that it'll never escalate privileges.
It is not trivial to design a sound (and efficient) capability based system, nor to implement it. I wonder when they appear in modern OSes as they can solve many privacy-related problems.
The scheduler will always schedule the highest priority task among ones in the ready queue, but at different times.
- If preemptive, the scheduler will schedule the higher priority task (higher than the currently running one) as soon as it enters the ready queue.
- If non preemptive, the scheduler will schedule the higher priority task only when the running one terminated or explicitly call a yield() (call to yield --> cooperative)
In principle, you can mix both scheduling types, making some tasks "non-preemptable" and other tasks "preemptable".
/proc/sched_debug is one I still don't understand.
This gives a nice overview, and adjusting the Quantum can certainly help any CPU but like the same on the Rpi, its possible to get to a point where the quantum is degrading performance noticeably and I think this has helped pc sales enormously.
https://www.microsoftpressstore.com/articles/article.aspx?p=...
Quantum Settings Registry Value
HKLM\SYSTEM\CurrentControlSet\Control\PriorityControl\Win32PrioritySeparation
2A Hex = Short, Fixed , High foreground boost.
29 Hex = Short, Fixed , Medium foreground boost.
28 Hex = Short, Fixed , No foreground boost.
26 Hex = Short, Variable , High foreground boost.
25 Hex = Short, Variable , Medium foreground boost.
24 Hex = Short, Variable , No foreground boost.
1A Hex = Long, Fixed, High foreground boost.
19 Hex = Long, Fixed, Medium foreground boost.
18 Hex = Long, Fixed, No foreground boost.
16 Hex = Long, Variable, High foreground boost.
15 Hex = Long, Variable, Medium foreground boost.
14 Hex = Long, Variable, No foreground boost.
https://docs.microsoft.com/en-us/windows-hardware/test/wpt/c...
Of course, if the process that is overloaded is the process responsible for keeping the system from crashing into the Sun, this doesn't quite fix the problem.