加载中…
个人资料
汤圆爱红豆
汤圆爱红豆
  • 博客等级:
  • 博客积分:0
  • 博客访问:2,105
  • 关注人气:4
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
谁看过这篇博文
加载中…
正文 字体大小:

学习笔记--操作系统 存储器管理2

(2014-11-29 12:13:59)
标签:

it

如何内存分配?


1.单一连续分配:只能用于单用户、单任务的操作系统中。采用这种存储方式时,可以把内存分为系统区和用户区两部分,系统区即提供给OS使用,通常是放在内存的低地址部分;用户区是指除系统区以外的全部内存空间,提供给用户使用。


2.固定分区分配:是最简单的一种可运行多道程序的存储管理方式。这是将内存用户空间划分为若干个固定大小的区域,在每个分区中只装入一道作业,这样,把用户空间划分为几个分区,便允许有几道作业并发运行。当有一空闲分区时,便可以再从外存的后备作业队列中找出另一作业调入该分区。


划分分区的方法1.分区大小相等 2.分区大小不相等(把内存区划分成含有多个较小的分区、适量的中等分区及少量的大分区。)


内存分配:通常将分区按大小进行排队,并为之建立一张分区使用表,其中各表项包括每个分区的起始地址、大小及状态(是否已分配)。当有一用户程序要装入时,由内存分配程序检索该表、从中找出一个能满足要求的、尚未分配的分区,将之分配给该程序,然后将该表项中的状态置为已分配;若未找到大小足够的分区,则拒绝为该用户程序分配内存。


3.动态分区分配

为什么要动态分区分配?

最重要的原因是经常直到程序实际运行时,它们才知道某些数据结构的大小。


分区分配中的数据结构:


1.空闲分区表:用于记录每个空闲分区的情况。每个空闲分区占一个表目,表目中包括分区序号、分区起始及分区的大小等数据项。


2.空闲分区链:为了实现对空闲分区的分配和链接,在每个分区的起始部分,设置了一些用于控制分区分配的信息,以及用于链表各分区所用的前向指针;在分区尾部则设置一后向指针,通过前、后向链表指针,可将所有的空闲分区链接成一个双向链。


动态分区分配的要求和目标:


1.处理任意请求序列:一个应用可以有任意的分配请求和释放请求序列,只要满足约束条件:每个释放请求必须对应于一个当前已分配块,这个块是由一个以前的分配请求获得的:因此,分配器不可以假设分配和释放请求的顺序。


2.立即响应请求


3.只使用堆:分区分配必须对齐块,使得可以保存任何类型的数据对象


4.不修改已分配的块:只能对空闲块进行操作或者改变。特别是,一旦空闲块被分配了,就不允许修改或者移动它了。因此,诸如压缩已分配块这样的技术是不允许使用的。


碎片:当虽然有未使用的空闲区但不能用来满足分配请求时,就会发生这种现象

有两种形式的碎片:内部碎片和外部碎片


内部碎片:在一个已分配块中存在未使用的空闲区,有些是因为分区是为了满足对齐块的要求而浪费了一些空闲区。


外部碎片:当空闲区合计起来足够满足一个分配请求,但是没有一个单独的空闲块足够大可以来处理这个请求时发生的。


如何找到空闲分区?


分区分配的算法


1.首次适应算法

要求空闲分区链以地址递增的次序链接。在分配内存时,从链首开始顺序查找,直至找到一个大小能满足要求的空闲分区为止;然后再按照作业的大小,从该分区中划出一块内存空间分配给请求者,余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区,则此次内存分配失败,返回。


该算法倾向于优先利用内存中低址部分的空闲分区,从而保留了高址部分的大空闲区。这给以后到达的大作业分配大的内存空间创造了条件

其缺点是低址部分不断被划分,会留下许多难以利用的、很小的空闲分区,而每次查找又都是从低址部分开始,这无疑会增加可用空闲分区时的开销。

 

