操作系统专业课程设计范本.doc

合肥工业大学宣城校区
《操作系统》
课程设计报告
课程设计题目：动态分区别配存储管理
学生姓名： 方晨宇
学号： 217143
专业班级： 物联网1班
指引教师： 田卫东
院系名称： 信息工程系

12月23日

一、课程设计概述 4
1.1设计任务 4
1.2设计规定 4
1.3设计目 4
二、原理及算法描述 4
2.1动态分区别配算法原理 4
2.1.1 初次适应算法 4
2.1.2 循环初次适应算法 5
2.1.3 最佳适应算法 5
2.1.4 最坏适应算法 5
2.1.5 紧凑算法 6
三、开发环境 6
四、重要算法和设计思路描述 6
4.1设计 初次适应算法 6
4.2设计 循环初次适应算法 6
4.3设计 最佳适应算法 6
4.4设计 最坏适应算法 7
4.5设计分区回收算法 7
4.6设计紧凑算法 7
五、程序实现-数据构造 7
5.1空闲分区数据构造----循环双向链表 7
5.2进程数据构造---单向循环队列 8
六、程序实现---程序清单 9
七、总结 41

一、课程设计概述
1.1设计任务
动态分区别配存储管理
1.2设计规定
1.建立描述内存分派状况数据构造；
2.建立描述进程数据构造；
3.使用两种方式产生进程：a 自动产生 b手动输入；
4.在屏幕上显示内存分派状况，每个进程执行状况；
5.建立分区别配和回收算法，支持紧凑算法；
6.时间流逝可用下面几种办法模仿：a按键盘，每按一次可以为过一种时间单位；b响应WM-TIMER;
7.将一批进程执行状况存入磁盘文献，后来可以读出并重放；
8.支持算法：初次适应算法，循环初次适应算法，最佳适应算法，最坏适应算法；
1.3设计目
旨在让咱们更好理解动态分区管理方面知识。
二、原理及算法描述
2.1动态分区别配算法原理
2.1.1 初次适应算法
*算法概述：分派内存时，从链首开始顺序查找，找到满足空闲分区则划出空间分派，余下空闲空间仍保存在空闲链表中
*实现算法：分派时从空闲链表第一种空闲节点查找，若找到可以放下当迈进程空闲节点，则分派
2.1.2 循环初次适应算法
*算法描述：由初次适应算法演变，只是每次分派改为由上一次找到空闲分区开始查找适当空闲节点
*实现算法：在初次适应算法基本上，将指针置为static，不必每次从头查找空闲分区
2.1.3 最佳适应算法
*算法描述：每次为作业分派内存时，总是把能满足规定、又是最小空闲分区别配给作业
*实现算法：每次为进程分派内存时，查找能放下该进程并且是最小空闲分区，避免了每次将空闲分区从小到大排序。
2.1.4 最坏适应算法
*算法描述：每次为作业分派内存时，总是挑选一种最大空闲分区别割给作业使用
*算法实现：算法与最佳适应算法几乎相似，每次查找最大空闲分区节点，将其分派给进程。
回收分区：
当进程运营完毕释放内存时,系统依照回收区首址,从空闲区链(表)中找到相应插入点,此时也许浮现如下四种状况之一；
1)回收区与插入点前一种空闲分区F1相邻接,此时应将回收区与插入点前一分区合并,不必为回收区别配新表项,而只需修改其前一分区F1大小.
2)回收分区与插入点后一空闲分区F2相邻接,此时也可将两分区合并,形成新空闲分区,但用回收区首址作为新空闲区首址,大小为两者之和.
3)回收区同步与插入点前,后两个分区邻接,此时将三个分区合并,使用F1表项和F1首址,取消F2表项,大小为三者之和.
4)回收区既不与F1相邻接,又不与F2邻接.这时应为回收区单独建立一新表项,填写回收区首址和大小,并依照其首址插入到空闲链中恰当位置.
2.1.5 紧凑算法
通过修改每个进程在内存中标志位status，虚拟将进程重新分派到内存中，此时分派满足紧凑，避免移动所有在内存中进程
三、开发环境
此程序是本小组运用c++语言在VS中实现
四、重要算法和设计思路描述
4.1设计 初次适应算法
每次为进程分派内存时，都一方面从双向空闲链表第一种空闲节点开始查找，如果该空闲分区只比进程大一点点，则把该空闲分区全某些配给该进程，之后删除该空闲节点；如果空闲分区比进程大诸多，则按需分派，修改该空闲区起始位置和大小；运用循环依次查找各个节点，为进程分派内存。当指针指向头结点时，阐明空闲链表已经查找完毕，没有适当空闲分区为该进程分派，return FALSE。
4.2设计 循环初次适应算法
与初次适应算法类似，只但是每次为进程分派内存时，不再指向空闲链表头部，设立指向头部指针是静态static，运营期间不再变化，则每次分派时从上一次分派空闲分区下一种开始。
4.3设计 最佳适应算法
依照最佳适应算法原理，每次从最小并且能放下该进程空闲分区开始分派，于是设计算法，每次查找空闲链表中最小并且能放下该进程空闲分区，避免了将空闲分区链表每次从小到大排序，提高效率。
4.4设计 最坏适应算法
与最佳适应算法类似，每次查找空闲链表中最大空闲分区进行分派，避免了将空闲分区链表每次从大到小排序，提高效率。
4.5设计分区回收算法
设计一种函数，时刻检查进程运营状态，当进程已经运营完毕，则回收该进程所占用内存分区。对内存分区状态进行查找,若回收区与插入点前一种空闲分区F1相邻接,此时应将回收区与插入点前一分区合并,不必为回收区别配新表项,而只需修改其前一分区F1大小.若回收分区与插入点后一空闲分区F2相邻接,此时也可将两分区合并,形成新空闲分区,但用回收区首址作为新空闲区首址,大小为两者之和.若回收区同步与插入点前,后两个分区邻接,此时将三个分区合并,使用F1表项和F1首址,取消F2表项,大小为三者之和.若回收区既不与F1相邻接,又不与F2邻接.这时应为回收区单独建立一新表项,填写回收区首址和大小,并依照其首址插入到空闲链中恰当位置。
4.6设计紧凑算法
通过修改每个进程在内存中标志位status，虚拟将进程重新分派到内存中，此时分派满足紧凑，避免移动所有在内存中进程
五、程序实现-数据构造
5.1空闲分区数据构造----循环双向链表
typedef struct fData
{
unsigned int size;
unsigned int StartPosition;
}fdata;
FreeList::FreeList()
{
//建立头结点
head = new fnode;
head->prior = head;
head->next = head;

//在建立第一种结点并指向整个内存空间
fnode *p，*s;
p = head->next;

s = new fnode;
s->data.size = MEMORY_MAX;
s->data.StartPosition = 0;

s->next = p;
s->prior = p->prior;
p->prior->next = s;
p->prior = s;
}
5.2进程数据构造---单向循环队列
typedef struct pData
{
unsigned int ID;
unsigned int size； //所占内存空间
unsigned int execTime； //规定服务时间
unsigned int usedTime=0； //已经运营时间
bool status = 0； //0没有调入内存，1调入内存
unsigned int StartPosition； //调入内存中始址
unsigned int memSize = 0； //在内存中实际占用内存空间
}pdata;
ProcessQueue::ProcessQueue()
{
front = new pnode； //产生头结点，指针为front;
rear = front;
front->next = NULL;
}
六、程序实现---程序清单
#include <windows.h>
#include <iostream>
#include <cstdlib>
#include <ctime>

