多道程序设计与内存管理组织

《多道程序设计与内存管理组织》由会员分享，可在线阅读，更多相关《多道程序设计与内存管理组织（17页珍藏版）》请在装配图网上搜索。

1、帯诸管理存储管理一一大纲重要概念存储体系.存储保护.地址直定位物理内存管理敷据结构（位示图.空闲区丧空闲区链農）分配算虚（It先适配.最佳适配.最差拓配）各种存储管理方案单一连续区.固定分区.可变分区.页式.段式、 段页式虐拟存储管理硬件.页表.页错误处理软件策略：读取策略.放It策略、换策略.驻留 集策路.清除策略.装载控制策略重点小结基本概念。存储体系。交换与覆盖技术。逻辑地址.物理地址、地址重定位。地址保护物理内存管理。位示图、空闲区表/已分配区表、空闲块链表、伙伴系统。分配与回收算法。碎片问题（内碎片、外碎片）各种存储管理方案。单一连续区、固定分区、可变分区、分页-分段、段页式。相关数

2、据结构。地址转换过程多道程序设计与内存管理是在计算机内存中同时存放几道相互独立的程序，使它们在管理程序控制之下，相 互穿插的运行。两个或两个以上程序在计算机系统中同处于开始到结束之间的状 态。这就称为多道程序设计。多道程序技术运行的特征：多道、宏观上并行、微观 上串行。需要内存管理做更多的工作需要支持地址重定位O程序中的地址不一定是最终的物理地址O在程序运行前无法计算出物理地址O因为不能确定程序被加载到内存什么地方需要支持地址保护O进程间地址空间不能互访问地址重定位地址重定位：将用户程序中的逻辑地址转换为运行时可由机器直接寻址的物理地址的过程目的:保证CPU执行指令时可正确访问内存单元逻辑地址

3、（相对Wit,虚拟地址）用户程序经过编译、汇编后形成目标代码，目标代码通常采用相对地址的形式,其首地 址为o,其余指令中的地址都相对于首地址而编址不能用逻辑地址在内存中读取信息物理地址（绝对地址,实地址）内存中存储单元的地址，可直接寻址静态地址映射（静态重定位）:当用户程序被装入内存时，一次性实现逻辑地址到物理地址 的转换,以后不再转换。（软件完成）动态地址映射（动态重定位）:在程序执行过程中要访问数据时再进行地址映射,即逐条指 令执行时完成地址映射。（硬件地址映射机制）基址寄存器（BR）,在程序装入后，将其内存空间的起始地址B送入BR ,旦遇到要访 问地址的指令时，硬件便自动将其中的访问地址

4、加上BR的内容形成世纪物理地址，然 后按该地址执行。存储共享、存储保护（防止地址越界、防止操作越权）答：存储共享是指两个或多个进程共用内存中相同区域，这样不仅能使多道程序动态地共享 内存，提高内存利用率，而且还能共享内存中某个区域的信息。包括:代码共享和数据共氧代码共享的代码必须是纯代码！目的：1通过代码共享节省内存空间2通过数据共享实现进程通信存储保护为多个程序共享内存提供保障，使在内存中的各 道程序，只能访问它自己的区域，避免各道程序间相互干扰。特别是当一道程序发生错 误时，不至于影响其他程序的运行，更要防止破坏系统程序。主要是硬件支持,软件配 合实现的。存储保护内容：1防止地址越界2防止

5、操作越权（对属于自己区域的信息，可读或写;对公共区域中允许共享的信息或获得授权可以使用的 信息，可读而不可修改;对未授权使用的信息，不可读,不可写） 般由硬件提供一对寄存器: 基址寄存器:存放起始地址 界限寄存器:存放长度或者是一对上界寄存器和下界寄存器存储管理的基本目标给进程分配内 一地址空间往内存加载内容映射进程地址空间到物理内存管理共享的内存最小化存储访问时间内存由存储单元（字节或字）组成的一维连续的地址空间，简称内存空间。用来存放当前正在运 行程序的代码及数据,是程序中指令本身地址所指的、亦即程序计数器所指的存储器系统区:用于存放操作系统用户区:用于装入并存放用户程序和数据存储管理的任

