本科生实验报告

实验课程: 操作系统

任课教师: 刘宁

实验题目:内存管理

专业名称: 信息与计算科学

学生姓名:罗弘杰

学生学号: 22336173

实验地点: 实验中心D503

实验时间: 2024/3/15

Section 1 实验概述

在本次实验中，我们首先学习如何使用位图和地址池来管理资源。然后，我们将实现在物理地址空间下的内存管理。接着，我们将会学习并开启二级分页机制。在开启分页机制后，我们将实现在虚拟地址空间下的内存管理。

本次实验最精彩的地方在于分页机制。基于分页机制，我们可以将连续的虚拟地址空间映射到不连续的物理地址空间。同时，对于同一个虚拟地址，在不同的页目录表和页表下，我们会得到不同的物理地址。这为实现虚拟地址空间的隔离奠定了基础。但是，本实验最令人困惑的地方也在于分页机制。开启了分页机制后，程序中使用的地址是虚拟地址。我们需要结合页目录表和页表才能确定虚拟地址对应的物理地址。而我们常常会忘记这一点，导致了我们不知道某些虚拟地址表示的具体含义。

Section 2 预备知识与实验环境

略

Section 3 实验任务

实验任务1：

复现实验7指导书中“物理页内存管理”一节的代码，实现物理页内存的管理，

具体要求如下：

结合代码分析位图，地址池，物理页管理的初始化过程，以及物理页进行分配和释放的实现思路。
构造测试用例来分析物理页内存管理的实现是否存在bug。如果存在，则尝试修复并再次测试。否则，结合测试用例简要分析物理页内存管理的实现的正确性。

复现“二级分页机制”一节的代码，结合代码来分析我们开启分页机制的三步方案、

实验任务2：

复现实验7指导书中“二级分页机制”一节的代码，实现二级分页机制，具体要求如下：

实现内存的申请和释放，保存实验截图并对能够在虚拟地址空间中进行内存管理，截图并给出过程解释（比如：说明哪些输出信息描述虚拟地址，哪些输出信息描述物理地址）。注意：建议使用的物理地址或虚拟地址信息与学号相关联（比如学号后四位作为页内偏移），作为报告独立完成的个人信息表征。
相比于一级页表，二级页表的开销是增大了的，但操作系统中往往使用的是二级页表而不是一级页表。结合你自己的实验过程，说说相比于一级页表，使用二级页表会带来哪些优势。

实验任务3：

复现“虚拟页内存管理”一节的代码，完成如下要求。

结合代码分析虚拟页内存分配的三步过程和虚拟页内存释放。
构造测试例子来分析虚拟页内存管理的实现是否存在bug。如果存在，则尝试修复并再次测试。否则，结合测例简要分析虚拟页内存管理的实现的正确性。
在pde（页目录项）和pte（页表项）的虚拟地址构造中，我们使用了第1023个页目录项。第1023个页目录项指向了页目录表本身，从而使得我们可以构造出pde和pte的虚拟地址。现在，我们将这个指向页目录表本身的页目录项放入第1000个页目录项，而不再是放入了第1023个页目录项。然后，同学们需要借助于这个第1000个页目录项，构造出第141个页目录项的虚拟地址和第891个页目录项指向的页表中的第109个页表项的虚拟地址。

实验任务4：

选做内容，如果完成，可附加实验完成度评分）在Assignment 3的基础上，实现一种理论课上学习到的虚拟内存管理中的页面置换算法，在虚拟页内存中实现页面的置换，比如下面所列算法的其中一种:

先进先出页面置换(FIFO).
最优页面置换(OPR).
最近最少使用页面置换(LRU)
最不经常使用页面置换(LFU)。

