一周总结(八)

发表于 | 分类于

前言

有关操作系统cpu进程调度的概念总结

基本概念

  1. CPU(处理机、进程)调度
  2. Nonprescriptive(非抢占式)调度: 直到某进程运行完成或者阻塞时才把处理机分配给另一个进程
    • running -> waiting
    • terminate
  3. Preemptive(抢占式)调度: 系统基于某种原则(优先权、短进程优先、时间片)，剥夺当前进程的处理机，并分配给其他进程
  4. Dispatcher(调度程序): 分配处理器给短期调度选中的进程
    • 切换上下文
    • 切换用户模式
    • 跳到用户程序所在位置开始执行
  5. Dispatch latency(调度延迟): 调度程序停止一个进程到启动另一个进程的时间

调度算法的准则

  1. 面向用户
    • 周转时间(turnaround time)：进程从提交到完成的时间(执行(CPU)+等待(就绪+阻塞))
      • 周转时间=完成时间-提交时间
      • 平均周转时间=∑周转时间/进程数
      • 带权周转时间=周转时间/CPU执行时间
      • 平均带权周转时间=∑平均周转时间/进程数
    • 响应时间(response time): 进程提出请求到首次被响应的时间
    • 等待时间(waiting time): 进程在就绪队列中等待的时间总和
    • 截止时间: 开始截止时间和完成截止时间
  2. 面向系统
    • 吞吐量(throughput)单位时间内完成的进程数(批处理系统)
    • 平均周转时间不是吞吐量的倒数(考虑并发)
    • 处理机利用率(cpu utilization)
    • 设备的均衡利用
  3. 调度算法
  4. 最优原则
    • 最大CPU利用率 Max Cpu utilization
    • 最大吞吐量 Max throughput
    • 最短周转时间 Min turnaround time
    • 最短等待时间 Min waiting time
    • 最短响应时间 Min response time
    • 公平

调度算法

  1. FCFS(First-Come,First-Served)先来先服务
    • 按照作业提交的顺序形成就绪状态的先后sx
    • 当前作业占用CPU直到执行完或阻塞(非抢占)
    • 作业唤醒后(I/O完成)要等到当前作业让出CPU才执行
    • 最简单
    • 有利于长进程；有利于CPU Bound型进程；不利于短进程；不利于I/O Bound型进程
  2. SJF(Shortest-Job-First,SPF,Shortesst-Process-First)短作业优先
    • 对预计执行时间短的作业优先
    • 非抢占
    • 抢占式(SRT,SRTF,Shortest-Remainint-Time-First)当新来进程的剩余时间小于当前进程的运行时间则抢占
    • HRRN(是FCFS和SJF的折中)：响应比R=(等待时间+要求执行时间)/要求执行时间
    • 只能预测其运行时间，通过之前的CPU burst预测本次的CPU burst:Tn+1=αtn+(1-α)Tn，tn为实际中第n次CPU burst的长度。Tn为预测的下次CPU burst；0<=α<=1
  3. Priority 优先权
    • 分配给最高优先权的进程
      • 静态优先权:创建进程时确定(进程类型、对资源要求、用户要求)
      • 动态优先权:基于某种原则
    • 最小的整数≡最高的优先级
    • SJF以下一次CPU脉冲长度作为优先数
    • 非抢占式将最高优先级的进程放在队列头
    • 抢占式需要在高优先级进程到来时中断
    • 易出现饥饿(Starvation)问题，即进程长时间得不到执行；通过动态优先级解决(老化(Aging),随时间增加进程优先权)
  4. Round Robin 时间片轮转
    • 将所有就绪进程按照FCFS排队列
    • 每次调度将CPU分配给队首执行一个时间片(time slice(几毫秒到几百毫秒))
    • 时间片结束发生时钟中断
    • 切换上下文，将当前进程送到就绪队列队尾
    • 进程未使用完时间片(阻塞)也可以让出CPU
    • 时间片过大=>FIFO; 时间片过小=>但必须大于上下文切换，否则开销过大
    • 设时间片长度为q，队列进程数为n，则响应时间为n*q，每个进程一次以至多q的长度占有1/n CPU,进程不会等待超过(n-1)q
    • 就绪进程越多，时间片越小(响应时间一定)
    • 一个时间片内应该能处理完用户输入
    • 平均周转时间大于SJF，但响应时间小于SJF
  5. Multilevel Queue 多级队列
    • 将就绪队列分为多个子队列，每个作业固定在一个队列(系统进程、用户交互进程、批处理进程)
    • 分为foreground(interactive 前台、交互式)-RR background(batch 后台、批处理)-FCFS
    • 固定优先级调度：先前台再后台，可能会饥饿
    • 给定时间片调度：每个队列得到一定的CPU时间，进程在给定时间内执行
  6. Multilevel Feedack Queue 多级反馈队列：是时间片和优先级的综合
    • 对短进程：提高系统吞吐量和缩短平均周转时间
    • 对I/O进程，获得较好的I/O设备利用率和缩短响应时间
    • 多个就绪队列，每个队列的优先级不同(逐级降低)，时间片不同(逐级升高)
    • 新进程进入内存后先进入队列1的末尾，按FCFS调度，若在队列1中一个时间片未执行完，则降低优先级并加入到队列2的末尾，仍然按FCFS进行，在最低级的队列中使用RR
    • 当高优先级的队列为空时才执行低优先级队列；若此时有进程进入高优先级队列，则抢占式执行新进程，并将被抢占的进程投入原队列的末尾
    • I/O型进程：进入最高优先级队列以即时响应I/O，执行一个小时间片(只处理I/O数据)，转入阻塞
    • CPU型进程：每次执行完时间片进入更低级队列，最终采用最大时间片来执行，减少调度次数
    • I/O<CPU:处理完I/O进程后回到原队列
    • I/O完成时，提高优先级，时间片用完时，降低优先级
  7. HRRN(Highest Response Ratio Next) 高响应比优先
  8. 多处理器进程调度

    多线程调度

  9. 本地(local)线程: 线程库调度
  10. 全局(global)线程: 内核调度