专注于c++

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  21 Posts :: 0 Stories :: 4 Comments :: 0 Trackbacks

常用链接

留言簿(15)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

第一节  存储管理概述

l          信息的二级存储

    为了提高处理器的利用率和系统的工作效率,主存储器中经常存放了多个程序和数据。现今许多计算机系统都采用二级存储的办法,利用辅助存储器(磁盘、磁带等)提供的大容量存储空间,存放准备运行的程序和数据,当需要时或主存空间允许时,随时将它们读入主存储器

l          存储管理的功能

(1)       主存空间的分配和去配

    主存储器中允许同时容纳多个用户的计算问题(作业),必须解决主存空间如何分配的问题。当主存中某个作业撤离或主动归还主存空间时,则收回它所占有的所有或部分的主存空间。收回存储空间的工作称为“去配”。

(2)       实现地址转换

由于用户程序中使用的是逻辑地址,而处理器执行程序时要按绝对地址访问主存。所以,存储管理必须配合硬件进行地址转换工作,把一组逻辑地址转换成绝对地址,以保证处理器的正确执行。

(3)       主存空间的共享和保护

在多道程序设计的系统中,若干个作业同时装入主存储器,它们共享了一个主存储器,在其中各自占用了某些主存区域。这些作业在执行时可能要调用共同的程序。因此,这个主存区域又成为各作业的共享区域。

为了防止各作业相互干扰和保护各区域内的信息不被破坏,必须实现存储保护。一般地说,对主存区域的保护可采取如下措施:

1)程序执行时访问属于自己主存区域中的信息,则允许它既可读,又可写。

2)对共享区域中的信息只可读,不可修改。

3)程序执行时,不允许访问其他程序的主存区域,即对于非共享区域或非自己的主存区域中的信息既不可读,也不可写。


(4)       主存空间的扩充


     操作系统为用户提供一个虚拟的内存,使用户编制程序时可以不考虑主存储器的实际容量,允许程序中的逻辑地址空间大于主存的绝对地址空间,起到了扩充主存空间的
第二节     重定位 

l           区分逻辑地址与绝对地址

绝对地址:主存储器以字节为编址单位,容量为n的主存储器中,每个单元有唯一的编号,从0n-1,这个唯一的编号就是主存储器的物理地址也叫绝对地址。

    逻辑地址:在多道程序设计的系统中,操作系统为了方便用户,就允许每个用户都认为自己作业的程序和数据存放在地址从 0开始的连续空间中。这样用户程序中使用的地址就是逻辑地址也叫相对地址。 

l          对主存储器为什么要区分绝对地址和逻辑地址?

中央处理器访问主存时必须指定确切的存储单元。在计算机系统中通常对主存储器以字节(每个字节8个二进制位)为编址单位,每个字节都有一个地址与其对应,这样的地址称为主存储器的“绝对地址”。

在多道程序设计系统中,主存中同时存放了多个用户作业。操作系统根据主存的使用情况为用户分配主存空间。每个用户不能预先知道他的作业将被存放到主存储器的什么地方。这样,用户程序中就不能使用主存的绝对地址。为了方便用户,允许用户程序中使用“逻辑地址”,每个用户都可认为自己作业的程序和资料存放在一组从“0”地址开始的连续的逻辑地址空间中。 

l          重定位

为了保证作业的正确执行,必须根据分配给作业的主存区域对作业中指令和数据的存放进行重定位,这种把逻辑地址转换成绝对地址的工作称为“重定位”或“地址转换”。重定位的方式有“静态重定位”和“动态重定位”两种。

(1)静态重定位

在装入一个作业时,把作业中的指令地址和数据地址全部转换成绝对地址。这种转换工作是在作业开始前集中完成的,在作业执行过程中无需再进行地址转换。所以称为“静态重定位”。图4_2.1指出了静态重定位的过程。

