动态分区存储管理

以你之姓@ 2022-02-03 21:21 205阅读 0赞

# 动态分区存储管理 #

## 一，实验目的： ##

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

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

## 二、实验内容： ##

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

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

## 三、实验代码 ##

最坏与最佳是一个比较器的问题，所以我写了比较器，没有写相关算法。

import java.util.*;
    
    public class DistributeMemo {
        private static LinkedList<Memo> freeMemo;
        private static HashMap<String, Memo> busyMemo;
        private static Scanner scanner = new Scanner(System.in);
        private static int allSize = 0;
    
        public static void main(String[] args) {
            System.out.println("请选择方式");
            System.out.println("1. 首次分配");
            System.out.println("2. 最佳适应");
            method = scanner.nextInt();
            freeMemo = new LinkedList<>();
            busyMemo = new HashMap<>();
            // 用户输入初始大小.
            inputAllMemo();
            // 开始模拟过程
            beginWork();
        }
    
        private static void beginWork() {
            int flag ;
            while (true) {
                System.out.println("\t\t\t\t\t\t\t\t\t************************\t\t\t");
                System.out.println("\t\t\t\t\t\t\t\t\t*  1. 开始一个新的作业  *\t\t\t");
                System.out.println("\t\t\t\t\t\t\t\t\t*  2. 回收一个旧的空间  *\t\t\t");
                System.out.println("\t\t\t\t\t\t\t\t\t*  3. 展示当前内存情况  *\t\t\t");
                System.out.println("\t\t\t\t\t\t\t\t\t* -1. ----停止模拟----  *\t\t\t");
                System.out.println("\t\t\t\t\t\t\t\t\t************************\t\t\t");
                try {
                    flag = scanner.nextInt();
                } catch (InputMismatchException e) {
                    System.out.println("输入不合法，请重新输入");
                    beginWork();
                    return;
                }
                scanner.nextLine();
                switch (flag) {
                    case 1:
                        getMemo();
                        break;
                    case 2:
                        freeMemo();
                        break;
                    case 3:
                        showMemo();
                        break;
                    case -1:
                        freeAll();
                        return;
                    default:
                        System.out.println("-------------输入不合法-------------");
                }
            }
        }
    
        /**
         * 最佳适应
         */
        private static boolean bestFit(String name, int size) {
            // 对链表排序
            freeMemo.sort(new BestComparator());
            // 遍历freeMemo, 将第一个满足条件的节点的内存分配一部分给新来的作业.
            return findFirstFreeMemo(name, size);
        }
    
        /**
         * 结束分配
         */
        private static void freeAll() {
            freeMemo = null;
            busyMemo = null;
            System.out.println("释放所有内存");
            System.out.println("释放完成");
        }
    
        /**
         * 首次适应
         */
        private static void getMemo() {
            System.out.println("输入作业名   期望内存大小");
            String content = scanner.nextLine();
            String[] contents = content.split(" ");
            if (contents.length != 2) {
                System.out.println("您输入的内容不合法，请重新输入");
                getMemo();
            } else {
                String name = contents[0];
                if (busyMemo.get(name) != null) {
                    System.out.println("您输入的作业名已存在，请重新输入");
                    System.out.println("-----------------------------");
                    getMemo();
                } else {
                    int size = Integer.parseInt(contents[1]);
                    boolean success;
                    if (method == 1) {
                        success = findFirstFreeMemo(name, size);
                    } else {
                        success = bestFit(name, size);
                    }
                    if (success) {
                        System.out.println("分配成功");
                    } else {
                        System.out.println("无可用内存空间");
                    }
                }
            }
        }
    
        private static boolean findFirstFreeMemo(String name, int size) {
            // 遍历freeMemo, 将第一个满足条件的节点的内存分配一部分给新来的作业.
            Iterator<Memo> it = freeMemo.iterator();
            while (it.hasNext()) {
                Memo val = it.next();
                if (val.size >= size) {
                    // 合适， 开始分配内存
                    busyMemo.put(name, new Memo(val.head, size));
                    if (val.size == size) {
                        // 移除这个空内存
                        it.remove();
                    } else {
                        // 改变空闲内存的size和起始位置.
                        val.size = val.size - size;
                        val.head = val.head + size;
                    }
                    return true;
                }
            }
            return false;
        }
    
        private static int method = 1;
    
        // 用户输入初始分区的大小,起始地址为0
        private static void inputAllMemo() {
            System.out.println("请输入总内存的大小(整数)");
            allSize = scanner.nextInt();
            scanner.nextLine();
            // 先初始化
            freeMemo.clear();
            freeMemo.add(new Memo(0, allSize));
        }
    
        private static void showMemo() {
            // 将busy和free的memo全部取出放入一个数组内.
            int size = busyMemo.size() + freeMemo.size();
            Memo[] allMemo = new Memo[size];
            int i = 0;
            HashMap<Memo, String> name = new HashMap<>();
            for (String nm : busyMemo.keySet()) {
                Memo m = busyMemo.get(nm);
                m.free = false;
                allMemo[i++] = m;
                name.put(m, nm);
            }
            for (Memo m : freeMemo) {
                m.free = true;
                allMemo[i++] = m;
            }
            Arrays.sort(allMemo);
            // 此时有序.
            for (Memo memo : allMemo) {
                System.out.println(memo.head + "\t\t|----------------|");
                if (memo.free) {
                    System.out.println("\t\t|      Free      |" + "----->空闲内存");
                } else {
                    System.out.println("\t\t|      Busy      |" + "----->进程名：" + name.get(memo));
                }
                System.out.println("\t\t|                |");
            }
            System.out.println(allSize + "\t\t|----------------|");
    
        }
    
        // 释放进程作业存储空间
        private static void freeMemo() {
            // 从busy中移除内存，添加至free的头节点。
            System.out.println("请输入作业名");
            String name = scanner.nextLine();
            Memo newFreeMemo = busyMemo.get(name);
            if (newFreeMemo == null) {
                System.out.println("并不存在这个作业,返回主页面");
            } else {
                // 将其从busy中删除
                busyMemo.remove(name);
                // 合并前后空闲内存.
                // 遍历空闲内存，查看是否存在与新内存相连的内存块，如果有，则取出并合并.
                Iterator<Memo> it = freeMemo.iterator();
                while (it.hasNext()) {
                    Memo val = it.next();
                    // 先判断后一个内存空间
                    if (val.head == newFreeMemo.head + newFreeMemo.size) {
                        newFreeMemo.size += val.size;
                        it.remove();
                    }
                    // 判断是否是连续的前一个内存空间.
                    if (val.head + val.size == newFreeMemo.head) {
                        newFreeMemo.size += val.size;
                        newFreeMemo.head = val.head;
                        it.remove();
                    }
                }
                freeMemo.addFirst(newFreeMemo);
            }
        }
    
    }
    
    
    class Memo implements Comparable<Memo> {
        // 块的大小
        int size;
        // 起始地址
        int head;
    
        boolean free = true;
    
        Memo(int head, int size) {
            this.size = size;
            this.head = head;
        }
    
        @Override
        public int compareTo(Memo o) {
            return this.head - o.head;
        }
    }
    
    /**
     * 最佳适应的比较器
     */
    class BestComparator implements Comparator<Memo>{
        @Override
        public int compare(Memo o1, Memo o2) {
            return o2.size - o1.size;
        }
    }
    
    /**
     * 最坏适应的比较器
     */
    class wrostComparator implements Comparator<Memo> {
    
        @Override
        public int compare(Memo o1, Memo o2) {
            return o1.size - o2.size;
        }
    }