一、题目描述

某操作系统采用段式管理，用户区主存为

512KB

，空闲块链入空闲链表，分配时截取空块的前半部分（小地址部分），初始时全部空闲。

模拟在首次适应算法下，执行如下申请、释放操作序列时，空闲链表和分配链表的变化：

reg(300KB)->reg(100KB)->release(300KB)->reg(150KB)->reg(50KB)->reg(90KB)

。

二、代码实现

linklist.h

#ifndef _LINKLIST_H_
#define _LINKLIST_H_

/**
 * 空闲分区链表和分配分区链表的节点类型定义
 */
typedef struct LNode {
    int m_begin, m_end; // 数据域，分别标识当前节点表示的内存块的起始地址和结束地址
    struct LNode *next; // 指针域
} LNode;

/**
 * 空闲分区链表和分配分区链表的链表类型定义
 */
typedef struct LinkList {
    LNode *m_head; // 头节点
} LinkList;

/**
 * 销毁链表
 * @param list 待操作的链表
 */
void listDestroy(LinkList list) {
    LNode *cur = list.m_head;
    while (cur) {
        LNode *tmp = cur->next;
        free(cur);
        cur = tmp;
    }
}

/**
 * 在指定位置后插入新节点
 * @param pre_node 待插入位置的前序节点
 * @param begin 新节点的起始地址值
 * @param end 新节点的结束地址值
 */
void listInsertByPosition(LNode *pre_node, int begin, int end) {
    LNode *new_node = (LNode *) malloc(sizeof(LNode));
    new_node->m_begin = begin;
    new_node->m_end = end;
    new_node->next = pre_node->next;
    pre_node->next = new_node;
}

/**
 * 根据值插入新节点
 * @param list 待操作的链表
 * @param begin 新节点的起始地址值
 * @param end 新节点的结束地址值
 * @return 分配成功返回true，否则返回false
 */
bool listInsertByValue(LinkList list, int begin, int end) {
    LNode *new_node = (LNode *) malloc(sizeof(LNode));
    new_node->m_begin = begin;
    new_node->m_end = end;

    for (LNode *cur = list.m_head; cur; cur = cur->next) {
        if (cur->next == NULL || cur->next->m_begin >= end) {
            new_node->next = cur->next;
            cur->next = new_node;

            return true;
        }
    }

    return false;
}

/**
 * 删除指定位置后面的节点
 * @param pre_node 待删除的节点的前序节点
 * @return 删除成功返回true，否则返回false
 */
bool listDeleteByPosition(LNode *pre_node) {
    if (!pre_node || !pre_node->next) {
        return false;
    }

    LNode *tmp = pre_node->next;
    pre_node->next = pre_node->next->next;
    free(tmp);

    return true;
}

/**
 * 修改指定节点的值
 * @param node 待操作的节点
 * @param begin 新的起始地址值
 * @param end 新的结束地址值
 */
void listAlter(LNode *node, int begin, int end) {
    node->m_begin = begin;
    node->m_end = end;
}

#endif

free_list.h

#ifndef _FREE_LIST_H_
#define _FREE_LIST_H_

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

#include "linklist.h"

/**
 * 初始化空闲分区链表
 * @param list 待操作的空闲分区链表
 * @param begin 初始状态下空闲分区的起始位置，即内存空间起始位置
 * @param end 初始状态下空闲分区的结束位置，即内存空间结束位置
 */
void freeListInit(LinkList *list, int begin, int end) {
    list->m_head = (LNode *) malloc(sizeof(LNode));

    LNode *new_node = (LNode *) malloc(sizeof(LNode));
    new_node->m_begin = begin;
    new_node->m_end = end;
    new_node->next = NULL;

    list->m_head->next = new_node;
}

/**
 * 输出空闲链表中的数据
 * @param list 待操作的空闲链表
 */
void freeListShow(LinkList list) {
    LNode *cur = list.m_head->next;
    printf("free_list: [head]->");
    while (cur) {
        printf("[%d, %d]->", cur->m_begin, cur->m_end);
        cur = cur->next;
    }
    printf("NULL\n");
}

#endif

assign_list.h

