1、第一章 1.操作系統的概念 ：通常把操作系統定義為用以控制和管理計算機系統資源方便用戶使用的程序和數據結構的集合。 2.操作系統的基本類型 ：批處理操作系統、分時操作系統、實時操作系統、個人計算機操作系統、網絡操作系統、分布式操作系統。批處理操作系統特點：用戶脫機使用計算機成批處理多道程序運行優點：由于系統資源為多個作業所共享，其工作方式是作業之間自動調度執行。并在運行過程中用戶不干預自己的作業，從而大大提高了系統資源的利用率和作業吞吐量。缺點：無交互性，用戶一旦提交作業就失去了對其運行的控制能力；而且是批處理的，作業周轉時間長，用戶使用不方便。批處理系統中作業處理及狀態分時操作系統(Time

2、 Sharing OS)分時操作系統是一個聯機的多用戶交互式的操作系統，如UNIX 是多用戶分時操作系統。分時計算機系統：由于中斷技術的使用，使得一臺計算機能連接多個用戶終端，用戶可通過各自的終端使用和控制計算機，我們把一臺計算機連接多個終端的計算機系統稱為分時計算機系統，或稱分時系統。分時技術：把處理機的響應時間分成若于個大小相等（或不相等）的時間單位，稱為時間片（如100 毫秒），每個終端用戶獲得等于獲得一個時間片，該用戶程序開始運行，當時間片到（用完），用戶程序暫停運行，等待下一次運行。特點：人機交互性好：在調試和運行程序時由用戶自己操作。共享主機：多個用戶同時使用。用戶獨立性：對每個用

3、戶而言好象獨占主機。實時操作系統(real-time OS)實時操作系統是一種聯機的操作系統，對外部的請求，實時操作系統能夠在規定的時間內處理完畢。特點：有限等待時間有限響應時間用戶控制可靠性高系統出錯處理能力強設計實時操作系統要考慮的一些因素：（1）實時時鐘管理（2）連續的人 機對話（3）過載CPU，就(4) 高度可靠性和安全性需要采取冗余措施。通用操作系統同時兼有多道批處理、分時、實時處理的功能，或其中兩種以上的功能。個人計算機上的操作系統個人計算機上的操作系統是聯機的交互式單用戶操作系統，目前在個人計算機上使用的操作系統以windows系列和linux系統為主。網絡操作系統特征：（ 1）

4、計算機網絡是一個互連的計算機系統群體。這些計算機在物理上是分散的。（ 2）這些計算機是自治的，每臺計算機有自己的操作系統，各自獨立工作，它們在網絡協議控制下協同工作。（ 3）系統互連要通過通信設施（硬件、軟件）來實現。（ 4）系統通過通信設施執行信息交換、資源共享、互操作和協作處理。分布式系統 (Distributed System)特征：（ 1）功能的分布（ 2）堅強性（ 3）高可靠性3 操作系統的功能處理機管理、存儲管理（內存分配、存儲保護、內存擴充）、設備管理（通道、控制器、輸入輸出設備的分配與管理，設備獨立性）、信息管理（文件系統管理） 、用戶接口（程序一級的接口、作業一級的接口）。4

5、.通道和中斷技術通道：用于控制I/O 設備與內存間的數據傳輸。啟動后可獨立于CPU 運行，實現CPU 與 I/O 的并行。通道有專用的I/O 處理器，可與CPU 并行工作可實現I/O 聯機處理中斷是指 CPU 在收到外部中斷信號后，停止原來工作，轉去處理該中斷事件，完畢后回到原來斷點繼續工作。中斷處理過程：中斷請求，中斷響應，中斷點（暫停當前任務并保存現場），中斷處理例程，中斷返回（恢復中斷點的現場并繼續原有任務監督程序發展為執行系統(executive system)，常駐內存 5.多道批處理系統特點多道：內存中同時存放幾個作業；宏觀上并行運行：都處于運行狀態，但都未運行完；微觀上串行運行：

6、各作業交替使用CPU；優點：資源利用率高：CPU 和內存利用率較高；作業吞吐量大：單位時間內完成的工作總量大；缺點：用戶交互性差：整個作業完成后或中間出錯時，才與用戶交互，不利于調試和修改；作業平均周轉時間長：短作業的周轉時間顯著增長；多道程序系統中，要解決的問題：同步互斥、內存不夠、使用效率、內存保護6.計算機硬件：構成計算機的基本硬件元素：處理器、存儲器、輸入輸出控制與總線、外部設備。與操作系統相關的幾種主要的寄存器數據寄存器地址寄存器條件碼寄存器程序計數器指令計數器程序狀態字PSW中斷現場保護寄存器過程調用用堆棧存儲器的訪問速度指令的執行和中斷操作系統的啟動啟動電源 產生中斷信號 觸發

