1、計算機操作系統復習資料1. 操作系統的定義操作系統(Operating System，簡稱OS)是管理計算機系統的全部硬件資源包括軟件資源及數據資源；控制程序運行；改善人機界面；為其它應用軟件提供支持等，使計算機系統所有資源最大限度地發揮作用，為用戶提供方便的、有效的、友善的服務界面。操作系統通常是最靠近硬件的一層系統軟件，它把硬件裸機改造成為功能完善的一臺虛擬機，使得計算機系統的使用和管理更加方便，計算機資源的利用效率更高，上層的應用程序可以獲得比硬件提供的功能更多的支持。操作系統是一個龐大的管理控制程序，大致包括5個方面的管理功能:進程與處理機管理、作業管理、存儲管理、設備管理、文件管理。

2、2. 操作系統的作用1） OS作為用戶與計算機硬件系統之間的接口2） OS作為計算機系統資源的管理者3） OS實現了對計算機資源的抽象3. 操作系統的基本特征1） 并發2） 共享3） 虛擬4） 異步4. 分時系統的概念把計算機的系統資源（尤其是CPU時間）進行時間上的分割，每個時間段稱為一個時間片，每個用戶依次輪流使用時間片，實現多個用戶分享同一臺主機的操作系統。5. 分時系統要解決的關鍵問題（2個）1） 及時接收2） 及時處理6. 并發性的概念并發性是指兩個或多個事件在同一事件間隔內發生。在多道程序環境下，并發性是指在一段時間內宏觀上有多個程序在同時運行，但在單處理機系統中，每一時刻卻僅能有

3、一道程序執行，故微觀上這些程序只能是分時的交替執行。7. 程序順序執行的特征和并發執行的特征順序執行的特點: 順序性 封閉性 可再現性程序并發執行的特點：1）、間斷性（失去程序的封閉性）2）、不可再現性 任何并發執行都是不可再現3）、進程互斥（程序并發執行可以相互制約）8. 進程的定義進程是指在系統中能獨立運行并作為資源分配的基本單位。為了使參與并發執行的每個程序（含數據）都能獨立的運行，在操作系統中必須為之配置一個專門的數據結構，稱為進程控制塊（PCB）。系統利用PCB來描述進程的基本情況和活動過程，進而控制和管理進程。9. 進程的組成部分進程是由一組機器指令，數據和堆棧組成的，是一個能獨立

4、運行的活動實體。由程序段，相關的數據段和PCB三部分便構成了進程實體（又稱進程映像）。10. 進程的狀態（狀態之間的變化）就緒狀態、執行狀態、阻塞狀態。處于就緒狀態的進程，在調度程序為之分配了處理機之后，該進程便可以執行，相應的，他就由就緒狀態轉變為執行狀態。正在執行的進程，如果因為分配給它的時間片已經用完而被暫停執行時，該進程便由執行狀態又回到就緒狀態；如果因為發生某事件而使進程的執行受阻（如進程請求訪問臨界資源，而該資源正在被其它進程訪問），使之無法繼續執行，該進程將有執行狀態轉變為阻塞狀態。處于阻塞狀態的進程，在獲得了資源后，轉變為就緒狀態。11. 進程同步的概念進程同步是是并發執行的諸

5、進程之間能有效地相互合作，從而使程序的執行具有可再現性，簡單的說來就是：多個相關進程在執行次序上的協調。12. PV原語的作用PV原語通過操作信號量來處理進程間的同步與互斥的問題。其核心就是一段不可分割不可中斷的程序。13. 處理死鎖的四種方法（有何不同）1） 預防死鎖。這是一種簡單和直觀的事先預防方法。該方法是通過設置某些限制條件，去破壞產生死鎖的四個必要條件（互斥條件，請求和保持條件，不可搶占條件，循環等待條件）中的一個或幾個來預防產生死鎖。預防死鎖是一種較易實現的方法，已被廣泛使用、2） 避免死鎖。同樣是屬于事先預防策略，但它并不是事先采取各種限制措施，去破壞產生死鎖的四個必要條件，而是

6、在資源的動態分配過程中，用某種方法防止系統進入不安全狀態，從而可以避免發生死鎖。3） 檢測死鎖。這種方法無須事先采取任何限制性措施，允許進程在運行過程中發生死鎖。但可通過檢測機構及時地檢測出死鎖的發生，然后采取適當的措施，把進程從死鎖中解脫出來。4） 解除死鎖。當檢測到系統中已發生死鎖時，就采取相應措施，將進程從死鎖狀態中解脫出來。常用的方法是撤銷一些進程，回收它們的資源，將它們分配給已處于阻塞狀態的進程，使其能繼續運行。上述的四種方法，從1）到4）對死鎖的防范程度逐漸減弱，但對應的是資源利用率的提高，以及進程因資源因素而阻塞的頻度下降（即并發程度提高）。14. 解除死鎖的方法常采用解除死鎖的

