操作系统最新课件VIP

1、操作系统PPT课件 (2)操作系统 操作系统PPT课件 (2)内存管理内存管理l概述概述l存储管理基本技术存储管理基本技术l分页存储管理分页存储管理l分段存储管理分段存储管理l段页式管理段页式管理l页的置换算法页的置换算法操作系统PPT课件 (2)概述概述l基本概念基本概念l虚拟存储器虚拟存储器l重定位重定位操作系统PPT课件 (2)存储器的层次存储器的层次3级存储器结构缓 存内 存外 存程序和数据必须先移到内存，才能被 CPU 存取程序和数据可以被 CPU直接存取速度、价格上升容量增加操作系统PPT课件 (2)存储管理存储管理 在单道程序系统中，存储管理就是分配和在单道程序系统中，存储管理就

2、是分配和回收内存区。回收内存区。 在多道程序系统中，要求存储管理具有内在多道程序系统中，要求存储管理具有内存空间管理、地址转换、内存扩充、内存存空间管理、地址转换、内存扩充、内存保护和共享等功能。保护和共享等功能。操作系统PPT课件 (2)内存空间管理内存空间管理 分配策略：静态、动态分配策略：静态、动态 策略：调入策略、放置策略、置换策略策略：调入策略、放置策略、置换策略操作系统PPT课件 (2)地址转换（重定位）地址转换（重定位） 逻辑地址到物理地址转换逻辑地址到物理地址转换 地址转换分静态地址重定位和动态地址重地址转换分静态地址重定位和动态地址重定位定位操作系统PPT课件 (2)内存扩充

3、内存扩充 通过软件技术实现内存扩充通过软件技术实现内存扩充 实存：覆盖、交换实存：覆盖、交换 虚存：内外存统一的内存扩充技术虚存：内外存统一的内存扩充技术操作系统PPT课件 (2) 内存的共享和保护内存的共享和保护 内存共享：共享内存中程序和数据内存共享：共享内存中程序和数据 内存保护：保证每道程序在自己的内存空内存保护：保证每道程序在自己的内存空间运行，不破坏系统和其他用户程序间运行，不破坏系统和其他用户程序 内存保护技术：上下界保护、存储键保护内存保护技术：上下界保护、存储键保护操作系统PPT课件 (2)虚拟存储器虚拟存储器计算机系统把辅存当作主存进行扩充，对用计算机系统把辅存当作主存进行

4、扩充，对用户来说，计算机系统有一个容量很大的主存户来说，计算机系统有一个容量很大的主存操作系统PPT课件 (2)关键：程序的逻辑地址和主存的实际地址相关键：程序的逻辑地址和主存的实际地址相脱离。脱离。虚拟地址空间的限制：虚拟地址空间的限制：指令中的地址场长度的限制指令中的地址场长度的限制外部存储器大小的限制外部存储器大小的限制容量：主存和辅存之和容量：主存和辅存之和操作系统PPT课件 (2)虚拟存储器特性虚拟存储器特性l虚拟性虚拟性l离散性离散性l多次性多次性l交换性交换性操作系统PPT课件 (2)重定位重定位1）绝对地址、相对地址和逻辑地址空间绝对地址、相对地址和逻辑地址空间2 2）重定位）

5、重定位 用户程序装入内存时对有关指令地址用户程序装入内存时对有关指令地址的修改称重定位技术。的修改称重定位技术。 重定位分静态地址重定位，动态地址重定位分静态地址重定位，动态地址重定位。重定位。操作系统PPT课件 (2)静态地址重定位静态地址重定位在程序装入过程中由装配程序进行重定位在程序装入过程中由装配程序进行重定位。 50 MOV AX，1000 100 3271050 MOV AX，11001100 327 1000程序空间 内存空间不能移动不能移动连续空间连续空间不能部分装入不能部分装入操作系统PPT课件 (2)动态地址重定位动态地址重定位在程序执行过程中，每次访存时将访问的在程序执行

6、过程中，每次访存时将访问的程序地址转换成内存地址。程序地址转换成内存地址。 50 MOV AX，1000 100 3271050 MOV AX，100 1100 327 1000程序空间 内存空间1000100 100 +1100 B VM解决静态地址重解决静态地址重定位的问题。定位的问题。操作系统PPT课件 (2)存储管理的基本技术存储管理的基本技术l分区法分区法l可重定位分区法可重定位分区法l覆盖技术覆盖技术l交换技术交换技术操作系统PPT课件 (2)分区法分区法分区管理：给每一个内存中的进程划分一块分区管理：给每一个内存中的进程划分一块适当大小的存储块，以连续存储各进程的程适当大小的存储

7、块，以连续存储各进程的程序和数据，使各进程能并发进行。序和数据，使各进程能并发进行。分区管理：固定分区、动态分区分区管理：固定分区、动态分区操作系统PPT课件 (2)固定分区固定分区处理作业之前，存储器就被划分成若干分区处理作业之前，存储器就被划分成若干分区1 1、数据库、数据库2 2、存储分配和回收、存储分配和回收3 3、存储保护和重定位、存储保护和重定位4 4、优缺点、优缺点操作系统PPT课件 (2)数据库数据库存储分块表存储分块表MBTMBT：用于描述内存各分区使：用于描述内存各分区使用情况的数据结构。用情况的数据结构。 分区号分区号 大小大小 位置位置 状态状态 1 12KB 20KB

8、 1 12KB 20KB 使用使用 2 32KB 32KB 2 32KB 32KB 使用使用 3 64KB 64KB 3 64KB 64KB 使用使用 4 128K 128KB 4 128K 128KB 未用未用操作系统PPT课件 (2)存储分配存储分配 要求要求XKXK大小分区大小分区 取存储分块表第一项取存储分块表第一项 表结束？表结束？ 该分区未使用？该分区未使用？ 分区大小分区大小 XKXK？ 状态位置置状态位置置“使用使用” 向用户返回分区号向用户返回分区号 YN YNN Y无法分配无法分配取下一项取下一项操作系统PPT课件 (2)存储回收存储回收给出分区号：把状态为由使用给出分区号

