計算機(jī)操作系統(tǒng)原理復(fù)習(xí)大全

1、名詞解釋計算機(jī)系統(tǒng)的層次結(jié)構(gòu)硬件層 操作系統(tǒng)層 支撐軟件層 應(yīng)用軟件層 財務(wù)系統(tǒng)航空訂票上網(wǎng)瀏覽電子商務(wù)科學(xué)計算(應(yīng)用軟件)編譯程序匯編程序數(shù)據(jù)庫(支撐軟件)操作系統(tǒng)(系統(tǒng)軟件)操作系統(tǒng)(系統(tǒng)軟件)計算機(jī)硬件用戶n用戶4用戶3用戶2用戶1實用程序操作系統(tǒng)系統(tǒng)調(diào)用庫操作系統(tǒng)內(nèi)核硬件層操作系統(tǒng)是管理系統(tǒng)資源、控制程序執(zhí)行，改善人機(jī)界面，提供各種服務(wù)，合理組織計算機(jī)工作流程和為用戶有效使用計算機(jī)提供良好運(yùn)行環(huán)境的最基本的一種系統(tǒng)軟件。管理 處理器管理 主要是對中央處理機(jī) (CPU) 進(jìn)行動態(tài)管理。為了提高CPU的利用率，采用多道程序設(shè)計技術(shù)(multiprogramming)。當(dāng)多道程序并發(fā)(eru

2、ptsimultaneously) 運(yùn)行時, 引進(jìn)進(jìn)程的概念(將一個程序分為多個處理模塊，進(jìn)程是程序運(yùn)行的動態(tài)過程)。通過進(jìn)程管理，協(xié)調(diào)(coordinate)多道程序之間的CPU分配調(diào)度、沖突處理及資源回收等關(guān)系。 存儲管理 是對存儲“空間”的管理，主要指對內(nèi)存資源的管理。存儲管理就是要根據(jù)用戶程序的要求為用戶分配主存儲區(qū)域。(1)主存分配 ； (2)地址轉(zhuǎn)換與存儲保護(hù)； (3)主存共享 ； (4)存儲擴(kuò)充 。 設(shè)備管理 是對硬件設(shè)備的管理，其中包括對輸入輸出設(shè)備的分配、啟動、完成和回收。負(fù)責(zé)管理計算機(jī)系統(tǒng)中除了中央處理機(jī)和主存儲器以外的其它硬件資源文件管理將邏輯上有完整意義的信息資源（程序

3、和數(shù)據(jù)）以文件的形式存放在外存儲器（磁盤、磁帶）上的，并賦予一個名字，稱為文件。是操作系統(tǒng)對計算機(jī)系統(tǒng)中軟件資源的管理并發(fā)性從宏觀上看，并發(fā)性反映一個時間段中幾個進(jìn)程都在同一處理器上，處于運(yùn)行還未運(yùn)行結(jié)束狀態(tài)。 從微觀上看，任一時刻僅有一個進(jìn)程在處理器上運(yùn)行。 并發(fā)進(jìn)程分類：無關(guān)的，交往的。（1）無關(guān)的并發(fā)進(jìn)程無關(guān)的并發(fā)進(jìn)程：一組并發(fā)進(jìn)程分別在不同的變量集合上操作，一個進(jìn)程的執(zhí)行與其他并發(fā)進(jìn)程的進(jìn)展無關(guān)。 并發(fā)進(jìn)程的無關(guān)性是進(jìn)程的執(zhí)行與時間無關(guān)的一個充分條件，又稱為Bernstein條件。 Bernstein條件R(pi)=a1,a2,an，程序pi在執(zhí)行期間引用的變量集 W(pi)=b1,b

