6 ms·

Operating Systems: CPU Scheduling

peter_d_sherman 5y ago
Related: https://en.wikipedia.org/wiki/Scheduling_(computing) https://en.wikipedia.org/wiki/Scheduling_(computing) https://en.wikipedia.org/wiki/Idle_(CPU) https://en.wikipedia.org/wiki/Idle_(CPU) https://en.wikipedia.org/wiki/System_Idle_Process https://en.wikipedia.org/wiki/System_Idle_Process https://en.wikipedia.org/wiki/HLT_(x86_instruction) https://en.wikipedia.org/wiki/HLT_(x86_instruction) https://stackoverflow.com/questions/5112097/what-is-the-code-for-the-idle-process https://stackoverflow.com/questions/5112097/what-is-the-code... https://github.com/torvalds/linux/tree/master/kernel/sched https://github.com/torvalds/linux/tree/master/kernel/sched
aabbqq 5y ago
I like writing as list pattern/style. Very easy to be engaged and learn. I found a article about his pattern earlier in hackernews https://dynomight.net/lists/ https://dynomight.net/lists/
Rechtsstaat 5y ago
I also followed a course that was based on the Silberschatz/Gagne/Galvin book, and when searching for background I found many courses based on the same - they were structured extremely similar. 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?
- pantulis 5y ago
  I guess these materials are intended as support for classes, so it is ok for them to resemble Powerpoint decks as there would be a lot of voice over and explanations on top of them by the teacher.
- bulibuta 5y ago
  I am a university professor teaching Operating Systems based on the Dinosaur book. I always use the authos' slides to which I add my own notes and extra/missing concepts. 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.
- windows_kernel 5y ago
  Vain attempt to justify tuition fees with "original" content.
anonymousiam 5y ago
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.
rossmohax 5y ago
I've been working with Linux systems for almost 20 years and became familiar with many files in /proc kernel provides to inspect its various subsystems. /proc/sched_debug is one I still don't understand.
- Terry_Roll 5y ago
  The early RaspberryPi's are/were excellent for experimenting with when trying to squeeze performance out of it, I managed to get one to clock up to close to 2Ghz which was that mythical beast to get past whilst remaining stable (no cpu heatsinks or fans) and the cpu scheduling certainly affects performance on them, but it affects all the main cpu's and OS near enough. So what works on Windows can be applied to Linux and vice versa. 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=2233328&seqNum=7 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/cpu-analysis https://docs.microsoft.com/en-us/windows-hardware/test/wpt/c... https://live.sysinternals.com/tools/Clockres.exe https://live.sysinternals.com/tools/Clockres.exe
sydthrowaway 5y ago
Now we need to know the state of the art.
- booboofixer 5y ago
  I agree, there are many people working on their own open-source operating systems. I would put in the effort to learn and contribute if only I knew what the state of the art was. Maybe linux kernel == S.O.T.A ?
  - sydthrowaway 5y ago
    How about seL4?
    - booboofixer 5y ago
      Interesting suggestion, thanks.
      - snvzz 5y ago
        seL4's mixed criticality (MCS) kernel and the time capabilities absolutely are the state of the art.
ailtonbsj_ 5y ago
I built two simulators when I studying this. https://ailtonbsj.github.io/cpu-scheduling-simulator/ https://ailtonbsj.github.io/cpu-scheduling-simulator/ https://ailtonbsj.github.io/cpu-scheduling-simulator/old.html https://ailtonbsj.github.io/cpu-scheduling-simulator/old.htm... Demo: https://youtu.be/vulTnsfu6GY https://youtu.be/vulTnsfu6GY
willis936 5y ago
How do you have a hard realtime system when the amount of work needed to be done in a period of time is not deterministic? How can you even prove the bounds of the amount of work?
- sedatk 5y ago
  With non-maskable hardware interrupts?
- ciarcode 5y ago
  Then it would be not an hard real time system.
- ip26 5y ago
  The way I understand it is a hard realtime system does not solve that problem but does ensure the process with too much work does not prevent any other process from meeting its obligations. In other words, the failure to meet demand is isolated & prevented from cascading into other tasks. 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.
ciarcode 5y ago
I always think to priority-based scheduling in this way. Maybe it can help someone else. 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".
asdadsdad 5y ago
love scheduling theory
paulmooreparks 5y ago
> CPU utilization - Ideally the CPU would be busy 100% of the time, so as to waste 0 CPU cycles. On a real system CPU usage should range from 40% ( lightly loaded ) to 90% ( heavily loaded. ) 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-more-than-it-helps/ https://blog.danslimmon.com/2015/07/09/when-efficiency-hurts...
7373737373 5y ago
The KeyKOS mainframe operating system, to which users connected with terminals, had an interesting scheduling and resource metering system: http://www.cap-lore.com/CapTheory/KK/Arch/Three.Special.html#meterkey http://www.cap-lore.com/CapTheory/KK/Arch/Three.Special.html... 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 http://www.erights.org/history/joule/MANUAL.BK8.pdf The Sel4 and Genode operating systems as well
- backes 5y ago
  Such a system is based on "capabilities" and many research OSes such as Barrelfish<https://barrelfish.org/ https://barrelfish.org/>, Hydra, Mach, and EROS explored these. 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.