#include "ProcessQueue.h"
#include"FreeList.h"

using namespace std;

//全局变量
ProcessQueue processqueue;
FreeList freelist;

void CALLBACK TimerProc(HWND hwnd，UINT Msg，UINT idEvent，DWORD dwTime);
void CALLBACK TimerProcBF(HWND hwnd，UINT Msg，UINT idEvent，DWORD dwTime);

int main(int argc，char* argv[])
{
out.open("out.txt"，ios::out | ios::trunc)； //打开日记文献
out.close()； //关闭日记文献

FreeList freelist1；//中间文献

int nChoice = -1；//操作选取
do
{
//显示主菜单
cout << "*******动态分区测试程序********" << endl;
cout << "* 0-退出 *" << endl;
cout << "* 1-自动产生进程 *" << endl;
cout << "* 2-进行一次分派 *" << endl;
cout << "* 3-初次适应算法 *" << endl;
cout << "*-----------------------------*" << endl;
cout << "* 4-最佳适应算法 *" << endl;
cout << "* 5-手动输入进程 *" << endl;
cout << "* 6-键盘模仿时间 *" << endl;
cout << "* 7-紧凑算法 *" << endl;
cout << "* 8- *" << endl;
cout << "************************** ****" << endl;

cout << "请输入数字选取操作：";
cin >> nChoice;

switch (nChoice)
{
case 0： //退出
cout << "当前选取操作：退出。" << endl;
cout << "<-- 程序退出 -->" << endl； //选取退出
break;

case 1:
system("cls")； //清除屏幕
int sum;
cout << "请输入生成变量个数： ";
cin >> sum;
processqueue.autoCreatProcess(sum);
processqueue.showProcess();
break;

case 2:
system("cls")； //清除屏幕
processqueue.assignMemory(freelist.getHead());
processqueue.showProcess();
break;

case 3:
system("cls")； //清除屏幕

//UINT timerId = 1;
MSG msg;

// int n = GetMessage(&msg，NULL，NULL，NULL)； //Wait for message，block the thread when getting no message

SetTimer(NULL，1，1000，TimerProc)； //每间隔1000毫秒定期器发送 一条信息，并执行回调函数中代码
int nTemp;
while ((nTemp = GetMessage(&msg，NULL，NULL，NULL)) && (-1 != nTemp) && (0 != nTemp))
{
if (WM_TIMER == msg.message)
{
cout << "I got a message" << endl;
TranslateMessage(&msg);
DispatchMessage(&msg);
}
}
break;

case 4:
system("cls")； //清除屏幕

SetTimer(NULL，2，1000，TimerProcBF)； //每间隔1000毫秒定期器发送 一条信息，并执行回调函数中代码
while ((nTemp = GetMessage(&msg，NULL，NULL，NULL)) && (-1 != nTemp) && (0 != nTemp))
{
if (WM_TIMER == msg.message)
{
cout << "I got a message" << endl;
TranslateMessage(&msg);
DispatchMessage(&msg);
}
}
break;

case 5:
system("cls")； //清除屏幕
unsigned int size，execTime;
cout << "进程大小和祈求服务时间： "<<endl;
cin >> size>>execTime;
processqueue.manualCreatProcess(size,execTime);
processqueue.showProcess();
break;

case 6:
system("cls")； //清除屏幕

char a[5];
cin.getline(a,10);
while (a[0]!='0')
{
processqueue.assignMemory(freelist.getHead());
processqueue.timePassed(freelist.getHead());
processqueue.showProcess();
freelist.showFreeList();
out.open("out.txt"，ios::out | ios::app)； //打开日记文献
cout << "---------------------------------------------------" << endl;
out << "---------------------------------------------------" << endl;
out.close()； //关闭日记文献
cin.getline(a，10);
}
break;

case 7:
system("cls")； //清除屏幕
pact();
freelist = freelist1； //也许有内存泄露
processqueue.assignMemory(freelist.getHead());
processqueue.showProcess();
freelist.showFreeList();
cout << "---------------------------------------------------" << endl;
break;

default:
cout << "功能选取错误，请在0到9之间选取，==>" << endl;
break;
}

} while (nChoice != 0);

return 0;
}

