第一章

★I.操作系統的概念：通常把操作系統定義為用以控制和管理計算機系統資源方便用戶使用的程序和數據結構的集合。

★2.操作系統的基本類型：批處理操作系統、分時操作系統、實時操作系統、個人計算機操作系統、網絡操作系統、分布式操作系統。

①批處理操作系統

特點：

用戶脫機使用計算機

成批處理

多道程序運行

優點：

由于系統資源為多個作業所共享，其工作方式是作業之間自動調度執行。并在運行過程中用戶不干預自己的作業，從而大大提高了系統資

源的利用塞和作業吞吐量。

缺點：

無交互性，用戶一旦提交作業就失去了對其運行的控制能力；而且是批處理的，作業周轉時間長，用戶使用不方便。

②分時操作系統（TimeSharingOS）

分時操作系統是一個聯機的多用戶交互式的操作系統，如UNIX是多用戶分時操作系統。

分時計算機系統：由于中斷技術的使用，使得一臺計算機能連接多個用戶終端，用戶可通過各自的終端使用和控制1一算機，我們把一臺計

算機連接多個終端的計算機系統稱為分時計算機系統，或稱分時系統。

分時技術：把處理機的響應時間分成若丁個大小相等（或不相等）的時間單位，稱為時間片（如100亮秒），每個終端用戶獲得CPU,就

等于獲得一個時間片，該用戶程序開始運行，當時間片到（用完），用戶程序暫停運行，等待下一次運行。

特點：

人機交互性好：在調試和運行程序時由用戶自己操作。

共享主機：多個用戶同時使用。

用戶獨立性：對?每個用戶而言好象獨占主機。

③實時操作系統（real-timeOS）

實時操作系統是一種聯機的操作系統，對外部的請求，實時操作系統能夠在規定的時間內處理完畢。

特點：

有限等待時間

有限響應時間

用戶控制

可靠性高

系統出錯處理能力強

設計實時操作系統要考慮的?些因素：

（1）實時時鐘管理

（2）連續的人一機對話

（3）過載

（4）高度可靠件和安全件需要采取冗余措施.

④通用操作系統

同時兼有多道批處理、分時、實時處理的功能，或其中兩種以上的功能。

⑤個人計算機上的操作系統

個人計算機上的操作系統是聯機的交互式單用戶操作系統，目前在個人計算機上使用的操作系統以windows系列和linux系統為主。

⑥網絡操作系統

特征；

（1）計算機網絡是一個互連的計算機系統群體。這些計算機在物理上是分散的。

（2）這些計算機是自治的，每臺計算機有自己的操作系統，各自獨立工作，它們在網絡協議控制下協同工作。

（3）系統互連要通過通信設施（硬件、軟件】來實現。

（4）系統通過通信設施執行信息交換、資源共享、互操作和協作處理。

⑦分布式系統（DistributedSystem）

特征：

（1）功能的分布

（2）堅強性

（3）高可靠性

★3.操作系統的功能

處理機管理、存儲管理（內存分配、存儲保護、內存擴充）、設備管理（通道、控制器、輸入輸出設備的分配與管理，設備獨立性）、信息

管理（文件系統管理）、用戶接口（程序一級的接口、作業一級的接口）。

4.通道和中斷技術

通道：用于控制I/O設備與內存間的數據傳輸。啟動后可獨立于CPU運行，實現CPU與I/O的并行。

O通道有專用的I/O處理器，可」JCPU并行工作

O可實現I/O聯機處理

中斷是指CPU在收到外部中斷信號后，停止原來工作，轉去處理該中斷事件，完畢后回到原來斷點繼續工作。

O中斷處理過程：中斷請求，中斷響應，中斷點（暫停當前任務并保存現場），中斷處理例程，中斷返回（恢復中斷點的

現場并繼續原有任務

監官程序發展為執行系統(execulivesystem),常駐內存

★5.多道批處理系統

特點

O多道：內存中同時存放幾個作業：

O宏觀上并行運行：都處于運行狀態，但都未運行完；

O微觀上串行運行：各作業交替使用CPU：

優點：

O資源利用率高：CPU和內存利用率較高：

O作業吞吐量大：單位時間內完成的工作總量大；

缺點：

o用戶交互性差：整個作業完成后或中間出錯時，才與用戶交互，不利于調試和修改:

o作業平均周轉時間長：短作業的周轉時間顯著增長：

多道程序系統中，要解決的問題：同步互斥、內存不夠、使用效率、內存保護

6.計算機硬件；

構成計算機的基本硬件元素：處理器、存儲器、輸入輸出控制與總線、外部設備,

與操作系統相關的幾種主要的寄存器

數據寄存器

■地址寄存器

■條件碼寄存器

■程序計數器

■擰令計數器

■程序狀態字PSW

■中斷現場保護寄存器

■過程調用用堆棧

存儲器的訪問速度

寄存器

高速緩存

內存

硬盤緩存

硬盤

光盤、磁盤

大小

指令的執行和中斷

操作系統的啟動

啟動電源一產生中斷信號一觸發CPU中的一段指令發現操作系統引導區位置——導入內存執行——操作系統程序加載到內存制定區

域——初始化硬件……

7.算法

begin....end算法的開始于結束

repeat操作…until條件當“條件”未被滿足時重復所描述的“操作”

while條件do操作…….od當“條件”滿足時，進行相應的“操作”

if條件then操作else操作fi滿足“if”所指的“條件”時，進行“then”后的相關“操作”，否則完成“else”后的相關操作。

第二章

★I.作業：在一次應用業務處理過程中，從輸入開始到輸出結束，用戶要求計算機所做的有關該次業務處理的全部工作稱為一個作業。

作業由不同的順序相連的作業步組成，作業步是一個作業的處理過程中計算機所做的相對獨立的工作。

