1實驗?zāi)康?/p>

（1）了解動態(tài)分區(qū)分配方式中使用的數(shù)據(jù)結(jié)構(gòu)和分配算法

（2）加深對動態(tài)分區(qū)存儲管理方式及其實現(xiàn)過程的理解。

2實驗內(nèi)容

（1）分別實現(xiàn)采用首次適應(yīng)算法和最佳適應(yīng)算法的動態(tài)分區(qū)分配過程alloc()和回收過程free()。其中，空閑分區(qū)通過空閑分區(qū)鏈來管理：在進(jìn)行內(nèi)存分配時，系統(tǒng)優(yōu)先使用空閑區(qū)低端的空間。

（2）假設(shè)初始狀態(tài)下，可用的內(nèi)存空間為640KB，并有下列的請求序列：

•作業(yè)1申請130KB。

•作業(yè)2申請60KB。

•作業(yè)3申請100KB。

•作業(yè)2釋放60KB。

•作業(yè)4申請200KB。

•作業(yè)3釋放100KB。

•作業(yè)1釋放130KB。

•作業(yè)5申請140KB。

•作業(yè)6申請60KB。

•作業(yè)7申請50KB。

•作業(yè)6釋放60KB。

分別采用首次適應(yīng)算法和最佳適應(yīng)算法，對內(nèi)存塊進(jìn)行分配和回收，要求每次分配和回收后顯示出空閑分區(qū)鏈的情況。

3實驗結(jié)果（給出編寫的程序源代碼和運行結(jié)果的截圖）

 這是操作系統(tǒng)實驗老師出的一個題目，要求模擬動態(tài)分區(qū)的內(nèi)存分配，上面是題目的要求。對于這道題，我自己并沒有獨立實現(xiàn)，在網(wǎng)上找了源碼，終于弄懂了，然后自己寫了最佳適應(yīng)算法，這里我就說一下怎么來解這道題。

1.首先，需要聲明占用內(nèi)存的進(jìn)程的各個屬性。你需要name來表示該進(jìn)程的名字、startAddress表示進(jìn)程所占內(nèi)存的起始地址、length表示進(jìn)程所占大小、flag表示用于標(biāo)記該內(nèi)存是否釋放。

2.然后需要分配算法和回收的算法。對于分配，因為存儲的方式是鏈?zhǔn)酱鎯Φ?，對于一個將要分配進(jìn)來的進(jìn)程，系統(tǒng)會將第一個適合該進(jìn)程的內(nèi)存分出足夠的大小分配給該進(jìn)程，這就是首次適應(yīng)算法。而我寫的最佳適應(yīng)算法的思路是這樣的：每次分配前，就對內(nèi)存中的所有片空間進(jìn)行排序，這樣每次分配進(jìn)來的內(nèi)存都會是最適合的內(nèi)存空間。

3.有分配就會有回收，回收分為幾種情況，需要注意的就是在回收過程中，當(dāng)相鄰的有空閑分區(qū)時，需要進(jìn)行合并

下面是源代碼：

進(jìn)程類Date.class

