《计算机操作系统7要点课件.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统7要点课件.ppt（83页珍藏版）》请在三一办公上搜索。
1、第四章存储管理,概述 分区存储管理 段式存储管理 页式存储管理 段页式存储管理 交换技术与覆盖技术 虚拟存储,存储器是计算机系统的重要管理资源。因为任何程序和数据以及各种控制用的数据结构都必须占用一定的存储空间，故存储管理直接影响着系统的性能。操作系统的任务之一是要尽可能地方便用户使用存储器，以及提高主存储器的利用率。,4.1 概 述,一、存储管理机构要解决的问题,存储分配问题。重点是研究存储共享和各种分配算法。地址再定位问题。研究各种地址变换机构，以及静态和动态再定位方法。存储共享问题。研究多个进程如何共享内存。存储保护问题。研究保护各类程序、数据区的方法。存储扩充问题。主要研究虚拟存储器问
2、题及其各种调度算法。,二、存储组织和层次结构,操作系统协调各存储器的使用,高速缓存Cache：少量的、非常快速、昂贵、易变的内存RAM：若干兆字节、中等速度、中等价格、易变的 磁盘：数百兆或数千兆字节、低速、价廉、不易变的,速度与CPU取指速度相匹配,内存：是由存储单元（字节或字）组成的一维连续的地址空间，简称内存空间。用来存放当前正在运行程序的代码及数据，是程序中指令本身地址所指的、亦即程序计数器所指的存储器。,内存可以分为：系统区：用于存放操作系统用户区：用于装入并存放用户程序和数据。,三、存储管理的功能,存储分配和回收：分配和回收算法及相应数据结构。存储共享和保护：代码和数据共享，地址空
3、间访问权限（读、写、执行）地址变换（地址再定位、地址映射）：可执行文件生成中的链接技术程序加载(装入)时的重定位技术进程运行时硬件和软件的地址变换技术和机构存储器扩充：存储器的逻辑组织和物理组织；由应用程序控制：覆盖；由OS控制：交换（整个进程空间），虚拟存储的请求调入和预调入（部分进程空间）,内存空间的管理、分配与回收,（1）内存空间的管理、分配与回收 记录内存的使用情况 设置相应的内存分配表（内存分配回收的依据）内存空间划分问题？静态或动态，等长或不等长,内存分配表位示图：用一位（bit）表示一个空闲页面（0：空闲，1：占用）空闲页面表：包括首页面号和页面个数，连续若干的页面作为一组登记在
4、表中空闲块表：空闲块首址和空闲块长度，没有记录的区域即为进程所占用空闲块链表：将所有的空闲块链成一个链表,第0页第1页 第i页 第n-1页,分配与回收,确定分配算法 实施内存分配 回收内存 内存存储分配和回收的三种方式：直接指定方式、静态和动态分配方式,连续性 离散性驻留性 交换性一次性 多次性,2.存储共享与保护,内存共享：两个或多个进程共用内存中相同区域目的：节省内存空间，提高内存利用率实现进程通信（数据共享）共享内容：代码共享，要求代码为纯代码 数据共享,存储保护,保护目的：为多个程序共享内存提供保障，使在内存中的各道程序，只能访问它自己的区域，避免各道程序间相互干扰，特别是当一道程序发
5、生错误时，不致于影响其他程序的运行。通常由硬件完成保护功能，由软件辅助实现。,存储空间一般分为两个部分系统区用户区保护系统程序区不被用户侵犯（有意或无意的）不允许用户程序读写不属于自己地址空间的数据（系统区地址空间，其他用户程序的地址空间）,保护过程-防止地址越界,每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。即当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理。,一般由硬件提供一对寄存器：基址寄存器：存放起始地址 限长寄存器：存放长度（或 上界寄存器/下界寄存器）,基址=被访问地址=
6、基址+界限,3200=被访问地址=4200,保护过程-防止操作越权,对于允许多个进程共享的存储区域，每个进程都有自己的访问权限。如果一个进程对共享区域的访问违反了权限规定，则发生操作越权，即读写保护。,共享存储区域的保护,3.地址变换(地址再定位,地址映射),直接指定方式:程序员在编程序时或编译程序对源程序进行编译时，所用的是实际存储地址。名空间程序逻辑空间逻辑地址（相对地址，虚地址）存储空间物理地址（绝对地址，实地址）地址映射,程序的名空间、地址空间及存储空间,逻辑地址、物理地址和地址映射,逻辑地址（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。
7、其首地址为0，其余指令中的地址都相对于首地址来编址。不能用逻辑地址在内存中读取信息。物理地址（绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址。地址映射：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。当程序装入内存时,操作系统要为该程序分配一个合适的内存空间，由于程序的逻辑地址与分配到内存物理地址不一致,而CPU执行指令时，是按物理地址进行的，所以要进行地址转换。,地址映射,编译连接,静态分配和静态再定位,程序中列出各个需要重定位的地址单元和相对地址值。当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成）。即：装入时根
8、据所定位的内存地址去修改每个重定位地址项，添加相应偏移量。,优点：不需硬件支持，可以装入有限多道程序。缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。不易实现共享。,地址再定位（地址转换）,0000,动态分配和动态再定位,在程序执行过程中，占用的存储空间大小与位置均是可变的。程序中虚拟内存地址，装入和执行时通过硬件地址变换机构，完成虚拟地址到实际内存地址的变换。,优点：OS可以将一个程序分散存放于不连续的内存空间，可以移动程序，有利用实现共享。能够支持程序执行中产生的地址引用，如指针变量（而不仅是生成可执行文件时的地址引用）。缺点：需要硬件支持（通常是CPU），OS实现较复杂
9、。它是虚拟存储的基础。,+,虚拟存储器的基本思想是把作业地址空间和实际主存的存储空间，视为两个不同的概念。一个计算机系统采用一定技术为程序员提供了一个足够大的地址空间，而完全不必考虑实际主存的大小。根据地址空间结构不同，虚拟存储器有两种形式。单段式虚存多段式虚存,4.虚拟存储器概念的引入,虚拟存储的基本原理,在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页或段调入到内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的页或段调
10、出保存在外存上，从而腾出空间存放将要装入的程序以及将要调入的页或段。只需程序的一部分在内存就可执行。,4.2 早期存储管理,单一连续分配分区分配覆盖和交换,单用户系统在一段时间内，只有一个进程在内存内存分为两个区域，一个供操作系统使用，一个供用户使用。应用程序装入到用户区，可使用用户区全部空间。优点：内存分配管理十分简单，适用于单用户、单任务的OS内存利用率低。对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占用内存。,一、单一连续存储管理,连续存储管理实例,用户独占内存,用户作业队列,界限地址,栅栏寄存器,用户A作业,用户B作业,用户C作业,二、分区存储管理,系统把内
11、存用户区划分为若干分区，分区大小可以相等，也可以不等。每个进程占据一个分区。,固定分区可变分区再定位分区多重分区,分区方式,1.原理,把内存分为一些大小相等或不等的分区(partition)，每个应用进程占用一个或几个分区。操作系统占用其中一个分区。,特点：适用于多道程序系统和分时系统支持多个程序并发执行难以进行内存分区的共享,问题：可能存在内碎片和外碎片。内碎片：占用分区之内未被利用的空间。外碎片：占用分区之间难以利用的空闲分区。,分区的数据结构：分区表，或分区链表可以只记录空闲分区，也可以同时记录空闲和占用分区分区表中，表项数目随着内存的分配和释放而动态改变，可以规定最大表项数目。分区表可
12、以划分为两个表格：空闲分区表，占用分区表。空闲分区表中按不同分配算法相应对表项排序。,内存紧缩(compaction)：将各个占用分区向内存一端移动。使各个空闲分区聚集在另一端，然后将各个空闲分区合并成为一个空闲分区。,对占用分区进行内存数据搬移占用CPU时间如果对占用分区中的程序进行浮动，则其重定位需要硬件支持。紧缩时机：每个分区释放后，或内存分配找不到满足条件的空闲分区时,2.固定分区(fixed partitioning),预先把可分配的主存储器空间分割成若干个连续区域，称为一个分区。每个分区的大小可以相同也可以不同，但分区大小固定不变，每个分区装一个且只能装一个作业。存储分配：如果有一
13、个空闲区,则分配给进程。,分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。,固定分区(大小相同),固定分区(多种大小),固定分区内存分配管理,通过设置内存分配表，内存分配简单,固定式分区举例,此时如果有5个作业，其容量分别为1K，9k，9K，33K，121K，可按下表分配给各区。,固定分区的进程队列,由于固定分区的大小一经定义无法改变，所以一个程序到达时，尽可能把它放入能容纳它的最小分区内。,固定分区存储管理的地址转换,优点：易于实现，开销小。缺点：内碎片造成浪费分区
14、总数固定，限制了并发执行的程序数目。可引入覆盖和交换技术。,覆盖(overlay),引入：其目标是在较小的可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。原理：一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。将程序必要部分（常用功能）的代码和数据常驻内存；可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要时才装入到内存；不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。(即不同时用的模块可共用一个分区),覆盖技术,缺点：编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度。从外存装入覆盖文件，以时间延长来
15、换取空间节省。,交换(swapping),引入：多个程序并发执行，可以将暂时不能执行的程序送到外存中，从而获得空闲内存空间来装入新程序，或读入保存在外存中而目前到达就绪状态的进程。交换单位为整个进程的地址空间。原理：暂停执行内存中的进程，将整个进程的地址空间保存到外存的交换区中，而将外存中由阻塞变为就绪的进程的地址空间读入到内存中，并将该进程送到就绪队列。,优点：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写程序时不影响程序结构；缺点：对换入和换出的控制增加处理机开销；程序整个地址空间都进行传送，没有考虑执行过程中地址访问的统计特性。与覆盖技术相比，交换技术不要求用户给出程序段之间
16、的逻辑覆盖结构；而且，交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。此外，覆盖只能覆盖那些与覆盖段无关的程序段。,3.可变分区分配,基本思想：内存不是预先划分好的。在装入程序时按其初始要求分配。当作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待主存空间。或在其执行中通过系统调用进行分配或改变分区大小。,内存管理：设置内存空闲块表记录了空闲区起始地址和长度内存分配：动态分配内存回收：当某一块归还后，前后空间合并，修改内存空闲块表,可变式分区举例,可变分区的分配,空闲分区状态表,已分配分区表,系统使用分区说明表对内
17、存管理可用空闲区分区表已分配分区状态表,申请分配一个,x,KB,大小的分区,置空白区号,f,=1,f,大于最后,一个空白区号？,空白区可用？,保存空白区的起始地址,空白区,f,的大小,x,KB,空白区的,状态=空项,修改空白区的大小,和起始地址,在已分配表中找一个状,态=空项的分区号,P,置分区P的大小为,x,KB,置分区起始地址,置分区状态为已分配,返回一个,分区号,此次无法分配,f+1 f,Y,Y,N,N,=,请求一个分区的流程,释放一个分区的流程,分区分配算法,分区分配算法：寻找某个空闲分区，其大小需大于或等于程序的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区为要求的大小并
18、标记为“占用”，而另一个分区为余下部分并标记为“空闲”。分区的先后次序通常是从内存低端到高端。分区释放算法：需要将相邻的空闲分区合并成一个空闲分区。(这时要解决的问题是：合并条件的判断和合并时机的选择),分配算法,按空闲块链接的方式不同，可以有以下四种算法：首次适应法下次适应法（循环首次适应法）最佳适应法最坏适应法,I首次适应算法(First Fit:FF),将自由区按存贮顺序链成一个队列，用一指针指向队首，分配时将找到的第一个满足要求的空白区分配给它。,首次适应算法实例：,要求：有四块自由区域，为一程序分配19k内存。,FF特点：简单，查找次数少，在高地址区中保持较大自由区域。,II循环首次
19、适应(Next fit:NF),将自由区组成环状队列，按循环顺序寻找自由区。(与FF区别，头指针从低地址开始向高地址循环移动),NF特点：使得小的自由区均匀分布，易于与其它自由区合并。,III最佳适应算法(Best fit:BF),将自由区按大小排成队列，寻找时总是以最小的自由区开始，找到第一个合适的分区。,BF特点：最佳地利用分区，查找效率低，碎片多而小。,最佳适应算法实例,要求：有四块自由区，为一程序分配19k内存。,IV最坏适应算法(Worst fit:WF),将自由区排序(按从大到小)，并寻找最大自由区域进行分配。,实例：,BF特点：不会出现小的自由区。,算法比较实验,实例：设系统自由
20、区链表为,要求：用户先后申请7.5k，4k内存空间，试用四种算法求出分配块。,WF:e,e,再排序从小到大,分配块为d,f,可再定位式分区分配的靠拢过程,4.可再定位式分区分配,利用浮动寄存器进行地址变换,地址变换,可再定位式分区分配算法流程,分区分配,可重定位分区的优缺点,优点:解决了可变分区分配所引入的“外部碎片”问题。消除内存碎片，提高内存利用率。缺点:提高硬件成本，紧凑时花费CPU时间。,5.多重分区,以上讨论都是基于一个作业在主存中占据的是一个连续分区的假定。为了支持结构化程序设计，操作系统往往把一道作业分成若干片段如子程序、主程序、数据组等）。这样，片段之间就不需要连续了。只要增加
21、一些重定位寄存器，就可以有效地控制一道作业片段之间的调用。这种给一个作业分配一个以上分区的方法，称为多重分区分配。采用这种方法时，作业可以在其执行期间申请附加的分区。,多重分区分配,如图所示，作业、分别被分成两个片段放进互不相连的存储区域中。由两个变址寄存器实现控制。,主要优点：(1)实现了主存的共享，因而有助于多道程序设计，更有效地利用了处理机和I/O设备，从而使系统的吞吐量和作业周转时间得到了相应的改善。至于主存利用率，可变式分区比固定式分区高些，可再定位式分区则更高些。(2)相对于后面介绍的存储管理方式，本方案为实现分区分配所使用的表格、占用的存储容量相对较少，算法也相对简单。(3)实现
22、存储保护的措施也比较简单。(4)多重分区分配方案能实现对子程序、数据段的共享。,分区分配方案的评价,(1)主存仍不能充分利用，除了可再定位式分区法外，都存在着严重的碎片问题。另外，即使不把存储器分碎，整个空白区也可能因容纳不下一个作业而造成浪费。(2)不能实现对主存的扩充。因此，作业的大小受到主存可用空间的限制。(3)和单一连续分配一样，要求一个作业在执行之前必须全部装入主存，因此在主存中可能包含从未使用过的信息。(4)采用靠拢方法，虽然能解决碎片问题，但有时需移动大量信息，从而损失了处理机时间。(5)除多重分区外，几个共行作业之间不能共享存入主存的单一信息副本(如公用子程序、数据段等)。,主
23、要缺点：,一、基本原理,把用户程序按逻辑页划分成大小相等的部分，称为页。从0开始编制页号，页内地址是相对于0编址。,4.3 分页存储管理,逻辑地址,逻辑地址,用户程序的划分是由系统自动完成的，对用户是透明的。一般，一页的大小为2的整数次幂，因此，地址的高位部分为页号，低位部分为页内地址。,0,11,12,23,页号P,页内位移量W,编号04096,相对地址04096,内存空间,内存块：按页的大小划分为大小相等的区域，称为内存块（又叫物理页面，页框）。内存分配：以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻，通过页表把作业的各个页面与页框对应起来。,.,.,.,.
24、,.,.,页面变换表,列出了作业的逻辑地址与其在主存中的物理地址间的对应关系。页面大小:页面的大小应选择得适中，且页面大小应是2的幂一个页表中包含若干个表目，自然序号对应于用户程序中的页号，块号是该页对应的物理块号。页面变换表的每一个表目除了包含指向页框的指针外，还包括一个存取控制字段。,二、地址变换机构,分页地址中的地址结构如下：,31,12,11,0,对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按右式求得：,使用位图表管理内存,固定内存空间中，页面的大小决定了位图的大小，单位页面越大，位图越小。,建立一张由若干个字节构成 的内
25、存位图表，每个二进制位对应内存的一个页面，0表示空闲，1表示占用。,使用链表的内存管理,空闲页面链,计算一个作业所需要的总块数N查位示图，看看是否还有N个空闲块如果有足够的空闲块，则页表长度设为N，可填入PCB中；申请页表区，把页表始址填入PCB依次分配N个空闲块，将块号和页号填入页表修改位示图,内存的分配与回收,如果把页表放在主存中，无疑会影响系统的性能。这是因为每次访问主存，首先必须访问页表，读出表目，之后根据形成的实际地址再访问主存，这样使访问主存的次数加倍，因而使总的处理速度明显下降。为了解决这个问题人们采用一组硬件寄存器，存放当前访问过的页的表目，每次访问主存时，首先查找快表，若找到
26、所需的表目，则快速形成物理地址。否则从页表中查找后形成物理地址，同时把页描述子写入快表。如果设计得当，快表的命中率可以很高。,快表,硬件支持,系统设置一对寄存器 页表始址寄存器 用于保存正在运行进程的页表的始址 页表长度寄存器 用于保存正在运行进程的页表的长度相联存储器快表 相联（联想）存储器（associative memory）TLB（Translation lookaside buffers）,相联存储器快表 用途：保存正在运行进程的页表的子集（部分表项）特点：按内容并行查找快表表项：页号；内存块号；标识位；淘汰位,利用快表加速查询,地址映射机制,(1)采用动态地址变换会增加计算机成本和降低处理机的速度。(2)各种表格要占用一定容量的主存空间，而且要花费一部分处理机时间用来建立和管理这些表格。(3)虽然说碎片消除了，但每个作业的最后一页一般都有不能充分利用的空白区。(4)存储扩充问题仍未得到解决。,分页存储管理方案的评价,
