linux进程调度

Posted on | Edited on | In | Views:

进程优先级

linux采用两种不同的优先级范围.
第一种用nice值,范围为-20到19,越低优先级越高.
第二种是实时优先级,从0-99,越大优先级越高.

在系统调度中总会解决I/O密集型的和CPU密集型的进程的协调,I/O密集型要求有更好的响应性,而执行时间应该更少.CPU要求有更好的执行时间,而不是花费更多时间用来调度.

调度器类

linux调度器是以模块方式提供的,每个模块化结构成为调度器类,允许多种不同的可动态添加的调度算法并存.每个调度器都有一个优先级,会按照优先级顺序便利调度类,拥有一个可执行进程的最高优先级的调度器类胜出,选出下面要执行的一个程序.

公平调度

在linux中采用公平调度算法CFS,允许每个进程运行一段时间,循环轮转,选择运行最少的进程作为下一个运行进程,而不在采用分配给每个进程时间片.CFS在所有可运行进程总数基础上计算出一个进程应该运行多久.通过用nice值作为进程获得处理器运行比的权重,越低的优先级进程获得更低的处理器使用权重.在这里nice值并不是通过绝对值值来进行划分的,而是通过相对差值来分配权重的.避免了优先级差值不大的两个进程得到的处理器使用权重相差过大的情况.
在这里是由操作系统来确定进程应该使用多久,假设nice=0的进程分配时间片为100ms,则另一个nice=20的进程时间片为5ms.
如果按照绝对差值来分配时间片可能出现下列情况:
两个进程优先级分别为0和1,一个为100ms,则另一个为95ms,这时候基本没有问题.但是当两个优先级分别为18和19,那么一个为10ms,一个为5ms,这样前者比后者多出了一倍的处理器时间,是相对不合理的.

linux调度的实现

时间记账

CFS不再有时间片概念,维护每个进程运行的时间的记账,保存在进程描述符中.
每个进程都有一个虚拟运行时间,该运行时间的计算是所有可运行进程总数的标准化(是被加权的).虚拟时间以ns为单位.CFS使用vruntime变量来记录一个程序到底运行了多长时间以及还应该在运行多久.
vruntime运行时间计算如下:

  • 首先的到当前进程的执行时间,然后在根据当前可运行进程总数对运行时间进行加权计算,在将权重值与当前进程的vruntime相加.
  • vruntime准确的测量给定进程的运行时间,而且可知道谁应该是下一个被运行的进程,因为他是根据运行时间最小的进程优先调度的.
1
2
3
4
5
6
7
8
9
10
static const int prio_to_weight[40] = {
/* -20 */     88761,     71755,     56483,     46273,     36291,
/* -15 */     29154,     23254,     18705,     14949,     11916,
/* -10 */      9548,      7620,      6100,      4904,      3906,
/*  -5 */      3121,      2501,      1991,      1586,      1277,
/*   0 */      1024,       820,       655,       526,       423,
/*   5 */       335,       272,       215,       172,       137,
/*  10 */       110,        87,        70,        56,        45,
/*  15 */        36,        29,        23,        18,        15,
};

在linux中CPU nice值每下降1,则获得多10%的cpu时间,而这10%有一个相对的概念.就像上文所说的,如果用绝对的方式来说那么就会出现两倍的差距;
这里一张表表明了40个优先级的权重表示.比如有A,B两个进程nice都为0,那么每个的cpu占用时间都为1024/(1024+1024)=50%(这里1024代表上面0对应的权值),但是B要少出10的cpu时间的话,则将B的nice值加1,则应该有1024/(1024+B的权值) = 45%;算出来B的权值为837,与820相差不多,所以这里是按照相对值来计算获得的cpu时间的.
以上参考博文 https://blog.csdn.net/u010173306/article/details/46743491

进程选择

主要选择具有最小vruntime的任务;通过使用红黑树来保存这些进程

