Linux Cache 机制探究

8月 27th, 2010 | Posted by | Filed under 操作系统

经过研究了下Linux相关代码,把对Linux Cache实现的方式做一些总结。
相关源码主要在:
./fs/fscache/cache.c    Cache实现的代码
./mm/slab.c                   SLAB管理器代码
./mm/swap.c                缓存替换算法代码
./mm/mmap.c             内存管理器代码
./mm/mempool.c       内存池实现代码

0. 预备:Linux内存管理基础

创建进程fork()、程序载入execve()、映射文件mmap()、动态内存分配malloc()/brk()等进程相关操作都需要分配内存给进程。不过这时进程申请和获得的还不是实际内存,而是虚拟内存,准确的说是“内存区域”。Linux除了内核以外,App都不能直接使用内存,因为Linux采用Memory Map的管理方式,App拿到的全部是内核映射自物理内存的一块虚拟内存。malloc分配很少会失败,因为malloc只是通知内存App需要内存,在没有正式使用之前,这段内存其实只在真正开始使用的时候才分配,所以malloc成功了并不代表使用的时候就真的可以拿到这么多内存。据说Google的tcmalloc改进了这一点。

进程对内存区域的分配最终多会归结到do_mmap()函数上来(brk调用被单独以系统调用实现,不用do_mmap())。内核使用do_mmap()函数创建一个新的线性地址区间,如果创建的地址区间和一个已经存在的地址区间相邻,并且它们具有相同的访问权限的话,那么两个区间将合并为一个。如果不能合并,那么就确实需要创建一个新的VMA了。但无论哪种情况, do_mmap()函数都会将一个地址区间加入到进程的地址空间中,无论是扩展已存在的内存区域还是创建一个新的区域。同样释放一个内存区域使用函数do_ummap(),它会销毁对应的内存区域。

另一个重要的部分是SLAB分配器。在Linux中以页为最小单位分配内存对于内核管理系统物理内存来说是比较方便的,但内核自身最常使用的内存却往往是很小(远远小于一页)的内存块,因为大都是一些描述符。一个整页中可以聚集多个这种这些小块内存,如果一样按页分配,那么会被频繁的创建/销毁,开始是非常大的。

为了满足内核对这种小内存块的需要,Linux系统采用了SLAB分配器。Slab分配器的实现相当复杂,但原理不难,其核心思想就是Memory Pool。内存片段(小块内存)被看作对象,当被使用完后,并不直接释放而是被缓存到Memory Pool里,留做下次使用,这就避免了频繁创建与销毁对象所带来的额外负载。

Slab技术不但避免了内存内部分片带来的不便,而且可以很好利用硬件缓存提高访问速度。但Slab仍然是建立在页面基础之上,Slab将页面分成众多小内存块以供分配,Slab中的对象分配和销毁使用kmem_cache_alloc与kmem_cache_free。

关于SALB分配器有一份资料:http://lsec.cc.ac.cn/~tengfei/doc/ldd3/ch08s02.html
关于内存管理的两份资料:http://lsec.cc.ac.cn/~tengfei/doc/ldd3/ch15.html
http://memorymyann.javaeye.com/blog/193061

1. Linux Cache的体系

在 Linux 中,当App需要读取Disk文件中的数据时,Linux先分配一些内存,将数据从Disk读入到这些内存中,然后再将数据传给App。当需要往文件中写数据时,Linux先分配内存接收用户数据,然后再将数据从内存写到Disk上。Linux Cache 管理指的就是对这些由Linux分配,并用来存储文件数据的内存的管理。

下图描述了 Linux 中文件 Cache 管理与内存管理以及文件系统的关系。从图中可以看到,在 Linux 中,具体的文件系统,如 ext2/ext3/ext4 等,负责在文件 Cache和存储设备之间交换数据,位于具体文件系统之上的虚拟文件系统VFS负责在应用程序和文件 Cache 之间通过 read/write 等接口交换数据,而内存管理系统负责文件 Cache 的分配和回收,同时虚拟内存管理系统(VMM)则允许应用程序和文件 Cache 之间通过 memory map的方式交换数据,FS Cache底层通过SLAB管理器来管理内存。

