操作系統內核具體實現中比較巧妙的思想有哪些？

01-14

如題，注意是具體實現，而不是操作系統原理中的好思想！
最好是一些比較精專的思想，而不是Hash、KMP等通用的思想，比如：
設計：fork；將全部物理地址空間重新映射作為每個進程的虛擬地址空間的一部分(有點偏原理了)；
演算法：Linux中的CFS調度演算法；各種RCU同步機制；
數據結構：物理塊分配中，不需要額外存儲空間的空閑鏈表(有點偏通用了)；

P.S. 回答時，最好能指明操作系統及其版本，以及該思想好的原因。

摘自ds.algorithms

Basic Data Structures and Algorithms in the Linux kernel

Links are to the source code on github.

Linked list, doubly linked list, lock-free linked list.
B+ Trees with comments telling you what you can"t find in the textbooks.

A relatively simple B+Tree implementation. I have written it as a learning exercise to understand how B+Trees work. Turned out to be useful as well.
...
A tricks was used that is not commonly found in textbooks. The lowest values are to the right, not to the left. All used slots within a node are on the left, all unused slots contain NUL values. Most operations simply loop once over all slots and terminate on the first NUL.
Priority sorted lists used for mutexes, drivers, etc.
Red-Black trees are used for scheduling, virtual memory management, to track file descriptors and directory entries,etc.
Interval trees
Radix trees, are used for memory management, NFS related lookups and networking related functionality.

A common use of the radix tree is to store pointers to struct pages;
Priority heap, which is literally, a textbook implementation, used in the control group system.

Simple insertion-only static-sized priority heap containing pointers, based on CLR, chapter 7
Hash functions, with a reference to Knuth and to a paper.

Knuth recommends primes in approximately golden ratio to the maximum integer representable by a machine word for multiplicative hashing. Chuck Lever verified the effectiveness of this technique:
http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
These primes are chosen to be bit-sparse, that is operations on them can use shifts and additions instead of multiplications for machines where multiplications are slow.
Some parts of the code, such as this driver, implement their own hash function.

hash function using a Rotating Hash algorithm
Knuth, D. The Art of Computer Programming, Volume 3: Sorting and Searching, Chapter 6.4. Addison Wesley, 1973
Hash tables used to implement inodes, file system integrity checks etc.
Bit arrays, which are used for dealing with flags, interrupts, etc. and are featured in Knuth Vol. 4.
Semaphores and spin locks
Binary search is used for interrupt handling, register cache lookup, etc.
Binary search with B-trees
Depth first search and variant used in directory configuration.

Performs a modified depth-first walk of the namespace tree, starting (and ending) at the node specified by start_handle. The callback function is called whenever a node that matches the type parameter is found. If the callback function returns a non-zero value, the search is terminated immediately and this value is returned to the caller.
Breadth first search is used to check correctness of locking at runtime.
Merge sort on linked lists is used for garbage collection, file system management, etc.
Bubble sort is amazingly implemented too, in a driver library.
Knuth-Morris-Pratt string matching,

Implements a linear-time string-matching algorithm due to Knuth, Morris, and Pratt [1]. Their algorithm avoids the explicit computation of the transition function DELTA altogether. Its matching time is O(n), for n being length(text), using just an auxiliary function PI[1..m], for m being length(pattern), precomputed from the pattern in time O(m). The array PI allows the transition function DELTA to be computed efficiently "on the fly" as needed. Roughly speaking, for any state "q" = 0,1,...,m and any character "a" in SIGMA, the value PI["q"] contains the information that is independent of "a" and is needed to compute DELTA("q", "a") 2. Since the array PI has only m entries, whereas DELTA has O(m|SIGMA|) entries, we save a factor of |SIGMA| in the preprocessing time by computing PI rather than DELTA.
[1] Cormen, Leiserson, Rivest, Stein Introdcution to Algorithms, 2nd Edition, MIT Press
[2] See finite automation theory
Boyer-Moore pattern matching with references and recommendations for when to prefer the alternative.

