linux的调度算法
1. linux系统的进程调度
Linux进程调度
1.调度方式
Linux系统的调度方式基本上采用“ 抢占式优先级 ”方式,当进程在用户模式下运行时,不管它是否自愿,核心在一定条件下(如该进程的时间片用完或等待I/O)可以暂时中止其运行,而调度其他进程运行。一旦进程切换到内核模式下运行时,就不受以上限制,而一直运行下去,仅在重新回到用户模式之前才会发生进程调度。
Linux系统中的调度基本上继承了UNIX系统的 以优先级为基础 的调度。也就是说,核心为系统中每个进程计算出一个优先级,该优先级反映了一个进程获得CPU使用权的资格,即高优先级的进程优先得到运行。核心从进程就绪队列中挑选一个优先级最高的进程,为其分配一个CPU时间片,令其投入运行。在运行过程中,当前进程的优先级随时间递减,这样就实现了“负反馈”作用,即经过一段时间之后,原来级别较低的进程就相对“提升”了级别,从而有机会得到运行。当所有进程的优先级都变为0(最低)时,就重新计算一次所有进程的优先级。
2.调度策略
Linux系统针对不同类别的进程提供了3种不同的调度策略,即SCHED_FIFO、SCHED_RR及SCHED_OTHER。其中,SCHED_FIFO适合于 短实时进程 ,它们对时间性要求比较强,而每次运行所需的时间比较短。一旦这种进程被调度且开始运行,就一直运行到自愿让出CPU或被优先级更高的进程抢占其执行权为止。
SCHED_RR对应“时间片轮转法”,适合于每次运行需要 较长时间的实时进程 。一个运行进程分配一个时间片(200 ms),当时间片用完后,CPU被另外进程抢占,而该进程被送回相同优先级队列的末尾,核心动态调整用户态进程的优先级。这样,一个进程从创建到完成任务后终止,需要经历多次反馈循环。当进程再次被调度运行时,它就从上次断点处开始继续执行。
SCHED_OTHER是传统的UNIX调度策略,适合于交互式的 分时进程 。这类进程的优先级取决于两个因素:一个是进程剩余时间配额,如果进程用完了配给的时间,则相应优先级降到0;另一个是进程的优先数nice,这是从UNIX系统沿袭下来的方法,优先数越小,其优先级越高。nice的取值范围是-20 19。用户可以利用nice命令设定进程的nice值。但一般用户只能设定正值,从而主动降低其优先级;只有特权用户才能把nice的值设置为负数。进程的优先级就是以上二者之和。
后台命令对应后台进程(又称后台作业)。后台进程的优先级低于任何交互(前台)进程的优先级。所以,只有当系统中当前不存在可运行的交互进程时,才调度后台进程运行。后台进程往往按批处理方式调度运行。
3.调度时机
核心进行进程调度的时机有以下5种情况:
(1)当前进程调用系统调用nanosleep( )或者pause( ),使自己进入睡眠状态,主动让出一段时间的CPU的使用权。
(2)进程终止,永久地放弃对CPU的使用。
(3)在时钟中断处理程序执行过程中,发现当前进程连续运行的时间过长。
(4)当唤醒一个睡眠进程时,发现被唤醒的进程比当前进程更有资格运行。
(5)一个进程通过执行系统调用来改变调度策略或者降低自身的优先级(如nice命令),从而引起立即调度。
4.调度算法
进程调度的算法应该比较简单,以便减少频繁调度时的系统开销。Linux执行进程调度时,首先查找所有在就绪队列中的进程,从中选出优先级最高且在内存的一个进程。如果队列中有实时进程,那么实时进程将优先运行。如果最需要运行的进程不是当前进程,那么当前进程就被挂起,并且保存它的现场—— 所涉及的一切机器状态,包括程序计数器和CPU寄存器等,然后为选中的进程恢复运行现场。
(二)Linux常用调度命令
· nohup命令
nohup命令的功能是以忽略挂起和退出的方式执行指定的命令。其命令格式是:
nohupcommand[arguments]
其中,command是所要执行的命令,arguments是指定命令的参数。
nohup命令告诉系统,command所代表的命令在执行过程中不受任何结束运行的信号(hangup和quit)的影响。例如,
$ nohup find / -name exam.txt -print>f1 &
find命令在后台运行。在用户注销后,它会继续运行:从根目录开始,查找名字是exam.txt的文件,结果被定向到文件f1中。
如果用户没有对输出进行重定向,则输出被附加到当前目录的nohup.out文件中。如果用户在当前目录中不具备写权限,则输出被定向到$HOME/nohup.out 中。
· at命令
at命令允许指定命令执行的时间。at命令的常用形式是:
attimecommand
其中,time是指定命令command在将来执行时的时间和日期。时间的指定方法有多种,用户可以使用绝对时间,也可以用相对时间。该指定命令将以作业形式在后台运行。例如:
$ at 15:00 Oct 20
回车后进入接收方式,接着键入以下命令:
mail -s "Happy Birthday!" liuzheny
按下D键,屏幕显示:
job 862960800.a at Wed Oct 20 15:00:00 CST 1999
$
表明建立了一个作业,其作业ID号是862960800.a,运行作业的时间是1999年10月20日下午3:00,给liuzheny发一条标题为“Happy Birthday!”(生日快乐)的空白邮件。
利用 at-l 可以列出当前at队列中所有的作业。
利用 at-r 可以删除指定的作业。这些作业以前由at或batch命令调度。例如,
at-r862960797.a
将删除作业ID号是862960797.a的作业。其一般使用形式是:
at-rjob_id
注意,结尾是.a的作业ID号,表示这个作业是由at命令提交的;结尾是.b的作业ID号,表示这个作业是由batch命令提交的。
· batch命令
batch命令不带任何参数,它提交的作业的优先级比at命令提交的作业的优先级低。batch无法指定作业运行的时间。实际运行时间要看系统中已经提交的作业数量。如果系统中优先级较高的作业比较多,那么,batch提交的作业则需要等待;如果系统空闲,则运行batch提交的作业。例如,
$ batch
回车后进入接收方式,接着键入命令:
find / -name exam.txt -print
按下D。退出接收方式,屏幕显示:
job 862961540.b at Thu Nov 18 14:30:00 CST 1999
表示find命令被batch作为一个作业提交给系统,作业ID号是862961540.b。如果系统当前空闲,这个作业被立即执行,其结果同样作为邮件发送给用户。
· jobs命令
jobs命令用来显示当前shell下正在运行哪些作业(即后台作业)。例如:
$ jobs
[2] + Running tar tv3 *&
[1] - Running find / -name README -print > logfile &
$
其中,第一列方括号中的数字表示作业序号,它是由当前运行的shell分配的,而不是由操作系统统一分配的。在当前shell环境下,第一个后台作业的作业号为1,第二个作业的作业号为2,等等。
第二列中的“ ”号表示相应作业的优先级比“-”号对应作业的优先级高。
第三列表明作业状态,是否为运行、中断、等待输入或停止等。
最后列出的是创建当前这个作业所对应的命令行。
利用 jobs-l 形式,可以在作业号后显示出相应进程的PID。如果想只显示相应进程的PID,不显示其它信息,则使用 jobs-p 形式。
· fg命令
fg命令把指定的后台作业移到前台。其使用格式是:
fg [job…]
其中,参数job是一个或多个进程的PID,或者是命令名称或者作业号(前面要带有一个“%”号)。例如:
$ jobs
[2] + Running tar tv3 *&
[1] - Running find / -name README -print > logfile&
$ fg %find
find / -name README -print > logfile
注意,显示的命令行末尾没有“&”符号。下面命令能产生同样的效果:
$ fg %1
这样,find命令对应的进程就在前台执行。当后台只有一个作业时,键入不带参数的fg命令,就能使相应进程移到前台。当有两个或更多的后台作业时,键入不带参数的fg,就把最后进入后台的进程首先移到前台。
· bg命令
bg命令可以把前台进程换到后台执行。其使用格式是:
bg [job…]
其中,job是一个或多个进程的PID、命令名称或者作业号,在参数前要带“%”号。例如,在cc(C编译命令)命令执行过程中,按下Z键,使这个作业挂起。然后键入以下命令:
$ bg %cc
该挂起的作业在后台重新开始执行。
2. Linux - 进程调度
进程调度算法也称 CPU 调度算法,毕竟进程是由 CPU 调度的。
当 CPU 空闲时,操作系统就选择内存中的某个“就绪状态”的进程,并给其分配 CPU。
什么时候会发生 CPU 调度呢?通常有以下情况:
其中发生在 1 和 4 两种情况下的调度称为“非抢占式调度”,2 和 3 两种情况下发生的调度称为“抢占式调度”。
非抢占式的意思就是,当进程正在运行时,它就会一直运行,直到该进程完成或发生某个事件而被阻塞时,才会把 CPU 让给其他进程。
而抢占式调度,顾名思义就是进程正在运行的时候,可以被打断,使其把 CPU 让给其他进程。那抢占的原则一般有三种,分别是时间片原则、优先权原则、短作业优先原则。
你可能会好奇为什么第 3 种情况也会发生 CPU 调度呢?假设有一个进程是处于等待状态的,但是它的优先级比较高,如果该进程等待的事件发生了,它就会转到就绪状态,一旦它转到就绪状态,如果我们的调度算法是以优先级来进行调度的,那么它就会立马抢占正在运行的进程,所以这个时候就会发生 CPU 调度。
那第 2 种状态通常是时间片到的情况,因为时间片到了就会发生中断,于是就会抢占正在运行的进程,从而占用 CPU。
调度算法影响的是等待时间(进程在就绪队列中等待调度的时间总和),而不能影响进程真在使用 CPU 的时间和 I/O 时间。
最简单的一个调度算法,就是非抢占式的先来先服务(First Come First Severd, FCFS)算法了。
顾名思义,先来后到,每次从就绪队列选择最先进入队列的进程,然后一直运行,直到进程退出或被阻塞,才会继续从队列中选择第一个进程接着运行。
这似乎很公平,但是当一个长作业先运行了,那么后面的短作业等待的时间就会很长,不利于短作业。
FCFS 对长作业有利,适用于 CPU 繁忙型作业的系统,而不适用于 I/O 繁忙型作业的系统。
最短作业优先(Shortest Job First, SJF)调度算法同样也是顾名思义,它会优先选择运行时间最短的进程来运行,这有助于提高系统的吞吐量。
这显然对长作业不利,很容易造成一种极端现象。
比如,一个长作业在就绪队列等待运行,而这个就绪队列有非常多的短作业,那么就会使得长作业不断的往后推,周转时间变长,致使长作业长期不会被运行。
前面的“先来先服务调度算法”和“最短作业优先调度算法”都没有很好的权衡短作业和长作业。
那么,高响应比优先 (Highest Response Ratio Next, HRRN)调度算法主要是权衡了短作业和长作业。
每次进行进程调度时,先计算“响应比优先级”,然后把“响应比优先级”最高的进程投入运行,“响应比优先级”的计算公式:
从上面的公式,可以发现:
最古老、最简单、最公平且使用最广的算法就是时间片轮转(Round Robin, RR)调度算法。
每个进程被分配一个时间段,称为时间片(Quantum),即允许该进程在该时间段中运行。
另外,时间片的长度就是一个很关键的点:
通常时间片设为 20ms~50ms 通常是一个比较合理的折中值。
前面的“时间片轮转算法”做了个假设,即让所有的进程同等重要,也不偏袒谁,大家的运行时间都一样。
但是,对于多用户计算机系统就有不同的看法了,它们希望调度是有优先级的,即希望调度程序能从就绪队列中选择最高优先级的进程进行运行,这称为最高优先级(Highest Priority First,HPF)调度算法。
进程的优先级可以分为,静态优先级或动态优先级:
该算法也有两种处理优先级高的方法,非抢占式和抢占式:
但是依然有缺点,可能会导致低优先级的进程永远不会运行。
多级反馈队列(Multilevel Feedback Queue)调度算法是“时间片轮转算法”和“最高优先级算法”的综合和发展。
顾名思义:
工作原理:
设置了多个队列,赋予每个队列不同的优先级,每个队列优先级从高到低,同时优先级越高时间片越短;
新的进程会被放入到第一级队列的末尾,按先来先服务的原则排队等待被调度,如果在第一级队列规定的时间片没运行完成,则将其转入到第二级队列的末尾,以此类推,直至完成;
当较高优先级的队列为空,才调度较低优先级的队列中的进程运行。如果进程运行时,有新进程进入较高优先级的队列,则停止当前运行的进程并将其移入到原队列末尾,接着让较高优先级的进程运行;
可以发现,对于短作业可能可以在第一级队列很快被处理完。对于长作业,如果在第一级队列处理不完,可以移入下次队列等待被执行,虽然等待的时间变长了,但是运行时间也会更长了,所以该算法很好的兼顾了长短作业,同时有较好的响应时间。
整体架构如下,即调度策略是模块化设计的,调度器根据不同的进程依次遍历不同的调度策略,找到进程对应的调度策略,调度的结果即为选出一个可运行的进程指针,并将其加入到进程可运行队列中。
以一棵红黑树管理所有需要调度的进程,
红黑树,左边节点小于右边节点的值,运行到目前为止vruntime最小的进程,同时考虑了CPU/IO和nice,总是找vruntime最小的线程调度。
vruntime = pruntime/weight × 1024;
vruntime是虚拟运行时间,pruntime是物理运行时间,weight权重由nice值决定(nice越低权重越高),则运行时间少、nice值低的的线程vruntime小,将得到优先调度。这是一个随运行而动态变化的过程。
3. linux io调度算法都有哪些
I/O调度的4种算法
1)CFQ(完全公平排队I/O调度程序)
特点:
在最新的内核版本和发行版中,都选择CFQ做为默认的I/O调度器,对于通用的服务器也是最好的选择.
CFQ试图均匀地分布对I/O带宽的访问,避免进程被饿死并实现较低的延迟,是deadline和as调度器的折中.
CFQ对于多媒体应用(video,audio)和桌面系统是最好的选择.
CFQ赋予I/O请求一个优先级,而I/O优先级请求独立于进程优先级,高优先级的进程的读写不能自动地继承高的I/O优先级.
工作原理:
CFQ为每个进程/线程,单独创建一个队列来管理该进程所产生的请求,也就是说每个进程一个队列,各队列之间的调度使用时间片来调度,
以此来保证每个进程都能被很好的分配到I/O带宽.I/O调度器每次执行一个进程的4次请求.
2)NOOP(电梯式调度程序)
特点:
在Linux2.4或更早的版本的调度程序,那时只有这一种I/O调度算法.
NOOP实现了一个简单的FIFO队列,它像电梯的工作主法一样对I/O请求进行组织,当有一个新的请求到来时,它将请求合并到最近的请求之后,以此来保证请求同一介质.
NOOP倾向饿死读而利于写.
NOOP对于闪存设备,RAM,嵌入式系统是最好的选择.
电梯算法饿死读请求的解释:
因为写请求比读请求更容易.
写请求通过文件系统cache,不需要等一次写完成,就可以开始下一次写操作,写请求通过合并,堆积到I/O队列中.
读请求需要等到它前面所有的读操作完成,才能进行下一次读操作.在读操作之间有几毫秒时间,而写请求在这之间就到来,饿死了后面的读请求.
3)Deadline(截止时间调度程序)
特点:
通过时间以及硬盘区域进行分类,这个分类和合并要求类似于noop的调度程序.
Deadline确保了在一个截止时间内服务请求,这个截止时间是可调整的,而默认读期限短于写期限.这样就防止了写操作因为不能被读取而饿死的现象.
Deadline对数据库环境(ORACLE RAC,MYSQL等)是最好的选择.
4)AS(预料I/O调度程序)
特点:
本质上与Deadline一样,但在最后一次读操作后,要等待6ms,才能继续进行对其它I/O请求进行调度.
可以从应用程序中预订一个新的读请求,改进读操作的执行,但以一些写操作为代价.
它会在每个6ms中插入新的I/O操作,而会将一些小写入流合并成一个大写入流,用写入延时换取最大的写入吞吐量.
AS适合于写入较多的环境,比如文件服务器
AS对数据库环境表现很差.
4. 关于linux的调度算法
Linux2.6
版本的
Linux
内核使用了新的调度器算法,它是由
Ingo
Molnar开发的
O(1)调度器算法。它在高负载的情况下极其出色,并且对处理器调度有很好的扩展。
Linux2.4
版本的标准调度器中,使用时间片重算的算法。这种算法要求在所有的进程都用尽时间片以后,重新计算下一次运行的时间片。这样每次任务调度的花销不确定,可能因为计算比较复杂,产生较大调度延迟。特别是多处理器系统,可能由于调度的延迟,导致大部分处理器处于空闲
状态,影响系统性能。
新的调度器采用
O(1)的调度算法,通过优先级数组的数据结构来实现。优先级数组可以使每个优先级都有相应的任务队列,还有一个优先级位图,每个优先级对应位图中一位,通过位图可快速执行最高优先级任务。因优先级个数是固定的,所以查找的时间也固定,不受运行任务数的影响。
新的调度器为每个处理器维护
2
个优先级数组:有效数组和过期数组。有效数组内任务队列的进程都还有可以运行的时间片;过期数组内任务队列的进程都没有时间片可以执行。当一个进程的时间片用光时,就把它从有效数组移到过期数组,并且时间片也已经重新计算好了。当需要重新调度这些任务的时候,只要在有效数组和过期数组之间切换就好了。这种交换是O(1)算法的核心。
关于该算法的更多内容,google
一下!
5. linux环境下的进程调度算法有哪些
第一部分: 实时调度算法介绍
对于什么是实时系统,POSIX 1003.b作了这样的定义:指系统能够在限定的响应时间内提供所需水平的服务。而一个由Donald Gillies提出的更加为大家接受的定义是:一个实时系统是指计算的正确性不仅取决于程序的逻辑正确性,也取决于结果产生的时间,如果系统的时间约束条件得不到满足,将会发生系统出错。
实时系统根据其对于实时性要求的不同,可以分为软实时和硬实时两种类型。硬实时系统指系统要有确保的最坏情况下的服务时间,即对于事件的响应时间的截止期限是无论如何都必须得到满足。比如航天中的宇宙飞船的控制等就是现实中这样的系统。其他的所有有实时特性的系统都可以称之为软实时系统。如果明确地来说,软实时系统就是那些从统计的角度来说,一个任务(在下面的论述中,我们将对任务和进程不作区分)能够得到有确保的处理时间,到达系统的事件也能够在截止期限到来之前得到处理,但违反截止期限并不会带来致命的错误,像实时多媒体系统就是一种软实时系统。
一个计算机系统为了提供对于实时性的支持,它的操作系统必须对于CPU和其他资源进行有效的调度和管理。在多任务实时系统中,资源的调度和管理更加复杂。本文下面将先从分类的角度对各种实时任务调度算法进行讨论,然后研究普通的 Linux操作系统的进程调度以及各种实时Linux系统为了支持实时特性对普通Linux系统所做的改进。最后分析了将Linux操作系统应用于实时领域中时所出现的一些问题,并总结了各种实时Linux是如何解决这些问题的。
1. 实时CPU调度算法分类
各种实时操作系统的实时调度算法可以分为如下三种类别[Wang99][Gopalan01]:基于优先级的调度算法(Priority-driven scheling-PD)、基于CPU使用比例的共享式的调度算法(Share-driven scheling-SD)、以及基于时间的进程调度算法(Time-driven scheling-TD),下面对这三种调度算法逐一进行介绍。
1.1. 基于优先级的调度算法
基于优先级的调度算法给每个进程分配一个优先级,在每次进程调度时,调度器总是调度那个具有最高优先级的任务来执行。根据不同的优先级分配方法,基于优先级的调度算法可以分为如下两种类型[Krishna01][Wang99]:
静态优先级调度算法:
这种调度算法给那些系统中得到运行的所有进程都静态地分配一个优先级。静态优先级的分配可以根据应用的属性来进行,比如任务的周期,用户优先级,或者其它的预先确定的策略。RM(Rate-Monotonic)调度算法是一种典型的静态优先级调度算法,它根据任务的执行周期的长短来决定调度优先级,那些具有小的执行周期的任务具有较高的优先级。
动态优先级调度算法:
这种调度算法根据任务的资源需求来动态地分配任务的优先级,其目的就是在资源分配和调度时有更大的灵活性。非实时系统中就有很多这种调度算法,比如短作业优先的调度算法。在实时调度算法中, EDF算法是使用最多的一种动态优先级调度算法,该算法给就绪队列中的各个任务根据它们的截止期限(Deadline)来分配优先级,具有最近的截止期限的任务具有最高的优先级。
1.2. 基于比例共享调度算法
虽然基于优先级的调度算法简单而有效,但这种调度算法提供的是一种硬实时的调度,在很多情况下并不适合使用这种调度算法:比如象实时多媒体会议系统这样的软实时应用。对于这种软实时应用,使用一种比例共享式的资源调度算法(SD算法)更为适合。
比例共享调度算法指基于CPU使用比例的共享式的调度算法,其基本思想就是按照一定的权重(比例)对一组需要调度的任务进行调度,让它们的执行时间与它们的权重完全成正比。
我们可以通过两种方法来实现比例共享调度算法[Nieh01]:第一种方法是调节各个就绪进程出现在调度队列队首的频率,并调度队首的进程执行;第二种做法就是逐次调度就绪队列中的各个进程投入运行,但根据分配的权重调节分配个每个进程的运行时间片。
比例共享调度算法可以分为以下几个类别:轮转法、公平共享、公平队列、彩票调度法(Lottery)等。
比例共享调度算法的一个问题就是它没有定义任何优先级的概念;所有的任务都根据它们申请的比例共享CPU资源,当系统处于过载状态时,所有的任务的执行都会按比例地变慢。所以为了保证系统中实时进程能够获得一定的CPU处理时间,一般采用一种动态调节进程权重的方法。
1.3. 基于时间的进程调度算法
对于那些具有稳定、已知输入的简单系统,可以使用时间驱动(Time-driven:TD)的调度算法,它能够为数据处理提供很好的预测性。这种调度算法本质上是一种设计时就确定下来的离线的静态调度方法。在系统的设计阶段,在明确系统中所有的处理情况下,对于各个任务的开始、切换、以及结束时间等就事先做出明确的安排和设计。这种调度算法适合于那些很小的嵌入式系统、自控系统、传感器等应用环境。
这种调度算法的优点是任务的执行有很好的可预测性,但最大的缺点是缺乏灵活性,并且会出现有任务需要被执行而CPU却保持空闲的情况。
2. 通用Linux系统中的CPU调度
通用Linux系统支持实时和非实时两种进程,实时进程相对于普通进程具有绝对的优先级。对应地,实时进程采用SCHED_FIFO或者SCHED_RR调度策略,普通的进程采用SCHED_OTHER调度策略。
在调度算法的实现上,Linux中的每个任务有四个与调度相关的参数,它们是rt_priority、policy、priority(nice)、counter。调度程序根据这四个参数进行进程调度。
在SCHED_OTHER 调度策略中,调度器总是选择那个priority+counter值最大的进程来调度执行。从逻辑上分析,SCHED_OTHER调度策略存在着调度周期(epoch),在每一个调度周期中,一个进程的priority和counter值的大小影响了当前时刻应该调度哪一个进程来执行,其中 priority是一个固定不变的值,在进程创建时就已经确定,它代表了该进程的优先级,也代表这该进程在每一个调度周期中能够得到的时间片的多少; counter是一个动态变化的值,它反映了一个进程在当前的调度周期中还剩下的时间片。在每一个调度周期的开始,priority的值被赋给 counter,然后每次该进程被调度执行时,counter值都减少。当counter值为零时,该进程用完自己在本调度周期中的时间片,不再参与本调度周期的进程调度。当所有进程的时间片都用完时,一个调度周期结束,然后周而复始。另外可以看出Linux系统中的调度周期不是静态的,它是一个动态变化的量,比如处于可运行状态的进程的多少和它们priority值都可以影响一个epoch的长短。值得注意的一点是,在2.4以上的内核中, priority被nice所取代,但二者作用类似。
可见SCHED_OTHER调度策略本质上是一种比例共享的调度策略,它的这种设计方法能够保证进程调度时的公平性--一个低优先级的进程在每一个epoch中也会得到自己应得的那些CPU执行时间,另外它也提供了不同进程的优先级区分,具有高priority值的进程能够获得更多的执行时间。
对于实时进程来说,它们使用的是基于实时优先级rt_priority的优先级调度策略,但根据不同的调度策略,同一实时优先级的进程之间的调度方法有所不同:
SCHED_FIFO:不同的进程根据静态优先级进行排队,然后在同一优先级的队列中,谁先准备好运行就先调度谁,并且正在运行的进程不会被终止直到以下情况发生:1.被有更高优先级的进程所强占CPU;2.自己因为资源请求而阻塞;3.自己主动放弃CPU(调用sched_yield);
SCHED_RR:这种调度策略跟上面的SCHED_FIFO一模一样,除了它给每个进程分配一个时间片,时间片到了正在执行的进程就放弃执行;时间片的长度可以通过sched_rr_get_interval调用得到;
由于Linux系统本身是一个面向桌面的系统,所以将它应用于实时应用中时存在如下的一些问题:
Linux系统中的调度单位为10ms,所以它不能够提供精确的定时;
当一个进程调用系统调用进入内核态运行时,它是不可被抢占的;
Linux内核实现中使用了大量的封中断操作会造成中断的丢失;
由于使用虚拟内存技术,当发生页出错时,需要从硬盘中读取交换数据,但硬盘读写由于存储位置的随机性会导致随机的读写时间,这在某些情况下会影响一些实时任务的截止期限;
虽然Linux进程调度也支持实时优先级,但缺乏有效的实时任务的调度机制和调度算法;它的网络子系统的协议处理和其它设备的中断处理都没有与它对应的进程的调度关联起来,并且它们自身也没有明确的调度机制;
3. 各种实时Linux系统
3.1. RT-Linux和RTAI
RT -Linux是新墨西哥科技大学(New Mexico Institute of Technology)的研究成果[RTLinuxWeb][Barabanov97]。它的基本思想是,为了在Linux系统中提供对于硬实时的支持,它实现了一个微内核的小的实时操作系统(我们也称之为RT-Linux的实时子系统),而将普通Linux系统作为一个该操作系统中的一个低优先级的任务来运行。另外普通Linux系统中的任务可以通过FIFO和实时任务进行通信。RT-Linux的框架如图 1所示:
图 1 RT-Linux结构
RT -Linux的关键技术是通过软件来模拟硬件的中断控制器。当Linux系统要封锁CPU的中断时时,RT-Linux中的实时子系统会截取到这个请求,把它记录下来,而实际上并不真正封锁硬件中断,这样就避免了由于封中断所造成的系统在一段时间没有响应的情况,从而提高了实时性。当有硬件中断到来时, RT-Linux截取该中断,并判断是否有实时子系统中的中断例程来处理还是传递给普通的Linux内核进行处理。另外,普通Linux系统中的最小定时精度由系统中的实时时钟的频率决定,一般Linux系统将该时钟设置为每秒来100个时钟中断,所以Linux系统中一般的定时精度为 10ms,即时钟周期是10ms,而RT-Linux通过将系统的实时时钟设置为单次触发状态,可以提供十几个微秒级的调度粒度。
RT-Linux实时子系统中的任务调度可以采用RM、EDF等优先级驱动的算法,也可以采用其他调度算法。
RT -Linux对于那些在重负荷下工作的专有系统来说,确实是一个不错的选择,但他仅仅提供了对于CPU资源的调度;并且实时系统和普通Linux系统关系不是十分密切,这样的话,开发人员不能充分利用Linux系统中已经实现的功能,如协议栈等。所以RT-Linux适合与工业控制等实时任务功能简单,并且有硬实时要求的环境中,但如果要应用与多媒体处理中还需要做大量的工作。
意大利的RTAI( Real-Time Application Interface )源于RT-Linux,它在设计思想上和RT-Linux完全相同。它当初设计目的是为了解决RT-Linux难于在不同Linux版本之间难于移植的问题,为此,RTAI在 Linux 上定义了一个实时硬件抽象层,实时任务通过这个抽象层提供的接口和Linux系统进行交互,这样在给Linux内核中增加实时支持时可以尽可能少地修改 Linux的内核源代码。
3.2. Kurt-Linux
Kurt -Linux由Kansas大学开发,它可以提供微秒级的实时精度[KurtWeb] [Srinivasan]。不同于RT-Linux单独实现一个实时内核的做法,Kurt -Linux是在通用Linux系统的基础上实现的,它也是第一个可以使用普通Linux系统调用的基于Linux的实时系统。
Kurt-Linux将系统分为三种状态:正常态、实时态和混合态,在正常态时它采用普通的Linux的调度策略,在实时态只运行实时任务,在混合态实时和非实时任务都可以执行;实时态可以用于对于实时性要求比较严格的情况。
为了提高Linux系统的实时特性,必须提高系统所支持的时钟精度。但如果仅仅简单地提高时钟频率,会引起调度负载的增加,从而严重降低系统的性能。为了解决这个矛盾, Kurt-Linux采用UTIME所使用的提高Linux系统中的时钟精度的方法[UTIMEWeb]:它将时钟芯片设置为单次触发状态(One shot mode),即每次给时钟芯片设置一个超时时间,然后到该超时事件发生时在时钟中断处理程序中再次根据需要给时钟芯片设置一个超时时间。它的基本思想是一个精确的定时意味着我们需要时钟中断在我们需要的一个比较精确的时间发生,但并非一定需要系统时钟频率达到此精度。它利用CPU的时钟计数器TSC (Time Stamp Counter)来提供精度可达CPU主频的时间精度。
对于实时任务的调度,Kurt-Linux采用基于时间(TD)的静态的实时CPU调度算法。实时任务在设计阶段就需要明确地说明它们实时事件要发生的时间。这种调度算法对于那些循环执行的任务能够取得较好的调度效果。
Kurt -Linux相对于RT-Linux的一个优点就是可以使用Linux系统自身的系统调用,它本来被设计用于提供对硬实时的支持,但由于它在实现上只是简单的将Linux调度器用一个简单的时间驱动的调度器所取代,所以它的实时进程的调度很容易受到其它非实时任务的影响,从而在有的情况下会发生实时任务的截止期限不能满足的情况,所以也被称作严格实时系统(Firm Real-time)。目前基于Kurt-Linux的应用有:ARTS(ATM Reference Traffic System)、多媒体播放软件等。另外Kurt-Linux所采用的这种方法需要频繁地对时钟芯片进行编程设置。
3.3. RED-Linux
RED -Linux是加州大学Irvine分校开发的实时Linux系统[REDWeb][ Wang99],它将对实时调度的支持和Linux很好地实现在同一个操作系统内核中。它同时支持三种类型的调度算法,即:Time-Driven、 Priority-Dirven、Share-Driven。
为了提高系统的调度粒度,RED-Linux从RT-Linux那儿借鉴了软件模拟中断管理器的机制,并且提高了时钟中断频率。当有硬件中断到来时,RED-Linux的中断模拟程序仅仅是简单地将到来的中断放到一个队列中进行排队,并不执行真正的中断处理程序。
另外为了解决Linux进程在内核态不能被抢占的问题, RED-Linux在Linux内核的很多函数中插入了抢占点原语,使得进程在内核态时,也可以在一定程度上被抢占。通过这种方法提高了内核的实时特性。
RED-Linux的设计目标就是提供一个可以支持各种调度算法的通用的调度框架,该系统给每个任务增加了如下几项属性,并将它们作为进程调度的依据:
Priority:作业的优先级;
Start-Time:作业的开始时间;
Finish-Time:作业的结束时间;
Budget:作业在运行期间所要使用的资源的多少;
通过调整这些属性的取值及调度程序按照什么样的优先顺序来使用这些属性值,几乎可以实现所有的调度算法。这样的话,可以将三种不同的调度算法无缝、统一地结合到了一起。
6. linux进程调度的三种策略是什么
进程调度策略就是调度系统种哪一个进程来CPU运行。这种调度分2层考虑。 第一层,进程状态这个是最优先考虑的,也就是说优先级最高的。在linux中只有就绪态的进程才有可能会被调度选中然后占有CPU,其它状态的进程不可能占有的到CPU。下面是linux中进程的状态TASK_RUNNING:就绪状态,得到CPU就可以运行。
TASK_INTERRUPTIBLE:浅度睡眠,资源到位或者受到信号就会变成就绪态。
TASK_UNINTERRUPTIBLE:深度睡眠,资源到位就会进入就绪态,不响应信号。
TASK_ZOMBIE:僵死态,进程exit后。
TASK_STOPPED:暂停态,收到SIG_CONT信号进入就绪态。 第二层,其实真正在操作系统中的实现,就是所有就绪态进程链接成一个队列,进程调度时候只会考虑这个队列中的进程,对其它的进程不考虑,这就实现了第一层中的要求。接下来就是就绪队列内部各个进程的竞争了。 Linux采用3种不同的调度政策,SCHED_FIFO(下面简写成FIFO,先来先服务),SCHED_RR(简写成RR,时间片轮流),SCHED_OTHER(下面简写成OTHER)。这里大家就能看出一个问题,采用同等调度政策的进程之间自然有可比性,Linux3种调度政策并存,那么不同调度政策间的进程如何比较呢?可以说他们之间根本就没有可比性。其实在调度时候,调度只看一个指标,那就是各个进程所具有的权值,权值最大的且在可执行队列中排在最前面的就会被调度执行。而权值的计算才会设计到各方面因素,其中调度政策可以说在计算权值中,份量是最重的。 为什么Linux要这么干呢?这是由于事务的多样性决定的,进程有实时性进程和非实时性的进程2种,FIFO和RR是用来支持实时性进程的调度,我们看一下这3种政策下权值的计算公式就明白了:FIFO和RR计算公式,权值=1000+进程真正的运行时间OTHER计算公式,当时间片为0时,权值=0.当时间片不为0时候,权值=剩余时间片+20-nice,同时如果是内核线程有+1的小加分,这是因为内核线程无需用户空间的切换,所以给它加了一分,奖励他在进程切换时候开销小的功劳。时间片好理解,那么nice这个值,用过linux系统的人都知道,这是一个从unix下继承过来的概念,表示谦让度,是一个从20~-19的数,可以通过nice和renice指令来设置。从代码中也能看到值越小就越不会谦让他人。 从这里我们看出FIFO和RR至少有1000的基数,所以在有FIFO和RR调度政策进程存在时,OTHER进程是没有机会被调度的到的。从权值计算公式同时也能看出,FIFO先来先服务的调度政策满足了,但RR这个时间片轮流的调度如果按照这种权值计算是不能满足时间片轮流这一概念的。这里只是权值的计算,在调度时候对RR政策的进程特殊处理。 以上都是权值计算,下面看看真正的调度过程,首先是对RR政策进程的特殊处理,如果当前进程采用的RR政策,那么看他的时间片是否用完,用完了就踢到就绪队列尾部,同时恢复他的时间片。然后是便利整个就绪队列,找到第一个权值最大的进程来运行。 整体调度效果就是:如果有FIFO和RR政策的进程,就优先调度他们2个,他们之间看已执行时间长短决定胜负,而2种政策内部则遵守各自调度政策。而OTHER只有在前面2种不存在于就绪队列时候才有可能执行,他们实际也是轮流执行,但他们之间是靠剩余时间和NICE值来决定胜负。同时就绪队列中排在最前面的最优先考虑在同样权值情况下。
7. linux调度算法的核心思想是什么
第一部分:实时调度算法
什么是实时系统,POSIX 1003.b作了这样的定义:是指系统可以在有限响应时间内提供所需的服务级别。较可取被定义为由Donald乔利士的的:一个实时系统的程序的逻辑正确性不仅取决于计算的准确度,而且还对结果,如果系统时间的限制不能满足将是一个系统错误发生。
基于实时系统的实时性要求的不同,可分为软实时和硬实时两种。硬实时系统是指系统必须确保,在最坏情况下的服务时间,截止日期为事件的响应时间是在任何情况下,必须满足。如航天飞船的控制是这样一个系统的现实。所有其他实时系统的特点,可以称为软实时系统。如果清除,软实时系统是那些从统计学的角度来看,一个任务(在下面的讨论中,我们将有任务和过程不作出区分),以确保系统的处理时间,可以得到事件可以处理的最后期限到来之前,违反的最后期限,并不会带来一个致命的错误,如实时多媒体系统是一种软实时系统。
一台电脑系统的CPU和其他资源进行有效的调度和管理,以提供实时操作系统的支持。的多任务的实时系统中,资源的调度和管理更复杂的。下面讨论本文将从各种实时任务调度算法的分类的角度来看,普通的Linux操作系统进程调度和各种实时Linux系统,然后研究,以支持实时特点,普通的Linux系统的改进。实时领域的一些问题,并总结了各种实时Linux的Linux操作系统,归根到底是如何解决这些问题。
CPU的实时调度算法的分类
多种实时操作系统的实时调度算法可以分为以下三类Wang99] [Gopalan01]:基于优先级调度算法(优先级驱动调度PD),基于在共享的CPU使用率调度算法(分享驱动调度SD)的比例,以及基于时间的进程调度算法(时间驱动调度TD),下面这三种调度算法逐一介绍。
1.1
/>基于优先级的调度算法,基于优先级的调度算法,每个进程被分配一个优先级,每次的进程调度程序,调度程序总是具有最高的调度优先级的任务执行。根据不同的优先级分配方法,基于优先级的调度算法可以分为以下两种类型的Krishna01] [Wang99]:静态优先级调度算法
该算法得到这些系统中运行的所有进程都静态分配一个优先级。静态优先级分配的属性的应用程序,如任务循环中的用户优先级,或其他预先确定的政策。 RM(速率单调)的调度算法是一个典型的静态优先级的调度算法,根据执行的任务的调度优先级的周期的长度确定,那些具有小的执行周期的任务的优先级较高。
动态优先级调度算法:
该算法基于任务的资源需求动态地分配任务的优先级,资源分配和调度的目的更大的灵活性。非实时系统,这种算法有很多,如短作业优先级调度算法。任务的实时调度算法,EDF算法是使用最广泛的动态优先级调度算法,该算法根据他们的截止日期(截止日期)分配优先级的就绪队列中的每个任务,最近期限具有最高的优先级。
1.2
基于优先级调度算法的调度算法是简单而有效的,但这种算法的基础上按比例份额是一个硬实时调度,许多的情况下,不适合使用此算法:例如,软实时应用,如实时多媒体会议系统。对于软实时应用程序,共享资源调度算法(SD算法)的比例使用是更合适的。
比例共享调度算法是指对CPU使用率的比例共享调度算法,其基本思路是按照一定的权重(比率),需要一组调度安排任务,以使它们的权重成比例的执行时间。
要实现比例共享调度算法[Nieh01]有两种方法:第一种方法是调整的准备过程中出现的调度队列队第一频率,并安排一线队的过程中,执行第二种方法是连续调度进程就绪队列中投产,但根据调整分配一个进程的运行时间片分配的权重。
比例共享调度算法可以分为以下类别:循环赛,公平份额,公平排队,的彩票调度方法,(彩票)。
比例共享调度算法的一个问题是,它并没有定义任何优先的概念,所有的任务都根据其应用的CPU资源的比例共享系统过载时,执行的所有任务将较慢比例。因此,为了确保该系统的实时过程中获得一定量的CPU处理时间,一般采用的是动态权重的调整过程。
1.3。基于时间进程调度算法的调度算法
对于那些具有稳定,简单的系统已知输入,您可以使用时间驱动(驱动时间时间:TD)数据处理,它可以提供一个良好的预测。这种调度算法本质上是一个设计定型的离线静态调度方法。在系统的设计阶段,所有处理的情况下,在明确的制度,每个任务切换的开始和结束的时间提前做出了明确的安排和设计。该算法是适用于小型嵌入式系统,自动化控制系统,传感器和其他应用环境。
该算法的优势是良好的可预测性任务的执行,但最大的缺点是缺乏灵活性,而且会有一个任务需要执行,而CPU保持空闲。
一般的Linux系统CPU调度
一般的Linux系统支持实时和非实时两种进程,实时进程与普通进程方面具有绝对的优先权。相应地,实时进程调度策略SCHED_FIFO或SCHED_RR,普通进程SCHED_OTHER调度策略。
每个任务调度算法的实现在Linux四种调度参数,它们是rt_priority优先政策(尼斯),计数器。调度进程调度的基础上,这四个参数。
SCHED_OTHER调度策略,调度程序总是会选择优先级+计数器的值进程调度的执行。从逻辑分析存在SCHED_OTHER调度策略调度处理来执行,其特征在于,所述优先级是一个固定的调度周期(历元),在每个调度周期内的过程中的优先级,计数器的值的大小的影响这一刻已经确定变量值的过程中被创建时,它代表了进程的优先级,也代表数量的时间片,通过该方法可以得到在每个调度周期内,计数器是一个动态值,它反映了当前调度周期的过程中,剩余的时间片。在每个调度周期的开始,分配给优先级值计数器,那么每一次进程被调度运行计数器的值?减少。当计数器的值是零,这个过程已经运行的时间片调度期内,不再参与调度周期进程调度。当所有的进程都用完了时间片调度期结束,然后一遍又一遍。此外,可以看出在Linux系统中的调度周期是不固定的,它的量是动态变化的,例如,在运行的进程的数目和它们的优先级值?可以影响一个划时代的长度。有一点值得注意的是,在2.4内核中,首要任务是不错的替换两个类似的作用。
按比例分担的调度策略调度策略SCHED_OTHER可见的性质,它的这种设计方法,以确保进程调度的公平性 - 一个低优先级进程,在每个时代也将得到他们的份额那些CPU的执行时间,此外,它也提供了不同的进程的优先级,进程执行时间可以得到更多的具有高优先级值。
对于实时的过程中,他们使用基于实时优先级rt_priority的优先级调度策略,但相同的实时优先级的进程调度方法是根据不同的调度策略,
BR /> SCHED_FIFO:不同的进程,根据静态优先级排队,然后在相同的优先级队列,先准备好运行的第一谁调度和运行的进程不会被终止,直到发生以下情况:1。高优先级的进程篡夺了CPU;自己的资源请求受阻;自己主动放弃CPU(呼叫SCHED_YIELD);
SCHED_RR是这样的:这个调度策略SCHED_FIFO与上述完全相同,除了时间片分配给每个进程,正在实施的过程中,给执行时间片,时间片的长度可以通过sched_rr_get_interval调用
由于Linux系统本身是一个桌面导向的系统,因此,它是用于在实时应用中的一些问题:/> /> Linux系统调度单位是10ms,所以它不能提供精确的定时中断; p>当一个进程调用系统调用进入内核模式运行,它不能被抢占;
Linux内核实现大量采用了封闭中断操作损失;
由于使用虚拟内存技术,当发生页面错误时,从硬盘中读取的数据交换的需要,但硬盘读取和写入的存储位置的随机性,将导致随机读取和写入时间,这在某些情况下,会影响实时任务期限;
虽然Linux的进程调度器还支持实时优先级,但由于缺乏有效的实时任务调度机制和调度算法;其网络子协议处理和其它设备的中断处理,调度伴有相应的过程和自己的有没有明确的调度机制;
各种实时Linux系统
Home>的的
3.1 RT-Linux和RTAI
RT-Linux是新墨西哥大学的研究(新墨西哥州技术学院)[RTLinuxWeb] [Barabanov97。其基本思路是,在Linux系统上的硬实时支持,它实现了一个微内核实时操作系统(也被称为RT-Linux的实时子系统),而普通的Linux系统作为一个低优先级任务在操作系统中运行。在正常的Linux系统的另一个任务可以沟通,通过FIFO和实时任务。 RT-Linux的框架如图1所示:
图1 RT-Linux的结构
RT-Linux的关键技术是软件模拟硬件中断控制器。当Linux系统不时阻止CPU中断,实时定量RT-Linux的子系统的请求拦截,爱不释手,而事实上并没有真正阻止硬件中断,从而避免了由于中断造成的封由系统在一段时间内没有响应,从而在改进的实时。当传递给Linux内核的RT-Linux的一个硬件中断到达截取的中断,并确定是否有一个实时子系统中断例程来处理或处理。此外,的最小定时的精度在正常的Linux系统是确定系统的实时时钟的频率,Linux的系统时钟被设置到时钟中断每秒100,所以在Linux的系统定时的精度10毫秒,即时钟周期10ms时,RT-Linux的实时时钟设置为单触发状态,可以提供更多的十几微秒调度粒度。
RT-Linux实时子系统的任务调度优先级驱动算法,RM,EDF等,也可用于其他调度算法。
RT-Linux的专有系统,重型工作,的确是一个不错的选择,但他只提供了CPU资源的调度和实时系统和Linux系统的关系不是非常密切,因此开发人员可以充分利用已在Linux系统中,如协议栈实现的功能。 RT-Linux的工业控制等实时任务简单和硬实时要求的环境,但大量的工作需要做,如果你想应用的多媒体处理。
意大利实时应用程序接口(RTAI)来自RT-Linux的,它是在设计和RT-Linux的思想相同。这是原来的设计中,为了解决问题,RT-Linux的不同版本的Linux之间很难很难移植,RTAI在Linux上定义的实时硬件抽象层,这个抽象层接口提供实时任务Linux系统的相互作用,这可以增加一点可以Linux内核源代码到Linux内核的实时支持。
3.2。 KURT-Linux的
KURT-Linux的堪萨斯大学开发的,它可以提供实时微秒精度[KurtWeb] [斯里尼瓦桑]。与RT-Linux的单独实现一个实时内核,KURT-Linux是常用的Linux系统的基础上实现的,这也是第一个基于Linux的实时系统可以使用普通的Linux系统调用。
KURT-Linux系统分为三种状态:正常状态,实时状态和混合状态,在正常状态下,它使用普通的Linux实时运行状态实时调度策略任务,实时和非实时任务的混合状态,可以执行实时状态可以被用来为实时的要求更加严格。
为了提高Linux系统的实时特性,有必要提高精度的时钟系统的支持。但是,如果只是简单地增加时钟频率将导致调度负载的增加,从而严重降低系统的性能。为了解决这个矛盾,KURT-Linux中使用的时钟精度的方法[UTIMEWeb]提高Linux系统UTIME,时钟芯片设置为单次触发状态(单拍模式),也就是每个时钟芯片设置超时,然后再次超时事件发生时,在时钟中断的处理程序所需的时钟芯片设置一个超时。其基本思想是一个精确的时间意味着我们需要的时钟中断发生时,我们需要一个更精确的时间,以达到这样的精度,但并不一定需要系统时钟频率。它采用了CPU时钟计数器时间戳计数器(TSC)提供准确的CPU频率精度的时间。
KURT-Linux的实时任务调度,使用静态CPU的实时调度算法,基于时间(TD)。实时任务需要实时事件发生在设计阶段就必须清楚列明。该算法可以实现更好的调度任务,对于那些谁周期。
KURT-Linux的相RT-Linux的优势之一是,你可以使用系统调用的Linux系统,它最初是专为硬实时支持,但因为它是简单的实现将使用一个简单的时间驱动调度取代Linux的调度,实时进程调度的影响等非实时任务,在某些情况下会发生实时任务的截止日期是脆弱的不符合的,也被称为严格的实时系统(快地实时)。基于KURT-Linux的应用程序:艺术(ATM参考交通系统),多媒体播放软件。 KURT-Linux的另一种方法,需要频繁的时钟芯片编程。
3.3。 RED-Linux的
RED-Linux是加州大学尔湾,实时Linux系统的发展[REDWeb] [Wang99],它将支持实时调度和Linux实现相同的操作系统内核。它支持三种类型的调度算法,即:时间驱动优先Dirven,分享驱动。
为了提高系统的调度粒度,RED-Linux的学习RT-Linux的软件模拟中断的管理机制,并增加频率的时钟中断。 RED-Linux的中断仿真程序只是简单地中断会在队列中排队一个硬件中断到来时,并没有进行实际的中断处理程序。
另外,为了解决Linux的内核模式的过程中不能被中断,RED-Linux的插入Linux内核抢占点原语的众多功能,使这一进程在内核模式下,也在一定程度上被抢占。通过这种方法提高了内核的实时特性。
RED-Linux的设计目标是提供常规调度框架可以支持多种调度算法,系统为每个任务增加几个属性,进程调度的基础上:
优先级:作业的优先级;
开始时间:工作的开始时间;
完成时间:工作的结束时间; BR p>预算:资源的数量在操作过程中要使用的工作;
调整值?这些属性和调度根据什么优先使用的这些属性值几乎所有的调度算法。在这种情况下,三种不同的调度算法无缝地一起耦合到一个统一的。
8. linux进程、线程及调度算法(三)
调度策略值得是大家都在ready时,并且CPU已经被调度时,决定谁来运行,谁来被调度。
两者之间有一定矛盾。
响应的优化,意味着高优先级会抢占优先级,会花时间在上下文切换,会影响吞吐。
上下文切换的时间是很短的,几微妙就能搞定。上下文切换本身对吞吐并多大影响, 重要的是,切换后引起的cpu 的 cache miss.
每次切换APP, 数据都要重新load一次。
Linux 会尽可能的在响应与吞吐之间寻找平衡。比如在编译linux的时候,会让你选择 kernal features -> Preemption model.
抢占模型会影响linux的调度算法。
所以 ARM 的架构都是big+LITTLE, 一个很猛CPU+ 多个 性能较差的 CPU, 那么可以把I/O型任务的调度 放在 LITTLE CPU上。需要计算的放在big上。
早期2.6 内核将优先级划分了 0-139 bit的优先级。数值越低,优先级越高。0-99优先级 都是 RT(即时响应)的 ,100-139都是非RT的,即normal。
调度的时候 看哪个bitmap 中的 优先级上有任务ready。可能多个任务哦。
在普通优先级线程调度中,高优先级并不代表对低优先级的绝对优势。会在不同优先级进行轮转。
100 就是比101高,101也会比102高,但100 不会堵着101。
众屌丝进程在轮转时,优先级高的:
初始设置nice值为0,linux 会探测 你是喜欢睡眠,还是干活。越喜欢睡,linux 越奖励你,优先级上升(nice值减少)。越喜欢干活,优先级下降(nice值增加)。所以一个进程在linux中,干着干着 优先级越低,睡着睡着 优先级越高。
后期linux补丁中
红黑树,数据结构, 左边节点小于右边节点
同时兼顾了 CPU/IO 和 nice。
数值代表着 进程运行到目前为止的virtual runtime 时间。
(pyhsical runtime) / weight * 1024(系数)。
优先调度 节点值(vruntime)最小的线程。权重weight 其实有nice 来控制。
一个线程一旦被调度到,则物理运行时间增加,vruntime增加,往左边走。
weight的增加,也导致vruntime减小,往右边走。
总之 CFS让线程 从左滚到右,从右滚到左。即照顾了I/O(喜欢睡,分子小) 也 照顾了 nice值低(分母高).所以 由喜欢睡,nice值又低的线程,最容易被调度到。
自动调整,无需向nice一样做出奖励惩罚动作,个人理解权重其实相当于nice
但是 此时 来一个 0-99的线程,进行RT调度,都可以瞬间秒杀你!因为人家不是普通的,是RT的!
一个多线程的进程中,每个线程的调度的策略 如 fifo rr normal, 都可以不同。每一个的优先级都可以不一样。
实验举例, 创建2个线程,同时开2个:
运行2次,创建两个进程
sudo renice -n -5(nice -5级别) -g(global), 会明显看到 一个进程的CPU占用率是另一个的 3倍。
为什么cpu都已经达到200%,为什么系统不觉得卡呢?因为,我们的线程在未设置优先级时,是normal调度模式,且是 CPU消耗型 调度级别其实不高。
利用chrt工具,可以将进程 调整为 50 从normal的调度策略 升为RT (fifo)级别的调度策略,会出现:
chrt , nice renice 的调度策略 都是以线程为单位的,以上 设置的将进程下的所有线程进行设置nice值
线程是调度单位,进程不是,进程是资源封装单位!
两个同样死循环的normal优先级线程,其中一个nice值降低,该线程的CPU 利用率就会比另一个CPU的利用率高。