2.循环首次适应算法

在为进程分配内存空间时,不再是每次都从链首开始查找,而是从上次找到的空闲分区的下一个空闲分区开始查找,直至找到一个能满足要求的空闲分区,从中划出一块与请求大小相等的内存空间分配给作业。为实现该算法,应设置一起始查询指针,用于指示下一次起始查寻的空闲分区,并采用循环查找方式,即如果最后一个(链尾)空闲分区的大小仍不能满足要求,则应返回到第一个空闲分区,比较其大小是否满足要求。找到后,应调整起始查寻指针。


该算法能使内存中的空闲分区分布得更均匀,从而减少了查找空闲分区时的开销

但这样会缺乏大的空闲分区


3.最佳适应算法

要求将所有的空闲分区按其容量以小到大的顺序形成一空闲分区链。这样,第一次找到的能满足要求的空闲区,必然是最佳的


孤立地看,最佳适应算法似乎是最佳的,然而在宏观上却不一定。因为每次分配后所切割下来的剩余部分总是最小的,这样,在存储器中会留下许多难以利用的小空闲区


4.最坏适应算法

要扫描整个空闲分区表或链表,总是挑选一个最大的空闲区分割给作业使用,其优点是可剩下地空闲区不至于太小,产生碎片地几率非常小,对中、小作业有利,同时最坏适应算法查找效率很高。

该算法要求将所有的空闲分区按其容量以从大到小地顺序形成一个空闲分区链,查找时只要看第一个分区能否满足作业要求。但是该算法的缺点也是明显地,它会使存储器中缺乏大的空闲分区。


最坏适应算法与前面所述地首次适应算法、循环首次适应算法、最佳适应算法一起,也称为顺序搜索法。


5.快速适应算法(分类搜索法)

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


优点:查找效率高,仅需要根据进程的长度,寻找到能容纳它的最小空闲区链表,并取下第一块进行分配即可。另外该算法在进行空闲分区分配时,不会对任何分区产生分割,所以能保留大的分区,满足对大空间的需求,也不会产生内存碎片

缺点:在分区归还主存时算法复杂,系统开销较大。此外,该算法在分配空闲分区是以进程为单位,一个分区只属于一个进程,因此在为进程所分配的一个分区中,或多或少地存在一定的浪费。

快速适应算法中,空闲分区划分越细,浪费则越严重,整体上会造成可观的存储空间浪费,这是典型的以空间换时间的做法。


找到空闲分区后,如何使用空闲分区?


一旦找到一个匹配的空闲块,就需要做一个策略决定——分配这个空闲块中多少空间。


1.选择用整个空闲块:这种方式简单而快捷,但是主要缺点就是它会造成内部碎片。

2.分为两部分,一部分为分配块,剩下的部分为新的空闲块

 

如果,不能为请求块找到适合的空闲块。首先会合并那些在存储器中物理上相邻的空闲快来创建一些更大的空闲块。如果合并后还是不能生成一个足够大的块,或者说如果空闲块已经最大程度地合并了,那么就可以向内核请求额外的堆存储器。

 

空闲分区使用完毕后,怎么办?


当释放一个已分配块时,可能有其他空闲块与这个新释放的空闲块相邻。合并就是合并相邻的空闲块的过程。


何时合并?

1.立即合并:每次一个块被释放时,就合并所有的相邻块(可能会造成抖动:块反复地合并,然后马上分割)

2.推迟合并:等到某个稍晚的时候再合并空闲块。

 

如何合并?

 

带边界标记的合并:允许在常数时间内进行对前面块的合并。

学习笔记--操作系统 <wbr>存储器管理2

合并当前块时可能出现的情况


1.前面的块是已分配的,后面的块也是已分配的

2.前面的块是空闲的,后面的块是已分配的。

3.前面的块是已分配的,后面的块是空闲的。

4.前面的和后面的块都是空闲的。