6、务内存空间的管理、分配与回收记住每个存储区域的状态（需要设置相应的非配表格，记录内存空间使用状态）实施分配（分为静态非配和动态分配两种）回收为实现上述功能，必须引入分配表，统称为系统分配表，组织方式有：位示图表示法:用一位（bit）表示一个内存页面（0表示空闲，1表示占用）空闲页面表:包括首页面号和空闲页面个数，连续若干的页面作为一组登记在表中;空闲块链表:将所有空闲块链成一个链表空闲区表、已分配区表:空闲块首址和空闲块长度，没有记录的区域即为进程所占 用静态分配:程序要求的内存空间是在目标模块连接装入内存是确定并分配的，并且在程序 运行过程中不允许再申请或在内存中搬家，即分配工作是在程序运行

7、前一次性完 成。动态分配:程序要求的基本内存空间实在目标模块装入时确定并分配的，但是程序运行过 程中允许申请附加的内存空间或在内存中搬家，即分配工作可以在程序运行前及程 序运行中逐步完成。动态分配的好处:具有较大的灵活性;暂不使用的信息可以不进内存，对提高内存利用率大 有好处;反映了程序的动态性，较之静态存储分配更为合理。内存共享内存共享是指两个或多个进程共用内存中相同区域，这样不仅能使多道程序动态地共享 内存，提高内存利用率，而且还能共享内存中某个区域的信息。包括:代码共享和数据共享。代码共享的代码必须是纯代码！目的：1通过代码共享节省内存空间2通过数据共享实现进程通信（3）存储保护存储保护

8、目的：为多个程序共享内存提供保障，使在内存中的各道程序，只能访问它自己的区域， 避免各道程序间相互干扰。特别是当一道程序发生错误时，不至于影响其他程序的运行, 更要防止破坏系统程序。主要是硬件支持,软件配合实现的。存储保护内容：1防止地址越界2防止操作越权（对属于自己区域的信息，可读或写;对公共区域中允许共享的信息 或获得授权可以使用的信息，可读而不可修改;对未授权使用的信息，不可读，不 可写）（4）扩充内存容量（内存扩充）在硬件支持下，软件、议案相互协作,将内存和外存结合起来统一使用。（5）地址映射（地址转换）逻辑地址（相对地址,虚地址）：用户的程序经过汇编或编译后形成目标代码,目标代码通常

9、采用相对地址的形式,其首地 址为0,其余指令中的地址都相对于首地址而编址，这就是逻辑地址的概念。物理地址（绝对地址，实地址）：内存中存储单元的地址，可直接寻址地址映射（地址转换，重定位）:为了保证CPU执行指令时可以正确访问存储单元,需将用 户程序中的逻辑地址转换为运行时可由机器直接寻址的物理地址,这一过程称为地址映 射。般由硬件提供一对寄存器：基址寄存器存放起始地址界限寄存器:存放长度或者是一对上界寄存器和下界寄存器静态地址映射（静态重定位）：当用户程序被装入内存是,次性实现逻辑地址到物理地址的转换，以后不再转换。（软 件完成）动态地址映射（动态重定位）：在程序执行过程中要访问数据时再进行地

10、址映射，即逐条指令执行时完成地址映射。（硬 件地址映射机制）基址寄存器（BR）,在程序装入后，将其内存空间的起始地址B送入BR ,旦遇到要访 问地址的指令时，硬件便自动将其中的访问地址加上BR的内容形成世纪物理地址，然 后按该地址执行。物理內存管理方案空闲内存管理数据结构位图每个分配单元对应于位图中的一位,0表示空闲,1表示占用（或者相反） 空闲区表、已分配区表表中每一项记录了空闲区（或已分配区）的起始地址、长 度、标志空闲块链表内存分配算法首次适配firstfit。在空闲区表中找到第一个满足进程要求的空闲区下次适配next fit。从上次找到的空闲区处接着查找最佳适配best fit 查找整

