文末領(lǐng)取大圖。

這不是一篇教你如何創(chuàng)建一個(gè)操作系統(tǒng)的文章录淡，相反捌木，這是一篇指導(dǎo)性文章，教你從幾個(gè)方面來(lái)理解操作系統(tǒng)嫉戚。首先你需要知道你為什么要看這篇文章以及為什么要學(xué)習(xí)操作系統(tǒng)刨裆。

搞清楚幾個(gè)問(wèn)題

首先你要搞明白你學(xué)習(xí)操作系統(tǒng)的目的是什么？操作系統(tǒng)的重要性如何彬檀？學(xué)習(xí)操作系統(tǒng)會(huì)給我?guī)?lái)什么帆啃？下面我會(huì)從這幾個(gè)方面為你回答下。

操作系統(tǒng)也是一種軟件窍帝，但是操作系統(tǒng)是一種非常復(fù)雜的軟件努潘。操作系統(tǒng)提供了幾種抽象模型

• 文件：對(duì) I/O 設(shè)備的抽象
• 虛擬內(nèi)存：對(duì)程序存儲(chǔ)器的抽象
• 進(jìn)程：對(duì)一個(gè)正在運(yùn)行程序的抽象
• 虛擬機(jī)：對(duì)整個(gè)操作系統(tǒng)的抽象

這些抽象和我們的日常開(kāi)發(fā)息息相關(guān)。搞清楚了操作系統(tǒng)是如何抽象的坤学，才能培養(yǎng)我們的抽象性思維和開(kāi)發(fā)思路疯坤。

很多問(wèn)題都和操作系統(tǒng)相關(guān)，操作系統(tǒng)是解決這些問(wèn)題的基礎(chǔ)深浮。如果你不學(xué)習(xí)操作系統(tǒng)压怠，可能會(huì)想著從框架層面來(lái)解決，那是你了解的還不夠深入略号，當(dāng)你學(xué)習(xí)了操作系統(tǒng)后刑峡，能夠培養(yǎng)你的全局性思維。

學(xué)習(xí)操作系統(tǒng)我們能夠有效的解決并發(fā)問(wèn)題玄柠，并發(fā)幾乎是互聯(lián)網(wǎng)的重中之重了突梦，這也從側(cè)面說(shuō)明了學(xué)習(xí)操作系統(tǒng)的重要性。

學(xué)習(xí)操作系統(tǒng)的重點(diǎn)不是讓你從頭制造一個(gè)操作系統(tǒng)羽利，而是告訴你操作系統(tǒng)是如何工作的宫患，能夠讓你對(duì)計(jì)算機(jī)底層有所了解，打?qū)嵞愕幕A(chǔ)这弧。

相信你一定清楚什么是編程

Data structures + Algorithms = Programming

操作系統(tǒng)內(nèi)部會(huì)涉及到眾多的數(shù)據(jù)結(jié)構(gòu)和算法描述娃闲，能夠讓你了解算法的基礎(chǔ)上虚汛，讓你編寫更優(yōu)秀的程序。

我認(rèn)為可以把計(jì)算機(jī)比作一棟樓

計(jì)算機(jī)的底層相當(dāng)于就是樓的根基皇帮，計(jì)算機(jī)應(yīng)用相當(dāng)于就是樓的外形卷哩，而操作系統(tǒng)就相當(dāng)于是告訴你大樓的構(gòu)造原理，編寫高質(zhì)量的軟件就相當(dāng)于是告訴你構(gòu)建一個(gè)穩(wěn)定的房子属拾。

認(rèn)識(shí)操作系統(tǒng)

在了解操作系統(tǒng)前将谊，你需要先知道一下什么是計(jì)算機(jī)系統(tǒng)：現(xiàn)代計(jì)算機(jī)系統(tǒng)由一個(gè)或多個(gè)處理器、主存渐白、打印機(jī)尊浓、鍵盤、鼠標(biāo)纯衍、顯示器栋齿、網(wǎng)絡(luò)接口以及各種輸入/輸出設(shè)備構(gòu)成的系統(tǒng)。這些都屬于硬件的范疇襟诸。我們程序員不會(huì)直接和這些硬件打交道瓦堵，并且每位程序員不可能會(huì)掌握所有計(jì)算機(jī)系統(tǒng)的細(xì)節(jié)。

所以計(jì)算機(jī)科學(xué)家在硬件的基礎(chǔ)之上歌亲，安裝了一層軟件谷丸，這層軟件能夠根據(jù)用戶輸入的指令達(dá)到控制硬件的效果哑姚，從而滿足用戶的需求舌厨，這樣的軟件稱為?操作系統(tǒng)匣沼，它的任務(wù)就是為用戶程序提供一個(gè)更好、更簡(jiǎn)單鹅龄、更清晰的計(jì)算機(jī)模型。也就是說(shuō)亭畜，操作系統(tǒng)相當(dāng)于是一個(gè)中間層扮休，為用戶層和硬件提供各自的借口，屏蔽了不同應(yīng)用和硬件之間的差異拴鸵，達(dá)到統(tǒng)一標(biāo)準(zhǔn)的作用玷坠。

上面一個(gè)操作系統(tǒng)的簡(jiǎn)化圖，最底層是硬件劲藐，硬件包括芯片八堡、電路板、磁盤聘芜、鍵盤兄渺、顯示器等我們上面提到的設(shè)備，在硬件之上是軟件汰现。大部分計(jì)算機(jī)有兩種運(yùn)行模式：內(nèi)核態(tài)?和?用戶態(tài)挂谍，軟件中最基礎(chǔ)的部分是操作系統(tǒng)叔壤，它運(yùn)行在?內(nèi)核態(tài)?中。操作系統(tǒng)具有硬件的訪問(wèn)權(quán)口叙，可以執(zhí)行機(jī)器能夠運(yùn)行的任何指令炼绘。軟件的其余部分運(yùn)行在?用戶態(tài)?下。

在大概了解到操作系統(tǒng)之后妄田，我們先來(lái)認(rèn)識(shí)一下硬件都有哪些

計(jì)算機(jī)硬件

計(jì)算機(jī)硬件是計(jì)算機(jī)的重要組成部分俺亮，其中包含了 5 個(gè)重要的組成部分：運(yùn)算器、控制器形庭、存儲(chǔ)器铅辞、輸入設(shè)備、輸出設(shè)備萨醒。

• 運(yùn)算器：運(yùn)算器最主要的功能是對(duì)數(shù)據(jù)和信息進(jìn)行加工和運(yùn)算斟珊。它是計(jì)算機(jī)中執(zhí)行算數(shù)和各種邏輯運(yùn)算的部件。運(yùn)算器的基本運(yùn)算包括加富纸、減囤踩、乘、除晓褪、移位等操作堵漱，這些是由?算術(shù)邏輯單元(Arithmetic&logical Unit)?實(shí)現(xiàn)的。而運(yùn)算器主要由算數(shù)邏輯單元和寄存器構(gòu)成涣仿。
• 控制器：指按照指定順序改變主電路或控制電路的部件勤庐，它主要起到了控制命令執(zhí)行的作用，完成協(xié)調(diào)和指揮整個(gè)計(jì)算機(jī)系統(tǒng)的操作好港∮淞控制器是由程序計(jì)數(shù)器、指令寄存器钧汹、解碼譯碼器等構(gòu)成丈探。

運(yùn)算器和控制器共同組成了 CPU

• 存儲(chǔ)器：存儲(chǔ)器就是計(jì)算機(jī)的記憶設(shè)備，顧名思義拔莱，存儲(chǔ)器可以保存信息碗降。存儲(chǔ)器分為兩種，一種是主存塘秦，也就是內(nèi)存讼渊，它是 CPU 主要交互對(duì)象，還有一種是外存尊剔，比如硬盤軟盤等精偿。下面是現(xiàn)代計(jì)算機(jī)系統(tǒng)的存儲(chǔ)架構(gòu)

• 輸入設(shè)備：輸入設(shè)備是給計(jì)算機(jī)獲取外部信息的設(shè)備，它主要包括鍵盤和鼠標(biāo)。

• 輸出設(shè)備：輸出設(shè)備是給用戶呈現(xiàn)根據(jù)輸入設(shè)備獲取的信息經(jīng)過(guò)一系列的計(jì)算后得到顯示的設(shè)備笔咽，它主要包括顯示器搔预、打印機(jī)等。

這五部分也是馮諾伊曼的體系結(jié)構(gòu)叶组，它認(rèn)為計(jì)算機(jī)必須具有如下功能：

把需要的程序和數(shù)據(jù)送至計(jì)算機(jī)中拯田。必須具有長(zhǎng)期記憶程序、數(shù)據(jù)甩十、中間結(jié)果及最終運(yùn)算結(jié)果的能力船庇。能夠完成各種算術(shù)、邏輯運(yùn)算和數(shù)據(jù)傳送等數(shù)據(jù)加工處理的能力侣监。能夠根據(jù)需要控制程序走向鸭轮，并能根據(jù)指令控制機(jī)器的各部件協(xié)調(diào)操作。能夠按照要求將處理結(jié)果輸出給用戶橄霉。

下面是一張 intel 家族產(chǎn)品圖窃爷，是一個(gè)詳細(xì)的計(jì)算機(jī)硬件分類，我們?cè)诟鶕?jù)圖中涉及到硬件進(jìn)行介紹

• 總線(Buses)：在整個(gè)系統(tǒng)中運(yùn)行的是稱為總線的電氣管道的集合姓蜂，這些總線在組件之間來(lái)回傳輸字節(jié)信息按厘。通常總線被設(shè)計(jì)成傳送定長(zhǎng)的字節(jié)塊钱慢，也就是?字(word)逮京。字中的字節(jié)數(shù)（字長(zhǎng)）是一個(gè)基本的系統(tǒng)參數(shù)，各個(gè)系統(tǒng)中都不盡相同∈現(xiàn)在大部分的字都是 4 個(gè)字節(jié)（32 位）或者 8 個(gè)字節(jié)（64 位）懒棉。

• I/O 設(shè)備(I/O Devices)：Input/Output 設(shè)備是系統(tǒng)和外部世界的連接。上圖中有四類 I/O 設(shè)備：用于用戶輸入的鍵盤和鼠標(biāo)览绿，用于用戶輸出的顯示器漓藕，一個(gè)磁盤驅(qū)動(dòng)用來(lái)長(zhǎng)時(shí)間的保存數(shù)據(jù)和程序。剛開(kāi)始的時(shí)候挟裂，可執(zhí)行程序就保存在磁盤上。

  每個(gè)I/O 設(shè)備連接 I/O 總線都被稱為控制器(controller)?或者是?適配器(Adapter)揍诽【魅兀控制器和適配器之間的主要區(qū)別在于封裝方式∈畲啵控制器是 I/O 設(shè)備本身或者系統(tǒng)的主印制板電路（通常稱作主板）上的芯片組渠啤。而適配器則是一塊插在主板插槽上的卡。無(wú)論組織形式如何添吗，它們的最終目的都是彼此交換信息沥曹。

• 主存(Main Memory)，主存是一個(gè)臨時(shí)存儲(chǔ)設(shè)備，而不是永久性存儲(chǔ)妓美，磁盤是?永久性存儲(chǔ)?的設(shè)備僵腺。主存既保存程序，又保存處理器執(zhí)行流程所處理的數(shù)據(jù)壶栋。從物理組成上說(shuō)辰如，主存是由一系列?DRAM(dynamic random access memory)?動(dòng)態(tài)隨機(jī)存儲(chǔ)構(gòu)成的集合。邏輯上說(shuō)贵试，內(nèi)存就是一個(gè)線性的字節(jié)數(shù)組琉兜，有它唯一的地址編號(hào)，從 0 開(kāi)始毙玻。一般來(lái)說(shuō)豌蟋，組成程序的每條機(jī)器指令都由不同數(shù)量的字節(jié)構(gòu)成，C 程序變量相對(duì)應(yīng)的數(shù)據(jù)項(xiàng)的大小根據(jù)類型進(jìn)行變化桑滩。比如梧疲，在 Linux 的 x86-64 機(jī)器上，short 類型的數(shù)據(jù)需要 2 個(gè)字節(jié)施符，int 和 float 需要 4 個(gè)字節(jié)往声，而 long 和 double 需要 8 個(gè)字節(jié)。

• 處理器(Processor)戳吝，CPU(central processing unit)?或者簡(jiǎn)單的處理器浩销，是解釋（并執(zhí)行）存儲(chǔ)在主存儲(chǔ)器中的指令的引擎。處理器的核心大小為一個(gè)字的存儲(chǔ)設(shè)備（或寄存器）听哭，稱為程序計(jì)數(shù)器(PC)慢洋。在任何時(shí)刻，PC 都指向主存中的某條機(jī)器語(yǔ)言指令（即含有該條指令的地址）陆盘。

  從系統(tǒng)通電開(kāi)始普筹，直到系統(tǒng)斷電，處理器一直在不斷地執(zhí)行程序計(jì)數(shù)器指向的指令隘马，再更新程序計(jì)數(shù)器太防，使其指向下一條指令。處理器根據(jù)其指令集體系結(jié)構(gòu)定義的指令模型進(jìn)行操作酸员。在這個(gè)模型中蜒车，指令按照嚴(yán)格的順序執(zhí)行，執(zhí)行一條指令涉及執(zhí)行一系列的步驟幔嗦。處理器從程序計(jì)數(shù)器指向的內(nèi)存中讀取指令酿愧，解釋指令中的位，執(zhí)行該指令指示的一些簡(jiǎn)單操作邀泉，然后更新程序計(jì)數(shù)器以指向下一條指令嬉挡。指令與指令之間可能連續(xù)钝鸽，可能不連續(xù)（比如 jmp 指令就不會(huì)順序讀取）

