程序員的自我修養(yǎng)――操作系統(tǒng)篇

　　也許，只需這一篇文章，便能讓你全面的認(rèn)識操作系統(tǒng)！

　　在閱讀本文之前，推薦閱讀“自己動(dòng)手制作4位計(jì)算機(jī)”。

目錄：

1. 進(jìn)程的有哪幾種狀態(tài)，狀態(tài)轉(zhuǎn)換圖，及導(dǎo)致轉(zhuǎn)換的事件。

2. 進(jìn)程與線程的區(qū)別。

3. 進(jìn)程通信的幾種方式。

4. 線程同步幾種方式。

5. 線程的實(shí)現(xiàn)方式. (用戶線程與內(nèi)核線程的區(qū)別)

6. 用戶態(tài)和核心態(tài)的區(qū)別。

7. 用戶棧和內(nèi)核棧的區(qū)別。

8. 內(nèi)存池、進(jìn)程池、線程池。

9. 死鎖的概念，導(dǎo)致死鎖的原因，導(dǎo)致死鎖的四個(gè)必要條件，處理死鎖的四個(gè)方式，預(yù)防死鎖的方法、避免死鎖的方法。

10. 進(jìn)程調(diào)度算法。

11. Windows內(nèi)存管理的方式(塊式、頁式、段式、段頁式).

12. 內(nèi)存連續(xù)分配方式采用的幾種算法及各自優(yōu)劣。

13. 動(dòng)態(tài)鏈接及靜態(tài)鏈接.

14. 基本分頁、請求分頁儲存管理方式。

15. 基本分段、請求分段儲存管理方式。

16. 分段分頁方式的比較各自優(yōu)缺點(diǎn)。

17. 幾種頁面置換算法，會算所需換頁數(shù)。(LRU用程序如何實(shí)現(xiàn)？)

18. 虛擬內(nèi)存的定義及實(shí)現(xiàn)方式。

19. 操作系統(tǒng)的四個(gè)特性。

20. DMA。

21. Spooling。

22. 外存分配的幾種方式，及各種優(yōu)劣。

　　操作系統(tǒng)是管理計(jì)算機(jī)硬件與軟件資源的計(jì)算機(jī)程序，同時(shí)也是計(jì)算機(jī)系統(tǒng)的內(nèi)核與基石。操作系統(tǒng)需要處理管理與配置內(nèi)存、決定系統(tǒng)資源供需的優(yōu)先次序、控制輸入與輸出設(shè)備、操作網(wǎng)絡(luò)與管理文件系統(tǒng)等基本事務(wù)。操作系統(tǒng)也提供一個(gè)讓用戶與系統(tǒng)交互的操作界面。

　　操作系統(tǒng)上運(yùn)行的計(jì)算機(jī)程序通常由一個(gè)或一組進(jìn)程組成。因此，本文便從進(jìn)程開始說起！

　　1.進(jìn)程的有哪幾種狀態(tài)，狀態(tài)轉(zhuǎn)換圖，及導(dǎo)致轉(zhuǎn)換的事件。

　　如上圖所示，進(jìn)程包括三種狀態(tài)：就緒態(tài)、運(yùn)行態(tài)和阻塞態(tài)。詳細(xì)說明如下：

　　注意：創(chuàng)建和退出不是進(jìn)程的狀態(tài)。阻塞也叫等待，等待和就緒的區(qū)別：等待是等待除CPU以外的資源，而就緒等待的是CPU資源。

　　1）就緒——執(zhí)行：對就緒狀態(tài)的進(jìn)程，當(dāng)進(jìn)程調(diào)度程序按一種選定的策略從中選中一個(gè)就緒進(jìn)程，為之分配了處理機(jī)后，該進(jìn)程便由就緒狀態(tài)變?yōu)閳?zhí)行狀態(tài)；

　　2）執(zhí)行——等待：正在執(zhí)行的進(jìn)程因發(fā)生某等待事件而無法執(zhí)行，則進(jìn)程由執(zhí)行狀態(tài)變?yōu)榈却隣顟B(tài)，如進(jìn)程提出輸入/輸出請求而變成等待外部設(shè)備傳輸信息的狀態(tài)，進(jìn)程申請資源（主存空間或外部設(shè)備）得不到滿足時(shí)變成等待資源狀態(tài)，進(jìn)程運(yùn)行中出現(xiàn)了故障（程序出錯(cuò)或主存儲器讀寫錯(cuò)等）變成等待干預(yù)狀態(tài)等等；

　　3）等待——就緒：處于等待狀態(tài)的進(jìn)程，在其等待的事件已經(jīng)發(fā)生，如輸入/輸出完成，資源得到滿足或錯(cuò)誤處理完畢時(shí)，處于等待狀態(tài)的進(jìn)程并不馬上轉(zhuǎn)入執(zhí)行狀態(tài)，而是先轉(zhuǎn)入就緒狀態(tài)，然后再由系統(tǒng)進(jìn)程調(diào)度程序在適當(dāng)?shù)臅r(shí)候?qū)⒃撨M(jìn)程轉(zhuǎn)為執(zhí)行狀態(tài)；

　　4）執(zhí)行——就緒：正在執(zhí)行的進(jìn)程，因時(shí)間片用完而被暫停執(zhí)行，或在采用搶先式優(yōu)先級調(diào)度算法的系統(tǒng)中,當(dāng)有更高優(yōu)先級的進(jìn)程要運(yùn)行而被迫讓出處理機(jī)時(shí)，該進(jìn)程便由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)榫途w狀態(tài)。

　　2.進(jìn)程與線程的區(qū)別。

　　詳見快課之前分享的文章：

　　進(jìn)程與線程的圖文描述

　　進(jìn)程和線程的區(qū)別

　　3.進(jìn)程通信的幾種方式。

　　以linux操作系統(tǒng)為例(window也類似)，linux下進(jìn)程間通信方式如下：

　　1管道（Pipe）及有名管道（namedpipe）：管道可用于具有親緣關(guān)系進(jìn)程間的通信，有名管道克服了管道沒有名字的限制，因此，除具有管道所具有的功能外，它還允許無親緣關(guān)系進(jìn)程間的通信；

