Linux 版 (精华区)

发信人: josephpei (蕉下客), 信区: Linux
标  题: 【转】UNIX核心介绍
发信站: BBS 哈工大紫丁香站 (Mon May  1 17:46:15 2006)

发信人: syc@cc.ntu.edu.tw (Shiau Yong-Ching), 信区: Linux
标  题: Unix核心 介绍
发信站: National Taiwan University (Wed Jul  9 23:23:08 1997)
转信站: cis_nctu!news.cis.nctu!news.cs.nthu!news.mcu!netnews.ntu!not-for-mail

来  源: syc@ccsun20.cc.ntu.edu.tw

在出国前, 送给陪伴我大学四年的TAnet & UNIX...


                               UNIX Internals

                              The New Fronters

                                    导读

                                          "UNIX系统的安装数已经成长到10个,
                                                   预料此数字会持续增加中"
                                           -- Ken Thompson和Dennis Ritchie
                                                于UNIX程式设计师手册第二版
                                                             1972年6月12日

讨论UNIX的书籍很多,但是绝大部分都只是讨论如何使用,讨论UNIX程式设计的书不
多,而介绍UNIX系统核心的书则是更少了..以下是几本有名的书:

   * Bach的The Design of the UNIX Operating System, 1986 --讨论System V
     Release 2
   * Leffler等人, The Design and Implementation of the 4.3BSD UNIX
     Operating System, 1988 -- 讨论4.3BSD UNIX
   * Goodheart和Cox, The Magic Garden Explained, 1994 -- 讨论System V
     Release 4.0

然而,这些书都只是针对单独的/特定的UNIX系统所写的,很少给读者一个整体的
观点. 而Uresh Vahalia的UNIX Internals -- The New Frontiers这本书
则是从一个宏观的角度来看Unix系统.在本书中,作者讨论了商业界,学术界
的各种UNIX系统,详细的介绍了各系统的演算法,并对各系统的优缺点作了
详细而且客观的比较,实在是系统管理员,程式设计师,电脑玩家认识各家
UNIX核心最好的读物.

本书是以介绍UNIX System V Release 4.2为主,并旁徵博引其他各家的UNIX,
以讨论其中利弊得失.出版日期是1996,是介绍UNIX核心的最新参考资料.

我的读后感是没有基础会读起来很辛苦.有UNIX的使用,管理以及程式设计的经验
是必须的,建议Bach的The Design of the UNIX Operating
System也先读过,那么读这本
书就驾轻就熟了.

本文依序介绍本书中精采的部分,也就是大部分UNIX爱好者想要了解的部分,以飨宴
那些无法读原文书,或者没有时间专研Unix核心者.对于读者的程度没有特定的假设.
介绍的深度也是随兴的,请各位多多包涵.


Chapter 1 Introduction

失落的UNIX

     本书对各家的UNIX皆有涉猎,唯独IBM的AIX则是几乎支字未提.如果你
     是AIX的支持者,那么本书可能会让你失望,因为AIX好像对UNIX核心的
     发展不具影响力.同样的, HP-UX也是一样. 唯一你会知道的,大概是
     这两个UNIX皆属于System V家族的著名UNIX.

     本书写作应在1995年左右,然而1995,1996是UNIX变动最大的一年,有许
     多的UNIX厂商更新了他们陈旧的UNIX系统,几乎都是向SVR4看齐,所以
     没有提到他们, 应该影响不大吧, 或许他们没有什么特殊的技术,也就是
     比较平庸:p, 也可能是因为他们比较不开放,跟学术界不太打交道的缘故吧...

     本章最重要的内容是UNIX的历史,不过由于1995/96变化太大了,有些东西
     来不及走进历史 :)

     本书常常提到的UNIX系统有正宗的UNIX System V Release 4.x,
     UNIX最大的非主流派BSD UNIX 4.x (基本上是4.3, 4.4)以及UNIX的传人,
     Carnegie-Mellon大学的Mach (ch发k的音,念Mac).再来就是占有率最高的
     UNIX--Sun的SunOS以及Solaris. Digital Equipment Corporation(简称
     Digital,或DEC) 的OSF/1,现在改名叫Digital UNIX,则是因为
     使用了Mach核心而沾了不少光,曝光率大增.

     综观全书, Sun 可以说是最有研发实力的UNIX厂商,实在不可轻忽.

历史课

1960年代末期,Bell Telephone Laboratories, General Electric 和
Massachusetts Institude of Technlogy合作研发一个多使用者的作
业系统, Multics.此计划于1969年三月取消. 取消后的故事大家有点
熟,又有点不熟,这里把key part点出来:

   * Ken Thompson在DEC PDP-7上写了个叫Space Travel的电玩.
   * PDP-7欠缺程式发展环境,so, Ken Thompson + Dennis Ritchie写了UNIX出来.
   * Ken Thompson写了B语言(由BCPL演化而来的直译语言)
   * Dennis Ritchie把B改成了著名的C语言.
   * 1973年11月Unix version 4,使用C语言改写而成.

