第六章存储管理重要资源“瓶颈”:关键、紧张帕金森定律:内存多大,程序多长存储器的层次结构高高高高(Cache)高高高高高高高高快贵慢存储器的层次结构高速缓存(Cache):少量的、非常快速、昂贵、易变的。内存(RAM):若干兆字节、中等速度、中等价格、易变的。磁盘:数百兆或数千兆字节、低速、廉价、不易变的。存储器的层次结构由操作系统协调这些存储器的使用。重要性:直接存储要求内存速度尽量快到与CPU取值速度相匹配,大到能装下当前运行的程序与数据,否则CPU执行速度就会受到内存速度和容量的影响而得不到充分发挥。存储器的层次结构内存:是由存储单元(字节或字)组成的一维连续的地址空间,简称内存空间。用来存放当前正在运行程序的代码及数据,是程序中指令本身地址所指的,亦即程序计数器所指的存储器。内存可以分为:系统区:用于存放操作系统。用户区:用于装入并存放用户程序和数据。存储管理的目的1、充分利用内存,为多道程序并发执行提供存储基础。2、尽可能方便用户使用。自动装入用户程序用户程序中不必考虑硬件细节3、系统能够解决程序空间比实际内存空间大的问题。存储管理的目的4、程序在执行时可以动态伸缩;5、内存存取速度快;6、存储保护与安全;7、共享与通信;8、了解有关资源的使用情况;9、实现性价比。6.1存储管理的功能1、存储分配记录内存的使用情况——设置相应的内存分配表(内存分配回收的依据)内存空间的划分问题?——静态或动态,等长或不等长6.1存储管理的功能内存分配表位示图表示法:用一位(bit)表示一个空闲页面(0:空闲,1:占用)10…1…0第0页第i页第1页第n-1页6.1存储管理的功能空闲页面表:包括首页面号和页面个数,连接若干个页面作为一组登记在表中空闲块表:空闲块首地址和空闲块长度,没有记录的区域即为进程所占用空闲块链表:将所有的空闲块连成一个链表。6.1存储管理的功能确定分配算法实施内存分配回收内存分配回收方式:静态分配与动态分配6.1存储管理的功能2、存储共享内存共享:两个或多个进程共用内存中相同的区域目的:节省内存空间,提高内存效率。实现进程通信(数据共享)共享内容:代码共享(要求代码为纯代码)数据共享6.1存储管理的功能3、存储保护目的:为多个程序共享内存提供保障,使在内存中的各道程序,只能访问它自己的区域,避各道程序间相互干扰,特别是当一道程序发生错误时,不至于影响其它程序的运行。通常由硬件完成保护功能,由软件辅助实现。含义:——保护系统程序不被用户侵犯——不允许用户程序读写不属于自己地址空间的数据6.1存储管理的功能保护过程:每个进程都有自己独立的进程空间,如果一个进程在运行时所产生的地址在其地址空间之外,则发生地址越界。即当进程要访问某个内存单元时,由硬件检查是否允许,如果允许则执行,否则产生地址越界中断,由操作系统进行相应处理。一般由硬件提供一对寄存器——基址寄存器:存放起始地址——限长寄存器:存放长度(上下界寄存器)6.1存储管理的功能4、存储扩充通过虚拟存储技术实现用户在编制程序时,不应该受内存容量限制,所以要采用一定的技术来“扩充”内存容量,使用户得到比实际内存容量大得多的内存空间。具体实现:在硬件的支持下,软硬件相互协作,将内存和外存结合起来统一使用。通过这种方法把内存扩充,使用户在编制程序时不受内存限制。6.1存储管理的功能5、地址映射(地址重定位、地址变换)逻辑地址(相对地址、虚地址)物理地址(绝对地址、实地址)地址映射源程序目标文件(逻辑地址空间)运行时(物理地址空间)编译、链接库函数地址映射6.1存储管理的功能由于用户的逻辑地址空间都是从0开始的,而当该程序装入内存运行时又不是从0开始,因此就需要将逻辑地址转换成实际的内存地址。6.3存储管理方式单一连续的存储管理固定分区的存储管理可变分区的存储管理程序浮动、多重分区页式存储管理交换、覆盖请求页式管理(虚拟存储管理)段式存储管理段页式存储管理6.3.1单一连续的存储管理所谓单一,是指内存中只驻留一道作业。为便于地址转换,把作业连续的存放在内存中,而不是离散的存放。单一连续的存储管理思想主要用在早期的单道批处理系统中,采用静态分配的方式,即作业或进程一进入内存,就要等到它运行结束后才能释放内存。优缺点优点:方法简单,易于实现。缺点:1)内存利用率低:一个作业独占主存储空间,降低存储空间的利用率;2)处理器利用率低:处理器和外部设备串行工作;3)外设的利用率低:系统中的资源为一个用户控制。分区式存储管理分区管理的基本思想就是给每一个内存中的进程划分一段存储区,用以连续存放各进程的程序和数据,使各进程并发执行。这是能满足多道程序设计需要的最简单的存储管理技术固定式分区动态式分区预先把可分配的内存空间分割成若干个连续区域,每一区域称为分区。每个分区的大小可以相同,也可以不同。分区大小固定不变,每个分区装一个且只能装一个作业。两个固定:1、各分区的大小固定不变;2、总分区的个数固定不变。1、固定式分区存储分配情况操作系统区(8K)用户分区1(8K)用户分区2(16K)用户分区3(16K)用户分区4(16K)用户分区5(32K)用户分区6(32K)缺点1、预先规定了分区大小,大程序无法装入,必须采用覆盖技术;2、主存的利用率不高:每个分区的作业不可能恰好占满该区,剩余的部分空间又不能为其它作业利用。——碎片问题3、内存的扩充和共享是困难的。在作业装入和处理过程中建立分区,并且要使分区的容量能正好适应作业的大小。在作业进入系统前,根据作业的大小来申请所需存储容量,然后由系统分配。可变式分区,通常采用动态重定位的方法来实现地址转换。存储保护仍用界地址存储器,不具备虚拟存储器的功能。两个可变:1、各分区的大小可变;2、总分区的个数可变。2、可变式分区OSOSOSOS进程A进程A进程A进程A进程B进程B进程C进程B进程C进程D进程A8K进程B16K进程C64K进程D124K存储分配情况在系统初始状态,除了操作系统常驻内存部分之外,只有一个空闲分区,随后,分配程序将该区划分给调度选中的作业。分区式存储管理系统为了管理主存分区分配情况,需要建立两个张表,他们是一张分区表和一张可用空间表。分区表可用空间表区号分区长度起始地址进程号120K30K1851223K56K4490316K110K206412K200K1123序号可用空间长度可用空间起始地址15K50K230K80K373K127K1)最佳适应算法优点:1)平均而言,只要查找一半的表格便能找到最佳适应的空闲区;2)如果有一个空闲区的容量正好满足要求,则它必被选中;3)如果不存在恰好满足需要的空闲区,则选择一个容量接近的空闲区,而较大的空闲区被保留下来。以后如果要求分配一个较大的空闲区时,就容易得到满足。缺点:空闲区一般不可能恰好满足要求,在分配之后的剩余部分通常非常小,以致小到无法使用。换言之,发展下去最后剩下许多非常小的空闲区(即形成碎片)。2)最差适应算法优点:1)只要比较第一项就能判定能否满足要求,如满足要求便立即进行分配;2)分配后剩下的空闲区可能比较大,可供以后使用。缺点:分配进行一段时间以后就不能满足对于较大空闲区的分配要求。3)最先适应算法优点:空闲区按从小到大排列时,最先适用分配算法能尽可能使用低地址区,从而高地址空间有较大的空闲区容纳大的作业。缺点:在低地址部分很快集中了许多非常小的空闲区,因而在空闲区分配时,搜索次数增加,影响工作效率。适应算法的比较搜索空闲区速度及主存利用率:最先适应分配、最佳适应算法比最坏适应算法性能好。如果空闲区按从小到大排列,则最先适用分配算法等于最佳适应分配算法。如果空闲区按从大到小排列,则最先适用分配算法等于最坏适应分配算法。最先适应算法简单、快速,在实际的操作系统中用得较多;其次是最佳适应算法。程序浮动ABCABCABCABC作业作业多重分区ABC作业ABCABC存储扩充-覆盖技术覆盖技术:作业之间或作业内部的若干程序段共享主存的技术。缺点:编程时必须划分程序模块和确定程序模块之间的覆盖关系,增加编程难度。存储扩充-覆盖技术程序大小=28K主程序(2K)A(3K)D(4K)C(1K)B(4K)E(3K)G(4K)F(4K)H(3K)主程序A(B)C(D;E;F;G)H...2k4k4k3k占用内存空间=13K存储扩充-交换技术分时系统中,同时执行几个作业(进程)。但是,这些同时存在于内存中的作业(进程),有的处于执行状态或就绪状态,而有的则处于等待状态。如果让这些等待状态中的进程继续驻留内存,必定会造成存储空间的浪费,因此应该把处于等待状态的进程换出内存,交换就是基于这种目标的一种内存扩充技术。存储扩充-交换技术RunReadyAReadyB...头…尾就绪队列磁盘内存③换入②调度①换出覆盖与交换比较1)交换不要求程序员给出程序之间的覆盖结构;覆盖需要。2)交换主要是在进程或作业之间进行;而覆盖则主要在同一个作业或进程内进行。3)覆盖只能覆盖那些与覆盖程序段无关的程序段。6.3.2页式存储管理为什么要引进分页技术?分区式存储管理:程序要求连续存放,会产生碎片问题。大程序进入时需要移动已在主存中的信息。分页式存储管理允许把一个作业存放到若干不相邻接的分区中免去移动信息充分利用主存空间分页式存储管理就是要实现从逻辑地址空间到物理地址空间的一种变换,即:f:L→S其中,L、S分别表示逻辑地址空间和实际地址空间。页架:把物理内存空间划分为若干个等份,每一份叫做一个页架。页面:把用户程序按页架划分成大小相等的部分,称为页面。从0开始编制页号,页内地址相对于0编址。基本原理地址结构用户程序的划分是由系统自动完成的,对用户是透明的。一般一页的大小为2的整数次幂。因此,地址的高位部分为页面号,低位部分为页内地址。地址结构如给定一个地址空间的地址为W,页面大小为L,则页面号P和页内地址D可按下式求得:P=INT[W/L]D=WMODL其中,INT是整除函数,MOD是取余函数。例如:系统的页面大小为1KB,设W=2230,则可求得P=2,D=182地址转换机构地址转换机构页地址映像表(页表):记录了一个作业的各个页面对应的页架。寄存器硬件成本过高,所以采用主存中开辟存储区存放页表,另设一个页表主存起址和长度控制寄存器,存放当前作业的页表起止和页表长。地址转换具体过程(页表)页表长度页表基址控制寄存器pdp’d………页号页表页号偏移量内存bb+pb页架号p’相联存储器为了提高查页表的速度,在地址变换机构中加入了一组高速寄存器(8个或者16个),这些寄存器连同管理他们的硬件构成了一个容量较小的寄存器,称之为高速相联存储器,也称快表。地址转换具体过程(快表)页表长度页表基址控制寄存器pdp’d………页号页表页号偏移量内存bb+pb页架号p’快表p’确定页面尺寸设内存为M,作业平均尺寸为J,一个页表项占一个单位,问最佳页面尺寸P=?*12()2PMMPJPFPMJP虚拟页式存储管理是将作业信息的副本存放在磁盘中,当作业被调度投入运行时,不把作业的程序和数据全部装入主存,而仅装入立即使用的页面,在执行过程中访问到不在主存的页面时,产生缺页中断,再把它们动态地装入。虚拟页式存储管理虚拟页式存储管理虚拟存储管理应解决以下问题:1、把哪一部分装入内存2、何时把页面装入3、装入内存什么位置4、当内存设备有空间时,淘汰哪个页面遵循的原则拿来策略:拿来策略就是缺哪页装哪页页面调入时机主要有两个策略:预调页策略和请求调页策略放置策略虚拟页式存储管理的页面表虚页号页面号中断位外存地址0123每个虚页号不仅对应一个页架号,还增设一个该页是否在主存的中断位和该页在外存中的副本起始地址。如果内存没有空闲页面,就应该用某种淘汰策略选中内存中的一个页面。如果被淘汰的页已经被修改了,应该把修改后的页重新写回外存,要是没有被修改,因为外存有副