Linux Cache体系 1
下图则非常清晰的描述了Cache所在的位置,磁盘与VFS之间的纽带。

Linux Cache体系 2

2. Linux Cache的结构

在 Linux 中,文件 Cache 分为两层,一是 Page Cache,另一个 Buffer Cache,每一个 Page Cache 包含若干 Buffer Cache。内存管理系统和 VFS 只与 Page Cache 交互,内存管理系统负责维护每项 Page Cache 的分配和回收,同时在使用 memory map 方式访问时负责建立映射;VFS 负责 Page Cache 与用户空间的数据交换。而具体文件系统则一般只与 Buffer Cache 交互,它们负责在外围存储设备和 Buffer Cache 之间交换数据。读缓存以Page Cache为单位,每次读取若干个Page Cache,回写磁盘以Buffer Cache为单位,每次回写若干个Buffer Cache。
Page Cache、Buffer Cache、文件以及磁盘之间的关系如下图所示。

Linux Cache实现

Page 结构和 buffer_head 数据结构的关系如下图所示。Page指向一组Buffer的头指针,Buffer的头指针指向磁盘块。在这两个图中,假定了 Page 的大小是 4K,磁盘块的大小是 1K。

Page Cache结构

在 Linux 内核中,文件的每个数据块最多只能对应一个 Page Cache 项,它通过两个数据结构来管理这些 Cache 项,一个是 Radix Tree,另一个是双向链表。Radix Tree 是一种搜索树,Linux 内核利用这个数据结构来通过文件内偏移快速定位 Cache 项,图 4 是 radix tree的一个示意图,该 radix tree 的分叉为4(22),树高为4,用来快速定位8位文件内偏移。Linux(2.6.7) 内核中的分叉为 64(26),树高为 6(64位系统)或者 11(32位系统),用来快速定位 32 位或者 64 位偏移,Radix tree 中的每一个到叶子节点的路径上的Key所拼接起来的字串都是一个地址,指向文件内相应偏移所对应的Cache项。

Page Cache使用的Radix Tree 1

查看Page Cache的核心数据结构struct address_space就可以看到上述结构(略去了无关结构):

struct address_space  {
struct inode             *host;              /* owner: inode, block_device */
struct radix_tree_root      page_tree;         /* radix tree of all pages */
unsigned long           nrpages;  /* number of total pages */
struct address_space       *assoc_mapping;      /* ditto */
......
} __attribute__((aligned(sizeof(long))));

下面是一个Radix Tree实例:

Page Cache使用的Radix Tree 2

另一个数据结构是双向链表,Linux内核为每一片物理内存区域(zone) 维护active_list和inactive_list两个双向链表,这两个list主要用来实现物理内存的回收。这两个链表上除了文件Cache之 外,还包括其它匿名(Anonymous)内存,如进程堆栈等。

Linux Cache 置换算法

相关数据结构如下:

truct page{
    struct list_head list;   //通过使用它进入下面的数据结构free_area_struct结构中的双向链队列
    struct address_space * mapping;   //用于内存交换的数据结构
    unsigned long index;//当页面进入交换文件后
    struct page *next_hash; //自身的指针,这样就可以链接成一个链表
    atomic t count; //用于页面交换的计数,若页面为空闲则为0,分配就赋值1,没建立或恢复一次映射就加1,断开映射就减一
    unsigned long flags;//反应页面各种状态,例如活跃,不活跃脏,不活跃干净,空闲
   struct list_head lru;
   unsigned long age; //表示页面寿命
   wait_queue_head_t wait;
   struct page ** pprev_hash;
   struct buffer_head * buffers;
   void * virtual
   struct zone_struct * zone; //指向所属的管理区
}
typedef struct free_area_struct {
    struct list_head free_list;   //linux 中通用的双向链队列
    unsigned int * map;
} free_area_t;
typedef struct zone_struct{
    spinlock_t        lock;
    unsigned long offset;  //表示该管理区在mem-map数组中,起始的页号
    unsigned long free pages;
    unsigned long inactive_clean_pages;
    unsigned long inactive_dirty_pages;
    unsigned pages_min, pages_low, pages_high;
    struct list_head inactive_clean_list;   //用于页面交换的队列,基于linux页面交换的机制。这里存贮的是不活动“干净”页面
    free_area_t free_area[MAX_ORDER]; //一组“空闲区间”队列,free_area_t定义在上面,其中空闲下标表示的是页面大小,例如:数组第一个元素0号,表示所有区间大小为2的 0次方的页面链接成的双向队列,1号表示所有2的1次方页面链接链接成的双向队列,2号表示所有2的2次方页面链接成的队列,其中要求是这些页面地址连续
    char * name;
    unsigned long size;
    struct pglist_data * zone_pgdat;   //用于指向它所属的存贮节点,及下面的数据结构
    unsigned  long  zone_start_paddr;
    unsigned  long    zone_start_mapnr;
    struct page * zone_mem_map;
} zone_t;

