文档章节

进程调度

China_OS
 China_OS
发布于 2012/12/03 21:19
字数 3296
阅读 254
收藏 2

     调度程序决定将那个程序投入运行,何时运行以及运行多长时间。只有通过调度程序的合理调度,系统资源才能最大限度的发挥作用。调度程序没有复杂的原理,最大限度的利用处理器时间的原则是,只要有可以执行的进程,那么就总会有进程在执行。但是系统中可运行的进程数目比处理器个数多,就注定某个时刻会有一些进程不能运行。

多任务
     多任务操作系统就是能同时并发的交互执行多个进程的操作系统,多任务系统可以分为两类:非抢占式多任务和抢占式多任务。在非抢占式多任务下,除非进程自己主动停止,否则它会一直执行。进程主动挂起自己的操作成为让步。但这有很大的缺点:调度程序无法对每个进程执行多长时间做出统一规定。所以近代绝大部分操作系统都采用抢占式多任务。抢占式多任务,在此模式下,由调度程序来决定什么时候停止一个进程的执行,以便其他进程能够得到执行就会,这个强制的挂起动作就叫抢占。进程在被抢占之前能够运行的时间是预先设置好的,而且有一个专门的名字叫时间片。当今众多现代操作系统都采用了动态时间片计算方式,并且引入了可配置的计算策略。

策略
     策略决定调度程序在什么时候让程序运行。进程可以被分为IO消耗型和处理器消耗型。前者指进程的大部分时间用来提交IO请求或者等待IO请求,这样的进程经常处于可运行态,但是每次都是运行较短的时间。处理器消耗型进程则把时间大多用在执行代码上。对于处理器消耗型的进程,调度策略往往是尽量降低他们的调度频率,而延长其运行时间。调度策略通常是在两个矛盾中间寻求平衡:进程响应迅速和最大系统利用率。

     调度算法中最基本的一类就是基于优先级的调度,这是一种根据进程的价值和其对处理器的时间需求来对进程分级的想法。优先级高的先运行,优先级低的后运行,相同优先级的按照轮转方式调度。linux采用两种不同的优先级范围:nice值和实时优先级。nice值的范围是-20~19,默认值是0,nice值越大优先级越低,nice值越小优先级越高。在linux中nice值代表的是时间片的比例。实时优先级,其值是可配置的,范围从0~99,与nice值相反越高的实时优先级数值意味着进程优先级越高。任何实时进程的优先级都高于普通进程,也就是说nice优先级和实时优先级处于互不相交的两个范畴。

     时间片是一个数值,它表明进程在被抢占前所能持续运行的时间,调度策略必须规定一个默认的时间片。但是时间片过长,系统交互表现不好,时间片过短会明显增大进程切换带来的资源消耗。但是linux的CFS调度器并没有直接分配时间片到进程,它是将处理器的使用比划分给了进程。这样进程所获得的处理器时间是和系统负载密切相关的,这个比例会受到nice值的影响,nice值作为权重将调整进程所使用的粗利器时间使用比。由于linux系统使抢占式的,在使用CFS调度器时,其抢占时间取决于新的可运行程序消耗了多少处理器使用比,如果消耗的使用比比当前进程小,则新进程立刻投入运行,抢占当前进程。

linux调度算法
     linux调度器是以模块的方式提供的,这样的目的是允许不同类型的进程可以有针对性的选择调度算法,这种模块化结构成为调度器类,它允许多种不同的可动态添加的调度算法并存,调度属于自己范畴的进程。完全公平调度(CFS)是一个针对普通进程的调度类,在linux中成为SCHED_NORMAL。

     CFS的出发点基于一个简单的理念:进程调度的效果应如同系统具备一个理想中的完美多任务处理器。CFS允许每个进程允许一段时间、循环轮转、选择运行最少的进程作为下一个运行的进程,而不再采用分配给每个进程时间片的做法了,CFS在所有可运行进程总数基础上计算出一个进程应该运行多久,而不是依靠nice值来计算时间片。你应该注意到,当可运行的任务数量趋于无限时,他们各自获得的处理器使用比和时间片都将趋于0,这样造成了不可接受的切换消耗,CFS为此引入每个进程获得的时间片底线,这个底线称为最小粒度,默认情况下这个值是1ms。任何进程所获得的处理器时间是由它自己和其他所有进程的nice值的相对差值决定的。nice值对时间片的作用不再是算数加权,而是几何加权,任何nice值对应的绝对时间不在是一个绝对值,而是处理器的使用比。

