Introduction
这章介绍了“头甲龙”操作系统,主要是 rCore 的内存虚拟化技术,这里会尝试与 xv6 对比。rCore 书中介绍的开发流程如下
- 修改
linker.ld将应用程序的起始地址都改成一样的0x10000 - 为了使用 Rust 的堆数据结构,在内核中添加连续内存分配的功能
- 建立物理内存管理机制
- 建立页表机制
- 实现地址空间抽象
- 修改任务控制块和任务管理器,控制地址空间相关内容
- 修改已有的
trap_handler和sys_write适应页表隔离
动态内存分配
和 xv6 不同,rCore 为了能够使用 Rust 核心库中各种灵活的动态数据结构而在内核建立了动态内存分配机制。
在通常的应用程序中,一般会有一段可以动态增减的内存空间,也就是堆,运行的时候可以增加堆的空间存放新的元素,用完之后回收这一空间。应用通常会依赖标准库的函数来进行堆空间的分配,而标准库的函数通过系统调用来请求增加应用地址内堆空间的大小。
比如 xv6 的 sbrk 系统调用可以增加进程内存的大小,通过 uvmalloc 在需要时分配新的物理页,而在用户程序中新增了一个 umalloc.c 实现了 next fit 为基础的 malloc() 函数和 free() 函数。xv6 是没有使用任何 C 标准库的内容的。
Rust 堆数据结构
Rust 存在三类指针:
- 智能指针 (Smart Pointer):相比较普通指针有管理和控制功能
- 裸指针
*const T/*mut T: 编译器只会检查写是否允许,需要 unsafe 包裹 - 引用
&T/&mut T:本质地址范围,编译器会有借用检查
与动态分配相关的智能指针如下:
Box<T>:对标 C++ 的unique_ptr,在堆上分配一个类型为T的变量,自身保存在堆上那个位置,但是回收时会顺带释放堆上的变量。Rc<T>:类似 C++ 的shared_ptr,支持多个指向变量的不可变引用来访问同一个变量,同时也是引用计数,在堆上的另一个位置会维护变量被引用的次数,次数归零时释放堆上的变量。Arc<T>:功能类似Rc<T>但是支持多线程RefCell<T>:借用检查在运行时进行,违反借用规则会panic,可在其自身是不可变的情况下修改其内部的值。Mutex<T>:是一个互斥锁,在多线程中使用。它可以保护里层的堆上的变量同一时间只有一个线程能对它进行操作,从而避免数据竞争
Rust 可以直接使用的集合或容器类型
- 向量
Vec<T>: 类似 C++std::vector - B树实现的键值对容器
BTreeMap<K, V>: 类似 C++std::map,但后者通常使用红黑树实现 - B树实现的有序集合
BTreeSet<T>: 类似 C++std::set,但后者通常使用红黑树实现 - 链表
LinkedList<T>: 类似于 C++ 中的std::list - 双端队列
VecDeque<T>: 类似于 C++ 中的std::deque - 变长字符串
String: 类似于 C++ 中的std::string
在内核中支持动态内存分配
禁用标准库(即 no_std )的裸机平台上,核心库 core 没有动态内存分配的功能,这个时候就要考虑利用 alloc 库定义的接口来实现基本的动态内存分配器。
Rust 在 alloc crate 中设定了一套简洁规范的接口,只要实现了这套接口,内核就可以很方便地支持动态内存分配
动态内存分配器需要实现它提供的 GlobalAlloc Trait,这个 Trait 有两个必须实现的抽象接口:
// alloc::alloc::GlobalAlloc
pub unsafe fn alloc(&self, layout: Layout) -> *mut u8;
pub unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout);
第二个参数的类型 alloc::alloc::Layout 包含所需空间的大小 size ,以及返回地址的对齐要求 align 。这个对齐要求必须是一个 2 的幂次,单位为字节数,限制返回的地址必须是 align 的倍数
rCore 直接使用了一个已有的伙伴分配器,这是一个第三方 crate 而非自带标准库组件,所以需要在 Cargo.toml 中声明依赖
# os/Cargo.toml
buddy_system_allocator = "0.6"
而 alloc 是 Rust 自带的组件,属于特殊的编译器提供的 crate,而 no_std 程序需要显式引入它。
// os/src/main.rs
extern crate alloc;
现在还需要指定全局动态内存分配器,使用 #[global_allocator],LockedHeap 已经实现了 GlobalAlloc 要求的抽象接口了。
// os/src/mm/heap_allocator.rs
use buddy_system_allocator::LockedHeap;
use crate::config::KERNEL_HEAP_SIZE;
#[global_allocator]
static HEAP_ALLOCATOR: LockedHeap = LockedHeap::empty();
static mut HEAP_SPACE: [u8; KERNEL_HEAP_SIZE] = [0; KERNEL_HEAP_SIZE];
pub fn init_heap() {
unsafe { // 给动态内存分配器提供一块内存
HEAP_ALLOCATOR
.lock()
.init(HEAP_SPACE.as_ptr() as usize, KERNEL_HEAP_SIZE);
}
}
现在有了动态内存分配器,还需要处理分配失败的情况
// os/src/main.rs
#![feature(alloc_error_handler)]
// os/src/mm/heap_allocator.rs
#[alloc_error_handler]
pub fn handle_alloc_error(layout: core::alloc::Layout) -> ! {
panic!("Heap allocation error, layout = {:?}", layout);
}
然后就可以尝试使用 rust 的动态内存分配了,尝试在 rust_main.c 中调用 heap_test
由于 heap_test 所在的模块 heap_allocator 是私有模块,不能直接访问,所以需要在 os/src/mm/mod.rs 中添加一行
pub use heap_allocator::heap_test;
然后调用这个函数
pub fn rust_main(_hart_id: usize, dtb_pa: usize) -> ! {
...
mm::init();
mm::heap_test();
...
}
可以看到打印出了 heap_test passed! 信息
sodium@nas-MacBook-Air-13 os % make run | grep "heap"
info: component rust-src is up to date
info: component llvm-tools is up to date
Finished `release` profile [optimized + debuginfo] target(s) in 0.00s
Compiling os v0.1.0 (/Users/sodium/Developer/rCore/rCore-Tutorial-v3/os)
Finished `release` profile [optimized + debuginfo] target(s) in 0.42s
heap_test passed!
测试函数基本上是创建了 Box<T> 和 Vec<T> 等对象,然后检查其是否在 .bss 段上,并且表现是否正常
sv39 多级页表
硬件基础
SATP 寄存器(Supervision Address Translation and Protection)
[63:60]: Mode 地址转换模式- Mode=0: 不进行地址转换
- Mode=8: 按 Sv39 三级页表规则进行翻译
- Mode=9: Sv48
- Mode=10: Sv57
[59:44]: ASID 当前进程的 ASID (Address Space Identifier)- 用于区分不同进程的虚拟地址空间,不同的进程可以有同样的虚拟地址,但是映射的物理地址不同
- 但是 xv6 没有用到这个,而是使用
sfence.vma rs1, rs2清除 TLB 来防止错误的映射 - 其中
rs1: virtual address,rs2: ASID
[43:0]: PPN 第一级页表基地址的物理页号- root page table 的物理地址进行右移得到 PPN
sv39 的 VA 组成
63 39 38 30 29 21 20 12 11 0
+---------------+------------+------------+------------+-----------+
| sign extension| VPN[2] | VPN[1] | VPN[0] | offset |
+---------------+------------+------------+------------+-----------+
9 bits 9 bits 9 bits 12 bits
VA
│
├── VPN[2] ← 第一级索引,用于 L2 Page Table/Root Page Table
├── VPN[1] ← 第二级索引,用于 L1 Page Table
├── VPN[0] ← 第三级索引,用于 L0 Page Table
└── offset ← 页内偏移
sv39 的 PA 组成
63 56 55 30 29 21 20 12 11 0
+---------------+------------+------------+------------+-----------+
| / | PPN[2] | PPN[1] | PPN[0] | offset |
+---------------+------------+------------+------------+-----------+
26 bits 9 bits 9 bits 12 bits
PTE 的组成
63 54 53 28 27 19 18 10 9 8 7 6 5 4 3 2 1 0
+----------+----------+----------+----------+-----+-+-+-+-+-+-+-+-+
| reserved | PPN[2] | PPN[1] | PPN[0] | RSW |D|A|G|U|X|W|R|V|
+----------+----------+----------+----------+-----+-+-+-+-+-+-+-+-+
10 26 9 9 2 1 1 1 1 1 1 1 1
更多 xv6 出现过的 sv39 的内容可以查看链接:
地址相关的数据结构抽象与类型定义
物理地址、虚拟地址、物理页号和虚拟页号在 rCore 中有所定义,和 xv6 类似,都和64位无符号整型相关,由于只有一个字段,它们都属于元组结构体
// os/src/mm/address.rs
#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
pub struct PhysAddr(pub usize);
#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
pub struct VirtAddr(pub usize);
#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
pub struct PhysPageNum(pub usize);
#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq)]
pub struct VirtPageNum(pub usize);
rCore 中,它们 usize 可以相互转换,但是需要实现 trait
// os/src/mm/address.rs
const PA_WIDTH_SV39: usize = 56;
const PPN_WIDTH_SV39: usize = PA_WIDTH_SV39 - PAGE_SIZE_BITS;
impl From<usize> for PhysAddr {
fn from(v: usize) -> Self { Self(v & ( (1 << PA_WIDTH_SV39) - 1 )) }
}
impl From<usize> for PhysPageNum {
fn from(v: usize) -> Self { Self(v & ( (1 << PPN_WIDTH_SV39) - 1 )) }
}
impl From<PhysAddr> for usize {
fn from(v: PhysAddr) -> Self { v.0 }
}
impl From<PhysPageNum> for usize {
fn from(v: PhysPageNum) -> Self { v.0 }
}
注意到 usize 转成 PhysAddr 和 PhysPageNum 分别只保留了低56位和低44位,而 VirtAddr 和 VirtPageNum 类似,也只保留了有效的部分。
而这里的 v.0 表示访问元组结构体(内部字段不像普通结构体那样有名字,而是通过数字索引访问)的第0个字段,也就是 usize 类型,因为声明是 pub struct XXX(pub usize),所以不用考虑权限问题,可以直接访问字段。
实现完 From<T> 之后,rust 会自动为 T 实现 Into<U> trait,然后就可以使用下面的方法
U::from(_: T) // 从一个 T 类型的实例来构造一个 U 类型的实例
u.into() // 使用 u.into() 来将 U 类型实例转化为一个类型为 T 的实例,使用时需要显式指出目标类型
注意所有权也会跟着转移
fn main() {
let p = PhysPageNum(42);
let n: usize = p.into();
println!("{n}"); // 42
// println!("{}", p.0); // 编译错误:p 已经被移动
}
除了 usize 的转换, PhysAddr 和 PhysPageNum 之间也可以转换,虚拟地址同理
// os/src/mm/address.rs
impl PhysAddr {
pub fn page_offset(&self) -> usize { self.0 & (PAGE_SIZE - 1) }
}
impl From<PhysAddr> for PhysPageNum {
fn from(v: PhysAddr) -> Self {
assert_eq!(v.page_offset(), 0);
v.floor()
}
}
impl From<PhysPageNum> for PhysAddr {
fn from(v: PhysPageNum) -> Self { Self(v.0 << PAGE_SIZE_BITS) }
}
相比之下,xv6 是直接使用了宏定义进行转换,并且没有额外定义 PA 和 VA
typedef uint64 pte_t;
typedef uint64 *pagetable_t; // 512 PTEs
// shift a physical address to the right place for a PTE.
#define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)
#define PTE2PA(pte) (((pte) >> 10) << 12)
#define PTE_FLAGS(pte) ((pte) & 0x3FF)
// extract the three 9-bit page table indices from a virtual address.
#define PXMASK 0x1FF // 9 bits
#define PXSHIFT(level) (PGSHIFT+(9*(level)))
#define PX(level, va) ((((uint64) (va)) >> PXSHIFT(level)) & PXMASK)
还有对不齐的情况,相比之下 xv6 直接使用了 #define PGROUNDUP(sz) (((sz)+PGSIZE-1) & ~(PGSIZE-1)) 和 #define PGROUNDDOWN(a) (((a)) & ~(PGSIZE-1))
// os/src/mm/address.rs
impl PhysAddr {
pub fn floor(&self) -> PhysPageNum { PhysPageNum(self.0 / PAGE_SIZE) }
pub fn ceil(&self) -> PhysPageNum { PhysPageNum((self.0 + PAGE_SIZE - 1) / PAGE_SIZE) }
}
前面提到了页表项的组成
63 54 53 28 27 19 18 10 9 8 7 6 5 4 3 2 1 0
+----------+----------+----------+----------+-----+-+-+-+-+-+-+-+-+
| reserved | PPN[2] | PPN[1] | PPN[0] | RSW |D|A|G|U|X|W|R|V|
+----------+----------+----------+----------+-----+-+-+-+-+-+-+-+-+
10 26 9 9 2 1 1 1 1 1 1 1 1
这里比较重要的是标志位,同样也有定义,使用 bitflags! 宏可以将一个 u8 封装成一个标志位的集合类型
// os/src/main.rs
#[macro_use]
extern crate bitflags;
// os/src/mm/page_table.rs
use bitflags::*;
bitflags! {
pub struct PTEFlags: u8 {
const V = 1 << 0;
const R = 1 << 1;
const W = 1 << 2;
const X = 1 << 3;
const U = 1 << 4;
const G = 1 << 5;
const A = 1 << 6;
const D = 1 << 7;
}
}
对比 xv6
#define PTE_V (1L << 0) // valid
#define PTE_R (1L << 1)
#define PTE_W (1L << 2)
#define PTE_X (1L << 3)
#define PTE_U (1L << 4) // 1 -> user can access
这里的 bitflags 是一个 crate ,需要引入依赖。
# os/Cargo.toml
[dependencies]
bitflags = "1.2.1"
继续实现页表项
// os/src/mm/page_table.rs
#[derive(Copy, Clone)] // 让编译器自动为 PageTableEntry 实现 Copy/Clone Trait
#[repr(C)] // 遵守 C 布局
pub struct PageTableEntry {
pub bits: usize,
}
impl PageTableEntry {
pub fn new(ppn: PhysPageNum, flags: PTEFlags) -> Self {
PageTableEntry {
bits: ppn.0 << 10 | flags.bits as usize,
}
}
pub fn empty() -> Self {
PageTableEntry {
bits: 0,
}
}
pub fn ppn(&self) -> PhysPageNum {
(self.bits >> 10 & ((1usize << 44) - 1)).into()
}
pub fn flags(&self) -> PTEFlags {
PTEFlags::from_bits(self.bits as u8).unwrap()
}
}
后面还有地址转换和TLB的介绍,主要是理论层面的东西,这里省略。
物理页和页表管理
物理页帧管理
在 xv6 中使用 kalloc, kfree 等函数对物理页进行了管理,但是需要知道物理页的实际范围是什么,首先不能把内核数据给分出去,并且范围也不能超过物理内存的限制。
extern char end[]; // first address after kernel.
// defined by kernel.ld.
#define PHYSTOP (KERNBASE + 128*1024*1024)
void
kinit()
{
...
freerange(end, (void*)PHYSTOP);
}
这里的 end 来自于 kernel.ld ,放在了末尾,而 PHYSTOP 则是 128MiB 内存决定的
而在 rCore 中,终止物理地址同样也是硬编码的,虽然无论是 rCore 还是 xv6 都可以通过启动时读取设备树来获得实际的物理内存大小。
// os/src/config.rs
pub const MEMORY_END: usize = 0x80800000;
0x80800000 意味着全部能使用的物理内存大小(包括内核)被限定在了 8,388,608 B 也就是 8MiB,超出的部分不会使用。这么做的原因是为了兼容 K210 开发板
而对于 end ,rCore 中在 linker-qemu.ld 标记了 ekernel,效果是一样的。
rCore 定义了一个 trait,里面包含了物理帧页管理的基本功能
trait FrameAllocator {
fn new() -> Self;
fn alloc(&mut self) -> Option<PhysPageNum>;
fn dealloc(&mut self, ppn: PhysPageNum);
}
然后再实现这个 trait ,使用栈式物理页帧管理策略,将释放的物理页放到 recycled 里面,分配时优先从 recycled 取页,如果没有再尝试通过增加 current 来分配物理页,这和 xv6 使用的链表并不一样。
// os/src/mm/frame_allocator.rs
pub struct StackFrameAllocator {
current: usize, //空闲内存的起始物理页号
end: usize, //空闲内存的结束物理页号
recycled: Vec<usize>,
}
impl StackFrameAllocator {
pub fn init(&mut self, l: PhysPageNum, r: PhysPageNum) {
self.current = l.0;
self.end = r.0;
}
}
impl FrameAllocator for StackFrameAllocator {
fn new() -> Self {
Self {
current: 0,
end: 0,
recycled: Vec::new(),
}
}
fn alloc(&mut self) -> Option<PhysPageNum> {
if let Some(ppn) = self.recycled.pop() {
Some(ppn.into())
} else if self.current == self.end {
None
} else {
self.current += 1;
Some((self.current - 1).into())
}
}
fn dealloc(&mut self, ppn: PhysPageNum) {
let ppn = ppn.0;
// validity check
if ppn >= self.current || self.recycled.iter().any(|&v| v == ppn) {
panic!("Frame ppn={:#x} has not been allocated!", ppn);
}
// recycle
self.recycled.push(ppn);
}
}
不过可以预见的是,这个分配器必须要解决并发问题,xv6的方法是使用全局锁,而 rCore 还是将分配器包裹在 RefCell 里面,然后再包裹一层 UPSafeCell
type FrameAllocatorImpl = StackFrameAllocator;
lazy_static! {
/// frame allocator instance through lazy_static!
pub static ref FRAME_ALLOCATOR: UPSafeCell<FrameAllocatorImpl> =
unsafe { UPSafeCell::new(FrameAllocatorImpl::new()) };
}
初始化时和之前一样,使用 ekernel 和 MEMORY_END
pub fn init_frame_allocator() {
unsafe extern "C" {
safe fn ekernel();
}
FRAME_ALLOCATOR.exclusive_access().init(
PhysAddr::from(linker_symbol_addr!(ekernel)).ceil(),
PhysAddr::from(MEMORY_END).floor(),
);
}
然后提供分配释放物理页的接口,这里的 FrameTracker 是一个包裹了 PPN 的结构体,它的生命周期和物理页相绑定,实现了 Debug 和 Drop trait,其中 Drop 的实现就是调用 frame_dealloc,所以可以看到这个方法并没有声明成 pub,每分配物理页一个物理页,就会创建一个绑定它的 FrameTracker 的实例,释放时只需要释放 FrameTracker 即可,这里和 RAII 思想是一致的。
// os/src/mm/frame_allocator.rs
pub fn frame_alloc() -> Option<FrameTracker> {
FRAME_ALLOCATOR
.exclusive_access()
.alloc()
.map(|ppn| FrameTracker::new(ppn)) // 根据 Option<PhysPageNumber> 转换为 Option<FrameTracker>
}
fn frame_dealloc(ppn: PhysPageNum) {
FRAME_ALLOCATOR
.exclusive_access()
.dealloc(ppn);
}
分配流程如下:
- 从回收栈或者连续内存里面取出一个未使用的 PPN
- 将这个 ppn 绑定到新创建的
FrameTracker上,因为PhysPageNum声明了#[derive(Copy, Clone)],所以没有发生所有权转移 - 返回这个
FrameTracker
释放流程:出于一些原因 FrameTracker 被自动回收了,那么 drop() 会被自动调用,然后物理页号会回收到 recycled 向量中
这么一来,就不需要手动释放物理页了。
多级页表管理
xv6 中的页表和页表项类型就是一个64位地址,页表相关操作基本靠各种函数实现(比如 walk)
typedef uint64 pte_t;
typedef uint64 *pagetable_t; // 512 PTEs
static pte_t *
walk(pagetable_t pagetable, uint64 va, int alloc)
{
if(va >= MAXVA)
panic("walk");
for(int level = 2; level > 0; level--) {
pte_t *pte = &pagetable[PX(level, va)];
if(*pte & PTE_V) {
pagetable = (pagetable_t)PTE2PA(*pte);
} else {
if(!alloc || (pagetable = (pde_t*)kalloc()) == 0)
return 0;
memset(pagetable, 0, PGSIZE);
*pte = PA2PTE(pagetable) | PTE_V;
}
}
return &pagetable[PX(0, va)];
}
但在 rCore,有专门的数据类型进行管理,除了根页表的地址以外(xv6的页表类型不区分根页表或者子页表),还存储了各个 FrameTracker
// os/src/mm/page_table.rs
pub struct PageTable {
root_ppn: PhysPageNum,
frames: Vec<FrameTracker>,
}
impl PageTable {
pub fn new() -> Self {
let frame = frame_alloc().unwrap();
PageTable {
root_ppn: frame.ppn,
frames: vec![frame],
}
}
}
PageTable 下提供了几个常用方法
from_token: 从 satp 寄存器临时创建一个一个页表对象,ppn来自寄存器,frames则是新创建的find_pte_create/find_pte给定 VPN 返回 PTE,两者的区别在于找不到时是否分配 PPN 并创建新的 PTEmap: 给定 VPN,PPN 和 flag,建立页表映射,和 xv6mappages类似unmap: 给定 VPN,解除页表映射translate: 给定 VPN 返回只读的 PTEtoken: 用于将页表转换成可以写入satp的值
访问物理帧的办法如下,将 PhysPageNum 转换成 PhysAddr 然后作为 slice 返回
// os/src/mm/address.rs
impl PhysPageNum {
pub fn get_pte_array(&self) -> &'static mut [PageTableEntry] {
let pa: PhysAddr = self.clone().into();
unsafe {
core::slice::from_raw_parts_mut(pa.0 as *mut PageTableEntry, 512) // 可变 PTE 切片引用,共512个PTE
}
}
pub fn get_bytes_array(&self) -> &'static mut [u8] {
let pa: PhysAddr = self.clone().into();
unsafe {
core::slice::from_raw_parts_mut(pa.0 as *mut u8, 4096) // 可变字节切片引用,共4096个字节
}
}
pub fn get_mut<T>(&self) -> &'static mut T {
let pa: PhysAddr = self.clone().into();
unsafe {
(pa.0 as *mut T).as_mut().unwrap() // 单个 T 对象可变引用
}
}
}
借助这里的方法,就可以实现前面的 find_pte 等方法了,需要注意的是这里的 unsafe 意味着编译器不会检查引用指向的对象是否还有效。
地址空间
rCore 对地址空间进行了抽象,以逻辑段 MapArea 为单位描述一段连续地址的虚拟内存。
// os/src/mm/memory_set.rs
pub struct MapArea {
vpn_range: VPNRange, // 描述一段虚拟页号的连续区间,表示该逻辑段在地址区间中的位置和长度
data_frames: BTreeMap<VirtPageNum, FrameTracker>, // VPN-FramTracker 对
map_type: MapType, // 枚举类型,逻辑段内的所有虚拟页面映射到物理页帧的同一种方式,包括恒等映射和一般的页表映射两种
map_perm: MapPermission, // 逻辑段的访问方式,保留 U/R/W/X 四个标志位
}
但是地址空间不一定是连续的逻辑段,所以使用了 MemorySet 类型来表示,包含了一个页表和一些逻辑段。
// os/src/mm/memory_set.rs
pub struct MemorySet {
page_table: PageTable,
areas: Vec<MapArea>,
}
它的方法如下
new_bare: 新建对象token: 从页表生成可以写入 satp 的整型insert_framed_area: 根据输入的VA和标志位,向areas新建并插入一段Framed类型映射的逻辑段push: 插入MapArea并拷贝给定的数据map_trampoline: 将 trampoline 映射到页表中new_kernel: 新建一个MemorySet实例,并且将内核的各个段、其他物理内存、以及 MMIO 恒等映射到这个实例的页表中from_elf: 从 ELF 格式数据中创建所需要的地址空间,包括各个段、用户栈、保护用户栈的 guard page、Trap context和Trampolineactivate: 将页表应用到satp寄存器中,然后刷新translate: 给定 VPN,调用页表的方法得到 PTEshrink_to: 给定 VA 起点终点,在areas找到该起点,并解除终点后面的映射,如果没找到对应的逻辑段,返回 false,否则 trueappend_to: 类似shrink_to,但是含义相反
MapArea 的方法如下
new: 新建对象,输入VA起点终点,映射类型以及标志位map_one: 输入页表和VPN,进行物理页分配和页表映射unmap_one: 从data_frames中移除键值对,并且解除相应的页表映射map: 给定页表,将vpn_range全部建立映射unmap: 类似map但是含义相反shrink_to/append_to: 释放/分配物理页,并且解除映射/新建映射copy_data: 给定页表和数据,从MapArea的起始地址开始进行复制。
前面已经提到了内核的地址空间的内容,现在应用程序的地址空间可以共用同一个链接脚本了
/* user/src/linker.ld */
OUTPUT_ARCH(riscv)
ENTRY(_start)
BASE_ADDRESS = 0x10000;
SECTIONS
{
. = BASE_ADDRESS;
.text : {
*(.text.entry)
*(.text .text.*)
}
. = ALIGN(4K);
.rodata : {
*(.rodata .rodata.*)
}
. = ALIGN(4K);
.data : {
*(.data .data.*)
}
.bss : {
*(.bss .bss.*)
}
/DISCARD/ : {
*(.eh_frame)
*(.debug*)
}
}
这里起始地址不设置为 0 主要是因为 0 一般代表空指针。值得注意的是 xv6 的用户程序内存布局直接从 0 开始
sodium@nas-MacBook-Air-13 xv6-oslabs-hitsz % grep -nE 'Ttext|user\.ld|ld .*user' Makefile
130: $(LD) $(LDFLAGS) -N -e start -Ttext 0 -o $U/initcode.out $U/initcode.o
144: $(LD) $(LDFLAGS) -N -e main -Ttext 0 -o $@ $^
157: $(LD) $(LDFLAGS) -N -e main -Ttext 0 -o $U/_forktest $U/forktest.o $U/ulib.o $U/usys.o
164: $(LD) $(LDFLAGS) -N -e main -Ttext 0 -o $@ $^
169: $(LD) $(LDFLAGS) -N -e main -Ttext 0 -o $@ $^
174: $(LD) $(LDFLAGS) -N -e main -Ttext 0 -o $@ $^
237: $(LD) $(LDFLAGS) -N -e main -Ttext 0 -o $U/_uthread $U/uthread.o $U/uthread_switch.o $(ULIB)
$(LD): 链接器命令,这里是 RISC-V 交叉编译工具链中的 ld$(LDFLAGS):Makefile中定义的额外链接器参数,例如目标架构、输出格式等,这里是-z max-page-size=4096-N: 将文本段和数据段设置为可读写,并取消数据段按页对齐的常规要求-e start: 指定程序入口符号为start-Ttext 0: 将.text代码段的起始虚拟地址设为 0-o $U/initcode.out: 指定输出文件路径$U/initcode.o: 输入目标文件,由汇编源代码等编译得到
所以实际上用户程序是可以读取空指针的值的,这里尝试对 xv6 做一个小实验
// user/nulltest.c
#include "kernel/types.h"
#include "kernel/stat.h"
#include "user/user.h"
int main(void)
{
// volatile int *p = (volatile int *)0;
volatile unsigned int *p = 0;
printf("before null read\n");
unsigned int value = *p;
printf("read from NULL: %x\n", value);
printf("before null write\n");
*p = 0x123;
printf("after null write\n");
printf("read from NULL: %x\n", *p);
exit(0);
}
然后尝试运行
$ nulltest
before null read
read from NULL: EC061101
before null write
after null write
read from NULL: 123
sodium@nas-MacBook-Air-13 xv6-oslabs-hitsz % riscv64-unknown-elf-objdump -d user/_nulltest | head -20
user/_nulltest: file format elf64-littleriscv
Disassembly of section .text:
0000000000000000 <main>:
0: 1101 addi sp,sp,-32
2: ec06 sd ra,24(sp)
4: e822 sd s0,16(sp)
6: e426 sd s1,8(sp)
8: 1000 addi s0,sp,32
a: 00001517 auipc a0,0x1
e: 8b650513 addi a0,a0,-1866 # 8c0 <statistics+0x8c>
12: 00000097 auipc ra,0x0
16: 668080e7 jalr 1640(ra) # 67a <printf>
1a: 4481 li s1,0
1c: 408c lw a1,0(s1)
1e: 00001517 auipc a0,0x1
22: 8ba50513 addi a0,a0,-1862 # 8d8 <statistics+0xa4>
sodium@nas-MacBook-Air-13 xv6-oslabs-hitsz %
可以看到读出来的就是前两条指令的内容
回到 rCore ,应用程序的二进制镜像还是像之前一样保存在了 .data 段中,不过加载的步骤简化了很多,因为 ELF 解析的步骤都放在了前面的方法中了,所以加载时只需要获得 ELF 数据即可
// os/src/loader.rs
pub fn get_num_app() -> usize {
unsafe extern "C" {
safe fn _num_app();
}
unsafe { (linker_symbol_addr!(_num_app) as *const usize).read_volatile() }
}
pub fn get_app_data(app_id: usize) -> &'static [u8] {
unsafe extern "C" {
safe fn _num_app();
}
let num_app_ptr = linker_symbol_addr!(_num_app) as *const usize;
let num_app = get_num_app();
let app_start = unsafe {
core::slice::from_raw_parts(num_app_ptr.add(1), num_app + 1)
};
assert!(app_id < num_app);
unsafe {
core::slice::from_raw_parts(
app_start[app_id] as *const u8,
app_start[app_id + 1] - app_start[app_id]
)
}
}
基于地址空间的分时多任务
实现页表和地址空间等抽象之后,现在需要将应用程序和内核的地址空间区分开,Trap时,除了保存/恢复寄存器以外,还需要添加切换页表的操作
创建内核地址空间
内核地址空间的全局实例
// os/src/mm/memory_set.rs
lazy_static! {
pub static ref KERNEL_SPACE: Arc<UPSafeCell<MemorySet>> = Arc::new(unsafe {
UPSafeCell::new(MemorySet::new_kernel()
)});
}
这里使用 Arc<T> 是为了使用共享引用
初始化操作如下,activate 之后,内核页表正式生效,由于有 lazy_static! 宏,使用 KERNEL_SPACE 时就会自动先完成上面的初始化。
// os/src/mm/mod.rs
pub use memory_set::KERNEL_SPACE;
pub fn init() {
heap_allocator::init_heap();
frame_allocator::init_frame_allocator();
KERNEL_SPACE.exclusive_access().activate();
}
Trampoline 实现
因为用户程序和内核使用的页表不同,所以同样的虚拟地址可能映射到了不同的物理地址,发生 Trap 时,页表仍然是用户页表,因此跳转的虚拟地址映射的位置必须无论如何都是同一块地方,这个地方就是 Trampoline,同样的,返回之前还是内核页表,在真正返回之前必须切换到用户页表,这一期间映射的位置必须是一样的。
rCore 和 xv6 一样使用了用户地址空间与内核地址空间隔离(类似KPTI),这么做的优点是能够避免 Meltdown 漏洞攻击
发生 Trap 时,需要做至少几件事情
- 保存 Trap 上下文到某片区域
- 切换至内核页表并使用内核栈
- 跳转至 Trap Handler
为了完成上面的工作,Trap 上下文不可避免地要多出来一些东西,这三个东西设置好之后不需要修改
- 内核页表的
satp值 - 内核栈的地址
kernel_sp - Trap Handler 的入口
trap_handler
并且切换页表之前使用的是用户虚拟地址,所以 Trampoline 的入口必须能够正确地映射,和内核页表的映射是一样的(同样的 VA 对应同样的 PA)
# os/src/trap/trap.S
.section .text.trampoline
.globl __alltraps
.globl __restore
.align 2
__alltraps:
csrrw sp, sscratch, sp
# now sp->*TrapContext in user space, sscratch->user stack
# save other general purpose registers
sd x1, 1*8(sp)
# skip sp(x2), we will save it later
sd x3, 3*8(sp)
# skip tp(x4), application does not use it
# save x5~x31
.set n, 5
.rept 27
SAVE_GP %n
.set n, n+1
.endr
# we can use t0/t1/t2 freely, because they have been saved in TrapContext
csrr t0, sstatus
csrr t1, sepc
sd t0, 32*8(sp)
sd t1, 33*8(sp)
# read user stack from sscratch and save it in TrapContext
csrr t2, sscratch
sd t2, 2*8(sp)
# load kernel_satp into t0
ld t0, 34*8(sp)
# load trap_handler into t1
ld t1, 36*8(sp)
# move to kernel_sp
ld sp, 35*8(sp)
# switch to kernel space
csrw satp, t0
sfence.vma
# jump to trap_handler
jr t1
__restore:
# a0: *TrapContext in user space(Constant); a1: user space token
# switch to user space
csrw satp, a1
sfence.vma
csrw sscratch, a0
mv sp, a0
# now sp points to TrapContext in user space, start restoring based on it
# restore sstatus/sepc
ld t0, 32*8(sp)
ld t1, 33*8(sp)
csrw sstatus, t0
csrw sepc, t1
# restore general purpose registers except x0/sp/tp
ld x1, 1*8(sp)
ld x3, 3*8(sp)
.set n, 5
.rept 27
LOAD_GP %n
.set n, n+1
.endr
# back to user stack
ld sp, 2*8(sp)
sret
这里使用了 sscratch 寄存器来暂存了 TrapContext 的保存地址,并且相比于之前多出来了切换页表和读取地址并跳转至 trap_handler 的操作。恢复时也是类似的,先是将用户页表 satp 写入,切换页表,保存 TrapContext 地址到 sscratch,从 TrapContext 中恢复各种寄存器,最后再恢复用户栈并返回。
现在还需要将 Trampoline 段写进链接脚本,放进代码段中一张对齐的物理页中
# os/src/linker.ld
stext = .;
.text : {
*(.text.entry)
+ . = ALIGN(4K);
+ strampoline = .;
+ *(.text.trampoline);
+ . = ALIGN(4K);
*(.text .text.*)
}
上面的 Trampoline 中之所以没有直接使用 call trap_handler 而是通过 jr t1 的方式跳转是因为 call 的跳转是通过计算链接时地址偏移量实现的
举个简化的例子:
- 链接时 trampoline 地址:$T_K$
- 链接时 trap_handler 地址:$H_K$
- 链接器计算的偏移量:$H_K-T_K$
- 实际执行时 trampoline 的虚拟地址:$T_U$
实际跳转目标就变成:
$$ T_U+(H_K-T_K) $$
但真正需要的是:
$$ H_K $$
但是 $T_U$ 和 $T_K$ 未必相等,实际跳转目标可能不是想要的。
现在查看链接地址并对比虚拟地址
sodium@nas-MacBook-Air-13 release % rust-nm -n os | grep -E 'strampoline|trap_handler|__alltraps'
0000000080201000 T __alltraps
0000000080201000 T strampoline
0000000080206c7a T trap_handler
可以看到 trampoline 的链接地址是 0x80201000 而 trap_handler 的链接地址是 0x80206c7a
但是虚拟地址却不是这样的
pub const TRAMPOLINE: usize = usize::MAX - PAGE_SIZE + 1; // 0xfffffffffffff000
pub const TRAP_CONTEXT: usize = TRAMPOLINE - PAGE_SIZE;
同样的原因,在返回 __restore 时也需要重新计算 VA
#[unsafe(no_mangle)]
/// set the new addr of __restore asm function in TRAMPOLINE page,
/// set the reg a0 = trap_cx_ptr, reg a1 = phy addr of usr page table,
/// finally, jump to new addr of __restore asm function
pub fn trap_return() -> ! {
set_user_trap_entry();
let trap_cx_ptr = TRAP_CONTEXT;
let user_satp = current_user_token();
unsafe extern "C" {
unsafe fn __alltraps();
unsafe fn __restore();
}
let restore_va = linker_symbol_addr!(__restore) - linker_symbol_addr!(__alltraps) + TRAMPOLINE;
unsafe {
asm!(
"fence.i",
"jr {restore_va}", // jump to new addr of __restore asm function
restore_va = in(reg) restore_va,
in("a0") trap_cx_ptr, // a0 = virt addr of Trap Context
in("a1") user_satp, // a1 = phy addr of usr page table
options(noreturn)
);
}
}
这一点和 xv6 是一样的
void
usertrapret(void)
{
struct proc *p = myproc();
intr_off();
w_stvec(TRAMPOLINE + (uservec - trampoline));
p->trapframe->kernel_satp = r_satp(); // kernel page table
p->trapframe->kernel_sp = p->kstack + PGSIZE; // process's kernel stack
p->trapframe->kernel_trap = (uint64)usertrap;
p->trapframe->kernel_hartid = r_tp(); // hartid for cpuid()
unsigned long x = r_sstatus();
x &= ~SSTATUS_SPP; // clear SPP to 0 for user mode
x |= SSTATUS_SPIE; // enable interrupts in user mode
w_sstatus(x);
w_sepc(p->trapframe->epc);
uint64 satp = MAKE_SATP(p->pagetable);
uint64 fn = TRAMPOLINE + (userret - trampoline);
((void (*)(uint64,uint64))fn)(TRAPFRAME, satp);
}
加载和执行用户程序
任务控制块需要添加新的内容,包括地址空间、trap 上下文位置以及应用程序数据大小
// os/src/task/task.rs
pub struct TaskControlBlock {
pub task_cx: TaskContext,
pub task_status: TaskStatus,
pub memory_set: MemorySet,
pub trap_cx_ppn: PhysPageNum,
pub base_size: usize,
}
rCore 为每个应用都准备了各自的内核栈,每个栈之间都会隔一个 PAGE 起保护作用
// os/src/config.rs
/// Return (bottom, top) of a kernel stack in kernel space.
pub fn kernel_stack_position(app_id: usize) -> (usize, usize) {
let top = TRAMPOLINE - app_id * (KERNEL_STACK_SIZE + PAGE_SIZE);
let bottom = top - KERNEL_STACK_SIZE;
(bottom, top)
}
随着新字段的添加,任务控制块也要修改,new 需要根据 ELF 建立用户地址空间,初始化 trap_cx_ppn,任务状态、并且向内核地址空间添加相应的内核栈
// os/src/task/task.rs
impl TaskControlBlock {
pub fn new(elf_data: &[u8], app_id: usize) -> Self {
// memory_set with elf program headers/trampoline/trap context/user stack
let (memory_set, user_sp, entry_point) = MemorySet::from_elf(elf_data);
let trap_cx_ppn = memory_set
.translate(VirtAddr::from(TRAP_CONTEXT).into())
.unwrap()
.ppn();
let task_status = TaskStatus::Ready;
// map a kernel-stack in kernel space
let (kernel_stack_bottom, kernel_stack_top) = kernel_stack_position(app_id);
KERNEL_SPACE
.exclusive_access()
.insert_framed_area(
kernel_stack_bottom.into(),
kernel_stack_top.into(),
MapPermission::R | MapPermission::W,
);
let task_control_block = Self {
task_status,
task_cx: TaskContext::goto_trap_return(kernel_stack_top),
memory_set,
trap_cx_ppn,
base_size: user_sp,
};
// prepare TrapContext in user space
let trap_cx = task_control_block.get_trap_cx();
*trap_cx = TrapContext::app_init_context(
entry_point,
user_sp,
KERNEL_SPACE.exclusive_access().token(),
kernel_stack_top,
linker_symbol_addr!(trap_handler),
);
task_control_block
}
pub fn get_trap_cx(&self) -> &'static mut TrapContext {
self.trap_cx_ppn.get_mut()
}
pub fn get_user_token(&self) -> usize {
self.memory_set.token()
}
}
而 get_trap_cx 则返回了一个 'static 的可变引用,get_mut 是一个泛型函数,get_user_token 则是获得能够直接写入 satp 的数据
TaskManager 的初始化仍然是使用向量来保存各个应用程序,并且进行初始化。
pub struct TaskManager {
/// total number of tasks
num_app: usize,
/// use inner value to get mutable access
inner: UPSafeCell<TaskManagerInner>,
}
/// The task manager inner in 'UPSafeCell'
struct TaskManagerInner {
/// task list
tasks: Vec<TaskControlBlock>,
/// id of current `Running` task
current_task: usize,
}
lazy_static! {
/// a `TaskManager` global instance through lazy_static!
pub static ref TASK_MANAGER: TaskManager = {
println!("init TASK_MANAGER");
let num_app = get_num_app();
println!("num_app = {}", num_app);
let mut tasks: Vec<TaskControlBlock> = Vec::new();
for i in 0..num_app {
tasks.push(TaskControlBlock::new(get_app_data(i), i));
}
TaskManager {
num_app,
inner: unsafe {
UPSafeCell::new(TaskManagerInner {
tasks,
current_task: 0,
})
},
}
};
}
相应的链接文件不再使用二进制镜像,而是用 ELF 格式,并且进行 8 字节(64位)对齐,避免发生不对齐的内存读写
// os/src/task/mod.rs
impl TaskManager {
fn get_current_token(&self) -> usize {
let inner = self.inner.borrow();
let current = inner.current_task;
inner.tasks[current].get_user_token()
}
fn get_current_trap_cx(&self) -> &mut TrapContext {
let inner = self.inner.borrow();
let current = inner.current_task;
inner.tasks[current].get_trap_cx()
}
}
pub fn current_user_token() -> usize {
TASK_MANAGER.get_current_token()
}
pub fn current_trap_cx() -> &'static mut TrapContext {
TASK_MANAGER.get_current_trap_cx()
}
为了方便起见,rCore 的 TaskManager 还添加了一些 getter 来获取当前应用的地址空间有关的信息。
修改 Trap Handler
// os/src/trap/mod.rs
fn set_kernel_trap_entry() {
unsafe {
stvec::write(stvec::Stvec::new(
linker_symbol_addr!(trap_from_kernel),
TrapMode::Direct,
));
}
}
#[unsafe(no_mangle)]
pub fn trap_from_kernel() -> ! {
panic!("a trap from kernel!");
}
#[unsafe(no_mangle)]
pub fn trap_handler() -> ! {
set_kernel_trap_entry();
let cx = current_trap_cx();
let scause = scause::read();
let stval = stval::read();
let trap: Trap<Interrupt, Exception> = match scause.cause().try_into() {
Ok(trap) => trap,
Err(_) => panic!(
"Unsupported trap {:?}, stval = {:#x}!",
scause.cause(),
stval
),
};
match trap {
...
}
trap_return();
}
注意到 Trap Context 虽然虚拟地址是固定的,但是物理地址是随机分配的,也并没有映射到内核页表中,所以需要通过 current_trap_cx 来获取。
这里的 set_kernel_trap_entry() 类似于 xv6 中的 w_stvec((uint64)kernelvec); 如果内核态期间发生 S 态 Trap,那么会跳转到另外的处理函数。这里是直接 panic 了,但 xv6 中会识别 Timer Interrupt 然后调用 yield 函数
fn set_kernel_trap_entry() {
unsafe {
stvec::write(stvec::Stvec::new(
linker_symbol_addr!(trap_from_kernel),
TrapMode::Direct,
));
}
}
#[unsafe(no_mangle)]
/// Unimplement: traps/interrupts/exceptions from kernel mode
/// Todo: Chapter 9: I/O device
pub fn trap_from_kernel() -> ! {
panic!("a trap from kernel!");
}
从 trap return 时,需要设置 trampoline 的地址,并且计算出返回地址,fence.i 指令清空指令缓存 i-cache 确保处理器后续取指时,不会因为指令缓存等机制而继续使用过期的指令内容。
// os/src/trap/mod.rs
fn set_user_trap_entry() {
unsafe {
stvec::write(stvec::Stvec::new(TRAMPOLINE, TrapMode::Direct));
}
}
#[unsafe(no_mangle)]
pub fn trap_return() -> ! {
set_user_trap_entry();
let trap_cx_ptr = TRAP_CONTEXT;
let user_satp = current_user_token();
unsafe extern "C" {
unsafe fn __alltraps();
unsafe fn __restore();
}
let restore_va = linker_symbol_addr!(__restore) - linker_symbol_addr!(__alltraps) + TRAMPOLINE;
unsafe {
asm!(
"fence.i",
"jr {restore_va}",
restore_va = in(reg) restore_va,
in("a0") trap_cx_ptr,
in("a1") user_satp,
options(noreturn)
);
}
panic!("Unreachable in back_to_user!");
}
每个程序的启动流程如下,首先每个任务控制块初始化时,上下文都会设置返回地址为 trap_return
impl TaskContext {
/// init task context
pub fn zero_init() -> Self {
Self {
ra: 0,
sp: 0,
s: [0; 12],
}
}
/// set Task Context{__restore ASM funciton: trap_return, sp: kstack_ptr, s: s_0..12}
pub fn goto_trap_return(kstack_ptr: usize) -> Self {
Self {
ra: linker_symbol_addr!(trap_return),
sp: kstack_ptr,
s: [0; 12],
}
}
}
然后执行时,读取 TaskManager 获得相应的 TaskContext 然后调用 __switch 进行上下文切换
impl TaskManager {
...
fn run_next_task(&self) {
if let Some(next) = self.find_next_task() {
let mut inner = self.inner.exclusive_access();
let current = inner.current_task;
inner.tasks[next].task_status = TaskStatus::Running;
inner.current_task = next;
let current_task_cx_ptr = &mut inner.tasks[current].task_cx as *mut TaskContext;
let next_task_cx_ptr = &inner.tasks[next].task_cx as *const TaskContext;
drop(inner);
// before this, we should drop local variables that must be dropped manually
unsafe {
__switch(current_task_cx_ptr, next_task_cx_ptr);
}
// go back to user mode
} else {
println!("All applications completed!");
shutdown(false);
}
}
...
}
切换完之后就会从 trap_return 开始执行,最后返回用户程序
修改 sys_write
因为用户页表和内核页表不一样,所以用户传入的地址不能直接在内核使用,所以 sys_write 也需要修改
// os/src/mm/page_table.rs
pub fn translated_byte_buffer(
token: usize,
ptr: *const u8,
len: usize
) -> Vec<&'static [u8]> {
let page_table = PageTable::from_token(token);
let mut start = ptr as usize;
let end = start + len;
let mut v = Vec::new();
while start < end {
let start_va = VirtAddr::from(start);
let mut vpn = start_va.floor();
let ppn = page_table
.translate(vpn)
.unwrap()
.ppn();
vpn.step();
let mut end_va: VirtAddr = vpn.into();
end_va = end_va.min(VirtAddr::from(end));
if end_va.page_offset() == 0 {
v.push(&mut ppn.get_bytes_array()[start_va.page_offset()..]);
} else {
v.push(&mut ppn.get_bytes_array()[start_va.page_offset()..end_va.page_offset()]);
}
start = end_va.into();
}
v
}
步骤大致如下
- 输入
token即为satp值,ptr:*const u8确实是裸指针,但仅仅持有裸指针或将它转换成整数不需要unsafe,len是长度 - 从
token转换成页表,使用translate函数不断获得物理地址,然后进行复制,直到复制完成。 - 返回复制的结果
v是存放多个字节切片引用的动态数组,v容器的所有权会被转移给调用者,而不是直接销毁
得到这些字节切片引用之后,就可以将它们读取并打印出来
// os/src/syscall/fs.rs
pub fn sys_write(fd: usize, buf: *const u8, len: usize) -> isize {
match fd {
FD_STDOUT => {
let buffers = translated_byte_buffer(current_user_token(), buf, len);
for buffer in buffers {
print!("{}", core::str::from_utf8(buffer).unwrap());
}
len as isize
},
_ => {
panic!("Unsupported fd in sys_write!");
}
}
}
超越物理内存的地址空间
这一节大部分内容都已经在 OSTEP 中涉及过了,这里只提一下新出现的两种置换策略
工作集置换策略 WSClock
工作集置换策略的目标就是动态调整工作集的内容和大小,一个任务占用的页面数接近其工作集大小,减少缺页异常次数。
工作集的定义是:在最近一段时间 $\tau$ 内,任务访问过的页面集合。
$$ W(t,\tau)={p\mid p\text{ 在 }(t-\tau,t]\text{ 内被访问过}} $$
理想情况下,淘汰不属于工作集的页面,可以尽量保留程序当前阶段正在使用的数据。
但操作系统很难精确追踪每一次内存访问,因此 WSClock 使用两个信息来近似判断:
- 访问位 $R$ :硬件记录页面是否被访问过,操作系统可以读取并清零它。
- 上次使用时间 $T_{\text{last}}$ :操作系统记录最近一次确认页面被访问的时间。
如果当前时间是 $t$ ,那么页面的年龄为:
$$ \text{age}=t-T_{\text{last}} $$
当页面年龄大于 $\tau$ ,就可以认为它已经不属于当前工作集。
假设时钟指针依次扫描页面。每次缺页时,检查指针指向的页面: 检查当前页框
- 访问位 $R=1$ ?
- 是: 清零访问位,更新最近使用时间,并继续扫描下一个页框。
- 否: 检查页面年龄是否超过 $\tau$
- 超过:选择该页作为淘汰候选。
- 不超过:页面仍可能属于工作集,继续扫描。
缺页率置换策略
缺页率置换策略就是一种直接根据缺页率的变化来动态调整任务的物理内存大小的方法。
- 如果缺页率高了,就增加任务占用的物理内存,如果缺页率低了,就减少任务占用的物理内存。
- 任务占用的物理内存也称 常驻集 ,即当前时刻,任务实际驻留在内存中的页面集合
缺页率(page fault rate)= 缺页次数 / 访存次数
由于访存次数不好统计,这里根据连续 两次缺页之间的时间间隔 ,近似判断缺页是否过于频繁。
用一个经验值 Ts 表示适中的缺页率,出现缺页时,计算上次缺页异常时间 Tlast 到现在缺页异常时间 Tcurrent 的时间间隔
- Tcurrent – Tlast > Ts, 判断缺页比较少,置换出在 [Tlast, Tcurrent] 时间内没有被引用的页,并增加缺失页到工作集中
- Tcurrent – Tlast ≤ Ts, 判断缺页比较频繁,只增加缺失页到工作集中。