9、：把状态为由使用未用未用操作系统PPT课件 (2)存储保护和重定位存储保护和重定位l存储保护：存储保护： 使用上下界保护使用上下界保护 使用存储键保护使用存储键保护分区号即为存储键分区号即为存储键l重定位：静态地址重定位重定位：静态地址重定位操作系统PPT课件 (2)例例有三个存储区。其大小为有三个存储区。其大小为2K2K，6K6K，12K12K现有作业：现有作业：1. 2K1. 2K，6K6K，12K12K2. 6K2. 6K，6K6K，6K6K操作系统PPT课件 (2)内部碎片：一个需要内部碎片：一个需要M M个字的作业可能包含在个字的作业可能包含在N N个字的存储空间（个字的存储空间（N

10、 N M M），则），则N-MN-M为内部碎片为内部碎片外部碎片：当某个存储空间空闲时，但对于等外部碎片：当某个存储空间空闲时，但对于等待的作业又太小，该空闲块为外部碎片。待的作业又太小，该空闲块为外部碎片。操作系统PPT课件 (2)优缺点优缺点l优点：存储管理简单，硬件支持为一对界优点：存储管理简单，硬件支持为一对界地址寄存器。地址寄存器。l缺点：内存利用率不高。缺点：内存利用率不高。操作系统PPT课件 (2)动态分区动态分区在系统运行过程中建立分区，并使分区的大在系统运行过程中建立分区，并使分区的大小和作业相符。小和作业相符。特点：特点：l分区个数可变，分区大小可变分区个数可变，分区大小可

11、变l主存中分布着个数和大小都是变化的自由主存中分布着个数和大小都是变化的自由分区或碎片分区或碎片操作系统PPT课件 (2)l数据库数据库l可变分区的分配和回收可变分区的分配和回收l四种放置策略四种放置策略l存储器的紧缩和程序的浮动存储器的紧缩和程序的浮动l动态重定位的可变分区多道管理动态重定位的可变分区多道管理操作系统PPT课件 (2)数据库数据库l存储分块表存储分块表l分开设置两个存储管理表：已经使用分区分开设置两个存储管理表：已经使用分区表和自由分区表表和自由分区表l自由存储块链自由存储块链操作系统PPT课件 (2)两个存储管理表两个存储管理表区号 大小 位置 状态 区号 大小 位置 状态

12、 1 8K 312K 已分 1 32K 352K 空闲 2 32K 320K 已分 2 空 3 空 3 520K 504K 空闲 4 120K 384K 已分 UBTFBT操作系统PPT课件 (2)自由存储块链自由存储块链在每个已分配的分区和未分配的空白区中在每个已分配的分区和未分配的空白区中附上表格，然后用地址指针把所有空白区附上表格，然后用地址指针把所有空白区链接起来。链接起来。在每个分区中，前末两个字用来存入下列在每个分区中，前末两个字用来存入下列有关信息：有关信息：l状态信息：状态信息：1 1 已分配已分配0 0 空白区空白区l大小大小l指针：只有空白区有指针：只有空白区有操作系统PP

13、T课件 (2)1N+21N+2容纳N个字的作业0N+20N+2N个字可用前向指针后向指针已使用分区自由分区操作系统PPT课件 (2)分配和释放算法分配和释放算法分配步骤：分配步骤：从未分配表中找到一个足以容纳该作业的从未分配表中找到一个足以容纳该作业的可用空白区（未分配区）可用空白区（未分配区）如果这个空白区比所要求的大，则将它分如果这个空白区比所要求的大，则将它分成两部分：一部部分成为已经分配的分区，成两部分：一部部分成为已经分配的分区，剩余部分仍为空白区剩余部分仍为空白区修改两个存储表的有关信息，并回送一个修改两个存储表的有关信息，并回送一个所分配分区的序号或该分区的始址所分配分区的序号或

14、该分区的始址操作系统PPT课件 (2)回收步骤：回收步骤：检查回收的分区是否与空白区相邻接，如有检查回收的分区是否与空白区相邻接，如有则加以合并，使之成为一个连续的空白区则加以合并，使之成为一个连续的空白区修改两张存储表修改两张存储表F1 空白R 回收F1 空白R 回收F2 空白R 回收F1 空白R回收操作系统PPT课件 (2)四种放置策略四种放置策略l空闲区的组织方法空闲区的组织方法l四种放置策略四种放置策略操作系统PPT课件 (2)空闲区的组织方法空闲区的组织方法l按空闲区首址递增的次序归类组织空闲区按空闲区首址递增的次序归类组织空闲区表或队列。表或队列。l按空闲区大小递增或递减的次序归类

15、组织按空闲区大小递增或递减的次序归类组织空闲区表或队列。空闲区表或队列。操作系统PPT课件 (2)四种放置策略四种放置策略l首次适应法首次适应法l最佳适应法最佳适应法l最坏适应法最坏适应法l下次适应法下次适应法操作系统PPT课件 (2)首次适应法首次适应法首次适应法要求空闲区按首址递增的次序首次适应法要求空闲区按首址递增的次序组织空闲区表或队列。组织空闲区表或队列。优点：释放某一存储区，若与空闲区相邻，优点：释放某一存储区，若与空闲区相邻，则合并后，无须改变该区在队列的位置。则合并后，无须改变该区在队列的位置。 尽可能利用低地址，高地址处留有尽可能利用低地址，高地址处留有较大的空间。较大的空间

