文章中，红色为不理解的问题，紫色为名词和问题标注。
有问题的地方欢迎在评论中提出，以便及时改正~
基本知识：
计算机：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.找到：获取页描述符，确定该页是否是脏页，确定其数据I\O??传送是否在进行。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(); //回收一部分内存
跳转到第一步（这是什么意思？循环吗？循环终止条件是什么？）
}
Bread（block_device描述符的地址bdev，块号block，块大小size）
——返回与缓冲区对应的缓冲区首部地址
{
调用getblk()；//在页高速缓存中查找与所请求的块相关的缓冲区页并获得指向乡音给的缓冲区首部的指针
如果块已经在页高速缓存中并包含有效数据
返回缓冲区首部的地址；
Else
递增缓冲区首部的引用计数器；
把end_buffer_read_sync()的地址赋给b_end_io字段
调用submit_bh(); //把缓冲区首部传送到通用块层
调用wait_on_buffer()； //把当前进程插入等待队列，直到I/O操作完成，即直到缓冲区首部的BH_Lock标志被清0；
返回缓冲区首部的地址；
}
向通用块层提交缓冲区首部
Submit_bh(数据传输的方向，指向描述快缓冲区的缓冲区首部的指针bh)——内核利用该函数向通用块层传递一个缓冲区首部，并请求传输一个数据块
{
设置缓冲区首部的BH_Req标志以表示块至少被访问过一次
如果数据穿刺术的方向是WRITE，就将BH_Write_ETO标志清0
调用bio_alloc(); //分配一个新的bio描述符
根据缓冲区首部的内容初始化bio描述符的字段；
递增bio的引用计数器
调用submit_bio()； //把bi_rw标志设置为数据传输的方向，更新没CPU的变量page_states以表示读和写的扇区数，并对bio描述符调用generic_make_request()函数
递减bio的使用计数器；//因为bio描述符现在已经被插入I/O调度程序的队列，所以没有释放bio描述符
Return 0；
}
把脏页写入磁盘——如何把也高速缓存中的脏页写回磁盘中
内核不断用包含块设备数据的页填充页高速缓存。只要进程修改了数据，相应的页就被标记为脏页，即把它的PG_dirty标志置位。
Unix系统允许把脏缓冲区写入块设备的操作延迟执行。
原因：因为这种策略可以显著地提高系统的性能。对高速缓存总的页的几次写错早可能
只需对相应的磁盘块进行一次缓慢的物理更新就可以满足。
一个脏页可能直到最后一刻都一直逗留在主存中。然而从延迟写策略的局限性来看，有两个主要缺点：
1. 如果发生了硬件错误或电源掉电的情况，那么就无法再获得RAM的内容，因此，从系统启动以来对文件进行的很多修改就丢失了
2. 页高速缓存的大小就可能要很大——至少要与所访问块设备的大小相同。
在下列情况下，把脏页刷新（写入）到磁盘
1. 页高速缓存变得太满，但还需要更多的页，或者脏页的数量已经太多。
2. 自从页变成脏页以来已过去太多时间。
3. 进程请求对块设备或者特定文件任何待定的变化都进行刷新。通过调用sync()、fsync()或fdatasync()系统调用来实现
Pdflush内核线程
功用：Linux2.6用一组通用内核线程pdflush来扫描页高速缓存以搜索要刷新的脏页，并保证所有的页不会“脏“太长时间。
Pdflush内核线程结构灵活，作用于两个参数：一个指向线程要执行的函数的指针和一个函数要用的参数。
为什么要用一组pdflush内核线程？
系统中pdflush内核线程的数量是要动态调整的：pdflush线程太少时就创建，太多时就杀死。因为这些内核线程所执行的函数可以阻塞，所以创建多个而不是一个pdflush内核线程可以改善系统性能。
控制pdflush线程的产生和消亡的原则：
1. 必须由至少两个，最多八个pdflush内核线程。
2. 如果到最近的1s期间没有空闲pdflush，就应该创建新的pdflush
3. 如果最近一次pdflush变为空闲的时间超过了1s，就应该删除一个pdflush。
运行原理：
所有的pdflush内核线程都执行函数pdflush(),这个函数本质上循环执行一直到内核线程死亡。
假设pdflush内核线程是空闲的，而进程正在睡眠（为何要做这种假设？）
一旦内核线程被唤醒，pdflush（）就访问其pdflush_work描述符，并执行回调函数fn
当回调函数结束时，pdflush（）检查last_empty_jifs变量（这个变量有何意义？）的值：
如果不存在空闲pdflush内核线程的时间已经超过1s，而且pdflush内核线程的数量不到8个
函数pdflush（）就创建另外一个内核线程
如果pdflush_list链表中的最后一项对应的pdflush内核线程空闲时间超过了1s，而且系统中有两个以上的pdflush内核线程
函数pdflush()就终止
搜索要刷新的脏页
为什么搜索要刷新的脏页？
答：所有的基树都可能由要刷新的脏页。为了得到所有这些页，就要彻底搜索与在磁盘上有映像的索引节点相应的所有address_space对象。
回写陈旧的脏页
为什么要回写陈旧的脏页？
答：内核试图避免当一些页很久没有被刷新时发生饥饿危险。因此，脏页在保留一定时间后，内核就显示开始进行I/O数据的传输，把脏页的内容写到磁盘。
怎么回写陈旧的脏页？
由被定期唤醒的pdflush内核线程完成，内核初始化期间，page_writeback_init()函数建立wb_timer动态定时器，以便定时器的到期时间发生在dirty_writeback_centisecs文件中所规定的几百分之一秒之后。定时器函数wb_timer_fn()本质上调用pdflush_operation()函数，传递给它的参数是回调函数wb_kupdate()的地址。Wb_kupdate()函数遍历页高速缓存搜索陈旧的脏搜索节点。
Sync()、fsync()和fdatasync()系统调用
——介绍一些让用户刷新页高速缓存的内容来更新磁盘内容。
Synv()允许进程把所有的脏缓冲区刷新到磁盘。
Fsync()允许进程把属于特定打开文件的所有块刷新到磁盘。
Fdatasync(),与sync()非常相似，但不刷新文件的索引节点。