# 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.

# 4 References

Keywords: Linux Programming vim less github

Added by bryansu on Sun, 17 May 2020 11:48:25 +0300