计算机操作系统第六章.ppt-得力文库

资源描述

《计算机操作系统第六章.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统第六章.ppt（41页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM主要内容基础知识请求分页存储管理请求分段存储管理第6章虚拟存储器1操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM6.1基础知识基础知识6.1.1覆盖技术覆盖技术覆盖技术，是程序运行过程中，在不同时刻把同一存储区分配给不同程序段或数据段，实现存储区共享的一种内存分配技术。覆盖技术通常与单一连续区分配、固定分区分配和动态分区分配等存储管理技术配合使用。每一个用户程序都被分为若干

2、程序段，一部分是经常要用的基本部分，作为常驻程序；另一部分不经常使用，可以让它们在需要时临时装入。当一段在内存中的程序运行完毕（或者暂时不运行）时，可以令它们放弃驻留权，让另一段程序占用它在内存中的位置。2操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM例如，某进程的程序段由例如，某进程的程序段由A、B、C、D、E、F、G和和H等等8个程序段组成。它们之间的调用关系如图（个程序段组成。它们之间的调用关系如图（a）所示。所示。3操作系统操作系统操作系统操作系统操作系统二十一世纪计算机

3、本科教育OPERATING SYSTERM交换(Swap)技术，是指将内存中某进程的程序和数据（全部或部分）写入外存交换区中，腾出来的内存空间供其它进程使用。待内存有空闲空间后再将它从外存交换区装入内存。一、磁盘交换区管理磁盘交换区是一个数据的暂存处。系统可根据内存的“拥挤”程度将信息调往交换区或者从交换区调入。6.1.2 6.1.2 交换技术交换技术4操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM操作系统管理下磁盘空间被划分为两部分：文件操作系统管理下磁盘空间被划分为两部分：文件区和交换区。二者的区别主要有

4、区和交换区。二者的区别主要有3点：点：存存储储方方式式不不同同。文件区中的信息是以文件形式存放的，为了提高空间利用率，一般采取离散存储方式；而交换区是按字符流方式存放，多采用连续存储形式。访访问问速速度度不不同同。文件区的存储空间特别大，为了提高检索效率一般通过建立目录对文件实现访问，也就是间接地址访问；而交换区空间较小，可按外存地址直接访问，因此速度快。存存储储时时间间不不同同。文件区的存储适合于较长久的数据存储；而交换区作为临时数据的存放处，只存放短期的数据。5操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM

5、二、进程调出二、进程调出进程调出操作，需要选择一个近期无运行要求的进程调出内存。这里，处于阻塞状态的进程是首选的，其次是就绪状态的进程，一个正在共享的程序不在考虑之列。选择过程中的另一个参数是进程的优先级或响应比。三、进程调入三、进程调入进程调入操作需要选择一个具有运行条件且最迫切的进程，将它调入。一般来说，选择过程就是前面所讲的“中级调度”，选出的进程可通过“进程激活”装入内存。一般来讲，系统选择的对象是处于“挂起就绪”状态的进程，处于“挂起阻塞”状态的进程不在考虑之列。6操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SY

6、STERM6.1.3 6.1.3 局部性原理局部性原理从程序对操作数的访问来看，一般情况下，一段程序访问的操作数也都局部于某个数据块中。因此在一个较短的时间内，程序执行中对内存地址的访问往往局限于一个较小的空间上。1968年，P.Denning提出了一个著名的“局部性原理”，并通过一幅运行图予以说明（见图所示）。7操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM 虚拟存储器虚拟存储器（VirtualMemory）一个进程运行时，可不必将其全部装载到内存中，只须把当前运行的部分程序和可能访问的数据块装入内存即可。