Unix的第一篇Paper "The UNIX Time Sharing System"由Ken Thompson和Dennis
Ritchie
提出,在1973年十月the ACM Symposium on OS (SOSP)中提出来.而在次年七月的
the Communications of the ACM发表.这是UNIX与外界的第一次接触.

UNIX免费流传的原因

1956年AT&T受到反托拉斯法调查.调查期间AT&T与联邦政府签订了一个协议,
不能经营与电话电报无关之业务.BTL隶属于AT&T.

UNIX在SOSP发表后,学术界对UNIX及其原始码索求不断,所以AT&T便免费的
提供原始码给学术界,此举造成了UNIX的广泛流传.

Berkeley的Computer Science Research Group, CSRG对UNIX的发展做了很多的贡献.
Berkeley的UNIX称为BSD UNIX. BSD对UNIX的贡献有virtual memory, TCP/IP, Fast
File System(FFS), reliable signals, socket介面.

4.4BSD把原来的VM换成Mach的VM,并引进了Logged File System. (LFS).
CSRG做完BSD4.4之后就关门大吉了.原因有:

   * 补助的不足
   * BSD的特色已经可以在商业系统上见到了(所以不用DIY了)
   * 系统已经大到不是一个小组可以维护的程度了

有一家公司Berkeley Software Design, Inc.(BSDI)成立来继续行销4.4BSD,
从事商业行为.他们的BSD叫做BSD/386. BSDI宣称BSD/386经过了Berkeley
的改写,已经没有AT&T的原始码了.不过AT&T还是对Berkeley和BSDI提出告诉.
导火线是BSDI的电话: 1-800-ITS-UNIX.此一诉讼延后了4.4BSD的发表.
终于1994年二月四日,双方达成和解,撤销告诉. BSDI发表了不含AT&T宣称
的原始码的4.4BSD原始码,称为4.4BSD-Lite. 接下来的故事就是在网路上
的传奇,你可以在386BSD的讨论区看到.


UNIX System #

反拖拉司法调查结束后将AT&T拆成数个子公司, BTL改名为AT&T Bell Laboratories.
并且AT&T被允许进入电脑市场. AT&T发表的商业版UNIX计有System III,
System V, System V Release 2 (SVR2) System V Release 3, System V Release
4/4.2

System V引进了许多新的特色(相对于旧的UNIX),如regions架构的虚拟记忆体(和
BSD的不太相同), IPC, remote file sharing, shared libraries,
STREAMS架构等等.

UNIX的商业化

商业化的UNIX也为UNIX争添不少特色,如SunOS的Network File System (NFS),
vnode/vfs interface支援多重档案系统,一个新的VM架构(为SVR4所采用)
AIX是第一个支援journaling file system的商业UNIX. ULTRIX (DEC的旧UNIX)
是支援multiprocessor UNIX的先趋之一.

Mach

Mach是Carnegie-Mellon大学(CMU)的microkernel(微核心)作业系统.(1980年代)

随著功能越来越多,UNIX也日渐庞大复杂而难以掌握, microkernel的概念就是
把Kernel去芜存菁,仅留下重要的部分,其余的功能都用user阶层的程式(称作
server)来达成就好了,藉此减低kernel的复杂度.

Mach设计目标有

   * 与UNIX相容
   * 在单处理器,多处理器上都能执行
   * 适合分散式运算环境

最普遍的版本是Mach2.5,是许多商业UNIX如DEC OSF/1, NextStep的基础.
Mach3.0才是真正纯粹的完全Microkernel化版本.

标准何在

UNIX的标准就像他的版本一样多.本小节仔细的介绍了各个标准与其命运.
讨论到最新的资讯为Novell将UNIX商标卖给了X/Open,以及Sun Solaris 2.5版.

1986年IEEE指定了一个委员会制定了一个一个开放作业系统的标准,称为
POSIX (Portable Operating Systems Interface,最后加上个X,为了好听,也是因为
本质上是UNIX的标准).<-这是我听说的,不是书上写的.

X/Open是一个由国际性电脑厂商组成的机构,成立于1984.其目的比较务实,
不是为众多的UNIX标准再添加一个.而是把重心放在汇集现有的标准,
整理出一个共通的环境.XPG (X/Open Portability Guide)就是他的大作.
目前UNIX这个商标应该是由X/Open所拥有.

除了标准以外,UNIX厂商也有合纵联盟.

