文档章节

进程调度

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

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

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

策略
     策略决定调度程序在什么时候让程序运行。进程可以被分为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
粉丝 400
博文 383
码字总数 483581
作品 0
徐汇
技术主管
基于CFS算法的schedule()源码分析

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

慎思 ⋅ 2012/08/15 ⋅ 0

常见的几种操作系统进程调度算法

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

科技小能手 ⋅ 2017/11/12 ⋅ 0

处理机调度

处理机调度 调度的实质是资源的分配 • 调度算法: 指根据系统的资源分配策略所规定的资源分配算法。 • 包括: –先来先服务调度算法 –短作业(进程)优先调度算法 –高优先权优先调度算法 ...

王大豆 ⋅ 2015/07/21 ⋅ 0

操作系之进程调度及算法详解

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

无寄语 ⋅ 2016/10/24 ⋅ 0

操作系统调度器的种类

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

乌龟运维 ⋅ 2017/06/09 ⋅ 0

Erlang并发机制 –进程调度

Erlang调度器主要完成对Erlang进程的调度,它是Erlang实现软件实时和进程之间公平使用CPU的关键。Erlang运行时,有4种任务需要被调度:进程,Port,Linked-in driver,Erlang虚拟机的系统级活...

梁杰_Jack ⋅ 2014/04/02 ⋅ 0

郭健: Linux进程调度技术的前世今生之“今生”

本文紧接着: 郭健: Linux进程调度技术的前世今生之“前世” 作者简介 郭健,一名普通的内核工程师,以钻研Linux内核代码为乐,热衷于技术分享,和朋友一起创建了蜗窝科技的网站,希望能汇集...

jus3ve ⋅ 2017/12/01 ⋅ 0

进程调度与切换简单总结

一、Linux时钟系统 1.时钟硬件 绝大多数的PC都有两个时钟源,RTC(实时时钟)和OS(系统时钟)。RTC也叫做CMOS时钟,它是PC主机板上的一块芯片。OS时钟产生于PC主板上的定时/计数芯片,由操作...

8yi少女的夢 ⋅ 2017/10/11 ⋅ 0

关于linux的cfs调度器的宏观理解

今天重读了cfs调度器,使我忍不住再写一篇关于cfs的文章,cfs调度器的运行时间是0(logN),而以前的调度器的运行时间是O(1),这是不是就是说cfs的效率比O(1)的更差呢?并不是那样,我们知道c...

晨曦之光 ⋅ 2012/04/10 ⋅ 0

浅谈Linux进程调度过程

在操作系统运行过程中,由于CPU bound和I/O bound,进行进程的调度自然是常事。进行进程调度时,操作系统使用某些特定算法(如FIFO、SCBF、轮转法等)在进程队列中选出一个进程作为下一个运行...

不高不富不帅的陈政_ ⋅ 2016/04/14 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

说说javascript中的那些专业名词

DOM(Document Object Model) 文档对象模型 BOM(Browser Object Model) 浏览器对象模型 ECMA(European Computer Manufacturer's Association) 欧洲计算机制造商协会 W3C(World Wide Web Conso......

hang1989 ⋅ 21分钟前 ⋅ 0

Bootstrap Wizard 多步表单控件

废话 有一块需求是 有多步表单 点击下一步时触发验证一个范围内的表单,点击上一步或取消,清空表单并返回第一步,点击最后一步提交整个表单的 就找到了这个插件,本来自己写了一个原生的 fo...

无极之岚 ⋅ 37分钟前 ⋅ 0

如何利用Spring Cloud构建起自我修复型分布式系统

利用Netflix所打造的组件及各类大家熟知的工具,我们完全可以顺利应对由微服务以及分布式计算所带来的技术挑战。 在过去一年当中,微服务已经成为软件架构领域一个炙手可热的新名词,而且我们...

harries ⋅ 今天 ⋅ 0

临近实习前的感想

再过两星期就要开始新的一段实习了,想想去年的这个时候也在实习,心中不免思绪万千,也一直想写对2017做个总结,但一直迟迟没有下笔。 2017年的春节,我就开始准备开学后找份实习。那时候就...

无精疯 ⋅ 今天 ⋅ 0

Spring AOP(面向切面编程)

Spring AOP概念: Spring AOP 可以劫持一个执行的方法,在方法执行之前或之后添加额外的功能。通常情况下,AOP把项目中需要在多处用到的功能,比如日志、安全和事物等集中到一个类中处理,而...

霍淇滨 ⋅ 今天 ⋅ 0

人工智能、机器学习、数据挖掘以及数据分析有什么联系?

人工智能是目前炙手可热的一个领域,所有的互联网公司以及各路大迦们纷纷表态人工智能将是下一个时代的革命性技术,可与互联网、移动互联网时代的变更相媲美;AlphaGo在围棋领域战胜人类最顶...

董黎明 ⋅ 今天 ⋅ 0

使用 vue-cli 搭建项目

vue-cli 是一个官方发布 vue.js 项目脚手架,使用 vue-cli 可以快速创建 vue 项目,GitHub地址是:https://github.com/vuejs/vue-cli 一、 安装 node.js 首先需要安装node环境,可以直接到中...

初学者的优化 ⋅ 今天 ⋅ 0

设计模式 之 享元模式

设计模式 之 享元模式 定义 使用共享技术来有效地支持大量细粒度对象的复用 关键点:防止类多次创建,造成内存溢出; 使用享元模式来将内部状态与外部状态进行分离,在循环创建对象的环境下,...

GMarshal ⋅ 今天 ⋅ 0

SpringBoot集成Druid的最简单的小示例

参考网页 https://blog.csdn.net/king_is_everyone/article/details/53098350 建立maven工程 Pom文件 <?xml version="1.0" encoding="UTF-8"?> <project xmlns="http://maven.apache.org/POM......

karma123 ⋅ 今天 ⋅ 0

Java虚拟机基本结构的简单记忆

Java堆:一般是放置实例化的对象的地方,堆分新生代和老年代空间,不断未被回收的对象越老,被放入老年代空间。分配最大堆空间:-Xmx 分配初始堆空间:-Xms,分配新生代空间:-Xmn,新生代的大小一...

算法之名 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部