發信人: syc@cc.ntu.edu.tw (Shiau Yong-Ching), 看板: Linux
標 題: Unix核心 介紹
發信站: National Taiwan University (Wed Jul 9 23:23:08 1997)
在出國前, 送給陪伴我大學四年的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真的不是一盞省油的燈, 確
實有兩三把刷子呢?
本書有個缺點就是校正不太完整. 內文reference到Section 0好幾次, 但是
並沒有Section 0. 應該是美中不足的地方吧!
本書沒有提到tcp/ip網路的部份, 應參考Stevens, TCP/IP Illustrated
Volumne 1,2,3.
本書對shared library以及執行檔的結構沒有作深入的討論, 也是一個
遺憾...
--
Shiau Yong-Ching
--
==================================Te-wei Yen=================================
http://lls.twbbs.org/
mail://kevinwatt@cc.nsysu.edu.tw/
=============================================================================
--
* Origin: 中山大學-美麗之島BBS * From: 61.70.122.184 [已通過認證]
|