　　2信號（Signal）：信號是比較復(fù)雜的通信方式，用于通知接受進(jìn)程有某種事件發(fā)生，除了用于進(jìn)程間通信外，進(jìn)程還可以發(fā)送信號給進(jìn)程本身；linux除了支持Unix早期信號語義函數(shù)sigal外，還支持語義符合Posix.1標(biāo)準(zhǔn)的信號函數(shù)sigaction（實(shí)際上，該函數(shù)是基于BSD的，BSD為了實(shí)現(xiàn)可靠信號機(jī)制，又能夠統(tǒng)一對外接口，用sigaction函數(shù)重新實(shí)現(xiàn)了signal函數(shù)）；

　　3報(bào)文（Message）隊(duì)列（消息隊(duì)列）：消息隊(duì)列是消息的鏈接表，包括Posix消息隊(duì)列systemV消息隊(duì)列。有足夠權(quán)限的進(jìn)程可以向隊(duì)列中添加消息，被賦予讀權(quán)限的進(jìn)程則可以讀走隊(duì)列中的消息。消息隊(duì)列克服了信號承載信息量少，管道只能承載無格式字節(jié)流以及緩沖區(qū)大小受限等缺點(diǎn)。

　　4共享內(nèi)存：使得多個(gè)進(jìn)程可以訪問同一塊內(nèi)存空間，是最快的可用IPC形式。是針對其他通信機(jī)制運(yùn)行效率較低而設(shè)計(jì)的。往往與其它通信機(jī)制，如信號量結(jié)合使用，來達(dá)到進(jìn)程間的同步及互斥。

　　5信號量（semaphore）：主要作為進(jìn)程間以及同一進(jìn)程不同線程之間的同步手段。

　　6套接口（Socket）：更為一般的進(jìn)程間通信機(jī)制，可用于不同機(jī)器之間的進(jìn)程間通信。起初是由Unix系統(tǒng)的BSD分支開發(fā)出來的，但現(xiàn)在一般可以移植到其它類Unix系統(tǒng)上：Linux和SystemV的變種都支持套接字。

　　4.線程同步幾種方式。

　　線程同步的方式主要有以下四種:臨界區(qū)（CriticalSection）、互斥量（Mutex）、信號量（Semaphore）、事件（Event）的區(qū)別。

　　他們的主要區(qū)別和特點(diǎn)如下：

　　1）臨界區(qū)：通過對多線程的串行化來訪問公共資源或一段代碼，速度快，適合控制數(shù)據(jù)訪問。在任意時(shí)刻只允許一個(gè)線程對共享資源進(jìn)行訪問，如果有多個(gè)線程試圖訪問公共資源，那么在有一個(gè)線程進(jìn)入后，其他試圖訪問公共資源的線程將被掛起，并一直等到進(jìn)入臨界區(qū)的線程離開，臨界區(qū)在被釋放后，其他線程才可以搶占。

　　2）互斥量：采用互斥對象機(jī)制。只有擁有互斥對象的線程才有訪問公共資源的權(quán)限，因?yàn)榛コ鈱ο笾挥幸粋€(gè)，所以能保證公共資源不會同時(shí)被多個(gè)線程訪問。互斥不僅能實(shí)現(xiàn)同一應(yīng)用程序的公共資源安全共享，還能實(shí)現(xiàn)不同應(yīng)用程序的公共資源安全共享。

　　3）信號量：它允許多個(gè)線程在同一時(shí)刻訪問同一資源，但是需要限制在同一時(shí)刻訪問此資源的最大線程數(shù)目。

　　4）事件：通過通知操作的方式來保持線程的同步，還可以方便實(shí)現(xiàn)對多個(gè)線程的優(yōu)先級比較的操作。

　　5.線程的實(shí)現(xiàn)方式.(換種方式說即：用戶線程與內(nèi)核線程的區(qū)別)

　　線程的實(shí)現(xiàn)可以分為兩類：用戶級線程(User-LevelThread)和內(nèi)核線線程(Kernel-LevelThread)，后者又稱為內(nèi)核支持的線程或輕量級進(jìn)程。在多線程操作系統(tǒng)中，各個(gè)系統(tǒng)的實(shí)現(xiàn)方式并不相同，在有的系統(tǒng)中實(shí)現(xiàn)了用戶級線程，有的系統(tǒng)中實(shí)現(xiàn)了內(nèi)核級線程。

　　用戶線程指不需要內(nèi)核支持而在用戶程序中實(shí)現(xiàn)的線程，其不依賴于操作系統(tǒng)核心，應(yīng)用進(jìn)程利用線程庫提供創(chuàng)建、同步、調(diào)度和管理線程的函數(shù)來控制用戶線程。不需要用戶態(tài)/核心態(tài)切換，速度快，操作系統(tǒng)內(nèi)核不知道多線程的存在，因此一個(gè)線程阻塞將使得整個(gè)進(jìn)程（包括它的所有線程）阻塞。由于這里的處理器時(shí)間片分配是以進(jìn)程為基本單位，所以每個(gè)線程執(zhí)行的時(shí)間相對減少。

　　內(nèi)核線程：由操作系統(tǒng)內(nèi)核創(chuàng)建和撤銷。內(nèi)核維護(hù)進(jìn)程及線程的上下文信息以及線程切換。一個(gè)內(nèi)核線程由于I/O操作而阻塞，不會影響其它線程的運(yùn)行。

　　以下是用戶級線程和內(nèi)核級線程的區(qū)別：

　　1）內(nèi)核支持線程是OS內(nèi)核可感知的，而用戶級線程是OS內(nèi)核不可感知的。

　　2）用戶級線程的創(chuàng)建、撤消和調(diào)度不需要OS內(nèi)核的支持，是在語言（如Java）這一級處理的；而內(nèi)核支持線程的創(chuàng)建、撤消和調(diào)度都需OS內(nèi)核提供支持，而且與進(jìn)程的創(chuàng)建、撤消和調(diào)度大體是相同的。

　　3）用戶級線程執(zhí)行系統(tǒng)調(diào)用指令時(shí)將導(dǎo)致其所屬進(jìn)程被中斷，而內(nèi)核支持線程執(zhí)行系統(tǒng)調(diào)用指令時(shí)，只導(dǎo)致該線程被中斷。

