# 存储器的多层结构
在存储器层次中,层次越高(越靠近CPU),存储介质的访问速度越快,价格也越高,相对的存储容量也越小。
CPU寄存器和主存属于存储管理的范畴,掉电后它们的信息都不在存在,操作系统负责对这部分的分配和回收,以及提供在存储层次间数据移动的管理机制。而低层的辅存属于设备管理的范畴,它们存储的信息长期存在。
寄存器和主存储器又被称为可执行存储器,对于存放在其中的信息,与存放在辅存中的信息相比较而言,操作系统采用的访问机制和消耗的时间是不同的,进程可以在很少的时钟周期内使用一条load或store指令对执行存储器进行访问,但对辅存的访问则需要通过I/O设备来实现,因此,访问中将涉及到中断、设备驱动程序以及物理设备的运行。
# 程序的装入和链接
用户程序想要在系统中运行,必须先将它装入内存,然后再将其转变为一个可执行程序,通常需要以下几个步骤:
- 编译:由编译程序(Compiler)对用户源程序进行编译,形成若干个目标模块
- 链接:由链接程序(Linker)将编译后形成的一组目标模块以及它们所需要的库函数链接在一起,形成一个完整的装入模块
- 装入:由装入程序(Loader)将将入模块装入内存
# 程序的装入
- 绝对装入方式
程序使用的绝对地址由程序员直接赋予,程序中的相对地址(即逻辑地址)与实际内存地址完全相同,因此在程序装入时不需要对程序和数据的地址进行修改。缺点是要求程序员知道内存的使用情况,然而在多道程序设计的环境下,内存的使用是动态的,不可能在编写程序时就知道装入的地址,因此这种方式在多线程环境下不能够实现。
- 可重定位装入方式
程序的逻辑地址是从0开始的,因此在程序装入内存后,可以根据当前物理地址的起始位置推算出程序和数据的地址,即物理地址=逻辑地址+起始物理地址。
- 动态运行时的装入方式
可重定位装入方式不允许程序运行时在内存中移动位置,程序的移动表示它的物理地址发生了变化,此时必须对程序和数据的地址进行修改才能运行。程序可能被多次移动,在JVM中有对内存整理的情况,此时可以采用动态运行时装入方式。
该方式在把程序装入内存后,并不立即将程序的逻辑地址转换为物理地址,而是把这种地址转换推迟到程序真正要执行时进行,因此,装入内存后所有地址都是逻辑地址,这种方式需要重定位寄存器将逻辑地址转换为物理地址,重定位寄存器保存的是程序的起始位置,物理地址=重定位寄存器+逻辑地址。
# 程序的链接
源程序经过编译,可以得到一组目标模块,链接程序的功能就是将这组目标模块以及它们所需要的库函数装配成一个完整的装入模块,根据链接时间的不同可分为3种:
- 静态链接方式
在程序运行之前,将个目标模块及它们所需的库函数链接成一个完整的装配模块。主要分两个步骤
- 对相对地址进行修改,区别于装入时的逻辑地址修改
- 将符号引用改为直接引用
- 装入时动态链接
边装入边链接,即在装入一个目标模块时,若发生一个外部模块调用事件,将引起装入程序去找出相应的外部目标模块,并将它装入内存,这样的优点是能够实现对目标模块的共享。
- 运行时动态链接
这种方式将对某些模块的链接推迟到程序执行时才进行,在程序执行的过程中,当发现一个被调用模块尚未装入内存时,立即由OS去找到该模块,并将之装入内存,将其链接到调用者模块上,凡是没有在执行过程中未被用到的目标模块,都不会被调入内存和被链接到装入模块上,这样能够加快程序的装入过程,而且可以节省大量内存空间。
# 内存管理概念
操作系统作为系统资源的管理者,需要对内存进行管理,要管些什么呢?
负责内存空间的分配和回收
三个问题: 操作系统要怎么记录哪些内存区域已经被分配出去了,哪些地方是空闲的? 程序应该放在内存的哪个位置? 当进程运行结束之后,如何回收进程占用的内存空间?
操作系统需要提供虚拟技术从逻辑上对内存空间进行扩充
一个程序占60GB大小,但是电脑内存才4GB,操作系统是如何能够保证程序的运行的?
交换技术、虚拟存储技术
操作系统需要提供地址转换功能,负责程序的逻辑地址与物理地址的转换(三种装入方式)
操作系统需要提供内存保护功能,保证各进程在各自存储空间内运行,互不干扰
采用第三种程序装入方式时,可以采用重定位寄存器和界地址寄存器进行越界检查,重定位寄存器存放的是进程的起始物理地址,界地址寄存器存放的是进程的最大逻辑地址。
# 内存空间的分配和回收
根据是否连续分配分为两种:
连续分配:为用户进程分配的必须是一个连续的内存空间
非连续分配:为用户进程分配的可以是一些分散的内存空间
# 连续分配管理方式
# 单一连续分配
在这个分配方式中,内存被分为系统区和用户区。系统区通常位于内存的低地址部分,用于存放操作系统相关数据;用户区用于存放用户进程相关数据。内存中只能有一道用户程序,用户程序独占整个用户区空间。
缺点:只能用于单用户、单任务的操作系统中,有内部碎片,存储器利用率极低。
# 固定分区分配
为了能在内存中装入多道程序,且这些程序之间又不会互相干扰,将整个用户空间划分为若干个固定大小的分区,在每个分区中只装入一道作业,固定分区分配分为两种,一种是分区大小相等,第二种是分区大小不相等。
此种分配方式需要建立一个分区说明表,实现各个分区的分配与回收,表中记录对应区号、分区的大小、起始地址、状态。
优点:实现简单,无外部碎片
缺点:会产生内存碎片,内存利用率低。
# 动态分区分配
又称为可变分区分配。这种分配方式不会预先划分内存分区,而是在进程装入内存时,根据进程的大小动态建立分区,并使进程的大小动态地建立分区,并使分区的大小适合进程的需要。
3个问题
系统要用什么样的数据结构记录内存的使用情况?
空闲分区表:每个空闲分区对应一个表项,表项中包含分区号、分区大小、分区起始地址等
空闲分区链:每个分区的起始部分和末尾部分分别设置前后指针,起始部分还可记录分区大小等信息
如何进行分区的分配与回收操作?
分配:通过动态分区分配算法选择一个空闲的分区,同时更新空闲分区表
回收时有四种情况
回收区前后没有都没有相邻的空闲分区,新增一个表项 回收区前有一个相邻的空闲分区,两个相邻的空闲分区合并为一个 回收区前有一个相邻的空闲分区,两个相邻的空闲分区合并为一个 回收区前后都有相邻的空闲分区,三个相邻的空闲分区合并为一个
当很多个空闲分区都能够满足需求时,应该选择哪个分区进行分配?
将一个新作业装入内存时,需要按照一定的动态分区分配算法,从空闲分区表(或者空闲分区链)中选出一个分区分配给该作业。
动态分区分配没有内部碎片,但是有外部碎片。
内部碎片,分配给某进程的内存区域中,有些内存部分没有用上的区域就叫做内部碎片。 外部碎片,是指内存中的某些空闲分区由于太小而难以利用的部分。
可以通过紧凑(拼凑,也可叫压缩)技术来解决外部碎片,如果采用的是动态运行时的装入方式,这时只需要改变PCB寄存器中记录的进程的起始地址就好,其他两种程序装入方式都不能够移动程序。
动态分区分配算法
首次适应算法
空闲分区以地址递增的次序排列,每次分配内存是顺序查找空闲分区表/链,找到大小能够满足要求的第一个空闲分区。
算法倾向于利用低址部分的空闲分区,导致低址部分不断被划分,形成小的外部碎片,而每次都从低址寻找可用分区,会增大查找开销。
循环首次适应算法
首次适应算法的改进,每次从上一次分配空闲分区的下一个空闲空闲分区地方开始查找,这样能够避免首次适应算法的缺点,使得空闲分区分布得更均匀,从而减少了查找空闲分区的开销,但是会缺乏大的空闲分区。
最佳适应算法
将空闲分区按照其容量大小从小到大排列,然后寻找能够满足要求的、又是最小的空闲分区分配给作业,但这样每次分配空间之后所切割下来的剩余部分总是最小的,会存在许多难以利用的碎片。
最坏适应算法
将空闲分区按照其容量大小从大到小排列,然后挑选扫描整个空闲分区表,总是挑一个最大的空闲区分配给作业使用。
# 非连续分配管理方式
连续分配方式的缺点
- 固定分区分配:缺乏灵活性,会产生大量的内部碎片,内存利用率很低
- 动态分区分配:会产生很多外部碎片,虽然可以用“紧凑”技术来处理,但是“紧凑”的时间代价很高
如果允许将一个进程分散地装入到许多不相邻的分区中,便可充分地利用内存,而无需再进行“紧凑”,基于这个思想,产生了非连续分配方式,又称离散分配方式。
# 分页存储管理
分页存储管理将进程逻辑空间分为若干页,并为各页加以编号,从0开始。相应地,也把内存的物理地址空间分为大小相同的若干块,为进程分配内存时,以块为单位,将进程中的若干页分别装入到多个可以不相邻接的物理块中,由于最后一页经常装不满一块,因此会形成内部碎片。
在这个分页存储管理中,页面的大小应该适中,并且是2的幂次,如果页面太小,虽然这样可以减少内存碎片,但是页表的长度大大增加,占用大量内存,如果页面太大,会增加内存碎片大小。
页表
为了能够知道进程的每个页面在内存中存放的位置,操作系统要为每个进程建立一张页表,页表始址和长度通常存在PCB中。
如何通过页表实现逻辑地址到物理地址的转换?
如果要访问逻辑地址A,那么如何找到它的物理地址
- 确定逻辑地址A的页号P
- 通过页表找到页号P在内存中块号,块号记录了该块在物理内存的起始地址
- 确定逻辑地址A的页内偏移量
逻辑地址A对应的物理地址 = P号页面在内存中的起始地址 + 页面偏移量W
如何确定一个逻辑地址对应的页号、页内偏移量?
页号 = 逻辑地址 / 页面长度 (向下取整)
页内偏移量 = 逻辑地址 % 页面长度
前面说了页面大小一般是2的幂次,那么对于页面大小为 2k bit来说,假设计算机是32位的
将逻辑地址转为2进制:[页号:页内偏移量],前32-k位是页号,末尾k位是页内偏移量。
基本地址变换机构(内存管理单元MMU)
PCB中存放有页表的始址和长度,当进程被CPU调度时,将这两个数据存放在页表寄存器中,当遇到逻辑地址时,通过以下步骤将逻辑地址转换为物理地址
- 根据逻辑地址计算出页号、页内偏移量
- 判断是否越界,如果越界,产生越界中断
- 查询页表,找到页号对应的页表项,确定页面存放的内存块号
- 将内存块号和页内偏移量拼接起来得到物理地址
- 最后访问目标内存单元
局部性原理
时间局部性:如果执行了程序中的某条指令,那么不久后这条指令很有可能再次执行;如果某个数据被访问过,不久之后该数据很有可能再次被访问。(因为程序中存在大量循环)
空间局部性:一旦程序访问了某个存储单元,那不久之后,其附近的存储单元也很有可能被访问,典型的情况是程序的顺序执行。(很多数据在内存中都是连续存放的)
通过这个局部性原理,我们在操作系统中引入高速缓存能够大大提高程序的运行效率。
快表
快表,又称联想寄存器(TLB),是一种访问速度比内存快很多的高速缓存寄存器,用来存放当前访问的若干页表项,以加速地址变换的过程,与此对应,内存中的页表常称为慢表。
引入快表后,地址变换过程是这样的
- CPU给出逻辑地址,将页号与快表中的所有页号相比较
- 如果找到匹配的页号,说明要访问的页表项在快表中有副本,则直接从中取出该页对应的内存块号,在将内存块号与页内偏移量拼接形成物理地址,最后访问物理地址对应的内存单元
- 如果没有找到匹配的页号,则需要访问内存中的页表,找到对应的页表项,得到页面存放的内存块号,再将内存块号与页内偏移量拼接形成物理地址,最后访问该物理地址对应的内存单元。因此,若快表未命中,则访问某个逻辑地址需要两次访存(注意:在找到页表项后,应同时将其存入快表,以便后面可能的再次访问。但若快表已满,则必须按照一定的算法对旧的页表项进行替换)
如果快表命中,则减少一次访问主存的获取块号的操作,增加了效率。
两级页表
单级页表存在的问题
某计算机系统按字节寻址,支持 32 位的逻辑地址,采用分页存储管理,页面大小为4KB,页表项长度为 4B。
4KB=2^12B,因此页内地址要用12位表示,剩余20位表示页号。因此,该系统中用户进程最多有2^20页,相应的,一个进程的页表中,最多会有2^20个页表项,所以一个页表最大需要2^20*4B=2^22B,共需要2^22/2^12=2^10个页框存储该页表。
根据页号查询页表的方法:K 号页对应的页表项存放位置 = 页表始址 + K * 页表项大小(B),要在所有的页表项都连续存放的基础上才能用这种方法找到页表项。
根据局部性原理,很多时候,进程在一段时间内只需要访问某几个页面就可以正常运行了。因此没有必要让整个页表都常驻内存。
问题一:页表必须连续存放,因此当页表很大的时,需要占用很多连续的页框,但这和我们离散内存分配方式的思想冲突了
问题二:根据局部性原理,没有必要让整个页表常驻内存,进程在一段时间内可能只需要访问某几个特定的页面
问题一解决:将页表再分页并离散存储,然后再建立一张页表记录页表各个部分的存放位置,称为页目录表。
地址变换步骤:
- CPU拿到一个逻辑地址,按照地址结构将逻辑地址拆分成三部分
- 从PCB中读出页目录表始址,再根据一级页号查页目录表,找到下一级页表在内存中的存放位置
- 根据二级页号查二级页表,找到最终想访问的内存块号
- 结合页内偏移量得到物理地址
问题二:在二级页表的基础上可以进一步节省内存的使用,只有在需要访问某页面时才将页面调入内存(虚拟存储技术)
在一级页表增加一个标志位,标志页面是否已经加载入内存,如果页面不在,则产生缺页中断,将目标页面从外存调入内存。
# 分段存储管理
按照程序自身的逻辑关系划分为若干个段,每个段都有一个段名(在低级语言中,程序员使用段名来编程),每段从0开始编址。内存分配时以段为单位进行分配,每个段在内存中占据连续空间,但各段之间可以不相邻。
分段系统中逻辑地址结构由段号(段名)和段内地址(段内偏移量)所组成。
程序分多个段,各段离散地装入内存,为了保证程序能正常运行,就必须能从物理内存中找到各个逻辑段的存放位置。为此,需为每个进程建立一张段映射表,简称“段表”,段表由段号(隐含)、段长和基址组成。
假设段的最大长度为64KB,那么其段内地址就为2^16=65535bit=64KB
逻辑地址转变为物理地址的过程
- CPU拿到一个逻辑地址,根据逻辑地址得到段号、页内地址
- 判断段号是否越界,如果越界,产生越界中断
- 在内存中找到段表,根据段号找到对应的段表项
- 检查段内地址是否超过段长,如果超过,产生越界中断
- 段基址加段内地址得到物理地址
- 最后访问目标内存单元
与分页存储管理一样,也可以引入快表,将刚访问过的段表项加入快表,提高效率。
分段与分页管理的区别
- 页是信息的物理单位,分页主要目的是为了实现离散分配,提高内存利用率。段是信息的逻辑单位,分页的主要目的是更好地满足用户需求,一个段通常包含一组属于一个逻辑模块的信息。
- 页的大小固定,由系统决定。段长不固定,由用户编写的程序决定
- 分页的用户进程地址空间是一维的,分段是二维的,段号+段内地址
- 分段比分页更易实现信息的共享和保护。比如一个常量池,分段可以把它分在一个独立的段内,很方便共享,在多进程环境下也不会产生数据不一致的问题,而分页可能把这个常量池分在两个不同的页面,两个页面中可能也有不能够共享的代码,这时候不利于信息的共享和保护。
# 段页式存储管理
分页、分段存储管理的优缺点
优点 | 缺点 | |
---|---|---|
分页 | 内存空间利用率高,不会产生外部碎片,只有少量内部碎片 | 不方便按照逻辑模块实现信息的共享和保护 |
分段 | 很方便按照逻辑模块实现信息的共享和保护 | 如果段长过大,为其分配很大的连续空间会很不方便,段式管理会产生外部碎片 |
分段+分页的存储管理方式称为段页式管理,能够将分页、分段的优点结合起来。
将进程按照逻辑模块分段,再将各段分页,内存空间分为大小相同的内存块。
段表、页表
与分段管理不同,段页式的段表由段号(隐含)、页表长度、页表存放块号构成,页表还是由页号(隐含)、内存块号构成。
地址变换
逻辑地址分为三部分:段号、页号、页内偏移量
- 根据逻辑地址得到段号、页号、页内偏移量
- 判断段号是否越界
- 在内存中查找段表,找到该段对应的段表项
- 检查页号是否越界
- 根据段表项的页表存放块号找到页表存放位置,在内存中找到某段的页表,再找到页表项,得到内存块号
- 由内存块号+页内偏移量得到最后的物理地址
# 内存空间的扩充
# 交换技术
内存空间紧张时,系统将内存中某些进程暂时换出外存,把外存某些已具备运行条件的进程换入内存,涉及到的技术是中级调度(内存调度),就是要决定将哪个处于挂起状态的进程重新调入内存
问题
- 应该在外存的什么位置保存被换出的进程?
具有对换功能的操作系统中,通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件,主要追求存储空间的利用率,因此对文件区空间的管理采用离散分配方式;对换区空间只占磁盘空间的小部分,被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度,因此对换区空间的管理主要追求换入换出速度,因此通常对换区采用连续分配方式(学过文件管理章节后即可理解)。总之,对换区的I/O速度比文件区的更快。PCB会常驻内存,因为要记录进程在磁盘中的信息。
- 什么时候应该交换?
交换通常在许多进程运行且内存吃紧时进行,而系统负荷降低就暂停。例如:在发现许多进程运行时经常发生缺页,就说明内存紧张,此时可以换出一些进程;如果缺页率明显下降,就可以暂停换出。
- 应该换出哪些进程?
可优先换出阻塞进程;可换出优先级低的进程;为了防止优先级低的进程在被调入内存后很快又被换出,有的系统还会考虑进程在内存的驻留时间。
# 虚拟内存
传统存储管理方式有连续分配和非连续分配管理方式,它们有共同的特征和缺点
- 一次性:作业必须一次性全部装入内存后才能开始运行,这会造成两个问题:一是当作业很大时,不能够将作业全部装入内存,导致大作业无法运行,二是当大量作业要求运行时,由于内存无法容纳所有作业,因此只有少量作业能运行,导致多道程序并发度下降
- 驻留性:一旦作业被装入内存,就会一直驻留在内存中,直到作业运行结束。事实上,在一个时间段内,只需要访问作业的一小部分数据即可正常运行,这就导致了内存中会驻留大量的、暂时用不到的数据,浪费了宝贵的内存资源。
局部性原理
- 时间局部性:如果执行了程序中的某条指令,那么不久后这条指令很有可能再次执行;如果某个数据被访问过,不久之后该数据很可能再次被访问。(因为程序中存在大量的循环)
- 空间局部性:一旦程序访问了某个存储单元,在不久之后,其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的,程序的顺序执行,程序的指令是顺序地在内存中存放的)
高速缓冲技术的思想就是借助局部性原理的,高速缓冲技术的思想就是将近期会频繁访问到的数据放到更高速的存储器中,暂时用不到的数据放在更低速存储器中。
虚拟内存的定义和特征
虚拟内存基于一个点,就是应用程序在运行之前没有必要将其全部装入内存,而仅须将那些当前要运行的少数页面或段先装入内存便可运行,其余部分留在磁盘上。
在程序运行时,如果程序所要访问的页尚未调入内存,会发出缺页中断,此时OS将它们调入内存,以便进程能够继续执行下去,如果此时内存已满,无法再装入新的页,OS还需利用页面置换算法,将内存中暂时不用的页放到磁盘上,再将访问的页调入内存,使得程序能够继续执行。
综上所诉,在操作系统的管理下,在用户看来似乎有一个比实际内存大得多的内存,这就是虚拟内存。就是实际的物理内存没有变,只是在逻辑上进行了扩充。
虚拟内存的最大容量是由计算机的地址结构(寻址范围CPU)确定的 虚拟内存的实际容量=min(内存和外存容量之和,CPU寻址范围) 如:某计算机地址结构为32位,按字节编址(每个地址可以存放1byte数据),内存大小为512MB,外存大小为2GB。 则虚拟内存的最大容量为 2^32B = 4GB 虚拟内存的实际容量 = min (2^32 B, 512MB+2GB) = 2GB+512MB
三个特征
- 多次性:无需在作业运行时一次性全部装入内存,而是允许被分成多次调入内存。
- 对换性:在作业运行时无需一直常驻内存,而是允许在作业运行过程中,将作业换入、换出。
- 虚拟性:从逻辑上扩充了内存的容量,使用户看到的内存容量,远大于实际的容量
虚拟技术的实现
虚拟内存的实现需要建立在离散分配的内存管理方式基础上
- 请求分页存储管理
- 请求分段存储管理
- 请求段页式存储管理
与传统非连续存储管理的主要区别就是在程序执行过程中,当所访问的信息不在内存时,由操作系统负责将所需信息从外存调入内存,然后继续执行程序。若内存空间不够,由操作系统负责将内存中暂时用不到的信息换出到外存(页面置换算法)。以下以请求分页管理方式来说明虚拟内存的实现方式。
请求分页管理方式
页表机制
在请求分页系统中需要的主要数据结构是请求页表,其基本作用仍然是将用户地址空间中的逻辑地址映射为内存空间中的物理地址。
- 状态位:标记该页是否已调入内存
- 访问字段:用户记录本页在一段时间内被访问的次数,或记录本页最近已有多长时间未被访问,提供给置换算法在选择换出页面的参考
- 修改位:标志该页在调入内存后是否被修改过,由于内存中的每一页都在外存上保留一份副本,因此在置换该页时,如果没有被修改,就无需将该页写到外存上,若已被修改,则需要将该页重写到外存上,保证外存中保留的副本始终是最新的。
- 外存地址:用于指出该页在外存上的地址。
缺页中断机制
每当要访问的页面不在内存时,便产生一个缺页中断,然后由操作系统缺页中断处理程序处理中断,此时缺页的进程阻塞,放入阻塞队列,调页完成后再将其唤醒,放回就绪队列中。
如果内存中有空闲块,则为进程分配一个空闲块,将所缺页面装入该块,并修改页表中相应的页表项。
如果内存中没有空闲块,则由页面置换算法选择一个页面淘汰,若该页面在内存期间被修改过,则要将其写回外存。
地址变换机构
请求分页存储管理与基本分页存储管理的主要区别:
在程序执行过程中,当所访问的信息不存在内存,由操作系统将所需信息从外存调入内存,然后继续执行程序。
如内存不够,由操作系统负责将内存中暂时用不到的信息换出到外存
- 只有“写指令”才需要修改 “修改位”。并且,一般来说只需修改快表中的数据,只有要将快表项删除时才需要写回内存中的慢表。这样可以减少访存次数。
- 和普通的中断处理一样,缺页中断处理依然需要保留CPU现场。
- 页面调入内存后,需要修改慢表,同时也需要将表项复制到快表中。
页面置换算法
操作系统发现要使用的页面不在内存时,就会发生缺页中断由用户态转为内核态去磁盘把相应的页面加载到内存,如果此时内存空间不够,就要通过页面置换算法将一个页面移除内存。
- 最佳页面置换算法(OPT):淘汰以后最久不使用的页面,因为并不能预知页面在多长时间不被访问,因此这个算法不能够实现,一般用来衡量其他算法的办法。
- 先进先出页面置换算法(FIFO):总是先淘汰最先进入内存的页面
- 最近最少使用页面置换算法(LRU):淘汰最近最少使用的页面
- 最少使用页面置换算法(LFU):淘汰一个当前最少使用的页面