操作系統(tǒng)期末復習要點總結

1、第一章OS地位、作用和定義地位：操作系統(tǒng)在硬件之上應用程序之下操作系統(tǒng)是控制應用程序執(zhí)行的程序，并充當應用程序和硬件間的接口.操作系統(tǒng)（Operating System）是最基本的系統(tǒng)軟件它控制計算機的所有資源（系統(tǒng) 的觀點）并提供應用程序開發(fā)的基礎（用戶的觀點）-OS分類和發(fā)展歷史批處理系統(tǒng)用于科學計算等但是CPU利用率仍然不高因為I/O操作太慢 多道程序系統(tǒng)用多道程序設計實現(xiàn)（仍是批處理系統(tǒng)）增加吞吐量;規(guī)模經濟；増加可靠性非對稱處理器（主從式）；對稱處理器（更普遍） l/n的處理速度按時完成多處理器系統(tǒng)（并行系統(tǒng)）：優(yōu)點： 類型：分時系統(tǒng)實時系統(tǒng)OS待征并發(fā)，共享，虛擬，異步性OS功能進

2、程管理，內存骨理，文件管理，設備管理，與用戶之間的接口 _些概念現(xiàn)代操作系統(tǒng)是由中斷驅動的特權指令：可能引起損S的指令每個用戶可以通過系統(tǒng)調用來執(zhí)行特權指令，稱之為軟中斷監(jiān)控程序（monitor）,多道程序系統(tǒng)、多處理系統(tǒng)、批處理、分時監(jiān)控程序：監(jiān)控程序包括服務器端和客戶端在一臺機器運行服務器程序客戶端運行客戶端程序可以動態(tài)監(jiān)視服務器的屏幕能將歸標和鍵盤事件傳過去，能進行一般的操作多道程序設計：2個或多個作業(yè)同時進入主存切換運行：當一個作業(yè)需要等待I/O時,切換到另一個不在等待I/O的作業(yè)讓CPV 保持忙碌多道程序系統(tǒng)：多道程序系統(tǒng)是在計算機內存中同時存放幾道相互獨立的程序，使它們在 管理程序

3、控制之下，相互穿插的運行多處理系統(tǒng)：有多個緊密通信的CPU,他們共享計算機總線，有時還有時鐘-內設和外設 等-三個優(yōu)點：増加吞吐童、規(guī)模經濟.増加可靠性批處理：批處理就是對某對象進行批童的處理分時：CPU還是通過在作業(yè)之間的切換來執(zhí)行多個作業(yè)，但耀由于切換頻率很高.用戶可 以在程序運行期間與之進行交互 引入多道程序設計的目的通過把各種不同用戶提出的CPU和IO設備請求相互交替的執(zhí)行，更高效的使用CPU,通 過不斷讓CPU工作來提高CPU的利用率 研究操作系統(tǒng)的幾種觀點系統(tǒng)觀點：用于資源管理器的操作系統(tǒng) 用戶觀點.用于擴展機的操作系統(tǒng) 什么是雙重操作模式？為什么要引進雙重操作模式CPU有兩種執(zhí)行

4、任務的模式1系統(tǒng)模式：用于執(zhí)行操作系統(tǒng)任務2用戶模式：用于執(zhí)行用戶任務為何引入：通過只能在系統(tǒng)模式下運行特權指令，可以保證操作系統(tǒng)時刻控制整個計算機 系統(tǒng)，并保證關鍵數據的安全- 系統(tǒng)態(tài)、用戶態(tài)以及轉換的條件用戶態(tài)，算態(tài)，目標程序態(tài)（目態(tài)），常態(tài)系統(tǒng)態(tài)，管態(tài)，核心態(tài)，管理態(tài)，特權態(tài)毎個用戶可以通過系統(tǒng)調用的方式執(zhí)行特權指令，操作系統(tǒng)視之為軟中斷 特權指令和非特權指令 特權指令：可以引起損害的指令 硬件保護機制所有I/O指令都是特權指令 用戶只能通過OS進行1/0-系統(tǒng)調用 確保用戶程序不能獲得管理模式第二章由一組鍵盤操作命令和命令解釋程序組成 為了用戶訪問系統(tǒng)資源而設，用戶程序獲取操作系統(tǒng)服務

5、的唯一途徑：系統(tǒng)調用戶與OS的兩種接口：定義和功能 命令接口： 程序接口： 用定義.功能系統(tǒng)調用：系統(tǒng)調用提供了操作系統(tǒng)提供的有效服務界面，提供了進程與操作系統(tǒng)之間的接口. 功能：允許用戶級進程請求操作系統(tǒng)服務分類：進程控制，文件管理，信息管理，設備管理，通信 操作系統(tǒng)的結構有幾種？各自的特點？結構：1整體式系統(tǒng)；一系列過程的集合，只要需要，就可以相互調用2. 層次式結構：實現(xiàn)模塊化，相對效率差3. C/S結構，易于維護，易于擴充，適用于分布式系統(tǒng)4虛擬機結構：提供了安全層操作系統(tǒng)特征 并發(fā)，共享，虛擬，異步性 幾個概念Shell.系統(tǒng)調用.虛擬機.陷入、陷入與中斷的區(qū)別 虛擬機：是硬件的完全

6、拷貝.Sh訓:解釋程序陷入： 陷入與中斷，中斷是異步的，因為從邏輯上來說，中斷的產生與當前正在執(zhí)行的進程無關。陷入是異常之一，異常是由當前正在執(zhí)行的進程產生.陷入的最主要的應用是在調試 中，被調試的進程遇到你設置的斷點，會停下來等待你的處理，等到你讓其®新執(zhí)行了， 它當然不會再去執(zhí)行已經執(zhí)行過的斷點指令.進程 定義:特征:第三章進程指一個正在執(zhí)行的程序，包括程序計數器、寄存器和變量當前值（程序是被動的實體，進程是活動的實體）（進程可中斷）（同一程序處理不同數據級時，可以構成不同的進程）動態(tài)性，并發(fā)性，獨立性，異步性，結構特征（進程映像） 程序順序執(zhí)行：程序順序執(zhí)行-嚴格按先后次序逐個

