For process thread scheduling we are certainly not strange, can say two sentences, such as what process is the basic unit of resource allocation, thread is the basic unit of scheduling, process has independent address space, thread has no, thread and process inside other threads to share resources, there is a variety of scheduling strategy. But may be a lot of people on the process thread scheduling internal situation is not very clear, just said that this knowledge is very familiar, have a sense of granted.
This article from a simple thread process scheduling design to help you clear the difference between the process thread, wisp clear scheduling this line.
- Public id: Rand_cs
A thread,
Let’s start with threads. In the POSIX thread standard, threads are created like this, with the following function prototype:
- Thread, used to store the id of a thread
- Attr indicates the type of the thread to be created. The default value is NULL
- Start_routine is a function pointer
- Arg, the function argument, passed to the function pointed to by the function pointer above. Because this parameter is the only one used as a start_routine parameter, the parameter is usually wrapped into a structure and passed.
The core of these four parameters should be the last two parameters, function and its parameters, with which the thread makes sense, right? You can already see from this that a thread is just executing a function. However, this “function” is special in that it can run on the CPU alone, rather than being called by a thread that can run on the CPU.
So a thread is like a carrier that can carry a function to the CPU alone. So what makes a thread so special is that the task is also executing a function, so why can a thread be scheduled to run on the CPU alone? What’s the difference, perhaps inappropriately, between a pile of wood and a wooden cart? It’s because the wooden car has a special structure, so it can drive on its own, but wood? It had to be loaded onto a wooden cart and transported somewhere. Similarly, threads are special compared to functions in that they have special structures, such as PCBS, stacks, register groups, etc.
After understanding the nature of threads, we will specifically design a very simple very simple kernel thread, look at the specific situation inside the thread, from the creation to run through what process, the following formally began to define some data structure of threads:
1, the PCB (task_struct)
PCB, Process Control Block, in a simple word, PCB contains all the necessary information in the running Process of a Process/thread, so PCB is the symbol of the Process/thread, and there is a one-to-one correspondence between them.
In Linux, the PCB of a process thread is defined by the task_struct structure, so there is no strict distinction between a process and a thread in Linux. Threads are also called lightweight processes.
What information will be stored in the PCB? To quote the following “Operating System Essentials and Design Principles”, the PCB will store the following information:
Identifier: A unique identifier associated with a process that distinguishes the executing process from other processes. State: Describes the state of the process. Since the process has several states, such as suspended, blocked, running, etc., there is an identifier to record the execution state of the process. Priority: If several processes are executing, it is a matter of the order in which the processes are executed, depending on the process priority identifier. Program counter: Address of the next instruction to be executed in a program. Memory Pointers: Pointers to program code and process-related data. Context data: data in the registers of the processor while the process is executing. I/O status information: includes the displayed I/O requests, I/O devices assigned to the process, and the list of files used by the process. Billing information: including processor time summation, billing number, etc.
The task_struct structure in Linux today is defined in hundreds of lines of code, and contains many more structures, all extended to thousands of lines. We only define a few elements here, so we can understand the basic principles of threading. The first version of task_struct defines the following:
We defined the stack, the state, the name of the thread. Threads also have their own state, which is defined as follows:
We won’t use that many states in this article, just RUNNABLE and RUNNING.
And then it identifies the thread by name, and then it defines a stack, and each thread has its own stack, and notice that the stack pointer is the first element of the thread PCB, which is used for special purposes, and will say later, just for reference.
In addition, our PCB information is very little, just a demonstration of the principle, and the stack is not too big, so we directly put the kernel stack and PCB on the same page, the top as the stack, the bottom as the PCB. The layout is as follows:
2. Definition of stack
The previous definition of the thread PCB, relatively simple, difficult in the stack definition, to be precise, is the stack partition when the thread is created. Thread creation is closely related to execution, which can be divided into two types: first run and non-first run. All the data structures, resources, and so on of the non-first run thread are already there and do not need to be defined manually. The information required for the first run must be set manually. For consistency, we should create a thread that mimics the structure of the non-first run.
So what is the structure of the non-first runtime thread? If a thread wants to get to the CPU, it must be scheduled, and who triggers the scheduling? We are only concerned here with scheduling due to clock interrupts. The structure of the kernel stack for threads should be clear, down from the top: interrupt stack frames, the return address of the parameters of the function call, and the context of the scheduler. It doesn’t matter that I feel vague and abstract at present. I have a general impression. After reading this article, I will feel suddenly enlightened.
Interrupt stack frame
This is the interrupt stack frame, where the context information is stored during an interrupt. We have already talked about interrupts in detail, but we have not said where these registers are stored. Now it is clear that these registers are stored in the kernel stack. We define all the registers here just for the sake of unification, but in fact only the necessary registers will be pushed in for efficiency. If you are not familiar with it, you can turn over the previous three articles, interrupt, clock and keyboard, which will not be described here.
Parameter address
Next, define the second part, parameters and addresses, which are essential for the thread to run. The second part is closely related to the first time a thread runs, so let’s talk about how it runs for the first time. The execution of a thread is the execution of a function. If a function is executed, the execution flow has changed. If the execution flow has changed, the value of cs: eIP has changed. There are only three instructions to change the value of CS: EIP: Call, RET and JMP. In general, we use the Call instruction for function call, but in order to be consistent with the later scheduling, we use the RET instruction for function run.
Let’s take a closer look at ret instructions. Ret instructions are actually equivalent to POPL % EIP, so the process is divided into two steps:
- Modify the EIP to store the value at the top of the stack in the EIP register. Eip stores the address of the next instruction, so when using ret instruction, the top of the stack must be the address of the instruction, otherwise there will be an error, usually the address of the next instruction of the call instruction of the calling function.
- Add 4 esp.
So we can mimic a function call, set the stack frame ourselves, put the address of the function to be executed at the top of the stack, and then we can return the function to be executed.
What does the stack frame look like when the function is called? So just to review, this has to do with calling conventions,The default c convention is CDEClTo take a simple example of how c calls a function, let’s say funcA calls funcB(param1, param2).
The stack looks like this:
To sum up, a function is called by pressing the parameters needed by the called function from right to left, leaving the return address of the calling function (the address of the next instruction in the call instruction), and then jumping to execute the called function. The function returns after execution, and the calling function cleans up the stack space occupied by parameters. Because of the calling convention, the called function knows that the return address is the argument, and the runtime will go to the appropriate place to fetch the argument and execute it.
This is how the function executes, and this is what our thread emulates the first time it runs. That is, we need to put the thread function parameters on the stack first, and then leave a dummy address, which is not used, just placeholder. As mentioned before, the return address is the parameter, we have to follow this convention, although we do not use the return address, but still have to set to form the correct stack frame. We then place a pointer to the function, ret, which is the top of the stack, and execute the function, and the thread runs. It is important to note here that ret is the thread function pointer at the top of the stack and not the return address we set
The typical function prototype passed by a thread is:
So the data structure that needs to be defined in the second part of the stack is almost clear, as follows:
This structure is only used for the first run by the thread, and will never be used again, because we are imitating a function call, and there is a real function call after the run, so we don’t need to use this structure, although the structure may be different, except that there is one more element than the function call, the function pointer eIP.
Scheduler context
Finally, we come to the third part, which defines the context of the scheduler. Why do we define this? It has to do with scheduling. So it’s important to state in advance the following scheduler, regardless of operating system, what the scheduler does boils down to two steps:
- Pick a thread
- Switch threads
Our scheduler is the schedule() function and the switch function is SWTCH (cur, next). Switching threads involves low-level operations, and it’s much easier to write directly using assembly instructions, where you have to do everything yourself, rather than having a compiler compile it for you in a high-level language. Compiler compilations follow certain rules, such as the calling convention described above. The switch function we wrote will be called in c files, so to be called correctly requires our own assembly to follow convention as well.
Here we need to follow a rule, ABI, Application Binary Interface, Application Binary Interface. Unlike the familiar API, it is a more low-level set of rules, a compilation convention. For example, the above calling convention is ABI. The ABI specifies which registers to hold for the called person, including EBX, EBP, ESI, EDI, esp. The five registers belong to the calling function. The called function needs to save these registers in order not to break the register structure of the calling function.
Hence the following context structure:
Here we define only four registers, not ESP, because ESP is guaranteed by the calling convention, and esp is stored in the Kstack, more on that later.
Finally, the structure of the thread creation needs to be defined, the following to create a specific thread, pseudo-code is as follows:
See a detailed flow chart to help understand:
Pseudo code with flow chart should be very clear, I will not explain the explanation.
3. Thread running
The thread_exec(thread) function does not exist because threads need to be scheduled to run on the CPU. The first run of a thread is very special. It is run by return. The pseudo-code is as follows:
The top of the thread kernel stack is assigned to the ESP register, then the four registers defined in the context are popped, and ret is returned to execute the thread function.
When ret, the top element of the stack is the address of the thread function. Assigning it to eIP changes the execution flow and executes the thread function. Due to function calling conventions, thread functions know that the current top of the stack is the return address, which is preceded by the argument. Of course, this is when the function is first run, usually there is a pushl %ebp step in the function, then the top of the stack is not the return address. Anyway, because of convention, functions can find the arguments they need and execute them. For those unfamiliar, take a closer look at 32-bit machine function calls.
Second, the scheduling
Finish the creation and operation of the thread, then said the task scheduling, process aspects of the problem in the back, because the process is more than the thread some things, so the process can be realized on the basis of the thread. So processes are much easier to understand once you understand thread execution and scheduling.
Without further ado, the schedule() function does two main things
- Select the next thread
- Call the thread switching function switch(cur, next)
1. Select a thread
First thing: Pick a thread. This raises two questions:
- Where can I choose?
- The principle of selection?
PCB is the identification of the thread, which records all the information needed by the thread. If we gather the PCB of all threads, there will be a place to choose. Here we string the PCB’s of all threads together in a queue, set this queue to ready_queue. This requires adding a queue node to the task_struct.
The principle of selection is the scheduling strategy. Let’s use “priority slice rotation” as an example. Because I think it’s more like slice rotation, but with a little bit of priority, so that’s the name. Here you need to add priority to the PCB for the priority and ticks for the number of clock ticks that can still run.
So now the PCB looks like this:
We will only discuss thread scheduling triggered in the event of a clock interrupt. Clock interrupt is not specific, not familiar with the time management master can look at the previous article. The previous article only briefly described the clock interrupt handler function, this article to add some material.
Our scheduling policy is as follows: priority represents the number of ticks that can be run on the CPU per thread, ticks records the number of ticks that the thread can continue to run, and each clock interrupt ticks decreases by 1. If it reaches zero, the scheduler is called. The pseudocode is as follows:
Next is the schedule function, first directly look at the pseudocode, our scheduling policy is very simple, and only discuss the situation that the time slice runs out, directly look at the code almost understand
The flow should be clear, just two things: get_cur_thread() and tag2thread(), both of which are used to get task_struct. The task_struct* element is an address value that points to the bottom of the page of memory, so its lower three bits should be zero.
The kernel stack and task_struct are on the same page. Esp points to the top of the stack, which is also an address value. The task_struct* thread is the current task_struct* thread. The same goes for converting a tag to a thread. Isn’t that neat? I was surprised when I saw this. It was so simple and clever, given how long it took to get the current process muddled in Xv6.
A ready_queue is a ready queue that holds all the node elements of a task_struct to string together all the state bits of a RUNNABLE task_struct. This aspect is a simple application of a data structure queue without further details. There is only one ready queue, in the actual system there should be multiple queues, such as all processes/threads queue, depending on the scheduling strategy may also have multi-level priority queue, etc.
2, SWTCH (cur, next)
Let’s start with the code:
It’s a classic function, and it’s almost exactly the same in Xv6. Let’s take a closer look at the stack when we call SWTCH:
1. The first two MOV instructions fetch cur, and next is stored in eAX and EDX registers
2. Four push instructions hold the context. This is an ABI rule that requires the caller to hold these registers
3, then movl %esp, (%eax) store the current thread stack top value, esp is also one of the registers, in addition to the call convention, there is a save location here, just different from the other 4 registers.
Take a look. Where is it? Task_struct (%eax) = kstack (%eax) = kstack (%eax); That’s what Kstack is all about, pointing to the top of the stack. And that’s why kstack is the first element of task_struct.
Movl (%edx) = kstack (%edx) = kstack (%edx) = kstack (%edx) This is the most critical stack switching step.
5. Then four POPL instructions pop up the next scheduling context, causing ESP to point to the return address in the next stack. Finally, RET returns, and the thread is switched.
Note next, which is highlighted. After step 4, the stack has switched and everything that pops up is next’s.
The thread execution function is written to mimic SWTCH, so threads can be added to the ready queue in the future. CPU execution is officially performed by the scheduler.
Let’s take a look at the kernel stack change diagram carefully:
The above is the whole process of thread switch scheduling, which can solve the problem of why the thread first run so layout, is to facilitate the operation of consistency.
Three, processes,
The above thread creation, running, switching has finished, let’s talk about the process, process we briefly here, about the knowledge of the process or a lot of, including privilege level, memory layout, user state and so on, in this we just talk about the process and thread what are the actual differences.
1. Separate address space
By now it should be clear from most books that processes simply have a few more things than threads, most importantly their own virtual address space.
Threads have very limited resources, only a stack on which to set up interrupt stack frames, run the necessary context, etc., which is usually referred to in books as register resources. The process has the entire virtual address space, the entire 4 GB, and there’s a lot of stuff it can build on it, including stacks, data snippet, and even resources owned by the thread, which is why the thread is dependent on the process.
The main difference between a process and a thread is that it does not have its own address space. The other mechanisms of a process are based on the address space.
As mentioned earlier, the process is implemented thread by thread, so the process thread uses the same task structure, except that the pgDIR of the process has the actual value, while the pgDIR of the thread is set to NULL.
2. Privilege level 3 Works in user mode
Another feature of a process is that it runs at privilege level 3. The process is created in kernel mode. If a process is scheduled, it needs to return to user mode from kernel mode and switch from high privilege level to low privilege level. The CPU generally does not allow switching from a higher privilege level back to a lower privilege level, with the exception of an interrupt return.
Thread execution mimics a function call and then returns to execution, whereas here we go to privilege 3 and mimic an interrupt and then returns to privilege 3, which is exactly the same thing. The thread structure of the interrupt stack frame has been defined, so we will not go into it here. We will look directly at the process creation.
Process creation
In this case, we will only describe the initial init process, because all the subsequent processes are children of the init process, through system calls such as fork, exec, etc., which involves a lot of content. I will write a separate article on creating a new process.
The init process is created on top of a thread, so there are no fewer steps to create a thread. The pgDIR of a process has an actual value, so pgDIR must be initialized in thread_init.
The remaining big difference lies in filling interrupt stack frames. The thread we implemented above just runs in the kernel and does not return to the user state step, so there is no filling interrupt stack frames. Filling a stack frame is like filling a function pointer, parameter, and return address when creating a thread, just to install the image and facilitate the return execution. Here we populate the interrupt stack frame with the interrupt stack. This is where we use the space we’ve been reserving for interrupts.
But there’s one more question. Our process is implemented on top of a thread. How does a thread work? When the dispatcher context pops up, ret returns to the execution thread function. If we do not change the ret, the execution stream will go somewhere else and there is no chance to interrupt the return. So we need to change the thread function to fill the interrupt stack frame, which also has eIP, so we put the entry address of the program here. This allows thread scheduling to run consistently while filling interrupt stack frames and then returning interrupts.
To sum up, let’s outline the steps required to create a process:
- Create thread, thread function used to fill interrupt stack frame
- Create a page table required by the process and switch the page table during scheduling
After a recognition, to see the specific pseudo-code:
Let’s look at the flowchart to help understand. The other part of the flowchart is the thread creation flowchart:
After the interrupt stack frame has been created, we can interrupt back. In this case, we directly jump to intr_exit to execute. This function is described in the previous article, which is the reverse process of breaking the stack. So much for process creation, and then for scheduling, you need to make some changes
Changes are minimal; the process has its own page table, so it needs to switch the page table. The page table switch is to load the page directory address into the CR3 register, as described in the previous page address translation article.
Iv. Design Instructions
On the process thread scheduling a simple design to this end, this design ideas mainly from the operating system image restoration, integration of XV6, Linux0.11 some ideas, as well as their own thinking. This design idea should be the simplest, although simple enough to let us understand the nature of the process thread scheduling.
1. Stack description
About this design private thought said or clear enough, if not understand can seize the stack, stack top, no matter which system source code, I think, as long as the stack changes, the top of the stack to figure out the change, the problem is solved. A few more words about stacks:
kstack
The kstack element is designed to point to the top of the stack, although it is intended to point to the top of the stack. Remember that this is a variable that we have defined in memory. It cannot point to the top of the stack at all times. Mainly I have stumbled in the above, explain to warn myself and hope that we do not make such a stupid mistake as I did.
Save the top value of the kernel stack when switching from kernel mode to user mode
It is mainly said that the top value of the stack should be recorded at the ESP0 position in the TSS structure when the interrupt is returned, which is not involved in the above pseudocode, because the relevant knowledge and details need to be explained quite a lot, and will be discussed in detail later. For a brief explanation, when switching from user mode to kernel mode, you need to switch to the kernel stack. The top value of the kernel stack is stored in TSS.esp0, which is automatically fetched by the CPU.
Kernel threads, lightweight processes, user threads
The thread we created above is a kernel thread and only runs in kernel mode, not user mode.
Lightweight processes are kernel-supported user threads, an abstraction of kernel threads. Each lightweight process is associated with a kernel thread to implement kernel-supported user threads. This association is now done by NPTL, which is POSIX compliant.
However, all the work of the user thread from beginning to end, such as the creation of scheduling, is independent of the kernel, only in the user state, the kernel does not support.
The kernel supports or does not support the thread, which can be added to the kernel’s ready queue and scheduled by the kernel’s scheduler if it is created. In contrast, the normal user thread is invisible to the kernel. The kernel only sees the whole process and only adds the process to the ready queue. After scheduling the process, the scheduler in user mode schedules the user thread.
So kernel threads are the most basic requirement in order to really implement threading. User threads supported by the kernel – Lightweight processes and kernel threads are injective, with each lightweight process having a kernel thread corresponding to it. This is often referred to as the one-to-one model. However, the CPU scheduling entity of ordinary user threads is still a process, and the whole process only corresponds to a kernel thread, that is, multiple user threads in the process also correspond to a kernel thread, which is the many-to-one model.
Five, the summary
A thread is a function that runs on a queue and is scheduled to run because of the PCB, stack, etc. A process is implemented on top of a thread, the main difference being that it has its own virtual address space, the page table, and then runs in the 3-privileged user state.
1. Explanation of common problems
Processes are the smallest unit of resource allocation and threads are the smallest unit of scheduling
The process has its own virtual address space, which contains various resources, such as heap, stack, various segments, and even some necessary resources of the thread, which are actually a part of the virtual address space. So processes are the smallest unit of resource allocation.
Thread? A thread is a stream of execution that executes a function, and it depends on the process because, as mentioned above, resources are managed by the process. So if a process has only one flow of execution, it can be considered a thread. If there are multiple threads that are supported by the kernel, each thread can be scheduled separately by the kernel. What about multiple normal user threads? From the kernel, the scheduling entity is indeed the whole process. From the user state, the scheduling is a thread in the process.
The average user thread has different opinions. Don’t get too caught up in theory. Be able to simulate in your mind roughly how the process thread is created, how to schedule on the line. And most operating system kernels today support threading. So in general processes are really the smallest unit of resource allocation, and threads are the smallest unit of scheduling.
Thread speed
The principle that threads can speed up a program is that multiple threads can execute in parallel, if there is only one CPU, that is pseudo-parallelism, and it can speed up.
For example, there are two processes A and B, A has three threads, A, B, C, and B has only one stream of execution. Therefore, when scheduling, A has three nodes in the ready queue that can be scheduled, and B has only one node, so A must run faster than B.
But be aware that with only one CPU, a multithreaded process should run for more time than a single-threaded process due to the overhead of thread switching. Just saying that multiple threads can seize more time slice resources and run more efficiently.
** The use of multithreading also has A point to speed up, is the case of blocking, such as A process A if blocked, BC two threads can run normally. ** If B runs somewhere and blocks, B’s entire process is blocked. Of course, this is also a discussion of user threads supported by the kernel. If it is a normal user thread, one thread blocking will cause the whole process to block, because the kernel does not feel multiple threads.
2, the final conclusion
The problem of process thread scheduling is easier to understand if it is only studied at a higher level, such as in an operating system class. But may feel fuzzy abstract, or is the knowledge point is very familiar with the sense of granted. And to really get a clear picture, you have to look at the code and see how it’s designed.
The design is not so simple, we need to take into account all aspects of the logic connection, for example, the design of the thread running for the first time in this paper, the way to enter the 3 privilege level, are designed to imitate the corresponding structure, so that the system before and after the consistency.
This paper is equivalent to the design of the predecessors to do a streamlined processing, hidden a lot of details, some places are not quite standard, but also forgive me. For example, assembly mixed with C, although there is inline assembly support but useless, just as pseudo-code. Process thread scheduling is closely related to the content of the three blocks, can not be more than seven thousand words can tell clearly, but I think the most basic principle should be said or more clear.
Ok, this article is here, if there is wrong or insufficient, but also please criticize;
Like the friends of this article also please like, follow the public account Rand_cs can get more about the system of high-quality articles, there are all kinds of e-books about the computer, you can always find what you need, hurry up to pay attention to it
