Java基础 操作系统

操作系统读书笔记二

操作系统精髓与设计原理第八版

Posted by Cfeng on March 20, 2019

死锁

必要条件

  • 互斥：每个资源要么已经分配给了一个进程，要么就是可用的。
  • 占有和等待：已经得到了某个资源的进程可以再请求新的资源。
  • 不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
  • 环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

处理方法

鸵鸟策略

把头埋在沙子里，假装根本没发生问题。 因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。 当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。 大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

死锁检测与死锁恢复

  • 不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。

  1. 每种类型一个资源的死锁检测 每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。

  2. 每种类型多个资源的死锁检测 资源分配 上图中，有三个进程四个资源，每个数据代表的含义如下： E 向量：资源总量 A 向量：资源剩余量 C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量 R 矩阵：每个进程请求的资源数量 进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，让 P3 执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。P2 可以执行，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行，没有死锁。 算法总结如下： 每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。
    • 寻找一个没有标记的进程 Pi，它所请求的资源小于等于 A。
    • 如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A 中，标记该进程，并转回 1。
    • 如果没有这样一个进程，算法终止。
  3. 死锁恢复
    • 利用抢占恢复
    • 利用回滚恢复
    • 通过杀死进程恢复

死锁预防

  • 在程序运行之前预防发生死锁。
    1. 破坏互斥条件 不可能禁止
    2. 破坏占有和等待条件 一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。 两个低效性：
  • 进程可能被阻塞很长时间，以等待满足所有的资源请求
  • 先分配的资源可能很长一段时间不被使用
  1. 破坏不可抢占条件
    • 占有某些资源的一个进程进一步申请资源时若被拒绝，则该进程必须释放最初占有的资源
    • 一个进程请求当前被另一个进程占有的一个资源时，操作系统可以抢占另一个进程，要求释放资源
  2. 破坏环路等待 给资源统一编号，进程只能按编号顺序来请求资源。

死锁避免

  • 在程序运行时避免发生死锁。

  1. 安全状态 安全状态判断 图 a 的第二列 Has 表示已拥有的资源数，第三列 Max 表示总共需要的资源数，Free 表示还有可以使用的资源数。从图 a 开始出发，先让 B 拥有所需的所有资源（图 b），运行结束后释放 B，此时 Free 变为 5（图 c）；接着以同样的方式运行 C 和 A，使得所有进程都能成功运行，因此可以称图 a 所示的状态时安全的。 定义：如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。 安全状态的检测与死锁的检测类似，因为安全状态必须要求不能发生死锁。下面的银行家算法与死锁检测算法非常类似，可以结合着做参考对比。

  2. 单个资源的银行家算法 单个资源银行家 上图 c 为不安全状态，因此算法会拒绝之前的请求，从而避免进入图 c 中的状态。

  3. 多个资源的银行家算法 多个资源的银行家 上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。 检查一个状态是否安全的算法如下：

    • 查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
    • 假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。
    • 重复以上两步，直到所有进程都标记为终止，则状态时安全的。 如果一个状态不是安全的，需要拒绝进入这个状态。 ** **

      内存管理

      虚拟内存

      虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。

为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。 从上面的描述中可以看出，虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。例如有一台计算机可以产生 16 位地址，那么一个程序的地址空间范围是 0~64K。该计算机只有 32KB 的物理内存，虚拟内存技术允许该计算机运行一个 64K 大小的程序。 虚拟内存

分页系统地址映射

内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。

一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。

下图的页表存放着 16 个页，这 16 个页需要用 4 个比特位来进行索引定位。例如对于虚拟地址（0010 000000000100），前 4 位是存储页面号 2，读取表项内容为（110 1），页表项最后一位表示是否存在于内存中，1 表示存在。后 12 位存储偏移量。这个页对应的页框的地址为 （110 000000000100）。 分页系统

页面置换算法

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

页面置换算法和缓存淘汰策略类似，可以将内存看成磁盘的缓存。在缓存系统中，缓存的大小有限，当有新的缓存到达时，需要淘汰一部分已经存在的缓存，这样才有空间存放新的缓存数据。