4、2,bm，程序pi在執(zhí)行期間改變的變量集 若兩個程序的變量集交集之和為空集： R(p1)W(p2)R(p2)W(p1)W(p1)W(p2)= 則并發(fā)進(jìn)程的執(zhí)行與時間無關(guān)。例如，有如下四條語句： S1: a := x + y S2: b := z + 1 S3: c := a b S4: w := c + 1 于是有：R(S1)=x,y ,R(S2)=z，R(S3)=a,b，R(S4)=c；W(S1)=a, W(S2)=b，W(S3)=c，W(S4)=w。 S1和S2可并發(fā)執(zhí)行，滿足Bernstein條件。其他語句并發(fā)執(zhí)行可能會產(chǎn)生與時間有關(guān)的錯誤。 （2）交往的并發(fā)進(jìn)程交往的并發(fā)進(jìn)程：一組并發(fā)

5、進(jìn)程共享某些變量，一個進(jìn)程的執(zhí)行可能影響其他并發(fā)進(jìn)程的結(jié)果。 與時間有關(guān)的錯誤對于一組交往的并發(fā)進(jìn)程，執(zhí)行的相對速度無法相互控制，各種與時間有關(guān)的錯誤就可能出現(xiàn)。 與時間有關(guān)錯誤的表現(xiàn)形式： 結(jié)果不唯一 永遠(yuǎn)等待 1.飛機(jī)票售票問題（結(jié)果不唯一）void T1( ) 按旅客訂票要求找到Aj; int X1=Aj; if(X1=1) X1-; Aj=X1; 輸出一張票; else 輸出信息票已售完; void T2( ) 按旅客訂票要求找到Aj; int X1=Aj; if(X1=1) X1-; Aj=X1; 輸出一張票; else 輸出信息票已售完; 2.主存管理問題（永遠(yuǎn)等待）/memory

6、為初始主存容量 int X=memory； void borrow(int B) while(BX) 進(jìn)程進(jìn)入等待主存資源隊列; X=X-B ; 修改主存分配表，進(jìn)程獲得主存資源; void return(int B) X=X+B; 修改主存分配表; 釋放等主存資源進(jìn)程; 進(jìn)程是運(yùn)行著的程序：不僅包含代碼，而且包含當(dāng)前的活動狀態(tài)： 程序計數(shù)器指明下一條要執(zhí)行的指令 處理器寄存器的內(nèi)容 進(jìn)程棧：方法參數(shù)，返回地址，局部變量 數(shù)據(jù)段：全局變量 進(jìn)程是可并發(fā)執(zhí)行的程序在某個數(shù)據(jù)集合上的一次計算活動，也是操作系統(tǒng)進(jìn)行資源分配和保護(hù)的基本單位。 進(jìn)程三態(tài)轉(zhuǎn)換運(yùn)行態(tài) 就緒態(tài)：時間片到貨出現(xiàn)更高優(yōu)先級的進(jìn)程

7、時，當(dāng)前進(jìn)程被迫讓出處理器 就緒態(tài) 運(yùn)行態(tài)：CPU空閑時，調(diào)度程序選中一個就緒進(jìn)程執(zhí)行 運(yùn)行態(tài) 等待態(tài)：運(yùn)行進(jìn)程等待使用某種資源或某事件發(fā)生 等待態(tài) 就緒態(tài)：進(jìn)程所需資源滿足或某事件已經(jīng)完成 進(jìn)程生命周期創(chuàng)建步1：在進(jìn)程列表中增加一項，從PCB池中申請一個空閑PCB，為新進(jìn)程分配惟一的進(jìn)程標(biāo)識符； 步2：為新進(jìn)程的進(jìn)程映像分配地址空間，以便容納進(jìn)程實體。進(jìn)程管理程序確定加載到進(jìn)程地址空間中的程序； 步3：為新進(jìn)程分配除主存空間外的其他各種所需資源； 步4：初始化PCB，如進(jìn)程標(biāo)識符、處理器初始狀態(tài)、進(jìn)程優(yōu)先級等； 步5：把新進(jìn)程狀態(tài)置為就緒態(tài)，并移入就緒進(jìn)程隊列； 步6：通知操作系統(tǒng)的某些模塊

