个人网站建设思路,东莞做网站 汇卓,做淘客app要网站吗,国外设计网站app吗一.作业调度
作业调度算法需要知道以下公式 周转时间完成时间 - 到达时间 带权周转时间周转时间/运行时间 注#xff1a;带权周转时间越大#xff0c;作业#xff08;或进程#xff09;越短#xff1b;带权周转时间越小#xff0c;作业#xff08;或进程#xff09;越…一.作业调度
作业调度算法需要知道以下公式 周转时间完成时间 - 到达时间 带权周转时间周转时间/运行时间 注带权周转时间越大作业或进程越短带权周转时间越小作业或进程越长。带权周转时间越小越好 平均周转时间作业周转总时间/作业个数 平均带权周转时间带权周转总时间/作业个数 同时作业调度算法会涉及一个概念
饥饿
作业饥饿Job Starvation或被饿死Starvation就是一个或多个低优先级的作业无法获得系统资源无法得到执行的机会从而长时间处于等待状态的情况。这种情况下这些作业就会被饿死或者饥饿因为它们无法得到所需的系统资源而无法完成执行。
看如下例子 1.FCFS先来先服务算法
谁先到达谁就先运行所以作业运行顺序为1-2-3-4 第一个作业完成后第二个作业才能开始运行所以第二个作业开始的时间是1000 以此类推得到 先来先服务算法的特点 先来先服务算法实现简单但是可以看到排在长作业后面的短作业需要等待很长时间对短作业来说用户体验不好。 是否导致饥饿此算法较为公平不会导致饥饿 2.SJF(短作业优先调度算法)
谁的运行时间最短谁就先运行
首先也从第一个开始因为234都没有到达 第一个的完成时间是1000这时候234都到达了但是作业3的运行时间最短所以接下来运行作业3 作业4的运行时间最短所以接下来运行作业4以此类推最终的执行顺序为1-3-4-2 SJF算法的特点 短作业优先算法拥有“最短的”平均等待时间和平均周转时间 是否导致饥饿此算法会导致饥饿如果有源源不断的短作业进来可能使长作业长时间得不到服务。如果一直得不到服务则称为“饿死”。 注在实际情况下作业的运行时间往往是由用户提供的估计值并不一定真实准确。这意味着在实际应用中我们可能无法完全实现真正的短作业优先。 3.HRRF(高响应比优先算法) (等待时间运行时间)/运行时间 注:较高的响应比意味着作业等待时间相对较短或者作业的服务时间相对较长这可以确保作业尽快得到响应并完成。因此响应比越高通常表示作业具有更好的调度优先级 从作业1开始 若下一个执行的作业为作业2那么响应比就是1000-83040/4013/4
若下一个执行的作业为作业3那么响应比就是1000-9:0025/2585/25
若下一个执行的作业为作业4那么响应比就是1000-93030/302
因为85/2513/42下一个执行的作业是作业3 执行完后要重新计算高响应比响应比最高的运行得到
若下一个执行的作业为作业21025-83040/40155/403.875
若下一个执行的作业为作业41025-93030/3085/302.8333...
所以下一个执行的作业为作业2,则最终执行的顺序是1-3-2-4 高响应比优先算法的特点 综合考虑了等待时间和运行时间(要求服务时间) 等待时间相同时要求服务时间短的优先(SJF 的优点) 要求服务时间相同时等待时间长的优先(FCFS 的优点)对于长作业来说随着等待时间越来越久其响应比也会越来越大从而避免了长作业饥饿的问题。 二.进程调度
以上的作业调度我没有提到进程二字就是怕大家混淆起来进程调度和作业调度是两个不同的调度方法
1、作业调度 作业调度又称为高级调度频度较低。其主要工作是将位于外存后备队列中的某个或某几个作业调入内存排在就绪队列上。注意了这个时候仅仅是将作业调入内存并为作业创建进程、分配资源此时进程处于就绪态并没有执行。
2、进程调度 进程调度又称为低级调度是最基本的、频度最高的调度方式。其主要任务是从就绪队列中选取一个或几个进程并分配处理机的过程这时候才可以理解为“执行”。
3、区别 作业调度和进程调度最主要的区别在于前者是为作业建立进程的过程是将作业由外存调入内存的过程而后者整个过程并没有跑出内存的范围是将就绪态的进程变为运行态的过程。
进程调度也有饥饿的概念同时进程调度中还有一个重要的概念
抢占式/非抢占式 抢占式调度 •抢占式调度是指操作系统允许正在运行的进程被强制中断以便让更高优先级的进程获得CPU资源并开始运行。 •在抢占式调度中操作系统会定期检查所有正在运行的进程的优先级并且如果有更高优先级的进程出现操作系统会立即中断当前进程的执行将CPU资源分配给更高优先级的进程。 •例如在抢占式调度中当一个进程正在执行一个关键任务时如果有更高优先级的进程需要运行操作系统会立即中断当前进程的执行并将CPU资源分配给更高优先级的进程。 非抢占式调度 •非抢占式调度是指一旦一个进程获得处理器它就会一直运行直到完成或者自愿让出CPU。 •在非抢占式调度中高优先级的进程必须等待当前正在运行的进程结束或者主动让出CPU后才能获得CPU资源并开始运行。 •例如在非抢占式调度中当一个进程正在执行一个关键任务时其他高优先级的进程需要等待该进程完成或者主动让出CPU才能获得CPU资源并开始执行。 正因为进程调度有这两个性质所以除了拥有作业调度的三种算法FCFS,SJF,HRRF还有其他常见的算法
1.SRTF最短剩余时间优先调度算法
SRTF与SJF最大的区别就是其是抢占式的算法。 运行原理每当有进程加入就绪队列改变时就需要调度如果新到达的进程剩余时间比当前运行的进程剩余时间更短则由新进程抢占处理机当前运行进程重新回到就绪队列等待下一次调度。 2.RR时间片轮转调度算法
算法思想公平地、轮流地为各个进程服务让每个进程在一定时间间隔内都可以得到响应。 调度程序每次把CPU分配给就绪队列首进程/线程使用一个时间间隔称为时间片就绪队列中的每个进程/线程轮流运行一个时间片。
算法规则按照各进程到达就绪队列的顺序轮流让各个进程执行一个时间片每次选择的都是排在就绪队列队头的进程。若进程未在一个时间片内执行完则剥夺处理机将进程重新放到就绪队列队尾重新排队。时间片的选取时间片大小的确定要从进程个数、切换开销、系统效率和响应时间等方面考虑。常用轮转法 ① 最常用的轮转法是等时间片轮转法每个进程轮流运行相同时间片。 ② 改进的轮转法对于不同的进程分配不同的时间片时间片的长短可以动态修改。 是否抢占式抢占式 是否会产生饥饿不会 优点公平响应快适用于分时操作系统。缺点由于高频率的进程切换因此有一定开销不区分任务的紧急性。 对于时间片轮转调度算法的实现建议观看如下视频
RR时间片轮转调度算法 相同到达时间_哔哩哔哩_bilibili
RR时间片轮转调度算法不同到达时间_哔哩哔哩_bilibili 时间片太大或太小 ① 如果时间片太大使得每个进程都可以在一个时间片内就完成则时间片轮转调度算法退化为先来先服务调度算法并且会增大进程的响应时间。 ② 如果时间片太小进程调度、切换是有时间代价的会导致进程切换过于频繁系统会花大量的时间来处理进程切换从而导致实际用于进程执行的时间比例减小。 3.PSA(优先级调度算法)
算法思想根据任务的紧急程度来决定处理顺序。算法规则根据确定的优先级选取进程/线程每次总是选择就绪队列中优先级最高者运行。 用户进程/线程优先级的规定者有两种 ① 用户用户自己提出优先级称为外部指定法。优先级越高费用越高。 ② 系统由系统综合考虑有关因素来确定用户进程/线程的优先级称为内部指定法。 进程/线程优先级的确定方式 根据优先级是否随时间而变进程/线程优先级的确定有静态和动态两种方式 ① 静态优先级在进程/线程创建时确定此后不再改变。优先级主要由进程类型、资源需求、时间需求和用户需求决定。 优点比较简单开销小。 缺点不够公平不太灵活可能出现优先级低的作业/进程长时间得不到调度的情况。 ② 动态优先级随时间而变基本原则是 a. 正在运行的进程/线程随着占有CPU时间的增加优先级逐渐降低 b. 就绪队列中等待CPU的进程/线程随着等待时间增加优先级逐渐提高。 优点公平性好灵活资源利用率高。 缺点需要花费比较多的执行程序时间因而花费的系统开销比较大。 是否可抢占抢占式非抢占式都有。 是否导致饥饿会 若源源不断地有高优先级进程到来则可能导致饥饿。 区别在于非抢占式只需在进程主动放弃处理机时进行调度即可而抢占式还需在就绪队列变化时检查是否发生抢占。优点用优先级区分紧急程度、重要程度适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。缺点若源源不断地有高优先级进程到来则可能导致饥饿。 优先级调度算法
速通操作系统优先级调度算法_哔哩哔哩_bilibili 4. MLFQ(多级反馈队列调度算法)
算法思想对其他调度算法的折中权衡。算法规则 1、建立多级就绪进程队列各级队列优先级从高到低时间片从小到大。每个队列赋予不同优先级较高优先级队列一般分配给较短的时间片。
2、新进程到达时先进入第1级队列按先来先服务原则排队等待被分配时间片若用完时间片进程还未结束则进程进入下一级队列队尾若此时已经在最下级的队列则重新放回该队列队尾。
3、处理器调度每次先从高优先级就绪队列中选取可占有处理器的进程只有在选不到时才从较低优先级就绪队列中选取进程。即只有第k级队列为空时才会为k1级队头的进程分配时间片。
4、任务可以根据自身的行为如CPU使用时间、等待时间等在不同的队列之间移动实现动态优先级的调整。 是否可抢占抢占式 在k级队列的进程运行过程中若更上级的队列1~k-1级中进入了一个新进程则由于新进程处于优先级更高的队列中因此新进程会抢占处理机原来运行的进程放回k级队列队尾。 是否导致饥饿会优点对其他调度算法的折中权衡。 对各类进程相对公平FCFS的优点 短进程只用较少的世界就可完成SPF的优点 每个新到达的进程都可以很快得到响应RR的优点 不必实现估计进程的运行时间避免用户作假 可灵活地调整对各类进程的偏好程度比如CPU密集型进程、I/O密集型进程拓展可以将因I/O而阻塞的进程重新放回原队列这样I/O型进程就可以保持较高优先级。缺点可能会导致饥饿 多级反馈队列调度算法
【进程管理】多级反馈队列调度算法_哔哩哔哩_bilibili
