实验课程: 操作系统

实验名称: Lab9 malloc-free

学生姓名: 庄云皓
学生学号: 22336327

1. 实验要求

实现系统调用malloc和free。malloc用于分配任意字节的内存，free用于释放任意字节的内存。

按照教程中给的代码复现实验，并对加入同步互斥代码以保证保证动态内存分配时的线程安全。

2. 实验过程

基本思路

分配𝑠𝑖𝑧𝑒个字节的内存时的时候，我们需要找到一个𝑁，满足2^(𝑁−1)<𝑠𝑖𝑧𝑒≤2^𝑁

也就是从小到大搜索，找到第一个恰好不小于𝑠𝑖𝑧𝑒的arena。找到这样一个arena后，我们便返回arena的起始地址作为分配的结果。特别地，当没有arena能够包含𝑠𝑖𝑧𝑒个字节时，我们就分配连续的𝑀个页，使得(𝑀−1)×4096<𝑠𝑖𝑧𝑒≤𝑀×4096

返回这𝑀个页的起始地址作为分配的结果。

过程

先在setup函数中设置两个系统调用：

//设置4号系统调用
systemService.setSystemCall(4, (int)syscall_malloc);
//设置5号系统调用
systemService.setSystemCall(5, (int)syscall_free);

在system_call.cpp中加入

void* malloc(int size){
    return (void*)asm_system_call(4,size);
}
void free(void* address){
    asm_system_call(5,(int)address);
}

接着我们需要完善这两个系统调用函数：

void* syscall_malloc(intsize)和 void syscall_free(void*address)

void *syscall_malloc(int size)
{
    PCB *pcb = programManager.running;
    if (pcb->pageDirectoryAddress)
    {
        // 每一个进程有自己的ByteMemoryManager
        return pcb->byteMemoryManager.allocate(size);
    }
    else
    {
        // 所有内核线程共享一个ByteMemoryManager
        return kernelByteMemoryManager.allocate(size);
    }
}

void syscall_free(void *address)
{
    PCB *pcb = programManager.running;
    if (pcb->pageDirectoryAddress)
    {
        pcb->byteMemoryManager.release(address);
    }
    else
    {
        kernelByteMemoryManager.release(address);
    }
}

在memory.h中定义

// MemoryManager是在内核态调用的内存管理对象
class ByteMemoryManager
{

private:
    // 16, 32, 64, 128, 256, 512, 1024
    static const int MEM_BLOCK_TYPES = 7;       // 内存块的类型数目
    static const int minSize = 16;              // 内存块的最小大小
    int arenaSize[MEM_BLOCK_TYPES];             // 每种类型对应的内存块大小
    MemoryBlockListItem *arenas[MEM_BLOCK_TYPES]; // 每种类型的arena内存块的指针

public:
    ByteMemoryManager();
    void initialize();
    void *allocate(int size);  // 分配一块地址
    void release(void *address); // 释放一块地址

private:
    bool getNewArena(AddressPoolType type, int index);
};

ByteMemoryManager初始化：

ByteMemoryManager::ByteMemoryManager()
{
    initialize();
}

void ByteMemoryManager::initialize()
{
    int size = minSize;
    for (int i = 0; i < MEM_BLOCK_TYPES; ++i)
    {
        arenas[i] = nullptr;
        arenaSize[i] = size;
        size = size << 1;
    }
}

以下是内存分配的函数。

void *ByteMemoryManager::allocate(int size)
{
    int index = 0;
    while (index < MEM_BLOCK_TYPES && arenaSize[index] < size)
        ++index;

    PCB *pcb = programManager.running;
    AddressPoolType poolType = (pcb->pageDirectoryAddress) ? AddressPoolType::USER : AddressPoolType::KERNEL;
    void *ans = nullptr;

    if (index == MEM_BLOCK_TYPES)
    {
        // 上取整
        int pageAmount = (size + sizeof(Arena) + PAGE_SIZE - 1) / PAGE_SIZE;

        ans = memoryManager.allocatePages(poolType, pageAmount);

        if (ans)
        {
            Arena *arena = (Arena *)ans;
            arena->type = ArenaType::ARENA_MORE;
            arena->counter = pageAmount;
        }
    }
    else
    {
        //printf("---ByteMemoryManager::allocate----\n");
        if (arenas[index] == nullptr)
        {
            if (!getNewArena(poolType, index))
                return nullptr;
        }

        // 每次取出内存块链表中的第一个内存块
        ans = arenas[index];
        arenas[index] = ((MemoryBlockListItem *)ans)->next;

        if (arenas[index])
        {
            (arenas[index])->previous = nullptr;
        }

        Arena *arena = (Arena *)((int)ans & 0xfffff000);
        --(arena->counter);
        //printf("---ByteMemoryManager::allocate----\n");
    }

    return ans;
}