void CALLBACK TimerProc(HWND hwnd，UINT Msg，UINT idEvent，DWORD dwTime)
{
processqueue.assignMemory(freelist.getHead());
processqueue.timePassed(freelist.getHead());
processqueue.showProcess();
freelist.showFreeList();

out.open("out.txt"，ios::out | ios::app)； //打开日记文献
cout << "---------------------------------------------------" << endl;
out << "---------------------------------------------------" << endl;
out.close()； //关闭日记文献
}

void CALLBACK TimerProcBF(HWND hwnd，UINT Msg，UINT idEvent，DWORD dwTime)
{
processqueue.assignMemory(freelist.getHead(),bf);
processqueue.timePassed(freelist.getHead());
processqueue.showProcess();
freelist.showFreeList();

out.open("out.txt"，ios::out | ios::app)； //打开日记文献
cout << "---------------------------------------------------" << endl;
out << "---------------------------------------------------" << endl;
out.close()； //关闭日记文献
}
#include "FreeList.h"

FreeList::FreeList()
{
//建立头结点
head = new fnode;
head->prior = head;
head->next = head;

//在建立第一种结点并指向整个内存空间
fnode *p，*s;
p = head->next;

s = new fnode;
s->data.size = MEMORY_MAX;
s->data.StartPosition = 0;

s->next = p;
s->prior = p->prior;
p->prior->next = s;
p->prior = s;
}