11、个空闲区表,找到能够满足进程要求的最小空闲区最差适配worst fit。总是分配满足进程要求的最大空闲区将该空闲区分为两部分，一部分供进程使用，另部分形成新的空闲区回收问题内存回收算法。当某一块归还后，前后空闲空间合并，修改内存空闲区表。四种情况上相邻、下相邻、上下都相邻、上下都不相邻伙伴系统Linux低层内存管理采用种特殊的“分离适配算法种经典的内存分配方案主要思想:将内存按2的專进行划分，组成若干空闲块链表;查找该链表 找到能满足进程需求的最佳匹配块算法：。首先将整个可用空间看作一块:2U。假设进程申请的空间大小 为s ,如果满足2U-ls=2Uz则分配整个块否则，将块划分为两个大小相等的

12、伙 伴，大小为2U-1。一直划分下去直到产生大于或等于s的最小块。基本内存管理方案单一连续区，固定分区，可变分区，分页，分段，段页式单一连续区每次只运行一个用户程序，用户程序独占内存，它总是被加栽 到同一个内存地址上固定分区把可分配的内存空间分割成若干个连续区域，每一区域称为分 区。每个分区的大小可以相同也可以不同，分区大小固定不变， 每个分区装一个且只能装一个进程可变分区根据进程的需求，把可分配的内存空间分割出一个分区，分配 给该进程页式把用户程序地址空间划分成大小相等的部分，称为页。内存空 间按页的大小划分为大小相竽的区域，称为内存块（物理页面， 页框，页帧）。以页为单位进行分配，逻辑上相

13、邻的页，物理 上不一定相邻段式用户程序地址空间按进程自身的逻辑关系划分为若干段，内存 空间被动态的划分为若干个长度不相同的区域（可变分区）。以段为单位分配内存，每一段在内存中占据连续空间，各段之 间可以不连续存放段页式用户程序地址空间：段式；内存空间：页式；分配单位：页1. 单一用户（连续区）特点:一段时间内只有一个进程在内存简单，内存利用率低内存分为两个区域:一个供操作系统使用;一个供用户使用用户程序进内存时，是从内存用 户区的固定地址开始连续完整存放;不存在分配、回收问题。分区管理2. 固定分区系统先把内存划分成若干个大小固定的分区，一旦划分好，在系统运行期间不再重新划 分。为了满足不同程

14、序的存储要求,各分区的大小可不相等。由于分区的大小固定,就限 制了可容纳程序的大小，因此要求程序运行时必须提供对内存资源的最大申请量。 每个分区装一个且只能装一个进程管動法.内存分配表每个分区按顺序在分区说明表中对应一个表目，表目内容包括分区序号、分区 大小、分区起始地址以及使用状态，程序运行时，根据具最大需求量，按一定的分 酉己策略在分区说明表中查找空闲分区，找到则占用，完成时释放。3可变分区1. 根据进程的需要，把内存空闲空间分割出一个分区，分配给该进程2. 剩余部分成为新的空闲区容易导致的问题：外碎片化，导致内存利用率下降碎片问题解决碎片-很小的、不易利用的空闲区-导致内存利用率下降 解

15、决方案t紧缩技术（memory compaction）在内存移动程序,将所有小的空闲区合并 为较大的空闲区又称:压缩技术,紧致技术，搬家技术紧缩时要考虑的问题系统开销？移动时机?分区管理优缺点：优点:存储管理技术简单易行，内存共享，便于动态申请内存缺点:内存利用率低，存在严重的碎片问题，不提供虚存，不能对内存扩充，存 储收到实际存储容量的限制。页式存储管理4页式存储管理出发点:打破存储分配的连续性，使得一个程序的逻辑地址空间可以分布在 若干离散的内存块上，从而达到充分利用内存，提高内存利用率的目 的。MMU:Memory Management Un it（存储管理咅M牛）页式存储管理英国曼 彻

