BF algorithm, boyfriend algorithm, ha ha to achieve dynamic partition allocation, need to consider three aspects of the problem. They are data structure, partition allocation algorithm, partition allocation and reclamation operations.

First data structure

Here we use the free partition chain, using a bidirectional linked list to represent the free partition. The concrete implementation is as follows:

typedef struct LNode{
    int order;                       // Indicates the order of memory blocks
    int start;                       // Indicates the initial address of memory
    int end;                         // Indicates the end address of the memory
    int size;                        // Indicates the size of the memory block
    int state;                       // Indicates the status of the memory block. 1 indicates that the memory block is occupied, and 0 indicates that the memory block is idle
    int process;                     // Stores the sequence number of the process that occupies the memory block
    struct LNode *next;              // points to the next memory block
    struct LNode *pre;               // points to the previous memory block
}LNode;
Copy the code

Allocation algorithm

The best Fit BF algorithm in dynamic partition allocation algorithm based on sequential search is adopted. When allocating memory for a job, always allocate the smallest free partition that meets the requirements to the job to avoid “overuse”.

Allocation and reclamation of memory

  • Allocate memory to find partitions of the desired size from the free partition chain. Let the requested partition size be u. SCize, the size of each free partition in the table can be expressed as M.SCize, if the memory allocation operation is performed when M.SCize -U. SCize >=0, if greater than 0, apply for a new node and insert it into the bipartite linked list; if equal to 0, only modify the information of the nodes that meet the requirements.

  • Reclaim memory, four cases (F: the memory area to be reclaimed, the first partition of F1 :F, the last partition of F2:F) \

    • F is connected to the address F1, and F1 is idle. Merge F and F1. After the merger, the first address of the node is the first address of F1, the last address is the last address of F, and the number of nodes is reduced by one.
    • F is connected to the address of F2 and F2 is idle. Merge F and F2. After merging, the beginning address of node is F, and the last address is F2, and the number of nodes is reduced by one.
    • F connects with the addresses of F1 and F2, and F1 and F2 are idle. After merging, the initial address of the node is the first address of F1, and the final address is the last address of F2. The number of nodes is reduced by two.
    • Otherwise, set the state flag and process flag of the node to 0.

Application to explain

int buf[N]={100.500.200.700.300};   // Memory block size, used to initialize the free partition linked list
int add[N]={20.150.700.950.1700};// The initial address of the memory block, used to initialize the free partition linked list
int dis[N]={301.400.310.105.190};   // The memory required by the process is marked with the process number

List list_init(a);               // The function used to initialize the free partition list, returns the head of the free partition list
void print(List head);          // Outputs linked list information sequentially
List allot_memory(List head,ing i);// Allocate memory for the process numbered I
List free_memory(List head,int i);// Release the memory occupied by the process numbered I
Copy the code

All the code

#include<stdio.h> 
#include<stdlib.h>

#define N 5

int buf[N]={100.500.200.700.300};
int add[N]={20.150.700.950.1700};int dis[N]={301.400.310.105.190};
typedef struct LNode *List;

typedef struct LNode{
    int order;
    int start;
    int end;
    int size;
    int state; 
    int process;
    struct LNode *next;
    struct LNode *pre;
}LNode;

List list_init(a){
    List head,p,m;
    int i;
    for(i=0; i<N; i++){ m=(List)malloc(sizeof(struct LNode));
        if(! m){printf("error\n");
            exit(0);
        }
        m->order=i+1;
        m->start=add[i];
        m->end=m->start+buf[i]- 1;
        m->size=buf[i];
        m->next=NULL;
        m->pre=NULL;
        m->state=0;
        p->process=0;
        if(i==0)
            head=p=m;
        else{ p->next=m; m->pre=p; p=p->next; }}return head;
}

void print(List head){
    List p=head;
    while(p){
        printf("The first % d block of memory - > start address: % - at the end of the 5 d - > address: % 5 d - > size: % 5 d - > status:",p->order,p->start,p->end,p->size);
        if(p->state==1)
            printf("Occupied by process % D! \n",p->process);
        else if(p->state==0) {printf("Idle! \n");
        } 
        p=p->next;
    }
    printf("\n");
}

List free_memory(List head,int i){
    List p,m,temp;
    p=head;
    while(p){
        if(p->process==i+1){
            temp=p;
            if(p->next){
                m=p->next;
                if(p->end+1==m->start){
                    if(! m->state){ p->size+=m->size; p->end+=m->size; p->next=m->next; p->state=0;
                        p->process=0;
                        if(m->next){
                            m->next->pre=p;
                        }
                        p=m->next;
                        free(m);
                        while(p){ p->order--; p=p->next; }}else{
                        p->state=0;
                        p->process=0; }}else{
                    p->state=0;
                    p->process=0;
                }
            }
            p=temp;
            if(p->pre){
                m=p->pre;
                if(p->start==m->end+1) {if(! m->state){ m->size+=p->size; m->end+=p->size; m->next=p->next;if(p->next){
                            p->next->pre=m;
                        }
                        free(p);
                        p=m->next;
                        while(p){ p->order--; p=p->next; }}else{
                        p->state=0;
                        p->process=0; }}else{
                    p->state=0;
                    p->process=0; }}returnhead; } p=p->next; }}List allot_memory(List head,int i){
    int memory_size=dis[i];
    List p=head;
    List m;
    int min=- 1;
    int order=- 1;

    while(p){
        if(p->process- 1==i){
            printf("Memory already has %d process \n",i+1);
            return head;
        }
        p=p->next;
    }

    p=head;

    while(p){
        if(p->size>=memory_size&&p->state==0) {if(min<0){
                min=p->size-memory_size;
                order=p->order;
            }
            else{
                if(min>p->size-memory_size){
                    min=p->size-memory_size;
                    order=p->order;
                }
            }
        }
        p=p->next;
    }
    if(order==- 1) {printf("%d process failed to allocate memory! \n",i+1);
        return head;
    }
    else{
        p=head;
        while(p){
            if(p->order==order){
                if(p->size==memory_size){
                    p->state=1;
                    p->process=i+1;
                    return head;
                }
                else{
                    m=(List)malloc(sizeof(struct LNode));
                    m->order=p->order;
                    m->start=p->start;
                    m->end=m->start+memory_size- 1;
                    m->size=memory_size;
                    m->state=1;
                    m->next=p;
                    m->process=i+1;

                    m->pre=p->pre;
                    p->pre->next=m;
                    p->pre=m;
                    p->start=m->end+1;
                    p->size-=memory_size;
                    while(p){
                        p->order++;
                        p=p->next;
                    }
                    returnhead; } } p=p->next; }}}int main(a){
    List p,m;
    int choice1,choice2;
    int i;
    p=list_init();


    print(p);
    p=allot_memory(p,3);
    print(p);
    p=allot_memory(p,3);
    p=free_memory(p,3);
    print(p);
    p=allot_memory(p,0);
    print(p);
    p=allot_memory(p,4);
    print(p);
    p=free_memory(p,4);
    print(p);
    p=allot_memory(p,4);
    print(p);
    p=free_memory(p,0);
    print(p);
    p=free_memory(p,4);
    print(p);
    return 0;
}
Copy the code