Linux kernel: schedule() function

Question

I have seen several other questions on the forum that talk about this schedule() function, but my question is a bit different. I have seen several discussions and literature about it's theoretical, algorithmic and implementation aspects.

The thing which is not clear and the question is asked about, is the execution aspect. Of course looking at the source of the kernel in depth and doing all the required debugging, tracing bla bla... might answer this question but it seem not wise to reinvent the wheel.

The questions/confusions are as following:

What is the path traversed by a multi-threaded user program at kernel level?

Who schedules the threads? Which interrupt context(s)? Any name? (if we see at a trace at kernel level, there is nothing called "sched", but there are swappers, inits, ksoft* bla bla) Deos it go like this:

A process (user program) its child threads all are taken by the kernel at first, then kernel makes them as executable threads (by amalgamating them with schedule() and/or other functions, i.e., this new executable thread has some instructions from the kernel maybe from schedule()/others, embedded along with user task instructions. That makes it scheduled automatically if the situation occurs )

OR

schedule() is always executing at some co-processor to observe and act, if necessary, from that co-processor? That's why, sometimes when we see any two threads switching on a cpu there is only swapper executing in-between and before and after, i.e., there is nothing called scheduler at that level, right?

Thanks for reading and sorry for writing my confusions to share with.

Answer 1

Inside the Linux kernel, threads are just processes that share some resources. In other words, for the Linux kernel, threads are just a particular case of processes. The data structure is the same (i.e., task_struct - see include/linux/sched.h).

The system timer is the hardware timer issuing an interrupt at a programmable frequency. Periodically, it issues an hardware interrupt. When the kernel receives such an interrupt, the execution of the current process/thread is interrupted and the system runs the Interrupt Service Routine (ISR) in kernel mode. This routine calls the scheduling functions which choose which process (or thread) should be excecuted in the next time slot. Then, the routine performs a context switch by preempting the currently executing process/thread. This is the basis of multitasking which is the same across all modern general-purpose operating systems.

Answer 2

X OR Y - neither.

These preemptive, multithreading OS kernels are all much the same overall.

Look at it, (very simply), like this:

The OS kernel scheduler/dispatcher is a big, complex, interrupt-handler. Interrupts, in OS terms come in two flavours:

Hardware interrupts from peripherals like disk, network, keyboard, mouse. These interrupts cause drivers to run, and the drivers may request a scheduling run from the kernel when they exit.

Software interrupts from threads - system calls that can change the state of a thread, eg. a thread may request input that is not immediately available, and so that thread will not run on until the input is available.

When an interrupt does occur, the kernel uses its internal state data, together with the request data from the interrupt, to run its scheduling algorithm and decide which threads should be running on the available cores. If it decides that the set of running threads needs to change, it can stop any thread running on any core by using an inter-core driver to cause a hardware-interrupt of the core running the thread.

If there are no interrupts, the kernel does nothing. It can't do anything because it is not being entered from anywhere. It does not need to execute on any co-processor. It does not need to 'inject' any calls into user code.

It's a state-machine with interrupts as inputs and a set of running threads as outputs.