0 personal information
- Zhang yingzi
- 201821121038
- Calculation 1812
1 purpose of the experiment
- Learn more about memory management through programming.
2 experiment content
- On the server, we use Vim to write a program: simulate a memory management algorithm, test the result, and explain the running result.
3. Experiment report
Three point one Record memory space usage
Use a linked list to record memory space usage.
1 //Memory block allocated to each process 2 typedef struct allocated_block{ 3 int pid; //Process number 4 int size; //Memory block size allocated by the process 5 int start_addr; //Memory block start address 6 char process_name[NAME_LEN]; //Process name 7 struct allocated_block *next; //Pointer to the next memory block 8 }AB; 9 10 //The first pointer of the process allocated memory block list 11 AB *allocated_block_head = NULL;
Three point two Record free partition
A linked list is also used to record free partitions.
1 //Each free block 2 typedef struct free_block_type{ 3 int size; //Free block size 4 int start_addr; //Free block start address 5 struct free_block_type *next; //Point to next free block 6 }FBT; 7 8 //The first pointer to the free block list in memory 9 FBT *free_block;
Three point three Memory allocation algorithm
The principle of the Best Fit Allocation algorithm is that the list of free partitions is sorted by size. When allocating, it finds a suitable partition (when allocating n-byte partition, it finds and uses the minimum space partition no less than n); when releasing, it finds and merges the near free partition (if found).
1 //Perform memory allocation 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 //distribution 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 //Allocate memory modules 20 int allocate_mem(AB *ab){ 21 FBT *fbt,*pre; 22 int request_size=ab->size; 23 fbt = pre = free_block; 24 //Try to find allocatable free 25 int f = find_free_mem(request_size); 26 if(f == -1){ 27 //Insufficient distribution 28 printf("Not enough free memory,memory allocation failed!\n"); 29 return -1; 30 }else{ 31 if(f == 0){ 32 //Memory crunch required to allocate 33 memory_compact(); 34 } 35 //Execute assignment 36 do_allocate_mem(ab); 37 } 38 //Rearrange free partitions 39 rearrange(ma_algorithm); 40 return 1; 41 } 42 43 //The best adaptive algorithm is to sort the free partition from small to large 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 //Traverse the whole free block list, compare and find the smallest free block 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 }
Three point four Memory release algorithm
1 //Release linked list node 2 int dispose(AB *free_ab){ 3 AB *pre,*ab; 4 if(free_ab == allocated_block_head){ 5 //If you want to release the first node 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 //Update partition table 22 int free_mem(AB *ab){ 23 //take ab Return of allocated areas indicated and possible consolidation 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 //Insert to end 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 //Rearrange by address 44 rearrange_BF(); 45 46 //Merge possible partitions;That is, if two free partitions are connected, they will be merged 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 //Sort by current algorithm 60 rearrange(ma_algorithm); 61 return 1; 62 } 63 64 //Free the allocated memory space and delete the node describing the memory block to which the process is allocated 65 int kill_process(int pid){ 66 AB *ab; 67 ab = find_process(pid); 68 if(ab!=NULL){ 69 //release ab Distribution table represented 70 free_mem(ab); 71 //release ab Data structure node 72 dispose(ab); 73 return 0; 74 }else{ 75 return -1; 76 } 77 }
Three point five Operation results
3.5.1 Generate test data
Randomly allocate and free memory for three processes for more than 10 times, that is, randomly generate more than 10 groups of data.
1 int main(int argc, char const *argv[]){ 2 /* 3 sel1=0 Indicates to allocate memory space for a process 4 sel1=1 Indicates to free memory space occupied by a process 5 */ 6 int sel1,sel2; 7 int total=0; //Record the number of times memory was allocated 8 free_block = init_free_block(mem_size); //Initialize free zone 9 10 Prc prc[PROCESS_NUM];//Store processes to load 11 init_program(prc,PROCESS_NUM);//Initialize these processes 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 //Count how many of the three processes have allocated memory 19 for(int j=0;j<PROCESS_NUM;++j){ 20 if(prc[j].pid!=-1) 21 count++; 22 } 23 //If you allocate all processes or processes 5 times, you cannot continue to allocate memory to free memory 24 if((count==PROCESS_NUM && sel1==0)||total==5) 25 sel1=1; 26 //If all processes are unallocated, memory cannot be freed 27 if(count==0 && sel1==1) 28 sel1=0; 29 if(sel1==0)//Allocate memory for processes 30 { 31 //Randomly find a process with unallocated memory 32 do{ 33 sel2=rand()%PROCESS_NUM; 34 }while(prc[sel2].pid!=-1); 35 alloc_process(prc[sel2]);//Allocate memory space 36 prc[sel2].pid=pid;//Change mark 37 total++; 38 display_mem_usage();//display 39 } 40 else//Free up memory occupied by the process 41 { 42 //Randomly find a releasable process 43 do{ 44 sel2=rand()%PROCESS_NUM; 45 }while(prc[sel2].pid==-1); 46 kill_process(prc[sel2].pid);//Free up memory 47 prc[sel2].pid=-1;//Change mark 48 display_mem_usage();//display 49 } 50 } 51 }
3.5.2 Interpretation results
The initial free block size is 1024KB,
① first distribution result:
Allocate 24KB of memory space for the process with PID 1, starting address 0, 1000KB of free space after allocation, and starting address 24.
Second distribution results:
Allocate 74KB of memory space for the process with PID 2, starting at 24, 926KB of free space after allocation, and starting at 98.
③ results of the third distribution:
Allocate 36KB of memory space for the process with PID 3, starting at 98, 890KB of free space after allocation, and starting at 134.
④ results of the fourth distribution:
The process with PID 3 is released, the free space is 926KB, and the starting address is 98.
⑤ fifth distribution result:
The process with PID 1 is released and the free space is changed into two pieces, one of which is 926KB in size and the starting address is 98. The other block has a size of 24KB and a starting address of 0.