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 }