FreeList::~FreeList()
{
}

//在指定位置添加结点
bool FreeList::listInsert(fnode * freenode,fnode * position)
{
if (position)
{
freenode->next = position;
freenode->prior = position->prior;
position->prior->next = freenode;
position->prior = freenode;
return true;
}
else
return false;
}

//在指定位置删除结点
bool FreeList::listDelete(fnode * position)
{
if (position && (position != head)) //该节点必要不为空并且还不是指向头结点
{
position->next->prior = position->prior;
position->prior->next = position->next;
delete position;
return true;
}
else
return false;
}

bool FreeList::FF(PelementType &process)
{
fnode * freenode;
freenode = head->next;
while (freenode != head)
{
//先删除找到第一种适当结点
if (freenode->data.size >= process.size)
{
//如果不大于最小分割区间则整体分割
if ((freenode->data.size - process.size) < uSIZE)
{
process.status = 1； //状态置1
process.memSize = freenode->data.size;
process.StartPosition = freenode->data.StartPosition;
listDelete(freenode)； //删除该节点
return true;
}
else //否则按需分割，别的某些留下来
{
process.status = 1； //状态置1
process.memSize = process.size； //拟定实际占用位置
process.StartPosition = freenode->data.StartPosition； //拟定所占起始位置

freenode->data.size -= process.size； //新size
freenode->data.StartPosition = process.StartPosition + process.memSize； //始址加大小
return true;
}
}
freenode = freenode->next;
}
return false;
}

bool FreeList::NF(PelementType &process)
{
static fnode * freenode = head->next;
while (freenode != head)
{
//先删除找到第一种适当结点
if (freenode->data.size >= process.size)
{
//如果不大于最小分割区间则整体分割
if ((freenode->data.size - process.size) < uSIZE)
{
process.status = 1； //状态置1
process.memSize = freenode->data.size;
process.StartPosition = freenode->data.StartPosition;
listDelete(freenode)； //删除该节点
return true;
}
else //否则按需分割，别的某些留下来
{
process.status = 1； //状态置1
process.memSize = process.size； //拟定实际占用位置
process.StartPosition = freenode->data.StartPosition； //拟定所占起始位置

freenode->data.size -= process.size； //新size
freenode->data.StartPosition = process.StartPosition + process.memSize； //始址加大小
return true;
}
}
freenode = freenode->next;
}
return false;
}

