Happy year of the tiger! I wish you greater progress next year!

Reference content: Chapter 11 of [wildfire] uCOS-III Kernel Implementation and application development Practical Guide - based on STM32.

1 definition of ready list and task control block (os.h)

1.1 task control block linked list OS_TCB

Before defining the ready list, modify the contents of TCB.

TCB is a two-way linked list. Each node contains the following contents:

• Task stack pointer StkPtr;
• Task stack size StkSize;
• Task blocking duration: TaskDelayTicks;
• Priority of task Prio;
• The forward pointer field PrevPtr and the backward pointer field NextPtr.

/*----------------------TCB---------------------------*/
/* TCB Rename to uppercase format */
typedef struct os_tcb	OS_TCB;

/* TCB Data type declaration */
struct os_tcb{
	CPU_STK			*StkPtr;
	CPU_STK_SIZE	StkSize;
	
	OS_TICK			TaskDelayTicks;		/* How many Ticks does the task delay? Note that one tick is 10ms */
	
	OS_PRIO			Prio;
	
	OS_TCB			*NextPtr;
	OS_TCB			*PrevPtr;
};

1.2 ready list OS_RDY_LIST

Unlike TCB, os_rdy_list is not a linked list, but a pure structure that stores:

• The header node of TCB linked list, HeadPtr;
• TailPtr, tail node of TCB linked list;
• The number of nodes in the TCB linked list NbrEntries, that is, the number of tasks.

/*---------------------OS_RDY_LIST----------------------------*/
/* Rename the ready list to uppercase format */
typedef struct os_rdy_list	OS_RDY_LIST;

/* Ready list data type declaration, which strings TCB into a two-way linked list */
struct os_rdy_list{
	OS_TCB		*HeadPtr;
	OS_TCB		*TailPtr;
	OS_OBJ_QTY	NbrEntries;		/* How many tasks are there under the same index */
};

1.3 global variable definition

• Ready list array OSRdyList: the number of array elements is the maximum support priority defined by us. For example, if we define the priority of support as 32, the ready list array has 32 elements;

This means that each array element will store TCB related information: the head pointer, tail pointer and the number of nodes of the TCB linked list. We can regard each array element as storing a TCB bidirectional linked list.

• Current priority OSPrioCur;
• Highest priority OSPrioHighRdy;
• Current task OSTCBCurPtr;
• The highest priority task OSTCBHighRdyPtr.

OS_EXT 	OS_TCB			*OSTCBCurPtr;
OS_EXT	OS_TCB			*OSTCBHighRdyPtr;

OS_EXT	OS_PRIO			OSPrioCur;		/* Current priority */
OS_EXT	OS_PRIO			OSPrioHighRdy;	/* Highest priority */

OS_EXT	OS_RDY_LIST		OSRdyList[OS_CFG_PRIO_MAX];

1.4 full structural drawing

As shown in the figure, each priority corresponds to a two-way linked list. When executing a task, when there are multiple ready tasks on the highest priority, the execution order is from the head to the tail of the two-way linked list.

——Excerpt from uC/OS-III source code analysis notes

2 initialization ready list OS_RdyListInit()(os_core.c)

Functions of this function:

• Initialize the ready list to empty: all information is cleared.

/* Initialize ready list */
void OS_RdyListInit (void)
{
	OS_PRIO		i;
	OS_RDY_LIST	*p_rdy_list;
	
	for ( i = 0u; i < OS_CFG_PRIO_MAX; i++ )
	{
		p_rdy_list = &OSRdyList[i];
		p_rdy_list->HeadPtr = (OS_TCB *) 0;
		p_rdy_list->TailPtr = (OS_TCB *) 0;
		p_rdy_list->NbrEntries = (OS_OBJ_QTY)0;
	}
}

3 move the TCB node from the head of the linked list to the tail of the linked list_ RdyListMoveHeadToTail()(os_core.c)

Functions of this function:

• Insert the task TCB into the ready list.

Therefore, the steps to be completed are:

• Set the corresponding position in the priority table according to the priority of the task;
• Insert it into the corresponding position of the ready list according to the priority: if the priority is equal to the current priority, insert the current task TCB into the tail of the linked list; Otherwise, insert it into the head of the linked list.

/* Insert a TCB into the ready list */
void OS_RdyListInsert (OS_TCB *p_tcb)
{	
	OS_PrioInsert (p_tcb->Prio);  /* Insert priority into current priority */
	
	if (p_tcb->Prio == OSPrioCur)
	{
		OS_RdyListInsertTail (p_tcb);  /* If the priority is equal to the current priority, the current task is inserted at the end of the linked list */
	}
	else
	{
		OS_RdyListInsertHead (p_tcb);	/* Otherwise, insert the current task into the head of the linked list */
	}
}

To this end, you need to implement the functions of inserting the head and tail of the linked list.

3.1 insert a TCB node OS into the head of the linked list_ RdyListInsertHead()(os_core.c)

Inserting a TCB into the head of the linked list can be divided into two cases:

