How does the scheduler interrupt the cpu ?

All development related issues welcome

Moderator: Moderator Team

Post Reply
victor6799
Posts: 5
Joined: Tue Feb 23, 2021 11:35 pm

How does the scheduler interrupt the cpu ?

Post by victor6799 »

How does the scheduler interrupt the cpu in order to perform a context switch ?
karlexceed
Posts: 531
Joined: Thu Jan 10, 2013 6:17 pm
Contact:

Re: How does the scheduler interrupt the cpu ?

Post by karlexceed »

I'm not a dev, but I would guess you can find your answer somewhere in here: https://github.com/reactos/reactos/tree ... nl/ke/i386
bugdude
Posts: 28
Joined: Wed Nov 27, 2019 11:41 pm

Re: How does the scheduler interrupt the cpu ?

Post by bugdude »

I'm not a dev either, but it's an interesting question. Look at KE/thrdschd.c for a bit more information.

I'll try to answer you with a sort of paraphrased high level summary of sorts based on what I have seen so far. Anyone out there that wants to correct my mistakes is invited to do so because I am also learning abd curious to learn more about it. Suffice it to say that your question goes right at one of the real computer-sciency topics of Operating system design, it is real propeller headed stuff that lies at the very core of things in any Operating System.

Here is a 'very' simplified and abridged summary of what I interpreted from the code. At startup the OS kernel sets up a lot of tracking structures including a certain number of thread objects which it manages in a in a list. An empty context storage object is created for each. The main control routines of the thread scheduler are found in the source file I mentioned above and that is the heart of context switching in ReactOS. It basically receives control whenever a thread yields, and that happens automatically during several routine API activities. I think the most common points where it happens are when calling API functions related to processing messages or calling drivers. Since messages and driver calls are the 'life blood' of internal communications and happen constantly, every windows application must have a message loop and check for messages often. In some high level tools or frameworks this loop is hidden from the programmer or lives in the framework or runtime, but trust me in every single windows application has one somewhere.

Those functions allow the scheduler to look at the threads 'execution time' and it decides if it's time to hand off control because the processing time the scheduler allotted to the thread has been exhausted. If the threads time is up the thread scheduler finds the next thread due to run and switches the context transferring control to the other thread. In addition to those internal checking points, well written applications occasionally 'yield' to allow other applications a chance to execute when they are idle or waiting for an event signal (or their frameworks do). The underlying mechanics are actually uglier because they involve checking the processor program counter rather than a real 'execution time', but the net result is that the scheduler looks at the current threads activity and triggers a context switch at certain intervals.

The source file above shows some of the 'high-level' logic at work, but the lower level plumbing that actually performs context switching, register loading/saving, and LDT swapping are probably handled in assembly routines because they manipulate processor and memory directly and must be very fast. I am deliberately simplifying things and just paraphrasing a complicated topic here, but if you really want to know the details you should review the source code. The ReactOS source is a really interesting learning tool and as far as I know nothing else that tries to emulate how Windows operates and its internal structures is available. ReactOS is also not complete yet and this is one area where the missing pieces show, the scheduler in ROS is mot MP capable yet and I think it only uses a single processor core even if several are present. For a student that is actually an advantage because it makes the code easier to read and understand. Once it is fully MP capable many more threads will run at once and racing through it will be harder. For now this is also why ReactOS is not as fast as it could be, it simply doesn't use all of the resources the processor makes available yet.

This is also a place in the OS where parts can be very specific to the processor architecture so you will see subfolders under ke for the each processor that ReactOS can work on. The decision of which thread runs next is also a good bit more complicated than I made it sound here because each thread has a priority level and a time allotment(quanta) and they can change dynamically as the system executes. A base level is set when each process starts, but I believe it changes if the process shifts priority, and is silently boosted up when it enters a critical section or takes any of a number of specific actions synchronization like acquiring a lock or semaphore.

Good luck in your exploration, if you are really interested in the topic study the code and look at the windows internals books. One of the developers who worked on many parts of ReactOS is an author of some of those books.

bugdude
bugdude
Posts: 28
Joined: Wed Nov 27, 2019 11:41 pm

Re: How does the scheduler interrupt the cpu ?

Post by bugdude »