8、，如記賬程序、性能監(jiān)控程序。撤銷步1根據(jù)撤銷進(jìn)程標(biāo)識號，從相應(yīng)隊列中找到并移除； 步2將該進(jìn)程擁有的資源歸還給父進(jìn)程或操作系統(tǒng)； 步3若該進(jìn)程擁有子進(jìn)程，先撤銷它的所有子進(jìn)程，以防它們脫離控制； 步4回收PCB，并歸還到PCB池。 進(jìn)程阻塞和喚醒 （自學(xué)了解）進(jìn)程阻塞步驟： 步1停止進(jìn)程執(zhí)行，保存現(xiàn)場信息到PCB； 步2修改進(jìn)程PCB有關(guān)內(nèi)容，如進(jìn)程狀態(tài)由運(yùn)行態(tài)改為等待態(tài)等，并把修改狀態(tài)后的進(jìn)程移入相應(yīng)事件的等待隊列中； 步3轉(zhuǎn)入進(jìn)程調(diào)度程序去調(diào)度其他進(jìn)程運(yùn)行。 進(jìn)程喚醒步驟： 步1從相應(yīng)的等待隊列中移出進(jìn)程； 步2修改進(jìn)程PCB的有關(guān)信息，如進(jìn)程狀態(tài)改為就緒態(tài)，并移入就緒隊列； 步3若被喚醒

9、進(jìn)程比當(dāng)前運(yùn)行進(jìn)程優(yōu)先級高，重新設(shè)置調(diào)度標(biāo)志線程是操作系統(tǒng)進(jìn)程中能夠獨(dú)立執(zhí)行的實體（控制流），是處理器調(diào)度和分派的基本單位。作業(yè)周轉(zhuǎn)與平均周轉(zhuǎn)時間如果作業(yè)i提交給系統(tǒng)的時刻是ts，完成時刻是tf，該作業(yè)的周轉(zhuǎn)時間ti為： ti = tf ts（作業(yè)在系統(tǒng)里的等待時間與運(yùn)行時間之和） 平均作業(yè)周轉(zhuǎn)時間 T = (ti) / n 作業(yè)帶權(quán)周轉(zhuǎn)時間和平均作業(yè)帶權(quán)周轉(zhuǎn)時間如果作業(yè)i的周轉(zhuǎn)時間為ti，所需運(yùn)行時間為tk，則稱wi=ti /tk為該作業(yè)的帶權(quán)周轉(zhuǎn)時間。 ti是等待時間與運(yùn)行時間之和，故帶權(quán)周轉(zhuǎn)時間總大于1。 平均作業(yè)帶權(quán)周轉(zhuǎn)時間W = (wi) / n 響應(yīng)比響應(yīng)比 1+已等待時間/估計運(yùn)

10、行時間作業(yè)調(diào)度算法先來先服務(wù)算法（不可剝奪）FCFS調(diào)度算法的平均作業(yè)周轉(zhuǎn)時間與作業(yè)提交的順序有關(guān)。具有相同優(yōu)先級的進(jìn)程使用FCFS，F(xiàn)CFS只考慮進(jìn)程等候時間而忽視了作業(yè)的運(yùn)行時間缺點(diǎn)：重要進(jìn)程無法得到及時響應(yīng)，若大進(jìn)程先到，容易導(dǎo)致平均等待時間過大，增加了進(jìn)程的平均周轉(zhuǎn)時間。短作業(yè)優(yōu)先算法（不可剝奪）-作業(yè)運(yùn)行時間事先估計總選取估計計算時間最短的作業(yè)投入運(yùn)行。只考慮用戶估計的作業(yè)運(yùn)行時間而忽視了作業(yè)等待時間優(yōu)點(diǎn)：作業(yè)同時到達(dá)的情況下，降低作業(yè)平均等待時間，提高系統(tǒng)吞吐量。缺點(diǎn)：大進(jìn)程餓死最短剩余時間優(yōu)先（可剝奪式的短進(jìn)程優(yōu)先算法）優(yōu)點(diǎn)：保證及時響應(yīng)，降低進(jìn)程平均等待時間缺點(diǎn)：系統(tǒng)開銷增大，