UI, Unix International,是AT&T和Sun为主的联盟.主要的产物有SVR4和OpenLook.
OSF, Open Software Foundation为以IBM,DEC,HP为首的公司投资的子公司.
OSF对UNIX的贡献有Motif标准,DCE (Distributed Computing Environment).

在NT出来搅局后,UI瓦解了,AT&T不要UNIX了(专心于他的plan9作业系统?),
SVR4的传人变成了Sun的Solaris,不过Sun也不再坚持OpenLook,同时支援CDE
(Common Desktop Environment,讲白话一点就是Motif).

Chapter 2 The Process and the Kernel

介绍Prcoess的各种资料结构与执行态,没什么特别的.等于是Unix Progarmming
的小复习.

比较特别的是vfork的描述.有些书会让我们有在现代的UNIX下, vfork = fork with
copy on write的错觉.实际上vfork后, child是和parent共用一块定址空间(比较像
multi-threading), child可以修改parent的资料.
可能目前unix的语意和原始的vfork
不一样了吧..

Chapter 3 Threads and Lightweight Processes

这里提到Modern UNIX的特性之一: threads. 在Win95/NT, OS2的吹捧之下
大家应该有点耳濡目染了吧.这边定义了Threads和Lightweight processes.
有些系统, threads = LWP,不过为了讨论的需要,本书threads != LWP.

thread是一个最小的执行单元, 代表一个process在系统里面的活动状态.传统的
process就是仅有一个thread的程式.一个程式有5个thread就是说同一个程式里面
有五个工作同时在进行,也就是五个小程式独立互不干扰的一起跑的意思.(这
句话有语病,姑且当作对的好了) 比较低阶一点的看法是一个process有5个
instruction flow和五个stack.如果还是很模糊,看看Mach的定义九比较清楚了.

Thread有三种:kernel threads, lightweight processes, user threads.

kernel threads就是kernel有好几个分身,一个分身可以处理一件事的意思.
这用来处理非同步事件很有用, kernel可以对每个非同步事件生个分身来处理.
kernel threads的操作非常轻便,几乎没有负担,而且对Kernel的结构有帮助.
支援kernel threads的kernel称作multithreaded kernel.

Lightweight Process是有Kernel支援的user thread.也就是说,每个LWP,kernel
皆使用一个thread来处理/支援.于是LWP可以看成是kernel thread的延伸.操
作LWP的代价是很大的,因为他牵扯到Kernel的context switching.

user threads是在使用者空间,透过library模拟的thread,不需要或仅需要极少的
kernel支援,context switching比较快,因为不用更改page table等等东西,
使用起来较为轻便快速.user threads提供操控视窗系统的绝佳解决方案.

kernel基本上可以完全不知道user threads的存在, 而一个系统可以
提供数个不同的 library来提供不同policy. user threads才是一般应用程式
需要的multi-threading的形式, 因为此方式没有kernel参与, 所以最轻盈,
最有效率. 提到这里,你是否对广告上, OS2和Win95/NT争multithreading支援
感到迷惑呢?他们真的不晓得在争哪个mulitthreading的功能耶...

最有名的thread library有Mach's C threads,和POSIX pthreads.

SunOS4.x所称的LWP指的是user threas,而不是本书的LWP.

Solaris是由一组Kernel threads所构成,有一些用来执行LWP,有些负责一些系统的
任务.

kernel thread比较有创意的应用是取代interrupt
handler.有interrupt产生时,kernel可以产
生一个thread(分身)用来处理该interrupt.一口气解决掉re-entrant的问题

thread的scheduling有些意思,不过不方便以三言两语描述,也不甚有趣,就算了.

Mach的Threads

Mach kernel有两个基本观念: task和thread.
Task是静态的物件,由定址空间和系统资源(port rights)构成.
task提供了一个thread的执行环境.
thread是Mach的基本执行单元.
Mach提供了cthread函式库用来操作threads.

Mach 3.0 Continuation

Mach3.0对threads的改进颇有意思,名为continuation,其出发点是为了
节省stack的使用,在一个multi-threaded kernel下, thread越多(滥用:)
则stack space也消耗越多,亟待解决.

