正如上文所述,Sinos使用基于x86硬件的页式内存管理思想。
由于不考虑跨平台设计,内核中所有对分页硬件及其数据结构的操作和引用均没有任何级别的抽象,完全与x86系列CPU紧耦合。
5.1 页表
Sinos使用二级页表,与Intel x86硬件一致,而不像Linux一样出于移植性考虑使用统一的三级页表。
由于采用的内存策略为共享核心态内存,所以系统各进程间需要共享同一组页表。Sinos的解决方案是通过页目录表来共享。每个进程拥有各自的页目录表,但其顶部(高地址端)的256项表项却指向同一组核心态内存页表。
所有核心态内存的页表在初始化分页系统时预先分配好了,共256*4KB=1MB大小。这样,所有进程页目录表的顶部256都是一样的,而且不会出现页表的缺页异常,可以使页表的处理简化。不过,这样做的后果是花了1MB物理内存来存放页表,但真正使用的页表不会超过三分之一,有点浪费。
应该承认,共享页表的这个预分配问题,是非常值得商榷的。预分配页表不但可以大大简化操作,而且可以使相应的共享页目录项始终固定。固定这些页目录项的好处是因为每个进程都有一份页目录表,也就有一份共享页目录项的复本,如果一旦这些页目录项更改,所有的进程都得做相应的更改,在进程数目较大的情况下,这个开销值得考虑。但是,就算一次更新开销很大,但这种更新其实并不麻烦,而且它可能并不经常发生。
由于Sinos只是对操作系统开发的一个探索,作者并没有更多操作系统开发的经验,目前没办法准确权衡两种方案的得失。所以,目前Sinos只能试探性地使用一种操作相对简单的办法,也许随着后续的开发,Sinos会采用内存更经济的方案。
现阶段不使用页表动态分配方案还有一个比较现实的原因,就是缺页处理模块还没有完成。由于Sinos计划使用交换文件,所以在文件系统完成之前不会开发缺页处理模块。
5.2 内存布局
在实模式下,已经设置了最初的页目录表和两张页表。通过这些设置,虚地址从00000000h和C0000000h开始的各4MB内存都被映射到物理内存的前4MB,所以可以通过这些地址存取前4MB的物理内存。
由于1MB以下物理内存结构复杂,内核管理和使用的内存从1MB物理内存开始。
1MB-2MB物理内存用作上文所提到的预分配页表。核心态内存地址共1GB,所以其所占页表为1GB/4KB*4B=1MB。这样设置后,虚地址C0000000h开始的1GB虚地址对应的页表项线性地存放在1MB的物理内存中,便于快速查找。这里有一个例外,就是第一张核心页表,即C0000000h-C0400000h对应的页表,由于是在实模式初始化时设置的,所以还是位于常规内存,但这并不影响内核的操作,因为Sinos内核在设计时没有显式引用这一段内存[1]
。
有两块内存需要在内存管理系统建立起来之前完成地址和物理空间的分配:页数据库,用于分配物理空间;核心态Buddy树,用于分配线性地址空间。
页数据库是实际使用的内存页的管理数据结构,是由页数据库项组成的线性表。每个页数据库项对应一页物理内存,所以线性表的长度就是可用物理内存页数。这样,物理内存的页帧号也可由页数据库项的线性表索引号计算获得,反之亦然。所以通过页表项中的页帧号可以直接找到对应的页数据库项。
通过页数据库项也可以找到页表项。页数据库项中有一个Pointer字段用于存放指针。当该页引用计数为1时,Pointer直接指向页表项;当页引用计数大于1时,即该页为进程间的共享内存,Pointer指向共享页的管理结构。由于共享内存模块还没有实现,只是留下了接口,所以目前无法详述了。
页表项是页式内存的主要数据结构,但其中容纳的信息有限,不足以用于操作系统的管理,所以需要把管理信息存放在页数据库中;页数据库管理着所有物理内存的使用情况,同时也需要知道该页被引用的情况。所以页表项和页数据库项的双向勾连,对于内存页的操作是非常有用的。
Sinos按照Windows的思想,在分页管理时使用工作集模型[2] ,同时把所有不在工作集中的页数据库项组织成四条链表:Dirty,Standby,Free,Zeroed。
同样是由于页交换部分还没有完成,这些链表目前只使用了Free链表。
当前的Sinos版本中,每一个物理内存页如果没有被使用,它就位于Free链表中;一旦该页被分配给某个进程,则该页所对应的页数据库项则被链入该进程的页链表中。进程页链表目前的作用只是在进程结束时释放所有使用的内存页,今后可能会有新的功能。
Free链表是一条单向链表,其链表头是一个全局变量,通过页数据库项中的链接字段来进行链接。由于物理内存页没有顺序和位置的区别,所以该链表只需要一个头指针。每当需要分配新的物理内存页时,系统从链表头部取出空的物理内存页;当释放物理内存页时,系统也在链表的头部插入该页。
其它三条链表(Dirty、Standby、Zeroed)也都是使用同样链接字体段的单向链表,由于还没有完成,其功能不再叙述。
5.3 虚地址管理
内存管理任务除了物理内存管理外,虚地址的管理也是非常重要的。
在各个进程共享的核心态内存范围中,共有1GB地址空间,这1GB地址空间必须由一个模块统一分配和释放,不然如果由各模块自行指定地址空间的话,一定会发生冲突。
在内存管理方面,使用地址块链表和首适(First Fit)算法是比较传统的做法,但这种Unix
v6时代的算法显然不太适合如今的硬件环境,因为其性能较差;同时也不能使用堆算法,因为地址和空间的管理是分开的,必须有一个集中的数据结构来管理地址才行。
Sinos使用了当前广泛使用的伙伴(Buddy)算法[3]来进行系统地址的分配,尽管伙伴算法有着内碎片[4]
较大的缺点,但对于系统模块来说还是不成问题的。
伙伴算法的关键是建立一棵伙伴树,通过个树结构来配置当前的地址空间。由于伙伴树的建立是系统内存分配的前提,所以伙伴树所占用的内存是在初始化分页系统时预分配的,其位置紧接在系统页表之后。
Sinos伙伴树管理的地址空间以页为单位,1GB核心态空间共1GB/4KB=256K页,所以伙伴树底层共256K个结点。由于伙伴树是满二叉树,所以整棵树的结点数为2*256K-1,即512K个结点。目前每个结点大小为32bit,整颗树占用空间为512K*4B=2MB。
2MB是个很可观的内存数量,但实际上每个结点的32bit中,伙伴树只使用了其中的3bit。也就是说,如果有必要,可以把树的大小控制在256KB以下。目前取32bit只是为了将来的扩充,由于作者也不确定后续开发会对该伙伴树结点作怎样的扩充,所以在物理内存不是太紧张的情况下保留了32bit。
关于伙伴算法的详情请参考相关操作系统资料。
[1] 在下面将看到,其实对于内核来说,这一段虚地址是不可用的,在后续的内存分配、释放操作中不会涉及该段地址。这样,只要不对页表地址进行显式操作,这种布局不会产生问题。
[2] 工作集(Working Set)模型,由于Sinos该部分模块还没有完成,请参阅相关论文资料。
[3] 由于作者没有看过Linux代码,所以不知道Sinos的伙伴算法是否与Linux类似。
[4] 内碎片 – Internal
Fragment,由于分配时必须以块为单位分配空间所造成的块内空间浪费。伙伴算法由于空间分配必需以2n来分配,内碎片问题更为明显。