7、執(zhí)行語句/程序段程序順序執(zhí)行的特征順序性只有前一個操作結束，才能執(zhí)行后續(xù)操作封閉性程序運行時獨占全機資源可再現(xiàn)性與執(zhí)行速度無關程序并發(fā)執(zhí)行:程序的并發(fā)執(zhí)行多道程序系統(tǒng):多道程序的并發(fā)執(zhí)行某道程序的可以包含若干個能夠并發(fā)執(zhí)行的程 序段好處-充分利用系統(tǒng)資源提高系統(tǒng)處理能力程序并發(fā)執(zhí)行的特征間斷性共享資源，相互合作今相互制約9執(zhí)行暫停-執(zhí)行-失去封閉性一個程序的執(zhí)行受到其他程序的形響 不可再現(xiàn)性程序順序執(zhí)行-并發(fā)執(zhí)行的特點;進程與程序的區(qū)別與聯(lián)系進程是一個正在執(zhí)行的程序進程是一個活動的實體，程序是一個被動的實體進程不只是程序代碼，還包括當前的活動（用CPU各種寄存器的內容表示）以及堆桟段和 數據段

8、進程狀態(tài)（三狀態(tài)和五狀態(tài)）及其轉換五狀態(tài)：新：新進程正在被創(chuàng)建就緒：只要有機會獲得CPU就開始執(zhí)行運行：進程正在被執(zhí)行等待：等待某個事發(fā)生終止：進程已經完成或者被迫終止PCB：作用及其內容PCB：進程控制塊，包含許多與一個待定進程相關的信息內容：進程標識進程狀態(tài)信息進程控制信息進程控制主要功能；創(chuàng)建、撤銷.掛起、喚S.阻塞、激活等原語所需完成的功能; 進程在執(zhí)行過程中通過系統(tǒng)調用創(chuàng)建.Fork ()由于代碼相同，父子共享存儲空間Execve ()必須重新分配空間(windows CrealeProcess ()了解fork ()和exec()的工作原理進程通信的幾種方法 共享內存和消息隊列消息

9、隊列.共享內存進程在內存中由四個部分組成LPCB2 程序3數據4系統(tǒng)堆桟第四章什么是線程？為什么要引進線程？線程：又稱為輕誥級進程，是使用CPU的基本單元，由線程ID、程序計數器、寄存器集 合和堆桟組成屬于同一進程的線程共享進程的代碼段、數據段和其他操作系統(tǒng)資源 引入進程的目的使多個進程并發(fā)執(zhí)行改善資源利用率提高系統(tǒng)吞吐量引入線程的原因程序并發(fā)執(zhí)行時所付出的時空開銷I使OS具有更好的并發(fā)性 線程是調度的單位 進程是資源的擁有者 線程和進程的區(qū)別？優(yōu)點：響應度高資源資源共享 經濟多處理器體系結構的利用 線程的實現(xiàn)方式用戶級線程 內核級線程用戶級線程和內核級線程第五章CPU調度調度的幾種類型長程調

10、度.中程調度、進程調度長期調度一確定把哪個作業(yè)放到內存中執(zhí)行中期調度一主要在分時系統(tǒng)中使用將內存中的作業(yè)換出到外存中等到內存允許的情 況下再換入到內存中執(zhí)行。短期調度_從就緒隊列中選擇進程執(zhí)行并把CPU分配給它調度隊列 可剝奪調度和不可剝奪調度：定義和特點調度的四種時機:1 運行的進程一 終止2. 運行態(tài)等待態(tài)：ex:因請求I/O而阻塞：調用wait等待子進程終止3. 運行態(tài)-A就緒態(tài)4. 等待態(tài)-A就緒態(tài)非搶占調度：僅在第1.2種情況下才進行調度一旦把處理器分配給某進程，就讓他一直執(zhí)行，直到它完成或因等待某事件而阻塞 特點：實現(xiàn)簡單，系統(tǒng)開銷小，無需特別硬件支持適用大多數批處理系統(tǒng)可搶占調度

11、：發(fā)生在調度時機的各種情況特點：避免一個進程獨占處理器時間過長-A可能對所有進程提供較好服務系統(tǒng)開銷增加調度算法的性能評價準則準則：公平、CPU使用率（保證一直在工作）、響應時間（交互用戶響應的時間盡可能短） 周轉時間！ T （執(zhí)行完）-T （進入系統(tǒng)）等待時間：進程在各種隊列中等待時間的總和吞吐*:使每小時處理的作業(yè)數最多 評價：1、批處理系統(tǒng)周轉時間很重要2x分時系統(tǒng)響應時間短很重要調度程序的功能、時機; 進程由執(zhí)行到等待 進程由執(zhí)行到準備就緒 進程終止進程由等待到準備就緒 調度算法：FCFS、SJF. RR.優(yōu)先級、多級隊列、多級反饋隊列、HRRNf 點和缺點、適用場合 要求會計算：調度

12、順序、周轉時間.平均周轉時間周轉時間（Tq）=完成時間（finish time）-到達時間（arrive （ime）Tq/Ts （服務時間）FCFS：先到先服務按到達持續(xù)先后調度對長進程有優(yōu)勢利于多處理器處理的進程不利于多I/O處理的進程SJF：最短作業(yè)優(yōu)先 需要知道或者估計進程會執(zhí)行多長時間可能會是長進程產生饑餓不適合在實時系統(tǒng)中使RR專為分時系統(tǒng)設計時間片太短：開銷大 太長：變成FCFS 優(yōu)先級（非搶占式調度算法）高響應比優(yōu)先調度算法（HRRN） 響應比=（A+B） /BA：等待處理器的時間B：期望服務的時間第6章進程同步進程同步與互斥概念競爭條件：兩個或兩個以上的進程共享數據，而最終的執(zhí)

13、行結果則是根據執(zhí)行次序而決定 的，這種情況成為競爭條件（解決方法：控制對共享資源的訪問）臨界資源：多個進程可同時讀寫共享的數據臨界區(qū)程序使用臨界資源的部分稱為臨界區(qū)信號量：兩個或者多個進程可以用信號的方法進行協(xié)作-進程可以在任何地方停下來以等 待收到特定的信號，這種信號的實現(xiàn)叫做信號a.同步：忙等待：持續(xù)檢測一個變量知道它具有某一特定值互斥：如果有程序在臨界區(qū)中執(zhí)行，那么其他進程都不能在臨界區(qū)中執(zhí)行。這樣可以避免 競爭條件的發(fā)生-進程間的制約關系（直接.間接）互斥問題死鎖：兩個或者多個進程無限期等待一個事件的發(fā)生，而這個事件只能由這些等待的進程 之一來實現(xiàn)。饑餓：無限期阻塞 準則實現(xiàn)方法：硬件

14、.信號量（軟件方法不要求）硬件互斥：系統(tǒng)提供了特殊硬件指令允許原子地檢査和修改字的內容或者交換兩個字。信號量：兩個或者多個進程可以用信號的方法進行協(xié)作，進程可以在任何時候停下來等待 收到特定的信號-信號fi：定義、含義、操作（初始化，p,v）進程同步與互斥問題 生產者與消費者sem n = 0”/用于表示緩沖區(qū)不為空=1 sent 2 1;/用于緩沖區(qū)無人操作 sem e = N”/緩沖區(qū)當前剩余長度 void ProducerOWhiled)Produce(片Wait(e); VVait(s);AppendO; SignaKs); Signal(n);Void consunierOWhile