linux调度实现
     CFS的实现主要有四个组成部分:时间记账、进程选择、调度器入口、睡眠和唤醒。

     所有的调度器都必须对进程的运行时间进行记账,当一个进程的时间片减少到0时,它就会被另一个尚未减少到0的时间片进程抢占,CFS虽然不再有时间片概念,但是它也必须维护每个进程运行的时间记账,因为它要确保每个进程只在公平分配给它的处理器时间内执行。CFS使用调度器实体结构来追踪进程记账实体结构作为一个名为se的成员变量,嵌入在进程描述符struct task_struct内。varuntime变量存放进程的虚拟运行时间,该运行时间的计算是经过了所有可运行进程总数的标准化。虚拟时间是以ns为单位的,所以vruntime和定时器节拍不再相关。CFS使用vruntime变量来记录一个程序到底运行了多长时间以及它还应该运行多久。update_curr()函数实现了记账功能,它是由系统定时器周期性调用的,无论进程是在可运行状态,还是处于堵塞状态。

     CFS试图用一个简单的规则去均衡进程的虚拟运行时间:当CFS需要选择下一个需要运行的进程时,它会选择一个具有最小vruntime的进程,这其实就是CFS调度算法的核心:选择具有最小vruntime的任务。CFS使用红黑树来组织可运行的进程队列,并利用其迅速找到最小vruntime值的进程。

     进程调度的主要入口点是函数schedule(),它正是内核其他部分用于调度进程调度器的入口。schedule()通常需要和一个具体的调度类相关联,也就是说,它会找到一个最高优先级的调度类--后者需要有自己的可运行队列,然后问后者谁才是下一个该运行的进程。这个函数中唯一重要的事情是它会调用pick_next_task(),pick_next_task会以优先级为次序,从高到低依次检查每一个调度类,并且从最高优先级的调度类中选择最高优先级进程。

     休眠的进程处于一个特殊的不可执行的状态。如果没有这个特殊的状态,调度器就有可能选出一个本不愿意被执行的进程。进程休眠的原因有多种,但肯定都是为了等待一些事情,最常见的就是文件IO。休眠通过等待队列进行处理,等待队列是由等待某些事件发生的进程组成的简单列表。内核用wake_queue_head_t来代表等待队列,进程把自己放入等待队列,并设置成不可执行状态,当与等待队列相关的事件发生时,队列上的进程就会被唤醒。唤醒操作通过函数wake_up()进行,它会唤醒指定队列上的所有进程。它调用函数try_to_wake_up(),该函数为进程设置为TASK_RUNNING状态,调用enqueue_task()将此进程放入红黑树中,如果被唤醒的进程的优先级比当前运行的进程的优先级高,还要设置need_resched标志。

抢占和切换上下文
     上下文切换就是从一个可执行进程切换到另一个可执行进程,由contex_switch()函数负责处理,每当一个新进程被选择出来运行时,schedule()就会调用该函数。内核知道在什么时候调用schedule()。内核提供了一个need_resched标志来表明是否需要重新执行一次调度,当某个进程被抢占时,scheduler_tick()就会设置这个标志,当一个优先级高的进程进入可执行状态的时候,try_to_wake_up()也会设置这个标志,内核会检查该标志,如果被设置了,则调用schedule()来切换到一个新进程。在返回用户空间以及从中断返回的时候,也会检查need_resched标志,如果被设置,内核会继续执行之前的调度程序。

     内核即将返回用户空间的时候,如果need_resched被设置,会导致schedule()被调用,此时就会发生用户抢占,内核无论是在中断处理程序还是在系统调用后返回,都会检查need_resched标志。在2.6内核版本中,引入了内核抢占,只要重新调度是安全的,内核就可以在任何时间抢占正在执行的任务。什么时候是安全的呢?只要没有持有锁,内核就可以进行抢占,锁是非抢占区域的标志。为了支持内核抢占所做的第一处变动,就是为每个进程的thread_info引入preempt_count计数器,计数器初始值为0,每当使用锁的时候计数器值加1,释放锁的时候计数器值减1,当计数器数值为0时,内核就可以执行抢占。当从中断返回内核空间的时候,内核会检查need_resched和preempt_count的值,如果被设置,则会发生内核抢占。如果内核中的进程被阻塞了,或者显示的调用了schedule(),内核抢占也会显示的发生。

