精华内容
下载资源
问答
  • 连续分配存储管理方式

    千次阅读 2018-11-25 12:42:05
    最简单的一种存储管理方式,只能用于单用户、单任务的操作系统中。 优点:易于管理。 缺点:对要求内存空间少的程序,造成内存浪费;程序全部装入,很少使用的程序部分也占用内存。 二、固定分区分配 把内存分为一些...

    一、单一连续分配
    最简单的一种存储管理方式,只能用于单用户、单任务的操作系统中。
    优点:易于管理。
    缺点:对要求内存空间少的程序,造成内存浪费;程序全部装入,很少使用的程序部分也占用内存。

    二、固定分区分配
    把内存分为一些大小相等或不等的分区(partition),每个应用进程占用一个分区。操作系统占用其中一个分区。支持多个程序并发执行,适用于多道程序系统和分时系统。最早的多道程序存储管理方式。
    缺点:内碎片(一个分区内的剩余空间)造成浪费;划分为几个分区,便只允许几道作业并发,分区总数固定,限制并发执行的程序数目。

    三、动态分区分配
    1、分区的大小不固定:在装入程序时根据进程实际需要,动态分配内存空间,即——需要多少划分多少。
    2、空闲分区表项:从1项到n项:内存会从初始的一个大分区不断被划分、回收从而形成内存中的多个分区。
    3、优点:并发进程数没有固定数的限制,不产生内碎片。缺点:有外碎片(分区间无法利用的空间)
    4、分区分配算法
    ①首次适应算法FF(first-fit)
    空闲分区排序:以地址递增的次序链接。
    检索:分配内存时,从链首开始顺序查找直至找到一个大小能满足要求的空闲分区;
    分配:从该分区中划出一块作业要求大小的内存空间分配给请求者,余下的空闲分区大小改变仍留在空闲链中。
    若从头到尾检索不到满足要求的分区则分配失败
    优点:优先利用内存低址部分,保留了高地址部分的大空闲区;
    缺点:但低址部分不断划分,会产生较多小碎片;而且每次查找从低址部分开始,会逐渐增加查找开销。

    ②循环首次适应算法
    空闲分区排序:按地址
    检索:从上次找到的空闲分区的下一个空闲分区开始查找,直到找到一个能满足要求的空闲分区。为实现算法,需要设置一个起始查寻指针并采用循环查找方式
    分配:分出需要的大小
    优点:空闲分区分布均匀,减少查找开销
    缺点:缺乏大的空闲分区

    ③最佳适应算法
    总是把能满足要求、又是最小的空闲分区分配给作业,避免“大材小用”。
    空闲分区排序:所有空闲分区按容量从小到大排序成空闲分区表或链。
    检索:从表或链的头开始,找到的第一个满足的就分配
    分配:分出需要的大小
    缺点:每次找到最合适大小的分区割下的空闲区也总是最小,会产生许多难以利用的小空闲区(外碎片)

    ④最差适应算法/最坏匹配法
    基本不留下小空闲分区,但会出现缺乏较大的空闲分区的情况。

    ⑤快速适应算法
    根据进程常用空间大小进行划分,相同大小的串成一个链,需管理多个各种不同大小的分区的链表。进程需要时,从最接近大小需求的链中摘一个分区。
    能快速找到合适分区,但链表信息会很多;实际上是空间换时间。

    5、回收分区
    (1)回收区(首址a)与一个分区f1末尾(首址b+大小)邻接:将回收区与f1合并,修改f1的表项的分区大小
    (2)回收区(首址a+大小)与一个分区f2的首址b邻接:将回收区与f2合并,修改f2的表项的首址、分区大小
    (3) (1)(2)两种情况都有,则将回收区与前后两个分区F1、F2邻接:将三个分区合并,使用F1的表项和F1的首址,取消F2的表项,大小为三者之和
    (4) 回收区没有邻接的分区:为回收区单独建立新表项,填写回收区的首址与大小,根据其首址插到空闲链中的适当位置

    四、动态重定位分区分配——有紧凑功能的动态分区分配
    动态重定位分区分配算法与动态分区分配算法基本相同,差别在于增加了紧凑的功能

    伙伴系统
    分区大小有规定,且分区动态变化
    1、无论已分配还是空闲分区,大小都为2的k此幂。若整个可分配空间大小为2m,则1≤k≤m.
    2、随着系统运行,内存被不断划分,形成若干不连续的空闲分区。对每一类具有相同大小的空闲分区设置一双向链表,即会有k个链表,链表中的分区大小都是2m。
    3、进程申请n个大小的空间时,计算n= 2i。则找i对应的链表。若i大小的链表没有,则找i+1的链表。找到的分区对半划分后,一半用于分配,一半链接到较小一级的链表里去。
    4、一次分配和回收都可能对应多次的划分和合并。

    五、内存空间管理之对换
    当内存空间还是满足不了需求时,把内存中暂时不能运行、或暂时不用的程序和数据调到外存上,以腾出足够的内存;把已具备运行条件的进程和进程所需要的程序和数据,调入内存。
    整体对换(或进程对换):以整个进程为单位(连续分配)
    页面对换或分段对换:以页或段为单位(离散分配)

    展开全文
  • 操作系统11————存储器管理之连续分配存储管理方式 一.目录 操作系统11————存储器管理之连续分配存储管理方式 一.目录 二.概述 三.单一连续分配 四.固定分区分配 1.划分分区的方法 2....

    操作系统11————存储器管理之连续分配存储管理方式

    一.目录

    二.概述

    为了能将用户程序装入内存,必须为它分配一定大小的内存空间。连续分配方式是最早出现的一种存储器分配方式,该分配方式为吗,每一个用户程序分配一个连续的内存空间,程序中的代码或者数据的逻辑地址相邻,体现在内存空间分配物理地址的相邻。连续分配方式分为四种:单一连续分配,固定分区分配,动态分区分配,动态可重定位分区。

    三.单一连续分配

    在单道程序环境下,当时的存储器管理方式是把内存分为系统区和用户区两部分,系统区仅提供给OS使用,它通常是放在内存的低址部分。而在用户区内存中,仅装有一道用户程序,即整个内存的用户空间由该程序独占。这样的存储器分配方式被称为单一连续分配方式。

    四.固定分区分配

    出现多道程序系统后,为了能在内存中装入多道程序,且这些程序之间不会发生相互干扰,于是将整个用户空间划分为若干固定大小的区域,每个分区只装入一个作业,这就是虽早的,最简单的一种可运行多道的分区式存储管理。

    1.划分分区的方法

    可按照下面两种方法将用户空间分为若干个固定大小的分区:

    • 分区大小相等(指所有的内存分区大小相等)。缺点:缺乏灵活性,适用于一台电脑同时孔子多个相同对象的场合。
    • 分区大小不等。增加了存储器分配的灵活性

    2.内存分配

    为了便于内存分配,通常将分区按其大小进行排队,并为之建立一张分区使用表,其中各表项包括每个分区的起始地址、大小及状态(是否已分配),如下图所示。
     这里写图片描述

    当有一个用户程序要装入时,由内存分配程序依据用户程序大小检索该表,从中找出一个能满足要求的,未分配的分区,将其分配给该程序,然后将该表项中的状态为"已分配"。若未找到大小足够的分区,则拒绝为该用户分配内存。

    五.动态分区分配

    动态分区分配是根据进程的实际需求,动态地为之分配内存空间。在实现动态分区分配时,将涉及分区分配中所用的数据结构,分区分配算法和分区的分配和回收这样三方面问题。

    1.动态分区分配中的数据结构

    动态分区分配常用的两种形式:

    a.空闲分区表
    在系统中设置一张空闲分区表,用来记录每个分区的情况,每个空闲分区占一个表目。表目中包括分区号,分区大小和分区始址等数据项
    这里写图片描述
    b.空闲分区链
    为实现对空闲分区的分配和链接,在每个分区的起始部分设置一些用于控制分区分配的信息,已经用来链接各分区所用的前向指针,在分区尾部设置一向后指针,通过前,后向链接指针,可将所有的空闲链接成一个双向链表。
    这里写图片描述

    2.动态分区分配算法

    为把一个新作业装入内存,须按照一定的分配算法,从空闲分区表或空闲分区链中选出一分区分配给该作业。由于内存分配算法对系统性能有很大的影响,故人们对它进行了较为广泛而深入的研究,于是产生了许多动态分区分配算法。在后文(六.基于顺序搜索的动态分区分配算法)介绍传统的四种分配算法。在(七.基于索引搜索的动态分区分配算法)中介绍三种教新的索引搜索算法。

    3.分区分配操作

    a. 分配内存
    系统应利用某种分配算法,从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为u.size,表中每个空闲分区的大小可表示为m.size。此时操作系统分配内存如下图的流程图:
    这里写图片描述
    b. 回收内存
    当进程运行完毕释放内存时,系统根据回收区的首址,从空闲区链(表)中找到相应的插入点,此时可能出现以下四种情况之一:

    • 回收区与插入点的前一个空闲分区F1相邻接,见图(a)。此时应将回收区与插入点的前一分区合并,不必为回收分区分配新表项,而只需修改其前一分区F1的大小。
    • 回收分区与插入点的后一空闲分区F2相邻接,见图 (b)。此时也可将两分区合并,形成新的空闲分区,但用回收区的首址作为新空闲区的首址,大小为两者之和。
    • 回收区同时与插入点的前、后两个分区邻接,见图 ©。此时将三个分区合并,使用F1的表项和F1的首址,取消F2的表项,大小为三者之和。
    • 回收区既不与F1邻接,又不与F2邻接。这时应为回收区单独建立一个新表项,填写回收区的首址和大小,并根据其首址插入到空闲链中的适当位置。图4-10示出了内存回收时的流程。
      这里写图片描述

    这里写图片描述

    六.基于顺序搜索的动态分区分配算法

    为了实现动态分区分配,通常是将系统的空闲分区链接成一个链。所谓的顺序搜索,是指依次搜索空闲分区链上的空闲分区,去寻找一个其大小能够满足要求的分区。基于顺序搜索的动态分区分配算法有以下几种:首次适应算法,循环首次适应算法,最佳适应算法,最坏适应算法。

    1.首次适应算法(FF)

    以空闲分区链为例来说明采用FF算法时的分配情况。FF算法要求空闲分区链以地址递增的次序链接。在分配内存时,从链首开始顺序查找,直至找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小,从该分区中划出一块内存空间,分配给请求者,余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区,则表明系统中已没有足够大的内存分配给该进程,内存分配失败,返回。

    优点:保留了高址部分的大空闲区,为之后到达的大作业分配大的内存空间创作了条件。
    缺点:低址部分不断被划分,留下许多难以利用的,很小的分区,称为碎片。而且每次都是从头开始搜索,这就增加了空闲分区的开销。

    2.循环首次适应算法(NF)

    为避免低址部分留下许多很小的空闲分区,以及减少查找可用空闲分区的开销,循环首次适应算法在为进程分配内存空间时,不再是每次都从链首开始查找,而是从上次找到的空闲分区的下一个空闲分区开始查找,直至找到一个能满足要求的空闲分区,从中划出一块与请求大小相等的内存空间分配给作业。

    优点:该算法可以使内存中的空闲分区分布的更加均匀,从而减少了查询时间
    缺点:缺乏较大空闲分区

    3.最佳适应算法(BF)

    所谓“最佳”是指,每次为作业分配内存时,总是把能满足要求、又是最小的空闲分区分配给作业,避免“大材小用”。为了加速寻找,该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。

    优点:可以尽可能的找到最适合的内存空间
    缺点:BF算法会造成每次分配后所切割的剩余部分总是最小的,这样,在存储器中会留下许多难以利用的碎片。

    4.最坏适应算法(WF)

    由于最坏适应分配算法选择空闲分区的策略正好与最佳适应算法相反:它在扫描整个空闲分区表或链表时,总是挑选一个最大的空闲区,从中分割一部分存储空间给作业使用,以至于存储器中缺乏大的空闲分区,故把它称为是最坏适应算法。

    优点:使可剩下的空闲区不至于太小,产生碎片的可能性很小,对中小作业有利。
    缺点:缺乏较大空闲分区

    七.基于索引搜索的动态分区分配算法

    基于顺序搜索的动态分区分配算法,比较适合于不太大的系统。当系统很大时,就不适用,而一般采用的是基于搜索的动态分区分配算法。目前常用的有快速适应算法,伙伴系统和哈希算法。

    1.快速适应算法

    该算法又称为分类搜索法,是将空闲分区根据其容量大小进行分类,对于每一类具有相同容量的所有空闲分区,单独设立一个空闲分区链表,这样系统中存在多个空闲分区链表。同时,在内存中设立一张管理索引表,其中的每一个索引表项对应了一种空闲分区类型,并记录了该类型空闲分区链表表头的指针。

    该算法在搜索可分为两步,第一步,根据进程的长度,从索引表中去寻找能够容纳它的最下空闲区链表;第二步就是从链表中取出第一块进行分配即可。

    优点:不会对分区进行切割,所以不会产生碎片,也能保留较大的分区,查询速度快。
    缺点:为了有效合并分区,在分区归还主存时的算复杂,

    2.伙伴系统

    该算法规定,无论已分配分区或空闲分区,其大小均为2的k次幂(k为整数,l≤k≤m)。通常2m2^m是整个可分配内存的大小(也就是最大分区的大小)。假设系统的可利用空间容量为2m2^m 个字,则系统开始运行时,整个内存区是一个大小为2m2^m的空闲分区。在系统运行过程中,由于不断地划分,将会形成若干个不连续的空闲分区,将这些空闲分区按分区的大小进行分类。对于具有相同大小的所有空闲分区,单独设立一个空闲分区双向链表,这样,不同大小的空闲分区形成了k个空闲分区链表。

    分配:
    当需要为进程分配一个长度为n的存储空间时,首先计算一个i值,使2i1<n2i2^{i-1}< n \le 2^i,然后在空闲分区大小为2i2^i的空闲分区查找,若找到,把该空闲分区分配给进程;否则,表示长度为2i2^i的空闲分区已经耗尽,则在分区大小为2i+12^{i+1}的空闲分区链表中寻找,若存在2i+12^{i+1}的一个空闲分区,则把该空闲分区分为相等的两个分区,这两个分区称为一对伙伴,其中一个用于分配,把另一个加入到分区大小为2i2^i的空闲分区链表中。如果不存在,则查找分区大小为2i+22^{i+2},若找到,进行两次分割,第一次分割为两块2i+12^{i+1},一块用于分配,一块插入到2i+12^{i+1}的空闲分区链表中,第二次分割为两块2i2^i,一块用于分配,一块插入到2i2^i的空闲分区链表中。若仍然找不到,继续寻2i+32^{i+3},依次类推。由此可见,在最坏情况下,可能需要对2k2^k大小的空闲空间进行k次分割才能得到所需的分区。

    回收:
    于一次分配可能需要多次分割一样,一次回收也可能需要多少合并。如果回收大小为2i2^i的空闲分区时,若事先存在2i2*i的空闲分区,则应将其与伙伴分区合并为大小为2i+12^{i+1},若存在2i+12*{i+1}的空闲分区,则应将其与伙伴分区合并为大小为2i+22^{i+2},依次类推。

    3.哈希算法

    在上述的分类搜索算法和伙伴系统算法中,都是将空闲分区根据分区大小进行分类,对于每一类具有相同大小的空闲分区,单独设立一个空闲分区链表。在为进程分配空间时,需要在一张管理索引表中查找到所需空间大小所对应的表项,从中得到对应的空闲分区链表表头指针,从而通过查找得到一个空闲分区。如果对空闲分区分类较细,则相应索引表的表项也就较多,因此会显著地增加搜索索引表的表项的时间开销。

    哈希算法就是利用哈希库快速查找的优点,以及空闲分区在可利用空闲区表中的分布规律,建立哈希函数,构造一张以空闲分区大小为关键字的哈希表,该表的每一个表项记录了一个对应的空闲分区链表表头指针。

    当进行空闲分区分配时,根据所需空闲分区的大小,通过哈希函数计算,即得到在哈希表中的位置。从中得到相应的空闲分区链表,实现最佳分配策略。

    八.动态可重定位分区

    1.紧凑

    连续分配方式的一个重要特点是,一个系统或用户程序必须被装入一片连续的内存空间中。当一台计算机运行了一段时间后,它的内存空间将会被分割成许多小的分区,而缺乏大的空闲空间。即使这些分散的许多小分区的容量总和大于要装入的程序,但由于这些分区不相邻接,也无法把该程序装入内存。

    如果想把大作业装入,可采用的一种方法是:将内存中所有作业进行移动,使他们都相邻接。这样,即可把许多碎片拼接成一个大分区,这种方法称为"拼接"或者"紧凑"

    这里写图片描述

    2.动态重定位

    在上一篇博客中所介绍的动态运行时装入的方式中,作业装入内存后的所有地址仍然都是相对(逻辑)地址。而将相对地址转换为绝对(物理)地址的工作被推迟到程序指令要真正执行时进行。为使地址的转换不会影响到指令的执行速度,必须有硬件地址变换机构的支持,即须在系统中增设一个重定位寄存器,用它来存放程序(数据)在内存中的起始地址。程序在执行时,真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。

    这里写图片描述

    3.动态重定位算法

    动态重定位分区分配算法与动态分区分配算法基本上相同,差别仅在于:在这种分配算法中,增加了紧凑的功能。通常,当该算法不能找到一个足够大的空闲分区以满足用户需求时,如果所有的小的空闲分区的容量总和大于用户的要求,这时便须对内存进行“紧凑”,将经“紧凑”后所得到的大空闲分区分配给用户。如果所有的小的空闲分区的容量总和仍小于用户的要求,则返回分配失败信息。

    这里写图片描述

    九.参考资料

    《操作系统第四版》

    展开全文
  • 操作系统连续分配存储管理方式

    千次阅读 2018-07-24 20:50:15
    最简单的一种存储管理方式,但只能用于单用户、单任务的OS中。 l存储管理方法:将内存分为系统区(内存低端,分配给OS用)和用户区(内存高端,分配给用户用)。采用静态分配方式,即作业一旦进入内存,...

    连续分配方式,是指为一个用户程序分配一个连续的内存空间。

    连续分配方式的分类:

    l单一连续分配

    l固定分区分配

    l动态分区分配

    l动态重定位分区分配

    下面来看这几种分配方式

    单一连续分配

    最简单的一种存储管理方式,但只能用于单用户、单任务的OS中。

    l存储管理方法:将内存分为系统区(内存低端,分配给OS用)和用户区(内存高端,分配给用户用)。采用静态分配方式,即作业一旦进入内存,就要等待它运行结束后才能释放内存

    固定分区分配 

    固定分区分配方式是最早使用的一种可运行多道程序的存储管理方法。

    l存储管理方法

    Ø内存空间的划分:将内存空间划分为若干个固定大小的分区,除OS占一区外,其余的一个分区装入一道程序。分区的大小可以相等,也可以不等,但事先必须确定,在运行时不能改变。即分区大小及边界在运行时不能改变。

    Ø系统需建立一张分区说明表或使用表,以记录分区号、分区大小、分区的起始地址及状态(已分配或未分配)。

    l特点

    ①一个作业只能装入一个分区,当分区大小不能满足作业的要求时,该作业暂时不能装入。

    ②通过对“分区使用表”的改写,来实现主存的分配与回收。作业在执行时,不会改变存储区域,所以采用静态地址重定位方式。此方法易于实现,系统开销小。

    ③有内部碎片。

    分区总数固定,限制了并发执行的作业数目

    动态分区分配

    动态分区分配又称为可变式分区分配,是一种动态划分存储器的分区方法。

    存储管理方法

    不事先将内存划分成一块块的分区,而是在作业进入内存时,根据作业的大小动态地建立分区,并使分区的大小正好适应作业的需要。因此系统中分区的大小是可变的,分区的数目也是可变的。

    动态分区分配算法包含2种类型:l1、基于顺序搜索的动态分区分配算法。2、l基于索引搜索的动态分区分配算法。

    基于顺序搜索的动态分区分配算法

    Ø首次适应算法

       算法描述:

      空闲分区(链)按地址递增的次序排列。在进行内存分配时,从空闲分区表/链首开始顺序查找,直到找到第一个满足其大小要求的空闲分区为止。然后再按照作业大小,从该分区中划出一块内存空间分配给请求者,余下的空闲分区仍留在空闲分区表(链)中。

     

    Ø循环首次适应算法

       算法描述:

      循环首次适应算法又称为下次适应算法,由首次适应算法演变而来。在为作业分配内存空间时,不再每次从空闲分区表/链首开始查找,而是从上次找到的空闲分区的下一个空闲分区开始查找,直到找到第一个能满足其大小要求的空闲分区为止。然后,再按照作业大小,从该分区中划出一块内存空间分配给请求者,余下的空闲分区仍留在空闲分区表/中。

    Ø最佳适应算法

       算法描述:

      空闲分区表/链按容量大小递增的次序排列。在进行内存分配时,从空闲分区表/链的首开始顺序查找,直到找到第一个满足其大小要求的空闲分区为止。

    Ø最坏适应算法

      算法描述:

      空闲分区表/链按容量大小递减的次序排列。在进行内存分配时,从空闲分区表/链的首开始顺序查找,直到找到第一个比之大的空闲分区为止。剩下的空闲仍留在空闲分区表/链中。

    基于索引搜索的动态分区分配算法

    基于顺序搜索动态分区分配算法,适用于不太大的系统。系统很大时:1.内存分区很多。2.空闲分区链很长。3.顺序搜索方法很慢。

    l基于索引搜索的动态分区分配算法常用的:

    快速适应算法(也叫分类搜索法(quick fit))

    该算法又称为分类搜索法,是将空闲分区根据其容量大小进行分类,对于每一类具有相同容量的所有空闲分区,单独设立一个空闲分区链表,这样系统中存在多个空闲分区链表。在内存中设立一张管理索引表,其中的每一个索引表项对应了一种空闲分区类型,并记录了该类型空闲分区链表表头的指针。

    伙伴系统

    伙伴系统规定:无论已分配分区或空闲分区,其大小均为2K次幂,K为整数l≦k≦m,其中:2l表示分配的最小分区的大小,2m表示分配的最大分区的大小。

    伙伴关系:初始内存是一个大小为2m的空闲分区,分区可以对半分割,分区大小均为2 k次幂。若申请长度为n的内存空间,计算一个i值使2i-1<n≤2i,在空闲分区大小为2i的空闲分区链表中查找。若找到,把该空闲分区分配。否则,2i长度空闲分区已经耗尽。则在2i+1的空闲分区链表中查找。若存在2i+1的空闲分区,则把该空闲分区分为相等的两个分区,这两个分区为一对伙伴。其中的一个分区用于分配,而把另一个加入分区大小为2i的空闲链表中,若大小为2i+1的空闲分区也不存在,则查找大小为2i+2的空闲分区,若找到也对其进行两次分割

    希算法

    算法描述:

     利用哈希快速查找的优点,以及空闲分区在可利用空间表中的分布规律,建立哈希函数,构造一张以空闲分区大小为关键字的哈希表,该表的每一个表项记录了一个对应的空闲分区链表表头指针。当进行空闲分区分配时,根据所需空闲分区的大小,通过哈希函数计算,得到相应的空闲分区链表,实现最佳分配策略。

    动态重定位分区分配

    动态重定位分区分配算法与动态分区分配算法基本上相同,差别仅在于:在这种分配算法中,增加了紧凑的功能。通常,当该算法不能找到一个足够大的空闲分区以满足用户需求时,如果所有的小的空闲分区的容量总和大于用户的要求,这时便须对内存进行“紧凑”,将经“紧凑”后所得到的大空闲分区分配给用户。如果所有的小的空闲分区的容量总和仍小于用户的要求,则返回分配失败信息。

    动态重定位的实现

    l在动态运行时装入的方式,将相对地址转换为物理地址的工作在程序指令真正要执行时才进行。地址转换需要重定位寄存器的支持。程序执行时访问的内存地址是相对地址与重定位寄存器中的地址相加而成。

    l地址变换过程是在程序执行过程期间,随着对每条指令的访问自动进行的,称为动态重定位。

      真正访问地址=相对地址+重定位寄存器中地址。

    展开全文
  • 连续分配方式(分区技术) :指为一个用户程序分配一片连续的内存空间。静态分区:作业装入时一次完成,分区大小及边界在运行时不能改变。动态分区:根据作业大小动态地建立分区,分区的大小、数目可变。连续分配...

    连续分配方式(分区技术) :指为一个用户程序分配一片连续的内存空间。

    静态分区:作业装入时一次完成,分区大小及边界在运行时不能改变。

    动态分区:根据作业大小动态地建立分区,分区的大小、数目可变。

    连续分配方式(分区技术)

    • 单一连续分区分配(静态分区技术) :仅用于单用户单任务系统
    • 固定分区分配(静态分区技术) :可用于多道系统
    • 动态分区分配(动态分区技术)
    • 动态可重定位分区分配(动态分区技术) :引入了动态
    • 重定位和内存紧凑技术
    • 伙伴系统(动态分区技术)

    单一连续分区分配

    存储管理方法:将内存分为系统区(内存低端,分配给OS 用)和用户区(内存高端,分配给用户用) 。

    采用静态分配方式,即作业一旦进入内存,就要等待它运行结束后才能释放内存。

    最简单的一种存储管理方式,但只能用于单用户、单任务的 OS 中。

    主要特点:管理简单,只需少量的软件和硬件支持,便于用户了解和使用。但因内存中只装入一道作业运行,内存空间浪费大,各类资源的利用率也不高。

    一个容量为 256KB 的内存,操作系统占用 32KB,剩下224KB 全部分配给用户作业,如果一个作业仅需64KB,那么就有 160KB 的存储空间被浪费。

    图示

    固定分区分配方式

    固定分区分配方式是最早使用的一种可运行多道程序的存储管理方法。
    存储管理方法:将内存空间划分为若干个固定大小的分区,除 OS 占一区外,其余的一个分区装入一道程序。分区的大小可以相等,也可以不等,但事先必须确定,在运行时不能改变。即分区大小及边界在运行时不能改变。
    系统需建立一张分区说明表或使用表,以记录分区号、分区大小、分区的起始地址及状态(已分配或未分配) 。

    图示

    划分分区的方法

    分区大小相等
    用于利用一台计算机去控制多个相同对象的场合。缺点是缺乏灵活性。

    分区大小不等
    把内存区划分成含有多个较小的分区、适量的中等分区及少量的大分区。

    内存分配

    当某个用户程序要装入内存时,通常将分区按大小进行排队,由内存分配程序检索分区说明表,从表中找出一个满足要求的尚未分配的分区分配该程序,同时修改说明表中相应分区的状态;若找不到大小足够的分区,则
    拒绝为该程序分配内存。
    程序执行完毕,释放占用的分区,管理程序修改说明表中相应分区的状态为未分配,实现内存资源的回收。
    主要特点:管理简单,但因作业的大小并不一定与某个分区大小相等,从而使一部分存储空间被浪费。所以主存的利用率不高。

    例:在某系统中,采用固定分区分配管理方式,内存分区(单位:字节)情况如图所示,现有大小为 1K、9K、33K、121K 的多个作业要求进入内存。

    图示

    根据分区说明表,将 4 个分区依次分配给 4 个作业,同时修改分区说明表,其内存分配和分区说明表如下所示:

    图示

    动态分区分配方式(可变分区分配)

    • 动态分区分配是一种动态划分存储器的分区方法。
    • 存储管理方法
      1. 内存不是预先划分好的,作业装入时,根据作业的需求和内存空间的使用情况来决定是否分配。
      2. 若有足够的空间,则按需要分割一部分分区给该进程;否则令其等待内存空间。
    • 主要特点:管理简单,只需少量的软件和硬件支持,便于用户了解和使用,主存的利用率有所提高。

    例:一个计算机有 2560K 内存,采用可变分区模式管理内存,操作系统占用低地址的 400K 空间,剩余 2160K 的空间为用户区。

    最初整个用户区是空闲的,只有一个分区。然后随着用户程序的创建和撤销。分区的个数和大小位置开始变化。

    图示

    图示

    动态分区分配中的数据结构

    空闲分区表:用来登记系统中的空闲分区(分区号、分区起始地址、分区大小及状态) 。

    空闲分区链:
    前、后向链接指针用于把所有的空闲分区链接成一个双向链。当分区被分配出去以后,前、后向指针无意义。

    状态位 0:未分配
    状态位 1:已分配

    图示

    分区分配操作(分配内存)

    系统利用某种分配算法,从空闲分区表/链中找到所需大小的分区。

    分配内存

    • 事先规定 size 是不再切割的剩余分区的大小。
    • 设请求的分区大小为 u.size,空闲分区的大小为m.size。
    • 若 m.size-u.size≤size,将整个分区分配给请求者。
    • 否则,从该分区中按请求的大小划分出一块内存空间分配出去,余下的部分仍留在空闲分区表/链中。

    图示

    分区分配操作(回收内存)

    • 回收分区上邻接一个空闲分区,合并后首地址为空闲分区的首地址,大小为二者之和。
    • 回收分区下邻接一个空闲分区,合并后首地址为回收分区的首地址,大小为二者之和。
    • 回收分区上下邻接空闲分区,合并后首地址为上空闲分区的首地址,大小为三者之和。
    • 回收分区不邻接空闲分区,这时在空闲分区表中新建一表项,并填写分区大小等信息。

    图示

    动态分区分配算法

    基于顺序搜索的动态分区分配算法

    • 首次适应算法(First Fit)
    • 循环首次适应算法(Next Fit)
    • 最佳适应算法(Best Fit)
    • 最坏适应算法(Worst Fit)

    基于索引搜索的动态分区分配算法

    • 快速适应算法(Quick Fit)
    • 伙伴系统(Buddy system)
    • 哈希算法

    基于顺序搜索的动态分区分配算法

    按照一定的分配算法从空闲分区表(链)中选出一个满
    足作业需求的分区分割,一部分分配给作业,剩下的部分仍
    然留在空闲分区表(链)中,同时修改空闲分区表(链)中
    相应的信息。

    首次适应算法

    空闲分区(链)按地址递增的次序排列。
    在进行内存分配时,从空闲分区表/链首开始顺序查找,直到找到第一个满足其大小要求的空闲分区为止。
    然后再按照作业大小,从该分区中划出一块内存空间分配给请求者,余下的空闲分区仍留在空闲分区表(链)中。

    例:系统中的空闲分区表如下表示,现有三个作业分配申请内存空间 100K、30K 及 7K,给出按首次适应算法的内存分配情况及分配后空闲分区表。

    图示

    按首次适应算法,申请作业 100k,分配 3 号分区,剩下分区为 20k,起始地址 160K ;申请作业 30k,分配 1 号分区,剩下分区为 2k,起始地址 50K ;申请作业 7k,分配 2 号分区,剩下分区为 1k,起始地址59K。

    图示

    首次适应算法的特点:优先利用内存低地址部分的空闲分区。但由于低地址部分不断被划分,留下许多难以利用的很小的空闲分区(碎片或零头) ,而每次查找又都是从低地址部分开始,增加了查找可用空闲分区的开销。

    循环首次适应算法

    循环首次适应算法又称为下次适应算法,由首次适应算法演变而来。在为作业分配内存空间时,不再每次从空闲分区表/链首开始查找,而是从上次找到的空闲分区的下一个空闲分区开始查找,直到找到第一个能满足其大小要求的空闲分区为止

    然后再按照作业大小,从该分区中划出一块内存空间分配给请求者,余下的空闲分区仍留在空闲分区表(链)中。

    例:系统中的空闲分区表如下表示,现有三个作业分配申请内存空间 100K、30K 及 7K,给出按循环首次适应算法的内存分配情况及分配后空闲分区表。

    图示

    按循环首次适应算法,申请作业 100k,分配 3 号分区,剩下分区为20k,起始地址 160K;申请作业 30k,分配 4 号分区,剩下分区为301k,起始地址 210K ;申请作业 7k,分配 1 号分区

    图示

    循环首次适应算法的特点:使存储空间的利用更加均衡,不致使小的空闲区集中在存储区的一端,但这会导致缺乏大的空闲分区。

    最佳适应算法

    空闲分区表/链按容量大小递增的次序排列。在进行内存分配时,从空闲分区表/链首开始顺序查找,直到找到第一个满足其大小要求的空闲分区为止。

    按这种方式为作业分配内存,就能把既满足作业要求又与作业大小最接近的空闲分区分配给作业。将剩余空闲分区仍留在空闲分区表/链中。第一次找到的能满足要求的空闲区必然是最佳的。

    例:系统中的空闲分区表如下表示,现有三个作业分配申请内存空间 100K、30K 及 7K,给出按最佳适应算法的内存分配情况及分配后空闲分区表。

    图示

    图示

    图示

    最佳适应算法的特点:若存在与作业大小一致的空闲分区,则它必然被选中,若不存在与作业大小一致的空闲分区,则只划分比作业稍大的空闲分区,从而保留了大的空闲分区。最佳适应算法往往使剩下的空闲区非常小,从而在存储器中留下许多难以利用的小空闲区(碎片) 。

    最坏适应算法

    空闲分区表/链按容量大小递减的次序排列。在进行内存分配时,从空闲分区表/链首开始顺序查找,直到找到第一个满足其大小要求的空闲分区为止。总是挑选一个最大的空闲区分割给作业使用,其优点是可使剩下的空闲区不至于太小,产生碎片的几率最小,对中、小作业有利。

    例:系统中的空闲分区表如下表示,现有三个作业分配申请内存空间 100K、30K 及 7K,给出按最佳适应算法的内存分配情况及分配后空闲分区表。

    图示

    图示

    图示

    最坏适应算法的特点:总是挑选满足作业要求的最大的分区分配给作业。这样使分给作业后剩下的空闲分区也较大,可装下其它作业。由于最大的空闲分区总是因首先分配而划分,当有大作业到来时,其存储空间的申请往往会得不到满足。

    基于索引搜索的动态分区分配算法

    基于顺序搜索的动态分区分配算法一般只是适合于较小的系统,如果系统的分区很多,空闲分区表(链)可能很大(很长) ,检索速度会比较慢。为了提高搜索空闲分区的速度,大中型系统采用了基于索引搜索的动态分区分配算法。

    快速适应算法

    快速适应算法,又称为分类搜索法,把空闲分区按容量大小进行分类,经常用到长度的空闲区设立单独的空闲区链表。系统为多个空闲链表设立一张管理索引表。
    优点是查找效率高,仅需要根据进程的长度,寻找到能容纳它的最小空闲区链表,取下第一块进行分配即可。
    该算法在分配时,不会对任何分区产生分割,所以能保留大的分区,也不会产生内存碎片。
    缺点是在分区归还主存时算法复杂,系统开销较大。在分配空闲分区时是以进程为单位,一个分区只属于一个进程,存在一定的浪费。空间换时间。

    伙伴系统

    固定分区方式不够灵活,当进程大小与空闲分区大小不匹配时,内存空间利用率很低。
    动态分区方式算法复杂,回收空闲分区时需要进行分区合并等,系统开销较大。
    伙伴系统 (buddy system)是介于固定分区与可变分区之间的动态分区技术。
    伙伴:在分配存储块时将一个大的存储块分裂成两个大小相等的小块,这两个小块就称为“伙伴” 。

    图示

    伙伴系统的内存分配

    图示

    图示

    伙伴系统的内存释放

    图示

    图示

    图示

    图示

    哈希算法

    哈希函数(Hash) ,也叫散列函数,是把任意长度的输入通过散列算法,变换成固定长度的输出,该输出就是散列值。

    哈希既是一种查找技术,也是一种存储技术。可以用哈希函数建立从关键字空间到存储地址空间的映射。

    若关键字为 k,计算出 Hash 函数值 Hash(k),把这个值(Hash 地址)存储为一个线性表,称为散列表或哈希表。

    查找时,对于给定关键字,求哈希值,然后直接在哈希表中取得所查记录。 (不必顺序查表,查找速度比较快)

    • 哈希函数是一种单向密码体制,即它是一个从明文到密文的不可逆映射,只有加密过程,没有解密过程。
    • 哈希函数可用于文件校验和数字签名。
    • 哈希函数的构造
      1. 哈希函数应是一个压缩映像函数,应具有较大的压缩性以节省存储空间。
      2. 哈希函数应具有较好的散列性,以尽量减少冲突(collision)现象的出现。
    • 冲突:不同的关键字可能得到相同的哈希值。即

    图示

    上述的分类搜索算法和伙伴系统算法中,都是将空闲分区根据分区大小进行分类,对于每一类具有相同大小的空闲分区,单独设立一个空闲分区链表。

    哈希算法:构造一张以空闲分区大小为关键字的哈希表,该表的每一个表项记录了一个对应的空闲分区链表表头指针。

    进行空闲分区分配时,根据所需空闲分区大小,通过哈希函数得到在哈希表中的位置,从中得到相应的空闲分区链表的表头指针。

    系统中的碎片

    内存中无法被利用的存储空间称为碎片。

    内部碎片:指分配给作业的存储空间中未被利用的部分,如固定分区中存在的碎片。

    单一连续区存储管理、固定分区存储管理、分页式存储管理和请求页式存储管理都会出现内部碎片。

    外部碎片:指系统中无法利用的小的空闲分区。如分区与分区之间存在的碎片。这些不连续的区间就是外部碎片。

    内部碎片无法被整理,但作业完成后会得到释放。它们其实已经被分配出去了,只是没有被利用。

    外部碎片才是造成内存系统性能下降的主要原因。外部碎片可以被整理后清除。

    另一种浪费内存的方式是额外开销(Overhead) 。Overhead:内存头,记录一些分配信息以便释放内存。

    动态可重定位分区分配用到的技术

    紧凑技术(Compaction)

    通过移动作业从把多个分散的小分区拼接成一个大分区的方法称为紧凑(拼接或紧缩) 。

    目标:消除外部碎片,使本来分散的多个小空闲分区连成一个大的空闲区。

    紧凑时机:找不到足够大的空闲分区且总空闲分区容量可以满足作业要求时。

    动态重定位:作业在内存中的位置发生了变化,这就必须对其地址加以修改或变换。

    图示

    动态重定位的实现

    图示

    动态可重定位分区分配算法

    在分区存储管理方式中,必须把作业装入到一片连续的内存空间。如果系统中有若干个小的分区,其总容量大于要装入的作业,但由于它们不相邻接,也将致使作业不能装入内存。

    动态可重定位分区分配相当于引入了动态重定位和内存紧凑技术的动态分区分配。

    图示

    分区的存储保护

    存储保护是为了防止一个作业有意或无意地破坏操作系统或其它作业。常用的存储保护方法有:

    界限寄存器方法:

    • 上下界寄存器方法
    • 基址、限长寄存器 (BR,LR) 方法

    存储保护键方法:给每个存储块分配一个单独的保护键,它相当于一把锁。进入系统的每个作业也赋予一个保护键,它相当于一把钥匙。当作业运行时,检查钥匙和锁是否匹配,如果不匹配,则系统发出保护性中断信号,停止作业运行。

    图示

    展开全文
  • 快速了解 连续分配方式存储管理

    千次阅读 2018-01-28 12:18:45
    采用这: 种存储管理方式时,可把内存分为系统区和用户区两部分,系统区仅提供给OS使用,通常是放在内存的低址部分;用户区是指除系统区以外的全部内存空间,提供给用户使用。 (2)固定分区分配:最简单的一种可...
  • 连续分配存储的四种管理方式

    千次阅读 2020-04-19 21:47:04
    连续分配存储的四种管理方式 连续分配方式指为一个用户程序分配给一个连续的内存空间 单一连续分配 原理:将内存分为用户区和系统区,每次运行时,都将整个用户区分配给当前执行的一道作业 固定分区分配 原理:将...
  • 在前面的博客中提到了连续分配方式。 本文主要是描述离散分配方式中的基本分页式存储管理。 为什么引入? 在连续分配方式中,内存分配...如果离散分配方式的基本单位是页,就称为分页存储管理方式;还有一种基本...
  • 3.1.3连续分配管理方式

    千次阅读 2016-07-15 20:25:55
    连续分配方式,是指为一个用户程序分配一个连续的内存空间。它主要包括单一连续分配、固定分区分配和动态分区分配。 1、单一连续分配 内存在此方式下分为系统区和用户区,系统区仅提供给操作系统使用,通常在低地址...
  • 分页存储管理方式

    万次阅读 2017-04-20 21:11:57
    连续分配存储管理方式产生的问题: 要求连续的存储区碎片问题 变连续分配为离散分配,允许将作业离散放到多个不相邻接的分区中。 分页式存储管理:离散分配的基本单位是页分段式存储管理:离散分配的基本...
  • 【操作系统】分页存储管理方式

    万次阅读 多人点赞 2016-12-12 21:16:25
    离散分配方式连续分配存储管理方式产生的问题: 要求连续的存储区 碎片问题 变连续分配为离散分配,允许将作业离散放到多个不相邻接的分区中。 分页式存储管理:离散分配的基本单位是页 分段式存储管理:离散分配的...
  • 内存管理之连续分配管理方式

    千次阅读 2018-04-01 13:03:23
    连续分配管理方式 连续分配方式是指为一个用户程序分配一个连续的内存空间。通俗地说,就是给内存划格子(格子中都是一个进程,和非连续分配管理方式相对)。(1)单一连续分配 将内存分为系统区和用户区,内存中...
  • 基本分页存储管理方式

    万次阅读 多人点赞 2018-07-26 20:16:41
    连续分配存储管理方式产生的问题 在分区存储管理中,要求把进程放在一个连续的存储区中,因而会产生许多碎片。 碎片问题的解决方法 (1)拼接/紧凑技术----代价较高。 (2)离散分配方式---允许将作业/进程离散...
  • 4.内存非连续分配管理方式

    千次阅读 2016-04-17 17:00:38
    连续分配允许一个程序分散地装入到不相邻的内存分区中,根据分区的大小是否固定分为分页存储管理方式和分段存储管理方式。 分页存储管理方式中,又根据运行作业时是否要把作业的所有页面都装入内存才能运行分为...
  • 连续分配方式允许将一个程序分散地装入不连续的内存空间。在连续分配管理方式中,即使内存有超过2GB的存储空间,但是没有连续的2GB内存空间,则需要2GB内存空间的作业仍然无法装入内存运行 ...
  • 内存管理之非连续分配管理方式

    千次阅读 2016-02-15 11:49:35
    内存管理之非连续分配管理方式基本分页储存管理方式进程会被固定单位的空间划分成块,一个块称之为页(Page),内存也被这个单位划分成块,一个块称之为页框(Page Frame),外存也以同样单位划分成块,称之为块...
  • 存储管理的离散分配方式

    千次阅读 2018-12-07 19:01:33
    基本分段存储管理方式 分段系统的基本原理 段表与地址变换机构 ★分页与分段的主要区别 段页式存储管理方式 基本原理 地址变换过程 存储管理的离散分配方式 页面的概念 页表的概念 地址的处理 连续...
  • 3.内存连续分配管理方式

    千次阅读 2016-03-29 11:14:23
    连续分配方式,是指为一个用户程序分配一个连续的内存空间。它主要包括单一连续分配、固定分区分配和动态分区分配。 单一连续分配 内存在此方式下分为系统区和用户区,系统区仅提供给操作系统使用,通常在低地址...
  • 连续分配方式,是指为一个用户程序分配一个连续的内存空间。它主要包括单一连续分配、固定分区分配和动态分区分配。 1单一连续分配 内存在此方式下分为系统区和用户区,系统区仅提供给操作系统使用,通常在低地址...
  • 连续存储管理

    千次阅读 2018-06-23 13:54:54
    连续存储管理⎧⎩⎨单一连续存储管理固定分区存储管理可变分区存储管理连续存储管理{单一连续存储管理固定分区存储管理可变分区存储管理连续存储管理 \begin {cases} 单一连续存储管理\\ 固定分区存储管理\\ 可变...
  • 分段存储管理方式

    千次阅读 2019-03-31 11:31:22
    分段存储管理方式(已成为当今所有存储管理方式的基础) 分段存储管理方式的引入 为了满足以下需要 方便编程 信息共享 信息保护 (数据段)动态增长 动态链接(以段作为基本单位链接) 基本原理 分段地址结构...
  • 分页存储存储管理方式详解

    千次阅读 多人点赞 2020-04-22 21:38:18
    分页存储存储管理方式详解离散分配方式分页储存管理方式页面与页表页面物理块逻辑地址结构页表快表(TLB,Translation Look aside Buffer)一级页表的缺陷两级多级页表反置页表反置页表的提出基于反置页表的地址转换...
  • 一、外存分配方式 二、储空间管理
  • 操作系统内存管理内存空间的连续分配方式1.概述、分类内存空间的连续分配方式,是指为一个用户程序(作业)分配一个连续的内存空间。 按照内存空间划分方式的不同可将连续分配方式划分为以下四种方式: 1. 单一...
  • 操作系统中存储管理的基本原理

    千次阅读 2014-09-03 09:31:13
    存储管理的基本原理 ...1.连续分配存储管理方式 连续分配是指为一个用户程序分配连续的内存空间。连续分配有单一连续存储管理和分区式储管理两种方式。 (1)单一连续存储管理 在这种管理方式
  • 分页存储管理方式介绍及例题

    千次阅读 2020-03-17 14:45:38
    一、引入  在存储器管理中连续...基于这一思想便产生了离散分配方式,根据在离散分配时所分配地址空间的基本单位不同,又可将离散分配方式分为以下三种:(1)分页存储管理方式(2)分段存储管理方式(3)段页式...
  • 3.1.4.1 基本分页存储管理方式

    千次阅读 2016-07-13 23:58:02
    连续分配允许一个程序分散地装入到不相邻的内存分区中,根据分区的大小是否固定分为分页存储管理方式和分段存储管理方式。 分页存储管理方式中,又根据运行作业时是否要把作业的所有页面都装入内存才能运行分为...
  • 存储管理的基本原理 ...1.连续分配存储管理方式 连续分配是指为一个用户程序分配连续的内存空间。连续分配有单一连续存储管理和分区式储管理两种方式。 (1)单一连续存储管理 在这种管理方式
  • 分页存储管理方式——初解

    千次阅读 2017-08-02 14:23:34
    一、连续分配方式缺点 连续分配方式的主要缺点是会形成许多碎片,尽管我们可以通过紧凑的方法将碎片拼接成可用的大块空间,但这样须付出很大的代价。 二、离散分配方式 ...基本的分页存储管理方式
  • 分页存储管理方式附网易校招笔试题

    万次阅读 多人点赞 2017-05-03 14:18:47
    一、连续分配方式缺点连续分配方式的主要缺点是会形成许多碎片,尽管我们可以通过紧凑的方法将碎片拼接成可用的大块空间,但这样须付出很大的代价。 二、离散分配方式离散分配方式思想:将进程直接分散地装入到许多...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 139,724
精华内容 55,889
关键字:

连续分配存储管理方式