调度器入口

进程调度的时候首先是以调度器的优先级为顺序从高到低一次检查每个调度类,并且从最高优先级的调度类中选择最高优先级的进程.这样就找到最高优先级的进程,也就是vruntime最小的进程.

睡眠和唤醒

内核操作: 首先标记自己为休眠状态,从可执行红黑树中移除,放入等待队列.在选择一个可执行进程.唤醒相反.
等待队列: 维护一个等待队列,当要休眠的时候放入到等待队列.编码是一个while(true)循环中等待,在被唤醒后在此检查条件是否为真,为真就会退出循环,将自己移除出等待队列,加入可执行红黑树中.
唤醒:唤醒操作通过函数wake_up()进行,唤醒指定的等待队列上的所有进程.

抢占和上下文切换

内核中有一个参数为need_resched参数,表明是否需要重新执行一次调度,此过程称为抢占.

  • 用户抢占:　在系统调用返回用户控件或从中断处理程序返回用户空间是会发生用户抢占，当然need_resched参数要设置
  • 内核抢占: 除了need_resched参数还有一个preempt_count参数,表明是否持有锁,在preempt_count为0的时候说明在执行任务持有锁,此次抢占是不安全的.直到当前新进程持有的所有锁都释放了,才会重新执行调度.

系统调用

系统调用在用户空间进程和硬件设备之间添加了一个中间层,作用有三个:

  1. 首先为用户空间提供了一种硬件的抽象接口.这样应用程序不管磁盘类型和介质,不管文件系统是那种类型
  2. 第二 系统调用保证了系统的稳定和安全.作为硬件设备和应用程序之间的中间人可以基于权限,用户类型和其他规则对需要进行的访问进行裁决,避免引用程序不正当的使用硬件设备.
  3. 每个进程都运行在虚拟系统中,而在用户控件和系统的其余部分提供这样一层公共接口.在linux中系统调用是用户空间进入内核的唯一手段,除了异常和陷入外,他们是内核唯一的合法入口.

在linux中,每个系统调用被赋予一个系统调用号. 这样就可以根据一个独一无二的号关联系统调用.进程不会提及系统调用的名称.如果一个系统调用删除,他所占用的系统调用号不允许被回收,否则以前编译过的代码调用此系统调用,但是事实上却调用另一个系统调用容易引发错误.如果一个系统调用被删除会用sys_ni_syscall()替换,此函数返回-ENOSYS.内核记录了系统调用表中的所有已注册过的系统调用的列表.存储在sys_call_table中.

指定系统调用

所有的系统调用陷入内核方式都一样,所以必须把系统调用号一并创给内核.在x86上,系统调用号通过eax寄存器传递给内核.在陷入内核前,用户空间就把响应系统调用锁对应的号放入eax中.

参数传递

调用系统调用有时需要一些参数,最简单的办法是把参数也存放在寄存器里.在ebx ecx edx esi edi按照顺序存放前5个参数.应用用一个单独的寄存器存放指向所有这些参数在用户空间地址的指针.给用户空间的返回值也通过寄存器传递.

调用参数限制

在进行系统调用之前会先检查他们所有的参数是否合法有效.在接受用户空间的指针前,内核必须保证:

  • 指针指向的内存区域属于用户空间.进程决不能哄骗内核去读内核空间的数据.
  • 指针指向的内核区域在进程的地址空间里.进程绝不能哄骗内核去读取其他进程的数据.
  • 如果是读,该内存可以被读;如果是写操作,该内存应该可写;如果是可执行,必须被标记为可执行.进程局不能绕过内存访问限制.
    如果调用成功返回0,否则返回标准-EFAULT

    绑定系统调用

    在编写完一个系统调用后，要把它注册程一个正式的系统调用
  1. 首先在系统调用表的最后加入一个表项,从0开始算起
  2. 系统调用必须被编译进内核映像(不能被编译成模块)