荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: tang (独孤九剑〖玄铁重剑〗), 信区: Linux
标 题: 好书共赏－《Unix Internels》（四）
发信站: BBS 荔园晨风站 (Sat Nov 27 18:49:44 1999), 站内信件
【 以下文字转载自 tang 的信箱 】
【 原文由 tang.bbs@bbs.net.tsinghua.edu.cn 所发表 】
发信人: BlueOcean (Blue), 信区: Unix
标 题: 好书共赏－《Unix Internels》（四）
发信站: BBS 水木清华站 (Tue Apr 28 01:07:10 1998)
Chapter 11 Advanced File Systems
首先提到interleave的问题.不懂interleave的人可以看这里. 这里提到一个关键
性的bench mark. Unix filesytem的效率在於写入资料的速度. 因为Unix系统的
cache作的已经很好了, 所以read()大部份都发生在cache上, 但是write()则必须
把资料写到硬碟去,变成了bottleneck. 如何改善write()的速度就可以提升
整体效率.
皆下来讨论kernel要如何把资料写到disk上,在crash时有最小的 损失,
fsck才能够做到最大的复原.
File System Clustering (Sun-FFS)
一般的档案存取都是sequential的,虽然会透过好几个read/write system call
达成. 如果kernel也可以像C stdio一样收集这些data block,然後再一起写到
disk去可以增加效率,这就是file system clustering. SunOS首先提出这种办法,
後来SVR4和4.4BSD也都采用了. file system clustering提升了不少FFS的效率,
使得FFS仍然足以与新提出的档案系统匹敌.
The Journaling Approach
这里logging = journaling, 意思是记录. journaling file system or
logging file system (jfs or lfs)基本上就是把对file system的修改
(包括对档案属性,档案内容,档案大小的修改)都以append only的方式附
加(记录)到单一的档案(磁碟空间)去.最主要的目的是crash之後,只有最
後append的部份有可能出问题, fsck的速度极快(只要放弃最後那段log
就可以了). 不过这样说好像太简单了,实际上lfs还要复杂些,有些race
condition要处理.
一个档案由两个资料组成, 一个是data, 另一个叫meta-data,指的是档案
的permission,access time, modify time,...等等.
我们可以下面的特性来区分lfs:
log 什麽东西? data, metadata都log, 或者是只记录meta-data. meta-data
logging更可进一步决定是所有对档案属性的改变都记录起来, 或者只记录影
响档案系统结构的改变就好了. (time-stamps, ownership, permissions等要
是当机时没改到基本上不会影响档案系统的完整)
实作的方式是使用纯LFS(log-structured file system),另一者是用lfs
的概念辅助FFS,改善crash的处理(log-enhanced file system). 纯LFS需
要full data logging, 辅助性lfs通常就是mata-data logging而已.
crash recovery方法也有两种, 一种是redo-only log,另外一种是undo-redo.
redo-only log在 crash後把残馀的log继续做完. undo-redo log则可以选择
redo或undo.不同点差在crash 後的处理. redo-only较省disk space,
但是crash recovery有较多synchronization 的问题会出现. undo-redo
的方式有较多的的优点,有synchronization 问题的地方可以把档案还原.
既然要undo,就会记录档案原来的资料, 当然较浪费空间.
本章讨论的两个lfs, 4.4BSD LFS和 Episode File System (by
Transarc,由AFS衍生出来). Episode是OSF DCE标准采用的local
file system, 是DFS的基础. 4.4BSD LFS是根据Sprite作业系统
的研究而来的. LFS使用redo-only log. Episode使用redo-undo log.
对LFS还是搞不清楚什麽是append only log? 没关系, 看了4.4BSD LFS後就了解了.
Figure 11-2一目了然. LFS基本上把DISK当成是一条磁带,每个block大小为0.5 MB.
一个block在disk上是一段连续的空间, 不过相邻的(logically..) block则没有在
disk上相邻, 而是用list的方式相邻. 用程式表示如下:
struct log_segment { /* block在LFS的术语里面叫log segment */
int next; /* 下一个log_segment 所在的位址 */
char data[0.5MB-sizeof(int)];
};
而FFS则是在disk上以渐进的方式动态配置新的log segment以记录log.
segment间以linked list的方式串在一起.
Kernel记录的log就是这样子记录到disk上的. 在这个segment chain
的tail才是整个档案系统的最新资料.不过旧的资料也没有被盖掉就是了.
LFS还有一个机制, 类似garbagge collection, 更像defragementation.
它使用一个cleaner process来清理旧的log. 这个process会固定的把旧
的log独出来(以segment为单位).然後他会将这个segment的内容与实际
的资料比对,要是这个segment内的资料都是没有用的资料(已被新的资料
所取代了)那麽cleaner process就可以把此segment free掉. 如果segment
还有一点东西, 怎麽办? 简单! 重写一次,append到最新的log去就好了
嘛(感觉好像nu的speed disk :).
LFS仍然维持directory和inode的架构, 只不过以前的inode是固定
在disk blocks的最前端,而现在inode则是分散各地,存在各log
segment里面. 这样子怎麽读这个file system呢? LFS还有一个
inode map, 记录所有inode的位置. inode map被当成是一般的
data一般,也是定期会写到log里面去. kernel就是靠此inode map
作为读取这个档案系统的开端.
大家最感兴趣的, 应该还是效率问题了. 首先LFS需要消耗更为大量
的记忆体才能满足他的运作所需, 有时候是个缺点. 与FFS比较的结
果在大部份的状况下都胜过FFS, 除了在高度多工的时候稍微输了一
点. Sun-FFS (有file system clustering和一些小地方的改进)和
LFS比就不相上下了. BSD LFS在处理meta-data方面较Sun-FFS强(create,
remove, mkdir,rmdir....). 但在read/write等io集中的测试中 Sun
FFS则较快, 特别是LFS cleaner启动的情况下更是如此. 显然
clustering发挥了不少功效.
这边你要谨记在心的是LFS在metadata处理会赢过FFS, 是因为写入
动作较有效率的原因(sequential write), 前面已经提到file system
的瓶颈在write...
Sun FFS和BSD LFS在模拟实际状况的bench mark上的平均分数是
差不多的. LFS比FFS占优势的地方大概是快速的复原能力吧!
本节引用了几份测试报告和bench mark, 有兴趣的可以看参考书目,
看人家如何评量一个档案系统的效能.
本节提到另一个有趣的产品, Write-Anywhere File Layout (WAFL)
system, 是一家名为 Network Appliance Corporation 的 FAServer
系列的NFS产品. WAFL整合了log-structured file system, NVRAM
(non-volatile ram, 像PC cmos的咚咚),和RAID-4磁碟阵列, 提供了
高速的NFS response time. WAFL 有一个特色是许多系统管里者有兴
趣的, 就是snapshot. snapshot就是备份的意思嘛! 也就是系统某一时间
的状态. snapshot在log-structured file system下应该不难制作,
因为所有的资料都用append模式嘛..把cleaner process的功能作个
修改就是了. snapshot 优於传统的备份的原因应该很明显, 传统的
备份过程必须花上一段时间,系统在这段时间内若有修改的话, 这段
时间内的修改则不知道有没有备份到.而snapshot则可以像照相一般
得到系统瞬间的备份.使用者也可以利用snapshot取得旧的档案内容
或达到undelete的功能.
由LFS和Sun-FFS的比较可以了解meta-data logging(log-enhanced
file system)存在的原因了, 取长补短嘛. 本章也讨论了meta-data
logging的系统. meta-data logging在商品化的系统上较受欢迎,
成为市场主流, 因为他可以架构在FFS上,改变不会太大, 还可以和
对FFS的改进(如clustering)互相配合,相得益彰.
本章讨论的另一个lfs是Transarc的Episode File System. Episode
采用redo-undo metadata logging, 并且他的file system可以横越
好几个硬碟. Episode也提供了类似snapshot的功能, 称为cloning.
cloning使用copy-on-write的技术,只复制anode (Episode的inode).
Episode在security方面也提供了POSIX式的access-control list (ACL),
提供较传统Unix更为精细的档案属性控制.
要是你可以拦截使用者对某些目录的存取,然後偷天换日一下, 那一定可以
让系统更有趣. 比如说Mail来的时候通知使用者(不用一直polling), 使用者
读某个档时就把目前时间印出来, 使用者open /tcp/<service>/<hostname>时,
就产生对<sevice:hostname>的连线,让没有网路知觉的shell,awk程式也可以
轻松处理网路上的资料.
本章讨论了两个这样的系统,第一个是watchdogs,这是学生的研究作品,
整合性不足. 4.4 BSD Portal file system才可以算完整解决方案.
一个新的File System写起来很复杂, 而一般人可能只想在file system
上加点小功能,比如说on-line compression等等. 4.4BSD和SunSoft皆
提出了Stackable file system的模组化机制,以达到这个目的.
SunSoft的版本在本书写作的时候还在草稿阶段而已.BSD的则是已经放
入4.4BSD原始码内了.
Chapter 12 Kernel Memory Allocation
本章以後开始讨论到记忆体管理的问题了. Chapter 12讨论kernel
如何管理自己所用的资料结构所使用的记忆体,如 inode的配置等问
题. Chapter 13,13,15则是讨论kernel的virtual memory管理. 被
kernel用来放自己的资料结构的记忆体就不能给paging system用,
所以两者之间如何平衡是很重要的.
本章提了好几个memory allocator. 其中提到C Library的malloc所
使用的方法值得提出来和大家分享. malloc配置记忆体是所谓的power
of two free lists.把记忆体分成不同的2的次方的大小
(32,64,128...1024bytes)来管理. 不过allocator保留这些block
的最前面几个byte当作header, 当这块记忆体不用时(free),
则header指向下一个free block, 彼此间是一个list. 而使用中
时header则指向他所属的list. (比如说大小是32的list), 这样
子free()才会知道怎麽归还记忆体.如果你有K&R这本书的话, 可
以翻翻看书上的□例是不是这样子作的.
power-of-two的配置方式有个致命的缺点, 就是可使用的空间只有
sizeof(block)-sizeof(header),也就是略小於(32,64,128,...1024).
如果应用程式要一个比如说64bytes的记忆体, 那麽64-block就装不下,
要分配一个128-block才行, 造成浪费.回想一下,你写程式是不是很喜欢
malloc(128), malloc(512), malloc(1024)呢? 是不是感觉上
应该对performance比较好呢? 看完这段描述, 那你可能就不会
这麽想了. 我想,这也是许多人评论不同的c compiler记忆体管
理优劣的一个地方吧!如果你常自己抓一些source code来安装,
就可以了解为什麽很多作者都弃系统的library不用,
自己提供malloc了吧.
书上提到power of two的改进法, 称为McKusic-Karels Allocator.
获得4.4BSD和Digital UNIX采用. McKusic-Karels 配置法把一段连
续的记忆体都切成固定的大小, 比如说32bytes, 那麽使用中的header
就不用指回他所属的list了, 因为由他的位置kernel就可以知道他属
於哪一国的.
皆下来提到Buddy System, 这是和power of two不太一样的配置法,
优点是free()之後的临接空间可以聚合起来成为较大的可用空间.
(power-of-two这方面作的并不好). 这个优点称为coalescing.并
且Buddy System可以简易的和paging system交换记忆体空间,
使的kernel占用的记忆体空间可以动态的调整. 不过他的performance
不太好, 因为每次release momory,allocator就很贪心的把所有
临接的记忆体空间并起来, 浪费许多时间.
SVR4使用了修改过的Buddy演算法 - Lazy Buddy 作为配置kernel
objects的方法.
Buddy系统和power of two一样, 都是以2^n作为配置记忆体的单位.
Mach, OSF/1使用了另一种方法, Zone Allocator. 这个配置法不
再以2^n作为配置单位, 而是以物件为导向来配置.也就是说allocator
从paging系统要来一块记忆体,把他按照object的大小切成n份,
比如说, port资料结构为104 bytes, 那麽mach会把要来的记忆体
(比如说1KB),分成1024/104块来使用. 这很明显提高了记忆体
的利用率. 给一个object用的记忆体称为一个zone, 比如说zone
of ports, zone of inodes等等. 不同的object使用不同的zone,
即使他们的大小一样.
Zone Allocator使用背景的garbage collection程式来回收记忆体.
本章最令人拍案叫绝的是Solaris 2.4的Slab Allocator.
Slab allocator和zone allocator 方向差不多, 以object size
当成配置单位,但是他更进一步分析记忆体的使用情形. 比如说
inode好了.首先我们要一块记忆体 - malloc(sizeof(inode)),
然後initialize inode,接著是正常的使用, 使用完毕後便用free()
归还记忆体. Slab allocator注意到free()之後的记忆体的资料
和刚刚initialize时差不多, 比如说inode的reference count
一定是降为零等等. Kernel有许多资料结构都是还原到和initialize时
一样的时候才会free掉.再说一个例子, 一个mutex lock initalize时
是unlock的状态, free时也是unlock的.
Slab allocator利用这项特性, 事先把所有的(用Mach的语言是zone)初始化,
那麽就可以省下不少initialize的时间.
另一个slab allocator注意到的问题是cpu cache的使用率.一般的cache演算法是
cache location = address % cache_size
一般的power of two配置法配置的记忆体都会经过align, 并且大多数程式
的习惯会把最常用的资料栏位放在一个结构的最前面. 这两个效应合在一起,
造成这些栏位互相的清掉彼此的cache. 512kb的cache可能只有部分有作用.
更甚者, 如果主记忆体使用interleave的方式, 比如说SPARC center 2000
使用两个bus, 较低的256byte使用第一个bus,较高的256byte使用第二个bus,
那麽所有的data可能会集中在第一个bus上, 造成不平衡现象.
Slab的解决方法是在向paging系统取得一块block之後, (假设为1KB),
Slab把他要用的资料摆在这个block最後面, 假设占y bytes. 假设所
要配置的是inode, 大小跟前面Mach的例子一样皆是104. 那麽这块记
忆体可以提供(1024-y)/104个inode. 并且有一些馀数, 也就是剩下
一些多馀的记忆体.Slab善用这些记忆体, 将之二等分, 一份摆在这
块记忆体的最前面,一块摆在最後面. 最前面那块称为coloring area.
Slab设法在每次配置的page上使用不同大小的coloring area, 以有效的
分散资料map到cache中的位置,增加cache rate.
Allocator Footprint指的是Allocator在配置记忆体的时候将自己,
以及所参考到的资料写到cpu cache/ TLB (translation lookaside
buffer), 在cache/TLB上面产生的"脚印". Allocator在cache/TLB内
所留下的资料基本上是没有用的, 并且妨碍真正有用的资料留在cache
上. buddy演算法需要参考许多资料才能配置记忆体, 会产生大量的
"footprint", 导致cache miss增加. McKusick-Karels和zone allocator
的足迹皆很小, 原因是配置记忆体的时候直接从free list上把第一个
element抓出来而已. 所以一个好的配置法应该使用简单的演算来配置
物件. Slab也是使用相同的原则, 不论是配置或者是释放,都是简单的
一两行运算而已,所以foot print也很小.
Chapter 13 Virtual Memory
本章对virtual memory作个通论, 如paging, segmentation, swaping,
virtual memory等等作个介绍, 跟作业系统的书讲的差不多. 然後个案
讨论了几个热门的CPU的MMU. MIPS R3000比较特别, CPU没有自动处理
TLB, 而是提供了一堆TLB暂存器让kernel自己玩.
现代Unix皆使用paging的机制来提供虚拟记忆体. 不过通常CPU对
paging的机制都不完全. kernel除了维护cpu所需的paging table
之外, 自己还需要维护一份相对应的表格, 以满足所需.
本章最後讨论了4.3BSD的Virtual Memory系统. 4.3BSD使用cmap[]
的资料结构来辅助paging管理. cmap的方式是在VAX-11的架构下设
计的, 没有shared memory也没有shared library, 没有memory
mapped file, 没有copy-on-write等等的支援,不胜枚举, 在现代
已经可以作古了. 不过4.3BSD的架构仍然为日後的发展奠立的良好
的基础.
BSD对swap space的处理颇为保守. 要求所有在主记忆体的page
在配置前都必须要先有一块swap space. 所以swap space的大
小限制了可以执行的程式数量.不过这也保证程式只有在fork或
exec时才会发生记忆体不足的现象, 而不会执行到一半要被swap
出去, 却找不到swap space可用的窘况.也就是说如果你的电脑有
64MB的记忆体,但是只划了16MB的记忆体,这样的系统只愿意让你使
用16MB而已, 这也是有些系统管理的书籍建议你swap space不要比
main memory小的原因.
Chapter 14 The SVR4 VM Architecture
SVR4的VM Architecture源自於SunOS 4.0引进的VM技术(Virtual
Memory之意).SunOS发展VM的用途在於提供memory sharing,
shared libraries, memory-mapped files. 又因为SunOS可以在
M68K, I386, SPARC上执行, 所以VM架构十分的portable.
之後, 在Sun和AT&T合力之下, 以VM为基础, 设计了SVR4的virtual
memory系统.取代SVR3以前使用的regions架构. regions架构在Bach
的书上有提到.
Memory-Mapped Files是透过virtual memory技术, 把档案的内
容映到程式的定址空间, 使得程式可以直接以存取记忆体的方
法存取档案. kernel提供了mmap() 系统呼叫来作为此机制的介面.
SVR4 VM的设计概念, 可以说是颠覆了传统对记忆体的观念.
在VM里面,physical memory变成是virtual address space的
cache而已. 怎麽说呢? 一个程式的位址空间可以被VM赋予不同
的意义, 比如说某一段表示 text, 指向硬碟上可执行档的text区段,
某一段表示data, 指向swap area, 某段指向某个档案, 为memory
mapped file的空间等等, VM的工作就是把这些实体的资料根据page
fault把他载入"cache" -- 主记忆体(以 page 为单位),好让cpu可以
存取.在主记忆体上的资料都是暂时的, 他们都有个实体的贮存装置
作为长时间记录资料的地方.(这里的长时间指的是process block著,
sleep时, 或者被swap out的意思).
前一段提到data区段指向swap area是为了说明方便起见瞎掰的. 真正的
作法是使用anonymous page来收容这些无家可归的小孩. data区段本来
指向档案, 但是设下一个flag, 只要一被修改, 就变成 anonymous page,
anonymous page就会自动使用swap area当作回存的装置.
一个记忆体空间映到不同的东西, 就应该有不同的程式来处理. SVR4把
一段空间称为一个segment. 处理这种segment的程式就是segment driver.
本节并提到vnode和paging系统的相互作用.
Solaris 2.x对SVR4的改进为提出virtual swap space的方法, 把
swap space扩展成swap area + physical memory (所以swap大小
可以小於physicalmem了?!)并且可以动态的重新分配swap区. 之前
的作法是某块swap区只要配给哪个page, 那整个process的生命周
期内, 这块swap就是许配给这个process的特定page,不会再换了,
这样的缺点是不能动态的移除swap disk/file.为了达到这个
功效, Sloaris设计了swapfs, 用来管理swap space. anonymous
page从此就回存到swapfs上, 而不是直接pass过filesystem,
存到swap上了.
当VM从SunOS移植到SVR4上时, 效能和regions架构相比很不理想. 经过
分析SVR4的fault rate太高了, 所以可以作些改善.
因为VM太懒了, 所有的东西都是page fault之後再作, 而page fault
的代价甚高.所以optimization朝向将一些显然会发生的page fault
减少. 比如说在fork和exec中间一般程式都会做一些事, 所以把
paging table initialize完整是件好事.exec时, 也把新的paging
table initialize好,省得一执行又产生page fault.
exec也会检查新执行的程式是否有text page在主记忆体里,
有的话就顺便include进来.
最後一个改进则是改进copy-on-write. 在fork後, kernel检查parent在
主记忆体内的anonymous page, 把他们都先拷贝起来. 前面提到,
会变成anonymous page的资料,都是有被修改过的, 而此page会在
主记忆体里,没有被swap out,表示最近曾被修改过.事先将这些
page复制的理由就是基於最近被修改的资料, 可能child也会修改之.
这种情况在shell下面最常发生. shell常常自己fork很多次.
而每次fork後都会以相同的pattern来修改变数.
最後本章提了一个测量结果, page fault次数有了明显的改进, 已经改善到
比SVR3时好了.
Chapter 15 More Memory Management Topics
本章提了Mach的virtual memory管理. 虽然是不同的设计, 术语也不同,
但是和SVR4的VM架构有许多地方都是相同的. Mach的设计比较清楚易懂,
如果Chapter 14看不懂,可以先看本章. 4.4BSD VM架构就是基於Mach的.
不过4.4BSD的系统管理比较向SVR4.
本章另一个重点是TLB一致性的处理. 这是在多处理器下发生的问题.
如果kernel改了某个page的资料, 他怎麽让其他的处理器知道并且更正
TLB的内容. 基本上这是一件很麻烦的问题, 尤其是CPU没什麽支援的状况下.
Mach的方法最简单,也最通用(不需要cpu支援,只要有个inter-processor lock),
但是浪费许多时间在synchronize上, 没什麽效率. 处理TLB应该算是
multiprocessor support内最麻烦的问题了, 处理不好,一堆processor
都会浪费时间在synchronize上.
盲目的synchronize造成不少的浪费, 比较聪明的作法是分析什麽时候会修改TLB.
如果是发生在kernel的定址空间, 那麽kernel可以透过谨慎的设计来避开TLB的修改,
那麽需要修改TLB的时机就只剩kernel所无法掌握的user processes了. 而剩下的
这些状况也不是每种都要马上更改其他processor的tlb不可. 因此可以省下了许多
不必要的麻烦.
Chapter 16 Device Drivers and I/O
介绍与device driver, io 相关的课题. 以及device driver 与file system
间的互相配合, dynamic loading unloading等等. 基本上就是device driver
必须提供哪些介面给kernel, 可以使用kernel的哪些function call,和变数.
随Unix版本而异...
Chapter 17 STREAMS
STREAMS架构本来是为了解决character devices重复发展太多程式码和
buffering的问题, 不过STREAMS设计得太强悍了, 使得terminal driver,
pipe和网路driver都利用他来完成. STREAMS已被大多数的UNIX厂商所支持,
成为广为接受的标准, 也是用来写网路driver较受欢迎的架构.
STREAMS使用模组化的方式, 让使用者可以依堆叠的方式循序推入处理模组,
而资料流则是通过一层层的模组达到驱动程式. 反之亦然. terminal driver
就可以专心的处理与terminal沟通的细节, 而与Unix系统其他的部份,以及使
用者介面,可以丢给上层的模组处理就好了. STREAMS架构详细的订定各模组间
要如何沟通和应有的"举止".
System V也定义了一个Transport Provider Interface及Transport Layer
Interface(TPI/TLI), 功用类似BSD的socket介面,用来提供高阶程式设计
的标准介面.
虽然STREAMS/TLI在本书写作之时好像颇具潜力,但是socket介面实在太强势了,
又有winsock助长声势, 显然STREAMS在网路上没成气候, 但是在其他方面
则发展得十分良好.
後记
就这样把这本书有趣的内容整理完了. 希望我的取材可以让那些略懂
Unix的人有更深入的空间,提高层次. 其中我省略了许多Unix Kernel基
础的概念,希望不会让人不知所云才好. 反倒是对Unix的简介好像写的
太详细了, 这是因为我发现有很多中文书在这方面写错了....
前言提到的那几本书(含本书)都很值得想了解Unix者阅读. 有许多的细
节都是要仔细的整篇阅读才会了解的, 像这样的摘要并不能完整的表达.
书中对4.4BSD, Mach, SVR4/Solaris的描述, 我都尽量提及了. 希望对
Linux/FreeBSD/Solaris以及未来的GNU Hurd 以及苹果的狂想曲的了解
有所帮助. 另外你是否也跟我一样发现Sun真的不是一盏省油的灯, 确
实有两三把刷子呢?
本书有个缺点就是校正不太完整. 内文reference到Section 0好几次, 但是
并没有Section 0. 应该是美中不足的地方吧!
本书没有提到tcp/ip网路的部份, 应参考Stevens, TCP/IP Illustrated
Volumne 1,2,3.
本书对shared library以及执行档的结构没有作深入的讨论, 也是一个
遗憾...
--
Shiau Yong-Ching
--
Buck barks in the darkness
※ 来源:·BBS 水木清华站 bbs.net.tsinghua.edu.cn·[FROM: ns.nlsde.buaa.e]
--
※ 转载:·BBS 荔园晨风站 bbs.szu.edu.cn·[FROM: 210.39.3.94]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店