上述置换算法的细节参见理论课教材(《操作系统概念》，原书第9版，中文)第272-280页，你也可以实现一种自己设计的置换算法。要求:描述你的设计思路并展示页面置换结果的截图(也可以统计缺页错误发生的次数作为输出）。

Section 4 实验步骤与实验结果

————————- 实验任务1————————-

任务要求：

复现实验7指导书中“物理页内存管理”一节的代码，实现物理页内存的管理，

具体要求如下：

结合代码分析位图，地址池，物理页管理的初始化过程，以及物理页进行分配和释放的实现思路。
构造测试用例来分析物理页内存管理的实现是否存在bug。如果存在，则尝试修复并再次测试。否则，结合测试用例简要分析物理页内存管理的实现的正确性。
（不强制要求，对实验完成度评分无影响）如果你有想法，可以在自己的理解的基础上，参考ucore，《操作系统真象还原》，《一个操作系统的实现》等资料来实现自己的物理页内存管理。在完成之后，你需要指明相比指导书，你实现的物理页内存管理的特点。

代码分析

class BitMap
{
public:
    // 被管理的资源个数，bitmap的总位数
    int length;
    // bitmap的起始地址
    char *bitmap;
public:
    // 初始化
    BitMap();
    // 设置BitMap，bitmap=起始地址，length=总位数(即被管理的资源个数)
    void initialize(char *bitmap, const int length);
    // 获取第index个资源的状态，true=allocated，false=free
    bool get(const int index) const;
    // 设置第index个资源的状态，true=allocated，false=free
    void set(const int index, const bool status);
    // 分配count个连续的资源，若没有则返回-1，否则返回分配的第1个资源单元序号
    int allocate(const int count);
    // 释放第index个资源开始的count个资源
    void release(const int index, const int count);
    // 返回Bitmap存储区域
    char *getBitmap();
    // 返回Bitmap的大小
    int size() const;
private:
    // 禁止Bitmap之间的赋值
    BitMap(const BitMap &) {}
    void operator=(const BitMap&) {}
};

class AddressPool
{
public:
    BitMap resources;
    int startAddress;
public:
    AddressPool();
    // 初始化地址池，参数为位图的起始地址，长度，以及地址池的开始地址
    void initialize(char *bitmap, const int length,const int startAddress);
    // 从地址池中分配count个连续页，成功则返回第一个页的地址，失败则返回-1
    int allocate(const int count);
    // 释放若干页的空间
    void release(const int address, const int amount);
};

class MemoryManager
{
public:
    // 可管理的内存容量
    int totalMemory;
    // 内核物理地址池
    AddressPool kernelPhysical;
    // 用户物理地址池
    AddressPool userPhysical;
public:
    MemoryManager();

    // 初始化地址池
    void initialize();

    // 从type类型的物理地址池中分配count个连续的页
    // 成功，返回起始地址；失败，返回0
    int allocatePhysicalPages(enum AddressPoolType type, const int count);

    // 释放从paddr开始的count个物理页
    void releasePhysicalPages(enum AddressPoolType type, const int paddr, const int count);

    // 获取内存总容量
    int getTotalMemory();

};

可以看到这三个类是由底层到高层的关系，在初始化的时候内存管理器的初始化函数，会计算一些关键的参数（位图的起始，地址空间的页数，地址空间的开始），然后调用地址池的初始函数，地址池的初始化函数除了规定该地址池的起始地址，还会初始化该地址处的位图，调用位图的初始化函数，其中，位图的初始化函数会计算页数所需要的位图的大小，然后调用Memset在其起始地址开辟一定大小的空间

// 内存管理器的初始化函数
    int usedMemory = 256 * PAGE_SIZE + 0x100000;
    if(this->totalMemory < usedMemory) {
        printf("memory is too small, halt.\n");
        asm_halt();
    }
    // 剩余的空闲的内存
    int freeMemory = this->totalMemory - usedMemory;

    int freePages = freeMemory / PAGE_SIZE;
    int kernelPages = freePages / 2; //计算可用的物理页的页数，平均分为内核空间和进程空间
    int userPages = freePages - kernelPages;

    int kernelPhysicalStartAddress = usedMemory;  //地址池的开始地址，也就是物理空间的起始
    int userPhysicalStartAddress = usedMemory + kernelPages * PAGE_SIZE;

    int kernelPhysicalBitMapStart = BITMAP_START_ADDRESS;  //位图开始地址
    int userPhysicalBitMapStart = kernelPhysicalBitMapStart + ceil(kernelPages, 8);

    kernelPhysical.initialize((char *)kernelPhysicalBitMapStart, kernelPages, kernelPhysicalStartAddress);
    userPhysical.initialize((char *)userPhysicalBitMapStart, userPages, userPhysicalStartAddress);

// 地址池的初始化函数
void AddressPool::initialize(char *bitmap, const int length, const int startAddress)
{
    resources.initialize(bitmap, length);
    this->startAddress = startAddress;
}

//位图的初始化函数
void BitMap::initialize(char *bitmap, const int length)
{
    this->bitmap = bitmap;
    this->length = length;

    int bytes = ceil(length, 8); //每一个字节对应一个页数，所以要计算除以8的天花板
    memset(bitmap, 0, bytes);

}

物理页分配和释放：

由于分配和释放几乎是类似而相反的操作，所以以下只分析分配的代码

//内存管理器的分配函数，参数是地址空间的类型，需要的页数（页内存管理）
int MemoryManager::allocatePhysicalPages(enum AddressPoolType type, const int count)
{
    int start = -1;

    if (type == AddressPoolType::KERNEL)
    {
        start = kernelPhysical.allocate(count); //调用该地址池的分配函数
    }
    else if (type == AddressPoolType::USER)
    {
        start = userPhysical.allocate(count);
    }

    return (start == -1) ? 0 : start;
}

// 从地址池中分配count个连续页
int AddressPool::allocate(const int count)
{
    uint32 start = resources.allocate(count);  //查看位图中的记录，是否存在这样连续的内存页
    return (start == -1) ? -1 : (start * PAGE_SIZE + startAddress);
}


//位图的分配函数
int BitMap::allocate(const int count)
{
    if (count == 0)
        return -1;

    int index, empty, start;

    index = 0;
    while (index < length)
    {
        // 越过已经分配的资源
        while (index < length && get(index))
            ++index;

        // 不存在连续的count个资源
        if (index == length)
            return -1;

        // 找到1个未分配的资源
        // 检查是否存在从index开始的连续count个资源
        empty = 0;
        start = index;
        while ((index < length) && (!get(index)) && (empty < count))
        {
            ++empty;
            ++index;
        }

        // 存在连续的count个资源
        if (empty == count)
        {
            for (int i = 0; i < count; ++i)
            {
                set(start + i, true);
            }

            return start;
        }
    }

    return -1;
}

总的来说，内存管理器会根据内存空间的类型调用地址池的内存分配函数，在地址池中，位图实际上是用来记录页数是否已经分配，分配了置为1，没分配置为0，所以查看位图中是否存在这样数量的连续内存页就可以确定是否可以分配，可以的话，通过计算位图中的index*pagesize+startaddress就可以正确来到可以满足要求的地址开始位置。

测试分析

测试代码：

void first_thread(void *arg)
{
    //测试地址管理器是否正常工作
    uint32 a =memoryManager.allocatePhysicalPages(AddressPoolType::USER, 3);
    uint32 b =memoryManager.allocatePhysicalPages(AddressPoolType::USER, 16000);/
    uint32 c =memoryManager.allocatePhysicalPages(AddressPoolType::KERNEL, 1);
    uint32 d =memoryManager.allocatePhysicalPages(AddressPoolType::KERNEL, 16000);
    uint32 e =memoryManager.allocatePhysicalPages(AddressPoolType::USER, 2);
    
    printf("trying to allocate 3 page in USER space and succeed at a: %x\n", a);
    printf("trying to allocate 16000 page in USER space and fail from b: %x\n", b);
    printf("trying to allocate 1 page in KERNEL space and succeed at c: %x\n", c);
    printf("trying to allocate 16000 page in kERNEL space and fail from d: %x\n", d);
    printf("trying to allocate 2 page in USER space and succeed at e: %x\n", e);
    asm_halt();
}

实验结果：

可以看到地址返回都是正确的，而且可以判断页数是否足够，不足够的话就不会分配，在下一侧分配的时候，根据连续内存分配的法则，会接着最近的可用地址空间来分配（由最后一个测试分配可以看出）。

————————- 实验任务2————————-

任务要求：

复现实验7指导书中“二级分页机制”一节的代码，实现二级分页机制，具体要求如下：

实现内存的申请和释放，保存实验截图并对能够在虚拟地址空间中进行内存管理，截图并给出过程解释（比如：说明哪些输出信息描述虚拟地址，哪些输出信息描述物理地址）。注意：建议使用的物理地址或虚拟地址信息与学号相关联（比如学号后四位作为页内偏移），作为报告独立完成的个人信息表征。
相比于一级页表，二级页表的开销是增大了的，但操作系统中往往使用的是二级页表而不是一级页表。结合你自己的实验过程，说说相比于一级页表，使用二级页表会带来哪些优势。

思路分析：

本实验在32位实模式下进行，具有32位地址空间，设计的二级分页机制为，1个页目录具有1024个页表项（大小为4B），每一个页表项有1024个物理页（大小也为4B）,每一个物理页大小为4KB.

由此1024* 1024*4KB = 32GB, 恰好是32位的地址空间，高10位负责在页目录中缺点页目录项，中10位负责在页表项中确定物理页的序号，最后12位是在该物理页中的偏移地址。

地址转换过程：

给定一个虚拟地址，先取31-22位，其数值乘4后得到页目录表项在页目录表的偏移地址。这个偏移地址加上页目录表的物理地址后得到页目录项的物理地址。
取页目录项中的内容，得到页表的物理地址。页表的物理地址加上21-12位乘4的结果后，得到页表项的物理地址。
取页表项的内容，即物理页的物理地址，加上11-0位的内容后便得到实际的物理地址。

实验步骤：

开启二级分页的3个步骤：

规划好页目录表和页表在内存中的位置，然后初始化。
将页目录表的地址写入cr3。
将cr0的PG位置1。

第一步，规划好页目录表和页表在内存中的位置并写入内容：

首先，我们需要明确一点，页目录表和页表是需要在内存中特意地划分出位置来存放的。所以，我们需要在内存中指定页目录表和页表存放的位置。同时，页目录表和页表的物理地址必须是4KB的整数倍，也就是低12位为0。

规定了页目录表的位置后，我们根据线性地址空间的大小来确定需要分配的页表的数量和位置，不必一开始就分配完1024个页表给页目录表。规划好了页目录表的位置后，我们向页目录表中写入页表对应的页目录项。页目录项的结构如下。

开始地址规划：0~1MB将会是内核代码段，其中我们会简单地使用恒等映射将物理页化为虚拟页，然后页目录会在1MB开始，

#define PAGE_DIRECTORY 0x100000  //
void MemoryManager::openPageMechanism()
{
    // 页目录表指针
    int *directory = (int *)PAGE_DIRECTORY;
    //线性地址0~4MB对应的页表
    int *page = (int *)(PAGE_DIRECTORY + PAGE_SIZE);

    // 初始化页目录表
    memset(directory, 0, PAGE_SIZE);
    // 初始化线性地址0~4MB对应的页表
    memset(page, 0, PAGE_SIZE);

    int address = 0;
    // 将线性地址0~1MB恒等映射到物理地址0~1MB
    for (int i = 0; i < 256; ++i)
    {
        // U/S = 1, R/W = 1, P = 1
        page[i] = address | 0x7;
        address += PAGE_SIZE;
    }

    // 初始化页目录项

    // 0~1MB
    directory[0] = ((int)page) | 0x07;
    // 3GB的内核空间
    directory[768] = directory[0];
    // 最后一个页目录项指向页目录表
    directory[1023] = ((int)directory) | 0x7;

    // 初始化cr3，cr0，开启分页机制
    asm_init_page_reg(directory);

    printf("open page mechanism\n");
    
}

第二步：将页目录表的地址写入cr3寄存器；

第三步，将cr0的PG位置1

这两步通过汇编函数执行

asm_init_page_reg:
    push ebp
    mov ebp, esp

    push eax

    mov eax, [ebp + 4 * 2]
    mov cr3, eax ; 放入页目录表地址
    mov eax, cr0
    or eax, 0x80000000
    mov cr0, eax           ; 置PG=1，开启分页机制

    pop eax
    pop ebp

    ret

实验结果：

实现内存的申请和释放，保存实验截图并对能够在虚拟地址空间中进行内存管理，截图并给出过程解释（比如：说明哪些输出信息描述虚拟地址，哪些输出信息描述物理地址）。注意：建议使用的物理地址或虚拟地址信息与学号相关联（比如学号后四位作为页内偏移），作为报告独立完成的个人信息表征。
相比于一级页表，二级页表的开销是增大了的，但操作系统中往往使用的是二级页表而不是一级页表。结合你自己的实验过程，说说相比于一级页表，使用二级页表会带来哪些优势。

首先使用一级页表会导致所有的页表是连续存放的，需要开辟需要的空间以备使用，在进程比较多，进程页表会产生大量的连续内存开销，给操作系统内存管理带来负担；使用二级页表，由于页表是离散存放的，不需要一整片的连续内存消耗

使用二级页表的话可以在需要的时候才开辟页表内存，这减少了内存消耗，比如本来需要20位的一级页表，只需要10位的页目录表就可以管理，减少了1024倍内存消耗

————————- 实验任务3————————-

任务要求：

复现“虚拟页内存管理”一节的代码，完成如下要求。
- 结合代码分析虚拟页内存分配的三步过程和虚拟页内存释放。
- 构造测试例子来分析虚拟页内存管理的实现是否存在bug。如果存在，则尝试修复并再次测试。否则，结合测例简要分析虚拟页内存管理的实现的正确性。
- 在pde（页目录项）和pte（页表项）的虚拟地址构造中，我们使用了第1023个页目录项。第1023个页目录项指向了页目录表本身，从而使得我们可以构造出pde和pte的虚拟地址。现在，我们将这个指向页目录表本身的页目录项放入第1000个页目录项，而不再是放入了第1023个页目录项。然后，同学们需要借助于这个第1000个页目录项，构造出第141个页目录项的虚拟地址和第891个页目录项指向的页表中的第109个页表项的虚拟地址。
- （不做要求，对评分没有影响）如果你有想法，可以在自己的理解的基础上，参考ucore，《操作系统真象还原》，《一个操作系统的实现》等资料来实现自己的虚拟页内存管理。在完成之后，你需要指明相比较于本教程，你的实现的虚拟页内存管理的特点所在。
最后将结果截图并说说你是怎么做的。

结合代码分析虚拟页内存分配的三步过程和虚拟页内存释放：

在任务二的基础上我们已经实现了二级分页机制，并通过cr3寄存器开启了分页机制，之后我们的传入的虚拟地址都需要转化位物理地址才能被cpu正常访问。我们需要维护虚拟地址和物理地址的对应关系。当我们进行页内存分配时，需要分别标识虚拟地址的分配状态和物理地址的分配状态，由此而产生了两种地址池——虚拟地址池和物理地址池。当我们需要进行连续的页内存分配时

在页分配的时候：

在虚拟地址中分配足够的连续虚拟页；
在物理地址池中为每一个虚拟地址分配相应大小的物理页；
在页目录表和页表中维护对应关系（对于二级页表）；

负责页内存分配的函数如下所示。

/*地址管理器中的地址分配函数；
    1： 调用虚拟地址池的地址分配函数，获得连续的虚拟地址页
    2： 依次为每一个虚拟页指定物理页，循环：
    	 	从物理地址池中分配一个物理页
    		为虚拟页建立页目录项和页表项，使虚拟页内的地址经过分页机制变换到物理页内。
    	   	若中间产生分配失败，释放前面已经分配的虚拟页和物理页表*/
int MemoryManager::allocatePages(enum AddressPoolType type, const int count)
{
    // 第一步：从虚拟地址池中分配若干虚拟页
    int virtualAddress = allocateVirtualPages(type, count);
    if (!virtualAddress)//如果不是内核虚拟页，则会在这一步退出
    {
        return 0;
    }

    bool flag;
    int physicalPageAddress;
    int vaddress = virtualAddress;

    // 依次为每一个虚拟页指定物理页
    for (int i = 0; i < count; ++i, vaddress += PAGE_SIZE)
    {
        flag = false;
        // 第二步：从物理地址池中分配一个物理页
        physicalPageAddress = allocatePhysicalPages(type, 1);
        if (physicalPageAddress)
        {
            //printf("allocate physical page 0x%x\n", physicalPageAddress);
            
            // 第三步：为虚拟页建立页目录项和页表项，使虚拟页内的地址经过分页机制变换到物理页内。
            flag = connectPhysicalVirtualPage(vaddress, physicalPageAddress);
        }
        else
        {
            flag = false;
        }
        // 分配失败，释放前面已经分配的虚拟页和物理页表
        if (!flag)
        {
            // 前i个页表已经指定了物理页
            releasePages(type, virtualAddress, i);
            // 剩余的页表未指定物理页
            releaseVirtualPages(type, virtualAddress + i * PAGE_SIZE, count - i);
            return 0;
        }
    }

    return virtualAddress; 
  
    \* 虚拟地址分配，目前只实现了内核虚拟页，会调用虚拟地址池的分配函数*\
 int allocateVirtualPages(enum AddressPoolType type, const int count)
{
    int start = -1;

    if (type == AddressPoolType::KERNEL)
    {
        start = kernelVrirtual.allocate(count);
    }

    return (start == -1) ? 0 : start;
}

关键是建立虚拟页和物理页的对应关系：

考虑一个虚拟地址virtual，变换过程如下所示。

构造页目录项的过程：

在本实验中，页目录的第1023页指向页目录，页目录作为页表的第1023个物理页指向页目录，后面的页面偏移确定虚拟地址的页表地址，等于虚拟页的页表序号乘以其大小（4B），由此得到toPDE

构造页表项pte的过程：pte的高10位在页目录表中查询仍然指向页目录表本身，然后中间10位在页目录表中查询指向的页表序号，也就是虚拟地址的【31：22】，最后是在页表中查询物理页的地址，这个是虚拟地址的【21：12】，大小为32位=4B,所以乘以4

int toPDE(const int virtualAddress)
{
    return (0xfffff000 + (((virtualAddress & 0xffc00000) >> 22) * 4));
} //前20位分别是查询页目录的1023个页表（也就是页目录本身），该页表的1023个页（还是页目录），最后的页内偏移获得对应页表的地址（也就是31：22的内容*4）

int toPTE(const int virtualAddress)
{
    return (0xffc00000 + ((virtualAddress & 0xffc00000) >> 10) + (((virtualAddress & 0x003ff000) >> 12) * 4));
}// 高10位要找页目录表在页目录表中的位置，中间10位找页表在页目录表中的位置，最后12位是物理页在该页表中的地址（注意不是序号）

bool MemoryManager::connectPhysicalVirtualPage(const int virtualAddress, const int physicalPageAddress)
{
    // 计算虚拟地址对应的页目录项和页表项
    int *pde = (int *)toPDE(virtualAddress);
    int *pte = (int *)toPTE(virtualAddress);

    // 页目录项无对应的页表，先分配一个页表
    if(!(*pde & 0x00000001)) //然后检查页目录项是否有效（即最低位是否为1），如果无效则分配一个新的页表，并将页目录项指向新分配的页表。
    {
        // 从内核物理地址空间中分配一个页表
        int page = allocatePhysicalPages(AddressPoolType::KERNEL, 1);
        if (!page)
            return false;

        // 使页目录项指向页表
        *pde = page | 0x7;
        // 初始化页表
        char *pagePtr = (char *)(((int)pte) & 0xfffff000);
        memset(pagePtr, 0, PAGE_SIZE);
    }

    // 使页表项指向物理页
    *pte = physicalPageAddress | 0x7;

    return true;
}

页内存释放

但我们在分配页内存时，如果遇到物理页无法分配的情况，之前成功分配的虚拟页和物理页都要释放。否则就会造成内存泄漏，这部分内存无法再被分配。

页内存的释放是页内存分配的过程，分两个步骤完成。

对每一个虚拟页，释放为其分配的物理页。
释放虚拟页。

void MemoryManager::releasePages(enum AddressPoolType type, const int virtualAddress, const int count)
{
    int vaddr = virtualAddress;
    int *pte, *pde;
    bool flag;
    const int ENTRY_NUM = PAGE_SIZE / sizeof(int);

    for (int i = 0; i < count; ++i, vaddr += PAGE_SIZE)
    {
        releasePhysicalPages(type, vaddr2paddr(vaddr), 1);

        // 设置页表项为不存在，防止释放后被再次使用
        pte = (int *)toPTE(vaddr);//由于指向的物理页已经不存在，所以需要标记为不可用
        *pte = 0;
    }

    releaseVirtualPages(type, virtualAddress, count);
}

int MemoryManager::vaddr2paddr(int vaddr)
{
    int *pte = (int *)toPTE(vaddr);
    int page = (*pte) & 0xfffff000;
    int offset = vaddr & 0xfff;
    return (page + offset);
}

void MemoryManager::releaseVirtualPages(enum AddressPoolType type, const int vaddr, const int count)
{
    if (type == AddressPoolType::KERNEL)
    {
        kernelVirtual.release(vaddr, count);
    }
}

构造测试例子来分析虚拟页内存管理的实现是否存在bug

分别分配5，100，10的物理页的3个内存，然后释放100的物理页，最后创建两个10的物理页；

1，查看虚拟页是否是连续的，二级页表下对应的物理页是否可以是离散的；

2，查看释放后的虚拟页和物理页是否是可被再利用的。

void first_thread(void *arg)
{

    char *p1 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 5);
    char *p2 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 100);
    char *p3 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 10);

    printf("%x %x %x\n", p1, p2, p3);

    memoryManager.releasePages(AddressPoolType::KERNEL, (int)p2, 100);
    char *p4 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 10);

    printf("%x\n", p4);

    char *p5 = (char *)memoryManager.allocatePages(AddressPoolType::KERNEL, 10);
    
    printf("%x\n", p5);

    asm_halt();
}

	P1:5	P2:100	P3:10