15、d)Wait(n); Wait(s); TakeO; SignaKs); Signal(e);Consume。;其他第7章死鎖死鎖定義:如果一個進程集合中每一個進程都在等待只能由本集合的另一個進程才能引發(fā)的* 件，則稱這種狀態(tài)為死鎖發(fā)生原因、4個必要條件互斥擁有并等待資源不可搶占環(huán)路等待 如果沒有環(huán)，那么一定沒有死鎖 掌握解決死鎖的方法：預防：破壞四個條件之一亶接預防：預防笫四個產生死鎖的條件（環(huán)路等待）.間接預防：預防前三個產生死鎖的條件預防互斥“不可??！避免：仔細檢査動態(tài)資源分配死鎖的避免是允許前三個條件的發(fā)生，但不允許后用一種機制來防止到達死鎖的狀態(tài) 掌握銀行家算法：如何判別安全性只要它

16、EAI location矩陣中一行的値都是0.就標記這個進程. 2）初給化一個IIS時向SwAvailable向S（3） S-個索引i.保證進程i還沒有標記-且Q的第i行小干零升- 即.對子有QikWWk.如果沒有這樣的行.«終止執(zhí)行（婦 如果找到這一行-則標記i«AI location相應的行加到碎上去. 副：Wk=WeMik然后執(zhí)行（3）沒有豐豔融潮谿険死皿每亍標記P4置嚴（0 0 0 0 1）P3的需求小于W,標記P3, W-W+ （0 0 0 1 0）=（0 0 0 1 1）因為沒有進程的需求小丁等丁W,所以結束P1和P2沒肴標記，死鎖010010010100001

17、10101R1R?R3R4R5RequestPlP2P3P410110110000001000000AllocationPlP2P3P4R1R2R3R4R5R1RZR3R4R5 |2|Re&OLVLe R1RZR3R4R5 |0|0|0|0|i| Available第8章內存管理（1）存儲器管理程序的功能邏輯地址：CPU生成的地址物理地址：內存單元的地址是物理地址地址重定位：邏輯地址向物理地址轉換的過程就是重定位 地址映射的概念：連續(xù)內存分配（固定分區(qū)、可變分區(qū)）： 固定分區(qū)：把存儲器分為若干大小相等的區(qū)（因調入數據小于分區(qū)而產生的分區(qū)空間浪費，叫做內部碎片） 可變分區(qū)：一開始運行的很

18、好，但是經過一段時間后，會出現(xiàn)外部碎片 BI DDY是兩者的結合內存骨理方法鏈表的內存分配方法： 每個麥項.P或h表示是進程還是空侑 起始地址 段長度指向下一個表項的指針First-Fit：從頭到尾掃描，選擇第一個足夠的空間 Best-Fit：找一個最接近需求的空間（空間小到大井） Worst-Fit：總是分配最大的空閑區(qū)（空間大到小排）頁式管理：原理、數據結構.地址-地址映射過程-特點 把主存分為定長的塊，成為頁框把用戶進程也分為與主存大小相等的塊，稱為頁內部碎片只在進程的最后一頁產生，沒有外部碎片（產生的碎片小，共享和保護不容易實現(xiàn)） MMU內存管理單元用于把虛擬地址轉化為物理地址頁表用于

