作业系统L5－行程排班

CPU-I/O分割

简介:CPU分割后接着IO分割

CPU排班程式

短程排班程式(Short-term scheduler):就绪伫列选出形成配置CPU给他，包含转换内容(context switch)，转换成使用者模式CPU排班决策时刻执行->等待(不可抢先nonpreemptive)执行->就绪(可抢先preemptive)等待->就绪(可抢先preemptive)形成终止(不可抢先nonpreemptive)分派潜伏期(dispatchlatency):分派程式用来停止一个行程，并开始另一个行程所用的时间排班原则CPU使用率(CPU Utilization)产量(Throughput)回复时间(Turnaround Time)等候时间(Waiting Time)反应时间(Response Time)

排班演算法

先来先做(FCFS)

等待时间:P1= 0; P2= 24; P3 = 27平均等待时间:(0 + 24 + 27)/3 = 17护送现象(convoyeffect) :短行程在长行程前面

最短工作先做(SJF)

平均等待时间= (3 + 16 + 9 + 0) / 4 = 7分割时间:预估接近前一次的长度

平均等待时间= [(10-1)+(1-1)+(17-2)+(5-3)]/4=26/4=6.5

优先权排班

每个行程都有优先权数字(越小=>越高优先权)饥饿(Starvation):低优先权行程可能永远无法执行老化(Aging):随着时间提高优先权

平均等待时间=8.2

依序循环(Round Robin, RR)

简介:每个行程分一小段时间量(time quantum)q，用完行程会被抢先，加到就绪伫列的尾端

多层伫列简介:分为多个独立伫列，EX前景 背景

执行绪排班

行程竞争範围(process-contentionscope, PCS)系统竞争範围(system-contentionscope, SCS)

多处理器

同质处理器(Homogeneous Processors):考虑所有处理器都相同非对称多元处理(Asymmetric Multiprocessing):一个主处理器负责排班决定、I/O处理、其它系统活动，其他只执行使用者程式码对称多元处理(Symmetric Multiprocessing):每一个处理器自行排班处理器亲和性软性亲和性(soft affinity):保持一个行程在相同处理器上执行，但不保证它会永远这么做硬性亲和性(hard affinity):指定处理器能够执行特定行程非均匀记忆体存取(non-uniform memory access负载平衡(Load balancing ):试着让工作量平均分布推转移(Push migration):将过度负载CPU的行程推到其它CPU拉转移(Pull migration):闲置处理器从忙碌处理器拉任务利用记忆体停滞:另一个硬体执行绪在记忆体存取发生时执行

即时CPU排班(Real-time System)

软即时系统:对于非常即时的行程排班没有提供保证硬即时系统–任务必须在指定的限期内被服务中断潜伏期(Interrupt Latency):中断到达到开始执行中断服务常式的时间分派潜伏期(Dispatch Latency):停止目前行程并且启动另一个行程的排班时间

单调速率排班演算法

单调速率排班而延误截止期限

简介:根据行程週期的反比设定优先权P1週期是50，P2週期是80，P1被设定优先权高于P2，P1处理时间25，P2处理时间35

最早截止期限优先排班(EDF)

简介:优先权是根据截止期限设定P1週期是50，P2週期是80，P1被设定优先权高于P2，P1处理时间25，P2处理时间35