动态分区分配算法实验报告心得

操作系统实验报告

实验二: 动态分区分配算法 .

学 生： 学 号： 学 院：

系 别： 专 业： 实验时间： 报告时间：

一、实验内容

编写一个内存动态分区分配模拟程序，模拟内存的分配和回收的完整过程。

一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现与主存储器的管理方式有关的，通过本实验帮助学生理解在可变分区管理方式下应怎样实现主存空间的分配和回收。 三、实验原理

模拟在可变分区管理方式下采用最先适应算法实现主存分配和回收。

(1)可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间

实验报告四 动态分区分配算法

班级 学号 姓名

一、 实验目的

动态分区分配是根据进程的实际需要，动态地为之分配内存空间，而在分配时，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。在本实验中运用了四种分配算法，分别是1.首次适应算法，2.循环首次适应算法，3.最坏适应算法4.最佳适应算法。

二、 实验环境

普通的计算机一台，编译环境Microsoft Visual C++ 6.0

三、 算法思想 1． 数据结构

（1） 分区开始地址startaddress （2） 分区大小size （3） 分区状态state

2． 功能介绍

（1） 首次适应算法

在首次适应算法中，是从已建立好的数组中顺序查找，直至找到第一个大小能满足要求的空闲分区为止，然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空间令开辟一块新的地址，大小为原来的大小减去作业大小，若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。

（2） 循环首次适应算法

该算法是由首次适应算法演变而成，在为进程分配内存空间时，不再是每次都从第一个空间开始查找，而是从上次找到的空闲分区的

配程序执行之后的结果图

实验目的

通过这次实验，加深对动态分区分配算法的理解，进一步掌握首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的实现方法。

【实验内容】

问题描述：

设计程序模拟四种动态分区分配算法：首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的工作过程。假设内存中空闲分区个数为n，空闲分区大小分别为P1, … ,Pn，在动态分区分配过程中需要分配的进程个数为m（m≤n），它们需要的分区大小分别为S1, … ,Sm，分别利用四种动态分区分配算法将m个进程放入n个空闲分区，给出进程在空闲分区中的分配情况。 程序要求如下：

1）利用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法四种动态分区分配算法模拟分区分配过程。

2）模拟四种算法的分区分配过程，给出每种算法进程在空闲分区中的分配情况。

3）输入：空闲分区个数n，空闲分区大小P1, … ,Pn，进程个数m，进程需要的分区大小S1, … ,Sm，算法选择1-首次适应算法，2-循环首次适应算法，3-最佳适应算法，4-最坏适应算法。

4）输出：最终内存空闲分区的分配情况。

实现提示：

配程序执行之后的结果图

用C++语言实现提示：

1）程序中变量定义参考（根据需要可添加）如下：

co

计算机科学 专业课程设计任务书

学生姓名 题 目 课题性质 指导教师 专业班级 学号 动态分区分配方式的模拟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 请采用首次适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。 了解动态分区分配中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。 任满杰等《操作系统原理实用教程》 电子工业出版社 2006 汤子瀛 《计算机操作系统》（修订版）西安电子科技大学出版社 2001 张尧学 史美林《计算机操作系统教程》实验

实验四 动态分区分配方式的模拟 答案

动态分区分配方式的模拟

第一部分 设计思想的说明

1 设计目标

用C语言或C++语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端空间。

预期结果：假设初始状态如下，可用的内存空间为640KB，并有下列请求序列：

作业1 申请 130KB

作业2 申请 60KB

作业3 申请 100KB

作业2 释放 60KB

作业4 申请 200KB

作业3 释放 100KB

作业1 释放 130KB

作业5 申请 140KB

作业6 申请 60KB

作业7 申请 50KB

作业6 释放 60KB

分别用首次适应算法和最佳适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。

2、设计理论

首次适应算法（First-fit）：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。

最佳适应算法（Best-fi

实验四 动态分区分配方式的模拟 答案

动态分区分配方式的模拟

第一部分 设计思想的说明

1 设计目标

用C语言或C++语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端空间。

预期结果：假设初始状态如下，可用的内存空间为640KB，并有下列请求序列：

作业1 申请 130KB

作业2 申请 60KB

作业3 申请 100KB

作业2 释放 60KB

作业4 申请 200KB

作业3 释放 100KB