19、顯示進程中每個頁在主存的哪個頁框中 邏輯地址由頁號和頁內地址偏移組成 頁表寄存器PTR用于存放頁表在內存中的起始地址和長度 碎片（內碎片，外碎片），怎么產生，如何解決？ 因為調入數據小于分區(qū)而產生分區(qū)空間的浪費，成為內部碎片 在分區(qū)之外的碎片.成為外部碎片內存緊縮解決 邏輯地址向物理地址的轉換過程就是重定位 緊縮亦稱作稱作“緊湊” “移動” 段式內存管理原理、數據結構、地址組成、地址變換、特點 不同段的長度不同，段的長度可以在運行中進行改變 產生的碎片浪費存儲空間，共享和保護容易實現(xiàn)段頁式內存管理原理.數據結構、地址組成、地址變換.特點將用戶的地址空間分段，段內按內存頁框的大小分頁 虛擬地址按

20、段號，段內頁號，和頁內位移三部分組成覆蓋與交換：原理.特點、比較覆蓋：在任何時候，都只能在內存中保留所需要的指令，新的指令可以覆蓋不要的指令和 數據不需要操作系統(tǒng)的特別支持交換：在內存不足的情況下，需要把一個進程整個換入和換出（進程分配固定的交換空間）第9章虛擬內存虛擬存儲器槪念、原理、實現(xiàn)方法、理論基礎（局部性原理概念：在一個新進程那個投入運行之前，OS只把開始時需要的幾頁/段裝入內存，進程 啟動運行，其余部分留在雄盤上進程運行時，如果欲取的指令或要訪問的數據己在內存, 則繼續(xù)執(zhí)行如果不在內存（缺頁/段）OS負責把所襦的頁/段調入內存，然后進程繼續(xù)執(zhí)行請求調入如果內存己滿，OS選擇內存中暫時

21、不用的頁/段，調出到磁盤上；騰出內 存空間后，再調入需要的頁/段置換功能虛擬使用戶邏輯存儲器與原理：允許僅把進程的一部分裝入內存就可運行進程，具有請求調入和置換功能，從 邏輯上擴充內存容量(用戶看到的)：容量巨大的存儲器 物理存儲器分離.實現(xiàn)方式S請求分頁系統(tǒng)/頁式虛擬存儲系統(tǒng)分頁+親求調頁+頁面置換請求分頁系統(tǒng)/段式虛擬存儲系統(tǒng)分段+請求調段+分段置換段頁式虛擬存儲系統(tǒng)段頁式+請求調頁+頁面置換理論基礎！局部性原理在一段時間內，程序的執(zhí)行僅限于某個部分，所訪問的存儲空間也局限于某個區(qū) 域慮擬存儲器的特征離散性內存的分配方式離散多次行進程執(zhí)行時不必全部裝入內存進程被分成多次調入內存對換性在進程

22、執(zhí)行過程中，e時不需要的代碼和數據被換出，換入需要的部分進程的換入換出虛擬性從邏輯上擴充內存容量用戶看到的請求頁式管理基本原理：當需要一頁時，才把該頁調入內存調頁程序/頁面調度程序只調入需要的頁，進程裝入需要I/O量減少進程需要的內存空間減少 內存可以容納更多用戶進程 什么是缺頁中斷.發(fā)生時機及處理過程缺頁/頁故障/頁錯誤進程執(zhí)行時，要訪問頁不在內存缺頁中斷OS響應缺頁中斷，把所需頁面調入內存發(fā)生時機：在指令執(zhí)行期間產生中斷信號,并被處理處理過程：引起缺頁中斷的指令被重新執(zhí)行置換策略(OPT、FIFO. LRU)：計算缺頁次數.缺頁中斷率、判別是否有Belady異 常頁面i換的峽頁處理基本流程

23、：1查找所需頁面在磁盤上的位置2. 找到一個空閑頁框，如果沒有，(1) 應用頁面置換算法選擇一個“犧牲”頁框(2) 如果“犧牲”頁框中的頁被修改過，把它寫回磁盤(3) 更新頁表和頁框表3. 將所需頁面讀入空閑頁框，更新頁表和頁框表4重啟進程(導致缺頁的指令)LRU：最近最少使用 OPT：理論最佳算法FIFO：先進先出算法邏輯地址到物理地址轉換 存儲的共享與保護方法保護：存儲區(qū)域保護和存儲方式保護什么是TLB?其作用？描述帶有TLB的地址轉換過程TLB (快表):傳輸后備緩沖器是一個內存管理單元作用：用于改進虛擬地址到物理地址轉換速度的緩存頁式地址=頁面其實地址+頁內偏移地址什么是Behidy異

24、常？哪一種算法會產生？為什么？ 缺頁率隨頁框分配的數量增加而增加FIFO頁置換 請求段式管理的原理請求分段系統(tǒng)是在分段系統(tǒng)的基礎上，增加了請求調段及分段置換功能后形成的，以 分段作為換入、換出的單位.虛擬段頁式原理地址轉換什么是顛簸(抖動)？為什么會出現(xiàn)？進程不斷的缺頁、調頁，幾乎不能完成有效工作分配給進程的頁框數 < 進程當前運行需要的頁面數原因：CPV利用率低增加多道程序度每個進程的頁框數更少“>缺頁次數更多 >CPU利用率更低第10章文件管理概念：文件、目錄、目錄項、記錄、域、文件管理系統(tǒng)、路徑、當前路徑 文件：記錄在外存上的相關信息的具有名稱的集合 目錄：文件屬性的集

25、合，本身也是文件目錄項：記錄：一組相關的域的集合，用于描述一個對象某方面的屬性 域:基本數據元素一個域包含一個值描述一個域：數據類型、長度 域的長度.固定的.可變的文件管理系統(tǒng)：操作系統(tǒng)的一部分5最可見的部分路徑：當前路徑：文件系統(tǒng)的功能和目的OS中負責操縱和管理文件的一整套設施方便用戶“按名存取”實現(xiàn)文件的共享和保護為用戶提供管理各種文件的方法存取方便、格式統(tǒng)一、安全可靠功能：創(chuàng)建、刪除、打開.關閉、讀、寫.執(zhí)行文件管理目錄管理文件存儲空間管理 文件的共享和保護 提供方便的接口文件的組織（邏輯）結構：類型、特點文件的邏輯結構/文件組織文件中記錄的組織結構由用戶訪問記錄的方式決定從用戶觀點出發(fā)

