操作系统备忘录--处理机

内容

  • 处理机

  • 作业与作业步

  • 作业调度

  • 进(线)程调度

  • 实时调度

1. 处理机

处理机是处理计算机系统中存储程序和数据，并按照程序规定的步骤执行指令的部件，包括中央处理器，主存储器，输入-输出接口，若加上接外围设备就构成完整的计算机系统。

处理机是计算机系统中存储程序和数据，并按照程序规定的步骤执行指令的部件

2. 作业与作业步

3. 作业

  • 在一次应用计算或者事务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该次任务处理的全部工作的总称

4. 作业步

  • 在一个作业的处理过程中，计算机所做的相对独立的工作。(如编译, 链接,运行)

5. 作业控制块

  • 作业在系统中存在的标志，保存系统对作业进行管理和调度所需信息
  • 作业标志，用户名称，作业类型，状态，调度信息，资源需求，时间信息等

6. 作业调度

  • 根据作业控制块的内容，检查系统是否满足作业的资源要求， 并按一定算法选取作业调入内存，为其创建进程，分配必要的资源。将新创建的进程插入就绪队列，准备运行

7. FCFS

  • 有利于长作业，不利于短作业

8. SJF

  • 降低作业的平均等待时间，提高系统吞吐量
  • 对长作业不利，严重的会导致长作业长期的得不到执行
  • 未考虑作业紧迫程度

9. HRRN

Highest Response Ratio Next

  • $优先权=\frac{等待时间+要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间}$
  • 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，转化为短作业优先。
  • 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，转化为先来先服务。

10. 进(线)程调度

调度方式

  • 非抢占
  • 抢占

11. RR

Round-Robin

  • 简单时间片轮转法

  • 进程排成队列、先来先服务

  • 多级反馈队列调度算法

    • 设置多个就绪队列；依次为各个队列赋予不同的优先级；优先权愈高的队列中，为每个进程所规定的执行时间片就愈短
    • 新进程进入内存，首先放入第一队列的末尾， 按FCFS原则待调度。轮到该进程执行时，如能在一 个时间片内完成，便可准备撤离系统；如果未能完成，便将该进程转入第二队列的末尾，再同样地按 FCFS原则等待调度执行, 依此类推
    • 仅当第$1\leftrightarrow (i-1)$队列均空时，才会调度第$i$队列中的进程运行。如果处理机正在第$i$队列中为某进程服务时，又有新进程进入优先权较高的队列(第$1\leftrightarrow (i-1)$中的任何一个队列)，则此时新进程 将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第$i$队列的末尾，把处理机分配给新到的高优先权进程。

  • 性能分析

    • 终端型作业用户：交互短作业 ，通常可在第一队列完成
    • 短批处理作业用户：可在前几个队列完成，周转时间较短
    • 长批处理作业用户：依次在1，2，…. 队列运行，最后到n队列按轮转方式运行

12. 实时调度

最早截止时间优先(Earliest Deadline First)

  • 截止时间早，优先级高

最低松弛度优先(Least Laxity First)

  • 根据任务的紧急（松弛）程度确定优先级

13. 优先级倒置2

  • 高优先级进程被低优先级进程延迟或阻塞

  • 动态优先级继承

    • 高优先级进程P因低优先级进程Q 而阻塞，提升 低优先级进程到高优先级进程级别，阻止优先级低 于进程P优先级而高于Q优先级的进程抢占Q.

14. 死锁

定义

死锁（英语：Deadlock），又译为死结，计算机科学名词。当两个以上的运算单元，双方都在等待对方停止运行，以获取系统资源，但是没有一方提前退出时，就称为死锁。

原因

  • 互斥条件
    • 资源不能同时被两个或以上进程共享
  • 不剥夺条件
    • 进程已经获得的资源在未使用完毕之前，不可被其它进程强行剥夺，而只能自己释放
  • 部分分配
    • 每次申请所需要的一部分资源，在等待新资源的同时， 继续占有已经分配到的资源
  • 循环等待
    • 存在进程循环链，链中每一进程已获得的资源同时被下一个进程所请求。

15. 预防死锁

  • 打破“部分分配”条件
    • 静态分配资源
  • 破坏“不破坏“不可抢占”条件”条件
    • 进程提出新的资源请求如不能满足则放弃已有资源
  • 破坏“环路等待”条件
    • 源分类按顺序排列，各进程有序申请资源
  • 以上都有缺点

16. 避免死锁（动态预防）

允许进程动态申请资源，分配之前考察分配的安全性

银行家算法

  • 略

17. 死锁的检测和解除

  • 死锁预防需要限制资源的请求顺序。

  • 死锁避免需要限制资源的分配顺序。

  • 越早下手处理死锁问题，对机器的性能影响越大。因此，Unix这种追求快的系统，这两种都不采用，而是用的死锁检测和解除

死锁检测

参考

特别要注意，不要手动限制进程请求资源的顺序，再考虑解脱。这是无意识间用了死锁预防的策略，不是我们说的死锁解除。也就是说，死锁预防根本不会出现死锁，那么检测死锁时还采用限制请求的顺序，就是两个知识点混淆的表现。

死锁解除

  • 剥夺资源
  • 撤消进程