7、兩種方法是：1） 搶占資源。從一個或多個進程中搶占足夠數量的資源，分配給死鎖進程，以解除死鎖狀態。2） 終止（或撤銷）進程。終止（或撤銷）系統中的一個或多個死鎖進程，直至打破循環環路，使系統從死鎖狀態解脫出來。15. 死鎖產生的必要條件1） 互斥條件2） 請求和保持條件3） 不可搶占條件4） 循環等待條件16. 死鎖的概念如果一組進程中的每一個進程都在等待僅由該組進程中的其它進程才能引發的事件，那么該組進程是死鎖的。17. 銀行家算法銀行家算法是一種最有代表性的避免死鎖的算法。要解釋銀行家算法，必須先解釋操作系統安全狀態和不安全狀態。安全狀態：如果存在一個由系統中所有進程構成的安全序列P1，P

8、n，則系統處于安全狀態。安全狀態一定是沒有死鎖發生。不安全狀態:不存在一個安全序列。不安全狀態不一定導致死鎖。安全序列一個進程序列P1，Pn是安全的，如果對于每一個進程Pi(1in），它以后尚需要的資源量不超過系統當前剩余資源量與所有進程Pj (j < i )當前占有資源量之和。18. 進程調度的功能1) 記錄系統中所有進程的執行情況作為進程調度的準備，進程管理模塊必須將系統中各進程的執行情況和狀態特征記錄在各進程的PCB表中。并且，根據各進程的狀態特征和資源需求等、進程管理模塊還將各進程的PCB表排成相應的隊列并進行動態隊列轉接。進程調度模塊通過PCB變化來掌握系統中存在的所有進程的執

9、行情況和狀態特征，并在適當的時機從就緒隊列中選擇出一個進程占據處理機。2) 選擇占有處理機的進程進程調度的主要功能是按照一定的策略選擇個處于就緒狀態的進程，使其獲得處理機執行。根據不同的系統設計目的，有各種各樣的選擇策略，例如系統開銷較少的靜態優先數調度法，適合于分時系統的輪轉法(Round RoLin)和多級互饋輪轉法(Round Robin with Multip1e feedback)等。這些選擇策略決定了調度算法的性能。3) 進行進程上下文切換個進程的上下文(context)包括進程的狀態、有關變量和數據結構的值、機器寄存器的值和PCB以及有關程序、數據等。一個進程的執行是在進程的上下

10、文中執行。當正在執行的進程由于某種原因要讓出處理機時，系統要做進程上下文切換，以使另一個進程得以執行。當進行上下文切換時點統要首先檢查是否允許做上下文切換(在有些情況下，上下文切換是不允許的，例如系統正在執行某個不允許中斷的原語時)。然后，系統要保留有關被切換進程的足夠信息，以便以后切換回該進程時，順利恢復該進程的執行。在系統保留了CPU現場之后，調度程序選擇一個新的處于就緒狀態的進程、并裝配該進程的上下文，使CPU的控制權掌握在被選中進程手中。19. 作業調度算法（FCFS和短作業優先）先來先服務（FCFS）調度算法FCFS是最簡單的調度算法，該算法既可用于作業調度，也可用于進程調度。當在作

11、業調度中采用該算法時，系統將按照作業到達的先后次序來進行調度，或者說它是優先考慮在系統中等待時間最長的作業，而不管該作業所需執行時間的長短從后備作業隊列中選擇幾個最先進入該隊列的作業，將它們調入內存，為它們分配資源和創建進程。然后把它們放入就緒隊列。當在進程調度中采用FCFS算法時，每次調度是從就緒的進程隊列中選擇一個最先進入該隊列的進程，為之分配處理機，使之投入運行。該進程一直運行到完成或發生某事件而阻塞后，進程調度程序才將處理機分配給其它進程。優點：1） 簡單可靠2） 容易理解，實現方便3） 非搶占式的缺點：1） 有利于長的作業和進程，不利于短的2） 有利于CPU繁忙型的作業或進程，不利于