在图42.l中,假定用户作业的逻辑地址空间从“0”到“124”,其中第8号单元处有一条“加法”指令,该指令要求从第32号单元处取出操作数3465,然后进行加法操作。如果存储管理为该作业分配的主存区域是从100单元开始,那么,逻辑地址第8号单元在主存中的对应位置是108单元,第32号单元在主存中的对应位置应该是132单元。如果不修改上述“加法”指令中的操作数地址,则处理器执行该指令时将从主存的032单元中去取操作数,这显然是错误的。于是,应把程序中所有逻辑地址都转换成绝对地址。上述加法指令中的操作数地址也应改成132。这样,在执行指令时便可从132单元取到正确的操作数。

(2)动态重定位

在装入一个作业时,不进行地址转换,而是直接把作业装到分配的主存区域中。在作业执行过程中,每当执行一条指令时都由硬件的地址转换机构转换成绝对地址。这种方式的地址转换是在作业执行时动态完成的,所以称为动态重定位。图4_2.2指出了动态重定位的过程。

在图42.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)主存的分配和去配

     在系统初始化时,主存除了操作系统所占部分外,整个用户区是一个大的空闲区,可以按作业需要的空间大小顺序分配空闲区直到不够时为止。

当作业结束时,它的占用分区被收回。这个空闲区又可以根据新作业的大小重新用于分配,所以主存中的已占分区和空闲区的数目和大小都是在变化的。可以用两张表“已分配区表”和“空闲区表”来记录和管理。

例如,某主存容量为2560K1K1024字节),其中操作系统占用400K,现依次有五个作业J1J2J3J4J5要求装入主存,它们对主存的需求量分别是600K1000K300K700K500K。图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栏始址+长度

    如果

        SL=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装入主存。如果找到的四个空闲块是第52324 27块,则四个页面就分别装入其中。同时应为该作业建立一张“页表”,指出逻辑地址中的页号与主存中块号的对应关系,页表的一般格式如图4-4.1中所示。作业执行时,按逻辑地址中的页号查“页表”,得到该页对应的块号,就可知道该页在主存中的位置,再按页内地址就能算出欲访问的绝对地址。绝对地址的计算公式为:绝对地址= 块号* 块长+ 页内地址。因此,虽然作业被存放在若干个不连续的块中,但在作业执行中总是能按确切的绝对地址进行存取。

 

l          在采用页式存储管理的系统中,怎样利用“位示图”来进行主存空间的分配与回收?

位示图:位示图中的每一位与一个主存块对应,每一位的值可以是“0”或“1”,当取值为“0”时表示对应块为空闲,当取值为“1”时表示对应块已被占用。在位示图中增加一个字节记录当前剩余的空闲块数

当需要分配一块主存空间时,可从位示图中找一个为“0”的位,把该位置成占用标志“1”,且根据它在位示图中的字号和位号,按如下公式计算出与它对应的块号:

                            块号=字号x字长+位号

这个块号就是当前所分配用来装作业信息的主存块的块号。

    当一个作业执行结束时,应收回该作业所占用的主存块。根据归还的块号可计算出归还块在位示图中的对应位置,计算公式如下,并将该位的占用标志置为“0”。

           字号=[块号/字长],位号=块号  mod 字长

 

l          地址转换

    每执行一条指令时按逻辑地址中的页号查页表,若页表中无此页号,则产生一个“地址错”的程序性中断事件;若页表中有此页号,则可得到对应的主存块号,按计算公式可转换成欲访问的主存绝对地址。按绝对地址的计算公式为“块号*块长+页内地址”

      在多道程序设计的系统中,进入主存储器的每个作业都有一张页表。硬件要增加一个“页表控制寄存器”。调度程序选中某个作业占用处理器时,就把该作业的页表起站地址和长度送入页表控制寄存器。于是,地址转换机构根据页表控制器就可找到该作业的页表。

l          采用页式存储管理为什么会延长指令的执行周期?有什么办法可提高指令的执行速度?

    页式存储管理中的页表一般是存放在主存中的。当要按给定的逻辑地址进行读/写时,首先要按页号从页表中读出对应的块号,然后算出绝对地址进行读/写。这样就必须访问主存两次,多花了一次访问主存的时间,因而延长了指令的执行周期,降低了执行速度。