页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。

  1. 最佳 OPT, Optimal replacement algorithm
    • 所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。
    • 是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。 OPT

  2. 最近最久未使用 LRU, Least Recently Used 虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。 为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。 LRU LRU算法的硬件支持 由于需要记录页面使用时间的先后关系，硬件开销太大。 硬件机构： 一个特殊的栈：把被访问的页面移到栈顶，于是栈底的是最久未使用页面。每个页面设立移位寄存器：被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。 LRU

  3. Clock置换算法 Clock算法也称最近未使用算法(NRU, Not Recently Used)或二次机会算法，它是LRU和FIFO的折衷。
    • 简易版： 每页有一个使用标志位A，若该页被访问则置A=1。 置换时采用一个指针，按照FIFO算法，寻找A=0的页面作为被置换页。若A=1，则重新将它置为0，暂不换出，给该页第二次驻留内存的机会。若所有页面都检查过，则回到开始位置重新检查。最后指针停留在被置换页的下一个页。
    • 改进版： 每个页有访问位A和修改位M，开始两个都为0，一旦访问该页，A置1，修改该页，则M置1。页面有四类： (1) A=0 M=0 最近即没使用、也没修改 (2) A=0 M=1 最近没使用、但已修改 (3) A=1 M=0 最近使用过、但没修改 (4) A=1 M=1 最近使用过、又修改过 找置换页面的过程分三步： （1）第1次找A=0 M=0 （不修改扫描过页面的访问位A），找到就为置换页； （2）找不到，第2轮扫描找A=0 M=1为置换页，同时将所有扫描过的页面的A置为0。 （3）若没找到，将指针返回起始位置，此时所有的A都为0。再按(1)方式找，若还找不到，再按（2）找，则定能找到。
  4. 先进先出 FIFO, First In First Out 选择换出的页面是最先进入的页面。 该算法会将那些经常被访问的页面也被换出，从而使缺页率升高。并且有Belady现象。 FIFO

    Belady现象

    • 一个进程P要访问M个页，OS分配N个内存页面给进程P；对一个访问序列S，发生缺页次数为PE（S,N）。当N增大时，PE(S, N)时而增大，时而减小。
    • 原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。

分段

虚拟内存采用的是分页技术，也就是将地址空间划分成固定大小的页，每一页再与内存进行映射。 一个编译器在编译过程中建立的多个表，表是动态增长的，如果使用分页系统的一维地址空间，动态增长的特点会导致覆盖问题的出现。 分段的做法是把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。

段页式

程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。

分页与分段的比较

  • 对程序员的透明性：分页透明，但是分段需要程序员显示划分每个段。
  • 地址空间的维度：分页是一维地址空间，分段是二维的。
  • 大小是否可以改变：页的大小不可变，段的大小可以动态改变。
  • 出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

设备管理

磁盘结构

  • 盘面（Platter）：一个磁盘有多个盘面；
  • 磁道（Track）：盘面上的圆形带状区域，一个盘面可以有多个磁道；
  • 扇区（Track Sector）：磁道上的一个弧段，一个磁道可以有多个扇区，它是最小的物理储存单位，目前主要有 512 bytes 与 4 K 两种大小；
  • 磁头（Head）：与盘面非常接近，能够将盘面上的磁场转换为电信号（读），或者将电信号转换为盘面的磁场（写）；
  • 制动手臂（Actuator arm）：用于在磁道之间移动磁头；
  • 主轴（Spindle）：使整个盘面转动。 磁盘结构

磁盘调度算法

读写一个磁盘块的时间的影响因素有：

  • 旋转时间（主轴转动盘面，使得磁头移动到适当的扇区上） 1/2r
  • 寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）
  • 实际的数据传输时间 b/(rN) 传送字节数/（旋转速度一个磁道的字节数） 转/秒

其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。

  1. 先来先服务 FCFS, First Come First Served 按照磁盘请求的顺序进行调度。 优点是公平和简单。缺点也很明显，因为未对寻道做任何优化，使平均寻道时间可能较长。

  2. 最短寻道时间优先 SSTF, Shortest Seek Time First 优先调度与当前磁头所在磁道距离最近的磁道。 虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。

  3. 电梯算法SCAN 电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。 电梯算法（扫描算法）和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。 因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题。

  4. C-SCAN 把扫描限定在一个方向上，当访问到沿某个方向的最后一个磁道时，磁头臂返回到磁盘相反方向末端的磁道，并再次开始扫描。 ** **

参考资料：

  • https://cyc2018.github.io/CS-Notes/#/notes/%E8%AE%A1%E7%AE%97%E6%9C%BA%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%20-%20%E7%9B%AE%E5%BD%951
  • 大话操作系统
  • 操作系统精髓与设计
CATALOG
    FEATURED TAGS
    数据结构 读书笔记 笔试 剑指Offer 算法 操作系统 Java基础 计算机网络 学习之路 Java SSM框架 每日leetcode Java巩固 spring cloud