免费智能真题库 > 历年试卷 > 数据库系统工程师 > 2011年上半年 数据库系统工程师 上午试卷 综合知识
  第27题      
  知识点:   存储管理方案   虚拟存储管理   存储管理   进程   内存   页式存储管理
  关键词:   进程   内存   页式存储管理   存储管理        章/节:   计算机软件基础知识       

 
某系统釆用请求页式存储管理方案,假设某进程有6个页面,系统给该进程分配了4个存储块,其页面变换表如下表所示,表中的状态位等于1/0分别表示页面在/不在内存。当该进程访问的页面2不在内存时,应该淘汰表中页号为(27)的页面。
 
 
  A. 

0

 
  B.  3
 
  C.  4
 
  D.  5
 
 
 

 
  第25题    2010年上半年  
   57%
某进程有5个页面,页号为0〜4,页面变换表如下所示。表中状态位等于0和1分别表示页面“不在内存”和“在内存..
  第26题    2012年上半年  
   66%
假设一台按字节编址的16位计算机系统,采用虚拟页式存储管理方案,页面的大小为2K,且系统中没有使用快表(或联想存储器)。某用户..
  第26题    2014年上半年  
   44%
某计算机系统页面大小为4K,若进程的页面变换表如下所示,逻辑地址为十六进制1D16H。该地址经过变换后,其物理地址应为十六进制(..
   知识点讲解    
   · 存储管理方案    · 虚拟存储管理    · 存储管理    · 进程    · 内存    · 页式存储管理
 
       存储管理方案
        存储管理的主要目的是解决多个用户使用主存的问题,其存储管理方案主要包括分区存储管理、分页存储管理、分段存储管理、段页式存储管理以及虚拟存储管理。本小节介绍分区存储管理方案,其他存储管理方案将在后续章节中介绍。
               分区存储管理
               分区存储管理是早期的存储管理方案,其基本思想是把主存的用户区划分成若干个区域,每个区域分配给一个用户作业使用,并限定它们只能在自己的区域中运行,这种主存分配方案就是分区存储管理方式。按划分方式不同,分区可分为固定分区、可变分区和可重定位分区。
               (1)固定分区。固定分区是一种静态分区方式,在系统生成时已将主存划分为若干个分区,每个分区的大小可不等。操作系统通过主存分配情况表管理主存。这种方法的突出问题是已分配区中存在未用空间,原因是程序或作业的大小不可能刚好等于分区的大小,故造成了空间的浪费。通常将已分配分区内的未用空间称为零头或内碎片。
               (2)可变分区。可变分区是一种动态分区方式,存储空间的划分是在作业装入时进行的,故分区的个数是可变的,分区的大小刚好等于作业的大小。可变分区分配需要已分配表和未分配表两种管理表格,分别记录已分配分区和未分配分区的情况。对于可变分区的请求和释放分区主要有4种算法:最佳适应算法、最差适应算法、首次适应算法和循环首次适应算法。
               引入可变分区后虽然主存的分配更灵活,也提高了主存的利用率,但是由于系统在不断地分配和回收中,必定会出现一些不连续的小的空闲区,尽管这些小的空闲区的总和超过某一个作业要求的空间,但是由于不连续而无法分配,产生了未分配区的无用空间,通常称之为外碎片。解决碎片的方法是拼接(或称紧凑),即向一个方向(例如向低地址端)移动已分配的作业,使那些零散的小空闲区在另一个方向连成一片。
               (3)可重定位分区。可重定位分区是解决碎片问题的简单且行之有效的方法。基本思想是移动所有已分配好的分区,使之成为连续区域。如同队列有一个队员出列,指挥员叫大家“靠拢”一样。分区“靠拢”的时机是当用户请求空间得不到满足时或某个作业执行完毕时。由于“靠拢”是要代价的,所以通常是在用户请求空间得不到满足时进行。需要注意的是,当进行分区“靠拢”时会导致地址发生变化,所以有地址重定位问题。
               分区保护
               分区保护的目的是防止未经核准的用户访问分区,常用的两种方式如下:
               (1)采用上界/下界寄存器保护。上界寄存器中存放的是作业的装入地址,下界寄存器中装入的是作业的结束地址,形成的物理地址必须满足如下条件:
               上界寄存器≤物理地址≤下界寄存器
               (2)采用基址/限长寄存器保护。基址寄存器中存放的是作业的装入地址,限长寄存器中装入的是作业的长度,形成的物理地址必须满足如下条件:
               基址寄存器≤物理地址<基址寄存器+限长寄存器
 
       虚拟存储管理
        在前面介绍的存储管理方案中,必须为每个作业分配足够的空间,以便装入全部信息。当主存空间不能满足作业要求时,作业无法装入主存执行。
        如果一个作业只部分装入主存便可开始启动运行,其余部分暂时留在磁盘上,在需要时再装入主存,这样可以有效地利用主存空间。从用户角度看,该系统所具有的主存容量将比实际主存容量大得多,人们把这样的存储器称为虚拟存储器。虚拟存储器是为了扩大主存容量而采用的一种设计方法,其容量是由计算机的地址结构决定的。
               程序局部性原理
               早在1968年P.Denning就指出,程序在执行时将呈现出局部性规律,即在一段时间内,程序的执行仅局限于某个部分。相应地,它所访问的存储空间也局限于某个区域内。程序的局限性表现在时间局限性和空间局限性两个方面。
               (1)时间局限性是指如果程序中的某条指令一旦执行,则不久的将来该指令可能再次被执行;如果某个存储单元被访问,则不久以后该存储单元可能再次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。
               (2)空间局限性是指一旦程序访问了某个存储单元,则在不久的将来,其附近的存储单元也最有可能被访问。即程序在一段时间内所访问的地址可能集中在一定的范围内,其典型原因是程序是顺序执行的。
               虚拟存储器的实现
               虚拟存储器是具有请求调入功能和置换功能,能仅把作业的一部分装入主存便可运行作业的存储器系统,是能从逻辑上对主存容量进行扩充的一种虚拟的存储器系统。其逻辑容量由主存和外存容量之和以及CPU可寻址的范围来决定,其运行速度接近于主存速度,成本也下降。可见,虚拟存储技术是一种性能非常优越的存储器管理技术,故被广泛地应用于大、中、小型机器和微型机中。虚拟存储器的实现主要有如下3种方式:
               (1)请求分页系统。该系统是在分页系统的基础上增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许只装入若干页的用户程序和数据(而非全部程序)就可以启动运行,以后再通过调页功能和页面置换功能陆续把将要使用的页面调入主存,同时把暂不运行的页面置换到外存上,置换时以页面为单位。
               (2)请求分段系统。该系统是在分段系统的基础上增加了请求调段和分段置换功能所形成的段式虚拟存储系统。它允许只装入若干段的用户程序和数据就可以启动运行,以后再通过调段功能和置换功能将不运行的段调出,同时调入将要运行的段。注意:置换时以段为单位。
               (3)请求段页式系统。该系统是在段页式系统的基础上增加了请求调页和页面置换功能所形成的段页式虚拟存储系统。
               请求分页管理的实现
               请求分页是在纯分页系统的基础上增加了请求调页功能、页面置换功能所形成的页式虚拟存储系统,它是目前常用的一种虚拟存储器的方式。
               请求分页的页表机制是在纯分页的页表机制上形成的,由于只将应用程序的一部分调入主存,还有一部分仍在磁盘上,故需在页表中再增加若干项(如状态位、访问字段和辅存地址等)供程序(数据)在换进、换出时参考。
               请求分页系统中的地址变换机构是在分页系统的地址变换结构的基础上增加了某些功能,如产生和处理缺页中断、从主存中换出一页实现虚拟存储。
               在请求分页系统中,每当所要访问的页面不在主存时便要产生一个缺页中断,请求OS将所缺的页调入主存,这是由缺页中断机构完成的。缺页中断与一般中断的主要区别如下:
               (1)缺页中断在指令执行期间产生和处理中断信号,而一般中断在一条指令执行完,下一条指令开始执行前检查和处理中断信号。
               (2)发生缺页中断时,返回到被中断指令的开始重新执行该指令,而一般中断返回到下一条指令执行。
               (3)一条指令在执行期间可能会产生多次缺页中断。
               页面置换算法
               请求分页是在纯分页系统的基础上增加了请求调页功能、页面置换功能所形成的页式虚拟存储系统,它是目前常用的一种虚拟存储器的方式。在进程运行过程中,如果发生缺页,此时主存中又无空闲块时,为了保证进程能正常运行,必须从主存中调出一页程序或数据送磁盘的对换区。但究竟将哪个页面调出,需要根据一定的页面置换算法来确定。置换算法的好坏将直接影响系统的性能,不适当的算法可能会导致系统发生“抖动”(thrashing)。即刚被换出的页很快又被访问,需重新调入,导致系统频繁地更换页面,以至于一个进程在运行中把大部分时间花费在完成页面置换的工作上,这种现象称为系统发生了“抖动”(也称颠簸)。请求分页系统的核心问题是选择合适的页面置换算法,常用的页面置换算法如下所述。
                      最佳(Optimal)置换算法
                      这是一种理想化的算法,即选择那些永不使用的,或者是在最长时间内不再被访问的页面置换出去。这种方法性能最好,但实际上难于实现,并且要确定哪一个页面是未来最长时间内不再被访问的是很难的,所以该算法通常用来评价其他算法。
                      先进先出(FIFO)置换算法
                      该算法总是淘汰最先进入主存的页面,即选择在主存中驻留时间最久的页面予以淘汰。该算法实现简单,只需把一个进程调入主存的页面,按先后次序链接成一个队列,并设置一个指针即可。它是一种最直观、性能最差的算法,有Belady异常现象。所谓Belady现象,是指如果对一个进程未分配它所要求的全部页面,有时就会出现分配的页面数增多但缺页率反而提高的异常现象。例如,对于页面访问序列“1,2,3,4,1,2,5,1,2,3,4,5”,当分配的物理块从3块增加到4块时,有缺页次数增加、缺页率提高的异常现象。
                      最近最少使用(Least Recently Used,LRU)置换算法
                      该算法是选择最近最少使用的页面予以淘汰,系统在每个页面设置一个访问字段,用于记录这个页面自上次被访问以来所经历的时间T,当要淘汰一个页面时,选择T最大的页面,但在实现时需要硬件的支持(寄存器或栈)。
                      最近未用(Not Used Recently,NUR)置换算法
                      NUR算法将最近一段时间未引用过的页面换出,这是一种LRU的近似算法。该算法为每个页面设置一位访问位,将主存中的所有页面都通过链接指针链成一个循环队列。当某页被访问时,其访问位置1。在选择一页淘汰时,检查其访问位,如果是0,则选择该页换出;若为1,则重新置为0,暂不换出该页,在循环队列中检查下一个页面,直到访问位为0的页面为止。由于该算法只有一位访问位,只能用它表示该页是否已经使用过,而置换时是将未使用过的页面换出去,所以把该算法称为最近未用算法。
               工作集
               事实上,程序在运行中所产生的缺页情况会影响程序的运行速度及系统性能,而缺页率的高低又与每个进程所占用的物理块数目有关。那么,究竟应该为每个进程分配多少个物理块才能把缺页率保持在一个合理的水平上,而不会因为进程频繁地从辅存请求页面而出现“颠簸”(也称抖动)现象?为了解决这一问题,引入了工作集理论。
               工作集的理论是1968年由Denning提出的,他认为,虽然程序只需有少量的几页在主存就可以运行,但为了使程序能够有效地运行,较少地产生缺页,必须使程序的工作集驻留在主存中。把某进程在时间t的工作集记为wtΔ),变量Δ称为工作集“窗口尺寸(Windows Size)”。正确地选择工作集窗口(Δ)的大小,对存储器的有效利用和系统吞吐量的提高都将产生重大的影响。可见工作集就是指在某段时间间隔(Δ)里进程实际要访问的页面的集合。
               程序在运行时对页面的访问是不均匀的,即往往在某段时间内的访问仅局限于较少的若干个页面,如果能够预知程序在某段时间间隔内要访问哪些页面,并能将它们提前调入主存,将会大大地降低缺页率,从而减少置换工作,提高CPU的利用率。当每个工作集都已达到最小值时,虚存管理程序跟踪进程的缺页数量,根据主存中自由页面的数量可以适当增加其工作集的大小。
 
       存储管理
        存储管理是操作系统的重要组成部分,它负责管理计算机系统的重要资源——主存储器。由于任何程序、数据必须占用主存空间后才能执行,因此存储管理直接影响系统的性能。主存储空间一般分为两部分:一部分是系统区,存放操作系统以及一些标准子程序,例行程序等;另一部分是用户区,存放用户的程序和数据等。存储管理主要是对主存储器中的用户区域进行管理,当然也包括对辅存储器的管理。目的是要尽可能地方便用户使用和提高主存储器的效率。具体地说,存储管理有下面几个方面的功能。
        (1)主存储空间的分配和回收。
        (2)地址转换和存储保护。
        (3)主存储空间的共享。
        (4)主存储空间的扩充。
               存储器的层次
               目前,计算机系统均采用分层结构的存储子系统,以便在容量大小、速度快慢、价格高低诸因素中取得平衡点,获得较好的性能价格比。计算机系统的存储器可以分为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等7个层次结构。如下图所示,越往上,存储介质的访问速度越快,价格也越高。其中,寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴,掉电后它们存储的信息不再存在。固定磁盘和可移动存储介质属于设备管理的管辖范畴,它们存储的信息将被长期保存。而磁盘缓存本身并不是一种实际存在的存储介质,它依托于固定磁盘,提供对主存储器存储空间的扩充。
               
               计算机系统存储器的层次
               可执行的程序必须被保存在计算机的主存储器中,与外围设备交换的信息一般也依托于主存储器地址空间。由于处理器在执行指令时主存访问时间远大于其处理时间,寄存器和高速缓存被引入以加快指令的执行。
               寄存器是访问速度最快但最昂贵的存储器,它的容量小,一般以字(word)为单位。一个计算机系统可能包括几十个甚至上百个寄存器,用于加速存储访问速度,如寄存器存放操作数,或用地址寄存器加快地址转换速度。
               高速缓存的容量稍大,其访问速度快于主存储器,利用它存放主存中一些经常访问的信息可以大幅度提高程序执行速度。
               由于程序在执行和处理数据时存在顺序性、局部性、循环性和排他性,因此在程序执行时有时并不需要把程序和数据全部调入内存,而只需先调入一部分,待需要时逐步调入。这样,计算机系统为了容纳更多的算题数,或是为了处理更大批量的数据,就可以在磁盘上建立磁盘缓存以扩充主存储器的存储空间。算题的程序和处理的数据可以装入磁盘缓存,操作系统自动实现主存储器和磁盘缓存之间数据的调进调出,从而向用户提供了比实际主存存储容量大得多的存储空间。
               地址转换与存储保护
               用户编写应用程序时,是从0地址开始编排用户地址空间的,把用户编程时使用的地址称为逻辑地址(相对地址)。而当程序运行时,它将被装入主存储器地址空间的某些部分,此时程序和数据的实际地址一般不可能同原来的逻辑地址一致,把程序在内存中的实际地址称为物理地址(绝对地址)。相应地构成了用户编程使用的逻辑地址空间和用户程序实际运行的物理地址空间。
               为了保证程序的正确运行,必须把程序和数据的逻辑地址转换为物理地址,这一工作称为地址转换或重定位。地址转换有两种方式,一种方式是在作业装入时由作业装入程序实现地址转换,称为静态重定位;另一种方式是在程序执行时实现地址转换,称为动态重定位。动态重定位必须借助于硬件的地址转换部件实现。
               分区存储管理
               分区存储管理的基本思想是给进入主存的用户进程划分一块连续存储区域,把进程装入该连续存储区域,使各进程能并发执行,这是能满足多道程序设计需要的最简单的存储管理技术。
                      固定分区管理
                      固定分区(fixed partition)存储管理如下图所示,是预先把可分配的主存储器空间分割成若干个连续区域,每个区域的大小可以相同,也可以不同。
                      
                      固定分区存储管理示意图
                      为了说明各分区的分配和使用情况,存储管理需设置一张“主存分配表”,该表如下图所示。
                      
                      固定分区存储管理的主存分配表
                      主存分配表指出各分区的起始地址和长度,表中的占用标志位用来指示该分区是否被占用了,当占用的标志位为“0”时,表示该分区尚未被占用。进行主存分配时总是选择那些标志为“0”的分区,当某一分区分配给一个作业后,则在占用标志栏填上占用该分区的作业名,如下图所示,第2、5分区分别被作业Jobl和Job2占用,而其余分区为空闲。
                      可变分区管理
                      可变分区(Variable Partition)存储管理是按作业的大小来划分分区。系统在作业装入主存执行之前并不建立分区,当要装入一个作业时,根据作业需要的主存量查看主存中是否有足够的空间,若有,则按需要量分割一个分区分配给该作业;若无,则令该作业等待主存空间。由于分区的大小是按作业的实际需要量来定的,且分区的个数也是随机的,所以可以克服固定分区方式中的主存空间的浪费,有利于多道程序设计,实现了多个作业对内存的共享,进一步提高了内存资源利用率。
                      随着作业的装入、撤离,主存空间被分成许多个分区,有的分区被作业占用,而有的分区是空闲的。当一个新的作业要求装入时,必须找一个足够大的空闲区,把作业装入该区,如果找到的空闲区大于作业需要量,则作业装入后又把原来的空闲区分成两部分,一部分被作业占用了;另一部分又分成为一个较小的空闲区。当一个作业运行结束撤离时,它归还的区域如果与其他空闲区相邻,则可合成一个较大的空闲区,以利于大作业的装入。采用可变分区方式的主存分配示例如下图所示。
                      
                      可变分区存储管理的主存分配示例
                      常用的可变分区管理的分配算法有:
                      (1)最先适用分配算法:对可变分区方式可采用最先适用分配算法,每次分配时,总是顺序查找未分配表或链表,找到第一个能满足长度要求的空闲区为止。分割这个找到的未分配区,一部分分配给作业,另一部分仍为空闲区。这种分配算法可能将大的空间分割成小区,造成较多的主存“碎片”。作为改进,可把空闲区按地址从小到大排列在未分配表或链表中,于是为作业分配主存空间时,尽量利用了低地址部分的区域,而可使高地址部分保持一个大的空闲区,有利于大作业的装入。
                      (2)最优适应分配算法:可变分区方式的另一种分配算法是最优适应分配算法,它是从空闲区中挑选一个能满足作业要求的最小分区,这样可保证不去分割一个更大的区域,使装入大作业时比较容易得到满足。采用这种分配算法时可把空闲区按长度以递增顺利排列,查找时总是从最小的一个区开始,直到找到一个满足要求的分区为止。按这种方法,在回收一个分区时也必须对分配表或链表重新排列。
                      (3)最坏适应分配算法:最坏适应分配算法是挑选一个最大的空闲区分割给作业使用,这样可使剩下的空闲区不至于太小,这种算法对中、小作业是有利的。
               分页式存储管理
                      分页式存储管理的基本原理
                      用分区方式管理的存储器,每道程序总是要求占用主存的一个或几个连续存储区域,作业或进程的大小仍受到分区大小或内存可用空间的限制,因此,有时为了接纳一个新的作业而往往要移动已在主存的信息。这不仅不方便,而且开销不小。采用分页存储器既可免去移动信息的工作,又可尽量减少主存的碎片。分页式存储管理的基本原理如下:
                      (1)页框:物理地址分成大小相等的许多区,每个区称为一块(又称页框Page Frame)。
                      (2)页面:逻辑地址分成大小相等的区,区的大小与块的大小相等,每个区称一个页面(page)。
                      (3)逻辑地址形式:与此对应,分页存储器的逻辑地址由两部分组成(页号和单元号)。逻辑地址格式如下:
                      
                      采用分页式存储管理时,逻辑地址是连续的。所以,用户在编制程序时仍只需使用顺序的地址,而不必考虑如何去分页。由地址结构和操作系统管理的需要来决定页面的大小,从而,也就确定了主存分块的大小。用户进程在内存空间中每个页框内的地址是连续的,但页框和页框之间的地址可以不连续。存储地址由连续到离散的变化,为以后实现程序的“部分装入、部分对换”奠定了基础。
                      (4)页表和地址转换:在进行存储分配时,总是以块(页框)为单位进行分配,一个作业的信息有多少页,那么在把它装入主存时就给它分配多少块。但是,分配给作业的主存块可以是不连续的,即作业的信息可按页分散存放在主存的空闲块中,这就避免了为得到连续存储空间而进行的移动。那么,当作业的程序和数据被分散存放后,作业的页面与分给的页框如何建立联系呢?页式虚拟地址如何变换成页框物理地址呢?作业的物理地址空间由连续变成分散后,如何保证程序正确执行呢?采用的办法是动态重定位技术,让程序的指令执行时作地址变换,由于程序段以页为单位,所以,给每个页设立一个重定位寄存器,这些重定位寄存器的集合便称为页表(Page Table)。页表是操作系统为每个用户作业建立的,用来记录程序页面和主存对应页框的对照表,页表中的每一栏指明了程序中的一个页面和分得的页框的对应关系。通常为了减少开销,不是用硬件,而是在主存中开辟存储区存放页表,系统中另设一个页表主存起址和长度控制寄存器(Page Table Control Register),存放当前运行作业的页表起址和页表长,以加快地址转换速度。每当选中作业运行时,应进行存储分配,为进入主存的每个用户作业建立一张页表,指出逻辑地址中页号与主存中块号的对应关系,页表的长度随作业的大小而定。同时页式存储管理系统还建立一张作业表,将这些作业的页表进行登记,每个作业在作业表中有一个登记项。作业表和页表的一般格式如下图所示。然后,借助于硬件的地址转换部件,在作业执行过程中按页动态定位。调度程序在选择作业后,从作业表的登记项中得到被选中作业的页表始址和长度,将其送入硬件设置的页表控制寄存器。地址转换时,就可以从页表控制寄存器中找到相应的页表,再以逻辑地址中的页号为索引查页表,得到对应的块号,根据关系式:
                      绝对地址=块号×块长+单元号
                      
                      页表和作业表的一般格式
                      计算出欲访问的主存单元的地址。因此,虽然作业存放在若干个不连续的块中,但在作业执行中总是能按正确的地址进行存取。
                      相联存储器和快表
                      页表可以存放在一组寄存器中,地址转换时只要从相应寄存器中取值就可得到块号,这虽然方便了地址转换,但硬件花费代价太高,如果把页表放在主存中就可降低计算机的成本。但是,当要按给定的逻辑地址进行读/写时,必须访问两次主存。第一次按页号读出页表中相应栏内容的块号,第二次根据计算出来的绝对地址进行读/写,降低了运算速度。
                      为了提高运算速度,通常都设置一个专用的高速存储器,用来存放页表的一部分,这种高速存储器称为相联存储器(Associative Memory),存放在相联存储器中的页表称为快表。相联存储器的存取时间是远小于主存的,但造价高,故一般都是小容量的,例如Intel 80486的快表为32个单元。
                      根据程序执行局部性的特点,即它在一定时间内总是经常访问某些页,若把这些页登记在快表中,无疑将大大加快指令的执行速度。快表的格式如下:
                      
                      它指出已在快表中的页及其对应主存的块号。有了快表后,绝对地址形成的过程是,按逻辑地址中的页号查快表,若该页已登记在快表中,则由块号和单元号形成绝对地址;若快表中查不到对应页号,则再查主存中的页表而形成绝对地址,同时将该页登记到快表中。当快表填满后,又要在快表中登记新页时,则需在快表中按一定策略淘汰一个旧的登记项,最简单的策略是“先进先出”,总是淘汰最先登记的那一页。
                      采用相联存储器的方法后,地址转换时间大大下降。假定访问主存的时间为100×10-9s,访问相联存储器的时间为20×10-9s,相联存储器为32个单元时查快表的命中率可达90%,于是按逻辑地址进行存取的平均时间为:
                      (100+20)×90%+(100+100+20)×(1-90%)=130×10-9s
                      比两次访问主存的时间100×10-9s×2+20×10-9s=220×10-9s下降了四成多。
                      同样,整个系统也只有一个相联存储器,只有占用CPU者才占有相联存储器。在多道程序中,当某道程序让出处理器时,应同时让出相联存储器。由于快表是动态变化的,所以让出相联存储器时应把快表保护好以便再执行时使用。当一道程序占用处理器时,除置页表控制寄存器外还应将它的快表送入相联存储器。
               分段式存储管理的基本原理
               分段式存储管理是以段为单位进行存储分配,为此提供如下形式的两维逻辑地址:
               段号:段内地址
               在分页式存储管理中,页的划分——即逻辑地址划分为页号和单元号是用户不可见的,连续的用户地址空间将根据页框架(块)的大小自动分页;而在分段式存储管理中,地址结构是用户可见的,即用户知道逻辑地址如何划分为段号和单元号,用户在程序设计时,每个段的最大长度受到地址结构的限制,进一步,每一个程序中允许的最多段数也可能受到限制。例如,PDP-11/45的段址结构为:段号占3位,单元号占13位,也就是一个作业最多可分8段,每段的长度可达8KB。
               分段式存储管理的实现可以基于可变分区存储管理的原理,为作业的每一段分配一个连续的主存空间,而各段之间可以不连续。在进行存储分配时,应为进入主存的每个用户作业建立一张段表,各段在主存的情况可用一张段表来记录,它指出主存储器中每个分段的起始地址和长度。同时段式存储管理系统包括一张作业表,将这些作业的段表进行登记,每个作业在作业表中有一个登记项。作业表和段表的一般格式如下图所示。
               
               段表和作业表的一般格式
               段表表目实际上起到了基址/限长寄存器的作用。作业执行时通过段表可将逻辑地址转换成绝对地址。由于每个作业都有自己的段表,地址转换应按各自的段表进行。类似于分页存储器那样,分段存储器也设置一个段表控制寄存器,用来存放当前占用处理器的作业的段表始址和长度。段式存储管理的地址转换和存储保护流程如下图所示。
               
               分段式存储管理的地址转换和存储保护
               虚拟存储管理基本概念
               在前面介绍的各种存储管理方式中,必须为作业分配足够的存储空间,以装入有关作业的全部信息,当然作业的大小不能超出主存的可用空间,否则这个作业是无法运行的。但当把有关作业的全部信息都装入主存储器后,作业执行时实际上不是同时使用全部信息的,有些部分运行一遍便再也不用,甚至有些部分在作业执行的整个过程中都不会被使用到(如错误处理部分)。进程在运行时不用的,或暂时不用的,或某种条件下才用的程序和数据,全部驻留于内存中是对宝贵的主存资源的一种浪费,大大降低了主存利用率。于是,提出了这样的问题:作业提交时,先全部进入辅助存储器,作业投入运行时,能否不把作业的全部信息同时装入主存储器,而是将其中当前使用部分先装入主存储器,其余暂时不用的部分先存放在作为主存扩充的辅助存储器中,待用到这些信息时,再由系统自动把它们装入到主存储器中,这就是虚拟存储器的基本思路。如果“部分装入、部分对换”这个问题能解决的话,那么当主存空间小于作业需要量时,这个作业也能执行;更进一步,多个作业存储总量超出主存总容量时,也可以把它们全部装入主存,实现多道程序运行。这样,不仅使主存空间能充分地被利用,而且用户编制程序时可以不必考虑主存储器的实际容量,允许用户的逻辑地址空间大于主存储器的绝对地址空间。对于用户来说,好像计算机系统具有一个容量很大的主存储器,把它称做为“虚拟存储器”(Virtual Memory)。
               对虚拟存储器的定义如下:具有部分装入和部分对换功能,能从逻辑上对内存容量进行大幅度扩充,使用方便的一种存储器系统。实际上是为扩大主存而采用的一种设计技巧。虚拟存储器的容量与主存大小无关。虚拟存储器的实现对用户来说是感觉不到的,他们总以为有足够的主存空间可容纳他的作业。
 
       进程
        简单而言,一个进程就是一个正在运行的程序。一般来说,一个进程至少应该包括以下几个方面的内容。
        .相应的程序:进程既然是一个正在运行的程序,当然需要有相应程序的代码和数据。
        .CPU上下文:指程序在运行时,CPU中各种寄存器的当前值,包括:程序计数器,用于记录将要取出的指令的地址;程序状态字,用于记录处理器的运行状态信息;通用寄存器,用于存放数据或地址;段寄存器,用于存放程序中各个段的地址;栈指针寄存器,用于记录栈顶的当前位置。
        .一组系统资源:包括操作系统用来管理进程的数据结构、进程的内存地址空间、进程正在使用的文件等。
        进程有动态性、独立性和并发行三个特性。
        (1)动态性。进程是一个正在运行的程序,而程序的运行状态是在不断地变化的。例如,当一个程序在运行的时候,每执行完一条指令,PC寄存器的值就会增加,指向下一条即将执行的指令。而CPU中用来存放数据和地址的那些通用寄存器,它们的值肯定也不断地变化。另外,堆和栈的内容也在不断地变化,每当发生一次函数调用时,就会在栈中分配一块空间,用来存放此次函数调用的参数和局部变量。而当函数调用结束后,这块栈空间就会被释放掉。
        (2)独立性。一个进程是一个独立的实体,是计算机系统资源的使用单位。每个进程都有自己的运行上下文和内部状态,在它运行的时候独立于其他的进程。
        (3)并发性。从宏观上来看,在系统中同时有多个进程存在,它们相互独立地运行。
        下图表示四个进程A、B、C、D在系统中并发地运行。从中可以看出,虽然从宏观上来说,这四个进程都是在系统中运行,但从微观上来看,在任何一个特定的时刻,只有一个进程在CPU上运行。从时间上来看,开始是进程A在运行,然后是进程B在运行,然后是进程C和进程D。接下来又轮到了进程A去运行。因此,在单CPU的情形下,所谓的并发性,指的是宏观上并发运行,而微观上还是顺序运行,各个进程轮流去使用CPU资源。
        
        四个进程在并发运行
        在具体实现上,以CPU中的程序计数器PC为例,真正物理上的PC寄存器只有一个。当四个进程在轮流执行时,PC取值的运动轨迹是先在进程A内部流动,然后再到进程B的内部流动,再到进程C和D。从进程的独立性角度来说,每个进程都有“自己”独立的PC寄存器,即逻辑上的PC寄存器,它们的取值相互独立、互不影响。所谓的逻辑PC,其实就是一个内存变量。例如,在上图中,当进程A要执行的时候,就把A的逻辑PC的值拷贝到物理PC中,然后开始运行。当轮到B运行的时候,先把物理PC的当前值保存到A的逻辑PC中,然后再把B的逻辑PC的值装入到物理PC中,即可运行。这样就实现了各个进程的轮流运行。
 
       内存
        除了CPU,内存也是影响系统性能的最常见的瓶颈之一。看系统内存是否够用的一个重要参考就是分页文件的数目,分页文件是硬盘上的真实文件,当操作系统缺少物理内存时,它就会把内存中的数据挪到分页文件中去,如果单位时间内此类文件使用频繁(每秒个数大于5),那就应该考虑增加内存。具体考察内存的性能的参数包括内存利用率、物理内存和虚拟内存的大小。
 
       页式存储管理
               基本原理
               分区存储管理的一个特点是连续性,每个程序都分得一片连续的内存区域。这种连续性将导致碎片问题,包括固定分区中的内碎片和可变分区中的外碎片。为了解决这些问题,人们又提出了页式存储管理方案。它的基本出发点是打破存储分配的连续性,使一个程序的逻辑地址空间可以分布在若干个离散的内存块上,从而达到充分利用内存,提高内存利用率的目的。
               页式存储管理的基本思路是:一方面,把物理内存划分为许多个固定大小的内存块,称为物理页面(physical page),或页框(page frame)。另一方面,把逻辑地址空间也划分为大小相同的块,称为逻辑页面(logical page),或简称为页面(page)。页面的大小要求是2n,一般在512B到8KB之间。当一个用户程序被装入内存时,不是以整个程序为单位,把它存放在一整块连续的区域,而是以页面为单位来进行分配。对于一个大小为N个页面的程序,需要有N个空闲的物理页面把它装进来,当然,这些物理页面不一定是连续的。
               下图是一个具体的例子。各个任务的逻辑地址空间和内存的物理地址空间被划分为1KB大小的页面。任务1有两个页面,任务2有三个页面,任务3有一个页面。当这三个任务被装入内存后,它们在内存空间的分布可能是:任务1的两个页面分别存放在第5和第6个物理页面中,它们碰巧被放在了一起。任务2的三个页面分别存放在第2、第4和第7个物理页面中。也就是说,虽然它们在逻辑地址空间是三个连续的页面,但在物理地址空间却被分散在内存的不同位置。最后,任务3的这个页面被存放在第8个物理页面中。
               
               页式存储管理的一个例子
               在实现页式存储管理的时候,需要解决以下的几个问题:
               .数据结构:用于存储管理的数据结构是什么?
               .内存的分配与回收:当一个任务到来时,如何给它分配内存空间?当一个任务运行结束后,如何回收它所占用的内存空间?
               .地址映射:当一个任务被加载到内存后,可能被分散地存放在若干个不连续的物理页面当中。在这种情形下,如何把程序中使用的逻辑地址转换为内存访问时的物理地址,以确保它能正确地运行。
               数据结构
               在页式存储管理中,最主要的数据结构有两个。
               .页表:页表给出了任务的逻辑页面号与内存中的物理页面号之间的对应关系。
               .物理页面表:用来描述内存空间中各个物理页面的使用分配状况。在具体实现上,可以采用位示图或空闲页面链表等方法。
               下图是页表的一个例子。在任务的逻辑地址空间当中,总共有4个页面,即页面0、页面1、页面2和页面3。页表描述的是逻辑页面号与物理页面号之间的对应关系,即每一个逻辑页面存放在哪一个物理页面中。页表的下标是逻辑页面号,从0到3。相应的页表项存放的就是该逻辑页面所对应的物理页面号。在本例中,任务的4个逻辑页面分别存放在第1、第4、第3和第7个物理页面中。
               
               页表示例
               内存的分配与回收
               当一个任务到来时,需要给它分配相应的内存空间,即将其每一个逻辑页面都装入到内存当中。显然,内存的分配与回收算法与物理页面表的实现方法是密切相关的。以位示图为例,内存的分配过程是这样的:
               (1)对于一个新来的任务,计算它所需要的页面数N。然后查看位示图,看是否还有N个空闲的物理页面。
               (2)如果有足够的空闲物理页面,就去申请一个页表,其长度为N,并把页表的起始地址填入到该任务的任务控制块TCB当中。
               (3)分配N个空闲的物理页面,把它们的编号填入到页表中。这样,就建立了逻辑页面与物理页面之间的对应关系。
               (4)修改位示图,对刚刚被占用的那些物理页面进行标记。
               当一个任务运行结束,释放了它所占用的内存空间后,需要对这些物理页面进行回收,并对位示图的内容进行相应的修改。
               地址映射
               如前所述,当一个任务被加载到内存后,它的各个连续的逻辑页面,被分散地存放在若干个不连续的物理页面当中。在这种情形下,为了保证程序能够正确地运行,需要把程序中使用的逻辑地址转换为内存访问时的物理地址,也就是地址映射。
               那么如何将一个逻辑地址映射为相应的物理地址呢?在页式存储管理当中,连续的逻辑地址空间被划分为一个个的逻辑页面,这些逻辑页面被装入到不同的物理页面当中。也就是说,系统是以页面为单位来进行处理的,而不是以一个个的字节为单位。因此,地址映射的基本思路是:
               .逻辑地址分析:对于给定的一个逻辑地址,找到它所在的逻辑页面,以及它在页面内的偏移地址;
               .页表查找:根据逻辑页面号,从页表中找到它所对应的物理页面号;
               .物理地址合成:根据物理页面号及页内偏移地址,确定最终的物理地址。
                      逻辑地址分析
                      由于页面的大小一般都是2的整数次幂,因此,人们可以很方便地进行逻辑地址的分析。具体来说,对于给定的一个逻辑地址,可以直接把它的高位部分作为逻辑页面号,把它的低位部分作为页内偏移地址。例如,假设页面的大小是4KB,即212,逻辑地址为32位。那么在一个逻辑地址当中,最低的12位就是页内偏移地址,而剩下的20位就是逻辑页面号。
                      下图是逻辑地址分析的一个例子,在这个例子中,逻辑地址用十六进制形式表示。假设页面的大小为1KB,逻辑地址为0x3BAD。在这种情形下,首先把这个十六进制的地址展开为二进制的形式。然后,由于页面的大小为1KB,即2的10次方,所以这个逻辑地址的最低10位,就表示页内偏移地址,而剩下的最高6位,就表示逻辑页面号。因此,该地址的逻辑页面号是0x0E,页内偏移地址是0x03AD。
                      
                      逻辑地址分析的例子
                      如果逻辑地址不是用十六进制,而是用十进制的形式来表示,那么有两种做法:一是先把它转换为十六进制的形式,然后重复刚才的步骤。二是采用如下的计算方法:
                      逻辑页面号=逻辑地址/页面大小
                      页内偏移量=逻辑地址%页面大小
                      用页面大小去除逻辑地址,得到的商就是逻辑页面号;得到的余数就是页内偏移地址。例如,假设页面的大小为2KB,现在要计算逻辑地址7145的逻辑页面号和页内偏移地址。用2048去除7145,得到的商是3,余数是1001。所以这个逻辑地址的逻辑页面号是3,页内偏移地址是1001。实际上,这个算法和刚才的十六进制的方法是完全等价的。从二进制运算的角度来看,一个是右移操作,一个是除法操作。把一个整数右移N位等价于把它除以2N
                      页表查找
                      对于给定的一个逻辑地址,如果知道其逻辑页面号,就可以去查找页表,从中找到相应的物理页面号。
                      在具体实现上,页表通常是保存在内核的地址空间中,因为它是操作系统的一个数据结构。另外,为了能够访问页表的内容,在硬件上要增加一对寄存器。一个是页表基地址寄存器,用来指向页表的起始地址;另一个是页表长度寄存器,用来指示页表的大小,即对于当前任务,它总共包含有多少个页面。操作系统在进行任务切换的时候,会去更新这两个寄存器当中的内容。
                      物理地址合成
                      对于给定的一个逻辑地址,如果已经知道了它所对应的物理页面号和页内偏移地址,可以采用简单的叠加算法,计算出最终的物理地址。假设物理页面号为f,页内偏移地址为offset,每个页面的大小为2n,那么相应的物理地址为:f×2n+offset。
                      下图是页式存储管理当中的地址映射机制,也是以上各个步骤的一个综合。假设在程序的运行过程中,需要去访问某个内存单元,因此就给出了这个内存单元的逻辑地址。如前所述,这个逻辑地址由两部分组成,一是逻辑页面号,二是页内偏移地址。这个分析工作是由硬件自动来完成的,对用户是透明的。在页表基地址寄存器当中,存放的是当前任务的页表首地址。将这个首地址与逻辑页面号相加,就找到相应的页表项。里面存放的是这个逻辑页面所对应的物理页面号。将这个物理页面号取出来,与页内偏移地址进行组合,从而得到最终的物理地址。然后就可以用这个物理地址去访问内存。
                      
                      页式存储管理中的地址映射
                      现有的这种地址映射方案,虽然能够实现从逻辑地址到物理地址的转换,但它有一个很大的问题。当程序运行时需要去访问某个内存单元,例如,去读写内存当中的一个数据,或是去内存取一条指令,需要访问2次内存。第一次是去访问页表,取出物理页面号;第二次才是真正去访问数据或指令。也就是说,内存的访问效率只有50%。这样,就会降低获取数据的存取速度,进而影响到整个系统的使用效率。为了解决这个问题,人们又引入了快表的概念。它的基本思路来源于对程序运行过程的一个观察结果。对于绝大多数的程序,它们在运行时倾向于集中地访问一小部分的页面。因此,对于它们的页表来说,在一定时间内,只有一小部分的页表项会被经常地访问,而其他的页表项则很少使用。根据这个观察结果,人们在MMU中增加了一种特殊的快速查找硬件:TLB(Translation Lookaside Buffer),或者叫关联存储器,用来存放那些最常用的页表项。这种硬件设备能够把逻辑页面号直接映射为相应的物理页面号,不需要再去访问内存当中的页表,这样就缩短了页表的查找时间。
                      在TLB方式下,地址映射的过程略有不同。当一个逻辑地址到来时,它首先会到TLB当中去查找,看这个逻辑页面号所在的页表项是否包含在TLB当中,这个查找的速度是非常快的,因为它是以并行的方式进行。如果能够找到的话,就直接从TLB中把相应的物理页面号取出来,与页内偏移地址拼接成最终的物理地址。如果在TLB中没有找到该逻辑页面,那只能采用通常的地址映射方法,去访问内存当中的页表。接下来,硬件还会在TLB当中寻找一个空闲单元,如果没有空闲单元,就把某一个页表项驱逐出来,然后把刚刚访问过的这个页表项添加到TLB当中。这样,如果下次再来访问这个页面,就可以在TLB中找到它。
                      页式存储管理方案的优点是:
                      (1)没有外碎片,而且内碎片的大小不会超过页面的大小。这是因为系统是以页面来作为内存分配的基本单位,每一个页面都能够用上,不会浪费。只是在任务的某一些页面当中,可能没有装满,里面有一些内碎片。
                      (2)程序不必连续存放,它可以分散地存放在内存的不同位置,从而提高了内存利用率。
                      (3)便于管理。
                      页式存储管理方案的缺点主要有:
                      (1)程序必须全部装入内存,才能够运行。如果一个程序的规模大于当前的空闲空间的总和,那么它就无法运行。
                      (2)操作系统必须为每一个任务都维护一张页表,开销比较大。简单的页表结构已经不能满足要求,必须设计出更为复杂的结构,如多级页表结构、哈希页表结构、反置页表等。
   题号导航      2011年上半年 数据库系统工程师 上午试卷 综合知识   本试卷我的完整做题情况  
1 /
2 /
3 /
4 /
5 /
6 /
7 /
8 /
9 /
10 /
11 /
12 /
13 /
14 /
15 /
 
16 /
17 /
18 /
19 /
20 /
21 /
22 /
23 /
24 /
25 /
26 /
27 /
28 /
29 /
30 /
 
31 /
32 /
33 /
34 /
35 /
36 /
37 /
38 /
39 /
40 /
41 /
42 /
43 /
44 /
45 /
 
46 /
47 /
48 /
49 /
50 /
51 /
52 /
53 /
54 /
55 /
56 /
57 /
58 /
59 /
60 /
 
61 /
62 /
63 /
64 /
65 /
66 /
67 /
68 /
69 /
70 /
71 /
72 /
73 /
74 /
75 /
 
第27题    在手机中做本题