7、随着进程运行的不断推进，其余部分程序和数据可随时装入。这样做可实现小内存运行大程序的设想。从逻辑上说，系统拥有一个容量很大的存储器，这就是人们常说的虚拟存储器。l多次性 l虚拟性 l离散性 l对换性 8操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM 6.2 6.2 请求分页存储管理请求分页存储管理请求分页（DemandPaging）存储管理是在普通的分页管理基础上，采用了虚拟技术发展起来的。由于分页管理中的页面长度是固定的，调出调入比较容易实现，因此目前许多操作系统中都支持这种管理方式。6.2.1 6.2.1

8、地址变换地址变换硬件上除了支持请求分页管理的内存和外存外，还要有相应的页表和地址变换机制，以及出现缺页（即某个需要运行的页面不在内存）时的中断响应机制等。9操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM1 1页表页表虚拟分页系统与普通分页系统的区别是，进程只有一部分页面进入内存。因此页表需要记录哪些页面在内存，哪些不在内存。并且，页表中还要记录页面的外存位置，以便当某个需要运行的页面不在内存时，系统能够立即找到它，将它装载进来。2 2地址变换机制地址变换机制当调度一个进程时，系统将其页表首址装入CPU中的页

9、表控制寄存器。运行中用相对地址的高端部分作为页号去检索页表，看该页是否已在内存。若已在内存就按普通分页机制的方式直接生成物理地址，并将访问标志和修改标志设置好。如果该页不在内存，则产生缺页中断信号，通过中断处理过程将缺页装入。10操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM3 3中断处理机制中断处理机制缺页中断是指令执行过程中产生的中断，而非（一般的中断）在一条指令执行完成后产生的。当CPU执行指令希望访问一个不在内存的页面时，将产生缺页中断，系统开始运行中断处理程序。此时指令计数器（PC）的值尚未来得及增加

10、就被压入堆栈，因此压入的断点必然是本次被中断的指令地址，而非下一条指令的地址。11操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM中断处理过程如下：中断处理过程如下：(1)保留进程上下文。(2)判断内存是否有空闲帧？若有，则获取一个帧号No，转（4）。(3)腾出一个空闲帧，即：(3)-1调用置换算法，选择一个淘汰页PTj。(3)-2PTj(S)=0；(3)-3No=PTj(F);。(3)-4若该页曾修改过，则：(3)-4-1请求外存交换区上一个空闲块B。(3)-4-2PTj(D)=B的外存地址。(3)-4-3启动

11、I/O管理程序，将该页写到外存上。(4)按页表中提供的缺页外存位置，启动I/O，将缺页装入空闲帧中。(5)修改页表的状态字段。PTi(F)=No；PTi(S)=1。(6)结束。12操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM地地址址变变换换流流程程13操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM虚拟分页系统中的页面分配应当以减少缺页率为目标。实践证明，进程占用的存储容量越小，缺页中断率就越高。Madnick曾经描述了一个真正

12、的System360系统中的程序缺页中断曲线（称为下降曲线），见图所示。14操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM 分配算法有以下分配算法有以下3 3种：种：l l平平均均分分配配法法系统的可用空间平均分配给所有进程，让它们都占有相等数量的帧。这样分配对短作业来说是很有利的。而对于一些较大的进程，缺页率必然居高不下。l l优先权分配法优先权分配法考虑进程的优先运行权，给高优先的进程分配较多的帧，使它的缺页率相对少一些。这里，我们可把优先权理解为高响应比、高优先级、最短剩余时间优先等。l l比例分配法

13、比例分配法这种分配方法比较公平，小进程分配小空间，大进程分配大空间。当可用空间为M个帧，系统当前的进程数为n，每个进程的页面数量为si，那么按比例分配法，应当分配给进程i的页数pi为：15操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM页面置换，页面置换，是指在内存空间已被装满而又要装入新页时，必须按某种算法将内存中的某页置换为一个新页。下面介绍几种比较典型的页面置换算法。1 1OPTOPT（最佳置换）算法最佳置换）算法OPT算法是一种理想化了的页面置换算法。该算法每次选择的淘汰页总是不再使用的，或者最长时间不再

