文章中，红 {MOD}为不理解的问题，紫 {MOD}为名词和问题标注。 有问题的地方欢迎在评论中提出，以便及时改正~   基本知识：          计算机：CPU（运算器、控制器、寄存器、髙速缓存、总线）                           内存（也叫随机存储器RAM）----体积小、速度快、有电可存、无电清空                           硬盘（属于外存）   Linux内核，即Linux操作系统所使用的内核? ＂内核＂指的是一个提供硬件抽象层，磁盘及文件系统控制，多任务等功能的系统软件。一个内核不是一个完整的操作系统。 一套基于Linux内核的完整操作系统叫做Linux操作系统 高速缓存：介于CPU和内存之间，是高速小容量存储器 磁盘高速缓存：介于内存和硬盘之间？是一种软件机制，允许系统把通常放在磁盘上的一些数据保。留在RAM中，以便对数据的进一步访问不用再访问磁盘而尽快得到满足。 （二者重点区别）? 其它高速缓存：目录项高速缓存（存放描述文件系统路径名的目录项对象）                      索引节点高速缓存（存放描述磁盘索引节点的索引节点对象） 页高速缓存：一种对完整的数据页进行操作的磁盘高速缓存。是Linux内核所使用的主要磁盘高速缓存。在多数情况下，内核在读写磁盘时都引用页高速缓存。新页被追加到页高速缓存以满足用户进程的读请求。如果页不在高速缓存中，新页就被加到高速缓存中，然后用磁盘读出的数据填充它。如果内存有足够的空闲空间，就让该页在高速缓存中长期保留，使其他进程再使用该页时不再访问磁盘。 实现页高速缓存的目的：1.快速定位含有给定所有者相关数据的特定页。为了尽可能充分发挥页高速缓存的优势，对它应该釆用高速的捜索操作。2.记录在读或写页中的数据时应当如何处理高速缓存中的每个页。例如，从普通文件、块设备文件或交换区读一个数据页必须用不同的实现方式，因此内核必须根据页的所有者选择适当的操作。 页高速缓存中的信息单位是一个完整的数据页。通过页的所有者和所有者数据中的索引来识别页高速缓存中的页。 页高速缓存中的核心数据是address-space对象，是一个嵌入在页所有者的索引节点对象中的数据结构。 Mapping和index是两个把页链接到页高速缓存的两个字段 ，每个页描述符都包括这两个字段。 Mapping字段指向拥有页的索引结点的address-space对象 Index字段表示在所有者的地址空间中以页为单位的偏移量，即在所有者的磁盘映象中页中数据的位置。 如果页属于一个文件，那么页的所有者就是文件的索引节点，而相应的address-space对象存放在VFS（？）索引节点对象的i-data字段中。索引节点的I-mapping字段指向同一个结点的i-data字段，而address-space对象的host字段也指向这个索引节点。 基数Radix tree Linux访问大文件时，用大量的捜索树实现页高速缓存的高效查找，每一个address-space对象对应一棵捜索树。 脏页：应当被刷新到磁盘的页。 页索引：表示页在所有者磁盘映象中的位置 Page-tree字段（在address-space对象中)------基树的根 含有指针-----指向页所有者的页描述符 当查找所需要的页时，内核把页索引转换为基树中的路径（基树中的路径是什么？）并快速找到页描述符所在的位置。1.找到：获取页描述符，确定该页是否是脏页，确定其数据IO??传送是否在进行。2.没找到怎么办??   基树的每个节点可以有多到64个指针指向其他节点或页描述符。 每个节点由radix_tree_node数据结构表示 Struct radix_tree_node { *ElemType  slots[64];     //包含64个指针的数组 int         count;      //记录节点中非空指针数量的计数器 ElemType  tags[ ][ ];     //二维标志数组 } Struct radix_tree_root {      Int        height;      //表述树的当前深度（不包括叶子节点的层数）      ElemType  gfp_mask;   //指定为新节点请求内存时所用的标志      ElemType  rnode;      //指向与树中第一层节点相应的数据结构radix_tree_node }   如果树中的索引没有大于63，那么树的深度就等于1，因为可能存在的64个叶子都存放在第一层的节点中。如果与索引131相应的新页的描述符肯定存放页高速缓存中（叶子什么时候存放在第一层节点？什么时候存放在页高速缓存？），那么树的高度就增加为2，这样基树就可以查找多达4095个索引（64*64=4096，即0~4095）   基树的最大深度是6，但系统中的页告诉缓存不大可能使用那么大的基树。因为页索引存放在32位变量中，当树的深度为6时，最高层的叶子节点最多可以有4个孩子节点。   分页系统是如何利用页表实现线性地址到物理地址的转换的？如何实现页查找？                                                                                 线性地址最高20位分成两个10位的字段，第一个字段是页目录中的偏移量，而第二个字段是某个页目录项所指的页表中的偏移量。     基树中，页索引相当于线性地址。但页索引中要考虑的字段的数量依赖于基树的深度。如果基树的深度为1，就只能表示0~63范围的索引，因此页索引的低6位被解释为slots数组的下标，每个下标对应第一层的一个节点。如果基树的深度为2，就可以表示0~4095范围的索引，页索引的低12位分成2个6位的字段，高位的字段用于表示第一层节点数组的下标， 而地位的字段用于表示第二层节点数组的下标。以此类推，如果深度等于6，页索引的最高两位表示第一层节点数组的下标，接下来6位表示第二层节点数组的下标，这样一直到最低6位，它们表示第六层节点数组的下标。 页高速缓存的处理函数 1.       查找页 find_get_page( 指向address_space对象的指针，指向address_space对象的偏移量) { 　 获取地址空间的自旋锁？； 　 调用radix_tree_lookup( )函数；//根据偏移量值中的位依次从树根开始向下搜索，搜索拥有指定偏移量的基树的叶子节点 　 如果遇到空指针       返回NULL； 　 Else       返回叶子节点的地址；//即所需要的页描述符指针 　 如果根据也描述符找到了所需要的页      { Find_get_page函数就增加该页的使用计数器；        释放自旋锁；        返回该页的地址； } 　 Else      {        释放自旋锁；        返回NULL； 　 　｝ } 2.       增加页 　 add_to_page_cache(页描述符的地址page，address_space对象的地址mapping，表示地址空间内的页索引的值offset，为基树分配新节点时所使用的内存分配标志gfp_mask) {   调用radix_tree_preload( )函数；//禁用内核抢占？，并把一些空的radix_tree_node结构赋给每个CPU变量radix_tree_preloads   获取mapping->tree_lock自旋锁；   调用radix_tree_insert( )在树中插入新节点；   增加页描述符的使用计数器page->count   设置页框的PG_locked标志；  //新页的内容无效，设置这个标志来阻止其它的内核路径并发访问该页   用mapping和offset参数 初始化page->mapping和page->index;   递增在地址空间所缓存页的计数器   释放地址空间的自旋锁； 调用radix_tree_preload_end( )；    //重新启用内核抢占？ return 0； } 3.       删除页 remove_from_page_cache( ) {   获取自旋锁page->mapping->tree_lock  并关掉中断？;     调用radix_tree_delete( )函数从树中删除节点；    把page->mapping 字段置为NULL； 把所缓存页中的page->mapping->nrpages计数器的值减1； 释放自旋锁page->mapping->tree_lock，打开中断，函数终止？ } 4.       更新页（确保高速缓存中包括最新版本的指定页） read_get_page(指向address_space对象的地址mapping，表示所请求页的偏移量的值index，指向从磁盘度页数据的函数的指针filler，传递给filler函数的指针data) {   调用函数find_get_page( )；   //检查页是否已经在高速缓存中   如果页不在高速缓存中     {       调用alloc_pages分配一个新页框；       调用add_to_page_cache( )；  //在页高速缓存中插入相应的页描述符       调用lru_cache_add( )；      //把页插入该管理区的非活动LRU链表中 }此时，页已经在高速缓冲中了      调用mark_page_accessed( )；    //记录页已经被访问过的事实      如果页不是新的（即PG_locked标志为0）          调用filler函数；      //从磁盘读该页      返回页描述符的地址； } 把块存放在页高速缓存中——讨论如何使用该页高速缓存快速检索单独的数据块（例如超级块和索引节点），是提高虚拟文件系统和磁盘文件系统的关键特征。 “块”：一种组织磁盘数据的逻辑单位。 稳定版本的LINUX内核不再单独分配块缓冲区，相反，把它们都存放在叫做“缓冲区页”的专门页中，而缓冲区页存在页高速缓存中。    “缓冲区首部”是附加描述符。该描述符包含内核必须了解的、有关如何处理块的所有信息。    缓冲区页在形式上就是与称作“缓冲区首部”的附加描述符相关的数据页，其主要目的是快速确定叶中的一个块在磁盘中的地址。    如下图：                         （在对块的操作之前要检查缓冲区首部） 分配块设备缓冲区页     当内核发现指定块的缓冲区页不在页告诉缓存中时，就分配一个新的块设备缓冲区页。 内核调用grow_buffers( )把块设备缓冲区添加到页告诉缓存中 grow_buffers(block_device描述符的地址bdev,块在设备中的位置block，块大小size) {    计算数据页在所请求块的块设备中的偏移量index；    如果需要，调用grow_dev_page( )；//创建新的块设备缓冲区页    为页解锁；    //函数find_or_create_page( )曾为页加了锁    递减页的使用计数器;    return 1; } 释放块设备缓冲区页 当内核驶入获得更多的空闲内存时，就释放块设备缓冲区页（不可能释放有脏的缓冲区的页 或上锁的缓冲区页） 内核调用try_to_release_page( )释放缓冲区页 try_to_release_page(页描述符的地址page) {   如果设置了页的PG_writeback标志       //因为正在把页写回磁盘，不可能释放该页       Return 0；   如果已经定义了块设备address_space对象的releasepage方法       就调用该方法（这个方法通常没有） 调用try_to_free_buffers( )并返回它的错误代码； }  try_to_free_buffers( )——依次扫描链接到缓冲区页的缓冲区首部 {    检查页中所有缓冲区的缓冲区首部标志； 如果有些缓冲区首部的BH_Dirty或BH_Locked标志被置位   //说明函数不可能释放这些缓冲区 　 　函数终止，return 0； 如果缓冲区首部在间接缓冲区的链表中     从链表中删除它； 清除页描述符的PG_private标记 把private字段设置为NULL 递减页的使用计数器 清除页的PG_dirty标记 反复调用free_buffer_head()     //释放页的所有缓冲区首部 return 1； } 在页高速缓存中搜索块     当内核需要读或写一个单独的物理设备快时（例如一个超级块？？），必须检查所请求的块缓冲区是否已经在页高速缓存中。 在页高速缓存中搜索指定的块缓冲区： 1.  获取一个指针，让他指向包含指定块的块设备的 address_space对象bdev->bd_inode->i_mapping) 2.  获得设备的块大小，并计算包含指定块的页索引 3.  在块设备的基树中搜索缓冲区页，获得页描述符之后，内核访问缓冲区首部，它描述了页中块缓冲区的状态。 Find_get_block(block_device描述符地址bdev，块号block，块大小size ) //函数返回页高速缓存中的块缓存中的块缓冲区对应的缓冲区首部的地址；如果不存在指定的块，就返回NULL。 { 检查执行CPU的LRU块高速缓存数组中是否有一个缓冲区首部，其b_bdev，b_blocknr和b_size字段分别等于bdev、block和size。 如果缓冲区首部在LRU块高速缓存中        刷新数组中的元素 如果缓冲区首部不在LRU块高速缓存中     Index=block>>(PAGE_SHIFT-bdev->bd->i_blkbits) 调用find_get_page( );                 //确定存有所请求的块缓冲区的缓冲区页的描述符在页高速缓存中的位置。 【函数已经得到了缓冲区页描述符的地址】 扫描链接到缓冲区页的缓冲区首部链表，查找逻辑块号等于block的块 递减页描述符count字段 把LRU块高速缓存中的所有元素向下移动一个位置，并把指向所请求块的缓冲区首部的指针插入到第一个位置 如果一个缓冲区首部已经不再LRU块高速缓存中，就递减它的引用计数器b_count。 如果需要，调用mark_page_accessed();     //把缓冲区页移至适当的LRU链表中 返回缓冲区首部指针。 } Getblk(block_device描述符的地址bdev，块号block，块大小size ) ——分配块设备缓冲区页并返回将要描述块的缓冲区首部的指针。 {    调用find_get_block();   //检查块是否已经在页高速缓存中    如果找到块        返回块的缓冲区首部的地址；    Else        调用grow_buffers();    // 为请求的页分配一个新的缓冲区页    如果grow_buffers()分配页时失败        调用函数free_more_memory();    //回收一部分内存