操作系統(tǒng)復習

1、第一章操作系統(tǒng)定義： 操作系統(tǒng)是控制和管理計算機系統(tǒng)內各種硬件和軟件資源，有效地組織多道程序運行的系統(tǒng)軟件（或程序集合），是用戶與計算機之間的接口。操作系統(tǒng)功能： (1)存儲管理功能：內存分配（策略）、地址映射（轉換）、內存保護（不干擾不越界）、內存擴充（邏輯擴充：虛擬存儲器與置換）。(2)處理機管理功能：作業(yè)和進程調度（創(chuàng)建進程，算法）、進程控制（創(chuàng)建、撤銷、喚醒、掛起等）和進程通信（依賴和制約：同步和互斥）。(3)設備管理功能：緩沖區(qū)管理（速度匹配），設備分配（請求、策略），設備驅動（通道）和設備無關性（邏輯設備名、物理設備名）。(4)文件管理功能：文件存儲空間的管理（分配與回收），文件操

2、作的一般管理（創(chuàng)建、刪除、打開、關閉），目錄管理，文件的讀寫管理和存取控制（防止越權與破壞）。(5)用戶接口：命令界面:這是指由OS提供了一組聯(lián)機命令(語言)， 用戶可通過鍵盤輸入有關命令，來直接操縱計算機系統(tǒng)。程序界面：OS提供了一組系統(tǒng)調用，用戶可在自己的應用程序中通過相應的系統(tǒng)調用，來操縱計算機。圖形界面：用戶通過屏幕上的窗口和圖標來操縱計算機系統(tǒng)和運行自己的程序。并發(fā)：是指兩個或多個活動在同一給定的時間間隔中進行。宏觀概念。如CPU共享。共享：是指計算機系統(tǒng)中的資源被多個進程所共用。如CPU、硬盤、內存、數(shù)據(jù)等。 互斥地共享：某進程申請資源、若空閑、分配、運行，下一個進程只能等待，直到

3、前一進程釋放資源。 宏觀上同時訪問、微觀上并發(fā)執(zhí)行的共享：如硬盤上文件的訪問。不確定性：是指系統(tǒng)中各種事件發(fā)生順序的不可預測性。多道程序設計：基本思想是在內存中同時存放多道程序，在管理程序的控制下交替地執(zhí)行。這些作業(yè)共享CPU和系統(tǒng)中的其他資源。分時系統(tǒng)：操作系統(tǒng)多個用戶終端，分時共享主機資源。時間片、交互性。實時系統(tǒng)：系統(tǒng)及時響應外部事件的請求，在規(guī)定的時間內完成對該事件的處理，并控制所有實時任務協(xié)調一致地運行。實時性、高可靠性。第二章進程：進程最根本的屬性是動態(tài)性和并發(fā)性，指程序在并發(fā)環(huán)境中的執(zhí)行過程。進程隊列的連接方式：線性隊列，鏈接，索引。進程和線程的關系： 一個進程可以有多個線程，但

4、至少要有一個線程；而一個線程只能在一個進程的地址空間內活動。 資源分配給進程，同一進程的所有線程共享該進程的所有資源。 處理機分配給線程，即真正在處理機上運行的是線程。 線程在執(zhí)行過程中需要協(xié)作同步。不同進程的線程間要利用消息通信的辦法實現(xiàn)同步。進程的同步：同步進程通過共享資源來協(xié)調活動，在執(zhí)行時間的次序上有一定約束。在協(xié)調動作的情況下，多個進程可以共同完成一項任務。雖然彼此不直接知道對方的名字，但知道對方的存在和作用。進程的互斥：邏輯上這兩個進程本來完全獨立，不知對方的存在，毫無關系，只是由于競爭同一個物理資源而相互制約。信號量：用于解決進程同步、互斥問題的通用工具。PV操作的含義：PV操作