16、斯特大学设计思想划分是由系统自动完成的，对用户是透明的用户程序地址空间划分划分为大小相等的部分一页内存空间按页大小划分为大小相等的区域，称为内存块（物理页面，页框，页帧）内存分配（规则）以页为单位进行分配，并按进程需要的页数来分配; 逻辑上相邻的页，物理上不一定相邻典型页面尺寸：4K或4M逻辑地址页号页内地址编号0V048575相对地址（T4095相关数据结构及地址转换页表页表项:记录了逻辑页号与页框号的对应关系每个进程一个页表,存放在内存 空闲内存管理地址转换（硬件支持）CPU取到逻辑地址，自动划分为页号和页内地址;用页号查页表,得到页框号,再 与页内地址（页内偏移）拼接为物理地址硬件支持：

17、1硬件寄存器每个进程都有一张页表，页表所指内存的起始地址和长度作为现场信息存 入PCB ,进程一旦被调用，这些信息将被作为恢复现场信息送入系统的地址映射机制中 的寄存器中。2地址映射过程也表示硬件进行地址转换的依据,每执行一条指令时按照逻辑地址中的 逻辑页号检查页表，若页表中无此页号，则产生一个地址越界的程序性中断事件;或 页表中有此页号，则可得到对应的内存块号，将其转成为可以访问的内存物理地址： 物理地址二内存块号X块长+页内地址注:由于块长是2的整数次幕，故实际上乘的运算在机器中用移位运算代替。因此上式的 结果就是把内存块号作为绝对地址（物理地址）的高位地址，而页内地址作为他的低地址部 分

18、。图示见书上P1883快表的引入（书上P189详解）TLB : Translation lookaside buffer,即旁路转换缓冲，或称为页表缓冲；里面存放的是一些页表文件 （虚扌她址到物理地址的转换表）o在地址映射机制中增加一个小容量的相联存储器。它由高速缓存器组成，可以从硬件上 保证按内容并行查找，速度快，所以称为快表。用来存放当前访问最频繁的少数活动页面 的页号。（1）页表始址寄存器:用于保存正在运行的进程的页表在内存的首地址。（2）页表长度寄存器，用于保存正在运行进程的页表长度。页式存储管理优缺点：优点:不要求作业或进程的程序段和数据在内存中连续存放,从而有效解决了碎片问题， 提

19、高了内存的利用率，有利于组织多道程序执行缺点:虽然页式存储管理消除了碎片，但每个程序的最后一页内总有一部分空间得不到利 用，如果页面较大，则这一部分的损失仍然很大。段式存储管理1内存划分：内存空间被动态地划分为若干个长度不相同的区域，每个区域称作一个物理段。每个物 理段在内存中有一个起始地址，称作段首址。将物理段中的所有单元从0开始依次编 制，称为段内地址。2逻辑地址空间划分：用户程序按逻辑上有完整意义的段来划分。成为逻辑段，简称段。一个逻辑段中的所有 单元从0开始编制，称为段内地址。用户程序的逻辑地址由段号和段内地址两部分组成:段号1段内地址3内存分配：系统以段为单位进行内存分配，为每一个逻

20、辑段分配一个连续的内存区(物理段)。逻辑上 连续的段在内存上不一定连续。管理方法：段表：程序装入内存后，系统为每个用户程序建立一张段表,用于记录用户程序的逻辑段 与内存物理段之间的对应关系。段表包括逻辑段号、物理段起始地址(段首址)和物 理段长度三项内容。用户程序有多少逻辑段，该段表里就登记多少行，且按逻辑段 的顺序排列。段表存放在内存系统区里。建立内存分配表：段式存储管理分配内存空间的方法与可变分区管理方案的分配方法相同，也有相同结构的 内存分配表，包括已分配区表和空闲区表。与可变分区管理方案不同的是：段式存储管理是为程序的每一个分段分配一个连续的内存空间。分配算法也可以采用首先适应算法、最

