🐳
uCore OS(on RISC-V64)实验指导书
  • Introduction
  • LAB0:ready~go!
    • 实验目的
    • 实验内容
    • 前导知识
      • 了解uCore
      • 了解RISC-V
      • 了解OS实验
      • 了解实验环境
      • 了解开发调试基本工具
      • 了解硬件模拟器
    • 配置环境
      • 安装虚拟环境
      • 安装开发工具
      • 安装硬件模拟器
      • 安装调试工具
  • LAB0.5:最小可执行内核
    • 实验目的
    • 实验内容
    • 练习
    • 内存布局
    • 链接脚本
    • 真正的入口点
    • 从SBI到stdio
    • 编译运行
    • 项目组成与执行流
  • LAB1:中断机制
    • 实验目的
    • 实验内容
    • 练习
    • RISC-V中断相关
    • 上下文处理
    • 中断处理程序
    • 时钟中断
    • 项目组成与执行流
  • LAB2:物理内存管理
    • 实验目的
    • 实验内容
    • 练习
    • 地址与页表
    • 物理内存探测
    • 以页为单位管理物理内存
    • 页面分配算法
    • 项目组成与执行流
  • LAB3:虚拟内存管理
    • 实验目的
    • 实验内容
    • 练习
    • 页面置换
    • PageFault
    • 使用多级页表
    • 页面置换机制
    • FIFO置换算法
    • 项目组成与执行流
  • LAB4:进程管理
    • 实验目的
    • 实验内容
    • 练习
    • 进程与线程
    • 相关结构体
    • 进程模块初始化
    • 进程切换
    • 项目组成与执行流
  • LAB5:用户程序
    • 实验目的
    • 实验内容
    • 练习
    • 用户进程
    • 用户程序
    • 创建并执行用户进程
    • 系统调用
    • 用户进程的退出和等待
    • 项目组成与执行流
  • LAB6:进程调度
    • 实验目的
    • 实验内容
    • 练习
    • 进程状态
    • 再次认识进程切换
    • 调度算法框架
    • 项目组成与执行流
  • LAB7:同步互斥
    • 实验目的
    • 实验内容
    • 练习
    • 同步互斥的基本概念
    • 信号量
    • 条件变量与管程
    • 项目组成与执行流
  • LAB8:文件系统
    • 实验目的
    • 实验内容
    • 练习
    • 文件系统介绍
    • 文件系统抽象层VFS
    • 硬盘文件系统SFS
    • 设备即文件
    • 从中断到终端
    • 项目组成与执行流
由 GitBook 提供支持
在本页
  • 关键数据结构与变量
  • 设计实现

这有帮助吗?

  1. LAB2:物理内存管理

页面分配算法

如果要在ucore中实现连续物理内存分配算法,则需要考虑的事情比较多,相对课本上的物理内存分配算法描述要复杂不少。下面介绍一下如果要实现一个FirstFit内存分配算法的大致流程。原理FirstFit内存分配算法上很简单,但要在ucore中实现,需要充分了解和利用ucore已有的数据结构和相关操作、关键的一些全局变量等。

关键数据结构与变量

first_fit分配算法需要维护一个查找有序(地址按从小到大排列)空闲块(以页为最小单位的连续地址空间)的数据结构,而双向链表是一个很好的选择。

libs/list.h定义了可挂接任意元素的通用双向链表结构和对应的操作,所以需要了解如何使用这个文件提供的各种函数,从而可以完成对双向链表的初始化/插入/删除等。

显然,我们可以通过free_area_t数据结构来完成对空闲块的管理。而default_pmm.c中定义的free_area变量就是干这个事情的。

kern/mm/pmm.h中定义了一个通用的分配算法的函数列表,用pmm_manager 表示。其中init函数就是用来初始化free_area变量的, first_fit分配算法可直接重用default_init函数的实现。init_memmap函数需要根据现有的内存情况构建空闲块列表的初始状态。何时应该执行这个函数呢?

通过分析代码,可以知道:

kern_init --> pmm_init-->page_init-->init_memmap--> pmm_manager->init_memmap

所以,default_init_memmap需要根据page_init函数中传递过来的参数(某个连续地址的空闲块的起始页,页个数)来建立一个连续内存空闲块的双向链表。这里有一个假定page_init函数是按地址从小到大的顺序传来的连续内存空闲块的。链表头是free_area.free_list,链表项是Page数据结构的base->page_link。这样我们就依靠Page数据结构中的成员变量page_link形成了连续内存空闲块列表。

设计实现

default_init_memmap函数将根据每个物理页帧的情况来建立空闲页链表,且空闲页块应该是根据地址高低形成一个有序链表。根据上述变量的定义,default_init_memmap可大致实现如下:

default_init_memmap(struct Page *base, size_t n) {
    struct Page *p = base;
    for (; p != base + n; p ++) {
        p->flags = p->property = 0;
        set_page_ref(p, 0);
    }
    base->property = n;
    SetPageProperty(base);
    nr_free += n;
    list_add(&free_list, &(base->page_link));
}

如果要分配一个页,那要考虑哪些呢?这里就需要考虑实现default_alloc_pages函数,注意参数n表示要分配n个页。另外,需要注意实现时尽量多考虑一些边界情况,这样确保软件的鲁棒性。比如

if (n > nr_free) {
return NULL;
}

这样可以确保分配不会超出范围。也可加一些 assert函数,在有错误出现时,能够迅速发现。比如 n应该大于0,我们就可以加上

assert(n \> 0);

这样在n<=0的情况下,ucore会迅速报错。firstfit需要从空闲链表头开始查找最小的地址,通过list_next找到下一个空闲块元素,通过le2page宏可以由链表元素获得对应的Page指针p。通过p->property可以了解此空闲块的大小。如果>=n,这就找到了!如果<n,则list_next,继续查找。直到list_next== &free_list,这表示找完了一遍了。找到后,就要从新组织空闲块,然后把找到的page返回。所以default_alloc_pages可大致实现如下:

static struct Page *
default_alloc_pages(size_t n) {
    if (n > nr_free) {
        return NULL;
    }
    struct Page *page = NULL;
    list_entry_t *le = &free_list;
    while ((le = list_next(le)) != &free_list) {
        struct Page *p = le2page(le, page_link);
        if (p->property >= n) {
            page = p;
            break;
        }
    }
    if (page != NULL) {
        list_del(&(page->page_link));
        if (page->property > n) {
            struct Page *p = page + n;
            p->property = page->property - n;
            list_add(&free_list, &(p->page_link));
        }
        nr_free -= n;
        ClearPageProperty(page);
    }
    return page;
}

default_free_pages函数的实现其实是default_alloc_pages的逆过程,不过需要考虑空闲块的合并问题。这里就不再细讲了。自行阅读代码。

看完了first fit算法了,就需要自己实现best fit算法了噢,思路都是一样的,依葫芦画瓢。

上一页以页为单位管理物理内存下一页项目组成与执行流

最后更新于4年前

这有帮助吗?