虚拟页开始	C010_0000h	C010_5000h	C016_9000h
物理页开始	0020_0000h	0020_5000h	0026_9000h

	P1:5	P2:100(已经释放)	P3:10	P4:10	P5:10
虚拟页开始	C010_0000h	C010_5000h	C016_9000h	C010_5000h	C010_F000h
物理页开始	0020_0000h	0020_5000h	0026_9000h	0020_5000h	0020_F000h

从以上测试可以看出，虚拟内存页是连续的，而在虚拟页和物理页释放以后，相应的空间可以被再利用。

在pde（页目录项）和pte（页表项）的虚拟地址构造中，我们使用了第1023个页目录项。第1023个页目录项指向了页目录表本身，从而使得我们可以构造出pde和pte的虚拟地址。现在，我们将这个指向页目录表本身的页目录项放入第1000个页目录项，而不再是放入了第1023个页目录项。、

然后，同学们需要借助于这个第1000个页目录项，构造出第141个页目录项的虚拟地址和第891个页目录项指向的页表中的第109个页表项的虚拟地址。

首先需要将页目录表放在页目录表中的1000处；

然后修改PDE, PTE的计算方法：

对于PDE, 其高10位是页目录表在页目录表中的位置，也就是1000，16进制为0x3e8乘以4得到地址为0xFA0,中间10位也是页目录表作为页表的位置所以也是0xFA0, 最后的是页表作为页内偏移在页目录表中的地址，是高10位乘以4；

