操作系统第五次实验报告——内存管理
c语言实现最佳分配进程内存空间算法
0 个人信息
- 张樱姿
- 201821121038
- 计算1812
1 实验目的
- 通过编程进一步了解内存管理。
2 实验内容
- 在服务器上用Vim编写一个程序：仿真实现某个内存管理算法，测试给出结果，并对解释运行结果。
3 实验报告
3.1 记录内存空间使用情况
使用链表记录内存空间使用情况。
1//每个进程分配到的内存块2 typedef struct allocated_block{
3int pid; //进程号
4int size; //进程分配到的内存块大小
5int start_addr; //内存块起始地址
6char process_name[NAME_LEN]; //进程名
7struct allocated_block *next; //指向下一个内存块的指针
8}AB;
9
10//进程分配内存块链表的首指针
11 AB *allocated_block_head = NULL;
3.2 记录空闲分区
同样也使用链表来记录空闲分区。
1//每个空闲块2 typedef struct free_block_type{
3int size; //空闲块大小
4int start_addr; //空闲块起始地址
5struct free_block_type *next; //指向下一个空闲块
6}FBT;
7
8//指向内存中空闲块链表的首指针
9 FBT *free_block;
3.3 内存分配算法
最佳分配算法（Best Fit Allocation）的原理是空闲分区列表按照大小排序，在分配时，查找一个合适的分区（分配n字节分区时，查找并使用不小于n的最小空间分区）；在释放时，查找并且合并临近的空闲分区（如果找到的话）。
1//执行分配内存2void do_allocate_mem(AB *ab){
3int request = ab->size;
4 FBT *tmp = free_block;
5while(tmp != NULL){
6if(tmp->size >= request){
7//分配
8 ab->start_addr = tmp->start_addr;
9int shengyu = tmp->size - request;
10 tmp->size = shengyu;
11 tmp->start_addr = tmp->start_addr + request;
12
13return ;
14 }
15 tmp = tmp->next;
16 }
17}
18
19//分配内存模块
20int allocate_mem(AB *ab){
21 FBT *fbt,*pre;
22int request_size=ab->size;
23 fbt = pre = free_block;
24//尝试寻找可分配空闲
25int f = find_free_mem(request_size);
26if(f == -1){
27//不够分配
28 printf("空闲内存不足,内存分配失败!
");
29return -1;
30 }else{
31if(f == 0){
32//需要内存紧缩才能分配
33 memory_compact();
34 }
35//执行分配
36 do_allocate_mem(ab);
37 }
38//重新排布空闲分区
39 rearrange(ma_algorithm);
40return1;
41}
42
43//最佳适应算法，空闲分区按大小从小到大排序
44void rearrange_BF(){
45if(free_block == NULL || free_block->next == NULL)
46return;
47 FBT *t1,*t2,*head;
48 head = free_block;
49//遍历整个空闲块列表，比较找到最小的一块空闲块
50for(t1 = head->next;t1;t1 = t1->next){
51for(t2 = head;t2 != t1;t2=t2->next){
52if(t2->size > t2->next->size){
53int tmp = t2->start_addr;
54 t2->start_addr = t2->next->start_addr;
55 t2->next->start_addr = tmp;
56
57 tmp = t2->size;
58 t2->size = t2->next->size;
59 t2->next->size = tmp;
60 }
61 }
62 }
63 }
3.4 内存释放算法
1//释放链表节点2int dispose(AB *free_ab){
3 AB *pre,*ab;
4if(free_ab == allocated_block_head){
5//如果要释放第一个节点
6 allocated_block_head = allocated_block_head->next;
7free(free_ab);
8return1;
9 }
10 pre = allocated_block_head;
11 ab = allocated_block_head->next;
12while(ab!=free_ab){
13 pre = ab;
14 ab = ab->next;
15 }
16 pre->next = ab->next;
17free(ab);
18return2;
19}
20
21//更新分区表
22int free_mem(AB *ab){
23//将ab所表示的已分配区归还，并进行可能的合并
24int algorithm = ma_algorithm;
25 FBT *fbt,*pre,*work;
26 fbt = (FBT*)malloc(sizeof(FBT));
27if(!fbt) return -1;
28 fbt->size = ab->size;
29 fbt->start_addr = ab->start_addr;
30
31//插至末尾
32 work = free_block;
33if(work == NULL){
34 free_block = fbt;
35 fbt->next == NULL;
36 }else{
37while(work ->next != NULL){
38 work = work->next;
39 }
40 fbt->next = work->next;
41 work->next = fbt;
42 }
43//按地址重新排布
44 rearrange_BF();
45
46//合并可能分区;即若两空闲分区相连则合并
47 pre = free_block;
48while(pre->next){
49 work = pre->next;
50if(pre->start_addr + pre->size == work->start_addr ){
51 pre->size = pre->size + work->size;
52 pre->next = work->next;
53free(work);
54continue;
55 }else{
56 pre = pre->next;
57 }
58 }
59//按照当前算法排序
60 rearrange(ma_algorithm);
61return1;
62}
63
64//释放已分配的内存空间，删除描述该进程分配到的内存块的节点
65int kill_process(int pid){
66 AB *ab;
67 ab = find_process(pid);
68if(ab!=NULL){
69//释放ab所表示的分配表
70 free_mem(ab);
71//释放ab数据结构节点
72 dispose(ab);
73return0;
74 }else{
75return -1;
76 }
77 }
3.5 运行结果
3.5.1 产生测试数据
随机为3个进程分配、释放内存10次以上，即随机产生10组以上数据。
1int main(int argc, charconst *argv[]){ 2/*3 sel1=0表示为某进程分配内存空间
4 sel1=1表示为释放某进程占用的内存空间
5*/
6int sel1,sel2;
7int total=0; //记录分配内存的次数
8 free_block = init_free_block(mem_size); //初始化空闲区
9
10 Prc prc[PROCESS_NUM];//存放要加载的进程
11 init_program(prc,PROCESS_NUM);//对这几个程进程进行初始化
12 srand( (unsigned)time( NULL ) );
13
14for(int i=0;i<DATA_NUM;++i)
15 {
16 sel1=rand()%2;
17int count=0;
18//统计三个进程中有多少个进程已经分配内存
19for(int j=0;j<PROCESS_NUM;++j){
20if(prc[j].pid!=-1)
21 count++;
22 }
23//如果全部分配进程或者进程分配到达5次，那么就不能继续分配内存改为释放内存
24if((count==PROCESS_NUM && sel1==0)||total==5)
25 sel1=1;
26//如果全部未分配进程，那么就不能继续释放内存
27if(count==0 && sel1==1)
28 sel1=0;
29if(sel1==0)//为进程分配内存
30 {
31//随机找到一个未分配内存的进程
32do{
33 sel2=rand()%PROCESS_NUM;
34 }while(prc[sel2].pid!=-1);
35 alloc_process(prc[sel2]);//分配内存空间
36 prc[sel2].pid=pid;//改变标记
37 total++;
38 display_mem_usage();//显示
39 }
40else//释放进程占用的内存空间
41 {
42//随机找到一个可释放进程
43do{
44 sel2=rand()%PROCESS_NUM;
45 }while(prc[sel2].pid==-1);
46 kill_process(prc[sel2].pid);//释放内存空间
47 prc[sel2].pid=-1;//改变标记
48 display_mem_usage();//显示
49 }
50 }
51 }
3.5.2 解释结果
初始的空闲块大小1024KB，
①第一次分配结果：
为PID为1的进程分配大小为24KB的内存空间，起始地址为0，分配完成后的空闲空间为1000KB，起始地址为24。
②第二次分配结果：
为PID为2的进程分配大小为74KB的内存空间，起始地址为24，分配完成后的空闲空间为926KB，起始地址为98。
③第三次分配结果：
为PID为3的进程分配大小为36KB的内存空间，起始地址为98，分配完成后的空闲空间为890KB，起始地址为134。
④第四次分配结果：
将PID为3的进程释放，空闲空间变为926KB，起始地址为98。
⑤第五次分配结果：
将PID为1的进程释放，空闲空间变为两块，一块大小926KB，起始地址为98。另一块大小24KB，起始地址为0。
4 References
- https://github.com/City-Zero/LinuxTest/tree/96c823cf1ed5aaaa401d3a3c9e3e4f7948def52b/OSex/mem_manager
以上是 操作系统第五次实验报告——内存管理 的全部内容， 来源链接： utcz.com/z/516518.html
