用戶線程的缺點(diǎn)：

• 資源調(diào)度按照進(jìn)程進(jìn)行（內(nèi)核只將處理器分配給進(jìn)程），多個(gè)處理機(jī)下，同一個(gè)進(jìn)程中的線程只能在同一個(gè)處理機(jī)下分時(shí)復(fù)用；
• 線程發(fā)生 I/O 或頁(yè)面故障引起的阻塞時(shí)，如果調(diào)用阻塞系統(tǒng)調(diào)用，則內(nèi)核由于不知道有線程的存在，而會(huì)阻塞整個(gè)進(jìn)程從而阻塞所有線程直到磁盤(pán) I/O 完成為止（盡管其他線程是可以運(yùn)行的），因此同一進(jìn)程中只能同時(shí)有一個(gè)線程在運(yùn)行；
• 一個(gè)單獨(dú)的進(jìn)程內(nèi)部，沒(méi)有時(shí)鐘中斷，所以不可能用輪轉(zhuǎn)調(diào)度的方式調(diào)度線程；

混合型線程

下圖說(shuō)明了用戶級(jí)與內(nèi)核級(jí)的組合實(shí)現(xiàn)方式, 在這種模型中，每個(gè)內(nèi)核級(jí)線程有一個(gè)可以輪流使用的用戶級(jí)線程集合：

image

線程創(chuàng)建在用戶空間完成，線程調(diào)度等在核心態(tài)完成。
多個(gè)用戶級(jí)線程多路復(fù)用多個(gè)內(nèi)核級(jí)線程。也就是說(shuō)，核外的用戶空間的線程通過(guò)一個(gè)機(jī)制和核內(nèi)的一個(gè)內(nèi)核級(jí)線程對(duì)應(yīng)起來(lái)，那么調(diào)度內(nèi)核的這個(gè)線程上CPU也就是調(diào)度核外的線程上的CPU。

用戶級(jí)線程和內(nèi)核級(jí)線程的區(qū)別

• 內(nèi)核支持線程是 OS 內(nèi)核可感知的，而用戶級(jí)線程是 OS 內(nèi)核不可感知的。
• 用戶級(jí)線程的創(chuàng)建、撤消和調(diào)度不需要 OS 內(nèi)核的支持，是在語(yǔ)言（如 Java）這一級(jí)處理的；而內(nèi)核支持線程的創(chuàng)建、撤消和調(diào)度都需 OS 內(nèi)核提供支持，而且與進(jìn)程的創(chuàng)建、撤消和調(diào)度大體是相同的。
• 用戶級(jí)線程執(zhí)行系統(tǒng)調(diào)用指令時(shí)將導(dǎo)致其所屬進(jìn)程被中斷，而內(nèi)核支持線程執(zhí)行系統(tǒng)調(diào)用指令時(shí)，只導(dǎo)致該線程被中斷。
• 在只有用戶級(jí)線程的系統(tǒng)內(nèi)，CPU 調(diào)度還是以進(jìn)程為單位，處于運(yùn)行狀態(tài)的進(jìn)程中的多個(gè)線程，由用戶程序控制線程的輪換運(yùn)行；在有內(nèi)核支持線程的系統(tǒng)內(nèi)，CPU 調(diào)度則以線程為單位，由 OS 的線程調(diào)度程序負(fù)責(zé)線程的調(diào)度。
• 用戶級(jí)線程的程序?qū)嶓w是運(yùn)行在用戶態(tài)下的程序，而內(nèi)核支持線程的程序?qū)嶓w則是可以運(yùn)行在任何狀態(tài)下的程序。

image

進(jìn)程與線程之間的關(guān)系

• 一個(gè)程序至少有一個(gè)進(jìn)程，一個(gè)線程只能屬于一個(gè)進(jìn)程，而一個(gè)進(jìn)程可以有多個(gè)線程，但至少有一個(gè)線程（通常說(shuō)的主線程）。
  線程的劃分尺度小于進(jìn)程，使得多線程程序的并發(fā)性高
• 資源分配給進(jìn)程，同一進(jìn)程的所有線程共享該進(jìn)程的所有資源。
• 線程在執(zhí)行過(guò)程中，需要協(xié)作同步。不同進(jìn)程的線程間要利用消息通信的辦法實(shí)現(xiàn)同步。
• 處理機(jī)分給線程，即真正在處理機(jī)上運(yùn)行的是線程。
• 線程是指進(jìn)程內(nèi)的一個(gè)執(zhí)行單元，也是進(jìn)程內(nèi)的可調(diào)度實(shí)體。

進(jìn)程與線程之間的區(qū)別

1. 調(diào)度：線程作為CPU調(diào)度和分配的基本單位，進(jìn)程作為資源分配的基本單位。把傳統(tǒng)進(jìn)程的兩個(gè)屬性分開(kāi)，線程便能輕裝運(yùn)行，從而可顯著地提高系統(tǒng)的并發(fā)程度。在同一進(jìn)程中，線程的切換不會(huì)引起進(jìn)程的切換；在由一個(gè)進(jìn)程中的線程切換到另一個(gè)進(jìn)程中的線程時(shí)，才會(huì)引起進(jìn)程的切換。
2. 并發(fā)性：在引入線程的操作系統(tǒng)中，不僅進(jìn)程之間可以并發(fā)執(zhí)行，同一個(gè)進(jìn)程的多個(gè)線程之間也可以并發(fā)執(zhí)行。因而使操作系統(tǒng)具有更好的并發(fā)性，從而能更有效地使用系統(tǒng)資源和提高系統(tǒng)吞吐量。
3. 擁有資源：進(jìn)程是擁有資源的一個(gè)獨(dú)立單位，它可以擁有自己的資源；而線程不擁有系統(tǒng)資源，只擁有一點(diǎn)在運(yùn)行中必不可少的資源（如程序計(jì)數(shù)器，一組寄存器和棧）
   ，但可以訪問(wèn)隸屬于同進(jìn)程擁有的全部資源。
   子進(jìn)程和父進(jìn)程有不同的代碼和數(shù)據(jù)空間，而多個(gè)線程則共享數(shù)據(jù)空間，每個(gè)線程有自己的執(zhí)行堆棧和程序計(jì)數(shù)器為其執(zhí)行上下文。
4. 系統(tǒng)開(kāi)銷：由于在創(chuàng)建或撤消進(jìn)程時(shí)，系統(tǒng)都要為之分配或回收資源，在進(jìn)程切換時(shí)，設(shè)計(jì)整個(gè)進(jìn)程當(dāng)前的CPU環(huán)境的保存以及新調(diào)度到進(jìn)程的CPU環(huán)境的設(shè)置，而線程切換只需保存和設(shè)置少量寄存器內(nèi)容，開(kāi)銷很小，而且進(jìn)程內(nèi)多個(gè)線程共享進(jìn)程地址空間、多線程之間的同步與通信非常容易實(shí)現(xiàn)，甚至無(wú)需操作系統(tǒng)干預(yù)。因此，操作系統(tǒng)所付出的開(kāi)銷將顯著地大于在創(chuàng)建或撤消線程時(shí)的開(kāi)銷。進(jìn)程切換的開(kāi)銷也遠(yuǎn)大于線程切換的開(kāi)銷。

處理器調(diào)度

實(shí)時(shí)操作系統(tǒng)主要的追求目標(biāo)：可靠性、及時(shí)響應(yīng)、快速處理。與追求系統(tǒng)的吞吐率、CPU 的利用效率無(wú)關(guān)。

進(jìn)程調(diào)度的方式

• 可搶占式（可剝奪式)：就緒隊(duì)列中一旦有某進(jìn)程的優(yōu)先級(jí)高于當(dāng)前正在執(zhí)行的進(jìn)程的優(yōu)先級(jí)時(shí)，操作系統(tǒng)便立即進(jìn)行進(jìn)程調(diào)度，完成進(jìn)程切換。
• 不可搶占式（不可剝奪式）：即使在就緒隊(duì)列存在有某進(jìn)程優(yōu)先級(jí)高于當(dāng)前正在執(zhí)行的進(jìn)程的優(yōu)先級(jí)時(shí)，當(dāng)前進(jìn)程仍將占用處理機(jī)執(zhí)行，直到該進(jìn)程自己進(jìn)入阻塞狀態(tài)，或時(shí)間片用完，或在執(zhí)行完系統(tǒng)調(diào)用后準(zhǔn)備返回用戶進(jìn)程前的時(shí)刻，才重新發(fā)生調(diào)度讓出處理機(jī)。

顯然，可搶占式調(diào)度可有效減少等待時(shí)間和響應(yīng)時(shí)間，但會(huì)帶來(lái)較大的其他管理開(kāi)銷，使得吞吐量等的性能指標(biāo)比不可搶占式調(diào)度要低。所以一般在桌面計(jì)算機(jī)中都支持可搶占式調(diào)度，使得用戶可以得到更好的人機(jī)交互體驗(yàn)，而在服務(wù)器領(lǐng)域不必非要可搶占式調(diào)度，而通常會(huì)采用不可搶占式調(diào)度，從而可提高系統(tǒng)的整體吞吐量。

處理器調(diào)度層次

• 高級(jí)調(diào)度：作業(yè)調(diào)度，本質(zhì)就是根據(jù)某種算法，把外存上的作業(yè)調(diào)入內(nèi)存，并為之創(chuàng)建進(jìn)程，掛入就緒隊(duì)列，分配處理機(jī)并執(zhí)行。執(zhí)行完后，回收資源。
  一般而言，批處理系統(tǒng)中才會(huì)有高級(jí)調(diào)度。
• 中級(jí)調(diào)度：交換調(diào)度，本質(zhì)就是讓暫時(shí)不能運(yùn)行的進(jìn)程掛起，釋放內(nèi)存資源，并把它們調(diào)到外存上去等待。
• 低級(jí)調(diào)度：進(jìn)程調(diào)度，本質(zhì)就是根據(jù)某種算法，把處理機(jī)分配給就緒進(jìn)程隊(duì)列中的某個(gè)進(jìn)程。
  進(jìn)程調(diào)度首先會(huì)保存處理機(jī)現(xiàn)場(chǎng)。將程序計(jì)數(shù)器等指定寄存器中的內(nèi)容保存到 PCB 中。然后將按照某種算法從就緒隊(duì)列中選取進(jìn)程，把處理機(jī)分配給進(jìn)程。最后，把指定進(jìn)程的 PCB 中的處理機(jī)現(xiàn)場(chǎng)信息恢復(fù)到處理機(jī)中，處理機(jī)分配給進(jìn)程執(zhí)行。

調(diào)度算法目標(biāo)

1）公平；2）保持系統(tǒng)素有部分盡可能忙碌；

• 批處理：1）吞吐量；2）周轉(zhuǎn)時(shí)間；3）CPU 利用率。
• 交互式：1）最小響應(yīng)時(shí)間；2）均衡性。
• 實(shí)時(shí)：1）滿足截止時(shí)間；2）可預(yù)測(cè)性。

調(diào)度算法（批處理、交互式、實(shí)時(shí)）

• 批處理系統(tǒng)
  • 先來(lái)先服務(wù)算法（FCFS)：不可搶占調(diào)度方式，優(yōu)點(diǎn)是公平，實(shí)現(xiàn)簡(jiǎn)單；缺點(diǎn)是不利于短作業(yè)。
  • 最短作業(yè)優(yōu)先算法（SJF）：不可搶占調(diào)度方式，有效地縮短進(jìn)程的平均周轉(zhuǎn)時(shí)間，提高系統(tǒng)的吞吐量，但不利于長(zhǎng)進(jìn)程的運(yùn)行。
  • 最短剩余時(shí)間優(yōu)先算法（SRTF）：可搶占調(diào)度方式
  • 最高響應(yīng)比優(yōu)先算法（HRRF）：介于先來(lái)先服務(wù)算法（只考慮了進(jìn)程的等待時(shí)間）與最短進(jìn)程優(yōu)先算法（只考慮了用戶估計(jì)的進(jìn)程的執(zhí)行時(shí)間）之間的一種折中算法。
    根據(jù) “響應(yīng)比 =（進(jìn)程執(zhí)行時(shí)間 + 進(jìn)程等待時(shí)間）/ 進(jìn)程執(zhí)行時(shí)間” 這個(gè)公式得到的響應(yīng)比來(lái)進(jìn)行調(diào)度。
    高響應(yīng)比優(yōu)先算法在等待時(shí)間相同的情況下，作業(yè)執(zhí)行的時(shí)間越短，響應(yīng)比越高，滿足段任務(wù)優(yōu)先，同時(shí)響應(yīng)比會(huì)隨著等待時(shí)間增加而變大，優(yōu)先級(jí)會(huì)提高，能夠避免饑餓現(xiàn)象。優(yōu)點(diǎn)是兼顧長(zhǎng)短作業(yè)，缺點(diǎn)是計(jì)算響應(yīng)比開(kāi)銷大，適用于批處理系統(tǒng)。