2.作業的組織：

作業由三部分組成，即程序、數據和作業說明書。作業中包含的程序和數據完成用戶所要求的業務處理工作，作業說明書則體現用戶的控

制意圖。

★由作業說明書在系統中生成一個稱為作業控制塊（JCB）的表格，JCB包括：作業名、估計執行時間、優先數（用于調度）、作業說明書

文件名、程序類型、資源要求（靜態申請和動態申請）、作業狀態（提交后各執行完成）。

作業說明書包括：作業基本情況描述（用戶名、作業名、使用語言名、允許最大處理時間等）、作業控制描述（控制方式、操作順序、出

錯處理等）、作業資源要求描述（要求處理時間、內存空間、外設類型和數量、處理及優先級、庫函數或實用程序等）。

★3.如何控制作業

①聯機輸入輸出方式

聯機輸入輸出方式大多用在交互式系統中，用戶與系統通過交互式會話輸入輸出昨業。在聯機輸入輸出方式中，外國設備直接與主機相連

接。

②脫機輸入輸出方式

脫機輸入又稱為偵輸入方式，利用低檔個人計算機作為外圍處理機進行輸入輸出處理。

③直接耦合方式

把主機與低檔外圍通過一個公用的大容量外存直接耦合起來。

④SPOOLING系統（外圍設備同時聯機操作）

多臺外圍設備通過通道或DMA器件和主機與外存連接起來。

⑤網絡聯機方式

網絡聯機方式以上述幾種輸入輸出方式為基礎。當用戶通過計算機網絡中的某一臺設備對計算機網絡中的另一臺主機進行輸入輸出操作

時，就構成了網絡聯機方式。

4系統調用

系統調用大致可分為6類：

（1）設備管理：該類系統調用被用來請求和釋放有關設備以及啟動設備操作等。

（2）文件管理：包括對文件的讀、寫、創建和刪除等。

（3）進程控制：包括進程創建、進程執行、進程撤銷、進程等待和執行優先級控制等。

（4）進程通信：該系統調用被用在進程之間傳遞消息或符號.

<5>存儲管理：包括調查作業占據內存區的大小、獲取作業占據內存區的始址第。

（6）線程管理：包括線程的創建、調度、執行、撤銷等。

系統調用的實現：當用戶使用系統調用時，產生?條相應的指令，處理機在執行到該指令時發生相應的中斷，并發出有關信號給該處理機

制。該處理機制在收到了處理機發來的信號后，啟動相關的處理程序去完成該系統調用所要求的功能。

陷進處理機構：在系統中為控制系統調用服務的機構稱為陷進處理機構。

陷進指令；把由于系統調用引起處理機中斷的指令稱為陷進指令。

第二早

1.程序的并發執行

程序用來描述計算機所完成的獨立功能，并在時間上嚴格地按前后次序相繼地進行計算機操作序列集合，是一個靜態概念。

個程序由若干個程序段組成，而這些程序段的執行必須是順序的，這種程序執行的方式就稱為程序的順序執行。

程序順序執行的特點：

■1.順序性

處理機嚴格按照程序所規定的順序執行，即每個操作必須在下一個操作開始之前結束。

■2.封閉性

程序一旦開始執行，其計算結果不受外界的影響，當程序的初始條件給定之后，其后的狀態只能由程序本身確定，即只有本程序才

能改變它。

■3.可再現性

程序執行的結果與初始條件有關，而與執行時間無關。即只要程序的初始條件相同，它的執行結果是相同的，不論它在什么時間執

行，乜不管計算機的運行速度。

多道程序系統中程序執行環境的變化

執行環境的特點：

■（1）獨立性

在多道環境下執行的每道程序都是邏輯上獨立的。

■（2）隨機性

程序和數據的輸入和執行開始時間都是隨機的。

■（3）資源共享

軟硬件資源的有限性導致資源共享。

程序并發執行：若干個程序段同時在系統中運行，這些程序的執行在時間上是重迭的，一個程序段的執行尚未結束，另一個程序段的執行

已經開始，即使這種重迭是很小的，也稱這幾個程序段是并發執行的。

2.★.進程：進程是一個程序對某個數據集的執行過程，是分配資源的基木單位。

進程和程序的區別與聯系：

①程序是指令的集合，是靜態的概念。進程是程序在處理機上的一次執行的過程，是動態的概念。程序可以作為軟件資料長期保存。進

程是有牛命周期的C

②進程是一個獨立的運行單位，能叮其它進程并行（并發）活動。而程序則不是,

③進程是競爭計算機系統有限資源的基本單位，也是進行處理機調度的基本單位，

④不同的進程可以包含同?程序，只要該程序所對應的數據集不同。

作業和進程的關系

作業是用尸需要計算機完成某項任務時要求計算機所做工作的集合。而進程則是已提交完畢程序的執行過程的描述，是資源分配的基本單

位。

其主要區別如下：

■作業是用戶向計算機提交任務的任務實體。

■一個作業可由多個進程組成。

■作業的概念主要用于批處理系統中。

進程描述

在系統中一個進程存在：進程控制塊PCB、有關程序段、數據結構集

①進程控制塊PCB（ProcessControlBlock）

包含一個過程的描述信息、控制信息及資源信息，有些系統還有進程調度等待所使用的現場保護區。PCB集中反映一個進程的動態特征。

在創建時，建立PCB,并伴隨進程運行的全過程，當進程完成其功能后，系統釋放PCB,進程也隨之消亡

（1）描述信息

1、進程名或進程標識號name

每個進程都必須有一個唯一的標識符，可以是字符串，也可以是一個數字。UNIX系統中就是一個整型數。在進程創建時由系統賦予。

2、用戶名或用戶標識號

每個進程都隸屬于某個用戶，用戶名或用戶標識號有利于資源共享和保護

