广告

QNX的调度算法

2022-10-24 汽车电子与软件 阅读:
作为一个硬实时操作系统,QNX是一个基于优先级抢占的系统。这也导致其基本调度算法相对比较简单。因为不需要像别的通用操作系统考虑一些复杂的“公平性”,只需要保证“优先级最高的线程最优先得到 CPU”就可以了。
作者 | xtang
作为一个硬实时操作系统,QNX是一个基于优先级抢占的系统。这也导致其基本调度算法相对比较简单。因为不需要像别的通用操作系统考虑一些复杂的“公平性”,只需要保证“优先级最高的线程最优先得到 CPU”就可以了。

基本调度算法

调度算法,是基于优先级的。QNX的线程优先级,是一个0-255的数字,数字越大优先级越高。所以,优先级0是内核中的idle线程。同时,优先级64是一个分界岭。就是说,优先级1 – 63 是非特权优先级,一般用户都可以用,而64 – 255必须是有root权限的线程才以设。这个“优先级64”分界线,如果有必要,还可以通过启动Procnto时传 –P 来改变。
调度算法的对像是线程,而线程在QNX上,有大约20个状态。(参考 /usr/include/sys/states.h)在这许多状态中,跟调度有关的,其实只有 STATE_RUNNING和STATE_READY两个状态。STATE_RUNNING是线程当前正在使用CPU,而STATE_READY是等着被执行(被调度)的线程。其他状态的线程,处于某种“阻塞”状态中,调度算法不需要关注。
所以在调度算法看来,整个系统里的线程像这样:
图 1 有两个CPU的系统里的线程
这是一个有两个CPU的系统,所以可以看到有两个RUNNING线程;对于 BLOCK THREAD,它们不参于调度,所以不需要考虑它们的优先级。

调度策略

在QNX上实质上只有三种基本调度策略,“轮询”(Round Robin),“先进先出”(First in first out)和"零星调度”(Sporadic) 算法。虽然形式上还有一个“其他”,但“其他”跟“轮询”是一样的。这些调度策略,在 /usr/include/sched.h 里有定义。(SCHED_FIFO, SCHED_RR, SCHED_SPORADIC, SCHED_OTHER)
强调一下,调度策略只限于在READY队列里的线程,优线级最高的线程有不止一个时,才会用到。如果线程不再 READY,或是有别的更高优先级的线程 READY了,那就高优先级线程获取CPU,没有什么策略可言。
“轮询调度”(Round Robin)跟平时生活里排队的情形差不多,晚到的人排在队尾,早到的人排在队首,等到叫号(调度)的时候,队首的人会被先叫到 。如下图所示:
图 2 论询调度示意
  • 首先在CPU 1上运行的线程4,被挪入优先级15的队列末尾
  • 然后重新搜索可执行的最高优先级线程,这里有优先级15队列上的线程3和4
  • 线程3因为在队列最前端,它被选择得到CPU,线程3的状态变为RUNNING,在CPU1上执行
可以预期,当下一次调度发生时,线程3会被挪入优先级15队列末尾,而线程4会被调度执行,这样线程3和4会分别得到CPU1.
“先进先出”(First in first out)调度则刚好相反,后来的人插在队首,然后在叫号的时候被先叫到。看下图:
图 3 先进先出调度示意
  • 首先在CPU 1上运行的线程4,被挪入优先级15的队列队首
  • 然后重新搜索可执行的最高优先级线程,这里有优先级15队列上的线程4和3
  • 线程4因为在队列最前端,它被选择得到CPU,线程4的状态变为RUNNING,在CPU1上执行
