第七章 内存管理
一、内存管理的功能
1.内存分配的三种基本形式
（1）直接指定方式——编写程序时确定地址
（2）静态分配方式——程序装入内存时确定地址
编译器编译的目标程序都采用从0开始的编址方式。
（3）动态分配方式——程序执行时确定地址
可以接受不可预测的分配和释放内存区域的请求，实现个别存储区域的分配和回收。
2.地址变换
（1）地址空间
程序编译后，从0开始，称为逻辑地址，其集合为地址空间。
由计算机体系结构决定，如16位地址范围64kb，32位地址范围4gb。
（2）存储空间
程序在主存中实际位置称为物理地址，其集合为存储空间。
大小由计算机的内存决定。
（3）地址转换
逻辑地址到物理地址的转换，又叫重定位。
3.存储保护
（1）地址保护
一个进程中的程序通常不能跳转到另一个进程的指令地址上去。
（2）权限保护
对于不同的进程有不同的存取权限。
4.存储共享
（1）允许每个进程访问该程序同一个副本
（2）让每个进程有自己单独的副本
5.存储扩充
（1）请求调入功能
把程序的一部分装入内存，使其先运行，在运行的过程中随时请求操作系统把需要的部分调入内存。
（2）置换功能
把不需要的部分换出主存，以装载需要的部分。（需要外存支持）
二、连续分配方式
1.单一连续分配
出现在单道程序系统中。
2.固定分区分配
（1）特点
- 操作系统初始化时把内存空间划分多个分区
- 运行时不改变，这种机制称为固定分区分配
（2）划分固定分区的两种方法
- 分区大小相同
- 分区大小不同
（3）优点：简单
缺点：内存利用率低，会产生很多内碎片
3.动态分区分配——按需分配
（1）特点
- 事先不划定大小
- 根据进程大小动态分配内存空间
（2）分配策略（重要）
- 首次适应算法：从链表的开头开始查找
- 下次适应算法：对首次适应算法的改动，从上次查找停止的位置开始查找
- 最佳适应算法：查找时间最长，产生最多外碎片
- 最坏适应算法：使用当前可用的最大分区
排序：首次>下次>最坏>最佳
三、交换和覆盖
四、基本分页分配方式
分区分配方式的缺点：
- 会遗留很多碎片
- 要求连续的较大的空间
当前操作系统全部采用基本分页分配方式。
1.页面相关概念
（1）页面：
分页存储管理是将作业的逻辑地址划分成一系列同等大小的部分，称为页。
每个作业的页的编号都是从0开始。
把可用的物理内存也划分成同样大小的连续的部分，称为块。
先有块，才有页。
（2）地址结构：
由页号和页内偏移量组成。
2^10=1K 2^11=2K 2^12=4K 2^20=1M
2.计算（重要）
（1）若逻辑地址A（十进制），页大小L
①页号p= INT（A/L)
②页内偏移w= (A mod L)
（2）若逻辑地址A（八/十六进制），页面大小为L
①先把逻辑地址A转换成二进制；
②计算页面大小L在地址结构中占的位数l；
③右侧数0 ~ l-1位为偏移量；
④右侧数第 l 位开始为页号。
（3）逻辑地址A转物理地址
若逻辑地址为十进制数，则用页号p=INT(A/页大小L), 页内偏移量w=AmodL，找页表块 号，
块号大小+偏移量=物理地址
若为八进制/十六进制，则转为二进制，然后根据页大小L从右往左取位数，取页内偏移量 和页号，找页表块号，
块号大小+偏移量=物理地址
3.页面大小
页数=文件大小/页面大小
页表文件大小=页数*块号大小
页表文件页数=页面大小/页表文件大小
（1）分页存储管理所造成的资源消耗
- 内存资源：页表需要保存在内存中，占用内存资源
- 运行性能：获取指令的过程中需要多次访问内存（至少2次！）
（2）把页表页看成普通的文件，对它进行离散的分配，即对页表再分页，由此形成多级页表 的思想。
（3）最优页面大小公式：
p=根号（2es）
页面大小p，每个页表项需要e字节，平均进程大小是s字节
五、基本分段分配方式
1.引入分段的必要性
逻辑上完整
动态增长
动态链接
信息共享
信息保护
2.地址变换机构
- 由逻辑地址得到段号，段内地址；
- 段号与段表寄存器中的段长度比较，检查是否越界；
- 由段表始址、段号找到对应段表项；
- 检查段表中记录的段长，检查段内地址是否越界（区分页表的一点）；
- 由段表中“基址+段内地址”得到最终的物理地址；
- 访问目标单元；
例题
在分段系统中，段表如下所示，请将逻辑地址（0，337），（1，5000），（2，3609），（5，1230）转换为物理地址。
段号 内存地址 段长
0 50K 10K
1 60K 3K
2 70K 5K
3 120K 8K
4 150K 4K
（1）段号0小于段表长5，段号合法；根据段表第0项可知段表的内存始址为50K，段长为10K；由于段内地址337小于段长10K，故段内地址也是合法的。因此可以得出对应物理地址为50K+337=51537；
（2）段号1小于段表长5，段号合法；根据段表第1项可知段表的内存始址为60K，段长为3K；经检查，段内地址5000超过段长3K，因此产生越界中断；
（3）段号2小于段表长5，段号合法；根据段表第2项可知段表的内存始址为70K，段长为5K；由于段内地址3609小于段长5K，故段内地址也是合法的。因此可以得出对应物理地址为70K+3609=75289；
（4）段号不合法，产生越界中断；
3.分页与分段的区别
- 页是信息的物理单位，段是信息的逻辑单位；
- 页是系统的，段是用户的；
- 页的大小是固定的，段的长度是不固定的；
- 分页的地址空间是一维的，分段的地址空间是二维的；
- 页存在内碎片，段存在外碎片。
第八章 虚拟存储管理
一、虚拟存储器
1.为什么需要虚拟存储器
(1) 用户地址空间可以大于物理内存空间
(2) 内存尽可能保存多个进程——提高并发性（提高CPU利用率）
2.虚拟存储器
通过请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统（基于程序局部性原理）
3.虚拟存储器的特点
- 多次性：一个进程的数据会多次装入内存
- 对换性：允许一个程序在运行过程中从内存换入和换出
- 虚拟性：未改变系统中内存物理的大小
4.需要解决的问题
地址映射、分配策略、置换策略、装载控制
二、请求页式分配
1.请求分页
在基本分页的基础上增加请求调页和页面置换功能的一种存储分配策略
(1) 在进程开始运行前，不是装入全部页面，而是装入几个页面
(2) 根据进程运行的需要，动态装入其他页
(3) 当内存空间已满，需要装入新页面，则需要置换算法淘汰某个页面
2.结构
3.缺页中断机构及特点
访问的页不在内存，产生一个缺页中断——状态位为0
缺页中断特点：
- 同样要经历中断步骤（硬件寄存器支持）
- 在指令执行期间产生
- 恢复执行被中断指令
4.内存分配策略
（1）内存分配要考虑的问题：
- 分配进程物理块少，内存中进程数越多，进程缺页可能性很高。
- 进程分配的物理块超过一定数目后，给该进程分配更多的物理块对该进程的缺页率没有影响。
（2）三种组合：
固定分配局部置换、可变分配局部置换、可变分配全局置换
（3）内存分配方法：
平均分配、按进程大小比例分配（bi=pi/p*m)、考虑优先级的分配算法
（4）影响缺页率的因素：
- 分配的物理块数
- 置换算法
- 数据访问顺序
5.页面置换算法
（1）最优页面置换算法——OPT
选择当前内存中最后一个用到的页并把它置换出去，往后推
（2）先进先出置换算法——FIFO
选择最早进入内存的那一页并把它置换出去
产生Belady异常（物理块多反而缺页率增加）
（3）最近最少使用置换算法——LRU
（4）时钟算法
某一页首次装入内存时，使用位u置为1，当被使用时也置为1；
指针扫描，当扫描到这个页面，置为0；
当扫描到一个u=0的物理块，这个物理块就被置换，指针继续移动一个格子。
（5）改进时钟算法
Clock只考虑了使用频率，未考虑是否修改。 故增加一个修改位w；
新装入页u=1，w=0； 找u=0，w=0 或 u=0，w=1的物理块替换
①扫描时不修改使用位，若找到u=0，w=0的，置换它；
②若未找到，再次扫描，找u=0，w=1的，置换它，并将期间遇到u=1的都置0
③若未找到，跳转①
6.段页式分配方法
（1）分页的优势
- 对程序员是透明的
- 消除外部碎片
- 大小固定相等，可开发出精致的存储管理算法
（2）分段的优势
- 具有处理不断增长的数据结构的能力
- 无内碎片
- 段共享及保护操作容易
- 支持动态链接
7.工作集模型
基本思想：
- 一个进程当前正在使用的页面的集合称为它的工作集
- 如果在内存中装入的是整个工作集，进程的运行就不会产生很多缺页
- 若分配给进程的物理块太少，无法容纳下整个工作集，进程的运行会产生大量的缺页
8.伙伴策略原理
在进程提出存储请求时，Linux并不一定按照请求的块数进行分配，而是将大于、等于这个数目的最小2^i个块数进行分配。
例如要求3个块，则分配2^2=4个块
（1）特点
- 允许内部碎片的存在
- 外部碎片非常少
- 从空间区队列表中搜索空闲块的速度极快
（2）分配和释放
内存可分配总量为1MB，请求和释放的序列为：A(100KB)→B(240KB)→C(64KB)→D(256KB)→B(240KB)→A(100KB)→E(75KB)→C(64KB)→E(75KB)→D(256KB)
第九章 设备管理（不考大题）
一、IO系统
1.设备的类别
（1）使用特性
（2）系统观点——数据传输率
低速设备——键盘、
中速设备——打印机
高速设备——磁带、磁盘、光盘
（3）按系统观点——传输单位
字符设备——不可寻址、I/O中断驱动和传输率相对较低
块设备——可寻址、一般为DMA方式
（4）按系统观点——共享属性
独占设备——如打印机、磁带机等顺序设备。作为系统资源，也称为临界资源
共享设备——如磁盘可随机访问随机设备
虚拟设备——通过虚拟技术将独占设备变换成可共享逻辑设备，供多个进程同时访问
（5）系统设备与用户设备
系统设备（标准设备）——一些通用设备；
如键盘、 打印机以及文件存储设备等
用户设备（非标准设备）——由用户自己安装配置后 ，由操作系统统一管理的设备；
如实时系统中的A/D 、D/A变换器、现场监控数码显示
2.设备标识
3 个原因:
①类型与数量多，赋予绝对设备号
② 并发性；编写程序时，不可能知道哪类哪台设备是可用的
③ 使用的方便性；I/O申请时，给出类型号、设备号（相对顺序），由系统进行“地址变换” （绝对设备号）
3.IO系统的结构
（1）总线结构
由于规模不同，系统结构不尽相同:
- 在微型计算机和小型计算机系统中大多采用了单总线 I/O系统结构
- 一些中、大型计算机系统中，往往具有专门进行I/O处理的通道（处理机），因而更多地采用了多总线多通道结构
（2）设备控制器
作用：
- 是CPU与IO设备之间的接口
- 根据主机发来的命令控制设备进行IO操作
功能：
- 接受命令并进行译码（控制寄存器）
- 进行数据交换（数据寄存器）
- 记录和报告设备状态（状态寄存器）
二、IO设备数据传输控制方式
1.程序直接控制方式——早期用户使用
①用户直接编写I/O指令程序控制输入输出
②要保持CPU与外设同步（由于速度差距）
（1）优点：CPU与外设通过状态信息得到同步，硬件简单。
（2）缺点：
- CPU不断读取状态寄存器信息，造成“忙等”。
- CPU只能与一台设备交换数据,不能实现设备之间的并行工作。
- 传输完全在CPU控制之下，对外部出现异常事件无实时响应能力。
(只适用于较简单的单片机系统）
2.中断控制方式——要求设备控制器应具备中断机构
中断驱动方式仅适合于中、慢速设备。对于大批量成组数据交换，可以利用DMA和通道方式
（1）基本工作过程：
① CPU执行设备驱动程序，向控制器发启动指令
② 控制器按照I/O指令要求，启动并控制I/O设备工作。CPU与外设是并行操作的。
③ 输入就绪/输出完成，控制器向CPU发中断信号。
④ CPU接中断信号，保护现场，转中断处理程序。
⑤ 中断处理程序完成后退出中断，恢复现场。
⑥ 将控制转回被打断的执行位置。
（2）优点：
- CPU与外设、外设与外设可以并行工作，提高系统效率
- 具有实时响应能力，可应用于实时控制场合
（3）弱点：
- 完成一次I/O要多次中断驱动
- 对各高速设备，或成组数据交换的问题——
- 一方面高速外设由于中断方式可能来不及响应而丢失数据
- 另一方面，成组数据交换多次地通过中断进行，也显得速度太慢
3.DMA控制方式
通道的引入：
- 一个DMA控制器只能挂接少量的同类设备
- 一次一块+且地址连续，若多个块，就需要多次启动DMA，因而也产生了多次中断处理
特点：
- 数据在内存和设备之间直接传送，CPU不干预。
- 一个数据块传输完，DMA向CPU发出一个中断请求。
- 数据的传输控制完全由DMA控制器完成，速度快， 适合高速成组数据传输。
- 数据块在传输过程中，CPU与外设并行工作，比中断控制方式的并行性高。
4.通道控制方式
特点：
- 一次可以实现多个离散数据块的传输。
- 可通过指令实现对设备控制，如磁带反绕等。
- 可以实现较为复杂的I/O控制。
三、设备管理
①用户不可能掌握每一种设备的具体控制与操作
②由于系统的并发性也不允许用户直接控制各个设备的启动与操作
1.设备管理的目标
(1) 设备独立性：提供通用、一致、规范的使用接口，做到用户应用程序与实际物理设备无关
(2) 提高系统整体效率：提高设备和CPU效率，如设备控制方式、缓冲技术
可利用分层方法实现IO管理软件
2.IO管理层次
（1）用户进程
（2）逻辑IO（独立于设备的软件）
（3）设备IO（设备驱动程序）
（4）中断控制程序（主机与IO设备接口）
3.IO 管理主要功能
(1) 记录设备信息
(2) 设备分配与再分配
(3) 实施IO操作
(4) 缓冲管理
四、缓冲
作用：
(1) 减少进程被阻塞的机会，以及设备和中断的次数
(2) 缓解对存储管理模块的干扰
(3) 缓解CPU和低速外设速度不匹配的矛盾，使数据处理速度提高
五、IO软件设计
IO 软件层次
(1) IO 中断处理设备
(2) IO 设备驱动程序
(3) 与设备无关的操作系统IO软件
(4) 用户层IO软件
六、磁盘存储器管理
扇区：IO传输和空间分配基本单位
1.改善磁盘IO速度
(1) 选硬件上性能指标高者
(2) 根据IO请求采用适合的磁盘调度算法
(3) 设置磁盘高速缓冲区
2.确定一个扇区需要三个参数
柱面号(磁道)、盘面号(磁头)和扇区号(三维地址物理形式)
对于数组A【i】【j】【k】
i=磁道，j=磁头，k=扇区
3.磁盘访问时间
寻道时间Ts=启动磁盘的时间S + 移动磁道n条*m（低速0.3，高速0.1）
旋转延迟时间Tr = 1 /（2r）
传输时间Td=每次读写的字节数b /旋转速度r*一条磁道上的字节数N
平均访问时间Ta=Ts + Tr + Td
4.磁盘调度算法（重点）
(1) FCFS/FIFO
优点：策略是公平的
缺点：大量进程访问者竞争一个磁盘，则性能接近于随机调度，性能很差
(2) SSTF 最短寻道时间优先
策略——选择当前位置移动距离最短I/O访问者
问题——每次选择距离最短者同时，忽略可能不断新I/O请求进程加入到队列 中，使队列中距离远访问者总也得不到调度，产生所谓“饥饿”现象
(3) SCAN
避免了饥饿现象。
由于这种算法使得磁臂移动规律颇似电梯的运动，因而也称为电梯算法
(4) CSCAN
磁头”单向”读/写运动