如果空闲arena链表为空，则需要从内核中分配一个页，写入元信息，然后将该页划分成一个个arena。

bool ByteMemoryManager::getNewArena(AddressPoolType type, int index)
{
    void *ptr = memoryManager.allocatePages(type, 1);

    if (ptr == nullptr)
        return false;

    // 内存块的数量
    int times = (PAGE_SIZE - sizeof(Arena)) / arenaSize[index];
    // 内存块的起始地址
    int address = (int)ptr + sizeof(Arena);

    // 记录下内存块的数据
    Arena *arena = (Arena *)ptr;
    arena->type = (ArenaType)index;
    arena->counter = times;
    // printf("---ByteMemoryManager::getNewArena: type: %d, arena->counter: %d\n", index, arena->counter);

    MemoryBlockListItem *prevPtr = (MemoryBlockListItem *)address;
    MemoryBlockListItem *curPtr = nullptr;
    arenas[index] = prevPtr;
    prevPtr->previous = nullptr;
    prevPtr->next = nullptr;
    --times;

    while (times)
    {
        address += arenaSize[index];
        curPtr = (MemoryBlockListItem *)address;
        prevPtr->next = curPtr;
        curPtr->previous = prevPtr;
        curPtr->next = nullptr;
        prevPtr = curPtr;
        --times;
    }

    return true;
}

接下来我们来实现内存释放。

内存释放非常简单，当我们释放一个动态分配的内存地址时，我们可以找到这个地址所在的页。然后通过这个页开头保存的元信息就能够找到这个地址对应的arena类型。最后将这个arena放到对应的空闲arena链表即可。

特别地，当一个页内的所有arena都被释放时，我们需要释放这个页。

教程中的代码有一些拼写问题和release没有指定内存池是kernel还是user的问题，进行了修改。

void ByteMemoryManager::release(void *address)
{
    // 由于Arena是按页分配的，所以其首地址的低12位必定0，
    // 其中划分的内存块的高20位也必定与其所在的Arena首地址相同
    Arena *arena = (Arena *)((int)address & 0xfffff000);

    if (arena->type == ARENA_MORE)
    {
        int address = (int)arena;

        memeoryManager.releasePage(address, arena->counter);
    }
    else
    {
        MemoryBlockListItem *itemPtr = (MemoryBlockListItem *)address;
        itemPtr->next = arenas[arena->type];
        itemPtr->previous = nullptr;

        if (itemPtr->next)
        {
            itemPtr->next->previous = itemPtr;
        }

        arenas[arena->type] = itemPtr;
        ++(arena->counter);

        // 若整个Arena被归还，则清空分配给Arena的页
        int amount = (PAGE_SIZE - sizeof(Arena)) / arenaSize[arena->type];
        // printf("---ByteMemoryManager::release---: arena->counter: %d, amount: %d\n", arena->counter, amount);

        if (arena->counter == amount)
        {
            // 将属于Arena的内存块从链上删除
            while (itemPtr)
            {
                if ((int)arena != ((int)itemPtr & 0xfffff000))
                {
                    itemPtr = itemPtr->next;
                    continue;
                }

                if (itemPtr->previous == nullptr) // 链表中的第一个节点
                {
                    arenas[arena->type] = itemPtr->next;
                    if (itemPtr->next)
                    {
                        itemPtr->next->previous = nullptr;
                    }
                }
                else
                {
                    itemPtr->previous->next = itemPtr->next;
                }

                if (itemPtr->next)
                {
                    itemPtr->next->previous = itemPtr->previous;
                }

                itemPtr = itemPtr->next;
            }

            memeoryManager.releasePage((int)address, 1);
        }
    }
}

