Shulou(Shulou.com)11/24 Report--

This article comes from the official account of Wechat: low concurrency programming (ID:dibingfa). Author: flash.

Everyone must know something about process scheduling, but they don't know much about it.

I know something because this concept has been mentioned too many times, but I don't know much about it because I always feel that it is not intuitive and floats at the conceptual level.

Today, we take a look at what process scheduling is all about from three perspectives. Please hold on when you start the car.

Tip: this article is about the linux-0.11 version of the process scheduling mechanism, learn its backbone and framework, do not drill into the details.

1. Tick-tock perspective tick-tock

There is a device in the computer called a timer, which is precisely called a programmable timer / counter.

This timer sends an interrupt signal to CPU at regular intervals.

In linux-0.11, this interval is set to 10 ms, or 100 Hz.

Shedule.c

The interrupt initiated by # define HZ 100is called a clock interrupt, and its interrupt vector number is set to 0x20.

Clock interrupt

The source of everything comes from this clock interruption per 10ms.

Of course, if there is no operating system, the clock interrupt of the 10ms will be wasted, and the CPU will receive the clock interrupt signal, but will not make any response.

Unfortunately, linux has set up the interrupt vector table in advance.

Schedule.c

Set_intr_gate (0x20, & timer_interrupt); in this way, when the clock is interrupted, that is, when the 0x20 interrupt comes, CPU looks for the function address at 0x20 in the interrupt vector table, which is the interrupt handler, and jumps to execute.

The interrupt handler is timer_interrupt, which is written in assembly language.

System_call.s

_ timer_interrupt: / / increasing the number of system ticks incl _ jiffies / / calling the function do_timer call _ do_timer this function does two things: one is to add one to the variable jiffies of system ticks, and the other is to call the other function do_timer.

Sched.c

Void do_timer (long cpl) {. / / the current thread still has a time slice left, so directly return if ((--current- > counter) > 0) return; / / if there is no remaining time slice, schedule schedule ();} the most important part of do_timer is the above code, which is very simple.

First, take the time slice of the current process-1, and then judge:

If the time slice is still greater than zero, do nothing and return directly.

If the time slice is zero, call schedule (), and you'll know with your feet that this is the backbone of process scheduling.

Scheduling of processes

Don't look at a big pile, I'll make a loose simplification, and you'll understand. Quite simply, this function does three things:

1. Get the process number next with the largest remaining time slice (the value of counter) and in the runnable state (state = 0).

two。 If all runnable process time slices are 0, reassign the counter of all processes (not just runnable's) (counter = counter / 2 + priority), and then perform step 1 again.

3. Finally, I get a process number next, call the switch_to (next) method, and switch to this process to execute.

Switching process

Look at the switch_to method, which is written in inline assembly statements.

Sched.h

# define switch_to (n) {\ struct {long ajar b;} _ _ tmp \ _ _ asm__ ("cmpl% ecx,_current\ n\ t"\ "je 1f\ n\ t"\ "movw% dx,%1\ n\ t"\ "xchgl% ecx,_current\ n\ t"\ "ljmp% 0\ n\ t"\ "cmpl% ecx _ last_task_used_math\ n\ t "\" jne 1f\ n\ t "\" clts\ n "\" 1: "\:" m "(* & _ _ tmp.a)," m "(* & _ _ tmp.b),\" d "(_ TSS (n))," c "((long) task [n])) \} this paragraph is the lowest and lowest code for process switching. It doesn't matter if you don't understand it. In fact, it mainly does two things.

1. Jump to the offset address of the new process through the ljmp jump instruction.

two。 Save the values of the current registers in the TSS of the current process, and load the TSS information of the new process into each register. (this part is a side effect of executing ljmp instructions and is implemented by hardware.)

Simply put, save the current process context, restore the context of the next process, and skip it! What is the context is just the value of a pile of registers he meow.

The above image comes from "Linux Kernel complete comments v5.0"

At this point, we have combed through the entire link of a process switch, let's review it first.

1. The culprit is the timer tick that is triggered every 10ms.

two。 And this tick will give CPU a clock interrupt signal.

3. This interrupt signal will make CPU look up the interrupt vector table and find a clock interrupt handling function do_timer written by the operating system.

4. Do_timer will first change the counter variable of the current process to-1. If the counter is still greater than 0 at this time, it ends here.

5. But if counter = 0, the process is scheduled.

6. Process scheduling is to find all the processes in the RUNNABLE state, find a process with the highest counter value, and throw it into the input parameter of the switch_to function.

7. Switch_to, the ultimate function, saves the current process context, restores the context of the process to be redirected, and causes CPU to jump to the offset address of the process.

8. Then the process began to run comfortably, waiting for the next tick-tock.

All right, I'll draw you a picture. I'll make you lazy.

This is the tick-tock perspective.

2. From the perspective of data structure, we start with a tick, set off a wave, and finish the whole process of tick-tock.

Let's change to a static perspective and look at the data structure.

The main culprit of all the data related to the process comes from this data structure.

Struct task_struct * task [64] = {}; yes, an array of 64 sizes, and the elements in the array are task_struct structures.

Struct task_struct {long state; long counter; long priority; struct tss_struct tss;}; only the key fields that we need to care about are taken here.

State is the state of the process, which is clearly defined in the value linux.

# define TASK_RUNNING 0#define TASK_INTERRUPTIBLE 1#define TASK_UNINTERRUPTIBLE 2#define TASK_ZOMBIE 3#define TASK_STOPPED 4 for example, if the value of state is not RUNNING, it will not be scheduled by the process. This is very clear in the above tick-tick perspective.

Counter and priority record the time slice of the process, counter records the remaining time slice, and priority means priority, which means to assign a value to the initial time slice of the process. This part is also very clear in the code from the tick perspective above.

The last important structure is tss, which is a structure that records process context information.

Struct tss_struct {... Long eip; long eflags; long eax,ecx,edx,ebx; long esp; long ebp;.}; when we talk about the tick perspective, we always talk about the context, what exactly is the context, is actually the value in this structure, is just the value of a pile of registers.

It is also mentioned in the explanation of the ticking perspective that the core step of process switching is a ljmp instruction, the side effect of which will save the values of the current registers in the TSS of the current process, and load the TSS information of the new process into each register, which is the essence of context switching.

So we see that the data mentioned in the data structure perspective is used in the tick-tock perspective.

3, operating system boot process perspective when you press the boot button, the bootstrap program loads the kernel from the hard disk into memory, and after a lot of trouble, it starts to execute the system initialization program init / main.c.

If you are curious about the details of this section, you can read the first few articles in my homemade operating system series.

All right, let's start our journey from this main.c, and of course, we only focus on the relevant parts of the process.

Void main (void) {. / / first step: process scheduling initializes sched_init ();. / / second step: create a new process and do something if (! fork ()) {init ();} / / step 3: endless loop, the operating system officially starts for () pause () The first step is sched_init process scheduling initialization. What should be initialized? It's very simple. I'll pick the main one.

Void sched_init (void) / / initialize the tss set_tss_desc () of the first process; / / clear the process array to for

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.