首次适应算法实现主存分配和回收

操作系统内存相关：首次适应算法实现主存分配和回收。

问题描述

  1. 可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存容量查看是否有足够的空闲空间，若有，则按需分配，否则，作业无法装入。
  2. 假定内存大小为128K，空闲区说明表格式为：
    • 分区号（表示是第几个空闲分区）
    • 起始地址（指出空闲区的起始地址）
    • 长度（一个连续空闲区的长度）
  3. 采用首次适应算法分配回收内存空间。运行时，输入一系列分配请求和回收请求。

要求

要求能接受来自键盘的空间申请及释放请求，能显示分区分配及回收后的内存布局情况。

代码实现

方法一：使用二叉树存储空闲区说明表

  • 节点结构为：
    • address ：首地址
    • length：分区长度
    • state：状态（F：空闲，B：忙碌，P：左右孩子节点的父节点）
    • homework：作业号（-1表示没有作业装入）
    • *lchild：左孩子（Busy状态）
    • *rchild：右孩子（Free状态）
  • 最开始只有一个根节点
  • 每次作业装入都是将一个节点划分为左右孩子，左孩子装入作业，右孩子为剩余空间
  • 每次卸载作业只需找到该作业将其 state 改为 F
  • 每次卸载作业成功后合并相邻空闲分区
  • 打印空闲区说明表时只打印度为0的节点，这才是真正的表项
  • 待优化：因为二叉树结构的特殊性，本程序无法合并不同深度的相邻空闲节点
1
#include<iostream>
2
using namespace std;
3
4
int flag = 0; // 装入一个作业时赋值为1，用来判断是否成功装入作业
5
int temp = 0; // 卸载一个作业时赋值为1，用来判断是否成功卸载作业
6
// 空闲区说明表结构体
7
typedef struct Node {
8
    int address;		// 首地址
9
    int length;			// 长度
10
    char state;			// 状态（F：空闲，B：忙碌，P：左右孩子节点的父节点）
11
    int homework;		// 作业号(-1表示没有作业装入)
12
    struct Node *lchild;	// 左孩子（Busy状态）
13
    struct Node *rchild;	// 右孩子（Free状态）
14
}TNode;		  		// 空闲区说明表节点
15
16
// 初始化空闲区说明表
17
void init_table(TNode *p) {
18
    p->address = 0;	// 从0开始
19
    p->length = 128;	// 大小为128K
20
    p->state = 'F';	// 空闲
21
    p->homework = -1;	// 没有作业装入
22
    p->lchild = NULL;
23
    p->rchild = NULL;
24
    cout << "*首地址为0，大小为128K的内存空间已初始化完成*" << endl;
25
}
26
27
// 打印空闲区说明表
28
void show_item(TNode *p) {
29
    cout << p->address << "\t" << p->length;
30
    if(p->state == 'F')		cout << "\tFree";
31
    else	cout << "\tBusy";
32
    if(p->homework != -1)	cout << "\t" << p->homework;
33
    else cout << "\tnull";
34
    cout << endl;
35
}
36
37
// 采用二叉树的先序遍历打印空闲区说明表
38
void show_table(TNode *p) {
39
    if(p) {
40
        if(!p->lchild && !p->rchild && p->length!=0)
41
            show_item(p); // 度为0的节点才是一个表项
42
        show_table(p->lchild);
43
        show_table(p->rchild);
44
    }
45
}
46
47
// 采用二叉树的后序遍历合并相邻空闲区
48
// 因为二叉树结构的特殊性，只能合并处于同一深度的空闲分区
49
void merge_table(TNode *p) {
50
    if(p) {
51
        merge_table(p->lchild);
52
        merge_table(p->rchild);
53
        if(p->lchild && p->rchild && p->lchild->state=='F' && p->rchild->state=='F') {
54
            p->state = 'F';
55
            p->homework = -1;
56
            p->address = p->lchild->address;
57
            p->length = p->lchild->length + p->rchild->length;
58
            p->lchild = NULL;
59
            p->rchild = NULL;
60
        }
61
    }
62
}
63
64
// 装入新作业
65
// 参数：空闲区说明表，作业号，作业长度
66
void insert_homework(TNode *p, int work, int len) {
67
    if(p) {
68
        // 当改节点：空闲 + 足够大 + 是一个表项 时，才能装入新作业
69
        if(p->state=='F' && len<=p->length && !p->lchild && !p->rchild && flag==0) {
70
            TNode *left = new TNode;  // 左孩子装入作业
71
            TNode *right = new TNode; // 右孩子为剩余空间
72
            // 设置左孩子节点
73
            left->homework = work;
74
            left->address = p->address;
75
            left->length = len;
76
            left->state = 'B';
77
            left->lchild = NULL;
78
            left->rchild = NULL;
79
            // 设置右孩子节点
80
            right->homework = -1;
81
            right->address = left->address + len;
82
            right->length = p->length - left->length;
83
            right->state = 'F';
84
            right->lchild = NULL;
85
            right->rchild = NULL;
86
            // 设置p节点
87
            p->state = 'P';
88
            p->lchild = left;
89
            p->rchild = right;
90
            flag = 1;
91
        }else {
92
            insert_homework(p->lchild, work, len);
93
            insert_homework(p->rchild, work, len);
94
        }
95
    }
96
}
97
98
// 卸载作业
99
// 参数：空闲区说明表，作业号
100
void delete_homework(TNode *p, int work) {
101
    if(p) {
102
        if(p->homework == work) {
103
            p->homework = -1;
104
            p->state = 'F';
105
            temp = 1;
106
        }else {
107
            delete_homework(p->lchild, work);
108
            delete_homework(p->rchild, work);
109
        }
110
    }
111
}
112
113
// 可变分区管理方式下采用首次适应算法实现主存分配和回收
114
void First_Fit() {
115
    // 初始化空闲区说明表
116
    TNode *p = new TNode;
117
    init_table(p);
118
    // 打印初始空闲区说明表
119
    cout << "*初始化空闲区说明表*" << endl;
120
	cout << "首地址\t长度\t状态\t作业号" << endl;
121
    show_table(p);
122
    // 作业信息
123
    char how; // 作业装入或卸载命令
124
    int no;   // 作业号
125
    int len;  // 作业长度
126
    // 响应来自键盘的作业装入和卸载请求
127
    cout << "*指令格式：装入/卸载 作业号 [作业长度]（如：n 1 20 / d 1)，输入'#'结束*" << endl;
128
    cout << "*请输入：";
129
    cin >> how;
130
    while(how != '#') {
131
        cin >> no;
132
        if(how == 'n') {
133
            flag = 0;
134
            cin >> len;
135
            if(len > 0) {
136
            	insert_homework(p, no, len);
137
            	if(flag == 1) {
138
                    cout << "装入作业" << no << endl;
139
                    cout << "首地址\t长度\t状态\t作业号" << endl;
140
                    show_table(p);
141
            	}else cout << "空间不足，装入失败！" << endl;
142
            }else cout << "作业所需空间大小需为正数！" << endl;
143
        }
144
        else if(how == 'd') {
145
            temp = 0;
146
            delete_homework(p, no);
147
            if(temp == 1) {
148
                merge_table(p); // 合并空闲分区
149
                cout << "卸载作业" << no << endl;
150
                cout << "首地址\t长度\t状态\t作业号" << endl;
151
                show_table(p);
152
            }else cout << "作业不存在，卸载失败！" << endl;
153
        }
154
        else
155
            cout << "指令格式错误，请重新输入！" << endl;
156
        cout << "*请输入：";
157
        cin >> how;
158
    }
159
}
160
161
int main() {
162
    cout << "**可变分区管理方式下采用首次适应算法实现主存分配和回收**" << endl;
163
    First_Fit();
164
165
    return 0;
166
}

