精华内容
下载资源
问答
  • 用Python模拟实现动态分区存储管理
    千次阅读
    2021-06-05 16:53:11

    实验目的:

        1、熟悉并掌握动态分区分配的各种算法。

        2、熟悉并掌握动态分区中分区回收的各种情况,并能够实现分区合并。

    实验内容及要求:

        用高级语言模拟实现动态分区存储管理

        分区分配算法至少实现首次适应算法或最坏适应算法中的至少1种。熟悉并掌握各种算法的空闲区组织方式。
        分区的初始化-可以由用户输入初始分区的大小。(初始化后只有一个空闲分区,起始地址为0,大小是用户输入的大小)
        分区的动态分配过程:由用户输入作业号和作业的大小,实现分区过程。
        分区的回收:用户输入作业号,实现分区回收,同时,分区的合并要体现出来。(注意:不存在的作业号要给出错误提示!)
        分区的显示:任何时刻,可以查看当前内存的情况(起始地址是什么,大小多大的分区时空闲的,或者占用的,能够显示出来)。

    代码(首次适应和最坏适应):

    import copy
    import operator
    
    class node(object):
        def __init__(self, start, end, length, state=1, ID=0):
            self.start = start
            self.end = end
            self.length = length
            self.state = state  #state为1:内存未分配
            self.Id = ID  #ID为0是未分配,其余为任务编号
    
    #展示所有区块信息
    def show_memory(list):
        print("分配状态    分区号    起始地址   终止地址  分区大小")
        for i in range(0,len(list)):
            p=list[i]
            if p.state==1:
                print("%s%s%s%11.d%11.d%10.d"%('空闲',"          ", p.Id,  p.start, p.end, p.length))
            else:
                print("%s%s%s%11.d%11.d%10.d"%('已分配',"        ", p.Id,  p.start, p.end, p.length))
    
    #回收区块
    def free_k(taskID, list_FREE):
        target=-1
        for i in range(0, len(list_FREE)):
            p = list_FREE[i]
            if p.Id == taskID:
                p.state = 1
                p.Id = 0
                target = i
                print("已回收:", taskID, '  start:', p.start, "  end:", p.end, "  length:", p.length)
                break
        if target == -1:
            print('不存在的作业号!请检查后重新输入。')
            return
        if target - 1 >= 0:
            if list_FREE[target - 1].state == 1:
                a = node(list_FREE[target - 1].start, list_FREE[target].end, list_FREE[target - 1].length + list_FREE[target].length, 1, 0)
                del list_FREE[target - 1]
                del list_FREE[target - 1]
                list_FREE.insert(target - 1, a)
                target = target - 1
        if target + 1 <= len(list_FREE):
            if list_FREE[target + 1].state == 1:
                a = node(list_FREE[target].start, list_FREE[target + 1].end, list_FREE[target].length + list_FREE[target + 1].length, 1, 0)
                del list_FREE[target]
                del list_FREE[target]
                list_FREE.insert(target, a)
    
    #首次适应算法
    def FF(taskID, Tasklength, list_FF):
        for i in range(0, len(list_FF)):
            p = list_FF[i]
            if p.state == 1 and p.length > Tasklength:
                node_bk = node(p.start + Tasklength, p.end, p.length - Tasklength, 1, 0)
                a = node(p.start, p.start + Tasklength - 1, Tasklength, state=0, ID=taskID)
                print("已分配:",a.Id, '  start:', a.start, "  end:", a.end, "  length:", a.length)
                del list_FF[i]
                list_FF.insert(i, node_bk)
                list_FF.insert(i, a)
                return
            if p.state == 1 and p.length == Tasklength:
                print("已分配:",taskID, '  start:', p.start, "  end:", p.end, "  length:", p.length)
                p.Id = taskID
                p.state = 0
                return
        print("内存空间不足")
    
    #最坏适应算法
    def BF(taskID, Tasklength, list_BF):
        q = copy.copy(list_BF)
        cmpfun = operator.attrgetter('length')
        q.sort(key=cmpfun,reverse=False)
        adr_1 = -1
        adr_2 = -1
        for i in range(0, len(q)):
            p = q[i]
            if p.state == 1 and p.length > Tasklength:
                adr_1 = p.start
            elif p.state == 1 and p.length == Tasklength:
                adr_2 = p.start
        if adr_1 == -1 and adr_2 == -1:
            print("内存空间不足")
            return
        for i in range(0, len(list_BF)):
            p = list_BF[i]
            if p.start == adr_1:
                node_bk = node(p.start + Tasklength, p.end, p.length - Tasklength, 1, 0)
                a = node(p.start, p.start + Tasklength - 1, Tasklength, state=0, ID=taskID)
                print("已分配:",a.Id, ' start:', a.start, " end:", a.end, " length:", a.length)
                del list_BF[i]
                list_BF.insert(i, node_bk)
                list_BF.insert(i, a)
                return
            elif p.start == adr_2:
                print("已分配:",taskID, ' start:', p.start, " end:", p.end, " length:", p.length)
                p.Id = taskID
                p.state = 0
                return
    
    if __name__ == "__main__":
        while True:
            try:
                memory_size = int(input("请输入您想要的初始分区的大小 --> "))
                a = node(0, memory_size-1, memory_size, state=1, ID=0)
                b = []
                b.append(a)  #存放所有分区块的信息
                pd_num1 = int(input("请选择:0、首次适应算法 1、最坏适应算法 2、退出程序 --> "))
                if pd_num1 == 0:
                    while True:
                        pd_num2 = int(input("请选择:1、分配内存 2、回收分区 3、展示分区表 4、退出 --> "))
                        if pd_num2 == 1:
                            task_id = int(input("请输入要分配任务的ID --> "))
                            task_size = int(input("请输入要该任务需要的内存大小 --> "))
                            FF(task_id, task_size, b)
                        elif pd_num2 == 2:
                            free_task_id = int(input("请输入要回收任务的ID --> "))
                            free_k(free_task_id, b)
                        elif pd_num2 == 3:
                            show_memory(b)
                        elif pd_num2 == 4:
                            break
                        else:
                            print("请重新输入 --> ")
                elif pd_num1 == 1:
                    while True:
                        pd_num2 = int(input("请选择:1、分配内存 2、回收分区 3、展示分区表 4、退出 --> "))
                        if pd_num2 == 1:
                            task_id = int(input("请输入要分配任务的ID --> "))
                            task_size = int(input("请输入要该任务需要的内存大小 --> "))
                            BF(task_id, task_size, b)
                        elif pd_num2 == 2:
                            free_task_id = int(input("请输入要回收任务的ID --> "))
                            free_k(free_task_id, b)
                        elif pd_num2 == 3:
                            show_memory(b)
                        elif pd_num2 == 4:
                            break
                        else:
                            print("请重新输入 --> ")
                elif pd_num1 == 2:
                    break
                else:
                    print("请输入正确的选项!")
                    continue
            except:
                print("请输入正确的选项!")
    

     

    更多相关内容
  • 动态分区存储管理

    2015-11-09 12:34:07
    动态分区存储管理
  • 熟悉主存的分配与回收 理解在不同的存储管理方式下如何实现主存空间的分配与回收 掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理 方式及其实现过程 实验原理 建立两张表空闲表和已分配表分别将未...
  • 计算机操作系统 实验报告 实验二 实验题目存储器管理 系别计算机科学与技术 系 班级 姓名 学号2 一实验目的 深入理解动态分区存储管理方式下的内存空间的分配与回收 二实验内容 编写程序完成动态分区存储管理方式下...
  • 系统采用最佳适应分配算法为作业分配主存空间,而且具有紧凑技术。请编程完成以下操作: (1). 输出此时的已分配区表和未分配区表; (2). 装入 Job3(15K),输出主存分配后的已分配区表和未分配区表; (3)....(4)....
  • 在Linux下动态分区存储管理的内存分别配回收,实现对动态分区的深层理解 通过遍历所有区间,每次都找到最小空闲分区进行分配 通过循环在空闲区找是否有适合区间存储作业 通过循环查找要回收的已使用分区区号
  • 操作系统 实验3【动态分区存储管理
    1. 操作系统 实验1【短作业优先调度算法(C++实现——FCFS\SJF\HRRN)】
    2. 操作系统 实验2【动态高优先权优先调度算法 C++实现】
    3. 操作系统 实验3【动态分区存储管理 Python实现】
    4. 操作系统 实验4【基本分页存储管理 C++实现】

    目录

    一、实验目的(目的与任务)

    二、实验内容(内容、要求与安排方式)

    三、实验代码

    ①创建表示分区的类,类包含:分区ID、起始地址、结束地址、分区长度、分区状态

    ②导入python模块,方便拷贝分区对象

    ③编写表示分区状态的函数

    ④编写冒泡排序函数

    ⑤编写首次适应算法(First Fit)函数

    ⑥编写最佳适应算法(Best Fit)函数

    ⑦回收内存(作业)函数

    ⑧编写主函数

    完整实验代码

    四、实验结果

    五、实验总结


    一、实验目的(目的与任务)

    熟悉并掌握动态分区分配的各种算法。

    熟悉并掌握动态分区中分区回收的各种情况,并能够实现分区合并。

    二、实验内容(内容、要求与安排方式)

    用高级语言模拟实现动态分区存储管理,要求:

    1. 分区分配算法至少实现首次适应算法、最佳适应算法和最坏适应算法中的至少一种。熟悉并掌握各种算法的空闲区组织方式。
    2. 分区的初始化——可以由用户输入初始分区的大小。(初始化后只有一个空闲分区,起始地址为0,大小是用户输入的大小)
    3. 分区的动态分配过程:由用户输入作业号和作业的大小,实现分区过程。
    4. 分区的回收:用户输入作业号,实现分区回收,同时,分区的合并要体现出来。(注意:不存在的作业号要给出错误提示!)
    5. 分区的显示:任何时刻,可以查看当前内存的情况(起始地址是什么,大小多大的分区时空闲的,或者占用的,能够显示出来)
    6. 要求考虑:(1)内存空间不足的情况,要有相应的显示;

          (2)作业不能同名,但是删除后可以再用这个名字;

          (3)作业空间回收是输入作业名,回收相应的空间,如果这个作业名不存在,也要有相应的提示。

    三、实验代码

    ①创建表示分区的类,类包含:分区ID、起始地址、结束地址、分区长度、分区状态

    class Memory(object):

        def __init__(selfstartendlengthstate=1ID=0):

            self.Id = ID  ##ID0是未分配,其余为任务编号

            self.start = start

            self.end = end

            self.length = length

            self.state = state  # state1:内存未分配

    ②导入python模块,方便拷贝分区对象

    import copy 导入python模块,copy仅拷贝对象本身

    ③编写表示分区状态的函数

    def show_memory(list):

        print("分配状态    分区号    起始地址   终止地址  分区大小")

        for i in range(0len(list)):

            p = list[i]

            if p.state == 1:

                print("%s%s%s%11.d%11.d%10.d" % ('空闲'"          ", p.Id, p.start, p.end, p.length))

            else:

                print("%s%s%s%11.d%11.d%10.d" % ('已分配'"        ", p.Id, p.start, p.end, p.length))

    ④编写冒泡排序函数

    ##冒泡排序

    def bubble_sort(list):

        count = len(list)

        for i in range(0, count):

            for j in range(i + 1, count):

                if list[i].length < list[j].length:

                    list[i], list[j] = list[j], list[i]

        return list

    ⑤编写首次适应算法(First Fit)函数

    首次适应算法(First Fit

    def FF(work_idwork_lengthlist):

        for i in list:

            if i.Id == work_id:

                print('作业已存在!')

                return

        for i in range(0len(list)):

            p = list[i]

            if p.state == 1 and p.length > work_length:  # p是当前未分配内存的大小

                node2 = Memory(p.start + work_length, p.end, p.length - work_length, 10)  剩下的未分配的

                a = Memory(p.start, p.start + work_length - 1, work_length, state=0ID=work_id)  # a是已分配的

                del list[i]

                list.insert(i, node2)

                list.insert(i, a)

                show_memory(list)

                return

            if p.state == 1 and p.length == work_length:

                p.state = 0

                show_memory(list)

                return

        print("内存空间不足!")

    ⑥编写最佳适应算法(Best Fit)函数

    ##最佳适应算法(Best Fit

    def BF(work_idwork_lengthli):

        for i in li:

            if i.Id == work_id:

                print('作业已存在!')

                return

        q = copy.copy(li)

        q = bubble_sort(q)  从小到大排序,给所有已分配和未分配的排序

        s = -1

        ss12 = -1

        for i in range(0len(q)):

            p = q[i]

            if p.state == 1 and p.length > work_length:  # p.state == 1 已分配的不参与分配

                s = p.start  # s得到起始位置

            elif p.state == 1 and p.length == work_length:

                ss12 = p.start

        if s == -1 and ss12 == -1:

            print("内存空间不足!")

            return

        for i in range(0len(li)):

            p = li[i]

            if p.start == s:

                node2 = Memory(p.start + work_length, p.end, p.length - work_length, 10)  未分配

                a = Memory(p.start, p.start + work_length - 1, work_length, state=0ID=work_id)

                del li[i]

                li.insert(i, node2)

                li.insert(i, a)

                show_memory(li)

                return

            elif p.start == ss12:

                p.state = 0

                show_memory(li)

                return

     

    ⑦回收内存(作业)函数

    ##回收内存(作业)函数

    def free1(work_idli):

        for i in range(0len(li)):

            p = li[i]

            if p.Id == work_id:

                p.state = 1

                target = i

                p.Id = 0

                break

        向前合并空闲块

        if target - 1 > 0:

            if li[target - 1].state == 1:

                a = Memory(li[target - 1].start, li[target].end, li[target - 1].length + li[target].length, 10)

                del li[target - 1]

                del li[target - 1]

                li.insert(target - 1, a)

                target = target - 1

        向后合并空闲块

        if target + 1 < len(li):

            if li[target + 1].state == 1:

                a = Memory(li[target].start, li[target + 1].end, li[target].length + li[target + 1].length, 10)

                del li[target]

                del li[target]

                li.insert(target, a)

        show_memory(li)

    ⑧编写主函数

    if __name__ == '__main__':

        print("输入内存大小:")

        size = int(input())

        a = Memory(0, size - 1, size, state=1ID=0)

        b = []

        b.append(a)

        print('*******1:初始化******')

        print('*******2:分配空间****')

        print('*******3:回收********')

        print('*******4:查看********')

        print('*******5:退出********')

        while (True):

            select = input('请输入想要执行的功能:')

            if select == '5':

                break

            elif select == '1':

                print("输入内存大小:")

                size = int(input())

                a = Memory(0, size - 1, size, state=1ID=0)

                b = []

                b.append(a)

            elif select == '2':

                print("1.首次适应算法:FF")

                print("2.最佳适应算法:BF")

                x = input("请输入分配执行的算法:")

                x = float(x)

                repit = 'Y'

                while (repit == 'Y'):

                    if x == 1:

                        work_size = input('请输入作业id和大小:').split()

                        FF(work_size[0], int(work_size[1]), b)

                        repit = input('是否继续(Y/N):')

                    elif x == 2:

                        work_size = input('请输入作业id和大小:').split()

                        BF(work_size[0], int(work_size[1]), b)

                        repit = input('是否继续(Y/N):')

            elif select == '3':

                id_delete = input('请输入删除作业id')

                free1(id_delete, b)

            else:

                show_memory(b)

    完整实验代码

    import copy  # 导入python模块,copy仅拷贝对象本身
    
    
    # 创建表示分区的类,类包含:分区ID、起始地址、结束地址、分区长度、分区状态
    class Memory(object):
        def __init__(self, start, end, length, state=1, ID=0):  # __init__()方法是一种特殊的方法,被称为类的初始化方法,当创建这个类的实例时就会调用该方法
            # self代表类的实例,self在定义类的方法时是必须有的,虽然在调用时不必传入相应的参数
            self.Id = ID  ##ID为0是未分配,其余为任务编号
            self.start = start
            self.end = end
            self.length = length
            self.state = state  # state为1:内存未分配
    
    
    # 编写表示分区状态的函数
    def show_memory(list):
        print("分配状态    分区号    起始地址   终止地址  分区大小")
        for i in range(0, len(list)):
            p = list[i]
            if p.state == 1:
                print("%s%s%s%11.d%11.d%10.d" % ('空闲', "          ", p.Id, p.start, p.end, p.length))
            else:
                print("%s%s%s%11.d%11.d%10.d" % ('已分配', "        ", p.Id, p.start, p.end, p.length))
    
    
    # 首次适应算法(First Fit)
    def FF(work_id, work_length, list):
        for i in list:
            if i.Id == work_id:
                print('作业已存在!')
                return
        for i in range(0, len(list)):
            p = list[i]
            if p.state == 1 and p.length > work_length:  # p是当前未分配内存的大小
                node2 = Memory(p.start + work_length, p.end, p.length - work_length, 1, 0)  # 剩下的未分配的
                a = Memory(p.start, p.start + work_length - 1, work_length, state=0, ID=work_id)  # a是已分配的
                del list[i]
                list.insert(i, node2)
                list.insert(i, a)
                show_memory(list)
                return
            if p.state == 1 and p.length == work_length:
                p.state = 0
                show_memory(list)
                return
        print("内存空间不足!")
    
    
    # 回收内存(作业)函数
    def free1(work_id, li):
        for i in range(0, len(li)):
            p = li[i]
            if p.Id == work_id:
                p.state = 1
                target = i
                p.Id = 0
                break
        # 向前合并空闲块
        if target - 1 > 0:
            if li[target - 1].state == 1:
                a = Memory(li[target - 1].start, li[target].end, li[target - 1].length + li[target].length, 1, 0)
                del li[target - 1]
                del li[target - 1]
                li.insert(target - 1, a)
                target = target - 1
        # 向后合并空闲块
        if target + 1 < len(li):
            if li[target + 1].state == 1:
                a = Memory(li[target].start, li[target + 1].end, li[target].length + li[target + 1].length, 1, 0)
                del li[target]
                del li[target]
                li.insert(target, a)
        show_memory(li)
    
    
    # 冒泡排序
    def bubble_sort(list):
        count = len(list)
        for i in range(0, count):
            for j in range(i + 1, count):
                if list[i].length < list[j].length:
                    list[i], list[j] = list[j], list[i]
        return list
    
    
    # 最佳适应算法(Best Fit)
    def BF(work_id, work_length, li):
        for i in li:
            if i.Id == work_id:
                print('作业已存在!')
                return
        q = copy.copy(li)
        q = bubble_sort(q)  # 从小到大排序,给所有已分配和未分配的排序
        s = -1
        ss12 = -1
        for i in range(0, len(q)):
            p = q[i]
            if p.state == 1 and p.length > work_length:  # p.state == 1,已分配的不参与分配
                s = p.start  # s得到起始位置
            elif p.state == 1 and p.length == work_length:
                ss12 = p.start
        if s == -1 and ss12 == -1:
            print("内存空间不足!")
            return
        for i in range(0, len(li)):
            p = li[i]
            if p.start == s:
                node2 = Memory(p.start + work_length, p.end, p.length - work_length, 1, 0)  # 未分配
                a = Memory(p.start, p.start + work_length - 1, work_length, state=0, ID=work_id)
                del li[i]
                li.insert(i, node2)
                li.insert(i, a)
                show_memory(li)
                return
            elif p.start == ss12:
                p.state = 0
                show_memory(li)
                return
    
    
    # 主函数
    if __name__ == '__main__':
        print("输入内存大小:")
        size = int(input())
        a = Memory(0, size - 1, size, state=1, ID=0)
        b = []
        b.append(a)
        print('*******1:初始化******')
        print('*******2:分配空间(FF\BF)****')
        print('*******3:回收********')
        print('*******4:查看********')
        print('*******5:退出********')
        while (True):
            select = input('请输入想要执行的功能:')
            if select == '5':
                break
            elif select == '1':
                print("输入内存大小:")
                size = int(input())
                a = Memory(0, size - 1, size, state=1, ID=0)
                b = []
                b.append(a)
            elif select == '2':
                print("1.首次适应算法:FF")
                print("2.最佳适应算法:BF")
                x = input("请输入分配执行的算法:")
                x = float(x)
                repit = 'Y'
                while (repit == 'Y'):
                    if x == 1:
                        work_size = input('请输入作业id和大小:').split()
                        FF(work_size[0], int(work_size[1]), b)
                        repit = input('是否继续(Y/N):')
                    elif x == 2:
                        work_size = input('请输入作业id和大小:').split()
                        BF(work_size[0], int(work_size[1]), b)
                        repit = input('是否继续(Y/N):')
            elif select == '3':
                id_delete = input('请输入删除作业id:')
                free1(id_delete, b)
            else:
                show_memory(b)

    四、实验结果

    BF算法有一点小毛病儿:两个相同的分区,比如2个20,这个BF是从末尾地址开始分配的;不能这样写,应该从低地址开始分配。

       

    五、实验总结

    动态分区分配算法包括如下4种算法:首次适应算法(First Fit)、最佳适应算法(Best Fit)、最坏适应算法(Worst Fit)、临近适应算法(Next Fit)。

    动态分区管理方式,在初始时不将主存划分区域,而是把占用区域外的空间看作一个大的空闲区。当作业要求装入主存时,根据作业的大小查询主存内各空闲区的状态,按照特定的算法选择一个合适的空闲区,按作业大小划分出一个分区并装入该作业,剩下的区域作为新的空闲区。

    当作业执行完毕后,所占用的主存空间将被回收,成为一个空闲区;如果该空闲区的相邻分区也是空闲区,则需要将相邻空闲区合并成一个空闲区。

       通过本次实验,我对动态分区分配算法有了更深的理解,将4种算法的特点整理如下:

    算法

    算法思想

    分区排列顺序

    优点

    缺点

    首次适应算法

    从头到尾寻找合适的分区

    空闲分区以地址递增次序排列

    综合看,首次适应算法性能最好。算法开销小,回收分区后,一般不需要对空闲分区队列重新排序

    略!

    最佳适应算法

    优先使用更小的分区,以保留更多的大分区

    空闲分区以容量递增次序排列

    会有更多的大分区被保留下来,更能满足大进程需求

    会产生很多太小的、难以利用的碎片:算法开销大,回收分区后可能需要对空闲分区队列重新排序

    最坏适应算法

    优先使用更大的分区,以防止产生太小的不可用碎片

    空闲分区以容量递减次序排列

    可以减少难以利用的小碎片

    大分区容易被用完,不利于大进程:算法开销大(原因同上)

    临近适应算法

    由首次适应算法演变而来,每次从上次查找结束的位置开始查找

    空闲分区以地址递增次序排列(可排列成循环链表)

    不用每次都从低地址的小分区开始检索。算法开销小(原因同首次适应算法)

    会使高地址的大分区也被用完

    展开全文
  • 操作系统课设做的动态分区分配算法。第一次上传资源,做的有些乱,献丑了,其中循环首次循环和最佳、最坏分配算法其实只是从首次适应算法改了一点东西。 补充几句,是JAVA做的,分配和回收算法都有,使用数组实现
  • ◆模拟动态分区存储管理算法,实现用户区的分配与回收 ◆菜单包括 ➢初始化(设置内存大小、可用分区表、内存分配表) ➢分配(输入一个进程名和所需内存大小,按某种分配算法进行分配,输出分配情况;如不能分配,说明...
  • 操作系统实验_动态分区存储管理方式的主存分配回收 功能: 《计算机操作系统》实验 首次适应性算法 摸拟 动态分区 存储管理方式的主存 分配 和 回收
  • 操作系统老师留的作业,动态分区存储管理方式的主存分配回收
  • c++模拟实现动态分区存储管理

    千次阅读 2021-06-05 17:08:58
    请重新选择"二、介绍 编程实现动态分区存储管理方式的主存分配与回收。具体内容包括:首先确定主存空间分配表;然后采用最优适应算法及首次适应算法完成主存空间的分配和回收。 具体讲: 初始状态:动态分区管理方式...

    一、代码

    #include<iostream>
    #include<vector>
    #include<string>
    using namespace std;
    typedef struct memoryBlock{
        string jobName;
        int startadress;
        int length;
        bool state;
    }memoryBlock;
    vector<memoryBlock> mb;
    void init(){
        memoryBlock m1,m2,m3,m4,m5;
        m1.jobName="作业1";m2.jobName="作业3";m3.jobName="未分配";m4.jobName="作业2";m5.jobName="未分配";
        m1.state=1;m2.state=1;m3.state=0;m4.state=1;m5.state=0;
        m1.startadress=5;m2.startadress=10;m3.startadress=14;m4.startadress=26;m5.startadress=32;
        m1.length=5;m2.length=4;m3.length=12;m4.length=6;m5.length=96;
        mb.push_back(m1);mb.push_back(m2);mb.push_back(m3);mb.push_back(m4);mb.push_back(m5);
    }
    void firstfit(){
        string name;
        cout<<"请输入要分配的作业名称:";
        cin>>name;
        int size;
        cout<<"请输入作业主存量:";
        cin>>size;
        for(vector<memoryBlock>::iterator it = mb.begin();it!=mb.end();++it){
            int s_pos = it->startadress+size;
            int last_size = it->length-size;
            int f = 0;
            if(it->length>size){
                f=1;
            }
            if(it->state==0&&it->length>=size){
                it->state=1;
                it->length=size;
                it->jobName = name;
                if(f){
                    memoryBlock m;
                    m.jobName="未分配";
                    m.length=last_size;
                    m.state=0;
                    m.startadress = s_pos;
                    it++;
                    mb.insert(it,m);
                }
                break;
            }
        }
    }
    void bestfit(){
        string name;
        cout<<"请输入要分配的作业名称:";
        cin>>name;
        int size;
        cout<<"请输入作业主存量:";
        cin>>size;
        int min_last=128;
        for(vector<memoryBlock>::iterator it = mb.begin();it!=mb.end();++it){
            if(it->state==0&&it->length>=size){
                int last_size = it->length-size;
                if(last_size<min_last){
                    min_last=last_size;
                }
            }
        }
        for(vector<memoryBlock>::iterator it = mb.begin();it!=mb.end();++it){
            int s_pos = it->startadress+size;
            int last_size = it->length-size;
            if(last_size==min_last){
                it->state=1;
                it->length=size;
                it->jobName = name;
                if(last_size>0){
                    memoryBlock m;
                    m.jobName="未分配";
                    m.length=last_size;
                    m.state=0;
                    m.startadress = s_pos;
                    it++;
                    mb.insert(it,m);
                }
                break;
            }
        }
    }
    void memoryrecycle(){
        cout<<"请输入要回收的作业名称:";
        string name;
        cin>>name;
        vector<memoryBlock>::iterator it_new;
        for(vector<memoryBlock>::iterator it = mb.begin();it!=mb.end();++it){
            if(it->jobName.compare(name)==0){
                it->state=0;
                it->jobName="未分配";
                it_new = it;
                break;
            }
        }
        vector<memoryBlock>::iterator it_pre=--it_new;
        it_new++;
        vector<memoryBlock>::iterator it_next=++it_new;
        it_new--;
        if(it_pre->state==1&&it_next->state==0){
            it_new->length+=it_next->length;
            mb.erase(it_next);
        }
        else if(it_pre->state==0&&it_next->state==1){
            it_pre->length+=it_new->length;
            mb.erase(it_new);
        }
        else if(it_pre->state==0&&it_next->state==0){
            it_pre->length+=it_new->length;
            it_pre->length+=it_next->length;
            mb.erase(it_new);
            mb.erase(it_next);
        }
    }
    void showMT(){
        cout<<"*********************空闲区表*********************"<<endl;
        cout<<"\t起止\t|\t长度\t|\t状态"<<endl;
        for(vector<memoryBlock>::iterator it = mb.begin();it!=mb.end();++it){
            if(it->state==0){
                cout<<"\t"<<it->startadress<<"k\t|\t"<<it->length<<"k\t|\t"<<it->jobName<<endl;
            }
        }
        cout<<"**************************************************"<<endl;
        cout<<"*********************已分配表*********************"<<endl;
        cout<<"\t起止\t|\t长度\t|\t名称"<<endl;
        for(vector<memoryBlock>::iterator it = mb.begin();it!=mb.end();++it){
            if(it->state==1){
                cout<<"\t"<<it->startadress<<"k\t|\t"<<it->length<<"k\t|\t"<<it->jobName<<endl;
            }
        }
        cout<<"**************************************************"<<endl;
    }
    int main(){
        init();
        cout<<"选择分配主存算法(a-首次适应算法,b-最优适应算法)"<<endl<<"请输入选择的算法:";
        char option1;
        cin>>option1;
        int option2;
        int running = 1;
        while(running){
            cout<<"选择功能项(0-退出,1-分配主存,2-回收主存,3-显示主存)"<<endl<<"请输入选择的功能:";
            cin>>option2;
            switch (option2){
                case 0: running = 0;break;
                case 1: {
                    if(option1=='a'){
                        firstfit();
                    }
                    else if(option1=='b'){
                        bestfit();
                    }
                    break;
                }
                case 2: {memoryrecycle();break;}
                case 3: {showMT();break;}
                default:{
                    cout<<"输入有误!请重新选择"<<endl;
                    break;
                } 
                
            }
        }
        return 0;
    }

    二、介绍

    编程实现动态分区存储管理方式的主存分配与回收。具体内容包括:首先确定主存空间分配表;然后采用最优适应算法及首次适应算法完成主存空间的分配和回收。

    具体讲:

    初始状态:动态分区管理方式预先不将主存划分区域。而是把主存除操作系统占用区域外的空间看作一个大的空闲区。当作业要求装入主存时,根据作业的大小查询主存内各空闲区。并按照特定的算法选择一合适的空闲区,按作业大小的要求画出一个分区并装入该作业。剩下的区域作为新的空闲区。

    当作业执行完毕后,所占用的主存空间将被回收,成为一个空闲区。注意如果该空闲区的相邻分区也是空闲区,则需要将相邻空闲区合并成一个空闲区。

    提示:

    动态分区大小由作业需求量决定,分区的长度预先不能固定。

    可建立两张分区表记录主存使用情况:

    “已分配表”记录作业占用分区;“空闲区表”记录空闲区。

    主程序菜单可参考:

        选择功能项(0-退出、1-分配主存、2-回收主存、3-显示主存)

        分配时,要求输入作业名和长度

        回收时,要求输入要回收的作业名

        显示主存,则显示空闲分区情况以及已分配分区情况等。

    本实验模拟在两种存储管理方式下的主存分配和回收。

    图例:

    可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时,根据作业需要的主存量查看是否有足够的空闲空间,若有,则按需要量分割一个分区分配给该作业;若无,则作业不能装入。随着作业的装入、撤离,主存空间被分成许多个分区,有的分区被作业占用,而有的分区是空闲的。

    为了说明哪些区是空闲的,可以用来装入新作业,必须要有一张空闲区说明表,格式如下:

     

    起    址

    长    度

    状      态

    第一栏

    14 K

    12 K

    未 分 配

    第二栏

    32 K

    96 K

    未 分 配

    其中,起址——指出一个空闲区的主存起始地址。

          长度——指出从起始地址开始的一个连续空闲的长度。

          状态——有两种状态,一种是“未分配”状态,指出对应的由起址指出的某个长度的区域是空闲区;另一种是“空表目”状态,表示表中对应的登记项目是空白(无效),可用来登记新的空闲区(例如,作业撤离后,它所占的区域就成了空闲区,应找一个“空表目”栏登记归还区的起址和长度且修改状态)。由于分区的个数不定,所以空闲区说明表中应有适量的状态为“空表目”的登记栏目,否则造成表格“溢出”无法登记。

    上述的这张说明表的登记情况是按例所装入的三个作业占用的主存区域后填写的。

    (1) 当有一个新作业要求装入主存时,必须查空闲区说明表,从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量,这时应把原来的空闲区变成两部分:一部分分给作业占用;另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区,而尽量保存高地址部分有较大的连续空闲区域,以利于大型作业的装入。为此,在空闲区说明表中,把每个空闲区按其地址顺序登记,即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩”,总是让“空表目”栏集中在表格的后部。

    (2) 采用最先适应算法(顺序分配算法)分配主存空间。

    按照作业的需要量,查空闲区说明表,顺序查看登记栏,找到第一个能满足要求的空闲区。当空闲区大于需要量时,一部分用来装入作业,另一部分仍为空闲区登记在空闲区说明表中。

    由于本实验是模拟主存的分配,所以把主存区分配给作业后并不实际启动装入程序装入作业,而用输出“分配情况”来代替。最先适应分配算法如图4-1。

    (3) 当一个作业执行结束撤离时,作业所占的区域应该归还,归还的区域如果与其它空闲区相邻,则应合成一个较大的空闲区,登记在空闲区说明表中。例如,在提示(1)中列举的情况下,如果作业2撤离,归还所占主存区域时,应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。归还主存时的回收算法如图4-2。

    (4) 请按最先适应算法设计主存分配和回收的程序。然后按主存中已装入三个作业,且形成两个空闲区,确定空闲区说明表的初值。现有一个需要主存量为6K的作业4申请装入主存;然后作业3撤离;再作业2撤离。请你为它们进行主存分配和回收,把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。

    图1:最先适应分配模拟算法

     
     

    图2: 主存回收算法

     
     


     

     

     

     

    展开全文
  • 操作系统:动态分区存储管理

    千次阅读 多人点赞 2020-05-17 17:09:04
    致读者: 博主是一名数据科学与大数据专业大二的学生,真正的一个互联网萌新,写博客...熟悉并掌握动态分区分配的各种算法,熟悉并掌握动态分区分区回收的各种情况,并能够实现分区合并。用高级语言模拟实现动态分区.

    致读者: 博主是一名数据科学与大数据专业大二的学生,真正的一个互联网萌新,写博客一方面是为了记录自己的学习历程,一方面是希望能够帮助到很多和自己一样处于困惑的读者。由于水平有限,博客中难免会有一些错误,有纰漏之处恳请各位大佬不吝赐教!之后会写大数据专业的文章哦。尽管当前水平可能不及各位大佬,但我会尽我自己所能,做到最好☺。——天地有正气,杂然赋流形。下则为河岳,上则为日星。

    实验目的

    熟悉并掌握动态分区分配的各种算法,熟悉并掌握动态分区中分区回收的各种情况,并能够实现分区合并。用高级语言模拟实现动态分区存储管理。

    实验内容

    分区分配算法至少实现首次适应算法、最佳适应算法和最坏适应算法中的至少一种。熟悉并掌握各种算法的空闲区组织方式。

    分区的初始化——可以由用户输入初始分区的大小。(初始化后只有一个空闲分区,起始地址为0,大小是用户输入的大小)

    分区的动态分配过程:由用户输入作业号和作业的大小,实现分区过程。

    分区的回收:用户输入作业号,实现分区回收,同时,分区的合并要体现出来。(注意:不存在的作业号要给出错误提示!)

    分区的显示:任何时刻,可以查看当前内存的情况(起始地址是什么,大小多大的分区时空闲的,或者占用的,能够显示出来)。

    实验要求

    (1)内存空间不足的情况,要有相应的显示;

    (2)作业不能同名,但是删除后可以再用这个名字;

    (3)作业空间回收是输入作业名,回收相应的空间,如果这个作业名不存在,也要有相应的提示。

    (4)实验完成后要参加实验答辩。

    正文

    结果展示

    {% checkbox checked, 划重点 %}

    为了输入和展示的方便,这次在代码的基础上增加了一组模拟数据,这个模拟数据是上课讲的例题。内置三种算法,分别是FF、BF、WF,这三种算法的区别就是排序算法的不同。

    初始化内存空间:

    这个地方设置了自定义异常处理类,用来输入整数。

    然后选择需要执行的算法

    这个地方设置了异常处理,只能够输入这三个字符,其它字符视为错误,需要重新输入。

    首先,我们调用模拟数据直接生成最终的结果:

    作业表状态:

    空闲区表状态:

    手动制表:

    在线绘图:

    这个图是使用plt第三方库绘制的图形,采用散点补帧的形式做成类动画效果,当时和自己本来预想的差别好大,自己预想的是能够根据输入动态改变,后来发现难度有点大,于是换成了这种最后结果的方式进行动画效果。

    绘制后图片会自动保存到当前目录下的show.png。

    注意,图形没有绘制结束不能够点击关闭否则会出现异常,只有当绘制完成之后才能够关闭窗口从而执行下一步。

    手动输入:考虑输入重复作业名,考虑作业无法分配内存,考虑删除作业不存在或已经删除的情况。

    重复输入:

    无法分配内存

    删除情况

    在任意的时刻都可以查看信息:

    手动打表:

    图形展示:

    实验总结

    这个实验我觉的,可以分为几个步骤,第一就是插入作业的时候,判断是否有重复的作业名,基本的思路大致有这几个:1、使用集合,判断这个作业名已经在集合了。2、直接查找,看看能否找到。对于这些方法,使用python都是比较方便的,在这里我使用的方法是 列表生成式 ,然后可以快速判断作业名已经重复。同样的释作业的时候,也需要查看,作业是否运行。插入完作业肯定要更新数据了。

    数据更新:主要分为两个方面,第一个就是作业信息的修改,包括起始地址和结束地址,第二个就是空闲分区是否被利用,如果成功分配并被利用,那么肯定要更新空闲区表,更新空闲区表的起始地址和结束地址,如果这个分区的大小位0,那么就移除这个分区。

    释放作业关于分区的释放:分区释放存在两方面的问题,同样是作业信息的修改和空闲分区的修改。作业信息的修改,其实就是,从内存里移除,然后修改作业的状态和作业的起始地址与结束地址。对于空闲区表的修改就有点复杂了,主要分为三种情况:1、释放后与前面的空闲分区合并;2、释放后与后面的空闲分区合并;3、释放后与前面后面的空闲分区合并。不过概括起来就是两个,前面的判断就是空闲分区的结束地址是否和当前作业的起始地址一样,后面的判断就是空闲分区的起始地址是否和当前作业的结束地址一样。

    排序函数就是分别处理空闲分区的三种情况。FF首次适应算法,所以分区的排序方式应该是按照起始地址排序。BF最佳适应算法,按照空闲分区从小到大的顺序进行排序。WF与最佳适应算法的排序方法刚好相反。

    实验代码

    # -*- coding: utf-8 -*-
    # @Author: wfy
    # @Date:   2020-05-03 11:07:17
    # @Last Modified by:   wfy
    # @Last Modified time: 2020-05-04 09:09:20
    
    import matplotlib.pyplot as plt
    import numpy as np
    
    
    class Solution(object):
        """docstring for Solution"""
    
        def __init__(self, name, size):
            super(Solution, self).__init__()
            self.name = name
            self.size = size
            self.start = None
            self.end = None
    
    
    class Memory(object):
        """docstring for Memory"""
    
        def __init__(self, size, method):
            super(Memory, self).__init__()
            self.size = size
            self.had_free = []
            self.works = []
            self.free = [{'start': 0, 'end': size, 'size': size}]
            self.method = method
            self.speed = 0.5
    
        def find_work(self, work):
            names = [i.name for i in self.works]
            return True if work.name in names else False
    
        def get_work(self, work):
            if self.find_work(work):
                return exec("print('error 作业已存在')")
            work = self.update(work)
            if work is not None:
                self.works.append(work)
    
        def free_work(self, work):
            if not self.find_work(work):
                return exec("print('error 没有该作业')")
            for i in range(len(self.works)):
                if self.works[i].name == work.name:
                    work = self.works[i]
                    self.works.pop(i)
                    break
            self.update_space(work)
    
        def update_space(self, work):
            '''合并空闲空间'''
            self.had_free.append(work)
            # 需要合并
            i = 0
            while self.free and i < len(self.free):
                # 前面有空间
                if self.free[i]['end'] == work.start:
                    work.start = self.free[i]['start']
                    self.free.pop(i)
                    i = 0
                i += 1
            i = 0
            while self.free and i < len(self.free):
                # 后面有空间
                if work.end == self.free[i]['start']:
                    work.end = self.free[i]['end']
                    self.free.pop(i)
                i += 1
            self.free.append({'start': work.start, 'end': work.end,
                              'size': work.end - work.start})
            self.free.sort(key=self.sort_methods())
    
        def sort_methods(self):
            if self.method.lower() in ['ff']:
                return lambda x: x['start']
            if self.method.lower() in ['bf']:
                return lambda x: x['size']
            return lambda x: (-x['size'])
    
        def put(self):
            space = []
            print("-"*11 + "作业表" + "-" * 11)
            print("名称  大小   起始地址  结束地址")
            for i in range(len(self.works)):
                space.append(
                    {'start': self.works[i].start, 'end': self.works[i].end, 'size': self.works[i].size, 'free': False})
                print("{:<6}{:<6}{:<10}{:<10}".format(
                    self.works[i].name, self.works[i].size, self.works[i].start, self.works[i].end))
    
            print("-"*11 + "空闲区表" + "-" * 11)
            print("序号  大小   起始地址  结束地址")
            for i in range(len(self.free)):
                space.append({'start': self.free[i]['start'], 'end': self.free[i]
                              ['end'], 'size': self.free[i]['size'], 'free': True})
                print("{:<6}{:<6}{:<10}{:<10}".format(
                    i, self.free[i]['size'], self.free[i]['start'], self.free[i]['end']))
            print('*' * 30)
            space.sort(key=lambda x: x['start'])
            for tmp in space:
                print("-"*20 + "——————>" + str(tmp['start']))
                if tmp['free']:
                    print('|                   |')
                    print('|       ' + 'free' + '        |——————>空闲区')
                    print('|                   |')
                else:
                    print('|···················|')
                    print('|·······' + 'busy' + '········|——————>作业使用')
                    print('|···················|')
            print("-"*20 + "——————>" + str(self.size))
    
        def update(self, work):
            '''新增作业'''
            for i in range(len(self.free)):
                if work.size <= self.free[i]['size']:
                    # 更新空闲区表
                    self.free[i]['size'] -= work.size
                    work.start = self.free[i]['start']
                    work.end = work.start + work.size
                    self.free[i]['start'] = work.end
                    if self.free[i]['size'] == 0:
                        self.free.pop(i)
                    return work
            else:
                print("没有足够的空闲空间")
                return None
    
        def get_y_ticks(self):
            pass
    
        def init_image(self):
            fig = plt.figure('lab_three', figsize=(4.5, 7))
            plt.title('the lab of memory')
            plt.xticks([])
            plt.yticks([])
    
        def ani_fun(self, x1, x2, y1, y2):
            '''补帧'''
            x = np.linspace(x1, x2, 30)
            y = np.linspace(y1, y2, 30)
            for i in range(29):
                plt.plot([x[i], x[i + 1]], [y[i], y[i + 1]], color='k')
                plt.pause(0.005)
    
        def drow_image(self):
            plt.plot([120, 120], [0, 0])
            for work in self.works:
                # right down left top
                x = [0, 100, 100, 0, 0]
                y = [work.start, work.start, work.end, work.end, work.start]
                self.ani_fun(0, 100, work.start, work.start)
                self.ani_fun(100, 100, work.start, work.end)
                self.ani_fun(100, 0, work.end, work.end)
                self.ani_fun(0, 0, work.end, work.start)
                plt.fill(x, y, color='g', alpha=0.2)
                plt.text(50, (work.start + work.end) / 2, r'$work \ name:%s$' %
                         str(work.name), ha='center')
                plt.pause(self.speed)
                plt.annotate(r'$%d$' % work.start, xy=(100, work.start), xycoords='data', xytext=(+30, -30),
                             textcoords='offset points', fontsize=16, arrowprops=dict(arrowstyle='->', connectionstyle="arc3,rad=.2"))
                plt.pause(self.speed)
                plt.annotate(r'$%d$' % work.end, xy=(100, work.end), xycoords='data', xytext=(
                    30, -30), textcoords='offset points', fontsize=16, arrowprops=dict(arrowstyle='->', connectionstyle="arc3,rad=.2"))
                plt.pause(self.speed)
            for space in self.free:
                # right down left top
                self.ani_fun(0, 100, space['start'], space['start'])
                self.ani_fun(100, 100, space['start'], space['end'])
                self.ani_fun(100, 0, space['end'], space['end'])
                self.ani_fun(0, 0, space['end'], space['start'])
    
        def set_ax(self):
            ax = plt.gca()  
            ax.spines['right'].set_color('none')
            ax.spines['bottom'].set_color('none')
            ax.spines['top'].set_color('none')
            ax.spines['left'].set_color('none')
            ax.xaxis.set_ticks_position('top') 
            ax.invert_yaxis()
    
        def show_image(self):
            self.init_image()
            self.set_ax()
            self.drow_image()
            plt.savefig('show.png', dpi=300)
            plt.show()
    
    
    class CustomError(Exception):
        def __init__(self, ErrorInfo):
            super().__init__(self)  # 初始化父类
            self.errorinfo = ErrorInfo
    
        def __str__(self):
            return self.errorinfo
    
    
    if __name__ == '__main__':
        while True:
            try:
                size = int(input('请输入合法内存整数大小\n'))
                method = input('请输入需要执行的算法:FF、BF、WF.不区分大小写\n')
                if method.lower() not in ['ff', 'bf', 'wf']:
                    raise CustomError("唔,输入的方法不正确哦。")
                memory = Memory(size, method)
            except Exception as e:
                print("执行错误:", e)
            else:
                print("内存生成成功")
                break
        if input('是否需要使用模拟数据:y/n\n') in ['y']:
            memory.get_work(Solution(0, 300))
            memory.get_work(Solution(1, 100))
            memory.free_work(Solution(0, 300))
            memory.get_work(Solution(2, 150))
            memory.get_work(Solution(3, 30))
            memory.get_work(Solution(4, 40))
            memory.get_work(Solution(5, 60))
            memory.free_work(Solution(3, 30))
            memory.put()
            memory.show_image()
            exit()
        while True:
            print('1:申请内存\t\n2:释放内存\t\n3:手动打表\t\n4:图形展示\t\n5:退出\n')
            flag = input('请输入执行的编号')
            if flag == '1':
                name = input('请输入作业名字\n')
                size = int(input('请输入作业整数大小'))
                memory.get_work(Solution(name, size))
            elif flag == '2':
                name = input('请输入释放的作业名')
                memory.free_work(Solution(name, 0))
            elif flag == '3':
                memory.put()
            elif flag == '4':
                memory.show_image()
            elif flag == '5':
                break
            else:
                print('输入的内容不合法,请重新输入')
                continue
    
    
    展开全文
  • mem.c //源代码文件 mem.exe //演示程序文件
  • 操作系统实验,动态分区存储管理,使用最佳适应算法,内存的分配和回收
  • 深入了解动态分区存储管理方式主存分配回收的实现。 二.实验要求 1.使用动态分区存储管理方式分配回收内存。 2.使用最优适应算法完成主存空间的分配。 3.输出空闲表,分配表,内存的分配情况。 三.实验设计 ...
  • 操作系统 动态分区存储管理 实验要求 通过编写动态分区存储管理的模拟程序,加深对操作系统存储管理功能中的动态分区管理方式、空闲分区表等相应知识的理解。 实验内容 实现动态分区存储管理方式下存储空间的分配和...
  • 分区存储管理又有三种不同的方式:静态分区、可变分区、可重定位分区 。 静态分区 静态分区存储管理是预先把可分配的主存储器空间分割成若干个连续区域,每个区域的大小可以相同,也可以不同。为了说明各分区的...
  • 操作系统实验三 动态分区存储管理

    千次阅读 2020-05-08 20:32:23
    任务:用高级语言模拟实现动态分区存储管理。 二、内容、要求与安排 1、实验内容 分区分配算法至少实现首次适应算法、最佳适应算法和最坏适应算法中的至少一种。熟悉并掌握各种算法的空闲区组织方式。 分区的初始化...
  • 动态分区存储管理.docx
  • 标准 实验五 动态分区存储管理模拟 一实验目的 深入了解可变分区存储管理方式主存分配回收的实现 二实验预备知识 可变分区存储管理方式不预先将主存划分成几个区域 而把主存除操作系统 占用区域外的空间看作一个大的...
  • 操作系统中动态分区存储管理方式的模拟的详细讲解。包括思想,代码的具体实现等。
  • 一设计任务 完成存储器动态分区分配算法的模拟实现 二设计思想 在对数据结构有一定掌握程度的情况下设计合理的数据结构来描述存 储空间实现分区存储管理的内存分配功能 应该选择最合适的适应算法 (首 次适应算法最佳...
  • 可变式分区存储管理: 通过文件操作读取空闲区表(包含空闲区的起始地址和长度),通过用户选择分配/回收内存,回收的内存如果和空闲区表的内存块相邻,则进行合并 注:解决方案中带有data.txt文件,并在代码中指定...
  • 掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程 实验原理 建立两张表空闲表和已分配表分别将未分配的作业和已分配好的作业放入其中当要装入一个作业时从空闲区表中查找标志为未分配...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 231,834
精华内容 92,733
关键字:

动态分区存储管理