可以看到,在这个调度算法下,如果没有别的状态发生,事实上线程4就会一直占据CPU1。
如果在优先级15上的线程3和线程4都是FIFO会怎样?按上面的描述,线程3还是始终无法获得CPU1,因为线程4每次都会插在3的前面,再调度就又是4获得CPU1。除非线层4进入了阻塞状态(从而不在READY队列里了),那么线程3才能获得CPU。
“零星调度”(Sporadic)算法比较特殊,它比较适合长时间占用CPU的线程。它的基本设计思想是给一个线程准备两个优先级,“前台”优先级比较高,“后台”优先级稍微底一点。如果线程在高优先级连续占用CPU超过一定时间后,线程会被强行降到“后台”低优先级上(这时线程能不能占用CPU取决于系统中有没有比“后台”优先级高的别的线程了);然后线程在低优先级上经过了一段时间后,会重新被调回高优先级。
图 4 零星调度示意
上图是一个零星调度线程的示意。
  • 开始的时候,线程在比较高的(正常)优先级 H 上运行,一直到把预先分配给零星调度的时间用完(sched_ss_init_budget)
  • 这时,线程会被自动调整为低优先级L(sched_ss_low_priority);一旦被调低,线程也可能运行(如果优先级L依然是系统里最高优先级的线程),也可能无法运行呆在READY队列里(系统里有比L更高的优先级)
  • 不管线程有没有执行,从最开始运行时间点算起,当线程“执行补充时间"(sched_ss_repl_period)过了以后,线程的优先级被重新提到优先级H,并试图取得CPU来。
“零星调度”看上去比较“公平”,但是实际在用QNX的项目中,这个调度算法很少被用户用到。主要是因为一般来说在QNX上很少有线程能够“连续占用CPU”的。而且当系统变得复杂,线程数成百上千后,这种上下调优先级的做法,很容易出现别的后遗症。

什么时候会发生调度?

上面介绍了QNX支持的几个调度算法。那么,什么时候才会发生调度呢?
QNX的设计目标是一个硬实时操作系统,所以,保证最高优先级的线程在第一时间占据CPU是很重要的。考虑到线程的状态都是在内核中进行变化的(都是因为线程进行了某个内核调用后变化的),所以QNX在每次从内核调用退出时,都会进行一次线程调度,以保证最高优先级的线程可以占据CPU。
得益于微内核结构,QNX的内核调用通常都非常短,或者说,每一个内核调用,都能够比较确定地知道要花多少时间。而且,因为微内核系统的基本就是进程间通信,所以在QNX上,一段程序非常容易进入内核并进行线程状态切换,很少能有长时间占满CPU的,在实际系统上测,现实上很少能有线程执行完整个时间片的。
举个例子,哪怕程序里只写一个 printf("Hello World!n"); 可是在libc库里,最后这个会变成一个IO_WRITE消息,MsgSend() 给控制台驱动;这时,在MsgSend()这个内核调用里,会把printf() 的线程置为阻塞状态(REPLY BLOCK),同时会把控制台驱动的信息接收线程(从RECEIVE BLOCK)改到 READY状态,并放入 READY 队列。当退出MsgSend() 内核调用时,线程调度发生,通常情况下(如果没有别的线程READY 的话)控制台驱动的信息接收线程被激活,并占据CPU.
如果用户写了一个既不内核调用,也不放弃CPU的线程会怎么样?那时候,时钟中断会发生,当内核记时到线程占据了一整个时间片(QNX上是4ms)后,内核会强制当前线程进入 READY,并重新调度。如果同一优先级只有这一个线程(这是优先级最高线程),那么调度后,还是这个线程获取CPU。如果同一优先级有别的线程存在,那么根据调度算法来决定哪个线程获得CPU。

另一种常见情况是,由于某些别的原因导致高优先级线程被激活,比如网卡驱动中断导致高优先级驱动线程READY,所设时钟到达导致高优先级线程从阻塞状态返回READY状态了,当前线程开放互斥锁之类的线程同步对象,导致别的线程返回READY状态了。这些,都会在从内核调用退出时,进行调度。AFmednc

文章来源及版权属于汽车电子与软件,EDN电子技术设计仅作转载分享,对文中陈述、观点判断保持中立,不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。如有疑问,请联系Demi.xia@aspencore.com
汽车电子与软件
汽车电子与软件
  • 微信扫一扫
    一键转发
  • 最前沿的电子设计资讯
    请关注“电子技术设计微信公众号”
广告
广告
热门推荐
广告
广告
EE直播间
在线研讨会
广告
面包芯语
广告
向右滑动:上一篇 向左滑动:下一篇 我知道了