12、I/O繁忙型的短作業優先（SJF）的調度算法SJF算法是以作業的長短來計算優先級，作業越短，其優先級越高。作業的長短是以作業所要求的運行時間來衡量的。SJF算法可以分別用于作業調度和進程調度。班在短作業優先調度算法用于作業調度時，它將從外存的作業后備隊列中選擇若干個估計運行時間最短的作業，優先將它們調入內存運行。缺點：1） 必須預知作業的運行時間2） 對長作業非常不利，長作業的周轉時間會明顯地增長3） 在采用SJF算法時，人-機無法實現交互4） 該調度算法完全未考慮作業的緊迫程度，故不能保證緊迫性作業能得到及時處理20. 存儲管理的對象存儲管理的對象是主存儲器(簡稱內存或主存) 。分

13、區管理的分配算法基于順序搜索的的動態分配算法：1首次適應算法 2循環首次適應算法 3最佳適應算法 4最壞適應算法基于索引搜索的動態分配算法1快速適應算法 2伙伴系統 3哈希算法21. 分頁存儲管理的基本思想和頁表的作用將用戶程序的地址空間分為若干個固定大小的區域，稱為“頁”或“頁面”。典型的頁面大小為1KB。相應的，也將內存空間分為若干個物理塊或頁框，頁和塊的大小相同。這樣可將用戶的程序的任一頁放入任一物理塊中，實現了離散分配。頁表的作用：能在內存中找到每一個頁面所對應的物理塊。22. 段式存儲的基本思想把用戶程序的地址空間分為若干個大小不同的段，每段可定義一組相對完整的信息。在存儲器分配時，

14、以段為單位，這些段在內存中可以不相鄰接，所以也同樣實現了離散分配。23. 分頁與分段的區別分頁和分段系統有許多相似之處，但在概念上兩者完全不同，主要表現在： 1、頁是信息的物理單位，分頁是為實現離散分配方式，以消減內存的外零頭，提高內存的利用率；或者說，分頁僅僅是由于系統管理的需要，而不是用戶的需要。 段是信息的邏輯單位，它含有一組其意義相對完整的信息。分段的目的是為了能更好的滿足用戶的需要。 2、頁的大小固定且由系統確定，把邏輯地址劃分為頁號和頁內地址兩部分，是由機器硬件實現的，因而一個系統只能有一種大小的頁面。 段的長度卻不固定，決定于用戶所編寫的程序，通常由編輯程序在對源程序進行編輯時，

15、根據信息的性質來劃分。 3、分頁的作業地址空間是維一的，即單一的線性空間，程序員只須利用一個記憶符，即可表示一地址。 分段的作業地址空間是二維的，程序員在標識一個地址時，既需給出段名，又需給出段內地址。24. 頁面置換的算法，FIFO,LRUFIFO：LRU：25. 輸入輸出四種控制方式1） 程序直接控制方式2） 中斷驅動方式3） DMA（直接存儲器存取）方式4） 通道控制方式26. 輸入輸出I/O重定向的概念I/O重定向是一個過程，這個過程捕捉一個文件、或命令、或程序、或腳本、甚至代碼塊（code block）的輸出，然后把捕捉到的輸出，作為輸入發送給另外一個文件、或命令、或程序、或腳本。I

16、/O重定向最常用的方法是管道（管道符"|"）。27. 設備獨立性設備獨立性，即應用程序獨立于具體使用的物理設備。為了實現設備獨立性而引入了邏輯設備和物理設備這兩個概念。在應用程序中， 使用邏輯設備名稱來請求使用某類設備;而系統在實際執行時， 還必須使用物理設備名稱。因此，系統須具有將邏輯設備名稱轉換為某物理設備名稱的功能，這非常類似于存儲器管理中所介紹的邏輯地址和物理地址的概念。28. 中斷的定義中斷是指CPU對I/O發來的中斷信號的一中響應。CPU暫停正在執行的程序，保留CPU環境后，自動地轉去執行該I/O設備的中斷處理程序。執行完后，在回到斷點，繼續執行原來的程序。I/

17、O設備可以是字符設備，也可以是塊設備，通信設備等。由于中斷是由外部設備引起的，故又稱為外中斷。29. 中斷處理程序的處理過程1） 測定是否有未響應的中斷信號2） 保護被中斷進程的CPU環境3） 轉入相應的設備處理程序4） 中斷處理5） 恢復CPU的現場并退出中斷30. 假脫機（Spooling）系統的作用1)提高了I/O速度.從對低速I/O設備進行的I/O操作變為對輸入井或輸出井的操作,如同脫機操作一樣,提高了I/O速度,緩和了CPU與低速I/O設備速度不匹配的矛盾.2)設備并沒有分配給任何進程.在輸入井或輸出井中,分配給進程的是一存儲區和建立一張I/O請求表.3)實現了虛擬設備功能.多個進程

