处理机调度参考

实验原理:

时间片轮转调度算法和优先权调度算法本质上是一致的,只是在调度时选择的策略不一样而已,其程序的流程图是一致的,所以在此仅给出了一个流程图。具体算法流程图如图1所示。

图1 处理机调度算法流程图

1. 时间片轮转调度算法

当系统按时间片轮转算法调度进程时,将所有的就绪进程按照一定的原则(如先来先服务原则)排列,形成一个就绪队列。每次调度为队首进程分配CPU资源,令其执行一个时间片,该时间片的大小从几ms到几百ms。当时间片用完时,由计时器发出中断信号,通知系统剥夺当前运行进程的CPU使用权,并将此进程送入就绪队列的末尾,等待下一次执行;然后,把处理机分配给就绪队列中新的队首进程,执行重复操作。在进程运行过程中,如果时间片未用完而等待事件发生,则该进程进入等待队列,系统将CPU重新分配给就绪队列的队首进程,一旦事件发生后,等待队列的队首进程进入就绪队列末尾。这样就可以保证就绪队列中的所有进程,在可接受的等待时间内,均能获得处理机并调度执行。

时间片轮转调度算法的进程状态转换图如图2所示。

事件发生

图 2 时间片轮转调度算法进程状态转换图

2. 优先权调度算法

优先权调度算法的进程状态转换图如图3所示。

事件发生

图 3 优先权调度算法进程状态转换图

1) 优先权调度算法的类型

(1) 非抢占式优先权算法

在这种方式下,系统一旦把处理机分配给就绪队列中优先权最高的进程,该进程便一直执行下去,直至完成;或因发生某事件使该进程放弃处理机时,系统方可将处理机分配给另一优先权高的进程。这种调度算法主要用于批处理系统中,也可用于某些对实时性要求不严的实时系统中。

(2) 抢占式优先权调度算法

在这种方式下,系统同样是把处理机分配给优先权最高的进程,使之执行。一旦出现了另一个优先权更高的进程时,进程调度程序就停止原最高优先权进程的执行,而将处理机分配给新出现的优先权最高的进程。

2) 优先权的类型

对于最高优先权算法,其关键在于是采用静态优先权,还是动态优先权。

(1) 静态优先权

静态优先权是在创建进程时确定的,且规定它在进程的整个运行期间保持不变。一般,优先权是利用某一范围内的一个整数来表示。确定进程优先权的依据是:

①进程类型

②进程对资源的需求

③进程的估计执行时间及内存需要量

④用户需求

(2)

动态优先权

动态优先权是指在创建进程时所赋予的优先权,可以随进程的推进或随其等待时间的增加而改变,以便获得更好的调度性能。

例如,在就绪队列中的进程,随其等待时间的增长,其优先权以速率a提高。若所有的进程都具有相同的优先权初值,则应将最先进入就绪队列的进程赋予最高动态优先权,从而优先获得处理机,即FCFS算法。

优先权的变化规律可描述为:

由于等待时间与服务时间之和,就是系统对该作业的响应时间,故该优先权又相当于响应比RP。

实验内容:

1. 设计一个按动态优先数调度算法实现处理机调度的程序

(1) 假定系统有四个进程,每一个进程用一个进程控制块PCB来代表,进程控制块的结构如表1所示。其中,

进程id——进程的标识

进程名称——假设若干个进程的进程名分别为P1,P2,P3,P4…

进程状态——进程三态转化的标识(1-运行态、2-就绪态、3-等待态、0-完成态)

进程类型——进程是系统进程还是用户进程(0-系统进程、1-用户进程)

请求资源的时刻——请求资源的时刻

表1 PCB结构

总共需要CPU的时间——假设进程需要运行时间数。

运行时间——当前进程已运行时间。

优先数——赋予进程的优先数,调度时总是选取优先数小(即优先级高的)的进程先执行。

指向下一个进程的指针——用指针指出下一个进程的进程控制块的首地址,最后一个进程中的指针为“NULL”。