• The linked list is empty: (1) directly create a node, and the pointer fields are empty; (2) Number of tasks plus one; (3) Both HeadPtr and TailPtr in the ready list point to the new node.
• The linked list is not empty: (1) make the forward pointer field of the original leading node point to the new node, set the forward pointer field of the new node to 0, and the backward pointer field points to the original leading node; (2) Number of tasks plus one; (3) The HeadPtr of the ready list points to the new header node.

/* Insert a TCB into the head of the linked list */
void OS_RdyListInsertHead (OS_TCB *p_tcb)
{
	OS_RDY_LIST	*p_rdy_list;
	OS_TCB		*p_tcb2;
	
	p_rdy_list = &OSRdyList[p_tcb->Prio];
	
	if (p_rdy_list->NbrEntries == (OS_OBJ_QTY)0)	/* If the linked list is empty */
	{
		p_rdy_list->NbrEntries = (OS_OBJ_QTY)1;
		p_rdy_list->HeadPtr = p_tcb;
		p_rdy_list->TailPtr = p_tcb;
		p_tcb->NextPtr = (OS_TCB *)0;
		p_tcb->PrevPtr = (OS_TCB *)0;
	}
	else		/* If the linked list is not empty */
	{
		p_rdy_list->NbrEntries++;
		p_tcb2 = p_rdy_list->HeadPtr;		/* p_tcb2 = The head node of the original TCB linked list */
		
		p_tcb->PrevPtr = (OS_TCB *)0;		/* New p_ The leading pointer of TCB is 0 */
		p_tcb->NextPtr = p_rdy_list->HeadPtr;
		p_tcb2->PrevPtr = p_tcb;			/* p_tcb2 The front pointer of points to p_tcb, the new p_tcb is added to the TCB linked list to become a new head node */
		
		p_rdy_list->HeadPtr = p_tcb;		/* After a new TCB is added, the HeadPtr of the ready list points to the new header node */
	}
}

3.2 insert a TCB node OS at the end of the linked list_ RdyListInsertTail()(os_core.c)

Inserting a TCB at the end of the linked list can also be divided into two cases:

• The linked list is empty: (1) directly create a node, and the pointer fields are empty; (2) Number of tasks plus one; (3) Both HeadPtr and TailPtr in the ready list point to the new node.
• The linked list is not empty: (1) make the backward pointer field of the original tail node point to the new node, set the backward pointer field of the new node to 0, and the forward pointer field points to the original tail node; (2) Number of tasks plus one; (3) TailPtr of the ready list points to the new tail node.

/* Insert a TCB at the end of the linked list */
void OS_RdyListInsertTail (OS_TCB *p_tcb)
{
	OS_RDY_LIST	*p_rdy_list;
	OS_TCB		*p_tcb2;
	
	p_rdy_list = &OSRdyList[p_tcb->Prio];
	
	if (p_rdy_list->NbrEntries == (OS_OBJ_QTY)0)	/* If the linked list is empty */
	{
		p_rdy_list->NbrEntries = (OS_OBJ_QTY)1;
		p_rdy_list->HeadPtr = p_tcb;
		p_rdy_list->TailPtr = p_tcb;
		p_tcb->NextPtr = (OS_TCB *)0;
		p_tcb->PrevPtr = (OS_TCB *)0;
	}
	else		/* If the linked list is not empty */
	{
		p_rdy_list->NbrEntries++;
		p_tcb2 = p_rdy_list->TailPtr;		/* p_tcb2 = The tail node of the original TCB linked list */
		
		p_tcb->PrevPtr = p_tcb2;			/* New p_ The front pointer of TCB points to p_tcb2 */
		p_tcb->NextPtr = (OS_TCB *)0;		/* New p_ The back pointer of TCB is 0 */
		p_tcb2->NextPtr = p_tcb;			/* p_tcb2 The back pointer of points to p_tcb, the new p_tcb is added to the TCB linked list and becomes a new tail node */
		
		p_rdy_list->TailPtr = p_tcb;		/* After adding a new TCB, the HeadPtr of the ready list points to the new tail node */
	}
}

4 move the TCB node from the head of the linked list to the tail of the linked list_ RdyListMoveHeadToTail()(os_core.c)

Move the TCB node from the head of the linked list to the tail of the linked list. There are four cases:

• The linked list is empty: you don't have to do anything.
• There is only one node in the linked list: you don't have to do anything.
• There are only two nodes in the linked list: (1) the forward pointer field of the original head node points to the original tail node, and the backward pointer field of the original head node is set to zero; (2) The forward pointer field of the original tail node is set to zero, and the forward pointer field of the original tail node points to the original head node; (3) The HeadPtr and TailPtr of the ready list point to the new head and tail nodes respectively.
• There are more than two nodes in the linked list: (1) the forward pointer field of the original head node points to the original tail node, and the backward pointer field of the original head node is set to zero; (2) The forward pointer field of the next node of the original head node is set to zero (as a new head node); (3) The forward pointer field of the original tail node points to the original head node; (4) The HeadPtr and TailPtr of the ready list point to the new head and tail nodes respectively.

