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

合肥工业大学宣城校区 操作系统 课程设计报告 课程设计题目：动态分区别配存储管理 学生姓名： 方晨宇 学号： 217143 专业班级： 物联网1班 指引教师： 田卫东 院系名称： 信息工程系 12月23日一、课程设计概述41.1设计任务41.2设计规定41.3设计目4二、原理及算法描述42.1动态分区别配算法原理42.1.1 初次适应算法42.1.2 循环初次适应算法52.1.3 最佳适应算法52.1.4 最坏适应算法52.1.5 紧凑算法6三、开发环境6四、重要算法和设计思路描述64.1设计 初次适应算法64.2设计 循环初次适应算法64.3设计 最佳适应算法64.4设计 最坏适应算法74.5设计分区回收算法74.6设计紧凑算法7五、程序实现-数据构造75.1空闲分区数据构造-循环双向链表75.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 fDataunsigned 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 pDataunsigned 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 messageSetTimer(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 a5;cin.getline(a,10);while (a0!='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;elsereturn false;/在指定位置删除结点bool FreeList:listDelete(fnode * position)if (position && (position != head) /该节点必要不为空并且还不是指向头结点position->next->prior = position->prior;position->prior->next = position->next;delete position;return true;elsereturn 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； /状态置1process.memSize = freenode->data.size;process.StartPosition = freenode->data.StartPosition;listDelete(freenode)； /删除该节点return true;else /否则按需分割，别的某些留下来process.status = 1； /状态置1process.memSize = process.size； /拟定实际占用位置process.StartPosition = freenode->data.StartPosition； /拟定所占起始位置freenode->data.size -= process.size； /新sizefreenode->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； /状态置1process.memSize = freenode->data.size;process.StartPosition = freenode->data.StartPosition;listDelete(freenode)； /删除该节点return true;else /否则按需分割，别的某些留下来process.status = 1； /状态置1process.memSize = process.size； /拟定实际占用位置process.StartPosition = freenode->data.StartPosition； /拟定所占起始位置freenode->data.size -= process.size； /新sizefreenode->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) /所有点都比进程小，则返回falsereturn false;/将最小找到可以装下结点分派给进程/如果不大于最小分割区间则整体分割if (minNode->data.size - process.size) < uSIZE)process.status = 1； /状态置1process.memSize = minNode->data.size;process.StartPosition = minNode->data.StartPosition;listDelete(minNode)； /删除该节点else /否则按需分割，别的某些留下来process.status = 1； /状态置1process.memSize = process.size； /拟定实际占用位置process.StartPosition = minNode->data.StartPosition； /拟定所占起始位置minNode->data.size -= process.size； /新sizeminNode->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) /所有点都比进程小，则返回falsereturn false;/将最小找到可以装下结点分派给进程/如果不大于最小分割区间则整体分割if (maxNode->data.size - process.size) < uSIZE)process.status = 1； /状态置1process.memSize = maxNode->data.size;process.StartPosition = maxNode->data.StartPosition;listDelete(maxNode)； /删除该节点else /否则按需分割，别的某些留下来process.status = 1； /状态置1process.memSize = process.size； /拟定实际占用位置process.StartPosition = maxNode->data.StartPosition； /拟定所占起始位置maxNode->data.size -= process.size； /新sizemaxNode->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;elsereturn 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;elsereturn false;/如果在中间某处if (process.StartPosition > freenode->data.StartPosition&&process.StartPosition < freenode->next->data.StartPosition)