首页 > 其他分享 >半期复习——第三章:处理机调度(3.1~3.4)

半期复习——第三章:处理机调度(3.1~3.4)

时间:2023-04-16 21:23:47浏览次数:35  
标签:算法 半期 处理机 队列 作业 调度 3.4 3.1 进程

3.1 处理机调度的层次和调度算法的目标 

一、处理机调度的层次(3)

    1.高级调度 (作业调度、长程调度)

        ①用于决定把外存上处于后备队列中的哪些作业调入内存,并为它们创建进程、分配必要的资源,然后,再将新创建的进程排在就绪队列上,准备执行 。主要用于多道批处理系统。

        ②考虑两个问题:选择多少个作业进入内存,为之创建进程? 取决于多道程序的度; 选择哪些作业? 取决于高级调度算法 。

    2.低级调度 (进程调度、短程调度)

        ①决定就绪队列中的哪个进程应获得处理机,然后再由分派程序把处理机分配给该进程的具体操作。运行频率最高。

        ②功能:保存处理机的现场信息;按某种算法选取进程; 把处理器分配给进程。

        ③非抢占/抢占方式

        非抢占方式:一旦把处理机分配给某进程后,便让该进程一直执行,直至该进程完成或发生某事件而被阻塞时,才再把处理机分配给其他进程。

         抢占方式:允许调度程序根据某种原则(优先权原则,短作业优先原则,时间片原则),去暂停某个正在执行的进程,将已分配给该进程的处理机重新分配给另一进程。

    3.中级调度(中程调度)

        ①当内存空间非常紧张时,选择一个进程(阻塞或就绪状态)换出到外存,释放出内存空间给别的进程使用;当内存空间较充裕时,从外存选择一个挂起状态的进程调度到内存。

         ②提高内存利用率和系统吞吐量。实际上是存储器管理的对换功能。

        ③只有支持进程挂起的操作系统才具有中程调度功能。

二、处理机调度算法的目标及准则

    1.面向用户的准则(4)

        ①周转时间短  

        周转时间:从作业被提交给系统开始,到作业完成为止的这段时间间隔

        平均周转时间:

         平均带权周转时间:

(Ti:周转时间 Tsi:服务时间)

        ②响应时间快 :从用户通过键盘提交一个请求开始,直至系统首次产生响应为止的时间

        ③截止时间的保证:指某任务必须开始执行的最迟时间,或必须完成的最迟时间

        ④优先权准则 :基于优先权让某些紧急的作业能得到及时处理

    2.面向系统的准则(3)

        ①系统吞吐量高。吞吐量是指在单位时间内,系统所完成的作业数。

        ②处理机利用率好

        ③各类资源的平衡利用

 

3.2 作业和作业调度

一、批处理系统中的作业

    1.作业:包含程序,数据,作业说明书。在多道批处理系统中,作业是用户提交给系统的一项相对独立的工作。

    2.作业控制块JCB

    3.作业运行的三个阶段和三种状态

        ①收容阶段—后备状态

        ②运行阶段 – 运行状态

        ③完成阶段 – 完成状态

二、作业调度的主要任务

    根据JCB信息,检查系统中的资源能否满足作业对资源的需求,按照一定的调度算法,从外存的后备队列中选取某些作业调入内存,并为他们创建进程、分配必要资源,安排在就绪队列。

三、FCFS算法:有利于长作业(进程),而不利于短作业(进程)

四、SJF算法:对长作业不利;完全未考虑作业的紧迫程度;估计不准运行时间

五、优先级调度算法 :把具有最高优先级的作业调入内存之中。

六、高响应比优先调度算法

    动态优先级:

 

3.3 进程调度

一、进程调度的任务:保存处理机现场,按照某种算法选取进程 ,把处理机分配给进程 

二、进程调度的方式 (最高优先权优先(FPF)调度下细分)

    1.非抢占方式

    在这种方式下,系统一旦把处理机分配给就绪队列中优先权最高的进程后,该进程便一直执行下去,直至完成;或因发生某事件使该进程放弃处理机时,系统方可再将处理机重新分配给另一优先权最高的进程。 

    2.抢占方式

    在这种方式下,系统同样是把处理机分配给优先权最高的进程,使之执行。但在其执行期间,只要又出现了另一个其优先权更高的进程,进程调度程序就立即停止当前进程的执行,重新将处理机分配给新到的优先权最高的进程。

    “抢占”的原则: ①优先权原则;②短进程优先原则;③时间片原则

三、基于时间片的轮转调度算法

    常用于分时系统及事务处理系统

四、优先级调度算法(抢占式/非抢占式)

五、多队列调度算法 具有较好的性能,能较好地满足各种类型用户的需要

    1.置多个就绪队列,并为各个队列赋予不同的优先级。 第一个最高,以后依次降低

    2.当一个新进程进入内存后,首先将它放入第一队列的末尾,按FCFS原则排队等待调度。

    3.如果它在一个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾,再同样地按FCFS原则等待调度执行。如果它在第二队列中运行一个时间片后仍未完成,再依次将它放入第三队列,……。 

    4.仅当第1~i-1队列空闲时,调度程序才调度第i队列中的进程运行。

    5.如果正在处理第i队列,又有新进程进入较高优先级的队列,则立即把正在处理的进程放回第i队末尾,将处理及分配给高优先级的进程。

 

3.4 实时调度

