Abstract: This article will introduce the reader to the hongmeng light kernel M core source code important data structure, task based on Priority ready Queue.

This article is shared from huawei cloud community “Hongmeng light kernel M core source code analysis series three data structure – task ready queue”, original author: zhushy.

This article introduces the reader to an important data structure in the Hongmeng Light kernel M core source code, the Priority Queue, which is a priority-based task ready Queue.

During the presentation, we will combine the relevant drawings of data structures to cultivate readers’ ability to visualize data structures on a plane and help them better learn and understand the usage of these data structures. The source code covered in this article, such as the OpenHarmonyLiteOS-M kernel, is available at the open source site gitee.com/openharmony… To obtain.

1. Task ready queue

Ready queue is an important data structure in task scheduling module. After the task is created, it enters the ready state and is put into the ready queue. In the Hongmeng Light kernel, the ready queue is a bidirectional array of circular lists, each array element is a list, and tasks of the same priority are placed in the same list.

Task ready Queue The PriorityQueue is mainly for internal use and is not involved in service development. Therefore, no external interface is provided. Bidirectional circular list arrays make it easier to schedule tasks based on priority. The core code for the task-ready queue is in the kernel\ SRC \los_task.c file.

1.1 Definition of the Task Ready queue

The main variables related to the task ready queue are defined in the kernel\ SRC \los_task.c file.

The source code is as follows:

⑴ LITE_OS_SEC_BSS LOS_DL_LIST *g_losPriorityQueueList = NULL; ⑵ static LITE_OS_SEC_BSS UINT32 g_priqueueBitmap = 0; ⑶ #define PRIORity_queue_prior0_bit (UINT32)0x80000000 ⑷Copy the code

(1) refers to the task ready queue, which is a bidirectional linked list array. When the array is initialized, the array length will be set to the OS_PRIORITY_QUEUE_PRIORITYNUM defined in (4). ⑵ indicates the priority bitmap, which identifies the priorities of the mounted ready tasks in the task ready queue; ⑶ is the bit of priority 0; ⑷ indicates the number of priorities supported by the task-ready queue (32). Therefore, the priority of the Hongmeng Light kernel ranges from 0 to 31. The smaller the value, the greater the priority.

G_priqueueBitmap (bit=31-priority); G_losPriorityQueueList [priority] contains the OS_PRIORITY_QUEUE_PRIORITYNUM array elements, each of which is a bidirectional list. All tasks in the ready state of the same priority are mounted to the bidirectional linked list of the corresponding priority.

The schematic is as follows:

2. Task ready queue operation

2.1 Initializing the Task Ready Queue

The task ready queue initialization function is OsPriQueueInit(), which is called during system initialization, and the path is: C :LOS_KernelInit() –> kernel\ SRC \los_task.c:OsTaskInit()–> OsPriqueueInit().

The source code is as follows:

STATIC UINT32 OsPriqueueInit(VOID) { UINT32 priority; ⑴ UINT32 SIZE = OS_PRIORITY_QUEUE_PRIORITYNUM * sizeof(LOS_DL_LIST); g_losPriorityQueueList = (LOS_DL_LIST *)LOS_MemAlloc(m_aucSysMem0, size); if (g_losPriorityQueueList == NULL) { return LOS_NOK; } for (priority = 0; priority < OS_PRIORITY_QUEUE_PRIORITYNUM; + + priority) {2 LOS_ListInit (& g_losPriorityQueueList [specify]); } return LOS_OK; }Copy the code

(1) Calculate the memory size required by the ready queue array, and then apply for memory for the task ready queue. The memory occupied is the memory size required by the BIdirectional linked list of OS_PRIORITY_QUEUE_PRIORITYNUM. During the operation, this memory will not be released and is the resident memory of the system. The code at (2) initializes each array element as a bidirectional circular list.

2.2 Task Ready queue insertion

The task ready queue insertion function is OsPriqueueEnqueue(), which inserts tasks in the ready state into the end of the task ready queue. In the task ready queue, the task at the head of the queue is called first and the task at the end of the queue is called last.