为了提高存取速度,通常都设置一个小容量的高速缓冲存储器,用来存放页表的一部分。把这部分页表称为“快表”。根据程序执行局部性的特点,在一段时间内总是经常访问某些页。若把这些页登记在快表中,就可不要从主存中查页表,而是从高速缓冲存储器中查快表,这样就可缩短查找时间,从而提高了指令执行速度。

 

l          页的共享与保护

      页的共享解决共享信息的保护问题。通常的办法是在页表中增加一些标志位指出对该页信息可执行的操作。处理器执行指令时要核对操作要求,若想向只读块写入信息,则指令停止执行。同样地,对共享程序块不允许读或写,只能调用执行,否则也停止指令的执行。当违反规定的访问权限时,将产生一个“非法操作”的程序性中断事件。
第五节      段式存储管理 

l          基本原理

    段式存储管理是根据人们对程序中需要分段编制的要求出发而提供的。它提供给用户编程时使用的逻辑地址由段号段内地址两部分组成,格式如下:

    其形式和页式存储管理相同。但是实际上是不同的:页式存储管理提供连续的逻辑地址,由系统自动地进行分页;段式存储管理中作业的分段是由用户决定的,每段独立编程,因此,段间的逻辑地址是不连续的。 

l          段式存储管理怎样为作业分配主存空间?

        段式存储管理为作业的每一段分配一个连续的主存区域。作业的各个段可被装到不相连的几个区域中。 

l          段式存储管理怎样保证作业的正确执行?

    为了控制作业的正确执行,必须把作业的各个段在主存储器中的位置记录下来。为此,装作业时,操作系统为作业建立一张“段表”,指出该作业每个段的长度和在主存储器的起始地址。作业执行时按逻辑地址中的段号到“段表”中查得该段在主存储器中的起始地址,把起始地址与逻辑地址中的段内地址相加就得到欲访问的主存绝对地址。所以,虽然各个段是分散存放在主存储器中,但在作业执行中总能找到对应的绝对地址。此外,还可通过段表中的长度,核对欲访问的主存单元是否在限定的分区内,以保证主存中信息的安全性。

段表段号本段限长起始地址三部分组成,由于每一行记录的行号可以对应程序的段号,因此段号实际上被省略,不占存储空间。

l          主存空间的分配和去配

这种分配方法和可变分区管理方式的分配方法相同,所不同的是:

可变分区管理方式中是为每个作业分一个区,而段式管理是为一个作业中的每个段分一个连续的空间。

l          地址转换和存储保护

这个转换过程如同可变分区方式的地址转换,但是由段表的表目替代了基址/限长寄存器。

绝对地址=根据段号找到段表中的起始地址+段内地址

如果段内地址超过限长则产生“地址越界”程序性中断事件达到存储保护

多道程序设计系统中,每个进入主存的作业都建立了段表,因此还有一个硬件“段表控制寄存器”来记录每个作业的段表在主存中的位置和长度。

l          可分页的段式存储管理

    段页式存储管理兼顾了段式在逻辑上清晰和页式在管理上方便的优点。

段页式存储管理把主存储器预先分成大小相等的许多块,在把一段的信息装入主存时,按块的大小分页,一段信息可被分散存放在若干主存块中。

段页式存储管理的逻辑地址的格式

    段页式存储管理为每一个装入主存储器的作业建立一张段表,且对每一段要建立一张页表。段表的长度由作业分段的个数决定,段表中的每一个表目指出本段的页表始址和长度。页表的长度由对应段所分的页的个数决定,页表中的每一个表目指出本段的逻辑页号与主存块号的对应关系。

       执行指令时,地址机构根据逻辑地址中的段号查段表,得到该段的页表始址,然后根据页号查页表,得到对应的主存块号,由主存块号与逻辑地址中的页内地址可形成可访问的绝对地址。如果逻辑地址中的段号超出了段表中的最大段号或者页号超出了该段页表中的最大页号,都要形成“地址越界”的程序性中断事件。

 第六节      虚拟存储器 

l          虚拟存储器

虚拟存储器:若允许逻辑地址空间大于存的实际空间,那么好像计算机系统为用户提供了一个比主存的实际容量大的主存储器,把这个可供用户编程时使用的主存储器称为虚拟存储器。

虚拟存储器的容量由计算机的地址结构(总线位数)决定。 