26、觀察到的文件組織形式，用戶可以直接處理的數據和結構，獨立 于物理特性文件的物理結構游儲結構文件在輔存上的存儲組織方式，與存儲介質的存儲性能有關，依賴于組塊策略. 文件分配策略 兩大類型：有結構文件/記錄文件用戶對文件內的信息按邏輯上獨立的含義再劃分信息單位一一錄由一個以上的記錄構成定長記錄變長記錄：域的數目不同，域的長度不定無結構文件噴式文件用戶對文件內的信息不再劃分可獨立的單位整個文件由一串順序的字符流組成文件的存取方法訪問文件中信息的方式典型的存取方式：順序存取：一個記錄接著一個記錄直接存取/隨機存取文件由定長的邏輯記錄組成 程序可以按任意次序訪問記錄 基于隨機存取設備素引存取文件存取控制

27、矩陣與文件存取控制表（FCB相關 文件控制塊FCB用于描述和控制文件的數據結構包括了文件名和文件的各種屬性文件控制塊與文件一一對應 文件目錄/目錄文件控制塊的有序集合一個文件控制塊就是一個文件目錄項一個文件目錄也被看作是一個文件，稱為目錄文件第u章文件系統(tǒng)實現(xiàn)文件系統(tǒng)的層次結構I/O控制組成設備驅動程序中斷處理程序任務內存2磁盤基本文件系統(tǒng)向設備驅動程序發(fā)命令文件組織模塊掌握關于文件機器邏輯記錄和物理塊的信息文件的分配和位置邏輯記錄物理塊磁盤空閑空間管理邏輯文件系統(tǒng)管理關于文件系統(tǒng)結構的信息一元數據目錄文件控制塊（FCB）負責文件的保護和安全文件分配方法三種方法：原理、優(yōu)缺點連續(xù)分配：原理:每

28、個文件占據磁盤上一組連續(xù)的物理塊優(yōu)點：實現(xiàn)簡單，只需記錄起始位置（塊號）和長度（塊數） 缺點：難以預知文件的大小i文件擴展困難；空間浪費（碎片） 鏈接分配：（文件一磁盤物理塊的鏈表原理5一個文件的物理塊可以分布在整個磁盤目錄項記錄起始塊號和終止塊號每個物理塊中包含指向下一塊的指針一一塊號僅供系統(tǒng)使用優(yōu)點：解決了連續(xù)分配的全部問題沒有空間浪費不需要事先知道文件大小文件大小可以増長缺點：不能有效支持隨機訪問：下一塊指針占用物理塊空間；可靠性 索引分配：原理：把所有塊指針一起放到_個位置索引塊毎個文件有自己的索引塊索引塊一磁盤塊地址的數組索引塊第i個條目文件第i個物理塊的塊號文件目錄項包抵索引塊的地

29、址（塊號）優(yōu)點：支持隨機訪問沒有外碎片充分利用磁盤空間缺點：索引塊中空間的浪費索引塊多大合適？多級索引分配 目錄項一級索引二級索引數據塊Unix的i節(jié)點的定義索引節(jié)點包含（13F）字節(jié)的地址信息第卜10個一指向文件的頭10塊（宜接地址）第11個一指向一個單重索引塊第12個一指向一個雙索引塊第13個一指向一個三重索引塊n的大小由系統(tǒng)決定磁盤存儲空間管理方法位圖、空閑塊鏈接、空閑目錄、成組塊鏈接法、空閑目錄/空閑表法 位圖：使用一個向量表示磁盤的分配情況向量的每一位對應一塊0已分配1可用向量的長度取決于輔存的容量空閑塊鏈接：特殊的空閑塊一保存n個自由塊的地址前n-1個塊是實際的空閑塊最后一個又是特

30、殊的空閑塊 成組塊鏈接法：786#278# 80#220#-645#s_nfrees_free|0|HI|2|220#內存中的專用塊961979899s_nfres_free0|HI|2|199#220#549#786#278#難點：多級索引分配、成組塊鏈接法110#176#80#22ft#110常645#34第12章大容量存儲結構確盤組織結構磁道仕雄盤片的表面被邏輯地劃分成圓形磁道 扇區(qū)S：磁道再進一步劃分為扇區(qū)柱面C：位于同一磁臂位置的磁道集合形成了柱面一次磯盤存取操作的時間組成 Ta=Tsek+Trd+T transfer 旋轉延遲時間：指定扇區(qū)移動到磁頭下面所經歷的時間 Trd=：l/