对于PTE, 其高10位仍然是页目录表在页目录表中的位置0xFA0，中间10位是页表作为页目录项在页目录中的位置是virtua[31:22], 低12位是页表项作为物理页在页表中的页内偏移，也就是virtual[21:12]左移4位；

int toPDE(const int virtualAddress)
{
    return (0xfa0fa000 + (((virtualAddress & 0xffc00000) >> 22) * 4));
} //在下面的计算中，141相当于(virtualAddress & 0xffc00000) >> 22) 的输出

int toPTE(const int virtualAddress)
{
    return (0xfa000000 + ((virtualAddress & 0xffc00000) >> 10) + (((virtualAddress & 0x003ff000) >> 12) * 4));
    //在下面的计算中，891相当于((virtualAddress & 0xffc00000) >> 10)，109相当于((virtualAddress & 0x003ff000) >> 12)的输出
}

计算结果：

那么对于页目录中的第141(0x8D)个页目录项，其虚拟地址是0xfa0fa08d0;

对于第891(0x37B)个页目录项指向的页表中的第109(0x6d)个页表项的虚拟地址，是0xfa037b6d0;

————————- 实验任务4 ————————-

任务要求：

先进先出页面置换(FIFO).
最优页面置换(OPR).
最近最少使用页面置换(LRU)
最不经常使用页面置换(LFU)。