bool FreeList::BF(PelementType &process)
{
fnode * minNode=NULL;
fnode *p;
p = head->next;
while (p != head)
{
if (!minNode) //如果还没有找到适当值
{
if (p->data.size > process.size) //找到第一种可以装下进程结点
minNode = p;
}
else //如果有一种值已经可以装下该进程，接下来需要找到最小那个点
{
if ((p->data.size >= process.size) && (p->data.size < minNode->data.size)) //找到了更小可以装下进程，则替代掉
{
minNode = p;
}
}
p = p->next;
}
if (!minNode) //所有点都比进程小，则返回false
return false;

//将最小找到可以装下结点分派给进程
//如果不大于最小分割区间则整体分割
if ((minNode->data.size - process.size) < uSIZE)
{
process.status = 1； //状态置1
process.memSize = minNode->data.size;
process.StartPosition = minNode->data.StartPosition;
listDelete(minNode)； //删除该节点
}
else //否则按需分割，别的某些留下来
{
process.status = 1； //状态置1
process.memSize = process.size； //拟定实际占用位置
process.StartPosition = minNode->data.StartPosition； //拟定所占起始位置

minNode->data.size -= process.size； //新size
minNode->data.StartPosition = process.StartPosition + process.memSize； //始址加大小
}
return true;
}

bool FreeList::WF(PelementType &process)
{
fnode * maxNode = NULL;
fnode *p;
p = head->next;
while (p != head)
{
if (!maxNode) //如果还没有找到适当值
{
if (p->data.size > process.size) //找到第一种可以装下进程结点
maxNode = p;
}
else //如果有一种值已经可以装下该进程，接下来需要找到最小那个点
{
if (p->data.size > maxNode->data.size) //找到了更小可以装下进程，则替代掉
{
maxNode = p;
}
}
p = p->next;
}
if (!maxNode) //所有点都比进程小，则返回false
return false;

//将最小找到可以装下结点分派给进程
//如果不大于最小分割区间则整体分割
if ((maxNode->data.size - process.size) < uSIZE)
{
process.status = 1； //状态置1
process.memSize = maxNode->data.size;
process.StartPosition = maxNode->data.StartPosition;
listDelete(maxNode)； //删除该节点
}
else //否则按需分割，别的某些留下来
{
process.status = 1； //状态置1
process.memSize = process.size； //拟定实际占用位置
process.StartPosition = maxNode->data.StartPosition； //拟定所占起始位置

maxNode->data.size -= process.size； //新size
maxNode->data.StartPosition = process.StartPosition + process.memSize； //始址加大小
}
return true;
}

bool FreeList::memoryRecycle(pData process)
{
fnode * freenode;
fnode * inode； //需要添加结点
freenode = head->next;

//如果在链首
if (process.StartPosition < freenode->data.StartPosition)
{
if ((process.StartPosition + process.memSize) == freenode->data.StartPosition) //如果背面空闲快与其邻接
{
freenode->data.StartPosition = process.StartPosition； //则将起始置为process起始位置
freenode->data.size += process.memSize;
return true;
}
else if ((process.StartPosition + process.memSize) < freenode->data.StartPosition)
{ //添加一种结点
inode = new fnode;
inode->data.size = process.memSize;
inode->data.StartPosition = process.StartPosition;
listInsert(inode，freenode);
return true;
}
else
return false;
}
while (freenode != head)
{
//如果在链尾
if (freenode == head)
{
if (process.StartPosition == (freenode->data.StartPosition + freenode->data.size)) //如果与前一种存储块相邻
{
freenode->data.size += process.memSize;
return true;
}
else if (process.StartPosition > (freenode->data.StartPosition + freenode->data.size))
{ //添加一种结点
inode = new fnode;
inode->data.size = process.memSize;
inode->data.StartPosition = process.StartPosition;
listInsert(inode，freenode->next);
return true;
}
else
return false;
}
//如果在中间某处
if (process.StartPosition > freenode->data.StartPosition&&process.StartPosition < freenode->next->data.StartPosition)