操作系统实验四——可变分区内存管理器设计与实现_可变分区存储管理的代码实现

操作系统实验四（可变分区内存管理器设计与实现）

一、 实验内容

可变分区内存管理器设计与实现

实验要求：

1. 进程数量4个以上
2. 按照首次适应模拟内存的分配；
3. 模拟内存的回收，回收时考虑分区的合并；
4. 挑战要求有碎片产生时，考虑碎片的整理。

二、 实验设计思想

（一）设计思路：

1.定义空闲区元素类型结构体FreeType，分别用整型变量length和base表示记录作业起始地址，用字符串类型变量state记录作业状态。在已分配表中state为作业名，未分配表中为空闲标志。
2.再定义作业类型变量JobType，包含结构体的长度length及作业名name。同时，
定义const int 全局变量MAX_BLOCKS用来初始化空闲区容量，初始值为120KB。
再使用vector容器来定义FreeType类型变量allocatedBlocks表示已分配表，freeBlocks表示空闲表。
3.首先主函数中调用InitialFreeArea()初始化空闲区，将内存空间设置为大小为120KB的freeBlocks类型元素加入到freeBlocks容器中，表示空闲区初始化。
4.再调用CreateTask()函数用来创建线程，模拟线程的运行，CreateTask()函数中用thread关键字来定义线程数组大小为5，创建5个线程传入ThreadTask函数名，表ThreadTask()示作业任务，模拟作业分配。内部使用互斥锁，保证临界资源的互斥，具体调用FristFit(user)最先适应分配算法，来对作业进行分配。
FristFit算法中，分以下步骤进行作业的分配工作：
（1）调用FindFreeBlock(user)函数，顺序查找空闲区表,找到第一个能满足作业要求的空闲区，若找到返回改空闲区在容器中的下标，否则返回-1表示未找到。
（2）找到该空闲区后，判断该空闲区与作业大小，若相等，则直接把它分给作业，否则
（3）分割这个空闲区,先将一部分分配给作业,即该空闲区表为空表，再将另一部分空闲区插入空闲区表中。之后再调整已分配区表，顺序查找已分配区空表目，把已分配区表中的一个空表目改为一个标志为某作业名的相应表目，若没有空表目则新建该元素，其起始地址和长度均来自空闲区表，并插入该已分配表中。
5.CreateTask()函数中再调用每个线程的join函数，以让主线程等待子线程完成。
6.之后，主函数中调用Recovery()函数，并传入作业名，用来模拟作业回收工作，
该函数中，分以下步骤进行作业的回收工作：
（1） 调用FindJob(string name)函数，在分配区根据寻该作业，若找到，返回该
业在已分配表中的下标，否则返回-1。
（2） 若找到该函数，首先，将已分配区表中相应表目的状态置成“空”，再调整相
应的未分配区表。
（3） 调用Merge()函数，判断是否需要合并，需要合并情况分为若释放区既有上邻
空闲区，又有下邻空闲区。将三个空闲区合并成一个大空闲区；若释放区只有上邻空闲区F1。则只修改空闲区F1大小；只有下邻空闲区，只修改该空闲区。三种情况。
（4） 若以上条件均不满足，则表示不需要合并，把空闲区表中的一个空表目改成
一个状态为“未分配”的相应表目。
7.主函数中调用Compaction()函数，即采用移动紧缩技术，来处理空闲分区中产生的“外碎片”。分以下步骤进行作业的移动紧缩工作：
（1） 倒序去除已分配区空表目。
（2） 已分配区作业按起始地址从小到大排序。
（3） 设置已分配区作业按起始地址从小到大连续分配（紧缩）。
（4） 和并空闲区所有空闲表目使其相邻连续。
8.编写PrintAllocation()函数，是每次分配空间发生变化时，打印出分配情况。

三、 实验结果及分析

（一）实验结果

（二）运行结果分析：

1.内存分配结果：
在内存分配过程中，程序按照首次适应原则，搜索可用的内存块，并分配给请求的线程。在运行过程中，程序正确地分配了内存块，并记录了每个线程的内存使用情况。
2.内存回收结果：
在内存回收过程中，程序考虑了分区的合并。当一个线程释放了它所占用的内存块时，程序会检查该内存块是否与相邻的空闲块可以合并。如果可以合并，程序会将它们合并为一个更大的空闲块。这样可以有效地减少内存碎片。
3.碎片整理结果：
当存在碎片时，程序会考虑碎片的整理。在运行过程中，程序会定期检查内存中的“外碎片”，并将它们整理成连续的空闲块。这样可以提高内存的利用率。
4.多线程处理结果：
在实验过程中，我们使用了5个线程进行测试。程序能够正确地处理多个线程的请求，并保证每个线程都能获得所需的内存资源。在多线程环境下，程序的运行稳定，没有出现死锁或竞争条件等问题。
综上所述，该可变分区内存管理器成功地实现了实验要求的功能。在运行过程中，程序能够正确地分配和回收内存资源，并有效地处理“外碎片”问题。同时，程序在多线程环境下运行稳定，能够满足实验要求。

