The Master said, “The superior man does not seek satiety in food, does not seek safety in habitation, is quick in matters and cautious in speech, and is in the right way. It can be said that he is eager to learn.” Analects of Confucius: Study and write

A hundred blog series. This paper is: the v06. Xx HongMeng kernel source code analysis (scheduling queue) | how many scheduling are the kernel queue

Task management related articles are:

  • V03. Xx HongMeng kernel source code analysis (the clock) whose biggest contribution | trigger scheduling
  • V04. Xx HongMeng kernel source code analysis (scheduling) | is the kernel task scheduling unit
  • V05. Xx HongMeng kernel source code analysis (task management) | pool of task is how to manage
  • V06. Xx HongMeng kernel source code analysis (scheduling queue) | how many scheduling are the kernel queue
  • V07. Xx HongMeng kernel source code analysis (scheduling) scheduler | task is how to
  • V21. Xx HongMeng kernel source code analysis concept (thread) | who is constantly with the CPU
  • V25. Xx HongMeng kernel source code analysis (concurrent parallel) | heard countless times two concepts
  • V37. Xx HongMeng kernel source code analysis (system calls) | forever mantra
  • V41. Xx HongMeng kernel source code analysis (task switching) switch | see how assembly task

Why schedule queues alone?

There are two source files in the Hongmun kernel code about queues, one for scheduling and the other for IPC queues for interthread communication.

Again, LOS_DL_LIST is so important that it’s key to understanding the kernel that it’s fair to say it’s the most important code. The source code appears in the sched_SQ module, indicating that it’s used for scheduling tasks. The sched_SQ module has only two files, the other los_sched.c is the scheduling code.

Involves the function

There are 32 ready queues for each kernel process and thread. The queue is stored in global variables and queued when the process is created. The task queue is placed in a threadPriQueueList of the process.

Map uncle Zhang’s story: Ready queue is lined up outside the 32 channel, priority 0-31 in turn arranged in a row, uncle zhang’s office has a brand, scoreboard, such as playing basketball, a total of 32, air and corresponding card is 1, some people in the queue is not 0, so uncle zhang started watching from 0 bit at a time and see the first one the man that is the highest priority. The scoreboard in the office is a bitmap scheduler.

Bitmap scheduler

/ / * 0 x80000000u = 10000000000000000000000000000000 (32, 1 is used to shift, the design of sophisticated, thumb up)
#define PRIQUEUE_PRIOR0_BIT   0x80000000U 
LITE_OS_SEC_BSS LOS_DL_LIST *g_priQueueList = NULL; // All the queue raw Pointers
LITE_OS_SEC_BSS UINT32 g_priQueueBitmap; // Bitmap scheduling
Copy the code

Los_priqueue. c has only two full variables. One is LOS_DL_LIST *g_priQueueList, which is a pointer to the head of the 32 ready queues. Is a 32-bit variable called the bitmap scheduler. How do you understand it?

The scheduling of hongmeng system is preemptive, task is divided into 32 priorities, how to quickly know which queue is empty, which queue has a task that needs an identity, and to achieve extremely efficiently? The answer is: bitmap scheduler. Check out this series of articles devoted to bitmap management. Simply put, it is the bit of a variable to mark whether there is a task in the corresponding queue. Under bitmap scheduling, the smaller the task priority is, the higher the priority is. Whenever scheduling is required, the position of the first bit set to 1 is found from the lowest bit to the highest bit, which is the current highest priority. Then, the corresponding task control block is obtained from the corresponding priority ready queue. The implementation complexity of the whole scheduler is O(1), that is, no matter how many tasks, the scheduling time is fixed.

Process ready queue mechanism

CPU execution speed is fast, its computing speed and memory read and write speed is an order of magnitude difference, and hard disk read and write is exponential. By default, a time slice in the Hongmeng kernel is 10ms. The resource is very precious. It constantly switches back and forth among many tasks, so the CPU must not wait for the task. This is how process and thread ready queues work. There are 32 task ready queues because threads have a default priority of 32, and each queue contains tasks of equal priority. What does queue initialization do? Look at the code in detail