14、使用的页面，尽量避免刚调出去又要立即调入。2 2FIFOFIFO（先进先出）算法先进先出）算法这种算法的出发点是“先装入内存者先被置换”。系统总是把驻留在内存中时间最长的页面（常驻的除外）作为被淘汰的对象。6.2.2 6.2.2 置换算法置换算法 16操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM 3 3LRULRU（最近最久未使用）算法最近最久未使用）算法被置换的页面是最长时间未访问的页面。这种算法所依据的原理是程序执行时所具有的局部性，即那些刚被使用过的页面可能马上再次被使用，而那些最久未使用的页面一般

15、不会马上被用到。4 4ClockClock（钟表算法）算法钟表算法）算法这是一个建立在循环检测基础上的LRU近似算法，试图以较小的开销获得接近LRU的性能。该算法中将被置换的候选帧集合构成一个环状缓冲区，并设一个循环移动指针。初始时，该指针指向缓冲区的头部。当某页被选择置换后，指针将顺序指向缓冲区的下一个帧。环状缓冲区中的每个候选帧关联一个“访问位”，记作A，当某帧的A=0时，说明该帧最近未被访问。显然，一个刚刚调入页面的帧，以及刚刚访问过的帧，其A=1。17操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM5 5

16、改进的改进的ClockClock算法算法一个提高Clock算法效率的方法是，为每个帧增设一个关联的“修改位”，记作M。如果M=1表示该帧中的页面被修改了，置换之前必须写到外存上。若将访问情况与修改情况一起考虑，每一帧可处于4种情况之一。lA=0且M=0：该帧中所存的页面最近没有访问，也没有修改。lA=1且M=0：该帧中所存的页面最近访问过，但没有修改。lA=0且M=1：该帧中所存的页面最近没有访问，但修改了。lA=1且M=1：该帧中所存的页面最近访问过，也修改过。18操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTE

17、RM据此给出改进的Clock算法的处理过程：（1）从指针当前位置开始，循环扫描候选帧，遇到的第1个A=0且M=0的帧，将该帧中的页面置换后返回。（2）若循环一周后没有找到可置换的帧，则继续循环扫描，遇到的第1个A=0且M=1的帧，将该帧中的页面置换后返回。在这个过程中，每跳过一个帧就将它的访问位A设置为0。（3）若第（2）步仍没有找到可置换的帧，则重复（1）和（2）必将能够找到一个可置换的帧。19操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM20操作系统操作系统操作系统操作系统操

18、作系统二十一世纪计算机本科教育OPERATING SYSTERM 6几种算法的性能比较置换算法的选择，将直接影响到内存的利用率和系统效率。对于上述四种算法，计算机学者Baer曾于己于1980年做过一个实验，选取的页面尺寸为256个字，分别实验了6、8、10、12、14帧的情况。当分配的帧数比较多时，四种算法的区别不太明显；而当分配的比较少时，它们的区别就相当显著了。特别是，当进程只有6个帧时，FIFO算法比OPT算法的缺页次数提高1倍还多。21操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM实验结果如图所示。其中

19、，横坐标是帧数，纵坐标是缺页次数。22操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM一、页面调入策略一、页面调入策略在调页过程中有两个策略：一个是“随用随调”策略，另一个是“预调页”策略。“预调页”策略的好处是：一次读多个连续的页面，可以减少磁头移动的时间，对系统效率提高有很大好处。另一个好处是，当发现缺页已在内存时，当前进程不必让出控制权，仅仅将缺页转移到用户区，修改页表后就可继续运行。6.2.3 6.2.3 驻留集和工作集驻留集和工作集 23操作系统操作系统操作系统操作系统操

