FreeBSD虚存系统splay树的代码分析

这是我于2006年3月18日发表在cu的BSD程序开发版上的一篇文章：
http://bbs.chinaunix.net/viewthread.php?tid=717530&extra=page%3D2

FreeBSD虚存系统splay树的代码分析
雨丝风片：chinaunix.net
已完成内容的目录：
1、vm_map_entry结构体中的adj_free和max_free
2、vm_map_entry_splay()函数
3、vm_map_findspace()函数
......
1、vm_map_entry结构体中的adj_free和max_free
vm_map_entry结构体同时按两种数据结构进行组织，一种是双向链表（通过prev和next指针），一种是二叉查找树（通过left和right指针）。其中的二叉查找树就是由Daniel Dominic Sleator和Robert Endre Tarjan提出的splay树，他们的论文题目把这种树叫做自调整二叉查找树。
splay树的基本原理请参见原始论文【Self-Adjusting Binary Search Trees】和我写的一些笔记
【FreeBSD虚存系统splay树的基本原理】
FreeBSD是从5.0开始将splay树引入VM系统的，在5.3的时候又加入了基于树状结构的空闲空间算法。本文就从这个空闲空间算法讲起。
vm_map_entry结构体的主要内容如下：
CODE:
[Copy to clipboard]
_____________________________________________________________________FreeBSD6.0
093  /*
094   *    Address map entries consist of start and end addresses,
095   *    a VM object (or sharing map) and offset into that object,
096   *    and user-exported inheritance and protection information.
097   *    Also included is control information for virtual copy operations.
098   */
099  struct vm_map_entry {
100      struct vm_map_entry *prev;    /* previous entry */
101      struct vm_map_entry *next;    /* next entry */
102      struct vm_map_entry *left;    /* left child in binary search tree */
103      struct vm_map_entry *right;    /* right child in binary search tree */
104      vm_offset_t start;        /* start address */
105      vm_offset_t end;        /* end address */
106      vm_offset_t avail_ssize;    /* amt can grow if this is a stack */
107      vm_size_t adj_free;        /* amount of adjacent free space */
108      vm_size_t max_free;        /* max free space in subtree */
_______________________________________________________/usr/src/sys/vm/vm_map.h
空闲空间算法向vm_map_entry结构体中添加了两个字段，adj_free和max_free。adj_free是和这个map entry相邻且紧跟其后（位于较高地址）的空闲空间的大小。注意，adj_free字段取决于链表结构，而不是splay树。这个链表是按照地址的升序来排列的，因此adj_free可以通过下述方式来计算：
CODE:
[Copy to clipboard]

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有