[HN Gopher] Operating Systems: CPU Scheduling
___________________________________________________________________
Operating Systems: CPU Scheduling
Author : peter_d_sherman
Score : 106 points
Date : 2022-04-16 16:34 UTC (6 hours ago)
(HTM) web link (www.cs.uic.edu)
(TXT) w3m dump (www.cs.uic.edu)
| willis936 wrote:
| 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?
| ip26 wrote:
| 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.
| sedatk wrote:
| With non-maskable hardware interrupts?
| ciarcode wrote:
| Then it would be not an hard real time system.
| ailtonbsj_ wrote:
| I built two simulators when I studying this.
|
| https://ailtonbsj.github.io/cpu-scheduling-simulator/
|
| https://ailtonbsj.github.io/cpu-scheduling-simulator/old.htm...
|
| Demo: https://youtu.be/vulTnsfu6GY
| anonymousiam wrote:
| 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.
| traverseda wrote:
| Reminds me of await/async. With micropython you can get a nice
| little cooperative multiprocessing operating system going on a
| micro-controller!
| inamberclad wrote:
| Yep, this is what the Apollo AGC did. Each process had to yield
| every 20 ms or so.
| slaymaker1907 wrote:
| 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.
| boondaburrah wrote:
| 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.
| 0xbadcafebee wrote:
| 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
| addaon wrote:
| 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.
| MrYellowP wrote:
| 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
|
| When you set a timer, which stops the running task to switch
| "to somewhere else", then it's not cooperative.
|
| Can you elaborate?
| anonymousiam wrote:
| The MSP430 RTOS I wrote was real-time and cooperative, with
| the caveat that it was application specific, and no task
| would ever take more than one millisecond to complete. I
| was careful to design all the tasks so they would never
| exceed the maximum run-time. For the tasks that needed more
| time, I broke them into several sub-tasks.
|
| 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.
| addaon wrote:
| A real time system can be cooperative. A real time
| operating system can use pre-emption to achieve bounded
| latency. A real time system that does not use pre-emption
| can use other mechanisms -- including a combination of
| analytical bounding of task run-times and static
| cooperative scheduling -- to achieve bounded latency. The
| latter system can be enhanced by enforcing the analytical
| bounds, making it somewhat robust to errors in analysis.
| One can argue that this enforcement makes the system non-
| cooperative, it's certainly not full pre-emption with all
| the costs and benefits that go with.
|
| 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.
| anonymousiam wrote:
| Heh. I2C was part of what I was doing on the
| aforementioned MSP430 OS. I ended up breaking up all the
| I2C stuff into parts of a state machine (I think I ended
| up with six states), and ran it in the background as the
| lowest priority main loop.
| booboofixer wrote:
| 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 wrote:
| 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.
| aabbqq wrote:
| 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/
| rossmohax wrote:
| 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.
| sydthrowaway wrote:
| Now we need to know the state of the art.
| booboofixer wrote:
| 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 wrote:
| How about seL4?
| booboofixer wrote:
| Interesting suggestion, thanks.
| ciarcode wrote:
| 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".
| Rechtsstaat wrote:
| 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 wrote:
| 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 wrote:
| 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.
| peter_d_sherman wrote:
| Related:
|
| https://en.wikipedia.org/wiki/Scheduling_(computing)
|
| https://en.wikipedia.org/wiki/Idle_(CPU)
|
| https://en.wikipedia.org/wiki/System_Idle_Process
|
| https://en.wikipedia.org/wiki/HLT_(x86_instruction)
|
| https://stackoverflow.com/questions/5112097/what-is-the-code...
|
| https://github.com/torvalds/linux/tree/master/kernel/sched
___________________________________________________________________
(page generated 2022-04-16 23:00 UTC)