操作系統(tǒng)面試題大全總結(jié)

　　我們想要學(xué)習(xí)或者在操作系統(tǒng)領(lǐng)域工作的朋友們，有沒有在面試時候遇到阻礙呀，面試題目有沒有準(zhǔn)備好呢，下面和小編一起看看!

　　操作系統(tǒng)面試總結(jié)

　　1. 處理死鎖的四個方式。

　　1)忽略該問題。例如鴕鳥算法，該算法可以應(yīng)用在極少發(fā)生死鎖的的情況下。為什么叫鴕鳥算法呢，(鴕鳥策略)

　　2)檢測死鎖并且恢復(fù)。(檢測與解除策略)

　　3)仔細(xì)地對資源進(jìn)行動態(tài)分配，以避免死鎖。(避免策略)

　　4)通過破除死鎖四個必要條件之一，來防止死鎖產(chǎn)生。(預(yù)防策略)

　　2. 預(yù)防死鎖的方法、避免死鎖的方法。

　　通過破除死鎖四個必要條件之一，來預(yù)防死鎖產(chǎn)生，有兩種方法，一種是當(dāng)其申請的資源得不到滿足時，也必須放棄其原先占有的資源;另一種方法是只適用于申請資源的進(jìn)程優(yōu)先級比占有該資源的進(jìn)程優(yōu)先級高時，如果一個進(jìn)程申請的資源被其它進(jìn)程占用，而申請進(jìn)程的優(yōu)先級較高，那么它可以強(qiáng)迫占有資源的進(jìn)程放棄。

　　仔細(xì)地對資源進(jìn)行動態(tài)分配，以避免死鎖。

　　3. 進(jìn)程調(diào)度算法。(周轉(zhuǎn)時間 = 程序結(jié)束時間 -- 開始服務(wù)時間、帶權(quán)周轉(zhuǎn)時間= 周轉(zhuǎn)時間 / 要求服務(wù)時間)

　　先來先服務(wù)(First Come First Service，F(xiàn)CFS)調(diào)度算法按照進(jìn)程進(jìn)入就緒隊列的先后順序選擇可以占用處理器的進(jìn)程。這是一種不可搶占方式的調(diào)度算法，優(yōu)點(diǎn)是實現(xiàn)簡單，缺點(diǎn)是后來的進(jìn)程等待CPU的時間較長。它現(xiàn)今主要用作輔助調(diào)度法;例如結(jié)合在優(yōu)先級調(diào)度算法中使用，當(dāng)有兩個最高優(yōu)先級的進(jìn)程時，則誰先來，誰就先被調(diào)度。

　　短執(zhí)行進(jìn)程優(yōu)先算法(Shortest Process First，SPF)就是從就緒隊列中選擇一個CPU執(zhí)行時間預(yù)期最短的進(jìn)程，將處理器分配給它。雖然較公平，但實現(xiàn)難度較大，因為要準(zhǔn)確預(yù)定下一個進(jìn)程的CPU執(zhí)行周期是很困難的。

　　•最高優(yōu)先級優(yōu)先(Highest Priority First，HPF)調(diào)度算法的核心是確定進(jìn)程的優(yōu)先級。首先，系統(tǒng)或用戶按某種原則為進(jìn)程指定一個優(yōu)先級來表示該進(jìn)程所享有的調(diào)度優(yōu)先權(quán)。確定優(yōu)先級的方法較多，一般可分為兩類，即靜態(tài)法和動態(tài)法。靜態(tài)法根據(jù)進(jìn)程的靜態(tài)特性，在進(jìn)程開始執(zhí)行之前就確定它們的優(yōu)先級，一旦開始執(zhí)行之后就不能改變。動態(tài)法則不然，它把進(jìn)程的靜態(tài)特性和動態(tài)特性結(jié)合起來確定進(jìn)程的優(yōu)先級，隨著進(jìn)程的執(zhí)行過程，其優(yōu)先級不斷變化。

　　•進(jìn)程的靜態(tài)優(yōu)先級確定最基本的方法是按照進(jìn)程的類型給予不同的優(yōu)先級。例如，在有些系統(tǒng)中，進(jìn)程被劃分為系統(tǒng)進(jìn)程和用戶進(jìn)程。系統(tǒng)進(jìn)程享有比用戶進(jìn)程高的優(yōu)先級;對于用戶進(jìn)程來說，則可以分為：I/O繁忙的進(jìn)程、CPU繁忙的進(jìn)程、I/O與CPU均衡的進(jìn)程和其他進(jìn)程等。