• 交互式系統(tǒng)
  • 優(yōu)先級(jí)調(diào)度算法（HPF）：在進(jìn)程等待隊(duì)列中選擇優(yōu)先級(jí)最高的來(lái)執(zhí)行。
  • 輪轉(zhuǎn)調(diào)度算法（RR）：搶占式調(diào)度，給每個(gè)進(jìn)程固定的執(zhí)行時(shí)間，根據(jù)進(jìn)程到達(dá)的先后順序讓進(jìn)程在單位時(shí)間片內(nèi)執(zhí)行，執(zhí)行完成后便調(diào)度下一個(gè)進(jìn)程執(zhí)行，時(shí)間片輪轉(zhuǎn)調(diào)度不考慮進(jìn)程等待時(shí)間和執(zhí)行時(shí)間。
  • 多級(jí)反饋隊(duì)列調(diào)度算法（MLFQ）：長(zhǎng)進(jìn)程無(wú)法長(zhǎng)期占用處理機(jī)，且系統(tǒng)的響應(yīng)時(shí)間會(huì)縮短，吞吐量也不錯(cuò)（前提是沒(méi)有頻繁的短進(jìn)程）。所以 MLFQ 調(diào)度算法是一種合適不同類型應(yīng)用特征的綜合進(jìn)程調(diào)度算法。
    優(yōu)點(diǎn)是兼顧長(zhǎng)短作業(yè)，有較好的響應(yīng)時(shí)間，可行性強(qiáng)，適用于各種作業(yè)環(huán)境；缺點(diǎn)是平均等待時(shí)間較長(zhǎng)，上下文切換較費(fèi)時(shí)。適用于分時(shí)系統(tǒng)。
• 實(shí)時(shí)調(diào)度
  • 硬實(shí)時(shí)（hard real time）調(diào)度：調(diào)度機(jī)制確保一個(gè)關(guān)鍵任務(wù)能在指定時(shí)間前完成
  • 軟實(shí)時(shí)（soft real time）調(diào)度：調(diào)度機(jī)制盡量給予關(guān)鍵任務(wù)最高優(yōu)先級(jí)，盡量在指定時(shí)間前完成

同步、通信與死鎖

進(jìn)程間通信 IPC

如何傳遞消息？
確保多個(gè)進(jìn)程在關(guān)鍵活動(dòng)時(shí)不會(huì)交叉
正確的順序

為什么進(jìn)程間要進(jìn)行通信

• 數(shù)據(jù)傳輸：一個(gè)進(jìn)程需要將它的數(shù)據(jù)發(fā)送給另一個(gè)進(jìn)程。
• 資源共享：多個(gè)進(jìn)程間共享同樣的資源。
• 通知事件：一個(gè)進(jìn)程需要向另一個(gè)或一組進(jìn)程發(fā)送消息。通知它們發(fā)送了某種事件。
• 進(jìn)程控制：有些進(jìn)程希望完全控制另一個(gè)進(jìn)程的執(zhí)行（如Debug進(jìn)程），此時(shí)控制進(jìn)程希望能夠攔截另一個(gè)進(jìn)程的所有操作，并能夠及時(shí)知道它的狀態(tài)改變。

進(jìn)程間的通信方式

每個(gè)進(jìn)程各自有不同的用戶地址空間，任何一個(gè)進(jìn)程的全局變量在另一個(gè)進(jìn)程中都看不到，所以進(jìn)程之間要交換數(shù)據(jù)必須通過(guò)內(nèi)核，在內(nèi)核中開(kāi)辟一塊緩沖區(qū)，進(jìn)程 1 把數(shù)據(jù)從用戶空間拷到內(nèi)核緩沖區(qū)，進(jìn)程 2 再?gòu)膬?nèi)核緩沖區(qū)把數(shù)據(jù)讀走，內(nèi)核提供的這種機(jī)制稱為進(jìn)程間通信（IPC，InterProcess Communication）。

進(jìn)程通信實(shí)質(zhì)上就是進(jìn)程中線程之間的通信。

進(jìn)程通信就是指進(jìn)程間的信息交換，交換信息可以使一個(gè)狀態(tài)，也可以是很多的 byte。進(jìn)程間同步互斥也存在信息的交換，因此也屬于是一種 IPC，屬于是低級(jí)通信。該低級(jí)通信存在的問(wèn)題：1）通信的數(shù)據(jù)量太少；2）通信對(duì)用戶不透明 (數(shù)據(jù)的傳遞或者同步互斥都需要程序員實(shí)現(xiàn))

高級(jí)通信機(jī)制：

• 信號(hào)(signal)通信機(jī)制：信號(hào)是一種比較復(fù)雜的通信方式，用于通知接收進(jìn)程某個(gè)事件已經(jīng)發(fā)生。只能發(fā)送單個(gè)信號(hào)而不能傳送數(shù)據(jù)。
• 管道(pipeline)通信機(jī)制
  • 匿名管道(pipe)：管道是一種半雙工的通信方式，數(shù)據(jù)只能單向流動(dòng)，需要雙向通信時(shí)需要建立起兩個(gè)管道；而且只能在具有親緣關(guān)系的進(jìn)程間（父子進(jìn)程關(guān)系）通信。
  • 命名管道(FIFO)：有名管道也是半雙工的通信方式，克服了管道沒(méi)有名字的限制，它允許無(wú)親緣關(guān)系進(jìn)程間的通信。
• 消息傳遞(message passing)通信機(jī)制：消息隊(duì)列是由消息的鏈表，存放在內(nèi)核中并由消息隊(duì)列標(biāo)識(shí)符標(biāo)識(shí)。有足夠權(quán)限的進(jìn)程可以向隊(duì)列中添加消息，被賦予讀權(quán)限的進(jìn)程則可以讀走隊(duì)列中的消息。消息隊(duì)列克服了信號(hào)傳遞信息少、管道只能承載無(wú)格式字節(jié)流以及緩沖區(qū)大小受限等缺點(diǎn)。
• 信號(hào)量(semaphore)通信機(jī)制：信號(hào)量是一個(gè)計(jì)數(shù)器，可以用來(lái)控制多個(gè)進(jìn)程對(duì)共享資源的訪問(wèn)。它常作為一種鎖機(jī)制，防止某進(jìn)程正在訪問(wèn)共享資源時(shí)，其他進(jìn)程也訪問(wèn)該資源。因此，主要作為進(jìn)程間以及同一進(jìn)程內(nèi)不同線程之間的同步手段。
• 共享內(nèi)存(shared memory)通信機(jī)制：共享內(nèi)存就是映射一段能被其他進(jìn)程所訪問(wèn)的內(nèi)存，這段共享內(nèi)存由一個(gè)進(jìn)程創(chuàng)建，但多個(gè)進(jìn)程都可以訪問(wèn)。共享內(nèi)存是最快的 IPC 方式，它是針對(duì)其他進(jìn)程間通信方式運(yùn)行效率低而專門設(shè)計(jì)的。它往往與其他通信機(jī)制，如信號(hào)兩，配合使用，來(lái)實(shí)現(xiàn)進(jìn)程間的同步和通信。
• 套接字(socket)通信機(jī)制：套解口也是一種進(jìn)程間通信機(jī)制，與其他通信機(jī)制不同的是，它可用于不同及其間的進(jìn)程通信。

進(jìn)程間通信 IPC (InterProcess Communication)

信號(hào)通信機(jī)制

信號(hào)機(jī)制是unix系統(tǒng)中最為古老的進(jìn)程間通信機(jī)制，很多條件可以產(chǎn)生一個(gè)信號(hào)：

• 當(dāng)用戶按某些鍵時(shí)，產(chǎn)生信號(hào)；
• 硬件異常產(chǎn)生信號(hào)，這些情況通常由硬件檢測(cè)到；
• 進(jìn)程用kill函數(shù)將信號(hào)發(fā)送給另一個(gè)進(jìn)程；
• 用戶可用kill命令將信號(hào)發(fā)送給其它進(jìn)程。

缺點(diǎn)：開(kāi)銷太大，發(fā)送進(jìn)程需要調(diào)用系統(tǒng)調(diào)用，這時(shí)核心會(huì)中斷接收進(jìn)程，且要管理它的堆棧、調(diào)用處理程序、恢復(fù)被中斷的接收信號(hào)進(jìn)程等。另外信號(hào)的數(shù)量受到限制，并且只能傳送有限的信息量，例如不能攜帶參數(shù)等，所以對(duì)于復(fù)雜的通信操作不適用。

管道通信機(jī)制

匿名管道通信

特點(diǎn)：

• 管道是半雙工的，數(shù)據(jù)只能向一個(gè)方向流動(dòng)；需要雙方通信時(shí)，需要建立起兩個(gè)管道；
• 只能在具有公共祖先的兩個(gè)進(jìn)程之間使用；
• 一個(gè)進(jìn)程向管道中寫(xiě)的內(nèi)容被管道另一端的進(jìn)程讀出。寫(xiě)入的內(nèi)容每次都添加在管道緩沖區(qū)的末尾，并且每次都是從緩沖區(qū)的頭部讀出數(shù)據(jù)。如果讀進(jìn)程不讀走管道緩沖區(qū)中的數(shù)據(jù)，那么寫(xiě)操作將阻塞。
• 管道內(nèi)部提供了同步機(jī)制

image

1. 父進(jìn)程調(diào)用 pipe 開(kāi)辟管道，得到兩個(gè)文件描述符指向管道的兩端。
2. 父進(jìn)程調(diào)用 fork 創(chuàng)建子進(jìn)程，那么子進(jìn)程也有兩個(gè)文件描述符指向同一管道。
3. 父進(jìn)程關(guān)閉管道寫(xiě)端，子進(jìn)程關(guān)閉管道讀端。子進(jìn)程可以往管道里寫(xiě)，父進(jìn)程可以從管道里讀，管道是用環(huán)形隊(duì)列實(shí)現(xiàn)的，數(shù)據(jù)從寫(xiě)端流入從讀端流出，這樣就實(shí)現(xiàn)了進(jìn)程間通信。

在 linux 下，管道被非常廣泛地使用，一般在編程中我們實(shí)現(xiàn)了 popen 等的應(yīng)用即可提供管道功能。而在命令行中使用地也非常多，| 就是最為典型的管道的應(yīng)用例子。shell 會(huì)為 | 符號(hào)兩側(cè)的命令各創(chuàng)建一個(gè)腳本，將左側(cè)的輸出管道與右側(cè)的輸入管道進(jìn)行連接，可以進(jìn)行單向管道通信。 比如我們使用 go env 來(lái)確認(rèn) go 語(yǔ)言的環(huán)境變量，然后使用 grep 從中確認(rèn)出 GOROOT 環(huán)境變量的值一般會(huì)如下這樣做：go env | grep GOROOT。
實(shí)現(xiàn)的過(guò)程其實(shí)是： go env 會(huì)啟動(dòng)一個(gè)進(jìn)程， 而 grep 命令也會(huì)產(chǎn)生一個(gè)進(jìn)程，grep 的進(jìn)程會(huì)在 go env 的標(biāo)準(zhǔn)輸出中進(jìn)行檢索 GOROOT 的行的信息然后顯示出來(lái)，而負(fù)責(zé)這兩個(gè)進(jìn)程間的通信的正是管道。 在 c 語(yǔ)言中，我們需要父進(jìn)程中進(jìn)行 fork 以及對(duì)父進(jìn)程的基本信息進(jìn)行處理，同時(shí)初期化連接的管道信息從而實(shí)現(xiàn)管道通信。接下來(lái)，我們來(lái)看一下在 go 語(yǔ)言中是如何實(shí)現(xiàn)的