3. Cache预读与换出

Linux 内核中文件预读算法的具体过程是这样的:
对于每个文件的第一个读请求,系统读入所请求的页面并读入紧随其后的少数几个页面(不少于一个页面,通常是三个页 面),这时的预读称为同步预读。对于第二次读请求,如果所读页面不在Cache中,即不在前次预读的group中,则表明文件访问不是顺序访问,系统继续 采用同步预读;如果所读页面在Cache中,则表明前次预读命中,操作系统把预读group扩大一倍,并让底层文件系统读入group中剩下尚不在 Cache中的文件数据块,这时的预读称为异步预读。无论第二次读请求是否命中,系统都要更新当前预读group的大小。
此外,系统中定义了一个 window,它包括前一次预读的group和本次预读的group。任何接下来的读请求都会处于两种情况之一:
第一种情况是所请求的页面处于预读 window中,这时继续进行异步预读并更新相应的window和group;
第二种情况是所请求的页面处于预读window之外,这时系统就要进行同步 预读并重置相应的window和group。
下图是Linux内核预读机制的一个示意图,其中a是某次读操作之前的情况,b是读操作所请求页面不在 window中的情况,而c是读操作所请求页面在window中的情况。

Cache预读算法

Linux内核中文件Cache替换的具体过程是这样的:刚刚分配的Cache项链入到inactive_list头部,并将其状态设置为active,当内存不够需要回收Cache时,系统首先从尾部开始反向扫描 active_list并将状态不是referenced的项链入到inactive_list的头部,然后系统反向扫描inactive_list,如果所扫描的项的处于合适的状态就回收该项,直到回收了足够数目的Cache项。其中Active_list的含义是热访问数据,及多次被访问的,inactive_list是冷访问数据,表示尚未被访问的。如果数据被访问了,Page会被打上一个Refrence标记,如果Page没有被访问过,则打上Unrefrence标记。这些处理在swap.c中可以找到。
下图也描述了这个过程。

Linux Cache 置换算法

下面的代码描述了一个Page被访问它的标记为变化:

*
 * Mark a page as having seen activity.
 *
 * inactive,unreferenced        ->      inactive,referenced
 * inactive,referenced          ->      active,unreferenced
 * active,unreferenced          ->      active,referenced
 */
void mark_page_accessed(struct page *page)
{
        if (!PageActive(page) && !PageUnevictable(page) &&
                        PageReferenced(page) && PageLRU(page)) {
                activate_page(page);
                ClearPageReferenced(page);
        } else if (!PageReferenced(page)) {
                SetPageReferenced(page);
        }
}

参考文章:
http://lsec.cc.ac.cn/~tengfei/doc/ldd3/
http://memorymyann.javaeye.com/blog/193061
http://www.cublog.cn/u/20047/showart.php?id=121850
http://blog.chinaunix.net/u2/74194/showart_1089736.html
关于内存管理,Linux有一个网页:http://linux-mm.org/

Load和CPU利用率是如何算出来的

8月 10th, 2010 | Posted by | Filed under 操作系统

相信很多人都对Linux中top命令里“load average”这一栏困惑过,到底什么是Load,Load代表了什么含义,Load高会有什么后果?“%CPU”这一栏为什么会超过100%,它是如何计算的?
带着这些问题,我们通过一些测试,来探索下其中的不解之处。