下面是 CPU 可能執(zhí)行簡(jiǎn)單操作的幾個(gè)步驟

• 加載(Load)：從主存中拷貝一個(gè)字節(jié)或者一個(gè)字到內(nèi)存中庞钢，覆蓋寄存器先前的內(nèi)容
• 存儲(chǔ)(Store)：將寄存器中的字節(jié)或字復(fù)制到主存儲(chǔ)器中的某個(gè)位置拔恰，從而覆蓋該位置的先前內(nèi)容
• 操作(Operate)：把兩個(gè)寄存器的內(nèi)容復(fù)制到?ALU(Arithmetic logic unit)。把兩個(gè)字進(jìn)行算術(shù)運(yùn)算焊夸，并把結(jié)果存儲(chǔ)在寄存器中仁连，重寫寄存器先前的內(nèi)容。

算術(shù)邏輯單元（ALU）是對(duì)數(shù)字二進(jìn)制數(shù)執(zhí)行算術(shù)和按位運(yùn)算的組合數(shù)字電子電路阱穗。

• 跳轉(zhuǎn)(jump)：從指令中抽取一個(gè)字饭冬，把這個(gè)字復(fù)制到程序計(jì)數(shù)器(PC)?中，覆蓋原來(lái)的值

進(jìn)程和線程

關(guān)于進(jìn)程和線程揪阶，你需要理解下面這張腦圖中的重點(diǎn)

進(jìn)程

操作系統(tǒng)中最核心的概念就是?進(jìn)程昌抠，進(jìn)程是對(duì)正在運(yùn)行中的程序的一個(gè)抽象。操作系統(tǒng)的其他所有內(nèi)容都是圍繞著進(jìn)程展開(kāi)的鲁僚。

在多道程序處理的系統(tǒng)中炊苫，CPU 會(huì)在進(jìn)程間快速切換，使每個(gè)程序運(yùn)行幾十或者幾百毫秒冰沙。然而侨艾，嚴(yán)格意義來(lái)說(shuō)，在某一個(gè)瞬間拓挥，CPU 只能運(yùn)行一個(gè)進(jìn)程唠梨，然而我們?nèi)绻褧r(shí)間定位為 1 秒內(nèi)的話，它可能運(yùn)行多個(gè)進(jìn)程侥啤。這樣就會(huì)讓我們產(chǎn)生并行的錯(cuò)覺(jué)当叭。因?yàn)?CPU 執(zhí)行速度很快，進(jìn)程間的換進(jìn)換出也非常迅速盖灸，因此我們很難對(duì)多個(gè)并行進(jìn)程進(jìn)行跟蹤蚁鳖。所以，操作系統(tǒng)的設(shè)計(jì)者開(kāi)發(fā)了用于描述并行的一種概念模型（順序進(jìn)程）赁炎，使得并行更加容易理解和分析醉箕。

進(jìn)程模型

一個(gè)進(jìn)程就是一個(gè)正在執(zhí)行的程序的實(shí)例，進(jìn)程也包括程序計(jì)數(shù)器徙垫、寄存器和變量的當(dāng)前值讥裤。從概念上來(lái)說(shuō)，每個(gè)進(jìn)程都有各自的虛擬 CPU松邪，但是實(shí)際情況是 CPU 會(huì)在各個(gè)進(jìn)程之間進(jìn)行來(lái)回切換。

如上圖所示哨查，這是一個(gè)具有 4 個(gè)程序的多道處理程序逗抑，在進(jìn)程不斷切換的過(guò)程中，程序計(jì)數(shù)器也在不同的變化。

在上圖中邮府，這 4 道程序被抽象為 4 個(gè)擁有各自控制流程（即每個(gè)自己的程序計(jì)數(shù)器）的進(jìn)程荧关，并且每個(gè)程序都獨(dú)立的運(yùn)行。當(dāng)然褂傀，實(shí)際上只有一個(gè)物理程序計(jì)數(shù)器忍啤，每個(gè)程序要運(yùn)行時(shí)，其邏輯程序計(jì)數(shù)器會(huì)裝載到物理程序計(jì)數(shù)器中仙辟。當(dāng)程序運(yùn)行結(jié)束后同波，其物理程序計(jì)數(shù)器就會(huì)是真正的程序計(jì)數(shù)器，然后再把它放回進(jìn)程的邏輯計(jì)數(shù)器中叠国。

從下圖我們可以看到未檩，在觀察足夠長(zhǎng)的一段時(shí)間后，所有的進(jìn)程都運(yùn)行了粟焊，但在任何一個(gè)給定的瞬間僅有一個(gè)進(jìn)程真正運(yùn)行冤狡。

因此，當(dāng)我們說(shuō)一個(gè) CPU 只能真正一次運(yùn)行一個(gè)進(jìn)程的時(shí)候项棠，即使有 2 個(gè)核（或 CPU）悲雳，每一個(gè)核也只能一次運(yùn)行一個(gè)線程。

由于 CPU 會(huì)在各個(gè)進(jìn)程之間來(lái)回快速切換香追，所以每個(gè)進(jìn)程在 CPU 中的運(yùn)行時(shí)間是無(wú)法確定的合瓢。并且當(dāng)同一個(gè)進(jìn)程再次在 CPU 中運(yùn)行時(shí)，其在 CPU 內(nèi)部的運(yùn)行時(shí)間往往也是不固定的翅阵。

這里的關(guān)鍵思想是認(rèn)識(shí)到一個(gè)進(jìn)程所需的條件歪玲，進(jìn)程是某一類特定活動(dòng)的總和，它有程序掷匠、輸入輸出以及狀態(tài)滥崩。

進(jìn)程的創(chuàng)建

操作系統(tǒng)需要一些方式來(lái)創(chuàng)建進(jìn)程。下面是一些創(chuàng)建進(jìn)程的方式

• 系統(tǒng)初始化（init）：?jiǎn)?dòng)操作系統(tǒng)時(shí)讹语，通常會(huì)創(chuàng)建若干個(gè)進(jìn)程钙皮。
• 正在運(yùn)行的程序執(zhí)行了創(chuàng)建進(jìn)程的系統(tǒng)調(diào)用（比如 fork）
• 用戶請(qǐng)求創(chuàng)建一個(gè)新進(jìn)程：在許多交互式系統(tǒng)中，輸入一個(gè)命令或者雙擊圖標(biāo)就可以啟動(dòng)程序顽决，以上任意一種操作都可以選擇開(kāi)啟一個(gè)新的進(jìn)程短条，在基本的 UNIX 系統(tǒng)中運(yùn)行 X，新進(jìn)程將接管啟動(dòng)它的窗口才菠。
• 初始化一個(gè)批處理工作

從技術(shù)上講茸时，在所有這些情況下，讓現(xiàn)有流程執(zhí)行流程是通過(guò)創(chuàng)建系統(tǒng)調(diào)用來(lái)創(chuàng)建新流程的赋访。該進(jìn)程可能是正在運(yùn)行的用戶進(jìn)程可都，是從鍵盤或鼠標(biāo)調(diào)用的系統(tǒng)進(jìn)程或批處理程序缓待。這些就是系統(tǒng)調(diào)用創(chuàng)建新進(jìn)程的過(guò)程。該系統(tǒng)調(diào)用告訴操作系統(tǒng)創(chuàng)建一個(gè)新進(jìn)程渠牲，并直接或間接指示在其中運(yùn)行哪個(gè)程序旋炒。

在 UNIX 中，僅有一個(gè)系統(tǒng)調(diào)用來(lái)創(chuàng)建一個(gè)新的進(jìn)程签杈，這個(gè)系統(tǒng)調(diào)用就是?fork瘫镇。這個(gè)調(diào)用會(huì)創(chuàng)建一個(gè)與調(diào)用進(jìn)程相關(guān)的副本。在 fork 后答姥，一個(gè)父進(jìn)程和子進(jìn)程會(huì)有相同的內(nèi)存映像铣除，相同的環(huán)境字符串和相同的打開(kāi)文件。

在 Windows 中踢涌，情況正相反通孽，一個(gè)簡(jiǎn)單的 Win32 功能調(diào)用?CreateProcess，會(huì)處理流程創(chuàng)建并將正確的程序加載到新的進(jìn)程中睁壁。這個(gè)調(diào)用會(huì)有 10 個(gè)參數(shù)背苦，包括了需要執(zhí)行的程序、輸入給程序的命令行參數(shù)潘明、各種安全屬性行剂、有關(guān)打開(kāi)的文件是否繼承控制位、優(yōu)先級(jí)信息钳降、進(jìn)程所需要?jiǎng)?chuàng)建的窗口規(guī)格以及指向一個(gè)結(jié)構(gòu)的指針厚宰，在該結(jié)構(gòu)中新創(chuàng)建進(jìn)程的信息被返回給調(diào)用者。在 Windows 中遂填，從一開(kāi)始父進(jìn)程的地址空間和子進(jìn)程的地址空間就是不同的铲觉。

進(jìn)程的終止

進(jìn)程在創(chuàng)建之后，它就開(kāi)始運(yùn)行并做完成任務(wù)吓坚。然而撵幽，沒(méi)有什么事兒是永不停歇的，包括進(jìn)程也一樣礁击。進(jìn)程早晚會(huì)發(fā)生終止盐杂，但是通常是由于以下情況觸發(fā)的

• 正常退出(自愿的)?： 多數(shù)進(jìn)程是由于完成了工作而終止。當(dāng)編譯器完成了所給定程序的編譯之后哆窿，編譯器會(huì)執(zhí)行一個(gè)系統(tǒng)調(diào)用告訴操作系統(tǒng)它完成了工作链烈。這個(gè)調(diào)用在 UNIX 中是?exit?，在 Windows 中是?ExitProcess挚躯。
• 錯(cuò)誤退出(自愿的)：比如執(zhí)行一條不存在的命令强衡，于是編譯器就會(huì)提醒并退出。
• 嚴(yán)重錯(cuò)誤(非自愿的)
• 被其他進(jìn)程殺死(非自愿的)?： 某個(gè)進(jìn)程執(zhí)行系統(tǒng)調(diào)用告訴操作系統(tǒng)殺死某個(gè)進(jìn)程码荔。在 UNIX 中漩勤，這個(gè)系統(tǒng)調(diào)用是 kill号涯。在 Win32 中對(duì)應(yīng)的函數(shù)是?TerminateProcess（注意不是系統(tǒng)調(diào)用）。

進(jìn)程的層次結(jié)構(gòu)

在一些系統(tǒng)中锯七，當(dāng)一個(gè)進(jìn)程創(chuàng)建了其他進(jìn)程后，父進(jìn)程和子進(jìn)程就會(huì)以某種方式進(jìn)行關(guān)聯(lián)誉己。子進(jìn)程它自己就會(huì)創(chuàng)建更多進(jìn)程眉尸，從而形成一個(gè)進(jìn)程層次結(jié)構(gòu)。

UNIX 進(jìn)程體系

在 UNIX 中巨双，進(jìn)程和它的所有子進(jìn)程以及子進(jìn)程的子進(jìn)程共同組成一個(gè)進(jìn)程組噪猾。當(dāng)用戶從鍵盤中發(fā)出一個(gè)信號(hào)后，該信號(hào)被發(fā)送給當(dāng)前與鍵盤相關(guān)的進(jìn)程組中的所有成員（它們通常是在當(dāng)前窗口創(chuàng)建的所有活動(dòng)進(jìn)程）筑累。每個(gè)進(jìn)程可以分別捕獲該信號(hào)袱蜡、忽略該信號(hào)或采取默認(rèn)的動(dòng)作，即被信號(hào) kill 掉慢宗。整個(gè)操作系統(tǒng)中所有的進(jìn)程都隸屬于一個(gè)單個(gè)以 init 為根的進(jìn)程樹(shù)坪蚁。

Windows 進(jìn)程體系

相反，Windows 中沒(méi)有進(jìn)程層次的概念镜沽，Windows 中所有進(jìn)程都是平等的敏晤，唯一類似于層次結(jié)構(gòu)的是在創(chuàng)建進(jìn)程的時(shí)候，父進(jìn)程得到一個(gè)特別的令牌（稱為句柄）缅茉，該句柄可以用來(lái)控制子進(jìn)程嘴脾。然而，這個(gè)令牌可能也會(huì)移交給別的操作系統(tǒng)蔬墩，這樣就不存在層次結(jié)構(gòu)了译打。而在 UNIX 中，進(jìn)程不能剝奪其子進(jìn)程的?進(jìn)程權(quán)拇颅。（這樣看來(lái)奏司，還是 Windows 比較渣）。

進(jìn)程狀態(tài)

盡管每個(gè)進(jìn)程是一個(gè)獨(dú)立的實(shí)體蔬蕊，有其自己的程序計(jì)數(shù)器和內(nèi)部狀態(tài)结澄，但是，進(jìn)程之間仍然需要相互幫助岸夯。當(dāng)一個(gè)進(jìn)程開(kāi)始運(yùn)行時(shí)麻献，它可能會(huì)經(jīng)歷下面這幾種狀態(tài)

圖中會(huì)涉及三種狀態(tài)

