设计实现内存的分配和回收算法

2022-04-13

摘要

操作系统作业

题目

如下数据结构下，设计实现内存的分配和回收算法：

归还区有下邻空闲区；
归还区有上邻空闲区；
归还区既有上邻空闲区又有下邻空闲区；
归还区既无上邻空闲区又无下邻空闲区

struct
{ float address;  /*已分分区起始地址*/
 float length;  	/*已分分区长度，单位为字节*/
 int flag;   	/*已分配区表登记栏标志，用“0”表示空栏目，实验中只支持一个字符的作业名*/
}used_table[n]; 	/*已分配区表*/
struct
{float address;	/*空闲区起始地址*/
 float length;    /*空闲区长度，单位为字节*/
 int flag;  	/*空闲区表登记栏标志，用“0”表示空栏目，用“1”表示未分配*/
}free_table[m]; 	/*空闲区表*/

编写程序，并输出结果。

代码

#include<stdio.h>

//区表数组结构
struct UsedTable {
    int address;  /*已分分区起始地址*/
    int length;  	/*已分分区长度，单位为字节*/
    int flag;   	/*已分配区表登记栏标志，用“0”表示空栏目，实验中只支持一个编号的作业名*/
} usedTable[100]; 	/*已分配区表*/

struct FreeTable {
    int address;	/*空闲区起始地址*/
    int length;    /*空闲区长度，单位为字节*/
    int flag;  	/*空闲区表登记栏标志，用“0”表示空栏目，用“1”表示未分配*/
} freeTable[100]; 	/*空闲区表*/

void InitTable();                                                   // 初始化区表
void allocTable(const int proName, const int proLenth);             // 创建作业
void reclaimTable(const int proName);                               // 回收作业
int findProName(const struct UsedTable temp[], const int proName);  // 按作业名查找下标
void sortUsedTable(struct UsedTable temp[]);                        // 排序已分配区表
void printUsedTable(const struct UsedTable temp);                   // 输出作业分区信息
void printFreeTable(const struct FreeTable temp);                   // 输出空闲分区信息


int i=0;                    //记录当前 已分配/空闲 区表数量
int Minsize=1;              //作业间最小空余地址

void InitTable() {
    //OS
    usedTable[0].address = 0;
    usedTable[0].length = 3;
    usedTable[0].flag = 1; //OS 的作业名为1
    
    freeTable[0].address = 3;
    freeTable[0].length = 97;
    freeTable[0].flag = 1;

    //图形界面
    freeTable[0].address = 8;
    freeTable[0].length = 92;
    freeTable[0].flag = 1;

    usedTable[1].address = 3;
    usedTable[1].length = 5;
    usedTable[1].flag = 2; //图形界面 的作业名为2
    
    //网络程序
    freeTable[0].address = 8;
    freeTable[0].length = 12;
    freeTable[0].flag = 1;
    
    usedTable[2].address = 20;
    usedTable[2].length = 10;
    usedTable[2].flag = 3; //网络程序 的作业名为3

    freeTable[1].address = 30;
    freeTable[1].length = 70;
    freeTable[1].flag = 1;
    i += 3;
}

void allocTable(const int proName, const int proLenth) {
    int j=0;
    while(freeTable[j].flag) {
        if(freeTable[j].length >= proLenth) break;
        j++;
    }
    if(freeTable[j].flag == 0) {
        printf("\033[0;31mNo free space available\033[0m\n");
        return;
    }
    if(freeTable[j].length - proLenth <= Minsize) {
        usedTable[i].address = freeTable[j].address;
        usedTable[i].length  = freeTable[j].length;
        usedTable[i].flag    = proName;
        while(freeTable[j].flag) {
            freeTable[j] = freeTable[j+1];
            j++;
        }
        freeTable[j].address = freeTable[j].length = freeTable[j].flag = 0;
        i++;
    } else {
        usedTable[i].address = freeTable[j].address;
        usedTable[i].length  = proLenth;
        usedTable[i].flag    = proName;
        freeTable[j].address = freeTable[j].address + proLenth;
        freeTable[j].length  = freeTable[j].length  - proLenth;
        i++;
    } return;
}

int findProName(const struct UsedTable temp[], const int proName) {
    int m=0;
    for(; m<i; m++) {
        if(temp[m].flag == proName)
            return m;
    }
    return -1;
}