(2) 在每次运行所设计的处理器调度程序之前,为每个进程确定它的“进程名称”和“总共需要CPU的时间”。

(3) 在调度过程中,设计四个队列:完成态队列、运行态队列、就绪态队列、等待态队列。

(4) 根据“总共需要CPU的时间”确定请求资源的时刻,资源的结构可以如表2所示。

表2 资源数据结构

(5) 处理器调度总是选就绪队列的首进程运行。采用动态改变优先数的办法,进程每运行一次优先数就减“1”,就绪队列中的进程加“2”。在运行过程中,改变进程的优先级,要求运行时间减“1”来模拟进程的一次运行。

(6) 当运行进程的运行时间到达请求资源的时刻时,去占用资源,若资源现处于被占用状态就进入等待状态,若资源空闲,进入就绪状态。

2. 设计一个按时间片轮转法实现处理机调度的程序

(1) 假定系统有四个进程,每一个进程用一个进程控制块PCB来代表,进程控制块的元素如表3所示。其中,

进程id——进程的标识

进程名称——假设若干个进程的进程名分别为P1,P2,P3,P4…

进程状态——进程三态转化的标识(1-运行态、2-就绪态、3-等待态、0-完成态)

进程类型——进程是系统进程还是用户进程(0-系统进程、1-用户进程)

表3 时间片轮转法PCB结构

请求资源的时刻——请求资源的时刻

总共需要CPU的时间——假设进程需要运行时间数。

运行时间——当前进程已运行时间。

优先数——赋予进程的优先数,调度时总是选取优先数小(即优先级高的)的进程先执行。

指向下一个进程的指针——用指针指出下一个进程的进程控制块的首地址,最后一个进程中的指针为“NULL”。

(2) 在每次运行所设计的处理器调度程序之前,为每个进程确定它的“进程名称”和“总共需要CPU的时间”。

(3) 在调度过程中,设计四个队列:完成态队列、运行态队列、就绪态队列、等待态队列。

(4) 根据“总共需要CPU的时间”确定请求资源的时刻,资源的数据结构如表2所示。

(5) 处理器调度总是选就绪队列的首进程运行。采用时间片轮转法的办法,进程每运行一个时间片当前运行进程进入就绪态,就绪队列中的首个进程进入运行态来模拟进程的一次运行。

当运行进程的运行时间到达请求资源的时刻时,去占用资源,若资源现处于被占用状态就进入等待状态等待,若资源空闲,进入就绪状态。

实验原理:

时间片轮转调度算法和优先权调度算法本质上是一致的,只是在调度时选择的策略不一样而已,其程序的流程图是一致的,所以在此仅给出了一个流程图。具体算法流程图如图1所示。

图1 处理机调度算法流程图

1. 时间片轮转调度算法

当系统按时间片轮转算法调度进程时,将所有的就绪进程按照一定的原则(如先来先服务原则)排列,形成一个就绪队列。每次调度为队首进程分配CPU资源,令其执行一个时间片,该时间片的大小从几ms到几百ms。当时间片用完时,由计时器发出中断信号,通知系统剥夺当前运行进程的CPU使用权,并将此进程送入就绪队列的末尾,等待下一次执行;然后,把处理机分配给就绪队列中新的队首进程,执行重复操作。在进程运行过程中,如果时间片未用完而等待事件发生,则该进程进入等待队列,系统将CPU重新分配给就绪队列的队首进程,一旦事件发生后,等待队列的队首进程进入就绪队列末尾。这样就可以保证就绪队列中的所有进程,在可接受的等待时间内,均能获得处理机并调度执行。

时间片轮转调度算法的进程状态转换图如图2所示。

事件发生

图 2 时间片轮转调度算法进程状态转换图

2. 优先权调度算法

优先权调度算法的进程状态转换图如图3所示。

事件发生

图 3 优先权调度算法进程状态转换图

1) 优先权调度算法的类型

(1) 非抢占式优先权算法

