精华内容
下载资源
问答
  • 存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。页式管理中页面置换算法,了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换算法。 2、学年设计内容 (1)通过随机数...

    存储管理页面置换算法模拟实现及比较

    在这里插入图片描述

    1、目的

    存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。页式管理中页面置换算法,了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换算法。

    2、学年设计内容

    (1)通过随机数产生一个指令序列,共320条指令。
    指令的地址按下述原则生成:
    ①一半的指令是顺序执行的;
    ②四分之一的指令是均匀分布在前地址部分;
    ③四分之一的指令是均匀分布在前地址部分。
    具体的实施办法是:
    ① 在[0,319]之间选一起点m;
    ② 顺序执行一条指令,即m+1条;
    ③ 向前地址[0,m—1]中执行一条指令m’;
    ④ 顺序执行一条指令,即m’+1条;
    ⑤ 向后地址(m’+2,319]执行一条指令m’’
    ⑥ 重复上述步骤①-⑤,直到执行320次指令。
    (2)将指令序列变换成为页地址流。
    假设:① 页面大小为1KB;
    ② 用户实寸容量为4页到32页;
    ③ 用户虚存容量为32KB。用户虚存容量32KB,每1KB中放10条指令,共320条指令(0319)。其中09为0页,1019为1页…310319为31页。
    (3)使用不同的页面调度算法处理缺页中断,并计算不同实存容量下(4~32KB)的命中率。
    ① 先进先出算法(FIFO);
    ② 最近最少使用算法(LRU);
    ③ 最佳淘汰算法(OPT);先淘汰最不常用的页地址;
    ④ 最少访问页面算法(LFU)。
    命中率的算法为: 命中率=1-缺页中断次数/页地址流长度

    3、问题分析

    (1)通过随机数产生一个指令序列,共320条指令
    (2) 将指令序列变换成为页地址流
    (3) 命中率=1-页面失效次数/页地址流长度;
    (4) 理解各个页面调度算法

    4、设计思路

    根据对实验内容的理解,做一个整体框图,然后在一步一步地实现每个功能
    在这里插入图片描述
    由框图可知,主要实现4个算法,首先理解一下每个算法:

    (1) FIFO页面置换算法(先进先出算法):这个算法的基本思想是:总是先淘汰一些驻留在内存时间最长的页面,即先进入内存的页面先被置换掉。作业只要把进入内存的各个页面按进入的时间次序用链表链接起来,设定一个链表首指针指向进入内存最早的一个页面,新进入的页面放在链表的尾部,需要淘汰某一个页面时,总是淘汰替换指针所指向的页面即可。先进先出算法在程序按线性顺序访问逻辑地址空间时比较理想,否则效率不高。特别是在遇到循环执行的程序段时,往往会把频繁访问的页面,因其在内存驻留时间过长,而周期性地淘汰掉。
    在这里插入图片描述
    FIFO算法实现的逻辑框图:
    在这里插入图片描述

    (2) LRU算法(最近最久未使用算法):本算法的基本思想是:如果某一页被访问了,那么它很可能马上又被访问;反之,如果某一页很长时间没有被访问,那么最近也不太可能会被访问。这种算法考虑了程序设计的局部性原理。其实质是:当需要置换一页时,选择最近一段时间内最久未使用的页面予以淘汰。以一个例子来解说,比较好好理解:假定系统为某进程分配了3个物理块,进程运行时的页面走向为 7 0 1 2 0 3 0 4,开始时3个物理块均为空,那么LRU算法是如下工作的:
    在这里插入图片描述
    LRU算法实现的逻辑框图:
    在这里插入图片描述

    (3) OPT算法(最优算法):这是最理想的页面置换算法:从内存中移出以后不再使用的页面;如无这样的页面,则选择以后最长时间内不需要访问的页面。本算法因为页面访问的顺序是很难预知的,所以不是一种实际的方法。例如:假定系统为某进程分配了3个物理块,进程运行时的页面走向为 6,7,5,2,6,7,3,6,7,5,2,3,开始时3个物理块均为空,那么OPT算法是如下工作的:

    在这里插入图片描述
    OPT算法实现的逻辑框图:

    在这里插入图片描述
    (4) LFU算法(最少访问页面算法):本算法的原理是:要求在页面置换时置换引用计数最小的页面,因为经常使用的页应该有一个较大的引用次数。但是有些页在开始时使用次数很多,但以后就不再使用,这类页会长时间留在内存中,因此可以将引用计数寄存器定时右移一位,形成指数衰减的平均使用次数。此算法的特点是:因为在每一时间间隔内,只是用寄存器的一位来记录页的使用情况,因此,访问一次和访问10000次是等效的,次算法不能真正反映出页面的使用情况。

    在这里插入图片描述
    LFU算法实现的逻辑框图

    在这里插入图片描述

    5、实现核心代码分析

    (1)通过随机数产生一个指令序列,共320条指令。
    在python中的random.randint(a,b)用于生成一个指定范围内的整数。其中参数a是下限,参数b是上限,生成的随机数n: a <= n <= b。根据实验内容来产生320个随机指令
    ① 在[0,319]之间选一起点m;
    ② 顺序执行一条指令,即m+1条;
    ③ 向前地址[0,m—1]中执行一条指令m’;
    ④ 顺序执行一条指令,即m’+1条;
    ⑤ 向后地址(m’+2,319]执行一条指令m’'⑥ 重复上述步骤①-⑤,直到执行320次指令。

    def createRandomNum():
        i = 0
        while i < 320:
            m = random.randint(0, 319)      # 在[0,319]之间选一起点m;
            num[i] = m + 1                  # 顺序执行一条指令,即m+1条
            m1 = random.randint(0, m-1)
            i += 1
            num[i] = m1                     # 在[0,m-1]之间执行了一条指令
            i += 1
            num[i] = m1 + 1                 # 顺序执行了一条指令
            if m1 < 317:
                m2 = random.randint(m1 + 2, 319)
                i += 1
                num[i] = m2                # 在[m1+2,319]之间执行了一条指令
    
        print('**********生成320个随机数**********')
        str = ''
        for index, i in enumerate(num):
            if index < 320:
                str += '{}\t'.format(i)
                if (index + 1) % 20 == 0:
                    str += '\n'
        print(str)

    (2)将指令序列变换成为页地址流用户虚存容量32KB,每1KB中放10条指令,共320条指令(0~319)。
    其中0到9为0页,10到19为1页…310~319为31页。这个地方开始理解有点错误,开始以为第0个指令到第9个指令算一页,但是这样导致之后页面调度算法太过于复杂难实现。所以再次理解题目的意思之后就由此将指令序列变换成为页地址流。

    #将指令序列变换成为页地址流
    def changeAsPage():
        for index, i in enumerate(num):
            if index < 320:
                page[index] = int(i / 10)
        print('**********转化为320个页码数**********')
        str = ''
        for index, i in enumerate(page):
            str += '{}\t'.format(i)
            if (index + 1) % 20 == 0:
                str += '\n'
        print(str)

    (3)不同的页面调度算法处理缺页中断
    A. 先进先出算法(FIFO)
    1.根据先进先出算法的理解,这种算法类似于队列,先进先出,像是在排队一样。所以根据这个特点,能够很快地想出如何实现。
    2.接下来就考虑3种情况下,分别应该实施什么操作。
    3.首先,当队列里的数小于msize(页帧)时,应该将数都加进队列中,此时缺页次数需加1,其次如果需加入的数在队列的存在时,只需移除它,并再将该数插入队列,来更新一下位置,此时是没有产生缺页的,最后就是队列的长度等于msize(页帧),并且插入的数不在队列中的时候,这时候就考虑淘汰最先进入队列的数,此时只需要使用列表的内置函数pop()就可以完成操作,然后插入即可,同时缺页数加1。

    #先进先出算法(FIFO)
    def FIFO(msize):
        Q=[]            #定义队列
        diseffect=0     #缺页次数
        for item in page:
            if item in Q:
                Q.remove(item)
                Q.append(item)
            elif len(Q)<msize:
                Q.insert(0,item)
                diseffect+=1
            else:
                Q.pop()
                Q.insert(0,item)
                diseffect += 1
        return 1-diseffect/len(page)

    B. 最近最少使用算法(LRU)
    1.根据最久未使用算法的理解,这种算法类似于堆栈,插入数据就往列表里加入,需淘汰时,淘汰列表里第一位数即可。
    2.依旧考虑3种情况下,分别应该实施什么操作。
    3.首先,当队列里的数小于msize(页帧)时,应该将数都加进队列中,此时缺页次数需加1,其次如果需加入的数在队列的存在时,只需移除它,并再将该数插入队列,来更新一下位置,此时是没有产生缺页的,最后就是队列的长度等于msize(页帧),并且插入的数不在队列中的时候,根据插入以及算法的特点,这时候只需要淘汰列表里的第一个数,使用列表的内置函数pop(0)就可以完成操作,然后插入即可,同时缺页数加1。

    #最近最少使用算法(LRU)
    def LRU(msize):
        L=[]            #堆栈
        diseffect=0     #缺页次数
        for item in page:
            if item in L:
                L.remove(item)
                L.append(item)
            elif len(L)<msize:
                L.append(item)
                diseffect+=1
            else:
                L.pop(0)
                L.append(item)
                diseffect += 1
        return 1-diseffect/len(page)

    C. 最佳淘汰算法(OPT);
    1.先淘汰最不常用的页地址;根据对最佳淘汰算法的理解,这种算法还是比较难实现的,我们需要找到插入数据之后最后出现的数并且存在列表当中的数,然后淘汰掉该数,并插入需要插入的数。
    2.依旧考虑3种情况下,分别应该实施什么操作。
    3.首先,当队列里的数小于msize(页帧)时,应该将数都加进队列中,此时缺页次数需加1,其次如果需加入的数在队列的存在时,只需移除它,并再将该数插入队列,来更新一下位置,此时是没有产生缺页的,最后就是队列的长度等于msize(页帧),并且插入的数不在队列中的时候,这时我们需要用列表s来记录插入数据之后的各个页码数的坐标,再考虑哪个页码最不常用,即比较哪个坐标最大,然后再到列表L中去除页码流最大坐标对应的数,然后插入即可,同时缺页数加1。

    #最佳淘汰算法(OPT);先淘汰最不常用的页地址;
    def OPT(msize):
        L = []
        diseffect = 0
        for index, item in enumerate(page):
            if item in L:
                L.remove(item)
                L.append(item)
            elif len(L) < msize:
                L.append(item)
                diseffect += 1
            else:
                s=[]        #用于存储列表L的数在页面流之后页码出现的坐标
                page1 = page[index + 1:]
                flag=False  #用于做之后进入哪个条件的判断
                for index,i in enumerate(L):
                    if i not in page1:
                        flag=True
                        break
                    else:
                        a = page1.index(i)
                        s.append(a)
                if flag==True:
                    L.pop(index)
                else:
                    maxindex = max(s)
                    index1 = L.index(page1[maxindex])
                    L.pop(index1)
                L.append(item)
                diseffect += 1
        return 1 - diseffect / len(page)A. 
    

    D. 最少访问页面算法(LFU);
    1.根据对最少访问算法的理解,开始理解有点误区,当时看到一个解释是在一段时间内淘汰被访问次数最少的页码,但是正确的理解应该是淘汰历史访问的的次数最少的页码。
    2.依旧考虑3种情况下,分别应该实施什么操作。
    3.首先,当队列里的数小于msize(页帧)时,应该将数都加进队列中,此时缺页次数需加1,其次如果需加入的数在队列的存在时,只需移除它,并再将该数插入队列,来更新一下位置,此时是没有产生缺页的,最后就是队列的长度等于msize(页帧),并且插入的数不在队列中的时候,这时我们需要用列表s记录历史访问的各个页码的次数,并用局部变量mincount记录每次最小访问的数,之后在列表中找出第一个与该数出现次数相同的数,淘汰掉该数,并插入需要插入的数,同时缺页数加1。

    #最少访问页面算法(LFU),根据数据的历史访问频率来淘汰数据
    def LFU(msize):
        L = []  # 队列
        diseffect = 0  # 缺页次数
        for index,item in enumerate(page):
            if item in L:
                L.remove(item)
                L.append(item)
            elif len(L) < msize:
                L.append(item)
                diseffect += 1
            else:
                s=[]        #用于存储历史访问的页码次数
                page1=page[:index]
                for i in page1:
                    s.append(page1.count(i))
                mincount=min(s)
                for item1 in page1:
                   if L.count(item1) == mincount:
                       L.remove(item1)
                       L.append(item)
                       break
                diseffect += 1
        return 1 - diseffect / len(page)4

    6、程序运行截图

    产生的320个随机指令和其对应的页码数
    在这里插入图片描述
    各个算法在不同页帧下的命中率:

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    7、源代码

    import random
    
    num = [0 for i in range(0,325)]     # 生成随机数会有溢出,所以数组长度设置大一点
    page = [0 for i in range(0,320)]
    
    def createRandomNum():
        i = 0
        while i < 320:
            m = random.randint(0, 319)      # 在[0,319]之间选一起点m;
            num[i] = m + 1                  # 顺序执行一条指令,即m+1条
            m1 = random.randint(0, m-1)
            i += 1
            num[i] = m1                     # 在[0,m-1]之间执行了一条指令
            i += 1
            num[i] = m1 + 1                 # 顺序执行了一条指令
            if m1 < 317:
                m2 = random.randint(m1 + 2, 319)
                i += 1
                num[i] = m2                # 在[m1+2,319]之间执行了一条指令
    
        print('**********生成320个随机指令**********')
        str = ''
        for index, i in enumerate(num):
            if index < 320:
                str += '{}\t'.format(i)
                if (index + 1) % 20 == 0:
                    str += '\n'
        print(str)
    
    #将指令序列变换成为页地址流
    def changeAsPage():
        for index, i in enumerate(num):
            if index < 320:
                page[index] = int(i / 10)
        print('**********转化为320个页码数**********')
        str = ''
        for index, i in enumerate(page):
            str += '{}\t'.format(i)
            if (index + 1) % 20 == 0:
                str += '\n'
        print(str)
    
    
    #先进先出算法(FIFO)
    def FIFO(msize):
        Q=[]            #定义队列
        diseffect=0     #缺页次数
        for item in page:
            if item in Q:
                Q.remove(item)
                Q.append(item)
            elif len(Q)<msize:
                Q.insert(0,item)
                diseffect+=1
            else:
                Q.pop()
                Q.insert(0,item)
                diseffect += 1
        return 1-diseffect/len(page)
    
    
    #最近最少使用算法(LRU)
    def LRU(msize):
        L=[]            #堆栈
        diseffect=0     #缺页次数
        for item in page:
            if item in L:
                L.remove(item)
                L.append(item)
            elif len(L)<msize:
                L.append(item)
                diseffect+=1
            else:
                L.pop(0)
                L.append(item)
                diseffect += 1
        return 1-diseffect/len(page)
    
    
    #最佳淘汰算法(OPT);先淘汰最不常用的页地址;
    def OPT(msize):
        L = []
        diseffect = 0
        for index, item in enumerate(page):
            if item in L:
                L.remove(item)
                L.append(item)
            elif len(L) < msize:
                L.append(item)
                diseffect += 1
            else:
                s=[]        #用于存储列表L的数在页面流之后页码出现的坐标
                page1 = page[index + 1:]
                flag=False  #用于做之后进入哪个条件的判断
                for index,i in enumerate(L):
                    if i not in page1:
                        flag=True
                        break
                    else:
                        a = page1.index(i)
                        s.append(a)
                if flag==True:
                    L.pop(index)
                else:
                    maxindex = max(s)
                    index1 = L.index(page1[maxindex])
                    L.pop(index1)
                L.append(item)
                diseffect += 1
        return 1 - diseffect / len(page)
    
    
    #最少访问页面算法(LFU),根据数据的历史访问频率来淘汰数据
    def LFU(msize):
        L = []  # 队列
        diseffect = 0  # 缺页次数
        for index,item in enumerate(page):
            if item in L:
                L.remove(item)
                L.append(item)
            elif len(L) < msize:
                L.append(item)
                diseffect += 1
            else:
                s=[]        #用于存储历史访问的页码次数
                page1=page[:index]
                for i in page1:
                    s.append(page1.count(i))
                mincount=min(s)
                for item1 in page1:
                   if L.count(item1) == mincount:
                       L.remove(item1)
                       L.append(item)
                       break
                diseffect += 1
        return 1 - diseffect / len(page)
    
    
    createRandomNum()
    changeAsPage()
    i=4
    while i<33:
        print("--- {} page frames---".format(i))
        print("FIFO命中率为:{}".format(FIFO(i)))
        print("LRU命中率为:{}".format(LRU(i)))
        print("OPT命中率为:{}" .format(OPT(i)))
        print("LFU命中率为:{}" .format(LFU(i)))
        print()
        i+=1
    

    8、参考文献

    [1] 几种缺页中断算法(FIFO,LRU与LFU)的实现过程:http://blog.chinaunix.net/uid-13246637-id-5185352.html
    [2] FIFO、LRU、OPT页面调度算法及例子:https://blog.csdn.net/lingzhm/article/details/47417017?utm_medium=distribute.pc_relevant.none-task-blo g-BlogCommendFromMachineLearnPai2-1.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase
    [3] LRU算法原理解析 :https://www.cnblogs.com/linxiyue/p/10926944.html
    [4] 图解缓存淘汰算法三之FIFO:https://www.cnblogs.com/geyifan/p/3830429.html
    [5] Python列表(List):https://www.runoob.com/python/python-lists.html
    [6] 操作系统存储管理实验课程设计报告:https://blog.csdn.net/zzh_569754126/article/details/51492348
    [7] 操作系统 存储管理实验报告:https://blog.csdn.net/qq_43592352/article/details/106850352?utm_medium=distribute.pc_relevant.none-t ask-blog-baidujs-2

    展开全文
  • 通过本实验,帮助学生理解存储管理的功能,掌握动态异长分区的存储分配与回收算法。 【实验内容】 模拟动态异长分区的分配算法、回收算法。 【实验要求】 常用的动态异长分区的分配算法有:最先适应算法、最佳...

    设计一  内存空间的分配和回收

    【实验目的】

    通过本实验,帮助学生理解存储管理的功能,掌握动态异长分区的存储分配与回收算法。

    【实验内容】

    模拟动态异长分区的分配算法、回收算法。

    【实验要求】

    常用的动态异长分区的分配算法有:最先适应算法、最佳适应算法和最坏适应算法。要求选择任意一种算法,设计相应的数据结构,模拟内存空间的分配和回收。实验报告中给出程序中使用的数据结构及流程图。

    【实验原理】

    • 首次适应算法(First Fit)

           该算法从空闲分区链首开始查找,直至找到一个能满足其大小要求的空闲分区为止。然后再按照作业的大小,从该分区中划出一块内存分配给请求者,余下的空闲分区仍留在空闲分区链中。空闲分区以地址递增次序排列。    

    缺点:低地址部分不断被划分,留下许多难以利用、很小的空闲区,而每次查找又都从低地址部分开始,会增加查找的开销。

    优点:开销较小,回收分区一般无需对空闲分区队列重新排序。该算法倾向于使用内存中低地址部分的空闲区,在高地址部分的空闲区很少被利用,从而保留了高地址部分的大空闲区。显然为以后到达的大作业分配大的内存空间创造了条件。

    • 最佳适应算法(Best Fit)

            该算法总是把既能满足要求,又是最小的空闲分区分配给作业。为了加速查找,该算法要求将所有的空闲区按容量递增顺序排成一个空白链。这样每次找到的第一个满足要求的空闲区,必然是最优的。

    缺点:因为每次分配后剩余的空间一定是最小的,所以内存中留下许多难以利用的小的空闲区(外部碎片);开销大,回收后可能要重新排序。

    优点:每次分配给文件的都是最合适该文件大小的分区。有更多大分区被保留。     

    • 最坏适应算法(Worst Fit)

           空闲区按容量递减次序排列,每次优先分配最大连续空闲区。     

    缺点:较大空闲分区被迅速用完,绝大多数时候都会造成资源的严重浪费甚至是完全无法实现分配;开销大,回收后可能要重新排序。

    优点:尽可能地利用存储器中大的空闲区,减少了难以利用的小碎片。

    【数据结构设计】

    (1)数据结构设计

           为了实现存储资源的分配和回收,操作系统需要记录内存资源使用情况,即哪些区域尚未分配,哪些区域已经分配以及分配给哪些进程等。为此一般需要两个表,一个为分配表, 另外一个为空闲区域表。前者记录已经分配的区域, 后者记录着所有当前未被进程占用的空闲区域,如图1所示。

    空闲区域首址

    空闲区域长度

    addr

    size

                  图1 空闲区域表

           显然, 没有记录于表中的区域即为已被进程所占用的非空闲区域,在实际的操作系统中,这些区域登记在进程的PCB中。而PCB中除了关于内存资源的信息外,还有其它大量信息。

            由于本实验是对存储管理算法的模拟,所以用一个线程来代表一个进程,用线程驻留区域表来描述线程占用的内存空间,如图2所示。

    线程名称

    驻留区始址

    驻留区大小

    a

    0

    10

    b

    20

    20

    ……

    ……

    ……

                图2 线程驻留区表

            同时,需要一张表来记录各个线程对内存的请求信息,如图3所示。

    线程名称

    请求大小(KB)

    预计驻留时间( 秒)

    thread_1

    20

    4

    thread_2

    10

    5

    ……

    ……

    ……

                           图3 内存申请表

    (2)设计并分析测试数据

            假设初始内存布局如图4,图中的起始地址以及大小都以KB来衡量。

            由图4可见,初始时共有五个线程驻留在内存,它们是a,b,c,d,e,线程驻留区表如图5;还有五个空闲区,空闲区域表如图6。

            假设现在有三个线程提出内存申请,申请情况见图7。经过分析我们得到在每种分配算法下这三个线程所申请到的内存情况。图8是最先适应算法分配情况,图9是最佳适应算法分配情况,图10是最坏适应算法分配情况。

    【算法设计】

    宏定义:

    #define Free 0 //空闲状态

    #define Busy 1 //已用状态

    #define OK 1    //完成

    #define ERROR 0 //出错

    #define MAX_length 640  //定义最大主存信息640KB      

     

    六大函数:

    ①status Alloc(int):内存分配函数。对于选择的首次适应算法或者是最佳适应算法判断分配完成状态,说明是否实现分配或者是分配错误。

    ②status free(int):内存回收函数。主要涉及合并内存的三种情况:

    该空闲块与前面的空闲块相连的主存回收,表示为:

    if (p->prior != block_first && p->prior->data.state == Free)

    {

                 p->prior->data.size += p->data.size;//空间扩充,合并为一个

                 p->prior->next = p->next;//去掉原来被合并的p

                 p->next->prior = p->prior;

                 p = p->prior;

    }

    该空闲块与后面的空闲块相连,表示为:

    if (p->next != block_last && p->next->data.state == Free) {

             p->data.size += p->next->data.size;//空间扩充,合并为一个 p->next->next->prior = p;

             p->next = p->next->next;

    }

    该空闲块与最后的空闲块相连,表示为:

    if (p->next == block_last && p->next->data.state == Free) {

           p->data.size += p->next->data.size;

           p->next = NULL;

    }

    ③status First_fit(int):首次适应算法,只需要将地址由小到大排列好,从头指针开始遍历,逐个检验,找到第一个空间>=所申请的空间时,给予分配。 temp->prior = p->prior;

    temp->next = p;

    temp->data.address = p->data.address;

    p->prior->next = temp;

    p->prior = temp;

    p->data.address = temp->data.address + temp->data.size; p->data.size -= request;

    ④status Best_fit(int):对由小到大的空闲区排列的空闲区,与所申请的内存大小相比,取两者差最小的给予分配,插入。初始化最小空间和最佳位置,用ch来记录最小位置。

    ⑤void show():查看分配。

    ⑥status Initblock():开创带头结点的内存空间链表。

    【程序代码】

    #include<iostream>
    #include<stdlib.h>
    using namespace std;
    #define Free 0 //空闲状态
    #define Busy 1 //已用状态
    #define OK 1    //完成
    #define ERROR 0 //出错
    #define MAX_length 640  //定义最大主存信息640KB
    typedef int Status;
    int flag;//标志位  0为空闲区     1为已分配的工作区
    
    typedef struct FreAarea//定义一个空闲区说明表结构
    {
    	long size;   //分区大小
    	long address; //分区地址
    	int state;   //状态
    }ElemType;
    
    typedef struct DuLNode// 线性表的双向链表存储结构
    {
    	ElemType data;
    	struct DuLNode *prior; //前趋指针
    	struct DuLNode *next;  //后继指针
    }
    
    DuLNode, *DuLinkList;
    DuLinkList block_first; //头结点
    DuLinkList block_last;  //尾结点
    Status Alloc(int);//内存分配
    Status free(int); //内存回收
    Status First_fit(int);//首次适应算法
    Status Best_fit(int); //最佳适应算法
    Status Worst_fit(int); //最差适应算法
    void show();//查看分配
    Status Initblock();//开创空间表 
    
    Status Initblock()//开创带头结点的内存空间链表
    {
    	block_first = (DuLinkList)malloc(sizeof(DuLNode));
    	block_last = (DuLinkList)malloc(sizeof(DuLNode));
    	block_first->prior = NULL;
    	block_first->next = block_last;
    	block_last->prior = block_first;
    	block_last->next = NULL;
    	block_last->data.address = 0;
    	block_last->data.size = MAX_length;
    	block_last->data.state = Free;
    	return OK;
    }
    Status Alloc(int ch)//分配主存
    {
    	int request = 0;
    	cout << "请输入需要分配的主存大小(单位:KB):"<<endl;
    	cin >> request;
    	if (request<0 || request == 0)
    	{
    		cout << "分配大小不合适,请重试!" << endl;
    		return ERROR;
    	}
    
    	if (ch == 2) //选择最佳适应算法
    	{
    		if (Best_fit(request) == OK) cout << "分配成功!" << endl;
    		else cout << "内存不足,分配失败!" << endl;
    		return OK;
    	}
    	if (ch == 3) //选择最差适应算法
    	{
    		if (Worst_fit(request) == OK) cout << "分配成功!" << endl;
    		else cout << "内存不足,分配失败!" << endl;
    		return OK;
    	}
    	else //默认首次适应算法
    	{
    		if (First_fit(request) == OK) cout << "分配成功!" << endl;
    		else cout << "内存不足,分配失败!" << endl;
    		return OK;
    	}
    }
    Status First_fit(int request)//首次适应算法
    {
    	//为申请作业开辟新空间且初始化
    	DuLinkList temp = (DuLinkList)malloc(sizeof(DuLNode));
    	temp->data.size = request;
    	temp->data.state = Busy;
    
    	DuLNode *p = block_first->next;
    	while (p)
    	{
    		if (p->data.state == Free && p->data.size == request)
    		{//有大小恰好合适的空闲块
    			p->data.state = Busy;
    			return OK;
    			break;
    		}
    		if (p->data.state == Free && p->data.size>request)
    		{//有空闲块能满足需求且有剩余
    			temp->prior = p->prior;
    			temp->next = p;
    			temp->data.address = p->data.address;
    			p->prior->next = temp;
    			p->prior = temp;
    			p->data.address = temp->data.address + temp->data.size;
    			p->data.size -= request;
    			return OK;
    			break;
    		}
    		p = p->next;
    	}
    	return ERROR;
    }
    Status Best_fit(int request)//最佳适应算法
    {
    	int ch; //记录最小剩余空间
    	DuLinkList temp = (DuLinkList)malloc(sizeof(DuLNode));
    	temp->data.size = request;
    	temp->data.state = Busy;
    	DuLNode *p = block_first->next;
    	DuLNode *q = NULL; //记录最佳插入位置
    
    	while (p) //初始化最小空间和最佳位置
    	{
    		if (p->data.state == Free && (p->data.size >= request))
    		{
    			if (q == NULL)
    			{
    				q = p;
    				ch = p->data.size - request;
    			}
    			else if (q->data.size > p->data.size)
    			{
    				q = p;
    				ch = p->data.size - request;
    			}
    		}
    		p = p->next;
    	}
    	if (q == NULL) return ERROR;//没有找到空闲块
    	else if (q->data.size == request)
    	{
    		q->data.state = Busy;
    		return OK;
    	}
    	else
    	{
    		temp->prior = q->prior;
    		temp->next = q;
    		temp->data.address = q->data.address;
    		q->prior->next = temp;
    		q->prior = temp;
    		q->data.address += request;
    		q->data.size = ch;
    		return OK;
    	}
    	return OK;
    }
    Status Worst_fit(int request)//最差适应算法
    {
    	int ch; //记录最大剩余空间
    	DuLinkList temp = (DuLinkList)malloc(sizeof(DuLNode));
    	temp->data.size = request;
    	temp->data.state = Busy;
    	DuLNode *p = block_first->next;
    	DuLNode *q = NULL; //记录最佳插入位置
    
    	while (p) //初始化最大空间和最佳位置
    	{
    		if (p->data.state == Free && (p->data.size >= request))
    		{
    			if (q == NULL)
    			{
    				q = p;
    				ch = p->data.size - request;
    			}
    			else if (q->data.size < p->data.size)
    			{
    				q = p;
    				ch = p->data.size - request;
    			}
    		}
    		p = p->next;
    	}
    	if (q == NULL) return ERROR;//没有找到空闲块
    	else if (q->data.size == request)
    	{
    		q->data.state = Busy;
    		return OK;
    	}
    	else
    	{
    		temp->prior = q->prior;
    		temp->next = q;
    		temp->data.address = q->data.address;
    		q->prior->next = temp;
    		q->prior = temp;
    		q->data.address += request;
    		q->data.size = ch;
    		return OK;
    	}
    	return OK;
    }
    Status free(int flag)//主存回收
    {
    	DuLNode *p = block_first;
    	for (int i = 0; i <= flag; i++)
    		if (p != NULL)
    			p = p->next;
    		else
    			return ERROR;
    
    	p->data.state = Free;
    	if (p->prior != block_first && p->prior->data.state == Free)//与前面的空闲块相连
    	{
    		p->prior->data.size += p->data.size;//空间扩充,合并为一个
    		p->prior->next = p->next;//去掉原来被合并的p
    		p->next->prior = p->prior;
    		p = p->prior;
    	}
    	if (p->next != block_last && p->next->data.state == Free)//与后面的空闲块相连
    	{
    		p->data.size += p->next->data.size;//空间扩充,合并为一个
    		p->next->next->prior = p;
    		p->next = p->next->next;
    	}
    	if (p->next == block_last && p->next->data.state == Free)//与最后的空闲块相连
    	{
    		p->data.size += p->next->data.size;
    		p->next = NULL;
    	}
    
    	return OK;
    }
    void show()//显示主存分配情况
    {
    	int flag = 0;
    	cout << "\n主存分配情况:\n";
    	cout << "++++++++++++++++++++++++++++++++++++++++++++++\n\n";
    	DuLNode *p = block_first->next;
    	cout << "分区号\t起始地址\t分区大小\t状态\n\n";
    	while (p)
    	{
    		cout << "  " << flag++ << "\t";
    		cout << "  " << p->data.address << "\t\t";
    		cout << " " << p->data.size << "KB\t\t";
    		if (p->data.state == Free) cout << "空闲\n\n";
    		else cout << "已分配\n\n";
    		p = p->next;
    	}
    	cout << "++++++++++++++++++++++++++++++++++++++++++++++\n\n";
    }
    int main() //主函数
    {
    	int ch;//算法选择标记
    	cout << "请输入所使用的内存分配算法:\n";
    	cout << "(1)首次适应算法\n(2)最佳适应算法\n(3)最坏适应算法\n";
    
    	cin >> ch;
    	while (ch<1 || ch>3)
    	{
    		cout << "输入错误,请重新输入所使用的内存分配算法:\n";
    		cin >> ch;
    	}
    
    	Initblock(); //开创空间表
    	int choice;  //操作选择标记
    	while (1)
    	{
    		show();
    		cout << "请输入您的操作:";
    		cout << "\n1: 分配内存\n2: 回收内存\n0: 退出\n";
    
    		cin >> choice;
    		if (choice == 1) Alloc(ch); // 分配内存
    		else if (choice == 2)  // 内存回收
    		{
    			int flag;
    			cout << "请输入您要释放的分区号:"<<endl;
    			cin >> flag;
    			free(flag);
    		}
    		else if (choice == 0) break; //退出
    		else //输入操作有误
    		{
    			cout << "输入有误,请重试!" << endl;
    			continue;
    		}
    	}
    }

     【实验结果】

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

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

    首次适应:

    最佳适应:

    最坏适应:

    【实验心得】

           我在编写主存空间的分配和回收的过程中总结,从解决实际问题的角度,我们可以这样来看:首先要了解这个问题的基本要求,即输入、输出、完成从输入到输出的要求是什么;其次,从问题的要害入手,从前到后解决问题的每个方面,即从输入开始入手,着重考虑如何从输入导出输出。在这个过程中,可确定所需的变量、数组、函数,然后确定处理的过程算法。可得出最后的结论,进而完成程序的编写。经过这次实验,我对主存空间的分配和回收有了深一步的了解,同时也初步了解了内存空间的工作原理。总的来说这个实验既具有挑战性又极具趣味性


    以下是老师给的代码:

    【程序结构】

           程序包含两个文件,一个是头文件variable_partition.h,另一个是源程序文件variable_partition.cpp。在头文件中定义了宏、数据结构、全局变量、函数声明,源程序中含有各个函数的实现。

           在头文件中,结构体FREEAREA、REQUIRE_MEMORY、THREAD_RESIDENCE_MEMORY分别对应于图1、图2、图3中的一行,不同之处是为了构成链表在三个结构体中都有前向指针。数组init_free_area_table对应于图6,数组init_thread_require_memory_table对应于图5,数组init_thread_residence_memory_table对应于图7,为了实现动态分配与释放,用链表重新组织空闲区域表、线程驻留区表和内存申请表,全局变量p_free_area_list是空闲区链首,p_thread_require_memory_queue是内存申请队列的队首,p_thread_residence_memory_list是线程驻留区链首,tail_thread_residence_memory_list是线程驻留区链尾,由于线程驻留区链表被内存分配函数和内存释放函数共享,故用临界区变量CS_THREAD_MEMORY_LIST来保护,同理,屏幕是所有线程共享的,所以用临界区变量CS_SCREEN来保护,空闲区链表被内存分配函数和内存释放函数共享,故用临界区变量CS_FREEAREA_LIST来保护。h_thread是线程句柄数组,用来存放各个线程的句柄。

             程序共包含25个函数,按照作用可以将它们分成五组。

             第一组是主函数main(),其作用是显示主菜单并根据用户的选择执行相应功能;

             第二组包括函数print_space()和函数display_thread_residence_memory(),前者用来显示若干个空格,后者用来显示线程驻留区表;

             第三组共十个函数,用来实现最先适应分配法,它们的名称及功能如图11。

            第四组共六个函数,用来实现最佳适应分配法,它们的名称及功能如图12。

             第五组共六个函数,用来实现最坏适应分配法,它们的名称及功能如图13。

    【在Windows下运行的程序代码】

    头文件 variable_partition.h 的清单

    #include <windows.h>
    #include <conio.h>
    #include <stdlib.h>
    #include <stdio.h>
    #include <io.h>
    #include <string.h>
    
    #define MAX_THREAD 3
    #define BF_initialize_require_memory_list FF_initialize_require_memory_list
    #define WF_initialize_require_memory_list FF_initialize_require_memory_list
    #define BF_initialize_thread_residence_memory_list FF_initialize_thread_residence_memory_list
    #define WF_initialize_thread_residence_memory_list FF_initialize_thread_residence_memory_list
    #define WF_delete_freearea_list FF_delete_freearea_list
    #define BF_delete_freearea_list FF_delete_freearea_list
    #define WF_delete_require_memory_list FF_delete_require_memory_list
    #define BF_delete_require_memory_list FF_delete_require_memory_list
    #define WF_delete_thread_residence_memory_list FF_delete_thread_residence_memory_list
    #define BF_delete_thread_residence_memory_list FF_delete_thread_residence_memory_list
    
    typedef struct freearea{                    //表示空闲区域的数据结构
    	struct freearea *next;                  //指向下一个结点的指针
    	int start_address;                     //空闲区起始地址
    	int size;                              //空闲区大小
    }FREEAREA;
    
    typedef struct require_memory{             //记录线程申请内存的数据结构
        struct require_memory *next;           //指向下一个结点的指针
    	char thread_name[10];                //线程名
    	int size;                             //申请内存大小(以KB为单位)
    	int duration;                         //在内存的驻留时间(以秒为单位)
    }REQUIRE_MEMORY;
    
    typedef struct thread_residence_memory{         //描述线程驻留区的数据结构
        struct thread_residence_memory *next;       //指向下一个结点的指针
    	char thread_name[10];                     //线程名
    	int start_address;                          //驻留区起始地址
    	int size;                                   //驻留区大小
    }THREAD_RESIDENCE_MEMORY;
    
    FREEAREA init_free_area_table[5]={             //测试数据:初始空闲区表
    	{NULL,10,10},
    	{NULL,40,30},
    	{NULL,80,5},
    	{NULL,145,15},
    	{NULL,180,20}
    };
    
    REQUIRE_MEMORY init_thread_require_memory_table[3]={       //测试数据:初始内存申请表
    	{NULL,"thread_1",20,4},
    	{NULL,"thread_2",10,5},
    	{NULL,"thread_3",5,6}
    };
    //测试数据:初始线程驻留区表
    THREAD_RESIDENCE_MEMORY init_thread_residence_memory_table[5]={
    	{NULL,"a",0,10},
    	{NULL,"b",20,20},
    	{NULL,"c",70,10},
    	{NULL,"d",85,60},
    	{NULL,"e",160,20}
    };
    
    FREEAREA *p_free_area_list=NULL;                                              //空闲区链首
    REQUIRE_MEMORY *p_thread_require_memory_queue=NULL;                //内存申请队列队首
    THREAD_RESIDENCE_MEMORY *p_thread_residence_memory_list=NULL;      //线程驻留区链首
    THREAD_RESIDENCE_MEMORY *tail_thread_residence_memory_list=NULL;     //线程驻留区链尾
    CRITICAL_SECTION CS_THREAD_MEMORY_LIST;                //保护线程驻留区链表的临界区
    CRITICAL_SECTION CS_SCREEN;                                         //保护屏幕的临界区
    CRITICAL_SECTION CS_FREEAREA_LIST;                           //保护空闲区链表的临界区
    HANDLE h_thread[MAX_THREAD];                                              //线程句柄数组
    
    void print_space(int num);                                                     //输出若干个空格
    void display_thread_residence_memory_list();                                 //显示线程驻留区表
    //最先适应分配法的函数
    FREEAREA *FF_initialize_freearea_list(FREEAREA *init_table,int num);          //初始化空闲区链表
    void FF_delete_freearea_list();                                                //删除空闲区链表
    REQUIRE_MEMORY *FF_initialize_require_memory_list(REQUIRE_MEMORY *init_table,int num);
    //初始化内存申请链表
    void FF_delete_require_memory_list();                                       //删除内存申请链表
    THREAD_RESIDENCE_MEMORY  *FF_initialize_thread_residence_memory_list
    (THREAD_RESIDENCE_MEMORY *init_table,int num);                   //初始化线程驻留区链表
    void FF_delete_thread_residence_memory_list();                            //删除线程驻留区链表
    void FF_thread(void *data);                                                          //线程函数
    int FF_require_memory(int size);                                                  //内存申请函数
    void FF_release_memory(int start_address,int size);                                 //内存释放函数
    void FF();                                                      //最先适应分配算法的初始化函数
    
    //最佳适应分配算法的函数
    void BF_thread(void *data);                                                         //线程函数
    int BF_require_memory(int size);                                                 //内存申请函数
    void BF_release_memory(int start_address,int size);                                //内存释放函数
    void BF_insert_freearea(FREEAREA *free_node);                            //空闲区结点插入函数
    void BF();                                                                       //初始化程序
    void BF_initialize_freearea_list(FREEAREA *init_table,int num);                  //初始化空闲区链表
    
    //最坏适应分配算法的函数
    void WF_thread(void *data);                                                        //线程函数
    void WF_insert_freearea(FREEAREA *free_node);                          //空闲区结点插入函数
    void WF_initialize_freearea_list(FREEAREA *init_table,int num);                //初始化空闲区链表
    int WF_require_memory(int size);                                               //内存申请函数
    void WF_release_memory(int start_address,int size);                              //内存释放函数
    void WF();                                                                      //初始化程序

    源程序文件 variable_partition.cpp 的清单

    #include "variable_partition.h"
    int main(int argc,char *argv[]){
    	char select;
    	while(1){
    		printf("|-----------------------------------|\n");
    		printf("|  1:first fit allocation     |\n");
    		printf("|  2:best fit allocation     |\n");
    		printf("|  3:worst fit allocation    |\n");
    		printf("|  4:exit                 |\n");
    		printf("|-----------------------------------|\n");
    		printf("select a function(1~4):");
    		do{
    			select=(char)getch();
    		}while(select!='1'&&select!='2'&&select!='3'&&select!='4');
    		system("cls");
    		switch(select){
    		case '1':
    			FF();
    			break;
    		case '2':
    			BF();
    			break;
    		case '3':
    			WF();
    			break;
    		case '4':
    			return 0;
    		}
    		printf("\nPress any key to return to main menu.");
    		getch();
    		system("cls");
    	}
    	return 0;
    }
    
    
    void print_space(int num){                           //显示若干个空格
    	int i;
    	for(i=0;i<num;i++){
    		printf(" ");
    	}
    }
    
    void display_thread_residence_memory_list(){          //显示驻留线程链表
    	THREAD_RESIDENCE_MEMORY *p;
    	char buffer[20];
       	p=p_thread_residence_memory_list;
    	printf("|-------------------|--------------------|------------------|\n");
    	printf("| thread_name | start_address(kB) | size(KB) |\n");
    	printf("|-------------------|--------------------|------------------|\n");
    	while(p!=NULL){
           printf("| %s",p->thread_name);
    	   print_space(18-strlen(p->thread_name));
    	   printf("| %d",p->start_address);
    	   itoa( p->start_address, buffer, 10 );
       	   print_space(19-strlen(buffer));
    	   printf("| %d",p->size);
           itoa(p->size, buffer, 10 );
       	   print_space(17-strlen(buffer));
           printf("|\n");
    	   p=p->next;
    	};
        printf("|-------------------|--------------------|------------------|\n\n");
    }
    
    //最先适应分配法:初始化空闲区链表
    FREEAREA *FF_initialize_freearea_list(FREEAREA *init_table,int num){
      FREEAREA *temp;
      FREEAREA *head=NULL;
      FREEAREA *tail=NULL;
      int i;
      for(i=0;i<num;i++){
         temp=(FREEAREA *)malloc(sizeof(FREEAREA));
         temp->start_address=init_table[i].start_address;
    	 temp->size=init_table[i].size;
    	 temp->next=NULL;
    	 if(head==NULL)
    		 head=tail=temp;
    	 else{
    		 tail->next=temp;
    		 tail=tail->next;
    	 }
      };
      return head;
    }
    
    //最先适应分配法:删除空闲区链表
    void FF_delete_freearea_list(){
    	FREEAREA *temp;
    	temp=p_free_area_list;
    	while(temp!=NULL){
    		temp=p_free_area_list->next;
    		free(p_free_area_list);
    		p_free_area_list=temp;
    	}
    	p_free_area_list=NULL;
    }
    
    
    //最先适应分配法:初始化内存申请链表
    REQUIRE_MEMORY *FF_initialize_require_memory_list(REQUIRE_MEMORY *init_table,int num){
      REQUIRE_MEMORY *temp;
      REQUIRE_MEMORY *head=NULL;
      REQUIRE_MEMORY *tail=NULL;
      int i;
      for(i=0;i<num;i++){
         temp=(REQUIRE_MEMORY *)malloc(sizeof(REQUIRE_MEMORY));
         strcpy(temp->thread_name,init_table[i].thread_name);
    	 temp->size=init_table[i].size;
    	 temp->duration=init_table[i].duration;
    	 temp->next=NULL;
    	 if(head==NULL)
    		 head=tail=temp;
    	 else{
    		 tail->next=temp;
    		 tail=tail->next;
    	 }
      };
      return head;
    }
    
    //最先适应分配法:删除内存申请链表
    void FF_delete_require_memory_list(){
    	REQUIRE_MEMORY *temp;
    	temp=p_thread_require_memory_queue;
    	while(temp!=NULL){
    		temp=p_thread_require_memory_queue->next;
    		free(p_thread_require_memory_queue);
    		p_thread_require_memory_queue=temp;
    	}
    	p_thread_require_memory_queue=NULL;
    }
    
    //最先适应分配法:初始化线程驻留区链表
    THREAD_RESIDENCE_MEMORY *FF_initialize_thread_residence_memory_list(THREAD_RESIDENCE_MEMORY *init_table,int num){
      THREAD_RESIDENCE_MEMORY *temp;
      THREAD_RESIDENCE_MEMORY *head=NULL;
      THREAD_RESIDENCE_MEMORY *tail=NULL;
      int i;
      for(i=0;i<num;i++){
         temp=(THREAD_RESIDENCE_MEMORY *)malloc(sizeof(THREAD_RESIDENCE_MEMORY));
         strcpy(temp->thread_name,init_table[i].thread_name);
    	 temp->start_address=init_table[i].start_address;
    	 temp->size=init_table[i].size;
    	 temp->next=NULL;
    	 if(head==NULL)
    		 head=tail=temp;
    	 else{
    		 tail->next=temp;
    		 tail=tail->next;
    	 }
      };
      tail_thread_residence_memory_list=tail;
      return head;
    }
    
    //最先适应分配法:删除线程驻留区链表
    void FF_delete_thread_residence_memory_list(){
    	THREAD_RESIDENCE_MEMORY *temp=p_thread_residence_memory_list;
    	
    	temp=p_thread_residence_memory_list;
    	while(temp!=NULL){
    		temp=p_thread_residence_memory_list->next;
    		free(p_thread_residence_memory_list);
    		p_thread_residence_memory_list=temp;
    	}
    	p_thread_residence_memory_list=NULL;
    }
    
    //线程:申请内存,驻留一段时间,释放内存
    void FF_thread(void *data){
        int start_address=-1;
    	THREAD_RESIDENCE_MEMORY *temp;
    	EnterCriticalSection(&CS_SCREEN);
    	printf("create thread:%s\n",((REQUIRE_MEMORY *)(data))->thread_name);
    	LeaveCriticalSection(&CS_SCREEN);
        
    	
        while(1){                                                        //申请内存
    		start_address=FF_require_memory(((REQUIRE_MEMORY *)(data))->size);
    		if(start_address>=0)
    			break;
    		else
    			Sleep(1000);
    	}
    	temp=(THREAD_RESIDENCE_MEMORY *)malloc(sizeof(THREAD_RESIDENCE_MEMORY));
        strcpy(temp->thread_name,((REQUIRE_MEMORY *)(data))->thread_name);
    	temp->start_address=start_address;
    	temp->size=((REQUIRE_MEMORY *)(data))->size;
    	temp->next=NULL;
    	EnterCriticalSection(&CS_THREAD_MEMORY_LIST);
    	                                                       //加入线程驻留区链表
    	tail_thread_residence_memory_list->next=temp;
    	tail_thread_residence_memory_list=tail_thread_residence_memory_list->next;
        LeaveCriticalSection(&CS_THREAD_MEMORY_LIST);
    	                                                       //显示线程驻留区链表
    	EnterCriticalSection(&CS_SCREEN);
    	printf("after %s %s\n",((REQUIRE_MEMORY *)(data))->thread_name,"get memory:");
    	display_thread_residence_memory_list();
    	LeaveCriticalSection(&CS_SCREEN);
    	
    	Sleep(((REQUIRE_MEMORY *)(data))->duration);
    	                                                       //释放内存
    	FF_release_memory(start_address,((REQUIRE_MEMORY *)(data))->size);
    }
    
    
    //最先适应分配法:内存申请函数
    int FF_require_memory(int size){
    	int start_address=-1;
    	FREEAREA *p;
    	FREEAREA *p_next;
    	EnterCriticalSection(&CS_FREEAREA_LIST);
    	p=p_next=p_free_area_list;
    	while(p_next!=NULL){
    		if(size==p_next->size){                     //刚好满足要求,删除空闲区结点
    			start_address=p_next->start_address;
    			if(p_next==p_free_area_list)
    				p_free_area_list=p_next->next;
    			else
    			    p->next=p_next->next;
    			free(p_next);
    			break;
    		}
    		else
    			if(size<p_next->size){                      //分割空闲区结点
    				start_address=p_next->start_address;
    				p_next->start_address+=size;
    				p_next->size-=size;
    				break;
    			}
    			else
    			{
    				p=p_next;
    				p_next=p_next->next;
    			}
    	}
       	LeaveCriticalSection(&CS_FREEAREA_LIST);
    	return start_address;
    }
    
    //最先适应分配法:内存释放函数
    void FF_release_memory(int start_address,int size){
    	EnterCriticalSection(&CS_FREEAREA_LIST);
    	//请读者自己实现这段代码
    	LeaveCriticalSection(&CS_FREEAREA_LIST);
    }
    
    //最先适应分配算法的初始化程序
    void FF(){
    	int i=0;
        REQUIRE_MEMORY *p;
       	HANDLE h_thread[MAX_THREAD];
    	InitializeCriticalSection(&CS_THREAD_MEMORY_LIST);
         InitializeCriticalSection(&CS_FREEAREA_LIST);
    	InitializeCriticalSection(&CS_SCREEN);
    	printf("最先适应分配算法\n");
        p_free_area_list=FF_initialize_freearea_list(init_free_area_table,5);
    p_thread_require_memory_queue=FF_initialize_require_memory_list(init_thread_require_memory_table,3);
    p_thread_residence_memory_list=FF_initialize_thread_residence_memory_list(init_thread_residence_memory_table,5);
        p=p_thread_require_memory_queue;
        while(p!=NULL){
          h_thread[i]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(FF_thread),p,0,NULL);
          i++;
    	 p=p->next;
        };
       WaitForMultipleObjects(MAX_THREAD,h_thread,TRUE,-1);              //等待所有线程结束
    
    	EnterCriticalSection(&CS_SCREEN);
    	printf("after all threads have finished:\n");
    	display_thread_residence_memory_list();                    //显示驻留线程链表
    	LeaveCriticalSection(&CS_SCREEN);
    	                                                         //删除各种链表
    	FF_delete_freearea_list();
    	FF_delete_require_memory_list();
    	FF_delete_thread_residence_memory_list();
    	getch();
        printf("\n");
    }
    
    //最佳适应分配算法的线程:申请内存,驻留一段时间,释放内存
    void BF_thread(void *data){
        int start_address=-1;
    	THREAD_RESIDENCE_MEMORY *temp;
    	EnterCriticalSection(&CS_SCREEN);
    	printf("create thread:%s\n",((REQUIRE_MEMORY *)(data))->thread_name);
    	LeaveCriticalSection(&CS_SCREEN);
        
    	//申请内存
        while(1){
    		start_address=BF_require_memory(((REQUIRE_MEMORY *)(data))->size);
    		if(start_address>=0)
    			break;
    		else
    			Sleep(1000);
    	}
    	temp=(THREAD_RESIDENCE_MEMORY *)malloc(sizeof(THREAD_RESIDENCE_MEMORY));
        strcpy(temp->thread_name,((REQUIRE_MEMORY *)(data))->thread_name);
    	temp->start_address=start_address;
    	temp->size=((REQUIRE_MEMORY *)(data))->size;
    	temp->next=NULL;
    	EnterCriticalSection(&CS_THREAD_MEMORY_LIST);
    	//加入线程内存驻留区链表
    	tail_thread_residence_memory_list->next=temp;
    	tail_thread_residence_memory_list=tail_thread_residence_memory_list->next;
        LeaveCriticalSection(&CS_THREAD_MEMORY_LIST);
    	//显示线程内存驻留区链表
    	EnterCriticalSection(&CS_SCREEN);
    	printf("after %s %s\n",((REQUIRE_MEMORY *)(data))->thread_name,"get memory:");
    	display_thread_residence_memory_list();
    	LeaveCriticalSection(&CS_SCREEN);
    	
    	Sleep(((REQUIRE_MEMORY *)(data))->duration);
    	//释放内存
    	BF_release_memory(start_address,((REQUIRE_MEMORY *)(data))->size);
    }
    
    //最佳适应分配算法的内存申请函数
    int BF_require_memory(int size){
      	int start_address=-1;
    	FREEAREA *p;
    	FREEAREA *p_next;
    	EnterCriticalSection(&CS_FREEAREA_LIST);
    	p=p_next=p_free_area_list;
    	while(p_next!=NULL){
    		if(size==p_next->size){//刚好满足要求,删除空闲区结点
    			start_address=p_next->start_address;
    			if(p_next==p_free_area_list)
    				p_free_area_list=p_next->next;
    			else
    			    p->next=p_next->next;
    			free(p_next);
    			break;
    		}
    		else
    			if(size<p_next->size){//分割空闲区结点
    				start_address=p_next->start_address;
    				p_next->start_address+=size;
    				p_next->size-=size;
    				p->next=p_next->next;
    				BF_insert_freearea(p_next);
    				break;
    			}
    			else
    			{
    				p=p_next;
    				p_next=p_next->next;
    			}
    	}
       	LeaveCriticalSection(&CS_FREEAREA_LIST);
    	return start_address;
    
    }
    
    //最佳适应分配算法的内存释放函数
    void BF_release_memory(int start_address,int size){
      //请读者自己实现这段代码
    }
    
    //最佳分配算法的空闲区结点插入函数
    void BF_insert_freearea(FREEAREA *free_node){
         FREEAREA *p;
         FREEAREA *p_next;
    	 
    	 if(p_free_area_list==NULL)
    		 p_free_area_list=free_node;
    	 else{
    	   p_next=p=p_free_area_list;
    	   while(p_next!=NULL&&p_next->size<free_node->size){
    		 p=p_next;
    		 p_next=p_next->next;
    	   }
    	   if(p_next==NULL)               //应插入到尾部
    		 p->next=free_node;
    	   else
    		 if(p==p_next){                //应插入到头部
    		    free_node->next=p;
    		    p_free_area_list=free_node;
    		 }
    		 else{                        //应插入到p与p_next之间
    			 free_node->next=p_next;
    			 p->next=free_node;
    		 }
    	 }
    }
    
    //最佳适应分配法:初始化空闲区链表
    void BF_initialize_freearea_list(FREEAREA *init_table,int num){
      FREEAREA *temp;
      int i;
      for(i=0;i<num;i++){
         temp=(FREEAREA *)malloc(sizeof(FREEAREA));
         temp->start_address=init_table[i].start_address;
    	 temp->size=init_table[i].size;
    	 temp->next=NULL;
    	 BF_insert_freearea(temp);
      }
    }
    
    //最佳分配算法的初始化程序
    void BF(){
      	int i=0;
        REQUIRE_MEMORY *p;
       	HANDLE h_thread[MAX_THREAD];
    	InitializeCriticalSection(&CS_THREAD_MEMORY_LIST);
        InitializeCriticalSection(&CS_FREEAREA_LIST);
    	InitializeCriticalSection(&CS_SCREEN);
    	printf("最佳适应分配算法\n");
        BF_initialize_freearea_list(init_free_area_table,5);
    p_thread_require_memory_queue=BF_initialize_require_memory_list(init_thread_require_memory_table,3);
    p_thread_residence_memory_list=BF_initialize_thread_residence_memory_list(init_thread_residence_memory_table,5);
        p=p_thread_require_memory_queue;
        while(p!=NULL){
          h_thread[i]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(BF_thread),p,0,NULL);
          i++;
    	  p=p->next;
        };
        //等待所有线程结束
        WaitForMultipleObjects(MAX_THREAD,h_thread,TRUE,-1);
    
    	//显示驻留线程链表
    	EnterCriticalSection(&CS_SCREEN);
    	printf("after all threads have finished:\n");
    	display_thread_residence_memory_list();
    	LeaveCriticalSection(&CS_SCREEN);
    
    	//删除各种链表
    	FF_delete_freearea_list();
    	FF_delete_require_memory_list();
    	FF_delete_thread_residence_memory_list();
    
    	getch();
        printf("\n");
    }
    
    
    //最坏适应分配算法的线程:申请内存,驻留一段时间,释放内存
    void WF_thread(void *data){
        int start_address=-1;
    	THREAD_RESIDENCE_MEMORY *temp;
    	EnterCriticalSection(&CS_SCREEN);
    	printf("create thread:%s\n",((REQUIRE_MEMORY *)(data))->thread_name);
    	LeaveCriticalSection(&CS_SCREEN);
        
    	//申请内存
        while(1){
    		start_address=WF_require_memory(((REQUIRE_MEMORY *)(data))->size);
    		if(start_address>=0)
    			break;
    		else
    			Sleep(1000);
    	}
    	temp=(THREAD_RESIDENCE_MEMORY *)malloc(sizeof(THREAD_RESIDENCE_MEMORY));
        strcpy(temp->thread_name,((REQUIRE_MEMORY *)(data))->thread_name);
    	temp->start_address=start_address;
    	temp->size=((REQUIRE_MEMORY *)(data))->size;
    	temp->next=NULL;
    	EnterCriticalSection(&CS_THREAD_MEMORY_LIST);
    	//加入线程内存驻留区链表
    	tail_thread_residence_memory_list->next=temp;
    	tail_thread_residence_memory_list=tail_thread_residence_memory_list->next;
        LeaveCriticalSection(&CS_THREAD_MEMORY_LIST);
    	//显示线程内存驻留区链表
    	EnterCriticalSection(&CS_SCREEN);
    	printf("after %s %s\n",((REQUIRE_MEMORY *)(data))->thread_name,"get memory:");
    	display_thread_residence_memory_list();
    	LeaveCriticalSection(&CS_SCREEN);
    	
    	Sleep(((REQUIRE_MEMORY *)(data))->duration);
    	//释放内存
    	WF_release_memory(start_address,((REQUIRE_MEMORY *)(data))->size);
    }
    
    //最坏分配算法的空闲区结点插入函数
    void WF_insert_freearea(FREEAREA *free_node){
        FREEAREA *p;
        FREEAREA *p_next;
    	 
    	 if(p_free_area_list==NULL)
    		 p_free_area_list=free_node;
    	 else{
           p=p_next=p_free_area_list;
    	   while(p_next!=NULL&&free_node->size<p_next->size){
    		 p=p_next;
    		 p_next=p_next->next;
    	   }
    	   if(p_next==NULL)      //应插入到尾部
    		 p->next=free_node;
    	   else
    		 if(p==p_next){  //应插入到头部
    		    free_node->next=p;
    		    p_free_area_list=free_node;
    		 }
    		 else{           //应插入到p与p_next之间
    			 free_node->next=p_next;
    			 p->next=free_node;
    		 }
    	 }
    }
    
    //最坏适应分配法:初始化空闲区链表
    void WF_initialize_freearea_list(FREEAREA *init_table,int num){
      FREEAREA *temp;
      int i;
      for(i=0;i<num;i++){
         temp=(FREEAREA *)malloc(sizeof(FREEAREA));
         temp->start_address=init_table[i].start_address;
    	 temp->size=init_table[i].size;
    	 temp->next=NULL;
    	 WF_insert_freearea(temp);
      }
    }
    
    //最坏适应分配算法的内存申请函数
    int WF_require_memory(int size){
    	int start_address=-1;
    	FREEAREA *p_next;
    	EnterCriticalSection(&CS_FREEAREA_LIST);
    	p_next=p_free_area_list;
    	if(size==p_free_area_list->size){//刚好满足要求,删除空闲区结点
    		start_address=p_next->start_address;
    		p_free_area_list=p_free_area_list->next;
    		free(p_next);
    	}
    	else
    		if(size<p_next->size){//分割空闲区结点
    			start_address=p_next->start_address;
    			p_next->start_address+=size;
    			p_next->size-=size;
    		    p_free_area_list=p_free_area_list->next;
    			WF_insert_freearea(p_next);
    		}
    	LeaveCriticalSection(&CS_FREEAREA_LIST);
    	return start_address;
    
    }
    
    //最坏适应分配算法:内存释放函数
    void WF_release_memory(int start_address,int size){
      //请读者自己实现这段代码
    }
    
    
    //最坏适应分配算法的初始化程序
    void WF(){
      int i=0;
        REQUIRE_MEMORY *p;
       	HANDLE h_thread[MAX_THREAD];
    	InitializeCriticalSection(&CS_THREAD_MEMORY_LIST);
        InitializeCriticalSection(&CS_FREEAREA_LIST);
    	InitializeCriticalSection(&CS_SCREEN);
    	printf("最坏适应分配算法\n");
        WF_initialize_freearea_list(init_free_area_table,5);
    p_thread_require_memory_queue=WF_initialize_require_memory_list(init_thread_require_memory_table,3);
    p_thread_residence_memory_list=WF_initialize_thread_residence_memory_list(init_thread_residence_memory_table,5);
        p=p_thread_require_memory_queue;
        while(p!=NULL){
          h_thread[i]=CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)(WF_thread),p,0,NULL);
          i++;
    	  p=p->next;
        };
        //等待所有线程结束
        WaitForMultipleObjects(MAX_THREAD,h_thread,TRUE,-1);
    
    	//显示驻留线程链表
    	EnterCriticalSection(&CS_SCREEN);
    	printf("after all threads have finished:\n");
    	display_thread_residence_memory_list();
    	LeaveCriticalSection(&CS_SCREEN);
    
    	//删除各种链表
    	FF_delete_freearea_list();
    	FF_delete_require_memory_list();
    	FF_delete_thread_residence_memory_list();
    
    	getch();
        printf("\n");	
    }

    【在Linux下运行的代码】

    编译命令:gcc variable_partition .cpp –o variable_partition.o –lcurses –lpthread

    头文件variable_partition.h

    #include <unistd.h>
    #include <curses.h>
    #include <stdlib.h>
    #include <pthread.h>
    #include <time.h>
    #include <string.h>
    #include <semaphore.h>
    
    #define MAX_THREAD 3
    #define BF_initialize_require_memory_list FF_initialize_require_memory_list
    #define WF_initialize_require_memory_list FF_initialize_require_memory_list
    #define BF_initialize_thread_residence_memory_list 
    FF_initialize_thread_residence_memory_list
    #define WF_initialize_thread_residence_memory_list 
    FF_initialize_thread_residence_memory_list
    #define WF_delete_freearea_list FF_delete_freearea_list
    #define BF_delete_freearea_list FF_delete_freearea_list
    #define WF_delete_require_memory_list FF_delete_require_memory_list
    #define BF_delete_require_memory_list FF_delete_require_memory_list
    #define WF_delete_thread_residence_memory_list 
    FF_delete_thread_residence_memory_list
    #define BF_delete_thread_residence_memory_list 
    FF_delete_thread_residence_memory_list
    
    typedef struct freearea{
    	struct freearea *next;
    	int start_address;
    	int size;
    }FREEAREA;
    
    typedef struct require_memory{
        struct require_memory *next;
    	char thread_name[10];
    	int size;
    	int duration;
    }REQUIRE_MEMORY;
    
    typedef struct thread_residence_memory{
        struct thread_residence_memory *next;
    	char thread_name[10];
    	int start_address;
    	int size;
    }THREAD_RESIDENCE_MEMORY;
    
    FREEAREA init_free_area_table[5]={
    	{NULL,10,10},
    	{NULL,40,30},
    	{NULL,80,5},
    	{NULL,145,15},
    	{NULL,180,20}
    };
    
    REQUIRE_MEMORY init_thread_require_memory_table[3]={
    	{NULL,"thread_1",20,4},
    	{NULL,"thread_2",10,5},
    	{NULL,"thread_3",5,6}
    };
    
    THREAD_RESIDENCE_MEMORY init_thread_residence_memory_table[5]={
    	{NULL,"a",0,10},
    	{NULL,"b",20,20},
    	{NULL,"c",70,10},
    	{NULL,"d",85,60},
    	{NULL,"e",160,20}
    };
    
    FREEAREA *p_free_area_list=NULL;
    REQUIRE_MEMORY *p_thread_require_memory_queue=NULL;
    THREAD_RESIDENCE_MEMORY *p_thread_residence_memory_list=NULL;
    THREAD_RESIDENCE_MEMORY *tail_thread_residence_memory_list=NULL;
    pthread_mutex_t CS_THREAD_MEMORY_LIST;
    pthread_mutex_t CS_SCREEN;
    pthread_mutex_t CS_FREEAREA_LIST;
    pthread_t h_thread[MAX_THREAD];
    sem_t thread_end[MAX_THREAD];
    
    void display_thread_residence_memory_list();
    FREEAREA *FF_initialize_freearea_list(FREEAREA *init_table,int num);
    
    void FF_delete_freearea_list();
    REQUIRE_MEMORY *FF_initialize_require_memory_list(REQUIRE_MEMORY *init_table,
    int num);
    
    void FF_delete_require_memory_list();
    THREAD_RESIDENCE_MEMORY *FF_initialize_thread_residence_memory_list
    (
    THREAD_RESIDENCE_MEMORY *init_table,
    int num
    );
    void  FF_delete_thread_residence_memory_list();
    void* FF_thread(void *data);
    int   FF_require_memory(int size);
    void  FF_release_memory(int start_address,int size);
    void  FF();
    
    void* BF_thread(void *data);
    int   BF_require_memory(int size);
    void  BF_release_memory(int start_address,int size);
    void  BF_insert_freearea(FREEAREA *free_node);
    void  BF();
    void  BF_initialize_freearea_list(FREEAREA *init_table,int num);
    
    void* WF_thread(void *data);
    void  WF_insert_freearea(FREEAREA *free_node);
    void  WF_initialize_freearea_list(FREEAREA *init_table,int num);
    int   WF_require_memory(int size);
    void  WF_release_memory(int start_address,int size);
    void  WF();

    源文件variable_partition.cpp

    #include "variable_partition.h"
    int main(int argc,char *argv[]){
    	char select;
    	bool end=false;
    	initscr();
    	while(!end){
    		clear();
    		refresh();
    		printw("|-----------------------------------|\n");
    		printw("|  1:first fit allocation           |\n");
    		printw("|  2:best  fit allocation           |\n");
    		printw("|  3:worst fit allocation           |\n");
    		printw("|  4:exit                           |\n");
    		printw("|-----------------------------------|\n");
    		printw("select a function(1~4):");
    		do{
    			select=(char)getch();
    		}while(select!='1'&&select!='2'&&select!='3'&&select!='4');
    		clear();
    		refresh();
    		switch(select){
    		case '1':
    			FF();
    			break;
    		case '2':
    			BF();
    			break;
    		case '3':
    			WF();
    			break;
    		case '4':
    			end=true;
    		}
    		printw("\nPress any key to return to main menu.");
    		refresh();
    		getch();
    		
    	}
    	endwin();
    	return 0;
    }
    
    void display_thread_residence_memory_list(){
    	THREAD_RESIDENCE_MEMORY *p;
       	p=p_thread_residence_memory_list;
    	int i=13;
    	move(10,0);
    	printw("|-------------------|--------------------|------------------|\n");
    	printw("| thread_name       | start_address(kB)  | size(KB)         |\n");
    	printw("|-------------------|--------------------|------------------|\n");
    	while(p!=NULL){
    	   move(i,0);
           printw("| %s",p->thread_name);
    	   move(i,20);
    	   printw("| %d",p->start_address);
    	   move(i,41);
    	   printw("| %d",p->size);
           move(i,60);
           printw("|\n");
    	   p=p->next;
    	   i++;
    	};
    	move(i,0);
            printw("|-------------------|--------------------|------------------|\n\n");
    	refresh();
    }
    
    FREEAREA *FF_initialize_freearea_list(FREEAREA *init_table,int num){
      FREEAREA *temp;
      FREEAREA *head=NULL;
      FREEAREA *tail=NULL;
      int i;
      for(i=0;i<num;i++){
         temp=(FREEAREA *)malloc(sizeof(FREEAREA));
         temp->start_address=init_table[i].start_address;
    	 temp->size=init_table[i].size;
    	 temp->next=NULL;
    	 if(head==NULL)
    		 head=tail=temp;
    	 else{
    		 tail->next=temp;
    		 tail=tail->next;
    	 }
      };
      return head;
    }
    
    void FF_delete_freearea_list(){
    	FREEAREA *temp;
    	temp=p_free_area_list;
    	while(temp!=NULL){
    		temp=p_free_area_list->next;
    		free(p_free_area_list);
    		p_free_area_list=temp;
    	}
    	p_free_area_list=NULL;
    }
    
    REQUIRE_MEMORY *
    FF_initialize_require_memory_list(REQUIRE_MEMORY *init_table,int num)
    {
      REQUIRE_MEMORY *temp;
      REQUIRE_MEMORY *head=NULL;
      REQUIRE_MEMORY *tail=NULL;
      int i;
      for(i=0;i<num;i++){
         temp=(REQUIRE_MEMORY *)malloc(sizeof(REQUIRE_MEMORY));
         strcpy(temp->thread_name,init_table[i].thread_name);
    	 temp->size=init_table[i].size;
    	 temp->duration=init_table[i].duration;
    	 temp->next=NULL;
    	 if(head==NULL)
    		 head=tail=temp;
    	 else{
    		 tail->next=temp;
    		 tail=tail->next;
    	 }
      };
      return head;
    }
    
    void FF_delete_require_memory_list(){
    	REQUIRE_MEMORY *temp;
    	temp=p_thread_require_memory_queue;
    	while(temp!=NULL){
    		temp=p_thread_require_memory_queue->next;
    		free(p_thread_require_memory_queue);
    		p_thread_require_memory_queue=temp;
    	}
    	p_thread_require_memory_queue=NULL;
    }
    
    THREAD_RESIDENCE_MEMORY 
    *FF_initialize_thread_residence_memory_list
    (THREAD_RESIDENCE_MEMORY *init_table,int num)
    {
      THREAD_RESIDENCE_MEMORY *temp;
      THREAD_RESIDENCE_MEMORY *head=NULL;
      THREAD_RESIDENCE_MEMORY *tail=NULL;
      int i;
      for(i=0;i<num;i++){
         temp=(THREAD_RESIDENCE_MEMORY *)malloc(sizeof(THREAD_RESIDENCE_MEMORY));
         strcpy(temp->thread_name,init_table[i].thread_name);
    	 temp->start_address=init_table[i].start_address;
    	 temp->size=init_table[i].size;
    	 temp->next=NULL;
    	 if(head==NULL)
    		 head=tail=temp;
    	 else{
    		 tail->next=temp;
    		 tail=tail->next;
    	 }
      };
      tail_thread_residence_memory_list=tail;
      return head;
    }
    
    void FF_delete_thread_residence_memory_list(){
    	THREAD_RESIDENCE_MEMORY *temp=p_thread_residence_memory_list;
    	
    	temp=p_thread_residence_memory_list;
    	while(temp!=NULL){
    		temp=p_thread_residence_memory_list->next;
    		free(p_thread_residence_memory_list);
    		p_thread_residence_memory_list=temp;
    	}
    	p_thread_residence_memory_list=NULL;
    }
    
    void* FF_thread(void *data){
            int start_address=-1;
    	int i=(((REQUIRE_MEMORY *)(data))->thread_name)[7]-49;
    	THREAD_RESIDENCE_MEMORY *temp;
    	pthread_mutex_lock(&CS_SCREEN);
    	printw("create thread:%s\n",((REQUIRE_MEMORY *)(data))->thread_name);
    	refresh();
    	pthread_mutex_unlock(&CS_SCREEN);
        
        while(1){
    		start_address=FF_require_memory(((REQUIRE_MEMORY *)(data))->size);
    		if(start_address>=0)
    			break;
    		else
    			sleep(1);
    	}
    	temp=(THREAD_RESIDENCE_MEMORY *)malloc(sizeof(THREAD_RESIDENCE_MEMORY));
        strcpy(temp->thread_name,((REQUIRE_MEMORY *)(data))->thread_name);
    	temp->start_address=start_address;
    	temp->size=((REQUIRE_MEMORY *)(data))->size;
    	temp->next=NULL;
    	pthread_mutex_lock(&CS_THREAD_MEMORY_LIST);	
    	tail_thread_residence_memory_list->next=temp;
    	tail_thread_residence_memory_list=tail_thread_residence_memory_list->next;
        pthread_mutex_unlock(&CS_THREAD_MEMORY_LIST);	
    	sleep(((REQUIRE_MEMORY *)(data))->duration);	
    	FF_release_memory(start_address,((REQUIRE_MEMORY *)(data))->size);
    	sem_post(&thread_end[i]);
    	return 0;
    }
    
    int FF_require_memory(int size){
    	int start_address=-1;
    	FREEAREA *p;
    	FREEAREA *p_next;
    	pthread_mutex_lock(&CS_FREEAREA_LIST);
    	p=p_next=p_free_area_list;
    	while(p_next!=NULL){
    		if(size==p_next->size){
    			start_address=p_next->start_address;
    			if(p_next==p_free_area_list)
    				p_free_area_list=p_next->next;
    			else
    			    p->next=p_next->next;
    			free(p_next);
    			break;
    		}
    		else
    			if(size<p_next->size){
    				start_address=p_next->start_address;
    				p_next->start_address+=size;
    				p_next->size-=size;
    				break;
    			}
    			else
    			{
    				p=p_next;
    				p_next=p_next->next;
    			}
    	}
       	pthread_mutex_unlock(&CS_FREEAREA_LIST);
    	return start_address;
    
    }
    
    void FF_release_memory(int start_address,int size){
    	pthread_mutex_lock(&CS_FREEAREA_LIST);
    	
    	pthread_mutex_unlock(&CS_FREEAREA_LIST);
    }
    
    void FF(){
    	int i=0;
    	int j=0;
            REQUIRE_MEMORY *p;
    
    	for(j=0;j<MAX_THREAD;j++){
    	   sem_init(&thread_end[j],0,0);
        }
       	
    	pthread_mutex_init(&CS_THREAD_MEMORY_LIST,NULL);
        pthread_mutex_init(&CS_FREEAREA_LIST,NULL);
    	pthread_mutex_init(&CS_SCREEN,NULL);
    	printw("First Fit\n");
    	refresh();
        p_free_area_list=FF_initialize_freearea_list(init_free_area_table,5);
        p_thread_require_memory_queue=FF_initialize_require_memory_list(init_thread_require_memory_table,3);
        p_thread_residence_memory_list=FF_initialize_thread_residence_memory_list
    (init_thread_residence_memory_table,5);
        p=p_thread_require_memory_queue;
        while(p!=NULL){
              pthread_create(&h_thread[i],NULL,FF_thread,p);
              i++;
      p=p->next;
        };
       
       for(j=0;j<MAX_THREAD;j++){
    		sem_wait(&thread_end[j]);
       }
    	
    	pthread_mutex_lock(&CS_SCREEN);
    	printw("after all threads have finished:\n");
    	refresh();
    	display_thread_residence_memory_list();
    	pthread_mutex_unlock(&CS_SCREEN);
    
    	
    	FF_delete_freearea_list();
    	FF_delete_require_memory_list();
    	FF_delete_thread_residence_memory_list();
    
    	for(j=0;j<MAX_THREAD;j++){
    	   sem_destroy(&thread_end[j]);
            }
    
    	getch();
            printw("\n");
    	refresh();
    }
    	
    void* BF_thread(void *data){
            int start_address=-1;
    	int i=(((REQUIRE_MEMORY *)(data))->thread_name)[7]-49;
    	THREAD_RESIDENCE_MEMORY *temp;
    	pthread_mutex_lock(&CS_SCREEN);
    	printw("create thread:%s\n",((REQUIRE_MEMORY *)(data))->thread_name);
    	refresh();
    	pthread_mutex_unlock(&CS_SCREEN);
        
        while(1){
    		start_address=BF_require_memory(((REQUIRE_MEMORY *)(data))->size);
    		if(start_address>=0)
    			break;
    		else
    			sleep(1);
    	}
    	temp=(THREAD_RESIDENCE_MEMORY *)malloc(sizeof(THREAD_RESIDENCE_MEMORY));
        strcpy(temp->thread_name,((REQUIRE_MEMORY *)(data))->thread_name);
    	temp->start_address=start_address;
    	temp->size=((REQUIRE_MEMORY *)(data))->size;
    	temp->next=NULL;
    	pthread_mutex_lock(&CS_THREAD_MEMORY_LIST);
    	
    	tail_thread_residence_memory_list->next=temp;
    	tail_thread_residence_memory_list=tail_thread_residence_memory_list->next;
        pthread_mutex_unlock(&CS_THREAD_MEMORY_LIST);
    	
    	sleep(((REQUIRE_MEMORY *)(data))->duration);
    	
    	BF_release_memory(start_address,((REQUIRE_MEMORY *)(data))->size);
    	sem_post(&thread_end[i]);
    	return 0;
    }
    
    int BF_require_memory(int size){
      	int start_address=-1;
    	FREEAREA *p;
    	FREEAREA *p_next;
    	pthread_mutex_lock(&CS_FREEAREA_LIST);
    	p=p_next=p_free_area_list;
    	while(p_next!=NULL){
    		if(size==p_next->size){
    			start_address=p_next->start_address;
    			if(p_next==p_free_area_list)
    				p_free_area_list=p_next->next;
    			else
    			    p->next=p_next->next;
    			free(p_next);
    			break;
    		}
    		else
    			if(size<p_next->size){
    				start_address=p_next->start_address;
    				p_next->start_address+=size;
    				p_next->size-=size;
    				p->next=p_next->next;
    				BF_insert_freearea(p_next);
    				break;
    			}
    			else
    			{
    				p=p_next;
    				p_next=p_next->next;
    			}
    	}
       	pthread_mutex_unlock(&CS_FREEAREA_LIST);
    	return start_address;
    
    }
    
    void BF_release_memory(int start_address,int size){
    }
    
    void BF_insert_freearea(FREEAREA *free_node){
         FREEAREA *p;
         FREEAREA *p_next;
    	 
    	 if(p_free_area_list==NULL)
    		 p_free_area_list=free_node;
    	 else{
    	   p_next=p=p_free_area_list;
    	   while(p_next!=NULL&&p_next->size<free_node->size){
    		 p=p_next;
    		 p_next=p_next->next;
    	   }
    	   if(p_next==NULL)      
    		 p->next=free_node;
    	   else
    		 if(p==p_next){  
    		    free_node->next=p;
    		    p_free_area_list=free_node;
    		 }
    		 else{          
    			 free_node->next=p_next;
    			 p->next=free_node;
    		 }
    	 }
    }
    
    void BF_initialize_freearea_list(FREEAREA *init_table,int num){
      FREEAREA *temp;
      int i;
      for(i=0;i<num;i++){
         temp=(FREEAREA *)malloc(sizeof(FREEAREA));
         temp->start_address=init_table[i].start_address;
    	 temp->size=init_table[i].size;
    	 temp->next=NULL;
    	 BF_insert_freearea(temp);
      }
    }
    
    void BF(){
      	int i=0;
    	int j=0;
        REQUIRE_MEMORY *p;
    	for(j=0;j<MAX_THREAD;j++){
    	   sem_init(&thread_end[j],0,0);
        }
     
    	pthread_mutex_init(&CS_THREAD_MEMORY_LIST,NULL);
        pthread_mutex_init(&CS_FREEAREA_LIST,NULL);
    	pthread_mutex_init(&CS_SCREEN,NULL);
    	printw("Best Fit\n");
    	refresh();
        BF_initialize_freearea_list(init_free_area_table,5);
        p_thread_require_memory_queue=BF_initialize_require_memory_list(init_thread_require_memory_table,3);
        p_thread_residence_memory_list=BF_initialize_thread_residence_memory_list
    (init_thread_residence_memory_table,5);
        p=p_thread_require_memory_queue;
        while(p!=NULL){
            pthread_create(&h_thread[i],NULL,BF_thread,p);
            i++;
    	    p=p->next;
        };
       
       for(j=0;j<MAX_THREAD;j++)
    	{sem_wait(&thread_end[j]);}
    	
    	pthread_mutex_lock(&CS_SCREEN);
    	printw("after all threads have finished:\n");
    	refresh();
    	display_thread_residence_memory_list();
    	pthread_mutex_unlock(&CS_SCREEN);
    
    	FF_delete_freearea_list();
    	FF_delete_require_memory_list();
    	FF_delete_thread_residence_memory_list();
    	
    	for(j=0;j<MAX_THREAD;j++){
    	   sem_destroy(&thread_end[j]);
        }
    
    	getch();
        printw("\n");
    	refresh();
    }
    
    void* WF_thread(void *data){
        int start_address=-1;
    	int i=(((REQUIRE_MEMORY *)(data))->thread_name)[7]-49;
    	THREAD_RESIDENCE_MEMORY *temp;
    	pthread_mutex_lock(&CS_SCREEN);
    	printw("create thread:%s\n",((REQUIRE_MEMORY *)(data))->thread_name);
    	refresh();
    	pthread_mutex_unlock(&CS_SCREEN);
        	
        while(1){
    		start_address=WF_require_memory(((REQUIRE_MEMORY *)(data))->size);
    		if(start_address>=0)
    			break;
    		else
    			sleep(1);
    	}
    	temp=(THREAD_RESIDENCE_MEMORY *)malloc(sizeof(THREAD_RESIDENCE_MEMORY));
            strcpy(temp->thread_name,((REQUIRE_MEMORY *)(data))->thread_name);
    	temp->start_address=start_address;
    	temp->size=((REQUIRE_MEMORY *)(data))->size;
    	temp->next=NULL;
    	pthread_mutex_lock(&CS_THREAD_MEMORY_LIST);
    	tail_thread_residence_memory_list->next=temp;
    	tail_thread_residence_memory_list=tail_thread_residence_memory_list->next;
        pthread_mutex_unlock(&CS_THREAD_MEMORY_LIST);
    	
    	sleep(((REQUIRE_MEMORY *)(data))->duration);
    	
    	WF_release_memory(start_address,((REQUIRE_MEMORY *)(data))->size);
    	sem_post(&thread_end[i]);
    	return 0;
    }
    
    void WF_insert_freearea(FREEAREA *free_node){
        FREEAREA *p;
        FREEAREA *p_next;
    	 
    	 if(p_free_area_list==NULL)
    		 p_free_area_list=free_node;
    	 else{
               p=p_next=p_free_area_list;
    	   while(p_next!=NULL&&free_node->size<p_next->size){
    		 p=p_next;
    		 p_next=p_next->next;
    	   }
    	   if(p_next==NULL)      
    		 p->next=free_node;
    	   else
    		 if(p==p_next){  
    		    free_node->next=p;
    		    p_free_area_list=free_node;
    		 }
    		 else{           
    			 free_node->next=p_next;
    			 p->next=free_node;
    		 }
    	 }
    }
    
    void WF_initialize_freearea_list(FREEAREA *init_table,int num){
      FREEAREA *temp;
      int i;
      for(i=0;i<num;i++){
         temp=(FREEAREA *)malloc(sizeof(FREEAREA));
         temp->start_address=init_table[i].start_address;
    	 temp->size=init_table[i].size;
    	 temp->next=NULL;
    	 WF_insert_freearea(temp);
      }
    }
    
    int WF_require_memory(int size){
    	int start_address=-1;
    	FREEAREA *p_next;
    	pthread_mutex_lock(&CS_FREEAREA_LIST);
    	p_next=p_free_area_list;
    	if(size==p_free_area_list->size){
    		start_address=p_next->start_address;
    		p_free_area_list=p_free_area_list->next;
    		free(p_next);
    	}
    	else{
    		if(size<p_next->size){
    			start_address=p_next->start_address;
    			p_next->start_address+=size;
    			p_next->size-=size;
    		        p_free_area_list=p_free_area_list->next;
    			WF_insert_freearea(p_next);
    		}
    	}
    	pthread_mutex_unlock(&CS_FREEAREA_LIST);
    	return (start_address);
    
    }
    void WF_release_memory(int start_address,int size){
    }
    
    void WF(){
        int i=0;
    	int j=0;
       REQUIRE_MEMORY *p;
    
    	for(j=0;j<MAX_THREAD;j++){
    	   sem_init(&thread_end[j],0,0);
        }
       	
    	pthread_mutex_init(&CS_THREAD_MEMORY_LIST,NULL);
        pthread_mutex_init(&CS_FREEAREA_LIST,NULL);
    	pthread_mutex_init(&CS_SCREEN,NULL);
    	printw("Wirst Fit\n");
      	refresh();
        WF_initialize_freearea_list(init_free_area_table,5);
        p_thread_require_memory_queue=WF_initialize_require_memory_list(init_thread_require_memory_table,3);
        p_thread_residence_memory_list=WF_initialize_thread_residence_memory_list
    (init_thread_residence_memory_table,5);
        p=p_thread_require_memory_queue;
        while(p!=NULL){
            pthread_create(&h_thread[i],NULL,WF_thread,p);
            i++;
    	    p=p->next;
       };
        
       for(j=0;j<MAX_THREAD;j++){
    	   sem_wait(&thread_end[j]);
       }
    
    	
    	pthread_mutex_lock(&CS_SCREEN);
    	printw("after all threads have finished:\n");
    	refresh();
    	display_thread_residence_memory_list();
    	pthread_mutex_unlock(&CS_SCREEN);
    
    	
    	FF_delete_freearea_list();
    	FF_delete_require_memory_list();
    	FF_delete_thread_residence_memory_list();
    	
    	for(j=0;j<MAX_THREAD;j++){
    	   sem_destroy(&thread_end[j]);
       }
    
    	getch();
        printw("\n");	
    	refresh();
    }

    【测试结果】

    展开全文
  • 操作系统之存储管理——FIFO算法和LRU算法

    万次阅读 多人点赞 2018-12-04 16:29:59
    操作系统之进程调度——优先权法和轮转法(附上样例讲解) ...存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。 本实验的目的是通过请求页式管理中页面置换算法模拟设...

    操作系统之进程调度——优先权法和轮转法(附上样例讲解)
    操作系统之银行家算法—详解流程及案例数据
    操作系统之多线程编程—读者优先/写者优先详解
    操作系统之存储管理——FIFO算法和LRU算法
    操作系统之磁盘调度——SCAN实例讲解

    要求

    一、实验目的
    存储管理的主要功能之一是合理地分配空间。请求页式管理是一种常用的虚拟存储管理技术。
    本实验的目的是通过请求页式管理中页面置换算法模拟设计,了解虚拟存储技术的特点,掌握请求页式存储管理的页面置换算法。
    二、实验内容
    (1)通过计算不同算法的命中率比较算法的优劣。同时也考虑了用户内存容量对命中率的影响。
    页面失效次数为每次访问相应指令时,该指令所对应的页不在内存中的次数。
    在本实验中,假定页面大小为1k,用户虚存容量为32k,用户内存容量为4页到32页。
    (2)produce_addstream通过随机数产生一个指令序列,共320条指令。
    A、指令的地址按下述原则生成:
    1)50%的指令是顺序执行的
    2)25%的指令是均匀分布在前地址部分
    3)25%的指令是均匀分布在后地址部分
    B、具体的实施方法是:
    1)在[0,319]的指令地址之间随机选取一起点m;
    2)顺序执行一条指令,即执行地址为m 1的指令;
    3)在前地址[0,m 1]中随机选取一条指令并执行,该指令的地址为m’;
    4)顺序执行一条指令,地址为m’ 1的指令
    5)在后地址[m’ 2,319]中随机选取一条指令并执行;
    6)重复上述步骤1)~5),直到执行320次指令
    C、将指令序列变换称为页地址流
    在用户虚存中,按每k存放10条指令排列虚存地址,即320条指令在虚存中的存放方式为:
    第0条~第9条指令为第0页(对应虚存地址为[0,9]);
    第10条~第19条指令为第1页(对应虚存地址为[10,19]);
    。。。。。。
    第310条~第319条指令为第31页(对应虚存地址为[310,319]);
    按以上方式,用户指令可组成32页。
    (3)计算并输出下属算法在不同内存容量下的命中率。
    1)先进先出的算法(FIFO);
    2)最近最少使用算法(LRU);
    3)最佳淘汰算法(OPT);
    4)最少访问页面算法(LFR);
    其中3)和4)为选择内容
    三、系统框图
    在这里插入图片描述
    一、运行结果
    a、运行程序:终端先显示:
    Start memory management.
    Producing address flow, wait for while, please.
    b、地址流、地址页号流生成后,终端显示:
    There are algorithms in the program
    1、Optimization algorithm
    2、Least recently used algorithm
    3、First in first out algorithm
    4、Least frequently used algorithm
    Select an algorithm number, please.
    用户输入适当淘汰算法的号码,并按回车,若是第一次选择,输出相应的地址页号流。然后输出该算法分别计算的用户内存从2k ~ 32k时的命中率,若输入的号码不再1~4中,则显示:
    there is not the algorithm in the program,并重复b。
    c、输出结果后,终端显示 “do you try again with anther algorithm(y/n)”。若键入y则重复b,否则结束。(一般讲四种算法都用过后结束,以便比较)。
    二、运行结果讨论
    1、比较各种算法的命中率
    2、分析当用户内存容量增加是对命中率的影响

    分析

    上面就是实验要求,因为时间关系,只写了fifo和lru两种,但是这两个会了,剩下的了解算法原理就很容易实现。
    对于两种算法的理解和实现为:

    先进先出算法算法(Fifo):

    这个算法原理没有算法,就是先进先出。对于这个结构最好采用的就算队列了,对于java而言,我用的是list集合,每次添加数据的时候添加到第0位置,而如果移除的时候移除末尾的页数。在这个过程中,每执行一条指令的时候,如果这个指令对应的地址(指令/10)在list中,那么就命中,否则就是缺页,需要移除尾,在0位置添加元素。

    举个例子,页面内存为3,(只能存三页),要执行指令地址页面对应为:4 2 3 4 1 2 1 5 6 3
    那么流程顺序为:(4)缺页—>(2,4)缺页—>(3,2,4)缺页—>4命中—>(1,3,2)缺页4被置换—>2命中—>1命中—>(5,1,3)缺页2被替换—>(6,5,1)缺页2被替换—>(3,6,5)缺页1被替换。

    最近最少使用算法(LRU):

    这个算法跟fifo其实还是挺像的,但是有一点区别,最近最少使用。也就是说在一个正常序列的时候如果命中的化,就会把这个地址的页号移动到首位(或者链表首位)。而如果缺页的时候,要把这个链表的末尾位置移除,因为末尾的元素是最近用的最少的(很久前才有的)。对于数据结构,我依然选择Arraylist。每次遇到指令地址的时候我只需要特殊判断下就可以了。我只为了实验的目的,没有考虑性能,因为检查是否存在地址的时候我用了list.contains()方法,这是线性查询复杂度O(n),如果数据量大可以list map组合使用,将查询降低到O(logn).还可以开一个boolean数组标记让查询复杂度降低到O(1),(但是这样的化增大空间),还好数据量不大,影响不大。

    如果页面内存为3,(只能存三页),要执行指令地址页面对应为:4 2 3 4 1 2 1 5 6 3
    那么流程顺序为(4)—>(2,4)—>(3,2,4)—>(4,3,2)命中—>(1,4,3)缺页2被替换—>(2,1,4)缺页—>(1,2,4)命中—>(5,1,2)缺页—>(6,5,1)缺页—>(3,6,5)缺页

    代码

    大致流程就是这样,有一点区别。
    下面附上我的ac代码。有的解释会在注释中:

    package 实验;
    
    import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class storemanage {
    
    	static int mingzhong;
    	static int lenyeliu=320;
    	static int errortime;//失效次数
    	static int random[]=new int[330];//随机指令
    	static Scanner sc=new  Scanner(System.in);
    	static void init()//初始随机数
    	{
    		int index=0;
    		while(index<320)
    		{
    			int m=(int) (Math.random()*320);
    			random[index++]=m;//顺序指令
    			int m1=(int) (Math.random()*(m+1));
    			if(m1==320) {continue;}//跳出问本次
    			random[index++]=m1;//前地址部分 最大317
    			if(m1+1==320) {continue;}//跳出问本次
    			random[index++]=m1+1;//顺序指令
    			int m2=(int) (Math.random()*(319-(m1+2))+m1+2);
    			if(m2==320) {continue;}//跳出问本次
    			random[index++]=m2;//后地址
    			if(index>320)
    			{
    				break;
    			}			
    		}
    	}
    	private static void  lur()
    	{
    		for(int memory=2;memory<=32;memory++)
    		{
    			mingzhong=0;errortime=0;
    		    Queue<Integer>q1=new ArrayDeque<>();
    		    int index=0;
    		    while(index<320)
    		    {
    		    	if(q1.size()<memory)
    		    	{
    		    	  if(q1.contains(random[index]/10))
    		    	  {
    		    		 q1.remove(random[index]/10);
    		    		 mingzhong++;
    		    		 q1.add(random[index]/10);
    		    	  }
    		    	  else
    		    	  {
    		    		  q1.add(random[index]/10);
    		    		  errortime++;
    		    	  }
    		    	}
    		    	else
    		    	{
    		    		if(q1.contains(random[index]/10))
    			    	  {
    			    		 q1.remove(index);
    			    		 mingzhong++;
    			    	  }
    			    	  else
    			    	  {
    			    		  q1.poll();//抛出
    			    		  q1.add(random[index]/10);
    			    		  errortime++;
    			    	  }
    		    	}
    		    	index++;
    		    }
    		    double minz=1-(double)(errortime/(double)(320));//mingzhong/320一样
    		    String minzhon=String.format("%.4f", minz);
    		    System.out.println("lur :memory:"+memory+" 缺失个数:"+errortime+" 命中个数"+mingzhong+"  命中率:"+minzhon);
    		
    		}
    		System.out.println("书否继续Y/N");
    		String team=sc.next();
    		if(team.equals("Y"))
    		{
    			System.out.println("请输入编号");
    			int index=sc.nextInt();
    			if(index==1) {fifo();}
    			else
    			{
    				lur();
    			}
    		}
    	}
    	private static void fifo() {
    		// TODO 自动生成的方法存根
    		for(int memory=2;memory<=32;memory++)
    		{
    			mingzhong=0;errortime=0;
    		    List<Integer>list=new ArrayList<>();
    		    int index=0;
    		    while(index<320)
    	 	    {
    			    if(list.size()<memory)//小于内存
    			    {
    				   if(list.contains(random[index]/10)) {mingzhong++;}
    				   else
    				   {
    					   list.add(random[index]/10);
    					   errortime++;
    				   }				   
    			    }
    			    else//内存慢了
    			    {
    			    	   if(list.contains(random[index]/10)) {mingzhong++;}
    					   else
    					   {
    						   list.remove(0);//移除第一个
    						   list.add(random[index]/10);
    						   errortime++;
    					   }
    			    }
    			    index++;
    			   // System.out.println(index);
    		     }
    		    double minz=1-(double)(errortime/(double)(320));//mingzhong/320一样
    		    String minzhon=String.format("%.4f", minz);
    		    System.out.println("fifo :memory:"+memory+" 缺失个数:"+errortime+" 命中个数"+mingzhong+"  命中率:"+minzhon);
    		}
    		System.out.println("书否继续Y/N");
    		String team=sc.next();
    		if(team.equals("Y"))
    		{
    			System.out.println("请输入编号");
    			int index=sc.nextInt();
    			if(index==1) {fifo();}
    			else
    			{
    				lur();
    			}
    		}
    	}
    	public static void main(String[] args) {
    	 
    	  init();
    	  System.out.println("随机数为");
    	  for(int i=0;i<320;i++)
    	  {
    		  System.out.print(String.format("%5d", random[i]));
    		  if((i+1)%20==0)System.out.println();
    	  }
    	  System.out.println("输入选择算法的计算方式序号\n1:先进先出的算法(FIFO);\n" + 
    	  		"2:最近最少使用算法(LRU);\n" + 
    	  		"3:最佳淘汰算法(OPT);\n" + 
    	  		"4:最少访问页面算法(LFR);");
    	  int index=sc.nextInt();
    	  if(index==1) {
    		  fifo();
    	  }
    	  else if(index==2)
    	  {
    		  lur();
    	  }		
    	}
    }
    
    

    执行结果

    在这里插入图片描述

    fifo

    在这里插入图片描述

    lur

    在这里插入图片描述
    可以看得出成功了。并且最后都是0.9因为固定缺页数(首次命中)达到0.1.
    如果对后端、爬虫、数据结构算法等感性趣欢迎关注我的个人公众号交流:bigsai

    展开全文
  • 1、对内存管理的相关内容做进一步的理解。 2、了解内存管理的主要任务。 3、了解内存管理任务的主要实现方法。 4、通过编程加深理解内存的分配、回收等主要算法的原理。 二、实验内容要求 1、在该实验中,采用可变...

    实验4 内存管理
    一、实验目的
    1、对内存管理的相关内容做进一步的理解。
    2、了解内存管理的主要任务。
    3、了解内存管理任务的主要实现方法。
    4、通过编程加深理解内存的分配、回收等主要算法的原理。
    二、实验内容及要求
    1、在该实验中,采用可变分区方式完成对存储空间的管理(即存储空间的分配与回收工作)。
    2、设计用来记录主存使用情况的数据结构:已分区表和空闲分区表。
    3、在设计好的数据结构上设计一个主存分配算法,要求实现的基本功能操作有:寻找空闲分区,空闲分区表的修改,已分区表的修改。
    4、在设计好的数据结构上设计一个主存回收算法。其中,若回收的分区有上邻空闲分区和(或)下邻空闲分区,要求合并为一个空闲分区登记在空闲分区表的一个表项里。
    三、实验报告
    1、程序中使用的数据结构及符号说明。
    2、给出主要算法的流程图。
    3、给出测试数据和运行结果,要求系统每进行一次分配或回收,都要给出内存映像图或已分配表及未分配表以观察内存的变化。

    代码:

    // OS4.1.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
    //
    #include<stdio.h>
    #include<stdlib.h>
    #define OK 1    //完成 
    #define ERROR 0 //出错
    typedef int Status;
    typedef struct free_table//定义一个空闲区说明表结构
    {
    	int num; //分区序号
    	long address; //起始地址
    	long length;//分区大小 
    	int state; //分区状态 
    }ElemType;
    typedef struct Node//线性表的双向链表存储结构
    {
    	ElemType data;
    	struct Node*prior;//前趋指针
    	struct Node *next;//后继指针
    }Node, *LinkList;
    LinkList first;//头结点
    LinkList end;//尾结点
    int flag;//记录要删除的分区序号
    
    
    Status Initblock()//开创带头结点的内存空间链表
    {
    	first = (LinkList)malloc(sizeof(Node));
    	end = (LinkList)malloc(sizeof(Node));
    	first->prior = NULL;
    	first->next = end;
    	end->prior = first;
    	end->next = NULL;
    	end->data.num = 1;
    	end->data.address = 40;
    	end->data.length = 600;
    	end->data.state = 0;
    	return OK;
    }
    
    void sort()//分区序号重新排序
    {
    	Node *p = first->next, *q;
    	q = p->next;
    	for (; p != NULL; p = p->next)
    	{
    		for (q = p->next; q; q = q->next)
    		{
    
    			if (p->data.num >= q->data.num)
    			{
    				q->data.num += 1;
    			}
    		}
    	}
    }//显示主存分配情况 
    void show()
    {
    	int flag = 0;//用来记录分区序号
    	Node *p = first;
    	p->data.num = 0;
    	p->data.address = 0;
    	p->data.length = 40;
    	p->data.state = 1;
    	sort();
    	printf("\n\t\t》主存空间分配情况《\n");
    	printf("**********************************************************\n\n");
    	printf("分区序号\t起始地址\t分区大小\t分区状态\n\n");
    	while (p)
    	{
    		printf("%d\t\t%d\t\t%d", p->data.num, p->data.address, p->data.length);
    		if (p->data.state == 0)
    			printf("\t\t空闲\n\n");
    		else
    			printf("\t\t已分配\n\n");
    		p = p->next;
    	}
    	printf("**********************************************************\n\n");
    }//首次适应算法
    Status First_fit(int request) {//为申请作业开辟新空间且初始化
    	Node *p = first->next;
    	LinkList temp = (LinkList)malloc(sizeof(Node));
    	temp->data.length = request;
    	temp->data.state = 1;
    	p->data.num = 1;
    	while (p)
    	{
    		if ((p->data.state == 0) && (p->data.length == request))
    		{//有大小恰好合适的空闲块
    			p->data.state = 1;
    			return OK;
    			break;
    		}
    		else if ((p->data.state == 0) && (p->data.length > request))
    		{//有空闲块能满足需求且有剩余
    			temp->prior = p->prior;
    			temp->next = p;
    			temp->data.address = p->data.address;
    			temp->data.num = p->data.num;
    			p->prior->next = temp;
    			p->prior = temp;
    			p->data.address = temp->data.address + temp->data.length;
    			p->data.length -= request;
    			p->data.num += 1;
    			return OK;
    			break;
    		}
    		p = p->next;
    	}
    	return ERROR;
    }//最佳适应算法
    Status Best_fit(int request)
    {
    	int ch;//记录最小剩余空间
    	Node *p = first;
    	Node *q = NULL;//记录最佳插入位置
    	LinkList temp = (LinkList)malloc(sizeof(Node));
    	temp->data.length = request;
    	temp->data.state = 1;
    	p->data.num = 1;
    	while (p)//初始化最小空间和最佳位置
    	{
    		if ((p->data.state == 0) && (p->data.length >= request))
    		{
    			if (q == NULL)
    			{
    				q = p;
    				ch = p->data.length - request;
    			}
    			else if (q->data.length > p->data.length)
    			{
    				q = p;
    				ch = p->data.length - request;
    			}
    		}
    		p = p->next;
    	}
    
    	if (q == NULL) return ERROR;
    	//没有找到空闲块
    	else if (q->data.length == request)
    	{
    		q->data.state = 1;
    		return OK;
    	}
    	else
    	{
    		temp->prior = q->prior;
    		temp->next = q;
    		temp->data.address = q->data.address;
    		temp->data.num = q->data.num;
    		q->prior->next = temp;
    		q->prior = temp;
    		q->data.address += request;
    		q->data.length = ch;
    		q->data.num += 1;
    		return OK;
    	}
    	return OK;
    }//最差适应算法
    Status Worst_fit(int request)
    {
    	int ch;//记录最大剩余空间
    	Node *p = first->next;
    	Node *q = NULL;//记录最佳插入位置
    	LinkList temp = (LinkList)malloc(sizeof(Node));
    	temp->data.length = request;
    	temp->data.state = 1;
    	p->data.num = 1;
    	while (p)//初始化最大空间和最佳位置
    	{
    		if (p->data.state == 0 && (p->data.length >= request))
    		{
    			if (q == NULL)
    			{
    				q = p;
    				ch = p->data.length - request;
    			}
    			else if (q->data.length < p->data.length)
    			{
    				q = p;
    				ch = p->data.length - request;
    			}
    		}
    		p = p->next;
    	}
    	if (q == NULL) return ERROR;//没有找到空闲块
    	else if (q->data.length == request)
    	{
    		q->data.length = 1;
    		return OK;
    	}
    	else
    	{
    		temp->prior = q->prior;
    		temp->next = q;
    		temp->data.address = q->data.address;
    		temp->data.num = q->data.num;
    		q->prior->next = temp;
    		q->prior = temp;
    		q->data.address += request;
    		q->data.length = ch;
    		q->data.num += 1;
    		return OK;
    	} return OK;
    }//分配主存
    Status allocation(int a)
    {
    
    	int request;//申请内存大小
    	printf("请输入申请分配的主存大小(单位:KB):");
    	scanf_s("%d", &request);
    	if (request < 0 || request == 0)
    	{
    		printf("分配大小不合适,请重试!");
    		return ERROR;
    	}
    
    	switch (a)
    	{
    	case 1://默认首次适应算法
    		if (First_fit(request) == OK)
    			printf("\t****分配成功!****");
    		else printf("\t****内存不足,分配失败!****");
    		return OK;
    		break;
    	case 2://选择最佳适应算法
    		if (Best_fit(request) == OK)
    			printf("\t****分配成功!****");
    		else printf("\t****内存不足,分配失败!****");
    		return OK;
    		break;
    	case 3://选择最差适应算法
    		if (Worst_fit(request) == OK)
    			printf("\t****分配成功!****");
    		else printf("\t****内存不足,分配失败!****");
    		return OK;
    		break;
    	}
    }
    Status deal1(Node *p)//处理回收空间
    {
    	Node *q = first;
    	for (; q != NULL; q = q->next)
    	{
    		if (q == p)
    		{
    			if (q->prior->data.state == 0 && q->next->data.state != 0)
    			{
    				q->prior->data.length += q->data.length;
    				q->prior->next = q->next;
    				q->next->prior = q->prior;
    				q = q->prior;
    				q->data.state = 0;
    				q->data.num = flag - 1;
    			}
    			if (q->prior->data.state != 0 && q->next->data.state == 0)
    			{
    				q->data.length += q->next->data.length;
    				q->next = q->next->next;
    				q->next->next->prior = q;
    				q->data.state = 0;
    				q->data.num = flag;
    			}
    			if (q->prior->data.state == 0 && q->next->data.state == 0)
    			{
    				q->prior->data.length += q->data.length;
    				q->prior->next = q->next;
    				q->next->prior = q->prior;
    				q = q->prior;
    				q->data.state = 0;
    				q->data.num = flag - 1;
    			}
    			if (q->prior->data.state != 0 && q->next->data.state != 0)
    			{
    				q->data.state = 0;
    			}
    		}
    	}
    	return OK;
    }
    Status deal2(Node *p)//处理回收空间
    {
    	Node *q = first;
    	for (; q != NULL; q = q->next)
    	{
    		if (q == p)
    		{
    			if (q->prior->data.state == 0 && q->next->data.state != 0)
    			{
    				q->prior->data.length += q->data.length;
    				q->prior->next = q->next;
    				q->next->prior = q->prior;
    				q = p->prior;
    				q->data.state = 0;
    				q->data.num = flag - 1;
    			}
    			if (q->prior->data.state != 0 && q->next->data.state == 0)
    			{
    				q->data.state = 0;
    			}
    			if (q->prior->data.state == 0 && q->next->data.state == 0)
    			{
    				q->prior->data.length += q->data.length;
    				q->prior->next = q->next;
    				q->next->prior = q->prior;
    				q = q->prior;
    				q->data.state = 0;
    				q->data.num = flag - 1;
    			}
    			if (q->prior->data.state != 0 && q->next->data.state != 0)
    			{
    				q->data.state = 0;
    			}
    		}
    	}
    	return OK;
    }//主存回收
    Status recovery(int flag)
    {
    	Node *p = first;
    	for (; p != NULL; p = p->next)
    	{
    		if (p->data.num == flag)
    		{
    			if (p->prior == first)
    			{
    				if (p->next != end)//当前P指向的下一个不是最后一个时
    				{
    					if (p->next->data.state == 0)//与后面的空闲块相连
    					{
    						p->data.length += p->next->data.length;
    						p->next->next->prior = p;
    						p->next = p->next->next;
    						p->data.state = 0;
    						p->data.num = flag;
    					}
    					else p->data.state = 0;
    				}
    				if (p->next == end)//当前P指向的下一个是最后一个时
    				{
    					p->data.state = 0;
    				}
    			}//结束if(p->prior==block_first)的情况
    			else if (p->prior != first)
    			{
    				if (p->next != end)
    				{
    					deal1(p);
    				}
    				else
    				{
    					deal2(p);
    				}
    			}//结束if(p->prior!=block_first)的情况
    		}//结束if(p->data.num==flag)的情况
    	}
    	printf("\t****回收成功****");
    	return OK;
    }//主函数
    void main()
    {
    	int i;//操作选择标记
    	int a;//算法选择标记
    	printf("**********************************************************\n");
    	printf("\t\t用以下三种方法实现主存空间的分配\n");
    	printf("\t(1)首次适应算法\t(2)最佳适应算法\t(3)最差适应算法\n");
    	printf("**********************************************************\n");
    	printf("\n");
    	printf("请输入所使用的内存分配算法:");
    	scanf_s("%d", &a);
    	while (a < 1 || a>3)
    	{
    		printf("输入错误,请重新输入所使用的内存分配算法:\n");
    		scanf_s("%d", &a);
    	}
    	switch (a)
    	{
    	case 1:printf("\n\t****使用首次适应算法:****\n"); break;
    	case 2:printf("\n\t****使用最佳适应算法:****\n"); break;
    	case 3:printf("\n\t****使用最坏适应算法:****\n"); break;
    	}
    	Initblock();//开创空间表
    	while (1)
    	{
    		show();
    		printf("\t1: 分配内存\t2: 回收内存\t0: 退出\n");
    		printf("请输入您的操作:");
    		scanf_s("%d", &i);
    		if (i == 1)
    			allocation(a);//分配内存
    		else if (i == 2)//内存回收
    		{
    			printf("请输入您要释放的分区号:");
    			scanf_s("%d", &flag);
    			recovery(flag);
    		}
    		else if (i == 0)
    		{
    			printf("\n退出程序\n");
    			break;//退出
    		}
    		else//输入操作有误
    		{
    			printf("输入有误,请重试!");
    			continue;
    		}
    	}
    }
    

    运行结果:
    在这里插入图片描述
    分配和回收测试的情况很多,自己试自己体会吧。

    转载自:操作系统课程设计内存管理含源代码(百度文库)

    展开全文
  • 线性表顺序存储实现应用 实验目的 掌握抽象数据类型ADT定义、表示和实现。 掌握线性表基本结构和操作方法。 培养学生灵活使用数据结构解决实际问题能力。 实验内容 采用顺序表方案实现一个简易学生...
  • 操作系统简单分页存储管理(含代码)

    千次阅读 多人点赞 2019-05-19 01:03:39
    在分页存储管理方式中,如果不具备页面置换功能,则称为基本的分页存储管理方式,或称为纯分页存储管理方式,它不具备支持虚拟存储器的功能,显示一次性的特征。本实验通过程序模拟操作系统的基本分页存储管理方式...
  • 预备内容:阅读操作系统的内存管理章节内容,理解段式存储管理的思想相应的分配主存的过程。 2.实践准备:掌握一种计算机高级语言的使用。 要求完成的主要任务: (包括课程设计工作量及其技术要求,以及说明书...
  • 操作系统可以提供多种功能,而操作系统必须提供但又不作为资源管理的是:处理中断。 处理中断是操作系统提供给用户操作系统本身使用的一种功能。 并行性:指两个或多个事件在同一时刻发生;并发性:指两个或多个...
  • 为了提高当前校园信息管理系统效率的目的,本研究在构建校园云存储服务系统用户层基础上,开发设计了基于HDFS体系校园云存储平台各个功能模块。利用了Mybatis开源持久层框架对HDFS体系进行改进,并且DAO层...
  • ⑴ 课程设计目的功能; ⑵ 需求分析,数据结构或模块说明(功能与框图); ⑶ 源程序主要部分; ⑷ 测试用例,运行结果与运行情况分析; ⑸ 自我评价与总结: i)你认为你完成设计哪些地方做得比较好或比较出色...
  • 单链表存储结构实现 ——学生信息管理 一、实验目的 (1) 掌握单链表概念实现方式。 (2) 掌握单链表的存储结构主要运算,如建立、查找、插入、删除等。 二、实验环境 Windows 10,Microsoft Visual C++ 2010 ...
  • 顺序表存储结构实现——学生信息管理 一、实验目的 (1) 掌握顺序表概念实现方式。 (2) 掌握顺序表的存储结构主要运算:建立、查找、插入、删除等。 二、实验环境 Windows 10,Microsoft Visual C++ 2010 ...
  • 7-1:存储管理的功能及目的是什么? 答:存储管理功能: 1) 将逻辑地址映射为物理主存地址 2) 在多用户之间分配物理主存 3) 对各用户区的信息提供保护措施 4) 扩充逻辑主存区 目的: 1) 提高资源利用率,尽量...
  • 数据库实验三 存储过程与触发器

    千次阅读 2020-04-16 16:48:10
    一、实验目的 (1)了解存储过程概念、优点 (2)熟练掌握创建存储过程方法 (3)熟练掌握存储过程调用方法 (4)了解触发器概念、优点 ...1、建立存储过程完成图书管理系统中借书功能,并调用该...
  • 企业中信息是以文档形式存储的,随着电子文档日益增多,建立功能全面文档管理信息系统是非常必要。在分析了现有文档管理系统不足基础上,描述了一个Internet?环境下新型文档管理系统设计与实现。系统采用...
  • 目前企业文件管理的现实状况中存在许许多多的问题,主要包括企业文件管理的失调,没办法保证企业文件的真实性、可靠性、可用性和完整性。随着信息技术和网络技术的发展,企业文件管理系统成为提高办公效率和节约成本...
  • 绪论 本课题是受医疗公司的委托,目的是要开发一套集表单样式的设计表单的可视化实现数据信息的填写与存储以及Web端与客户端的数据同步功能于一体的电子表单辅助设计及管理系统根据委托单位的需求并研究系统的功能,将...
  • 本课题研究的目的是开发一个培训班管理系统。培训班管理系统实现将极大提高培训机教师和管理人员工作效率,也给了学生用户更大选择空间。用户可以通过网站浏览有关培训课程信息教师教学成果和教育资讯...
  • 实验十 视图和存储过程

    千次阅读 2014-12-26 02:40:10
    (1)掌握视图和存储过程基本概念和功能 (2)掌握利用SQL Server Management Studio和Transact-SQL语句创建、修改视图方法 (3)掌握创建、管理存储过程方法 (4)掌握通过视图插入、修改、删除基本表中...
  • 主控部件选用是MSP430F149超低功耗16位单片机,MSP430单片机采用FLASH存储体,此单片机采用了FLASH在线编程JTAG技术,可以利用片内FLASH方便实现软件升级,以达到系统升级的目的。设定状态直接通过在系统...
  • Rich是CKEditor for Rails 3.2更高版本可靠实现。 它包括一个简化工具栏,简化对话框和一个自定义文件管理器。 文件管理器也可以与CKEditor分开使用。 目前,Rich与Active Admin,Rails Admin和Vanilla ...
  • 建立一个高效的存储和读取高安全客户信息管理系统已经成为一种必然! 2系统开发目的 基于企业管理管理自己客户需求,本系统能满足管理安全需求同时, 采用简洁操作增加新客户信息和删除不良客户信息...
  • 应具备的功能 功能为管理有关读者,书籍,借阅和管理者的信息等。本系统结构分为读者信息管理模块,书籍信息管理模块,借阅信息管理模块,管理者信息管理模块。 四.设计思想,主要算法的实现、基本操作、子程序...
  • 文件管理系统 第一章 概 述 操作系统是配置在计算机硬件上的第一层软件,是对硬件的首次扩充,是最...进入文件管理的界面之后,系统则通过一个switch()语句来实现文件管理系统的各个功能的。 switch()语句如下:
  • 项目成本管理的原理和术语 项目成本预算 项目成本控制 项目成本估算 项目质量管理 项目质量计划编制 项目质量保证 质量控制 项目人力资源管理 人力资源计划编制 项目团队组建 项目团队建设 项目团队管理 项目...
  • 使用PL/SQL编写存储过程访问数据库

    千次阅读 2018-06-01 12:08:12
    对学生课程数据库,编写存储过程,完成下面功能: 统计离散数学成绩分布情况,即按照各分数段统计人数; 统计任意一门课平均成绩。 将学生选课成绩从百分制改为等级制(即A、B、C、D、E); 要求...
  • 目录 TOC \o "3-3" \h \z \t "标题 1,1,标题 2,2" 摘要 2 关键词android日程管理智能手机平台SQLite存储 2 第一章 绪 论 3 1.1选题背景 3 1.2选题目的及意义 4 1.3 android系统开发技术 4 1.3.1 Android的功能特征 ...
  • 其编译及建置系统以预编译头文件、最小重建功能及累加连结著称。这些特征明显缩短程式编辑、编译及连结时间花费,在大型软件计划上尤其显著。正是因为Microsoft Visual C++有如此多有点,因此在开发本系统时我把...
  • 在中国客户关系管理的管理思想有着很深的渊源,上下5000年以来那些卖肉的、卖布的、卖鸡的和卖鱼的富商大贾或是小商小贩们,就已经在利用“CRM”做生意了,马路边上的那些杂货店的小老板对自己的客户了如指掌,因为...
  • 本课题研究的目的是利用多媒体和网络技术,建立一个基于网络平台符合现代医疗要求数字化心电图诊断管理系统,将与心电图有关大量数据进行采集、分析、处理与保存,提高心电工作效率并实现心电数据数字化...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 596
精华内容 238
关键字:

存储管理的功能及目的