精华内容
下载资源
问答
  • 学习资料收集于网络仅供参考 上次找到的下一个空 闲区地址 循环首次适应算法 该空闲区与作业关系 大于 等于 小于 该空闲获等于作业要 该空闲获小于作业要 该区大于作业要求 求 求 取出空闲区一块空间 截取长度并修改...
  • 分配算法 首次适应算法 最佳适应算法 循环首次适应算法流程图 源代码
  • 操作系统中利用最佳适应算法 最坏适应算法 循环首次适应算法 首次适应算法实现动态内存的分配和回收内存
  • 含本人实验报告,有具体流程图,实验课上写的,有更好的想法可以提出,大家一起学习,赚点积分不容易
  • 模拟动态分区的分配以及回收 ,首次适应算法,循环首次适应算法以及最佳适应算法。
  • 关于首次适应算法、最佳适应算法和最差适应算法,先看一下百度百科的解释,已经说出了三者的最大区别。首次适应算法(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

    展开全文
  • 操作系统课程设计报告_首次适应算法操作系统课程设计报告_首次适应算法
  • 用C语言(不会C这里就用JS实现)分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。其中,空闲分区通过空闲分区链来管理:在进行内存分配时,系统优先使用空闲区低端的空间。 (2)...

    实验目的

    了解动态分区分配方式中使用的数据结构和分配算法,并进一步加深对动态分区存储管理方式及其实现过程的理解。

    实验内容

    (1)

    用C语言(不会C这里就用JS实现)分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。其中,空闲分区通过空闲分区链来管理:在进行内存分配时,系统优先使用空闲区低端的空间。

    (2)

    假设初始状态下,可用的内存空间为640KB,并有下列的请求序列:

    •作业1申请130KB。
    •作业2申请60KB。
    •作业3申请100KB。
    •作业2释放60KB。
    •作业4申请200KB。
    •作业3释放100KB。
    •作业1释放130KB。
    •作业5申请140KB。
    •作业6申请60KB。
    •作业7申请50KB。
    •作业6释放60KB。
    

    请分别采用首次适应算法和最佳适应算法,对内存块进行分配和回收,要求每次分配和回收后显示出空闲分区链的情况。

    思路解析

    1 首先给大家介绍下首次适应算法和最佳适算法
    首次适应算法

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

    最佳适应算法

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

    上面是百度百科给的定义,其实已经解释的很清楚了,我在这里给大家举一个例子。
    比如你有一个数组->[6,4,9,5,2,1],里面的数值分别代表空间吧,这时候你有一个物体,只需要占用2空间。
    这时候你使用这个算法,从6开始遍历,发现6大于你需要的空间,那么这个物体肯定是可以存放的,所以你就选用6来存储这个2空间的物体,然后6空间就会成4空间。其实这个4空间就算是一个碎片了
    如果你又来了一个需要6空间的物体,然后刚好6空间被你用了(只剩下一个4空间),那么只好向下找。这个就是首次适应算法。
    如果你采用最佳适应算法,那么你需要2空间,它从6开始遍历,然后找到刚刚适合2空间的(或者是距离它并且能装下它的空间)2。这时候就把2空间给占用了。如果你需要4空间,那么5就会被占用,剩下1空间。它的缺点就是,会有很多的小碎片。
    2 切入正题 题目要求是两种方法来实现对这个作业的调度

    作业的调度有申请和释放,空间同时有空闲分区和占用的分区。这就意味着我们需要先定义两个方法和两个数组空间

    firstaddress是指该作业的首地址。 lastaddress是该作业的末地址。 length是指长度

    let UseQueue = []// 占用的分区
    let freeQueue = [{
        firstAddress: 0,
        lastAddress: 640,
        length: 640
    }]//空闲的分区  因为首先由640的空间
    function free(Progress)//释放过程
    function FirstFit(Progress)//首次适应算法 申请
    function BestFit(Progress)//最佳适应算法 申请
    

    一共有7个作业,所以我们这里需要先定义一个作业类,然后创建7个作业对象

    function PCB(ID, firstAddress, length, lastAddress, flag) {
        this.ID = ID //进程的ID
        this.firstAddress = firstAddress //进程的首地址
        this.length = length //进程的长度
        this.lastAddress = lastAddress //进程的末地址
        this.flag = flag //是否使用
    }
    
    //定义七个进程 这里首地址都是0,因为没分配
    let one = new PCB(1, 0, 130, 0, 'false')
    let two = new PCB(2, 0, 60, 0, 'false')
    let three = new PCB(3, 0, 100, 0, 'false')
    let four = new PCB(4, 0, 200, 0, 'false')
    let five = new PCB(5, 0, 140, 0, 'false')
    let six = new PCB(6, 0, 60, 0, 'false')
    let seven = new PCB(7, 0, 50, 0, 'false')
    

    先编写一个有用的排序算法,后面会用的到,是利用一个对象中的某个属性进行排序

    function sortlastAddressy(field) {
        return function(a, lastAddress) {
            return a[field] - lastAddress[field];
        }
    }
    

    这里实现首次适应算法

    Progress就是指各个作业 比如one作业 上面已经定义了,每次进入一个作业
    首先对空闲队列里面的空间进行排序(按照首地址排,并不是按照空间的大小排序,按照空间大小排那就是最佳适应算法了)。
    然后对空闲队列进行遍历,找到第一个适应Progress长度的空间,然后分配给它。
    里面的各个参数我进入代码给你们解释,看代码!

    function FirstFit(Progress) {
        Progress.flag = "true"
        let d //它用来记录每次是空闲区间中哪一块被使用,记录它的末地址
        freeQueue.sort(sortlastAddressy("firstAddress"));//利用首地址排序,
        for (let i = 0; i < freeQueue.length; i++) {
            if (freeQueue[i].length > Progress.length) {
                Progress.firstAddress = freeQueue[i].firstAddress
                d = freeQueue[i].lastAddress
                break;//找到以后就退出循环,不在遍历 找到了还遍历个逑啊
            }
        }
        /*
        firstaddress 是我在全局定义的一个变量,用来记录每次在空闲去 生成空闲块的首地址
        比如200-400的空闲   然后作业需要100空间,这里的Progress.firstAddress都是0,因为没有
        被分配,所以都是0,那么firstaddress=100 ,分配以后,剩下的空闲块的首地址就是100了
        
        */
        firstAddress = Progress.firstAddress + Progress.length
        Progress.lastAddress = Progress.firstAddress + Progress.length
        UseQueue.push(Progress)//当作业被申请以后,就要进入占用空间
        /*定义空闲块的末地址,也就是被使用的空闲块的末地址,200-400
        被占用100以后 400还是是末地址   剩下的就是300-400的空闲块/*
        let lastAddress = d 
        let length = lastAddress - firstAddress
        //每次分配作业以后就把 空闲块装进空闲空间
        freeQueue.push({
            firstAddress,
            lastAddress,
            length,
        })
    }
    

    这里实现最佳适应算法

    这里和首次适应算法的流程一样,区别就是排序的时候,这里是使用长度排序,而不是首地址
    空闲区里面第一个就是长度就短了,那么每次遍历只需要从头开始,找到第一个适合自己的,就是那个最适合自己的空间,然后退出,发现自己太聪明了。

    function BestFit(Progress) {
        Progress.flag = "true"
        let d
        freeQueue.sort(sortlastAddressy("length"));
        for (let i = 0; i < freeQueue.length; i++) {
            if (freeQueue[i].length > Progress.length) {
                Progress.firstAddress = freeQueue[i].firstAddress
                d = freeQueue[i].lastAddress
                break;
            }
        }
        firstAddress = Progress.firstAddress + Progress.length
        Progress.lastAddress = Progress.firstAddress + Progress.length
        UseQueue.push(Progress)
        let lastAddress = d
        let length = lastAddress - firstAddress
        freeQueue.push({
            firstAddress,
            lastAddress,
            length
        })
    }
    

    这里实现释放算法

    每次释放,作业就不是调用状态,就把它的状态改为false
    详细解析看代码

    function free(Progress) {
        Progress.flag = 'false'
        //找到要释放的作业的位置
        let index = UseQueue.indexOf(Progress)
        //把该作业删除
        UseQueue.splice(index, 1)
        /* 
        同时记录该作业的首地址,末地址,长度
        因为他们释放以后,他们占用的空间就会变成空闲的,把该空闲块放到空闲空间中
        */
        let firstAddress = Progress.firstAddress
        let lastAddress = Progress.firstAddress + Progress.length
        let length = lastAddress - firstAddress
        freeQueue.push({
            firstAddress,
            lastAddress,
            length
        })
    }
    

    这里实现对空闲空间的操作

    里面的内容众多for循环,你先看的话,你肯定不明白什么意思,这里给你说下它的功能你就知道它的代码意思 。
    这里是因为空闲空间的要求,需要对空间内的碎片进行整合
    比如空闲空间有两个空闲块 分别是100-200 200-300 你发现 第一块的末地址与第二块的首地址相同,你就需要把它们合并成为100-300,这就就剩下一个长度为200的大的空闲块
    同时如果是100-400 300-400 这样的空闲块 你需要把第一块给删除了,因为100-300被使用。这样就只剩下300-400一块空闲。

    function dealFreequeue(freeQueue) {
        if (freeQueue.length > 1) {
            for (let i = 0; i < freeQueue.length; i++) {
                for (let j = 0; j < freeQueue.length; j++) {
                    if (freeQueue[i].lastAddress == freeQueue[j].lastAddress && i != j) {
                        if (freeQueue[i].firstAddress > freeQueue[j].firstAddress) {
                            freeQueue.splice(j, 1)
                        } else {
                            freeQueue.splice(i, 1)
                        }
    
                    }
    
                }
            }
    
            for (let i = 0; i < freeQueue.length; i++) {
                for (let j = 0; j < freeQueue.length; j++) {
                    if (freeQueue[i].lastAddress == freeQueue[j].firstAddress && freeQueue[i] != undefined) {
                        freeQueue[i].lastAddress = freeQueue[j].lastAddress
                        freeQueue[i].length = freeQueue[i].lastAddress - freeQueue[i].firstAddress
                        freeQueue.splice(j, 1)
                        break;
                    }
                }
            }
        }
        freeQueue.sort(sortlastAddressy("firstAddress"));
        return freeQueue
    }
    

    定义七个作业的执行数组

    index=1表示作业申请 index=-1 表示作业释放

    let runqueue = [{
            index: 1,
            Progress: one
        },
        {
            index: 1,
            Progress: two
        },
        {
            index: 1,
            Progress: three
        }, {
            index: -1,
            Progress: two
        }, {
            index: 1,
            Progress: four
        }, {
            index: -1,
            Progress: three
        }, {
            index: -1,
            Progress: one
        }, {
            index: 1,
            Progress: five
        }, {
            index: 1,
            Progress: six
        }, {
            index: 1,
            Progress: seven
        }, {
            index: -1,
            Progress: six
        }
    ]
    

    实现展示界面

    function show(freeQueue) {
        let str = ""
        let str1 = "";
        for (item of freeQueue) {
            str = item.firstAddress + "            " + item.lastAddress + "            " + item.length + "\n"
            str1 += str
        }
        console.log("首地址         末地址          长度")
        console.log(str1)
    
    }
    

    实现首次适应算法的执行函数

    function FirstFitMain(runqueue) {
        for (item of runqueue) {
            console.log(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>")
            if (item.index == 1) {
                console.log("申请-------->", "ID:", item.Progress.ID, "长度:", item.Progress.length)
                FirstFit(item.Progress)
            } else {
                console.log("释放-------->", "ID:", item.Progress.ID, "首地址:", item.Progress.firstAddress, "长度:", item.Progress.length)
                free(item.Progress)
    
            }
            freeQueue = dealFreequeue(freeQueue)
            console.log("空闲的空间:")
            show(freeQueue)
    
            console.log("已被占用的空间:")
            console.log(UseQueue)
        }
    }
    

    实现最佳适应算法的执行函数

    function BestFitMain(runqueue) {
        for (item of runqueue) {
            console.log(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>")
            if (item.index == 1) {
                console.log("申请-------->", "ID:", item.Progress.ID, "长度:", item.Progress.length)
                BestFit(item.Progress)
            } else {
                console.log("释放-------->", "ID:", item.Progress.ID, "首地址:", item.Progress.firstAddress, "长度:", item.Progress.length)
                free(item.Progress)
            }
            freeQueue = dealFreequeue(freeQueue)
            console.log("空间的空间:")
            show(freeQueue)
            console.log("已被占用的空间:")
            console.log(UseQueue)
        }
    }
    

    调用函数

    不使用哪一个算法,就把它注释掉

    //FirstFitMain(runqueue)
    BestFitMain(runqueue)
    

    详细代码

    /*
     * @Author: mikey.zhaopeng 
     * @Date: 2018-12-08 00:20:04 
     * @Last Modified by:   mikey.zhaopeng 
     * @Last Modified time: 2018-12-08 00:20:04 
     */
    function PCB(ID, firstAddress, length, lastAddress, flag) {
        this.ID = ID //进程的ID
        this.firstAddress = firstAddress //进程的首地址
        this.length = length //进程的长度
        this.lastAddress = lastAddress //进程的末地址
        this.flag = flag //是否使用
    }
    //定义七个进程
    let one = new PCB(1, 0, 130, 0, 'false')
    let two = new PCB(2, 0, 60, 0, 'false')
    let three = new PCB(3, 0, 100, 0, 'false')
    let four = new PCB(4, 0, 200, 0, 'false')
    let five = new PCB(5, 0, 140, 0, 'false')
    let six = new PCB(6, 0, 60, 0, 'false')
    let seven = new PCB(7, 0, 50, 0, 'false')
    
    let freeQueue = [{
        firstAddress: 0,
        lastAddress: 640,
        length: 640
    }]
    let UseQueue = []
    let firstAddress = 0
        //
    function sortlastAddressy(field) {
        return function(a, lastAddress) {
            return a[field] - lastAddress[field];
        }
    }
    
    function FirstFit(Progress) {
        Progress.flag = "true"
        let d
        freeQueue.sort(sortlastAddressy("firstAddress"));
        for (let i = 0; i < freeQueue.length; i++) {
            if (freeQueue[i].length > Progress.length) {
                Progress.firstAddress = freeQueue[i].firstAddress
                d = freeQueue[i].lastAddress
                break;
            }
        }
        firstAddress = Progress.firstAddress + Progress.length
        Progress.lastAddress = Progress.firstAddress + Progress.length
        UseQueue.push(Progress)
        let lastAddress = d
        let length = lastAddress - firstAddress
        freeQueue.push({
            firstAddress,
            lastAddress,
            length,
        })
    }
    
    function free(Progress) {
        Progress.flag = 'false'
        let index = UseQueue.indexOf(Progress)
        UseQueue.splice(index, 1)
        let firstAddress = Progress.firstAddress
        let lastAddress = Progress.firstAddress + Progress.length
        let length = lastAddress - firstAddress
        freeQueue.push({
            firstAddress,
            lastAddress,
            length
        })
    }
    
    function BestFit(Progress) {
        Progress.flag = "true"
        let d
        freeQueue.sort(sortlastAddressy("length"));
        for (let i = 0; i < freeQueue.length; i++) {
            if (freeQueue[i].length > Progress.length) {
                Progress.firstAddress = freeQueue[i].firstAddress
                d = freeQueue[i].lastAddress
                break;
            }
        }
        firstAddress = Progress.firstAddress + Progress.length
        Progress.lastAddress = Progress.firstAddress + Progress.length
        UseQueue.push(Progress)
        let lastAddress = d
        let length = lastAddress - firstAddress
        freeQueue.push({
            firstAddress,
            lastAddress,
            length
        })
    }
    let runqueue = [{
            index: 1,
            Progress: one
        },
        {
            index: 1,
            Progress: two
        },
        {
            index: 1,
            Progress: three
        }, {
            index: -1,
            Progress: two
        }, {
            index: 1,
            Progress: four
        }, {
            index: -1,
            Progress: three
        }, {
            index: -1,
            Progress: one
        }, {
            index: 1,
            Progress: five
        }, {
            index: 1,
            Progress: six
        }, {
            index: 1,
            Progress: seven
        }, {
            index: -1,
            Progress: six
        }
    ]
    
    function dealFreequeue(freeQueue) {
        if (freeQueue.length > 1) {
            for (let i = 0; i < freeQueue.length; i++) {
                for (let j = 0; j < freeQueue.length; j++) {
                    if (freeQueue[i].lastAddress == freeQueue[j].lastAddress && i != j) {
                        if (freeQueue[i].firstAddress > freeQueue[j].firstAddress) {
                            freeQueue.splice(j, 1)
                        } else {
                            freeQueue.splice(i, 1)
                        }
    
                    }
    
                }
            }
    
            for (let i = 0; i < freeQueue.length; i++) {
                for (let j = 0; j < freeQueue.length; j++) {
                    if (freeQueue[i].lastAddress == freeQueue[j].firstAddress && freeQueue[i] != undefined) {
                        freeQueue[i].lastAddress = freeQueue[j].lastAddress
                        freeQueue[i].length = freeQueue[i].lastAddress - freeQueue[i].firstAddress
                        freeQueue.splice(j, 1)
                        break;
                    }
                }
            }
        }
        freeQueue.sort(sortlastAddressy("firstAddress"));
        return freeQueue
    }
    
    function FirstFitMain(runqueue) {
        for (item of runqueue) {
            console.log(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>")
            if (item.index == 1) {
                console.log("申请-------->", "ID:", item.Progress.ID, "长度:", item.Progress.length)
                FirstFit(item.Progress)
            } else {
                console.log("释放-------->", "ID:", item.Progress.ID, "首地址:", item.Progress.firstAddress, "长度:", item.Progress.length)
                free(item.Progress)
    
            }
            freeQueue = dealFreequeue(freeQueue)
            console.log("空闲的空间:")
            show(freeQueue)
    
            console.log("已被占用的空间:")
            console.log(UseQueue)
        }
    }
    
    function BestFitMain(runqueue) {
        for (item of runqueue) {
            console.log(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>")
            if (item.index == 1) {
                console.log("申请-------->", "ID:", item.Progress.ID, "长度:", item.Progress.length)
                BestFit(item.Progress)
            } else {
                console.log("释放-------->", "ID:", item.Progress.ID, "首地址:", item.Progress.firstAddress, "长度:", item.Progress.length)
                free(item.Progress)
            }
            freeQueue = dealFreequeue(freeQueue)
            console.log("空间的空间:")
            show(freeQueue)
            console.log("已被占用的空间:")
            console.log(UseQueue)
        }
    }
    
    function show(freeQueue) {
        let str = ""
        let str1 = "";
        for (item of freeQueue) {
            str = item.firstAddress + "            " + item.lastAddress + "            " + item.length + "\n"
            str1 += str
        }
        console.log("首地址         末地址          长度")
        console.log(str1)
    
    }
    //FirstFitMain(runqueue)
    BestFitMain(runqueue)
    

    给大家看下结果,这里就截几个图,并不是全部结果,就前三个
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    下面是我的博客地址:

    http://jsfei.top/

    展开全文
  • 操作系统实验 首次适应算法 运行无误
  • 首次适应算法(FF)和循环首次适应算法(NF)

    万次阅读 多人点赞 2015-12-26 22:13:35
    FF和NF算法都是基于顺序搜索的动态分区分配算法,在内存中检索一块分区分配给作业。如果空间大小合适则分配,如果找不到空间则等待。 FF算法按地址递增从头扫描空闲分区,如果找到空闲分区大小>=作业大小则分配。...

    FF和NF算法都是基于顺序搜索的动态分区分配算法,在内存中检索一块分区分配给作业。如果空间大小合适则分配,如果找不到空间则等待。

    FF算法按地址递增从头扫描空闲分区,如果找到空闲分区大小>=作业大小则分配。如果扫描完空闲分区表都没有找到分区,则分配失败。

    NF算法和FF算法类似,但是NF算法每次分配都会记录下位置,下次分配的时候从记录的位置开始,循环扫描一遍空闲分区。


    注:回收分区的算法写的和书上不太一样,书上是分配过后把分区从空闲分区链中移除,我是直接分配然后状态为设置为false,所以可能不太一样。








    //公共模块,负责定义结构体,初始化,显示结果,回收
    //BlockJob.h
    #ifndef BLOCKJOB_H_
    #define BLOCKJOB_H_
    
    #include <vector>
    
    const int MINSIZE = 10;		//最小不可分割分区大小
    
    							//空闲分区
    typedef struct block
    {
    	int start;	//开始地址
    	int size;	//大小
    	bool state;	//分区状态 true:空闲 false:占用
    }block;
    
    //作业
    typedef struct job
    {
    	int size;	//作业大小
    	int start;	//分配的分区首址
    	int BlockSize;	//分配空闲分区的大小(可能大于作业大小)
    };
    
    //初始化空闲分区与作业
    void init(std::vector<block> &BlockList, std::vector<job> &JobList);
    
    //显示结果
    void show(std::vector<block> &BlockList, std::vector<job> &JobList);
    
    //回收分区
    void recycle(std::vector<block> &BlockList, std::vector<job> &JobList);
    
    #endif
    
    //BlockJob.cpp
    #include "BlockJob.h"
    #include <iostream>
    #include <iomanip>
    
    //初始化空闲分区与作业
    void init(std::vector<block> &BlockList, std::vector<job> &JobList)
    {
    	std::cout << "输入空闲分区数: ";
    	int num;
    	std::cin >> num;
    
    	std::cout << "输入空闲分区的起始地址与大小: \n";
    	block temp;
    	for (int i = 0; i < num; ++i)
    	{
    		std::cin >> temp.start >> temp.size;
    		temp.state = true;
    		BlockList.push_back(temp);
    	}
    
    	std::cout << "输入作业数: ";
    	std::cin >> num;
    	std::cout << "输入作业的大小: \n";
    	job tempj;
    	for (int i = 0; i < num; ++i)
    	{
    		std::cin >> tempj.size;
    		tempj.BlockSize = 0;
    		tempj.start = 0;
    		JobList.push_back(tempj);
    	}
    }
    
    //显示结果
    void show(std::vector<block> &BlockList, std::vector<job> &JobList)
    {
    	using std::setw;
    	std::cout.setf(std::ios_base::left);
    
    	std::cout << "空闲分区表: \n";
    	std::cout << setw(10) << "分区号" << setw(10) << "分区大小" << setw(10) << "分区始址" << setw(10) << "状态" << std::endl;
    	int num = 0;
    	for (std::vector<block>::iterator it = BlockList.begin(); it != BlockList.end(); ++it, ++num)
    		std::cout << setw(10) << num << setw(10) << (*it).size << setw(10) << (*it).start << setw(10) << (((*it).state == true) ? "空闲" : "占用") << std::endl;
    
    	std::cout << "作业信息: \n";
    	std::cout << setw(10) << "作业号" << setw(10) << "作业大小" << setw(10) << "分区大小" << setw(10) << "分区始址" << std::endl;
    	num = 0;
    	for (std::vector<job>::iterator it = JobList.begin(); it != JobList.end(); ++it, ++num)
    		std::cout << setw(10) << num << setw(10) << (*it).size << setw(10) << (*it).BlockSize << setw(10) << (*it).start << std::endl;
    }
    
    //回收分区
    void recycle(std::vector<block> &BlockList, std::vector<job> &JobList)
    {
    	std::cout << "输入回收分区的首址: ";
    	int start;
    	std::cin >> start;
    
    	for (std::vector<block>::iterator it = BlockList.begin(); it != BlockList.end(); ++it)
    	{
    		//找到要回收的分区
    		if (start == (*it).start)
    		{
    			//与前一个分区邻接
    			if (it != BlockList.begin() && (*(it - 1)).start + (*(it - 1)).size == (*it).start)
    			{
    				//与后一个分区邻接
    				if (it != BlockList.end() - 1 && (*it).start + (*it).size == (*(it + 1)).start)
    				{
    					//将前一块分区,要回收的分区,后一块分区合并
    					(*(it - 1)).size += (*it).size + (*(it + 1)).size;
    					(*(it - 1)).state = true;
    					BlockList.erase(it);
    					BlockList.erase(it);
    				}
    				else	//不与后一个分区邻接
    				{
    					//将此分区与前一个分区合并
    					(*(it - 1)).size += (*it).size;
    					(*(it - 1)).state = true;
    					BlockList.erase(it);
    				}
    			}
    			else if(it != BlockList.end()-1 && (*it).start +(*it).size == (*(it+1)).start)	//不与前一个分区邻接,与后一个分区邻接
    			{
    				//将此分区与后一个分区合并
    				(*it).size += (*(it + 1)).size;
    				(*it).state = true;
    				BlockList.erase(it + 1);
    			}
    			else	//都不邻接
    			{
    				(*it).state = true;
    			}
    			break;
    		}
    	}
    
    	for (std::vector<job>::iterator it = JobList.begin(); it != JobList.end(); ++it)
    	{
    		if ((*it).start == start)
    		{
    			(*it).BlockSize = (*it).start = 0;
    			break;
    		}
    	}
    }


    //FF.cpp
    #include "BlockJob.h"
    
    //FF算法
    void FF(std::vector<block> &BlockList, std::vector<job> &JobList);
    
    int main()
    {
    	std::vector<block> BlockList;
    	std::vector<job> JobList;
    
    	//初始化空闲分区与作业
    	init(BlockList, JobList);
    
    	//FF算法
    	FF(BlockList, JobList);
    
    	//显示结果
    	show(BlockList, JobList);
    
    	//回收分区
    	recycle(BlockList, JobList);
    
    	//显示结果
    	show(BlockList, JobList);
    
    	return 0;
    }
    
    //FF算法
    void FF(std::vector<block> &BlockList, std::vector<job> &JobList)
    {
    	for (std::vector<job>::iterator ItJob = JobList.begin(); ItJob != JobList.end(); ++ItJob)
    	{
    		for (std::vector<block>::iterator ItBlock = BlockList.begin(); ItBlock != BlockList.end(); ++ItBlock)
    		{
    			//分区未被使用且能够装下作业
    			if ((*ItBlock).state && (*ItBlock).size >= (*ItJob).size)
    			{
    				if ((*ItBlock).size - (*ItJob).size > MINSIZE)	//剩余空间还可以继续分配
    				{
    					(*ItBlock).state = false;
    
    					//修改作业信息,分配空间
    					(*ItJob).start = (*ItBlock).start;
    					(*ItJob).BlockSize = (*ItJob).size;
    
    					//添加新表项
    					block NewBlock;
    					NewBlock.start = (*ItBlock).start + (*ItJob).size;
    					NewBlock.size = (*ItBlock).size - (*ItJob).size;
    					NewBlock.state = true;
    					(*ItBlock).size = (*ItJob).size;
    					BlockList.insert(ItBlock + 1, NewBlock);
    
    				}
    				else		//剩余空间不可分配,全部分配给此作业
    				{
    					(*ItBlock).state = false;
    
    					//修改作业信息,分配空间
    					(*ItJob).start = (*ItBlock).start;
    					(*ItJob).BlockSize = (*ItBlock).size;
    				}
    
    				break;
    			}
    		}
    	}
    }
    
    


    //NF.cpp
    #include "BlockJob.h"
    
    //NF算法
    void NF(std::vector<block> &BlockList, std::vector<job> &JobList);
    
    int main()
    {
    	std::vector<block> BlockList;
    	std::vector<job> JobList;
    
    	//初始化空闲分区与作业
    	init(BlockList, JobList);
    
    	//NF算法
    	NF(BlockList, JobList);
    
    	//显示结果
    	show(BlockList, JobList);
    
    	//回收分区
    	recycle(BlockList, JobList);
    
    	//显示结果
    	show(BlockList, JobList);
    
    	return 0;
    }
    
    //NF算法
    void NF(std::vector<block> &BlockList, std::vector<job> &JobList)
    {
    	int pos = 0;		//上一次查找的位置
    
    	for (std::vector<job>::iterator ItJob = JobList.begin(); ItJob != JobList.end(); ++ItJob)
    	{
    		std::vector<block>::iterator ItBlock = BlockList.begin() + pos;
    		do {
    			//分区未被使用且能够装下作业
    			if ((*ItBlock).state && (*ItBlock).size >= (*ItJob).size)
    			{
    				pos = &(*ItBlock) - &BlockList[0];	//记录此次分配位置
    				if ((*ItBlock).size - (*ItJob).size > MINSIZE)	//剩余空间还可以继续分配
    				{
    					(*ItBlock).state = false;
    
    					//修改作业信息,分配空间
    					(*ItJob).start = (*ItBlock).start;
    					(*ItJob).BlockSize = (*ItJob).size;
    
    					//添加新表项
    					block NewBlock;
    					NewBlock.start = (*ItBlock).start + (*ItJob).size;
    					NewBlock.size = (*ItBlock).size - (*ItJob).size;
    					NewBlock.state = true;
    					(*ItBlock).size = (*ItJob).size;
    					BlockList.insert(ItBlock + 1, NewBlock);
    
    				}
    				else		//剩余空间不可分配,全部分配给此作业
    				{
    					(*ItBlock).state = false;
    
    					//修改作业信息,分配空间
    					(*ItJob).start = (*ItBlock).start;
    					(*ItJob).BlockSize = (*ItBlock).size;
    				}
    
    				break;
    			}
    
    			++ItBlock;
    			if (ItBlock == BlockList.end())
    				ItBlock = BlockList.begin();
    		} while (pos != &(*ItBlock) - &BlockList[0]);
    	}
    }


    展开全文
  • 首次适应算法(First Fit):该算法从空闲分区链首开始查找,直至找到一个能满足其大小要求的空闲分区为止。然后再按照作业的大小,从该分区中划出一块内存分配给请求者,余下的空闲分区仍留在空闲分区链中。 最佳...

    【实验目的】

    本实验主要练习主存的各种分配和回收。所谓分配,就是解决多道作业或多进程如何共享主存空间的问题。所谓回收,就是当作业运行完成时,将作业或进程所占用的主存空间归还给系统。主存的分配和回收的实现就是与主存储器的管理方式有关的。通过本实验理解在不同的存储管理方式下,如何实现主存空间的分配与回收。

    【实验原理】

    1. 首次适应算法(First Fit)
      该算法从空闲分区链首开始查找,直至找到一个能满足其大小要求的空闲分区为止。然后再按照作业的大小,从该分区中划出一块内存分配给请求者,余下的空闲分区仍留在空闲分区链中。
      特点:该算法倾向于使用内存中低地址部分的空闲区,在高地址部分的空闲区很少被利用,从而保留了高地址部分的大空闲区。显然为以后到达的大作业分配大的内存空间创造了条件。
      缺点:低地址部分不断被划分,留下许多难以利用、很小的空闲区,而每次查找又都从低地址部分开始,会增加查找的开销。
    2. 最佳适应算法(Best Fit)
      该算法总是把既能满足要求,又是最小的空闲分区分配给作业。为了加速查找,该算法要求将所有的空闲区按其大小排序后,以递增顺序形成一个空白链。这样每次找到的第一个满足要求的空闲区,必然是最优的。孤立地看,该算法似乎是最优的,但事实上并不一定。因为每次分配后剩余的空间一定是最小的,在存储器中将留下许多难以利用的小空闲区。同时每次分配后必须重新排序,这也带来了一定的开销。
      特点:每次分配给文件的都是最合适该文件大小的分区。
      缺点:内存中留下许多难以利用的小的空闲区。

    【实验内容】

    采用可变式分区管理,使用首次或最佳适应算法实现主存的分配与回收。

    1.数据结构与符号说明

    1.1全局变量
    在这里插入图片描述
    1.2 PST 类
    在这里插入图片描述
    1.3 Memory 类
    在这里插入图片描述

    2. 程序流程图与源程序

    2.1 程序流程图
    首次适应算法分配框图和首次适应算法回收框图分别如图3.1和图3.2所示,最佳适应算法则在首次适应算法基础上加上对内存按大小排序,流程图几乎一致,这里不再给出。
    在这里插入图片描述
    在这里插入图片描述
    2.2 源程序

    #include<iostream>
    #include<string>
    #define OK 0
    #define ERROR -1
    #define MAXSIZE 10	// 默认表长最大为10
    using namespace std;
    string Unallocated = "Unallocated";	// 未分配
    string Allocated = "Allocated";	// 已分配
    string Empty = "Empty";		// 空表目
    
    class Memory;
    class PST	// Partition Specification Table分区说明表
    {
    public:
    	PST();	// 构造函数
    	void display();	// 打印分区说明表
    	void sort();	// 表目按分区从小到大排序
    	int search(int start);	// 寻找起始地址为start的分区,并返回其编号
    	void Move_Forward(int n);	// 从第n个到最后一个非空表项,每一表项向前移
    	void Move_Backwark(int n);	// 从第n个到最后一个非空表项,每一表项向后移
    	friend class Memory;
    private:
    	int *Start_Address;		// 分区起始地址
    	int *Partition_Size;	// 分区大小
    	string *Partition_Status;	// 分区状态
    	int Real_Length;		// 实际表长(即表中的分区数)
    };
    PST::PST()	// 构造函数,初始化
    {
    	Start_Address = new int[MAXSIZE];
    	Partition_Size = new int[MAXSIZE];
    	Partition_Status = new string[MAXSIZE];
    	for (int i = 0; i < MAXSIZE; i++) {
    		Start_Address[i] = ERROR;	// 将所有表目置空
    		Partition_Size[i] = ERROR;
    		Partition_Status[i] = Empty;
    	}
    	Real_Length = 0;	// 实际表长为0
    }
    void PST::display()// 打印分区说明表
    {
    	cout << "\tstart" << "\tsize" << "\tstatus" << endl;
    	cout << "\t━━━━━━━━━━━━━━━━━━━━━━━━━━━━"<<endl;
    	if (Real_Length > 0) {
    		for (int i = 0; i < Real_Length; i++) {
    			cout << "\t" << Start_Address[i] << "(KB)\t" << Partition_Size[i] << "(KB)\t" << Partition_Status[i] << endl;
    		}
    	}
    	for (int i = Real_Length; i < MAXSIZE; i++) {
    		cout << "\t\t\tEmpty" << endl;
    	}
    	cout << endl;
    }
    void PST::sort()	// 表目按分区从小到大排序(最佳适应算法中使用)
    {
    	int i, j, temp;
    	for (i = 0; i < Real_Length - 1; i++) {	// 使用冒泡排序将分区按大小升序排列
    		for (j = 0; j < Real_Length - 1 - i; j++) {
    			if (Partition_Size[j] > Partition_Size[j + 1]) {
    				temp = Partition_Size[j];
    				Partition_Size[j] = Partition_Size[j + 1];
    				Partition_Size[j + 1] = temp;
    				temp = Start_Address[j];
    				Start_Address[j] = Start_Address[j + 1];
    				Start_Address[j + 1] = temp;
    			}
    		}
    	}
    }
    int PST::search(int start)	// 寻找起始地址为start的分区,并返回其编号
    {
    	for (int i = 0; i < Real_Length; i++) {
    		if (Start_Address[i]==start){
    			return i;
    		}
    	}
    	return ERROR;	// 若不存在则返回-1
    }
    void PST::Move_Forward(int n) // 从第n个到最后一个非空表项,每一表项向前移
    {
    	for (int i = n ; i < Real_Length; i++) {
    		Start_Address[i] = Start_Address[i + 1];
    		Partition_Size[i] = Partition_Size[i + 1];
    		Partition_Status[i] = Partition_Status[i + 1];
    	}
    }
    void PST::Move_Backwark(int n)	// 从第n个到最后一个非空表项,每一表项向后移
    {
    	for (int i = Real_Length - 1; i > n; i--) {
    		Start_Address[i] = Start_Address[i - 1];
    		Partition_Size[i] = Partition_Size[i - 1];
    		Partition_Status[i] = Partition_Status[i - 1];
    	}
    	Start_Address[n] = Partition_Size[n] = ERROR;
    	Partition_Status[n] = Empty;
    }
    
    class Memory
    {
    public:
    	Memory();	// 构造函数
    	void display();	// 打印主存状态
    	int allocate(int jobs, int choice);	// 分配
    	void recycle(int start);	// 回收
    private:
    	PST Free_Table, Allocated_Table;	// 空闲分区表,已分配区表
    };
    Memory::Memory()	// 构造函数,手动初始化主存空间状态
    {	
    	int num;	// num:分区数
    	cout << "\n    Input the num of partitions in Memory:    ";
    	cin >> num;	// 手动输入分区数
    	int start, size, state;	// 分区起始地址,大小,状态
    	cout << "\n    Input the start address, size, status of each partition:" << endl;
    	cout << "    (Tip : About the status, 0 is unallocated, and 1 is allocated.)" << endl;
    	for (int i = 0; i < num; i++){
    		cout <<"\t"<< i + 1 << ".  ";
    		cin >> start >> size >> state;// 手动输入分区起始地址,大小,状态
    		if (state==0){
    			Free_Table.Start_Address[Free_Table.Real_Length] = start;
    			Free_Table.Partition_Size[Free_Table.Real_Length] = size;
    			Free_Table.Partition_Status[Free_Table.Real_Length] = Unallocated;
    			Free_Table.Real_Length++;
    		}
    		else if(state == 1){
    			Allocated_Table.Start_Address[Allocated_Table.Real_Length] = start;
    			Allocated_Table.Partition_Size[Allocated_Table.Real_Length] = size;
    			Allocated_Table.Partition_Status[Allocated_Table.Real_Length] = Allocated;
    			Allocated_Table.Real_Length++;
    		}
    	}
    }
    void Memory::display()
    {
    	cout << endl;
    	cout << "    Memory: " << endl;
    	cout << "\tstart" << "\tsize" << "\tstatus" << endl;	// 按地址顺序打印各个分区及其状态
    	cout << "\t━━━━━━━━━━━━━━━━━━━━━━━━━━━━" << endl;
    	int i, num;
    	int start = 0;
    	for (i = 0; i < Free_Table.Real_Length + Allocated_Table.Real_Length; i++) {
    		num = Free_Table.search(start);
    		if (num != ERROR) {
    			cout << "\t" << Free_Table.Start_Address[num] << "(KB)\t" << Free_Table.Partition_Size[num] << "(KB)\t" << Free_Table.Partition_Status[num] << endl;
    			start += Free_Table.Partition_Size[num];
    			continue;
    		}
    		num = Allocated_Table.search(start);
    		if (num != ERROR) {
    			cout << "\t" << Allocated_Table.Start_Address[num] << "(KB)\t" << Allocated_Table.Partition_Size[num] << "(KB)\t" << Allocated_Table.Partition_Status[num] << endl;
    			start += Allocated_Table.Partition_Size[num];
    			continue;
    		}
    	}
    	cout << endl;
    	cout << "    Free partition table:" << endl;
    	Free_Table.display();
    }
    int Memory::allocate(int XK, int choice)	// XK为作业大小,choice为算法选择,1为首次适应,2为最佳适应
    {
    	if (choice == 2) {	// 选择最佳适应分配
    		Free_Table.sort();	// 最佳适应才会执行,将分区按大小升序排列
    	}
    	for (int j = 0; j < Free_Table.Real_Length; j++) {
    		if (Free_Table.Partition_Status[j] == Unallocated) {	// 第i个表项中分区未分配
    			if (Free_Table.Partition_Size[j] > XK) {	// 分区大小 > 作业大小
    				// 登记已分配表
    				Allocated_Table.Partition_Size[Allocated_Table.Real_Length] = XK;	// 已分配分区大小
    				Allocated_Table.Start_Address[Allocated_Table.Real_Length] = Free_Table.Start_Address[j]; // 已分配分区起始地址
    				Allocated_Table.Partition_Status[Allocated_Table.Real_Length] = Allocated;	// 表目状态为已分配
    				Allocated_Table.Real_Length++;
    				// 修改空闲分区表
    				Free_Table.Partition_Size[j] -= XK;	// 分区剩余大小
    				Free_Table.Start_Address[j] += XK;	// 分区新的起始地址
    				return OK;
    			}
    			else if (Free_Table.Partition_Size[j] == XK){	// 分区大小 = 作业大小
    				// 登记已分配表
    				Allocated_Table.Partition_Size[Allocated_Table.Real_Length] = XK;	// 已分配分区大小
    				Allocated_Table.Start_Address[Allocated_Table.Real_Length] = Free_Table.Start_Address[j];// 已分配分区起始地址
    				Allocated_Table.Partition_Status[Allocated_Table.Real_Length] = Allocated;	// 表目状态为已分配
    				Allocated_Table.Real_Length++;
    				// 修改空闲分区表
    				Free_Table.Start_Address[j] = Free_Table.Partition_Size[j] = ERROR;
    				Free_Table.Partition_Status[j] == Empty;	// 空闲分区表中,该表项置空
    				Free_Table.Move_Forward(j);	// 置空后将该表项后移
    				Free_Table.Real_Length--;	// 实际表长减1
    				return OK;
    			}
    			else {	// 分区大小 < 作业大小
    				if (j + 1 == Free_Table.Real_Length) {	// 后一个表项为空表项,则作业等待
    					return ERROR;
    				}
    				else {	// 后一个表项非空,则查看后一个表项
    					continue;
    				}
    			}
    		}
    		else {	// 第i个表项为空表目
    			if (j + 1 == Free_Table.Real_Length) {// 后一个表项为空表项,则作业等待
    				return ERROR;
    			}
    			else {	// 后一个表项非空,则查看后一个表项
    				continue;
    			}
    		}
    	}
    }
    void Memory::recycle(int start)	// 回收起始地址为start的分区空间
    {
    	int num = Allocated_Table.search(start);// num为待回收的分区的编号
    	int end = start + Allocated_Table.Partition_Size[num];	// end为与待回收的分区尾部邻接的分区起始地址
    	int end_adjoin = Free_Table.search(end);// 与待回收的分区尾部邻接的分区编号
    	int start_adjoin = ERROR;	// 与待回收的分区起始地址邻接的分区编号
    	int i;
    	for (i = 0; i < Free_Table.Real_Length; i++) {
    		if (Free_Table.Start_Address[i]+Free_Table.Partition_Size[i]==start){
    			start_adjoin = i;
    			break;
    		}
    	}
    	if (start_adjoin != ERROR && end_adjoin != ERROR) {// 待回收分区头尾都有空闲分区邻接
    		Free_Table.Partition_Size[start_adjoin] += (Allocated_Table.Partition_Size[num] + Free_Table.Partition_Size[end_adjoin]);
    		Free_Table.Move_Forward(end_adjoin);
    		Free_Table.Real_Length--;
    	}
    	else if (start_adjoin != ERROR) {	// 待回收分区起始处有空闲分区邻接
    		Free_Table.Partition_Size[start_adjoin] += Allocated_Table.Partition_Size[num];
    	}
    	else if (end_adjoin != ERROR) {	// 待回收分区尾部有空闲分区邻接
    		Free_Table.Start_Address[end_adjoin] = start;
    		Free_Table.Partition_Size[end_adjoin] += Allocated_Table.Partition_Size[num];
    	}
    	else {	// 待回收分区不与任何空闲分区邻接
    		Free_Table.Start_Address[Free_Table.Real_Length] = start;
    		Free_Table.Partition_Size[Free_Table.Real_Length] = Allocated_Table.Partition_Size[num];
    		Free_Table.Partition_Status[Free_Table.Real_Length] = Unallocated;
    		Free_Table.Real_Length++;
    	}
    	Allocated_Table.Move_Forward(num);
    }
    
    int main()
    {
    	Memory m;// 主存
    	int operate_choice = 1;// 对下一步操作的选择
    	while (operate_choice == 1 || operate_choice == 2) {
    		m.display();	// 显示主存与空闲分区表
    		cout << endl;
    		cout << "\n    Operation options:\n\t1.Allocate space for a job; \n\t2.Recycle space from a job;\n\t3.Any key to Quit"<<endl;
    		cout << "    Choose: ";
    		cin >> operate_choice;
    		if (operate_choice == 1) {
    			cout << "\n    Input the size of job: ";
    			int job;
    			cin >> job;
    
    			int algorithm_choice;
    			cout << "\n    Allocate algorithm options: \n\t1.First Fits;\n\t2.Best Fits." << endl;
    			cout << "    Choose: ";
    			cin >> algorithm_choice;
    			int allocate_result = m.allocate(job, algorithm_choice);
    			if (allocate_result != ERROR) {
    				cout << "\n----Allocate Succeed!----" << endl;	// 分配成功,则打印主存
    				m.display();
    			}
    			else {
    				cout << "\n----Allocate failed!----" << endl;	// 分配失败
    			}
    			cout << endl;
    		}
    		else if (operate_choice == 2) {
    			int start;
    			cout << "\n    Input the start address to recycle: ";	// 输入待回收的分区起始地址
    			cin >> start;
    			m.recycle(start);
    			cout << "\n----Recycle succeed!----" << endl;	// 回收完成
    			m.display();
    		}
    		system("pause");
    		system("cls");
    	}
    	system("pause");
    	return 0;
    }
    
    

    3. 运行结果

    3.1 手动初始化主存
    手动输入主存主存初始状态的分区数,这里输入的是6个;再手动输入每个分区的起始地址,长度,状态。
    在这里插入图片描述
    输入完毕,打印主存和空闲分区表:
    在这里插入图片描述
    3.2 首次适应算法
    操作选择,输入1,为作业分配空间;这里输入作业大小为30(KB);算法选择,输入1,首次适应算法。
    在这里插入图片描述
    分配成功后的主存和空闲分区表:(从起始地址为110KB的分区分配了30KB给作业)
    在这里插入图片描述
    操作选择,输入2,回收作业空间;这里回收的空间起始地址为0KB;
    在这里插入图片描述
    成功回收地址为0KB的分区(低地址,高地址都不邻接,新的空闲分区加入表中):
    在这里插入图片描述
    3.3 最佳适应算法
    操作选择,输入1,为作业分配空间;这里输入作业大小为5(KB);算法选择,输入2,首次适应算法。
    在这里插入图片描述
    分配成功后的主存和空闲分区表:(从起始地址为0KB的分区分配了5KB给作业)
    在这里插入图片描述
    3.4 回收:逐个回收被分配出去的分区。
    成功回收起始地址为0KB的分区(高地址邻接)
    在这里插入图片描述
    成功回收起始地址为10KB的分区(低地址邻接)
    在这里插入图片描述
    成功回收起始地址为110KB的分区(高地址邻接)
    在这里插入图片描述
    成功回收起始地址为20KB的分区(低地址、高地址都邻接)
    在这里插入图片描述
    成功回收起始地址为65KB的分区(低地址、高地址都邻接)
    在这里插入图片描述
    3.5 退出
    在这里插入图片描述

    【小结或讨论】

    实验过程中,发现首次适应算法和最佳适应算法的流程中,唯一区别在于最佳适应算法在分配前将空闲分区表按升序排列(即先分配空间小的分区),所以将两个算法合并在同一个allocate()函数中,通过与用户交互来选择分配方法。

    展开全文
  • 用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc()和回收过程free()。其中,空闲分区通过空闲分区链来管理:在进行内存分配时,系统优先使用空闲区低端的空间。 假设初始状态下,可用的内存...
  • 一、概述  因为这次os作业对用户在控制台的输入输出有要求... 因为不同内存分配算法,只有对空闲分区表的排序不同,所以可以将FF和BF等内存分配算法一起实现。    如果只关心和算法有关的核心代码的话,只看M...
  • 动态分区分配-首次适应算法

    千次阅读 2014-05-23 15:24:20
    动态分区分配-首次适应算法 动态分区分配是根据进程的实际需要,动态的为之分配内存的空间。 首次适应算法,要求空闲分区链以地址递增的次序链接,在分配内存时,从链首开始顺序查找,直到找到一个大小能满足要求...
  • 首次适应算法是将空闲区按照起始地址排序,从中找到第一个刚好可以容纳进程所需空间的区域进行分配。 代码的思路相对简单,时间性能上不是很高,仅仅达到了效果。 1.用C语言分别实现采用首次适应算法和最佳适应算法...
  • 采用首次适应算法实现动态分区分配过程的模拟 实验要求 用C语言编程,实现采用首次适应算法的动态分区分配过程 实验内容 (1)空闲分区通过空闲分区链来管理;进行内存分配时,系统优先使用空闲区低端的空间。 (2)...
  • NF 循环首次适应算法 (java)

    千次阅读 2019-12-24 20:08:44
    2. 邻近适应 (循环首次适应)NF 从上一次 查找结束的位置 开始查找 运行结果 -----java 代码 ---- ... * NF 循环首次适应算法 * @author ymj * @Date: 2019/12/24 16:18 */ public class NF { ...
  • 操作系统-首次适应算法

    千次阅读 2017-11-27 20:20:47
    所以运用链表操作首次适应算法时初始化内存分配的空闲区大小是固定的,接下来的代码是初始化的大小为用户输入的max,然后就可以进行分割 回收的时候回考虑三种情况: 一是回收的区域的前一块和后一块均是空闲区,则...
  • 分配方式可分为四类:单一连续分配、固定分区分配、动态分区分配以及动态可重定位分区分配算法四种方式,其中动态分区分配算法就是此实验的实验对象。动态分区分配又称为可变分区分配,它是根据进程的实际需要,动态...
  • 里面有实验题目,实验流程图,实验代码,运行结果,测试用例,很全面的。
  • 课程设计报告 课程设计题目循环首次适应的动态分区分配算法模拟 专 业计算机科学与技术 班 级10204102 姓 名...基本思想4 2数据结构4 三运行环境6 四流程图6 五循环首次适应算法代码5 六调试结果11 七总结14 八参考文献
  • 本次实现均是基于顺序搜索的动态分区分配算法,为实现动态分配,通常将系统中的空闲分区...1.首次适应算法(first Fit,FF) 流程图: 2.循环首次适用算法(next fit ,NF) 流程图: 3.最佳适应算法(best fit ,...
  • 用c 语言实现的最佳适应算法。 用C语言或C++语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程allocate()和回收过程reclaim()
  • 最优适应算法

    千次阅读 2010-05-26 21:17:00
    【问题描述】编写程序,采用最优适应算法实现可变分区存储管理方式的主存分配及回收。设计具体包括:首先构造主存空间分配表,然后完成主存空间的分配和回收;最后编写主函数对所做工作进行测试。【提示】动态构造...
  • 动态分区-首次适应&最佳适应

    千次阅读 2015-11-05 11:32:47
    首次适应算法 循环首次适应算法 最佳适应算法 1,在内存分配时,系统优先使用空闲区低端的空间 10240+102380=112640 从地址112460开始分配,由低端向高端增长。 例如:分配给作业1,作业长度20,==》起始地址:...
  • 操作系统实验,动态分区存储管理,使用最佳适应算法,内存的分配和回收
  • 动态分区分配算法的模拟四类算法首次适应算法(FF)循环首次适应算法(NF)最佳适应算法(BF)最坏适应算法(WF)四类算法流程图首次适应算法(FF)循环首次适应算法(NF)最佳适应算法(BF)最坏适应算法(WF)源代码类代码Partiton...
  • 1)首次适应算法。每次分配时,总是顺序查找未分配表,找到第一个能满足长度要求的空闲区为止。分割这个找到的未分配区,一部分分配给作业,另一部分仍为空闲区。这种分配算法可能将大的空间分割成小区,造成较多的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,628
精华内容 2,251
关键字:

首次适应算法流程图