package memory;public class Date {    String name;        //進(jìn)程名稱    int startAddress;    //起始地址    int length;            //占用大小長度    int flag;            //是否已使用    public Date(String name, int startAddress, int length, int flag) {        super();        this.name = name;        this.startAddress = startAddress;        this.length = length;        this.flag = flag;    }    public Date() {        super();    }    @Override    public String toString() {        return "Date [name=" + name + ", startAddress=" + startAddress                + ", length=" + length + ", flag=" + flag + "]";    }}

Main.class

package memory;import java.util.ArrayList;import java.util.Collection;import java.util.Scanner;public class Main {    static ArrayList list = new ArrayList();    //建立一個鏈表，來表示內(nèi)存的使用情況    static Scanner sc = new Scanner(System.in);        //首次適應(yīng)算法    static void fenPei(){        Date date = new Date();        System.out.);        date.name = sc.next();        System.out.println("輸入分配的內(nèi)存大?。?);        date.length = sc.nextInt();        int i;        for ( i = 0; i < list.size(); i++) {            if (date.length <= ((Date)list.get(i)).length && ((Date)list.get(i)).flag == 0) {                //當(dāng)有適合的內(nèi)存，且未被使用                break;            }        }        if (i == list.size()) {            System.out.println("沒有足夠的內(nèi)存進(jìn)行分配");        }        if (((Date)list.get(i)).length - date.length <= 4 && i != list.size() - 1 ) {//當(dāng)內(nèi)存比進(jìn)程所占的內(nèi)存在4kB以內(nèi)的話，就不進(jìn)行分片            ((Date)list.get(i)).name = date.name;            ((Date)list.get(i)).flag = 1;        }else {            //分片分配內(nèi)存            date.flag = 1;            ((Date)list.get(i)).length -= date.length;            date.startAddress = ((Date)list.get(i)).startAddress;            ((Date)list.get(i)).startAddress += date.length;            list.add(i, date);        }    }    //最佳適應(yīng)算法    static void fenPei1(){        Date date = new Date();        System.out.println("輸入請求分配進(jìn)程的名稱：");        date.name = sc.next();        System.out.println("輸入分配的內(nèi)存大?。?);        date.length = sc.nextInt();        int m, j;        Date target = new Date();            for (m = 1; m < list.size()-1; m++){                j = m;                target.name = ((Date)list.get(m)).name;                target.flag = ((Date)list.get(m)).flag;                target.length = ((Date)list.get(m)).length;                target.startAddress = ((Date)list.get(m)).startAddress;                while(j>0 && ((Date)list.get(j-1)).length>target.length){                                        ((Date)list.get(j)).name = ((Date)list.get(j-1)).name;                    ((Date)list.get(j)).flag = ((Date)list.get(j-1)).flag;                    ((Date)list.get(j)).length = ((Date)list.get(j-1)).length;                    ((Date)list.get(j)).startAddress = ((Date)list.get(j-1)).startAddress + ((Date)list.get(j)).length;                    j--;                }                ((Date)list.get(j)).name = target.name;                ((Date)list.get(j)).length = target.length;                ((Date)list.get(j)).flag = target.flag;                ((Date)list.get(j)).startAddress = target.startAddress-((Date)list.get(j+1)).length;                            }            int i;            for ( i = 0; i < list.size(); i++) {                if (date.length <= ((Date)list.get(i)).length && ((Date)list.get(i)).flag == 0) {                    //當(dāng)有適合的內(nèi)存，且未被使用                    break;                }            }            if (i == list.size()) {                System.out.println("沒有足夠的內(nèi)存進(jìn)行分配");            }            if (((Date)list.get(i)).length - date.length <= 4 && i != list.size() - 1 ) {                ((Date)list.get(i)).name = date.name;                ((Date)list.get(i)).flag = 1;            }else {                //分片分配內(nèi)存                date.flag = 1;                ((Date)list.get(i)).length -= date.length;                date.startAddress = ((Date)list.get(i)).startAddress;                ((Date)list.get(i)).startAddress += date.length;                list.add(i, date);            }    }    //回收部分    static void huiShou(){        System.out.println("請輸入要回收的進(jìn)程：");        String name = sc.next();        int i;        for ( i = 0; i < list.size(); i++) {            if (name.equals(((Date)list.get(i)).name)) {                break;            }        }        if (i == list.size()) {            System.out.println("沒有找到該進(jìn)程。");            return;        }        System.out.println("找到的是====>"+ i);        int hui = ((Date)list.get(i)).length;        if (i == 0 && ((Date)list.get(i+1)).flag == 0) {        //回收第一個進(jìn)程，且第二個內(nèi)存位置空閑，合并這兩者            ((Date)list.get(i)).flag = 0;            ((Date)list.get(i)).length += ((Date)list.get(i+1)).length;            ((Date)list.get(i)).name = "";            list.remove(1);        }else if (i == 0 && ((Date)list.get(i+1)).flag == 1) {    //回收第一個進(jìn)程，但第二個內(nèi)存位置被占用            ((Date)list.get(i)).name = "";            ((Date)list.get(i)).flag = 0;        }else if (((Date)list.get(i-1)).flag == 0 && ((Date)list.get(i+1)).flag == 0) {//回收位置的進(jìn)程左右兩邊的內(nèi)存空間都空閑            ((Date)list.get(i)).name = "";            ((Date)list.get(i)).flag = 0;            ((Date)list.get(i-1)).length += ((Date)list.get(i)).length + ((Date)list.get(i+1)).length;             list.remove(i);            list.remove(i+1);        }else if (((Date)list.get(i-1)).flag == 0 && ((Date)list.get(i+1)).flag == 1) {//回收位置左邊的內(nèi)存空閑，而右邊的內(nèi)存被占用            ((Date)list.get(i)).name = "";            ((Date)list.get(i)).flag = 0;            ((Date)list.get(i-1)).length += ((Date)list.get(i)).length;            list.remove(i);        }else if (((Date)list.get(i-1)).flag == 1 && ((Date)list.get(i+1)).flag == 0) {//回收位置右邊的內(nèi)存空閑，而左邊的內(nèi)存被占用            ((Date)list.get(i)).name = "";            ((Date)list.get(i)).flag = 0;            ((Date)list.get(i)).length += ((Date)list.get(i+1)).length;            list.remove(i+1);        }else {//左右兩邊的內(nèi)存都被占用            ((Date)list.get(i)).name = "";            ((Date)list.get(i)).flag = 0;        }        System.out.println("成功回收進(jìn)程"+i+"的"+hui+"kb的空間");    }        static void disPlay(){        System.out.println("=============================================");        for (int i = 0; i < list.size(); i++) {            System.out.println(list.get(i));        }        System.out.println("=============================================");    }        public static void main(String[] args){        Date date = new Date("", 0, 640, 0);        list.add(date);        int choice0;        int choice1;        while(true){            System.out.println("請選擇：內(nèi)存分配方式");            System.out.println("1.首次適應(yīng)算法");            System.out.println("2.最佳適應(yīng)算法");            System.out.println("3.退出");            choice0 = sc.nextInt();            switch (choice0) {            case 1:                while(true){                System.out.println("請選擇：");                System.out.println("1.分配內(nèi)存");                System.out.println("2.回收內(nèi)存");                System.out.println("3.查看內(nèi)存");                System.out.println("4.退出");                choice1 = sc.nextInt();                switch (choice1) {                case 1:                    fenPei();                    break;                case 2:                    huiShou();                    break;                case 3:                    disPlay();                    break;                case 4:                    System.exit(0);                    break;                default:                    System.out.println("請正確輸入");                    break;                }                }            case 2:                while(true){                    System.out.println("請選擇：");                    System.out.println("1.分配內(nèi)存");                    System.out.println("2.回收內(nèi)存");                    System.out.println("3.查看內(nèi)存");                    System.out.println("4.退出");                    choice1 = sc.nextInt();                    switch (choice1) {                    case 1:                        fenPei1();                        break;                    case 2:                        huiShou();                        break;                    case 3:                        disPlay();                        break;                    case 4:                        System.exit(0);                        break;                    default:                        System.out.println("請正確輸入");                        break;                    }                    }            case 3:                    System.exit(0);                break;            default:                System.out.println("請正確輸入：");            }        }            }}