精华内容
下载资源
问答
  • 关于首次适应算法、最佳适应算法和最差适应算法,先看一下百度百科的解释,已经说出了三者的最大区别。 首次适应算法(first-fit):从空闲分区表的第一个表目起查找该表,把最先能够满足要求的空闲区分配给作业,...

    关于首次适应算法、最佳适应算法和最差适应算法,先看一下百度百科的解释,已经说出了三者的最大区别。


    首次适应算法(first-fit):

        从空闲分区表的第一个表目起查找该表,把最先能够满足要求的空闲区分配给作业,这种方法的目的在于减少查找时间。


        最佳适应算法(best-fit):从全部空闲区中找出能满足作业要求的,且大小最小的空闲分区,这种方法能使碎片尽量小。


        最差适应算法(worst-fit):它从全部空闲区中找出能满足作业要求的、且大小最大的空闲分区,从而使链表中的节点大小趋于均匀。


    下面看一个实例:

    Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (in order), how would each of the first-fit, best-fit, and worst-fit algorithms place processes of 212 KB, 417 KB, 112 KB, and 426 KB (in order)? Which algorithm makes the most efficient use of memory?


    首次适应算法:

        为212k分配空间:

            依次找寻,找到第一个大于212k的空闲区;

            找到第二个空闲区500k>212k,分配给212k,剩余288k空闲区;

        为417k分配空间:

            依次找寻,找到第一个大于417k的空闲区;

            找到第五个空闲区600k>417k,分配给417k,剩余183k空闲区

        为112k分配空间:

            依次找寻,找到第一个大于112k的空闲区;

            找到第二个空闲区288k>112k,分配给112k,剩余176k空闲区

        为426k分配空间:

            依次找寻,找到第一个大于426k的空闲区;

            未找到,此作业将等待释放空间

    最佳适应算法

        为212k分配空间:

            找到第一个跟212k大小最接近的空闲区

            找到第四个空闲区300>212k,剩余88k空闲区

        为417k分配空间:

            找到第一个跟417k大小最接近的空闲区

            找到第二个空闲区500>417,剩余83k空闲区

        为112k分配空间:

            找到第一个跟112k大小最接近的空闲区

            找到第三个空闲区200>112k,剩余88k空闲区

        为426k分配空间:

            找到第一个跟426大小最接近的空闲区

            找到第五个空闲区600k>426,剩余74k空闲区

    最坏适应算法

        为212k分配空间:

            找到第一个大小最大的空闲区

            找到第五个空闲区600>212k,剩余388k空闲区

       为417k分配空间:

            找到第一个大小最大的空闲区

            找到第二个空闲区500>417,剩余83k空闲区

        为112k分配空间:

            找到第一个大小最大的空闲区

            找到第三个空闲区388>112k,剩余276k空闲区

        为426k分配空间:

            找到第一个大小最大的空闲区

            达到大小最大的空闲区300k<426k,所以不分配

    Answer

    Free partition

      100  

        500  

      200  

      300  

      600

        Not satisfied

    First-fit   

     

       212,112    

     

     

      417

        426

    Best-fit

     

       417

      112

      212

      426

     

    Worst-fit

     

       417

     

     

      212,112  

        426


      ps:好久没碰操作系统了,今天看到这三个算法的第一反应居然有点懵,还是好记性不如烂笔头啊,本文中的定义来自百度百科,实例题目来自老师布置的作业,答案分析为笔者按自己的理解写的,若有不对,欢迎指出~~

    展开全文
  • 关于首次适应算法、最佳适应算法和最差适应算法,先看一下百度百科的解释,已经说出了三者的最大区别。首次适应算法(first-fit): 从空闲分区表的第一个表目起查找该表,把最先能够满足要求的空闲区分配给作业,...

    关于首次适应算法、最佳适应算法和最差适应算法,先看一下百度百科的解释,已经说出了三者的最大区别。


    首次适应算法(first-fit):

        从空闲分区表的第一个表目起查找该表,把最先能够满足要求的空闲区分配给作业,这种方法的目的在于减少查找时间。


        最佳适应算法(best-fit):从全部空闲区中找出能满足作业要求的,且大小最小的空闲分区,这种方法能使碎片尽量小。


        最差适应算法(worst-fit):它从全部空闲区中找出能满足作业要求的、且大小最大的空闲分区,从而使链表中的节点大小趋于均匀。


    下面看一个实例:

    Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (in order), how would each of the first-fit, best-fit, and worst-fit algorithms place processes of 212 KB, 417 KB, 112 KB, and 426 KB (in order)? Which algorithm makes the most efficient use of memory?


    首次适应算法:

        为212k分配空间:

            依次找寻,找到第一个大于212k的空闲区;

            找到第二个空闲区500k>212k,分配给212k,剩余288k空闲区;

        为417k分配空间:

            依次找寻,找到第一个大于417k的空闲区;

            找到第五个空闲区600k>417k,分配给417k,剩余183k空闲区

        为112k分配空间:

            依次找寻,找到第一个大于112k的空闲区;

            找到第二个空闲区288k>112k,分配给112k,剩余176k空闲区

        为426k分配空间:

            依次找寻,找到第一个大于426k的空闲区;

            未找到,此作业将等待释放空间

    最佳适应算法

        为212k分配空间:

            找到第一个跟212k大小最接近的空闲区

            找到第四个空闲区300>212k,剩余88k空闲区

        为417k分配空间:

            找到第一个跟417k大小最接近的空闲区

            找到第二个空闲区500>417,剩余83k空闲区

        为112k分配空间:

            找到第一个跟112k大小最接近的空闲区

            找到第三个空闲区200>112k,剩余88k空闲区

        为426k分配空间:

            找到第一个跟426大小最接近的空闲区

            找到第五个空闲区600k>426,剩余74k空闲区

    最坏适应算法

        为212k分配空间:

            找到第一个大小最大的空闲区

            找到第五个空闲区600>212k,剩余388k空闲区

       为417k分配空间:

            找到第一个大小最大的空闲区

            找到第二个空闲区500>417,剩余83k空闲区

        为112k分配空间:

            找到第一个大小最大的空闲区

            找到第三个空闲区388>112k,剩余276k空闲区

        为426k分配空间:

            找到第一个大小最大的空闲区

            达到大小最大的空闲区300k<426k,所以不分配

    Answer

    Free partition

      100  

        500  

      200  

      300  

      600

        Not satisfied

    First-fit   

     

       212,112    

     

     

      417

        426

    Best-fit

     

       417

      112

      212

      426

     

    Worst-fit

     

       417

     

     

      212,112  

        426


      ps:好久没碰操作系统了,今天看到这三个算法的第一反应居然有点懵,还是好记性不如烂笔头啊,本文中的定义来自百度百科,实例题目来自老师布置的作业,答案分析为笔者按自己的理解写的,若有不对,欢迎指出~~

    原文链接 http://blog.csdn.net/u011070169/article/details/53177987?locationNum=5&fps=1

    展开全文
  • 最佳、最差、最先适应算法

    千次阅读 2018-06-13 16:19:35
    最差适应算法 void allocateFirst(float J,float J_length);// 最先适应算法 void reclaim(char J);// 内存回收   void init();// 初始化空闲分区表、已分配分区表 void menuHost();// 菜单选项 void menuAllocate...

    #include<iostream>

    using namespace std;

    #define n 10 //假定系统允许的最大作业数、空闲区表的最大值是n

    #define mini_size 100 //碎片大小

     

    typedef struct table{

    float address;

    float length;

    float flag;

    }Table;

    typedef struct table1{

    float address;

    float length;

    char flag;

    }Table1;

    Table free_table[n];

    Table1 used_table[n];

     

    //最佳适应算法

    void allocateBest(float J,float J_length);//最佳适应算法

    void allocateWorst(float J,float J_length);//最差适应算法

    void allocateFirst(float J,float J_length);//最先适应算法

    void reclaim(char J);//内存回收

     

    void init();//初始化空闲分区表、已分配分区表

    void menuHost();//菜单选项

    void menuAllocate();//分配选项

    int main()

    {

     

    init();

    int in;

    int inAllocate;

    while(1)

    {

    menuHost();

    cin>>in;

    char J;//作业名

    while(!(in==0||in==1||in==2||in==3))

    {

    cout<<"没有该选项,请重新输入:"<<endl;

    cin>>in;

    }

    switch(in)

    {

    case 0:exit(0);

    case 1://为作业分配空间

    float length ;

    cout<<"请输入作业名:"<<endl;

    cin>>J;

    while(!(J>='a'&&J<='z' ||J>='A'||J<='Z'))

    {

    cout<<"输入有误,请输如代表一个作业的字符,如‘A"<<endl;

    cin>>J;

    }

    cout<<"请输入作业的长度:"<<endl;

    cin>>length;

    while(length<0)

    {

    cout<<"输入的作业长度为:"<<length<<" <0不合理,请重新输入:"<<endl;

    cin>>length;

    }

    menuAllocate();

    cout<<"请输入选项:\n";

    cin>>inAllocate;

    while(!(inAllocate==0||inAllocate==1||inAllocate==2||inAllocate==3))

    {

    cout<<"没有该选项,请重新输入:"<<endl;

    cin>>inAllocate;

    }

    if(inAllocate==0)

    exit(0);

    else if(inAllocate==1)

    {

    allocateBest(J,length);

    break;

    }

    else if(inAllocate==2)

    {

    allocateWorst(J,length);

    break;

    }

    else

    {

    allocateFirst(J,length);

    break;

    }

    case 2:

    //回收作业空间

    cout<<"请输入回收的作业名:"<<endl;

    cin>>J;

    while(!(J>='a'&&J<='z' ||J>='A'||J<='Z'))

    {

    cout<<"输入有误,请输如代表一个作业的字符,如‘A"<<endl;

    cin>>J;

    }

    reclaim(J);

    break;

    case 3:

    cout<<"输出空闲区表:"<<endl;

    cout<<"起始地址\t分区长度\t标志"<<endl;

    for(int i=0;i<n;i++)

    cout<<free_table[i].address<<"\t\t"<<free_table[i].length<<"\t\t"<<free_table[i].flag<<endl;

    cout<<"按任意键输出已分配区表"<<endl;

    char c;

    cin>>c;

    cout<<"输出已分配区表:"<<endl;

    cout<<"起始地址 \t分区长度\t标志\n";

    for(i=0;i<n;i++){

    cout<<used_table[i].address<<"\t\t"<<used_table[i].length<<"\t\t"<<used_table[i].flag<<endl;

    }

    break;

    }//switch

    }//while

     

    return 0;

    }

     

     

    //最先适应算法

    void allocateBest(float J,float J_length)//id==J的作业分配J_length的空间

    {

    cout<<"您选择了最佳分配算法!"<<endl;

    float ad = 0.0;

    int k=-1;

    for(int i=0;i<n;i++)

    {

    if(free_table[i].length>=J_length && free_table[i].flag==1)//表示该分区空闲

    {

    if(k==-1|| free_table[i].length<free_table[k].length)

    k=i;

    }

    }

     

    if(k==-1)

    {

    cout<<"没有可用空闲区!"<<endl;

    return;

    }

    if((free_table[k].length-J_length)<=mini_size)

    {

    free_table[k].flag = 0;//该空闲分区空间已经全部分配出去或成为碎片,已经不能再使用,flag置为0

    ad = free_table[k].address;

    J_length = free_table[k].length;

    }

    else{

    ad = free_table[k].address;

    free_table[k].length -= J_length;

    free_table[k].address +=J_length;

    }

    //修改used_table

    i=0;

    while(used_table[i].flag!='0' && i<n)//寻找可以用于记录该作业的分配情况的空表目

    i++;

    if(i>=n)

    {

    cout<<"记录作业的表目已经用完,没有空间填写该表目了!"<<endl;

    //因为无法记录,所以之前的free_table修改的地方就要重新修改回来

    if(free_table[k].flag==0)

    free_table[k].flag = 1;

    else{

    free_table[k].length +=J_length;

    free_table[k].address-=J_length;

    }

    return;

    }

    else{

    used_table[i].address = ad;

    used_table[i].length = J_length;

    used_table[i].flag = J;

    }

    cout<<"最佳分配算法已成功完成!"<<endl;

    return;

     

    }

    //以上分配函数结束

     

    void reclaim(char J){

    cout<<"您选择回收 "<<J<<"  作业!"<<endl;

    int i=0;

    int s=0;

    while(used_table[i].flag!=J && i<n)

    i++;

    if(i==n)

    {

    cout<<"没有该记录的作业!"<<endl;

    return;

    }

    used_table[i].flag = '0';//flag0才意味着可以用来记录

    float ad = used_table[i].address;

    float length = used_table[i].length;

    //cout<<ad<<"  "<<length<<endl;

    int free_up=-1,j=0,free_down=-1;//寻找回收分区的空闲上下邻

    while(j<n && (free_up==-1 || free_down==-1)){

    if(free_table[j].flag==1)

    {

    if(free_table[j].address+free_table[j].length==ad)

    free_up = j;//找到上邻

    if(free_table[j].address==ad+length)

    free_down = j;//找到下邻

    }

    j++;

    }

    if(free_up!=-1)

    if(free_down!=-1)//三项合并

    {

    free_table[free_up].length+= length+free_table[free_down].length;

    free_table[free_down].flag = 0;

    }

    else{

    free_table[free_up].length +=length;

    }

    else{

    //上非空闲,下空闲

    if(free_down!=-1)

    {

    free_table[free_down].address = ad;

    free_table[free_down].length+=length;

    }

    else{

    //上下均为非空闲区,free_table中寻找空栏目,填入该回收记录

    while(s<n && free_table[s].flag==1)

    s++;

    if(s==n)

    {

    cout<<"free_table表已经没有空间插入新纪录了,空间回收失败!!"<<endl;

    used_table[s].flag=J;

    return;

    }

    free_table[s].flag=1;

    free_table[s].address = ad;

    free_table[s].length = length;

    }

    return;

    }

     

    cout<<J<<" 作业回收完成!"<<endl;

     

    }

     

    void init()

    {

    free_table[0].flag=1;//空闲区表的flag==1的话说明该空闲区表是有空间的,可 以用来未作业分配孔家安

    free_table[0].address=10000;

    free_table[0].length=50;

     

    for(int i=1;i<n;i++)

    free_table[i].flag = 0;//初始空闲分区表除了第0个,其余都尚未分配

     

    //初始化下标为1的空闲区

    free_table[1].address = 20000;

    free_table[1].length = 200;

    free_table[1].flag = 1;

    //初始化下标为2的空闲区

    free_table[2].address = free_table[1].address+free_table[1].length;

    free_table[2].length = 150;

    free_table[2].flag = 1;

    //初始化下标为3的空闲区

    free_table[3].address = free_table[2].address+free_table[2].length;

    free_table[3].length = 600;

    free_table[3].flag = 1;

    //初始化下标为4的空闲区

    free_table[4].address = 18000;

    free_table[4].length = 1950;

    free_table[4].flag = 1;

    for(i=0;i<n;i++)

    used_table[i].flag='0';//初始时均为分配

     

    //初始化一个名字为K的作业

    used_table[1].address = 10050;

    used_table[1].flag = 'K';

    used_table[1].length = 1000;

    used_table[2].address = 19950;

    used_table[2].flag = 'W';

    used_table[2].length = 50;

     

    }

    void menuHost(){

    cout<<"选择功能项: "<<endl;

    cout<<"0-退出"<<endl;

    cout<<"1-分配主存"<<endl;

    cout<<"2-回收主存"<<endl;

    cout<<"3-显示主存"<<endl;

    }

     

    void allocateWorst(float J,float J_length){

    cout<<"您选择了最差分配算法!"<<endl;

    float ad = 0.0;

    int k=-1;

    for(int i=0;i<n;i++)

    {

    if(free_table[i].length>=J_length && free_table[i].flag==1)//表示该分区空闲

    {

    if(k==-1|| free_table[i].length>free_table[k].length)//找最大的空闲分区

    k=i;

    }

    }

     

    if(k==-1)

    {

    cout<<"没有可用空闲区!"<<endl;

    return;

    }

    if((free_table[k].length-J_length)<=mini_size)

    {

    free_table[k].flag = 0;//该空闲分区空间已经全部分配出去或成为碎片,已经不能再使用,flag置为0

    ad = free_table[k].address;

    J_length = free_table[k].length;

    }

    else{

    ad = free_table[k].address;

    free_table[k].length -= J_length;

    free_table[k].address +=J_length;

    }

    //修改used_table

    i=0;

    while(used_table[i].flag!='0' && i<n)//寻找可以用于记录该作业的分配情况的空表目

    i++;

    if(i>=n)

    {

    cout<<"记录作业的表目已经用完,没有空间填写该表目了!"<<endl;

    //因为无法记录,所以之前的free_table修改的地方就要重新修改回来

    if(free_table[k].flag==0)

    free_table[k].flag = 1;

    else{

    free_table[k].length +=J_length;

    free_table[k].address-=J_length;

    }

    return;

    }

    else{

    used_table[i].address = ad;

    used_table[i].length = J_length;

    used_table[i].flag = J;

    }

    cout<<"最先分配算法已成功完成!"<<endl;

    return;

    }

     

    void allocateFirst(float J,float J_length)//最先适应算法

    {

    cout<<"您选择了最先分配算法!"<<endl;

    float ad = 0.0;

    int k=-1;

    for(int i=0;i<n;i++)

    {

    if(free_table[i].length>=J_length && free_table[i].flag==1)//表示该分区空闲

    {

    k=i;

    break;

    }//找到第一个长度大于待分配作业的内存分区

    }

     

    if(k==-1)

    {

    cout<<"没有可用空闲区!"<<endl;

    return;

    }

    if((free_table[k].length-J_length)<=mini_size)

    {

    free_table[k].flag = 0;//该空闲分区空间已经全部分配出去或成为碎片,已经不能再使用,flag置为0

    ad = free_table[k].address;

    J_length = free_table[k].length;

    }

    else{

    ad = free_table[k].address;

    free_table[k].length -= J_length;

    free_table[k].address +=J_length;

    }

    //修改used_table

    i=0;

    while(used_table[i].flag!='0' && i<n)//寻找可以用于记录该作业的分配情况的空表目

    i++;

    if(i>=n)

    {

    cout<<"记录作业的表目已经用完,没有空间填写该表目了!"<<endl;

    //因为无法记录,所以之前的free_table修改的地方就要重新修改回来

    if(free_table[k].flag==0)

    free_table[k].flag = 1;

    else{

    free_table[k].length +=J_length;

    free_table[k].address-=J_length;

    }

    return;

    }

    else{

    used_table[i].address = ad;

    used_table[i].length = J_length;

    used_table[i].flag = J;

    }

    cout<<"最先分配算法已成功完成!"<<endl;

    return;

    }

     

    void menuAllocate(){

    cout<<"选择分配算法: "<<endl;

    cout<<"0-退出"<<endl;

    cout<<"1-最佳适应算法"<<endl;

    cout<<"2-最差适应算法"<<endl;

    cout<<"3-最先适应算法"<<endl;

    }

    运行结果:

    空闲分区列表和已分配空间列表初始状态:

     

    W作业的上下邻区都空闲,回收之后地址被置为18000,地址为18000空闲区的大小由1950被加上W的作业长度50和地址为20000的空闲区的大小200,最后变成2200

     

    继续回收K作业:

    地址为10000的空闲区为作业K的上邻区,加上地址为10050作业K所在空闲区的大小,地址为10000的空闲区大小变为1050

     

    为大小为100J作业分配内存:

     

    1、最佳适应算法

     

    回收J作业:

     

    2、最差适应算法:

     

     

    3、最先适应算法

     

    展开全文
  • 最优最差算法

    2013-07-20 11:30:23
    循环首次适应算法 最佳适应算法 最坏适应算法
  • 首次适应算法: 首次适应算法从空闲分区表的第一个表目起查找该表,把最先能够满足要求的空闲区分配给作业,这种方法目的在于减少查找时间。为适应这种算法,空闲分区表(空闲区链)中的空闲分区要按地址由低到高进行...

    首次适应算法:

    首次适应算法从空闲分区表的第一个表目起查找该表,把最先能够满足要求的空闲区分配给作业,这种方法目的在于减少查找时间。为适应这种算法,空闲分区表(空闲区链)中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区,在低址空间造成许多小的空闲区,在高地址空间保留大的空闲区。

    代码实现

    import java.util.*;
    
    public class FF {
        private static class Node {
            int id;    // 作业id,为-1代表空闲分区;大于0代表已分配
            int start; // 初始地址
            int size;  // 大小
    
            public String toString() {
                return String.format("[%4d, %4d, %4d]", id, start, size);
            }
        }
    
        private static final int SIZE = 4; // 定义碎片大小
        private static Scanner sc = new Scanner(System.in);
    
        // 返回分区链表
        private static List<Node> init() {
            List<Node> list = new ArrayList<>();
            Node node = new Node();
    
            // 初始化,为整个内存空间分配一个空闲节点
            node.id = -1;
            node.start = 0;
            System.out.print("请输入内存空间大小: ");
            node.size = sc.nextInt();
            list.add(node);
    
            return list;
        }
    
        // 为作业id在分区链表list中分配大小为size的内存
        private static boolean add(List<Node> list, int id, int size) {
            Node p = null;
            int i;
    
            // 找到第一个未分配且大于size的内存空间节点p,i为其下标
            for (i = 0; i < list.size(); i++) {
                p = list.get(i);
                if (p.id == -1 && p.size >= size)
                    break;
            }
    
            if (i == list.size()) return false; // 不存在未分配且大于或等于size的内存空间节点,分配失败
    
            // 当原来节点的大小大于size+SIZE时需要创建一个新节点temp保留余下的分区,并插在p的后面
            if (p.size - size > SIZE) {
                Node temp = new Node();
                temp.id = -1;
                temp.start = p.start + size;
                temp.size = p.size - size;
                list.add(i + 1, temp);
            }
            // 将原来节点变成已分配的节点,当剩余空间大于SIZE时,该节点大小为size;当剩余空间小于或等于SIZE时,该节点大小不变,因为剩余大小已经不够再次分配任务;
            p.id = id;
            p.size = (p.size - size > SIZE ? size : p.size);
    
            return true;
        }
    
        // 回收作业id的内存,并合并相邻的空闲分区
        private static boolean del(List<Node> list, int id) {
            Node p = null;
            int i;
    
            // 找到作业id所在的节点p,i为其下标
            for (i = 0; i < list.size(); i++) {
                p = list.get(i);
                if (p.id == id) break;
            }
            if (i == list.size()) return false;//此作业id不存在
    
            p.id = -1; // 回收分区
    
            Node a, b;
            if (i != 0) { // 若第i-1个节点和第i个节点相邻,合并两个分区
                a = list.get(i - 1);
                b = list.get(i);
                if (a.id == -1 && b.id == -1 && a.start + a.size == b.start) {
                    a.size += b.size;
                    list.remove(i);
                    i--;
                }
                // i--是因为可能存在合并后的节点可能与后一个节点相邻
            }
            if (i != list.size() - 1) { // 若第i个节点和第i+1个节点相邻,合并两个分区
                a = list.get(i);
                b = list.get(i + 1);
                if (a.id == -1 && b.id == -1 && a.start + a.size == b.start) {
                    a.size += b.size;
                    list.remove(i + 1);
                }
            }
    
            return true;
        }
    
        private static void show(List<Node> list) {
            System.out.println("已分配分区:");
            int i = 1;
            for (Node temp : list) {
                if (temp.id != -1) System.out.println("分区号:" + i + " 分配情况:" + temp);
                i++;
            }
            i = 1;
            System.out.println("未分配分区:");
            for (Node temp : list) {
                if (temp.id == -1) System.out.println("分区号:" + i + " 分配情况:" + temp);
                i++;
            }
    //        System.out.println(list);
        }
    
        public static void main(String[] args) {
            List<Node> list = init();
            int id, size, op;
            while (true) {
                System.out.println("\n************************************************");
                System.out.println("   1: 为新作业分配内存        2: 撤销作业释放内存");
                System.out.println("   3: 查看FF算法内存分配      4: 退出");
                System.out.print("请输入操作: ");
                op = sc.nextInt();
                switch (op) {
                    case 1:
                        System.out.print("请输入作业id和作业大小size: ");
                        id = sc.nextInt();
                        size = sc.nextInt();
                        if (add(list, id, size)) System.out.println("分配成功");
                        else System.out.println("分配失败");
                        break;
                    case 2:
                        System.out.print("请输入需要撤销的作业id: ");
                        id = sc.nextInt();
                        if (del(list, id)) System.out.println("撤销成功");
                        else System.out.println("撤销失败,此作业id不存在");
                        break;
                    case 3:
                        show(list);
                        break;
                    case 4:
                        return;
                }
            }
        }
    }

    最佳适应和最差适应算法:

    最佳适应算法(Best Fit):

    它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区,这种方法能使碎片尽量小。为适应此算法,空闲分区表(空闲区链)中的空闲分区要按从小到大进行排序,自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区,但造成许多小的空闲区。

     

     

    最差适应算法(Worst Fit)

    也称最差适配算法:

    它从全部空闲区中找出能满足作业要求的、且大小最大的空闲分区,从而使链表中的结点大小趋于均匀,适用于请求分配的内存大小范围较窄的系统。为适应此算法,空闲分区表(空闲区链)中的空闲分区要按大小从大到小进行排序,自表头开始查找到第一个满足要求的自由分区分配。该算法保留小的空闲区,尽量减少小的碎片产生。

    代码实现(其中将Integer.compare(this.size, node.size)中的两个参数互换位置即为WF(最差适应)算法)

    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
    
    public class BF {
        private static class Node implements Comparable {
            int id;    // 作业id,为-1代表空闲分区;大于0代表已分配
            int start; // 初始地址
            int size;  // 大小
    
            public String toString() {
                return String.format("[分区:%d, 起始地址:%d, 分区大小%d]", id, start, size);
            }
    
            @Override
            public int compareTo(Object o) {
                Node node = (Node) o;
                return Integer.compare(this.size, node.size);//升序,此处将compare中的参数颠倒顺序传入即可实现最差适应算法
            }
        }
    
        private static final int SIZE = 4;
        private static Scanner sc = new Scanner(System.in);
    
        //返回分区表
        public static List<Node> init() {
            List<Node> list = new ArrayList<>();
            System.out.println("请输入分区总大小:");
            Node node = new Node();
            node.size = sc.nextInt();
            node.start = 0;
            node.id = -1;
            list.add(node);
            return list;
        }
    
        //为作业分配分区
        public static boolean add(List<Node> list, int id, int size) {
            Node p = null;
            list.sort(Node::compareTo);
            //找到空闲分区最小且大于碎片大小的分区
            int i;
            for (i = 0; i < list.size(); i++) {
                p = list.get(i);
                if (p.size >= size && p.id == -1)
                    break;
            }
    
            if (i == list.size())
                return false;
    
            // 当原来节点的大小大于size+SIZE时需要创建一个新节点temp保留余下的分区,并插在p的后面
            if (p.size - size > SIZE) {
                Node tNode = new Node();
                tNode.start = p.start + size;
                tNode.id = -1;
                tNode.size = p.size - size;
                list.add(i + 1, tNode);
            }
    
            //修改p中的值
            p.id = id;
            p.size = (p.size - size > SIZE ? size : p.size);
    
            return true;
        }
    
        //撤销作业释放分区
        public static boolean delete(List<Node> list, int id) {
            Node p = null;
            Node t = null;
            int i, j;
            for (i = 0; i < list.size(); i++) {
                p = list.get(i);
                if (p.id == id)
                    break;
            }
    
            if (i == list.size())
                return false;//此作业id不存在
    
            p.id = -1;//回收作业
    
            //合并分区
            int count = 0;
            for (j = 0; j < list.size(); j++) {
                t = list.get(j);
                //合并p前面的分区
                if (t.start + t.size == p.start && t.id == -1) {
                    p.start = t.start;
                    p.size += t.size;
                    list.remove(j);
                    count++;
                    if (count == 2)
                        break;
                }
                //合并p后面的分区
                if (p.start + p.size == t.start && t.id == -1) {
                    p.size += t.size;
                    list.remove(j);
                    count++;
                    if (count == 2)
                        break;
                }
            }
            return true;//撤销成功
        }
    
        private static void show(List<Node> list) {
            System.out.println("已分配分区:");
            for (Node t : list) {
                if (t.id != -1) {
                    System.out.println("分配情况" + t);
                }
            }
            System.out.println("未分配分区:");
            for (Node t : list) {
                if (t.id == -1) {
                    System.out.println("分配情况" + t);
                }
            }
        }
    
    //    public static List<Node>
    
        public static void main(String[] args) {
            List<Node> list = init();
            int id, size, op;
            while (true) {
                System.out.println("\n************************************************");
                System.out.println("   1: 为新作业分配分区        2: 撤销作业释放内存");
                System.out.println("   3: 查看内存分区情况        4: 退出");
                System.out.print("请输入操作: ");
                op = sc.nextInt();
                switch (op) {
                    case 1:
                        System.out.print("请输入作业id和作业大小size: ");
                        id = sc.nextInt();
                        size = sc.nextInt();
                        if (add(list, id, size)) System.out.println("分配成功");
                        else System.out.println("分配失败");
                        break;
                    case 2:
                        System.out.print("请输入撤销的作业id: ");
                        id = sc.nextInt();
                        if (delete(list, id)) System.out.println("撤销成功");
                        else System.out.println("撤销失败,此作业id不存在");
                        break;
                    case 3:
                        show(list);
                        break;
                    case 4:
                        return;
                }
            }
        }
    }
    

     

    展开全文
  • 最佳适应算法; 首次适应算法; 最坏适应算法三种算法的图形实现 VS2005 C++实现
  • 以下代码如有疑问,请联系博主,最佳适应算法与最差适应算法只需添加简单的排序即可完成(本代码中未添加) #include <windows.h> #include <conio.h> #include <stdlib.h> #include <stdio.h&...
  • 页面置换算法

    2011-11-30 10:02:45
    操作系统页面置换算法的实现,包括最先适应算法、最佳适应算法、最差适应算法、循环适应算法,很适于操作系统实验。
  • 首次适应算法(FF),循环首次适应算法(NF),最佳适应算法(BF),最差适应算法(WF),回收并打印!
  • 内存分配算法代码模拟。包含 首次适应算法(First Fit) 最佳适应算法(Best Fit)最差适应算法(Worst Fit)伙伴算法(buddy) https://blog.csdn.net/GreyBtfly/article/details/84646981
  • 动态分区分配算法

    2020-12-05 15:59:14
    对于下列连续存储区的请求:12KB、10KB、15KB、18KB,试问:使用首次适应算法、最佳适应算法、最差适应算法和下次适应算法,哪个空闲区将被使用? 首次适应算法 思想:每次都从低地址开始查找,找到第一个能满足...
  • 关于首次适应算法、最佳适应算法和最差适应算法,先看一下百度百科的解释,已经说出了三者的最大区别。 首次适应算法(first-fit): 从空闲分区表的第一个表目起查找该表,把最先能够满足要求的空闲区分配给作业,...
  • 首次适应、最佳适应、最差适应算法 输入: 1)当前内存空闲分区的序列,包括起始地址、空闲分区大小。 2)进程的分区请求序列。 输出要求: 1)三种算法的空闲分区队列。 2)三种算法的分配结果。
  • 1.采用指定算法模拟动态分区管理方式的主存分配。能够处理以下的情形: ⑴ 随机出现的进程i申请jKB内存,程序能判断是否能分配,如果能分配,要求输出分配的首地址Faddress,并要求输出内存使用情况和空闲情况。 ...
  • 关于首次适应算法、最佳适应算法和最差适应算法,先看一下百度百科的解释,已经说出了三者的最大区别。 首次适应算法(first-fit):     从空闲分区表的第一个表目起查找该表,把最先能够满足要求的空闲...
  • java实现的一个简单的动态分区内存分配算法的实现 本人只是一个学生,写这篇东西纯粹是做完课设留个记录,代码仅供参考,不一定正确。 By ...4.最差适应算法。 关键代码: //表结构 class Dy...
  • 发一些大三操作系统的实验代码吸引阅读量吧,... Fit,FF)、循环首次适应算法(Next Fit,NF)、最佳适应算法(Best Fit,BF)、最差适应算法(Worst Fit,WF),本实验中实现了这4种算法,使用C++语言实现。使用SIZ
  • MINI3内存分配算法

    2019-10-08 16:45:43
    1 最差适应算法 2 #ifdef USING_WORST_FIT 3 { 4 //先找到第一个满足要求的空洞, 5 //再以第一个为标准寻找最适合的空洞。 6 //当最适合的空洞完全吻合 7 //就直接划给它,当空洞较大时就切割。 ...
  • 基本思想是:按照共享的思想在对个体的适应值进行调整的同时,将排挤选择和相似个体中适应最差个体被替换的策略分别应用于选择算子和群体的进化中。理论分析和数值实验表明,该算法很好地维持了种群多样性,对于...
  • C++编写的可变分区存储管理实验报告,包括首次适应算法,最佳适应算法和最差适应算法。我也是学生,所以希望这份报告对大家有用哦~
  • 用简单遗传算法求解8皇后问题,每次输出一代染色体中最好和最差个体的适应度,当求的解时便将解输出,解依次为0到7行哪一列放棋子,只是简单的熟悉一下遗传算法,代码没有写注释,如果有问题与我讨论就发邮件吧,...
  • 最差适应算法(WorstFit) 源代码 MemoryBlock class 内存块 package com.company.dynamicinterval; /** * @author hudongsheng * @date 2020/12/15 - 21:47 * 划分节点 */ public class MemoryBlock { pri
  • 此代码是本人原创,模拟最差适应算法实现的动态内存管理,java语言版。
  • 例在可变式分区分配方案中只需要进行一次比较就可以判定系统是否能满足作业对主存空间要求的算法式 A 最先适应算法 B 最佳适应算法 C 最差适应算法 D 固定式分区方法 答案C;例在可变分区存储管理中主要是利用 来
  • 连续分配存储管理方式1....最差适应算法 :基本不留下小空闲分区,但会出现缺乏较大的空闲分区的情况。快速适应算法 (伙伴算法):根据进程常用空间大小进行划分,相同大小的串成一个链,需管理多个各...
  • 提供用户友好的界面设计模拟可变分区管理方式中根据用户的选择使用首次适应算法、最佳适应算法和最差适应算法实现主存的分配与回收。在此过程中,用户可以随时查看当前的内存分配情况,包括每个作业在主存中的位置,...
  • 操作系统报告

    2018-01-18 15:24:36
    绝对原创,请勿抄袭!!! 目录: 一、多级队列调度算法 3 (一)、程序功能: 3 (二)、设计思路 3 (三)、数据结构 3 1、PCB类(进程控制块) 3 2、RQ类(调度队列) 3 (四)、算法设计 3 ...(3)、最差适应算法 17

空空如也

空空如也

1 2 3 4
收藏数 66
精华内容 26
关键字:

最差适应算法