RT-Thread / RT-Thread/rt-thread

ready list插入顺序问题

Open
#8,459 4 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
C
Stars
12.2k
Forks
5.4k
Avg merge
4d 12h
Merged PRs (30d)
40

Description

版本:master分支最新commit
背景:结合两次修复历史(https://github.com/RT-Thread/rt-thread/pull/6232https://github.com/RT-Thread/rt-thread/issues/8050)
都是针对ready list add 成员时做出的修复,其中rt_schedule_insert_thread函数中代码如下:
/* there is no time slices left(YIELD), inserting thread before ready list*/
if((thread->stat & RT_THREAD_STAT_YIELD_MASK) != 0)
{
rt_list_insert_before(&(rt_thread_priority_table[thread->current_priority]),
&(thread->tlist));
}
/* there are some time slices left, inserting thread after ready list to schedule it firstly at next time*/
else
{
rt_list_insert_after(&(rt_thread_priority_table[thread->current_priority]),
&(thread->tlist));
}
我们的本意应该是如果时间片没用完被调度切换到更高优先级的线程时,那么在下次切回时应优先执行未使用完时间片的线程,例如A,B,C三线程,优先级值为A=B>C,在A执行时,C由于优先级最高被调度执行(假设被中断触发信号量),那么在C执行完时,应该先执行A,待A时间片轮完再执行B,以此交替。总结起来就是同优先级的线程必须按顺序依次执行完各自的时间片,中途可被中断或更高优先级打断,但总顺序不变,这样可以保证同优先级线程最大的公平性。

问题1:
假设线程ABCD,D优先级最高,ABC优先级相同,线程A,B,C依次获取信号量s从而挂起(s的flag为fifo),那么在插入s的挂起线程链表时调用rt_list_insert_before函数,其挂起线程链表中顺序为A->B->C,在某个时刻释放信号量时,依次调用函数_ipc_list_resume,rt_thread_resume,rt_schedule_insert_thread,此时将A取出插入相应优先级的ready list中,由于没有RT_THREAD_STAT_YIELD,那么是插队插入ready链表头中,调度时由于A优先级低,D继续执行,而后又释放了一次信号量,相同的步骤将B插队插入ready list中,此时ready list中链表顺序为B->A,若D此时释放CPU,那么调度先执行B而不是A,这显然违背了我们的意图。

最终目的:
插队插入链表头只能是线程已运行且时间片未用完的情况或者线程还未运行又要被切换(#6232)的情况,其余大部分情况应该都是顺序插入链表尾,包括线程的主动挂起(rt_thread_yield)。

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by tracing rt_schedule_insert_thread, rt_thread_resume, and _ipc_list_resume, then inspect the ready-list and semaphore-wait-list operations described in the issue. Reproduce the FIFO semaphore scenario with equal-priority threads A, B, and C interrupted by higher-priority D; done means resumed threads preserve the intended time-slice order instead of later threads overtaking earlier ones.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
operating-systems
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.