七、死锁

概念

死锁的特征（四个条件同时出现，死锁将会发生（必要条件））
- 互斥：一次只有一个进程可以使用一个资源
- 占有并等待：一个至少有一个资源的进程等待获得额外的由其他进程所持有的资源
- 不可抢占：一个资源只有当持有它的进程完成任务后，自由的释放
- 循环等待：等待资源的进程之间存在环{P0，P1，...,P0}
  - P0等待P1占有的资源，P1等待P2占有的资源,...,Pn-1等待Pn占有的资源，Pn等待P0占有的资源
处理死锁的方法
- 确保系统永远不会进入死锁
  - 死锁预防
  - 死锁避免
- 允许系统进入死锁状态，然后检测它并加以恢复
  - 死锁检测
  - 死锁恢复
- 忽略这个问题，假装系统中从未出现过死锁

如果图没有环，那么不会有死锁

如果图有环

如果每种资源类型只有一个实例，那么死锁发生

如果一种资源类型有多个实例，可能死锁

死锁预防

死锁避免

银行家算法

死锁检测和恢复

八、内存管理

连续分配方式会形成很多“碎片”，所以有了离散分配方式
内存管理有
- 分页内存管理
- 分段内存管理
- 段页式内存管理

分页内存管理

页
- 把物理地址空间分成大小固定的块，称为帧。
- 把逻辑内存也分为同样大小的块，称为页。
- 页面大小
  - CPU固定，过小=>页表过大
  - 过大=>页内碎片增大
页地址
- 页号：包含每个页在物理内存中的基址，用来作为页表的索引
- 页偏移：同基址相结合，用来确定送入内存设备的物理内存地址

32位即4Byte = 一条页地址记录

若逻辑地址空间是32位，也就产生了2³²个逻辑地址

页面大小=4KB=2¹²Byte（系统设定）

此时产生的页表有2²⁰条记录

页表大小=4B*2²⁰=4MB

页表
- 页表被保存在主存中
- 页表基址寄存器（PTBR）指向页表
- 页表限长寄存器（PRLR）表明页表的长度
- 在这个机制中，每一次的数据/指令存取需要两次内存存取，一次是存取页表，一次是存取数据/指令
- 解决两次存取的问题，是采用小但专用且快速的硬件缓冲，这种缓冲称为转换表缓冲器（TLB）或联想寄存器

页表结构

页表结构
- 例子：
  - 32位逻辑地址、页大小4KB
  - 一个页最多可包含100万个表项
  - 每个页表项4个字节，需要4MB空间放页表，1024个连续页面
  - 需要这么多个连续页面来存放页表不一定能实现
- 解决方法：
  - 层次页表
  - 哈希页表
  - 反向页表

层次页表

大多数计算机系统支持大逻辑地址空间（2的32到64的幂）。这种情况下，页表本身非常大。我们并不可能在内存中连续的分配这个表。一个简单方法是将页表划分为更小部分。
一种方法是使用两级分页算法，将页表在分页。以一个4kb页大小的32位系统为例。一个逻辑地址被分为20位的页码和12位的页偏移。因为要对页表进行再000分页，所以该页号可分为10位的页码和10位的页偏移。这样一个逻辑地址就表示如下形式：

是用来访问外部页表的索引，p2是外部页表的页偏移，采用这种结构地址转换方法如下图所示。由于地址转换由外向内，这种方案也称为向前映射页表。

哈希页表

处理超过32位地址空间的常用方法是使用哈希页表（hashed page table)，并以虚拟页码作为哈希值。哈希页表的每一条目都包括一个链表的元素，这些元素哈希成同一位置。每个元素有三个域：虚拟页码所映射的帧号指向链表中下一个元素的指针。

虚拟地址中的虚拟页号转换到哈希表中，用虚拟页号与链表中的每一个元素的第一个域相比较。如果匹配，那么相应的帧号就用来形成物理地址。如果不匹配，就对链表中的下一个节点进行比较，以寻找一个匹配的页号：

群集页表类似于哈希页表，对于稀疏地址空间很有用，稀疏地址空间的地址引用不连续，且分散在整个地址空间

反向页表

通常每个进程都有一个相关页表。每个页表有很多项。这可能消耗大量物理内存。为解决这个问题，可以使用反向页表。

内存扩充技术

解决方法（如何在较小的内存空间运行较大的进程）
- 紧缩
- 覆盖技术
- 交换技术
- 虚拟内存

http://blog.csdn.net/omenglishuixiang1234/article/details/51536771
http://blog.csdn.net/windowseight/article/details/8279863

7-8.死锁与分页