CPU调度 用于多道程序
以下先讨论对于单CPU的调度问题。
回顾多道程序,同时把多个进程导入内存,使得一个进程在CPU中执行I/O时,一个进程用来填补CPU的时间。
通常进程都是在CPU区间和I/O区间之间转换。
CPU调度程序称为短期调度程序,从内存调度到CPU。
在内存中等待的就绪队列的节点是PCB。有许多不同的队列实现方法。
抢占调度和非抢占调度(协作):前者为一个进程还没结束之前就被夺取CPU的拥有权,而后者则要一个进程结束或等待I/O才给予其他进程CPU的拥有权。
虽然现代操作系统都是用抢占调度,但是对于同时访问一个数据来说就会有风险,比如一个进程在试图更新一个数据,但是另一个进程抢占,并且读取这个数据,使得数据不一致。这时就要用到进程同步的内容。lock
对于中断随时可能发生的情况,我们可以在执行某个代码段时,禁止中断。
分派程序用来把CPU的拥有权交给短期调度程序选定的进程。每次切换进程时都要使用。
分派延迟:分派程序所花的时间。
CPU调度需要考虑的因素:
1.CPU使用率。
2.吞吐量:单位时间完成进程的数量。
3.周转时间:进程提交到进程完成。即从磁盘等待进入内存+就绪队列等待时间+CPU执行时间+I/O执行时间。但是CPU调度算法只是里面的一块。
4.等待时间:在就绪队列等待的时间之和。
5.响应时间:用于交互系统。
CPU调度算法: Gantt图考点求等待时间
此算法应用于内存就绪队列到CPU的过程。
1.FCFS 先到先服务
一旦选定进程,那么在结束之前就不能再切换到另一个进程。
2.SJF 最短优先 精确的讲是最短下一个CPU区间的算法
前面提到,一个进程是由CPU区间和I/O区间交替组成的。而SJF是看哪个进程的CPU区间最短。
(1)SRTF抢占式:又称最短剩余优先,当新进来的进程的CPU区间比当前执行的进程所剩的CPU区间短,则抢占。
(2)非抢占:称为下一个最短优先,因为在就绪队列中选择最短CPU区间的进程放在队头。
SJF用于长期调度而不能用短期调度,因为进程是一个整体,CPU没法知道进程中第一个CPU区间长度。
SJF需要确定下一个CPU区间的时间长度,可以通过近似估算出下一个CPU区间的长度,比如tn+1=atn+(1-a)rn tn为最近最近一次的CPU时间,rn为历史记录。a是给定的权重。
3.优先级调度算法 pintos的优先级是0-63 0为最低优先级,63为最高优先级
SJF是特殊的优先级调度算法,以CPU区间长度的倒数为优先级。
(1)内部优先级:通过内部数据比如内存要求等。
(2)外部优先级:用户自己设定。set_priority
分为抢占式和非抢占式,前者为如果进来的进程优先级高于运行的进程,则替换;后者只是在就绪队列中按优先级排队。
缺点:无线阻塞或饥饿。前者为一个优先级高且运行时间长的进程一直阻塞,后者为优先级低的进程永远都得不到执行。
解决饥饿的方法是老化。通过每个时间间隔后将等待的进程优先级降低。
4.转轮法 RR算法 抢占式
用于分时系统。每个进程都占用一个时间片的时间。就绪队列为FIFO循环队列。如果一个进程的CPU区间长度小于时间片,则继续下面的进程;如果大于时间片,则中断切换到下一个进程执行。
通常时间片长度为10ms-100ms,由此需要确定时间片大小使得上下文切换次数适当少。
5.多级队列调度
根据某种性质将一个就绪队列分成不同的独立队列,如系统进程,交互进程(前台进程),交互编辑进程,批处理进程,学生进程。
每个队列都有不同的调度算法。
每个队列都有优先级,比如前台队列就比后台队列要有绝对的优先级,因此队列间的分配方法:
(1)只有优先级高的队列为空,才能执行低优先级队列。
(2)为队列分配不同权重的CPU时间,优先级高的分配时间多。
6.多级反馈队列 抢占式
动态调整进程,进程在不同队列之间移动,虽然在队列间移动需要耗费资源,但是更合理。
按照CPU区间的大小分队列。
进程之间的划分是按照所花CPU时间划分,比如队列0是就绪队列,且规定一个时间上界,如果一个进程没能规定时间完成,则被放入队列1中。CPU区间越大的进程就被放入低优先级中。每个进程一开始都进入就绪队列。
多级反馈队列的参数:
1.队列的数量。
2.每个队列的调度算法。
3.怎样升级到优先级更高的队列。
4.确定怎样降级到优先级更低的队列。
5.进程需要确定进入哪个队列。
接下来讲多个CPU的负载均衡问题。
假设多个CPU是同构的,但是可能也会有特殊的限制比如只有某个CPU与I/O设备连接。
(1)非对称多处理:一个处理器专门用于CPU调度决定等,其他用于执行用户代码。
(2)对称多处理(SMP):为每个处理器自我调度,可能会造成多个处理器同时访问同一个数据结构则会造成冲突。
处理器亲和性:一个进程只需要在一个处理器上执行即可,不会转到另一个处理器上执行,因为如果转移的话,处理器缓存的资源全部无效,浪费。缓存存储的是进程的连续访问的数据。
软亲和性:占时的不会转移。
硬亲和性:操作系统不允许进程在多处理器间游走。
负载平衡条件:每个处理器都有私有的就绪队列。
负载平衡方法:push和pull。即从负载高的处理器push到低负载的处理器上,从负载低的处理器pull到负载高的处理器,但是这样就缺失了处理器亲和性。
一个物理处理器可以划分为逻辑处理器,SMT(对称多线程)使得在一个物理处理器上同时运行多个线程。
逻辑处理器对于物理处理器就像线程对进程。多个逻辑处理器共享物理处理器的资源,如缓存和总线。
举个例子,就像分区一样,硬盘分为C盘,D盘等,但事实上不是真的分硬盘。更理论的讲,像数据库的逻辑和物理关系。
系统调度的是内核线程,用户线程由线程库管理。如果线程要在CPU上运行,需要与某个内核线程相连。
用户线程需要连接到LWP(进程竞争范围PCS)。
内核线程连接到物理CPU(系统竞争范围SCS)。
linux采用抢占、优先级的调度算法,较高优先级的进程被分配较多的CPU时间片。每个处理器都维护一个运行队列。运行队列分为活动和到期的,前者是进程所耗时间小于时间片的,后者是所花时间大于时间片的任务。
当活动队列为空,则互换两队列。
调度算法的评估:
1.分析评估法。事先确定负荷和算法,即一些本来可以自己设定的数据,比如确定特定算法FCFS,确定进程到来的时间和数量;根据不同的模型来比较性能。缺点是只适用于特定的情况。
2.排队模型。数学公式以分析CPU和I/O的区间分布,给定进程到达系统的时间分布,排队网络分析。LITTLE公式:进入队列的进程和离开队列的进程要相等。
3.模拟。建模计算机系统,模拟程序,根据概率分布随机生成数据,不能对于前后事件进行预测。但是通过跟踪磁带来记录真实系统的运作,再来按照这种顺序来模拟即可。
4.实现。编程后放入操作系统,观测。
分享到:
相关推荐
操作系统课程实验 ,能直接运行,cpu调度算法集合
操作系统概念课程,实验一CPU调度,设计一个按优先权调度算法实现处理机调度的程序,实验工具是NetBeans IDE 8.2,采用图形界面和代码实现。
这是操作系统中的调度问题,调度策略是动态优先级调度,仅是模拟
轮询调度算法的CPU调度模拟程序.操作系统课的作业。原理
操作系统\ CPU调度.pdf 操作系统\ CPU调度.pdf
此CPU调度算法是自己精心做的,也是为了完成课程设计。
操作系统实验报告 C语言模拟实现FIFO、SJF和优先权调度。内含实验原理、源码、运行结果。源码可运行
多种CPU调度算法模拟(操作系统实验) C++
1,本资源共分两部分,第一期为本人的...2,因为资源中会引用他人的作品,涉及原创的问题,故在“操作系统实验项目开发声明.txt”中予以声明, 3,因个人时间安排原因,暂上传第一期资源,第二期会尽快续传,望见谅!
操作系统概念中文书 第六版的(第六章 CPU调度) 俗称“恐龙书” 对学习有所帮助的
本人以前的做的操作系统实验——CPU调度算法,里面有很多缺陷,读者可以自己完善一下。代码比较简单,所以只适合对cpu调度算法不理解和刚接触编程的朋友,更复杂的设计读者朋友可以自己设计。如果在dos下面运行,则...
星载实时微内核操作系统的CPU调度.pdf
操作系统实验之进程调度.进程调度算法:采用最高优先数优先的调度算法(即把处理机分配给优先数最高的进程)和先来先服务算 法。 每个进程有一个进程控制块( PCB)表示。进程控制块可以包含如下信息:进程名、...
操作系统课程设计报告( 进程调度).doc 操作系统课程设计报告( 进程调度).doc 操作系统课程设计报告( 进程调度).doc 修改即可
这是模拟操纵系统中CPU调度问题,调度策略是最短剩余时间优先,声明只是模拟,并没有真正的进程调度。
进程调度模拟程序:假设有10个进程需要在CPU上执行,分别用: 先进先出调度算法; 基于优先数的调度算法; 最短执行时间调度算法 确定这10个进程在CPU上的执行过程。要求每次进程调度时在屏幕上显示: 当前...
然后就是调度函数了,循环320次,随机生成指令,然后模拟请求调页的过程。 按照老师PPT上给的指令访问次序原则,FIFO算法和LRU算法基本上都是 页面0调页,页面1调页,页面2调页,页面3调页,这种顺序,缺页率也始终...
CPU调度的模拟实现
本资源包含用C++写的三个程序,分别是模拟操作系统的处理器的优先级调度算法,内存管理的首次适应算法,磁盘管理的模拟unix磁盘管理算法。还包含完整的实验报告。