1. 運(yùn)行態(tài)，運(yùn)行態(tài)指的就是進(jìn)程實(shí)際占用 CPU 時(shí)間片運(yùn)行時(shí)
2. 就緒態(tài)猜扮，就緒態(tài)指的是可運(yùn)行勉吻，但因?yàn)槠渌M(jìn)程正在運(yùn)行而處于就緒狀態(tài)
3. 阻塞態(tài)，除非某種外部事件發(fā)生旅赢，否則進(jìn)程不能運(yùn)行

進(jìn)程的實(shí)現(xiàn)

操作系統(tǒng)為了執(zhí)行進(jìn)程間的切換齿桃，會(huì)維護(hù)著一張表惑惶，這張表就是?進(jìn)程表(process table)。每個(gè)進(jìn)程占用一個(gè)進(jìn)程表項(xiàng)短纵。該表項(xiàng)包含了進(jìn)程狀態(tài)的重要信息带污，包括程序計(jì)數(shù)器、堆棧指針香到、內(nèi)存分配狀況鱼冀、所打開(kāi)文件的狀態(tài)、賬號(hào)和調(diào)度信息悠就，以及其他在進(jìn)程由運(yùn)行態(tài)轉(zhuǎn)換到就緒態(tài)或阻塞態(tài)時(shí)所必須保存的信息千绪。

下面展示了一個(gè)典型系統(tǒng)中的關(guān)鍵字段

第一列內(nèi)容與進(jìn)程管理有關(guān)，第二列內(nèi)容與?存儲(chǔ)管理有關(guān)梗脾，第三列內(nèi)容與文件管理有關(guān)荸型。

現(xiàn)在我們應(yīng)該對(duì)進(jìn)程表有個(gè)大致的了解了，就可以在對(duì)單個(gè) CPU 上如何運(yùn)行多個(gè)順序進(jìn)程的錯(cuò)覺(jué)做更多的解釋炸茧。與每一 I/O 類相關(guān)聯(lián)的是一個(gè)稱作?中斷向量(interrupt vector)?的位置（靠近內(nèi)存底部的固定區(qū)域）瑞妇。它包含中斷服務(wù)程序的入口地址。假設(shè)當(dāng)一個(gè)磁盤中斷發(fā)生時(shí)梭冠，用戶進(jìn)程 3 正在運(yùn)行踪宠，則中斷硬件將程序計(jì)數(shù)器、程序狀態(tài)字妈嘹、有時(shí)還有一個(gè)或多個(gè)寄存器壓入堆棧柳琢，計(jì)算機(jī)隨即跳轉(zhuǎn)到中斷向量所指示的地址。這就是硬件所做的事情润脸。然后軟件就隨即接管一切剩余的工作柬脸。

當(dāng)中斷結(jié)束后，操作系統(tǒng)會(huì)調(diào)用一個(gè) C 程序來(lái)處理中斷剩下的工作毙驯。在完成剩下的工作后倒堕，會(huì)使某些進(jìn)程就緒，接著調(diào)用調(diào)度程序爆价，決定隨后運(yùn)行哪個(gè)進(jìn)程垦巴。然后將控制權(quán)轉(zhuǎn)移給一段匯編語(yǔ)言代碼，為當(dāng)前的進(jìn)程裝入寄存器值以及內(nèi)存映射并啟動(dòng)該進(jìn)程運(yùn)行铭段，下面顯示了中斷處理和調(diào)度的過(guò)程骤宣。

1. 硬件壓入堆棧程序計(jì)數(shù)器等

2. 硬件從中斷向量裝入新的程序計(jì)數(shù)器

3. 匯編語(yǔ)言過(guò)程保存寄存器的值

4. 匯編語(yǔ)言過(guò)程設(shè)置新的堆棧

5. C 中斷服務(wù)器運(yùn)行（典型的讀和緩存寫入）

6. 調(diào)度器決定下面哪個(gè)程序先運(yùn)行

7. C 過(guò)程返回至匯編代碼

8. 匯編語(yǔ)言過(guò)程開(kāi)始運(yùn)行新的當(dāng)前進(jìn)程

一個(gè)進(jìn)程在執(zhí)行過(guò)程中可能被中斷數(shù)千次，但關(guān)鍵每次中斷后序愚，被中斷的進(jìn)程都返回到與中斷發(fā)生前完全相同的狀態(tài)憔披。

線程

在傳統(tǒng)的操作系統(tǒng)中，每個(gè)進(jìn)程都有一個(gè)地址空間和一個(gè)控制線程。事實(shí)上芬膝，這是大部分進(jìn)程的定義望门。不過(guò)，在許多情況下锰霜，經(jīng)常存在同一地址空間中運(yùn)行多個(gè)控制線程的情形筹误，這些線程就像是分離的進(jìn)程。下面我們就著重探討一下什么是線程

線程的使用

或許這個(gè)疑問(wèn)也是你的疑問(wèn)，為什么要在進(jìn)程的基礎(chǔ)上再創(chuàng)建一個(gè)線程的概念寻狂，準(zhǔn)確的說(shuō)，這其實(shí)是進(jìn)程模型和線程模型的討論，回答這個(gè)問(wèn)題设拟，可能需要分三步來(lái)回答

• 多線程之間會(huì)共享同一塊地址空間和所有可用數(shù)據(jù)的能力，這是進(jìn)程所不具備的
• 線程要比進(jìn)程更輕量級(jí)磕蛇，由于線程更輕命锄，所以它比進(jìn)程更容易創(chuàng)建，也更容易撤銷万哪。在許多系統(tǒng)中侠驯，創(chuàng)建一個(gè)線程要比創(chuàng)建一個(gè)進(jìn)程快 10 - 100 倍。
• 第三個(gè)原因可能是性能方面的探討奕巍，如果多個(gè)線程都是 CPU 密集型的吟策，那么并不能獲得性能上的增強(qiáng)，但是如果存在著大量的計(jì)算和大量的 I/O 處理的止，擁有多個(gè)線程能在這些活動(dòng)中彼此重疊進(jìn)行檩坚，從而會(huì)加快應(yīng)用程序的執(zhí)行速度

經(jīng)典的線程模型

進(jìn)程中擁有一個(gè)執(zhí)行的線程，通常簡(jiǎn)寫為?線程(thread)诅福。線程會(huì)有程序計(jì)數(shù)器匾委，用來(lái)記錄接著要執(zhí)行哪一條指令；線程實(shí)際上 CPU 上調(diào)度執(zhí)行的實(shí)體氓润。

下圖我們可以看到三個(gè)傳統(tǒng)的進(jìn)程赂乐，每個(gè)進(jìn)程有自己的地址空間和單個(gè)控制線程。每個(gè)線程都在不同的地址空間中運(yùn)行

下圖中咖气，我們可以看到有一個(gè)進(jìn)程三個(gè)線程的情況挨措。每個(gè)線程都在相同的地址空間中運(yùn)行。

線程不像是進(jìn)程那樣具備較強(qiáng)的獨(dú)立性崩溪。同一個(gè)進(jìn)程中的所有線程都會(huì)有完全一樣的地址空間浅役，這意味著它們也共享同樣的全局變量。由于每個(gè)線程都可以訪問(wèn)進(jìn)程地址空間內(nèi)每個(gè)內(nèi)存地址伶唯，因此一個(gè)線程可以讀取担租、寫入甚至擦除另一個(gè)線程的堆棧。線程之間除了共享同一內(nèi)存空間外抵怎，還具有如下不同的內(nèi)容

上圖左邊的是同一個(gè)進(jìn)程中每個(gè)線程共享的內(nèi)容奋救，上圖右邊是每個(gè)線程中的內(nèi)容岭参。也就是說(shuō)左邊的列表是進(jìn)程的屬性，右邊的列表是線程的屬性尝艘。

線程之間的狀態(tài)轉(zhuǎn)換和進(jìn)程之間的狀態(tài)轉(zhuǎn)換是一樣的演侯。

每個(gè)線程都會(huì)有自己的堆棧，如下圖所示

線程系統(tǒng)調(diào)用

進(jìn)程通常會(huì)從當(dāng)前的某個(gè)單線程開(kāi)始背亥，然后這個(gè)線程通過(guò)調(diào)用一個(gè)庫(kù)函數(shù)（比如?thread_create）創(chuàng)建新的線程秒际。線程創(chuàng)建的函數(shù)會(huì)要求指定新創(chuàng)建線程的名稱。創(chuàng)建的線程通常都返回一個(gè)線程標(biāo)識(shí)符狡汉，該標(biāo)識(shí)符就是新線程的名字娄徊。

當(dāng)一個(gè)線程完成工作后，可以通過(guò)調(diào)用一個(gè)函數(shù)（比如?thread_exit）來(lái)退出盾戴。緊接著線程消失寄锐，狀態(tài)變?yōu)榻K止，不能再進(jìn)行調(diào)度尖啡。在某些線程的運(yùn)行過(guò)程中橄仆，可以通過(guò)調(diào)用函數(shù)例如?thread_join?，表示一個(gè)線程可以等待另一個(gè)線程退出衅斩。這個(gè)過(guò)程阻塞調(diào)用線程直到等待特定的線程退出盆顾。在這種情況下，線程的創(chuàng)建和終止非常類似于進(jìn)程的創(chuàng)建和終止畏梆。

另一個(gè)常見(jiàn)的線程是調(diào)用?thread_yield您宪，它允許線程自動(dòng)放棄 CPU 從而讓另一個(gè)線程運(yùn)行。這樣一個(gè)調(diào)用還是很重要的奠涌，因?yàn)椴煌谶M(jìn)程蚕涤，線程是無(wú)法利用時(shí)鐘中斷強(qiáng)制讓線程讓出 CPU 的。

POSIX 線程

POSIX 線程 通常稱為 pthreads是一種獨(dú)立于語(yǔ)言而存在的執(zhí)行模型铣猩，以及并行執(zhí)行模型揖铜。

它允許程序控制時(shí)間上重疊的多個(gè)不同的工作流程。每個(gè)工作流程都稱為一個(gè)線程达皿，可以通過(guò)調(diào)用 POSIX Threads API 來(lái)實(shí)現(xiàn)對(duì)這些流程的創(chuàng)建和控制天吓。可以把它理解為線程的標(biāo)準(zhǔn)峦椰。

POSIX Threads 的實(shí)現(xiàn)在許多類似且符合POSIX的操作系統(tǒng)上可用龄寞，例如?FreeBSD、NetBSD汤功、OpenBSD物邑、Linux、macOS、Android色解、Solaris茂嗓，它在現(xiàn)有 Windows API 之上實(shí)現(xiàn)了pthread。

IEEE 是世界上最大的技術(shù)專業(yè)組織科阎，致力于為人類的利益而發(fā)展技術(shù)述吸。

線程調(diào)用描述pthread_create創(chuàng)建一個(gè)新線程pthread_exit結(jié)束調(diào)用的線程pthread_join等待一個(gè)特定的線程退出pthread_yield釋放 CPU 來(lái)運(yùn)行另外一個(gè)線程pthread_attr_init創(chuàng)建并初始化一個(gè)線程的屬性結(jié)構(gòu)pthread_attr_destory刪除一個(gè)線程的屬性結(jié)構(gòu)

所有的 Pthreads 都有特定的屬性，每一個(gè)都含有標(biāo)識(shí)符锣笨、一組寄存器（包括程序計(jì)數(shù)器）和一組存儲(chǔ)在結(jié)構(gòu)中的屬性蝌矛。這個(gè)屬性包括堆棧大小、調(diào)度參數(shù)以及其他線程需要的項(xiàng)目错英。

線程實(shí)現(xiàn)

主要有三種實(shí)現(xiàn)方式

• 在用戶空間中實(shí)現(xiàn)線程入撒；
• 在內(nèi)核空間中實(shí)現(xiàn)線程；
• 在用戶和內(nèi)核空間中混合實(shí)現(xiàn)線程椭岩。

下面我們分開(kāi)討論一下

在用戶空間中實(shí)現(xiàn)線程

第一種方法是把整個(gè)線程包放在用戶空間中茅逮，內(nèi)核對(duì)線程一無(wú)所知，它不知道線程的存在簿煌。所有的這類實(shí)現(xiàn)都有同樣的通用結(jié)構(gòu)

線程在運(yùn)行時(shí)系統(tǒng)之上運(yùn)行，運(yùn)行時(shí)系統(tǒng)是管理線程過(guò)程的集合鉴吹，包括前面提到的四個(gè)過(guò)程： pthread_create, pthread_exit, pthread_join 和 pthread_yield姨伟。

在內(nèi)核中實(shí)現(xiàn)線程

當(dāng)某個(gè)線程希望創(chuàng)建一個(gè)新線程或撤銷一個(gè)已有線程時(shí)，它會(huì)進(jìn)行一個(gè)系統(tǒng)調(diào)用豆励，這個(gè)系統(tǒng)調(diào)用通過(guò)對(duì)線程表的更新來(lái)完成線程創(chuàng)建或銷毀工作夺荒。

內(nèi)核中的線程表持有每個(gè)線程的寄存器、狀態(tài)和其他信息良蒸。這些信息和用戶空間中的線程信息相同技扼，但是位置卻被放在了內(nèi)核中而不是用戶空間中。另外嫩痰，內(nèi)核還維護(hù)了一張進(jìn)程表用來(lái)跟蹤系統(tǒng)狀態(tài)剿吻。