5、由P操作原語和V操作原語組成（原語是不可中斷的過程），對信號量進行操作，具體定義如下： P（S）：將信號量S的值減1，即S=S-1； 如果S0，則該進程繼續(xù)執(zhí)行；否則該進程置為等待狀態(tài)，排入等待隊列。 V（S）：將信號量S的值加1，即S=S+1； 如果S0，則該進程繼續(xù)執(zhí)行；否則釋放隊列中第一個等待信號量的進程。什么是信號量？信號量（semaphore）的數(shù)據(jù)結構為一個值和一個指針，指針指向等待該信號量的下一個進程。信號量的值與相應資源的使用情況有關。當它的值大于0時，表示當前可用資源的數(shù)量；當它的值小于0時，其絕對值表示等待使用該資源的進程個數(shù)。注意，信號量的值僅能由PV操作來改變。 一般來

6、說，信號量S0時，S表示可用資源的數(shù)量。執(zhí)行一次P操作意味著請求分配一個單位資源，因此S的值減1；當S0時，表示已經(jīng)沒有可用資源，請求者必須等待別的進程釋放該類資源，它才能運行下去。而執(zhí)行一個V操作意味著釋放一個單位資源，因此S的值加1；若S0，表示有某些進程正在等待該資源，因此要喚醒一個等待狀態(tài)的進程，使之運行下去。【例1】生產(chǎn)者-消費者問題在多道程序環(huán)境下，進程同步是一個十分重要又令人感興趣的問題，而生產(chǎn)者-消費者問題是其中一個有代表性的進程同步問題。下面我們給出了各種情況下的生產(chǎn)者-消費者問題，深入地分析和透徹地理解這個例子，對于全面解決操作系統(tǒng)內的同步、互斥問題將有很大幫助。（1）一個

7、生產(chǎn)者，一個消費者，公用一個緩沖區(qū)。定義兩個同步信號量：empty表示緩沖區(qū)是否為空，初值為1。 full表示緩沖區(qū)中是否為滿，初值為0。生產(chǎn)者進程while(TRUE)生產(chǎn)一個產(chǎn)品; P(empty); 產(chǎn)品送往Buffer; V(full);消費者進程while(True)P(full); 從Buffer取出一個產(chǎn)品; V(empty); 消費該產(chǎn)品; （2）一個生產(chǎn)者，一個消費者，公用n個環(huán)形緩沖區(qū)。定義兩個同步信號量：empty表示緩沖區(qū)是否為空，初值為n。full表示緩沖區(qū)中是否為滿，初值為0。 設緩沖區(qū)的編號為1n-1，定義兩個指針in和out，分別是生產(chǎn)者進程和消費者進程使用的指

8、，指向下一個可用的緩沖區(qū)。生產(chǎn)者進程while(TRUE) 生產(chǎn)一個產(chǎn)品; P(empty); 產(chǎn)品送往buffer（in）； in=(in+1)mod n； V(full);消費者進程while(TRUE) P(full); 從buffer（out）中取出產(chǎn)品； out=(out+1)mod n； V(empty); 消費該產(chǎn)品; （3）一組生產(chǎn)者，一組消費者，公用n個環(huán)形緩沖區(qū) 在這個問題中，不僅生產(chǎn)者與消費者之間要同步，而且各個生產(chǎn)者之間、各個消費者之間還必須互斥地訪問緩沖區(qū)。定義四個信號量：empty表示緩沖區(qū)是否為空，初值為n。full表示緩沖區(qū)中是否為滿，初值為0。mutex1生產(chǎn)

9、者之間的互斥信號量，初值為1。mutex2消費者之間的互斥信號量，初值為1。 設緩沖區(qū)的編號為1n-1，定義兩個指針in和out，分別是生產(chǎn)者進程和消費者進程使用的指針，指向下一個可用的緩沖區(qū)。生產(chǎn)者進程while(TRUE) 生產(chǎn)一個產(chǎn)品; P(empty); P(mutex1)； 產(chǎn)品送往buffer（in）； in=(in+1)mod n； V(mutex1); V(full);消費者進程while(TRUE) P(full) P(mutex2)； 從buffer（out）中取出產(chǎn)品； out=(out+1)mod n； V（mutex2）； V(empty); 消費該產(chǎn)品; 需要注意的

