Skip to content

Latest commit

 

History

History
165 lines (111 loc) · 5.84 KB

LinearArrayAllocator.md

File metadata and controls

165 lines (111 loc) · 5.84 KB

对rCore_tutorial 第四章：内存管理 part1 尝试了简单的线性数组方式

原方式为 线段树、
改为 线性数组

有什么变化：

不理想的变化：运行效率变低、看起来不够那么fashion、放弃了一些优化的想法、

理想的变化：肉眼可见的简单、逻辑清晰、易于理解、对第一次接触学习人员的友好、属于蛮力算法、

总结：侧重点不同、添加线性数组方式、为了继续降低初次学习这方面知识人员的学会阈值、

详细内容(废话)如下↓

物理内存管理

前提

  1. 可用物理内存地址
  2. 物理页帧大小
  3. 可用物理页数目

需要做的行为

  1. 把目前未被组织起来的物理内存地址资源、用结构组织起来、叫做初始化、
  2. 把已组织起来的资源、建立分配规则、
  3. 把已组织起来的资源、建立收回规则、

规则的语义描述、

前提： 当我们把资源组织起来后、我们所拥有的能力是：

  • 连续的物理页号
  • 通过物理页号能对应的物理地址范围

初始化：

目的：把资源用数据结构组织起来、结构化后、方便后续的使用

问题：

  • 用什么结构
  • 怎么组织

思考过程：

  1. 看需求选择数据结构
  2. 目前的情况是、物理内存就在那里、就像一排排椅子、在一个有序的活动中、怎么坐是有规则的、不能想坐哪里坐哪里、我们要管理人员落座、需要一个本本、记录一下情况、哪里已经坐人了、哪里没坐人、哪里能坐、哪里不能坐、都要明明白白的、现在就是要初始化这么一个本子、

分配 alloc：

目的：分配出去一个物理页帧
问题：

  • 分配哪一个页帧
  • 怎么分配、
  • 有什么输入、
  • 有什么输出、

思考过程：

  1. 分配哪一个物理页、好像都没什么关系、因为还有上一层的虚拟地址、所以无差别看待物理地址、于是可以选择只要是能分配的就分配出去就好。

  2. 怎么分配、通过物理页帧号、去计算分配一个地址、

  3. 需要有什么？应该不需要、

  4. 需要有什么输出么、需要、需要给出去页帧号

回收 dealloc

目的：回收一个指定的物理页帧
问题：

  • 怎么回收

思考过程：

  1. 理论上我们在本子上把占用的状态改一下就好了

LinearArrayAllocator 具体实现

1、定义一个结构

pub struct LinearArrayAllocator {
    ppns : [u8;MAX_PHYSICAL_PAGES],
    offset:usize,
}

ppns就是我们的线性数组了、一共有最大的物理页帧数大小、这就是我们上文所说的小本子了、

offset是有一些说法的、因为我们的物理地址不是从0开始的（物理地址开始的位置是0x80_200_000、）、offset的值是以物理地址为参考的、而我们定义的本子范围确是从0开始计算、所以也不麻烦、加上一个偏移就好了、或者需要理解为y=ax+b中的b、很有用、

功能的实现

一、init

pub fn init (&mut self,l:usize,r:usize)

pub fn init (&mut self,l:usize,r:usize) {
        self.offset = l-1;                   // 计算出偏移值
        let usedppn= MAX_PHYSICAL_PAGES+l-r; // 计算之前有多少已被占用
        for i in 0..usedppn {                // 把已被占用的页帧记录上
            self.ppns[i] = 1;
        }
    }

我们接收一个需要初始化的页帧号范围[l,r)、左闭右开、 （这时是物理地址参考）

offset被设置为l-1、是表示物理地址从0开始要偏移这么多、下一个才到达可用的首个页号

因为我们的规矩、默认了有一些内存地址不可用、比如被kernel占用的空间、当我们接收到可用的地址时、在记录的本子上、必然不能在第一页就开始写字、这是用上offset调整到正确的位置、是必要的、

回到我们本子上的序号、实际情况是比（l-物理地址开始的位置的）页号还小的页号都已经被占用了、

接下来我们在本子上、把已被占用的位置都标记上1、当作已占用的意思。

这样基本上就简单的初始化完成了、

我这个表达可能不够好、但事实确实这样的事、关键要分清、实际的物理空间、和我们本子上的序号、

（offset的值包含了我们kernel的页帧号的范围）

二、 alloc

pub fn alloc (&mut self) -> usize

pub fn alloc (&mut self) -> usize {
        let mut freeppn = 0;
        for i in 0..MAX_PHYSICAL_PAGES {
            if self.ppns[i] == 0 {
                freeppn = i + self.offset;
                self.ppns[i] = 1;
                break;
            }
        }
        if freeppn == 0 {
            panic!("physical memory depleted!");
        }
        freeppn
    }

当我们要分配一个页帧出去时、我们要看哪里可以分配、很纯粹的想法、如果我们顺序的找可用的资源、找到第一个给出去就好了、

定义一个freeppn代表要分配出去的可用页帧号、初始值为0、但0号必不可用、所以最后要给出去时、看一眼freeppn是否还是0、如果是那么就表示、目前可能没有可用的页帧号了、也就是满了、

接下来我们在整个本子上查找、看看哪个页空闲、可以被分配出去、本子上值为0就代表可用、找到后、加上个偏移值、就是应该被分配出去的页号了、

二、 dealloc

pub fn dealloc (&mut self,n: usize)

pub fn dealloc (&mut self,n: usize) {
        let p = n - self.offset;
        self.ppns[p] = 0;
    }

外面接受一个要被收回的页帧号、

我们用这个页帧号减去偏移值

然后在设置本子上、可用、就基本结束了

总体上没多少东西、想把过程写出来看上去有点多、表述能力训练不够、望大家捡有用的看吧、