20、作系统二十一世纪计算机本科教育OPERATING SYSTERM二、驻留集管理二、驻留集管理驻驻留留集集，是进程在内存中的页面集合，驻留集尺寸是驻留在内存中的页面数量。管理驻留集的方式有以下管理驻留集的方式有以下3 3种：种：（1）固定分配局部置换（2）可变分配全局置换（3）可变分配局部置换24操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM三、工作集三、工作集工作集（working set）的概念是Denning提出来的，对虚拟存储器的设计产生过重大影响。一个进程的工作集W（t,）表示在时间t-到t之间进程引

21、用的一串页面；工作集的尺寸记作w（t,），指的是W（t,）中的页面数。w（t,）是的单调函数，也就是说，时间段越长，引用的页面越多，直到接近实际所需的页面总数（实际操作中，时间段长度往往用执行指令的数量来度量，而不是实际经历的时间）。在进程执行期间可以容易地确定该进程对存储空间的需求，也就是它的工作集尺寸。操作系统可以用这种方法决定给谁分配更多的帧，以及哪个进程应当让出一些帧来。25操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM下面是按照工作集决定驻留集的策略下面是按照工作集决定驻留集的策略工作集策略工作集策

22、略(1)监视各进程的工作集。监视各进程的工作集。(2)周周期期性性地地从从一一个个进进程程中中调调出出那那些些不不在在它它的的工作集中的页，令其释放部分帧。工作集中的页，令其释放部分帧。(3)当当一一个个进进程程的的驻驻留留集集包包含含了了它它的的工工作作集集时时，才才可可以以执执行行该该进进程程。否否则则为为进进程程增增加加新新帧帧或或者暂者暂缓调度该进程。缓调度该进程。26操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM四、一种怪现象四、一种怪现象在谈到驻留集时，有一种怪现象不得不提，那就是Belaly于1

23、969年指出的，在FIFO算法中，有时增加更多的物理存储块后反倒导致利用率下降。导致这种怪现象的页面走向虽然是罕见的，然而必然还和其它因素有关。这说明，不能将“进程的可用帧越多缺页率就越低”这一结论绝对化。27操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM6.2.4 抖动的产生和预防抖动（Thrashing）又称颠簸，是指刚被调出去的页需要马上被调回，刚调回不久又要马上被调出。频繁调入调出，使系统的大部分时间都花费在内存和外存之间的来回折腾上。抖动主要表现为磁盘I/O极度繁忙，而处理机大量时间空闲。28操作

24、系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM一、抖动的产生及应对措施产生抖动的原因归根到底是内存驻留的进程太多，下图是处理机利用率与多道程序度（即进程数量）之间的关系曲线。29操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM从图中可以看出，当多道程序度达到M点时，处理机利用率最大。当系统处于M点左边的位置，也就是说驻留在内存的进程数量较少时，处理机的利用率不高是因为负荷太轻所致。此时应当增加内存的进程数量方可提高利用率。如果系统处于M

25、点的右边位置，也就是说内存的驻留进程较多时，处理机的利用率不高是因为系统过载而致。此种情况下，减少内存的进程数量是提高处理机利用率的当务之急。30操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM二、抖动预防二、抖动预防下面的方法可以预防抖动的发生。1在处理机调度中引入工作集策略2采用局部置换策略防止抖动扩散3挂起部分进程一般选择缺页进程、最后被激活的进程、最大进程驻留集最小的进程、剩余执行时间最多的进程等。4L=S准则这一准则中，L是产生缺页的平均时间，S是系统处理缺页的平均时间。理论证明，当L=S是，处理机的

26、利用率最高。该理论也得到实践的检验。31操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM6.3 6.3 请求分段存储管理请求分段存储管理1段表为了实现段的动态管理，我们要为每个进程设置一个段表ST，并在ST中设立一些“控制位”记录该段的控制信息32操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM2地址变换33操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYST

