南昌大学实验报告
学生姓名：马江涛学号：8000612091 专业班级：计算机软件121班
实验类型：□验证□综合□设计□创新实验日期：2014-05-08 实验成绩：
【实验要求】
1、编程实现首次适应算法和最佳适应算法的动态分区分配的分配过程和回收过程。其中，空闲分区通过分区链来管理；在进行内存分配时，系统优先使用空闲区低端的空间。
2、假设初始状态下，可用内存空间为640K，并依次有下列请求序列：
1)作业1申请130KB。
2)作业2申请60KB。
3)作业3申请100KB。
4)作业2释放60KB。
5)作业4申请200KB。
6)作业3释放100KB。
7)作业1释放130KB。
8)作业5申请140KB。
9)作业6申请60KB。
10)作业7申请50KB。
11)作业6释放60KB。
请分别用首次适应算法和最佳适应算法进行内存块的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况【可参考后文的实验提示】。
3、上机时认真的进行测试，输入不同的资源分配请求，写出实验结果；
4、具体要求：
（1）对你的程序关键代码处进行注释。
（2）给出实验数据，对结果进行分析，说明对相关知识点的理解。
【实验目的】
了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。
【实验思路】
首次适应算法（First-fit）：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。
最佳适应算法（Best-fit）：当要分配内存空间时，就查找空闲表中满足要求的空闲块，并使得剩余块是最小的。然后把它分配出去，若大小恰好合适，则直按分配；若有剩余块，则仍保留该余下的空闲分区，并修改分区大小的起始地址。
内存回收：将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空。并判断该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及起始地址。
【实验结果分析】
【实验提示】
你的动态分区的分配与回收，程序运行结果要可视化。可参考如下运行结果的模式。请分析如下这个结果来自于哪一种动态分配算法？？
实现可变分区的分配和回收，主要考虑的问题有三个：
第一，设计记录内存使用情况的数据表格，用来记录空闲区和作业占用的区域；
第二，在设计的数据表格基础上设计内存分配算法；
第三，在设计的数据表格基础上设计内存回收算法。
首先，考虑第一个问题，设计记录内存使用情况的数据表格，用来记录空间区和作业占用的区域。
由于可变分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随内存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在内存中的起始地址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收内存分区时，可能会合并空闲分区，这样如果整个内存采用一张表格记录己分分区和空闲区，就会使表格操作繁琐。分配内存时查找空闲区进行分配，然后填写己分配区表，主要操作在空闲区；某个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见，内存的分配和回收主要是对空闲区的操作。这样为了便于对内存空间的分配和回收，就建立两张分区表记录内存使用情况，一张表格记录作业占用分区的“己分分区表”；一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种：一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分分区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数。
+++++++++++++++++++++++++++++++++++++++
+++ 主存分配情况+++
+++++++++++++++++++++++++++++++++++++++
分区号：1
起始地址：0
分区大小：130 KB
状态：已分配
——————————————
分区号：Free
起始地址：130
分区大小：60 KB
状态：空闲——————————————
分区号：3
起始地址：190
分区大小：100 KB
状态：已分配——————————————
分区号：Free
起始地址：290
分区大小：350 KB
状态：空闲——————————————
********************************************
** 1: 分配内存2: 回收内存**
** 3: 查看分配0: 退出**
********************************************
请输入您的操作：1
请输入作业(分区号)：4
请输入需要分配的主存大小(单位:KB)：200
分配成功！
********************************************
** 1: 分配内存2: 回收内存**
** 3: 查看分配0: 退出**
********************************************
请输入您的操作：3
+++++++++++++++++++++++++++++++++++++++ +++ 主存分配情况+++
+++++++++++++++++++++++++++++++++++++++ 分区号：1
起始地址：0
分区大小：130 KB
状态：已分配——————————————
分区号：Free
起始地址：130
分区大小：60 KB
状态：空闲——————————————
分区号：3
起始地址：190
分区大小：100 KB
状态：已分配——————————————
分区号：4
起始地址：290
分区大小：200 KB
状态：已分配——————————————
分区号：Free
起始地址：490
分区大小：150 KB
状态：空闲——————————————
********************************************
** 1: 分配内存2: 回收内存**
** 3: 查看分配0: 退出**
********************************************
请输入您的操作：2
请输入您要释放的分区号：3
********************************************
** 1: 分配内存2: 回收内存**
** 3: 查看分配0: 退出**
********************************************
请输入您的操作：3
+++++++++++++++++++++++++++++++++++++++ +++ 主存分配情况+++
+++++++++++++++++++++++++++++++++++++++ 分区号：1
起始地址：0
分区大小：130 KB
状态：已分配——————————————
分区号：Free
起始地址：130
分区大小：160 KB
状态：空闲——————————————
分区号：4
起始地址：290
分区大小：200 KB
状态：已分配——————————————
分区号：Free
起始地址：490
分区大小：150 KB
状态：空闲——————————————
********************************************
** 1: 分配内存2: 回收内存**
** 3: 查看分配0: 退出**
********************************************
请输入您的操作：2
请输入您要释放的分区号：1
********************************************
** 1: 分配内存2: 回收内存**
** 3: 查看分配0: 退出**
********************************************
请输入您的操作：3
+++++++++++++++++++++++++++++++++++++++ +++ 主存分配情况+++
+++++++++++++++++++++++++++++++++++++++ 分区号：Free
起始地址：0
分区大小：290 KB
状态：空闲——————————————
分区号：4
起始地址：290
分区大小：200 KB
状态：已分配——————————————
分区号：Free
起始地址：490
分区大小：150 KB
状态：空闲——————————————
********************************************
** 1: 分配内存2: 回收内存**
** 3: 查看分配0: 退出**
********************************************
请输入您的操作：1
请输入作业(分区号)：5
请输入需要分配的主存大小(单位:KB)：140
分配成功！
********************************************
** 1: 分配内存2: 回收内存**
** 3: 查看分配0: 退出**
********************************************
请输入您的操作：3
+++++++++++++++++++++++++++++++++++++++ +++ 主存分配情况+++
+++++++++++++++++++++++++++++++++++++++
分区号：5
起始地址：0
分区大小：140 KB
状态：已分配——————————————
分区号：Free
起始地址：140
分区大小：150 KB
状态：空闲——————————————
分区号：4
起始地址：290
分区大小：200 KB
状态：已分配——————————————
分区号：Free
起始地址：490
分区大小：150 KB
状态：空闲——————————————
********************************************
** 1: 分配内存2: 回收内存**
** 3: 查看分配0: 退出**
********************************************
请输入您的操作：1
请输入作业(分区号)：6
请输入需要分配的主存大小(单位:KB)：60
分配成功！
********************************************
** 1: 分配内存2: 回收内存**
** 3: 查看分配0: 退出**
********************************************
请输入您的操作：3
+++++++++++++++++++++++++++++++++++++++ +++ 主存分配情况+++
+++++++++++++++++++++++++++++++++++++++ 分区号：5
起始地址：0
分区大小：140 KB
状态：已分配——————————————
分区号：6
起始地址：140
分区大小：60 KB
状态：已分配——————————————
分区号：Free
起始地址：200
分区大小：90 KB
状态：空闲——————————————
分区号：4
起始地址：290
分区大小：200 KB
状态：已分配——————————————
分区号：Free
起始地址：490
分区大小：150 KB
状态：空闲——————————————
********************************************
** 1: 分配内存2: 回收内存**
** 3: 查看分配0: 退出**
********************************************
请输入您的操作：1
请输入作业(分区号)：7
请输入需要分配的主存大小(单位:KB)：50
分配成功！
********************************************
** 1: 分配内存2: 回收内存**
** 3: 查看分配0: 退出**
********************************************
请输入您的操作：3
+++++++++++++++++++++++++++++++++++++++ +++ 主存分配情况+++
+++++++++++++++++++++++++++++++++++++++ 分区号：5
起始地址：0
分区大小：140 KB
状态：已分配——————————————
分区号：6
起始地址：140
分区大小：60 KB
状态：已分配——————————————
分区号：7
分区大小：50 KB
状态：已分配——————————————
分区号：Free
起始地址：250
分区大小：40 KB
状态：空闲——————————————
分区号：4
起始地址：290
分区大小：200 KB
状态：已分配——————————————
分区号：Free
起始地址：490
分区大小：150 KB
状态：空闲——————————————
********************************************
** 1: 分配内存2: 回收内存**
** 3: 查看分配0: 退出**
********************************************
请输入您的操作：2
请输入您要释放的分区号：6
********************************************
** 1: 分配内存2: 回收内存**
** 3: 查看分配0: 退出**
********************************************
请输入您的操作：3
+++++++++++++++++++++++++++++++++++++++ +++ 主存分配情况+++
+++++++++++++++++++++++++++++++++++++++ 分区号：5
起始地址：0
分区大小：140 KB
状态：已分配——————————————
分区号：Free
起始地址：140
分区大小：60 KB
状态：空闲——————————————
分区号：7
分区大小：50 KB
状态：已分配
——————————————
分区号：Free
起始地址：250
分区大小：40 KB
状态：空闲
——————————————
分区号：4
起始地址：290
分区大小：200 KB
状态：已分配
——————————————
分区号：Free
起始地址：490
分区大小：150 KB
状态：空闲
——————————————
********************************************
** 1: 分配内存2: 回收内存**
** 3: 查看分配0: 退出**
********************************************
请输入您的操作：0
Press any key to continue
【首次适应算法】
1.作业1申请130KB。作业2申请60KB。作业3申请100KB。
具体分配情况如下：
2.作业2释放60KB。
3.作业4申请200KB。
4.作业3释放100KB。
5.作业1释放130KB。
6.作业5申请140KB。
作业6申请60KB。
作业7申请50KB。
7.作业6释放60KB。
【最佳适应算法】
1.作业1申请130KB。作业2申请60KB。作业3申请100KB。
2.作业2释放60KB。作业4申请200KB。
3.作业3释放100KB。
4.作业1释放130KB。
5.作业5申请140KB。作业6申请60KB。作业7申请50KB。
6.作业6释放60KB。
【代码实现】
//*************************************************************** //******** 动态分区分配方式的模拟********* //******** 制作者：马江涛********* //******** 学号：8000612091 ********* //******** 班级：计算机软件121班********* //***************************************************************
#include
#include
#define Free 0 //空闲状态
#define Busy 1 //已用状态
#define OK 1 //完成
#define ERROR 0 //出错
#define MAX_length 640 //最大内存空间为640KB
typedef int Status;
typedef struct freearea//定义一个空闲区说明表结构
{
int ID; //分区号
long size; //分区大小
long address; //分区地址
int state; //状态
}ElemType;
//---------- 线性表的双向链表存储结构------------
typedef struct DuLNode //double linked list
{
ElemType data;
struct DuLNode *prior; //前趋指针
struct DuLNode *next; //后继指针
}DuLNode,*DuLinkList;
DuLinkList block_first; //头结点
DuLinkList block_last; //尾结点
Status alloc(int);//内存分配
Status free(int); //内存回收
Status First_fit(int,int);//首次适应算法
Status Best_fit(int,int); //最佳适应算法
void show();//查看分配
Status Initblock();//开创空间表
Status Initblock()//开创带头结点的内存空间链表
{
block_first=(DuLinkList)malloc(sizeof(DuLNode));
block_last=(DuLinkList)malloc(sizeof(DuLNode));
block_first->prior=NULL;
block_first->next=block_last;
block_last->prior=block_first;
block_last->next=NULL;
block_last->data.address=0;
block_last->data.size=MAX_length;
block_last->data.ID=0;
block_last->data.state=Free;
return OK;
}
//----------------------- 分配主存-------------------------
Status alloc(int ch)
{
int ID,request;
cout<<"请输入作业(分区号)：";
cin>>ID;
cout<<"请输入需要分配的主存大小(单位:KB)：";
cin>>request;
if(request<0 ||request==0)
{
cout<<"分配大小不合适，请重试！"< return ERROR; } if(ch==2) //选择最佳适应算法 { if(Best_fit(ID,request)==OK) cout<<"分配成功！"< else cout<<"内存不足，分配失败！"< return OK; } else //默认首次适应算法 { if(First_fit(ID,request)==OK) cout<<"分配成功！"< else cout<<"内存不足，分配失败！"< return OK; } } //------------------ 首次适应算法----------------------- Status First_fit(int ID,int request)//传入作业名及申请量 { //为申请作业开辟新空间且初始化 DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); temp->data.ID=ID; temp->data.size=request; temp->data.state=Busy; DuLNode *p=block_first->next; while(p) { if(p->data.state==Free && p->data.size==request) {//有大小恰好合适的空闲块 p->data.state=Busy; p->data.ID=ID; return OK; break; } if(p->data.state==Free && p->data.size>request) {//有空闲块能满足需求且有剩余" temp->prior=p->prior; temp->next=p; temp->data.address=p->data.address; p->prior->next=temp; p->prior=temp; p->data.address=temp->data.address+temp->data.size; p->data.size-=request; return OK; break; } p=p->next; } return ERROR; } //-------------------- 最佳适应算法------------------------ Status Best_fit(int ID,int request) { int ch; //记录最小剩余空间 DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); temp->data.ID=ID; temp->data.size=request; temp->data.state=Busy; DuLNode *p=block_first->next; DuLNode *q=NULL; //记录最佳插入位置 while(p) //初始化最小空间和最佳位置 { if(p->data.state==Free && (p->data.size>request || p->data.size==request) ) { q=p; ch=p->data.size-request; break; } p=p->next; } while(p) { if(p->data.state==Free && p->data.size==request) {//空闲块大小恰好合适 p->data.ID=ID; p->data.state=Busy; return OK; break; } if(p->data.state==Free && p->data.size>request) {//空闲块大于分配需求 if(p->data.size-request { ch=p->data.size-request;//更新剩余最小值 q=p;//更新最佳位置指向 } } p=p->next; } if(q==NULL) return ERROR;//没有找到空闲块 else {//找到了最佳位置并实现分配 temp->prior=q->prior; temp->next=q; temp->data.address=q->data.address; q->prior->next=temp; q->prior=temp; q->data.address+=request; q->data.size=ch; return OK; } } //----------------------- 主存回收-------------------- Status free(int ID) { DuLNode *p=block_first; while(p) { if(p->data.ID==ID) { 华东师范大学计算机科学技术系上机实践报告 一、 内容与设计思想 1．对于以下5 个矩阵： M 1: 2?3, M 2: 3?6, M 3: 6?4, M 4: 4?2, M 5: 2?7 , (a) 找出这5个矩阵相乘需要的最小数量乘法的次数。 (b) 请给出一个括号化表达式，使在这种次序下达到乘法的次数最少。 输入： 第一行为正整数N,表示有N 组测试数据； 每组测试数据的第一行为n,表示有n 个矩阵,2<=n<=50； 接下去的n 行,每行有两个整数x 和y,表示第ni 个矩阵是x*y 的。 输出： 对行每组数据,输出一行,每行一个整数,最小的矩阵连乘积。 我们保证输出的结果在2^64之内。 基本思想： 对于n 个矩阵的连乘积，设其不同的计算次序为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下： 2．定义0/1/2背包问题为：}x p max{n 1i i i ∑=。限制条件为：c x w n 1i i i ≤∑=，且 n i 1},2,1,0{x i ≤≤∈。设f(i , y)表示剩余容量为y ，剩余物品为：i ，i+1，…，n 时的最优解的值。 1．）给出f(i , y)的递推表达式； 2．）请设计求解f(i , y)的算法，并实现你的算法； 3．）设W=[10,20,15,30]，P=[6,10,15,18],c=48，请用你的算法求解。 输入： 第一行为一个正整数N ，表示有几组测试数据。 每组测试数据的第一行为两个整数n 和M ，0 分区分配算法的实现 实验要求： ?分区空闲表要表示出分区号、始址、大小 ?作业序列能够动态输入 ?内存不足，必须有提示功能 ?总结收获体会及对该题解的改进意见和见解 （红色字体为再修改处） 源代码： /********************操作系统实验四:首次适应(first fit)算法的分区分配算法*******************/ #include } } } printf("\n---------首次适应算法按地址从小到大排列后空闲区---------\n"); printf("\t分区号\t\t大小\t\t起始地址\n"); for(i=0;i 一、实验目的 (2) 二、实验内容 (2) 三、实验步骤 (3) 四.程序调试及运行结果分析 (5) 附录：程序清单（程序过长，可附主要部分） (7) 实验四动态规划算法的应用 一、实验目的 1．掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优值计算方法。 2．熟练掌握分阶段的和递推的最优子结构分析方法。 3．学会利用动态规划算法解决实际问题。 二、实验内容 1.问题描述： 题目一：数塔问题 给定一个数塔，其存储形式为如下所示的下三角矩阵。在此数塔中，从顶部出发，在每一节点可以选择向下走还是向右走，一直走到底层。请找出一条路径，使路径上的数值和最大。 输入样例（数塔）： 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 输出样例（最大路径和）： 59 题目二：最长单调递增子序列问题(课本184页例28) 设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j) 若存在i1 题目三 0-1背包问题 给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为c，。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品只有两个选择：装入或不装入，且不能重复装入。输入数据的第一行分别为：背包的容量c，，物品的个数n。接下来的n 行表示n个物品的重量和价值。输出为最大的总价值。 输入样例： 20 3 11 9 9 10 7 5 输出样例 19 2.数据输入：个人设定，由键盘输入。 3.要求： 1）上述题目任选一做。上机前，完成程序代码的编写 2）独立完成实验及实验报告 三、实验步骤 1.理解算法思想和问题要求； 2.编程实现题目要求； 3.上机输入和调试自己所编的程序； 4.验证分析实验结果； 5.整理出实验报告。 实验二动态规划算法的应用 一、实验目的 1．掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优值计算方法。 2．熟练掌握分阶段的和递推的最优子结构分析方法。 3．学会利用动态规划算法解决实际问题。 二、实验内容 1.问题描述： 题目一：数塔问题 给定一个数塔，其存储形式为如下所示的下三角矩阵。在此数塔中，从顶部出发，在每一节点可以选择向下走还是向右走，一直走到底层。请找出一条路径，使路径上的数值和最大。 输入样例（数塔）： 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 输出样例（最大路径和）： 59 三、算法设计 void main() { 申明一个5*5的二维数组； for(int i=0;i<5;i++) { for(int j=0;j<=i;j++) { 输入数组元素p[i][j]; } } for(int k=0;k<5;k++) { for(int w=0;w<=k;w++) { 输出数组元素p[k][w]; } } for(int a=4;a>0;a--) { for(int s=0;s<=a;s++) { if(p[a][s]大于p[a][s+1]) p[a-1][s]等于p[a-1][s]加p[a][s]; else p[a-1][s] 等于p[a-1][s] 加p[a][s+1]; } } 输出p[0][0] } 四.程序调试及运行结果分析 五.实验总结 虽然这个实验比较简单，但是通过这次实验使我更加了解的动态规划法的好处和、，在解决问题时要尝试使用动态规划，这样就有可能得到一种即简单复杂性有不高的算法。 操作系统实验四 【实验题目】：动态分区分配算法 【实验学时】：4学时 【实验目的】 通过这次实验，加深对动态分区分配算法的理解，进一步掌握首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的实现方法。 【实验内容及要求】 问题描述： 设计程序模拟四种动态分区分配算法：首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的工作过程。假设内存中空闲分区个数为n，空闲分区大小分别为P1, … ,P n，在动态分区分配过程中需要分配的进程个数为m（m≤n），它们需要的分区大小分别为S1, … ,S m，分别利用四种动态分区分配算法将m个进程放入n个空闲分区，给出进程在空闲分区中的分配情况。 程序要求： 1）利用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法四种动态分区分配算法模拟分区分配过程。 2）模拟四种算法的分区分配过程，给出每种算法进程在空闲分区中的分配情况。 3）输入：空闲分区个数n，空闲分区大小P1, … ,P n，进程个数m，进程需要的分区大小S1, … ,S m。 4）输出：首次适应算法，循环首次适应算法，最佳适应算法，最坏适应算法，最终内存空闲分区的分配情况。 实现源代码： #include 使用动态分区分配方式的模拟 1内容 （1）用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。 （2）假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：?作业1申请130KB。 ?作业2申请60KB。 ?作业3申请100KB。 ?作业2释放60KB。 ?作业4申请200KB。 ?作业3释放100KB。 ?作业1释放130KB。 ?作业5申请140KB。 ?作业6申请60KB。 ?作业7申请50KB。 ?作业6释放60KB。 请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。 2、示例程序： //Tittle: 使用动态分区算法的模拟 //author: XuYongzhen #include 动态分区分配算法 一实验内容与要求 内容：动态分区分配是根据进程的实际需要，动态地为之分配内存空间，而在分配时，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。在本实验中运用了三种分配算法，分别是1.首次适应算法，2.循环首次适应算法，3.最佳适应算法。 要求：动态分区算法也称为可变分区分配算法，常见的空闲区查找算法有首次适应算法，循环首次适应算法，最佳适应算法。特别注意分区回收时，相邻空闲分区需要合并。 (1)参考操作系统教材理解这3种分配算法以及回收算法。 (2)实现3种分配算法以及回收算法。 (3)已知作业申请内存和释放内存的序列，给出内存的使用情况。 (4)作业申请内存和释放内存的序列可以存放在文本文件中。 (5)设计简单的交互界面，演示所设计的功能。(可以使用MFC进行界面的设计) (6)可根据自己能力，在完成以上基本要求后，对程序功能进行适当扩充。 二、需求分析 本次实验通过用C语言进行编程并调试、运行，形象地表现出动态分区的分配方式，直观地展现了首次适应算法和最佳适应算法对内存的释放和回收方式之间的区别。加深了我们对两种算法优缺点的理解，帮助我们了解一些数据结构和分配算法，进一步加深我们对动态分区存储器管理方式及其实现过程的理解。主要的问题在于，如何解决两种算法对内存的释放和回收空间的表示。 动态分区分配：又称为可变分区分配，这种分配方式并不事先先将主存划分成一块块的分区，而是在作业进入主存时，根据作业的大小动态地建立分区。并使分区的大小正好适应作业的需要。因此系统中分区的大小是可变的，分区的数 目也是可变的。 分区分配算法： 1.首次适应法： 为作业选择分区时总是按地址从高到低搜索，只要找到可以容纳该作业的空白块，就把该空白块分配给该作业。 特点：优先利用内存中底地址部分的空闲分区 (将所有空闲区,按其地址递增的顺序链接) 2.循环首次适应算法 该算法是由首次适应算法演变而成，在为进程分配内存空间时，不再是每次都从第一个空间开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到第一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业，为实现本算法，设置一个全局变量f，来控制循环查找，当f%N==0时，f=0；若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。 3.最佳适应算法： 接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配;为作业选择分区时总是寻找其大小最接近于作业所要求的存储区域。 三、概要设计 动态分区常用的数据结构有空闲分区表和空闲分区链，用来记录内存的使用情况，此题中我采用的是空闲分区链的结构，用链指针将所有的分区链接成一条链，每个分区的结构如下所示： typedef struct freearea//定义一个空闲区说明表结构 { int ID; //分区号 long size; //分区大小 long address; //分区地址 int state; //状态 }ElemType; typedef struct DuLNode //double linked list { ElemType data; struct DuLNode *prior; //前趋指针 struct DuLNode *next; //后继指针 }DuLNode,*DuLinkList; 南昌大学实验报告 学生姓名：马江涛学号： 8000612091 专业班级：计算机软件121班 实验类型：□验证□综合□设计□创新实验日期： 2014-05-08 实验成绩： 【实验要求】 1、编程实现首次适应算法和最佳适应算法的动态分区分配的分配过程和回收过程。其中，空闲分区通过分区链来管理；在进行内存分配时，系统优先使用空闲区低端的空间。 2、假设初始状态下，可用内存空间为640K，并依次有下列请求序列： 1)作业1申请130KB。 2)作业2申请60KB。 3)作业3申请100KB。 4)作业2释放60KB。 5)作业4申请200KB。 6)作业3释放100KB。 7)作业1释放130KB。 8)作业5申请140KB。 9)作业6申请60KB。 10)作业7申请50KB。 11)作业6释放60KB。 请分别用首次适应算法和最佳适应算法进行内存块的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况【可参考后文的实验提示】。 3、上机时认真的进行测试，输入不同的资源分配请求，写出实验结果； 4、具体要求： （1）对你的程序关键代码处进行注释。 （2）给出实验数据，对结果进行分析，说明对相关知识点的理解。 【实验目的】 了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。 【实验思路】 首次适应算法（First-fit）：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。 最佳适应算法（Best-fit）：当要分配内存空间时，就查找空闲表中满足要求的空闲块，并使得剩余块是最小的。然后把它分配出去，若大小恰好合适，则 实验三使用动态分区分配方式的模拟 1、实验目的 了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。 2、实验内容 (1) 用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。 (2) 假设初始状态下，可用的内存空间为640KB，并有下列的请求序列： ?作业1申请130KB。 ?作业2申请60KB。 ?作业3申请100KB。 ?作业2释放60KB。 ?作业4申请200KB。 ?作业3释放100KB。 ?作业1释放130KB。 ?作业5申请140KB。 ?作业6申请60KB。 ?作业7申请50KB。 ?作业6释放60KB。 请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。 程序代码——C语言实现 #include void Init() //空闲分区链的初始化 { node *p; p=(node *)malloc(sizeof(node)); p->before=&L; p->after=NULL; p->size=640; p->address=0; p->state=0; L.after=p; L.before=NULL; L.size=0; U.next=NULL; n=&U; } node *search(int a) { node *p=L.after; if(p==NULL) { printf("没有空闲的区域!"); p=NULL; return p; } else { while(p!=NULL && a>p->size) p=p->after; if(p==NULL) { printf("没有找到合适的空闲空间!"); p=NULL; return p; } else return p; } } void recovery(int a,int b) //内存回收算法 { 课程设计报告 课程设计题目：循环首次适应的动态分区分配算法模拟 专业：计算机科学与技术 班级：10204102 姓名：谱 学号: 10204102 指导教师:高小辉 2013年1月11 日 目录 一．循环首次适应算法 (3) 1. 概述 (3) 2．需求分析 (3) 二．实验指导 (4) 1.基本思想 (4) 2．数据结构 (4) 三．运行环境 (6) 四．流程图 (6) 五．循环首次适应算法代码 (5) 六．调试结果 (11) 七、总结 (14) 八．参考文献 (14) 一．循环首次适应算法 1.概述： 该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块的请求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查找指针，用于指示下一次起始查询的空闲分区，并采用循环查找方式，即如果最后一个（链尾）空闲分区的大小仍不能满足要求，则返回到第一个空闲分区，比较大小是否满足，找到后，应调整起始查询指针。 2. 需求分析 了解动态分区分配中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。采用首次适应算法的动态分区分配过程alloc()和回收过程free()。 空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间，即每次分配内存空间是总是从低址部分开始进行循环，找到第一个合适的空间，便按作业所需分配的大小分配给作业。 作业完成时，需要释放作业所占空间，此时要考虑到四种情况： (1)回收区与插入点的前一个空闲分区相邻接。此时将二者合并，修改前一 分区的大小。 (2)回收区与插入点的后一空闲分区相邻接，将二者合并，用回收区的首址 作为新空闲区的首址。 (3)回收区同时与插入点的前后两个空闲分区相邻接，三者合并，使用前一空 闲分区的表项和首址。 (4)回收区单独存在。 二、实验指导 1．基本思想 动态分区是指系统不预先划分固定分区，而是在装入程序的时候划分内存区域，使得为程序分配的分区大小恰好等于该程序的需求量，且分区的个数是动态的。显然动态分区有较大的灵活性，较之固定分区能获得好的内存利用率。 2．数据结构 动态分区管理可以用两种数据结构实现，一种是已分配区表和空闲区表，也就是用预先定义好的系统空间来存放空间分配信息。 实验三：动态规划法 【实验目的】 深入理解动态规划算法的算法思想，应用动态规划算法解决实际的算法问题。 【实验性质】 验证性实验。 【实验要求】 对于下列所描述的问题，给出相应的算法描述，并完成程序实现与时间复杂度的分析。该问题描述为：一般地，考虑矩阵A1，A2，…，An的连乘积，它们的维数分别为d0,d1,…,dn,即Ai的维数为di-1×di (1≤i≤n)。确定这n个矩阵的乘积结合次序，使所需的总乘法次数最少。对应于乘法次数最少的乘积结合次序为这n个矩阵的最优连乘积次序。按给定的一组测试数据对根据算法设计的程序进行调试：6个矩阵连乘积A=A1×A2×A3×A4×A5×A6，各矩阵的维数分别为：A1：10×20，A2：20×25，A3：25×15，A4：15×5，A5：5×10，A6：10×25。完成测试。 【算法思想及处理过程】 【程序代码】 printf ("\n\n矩阵连乘次数的最优值为:\n"); printf ("-----------------------------------------------\n"); print2 (0, 6-1, s); printf ("\n-----------------------------------------------\n\n"); return 0; } void MatrixChain (int p[], int m[][6], int s[][6], int n) { int i, j, k, z, t; for (i=0; i 实验报告 （2009/2010学年第一学期） 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程 实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。 任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。 要求：掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件：计算机 软件：Visual C++ 三、实验原理及内容（包括操作过程、结果分析等） 1、最长公共子序列（LCS）问题是：给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n}，要求找出X和Y的一个最长公共子序列。 例如：X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列，检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。 2、分析LCS问题特征可知，如果Z={z1,z2,……，z k}为它们的最长公共子序列，则它们一定具有以下性质： （1）若x m=y n，则z k=x m=y n，且Z k-1是X m-1和Y n-1的最长公共子序列； （2）若x m≠y n且x m≠z k，则Z是X m-1和Y的最长公共子序列； （3）若x m≠y n且z k≠y n，则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题： 若x m=y m，则进一步分解为求解两个（前缀）子字符序列X m-1和Y n-1的最长公共子序列问题； 如果x m≠y n，则原问题转化为求解两个子问题，即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。 c++动态分区分配算法模拟(操作系统课程 设计) 课程设计 课程设计名称：操作系统课程设计 专业班级： 学生姓名： 学号： 指导教师： 课程设计时间：6月13日-——6月17日 计算机科学专业课程设计任务书 说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页 1：需求分析 （1）用C语言实现采用首次适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间。 （2）假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：作业1申请130KB；作业2申请60KB；作业3申请100KB；作业2释放60KB；作业4申请200 KB；作业3释放100 KB；作业1释放 130 KB；作业5申请140 KB；作业6申请60 KB；作业7申请 50KB；作业6释放60 KB。采用首次适应算法进行内存块的分配和回 收，同时显示内存块分配和回收后空闲内存分区链的情况。 2：概要设计 （1）数据结构：作业队列数据结构，用于存储待处理作业；阻塞作业队列数据结构，用于存储阻塞的作业。已分配内存块的双向链表，记录当前系 统已分配的各个内存块；未分配内存块的双向链表，记录系统中剩余的 各个内存块；系统内存分配总情况的结点对象，记录系统中阻塞的作业 总数，已分配的内存块数，剩余的内存块数。 （2）主函数：对作业队列、阻塞队列、已分配内存块链表、未分配内存块链表、系统总内存分配情况结点对象进行初始化，调用分配函数或回收函 数，循环处理11个作业步。 （3）分配函数alloc()：首次适应算法检索未分配的内存块链表，若找到合适的内存块，则加以判断，空闲内存块大小减去作业去请求内存块大小小于 /*9.3.2 源程序*/ /***pcb.c***/ #include "stdio.h" #include "stdlib.h" #include "string.h" #define MAX 32767 typedef struct node /*设置分区描述器*/ { int address,size; struct node *next; }RECT; /*函数原型*/ RECT *assignment(RECT *head,int application); void acceptment1(RECT *head,RECT *back1); void acceptment2(RECT *head,RECT *back1) ; int backcheck(RECT *head,RECT *back1); void print(RECT *head); /*变量声明*/ RECT *head,*back,*assign1,*p; int application1,maxblocknum; char way; /*主函数*/ main() { char choose[10]; int check; head=malloc(sizeof(RECT)); /*建立可利用区表的初始状态*/ p=malloc(sizeof(RECT)); head->size=MAX; head->address=0; head->next=p; maxblocknum=1; p->size=MAX; p->address=0; p->next=NULL; print(head); /*输出可利用表初始状态*/ printf("Enter the way(best or first(b/f)\n");/*选择适应策略*/ scanf("%c",&way); do{ printf("Enter the assign or accept(as/ac)\n"); scanf("%s",choose); /*选择分配或回收*/ if(strcmp(choose,"as")==0) /*as为分配*/ { printf("Input application:\n"); 本科实验报告 课程名称：算法设计与分析 实验项目：递归与分治算法 实验地点：计算机系实验楼110 专业班级：物联网1601 学号：2016002105 学生姓名：俞梦真 指导教师：郝晓丽 2018年05月04 日 实验一递归与分治算法 1.1 实验目的与要求 1．进一步熟悉C/C++语言的集成开发环境； 2．通过本实验加深对递归与分治策略的理解和运用。 1.2 实验课时 2学时 1.3 实验原理 分治（Divide-and-Conquer）的思想：一个规模为n的复杂问题的求解，可以划分成若干个规模小于n的子问题，再将子问题的解合并成原问题的解。 需要注意的是，分治法使用递归的思想。划分后的每一个子问题与原问题的性质相同，可用相同的求解方法。最后，当子问题规模足够小时，可以直接求解，然后逆求原问题的解。 1.4 实验题目 1．上机题目：格雷码构造问题 Gray码是一个长度为2n的序列。序列无相同元素，每个元素都是长度为n的串，相邻元素恰好只有一位不同。试设计一个算法对任意n构造相应的Gray码（分治、减治、变治皆可）。 对于给定的正整数n，格雷码为满足如下条件的一个编码序列。 （1）序列由2n个编码组成，每个编码都是长度为n的二进制位串。 （2）序列中无相同的编码。 （3）序列中位置相邻的两个编码恰有一位不同。 2．设计思想： 根据格雷码的性质，找到他的规律，可发现，1位是0 1。两位是00 01 11 10。三位是000 001 011 010 110 111 101 100。n位是前n-1位的2倍个。N-1个位前面加0，N-2为倒转再前面再加1。 3．代码设计： 实验四动态分区分配算法实验报告及程序 ————————————————————————————————作者：————————————————————————————————日期： 实验报告四动态分区分配算法 班级学号姓名 一、实验目的 动态分区分配是根据进程的实际需要，动态地为之分配内存空间，而在分配时，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。在本实验中运用了四种分配算法，分别是 1.首次适应算法，2.循环首次适应算法，3.最坏适应算法4.最佳适应算法。 二、实验环境 普通的计算机一台，编译环境Microsoft Visual C++ 6.0 三、算法思想 1．数据结构 （1）分区开始地址startaddress （2）分区大小size （3）分区状态state 2．功能介绍 （1）首次适应算法 在首次适应算法中，是从已建立好的数组中顺序查找，直至找到第一个大小能满足要求的空闲分区为止，然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空间令开辟一块新的地址，大小为原来的大小减去作业大小，若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。 （2）循环首次适应算法 该算法是由首次适应算法演变而成，在为进程分配内存空间时，不再是每次都从第一个空间开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到第一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业，为实现本算法，设置一个全局变量f，来控制循环查找，当f%N==0时，f=0；若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。 操作系统课程设计 动态分区分配存储管理 吕 霆 计算机10-01班 设计题目 学 号 专业班级 学生姓名 指导教师 第一章课程设计概述 1.1 设计任务: 动态分区分配存储管理 1.2 设计要求 建立描述内存分配状况的数据结构； 建立描述进程的数据结构； 使用两种方式产生进程：（a）自动产生，（b）手工输入； 在屏幕上显示内存的分配状况、每个进程的执行情况； 建立分区的分配与回收算法，支持紧凑算法； 时间的流逝可用下面几种方法模拟：（a）按键盘，每按一次可认为过一个时间单位； (b) 响应WM_TIMER； 将一批进程的执行情况存入磁盘文件，以后可以读出并重放； 支持算法：首次适应算法、循环首次适应算法、最佳适应算法：最坏适应算法。1.3 设计目的 旨在让我们更好的了解动态分区管理方面的知识. 第二章原理及算法描述 2.1动态分区分配算法原理 首次适应算法 * 算法概述：分配内存时，从链首开始顺序查找，找到满足的空闲分区则划出空间分配，余下的空闲空间仍保留在空闲链表中 * 实现方法：分配时从数组第一个元素开始比较，若符合条件则将该元素减去对应作业的值 循环首次适应算法 * 算法概述：由首次适应算法演变，只是每次分配改为由上一次找到的空闲分区开始查找 * 实现方法：在首次适应算法的基础上增加一个值用于记录找到的空闲分区的位置 最佳适应算法 * 算法概述：每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区 分配给作业 * 实现方法：我们决定每次分配先把空闲分区按从小到大的顺序排列，然后将第一个匹配分区分配给作业 最坏适应算法 * 算法概述：每次为作业分配内存时，总是挑选一个最大的空闲分区分割给作业使用 * 实现方法：算法与最佳适应算法几乎相同，仅在排序时把空闲分区表按从大到小的顺序排列，所以未作详细注释 回收分区 当进程运行完毕释放内存时,系统根据回收区的首址,从空闲区链(表)中找到相应的插入点,此时可能出现以下四种情况之一; 1)回收区与插入点的前一个空闲分区F1相邻接,此时应将回收区与插入点的前一分 区合并,不必为回收区分配新表项,而只需修改其前一分区F1的大小. 2)回收分区与插入点的后一空闲分区F2相邻接,此时也可将两分区合并,形成新的 空闲分区,但用回收区的首址作为新空闲区的首址,大小为两者之和. 3)回收区同时与插入点的前,后两个分区邻接,此时将三个分区合并,使用F1的表项 和F1的首址,取消F2的表项,大小为三者之和. 4)回收区既不与F1相邻接,又不与F2邻接.这时应为回收区单独建立一新表项,填 写回收区的首址和大小,并根据其首址插入到空闲链中的适当位置. 紧凑算法 通过移动内存中的作业的位置,以把原来多个分散的小分区拼接成一个大分区的方法. 第三章开发环境 此程序是本人利用c++语言在vs2012的开发环境中实现的 第四章程序实现--数据结构 #include 《算法设计与分析》实验报告实验二递归与分治策略 Module 1: 免费馅饼 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 59327 Accepted Submission(s): 20813 Problem Description 都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以gameboy马上卸下身上的背包去接。但由于小径两侧都不能站人，所以他只能在小径上接。由于gameboy平时老呆在房间里玩游戏，虽然在游戏中是个身手敏捷的高手，但在现实中运动神经特别迟钝，每秒种只有在移动不超过一米的范围内接住坠落的馅饼。现在给这条小径如图标上坐标： 为了使问题简化，假设在接下来的一段时间里，馅饼都掉落在0-10这11个位置。开始时gameboy站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中其中一个位置上的馅饼。问gameboy最多可能接到多少个馅饼？（假设他的背包可以容纳无穷多个馅饼） Input 输入数据有多组。每组数据的第一行为以正整数n(0 操作系统实验报告实验2 动态分区分配算法 报告日期：2016-6-15 姓名： 学号： 班级： 任课教师： 实验2 动态分区分配算法 一、实验内容 编写一个内存动态分区分配模拟程序，模拟内存的分配和回收的完整过程。 二、实验目的 一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现与主存储器的管理方式有关的，通过本实验帮助学生理 解在可变分区管理方式下应怎样实现主存空间的分配和回收。 三、实验原理 模拟在可变分区管理方式下采用最先适应算法实现主存分配和回收。 (1)可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如： 为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下： 第一栏 第二栏 其中，起址——指出一个空闲区的主存起始地址。 长度——指出从起始地址开始的一个连续空闲的长度。 状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区。 (2) 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。 (3) 采用最先适应算法（顺序分配算法）分配主存空间。 按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。 由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。 (4) 当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。 (5) 请按最先适应算法设计主存分配和回收的程序。假设初始时主存中没有作业，现按下面序列进行内存的申请与释放： 作业1申请300K，作业2申请100K，作业1释放300K，作业3申请150K， 作业4申请30K，作业5申请40K，作业6申请60K，作业4释放30K。 请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。 四、实验报告 1. 画出算法流程图。动态规划实验报告
分区分配算法的实现
动态规划算法实验
动态规划算法的应用实验报告
操作系统实验四实验报告动态分区分配算法
动态分区分配方式模拟
动态分区分配算法资料
实验报告-动态分区分配算法
动态分区分配方式的模拟C语言代码和C代码
循环首次适应的动态分区分配算法模拟
算法实验动态规划----矩阵连乘
南京邮电大学算法设计实验报告——动态规划法
最新c++动态分区分配算法模拟(操作系统课程设计)
存储管理分区分配算法
算法设计与分析实验报告
实验四动态分区分配算法实验分析报告及程序
操作系统课程设计动态分区分配存储管理
算法设计与分析---动态规划实验
操作系统实验—动态分区分配算法
相关主题
文本预览