xiaing_log 2016-05-02 06:37 采纳率: 40%
浏览 1645

操作系统 内存分配 请求帮助

内存管理是所有操作系统必备的功能。为深入研究内存管理功能、实现内存的有效使用,某研究小组计划开发一个实验性内存管理器,实现对内存的分配、释放和整理。对应的接口为 new 、 delete 和 defrag ,使用语法为:
new size :分配 size 字节大小的内存块,返回该内存块的句柄 handle , size 为正整数;
new start size :同 new size ,从指定首地址 start 处分配 size 字节大小的内存块;
delete handle :释放句柄 handle 指向的内存块;
defrag :整理内存碎片,将所有已分配内存块按地址从低到高的顺序迁移,使空闲内存碎片在高地址端拼接在一起;

初始内存为 initSize 字节大小的整片空闲内存,编号为 1 到 initSize 。
new size 操作中,若存在不小于 size 的连续空闲内存,则按照小地址优先的原则从空闲内存区域中分配 size 大小的内存块,标记该内存块状态为已分配,并返回指向该内存块的句柄。若无法分配,则返回 NULL 。
new start size 操作与 new size 类似,但分配的起始位置由 start 指定。
delete handle 操作释放由 handle 标记的内存块,标记被释放的内存状态为空闲。若 handle 为无效句柄,则返回 ILLEGAL_OPERATION 。
defrag 完成内存整理工作,无返回值。

根据设计,每次成功内存分配返回的句柄为一个正整数,从 1 开始,依次计数。失败的存储分配操作不影响计数。

请帮助编写上述内存管理程序,并输出 new 操作的返回值。对于操作失败的 delete 操作,请输出 ILLEGAL_OPERATION 。本程序编写不限制函数使用。

输入
输入数据的第一行为两个正整数 T 和 MaxMem ( 1<=T<=10000, 1<=MaxMem<=10000 ),其中 T 为开展的内存操作数, MaxMem 为初始内存大小(单位为字节)。
其后有 T 行操作指令,如题面所述。

输出
按操作顺序输出操作结果。对每个成 new 操作,将其返回句柄值单独输出一行,失败输出 NULL 。若 delete 操作失败,输出 ILLEGAL_OPERATION 。

样例输入
25 1000
new 73
new 74
new 814 55
delete 1
new 989 10
delete -22233
new 76
defrag
new 93
new 20
new 43
defrag
new 989 10
delete 5
delete -1
new 989 110
defrag
new 50
new 1001
defrag
new 220
new 43 85
defrag
delete 10
new 49

样例输出
1
2
3
4
ILLEGAL_OPERATION
5
6
7
8
9
ILLEGAL_OPERATION
NULL
10
NULL
11
NULL
12

可以用Java写也可以用c/c++
我是用java写的,但是只能通过上面的测试用例,还有两个用例是保密的,我也不知的是什么样的输入和输出。求帮忙
我的代码:

import java.util.LinkedList;
import java.util.Scanner;

public class Main {

    private static int[] mm;
    private static int count;
    private static LinkedList<Node> part;//空闲分区表
    private static LinkedList<Node> reqd;//已分配的内存
    private static int maxMem;

    private static class Node {
        int start;
        int end;
        int size;
        int idx;

        public Node() {
        }

        public Node(int start, int end, int size, int idx) {
            this.end = end;
            this.size = size;
            this.start = start;
            this.idx = idx;
        }