31、(2rhr為磁盤轉速(轉/s)傳輸時間！把數據從磁盤獨處，或向磁盤寫入所經歷的時間 Transfer=b/(rN) b：欲讀寫的磯盤調度算法先進先出FIFO/先進先出FCFS8按順序處理請求隊列中的項目公平、簡單，性能不佳最短尋道時間有限（SSTF）沿磁臂的移動方向掃描,選擇離當前磁道最近的請求 磁頭到達此咅鳥彎§二佬豎圖蘭歹里反向掃描183 1990 1437 53 656798 122124III- IIIII:JC-SCAN算法只進行一個方向的掃描當到達最后一個磁道后，磁頭迅速返回另一端,與SCAN算法的區(qū)別:在滿足一個方向上的最后 一個請求以后9不再繼續(xù)前進號而是立即改變方向

32、183 199queue = 98, 183, 37, 122, 14.124, 65, 67 head starts at 5337536567II II98122124III4LO183 19914375365 6798122124與C-SCAN算法的區(qū)別：在滿足一個方向上的最后一個 請求以后,不再繼續(xù)前進，而是立即改變方向，直接到達 另一端的第it丐$宀亠亠_訪問順序，移動距離第13章I/O系統(tǒng)什么是緩沖？為什么要引入緩沖?緩沖是用來保存兩個設備之間或在設備和應用程序之間所傳輸數據的內存區(qū)域 理由：1處理數據流的生產者與消費者之間的速度差異2. 協(xié)調傳輸數據大小不一致的設備3. 支持應用

33、程序I/O的復制語義區(qū)分獨占設備、共享設備、虛擬設備獨占設備：在一段時間內只允許一個進程或線程訪問共享設備：在一段時間內允許多個進程或線程同時訪問對于每一時刻仍只允許一個進程或線程訪問通常是可尋址、可隨機訪問的設備虛擬設備：通過虎擬技術把一臺獨占設備變換為若干臺邏輯設備，供若干個用戶（進程）同 時使用，經過虛擬技術處理的設備，稱為虛擬設備-理解對共享設備可同時使用的含義；見上一條簡述實現(xiàn)虛擬設備的基本條件，虛擬設備的實現(xiàn)原理采用Spooling技術后，每個作業(yè)都感到各自擁有獨占使用的設備Spooling 技術：將一臺獨占設備改造成若干臺邏輯設備，供若干個用戶同時使用（像共事設備一樣） 經過這種

34、技術處理后的設備成為虛擬設備解釋Spooling系統(tǒng)及其組成；輸入井和輸出井的位置及作用輸入井與輸出井系統(tǒng)在輔存開辟的用作緩沖的存儲區(qū)域，存放 從輸入設備輸入的信息存放作業(yè)的執(zhí)行結果（輸出）設備獨立性的含義應用程序獨立于具體使用的物理設備邏輯設備.在應用程序中，用邏輯設備名稱來請求使用某類設備 物理設備：系統(tǒng)實際執(zhí)行時，用物理設備名稱系統(tǒng)完成邏輯設備名物理設備名設備分配方法設備的絕對號用戶申請設備不用絕對號，應當指明設備類用戶申請多個同類設備“設備類，相對號”第一次作業(yè)書上的作業(yè)1.1操作系統(tǒng)的兩個主要目標是什么？答：（1）為計算機用戶提供一個環(huán)境讓用戶可以方便地在計算機硬件上執(zhí)行程序（2）以

35、公平有效的方式分配計算機的資源用于解決特定的問題簡記為：1.方便用戶使用2.讓計算機高效執(zhí)行13多道程序設計的主要優(yōu)點是什么？答：通過把各種不同的用戶提出的對CPU和I/O設備的請求相互交替執(zhí)行而更高效地使用 CPU.它通過不斷讓CPU工作而提高CPI：的利用率 2.2系統(tǒng)模式和用戶模式之間的區(qū)別？答：系統(tǒng)模式：用于執(zhí)行操作系統(tǒng)任務用戶模式：用于執(zhí)行用戶任務通過只能在系統(tǒng)模式下執(zhí)行特權指令可以保證操作系統(tǒng)時刻控制整個計算機系統(tǒng)，并保證 關鍵數據的安全（如果在用戶模式下執(zhí)行特權指令.這稱謂非法指令）2.3陷入與中斷之間的區(qū)別？中斷是一個系統(tǒng)中由硬件產生的用于改變執(zhí)行流程的信號-一個中斷控制程序來

36、處理中斯, 執(zhí)行完成后返回被中斷的程序指令.陷阱是因為錯誤，或者用戶程序的特定請求而引起的軟件生成的中斷-2.5下面哪些指令是特權指令？ a）設置定時器的值；b）讀時鐘：C）清除內存；d）關閉中斷,e） 從用戶模式切換到監(jiān)督程序模式。 aGd,e是特權指令 3.7系統(tǒng)調用的用途是什么？ 答:允許用戶級進程請求操作系統(tǒng)的服務 補充作業(yè)1. 把下面的應用程序分為交互性和批處理兩類：字處理、按月生成銀行報表.計算圓周率 到百萬分位、飛行模擬器答：交互性：字處理、飛行模擬器批處理：按月生成銀行報表、計算M周率到百萬分位2. 寫出操作系統(tǒng)的五大功能。答：進程管理.內存管理、文件管理、設備管理、與用戶之間

37、的接口.3. 為什么操作系統(tǒng)的發(fā)展與計算機硬件的發(fā)展息息相關？答：如果沒有硬件的支持，很多方法無法實現(xiàn).例如，要想內存中同時保存多個進程則希 要相應的寄存器支持。附加題1. 在網上搜集關于操作系統(tǒng)的定義，總結出其中的共性和特性。2. 操作系統(tǒng)是否應包含像網絡瀏覽器和電子郵件程序這樣的應用程序？談一下你的觀點。第二次作業(yè)書上的作業(yè)4.2論述短期、中期、長期調度之間的區(qū)別答：短期調度一從就緒隊列中選擇進程執(zhí)行并把CPU分配給它.中期調度一主要在分時系統(tǒng)中使用.將內存中的作業(yè)換出到外存中等到內存允許的情 況下再換入到內存中執(zhí)行長期調度一確定把哪個作業(yè)放到內存中執(zhí)行.它們之間的主要區(qū)別是執(zhí)行的頻率不同

38、.短期調度執(zhí)行頻率高而長期調度執(zhí)行頻率低.4.4兩個進程進行上下文切換的操作3.2答：通常，操作系統(tǒng)必須保存當前運行進程的狀態(tài)并恢復下一個要調度的進程的狀態(tài)。保 存一個進程的狀態(tài)通常包括CPU所有番存器的值和內存的分配情況。5.3用戶級線程和內核級線程之間的區(qū)別？相互對比的優(yōu)勢在哪里？ 答：（1）內核不知道用戶級線程的存在，但內核知道內核級線程的存在（2）內核調度內核級線程，而用戶級線程則由線程庫調度在要體現(xiàn)系統(tǒng)靈活性的時候使用用戶級線程好，因為用戶級線程可以自己設計自己的 調度。內核級線程則被內核知道，所以可以保證一個線程阻塞時可以調度一個進程的另一 個線程，減少系統(tǒng)開銷。補充作業(yè)1.假設有

39、一個進程，它的工作流程是先運行150ms.然后進行I/O,最后執(zhí)行250ms結束 如果系統(tǒng)中的進程有三個狀態(tài)，當時間片為200ms請寫出進程A從被系統(tǒng)接納到運行結束所經歷的狀態(tài)轉換并說明原因，答：被系統(tǒng)接納之后：就緒運行（原因：被調度執(zhí)行）、運行阻塞（原因：執(zhí)行I/O操作）、 阻塞就緒（原因：I/O操作完成）、就緒運行（原因：被調度執(zhí)行）、運行就緒（原因： 時間片到）.就緒運行（原因：被調度執(zhí)行）.結束-2為什么現(xiàn)代計算機系統(tǒng)中還有中斷處理程序是用匯編語言編寫？答：通常高級語言不允許直接訪問CPU.例如，一個中斷控制程序需要打開或者關閉中斷 己完成對特定設備的服務，或者處理一個進程的堆棧中的數

40、據。并且，中斷例程應該可以 以最快的速度執(zhí)行完成。附加題：1. 單線程文件服務器和多線程文件服務器的比較.如果數據保存在cache中，獲取數據的時 間jtlSms,而如果數據不在zche中，則需要另外的75ms將磯盤中的數據讀入cache.假設 高速緩存的命中率是2/3,則單線程文件服務器1秒鐘最多可以處理多少個請求？多線程服務 器1秒鐘最多可以處理多少個請求？答：在單線程服務器中，從cache中得到數據的時間是15 msec而從磁盤中得到數據的時 間是90 mseco則加權平均值長2/3*15+1/3*90=40,因此服務器1秒鐘可以處理1000/4（X25 次請求；對于多線程服務器，所有的

41、等待磁盤時間都可以相互覆蓋，所以每次磁盤請求都 只襦要15 msec.所以服務器1秒鐘可以處理1000/15=66.67次請求。第三次作業(yè)7-1什么是忙等待？操作系統(tǒng)中其他種類的等待有什么？忙等待是否可以完全避免？為什 么？答：所謂忙等待是不斷測試等待一個條件滿足。除了忙等待之外，操作系統(tǒng)中還有一種等待是讓進程在等待狀態(tài)阻塞等待一個條件滿 足，當條件滿足時，通過中斷告知進程忙等待的進程浪費CPU的時間，降低了效率，并且有可能導致優(yōu)先級反轉.但是并不 能完全避免忙等待。如果在等待時間不是很長，并且系統(tǒng)內部進程的數量小，并且對CPU 利用率要求不高的無優(yōu)先級或者不同優(yōu)先級的進程不會有同一個臨界區(qū)的

42、小型系統(tǒng)而言， 可以考慮使用忙等待的方式解決簡單的問題.另外，在多CPU的小型系統(tǒng)中，忙等待所導 致的優(yōu)先級反轉的問題并不存在，因此這樣的有優(yōu)先級的小型系統(tǒng)也可以使用忙等待7.9吸煙者問題：有3個吸煙者和一個供應者第一個吸煙者有自己的煙草；第二個吸煙者 有自己的紙；第三個吸煙者有自己的火柴。供應者每次隨機放兩樣東西到桌子上提供給3 個吸煙者之中的一個以完成吸煙。請用信號量為吸煙者和供應者進程編寫程序 semaphore a2=0: semaphore agent=l;provider （）while(true)set i to value between 0 and 2; wait(agent

43、);/put two items on table signal (ai):Smoker (int i)while(true)wait (aCi); smoke;signal (agent);補充作業(yè)1.假設有三個進程R、WK W2共享緩沖區(qū)B。B中只能存放一個數.R每次從輸入設備 中讀一個整數放入B中。如果這個整數是奇數，由取出打印，如果這個整數是偶數， 則由W2取出打印。規(guī)定僅當B中沒有數據或數據已經被打印才會啟動R去讀數。W1、 W2對B中的數據不能重復打印，當B中沒有數據時也不能打印。要求用信號量操作寫出 R、WK W2三個進程的程序。（請詳細描述所使用變量的含義）semaphore

44、SO=1 （表示緩沖區(qū)中可以存放的»據數目）semaphore SUO （表示W1可以打印的數據數目） semaphore S2=0 （表示V2可以打印的數據數目） R:While (true)Read integer into item wail(SO);put item in Bif (itein%2= =1) signal(Sl); if (itein%2= =0) signal(S2);Wl:While (true)wail(Sl);Take item from B; signal(SO); P rint item;W2:While (true)wait(S2);Take i

45、tem from B;Signal(SO);Print item;2. 有一個鐵籠子，獵手放入老虎，農民放入豬，動物園等待取走老虎，飯店等待取走豬。 籠子中只能放入一個動物-請使用信號量方法為獵手、農民、動物園.飯店進程編寫程序。semaphore no=l, tiger=O;pig=O; hunter 0 wait (no); put in tiger： signal(tiger);farmer ()wait(no); put in pig： signal(pig);zoo 0 wait(tiger); take tiger： signal(no);hotel 0 wait(pig); ta

46、ke pig; signal(no);3. 某寺廟，有小、老和尚若干有一個水缸，由小和尚提水入缸供老和尚飲用水缸可容 10桶水水取自一個井中，水井窄，每次只能容一個水桶水桶總數為3。水缸每次進出 也僅1桶水，不可以同時進行。請設置合適的信號量描述小和尚老和尚取水.入水的算 法-Semaphore bucket=3, well=l Jar=10, empty=l, full=O; Void littkmonkOwhiled)wait(em pty); wait(bucket); wait(well 片 取水； signal(well); wait(jar)； 放水； signalljar); s