方法二：使用单链表存储空闲区说明表

  • 节点结构为：
    • address ：首地址
    • length：分区长度
    • state：状态（F：空闲，B：忙碌）
    • homework：作业号（-1表示没有作业装入）
    • *next：后继节点
  • 每次装入作业时：
    • 该空闲区大小和作业大小相等，直接将作业信息赋给当前分区节点
    • 否则，装入作业当前节点，新建一个节点作为剩余空间节点
  • 每次卸载作业只需找到该作业将其 state 改为 F
  • 每次卸载作业成功后合并相邻空闲分区
  • 本方法克服了方法一的不足，能够实现任意相邻空闲分区的合并
1
#include<iostream>
2
using namespace std;
3
4
// 空闲区说明表结构体
5
typedef struct Node {
6
    int address;		// 首地址
7
    int length;			// 长度
8
    char state;			// 状态（F：空闲，B：忙碌）
9
    int homework;		// 作业号(-1表示没有作业装入)
10
    struct Node *next;		// 后继节点
11
}TNode;		  		// 空闲区说明表节点
12
13
// 初始化空闲区说明表
14
void init_table(TNode *p) {
15
    p->address = 0;	// 从0开始
16
    p->length = 128;	// 大小为128K
17
    p->state = 'F';	// 空闲
18
    p->homework = -1;	// 没有作业装入
19
    p->next = NULL;
20
    cout << "*首地址为0，大小为128K的内存空间已初始化完成*" << endl;
21
}
22
23
// 打印空闲区说明表节点
24
void show_item(TNode *p) {
25
    cout << p->address << "\t" << p->length;
26
    if(p->state == 'F')		cout << "\tFree";
27
    else	cout << "\tBusy";
28
    if(p->homework != -1)	cout << "\t" << p->homework;
29
    else cout << "\tnull";
30
    cout << endl;
31
}
32
33
// 打印空闲区说明表
34
void show_table(TNode *p) {
35
    while(p) {
36
        show_item(p);
37
        p = p->next;
38
    }
39
}
40
41
// 装入新作业
42
// 参数：空闲区说明表，作业号，作业长度
43
// 返回值：true装入成功，false装入失败
44
bool insert_homework(TNode *p, int work, int len) {
45
    while(p) {
46
        // 当改节点：空闲 + 足够大 + 是一个表项 时，才能装入新作业
47
        if(p->state=='F' && len<=p->length) {
48
            if(len == p->length) { // 作业完全填充该表项，没有剩余空间
49
                p->homework = work;
50
                p->state = 'B';
51
            }else {
52
                // 新表项表示装入作业后的剩余空间
53
                TNode *q = new TNode;
54
                q->address = p->address + len;
55
                q->state = 'F';
56
                q->homework = -1;
57
                q->length = p->length - len;
58
                // 作业装入当前表项的前len长度的空间
59
                p->state = 'B';
60
                p->homework = work;
61
                p->length = len;
62
                // 链接
63
                q->next = p->next;
64
                p->next = q;
65
            }
66
            return true;
67
        }
68
        p = p->next;
69
    }
70
    return false;
71
}
72
73
// 合并相邻空闲区
74
void merge_table(TNode *p) {
75
    while(p) {
76
        if(p->state == 'F') {
77
            if(p->next && p->next->state=='F') {
78
                TNode *q = p->next;
79
                p->length += q->length;
80
                p->next = q->next;
81
                free(q);
82
            }
83
            else if(p->next && p->next->state=='B')
84
                p = p->next->next;
85
            else if(p->next == NULL)
86
                return;
87
        }else p = p->next;
88
    }
89
}
90
91
// 卸载作业
92
// 参数：空闲区说明表，作业号
93
// 返回值：true卸载成功，false卸载失败
94
bool delete_homework(TNode *p, int work) {
95
    while(p) {
96
        if(p->homework == work) {
97
            p->homework = -1;
98
            p->state = 'F';
99
            return true;
100
        }
101
        p = p->next;
102
    }
103
    return false;
104
}
105
106
// 可变分区管理方式下采用首次适应算法实现主存分配和回收
107
void First_Fit() {
108
    // 初始化空闲区说明表
109
    TNode *p = new TNode;
110
    init_table(p);
111
    // 打印初始空闲区说明表
112
    cout << "*初始化空闲区说明表*" << endl;
113
	cout << "首地址\t长度\t状态\t作业号" << endl;
114
    show_table(p);
115
    // 作业信息
116
    char how; // 作业装入或卸载命令
117
    int no;   // 作业号
118
    int len;  // 作业长度
119
    // 响应来自键盘的作业装入和卸载请求
120
    cout << "*指令格式：装入/卸载 作业号 [作业长度]（如：n 1 20 / d 1)，输入'#'结束*" << endl;
121
    cout << "*请输入：";
122
    cin >> how;
123
    while(how != '#') {
124
        cin >> no;
125
        if(how == 'n') {
126
            cin >> len;
127
            if(len > 0) {
128
                bool flag = insert_homework(p, no, len);
129
                if(flag == true) {
130
                    cout << "装入作业" << no << endl;
131
                    cout << "首地址\t长度\t状态\t作业号" << endl;
132
                    show_table(p);
133
                }else cout << "空间不足，装入失败" << endl;
134
            }else cout << "作业所需空间大小需为正数！" << endl;
135
        }
136
        else if(how == 'd') {
137
            bool flag = delete_homework(p, no);
138
            if(flag == true) {
139
                merge_table(p); // 合并空闲分区
140
                cout << "卸载作业" << no << endl;
141
                cout << "首地址\t长度\t状态\t作业号" << endl;
142
                show_table(p);
143
            }else cout << "作业不存在，卸载失败！" << endl;
144
        }
145
        else
146
            cout << "指令格式错误，请重新输入！" << endl;
147
        cout << "*请输入：";
148
        cin >> how;
149
    }
150
}
151
152
int main() {
153
    cout << "**可变分区管理方式下采用首次适应算法实现主存分配和回收**" << endl;
154
    First_Fit();
155
156
    return 0;
157
}

程序中的命令格式

  • 装入作业：n 作业号 作业长度，如：
    • n 1 20
    • n 2 50
  • 卸载作业：d 作业号，如：
    • d 2
    • d 1