所有能夠阻塞的調(diào)用都會(huì)通過(guò)系統(tǒng)調(diào)用的方式來(lái)實(shí)現(xiàn)，當(dāng)一個(gè)線程阻塞時(shí)串纺，內(nèi)核可以進(jìn)行選擇丽旅，是運(yùn)行在同一個(gè)進(jìn)程中的另一個(gè)線程（如果有就緒線程的話）還是運(yùn)行一個(gè)另一個(gè)進(jìn)程中的線程。但是在用戶實(shí)現(xiàn)中纺棺，運(yùn)行時(shí)系統(tǒng)始終運(yùn)行自己的線程榄笙，直到內(nèi)核剝奪它的 CPU 時(shí)間片（或者沒(méi)有可運(yùn)行的線程存在了）為止。

混合實(shí)現(xiàn)

結(jié)合用戶空間和內(nèi)核空間的優(yōu)點(diǎn)祷蝌，設(shè)計(jì)人員采用了一種內(nèi)核級(jí)線程的方式茅撞，然后將用戶級(jí)線程與某些或者全部?jī)?nèi)核線程多路復(fù)用起來(lái)

在這種模型中，編程人員可以自由控制用戶線程和內(nèi)核線程的數(shù)量，具有很大的靈活度米丘。采用這種方法剑令，內(nèi)核只識(shí)別內(nèi)核級(jí)線程，并對(duì)其進(jìn)行調(diào)度蠕蚜。其中一些內(nèi)核級(jí)線程會(huì)被多個(gè)用戶級(jí)線程多路復(fù)用尚洽。

進(jìn)程間通信

進(jìn)程是需要頻繁的和其他進(jìn)程進(jìn)行交流的。下面我們會(huì)一起討論有關(guān)?進(jìn)程間通信(Inter Process Communication, IPC)?的問(wèn)題靶累。大致來(lái)說(shuō)腺毫，進(jìn)程間的通信機(jī)制可以分為 6 種

下面我們分別對(duì)其進(jìn)行概述

信號(hào) signal

信號(hào)是 UNIX 系統(tǒng)最先開(kāi)始使用的進(jìn)程間通信機(jī)制，因?yàn)?Linux 是繼承于 UNIX 的挣柬，所以 Linux 也支持信號(hào)機(jī)制潮酒，通過(guò)向一個(gè)或多個(gè)進(jìn)程發(fā)送異步事件信號(hào)來(lái)實(shí)現(xiàn)，信號(hào)可以從鍵盤或者訪問(wèn)不存在的位置等地方產(chǎn)生邪蛔；信號(hào)通過(guò) shell 將任務(wù)發(fā)送給子進(jìn)程急黎。

你可以在 Linux 系統(tǒng)上輸入?kill -l?來(lái)列出系統(tǒng)使用的信號(hào)，下面是我提供的一些信號(hào)

進(jìn)程可以選擇忽略發(fā)送過(guò)來(lái)的信號(hào)侧到，但是有兩個(gè)是不能忽略的：SIGSTOP?和?SIGKILL?信號(hào)勃教。SIGSTOP 信號(hào)會(huì)通知當(dāng)前正在運(yùn)行的進(jìn)程執(zhí)行關(guān)閉操作，SIGKILL 信號(hào)會(huì)通知當(dāng)前進(jìn)程應(yīng)該被殺死匠抗。除此之外故源，進(jìn)程可以選擇它想要處理的信號(hào)，進(jìn)程也可以選擇阻止信號(hào)汞贸，如果不阻止绳军，可以選擇自行處理，也可以選擇進(jìn)行內(nèi)核處理矢腻。如果選擇交給內(nèi)核進(jìn)行處理门驾，那么就執(zhí)行默認(rèn)處理。

操作系統(tǒng)會(huì)中斷目標(biāo)程序的進(jìn)程來(lái)向其發(fā)送信號(hào)多柑、在任何非原子指令中奶是，執(zhí)行都可以中斷，如果進(jìn)程已經(jīng)注冊(cè)了新號(hào)處理程序竣灌，那么就執(zhí)行進(jìn)程诫隅，如果沒(méi)有注冊(cè)，將采用默認(rèn)處理的方式帐偎。

管道 pipe

Linux 系統(tǒng)中的進(jìn)程可以通過(guò)建立管道 pipe 進(jìn)行通信

在兩個(gè)進(jìn)程之間逐纬，可以建立一個(gè)通道，一個(gè)進(jìn)程向這個(gè)通道里寫入字節(jié)流削樊，另一個(gè)進(jìn)程從這個(gè)管道中讀取字節(jié)流豁生。管道是同步的兔毒，當(dāng)進(jìn)程嘗試從空管道讀取數(shù)據(jù)時(shí)，該進(jìn)程會(huì)被阻塞甸箱，直到有可用數(shù)據(jù)為止育叁。shell 中的管線 pipelines?就是用管道實(shí)現(xiàn)的，當(dāng) shell 發(fā)現(xiàn)輸出

sort <f | head

它會(huì)創(chuàng)建兩個(gè)進(jìn)程芍殖，一個(gè)是 sort豪嗽，一個(gè)是 head，sort豌骏，會(huì)在這兩個(gè)應(yīng)用程序之間建立一個(gè)管道使得 sort 進(jìn)程的標(biāo)準(zhǔn)輸出作為 head 程序的標(biāo)準(zhǔn)輸入龟梦。sort 進(jìn)程產(chǎn)生的輸出就不用寫到文件中了，如果管道滿了系統(tǒng)會(huì)停止 sort 以等待 head 讀出數(shù)據(jù)

管道實(shí)際上就是?|窃躲，兩個(gè)應(yīng)用程序不知道有管道的存在计贰，一切都是由 shell 管理和控制的。

共享內(nèi)存 shared memory

兩個(gè)進(jìn)程之間還可以通過(guò)共享內(nèi)存進(jìn)行進(jìn)程間通信蒂窒，其中兩個(gè)或者多個(gè)進(jìn)程可以訪問(wèn)公共內(nèi)存空間躁倒。兩個(gè)進(jìn)程的共享工作是通過(guò)共享內(nèi)存完成的，一個(gè)進(jìn)程所作的修改可以對(duì)另一個(gè)進(jìn)程可見(jiàn)(很像線程間的通信)洒琢。

在使用共享內(nèi)存前秧秉，需要經(jīng)過(guò)一系列的調(diào)用流程，流程如下

• 創(chuàng)建共享內(nèi)存段或者使用已創(chuàng)建的共享內(nèi)存段(shmget())
• 將進(jìn)程附加到已經(jīng)創(chuàng)建的內(nèi)存段中(shmat())
• 從已連接的共享內(nèi)存段分離進(jìn)程(shmdt())
• 對(duì)共享內(nèi)存段執(zhí)行控制操作(shmctl())

先入先出隊(duì)列 FIFO

先入先出隊(duì)列 FIFO 通常被稱為?命名管道(Named Pipes)衰抑，命名管道的工作方式與常規(guī)管道非常相似象迎，但是確實(shí)有一些明顯的區(qū)別。未命名的管道沒(méi)有備份文件：操作系統(tǒng)負(fù)責(zé)維護(hù)內(nèi)存中的緩沖區(qū)停士，用來(lái)將字節(jié)從寫入器傳輸?shù)阶x取器挖帘。一旦寫入或者輸出終止的話完丽，緩沖區(qū)將被回收恋技，傳輸?shù)臄?shù)據(jù)會(huì)丟失。相比之下逻族，命名管道具有支持文件和獨(dú)特 API 蜻底，命名管道在文件系統(tǒng)中作為設(shè)備的專用文件存在。當(dāng)所有的進(jìn)程通信完成后聘鳞，命名管道將保留在文件系統(tǒng)中以備后用薄辅。命名管道具有嚴(yán)格的 FIFO 行為

寫入的第一個(gè)字節(jié)是讀取的第一個(gè)字節(jié)，寫入的第二個(gè)字節(jié)是讀取的第二個(gè)字節(jié)抠璃，依此類推站楚。

消息隊(duì)列 Message Queue

一聽(tīng)到消息隊(duì)列這個(gè)名詞你可能不知道是什么意思，消息隊(duì)列是用來(lái)描述內(nèi)核尋址空間內(nèi)的內(nèi)部鏈接列表搏嗡×海可以按幾種不同的方式將消息按順序發(fā)送到隊(duì)列并從隊(duì)列中檢索消息拉一。每個(gè)消息隊(duì)列由 IPC 標(biāo)識(shí)符唯一標(biāo)識(shí)。消息隊(duì)列有兩種模式旧乞，一種是嚴(yán)格模式蔚润， 嚴(yán)格模式就像是 FIFO 先入先出隊(duì)列似的，消息順序發(fā)送尺栖，順序讀取嫡纠。還有一種模式是?非嚴(yán)格模式，消息的順序性不是非常重要延赌。

套接字 Socket

還有一種管理兩個(gè)進(jìn)程間通信的是使用?socket除盏，socket 提供端到端的雙相通信。一個(gè)套接字可以與一個(gè)或多個(gè)進(jìn)程關(guān)聯(lián)皮胡。就像管道有命令管道和未命名管道一樣痴颊，套接字也有兩種模式，套接字一般用于兩個(gè)進(jìn)程之間的網(wǎng)絡(luò)通信屡贺，網(wǎng)絡(luò)套接字需要來(lái)自諸如TCP（傳輸控制協(xié)議）或較低級(jí)別UDP（用戶數(shù)據(jù)報(bào)協(xié)議）等基礎(chǔ)協(xié)議的支持蠢棱。

套接字有以下幾種分類

• 順序包套接字(Sequential Packet Socket)： 此類套接字為最大長(zhǎng)度固定的數(shù)據(jù)報(bào)提供可靠的連接。此連接是雙向的并且是順序的甩栈。
• 數(shù)據(jù)報(bào)套接字(Datagram Socket)：數(shù)據(jù)包套接字支持雙向數(shù)據(jù)流泻仙。數(shù)據(jù)包套接字接受消息的順序與發(fā)送者可能不同。
• 流式套接字(Stream Socket)：流套接字的工作方式類似于電話對(duì)話量没，提供雙向可靠的數(shù)據(jù)流玉转。
• 原始套接字(Raw Socket)： 可以使用原始套接字訪問(wèn)基礎(chǔ)通信協(xié)議。

調(diào)度

當(dāng)一個(gè)計(jì)算機(jī)是多道程序設(shè)計(jì)系統(tǒng)時(shí)殴蹄，會(huì)頻繁的有很多進(jìn)程或者線程來(lái)同時(shí)競(jìng)爭(zhēng) CPU 時(shí)間片究抓。當(dāng)兩個(gè)或兩個(gè)以上的進(jìn)程/線程處于就緒狀態(tài)時(shí)，就會(huì)發(fā)生這種情況袭灯。如果只有一個(gè) CPU 可用刺下，那么必須選擇接下來(lái)哪個(gè)進(jìn)程/線程可以運(yùn)行。操作系統(tǒng)中有一個(gè)叫做?調(diào)度程序(scheduler)?的角色存在稽荧，它就是做這件事兒的橘茉，該程序使用的算法叫做?調(diào)度算法(scheduling algorithm)?。

調(diào)度算法的分類

毫無(wú)疑問(wèn)姨丈，不同的環(huán)境下需要不同的調(diào)度算法畅卓。之所以出現(xiàn)這種情況，是因?yàn)椴煌膽?yīng)用程序和不同的操作系統(tǒng)有不同的目標(biāo)蟋恬。也就是說(shuō)翁潘，在不同的系統(tǒng)中，調(diào)度程序的優(yōu)化也是不同的歼争。這里有必要?jiǎng)澐殖鋈N環(huán)境

• 批處理(Batch)?: 商業(yè)領(lǐng)域
• 交互式(Interactive)： 交互式用戶環(huán)境
• 實(shí)時(shí)(Real time)

批處理中的調(diào)度

現(xiàn)在讓我們把目光從一般性的調(diào)度轉(zhuǎn)換為特定的調(diào)度算法拜马。下面我們會(huì)探討在批處理中的調(diào)度箱歧。

先來(lái)先服務(wù)

最簡(jiǎn)單的非搶占式調(diào)度算法的設(shè)計(jì)就是?先來(lái)先服務(wù)(first-come,first-serverd)。當(dāng)?shù)谝粋€(gè)任務(wù)從外部進(jìn)入系統(tǒng)時(shí)一膨，將會(huì)立即啟動(dòng)并允許運(yùn)行任意長(zhǎng)的時(shí)間呀邢。它不會(huì)因?yàn)檫\(yùn)行時(shí)間太長(zhǎng)而中斷。當(dāng)其他作業(yè)進(jìn)入時(shí)豹绪，它們排到就緒隊(duì)列尾部价淌。當(dāng)正在運(yùn)行的進(jìn)程阻塞，處于等待隊(duì)列的第一個(gè)進(jìn)程就開(kāi)始運(yùn)行瞒津。當(dāng)一個(gè)阻塞的進(jìn)程重新處于就緒態(tài)時(shí)蝉衣，它會(huì)像一個(gè)新到達(dá)的任務(wù)，會(huì)排在隊(duì)列的末尾巷蚪，即排在所有進(jìn)程最后病毡。

這個(gè)算法的強(qiáng)大之處在于易于理解和編程，在這個(gè)算法中屁柏，一個(gè)單鏈表記錄了所有就緒進(jìn)程啦膜。要選取一個(gè)進(jìn)程運(yùn)行，只要從該隊(duì)列的頭部移走一個(gè)進(jìn)程即可淌喻；要添加一個(gè)新的作業(yè)或者阻塞一個(gè)進(jìn)程僧家，只要把這個(gè)作業(yè)或進(jìn)程附加在隊(duì)列的末尾即可。這是很簡(jiǎn)單的一種實(shí)現(xiàn)裸删。