16、。操作系统PPT课件 (2)最佳适应法最佳适应法最佳适应法要求空闲区按大小递增的次序最佳适应法要求空闲区按大小递增的次序组织空闲区表或队列。组织空闲区表或队列。优点：若系统中存在一个和申请区大小相优点：若系统中存在一个和申请区大小相同的空闲区，则必定被选中。同的空闲区，则必定被选中。 若不存在这样的空闲区，选中的是若不存在这样的空闲区，选中的是满足要求的最小空闲区。满足要求的最小空闲区。缺点：缺点： 容易产生碎片。容易产生碎片。 操作系统PPT课件 (2)最坏适应法最坏适应法最坏适应法要求空闲区按大小递减的次序最坏适应法要求空闲区按大小递减的次序组织空闲区表或队列。组织空闲区表或队列。优点：当

17、程序装入内存中最大的空闲区剩优点：当程序装入内存中最大的空闲区剩下的空闲区较大，还能装较大的程序。下的空闲区较大，还能装较大的程序。 每次仅做一次查找。每次仅做一次查找。操作系统PPT课件 (2)下次适应法下次适应法把存储空间中空闲块构成一个循环链，每把存储空间中空闲块构成一个循环链，每次查找合适分区时，总是从上次结束地方次查找合适分区时，总是从上次结束地方开始。开始。优点：使整个存储空间的利用更加均衡优点：使整个存储空间的利用更加均衡。操作系统PPT课件 (2)例例有一作业序列，要求用首次，最佳，最坏有一作业序列，要求用首次，最佳，最坏适应法分析哪种算法最合适。适应法分析哪种算法最合适。 a

18、bcdefgh16k14k5k30k作业作业A A要求要求13K13K作业作业B B要求要求15K15K作业作业C C要求要求30K30K内存分布情况内存分布情况操作系统PPT课件 (2)首次适应法首次适应法 ABC无无法法分分配配始址始址 大小大小 始址始址 大小大小 始址始址 大小大小 a 16K a+13K 3K a+16k 3k c 14K c 14k c 14k e 5K e 5k e 5k g 30k 9 30k g+15k 15k操作系统PPT课件 (2)最佳适应法最佳适应法 始址始址 大小大小 始址始址 大小大小 始址始址 大小大小 e 5k c+13k 1k c+13k 1k

19、 c 14k e 5k a+15k 1k a 16k a 16k e 5K g 30k g 30k g 30k AB始址始址 大小大小 c+13k 1ka+15k 1ke 5KC操作系统PPT课件 (2)最坏适应法最坏适应法 始址始址 大小大小 始址始址 大小大小 始址始址 大小大小 g 30k g+13k 17k a 16k a 16k a 16k c 14k c 14k c 14k e 5k a 5k a 5k g+28K 2kABC无无法法分分配配操作系统PPT课件 (2)存储器的紧缩和程序的浮动存储器的紧缩和程序的浮动l碎片问题和存储器的紧缩碎片问题和存储器的紧缩l程序的浮动程序的浮动

20、操作系统PPT课件 (2)解决碎片方法解决碎片方法l把程序分成几个部分装入不同的分区。把程序分成几个部分装入不同的分区。l规定一个门限值（由规定一个门限值（由OSOS决定）。决定）。l定期压缩存储空间。定期压缩存储空间。操作系统PPT课件 (2)可重定位的分区法可重定位的分区法动态重定位的硬件支持和软件算法动态重定位的硬件支持和软件算法硬件支持：定位寄存器、加法器、硬件支持：定位寄存器、加法器、 逻辑地址寄存器逻辑地址寄存器 软件算法软件算法:1.:1.在某个分区被释放后立即紧在某个分区被释放后立即紧缩。缩。 2.2.找不到足够大的空闲区再进找不到足够大的空闲区再进行紧缩。行紧缩。操作系统PP

21、T课件 (2) 请求分配一个Xk大小分区有大于Xk空闲区空闲区总和Xk？紧缩存储并相应修改各表（得到一个大于Xk空闲区）分配分区并修改各表返回分区表无法分配NYNY可重定位分区分配算法可重定位分区分配算法操作系统PPT课件 (2)l优点：优点：主存的使用更加灵活、更加有效主存的使用更加灵活、更加有效便于实现动态链接便于实现动态链接提高了主存的利用率提高了主存的利用率l缺点：缺点：需要附加的硬件支持需要附加的硬件支持实现存储管理的软件算法比较复杂实现存储管理的软件算法比较复杂操作系统PPT课件 (2)覆盖技术覆盖技术覆盖：指一个作业的若干程序段（或数据覆盖：指一个作业的若干程序段（或数据段）间或

22、几个作业的某些部分间共享某主段）间或几个作业的某些部分间共享某主存空间。存空间。覆盖段覆盖段 覆盖区覆盖区操作系统PPT课件 (2)例 MAIN20KA0 30K A1 60KA2 30KA3 20KA4 40KB1 30KB0 40KMAINA0B0A1A2 B1A3 A4覆盖段0 40K覆盖段1 60K覆盖段2 40K270K160K操作系统PPT课件 (2)交换技术交换技术 交换是指将一个进程从内存拷贝到磁盘上，交换是指将一个进程从内存拷贝到磁盘上，以腾出空间给其他进程使用。需要时，再将以腾出空间给其他进程使用。需要时，再将该进程调入内存。交换进程由换出和换进两该进程调入内存。交换进程由