四、 其他

（一）可变分区存储管理

为了克服固定分区管理方式“内碎片”问题严重，主存利用率低的缺点,一种可以消除“内碎片”的动态分区技术应运而生,这就是可变分区存储管理方式。这种管理方式不是把作业装人已经分好的分区中,而是在作业要求装人主存时,根据作业需要的主存量和当时主存空间的使用情况决定是否可以装入该作业。当主存有足够的空间能满足作业要求时,就按作业需求量划出一个分区给该作业。由于分区的大小是按照作业的实际需求量来定的,故在作业占用的分区里没有“内碎片”。这种动态分区法使得分区的长度和大小都是可变的。

（二）主存空间的分配与释放

可变分区管理方式下主存空间的分配与释放跟固定分区管理采用的算法差不多,但由于可变分区管理方式下主存空间在使用过程中会出现划分得比较凌乱的情况,因而带来一些新的问题,因此相应的主存空间的分配与释放算法也稍微复杂一些。
采用可变分区管理方式的系统中,系统初始化时,主存中除操作系统占用部分外,把整个用户区看成是一个大的空闲区，当有作业要装入主存时,从空闲区中划出一个与作业长度一致的分区来装作业,剩余部分仍为空闲区。当作业需求量超过空闲区长度时,该作业暂时不能装入。当某作业执行结束后,它所占的分区必须被收回,成为一个空闲区。随着作业不断地进出主存,主存空间被分成了许多区,有的分区被占用,有的分区空闲。特别是,可能在许多被作业占用的分区之间出现了一些无法装入任何作业的小的空闲区,这些小的空闲分区也是主存空间的一种浪费,称为“外碎片”。为了尽可能简单地及时消除这些外部碎片，主存空间的释放算法中增加了合并相邻空闲分区的操作。
由于采用可变分区方式管理主存时,主存中已占分区和空闲分区的数目和大小都是在变化的,所以为了便于对主存空间的分配与释放,主存分配表可以用两张表格组成,一张是“已分配区表”,另一张是“空闲区表”。已分配区表记录已装入主存的作业所占分区的起始地址和长度,并用标志位指出占用分区的作业名。空闲区表记录主存中可供分配的空闲区的起始地址和长度,也用标志位指出该分区是“未分配”的空闲区。由于已占分区和空闲分区的个数不定,所以在已分配区表和空闲区表中都有一定数目的空表目(其标志位的值为“空"),分别表示相应的分区“已释放”和“已分配或已被合并”。其实,空表目是这两种分区管理表格中的分配单位。
采用可变分区方式管理主存时,主存空间的分配与释放都要对已分配区表和空闲区表这两个表进行访问和修改。比如,分配主存时,先查空闲区表,等完成分配后,要修改空闲区表和已分配区表。具体调整过程如下:分配后,把已分配区表中的一个空表目改为一个标志为某作业名的相应表目,其起始地址和长度均来自空闲区表;同时,空闲区表仅当被选中分区的尺寸与作业需求相等时才将相应表目状态置成“空”,否则只把相应表目的起始地址和长度改为分割后的值。释放后,将已分配区表中相应表目的状态置成“空”;同时,按被释放分区的起始地址和长度先在空闲区表中找到插入点,仅当被释放分区与其他空闲分区不相连时,才把空闲区表中的一个空表目改成一个状态为“未分配”的相应表目,否则,要把释放区与相邻的空闲分区进行合并,最后把合并结果记录在空闲区表中。
为了提高主存分配算法访问空闲区表的效率,常常对空闲区表的表目按一定顺序进行排列,然后仍按“顺序分配算法”检索空闲区表,进行主存空间的分配。这也导致主存空间的释放算法中必须增加有序插人一个表目的操作。由于空闲区表表目的排列顺序有三种,因此就有了由顺序分配算法演化来的以下三种不同的分配算法。这三种分配算法的执行效果各有利弊,但执行流程是一样的,只不过所用的空闲区表表目的排列顺序不同罢了。

（三）最先适应分配算法

是一种性能一般,但实现比较自然直接,而且易于释放时合并相邻空闲分区的分配算法,因而也是可变分区管理中最常用的分配算法,它所用的空闲区表的表目是按相应分区的地址大小以递增顺序排列的。分配时顺序查找空闲区表,找到第一个能满足作业要求的空闲区,如果该空闲区比作业长度大,则分割这个空闲区,一部分分配给作业,另一部分仍为空闲区;如果该空闲区与作业等大小,则直接把它分给作业。调整相应的空闲区表利已分配区表。
优点:释放分区时易于合并相邻的空闲分区,尽可能地保留了高地址端的空闲区。
缺点:完成一次分配平均需要的搜索次数较大，影响了工作效率。

（四）移动紧缩技术

1．消除了固定分区管理造成的“内碎片”，但是不可避免的在内存空间造成“外碎片”。采用移动（紧缩）技术。定时的或在内存紧张时，将内存中所有作业移到内存的一端，使其相邻。
2.经过紧缩后的进程在内存中的位置发生了变化，若不对程序和数据的地址进行修改，在进程就无法运行。
3.要使其运行，必须进行“动态重定位”
注意紧缩的时机：
（1）一旦有归还的分区便进行紧缩，系统开销大。
（2）分配算法发现各空闲区不够用，但其和够用时。此法紧缩开销小，更实用。因此，实际的可变分区分配算法比固定分区分配算法主要增加了“紧缩”操作。

五、实验代码

#include<bits/stdc++.h>
using namespace std;
mutex mut;
typedef struct{
    int length; //记录作业长度
    int base;   //记录作业起始地址
    string state; //记录作业状态，已分配为作业名，未分配为空闲
} FreeType; //空闲区类型

typedef struct{
    int length;//作业大小
    string name; //作业名
} JobType;  //作业类型

const int MAX_BLOCKS = 120; // 设空闲区初始容量120KB
vector <FreeType> allocatedBlocks; //已分配表
vector <FreeType> freeBlocks;//空闲表
void PrintAllocation(); //打印内存分配情况
bool cmp(FreeType x,FreeType y);
//空闲区初始化
void InitialFreeArea(){
    FreeType data;
    data.length = MAX_BLOCKS;//初始最大120
    data.base= 0;
    data.state = "空闲";
    freeBlocks.push_back(data);
}

//分配时顺序查找空闲区表,找到第一个能满足作业要求的空闲区,返回下标
int FindFreeBlock(JobType user){
    for(int i = 0; i<freeBlocks.size(); i++){
        if(freeBlocks[i].length >= user.length && freeBlocks[i].state =="空闲") return i;
    }
    //当作业需求量超过空闲区长度时,该作业暂时不能装入。
    cout <<"该作业暂时不能装入"<<endl;
    return -1;
}

//最先适应分配算法
void FristFit(JobType user){
//1.顺序查找空闲区表,找到第一个能满足作业要求的空闲区
    int num = FindFreeBlock(user);
    if(num != -1){//找到能装入改作业的空闲区
        if(freeBlocks[num].length == user.length)//2.如果该空闲区与作业等大小,则直接把它分给作业。
            freeBlocks[num].state = " ";
        else{
            //3.如果该空闲区比作业长度大。
            FreeType data;
            data.length = freeBlocks[num].length - user.length;
            data.base = user.length + freeBlocks[num].base;
            data.state = "空闲";  //将另一部分设为空闲区;
            freeBlocks[num].length = user.length;
            freeBlocks[num].state = " ";//分割这个空闲区,该部分分配给作业,
            if(num<freeBlocks.size()-1) freeBlocks.insert(freeBlocks.begin()+num+1,data);
            else freeBlocks.push_back(data);//将另一部分空闲区插入空闲区表
        }//调整相应的空闲区表。
        FreeType data1;//调整相应的已分配区表。
        data1.length = freeBlocks[num].length;
        data1.base = freeBlocks[num].base;//其起始地址和长度均来自空闲区表
        data1.state = user.name;
        int i;
        for(i = 0; i<allocatedBlocks.size(); i++){
            //分配后,把已分配区表中的一个空表目改为一个标志为某作业名的相应表目
            if(allocatedBlocks[i].state == " "){
                allocatedBlocks[i] = data1;
                break;
            }
        }
        if(i==allocatedBlocks.size()) allocatedBlocks.push_back(data1);
    }//若没有空表目新建插入
    PrintAllocation();
}

//合并操作，减少“外碎片”利于今后大作业的到来。
bool Merge(FreeType data,int i){
    bool flag = true;
    if(freeBlocks[i-1].state =="空闲" && freeBlocks[i+1].state =="空闲"){
        //若释放区既有上邻空闲区，又有下邻空闲区。将三个空闲区合并成一个大空闲区。
        freeBlocks[i+1].base = data.base;
        freeBlocks[i+1].length += data.length;
        freeBlocks.erase(freeBlocks.begin()+i);
        freeBlocks[i-1].length += freeBlocks[i+1].length;
        freeBlocks.erase(freeBlocks.begin()+i);
    }
    else if(freeBlocks[i-1].state =="空闲"){
        //若释放区只有上邻空闲区F1。则只修改空闲区F1大小。
        freeBlocks[i-1].length += data.length;
        freeBlocks.erase(freeBlocks.begin()+i);
    }
    else if(freeBlocks[i+1].state =="空闲"){
        //只有下邻空闲区，只修改该空闲区。
        freeBlocks[i+1].base = data.base;
        freeBlocks[i+1].length += data.length;
        freeBlocks.erase(freeBlocks.begin()+i);
    }
    else flag = false;
    return flag;
}

//已分配表查找回收作业名
int FindJob(string name){
    for(int i = 0; i<allocatedBlocks.size(); i++){
        if(allocatedBlocks[i].state == name) return i;
    }
    cout << "该作业不存在，不可回收"<<endl;
    return -1;
}

//作业回收
void Recovery(string name){
    int num = FindJob(name);
    if(num !=-1) {//分配区找到该作业
        allocatedBlocks[num].state = " ";
        //释放后,将已分配区表中相应表目的状态置成“空”;
        for(int  i=0 ; i<freeBlocks.size(); i++ ){
            if(freeBlocks[i].base == allocatedBlocks[num].base){
                if(Merge(allocatedBlocks[num],i)== false) freeBlocks[i].state = "空闲";
                //不需要合并，把空闲区表中的一个空表目改成一个状态为“未分配”的相应表目。
                break;
            }
        }
    }
    PrintAllocation();
}

//移动紧缩技术，将内存中所有作业移到内存的一端，使其相邻。
void Compaction( ){
    for(int i=allocatedBlocks.size()-1; i>=0; i--){
        if(allocatedBlocks[i].state == " ") allocatedBlocks.erase(allocatedBlocks.begin()+i);
    }//1.倒序去除已分配区空表目
    sort(allocatedBlocks.begin(),allocatedBlocks.end(),cmp);//2.已分配区作业按起始地址从小到大排序
    for(int i = 0; i<allocatedBlocks.size(); i++){
        if(!i) allocatedBlocks[i].base = 0;
        else allocatedBlocks[i].base = allocatedBlocks[i-1].base + allocatedBlocks[i-1].length;
    }//3.设置已分配区作业按起始地址从小到大连续分配（紧缩）
    freeBlocks.front().base = allocatedBlocks.back().base+allocatedBlocks.back().length;
    freeBlocks.front().length = MAX_BLOCKS -  freeBlocks.front().base;
    freeBlocks.front().state = "空闲";
    for(int i = freeBlocks.size()-1; i>0; i--) freeBlocks.erase(freeBlocks.begin()+i);
    //4.和并空闲区所有空闲表目使其相邻连续
    PrintAllocation();
}

//创建5个作业信息
JobType user[5] = {{10,"作业1"},{10,"作业2"},{20,"作业3"},{30,"作业4"},{40,"作业5"}};
void ThreadTask(JobType user) {//作业任务，模拟作业分配
    mut.lock();
    FristFit(user); //调用最先适应分配算法
    mut.unlock();
}
void CreateTask(){
    thread thread_[5]; //定义5个线程
    for(int i=0; i<5; i++){
        thread_[i] = thread(ThreadTask,user[i]);
    }
    for(int i=0; i<5; i++){
        thread_[i].join();
    }//主线程等待子线程完成
}
int main( ){
    InitialFreeArea();//初始化内存区
    CreateTask();
    for(int i=0; i<2; i++){//模拟作业回收，回收前两个作业
        Recovery(allocatedBlocks[i].state);
    }
    Compaction(); //移动紧缩技术
    cout << "End" ;
    return 0;
}
void PrintAllocation() { //打印分配情况
    cout <<"********************************"<<endl;
    cout<<"        已分配分区表\n";
    cout<<"--------------------------------"<<endl;
    cout <<"序号\t长度\t始址\t标志位\t"<<endl;
    for(int i=0 ; i<allocatedBlocks.size(); i++ ){
        cout<<"--------------------------------"<<endl;
        cout << i+1<< "\t" << allocatedBlocks[i].length << "KB\t" ;
        cout << allocatedBlocks[i].base << "KB\t" <<allocatedBlocks[i].state<< "\t"<<endl;
    }
    cout <<"********************************"<<endl;
    cout <<"\n********************************\n";
    cout<<"          空闲分区表\n";
    cout<<"--------------------------------"<<endl;
    cout <<"序号\t长度\t始址\t标志位\t"<<endl;
    for(int i=0 ; i<freeBlocks.size(); i++ ){
        cout<<"--------------------------------"<<endl;
        cout << i+1<< "\t" << freeBlocks[i].length << "KB\t" ;
        cout << freeBlocks[i].base << "KB\t" <<freeBlocks[i].state<< "\t"<<endl;
    }
    cout <<"********************************\n\n";
    system("pause");
}

bool cmp(FreeType x,FreeType y){
    return x.base < y.base ;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197