命名管道

FIFO 是一種先進(jìn)先出的隊(duì)列。它類似于一個(gè)管道，只允許數(shù)據(jù)的單向流動(dòng)。每個(gè)FIFO 都有一個(gè)名字，允許不相關(guān)的進(jìn)程訪問(wèn)同一個(gè) FIFO。因此也成為命名管道。

命名管道 (NamedPipe) 是服務(wù)器進(jìn)程和一個(gè)或多個(gè)客戶進(jìn)程之間通信的單向或雙向管道。不同于匿名管道的是：命名管道可以在不相關(guān)的進(jìn)程之間和不同計(jì)算機(jī)之間使用，服務(wù)器建立命名管道時(shí)給它指定一個(gè)名字，任何進(jìn)程都可以通過(guò)該名字打開(kāi)管道的另一端，根據(jù)給定的權(quán)限和服務(wù)器進(jìn)程通信。命名管道提供了相對(duì)簡(jiǎn)單的編程接口，使通過(guò)網(wǎng)絡(luò)傳輸數(shù)據(jù)并不比同一計(jì)算機(jī)上兩進(jìn)程之間通信更困難，不過(guò)如果要同時(shí)和多個(gè)進(jìn)程通信它就力不從心了。

命名管道不同與管道只能在具有親緣關(guān)系的進(jìn)程間通信了。它提供了一個(gè)路徑名與之關(guān)聯(lián)，有了自己的傳輸格式。

命名管道和管道的不同之處還有一點(diǎn)是, 有名管道是個(gè)設(shè)備文件，存儲(chǔ)在文件系統(tǒng)中，沒(méi)有親緣關(guān)系的進(jìn)程也可以訪問(wèn)，但是它要按照先進(jìn)先出的原則讀取數(shù)據(jù)。同樣也是單雙工的。

消息傳遞通信機(jī)制

消息隊(duì)列實(shí)際上就是一個(gè)鏈表，而消息就是鏈表中具有特定格式和優(yōu)先級(jí)的記錄，對(duì)消息隊(duì)列有寫(xiě)權(quán)限的進(jìn)程可以根據(jù)一定規(guī)則在消息鏈表中添加消息，對(duì)消息隊(duì)列有讀權(quán)限的進(jìn)程則可以從消息隊(duì)列中獲得所需的信息。

在某個(gè)進(jìn)程往一個(gè)消息隊(duì)列寫(xiě)入消息之前，并不需要另外某個(gè)進(jìn)程在該隊(duì)列上等待消息的到達(dá)。這跟命名管道是不同的，對(duì)后者來(lái)說(shuō)，除非讀端已經(jīng)存在，否則寫(xiě)端的打開(kāi)管道操作會(huì)一直阻塞。此外，管道和命名管道都是隨進(jìn)程持續(xù)的，而消息隊(duì)列還有后面的信號(hào)量、共享內(nèi)存都是隨內(nèi)核持續(xù)的。也就是說(shuō)當(dāng)一個(gè)管道或 FIFO 的最后一次關(guān)閉發(fā)生時(shí)，仍在該管道或 FIFO 上的數(shù)據(jù)將被丟棄。而對(duì)于消息隊(duì)列來(lái)說(shuō)，除非內(nèi)核自舉或顯式刪除，否則其一直存在。

與命名管道相比，消息隊(duì)列的優(yōu)勢(shì)在于：

• 消息隊(duì)列可以獨(dú)立于發(fā)送和接收進(jìn)程而存在，從而消除了在同步命名管道的打開(kāi)和關(guān)閉時(shí)可能產(chǎn)生的困難。
• 同時(shí)通過(guò)發(fā)送消息還可以避免命名管道的同步和阻塞問(wèn)題，不需要由進(jìn)程自己來(lái)提供同步方法。
• 接收程序可以通過(guò)消息類型有選擇地接收數(shù)據(jù)，而不是像命名管道中那樣，只能默認(rèn)地接收。

信號(hào)量通信機(jī)制

為了防止出現(xiàn)因多個(gè)程序同時(shí)訪問(wèn)一個(gè)共享資源而引發(fā)的一系列問(wèn)題，我們需要一種方法，它可以通過(guò)生成并使用令牌來(lái)授權(quán)，在任一時(shí)刻只能有一個(gè)執(zhí)行線程訪問(wèn)代碼的臨界區(qū)域。而信號(hào)量就可以提供這樣的一種訪問(wèn)機(jī)制，讓一個(gè)臨界區(qū)同一時(shí)間只有一個(gè)線程在訪問(wèn)它，也就是說(shuō)信號(hào)量是用來(lái)協(xié)調(diào)進(jìn)程對(duì)共享資源的訪問(wèn)的。

信號(hào)量是一個(gè)特殊的變量，程序?qū)ζ湓L問(wèn)都是原子操作，且只允許對(duì)它進(jìn)行等待和發(fā)送操作，也即 P(sv) 和 V(sv)，他們的行為是這樣的：

• P(sv)：如果 sv 的值大于零，就給它減 1；如果它的值為零，就掛起該進(jìn)程的執(zhí)行；
• V(sv)：如果有其他進(jìn)程因等待 sv 而被掛起，就讓它恢復(fù)運(yùn)行，如果沒(méi)有進(jìn)程因等待 sv 而掛起，就給它加 1。

最簡(jiǎn)單的信號(hào)量是只能取 0 和 1 的變量，這也是信號(hào)量最常見(jiàn)的一種形式，叫做互斥信號(hào)量，可以取多個(gè)正整數(shù)的信號(hào)量被稱為通用信號(hào)量。

舉個(gè)例子來(lái)說(shuō)，如果兩個(gè)進(jìn)程共享互斥信號(hào)量 sv，一旦其中一個(gè)進(jìn)程執(zhí)行了 P(sv) 操作，它將得到信號(hào)量，并可以進(jìn)入臨界區(qū)，使 sv 減 1。而第二個(gè)進(jìn)程將被阻止進(jìn)入臨界區(qū)，因?yàn)楫?dāng)它試圖執(zhí)行 P(sv) 時(shí)，sv 為 0，它會(huì)被掛起以等待第一個(gè)進(jìn)程離開(kāi)臨界區(qū)域并執(zhí)行 V(sv) 釋放信號(hào)量，這時(shí)第二個(gè)進(jìn)程就可以恢復(fù)執(zhí)行。

共享內(nèi)存通信機(jī)制

共享內(nèi)存就是允許兩個(gè)不相關(guān)的進(jìn)程訪問(wèn)同一個(gè)邏輯內(nèi)存。共享內(nèi)存是在兩個(gè)正在運(yùn)行的進(jìn)程之間共享和傳遞數(shù)據(jù)的一種最有效的方式，不同進(jìn)程之間共享的內(nèi)存通常安排為同一段物理內(nèi)存。進(jìn)程可以將同一段共享內(nèi)存連接到它們自己的地址空間中，所有進(jìn)程都可以訪問(wèn)共享內(nèi)存中的地址，就好像它們是由用 C 語(yǔ)言函數(shù) malloc 分配的內(nèi)存一樣。而如果某個(gè)進(jìn)程向共享內(nèi)存寫(xiě)入數(shù)據(jù)，所做的改動(dòng)將立即影響到可以訪問(wèn)同一段共享內(nèi)存的任何其他進(jìn)程。

image

注意共享內(nèi)存并未提供同步機(jī)制，也就是說(shuō)，在第一個(gè)進(jìn)程結(jié)束對(duì)共享內(nèi)存的寫(xiě)操作之前，并無(wú)自動(dòng)機(jī)制可以阻止第二個(gè)進(jìn)程開(kāi)始對(duì)它進(jìn)行讀取。所以通常需要用其他的機(jī)制來(lái)同步對(duì)共享內(nèi)存的訪問(wèn)，例如前面說(shuō)到的信號(hào)量。

采用共享內(nèi)存通信的一個(gè)顯而易見(jiàn)的好處是效率高，因?yàn)檫M(jìn)程可以直接讀寫(xiě)內(nèi)存，而不需要任何數(shù)據(jù)的拷貝。對(duì)于像管道和消息隊(duì)列等通信方式，則需要在內(nèi)核和用戶空間進(jìn)行四次的數(shù)據(jù)拷貝，而共享內(nèi)存則只拷貝兩次數(shù)據(jù)：一次從輸入文件到共享內(nèi)存區(qū)，另一次從共享內(nèi)存區(qū)到輸出文件。

套接字通信機(jī)制

Socket 通信，不僅僅是一臺(tái)主機(jī)上的兩個(gè)進(jìn)程可以進(jìn)行通信，還可以讓處在因特網(wǎng)中的兩個(gè)進(jìn)程進(jìn)行通信。在兩個(gè)進(jìn)程進(jìn)行通信的時(shí)候，首先本地的進(jìn)程在運(yùn)行的時(shí)候會(huì)綁定一個(gè)端口，然后我們本地為該進(jìn)程生成一個(gè)緩沖區(qū)，返回一個(gè)值，即為 socket 作為對(duì)其進(jìn)行標(biāo)記，每當(dāng)本地進(jìn)程和遠(yuǎn)程一個(gè)進(jìn)程建立連接的時(shí)候，就會(huì)根據(jù)遠(yuǎn)程進(jìn)程的信息和本地進(jìn)程的信息生成一個(gè) socket，然后雙方借助于 socket 就可以進(jìn)行通信，運(yùn)輸層得到的數(shù)據(jù)寫(xiě)入 socket 標(biāo)志的緩沖區(qū)，然后在里面進(jìn)行相應(yīng)的操作之后將其提交給網(wǎng)絡(luò)層。相比其它的幾種處理方式，該中方式比較麻煩。多于服務(wù)端，通過(guò) listen 阻塞監(jiān)聽(tīng)，監(jiān)聽(tīng)到有連接請(qǐng)求，通過(guò) accept 函數(shù)得到一個(gè)本地與之對(duì)應(yīng)的緩沖區(qū)，然后創(chuàng)建一個(gè)進(jìn)程用來(lái)和該連接進(jìn)行交互，然后通過(guò) receive 來(lái)接收信息。

解決并發(fā)的方案

需要滿足 4 個(gè)條件：

• 空閑讓進(jìn)
• 忙則等待
• 有限等待
• 讓權(quán)等待（阻塞的進(jìn)程把 CPU 讓給其他進(jìn)程）

經(jīng)典的進(jìn)程同步問(wèn)題

生產(chǎn)者 - 消費(fèi)者問(wèn)題；哲學(xué)家進(jìn)餐問(wèn)題；讀者 - 寫(xiě)者問(wèn)題

死鎖

死鎖的概念

死鎖：當(dāng)某進(jìn)程提出資源申請(qǐng)后，使得系統(tǒng)中一些進(jìn)程處于無(wú)休止的阻塞狀態(tài)，在無(wú)外力作用下，永遠(yuǎn)不能再繼續(xù)前進(jìn)。

產(chǎn)生死鎖的根本原因：資源有限且操作不當(dāng)。

產(chǎn)生死鎖的必要條件

• 互斥條件：某段時(shí)間內(nèi)某資源只能由一個(gè)進(jìn)程使用。
• 占有和等待條件：進(jìn)程因請(qǐng)求資源而阻塞時(shí)，對(duì)已分配給它的資源保持不放。
• 不剝奪條件：資源在未使用完前，不能被剝奪，由使用進(jìn)程釋放。
• 循環(huán)等待條件：發(fā)生死鎖時(shí)，有向圖必構(gòu)成一環(huán)路。

解決死鎖的方法

死鎖防止：破壞四個(gè)條件
死鎖避免：銀行家算法
死鎖的檢測(cè)和恢復(fù)：死鎖檢測(cè)算法

死鎖例題

• 一個(gè)計(jì)算機(jī)有 6 臺(tái)可互換使用的磁帶機(jī)，由 n 個(gè)進(jìn)程競(jìng)爭(zhēng)使用，每一個(gè)進(jìn)程在一段時(shí)間內(nèi)需要獨(dú)占兩臺(tái)磁帶機(jī)進(jìn)行使用，n 最多為 5 時(shí)系統(tǒng)一定不會(huì)發(fā)生死鎖。