The source code is as follows:

STATIC VOID OsPriqueueEnqueue(LOS_DL_LIST *priqueueItem, UINT32 priority) {(1) if (LOS_ListEmpty (& g_losPriorityQueueList (priority))) {2 g_priqueueBitmap | = (PRIQUEUE_PRIOR0_BIT >> priority); } (3) LOS_ListTailInsert (& g_losPriorityQueueList (priority), priqueueItem); }Copy the code

(1) First judge whether the task ready queue with specified priority is empty; if it is empty, then update the priority bitmap at (2) and set the 31-prioritybit to 1. (3) insert the task in the ready state into the end of the task ready queue and queue.

2.3 Deleting a Task from the Task Ready Queue

The function removed from the task ready queue is OsPriqueueDequeue(). This function is used to delete a task from the task ready queue when the task is deleted, when the task is in the Suspend blocked state, or when the priority is adjusted.

The source code is as follows:

STATIC VOID OsPriqueueDequeue(LOS_DL_LIST *priqueueItem) { LosTaskCB *runningTask = NULL; (1) LOS_ListDelete (priqueueItem); ⑵ runningTask = LOS_DL_LIST_ENTRY(priqueueItem, LosTaskCB, pendList); ⑶ if (LOS_ListEmpty(&g_losPriorityQueueList[runningTask->priority])) {⑷ g_priqueueBitmap &= ~(PRIQUEUE_PRIOR0_BIT >> runningTask->priority); }}Copy the code

(1) Remove the task from the task ready queue. (2) Obtain the task control block information of the deleted task to obtain the priority of the task. After deleting the task, the queue may become empty, so the code at ⑶ determines whether the task ready queue is empty. If it is empty, the code at ⑷ needs to be executed, the priority bitmap updated, and the 31-prioritybit set to 0.

2.4 Obtaining the highest priority node in the queue

The function that gets the highest priority list node in the task ready queue is OsPriQueueTop().

The source code is as follows:

STATIC LOS_DL_LIST *OsPriqueueTop(VOID) { UINT32 priority; (1) if (g_priqueueBitmap! = 0) {⑵ priority = g_priqueueBitmap; (3) the return LOS_DL_LIST_FIRST (& g_losPriorityQueueList [priority]); } return (LOS_DL_LIST *)NULL; }Copy the code

(1) Determine whether g_priqueueBitmap is 0. If it is 0, NULL is directly returned, indicating that there are no tasks in the task ready queue. The value of g_priqueueBitmap is the priority of the task. The value of g_priqueueBitmap is the highest priority of all tasks in the ready queue. We then retrieve the first list node from the queue g_losPriorityQueueList[priority] at (3), which is the highest priority task in the task ready queue.

2.5 Obtain the number of ready tasks with a specified priority

The function that gets the number of tasks with a specified priority in the task ready queue is OsPriqueueSize().

The source code is as follows:

STATIC UINT32 OsPriqueueSize(UINT32 priority) { UINT32 itemCnt = 0; LOS_DL_LIST *curPQNode = (LOS_DL_LIST *)NULL; ⑴ los_list_for_each (curPQNode, &g_lospriorityqueuelist [priority]) {⑵ ++itemCnt; } return itemCnt; }Copy the code

(1) use the macro LOS_DL_LIST_FOR_EACH to iterate over a bidirectional list of priority. If a new node is obtained, it indicates that there is a ready task under the priority. (2) Execute the code at (1) and increment the count by 1. The result is to specify how many tasks are ready at the priority.

summary

Mastering the important data structure of the Priority Queue of the Hongmeng Light kernel will lay a foundation for further study and analysis of the source code of the Hongmeng light kernel, and make the subsequent study easier. The following will also launch more articles to share, please look forward to, also welcome to share learning, using hongmeng Light kernel experience, any questions, suggestions, you can leave a message to us: gitee.com/openharmony… . To make it easier to find the Hongmunlightweight kernel repository, you are advised to visit gitee.com/openharmony… .

Click follow to learn about the fresh technologies of Huawei Cloud