23、换出和换进两个过程组成，换出是把内存中的数据和程序个过程组成，换出是把内存中的数据和程序换到外存的交换区，而换进则是把外存交换换到外存的交换区，而换进则是把外存交换区中的数据和程序换到内存的分区中。区中的数据和程序换到内存的分区中。 在交换系统中，交换所占用的时间相当多。在交换系统中，交换所占用的时间相当多。操作系统PPT课件 (2)分页存储管理分页存储管理l基本概念基本概念l分页系统中的地址转换分页系统中的地址转换l纯分页系统纯分页系统l请求式分页请求式分页l硬件支持及缺页处理硬件支持及缺页处理l页的共享和保护页的共享和保护操作系统PPT课件 (2)基本概念基本概念l等分主存：页架、页架号等

24、分主存：页架、页架号l用户逻辑地址空间的分页：页、页号用户逻辑地址空间的分页：页、页号l逻辑地址的表示：（页号逻辑地址的表示：（页号p,p,页内地址页内地址d d）l分配原则：以页架为基本分配单位分配原则：以页架为基本分配单位l页表与页表地址寄存器页表与页表地址寄存器页表：页号、页架号、状态页表：页号、页架号、状态页表地址寄存器：页表起始地址、页表长页表地址寄存器：页表起始地址、页表长l分页系统中的地址结构：分页系统中的地址结构：页号页号最大页数最大页数页内地址页内地址页架的大小页架的大小l页面尺寸应是页面尺寸应是2 2的幂的幂操作系统PPT课件 (2)分页系统中的地址转换分页系统中的地址转换

25、l基本的地址转换基本的地址转换l多级页表地址转换多级页表地址转换l反向页表地址转换反向页表地址转换l快表地址转换快表地址转换操作系统PPT课件 (2)基本的地址转换基本的地址转换 p+L bp d p 页表页表地址寄存器虚地址v=(p,d)实地址p d操作系统PPT课件 (2)l转换过程：转换过程： 1.1.将逻辑地址分离出页号，页内地址。将逻辑地址分离出页号，页内地址。 2.2.以页号为索引查页表，得该页在内存的页架以页号为索引查页表，得该页在内存的页架号号 3.3.把页架号，页内地址（二进制形式把页架号，页内地址（二进制形式） 拼接成物理地址。拼接成物理地址。l例例操作系统PPT课件 (2

26、)一分页系统，页架的大小为一分页系统，页架的大小为1KB1KB，逻辑，逻辑地址为地址为41014101（十进制数）页表如下。（十进制数）页表如下。 页表 0 15 1 17 2 20 3 39 4 18 5 22要求把逻辑地址转要求把逻辑地址转换成物理地址换成物理地址操作系统PPT课件 (2)4101=00101B 4101=00101B 得得P=4P=4，d=5d=5由由P=4P=4查查P P =18=18物理地址拼接物理地址拼接0000101B=4805H0000101B=4805H P dPd操作系统PPT课件 (2)问题：问题：l页表放在哪里，整个系统的页表空间多大页表放在哪里，整个系

27、统的页表空间多大l对系统的效能有何影响对系统的效能有何影响操作系统PPT课件 (2)多级页表地址转换多级页表地址转换 页目录寄存器页目录号 页号 页内位移页架号 页内位移页架号当前进程某个次级页表页架号操作系统PPT课件 (2)解决页表非常大的问题解决页表非常大的问题访存次数增加，增加一级页表，增加一次访存次数增加，增加一级页表，增加一次访存次数。访存次数。操作系统PPT课件 (2)反向页表地址转换反向页表地址转换 页号 页内位移哈希函数页架号页架号页号 表目体 链指针哈希表 反向页表页架号 页内位移物理地址逻辑地址操作系统PPT课件 (2)快表的地址转换快表的地址转换 页号 页内位移页号 页

28、架号页架号 页内位移逻辑地址物理地址快表操作系统PPT课件 (2)l提高速度提高速度l增加成本增加成本l快慢结合（关键在命中率）快慢结合（关键在命中率）操作系统PPT课件 (2)如果查找快表花费的时间是如果查找快表花费的时间是50NS50NS，访问内，访问内存的时间是存的时间是750NS750NS，试计算命中率为，试计算命中率为80%80%，90%90%时实际的访存时间。时实际的访存时间。操作系统PPT课件 (2)l页号在快表：存取时间为页号在快表：存取时间为50+750=800NS50+750=800NSl页号在慢表：存取时间为页号在慢表：存取时间为750+750=1500NS750+750

29、=1500NSl命中率为命中率为80% 80% 存取时间为存取时间为0.80.8* *800+0.2800+0.2* *1500=940NS1500=940NSl命中率为命中率为90% 90% 存取时间为存取时间为0.90.9* *800+0.1800+0.1* *1500=870NS1500=870NSl时间延迟（时间延迟（870-750870-750）/750=16%/750=16%操作系统PPT课件 (2)纯分页系统纯分页系统l纯分页系统：在调度一个作业时，必须把纯分页系统：在调度一个作业时，必须把它的所有的页一次装入内存它的所有的页一次装入内存l纯分页技术是实存技术纯分页技术是实存技术

30、操作系统PPT课件 (2) 页号 页内位移如果页号页表大小，则中断页表大小 页表始址页架号 存储控制如果访问不允许，中断页架号 页内位移逻辑地址物理地址页表寄存器页表纯分页系统地址转换纯分页系统地址转换操作系统PPT课件 (2)请求式分页请求式分页请求式分页：运行作业时不需要把全部的逻请求式分页：运行作业时不需要把全部的逻辑页都调入内存辑页都调入内存该技术为用户提供虚存该技术为用户提供虚存操作系统PPT课件 (2)请求式分页的页表要增设请求式分页的页表要增设3 3个标识位个标识位 状态位：指示该页是否在内存状态位：指示该页是否在内存 访问位：指示该页是否被访问过访问位：指示该页是否被访问过 修