這種題的解法一般都是從最壞的角度出發(fā)：即假設(shè)有很多進(jìn)程來(lái)申請(qǐng)磁帶機(jī)，假設(shè)已經(jīng)有 5 個(gè)進(jìn)程，一個(gè)進(jìn)程申請(qǐng)了一個(gè)磁帶機(jī)，那么還剩下一個(gè)磁帶機(jī)，此時(shí)剛剛的 5 個(gè)進(jìn)程中的任意一個(gè)還可以再申請(qǐng)一個(gè)磁帶機(jī)即可滿足運(yùn)行條件。但是如果一開(kāi)始就有 6 個(gè)進(jìn)程，一個(gè)進(jìn)程申請(qǐng)一個(gè)磁帶機(jī)的話，那么就沒(méi)有剩下的磁帶機(jī)了，所以這時(shí)候誰(shuí)都不能運(yùn)行，所以，最多不能超過(guò) 5 個(gè)。

• 某系統(tǒng)中有 11 臺(tái)打印機(jī)，N 個(gè)進(jìn)程共享打印機(jī)資源，每個(gè)進(jìn)程要求 3 臺(tái)，當(dāng) N 不超過(guò) 5 時(shí)，系統(tǒng)不會(huì)發(fā)生死鎖。

思路和上面的一樣，考慮最壞的情況，有 5 個(gè)進(jìn)程均申請(qǐng)了 2 臺(tái)打印機(jī)，那么此時(shí) 5 個(gè)進(jìn)程中的任一進(jìn)程再申請(qǐng)一臺(tái)打印機(jī)即可正常運(yùn)行。但是如果 N=6，那么假設(shè)有 5 個(gè)進(jìn)程申請(qǐng)了 2 臺(tái)打印機(jī)，一個(gè)進(jìn)程申請(qǐng)了一臺(tái)打印機(jī)，此時(shí)已經(jīng)沒(méi)有剩余的打印機(jī)了，現(xiàn)在誰(shuí)都不能繼續(xù)運(yùn)行。

多道程序設(shè)計(jì)中，進(jìn)程間存在的制約關(guān)系有哪些？

同步：某一進(jìn)程收不到另一進(jìn)程給他的必要信息，就不能繼續(xù)運(yùn)行下去，這種制約關(guān)系源于進(jìn)程間的合作。 互斥：某一進(jìn)程要求使用某資源，而該資源正被另一進(jìn)程使用，并且這以資源不許兩進(jìn)程同時(shí)使用，那么進(jìn)程只好等占用資源進(jìn)程釋放資源后才能占有使用。

高級(jí)通信機(jī)制與低級(jí)通信機(jī)制PV操作的區(qū)別是什么？簡(jiǎn)述消息緩沖隊(duì)列的工作原理。

PV操作時(shí)指進(jìn)程之間通過(guò)共享變量實(shí)現(xiàn)信息傳遞；而高級(jí)通信機(jī)制是由系統(tǒng)提供發(fā)送（sender）與接收（receive）兩個(gè)操作，進(jìn)程間通過(guò)這兩個(gè)操作進(jìn)行通信，無(wú)需貢獻(xiàn)任何變量。基本原理：操作系統(tǒng)管理一個(gè)用于進(jìn)程通信的緩沖池，其中的每一個(gè)緩沖區(qū)單元咳存放一條信息。發(fā)送消息時(shí)，發(fā)送者從中申請(qǐng)一個(gè)可用緩沖區(qū)，接受者取出一條信息時(shí)再釋放該緩沖區(qū)，每個(gè)進(jìn)程均設(shè)置一條消息隊(duì)列，任何發(fā)送給該進(jìn)程的消息均暫存在其中。

存儲(chǔ)管理

存儲(chǔ)器工作原理

存儲(chǔ)器功能

• 存儲(chǔ)分配與回收：為每道程序分配內(nèi)存空間；提高內(nèi)存利用率；允許動(dòng)態(tài)申請(qǐng)內(nèi)存空間。
• 地址映射：在多道程序環(huán)境下，程序中的邏輯地址與內(nèi)存中的物理地址不可能一致，因此必須提供地址變換功能，將用戶的邏輯地址轉(zhuǎn)換成主存的物理地址，實(shí)現(xiàn)重定位，確保程序正常運(yùn)行。
• 存儲(chǔ)保護(hù)：每道程序都只在自己的內(nèi)存空間內(nèi)運(yùn)行，互不干擾。
• 存儲(chǔ)共享：
• 存儲(chǔ)擴(kuò)充：借助于虛擬存儲(chǔ)技術(shù)，從邏輯上去擴(kuò)充內(nèi)存容量。

程序裝入和鏈接

創(chuàng)建進(jìn)程首先要將程序和數(shù)據(jù)裝入內(nèi)存。將用戶源程序變?yōu)榭稍趦?nèi)存中執(zhí)行的程序，通常需要以下幾個(gè)步驟：

編譯：由編譯程序?qū)⒂脩粼创a編譯成若干個(gè)目標(biāo)模塊。
鏈接：由鏈接程序?qū)⒕幾g后形成的一組目標(biāo)模塊，以及所需庫(kù)函數(shù)鏈接在一起，形成一個(gè)完整的裝入模塊。
裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存運(yùn)行。

重定位

重定位的概念

由于一個(gè)作業(yè)裝入到與其地址空間不一致的存儲(chǔ)空間，對(duì)有關(guān)地址部分的調(diào)整過(guò)程稱為重定位?，F(xiàn)在一般計(jì)算機(jī)系統(tǒng)中都采用動(dòng)態(tài)重定位方法。

為什么要重定位？

我們寫(xiě)正常程序的時(shí)候根本不用去關(guān)心變量的位置，因?yàn)樵闯绦蛟诰幾g的時(shí)候它的內(nèi)存中的位置郡被計(jì)算好了。程序裝入內(nèi)存時(shí)，系統(tǒng)不會(huì)為它重定位。我們需要用到變量 的時(shí)候直接用變量名訪問(wèn)它就行了。有的程序不可避免也要用到變量，各個(gè)變量 在內(nèi)存中的位置自然也不相同。既然這些變量沒(méi)有固定的地址，那么程序在運(yùn)行的過(guò)程中只有重定位，才可以正常地訪問(wèn)相關(guān)資源。

重定位方式

對(duì)程序進(jìn)行重定位的技術(shù)按重定位的時(shí)機(jī)可分為兩種：靜態(tài)重定位和動(dòng)態(tài)重定位。

• 靜態(tài)重定位：是在目標(biāo)程序裝入內(nèi)存時(shí)，由裝入程序?qū)δ繕?biāo)程序中的指令和數(shù)據(jù)的地址進(jìn)行修改，即把程序的邏輯地址都改成實(shí)際的地址。對(duì)每個(gè)程序來(lái)說(shuō)，這種地址變換只是在裝入時(shí)一次完成，在程序運(yùn)行期間不再進(jìn)行重定位。

  • 優(yōu)點(diǎn)：是無(wú)需增加硬件地址轉(zhuǎn)換機(jī)構(gòu)，便于實(shí)現(xiàn)程序的靜態(tài)連接。在早期計(jì)算機(jī)系統(tǒng)中大多采用這種方案。
  • 缺點(diǎn)：（1）程序的存儲(chǔ)空間只能是連續(xù)的一片區(qū)域，而且在重定位之后就不能再移動(dòng)。這不利于內(nèi)存空間的有效使用。（2）各個(gè)用戶進(jìn)程很難共享內(nèi)存中的同一程序的副本。

• 動(dòng)態(tài)重定位：是在程序執(zhí)行期間每次訪問(wèn)內(nèi)存之前進(jìn)行重定位，即逐條指令執(zhí)行時(shí)完成地址轉(zhuǎn)換。這種變換是靠硬件地址變換機(jī)構(gòu)實(shí)現(xiàn)的。通常采用一個(gè)重定位寄存器，其中放有當(dāng)前正在執(zhí)行的程序在內(nèi)存空間中的起始地址，而地址空間中的代碼在裝入過(guò)程中不發(fā)生變化。

  • 優(yōu)點(diǎn)：（1）程序占用的內(nèi)存空間動(dòng)態(tài)可變，不必連續(xù)存放在一處。（2）比較容易實(shí)現(xiàn)幾個(gè)進(jìn)程對(duì)同一程序副本的共享使用。
  • 缺點(diǎn)：是需要附加的硬件支持，增加了機(jī)器成本，而且實(shí)現(xiàn)存儲(chǔ)管理的軟件算法比較復(fù)雜。
    動(dòng)態(tài)重定位是在作業(yè)運(yùn)行時(shí)執(zhí)行到一條訪存指令時(shí)再把邏輯地址轉(zhuǎn)換為主存中的物理地址，實(shí)際中是通過(guò)硬件地址轉(zhuǎn)換機(jī)制實(shí)現(xiàn)的。

連續(xù)存儲(chǔ)管理

單一連續(xù)存儲(chǔ)管理

在這種管理方式中，內(nèi)存被分為兩個(gè)區(qū)域：系統(tǒng)區(qū)和用戶區(qū)。應(yīng)用程序裝入到用戶區(qū)，可使用用戶區(qū)全部空間。其特點(diǎn)是，最簡(jiǎn)單，適用于單用戶、單任務(wù)的操作系統(tǒng)。CP／M 和 DOS 2．0 以下就是采用此種方式。這種方式的最大優(yōu)點(diǎn)就是易于管理。但也存在著一些問(wèn)題和不足之處，例如對(duì)要求內(nèi)存空間少的程序，造成內(nèi)存浪費(fèi)；程序全部裝入，使得很少使用的程序部分也占用—定數(shù)量的內(nèi)存。

固定分區(qū)存儲(chǔ)管理

原理

把內(nèi)存空間劃分為數(shù)量和大小固定不變的連續(xù)分區(qū)，各分區(qū)大小不等，每個(gè)分區(qū)只裝入一個(gè)作業(yè)，若多個(gè)分區(qū)中都裝有作業(yè)，則它們可以并發(fā)執(zhí)行，這樣就支持多道程序設(shè)計(jì)。

設(shè)置一張內(nèi)存分配表，記錄內(nèi)存中劃分的分區(qū)及其使用情況。內(nèi)存分配表指出各分區(qū)起始地址和長(zhǎng)度，占用標(biāo)志用來(lái)指示此分區(qū)是否被使用。

內(nèi)存分配時(shí)總是選擇那些占用標(biāo)志為0的未被占用分區(qū)，當(dāng)某分區(qū)被分配給一個(gè)長(zhǎng)度小于等于分區(qū)長(zhǎng)度的作業(yè)后，則在占用標(biāo)志中填入占用此分區(qū)的作業(yè)名。

當(dāng)分區(qū)中的程序執(zhí)行結(jié)束歸還內(nèi)存區(qū)時(shí)，相應(yīng)分區(qū)的占用標(biāo)志置0，其占用的分區(qū)又變成空閑，可被重新分配使用。

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：易于實(shí)現(xiàn)，開(kāi)銷小；能解決單道程序運(yùn)行在并發(fā)環(huán)境下與CPU速度不匹配且內(nèi)存空間利用率低的問(wèn)題。

缺點(diǎn)：內(nèi)碎片問(wèn)題；存儲(chǔ)器利用率極低；大作業(yè)無(wú)法裝入；分區(qū)總數(shù)固定，很難動(dòng)態(tài)擴(kuò)充內(nèi)存空間；分區(qū)數(shù)目在系統(tǒng)初始化時(shí)指定，限制了并發(fā)執(zhí)行的程序數(shù)目。

可變分區(qū)存儲(chǔ)管理

原理

動(dòng)態(tài)創(chuàng)建分區(qū)：在裝入程序時(shí)按其初始要求分配，或在其執(zhí)行過(guò)程中根據(jù)作業(yè)大小通過(guò)系統(tǒng)調(diào)用進(jìn)行分配或改變分區(qū)大小。

