张惠娟副教授Mszhj@163.ppt

1,张惠娟 副教授M,实用操作系统概念,2,内容框架,概述 体系结构 进程管理 内存管理 文件管理 外设管理,3,内容,Ch9:Memory Management Ch10:Virtual Memory,4,Ch 9:Memory Management,引言 存储管理思想 连续分配方式 常用分区算法 内存扩充技术 离散分配方式 虚拟存储器,5,引言,User programs go through several steps before being executed.第一步：编译 编译程序将用户代码编译程若干个目标模块第二步：链接 链接程序将编译后形成的一组目标模块，以及所需要的库函数链接在一起，形成完整的装入模块第三步：装入 由装入程序将装入模块装入内存,6,引言,第一步,第二步,第三步,编译程序产生的目标模块,7,引言,程序链接技术根据链接时间不同，分为静态链接 程序运行之前，将各目标模块及所需函数，链接成为一个完整的装入模块，以后不再拆开装入时动态链接一组目标模块，在装入内存时，边装入边链接运行时动态链接 程序执行中需要该目标模块时，才进行链接,8,链接解决的问题对相对地址进行修改变换外部调用符号,引言,9,10,程序装入技术 地址空间和存储空间 常用程序装入技术,引言,11,地址空间和存储空间名空间 把程序中由符号名组成的空间称为名空间逻辑地址空间存储空间 逻辑地址空间(简称地址空间)是逻辑地址的集合，物理地址空间(简称存储空间)是物理地址的集合。,引言,12,地址空间和存储空间,符号指令数据说明I/O说明,目标程序（装配模块）,名空间,地址空间,存储空间,0,1MB,0,x,13,常用程序装入技术可执行文件装入时将逻辑地址和物理内存地址对应起来的过程，称为地址再定位。地址再定位由操作系统中的装入程序来完成 常用程序装入技术绝对装入技术可重定位装入技术,引言,14,绝对装入技术也称为固定地址再定位，程序地址再定位在执行之前被确定，也就是在编译链接时直接制定程序在执行时访问的实际存储器地址。程序地址空间和内存地址空间是一一对应优点：装入过程简单缺点 过于依赖于硬件结构，不适于多道程序系统,引言,15,可重定位装入技术可执行文件中，列出各个需要重定位的地址单元和相对地址值，装入时再根据所定位的内存地址去修改每个重定位地址项，添加相应偏移量。两种地址再定位方式 静态再定位和动态再定位,引言,16,静态再定位由装入程序在程序执行之前进行地址再定位，地址定位完成后，在程序执行期间不会发生变化。优点 易实现，无需硬件支持缺点程序再定位后就不能移动，因而不能重新分配内存，不利于内存的有效利用。程序在存储空间中只能连续分配，不能分布在内存的不同区域。,引言,17,地址映射,Load A 200 3456。,1200,物理地址空间,Load A data1data1 3456,源程序,Load A 200 3456,0,100,200,编译连接,逻辑地址空间,BA=1000,18,动态再定位程序装入内存时，不修改逻辑地址，在访问物理内存之前，再实时地将逻辑地址转换成物理地址。优点程序在执行过程中可以移动，有利于内存充分利用。程序不必连续存放在内存中，可分散在内存若干个不同区域，只需增加几对基址一限长寄存器，每对寄存器对应一个区域。缺点 需要附加硬件支持，实现存储管理的软件算法比较复杂。,引言,19,0,.,.,.,.,.,.,.,0,.,.,.,.,.,.,.,VR,20,存储管理思想,存储组织 存储管理目的 存储管理任务 存储管理方案,21,存储组织存储器的功能是保存数据存储组织的功能在存储技术和CPU寻址技术许可的范围内，组织合理的存储结构，依据是访问速度匹配关系、容量要求和价格。,存储管理思想,22,存储层次结构,23,存储管理目的充分利用内存尽可能方便用户使用解决程序空间比实际内存空间大的问题存储保护与安全共享与通信实现的性能和代价,存储管理思想,24,存储管理任务存储分配和回收存储共享存储保护存储器扩充,存储管理思想,25,存储管理方案连续分配方式单一连续存储管理分区存储管理离散分配方式分页存储管理（分配单位是页）段式存储管理（分配单位是段）段页式存储管理虚拟存储器,存储管理思想,26,基本思想 单一连续存储管理 分区存储管理,连续分配方式,27,基本思想,基本思想 Main memory usually into two partitions:Resident operating system,usually held in low memory with interrupt vector.User processes then held in high memory,28,单一连续存储管理,单一连续存储管理基本思想 整个内存空间分成系统区和用户区，系统区给操作系统使用，用户区给用户使用。适用场合 最简单，适用于单用户、单任务的OS优点易于管理缺点 对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占用内存。,29,单一连续存储管理,30,基本原理 固定分区 动态分区 常用分区分配算法 分区问题 评价,分区存储管理,31,基本原理把内存分为一些大小相等或不等的分区每个应用进程占用一个或几个分区。操作系统占用其中一个分区。特点：适用于多道程序系统和分时系统支持多个程序并发执行难以进行内存分区的共享。问题：可能存在内碎片和外碎片。,分区存储管理,32,数据结构 分区表，或分区链表可以只记录空闲分区，也可以同时记录空闲和占用分区分区表中，表项数目随着内存的分配和释放而动态改变，可以规定最大表项数目。分区表可以划分为两个表格：空闲分区表，占用分区表。空闲分区表中按不同分配算法相应对表项排序。,分区存储管理,33,固定分区基本思想 内存划分为若干个固定大小的连续分区分区大小相等 适合于多个相同程序的并发执行（处理多个类型相同的对象）。分区大小不等 多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。,分区存储管理,34,固定分区(大小相同),固定分区(多种大小),35,分区4分区3分区2分区1操作系统,多个等待队列,单个等待队列,分区4分区3分区2分区1操作系统,36,优点比单一连续分配方法，内存利用率提高了可以支持多道程序实现简单缺点作业必须预先能够估计自己要占用多大的内存空间内碎片造成浪费分区总数固定，限制了并发执行的程序数目。,分区存储管理,37,动态分区 动态创建分区 在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小。优点 没有内碎片缺点 有外碎片,分区存储管理,38,39,40,41,分区分配算法 寻找某个空闲分区，其大小需大于或等于程序的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为“占用”，而另一个分区为余下部分并标记为“空闲”。分区的先后次序通常是从内存低端到高端。分区释放算法 需要将相邻的空闲分区合并成一个空闲分区。(解决的问题是：合并条件的判断和合并时机的选择),分区存储管理,42,评价优点实现了主存共享，有助于多道程序设计可变式分区主存利用率比固定分区高些相对于后面介绍的存储管理方式，本方案为实现分区分配所使用的表格，占用存储容量相对较少，算法也相对简单。实现存储保护的措施也比较简单。多重分区分配方案能实现对子程序、数据段的共享。,分区存储管理,43,缺点主存仍不能充分利用，除了采用紧凑技术外，都存在着严重碎片。不能实现对主存扩充和单一连续分配一样，要求一个作业执行前必须全部装入主存。,分区存储管理,44,常用分区分配算法,最先适配算法 循环最先适配算法 最佳适配算法 最坏适配算法 分区算法存在的问题,45,最先适配算法算法思想 按分区先后次序，从头查找，找到符合要求的第一个分区。算法实质 尽可能利用存储区低地址空闲区，尽量在高地址部分保存较大空闲区，以便一旦有分配大空闲区要求时，容易得到满足。,常用分区分配算法,46,算法优点 分配简单，合并相邻空闲区也比较容易算法缺点 查找总是从表首开始，前面空闲区往往被分割的很小时，满足分配要求的可能性较小，查找次数较多。解决方法 针对这个问题，对最先适应法稍加改进，就有了循环最先适应法。,常用分区分配算法,47,循环最先适应法。算法思想 按分区先后次序，从上次分配的分区起查找（到最后分区时再回到开头），找到符合要求的第一个分区算法特点 算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大的空闲分区不易保留。,常用分区分配算法,48,最佳适配算法算法思想 在所有大于或者等于要求分配长度的空闲区中挑选一个最小的分区，即对该分区所要求分配的大小来说，是最合适的。分配后，所剩余的块会最小。算法实现 空闲存储区管理表采用从小到大的顺序结构,常用分区分配算法,49,优点 较大的空闲分区可以被保留缺点 空闲区是按大小而不是按地址顺序排列的，因此释放时，要在整个链表上搜索地址相邻的空闲区，合并后，又要插入到合适的位置。,常用分区分配算法,50,最坏适配算法算法思想 分区时取所有空闲区中最大的一块，把剩余的块再变成一个新的小一点的空闲区。算法实现 空闲区按由大到小排序,常用分区分配算法,51,优点 分配时，只需查找一次，就可成功，分配算法很快。缺点 最后剩余分区会越来越小，无法运行大程序,常用分区分配算法,52,0K,15K,38K,48K,68K,80K,110K,120K,空闲区表,已分配区表,最坏适配算法举例,53,0K,15K,38K,48K,68K,80K,110K,120K,空闲区表,已分配区表,85K,98K,54,分区算法中存在的问题碎片问题分区保护,常用分区分配算法,55,碎片问题 经过一段时间分配、回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求；但其总和满足分配要求。这些空闲块被称为碎片，碎片造成存储资源浪费（外碎片）解决方法：紧凑技术 通过在内存移动程序，将所有小的空闲区域合并为大的空闲区域系统开销大 从而，引出了离散分配方式,常用分区分配算法,56,57,分区保护问题界限寄存器定位寄存器和界限寄存器 访问内存时，先利用定位寄存器将有效地址转换为物理地址，再将物理地址和界限寄存器比较上下限寄存器保护键,常用分区分配算法,58,问题提出 内存扩充 扩充技术覆盖技术交换技术 两种技术比较,内存扩充,59,内存扩充,问题提出一个作业的程序地址空间大于内存可使用空间时，该作业就不能装入运行；当并发运行作业的程序地址空间总和大于内存可用空间时，多道程序设计实现就会碰到非常大的困难。内存扩充 借助大容量辅存在逻辑上实现内存扩充，来 解决内存容量不足的问题,60,覆盖技术引入目的 在较小可用内存中运行较大的程序。常用于多道程序系统，与分区存储管理配合使用。,内存扩充,61,基本原理 一个程序的几个代码段或数据段，按照时间先后来占用公共的内存空间。将程序的必要部分代码和数据常驻内存；可选部分在其他程序模块中实现，平时存放在外存中（覆盖文件），需要用到时才装入到内存；不存在调用关系的模块不必同时装入到内存，可相互覆盖。,内存扩充,62,注：另一种覆盖方法：(100K)A(20K)占一个分区：20K；B(50K)、D(20K)和E(40K)共用一个分区：50K；F(30K)和C(30K)共用一个分区：30K；,63,缺点：编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度。从外存装入覆盖文件，以时间延长来换取空间节省。实现 函数库（操作系统对覆盖不得知），或操作系统支持,内存扩充,64,交换技术原理 把内存中暂时不能运行或暂不能用的程序和数据，调出到外存上，以便腾出足够内存空间给其它进程或程序使用。,内存扩充,65,Schematic View of Swapping,66,引入目的整体交换 也称为进程交换，交换是以整个进程为单位，目的是解决内存紧张问题，进一步提高内存利用率部分交换 也称为页面交换、分段交换，是分页、分段交换的基础，目的是为了支持虚拟存储系统,内存扩充,67,优点 增加并发运行的程序数目，并给用户提供适当的响应时间；编写程序时不影响程序结构缺点 换入和换出的控制增加处理机开销 程序整个地址空间都进行传送,内存扩充,68,覆盖技术主要用在早期的操作系统中 交换技术被广泛用于小型分时系统中，交换技术的发展导致了虚存技术的出现交换技术不要求用户给出程序段之间的逻辑覆盖结构；交换发生在进程或作业之间，覆盖发生在同一进程或作业内；覆盖只能覆盖那些与覆盖段无关的程序段存。,内存扩充,69,离散分配方式,页式存储管理 段式(Segment)存储管理 比较 段页式管理,70,页式存储管理,基本原理 存储管理 硬件支持 两级页表 共享 评价,71,基本原理用户空间划分 把用户程序按逻辑页划分成大小相等的部分，称为页（虚页）。从0开始编制页号，页内地址是相对于0编址。用户空间划分是由系统自动完成的，对用户是透明的。一般，页大小为2的整数次幂，因此，地址的高位部分为页号，低位部分为页内地址,页式存储管理,72,31,73,内存空间划分 按页的大小划分为大小相等的区域，称为 内存块（物理页面，页框、实页）内存分配 以页为单位进行分配，并按作业的页数多 少来分配。逻辑上相邻的页，物理上不一 定相邻。,页式存储管理,74,75,76,页式存储管理,存储管理进程页表 系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系，页表放在内存，属于进程的现场信息。,77,进程页表,78,物理页面表 整个系统有一个物理页面表，描述物理内存空间的分配使用状况。数据结构：位示图，空闲页面链表请求表 整个系统有一个请求表，描述系统内各个进程页表位置和大小，用于地址转换，也可结合到各进程PCB里；,页式存储管理,79,0,31,0/1,0/1,0/1,0/1,0/1,0,1,7,空闲块数,空块管理位示图,80,管理过程计算一个作业所需要的总块数N查位示图，看看是否还有N个空闲块如果有足够的空闲块，则页表长度设为N，可填入PCB中；申请页表区，把页表始址填入PCB依次分配N个空闲块，将块号和页号填入页表修改位示图,页式存储管理,81,硬件支持系统设置一对寄存器：页表始址寄存器 页表长度寄存器联想寄存器器快表 为缩短查找时间，可以将页表从内存装入到关联存储器(TLB)，按内容查找，即逻辑页号物理页号,页式存储管理,82,地址映射过程,83,地址映射举例,84,两级页表,页式存储管理,85,共享页面,页式存储管理,86,评价优点 解决了碎片问题 便于管理缺点 不易实现程序共享 不便于动态连接,页式存储管理,87,段式存储管理,引入目的 基本原理 存储管理 硬件支持 评价,88,段式存储管理,引入目的 主要是为了满足用户再变成和使用上的多方面要求。方便编程信息共享信息保护动态增长动态链接,89,Logical View of Segmentation,1,3,2,4,user space,physical memory space,90,操作系统,91,段式存储管理,基本原理用户空间划分 按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的。,92,内存空间划分 内存空间被动态的划分为若干个长度不相同的区域，这些区域被称为物理段，每个物理段由起始地址和长度确定。内存分配 以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），各段之间可以不连续存放,段式存储管理,93,存储管理进程段表 记录了段号，段的首（地）址和长度之间的关系。每一个程序设置一个段表，放在内存，属于进程的现场信息,段式存储管理,94,系统段表 系统内所有占用段空闲段表 记录空闲段起始地址和长度，可以结合到系统段表中内存分配算法 首先适配；最佳适配；最坏适配,段式存储管理,95,96,硬件支持系统设置一对寄存器 段表始址寄存器 保存正在运行进程的段表始址段表长度寄存器 用于保存正在运行进程的段表长度联想存储器 保存正在运行进程的段表的子集，快表项目：段号；段始址；段长度；标识（状态）位；访问位（淘汰位）,段式存储管理,97,评价优点 便于动态申请内存 管理和使用统一化 便于共享 便于动态链接缺点 产生碎片,段式存储管理,98,比较,分页是出于系统管理需要，分段是出于用户 应用需要。页大小是系统固定的，而段大小则通常不固定 逻辑地址表示：分页是一维的，各个模块在链接时必须组织成同一个地址空间 分段是二维的，各个模块在链接时可以每个段组织成一个地址空间 通常段比页大，因而段表比页表短，可以缩短 查找时间，提高访问速度。,99,段式页式存储管理,产生背景 基本思想 存储管理 硬件支持 举例,100,产生背景 结合了二者优点 克服了二者的缺点,段式页式存储管理,101,基本思想用户程序按段式划分内存页式存储管理方案内存分配 以页为单位进行分配,段式页式存储管理,102,存储管理段表 记录每一段的页表始址和页表长度页表 记录了逻辑页号与内存块号的对应关系（每一 段有一个，一个程序可能有多个页表）空块管理同页式管理分配同页式管理,段式页式存储管理,103,硬件支持 段表始址寄存器 段表长度寄存器 相联存储器（快表）,段式页式存储管理,104,MULTICS Address Translation Scheme,105,Segmentation with Paging Intel 386,106,小结,理解存储管理思想 连续存储方式缺点 常用分区算法 分页管理机制 分段管理机制,107,练习,阅读讲义 阅读p255-p291 P295 9.19.3、9.5、9.6、9.79.10、9.13、9.16、9.17,