以下的程式片断很常见,也是一般kernel thread会block的原因(也就是
需要stack的时候.
  syscall(args) {
    ... /* 比如说,安排DMA传输一块disk block....*/
    thread_block();     /* wait until completed */
    process(args1);
    return;
  }
如果 syscall block住的话,就要保留一个stack下来.要是可以让process()不需要
用到stack里面的资料的话,那就不用保留stack.当然事先要把tail所需的
参数存在static variable里.
所以原程式就变成这样:
  syscall() {
   ...
   thread_block(process);
   /* not reached */
 }
  process() { /* 最终处理*/
   ...
   thread_syscall_return(status);
  }

省下来的stack则要是下一个被wake up的thread刚好也是个continuation,
可以直接给他用,省下一点cache/TLB misses.


Digital UNIX

讨论了OSF/1如何在Mach上利用tasks&threads实做出合UNIX语意的Process出来.


Chapter 4 Signals and Session Management

本节对UNIX的signal和session( &controlling terminals...) 作了详细的描述,
不只是详细而已,而且把各版本的一同都写清楚了,一般的书没有这么清楚的.

Mach对signal的策略也是焦点之一,更可以看出mach不全是Unix.
在Unix下我们安装一个signal handler来处理signal.而Mach则是使用
IPC来处理signal (正式的名字叫exception). Mach的每个thread都有对应的
exception port.如果要处理exception,就是再用另外一个thread去listen这个
exception port.这是per-thread exception port.另外还有一个per-task
exception port. 如果thread的exception port没人听,就会转到task 
exception port,在没有人听当然就让他死啦! task exception port给
谁用的呢? debugger是也!

Unix的debugger有个缺点,就是没办法debug fork出去的child.而透过IPC,
mach debugger就没有这个问题,只要mach debugger可以listen他的exception
port就行了. 使用IPC也让remote debugging变成一件容易的事.(mach有个
proxy server,可以把local port的message route到remote去,seeminglessly!)

Unix的debugger从前只能debug自己fork出去的child,如果是一个已经执行的
程式就没法度了. Mach则是如前面所说的,只要能够listen人家的exception
port即可. UNIX这方面也改进了,使用/proc file system也可以达到相同的作用.

你学过UNIX一定了解什么是process group,可是你不一定清楚session是什么.
session的概念是在SVR4和4.4BSD内成型的,因为以往只用process group的概念
没办法分清楚一个login session和一个session的某个job的不同. session的观念
算是蛮新的..在SVR3和4.3BSD以前都和process group混在一起.


Chapter 5 Process Scheduling

process scheduling的核心是clock interrupt,算是多工系统的心脏吧!
Kernel以callout的形式来使用之.
    int id = timeout(void (*callout)(), caddr_t arg, long delta);
向注册一个callout function,于delta tick后启动.
许多kernel的机制都是这样子向timer注册达成的,包括scheduler.

一个系统的ap可分为三类:

   * interactive - io intensive, 如shell, editor, GUI
   * batch - cpu intensive,如software buil;ds, scientific compuutations.
   * real-time - time critical,如放映影片, ap的需求是固定的放映速率,
     如每秒20 frames. 一个系统如果只能提供一个不确定的速率,在
     15-40间变化,而平均值为30,那是难以接受的.

Unix对前两项(i.e., time-sharing)都很在行,本章也对各种Unix的
run queue的处理做了深入的讨论.当然比较值得注意的还是Unix
对real time的支援.

以前, Unix Kernel不能支援realtime的原因是non-preemptive的缘故,
有时候kernel会作某件事太久,让process饿死. SVR4解决的方法是
把耗时的演算法切成几节,中间放入几个preemption point.在这些点
kernel就可以preempt,使得支援real-time成为可能.

Solaris kernel则更进一步,把大部分的data-structure都用适当的方法
保护起来(synchronize,如mutex lock, samaphore),让kernel变成真正的
preemptive.可见Solaris真的还不错.

传统的Unix则是利用non-preemptive kernel的特性省去了这些lock.

mach的scheduling policy有一点有趣的地方,在一个thread msg_send()
后,一般可能会把他block住,把message enqueue起来, 到run queue内找
一个thread来跑. 但是如果已经有人在等这个message,
mach则是直接scheduling receiver出来跑, message也不enqueue了,直接
copy到user-level address space.这样子增加IPC的效能,
因为省却了搜寻run queue的时间, 以及IPC enqueue/dequeue的时间.

Mach特别的地方是processor set的概念.一个task可以要求kernel配给他
n颗(a set,一组) CPU来跑.

Digital UNIX源自于mach,但是却没有使用mach的scheduler.

本章末也介绍了一些被提出来的演算法,比较有趣的是three-level scheduler.
要同时满足任意的time-sharing和real-time的需求是不太可能, 因为资
源有限.three-level scheduler引进了节制的观念, real-time process要先注册,
kernel能够reserve足够的resource才允许执行.而kernel也会reserve适当的资源,
确保time-sharing processes不会动弹不得.

在网路负荷过重的时候,kernel只要处理network activity就来不及了,
会导致receive livelock情形发生. 3-level scheduler可以把network
的处理当成real-time task,给予适当的配额就好了.不够用就drop掉嘛.
这样子保证大家有饭吃,不会活当机! [ real-time task有固定的priority,
和固定的resource配额 -- kernel保证他会有这些东西,就像有人保证每天
都会给你一颗面包一样,不会说放一堆面包给大家抢(time-sharing),一天
有时候可以抢好几颗,有时一颗也抢不到,要是有一个人很会抢,那其他的
人就要饿死了!]


Chapter 6 Interprocess Communications

本章对IPC programming做了一些复习.
传统的Unix IPC机制只有pipe. System V引进了SYSV IPC,包含semaphore,
shared memory和message queue. System V的STREAMS架构也是Unix
重要的IPC机制之一. 本书没有提到BSD socket介面,假设这个也是
IPC的话. Mach是一message passing为中心的kernel(message-passing
kernel),大部分的系统服务都是靠交换讯息达成的,所以本章也花了
不少篇幅介绍之.

特别的有:
SVR4使用STREAMS来实作pipe,所以SVR4 pipe是bi-directional.一个
pipe两端都可读又可写.其他的UNIX则要用一对pipe才可达到相同目的.□

System V semaphore有一个缺点: allocation和initialization不是单一步骤,
可以导致race condition发生.

在System V STREAMS下, IPC的message queue几乎可以淘汰了. STREAMS
功能强大(see最后一章) ,可以取代掉所有message queue的功能.

本章最深奥的就是介绍Mach IPC了. 相信大家也最感兴趣.
message := 一些有型别的data.型别分为两类, simple data,即一般的
            资料. complex data,可能为out-of-line memory或是port rights.
            (后述)

port := a protected queue of messages. 简单的说就是message queue的id.
            跟file descriptor差不多,为一个整数,代表一个message queue.
            message必须送到port(通信埠),而不是送给某个task或thread.
port rights := 一个port的存取权限, send rights和receive rights.这种
            存取权是以task为控制对象,而不是thread. send rights允许
            一个task(的所有threads)对某个port传送讯息. receive rights
            类推. 一个port可以把send rights给好几个tasks,但是只能有
            一个task有receive rights -- 拥有该port的task. 有receive
            right的task,就自动有send right)
