2016第四章存储管理21剖析

《2016第四章存储管理21剖析》由会员分享，可在线阅读，更多相关《2016第四章存储管理21剖析（96页珍藏版）》请在金锄头文库上搜索。

1、在早期的操作系统中，主存分配广泛采用连续分配方式。 连续分配方式为一个用户程序和数据分配一个连续的主存空间。,4.2 连续存储空间管理,1,一、单一连续分配（单个分区）,最简单的存储管理方式，用于多道程序设计技术之前。 内存分为系统区和用户区，系统区由操作系统使用。用户区作为一个连续的分区分配给一个作业。 评价 优点：方法简单，易于实现 缺点： 1.仅适用于单道程序，只能用于单用户单任务的操作系统 2.系统资源利用率低,2,分区存储管理是满足多道程序设计的最简单的一种存储管理方法，它允许多个用户程序同时存在系统内存中，即共享内存空间。 按分区划分方式可分为固定分区和可变分区。,3,二、 固定分

2、区存储管理,1.基本思想 把内存的用户区预先划分成多个分区，每个分区大小可以相同，也可以不同。（分区的划分由计算机的操作员或者由操作系统给出，并给出主存分配表） 分区个数固定，分区的大小固定。 一个分区中可装入一个作业，作业执行过程中不会改变存放区域。,早期的IBM的OS/MFT（具有固定任务数的多道程序系统）采用了这种固定分区的方法。,4,例：某系统的内存容量为256K，操作系统占用低地址的20K，其余空间划分成4个固定大小的分区。如下图,主存分配表,5,2.主存分配表 为了说明各分区的分配和使用情况，需设置“主存分配表”，记录各分区及其使用情况。 主存分配表内容：分区号，分区的起始地址，长

3、度，占用标志。 3.主存空间分配 主存存分配程序检索主存分配表，从中找到还未分配且大小满足（作业要求的内存空间大小小于等于分区的大小）要求的分区，则将此分区分配给该作业。若没找到满足条件的分区，则拒绝为该作业分配主存。,6,三、 可变分区存储管理（动态分区）,1.基本思想 内存不是预先划分好的，而是在系统运行的过程中建立分区.当作业装入主存时，根据作业所需要的主存容量查看是否有足够的主存空间，若有则按需要分割一个分区给该作业；否则令该作业等待. 分区长度不固定,分区个数不固定. 这种存储管理的方法克服了固定分区严重浪费主存的问题，提高了主存资源的利用率。 操作系统采用可变分区存储管理。,7,当

4、有作业完成后释放所占用的存储区。 在系统运行的过程中，系统中形成多个空闲的不连续的存储区，称空闲区。,2.实现动态分区需要的数据结构,在动态分区存储管理中，要有相应的数据结构来登记空闲区信息，它包括空闲区的大小和位置。 不同系统根据设计要求采用不同的结构。常用的有表结构和链结构。 系统还要设置了等待分区队列，当系统中无空闲区或无满足要求的空闲区时，则把申请者送入等待队列中，等待别的进程释放内存之后再唤醒队列中的进程。,9,例:,10,3.分区分配算法,空闲区表（链）中的空闲区可按一定规则排列，例如按空闲区大小的升序（降序）排列；按空闲区地址升序（降序）组织。 根据空闲区表（链）排列方法不同，对

5、应不同的分配算法，常用的可变分区分配算法有最先适应算法，下次适应分配算法，最优适应算法、最坏适应算法等。,11,(1)最先适应算法,各个空闲区按其首地址从小到大的次序排列。,分配：当进程申请大小为SIZE的内存时，系统顺序查找空闲区表（链），直到找到容量满足要求（SIZE）的空闲区为止。从该空闲区中划出大小为SIZE的分区分配给进程，余下的部分仍作为一个空闲区，但要修改其首址和大小。,优点：这种算法是尽可能地利用低地址部分的空闲区，而尽量地保证高地址部分的大空闲区，有利于大作业的装入。 缺点:主存低地址和高地址分区利用不均衡。在低地址部分,集中了许多非常小的空闲区(碎片),降低了主存的利用率。