/* Move TCB from the head of the linked list to the tail of the linked list */
void OS_RdyListMoveHeadToTail (OS_RDY_LIST *p_rdy_list)
{
	OS_TCB	*p_tcb1;
	OS_TCB	*p_tcb2;
	OS_TCB	*p_tcb3;
	
	switch (p_rdy_list->NbrEntries)
	{
		case 0:		/* The linked list is empty */
		case 1:		/* The linked list has only one node */
			break;
		
		case 2:		/* The linked list has only two nodes */
			p_tcb1 = p_rdy_list->HeadPtr;
			p_tcb2 = p_rdy_list->TailPtr;
			p_tcb1->PrevPtr = p_tcb2;
			p_tcb1->NextPtr = (OS_TCB *)0;
			p_tcb2->PrevPtr = (OS_TCB *)0;
			p_tcb2->NextPtr = p_tcb1;
			p_rdy_list->HeadPtr = p_tcb2;
			p_rdy_list->TailPtr = p_tcb1;
			break;
		
		default:	/* The linked list has more than two nodes */
			p_tcb1 = p_rdy_list->HeadPtr;
			p_tcb2 = p_rdy_list->TailPtr;
			p_tcb3 = p_tcb1->NextPtr;
			
			p_tcb1->PrevPtr = p_tcb2;
			p_tcb1->NextPtr = (OS_TCB *)0;
			p_tcb3->PrevPtr = (OS_TCB *)0;
			p_tcb2->NextPtr = p_tcb1;
		
			p_rdy_list->HeadPtr = p_tcb3;
			p_rdy_list->TailPtr = p_tcb1;
			break;
	}
}

5. Remove a TCB node OS from the linked list_ RdyListRemove()(os_core.c)

To remove a TCB node from the TCB linked list, first save the previous and subsequent nodes of the TCB node to be deleted, and then there are four cases:

• The linked list has only one node (or the linked list is empty): (1) all the information of the array elements corresponding to the ready list is cleared; (2) Set the corresponding priority in the priority table to 0.
• What is deleted is the head node of the linked list: (1) the forward pointer field of the latter node is set to zero; (2) Reduce the number of tasks by one; (3) The HeadPtr of the ready list points to the new head node (i.e. the next node).
• What is deleted is the tail node of the linked list: (1) the backward pointer field of the previous node is set to zero; (2) Reduce the number of tasks by one; (3) TailPtr of the ready list points to the new tail node (i.e. the previous node).
• The common nodes of the linked list are deleted: (1) the backward pointer field of the previous node points to the next node, and the forward pointer field of the latter node points to the previous node. (2) Reduce the number of tasks by one.

Finally, set all the pointer fields of the deleted node to zero for the next linked list insertion operation.

/* Remove a TCB from the linked list */
void OS_RdyListRemove (OS_TCB *p_tcb)
{
	OS_RDY_LIST	*p_rdy_list;
	OS_TCB		*p_tcb1;
	OS_TCB		*p_tcb2;
	
	/* Save the previous and subsequent nodes of the TCB node to be deleted */
	p_tcb1 = p_tcb->PrevPtr;
	p_tcb2 = p_tcb->NextPtr;
	p_rdy_list = &OSRdyList[p_tcb->Prio];
	
	if (( p_tcb1 == (OS_TCB *)0 ) && ( p_tcb2 == (OS_TCB *)0 ))			/* If the linked list has only one node */
	{
		p_rdy_list->HeadPtr = (OS_TCB *) 0;
		p_rdy_list->TailPtr = (OS_TCB *) 0;
		p_rdy_list->NbrEntries = (OS_OBJ_QTY)0;
		OS_PrioRemove (p_tcb->Prio);
	}
	else if (( p_tcb1 == (OS_TCB *)0 ) && ( p_tcb2 != (OS_TCB *)0 ))	/* If the head node of the linked list is deleted (p_tcb1 = 0) */
	{
		p_tcb2->PrevPtr = (OS_TCB *) 0;
		p_rdy_list->HeadPtr = p_tcb2;
		p_rdy_list->NbrEntries--;
	}
	else if (( p_tcb1 != (OS_TCB *)0 ) && ( p_tcb2 == (OS_TCB *)0 ))	/* If the tail node of the linked list is deleted (p_tcb2 = 0) */
	{
		p_tcb1->NextPtr = (OS_TCB *) 0;
		p_rdy_list->TailPtr = p_tcb1;
		p_rdy_list->NbrEntries--;
	}
	else																/* If you delete an ordinary node of the linked list */
	{
		p_tcb1->NextPtr = p_tcb2;
		p_tcb2->PrevPtr = p_tcb1;
		p_rdy_list->NbrEntries--;
	}
	
	/* Reset the two pointers PrevPtr and NextPtr of TCB deleted from the ready list */
	p_tcb->PrevPtr = (OS_TCB *)0;
	p_tcb->NextPtr = (OS_TCB *)0;
}

Reviewed the data structure of the linked list again. Well, the needle doesn't poke!