動(dòng)態(tài)分區(qū)的分區(qū)分配就是尋找某個(gè)空閑分區(qū)，其大小需大于或等于程序的要求。若是大于要求，則將該分區(qū)分割成兩個(gè)分區(qū)，其中一個(gè)分區(qū)為要求的大小并標(biāo)記為 “占用”，而另一個(gè)分區(qū)為余下部分并標(biāo)記為 “空閑”。分區(qū)分配的先后次序通常是從內(nèi)存低端到高端。動(dòng)態(tài)分區(qū)的分區(qū)釋放過(guò)程中有一個(gè)要注意的問(wèn)題是，將相鄰的空閑分區(qū)合并成一個(gè)大的空閑分區(qū)。

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：沒(méi)有內(nèi)碎片。

缺點(diǎn)：外碎片問(wèn)題。

可變分區(qū)分配算法

• 最先適應(yīng)法(first fit)：按分區(qū)在內(nèi)存的先后次序從頭查找，找到符合要求的第一個(gè)分區(qū)進(jìn)行分配。該算法的分配和釋放的時(shí)間性能較好，較大的空閑分區(qū)可以被保留在內(nèi)存高端。但隨著低端分區(qū)不斷劃分會(huì)產(chǎn)生較多小分區(qū)，每次分配時(shí)查找時(shí)間開(kāi)銷便會(huì)增大。
• 下次適應(yīng)法(next fit)：按分區(qū)在內(nèi)存的先后次序從上次分配的分區(qū)起查找，找到符合要求的第一個(gè)分區(qū)進(jìn)行分配。該算法的分配和釋放的時(shí)間性能較好，使空閑分區(qū)分布得更均勻，但較大空閑分區(qū)不易保留。
• 最優(yōu)適應(yīng)法(best fit)：按分區(qū)在內(nèi)存的先后次序從頭查找，找到其大小與要求相差最小的空閑分區(qū)進(jìn)行分配。從個(gè)別來(lái)看，外碎片較?。坏珡恼w來(lái)看，會(huì)形成較多外碎片優(yōu)點(diǎn)是較大的空閑分區(qū)可以被保留。
• 最壞適應(yīng)法(worst fit)：按分區(qū)在內(nèi)存的先后次序從頭查找，找到最大的空閑分區(qū)進(jìn)行分配?；静涣粝滦】臻e分區(qū)，不易形成外碎片。但由于較大的空閑分區(qū)不被保留，當(dāng)對(duì)內(nèi)存需求較大的進(jìn)程需要運(yùn)行時(shí)，其要求不易被滿足。
• 快速應(yīng)法 (quick fit)：為那些經(jīng)常用到的長(zhǎng)度的空閑區(qū)設(shè)立單獨(dú)的空閑區(qū)鏈表。

內(nèi)存不足的存儲(chǔ)管理技術(shù)（碎片整理）

• 移動(dòng)技術(shù)：把已在內(nèi)存中的進(jìn)程分區(qū)連接到一起，使分散的空閑區(qū)匯集成片，也叫內(nèi)存緊湊。
• 對(duì)換技術(shù)：在某個(gè)進(jìn)程在不被使用（阻塞）或在CPU調(diào)度原則下被剝奪運(yùn)行權(quán)利的時(shí)候，被暫時(shí)移出內(nèi)存，騰出空間給其他進(jìn)程使用，同時(shí)交換到磁盤(pán)中，此時(shí)處于就緒狀態(tài)，需要時(shí)再加載回來(lái)。
• 覆蓋技術(shù)：一個(gè)程序的幾個(gè)代碼段或數(shù)據(jù)段，按照時(shí)間先后來(lái)占用公共的內(nèi)存空間。將程序必要部分(常用功能)的代碼和數(shù)據(jù)常駐內(nèi)存；可選部分(不常用功能)平時(shí)存放在外存(覆蓋文件)中，在需要時(shí)才裝入內(nèi)存。不存在調(diào)用關(guān)系的模塊不必同時(shí)裝入到內(nèi)存，從而可以相互覆蓋。

交換技術(shù)主要是在不同進(jìn)程（或作業(yè)）之間進(jìn)行，而覆蓋則用于同一個(gè)程序或進(jìn)程中。由于覆蓋技術(shù)要求給出程序段之間的覆蓋結(jié)構(gòu)，使得其對(duì)用戶和程序員不透明，所以對(duì)于主存無(wú)法存放用戶程序的矛盾，現(xiàn)代操作系統(tǒng)是通過(guò)虛擬內(nèi)存技術(shù)來(lái)解決的，覆蓋技術(shù)則已成為歷史；而交換技術(shù)在現(xiàn)代操作系統(tǒng)中仍具有較強(qiáng)的生命力。

分頁(yè)存儲(chǔ)管理

非連續(xù)分配允許一個(gè)程序分散地裝入到不相鄰的內(nèi)存分區(qū)中，根據(jù)分區(qū)的大小是否固定分為分頁(yè)存儲(chǔ)管理方式和分段存儲(chǔ)管理方式。

原理

• 將用戶進(jìn)程地址空間（進(jìn)程的虛擬空間）劃分為大小相等的部分，稱為“頁(yè)”或“頁(yè)面”。
• 將內(nèi)存空間按同樣的大小劃分為大小相等的部分，稱為“頁(yè)框”或“物理頁(yè)”。
• 然后把頁(yè)式虛擬地址與內(nèi)存地址建立一一對(duì)應(yīng)的頁(yè)表，并用相應(yīng)的硬件地址轉(zhuǎn)換機(jī)構(gòu)來(lái)解決離散地址變換問(wèn)題。
• 內(nèi)存分配規(guī)則：以頁(yè)為單位進(jìn)行分配，并按進(jìn)程需要的頁(yè)數(shù)來(lái)分配。邏輯上相鄰的頁(yè)物理上不一定相鄰。
• 頁(yè)式管理采用請(qǐng)求調(diào)頁(yè)和預(yù)調(diào)頁(yè)技術(shù)來(lái)實(shí)現(xiàn)內(nèi)外存存儲(chǔ)器的統(tǒng)一管理。

把主存空間劃分為大小相等且固定的塊，塊相對(duì)較小，作為主存的基本單位。每個(gè)進(jìn)程也以塊為單位進(jìn)行劃分，進(jìn)程在執(zhí)行時(shí)，以塊為單位逐個(gè)申請(qǐng)主存中的塊空間。

因?yàn)槌绦驍?shù)據(jù)存儲(chǔ)在不同的頁(yè)面中，而頁(yè)面又離散的分布在內(nèi)存中，因此需要一個(gè)頁(yè)表來(lái)記錄邏輯地址和實(shí)際存儲(chǔ)地址之間的映射關(guān)系，以實(shí)現(xiàn)從頁(yè)號(hào)到物理塊號(hào)的映射。

由于頁(yè)表也是存儲(chǔ)在內(nèi)存中的，因此和不適用分頁(yè)管理的存儲(chǔ)方式相比，訪問(wèn)分頁(yè)系統(tǒng)中內(nèi)存數(shù)據(jù)需要兩次的內(nèi)存訪問(wèn) (一次是從內(nèi)存中訪問(wèn)頁(yè)表，從中找到指定的物理塊號(hào)，加上頁(yè)內(nèi)偏移得到實(shí)際物理地址；第二次就是根據(jù)第一次得到的物理地址訪問(wèn)內(nèi)存取出數(shù)據(jù))。

為了減少兩次訪問(wèn)內(nèi)存導(dǎo)致的效率影響，分頁(yè)管理中引入了快表機(jī)制，包含快表機(jī)制的內(nèi)存管理中，當(dāng)要訪問(wèn)內(nèi)存數(shù)據(jù)的時(shí)候，首先將頁(yè)號(hào)在快表中查詢，如果查找到說(shuō)明要訪問(wèn)的頁(yè)表項(xiàng)在快表中，那么直接從快表中讀取相應(yīng)的物理塊號(hào)；如果沒(méi)有找到，那么訪問(wèn)內(nèi)存中的頁(yè)表，從頁(yè)表中得到物理地址，同時(shí)將頁(yè)表中的該映射表項(xiàng)添加到快表中 (可能存在快表?yè)Q出算法)。

在某些計(jì)算機(jī)中如果內(nèi)存的邏輯地址很大，將會(huì)導(dǎo)致程序的頁(yè)表項(xiàng)會(huì)很多，而頁(yè)表在內(nèi)存中是連續(xù)存放的，所以相應(yīng)的就需要較大的連續(xù)內(nèi)存空間。為了解決這個(gè)問(wèn)題，可以采用兩級(jí)頁(yè)表或者多級(jí)頁(yè)表的方法，其中外層頁(yè)表一次性調(diào)入內(nèi)存且連續(xù)存放，內(nèi)層頁(yè)表離散存放。相應(yīng)的訪問(wèn)內(nèi)存頁(yè)表的時(shí)候需要一次地址變換，訪問(wèn)邏輯地址對(duì)應(yīng)的物理地址的時(shí)候也需要一次地址變換，而且一共需要訪問(wèn)內(nèi)存 3 次才可以讀取一次數(shù)據(jù)。

快表

什么是快表？它在地址轉(zhuǎn)換中起什么作用？
快表是一個(gè)高速、具有并行查詢能力的聯(lián)想存儲(chǔ)器，用于存放正運(yùn)行的進(jìn)程的當(dāng)前頁(yè)號(hào)和塊號(hào)，或者段號(hào)和段起始地址。
加入快表后,在地址轉(zhuǎn)換時(shí)，首先在快表中查找，若找到就直接進(jìn)行地址轉(zhuǎn)換；未找到，則在主存頁(yè)表繼續(xù)查找，并把查到的頁(yè)號(hào)和塊號(hào)放入聯(lián)想存儲(chǔ)器中。快表的命中率很高，有效地提高了地址轉(zhuǎn)換的速度。

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：沒(méi)有外碎片，每個(gè)內(nèi)碎片不超過(guò)頁(yè)的大小。
缺點(diǎn)：程序的最后一頁(yè)會(huì)有浪費(fèi)空間的現(xiàn)象，不能應(yīng)用在分段編寫(xiě)的、非連續(xù)存放的大型程序中。
程序全部裝入內(nèi)存，要求有相應(yīng)的硬件支持，如地址變換機(jī)構(gòu)缺頁(yè)中斷的產(chǎn)生和選擇淘汰頁(yè)面等都要求有相應(yīng)的硬件支持。增加了機(jī)器成本和系統(tǒng)開(kāi)銷。

分段存儲(chǔ)管理

原理

一個(gè)用戶作業(yè)或者進(jìn)程所包含的段對(duì)應(yīng)一個(gè)二維線性虛擬空間，也就是一個(gè)二維虛擬存儲(chǔ)器。

• 用戶進(jìn)程地址空間：按程序自身的邏輯關(guān)系劃分為若干個(gè)程序段，每個(gè)程序段都有一個(gè)段名。
• 內(nèi)存空間：被動(dòng)態(tài)劃分為若干個(gè)長(zhǎng)度不相同的區(qū)域，稱為“物理段”，每個(gè)物理段由起始地址和長(zhǎng)度確定。
• 內(nèi)存分配規(guī)則：以段為單位進(jìn)行分配，每段在內(nèi)存中占據(jù)連續(xù)空間，但各段之間可以不相鄰。然后通過(guò)地址映射機(jī)構(gòu)把段式虛擬地址轉(zhuǎn)換為實(shí)際內(nèi)存物理地址。

分頁(yè)是為了提高內(nèi)存利用率，而分段是為了滿足程序員在編寫(xiě)代碼的時(shí)候的一些邏輯需求（比如數(shù)據(jù)共享，數(shù)據(jù)保護(hù)，動(dòng)態(tài)鏈接等）。

分段內(nèi)存管理當(dāng)中，地址是二維的，一維是段號(hào)，一維是段內(nèi)地址；其中每個(gè)段的長(zhǎng)度是不一樣的，而且每個(gè)段內(nèi)部都是從 0 開(kāi)始編址的。由于分段管理中，每個(gè)段內(nèi)部是連續(xù)內(nèi)存分配，但是段和段之間是離散分配的，因此也存在一個(gè)邏輯地址到物理地址的映射關(guān)系，相應(yīng)的就是段表機(jī)制。段表中的每一個(gè)表項(xiàng)記錄了該段在內(nèi)存中的起始地址和該段的長(zhǎng)度。段表可以放在內(nèi)存中也可以放在寄存器中。