I think it's likely that a thread scheduling check also takes place when there are interrupts (IRQs or interrupt requests IRPs) being processed because handling them often requires a context switch. I haven't seen that in the source, but suspect it's there somewhere. Hardware generated Interrupts are probably the only truly 'preemptive' entry into the scheduler, but you have to remember that this includes frequent interruptors like RTC timer. If I'm not mistaken many other hardware drivers rely on watchdog type timer interrupts to avoid missing data, most bus drivers and the PIC driver would pretty much require these to even function. Since the scheduler would need to switch context for the drivers to run their code it seems logical that the scheduler would check if the original thread was still the highest priority thread when the driver routine finished, Although I haven't seen that in the source, it is very visible in the debugger when tracing, the PID shifts around at API call boundaries very regularly when tracing.
victor6799
Posts: 5
Joined: Tue Feb 23, 2021 11:35 pm

Re: How does the scheduler interrupt the cpu ?

Post by victor6799 »

bugdude thanks and same to karlexceed. What I was hoping to learn is how does the kernel wake up once a thread has exhausted it's quantum ? Does an interrupt fire or perhaps something else ? Just to clear any confusion what I am asking is how does the scheduler (kernel) code know that it's CPU quantum has expired ? Does a clock CPU timer interrupt fire off or is it something else that takes place ?
bugdude
Posts: 28
Joined: Wed Nov 27, 2019 11:41 pm

Re: How does the scheduler interrupt the cpu ?

Post by bugdude »

victor6799,

Looking through the code is the only way to see the details, but as I said before I believe there are actually several ways this happens.

In a running system each thread returns control to the kernel when it finishes a task via yield or exit, since there are multiple threads in virtually all processors these days something would enter the thread scheduler quite frequently because yields are not always explicit. Any interrupt that occurs requires a context switch and that passes through the kernel and many Windows API calls do as well. At each of those points the thread scheduler can decide to let them run right away or wait its turn, and can review the thread list to see if some 'other' thread has expired or if a higher priority thread should preempt the one that initiated the API call. The messaging API and many other API calls do this and behave somewhat like an interrupt because they require kernel participation to retrieve information or messages from global objects (like the message queue or the PEB) which are owned by the kernel (the same is true for accessing objects belonging to another process or driver, filesystems, memory allocations etc). I'm fairly sure that the majority of Windows API calls would trigger entry into the thread scheduler to see if their quanta had expired because you cannot get messages, send messages, output to screen or devices without making API calls along the way. Even if you use screen API's to access memory directly, you still need messages to ket leyboard or mouse input or output to any other device.. Truly other than writing a loop that does nothing but manipulate local variables and not do any output it is rather hard to avoid calling the Windows API frequently.

As far as I know there is NOT a specific timer for each thread in the processor or hardware that is set to 'expire' that would trigger this event directly, instead the scheduler in the Windows environment relies on those frequent entries into the kernel to check for expirations or higher priority items waiting. While I may be grossly oversimplifying the details in order to illustrate the concept, and may even have some of the details just plain wrong..

The lack of a specific interrupt for thread expiration is why you can actually 'freeze' a windows system. Even though the design is pretty robust, pushing too many threads into tight loops, critical sections, or simultaneous calls to use a protected kernel object can leave the system frozen. Empirically I can tell you that if a hard timer existed for Quanta expiration it would truly be impossible to freeze a Windows based system (ever) because the process that is locked-up would eventually expire.

This is why it's a popular computer-science topic. Doing it wrong leads to busted environments with crazy behavior, and this is a place where both hardware and software elements are involved. Without a supervisor multi-process or multi-thread scheduling are done through a lot of software/firmware smoke and mirrors rather than through a hard system timer like you describe. By the way, in some mainframes there were supervisors that did work that way, but they just generated a processor dump and took you to something much like the kernel debugger. Technically one could build a supervisor at the hardware level using the NMI in the PC, but as far as I know nothing of the sort has been done other than the 'reset button'. The closest thing I know of to that concept in Windows is the system timer interrupt in PC hardware that fires frequently and which the OS leverages that for its supervisor-like behaviors including scheduling preemption checks. That timer is not set to anything complex like quanta expiration, it just runs constantly generating interrupts at fixed intervals after a certain number of ms. Its frequency is 'much' slower than the CPU clock cycle, but is fast enough that it is used to check if other hardware like the keyboard or bus controllers have raised any interrupts (which they do by placing a voltage on a certain physical wire on a bus connector or chip).

bugdude
Post Reply

Who is online

Users browsing this forum: No registered users and 5 guests