6、,12,（）下次适应分配算法,最先适应算法的变种。 总是从空闲区上次扫描结束处顺序查找空闲区表（链），直到找到第一个满足容量要求的空闲区为止，分割一部分给作业，剩余部分仍作为空闲区。,13,()最优适应算法,空闲区按容量递增的次序排列。,分配：当进程申请存储空间，系统顺序查找空闲区表（链），直到找到第一个满足容量要求的空闲区为止。 采用最优适应算法选中的空闲区是满足容量要求的最小空闲区。,14,()最坏适应算法,要求空闲区按容量递减的顺序排列。,分配：进程申请存储区时，检查空闲区表（链）的第一个空闲区的大小是否满足要求，若不满足则令进程等待；若满足则从该空闲区中分配一部分存储区给用户，剩下的部

7、分仍作为空闲区。,为了克服最佳适应算法把空闲区切割得太小的缺点，人们提出了一种最坏适应算法，即每次分配时，总是将最大的空闲区切去一部分分配给请求者，剩余的部分仍是一个较大的空闲区。避免了空闲区越分越小的问题。,15,例：某时刻系统中有三个空闲区,有一作业大小25k。,首次适应算法： 最优适应算法： 最坏适应算法：,16,4.可变分区的回收,当某个进程释放某存储区时，系统首先检查释放区是否与系统中的空闲区相邻，若相邻则把释放区合并到相邻的空闲区中去，否则把释放区作为一个空闲区插入到空闲区表的适当位置。,释放区与空闲区相邻的四种情况,17,(a)释放区与前空闲区相邻：将释放区与前空闲区合并为一个空

8、闲区。其首址仍为前空闲区首址，大小为释放区大小与空闲区大小之和。 (b)释放区与后空闲区相邻：则把释放区合并到后空闲，首地址为释放区首地址，大小为二者大小之和。 (c)释放区与前后两个空闲区相邻：将这三个区合为一个空闲区，其首址为前空闲区首址，大小为这三个区大小之和，并取消原后空闲区表目。 (c)释放区不与任何空闲区相邻：将释放区作为一个空闲区，将其大小和首址插入到空闲区表的适当位置。,18,5.地址变换与存储保护,在多道程序设计的环境下，为了不相互干扰，要将各个程序限定在自己的范围内（没有授权不许访问其它程序空间的数据）。这就是存储保护所要解决的问题。 界地址寄存器被广泛使用的一种存储保护技

9、术机制比较简单，易于实现. 实现方法有两种：上下界保护，基址、限长寄存器保护。,限定在该范围内,上下界保护（见本章第一节课件）,下界寄存器：存放程序装入内存后的首地址 上界寄存器：存放程序装入内存后的末地址 判别式：（下界寄存器） 物理地址 （上界寄存器）,例： 有一程序装入内存的首地址是500，末地址是1500，访问内存的逻辑地址是500、345、1005。 下界寄存器：500 上届寄存器：1500 逻辑地址装入内存的首地 物理地址 1、500500 1000 500 1000 1500 2、345500 845 500 845 1500 3、1005500 1505 500 1505 15

10、00,基址、限长寄存器保护,基址寄存器：存放程序的起始地址。 限长寄存器：程序的长度（单位：字节） 判别式：0 逻辑地址（限长寄存器） 如果未越界，则按此地址访问主存，否则将产生程序中断越界中断（存储保护中断）,例： 有一程序装入内存的首地址是500，末地址是1500，访问内存的逻辑地址是500、345、1005。 基址寄存器：500 限长寄存器：1000 1、 0 500 1000 2、 0 345 1000 3、 0 1005 1000,支持共享的多对重定位寄存器,24,重定位寄存器1,限长寄存器1,重定位寄存器2,限长寄存器2,重定位寄存器1,限长寄存器1,重定位寄存器2,限长寄存器2,

11、进程A的私有空间,进程B的私有空间,共享空间,重定位寄存器同时也是基址寄存器,四、内存不足存储管理技术,1.移动技术。 基本思想 例:内存中现有3个空闲区，如图所示，现有一作业到达，要求获得30k内存空间，没有分区满足容量要求，若想把作业装入，可将内存中所有作业进行移动，这样把原来分散的空闲区汇集成一个大的空闲区。,25,将内存中的作业进行移动,使它们连接在一起,把原来分散的多个小分区拼接成一个大的空闲区.这个过程称为”紧凑”或”移动”. 需解决的问题:每次”紧凑”后,程序或数据装入的物理地址变化,采用动态重定位.,26,2. 覆盖技术,27,把程序划分为若干个功能上相对独立的程序段，按照其自

