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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
详解操作系统分配内存
计算机体系结构和内存层次 操作系统中内存的最小访问单位是 字节 ,也就是8bit。 通常我们所说的计算机系统是32位的总线,所谓的32位总线就是说一次读写可以从内存当中读或者写32位(也就是4字节)。 因为一次读写是32位,所以需要地址对齐,访问的时候不能从任意地方开始。 在CPU中可以看到高速缓存,由于指令执行和访问数据都需要从内存里读数据,如果此时有大量数据要读写而且会
操作系统实验之二--内存分配算法的模拟实现
发一些大三操作系统的实验代码吸引阅读量吧,当时做实验的时候看见网上很多人写的代码并不好,而且很多人都有错误的地方。如果好的话希望能点赞关注。 常见的内存分配算法有首次适应算法(First Fit,FF)、循环首次适应算法(Next Fit,NF)、最佳适应算法(Best Fit,BF)、最差适应算法(Worst Fit,WF),本实验中实现了这4种算法,使用C++语言实现。使用SIZ
操作系统内存分配算法
四种常见的内存分配算法,简要介绍其优缺点以及代码实现
操作系统-动态内存分配算法
内存分配算法 1、首次适应算法(FF) 2、循环首次适应算法(NF) 3、最佳适应算法(BF) 4、最坏适应算法(WF) 本程序使用前端技术实现(html+css+JavaScript)新建以下文件在同一目录:index.html、index.css、index.jsindex.css *{ margin: 0; padding: 0; }li{ list-styl
操作系统常见内存分配算法及优缺点
常见内存分配算法及优缺点如下:   (1)首次适应算法。使用该算法进行内存分配时,从空闲分区链首开始查找,直至找到一个能满足其大小需求的空闲分区为止。然后再按照作业的大小,从该分区中划出一块内存分配给请求者,余下的空闲分区仍留在空闲分区链中。   该算法倾向于使用内存中低地址部分的空闲分区,在高地址部分的空闲分区非常少被利用,从而保留了高地址部分的大空闲区。显然为以后到达的大作业分配大的内存空
操作系统内存分配
<br />内存分配原理<br /> <br />康  林  2011-1-12<br /> <br />W问:“K,知道,stl的list直接clear后怎样可以释放内存没!”<br />K答:“stl 中 list 的 clear 方法会自己释放自己分配的节点内存,但如果数据是用户用 new 产生的,那用户需要负责释放。”<br />W说:“我说的就是list自己分配的节点内存如何强行释放,它没有自己释放。刚才找了下,3.3以前的gcc会自己释放,3.4以后的就不会释放!”<br />K说:“有这事?它
操作系统的内存分配
首先看一下“基本的存储分配方式”种类:        1.  离散分配方式的出现   由于连续分配方式会形成许多内存碎片,虽可通过“紧凑”功能将碎片合并,但会付出很大开销。于是出现离散分配方式:将一个进程直接分散地装入到许多不相邻的内存分区中。        下面主要介绍“离散分配”三种方式的基本原理以及步骤: 2.  
操作系统内存分配算法模拟实现
掌握为实现多道程序并发执行,操作系统是如何通过作业调度选择作业进入内存。系统如何为进入内存的作业分配内存空间,实现多道作业同时驻留内存,就绪进程队列中的多个进程是如何以分式方式共享CPU,作业运行完成离开系统时,系统如何进行内存回收,计算进程周转时间。
操作系统 笔记(三)计算机体系结构,地址空间、连续内存分配(四)非连续内存分配:分段,分页
上一篇:操作系统from清华大学向勇,陈渝 笔记(二)操作系统的启动、中断、异常、系统调用 3-1 计算机体系结构&内存分层体系 3-2地址空间和地址生成 3-3连续内存分配:内存碎片与分区的动态分配 3-4 连续内存分配:压缩式/交换式碎片整理4-1 非连续内存分配:分段 页表-概述,TLB,二级页表,多级也比哦啊,反向页表
MFC实现操作系统四种内存分配算法的模拟
作为操作系统的期末作业,和大家分享一下操作系统内存分配算法基于MFC的可视化模拟,本人小菜鸟一只,欢迎大神指正,以后也希望能坚持下来写技术博客的习惯,不断总结不断积累,结交更多兴趣爱好相同的朋友和前辈。 ------------------------------------------------------------------------------------   正文-------