l 区分逻辑地址与绝对地址
绝对地址:主存储器以字节为编址单位,容量为n的主存储器中,每个单元有唯一的编号,从0到n-1,这个唯一的编号就是主存储器的物理地址也叫绝对地址。
逻辑地址:在多道程序设计的系统中,操作系统为了方便用户,就允许每个用户都认为自己作业的程序和数据存放在地址从 0开始的连续空间中。这样用户程序中使用的地址就是逻辑地址也叫相对地址。
l 对主存储器为什么要区分绝对地址和逻辑地址?
中央处理器访问主存时必须指定确切的存储单元。在计算机系统中通常对主存储器以字节(每个字节8个二进制位)为编址单位,每个字节都有一个地址与其对应,这样的地址称为主存储器的“绝对地址”。
在多道程序设计系统中,主存中同时存放了多个用户作业。操作系统根据主存的使用情况为用户分配主存空间。每个用户不能预先知道他的作业将被存放到主存储器的什么地方。这样,用户程序中就不能使用主存的绝对地址。为了方便用户,允许用户程序中使用“逻辑地址”,每个用户都可认为自己作业的程序和资料存放在一组从“0”地址开始的连续的逻辑地址空间中。
l 重定位
为了保证作业的正确执行,必须根据分配给作业的主存区域对作业中指令和数据的存放进行重定位,这种把逻辑地址转换成绝对地址的工作称为“重定位”或“地址转换”。重定位的方式有“静态重定位”和“动态重定位”两种。
(1)静态重定位
在装入一个作业时,把作业中的指令地址和数据地址全部转换成绝对地址。这种转换工作是在作业开始前集中完成的,在作业执行过程中无需再进行地址转换。所以称为“静态重定位”。图4_2.1指出了静态重定位的过程。
在图4-2.l中,假定用户作业的逻辑地址空间从“0”到“124”,其中第8号单元处有一条“加法”指令,该指令要求从第32号单元处取出操作数3465,然后进行加法操作。如果存储管理为该作业分配的主存区域是从100单元开始,那么,逻辑地址第8号单元在主存中的对应位置是108单元,第32号单元在主存中的对应位置应该是132单元。如果不修改上述“加法”指令中的操作数地址,则处理器执行该指令时将从主存的032单元中去取操作数,这显然是错误的。于是,应把程序中所有逻辑地址都转换成绝对地址。上述加法指令中的操作数地址也应改成132。这样,在执行指令时便可从132单元取到正确的操作数。
(2)动态重定位
在装入一个作业时,不进行地址转换,而是直接把作业装到分配的主存区域中。在作业执行过程中,每当执行一条指令时都由硬件的地址转换机构转换成绝对地址。这种方式的地址转换是在作业执行时动态完成的,所以称为动态重定位。图4_2.2指出了动态重定位的过程。
在图4-2.2中,基址寄存器中存放了作业所在主存区域的起始地址100。当处理器从108单元取出指令后,该指令中的逻辑地址是032,把基址寄存器中的值100与逻辑地址032相加得到绝对地址132,处理器便可从132单元中取出正确的操作数。
点击见相关动画
l 什么是“程序浮动”?为什么动态重定位能支持程序浮动?
若在作业的执行过程中改变了该作业在主存中的存放区域后,该作业仍然能正确执行,则称该作业的程序是可浮动的。采用动态重定位的系统能支持“程序浮动”。这是因为动态重定位是在每执行一条指令时进行地址转换的。当作业在主存中的位置被移动后,只要把新区域的起始地址存入基址寄存器中,作业继续执行时硬件的地址转换机构就会按基址寄存器中新存入的地址与逻辑地址相加,所得的绝对地址就是新区域中的存储单元地址,作业当然仍可正确执行。
第三节 分区存储管理
l 什么是分区存储管理?
分区存储管理是把存储器中的用户区作为一个连续区或分成若干连续区进行管理。早先使用一个分区的存储管理,后发展成多分区的存储管理。多个分区的管理可采用固定分区方式和可变分区方式。
l 一个分区的存储管理
(1) 一个分区的存储管理
又称单连续存储管理,是最简单的存储管理方式。除操作系统占用的一部分存储空间外,其余的用户区域作为一个连续的分区分配给一个作业使用,即在任何时刻主存储器中最多只有一个作业。一个分区的存储管理只适用于单用户的情况。
(2) 一个分区的存储管理方法
处理器中设置一个界限寄存器,寄存器的内容为当前可供用户使用的主存区域的起始地址。只当操作系统的功能扩充或修改时改变了所占区的长度,才更改界限寄存器的内容。
等待装入主存储器的作业排成一个作业队列。当主存储器中无作业或一个作业执行结束;就可以让作业队列中的一个作业装入主存储器。如图4_3.1所示。
l 固定分区存储管理
(1) 固定分区
固定分区是指把主存储器中可分配的用户区域预先划分成若干个连续区。每个连续区的大小可以相同,也可以不同。但是一旦划分好分区之后,主存储器中分区的个数就固定了,且每个分区的大小也固定不能再变。
(2) 固定分区存储管理的原理
在固定分区方式管理下,每个分区可用来装入一个作业。由于主存中有多个分区,可同时在每个分区中装人一个作业,故适用于多道程序设计系统。
等待进人主存的作业排成队列。当主存储器中有空闲的分区时,依次从作业队列中选择一个能装入该分区的作业。当所有的分区都装有作业,就暂停装入其它作业。已经装入主存的作业能得到处理器运行时,应限定它只能在所占的分区中执行。当作业执行结束后,收回该作业所占的分区。收回的分区可用来装入新的作业。
图4_3.2是划分成三个分区的固定分区管理方式的示意图。
(3) 主存空间的分配与去配
设置一张“主存分配表”,以说明各分区的分配情况。主存分配表中应指出各分区的起始地址和长度,并为每个分区设一个标志位。当标志位为“0”时,表示对应的分区是空闲分区,当标志位为非“0”时,表示对应的分区已被占用。空闲分区可以用来装作业,已被占用的分区需指出被哪个作业占用。
用“顺序分配算法”进行主存空间的分配。顺序查看主存分配表,找到一个标志为“0”的分区,再把欲装入作业的逻辑地址空间的长度与找到的分区长度进行比较。当能容纳该作业时,则把此分区分配给该作业,把它的作业名填到占用标志位上。当找到的分区不能容纳该作业时,则重复上述过程继续顺序查看主存分配表中是否有能满足该作业长度要求的且标志为“0”的分区,若有,则分配,若无,则该作业暂时得不到主存空间而不能装入。
(4) 地址转换
固定分区管理可采用静态重定位的方式装入作业。装入程序把作业中的逻辑地址转换为绝对地址与分区的下限地址相加,得到相应的绝对地址。
(5)
存储保护
实现存储保护需要软件与硬件相互配合。采用固定分区方式管理时,处理器中应设置两个寄存器:下限寄存器和上限寄存器。
当一个被装入分区的作业能占用处理器时,由操作系统把该分区的上限地址和下限地址分别存入处理器的上限寄存器和下限寄存器之中。处理器执行该作业时,对每条指令中的地址都要核对绝对地址是否在上下限地址之间,即核对
“下限地址<绝对地址<上限地址”
是否成立。若成立,表示绝对地址在规定的分区之内,可按绝对地址访问主存,否则便形成“地址越界”的程序性中断事件。从而达到存储保护的目的。
当一个作业让出处理器时,另一作业可能被选中占用处理器。这时应更改上、下限寄存器的内容为当前被选中作业所在分区的上限地址和下限地址,以保证处理器能控制每个作业都在规定的分区内执行。
(6) 固定分区管理方式不能充分利用主存空间
采用固定分区方式管理主存时,规定每个分区只能装入一个作业,且总是要为作业分配一个不小于作业长度的分区。这样就有可能造成很多作业实际上只占用了分区的一部分空间,使分区中有一部分空间不能被利用,影响了主存空间的利用率。
(7) 固定分区管理方式提高主存空间利用率的办法
1)分区按大小顺序排列,这样可以使作业总是先使用满足要求的最小分区。
2)根据经常出现的作业大小和频率划分分区。
3)按作业对主存空间的需求量排成多个队列,规定队列与分区的对应关系。也就是说多大的作业只能放在多大的分区里,就算有更大的分区空着,也不许他进入。
l 可变分区的管理
可变就是指分区的大小和位置不是固定的,而是根据作业要求的主存量来分配分区的大小。
图4_3.3是可变分区管理方式的存储空间分配示意图。
(1)主存的分配和去配
在系统初始化时,主存除了操作系统所占部分外,整个用户区是一个大的空闲区,可以按作业需要的空间大小顺序分配空闲区直到不够时为止。
当作业结束时,它的占用分区被收回。这个空闲区又可以根据新作业的大小重新用于分配,所以主存中的已占分区和空闲区的数目和大小都是在变化的。可以用两张表“已分配区表”和“空闲区表”来记录和管理。
例如,某主存容量为2560K(1K为1024字节),其中操作系统占用400K,现依次有五个作业J1,J2,J3,J4,J5要求装入主存,它们对主存的需求量分别是600K,1000K,300K,700K,500K。图4_3.4指出了作业被装入、执行结束后撤离的主存空间分配情况。
图4_3.5是可变分区管理方式的主存分配表,表中内容是按图4_3.4(b)的情况填写的。
(2)常用的分配算法
最先适应分配算法:空闲区按地址顺序由小到大登记在空闲区表中,在分区表中顺序查找,找到够大的空闲区就分配。但是这样的分配算法可能形成许多不连续的空闲区,造成许多“碎片”,使主存空间利用率降低。 点击见相关动画
最优适应分配算法:这种算法总是挑选一个能满足作业要求的最小空闲区。
点击见相关动画
在实现这种算法时,可把空闲区按长度以速增顺序登记在空闲区表中。分配时顺序查找空闲区表,由于查找时每次总是从最小的一个区开始,同时要不断调整空闲区表,每当收回一个分区,必须把收回后的分区按长度顺序插入登记到空闲区表的适当位置。
但是这种算法可能形成一些极小的空闲区,以致无法使用,这也会影响主存利用率。
最坏适应分配算法:这种算法总是挑一个最大的空闲区分给作业使用,使剩下的空间不至于太小。空闲区按长度以递减顺序登记在空闲区表中。
收回主存空间:收回主存空间时,应检查是否有与归还区相邻的空闲区。若有,则应合并成一个空闲区登记。
一个归还区可能有上邻空闲区,也可以有下邻空闲区,或既有上邻又有下邻空闲区,或既无上邻又无下邻空闲区。在实现去配时应顺序检查空闲区表中标志为“未分配”的栏目,以确定是否有相邻空闲区。四种情形如图4_3.6所示。
假定作业归还的分区始址为s,长度为L,则:
(1)归还区有下邻空闲区。如果S+L正好等于空闲区表中某个登记栏目(假定为第j栏)所示分区的始址,则表明归还区有一个下邻空闲区。这时修改第j栏登记项的内容:
始址:=S
长度:=原长度+L
则第j栏指示的空闲区是归还区与下邻空闲区合并后的一个大空闲区。
(2)归还区有上邻空闲区。如果空闲区表中第j个登记栏中的“始址+长度”正好等于s,则表明归还区有一个上邻空闲区。这时修改第j栏登记项的内容:始址不变,长度为原长度加上L。于是,归还区便与上邻空闲区合在一起了。
(3)归还区既有上邻空闲区又有下邻空闲区。
S=第j栏始址+长度
如果
S+L=第k栏始址
则表明归还区既有上邻空闲区,又有下邻空闲区。此时,须把这三个区合并成一个空闲区登记入空闲区表中,只需使用一个登记栏目。进行如下修改:第j栏始址不变;第j栏长度为“j栏中原长度+k栏中长度+L”;第k栏的标志应修改成“空”状态。于是,第j栏中登记的空闲区就是合并后的空闲区,而第k栏成为空表目了。
(4)归还区既无上邻又无下邻空闲区。如果在检查空闲区表时,无上述三种情况出现,则表明归还区既无上邻又无下邻空闲区。这时,应找一个标志为“空”的登记栏,把归还区的始址和长度登记入表,且把该栏目中的标志位修改成“未分配”。
(3) 可变方式管理主存时的存储保护
硬件设置两个专用的控制寄存器:限长寄存器和基址寄存器。当进程调度选中某作业进程占用处理器时,把作业所占分区的始址和长度送入基址寄存器和限长寄存器中。作业执行过程中,处理器每执行一条指令都要取出指令中的逻辑地址。当逻辑地址小于限长寄存器中的限长值时,由该逻辑地址加基址寄存器之值就可得到合法的(即不越界的)绝对地址。当逻辑地址大于或等于限长寄存器中的限长值时,表示欲访问的主存地址超出了所分配的分区的范围,这时就不允许访问该主存地址,并形成一个“地址越界”的程序性中断事件。由此可知,存储保护是需要操作系统与硬件相互配合来实现的。
(4)
移动技术的应用
移动技术要“移动”的东西就是主存空间中的作业。把某个作业移到另一处主存空间去(在磁盘整理中我们应用的也是类似的移动技术),这样的最大好处就是可以合并一些空闲区。如图4_3.7 所示
但是移动技术的应用也要注意以下问题:
1)
移动会增加系统开销。所以要尽量减少移动。
2)移动是有条件的,如果作业在执行过程中正等待与外围设备传输信息,就不能移动。因此在移动时首先要判定该作业是否与外设交换信息。
第四节 页式存储管理
l 基本原理
页式存储管理中有两个名词:“页”和“块”,其中的“块”是针对硬件来说的,就是把存储器分成若干相等大小的区,每个区就称为一个块。对应的,在程序中,逻辑地址进行“分页”,其大小和每个块相一致。
事实上,页面的大小是由块的大小自然决定的。对于程序来说,其逻辑地址还是和原来一样采用连续的地址。只是按照块的位数取其前面数位做为页号。
分配空间时,根据作业长度可以确定它的页面数,根据这个页面数在主存中分配相应的块数,只要是空闲块就可以放入,即使不是相邻的。并把分配情况记在“页表”中,根据页表可以找到相对应的页号与块号,就得出绝对地址了。
采用页式管理,使主存空间充分利用,页不必为了得到连续空间而进行移动。可以提高系统效率。
l 页式存储管理中主存块的大小是如何决定的?
主存块的大小是由硬件地址结构确定的。在页式存储管理中,地址由两部分组成:页号和页内地址。假定地址用m个二进制位表示,其中页内地址部分占用了n个二进制,那么每一个块的长度就是
。
l 页表的构造与作用
每个被装入主存的作业都有一张页表,指出该作业逻辑地址中的页号与所占用的主存块号之间的对应关系。页表的长度由作业拥有的页面数决定,行号对应为页号,行中记录的是主存中的块号。
页表是硬件进行地址转换的依据,每执行一条指令时按逻辑地址中的页号查找页表并转换成绝对地址。绝对地址的计算公式如下:
绝对地址= 块号* 块长+ 页内地址
图4_4.1指出了作业按页装入主存的示例。
图4-4.1中假定作业J有四个页面:
JP0,
JP1,
JP2,
JP3,现只要找出四个空闲块就可把作业1装入主存。如果找到的四个空闲块是第5,23,24,
27块,则四个页面就分别装入其中。同时应为该作业建立一张“页表”,指出逻辑地址中的页号与主存中块号的对应关系,页表的一般格式如图4-4.1中所示。作业执行时,按逻辑地址中的页号查“页表”,得到该页对应的块号,就可知道该页在主存中的位置,再按页内地址就能算出欲访问的绝对地址。绝对地址的计算公式为:绝对地址=
块号*
块长+
页内地址。因此,虽然作业被存放在若干个不连续的块中,但在作业执行中总是能按确切的绝对地址进行存取。
l 在采用页式存储管理的系统中,怎样利用“位示图”来进行主存空间的分配与回收?
位示图:位示图中的每一位与一个主存块对应,每一位的值可以是“0”或“1”,当取值为“0”时表示对应块为空闲,当取值为“1”时表示对应块已被占用。在位示图中增加一个字节记录当前剩余的空闲块数
当需要分配一块主存空间时,可从位示图中找一个为“0”的位,把该位置成占用标志“1”,且根据它在位示图中的字号和位号,按如下公式计算出与它对应的块号:
块号=字号x字长+位号
这个块号就是当前所分配用来装作业信息的主存块的块号。
当一个作业执行结束时,应收回该作业所占用的主存块。根据归还的块号可计算出归还块在位示图中的对应位置,计算公式如下,并将该位的占用标志置为“0”。
字号=[块号/字长],位号=块号 mod
字长
l 地址转换
每执行一条指令时按逻辑地址中的页号查页表,若页表中无此页号,则产生一个“地址错”的程序性中断事件;若页表中有此页号,则可得到对应的主存块号,按计算公式可转换成欲访问的主存绝对地址。按绝对地址的计算公式为“块号*块长+页内地址”
在多道程序设计的系统中,进入主存储器的每个作业都有一张页表。硬件要增加一个“页表控制寄存器”。调度程序选中某个作业占用处理器时,就把该作业的页表起站地址和长度送入页表控制寄存器。于是,地址转换机构根据页表控制器就可找到该作业的页表。
l 采用页式存储管理为什么会延长指令的执行周期?有什么办法可提高指令的执行速度?
页式存储管理中的页表一般是存放在主存中的。当要按给定的逻辑地址进行读/写时,首先要按页号从页表中读出对应的块号,然后算出绝对地址进行读/写。这样就必须访问主存两次,多花了一次访问主存的时间,因而延长了指令的执行周期,降低了执行速度。
为了提高存取速度,通常都设置一个小容量的高速缓冲存储器,用来存放页表的一部分。把这部分页表称为“快表”。根据程序执行局部性的特点,在一段时间内总是经常访问某些页。若把这些页登记在快表中,就可不要从主存中查页表,而是从高速缓冲存储器中查快表,这样就可缩短查找时间,从而提高了指令执行速度。
l 页的共享与保护
页的共享解决共享信息的保护问题。通常的办法是在页表中增加一些标志位,指出对该页信息可执行的操作。处理器执行指令时要核对操作要求,若想向只读块写入信息,则指令停止执行。同样地,对共享程序块不允许读或写,只能调用执行,否则也停止指令的执行。当违反规定的访问权限时,将产生一个“非法操作”的程序性中断事件。