7、CPU 中的一段指令發現操作系統引導區位置 導入內存執行 操作系統程序加載到內存制定區域 初始化硬件 7.算法begin .end 算法的開始于結束repeat操作 .until條件while 條件do操作 .odif 條件then操作else 操作當“條件”未被滿足時重復所描述的“操作”當“條件”滿足時，進行相應的“操作”fi滿足“ if ”所指的“條件”時，進行“then”后的相關“操作” ，否則完成“else”后的相關操作。第二章 1.作業：在一次應用業務處理過程中，從輸入開始到輸出結束，用戶要求計算機所做的有關該次業務處理的全部工作稱為一個作業。作業由不同的順序相連的作業步組成，作業步

8、是一個作業的處理過程中計算機所做的相對獨立的工作。2.作業的組織：作業由三部分組成，即程序、數據和作業說明書。作業中包含的程序和數據完成用戶所要求的業務處理工作，作業說明書則體現用戶的控制意圖。由作業說明書在系統中生成一個稱為作業控制塊（JCB）的表格， JCB 包括：作業名、估計執行時間、優先數（用于調度）、作業說明書文件名、程序類型、資源要求(靜態申請和動態申請)、作業狀態（提交后各執行完成）。作業說明書包括：作業基本情況描述（用戶名、作業名、使用語言名、允許最大處理時間等）、作業控制描述（控制方式、操作順序、出錯處理等）、作業資源要求描述（要求處理時間、內存空間、外設類型和數量、處理及優

9、先級、庫函數或實用程序等）。 3.如何控制作業聯機輸入輸出方式聯機輸入輸出方式大多用在交互式系統中，用戶與系統通過交互式會話輸入輸出作業。在聯機輸入輸出方式中，外圍設備直接與主機相連接。脫機輸入輸出方式脫機輸入又稱為預輸入方式，利用低檔個人計算機作為外圍處理機進行輸入輸出處理。直接耦合方式把主機與低檔外圍通過一個公用的大容量外存直接耦合起來。 SPOOLING 系統（外圍設備同時聯機操作）多臺外圍設備通過通道或 DMA 器件和主機與外存連接起來。網絡聯機方式網絡聯機方式以上述幾種輸入輸出方式為基礎。當用戶通過計算機網絡中的某一臺設備對計算機網絡中的另一臺主機進行輸入輸出操作時，就構成了網絡聯機

10、方式。4.系統調用系統調用大致可分為6 類：（ 1）設備管理：該類系統調用被用來請求和釋放有關設備以及啟動設備操作等。（ 2）文件管理：包括對文件的讀、寫、創建和刪除等。（ 3）進程控制：包括進程創建、進程執行、進程撤銷、進程等待和執行優先級控制等。（ 4）進程通信：該系統調用被用在進程之間傳遞消息或符號。（ 5）存儲管理：包括調查作業占據內存區的大小、獲取作業占據內存區的始址等。（ 6）線程管理：包括線程的創建、調度、執行、撤銷等。系統調用的實現：當用戶使用系統調用時，產生一條相應的指令，處理機在執行到該指令時發生相應的中斷，并發出有關信號給該處理機制。該處理機制在收到了處理機發來的信號后，

11、啟動相關的處理程序去完成該系統調用所要求的功能。陷進處理機構：在系統中為控制系統調用服務的機構稱為陷進處理機構。陷進指令：把由于系統調用引起處理機中斷的指令稱為陷進指令。第三章1. 程序的并發執行程序用來描述計算機所完成的獨立功能，并在時間上嚴格地按前后次序相繼地進行計算機操作序列集合，是一個靜態概念。個程序由若干個程序段組成，而這些程序段的執行必須是順序的，這種程序執行的方式就稱為程序的順序執行。程序順序執行的特點：1. 順序性處理機嚴格按照程序所規定的順序執行，即每個操作必須在下一個操作開始之前結束。2. 封閉性程序一旦開始執行，其計算結果不受外界的影響，當程序的初始條件給定之后，其后的狀

12、態只能由程序本身確定，即只有本程序才能改變它。3. 可再現性程序執行的結果與初始條件有關，而與執行時間無關。即只要程序的初始條件相同，它的執行結果是相同的，不論它在什么時間執行，也不管計算機的運行速度。多道程序系統中程序執行環境的變化執行環境的特點：（ 1）獨立性在多道環境下執行的每道程序都是邏輯上獨立的。（ 2）隨機性程序和數據的輸入和執行開始時間都是隨機的。（ 3）資源共享軟硬件資源的有限性導致資源共享。程序并發執行：若干個程序段同時在系統中運行，這些程序的執行在時間上是重迭的，一個程序段的執行尚未結束，另一個程序段的執行已經開始，即使這種重迭是很小的，也稱這幾個程序段是并發執行的。2.

