RT thread Kernel Implementation (IV): multi priority

• Holistic thinking :
  Previous chapters do not support multiple priorities , Manually switch the specified thread to run . After priority support , The scheduler will only find the current highest priority thread to run .RT-Thread It belongs to preemptive real-time operating system ,CPU Will be preempted by the current highest priority thread , Unless the highest priority thread voluntarily gives up , For example, call rt_thread_delay(rt_tick_t tick) The time delay function , Will change the thread state to suspended or blocked state , Then execute system scheduling .

• Thread control block Added several attributes

    rt_uint8_t current_priority;    /*  Current priority  */
    rt_uint8_t init_priority;       /*  Initial priority  */
    rt_uint32_t number_mask;        /*  Current priority mask  */
    
    rt_err_t    error;              /*  Error code  */
    
    rt_uint8_t stat;                /*  State of thread  */

• Thread initialization function The added part

rt_err_t rt_thread_init(struct rt_thread *thread,
                        const char       *name,
                        void (*entry)(void *parameter),
                        void             *parameter,
                        void             *stack_start,
                        rt_uint32_t       stack_size,
                        rt_uint8_t          priority)
{
    
	/* *  Omit ... */
	thread->init_priority = priority;
	thread->current_priority = priority;
	thread->number_mask = 0;
	
	thread->error = RT_EOK;
	thread->stat = RT_THREAD_INIT;	//  Initialization status 
	
	return RT_EOK;
}

• Scheduler initialization function
  Initialize the current priority (rt_current_priority) Is the priority of idle threads , Global variables .

/*  Initialize the system scheduler  */
void rt_system_scheduler_init(void)
{
    	
	register rt_base_t offset;	

	
	/*  Thread ready list initialization  */
	for (offset = 0; offset < RT_THREAD_PRIORITY_MAX; offset ++)
	{
    
			rt_list_init(&rt_thread_priority_table[offset]);
	}
    
    /*  Initialize the current priority to the priority of the idle thread  */
    rt_current_priority = RT_THREAD_PRIORITY_MAX - 1;
	
	/*  Initializes the current thread control block pointer  */
	rt_current_thread = RT_NULL;
    
    /*  Initialize thread ready priority group  */
    rt_thread_ready_priority_group = 0;
	
}

• add to Thread start function
  Start a thread and put it in the system's ready list , First, set the status of the thread to suspended status , Then call the resume thread function rt_thread_resume(rt_thread_t thread), Only suspended threads can be resumed . Then carry out system scheduling . The current priority mask can be seen here (thread->number_mask) The role of , take 32 The corresponding position in the bit priority 1, When modifying this thread priority group (rt_thread_ready_priority_group) It's more convenient when .

rt_err_t rt_thread_startup(rt_thread_t thread)
{
    
    /*  Set the current priority as the initial priority  */
    thread->current_priority = thread->init_priority;
    thread->number_mask = 1L << thread->current_priority;
    
    /*  Change the state of the thread to suspended state  */
    thread->stat = RT_THREAD_SUSPEND;
    /*  Then resume the thread  */
    rt_thread_resume(thread);
    
    if (rt_thread_self() != RT_NULL)
    {
    
        /*  System scheduling  */
        rt_schedule();
    }

    return RT_EOK;
}

• Thread recovery function
  • First, determine whether the target thread is suspended , Then remove from the pending queue .
  • Here we mention suspending queues , It should be a global variable rt_list_t rt_thread_defunct;, There's no use for , In the official source code, only the thread exits (rt_thread_exit)、 Separate (rt_thread_detach) And delete (rt_thread_delete) The operation will suspend the thread to rt_thread_defunct On .
  • Then insert the thread into the on-line list ,void rt_schedule_insert_thread(struct rt_thread *thread), The thread ready priority group is updated in this function (rt_thread_ready_priority_group) Value .
  • Corresponding to the insert function is the remove function ,void rt_schedule_remove_thread(struct rt_thread *thread), The insert operation is set using a priority mask , Remove operation reset .