訪問(wèn)內(nèi)存的時(shí)候根據(jù)段號(hào)和段表項(xiàng)的長(zhǎng)度計(jì)算當(dāng)前訪問(wèn)段在段表中的位置，然后訪問(wèn)段表，得到該段的物理地址，根據(jù)該物理地址以及段內(nèi)偏移量就可以得到需要訪問(wèn)的內(nèi)存。由于也是兩次內(nèi)存訪問(wèn)，所以分段管理中同樣引入了聯(lián)想寄存器。

優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：可以分別編寫(xiě)和編譯，可以針對(duì)不同類型的段采取不同的保護(hù)，可以按段為單位來(lái)進(jìn)行共享，包括通過(guò)動(dòng)態(tài)鏈接進(jìn)行代碼共享。
缺點(diǎn)：會(huì)產(chǎn)生碎片。

分段分頁(yè)方式的比較

頁(yè)是信息的物理單位，是出于系統(tǒng)內(nèi)存利用率的角度提出的離散分配機(jī)制；段是信息的邏輯單位，每個(gè)段含有一組意義完整的信息，是出于用戶角度提出的內(nèi)存管理機(jī)制。

頁(yè)的大小是固定的，由系統(tǒng)決定；段的大小是不確定的，由用戶決定。

段頁(yè)式存儲(chǔ)管理

原理

系統(tǒng)必須為每個(gè)作業(yè)或者進(jìn)程建立一張段表以管理內(nèi)存分配與釋放、缺段處理等。另外由于一個(gè)段又被劃分為若干個(gè)頁(yè)，每個(gè)段必須建立一張頁(yè)表以把段中的虛頁(yè)變換為內(nèi)存中的實(shí)際頁(yè)面。顯然與頁(yè)式管理時(shí)相同，頁(yè)表也要有相應(yīng)的實(shí)現(xiàn)缺頁(yè)中斷處理和頁(yè)面保護(hù)等功能的表項(xiàng)。

優(yōu)缺點(diǎn)

段頁(yè)式管理是段式管理和頁(yè)式管理相結(jié)合而成，具有兩者的優(yōu)點(diǎn)。

由于管理軟件的增加，復(fù)雜性和開(kāi)銷也增加。另外需要的硬件以及占用的內(nèi)存也有所增加，使得執(zhí)行速度下降。

在分頁(yè)、分段和段頁(yè)式存儲(chǔ)管理中，當(dāng)訪問(wèn)一條指令時(shí)，需要訪問(wèn)內(nèi)存幾次各做什么操作？

在分頁(yè)和分段系統(tǒng)中，首先需要訪問(wèn)頁(yè)表或段表，然后才能訪問(wèn)實(shí)際數(shù)據(jù)，因此需要至少訪問(wèn)內(nèi)存 2 次。
在段頁(yè)式存儲(chǔ)管理中，首先要訪問(wèn)段表，最后訪問(wèn)相關(guān)段的頁(yè)表，最后才能訪問(wèn)實(shí)際數(shù)據(jù)，因此一共需訪問(wèn)內(nèi)存至少 3 次。
如果采用的是多級(jí)頁(yè)表，則訪問(wèn)次數(shù)還將增加。如果使用快表，且在快表中命中，則只需要訪問(wèn)內(nèi)存 1 次。

在固定分區(qū)管理、動(dòng)態(tài)分區(qū)管理、分頁(yè)存儲(chǔ)管理、分段存儲(chǔ)管理中，各會(huì)產(chǎn)生何種碎片？

答：在固定分區(qū)管理中，每個(gè)分區(qū)內(nèi)都可能存在碎片；

在動(dòng)態(tài)分區(qū)管理中，會(huì)存在一些很小的，不足以任何應(yīng)用程序使用的小碎片； 在分頁(yè)存儲(chǔ)管理中，每個(gè)應(yīng)用程序的最后一頁(yè)可能存在碎片。

在分段存儲(chǔ)管理中，可能存在小的內(nèi)存區(qū)，不足以存放應(yīng)用程序的一個(gè)連續(xù)的段，形成碎片。

在內(nèi)存管理中，“內(nèi)零頭” 和 “外零頭” 個(gè)指的是什么？在固定式分區(qū)分配、可變式分區(qū)分配、頁(yè)式虛擬存儲(chǔ)系統(tǒng)、段式虛擬存儲(chǔ)系統(tǒng)中，各會(huì)存在何種零頭？為什么？
解答：
在存儲(chǔ)管理中，內(nèi)零頭是指分配給作業(yè)的存儲(chǔ)空間中未被利用的部分，外零頭是指系統(tǒng)中無(wú)法利用的小存儲(chǔ)塊。

在固定式分區(qū)分配中，為將一個(gè)用戶作業(yè)裝入內(nèi)存，內(nèi)存分配程序從系統(tǒng)分區(qū)表中找出一個(gè)能滿足作業(yè)要求的空閑分區(qū)分配給作業(yè)，由于一個(gè)作業(yè)的大小并不一定與分區(qū)大小相等，因此，分區(qū)中有一部分存儲(chǔ)空間浪費(fèi)掉了。由此可知，固定式分區(qū)分配中存在內(nèi)零頭。

在可變式分區(qū)分配中，為把一個(gè)作業(yè)裝入內(nèi)存，應(yīng)按照一定的分配算法從系統(tǒng)中找出一個(gè)能滿足作業(yè)需求的空閑分區(qū)分配給作業(yè)，如果這個(gè)空閑分區(qū)的容量比作業(yè)申請(qǐng)的空間容量要大，則將該分區(qū)一分為二，一部分分配給作業(yè)，剩下的部分仍然留作系統(tǒng)的空閑分區(qū)。由此可知，可變式分區(qū)分配中存在外零頭。

在頁(yè)式虛擬存儲(chǔ)系統(tǒng)中，用戶作業(yè)的地址空間被劃分成若干大小相等的頁(yè)面，存儲(chǔ)空間也分成也頁(yè)大小相等的物理塊，但一般情況下，作業(yè)的大小不可能都是物理塊大小的整數(shù)倍，因此作業(yè)的最后一頁(yè)中仍有部分空間被浪費(fèi)掉了。由此可知，頁(yè)式虛擬存儲(chǔ)系統(tǒng)中存在內(nèi)零頭。在段式虛擬存儲(chǔ)系統(tǒng)中，作業(yè)的地址空間由若干個(gè)邏輯分段組成，每段分配一個(gè)連續(xù)的內(nèi)存區(qū)，但各段之間不要求連續(xù)，其內(nèi)存的分配方式類似于動(dòng)態(tài)分區(qū)分配。

由此可知，段式虛擬存儲(chǔ)系統(tǒng)中存在外零頭。

基本內(nèi)存管理方案小結(jié)

虛擬存儲(chǔ)管理

局部性原理

程序的局部性原理：指程序在執(zhí)行過(guò)程中的一個(gè)較短時(shí)期，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域。這可以表現(xiàn)為：

• 時(shí)間局部性：一條指令的一次執(zhí)行和下次執(zhí)行，一個(gè)數(shù)據(jù)的一次訪問(wèn)和下次訪問(wèn)都集中在一個(gè)較短時(shí)期內(nèi)。即如果程序中的某條指令一旦執(zhí)行，不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪問(wèn)過(guò)，不久以后該數(shù)據(jù)可能再次被訪問(wèn)。產(chǎn)生時(shí)間局部性的典型原因，是由于在程序中存在著大量的循環(huán)操作。
• 空間局部性：當(dāng)前指令和鄰近的幾條指令，當(dāng)前訪問(wèn)的數(shù)據(jù)和鄰近的幾個(gè)數(shù)據(jù)都集中在一個(gè)較小區(qū)域內(nèi)。即一旦程序訪問(wèn)了某個(gè)存儲(chǔ)單元，在不久之后，其附近的存儲(chǔ)單元也將被訪問(wèn)，即程序在一段時(shí)間內(nèi)所訪問(wèn)的地址，可能集中在一定的范圍之內(nèi)，這是因?yàn)橹噶钔ǔＪ琼樞虼娣拧㈨樞驁?zhí)行的，數(shù)據(jù)也一般是以向量、數(shù)組、表等形式簇聚存儲(chǔ)的。

時(shí)間局部性是通過(guò)將近來(lái)使用的指令和數(shù)據(jù)保存到高速緩存存儲(chǔ)器中，并使用高速緩存的層次結(jié)構(gòu)實(shí)現(xiàn)。
空間局部性通常是使用較大的高速緩存，并將預(yù)取機(jī)制集成到高速緩存控制邏輯中實(shí)現(xiàn)。

虛擬內(nèi)存技術(shù)實(shí)際上就是建立了 “內(nèi)存一外存” 的兩級(jí)存儲(chǔ)器的結(jié)構(gòu)，利用局部性原理實(shí)現(xiàn)髙速緩存。

虛擬存儲(chǔ)器的概念及特點(diǎn)

虛擬存儲(chǔ)器是一種存儲(chǔ)管理技術(shù)，用以完成用小的內(nèi)存實(shí)現(xiàn)在大的虛空間中程序的運(yùn)行工作。它是由操作系統(tǒng)提供的一個(gè)假想的特大存儲(chǔ)器。但是虛擬存儲(chǔ)器的容量并不是無(wú)限的，它由計(jì)算機(jī)的地址結(jié)構(gòu)長(zhǎng)度所確定，另外虛存容量的擴(kuò)大是以犧牲CPU工作時(shí)間以及內(nèi)、外存交換時(shí)間為代價(jià)的。

虛存技術(shù)的特征

• 大的用戶空間：通過(guò)把物理內(nèi)存與外存相結(jié)合，提供給用戶的虛擬內(nèi)存空間通常大于實(shí)際的物理內(nèi)存，即實(shí)現(xiàn)了這兩者的分離。
• 虛擬擴(kuò)充：即不是物理上而是邏輯上擴(kuò)充了內(nèi)存容量。
• 部分裝入：即每個(gè)作業(yè)不是全部一次性地裝入內(nèi)存，而是只裝入一部分。
• 離散分配（不連續(xù)性）：即不必占用連續(xù)的內(nèi)存空間，而是“見(jiàn)縫插針”。
• 多次對(duì)換：即所需的全部程序和數(shù)據(jù)要分成多次調(diào)入內(nèi)存。

虛擬存儲(chǔ)器的容量主要受到指令中表示地址的字長(zhǎng)和外存的容量的限制。

虛存技術(shù)的目標(biāo)

• 像覆蓋技術(shù)那樣，不是把程序的所有內(nèi)容都放在內(nèi)存中（部分裝入），因而能夠運(yùn)行比當(dāng)前的空閑內(nèi)存空間還要大的程序。但做得更好，由操作系統(tǒng)自動(dòng)完成而無(wú)須程序員的干涉。
• 像交換技術(shù)那樣，能夠實(shí)現(xiàn)進(jìn)程在內(nèi)存與外存之間的交換，因而獲得更多的空閑內(nèi)存空間。但做得更好，只對(duì)進(jìn)程的部分內(nèi)容進(jìn)行交換。（交換技術(shù)的粒度是以一個(gè)程序?yàn)閱挝?，虛存以更小的粒度?shí)現(xiàn)）

虛存技術(shù)的實(shí)現(xiàn)

在頁(yè)式或段式內(nèi)存管理的基礎(chǔ)上實(shí)現(xiàn)。

• 在裝入程序時(shí)，不必將其全部裝入到內(nèi)存，則只需將當(dāng)前需要執(zhí)行的部分頁(yè)面或段裝入到內(nèi)存，就可以讓程序開(kāi)始執(zhí)行；
• 在程序執(zhí)行過(guò)程中，如果需執(zhí)行的指令或訪問(wèn)的數(shù)據(jù)尚未在內(nèi)存（稱為缺頁(yè)或缺段），則由處理器通知操作系統(tǒng)將相應(yīng)的頁(yè)面或段調(diào)入到內(nèi)存，然后繼續(xù)執(zhí)行程序；
• 另一方面，操作系統(tǒng)將內(nèi)存中暫時(shí)不使用的頁(yè)面或段調(diào)出保存在外存上，從而騰出更多空閑空間存放將要裝入的程序以及將要調(diào)入的頁(yè)面或段。

虛擬頁(yè)式內(nèi)存管理