首先,我们通过实验来大概确定其计算方式:
测试服务器:4核Xeon处理器
测试软件:MySQL 5.1.40
服务器上除了MySQL没有运行其他任何非系统自带软件。因为MySQL只能单线程运行单条SQL,所以可以很好的通过增加查询并发来控制使用的CPU核数。

空载时,top的信息为:

top – 14:51:47 up 35 days, 4:43, 1 user, load average: 0.00, 0.00, 0.00
Tasks: 76 total, 1 running, 75 sleeping, 0 stopped, 0 zombie
Cpu(s): 0.0%us, 0.0%sy, 0.0%ni, 99.5%id, 0.1%wa, 0.2%hi, 0.2%si, 0.0%st

在数据库中启动一个大查询:

top – 15:28:09 up 35 days, 5:19, 3 users, load average: 0.99, 0.92, 0.67
Tasks: 80 total, 1 running, 79 sleeping, 0 stopped, 0 zombie
Cpu0 : 0.0%us, 0.0%sy, 0.0%ni, 96.3%id, 0.0%wa, 1.3%hi, 2.3%si, 0.0%st
Cpu1 : 0.0%us, 0.0%sy, 0.0%ni,100.0%id, 0.0%wa, 0.0%hi, 0.0%si, 0.0%st
Cpu2 : 98.7%us, 1.3%sy, 0.0%ni, 0.0%id, 0.0%wa, 0.0%hi, 0.0%si, 0.0%st
Cpu3 : 0.0%us, 0.0%sy, 0.0%ni,100.0%id, 0.0%wa, 0.0%hi, 0.0%si, 0.0%st

同时可以看到%CPU也是在100%

PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
877 mysql 15 0 308m 137m 4644 S 99.9 6.8 15:13.28 mysqld

然后开启第二个大查询,不久就可以看到top信息的变化,Load到了2:

top – 15:36:44 up 35 days, 5:28, 3 users, load average: 1.99, 1.62, 1.08
Tasks: 80 total, 1 running, 79 sleeping, 0 stopped, 0 zombie
Cpu0 : 0.0%us, 0.0%sy, 0.0%ni, 97.7%id, 0.0%wa, 1.0%hi, 1.3%si, 0.0%st
Cpu1 : 99.0%us, 1.0%sy, 0.0%ni, 0.0%id, 0.0%wa, 0.0%hi, 0.0%si, 0.0%st
Cpu2 : 0.0%us, 0.0%sy, 0.0%ni,100.0%id, 0.0%wa, 0.0%hi, 0.0%si, 0.0%st
Cpu3 : 99.0%us, 1.0%sy, 0.0%ni, 0.0%id, 0.0%wa, 0.0%hi, 0.0%si, 0.0%st

也可以观察到%CPU增加到了200%:

PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND
877 mysql 15 0 312m 141m 4644 S 199.8 7.0 22:31.27 mysqld

由此可以简单的做出如下临时结论:
1. %CPU是由每个核的CPU占用律之和算出来的。
2. load跟执行的任务数有关
不过要想准确的知道其含义,还是必须从源码入手。
阅读全文…

标签: , ,

理想的计算机科学知识体系

8月 8th, 2010 | Posted by | Filed under 学习研究

