动态分区分配.docx
《动态分区分配.docx》由会员分享,可在线阅读,更多相关《动态分区分配.docx(22页珍藏版)》请在冰点文库上搜索。
动态分区分配
操作系统课程设计
动态分区分配
学院
专业
学号
学生姓名
指导教师姓名
2014年3月12日
目录
一、引言1
二、总体设计2
1.数据处理类设计2
2.相关消息映射设计3
3.相关流图5
三、实验验证6
1.结果截图6
2.代码分析9
四、总结15
五、参考资料16
一、引言
连续分配方式,是指为一个用户程序分配一个连续的内存空间。
这种分配方式曾被广泛应用于20世纪60~70年代的OS中,它至今仍在内存分配方式中占有一席之地;又可把连续分配方式进一步分为单一连续分配、固定分区分配、动态分区分配以及动态重定位分区分配四种方式。
动态分区分配是根据进程的实际需要,动态地为之分配内存空间。
在实现可变分区分配时,将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配与回收操作这样的三个问题。
最佳适应算法(bestfit)
所谓“最佳”是指每次为作业分配内存时,总是把能满足要求、又是最小的空闲分区分配给作业,避免“大财小用”。
为了加速寻找,该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一个空闲分区链。
这样,第一次找到的能满足要求的空闲区,必然是最佳的。
最坏适应算法(worstfit)
最坏适应算法与最佳适应算法对应,具体实现过程中,仅仅对空闲分区链的创建不同。
最坏适应算法是以从大到小的方式创建的。
本次课设,对最佳适应算法与最坏适应算法两种算法进行模拟,程序的数据处理由标准的C++类设计完成。
程序采用了可视化程序界面的设计方法,协调完成各项要求。
【关键词】操作系统课设,动态分区分配,C++,MFC。
二、总体设计
1.数据处理类设计
数据处理是本次实验的设计的核心,具体算法的实现均是在此类中设计完成的。
作业节点类(classpcb)作为内嵌类,该类的主要作用是作为相关分区链节点。
该类的定义如下:
classpcb
{
private:
intID;
intFirstAddr;
intlen;
intarrive_time;
intholding_time;
intrun_time;
public:
pcb(){ID=0;FirstAddr=len=arrive_time=holding_time=run_time=0;}
voidsetID(intN){ID=N;}
voidsetFA(intfa){FirstAddr=fa;}
voidsetLen(intl){len=l;}
voidsetAT(intat){arrive_time=at;}
voidsetHT(intht){holding_time=ht;}
voidsetRT(intrt){run_time=rt;}
intgetFA()const{returnFirstAddr;}
intgetLen()const{returnlen;}
intgetAT()const{returnarrive_time;}
intgetHT()const{returnholding_time;}
intgetRT()const{returnrun_time;}
intgetID()const{returnID;}};
分区链类主要处理空闲分区节点和作业节点的分配,实现最佳分配算法和最坏分配算法。
采用双链表组织各节点,采用了快速排序算法对空闲分区节点进行排序,使用了Vector容器对相关结果的保存。
具体代码设计如下:
classMemory
{
private:
structNode{intstyle;memItemitem;Node*prior;Node*next;};
constlongintMAXLEN;
intchoose;
intrunning_time;//程序运行时间,建立时间轴
CListCtrl*m_plistFT;
CListCtrl*m_plistPcb;
private:
Node*front;
Node*rear;
private:
vector>FTvec;
intsplit(vector>&vec,intlow,inthigh);
voidquick_sort(vector>&vec,intlow,inthigh);
intlsplit(vector>&vec,intlow,inthigh);
voidlquick_sort(vector>&vec,intlow,inthigh);
intcaculFTnum();//计算空闲分区表的个数
boolenFTVec();//加空闲分区表节点到FTvec向量中
private:
Memory(constMemory*f):
MAXLEN(0){}
Memory&operator=(constMemory*f){return*this;}
boolinitMemory();
boolenqueue(memItem&item);
boolenqueue(Node*p,memItem&item);
boolnewFTNode(memItem&item);
public:
Memory(intmax);
~Memory();
inttotal;
boolrequest(memItem&item);
boolrelease(intID);
boolsetChoose(int);
boolshowFT();
boolshowPCB();
boolrunning();
boolinitList(CListCtrl*list1,CListCtrl*list2);
boolclear();
private:
boolBestFit(memItem&item);
boolWorstFit(memItem&item);
};
2.相关消息映射设计
可视化程序设计的核心之一便是各消息映射的设计与相关类之间的通信。
本次实验采用对话框型MFC程序为设计基础。
所使用到的控件类型分别有:
单选框、按钮、编辑控件。
列表控件。
设计界面如下:
单选框控件:
通过在OnInitDialog()方法中调用CheckRadioButton(IDC_RADIO1,IDC_RADIO2,IDC_RADIO1);完成对单选框控件的初始化工作。
通过intnID=GetCheckedRadioButton(IDC_RADIO1,IDC_RADIO2);检查单选按钮的值。
列表控件:
在列表控件的属性中设置Style类型为Report(报表)类型,在OnInitDialog()方法中对两个列表控件进行初始化。
m_listPcb.InsertColumn(0,"进程名",LVCFMT_LEFT);
m_listPcb.InsertColumn(1,"首址",LVCFMT_LEFT);
m_listPcb.InsertColumn(2,"长度",LVCFMT_LEFT);
m_listPcb.InsertColumn(3,"AT",LVCFMT_LEFT);
m_listPcb.InsertColumn(4,"RT",LVCFMT_LEFT);
m_listPcb.InsertColumn(5,"HT",LVCFMT_LEFT);
m_listFT.InsertColumn(0,"首址",LVCFMT_LEFT);
m_listFT.InsertColumn(1,"长度",LVCFMT_LEFT);
RECTrect_pcb,rect_ft;
m_listPcb.GetWindowRect(&rect_pcb);
m_listFT.GetWindowRect(&rect_ft);
intwid_pcb=rect_pcb.right-rect_pcb.left;
intwid_ft=rect_ft.right-rect_ft.left;
//设置列表控件列宽度
m_listPcb.SetColumnWidth(0,wid_pcb/6);
m_listPcb.SetColumnWidth(1,wid_pcb/6);
m_listPcb.SetColumnWidth(2,wid_pcb/6);
m_listPcb.SetColumnWidth(3,wid_pcb/6);
m_listPcb.SetColumnWidth(4,wid_pcb/6);
m_listPcb.SetColumnWidth(5,wid_pcb/6);
m_listFT.SetColumnWidth(0,wid_ft/2);
m_listFT.SetColumnWidth(1,wid_ft/2);
//设置列表控件边线可见
m_listPcb.SetExtendedStyle(LVS_EX_GRIDLINES);
m_listFT.SetExtendedStyle(LVS_EX_GRIDLINES);
其余控件的具体实现,请见实验验证部分的代码分析章节。
3.相关流图
三、实验验证
1.结果截图
数据初始化方式之一从文件导入,导入文件类型为txt文本格式。
点击打开,提示文件导入成功。
点击开始,执行通过单选框选择的分配算法并且在列表控件中显示分配结果。
点击暂停按钮,停止执行。
模拟完毕按钮提示模拟完成。
上图显示了静态初始化结果,静态初始化由程序内部初始化序列。
图中显示清空原有数据,清空数据以便于继续进行模拟。
图中显示从键盘输入相关数据初始化输入情况。
2.代码分析
三种初始化数据代码,分别在各自ID控件按钮的消息响应代码中:
静态初始化:
voidCDyPartitionDlg:
:
OnBnClickedBtnStatic()
{
//TODO:
在此添加控件通知处理程序代码
MessageBox("静态初始化为8个作业序列");
m_intPcbNum=8;
m_strLenTable="4101534159";
m_strATTable="12345678";
m_strRTTable="23413242";
}
输入按钮:
voidCDyPartitionDlg:
:
OnBnClickedBtnInput()
{
//TODO:
在此添加控件通知处理程序代码
CInputDlginputdlg;
if(inputdlg.DoModal()!
=IDOK)
{
MessageBox("输入窗口打开失败!
","错误",MB_ICONHAND);
return;
}
m_intPcbNum=inputdlg.m_intPcbNum;
m_strATTable=inputdlg.m_strATTable;
m_strLenTable=inputdlg.m_strLenTable;
m_strRTTable=inputdlg.m_strRTTable;
if(m_strLenTable.GetLength()>1)
{
MessageBox("输入成功","提示");
return;
}
}
文件读取操作:
//文件读取操作
voidCDyPartitionDlg:
:
OnBnClickedBtnOpen()
{
//TODO:
在此添加控件通知处理程序代码
CFileDialogfiledlg(TRUE);
//改变保存文本框的标题
filedlg.m_ofn.lpstrTitle="打开文件";
//设置文件过滤器
filedlg.m_ofn.lpstrFilter="文本文件(*.txt)\0*.txt\0所有文件(*.*)\0*.*\0\0";
if(IDOK==filedlg.DoModal())
{
//获得文件路径
CStringstrPathName=filedlg.GetPathName();
CStdioFilefile;
//打开文件
if(!
file.Open(strPathName,CFile:
:
modeRead))
{
:
:
AfxMessageBox("文件打开失败!
");
return;
}
//读文件
CStringstrText="";
while(file.ReadString(strText))
{
chartype=strText.GetAt(0);
switch(type)
{
case'1':
{
CStringsubStr;
subStr=strText.Mid(strText.Find(':
')+1);
m_intPcbNum=:
:
atoi((LPCTSTR)(subStr));
break;
}
case'2':
m_strLenTable=strText.Mid(strText.Find(':
')+1);
break;
case'3':
m_strATTable=strText.Mid(strText.Find(':
')+1);
break;
case'4':
m_strRTTable=strText.Mid(strText.Find(':
')+1);
break;
default:
break;
}
}
}
if(m_strLenTable.GetLength()>0)
{
MessageBox("文件导入成功","提示",MB_ICONASTERISK);
return;
}
}
开始按钮:
voidCDyPartitionDlg:
:
OnBnClickedBtnStart()
{
//TODO:
在此添加控件通知处理程序代码
//检查两个单选框
intnID=GetCheckedRadioButton(IDC_RADIO1,IDC_RADIO2);
if(nID==IDC_RADIO1)
{
test.setChoose
(1);
}
else
if(nID==IDC_RADIO2)
{
test.setChoose
(2);
}
convert_data(m_strLenTable,1);
convert_data(m_strATTable,2);
convert_data(m_strRTTable,3);
//传送两个ListCtrl控件的地址
test.initList(&m_listFT,&m_listPcb);
m_bBtn_start=!
m_bBtn_start;
CWnd*MyWnd=GetDlgItem(IDC_BTN_START);
if(m_bBtn_start==true)
{
MyWnd->SetWindowTextA("停止");
SetTimer(1,1000,NULL);
}
else
{
MyWnd->SetWindowTextA("开始");
KillTimer
(1);
}
}
上述类中实现了对WM_TIME消息的响应,并且设置了两个事件响应,分别对应数据处理中的不同的操作。
其消息响应函数编写如下:
voidCDyPartitionDlg:
:
OnTimer(UINT_PTRnIDEvent)
{
CDialog:
:
OnTimer(nIDEvent);
switch(nIDEvent)
{
case1:
{
staticintID=1;
//staticinti=0;
if(m_intIndex{
memItemitem;
item.setID(ID++);
item.setLen(len_table[m_intIndex]);
item.setAT(arrive_time_table[m_intIndex]);
item.setRT(run_time_table[m_intIndex++]);
test.request(item);
test.showFT();
test.showPCB();
Sleep(1000);
}
else
{
if(test.total>1)
SetTimer(2,1000,NULL);
}
break;
}
case2:
{
test.running();
if(test.total>1)
{
test.showFT();
test.showPCB();
Sleep(1000);
}
else
{
test.showFT();
m_listPcb.DeleteAllItems();
KillTimer
(2);
CWnd*MyWnd=GetDlgItem(IDC_BTN_START);
MyWnd->SetWindowTextA("模拟完成");
}
break;
}
}
}
该函数具体上通过调用Memory实例化的test对象中的成员函数,完成相关的动态分区分配操作,并且在start按钮的消息响应函数中传给该类中的两个CListCtrl控件的地址,实现对数据的动态显示操作。
Convert_data()函数实现相关的数据格式化工作:
boolCDyPartitionDlg:
:
convert_data(CString&str,intstyle)
{
stringcstr=str.GetBuffer(0);
cstr.push_back('');
string:
:
iteratorpcstr=cstr.begin();
stringinteger;
intindex=0;
switch(style)
{
case1:
{
while(pcstr!
=cstr.end())
{
if(*pcstr!
='')
integer.push_back(*pcstr);
else
{
len_table[index++]=:
:
atoi(integer.data());
integer.clear();
}
pcstr++;
}
break;
}
case2:
{
while(pcstr!
=cstr.end())
{
if(*pcstr!
='')
integer.push_back(*pcstr);
else
{
arrive_time_table[index++]=:
:
atoi(integer.data());
integer.clear();
}
pcstr++;
}
break;
}
case3:
{
while(pcstr!
=cstr.end())
{
if(*pcstr!
='')
integer.push_back(*pcstr);
else
{
run_time_table[index++]=:
:
atoi(integer.data());
integer.clear();
}
pcstr++;
}
break;
}
default:
break;
}
returntrue;
}
通过响应WM_NCHITTEST()消息,达到了控制鼠标在客户区的不同区域的响应。
其消息响应函数编写如下,实验中屏蔽了窗口的水平和垂直放大的操作:
LRESULTCDyPartitionDlg:
:
OnNcHitTest(CPointpoint)
{
intret=CDialog:
:
OnNcHitTest(point);
if(HTTOP==ret||HTBOTTOM==ret||HTLEFT==ret||HTRIGHT==ret
||HTBOTTOMLEFT==ret||HTBOTTOMRIGHT==ret||HTTOPLEFT==ret||HTTOPRIGHT==ret
/*||HTCAPTION==ret*/)
returnHTCLIENT;
returnret;
}
四、总结
1.通过本次课设试验,复习了相关操作系统知识点。
总体上掌握MFC可视化程序的开发流程,熟悉了多种MFC控件的响应以及设计。
2.开发过程遇到了很多问题,诸如:
在释放内存中的相应的作业时,由于对双链表指针的操作有误,导致最后在程序可视化程序中的直接体现是:
程序严重崩溃。
通过运用以往的经验,快速定位到错误位置,并且通过一步步的加断点调试,最终发现是两条代码的操作先后出现了混乱。
等等,相关的错误。
3.MFC程序设计初期需要有一个良好的架构!
本次课设中,由于对某些方面考虑不是很充分(这里特指MFC绘图操作),导致在对话框程序中后期设计相关的操作的时候,变得异常麻烦,最终不得不放弃。
4.MFC类与标准C++类之间的交互应当在初期能有个较好的规划,以免在后