10、是無論在生產(chǎn)者進程中還是在消費者進程中，兩個P操作的次序不能顛倒。應先執(zhí)行同步信號量的P操作，然后再執(zhí)行互斥信號量的P操作，否則可能造成進程死鎖?！纠?】讀者寫者問題：（1）讀者優(yōu)先。對于讀者優(yōu)先，應滿足下列條件：如果新讀者到：無讀者、寫者，新讀者可以讀；有寫者等待，但有其它讀者正在讀，則新讀者也可以讀；有寫者寫，新讀者等待。如果新寫者到：無讀者，新寫者可以寫；有讀者，新寫者等待；有其它寫者，新寫者等待。設置兩個信號量：讀互斥信號量rmutex和寫互斥信號量wmutex。另外設立一個讀計數(shù)器readcount，它是一個整型變量。rmutex：用于讀者間互斥地訪問讀者計數(shù)的公用變量readcou

11、nt（臨界資源） ，初值為1。readcount初值為0。wmutex：用于保證一個寫者與其他讀者或寫者互斥地訪問共享資源，初值為1。讀者Readers: while(TRUE) P(rmutex); /開始對rc共享變量進行互斥訪問 readcount=readcount+1; /來了一個讀進程，讀進程數(shù)加1 if(readcount=1) /如是第一個讀進程，判斷是否有寫進程在臨界區(qū) P(wmutex); /若有，讀進程等待，若無，阻塞寫進程 V(rmutex); /結束對rc共享變量的互斥訪問 執(zhí)行讀操作； P(rmutex); /開始對rc共享變量的互斥訪問 readcount=rea

12、dcount-1; /一個讀進程讀完，讀進程數(shù)減1 if(readcount=0)/最后一個離開臨界區(qū)的讀進程需要判斷是否有寫進程 V(wmutex); /需要進入臨界區(qū)，若有，喚醒一個寫進程進臨界區(qū) V(rmutex); /結束對rc共享變量的互斥訪問 其他使用讀取的數(shù)據(jù) 寫者Writers： while(TRUE) P(wmutex); /無讀進程，進入寫進程；若有讀進程，寫進程等待 執(zhí)行寫操作 V(wmutex); /寫進程完成；判斷是否有讀進程需要進入臨界區(qū)， /若有，喚醒一個讀進程進臨界區(qū) P(wmutex); /無讀進程，進入寫進程；若有讀進程，寫進程等待 執(zhí)行寫操作； V(wmu

13、tex); /寫進程完成；判斷是否有讀進程需要進入臨界區(qū)， /若有，喚醒一個讀進程進臨界區(qū) 讀者出讀者進同步機制的原則：空閑讓進，忙則等待，有限等待，讓權等待。第三章死鎖的定義： 是指兩個或兩個以上的進程在執(zhí)行過程中，因爭奪資源而造成的一種互相等待的現(xiàn)象，若無外力作用，它們都將無法推進下去。產(chǎn)生死鎖的根本原因：資源有限，且操作不當產(chǎn)生死鎖的四個必要條件：互斥條件，占有且等待條件，不可搶占條件，循環(huán)等待條件安全狀態(tài)：在當前分配狀態(tài)下，進程的安全序列P1,P2, Pn是這樣組成的：若對于每一個進程Pi（1in），它需要的附加資源可被系統(tǒng)中當前可用資源與所有進程Pj（ ji）當前占有資源之和所滿足，

14、則P1, P2, Pn為一個安全序列。這時系統(tǒng)處于安全狀態(tài)。安全序列：針對當前分配狀態(tài)來說，系統(tǒng)至少能夠按照某種次序分配資源(直至最大需求)，并且使它們依次成功地運行完畢，這種進程序列P1,P2,Pn就是安全序列*存在安全序列時不會死鎖；但系統(tǒng)進入不安全狀態(tài)也未必產(chǎn)生死鎖；死鎖是不安全狀態(tài)的特例；銀行家算法：p82三級調度各指的什么： 作業(yè)調度（高級調度）:從用戶工作流程的角度。從輸入的一批作業(yè)中選出若干作業(yè)，為其分配必要的內存，建立相應的用戶進程和系統(tǒng)進程，然后將程序和數(shù)據(jù)調入內存，等待進程調度。時間上通常是分鐘、小時或天。作業(yè)狀態(tài) 提交狀態(tài) 后備狀態(tài) 執(zhí)行狀態(tài) 完成狀態(tài)作業(yè)調度功能： 記錄