学了这么多年的计算机,真没好好梳理过整个计算机科学体系,正好看到一篇帖子讨论此问题,就此总结一下吧。

  • 理论
    • 数学理论(书籍:《具体数学》《离散数学》《数理逻辑》)
      • 基础数学
      • 高等数学(极限理论)
      • 数论(Number Theory)
      • 离散数学(集合论、图论)
      • 数理逻辑
    • 形式语言与自动机(Automata,书籍:《形式语言与自动机》)
    • 几何理论(Geometry)
  • 硬件(书籍:《Computer Architecture: A Quantitative Approach》)
    • 计算机组成原理:计算机组成部件、CPU时间片、存储体系、IO接口、总线技术
    • 计算机体系结构:多处理机、流水技术、指令调度
    • 计算机微机原理:一种处理机的具体结构、引脚作用
    • 数字电路:逻辑门电路、触发器、组合电路设计
  • 机器语言编程
    • 汇编程序设计(Assembly)
    • 可执行文件格式
    • 链接(Linking)与加载(Loading)
  • 操作系统(书籍:《现代操作系统》《操作系统实现》)
    • 进程与线程理论
    • 段页式内存管理
    • 文件系统
    • IO管理
    • 内核与驱动
  • 程序设计基础(书籍:《The Art of Computer Programming》)
    • 数据结构(书籍:《数据结构与算法分析》)
    • 算法
      • 算法分析(书籍:《算法分析》)
      • 算法设计(书籍:《算法导论》)
  • 程序设计语言
    • 编译原理(《编译原理》龙书)
    • C一定要会
    • C++/Java建议要会(《C++ Primer》《Effective C++》《Thinking in Java》)
    • C#/F#等新语言了解
    • Python/Perl/Shell等脚本语言掌握其一
  • 编程框架和库
    • 平台程序开发
      • Windows程序设计(书籍:《Programming Windows》)
      • Linux/Unix系统编程(书籍:《Advanced Programming in the UNIX Environment》)
      • 跨平台程序设计
    • 程序库
      • C++:STL/Boost/MFC/
      • 跨平台:GTK/wxWidgets/Qt
      • Perl:CPAN
  • 程序设计与软件工程
    • 面向对象的程序设计方法,必须掌握(书籍:《深入浅出设计模式》《Thinking in UML》《The Unified Modeling Language User Guide》)
    • 敏捷(Agile)、统一过程(RUP)、迭代方法(Iterative)建议掌握一些
    • 调试和测试方法必须掌握一些
  • 应用
    • 计算机网络(书籍:《计算机网络》)
    • 数据库(书籍:《数据库系统概念》《数据库系统实现》)
    • WEB应用
    • 并行开发(Concurrent Programming)
    • 分布式系统(Distributed System)

非常理想的计算机科学知识结构,原则上每个CS毕业的同学都应该具备这些技能,不过包括我在内绝大部分同学都有欠缺,虽然毕业了,继续努力补上自己的缺陷。

利用临时表清除数据库重复数据

7月 25th, 2010 | Posted by | Filed under 数据库

上周遇到一个问题,开发忘了告诉DBA需要唯一索引,导致线上一个库出现了大量重复数据,需要立即清除,重复数据只保留一条,于是采用了临时表的方案。

首先查看重复数据的数量:

SELECT  c1,c2 FROM tbl GROUP BY c1,c2 HAVING count(ID)> 1

然后创建一张临时表,把上述结果存下来,这就是存在重复的数据各选出一条:

CREATE TABLE tbl_tmp_1 
SELECT * FROM tbl GROUP BY c1,c2 HAVING count(ID)> 1

然后通过上述临时表与原表关联,获取全部存在重复的数据:

CREATE TABLE tbl_tmp_2
SELECT b.* 
FROM tbl_tmp_1 a, tbl b
WHERE a.c1 = b.c1
AND a.c2D = b.c2;

验证一下有没有选错,即有没有不重复的数据被选出来了:

SELECT *
FROM tbl_tmp_2 
GROUP BY c1, c2
HAVING count(*) = 1;
SELECT b.* 
FROM tbl_tmp_2 a, rbl b
WHERE a.c1= b.c2
AND a.c2= b.c2
AND a.id=b.id;

全量删除所有重复数据:

DELETE FROM 
tbl, tbl_tmp_2 USING tbl
INNER JOIN tbl_tmp_2
ON tbl.id = tbl_tmp_2.id;

将原重复数据中的一条都插入数据库中:

INERT INTO tbl
SELECT * FROM tbl_tmp_1;

都做完就可以加上唯一索引了:

ALTER TABLE tbl
ADD UNIQUE uk_tbl_c1_c2 (`c1`,`c2`) ;
标签:

每周推特 2010-07-25