　　4）在只有用戶級線程的系統(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)度。

　　5）用戶級線程的程序?qū)嶓w是運(yùn)行在用戶態(tài)下的程序，而內(nèi)核支持線程的程序?qū)嶓w則是可以運(yùn)行在任何狀態(tài)下的程序。

　　6.用戶態(tài)和核心態(tài)的區(qū)別。

　　在講述用戶態(tài)和核心態(tài)的區(qū)別之前，我們先要說說“特權(quán)級”的概念。

　　熟悉Unix/Linux系統(tǒng)的人都知道，我們創(chuàng)建一個(gè)子進(jìn)程時(shí)，是通過調(diào)用fork函數(shù)來實(shí)現(xiàn)的。事實(shí)上，fork的工作實(shí)際上是以系統(tǒng)調(diào)用的方式完成進(jìn)程創(chuàng)建功能的，具體的工作是由sys_fork負(fù)責(zé)實(shí)施。對于任何操作系統(tǒng)來說，創(chuàng)建一個(gè)新的進(jìn)程都是屬于核心功能，因?yàn)樗龊芏嗟讓蛹?xì)致地工作，消耗系統(tǒng)的物理資源，比如分配物理內(nèi)存，從父進(jìn)程拷貝相關(guān)信息，拷貝設(shè)置頁目錄頁表等等，這些顯然不能隨便讓哪個(gè)程序就能去做，于是就自然引出特權(quán)級別的概念，顯然，最關(guān)鍵性的權(quán)力必須由高特權(quán)級的程序來執(zhí)行，這樣才可以做到集中管理，減少有限資源的訪問和使用沖突。

　　特權(quán)級顯然是非常有效的管理和控制程序執(zhí)行的手段，因此在硬件上對特權(quán)級做了很多支持，就Intelx86架構(gòu)的CPU來說一共有0~3四個(gè)特權(quán)級，0級最高，3級最低，硬件上在執(zhí)行每條指令時(shí)都會對指令所具有的特權(quán)級做相應(yīng)的檢查，相關(guān)的概念有CPL、DPL和RPL，這里不再過多闡述。硬件已經(jīng)提供了一套特權(quán)級使用的相關(guān)機(jī)制，軟件自然就是好好利用的問題，這屬于操作系統(tǒng)要做的事情，對于Unix/Linux來說，只使用了0級特權(quán)級和3級特權(quán)級。也就是說在Unix/Linux系統(tǒng)中，一條工作在0級特權(quán)級的指令具有了CPU能提供的最高權(quán)力，而一條工作在3級特權(quán)級的指令具有CPU提供的最低或者說最基本權(quán)力。

　　OK，有了上面對“特權(quán)級”概念的了解，就能更直觀的了解用戶態(tài)和核心態(tài)的區(qū)別。內(nèi)核態(tài)與用戶態(tài)是操作系統(tǒng)的兩種運(yùn)行級別,，當(dāng)程序運(yùn)行在3級特權(quán)級上時(shí)，就可以稱之為運(yùn)行在用戶態(tài)，因?yàn)檫@是最低特權(quán)級，是普通的用戶進(jìn)程運(yùn)行的特權(quán)級，大部分用戶直接面對的程序都是運(yùn)行在用戶態(tài)；反之，當(dāng)程序運(yùn)行在0級特權(quán)級上時(shí)，就可以稱之為運(yùn)行在內(nèi)核態(tài)。運(yùn)行在用戶態(tài)下的程序不能直接訪問操作系統(tǒng)內(nèi)核數(shù)據(jù)結(jié)構(gòu)和程序。當(dāng)我們在系統(tǒng)中執(zhí)行一個(gè)程序時(shí)，大部分時(shí)間是運(yùn)行在用戶態(tài)下的，在其需要操作系統(tǒng)幫助完成某些它沒有權(quán)力和能力完成的工作時(shí)就會切換到內(nèi)核態(tài)。通常來說，以下三種情況會導(dǎo)致用戶態(tài)到內(nèi)核態(tài)的切換：

　　1）系統(tǒng)調(diào)用

　　這是用戶態(tài)進(jìn)程主動(dòng)要求切換到內(nèi)核態(tài)的一種方式，用戶態(tài)進(jìn)程通過系統(tǒng)調(diào)用申請使用操作系統(tǒng)提供的服務(wù)程序完成工作，比如前例中fork()實(shí)際上就是執(zhí)行了一個(gè)創(chuàng)建新進(jìn)程的系統(tǒng)調(diào)用。而系統(tǒng)調(diào)用的機(jī)制其核心還是使用了操作系統(tǒng)為用戶特別開放的一個(gè)中斷來實(shí)現(xiàn)，例如Linux的int80h中斷。

　　2）異常

　　當(dāng)CPU在執(zhí)行運(yùn)行在用戶態(tài)下的程序時(shí)，發(fā)生了某些事先不可知的異常，這時(shí)會觸發(fā)由當(dāng)前運(yùn)行進(jìn)程切換到處理此異常的內(nèi)核相關(guān)程序中，也就轉(zhuǎn)到了內(nèi)核態(tài)，比如缺頁異常。

　　3）外圍設(shè)備的中斷

　　當(dāng)外圍設(shè)備完成用戶請求的操作后，會向CPU發(fā)出相應(yīng)的中斷信號，這時(shí)CPU會暫停執(zhí)行下一條即將要執(zhí)行的指令轉(zhuǎn)而去執(zhí)行與中斷信號對應(yīng)的處理程序，如果先前執(zhí)行的指令是用戶態(tài)下的程序，那么這個(gè)轉(zhuǎn)換的過程自然也就發(fā)生了由用戶態(tài)到內(nèi)核態(tài)的切換。比如硬盤讀寫操作完成，系統(tǒng)會切換到硬盤讀寫的中斷處理程序中執(zhí)行后續(xù)操作等。

　　這3種方式是系統(tǒng)在運(yùn)行時(shí)由用戶態(tài)轉(zhuǎn)到內(nèi)核態(tài)的最主要方式，其中系統(tǒng)調(diào)用可以認(rèn)為是用戶進(jìn)程主動(dòng)發(fā)起的，異常和外圍設(shè)備中斷則是被動(dòng)的。

　　7.用戶棧和內(nèi)核棧的區(qū)別。

