11.第11节课第四章存储器管理
第二种情况呢？是回收区域插入点的后一分区的。后一空闲分区f2相邻，那么此时呢？可将两分区合并，形成新的空闲分区，但用回收区的手指呢？作为新空闲区的手指大小为两者之和。啊，比如说我们的回收区啦，与它之后的这个空闲区啦。相连接，那么此时呢？将两者分两分区的合并形成新的共享分区。那么，但回收区的手指呢？作为空闲区的手指，你看大小为两者之和，那么还有第三种情况，回收区呢？同时，与插入点的前后两个分区连接。比如说这个时候三个分区合并使用f1的表象和f1的手指，取消f2的表象大小，为三者之和。比如说这是这种情况呢，当回收区呢，与同时与插入点的前后两个分区呢都相连接，那么这个时候呢，两个三个分区合并。
使用f1的表象和f1的手指取消f2的表象大小呢，为三者之和，还有第四种情况维持距，既不与f1相邻，又不与f2相邻。这是因为回收区单独建立一个新表项，填写回收区的手指和大小，并根据其手指插入到贡献表中的相应位置。那我们来看一下这个图，当中回收的这样一个流程。首先呢，回去去m free顺序。顺顺序字。检索可用资源表，直到找到某表的这样一个m address，
大于a或者m散热等于零。那么，如果不是第一个表目，那么是否与前一个相邻？那么是与前一个相邻，那么把所释放的可用分区与权益分区合并？那么，是否为另一后一分区和相邻呢？如果是的话，与后一分区相合，并将该表目以及所有表目呢向下移一个。那么，如果呢？不是以后有分区详离，那么就返回的这样一个部分。
那么，如果呢？不是与第一个，如果第一个表目呢？不是与前一个表目相邻，那么是否与后一个表目相邻？如果是的话，那么所释放可用去的赛日呢？等于零。那么，如果是的话呢，将该表目以上所有表目的上移一个，并插入新释放的可用去表目，如果否的话呢，就进行返回。
那么，如果呢？是否与后一分区相邻，局部为空表部？如果是的话，那么所释放的可用区？与后羿可用去合并那么进行返回，那么这是我们内存回收流程的这样一个部分，那么接下来我们看一下基于动态，基于顺序搜索的这种动态分区分配算法。那么，我们来看一下。那么，我们呢？基于顺序搜索的动态分区分配算法呢？
是指依次搜索空闲分区链上的空闲分区，去寻找一个大小能满足要求的分区。基于顺序搜索和动态分配的动态收分区的这样一个分配算法呢，有四种首次适应循环，首次适应。最佳适应和最坏适应，那么我们首先来看一下最佳适应。最佳适应算法呢ff算法，我们以空闲分区为例呢，来说明采用ff算法分类情况ff算法呢，要求空闲分区呢，以地址递增的次序链接。那么，在分配内存时呢？从练手开始，
顺序查找，直到查找一找到一个大小能满足要求的空闲分区位置，然后按照该作按照该作业的大小呢？从。该分区中呢，划分出一块内存空间，分别给请求者剩余的空闲区呢，仍留在空闲列表中。如果从链首至链尾都不能找到一个能满足该要求的分区呢？则表明系统呢，也没有足够大的内存的分配给分I分区内存分配失败，那么我们这里呢是将？大家大家注意，这里首次适应呢。要求空闲分区以地址递增的顺序链接这里，
大家要注意。首次适应要求，空闲分区以地址递增的顺序。次序链接在分配内存时，从链首开始顺序查找，直到找到一个大小的满足要求的空闲分区为止，然后按照作业的大小呢，从分区中划出一块存内存空间。分配给请求者剩余的空闲区呢？仍留在空闲列表中，那么这是我们的首次适应算法，那么该算法呢？倾向于优先利用内存中低质部分的空闲空间。从而保留了高质部分的大空闲区，这为以后到达的大作业分配的内存空间呢，
创造了条件，其缺点呢，是低质部分的不断被划分，会留下许多难以利用的很小的空闲分区。称为碎片，而每次查找呢，又是从低址部分开始，这样呢，又增加了可用分区查找，可用分区的开销。接下来我们看一下循环首次适应算法，为了避免低值部分呢，留下许多小空闲区以及查找可用空闲分区的开销。循环首次适应算法呢，在为内进程分配内存空间时，
不再是每次都从练手开始查找，而是从上次找到的空闲分区的下一个空闲分区查找。大家要注意。是从上次找到空闲分区的下一个空闲分区开始查找，直到了找到一个能满足要求的空闲分区，从中划出一块来与请求大小相等的这样一个空闲分区。空间空间空间内存空间来分配给该作业，那么这是我们的循环处置适应算法。那么，为了实现该算法呢？应该设置一起始查询指针，用于指示下一次起始查询的空闲分区，并采用循环查找方式。如果最后一个空闲分区的大小呢？仍不能满足要求，
则返回到第一个空闲区。比较其是否符合要求，找到后呢，应该调调整查询起始查询指针，因此算法在类存中的共享分区啊，分布的均均匀。从而减少了查找空闲分区时的开销，但这样呢，会缺乏大的空闲空间。接下来我们看一下最佳适应。最佳适应是什么呢？最佳适应是每次当作业分配内存时，总能把满足要求就是最小的空闲分区分配给作业。避免了大材小用，为了加速寻找呢，
该算法要求将所有的空闲分区呢，按其容量。从小到大的数据形成一个空闲分区，那么也就是说。这样呢？第一次找到的能满足空闲区满足要求的空闲区呢，必然是最佳的，那么这样呢？但是呢。用最佳适应算法最似乎。虽然呢，看上去是最佳的，但是呢，实际上呢，却不一定是最佳的，
这样一个情况，因此每次分配后所切割下来的剩余部分呢，总是最小的，因此呢，在存存储器中会留下许多难以利用的碎片。那么我们再看一下最坏适应，由于最坏适应分配算法呢，选择空闲分区的策略呢，恰好与最佳适应，相反它扫描整个空闲分区或列表时。总是挑选一个最大的空闲区从中。分割一部分存储空间给作业使用，那么以致存储器中缺乏大的空闲区，不把它称为最快适应算法。实际上呢，
这样的算法未必了了吧？是最最坏的这样一个情况，它的优点呢？是使可剩下的空间却不是太小，产生的退变的可能性在。最小对中小作业呢，比较有利，同时呢，最坏适应算法，查找效率高，该算法要求呢，将所有空闲分区，其容量呢，从大到小呢，形成一个空闲分区链。
查找时只要看第一个分区了，是否满足作业要求的话就可以，那么这是我们的最快适应的，这样一个算法。接下来我们再看一下基于索引搜索的动态分区分配算法。基于索引分配的动态，分区的分配算法呢，比较适用于不太大的系统，当系统很大时，系统中的内存分区可能很多。相应的，控权分区链可能很长，这时采用动态搜索分区分区方法呢，可能会很慢。为了提高搜索空间，
搜索空闲分区的速度，在大中型系统中呢，往往会采用基于索引搜索的动态分区分配算法。那么，目前常用的算法呢？有我们的快速适应，以及呢伙伴系统和哈希算法。快速算法又称为。分类搜索法是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区呢，单独设立一个空闲分区链表。这样呢，系统中存在多个空闲分区列表，同时呢，在内存中设立一张所谓管理索引表，
其中的每一个索引表项呢，对应了一个空闲分区类型。并记录了该类型共享分区链表表头的指针伙伴系统呢。该上报规定，无论对已分配。分区或者空闲分区。其大小呢，均为二的k次幂k为整数一小于k小于m，通常二的m次幂。是整个可分配内存的大小，也就是最大分配分区的大小，假设系统的可利用空间呢，为2m个字。在二的m次方个字在系统开始运行时，整个内存是一个大小为二的m次方个字的二二的m次方的，
这样一个共享分区。在系统运行过程中呢，由于不断的划分，将会形成若干个不连续的空闲分区。像这些空闲分区呢，按照分区的大小进行分类。对于具有若干相同大小的这样一个共享分区呢，单独设立一个共享分区，双向链表这样呢，不同的共享分区呢，形成了n形成了k个。共享分区列表在伙伴系统中对于一个大小为二的k次方，内存为x的地址块，其伙其伙伴块的地址用波dk x表示，那么它的这样一个公式呢？
是我们这样一个body kx=x+2的k次方若x的模二的k+1次方等于零，那么就是取x+2的k次方。那么，或者是当x模二的k次方呢与？二的k1的五，二的k+1次方呢？与二的k次方那么这个时候呢？它的公式呢，就是x- 2的k次方。那么，哈希算法呢？在上述的分类搜索算法和伙伴输入系统中，都是将空闲分区呢？根据大小进行分类。对于每一类具有相同大小的空闲分区，
单独设立一个空闲分区链表，在分配在为进程分配空间时呢？需要在一张管理所领表中查找所需空间大小所对应的表象，那么从中呢？得到对应的空闲分区列表，表头指针，从而通过查找了得到一个空闲分区。如果空闲分区了。分类较细则相应索引表的表象又就越多，因此呢，会显著增加搜索索引表的表象的时间开销。哈希算法呢，就是利用哈希快速查找的优点。以及呢，空闲分区在利用该空闲区表中的分布规律呢，
建立哈希函数，构造一张以空闲分区大小呢为关键字的哈希表。该表的每一个表象记录呢，对应的一个空闲分区列表表头指针。当进行空闲分区分配的时候呢，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的分区分区。共享分区链表实现最佳分配策略。那么，接下来我们看一下重定位动态，可重定位分区分配，那么重定位呢？那么我们就是。
可重定位呢，那么的含义呢，就是改变它的这样一个地址的，这样一个部分改变它的这样一个物理地址的，这样一个部分，那么我们来看一下紧凑第一个紧凑。连续分配的一个重要特点呢，是一个系统或用户程序呢，必须装入一片连续的。内存空间中，当一台计算机呢，运行了一段时间后，它的内存空间呢，将会被划分出多个小的分区。而缺乏大的。
空闲空间那么即使这些分散的许多小的分区呢，它的总容量之和大于要装入的程序，但由于这些分区呢，不相连接也无法呢，把该程序装入内存。比如说。我们可以采用紧凑的方式。将它呢？组合成一个新的分区，比如说在这个图中呢，我们在图中呢，总共有四个步步相连的小分区，它们的容量分别是10k，30k，14k和64k。
其实总量是80k，但如果一个作业到要求40k的内存空间，则必须为它分配一个连续空间，所以作业无法装入。这些不利不被不能被利用的小分区呢，则是以就是我们的碎片或者称为零头，为什么把大作业装入？则可采用一种。方法呢，是将内存中的所有作业进行移动，将它们全部连接，这样呢，就是把原来的分散的多个空闲小分区呢，分配成一个。拼凑成一个大分区，
将一个作业呢装入该区，通过移动或内存中的作业的位置，把原来多个分散的小分区拼凑成一个大分区的方法呢。称为紧凑，那么虽然紧凑能获得大的充钱空间，但也带来了新的问题。经过紧凑后的用户程序呢，在内存中的位置呢，发生改变，此时呢，若不对程序和数据的地址呢加以修改。或者说加以重定位。这程序呢，并无法执行。因此呢，
在某次紧凑后呢，就必须对移动的程序和数据进行重定位。为了提高历程的利用率，系统在运行过程中经常呢。需要紧凑，每紧凑一次就要对移动的程序和数据进行修改，那么。我们这样呢。可以采用动态重定位的方法来很好的解决这样一个问题。动态重建，我们来看一下，那么在我们之前介绍过的动态装置重运行时，动态装置的方法呢？作业装入内存后呢？所有的地址仍然是相对地址。
而将相对地址转换为物理地址的工作推迟到程序。指令真正要执行时进行，为了使地址的转换不会影响指令的执行速度，必须用硬件机制来变换机，变换机构的支持，也就是说系统中呢，增成一个重定位寄存器，用它来存放程序呢，在内存中的起始地址。程序在运行时呢，真正的内存地址是与地址相对，地址与重定位基准器的地址相加而形成的。比如说我们来看一下这个重定位，它的这样一个实现原理。重新为它这样一个实现的，
这样一个部分。那么，地址变换机构呢？是地址变换过程呢，是在程序执行期间，随着对每条指令和数据的访问，自动进行的。故称为重定位，故称为重，故称为动态重定位。当系统呢，对内存进行了紧凑，而使若干程序呢，从内存的某处移向另一处的时候呢，不需对程序做任何修改。
只要用该程序的内存地址呢？内存的在内存的新起始地址去。置换原来的起始地址就可以啊，比如说这是我们的这样一个动态重定位，它的这样一个示意图，那么这是我们的。相对地址了好吧，再加再加上我们重重的寄存器，那么就得了它这样一个新的，这样一个地址的，这样一个使用的，这样一个应用部分。接下来我们看一下动态态定位，分区分配算法，动态重定位，
分区分配算法呢？与动态分区分配算法的基本相同，区别仅在于呢，在这种分配算法中增加了紧凑的功能。通常呢，如果该算法呢，不能找到一个足够大的共享分区呢，以满足用户的需求时。如果所有的小的。空闲分区的总容量呢？大于用户的要求，只是面对内存进行紧凑，将紧凑后所得到的大空闲区呢？分配给用户。如果所有小的空闲分区的容量仍之和仍小于用户的需求，
则返回分配失败的这样一个信息。那么，我们看这样一个图。首先呢，请求分配u size分区检索共享分区表，那么到找了大于u size的分区了。如果是的话，就按分区动态分区分配进行分配，那么进行紧凑型的新的空选区返回分区号以及手指。那么，如果没有了，那么总空闲总分区啊，空闲分区总和是否大于六的？如果不是的话，那么无法分配返回，
如果是的话，通过紧凑形成新的空闲区。修改有关的数据结构，然后按照动态分区分配进行分配。动态分区方式来进行分配，然后紧凑型的新的邻居空间区返回分区号及手指。那么，接下来我们再看一下兑换兑换技术呢？也称为交换技术。那么，由于我们的最开始呢，计算机的内存内存呢？比较小，为了使系统能够分时运行，多个用户程序而引入的兑换技术。
系统的把所有的用户呢作业存放在磁盘上，每次只能调入一个作业，进入后堆内存，当该作业一个时间片用完时，将它调至外储后备机位上等待。然后从后备队列上呢，将另一个作业调入内存，那么这是最早出现的分时系统的这样一个兑换技术，那么也就是说要实现呢，内外层之间的兑换系统中呢，必须要有一台IO速度极高的外存，其容量呢也比较大。能够容纳正在分时运行的所有作业，那么最常用的是大型容量大容量磁盘存储器，那么接下来我们看一下多大程序环境下的这样一个兑换技术。
那么多大情绪环境下的兑换基数呢？那么在多大情绪环境下，一方面呢，在系统中，由于某些。进程某事件未发生而被阻塞运行，而它却占用了大量的存储空间，甚至呢，有可能出现在内存中，所有进程都被阻塞而无运行进程。而无运行的进程，那么使CPU停下来进行等待，另一方面呢，却有许多的作业因内存空间不足一直驻留在外层上而不能进入内存运行。那么，
这是对系统资源的一种浪费，使系统分组量下降。那么，为了解决这一问题呢？为了解决这一问题呢？在系统中呢，又增加了兑换设施，所谓的兑换呢，那么是把内存中暂时不能运行的进程，或暂时不用的程序或数据灌在了外层上，以腾出足够的内存空间。再把已具备运行条件的进程或进程所需要的程序或数据装入到外存上。装入到外层上。那么，已腾出足够的内存空间，
再把已具备运行条件的。进程或进程所需要的程序和数据呢？换入内存兑换呢？是改善利用内存利用率的有效措施，它可以直接提高处理机的利用率和系统的存储量，那么这是我们的。这是我们的这样一个。兑换的这样一个部分。那么，兑换的类型是什么呢？每次兑换时呢？就是将一定数量的程序或数据换入或换出内存。而根据每次兑换时所换的数量呢，可以把兑换呢分为两类，比如说整体兑换。
整体兑换呢，就说我们之前讲过处理器中级调度呢，实际上就是存储器的兑换功能，目的是为了解决内存的紧张问题，并可以进一步提高内存的利用率和系统的存储量。由于在终极调度中的兑换呢，是以整个进程为单位的，所以称为进程兑换，或者说整体兑换，这种兑换呢被广泛的应用于多道程序系统中，并称之为终极调度。那么，页面兑换或者分段兑换，如果兑换是进程的一个页面，或者说分段为单位介绍的，
这个我们之后呢会介绍这样一个页面会分段。那么，只要称之为页面兑换和分段兑换，又称为部分兑换，这种方法呢？是实现。请求分页或请求分段式的存储管理的基础，其目的是为了支持虚拟机虚拟存储系统了吗？我们之后会讲一下这个虚拟存储系统。为了实现进程兑换，那么系统呢？必须具备三方面的功能，就兑换空间的管理进程的换入。以及进程的换出，那么这些部分那么我们来看一下对兑换兑换空间的管理。
在具有兑换功能操作系统中，通常呢，把磁盘空间分为文件区和兑换区两部分，对文件区管理的主要目标呢，是文件区占用了大量的。此外呢，大部分存放各类文件，由于通常的文件呢，是较长时间的驻留在外层上，对它的访问频率较低。因此呢，固定文件去管理的主要目的呢，是提高文件存储空间的利用率，然后呢，才是对文件的访问速度，
因此呢，对文件空间的管理呢，采取离散分配方式。那么，对兑换空间管理的主要目标呢？兑换空间只占用磁盘空间的小部分用于存放，从内存换出的进程，由于这些进程呢？在兑换区中驻留的时间是短暂的。而兑换超出的频率高，所以呢，对兑换空间管理的主要目标是提高进程换入和换出的速度，然后呢，才是提高文件存储空间的利用率，因此呢，
对兑换空间的管理呢，主要采用连续。去分配方式，那么这是我们的这样一个部分，我们呢？我们再看一下对兑换管理空间当中的这样一个数据结构。由为了实现兑兑换区中的贡献，盘块的管理了在系统中应配置相应的数据结构，用于记录外存兑换区中的贡献，盘块的使用情况，其数据结构的形式呢，与内存在动态。分区分配中的所用的数据结构相似，那么同样的可以用分区空闲分区表或者空闲分区列在空闲分区表的每个表目中呢？应该包含兑换区的手指和其大小，
分别用盘块数呢和盘块号来进行表。表示那么我们再看一下动态分区。兑换空间的这样一个分配与回收，由于兑换空间的分配呢，是采用连续分配方式，因而呢，兑换空间的分配与回收呢，与动态分区。方式的这样一个。内存的分配与回收呢？相对相类似，其分配技术呢？可以是首次适应算法循环，首次算法或者最佳适应算法，具体的分配操作呢？
那么与我们之前图中的内存的分配过程相同。那么，兑兑兑换区的回收操作呢？可以分为四种回收区的取插入点的前一个空权分区f1相连接回收区与插入点后的空权分区相连接。回收分区呢，同时与插入点后两个空间分区相连接，回收分区既不与f1连接，又不与f2连接，那么这样一些。运用的这样一个方式，那么我们再看一下进程的换入与换出当内核，因执行某操作而发现内存不足时，比如说当一进程。由于创建了子进程，而需要更多的内存空间，
但又无足够的内存空间呢。等情况发生，便调用兑换。进程那么，它的主要任务呢，是实现内核，实现进程的换入与换出，那么进程的换出呢？兑兑换进程在实现进程的这样一个换出时，是将内存中某些进程调出至换出区，以便腾出内存空间呢？这样一个部分换出过程呢，可以分为两步，第一步呢，是选择被换出的进程，
第二个呢，是进程换出的过程。选择被换出的进程呢？兑换进程在选择被换出的进程时，将检查所有驻留在内存中的进程。首先，选择处于阻塞状态或睡眠状态的进程。当有多个这样的进程时呢？应优应当优先选择，应当选择优先级最低的进程作为换出进程。这是我们的这样一个部分，换出进程，换出过程呢，那么应当注意在选择换出进程后，对兑换对进程进行换出时，
只能换出其非共享的程序和数据段。对于那些共享的程序和数据段。呢还有进去需要它就不能被换出在进行换出的时候呢，应当申请兑换空间，若申请成功就启动磁盘。将该进程的程序和数据传送到磁盘的对话区上，若传送过程呢，未出现错误便可回收该进程所占用的内存空间，并对该进程的进程控制块和内存分配表等数据结构呢，做相应的修改。若此时的内存中还有可兑换的这样一个进程呢，便继续执行换出过程，直到内存中无阻塞进程为止，这是选择被换出的进程以及进程换出过程这两部分的过两部分的方式。我们再看一下进程的换入，
最坏进程将定时执行，换入操作。它首先查看哎PCB集合中的所有进进程的状态，从中找出就绪状态，单有换出的进程。当有许多这样的进程时，它就选择出其中呢？选择其中与换车道进程时间最久的这样一个进程呢？作为换路进程。为他申请内存，如果申请成功，可直接将内存呢进程呢从外存调入内存，如果失败，则需将内存中的某些进程换出程度足够的内存空间，再将进行调入。
那么，在兑换进程成功的换入一个进程后呢？若还有可换入的进程，则再执行换入换出过程。将其余的处于就绪且换出的状态的进程呢？进行换入，直到外存中的无无再无就绪且换出的状态的进程为止，或者已无足够的内存呢？换出进换入进程。此时呢，兑换进程呢，才停止换入，那么这是我们的换进程，换入的这样一个过程。
页:
[1]