3、家族關系processfamily

有的系統允許一個進程可創建自己的r進程，r進程還可以創建，一個進程往往處在一個家族之中，就需要記錄進程在家族中位置的

信息。

（2）控制信息

1、進程當前狀態status

說明進程當前所處的狀態。

為了管理的方便，系統設計時會符相同的狀態的進程組成一個隊列，如就緒進程隊列，等待進程則要根據等待的事件組成多個等待隊列，

如等待打印機隊列、等待磁盤I/O完成隊列等等。

2、進程優先級priority

進程的優先級反映進程的緊迫程度，通常由用戶指定和系統設置。

3、執行程序開始地址start-addr

4、各種計時信息

進程占用祭統資源的情況,不同的系統的處理差別很大C

5、通信信息communicalioninformalion

是指某個進程在運行的過程中要與其它進程進行通信，該區記錄有關進程通信方而的信息。

（3）資源管理信息

包括有關存儲器的信息、使用輸入、輸出設備的信息、有關文件系統的信息：

I、占用內存大小及管理用數據結構指針。

2、在某些曳雜系統中，還有對換或覆靛用的有關信息。

3、共享程序段大小及起始地址。

4、輸入輸出設備的設備號，所要傳送的數據長度、緩沖區地址、緩沖區長度及使用設備的有關數據結構指針等。

5、指向文件系統的指針及有關標識等。

（4）、CPU現場保護區cpustatus

當進程因某種原因不能繼續占用CPU時（等待打印機），粒放CPU,這時就要招CPU的各種狀態信息保護起來，為將來再次得到處理機

恢更CPU的各種狀態，繼續運行。

②進程上下文實際上是進程執行活動全過程於靜態描述。

進程上下文是一個抽象的概念，它包含了每個進程執行過的、執行時的以及待執廳的指令和數據，在指令寄存器、坨棧（存放個調用子程

序的返回點和參數等），狀態字寄存器等中的內容。

上文：已執行過的進程指令和數據在相關寄存器與堆棧中的內容。

正文：正在執行的指令和數據在相關寄存器與堆棧中的內容。

下文：待執行的指令和數據在相關寄存器與堆棧中的內容。

③進程上下文切換

進程上下文切換發生在不同的進程之間而不是同一個進程內。包含3個部分，第一部分為保存被切換進程的正文部分（或當前狀態）至有

關存儲區。第二部分操作系統進程中有關調度和資源分配程序執行，并選取新的進程。第三部分則是將被選中進程的原來被保存的正文部

分從有關存儲區中選出，并送至有關寄存器或堆棧中，激活被選中進程執行。

I進程Pl執行

中斷或進程調用

］新進程&執行

④進程空間和大小

任?進程都有H己的地址空間，把該空間稱為進程空間或虛空間。進程空間的大小只與處理機的位數有關。程序的執行都在進程空間內進

行。用戶程序、進程的各種控制表格等都按一定的結構排列在進程空間中。

在有的系統中進程空間被劃分為兩部分：用戶空間和系統空間。

為了防止用戶程序訪問系統空間，造成訪問出錯，計算機通過程序狀態寄存器等設置不同的執行模式，即用戶模式［用戶態）和系統模式

（系統態）來進行保護。

3,進程狀態及其轉換

★進程的三種基本狀態：執行狀態、就緒狀態、等待狀態（又稱阻塞、掛起、睡眠）

就緒狀態（Ready）

存在于處理機調度隊列中的那些進程，它們已經準備就緒，一旦得到CPU,就立即可以運行，這些進程所取的狀態為就緒狀態。（有多個

進程處于此狀態）

執行狀態（Running）

當進程由訓度/分派程序分派后，得到CPU控制權，它的程序正在運行，該進程所處的狀態為執行狀態。（在系統中，總只有一個進程處于

此狀態）

等待狀態（Wai。

若一個進程正在等待某個事件的發生（如等待i/o的完成），而暫停執行，這時.，即使給它CPU時間，它也無法執行，則稱該進程處于等

待狀態。

★進程狀態轉換

運行到等待等待某事件的發生（如等待I/O完成）

等待到就緒事件已經發生（如1/0完成）

運行到就緒時間片到（例如，兩節課時叵到，下課）

新建進程到就緒新創建的進程進入就緒狀態

就緒到運行當處理機空閉時，山調度（分派）程序從就緒進程隊列中選擇一個進程占用CPU。

進程控制：就是系統使用?些具有特定功能的程序段來創建、撤銷進程以及完成進程各狀態的轉換，從而達到多進程高效率并發執行和協

調、實現資源共享的目的。

原語：把系統態下執行的某些具有特定功能的程序段稱為原語。

用于進程控制的原語有：創建原語、撤銷原語、阻塞原語、喚醒原語。

進程創建方式：由系統程序模塊統一創建；由父進程創建。進程創建系統調用：create（name.priority.start-addr）UNIX系統：fork（）

進程撤銷：（1）該進程已完成所要求的功能而正常終止（2）由于某種錯誤導致非正常終止（3）祖先進程要求撤銷某個子進程。在一般操

作系統中進程撤消的系統調用是：killUNIX系統中是exit。如果撤銷進程有自己的了進程，則撤銷原語先撤銷其「進程的PCB結構并

釋放子進程所釋放的資源后，再撤銷當前進程的PCB結構和釋放其資源。

進程的阻塞與喚醒

當一個處在運行狀態的進程，因等待某個事件的發生（如等待打印機）而不能繼續運行時，將調用進程掛起系統調用，把進程的狀態置.為

阻塞狀態，并調用進程調度程序（等于讓出處理機）。

進程從運行狀態轉換成阻塞狀態是由進程掛起原語實現的，因此，調用進程掛起操作是在進程處于運行狀態下執行的。它的執行將引起等

待某事件的隊列的改變.