31、改位：指示该页是否被修改过修改位：指示该页是否被修改过 操作系统PPT课件 (2)硬件支持及缺页中断硬件支持及缺页中断l主存管理单元主存管理单元MMUMMUl页表页表l快表快表l反向页表反向页表l缺页中断机构缺页中断机构操作系统PPT课件 (2)主存管理单元主存管理单元MMUl页表地址寄存器：页表始址，长度页表地址寄存器：页表始址，长度l将虚地址分成虚页号和页内地址将虚地址分成虚页号和页内地址l判断有有效性和保护性错误、越界保护判断有有效性和保护性错误、越界保护页表中页表中有效位有效位保护权限保护权限操作系统PPT课件 (2)页表页表实现页式管理地址重定位重要的数据结构实现页式管理地址重定位重

32、要的数据结构内容：物理页架号内容：物理页架号 修改位修改位 有效位有效位 引用位引用位 保护权限保护权限操作系统PPT课件 (2)快表快表为加快地址转换而使用高速缓存为加快地址转换而使用高速缓存内容：虚页号内容：虚页号 物理页架号物理页架号 保护权限保护权限操作系统PPT课件 (2)反向页表反向页表内容：虚页号内容：虚页号 物理页架号物理页架号 指向哈希链的下一项指针指向哈希链的下一项指针 有效位，修改位，引用位有效位，修改位，引用位 保护和加锁信息保护和加锁信息操作系统PPT课件 (2)缺页中断机构缺页中断机构缺页中断是一种特殊的中断，它与一般中缺页中断是一种特殊的中断，它与一般中断的区别为

33、：断的区别为：l在指令执行期间产生和处理中断信号；在指令执行期间产生和处理中断信号；l一条指令在执行期间可能产生多次缺页中一条指令在执行期间可能产生多次缺页中断。断。操作系统PPT课件 (2)缺页中断处理缺页中断处理 保留C P U的状态 缺页故障 在外存找到所需页 有 空页架吗? 选择淘汰的页面 该页是否 修改过? 把该页写入外存 装入新的一页 更新页表和缓存 恢复执行 Y N N Y 操作系统PPT课件 (2)页的共享页的共享共享的方法：使共享进程的逻辑地址空间中共享的方法：使共享进程的逻辑地址空间中的页指向相同的页架号的页指向相同的页架号操作系统PPT课件 (2)l优点：解决碎片（仅存最

34、后一页页内头）优点：解决碎片（仅存最后一页页内头） 较好利用内存空间。较好利用内存空间。l缺点：逻辑地址空间是一唯的。缺点：逻辑地址空间是一唯的。 页面的划分对用户是透明的。页面的划分对用户是透明的。 最后一页页内零头。最后一页页内零头。操作系统PPT课件 (2)分段存储管理分段存储管理l基本概念基本概念l分段系统的地址转换分段系统的地址转换l硬件支持和缺段处理硬件支持和缺段处理l段的共享和保护段的共享和保护操作系统PPT课件 (2)基本概念基本概念l进程的逻辑地址空间：按自然逻辑关系分段。进程的逻辑地址空间：按自然逻辑关系分段。l程序的地址结构：（段号程序的地址结构：（段号s s、段内地址、

35、段内地址w w）段号段号最多段数最多段数段内地址段内地址最大段长最大段长l主存分配：以段为单位分配，一个段占连续空间，主存分配：以段为单位分配，一个段占连续空间，各段可不连续。各段可不连续。l段表和段表寄存器段表和段表寄存器段表：段号、段的长度、段在主存中的起始地段表：段号、段的长度、段在主存中的起始地址、段的状态位、访问位、修改位、段的外存址、段的状态位、访问位、修改位、段的外存地址地址段表寄存器：段表起始地址、段表长度段表寄存器：段表起始地址、段表长度操作系统PPT课件 (2)分段和分页的主要区别分段和分页的主要区别l页是信息的物理单位，分页是为了便于系页是信息的物理单位，分页是为了便于系

36、统管理；而段是信息的逻辑单位，分段是统管理；而段是信息的逻辑单位，分段是为了满足用户需要。为了满足用户需要。l分页式存储管理的作业地址空间是一维的；分页式存储管理的作业地址空间是一维的；而分段式存储管理作业地址空间是二维的。而分段式存储管理作业地址空间是二维的。 l页的长度由系统确定，是等长的；而段的页的长度由系统确定，是等长的；而段的长度由具有相对完整意义的信息长度确定，长度由具有相对完整意义的信息长度确定，是不固定的。是不固定的。 操作系统PPT课件 (2)分段系统中的地址转换分段系统中的地址转换 L B段 表 长 段 表 地 址段 表寄 存 器+ s d段 号 段 内 地 址逻 辑 地

37、址段 长 内 存 始 址1K5006K10K段 表 +d m ?访 内 地 址10K内 存段长YN地 址 越 界 ， 发 生 中 断操作系统PPT课件 (2)l把逻辑地址中段号取出来。把逻辑地址中段号取出来。l按段号查找段表：取段长，段首地址。按段号查找段表：取段长，段首地址。l判段内地址判段内地址 段长？段长？ 不是，产生越界中断不是，产生越界中断 是，访问合法是，访问合法l把段内地址加上段首址形成实地址把段内地址加上段首址形成实地址操作系统PPT课件 (2) 段长段长 段起始地址段起始地址 有效位有效位 0 200 500 1 1 400 1000 1 2 100 1400 0 3 900

38、 2000 1 虚地址：（虚地址：（0 0，100100），（），（1 1，500500），（），（2 2，5050） （4 4，470470）完成实地址转换）完成实地址转换操作系统PPT课件 (2)1. 500+100=600500+100=6002. 2. 越界越界3. 3. 缺段中断缺段中断4. 4. 越界越界操作系统PPT课件 (2)硬件支持和缺段处理硬件支持和缺段处理l段表机制：段表和段表寄存器段表机制：段表和段表寄存器l地址转换机构：动态地址重定位地址转换机构：动态地址重定位l缺段中断机构缺段中断机构操作系统PPT课件 (2)地址转换机构地址转换机构访问sww段长?符合存取方式?Y