        public Node clon() {
            return new Node(this.start, this.end, this.size, this.idx);
        }
    }
//请求指定大小内存,返回一个句柄
    private static int mm_require(int size) {
        if (size <= 0)
            return -1;
        for (Node p : part) {
            if (p.size >= size) {
                p.size -= size;
                Node r = new Node();
                r.start = p.start;
                r.end = p.start + size - 1;
                r.size = size;
                r.idx = ++count;
                reqd.add(r);
                if (p.size == 0) {
                    part.remove(p);
                } else {
                    p.start += size;
                }
                return r.idx;
            }
        }
        return -1;
    }
//从某一位置开始分配请求大小的内存
    private static int mm_require(int start, int size) {
        int id = 0;
        if (start < 0 || size <= 0)
            return -1;
        for (Node p : part) {
            if (p.start <= start && start + size - 1 <= p.end) {
                Node r = new Node();
                r.start = start;
                r.end = start + size - 1;
                r.size = size;
                r.idx = ++count;
                reqd.add(r);
                if (p.start == start) {
                    p.size -= size;
                    if (p.size == 0) {
                        part.remove(p);
                    } else {
                        p.start += size;
                    }
                } else {
                    int tend = p.end;
                    p.end = start - 1;
                    p.size = p.end - p.start + 1;
                    if (start + size - 1 != p.end) {
                        Node temp = new Node();
                        temp.start = start + size;
                        temp.end = tend;
                        temp.size = temp.end - temp.start + 1;
                        part.add(id + 1, temp);
                    }
                }
                return r.idx;
            }
            id++;
        }
        return -1;
    }
//释放句柄指向的内存空间
    private static boolean mm_release(int handle) {
        for (Node r : reqd) {
            if (r.idx == handle) {
                reqd.remove(r);
                for (int i = 0; i < part.size(); i++) {
                    Node p = part.get(i);
                    if (p.end + 1 == r.start) {
                        p.end = r.end;
                        p.size = p.end - p.start + 1;
                        initpart();
                        return true;
                    } else if (r.end + 1 == p.start) {
                        p.start = r.start;
                        // defrag();
                        return true;
                    }
                }
                Node temp = new Node();
                temp.start = r.start;
                temp.end = r.end;
                temp.size = r.size;
                for (int j = 0; j < part.size(); j++) {
                    if (temp.start < part.get(j).start) {
                        part.add(j, temp);
                        break;
                    }
                }
                return true;
            }
        }
        return false;
    }
//碎片整理
    private static void defrag() {
        Node temp = new Node();
        for (Node p : part) {
            temp.size += p.size;
        }
        temp.end = maxMem - 1;
        temp.start = maxMem - temp.size;
        part.clear();
        part.add(temp);
        LinkedList<Node> newreq = new LinkedList<Node>();
        for (int i = 1; i < reqd.size(); i++) {
            for (int j = i + 1; j <= reqd.size(); j++) {
                Node temp1 = reqd.get(i - 1);
                Node temp2 = reqd.get(j - 1);
                if (temp1.start > temp2.start) {
                    Node clon = temp1.clon();
                    temp1.idx = temp2.idx;
                    temp1.end = temp2.end;
                    temp1.size = temp2.size;
                    temp1.start = temp2.start;
                    temp2.idx = clon.idx;
                    temp2.end = clon.end;
                    temp2.size = clon.size;
                    temp2.start = clon.start;
                }
            }
        }
        Node firstr = new Node();
        firstr.start = 0;
        for (Node p : reqd) {
            Node t = new Node();
            t.start = firstr.start;
            t.end = firstr.start + p.size - 1;
            t.size = p.size;
            t.idx = p.idx;
            newreq.add(t);
            firstr.start += p.size;
        }
        reqd = newreq;
    }

    private static void initpart() {
        for (int j = 0; j < part.size() - 1; j++) {
            Node temp1 = part.get(j);
            Node temp2 = part.get(j + 1);
            if (temp1.end + 1 == temp2.start) {
                part.remove(temp2);
                temp1.end = temp2.end;
            }
        }
    }

    private static void init() {
        part = new LinkedList<Node>();
        reqd = new LinkedList<Node>();
        Node first = new Node();
        first.start = 0;
        first.end = maxMem - 1;
        first.size = maxMem;
        first.idx = 0;
        part.add(first);
        count = 0;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        maxMem = in.nextInt();
        mm = new int[maxMem];
        init();
        while (t > 0) {
            String instruct = in.nextLine();
            if (!instruct.equals("")) {
                int n1 = instruct.indexOf(" ");
                if (n1 != -1) {
                    String op = instruct.substring(0, n1);
                    if ("new".equals(op)) {
                        int n2 = instruct.indexOf(" ", n1 + 1);
                        if (n2 != -1) {
                            int start = Integer.valueOf(instruct.substring(
                                    n1 + 1, n2));
                            int size = Integer.valueOf(instruct
                                    .substring(n2 + 1));
                            int handle = mm_require(start, size);
                            if (handle != -1)
                                System.out.println(handle);
                            else
                                System.out.println("NULL");
                        } else {
                            int size = Integer.valueOf(instruct
                                    .substring(n1 + 1));
                            int handle = mm_require(size);
                            if (handle != -1)
                                System.out.println(handle);
                            else
                                System.out.println("NULL");
                        }
                    } else if ("delete".equals(op)) {
                        int handle = Integer
                                .valueOf(instruct.substring(n1 + 1));
                        if (!mm_release(handle)) {
                            System.out.println("ILLEGAL_OPERATION");
                        }
                    }
                } else {
                    defrag();
                }
                t--;
            }
        }
    }
}

  • 写回答

0条回答

    报告相同问题?

    悬赏问题

    • ¥20 iqoo11 如何下载安装工程模式
    • ¥15 本题的答案是不是有问题
    • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
    • ¥15 C++使用Gunplot
    • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
    • ¥15 matlab数字图像处理频率域滤波
    • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
    • ¥15 ELGamal和paillier计算效率谁快?
    • ¥15 蓝桥杯单片机第十三届第一场,整点继电器吸合,5s后断开出现了问题
    • ¥15 file converter 转换格式失败 报错 Error marking filters as finished,如何解决?