OJ1193内存分配.ppt_第1页
OJ1193内存分配.ppt_第2页
OJ1193内存分配.ppt_第3页
OJ1193内存分配.ppt_第4页
OJ1193内存分配.ppt_第5页
已阅读5页，还剩10页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

内存分配,00201066 张伟,题意描述,内存单元 ，给定一个有n个内存单元组成的内存，有若干程序运行时要占用内存 ，即占用一定长度连续的内存单元。 每个进程有一个申请时刻T，需要内存单元数M及运行时间P。在运行时间P内，这M个被占用的内存单元不能再被其他进程使用。,题意描述,假设在T时刻有一个进程申请M个单元，且运行时间为P，则： 1. 若T时刻内存中存在长度为M的空闲地址片，则系统将这M个空闲单元分配给该进程。若存在多个长度为M个空闲地址片，则系统将首地址最小的那个空闲地址片分配给该进程。,题意描述,如果T时刻不存在长度为M的空闲地址片，则该进程被放入一个等待队列。等待队列队头的进程，只要在任一时刻存在长度为M的空闲地址片，系统马上将该进程取出队列，并为它分配内存单元。在进行内存分配处理过程中，队列中的其它进程不能先于队头进程被处理。,任务：,给出一系列描述进程的数据，模拟系统分配内存的过程。 输出 ： 第一行是全部进程都运行完毕的时刻。 第二行是被放入过等待队列的进程总数。 数据规模 ： 输入文件最多10000行，且所有数据都小于109。,sample 10 1 3 10 2 4 3 3 4 4 4 1 4 5 3 4 0 0 0,算法分析,该题为一模拟题。根据题意我们应在模拟过程中建立一个等待队列。另外，每次为新的进程分配内存时都要查找内存中的空闲位置。要了解在当前时刻内存的占用情况。当然总的内存单元数目太多，我们可以针对相对较少的进程来分析。即建立一个运行队列。,算法分析,1.运行队列与等待队列。 运行队列记录被分配地址的首位置mid及长度m。并记录下完成时间t与指向后进程的指针。 等待队列记录下内存需求量，运行时间及指向下一进程的指针。,算法分析,运行队列的结构： typedef struct node long m,t,mid; node *next; ; 将运行队列中的进程按所占内存的位置从小到大排列。查找内存空闲区域的过程： 如果p-next!=NULL且p-mid+p-m next-mid则在p与p.next 之间存在一块大小为 p.next-mid-(p.mid+p.m) 的空闲空间。,算法分析,2.运行队列的最早结束时间nexttime和最晚结束时间stoptime。,算法分析,算法分析 试图为当前申请的进程分配内存。 在运行序列中查找是否存在某两个进程这间的空闲空间满足要求。存在则分配，并重新计算nexttime, stoptime.否则该进程进入等待队列队尾。,算法分析,所有的进程都分配完后则可知总的运行时间和进入过等待队列的进程总数。 注意最后head2等待队列中仍可能有进程未处理，所以最后还应处理等待队列中剩
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论