CPU调度

Wesley13
• 阅读 564

1.CPU调度程序

   每当CPU空闲时,OS必须从就绪队列选择一个进程来执行。进程选择由短期调度程序或CPU调度程序执行。调度程序从内存中选择一个能执行的进程,并为之分配CPU。

2.抢占:可以选择

             (1)当一个进程从运行状态切换到就绪状态;(eg:当出现中断时)

             (2)当一个进程从等待状态切换到就绪状态;(eg:I/O完成)

   非抢占/协作:没有选择,只有调度,一个新进程(如果就绪队列中已有一个进程存在)必须被选择执行。

(1)当一个进程从运行状态切换到等待状态(eg:I/O请求,或调用wait等待一个子进程的终止);

(2)当一个进程终止;

3.分派程序:是一个模块,用来将CPU的控制交给由短期调度程序选择的进程。

   功能:切换上下文;  切换到用户模式;   跳转到用户程序的合适位置,以重新启动程序;

   分派延迟:分派程序停止一个进程而启动另外一个所花时间。

4.调度准则

   (1)CPU使用率;

   (2)吞吐量:一个时间单元内所完成进程的数量;

   (3)周转时间:从进程提交到进程完成的时间段。为所有时间段之和,including 等待进入内存,在就绪队列中等待,在CPU上执行和I/O执行。

   (4)等待时间:在就绪队列中等待所花费时间。CPU调度算法只影响进程在就绪队列中等待所花的时间。

   (5)响应时间:从提交请求到产生第一响应的时间。

5.先到先服务(FCFS)调度(非抢占)

   先请求CPU的进程先分配给CPU。用FIFO队列实现。

CPU调度

补充:对于第一个Gantt图:周转时间:(24+27+30)/3 = 27                 响应时间:(0+24+27)/3 = 17

6.最短作业优先调度(SJF)(非抢占)

   最短下一个CPU区间的算法,当CPU空闲时,它会赋给具有最短CPU区间的进程。如果两个进程具有同样长度,则使用FCFS。

CPU调度

7.最短剩余时间优先调度(抢占式的SJF调度)

   当一个新进程到达就绪队列而以前的进程还在执行时,需要选择。与当前运行的进程相比,新进程可能会有一个更短的CPU区间。抢占SJF算法可抢占当前运行的进程。

CPU调度

Ps:响应时间:(0+0+15+2)/4=17           周转时间:(17+4+24+7)/4 = 13

8.优先级调度:(既可以抢占,也可以非抢占,实际应用中为抢占)

   每一个进程都有一个优先级与其关联,具有最高优先级的进程会分配到CPU,具有相同优先级的进程按照FCFS。

  for windows: 数字越大,优先级越高               for Linux:与windows相反

CPU调度

问题:无穷阻塞/饥饿:使某个低优先级进程无穷等待CPU

            解决方法: 老化:逐渐增加在系统中等待很长时间的进程的优先级。

9.轮转法调度(增加了抢占以切换进程)(RR)

   定义一个较小时间单元,称为时间片。通常为10-100ms

CPU调度

若时间片很小,则RR算法称为处理器共享。   根据经验,80%的CPU区间应小于时间片。

10.多级队列调度:

    适用于进程可容易的分为不同组的情况,例如一个常用的划分方法是前台(交互)和后台(批处理)进程。

    将就绪队列分成多个独立队列(见图)。根据进程属性,如内存大小,优先级,类型,一个进程被永久的分配到一个队列。每个队列有自己的调度算法。例如前台队列使用RR,后台使用FCFS。

CPU调度

另外,队列之间必须有调度,通常采用固定优先级抢占调度。即每个队列与更底层队列相比有绝对的优先级。另一种可能是在队列之间划分时间片。

11.多级反馈队列调度:

    允许进程在队列之间移动,主要思想为根据不同CPU区间的特点以区分进程。如果进程使用更多CPU时间,则它会被转移到更低优先级队列。

CPU调度

注:进入就绪队列的进程被放入队列0里面,其中每个进程都有8ms的时间片,若进程不能在这一时间内完成,则被移动到队列1的尾部。

       如果队列0为空,队列1的头部进程会得到一个16ms的时间片。如果它不能完成,那么将被抢占,并被放到队列2中。只有当队列0和

       队列1为空时,队列2内的进程才可根据FCFS运行。