47、ignal(bucket); signal(full);Void oldmonkOwhiled) wait(fuH); wait(bucket); wait(jar); 取水； signaKjar); signal(bucket); signahempty);附加題1.獨木橋問題：某條河上只有一座獨木橋，兩邊都有人要過河，為保證安全，一個方向有 人過河另一個方向的人就要等待，并且允許一個方向上的人連續(xù)過河。請使用信號量實現(xiàn) 正確的管理。semaphore s=l, sl=l,s2=l; int rcl,rc2;one 0wait (si);rcl+;if (rcl=l) wait (s); s

48、ignal (si);walk through;wait (si);rcl;if (re 1=0) signal (s); signal (si);another 0wait(s2);rc2+：if (rc2=l) wait (s):signal($2);walk through;wait(s2);rc2;if (rc2=0) signal (s);signal (s2);有人給出這樣的獨木橋問題的答案，看看有什么問題么？(1 )定義兩個信號量S1和S2 , S1 :=1 , S2 :操作管理時的程序應如下:(2)假定開始時讓河東的一個人先過橋，則用PVone()S1S2anotherOS2S

49、1第四次作業(yè) 書上的作業(yè)：6.3 之 b,c,db.各個進程的周轉時間FCFSRRSJFPhorhvPiIP19W16卩2II2I1P313rAISPi114-)19P31914g6G各個進程的等待時間PCFSRRSJFrriorilvP.0q96P210J00內II516幾1331IS卩51494Id最小的是SJF 8.8有3個進程共享4個資源，一次只能保留或者釋放一個資源每個進程最大需要2個單 元。說明不會發(fā)生死鎖。答：如果所有的資源都被占用并且還有一個或多個進程在無限制的等待更多的資源那么死 鎖就會發(fā)生。但是，如果所有的4個資源都被占用，那么一定有一個進程已經得到了所有 的兩個資源，那么

