实验目
熟悉存分配回收理解存储理方式实现存空间分配回收掌握动态分区分配方式中数结构分配算法动态分区存储理方式实现程
二实验容求
存分配回收实现存储器理方式关谓分配解决道作业进程享存空间问题谓回收作业运行完成时作业进程占存空间系统
变分区理指处理作业程中建立分区分区正适合作业需求分区数调整装入作业时根作业需存量查否足够空闲空间需量分割分区分配该作业作业装入作业等着作业装入完成存空间分成许分区分区作业占分区空闲
实验求变分区存储理方式分区分配中数结构采空闲分区表空闲分区链进行分区分配中算法采首次适应算法佳适应算法差适应算法三种算法实现存分配回收时求设计实友户界面显示分配回收程时求设计实友户界面显示分配回收程
三实验仪器设备材料
实验环境
硬件环境:PC兼容机
软件环境:VC++ 60
四实验原理设计分析
某系统采变分区存储理系统运行然开始假设初始状态存空间640KB存储器区分操作系统分区(40KB)户空间区(600KB)
(作业1 申请130KB 作业2 申请60KB 作业3 申请100KB 作业2 释放 60KB
作业4 申请 200KB 作业3释放100KB 作业1 释放130KB 作业5申请140KB
作业6申请60KB 作业7申请50KB)
作业1进入存分作业1(130KB)着作业123进入分分配60KB100KB段时间运行作业2运行完毕释放占存时作业4进入系统求分配200KB存作业31运行完毕释放占存时作业5申请140KB作业6申请60KB作业7申请50KB进行存分配回收
1采变分区存储理空闲分区链实现存分配回收
空闲分区链:链指针空闲分区链成条链实现空闲分区分配链接分区起始部分设置状态位分区链接分区前指针状态位指示该分区否分配出时分区尾部设置指针链接面分区分区中间部分存放作业空闲存空间该分区分配出状态位0置1
设置存空闲分区链存空间分区通空闲分区链理进行存分配时系统优先空闲低端空间
设计空闲分区说明链设计某时刻存空间占情况表作存前基础初始化空间区已分配区说明链值设计作业申请队列作业完成释放序实现存分配回收求次分配回收显示出空闲存分区链情况空闲区说明链变化情况作业申请释放情况显示印出
2采变分区存储理分采首次适应算法佳适应算法坏适应算法实现存分配回收
3存空间分配
(1)首次适应算法
该算法中存中空闲区起始址递增次序排列作业分配存储空间时次找空闲分区空闲分区开始查找直找第满足求空闲区中划出请求相等存储空间分配作业余空闲区留空闲区链中
(2)佳适应算法
该算法中存中空闲区起始址递增次序排列作业分配存储空间时次找空闲分区空闲分区开始查找直找满足求空闲区该空闲区满足求空闲区中划出请求相等存储空间分配作业余空闲区留空闲区链中
(3)坏适应算法
该算法中存中空闲区起始址递增次序排列作业分配存储空间时次找空闲分区空闲分区开始查找直找满足求空闲区该空闲区满足求空闲区中划出请求相等存储空间分配作业余空闲区留空闲区链中
4存空间回收
作业执行完成撤离时作业占分区应该系统分区果空闲区相邻应合成较空闲区登记空闲区说明链中时相邻空闲区合问题求考虑四种情况:
(1) 释放区邻空闲区(低址邻接)
(2) 释放区邻空闲区(高址邻接)
(3) 释放区空闲区邻接
(4) 释放区邻空闲区邻接
五程序流程图
main函数里流程图
初始化firstend
整理分区序号
显示空闲分区链
选择算法a
a1首次适应算法
a2佳适应算法
a3坏适应算法
选择操作i
i1分配空间函数a
i0退出程序
i2回收空间函数
结束
分配空间里流程图
p>datalengthrequest
分配成功
分配空间函数
a1
a2
a3
输入申请存
序找空闲块
初始化q指空闲块中长度块
输入申请存
初始化q指空闲块中长度块
p>datalength>request
p状态已分配
剩
p>datalengthrequest
输入申请存
Y
Y
N
N
返回整理分区序号
回收空间里流程图
p状态改空闲
回收pp前first
pend
p状态空
面空闲块相连
p 状态改空闲
p 状态改空闲
回收空间函数
pend
Y
N
Y
N
Y
N
p前状态空
p前状态空
p状态空
p状态空
p状态空
p状态空
Y
Y
Y
N
N
N
前面空闲块相连
p状态改空闲
前面空闲块相连
面空闲块相连
Y
N
返回整理分区序号
六相关数结构关键函数说明
程序采struct free_table数结构里面包含分区序号(num)起始址(address)分区长度(length)分区状态(state)线性表双性链表存储结构(struct Node)里面包含前区指针(prior)继指针(next)开始定义条(含firstend)链开始指针尾指针开创空间链表然分三种算法进行分配回收
该程序中关键函数sort()allocation()recovery()First_fit()Best_fit()Worst_fit()中sort()函数整理分区序号删序号3时前面序号2相连起然序号2中长度总满足申请存会序号2中分配然序号2基础加1直加加原序号3序号4相等时sort()开始明显工作allocation()分配空间渡三算法中三算法中满足者满足分配请求会返回值allocation()recovery()回收存里面包含四种情况相连结果释放区空闲区邻接释放区空闲区邻接释放区空闲区邻接释放区空闲区邻接四种情况结果
七源代码
#include
#include
#define OK 1 完成
#define ERROR 0 出错
typedef int Status
typedef struct free_table定义空闲区说明表结构
{
int num 分区序号
long address 起始址
long length 分区
int state 分区状态
}ElemType
typedef struct Node 线性表双链表存储结构
{
ElemType data
struct Node *prior 前趋指针
struct Node *next 继指针
}Node*LinkList
LinkList first 头结点
LinkList end 尾结点
int flag记录删分区序号
Status Initblock()开创带头结点存空间链表
{
first(LinkList)malloc(sizeof(Node))
end(LinkList)malloc(sizeof(Node))
first>priorNULL
first>nextend
end>priorfirst
end>nextNULL
end>datanum1
end>dataaddress40
end>datalength600
end>datastate0
return OK
}
void sort()分区序号重新排序
{
Node *pfirst>next*q
qp>next
for(pNULLpp>next)
{
for(qp>nextqqq>next)
{
if(p>datanum>q>datanum)
{
q>datanum+1
}
}
}
}
显示存分配情况
void show()
{ int flag0记录分区序号
Node *pfirst
p>datanum0
p>dataaddress0
p>datalength40
p>datastate1
sort()
printf(\n\t\t存空间分配情况\n)
printf(**********************************************************\n\n)
printf(分区序号\t起始址\t分区\t分区状态\n\n)
while(p)
{
printf(d\t\td\t\tdp>datanump>dataaddressp>datalength)
if(p>datastate0) printf(\t\t空闲\n\n)
else printf(\t\t已分配\n\n)
pp>next
}
printf(**********************************************************\n\n)
}
首次适应算法
Status First_fit(int request)
{
申请作业开辟新空间初始化
Node *pfirst>next
LinkList temp(LinkList)malloc(sizeof(Node))
temp>datalengthrequest
temp>datastate1
p>datanum1
while(p)
{
if((p>datastate0)&&(p>datalengthrequest))
{恰合适空闲块
p>datastate1
return OK
break
}
else if((p>datastate0) && (p>datalength>request))
{空闲块满足需求剩余
temp>priorp>prior
temp>nextp
temp>dataaddressp>dataaddress
temp>datanump>datanum
p>prior>nexttemp
p>priortemp
p>dataaddresstemp>dataaddress+temp>datalength
p>datalengthrequest
p>datanum+1
return OK
break
}
pp>next
}
return ERROR
}
佳适应算法
Status Best_fit(int request)
{
int ch 记录剩余空间
Node *pfirst
Node *qNULL 记录佳插入位置
LinkList temp(LinkList)malloc(sizeof(Node))
temp>datalengthrequest
temp>datastate1
p>datanum1
while(p) 初始化空间佳位置
{
if((p>datastate0) && (p>datalength>request) )
{
if(qNULL)
{
qp
chp>datalengthrequest
}
else if(q>datalength > p>datalength)
{
qp
chp>datalengthrequest
}
}
pp>next
}
if(qNULL) return ERROR没找空闲块
else if(q>datalengthrequest)
{
q>datastate1
return OK
}
else
{
temp>priorq>prior
temp>nextq
temp>dataaddressq>dataaddress
temp>datanumq>datanum
q>prior>nexttemp
q>priortemp
q>dataaddress+request
q>datalengthch
q>datanum+1
return OK
}
return OK
}
差适应算法
Status Worst_fit(int request)
{
int ch 记录剩余空间
Node *pfirst>next
Node *qNULL 记录佳插入位置
LinkList temp(LinkList)malloc(sizeof(Node))
temp>datalengthrequest
temp>datastate1
p>datanum1
while(p) 初始化空间佳位置
{
if(p>datastate0 && (p>datalength>request) )
{
if(qNULL)
{
qp
chp>datalengthrequest
}
else if(q>datalength < p>datalength)
{
qp
chp>datalengthrequest
}
}
pp>next
}
if(qNULL) return ERROR没找空闲块
else if(q>datalengthrequest)
{
q>datalength1
return OK
}
else
{
temp>priorq>prior
temp>nextq
temp>dataaddressq>dataaddress
temp>datanumq>datanum
q>prior>nexttemp
q>priortemp
q>dataaddress+request
q>datalengthch
q>datanum+1
return OK
}
return OK
}
分配存
Status allocation(int a)
{
int request申请存
printf(请输入申请分配存(单位KB))
scanf(d&request)
if(request<0 ||request0)
{
printf(分配合适请重试)
return ERROR
}
switch(a)
{
case 1 默认首次适应算法
if(First_fit(request)OK) printf(\t****分配成功****)
else printf(\t****存足分配失败****)
return OK
break
case 2 选择佳适应算法
if(Best_fit(request)OK) printf(\t****分配成功****)
else printf(\t****存足分配失败****)
return OK
break
case 3 选择差适应算法
if(Worst_fit(request)OK) printf(\t****分配成功****)
else printf(\t****存足分配失败****)
return OK
break
}
}
Status deal1(Node *p)处理回收空间
{
Node *qfirst
for(qNULLqq>next)
{
if(qp)
{
if(q>prior>datastate0&&q>next>datastate0)
{
q>prior>datalength+q>datalength
q>prior>nextq>next
q>next>priorq>prior
qq>prior
q>datastate0
q>datanumflag1
}
if(q>prior>datastate0&&q>next>datastate0)
{
q>datalength+q>next>datalength
q>nextq>next>next
q>next>next>priorq
q>datastate0
q>datanumflag
}
if(q>prior>datastate0&&q>next>datastate0)
{
q>prior>datalength+q>datalength
q>prior>nextq>next
q>next>priorq>prior
qq>prior
q>datastate0
q>datanumflag1
}
if(q>prior>datastate0&&q>next>datastate0)
{
q>datastate0
}
}
}
return OK
}
Status deal2(Node *p)处理回收空间
{
Node *qfirst
for(qNULLqq>next)
{
if(qp)
{
if(q>prior>datastate0&&q>next>datastate0)
{
q>prior>datalength+q>datalength
q>prior>nextq>next
q>next>priorq>prior
qp>prior
q>datastate0
q>datanumflag1
}
if(q>prior>datastate0&&q>next>datastate0)
{
q>datastate0
}
if(q>prior>datastate0&&q>next>datastate0)
{
q>prior>datalength+q>datalength
q>prior>nextq>next
q>next>priorq>prior
qq>prior
q>datastate0
q>datanumflag1
}
if(q>prior>datastate0&&q>next>datastate0)
{
q>datastate0
}
}
}
return OK
}
存回收
Status recovery(int flag)
{
Node *pfirst
for(pNULLpp>next)
{
if(p>datanumflag)
{
if(p>priorfirst)
{
if(p>nextend)前P指时
{
if(p>next>datastate0) 面空闲块相连
{
p>datalength+p>next>datalength
p>next>next>priorp
p>nextp>next>next
p>datastate0
p>datanumflag
}
else p>datastate0
}
if(p>nextend)前P指时
{
p>datastate0
}
}结束if(p>priorblock_first)情况
else if(p>priorfirst)
{
if(p>nextend)
{
deal1(p)
}
else
{
deal2(p)
}
}结束if(p>priorblock_first)情况
}结束if(p>datanumflag)情况
}
printf(\t****回收成功****)
return OK
}
函数
void main()
{
int i 操作选择标记
int a算法选择标记
printf(**********************************************************\n)
printf(\t\t三种方法实现存空间分配\n)
printf(\t(1)首次适应算法\t(2)佳适应算法\t(3)差适应算法\n)
printf(**********************************************************\n)
printf(\n)
printf(请输入存分配算法)
scanf(d&a)
while(a<1||a>3)
{
printf(输入错误请重新输入存分配算法\n)
scanf(d&a)
}
switch(a)
{
case 1printf(\n\t****首次适应算法:****\n)break
case 2printf(\n\t****佳适应算法:****\n)break
case 3printf(\n\t****坏适应算法:****\n)break
}
Initblock() 开创空间表
while(1)
{
show()
printf(\t1 分配存\t2 回收存\t0 退出\n)
printf(请输入您操作:)
scanf(d&i)
if(i1)
allocation(a) 分配存
else if(i2) 存回收
{
printf(请输入您释放分区号:)
scanf(d&flag)
recovery(flag)
}
else if(i0)
{
printf(\n退出程序\n)
break 退出
}
else 输入操作误
{
printf(输入误请重试)
continue
}
}
}
八执行结果结果分析
初始化首次适应算法:
作业123利分配存空间:
回收序号2里面存:
分配作业4:
回收序号3里面存(邻序号2相连)
回收序号1里存(邻序号2相连)
继续分配(会发现总序查找满足求第空闲块旦发现会分配):
初始化佳适应算法:
继续分配(会发现总查找满足求空闲块空闲块长度旦发现会分配):
初始化坏适应算法:
继续分配(会发现总查找满足求空闲块空闲块长度旦发现会分配):
九遇困难解决心体会
实验采取条链表时表示空闲分区链存空间占情况存总固定空闲分区链表示区域总存里占空间实验较简单执行程中遇问题回收空间函数中考虑四种情况开始想法样:p指链表开头直等找p指分区序号等删分区序号然开始执行p>prior链首first时考虑p>next链尾end然继续考虑p前指针指针状态否空闲等考虑完p>prior链首进行考虑p>prior链首问题然进行考虑p>next链尾end然继续考虑p前指针指针状态否空闲等考虑完p>prior问题进行考虑p>next问题直样重复知道时超烦静心重新检查写程序知道写函数凌乱直接p>nextend情况掉程序出现转解决回收问题发现回收作业请求分配时分配序号会出现种情况分区序号相等情况图(a)采sort()整理分区序号开始函数放三算法函数中没发生改变然继续检查程序想函数sort()放show()函数中会样呢?没想真改变分区序号值图(b)实sort()实现图(c)里面功然止两问题程序中整理分区序号回收存花时间解决问题总次收获挺
图(a)
图(b)
图(c)
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容,不代表《香当网》观点或立场,请自行判断内容的真实性和可靠性!
该内容是文档的文本内容,更好的格式请下载文档