13、.進程：進程是一個程序對某個數據集的執行過程，是分配資源的基本單位。進程和程序的區別與聯系：程序是指令的集合，是靜態的概念。 進程是程序在處理機上的一次執行的過程，是動態的概念。程序可以作為軟件資料長期保存。進程是有生命周期的。進程是一個獨立的運行單位，能與其它進程并行（并發）活動。而程序則不是。進程是競爭計算機系統有限資源的基本單位，也是進行處理機調度的基本單位。不同的進程可以包含同一程序，只要該程序所對應的數據集不同。作業和進程的關系作業是用戶需要計算機完成某項任務時要求計算機所做工作的集合。而進程則是已提交完畢程序的執行過程的描述，是資源分配的基本單位。其主要區別如下：作業是用戶向計算機

14、提交任務的任務實體。一個作業可由多個進程組成。作業的概念主要用于批處理系統中。進程描述在系統中一個進程存在：進程控制塊PCB、有關程序段、數據結構集進程控制塊PCB (Process Control Block)包含一個進程的描述信息、控制信息及資源信息，有些系統還有進程調度等待所使用的現場保護區。PCB 集中反映一個進程的動態特征。在創建時，建立PCB，并伴隨進程運行的全過程，當進程完成其功能后，系統釋放PCB，進程也隨之消亡（1）描述信息1、進程名或進程標識號name每個進程都必須有一個唯一的標識符，可以是字符串，也可以是一個數字。UNIX系統中就是一個整型數。在進程創建時由系統賦予。2、

15、用戶名或用戶標識號每個進程都隸屬于某個用戶，用戶名或用戶標識號有利于資源共享和保護3、家族關系process family有的系統允許一個進程可創建自已的子進程，子進程還可以創建，一個進程往往處在一個家族之中，就需要記錄進程在家族中位置的信息。（2）控制信息1、進程當前狀態status說明進程當前所處的狀態。為了管理的方便，系統設計時會將相同的狀態的進程組成一個隊列，如就緒進程隊列，等待進程則要根據等待的事件組成多個等待隊列，如等待打印機隊列、等待磁盤 I/O 完成隊列等等。2、進程優先級priority進程的優先級反映進程的緊迫程度，通常由用戶指定和系統設置。3、執行程序開始地址start-

16、addr4、各種計時信息進程占用系統資源的情況，不同的系統的處理差別很大。5、通信信息communication information是指某個進程在運行的過程中要與其它進程進行通信，該區記錄有關進程通信方面的信息。（ 3）資源管理信息包括有關存儲器的信息、使用輸入、輸出設備的信息、有關文件系統的信息：1、占用內存大小及管理用數據結構指針。2、在某些復雜系統中，還有對換或覆蓋用的有關信息。3、共享程序段大小及起始地址。4、輸入輸出設備的設備號，所要傳送的數據長度、緩沖區地址、緩沖區長度及使用設備的有關數據結構指針等。5、指向文件系統的指針及有關標識等。（ 4）、CPU 現場保護區 cpusta

17、tus當進程因某種原因不能繼續占用 CPU 時（等待打印機） ，釋放 CPU ，這時就要將 CPU 的各種狀態信息保護起來，為將來再次得到處理機恢復 CPU 的各種狀態，繼續運行。進程上下文實際上是進程執行活動全過程的靜態描述。進程上下文是一個抽象的概念，它包含了每個進程執行過的、執行時的以及待執行的指令和數據，在指令寄存器、堆棧（存放個調用子程序的返回點和參數等） ，狀態字寄存器等中的內容。上文：已執行過的進程指令和數據在相關寄存器與堆棧中的內容。正文：正在執行的指令和數據在相關寄存器與堆棧中的內容。下文：待執行的指令和數據在相關寄存器與堆棧中的內容。進程上下文切換進程上下文切換發生在不同的

18、進程之間而不是同一個進程內。包含 3 個部分，第一部分為保存被切換進程的正文部分（或當前狀態）至有關存儲區。第二部分操作系統進程中有關調度和資源分配程序執行，并選取新的進程。第三部分則是將被選中進程的原來被保存的正文部分從有關存儲區中選出，并送至有關寄存器或堆棧中，激活被選中進程執行。進程空間和大小任一進程都有自己的地址空間，把該空間稱為進程空間或虛空間。進程空間的大小只與處理機的位數有關。程序的執行都在進程空間內進行。用戶程序、進程的各種控制表格等都按一定的結構排列在進程空間中。在有的系統中進程空間被劃分為兩部分：用戶空間和系統空間。為了防止用戶程序訪問系統空間，造成訪問出錯，計算機通過程序

19、狀態寄存器等設置不同的執行模式，即用戶模式（用戶態）和系統模式（系統態）來進行保護。3.進程狀態及其轉換進程的 三種基本狀態：執行狀態、就緒狀態、等待狀態（又稱阻塞、掛起、睡眠）就緒狀態（ Ready)存在于處理機調度隊列中的那些進程，它們已經準備就緒，一旦得到 CPU，就立即可以運行，這些進程所取的狀態為就緒狀態。 （有多個進程處于此狀態）執行狀態 (Running ）當進程由調度 / 分派程序分派后，得到CPU 控制權，它的程序正在運行，該進程所處的狀態為執行狀態。（在系統中，總只有一個進程處于此狀態）等待狀態（ Wait)若一個進程正在等待某個事件的發生（如等待I/O 的完成），而暫停執