一個正在運行的進程會因等待某事件（例如，等待打印機）的發生，由運行狀態轉換成阻塞狀態，當它等待的事件發生后，這個進程將由

阻塞狀態轉換成就緒狀態。這種轉換由進程?喚醒操作完成。

喚醒一個進程有兩種方式：系統進程喚醒、事件發生進程喚醒。

調用進程喚醒操作一般在中斷處理、進程通信等過程中。例如，打印機完成中斷處理程序，在完成了打印完成的操作后，就去檢查等待

打印機的隊列，若不為空，則調用進程喚醒操作，喚醒一個（或多個）等待打印機的進程。

4.進程互斥

產生互斥的原因：資源共享、進程合作

★臨界資源：?次僅允許?個進程使用的資源稱為臨界資源。

★臨界區：每個進程中訪問臨界資源的那段程序段稱為臨界區（臨界段）。

間接制約：山丁共享某公有資源而引起的在臨界區內不允許并發進程交叉執行的現象稱為有共享公有資源而造成的對并發進程執行速度的

間接制約，簡稱間接制約。

★互斥：在操作系統中，當某一進程正在訪問某臨界區時，就不允許其它進程進入，否則就會發生（后果）無法估計的錯誤。我們把進程之

間的這種相互制約的關系稱為互斥。

進入臨界區的準則：

（1）不能假設各并發進程的相對執行速度:

（2）并發進程中的某個進程不在臨界區時，它不能阻止其他進程進入臨界區;

<3>并發進程中的若干個進程申請進入界區時，只能允許一個進程進入;

（4）當有若干個進程欲進入臨界區時，應在有限的時間內使其進入。

解決進程互斥的最簡單的辦法是加鎖。

在系統中為每個臨界資源設置一個鎖位,

I表示資源可用,

0表示資源已被占用（不可用;%

這樣當一個進程使用某個臨界資源之前必須完成下列操作:

1、考察鎖位的值;

2、若原來的值是為“I”，將鎖位置為“O''（占用該資源）:

3、若原來值是為“0”，（該資源已被別人占用），則轉到1。

當進程使月完資源后，將鎖位貴為稱為開鎖操作。

5.信號量與P、V原語

★信號量scm；是一個整數，在8cm大于等于零時，代表可供并發資源使用的資源實體數，但scm小于零時則表示正在等待使用臨界區的

進程數。sem代表資源的實體。在實際應用中應準確地說明sem的意義和初值。

★P操作:

(I)sem減1：

（2）若sem減1后仍大于等于0,則進程繼續執行;

（3）若結果小于0,則該進程掛起。

注：掛起該進程包括：保留調用進程CPU現場：置“等待”狀態：入等待隊列：轉進程調度:

算法：V

輸入：S

輸出：無

S++；

if（s<=0）

喚醒等待S的進程;

}

V操作:

（1）s值加I；

（2）若相加結果大于0,進程繼續執行:

（3）否則，喚醒一個（或多個）等待該信號燈的進程，然后本進程繼續執行或轉進程調度。

算法：V

輸入：s

sem=sem+l

輸出：無

(

s++;

返回if(s<=0)

喚醒等待S的進程;

}

返回或轉進程調度

★P、V原語實現互斥的原理

當一個進程想要進入臨界區時，它必須先執行P原語操作以將信號量sem減1。在一個進程完成對臨界資源的操作后，它必須執行V原語

操作以驛放它占用的臨界資源。由于信號量初始值為1,所以，任一進程在執行P原語操作之后將sem的值變為0,表示該進程可以進入

臨界區。在該進程未執行V原語操作之前如有另一進程想進入臨界區的話，它也應先執行P原語操作，從而使sem的值變為因此，第

二個進程將會被阻塞，直到第一個進程執行，原語操作之后，sem的值變為0,從而可喚醒第二個進程進入就緒隊列，經調度后進入臨界

區。在第二個進程執行完V原語操作之后，如果沒有其它進程申請進入臨界區的話，則sem又恢復到初始值。

用信號量實現兩并發進程Pa,Pb互斥的描述如下：

(1)設sem為互斥信號量，其取值范圍為(1,0,-l)o

其中sem=l標志進程Pa,Pb都未進入類名為S的臨界區，sem=0表示進程Pa,Pb已進入類名為S的臨界區,$em=-l表示進程Pa,Pb中,

一個進程已進入臨界區，而另一進程等待進入臨界區。

<2)描述

Pa：

P(sen)

<s>

V(sem)：

Pb：

P(sem)

<S>

V(sem)：：

main()甫個進程并發研時，pmt值1、0,7.