l          虚拟存储器的实现原理

首先把作业信息保留在磁盘上,当作业请求装入时,只将其中一部分先装入主存,作业执行中若要访问的信息不在主存中,再设法将这些信息装入主存。 

l          任何程序必须装入主存后才能执行。现在又允许用户作业中使用虚拟存储器。试问,当用户作业使用的虚存量超出实际主存量时怎么办?

一般说来,程序有两个特点

         1) 程序执行时有些部分是彼此互斥的,即在程序的一次执行中,执行了这一部分就不会去执行另一部分。

2) 程序的执行往往具有局部性,在一段时间里可能循环执行某些指令或多次访问某一部分的数据。因此没有必要把全部作业信息同时装入主存储器。只要有大容量的磁盘作后盾,把作业信息保留在磁盘上,只将其中的一部分先装入主存储器。若作业执行中要访问的信息不在主存中,则再设法把当前所需的信息装入主存。这样,通过合理的调度就可以使大作业在小空间里正确执行。

l          采用页式虚拟存储管理时怎样设计页表?

由于页式虚拟存储管理是把作业信息作为副本存放在磁盘上的,为了能方便地从磁盘上找到作业信息,应在表中指出每一页副本在磁盘上的位置,此外还应指出哪些页已在主存储器,哪些页还没有装人主存。通常在页表中设置一个标志位来指示对应的页是否在主存储器,标志位为“1”表示对应页在主存,为“0”表示尚未装入主存。当对应页在主存时,需在页表中指出该页所占用的主存块号。 

l          在采用页式虚拟存储管理的系统中执行作业时硬件和操作系统应怎样配合?

      在作业执行中访问某页时,由硬件的地址转换机构查页表。若该页的对应表项中标志位为" 1",则按该表项中主存块号进行地址转换,得到绝对地址后去访问主存。若该页对应表项中标志位为“0”,则硬件形成“缺页中断”,表示该页不在主存储器中。当中断装置响应该中断后,操作系统就要处理这个缺页中断。处理的办法是:查主存分配表,找出一个空闲的主存块;再查页表,找出该页在磁盘上的位置;再启动磁盘读出该页信息,并把该页信息装入所找到的主存块中;再修改页表中与该页对应的表项,在该表项中填入所找到的主存块的块号,并把标志位置为“1”;最后修改指令地址,让硬件重新执行被中断的指令。 

l          常用的页面调度算法:FIFOLRULFU

    当主页中无空闲块时,为了装入一个页面,就必须按某种算法将主存中某个页调出,调入所需装入的页面。这就是页面调度。常用的算法有:先进先出调度算法(FIFO)、最近最少使用调度算法(LRU)和最近最不常用调度算法(LFU)

1)先进先出调度算法(FIFO)

    算法思想:总是选择最先装入主存储器的那一页调出,或者说是把驻留在主存中时间最长的那一页调出。

算法实现:把装入主存储器的那些页的页号按进入的先后次序排成队列,每次总是调出队首的页,当装入一个新页后,把新页的页号排入队尾。在具体实现时可用指针K指示最早被装入主存的那页在队列中的位置,每次总是选择指针K指示的页调出,在装入一个新页后,在指针指示的位置上填上新页页号,然后指针K1,指向下一次可调出的页。图4_6.1是先进先出调度算法的示例。

 2)最近最少用算法(LRU)

    算法思想:总是选择距现在最长时间内没有被访问过的页面先调出。

    算法实现:1是在页表中为每一页增加一个计时标志,记录该页面自上次被访问以来所经历的时间,每被访问一次都应从“0”开始重新计时。于是,产生缺页中断,而要装入新页时,检查页表中各页的计时标志,从中选出计时值最大的那一页调出(即最近一段时间里最久没有被使用过的页),并且把各页的计时标志全部置“0”,重新计时。当再一次产生缺页中断时,又可找到最近最久没有被使用过的页,将其调出。这种实现方法必须对每一页的访问情况加以记录和更新,实现比较麻烦且开销大。

    2堆栈实现,这种方法能准确地选择最近最少用的页。栈中存放当前在主存中的页,每当访问一页时就调整一次,使栈顶总是指出最近访问的页,而栈底是最近最少用的页。