15、系統(tǒng)中各個作業(yè)的情況。 按照某種調度算法從后備作業(yè)隊列中挑選作業(yè)。 為選中的作業(yè)分配內存和外設等資源。（通常由存儲管理與外設管理程序完成） 為選中的作業(yè)建立相應的進程，并把該進程放入就緒隊列中。 作業(yè)結束后進行善后處理工作。 進程掛起與對換（中級調度）:從存儲器資源的角度。將進程的部分或全部換出到外存上，將當前所需部分換入到內存。(指令和數(shù)據(jù)必須在內存里才能被CPU直接訪問。) 進程調度（低級調度）:指根據(jù)一定的算法，將CPU分派給就緒隊列中的一個進程，獲得CPU的控制權。先來先服務算法（FCFS）：非搶占式優(yōu)先級算法：采用非搶占式優(yōu)先算法時，最先來到的是進程P1，所以最先處理進程P1直到它結

16、束，由于其他進程不能搶占P1的進程，所以只能等待P1完成，假設這些等待進程（注意，是等待中的進程，還未到達的進程不能參與比較，到達時間非常重要?。┲蠵4的優(yōu)先數(shù)最高，所以當P1執(zhí)行完成后，先執(zhí)行進程P4，以此類推。更多列題見p129（8&9）。時間片法：主要用于分時系統(tǒng)中的進程調度。中斷：指當出現(xiàn)需要時，CPU暫時停止當前程序的執(zhí)行轉而執(zhí)行處理新情況的程序和執(zhí)行過程。即在程序運行過程中，系統(tǒng)出現(xiàn)了一個必須由CPU立即處理的情況，此時，CPU暫時中止程序的執(zhí)行轉而處理這個新的情況的過程就叫做中斷。第五章邏輯地址：用戶程序經(jīng)編譯之后的每個目標模塊都以0為基地址順序編址，其余指令中的地址都相對于首地

17、址而編址。這種地址稱為相對地址或邏輯地址；物理地址：內存中各物理存儲單元的地址是從統(tǒng)一的基地址開始順序編址的，這種地址稱為絕對地址或物理地址。地址重定位：把作業(yè)地址空間中使用的邏輯地址變換成內存空間中的物理地址的過程。又稱地址映射。動態(tài)地址重定位：在程序運行過程中要訪問數(shù)據(jù)時再進行地址變換。由地址變換機構進行的地址變換，硬件上需要重定位寄存器的支持。優(yōu)點：OS可以將一個程序分散存放于不連續(xù)的內存空間，可以移動程序。有利于實現(xiàn)共享。它是虛擬存儲的基礎。缺點：需要硬件支持（通常是CPU），OS實現(xiàn)較復雜。碎片：經(jīng)過一段時間的分配回收后，內存中存在很多很小的空閑塊。它們每一個都很小，不足以滿足分配要

18、求；但其總和滿足分配要求。這些空閑塊被稱為碎片。 在一個分區(qū)內部出現(xiàn)的碎片（即被浪費的空間）稱做內部碎片，如固定分區(qū)法會產(chǎn)生內部碎片。 在所有分區(qū)之外新增的碎片稱做外部碎片。拼湊：移動某些已分配區(qū)的內容，使所有進程的分區(qū)緊挨在一起，而把空閑區(qū)留在另一端。這種技術稱為緊縮（或拼湊）內存管理保護措施：防止地址越界&防止操作越權分頁技術（地址轉換的計算）： 內存快 頁面頁號塊號0213283645p=INT A/L d=A MOD LA為邏輯地址L為頁面大小頁號p / 頁內地址d例題：某作業(yè)J的邏輯地址空間為5個頁，每頁2048字節(jié)，且已知該作業(yè)的頁表如右圖請畫出地址轉換圖，求出有效邏輯地址4865

19、B所對應的物理地址。A=4865B,L=2048B,則 P=2, d=769.則物理地址為17153B分段技術（地址轉換的技術）：段號s段內地址d邏輯地址：例題：已知段表如圖所示，將下面的邏輯地址轉化為物理地址段號基址長度合法0 / 非法10219600 01230014 0290100 131327580 04195296 0(0，430),(1,10),(1,11),(2,500),(3,400),(4,112)219+430=649虛擬存儲器：借助于外存空間，允許一個進程在其運行過程中部分裝入內存。虛擬存儲系統(tǒng)將內存和外存有機結合在一起，從而得到一個容量相當于外存，速度接近于內存的存儲體

