1、实验目的

了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。

2、实验内容

1. 用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。
2. 假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：
   作业1申请130KB。
作业2申请60KB。
作业3申请100KB。
作业2释放60KB。
作业4申请200KB。
作业3释放100KB。
作业1释放130KB。
作业5申请140KB。
作业6申请60KB。
作业7申请50KB。
作业6释放60KB。

请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。

实验代码

#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;
}