一、实现实时调度的基本条件 

    1.提供必要的信息 :就绪时间,开始和完成截止时间,处理时间,资源要求,优先级

    2.系统处理能力强 

    3.采用抢占式调度机制 :硬实时任务

    4.具有快速切换机制

二、实时调度算法分类

     1.非抢占式轮转调度算法:

    调度程序每次选择队列中的第一个任务投入运行。当该任务完成后,便把它挂在轮转队列的末尾,等待下次调度运行。

    2.非抢占式优先调度算法:  

    如果在系统中存在着实时要求较为严格的任务,则可采用非抢占式优先调度算法,为这些任务赋予较高的优先级。当这些实时任务到达时,把它们安排在就绪队列的队首,等待当前任务自我终止或运行完成后,才能被调度执行。  

    3.基于时钟中断的抢占式优先权调度算法:

    某实时任务到达后,如果该任务的优先级高于当前任务的优先级,这时并不立即抢占当前任务的处理机,而是等到时钟中断到来时,调度程序才剥夺当前任务的执行,将处理机分配给新到的高优先权任务。  

    4.立即抢占的优先权调度算法:

    一旦出现外部中断,只要当前任务未处于临界区,便能立即剥夺当前任务的执行,把处理机分配给请求中断的紧迫任务。 

 

三、最早截止时间优先EDF(Earliest Deadline First) 算法 

    该队列按各任务截止时间的早晚排序;具有最早截止时间的任务排在队列的最前面

    1.用于非抢占调度的调度方式 

    2.抢占式调度方式用于周期实时任务

四、最低松弛度优先LLF(Least Laxity First)算法 

    松弛度=必须完成时间-本身的运行时间-当前时间

    当有任务执行时,只有等待任务的松弛度值为0才会发生任务的调度,其他情况不发生调度。 

    任务执行结束后或无任务执行时,再比较等待任务的松弛度值,较小的先执行。

标签:算法,半期,处理机,队列,作业,调度,3.4,3.1,进程
From: https://www.cnblogs.com/05-ReFrain-19/p/17324112.html

相关文章

  • 2023.4.16每日会议
    昨天做了什么:完成了饼状图和比例listview遇到了哪些问题:对饼状图的使用不知道今天准备做什么:尝试将数据库迁移到官方服务器 ......
  • 半期复习——第二章:进程管理(2.6)
    2.6进程通信一、进程通信的类型(3)  1.共享存储器系统    ①基于共享存储区的通信方式:为了传输大量数据,在存储器中划出了一块共享存储区,诸进程可通过对共享存储区中数据的读或写来实现通信。这种通信方式属于高级通信。    ②基于共享数据结构的通信方式:......
  • 2023.4.16周报
    本周总结:学了一些DP的优化套路大方向:动态规划小专题:斜率优化DP、四边形不等式优化DP题目完成情况:16 ......
  • 半期复习——第二章:进程管理(2.3)
    2.3进程控制(创建,终止,状态转换)一般由OS内核的原语实现一、操作系统内核  1.OS内核包含与硬件紧密相关的模块(如中断处理程序),常用设备驱动、运行频率高的模块(如时钟管理、进程调度)。安排在紧靠硬件的软件层次,常驻内存。  2.OS内核两大功能    ①支撑功能(中断处......
  • 退划 2 23.4.15
    与世隔绝压抑,喘不过气来。或者是说整个实验一都是比较死板的,如一潭死水般,没有新鲜的源头。我渴望一片充满阳光的绿茵地可是我被装进一间铁屋子里而我,也如密不透风的铁屋子里那唯一燃烧的蜡烛随着氧气耗尽,最终也会熄灭只希望我在所有的热情都被磨灭殆尽之日,可以熔出一个小......
  • 半期复习——第二章:进程管理(2.1 2.2)
    2.1前趋图和程序执行一、前趋图图(a)所示的前趋图,关系:P1→P2,P1→P3,P1→P4,P2→P5,P3→P5,P4→P6,P4→P7,P5→P8,P6→P8,P7→P9,P8→P9或表示为二元关系<P,→>P={P1,P2,P3,P4,P5,P6,P7,P8,P9}→={(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5),(P4,P6),(P4,P7),(P5,Ps),(P6,P8),(......
  • 2023.15 人工智能训练师
    AI在消灭一些职业岗位的同时,也会带来一些新的岗位,人工智能训练师就是其中之一。2020年,「人工智能训练师」正式成为新职业并纳入国家职业分类目录,是指「使用智能训练软件,在人工智能产品实际使用过程中进行数据库管理、算法参数设置、人机交互设计、性能测试跟踪及其他辅助作......
  • 2023.4.16
    1#include<iostream>2usingnamespacestd;3//设计圆类和点类,判断点和圆的关系4classPoint5{6public:7voidsetX(intx)8{9m_X=x;10}11intgetX()12{13returnm_X;14}15voidsetY(inty)......
  • day46(2023.4.15)
    1.多表查询 2.迪卡尔乘积 3.等值连接 4.非等值连接 5.自连接 6.99交叉连接 7.99自然连接 8.99内连接 9.外连接查询 10.多表查询,连接小练习 day46(2023.4.15)......
  • 2023.4.15
    1//设计立方体类,求出立方体的面积和体积,分别用全局函数和成员函数判断两个立方体是否相等2#include<iostream>3usingnamespacestd;4//立方体类设计5//1、创建立方体类6//2、设计属性7//3、设计行为获取立方体面积和体积8//4、分别利用全局函数和成员......