操作系统基本原理---存储管理
存储管理
存储器是计算机系统中最重要的资源之一。因为任何程序和数据以及各种控制用的数据结构都必须占有一定的存储空间,因此,存储管理直接影响系统性能。
存储器由内存和外存组成。内存是由系统实际提供的存储单元(常指字节)组成的一个连续地址空间,处理器可直接存取。外存(辅存)是指软盘、硬盘、光盘和磁带等一些外部存储部件,常用来存放暂不执行的程序和数据。处理器不能直接访问外存,需通过启动 I/O(Input/Output,输入/输出)设备才能进行内存、外存交换,其访问速度慢,但价格便宜,常用作内存的后援设备。
内存大小由系统硬件决定,存储容量受到实际存储单元的限制。虚拟存储器(简称虚存)不考虑实际内存的大小和数据存取的实际地址,只考虑相互有关的数据之间的相对位置,其容量由计算机地址的位数决定。
系统中内存的使用一般分成两部分,一部分为系统空间,存放操作系统本身及相关的系统程序;另一部分为用户空间,存放用户的程序和数据。
存储管理主要是指对内存储器的管理,负责对内存的分配和回收、内存的保护和内存的扩充。存储管理的目的是尽量提高内存的使用效率。存储管理的机制经历了多次变迁,由以前的单一连续区管理到分区存储管理再发展为段页式管理。目前前两种技术已逐步被淘汰,下面我们将详细解读段页式存储管理。
1.页式存储管理
分页的基本思想是把程序的逻辑空间和内存的物理空间按照同样的大小划分成若干页面,并以页面为单位进行分配。在页式存储管理中,系统中虚地址是一个有序对(页号,位移)。系统为每一个进程建立一个页表,其内容包括进程的逻辑页号与物理页号的对应关系、状态等。
页式系统的动态地址转换是这样进行的:当进程运行时,其页表的首地址已在系统的动态地址转换机构中的基本地址寄存器中。执行的指令访问虚存地址(p,d)时,首先根据页号 p 查页表,由状态可知,这个页是否已经调入内存。若已调入内存,则得到该页的内存位置 p',然后,与页内相对位移 d 组合,得到物理地址 r。如果该页尚未调入内存,则产生缺页中断,以装入所需的页,如图 2-5 所示。
页式虚拟存储管理是在页式存储管理的基础上实现虚拟存储器的。首先把作业信息作为副本存放在磁盘上,作业执行时,把作业信息的部分页面装入内存储器,作业执行时若所访问的页面已在内存中,则按页式存储管理方式进行地址转换,得到欲访问的内存绝对地址,若欲访问的页面不在内存中,则产生一个“缺页中断”,由操作系统把当前所需的页面装入内存储器中。
为此,在装入作业时,就应在该作业的页表中指出哪些页已在内存储器中,哪些页还没有装入内存。可用一个标志位指示对应页是否在内存储器,可假设标志位为 1 表示该页在内存,而标志位为 0 表示该页尚未装入内存。为了能方便地从磁盘上找到作业信息的副本,故在页表中还可指出每一页副本在磁盘上的位置。
当要装入一个当前需要的页面时,如果内存储器中无空闲块,则可选择一个已在内存储器中的页面,把它暂时调出内存。若在执行中该页面被修改过,则把该页信息重新写回到磁盘上,否则不必重新写回磁盘。当一页被暂时调出内存后,让出的内存空间用来存放
当前需要使用的页面。以后再使用被调出的页面时,可用同样的方法调出另一个页面而将其再装入内存。页面被调出或装入之后都要对页表中的相应表目做修改。
当内存中无空闲块时,为了装入一个页面而必须按某种算法从已在内存的页中选择一页,将它暂时调出内存,让出内存空间以存放所需装入的页面,这个工作称为“页面调度”。如何选择调出的页面是很重要的,如果采用了一个不合适的算法,就会出现这样的现象:刚被调出的页面又立即要用,因而又要把它装入,而装入不久又被选中调出,调出不久又被装入,如此反复,使调度非常频繁。这种现象称为“抖动”。一个好的调度算法应减少或避免抖动现象。常用的页面调度算法有:
(1)最优(OPT)算法。选择不再使用或最远的将来才被使用的页,这是理想的算法,但是难以实现,常用于淘汰算法的比较。
(2)随机(RAND)算法。随机地选择被淘汰的页,开销小,但是可能选中立即就要访问的页。
(3)先进先出算法。选择在内存驻留时间最长的页似乎合理,但可能淘汰掉频繁使用的页。另外,使用 FIFO 算法时,在未给予进程分配足够的页面数时,有时会出现给予进程的页面数增多,缺页次数反而增加的异常现象。FIFO 算法简单,易实现。可以把装入内存储器的那些页的页号按进入的先后顺序排成队列,每次总是调出队首的页,当装入一个新页后,把新页的页号排到队尾。
(4)最近最少使用(Least Recently Used,LRU)算法。选择离当前时间最近的一段时间内使用得最少的页。这个算法的主要出发点是,如果某个页被访问了,则它可能马上就要被访问;反之,如果某个页长时间未被访问,则它在最近一段时间也不会被访问。
2.段式存储管理
段式存储管理与页式存储管理相似。分段的基本思想是把用户作业按逻辑意义上有完整意义的段来划分,并以段为单位作为内外存交换的空间尺度。
一个作业是由若干个具有逻辑意义的段(如主程序、子程序、数据段等)组成。分段系统中,容许程序(作业)占据内存中许多分离的分区。每个分区存储一个程序分段。这样,每个作业需要几对界限地址寄存器,判定访问地址是否越界也就更困难了。在分段存储系统中常常利用存储保护键实现存储保护。分段系统中虚地址是一个有序对(段号,位移)。系统为每个作业建立一个段表,其内容包括段号、段长、内存起始地址和状态等。状态指出这个段是否已调入内存,即内存起始地址指出这个段,状态指出这个段的访问权限。
分段系统的动态地址转换是这样进行的:进程执行时,其段表的首地址已在基本地址寄存器中,执行的指令访问虚存(s,d)(取指令或取操作数)时,首先根据段号 s 查段表,若段已经调入内存,则得到该段的内存起始地址,然后与段内相对地址(段内偏移量 d)相加,得到实地址。如果该段尚未调入内存,则产生缺段中断,以装入所需要的段。段式存储与页式存储的地址转换方式类似,参看图 1-6。
段式虚拟存储管理仍然以段式存储管理为基础,为用户提供比内存实际容量大的虚拟空间。段式虚拟存储管理把作业中的各个分段信息都保留在磁盘上,当作业可以投入执行时,做如下操作:
(1)首先把当前需要的一段或几段装入内存。
(2)作业执行时,如果要访问的段已经在内存,则按照“段式存储管理”中的方式进行地址转换;如果要访问的段不在内存中,则产生一个“缺段中断”,由操作系统把当前需要的段装入内存。
因此,在段表中应增设段是否在内存的标志以及各段在磁盘上的位置,已在内存中的段仍要指出该段在内存中的起始地址和占用内存区长度。
作业执行要访问的段时,由硬件的地址转换机构查段表。若该段在内存中,则立即把逻辑地址转换成绝对地址;若该段不在内存中,则形成“缺段中断”,由操作系统处理这个中断。
处理的办法是,查内存分配表,找出一个足够大的连续区以容纳该分段,如果找不到足够大的连续区则检查空闲区的总和,若空闲区总和能满足该段要求,那么进行适当移动将分散的空闲区集中;若空闲区总和不能满足该段要求,可把内存中的一段或几段调出,然后把当前要访问的段装入内存中。段被移动、调出和装入后都要对段表中的相应表目做修改。新的段被装入后应让作业重新执行被中断的指令,这时就能找到要访问的段,也可以继续执行下去。
3.段页式存储管理
段页式管理是段式和页式两种管理方法结合的产物,综合了段式组织与页式组织的特点,根据程序模块分段,段内再分页,内存被分划成定长的页。段页式系统中虚地址形式是(段号、页号、页内偏移),如图 2-6 所示。系统为每个进程建立一个段表,为每个段建立一个页表。段页式管理采用段式分配、页式使用的方法,便于动态连接和存储的动态分配。这种存储管理能提高内存空间的利用率。
段式虚拟管理还是以段为单位分配内存空间,整段的调出、装入,有时还要移动,这些都增加了系统的开销。如果按段页式存储管理的方式,把每一段再分成若干页面,那么,每一段不必占用连续的存储空间;甚至当内存块不够时,可只将一段中的部分页面装入内存,这种管理方式称为“段页式虚拟存储管理”。
段页式虚拟存储管理为每一个装入内存的作业建立一张段表,还要为每一段建立页表。段表中指出该段的页表存放位置及长度,页表中应指出该段的各页在磁盘上的位置以及页是否在内存中,若在内存中则填上占用的内存块号。作业执行时按段号查段表,找到相应的页表再根据页号查页表,由标志位判定该页是否已在内存,若是,则进行地址转换;否则进行页面调度。地址转换过程如图 2-7 所示。
段页式虚拟存储管理结合了段式和页式的优点,但增加了设置表格(段表、页表)和查表等开销,段页式虚拟存储器一般只在大型计算机系统中使用。