11、保存進(jìn)程的運(yùn)行情況以比較時間，剝奪本身消耗處理機(jī)時間響應(yīng)比最高者優(yōu)先（不可剝奪）優(yōu)先數(shù)（要求服務(wù)時間+已等待時間）/（要求服務(wù)時間）響應(yīng)比=響應(yīng)時間/服務(wù)時間短作業(yè)容易得到較高響應(yīng)比， 長作業(yè)等待時間足夠長后，也將獲得足夠高的響應(yīng)比， 饑餓現(xiàn)象不會發(fā)生。 優(yōu)點(diǎn)：既考慮作業(yè)等待時間，又考慮作業(yè)的運(yùn)行時間，既照顧短作業(yè)又不使長作業(yè)的等待時間過長，改進(jìn)了調(diào)度性能。消除饑餓現(xiàn)象 優(yōu)先級調(diào)度算法（靜態(tài)+動態(tài)）1.根據(jù)進(jìn)程占有CPU時間多少來決定,當(dāng)進(jìn)程占有CPU時間愈長,那么，在它被阻塞之后再次獲得調(diào)度的優(yōu)先級就越低，反之,進(jìn)程獲得調(diào)度的可能性越大; 2.根據(jù)進(jìn)程等待CPU時間多少來決定,當(dāng)進(jìn)程在就緒隊

12、列中等待時間愈長,那么，在它被阻塞之后再次獲得調(diào)度的優(yōu)先級就越高，反之,進(jìn)程獲得調(diào)度的可能性越小。 多級反饋隊列調(diào)度（了解）多個進(jìn)程就緒隊列，每個序列有調(diào)度級別，優(yōu)先級逐層降低。優(yōu)先級最高的的序列時間片最小缺頁中斷率假定作業(yè)p共計n頁，系統(tǒng)分配給它的主存塊只有m塊（mn）。如果作業(yè)p在運(yùn)行中成功的訪問次數(shù)為s， 不成功的訪問次數(shù)為F，則總的訪問次數(shù)為： A = S + F 又定義： f = F / A 稱f為缺頁中斷率。影響缺頁中斷率f的因素有： (1)主存頁框數(shù)。 (2)頁面大小。 (3)頁面替換算法。 (4)程序特性。 I/O控制方式(1)輪詢方式 (2)中斷方式 （3)DMA方式 靜態(tài)地

13、址重定位裝載器將代碼模塊裝入內(nèi)存后，將所有邏輯地址修改成物理地址 特點(diǎn)： 無需硬件支持，易于實現(xiàn) 無法實現(xiàn)代碼模塊的移動 動態(tài)地址重定位裝載器不修改邏輯地址，而是通過將代碼起始地址置入重定位寄存器（段寄存器）來實現(xiàn)尋址 特點(diǎn)： 需要硬件（重定位寄存器）支持 可以實現(xiàn)代碼的動態(tài)移動 進(jìn)程互斥進(jìn)程互斥是指若干個進(jìn)程因相互爭奪獨(dú)占型資源時所產(chǎn)生的競爭制約關(guān)系。 進(jìn)程同步進(jìn)程同步指為完成共同任務(wù)的并發(fā)進(jìn)程基于某個條件來協(xié)調(diào)它們的活動，因為需要在某些位置上排定執(zhí)行的先后次序而等待、傳遞信號或消息所產(chǎn)生的協(xié)作制約關(guān)系。臨界區(qū)：并發(fā)進(jìn)程中與共享變量有關(guān)的程序段臨界資源：共享變量代表的資源原語：內(nèi)核中執(zhí)行時不