最短作業(yè)優(yōu)先

批處理中八拱，第二種調(diào)度算法是?最短作業(yè)優(yōu)先(Shortest Job First)，我們假設(shè)運(yùn)行時(shí)間已知涯塔。例如肌稻，一家保險(xiǎn)公司，因?yàn)槊刻煲鲱愃频墓ぷ髫拜匀藗兛梢韵喈?dāng)精確地預(yù)測(cè)處理 1000 個(gè)索賠的一批作業(yè)需要多長(zhǎng)時(shí)間爹谭。當(dāng)輸入隊(duì)列中有若干個(gè)同等重要的作業(yè)被啟動(dòng)時(shí)，調(diào)度程序應(yīng)使用最短優(yōu)先作業(yè)算法

需要注意的是每聪，在所有的進(jìn)程都可以運(yùn)行的情況下旦棉，最短作業(yè)優(yōu)先的算法才是最優(yōu)的齿风。

最短剩余時(shí)間優(yōu)先

最短作業(yè)優(yōu)先的搶占式版本被稱作為?最短剩余時(shí)間優(yōu)先(Shortest Remaining Time Next)?算法药薯。使用這個(gè)算法，調(diào)度程序總是選擇剩余運(yùn)行時(shí)間最短的那個(gè)進(jìn)程運(yùn)行救斑。

交互式系統(tǒng)中的調(diào)度

交互式系統(tǒng)中在個(gè)人計(jì)算機(jī)童本、服務(wù)器和其他系統(tǒng)中都是很常用的，所以有必要來(lái)探討一下交互式調(diào)度

輪詢調(diào)度

一種最古老脸候、最簡(jiǎn)單穷娱、最公平并且最廣泛使用的算法就是?輪詢算法(round-robin)绑蔫。每個(gè)進(jìn)程都會(huì)被分配一個(gè)時(shí)間段，稱為時(shí)間片(quantum)泵额，在這個(gè)時(shí)間片內(nèi)允許進(jìn)程運(yùn)行配深。如果時(shí)間片結(jié)束時(shí)進(jìn)程還在運(yùn)行的話，則搶占一個(gè) CPU 并將其分配給另一個(gè)進(jìn)程嫁盲。如果進(jìn)程在時(shí)間片結(jié)束前阻塞或結(jié)束篓叶，則 CPU 立即進(jìn)行切換。輪詢算法比較容易實(shí)現(xiàn)羞秤。調(diào)度程序所做的就是維護(hù)一個(gè)可運(yùn)行進(jìn)程的列表缸托，就像下圖中的 a，當(dāng)一個(gè)進(jìn)程用完時(shí)間片后就被移到隊(duì)列的末尾瘾蛋，就像下圖的 b俐镐。

優(yōu)先級(jí)調(diào)度

輪詢調(diào)度假設(shè)了所有的進(jìn)程是同等重要的。但事實(shí)情況可能不是這樣哺哼。例如佩抹，在一所大學(xué)中的等級(jí)制度，首先是院長(zhǎng)取董，然后是教授匹摇、秘書(shū)、后勤人員甲葬，最后是學(xué)生廊勃。這種將外部情況考慮在內(nèi)就實(shí)現(xiàn)了優(yōu)先級(jí)調(diào)度(priority scheduling)

它的基本思想很明確，每個(gè)進(jìn)程都被賦予一個(gè)優(yōu)先級(jí)经窖，優(yōu)先級(jí)高的進(jìn)程優(yōu)先運(yùn)行坡垫。

多級(jí)隊(duì)列

最早使用優(yōu)先級(jí)調(diào)度的系統(tǒng)是?CTSS(Compatible TimeSharing System)。CTSS 在每次切換前都需要將當(dāng)前進(jìn)程換出到磁盤画侣，并從磁盤上讀入一個(gè)新進(jìn)程冰悠。為 CPU 密集型進(jìn)程設(shè)置較長(zhǎng)的時(shí)間片比頻繁地分給他們很短的時(shí)間要更有效（減少交換次數(shù)）。另一方面配乱，如前所述溉卓，長(zhǎng)時(shí)間片的進(jìn)程又會(huì)影響到響應(yīng)時(shí)間，解決辦法是設(shè)置優(yōu)先級(jí)類搬泥。屬于最高優(yōu)先級(jí)的進(jìn)程運(yùn)行一個(gè)時(shí)間片桑寨，次高優(yōu)先級(jí)進(jìn)程運(yùn)行 2 個(gè)時(shí)間片，再下面一級(jí)運(yùn)行 4 個(gè)時(shí)間片忿檩，以此類推尉尾。當(dāng)一個(gè)進(jìn)程用完分配的時(shí)間片后，它被移到下一類燥透。

最短進(jìn)程優(yōu)先

最短進(jìn)程優(yōu)先是根據(jù)進(jìn)程過(guò)去的行為進(jìn)行推測(cè)沙咏，并執(zhí)行估計(jì)運(yùn)行時(shí)間最短的那一個(gè)辨图。假設(shè)每個(gè)終端上每條命令的預(yù)估運(yùn)行時(shí)間為?T0，現(xiàn)在假設(shè)測(cè)量到其下一次運(yùn)行時(shí)間為?T1肢藐，可以用兩個(gè)值的加權(quán)來(lái)改進(jìn)估計(jì)時(shí)間故河，即aT0+ (1- 1)T1。通過(guò)選擇 a 的值吆豹，可以決定是盡快忘掉老的運(yùn)行時(shí)間忧勿，還是在一段長(zhǎng)時(shí)間內(nèi)始終記住它們。當(dāng) a = 1/2 時(shí)瞻讽，可以得到下面這個(gè)序列


可以看到鸳吸，在三輪過(guò)后，T0 在新的估計(jì)值中所占比重下降至 1/8速勇。

保證調(diào)度

一種完全不同的調(diào)度方法是對(duì)用戶做出明確的性能保證晌砾。一種實(shí)際而且容易實(shí)現(xiàn)的保證是：若用戶工作時(shí)有 n 個(gè)用戶登錄，則每個(gè)用戶將獲得 CPU 處理能力的 1/n烦磁。類似地养匈，在一個(gè)有 n 個(gè)進(jìn)程運(yùn)行的單用戶系統(tǒng)中，若所有的進(jìn)程都等價(jià)都伪，則每個(gè)進(jìn)程將獲得 1/n 的 CPU 時(shí)間呕乎。

彩票調(diào)度

對(duì)用戶進(jìn)行承諾并在隨后兌現(xiàn)承諾是一件好事，不過(guò)很難實(shí)現(xiàn)陨晶。但是存在著一種簡(jiǎn)單的方式猬仁，有一種既可以給出預(yù)測(cè)結(jié)果而又有一種比較簡(jiǎn)單的實(shí)現(xiàn)方式的算法，就是?彩票調(diào)度(lottery scheduling)算法先誉。

其基本思想是為進(jìn)程提供各種系統(tǒng)資源（例如 CPU 時(shí)間）的彩票湿刽。當(dāng)做出一個(gè)調(diào)度決策的時(shí)候，就隨機(jī)抽出一張彩票褐耳，擁有彩票的進(jìn)程將獲得該資源诈闺。在應(yīng)用到 CPU 調(diào)度時(shí)，系統(tǒng)可以每秒持有 50 次抽獎(jiǎng)铃芦，每個(gè)中獎(jiǎng)?wù)邔@得比如 20 毫秒的 CPU 時(shí)間作為獎(jiǎng)勵(lì)雅镊。

公平分享調(diào)度

到目前為止，我們假設(shè)被調(diào)度的都是各個(gè)進(jìn)程自身刃滓，而不用考慮該進(jìn)程的擁有者是誰(shuí)仁烹。結(jié)果是，如果用戶 1 啟動(dòng)了 9 個(gè)進(jìn)程注盈，而用戶 2 啟動(dòng)了一個(gè)進(jìn)程晃危，使用輪轉(zhuǎn)或相同優(yōu)先級(jí)調(diào)度算法叙赚，那么用戶 1 將得到 90 % 的 CPU 時(shí)間老客，而用戶 2 將之得到 10 % 的 CPU 時(shí)間僚饭。

為了阻止這種情況的出現(xiàn)，一些系統(tǒng)在調(diào)度前會(huì)把進(jìn)程的擁有者考慮在內(nèi)胧砰。在這種模型下鳍鸵，每個(gè)用戶都會(huì)分配一些CPU 時(shí)間，而調(diào)度程序會(huì)選擇進(jìn)程并強(qiáng)制執(zhí)行尉间。因此如果兩個(gè)用戶每個(gè)都會(huì)有 50% 的 CPU 時(shí)間片保證偿乖，那么無(wú)論一個(gè)用戶有多少個(gè)進(jìn)程，都將獲得相同的 CPU 份額哲嘲。

實(shí)時(shí)系統(tǒng)中的調(diào)度

實(shí)時(shí)系統(tǒng)(real-time)?是一個(gè)時(shí)間扮演了重要作用的系統(tǒng)贪薪。實(shí)時(shí)系統(tǒng)可以分為兩類，硬實(shí)時(shí)(hard real time)?和?軟實(shí)時(shí)(soft real time)?系統(tǒng)眠副，前者意味著必須要滿足絕對(duì)的截止時(shí)間画切；后者的含義是雖然不希望偶爾錯(cuò)失截止時(shí)間，但是可以容忍囱怕。

實(shí)時(shí)系統(tǒng)中的事件可以按照響應(yīng)方式進(jìn)一步分類為周期性(以規(guī)則的時(shí)間間隔發(fā)生)事件或?非周期性(發(fā)生時(shí)間不可預(yù)知)事件霍弹。一個(gè)系統(tǒng)可能要響應(yīng)多個(gè)周期性事件流，根據(jù)每個(gè)事件處理所需的時(shí)間娃弓，可能甚至無(wú)法處理所有事件典格。例如，如果有 m 個(gè)周期事件台丛，事件 i 以周期 Pi 發(fā)生耍缴，并需要 Ci 秒 CPU 時(shí)間處理一個(gè)事件，那么可以處理負(fù)載的條件是

只有滿足這個(gè)條件的實(shí)時(shí)系統(tǒng)稱為可調(diào)度的挽霉，這意味著它實(shí)際上能夠被實(shí)現(xiàn)私恬。一個(gè)不滿足此檢驗(yàn)標(biāo)準(zhǔn)的進(jìn)程不能被調(diào)度，因?yàn)檫@些進(jìn)程共同需要的 CPU 時(shí)間總和大于 CPU 能提供的時(shí)間炼吴。

下面我們來(lái)了解一下內(nèi)存管理本鸣，你需要知道的知識(shí)點(diǎn)如下

地址空間

如果要使多個(gè)應(yīng)用程序同時(shí)運(yùn)行在內(nèi)存中，必須要解決兩個(gè)問(wèn)題：保護(hù)和?重定位硅蹦。第一種解決方式是用保護(hù)密鑰標(biāo)記內(nèi)存塊荣德，并將執(zhí)行過(guò)程的密鑰與提取的每個(gè)存儲(chǔ)字的密鑰進(jìn)行比較淹真。這種方式只能解決第一種問(wèn)題（破壞操作系統(tǒng)）瓦阐，但是不能解決多進(jìn)程在內(nèi)存中同時(shí)運(yùn)行的問(wèn)題。

還有一種更好的方式是創(chuàng)造一個(gè)存儲(chǔ)器抽象：地址空間(the address space)胶台。就像進(jìn)程的概念創(chuàng)建了一種抽象的 CPU 來(lái)運(yùn)行程序假褪，地址空間也創(chuàng)建了一種抽象內(nèi)存供程序使用署咽。

基址寄存器和變址寄存器

最簡(jiǎn)單的辦法是使用動(dòng)態(tài)重定位(dynamic relocation)技術(shù)，它就是通過(guò)一種簡(jiǎn)單的方式將每個(gè)進(jìn)程的地址空間映射到物理內(nèi)存的不同區(qū)域。還有一種方式是使用基址寄存器和變址寄存器宁否。

• 基址寄存器：存儲(chǔ)數(shù)據(jù)內(nèi)存的起始位置
• 變址寄存器：存儲(chǔ)應(yīng)用程序的長(zhǎng)度窒升。

每當(dāng)進(jìn)程引用內(nèi)存以獲取指令或讀取、寫入數(shù)據(jù)時(shí)慕匠，CPU 都會(huì)自動(dòng)將基址值添加到進(jìn)程生成的地址中饱须，然后再將其發(fā)送到內(nèi)存總線上。同時(shí)台谊，它檢查程序提供的地址是否大于或等于變址寄存器?中的值蓉媳。如果程序提供的地址要超過(guò)變址寄存器的范圍，那么會(huì)產(chǎn)生錯(cuò)誤并中止訪問(wèn)锅铅。

交換技術(shù)

在程序運(yùn)行過(guò)程中酪呻，經(jīng)常會(huì)出現(xiàn)內(nèi)存不足的問(wèn)題。

