1、15.3 覆盖与交换技术覆盖与交换技术(内存扩充内存扩充) 问题的提出 物理存储器 物理存储器结构是一维的线性空间，容量有限。 用户程序 用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大得多。 解决办法 内存扩充2 实现内存扩充的方法： 采用覆盖技术 采用交换技术 采用虚拟存储技术3 覆盖技术 将程序结构分层 第0层设置为常驻内存区。 第一层起，为该层中的多个模块设置一个共享覆盖区，其容量与该层中最大模块的容量相当。程序执行到哪个模块就将该模块送到它所共享的覆盖区中。5.3.1 覆盖技术覆盖技术4A、B、C、D、E、F总计190K，实际分配110K5 采用交换技术 在系统盘上开
2、辟一个专门的空间作为内存的扩充，这部分磁盘空间称为“交换区”或“对换区”，由内存管理模块进行管理。 交换区的作用是当内存空间不够时，将暂时不用的进程映像调到磁盘交换区，以腾出内存空间，当再度用到被调出的这部分进程映像时再将其调回内存。5.3.2 交换技术交换技术6交换技术7 1虚拟存储器的基本思想 问题 作业在运行时暂时不用的程序和数据，全部驻留于内存中降低了内存利用率。 解决方法 当作业开始运行时，将当前使用的部分先装入内存，其余部分先存放在外存中，等到用到这些信息时，再由系统自动把它们装入到内存中，这就是虚拟存储器的基本思想。 概念：虚拟存储器（虚拟内存） 是操作系统采用虚拟技术，在不改变
3、物理内存实际大小的情况下提供的逻辑上被扩充了的内存。这种物理上不具备而逻辑上具备的内存就是虚拟内存。补充: 虚拟存储技术8 2. 虚拟存储技术的依据虚拟存储技术的依据 局部性理论（8/2原理） 时间局部性: 是指程序即将用到的信息可能就是目前正在使用的信息。 空间局部性: 是指程序即将用到的信息可能与目前正在使用的信息在空间上相邻或者临近。 局部性理论的应用意义 虚拟存储管理：程序执行时往往会遵循局部原理(时间、空间)访问内存，将部分进程存入内存，结合外存实现虚拟存储。9 3. 虚拟存储技术的硬件技术基础虚拟存储技术的硬件技术基础 相当数量的外存 足以存放多个用户程序 一定容量的内存 程序运行
4、过程中，必须有一部分放在内存 地址变换机构 实现逻辑地址到物理地址的变换105.4 页式管理页式管理5.4.1 页式管理的基本原理页式管理的基本原理页式管理的引入 分区存储管理的主要问题是碎片问题。 问题描述在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户程序利用而浪费。 问题产生原因 作业要求分配的空间连续,主存有足够的空间但因不连续而不能分配 解决问题的思路 程序适应主存。将程序分开存放分页存储管理技术。 11 分页的思想 页(虚拟页)：程序地址空间分成大小相等的页面 块(内存块、页块、页祯、内存页面)：把内存分成与页面大小相等的块。 思想：当
5、一个用户程序装入内存时，针对。一每一页分配一个内存块个作业的若干连续的页，可以分配到内存中若干不连续的块中。121. 内存页面分配与回收页式存储管理的数据结构(1)页表:页表包括用户程序空间的页面与内存块的对应关系。页表每个进程至少一张。5.4.2静态页面管理13 (2)请求表:表明各进程与其分页的页面之间的关联。请求表整个系统一张。图 5.16请求表示例14 (3)存储页面表：表示内存的分配情况。存储页面表一个系统一张，可用位示图表示。图 5.17位示图 155.4.2静态页面管理 2.分配算法 利用页表、请求表、位示图进行分配。图5.18页面分配算法流图163.页式地址变换(1)虚地址（线
6、性地址、逻辑地址）(2)分页地址映射机制 虚地址切分：页号与页内位移划分页号和页内地址的依椐：页的大小。 2X =页大小，X即为页号的最低位CPU字长为16位，页长为1K的地址分割17mov dx,3badh页号01234567第0页第1页01023010231页式管理的地址小结：页大小决定页内位移（地址）的位数，所以在地址划分时以页大小作为划分依据页内地址页大小为1K，以字节（B）为单位划分，可划分为1024个单位，进行编址，表示为0-1023，要表示1023需要10位二进制（11 1 1 1 1 1 1 1 1 ） ， 1KB=210B 18二进制表示虚地址页号页内位移十六进制表示页号、页
7、内位移19(3)地址变换使用二进制方法求物理地址 将逻辑地址线性分割求出页号P和页内位移W：若逻辑地址以十六进制、八进制的形式给出，将逻辑地址转换成二进制；按页的大小分离出页号P和位移量W（低位部分是位移量，高位部分是页号）； 将位移量直接复制到内存地址寄存器的低位部分； 以页号查页表，得到对应块号，将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。20mov dx,3badh页号01234567页号块号0F18233549546A7B0 0 1 1 1 0 1 1 1 0 1 0 1 1 0 1块号OS0123456798BACD0101115P=7HW=3ADH0 0 0 0
8、 0 1 0 1 1 0 1 1 1 0 1 0 1 1 0 1虚地址3BAD，页面大小2K，用二进制方法求物理地址物理地址=5BADH21 使用十进制方法求物理地址 根据逻辑地址求出页号P和页内位移W； 页号P=逻辑地址 % 页大小(%表示整除) 页内位移W=逻辑地址 mod 页大小 根据页号查页表得块号B； 物理地址=块号B页大小+页内位移W 公式说明 物理地址块起始地址块内位移W 块起始地址块长块号 块长=页长 块内位移页内位移 22块号OS0123456798BACD第0块起始地址：0第1块起始地址：块号*页长=1*2K块大小：2K02K4K第2块起始地址：块号*页长=2*2K块起始地
9、址计算mov dx,3badh页号0123456723【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成内存地址。解：求虚地址0AFEH的物理地址：0000 1010 1111 1110P P1 W010 1111 1110MR0100 1010 1111 11104AFEH求虚地址1ADDH的物理地址：0001 1010 1101 1101P3 W010 1101 1101MR0010 1010 1101 11012ADDH24【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，
10、依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。解：转换虚地址 3412：P3412 2048 1W 3412 mod 2048 1364MR=9*2048+1364=19796转换虚地址 7145：P7145 2048 3W7145 mod 2048 1001MR=5*2048+1001=11241问题：块号若为十六进制的字母表示，MR如何计算？(十六进制转换成十进制)例：考虑一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入到有32个物理块的存储器中，问：（1）逻辑地址至少需要多少二进制位表示？ （2）物理地址至少需要多少二进制位表示？分析 ：逻辑
11、地址结构由两个部分组成：前一部分表示该地址所在页面的页号P；后一部分表示页内地址(页内位移)W。物理地址中块号的地址位数决定了块的数量。由于页式存储管理内存空间块的大小与页面大小相同，所以物理地址中块内地址与逻辑地址中的页内地址位数相同。解 ：因为页面数为8=23，故需要3位二进制数表示。每页有1024个字节，1024=210，于是页内地址需要10位二进制数表示。32个物理块，需要5位二进制数表示（32=25）。（1）页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。（2）页的物理地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。26相联存储器和快表 问题
12、提出 在页式存储技术中，每访问一次内存，就要做两次访问内存的工作： 查页表时（页表在内存中）； 访问程序时。 为了提高查页表的速度，将当前常用的一部分页表内容存放到高速缓存（相联存储器）中，存放在相联存储器中的页表称之为快表(TLB-translation lookaside buffer)。 查表时首先在快表中查，只有当快表中没有时才访问内存中的页表，从而减少在内存查表的次数，达到提高查找速度的目的。27作业 习题：P134:5.2, 物理地址计算 有一系统采用页式存储管理，某个作业大小是4GB，页大小为4KB，依次装入内存的第6、5、3、2块， （1）画出页表； （2）试将虚地址5000，
13、12000转换成内存地址。285.4.3 动态页式管理(请求页式管理) 复习: 5.3 覆盖与交换技术 实现内存扩充的方法： 采用覆盖技术 采用交换技术 采用虚拟存储技术 常用的虚拟存储技术 请求分页存储管理 请求分段存储管理 请求段页式存储管理29动态页式管理的思想及实现 分页内存管理方式 静态分页管理 动态分页管理 静态分页管理 基本思想：进程开始执行前，将全部页装入内存。 动态分页管理（请求页式管理） 基本思想：进程开始执行前，只需装入即将运行的页面，然后根据需要载入其他页面。30 请求分页管理要解决的问题 不在内存的页什么时候调入内存？（调入策略） 如何知道要访问的页不在内存？不在内存
14、的页在外存的什么地方？(页表) 当页调入内存时，内存没有空闲块时，应覆盖（淘汰）哪些页？（淘汰策略） 被覆盖（淘汰）的页是否需要回写到辅存？（页表）31 请求页式管理的调入策略 预测调页：分析预测，运行前调入 系统根据作业运行的情况，预测哪些页将要运行，在其运行之前先行调入内存，这样在程序运行的过程中就不会出现缺页中断。 缺点:系统无法预计系统中作业的运行情况，难以实现。 请求调页（请求分页）：缺页请求，运行时调入 进程在执行的过程中，发现要执行的程序或处理的数据不在内存，向系统提出调入相应程序的请求，系统响应用户的请求将它所请求的页调入内存。 32 请求页式管理的页表结构 页表：反映该页是否
15、在内存，在外存的位置，在内存的时间的长短，是否需要回写等。 页号： 块号： 中断位：0 表示该页在内存，1示该页不在内存（需要缺页中断） 辅存地址：该页在辅存的位置 修改位：0 表示该页调入内存后没有修改，1表示页调入内存后修改过 引用位：0 表示最近没有被访问，1表示最近被访问过页号页号 块号块号 中断位中断位 辅存地址辅存地址 修改位修改位 引用位引用位请求分页的页表结构33补充补充:多级页表多级页表 二级页表 问题：页表占用存储空间太大 解决：将页表也分页后，对页表占用的存储空间的分配也采用动态方式分配（部分分配），提高内存利用率。 页表页：将页表分页，称为页表页，大小与页面长度相同。
16、页目录表：为页表页建立的地址索引表称为页目录表。 二级页表机制：页目录表是一级页表、页表页是二级页表，共同构成二级页表机制。34二级页表结构35具有二级页表的地址结构36二级页表机制的地址变换375.4.4 请求页式管理的页面置换算法请求页式管理的页面置换算法当要将辅存中的一页面并送入到全满的内存中时，必须把已在内存中的某一页淘汰掉。用来选择淘汰哪一页的规则叫做置换算法，也称为淘汰算法。常用算法： 先进先出算法FIFO：淘汰先调入内存的页 最久未使用淘汰算法LRU：淘汰未被访问的页中时间最长的页 最近未使用淘汰算法NUR：淘汰第1个最近未被访问的页（淘汰页表中第一个访问位为0的页） 最不经常使
17、用页面淘汰算法（LFU）：淘汰那些到当前时间为止访问次数最少的页。页表中增加一个访问记数器。 最佳算法：当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。这种算法是不可能的。页面淘汰算法优劣的衡量标准：缺页中断率fffa （a是总的页面访问次数，f是缺页中断次数）38【例】一个进程已分到4个页帧（块）（M=4），其页表如下表所示，当进程访问第4页时产生缺页中断，请分别用FIFO、LRU、NRU算法决定将哪一页淘汰？是否需要回写？页表： 页号 页帧 装入时间 最近访问时间 访问位 修改位 2 0 60 161 0 1 1 1 130 160 0 0
18、 0 2 26 162 1 0 3 3 20 163 1 1FIFO：淘汰最先调入的页面（页帧为3的页） 修改位为1，要回写。LRU：淘汰最久未访问的页（页帧为1的页） 修改位为0，不要回写。NRU： 淘汰最近未使用的页，淘汰第一个访问位为0的页（页帧为0的页） 修改位为1，要回写。39【例】对访问串：1、2、3、4、1、2、5、1、2、3、4、5，指出在驻留集大小分别为3和4时，使用FIFO（先进先出）和LRU（最久未使用）置换算法的缺页率，结果说明了什么？（设驻留集M表示分给该作业的内存块数）分析：40M=3，FIFO淘汰先调入内存的页M=4，FIFO41刚被访问最久未被访问M=3，LRU
19、淘汰最久未使用的页M=4，LRU调整顺序42解 FIFO ： M3 f fa91275% M4 f101283% LRU ： M3 f fa101283% M4 f fa81267% Belady异常现象：对于FIFO算法，有时会出现当M增加时缺页次数不是减少，反而增加的现象。43课堂练习：设页面走向为：2、3、2、1、5、2、4、5、3、2、5、2，页帧M=3，试用FIFO和LRU两种算法分别计算访问过程中的缺页率。44补充补充: 抖动抖动 抖动 主存和辅存之间的频繁的页面置换 现象称为抖动，也称为颠簸，其导致系统效率急剧下降。 产生抖动的原因： 系统的淘汰算法不合理从而导致刚淘汰的页面马上
20、又要访问的频繁的页面置换状态。 系统在考虑置换算法时既要考虑有尽可能少的缺页率、置换算法的简单性、还要尽量避免系统抖动。455.4.5页的共享与保护页面共享（各进程中统一页号）46 分页管理的存储保护有两种方式： 一是由CPU提供的越界保护，当地址映射机构分离出页号和页内位移后，若0页号用户程序的总页数则访问合法，否则访问越界。 二是由操作系统在页表中为页的存取权限设置的保护位，表示该页的存取控制权限，如r表示可读，w表示可读，e表示可执行。当有一程序访问该页时，系统就按存取控制位设置的权限实施存取控制。475.4.6页式管理的优缺点 优点： 有效地解决了碎片问题； 提供了内存和外存统一管理的
21、虚拟存储器实现方式，使用户可以利用的存储空间大大增加。 缺点： 要求有相应的硬件支持； 增加了系统开销（如缺页中断处理）； 如置换算法选择不当，可能会产生抖动现象； 每个进程的最后总有一部分空间得不到利用。48作业 习题：缺页次数及中断率的计算。 在一个请求分页虚拟存储管理系统中，一个程序页面的访问序列是1、2、3、4、2、1、5、2、1、2、3、5、2、1、4、2、3。分别用FIFO和LRU算法，对分配给程序3个页框和4个页框的情况下，求出缺页次数和缺页中断率。495.5分段内存管理分段内存管理段式管理的引入段式管理的引入 问题的提出 由于分页方式只考虑程序空间按页的尺寸切分，没有考虑各连续
22、的页之间是否在逻辑上也是连续的。 逻辑上的不连续导致 请调一页，可能只用到该页中的一部分； 不方便实现段的共享和保护。 解决办法 段式管理,保留程序在逻辑上的完整性505.5.1段式管理的基本原理段式管理的基本原理 段式管理原理 作业：按逻辑意义分段 内存分配 段内在内存中连续 各段在内存中可连续，也可不连续51 段 程序按逻辑上有完整意义的段来划分，称为逻辑段。例如主程序、子程序、数据等都可各成一段。每个段的大小可以不相等。 逻辑地址 程序中的逻辑地址由段号和段内位移两部分（二维）组成。 段号 将一个程序的所有逻辑段从0开始编号，称为段号。 段内地址 每一个逻辑段都是从0开始编址，称为段内地
23、址。段号S段内位移W程序逻辑地址段式地址5.5.2段式管理的实现原理52代码段 （第2段） 数据段（第1段） 栈段（第0段） 某行代码逻辑地址：2：2K段号 01K-11段内地址1K2K02K-1105K-11段式管理地址53 段式管理的分配与回收 参考动态分区管理 段式管理中使用的数据结构 段表：记录内存分配情况 段表属性段表属性 段号段号 段首址段首址 段长段长 中断位中断位 引用位引用位 改变位改变位 保护位保护位 段式管理地址映射机制 由逻辑地址得到段号S和段内位移W； 查段表得到物理起址B，加上W即得物理地址。5455段的共享与保护段的共享与保护 段的共享 实现：段表中设置指向共享段
24、的地址指针56 段保护： 地址越界保护：段起址物理地址段起址+段长 段式管理中，地址越界引发的中断称为越段中断。但如果系统允许段动态增长，则应修改段表中的段长表项值。此时的段表数据结构如表所示。 设置段的存取保护位:可读、可写、可执行等。 相比较页的存取保护，段的存取保护更易于实现，解决了分页管理中由于页在逻辑上不具备逻辑完整性，当一页的内容涉及多个逻辑模块时，该页的存取控制难以实现的难题。 段号段 长度起 始 地 址允许动态增长内 / 外存访问位575.5.3 分段的优缺点分段的优缺点 分段的优缺点：见下 分段和分页的比较 不同（1）段根据用户的需要划分，便于存储保护和信息的共享；页是为了管
25、理内存的方便而划分的，页的保护和共享受到限制。（2）页的大小固定不变，由系统决定；段的大小是不固定的，由其完成的功能决定。（3）段式提供的是二维地址空间；页式提供的是一维地址空间。（4）段式管理可能产生内存外碎片，页式管理消除了外碎片，但有页内碎片。58 相同（5）段式与页式一样，都需要在进程运行前，全部信息装内存，内存利用不够充分。 （6）段式与页式一样，为实现地址变换，CPU要花费较大的开销，为实现管理要提供更多的表格。（7）段式与页式一样，寻址都需要访问二次内存，如果要提高访问速度，都需要在相联存储器中设置快表。59请求段式管理的基本思想请求段式管理的基本思想 段式存储也可实现虚拟存储管
26、理，称为请求段式管理。 请求段式管理的基本思想 把作业的所有分段的副本都存放在外存上，当作业被调度投入运行时，首先把当前需要用的一段或几段装入内存，在执行过程中，访问到不在内存的段时，再通过缺段中断机构把它从外存上调入。60请求段式管理的实现原理请求段式管理的实现原理 请求段表的结构61请求段式管理的地址变换过程(*) 625.5.4请求段页式管理的基本思想请求段页式管理的基本思想 问题引入 段式管理优点：能够反映程序的逻辑结构。 页式管理优点：有利于提高内存利用率。 请求段式管理优点：保留段式优点，且只部分调入 请求段式管理问题：调入段时需全部调入，会产生碎片。 请求页式管理优点：保留页式优
27、点，且只部分调入 请求页式管理问题：逻辑上没有完整性，不利于共享。 解决：保留上述方式优点，克服缺点 段、页相结合635.5.5请求段页式管理的实现原理请求段页式管理的实现原理 地址的构成 逻辑上分段：便于共享和保护 虚地址组成（二维）：段号、段内位移（页号、页内位移） 内存分块：便于分配和内存的利用。段号S段内位移页号P页内位移W分解为64 段表、段页表（页表）段号状态页表大小页表起址给进程分配的段表页号状态块号给第X段分配的页表(段页表)65地址变换过程地址变换过程进程进程A对应对应的程序空间的程序空间分段分段012给进程给进程A分配的段表分配的段表段页式内存管理的段表、页表和内存的关系逻辑上分段物理上分块66 段页式管理地址映射 根据程序的逻辑地址得到段号和段内位移，并将段内位移根据页容量分解为页号和页内位移。 根据该进程的段表寄存器得到段表起始地址，在段表中查找该段号的表项，得到页表起始地址。 根据页号在页表中查找该页对应的内存块号。 根据块号计算得到该块的起始地址。 将块的起始地址加上页内位移，得到物理地址。67 段页式存储管理中每次存取须经过三次主存访问 第一次：访问段表，得到页表起始地址； 第二次：访问页表，得到主存块号； 第三次：存取 。68作业 习题P135：5.19