20、系。請求分頁原理：請求分頁存儲管理技術是在單純分頁技術基礎上發(fā)展起來的，二者的根本區(qū)別在于請求分頁提供虛擬存儲器?；舅枷胧牵寒斠粋€進程的部分頁面在內存時就可調度它運行；在運行過程中若用到的頁面尚未在內存，則把它們動態(tài)換入內存。頁面走向： 0100，0432，0101，0612，0102，0103，0104，0101，0611，0102，0103，0104，0101，0610，0102，0103，0104，0101，0609，0102，0105 若每頁100個字節(jié)，則頁面走向簡化為：1，4，1，6，1，6，1，6，1，6，1以下為缺頁率計算的圖示-先進先出法FIFO：最佳置換法OPT：最近最少

21、使用置換法LRU：抖動：在虛存中，頁面在內存與外存之間頻繁調度，以至于調度頁面所需時間比進程實際運行的時間還多，此時系統(tǒng)效率急劇下降，甚至導致系統(tǒng)崩潰。這種現(xiàn)象為“抖動或顛簸”。第六章文件系統(tǒng)的功能： 文件管理。創(chuàng)建、刪除、讀寫、執(zhí)行等。 目錄管理。每個文件創(chuàng)建一個目錄項，若干目錄項構成一個目錄文件。可進行文件檢索和權限限制。 文件存儲空間管理。對文件存儲空間的分配與回收、文件邏輯地址與物理地址的映射。 文件的共享和保護。共享、保護、轉儲、恢復。 提供方便的接口。用戶觀點（方便、可靠、共享、保護）、系統(tǒng)的觀點（存儲空間組織、分配、信息傳輸?shù)龋Ｎ募到y(tǒng)目錄的作用：為了加快對文件的檢索，往往將文

22、件控制塊集中在一起進行管理。這種文件控制塊的有序集合稱為文件目錄。文件控制塊就是其中的目錄項。完全由目錄項構成的文件稱為目錄文件。文件目錄實現(xiàn)文件名與存放盤塊之間的映射。UNIX系統(tǒng)中目錄分解的意義（課后題會計算）：【課后題】在實現(xiàn)文件系統(tǒng)時，為加快文件目錄的檢索速度，可利用“文件控制塊分解法”。假設目錄文件存放在磁盤上，每個盤塊512字節(jié)。文件控制塊占64字節(jié)，其中文件名占8字節(jié)。通常將文件控制塊分解成兩部分，第1部分占10字節(jié)（包括文件名和文件內部號），第2部分占54字節(jié)（包括文件內部號和文件其他描述信息）。（1）假定某一目錄文件共有254個文件控制塊，試分別給出采用分解法前和分解法后，查

23、找該目錄的某一個文件控制塊的平均訪問磁盤次數(shù)。（2）一般地，若目錄文件分解前占用n個盤塊，分解后改用m個盤塊存放文件名和文件內部號，請給出訪問磁盤次數(shù)減少的條件。答：（1）采用分解法前，一個盤塊存放5l2/64=8目錄項，254個目錄項需要32個盤塊，查找一個文件的平均訪問的盤塊數(shù)：(1+32)/2=16.5次； 采用分解法后，一個盤塊存放5l2/10=51目錄項，254個目錄項需要5個盤塊，查找一個文件的第1部分平均訪問的盤塊數(shù)：(1+5)/2=3次；查找第2部分需要訪問磁盤1次，故查找一個文件控制塊的平均訪問磁盤次數(shù)是314次。（2）訪問磁盤次數(shù)減少的條件為：（n1）/2（m1）/21 即 mn2第七章按使用性質對設備的分類： 存儲設備：計算機用來存儲信息的主要設備。 輸入/輸出設備：字符設備。SPOOLING系統(tǒng)概念：SPOOLing實現(xiàn)過程：SPOOLing技術的特點:(1)提高了I/O速度.從對低速I/O設備進行的I/O操作變?yōu)閷斎刖蜉敵鼍牟僮?如同脫機操作一樣,提高了I/O速度,緩和了CPU與低速I/O設備速度不