#ifndef _ASSIGN_LIST_H_
#define _ASSIGN_LIST_H_

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

#include "linklist.h"

/**
 * 初始化分配分区链表
 * @param list 待操作的分配分区链表
 */
void assignListInit(LinkList *list) {
    list->m_head = (LNode *) malloc(sizeof(LNode));
    list->m_head->next = NULL;
}

/**
 * 输出分配链表中的数据
 * @param list 待操作的分配分区链表
 */
void assignListShow(LinkList list) {
    LNode *cur = list.m_head->next;
    printf("assign_list: [head]->");
    while (cur) {
        printf("[%d, %d]->", cur->m_begin, cur->m_end);
        cur = cur->next;
    }
    printf("NULL\n");
}

/**
 * 根据内存块的首尾地址删除分配内存链表中的节点
 * @param list 待操作的分配分区链表
 * @param begin 待删除的内存块的起始地址
 * @param end 待删除的内存块的结束地址
 * @return 删除成功返回true，否则返回false
 */
bool assignListDeleteByValue(LinkList list, int begin, int end) {
    LNode *cur = list.m_head;

    while (cur->next) {
        if (cur->next->m_begin == begin && cur->next->m_end == end) {
            LNode *tmp = cur->next;
            cur->next = cur->next->next;
            free(tmp);
            return true;
        }
        cur = cur->next;
    }

    return false;
}

#endif

main.c

#include "free_list.h"
#include "assign_list.h"

/**
 * 通过首次适应算法进行内存分配
 * @param free_list 待操作的空闲分区链表
 * @param assign_list 待操作的分配分区链表
 * @param size 进程请求的内存大小
 * @param ret_begin 分配成功时分配的内存块的起始地址
 * @param ret_end 分配成功时分配的内存块的结束地址
 * @return 分配成功返回true，反之返回false
 */
bool FF(LinkList free_list, LinkList assign_list, int size, int *ret_begin, int *ret_end) {
    LNode *cur = free_list.m_head->next;

    while (cur) {
        if (cur->m_end - cur->m_begin >= size) { // 当前分区足够大，可以用于分配
            /* 计算分配内存块的首尾地址 */
            *ret_begin = cur->m_begin; // 首地址是当前空闲块首地址
            *ret_end = cur->m_begin + size; // 尾地址是当前空闲块首地址偏移size个单位后的地址

            /* 如果此空闲块没能全部分配出去，要对剩余空闲空间进行记录，否则直接删除即可 */
            if (*ret_end != cur->m_end) {
                listAlter(cur, *ret_end, cur->m_end);
            } else {
                listDeleteByPosition(cur);
            }

            /* 要为刚刚分配的内存块在分配分区链表中进行标识 */
            if (!listInsertByValue(assign_list, *ret_begin, *ret_end)) {
                printf("listInsertByValue error!");
                exit(1);
            }

            return true;
        }
        cur = cur->next;
    }

    return false;
}

/**
 * 向内存中归还内存块
 * @param free_list 待操作的空闲分区链表
 * @param assign_list 待操作的分配分区链表
 * @param begin 待归还内存块的起始地址
 * @param end 待归还内存块的结束地址
 * @return 归还成功返回true，否则返回false
 */