20、行，這時，即使給它CPU 時間，它也無法執行，則稱該進程處于等待狀態。進程狀態轉換運行到等待等待某事件的發生（如等待I/O 完成）等待到就緒事件已經發生（如I/O 完成）運行到就緒時間片到（例如，兩節課時間到，下課）新建進程到就緒新創建的進程進入就緒狀態就緒到運行當處理機空閉時，由調度（分派）程序從就緒進程隊列中選擇一個進程占用CPU。進程控制：就是系統使用一些具有特定功能的程序段來創建、撤銷進程以及完成進程各狀態的轉換，從而達到多進程高效率并發執行和協調、實現資源共享的目的。原語：把系統態下執行的某些具有特定功能的程序段稱為原語。用于進程控制的原語有：創建原語、撤銷原語、阻塞原語、喚醒原語。

21、進程創建方式：由系統程序模塊統一創建；由父進程創建。進程創建系統調用：create(name,priority,start-addr)UNIX 系統： fork()進程撤銷：（ 1）該進程已完成所要求的功能而正常終止（2）由于某種錯誤導致非正常終止（3）祖先進程要求撤銷某個子進程。在一般操作系統中進程撤消的系統調用是：killUNIX 系統中是 exit()如果撤銷進程有自己的子進程，則撤銷原語先撤銷其子進程的PCB 結構并釋放子進程所釋放的資源后，再撤銷當前進程的PCB 結構和釋放其資源。進程的阻塞與喚醒當一個處在運行狀態的進程，因等待某個事件的發生（如等待打印機）而不能繼續運行時，將調用進

22、程掛起系統調用，把進程的狀態置為阻塞狀態，并調用進程調度程序（等于讓出處理機）。進程從運行狀態轉換成阻塞狀態是由進程掛起原語實現的，因此，調用進程掛起操作是在進程處于運行狀態下執行的。它的執行將引起等待某事件的隊列的改變 .一個正在運行的進程會因等待某事件（例如，等待打印機）的發生，由運行狀態轉換成阻塞狀態，當它等待的事件發生后，這個進程將由阻塞狀態轉換成就緒狀態。這種轉換由進程喚醒操作完成。喚醒一個進程有兩種方式：系統進程喚醒、事件發生進程喚醒。調用進程喚醒操作一般在中斷處理、進程通信等過程中。例如，打印機完成中斷處理程序，打印機的隊列，若不為空，則調用進程喚醒操作，喚醒一個（或多個）等待打

23、印機的進程。4.進程互斥在完成了打印完成的操作后，就去檢查等待產生互斥的原因：資源共享、進程合作臨界資源：一次僅允許一個進程使用的資源稱為臨界資源。臨界區：每個進程中訪問臨界資源的那段程序段稱為臨界區（臨界段）。間接制約： 由于共享某公有資源而引起的在臨界區內不允許并發進程交叉執行的現象稱為有共享公有資源而造成的對并發進程執行速度的間接制約，簡稱間接制約。互斥：在操作系統中，當某一進程正在訪問某臨界區時，就不允許其它進程進入，否則就會發生(后果 )無法估計的錯誤。我們把進程之間的這種相互制約的關系稱為互斥。進入臨界區的準則：(1)不能假設各并發進程的相對執行速度；（ 2）并發進程中的某個進程不

24、在臨界區時，它不能阻止其他進程進入臨界區；（ 3）并發進程中的若干個進程申請進入界區時，只能允許一個進程進入；(4)當有若干個進程欲進入臨界區時，應在有限的時間內使其進入。解決進程互斥的最簡單的辦法是加鎖。在系統中為每個臨界資源設置一個鎖位，1 表示資源可用，0 表示資源已被占用（不可用） 。這樣當一個進程使用某個臨界資源之前必須完成下列操作：1、考察鎖位的值；2、若原來的值是為“1”，將鎖位置為 “0”（占用該資源）；3、若原來值是為“0”，（該資源已被別人占用） ，則轉到1。當進程使用完資源后，將鎖位置為“1“，稱為開鎖操作。5.信號量與P、 V原語信號量 sem：是一個整數，在 sem

25、大于等于零時，代表可供并發資源使用的資源實體數，但進程數。 sem 代表資源的實體。在實際應用中應準確地說明 sem 的意義和初值。sem 小于零時則表示正在等待使用臨界區的P 操作：（ 1） sem 減 1；（ 2）若 sem 減 1 后仍大于等于 0，則進程繼續執行；（ 3）若結果小于 0，則該進程掛起。注：掛起該進程包括：保留調用進程CPU 現場；置 “等待 ”狀態；入等待隊列；轉進程調度；V 操作：（ 1） s 值加 1；（ 2）若相加結果大于 0，進程繼續執行；（ 3）否則，喚醒一個（或多個）等待該信號燈的進程，然后本進程繼續執行或轉進程調度。 P、V 原語實現互斥的原理當一個進程想

