江苏龙网

  1. 主页 > 生活百科 > >

计算机操作系统基础笔记( 六 )

作系统


数据结构：空闲分区表 / 空闲分区链
分区分配算法基于顺序搜索：
1. 最佳适应算法
2. 最坏适应算法
3. 首次适应算法
4. 循环首次（下次）适应算法
基于索引搜素：
1. 快速适应算法
2. 伙伴系统
最佳适应算法总是寻找其大小最接近作业所要求的存储区域 。即使作业放入后剩下的零头最小 。
优点：
遇到大作业到来时，作业要求的存储区域就比较容易得到满足 。
缺点：
产生空白区较多，且空白区较小无法使用（可干脆将整个区域划分给申请的作业 。
回收分区时插入到合适的位置较为费时 。
为了加快查找速度，应将存储空间中所有的空白 区按其大小递增的顺序链接起来，组成一空白区链 (Free List) 。
最坏适应算法它在为作业选择存储区域时，总是寻找最大的空白区 。在划分后剩下的空白区也是最大的，因而对以后的分配很可能仍然是有用的，这是该算法的一个优点 。
但是，由于最大的空白块总是首先被分配而进行划分，当有大的作业时，其存储空间的申请往往得不到满足，这是该算法的一个缺点 。
为了支持这个算法的实现，空白块应以大小递减的顺序链接起来 。
首次适应算法每个空白区按其在存储空间中地址递增的顺序链在 一起，即每个后继空白区的起始地址总是比前者的 大 。在为作业分配存储区域时，从这个空白区链的 始端开始查找，选择第一个足以满足请求的空白块，而不管它究竟有多大 。
这个选择的空白区被分成两部分 。一部分与请求的大小相等，分配给作业；剩下的部分留在空白区链中 。显然，这个算法倾向于优先利用存储空间中低址部分的空白区 。
优点：
算法简单，查找速度快，大作业到来时也比较容易得到满足
缺点：
会留下较多无法使用的空白区，存储空间利用率不高 。较小空白区集中在前端，较大空白区在尾端，导致找到合适的空白区的速度降低 。
下次适应算法我们把存储空间中空白区构成一个循环链 。每次为存储请求查找合适的分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空白区，就将它划分后分配出去 。
优点：存储空间的利用更加均衡 。
快速适应算法【计算机操作系统基础笔记】将空闲分区根据其容量大小进行分类，对于每一 类具有相同容量的所有空闲分区，单独设立一个空闲分区链表 。
在内存中设立一张管理分区类型，并记录 了该类型空闲分区链表表头的索引表，该表的每一个表项记录了对应类型空闲分区链表表头的指针 。
在内存中设立一张管理分区类型，并记录了该类型空闲分区链表表头的索引表，该表的每一个表项记录了对应类型空闲分区链表表头的指针 。
优点：
查找效率高 。
该算法在进行空闲分区分配时，不会对任何分区产生 分割，所以能保留大的分区，满足对大空间的需求，也不会产生内存碎片 。（外碎片）
缺点：
在分区归还主存时算法复杂，系统开销较大 。
该算法在分配空闲分区时是以进程为单位，一个分区 只属于一个进程，因此在为进程所分配的一个分区中 ，或多或少地存在一定的浪费 。空闲分区划分越细，浪费则越严重 。（内碎片）
伙伴系统进程请求大小为n的存储空间时，
首先计算一个 i 值，使 2 i－1 < n ≤ 2 i ；
在空闲分区大小为 2 i 的空闲分区链表中查找 。if 找到，即把该空闲分区分配给进程 。else 在分区大小为2 i＋1 的空闲分区链表中寻找; //表明长度为2 i 的空闲分区已经耗尽 if 找到大小为2 i＋1 的空闲分区 把该空闲分区分为相等的两个分区（一对伙 伴），其中一个用于分配，另一个加入分区大 小为 2 i 的空闲分区链表中 。else 查找大小为2 i＋2 的空闲分区……
哈希算法利用哈希快速查找的优点，以及空闲分区在可利 用空间表中的分布规律，建立哈希函数，构造一 张哈希表，以空闲分区大小为关键字，每一个表 项记录了一个对应的空闲分区链表表头指针 。
当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策 略 。
可重定位分区分配紧凑解决零头问题的办法，将内存中的所有作业进行移动，使它们全都相邻接，这样，可把原来分散的多个小分区合成一个大分区 。这种技术称为存储器的“紧凑” 。


推荐阅读


上一篇：两个地方的电脑，如何构成一个局域网？

下一篇：写个App 启动任务框架，有多难？