針對(duì)上面內(nèi)存不足的問(wèn)題盐须，提出了兩種處理方式：最簡(jiǎn)單的一種方式就是交換(swapping)技術(shù)号杠，即把一個(gè)進(jìn)程完整的調(diào)入內(nèi)存，然后再內(nèi)存中運(yùn)行一段時(shí)間丰歌，再把它放回磁盤姨蟋。空閑進(jìn)程會(huì)存儲(chǔ)在磁盤中立帖，所以這些進(jìn)程在沒(méi)有運(yùn)行時(shí)不會(huì)占用太多內(nèi)存眼溶。另外一種策略叫做虛擬內(nèi)存(virtual memory)，虛擬內(nèi)存技術(shù)能夠允許應(yīng)用程序部分的運(yùn)行在內(nèi)存中晓勇。下面我們首先先探討一下交換

交換過(guò)程

下面是一個(gè)交換過(guò)程

剛開(kāi)始的時(shí)候堂飞，只有進(jìn)程 A 在內(nèi)存中，然后從創(chuàng)建進(jìn)程 B 和進(jìn)程 C 或者從磁盤中把它們換入內(nèi)存绑咱，然后在圖 d 中绰筛，A 被換出內(nèi)存到磁盤中，最后 A 重新進(jìn)來(lái)描融。因?yàn)閳D g 中的進(jìn)程 A 現(xiàn)在到了不同的位置铝噩，所以在裝載過(guò)程中需要被重新定位，或者在交換程序時(shí)通過(guò)軟件來(lái)執(zhí)行窿克；或者在程序執(zhí)行期間通過(guò)硬件來(lái)重定位骏庸。基址寄存器和變址寄存器就適用于這種情況年叮。

交換在內(nèi)存創(chuàng)建了多個(gè)?空閑區(qū)(hole)具被，內(nèi)存會(huì)把所有的空閑區(qū)盡可能向下移動(dòng)合并成為一個(gè)大的空閑區(qū)。這項(xiàng)技術(shù)稱為內(nèi)存緊縮(memory compaction)只损。但是這項(xiàng)技術(shù)通常不會(huì)使用一姿，因?yàn)檫@項(xiàng)技術(shù)會(huì)消耗很多 CPU 時(shí)間。

空閑內(nèi)存管理

在進(jìn)行內(nèi)存動(dòng)態(tài)分配時(shí)，操作系統(tǒng)必須對(duì)其進(jìn)行管理叮叹。大致上說(shuō)艾栋，有兩種監(jiān)控內(nèi)存使用的方式

• 位圖(bitmap)
• 空閑列表(free lists)

使用位圖的存儲(chǔ)管理

使用位圖方法時(shí)，內(nèi)存可能被劃分為小到幾個(gè)字或大到幾千字節(jié)的分配單元衬横。每個(gè)分配單元對(duì)應(yīng)于位圖中的一位裹粤，0 表示空閑终蒂， 1 表示占用（或者相反）蜂林。一塊內(nèi)存區(qū)域和其對(duì)應(yīng)的位圖如下

位圖提供了一種簡(jiǎn)單的方法在固定大小的內(nèi)存中跟蹤內(nèi)存的使用情況，因?yàn)?strong>位圖的大小取決于內(nèi)存和分配單元的大小拇泣。這種方法有一個(gè)問(wèn)題是噪叙，當(dāng)決定為把具有 k 個(gè)分配單元的進(jìn)程放入內(nèi)存時(shí)，內(nèi)容管理器(memory manager)?必須搜索位圖霉翔，在位圖中找出能夠運(yùn)行 k 個(gè)連續(xù) 0 位的串睁蕾。在位圖中找出制定長(zhǎng)度的連續(xù) 0 串是一個(gè)很耗時(shí)的操作，這是位圖的缺點(diǎn)债朵。（可以簡(jiǎn)單理解為在雜亂無(wú)章的數(shù)組中子眶，找出具有一大長(zhǎng)串空閑的數(shù)組單元）

使用鏈表進(jìn)行管理

另一種記錄內(nèi)存使用情況的方法是，維護(hù)一個(gè)記錄已分配內(nèi)存段和空閑內(nèi)存段的鏈表序芦，段會(huì)包含進(jìn)程或者是兩個(gè)進(jìn)程的空閑區(qū)域臭杰。可用上面的圖 c?來(lái)表示內(nèi)存的使用情況谚中。鏈表中的每一項(xiàng)都可以代表一個(gè)?空閑區(qū)(H)?或者是進(jìn)程(P)的起始標(biāo)志渴杆，長(zhǎng)度和下一個(gè)鏈表項(xiàng)的位置。

當(dāng)按照地址順序在鏈表中存放進(jìn)程和空閑區(qū)時(shí)宪塔，有幾種算法可以為創(chuàng)建的進(jìn)程（或者從磁盤中換入的進(jìn)程）分配內(nèi)存磁奖。我們先假設(shè)內(nèi)存管理器知道應(yīng)該分配多少內(nèi)存，最簡(jiǎn)單的算法是使用?首次適配(first fit)某筐。內(nèi)存管理器會(huì)沿著段列表進(jìn)行掃描比搭，直到找個(gè)一個(gè)足夠大的空閑區(qū)為止。 除非空閑區(qū)大小和要分配的空間大小一樣南誊，否則將空閑區(qū)分為兩部分敢辩，一部分供進(jìn)程使用；一部分生成新的空閑區(qū)弟疆。首次適配算法是一種速度很快的算法戚长，因?yàn)樗鼤?huì)盡可能的搜索鏈表。

首次適配的一個(gè)小的變體是?下次適配(next fit)怠苔。它和首次匹配的工作方式相同同廉，只有一個(gè)不同之處那就是下次適配在每次找到合適的空閑區(qū)時(shí)就會(huì)記錄當(dāng)時(shí)的位置，以便下次尋找空閑區(qū)時(shí)從上次結(jié)束的地方開(kāi)始搜索，而不是像首次匹配算法那樣每次都會(huì)從頭開(kāi)始搜索迫肖。

另外一個(gè)著名的并且廣泛使用的算法是?最佳適配(best fit)锅劝。最佳適配會(huì)從頭到尾尋找整個(gè)鏈表，找出能夠容納進(jìn)程的最小空閑區(qū)蟆湖。

虛擬內(nèi)存

盡管基址寄存器和變址寄存器用來(lái)創(chuàng)建地址空間的抽象故爵，但是這有一個(gè)其他的問(wèn)題需要解決：管理軟件的不斷增大(managing bloatware)。虛擬內(nèi)存的基本思想是隅津，每個(gè)程序都有自己的地址空間诬垂，這個(gè)地址空間被劃分為多個(gè)稱為頁(yè)面(page)的塊。每一頁(yè)都是連續(xù)的地址范圍伦仍。這些頁(yè)被映射到物理內(nèi)存结窘，但并不是所有的頁(yè)都必須在內(nèi)存中才能運(yùn)行程序。當(dāng)程序引用到一部分在物理內(nèi)存中的地址空間時(shí)充蓝，硬件會(huì)立刻執(zhí)行必要的映射隧枫。當(dāng)程序引用到一部分不在物理內(nèi)存中的地址空間時(shí)，由操作系統(tǒng)負(fù)責(zé)將缺失的部分裝入物理內(nèi)存并重新執(zhí)行失敗的指令谓苟。

分頁(yè)

大部分使用虛擬內(nèi)存的系統(tǒng)中都會(huì)使用一種?分頁(yè)(paging)?技術(shù)官脓。在任何一臺(tái)計(jì)算機(jī)上，程序會(huì)引用使用一組內(nèi)存地址涝焙。當(dāng)程序執(zhí)行

MOV REG,1000

這條指令時(shí)卑笨，它會(huì)把內(nèi)存地址為 1000 的內(nèi)存單元的內(nèi)容復(fù)制到 REG 中（或者相反，這取決于計(jì)算機(jī)）纱皆。地址可以通過(guò)索引湾趾、基址寄存器、段寄存器或其他方式產(chǎn)生派草。

這些程序生成的地址被稱為?虛擬地址(virtual addresses)?并形成虛擬地址空間(virtual address space)搀缠，在沒(méi)有虛擬內(nèi)存的計(jì)算機(jī)上，系統(tǒng)直接將虛擬地址送到內(nèi)存中線上近迁，讀寫操作都使用同樣地址的物理內(nèi)存艺普。在使用虛擬內(nèi)存時(shí)，虛擬地址不會(huì)直接發(fā)送到內(nèi)存總線上鉴竭。相反歧譬，會(huì)使用?MMU(Memory Management Unit)?內(nèi)存管理單元把虛擬地址映射為物理內(nèi)存地址，像下圖這樣

下面這幅圖展示了這種映射是如何工作的

頁(yè)表給出虛擬地址與物理內(nèi)存地址之間的映射關(guān)系搏存。每一頁(yè)起始于 4096 的倍數(shù)位置瑰步，結(jié)束于 4095 的位置，所以 4K 到 8K 實(shí)際為 4096 - 8191 璧眠，8K - 12K 就是 8192 - 12287

在這個(gè)例子中缩焦，我們可能有一個(gè) 16 位地址的計(jì)算機(jī)读虏，地址從 0 - 64 K - 1，這些是虛擬地址袁滥。然而只有 32 KB 的物理地址盖桥。所以雖然可以編寫 64 KB 的程序，但是程序無(wú)法全部調(diào)入內(nèi)存運(yùn)行题翻，在磁盤上必須有一個(gè)最多 64 KB 的程序核心映像的完整副本揩徊，以保證程序片段在需要時(shí)被調(diào)入內(nèi)存。

頁(yè)表

虛擬頁(yè)號(hào)可作為頁(yè)表的索引用來(lái)找到虛擬頁(yè)中的內(nèi)容嵌赠。由頁(yè)表項(xiàng)可以找到頁(yè)框號(hào)（如果有的話）塑荒。然后把頁(yè)框號(hào)拼接到偏移量的高位端，以替換掉虛擬頁(yè)號(hào)猾普，形成物理地址袜炕。

因此本谜，頁(yè)表的目的是把虛擬頁(yè)映射到頁(yè)框中初家。從數(shù)學(xué)上說(shuō)，頁(yè)表是一個(gè)函數(shù)乌助，它的參數(shù)是虛擬頁(yè)號(hào)溜在，結(jié)果是物理頁(yè)框號(hào)。

通過(guò)這個(gè)函數(shù)可以把虛擬地址中的虛擬頁(yè)轉(zhuǎn)換為頁(yè)框他托，從而形成物理地址掖肋。

頁(yè)表項(xiàng)的結(jié)構(gòu)

下面我們探討一下頁(yè)表項(xiàng)的具體結(jié)構(gòu)，上面你知道了頁(yè)表項(xiàng)的大致構(gòu)成赏参，是由頁(yè)框號(hào)和在/不在位構(gòu)成的志笼，現(xiàn)在我們來(lái)具體探討一下頁(yè)表項(xiàng)的構(gòu)成

頁(yè)表項(xiàng)的結(jié)構(gòu)是與機(jī)器相關(guān)的，但是不同機(jī)器上的頁(yè)表項(xiàng)大致相同把篓。上面是一個(gè)頁(yè)表項(xiàng)的構(gòu)成纫溃，不同計(jì)算機(jī)的頁(yè)表項(xiàng)可能不同，但是一般來(lái)說(shuō)都是 32 位的韧掩。頁(yè)表項(xiàng)中最重要的字段就是頁(yè)框號(hào)(Page frame number)紊浩。畢竟，頁(yè)表到頁(yè)框最重要的一步操作就是要把此值映射過(guò)去疗锐。下一個(gè)比較重要的就是在/不在位坊谁，如果此位上的值是 1，那么頁(yè)表項(xiàng)是有效的并且能夠被使用滑臊。如果此值是 0 的話口芍，則表示該頁(yè)表項(xiàng)對(duì)應(yīng)的虛擬頁(yè)面不在內(nèi)存中，訪問(wèn)該頁(yè)面會(huì)引起一個(gè)缺頁(yè)異常(page fault)雇卷。

保護(hù)位(Protection)?告訴我們哪一種訪問(wèn)是允許的鬓椭，啥意思呢虹钮？最簡(jiǎn)單的表示形式是這個(gè)域只有一位，0 表示可讀可寫膘融，1 表示的是只讀芙粱。

修改位(Modified)?和?訪問(wèn)位(Referenced)?會(huì)跟蹤頁(yè)面的使用情況。當(dāng)一個(gè)頁(yè)面被寫入時(shí)氧映，硬件會(huì)自動(dòng)的設(shè)置修改位春畔。修改位在頁(yè)面重新分配頁(yè)框時(shí)很有用。如果一個(gè)頁(yè)面已經(jīng)被修改過(guò)（即它是?臟?的）岛都，則必須把它寫回磁盤律姨。如果一個(gè)頁(yè)面沒(méi)有被修改過(guò)（即它是?干凈的），那么重新分配時(shí)這個(gè)頁(yè)框會(huì)被直接丟棄臼疫，因?yàn)榇疟P上的副本仍然是有效的择份。這個(gè)位有時(shí)也叫做?臟位(dirty bit)，因?yàn)樗从沉隧?yè)面的狀態(tài)烫堤。

訪問(wèn)位(Referenced)?在頁(yè)面被訪問(wèn)時(shí)被設(shè)置荣赶，不管是讀還是寫。這個(gè)值能夠幫助操作系統(tǒng)在發(fā)生缺頁(yè)中斷時(shí)選擇要淘汰的頁(yè)鸽斟。不再使用的頁(yè)要比正在使用的頁(yè)更適合被淘汰拔创。這個(gè)位在后面要討論的頁(yè)面置換算法中作用很大。