　　•對系統(tǒng)進(jìn)程，也可以根據(jù)其所要完成的功能劃分為不同的類型。例如，調(diào)度進(jìn)程、I/O進(jìn)程、中斷處理進(jìn)程、存儲管理進(jìn)程等。這些進(jìn)程還可進(jìn)一步劃分為不同類型并賦予不同的優(yōu)先級。例如，在操作系統(tǒng)中，對于鍵盤中斷的處理優(yōu)先級和對于電源掉電中斷的處理優(yōu)先級是不相同的。

　　•基于靜態(tài)優(yōu)先級的調(diào)度算法實現(xiàn)簡單，系統(tǒng)開銷小，但由于靜態(tài)優(yōu)先級一旦確定之后，直到執(zhí)行結(jié)束為止始終保持不變，從而系統(tǒng)效率較低，調(diào)度性能不高。現(xiàn)在的操作系統(tǒng)中，如果使用優(yōu)先級調(diào)度的話，則大多采用動態(tài)優(yōu)先級的調(diào)度策略。

　　•進(jìn)程的動態(tài)優(yōu)先級一般可以根據(jù)以下兩個方面來確定：

　　• (1)根據(jù)進(jìn)程占有CPU時間的長短來決定。一個進(jìn)程占有處理機(jī)的時間愈長，則在被阻塞之后再次獲得調(diào)度的優(yōu)先級就越低。反之，其獲得調(diào)度的可能性就會越大。

　　• (2)根據(jù)就緒進(jìn)程等待CPU的時間長短來決定。一個就緒進(jìn)程在就緒隊列中等待的時間越長，則它獲得調(diào)度選中的優(yōu)先級就越高。

　　•由于動態(tài)優(yōu)先級隨時間的推移而變化，系統(tǒng)要經(jīng)常計算各個進(jìn)程的優(yōu)先級，因此，系統(tǒng)要為此付出一定的開銷。

　　•最高優(yōu)先級優(yōu)先調(diào)度算法用于多道批處理系統(tǒng)中較好，但它使得優(yōu)先級較低的進(jìn)程等待時間較長，這對于分時系統(tǒng)中要想獲得較好的響應(yīng)時間是不允許的，所以在分時系統(tǒng)中多采用時間片輪轉(zhuǎn)法來進(jìn)行進(jìn)程調(diào)度。

　　時間片輪轉(zhuǎn)(Round Robin，RR)法的基本思路是讓每個進(jìn)程在就緒隊列中的等待時間與享受服務(wù)的時間成比例。在時間片輪轉(zhuǎn)法中，需要將CPU的處理時間分成固定大小的時間片，例如，幾十毫秒至幾百毫秒。如果一個進(jìn)程在被調(diào)度選中之后用完了系統(tǒng)規(guī)定的時間片，但又未完成要求的任務(wù)，則它自行釋放自己所占有的CPU而排到就緒隊列的末尾，等待下一次調(diào)度。同時，進(jìn)程調(diào)度程序又去調(diào)度當(dāng)前就緒隊列中的第一個進(jìn)程。

　　•顯然，輪轉(zhuǎn)法只能用來調(diào)度分配一些可以搶占的資源。這些可以搶占的資源可以隨時被剝奪，而且可以將它們再分配給別的進(jìn)程。CPU是可搶占資源的一種。但打印機(jī)等資源是不可搶占的。由于作業(yè)調(diào)度是對除了CPU之外的所有系統(tǒng)硬件資源的分配，其中包含有不可搶占資源，所以作業(yè)調(diào)度不使用輪轉(zhuǎn)法。在輪轉(zhuǎn)法中，時間片長度的選取非常重要。首先，時間片長度的選擇會直接影響到系統(tǒng)的開銷和響應(yīng)時間。如果時間片長度過短，則調(diào)度程序搶占處理機(jī)的次數(shù)增多。這將使進(jìn)程上下文切換次數(shù)也大大增加，從而加重系統(tǒng)開銷。反過來，如果時間片長度選擇過長，例如，一個時間片能保證就緒隊列中所需執(zhí)行時間最長的進(jìn)程能執(zhí)行完畢，則輪轉(zhuǎn)法變成了先來先服務(wù)法。時間片長度的選擇是根據(jù)系統(tǒng)對響應(yīng)時間的要求和就緒隊列中所允許最大的進(jìn)程數(shù)來確定的。

