首页 > > 操作系统 > Linux >

操作系统第五次实验报告——内存管理

2020-05-17 16:06:48来源：博客园阅读 ()

操作系统第五次实验报告——内存管理

c语言实现最佳分配进程内存空间算法

0 个人信息

张樱姿
201821121038
计算1812

1 实验目的

通过编程进一步了解内存管理。

2 实验内容

在服务器上用Vim编写一个程序：仿真实现某个内存管理算法，测试给出结果，并对解释运行结果。

3 实验报告

　　3.1 记录内存空间使用情况

　　　使用链表记录内存空间使用情况。

 1 //每个进程分配到的内存块
 2 typedef struct allocated_block{
 3     int pid;           //进程号
 4     int size;          //进程分配到的内存块大小
 5     int start_addr; //内存块起始地址
 6     char process_name[NAME_LEN]; //进程名
 7     struct allocated_block *next;       //指向下一个内存块的指针
 8 }AB;    
 9 
10 //进程分配内存块链表的首指针
11 AB *allocated_block_head = NULL;

　　3.2 记录空闲分区

　　　同样也使用链表来记录空闲分区。

1 //每个空闲块
2 typedef struct free_block_type{
3     int size;            //空闲块大小
4     int start_addr;   //空闲块起始地址
5     struct free_block_type *next;   //指向下一个空闲块
6 }FBT;
7 
8 //指向内存中空闲块链表的首指针
9 FBT *free_block;

　　3.3 内存分配算法

　　　最佳分配算法（Best Fit Allocation）的原理是空闲分区列表按照大小排序，在分配时，查找一个合适的分区（分配n字节分区时，查找并使用不小于n的最小空间分区）；在释放时，查找并且合并临近的空闲分区（如果找到的话）。

 1 //执行分配内存
 2 void do_allocate_mem(AB *ab){
 3     int request = ab->size;
 4     FBT *tmp = free_block;
 5     while(tmp != NULL){
 6         if(tmp->size >= request){
 7             //分配
 8             ab->start_addr = tmp->start_addr;
 9             int shengyu = tmp->size - request;
10             tmp->size = shengyu;
11             tmp->start_addr = tmp->start_addr + request;
12         
13             return ;
14         }
15         tmp = tmp->next;
16     }
17 }
18 
19 //分配内存模块
20 int allocate_mem(AB *ab){
21     FBT *fbt,*pre;
22     int request_size=ab->size;
23     fbt = pre = free_block;
24     //尝试寻找可分配空闲
25     int f = find_free_mem(request_size);
26     if(f == -1){
27         //不够分配
28         printf("空闲内存不足,内存分配失败!\n");
29         return -1;
30     }else{
31         if(f == 0){
32             //需要内存紧缩才能分配
33             memory_compact();
34         }
35         //执行分配
36         do_allocate_mem(ab);
37     }
38     //重新排布空闲分区
39     rearrange(ma_algorithm);
40     return 1;
41 } 
42 
43 //最佳适应算法，空闲分区按大小从小到大排序
44 void rearrange_BF(){
45     if(free_block == NULL || free_block->next == NULL)
46         return;
47     FBT *t1,*t2,*head;
48     head = free_block;
49     //遍历整个空闲块列表，比较找到最小的一块空闲块
50     for(t1 = head->next;t1;t1 = t1->next){
51         for(t2 = head;t2 != t1;t2=t2->next){
52             if(t2->size > t2->next->size){
53                 int 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 //释放链表节点
 2 int dispose(AB *free_ab){
 3     AB *pre,*ab;
 4     if(free_ab == allocated_block_head){
 5         //如果要释放第一个节点
 6         allocated_block_head = allocated_block_head->next;
 7         free(free_ab);
 8         return 1;
 9     }
10     pre = allocated_block_head;
11     ab = allocated_block_head->next;
12     while(ab!=free_ab){
13         pre = ab;
14         ab = ab->next;
15     }
16     pre->next = ab->next;
17     free(ab);
18     return 2;
19 }
20 
21 //更新分区表
22 int free_mem(AB *ab){
23     //将ab所表示的已分配区归还，并进行可能的合并
24     int algorithm = ma_algorithm;
25     FBT *fbt,*pre,*work;
26     fbt = (FBT*)malloc(sizeof(FBT));
27     if(!fbt) return -1;
28     fbt->size = ab->size;
29     fbt->start_addr = ab->start_addr;
30 
31     //插至末尾
32     work = free_block;
33     if(work == NULL){
34         free_block = fbt;
35         fbt->next == NULL;
36     }else{
37         while(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;
48     while(pre->next){
49         work = pre->next;
50         if(pre->start_addr + pre->size == work->start_addr ){
51             pre->size = pre->size + work->size;
52             pre->next = work->next;
53             free(work);
54             continue;
55         }else{
56             pre = pre->next;
57         }
58     }
59     //按照当前算法排序
60     rearrange(ma_algorithm);
61     return 1;
62 }
63 
64 //释放已分配的内存空间，删除描述该进程分配到的内存块的节点
65 int kill_process(int pid){
66     AB *ab;
67     ab = find_process(pid);
68     if(ab!=NULL){
69         //释放ab所表示的分配表
70         free_mem(ab);    
71         //释放ab数据结构节点
72         dispose(ab);    
73         return 0;
74     }else{
75         return -1;
76     }
77 }

　　3.5 运行结果

　　　　3.5.1 产生测试数据

　　　　随机为3个进程分配、释放内存10次以上，即随机产生10组以上数据。

 1 int main(int argc, char const *argv[]){
 2     /*
 3         sel1=0表示为某进程分配内存空间 
 4         sel1=1表示为释放某进程占用的内存空间 
 5     */ 
 6     int sel1,sel2; 
 7     int 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     
14     for(int i=0;i<DATA_NUM;++i)
15     {
16         sel1=rand()%2;
17         int count=0;
18         //统计三个进程中有多少个进程已经分配内存 
19         for(int j=0;j<PROCESS_NUM;++j){
20             if(prc[j].pid!=-1)
21                 count++;
22         }
23         //如果全部分配进程或者进程分配到达5次，那么就不能继续分配内存改为释放内存 
24         if((count==PROCESS_NUM && sel1==0)||total==5)
25             sel1=1;
26         //如果全部未分配进程，那么就不能继续释放内存 
27         if(count==0 && sel1==1)
28             sel1=0;
29         if(sel1==0)//为进程分配内存 
30         {
31             //随机找到一个未分配内存的进程 
32             do{
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         }
40         else//释放进程占用的内存空间 
41         {
42             //随机找到一个可释放进程 
43             do{
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 }