rt_err_t rt_thread_resume(rt_thread_t thread)
{
    
    register rt_base_t temp;
    
    /*  The thread to be resumed must be in the suspended state , Otherwise, an error code is returned  */
    if ((thread->stat & RT_THREAD_STAT_MASK) != RT_THREAD_SUSPEND)
    {
    
        return -RT_ERROR;
    }

    /*  Close the interrupt  */
    temp = rt_hw_interrupt_disable();

    /*  Remove from pending queue  */
    rt_list_remove(&(thread->tlist));

    /*  Open the interrupt  */
    rt_hw_interrupt_enable(temp);

    /*  Insert ready list  */
    rt_schedule_insert_thread(thread);

    return RT_EOK;
}

void rt_schedule_insert_thread(struct rt_thread *thread){
    
    register rt_base_t temp;
    
    /*  Close the interrupt  */
    temp = rt_hw_interrupt_disable();
    
    thread->stat = RT_THREAD_READY;
    
    rt_list_insert_before(&(rt_thread_priority_table[thread->current_priority]),
                            &(thread->tlist));
    
    /*  Set the corresponding bit in the thread ready priority group  */
    rt_thread_ready_priority_group |= thread->number_mask;

    /*  Open the interrupt  */
    rt_hw_interrupt_enable(temp);
}

void rt_schedule_remove_thread(struct rt_thread *thread)
{
    
    register rt_base_t temp;


    /*  Close the interrupt  */
    temp = rt_hw_interrupt_disable();
    
    /*  Remove the thread from the ready list  */
    rt_list_remove(&(thread->tlist));
    
    if (rt_list_isempty(&(rt_thread_priority_table[thread->current_priority])))
    {
    
        rt_thread_ready_priority_group &= ~thread->number_mask;
    }

    /*  Open the interrupt  */
    rt_hw_interrupt_enable(temp);
}

• Idle function The initialization of has also been modified accordingly

void rt_thread_idle_init(void)
{
    
    
    /*  Initialization thread , Lowest priority  */
    rt_thread_init(&idle,
                   "idle",
                   rt_thread_idle_entry,
                   RT_NULL,
                   &rt_thread_stack[0],
                   sizeof(rt_thread_stack),
                   RT_THREAD_PRIORITY_MAX-1);
    
                   
    rt_thread_startup(&idle);
}

• Start the system scheduler function rt_system_scheduler_start()
  Before that, a thread was manually specified , Now through __rt_ffs() Get the thread with the highest priority .

/*  Start the system scheduler  */
void rt_system_scheduler_start(void)
{
    
	register struct rt_thread *to_thread;
    register rt_ubase_t highest_ready_priority;
    
    /*  Get the highest priority for readiness  */
    highest_ready_priority = __rt_ffs(rt_thread_ready_priority_group) - 1;
    
    /*  Get the thread control block of the thread to run  */
    to_thread = rt_list_entry(rt_thread_priority_table[highest_ready_priority].next,
                              struct rt_thread,
                              tlist);
    
     rt_current_thread = to_thread;
                              
     rt_hw_context_switch_to((rt_uint32_t)&to_thread->sp);
}

• System scheduling function rt_schedule ()
  Similarly passed __rt_ffs() Get the thread with the highest priority , Then switch threads .

/*  System scheduling  */
void rt_schedule(void)
{
    
    rt_base_t level;
    register rt_ubase_t highest_ready_priority;
	struct rt_thread *to_thread;
	struct rt_thread *from_thread;
	
	/*  Close the interrupt  */
    level = rt_hw_interrupt_disable();
    
    /*  Get the highest priority for readiness  */
    highest_ready_priority = __rt_ffs(rt_thread_ready_priority_group) - 1;
    
    /*  Get the thread control block corresponding to the highest priority ready  */
    to_thread = rt_list_entry(rt_thread_priority_table[highest_ready_priority].next,
                              struct rt_thread,
                              tlist);
	
    /*  If the target thread is not the current thread , Thread switching is required  */
    if(to_thread != rt_current_thread){
    
        rt_current_priority = (rt_uint8_t)highest_ready_priority;
        from_thread = rt_current_thread;
        rt_current_thread = to_thread;
        
        /*  Generate context switching  */
        rt_hw_context_switch((rt_uint32_t)&from_thread->sp, (rt_uint32_t)&to_thread->sp);
        
        rt_hw_interrupt_enable(level);
    }else{
    
        rt_hw_interrupt_enable(level);
    }
	
}

