1、實驗?zāi)康?/h1>

了解動態(tài)分區(qū)分配方式中使用的數(shù)據(jù)結(jié)構(gòu)和分配算法，并進(jìn)一步加深對動態(tài)分區(qū)存儲管理方式及其實現(xiàn)過程的理解。

2、實驗內(nèi)容

1. 用C語言分別實現(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ū)鏈的情況。

實驗代碼

#include <iostream>
#include <queue>
#include <set>
#include <iomanip>

using namespace std;
enum Unit {
    KB, MB
};
typedef int Addr;
Addr getAddr(int num, Unit unit) {
    return
    (unit == KB) ? (num) :
    (unit == MB) ? (num*1024) : 0;
}

struct mem_block {
    Addr start;
    Addr len;
    int task_id;
    mem_block(Addr start0, Addr len0, int task_id0):start(start0), len(len0), task_id(task_id0) {}
};

struct FF_cmp {
    bool operator() (mem_block a, mem_block b) {
        return a.start > b.start; //小頂堆
    }
};

struct BF_cmp {
    bool operator() (mem_block a, mem_block b) {
        return a.len > b.len; //小頂堆
    }
};

typedef priority_queue<mem_block, vector<mem_block>, FF_cmp> FF_Queue;
typedef priority_queue<mem_block, vector<mem_block>, BF_cmp> BF_Queue;


FF_Queue ffq;
BF_Queue bfq;
set<int> tasks;
void init() {
    ffq.push(mem_block(0,getAddr(640, KB), 0));
    bfq.push(mem_block(0,getAddr(640, KB), 0));
}
template<class T>
void merge_mem(T& q) {
    FF_Queue tq;
    while (!q.empty()) {
        tq.push(q.top());
        q.pop();
    }
    vector<mem_block> vt;
    while (!tq.empty()) {
        mem_block t = tq.top();
        tq.pop();
        while (!tq.empty() && tq.top().task_id == t.task_id) {
            t.len += tq.top().len;
            tq.pop();
        }
        vt.push_back(t);
    }
    for(auto item : vt) {
        q.push(item);
    }
}
template<class T>
void alloc_mem(T& q, int task_id, Addr num) {
    if (num <= 0) {
        return;
    }
    vector<mem_block> vt;
    while (!q.empty()) {
        mem_block t = q.top();
        q.pop();
        if (t.len >= num && t.task_id == 0) {
            q.push(mem_block(t.start, num, task_id));
            if (t.len > num) {
                q.push(mem_block(t.start +num, t.len - num, 0));
            }
            for(auto item : vt) {
                q.push(item);
            }
            merge_mem<T>(q);
            return;
        } else {
            vt.push_back(t);
        }
    }
    cout << "error no enough mem alloc" << endl;
    for(auto item : vt) {
        q.push(item);
    }
}

template<class T>
void free_mem(T& q, int task_id, Addr num) {
    if (num <= 0) {
        return;
    }
    vector<mem_block> vt;
    while (!q.empty()) {
        mem_block t = q.top();
        q.pop();
        if (t.task_id == task_id) {
            if(t.len >= num) {
                q.push(mem_block(t.start, num, 0));
                if (t.len > num) {
                    q.push(mem_block(t.start + num, t.len - num, task_id));
                }
            } else {
                num -= t.len;
                continue;
            }
            
            for(auto item : vt) {
                q.push(item);
            }
            merge_mem<T>(q);
            return;
        } else {
            vt.push_back(t);
        }
    }
    cout << "error no enough mem free" << endl;
    for(auto item : vt) {
        q.push(item);
    }
}
const int char_len = 8;
#define chart_item << "|" << setw(char_len) << left << setfill(' ')
#define chart_head << setw((char_len+1)*3+1) << left << setfill('-')
string itoa(int n) {
    string s;
    while (n) {
        s = char(n%10+'0') + s;
        n /= 10;
    }
    return s;
}
template<class T>
void show(T q) {
    T tq;
    while (!q.empty()) {
        tq.push(q.top());
        q.pop();
    }
    cout
    chart_head<<""<<endl
    chart_item << "start" << ""
    chart_item << "len" << ""
    chart_item << "task_id" << "|"<< endl
    chart_head<<""<<endl;
    while (!tq.empty()) {
        mem_block mb = tq.top();
        cout
        chart_item<< mb.start << ""
        chart_item<< mb.len << ""
        chart_item<< ((mb.task_id == 0) ? "spare" : itoa(mb.task_id)) << "|"<< endl;
        tq.pop();
    }
    cout
    chart_head<<""<<endl;
}
int main(int argc, const char * argv[]) {
    init();
    const int free = 0, alloc = 1;
    vector<vector<int>> reqs = {
        {1,130,alloc},
        {2,60, alloc},
        {3,100, alloc},
        {2,60,free},
        {4, 200, alloc},
        {3, 100, free},
        {1, 130, free},
        {5, 140, alloc},
        {6, 60, alloc},
        {7,50, alloc},
        {6, 60, free}
    };
    
    for(auto req : reqs) {
        if (req[2] == alloc) {
            alloc_mem<FF_Queue>(ffq,req[0], req[1]);
            alloc_mem<BF_Queue>(bfq,req[0], req[1]);
        } else if (req[2] == free) {
            free_mem<FF_Queue>(ffq,req[0], req[1]);
            free_mem<BF_Queue>(bfq,req[0], req[1]);
        } else {
            
        }
        cout << "FF" << endl;
        show<FF_Queue>(ffq);
        cout << "BF" << endl;
        show<BF_Queue>(bfq);
    }
    
    return 0;
}