操作系统实验报告 实验四
《计算机操作系统》
实验报告
院 系： 计算机科学与技术
学 号：
专业班级：
学生姓名：
完成时间： 2012.05.22
实验四
动态分区分配算法
1、 需求
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
1、设计背景
动态分区分配是根据进程的实际需要，动态地为之分配内存空间，而在分配时，须按照一定的算法，从空闲分区或空闲分区链中选出一分区分配给该作业。对于不同的作业的分区需求，通常采用不同的动态分区算法，或者多个算法一起使用。
2、实验目的：
通过这次实验，加深对动态分区分配算法的理解，进一步掌握首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的实现方法。
3、问题描述：
设计程序模拟四种动态分区分配算法：首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的工作过程。假设内存中空闲分区个数为n，空闲分区大小分别为P1, … ,Pn，在动态分区分配过程中需要分配的进程个数为m（m≤n），它们需要的分区大小分别为S1, … ,Sm，分别利用四种动态分区分配算法将m个进程放入n个空闲分区，给出进程在空闲分区中的分配情况。
4、程序要求：
1）利用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法四种动态分区分配算法模拟分区分配过程。
2）模拟四种算法的分区分配过程，给出每种算法进程在空闲分区中的分配情况。
3）输入：空闲分区个数n，空闲分区大小P1, … ,Pn，进程个数m，进程需要的分区大小S1, … ,Sm，算法选择1-首次适应算法，2-循环首次适应算法，3-最佳适应算法，4-最坏适应算法。
4）输出：最终内存空闲分区的分配情况。
5、实验原理：
首次适应算法（first fit）：在首次适应算法中，是从已建立好的数组中顺序查找，直到找到第一个大小能满足要求的空闲分区为止，然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空间令开辟一块新的地址，大小为原来的大小减去作业大小，若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。
循环首次适应算法（next fit）：该算法是由首次适应算法演变而成，在为进程分配空间时，不再是每次都从第一个空间开始查找，而是从上次找到的空间分区的下一个空间分区开始查找，直到找到第一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。为实现本算法，设置一个全局变量count，来控制循环查找，当count等于数组的大小时，查找结束。当在没有查找结束时就已经到了数组末尾，则从数组的开头开始查找。若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。
最佳适应算法（best fit）：最佳适应分配算法是每次为作业分配内存时，扫描整个数组，将总是能满足条件的，又是最小的空闲分区分配给作业。
最坏适应算法（worse fit）：最坏适应分配算法是每次为作业分配内存时，扫描整个数组，总是挑选一个最大的空闲分区分配给作业使用。
6、运行环境：
Eclipse----java
2、 概要设计
1、 主要抽象数据类型定义
ArrayList
Spacelist=new ArrayList(); //空闲分区数组
ArrayList Plist=new ArrayList(); //作业需要分区大小的数组
//定义item类 描述分区的序列号和名称
class item
{
int index; //分区的序列号
String name; //分区的名称，有作业的时候现在作业名，空闲分区则为Null
public item(int i,String n)
{
index=i;
name=n;
}
}
ArrayList- spacelist; //进程在空闲分区的数组
int count=0; //循环首次适应算法关于搜索查询的计数
2、 主要函数设计：
void main() //主函数，输入空闲分区、作业所需分区
public PartitioningPlacement() //选择算法，输出分区分配过程
public int FirstFit() //首次适应算法
public int NextFit() //循环首次适应算法
public int BestFit() //最佳适应算法
public int WorstFit() //最坏适应算法
void output() //输出当前分区数组情况
3、 函数调用
流程图
破产流程图 免费下载数据库流程图下载数据库流程图下载研究框架流程图下载流程图下载word
：
●核心设计：
eq \o\ac(○,1)void main()主函数输入选择动态分区分配算法1-首次适应算法，2-循环首次适应算法，3-最佳适应算法，4-最坏适应算法，或者0-退出。输入空闲分区大小、作业大小，调用PartitioningPlacement()函数。
eq \o\ac(○,2)PartitioningPlacement()函数根据用户输入choice选择调用choice所对应的相关动态分区分配算法。
PartitionningPlacement( )
switch(choice) {
case 1: {
System.out.println("首次适应算法:");
int temp=0;
for(int i=0;i AList=spacelist;
//int flag=0;
for(int i=0;iinput)
{
item temp=spacelist.get(i);
temp.name=temp.name+(char)('A'+tage);
temp.index=temp.index-input;
spacelist.set(i,temp) ;
output(spacelist);
return i;
}
if(spacelist.get(i).index==input)
{
item temp=spacelist.get(i);
temp.name=temp.name+(char)('A'+tage);
temp.index=temp.index-input;
spacelist.set(i,temp) ;
output(spacelist);
return i;
}
}
output(spacelist);
return -1;//失败
}
●//循环首次适应算法
public int NextFit(int input,int tage)
{
int i=index-1;
count=0;
while(true)
{
count++;
i=(i+1)%spacelist.size();
if(count==spacelist.size()+1)
{
output(spacelist);
return -1;//失败
}
//System.out.println("next____: "+spacelist.size()+" i:"+i);
//System.out.println("next____: "+spacelist.get(i).index);
if(spacelist.get(i).index>input)
{
item temp=spacelist.get(i);
temp.name=temp.name+(char)('A'+tage);
temp.index=temp.index-input;
spacelist.set(i,temp) ;
output(spacelist);
return i;
}
if(spacelist.get(i).index==input)
{
item temp=spacelist.get(i);
temp.name=temp.name+(char)('A'+tage);
temp.index=temp.index-input;
spacelist.set(i,temp) ;
output(spacelist);
return i;
}
}
}
●//最坏适应算法
public int WorstFit(int input,int tage)
{
int i=Findmax();
while(i!=-1)
{
if(spacelist.get(i).index>input)
{
item temp=spacelist.get(i);
temp.name=temp.name+(char)('A'+tage);
temp.index=temp.index-input;
spacelist.set(i,temp) ;
output(spacelist);
return i;
}
if(spacelist.get(i).index==input)
{
item temp=spacelist.get(i);
temp.name=temp.name+(char)('A'+tage);
temp.index=temp.index-input;
spacelist.set(i,temp) ;
output(spacelist);
return i;
}
i=Findmax();
}
output(spacelist);
return -1;
}
●//最佳适应算法
public int BestFit(int input,int tage)
{
ArrayList AList=new ArrayList();
for(int j=0;jinput)
{
item temp=spacelist.get(i);
temp.name=temp.name+(char)('A'+tage);
temp.index=temp.index-input;
spacelist.set(i,temp) ;
output(spacelist);
return i;
}
if(spacelist.get(i).index==input)
{
item temp=spacelist.get(i);
temp.name=temp.name+(char)('A'+tage);
temp.index=temp.index-input;
spacelist.set(i,temp) ;
output(spacelist);
return i;
}
}
output(spacelist);
return -1;
}
●//mian()函数 输入
public static void main(String[] args) {
// TODO Auto-generated method stub
int choice=0;
while(true)
{
Scanner in = new Scanner(System.in);
System.out.println("0:退出");
System.out.println("1:首次适应算法");
System.out.println("2:循环首次适应算法");
System.out.println("3:最佳适应算法");
System.out.println("4:最坏适应算法");
choice=in.nextInt();
if(choice==0)
{System.out.println("退出!");
System.exit(0);
}
ArrayList Spacelist=new ArrayList();
ArrayList Plist=new ArrayList();
System.out.println("请输入空闲空间的个数：");
int s=in.nextInt();
System.out.println("请输入空闲分区大小：");
int temp=0;
for(int i=0;i list)
{
System.out.print("\n(");
for(int i=0;i
书
关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf
上写的进行排列问题进行了对原来的空闲分区数组进行排列，打乱了其顺序，出现错误。之后通过添加函数public int Findmax()和public int Findmin()来返回数组中最大的分区和最小的分区的序列号。其它的就是一些编程中常见的小问题，如排版问题，输出的
格式
pdf格式笔记格式下载页码格式下载公文格式下载简报格式下载
问题等，也经过不断调试解决问题。
(2)算法的改进设想
做出一个人际交互的界面，是输入更加清晰好看。
(3)经验和体会。
通过本次实验加深了对动态分区分配概念的认识，并且更加深刻地了解了实验中这四个动态分区分配算法的基本原理。
6、 用户使用说明：
本程序没有过多地涉及人机交互的处理，在将程序调试通过并编译链接后，只需直接执行并按提示输入便可得出结果。
1.运行程序，首先提示选择动态分区分配算法1-首次适应算法，2-循环首次适应算法，3-最佳适应算法，4-最坏适应算法，或者0-退出。用户按需求输入选择数字
2.运行程序输出“请输入空闲分区个数”，用户按需求输入空间分区个数n，输出“请输入空间分区大小”，用户根据自己的需求输入数组，数组之间的数可以用空格隔开，也可以用回车键隔开；运行程序输出“请输入进程个数”，用户根据需求输入进程个数，输出“请输入进程需要分区大小”，用户根据需求输入数组，数组之间的数可以用空格隔开，也可以用回车键隔开。
3.前两个步骤输入后，可以得出用户所输入的进程按所选的算法得到的分区
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
。
4.用户可以选择退出，或者继续选择动态分区分配算法，执行前面三个个步骤。
7、 测试结果:
实验测试数据：
假设有一批作业A、B、C、D、E、F，它们的大小分别为7KB、18KB、9KB、20KB、35KB、8KB，根据不同的算法把它们分配到如下空闲分区表中。
首次适应算法
循环首次适应算法
最佳适应算法
最坏适应算法
8、 附录：
import java.util.ArrayList;
import java.util.Scanner;
//动态分区
public class PartitioningPlacement {
ArrayList
- spacelist;
public PartitioningPlacement(int choice,ArrayList s,ArrayList p) {
// TODO Auto-generated constructor stub
spacelist=new ArrayList
- ();
for(int i=0;i Spacelist=new ArrayList();
ArrayList Plist=new ArrayList();
System.out.println("请输入空闲空间的个数：");
int s=in.nextInt();
System.out.println("请输入空闲分区大小：");
int temp=0;
for(int i=0;i list)
{
System.out.print("\n(");
for(int i=0;i ans=new ArrayList
- ();
public int FirstFit(int input,int tage)//首次适应算法
{
for(int i=0;iinput)
{
item temp=spacelist.get(i);
temp.name=temp.name+(char)('A'+tage)+" |";
temp.index=temp.index-input;
spacelist.set(i,temp) ;
output(spacelist);
return i;
}
if(spacelist.get(i).index==input)
{
item temp=spacelist.get(i);
temp.name=temp.name+(char)('A'+tage)+" |";
temp.index=temp.index-input;
spacelist.set(i,temp) ;
output(spacelist);
return i;
}
}
output(spacelist);
return -1;//失败
}
int index=0;
int count=0;
public int NextFit(int input,int tage)
{
int i=index-1;
count=0;
while(true)
{
count++;
i=(i+1)%spacelist.size();
if(count==spacelist.size()+1)
{
output(spacelist);
return -1;//失败
}
if(spacelist.get(i).index>input)
{
item temp=spacelist.get(i);
temp.name=temp.name+(char)('A'+tage)+" |";
temp.index=temp.index-input;
spacelist.set(i,temp) ;
output(spacelist);
return i;
}
if(spacelist.get(i).index==input)
{
item temp=spacelist.get(i);
temp.name=temp.name+(char)('A'+tage)+" |";
temp.index=temp.index-input;
spacelist.set(i,temp) ;
output(spacelist);
return i;
}
}
}
public int Findmax()
{
int maxindex=-1;
int max=-1;
for(int i=0;imax)
{
max=spacelist.get(i).index;
maxindex=i;
}
}
if(maxindex==-1)
{
return -1;//ERROR
}
else
return maxindex;
}
public int Findmin(ArrayList AList)
{
int minindex=-1;
int min=-1;
for(int i=0;iinput)
{
item temp=spacelist.get(i);
temp.name=temp.name+(char)('A'+tage)+" |";
temp.index=temp.index-input;
spacelist.set(i,temp) ;
output(spacelist);
return i;
}
if(spacelist.get(i).index==input)
{
item temp=spacelist.get(i);
temp.name=temp.name+(char)('A'+tage)+" |";
temp.index=temp.index-input;
spacelist.set(i,temp) ;
output(spacelist);
return i;
}
i=Findmax();
}
output(spacelist);
return -1;
}
public int BestFit(int input,int tage)//最佳适应算法
{
ArrayList AList=new ArrayList();
for(int j=0;jinput)
{
item temp=spacelist.get(i);
temp.name=temp.name+(char)('A'+tage)+" |";
temp.index=temp.index-input;
spacelist.set(i,temp) ;
output(spacelist);
return i;
}
if(spacelist.get(i).index==input)
{
item temp=spacelist.get(i);
temp.name=temp.name+(char)('A'+tage)+" |";
temp.index=temp.index-input;
spacelist.set(i,temp) ;
output(spacelist);
return i;
}
}
output(spacelist);
return -1;
}
}
2 / 25
浙公网安备 33021202002483