在頁(yè)式存儲(chǔ)管理的基礎(chǔ)上，增加請(qǐng)求調(diào)頁(yè)和頁(yè)面置換功能。

主存空間信息保護(hù)

1. 程序執(zhí)行時(shí)訪問(wèn)屬于自己主存區(qū)域的信息，允許它既可讀，又可寫(xiě)；
2. 對(duì)共享區(qū)域中的信息只可讀，不可修改；
3. 對(duì)非共享區(qū)域或非自己的主存區(qū)域中的信息既不可讀，也不可寫(xiě)。

設(shè)備管理

設(shè)備管理的功能

• 管理所有外圍設(shè)備，包括完成用戶的 IO 請(qǐng)求
• 為用戶進(jìn)程分配 IO 設(shè)備
• 提高 IO 設(shè)備利用率
• 提高 IO 速度
• 方便 IO 的使用

I/O硬件原理

I/O設(shè)備的分類

• 獨(dú)占設(shè)備：在一段時(shí)間內(nèi)只能有一個(gè)進(jìn)程使用的設(shè)備，一般為低速I/O設(shè)備（如打印機(jī)，磁帶等）
• 共享設(shè)備：在一段時(shí)間內(nèi)可由多個(gè)進(jìn)程共同使用的設(shè)備，多個(gè)進(jìn)程以交叉的方式來(lái)使用設(shè)備，其資源利用率高（如硬盤(pán)）
• 虛擬設(shè)備：在一類設(shè)備上模擬另一類設(shè)備，常用共享設(shè)備模擬獨(dú)占設(shè)備，用高速設(shè)備模擬低速設(shè)備，被模擬的設(shè)備稱為虛設(shè)備。其目的就是將慢速的獨(dú)占設(shè)備改造成多個(gè)用戶可共享的設(shè)備，提高設(shè)備的利用率。如SPOOLing技術(shù)，利用虛設(shè)備技術(shù)（用硬盤(pán)模擬輸入輸出設(shè)備）

設(shè)備管理的主要功能

在現(xiàn)代的操作系統(tǒng)中，設(shè)備管理的任務(wù)主要有以下幾個(gè)方面。

• 根據(jù)用戶提出的要求對(duì) I/O 設(shè)備進(jìn)行控制，完成用戶提出的輸入 / 輸出要求。
• 由于現(xiàn)代的操作系統(tǒng)允許多個(gè)進(jìn)程的并發(fā)執(zhí)行，為了有效地分配設(shè)備資源，要求設(shè)備管理能夠根據(jù)設(shè)備請(qǐng)求的情況，按照一定的算法實(shí)現(xiàn)對(duì)某個(gè) I/O 設(shè)備進(jìn)行合理分配。
• 當(dāng)計(jì)算機(jī)系統(tǒng)屮有種類繁多的 I/O 設(shè)備時(shí)，要求設(shè)備管理能夠充分而有效地使用這些設(shè)備，盡可能提高它們與 CPU 的并行操作程度。

針對(duì)上述的任務(wù)需求，設(shè)備管理應(yīng)具有以下功能：

• 緩沖管理：CPU 與設(shè)備之間、設(shè)備與設(shè)備之間交換信息時(shí)，需要利用緩沖區(qū)來(lái)緩解速度不匹配的矛盾，提高 CPU 與設(shè)備之間、設(shè)備與設(shè)備之間操作的并行程度。
• 設(shè)備分配：系統(tǒng)根據(jù)進(jìn)程所請(qǐng)求的設(shè)備，按分配算法對(duì)設(shè)備和設(shè)備相應(yīng)的控制器和通道進(jìn)行分配，建立從設(shè)備到內(nèi)存之間傳輸信息的通路。在進(jìn)程的 I/O 完成后，系統(tǒng)應(yīng)及時(shí)回收設(shè)備，以便重新分配給其他進(jìn)程使用。將未獲得所需設(shè)備的進(jìn)程放進(jìn)相應(yīng)設(shè)備的等待隊(duì)列中。
• 設(shè)備驅(qū)動(dòng)：邏輯設(shè)備名轉(zhuǎn)換成設(shè)備的物理地址，啟動(dòng)指定的 I/O 設(shè)備，完成程序規(guī)定的 I/O 操作，并對(duì)由設(shè)備發(fā)來(lái)的中斷請(qǐng)求進(jìn)行及時(shí)響應(yīng)，根據(jù)中斷類型進(jìn)行相應(yīng)的處理。
• 設(shè)備無(wú)關(guān)性: 用戶在編制程序時(shí)，不直接使用實(shí)際的設(shè)備名而使用邏輯設(shè)備名。有利于解決設(shè)備的故障和增加設(shè)備分配的靈活性。
• 虛擬設(shè)備：一次僅允許一個(gè)進(jìn)程使用的設(shè)備稱為獨(dú)占設(shè)備。獨(dú)占設(shè)備不僅降低了系統(tǒng)的設(shè)備利用率，而且可能產(chǎn)生死鎖。虛擬設(shè)備能被多個(gè)進(jìn)程共享，提高了設(shè)備的利用率，并且防止了死鎖。關(guān)于虛擬設(shè)備的實(shí)現(xiàn)以后章節(jié)將詳細(xì)討論。

I/O控制方式

設(shè)備管理的主要任務(wù)之一是控制設(shè)備和內(nèi)存或者處理機(jī)之間的數(shù)據(jù)傳送。

• 輪詢方式
• 中斷方式
• DMA方式
• 通道方式

輪詢方式

CPU 需要時(shí)刻對(duì)外設(shè)設(shè)備狀態(tài)進(jìn)行循環(huán)檢查，直到確定該字已經(jīng)在 I/O 控制器的數(shù)據(jù)寄存器中。CPU 和設(shè)備只能串行工作，CPU 效率相當(dāng)?shù)汀?/p>

中斷方式

允許 I/O 設(shè)備主動(dòng)打斷 CPU 的運(yùn)行并且請(qǐng)求服務(wù)，使得其向 I/O 控制器發(fā)送讀命令。

DMA方式

直接存儲(chǔ)讀取在 I/O 設(shè)備和內(nèi)存之間加上 DMA 控制器使得數(shù)據(jù)進(jìn)行直接傳輸而不經(jīng)過(guò) CPU。

通道方式

I/O 通道是指專門負(fù)責(zé)輸入 / 輸出的處理機(jī)，因此屬于硬件技術(shù)。
CPU 要完成一組相關(guān)的讀寫(xiě)操作以及有關(guān)控制時(shí)候，向 I/O 通道發(fā)送一條 I/O 指令，給出所要執(zhí)行的通道程序的首地址和要訪問(wèn)的 I/O 設(shè)備，通道接受指令后，執(zhí)行通道程序完成 CPU 指定的 I/O 任務(wù)，數(shù)據(jù)傳送結(jié)束時(shí)向 CPU 發(fā)送中斷請(qǐng)求。
通道方式由通道控制傳輸?shù)臄?shù)據(jù)塊大小以及傳輸?shù)膬?nèi)存位置，一個(gè)通道可以控制多臺(tái)設(shè)備與內(nèi)存的數(shù)據(jù)交換。

I/O軟件原理

設(shè)備獨(dú)立性

設(shè)備獨(dú)立性即應(yīng)用程序獨(dú)立于使用的物理設(shè)備，在應(yīng)用程序中使用邏輯設(shè)備名稱來(lái)請(qǐng)求使用某類設(shè)備。系統(tǒng)在執(zhí)行時(shí)，是使用物理設(shè)備名稱。

要實(shí)現(xiàn)設(shè)備獨(dú)立性必須由設(shè)備獨(dú)立性軟件完成，包括執(zhí)行所有設(shè)備的公有操作軟件提供統(tǒng)一的接口，其中邏輯設(shè)備到物理設(shè)備的映射是由邏輯設(shè)備表LUT完成的。

I/O軟件的分層結(jié)構(gòu)

共有5層，從底到高依次是硬件->中斷處理程序->設(shè)備驅(qū)動(dòng)程序->設(shè)備獨(dú)立性軟件->用戶層I/O軟件。

• 中斷處理程序：用于保存被中斷進(jìn)程的CPU環(huán)境，轉(zhuǎn)入相應(yīng)的中斷處理程序進(jìn)行處理，處理完后恢復(fù)現(xiàn)場(chǎng)，并返回到被中斷的進(jìn)程
• 設(shè)備驅(qū)動(dòng)程序：與硬件直接有關(guān)，用來(lái)具體實(shí)現(xiàn)系統(tǒng)對(duì)設(shè)備發(fā)出的操作指令，驅(qū)動(dòng)I/O設(shè)備工作
• 設(shè)備獨(dú)立性軟件/獨(dú)立于設(shè)備的I/O軟件：用于實(shí)現(xiàn)用戶程序與設(shè)備驅(qū)動(dòng)器的統(tǒng)一接口、設(shè)備命令、設(shè)備保護(hù)，以及設(shè)備分配與釋放等。
• 最高層：用于實(shí)現(xiàn)用戶與I/O設(shè)備交互

I/O軟件的主要功能

通常將 I/O 軟件組織成四個(gè)層次：用戶應(yīng)用層軟件、中斷處理程序、獨(dú)立于設(shè)備的軟件和設(shè)備驅(qū)動(dòng)程序。
I/O 軟件包括 I/O 設(shè)備驅(qū)動(dòng)軟件和設(shè)備無(wú)關(guān)軟件。設(shè)計(jì) I/O 軟件的一個(gè)最關(guān)鍵的目標(biāo)是設(shè)備無(wú)關(guān)性，I/O 設(shè)備管理軟件采用分層構(gòu)造，每一層的軟件都有自己獨(dú)立的功能，最低層軟件與硬件的細(xì)節(jié)密切相關(guān)，并對(duì)高層軟件隱藏了硬件的具體特性，I/O 軟件除了直接與設(shè)備打交道的低層軟件之外，其他部分的軟件并不依賴于硬件。

I/O軟件的處理過(guò)程

采用分層思想，當(dāng)用戶進(jìn)程提出 I/O 請(qǐng)求訪問(wèn)硬件時(shí)，需要按：進(jìn)程請(qǐng)求 I/O→獨(dú)立于設(shè)備的軟件→設(shè)備驅(qū)動(dòng)程序→中斷處理程序→硬件的層次結(jié)構(gòu)進(jìn)行。

緩沖技術(shù)

緩沖引入的原因

• 緩和CPU與I/O設(shè)備間速度不匹配的矛盾
• 減少對(duì)CPU的中斷頻率，放寬對(duì)CPU中斷響應(yīng)時(shí)間的限制
• 提高CPU和I/O設(shè)備之間的并行性
• 解決數(shù)據(jù)粒度不匹配的問(wèn)題

緩沖的實(shí)現(xiàn)方式

軟緩沖的種類

系統(tǒng)調(diào)用的處理步驟

首先，將處理機(jī)狀態(tài)由用戶態(tài)轉(zhuǎn)為系統(tǒng)態(tài)；之后由硬件和內(nèi)核程序進(jìn)行系統(tǒng)調(diào)用的一般處理；然后將用戶定義的參數(shù)傳送到指定的地址并保存起來(lái)。
其次，分析系統(tǒng)調(diào)用類型，轉(zhuǎn)入相應(yīng)的系統(tǒng)調(diào)用處理子程序。
最后，恢復(fù)被中斷的或設(shè)置新進(jìn)程的CPU現(xiàn)場(chǎng)，然后返回被中斷進(jìn)程或新進(jìn)程，繼續(xù)往下執(zhí)行。

驅(qū)動(dòng)調(diào)度技術(shù)

設(shè)備驅(qū)動(dòng)程序的功能、特點(diǎn)

磁盤(pán)訪問(wèn)時(shí)間包括什么？

磁盤(pán)訪問(wèn)時(shí)間由：尋道時(shí)間、旋轉(zhuǎn)延遲時(shí)間和數(shù)據(jù)傳輸時(shí)間三部分構(gòu)成。

磁盤(pán)調(diào)度算法

計(jì)算平均尋道長(zhǎng)度

設(shè)備分配

設(shè)備獨(dú)立性

設(shè)備分配考慮的因素

設(shè)備分配技術(shù)

虛擬設(shè)備

Spooling技術(shù)的組成、特點(diǎn)、舉例