　　• 在輪轉(zhuǎn)法中，加入到就緒隊列的進(jìn)程有3種情況，一種是分給它的時間片用完，但進(jìn)程還未完成，回到就緒隊列的末尾等待下次調(diào)度去繼續(xù)執(zhí)行。另一種情況是分給該進(jìn)程的時間片并未用完，只是因為請求I/O或由于進(jìn)程的互斥與同步關(guān)系而被阻塞。當(dāng)阻塞解除之后再回到就緒隊列。第三種情況就是新創(chuàng)建進(jìn)程進(jìn)入就緒隊列。如果對這些進(jìn)程區(qū)別對待，給予不同的優(yōu)先級和時間片，從直觀上看，可以進(jìn)一步改善系統(tǒng)服務(wù)質(zhì)量和效率。例如，我們可把就緒隊列按照進(jìn)程到達(dá)就緒隊列的類型和進(jìn)程被阻塞時的阻塞原因分成不同的就緒隊列，每個隊列按FCFS原則排列，各隊列之間的進(jìn)程享有不同的優(yōu)先級，但同一隊列內(nèi)優(yōu)先級相同。這樣，當(dāng)一個進(jìn)程在執(zhí)行完它的時間片之后，或從睡眠中被喚醒以及被創(chuàng)建之后，將進(jìn)入不同的就緒隊列。

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

　　內(nèi)存管理是操作系統(tǒng)中的重要部分，兩三句話恐怕誰也說不清楚吧～～我先說個大概，希望能夠拋磚引玉吧 當(dāng)程序運(yùn)行時需要從內(nèi)存中讀出這段程序的代碼。代碼的位置必須在物理內(nèi)存中才能被運(yùn)行，由于現(xiàn)在的操作系統(tǒng)中有非常多的程序運(yùn)行著，內(nèi)存中不能夠完全放下，所以引出了虛擬內(nèi)存的概念。把哪些不常用的程序片斷就放入虛擬內(nèi)存，當(dāng)需要用到它的時候在load入主存(物理內(nèi)存)中。這個就是內(nèi)存管理所要做的事。內(nèi)存管理還有另外一件事需要做：計算程序片段在主存中的物理位置，以便CPU調(diào)度。 內(nèi)存管理有塊式管理，頁式管理，段式和段頁式管理。現(xiàn)在常用段頁式管理。

　　塊式管理：把主存分為一大塊、一大塊的，當(dāng)所需的程序片斷不在主存時就分配一塊主存空間，把程序片斷l(xiāng)oad入主存，就算所需的程序片度只有幾個字節(jié)也只能把這一塊分配給它。這樣會造成很大的浪費(fèi)，平均浪費(fèi)了50%的內(nèi)存空間，但是易于管理。

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

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

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

　　二維邏輯地址：段號+段內(nèi)地址

　　分頁與分段的主要區(qū)別：

　　1)、段是信息的邏輯單位，它是根據(jù)用戶的需要劃分的，因此段對用戶是可見的;頁是信息的物理單位，是為了管理主存的方便而劃分的，對用戶是透明的。

　　2)、頁的大小固定不變，由系統(tǒng)決定。段的大小是不固定的，它由其完成的功能決定。

　　3)、段式向用戶提供的是二維地址空間，頁式向用戶提供的是一維地址空間，其頁號和頁內(nèi)偏移是機(jī)器硬件的功能。

　　4)、由于段是信息的邏輯單位，因此便于存貯保護(hù)和信息的共享，頁的保護(hù)和共享受到限制。

　　分頁與分段存儲管理系統(tǒng)雖然在很多地方相似，但從概念上講，兩者是完全不同的，它們之間的區(qū)別如下：