14、可被中斷的過程信號量： 一個進(jìn)程在某一特殊點(diǎn)上被迫停止執(zhí)行直到接收到一個對應(yīng)的特殊變量值，這種特殊變量就是信號量（一種軟件資源）死鎖定義如果在一個進(jìn)程集合中的每個進(jìn)程都在等待只能由該集合中的其他一個進(jìn)程才能引發(fā)的事件，則稱一組進(jìn)程或系統(tǒng)此時發(fā)生死鎖。 死鎖的四個必要條件互斥條件：進(jìn)程互斥使用資源 部分分配條件：申請新資源時不釋放已占有資源 不剝奪條件：一個進(jìn)程不能搶奪其他進(jìn)程占有的資源 環(huán)路條件：存在一組進(jìn)程循環(huán)等待資源的 死鎖定理如果能在進(jìn)程-資源分配圖中消去此進(jìn)程的所有請求邊和分配邊，成為孤立結(jié)點(diǎn)。經(jīng)一系列簡化，使所有進(jìn)程成為孤立結(jié)點(diǎn)，則該圖是可完全簡化的；否則則稱該圖是不可完全簡化的。

15、系統(tǒng)為死鎖狀態(tài)的充分條件是：當(dāng)且僅當(dāng)該狀態(tài)的進(jìn)程-資源分配圖是不可完全簡化的。該充分條件稱為死鎖定理。 生產(chǎn)者-消費(fèi)者item Bk; semaphore empty;empty=k; /可以使用的空緩沖區(qū)數(shù) semaphore full; full=0; /緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù) semaphore mutex;mutex=1; /互斥信號量 int in=0; /放入緩沖區(qū)指針 int out=0; /取出緩沖區(qū)指針 cobegin process producer_i ( ) process consumer_j ( ) while(true) while(true) produce(

16、 ); P(full); P(empty); P(mutex); P(mutex); take( ) from Bout; append to Bin; out=(out+1)%k; in=(in+1)%k; V(mutex); V(mutex); V(empty); V(full); consume( ); coend 讀者-寫者int readcount=0;/讀進(jìn)程計數(shù) semaphore writeblock,mutex; writeblock=1;mutex=1; cobegin process reader_i( ) process writer_j( ) P(mutex); P(

17、writeblock); readcount+; 寫文件; if(readcount=1) V(writeblock); P(writeblock); V(mutex); 讀文件; P(mutex); readcount-; if(readcount=0) V(writeblock); V(mutex); coend 理發(fā)師int waiting=0;/等候理發(fā)顧客坐的椅子數(shù) int CHAIRS=N; /為顧客準(zhǔn)備的椅子數(shù) semaphore customers,barbers,mutex; customers=0;barbers=0;mutex=1; cobegin process bar

18、ber( ) while(true) P(customers); /有顧客嗎？若無顧客，理發(fā)師睡眠 P(mutex); /若有顧客時，進(jìn)入臨界區(qū) waiting-; /等候顧客數(shù)少一個 V(barbers); /理發(fā)師準(zhǔn)備為顧客理發(fā) V(mutex); /退出臨界區(qū) cut_hair(); /理發(fā)師正在理發(fā)(非臨界區(qū)) process customer_i( ) P(mutex); /進(jìn)入臨界區(qū) if(waitingCHAIRS) /有空椅子嗎 waiting+; /等候顧客數(shù)加1 V(customers); /喚醒理發(fā)師 V(mutex); /退出臨界區(qū) P(barbers); /理發(fā)師忙，顧客坐下等待 get_haircut(); /否則顧客坐下理發(fā) else V(mutex); /人滿了，走吧！ Coend 哲學(xué)家吃面semaphore fork5; for (int i=0;i5;i+) forki= 1; cobegin process philosopher_i( )/*i=0,1,2,3 */ while(true) thi