UNIX程式设计师手册第二版

从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真的不是一盏省油的灯, 确
实如此...



★  欢迎分享  ★


--

       十里平湖霜满天      寸寸青丝愁华年
       对月形单望相护      只羡鸳鸯不羡仙


※ 来源:·BBS 水木清华站 http://smth.org·[FROM: 166.111.165.*]