#define OS_PRIORITY_QUEUE_NUM 32

// The internal queue is initialized
UINT32 OsPriQueueInit(VOID)
{
    UINT32 priority;

    /* system resident resource */// Resident memory
    g_priQueueList = (LOS_DL_LIST *)LOS_MemAlloc(m_aucSysMem0, (OS_PRIORITY_QUEUE_NUM * sizeof(LOS_DL_LIST)));Allocate 32 queue head nodes
    if (g_priQueueList == NULL) {
        return LOS_NOK;
    }

    for (priority = 0; priority < OS_PRIORITY_QUEUE_NUM; ++priority) {
        LOS_ListInit(&g_priQueueList[priority]);// The queue is initialized with a pointer to itself
    }
    return LOS_OK;
}
Copy the code

Since tasks have 32 priorities, the kernel creates 32 bidirectional linked lists at one time during initialization. Each priority has a queue to record the position of ready tasks. G_priQueueList allocates a contiguity block of memory holding 32 bidirectional linked lists

Several common functions

Look at the source code for joining and leaving the team, and pay attention to the bitmap changes!

As you can see from the code, LOS_ListTailInsert is called, noting that the TASK is inserted from the end of the circular list, i.e. the TASK of the same priority is executed last, as long as it is inserted from the end each time, it forms a queue for execution in order. Hongmeng kernel design is very clever, with very little code, very high efficiency to implement the queuing function.

VOID OsPriQueueEnqueue(LOS_DL_LIST *priQueueList, UINT32 *bitMap, LOS_DL_LIST *priqueueItem, UINT32 priority)
{
    /* * Task control blocks are inited as zero. And when task is deleted, * and at the same time would be deleted from priority queue or * other lists, task pend node will restored as zero. */
    LOS_ASSERT(priqueueItem->pstNext == NULL);

    if (LOS_ListEmpty(&priQueueList[priority])) {
        *bitMap |= PRIQUEUE_PRIOR0_BIT >> priority;// Set the priority bit to 1
    }

    LOS_ListTailInsert(&priQueueList[priority], priqueueItem);
}

VOID OsPriQueueEnqueueHead(LOS_DL_LIST *priQueueList, UINT32 *bitMap, LOS_DL_LIST *priqueueItem, UINT32 priority)
{
    /* * Task control blocks are inited as zero. And when task is deleted, * and at the same time would be deleted from priority queue or * other lists, task pend node will restored as zero. */
    LOS_ASSERT(priqueueItem->pstNext == NULL);

    if (LOS_ListEmpty(&priQueueList[priority])) {
        *bitMap |= PRIQUEUE_PRIOR0_BIT >> priority;// Set the priority bit to 1
    }

    LOS_ListHeadInsert(&priQueueList[priority], priqueueItem);
}