18、同時使用一獨享設備,而對每一進程而言,都認為自己獨占這一設備,不過,該設備是邏輯上的設備.31. 磁盤調度的算法早期的磁盤調度算法1） 先來先服務（FCFS）2） 最短尋道時間優先（SSTF）基于掃描的磁盤調度算法1） 掃描（SCAN）算法2） 循環掃描（CSCAN）算法3） NStepSCAN和FSCAN調度算法 32. 文件邏輯結構，物理結構的定義1） 文件的邏輯結構。這是從用戶觀點出發所觀察到的文件組織形式，即文件是由一系列的邏輯記錄組成的，是用戶可以直接處理的數據及其結構，它獨立于文件的物理特性，又稱為文件組織。2） 文件的物理結構，又稱為文件的存儲結構。這是指系統將文件存儲在外存上所

19、形成的一種存儲組織形式，是用戶不能看見的。文件的物理結構不僅與存儲介質的存儲性能有關，而且與所采用的外存分配方式有關。無論是文件的邏輯結構，還是其物理結構，都會影響對文件的檢索速度。33. 目錄文件存放的信息該目錄中所有子目錄文件和數據文件的目錄34. 文件多級目錄結構的特點多級（樹形）目錄結構的優點是便于文件分類，可為每類文件建立一個子目錄；查找速度快，因為每個目錄下的文件數目較少；可以實現文件共享；缺點是比較復雜。 35. 保護域的定義為了對系統中的資源進行保護而引入了保護域的概念，保護域簡稱“域”。“域”是進程對一組對象訪問權的集合，進程只能在制定域內執行操作。這樣，“域”也就規定了進程

20、所能訪問的對象和能執行的操作。36. 訪問權的定義為了對系統中的對象加以保護，應由系統來控制進程對對象的訪問。對象可以是硬件對象，如磁盤驅動器，打印機；也可以是軟件對象，如文件，程序。對對象所施加的操作也有所不同，如對文件可以是讀，也可以是寫或執行操作。我們把一個進程能對某對象執行操作的權力，稱為訪問權。每個訪問權可以用一個有序對（對象名，權集）來表示。例如，某進程有對文件F1執行讀和寫操作的權力，則可將該進程的訪問權表示成（F1，R/W）。37. 位示圖進行盤塊，回收的過程位示圖是利用二進制的一位來表示磁盤中的一個盤塊的使用情況。當其值為"0"時，表示對應的盤塊空閑;為&

21、quot;1"時，表示已經分配。有的系統把"0"作為盤塊已分配的標記，把"1"作為空閑標志。(它們的本質上是相同的，都是用一位的兩種狀態標志空閑和已分配兩種情況。)磁盤上的所有盤塊都有一個二進制位與之對應，這樣，由所有盤塊所對應的位構成一個集合，稱為位示圖。通常可用m*n個位數來構成位示圖，并使m*n等于磁盤的總塊數。位示圖也可描述為一個二維數組mapm,n。盤塊的分配根據位示圖進行盤塊分配時，可分三步進行：1） 順序掃描位示圖，從中找出一個或一組其值為“0”的二進制位（“0”表示空閑時）。2） 將所找到的一個或一組二進制位轉換為與之對應的盤塊

22、號。假定找到的其值為“0”的二進制位位于位示圖的第i行，第j列，則其相應的盤塊號應按下式計算：b=n(i-1)+j，式中，n代表每行的位數。3） 修改位示圖，令mapI,j=1。盤塊的回收1） 將回收盤塊的盤塊號轉換為位示圖中的行號和列號。轉換公式為：I=(b-1)DIV n+1J=(b-1)MOD n+12） 修改位示圖。令mapI,j=0.。38. CPU指令的分類常見的特權指令有以下幾種:（1）有關對I/O設備使用的指令 如啟動I/O設備指令、測試I/O設備工作狀態和控制I/O設備動作的指令等。（2）有關訪問程序狀態的指令 如對程序狀態字（PSW）的指令等。（3）存取特殊寄存器指令 如存

23、取中斷寄存器、時鐘寄存器等指令。（4）其他指令39. CPU運行狀態的分類40. 網絡操作系統的互操作功能為了了實現多個網絡之間的通信和資源共享，不僅需要將他們從物理上連接在一起，而且還應使不同網絡的計算機系統之間能進行通信（信息互通）和實現資源共享（信息互用）。為此網絡OS中必須提供應用互操作功能，以實現“信息互通性”及“信息互用性”。（1） 信息互通性。為了避免在不同網絡中，因采用了不同的協議而不能識別和通信，在互連網絡的每一個網絡中都應配置同一類型的傳輸協議，以實現各個網絡之間的通信。（2） 信息的互用性。所謂信息的互用性，是指在不同的網絡中的站點之間能實現信息的互用，亦即一個網絡中的用