概念

SPOOLing技術(shù)又稱假脫機(jī)技術(shù)，是一種虛擬設(shè)備技術(shù)，它可以把一臺(tái)獨(dú)占設(shè)備改造成為虛擬設(shè)備，在進(jìn)程所需的物理設(shè)備不存在或被占用的情況下，使用該設(shè)備。SPOOLING技術(shù)是對(duì)脫機(jī)輸入，輸出系統(tǒng)的模擬，又稱為假脫機(jī)操作。它是一種用空間換取時(shí)間的資源轉(zhuǎn)換技術(shù)。

組成

image

SPOOLINGing 系統(tǒng)主要由三部分組成：輸入井和輸出井、輸入緩沖區(qū)和輸出緩沖區(qū)、輸入進(jìn)程和輸出進(jìn)程。

1. 輸入井和輸出井: 輸入井和輸出井的存儲(chǔ)區(qū)域是在磁盤(pán)上開(kāi)辟出來(lái)的。輸入輸出井中的數(shù)據(jù)一般以文件的形式組織管理，這些文件稱之為井文件。一個(gè)文件僅存放某一個(gè)進(jìn)程的輸入或輸出數(shù)據(jù)，所有進(jìn)程的數(shù)據(jù)輸入或輸出文件鏈接成為一個(gè)輸入輸出隊(duì)列。
2. 輸入緩沖區(qū)和輸出緩沖區(qū): 輸入緩沖區(qū)和輸出緩沖區(qū)的存儲(chǔ)區(qū)域是在內(nèi)存中開(kāi)辟出來(lái)的。主要用于緩和 CPU 和磁盤(pán)之間速度不匹配的矛盾。輸入緩沖區(qū)用于暫存有輸入設(shè)備傳送的數(shù)據(jù)，之后再傳送到輸入井；輸出緩沖區(qū) 同理。
3. 輸入進(jìn)程和輸出進(jìn)程: 輸入進(jìn)程也稱為預(yù)輸入進(jìn)程，用于模擬脫機(jī)輸入時(shí)的外圍控制機(jī)，將用戶要求的數(shù)據(jù)從輸入設(shè)備傳送到輸入緩沖區(qū)，再存放到輸入井。當(dāng) CPU 需要的時(shí)候，直接從輸入井將數(shù)據(jù)讀入內(nèi)存。反之，輸出的同理。
4. 井管理程序: 用于控制作業(yè)與磁盤(pán)井之間信息的交換。

原理

image

在多道系統(tǒng)中，對(duì)于每一個(gè)獨(dú)占的設(shè)備，專門利用一道程序，即 SPOOLing 程序，來(lái)完成對(duì)這個(gè)設(shè)備的輸入輸出操作。

一方面，SPOOLing 程序負(fù)責(zé)與這個(gè)獨(dú)占的 I/O 設(shè)備進(jìn)行數(shù)據(jù)交換，這可以成為 “實(shí)際的 I/O”。如果這是一個(gè)輸入設(shè)備，那么 SPOOLing 程序預(yù)先從該設(shè)備輸入數(shù)據(jù)并加以緩沖，然后在需要時(shí)再交給應(yīng)用程序。如果這是一個(gè)輸出設(shè)備，那么 SPOOLing 程序會(huì)接受應(yīng)用程序的輸出數(shù)據(jù)并加以緩沖，然后在適當(dāng)?shù)臅r(shí)候再輸出到該設(shè)備。
另一方面，應(yīng)用程序在進(jìn)行 I/O 操作時(shí)，只是與 SPOOLing 程序交換數(shù)據(jù)，這可以稱為 “虛擬的 I/O”。

輸入值班進(jìn)程 SPi 模擬 SPOOLing 輸入時(shí)的外圍控制機(jī)的功能?？刂戚斎朐O(shè)備經(jīng)輸入緩沖區(qū)把用戶的數(shù)據(jù)傳送到備用存儲(chǔ)器的輸入井中，當(dāng)用戶進(jìn)程需要輸入數(shù)據(jù)時(shí)，直接將輸入井中預(yù)存的輸入數(shù)據(jù)讀入內(nèi)存，提供給用戶進(jìn)程使用。
輸出值班進(jìn)程 SPo 模擬 SPOOLing 輸出時(shí)的外圍控制機(jī)的功能。把用戶進(jìn)程的輸出數(shù)據(jù)傳送到備用存儲(chǔ)器的輸出井中，形成輸出請(qǐng)求隊(duì)列?？刂戚敵鼍械臄?shù)據(jù)傳送到低速的輸出設(shè)備。

優(yōu)點(diǎn)

所有字符設(shè)備都是獨(dú)占設(shè)備并屬于慢速設(shè)備，因此，當(dāng)一個(gè)進(jìn)程在某臺(tái)字符設(shè)備上進(jìn)行數(shù)據(jù)交換時(shí)，往往要等待較長(zhǎng)時(shí)間，并且在此進(jìn)程未釋放該設(shè)備之前，其他進(jìn)程不能同時(shí)訪問(wèn)這臺(tái)設(shè)備，從而使這類設(shè)備成為系統(tǒng)中的瓶頸資源，使許多進(jìn)程因等待它們而阻塞。另一方面，分配到字符設(shè)備的進(jìn)程，在其整個(gè)運(yùn)行期間，往往占有這些設(shè)備，卻并不是經(jīng)常使用這些設(shè)備，因而使這些設(shè)備的利用率很低。從而降低了整個(gè)系統(tǒng)的性能。 Spooling技術(shù)正是針對(duì)上述問(wèn)題提出的一種技術(shù)。

• 提高I/O的速度：應(yīng)用程序的虛擬 I/O 比實(shí)際的 I/O 速度要快，因?yàn)樗皇窃趦蓚€(gè)進(jìn)程之前的一種通信，把數(shù)據(jù)從一個(gè)進(jìn)程交給另一個(gè)進(jìn)程。這種數(shù)據(jù)交換是在內(nèi)存中進(jìn)行的，而不是真正地讓機(jī)械的物理設(shè)備去運(yùn)作。這就縮短了應(yīng)用程序的執(zhí)行時(shí)間。對(duì)數(shù)據(jù)執(zhí)行的 I/O 操作，已從對(duì)低速 I/O 設(shè)備執(zhí)行的 I/O 操作演變?yōu)閷?duì)磁盤(pán)緩沖區(qū)中數(shù)據(jù)的存取，如同脫機(jī)輸入輸出一樣，提高了 I/O 速度，緩和了 CPU 和低速的 I/Os 設(shè)備之間速度的不匹配的矛盾。
• 實(shí)現(xiàn)對(duì)獨(dú)占設(shè)備的共享：由 SPOOLing 程序提供虛擬設(shè)備，然后各個(gè)用戶進(jìn)程就可以對(duì)這個(gè)獨(dú)占設(shè)備依次地共享使用。因?yàn)樵诩倜摍C(jī)打印機(jī)系統(tǒng)中，實(shí)際上并沒(méi)有為任何進(jìn)程分配設(shè)備，而只是在磁盤(pán)緩沖區(qū)中為進(jìn)程分配了一個(gè)空閑盤(pán)塊和建立了一張 I/O 請(qǐng)求表。
• 實(shí)現(xiàn)了虛擬設(shè)備功能: 宏觀上，對(duì)于每一個(gè)進(jìn)程而言，它們認(rèn)為是自己獨(dú)占了一個(gè)設(shè)備，即使實(shí)際上是多個(gè)進(jìn)程在同時(shí)使用一臺(tái)獨(dú)占設(shè)備。也可以說(shuō)假脫機(jī)系統(tǒng)實(shí)現(xiàn)了將獨(dú)占設(shè)備變換為若干臺(tái)對(duì)應(yīng)的邏輯設(shè)備的功能。

例子

打印機(jī)就是一種獨(dú)占設(shè)備，在任何時(shí)候只能允許一個(gè)用戶進(jìn)程使用。在現(xiàn)代操作系統(tǒng)中，對(duì)于打印機(jī)設(shè)備，普遍采用了 SPOOLing 技術(shù)。具體來(lái)說(shuō)，首先創(chuàng)建一個(gè) SPOOLing 進(jìn)程，或稱后臺(tái)打印程序，以及一個(gè) SPOOLing 目錄。當(dāng)一個(gè)進(jìn)程需要打印一個(gè)文件時(shí)，首先會(huì)生成將要打印的文件，并把它放入到 SPOOLing 目錄中，然后由這個(gè)后臺(tái)打印進(jìn)程來(lái)負(fù)責(zé)真正的打印操作。

文件管理

文件管理的意義

由于系統(tǒng)的內(nèi)存有限并且不能長(zhǎng)期保存，故平時(shí)總是把它們以文件的形式存放在外存中，需要時(shí)再將它們調(diào)入內(nèi)存。

文件系統(tǒng)的功能

文件系統(tǒng)的主要作用是用于明確磁盤(pán)或分區(qū)上的文件的方法和數(shù)據(jù)結(jié)構(gòu)，即在磁盤(pán)上組織文件的方法。

• 存儲(chǔ)和管理文件：如創(chuàng)建/刪除文件，對(duì)文件的各種操作等
• 目錄管理：如創(chuàng)建/刪除目錄項(xiàng)，權(quán)限驗(yàn)證等
• 文件存儲(chǔ)空間的管理：如外存空間的分配與回收
• 文件共享和保護(hù)
• 提供方便的接口：如實(shí)現(xiàn)按名存取,文件系統(tǒng)調(diào)用等

文件

文件是具有文件名的一組相關(guān)元素的集合，分為有結(jié)構(gòu)文件和無(wú)結(jié)構(gòu)文件。

文件的邏輯結(jié)構(gòu)及分類

• 無(wú)結(jié)構(gòu)文件
• 有結(jié)構(gòu)文件
  • 順序文件
  • 索引文件
  • 索引順序文件
  • 散列文件

文件的物理結(jié)構(gòu)及分類

• 順序結(jié)構(gòu)
• 鏈接結(jié)構(gòu)
  • 隱式鏈接
  • 顯式鏈接：FAT表
  • 索引結(jié)構(gòu)

文件存儲(chǔ)空間的管理方法

• 空閑表法
• 空閑鏈表法
• 位示圖

文件目錄

目錄管理的要求

文件控制塊

索引節(jié)點(diǎn)

成組鏈接法的空閑盤(pán)快的組織、分配回收過(guò)程

文件系統(tǒng)目錄結(jié)構(gòu)

為了給用戶提供對(duì)文件的存取控制及保護(hù)功能，而按一定規(guī)則對(duì)系統(tǒng)中的文件名，(亦可包含文件屬性)進(jìn)行組織所形成的表，稱為目錄表或文件目錄。目前操作系統(tǒng)采用的目錄結(jié)構(gòu)是樹(shù)型目錄結(jié)構(gòu)，它的優(yōu)點(diǎn)有：有效地提高對(duì)目錄的檢索速度；允許文件重名；便于實(shí)現(xiàn)文件共享。

文件分配的方法/數(shù)據(jù)塊組織方式

• 連續(xù)方式：一次寫(xiě)入不存在插入問(wèn)題，而且寫(xiě)入文件之后不需要修改，連續(xù)的數(shù)據(jù)塊組織方式很適合一次性寫(xiě)入磁盤(pán)不再修改的情況，同時(shí)連續(xù)存儲(chǔ)相對(duì)鏈?zhǔn)胶退饕∪チ酥羔樀目臻g開(kāi)銷，支持隨機(jī)查找，查找速度最快。
• 鏈接塊方式：
• 索引方式：

參考資料

• http://blog.csdn.net/gatieme/article/details/51892437
• [操作系統(tǒng)] 三種實(shí)現(xiàn)線程的方式
• 內(nèi)核線程與用戶線程的一點(diǎn)小總結(jié) 《程序員的自我修養(yǎng)》· 筆記
• 分段和分頁(yè)
• 幾個(gè)常用的操作系統(tǒng)進(jìn)程調(diào)度算法
• 操作系統(tǒng)之內(nèi)存管理
• 操作系統(tǒng)內(nèi)存管理——分區(qū)、頁(yè)式、段式管理
• IPC.md
• 操作系統(tǒng)（九）：虛擬內(nèi)存