Timeslice expiration linux code#

The currently running process is holding a spin lock in the kernel, it cannotīe put to sleep from the interrupt handler. Itself, from within the timer interrupt? After all, if the scheduler knows thatĪ process’s time has expired, shouldn’t it just context switch right away?Īs it turns out, it is not always safe to call schedule. When the current process has been running for 10 milliseconds or more.īut wait, why the heck can’t scheduler_tick just call schedule by In our simplified example, scheduler_tick would set this flag This indicates to the rest of the kernel that schedule If so, it sets a (over-simplification alert) per-cpu flag called Scheduler_tick, the scheduler checks to see if the running process’s time hasĮxpired. Notice how update_process_times invokes scheduler_tick. Here is the portion relevant to us: static void _sched notrace _schedule ( bool preempt ) Texts as “the entrypoint into the scheduler”. Process and runs the next one on the CPU. The scheduleįunction is the crux of Responsibility I: it halts the currently running Understand how Responsibility I is carried out by the scheduler. With a conceptual understanding of the runqueue, we now have the background to

“yielding” is when a process voluntarily gives up the CPU.

“preemption” is when a process is forcibly kicked off the CPU.

In this case, the process has yielded the CPU. To do this, the process puts itself on a “wait queue” and takes itself ForĮxample, a process might voluntarily go to sleep, waiting for an IO event or

Preemption is not always the reason a process is taken off the CPU. The main takeaway is that a process is allowed to runįor some time, and when that time expires, it gets preempted so that the next Remember: the goal here is to understand how the scheduler interoperates with

Keep these details at the back of your mind so that you don’t get bogged down. Struct rq has the following members: struct cfs_rq cfs // CFS scheduler runqueue struct rt_rq rt // Real-time scheduler runqueue struct dl_rq dl // Deadline scheduler runqueue The modern-day runqueue is no longer a linked list but actually a collection ofĪlgorithm-specific runqueues corresponding to the list above. Scheduler evolved to incorporate multiple scheduling algorithms.

More or less describes the very first Linux runqueue. The scheduler is not really this simple the runqueue is defined in the kernelĪs struct rq, and you can take a peek at it’s definitionĪlert: it’s not a linked list! To be fair, the explanation that I gave above Processes CAN migrate between various CPUs’ runqueues, but we’ll save thisįigure 1: An over-simplification of the runqueue Runqueue, and a given process may appear on only one CPU’s runqueue at a time. Waiting to have a go on the CPU is called the runqueue. This way, we say that it has been preempted. When a running process is forcibly stopped and taken off the CPU in The back of the queue, and the next process gets to run on the CPU for the same After this time slice expires, the process is moved to The process at the head of the queue is allowed to run for some “time slice”. System that maintains a simple queue of processes in the form of a linked list. Here’s the first over-simplification: you can think of the scheduler as a To fulfill its first responsibility, the scheduler must somehow keep track of Responsibility I: Switching to the Next Process Responsibility II: Indicate to the rest of the OS when a new process.Process to run, which is a nontrivial problem. To do so, the scheduler must pick the next Responsibility I: Provide an interface to halt the currently running.Perspective of the rest of the kernel - has two main responsibilities: Invoked with a simple and well-defined API. So, to hide the complexity of the scheduler, it is Know or care how the scheduler performs its magic, as long as it can be called Scheduler has a distinct and nontrivial job.

Timeslice expiration linux code#

You can find most scheduler-related code under kernel/sched. The scheduler is in charge of coordinating all of this Occurs quickly enough to create the illusion that all processes are running Letting the CPU perform work on behalf of each one in turn. At a high level, Linux context switches from process to process, At any instant, there are many processesĪctive at once, but a single CPU can only perform work on behalf of one processĪt a time. Simplifying assumptions while focusing on understanding what the scheduler does We won’t worryĪbout the scheduler’s internals just yet. Where it fits in with respect to the rest of the kernel. In this post, I introduce the Linux scheduler, describe its job, and explain This article is Part 2 in a 3-Part Series.