26、要進入臨界區時，它必須先執行P 原語操作以將信號量 sem 減 1。在一個進程完成對臨界資源的操作后，它必須執行V 原語操作以釋放它占用的臨界資源。由于信號量初始值為1，所以，任一進程在執行P 原語操作之后將 sem 的值變為 0，表示該進程可以進入臨界區。在該進程未執行V 原語操作之前如有另一進程想進入臨界區的話，它也應先執行P 原語操作，從而使 sem 的值變為 -1 ，因此，第二個進程將會被阻塞，直到第一個進程執行V 原語操作之后， sem 的值變為 0，從而可喚醒第二個進程進入就緒隊列，經調度后進入臨界區。在第二個進程執行完V 原語操作之后，如果沒有其它進程申請進入臨界區的話，則sem

27、 又恢復到初始值。用信號量實現兩并發進程Pa，Pb 互斥的描述如下：（1）設 sem 為互斥信號量，其取值范圍為（1，0， -1）。其中 sem=1 標志進程 Pa，Pb 都未進入類名為S 的臨界區， sem=0 表示進程Pa，Pb 已進入類名為S 的臨界區， sem=-1 表示進程 Pa，Pb 中，一個進程已進入臨界區，而另一進程等待進入臨界區。（2）描述Pa：P（sem）V(sem)： .Pb：P（sem）V(sem)： .6.進程同步同步：把異步環境下的一組并發進程，因直接制約而互相發送消息而進行互相合作、互相等待，使得各進程按一定的速度執行的過程稱為進程間的同步。用 wait（消息名）

28、表示進程等待合作進程發來的消息.功能：等待到消息名為true 的進程繼續執行。用 signal（消息名）表示向合作進程發送消息功能：發送消息名，并將其值置為true。利用過程 wait 和 singnal 描述計算進程Pc 和打印進程Pp 的同步關系（ 1） 設消息名 Bufempty 表示 buf 為空，消息名 Buffull 表示 Buf 中裝滿了數據。（2）（3）初始化 Bufempty=true ， Buffull=false. 。描述：Pc：A： wait(Bufempty)計算Buf計算結果Bufemptyfalsesignal(Buffull)GotoAPp：B ： wait(B

29、ufful)打印 Buf 中的數據清除 Buf 中的數據Buffulfalsesignal(Bufempty)GotoB私有信號量（ private Semaphore）：進程同步的信號量只與制約進程及被制約進程有關而不是與整組并發進程有關。因此該信號量稱為私有信號量。用 P,V 原語操作實現同步首先，為各并發進程設置私有信號量，然后，為私有信號量賦初值，最后，利用P， V 原語和私有信號量規定各進程的執行順序。例：設進程 Pa 和 Pb 通過緩沖區隊列傳遞數據。 Pa 為發送進程， Pb 為接收進程。 Pa 發送數據時調用發送過程 deposit(data)，Pb 接受數據時調用過程 rem

30、ove(data)，且數據的發送和接受過程滿足如下條件：（1）在 7.生產者與消費者問題對于生產者進程：產生一個數據，當要送入緩沖區時，要檢查緩沖區是否已滿，若未滿，則可將數據送入緩沖區，并通知消費者進程；否則，等待；對于消費者進程：當它去取數據時，要看緩沖區中是否有數據可取，若有則取走一個數據，并通知生產者進程，否則，等待。這種相互等待，并互通信息就是典型的進程同步。同時，緩沖區是個臨界資源，因此，諸進程對緩沖區的操作程序是一個共享臨界區，因此，還有個互斥的問題。8.進程通信通信（ communication ）意味著進程間傳遞數據。操作系統可以看作是各種進程組成的，這些進程都具有各自獨立的

31、功能，且大多數都被外部需要而啟動執行。在單機系統中進程的通信有4 種形式：（ 1）主從式（ 2）會話式（ 3）消息或郵箱機制（ 4）共享存儲區方式會話方式的特點：(1)使用進程在使用服務進程所提供的服務之前，必須得到服務進程的許可。(2)服務進程根據使用進程的要求提供服務，但對所提供服務的控制由服務進程自身完成。（ 3）使用進程和服務進程在進行通信時有固定連接關系。消息或郵箱機制的特點是：（ 1）只要存在空緩沖區或郵箱，發送進程就可以發送消息。（ 2）與會話系統不同，發送進程和接受進程之間無直接聯接關系。（ 3）發送進程和接受進程之間存在緩沖區或郵箱用來存放被傳送消息。郵箱通信就是由發送進程申