例:假定系统为某个进程分配了三个物理块,而进程的访问顺序为701203042303212。采用LRU算法如图4_6.2所示。

进程运行时陆续将要访问的701三个页面装入内存。因为此时内存中尚有空闲块,因此不存在淘汰问题。第四个要访问的页面是2页面,不在内存中,此时发生缺页中断,需要从外存调入,而这时该进程已不存在空闲块,需要选择淘汰的页面以被置换。我们将最近最少使用的7页面淘汰。第五个要访问的页面是0页面,在系统中已经存在,不需要调入,命中一次。由图中可看出,采用LRU算法共命中5次(×标记)。

    3)最近最不常用调度算法(LFU)

算法思想:如果一个页面被访问的次数多,则是经常要使用的页面,就不把它调出。所以,这种算法总是选择被访问次数少的页面调出。

算法实现:为每一页设置一个计数器,每当访问一页时,就把该页对应的计数器加1。操作系统确定一个周期T, 在周期T的一段时间内,若没有发生缺页中断,则把所有的计数器清“0”,开始一个新的周期重新计数。若在周期T的时间内发生了缺页中断,则选择计数值最小的那页调出(它是最近一段时间内最不常用的页),同时把所有的计数器清“0”。

    4)最佳页面调度算法(OPT

    一个理想的调度算法是当要装入一个新页而必须调出一个页面时,所选择的调出页应该是以后再也不使用的页或者是距当前最长时间以后才使用的页。这种调度算法是最优的,然而这种算法是无法实现的,因为无法预测作业的运行情况,而只能将其作为衡量其他页面调度算法的标准。

l          什么叫“抖动”?

如果采用的页面调度算法不合适,就会出现这样一种现象:刚刚被调出的页面又立即要用,因而又要把它装入,而装入不久又被选中调出,调出不久又要装入使用,如此反复,使调度非常频繁。这种现象称为“抖动”,或称为“颠簸”。 

l          缺页中断率

    如果作业执行中访问页面的总次数为A,其中有F次访问的页面尚未装入主存,则有F次缺页中断,f=F/A,这里的f就称为缺页中断率。影响缺页中断的因素有:

1)分配给作业的主存块数----块数n↑(增加) f↓(下降)

2)页面的大小----页面大小↑ f↓

3)程序编制方法----局部化程度↑ f↓

l          段式虚拟存储管理

段式虚拟存储管理以段式存储管理为基础,在磁盘上保留作业的各个分段信息,作业执行时把需要执行的一段或几段装入主存。在实际使用中,也要进行查表和地址转换以及“缺段中断”和调度(包括调出、装入、移动等)工作。 

l          段式虚拟存储管理的实现要点

    段式存储管理把作业中各个分段信息都保留在磁盘上,以段为单位分配主存空间。

    当作业可以占用处理执行时,首先把当前需要的一个段或几个段装入主存,同时为该作业建立段表。作业执行时若要访问段已在主存,则可立即把逻辑地址转换成绝对地址,否则产生一个“缺段中断”,由操作系统把需要用的段装入主存。新的段装好之后重新执行被中断的指令。  点击见相关动画

l          操作系统处理缺段中断时应做哪些主要工作?

为了装入所缺的段,操作系统应根据该段的长度,查主存分配表,找出一个足够大的连续区以容纳该分段。如果找不到足够大的连续区,则检查空闲区的总和。若空闲区总和能满足该段要求,则进行适当移动,将分散的空闲区集中,否则把主存中的一段或几段调出;然后把要访问的段装入主存。段被移动、调出、装人后都要对段表中相应表项作修改。新的段装入后应让作业重新执行被中断的指令。

l          提供虚拟存储器有什么优点?

提供虚拟存储器后,从系统的角度来看,使主存空间能充分地被利用,从而提高了主存空间的利用率。从用户的角度来看,程序使用的逻辑地址空间可以大于主存的实际容量,为编制程序提供了方便。

posted on 2009-09-28 14:08 bellgrade 阅读(1368) 评论(0)  编辑 收藏 引用 所属分类: 操作系统原理

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理