24、戶能夠訪問另一個網絡文件系統（或數據庫系統）中的文件（數據）。不能實現信息的互用性的原因是在不同網絡中所配置的網絡文件系統（或數據庫系統），通常使用了各不相同的結構、各不相同的文件命名方式和存取文件的命令，于是便發生了有一個源網絡中的用戶發往一個目標網絡的文件訪問命令不能被目標網絡的節點所識別的情況。對此，一個當前相對比較流行的解決方案是由SUN公司推出的網絡文件系統協議NFS41. 網絡協議的三要素1） 語義2） 語法3） 時序42. 加密算法的分類對稱加密算法非對稱加密算法43. 身份認證的依據當前身份驗證主要依據下述三個方面的信息來確認：1) 所知，即基于用戶所知道的信息，如系統的登錄名

25、，口令等。2) 所有，指用戶所具有的東西，如身份證，信用卡等。3) 用戶特征，指用戶所具有的特征，特別是生理特征，如指紋，聲紋，DN等。1. 某雜技團進行走鋼絲表演。在鋼絲的A、B兩端各有n名演員（n>1）在等待表演。只要鋼絲上無人時便允許一名演員從鋼絲的一端走到另一端。現要求兩端的演員交替地走鋼絲，且從A端的一名演員先開始。請問，把一名演員看作一個進程時，怎樣用WAIT,SIGNAL操作來進行控制？請寫出能進行正確管理的程序。2. 有閱覽室，讀者進入時必須先在一張登記表中進行登記，該表為每一座位列一表目，包括座號和讀者姓名，讀者離開時要消掉登記信息，閱覽室中共有100個座位，試問：試用

26、信號量和wait，signal原語寫出這些進程間的同步算法。3. 請用信號量解決以下的“過獨木橋”問題：同一方向的行人可連續過橋，當某一方向有人過橋時，另一方向的行人必須等待；當某一方向無人過橋時，另一方向的行人可以過橋。4. 假定系統有三個并發進程read, move和print共享緩沖器B1和B2。進程read負責從輸入設備上讀信息，每讀出一個記錄后把它存放到緩沖器B1中。進程move從緩沖器B1中取出一記錄，加工后存入緩沖器B2。進程print將B2中的記錄取出打印輸出。緩沖器B1和B2每次只能存放一個記錄。要求三個進程協調完成任務，使打印出來的與讀入的記錄的個數，次序完全一樣。請用WA

27、IT()和SIGNAL()原語操作，寫出它們的并發程序。1、某虛擬存儲器的用戶編程空間共32個頁面，每頁為1KB，內存為16KB。假定某時刻一用戶頁表中已調入內存的頁面的頁號和物理塊號的對照表如下：頁號 物理塊號0 51 102 43 7則邏輯地址0A5C（H）所對應的物理地址是什么？解：程序空間的大小為32KB，因此邏輯地址的有效位數是15位。內存儲空間的大小是16KB，因此物理地址至少需要14位。2、某段表內容如下：段號 段首地址 段長度0 120K 40K1 760K 30K2 480K 20K3 370K 20K一邏輯地址為（2，154）的實際物理地址為多少？答：邏輯地址（2,154）

28、表示段號為2，即段手地址為480K，154為單元號，則實際物理地址為480K+154。3、考慮下述頁面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6當內存塊數量分別為3時，試問FIFO、LRU、OPT這三種置換算法的缺頁次數各是多少？答：缺頁定義為所有內存塊最初都是空的，所以第一次用到的頁面都產生一次缺頁。當內存塊數量為3時：發生缺頁中斷的次數為16。在FIFO算法中，先進入內存的頁面被先換出。當頁6要調入時，內存的狀態為4、1、5，考查頁6之前調入的頁面，分別為5、1、2、4，可見4為最先進入內存的，本次應換出，然后把頁6調入內存。發生缺頁中斷的次數為15。在LRU算法中，最近最少使用的頁面被先換出。當頁6要調入時，內存的狀態為5、2、1，考查頁6之前調入的頁面，分別為5、1、2，可見2為最近一段時間內使用最少的，本次應換出，然后把頁6調入內存。發生缺頁中斷的次數為11。在OPT算法中，在最遠的將來才被訪問的頁面被先換出。當頁6要調入時，內存的狀態為1、2、5，考查頁6后面要調入的頁面，分別為2、1、2、，可見5為最近一段時間內使用最少的，本次應換出，然后把頁6調入內存。OPT算法因為要知道后面請求的頁框，因此我覺得這個算法有