• Blocking delay function rt_thread_delay()
  Update the remaining tick Count , Update thread state , Update global thread ready priority group , Then carry out system scheduling . High priority threads can give up in this way CPU.

void rt_thread_delay(rt_tick_t tick)
{
    
    register rt_base_t tmp;
    struct rt_thread *thread;    
    
    tmp = rt_hw_interrupt_disable();
    
    thread = rt_current_thread;
    thread->remaining_tick = tick;
    
    /*  Change thread state  */
    thread->stat = RT_THREAD_SUSPEND;
    
    /*  Take the opposite , Clear the corresponding position 0 */
    rt_thread_ready_priority_group &= ~thread->number_mask;
    
    rt_hw_interrupt_enable(tmp);
    
    rt_schedule();
}

• Time base update function rt_tick_increase()
  • The function is in SysTick Called in interrupt service function , The function is to update the system tick Count , And all threads remaining_tick, If not for 0, Then subtract 1, If it is equal to 0, Then update the global thread ready priority group . Then carry out system scheduling .
  • Here and PDF Some of the differences introduced in ,1. The remainder of the idle function tick Don't judge ;2. If rt_list_isempty(&thread->tlist) True indicates that no thread is suspended under this priority , Don't need to update remaining_tick.

void rt_tick_increase(void)
{
    
    rt_ubase_t i;
    struct rt_thread *thread;
    rt_tick ++;

	/*  Scan all threads in the ready list (idle Threads should not judge ) Of remaining_tick, If not for 0, Then subtract 1 */
	for(i=0; i < RT_THREAD_PRIORITY_MAX - 1; i++)
	{
    
            thread = rt_list_entry( rt_thread_priority_table[i].next,
                                     struct rt_thread,
                                     tlist);
                                     
            if(rt_list_isempty(&thread->tlist)){
    
                continue;
            }
                
            if(thread->remaining_tick > 0)
            {
    
                thread->remaining_tick --;
                if(thread->remaining_tick == 0){
    
                	/*  When the delay time expires, the original priority will be restored  */
                    rt_thread_ready_priority_group |= thread->number_mask;
                }
            }
            
	}
    
    /*  System scheduling  */
	rt_schedule();
}

• The main function main()
  • You can see in initialization rt_flag1_thread after , It's called rt_thread_startup(&rt_flag1_thread), Used to modify the thread state and start the thread , But the thread does not run immediately . because rt_thread_startup() There is judgment in , When rt_thread_self() != RT_NULL The system scheduling will be carried out only when .
  • Also note that ,main The first step of the function is to turn off the total interrupt , It will not be opened until the system scheduler is started for the first thread switching .