作业1 释放 130KB

作业5 申请 140KB

作业6 申请 60KB

作业7 申请 50KB

作业6 释放 60KB

分别用首次适应算法和最佳适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。

2、设计理论

首次适应算法（First-fit）：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。

最佳适应算法（Best-fi

成 绩 评 定 表

学生姓名 专 业 班级学号 内存分配算法 计算机科学课程设计题目 与技术 评 语 组长签字： 成绩 日期

1

2015 年 12月 10 日 课程设计任务书

学 院 学生姓名 课程设计题目 实践教学要求与任务: 模拟分区内存管理的模式下的各种分配策略，根据输入的各进程的信息（进程名，需要内存大小，进入内存时间，退出内存时间，发生申请内存的时间，申请内存的大小等），输出各个时间段上系统中的内存分配情况（各个空闲区位置和大小，各个进程空间的位置和大小）。 任务：利用静态链表，模拟实现内存分配（分页，分区） 要求： 1. 设计数据结构，存储结构； 2. 在c兼容环境完成上述题目的代码编写与调试； 3. 程序运行及诶按交互性好； 4. 软件运行，给出测试数据。 信息学院 专 业 计算机科学与技术 班级学号 内存分配技术 工作计划与进度安排: 第14周：布置课程设计任务，查阅资料，分组设计，程序调试。 第15周：程序调试，编写课程设计报告，验收，答辩。 指导教师： 2015年11月 28日 专业负责人： 2015年11月 2

操作系统课程设计

设计题目 动态分区分配存储管理

学生姓名学 号 专业班级 指导教师

吕 霆

20102675 计算机10-01班

1

第一章 课程设计概述

1.1 设计任务:

动态分区分配存储管理

1.2 设计要求

建立描述内存分配状况的数据结构； ?建立描述进程的数据结构； ?使用两种方式产生进程：（a）自动产生， （b）手工输入； ? 在屏幕上显示内存的分配状况、每个进程的执行情况； ? 建立分区的分配与回收算法，支持紧凑算法； ? 时间的流逝可用下面几种方法模拟：（a）按键盘，每按一次可认为过一个时间单位； (b) 响应WM_TIMER；

? 将一批进程的执行情况存入磁盘文件，以后可以读出并重放；

? 支持算法：首次适应算法、循环首次适应算法、最佳适应算法：最坏适应算法。

1.3 设计目的

旨在让我们更好的了解动态分区管理方面的知识.

第二章 原理及算法描述

2.1动态分区分配算法原理

首次适应算法

* 算法概述：分配内存时，从链首开始顺序查找，找到满足的空闲分区则划出空间分配，余下的空闲空间仍保留在空闲链表中

* 实现方法：分配时从数组第一个元素开始比较，若符合条件

实验标题

实验目的

1、矩阵连乘 2、最长公共子序列 3、最大子段和 4、凸多边形最优三角剖分 5、流水作业调度 6、0-1背包问题 7、最优二叉搜索树

掌握动态规划法的基本思想和算法设计的基本步骤。 实验内容与源码

1、矩阵连乘

#include #include using namespace std;

const int size=4;

//ra,ca和rb,cb分别表示矩阵A和B的行数和列数

void matriMultiply(int a[][4],int b[][4],int c[][4],int ra ,int ca,int rb ,int cb ) {

if(ca!=rb) cerr<<\矩阵不可乘\ for(int i=0;i

int sum=a[i][0]*b[0][j]; for(int k=1;k

void MatrixChain(int *p,int n,int m[][4],int s[][4]) {

for(int i=1;i<=n;i++) m[i][i]=0;//对角线 for(int r=2;r<=n;r++)//外维 for(int i=1;i<=n-r+1;i++)//上三角 {

int j=i+r-1;

m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]

//文件名 gdf.c//

#include "stdio.h"

struct gdf //固定分区结构体//

{

char num[2]; //区号//

char size[4]; //大小//

char begin[4]; //起址//

char flag[2];

struct gdf *next; //后指针//

struct gdf *prior; //前指针//

}stu;

struct gdf *fir; //分区链表的头指针//

struct gdf *back; //分区链表的尾指针//

void enter( ),turn(),prin( );

char str[16][4]={"1","16","20","1","2","32","36","1","3","64","68","1","4","124","132","0"};