Implements Boyer-Moore string matching algorithm:
[1] A Fast String Searching Algorithm, R.S. Boyer and Moore. Communications of the Association for Computing Machinery, 20(10), 1977, pp. 762-772.http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf
[2] Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004 http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf
Note: Since Boyer-Moore (BM) performs searches for matchings from right to left, it"s still possible that a matching could be spread over multiple blocks, in that case this algorithm won"t find any coincidence.
If you"re willing to ensure that such thing won"t ever happen, use the Knuth-Pratt-Morris (KMP) implementation instead. In conclusion, choose the proper string search algorithm depending on your setting.
Say you"re using the textsearch infrastructure for filtering, NIDS or

any similar security focused purpose, then go KMP. Otherwise, if you really care about performance, say you"re classifying packets to apply Quality of Service (QoS) policies, and you don"t mind about possible matchings spread over multiple fragments, then go BM.

Linux內核的愛好者，就讓我以Linux內核來回答這個問題吧：

1. 我大VFS！通過VFS的抽象層，一切都變成了文件。於是Linux的系統調用精簡了好多，於是很多虛擬文件系統(proc, sysfs, cgroup, tmpfs)得以實現，於是linux可以相對容易的支持多種文件系統。

2. current宏的實現。將內核棧建立在當前的進程描述符的上面，通過棧地址偏移即可快速獲得當前進程的信息。

3. clone系統調用。模糊了進程，線程的界線，在linux內核中沒有明確的線程、進程的概念，都是task_struct表示的運行實例，且依據clone的參數，實例間靈活的可以共享多種信息。而共享程度的兩種特殊情況，就是進程和線程。

4. cgroup, namespace。內核居然要虛擬化進程的運行環境！也成就了Docker。

5. 紅黑樹的數組做hash結構。用紅黑樹而非鏈表來組織哈希衝突的元素(源碼中部分哈希是這樣的)。

6. CFS調度器。通過紅黑樹、vruntime等將之前多鏈表表示不同優先順序的調度演算法簡化，妙！

7. ……（內核的學習是一個充滿了驚喜的旅程，路途遙遠，允許我以沒有結尾的結尾來做個結尾吧！）

Linux內存管理裡面有一個機制叫冷熱緩存（也叫冷熱頁），這個想法非常好。

冷熱緩存，是指一個空閑page的list，裡面存著熱頁（剛用完的頁）和冷頁（很久不用的頁）。有時候內核代碼需要向內核要一個page，如果從buddy system中直接拿，那麼很有可能這一個page原先不在高速緩存中(L1/L2/L3)，那麼要用這個page的話需要把它拿到緩存中來，性能和時間都不高。如果這個頁原來就在高速緩存中，那不是省了這些步驟了？冷熱緩存這個機制存在的意義就是讓你申請的那頁剛好就在緩存里，可以直接用。

那麼怎麼實現呢？每次要free一個page的時候，把這個頁放到冷熱緩存的list里。這裡又引出了另一個非常精妙的思想：冷熱緩存list是單獨的一個list，同時存放熱頁和冷頁。不是冷頁list和熱頁list。為什麼會這樣？因為你還一個page的時候，還到list的頭部，隨著page的插入，這個list越靠前越熱，越靠後越冷，下一次你要一個page的時候，系統就把頭頁當成是最熱的頁，尾頁當成是最冷的頁。

FreeBSD 內核中用到的比較巧妙的思想至少有這些：

ULE Scheduler:

ULE: A Modern Scheduler For FreeBSD

Keeping ULE O(1) required implementing a CPU usage estimator that
operated on an event driven basis. Since a thread may go to sleep for a
long time it will have no regular event to keep its CPU usage up to
date. To account for this, a hook was added to the scheduler API that is
used whenever the CPU usage is read. This hook adjusts the current
tick window and tick counts to keep the statistics sane.
ULE supports two mechanisms for CPU load-balancing. The first is a pull method, where an idle CPU steals a thread from a non-idle CPU. The second is a push method where a periodic task evaluates the current load situation and evens it out. These two mechanisms work in tandem to keep the CPUs evenly balanced with a variety of workloads.