39、段 s 在主存?YY修改访问字段，如写访问，则置修改位=1形成访问主存地址(A)=(主存始址)+(位移 w)返回分段越界中断处理N分段越界中断处理N缺段中断处理N操作系统PPT课件 (2)缺段中断处理程序缺段中断处理程序虚段 s 不在内存阻塞请求进程从外存读入段 s修改段表及内存空闲区链唤醒请求进程返回空闲区拼接，以形成一个合适的空闲区淘汰一个或几个实段以形成一个合适空闲区Y空闲区容量总和能否满足？内存中有合适的空闲区吗 ?YNN操作系统PPT课件 (2)段的共享和保护段的共享和保护段的共享段的共享 段的共享是指两个以上的作业，使用某段的共享是指两个以上的作业，使用某个子程序或数据段，而在内存

40、中只保留该个子程序或数据段，而在内存中只保留该信息的一个副本。具体地说，只需在每个信息的一个副本。具体地说，只需在每个进程的段表中，用相应的表项来指向共享进程的段表中，用相应的表项来指向共享段在内存的起始地址即可。段在内存的起始地址即可。 操作系统PPT课件 (2)段的保护段的保护 在分段系统中，由于每个分段在逻辑上是在分段系统中，由于每个分段在逻辑上是独立的，因而比较容易实现信息保护。段的独立的，因而比较容易实现信息保护。段的保护是为了实现段的共享和保证作业正常运保护是为了实现段的共享和保证作业正常运行的一种措施。分段存储管理中的保护主要行的一种措施。分段存储管理中的保护主要有地址越界保护和

41、存取方式控制保护。有地址越界保护和存取方式控制保护。 操作系统PPT课件 (2)分段存储管理的优缺点分段存储管理的优缺点l优点：优点：便于处理变化的数据便于处理变化的数据结构结构便于共享便于共享提供虚存的功能提供虚存的功能提供动态连接的便利提供动态连接的便利便于控制存取访问便于控制存取访问l缺点：缺点：要为存储紧缩付出处理要为存储紧缩付出处理机机时的代价机机时的代价分段的最大尺寸受到主分段的最大尺寸受到主存大小的限制存大小的限制在外存中管理可变尺寸在外存中管理可变尺寸的分段比较困难的分段比较困难与分页一样，提高了硬与分页一样，提高了硬件成本件成本操作系统PPT课件 (2)段页式存储管理段页式存

42、储管理l基本概念基本概念l地址转换地址转换l管理算法管理算法操作系统PPT课件 (2)段页式存储管理的基本概念段页式存储管理的基本概念l等分主存：页架、页架号等分主存：页架、页架号l进程的地址空间采用分段的方式进程的地址空间采用分段的方式l每一段又采用分页的方法每一段又采用分页的方法l逻辑地址结构：（逻辑地址结构：（s,p,ds,p,d）l主存分配：以页为单位非连续分配主存分配：以页为单位非连续分配l数据结构：段表、页表、段表地址寄存器数据结构：段表、页表、段表地址寄存器操作系统PPT课件 (2)段表寄存器：段表始址，段表长度段表寄存器：段表始址，段表长度段表：段表： 给出页表始址，页表长度给

43、出页表始址，页表长度页表：页表： 指出该段的指出该段的 每页在内存的页架号每页在内存的页架号数据结构数据结构 操作系统PPT课件 (2)段页式地址转换段页式地址转换0123段 表 寄 存 器 段 表 始 址 段 表 长 度段 超 长 段 号s页 号p页 内 地 址0123段 表页 表b 块 号b块 内 地 址页 表 长 度页 表 始 址操作系统PPT课件 (2)快表的内容快表的内容 段号 虚页号 页架号 保护信息 AGE 有效位操作系统PPT课件 (2)段页式管理算法段页式管理算法 启动要处理的指令启动要处理的指令计算有效地址计算有效地址访问地址访问地址V=( s,p,d)S段表长度？段表长度

44、？段在主存？段在主存？P页表长？页表长？访问类型合法？访问类型合法？页在主存？页在主存？缺页中断处理缺页中断处理形成主存地址形成主存地址访问该地址访问该地址执行下一条指令执行下一条指令YN越界中断越界中断出错处理出错处理缺段中断处理缺段中断处理NN允许动态增加允许动态增加YYYYNNNY出错处理出错处理操作系统PPT课件 (2)段页式存储管理的优缺点段页式存储管理的优缺点优点：优点：l提供虚拟存储器的功能提供虚拟存储器的功能l无紧缩问题，无页外碎片无紧缩问题，无页外碎片l便于处理变化的数据结构便于处理变化的数据结构l便于共享便于共享l提供了动态连接的便利提供了动态连接的便利l便于控制存取访问便

45、于控制存取访问缺点：缺点：l增加了硬件成本增加了硬件成本l增加了软件复杂性和增加了软件复杂性和管理的开销管理的开销l有页内碎片有页内碎片操作系统PPT课件 (2)页的置换算法页的置换算法l页面访问失效及处理页面访问失效及处理l页面置换算法页面置换算法操作系统PPT课件 (2)页面访问失效及处理页面访问失效及处理引起失效的原因：引起失效的原因：l边界错误边界错误 纯分页：纯分页：页号超过页表长度页号超过页表长度 纯分段：纯分段：偏移量超过段长，段号超过段表长度偏移量超过段长，段号超过段表长度 段页式：段页式：页号超过该段的页表长度页号超过该段的页表长度l有效性错误：有效性错误：缺页或缺段中断缺页