32、請建立一與接受進程聯接的郵箱。設置郵箱的最大好處是發送進程和接受進程之間沒有時間上的限制。共享存儲區方式不要求數據移動，兩個需要互相交換信息的進程通過共享數據區的操作達到互相通信的目的。9. 死鎖問題死鎖：指個并發進程彼此互相等待對方所擁有的資源，且這些并發進程在得到對方的資源之前不會釋放自己所擁有的資源。從而造成大家都想得到資源而又得不到資源，個并發進程不能繼續向前推進的狀態。死鎖的起因：根本原因在于系統提供的資源個數少于并發進程所要求的該類資源數。產生死鎖有四個必要條件：（ 1）互斥條件。并發進程所要求和占有的資源是不能同時被兩個以上進程使用或操作的，進程對他所需要的資源進行排他性控制。（

33、 2）不剝奪條件。進程所獲得的資源在未使用完畢之前，不能被其它進程強行剝奪，而只能由獲得該資源的進程自己釋放。（ 3）部分分配。進程每次申請它所需要的一部分資源，在等待新資源的同時，繼續占用已分配的資源。（ 4）環路等待條件。存在一種進程循環鏈，鏈中每一個進程已獲得的資源同時被下一個進程所請求。只要有一個條件不滿足，死鎖就可解除。預防死鎖1破壞 “請求與保持條件 ”每個進程在運行之前，必須預先提出自己所要使用的全部資源，調度程序在該進程所需要的資源末得到滿足之前，不讓它們投入運行，并且當資源一旦分配給某個進程之后，那么在該進程的整個運行期間相應資源一直被它占有，這就破壞了產生死鎖的部分分配條件

34、。2破壞環路條件對系統提供的每一項資源，由系統設計者將它們按類型進行線性排隊，并賦予不同的序號。3資源受控動態分配為了避免死鎖發生，操作系統必須根據預先掌握的關于資源用法的信息控制資源分配，使得共同進展路徑的下一步不致于進入危險區，即只要有產生死鎖的可能性，就避免把一種資源分配給一個進程。死鎖的檢測和恢復1資源剝奪法（ 1）還原算法。即恢復計算結果和狀態。（ 2）建立檢查點主要是用來恢復分配前的狀態。2撤消進程法按一定的順序中止進程序列，直至已釋放到有足夠的資源來完成剩下的資源為止。第四章1.一個作業從提交給計算機系統到執行結束退出系統，一般都要經歷提交、收容、執行和完成四個狀態。一個作業在其

35、處于從輸入設備進入外部存儲設備的過程成為提交狀態 。處于提交狀態的作業，因其信息尚未全部進入系統，所以不能被調用程序選取。收容狀態 也稱為后備狀態，輸入管理系統不斷地將作業輸入到外存中對應部分（或稱輸入井，即專門用來存放待處理作業信息的一組外存分區）。若一個作業的全部信息已全部被輸入進輸入井，那么，在它還未被調度去執行之前，該作業處于收容狀態。作業調度程序從后備作業中選取若干作業到內存投入運行。它為被選中作業建立進程并分配必要的資源，這時，這些被選中的作業處于執行狀態 。當作業運行完畢，但它所占用的資源尚未全部被系統收回時，該作業處于完成狀態 。一般來說，處理機調度可分為4 級：作業調度、交換

36、調度、進程調度、線程調度。作業調度： 又稱宏觀調度或高級調度，其主要任務是按一定的原則對外存輸入井上的大量后備作業進行選擇，給選出的作業分配內存、輸入輸出設備等必要的資源，并建立相應的根程序，以使該作業的進程獲得競爭處理機的權利，另外，當該作業執行完畢時，還負責回收系統資源。交換調度： 又稱中級調度，其主要任務是按照給定的原則和策略，將處于外存交換區中的就緒狀態或就緒等待狀態的進程調入內存，或把處于內存就緒狀態或內存等待狀態的進程交換到外存交換區。交換調度主要涉及內存的管理和擴充，一般將它歸在存儲管理之中。進程調度： 又稱微觀調度或低級調度，其主要任務是按照某種策略和方法選取一個處于就緒狀態的

37、進程占用處理機。只有在多道批處理系統中才有作業調度，而在分時和實時系統中一般只有進程調度、交換調度和線程調度。這是因為在分時和實時系統中，為了縮短響應時間或為了滿足用戶需求的截止時間，作業不是建立在外存中，而是直接建立在內存中。2.作業調度作業調度的功能：（1）記錄系統中各作業的狀況，包括執行階段的有關情況。通常，系統為每個作業建立一個作業控制表JCB 記錄這些有關信息。作業控制塊 JCB：在作業調度的過程中記錄作業各方面的信息。它隨作業的創建而產生，隨作業的撤消而被清除。（ 2）從后備隊列中選取一部分作業投入執行（ 3）為被選中的作業做好執行前的準備工作。（ 4）在作業執行結束時做好善后處理