out-of-line memory := 传送大量的资料, message直接copy很没效率. 透过
            virtual memory系统改memory mapping,用copy-on-write的方式可
            以改进. in-line memory传送是message从sender copy到kernel,
            再由kernel copy-to receiver. out-of-line memory则是kernel
            改一些virtual memory mapping, 只有在sender/receiver
            modify该资料时产生copy-on-write的page fault, 只发生
            了一次copy.

complex data和simple data的不同是complex data需要kernel处理message的
内容,再翻译给receiver. simple data直接transfer就可以了.

每个task拥有task_self port的send-right. task_self port是kernel
拥有的. task透过task_self port与kernel沟通.task另外有一个task_notify
port的receive rights,用来接收(kernel)来的message. thread有thread_self
port,用来送message给kernel, reply用来接收kernel传回来的reply
(比如system call, rpc...). thread用的port,其 port rights为task所有.
另外还有exception port用来处理exception/signal/debug.前面讲过了.

一个message内的资料结构有一栏为reply_port. 如果sender需要reply就在
此栏填入自己拥有的port.(所以自己就有receive right). message passing之中,
kernel就会为receiver建立一个到reply_port的send right.

Port Name Space

port是一个整数,和file descriptor一样, 每个task拥有独自的命名空间.
ie.不同task的port id如果一样, say,编号100,并不是指到相同的port.

Port translations

由于port name space是task间互相独立的. kernel必须建立一个translation
来记住谁是谁. (Unix是用global file descriptor table达成的).

研读本章最令人感到不解的是port right. 因为port的kernel data structure里面
没有port right的纪录. 那到底mach把port right资料藏到哪里去呢?搞了老半天,
原来就是port translation. kernel的port translation就是port
right.大胆一点说,
就是mach kernel根本没有port right的观念.只要在port translation查的到的
port,就可以送message就对了.

port translations的每个entry,代表的都是一个connection.
一个entry包含下列资料: ,代表的意义是
一个task的id是local_name的port, 拥有对kport (一个指向kernel的port data
structure的指标)的port right. port right是receive还是send呢?由type决定.
local_name就是所谓的port right的名字.

msg_send()用 找到kport,再由
找到该port于task的local_name.

task删掉一个port, kernel要找到kport,再除掉<*,*, kport, *>,并且
通知相关的task.

task结束要清掉的所有kports.

Kernel用两个hash table来快速存取translation, TP_table (key=)
TL_table(key=)


Port Rights Transfer

普通的port right transfer embed到message header里面,就是前面提
的reply port.这样子的port right transfer是把自己的port的send 
right送给别人用的.比较复杂的就要用complex message. message里面,
告诉kernel要把他人的(send right)送给第三者. (本章没有提到详情).
这是mach name server的功能:除了之前提到的port之外, mach的每个
task还有一个bootstrap port,透过此port, task可以送message到mach
的name server. name server提供了存取其他server的机制.过程如下:

  1. server向name server注册(透过bootstrap port)
  2. client向name server询问如何与server沟通.
  3. name server transfer一个到server的send right给client
  4. client得到一个可以和server沟通的port,利用此port和server联系.

