东北大学操作系统总结 死锁.doc

Chapter 8：死锁 Deadlock characterization 死锁四个条件： Mutual exclusion Hold and wait No preemptive Circular wait 检测 资源分配图Resource allocation graph 没有环，no deadlock！ 有环，每个资源只有一个实例，deadlock！死锁。 预防 Mutual exclusion Hold and wait No preemptive Circular wait 避免 安全状态 找到安全状态——safe state Unsafe 也不一定死锁 两种算法： 资源分配图Resource allocation graph algorithm 每种资源只有一个实例。 银行家算法 Bankers algorithm 计算 恢复 Process termination Resource preemption 区别： 调度 starvation 死锁 starvation Chapter 9：内存管理 Overlays覆盖 Swapping 交换 MMU （memory management unit）内存管理单元 内存分配方式 内存必须容纳操作系统和多个用户程序。 连续内存分配 contiguous memory allocation 内存分为两个区域： 一个驻留操作系统，通常放在低内存之中（受中断向量interrupt vector位置影响）。 另一个用于用户进程，放在高内存中。 每个进程在存储中都获得一个单一连续的部分。 为了内存保护： 重定位寄存器 界限寄存器 Hole（孔） 计算 first-fit best-fit worst-fit（三个算法都会产生外部碎片） Fragmentation 碎片 外部碎片：总的内存之和可以满足请求，但并不连续。 内部碎片：进程分配的内存可能比所需要的要大一些。这两数字之差是内部碎片。这部分内存在分区内，不能使用。 减少外部碎片方法——缩紧 compaction： 条件：只有在relocation是dynamic的时候。 移动内存内容，将所有空闲内存合成一整块。 非连续内存分配 noncontiguous memory allocation 分页 分段（segmentation） 不产生外部碎片 Paging 分页 将内存分为相等大小的页（equal sized pages） Frames ：physical Pages ： logical Clusters 大小相等 Page table：存放每页的物理帧首地址。 Physical address = logical address + offset L addr = page number + offset P addr = frame number + offset 计算 地址题 Page table 小而快的寄存器；存在main memory 中；基表寄存器（PTBR)指向页表。 实现： TLB 翻译后备缓冲器 页表的一部分。 先在TLB中寻找，没有，则在page table中找。 高命中率——高效率 计算 hit rato 页表结构：层次划分页表 Hash页表 （地址空间32 bits) 反向页表 Shared page：代码共享，数据不共享。 段式 分为不同大小的段 计算 章末作业题！ Chapter 10 virtual memory虚拟内存 帧的分配 全局置换和局部置换的区别 Global replacement: 1、允许一个进程从所有帧的集合中选择一个置取帧，不管这个帧当前是否已分配给其他进程。 2、可以增加分配的帧的数量 3、不可以控制页错误率（fault rate) 4、更好的系统吞吐量 Greater system throughput. 常用！better choice！ Local replacement: 1、要求每个进程仅在自己的分配帧中进行选择。 2、不会增加分配帧的数量。 3、可以控制页错误率。 Thrashing 颠簸 Concept：进程在换页上的时间多于执行时间，这个进程在颠簸。 Cause：如果CPU利用率太低，（utilization too low）则引入新程序，以增加多道程序的度。采用全局置换算法，它会从其他进程中取帧。而其他进程也需要这些帧，所以会出现页错误。进程等待调页设备，CPU利用率会降低。从而引起进程的颠簸。 分配的帧数小于局部的大小，则它不能将经常使用的页放在内存中，进程会颠簸。 示意图。（多道程序的度，利用率）