2 sinat 31488069 sinat_31488069 于 2016.05.02 14:37 提问

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

内存管理是所有操作系统必备的功能。为深入研究内存管理功能、实现内存的有效使用,某研究小组计划开发一个实验性内存管理器,实现对内存的分配、释放和整理。对应的接口为 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--;
            }
        }
    }
}

1个回答

CSDNXIAON
CSDNXIAON   2016.05.02 14:41

操作系统内存分配
操作系统的内存分配
2013.06.25《操作系统-内存分配》
----------------------同志你好,我是CSDN问答机器人小N,奉组织之命为你提供参考答案,编程尚未成功,同志仍需努力!

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!