Mach的理想是把许多Unix kernel的机制变成user level server. name server
是开启这个机制的钥匙.

Port Interpolation

Port interpolation可以让别人偷走某task的send/receive rights.
Mach提供task_extract_send(), task_insert_send(), task_extract_receive(),
task_insert_receive()来干这档事. debugger就是这样拦截ipc message的.

netmsgserver

另外一个和Port interpolation很像的机制,就是Mach的remote IPC. 其实
说穿了, Mach remote IPC的达成只是靠netmsgserver作proxy而已.
Mach可以这样做的原因有二, 第一个是send_msg()只要知道自己的
local_port_name就行了,他不需要知道这个port怎样连,连到哪里去.这是
port name server和netmsgserver的工作, task尽管往name server告诉他的
port送就可以了.第二点是senders是匿名的. receiver无法从message得知
sender是谁.所以netmsgserver可以提供完全透明的服务.

Mach 3.0对IPC的问题做了一些改进,自己看吧. 这是Mach 2.5 IPC
会遇到的问题.


Chapter 7 Synchronization and Multiprocessors

提到Kernel synchronization的演算法和资料结构.特别是multiprocessor
下的问题. multiprocessor最大的问题在virtual memory的cache/tlb
synchronize 的问题.本章没有提到, 延至virtual memory再讨论.

Chapter 7讨论的内容颇为琐碎, 不适合摘要.


Chapter 8 File System Interface and Framework

本节前半段讨论(复习)跟filesystem有关的系统呼叫. 后半段讨论mordern
Unix的VFS (vnode)架构, 亦即, kernel处理file system的方法. 下一个chapter
主要讨论file system在disk上的layout.

s5fs是unix早期(System V r4以前)档案系统,特色是简单但功能尚可,最大
的缺点是有14个字的档名限制. 4.2BSD设计了Fast File System, FFS,
提供了较优的performance和功能. FFS受到广大的欢迎, 最后被SVR4
所采用. FFS又称为UFS (UNIX File System)

早期的Unix kernel不能同时支援两种以上的档案系统. 各家
都有解决之道. AT&T用file system switch, DEC用gnode/gfs, Sun
所提出的vnode/vfs最广为接受, 最后赢得胜利,成为SVR4的
一部份.

inode 是Unix特有的观念. Unix kernel利用inode来作为他对档案的介面.
一个inode代表一个档案, 记录了kernel存取该档案所需要用到的资料,
以及该档案的属性等等.名叫inode的原因是因为本资料结构的大部份
内容皆由on-disk的inode而来.Unix file system 在disk上的image不用档名
而用整数(i-number)来表示每一个档案. 目录只是一个较为特别的档案,
记录i-number和档名的对照而已.有了i-number,kernel才找得到inode,
也就是记录档案存放位置与属性的地方.一般称在disk上的inode为on-disk
inode,被kernel读进记忆体,使用中的inode为in-core inode.

vnode/vfs的概念是把原来in-core inode物件化成为 virtual class.
vnode提供一个抽象化的介面. kernel要对档案的所有操作接
透过vnode所定义的虚拟函式来达成. 一个vnode 初始化后,就
会有个指标指向file system dependant part.所以不管底下的档案
系统格式为何, kernel皆能呼叫到正确的函数. VFS的架构使得
Unix可以支援多重档案系统, kernel经由vnode提供档案系统的
发展者一个标准的介面. 七月号的InfoMac介绍狂想曲的
一篇文章说VFS可以有档案压缩,解压缩,线上防毒的功能, 
真的是颇为奇怪..

比较特别的是Unix的实作和定义有点不太一样.
定义说:

    struct vnode {

        public_data1,2,3,....

        caddr_t v_data;

    } vnode;

    vnode.v_data = (caddr_t *)&ffs_data;

而实作作成这样,把interface和file system dependant data放在一起:

    struct ffs_node {

        public_data1,2,3,... /*和struct vnode顺序一样*/

        caddr_t v_data;

        private_data1,2,3.... /* ffs private data */

    } vnode;

    vnode.v_data = (caddr_t *)&vnode;

Understand?不懂就去看书吧!书上是用图示法的,见图知意.