　　操作系統(tǒng)中，每個(gè)進(jìn)程會有兩個(gè)棧，一個(gè)用戶棧，存在于用戶空間，一個(gè)內(nèi)核棧，存在于內(nèi)核空間。當(dāng)進(jìn)程在用戶空間運(yùn)行時(shí)，cpu堆棧指針寄存器里面的內(nèi)容是用戶堆棧地址，使用用戶棧；當(dāng)進(jìn)程在內(nèi)核空間時(shí)，cpu堆棧指針寄存器里面的內(nèi)容是內(nèi)核棧空間地址，使用內(nèi)核棧。

　　內(nèi)核棧是內(nèi)存中屬于操作系統(tǒng)空間的一塊區(qū)域，其主要用途為：

　　1)保存中斷現(xiàn)場，對于嵌套中斷，被中斷程序的現(xiàn)場信息依次壓入系統(tǒng)棧，中斷返回時(shí)逆序彈出；

　　2)保存操作系統(tǒng)子程序間相互調(diào)用的參數(shù)、返回值、返回點(diǎn)以及子程序(函數(shù))的局部變量。

　　用戶棧是用戶進(jìn)程空間中的一塊區(qū)域，用于保存用戶進(jìn)程的子程序間相互調(diào)用的參數(shù)、返回值、返回點(diǎn)以及子程序(函數(shù))的局部變量。

　　PS：那么為什么不直接用一個(gè)棧，何必浪費(fèi)那么多的空間呢？

　　1）如果只用系統(tǒng)棧。系統(tǒng)棧一般大小有限，如果中斷有16個(gè)優(yōu)先級，那么系統(tǒng)棧一般大小為15（只需保存15個(gè)低優(yōu)先級的中斷，另一個(gè)高優(yōu)先級中斷處理程序處于運(yùn)行），但用戶程序子程序調(diào)用次數(shù)可能很多，那樣15次子程序調(diào)用以后的子程序調(diào)用的參數(shù)、返回值、返回點(diǎn)以及子程序(函數(shù))的局部變量就不能被保存，用戶程序也就無法正常運(yùn)行了。

　　2）如果只用用戶棧。我們知道系統(tǒng)程序需要在某種保護(hù)下運(yùn)行，而用戶棧在用戶空間（即cpu處于用戶態(tài)，而cpu處于核心態(tài)時(shí)是受保護(hù)的），不能提供相應(yīng)的保護(hù)措施（或相當(dāng)困難）。

　　8.內(nèi)存池、進(jìn)程池、線程池。

　　首先介紹一個(gè)概念“池化技術(shù)”。池化技術(shù)一言以蔽之就是：提前保存大量的資源，以備不時(shí)之需以及重復(fù)使用。池化技術(shù)應(yīng)用廣泛，如內(nèi)存池，線程池，連接池等等。內(nèi)存池相關(guān)的內(nèi)容，建議看看Apache、Nginx等開源web服務(wù)器的內(nèi)存池實(shí)現(xiàn)。

　　由于在實(shí)際應(yīng)用當(dāng)做，分配內(nèi)存、創(chuàng)建進(jìn)程、線程都會設(shè)計(jì)到一些系統(tǒng)調(diào)用，系統(tǒng)調(diào)用需要導(dǎo)致程序從用戶態(tài)切換到內(nèi)核態(tài)，是非常耗時(shí)的操作。因此，當(dāng)程序中需要頻繁的進(jìn)行內(nèi)存申請釋放，進(jìn)程、線程創(chuàng)建銷毀等操作時(shí)，通常會使用內(nèi)存池、進(jìn)程池、線程池技術(shù)來提升程序的性能。

　　線程池：線程池的原理很簡單，類似于操作系統(tǒng)中的緩沖區(qū)的概念，它的流程如下：先啟動(dòng)若干數(shù)量的線程，并讓這些線程都處于睡眠狀態(tài)，當(dāng)需要一個(gè)開辟一個(gè)線程去做具體的工作時(shí)，就會喚醒線程池中的某一個(gè)睡眠線程，讓它去做具體工作，當(dāng)工作完成后，線程又處于睡眠狀態(tài)，而不是將線程銷毀。

　　進(jìn)程池與線程池同理。

　　內(nèi)存池：內(nèi)存池是指程序預(yù)先從操作系統(tǒng)申請一塊足夠大內(nèi)存，此后，當(dāng)程序中需要申請內(nèi)存的時(shí)候，不是直接向操作系統(tǒng)申請，而是直接從內(nèi)存池中獲取；同理，當(dāng)程序釋放內(nèi)存的時(shí)候，并不真正將內(nèi)存返回給操作系統(tǒng)，而是返回內(nèi)存池。當(dāng)程序退出(或者特定時(shí)間)時(shí)，內(nèi)存池才將之前申請的真正內(nèi)存釋放。

　　9.死鎖的概念，導(dǎo)致死鎖的原因，導(dǎo)致死鎖的四個(gè)必要條件，預(yù)防死鎖的方法、避免死鎖的方法

　　計(jì)算機(jī)系統(tǒng)中,如果系統(tǒng)的資源分配策略不當(dāng)，更常見的可能是程序員寫的程序有錯(cuò)誤等，則會導(dǎo)致進(jìn)程因競爭資源不當(dāng)而產(chǎn)生死鎖的現(xiàn)象。

　　產(chǎn)生死鎖的原因主要是：

　　1）因?yàn)橄到y(tǒng)資源不足。

　　2）進(jìn)程運(yùn)行推進(jìn)的順序不合適。

　　3）資源分配不當(dāng)?shù)取?/p>

　　如果系統(tǒng)資源充足，進(jìn)程的資源請求都能夠得到滿足，死鎖出現(xiàn)的可能性就很低，否則就會因爭奪有限的資源而陷入死鎖。其次，進(jìn)程運(yùn)行推進(jìn)順序與速度不同，也可能產(chǎn)生死鎖。

　　產(chǎn)生死鎖的四個(gè)必要條件：

　　1）互斥條件：一個(gè)資源每次只能被一個(gè)進(jìn)程使用。

　　2）請求與保持條件：一個(gè)進(jìn)程因請求資源而阻塞時(shí)，對已獲得的資源保持不放。