12、身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域 程序段先保存在磁盘上，当有关程序段的前一部分执行结束，把后续程序段调入内存，覆盖前面的程序段（内存“扩大”了） 覆盖：一个作业的若干程序段，或几个作业的某些部分共享某一个存储空间 一般要求作业各模块之间有明确的调用结构，程序员要向系统指明覆盖结构，然后由由操作系统完成自动覆盖,28,3.对换技术,为平衡系统负载，通过选择一个进程，把其暂时移出到磁盘，腾出空间给其他进程使用，同时把磁盘中的某个进程再换进主存，让其投入运行，这种互换称对换。 多用于分时系统中,29,选择原则（即：将哪个进程换出内存？） 时间片轮转法或基于优先数的调度算法，通

13、常把时间片耗尽或优先级较低的进程换出，因为短时间内它们不会被投入运行。 对换时机（即：何时需发生对换） 批处理系统中，当有进程要求动态扩充主存且得不到满足时可触发对换； 分时系统中，对换可与调度结合在一起，每个时间片结束或执行I/O操作时实施。,30,上节所介绍的连续分配方式，会出现碎片问题，虽然采用“紧凑”的方法将许多碎片拼接成可用的大块空间，但须为之付出很大开销，而无实用价值。如果允许将一个进程直接分散地装入到许多不相邻的分区中，则无须再进行“紧凑”。基于这一思想而产生了离散分配方式。 离散分配方式：给进程分配几个不连续的内存区域，并可保证进程的正确执行。 离散分配方式按分配基本单位不同分

14、为分页存储管理和分段存储管理。,31,4.3 分页存储管理,分页技术是由曼彻斯特大学提出，并于1960年前后在Atlas计算机上实现。这种技术对操作系统的发展产生了深远影响。,32,一、基本原理,1.页面 把一个进程的逻辑地址空间分成若干大小相等的片，每个片称为页面或页 。从0开始编制页号。 页面的大小应选择适中，一般页的大小为2的幂，通常为512 B8 KB。 2.逻辑地址 分页存储管理逻辑地址分为两部分：地址的高位部分为页号，低位部分为页内位移。,例：逻辑地址32位，页大小4k，则页内位移占12位，页号占20位。,33,3.物理块（页框） 把主存的物理地址空间分成和页面大小相等的区，每个区

15、称为物理块或页框。从0开始编制块号。 4.物理地址 5.分页存储管理基本原理 以页为单位进行分配。当一个进程装入内存时，将进程的多个页面分别装入内存的多个物理块中，这些物理块可以是不相邻的。,34,例：页面大小1k,35,如何重定位这些分散的页面？,6.页表 进程的各个页面分散存放在主存不相邻的物理块中，系统如何知道页面和物理块的对应关系。 这就需要系统为每个进程建立一个页表，用来登记页号和块的对应关系和有关信息。 一个进程有多少个页面，页表就有多少项。 进程的页表大多驻留在内存中 ，页表在主存的首地址和长度存放在该进程的进程控制块。,36,例：页面大小1k,进程1页表,页号 块号,页号 块号

16、,进程2页表,37,二、地址转换,把程序的逻辑地址转换成内存的物理地址。 1.分析： 程序逻辑地址： 内存物理地址：,页表,38,进程的页表放在内存中，页表在主存的首地址和页表长度保存在本进程的PCB中。 系统设置了一个页表寄存器，当系统调度一个进程运行前，系统把该进程的页表首地址和页表长度送入到该页表寄存器中，以便地址转换时使用。,39,2.地址转换过程：,p,页表,地址越界中断,L,比较,P=L,b,+,页号p 页内地址d,块号P,块内地址d,物理地址,页表首址寄存器,页表长度寄存器,逻辑地址,P*表项长度,p,40,40,页式地址变换过程例子,假设页大小为1K,逻辑地址2500处是123数据,0 0 0 1 1 1,0 1 1 1 0 0 0 1 0 0,页式地址变换过程,比较,硬件能自动分离出页号和页内地址，但我们只能通过计算才能得到。计算时要注意