7月 25th, 2010 | Posted by | Filed under 生活轨迹
  • 俗话说的好看热闹看多了最终将会变成悲剧,中石油,看你这次培多少,耻笑完BP,这次轮到你了 #
  • 每天回家给老婆送饭,下班就冲回家,好久没有加班了,悲剧 #
  • RT @wenyunchao: 天朝上人:苏州通安发生大规模群体事件,过万人参与。18日南京机场、无锡机场大多数民用航班延迟数小时,机场被征用空运各省赶来驰援的平暴武警据悉为了保证世博会安全,防止紧邻上海的苏州闹事,在苏州聚集的武警特警已经达到五万八千人。 #
  • 一台数据库空间不足了,紧张的删除数据,暂时解决了Warning,淡定下来想想其实不用紧张,剩下的空间足够支撑半个月,部署上按日期Drop分区的脚本,足以在一个月内将空间平滑的回收,没必要按日期DELETE,我不淡定…… #
  • 幸亏Donny把我送回来,否则绝对落汤鸡了 #
  • 要买凉鞋和短裤了,这天气穿运动鞋脚可以游泳了 #
  • @Fenng 由Sky.Jian转发给你的简历 in reply to Fenng #
  • 瑞典有句老话:钱是可以储存的,而时间是不能储存的,你怎么花时间,决定了你一生的生活质量。 #
  • 内网里我的实习生标志没了 #
  • @yangsimin B2B in reply to yangsimin #
  • 真看到一哥们拿个Mac装个Win的…… #
  • 听这Linux高级程序设计的培训,感觉回到了当初搞嵌入式的时候搞得东西 #
  • 永远需要记住的命令只有一个,man #
  • 优化的目的是降低成本,而不是提高效率,否则会累死。 #
  • 能插条内存解决的问题,别费那劲优化这优化那,宁费料勿费工,工程师是低成本解决问题,研究员才是想尽一切办法优化性能,“如何让NFS性能提高0.7%”,然后哗哗列出一个长单子,这是研究员做的事,不应该是工程师的思维。 #
  • Linux下的内存碎片整理:启动一个进程狂向系统申请内存,让系统被迫整理合并碎片,然后进程一退出,看起来可用内存就多了。纯属恶作剧程序,在Linux中内存碎片其实并不影响效率。 #
  • SWAP分区被占用,并不是表示内存不足,但是SWAP被频繁的换入换出,才是内存不足,当然,也可能是内存泄漏~ #
  • 闭源软件有两种:第一是舍不得,第二是不好意思。我觉得不好意思还是占多数,开源了就没人敢买了或者没人敢雇用作者了。所以开源软件的平均质量高于闭源软件,但是文档上开源软件平均质量远低于闭源软件。 #
  • @ygcoffice 有时间耗在极端的调优上,才是真不差钱,工程师工资不要钱?能做高级调优的工程师不要钱么?我说的是低成本,包括人力成本。 in reply to ygcoffice #
  • Unix/Linux就是个半成品,只提供机制,不提供策略。装好系统第一件事就是写好自己要用的脚本来做自己的事情,完成Unix/Linux的最后一步,自己加上适合自己的策略。 #
  • 关于中科院力学所怀柔试验基地被非法拆毁的严正声明,http://goo.gl/Np9K, 有钱还是赶紧跑吧,研究所都能拆,还有什么不敢拆的 #
  • @yanzisky1989 把插头拔了 in reply to yanzisky1989 #
  • 周末蹭饭大军多到惊人,大都背着个包,吃完就走出公司了。 #
  • RT @rtmeme: RT @81xiao RT @virushuo: 蒋涛最后那段评论太没眼光了,要说在移动平台上的布局,中国还没有互联网企业超过腾讯。据我所知,动用在美国所有员工的信用卡去第一时间买到iPad通通寄回国内做研发的,只此一家。 #
  • 给@yanzisky1989 装系统,天哪,女生的电脑怎么这么乱 #
  • 搞C的看不起搞C++的搞C++的看不起搞java的 搞java的看不起高.net的 搞.net的看不起搞js的 搞js的看不起搞html的 搞html的看不起美工. 最后美工周末去泡mm的时候, 一群傻X在那里加班 #

Powered by Twitter Tools

标签: