Chapter 7 死锁
死锁：是指多个进程因竞争系统资源或相互通信而造成的一种僵局，若无外力作用，这些进程都将永远不能向前推进
可剥夺资源：某进程获得这类资源后，该资源可以被其他进程或系统剥夺，如CPU，存储器
非剥夺资源：系统将这类资源分配给进程后，再不能强行收回，只能在进程使用完后主动释放。如打印机、读卡器 注：竞争可剥夺资源不会产生死锁。
永久性资源：可顺序重复使用的资源，如打印机
消耗性资源：由一个进程产生，被另一个进程使用短暂时间后便无用的资源，又称为临时性资源。如消息
注:竞争永久性资源和临时性资源都可能产生死锁
死锁产生的原因：竞争资源，进程推进顺序不当
死锁发生的条件：互斥，占有并等待，非抢占，循环等待（等待资源的进程间存在环）
通过资源分配图来观察进程是否发生死锁
如果资源分配图没有环，系统就没有进程死锁。如果分配图有环，那可能产生死锁
有死锁的资源分配图： 有环但没有死锁的资源分配图 图中P1占有R2的一个实例 可知P4释放资源后就不会死锁 P1申请并等待R1的一个实例
处理死锁的基本办法：忽略思索，预防死锁，避免死锁，检测死锁及解除 避免死锁：
1.打破占有并等待，要求进程在执行前一次申请全部的资源，或只有没有占有资源时才可以分配资源。导致资源利用率低，可能出现饥饿
2.破坏非抢占条件，如果一个进程占有资源并申请另一个不能立即分配的资源，那么其现已分配的资源都可被抢占。缺点：实现复杂，释放已获得资源可能造成前一段工作的失效，重复申请和释放资源会增加系统开销，降低系统吞吐量。该协议通常应用于状态可以保存和恢复的资源，如CPU寄存器、内存
3.破坏循环等待：有序资源分配法;将所有资源按类型排队，并赋予不同序号，要求进程均严格按照序号递增的次序请求资源，同类资源一次申请完。能保证没有死锁
安全状态：系统能按某种顺序如< P1、P2? 、Pn>来为每个进程分配其所需的资源，直至最大需求，使每个进程都可以顺利完成 < P1、P2、?、Pn >为安全序列
银行家算法：（举例）
T0时刻存在着一个安全序列< P1、P3、P4、P2、P0 >，故系统是安全的。
资源分配图简化判断是否死锁：找出一个既不阻塞又非孤立的进程结点pi，进程pi获得了它所需要的全部资源，能运行完成然后释放所有资源。如果能消去所有边，则不死锁
资源抢占来处理死锁：逐步从进程中抢占资源给其他进程使用，直到死锁环被打破为止。
选择一个牺牲：最小代价
回退：返回到安全状态，然后重新启动进程 饥饿：同一进程可能总是被选中
处理死锁的综合方法：将系统中的资源按层次分为若干类，对每一类资源使用最适合它的办法解决死锁问题。即使发生死锁，一个死锁环也只包含某一层次的资源，因此整个系统不会受控于死锁。
把资源分为：内部资源（有序资源分配法），主存资源（资源剥夺法），作业资源（可分配的设备和文件采用避免方法），交换空间（静态分配法）
对待死锁，一般应考虑死锁的预防、避免、检测和解除四个问题。典型的银行家算法是属于 避免 ，破坏环路等待条件是属于 预防 ，而剥夺资源是 解除 的基本方法
Chapter 8 内存管理
内存：即存储器、主存，分为两大部分：系统区，用户区
内存由很大一组字或字节组成，每个字或字节都有它们自己的地址
存储器管理的功能 存储空间的分配和回收
地址变换：将逻辑地址变换成物理地址
存储保护：防止因用户程序错误破坏系统或其他用户，防止程序之间的相互干扰 存储扩充：在逻辑上为用户提供一个比实际内存更大的存储空间
CPU能直接访问的存储器有：主存，高速缓存和寄存器
将程序装入内存有三种方式:绝对装入方式（编译时产生绝对地址的代码无需地址变换），可重定位装入方式（编译时产生相对地址的目标代码），动态运行时装入方式（执行时进行地址变换）
逻辑地址：由CPU产生的地址。用户编程时所用的地址，又称相对地址、虚地址 物理地址：内存单元所看到的地址。又称绝对地址，实地址 逻辑地址空间：逻辑地址的集合 物理地址空间：物理地址的集合
为了确保每个进程都有独立的内存空间。 基地址寄存器，界限地址寄存器 300040 120900
那么程序可以访问300040-420900的所有地址
内存管理单元（MMU， memory-management-unit）:运行时把虚拟地址映射到物理地址的设备。在MMU中，用户进程所产生的地址在送交内存前都将加上重定位寄存器的值
地址变换：将逻辑地址转换为物理地址。又称地址映射、重定位
地址变换分两类：静态地址变换（程序装入时一次完成不改变，需要连续存储空间，难共享），动态地址变换（在程序执行过程中，每次访问内存之前将要访问的地址转为内存地址，不需连续空间，可以实现虚拟存储）
动态加载：子程序只有调用时才被加载。优点：不用的子程序不会被加载 动态链接：链接被推迟到执行时期
存根：小段代码用来定位合适的内存驻留库程序
程序的链接：链接程序的功能是将经过编译或汇编后得到的目标模块以及所需的库函数装配成一个完整的装入模块
实现链接的三种方式：静态链接，装入时动态链接，运行时动态链接
静态链接：在程序运行之前，将各目标模块及其所需的库函数装配成一个完整的装入模块
装入时动态链接：源程序编译后所得到的目标模块在装入内存时边装入边链接。 运行时动态链接：将某些目标模块的链接推迟到执行时才进行。即在执行过程中，若发现一个被调用模块尚未装入内存时，由OS去找到该模块，将它装入内存并链接到调用者模块上。
覆盖技术：把一个大程序划分为一系列覆盖，每个覆盖是一个相对独立的程序单位。把程序执行时不要求同时装入内存的覆盖组成一组叫覆盖段。将一个覆盖段分配到同一个存储区中，这个存储区称为覆盖区。覆盖区的大小由覆盖段中最大的覆盖确定。
覆盖技术主要在早期系统使用，要求专业的程序员给出覆盖结构。
交换：进程可以暂时从内存中交换到备份存储上，当需要再次执行时再换回内存。（例如低优先级内存被换出，这样高优先级进程可以装入执行。这种交换又被称为滚出，滚入）
交换空间管理：交换空间设置在外存交换区，交换空间管理的主要目标是提高交换速度
交换空间采用连续分配方式，使用与动态分区分配类似的数据结构和分配算法 交换技术由操作系统自己完成
连续内存分配
内存通常分为两个区域：一个驻留操作系统，通常位于内存低端；一个驻留用户进程，通常位于内存高端
内存保护：防止一个进程有意无意的破坏系统或其他进程（内存访问不能越界） 常用的存储保护方法：界限寄存器法，存储保护键，环保护机制，访问权限 界限寄存器法：通过对每个进程设置一对界限寄存器（上下界寄存器或基址限长寄存器）来防止越界访问（如果越界则产生越界中断），达到存储保护的目的。 存储保护键：为每个存储块分配一个保护键，相当于一把锁；进入系统的每个作业赋予一个保护键，相当于一把钥匙。当作业运行时，检查钥匙和锁是否匹配，若二者匹配，则允许访问。否则发出保护性中断信号