本实验尝试实现FIFO算法

思路分析：

维护一个队列，当物理页（虚拟页）不够的时候，将这个队列的队首页置换为新的页

由于在本实验虚拟页是从低处到高处连续分配的，实际上，可以简单地使用一个指针指向最早分配的虚拟页地址，在内存页不够的时候（缺页），将这个指针所指向的虚拟页回收，指向这个虚拟页的下一个虚拟页，不断重复知道获得足够的空内存页，然后分配给进程。注意本实验中虚拟页可用总数为15984个，所以可以分配一个15900的虚拟页给进程，然后开展后续的测试；

void second_thread(void *arg)
{   
    char* p1 = (char*)memoryManager.allocatePages(AddressPoolType::KERNEL, 15900);
    char* p2 = (char*)memoryManager.allocatePages(AddressPoolType::KERNEL, 10);
    char* p3 = (char*)memoryManager.allocatePages(AddressPoolType::KERNEL, 10);
    char* p4 = (char*)memoryManager.allocatePages(AddressPoolType::KERNEL, 10);

    printf("%x %x %x %x\n", p1);

    asm_halt();
}

    class MemoryManager
{
public:
    // 可管理的内存容量
    int totalMemory;
    // 内核物理地址池
    AddressPool kernelPhysical;
    // 用户物理地址池
    AddressPool userPhysical;
    // 内核虚拟地址池
    AddressPool kernelVirtual;