　　3）不剝奪條件:進(jìn)程已獲得的資源，在末使用完之前，不能強(qiáng)行剝奪。

　　4）循環(huán)等待條件:若干進(jìn)程之間形成一種頭尾相接的循環(huán)等待資源關(guān)系。

　　這四個(gè)條件是死鎖的必要條件，只要系統(tǒng)發(fā)生死鎖，這些條件必然成立，而只要上述條件之一不滿足，就不會發(fā)生死鎖。

　　死鎖的解除與預(yù)防：

　　理解了死鎖的原因，尤其是產(chǎn)生死鎖的四個(gè)必要條件，就可以最大可能地避免、預(yù)防和解除死鎖。所以，在系統(tǒng)設(shè)計(jì)、進(jìn)程調(diào)度等方面注意如何不讓這四個(gè)必要條件成立，如何確定資源的合理分配算法，避免進(jìn)程永久占據(jù)系統(tǒng)資源。

　　此外，也要防止進(jìn)程在處于等待狀態(tài)的情況下占用資源,在系統(tǒng)運(yùn)行過程中，對進(jìn)程發(fā)出的每一個(gè)系統(tǒng)能夠滿足的資源申請進(jìn)行動(dòng)態(tài)檢查，并根據(jù)檢查結(jié)果決定是否分配資源，若分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配。因此，對資源的分配要給予合理的規(guī)劃。

　　10.進(jìn)程調(diào)度算法。

　　幾種進(jìn)程調(diào)度算法：

　　一、先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法

　　1.先來先服務(wù)調(diào)度算法。先來先服務(wù)（FCFS）調(diào)度算法是一種最簡單的調(diào)度算法，該算法既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。FCFS算法比較有利于長作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）。由此可知，本算法適合于CPU繁忙型作業(yè)，而不利于I/O繁忙型的作業(yè)（進(jìn)程）。　　2.短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法。短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法（SJ/PF）是指對短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法，該算法既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。但其對長作業(yè)不利；不能保證緊迫性作業(yè)（進(jìn)程）被及時(shí)處理；作業(yè)的長短只是被估算出來的。

　　二、高優(yōu)先權(quán)優(yōu)先調(diào)度算法

　　1.優(yōu)先權(quán)調(diào)度算法的類型。為了照顧緊迫性作業(yè)，使之進(jìn)入系統(tǒng)后便獲得優(yōu)先處理，引入了最高優(yōu)先權(quán)優(yōu)先（FPF）調(diào)度算法。此算法常被用在批處理系統(tǒng)中，作為作業(yè)調(diào)度算法，也作為多種操作系統(tǒng)中的進(jìn)程調(diào)度，還可以用于實(shí)時(shí)系統(tǒng)中。當(dāng)其用于作業(yè)調(diào)度，將后備隊(duì)列中若干個(gè)優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。當(dāng)其用于進(jìn)程調(diào)度時(shí)，把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程，此時(shí)，又可以進(jìn)一步把該算法分成以下兩種：

　　1)非搶占式優(yōu)先權(quán)算法

　　2)搶占式優(yōu)先權(quán)調(diào)度算法（高性能計(jì)算機(jī)操作系統(tǒng)）

　　2.優(yōu)先權(quán)類型

　　對于最高優(yōu)先權(quán)優(yōu)先調(diào)度算法，其核心在于：它是使用靜態(tài)優(yōu)先權(quán)還是動(dòng)態(tài)優(yōu)先權(quán)，以及如何確定進(jìn)程的優(yōu)先權(quán)。

　　3.高響應(yīng)比優(yōu)先調(diào)度算法

　　為了彌補(bǔ)短作業(yè)優(yōu)先算法的不足，我們引入動(dòng)態(tài)優(yōu)先權(quán)，使作業(yè)的優(yōu)先等級隨著等待時(shí)間的增加而以速率a提高。該優(yōu)先權(quán)變化規(guī)律可描述為：優(yōu)先權(quán)=（等待時(shí)間+要求服務(wù)時(shí)間）/要求服務(wù)時(shí)間；即=（響應(yīng)時(shí)間）/要求服務(wù)時(shí)間

　　三、基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法

　　1.時(shí)間片輪轉(zhuǎn)法。時(shí)間片輪轉(zhuǎn)法一般用于進(jìn)程調(diào)度，每次調(diào)度，把CPU分配隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)記時(shí)器發(fā)出一個(gè)時(shí)鐘中斷請求，該進(jìn)程被停止，并被送往就緒隊(duì)列末尾；依次循環(huán)。

　　2.多級反饋隊(duì)列調(diào)度算法多級反饋隊(duì)列調(diào)度算法多級反饋隊(duì)列調(diào)度算法，不必事先知道各種進(jìn)程所需要執(zhí)行的時(shí)間，它是目前被公認(rèn)的一種較好的進(jìn)程調(diào)度算法。其實(shí)施過程如下：

　　1)設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級。在優(yōu)先權(quán)越高的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就越小。

　　2)當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先放入第一隊(duì)列的末尾，按FCFS原則排隊(duì)等候調(diào)度。如果他能在一個(gè)時(shí)間片中完成，便可撤離；如果未完成，就轉(zhuǎn)入第二隊(duì)列的末尾，在同樣等待調(diào)度……如此下去，當(dāng)一個(gè)長作業(yè)（進(jìn)程）從第一隊(duì)列依次將到第n隊(duì)列（最后隊(duì)列）后，便按第n隊(duì)列時(shí)間片輪轉(zhuǎn)運(yùn)行。

　　3)僅當(dāng)?shù)谝魂?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)?到第（i-1）隊(duì)列空時(shí)，才會調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行，并執(zhí)行相應(yīng)的時(shí)間片輪轉(zhuǎn)。

　　4)如果處理機(jī)正在處理第i隊(duì)列中某進(jìn)程，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列，則此新隊(duì)列搶占正在運(yùn)行的處理機(jī)，并把正在運(yùn)行的進(jìn)程放在第i隊(duì)列的隊(duì)尾。

　　11.Windows內(nèi)存管理的方式(塊式、頁式、段式、段頁式).

　　塊式管理