27、ERM3缺段中断机制与缺页中断类似，缺段中断也是指令执行过程中产生的中断，而不是产生在一条指令执行完成后。也就是说，进程执行一条指令产生缺段中断时，压入堆栈的断点是当前指令的地址。当缺段被装入内存后，该段变成了“实段”。进程再次恢复运行时，CPU将重新执行这条指令。4中断处理程序当第i#段是一个缺段，则缺段中断处理过程为：(1)阻塞进程。(2)LengthSTi(长度)。(3)检索“内存分配表”，若存在一个独立的内存块长度Length，则：(3)-1将该内存块分配给进程。34操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SY

28、STERM(3)-2首址B0；转(6)。(4)若内存可用空间总和Length，则：(4)-1调用某种置换算法，选择一个内存中的段。(4)-2若该段被修改过，则，将它写回外存。(4)-3修改“内存分配表”。(4)-4转(3)。(5)内存各进程浮动，拼接出一个足够大的内存空间；将该内存块分配给进程；首址B0。(6)从外存读入缺段，存入B0处。(7)STi(B)B0；STi(S)1。(8)修改内存分配表。(9)唤醒进程。(10)结束。35操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM6.3.2 6.3.2 分段共享分

29、段共享 1共享段表SST 为了实现段的共享，系统设一个“共享段表”（SST，Sharing Segment Table），记载各个共享段的使用情况。任何一个进程调用共享段时，系统都将访问该表。2共享段的分配共享段的空间分配与一般段的分配有所不同，共享段在内存中只驻留一个备份，所有共享该段的进程都通过自己的逻辑段号映射到该共享段上。36操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM分配过程为：分配过程为：（1）当系统为一个进程分配地址空间并创建段表ST时，若发现该进程调用了某个共享段，比如说，Sqrt段，系统检

30、查内存中的共享段表SST。（2）若SST中已包含Sqrt段，则系统就将Sqrt段的内存基地址拷贝到进程的ST中，并将SST中关于Sqrt段的共享计数字段加1，转第（4）步。（3）若SST中未包含Sqrt段，说明该进程是第一个使用该共享段Sqrt的进程。系统需要为该共享段分配存储空间，将该段加载到内存中。此外，还要在SST中增加一个表项，将共享段的信息填入，并将共享计数字段加1。（4）将进程的信息填入SST的相关字段中。37操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM 3共享段的回收当一个进程被撤消时，其地址空

31、间需要回收。此时系统需要扫描它的段表ST，当发现该进程使用了某个共享段，比如Sqrt段，则：（1）系统扫描内存中的共享段表SST，查找共享段Sqrt。（2）将共享段Sqrt的共享计数字段减1。若其值不为0，说明当前尚有其它进程正在使用该段，撤消SST中关于该进程情况的记载，返回。（3）若共享计数字段的值为0，说明当前已没有进程使用该共享段Sqrt了。应当立即将它从内存中撤消，同时将该段信息从SST中删除。38操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM6.3.3 6.3.3 请求段页式存储管理请求段页式存储管

32、理原理：也称分段加请求分页的存储管理方式。把段划分为若干个页面进行离散存储。系统将一个段的当前页面调入内存，其余的仍驻留在外存上，随时需要随时通过缺页中断装入。硬件支持：处理机中设有段表控制寄存器参与地址映射，存放的内容是段表起始地址和段表长度。在地址结构方面，页面长度和分段长度由系统对控制寄存器的安排来决定。软件支持：在请求段页式管理系统中，缺页置换算法是必须的，而且与纯粹请求分页管理机制中采用的算法相同。39操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM请求段页式存储管理优点：请求段页式管理系统的主要是具有虚拟存储器的功能，并保持了段页式管理的优点：既体现段的独立性，又纳入了页的离散分配，使系统更加灵活。缺点：增加了硬件的成本，系统复杂性提高，而且段表和页表的存储与检索问题突出，对处理机的运行速度影响较大。40操作系统操作系统操作系统操作系统操作系统二十一世纪计算机本科教育OPERATING SYSTERM本章结束本章结束41

展开阅读全文