第7章 操作系统ppt课件 07主存管理.ppt

第七章 主存管理,（一） 主存的共享方式（二） 主存管理的功能（三） 分区存储管理技术（四） 页式存储管理技术（五） 段式及段页式存储管理技术,2,计算机系统存储结构,内存管理的目的,操作系统的“方便”性便于用户装入程序，无须了解底层细节可实现动态的存储空间伸缩，适应不同程序的需要操作系统的“合理”性合理分配内存空间，保证多道程序的顺利运行合理保护内存空间，防止各种可能的破坏泄漏操作系统的“有效性”有效保持内存空间的可用性，防止对资源的浪费有效实现“小空间大容量”，提高计算机的适应性有效配合CPU的调度过程，实现系统运行的稳定,（一） 主存的共享方式,内存储器（简称内存、主存、物理存储器） 处理机能直接访问的存储器。用来存放系统和用户的程序和数据，其特点是存取速度快，断电信息丢失。,主存的共享方式包含三种：,大小不等的区域 分区存储管理 分段存储管理 大小相等的片 页式存储管理 两者结合 段页式存储管理,（二）主存管理的功能,一. 几个概念1、物理地址（绝对地址、实地址）：把内存分成若干个大小相等的存储单元，每个单元给一个编号，这个编号称为内存地址，是计算机主存单元的真实地址。存储单元占8位，称作字节（byte）。2. 物理地址空间：物理地址的集合称为物理地址空间（主存地址空间），它是一个一维的线性空间。,3. 逻辑地址（相对地址、虚地址）:用户编程序时所用的地址。基本单位可与内存的基本单位相同，也可以不相同。4. 逻辑地址空间（作业地址空间、虚地址空间）:用户的程序地址的集合称为逻辑地址空间，它的编址总是从0开始的。,二. 主存管理的功能,1. 地址映射将程序地址空间中使用的逻辑地址变换成主存中的地址的过程。2. 主存分配 按照一定的算法把某一空闲的主存区分配给作业或进程。3. 存储保护 保证用户程序(或进程映象)在各自的存储区域内操作，互不干扰。4. 主存扩充（提供虚拟存储技术）向用户提供一种不受物理存储器大小和结构限制的用户编程时使用的存储器。即使在用户程序比主存容量还要大的情况下，程序也能正确运行。,1. 主存功能地址映射, ,（1）为什么要进行地址映射 作业的相应进程在处理机上运行时，所要访问的指令和数据的物理地址和作业地址空间中的地址是不同的。,将500号单元处的数据123送到寄存器r1中,（2）地址映射的定义将程序地址空间中使用的逻辑地址变换成主存中的地址的过程称为地址映射。有时也称为地址重定位。 （3）地址映射的方式编程或编译时确定地址映射关系静态地址映射动态地址映射,静态地理映射定义： 在作业装入过程中随即进行的地址变换方式称为静态重定位或静态地址映射。,动态地址映射定义： 在程序运行时确定地址映射关系。在程序执行期间，随着每条指令和数据的访问自动地连续地进行地址映射。,静态地址映射与动态地址映射的区别,构造分配用的数据结构 主存资源信息块（M_RIB）、空闲区队列等等 制定分配策略,2、主存功能主存分配,实施主存分配与回收,主存扩充也就是提供虚拟存储器 1）问题的提出,3、主存扩充,物理存储器容量是有限的，用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大得多。在主存容量十分紧张的情况下，如何让用户使用计算机不受主存容量的限制？,2）解决问题的思路 装入部分程序地址空间，它还能正确地执行？3）实现方法 程序的全部代码和数据存放在辅存中； 将程序当前执行所涉及的那部分程序代码放入主存中； 程序执行时，当所需信息不在主存，由操作系统和硬件相配合来完成主存从辅存中调入信息，程序继续执行。,4. 什么是虚拟存储器,由操作系统和硬件相配合来完成主存和辅存之间的信息的动态调度。这样的计算机系统好像为用户提供了一个其存储容量比实际主存大得多的存储器（虚拟存储器）。,5. 虚拟存储器的核心 逻辑地址与物理地址分开 主存空间与地址空间分开 提供地址变换机构 6. 实现虚拟存储器的物质基础 有相当容量的辅存 足以存放多用户的作业的地址空间 有一定容量的主存 存放运行进程的当前信息 地址变换机构,4、存储保护,1）什么是存储保护在多道程序设计的环境下，系统中有系统程序和多个用户程序同时存在，如何保证用户程序不破坏系统程序，用户程序之间不相互干扰？主存储器按区分配给各用户程序使用。为了互不影响，由硬件(软件配合)保证每道程序只能在给定的存储区域内活动，这种措施叫做存储保护。2）存储保护方法 通常的存储保护方法 界地址保护和存储键保护（不介绍）,(1) 上、下界防护,下界寄存器：存放程序装入内存后的开始地址上界寄存器：存放程序装入内存后的末地址判别式：下界寄存器 物理地址 上界寄存器,(2) 基地址、限长防护,基址寄存器=下界寄存器 （首地址）限长寄存器：存放程序长度基址+限长=上界寄存器 （末地址）判别式：基址寄存器物理地址基址+限长寄存器,23,作业,第7章 第2题,（三） 分区存储管理,分区存储管理分为：1. 固定分区2. 动态分区（可变分区）,25,固定分区,固定分区,一. 动态分区分配1. 什么是动态分区分配 在处理作业的过程中，建立分区，依用户请求的大小分配分区。 思想：分区的大小、数量和位置随内存中进程的大小和数量动态变化（根据作业的实际需要在装入内存时动态地分配连续的内存空间）。,(1) 动态分区的分配过程,作业1申请 32KB,作业2申请 14KB,作业3申请 64KB,作业4申请 100KB,作业5申请 50KB,(2) 动态分区的回收过程,29,2、分区分配机构 1) 主存资源信息块 在动态分区方法中，描述主存资源的数据结构是主存资源信息块,2) 分区描述器和空闲队列 主存中的每一个分区都有相应的分区描述器（pd）说明分区的特征信息。flag： 为 0空闲区; 为 1已分配区 size： 分区大小 next：空闲区自由主存队列中的勾链字;已分配区此项为零,m_rib,pd,30,自由主存队列 (或空闲区队列) 结构在主存分配中，主要讨论空闲区描述器和空闲区队列。下面是在t时刻的主存分布、空闲区描述器的内容和空闲区队列结构。,空闲区表的组织有两种方法：1、按空闲区大小的升序（降序）组织；2、按空闲区首址升序（降序）组织。,3、分区的分配与放置策略,1）分区分配 用户请求分配一个主存块 分区分配程序在自由主存队列中找一个满足用户需要的空闲块 若找到，则返回所分配区域的首址，否则， 告之不能满足要求。,2）放置策略选择空闲区的策略，称为放置策略。 空闲区表的组织有两种方法：1、按空闲区大小的升序（降序）组织；2、按空闲区首址升序（降序）组织。 根据空闲区表组织的方法的不同，有不同的放置策略：首次适应算法、最佳适应算法和最坏适应算法三种。,33,1）首次适应算法空闲区按起始地址递增的顺序排列，将作业放到最先找到的空闲分区。,34,2）最佳适应算法 空闲区按由小到大的顺序排列，将作业放到满足要求的最小的空闲分区。,35,3）最坏适应算法空闲区按由大到小的顺序排列，将作业放到满足要求的最大的空闲分区。,几种放置策略的比较,例如：某时刻系统中有三个空闲区，其大小和首址为：(35KB，100KB)、(12KB，156KB)、(28KB，200KB)有一作业系列： (JOB1，12KB)、(JOB2，30KB)、(JOB3，28KB)用首次适应算法、最佳适应算法和最坏适应算法来处理该作业序列，看哪种算法合适？注：设分配时从空闲区的高地址分割，以保持剩余空闲区的起始地址不变。,首次适应算法,100KB,作业1（12KB）放到首址100KB的空闲区,100KB,作业2（30KB）不能分配作业3（28KB）放到首址200KB的空闲区,最佳适应算法,156KB,作业1（12KB）放到首址156KB的空闲区,200KB,作业2（30KB）放到首址100KB的空闲区作业3（28KB）放到首址200KB的空闲区,100KB,最坏适应算法,100KB,作业1（12KB）放到首址100KB的空闲区,作业2（30KB）不能继续分配作业3（28KB）放到首址200KB的空闲区,200KB,四、碎片问题及拼接技术,1. 什么是碎片问题在已分配区之间存在着的一些没有被充分利用的空闲区。如何解决碎片问题？ 2. 拼接技术所谓拼接技术是指移动存储器中某些已分配区中的信息，使本来分散的空闲区连成一个大的空闲区。,41,OS,400KB,JOB1(100KB),JOB2(200KB),0,300KB,JOB6(100KB),800KB,700KB,900KB,JOB5(100KB),JOB4(100KB),JOB7(100KB),600KB,1000KB,1024KB,OS,400KB,JOB2(200KB),0,300KB,JOB6(100KB),800KB,700KB,900KB,JOB5(100KB),JOB4(100KB),JOB7(100KB),600KB,1000KB,空闲(24KB),1024KB,空闲(100KB),OS,400KB,JOB2(200KB),0,300KB,800KB,700KB,900KB,JOB5(100KB),JOB7(100KB),600KB,1000KB,空闲(24KB),1024KB,空闲(100KB),空闲(100KB),空闲(100KB),有一大小为200K的作业需要运行!,空闲(24KB),分区管理的优缺点,优点：实现了多道程序共享主存。实现分区管理的系统设计相对简单，不需要更多的系统软硬件开销。实现存储保护的手段也比较简单。缺点：主存利用不够充分。系统中总有一部分存储空间得不到利用，这部分被浪费的空间叫碎片。没有实现主存的扩充问题。 当作业的地址空间大于存储空间时，作业无法运行。也即作业的地址空间受实际存储空间限制。,（四） 页式存储管理,一. 问题的提出分区存储管理的主要问题是碎片问题。在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，提出了分页存储管理技术。,二. 页式系统的基本概念,1. 页面程序的地址空间被等分成大小相等的片，称为页面，又称为虚页。2. 主存块主存被等分成大小相等的片，称为主存块，又称为实页。,作业页面与主存块的关系,页表地址映射,3. 页表,（1）什么是页表为了实现从地址空间到物理主存的映象，系统建立的记录页与内存块之间对应关系的地址变换的机构称为页面映像表，简称页表。 包括用户程序空间的页面与内存块的对应关系、页面的存储保护和存取控制方面的信息。,三. 页式地址变换,1. 虚地址结构虚地址是用户程序中的逻辑地址，它包括页号和页内地址（页内位移）。区分页号和页内地址的依椐是页的大小，页内地址占虚地址的低位部分，页号占虚地址的高位部分。【例】设虚地址长度为16位，页面大小为1KB：页号 页内地址（位移量） P W 15 10 9 0,49,如何方便将逻辑地址线性分割求出页号P和页内位移W：逻辑地址以十进制数给出：页号P=逻辑地址 % 页大小页内位移W=逻辑地址 mod 页大小逻辑地址以十六进制、八进制、二进制的形式给出：将逻辑地址转换成二进制；按页的大小分离出页号P和位移量W（低位部分是位移量，高位部分是页号）；,50,【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB。解：求虚地址 3412P3412 2048 1W 3412 mod 2048 1364求虚地址 7145：P7145 2048 3W7145 mod 2048 1001,51,【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB。虚地址0AFEH：0000 1010 1111 1110P1 W010 1111 1110虚地址1ADDH：0001 1010 1101 1101P3 W010 1101 1101,例1 页面大小是1KB，虚地址是3BADH例2 页面大小是2KB，虚地址是3BADH,53,2、地址变换根据逻辑地址求物理地址的步骤：1）将逻辑地址线性分割求出页号P和页内位移W：2）根据页号查页表得块号B；3）物理地址=块号B页大小+页内位移W,54,0 0 0 1 1 1,0 1 1 1 0 0 0 1 0 0,55,【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。解：求虚地址 3412P3412 2048 1W 3412 mod 2048 1364MR=9*2048+1364=19796求虚地址 7145：P7145 2048 3W7145 mod 2048 1001MR=5*2048+1001=11241,56,【例】：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成内存地址。解：求虚地址0AFEH的物理地址：0000 1010 1111 1110P1 W010 1111 1110MR0100 1010 1111 11104AFEH求虚地址1ADDH的物理地址：0001 1010 1101 1101P3 W010 1101 1101MR0010 1010 1101 11012ADDH,57,课堂练习： 1、某作业J的逻辑空间为4页，每页2048B，已知该作业J的页表如下：页号：0 1 2 3块号：2 4 6 8 求：逻辑地址为0A65H的物理地址。2、某作业有4个页面，分别装入主存的3、4、6、8块中，设页面尺寸为1024B（1）、写出该作业的页表；（2）、求mov 2100,3100指令中两个操作数的物理地址。,四. 请调策略,1、请调策略定义： 在页式系统中，允许一个作业程序只装入部分页面即可投入运行，需要信息时动态调入，这种装入信息的策略称为请调策略。 (1) 怎样发现所访问的页面在不在主存？ (2) 当发现所需访问的页面不在主存时如何处理?,2. 扩充页表功能 中断位 i标识该页是否在主存若i=1，表示此页不在主存若i=0，表示该页在主存 辅存地址该页面在辅存的位置,3. 缺页处理过程 （举例说明）,作业2的主存块数为 m2=3，页面大小为1KB。 当程序执行 “mov r1，2120”时 CPU产生的虚地址为2120 分页机构得 p=2，w=72 查页表。该页中断位i=1， 则发生缺页中断, 如主存中有空白块，且nm 则直接调入 如主存中无空白块，或n m ，则需淘汰该作业在主存中的一页（其中n 代表作业已分配到的主存块数， m 为内存为作业准备的物理块数）。,缺页处理流程,4. 淘汰策略,1. 什么是淘汰策略用来选择淘汰哪一页的规则就叫做置换策略，或称淘汰算法。常用算法：1、最优算法OPT:(optimal page-replacement algorithm)置换在最长时间内不会使用的页)2、先进先出算法FIFO：淘汰先调入内存的页3、最近最少使用淘汰算法LRU：淘汰未被访问的页中时间最长的页;(Least Recently Used) 使用缺页中断率f衡量页面淘汰算法的优劣： ffa （a是总的页面访问次数，f是缺页中断次数）,2. 扩充页表的功能,页表应增加相应的内容，反映该页是否在内存，在外存的位置，在内存的时间的长短等。 引用位：0 表示最近没有进程访问 1 表示最近有进程访问 改变位：0 该页调入内存后没有修改 1 该页调入内存后修改过,3. 颠簸,颠簸(thrashing)，又称为“抖动”。简单地说，导致系统效率急剧下降的主存和辅存之间的频繁页面置换现像称为“抖动”。,OPT原理（难实现）：当要调入一新页而必须先淘汰一旧页时，所淘汰的那一页应是以后不再要用的，或者是在最长的时间以后才会用到的那页。 缺页率假定程序p共有n页，系统分配m块，有1mn 若程序p在运行中:成功的访问次数： s 不成功的访问次数： f 则缺页中断率： f=f/ (s+ f)*100% f=f (r，m，p),4. 页面置换算法OPT算法,例：假设系统为某进程分配了3个物理块，并考虑有以下的访问串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1，求缺页率。,7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1,缺页率f=(9/20)*100%=45%,(2) 先进先出淘汰算法(FIFO算法) 1) 什么是先进先出淘汰算法 原理：总是选择在主存中居留时间最长(即最老)的一页淘汰。 2) 先进先出淘汰算法的实现方法 建立一个页面进入主存的先后次序表； 建立一个替换指针，指向最早进入主存的页面； 当需要置换一页时，选择替换指向的那一页，然 后调整替换指针的内容。,69,【例】某进程的页面访问序列：1、2、3、4、1、2、5、1、2、3、4、5，指出在驻留集大小分别为3和4时，使用FIFO置换算法的缺页率，结果说明了什么？（设驻留集M表示分给该作业的内存块数）解：FIFO M3 f fa91275% M4 f101283%,70,1,2,3,4,1,2,5,1,2,3,4,5,t,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,5,5,5,5,5,5,1,2,5,1,2,3,4,1,2,5,1,3,4,5,t,1,1,1,4,3,3,4,5,2,2,2,4,4,5,1,1,3,3,2,3,3,4,4,3,2,4,5,5,1,2,2,2,3,2,2,3,4,1,5,1,1,1,2,采用FIFO算法,(3) 最久未使用淘汰算法(LRU算法) 总是选择最长时间未被使用的那一页淘汰。 LRU算法的实现方法 用引用位考察页面的使用情况； 当访问页面时，将引用位置1，并记时； 当要淘汰一页时，选择时间最长的一页淘汰。 要精确实现很困难 硬件方法：采用寄存器（计时法） 软件方法：采用页号栈,72,【例】某进程的页面访问序列：1、2、3、4、1、2、5、1、2、3、4、5，指出在驻留集大小分别为3和4时，使用LRU置换算法的缺页率，？（设驻留集M表示分给该作业的内存块数）解： LRU M3 f fa101283% M4 f fa81267%,73,1,2,3,4,1,2,5,1,2,3,4,5,t,1,1,1,1,1,1,2,5,2,2,2,2,2,5,1,1,3,3,3,3,3,4,4,4,4,4,5,5,1,2,2,2,3,1,2,1,2,3,4,1,2,5,1,3,4,5,t,1,1,1,1,1,1,2,5,2,2,2,2,2,5,1,1,3,3,3,3,3,4,4,4,4,4,5,5,1,2,2,2,3,2,4,4,4,1,5,2,3,1,2,采用LRU算法,练习,在分页虚拟存储管理系统中，假设系统为某进程分配了四个主存块（将开始4页先装入主存），进程执行时页的引用顺序为：7,1,2,0,3,0,4,2,3,0,3,2,7,0,1，求分别采用OPT、FIFO、LRU算法计算产生多少次缺页中断？产生多少次缺页置换？依次淘汰的页是什么？缺页率为多少？,