情况1:两个邻接的块都是已分配的,因此不可能进行合并,所以只是简单地将当前块的状态丛已分配变成空闲。


情况2:将前面的块和当前块进行合并。用前面的块和当前块的大小和来更新前面块的头部和当前块的脚部,然后前面的块和当前的块就合并成一个快啦。

学习笔记--操作系统 <wbr>存储器管理2


情况3:将当前的块和后面的块进行合并。用当前的块和后面的块的大小纸鹤来更新当前块的头部和后面块的脚部。

学习笔记--操作系统 <wbr>存储器管理2

 

情款4:将前面的块、当前块和后面的块进行合并。用这三个块的大小来更新前面块的头部和后面块的脚部。

学习笔记--操作系统 <wbr>存储器管理2

人们想到用带边界标记的合并是为了用常数级的时间复杂度来替代来解决每次调用free需要的时间与堆的大小呈线性级的时间复杂度的问题。虽然时间复杂度得到了提高,但是也多占据了一些空间。


然后人们又想到一种边界标记的优化方法。能够使得在已分配块中不再需要脚部因为只有在前面的块是空闲,后面的块是已分配的时候,才需要用到当前已分配块的脚部。如果我们把当前块的已分配/空闲位存放在当前块中多出来的低位中,那么已分配的块就不需要脚部了,这样我们就可以多利用这个多出来的空间了。当然空闲块仍然需要脚部


 

存储器映射:


通过将虚拟存储器区域与一个磁盘上的对象关联起来,以初始化这个虚拟存储器区域的内容,这个过程称为存储器映射


虚拟页面总数=内存页面数+页面数(磁盘交换空间)


一个对象可以被映射到虚拟存储器的一个区域,要么作为共享对象,要么作为私有对象


如果一个进程将一个共享对象映射到它的虚拟地址空间的一个区域内,那么这个进程对这个区域的任何写操作,对于那些也把这个共享对象映射到它们虚拟存储器的其他进程而言也是可见的。而对一个映射私有对象的区域做的改变,对于其他进程来说是不可见的

 

写时复制:比如说,两个进程将一个私有对象映射到它们虚拟存储器的不同区域,但是共享这对象同一物理拷贝。对于每个映射私有对象的进程,相应私有区域的页表条目都被标记为只读,并且区域结构被标记为私有的写时拷贝。只要没有进程试图写它自己的私有区域,它们就可以继续共享物理存储器中对象的一各单独拷贝。然而,只要有一个进程试图写私有区域内的某个页面,那么这个写操作就会触发一个保护故障


当故障处理程序注意到保护异常是由于进程试图写私有的写时拷贝区域中的一个页面而引起的,它就会在物理存储器中创建这个页面的新拷贝,更新页表条目指向这个新的拷贝,然后恢复这个页面的可写权限。当故障处理程序返回时,CPU重新执行这个写操作,现在在新创建的页面上这个写操作就可以正常执行了。

 

存储器管理中有分页,也又分段。分段和分页有许多相似之处,也多不同之处。主要有下述三个方面的不同:


1.页是信息的物理单位,分页是为实现离散分配方式,以消减内存的外零头,以提高内存的利用率。或者说,分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位,它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。


2.页的大小固定且有系统决定,由系统把逻辑地址划分为页号和页内地址两部分,是由机器硬件实现的,因而在系统中只能由一种大小的页面;而段的长度却不固定,决定于用户所编写的程序,通常由编译程序在对源程序进行编译时,根据信息的性质来划分的。


3.分页的作业地址空间是一维的,即单一的线性地址空间,程序员只需利用一个记忆符,即可表示一个地址;而分段的作业地址空间则是二维的,程序员在标识一个地址时,即需要给出段名,又需要给出段内地址。

 

学习资料:

《计算机操作系统》 西安电子科技大学出版社

《深入理解计算机系统》机械工业出版社


0

阅读 评论 收藏 转载 喜欢 打印举报
已投稿到:
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有