　?、夙撌切畔⒌奈锢韱挝?。分頁的目的是實現(xiàn)離散分配，減少外部碎片，提高內(nèi)存利用率。段是信息的邏輯單位。每一段在邏輯上是一組相對完整的信息集合。

　?、诜猪撌酱鎯芾淼淖鳂I(yè)地址空間是一維的，而分段式存儲管理的作業(yè)地址空間是二維的。

　?、垌摰拇笮」潭ㄇ矣上到y(tǒng)確定，是等長的。而段的長度不定。

　　④分頁的優(yōu)點(diǎn)體現(xiàn)在內(nèi)存空間的管理上，而分段的優(yōu)點(diǎn)體現(xiàn)在地址空間的管理上。

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

　　1) 單一連續(xù)分配 是一種最簡單的存儲管理方式，其優(yōu)點(diǎn)是軟件處理簡單，最大缺點(diǎn)是存儲器不能充分利用。多用于單用戶微機(jī)操作系統(tǒng)中。

　　2) 動態(tài)分區(qū)分配 是多道程序環(huán)境下各種存儲管理方式中最簡單的一種。它將內(nèi)存劃分成若干個分區(qū)，在每個分區(qū)中按照連續(xù)分配方式分配給一個作業(yè)。分區(qū)形式: a) 固定分區(qū)分配：指內(nèi)存在處理作業(yè)前已被劃分成若干個大小不等的分區(qū)，存儲管理程序根據(jù)每個作業(yè)步的最大存儲量分配一個足夠大的分區(qū)給它。當(dāng)找不到一個足夠大的分區(qū)時，則通知作業(yè)調(diào)度挑選另一作業(yè)，這種方式分配和回收內(nèi)存簡單，但內(nèi)存利用不充分，會產(chǎn)生“碎片”空間。b) 可變分區(qū)分配：指內(nèi)存事先并未被分區(qū)，只有當(dāng)作業(yè)進(jìn)入內(nèi)存時，才根據(jù)作業(yè)的大小建立分區(qū)。其特點(diǎn)是分區(qū)的個數(shù)和大小都是可變的，但需要建立分配區(qū)表和空白區(qū)表，且表的長度是不固定的。

　　3) 可重定位分區(qū)分配 為使各分區(qū)中的用戶程序能移到內(nèi)存的一端，使碎片集中于另一端成為一個大分區(qū)，在程序執(zhí)行過程中，需對作業(yè)移動過程中的與地址有關(guān)項進(jìn)行調(diào)整。這種分配方法的優(yōu)點(diǎn)是清除碎片，更大程度地利用內(nèi)存空間，但必須硬件的支持，且要花費(fèi)時間。

　　16. 動態(tài)鏈接及靜態(tài)鏈接.

　　靜態(tài)鏈接庫與動態(tài)鏈接庫都是共享代碼的方式，如果采用靜態(tài)鏈接庫，則無論你愿不愿意，lib 中的指令都全部被直接包含在最終生成的 EXE 文件中了。但是若使用 DLL，該 DLL 不必被包含在最終 EXE 文件中，EXE 文件執(zhí)行時可以“動態(tài)”地引用和卸載這個與 EXE 獨(dú)立的 DLL 文件。靜態(tài)鏈接庫和動態(tài)鏈接庫的另外一個區(qū)別在于靜態(tài)鏈接庫中不能再包含其他的動態(tài)鏈接庫或者靜態(tài)庫，而在動態(tài)鏈接庫中還可以再包含其他的動態(tài)或靜態(tài)鏈接 庫

　　動態(tài)鏈接是指在生成可執(zhí)行文件時不將所有程序用到的函數(shù)鏈接到一個文件，因為有許多函數(shù)在操作系統(tǒng)帶的dll文件中，當(dāng)程序運(yùn)行時直接從操作系統(tǒng)中找。

　　而靜態(tài)鏈接就是把所有用到的函數(shù)全部鏈接到exe文件中。

　　動態(tài)鏈接是只建立一個引用的接口，而真正的代碼和數(shù)據(jù)存放在另外的可執(zhí)行模塊中，在運(yùn)行時再裝入;

　　而靜態(tài)鏈接是把所有的代碼和數(shù)據(jù)都復(fù)制到本模塊中，運(yùn)行時就不再需要庫了。