vnode/vfs有个地方和原本的unix不一样,会导致race condition.我想这是
许多security hole的泉源.就是file name lookup不一样.以前只有一个
filesystem的时候(看Bach的书) Unix是传一个路径给namei(),就可以找到
inode. vnode的方法要把一个路径切碎,一段一段找.这也使performance
降低不少. (unix filesystem瓶颈之一在file name lookup,每次lookup都会
碰到路径上每一个目录的inode....4.4BSD和OSF/1都有提出解决的对策.
(自己看书,太琐碎了)

有了vnode/vfs, 则可以鼓励出更多的创意, 更多的档案系统可以被提出来.
比较有趣的有NFS, specfs, fifofs, /proc fs.这里顺便提一下后三者.本书是在
稍后的章节才提到.

specfs在干什么的呢?以前s5fs的时代,有些特别的inode不表示实体的档案,
而是用来表示周边装置.现在假设我们的ffs上有个/dev/tty1的档案. 利用
刚刚提到的vnode/vfs的方式, kernel会去呼叫到ffs的函式,而这些函式并不能
知道怎样驱动tty driver.解决的方式是设计一个specfs.只要kernel发现
inode是个device file的话,就不去呼叫vnode的open,而是呼叫specvp(),把
该vnode传给他.specvp就会把适当的virtual function和指标填到vnode去,
而得到所希望的操作.这就是specfs存在的目的. Chapter 16有更详细的资料.
并讨论到不同device file major/minor device number都一样,也就是指到
相同device的问题解法.

fifofs和specfs一样.用来把ffs的某个vnode换成有fifo作用的named pipe.

/proc file system则是把process在记忆体中的状态,转换为file system的方式
方便存取.这样子debugger得以更方便的控制process,提供更多的功能,
也可以debugger执行到一半的process. (前面提到在旧的Unix下,这是不可行的)


Chapter 9 File System Implementations

本章主要讨论on disk  file system layout, 和一些其他的file system.
前面没有提到vnode在kernel如何组织,所以这章也补齐.

首先是s5fs.其实这还是自己看比较快,看图说故事就对了.

比较特别的是file system如何处理free block. s5fs用free block
list来管理free block.这个list会很占空间吗?不会的,因为此
list在free block上,也就是借用没有用的的空间.free block list
的大小和所剩的空间成正比.如果没有空间了,也不需要
free block list了; free block list原先占用的空间就
会释出来当作free block用.

其实前面没说清楚. free block list分成两部份.在super block
内有一小节,剩下的才放在free data block上. super block的
free list用完了就会从free data block上的list调借. 所以
free block list占用data block的空间会在data block用完前释出.


Berkeley Fast File System

s5fs有许多限制, performance是一个问题.比如说ls -l dir,就会在inode和dir
的档案间来回奔跑. (inode才有file attribute.) s5fs把inode table放在disk
空间的最前面, 其他的地方放data block.导致浪费掉许多seek time.

s5fs fragmentation的问题也没有处理得很好.用free block list的方法只能
在档案系统刚建立的时候拥有良好的连续配置,用久了fragmentation就严重了.

block size也有问题.  block size大会增加效率,但是浪费空间,反之减少效率,
但是空间利用率较高.

s5fs单一的super block也很危险, super block 毁了整个filesystem就完了.

s5fs还有一个缺点是14个字的档名限制.

FFS的出现就是解决这些问题的. How? s5fs把disk看成是一个磁带般处理,
没有考虑实体结构, FFS设计的时候就面对现实,把实体结构考虑进去,也就是
考虑了disk的head, track, cylinder等性质. hard disk由好几片platter
(硬碟片)组成.cylinder就是不同platter下相同track所组成的圆柱体.

FFS把一个disk划成好几个cylinder group. 一个cylinder group
由相邻的cylinder组成.简单的说,FFS就是把一个disk划成几个小
disk (cylinder group),每个cylinder group (disk)上面放个s5fs
就是了. 这样子作可以让某个cylinder group内的资料限制在几个
cylinder的范围内,减少seek time.

针对fragmentation的问题则是使用bitmap来解决. FFS使用超大
的data block以降低fragmentation带来的影响.

但是对于小的档案(和大档案的尾巴,不满一个block的部份),则是把data block
切成几个小块,存放好几个小档来节省浪费掉的空间.存放在fragmented
block的资料一定要是一个档案的最尾端,而且在此block内的资料必须
连续存放,不可以说A档的tail住在一block的第1/4, 3/4块, B档比较小,
住在同一 block的第2/4块.这种情形要把A档的block移到另一个新的block
上,让A的最后一个block连续存放.

为了避免因为一个档案慢慢的成长导致不必要的搬移, FFS限制只有direct
block可以用fragmentation.也就是档案超过一定大小就不用fragmentation block
了.

除了架构上的改变, allocation policy也很重要. FFS这样配置硬碟空间:

   * 同一个目录的档案(inode)都放在同一个cylinder group上. (localizing
     policy)
   * 每个新的目录都和其parent位于不同的cylinder group上. (distributing
     policy)
   * 档案的data block放在和其inode相同的cylinder group上(localizing policy)
   * 档案超过48kb,以及以后每增加1MB,就要换跑道,喔是cylinder
     group.免得某个档案灌爆一个cylinder.
   * 配置data block时考虑disk的interleave factor.(不懂?那你一定没有
     用过MS-DOS的floppy加速程式:) 没关系, 本书有图解)