(若print*表示賄進程使用打卬機；

inIpiinL=l,§pnnt=0,表萬有一個進科正在使用打印機;

cobegin?print=-l,表示有一進程正在使用打聃I

pa();還有一個進程等件使用瓶機

Rb();

pa()《）

{

p(print);q(pr-int)；

使用打印機;使用打印機;

v(px-i.nt),

v(print);

???>

L

6.進程同步

★同步：把異步環境下的一組并發進程，因直接制約而互相發送消息而進行互相合作、互相等待，使得各進程按一定的速度執行的過程稱

為進程間的同步。

用wait（消息名）表示進程等待合作進程發來的消息.

功能：等存到消息名為true的進程繼續執行。

用signal（消息名）表示向合作進程發送消息

功能：發送消息名，并將其值置為血忙。

利用過程wait和singnal描述計算進程Pc和打印進程Pp的同步關系

（1）設消息名Bufcmpty表示buf為空，消息名Buffull表示Buf中裝滿了數據。

（2）初始化Bufcmpiy=lrue,Buffull=false.o

（3）描述：

Pc：

A：wait（Bufempty）

計算

Buf一計算結果

Bufemptyfalse

signaKBuffull）

GotoA

Pp：

B：wait（Bufful）

打印Buf中的數據

清除Buf中的數據

Bufful<false

signal(Bufcmply)

GotoB

★私有信號量(privateSem叩hore)：進程同步的信號量只與制約進程及被制約進程有關而不是與整組并發進程有關。因此該信號量稱為私

有信號量。

★用P.V原語操作實現同步

苜先，為各并發進程設置私有信號量，

然后，為私有信號量賦初值，

最后，利月P,V原語和私有信號量規定各進程的執行順序。

例：設進程Pa和Pb通過緩沖區隊列傳遞數據。Pa為發送進程，Pb為接收進程。Pa發送數據時調用發送過程dcpsiKdala),Pb接受數據

時調用過程remove((lata),H數據的發送和接受過程滿足如下條件：

Bufl—Buf2—―…一一Bufz——BufT?—

(1)在

PA：deposit(data)：

beginlocalx

P(Bufempty);

按FIFO方式選擇一個空緩沖區Buf(x)；

Buf(x)-dat

Buf(x)置滿標記

V(Buffull)

end

PB：remove(data)：

Beginlocalx

P(Buffull)；

按FIFO方式選擇一個裝滿數據的緩沖區Buf(x)

data<—Buf(%)

BufQ)置空標記

V(Bufempty)

End

★7.生產者與消費者問題

對于生產者進程：產生一個數據，當要送入緩沖區時，要檢查緩沖區是否已滿，若未滿，則可將數據送入緩沖區，尹通知消費者進程：否

則，等待；

對于消費者進程：當它去取數據時，要看緩沖區中是否有數據可取，若有則取走?個數據，并通知生產者進程，否則，等待。

這種相互等待，并互通信息就是典型的進程同步。

同時，緩沖區是個臨界資源，因此，諸進程對緩沖區的操作程序是一個共享臨界區，因此，還有個互斥的問題。

deposit(data)：

begin

P(avail)

P(uiulex)

送數據入緩沖區某單元

V(fbll)

V(mutex)

end

remove(data)：

begin

P(full)

P(mutex)

取緩沖X中某單元數據

V(avail)

V(mutex)

End

full：緩沖區產品做目.初位為O,unw：緩沖區E存放產品的空位，初值為n;

inutux：對輟沖區反斥信號火丁.初值,為1,

pr-oducer'Oconsurner"()

{{

while(生產未完成)while(玨騾名強綾7肖費)

{{

P(full);

生上一個產品;p(mutex);

p(empty);從緩沖區中取出一個產品；

p(mutex);v(mutex);

枸產品放入短沖區：v(empty);

v(mutex);消費一個產品；

v(full)；????

}}

))

8.進程通信

通信(communicalion)意味著進程間傳遞數據。操作系統可以看作是各種進程組成的，這些進程都具有各自獨立的功能，且大多數都被外

部需要而后動執行。

在單機系統中進程的通信有4種形式：

(1)主從式

(2)會話式

(3)消息或郵箱機制

(4)共享存儲區方式

會話方式的特點：

(1)使用進程在使用服務進程所提供的服務之前，必須得到服務進程的許可。

(2)服務進程根據使用進程的要求提供服務，但對所提供服務的控制由服務進程自身完成。

（3）使用進程和服務進程在進行通信時有固定連接關系。

消息或郵符機制的特點是：

（I）只要存在空緩沖區或郵箱，發送進程就可以發送消息。

（2）與會話系統不同，發送進程和接受進程之間無宜接聯接關系。

（3）發送進程和接受進程之間存在緩沖區或郵箱用來存放被傳送消息。

郵箱通信就是由發送進程申請建立一與接受進程聯接的郵箱。設置郵箱的最大好處是發送進程和接受進程之間沒有時間上的限制。

共享存儲區方式不要求數據移動，兩個需要互相交換信息的進程通過共享數據區的操作達到互相通信的目的。

9.死鎖問題

死鎖：指個并發進程彼此互相等待對方所擁有的資源，且這些并發進程在得到對方的資源之前不會釋放自己所擁有的資源。從而造成大家

都想得到資源而又得不到資源，個并發進程不能繼續向前推進的狀態。

★死鎖的起因：根本原因在于系統提供的資源個數少于并發進程所要求的該類資源數。

★產生死鎖有四個必要條件：

（1）互斥條件。并發進程所要求和占有的資源是不能同時被兩個以上進程使用或操作的，進程對他所需要的資源進行排他性控制。

<2>不剝奪條件。進程所獲得的資源在未使用完畢之前，不能被其它進程強行剝奪，而只能由獲得該資源的進程自己釋放。

（3）部分分配。進程每次申請它所需要的一部分資源，在等待新資源的同時，紙續占用已分配的資源。

（4）環路等待條件。存在一種進程循環鏈，鏈中每一個進程已獲得的資源同時被下一個進程所請求。

只要有一個條件不滿足，死鎖就可解除。

預防死鎖

1.破壞“請求與保持條件”每個進程在運行之前，必須預先提出自己所要使用的全部資源，調度程序在該進程所需要的資源末得到滿足之

前，不讓它們投入運行，并且當資源一旦分配給某個進程之后，那么在該進程的些個運行期間相應資源一直被它占有，這就破壞了產生死

鎖的部分分配條件。

2.破壞環路條件對系統提供的每一項資源，由系統設計者將它們按類型進行線性排隊，并賦予不同的序號。

3.資源受控動態分配為了避免死鎖發牛.，澡作系統必須根據預先掌握的關于資源用法的信息控制資源分配，使得共同進展路徑的下一

步不致于進入危險區，即只要有產生死鎖的可能性，就避免把?種資源分配給一個進程。

死鎖的檢測和恢復

1.資源剝奪法

（1）還原算法。即恢復計算結果和狀態。

（2）建立檢查點主要是用來恢復分配前的狀態。

2.撤消進程法

按一定的順序中止進程序列，直至已釋放到有足夠的資源來完成剩下的資源為止，

第四章

L一個作業從提交給計算機系統到執行結束退出系統，一般都要經歷提交、收容、執行和完成四個狀態。

一個作業在其處于從輸入設備進入外部存儲設備的過程成為提交狀態。處于提交狀態的作業，因其信息尚未全部進入系統，所以不能被調

用程序選取。

收容狀態乜稱為后備狀態，輸入管理系統不斷地將作業輸入到外存中對應部分（或稱輸入井，即專門用來存放待處理作業信息的一組外存

分區）。若一個作業的全部信息已全部被輸入進輸入井，那么，在它還未被調度去執行之前，該作業處于收容狀態。

作業調度程序從后備作業中選取若干作業到內存投入運行。它為被選中作業建立進程并分配必要的資源，這時，這些被選中的作業處于執

行狀態。

當作業運行完畢，但它所占用的資源尚未全部被系統收回時，該作業處丁完成狀態。

一股來說，處理機調度可分為4級：作業調度、交換調度、進程調度、線程調度,

作亞調度，又稱宏觀調度或高的調度,其中要仟務是按一定的原則對外在輸入井卜的大量后備作W進行選擇.給選出的作業分配內存、輸

入輸出設各等必要的資源，并建立相應的根程序，以使該作業的進程獲得競爭處理機的權利，另外，當該作業執行完畢時，還負責回收系

統資源。

交換調度：又稱中級調度，其主要任務是按照給定的原則和策略，將處于外存交換區中的就緒狀態或就緒等待狀態的進程調入內存，或把

處于內存就緒狀態或內存等待狀態的進程交換到外存交換區。交換調度主要涉及內存的管理和擴充，一般將它歸在存儲管理之中。

進程調度：又稱微觀調度或低級調度，其主要任務是按照某種策略和方法選取一個處于就緒狀態的進程占用處理機.

只有在多道批處理系統中才有作業調度，而在分時和實時系統中一般只有進程調度、交換調度和線程調度。

這是因為在分時和實時系統中，為了縮短響應時間或為了滿足用戶需求的截止時間，作業不是建立在外在中，而是直接建立在內存中。

2.作業調度

作業調度的功能：

記錄系統中各作業的狀況，包括執行階段的有關情況。通常，系統為每個作業建立一個作業控制表JCB記錄這些有關信息。

作業控制塊JCB：在作業調度的過程中記錄作業各方面的信息。它隨作業的創建而產生，隨作業的撤消而被清除。

（2）從后備隊列中選取一部分作業投入執行

（3）為被選中的作業做好執行前的準備工作，

（4）在作業執行結束時做好善后處理工作。

作業調度目標：

（1）對所有作業應該是公平合理的。

（2）應使設備有高的利用率。

（3）每天執行盡可能多的作業

（4）有快的響應時間

對于批處理系統，作業的平均周轉時間或平均帶權周轉時間，被作為衡量調度算法優劣的標準：對于分時系統和實時系統，外加平均響應

時間作為衡量調度算法優劣的標準

★（I）周轉時間：

作業i從提交時刻到完成時刻稱為作業的周轉時間。Ti=Tei-Tsi

Tei為作業i的完成時間，Tsi為作業的提交時間

一個作業的周轉時間說明了該作業在系統內停留的時間，包含兩部分：一是等待時間：二為執行時間

Ti=Twi+Tri

Twi主要是指作業i由后備狀態到執行狀態的等待時間，它不包括作業進入執行狀態后的等待時間。

★一批作業的平均周轉時間為：

n

T==l/n￡Ti

i=l

★帶權周轉時間

Wi=Ti/TriTi作亞周轉時間Tri作'”執行時間

★一批作業的平均帶權周轉時間為

n

W=l/nEWi

i=l

3.進程調度

進程調度的功能；

①用PCB塊記錄系統中所有進程的執行情況

②按照一定的調度算法，選擇一個處于就緒狀態的進程，給它分配處理機（這是最重要的功能）

③實施進行進程上下文的切換

引起進程調度的原因：

（1）E在執行的進程執行完畢。這時，圻果不選擇新的就緒進程執行，將浪巖處理機資源。

（2）執行中進程自己調用阻塞原語將自己阻塞起來進入睡眠等待狀態。

（3）執行中進程調用了P原語操作，從而因資源不足而被阻塞；或調用了V原語激活了等待資源的進程隊列。

（4）執行中進程提出了I/O請求后被阻塞。

（5）在分時系統中時間片己經用完。

（6）在執行完系統調用，在系統程序返叵用戶進程，可認為系統進程執行完畢，從而可調度選擇一新的用戶程序執行。

以上都是CPU執行不可剝奪方式下做引起的進程調度的原因，在CPU執行方式走可剝奪時，還有：

（7）就緒隊列中的某進程的優先級變得高于當前執行進程的優先級，從而也將發生進程調度。

可剝奪方式：即就緒隊列中一旦有優先級高于當前進程優先級的進程存在時，便立即發生進程調度，轉讓處理機。

非剝奪方式（不可剝奪方式）：即使在就緒隊列存在有優先級高于當前執行進程時，當前進程仍將繼續占有處理機，直到該進程因自己調

度調用原語操作或、等待I/O進入阻塞狀態或時間片用完時才重新發生調度讓出處理機。

進程調度性能評價

（I）進程調度性能是衡量操作系統性能的?個重要指標

（2）在大多數情況下，利用測試或模擬系統響應時間的方法來評價進程調度的性能

★4.調度算法

①先來先服務（FCFS）算法

將用戶作業和就緒進程按提交順序或變成就緒狀態的先后排成隊列，并按照先來先服務的方式進行調度處理。

優點：在一般意義下是公平的，即每個作業或進程都按照它們在隊列中等待時間長短來決定它們是否優先享受服務。

缺點：對于那些執行時間較短的作業或進程來說，如果它們在某些執行時間很長的作業或進程之后到達，則它們等待很長時間。

②（時間片］輪轉法（RR）

算法描述：就緒隊列按進程到達的時間來排列。處理機的時間被分為固定大小的時間片。調度程序總是選擇就緒隊列中的第一個進程。一

個執行進程如果在用完一個時間片后還沒有完成其任務，它就自動釋放處理機回到就緒隊列的末尾重新排隊，等待下一次被調度。

缺點：只能用來分配那些可搶占資源,而R這種算法只能用十進程調度,不能用干作業調度（作加調度包含了不可搶占資源工

時間片的選取非常重要，時間片長度的選擇會直接影響系統開銷和響應時間。如果時間片長度過短，則調度程序剝奪處理機的次數

增多，這將使進程上下文交換次數也大大增加，加重了系統開銷。如果時間片長度選擇過長（大），大到一個進程足以完成其全部運行工作

所需的時間，那么時間片輪轉法就退化為先來先服務策略了。最佳的時間片量值應能使分時用戶得到好的響應時間。

時間片的確定

在輪轉法中，時間片長度q根據系統對響應時間的要求R和就緒隊列中所能容納的最大進程數Nmax確定的。q=R/Nmax

一種改進的方法就是每當一輪調度開始時，系統根據就緒隊列中當前的進程數計算一次q,作為新一輪調度的時間片。

③多級反饋輪轉法（進程調度）

（1）在時間片輪轉法中設置三個就緒隊列

a.時間片完成就緒隊列

b.等待結束就緒隊列

c.新進程就緒隊列

（2）每個隊列建立時按FCFS排列，同一隊列中進程的優先級相同，不同隊列具有不同的優先級

優先級高的隊列中進程的時間片短，優先級低的隊列中進程的時間片長。

（3）進程調度時，先調度高優先級就緒隊列中的進程，當高優先級就緒隊列為空時才調度優先級低的就緒隊列中的進程

（4）一個進程在執行過程中要經歷不同的就緒隊列

④優先級法

算法描述：按照某種原則給作業或進程確定一個優先級，進程的就緒隊列或作業的后冬隊列按對象的優先級進行排列，高前低后。對象進

入隊列是插入。當調度發生時，排列在最前面的進程或作業被調度。

確定優先級的方法有兩類：動態法和靜態法

靜態法是根據作業或進程的靜態特性，在作業或進程開始執行之前就確定它們的優先級，一旦開始執行后就不能改變。

動態法：把作業或進程靜態性和動態性結合起來確定作業或進程的優先級，隨著作業或進程的執行過程，優先級不斷變化。

作業調度中靜態優先級確定原則：

（I）日用戶自己根據作業的緊急程度輸入一個適當的優先級

（2）L1系統或操作員根據作業類型指定優先級。

（3）系統根據作業要求資源情況確定優先級。

進程調度靜態優先級確定原則:

（1）按照進程的類型給與不同的優先級。

（2）籽作業的靜態優先級作為它所屬進程的優先級。

由于在進程調度中靜態優先級確定方法的缺陷：系統效率低、調度性能不高，所以多采用動態的方法確定優先級。

進程調度動態優先級確定原則：

（1）根據進程占有CPU時間的長短來決定。一個進程占有處理機時間越長，則在被阻塞后再次獲得調度的優先級越低，反之，獲得

訓度的可能性越大

<2>根據就緒進程等待CPU的時間長短來決定。一個就緒進程在就緒隊列中等待的時間越長，則它獲得調度選中的優先級就越高。

⑤最短作業優先法SJF（作業調度）

選擇那些估計需要執行時間最短的作業投入執行，為它們創建進程和分配資源。

優點：可使得系統在同一時間內處理的作業個數最多，從而吞吐量也就大于其他調度方式。

缺點：對于一個不斷有作業進入的批處理系統來說，最短作業優先法有可能使得那些長作業永遠得不到調度執行的機會。

⑥最高響應比優先法（作業調度）

綜合平衡FCFS和SJF,既考慮等待時間長的作業，也照顧執行時間短的作業。

響應比：R=（等待時間W+執行時間T）/執行時間T

優點：長作業有機會獲得調度執行

缺點：同一時間內處理的作業數少于最短作業優先法，吞吐量也小于最短作業優先法

調度前計算響應比，系統開銷增加。

算法評價

FCFS算法

人:作業到達率：

U：服務器（主機）的服務率：

只有當入<U時系統才是穩定的。

n：系統中的平均作業個數：

R：系統晅應時間；

P：5,是系統中存在作業的概率，1-P是系統中沒有作業的概率。

n=P/（I-P）

Little結果：n=入R；R=n/入

FCFS算法的評價：

R=n/X=p/（l-p）*l/X

RR算法

q：時間片:

k:每個進程平均需要的時間片數，即該進程到達等待隊列的次數；

線性優先級法的調度性能

I/U：平均服務時間，貝Ij:l/U=kXq

RR算法的評價：

已使用過k次時間片的進程的響應時間是：

R（k）=P/（A（1-P））

=l/（u（l-P））=kXq/（l-p）

FCFS方式短作業駐留時間與長作W相同,對如作業不利.

輪轉法所需服務時間短的顧客響應時間將會小于所需服務時間長的顧客響應時間，

實時調度算法分類：靜態表格驅動類、靜態優先級驅動搶先式調度算法類、動態計劃調度算法類、盡力而為調度算法類。

具有代表性的實時調度算法

時限式調度法（靜態表格驅動類代表）：是一種以滿足用戶要求時限為調度原則的算法。

算法描述：時限有兩種：處理開始時限和處理結束時限，在實際中可以使用任一種時限.

頻率單調調度（靜態優先級驅動搶先式調度算法類代表）；是一種被廣泛用于多周期性實時處理的調度算法。其基本原理是頻率低（周期

越長）的任務優先級越低。

第五章

1.存儲器：能接收數據和保存數據、而且能根據命令提供這些數據的裝置。

存儲器分成兩類：內存儲器（簡稱內存、主存、物理存儲器）外存儲器（簡稱外存、輔助存儲器）

虛擬存儲器：為用戶提供一種不受物理存儲器結構和容量限制的存儲器的技術稱為虛擬存儲器，或稱虛擬存儲技術。虛擬存儲器需要大容

量的外存儲器的支持，或稱物資基礎。

程序地址：用戶編程序時所用的地址（或稱邏輯地址、虛地址），基本單位可與內存的基本單位相同，也可以不相同。

程序地址空間（邏輯地址空間、虛地址空間）：用戶的程序地址的集合稱為邏輯地H:空間，它的編址總是從。開始的，可以是一維線性空間，

也可以是多維空間。

物理地址：把內存分成若干個大小相等的存儲單元，每個單元給一個編號，這個編號稱為內存地址（物理地址、絕對地址、實地址），存

儲單元占8位，稱作字節（byte）。

物理地址空間：物理地址的集合稱為物理地址空間（主存地址空間），它是一個一維的線性空間。

安排進程的地址方法：

（1）按照物理存儲器中的位置賦予實際物理地址。好處：CPU執行目標代碼時的執行速度高。壞處：由于物理存儲器的容量限制，能

裝入內存并發執行的進程數將會大大減少，對于某些較大的進程來說，當其所要求的總內存容量超過內存容量時將會無法執行；

曰于編譯程序必須知道內存的當前空閑部分及其地址，并且把一個進程的不同程序段連續的存放起來，因此編譯程序將非常復雜。

（2）編譯鏈接程序把用戶源程序編譯后鏈接到一個以（）地址為始地址的線性或多維虛擬地址空間。

2.存儲管理功能：

★地址映射將程序地址空間中使用的邏輯地址變換成主存中的地址的過程

主存分配按照一定的算法把某一空閑的主存區分配給作業或進程。

存儲保護保證用戶程序（或進程映象）在各自的存儲區域內操作,互不干擾。

提供虛擬存儲技術使用戶程序的大小和結構不受主存容量和結構的限制，即使在用戶程序比實際主存容量還要大的情況下，程序也能正

確運行.

★實現地址映射有三種方式：

①.編程或編譯時確定地址映射關系

②.靜態地址映射

③.動態地加映射

（1）編程或編譯時確定地址映射關系

編程時確定虛一實地址的關系是指在用機器指令編程時，程序員直接按物理內存地址編程，這種程序在系統中是不能做任何移動的，否則

就會出借。

（2）靜態地址映射

靜態地址映射是在程序裝入內存時完成從邏輯地址到物理地址的轉換的。在一些早期的系統中都有一個裝入程序（加載程序），它負責將

用戶程序裝入系統，并將用戶程序中使用的訪問內存的邏輯地址轉換成物理地址,

優點：實現筒單，不要硬件的支持。

缺點：程序一旦裝入內存，移動就比較困難。有時間上的浪費。在程序裝入內存時要將所有訪問內存的地址轉換成物理地址。

必須占用連續的內存空間，很難做到程序和數據的共享。

（3）動態地址映射

動態地址映射是在程序執行時山系統硬件完成從邏輯地址到物理地址的轉換的。動態地址映射是山硬件地執行時完成的，程序中不執行的

程序就不做地址映射的工作，這樣節省了CPU的時間。重定位寄存器的內容由操作系統用特權指令來設置.，比我靈活。實現動態地址

映射必須有硬件的支持，并有一定的執行時同延遲。現代計算機系統中都采用動態地址映射技術。

優點：可以對內存進行非連續分配，動態市.定位提供了實現虛擬存儲器的基礎，有利于程序段的共享。

動態地址映射技術能滿足以下目標：

（1）具有給一個用戶程序任意分配內存區的能力；

（2）可實現虛擬存儲；

（3）具有重新分配的能力

（4）對于一個用戶程序，可以分配到多個不同的存儲區

3.內外存數據傳輸的控制

要實現內存擴充，在程序執行過程中，內存和外存之間必須經常地交換數據。內外存的數據流動控制方法有兩種

一種是用尸自己控制程序，例子：卷蓋技術，一種早期的主存擴充技術，要求用戶了解程序結構，指定各程序段調入內存的先后次序。

另種是操作系統控制，A交換方式：操作系統把等待狀態的進程換出內存，而把等待事件已發生，處于就緒態的進程換入內存。B請求

調入方式和預調入方式：請求調入方式：在程序執行時，如果所要訪問的程序段或數據段不在內存中，則操作系統自動地從外存將有關程

序段和數據段調入內存地一種操作系統控制方式。預調入方式：系統預測在不遠的將來會訪問到的哪些程序段和數據段，并在它們訪問前

調人。

4內存的分配和回收

在多道程序設計的環境中，內存分配的功能包括：制定分配策略、構造分配用的數據結構、響應系統的內存分配的請求和回收系統釋放的

內存區。內存管理策略有5種：

（1）分配結構登記內存使用情況，供分配程序使用的表格和鏈表。

（2）放置策略確定調入內存的程序和數據在內存中的位苴。決定內存中放置信息的區域（或位宜），即如何在若干個空閑區中選擇一個

或幾個空閉區的原則：

（3）交換第咯當內存不足時,決定將某些信息調出內存的策略.

（4）調入策咯外存中的程序段和數據段什么時間按照什么樣的控制方式進入內存

（5）回收策咯