最后一位用于禁止該頁(yè)面被高速緩存富蓄，這個(gè)功能對(duì)于映射到設(shè)備寄存器還是內(nèi)存中起到了關(guān)鍵作用剩燥。通過(guò)這一位可以禁用高速緩存。具有獨(dú)立的 I/O 空間而不是用內(nèi)存映射 I/O 的機(jī)器來(lái)說(shuō)立倍，并不需要這一位灭红。

頁(yè)面置換算法

下面我們就來(lái)探討一下有哪些頁(yè)面置換算法。

最優(yōu)頁(yè)面置換算法

最優(yōu)的頁(yè)面置換算法的工作流程如下：在缺頁(yè)中斷發(fā)生時(shí)口注，這些頁(yè)面之一將在下一條指令（包含該指令的頁(yè)面）上被引用变擒。其他頁(yè)面則可能要到 10、100 或者 1000 條指令后才會(huì)被訪問(wèn)疆导。每個(gè)頁(yè)面都可以用在該頁(yè)首次被訪問(wèn)前所要執(zhí)行的指令數(shù)作為標(biāo)記赁项。

最優(yōu)化的頁(yè)面算法表明應(yīng)該標(biāo)記最大的頁(yè)面。如果一個(gè)頁(yè)面在 800 萬(wàn)條指令內(nèi)不會(huì)被使用澈段，另外一個(gè)頁(yè)面在 600 萬(wàn)條指令內(nèi)不會(huì)被使用悠菜，則置換前一個(gè)頁(yè)面，從而把需要調(diào)入這個(gè)頁(yè)面而發(fā)生的缺頁(yè)中斷推遲败富。計(jì)算機(jī)也像人類一樣悔醋，會(huì)把不愿意做的事情盡可能的往后拖。

這個(gè)算法最大的問(wèn)題時(shí)無(wú)法實(shí)現(xiàn)兽叮。當(dāng)缺頁(yè)中斷發(fā)生時(shí)芬骄，操作系統(tǒng)無(wú)法知道各個(gè)頁(yè)面的下一次將在什么時(shí)候被訪問(wèn)猾愿。這種算法在實(shí)際過(guò)程中根本不會(huì)使用。

最近未使用頁(yè)面置換算法

為了能夠讓操作系統(tǒng)收集頁(yè)面使用信息账阻，大部分使用虛擬地址的計(jì)算機(jī)都有兩個(gè)狀態(tài)位蒂秘，R 和 M，來(lái)和每個(gè)頁(yè)面進(jìn)行關(guān)聯(lián)淘太。每當(dāng)引用頁(yè)面（讀入或?qū)懭耄r(shí)都設(shè)置 R姻僧，寫入（即修改）頁(yè)面時(shí)設(shè)置 M，這些位包含在每個(gè)頁(yè)表項(xiàng)中蒲牧，就像下面所示

因?yàn)槊看卧L問(wèn)時(shí)都會(huì)更新這些位撇贺，因此由硬件來(lái)設(shè)置它們非常重要。一旦某個(gè)位被設(shè)置為 1冰抢，就會(huì)一直保持 1 直到操作系統(tǒng)下次來(lái)修改此位松嘶。

如果硬件沒(méi)有這些位，那么可以使用操作系統(tǒng)的缺頁(yè)中斷和時(shí)鐘中斷機(jī)制來(lái)進(jìn)行模擬挎扰。當(dāng)啟動(dòng)一個(gè)進(jìn)程時(shí)翠订，將其所有的頁(yè)面都標(biāo)記為不在內(nèi)存；一旦訪問(wèn)任何一個(gè)頁(yè)面就會(huì)引發(fā)一次缺頁(yè)中斷鼓鲁，此時(shí)操作系統(tǒng)就可以設(shè)置?R 位(在它的內(nèi)部表中)蕴轨，修改頁(yè)表項(xiàng)使其指向正確的頁(yè)面港谊，并設(shè)置為?READ ONLY?模式骇吭，然后重新啟動(dòng)引起缺頁(yè)中斷的指令。如果頁(yè)面隨后被修改歧寺，就會(huì)發(fā)生另一個(gè)缺頁(yè)異常燥狰。從而允許操作系統(tǒng)設(shè)置 M 位并把頁(yè)面的模式設(shè)置為?READ/WRITE。

可以用 R 位和 M 位來(lái)構(gòu)造一個(gè)簡(jiǎn)單的頁(yè)面置換算法：當(dāng)啟動(dòng)一個(gè)進(jìn)程時(shí)斜筐，操作系統(tǒng)將其所有頁(yè)面的兩個(gè)位都設(shè)置為 0龙致。R 位定期的被清零（在每個(gè)時(shí)鐘中斷）。用來(lái)將最近未引用的頁(yè)面和已引用的頁(yè)面分開(kāi)顷链。

當(dāng)出現(xiàn)缺頁(yè)中斷后目代，操作系統(tǒng)會(huì)檢查所有的頁(yè)面，并根據(jù)它們的 R 位和 M 位將當(dāng)前值分為四類：

• 第 0 類：沒(méi)有引用 R嗤练，沒(méi)有修改 M
• 第 1 類：沒(méi)有引用 R榛了，已修改 M
• 第 2 類：引用 R ，沒(méi)有修改 M
• 第 3 類：已被訪問(wèn) R煞抬，已被修改 M

盡管看起來(lái)好像無(wú)法實(shí)現(xiàn)第一類頁(yè)面霜大，但是當(dāng)?shù)谌愴?yè)面的 R 位被時(shí)鐘中斷清除時(shí)，它們就會(huì)發(fā)生革答。時(shí)鐘中斷不會(huì)清除 M 位战坤，因?yàn)樾枰@個(gè)信息才能知道是否寫回磁盤中曙强。清除 R 但不清除 M 會(huì)導(dǎo)致出現(xiàn)一類頁(yè)面。

NRU(Not Recently Used)?算法從編號(hào)最小的非空類中隨機(jī)刪除一個(gè)頁(yè)面途茫。此算法隱含的思想是碟嘴，在一個(gè)時(shí)鐘內(nèi)（約 20 ms）淘汰一個(gè)已修改但是沒(méi)有被訪問(wèn)的頁(yè)面要比一個(gè)大量引用的未修改頁(yè)面好，NRU 的主要優(yōu)點(diǎn)是易于理解并且能夠有效的實(shí)現(xiàn)囊卜。

先進(jìn)先出頁(yè)面置換算法

另一種開(kāi)銷較小的方式是使用?FIFO(First-In,First-Out)?算法臀防，這種類型的數(shù)據(jù)結(jié)構(gòu)也適用在頁(yè)面置換算法中。由操作系統(tǒng)維護(hù)一個(gè)所有在當(dāng)前內(nèi)存中的頁(yè)面的鏈表边败，最早進(jìn)入的放在表頭袱衷，最新進(jìn)入的頁(yè)面放在表尾。在發(fā)生缺頁(yè)異常時(shí)笑窜，會(huì)把頭部的頁(yè)移除并且把新的頁(yè)添加到表尾致燥。

第二次機(jī)會(huì)頁(yè)面置換算法

我們上面學(xué)到的 FIFO 鏈表頁(yè)面有個(gè)缺陷，那就是出鏈和入鏈并不會(huì)進(jìn)行 check?檢查排截，這樣就會(huì)容易把經(jīng)常使用的頁(yè)面置換出去嫌蚤，為了避免這一問(wèn)題，我們對(duì)該算法做一個(gè)簡(jiǎn)單的修改：我們檢查最老頁(yè)面的?R 位断傲，如果是 0 脱吱，那么這個(gè)頁(yè)面就是最老的而且沒(méi)有被使用，那么這個(gè)頁(yè)面就會(huì)被立刻換出认罩。如果 R 位是 1箱蝠，那么就清除此位，此頁(yè)面會(huì)被放在鏈表的尾部垦垂，修改它的裝入時(shí)間就像剛放進(jìn)來(lái)的一樣宦搬。然后繼續(xù)搜索。

這種算法叫做?第二次機(jī)會(huì)(second chance)算法劫拗，就像下面這樣间校，我們看到頁(yè)面 A 到 H 保留在鏈表中，并按到達(dá)內(nèi)存的時(shí)間排序页慷。

a）按照先進(jìn)先出的方法排列的頁(yè)面憔足；b）在時(shí)刻 20 處發(fā)生缺頁(yè)異常中斷并且 A 的 R 位已經(jīng)設(shè)置時(shí)的頁(yè)面鏈表。

假設(shè)缺頁(yè)異常發(fā)生在時(shí)刻 20 處酒繁，這時(shí)最老的頁(yè)面是 A 滓彰，它是在 0 時(shí)刻到達(dá)的。如果 A 的 R 位是 0欲逃，那么它將被淘汰出內(nèi)存找蜜，或者把它寫回磁盤（如果它已經(jīng)被修改過(guò)），或者只是簡(jiǎn)單的放棄（如果它是未被修改過(guò)）稳析。另一方面洗做，如果它的 R 位已經(jīng)設(shè)置了弓叛，則將 A 放到鏈表的尾部并且重新設(shè)置裝入時(shí)間為當(dāng)前時(shí)刻（20 處），然后清除 R 位诚纸。然后從 B 頁(yè)面開(kāi)始繼續(xù)搜索合適的頁(yè)面撰筷。

尋找第二次機(jī)會(huì)的是在最近的時(shí)鐘間隔中未被訪問(wèn)過(guò)的頁(yè)面。如果所有的頁(yè)面都被訪問(wèn)過(guò)畦徘，該算法就會(huì)被簡(jiǎn)化為單純的?FIFO 算法毕籽。具體來(lái)說(shuō)，假設(shè)圖 a 中所有頁(yè)面都設(shè)置了 R 位井辆。操作系統(tǒng)將頁(yè)面依次移到鏈表末尾关筒，每次都在添加到末尾時(shí)清除 R 位。最后杯缺，算法又會(huì)回到頁(yè)面 A蒸播，此時(shí)的 R 位已經(jīng)被清除，那么頁(yè)面 A 就會(huì)被執(zhí)行出鏈處理萍肆，因此算法能夠正常結(jié)束袍榆。

時(shí)鐘頁(yè)面置換算法

一種比較好的方式是把所有的頁(yè)面都保存在一個(gè)類似鐘面的環(huán)形鏈表中，一個(gè)表針指向最老的頁(yè)面塘揣。如下圖所示

當(dāng)缺頁(yè)錯(cuò)誤出現(xiàn)時(shí)包雀，算法首先檢查表針指向的頁(yè)面，如果它的 R 位是 0 就淘汰該頁(yè)面亲铡，并把新的頁(yè)面插入到這個(gè)位置才写，然后把表針向前移動(dòng)一位；如果 R 位是 1 就清除 R 位并把表針前移一個(gè)位置奴愉。重復(fù)這個(gè)過(guò)程直到找到了一個(gè) R 位為 0 的頁(yè)面位置琅摩。了解這個(gè)算法的工作方式，就明白為什么它被稱為?時(shí)鐘(clokc)算法了锭硼。

最近最少使用頁(yè)面置換算法

在前面幾條指令中頻繁使用的頁(yè)面和可能在后面的幾條指令中被使用。反過(guò)來(lái)說(shuō)蜕劝，已經(jīng)很久沒(méi)有使用的頁(yè)面有可能在未來(lái)一段時(shí)間內(nèi)仍不會(huì)被使用檀头。這個(gè)思想揭示了一個(gè)可以實(shí)現(xiàn)的算法：在缺頁(yè)中斷時(shí)，置換未使用時(shí)間最長(zhǎng)的頁(yè)面岖沛。這個(gè)策略稱為?LRU(Least Recently Used)?暑始，最近最少使用頁(yè)面置換算法。

雖然 LRU 在理論上是可以實(shí)現(xiàn)的婴削，但是從長(zhǎng)遠(yuǎn)看來(lái)代價(jià)比較高廊镜。為了完全實(shí)現(xiàn) LRU，會(huì)在內(nèi)存中維護(hù)一個(gè)所有頁(yè)面的鏈表唉俗，最頻繁使用的頁(yè)位于表頭嗤朴，最近最少使用的頁(yè)位于表尾配椭。困難的是在每次內(nèi)存引用時(shí)更新整個(gè)鏈表。在鏈表中找到一個(gè)頁(yè)面雹姊，刪除它股缸，然后把它移動(dòng)到表頭是一個(gè)非常耗時(shí)的操作，即使使用硬件來(lái)實(shí)現(xiàn)也是一樣的費(fèi)時(shí)吱雏。

用軟件模擬 LRU

盡管上面的 LRU 算法在原則上是可以實(shí)現(xiàn)的敦姻，但是很少有機(jī)器能夠擁有那些特殊的硬件。上面是硬件的實(shí)現(xiàn)方式歧杏，那么現(xiàn)在考慮要用軟件來(lái)實(shí)現(xiàn) LRU 镰惦。一種可以實(shí)現(xiàn)的方案是?NFU(Not Frequently Used，最不常用)算法犬绒。它需要一個(gè)軟件計(jì)數(shù)器來(lái)和每個(gè)頁(yè)面關(guān)聯(lián)陨献，初始化的時(shí)候是 0 。在每個(gè)時(shí)鐘中斷時(shí)懂更，操作系統(tǒng)會(huì)瀏覽內(nèi)存中的所有頁(yè)眨业，會(huì)將每個(gè)頁(yè)面的 R 位（0 或 1）加到它的計(jì)數(shù)器上。這個(gè)計(jì)數(shù)器大體上跟蹤了各個(gè)頁(yè)面訪問(wèn)的頻繁程度沮协。當(dāng)缺頁(yè)異常出現(xiàn)時(shí)龄捡，則置換計(jì)數(shù)器值最小的頁(yè)面。