void reclaimTable(const int proName) {
    if(proName==1) {
        printf("\033[0;31mCannot reclaim OS progress!\n\033[0m");
        return;
    }
    int k=0,j=0,h=0;
    sortUsedTable(usedTable);
    if(findProName(usedTable, 1) == -1) {
        printf("\033[0;31mERROR!\033[0m");
        return;
    }
    k = findProName(usedTable, proName);
    if(k == -1) {
        printf("\033[0;31mCannot find this progress!\033[0m\n");
        return;
    } else {
        while(freeTable[j].flag || usedTable[h].flag) {
            if(freeTable[j].address + freeTable[j].length == usedTable[k].address) {

                if(freeTable[j+1].flag && usedTable[k].address + usedTable[k].length == freeTable[j+1].address) {
                    freeTable[j].length += (usedTable[k].length + freeTable[j+1].length);
                    usedTable[k].address = usedTable[k].flag = usedTable[k].length = 0;
                    for(int l=j+1; freeTable[l].flag; l++) {
                        freeTable[l] = freeTable[l+1];
                    } //上有，下有
                    i--;
                    return;

                } else {
                    freeTable[j].length += usedTable[k].length;
                    usedTable[k].address = usedTable[k].length = usedTable[k].flag = 0;
                    i--;
                    return;
                } //上有，下无

            } else if (usedTable[k].address + usedTable[k].length == freeTable[j].address) {
                freeTable[j].address = usedTable[k].address;
                freeTable[j].length += usedTable[k].length;
                usedTable[k].address = usedTable[k].flag = usedTable[k].length = 0;
                //上无，下有
                i--;
                return;

            }  else if (usedTable[k-1].address + usedTable[k-1].length + usedTable[k].length == usedTable[k+1].address) {
                int e=0;
                while(freeTable[e].flag) {
                    e++;
                }
                for(int m=e; j<m; m--) {
                    freeTable[m].address = freeTable[m-1].address;
                    freeTable[m].length  = freeTable[m-1].length;
                    freeTable[m].flag    = 1;
                }
                freeTable[j].address = usedTable[k].address;
                freeTable[j].length  = usedTable[k].length;
                usedTable[k].address = usedTable[k].length = usedTable[k].flag = 0;
                //上无，下无
                i--;
                return;

            } //elif
            j++, h++;
        } //while
    } //else
    
    return;
}

void sortUsedTable(struct UsedTable temp[]) {
    int j, k, f;
    struct UsedTable t;
    for(int l=0; l<i; l++) {
        if(temp[l].flag == 0) {
            for(int m = l; m<=i; m++) temp[m] = temp[m+1];
        }
    }
    for(j=0; j<i-1; j++) {
        f=1;
        for(k=0; k<i-1-j; k++)
            if(temp[k+1].address < temp[k].address) {
                f=0;
                t         = temp[k];
                temp[k]   = temp[k+1];
                temp[k+1] = t;
            }
        if(f) break;
    }
}

void printUsedTable(const struct UsedTable temp) {
    printf("\t%d\t%d\t%d\tNormal\n", temp.flag, temp.address, temp.length);
}

void printFreeTable(const struct FreeTable temp) {
    printf("\033[0;36m\tNULL\t%d\t%d\tNULL\n\033[0m", temp.address, temp.length);
}

int main() {
    int a=0, proName=0, proLenth=0;
    InitTable();
    while(1) {
        int m=0, j=0;
        printf("\033[0;32m*Select operation:\n\033[0m");
        printf("\t(0) - exit\n\t(1) - allocate memory\n\t(2) - reclaim memory\n\t(3) - print table\n");
        printf("\033[0;32minput operation: \033[0m");
        scanf("%d", &a);
        switch(a) {
            case 0:
                printf("Bye~\n");
                return 0;
            case 1:
                while(1) {
                    printf("\033[0;32mthe name of the progress: \033[0m");
                    scanf("%d", &proName);
                    if(proName == 0) {
                        printf("\033[0;31munvalidated proName!\033[0m\n");
                        continue;
                    }
                    if(findProName(usedTable, proName) != -1) {
                        printf("\033[0;31mthis proName has been used!\033[0m\n");
                        continue;
                    }
                    break;
                }
                printf("\033[0;32mrequired memory size: \033[0m");
                scanf("%d", &proLenth);
                allocTable(proName, proLenth);
                break;
            case 2:
                printf("\033[0;32mthe name of the progress to reclaim: \033[0m");
                scanf("%d", &proName);
                reclaimTable(proName);
                break;
            case 3:
                printf("----------------------------------------------\n");
                printf("\033[0;32mmemory table:\033[0m\n");
                printf("\033[0;34m\tproName\taddress\tlength\tstatus\033[0m\n");
                sortUsedTable(usedTable);
                while(usedTable[m].flag || freeTable[j].flag) {
                    if(usedTable[m].address < freeTable[j].address && usedTable[m].flag) {
                        printUsedTable(usedTable[m]);
                        m++;
                    } else if (freeTable[j].flag) {
                        printFreeTable(freeTable[j]);
                        j++;
                    }
                }
                printf("----------------------------------------------\n");
                //getchar();
                break;
            default: printf("\033[0;31mNo such this operation\n\033[0m");
        }
    }
    return 0;
}