实时调度策略
     linux提供了两种实时调度策略:SCHED_FIFO和SCHED_RR,普通的非实时调度策略是SCHED_NORMAL。SCHED_FIFO实现了一种简单的先入先出的调度算法,它不使用时间片,处于可运行状态的SCHED_FIFO级进程会比任何SCHED_NORMAL级的进程都先得到调度,SCHED_FIFO级进行可以一直执行下去,直到它自己阻塞或者显示的释放处理器,它不基于时间片,可以一直执行,只有更高优先级的SCHED_FIFO或者SCHED_RR任务才能抢占SCHED_FIFO任务。如果SCHED_FIFO优先级相同,则它们会轮流执行。SCHED_RR与SCHED_FIFO大体相同,只是SCHED_RR级的进程在消耗完自己的时间片后就不在继续执行了,当时间片用完后,同一优先级的其他进程被轮流调度,时间片只用来重新调度同一优先级的进程。对于SCHED_FIFO进程,高优先级总是立即抢占低优先级,但低优先级进程决不能抢占SCHED_RR任务,即使它的时间片耗尽。

     实时优先级的范围从0到MAX_RT_PRIO(100)-1,也就是0~99.SCHED_NORMAL级进程的nice值共享了这个取值空间,它的取值范围是MAX_RT_PRIO~MAX_RT_PRIO+40,也就是100~139。

与调度相关的系统调用
     linux提供了一个系统调用表,用于管理与调度程序相关的参数。这些系统调用可以用来操作和处理进程优先级、调度策略以及处理器绑定。




© 著作权归作者所有

共有 人打赏支持
China_OS
粉丝 406
博文 440
码字总数 493809
作品 0
徐汇
技术主管
基于CFS算法的schedule()源码分析

内核中的调度算法在不断变化,2.4内核中的调度器是在所有的进程中选择优先级最高的进程,2.6内核前期的调度器是基于O(1)算法的,而 2.6.23版本之后的内核采用CFS调度算法,并同时对调度器进行...

慎思
2012/08/15
0
0
常见的几种操作系统进程调度算法

什么是进程调度算法??? 进程调度算法:根据系统的资源分配策略所规定的资源分配算法。 一、先来先服务和短作业(进程)优先调度算法 1.先来先服务调度算法 先来先服务(FCFS)调度算法是一种...

科技小能手
2017/11/12
0
0
调度器简介,以及Linux的调度策略

进程是操作系统虚拟出来的概念,用来组织计算机中的任务。但随着进程被赋予越来越多的任务,进程好像有了真实的生命,它从诞生就随着CPU时间执行,直到最终消失。不过,进程的生命都得到了操...

Vamei
07/25
0
0
操作系统调度器的种类

我们的公共号 乌龟运维 官网 wuguiyunwei.com 调度在计算机中是分配工作所需资源的方法。资源可以指虚拟的计算资源,如线程、进程或数据流;也可以指硬件资源,如处理器、网络连接或扩展卡。...

乌龟运维
2017/06/09
0
0
操作系之进程调度及算法详解

引言 在多进程环境下,虽然从概念上看,有多个进程在同时执行,但在单个cpu下,实际上任何时刻只能有一个进程处于执行状态。而其它进程处于非执行状态。那么就有一个需要解决的问题:我们是如...

无寄语
2016/10/24
9
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JS:异步 - 面试惨案

为什么会写这篇文章,很明显不符合我的性格的东西,原因是前段时间参与了一个面试,对于很多程序员来说,面试时候多么的鸦雀无声,事后心里就有多么的千军万马。去掉最开始毕业干了一年的Jav...

xmqywx
今天
0
0
Win10 64位系统,PHP 扩展 curl插件

执行:1. 拷贝php安装目录下,libeay32.dll、ssleay32.dll 、 libssh2.dll 到 C:\windows\system32 目录。2. 拷贝php/ext目录下, php_curl.dll 到 C:\windows\system32 目录; 3. p...

放飞E梦想O
今天
0
0
谈谈神秘的ES6——(五)解构赋值【对象篇】

上一节课我们了解了有关数组的解构赋值相关内容,这节课,我们接着,来讲讲对象的解构赋值。 解构不仅可以用于数组,还可以用于对象。 let { foo, bar } = { foo: "aaa", bar: "bbb" };fo...

JandenMa
今天
1
0
OSChina 周一乱弹 —— 有人要给本汪介绍妹子啦

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @莱布妮子 :分享水木年华的单曲《中学时代》@小小编辑 手机党少年们想听歌,请使劲儿戳(这里) @须臾时光:夏天还在做最后的挣扎,但是晚上...

小小编辑
今天
21
5
centos7安装redis及开机启动

配置编译环境: sudo yum install gcc-c++ 下载源码: wget http://download.redis.io/releases/redis-3.2.8.tar.gz 解压源码: tar -zxvf redis-3.2.8.tar.gz 进入到解压目录: cd redis-3......

hotsmile
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部