只需要對(duì) NFU 做一個(gè)簡(jiǎn)單的修改就可以讓它模擬 LRU慷暂，這個(gè)修改有兩個(gè)步驟

• 首先聘殖，在 R 位被添加進(jìn)來(lái)之前先把計(jì)數(shù)器右移一位；
• 第二步行瑞，R 位被添加到最左邊的位而不是最右邊的位奸腺。

修改以后的算法稱為?老化(aging)?算法，下圖解釋了老化算法是如何工作的血久。

我們假設(shè)在第一個(gè)時(shí)鐘周期內(nèi)頁(yè)面 0 - 5 的 R 位依次是 1突照，0，1氧吐，0讹蘑，1，1筑舅，（也就是頁(yè)面 0 是 1座慰，頁(yè)面 1 是 0，頁(yè)面 2 是 1 這樣類推）翠拣。也就是說(shuō)版仔，在 0 個(gè)時(shí)鐘周期到 1 個(gè)時(shí)鐘周期之間，0，2蛮粮，4益缎，5 都被引用了，從而把它們的 R 位設(shè)置為 1蝉揍，剩下的設(shè)置為 0 链峭。在相關(guān)的六個(gè)計(jì)數(shù)器被右移之后 R 位被添加到?左側(cè)?，就像上圖中的 a又沾。剩下的四列顯示了接下來(lái)的四個(gè)時(shí)鐘周期內(nèi)的六個(gè)計(jì)數(shù)器變化弊仪。

CPU正在以某個(gè)頻率前進(jìn)，該頻率的周期稱為時(shí)鐘滴答或時(shí)鐘周期杖刷。一個(gè) 100Mhz 的處理器每秒將接收100,000,000個(gè)時(shí)鐘滴答励饵。

當(dāng)缺頁(yè)異常出現(xiàn)時(shí)，將置換（就是移除）計(jì)數(shù)器值最小的頁(yè)面滑燃。如果一個(gè)頁(yè)面在前面 4 個(gè)時(shí)鐘周期內(nèi)都沒(méi)有被訪問(wèn)過(guò)役听，那么它的計(jì)數(shù)器應(yīng)該會(huì)有四個(gè)連續(xù)的 0 ，因此它的值肯定要比前面 3 個(gè)時(shí)鐘周期內(nèi)都沒(méi)有被訪問(wèn)過(guò)的頁(yè)面的計(jì)數(shù)器小表窘。

這個(gè)算法與 LRU 算法有兩個(gè)重要的區(qū)別：看一下上圖中的?e典予，第三列和第五列

工作集時(shí)鐘頁(yè)面置換算法

當(dāng)缺頁(yè)異常發(fā)生后，需要掃描整個(gè)頁(yè)表才能確定被淘汰的頁(yè)面乐严，因此基本工作集算法還是比較浪費(fèi)時(shí)間的瘤袖。一個(gè)對(duì)基本工作集算法的提升是基于時(shí)鐘算法但是卻使用工作集的信息，這種算法稱為WSClock(工作集時(shí)鐘)昂验。由于它的實(shí)現(xiàn)簡(jiǎn)單并且具有高性能捂敌，因此在實(shí)踐中被廣泛應(yīng)用。

與時(shí)鐘算法一樣既琴，所需的數(shù)據(jù)結(jié)構(gòu)是一個(gè)以頁(yè)框?yàn)樵氐难h(huán)列表占婉，就像下面這樣

工作集時(shí)鐘頁(yè)面置換算法的操作：a) 和 b) 給出 R = 1 時(shí)所發(fā)生的情形；c) 和 d) 給出 R = 0 的例子

最初的時(shí)候甫恩，該表是空的逆济。當(dāng)裝入第一個(gè)頁(yè)面后，把它加載到該表中填物。隨著更多的頁(yè)面的加入纹腌，它們形成一個(gè)環(huán)形結(jié)構(gòu)。每個(gè)表項(xiàng)包含來(lái)自基本工作集算法的上次使用時(shí)間滞磺，以及 R 位（已標(biāo)明）和 M 位（未標(biāo)明）。

與時(shí)鐘算法一樣莱褒，在每個(gè)缺頁(yè)異常時(shí)击困，首先檢查指針指向的頁(yè)面。如果 R 位被是設(shè)置為 1，該頁(yè)面在當(dāng)前時(shí)鐘周期內(nèi)就被使用過(guò)阅茶，那么該頁(yè)面就不適合被淘汰蛛枚。然后把該頁(yè)面的 R 位置為 0，指針指向下一個(gè)頁(yè)面脸哀，并重復(fù)該算法蹦浦。該事件序列化后的狀態(tài)參見(jiàn)圖 b。

現(xiàn)在考慮指針指向的頁(yè)面 R = 0 時(shí)會(huì)發(fā)生什么撞蜂，參見(jiàn)圖 c盲镶，如果頁(yè)面的使用期限大于 t 并且頁(yè)面為被訪問(wèn)過(guò)，那么這個(gè)頁(yè)面就不會(huì)在工作集中蝌诡，并且在磁盤上會(huì)有一個(gè)此頁(yè)面的副本溉贿。申請(qǐng)重新調(diào)入一個(gè)新的頁(yè)面，并把新的頁(yè)面放在其中浦旱，如圖 d 所示宇色。另一方面，如果頁(yè)面被修改過(guò)颁湖，就不能重新申請(qǐng)頁(yè)面宣蠕，因?yàn)檫@個(gè)頁(yè)面在磁盤上沒(méi)有有效的副本。為了避免由于調(diào)度寫磁盤操作引起的進(jìn)程切換甥捺，指針繼續(xù)向前走抢蚀，算法繼續(xù)對(duì)下一個(gè)頁(yè)面進(jìn)行操作。畢竟涎永，有可能存在一個(gè)老的思币，沒(méi)有被修改過(guò)的頁(yè)面可以立即使用。

原則上來(lái)說(shuō)羡微，所有的頁(yè)面都有可能因?yàn)榇疟PI/O?在某個(gè)時(shí)鐘周期內(nèi)被調(diào)度谷饿。為了降低磁盤阻塞，需要設(shè)置一個(gè)限制妈倔，即最大只允許寫回 n 個(gè)頁(yè)面博投。一旦達(dá)到該限制，就不允許調(diào)度新的寫操作盯蝴。

那么就有個(gè)問(wèn)題毅哗，指針會(huì)繞一圈回到原點(diǎn)的，如果回到原點(diǎn)捧挺，它的起始點(diǎn)會(huì)發(fā)生什么虑绵？這里有兩種情況：

• 至少調(diào)度了一次寫操作
• 沒(méi)有調(diào)度過(guò)寫操作

在第一種情況中，指針僅僅是不停的移動(dòng)闽烙，尋找一個(gè)未被修改過(guò)的頁(yè)面翅睛。由于已經(jīng)調(diào)度了一個(gè)或者多個(gè)寫操作，最終會(huì)有某個(gè)寫操作完成盛垦，它的頁(yè)面會(huì)被標(biāo)記為未修改芹枷。置換遇到的第一個(gè)未被修改過(guò)的頁(yè)面，這個(gè)頁(yè)面不一定是第一個(gè)被調(diào)度寫操作的頁(yè)面讶泰，因?yàn)橛脖P驅(qū)動(dòng)程序?yàn)榱藘?yōu)化性能可能會(huì)把寫操作重排序扎酷。

對(duì)于第二種情況檐涝，所有的頁(yè)面都在工作集中，否則將至少調(diào)度了一個(gè)寫操作法挨。由于缺乏額外的信息谁榜，最簡(jiǎn)單的方法就是置換一個(gè)未被修改的頁(yè)面來(lái)使用，掃描中需要記錄未被修改的頁(yè)面的位置坷剧，如果不存在未被修改的頁(yè)面惰爬，就選定當(dāng)前頁(yè)面并把它寫回磁盤。

頁(yè)面置換算法小結(jié)

我們到現(xiàn)在已經(jīng)研究了各種頁(yè)面置換算法惫企，現(xiàn)在我們來(lái)一個(gè)簡(jiǎn)單的總結(jié)撕瞧，算法的總結(jié)歸納如下

算法注釋最優(yōu)算法不可實(shí)現(xiàn)，但可以用作基準(zhǔn)NRU(最近未使用) 算法和 LRU 算法很相似FIFO(先進(jìn)先出) 算法有可能會(huì)拋棄重要的頁(yè)面第二次機(jī)會(huì)算法比 FIFO 有較大的改善時(shí)鐘算法實(shí)際使用LRU(最近最少)算法比較優(yōu)秀狞尔，但是很難實(shí)現(xiàn)NFU(最不經(jīng)常食用)算法和 LRU 很類似老化算法近似 LRU 的高效算法工作集算法實(shí)施起來(lái)開(kāi)銷很大工作集時(shí)鐘算法比較有效的算法

• 最優(yōu)算法在當(dāng)前頁(yè)面中置換最后要訪問(wèn)的頁(yè)面丛版。不幸的是，沒(méi)有辦法來(lái)判定哪個(gè)頁(yè)面是最后一個(gè)要訪問(wèn)的偏序，因此實(shí)際上該算法不能使用页畦。然而，它可以作為衡量其他算法的標(biāo)準(zhǔn)研儒。

• NRU?算法根據(jù) R 位和 M 位的狀態(tài)將頁(yè)面氛圍四類豫缨。從編號(hào)最小的類別中隨機(jī)選擇一個(gè)頁(yè)面。NRU 算法易于實(shí)現(xiàn)端朵，但是性能不是很好好芭。存在更好的算法。

• FIFO?會(huì)跟蹤頁(yè)面加載進(jìn)入內(nèi)存中的順序冲呢，并把頁(yè)面放入一個(gè)鏈表中舍败。有可能刪除存在時(shí)間最長(zhǎng)但是還在使用的頁(yè)面，因此這個(gè)算法也不是一個(gè)很好的選擇敬拓。

• 第二次機(jī)會(huì)算法是對(duì) FIFO 的一個(gè)修改邻薯，它會(huì)在刪除頁(yè)面之前檢查這個(gè)頁(yè)面是否仍在使用。如果頁(yè)面正在使用乘凸，就會(huì)進(jìn)行保留厕诡。這個(gè)改進(jìn)大大提高了性能。

• 時(shí)鐘?算法是第二次機(jī)會(huì)算法的另外一種實(shí)現(xiàn)形式营勤，時(shí)鐘算法和第二次算法的性能差不多木人，但是會(huì)花費(fèi)更少的時(shí)間來(lái)執(zhí)行算法信柿。

• LRU?算法是一個(gè)非常優(yōu)秀的算法冀偶，但是沒(méi)有特殊的硬件(TLB)很難實(shí)現(xiàn)醒第。如果沒(méi)有硬件，就不能使用 LRU 算法进鸠。

• NFU?算法是一種近似于 LRU 的算法稠曼，它的性能不是非常好。

• 老化?算法是一種更接近 LRU 算法的實(shí)現(xiàn)客年，并且可以更好的實(shí)現(xiàn)霞幅，因此是一個(gè)很好的選擇

• 最后兩種算法都使用了工作集算法。工作集算法提供了合理的性能開(kāi)銷量瓜，但是它的實(shí)現(xiàn)比較復(fù)雜司恳。WSClock?是另外一種變體，它不僅能夠提供良好的性能绍傲，而且可以高效地實(shí)現(xiàn)扔傅。

總之，最好的算法是老化算法和WSClock算法烫饼。他們分別是基于 LRU 和工作集算法猎塞。他們都具有良好的性能并且能夠被有效的實(shí)現(xiàn)。還存在其他一些好的算法杠纵，但實(shí)際上這兩個(gè)可能是最重要的荠耽。

下面來(lái)聊一聊文件系統(tǒng)，你需要知道下面這些知識(shí)點(diǎn)

文件

文件命名

文件是一種抽象機(jī)制比藻，它提供了一種方式用來(lái)存儲(chǔ)信息以及在后面進(jìn)行讀取铝量。可能任何一種機(jī)制最重要的特性就是管理對(duì)象的命名方式银亲。在創(chuàng)建一個(gè)文件后慢叨，它會(huì)給文件一個(gè)命名。當(dāng)進(jìn)程終止時(shí)群凶，文件會(huì)繼續(xù)存在插爹，并且其他進(jìn)程可以使用名稱訪問(wèn)該文件。

文件命名規(guī)則對(duì)于不同的操作系統(tǒng)來(lái)說(shuō)是不一樣的请梢，但是所有現(xiàn)代操作系統(tǒng)都允許使用 1 - 8 個(gè)字母的字符串作為合法文件名赠尾。

某些文件區(qū)分大小寫字母，而大多數(shù)則不區(qū)分毅弧。UNIX?屬于第一類气嫁；歷史悠久的?MS-DOS?屬于第二類（順便說(shuō)一句，盡管 MS-DOS 歷史悠久够坐，但 MS-DOS 仍在嵌入式系統(tǒng)中非常廣泛地使用寸宵，因此它絕不是過(guò)時(shí)的）崖面；因此，UNIX 系統(tǒng)會(huì)有三種不同的命名文件：maria梯影、Maria巫员、MARIA?。在 MS-DOS 甲棍，所有這些命名都屬于相同的文件简识。