int main(){
    
    
    /*  Hardware related initialization  */
    
    /*  Close the interrupt  */
    rt_hw_interrupt_disable();
    
    /*  Set up SysTick Interrupt frequency  25MHz / 100 */
    SysTick_Config(SystemCoreClock / RT_TICK_PER_SECOND);
    
    /*  Initialize the system scheduler  */
    rt_system_scheduler_init();
    
    /*  Initialize idle thread  */    
    rt_thread_idle_init();
    
    /*  Initialization thread  */
    rt_thread_init( &rt_flag1_thread,
                    "rt_flag1_thread",                /*  Thread name , String form  */
                    flag1_thread_entry,
                    RT_NULL,
                    &rt_flag1_thread_stack[0],
                    sizeof(rt_flag1_thread_stack),
                    2);
    
// rt_list_insert_before(&(rt_thread_priority_table[0]), &(rt_flag1_thread.tlist));
    rt_thread_startup(&rt_flag1_thread);    //  Start thread , But it will not be executed immediately 
                    
    rt_thread_init( &rt_flag2_thread,
                    "rt_flag2_thread",                /*  Thread name , String form  */
                    flag2_thread_entry,
                    RT_NULL,
                    &rt_flag2_thread_stack[0],
                    sizeof(rt_flag2_thread_stack),
                    3);
    
// rt_list_insert_before(&(rt_thread_priority_table[1]), &(rt_flag2_thread.tlist));
    rt_thread_startup(&rt_flag2_thread);
    
    rt_thread_init( &rt_flag3_thread,
                    "rt_flag3_thread",                /*  Thread name , String form  */
                    flag3_thread_entry,
                    RT_NULL,
                    &rt_flag3_thread_stack[0],
                    sizeof(rt_flag3_thread_stack),
                    4);
    
// rt_list_insert_before(&(rt_thread_priority_table[2]), &(rt_flag3_thread.tlist));
    rt_thread_startup(&rt_flag3_thread);
    
    rt_system_scheduler_start();
    
}

• Look again. Get the highest priority for readiness function int __rt_ffs(int value)
  The notes are quite clear .

#ifndef RT_USING_CPU_FFS
/* * __lowest_bit_bitmap[]  Parsing of arrays  *  Will a 8 Value range of bit integer number 0~255 As an index to an array , Index value appears first 1( Let's start at the lowest point ) As the member value under the index of the array . *  give an example ： Decimal number 10 The binary of is ：0000 1010, Let's start at the lowest point , The first to appear 1 The tag number of is bit1, Then there are __lowest_bit_bitmap[10]=1 *  Be careful ： Just find the first one to appear 1 The tag number of  */
const rt_uint8_t __lowest_bit_bitmap[] =
{
    
    /* 00 */ 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 10 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 20 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 30 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 40 */ 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 50 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 60 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 70 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 80 */ 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 90 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* A0 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* B0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* C0 */ 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* D0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* E0 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* F0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};

/** *  This function is used to start from a 32 Find the first set in the number of bits 1 Bit （ Starting from the low ）, *  Then return the index of the bit （ Accession number ） * * @return  Return to the first setting 1 Index number of bit . If it's all 0, Then return to 0. */
int __rt_ffs(int value)
{
    
    /*  If the value is 0, Then return directly 0 */
    if (value == 0) return 0;

    /*  Check  bits [07:00]  Here plus 1 The reason is to avoid being the first to set 1 The bit of is bit 0 when   The returned index number and value are 0 The index number returned during the  */
    if (value & 0xff)
        return __lowest_bit_bitmap[value & 0xff] + 1;

    /*  Check  bits [15:08] */
    if (value & 0xff00)
        return __lowest_bit_bitmap[(value & 0xff00) >> 8] + 9;

    /*  Check  bits [23:16] */
    if (value & 0xff0000)
        return __lowest_bit_bitmap[(value & 0xff0000) >> 16] + 17;

    /*  Check  bits [31:24] */
    return __lowest_bit_bitmap[(value & 0xff000000) >> 24] + 25;
}
#endif

Engineering documents

Schedule by priority

Expand

Linux CFS Scheduling priority policy ： The scheduler always chooses vruntime The process with the smallest value to execute . High priority processes vruntime Value growth is slow .
for example A、B Two processes ,A The weight of 1,B Higher priority (nice Lower value ) The weight of 2, if A Of vruntime The unit of growth rate is 1,B The is 1/2, But in one cycle A What you get CPU Time in units 1,B The time obtained is 2, therefore On the macro AB Of vruntime The growth rate is the same , So in a cycle, if someone's vruntime It is worth mentioning that he used to occupy cpu The time is short , therefore CPU“ Fair ” Select it to perform .