38、工作。作業調度目標：（ 1） 對所有作業應該是公平合理的。（ 2） 應使設備有高的利用率。（ 3）每天執行盡可能多的作業（ 4） 有快的響應時間對于批處理系統，作業的平均周轉時間或平均帶權周轉時間，被作為衡量調度算法優劣的標準；對于分時系統和實時系統，外加平均響應時間作為衡量調度算法優劣的標準(1)周轉時間：作業 i 從提交時刻到完成時刻稱為作業的周轉時間。Ti=Tei-TsiTei 為作業 i 的完成時間， Tsi 為作業的提交時間一個作業的周轉時間說明了該作業在系統內停留的時間,包含兩部分：一是等待時間；二為執行時間Ti=Twi+TriTwi 主要是指作業i 由后備狀態到執行狀態的等待時間

39、，它不包括作業進入執行狀態后的等待時間。一批作業的平均周轉時間為：nT=1/nTii=1帶權周轉時間Wi=Ti/TriTi 作業周轉時間Tri 作業執行時間一批作業的平均帶權周轉時間為nW=1/n Wii=13進程調度進程調度的功能：用 PCB 塊記錄系統中所有進程的執行情況按照一定的調度算法，選擇一個處于就緒狀態的進程，給它分配處理機(這是最重要的功能)實施進行進程上下文的切換引起進程調度的原因：（1）正在執行的進程執行完畢。這時，如果不選擇新的就緒進程執行，將浪費處理機資源。（2）執行中進程自己調用阻塞原語將自己阻塞起來進入睡眠等待狀態。（3）執行中進程調用了P 原語操作，從而因資源不足而

40、被阻塞；或調用了V 原語激活了等待資源的進程隊列。（ 4） 執行中進程提出了 I/O 請求后被阻塞。（ 5） 在分時系統中時間片已經用完。（ 6） 在執行完系統調用，在系統程序返回用戶進程，可認為系統進程執行完畢，從而可調度選擇一新的用戶程序執行。以上都是 CPU 執行不可剝奪方式下做引起的進程調度的原因，在CPU 執行方式是可剝奪時，還有：（7）就緒隊列中的某進程的優先級變得高于當前執行進程的優先級，從而也將發生進程調度。可剝奪方式：即就緒隊列中一旦有優先級高于當前進程優先級的進程存在時，便立即發生進程調度，轉讓處理機。非剝奪方式（不可剝奪方式） ：即使在就緒隊列存在有優先級高于當前執行進程

41、時，當前進程仍將繼續占有處理機，直到該進程因自己調度調用原語操作或、等待 I/O 進入阻塞狀態或時間片用完時才重新發生調度讓出處理機。進程調度性能評價（ 1）進程調度性能是衡量操作系統性能的一個重要指標（ 2）在大多數情況下，利用測試或模擬系統響應時間的方法來評價進程調度的性能4.調度算法先來先服務 (FCFS) 算法將用戶作業和就緒進程按提交順序或變成就緒狀態的先后排成隊列，并按照先來先服務的方式進行調度處理。優點：在一般意義下是公平的，即每個作業或進程都按照它們在隊列中等待時間長短來決定它們是否優先享受服務。缺點：對于那些執行時間較短的作業或進程來說，如果它們在某些執行時間很長的作業或進程

42、之后到達，則它們等待很長時間。(時間片 )輪轉法 (RR)算法描述：就緒隊列按進程到達的時間來排列。處理機的時間被分為固定大小的時間片。調度程序總是選擇就緒隊列中的第一個進程。一個執行進程如果在用完一個時間片后還沒有完成其任務，它就自動釋放處理機回到就緒隊列的末尾重新排隊，等待下一次被調度。缺點：只能用來分配那些可搶占資源，而且這種算法只能用于進程調度，不能用于作業調度（作業調度包含了不可搶占資源）。時間片的選取非常重要，時間片長度的選擇會直接影響系統開銷和響應時間。如果時間片長度過短，則調度程序剝奪處理機的次數增多，這將使進程上下文交換次數也大大增加，加重了系統開銷。如果時間片長度選擇過長(

43、大 )，大到一個進程足以完成其全部運行工作所需的時間，那么時間片輪轉法就退化為先來先服務策略了。最佳的時間片量值應能使分時用戶得到好的響應時間。時間片的確定在輪轉法中，時間片長度q 根據系統對響應時間的要求R 和就緒隊列中所能容納的最大進程數Nmax 確定的。q=R/Nmax一種改進的方法就是每當一輪調度開始時，系統根據就緒隊列中當前的進程數計算一次 q，作為新一輪調度的時間片。多級反饋輪轉法 ( 進程調度 )（1）在時間片輪轉法中設置三個就緒隊列a.時間片完成就緒隊列b.等待結束就緒隊列c.新進程就緒隊列（2）每個隊列建立時按FCFS 排列，同一隊列中進程的優先級相同，不同隊列具有不同的優先