在这种方式下,系统一旦把处理机分配给就绪队列中优先权最高的进程,该进程便一直执行下去,直至完成;或因发生某事件使该进程放弃处理机时,系统方可将处理机分配给另一优先权高的进程。这种调度算法主要用于批处理系统中,也可用于某些对实时性要求不严的实时系统中。

(2) 抢占式优先权调度算法

在这种方式下,系统同样是把处理机分配给优先权最高的进程,使之执行。一旦出现了另一个优先权更高的进程时,进程调度程序就停止原最高优先权进程的执行,而将处理机分配给新出现的优先权最高的进程。

2) 优先权的类型

对于最高优先权算法,其关键在于是采用静态优先权,还是动态优先权。

(1) 静态优先权

静态优先权是在创建进程时确定的,且规定它在进程的整个运行期间保持不变。一般,优先权是利用某一范围内的一个整数来表示。确定进程优先权的依据是:

①进程类型

②进程对资源的需求

③进程的估计执行时间及内存需要量

④用户需求

(2)

动态优先权

动态优先权是指在创建进程时所赋予的优先权,可以随进程的推进或随其等待时间的增加而改变,以便获得更好的调度性能。

例如,在就绪队列中的进程,随其等待时间的增长,其优先权以速率a提高。若所有的进程都具有相同的优先权初值,则应将最先进入就绪队列的进程赋予最高动态优先权,从而优先获得处理机,即FCFS算法。

优先权的变化规律可描述为:

由于等待时间与服务时间之和,就是系统对该作业的响应时间,故该优先权又相当于响应比RP。

实验内容:

1. 设计一个按动态优先数调度算法实现处理机调度的程序

(1) 假定系统有四个进程,每一个进程用一个进程控制块PCB来代表,进程控制块的结构如表1所示。其中,

进程id——进程的标识

进程名称——假设若干个进程的进程名分别为P1,P2,P3,P4…

进程状态——进程三态转化的标识(1-运行态、2-就绪态、3-等待态、0-完成态)

进程类型——进程是系统进程还是用户进程(0-系统进程、1-用户进程)

请求资源的时刻——请求资源的时刻

表1 PCB结构

总共需要CPU的时间——假设进程需要运行时间数。

运行时间——当前进程已运行时间。

优先数——赋予进程的优先数,调度时总是选取优先数小(即优先级高的)的进程先执行。

指向下一个进程的指针——用指针指出下一个进程的进程控制块的首地址,最后一个进程中的指针为“NULL”。

(2) 在每次运行所设计的处理器调度程序之前,为每个进程确定它的“进程名称”和“总共需要CPU的时间”。

(3) 在调度过程中,设计四个队列:完成态队列、运行态队列、就绪态队列、等待态队列。

(4) 根据“总共需要CPU的时间”确定请求资源的时刻,资源的结构可以如表2所示。

表2 资源数据结构

(5) 处理器调度总是选就绪队列的首进程运行。采用动态改变优先数的办法,进程每运行一次优先数就减“1”,就绪队列中的进程加“2”。在运行过程中,改变进程的优先级,要求运行时间减“1”来模拟进程的一次运行。

(6) 当运行进程的运行时间到达请求资源的时刻时,去占用资源,若资源现处于被占用状态就进入等待状态,若资源空闲,进入就绪状态。

2. 设计一个按时间片轮转法实现处理机调度的程序

(1) 假定系统有四个进程,每一个进程用一个进程控制块PCB来代表,进程控制块的元素如表3所示。其中,

进程id——进程的标识

进程名称——假设若干个进程的进程名分别为P1,P2,P3,P4…

进程状态——进程三态转化的标识(1-运行态、2-就绪态、3-等待态、0-完成态)

进程类型——进程是系统进程还是用户进程(0-系统进程、1-用户进程)

表3 时间片轮转法PCB结构

请求资源的时刻——请求资源的时刻

总共需要CPU的时间——假设进程需要运行时间数。

运行时间——当前进程已运行时间。

优先数——赋予进程的优先数,调度时总是选取优先数小(即优先级高的)的进程先执行。