　　17. 基本分頁、請求分頁儲存管理方式。18. 基本分段、請求分段儲存管理方式。

　　分頁式存儲管理的基本原理：采用分頁存儲器允許把一個作業(yè)存放到若干不相鄰的分區(qū)中，既可免去移動信息的工作，又可盡量減少主存的碎片。分頁式存儲管理的基本原理如下：

　　1、 頁框：物理地址分成大小相等的許多區(qū)，每個區(qū)稱為一塊;

　　2、址分成大小相等的區(qū)，區(qū)的大小與塊的大小相等，每個稱一個頁面。

　　3、 邏輯地址形式：與此對應(yīng)，分頁存儲器的邏輯地址由兩部分組成，頁號和單元號。邏輯地址格式為

　　頁號 單元號(頁內(nèi)地址)

　　采用分頁式存儲管理時，邏輯地址是連續(xù)的。所以，用戶在編制程序時仍只須使用順序的地址，而不必考慮如何去分頁。

　　4、頁表和地址轉(zhuǎn)換：如何保證程序正確執(zhí)行呢?采用的辦法是動態(tài)重定位技術(shù)，讓程序的指令執(zhí)行時作地址變換，由于程序段以頁為單位，所以，我們給每個頁設(shè)立一個重定位寄存器，這些重定位寄存器的集合便稱頁表。頁表是操作系統(tǒng)為每個用戶作業(yè)建立的，用來記錄程序頁面和主存對應(yīng)頁框的對照表，頁表中的每一欄指明了程序中的一個頁面和分得的頁框的對應(yīng)關(guān)系。絕對地址=塊號*塊長+單元號

　　以上從拓?fù)浣Y(jié)構(gòu)角度分析了對稱式與非對稱式虛擬存儲方案的異同,實際從虛擬化存儲的實現(xiàn)原理來講也有兩種方式;即數(shù)據(jù)塊虛擬與虛擬文件系統(tǒng).

　　數(shù)據(jù)塊虛擬存儲方案著重解決數(shù)據(jù)傳輸過程中的沖突和延時問題.在多交換機(jī)組成的大型Fabric結(jié)構(gòu)的SAN中,由于多臺主機(jī)通過多個交換機(jī)端口訪問存儲設(shè)備,延時和數(shù)據(jù)塊沖突問題非常嚴(yán)重.數(shù)據(jù)塊虛擬存儲方案利用虛擬的多端口并行技術(shù),為多臺客戶機(jī)提供了極高的帶寬,最大限度上減少了延時與沖突的發(fā)生,在實際應(yīng)用中,數(shù)據(jù)塊虛擬存儲方案以對稱式拓?fù)浣Y(jié)構(gòu)為表現(xiàn)形式.

　　虛擬文件系統(tǒng)存儲方案著重解決大規(guī)模網(wǎng)絡(luò)中文件共享的安全機(jī)制問題.通過對不同的站點(diǎn)指定不同的訪問權(quán)限,保證網(wǎng)絡(luò)文件的安全.在實際應(yīng)用中,虛擬文件系統(tǒng)存儲方案以非對稱式拓?fù)浣Y(jié)構(gòu)為表現(xiàn)形式.

　　虛擬存儲技術(shù),實際上是虛擬存儲技術(shù)的一個方面,特指以CPU時間和外存空間換取昂貴內(nèi)存空間的操作系統(tǒng)中的資源轉(zhuǎn)換技術(shù)

　　基本思想:程序,數(shù)據(jù),堆棧的大小可以超過內(nèi)存的大小,操作系統(tǒng)把程序當(dāng)前使用的部分保留在內(nèi)存,而把其他部分保存在磁盤上,并在需要時在內(nèi)存和磁盤之間動態(tài)交換,虛擬存儲器支持多道程序設(shè)計技術(shù)

　　目的:提高內(nèi)存利用率

　　管理方式

　　A 請求式分頁存儲管理

　　在進(jìn)程開始運(yùn)行之前,不是裝入全部頁面,而是裝入一個或零個頁面,之后根據(jù)進(jìn)程運(yùn)行的需要,動態(tài)裝入其他頁面;當(dāng)內(nèi)存空間已滿,而又需要裝入新的頁面時,則根據(jù)某種算法淘汰某個頁面,以便裝入新的頁面