44、級優先級高的隊列中進程的時間片短，優先級低的隊列中進程的時間片長。（ 3）進程調度時，先調度高優先級就緒隊列中的進程，當高優先級就緒隊列為空時才調度優先級低的就緒隊列中的進程（ 4）一個進程在執行過程中要經歷不同的就緒隊列優先級法算法描述：按照某種原則給作業或進程確定一個優先級，進程的就緒隊列或作業的后備隊列按對象的優先級進行排列，高前低后。對象進入隊列是插入。當調度發生時，排列在最前面的進程或作業被調度。確定優先級的方法有兩類：動態法和靜態法靜態法是根據作業或進程的靜態特性，在作業或進程開始執行之前就確定它們的優先級，一旦開始執行后就不能改變。動態法：把作業或進程靜態性和動態性結合起來確定作

45、業或進程的優先級，隨著作業或進程的執行過程，優先級不斷變化。作業調度中靜態優先級確定原則：（1）由用戶自己根據作業的緊急程度輸入一個適當的優先級（2）由系統或操作員根據作業類型指定優先級。（3）系統根據作業要求資源情況確定優先級。進程調度靜態優先級確定原則：（1）按照進程的類型給與不同的優先級。（2）將作業的靜態優先級作為它所屬進程的優先級。由于在進程調度中靜態優先級確定方法的缺陷：系統效率低、調度性能不高，所以多采用動態的方法確定優先級。進程調度動態優先級確定原則：（ 1） 根據進程占有 CPU 時間的長短來決定。一個進程占有處理機時間越長，則在被阻塞后再次獲得調度的優先級越低，反之，獲得調

46、度的可能性越大（ 2） 根據就緒進程等待 CPU 的時間長短來決定。一個就緒進程在就緒隊列中等待的時間越長，則它獲得調度選中的優先級就越高。最短作業優先法 SJF(作業調度 )選擇那些估計需要執行時間最短的作業投入執行，為它們創建進程和分配資源。優點：可使得系統在同一時間內處理的作業個數最多，從而吞吐量也就大于其他調度方式。缺點：對于一個不斷有作業進入的批處理系統來說，最短作業優先法有可能使得那些長作業永遠得不到調度執行的機會。最高響應比優先法 (作業調度 )綜合平衡 FCFS 和 SJF，既考慮等待時間長的作業，也照顧執行時間短的作業。響應比： R=( 等待時間 W+ 執行時間 T)/ 執行

47、時間 T優點：長作業有機會獲得調度執行缺點：同一時間內處理的作業數少于最短作業優先法，吞吐量也小于最短作業優先法調度前計算響應比，系統開銷增加。算法評價FCFS 算法 ：作業到達率； ：服務器 (主機 )的服務率；只有當 時系統才是穩定的。n：系統中的平均作業個數；R：系統響應時間； ：/ ，是系統中存在作業的概率，1- 是系統中沒有作業的概率。n= /(1- )Little 結果： n= R；R=n/ FCFS 算法的評價：R=n/= /(1- )*1/ RR 算法q：時間片；k：每個進程平均需要的時間片數，即該進程到達等待隊列的次數；線性優先級法的調度性能1/：平均服務時間，則：1/=k

48、qRR 算法的評價：已使用過 k 次時間片的進程的響應時間是：R(k)= /( (1- )=1/(1- )=k q/(1- )FCFS 方式短作業駐留時間與長作業相同，對短作業不利。輪轉法所需服務時間短的顧客響應時間將會小于所需服務時間長的顧客響應時間。實時調度算法分類：靜態表格驅動類、靜態優先級驅動搶先式調度算法類、動態計劃調度算法類、盡力而為調度算法類。具有代表性的實時調度算法時限式調度法（靜態表格驅動類代表）：是一種以滿足用戶要求時限為調度原則的算法。算法描述：時限有兩種：處理開始時限和處理結束時限，在實際中可以使用任一種時限。頻率單調調度（靜態優先級驅動搶先式調度算法類代表）：是一種被

49、廣泛用于多周期性實時處理的調度算法。其基本原理是頻率低（周期越長）的任務優先級越低。第五章1.存儲器：能接收數據和保存數據、而且能根據命令提供這些數據的裝置。存儲器分成兩類：內存儲器（簡稱內存、主存、物理存儲器）外存儲器（簡稱外存、輔助存儲器）虛擬存儲器：為用戶提供一種不受物理存儲器結構和容量限制的存儲器的技術稱為虛擬存儲器，或稱虛擬存儲技術。虛擬存儲器需要大容量的外存儲器的支持，或稱物資基礎。程序地址：用戶編程序時所用的地址（或稱邏輯地址、虛地址），基本單位可與內存的基本單位相同，也可以不相同。程序地址空間 （邏輯地址空間、 虛地址空間） :用戶的程序地址的集合稱為邏輯地址空間，它的編址總是從 0開始的，可以是一維線