指向下一个进程的指针——用指针指出下一个进程的进程控制块的首地址,最后一个进程中的指针为“NULL”。

(2) 在每次运行所设计的处理器调度程序之前,为每个进程确定它的“进程名称”和“总共需要CPU的时间”。

(3) 在调度过程中,设计四个队列:完成态队列、运行态队列、就绪态队列、等待态队列。

(4) 根据“总共需要CPU的时间”确定请求资源的时刻,资源的数据结构如表2所示。

(5) 处理器调度总是选就绪队列的首进程运行。采用时间片轮转法的办法,进程每运行一个时间片当前运行进程进入就绪态,就绪队列中的首个进程进入运行态来模拟进程的一次运行。

当运行进程的运行时间到达请求资源的时刻时,去占用资源,若资源现处于被占用状态就进入等待状态等待,若资源空闲,进入就绪状态。


相关文章

  • 在线作业3 期末考试复习
  • 在线作业3 一.单选 1. 为了根据进程的紧迫性做进程调度,应采用( ).[参考答案] 优先数调度算法 2. 采用优先数调度算法时,对那些具有相同优先数的进程再按( ? ?)的次序分配处理器.? ?[参考答案] 先来先服务 3. 当一进程运 ...查看


  • 第一章作业 参考答案
  • 第一章作业 1.设计现代OS 的主要目标是什么? 答:有效性.方便性.可扩充性.开放性. 12.试从交互性.及时性以及可靠性方面,将分时系统与实时系统进行比较. 答: a. 交互性:分时系统是一种通用系统,主要用于运行终端用户程序,因而它具 ...查看


  • 操作系统课程设计-对处理机的调度
  • 福建农林大学金山学院 课程设计报告 课程名称: 课程设计题目: 姓 名: 系: 专 业: 年 级: 学 号: 指导教师: 职 称: <操作系统> 对处理机的调度 信息与机电工程系 计算机科学与技术 李盼盼 助教 2013年12月 ...查看


  • 炼铁厂煤气中毒事故应急演练预案方案 (参考)
  • 炼铁厂煤气中毒事故应急演练预案 1总则 1.1编制目的 为提高炼铁厂处置煤气突发事件的应急能力,使当班员工及炼铁厂相关车间.科室掌握煤气事故应急救援的程序和中毒人员的施救方法,能够在事故发生后立即启动事故应急响应,最大限度地确保人员安全和减 ...查看


  • 嵌入式实时系统中的关键技术.doc
  • JIU JIANG UNIVERSITY 毕业 综合技能测试 题 目 嵌入式实时系统中的关键技术 院 系 信息科学与技术学院 专 业 计算机应用技术 姓 名 江源泉 班级学号 B123113 指导教师 二○一四年十二月 摘 要 本文介绍了嵌 ...查看


  • 作业调度算法
  • 2011年第17 期 ● ◇高教论述◇ 作业调度算法 崔帅1楚蓝天2高凯2 (1. 中国矿业大学环境与测绘学院江苏徐州221116: 2. 中国矿业大学化工学院江苏徐州221116) [摘要]在多道系统中,对批处理作业需要进行作业调度.作业 ...查看


  • 山东光伏电站并网调度技术支持系统技术规范
  • 山东光伏电站并网调度技术支持系统 技术规范 二○一四年三月 目 录 1 范围 ................................................................................. ...查看


  • 采用高响应比算法的进程调度程序
  • 操作系统课程设计 采用高响应比算法的进程调度程序 学 院 专 业 学 生 姓 名 学 号 指导教师姓名 2014 年 3月 18日 目 录 一. 实验题目 .......................................... ...查看


  • 智能变电站一体化监控系统有关规范解读_樊陈
  • 第36卷 第19期2012年10月10 日Vol.36 No.19 ,Oct.102012 :/.issn.1000DOI10.39691026.2012.19.001-j 智能变电站一体化监控系统有关规范解读 樊 陈1,倪益民1,窦仁晖1 ...查看


热门内容