（推荐）操作系统课程设计

如果您需要使用本文档，请点击下载按钮下载! 合肥工业大学宣城校区 操作系统 课程设计报告 课程设计题目：动态分区分配存储管理 学生姓名： 方晨宇 学号： 2014217143 专业班级： 物联网1班 指导老师： 田卫东 院系名称： 信息工程系 2016年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空闲分区的数据结构-循环双向链表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+语言在VS2013中实现的四、重要算法和设计思路描述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 #include #include #include #include ProcessQueue.h#includeFreeList.husing 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 nChoice;如果您需要使用本文档，请点击下载按钮下载!switch (nChoice)case 0: /退出cout 当前选择操作：退出。 endl;cout endl; /选择退出break;case 1:system(cls); /清除屏幕int sum;cout 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 进程大小和请求服务时间： sizeexecTime;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 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 - 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) 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) 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 data.size) /找到了更小可以装下的进程，则替换掉minNode = p;p = p-next;if (!minNode) /所有的点都比进程小，则返回falsereturn false;/将最小找到的可以装下的结点分配给进程/如果小于最小分割区间则整体分割if (minNode-data.size - process.size) 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) 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 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) 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 next-data.StartPosition)if (process.StartPosition = (freenode-data.StartPosition + freenode-data.size) & (process.StartPosition + process.memSize) next-data.StartPosition)如果您需要使用本文档，请点击下载按钮下载! /只与左相邻freenode-data.size += process.memSize;return true;else if (process.StartPosition + process.memSize) = freenode-next-data.StartPosition) & (process.StartPosition (freenode-data.StartPosition + freenode-data.size) /只与右相邻freenode-next-data.StartPosition = process.StartPosition;freenode-next-data.size += process.memSize;return true;else if (process.StartPosition + process.memSize) = freenode-next-data.StartPosition) & (process.StartPosition = (freenode-data.StartPosition + freenode-data.size) /既与左相邻又与右相邻freenode-data.size = freenode-data.size + process.memSize + freenode-next-data.size;listDelete(freenode-next); /删除后面的结点return true;else /都不相邻inode = new fnode;inode-data.size = process.memSize;inode-data.StartPosition = process.StartPosition;listInsert(inode, freenode-next);return true;如果您需要使用本文档，请点击下载按钮下载!freenode = freenode-next;return false;void FreeList:showFreeList()out.open(out.txt, ios:out | ios:app); /打开日志文件fnode * p;p = head-next;cout StartPosition size endl;out StartPosition size endl;while (p != head)cout data.StartPosition t data.size endl;out data.StartPosition t data.size next;out.close(); /关闭日志文件void FreeList:setHead(fNode * Head)head = Head;#include ProcessQueue.h如果您需要使用本文档，请点击下载按钮下载!ProcessQueue:ProcessQueue()front = new pnode; /产生头结点，指针为front;rear = front;front-next = NULL;ProcessQueue:ProcessQueue()pnode *p, *u;p = front;while (p)u = p;p = p-next;delete(u);front = NULL;rear = NULL;/判队空bool ProcessQueue:queueEmpty()if (front = rear)return true; /队空，返回trueelsereturn false; /队不空如果您需要使用本文档，请点击下载按钮下载!/取队头元素bool ProcessQueue:getFront(PelementType &x)if (queueEmpty()return false; /队空elsex = front-next-data; /front指示的下一个单元才是队头元素return true;/入队（插入）void ProcessQueue:inQueue(PelementType x)pnode* P = new pnode; /申请内存，产生新节点P-data = x;P-next = NULL;rear-next = P;rear = P; /尾指针指向新的节点（新队尾）/出队（删除）*这里有些疑问？void ProcessQueue:outQueue(pnode * &position)pnode * u;u = position-next;position-next = u-next;如果您需要使用本文档，请点击下载按钮下载!delete u;/自动产生进程void ProcessQueue:autoCreatProcess(unsigned int sum)/static unsigned int id = 0;srand(unsigned)time(NULL); /产生随机数种子pnode * process;/unsigned int ssize, sexecTime; /随机大小和随机服务时间for (unsigned int i = 0; i data.ID = (id+);process-data.size = (unsigned int)1024 + rand() % 1073741824; /大小的范围在1k-1G之间process-data.execTime = (unsigned int)5 + rand() % 30; /服务时间的范围在5-35之间/插入结点process-next = NULL;rear-next = process;rear = process;/手工输入进程void ProcessQueue:manualCreatProcess(unsigned int size,unsigned int execTime)pnode * process;如果您需要使用本文档，请点击下载按钮下载!process = new pnode;process-data.ID = (id+);process-data.size = size;process-data.execTime = execTime;/插入队尾process-next = NULL;rear-next = process;rear = process;/显示内存的分配状况和执行情况void ProcessQueue:showProcess()out.open(out.txt, ios:out|ios:app); /打开日志文件pnode * process;if (queueEmpty()cout 队列中无进程 next;cout ID size execTime usedTime status StartPosition memSize endl;out ID size execTime usedTime status StartPosition memSize endl;while (process != NULL)cout data.IDtdata.size t proces