46、或缺段中断l保护错误：保护错误：访问权限错误访问权限错误操作系统PPT课件 (2)页面置换算法页面置换算法l最佳置换算法最佳置换算法OPTOPTl先进先出置换算法先进先出置换算法FIFOFIFOl两次机会置换算法两次机会置换算法l时钟页面置换算法时钟页面置换算法CLOCKCLOCKl最近最少使用置换算法最近最少使用置换算法LRULRUl最近未使用置换算法最近未使用置换算法NURNURl最不经常使用置换算法最不经常使用置换算法LFULFU操作系统PPT课件 (2)最佳置换算法最佳置换算法OPTl原则：淘汰将来再也不被访问，或者是在原则：淘汰将来再也不被访问，或者是在最远的将来才被访问的页。最远的

47、将来才被访问的页。l该算法命中率最高是一种理论算法。该算法命中率最高是一种理论算法。操作系统PPT课件 (2)先进先出置换算法先进先出置换算法FIFOl原则：选择最早进入主存的页面淘汰原则：选择最早进入主存的页面淘汰l缺点：缺点：最早进入主存的页面可能是经常被使用的页最早进入主存的页面可能是经常被使用的页命中率较低命中率较低异常现象：进程所分的页架数越多，缺页次数也异常现象：进程所分的页架数越多，缺页次数也越多越多操作系统PPT课件 (2)两次机会置换算法两次机会置换算法l原则：把原则：把FIFOFIFO算法与访问位结合，若最早算法与访问位结合，若最早进来的页访问位为进来的页访问位为0 0，则

48、置换出去，若访问，则置换出去，若访问位为位为1 1，则把它置入链尾，再给它一次机会。，则把它置入链尾，再给它一次机会。l命中率优于命中率优于FIFOFIFO，有异态。，有异态。操作系统PPT课件 (2)时钟页面置换算法时钟页面置换算法CLOCK两次机会置换算法的改进。两次机会置换算法的改进。实现：把所有的页面保存在一个类似时钟实现：把所有的页面保存在一个类似时钟表面的环形链表中。有一个指针指向最老表面的环形链表中。有一个指针指向最老的页面。当产生缺页时，检查指针指向的的页面。当产生缺页时，检查指针指向的页面，如果它的访问位为页面，如果它的访问位为0 0，就淘汰该页，就淘汰该页，并把新页插入这个

49、位置，指针前移一个位并把新页插入这个位置，指针前移一个位置；如果访问位为置；如果访问位为1 1，就清除访问位并把，就清除访问位并把指针前移一个位置，重复这个过程直到找指针前移一个位置，重复这个过程直到找到一个访问位为到一个访问位为0 0的页为止。的页为止。操作系统PPT课件 (2)最近最少使用置换算法最近最少使用置换算法LRUl原则：选择最长时间未被访问的页面原则：选择最长时间未被访问的页面l基于程序的局部性原理，命中率较高基于程序的局部性原理，命中率较高l实现较困难实现较困难l方法：计数法方法：计数法 n n n n矩阵法矩阵法 堆栈堆栈操作系统PPT课件 (2)最不经常使用置换算法最不经常

50、使用置换算法LFU该算法在需要淘汰某一页时，首先淘汰到该算法在需要淘汰某一页时，首先淘汰到当前时间为止，被访问次数最少的那一页。当前时间为止，被访问次数最少的那一页。方法：为每页设置一计数器，访问一次，方法：为每页设置一计数器，访问一次， 计数器加计数器加1 1，找到该页，计数器清，找到该页，计数器清0 0。操作系统PPT课件 (2)最近未使用置换算法最近未使用置换算法NURl原则：原则：1 1、淘汰未被访问过的页、淘汰未被访问过的页 2 2、淘汰未被修改过的页、淘汰未被修改过的页l硬件：为每页增设两个硬件位硬件：为每页增设两个硬件位访问位，修改位访问位，修改位 访问位访问位=0=0，未访问，

51、未访问 访问位访问位=1=1，已访，已访问问 修改位修改位=0=0，未修改，未修改 修改位修改位=1=1，已修，已修改改 操作系统PPT课件 (2)FIFOCLOCK=TWO CHANCE LRUOPTFIFO，CLOCK有异态有异态操作系统PPT课件 (2)举例举例如果页面的引用顺序为如果页面的引用顺序为2 2，3 3，2 2，1 1，5 5，2 2，4 4，5 5，3 3，2 2，5 5，2 2，而分配给它们内存页，而分配给它们内存页架数为架数为3 3，用，用OPTOPT，LRULRU，FIFOFIFO，CLOCKCLOCK计算它的缺页次数。计算它的缺页次数。操作系统PPT课件 (2) 2

52、 3 2 1 5 2 4 5 3 2 5 2 2 2 2 2* 5 5 5* 5* 3 3 3 3 3 3 3 3* 2 2 2 2* 2* 5 5 1 1 1* 4 4 4 4 4* 2 调 调 中 调 替 替 替 中 替 中 替 替 FIFO操作系统PPT课件 (2) 2 3 2 1 5 2 4 5 3 2 5 2 2 2 2 2 2* 2 2 2* 3 3 3* 3* 3 3 3* 5 5 5* 5 5 5* 5 5 1 1 1* 4 4 4* 2 2 2 调 调 中 调 替 中 替 中 替 替 中 中 LRU操作系统PPT课件 (2) 2 3 2 1 5 2 4 5 3 2 5 2 2

