面试题：C语言指针的指针在操作系统底层模拟场景中的应用

数据结构定义

#include <stdint.h>

// 内存块信息结构体
typedef struct MemoryBlock {
    uintptr_t startAddress;
    size_t size;
    struct MemoryBlock* prev;
    struct MemoryBlock* next;
} MemoryBlock;

// 双向链表头结构体
typedef struct MemoryList {
    MemoryBlock* head;
    MemoryBlock* tail;
} MemoryList;

插入节点函数

// 插入节点到双向链表
void insertNode(MemoryList** listPtr, MemoryBlock* newNode) {
    MemoryList* list = *listPtr;
    if (!list) {
        list = (MemoryList*)aligned_alloc(alignof(MemoryList), sizeof(MemoryList));
        list->head = newNode;
        list->tail = newNode;
        newNode->prev = NULL;
        newNode->next = NULL;
        *listPtr = list;
        return;
    }
    // 插入到链表尾部
    newNode->prev = list->tail;
    newNode->next = NULL;
    list->tail->next = newNode;
    list->tail = newNode;
}

优化思路

内存对齐：使用aligned_alloc函数确保MemoryList结构体在分配内存时满足对齐要求。对于MemoryBlock结构体，由于其成员类型的对齐要求（uintptr_t和size_t通常是自然对齐），整体结构体自然满足对齐。在插入节点时，newNode的分配也应考虑对齐，可根据实际使用的内存分配函数（如aligned_alloc）来确保。
缓存一致性：尽量减少对链表频繁的跨缓存行操作。在插入节点时，由于是在链表尾部插入，对缓存影响相对较小。但如果链表较长，可考虑预取技术，例如在即将插入节点前，提前将list->tail所在缓存行预取到缓存中，减少访问内存的延迟。在C语言中，可使用编译器特定的预取指令（如GCC的__builtin_prefetch）。

删除节点函数

// 删除节点
void deleteNode(MemoryList** listPtr, MemoryBlock* nodeToDelete) {
    MemoryList* list = *listPtr;
    if (!list ||!nodeToDelete) {
        return;
    }
    if (nodeToDelete == list->head && nodeToDelete == list->tail) {
        free(list);
        *listPtr = NULL;
        free(nodeToDelete);
        return;
    }
    if (nodeToDelete == list->head) {
        list->head = nodeToDelete->next;
        list->head->prev = NULL;
        free(nodeToDelete);
        return;
    }
    if (nodeToDelete == list->tail) {
        list->tail = nodeToDelete->prev;
        list->tail->next = NULL;
        free(nodeToDelete);
        return;
    }
    nodeToDelete->prev->next = nodeToDelete->next;
    nodeToDelete->next->prev = nodeToDelete->prev;
    free(nodeToDelete);
}

优化思路

内存对齐：在释放节点内存时，确保使用与分配时相同的对齐方式，防止内存管理库出现对齐错误。例如使用free释放通过aligned_alloc分配的内存块。
缓存一致性：删除节点时，尽量减少对周围缓存行的影响。由于删除操作可能涉及到更新相邻节点的指针，这些相邻节点可能已经在缓存中，所以操作相对较友好。但如果链表较长，删除节点后，可能需要考虑对后续链表操作的缓存预取优化，以避免缓存缺失。同样可使用__builtin_prefetch指令。

星途面试题库

面试题：C语言指针的指针在操作系统底层模拟场景中的应用

知识考点

面试题答案

数据结构定义

插入节点函数

优化思路

删除节点函数

优化思路