s5fs的super block被分成两部份. FFS4每个cylinder group都有记录
自己的空间使用状况. 而整个disk的super block只记录整体性的资料,
如cylinder的大小位置, block的大小位置等等资料.每个cylinder group
都有一个super block的备份. FFS把这些备份分散开来, 使得没有单一的
磁头,磁轨,磁柱或碟片存放这些备份. (没有把所有的鸡蛋放在同一篮子
上的意思.)

即使目前的SCSI硬碟并不区分head, cylinder, sector,制造商提供的资料只是
让他乘起来和硬碟的大小相同而已, 但是实验显示FFS的方式还是可以得到
良好的效能.

FFS还有很多chache的改进可以提高他的效能,不过要自己看书:)

Temporary File System

temporary file system对于需要暂时使用档案的场合可以增进效率.
以前的方式是把一块ram划下来作ram disk.这样子浪费记忆体. BSD用memory file
system (mfs)的方式, 让一个io server用他的address space当作空间来提供
temporary file system的暂存空间,不过最大的缺点是context switch使
performance不好. Sun的方式最好, tmpfs整合了vnode/vfs介面和VM介面,
让整个virtual memory来提供tmpfs的空间. 整个存取的方法和一般的filesystem
没有两样,是最理想的方法. 另外一个方法是设定file system write back的时间,
以企图延后所有档案系统的资料写入disk来达到temp file system的目的. (期望
他没被写入前就杀掉了).

Unix用到暂时档的地方很多(如cc).所以temporary file system的发展
是很有价值的.

Chapter 9结束的时候提到了Buffer Cache.这个东西在Bach的书里是重点,但是
目前的Unix已经不用Buffer Cache,改采整合file system和virtual memory的方式,
更为有效的运用记忆体.


Chapter 10 Distributed File Systems

本章介绍..NFS/RFS/AFS/DFS.
NFS其实算蛮简单的,他只是把kernel往disk写回的动作(& reading),换成
network packet送出去而已.对kernel的介面则是藏在vnode/vfs下.

NFS performance bottleneck在于NFS要求每次的write()不能够cache,一定要
马上写回,而档案属性必须一个一个档询问,使得ls -l产生大量的traffic.
当然现在已有方法改进.

NFS version 3于1995年公布,更正了NFS v2的大部份的问题. (security
的问题是在RPC上面. RPC本来就有提供security的机制,只是少有实作而
已...) 由于NFS v3出现蛮晚的,有支援的Unix可能算很赶的上流行了:)

本章提到两个dedicated NFS server. 我比较有兴趣的是Auspex NS5000.
另外一个是IBM的, focus在容错. Auspex NS5000有好几个CPU, 每个CPU
都作单一个事,分成两组,一组处理网路上的需求,另一组处理硬碟档案系
统的IO.另外有一个CPU跑修改过的SunOS,admin用,其他的CPU都跑一个叫
做functional multiprocessing kenel (FMK)的系统,彼此间用message 
passing交谈. FMK的好处是他只提供作NFS server所必要的function, 
而不提供Unix的语意/环境,使得系统省下不少负担.

RFS没什么好提的...

AFS, Andrew File System是CMU发展的系统, 后来成立Transarc
Corporation.继续发展. 后来AFS演变成OSF DCE的Distributed File
System.本书AFS/DFS都有详细的介绍.他们太复杂了,看书比较清楚.
结论是AFS比较不好, DFS作了很多改善, 功能也比较多. DFS比较特
别的是对分散式档案系统cache的改进. DFS server会给他的client
一个(read/write/status/lock..)token, 允许他(read/write/status
/lock..)等等的动作而不需要与server synchronize,也不用
update cache.也就是说该client拥有该资料的使用权(token,权杖之意).
client拥有token直到kernel撤回这样权力为止.kernel随时可撤回
这些token,表示有人要更改data,需要synchronize了.

token的想法非常的高明,因为传统的方法所有的时间都要synchronize.但是
token的想法则是考虑到大部份的时间内皆不会产生race condition,所以
不需要每个动作都synchronize.

不过文中也指出, DFS非常的复杂, 不好实作就是了.


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//时,
就产生对的连线,让没有网路知觉的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真的不是一盏省油的灯,

--
|┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷|
|┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯|
|┯┷┯┷┯┷┯┷┯别拦俺，俺要去撞墙清醒一下！┷┯┷┯┷┯┷┯┷|
|┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯|
|┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷┯┷|


※ 来源:·哈工大紫丁香 http://bbs.hit.edu.cn·[FROM: 202.118.235.145]