50、這個進程就可以運行完并釋放它占用的兩個資源，這樣就可以讓其他的 進程正確地工作完成。& 13a.Need 矩陣的樣子是(Max-Allocation) 07006050240020200b.因為有一個執(zhí)行次序是pK p2. p4、pO可以執(zhí)行完，所以是安全狀態(tài)。20424C.如果滿足，則系統(tǒng)的available變成1 1 0 0 allocation 變成0 01 41 30 60 0這時的Need是030060302400202這時如果PO先歸還它占有的(0012),那么available的值是(1112)，可以 找到一個執(zhí)行次序p0,p2,pl,p3,p4保證所有進程都可以安全執(zhí)行

51、完，會處于安全狀態(tài)，因 此這個請求會被滿足。附加S1- N個進程共享M個資源，一次只能保留或者釋放一個資源。每個進程最大需要單元的 數目不超過并且所有的最大需求的總和小于M+N.說明不會發(fā)生死鎖答：使用與銀行家算法一樣的術語，定義claimCi=進程I所需要的所有資源數; allocationCi=當前分配給進程I的資源數；deficiti=進程I仍然需要的資源數. 那么：NNN三小誠卩= -h aihcaisofs < Af + "死鎖時，所有的資源都被占用：N£ a”0ca 為朿=M并且一些進程在等待使用更多的資源但是從上面的等式中我們發(fā)現(xiàn)這意味著最后一個進程j已

52、經獲取了所有的資源，因為deficitj =0,這樣它就能 夠完成他的任務并釋放占用的所有資源，讓系統(tǒng)中其他的進程繼續(xù)執(zhí)行。所以死鎖不會發(fā) 生.第五次作業(yè)書上的作業(yè)9.2內部碎片與外部碎片之間的區(qū)別？答：一個作業(yè)占據了一個內存區(qū)域或者頁，但是其中的一部分沒有使用，把沒有使用的部分成 為內部碎片.內部碎片不會被操作系統(tǒng)或者其他進程使用，除非這個作業(yè)執(zhí)行完并且釋放它所占用的內 存區(qū)域.外部碎片是在分區(qū)之間存在的不能夠被使用的小的內存.9.5內存按順序有100k, 500k. 200k, 300k. 600k,用首次適應、最佳適應和最差適應如 何放置 212k, 417k, 112k, 426k 的

53、進程？首次適應算法放入500K的分區(qū)放入600K的分區(qū)放入288K的分區(qū)(產生新的分區(qū)288K = 500K - 212K) 必須等待最佳適應算法答：(1)212K417K112K426K(2)212K5SC入300K的分區(qū)417MC入500K的分區(qū)112腹入200K的分區(qū)426iaftA600K 的分區(qū)(3) 最差適應算法212K®入600K的分區(qū)417做入500K的分區(qū)112腹入388K的分區(qū)426K必須等待在這個例子中，最佳適應算法是最好的。9. 8假設一個有8個Ik頁面的邏輯地址空間，映射到一個32個頁框的物理內存，問：邏輯 地址多少位？物理地址多少位？邏輯地址是由頁號和頁內地址位移組成物理地址是由員內地址偏移和頁框號相組成a. 邏輯地址：13 bitsb. 物理地址：15 bits9.14為什么純分段比純分頁更容易實現(xiàn)共享可充入模塊答：因為段是基于內存的邏輯劃分而不是物理劃