0

I've been studying unix/linux system fundamentals and in particular, how a list of tasks or processes gets handled in a modern computer system.

I've found a lot of resources that give what appears to be a standard explanation of the context switching that the kernel does and how signals (SIGXXX) are handled:

  • A process runs for a set amount of time or until an interrupt is received
  • The kernel unloads the process from running memory (cache), stows data about its context in memory elsewhere to load the next process that needs CPU time.
  • If a signal (SIGXXX) is waiting for the process, the kernel tries to invoke the appropriate handler in the process. If none exists, the process is not loaded back again (killed).
  • The new process is loaded in to memory and runs; the cycle continues

(Please let me know if this understanding is incorrect)

The thing I've been struggling with is, if this is all occurring on a single-core, single-thread CPU, what's physically running the scheduler? I'm missing something really simple, but I'm stuck in this chicken-or-the-egg kind of thinking.

And further, in modern systems that have multiple cores, threads, and lots of CPU resources available, does the scheduler consume a core by itself to run?

I've read a lot of articles about the different process schedulers, the original O(n), the newer O(1) introduced in 2.6 and beyond, and the CFS scheduler that (I think?) is used in most Linuxes nowadays. All of them talk about how they are prioritizing and queing processes, and none of them go in to detail about how and when the scheduler is actually running to accomplish all its tasks.

Is the scheduler sharing CPU time? Shuffling itself in and out of the CPU somehow? If so, how does the CPU know when to stop a process and let the scheduler run to do its thing?

Locane
  • 2,886
  • 2
  • 24
  • 35

2 Answers2

3

if this is all occurring on a single-core, single-thread CPU, what's physically running the scheduler?

You're right in your thinking that it needs to be something outside of the kernel, because the current thread is busy doing stuff and issuing system calls. The key idea is that the kernel registered a clock interrupt in the CPU kernel, the exact implementation differs from device to device, but the CPU kernel itself calls the registered interrupt handler (aka ISR) every time the timer interval is over or a kernel signal has occurred. The ISR is in effect a memory pointer to your interrupt function you give to the kernel. Before the interrupt function would return back to user space (i.e. the currently working thread) the scheduler is called (more details here)

The frequency of the scheduling depends on the clock speed of the cpu.

does the scheduler consume a core by itself to run?

No, the scheduler runs on every core by itself and also has the possibility to schedule the thread on another core.

Some further reading:

Community
  • 1
  • 1
hansaplast
  • 11,007
  • 2
  • 61
  • 75
1

Scheduler is part of kernel and yes of course, it consumes CPU. In simplest case, you can think of timer being attached to CPU, which ticks e.g every 10ms. On every tick, CPU gets 'interrupted', that is, it jumps to some pre-defined address, where scheduler is located. scheduler then saves some process-related data to some internal structure, chooses another process, loads its data and jumps to the address that the process was executing at.

Those O(n) and O(1) are exactly time complexities of schedulers, which means, how much time does scheduler need to decide which task to schedule next.

Zhani Baramidze
  • 1,407
  • 1
  • 13
  • 32
  • Part of my question is about not simplest case - in the case of a multi-core processor, or multiple processors. Are you saying that there is always a hard-coded limit to how long a CPU will spend on a specific task, and that an interrupt happens at a maximum and the CPU loads the scheduler? Which CPU loads the scheduler in the case of 12 cores? What determines that? – Locane Feb 10 '17 at 01:04
  • Scheduler has to run on every core, one core cannot change another core's registers. And that hard-coded limit depends on scheduling algorithm. Some of them give maximum time slice to each process, and if process doesn't voluntarily 'give up' on CPU, that interrupt makes context switch happen – Zhani Baramidze Feb 10 '17 at 08:52