bool RetSpace(LinkList free_list, LinkList assign_list, int begin, int end) {
    /* 从分配分区链表中将对应节点删除 */
    if (!assignListDeleteByValue(assign_list, begin, end)) {
        printf("assignListDeleteByValue error!");
        exit(1);
    }

    /* 向空闲分区链表中进行插入，插入过程中还要考虑到空闲分区的合并 */
    for (LNode *cur = free_list.m_head; cur; cur = cur->next) {
        if (cur->next == NULL) { // 在末尾插入，此时不存在后相邻
            if (cur->m_end == begin) { // 归还空闲区与前序空闲区相邻
                listAlter(cur, cur->m_begin, end);
            } else { // 不存在相邻
                listInsertByPosition(cur, begin, end);
            }
            return true;
        } else if (cur == free_list.m_head && cur->next->m_begin >= end) { // 在开头插入，此时不存在前相邻
            if (cur->next->m_begin == end) { // 归还空闲区与后序空闲区相邻
                listAlter(cur->next, begin, cur->next->m_end);
            } else { // 不存在相邻
                listInsertByPosition(cur, begin, end);
            }
            return true;
        } else if (cur->next->m_begin >= end) { // 在中间位置插入
            if (cur->m_end != begin && cur->next->m_begin != end) { // 没有相邻，无需合并，直接插入即可
                if (!listInsertByValue(free_list, begin, end)) {
                    printf("listInsertByValue error!");
                    exit(1);
                }
            } else if (cur->m_end == begin && cur->next->m_begin == end) { // 与前后空闲区都相邻，需要进行合并
                /* 这里通过修改前空闲区的结束位置，并删除后空闲区来实现合并，反之亦可 */
                cur->m_end = end;
                if (!listDeleteByPosition(cur)) {
                    printf("listDeleteByPosition error!");
                    exit(1);
                }
            } else { // 存在单相邻
                if (cur->m_end == begin) { // 前相邻
                    listAlter(cur, cur->m_begin, end);
                } else { // 后相邻
                    listAlter(cur, begin, cur->m_end);
                }
            }
            return true;
        }
    }

    return false;
}

int main() {
    LinkList free_list;
    LinkList assign_list;

    int records[5][2]; // 累计会申请五次内存，记录这五块内存的起始地址和结束地址

    /* 初始化两个链表 */
    freeListInit(&free_list, 0, 512);
    assignListInit(&assign_list);

    freeListShow(free_list);
    assignListShow(assign_list);

    /* reg(300KB) */
    printf("----------reg(300KB)----------\n");
    FF(free_list, assign_list, 300, &records[0][0], &records[0][1]);
    freeListShow(free_list);
    assignListShow(assign_list);

    /* reg(100KB) */
    printf("----------reg(100KB)----------\n");
    FF(free_list, assign_list, 100, &records[1][0], &records[1][1]);
    freeListShow(free_list);
    assignListShow(assign_list);

    /* release(300KB) */
    printf("----------release(300KB)----------\n");
    RetSpace(free_list, assign_list, records[0][0], records[0][1]);
    freeListShow(free_list);
    assignListShow(assign_list);

    /* reg(150KB) */
    printf("----------reg(150KB)----------\n");
    FF(free_list, assign_list, 150, &records[2][0], &records[2][1]);
    freeListShow(free_list);
    assignListShow(assign_list);

    /* reg(50KB) */
    printf("----------reg(50KB)----------\n");
    FF(free_list, assign_list, 50, &records[3][0], &records[3][1]);
    freeListShow(free_list);
    assignListShow(assign_list);

    /* reg(90KB) */
    printf("----------reg(90KB)----------\n");
    FF(free_list, assign_list, 90, &records[4][0], &records[4][1]);
    freeListShow(free_list);
    assignListShow(assign_list);

    /* 销毁两个链表 */
    listDestroy(free_list);
    listDestroy(assign_list);

    return 0;
}

三、执行结果

atreus@MacBook-Pro % gcc main.c -o main 
atreus@MacBook-Pro % ./main
free_list: [head]->[0, 512]->NULL
assign_list: [head]->NULL
----------reg(300KB)----------
free_list: [head]->[300, 512]->NULL
assign_list: [head]->[0, 300]->NULL
----------reg(100KB)----------
free_list: [head]->[400, 512]->NULL
assign_list: [head]->[0, 300]->[300, 400]->NULL
----------release(300KB)----------
free_list: [head]->[0, 300]->[400, 512]->NULL
assign_list: [head]->[300, 400]->NULL
----------reg(150KB)----------
free_list: [head]->[150, 300]->[400, 512]->NULL
assign_list: [head]->[0, 150]->[300, 400]->NULL
----------reg(50KB)----------
free_list: [head]->[200, 300]->[400, 512]->NULL
assign_list: [head]->[0, 150]->[150, 200]->[300, 400]->NULL
----------reg(90KB)----------
free_list: [head]->[290, 300]->[400, 512]->NULL
assign_list: [head]->[0, 150]->[150, 200]->[200, 290]->[300, 400]->NULL
atreus@MacBook-Pro %