操作系统课程设计
设计题目
动态分区分配存储理
学生姓名号
学 号
指导教师
专业班级
计算机班
第章 课程设计概述
11 设计务
动态分区分配存储理
12 设计求
建立描述存分配状况数结构
l建立描述进程数结构
l两种方式产生进程:(a)动产生 (b)手工输入
l 屏幕显示存分配状况进程执行情况
l 建立分区分配回收算法支持紧凑算法
l 时间流逝面种方法模拟:(a)键盘次认时间单位 (b) 响应WM_TIMER
l 批进程执行情况存入磁盘文件读出重放
l 支持算法:首次适应算法循环首次适应算法佳适应算法:坏适应算法
13 设计目
旨更解动态分区理方面知识
第二章 原理算法描述
21动态分区分配算法原理
首次适应算法
* 算法概述:分配存时链首开始序查找找满足空闲分区划出空间分配余空闲空间保留空闲链表中
* 实现方法:分配时数组第元素开始较符合条件该元素减应作业值
循环首次适应算法
* 算法概述:首次适应算法演变次分配改次找空闲分区开始查找
* 实现方法:首次适应算法基础增加值记录找空闲分区位置
佳适应算法
* 算法概述:次作业分配存时总满足求空闲分区分配作业
* 实现方法:决定次分配先空闲分区序排列然第匹配分区分配作业
坏适应算法
* 算法概述:次作业分配存时总挑选空闲分区分割作业
* 实现方法:算法佳适应算法相仅排序时空闲分区表序排列未作详细注释
回收分区
进程运行完毕释放存时系统根回收区首址空闲区链(表)中找相应插入点时出现四种情况
1)回收区插入点前空闲分区F1相邻接时应回收区插入点前分区合必回收区分配新表项需修改前分区F1
2)回收分区插入点空闲分区F2相邻接时两分区合形成新空闲分区回收区首址作新空闲区首址两者
3)回收区时插入点前两分区邻接时三分区合F1表项F1首址取消F2表项三者
4)回收区F1相邻接F2邻接时应回收区单独建立新表项填写回收区首址根首址插入空闲链中适位置
紧凑算法
通移动存中作业位置原分散分区拼接成分区方法
第三章 开发环境
程序利c++语言vs2012开发环境中实现
第四章 程序实现数结构
#include
#include
#include
using namespace std
ofstream stream输出流象
int ary1[20][4]存分配状态
int ary2[20][3]空闲分区状态
int ary3[10]进程分配状态
int recycle需回收盘块序号
int id1算法选择号
int m存区数
int n空闲区数
int q进程数
int r0循环首次适应算法:应次查找空闲分区序号
印输出函数
void vision()
{
int i
int j
if(id11)streamopen(first_fittxt iosapp)
if(id12)streamopen(nextfirst_fittxt iosapp)
if(id13)streamopen(best_fittxtiosapp)
if(id14)streamopen(worst_fittxt iosapp)
if(id15)streamopen(compacttxtiosapp)
if(id16)streamopen(huishoutxtiosapp)
cout<<存分配状态<
cout <
cout<<已分配
stream<<已分配}
else{
cout<<未分配
stream<<未分配
}
cout <
cout <
cout<
cout<<<
}
作业信息动产生
void create_pro()
{
int i
for(i0i
ary3[i]rand()100
if(ary3[i]0)
{i}
}
ary3[0]42
ary3[1]86
cout<<产生<
cout<<分
for(i0icout<<[< }
cout <}
作业手动生成
void create_zuoye(){
int j
int choice2
int id3rand()10
mid3存区数量
cout<<您创建进程:
cin>>choice2
qchoice2
cout<<输入想创建作业请求<for(int i0i {
cin>>j
ary3[i]j
}
cout<<创建<for(int i0i cout< }
cout<}
存信息动产生
void create_apply()
{
int i
for (i0i{
ary1[i][0]i+1
ary1[i][1]rand()100
if(i0)
ary1[i][2]0
else
{
ary1[i][2]ary1[i1][2]+ary1[i1][1]
}
ary1[i][3]rand()3
cout < if(ary1[i][1]0)
{i}
}
int k0空闲区数量
for (i0i{
if(ary1[i][3]2)
{ary2[k][0]ary1[i][0]
ary2[k][1]ary1[i][1]
ary2[k][2]ary1[i][2]
k++
}
}
nk空闲块数量
}
存信息手动生成
int create_fenqu(){
int kxyo0
int a0
cout<<输入想创建存分区块数
cin>>k
cout<<输入<for(int i0i ary1[i][0]i 序号
cin>>x
ary1[i][1]x
}
cout<<输入存块分配状态<for(int i0i cin>>y
if(y2){
n++
}
ary1[i][3]y状态
}
ary1[0][2]0
ary1[1][2]ary1[0][1]
for(int i2iary1[i][2]ary1[i1][2]+ary1[i1][1]起始址
}
mk
for (int i0i{
if(ary1[i][3]2){
ary2[a][0]ary1[i][0]
ary2[a][1]ary1[i][1]
ary2[a][2]ary1[i][2]
a++
}
}
na
return mn
}
首次适应算法
void first_fit()
{
vision()
int i
int j
int k
int l
int d保存第k值
int id20
for(i0i{
for(j0j{
if(ary2[j][1]>ary3[i])进程占空间等中空闲区
{
cout<<[<streamopen(first_fittxt iosapp)
stream<<[<streamclose()
if(ary2[j][1]ary3[i])进程占空间等中空闲区块
{
ary1[ary2[j][0]1][3]2
for(kj+1k{
ary2[k1][0]ary2[k][0]
ary2[k1][1]ary2[k][1]
ary2[k1][2]ary2[k][2]
}
n
}else否话空闲链应方盘块进程占存分配应项开始增加项
{
lary2[j][0]
dary1[l1][1]
ary1[l1][1]ary3[i]
ary1[l1][3]2
m++
for(kmk>ary2[j][0]+1k)
{
ary1[k1][0]ary1[k2][0]+1
ary1[k1][1]ary1[k2][1]
ary1[k1][2]ary1[k2][2]
ary1[k1][3]ary1[k2][3]
}
lary2[j][0]
ary1[l][0]l+1
ary1[l][1]dary3[i]
ary1[l][2]ary1[l1][1]+ary1[l1][2]
ary1[l][3]0
k0
for(id20id2{
if(ary1[id2][3]2)
{
ary2[k][0]ary1[id2][0]
ary2[k][1]ary1[id2][1]
ary2[k][2]ary1[id2][2]
k++
}
}
nk
}
break
}
else
{
cout<<[<streamopen(first_fittxt iosapp)
stream<<[<streamclose()
}
}
vision()
}
}
首次循环适应算法
void next_fit()
{
vision()
int i
int j
int k
int s
int d
int id2
for(i0i{
for(jrj{
if(ary3[i]{
cout<<[<streamopen(nextfirst_fittxt iosapp)
stream<<[<streamclose()
if(ary3[i]ary2[j][1])
{
改变存分配
kary2[j][0]应空闲块应存块序号
k
ary1[k][3]2应存块标志位改成已分配
改变空闲块表:块空闲块空闲块移格
n
for(kjk{
ary2[k][0]ary2[k+1][0]
ary2[k][1]ary2[k+1][1]
ary2[k][2]ary2[k+1][2]
}
vision()
break
}
else应空闲块进程需
{
改变存分配情况
r(r+1)n
改变第k块容
kary2[j][0]
dary1[k1][1]
ary1[k1][1]ary3[i]
ary1[k1][3]2
k+1移格
m++存块数增加1
for(sm1s>ks)
{
ary1[s][0]ary1[s1][0]+1
ary1[s][1]ary1[s1][1]
ary1[s][2]ary1[s1][2]
ary1[s][3]ary1[s1][3]
}
改变第k+1块容:应数组ary1[k]
ary1[k][0]ary1[k1][0]+1
ary1[k][1]dary1[k1][1]
ary1[k][2]ary1[k1][1]+ary1[k1][2]
改变空闲表分配情况
k0
for(id20id2{
if(ary1[id2][3]2)
{
ary2[k][0]ary1[id2][0]
ary2[k][1]ary1[id2][1]
ary2[k][2]ary1[id2][2]
k++
}
}
nk
vision()
break
}
}
else{
cout<<[<streamopen(nextfirst_fittxt iosapp)
stream<<[<streamclose()
}
}
}
}
思路:先空闲列表检索遍选出佳答案进行分配
void best_fit()佳算法序检索进程求存接快分配进程
{
int i
int s
int j9999保存接答案
int e存放进行较时中间结果
int k
int l
int d
int id2
vision()
for(i0i{ e9999
j9999
for(s0s{
if((ary2[s][1]>ary3[i])&&(e>ary2[s][1]))满足分配求
{
eary2[s][1]
js
}
}
if(j<0)
{
cout<<[<streamopen(best_fittxt iosapp)
stream<<[<streamclose()
}else
{
cout<<[<streamopen(best_fittxt iosapp)
stream<<[<streamclose()
if(ary2[j][1]ary3[i])
{
kary2[j][0]
ary1[k1][3]2
for(lkl{
ary2[l1][0]ary2[l][0]
ary2[l1][1]ary2[l][1]
ary2[l1][2]ary2[l][2]
}
n
}
else
{
应存分配进行更改
kary2[j][0]
dary1[k1][1]
ary1[k1][1]ary3[i]
ary1[k1][3]2
m++
for(lml>ary2[j][0]+1l)
{
ary1[l1][0]ary1[l2][0]+1
ary1[l1][1]ary1[l2][1]
ary1[l1][2]ary1[l2][2]
ary1[l1][3]ary1[l2][3]
}
kary2[j][0]
ary1[k][0]k+1
ary1[k][1]dary1[k1][1]
ary1[k][2]ary1[k1][1]+ary1[k1][2]
ary1[k][3]0
k0
for(id20id2{
if(ary1[id2][3]2)
{
ary2[k][0]ary1[id2][0]
ary2[k][1]ary1[id2][1]
ary2[k][2]ary1[id2][2]
k++
}
}
nk
for(kj+1k{
ary2[k][0]++
}
}
}
vision()
}
}
坏适应算法
void worst_fit()
{
int i
int s
int j9999保存接答案
int e9999存放进行较时中间结果
int k
int l
int d
int id2
vision()
for(i0i{
j9999
e9999
for(s0s{
if((ary2[s][1]>ary3[i])&&(e{
eary2[s][1]
js
}
}
if(j<0)
{
cout<<[<streamopen(worst_fittxt iosapp)
stream<<[<streamclose()
}else
{
cout<<[<streamopen(worst_fittxt iosapp)
stream<<[<streamclose()
if(ary2[j][1]ary3[i])
{
kary2[j][0]
ary1[k1][3]2
for(lkl{
ary2[l1][0]ary2[l][0]
ary2[l1][1]ary2[l][1]
ary2[l1][2]ary2[l][2]
}
n
}
else
{
应存分配进行更改
kary2[j][0]
dary1[k1][1]
ary1[k1][1]ary3[i]
ary1[k1][3]2
m++
for(lml>ary2[j][0]+1l)
{
ary1[l1][0]ary1[l2][0]+1
ary1[l1][1]ary1[l2][1]
ary1[l1][2]ary1[l2][2]
ary1[l1][3]ary1[l2][3]
}
kary2[j][0]
ary1[k][0]k+1
ary1[k][1]dary1[k1][1]
ary1[k][2]ary1[k1][1]+ary1[k1][2]
ary1[k][3]0
k0
for(id20id2{
if(ary1[id2][3]2)
{
ary2[k][0]ary1[id2][0]
ary2[k][1]ary1[id2][1]
ary2[k][2]ary1[id2][2]
k++
}
}
nk
for(kj+1k{
ary2[k][0]++
}
}
}
vision()
}
}
回收存算法:
*
计八种情况1(1)回收区邻接着空闲盘块连接着已分配盘块
(2)回收区邻接着空闲盘块邻接着已分配盘块
(3)回收区连接空闲盘块
(4)空闲区邻接已分配盘块
(5)回收盘块第盘块邻接着空闲盘块
(6)回收盘块第盘块邻接着已分配盘块
(7)回收盘块盘块邻接空闲盘块
(8)回收盘块盘块邻接已分配盘块
*
void apply_recycle()
{
int i
int j
int k
if(m1)
{
ary1[0][3]0
n++
ary2[0][0]1
ary2[0][1]ary1[0][1]
ary2[0][2]ary1[0][2]
vision()
}
else
{
if(recycle1)
{ cout<if(ary1[1][3]2)
{
cout<<回收盘块第盘块邻接着空闲盘块<streamopen(huishoutxt iosapp)
stream<<回收盘块第盘块邻接着空闲盘块<streamclose()
ary1[0][1]ary1[0][1]+ary1[1][1]
ary1[0][3]0
for(i1i{
ary1[i][0]ary1[i+1][0]1
ary1[i][1]ary1[i+1][1]
ary1[i][2]ary1[i+1][2]
ary1[i][3]ary1[i+1][3]
cout<}
m
cout<<
k0
vision()
cout<cout< cout< cout< for(j0j {
cout<if(ary1[j][3]2)
{
ary2[k][0]ary1[j][0]
ary2[k][1]ary1[j][1]
ary2[k][2]ary1[j][2]
k++
}
}
nk
vision()
}
else{
cout<<回收盘块第盘块邻接着已分配盘块<streamopen(huishoutxt iosapp)
stream<<回收盘块第盘块邻接着已分配盘块<streamclose()
ary1[0][3]0
k0
for(j0j{
cout<if(ary1[j][3]2)
{
ary2[k][0]ary1[j][0]
ary2[k][1]ary1[j][1]
ary2[k][2]ary1[j][2]
k++
}
}
nk
vision()
}
}
else if(recyclem)
{
if(ary1[recycle2][3]2)
{
cout<<回收盘块盘块邻接空闲盘块<streamopen(huishoutxt iosapp)
stream<<回收盘块盘块邻接空闲盘块<streamclose()
ary1[recycle2][3]0
ary1[recycle2][1]ary1[recycle2][1]+ary1[recycle1][1]
m
k0
for(j0j{
cout<if(ary1[j][3]2)
{
ary2[k][0]ary1[j][0]
ary2[k][1]ary1[j][1]
ary2[k][2]ary1[j][2]
k++
}
}
nk
vision()
}
else{
cout<<回收盘块盘块邻接已分配盘块<streamopen(huishoutxt iosapp)
stream<<回收盘块盘块邻接已分配盘块<streamclose()
ary1[recycle1][3]0
k0
for(j0j{
cout<if(ary1[j][3]2)
{
ary2[k][0]ary1[j][0]
ary2[k][1]ary1[j][1]
ary2[k][2]ary1[j][2]
k++
}
}
nk
vision()
}
}
else{剩较复杂四种情况
if((ary1[recycle2][3]2)&&(ary1[recycle][3]2))回收区邻接着空闲盘块连接着已分配盘块
{cout<<回收区邻接着空闲盘块连接着已分配盘块<streamopen(huishoutxt iosapp)
stream<<回收区邻接着空闲盘块连接着已分配盘块<streamclose()
ary1[recycle2][1]ary1[recycle2][1]+ary1[recycle1][1]
for(irecycle1i{
ary1[i][0]ary1[i+1][0]1
ary1[i][1]ary1[i+1][1]
ary1[i][2]ary1[i+1][2]
ary1[i][3]ary1[i+1][3]
}
m
k0
for(j0j{
cout<if(ary1[j][3]2)
{
ary2[k][0]ary1[j][0]
ary2[k][1]ary1[j][1]
ary2[k][2]ary1[j][2]
k++
}
}
nk
vision()
}
if((ary1[recycle][3]2)&&(ary1[recycle2][3]2))回收区邻接着空闲盘块邻接着已分配盘块
{
cout<<回收区邻接着空闲盘块邻接着已分配盘块<streamopen(huishoutxt iosapp)
stream<<回收区邻接着空闲盘块邻接着已分配盘块<streamclose()
ary1[recycle2][3]0
ary1[recycle2][1]ary1[recycle2][1]+ary1[recycle1][1]
for(irecycle1i{
ary1[i][0]ary1[i+1][0]1
ary1[i][1]ary1[i+1][1]
ary1[i][2]ary1[i+1][2]
ary1[i][3]ary1[i+1][3]
}
m
k0
for(j0j{
cout<if(ary1[j][3]2)
{
ary2[k][0]ary1[j][0]
ary2[k][1]ary1[j][1]
ary2[k][2]ary1[j][2]
k++
}
}
nk
vision()
}
if((ary1[recycle2][3]2)&&(ary1[recycle][3]2))回收区连接空闲盘块
{
cout<<回收区连接空闲盘块<streamopen(huishoutxt iosapp)
stream<<回收区邻接着空闲盘块邻接着已分配盘块<streamclose()
ary1[recycle2][1]ary1[recycle2][1]+ary1[recycle1][1]+ary1[recycle][1]
cout<<回收区连接空闲盘块<cout< for(irecycle+1i {
ary1[recycle1][0]ary1[recycle+1][0]2
ary1[recycle1][1]ary1[recycle+1][1]
ary1[recycle1][2]ary1[recycle+1][2]
ary1[recycle1][3]ary1[recycle+1][3]
}
mm2
k0
for(j0j{
cout<if(ary1[j][3]2)
{
ary2[k][0]ary1[j][0]
ary2[k][1]ary1[j][1]
ary2[k][2]ary1[j][2]
k++
}
}
nk
vision()
}
if((ary1[recycle2][3]2)&&(ary1[recycle][3]2))空闲区邻接已分配盘块
{
ary1[recycle1][3]0
k0
for(j0j{
cout<if(ary1[j][3]2)
{
ary2[k][0]ary1[j][0]
ary2[k][1]ary1[j][1]
ary2[k][2]ary1[j][2]
k++
}
}
nk
vision()
}
}
}
}
紧凑算法
void compact(){
int id10记录已分配存数量
int id2循环量
int num_avl记录空闲盘块数量
int sum_avl0总空闲区
int num_apl0
统计总空闲区
vision()
for(id20id2{
sum_avlsum_avl+ary2[id2][1]
}
for(id20id2{
if(ary1[id2][3]2)
{
ary1[num_apl][0]num_apl+1
ary1[num_apl][1]ary1[id2][1]
if(num_apl0)
{
ary1[num_apl][2]0
}else{
ary1[num_apl][2]ary1[num_apl1][1]+ary1[num_apl1][2]
}
ary1[num_apl][3]2
num_apl++
cout<}
}
块空闲块
ary1[num_apl][0]num_apl+1
ary1[num_apl][1]sum_avl
ary1[num_apl][2]ary1[num_apl1][1]+ary1[num_apl1][2]
ary1[num_apl][3]0
mnum_apl+1包括空闲区
num_avl0
for(id20id2{
if(ary1[id2][3]2)
{
ary2[num_avl][0]ary1[id2][0]
ary2[num_avl][1]ary1[id2][1]
ary2[num_avl][2]ary1[id2][2]
num_avl++
}
}
nnum_avl
vision()
}
函数入口
void main()
{
int i
int j
int num
int choice1 操作选择标记
int choice2
int flag1 标记否执行
while(flag1){
cout<<********************************************<cout<<****** 信息产生方式 ******< cout<<****** 1 动生成 2 手动输入 ******< cout<<********************************************< cout<<请选择产生存分区作业信息方式
cin>>choice1
if(choice11)
{
numrand()&10
qnum
int id32+rand()8
mid3存区数量
create_apply()
create_pro()
}
if(choice12)
{
create_zuoye()
create_fenqu()
}
vision()
cout<<**请选择处理算法**<cout<<**1首次适应算法2循环首次适应算法3佳适应算法 **< cout<<**4坏适应算法5紧凑算法6回收算法 **< cout<<****< cin>>id1
if(id11) {first_fit()}
if(id12) {next_fit()}
if(id13) {best_fit()}
if(id14) {worst_fit()}
if(id15) { compact()}
if(id16) {
cout<<*******************生成存状态******************<int id3rand()10
m5存区数量
create_apply()
vision()
cout<<请您空闲列表中选出需回收存块(必须已分配):<cin>>recycle
if((recycle>m)||(recycle<1))
{
cout<<错误存中存块<}else{
int id29999
for(i0iif(ary2[i][0]recycle) {
cout<<错误:输入空闲盘块<id21
break
}
}
if(id29999){
apply_recycle()}
}
}
cout<<**************************** <cout<< 否继续演示算法< cout<< 1 0否 < cout<<**************************** < int o
cin>>o
flago
}
}
合 肥 工 ye 学
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容,不代表《香当网》观点或立场,请自行判断内容的真实性和可靠性!
该内容是文档的文本内容,更好的格式请下载文档