53、 2 2 2 2 2* 4* 4* 4* 2 2 2 3 3 3 3* 3 3 3 3 3* 3* 3* 1* 5 5 5 5 5 5 5 5OPT调 调 中 调 替 中 替 中 中 替 中 中操作系统PPT课件 (2) 2 3 2 1 5 2 4 5 3 2 5 2 2 2 2* . 2* 2 2* . 2* . 2* . 2 . 2* . 2* . 2*. 3 3 3 5 5 5 5* 5 5 5* 5* . . 1 . 1 . 1 4 4 3 3 3 3CLOCK 调 调 中 调 替 中 替 中 替 中 中 中操作系统PPT课件 (2)页架分配算法页架分配算法l物理主存物理主存l空闲页面

54、链表空闲页面链表l页架分配中有关策略页架分配中有关策略l分页环境中程序的行为特性分页环境中程序的行为特性操作系统PPT课件 (2)物理主存物理主存l低地址端的非换页池：用于内核代码，静低地址端的非换页池：用于内核代码，静态分配区。态分配区。l高地址端：保存系统崩溃时产生的错误信高地址端：保存系统崩溃时产生的错误信息息l中间部分的换页池：用户的进程页面，内中间部分的换页池：用户的进程页面，内核动态分配的页面核动态分配的页面操作系统PPT课件 (2)空闲页面链表空闲页面链表为加速进程运行，系统通过某种算法始终为加速进程运行，系统通过某种算法始终维护一个可用的空闲页面表。维护一个可用的空闲页面表。操

55、作系统PPT课件 (2) 特点：特点：l用一专门的独立进程负责页面替换工作用一专门的独立进程负责页面替换工作l链表中的页面并非真正空闲页面链表中的页面并非真正空闲页面l置换并不是页在主存中的移动置换并不是页在主存中的移动操作系统PPT课件 (2)页架分配中有关策略页架分配中有关策略l调入策略（预调，请调）调入策略（预调，请调）l局部和全局置换，固定和可变分配局部和全局置换，固定和可变分配l工作集工作集l页的大小页的大小操作系统PPT课件 (2)调入策略调入策略 l提前分配（预调）根据程序的结构特性和提前分配（预调）根据程序的结构特性和程序运行的过去行为预测将来行为，在实程序运行的过去行为预测将

56、来行为，在实际运行前，将要运行的程序调入内存际运行前，将要运行的程序调入内存 。l请求分配（请调）在需要的时候才调入要请求分配（请调）在需要的时候才调入要运行的程序。运行的程序。操作系统PPT课件 (2)局部和全局置换，固定和可变分配局部和全局置换，固定和可变分配l固定分配：进程的页架数不变。固定分配：进程的页架数不变。l可变分配：进程的页架数是可变的。可变分配：进程的页架数是可变的。l全局置换：从整个主存中选择淘汰页。全局置换：从整个主存中选择淘汰页。l局部置换：从自己以占有的页架中选择淘局部置换：从自己以占有的页架中选择淘汰页。汰页。操作系统PPT课件 (2) l固定分配，局部替换固定分配

57、，局部替换l可变分配，全局替换可变分配，全局替换l可变分配，局部替换可变分配，局部替换操作系统PPT课件 (2)工作集工作集一个运行进程在一个运行进程在t-wt-w到到t t这个时间间隔内所这个时间间隔内所访问的页的集合称为该进程在时间访问的页的集合称为该进程在时间t t的工作的工作集，记为集，记为W W（t,wt,w） W W（t,wt,w）为工作集尺寸：工作集中包含的）为工作集尺寸：工作集中包含的页面数。页面数。操作系统PPT课件 (2)页的大小页的大小l大页面：页内碎片大，缺页次数多大页面：页内碎片大，缺页次数多l小页面：页表空间大小页面：页表空间大l大页面：可减少输入输出工作大页面：可

58、减少输入输出工作操作系统PPT课件 (2)分页环境中程序的行为特性分页环境中程序的行为特性l局部性的概念局部性的概念l分页环境中程序的行为特性分页环境中程序的行为特性l减少访问离散性的程序结构减少访问离散性的程序结构操作系统PPT课件 (2)局部性的概念局部性的概念l时间局部性：某个位置最近被访问，那么时间局部性：某个位置最近被访问，那么往往很快又要被访问。往往很快又要被访问。l空间局部性：某个位置最近被访问，则它空间局部性：某个位置最近被访问，则它附近的位置也会被访问。附近的位置也会被访问。操作系统PPT课件 (2)减少访问离散性的程序结构减少访问离散性的程序结构For j:=1 to 51

59、2do For i:=1 to 512do Ai,j:=0 For i:=1 to 512do For j:=1 to 512do Ai,j:=0 若以行序为主序存数若以行序为主序存数第一种编制：程序执行产第一种编制：程序执行产生生512512* *512=262144512=262144次缺页次缺页第二种编制：程序执行产第二种编制：程序执行产生生512512次缺页次缺页操作系统PPT课件 (2)方法功能分区式页式段式段页式固定 可变纯 请求适用环境 多道 多道 多道 多道 虚拟空间 一维 一维 二维 二维 重定位 静态 动态 动态 动态 动态分配方式 分配连续区以页为单位非连续以段为单位非连

60、续以页为单位非连续释放 执行完全部释放分区释放执行完全部释放淘汰与执行完释放 同左 同左保护 同左 同左 越界保护与存储键覆盖与交换越界保护与控制权保护 同左 同左 同左同左内外存统一管理虚存内存扩充 共享 不能 较难 方便 方便 硬件支持保护用寄存器重定位机构地址变换机构中断机构 保护机构地址变换机构中断机构保护机构动态链接机构操作系统PPT课件 (2)某虚拟存储器的用户空间共有某虚拟存储器的用户空间共有3232个页面，个页面，每页每页1KB1KB，主存，主存16KB16KB试问：试问：1.1.逻辑地址的有效位是多少？逻辑地址的有效位是多少？ 2.2.物理地址需要多少位？物理地址需要多少位？ 3.3