抢占时机是松弛度为0时
机制与策略分离 调度策略（Scheduling policy ）与
调度机制（ Scheduling mechanism）分离
调度机制位于内核，调度策略以参数化形式传递给内核，由用户进程决定
经典IPC问题 生产者-消费者问题 共享有界缓冲区问题 读者-写者问题 数据库访问模型 哲学家就餐问题 互斥访问有限资源
第三章存储管理P1
无存储器抽象 关键问题： 每个程序都使用私有的本地地址进行内存寻址，不知道其他程序的存在，不知道冲突或者不知道会不会冲突。
两个程序都引用了绝对物理地址，不能同时满足装入内存的起始地址，就会出现冲突 静态重定位：当一个程序被装载到16384地址时，所有的程序地址都加上常数16384 装载速度会变慢
装载器需要辨别地址和常数
把物理地址暴露给进程带来的问题 1.用户程序可以寻址内存中的每个字节，可能会故意或者无意的破坏操作系统或其他程序 2.实现程序的并发运行很困难，而并行是我们的需要
如何保证同时处于内存中的多个应用程序互不影响？ 需要解决2个问题：保护和重定位
地址空间 地址空间：一个进程可用于寻址内存的一套地址集合
每个进程都有一个自己的地址空间，独立于其他进程的地址空间
动态重定位：Base and Limit Registers 基址寄存器与界限寄存器 1.把每个进程的地址空间映射到物理内存的不同部分 2.CPU增加两个硬件寄存器
3.程序装载到内存中连续的空闲位置，装载时无需重定位
4.进程运行时，程序的起始物理地址装载到基址寄存器中，程序的长度装载到界限寄存器中
基址寄存器和界限寄存器为每个进程提供一个独立的地址空间
寄存器的值只有OS可以修改
每个内存地址送到内存前都需要先加上基址寄存器的内容；然后和界限寄存器的内容比较，检查地址是否越界
内存管理 操作系统必须跟踪内存使用情况，动态分配内存（以下是分配内存两种方式） 位图 内存被划分成若干个分配单元，每个分配单元对应位图中的一个位，例如0表示空闲，1表示占用 链表 维护一个记录已分配内存段和空闲内存段的链表，例如按地址顺序维护，链表中结点或者是一个进程占有的内存，或者是两个进程间的空闲区
链表的每个结点包含：空闲区（H）或进程（P）的标志，起始地址，长度和指向下一个结
点的指针 位图 1.提供了一种简单的利用一块固定大小的内存区就能对内存使用情况进行记录的方法
2.分配单元大小是一个重要设计因素，单元小，位图大；单元大，位图小，但可能会有浪费 3.但是分配内存时，必须查找指定长度的连续的0位串，耗时
链表 1.进程终止或者被换出时，操作比较容易，要么更改标志位（P变H），要么合并两个或者三个结点变成一个结点
课后习题：第3题 请比较用位图和链表两种方法来记录空闲内存所需的存储空间。128MB的内存以N字节为单元分配，对于链表，假设内存中数据段和空闲区交替排列，长度均为64KB。并假设链表中的每个节点需要32位的内存地址、16位长度和16位下一节点域。这两种方法分别需要多少字节的存储空间？哪种方法更好？ 位图 nbyte为分配单元
128*1024*1024byte/nbyte=227/n个位的位图 链表 数据段和空闲区交替出现，每个长度64kb，所以需要128*1024kb/64kb=2048个链表结点 一个链表结点需要32+16+16=64bit 链表所占空间2048*64bit=211*26=217
分配单元n为210=1K时，二者管理内存所需的空间相同
空闲内存管理 First fit 首次适配算法 沿着链表搜索，直到找到一个足够大的空闲区，要么刚好，要么将空闲区分成两部分，一部分分配给进程，一部分形成新的空闲区 Next fit下次适配算法 与首次适配算法类似，只是每次找到合适的空闲区时，记录下当时的位置，下次寻找空闲区从上次结束的地方开始搜索，不像首次适配算法每次都从头开始搜索 Best fit 最佳适配 搜索整个链表，找到能够容纳进程的最小的空闲区
结果是比首次适配算法和下次适配算法浪费更多的内存，因为它会产生大量的小空闲区 Worst fit 最差适配 为了防止最佳适配算法产生的小空闲区，总是分配最大的空闲区给进程
可以将进程链表和空闲区链表分开描述 将空闲表按空闲区大小排序
同时要维护两个链表（空间换时间）
申请空闲区，减少空闲表结点，增加进程表结点
释放进程，减少进程表结点，增加空闲表结点，可能需要合并空闲区 Quick fit 快速适配算法 单独维护一个常用大小的空闲区链表，例如4k，8k，12k等 也可能需要合并空闲区
内存超载问题 内存超载 进程所需的RAM数量总和通常远远超过存储器能够支持的范围
软件膨胀 存储器容量增长快速，软件大小的增长更快
单独一个程序超出内存的大小，同时系统必须支持多个程序同时运行 解决办法 交换技术 覆盖技术 虚拟内存
Swapping交换技术 把进程完整的调入内存，进程运行一段时间后，被存回磁盘（交换出去）
交换技术面临的问题？ 重新被换入时，要重新定位 产生多个空闲区，成为空洞hole
进程创建或换入时应该分配多大的内存？是固定的吗？ 为了减少因内存区域不够而引起的进程交换和移动所产生的开销，为进程多分配一些额外的内存，被换出时，只换出进程实际使用的内存中的内容
虚拟内存技术 实现用户的逻辑视图与操作系统所管理的物理视图分离
每个程序有自己的地址空间
地址空间分割成多个块，每个块称作一个页或页面 每个页有连续的地址范围 页被映射到物理内存
并不是所有的页都必须在内存中才能运行程序
1.程序引用在物理内存中的一部分地址空间，硬件立刻执行映射 2.程序引用不在物理内存中的一部分地址空间，操作系统负责将缺失的部分装入物理内存