操作系统快速入门笔记--4
最近效率不是特别高，写了点python的后台，看了看 面向对象，差点把这个坑给忘了！！今天赶紧补起来。
可变分区存储管理
按进程的内存需求来动态划分分区
创建一个进程时，根据进程所需空间量查看主存中是否有足够的空闲空间
- 若有，按需要量分割一个分区
- 若无，则令该进程等待主存资源
分区个数是随机变化的，因为分区大小按照进程实际需要量来确定。
可变分区方式的主存分配表分为已分配区表和未分配区表，采用链表形式存储。
可变分区主存分配表.png
可变分区方式的内存分配
- 最先适应分配算法
- 邻近适应分配算法
- 最优适应分配算法
- 最坏适应分配算法
地址转换与存储保护
硬件实现机制与动态重定位.png
可变分区方式的内存零头
固定分区方式会产生内存内零头
可变分区方式会随着进程的内存分配产生一些小的不可用的内存分区，这是内存外零头。
最优适配算法最易产生外零头。
任何设配算法都不能避免产生外零头。
移动技术（程序浮动技术）
移动分区可以解决内存外零头。这需要动态重定位的支撑。
移动技术.png
移动技术的工作流程.png
下面是页式存储管理的内容
页式存储管理的基本原理
分页存储器将主存划分成多个大小相等的页架。
受页架尺寸限制，程序的逻辑地址自然分成页。
不同的页可以放在不同页架中，不需要连续。
页表用于维系进程的主存完整性。
页式存储管理中的地址
逻辑地址：页号和单元号。
物理地址：页架号和单元号。
地址转换可通过查页架表实现
地址转换.png
页式存储管理的内存分配/去配
可用一张位示图来记录主存分配情况
建立进程页表维护主存逻辑完整性。
位示图.png
页的共享
页式存储管理能够实现多个进程共享程序和数据。
数据共享：不同进程可以使用不同页号共享数据项
程序共享：不同进程必须使用相同页号共享代码页
（共享代码页中的(JMP <页内地址>)指令，使用不同页号做不到）
页式存储管理的地址转换代价
页表放在主存内，每次地址转换必须访问两次主存。
- 按页号读出页表中的相应页架号
- 按计算处来的绝对地址进行读写
需要用Cache存放部分页表来提高存取速度。
页式存储管理的块表
设置专用的高速存储器快表，存放页表的一部分。
快表表项：页号，页架号。
按照内容寻址，而不是按照地址访问。
引入块表后，可以加快地址转换速度。
假定主存访问时间为200毫微秒，快表访问时间为40毫微秒，查快表的命中率是90%，平均地址转换代价为(200+40)90%+(200+200)10%=256毫微秒
比访问两次主存的400毫微秒下降了36%
基于快表的地址转换流程
按逻辑地址中的页号查找快表。
若该页已在快表中，则由页架号和单元号形成绝对地址。
若该页不在快表中，则再查主存页表形成绝对地址，同时将该页登记到快表中。
当快表填满后，又要登记新页时，需要在快表中按照一定策略淘汰一个旧登记项
多道程序环境下的进程表
进程表中登记了每个进程的页表
进程占有处理器运行时，其页表起始地址和长度送入页表控制寄存器。
多道程序环境下的地址转换
下面就进入虚拟存储管理的内容
页式虚拟存储管理的基本思想
把进程全部页面装入虚拟存储器，执行时先把部分页面装入实际内存，然后根据执行行为，动态调入不在主存的页，同时进行必要的页面调出。（这是现代OS主流存储管理技术）
首次只把进程第一页信息装入主存，成为请求页式存储管理。
页式虚拟存储管理的页表
需要指出每页的虚拟地址，实际地址。
主存驻留标志，写回标志，保护标志，引用标志，可移动标志。
页式虚拟存储管理的实现
CPU处理地址
- 若页驻留，则获得块号形成绝对地址
- 若页不在内存中，则CPU发出缺页中断
OS处理缺页中断
- 若有空闲页架，则根据辅存地址调入页，更新页表和快表等。
- 若无空闲页架，则决定淘汰页，调出已修改页，调入页，更新页表与快表。
页式存储管理的地址转换
页式虚拟存储管理的地址转换--硬件部分.png
操作系统部分.png
页面调度
当主存空间已满而又需要装入新页时，页式虚拟存储管理必须按照一定的算法把已在主存的一些页调出去。
选择淘汰页的工作称为页面调度
选择淘汰页的算法称为页面调度算法
页面调度算法设计不当会出现淘汰的界面立即又要调入，并如此反复的现象（抖动&颠簸）
缺页中断率
假定进程P共n页，系统分配页架数m个
P运行中成功访问次数为S，不成功访问次数为F，总访问次数A=S+F
缺页中断率定义为：f=F/A
缺页中断率是衡量存储管理性能和用户编程水平的重要依据
影响缺页中断率的因素
分配给进程的页架数：可用页架数越多，缺页的中断率越低
页面的大小：页面尺寸越大，中断率越低
用户程序的编制方法：在大数据量情况下，对缺页中断率也有很大影响（要注意到局部性）
OPT页面调度算法
理想的调度算法是：当要调入新页面时，首先淘汰以后不再访问的页，然后选择距现在最长时间后再访问的页
该算法由Beladyᨀ出，称Belady算法，又称最佳算法（OPT）
OPT只可以模拟，不可以实现
先进先出FIFO页面调度算法
总是淘汰最先调入主存的那一页，或者说主存驻留时间最长的那一页（常驻的除外）
模拟的是程序执行的顺序性，有一定的合理性
最近最少用LRU页面调度算法
淘汰最近一段时间较久未被访问的那一页，即那些刚被使用过的页面可能马上还要被使用到。
模拟了程序执行的局部属性，既考虑了循环性又兼顾了顺序性。
实现的代价大（需要维护一个特殊队列）
LRU的算法实现
每页建一个引用标志，供硬件使用
设置一个时间间隔中断：中断时页引用标志置为0
地址转换时，页引用标志置为1
淘汰页面时，从页引用标志为0的页中随机选择
时间间隔多长是个难点
最不常用LFU页面调度算法
淘汰最近一段时间内访问次数较少的页面，对OPT模拟性比LRU更好
基于时间间隔中断，并给每一页设置一个计数器
时间间隔中断发生后，所有计数器清0
每访问页1次就给计数器加1
选择计数值最小的页面淘汰
时钟CLOCK页面调度算法
采用循环队列机制构造页面队列，形成了一个类似于时钟表面的环形表。
队列指针相当于钟表上的表针，指向可能要淘汰的页面。
使用页引用标志位。
- 页面调入主存时，其引用标志位置1
- 访问主存页面时，其引用标志位置1
- 淘汰页面时，从指针当前指向的页面开始扫描循环队列
- 把所遇到的引用标志位是1的页面的引用标志位清0，并跳过
- 把所遇到的引用标识位是0的页面淘汰，指针推进一步。
反置页表的提出
页表及相关硬件机制在地址转换、存储保护、虚拟地址访问中发挥了关键作用
为页式存储管理设置专门硬件机构
内存管理单元MMU：CPU管理虚拟/物理存储器的控制线路，把虚拟地址映射为物理地址，并提供存储保护，必要时确定淘汰页面
反置页表IPT：MMU用的数据结构
反置页表的基本设计思想
针对内存中的每个页架建立一个页表，按照块号排序。
表项包含：正在访问该页框的进程标识、页号及特征位，和哈希链指针等
用来完成内存页架到访问进程页号的对应，即物理地址到逻辑地址的转换
基于反置页表的地址转换过程
- MMU通过哈希表把进程标识和虚页号转换成一个哈希值，指向IPT的一个表目
- MMU遍历哈希链找到所需进程的虚页号，该项的索引就是页架号，通过拼接位移便可生成物理地址
-
若遍历整个反置页表中未能找到匹配页表项，说明该页不在内存，产生缺页中段，请求操作系统调入
反置页表下的地址转换.png
下面是段式存储管理的内容
段式程序设计
每个程序可由若干段组成，每一段都可以从“0”开始编址，段内的地址是连续的。
分段存储器的逻辑地址由两部分组成：
段号+单元号
是自己设计的，用户可控，编程可见。
程序的分段结构.png
段式存储管理的基本思想
段式存储管理基于可变分区存储管理实现。
一个进程要占用多个分区。
硬件需要增加一组用户可见的段地址寄存器（代码段、数据段、堆栈段，附加段），供地址转换使用、
存储管理需要增加设置一个段表，每个段占用一个段表项，包括：段始址、段限长，以及存储保护、可移动、可扩充等标志位。
段式存储管理的地址转换流程
段式存储管理的地址转换流程.png
段的共享
通过不同进程段表中的项指向同一个段基址实现。
对共享段的信息必须进行保护。如：规定只能读出不能写入，若不满足条件则产生保护中断。
段式虚拟存储管理的基本思想
把进程的所有分段都存放在辅存中，进程运行时先把当前需要的一段或几段装入主存，在执行过程中访问到不再主存的段时再把他们动态装入。
段式虚拟存储管理中段的调进调出是由OS自动实现的，对用户透明
与段覆盖技术不同，它是用户控制的主存扩充技术，OS不感知。
段表扩充.png
段式虚拟存储管理的地址转换
段式虚拟存储管理的地址转换.png
最后是段页式存储管理！！！（哇终于要整理完了）
段页式存储管理的基本思想
段式存储管理可以基于页式存储管理实现
每一段不必占据连续的存储空间，可存放在不连续的主存页架中
能够扩充为段页式虚拟存储管理
装入部分段，或者装入段中部分页面
段表和页表.png
地址转换
段页式地址转换.png
虚拟存储管理的地址转换
段页式虚拟存储管理的地址转换.png
搞定！！！下一节将学习设备管理。