　　B 請求式分段存儲管理

　　為了能實現(xiàn)虛擬存儲,段式邏輯地址空間中的程序段在運(yùn)行時并不全部裝入內(nèi)存,而是如同請求式分頁存儲管理,首先調(diào)入一個或若干個程序段運(yùn)行,在運(yùn)行過程中調(diào)用到哪段時,就根據(jù)該段長度在內(nèi)存分配一個連續(xù)的分區(qū)給它使用.若內(nèi)存中沒有足夠大的空閑分區(qū),則考慮進(jìn)行段的緊湊或?qū)⒛扯位蚰承┒翁蕴鋈?這種存儲管理技術(shù)稱為請求式分段存儲管理

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

　　頁和分段系統(tǒng)有許多相似之處，但在概念上兩者完全不同，主要表現(xiàn)在：

　　1、頁是信息的物理單位，分頁是為實現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存的利用率;或者說，分頁僅僅是由于系統(tǒng)管理的需要，而不是用戶的需要。

　　段是信息的邏輯單位，它含有一組其意義相對完整的信息。分段的目的是為了能更好的滿足用戶的需要。

　　2、頁的大小固定且由系統(tǒng)確定，把邏輯地址劃分為頁號和頁內(nèi)地址兩部分，是由機(jī)器硬件實現(xiàn)的，因而一個系統(tǒng)只能有一種大小的頁面。

　　段的長度卻不固定，決定于用戶所編寫的程序，通常由編輯程序在對源程序進(jìn)行編輯時，根據(jù)信息的性質(zhì)來劃分。

　　3、分頁的作業(yè)地址空間是維一的，即單一的線性空間，程序員只須利用一個記憶符，即可表示一地址。

　　分段的作業(yè)地址空間是二維的，程序員在標(biāo)識一個地址時，既需給出段名，又需給出段內(nèi)地址。

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

　　地址映射過程中，若在頁面中發(fā)現(xiàn)所要訪問的頁面不再內(nèi)存中，則產(chǎn)生缺頁中斷。當(dāng)發(fā)生缺頁中斷時操作系統(tǒng)必須在內(nèi)存選擇一個頁面將其移出內(nèi)存，以便為即將調(diào)入的頁面讓出空間。而用來選擇淘汰哪一頁的規(guī)則叫做頁面置換算法。常見的置換算法有：

　　1)最佳置換算法(OPT)(理想置換算法)

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

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

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

　　這種算法只是在按線性順序訪問地址空間時才是理想的，否則效率不高。因為那些常被訪問的頁，往往在主存中也停留得最久，結(jié)果它們因變“老”而不得不被置換出去。

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

　　3)最近最久未使用(LRU)算法

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

　　LRU算法是與每個頁面最后使用的時間有關(guān)的。當(dāng)必須置換一個頁面時，LRU算法選擇過去一段時間里最久未被使用的頁面。

　　LRU算法是經(jīng)常采用的頁面置換算法，并被認(rèn)為是相當(dāng)好的，但是存在如何實現(xiàn)它的問題。LRU算法需要實際硬件的支持。其問題是怎么確定最后使用時間的順序，對此有兩種可行的辦法：

　　1.計數(shù)器。最簡單的情況是使每個頁表項對應(yīng)一個使用時間字段，并給CPU增加一個邏輯時鐘或計數(shù)器。每次存儲訪問，該時鐘都加1。每當(dāng)訪問一個頁面時，時鐘寄存器的內(nèi)容就被復(fù)制到相應(yīng)頁表項的使用時間字段中。這樣我們就可以始終保留著每個頁面最后訪問的“時間”。在置換頁面時，選擇該時間值最小的頁面。這樣做，不僅要查頁表，而且當(dāng)頁表改變時(因CPU調(diào)度)要維護(hù)這個頁表中的時間，還要考慮到時鐘值溢出的問題。

　　2.棧。用一個棧保留頁號。每當(dāng)訪問一個頁面時，就把它從棧中取出放在棧頂上。這樣一來，棧頂總是放有目前使用最多的頁，而棧底放著目前最少使用的頁。由于要從棧的中間移走一項，所以要用具有頭尾指針的雙向鏈連起來。在最壞的情況下，移走一頁并把它放在棧頂上需要改動6個指針。每次修改都要有開銷，但需要置換哪個頁面卻可直接得到，用不著查找，因為尾指針指向棧底，其中有被置換頁。