　　把主存分為一大塊、一大塊的，當(dāng)所需的程序片斷不在主存時(shí)就分配一塊主存空間，把程序片斷載入主存，就算所需的程序片度只有幾個(gè)字節(jié)也只能把這一塊分配給它。這樣會造成很大的浪費(fèi)，但時(shí)易于管理。

　　頁式管理

　　把主存分為一頁一頁的，每一頁的空間要比一塊一塊的空間小很多，顯然這種方法的空間利用率要比塊式管理高很多。

　　段式

　　把主存分為一段一段的，每一段的空間又要比一頁一頁的空間小很多，這種方法在空間利用率上又比頁式管理高很多，但是也有另外一個(gè)缺點(diǎn)。一個(gè)程序片斷可能會被分為幾十段，這樣很多時(shí)間就會被浪費(fèi)在計(jì)算每一段的物理地址上（計(jì)算機(jī)最耗時(shí)間的大家都知道是I/O吧）。

　　段頁式管理。(現(xiàn)在常用)

　　結(jié)合了段式管理和頁式管理的優(yōu)點(diǎn)。把主存分為若干頁，每一頁又分為若干段。

　　12.內(nèi)存連續(xù)分配方式采用的幾種算法及各自優(yōu)劣。

　　內(nèi)存的連續(xù)分配方式有：單一連續(xù)分配、固定分區(qū)分配、動(dòng)態(tài)分區(qū)分配以及動(dòng)態(tài)重定位分區(qū)分配四種方式。

　　單一連續(xù)分配：只能用于單用戶、單任務(wù)的操作系統(tǒng)中。

　　固定分區(qū)分配：可運(yùn)行多道程序的存儲管理方式。

　　動(dòng)態(tài)分區(qū)分配：根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)地為之分配內(nèi)存空間。

　　可重定位分區(qū)分配：必須把一個(gè)系統(tǒng)或用戶程序裝入一連續(xù)的內(nèi)存空間。

　　13.動(dòng)態(tài)鏈接及靜態(tài)鏈接。

　　靜態(tài)鏈接就是在編譯鏈接時(shí)直接將需要的執(zhí)行代碼拷貝到調(diào)用處，優(yōu)點(diǎn)就是在程序發(fā)布的時(shí)候就不需要的依賴庫，也就是不再需要帶著庫一塊發(fā)布，程序可以獨(dú)立執(zhí)行，但是體積可能會相對大一些。

　　動(dòng)態(tài)鏈接就是在編譯的時(shí)候不直接拷貝可執(zhí)行代碼，而是通過記錄一系列符號和參數(shù)，在程序運(yùn)行或加載時(shí)將這些信息傳遞給操作系統(tǒng)，操作系統(tǒng)負(fù)責(zé)將需要的動(dòng)態(tài)庫加載到內(nèi)存中，然后程序在運(yùn)行到指定的代碼時(shí)，去共享執(zhí)行內(nèi)存中已經(jīng)加載的動(dòng)態(tài)庫可執(zhí)行代碼，最終達(dá)到運(yùn)行時(shí)連接的目的。優(yōu)點(diǎn)是多個(gè)程序可以共享同一段代碼，而不需要在磁盤上存儲多個(gè)拷貝，缺點(diǎn)是由于是運(yùn)行時(shí)加載，可能會影響程序的前期執(zhí)行性能。

　　14.基本分頁、請求分頁儲存管理方式。

　　基本分頁儲存管理方式具有如下特征：

　　1)一次性。要求將作業(yè)全部裝入內(nèi)存后方能運(yùn)行。許多作業(yè)在每次運(yùn)行時(shí)，并非其全部程序和數(shù)據(jù)都要用到。如果一次性地裝入其全部程序，造成內(nèi)存空間的浪費(fèi)。

　　2)駐留性。作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存中，直至作業(yè)運(yùn)行結(jié)束。盡管運(yùn)行中的進(jìn)程會因I/O而長期等待，或有的程序模塊在運(yùn)行過一次后就不再需要(運(yùn)行)了，但它們都仍將繼續(xù)占用寶貴的內(nèi)存資源。

　　請求分頁儲存管理是實(shí)現(xiàn)虛擬存儲器的一種常用方式，它是在基本分頁儲存管理的基礎(chǔ)上實(shí)現(xiàn)的。其基本思想是：在進(jìn)程開始運(yùn)行之前，僅裝入當(dāng)前要執(zhí)行的部分頁面即可運(yùn)行；在執(zhí)行過程中，可使用請求調(diào)入中斷動(dòng)態(tài)裝入要訪問但又不在內(nèi)存的頁面；當(dāng)內(nèi)存空間已滿，而又需要裝入新的頁面時(shí)，者根據(jù)置換功能適當(dāng)調(diào)出某個(gè)頁面，以便騰出空間而裝入新的頁面。為實(shí)現(xiàn)請求分頁，需要一定的硬件支持，包括：頁表機(jī)制、缺頁中斷機(jī)構(gòu)、地址變換機(jī)構(gòu)。

　　15.基本分段、請求分段儲存管理方式。(略)

　　16.分段分頁方式的比較各自優(yōu)缺點(diǎn)。

　　分段和分頁其實(shí)都是一種對地址的劃分或者映射的方式。兩者的區(qū)別主要有以下幾點(diǎn)：

　　1)頁是信息的物理單位，分頁是為實(shí)現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存的利用率；或者說，分頁僅僅是由于系統(tǒng)管理的需要，而不是用戶的需要（也是對用戶透明的）。段是信息的邏輯單位，它含有一組其意義相對完整的信息（比如數(shù)據(jù)段、代碼段和堆棧段等）。分段的目的是為了能更好的滿足用戶的需要（用戶也是可以使用的）。

　　2)頁的大小固定且由系統(tǒng)確定，把邏輯地址劃分為頁號和頁內(nèi)地址兩部分，是由機(jī)器硬件實(shí)現(xiàn)的，因而一個(gè)系統(tǒng)只能有一種大小的頁面。段的長度卻不固定，決定于用戶所編寫的程序，通常由編輯程序在對源程序進(jìn)行編輯時(shí)，根據(jù)信息的性質(zhì)來劃分。