Slab Allocator (VM):

The Slab Allocator: An Object-Caching Kernel Memory Allocator

uma(9)

Object caching is a technique for dealing with objects that are frequently
allocated and freed. The idea is to preserve the invariant portion of an
object"s initial state - its constructed state - between uses, so it does not
have to be destroyed and recreated every time the object is used.

Page Coloring (VM):

Page Coloring

Cache coloring

Space Map (ZFS):

Space Maps (Jeff Bonwick"s Blog)

One way to mitigate the pathology of random frees is to defer the
update of the bitmaps or B-trees, and instead keep a list of recently
freed blocks.
But what if we went further?
Recall that log-structured filesystems long ago posed this question:
what if, instead of periodically folding a transaction log back into the
filesystem, we made the transaction log be the filesystem?
Well,
the same question could be asked of our deferred free list: what if,
instead of folding it into a bitmap or B-tree, we made the deferred free
list be the free space representation?

That is precisely what ZFS does.

Deduplication (ZFS):

ZFS Deduplication (Jeff Bonwick"s Blog)

Chunks of data are remembered in a table of some sort that maps the
data"s checksum to its storage location and reference count. When you
store another copy of existing data, instead of allocating new space
on disk, the dedup code just increments the reference count on the
existing data.

Soft Update (UFS):

https://www.ece.cmu.edu/~ganger/papers/CSE-TR-254-95.pdf

Dynamic Directory Hashing (UFS2):

http://www.maths.tcd.ie/report_series/tcdmath/tcdm0206.pdf

Stackable Filesystem

The early vnode interface was simply an object-oriented interface to an underlying filesystem. As the demand grew for new filesystem features, it become desirable to find ways of providing them without having to modify the existing and stable filesystem code. One approach was to provide a mechanism for stacking several filesystems on topn of one another other.

http://www.lockss.org/locksswp/wp-content/uploads/2015/02/EvolvingVnodeInterface.pdf

如果站在的更宏觀的角度看，應用最廣的思想可能還是這幾個：

Lazy Evaluation (delayed write/allocate/release)

Reference Count (inode, vnode, vm_object)

Object Oriented (VFS, Pager Interface, Slab Allactor, Scheduling )

推薦讀物：

The Design and Implementation of the FreeBSD Operating System (2nd Edition)

廣告：歡迎大家加入 FreeBSD 陣營：）

學習linux0.11源代碼的時候，印象很深刻的一個地方是內核函數sleep_on(struct task_struct **p)的實現。

這個函數由當前進程在內核中調用，作用是將當前進程添加到某個休眠隊列中，然後讓當前進程陷入休眠。確切的說是將當前進程的任務結構體指針（struct task_struct*）添加到某個任務結構體指針隊列中，參數*p總是指向最後一個添加到隊列的元素。

令人拍案叫絕的就是這裡根本不存在一個顯式的休眠隊列，他這裡所謂的「休眠隊列」其實是通過不同進程的sleep_on內核函數棧隱式地建立起來的！

內核棧隱式隊列示意圖[1]

上圖中的綠色圓角矩形就是各個進程的sleep_on內核棧，tmp指針是函數內部的局部變數，紅色矩形是各個進程的任務結構體。由於進程在sleep_on函數內部陷入休眠，所以進程休眠過程中函數棧一直保留。

sleep_on函數內部邏輯可以簡單描述為：

void sleep_on(struct task_struct **phead) { struct task_struct *last; last = *phead; *phead = current;//當前進程任務結構體指針 sleep(); *phead = last; if (last) wakeup(last);//鏈式喚醒 }

參考文獻：

[1] 趙炯. Linux內核完全注釋內核版本0.11 修正版V3.0. http://oldlinux.org/download/clk011c-3.0-toc.pdf

紅黑樹

需要伺候頁面管理, CFS, 高精度定時器, 容易么人家?

我最喜歡CFS的演算法, 那個虛擬時鐘非常有意思。

大多數都是linux/windows下的，來個rtos的. 比如ucos

實時操作系統就和消費級用的系統對時間的敏感度不一樣了，手機卡個十幾ms，人類也感覺不出來啥，但是工控/航天等領域那都是按us來算的，上學的時候做電流控制就在那天天糾結1us波形的事兒呢；介紹一個ucos中的基石數據結構（演算法），簡單實用.

補充下思想好的原因，以前就是覺著很奇妙，沒細想.

-&>如果查找表這個數據結構或演算法是比較通用的話，那麼本身就很普通了，不過想想，如果我設計，冥思苦想發現可以查找表，那麼毫無疑問，我會設計成64位的二進位數，那就要存儲計算這麼多個數，又傻又蠢.

-&>精妙之處在於，結合了任務優先順序演算法的需求：即找到最小置1的位。而分離出來優先順序判定表而大大減少了查找表的個數.

任務控制快的管理存儲與演算法

預備：除了空閑任務和統計任務之外，操作系統還運行著各種用戶創建任務，這些任務優先順序不一樣，狀態不同，ucos默認可以有64個任務，可剝奪型內核，也就是系統中時刻運行著最高優先順序的任務，調度任務的核心就是基於任務的優先順序演算法（不會像非剝奪型內核一樣任務會一直阻塞在能力直至完成），那麼就要求根據中斷時間（根據不同的硬體封裝的）周期到了就要查找當前系統中就緒任務優先順序最高的運行，ucos的每個任務維護著一個任務控制快，其中包括任務堆棧信息和優先順序等，思路也很好想，遍歷任務控制塊好了，找到優先順序最低的那個運行不就行了，windows可以接受，對於RTOS就不行啦，運氣好第一個就找到了，運氣不好那最後一個，時間豈不是很長？ucos給出的解決方法是--查找表.

數據結構：

1. 首先把任務地址放在優先順序指針表裡面，那麼如果知道最高優先順序的話，對應的任務也可以隨機存儲了

OS_TCB *OSTCBPrioTbl[OS_LOWEST_PRIO + 1]

2. 接下來主要就是找優先順序最高的任務了，如果最大任務總數是64個，也就是有64個優先順序，實際上可以用64為來標示，每一個優先順序是否有任務是就緒態，1就是就緒，0是沒有任務或者有任務沒有就緒，遍歷的做法是直接找最小位就可以了（數字越小優先順序越高），查表髮結構如下：

INT8U OSRdyGrp INT8U OSRdyTbl[8]

這樣，64個優先順序分成了8組，每個組有8位，只要是該優先順序處於就緒態的那就是1了. 只要這一組有一個位數是1，那麼OSRdyGrp對應位數就是1，否則是零，實際上要找的最高優先順序就是從低位開始遇到到的第一個1，每一個OSRdyGrp OSRdyTbl[]都代表了當前任務的狀態.,

既然是查找表，思路就是不把不同狀態值固話到內存（表）中以供查找。優先順序判定表：

INT8U const OSUnMapTbl[256] = { 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 };

公式如下：

y = OSUnMapTbl[OSRdyGrp] --1 OSPrioHighRdy = (y &<&< 3) + OSUnMapTbl[OSRdyTbl[y]] --2

先來理解1, 2也就理解了，對於就緒組來說，無論8位二進位數（256），無論怎麼組合都在256個範圍內，而對於任何一種組合來說，最低位數就是確定的，這即使查找表應用的核心（映射是唯一的），比如OSUnMapTbl[4]吧，二進位100，顯然最低在二組（還有0組），即最高的優先順序肯定在這組，y&<&<3用來累計了前面組的任務數；同樣 OSRdyTbl[y] 的結果是當前組的狀態位，放到OSUnMapTbl中查找，找到的就是最低位1所在的位（基於當前組），加上前面累計的優先順序個數，得到的就是當前的最高優先順序；最後再到最開始提到的任務指針表中找到任務堆棧，最高優先順序任務就找到了，

OSTCBPrioTbl

可以看到，無論是任務指針表 還是 優先順序狀態表的查找，都是隨機存取的，無論是設置還是查找，時間都是恆定不變且是最短的，滿足了RTOS對任務調度演算法的要求. 簡單（？）高效

#define offsetof(TYPE, MEMBER) ((size_t) ((TYPE *)0)-&>MEMBER)


#define container_of(ptr, type, member) ((!ptr)?(0):((char *)ptr) - offsetof(type, member))

通過一個結構體的member, 找到這個結構體的首地址. 廣泛用在Linux內核中的鏈表，紅黑樹等結構里.

Windows內核裡面的頁表自映射。對x86的二級映射，在虛擬地址空間，4K的頁目錄表被放在了4M的頁表裡面，而這4M的頁表放在了進程地址空間。這樣就有一個頁目錄項(Page Directory Entry)指向了包含他的頁面本身（Page Directory)，同樣這一項也可以解釋成頁表項(Page Table)指向成包含它本身的頁表。

這樣的好處是為每個進程節省了4K的虛擬空間（不用單獨分配頁目錄表），同事頁目錄表和頁表都放在了地址空間裡面，通過虛擬地址來統一操作頁面映射。

為了不讓明珠蒙塵，這裡介紹一下FreeBSD內核中的遞歸頁表，下面是多年前整理的內容。

在分層的頁表中，如果在最高層的頁目錄中增加一個指向自己的頁目錄指針，就能把頁表項（pte），頁目錄項（pde）抽象為一系列數組，從而高效的查找任意虛擬地址對應的pte,pde或者物理地址。這甚至是一項專利，http://www.mail-archive.com/freebsd-hackers@freebsd.org/msg23732.html

在FreeBSD i386中，相關介面定義為，

extern pt_entry_t PTmap[]; extern pd_entry_t PTD[]; extern pd_entry_t PTDpde[]; #define vtopte(va) (PTmap + i386_btop(va))

假設系統中頁表分為N層，那麼一個虛擬地址分為(N+1)部分( $a_{0}a_{1}a_{2}...a_{N}$ )， $a_{N}$

是頁內偏移量，把每層頁表都當做數組，並且最高層數組定義為T，並且其A項指向自己，即T[A] = T，那麼有 $*(a_{0}a_{1}...a_{N})=*(T[a_{0}][a_{1}]...[a_{(N-1)}] + a_{N})=T[a_{0}][a_{1}]...[a_{N}]$

記第i層頁表為 $L_{i}$ (i = 0, 1, 2, ..., N - 1)，則，

$*L_{i} = T[a_{0}][a_{1}]...[a_{i}] = T[A]...[A][a_{0}][a_{1}]...[a_{i}] = *(A...Aa_{0}a_{1}...a_{i})$

/* 第一個想出這種技巧的人真是太聰明了。*/

@李鑫有請行家指正

數據堆棧先進後出

普通的紅黑樹會單獨開一個單位用來存儲紅黑特性，然後 linux kernel 裡面因為整個struct是四位元組對齊的，所以他們把紅黑的性質直接存儲在每個節點的最低有效位上了。

我研究的是linux操作系統，我覺得最出彩還是內存管理這部分。每個進程都有一個進程描述符，然後進程的內存空間由進程描述符的屬性內存描述符管理，分為一段一段的vma。當分配內存時，先分配虛擬內存，當訪問這塊內存時，產生內存缺頁，在由內核夥伴系統分配物理內存映射～加了一層虛擬內存空間，這樣相當於每個進程都有3G的用戶空間，即使物理內存並沒有那麼多～而且即使物理內存用完了，還支持swaped out到交換區，給人感覺內存取之不盡，用之不竭(;｀O′)o～

linux kernel2.6以後的CFS調度演算法，至於具體實現，擼sched部分源碼吧

我覺得最精華的就是那個內嵌在結構體裡面的雙鏈表，通過container_of來找到外圍結構體我看過這個實現以後基本上鏈表都變成了這種形式，只不過有inline function代替了Linux內核源碼裡面的宏。還有我很喜歡Linux的內存模型。

PS 樓主提得利用物理塊本身實現空閑鏈表的這一設計其實很常見，也很容易想到

看了這個問題，覺得可以回答一下：

1、虛擬內存管理。

由於我們上操作系統課的時候，老師直接就開始講操作系統CPU如何使用頁表進行管理虛擬內存空間，好像在操作系統的歷史上沒有經歷過其它的階段一樣。其實如果讓一個從來沒有了解過現代虛擬內存管理機制的人來設計內存管理，那肯定是有多大物理內存就管理多大物理內存。

但其實不那麼古老的dos（ms-dos）就是在實模式下運行，沒有虛擬內存，沒有頁表的理解。一次就只能運行一個進程，只能訪問1M的進程空間。

當虛擬內存管理的思想發展起來之後（我沒有考證是誰最先提出的），我十分懷疑最先還是由操作系統開發商提出來，後來逐漸成為通用CPU的硬體模塊（MMU，TLB），甚至直接成為通用CPU的內存訪問的標準。至少已知的（x86，arm，mips，好嗎，最後這個是我大龍芯）CPU的內存訪問都是虛擬內存訪問。

有了頁表的虛擬內存機制，我們才有了4GB獨立地進程地址空間。不用擔心物理內存多大就只能使用多大的，不用擔心寫一個地址把別的進程數據寫壞了。

另外，由於所有的地址訪問都是虛擬地址訪問（保護模式下），那麼創建一個頁表，尤其是想出創建一個自映射的頁表，也是一個非常巧妙的設計（前面有人提到這個思想了）。

2、多線程調用。

還是在上操作系統課的時候，老師直接就告訴你怎麼在一個單獨的CPU上實現看起來像是多個線程的運行，實際上還是一次只能運行一個線程的「魔法」。

讓一個CPU同時運行多個程序（線程，至少看起來是同時運行），就有點像完成讓一台發動機同時讓很多輛汽車跑起來的任務一樣，能夠提出這個想法，才是其最閃光的點。

每一個線程共用一個CPU，而且每一個線程並不會感覺到自己被「打斷」了（這個比喻不完全準確）。在我不了解線程切換的代碼實現之前，感覺線程切換是一件很神奇的事情。在我了解了線程切換的代碼之後，真tm的精妙。（可參考毛德操的《22.漫談兼容內核之二十二：Windows線程的調度和運行》）

有了虛擬內存管理，有了多線程調度，才有了現代操作系統的基本框架啊。

3、misc

當然還有一些其它的實現方法也很精妙，FAT表的備份表，增加在文件系統損壞時找迴文件的概率；NT內核的對象管理，以及handle機制，要知道內核是沒有stl的map這種東西，handle表在效率與空間都給出了很好的解決方案；還有調試模塊的很多實現，比如硬體斷點。

先寫這些吧……

Windows內核原理與實現 (豆瓣)

Windows? Internals (豆瓣)

結構體成員指針取出結構體本身指針。以及類似的一些幫助類宏定義

1.進程調度：優先順序與時間片計算。進程隊列中可執行隊列(還有時間片)與過期隊列(時間片耗盡的)交叉替換。

2.內存分配策略：夥伴演算法與slab演算法。

3.快閃記憶體文件系統：借鑒了yaffs文件系統。演算法倒是沒有很出彩的地方。數據結構覺得不錯。由於快閃記憶體的特性(寫入之前要擦除，擦除需要整個塊擦除)，沒辦法把文件系統的結構信息固定的存儲在某個位置，所以只能通過掃描整個flash，收集分布在各地的文件節點，在內存中構建文件系統結構。

bios載入的磁碟的第一個扇區代碼執行完後，就將位於0x10000的內核程序拷貝到內存的起始位置0x00000處，這樣，既廢除了無用的BIOS中斷向量表，又收回了剛剛執行完的BIOS程序的內存空間，讓內核代碼佔據物理內存最開始最天然和最有利的位置。實模式切換保護模式時，head.s的代碼自己覆蓋自己前面已經執行過的代碼來初始化GDT，IDT等。這內存利用效率，這精打細算。。。。。