　　因?qū)崿F(xiàn)LRU算法必須有大量硬件支持，還需要一定的軟件開銷。所以實際實現(xiàn)的都是一種簡單有效的LRU近似算法。

　　一種LRU近似算法是最近未使用算法(Not Recently Used，NUR)。它在存儲分塊表的每一表項中增加一個引用位，操作系統(tǒng)定期地將它們置為0。當(dāng)某一頁被訪問時，由硬件將該位置1。過一段時間后，通過檢查這些位可以確定哪些頁使用過，哪些頁自上次置0后還未使用過。就可把該位是0的頁淘汰出去，因為在最近一段時間里它未被訪問過。

　　4)Clock置換算法(LRU算法的近似實現(xiàn))

　　5)最少使用(LFU)置換算法

　　在采用最少使用置換算法時，應(yīng)為在內(nèi)存中的每個頁面設(shè)置一個移位寄存器，用來記錄該頁面被訪問的頻率。該置換算法選擇在最近時期使用最少的頁面作為淘汰頁。由于存儲器具有較高的訪問速度，例如100 ns，在1 ms時間內(nèi)可能對某頁面連續(xù)訪問成千上萬次，因此，通常不能直接利用計數(shù)器來記錄某頁被訪問的次數(shù)，而是采用移位寄存器方式。每次訪問某頁時，便將該移位寄存器的最高位置1，再每隔一定時間(例如100 ns)右移一次。這樣，在最近一段時間使用最少的頁面將是∑Ri最小的頁。

　　LFU置換算法的頁面訪問圖與LRU置換算法的訪問圖完全相同;或者說，利用這樣一套硬件既可實現(xiàn)LRU算法，又可實現(xiàn)LFU算法。應(yīng)該指出，LFU算法并不能真正反映出頁面的使用情況，因為在每一時間間隔內(nèi)，只是用寄存器的一位來記錄頁的使用情況，因此，訪問一次和訪問10 000次是等效的。

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

　　虛擬內(nèi)存，它的作用與物理內(nèi)存基本相似，但它是作為物理內(nèi)存的“后備力量”而存在的，也就是說，只有在物理內(nèi)存已經(jīng)不夠使用的時候，它才會發(fā)揮作用。

　　改變頁面文件位置的方法是：用鼠標(biāo)右鍵點(diǎn)擊“我的電腦”，選擇“屬性→高級→性能設(shè)置→高級→更改虛擬內(nèi)存”，在驅(qū)動器欄里選擇想要改變到的位置

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

　　并發(fā)性(concurrency)：指在計算機(jī)系統(tǒng)中存在著許多并發(fā)執(zhí)行的活動。對計算機(jī)系統(tǒng) 而言，并發(fā)是指宏觀上看系統(tǒng)內(nèi)有多道程序同時運(yùn)行，微觀上看是串行運(yùn)行。因為在 大多數(shù)計算機(jī)系統(tǒng)中一般只有一個CPU，在任意時刻只能有一道程序占用CPU。

　　共享性(sharing)：系統(tǒng)中各個并發(fā)活動要共享計算機(jī)系統(tǒng)中的各種軟、硬件資源，因此操作系統(tǒng)必須解決在多道程序間合理地分配和使用資源問題。

　　虛擬性(virtual)：虛擬是操作系統(tǒng)中的重要特征，所謂虛擬是指把物理上的一臺設(shè)備 變成邏輯上的多臺設(shè)備。例如，在操作系統(tǒng)中采用了spooling技術(shù)，可以利用快速、 大容量可共享的磁盤作為中介，模擬多個非共享的低速的輸入輸出設(shè)備，這樣的設(shè)備 稱為虛擬設(shè)備。

　　異步性：在多道程序環(huán)境下允許多個進(jìn)程并發(fā)執(zhí)行，但只有進(jìn)程在獲得所需的資源后方能執(zhí)行。在單處理機(jī)環(huán)境下，由于系統(tǒng)中只有一臺處理機(jī)，因而每次只允許一個進(jìn)程執(zhí)行，其余進(jìn)程只能等待。