    unsigned int virtual_pages; //记录最早分配的虚拟页，在初始化函数中被初始化为kernel_virtual_strat,也就是0xC0100000

int MemoryManager::allocatePages(enum AddressPoolType type, const int count)
{
    // 第一步：从虚拟地址池中分配若干虚拟页
    if(count >15984){
        printf("No enougn pages in total!\n");
        return 0;  //物理页总数不够，没办法
    }
    int virtualAddress = allocateVirtualPages(type, count); //尝试分配内存页
    while(!virtualAddress){
        releasePages(type, virtual_pages, 1);
        virtual_pages += PAGE_SIZE;
        if(virtual_pages == (0x3e71000+0xC0100000)) //0x3E700是第15984页的末地址
            virtual_pages = KERNEL_VIRTUAL_START;
        virtualAddress = allocateVirtualPages(type, count); 
    }
    printf("the first virtual page to exchange is 0x%x\n",virtual_pages); 
    //打印准备抛弃的虚拟页
    

成果展示：

可以看到第一个线程使用15900个页，在0xc010000开始；

第二个线程请求10个页，这时候没有发生页错误（存在连续的10个页），所以第二个线程的开始是0xc3f1c000;

第三个线程请求10个页，发生缺页错误，需要抛弃第一个线程的10个页，所以按照FIFO的规则，抛弃第一个线程的10个页，这个时候指针来到0xc016400（起始加10页），

最后一个线程类似第三个线程，依然要抛弃10个页；

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

OS lab7 实现虚拟内存的内存管理

本科生实验报告

Section 1 实验概述

Section 2 预备知识与实验环境

Section 3 实验任务

实验任务1：

实验任务2：

实验任务3：

实验任务4：

Section 4 实验步骤与实验结果

————————- 实验任务1————————-

任务要求：

代码分析

测试分析

测试代码：

实验结果：

————————- 实验任务2————————-

任务要求：

思路分析：

实验步骤：

实验结果：

————————- 实验任务3————————-

任务要求：

结合代码分析虚拟页内存分配的三步过程和虚拟页内存释放：

在页分配的时候：

页内存释放

构造测试例子来分析虚拟页内存管理的实现是否存在bug

然后，同学们需要借助于这个第1000个页目录项，构造出第141个页目录项的虚拟地址和第891个页目录项指向的页表中的第109个页表项的虚拟地址。

计算结果：

————————- 实验任务4 ————————-

任务要求：

思路分析：

成果展示：

CATALOG

FEATURED TAGS