VOID OsPriQueueDequeue(LOS_DL_LIST *priQueueList, UINT32 *bitMap, LOS_DL_LIST *priqueueItem)
{
    LosTaskCB *task = NULL;
    LOS_ListDelete(priqueueItem);

    task = LOS_DL_LIST_ENTRY(priqueueItem, LosTaskCB, pendList);
    if (LOS_ListEmpty(&priQueueList[task->priority])) {
        *bitMap &= ~(PRIQUEUE_PRIOR0_BIT >> task->priority);// The queue is empty and the priority bit is set to 0}}Copy the code

Can threads in the same process have different priorities?

Please think about this problem for a moment.

Process and thread is a one-to-many father-son relationship, the unit of kernel scheduling is task (thread), hongmu-kernel task and thread is one thing, but different identity. A process can have multiple threads, and threads have their own independent states, so how to define the state of the process? For example, ProcessA has two threads, TaskA(blocked) and TaskB(ready). Is ProcessA in the blocked or ready state?

Read the official documentation first and then read the source code.

Description of process status migration:

  • Init – > Ready:

    When a process is created or forked, it enters the Init state after receiving the process control block and is in the process initialization stage. When the process initialization is complete, the process is inserted into the scheduling queue and the process enters the ready state.

  • Ready to Running:

    After a process is created, it enters the ready state. When a process switchover occurs, the process with the highest priority in the ready list is executed and enters the running state. If there is no other thread in the ready state, the process is deleted from the ready list and only in the running state. If there are other threads in the ready state, the process is still in the ready queue. At this time, the ready state and running state of the process coexist.

  • Running to Pend:

    When all threads in a process are blocked, the process synchronously enters the blocked state when the last thread becomes blocked, and then a process switch occurs.

  • Pend – Ready/Pend – Running:

    When any thread in the blocked process restores to the ready state, the process is added to the ready queue and synchronized to the ready state. If process switchover occurs at this time, the state of the process changes from the ready state to the running state.

  • Ready to Pend:

    When the last ready thread in the process is blocked, the process is removed from the ready list and the process changes from ready to blocked.

  • Running – > Ready:

    A process can change from a running state to a ready state in either of the following ways:

    1. After a process with a higher priority is created or restored, process scheduling occurs. At this moment, the process with the highest priority in the ready list becomes running, and the previously running process changes from running state to ready state.
    2. If a process with a SCHED_RR scheduling policy exists and another process with the same priority is in ready state, that process goes from running to ready state and another process with the same priority goes from ready to running when its time slice runs out.

  • Running – > Zombies:

    When the main thread or all threads of a process finish running, the process changes from running state to zombie state and waits for the parent process to reclaim resources.

As you can see from the documentation, a process can coexist in two states.

    UINT16               processStatus;                /**< [15:4] process Status; [3:0] The number of threads currently running in the process */

    processCB->processStatus &= ~(status | OS_PROCESS_STATUS_PEND);// take the inverse and bit operation
    processCB->processStatus |= OS_PROCESS_STATUS_READY;// or bit operations
Copy the code

How can you store two states in one variable? The answer is to keep it bitwise. Remember g_priQueueBitmap above, which stores 32 states. In fact, this is common in the kernel source of any system, as well as left shift <<, right shift >> and so on

Continuing with the relationship between processes and threads, must threads have the same priority as processes? Can they be different? The answer is: of course not, otherwise there would be no function to set task priority. In fact, a task has a special bitmap to record its previous priorities. For example, if a task is blocked during the scheduling process, the kernel usually increases the priority of the task holding the lock so that it can be selected by the next schedule with the maximum probability to quickly release the lock resources.

The task scheduler.

What really makes the CPU work is the task. A process is just a container for a task. A task has stack space, and the process structure LosProcessCB has one. You can tell by the name. It’s related to dispatch.

    UINT32               threadScheduleMap;            /**< The scheduling bitmap table for the thread group of the process */
    LOS_DL_LIST          threadPriQueueList[OS_PRIORITY_QUEUE_NUM]; /**< The process's thread group schedules the priority hash table */
Copy the code

There are 32 queues in the structure of the process, which is the ready state queue of the task. ThreadScheduleMap is the process’s own bitmap scheduler. See process into the team and out of the team source code. The process of scheduling is to find the process with the highest priority in the ready queue and then find the thread with the highest priority in the process to schedule. Look at OsGetTopTask, which I consider the most beautiful function in the kernel, and see how the ready queue is managed.

LITE_OS_SEC_TEXT_MINOR LosTaskCB *OsGetTopTask(VOID)
{
    UINT32 priority, processPriority;
    UINT32 bitmap;
    UINT32 processBitmap;
    LosTaskCB *newTask = NULL;
#if (LOSCFG_KERNEL_SMP == YES)
    UINT32 cpuid = ArchCurrCpuid(a);#endif
    LosProcessCB *processCB = NULL;
    processBitmap = g_priQueueBitmap;
    while (processBitmap) {
        processPriority = CLZ(processBitmap);
        LOS_DL_LIST_FOR_EACH_ENTRY(processCB, &g_priQueueList[processPriority], LosProcessCB, pendList) {
            bitmap = processCB->threadScheduleMap;
            while (bitmap) {
                priority = CLZ(bitmap);
                LOS_DL_LIST_FOR_EACH_ENTRY(newTask, &processCB->threadPriQueueList[priority], LosTaskCB, pendList) {
#if (LOSCFG_KERNEL_SMP == YES)
                    if (newTask->cpuAffiMask & (1U << cpuid)) {
#endif
                        newTask->taskStatus &= ~OS_TASK_STATUS_READY;
                        OsPriQueueDequeue(processCB->threadPriQueueList,
                                          &processCB->threadScheduleMap,
                                          &newTask->pendList);
                        OsDequeEmptySchedMap(processCB);
                        goto OUT;
#if (LOSCFG_KERNEL_SMP == YES)
                    }
#endif
                }
                bitmap &= ~(1U << (OS_PRIORITY_QUEUE_NUM - priority - 1));
            }
        }
        processBitmap &= ~(1U << (OS_PRIORITY_QUEUE_NUM - processPriority - 1));
    }

OUT:
    return newTask;
}
Copy the code

Map the story of Uncle Zhang: Uncle Zhang shouted to zhang Quan Egg when entering the performance, Zhang Quan egg to decide which program to perform first, but also check his list of priorities, it also has a uncle Zhang with the same scoreboard, so simple.

Intensive reading of the kernel source code

Four code stores synchronous annotation kernel source code, >> view the Gitee repository

Analysis of 100 blogs. Dig deep into the core

Add comments to hongmeng kernel source code process, sort out the following article. Content based on the source code, often in life scene analogy as much as possible into the kernel knowledge of a scene, with a pictorial sense, easy to understand memory. It’s important to speak in a way that others can understand! The 100 blogs are by no means a bunch of ridiculously difficult concepts being put forward by Baidu. That’s not interesting. More hope to make the kernel become lifelike, feel more intimate. It’s hard, it’s hard, but there’s no turning back. 😛 and code bugs need to be constantly debug, there will be many mistakes and omissions in the article and annotation content, please forgive, but will be repeatedly amended, continuous update. Xx represents the number of modifications, refined, concise and comprehensive, and strive to create high-quality content.

Compile build The fundamental tools Loading operation Process management
Compile environment

The build process

Environment script

Build tools

Designed.the gn application

Ninja ninja

 Two-way linked list

Bitmap management

In the stack way

The timer

Atomic operation

Time management

 The ELF format

The ELF parsing

Static link

relocation

Process image

 Process management

Process concept

Fork

Special process

Process recycling

Signal production

Signal consumption

Shell editor

Shell parsing
Process of communication Memory management Ins and outs Task management
spinlocks

The mutex

Process of communication

A semaphore

Incident control

The message queue

 Memory allocation

Memory management

Memory assembly

The memory mapping

Rules of memory

Physical memory

 Total directory

Scheduling the story

Main memory slave

The source code comments

Source structure

Static site

 The clock task

Task scheduling

Task management

The scheduling queue

Scheduling mechanism

Thread concept

Concurrent parallel

The system calls

Task switching
The file system Hardware architecture
File concept

The file system

The index node

Mount the directory

Root file system

Character device

VFS

File handle

Pipeline file

 Compilation basis

Assembly and the cords

Working mode

register

Anomaly over

Assembly summary

Interrupt switch

Interrupt concept

Interrupt management

HongMeng station | into a little bit every day, the original is not easy, welcome to reprint, please indicate the source.