由于进程有自己的内存空间，我们修改PCB，在PCB中加入 ByteMemeoryManager。

struct PCB
{
	...
    ByteMemoryManager byteMemoryManager; // 进程内存管理者
    ...
};

在pcb初始化函数中加上

1	thread->byteMemoryManager.initialize();

setup函数中

ByteMemoryManager kernelByteMemoryManager;
extern "C" void setup_kernel()
{

    ...
    kernelByteMemoryManager.initialize();
    ...
}

3. 关键代码

见上一部分

4. 实验结果

我们在这里加上延迟来展示没有实现互斥时发生的错误，同时把时间片轮转的ticks调低来增加并发度

void *ByteMemoryManager::allocate(int size)
{
	...
	ans = arenas[index];
        //设置延迟

        int delay = 0xfffffff;
        while(delay--);
	...
}

来看这个样例：

void second_thread(void *arg) {
    void* addr = malloc(50);
    printf("first_thread get addr0(50) %x\n", addr);
    void* addr1 = malloc(30);
    printf("first_thread get addr1(30) %x\n", addr1);
    free(addr);
  
    free(addr1);

}
void third_thread(void *arg) {
    void* addr2 = malloc(50);
    printf("second_thread get addr2(50) %x\n",addr2);
    free(addr2);
}

thread1和 tread2都malloc了50B,在tread1获取了ans之后延迟，并没有设置 arenas[index] = ((MemoryBlockListItem *)ans)->next;此时tread2被调度上处理机，获取了一样的地址。

分配了同样的地址会导致release的时候也无法回收，所以我们只看到了两个release.

无锁:

有锁：

在这里加上锁保证对arena数组的互斥访问

void *ByteMemoryManager::allocate(int size){
    ...
    else
    {
        bt_sem.P();
        printf("---ByteMemoryManager::allocate----\n");
        if (arenas[index] == nullptr)
        {

            if (!getNewArena(poolType, index))
                return nullptr;
            printf("getNewArena\n");
        }

        // 每次取出内存块链表中的第一个内存块
        ans = arenas[index];
        //设置延迟

        int delay = 0xfffffff;
        while(delay--);

  
        arenas[index] = ((MemoryBlockListItem *)ans)->next;

        if (arenas[index])
        {
            (arenas[index])->previous = nullptr;
        }

        Arena *arena = (Arena *)((int)ans & 0xfffff000);
        --(arena->counter);
        //printf("---ByteMemoryManager::allocate----\n");
        bt_sem.V();
    }
}

加锁之后在 thread1和 tread2都malloc了50B时分配的地址是不同的。可见实现了分配时的互斥。thread1在exit的时候回收了资源，所以 thread2malloc分配到的地址和thread1是一样的。

在其他需要互斥的地方加上信号量：

这里加上是为了保证在为进程分配内存的时候实现的互斥以及malloc分配空间>1024Byte时的分配

Semaphore semaphore;
void MemoryManager::initialize()
{
    semaphore.initialize(1);
    ...
}
int MemoryManager::allocatePages(enum AddressPoolType type, const int count)
{
    semaphore.P();
    // 第一步：从虚拟地址池中分配若干虚拟页
    int virtualAddress = allocateVirtualPages(type, count);
    ...
    semaphore.V();
    return virtualAddress;
}

对于进程来说，也能通过系统调用实现正常分配内存：

void first_process()
{
    void* addr = malloc(50);

    printf("first_process get addr0(50) %x\n", addr);
    void* addr1 = malloc(30);
    printf("first_process get addr1(30) %x\n", addr1);
    free(addr);
    free(addr1);
}

5. 总结

这次实验可以说比较综合，涉及到内存管理、系统调用、线程互斥等多方面的内容，虽然说整体难度不大只需要在教程给出的代码上进行修改但是还是要完全理解还是有些难度。实验中遇到了没有在setup.cpp函数中BytememoryManagemebt.initalize()，导致调用默认构造函数size都被初始化为0的问题。后来发现并解决了。实验教程中采用了不同大小的块进行动态内存分配，减少了碎片，可以说是很精巧的。