21、佳适应算法、最坏适应算法。进行内存分配时，根 据段长找出一个可容纳该段的空闲区，分割该空闲区，一部分用来装入段信息，另一部 分仍为空闲区。仍可采用拼接技术来合并分散的空闲区。硬件支持：(1) 段表始址寄存器:用于保存正在运行的进程的段表在内存的首地址。(2) 段表长度寄存器，用于保存正在运行进程的段表长度。为了加快地址映射,也可以采用快表技术。地址映射过程:（书上P191）需要注意的是，此时在快表中除了段号、段首址外还有段长度 需要匕液判断。段式存储管理优缺点：优点:支持用户内存观点的一种内存管理模式。进程逻辑空间最接近用户观点，克服 了页式的非逻辑划分给保护和共享与动态伸缩带来的不自然性。最

22、大好处是可以充分 实现共享和俯户。总结:便于动态申请内存,管理和使用统一化，便于共享，便于动态链接；缺点:仍然存在碎片问题。段页式存储耳1基本思想：用页式方法来分配和管理内存空间，即把内存划分为若干大小相等的页面;用段式 方法对用户程序按照其内在的逻辑关系划分为若干段;再按照划分内存页面的大小，把每 段划分成若干大小相等的页面。因此用户程序的逻辑地址由三部分组成：段号S段内地址w页号P页内地址D程序员可见的是段号S和段内相对地址W。P和D是由地址变换机构把W的高几位解 释成页号P ,把剩下的低位解释为页内地址D得到的。同时体现了段、页式管理方式的 特点:书上P193页2管理方法：系统必须为每个

23、进程建立一张段表;系统还要为每一个段建立一张页表。段表中记 录了该段对应页表的起始地址和长度;而页表则给出该段的每个逻辑页面与内存块号之间 的对应关系。需要位图”法建立内存分配表,用于记录并管理内存空闲块。3硬件支持：(1) 段表始址寄存器:用于保存正在运行进程段表的起始地址(2) 段表长度寄存器:用于保存正在运行进程段表的长度详见P193内存扩充目标:解决在较小的存储空间中运行较大程序时遇到的矛盾内存紧凑(例如:可变分区)覆盖技术交换技术虚存技术覆盖技术(Overlaying)(主要用于早期的操作系统中)解决的问题-程序大小超过物理内存总和程序执行过程中，程序的不同部分在内存中相互替代-按照

24、其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域-要求程序各模块之间有明确的调用结构程序员声明覆盖结构,操作系统完成自动覆盖覆盖技术的不足增加编程困难。需程序员划分功能模块,并确定模块间的覆盖关系。增加了编程的复杂度增加执行时间。从外存装入覆盖模块。时间换空间交换技术（Swapping）最早用于小型分时系统roll in roll out设计思想内存空间紧张时，系统将内存中某些进程暂时移到夕卜存，把外存中某些进程 换进内存，占据前者所占用的区域（进程在内存与外存之间的动态调度）讨论:实现时遇到的问题进程的什么部分需要交换到磁盘?会遇到什么困难?运行时创建或修改的内容:栈和堆在磁盘的

25、什么位置保存被换出的进程?交换区一般系统会指定一块特殊的磁盘区域作为交换空间（swap spac , 包含连续的磁道，操作系统可以使用底层的磁盘读写操作对其高效访问。交换区是生盘，不用找页表（找页表的是文件系统），直接由操作系统管理 交换时机?只要不用就换出（很少再用）;内存空间不够或有不够的危险时换出-与调度器结合使用如何选择被换出的进程?考虑进程的各种属性;不应换出处于等待I/O状态的进程（如果传回数据传 给谁呢？并且数据是可变的）换出后再换入的进程是否回到原处?换出后又换入的进程不一定回到原处（采用动态重定位）如何处理进程空间增长?进程空间增长的困难及解决数据段 栈段Room lor growthActually in useRoom lor growth Actually in user Room for growth Room for growlh数据段和栈段相对增长