12.多处理器调度:

    12.1 多处理器调度的方法

     (1)非对称处理:只有一个处理器(主服务器)访问系统数据结构,处理所有的调度决定,I/O处理以及其他系统活动,其他处理器只执行用户代码。

     (2)对称多处理(SMP):每个处理器自我调度。所有进程可能处于一个共同的就绪队列中,或每个处理器都有自己的私有就绪进程队列。

   12.2 处理器亲和性:绝大多数SMP系统试图避免将进程从一个处理器移动至另一个处理器,而是努力使一个进程在同一个处理器上运行。

          软亲和性:OS设法将一个进程保持在同一个处理器,但不能做任何保证。

          硬亲和性:允许进程指定它不允许移动至其他处理器。

   12.3 负载均衡

        设法将工作负载平均地分配到SMP系统中的所有处理器上。通常只是对拥有自己私有的可执行进程的处理器而言是必要的。在具有共同队列的系统中,通常不需要负载均衡(一旦处理器空闲,它立刻从共同队列中取走一个可执行进程)。在绝大多数SMP当代OS中,每个处理器都具有一个可执行进程的私有队列。

       两种方法:push migration:一个特定任务周期性检查每个处理器上的负载,若发现不平衡,即通过将进程从超载处理器移动到(or推送)空闲或不太忙的处理器。

                        pull(拉) migration:当空闲处理器从一个忙的处理器上推送(pull)一个等待任务。

   12.4 对称多线程(SMT)/超线程技术

      在同一个物理处理器上生成多个逻辑处理器,向操作系统呈现一个多逻辑处理器的视图。每个逻辑处理器都有自己的架构状态。SMT是硬件提供的。

13.线程调度

    13.1竞争范围

     进程竞争范围(PCS):线程库调度用户级线程到一个有效的LWP上运行。

     系统竞争范围(SCS):内核决定调度哪个内核线程到CPU上。

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
半臻 半臻
2年前
Python基础10——线程、进程、协程
18线程18.1进程和线程进程:打开一个程序至少就会有一个进程。操作系统进行资源分配的基本单位线程:线程是CPU调度的基本单位,每个进程至少都有一个线程。单线程:只有一个线程pythondeffuna():print(123)deffunb():print(456)funa()funb()先执行funa再执行funb多线程线程
BichonCode BichonCode
3年前
操作系统
一、进程的相关概念1.1定义进程用来描述一个程序及其执行过程中的信息,即描述一个执行中的程序,所以才将其命名为进程,即进行中的程序,也可以说进程是程序的一次执行。1.2进程的状态操作系统中的进程状态主要包括∶运行态——当前占有CPU、正在执行的进程状态;就绪态——一个进程具备了所有可以执行的条件,只要获得CPU就能开始执
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Wesley13 Wesley13
2年前
java多线程小结,及解决应用挂死的问题
这两天为了定位JBOSS老是挂死的问题,学习了一下JAVA多线程方面的知识,在此总结一下1、在Java程序中,JVM负责线程的调度。线程调度是指按照特定的机制为多个线程分配CPU的使用权。调度的模式有两种:分时调度和抢占式调度。分时调度是所有线程轮流获得CPU使用权,并平均分配每个线程占用CPU的时间;抢占式调度是根据线程的优先级别来获
限时发布!非科班程序员金三银四求职经历
进程和线程的概念进程是具有独立功能的程序在一个数据集合上运行的过程。进程是系统进行资源分配的单位,实现的操作系统的并发。线程是比进程更小的能独立运行的单位,是  调度的基本单位,实现了进程内部的并发。线程成为了程序执行流的最小单位。进程状态转换图1.创建状态:进程正在被创建。2.就绪状态:进程已经分配到了除  之外的所有资源,只要分配到  就可以开
Wesley13 Wesley13
2年前
UNIX基础概念
UNIX基本概念进程从用户观点来看:进程是程序的一个执行实例。从UNIX系统内部来看,是为运行程序提供执行环境的实体,是系统进行资源分配和调度运行的一个单位。进程有三个特点:1)进程有一个控制点和自己的独立地址空间。进程的控制点通过程序计数器跟踪着程序的指令序列。进程的地址空间由进程可以引用或访问的存
Stella981 Stella981
2年前
Python进程、线程、协程的对比
1\.执行过程每个线程有一个程序运行的入口、顺序执行序列和程序的出口。但是线程不能够独立执行,必须依存在进程中,由进程提供多个线程执行控制。每个线程都有他自己的一组CPU寄存器,称为线程的上下文,该上下文反映了线程上次运行该线程的CPU寄存器的状态。协程,又称微线程,Coroutine。执行过程中,在子程序内部可中断,然后转而
Wesley13 Wesley13
2年前
Java中多线程并发体系知识点汇总
一、多线程1、操作系统有两个容易混淆的概念,进程和线程。进程:一个计算机程序的运行实例,包含了需要执行的指令;有自己的独立地址空间,包含程序内容和数据;不同进程的地址空间是互相隔离的;进程拥有各种资源和状态信息,包括打开的文件、子进程和信号处理。线程:表示程序的执行流程,是CPU调度执行的基本单位;线程有自己的程序计数器、寄存器、堆栈和帧。同一进
Wesley13 Wesley13
2年前
Java 基础夺命连环16问(面试硬核敲门砖 )
说说进程和线程的区别?进程是程序的一次执行,是系统进行资源分配和调度的独立单位,他的作用是是程序能够并发执行提高资源利用率和吞吐率。由于进程是资源分配和调度的基本单位,因为进程的创建、销毁、切换产生大量的时间和空间的开销,进程的数量不能太多,而线程是比进程更小的能独立运行的基本单位,他是进程的一个实体,可以减少程序并发执行时的时间和空间开销,