《操作系统原理及应用》课程设计报
告
存储管理---动态分区分配算法的模拟
学院（系）： 计算机科学与工程学院
班 级： 学号
学生姓名：
指导教师：
时间：从 2011 年 07 月 04 日 到 2011 年 07 月 08 日
摘要:动态分区分配算法就是系统在寻找空闲的分区分配给某一用户作业 ,具体
可采用首次适应算法,循环首次适应算法和最佳适应算法。下面将针对每个算法
的数据结构及算法实现进行分析，在分析算法前，先对此次课题进行了分析，
再对一些基础相关知识进行了整理。
关键字:分区分配算法；首次适应；循环首次适应；最佳适应
1．课程设计的目的
本课程设计是学生学习完《计算机操作系统》课程后，进行的一次全面的
综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深
对操作系统基础理论和重要算法的理解，加强学生的动手能力。
2．课程设计的内容及要求
内容：动态分区分配是根据进程的实际需要，动态地为之分配内存空间。
在实现可变分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法
和分区的分配和回收操作这样三个问题。
要求：设计主界面以灵活选择某算法，且以下算法都要实现：首次适应算
法、循环首次适应算法、最佳适应算法。
3．实现原理
（1）首次适应算法
首次适应算法要求空闲区按其起始地址由小到大排列，当某一用户作业要求
装入内存时，存储分配程序从起始地址最小的空间区开始扫描，直到找到满足
该作业要求的空闲区为止。
（2）循环首次适应算法
在查找空闲区时，不再每次从链首开始查找，而是从上一次找到的空闲区的
下一个空闲分区开始查找，直到找到一个能满足要求的空闲区为止，并从中划
出一块与请求大小相等的内存空间分给该作业。
（3）最佳适应算法
该算法总是把满足要求，又是最小的空闲区分配给请求进程，即在空闲区表
中，按空闲区的大小由小到大排序，建立索引，当用户进程请求分配内存时，
从索引表中找到第一个满足该进程大小要求的空闲区分配给它。
4．程序中使用的数据结构及使用的变量说明和作用
(1) 空 闲 区 说 明 表 结 构 ： 把 空 闲 区 定 义 为 数 组 变 量 ， 包 括 空 闲 区 始 址
begin[]，空闲区末址 end[]，空闲区大小 count[]，分配作业后该空闲区的始
址 new_begin[]。
int begin[];
int end[]
int []count;
int []new_begin;
数组 count[]、new_begin[]、begin[]和 end[]的长度为输入的空闲区总
数 ， 开 始 时 ： new_begin[i] = end[i] – begin[i]; 为 作 业 分 配 内 存 时 ：
new_begin[i] = new_begin[i] + 作 业 大 小 ， count[i] = end[i] –
new_begin[i]。
(2) 作 业 说 明 表 结 构 ： 各 作 业 的 大 小 job[] 和 各 作 业 分 配 的 首 址
already_begin[]。
int job[];
int already_begin[];
数组 job[]和数组 already_begin[]的长度为输入的作业总数，每次为作业
分 配 内 存 成 功 ， 则 already_begin[i] = new_begin[i]; 否 则 ，
already_begin[i]= -1，说明不在内存。
(3) 首次适应算法为作业分配主存空间的函数 "rst_"t()，循环首次适应算法为
作业分配主存空间的函数 next_"t()，最佳适应算法为作业分配主存空间的函
数 best_"t()。回收作业主存空间的函数 callback()，三个算法分别对应三个
回收主存空间的算法。显示主存空间的函数 show()，三个算法分别对应三个显
示主存空间的算法：
① 首次适应算法：
public static void first_fit( int n, int m, int job[], int begin[],
int end[]) {//分配主存
count = new int[m];//空闲分区大小
new_begin = new int[m];//存储分区分配后的首址
already_begin = new int[n];//每个作业分配的首址
boolean is_fit = true;
is_run = true;
for( int i = 0; i < m; i ++){
new_begin[i] = begin[i];
}
System.out.print("\n---首次适应算法过程如下：\n");
while( num < n){
str = "";
is_fit = false;
System.out.print("将空闲分区链以地址递增的次序链接(只显示空闲分区
大小)：");
for( int i = 0; i < m; i ++ ){//计算空闲分区大小并保存
count[i] = end[i] - new_begin[i];
if( i != m-1 ){
str =str + "|" + count[i] + "|——>";
}
else{
str =str + "|" + count[i] + "|";
}
}
System.out.print(str);
for( int i = 0; i < m; i ++){//为作业分配存储空间
if( job[num] <= count[i] ){
already_begin[num] = new_begin[i];
new_begin[i] = new_begin[i] + job[num];
count[i] = end[i] - new_begin[i];
is_fit = true;
System.out.print("作业" + (num+1) + "已成功分配" +
job[num] + "KB存储空间！");
num ++;
break;
}
}
if( is_fit == false ){
already_begin[num] = -1;
num ++;
System.out.print("找不到合适的空闲分区分配给作业" + num +
"！");
}
}
}
② 循环首次适应算法：
public static void next_fit( int n, int m, int job[], int begin[],
int end[]) {
count = new int[m];//空闲分区大小
new_begin = new int[m];//存储分区分配后的首址
already_begin = new int[n];//每个作业分配的首址
int flag = 0;//用于记录已比较过的次数
boolean is_fit = true;
is_run = true;
for( int i = 0; i < m; i ++){
new_begin[i] = begin[i];
}
- 1
- 2
前往页