　　3)分頁的作業(yè)地址空間是維一的，即單一的線性空間，程序員只須利用一個(gè)記憶符（線性地址的16進(jìn)制表示），即可表示一地址。分段的作業(yè)地址空間是二維的，程序員在標(biāo)識一個(gè)地址時(shí)，既需給出段名（比如數(shù)據(jù)段、代碼段和堆棧段等），又需給出段內(nèi)地址。

　　4)頁和段都有存儲保護(hù)機(jī)制。但存取權(quán)限不同：段有讀、寫和執(zhí)行三種權(quán)限；而頁只有讀和寫兩種權(quán)限。

　　17.幾種頁面置換算法。

　　1）最佳置換算法（OPT）（理想置換算法）

　　這是一種理想情況下的頁面置換算法，但實(shí)際上是不可能實(shí)現(xiàn)的。該算法的基本思想是：發(fā)生缺頁時(shí)，有些頁面在內(nèi)存中，其中有一頁將很快被訪問（也包含緊接著的下一條指令的那頁），而其他頁面則可能要到10、100或者1000條指令后才會被訪問，每個(gè)頁面都可以用在該頁面首次被訪問前所要執(zhí)行的指令數(shù)進(jìn)行標(biāo)記。最佳頁面置換算法只是簡單地規(guī)定：標(biāo)記最大的頁應(yīng)該被置換。這個(gè)算法唯一的一個(gè)問題就是它無法實(shí)現(xiàn)。當(dāng)缺頁發(fā)生時(shí)，操作系統(tǒng)無法知道各個(gè)頁面下一次是在什么時(shí)候被訪問。雖然這個(gè)算法不可能實(shí)現(xiàn)，但是最佳頁面置換算法可以用于對可實(shí)現(xiàn)算法的性能進(jìn)行衡量比較。

　　2）先進(jìn)先出置換算法（FIFO）

　　最簡單的頁面置換算法是先入先出（FIFO）法。這種算法的實(shí)質(zhì)是，總是選擇在主存中停留時(shí)間最長（即最老）的一頁置換，即先進(jìn)入內(nèi)存的頁，先退出內(nèi)存。理由是：最早調(diào)入內(nèi)存的頁，其不再被使用的可能性比剛調(diào)入內(nèi)存的可能性大。建立一個(gè)FIFO隊(duì)列，收容所有在內(nèi)存中的頁。被置換頁面總是在隊(duì)列頭上進(jìn)行。當(dāng)一個(gè)頁面被放入內(nèi)存時(shí)，就把它插在隊(duì)尾上。

　　這種算法只是在按線性順序訪問地址空間時(shí)才是理想的，否則效率不高。因?yàn)槟切┏１辉L問的頁，往往在主存中也停留得最久，結(jié)果它們因變“老”而不得不被置換出去。

　　FIFO的另一個(gè)缺點(diǎn)是，它有一種異常現(xiàn)象，即在增加存儲塊的情況下，反而使缺頁中斷率增加了。當(dāng)然，導(dǎo)致這種異常現(xiàn)象的頁面走向?qū)嶋H上是很少見的。

　　3）最近最久未使用（LRU）算法

　　FIFO算法和OPT算法之間的主要差別是，F(xiàn)IFO算法利用頁面進(jìn)入內(nèi)存后的時(shí)間長短作為置換依據(jù)，而OPT算法的依據(jù)是將來使用頁面的時(shí)間。如果以最近的過去作為不久將來的近似，那么就可以把過去最長一段時(shí)間里不曾被使用的頁面置換掉。它的實(shí)質(zhì)是，當(dāng)需要置換一頁時(shí)，選擇在最近一段時(shí)間里最久沒有使用過的頁面予以置換。這種算法就稱為最久未使用算法（LeastRecentlyUsed，LRU）。LRU算法是與每個(gè)頁面最后使用的時(shí)間有關(guān)的。當(dāng)必須置換一個(gè)頁面時(shí)，LRU算法選擇過去一段時(shí)間里最久未被使用的頁面。

　　18.虛擬內(nèi)存的定義及實(shí)現(xiàn)方式。

　　虛擬內(nèi)存是計(jì)算機(jī)系統(tǒng)內(nèi)存管理的一種技術(shù)。它使得應(yīng)用程序認(rèn)為它擁有連續(xù)的可用的內(nèi)存（一個(gè)連續(xù)完整的地址空間），而實(shí)際上，它通常是被分隔成多個(gè)物理內(nèi)存碎片，還有部分暫時(shí)存儲在外部磁盤存儲器上，在需要時(shí)進(jìn)行數(shù)據(jù)交換。與沒有使用虛擬內(nèi)存技術(shù)的系統(tǒng)相比，使用這種技術(shù)的系統(tǒng)使得大型程序的編寫變得更容易，對真正的物理內(nèi)存（例如RAM）的使用也更有效率。

　　19.操作系統(tǒng)的四個(gè)特性。

　　1）并發(fā)（concurrence）

　　并行性與并發(fā)性這兩個(gè)概念是既相似又區(qū)別的兩個(gè)概念。并行性是指兩個(gè)或者多個(gè)事件在同一時(shí)刻發(fā)生，這是一個(gè)具有微觀意義的概念，即在物理上這些事件是同時(shí)發(fā)生的；而并發(fā)性是指兩個(gè)或者多個(gè)事件在同一時(shí)間的間隔內(nèi)發(fā)生，它是一個(gè)較為宏觀的概念。在多道程序環(huán)境下，并發(fā)性是指在一段時(shí)間內(nèi)有多道程序在同時(shí)運(yùn)行，但在單處理機(jī)的系統(tǒng)中，每一時(shí)刻僅能執(zhí)行一道程序，故微觀上這些程序是在交替執(zhí)行的。應(yīng)當(dāng)指出，通常的程序是靜態(tài)實(shí)體，它們是不能并發(fā)執(zhí)行的。為了使程序能并發(fā)執(zhí)行，系統(tǒng)必須分別為每個(gè)程序建立進(jìn)程。進(jìn)程，又稱任務(wù)，簡單來說，是指在系統(tǒng)中能獨(dú)立運(yùn)行并作為資源分配的基本單位，它是一個(gè)活動(dòng)的實(shí)體。多個(gè)進(jìn)程之間可以并發(fā)執(zhí)行和交換信息。一個(gè)進(jìn)程在運(yùn)行時(shí)需要運(yùn)行時(shí)需要一定的資源，如cpu,存儲空間，及i/o設(shè)備等。在操作系統(tǒng)中引入進(jìn)程的目的是使程序能并發(fā)執(zhí)行。

