作业系统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