网络操作系统第8章 存储管理 1

1第8章存储管理存储器是计算机的记忆部件，计算机系统的主要用途是执行程序，在执行程序时，这些程序及其所访问的数据必须在内存里。由于内存通常太小不足以永久地容纳所有数据和程序，因此计算机系统必须提供外存（如硬盘）以扩充内存的技术。在现代计算机系统中，内存是一个关键性的资源。能否合理而有效地使用它，在很大程度上反映了操作系统的性能，并直接影响整个计算机系统作用的发挥。所以，存储管理是目前人们研究操作系统的中心问题之一。28.1存储器的层次8.1.1三级存储器结构高速缓存（cache）—内存（primarystorage）—外存（secondarystorage）目的:解决CPU访问数据时CPU与内存、外存与内存在传递信息交换过程中的速度差问题。38.1.2存储管理的功能1.内存分配和回收使各作业或进程各得其所2.内存保护内存保护就是确保多个进程都在各自分配到内存区域内操作，互不干扰，防止一个进程破坏其他进程的信息。3.内存扩充内存“扩充”包含了存储器利用的提高和扩充两方面的内容。为用户提供比内存物理空间大得多的地址空间。比较典型的内存扩充是虚拟存储器。4.地址映射地址映射就是将进程的逻辑地址变换为内存中的物理地址。我们需要实现从逻辑地址到物理地址的变换，即实现从虚地址到实地址的变换。这种变换就是重定位。4几个重要的概念①逻辑地址（虚拟地址）用户程序经编译、链接以后形成的每条指令或数据单元的地址，这些地址都是相对于某个基地址来编制的。②逻辑地址空间某个用户程序的虚拟地址的集合。③物理地址（绝对地址）处理机能直接访问的存储器地址。④物理地址空间物理地址空间是指进程在内存中一系列存储信息的物理单元的集合。物理地址空间也叫存储空间，存储空间与地址空间既相互关联，又相互独立，是内存管理的核心概念。51、直接分配2、静态分配3、动态分配8.1.3内存分配的方式8.1.4重定位重定位：完成虚拟地址到物理地址的转换。重定位可分为静态重定位和动态重定位。①静态重定位在程序执行之前由装配程序完成由虚拟地址到物理地址的转换过程。6优点：(1)、不需要硬件的支持。(2)、程序执行速度快。缺点：(1)、不能实现虚拟存储。(2)、必须占用连续的内存空间。(3)、不能实现程序和数据的共享。静态重定位示例：Movax,[100]Xorax,axMov[200],ax如装入起始地址为1000H的内存块处，则重定位后，程序段改为：静态重定位示例：Movax,[1100]Xorax,axMov[1200],ax7②动态重定位在程序的执行过程中，在CPU访问内存时所进行的虚拟地址到物理地址的转换过程。动态地址重定位必须依靠硬件地址变换结构（动态重定位机构）的支持+50010008优点:(1)、可以对内存进行非连续分配。(2)、为实现虚拟存储器提供了基础；(3)、有利于程序段或数据的共享。缺点：需硬件支持，成本增加。动态重定位是一种允许进程在执行过程中在内存中移动的技术，必须获得硬件地址变换机构的支持。在多任务操作系统中，多个进程在内存中并发执行，进程的创建与撤消，多个进程之间频繁的上下文切换，其内存分配呈现动态性和随机性。静态重定位仅适应于连续分配，不能满足多任务操作系统动态性和随机性的要求，因此多任务操作系统存储管理适合采用离散分配，必须采用动态重定位。98.2分区式存储管理内存分配方式可分为连续分配方式和离散分配方式，本节将讨论连续分配方式。分区式存储管理是连续分配方式，为一个进程分配一个连续的存储空间。分区式存储管理支持多道程序系统和分时系统，但内存分配存在不可利用的内存空间，即碎片问题。碎片一般可分为内碎片和外碎片。前者是指分区内不可利用的内存空间，后者是指分区之间难以利用的小空闲分区。内碎片和外碎片都可以降低内存的利用率，但外碎片对系统的危害更大。关于碎片问题将在各种内存分配方式中详细讨论。108.2.1单一连续分配单一连续分配内存分配优缺点如下：优点：实现简单，不需要复杂的软、硬件支持。缺点：存在内碎片问题。资源利用率低，由于存储资源利用率低而造成其他资源利用率低（如CPU、外设等），特别是不允许多个进程并发运行，这是不容忽视的缺点。CP/M和DOS2．0以下的版本就是采用此种方式。118.2.2固定分区分配1、基本原理：操作系统或系统管理员在操作系统启动时，把内存划分为若干大小不等的区域，分区一旦划定，在整个执行过程中就不能改变。每个作业占用一个分区，每个作业都占用连续的一片内存区域。固定分区分配是最简单的多道程序的存储管理方式，它用于IBM/360的MFT操作系统中。2、存储器的分配和回收：分配：当用户程序要装入执行时，系统就根据其要求的内存空间大小，按最佳适应法找出一个存储区分配给它。回收：当用户作业执行完毕时，系统将其占用分区的状态位置为空闲即可。123、使用的数据结构和分配算法（1）数据结构：分区说明表（2）地址变换：采用静态重定位技术4、优缺点：优点：管理简单，系统开销小，需要硬件少，只需要一对界址寄存器；缺点：因分区大小固定，分区中总会有空闲的部分，所以存储空间的浪费大，无法实现存储共享，也无法存储扩充。138.2.3动态分区1、基本原理：作业运行前系统中不建立分区，分区的建立是在作业的处理过程中进行的，是根据进程对内存的要求而为作业或进程分配相应大小的分区。每个作业占用一个分区，每个分区都是一片连续的内存区域。动态分区是根据进程的实际需要，动态地为之分配内存空间。空闲区OS作业1作业2OS空闲区作业空闲区作业作业空闲区作业OS142、存储器的分配和回收（1）分配回收中要用到的数据结构：空闲分区表用于为内存中每个尚未分配出去的分区设置一个表项，包括分区序号，分区始址，分区大小和状态等。如下所示：区号大小始址状态132k552k可用2…………空表项3520k704k可用4…………空表项5…………空表项空闲分区表FBT15已分配分区表每个已分配分区对应一个表项，记录了该分区的始址和大小等区号大小始址状态18k512k已分232k552已分3…………空表项4120k584已分5…………空表项已分分区表UBT161．空闲分区链表每个空闲分区的前后两个单元，放置空闲分区的说明信息和指针。如图所示，系统设立一个链首指针Free，指向第一个空闲分区。空闲分区排列需按照一定的规律（如按大小、按地址），分配进程可以依照空闲分区链表，来查找适合的空闲分区进行分配。172.动态分区的分配算法⑴首次适应算法一旦找到大于或等于所要求内存长度的分区，则结束查找，然后按作业的大小，从该分区中划出一块空间分给请求者，余下的部分仍留在空闲链或空闲表中，它要求空闲分区表或自由链按其始地址递增的次序排列。优点：倾向于使用低地址空间，为以后的大作业保存了高地址的大空闲区。缺点：低地址空间被多次划分，会产生许多个小的无法使用的分区。而且每次查找空闲区都从低地址开始，会增加查找开销。18（2）最佳适应算法它要求找到一个长度大于等于所要求内存长度，且最接近于所要求内存大小的分区进行分配。然后按作业的大小，从该分区中划出一块空间分给请求者，余下的部分仍留在空闲链或空闲表中。它要求空闲分区表或自由链按分区大小递增的次序排列。说明：从表面上看，该算法是最节省空间的，但由于每次分配后剩下的部分，也是最小的，这样会产生许多难以利用的小空闲区。19（3）最差适应算法它要求找到一个长度大于等于所要求内存长度，且最大的分区，然后按作业的大小，从该分区中划出一块空间分给请求者，余下的部分仍留在空闲链或空闲表中。它要求可用表或自由链按分区大小递减的次序排列。说明：孤立地看，该算法是最浪费内存空间的，但由于每次分配后剩下的部分也是最大的，这样会为以后的大作业留下空间。20（4）循环首次适应算法循环首次适应算法的空闲链是对空闲分区按照地址从低到高的顺序排列起来（同上）。每次分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空闲区，就把该空闲区切割出进程大小，分配给该进程，余下的空闲分区仍留在空闲链中。该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销，但这样会缺乏大的空闲分区。213、自由（空闲）分区表FTB的组织：（1）如果分配算法采用最先适应法，则按分区的起始地址从小到大排序（内存地址高低）（2）如果分配算法采用最佳适应法，则按分区的大小从小到大排序（3）如果分配算法采用最坏适应法，则按分区的大小从大到小排序4、自由分区链的组织：（1）如果分配算法采用最先适应法，则按分区的位置拉链（2）如果分配算法采用最佳适应法，则按分区的大小从小到大拉链（3）如果分配算法采用最坏适应法，则按分区大小从大到小拉链225．动态分区内存的分配与回收。（1）动态分区内存分配规定不再切割尺寸大小为size。从空闲分区链表中找到所需大小的分区。设进程请求的尺寸大小为u.size，空闲分区的大小可表示为m.size。若m.size-u.size≤size，说明多余部分太小，可不再切割，将整个分区分配给进程；23（2）内存回收和拼接情况一：前邻空闲区，回收区与插入点的前一个空闲区F1相邻接。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区Fl的大小，大小为两者之和。情况二：前后邻空闲区，回收区同时与插入点的前空闲区F1和后空闲区F2两个空闲区邻接。此时将三个分区合并，使用前空闲区F1的首址作为新空闲区的首址，大小为三者之和，取消F2的表项。情况三：后邻空闲区，回收分区与插入点的后一空闲区F2相邻接。此时也可将两分区合并，形成新的空闲分区，用回收区的首址作为新空闲区的首址，大小为两者之和。情况四：前后不邻接空闲区，回收区不与空闲区邻接。这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。24（3）动态分区优缺点优点：①实现了多个作业或进程共享存储器②要求硬件支持少，管理简单，容易实现缺点：①内存利用率不高（碎片）②作业或进程大小受分区大小的控制（连续分配）③难以实现信息共享258.2.4内存紧缩问题在采用动态分区管理的系统经过长时间运行有可能出现内存中剩余空闲很多但却无法分配的问题，因为这些空闲分区都是分散，而且较小。这时就需要进行内存紧缩，把分散的空闲区集中到一起。空闲3（18k)作业3（10k)空闲2（6k)作业2（60k)空闲1（6k)作业1（50k)OS(50k)空闲3（30k)作业3（10k)作业2（60k)作业1（50k)OS(50k)268.2.5覆盖技术和交换技术1、覆盖技术覆盖技术就是在较小的可用内存中运行较大的程序。所谓覆盖是指程序中的若干程序段或数据段按照时间先后使用内存的某个区域。实现方法：将程序必要部分的代码和数据常驻内存，可选覆盖部分平时存放在外存中，在需要时才装入内存。2、交换技术操作系统把那些在内存处于阻塞状态的进程换出内存，而把那些等待事件已经发生、处于外存就绪状态的进程换入内存。MAIN（30K）Sub1(20k)Sub2(40k)Sub3(30k)Sub11(40k)Sub31(40k)Sub12(50k)Sub32(40k)278.2.6伙伴系统实现原理：一个伙伴系统内存的用户可用空间为2U。进程申请存储空间时，系统总是为其分配大小为2I的一个空闲分区。其中S≤I≤U，2S是系统允许的最小分区尺寸。在实际操作系统中，最小分区尺寸一般为212。如果进程申请的存储空间大小为K，且2I-1K≤2I，则将整个2I大小的分区分配给该进程；否则，该分区被分割成两个大小相等的伙伴分区，大小为2I-1；再判断K是否满足条件：2I-2K≤2I-1，若满足条件，则将两个伙伴中的任何一个分配给该进程。否则，将其中一个伙伴又分成两个大小相等的伙伴分区；此过程一直继续进行，直到