　　2）共享(sharing)

　　所謂共享是指，系統(tǒng)中的資源可供內(nèi)存中多個(gè)并發(fā)執(zhí)行的進(jìn)程共同使用。由于資源的屬性不同，故多個(gè)進(jìn)程對資源的共享方式也不同，可以分為：互斥共享方式和同時(shí)訪問方式。

　　3）虛擬(virtual)

　　是指通過技術(shù)吧一個(gè)物理實(shí)體變成若干個(gè)邏輯上的對應(yīng)物。在操作系統(tǒng)中虛擬的實(shí)現(xiàn)主要是通過分時(shí)的使用方法。顯然，如果n是某一個(gè)物理設(shè)備所對應(yīng)的虛擬邏輯設(shè)備數(shù)，則虛擬設(shè)備的速度必然是物理設(shè)備速度的1/n。

　　4）異步(asynchronism)

　　在多道程序設(shè)計(jì)環(huán)境下，允許多個(gè)進(jìn)程并發(fā)執(zhí)行，由于資源等因素的限制，通常，進(jìn)程的執(zhí)行并非“一氣呵成”，而是以“走走停停”的方式運(yùn)行。內(nèi)存中每個(gè)進(jìn)程在何時(shí)執(zhí)行，何時(shí)暫停，以怎樣的方式向前推進(jìn)，每道程序總共需要多少時(shí)間才能完成，都是不可預(yù)知的。或者說，進(jìn)程是以一步的方式運(yùn)行的。盡管如此，但只要運(yùn)行環(huán)境相同，作業(yè)經(jīng)過多次運(yùn)行，都會獲得完全相同的結(jié)果。

　　20.DMA

　　直接存儲器訪問（DirectMemoryAccess，DMA）是計(jì)算機(jī)科學(xué)中的一種內(nèi)存訪問技術(shù)。它允許某些計(jì)算機(jī)內(nèi)部的硬件子系統(tǒng)（電腦外設(shè)），可以獨(dú)立地直接讀寫系統(tǒng)存儲器，而不需繞道中央處理器（CPU）。在同等程度的處理器負(fù)擔(dān)下，DMA是一種快速的數(shù)據(jù)傳送方式。很多硬件的系統(tǒng)會使用DMA，包含硬盤控制器、繪圖顯卡、網(wǎng)卡和聲卡。

　　21.Spooling

　　SPOOLing(即外部設(shè)備聯(lián)機(jī)并行操作)，即SimultaneousPeripheralOperationOn-Line的縮寫，它是關(guān)于慢速字符設(shè)備如何與計(jì)算機(jī)主機(jī)交換信息的一種技術(shù)，通常稱為“假脫機(jī)技術(shù)”。

　　22.外存分配的幾種方式，及其優(yōu)劣。

　　1）連續(xù)分配

　　連續(xù)分配：創(chuàng)建文件時(shí)，分配一組連續(xù)的塊；FAT中每個(gè)文件只要一項(xiàng)，說明起始塊和文件的長度。對順序文件有利。

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

　　簡單。適用于一次性寫入的操作

　　支持順序存取和隨機(jī)存取，順序存取速度快

　　所需的磁盤尋道次數(shù)和尋道時(shí)間最少（因?yàn)橛捎诳臻g的連續(xù)性，當(dāng)訪問下一個(gè)磁盤塊時(shí)，一般無需移動(dòng)磁頭，當(dāng)需要磁頭移動(dòng)，只需要移動(dòng)一個(gè)磁道。

　　缺點(diǎn):

　　文件不能動(dòng)態(tài)增長（可能文件末尾處的空塊已經(jīng)分配給別的文件）

　　不利于文件插入和刪除

　　外部碎片問題（反復(fù)增刪文件后），使得很難找到空間大小足夠的連續(xù)塊。進(jìn)行緊縮

　　在創(chuàng)建文件時(shí)聲明文件的大小。

　　2）鏈?zhǔn)椒峙?/p>

　　鏈?zhǔn)椒峙洌阂粋€(gè)文件的信息存放在若干不連續(xù)的物理塊中，各塊之間通過指針連接，前一個(gè)物理塊指向下一個(gè)物理塊。FAT中每個(gè)文件同樣只需要一項(xiàng)，包括文件名、起始塊號和最后塊號。任何一個(gè)自由塊都可以加入到鏈中。

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

　　提高了磁盤空間利用率,不存在外部碎片問題

　　有利于文件插入和刪除

　　有利于文件動(dòng)態(tài)擴(kuò)充

　　缺點(diǎn)：

　　存取速度慢，一般僅適于對信息的順序存取，不適于隨機(jī)存取:查找某一個(gè)塊必須從頭開始沿指針進(jìn)行。

　　可靠性問題，如指針出錯(cuò)；更多的尋道次數(shù)和尋道時(shí)間

　　鏈接指針占用一定的空間，將多個(gè)塊組成簇（cluster），按簇進(jìn)行分配而不是按塊進(jìn)行分配（增加了磁盤碎片）。

　　3）索引分配

　　索引分配：每個(gè)文件在FAT中有一個(gè)一級索引，索引包含分配給文件的每個(gè)分區(qū)的入口。文件的索引保存在一個(gè)單獨(dú)的塊中。FAT中該文件的入口指向這一塊。

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

　　保持了鏈接結(jié)構(gòu)的優(yōu)點(diǎn),又解決了其缺點(diǎn)：按塊分配可以消除外部碎片，按大小可變的分區(qū)分配可以提高局部性。索引分配支持順序訪問文件和直接訪問文件，是普遍采用的一種方式。

　　滿足了文件動(dòng)態(tài)增長、插入刪除的要求（只要有空閑塊）

　　也能充分利用外存空間

　　缺點(diǎn)：

　　較多的尋道次數(shù)和尋道時(shí)間.

　　索引表本身帶來了系統(tǒng)開銷，如：內(nèi)外存空間，存取時(shí)間

　　如果覺得本文有用，請頂我們一下！謝謝！

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