Related: https://en.wikipedia.org/wiki/Scheduling_(computing) https://en.wikipedia.org/wiki/Scheduling_(computing) https://en.wikipedia.org/wiki/Idle_(CPU) https://en.wikipedia.org/wiki/Idle_(CPU) https://en.wikipedia.org/wiki/System_Idle_Process https://en.wikipedia.org/wiki/System_Idle_Process https://en.wikipedia.org/wiki/HLT_(x86_instruction) https://en.wikipedia.org/wiki/HLT_(x86_instruction) https://stackoverflow.com/questions/5112097/what-is-the-code-for-the-idle-process https://stackoverflow.com/questions/5112097/what-is-the-code... https://github.com/torvalds/linux/tree/master/kernel/sched https://github.com/torvalds/linux/tree/master/kernel/sched

aabbqq 5y ago

I like writing as list pattern/style. Very easy to be engaged and learn. I found a article about his pattern earlier in hackernews https://dynomight.net/lists/ https://dynomight.net/lists/

Rechtsstaat 5y ago

I also followed a course that was based on the Silberschatz/Gagne/Galvin book, and when searching for background I found many courses based on the same - they were structured extremely similar. 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?

pantulis 5y ago
I guess these materials are intended as support for classes, so it is ok for them to resemble Powerpoint decks as there would be a lot of voice over and explanations on top of them by the teacher.
bulibuta 5y ago
I am a university professor teaching Operating Systems based on the Dinosaur book. I always use the authos' slides to which I add my own notes and extra/missing concepts. 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.
windows_kernel 5y ago
Vain attempt to justify tuition fees with "original" content.

anonymousiam 5y ago

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.

rossmohax 5y ago

I've been working with Linux systems for almost 20 years and became familiar with many files in /proc kernel provides to inspect its various subsystems. /proc/sched_debug is one I still don't understand.

Terry_Roll 5y ago
The early RaspberryPi's are/were excellent for experimenting with when trying to squeeze performance out of it, I managed to get one to clock up to close to 2Ghz which was that mythical beast to get past whilst remaining stable (no cpu heatsinks or fans) and the cpu scheduling certainly affects performance on them, but it affects all the main cpu's and OS near enough. So what works on Windows can be applied to Linux and vice versa. 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=2233328&seqNum=7 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/cpu-analysis https://docs.microsoft.com/en-us/windows-hardware/test/wpt/c... https://live.sysinternals.com/tools/Clockres.exe https://live.sysinternals.com/tools/Clockres.exe

sydthrowaway 5y ago

Now we need to know the state of the art.

booboofixer 5y ago
I agree, there are many people working on their own open-source operating systems. I would put in the effort to learn and contribute if only I knew what the state of the art was. Maybe linux kernel == S.O.T.A ?
- sydthrowaway 5y ago
  How about seL4?
  - booboofixer 5y ago
    Interesting suggestion, thanks.
    - snvzz 5y ago
      seL4's mixed criticality (MCS) kernel and the time capabilities absolutely are the state of the art.

ailtonbsj_ 5y ago

I built two simulators when I studying this. https://ailtonbsj.github.io/cpu-scheduling-simulator/ https://ailtonbsj.github.io/cpu-scheduling-simulator/ https://ailtonbsj.github.io/cpu-scheduling-simulator/old.html https://ailtonbsj.github.io/cpu-scheduling-simulator/old.htm... Demo: https://youtu.be/vulTnsfu6GY https://youtu.be/vulTnsfu6GY

willis936 5y ago

How do you have a hard realtime system when the amount of work needed to be done in a period of time is not deterministic? How can you even prove the bounds of the amount of work?

sedatk 5y ago
With non-maskable hardware interrupts?
ciarcode 5y ago
Then it would be not an hard real time system.
ip26 5y ago
The way I understand it is a hard realtime system does not solve that problem but does ensure the process with too much work does not prevent any other process from meeting its obligations. In other words, the failure to meet demand is isolated & prevented from cascading into other tasks. 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.

ciarcode 5y ago

I always think to priority-based scheduling in this way. Maybe it can help someone else. 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".

asdadsdad 5y ago

love scheduling theory

paulmooreparks 5y ago

> CPU utilization - Ideally the CPU would be busy 100% of the time, so as to waste 0 CPU cycles. On a real system CPU usage should range from 40% ( lightly loaded ) to 90% ( heavily loaded. ) 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-more-than-it-helps/ https://blog.danslimmon.com/2015/07/09/when-efficiency-hurts...

7373737373 5y ago

The KeyKOS mainframe operating system, to which users connected with terminals, had an interesting scheduling and resource metering system: http://www.cap-lore.com/CapTheory/KK/Arch/Three.Special.html#meterkey http://www.cap-lore.com/CapTheory/KK/Arch/Three.Special.html... 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 http://www.erights.org/history/joule/MANUAL.BK8.pdf The Sel4 and Genode operating systems as well

backes 5y ago
Such a system is based on "capabilities" and many research OSes such as Barrelfish<https://barrelfish.org/ https://barrelfish.org/>, Hydra, Mach, and EROS explored these. 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.