操作系统内存分配算法模拟实现.doc

实 验 报 告 册院系名称： 计算机科学学院 课程名称： 操作系统 实验学期 2009 年至 2010 年 第 二 学期专业班级： 计算机科学与技术 2008级1班 姓名： HORACE 学号： 2008110108 指导教师： 高老师 实验最终成绩： 实验报告须知1学生填写实验报告应按规范填写，填写格式见由任课老师给出的实验报告样本；2学生应填写的内容包括：封面相关栏目、第一页中本学期（年）开设实验课程情况一览表中的实验名称、学时数；每次报告中的实验性质、同组人姓名、实验日期、以及实验报告中的一至五项；3教师填写内容为：实验评价、每次报告成绩、第一页中本学期（年）开设实验课程情况一览表中成绩、及封面的实验最终成绩；4学生实验结束后，教师应对学生实验结果进行核实，学生方可离开实验室。5、实验成绩等级分为（90100分）优，（8089分）良，(70-79分)中，（6069分）及格，（59分）不及格。6本实验册应妥善保管，本课程实验结束后应交回实验室实验报告（2）实验名称内存分配与回收算法实现同组人姓名实验性质 基本操作 验证性 综合性 设计性实验日期2010-5-17实验成绩教师评价：实验预习 实验操作 实验结果 实验报告 其它 教师签名：一、实验目的及要求1） 掌握为实现多道程序并发执行，操作系统是如何通过作业调度选择作业进入内存2） 系统如何为进入内存的作业分配内存空间，实现多道作业同时驻留内存，就绪进程队列中的多个进程是如何以分式方式共享CPU，作业运行完成离开系统时，系统如何进行内存回收，计算进程周转时间。3） 掌握各种调度算法，以及实现所需的各种数据结构。二、实验内容根据给定的动态分区分配算法流程图，用你熟悉的计算机编程语言编写一程序，该程序实现内存的合理分配后回收。三、主要设备及软件PC、Windows2000操作系统、Linux操作系统四、实验流程、操作步骤或核心代码、算法片段请求分配u.size分区检索空闲分区链（表）找到大于u.size的可用分区否？按动态分区方式进行分配修改有关数据结构返回分区号及首地址空闲分区总和=u.size进行紧筹形成连续空闲区修改有关数据结构无法分配返回1、分配算法流程出2、算法模拟实现 相关数据结构定义 空闲分区块类：class FreeBlock 空闲分区链类：class FreeList 内存分配回收算法类：class MemoryManager 测试类（主类）：class TestForMemManage 具体实现 请允许我先列出核心部分，内存分配回收算法类的实现：package com.kaiping.memorymanage;/个人包import java.util.Scanner;public class MemoryManager FreeList flist; /空闲分区类对象public MemoryManager()flist = new FreeList();flist.InitFBlock();public void memAllocation(int size, String new_job_name)/内存分配（首次适应算法）FreeBlock q=flist.head;FreeBlock p=flist.head.next;while(p != null)if(size = size)q = new FreeBlock(p.size - size);p.size = size;p.state = true;p.job_name = new_job_name;q.next = p.next;p.next = q;break;/完成分配elsep = p.next;/移动到足够分配的空闲块if(p = null)if(flist.flistsize = size)System.out.println(目前尚无足够大的空闲块，系统将进行重定位操作.);relocation();/重定向memAllocation(size,new_job_name);/重新分配内存elseSystem.out.println(作业+new_job_name+内存尚未分配成功！);else/分配内存后可能存在大小为0的空间，将其清除System.out.println(作业+new_job_name+内存分配成功！);p = flist.head.next;/q = flist.head;while(p != null)if(p.size = 0)flist.deleteFBlock(p);p = p.next;private void memRecovery(FreeBlock target) /内存回收FreeBlock p = flist.head.next;while(p != null)/回收区与插入点的前一个空闲分区相邻接if(p.next = target & p.state = false)p.size += target.size;p.next = target.next;/回收区同时与插入点的前后两个空闲分区相邻接if(!p.next.state)p.size += p.next.size;p.next = p.next.next;break;if(p = target)/回收区与插入点的后一空闲分区相邻接if(!p.next.state)target.size += p.next.size;target.next = p.next.next;break;/若两不邻接，则直接跳出p = p.next;private void relocation() /空闲资源重定向，回收空闲空间FreeBlock front_r=flist.head;/FreeBlock r=front_r.next;/当前重定向空闲块FreeBlock behind_r=r.next;while(r != null)/将r定位到第一块空闲分区块if(r.state = false)break;r = r.next;behind_r = r.next;front_r = front_r.next;/记录第一块空闲分区的上一块while(behind_r != null)if(behind_r.state)front_r.next = behind_r;r.next = behind_r.next;behind_r.next = r;front_r = behind_r;elser.size += behind_r.size;r.next = behind_r.next;behind_r = r.next;System.out.println(重定向成功，继续为作业分配内存.);public void addJob() /添加作业int newSize;/新作业所需内存大小String nJobName = new String();Scanner scanner=new Scanner(System.in);System.out.print(请输入新任务的名称：);nJobName = scanner.nextLine();System.out.print(请输入新任务所需内存大小：);newSize = scanner.nextInt();memAllocation(newSize,nJobName);public void delJob() /销毁作业String cur_job_name = new String();boolean flag = false;/指示作业是否删除成功FreeBlock q=flist.head.next;Scanner scanner=new Scanner(System.in);System.out.print(请输入需要回收的作业名称:);cur_job_name = scanner.nextLine();while(q != null)if(q.job_name = cur_job_name)q.state = false;q.job_name = ;memRecovery(q);/回收内存flag = true;break;elseq = q.next;/找到要删除的作业的下一个结点if(flag)System.out.println(删除作业成功！);elseSystem.out.println(删除作业未成功！);public void printJobInfo()/打印作业信息FreeBlock p = flist.head.next;int pro_num = 1;/用户程序号int mem_num = 1;/内存分区块号System.out.println(-用户程序信息-);while(p != null)if(p.state)System.out.println(用户程序+pro_num+(+p.job_name+)+t占用第+mem_num+分区块);pro_num+;mem_num+;p = p.next;public void printFreeSubareaInfo()/打印空闲分区信息FreeBlock p = flist.head.next;int leav_size = 0;/剩余内存大小int mem_num = 1;/内存分区块号System.out.println(-空闲分区信息-);System.out.println(t分区块号t大小);while(p != null)if(!p.state)System.out.println(t+mem_num+t+p.size);leav_size += p.size;mem_num+;p = p.next;System.out.println(剩余内存总打小为+leav_size);其它类的实现空闲分区块类：package com.kaiping.memorymanage;public class FreeBlock int size; /空闲块大小 boolean state; /false表示空闲，true表示已经装入作业 String job_name; /装入的作业名称 FreeBlock next;/下一空闲块的自引用 public FreeBlock(int s) size = s; state = false; job_name = new String(); next = null; 空闲分区链类：package com.kaiping.memorymanage;import java.util.Scanner;public class FreeList FreeBlock fblock;FreeBlock head;int fblockNum;/空闲块数int sumMemCount;/内存总大小int flistsize;/空闲分区总和public FreeList()fblock = null;head = new FreeBlock(0);public boolean isEmpty()return (fblock = null);public void insertFBlock(int size)FreeBlock newBlock = new FreeBlock(size);if(fblock = null)fblock = newBlock;head.next = fblock;elsefblock.next = newBlock;fblock = fblock.next;public void deleteFBlock(FreeBlock dblock)FreeBlock temp = head;while(temp != null)if(temp.next = dblock)temp.next = dblock.next;break;temp = temp.next;public void InitFBlock()int leavesCount;/为化入分区内存总大小int bsize=0;/分区块大小Scanner scanner=new Scanner(System.in);System.out.print(初始多大空间，请输入一整数：);sumMemCount = scanner.nextInt();leavesCount = sumMemCount;flistsize = sumMemCount;/初始空闲分区大小为内存大小System.out.print(需将内存分为多少分区块，请输入一整数：);fblockNum = scanner.nextInt();System.out.println(-初始化内存分区-);for(int i=1; i = leavesCount - i)System.out.print(您输入的数据无法保证每分区块最少有1单位内存，请重新输入：);bsize = scanner.nextInt();insertFBlock(bsize);leavesCount -= bsize;System.out.println(余下内存大小为+leavesCount+，请继续分配！);System.out.println(分配完毕！);System.out.println(-创建空闲分区表如下-);System.out.println(t分区号t大小);FreeBlock temp = head.next;for(int i=1; i = fblockNum; i+)System.out.println(t+i+t+temp.size);temp = temp.next;测试类（主类）：package com.kaiping.memorymanage;import java.util.Scanner;public class TestForMemManage public static void main(String args) MemoryManager mem_manage = new MemoryManager();int choice=0;Scanner scanner=new Scanner(System.in);doSystem.out.println(0.退出程序);System.out.println(1.添加新作业);System