操作系統引論1.0什么是操作系統1.0.1計算機系統的組成1.0.2操作系統的定義1.0.3操作系統在軟硬件層次中的地位1.0.1計算機系統的組成

輸入設備：鍵盤、鼠標、掃描儀

輸出設備：顯示器、打印機

外

存：軟、硬盤、光盤、閃存

網絡設備：網卡、調制解調器等

計算機系統軟件外部設備系統軟件應用軟件硬件運算器控制器主機內存CPU隨機存儲器(RAM)只讀存儲器(ROM)高速緩沖存儲器

操作系統：Windows、Unix、Linux語言處理程序：C、Pascal、VB等實用程序：診斷程序、排錯程序等

辦公軟件包、數據庫管理系統

1.0.2操作系統的定義

操作系統是計算機系統的一個系統軟件，它直接控制和管理計算機系統中的硬件及軟件資源，合理的組織計算機工作流程，以便有效的利用這些資源為用戶提供一個功能強大、使用方便和可擴展的工作環境，從而在計算機與其用戶之間起到接口的作用。操作系統（operatingsystem，簡稱OS）1.0.3操作系統在軟硬件層次中的地位

裸機操作系統編譯軟件應用軟件1.1操作系統的目標和作用1.1.1操作系統的目標1.1.2操作系統的作用1.1.3推動操作系統發展的主要動力1.1.1操作系統的目標

目前存在著多種類型的OS，不同類型的OS，其目標各有所側重。通常在計算機硬件上配置的OS，其目標有以下幾點：

1.方便性

2.有效性

3.可擴充性

4.開放性1.1.2操作系統的作用1.OS作為用戶與計算機硬件系統之間的接口

OS作為用戶與計算機硬件系統之間接口的含義是：OS處于用戶與計算機硬件系統之間，用戶通過OS來使用計算機系統。或者說，用戶在OS幫助下，能夠方便、快捷、安全、可靠地操縱計算機硬件和運行自己的程序。應注意，OS是一個系統軟件，因而這種接口是軟件接口。圖1-1OS作為接口的示意圖用戶應用程序系統調用命令圖標、窗口操作系統計算機硬件

(1)命令方式。這是指由OS提供了一組聯機命令(語言)，用戶可通過鍵盤輸入有關命令，來直接操縱計算機系統。

(2)系統調用方式。OS提供了一組系統調用，用戶可在自己的應用程序中通過相應的系統調用，來操縱計算機。

(3)圖形、窗口方式。用戶通過屏幕上的窗口和圖標來操縱計算機系統和運行自己的程序。2.OS作為計算機系統資源的管理者

處理機管理，用于分配和控制處理機；

存儲器管理，主要負責內存的分配與回收；

I/O設備管理，負責I/O設備的分配與操縱；

文件管理，負責文件的存取、共享和保護。

3.OS用作擴充機器

把覆蓋了軟件的機器稱為擴充機器或虛機器。

OS包含了若干個層次，因此在裸機上覆蓋OS后，便可獲得一臺功能顯著增強，使用極為方便的多層擴充機器或多層虛機器。1.1.3推動操作系統發展的主要動力不斷提高計算機資源利用率2.方便用戶3.器件的不斷更新換代4.計算機體系結構的不斷發展1.2操作系統的發展過程1.2.1無操作系統的計算機系統1.2.2單道批處理系統1.2.3多道批處理系統1.2.4分時系統1.2.5實時系統1.2.1無操作系統的計算機系統1.人工操作方式電子管計算機時代（1945年到50年代中期），無操作系統。由手工控制作業的輸入輸出,通過控制臺開關啟動程序運行。用戶使用計算機的過程大致如下：先把程序紙帶裝上輸入機，啟動輸入機把程序和數據送入計算機，然后通過控制臺開關啟動程序運行，計算完畢后，用戶拿走打印結果，并卸下紙帶。缺點：(1)用戶獨占全機(2)CPU等待人工操作。2.脫機輸入/輸出(Off-LineI/O)方式

用戶使用計算機的過程大致如下：先把程序紙帶裝上輸入機，在外圍機的控制下，輸入到磁帶上，當CPU需要時，從磁帶高速調入內存。輸出時，CPU直接高速把數據從內存送到磁帶，然后在另一臺外圍機的控制下，將磁帶上的結果通過輸出設備輸出。脫機輸入/輸出（Off－LineI/O）方式脫離主機的情況下輸入輸出程序和數據聯機輸入/輸出（On－LineI/O）方式在主機的直接控制下輸入輸出程序和數據脫機I/O方式的主要優點如下：減少了CPU的空閑時間。(2)提高I/O速度。輸入設備外圍機磁盤主機外圍機輸出設備圖1-2脫機I/O示意圖1.2.2單道批處理系統(SimpleBatchProcessingSystem)1.單道批處理系統的處理過程圖1-3單道批處理系統的處理流程把下一個作業的源程序轉換為目標程序源程序有錯嗎？否裝配目標程序還有下一個作業？是否停止運行目標程序是開始2.單道批處理系統的特征單道批處理系統是最早出現的一種OS，嚴格地說，它只能算作是OS的前身而并非是現在人們所理解的OS。盡管如此，該系統比起人工操作方式的系統已有很大進步。該系統的主要特征如下：

(1)自動性。

(2)順序性。

(3)單道性。1.2.3多道批處理系統1.多道程序設計的基本概念

在單道批處理系統中，內存中僅有一道作業，它無法充分利用系統中的所有資源，致使系統性能較差。為了進一步提高資源的利用率和系統吞吐量，在60年代中期又引入了多道程序設計技術，由此而形成了多道批處理系統(MultiprogrammedBatchProcessingSystem)。在該系統中，用戶所提交的作業都先存放在外存上并排成一個隊列，稱為“后備隊列”；然后，由作業調度程序按一定的算法從后備隊列中選擇若干個作業調入內存，使它們共享CPU和系統中的各種資源。在OS中引入多道程序設計技術可帶來以下好處：提高CPU的利用率。比較：圖1-4(a)：單道程序的運行情況圖1-4(b)：多道程序的運行情況（以四道為例）(2)可提高內存和I/O設備利用率。(3)增加系統吞吐量（在單位時間內完成的總工作量）。圖1-4單道和多道程序運行情況(b)四道程序運行情況t1t2t3t4t5t6t7t8結束中斷I/O

完成啟動I/OI/O

中斷請求I/O

完成啟動

I/OI/O

中斷請求用戶程序監督程序I/O

操作(a)單道程序運行情況程序A程序AI/O請求程序AI/O完成程序B程序BI/O請求程序C程序CI/O請求程序D程序DI/O請求CI/O完成C再被調度程序BI/O完成程序A再被調度程序A程序B程序C程序D調度程序A完成結束中斷2.多道批處理系統的特征多道性。(2)無序性。(3)調度性。3.多道批處理系統的優缺點資源利用率高。(2)系統吞吐量大。(3)平均周轉時間長。(4)無交互能力。優點缺點

作業的周轉時間：是指從作業進入系統開始，直至其完成并退出系統為止所經歷的時間。4.多道批處理系統需要解決的問題處理機管理問題。(2)內存管理問題。(3)I/O設備管理問題。(4)文件管理問題。(5)作業管理問題。1.2.4分時系統1.分時系統(Time-SharingSystem)的產生

推動多道批處理系統形成和發展的動力是提高資源利用率和系統吞吐量。推動分時系統形成和發展的主要動力是用戶的需要：（1）人機交互（2）共享主機（3）便于用戶上機

分時系統是指在一臺主機上連接多個帶有顯示器和鍵盤的終端，同時允許多個用戶通過自己的鍵盤，以交互的方式使用計算機，共享主機中的資源。主機終端2.分時系統實現中的關鍵問題

如何使用戶能與自己的作業進行交互，即當用戶在自己的終端上鍵入命令時，系統應能及時接收并及時處理該命令，再將結果返回給用戶。即使有多個用戶同時通過自己的鍵盤鍵入命令，系統也應能全部地及時接收并處理。(1)及時接收（多路卡和緩沖區）(2)及時處理（作業直接進入內存，劃分時間片）3.分時系統的特征多路性。(2)獨立性。(3)及時性。(4)交互性。

1.2.5實時系統

實時系統(Real-TimeSystem)是指系統能及時(或即時)響應外部事件的請求，在規定的時間內完成對該事件的處理，并控制所有實時任務協調一致地運行。1.應用需求實時控制：通常是指以計算機為中心的生產過程控制系統和武器控制系統。(2)實時信息處理：通常是指對信息進行實時處理的系統。2.實時任務1)按任務執行時是否呈現周期性來劃分周期性實時任務外部設備發出周期性的激勵信號。

(2)非周期性實時任務外部設備所發出的激勵信號并無明顯的周期性，但都必須聯系著一個截止時間(Deadline)。它又可分為：

①開始截止時間——任務在某時間以前必須開始執行

②完成截止時間——任務在某時間以前必須完成

2)根據對截止時間的要求來劃分

(1)硬實時任務(hardreal-timetask)。系統必須滿足任務對截止時間的要求，否則可能出現難以預測的結果。

(2)軟實時任務(Softreal-timetask)。它也聯系著一個截止時間，但并不嚴格，若偶爾錯過了任務的截止時間，對系統產生的影響也不會太大。3.實時系統與分時系統特征的比較多路性。(2)獨立性。(3)及時性。(4)交互性。(5)可靠性。1.3操作系統的基本特性1.3.1并發（Concurrence）1.3.2共享（Sharing）1.3.3虛擬（Virtual）1.3.4異步性（Asynchronism）1.3.1并發(Concurrence)

所謂并發是指在內存中放多道作業，在一個時間段上來看，每一道作業都能不同程度地向前推進，但在任何一個時間點上只能有一道占用CPU。與并發相關的兩個概念：串行：在內存中每次只能放一道作業，只有它完 全執行完后別的作業才能進入內存執行。并行：存在于有多個CPU的環境中，在內存中放 多道作業，在任一時間點上都可能有多道 作業在不同的CPU上同時執行。1.3.2共享(Sharing)

共享：系統中的資源可供內存中多個并發執行的進程（線程）共同使用。兩種資源共享方式：互斥共享方式（臨界/獨占資源）同時訪問方式并發與共享互為條件！1.3.3虛擬(Virtual)

虛擬是指通過某種技術，將一個物理實體變為若干個邏輯上的對應物。用來實現虛擬的技術，被稱為虛擬技術。在現代OS中利用了多種虛擬技術，分別用來實現虛擬處理機、虛擬存儲器和虛擬設備等。1.3.4異步性(Asynchronism)

異步性是指在多道程序的環境下，每個程序不知何時執行、何時暫停，即它們以不可預知的速度向前推進。但同時，操作系統應保證程序的執行結果是可再現的。即只要運行環境相同，一個作業的多次運行都會得到相同的結果。1.4操作系統的主要功能1.4.1處理機管理功能1.4.2存儲器管理功能1.4.3設備管理功能1.4.4文件系統管理1.4.5用戶接口1.4.1處理機管理功能

處理機是最重要的資源，現代操作系統允許多個程序共享處理機，按照某種算法（分時、優先級）交替地使用處理機。處理機管理包括以下幾方面：進程控制進程同步（進程互斥方式、進程同步方式）進程通信調度1.4.2存儲器管理功能

第二重要資源。存儲器管理主要是為多道程序的運行提供良好的環境。存儲器管理要具備下列功能：內存分配

內存保護：使多道程序間互不干擾

地址映射：把程序中的邏輯地址映射為物理地址內存擴充：用輔存擴充主存，實現“虛擬存儲器”

最龐大、瑣碎的部分，因為：

物理設備品種繁多、用法各異

各種外設能和主機并行工作主機與各類外設速度極不匹配，級差很大1.4.3設備管理功能

設備管理主要是完成用戶的I/O請求。它的主要功能包括：緩沖管理：為設備提供緩沖區以緩和CPU同設備的I/O速度不匹配的矛盾。

設備分配

設備處理1.4.4文件管理功能

文件管理主要是使用戶能方便、安全地使用各種信息資源。主要功能包括：

文件存儲空間的管理目錄管理文件的讀/寫管理和保護2.1進程的基本概念2.1.1前趨圖2.1.2程序的順序執行及其特征2.1.3程序的并發執行及其特征2.1.4進程的特征與狀態2.1.5進程控制塊2.1.1前趨圖（PrecedenceGraph）

是一個有向無循環圖，記為DAG(DirectedAcyclicGraph)，用于描述進程之間執行的前后關系。P1P2P3P4P5P6P7P8P9結點有向邊直接前驅直接后繼初始結點終止結點重量例：具有九個結點的前趨圖PiPj前趨關系：P1→P2,P1→P3,P1→P4,P2→P5,P3→P5,P4→P6,P4→P7,P5→P8,P6→P8,P7→P9,P8→P9

S1S2S3前驅圖中不能存在循環關系。如：2.1.2程序的順序執行及其特征各程序段間程序的順序執行如圖：

在計算機系統中只有一個程序在運行，這個程序獨占系統中所有資源，其執行不受外界影響。一道程序執行完后另一道才能開始。I1P1O1I2P2O2作業1作業2一個程序段的多條語句的順序執行：S1S2S3S1:a:=x+yS2:b:=a-5S3:c:=b+1程序順序執行的特征：順序性：一個程序開始執行必須要等到前一個程序已執行完成。封閉性：程序一旦開始執行，其計算結果不受外界因素影響。可再現性：程序的結果與它的執行速度無關（即與時間無關），只要給定相同的輸入，一定會得到相同的結果。2.1.3程序的并發執行及其特征1.程序的并發執行所謂程序的并發執行是指：若干個程序同時在系統中執行，這些程序的執行在時間上是重疊的，一個程序的執行尚未結束，另一個程序的執行已經開始。

I1I2I3C1C2C3P1P2P3I4C4P4一個程序段的多條語句的并發執行：S1:a:=x+2S2:b:=y+5S3:c:=a+bS4:d:=c+6S1S3S4S2程序并發執行的特征：間斷性由于資源共享和相互合作，并發執行的程序間形成了相互制約關系，導致程序的運行過程出現“執行—暫停—執行”的現象。失去封閉性程序在并發執行時，是多個程序共享系統中的資源，因此這些資源的狀態將由多個程序來改變。不可再現性由失去封閉性導致。同樣的初始條件，一個程序的多次重復執行，可得到不同的結果。

例：程序A、B，共享變量N。代碼如下：程序ABEGINREPEAT……N：=N+1……UNTILFALSEEND程序BBEGINREPEAT……PRINT(N)N:=0…UNTILFALSEEND兩個程序以不同速度運行，可能出現三種情況：N:=N+1在Print(N)和N:=0之前

——N值分別為N+1，N+1，0N:=N+1在Print(N)和N:=0之后

——N值分別為N,0,1N:=N+1在Print(N)和N:=0之間

——N值分別為N,N+1，0思考：任何并發執行都是不可再現的嗎？并發執行的條件：

并發執行的條件：達到封閉性和可再現性。并發執行失去封閉性的的原因是共享資源的影響，去掉這種影響就行了。1966年，由Bernstein給出并發執行的條件。將程序中任一語句或程序段Pi劃分為兩個變量的集合，R(pi)和W(pi)。其中，

R(pi)={a1,a2,…an}，程序pi在執行期間引用的（讀的）變量集，稱為“讀集”。

W(pi)={b1,b2,…bm}，程序pi在執行期間改變的（寫的）變量集，稱為“寫集”。

Bernstein條件:

如果對于語句p1、p2，如果同時滿足以下三個條件：R(p1)∩W(p2)={}R(p2)∩W(p1)={}W(p1)∩W(p2)={}

則語句p1、p2可以并發執行。例如，有如下四條語句：

S1:a:=x+yS2:b:=z+1S3:c:=a–bS4:w:=c+1其中：R(S1)={x,y}W(S1)={a}R(S2)={z}W(S2)={b}R(S3)={a,b}W(S3)={c}R(S4)={c}W(S4)={w}對于S1和S2，有：

R(S1)∩W(S2)={}，R(S2)∩W(S1)={}，

W(S1)∩W(S2)={}結論：語句S1和S2滿足Bernstein條件，可以并發執行。其他語句之間自己分析。2.1.4進程的特征與狀態1.進程的定義

進程是操作系統中最基本、重要的概念。是多道程序系統出現后，為了刻畫系統內部出現的動態情況，描述系統內部各道程序的活動規律引進的一個概念，所有多道程序設計操作系統都建立在進程的基礎上。較典型的進程定義有：

(1)進程是程序的一次執行。

(2)進程是一個程序及其數據在處理機上順序執行時所發生的活動。

(3)進程是程序在一個數據集合上運行的過程，它是系統進行資源分配和調度的一個獨立單位。

(4)進程是進程實體的運行過程，是系統進行資源分配和調度的一個獨立單位。

(5)進程是一個具有一定獨立功能的程序關于某個集合的一次運行活動。(我國78年廬山研討會)

2.進程同程序的比較：進程是動態的，程序是靜態的：程序是有序代碼的集合；進程是程序的執行。通常進程不可在計算機之間遷移；而程序通常對應著文件、靜態和可以復制。進程是暫時的，程序是永久的：進程是一個狀態變化的過程，是有一定生命期的；而程序可以作為一種軟件資料長久保存。進程與程序的組成不同：進程是由程序和數據、進程控制塊三部分組成的。進程與程序的對應關系：同一程序同時運行于若干個數據集合上，它將屬于若干個不同的進程。也就是說同一程序可以對應多個進程；一個進程的執行也可以涉及到一個或幾個程序（調用）。3.進程的特征：結構特征：由程序段、數據段、進程控制塊三部分組成；動態性：進程是程序的執行；并發性：多個進程可同存于內存中，能在一段時間內同時運行；獨立性：獨立運行的基本單位，獨立獲得資源和調度的基本單位；異步性：各進程按各自獨立的不可預知的速度向前推進。4.進程的三種基本狀態不同系統設置的進程狀態數目不同。進程有三種基本狀態：

1)就緒狀態：進程已獲得除CPU以外的所有必要資源，只要得到CPU，便可立即執行。2)執行狀態：進程已得到CPU，其程序正在CPU上執行。3)阻塞狀態：正在執行的進程因某種事件(如I/O請求)的發生而暫時無法繼續執行，只有等相應事件完成后，才能去競爭CPU。進程的狀態變遷圖執行五狀態進程模型進程正常結束，或因某種原因被取消后，OS釋放出的進程。剛剛建立的進程，還未送入就緒隊列。執行新建態終止態5.

七狀態進程模型引入掛起狀態的原因：終端用戶的請求父進程請求負荷調節的需要操作系統的需要

“掛起”的實質是使進程不能繼續執行，即使掛起后的進程處于就緒狀態，它也不能參與對CPU的競爭。因此，稱被掛起的進程處于靜止狀態，相反，沒被掛起的進程則處于活動狀態。而且，處于靜止狀態的進程，只有通過“激活”動作，才能轉換成活動狀態。進程掛起后,程序代碼和數據集被調出到外存的交換區中,騰出來的內存空間供其它進程使用。激活掛起事件發生事件發生等待事件掛起調度超時釋放激活掛起激活掛起事件發生事件發生等待事件掛起調度超時釋放激活掛起七狀態進程模型掛起就緒態掛起阻塞態就緒態阻塞態執行態終止態新建態就緒態（ready）:進程在內存且可立即進入運行狀態。阻塞態（blocked）:進程在內存并等待某一個事件的出現。掛起就緒態（readysuspend）:進程在外存,但只要進入內存,即可運行。掛起阻塞態（blockedsuspend）:進程在外存并等待某一個事件的出現。【思考題】有沒有這樣的狀態轉換，為什么？ 阻塞—運行就緒—阻塞2.1.5進程控制塊（ProcessControlBlock，PCB

）

1.進程控制塊的作用

進程控制塊的作用是使一個在多道程序環境下不能獨立運行的程序(含數據)，成為一個能獨立運行的基本單位，一個能與其它進程并發執行的進程。或者說，OS是根據PCB來對并發執行的進程進行控制和管理的。進程與PCB是一一對應的。

PCB應常駐內存。2.進程控制塊中的信息進程標識符：用于惟一地標識系統中的每個進程。另外，還可以用父進程的標識符及子進程的標識符來描述進程的家族關系。處理機狀態：用于CPU切換時保存現場和恢復現場，主要由處理機中各種寄存器的內容組成。進程調度和控制信息：用于進程調度和控制，主要包括進程狀態、優先級、等待和使用CPU的時間總和、程序和數據的地址、進程同步和通信信息、資源清單和進程隊列指針等。3.進程控制塊的組織方式圖2-7PCB鏈接隊列示意圖

在一個系統中通常有許多的PCB，稱為PCB集合。為了便于管理，系統必須用適當的方式將PCB組織起來，常用的方式有鏈接方式和索引方式。PCB14PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB93087901執行指針就緒隊列指針阻塞隊列指針空閑隊列指針…1)鏈接方式相同狀態的進程PCB組成一個鏈表，不同狀態對應多個不同的鏈表。空指針2)索引方式執行指針就緒索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7阻塞索引表就緒表指針阻塞表指針對具有相同狀態的進程，分別設置各自的PCB索引表，表明PCB在PCB表中的地址。2.2進程控制2.2.1進程的創建2.2.2進程的終止2.2.3進程的阻塞與喚醒2.2.4進程的掛起與激活

進程控制是進程管理中最基本的功能，它用于創建和撤消進程，并對進程在整個生命周期中各種狀態之間的轉換進行有效控制。進程控制是由操作系統的內核通過原語來實現的。原語：系統狀態下執行的某些具有特定功能的程序段稱為原語。(原語的執行具有原子性，執行時不可分割)。2.2.1進程的創建1.進程圖(ProcessGraph)：用于描述一個進程的家族關系的有向樹。

DEFGHBCIJKLMA祖先進程父進程子進程

子進程可以繼承父進程的所有資源，當子進程被撤消時，應將從父進程那里獲得的資源歸還給父進程。撤消父進程時也必須同時撤消其所有的子進程。2.引起創建進程的事件(1)用戶登錄。(2)作業調度。(3)提供服務。(4)應用請求。3.進程的創建(CreationofProgress)(1)申請空白PCB。

(2)為新進程分配資源。

(3)初始化進程控制塊。

(4)將新進程插入就緒隊列。創建新進程通過進程創建原語creat（）來完成。進程創建原語的主要任務是創建進程控制塊PCB。入口查PCB鏈表有空PCB？取空PCB（i）將有關參數填入PCB（i）相應項PCB（i）入就緒隊列PCB(i)入進程家族或進程鏈創建失敗返回創建原語流程圖NY2.2.2進程的終止

當某進程實現完成任務正常結束時，或在運行過程中遇到某些異常情況（如越界錯誤、非法指令、運行超時等），或外界干預需要結束時，應予以終止（撤消）。（參見P35）通過進程終止原語來終止進程。終止進程的實質是收回PCB。進程的終止過程：

(1)查找對應的PCB(2)終止該進程及子孫進程

(3)釋放資源

(4)釋放PCB

終止原語流程圖入口查進程鏈表或進程家族有此PCB嗎？釋放該進程所占有的資源出錯處理該PCB有子進程嗎？釋放該PCB結構本身YYNN返回2.2.3進程的阻塞與喚醒1.進程的阻塞當正在執行的進程需要等待某種事件的完成或本身無新工作可做時，應調用阻塞原語將自己從執行狀態轉換成阻塞狀態。進程阻塞是進程的一種主動行為。通過阻塞原語block（）來完成。具體的操作過程是：停止進程的執行，將其狀態改為阻塞狀態，并把它的PCB插入相應的阻塞（等待）隊列，轉調度程序進行重新調度。阻塞原語流程圖保存當前進程的CPU現場置該進程的狀態被阻塞進程入阻塞隊列轉進程調度入口2.進程的喚醒當阻塞進程所等待的事件完成時，應調用喚醒原語將該進程的狀態從阻塞狀態轉換成就緒狀態。通過喚醒原語wakeup（）來完成。

處于阻塞狀態的進程是絕不可能叫醒自己的，必須由它的合作進程用喚醒原語喚醒它。具體的操作過程是：在等待隊列中移出該進程的PCB，將其置成就緒狀態，并把它插入就緒隊列。喚醒原語流程圖從等待隊列中摘下被喚醒進程將被喚醒進程置為就緒態將被喚醒進程送入就緒隊列轉進程調度或返回入口2.2.4進程的掛起與激活1、進程的掛起當出現了引起進程掛起的事件時，用戶請求將自己掛起，或者父進程請求掛起自己的子進程。系統通過掛起原語suspend（）將指定進程掛起。具體的執行過程：檢查被掛起進程的狀態，如果處于活動就緒狀態，就將它改為靜止就緒；如果處于活動阻塞，則改為靜止阻塞。將PCB復制到指定的內存區域供用戶或父進程考查。若掛起前進程正在執行，則轉調度程序重新進行進程調度。2、進程的激活當發生激活事件后，系統利用激活原語Active()將指定進程激活。具體的操作過程是：若進程處于靜止阻塞狀態，則將它轉換成活動阻塞狀態，否則將它轉換成活動就緒狀態。若進程轉換成活動就緒狀態，而系統又采用搶占調度策略，則應檢查該進程是否有權搶占CPU，若有則應進行進程調度。2.3進程同步2.3.1進程同步的基本概念2.3.2信號量機制2.3.3信號量的使用

進程同步是指對多個相關進程在執行次序上進行協調。進程同步的主要任務是使并發執行的諸進程之間能有效的共享資源和相互合作，從而使程序的執行具有可再現性。1.兩種形式的制約關系

間接相互制約關系互斥關系，資源共享關系直接相互制約關系同步關系，相互合作關系2.3.1進程同步的基本概念2.臨界資源

一次僅允許一個進程訪問的資源。如：進程Ａ、Ｂ共享一臺打印機，若讓它們交替使用則得到的結果肯定不是我們希望的。臨界資源可能是硬件，也可能是軟件：變量，數據，表格，隊列等。并發進程對臨界資源的訪問必須作某種限制，否則就可能出現錯誤，如：聯網售票，會出現與時間有關的錯誤。例：兩進程共享一個變量COUNTP1:R1:=COUNT;R1:=R1+1;COUNT:=R1;P2:P2:=COUNT;R2:=R2+1;COUNT:=R2;試比較兩進程順序執行和并發執行的結果。若P1、P2按如下順序并發執行：P1:R1:=COUNT;P2:R2:=COUNT;P1:R1:=R1+1;COUNT:=R1;P2:R2:=R2+1;COUNT:=R2;

若P1、P2順序執行：

P1:R1:=COUNT;R1:=R1+1;COUNT:=R1;P2:R2:=COUNT;R2:=R2+1;COUNT:=R2;3.臨界區(CriticalSection)

每個進程中，訪問臨界資源的那段代碼稱為臨界區。諸進程對臨界資源的互斥訪問就變為怎樣使諸進程互斥地進入臨界區。

互斥的實質就是同步，或者說，互斥是同步的一種特殊形式。

訪問臨界資源的循環進程描述如下：

REPEAT

ENTRYSECTIONCRITICALSECTIONEXITSECTIONREMAINDERSECTIONUNTILFALSE進入區臨界區退出區剩余區4.同步機制應遵循的原則

用來實現互斥的同步機制必須遵循下述四條準則：

(1)空閑讓進。

(2)忙則等待。

(3)有限等待。

(4)讓權等待。2.3.2信號量機制

信號量機制是荷蘭學者Dijkstra在1965年提出的一種卓有成效的同步工具，在長期且廣泛的應用中，已由早期的整型信號量發展為記錄型信號量，進而發展為信號量集。1.整型信號量

整型信號量是一個非負的共享整數，除了初始化外，它只能通過兩個標準的原子操作wait和signal來訪問，即P、V操作。

wait和signal操作可描述為：

wait(S):whileS≤0dono-op

S∶=S-1;

signal(S):S∶=S+1;

整型信號量的主要問題是，只要S≤0，wait操作就會不斷地測試，因而，沒能做到“讓權等待”。2.記錄型信號量

記錄型信號量中除了一個整型變量value外，還增加了一個等待隊列指針L。記錄型信號量采用了記錄型的數據結構，描述為：typesemaphore=record

value:integer;

L:listofprocess;

end

相應的wait和signal操作（即P、V操作）可描述為：procedureP(S)

varS:semaphore;

begin

S.value:=S.value-1;

ifS.value＜0thenblock(S.L)

end

當S.value＜0時，進程會立即將自己阻塞，因此解決了整型信號量的“忙等”問題，做到了“讓權等待”。該進程狀態置為阻塞狀態；放棄處理機；將該進程的PCB插入鏈表S.L中。procedureV(S)

varS:semaphore;

begin

S.value:=S.value+1;

ifS.value≤0thenwakeup(S.L)

end

喚醒S.L鏈表中的第一個等待進程；改變狀態為就緒態；將其插入就緒隊列中。

一個信號量通常對應于一類臨界資源，在使用前，信號量必須經過定義并賦適當的初值，初值表示系統中某類資源的數目。初值為1表示對臨界資源進行訪問，此時信號量轉化為互斥信號量。每次對信號量進行wait操作意味著申請一個單位的該類資源，signal操作意味著歸還一個單位的該類資源。當S.value＞0時，它的值表示系統中該類資源當前可用的數目；S.value≤0時，表示該類資源已分配完畢，其絕對值表示系統中因申請該類資源而阻塞在S.L隊列上的進程數目。

必須注意的幾個問題：2.3.3信號量的使用必須置一次且只能置一次初值初值為整數，且不能為負數

只能執行P、V操作1.用信號量實現進程互斥P(mutex)V(mutex)P1P2P3互斥區P(mutex)P(mutex)V(mutex)V(mutex)PA:…P(mutex);criticalsection;V(mutex);…PB:…P(mutex);criticalsection;V(mutex);…mutex用于實現互斥，初值為1。在每個進程中將臨界區代碼置于P(mutex)和V(mutex)之間。模型：模擬執行：序號PAPBmutex說明011P(mutex)0PA進入，占資源2P(mutex)-1PB進入，無資源3V(mutex)0PA釋放資源，PB解封4V(mutex)1PB釋放資源0可反復執行

對于兩個并發進程，互斥信號量的值僅取1、0和-1三個值：若mutex＝1表示沒有進程進入臨界區；若mutex＝0表示有一個進程進入臨界區；若mutex＝-1表示一個進程進入臨界區，另一個進程等待進入。當實現n個進程并發時，互斥信號量的取值為1、0、-1、…、-(n-1)。

P、V操作必須成對出現：遺漏P(mutex)將不能保證互斥訪問，遺漏V(mutex)將不能再使用臨界資源之后將其釋放（給其他等待的進程）。PA:…L1：P(proceed)…2.用信號量實現同步PB:…L2：V(proceed)…proceed用于實現同步，初值為0。PA在L1點必須與PB在L2點同步，PA受PB的制約，而PB不受PA的制約，使非對稱的。

P、V操作必須成對出現，當用于實現互斥時，它們同處于同一進程；當用于實現同步操作時，則不在同一進程中出現。模型：3.利用信號量描述前趨關系

信號量可用來描述程序或語句之間的前趨關系。若Pi是Pj的直接前趨，即Pi→Pj，則可設置一個初值為0的公用信號量S，并將V(S)操作放在Pi后，而在Pj前插入P(S)操作，以保證Pi在Pj開始執行之前完成。PiPjVara,b,c,d,e,f,g:semaphores;Beginparbeginbegins1;v(a);v(b);end;beginp(a);s2;v(c);end;beginp(c);s4;v(e);v(f);end;beginp(b);s3;v(d);end;beginp(e);s5;v(g);end;beginp(f);p(d);s6;v(h);end;beginp(g);p(h);s7;end;Parbeginends1s2s3s4s5s1s6s7abcdefgh例：2.4經典進程的同步問題2.4.1生產者—消費者問題2.4.2哲學家進餐問題2.4.3讀者——寫者問題2.4.1生產者—消費者問題放產品取產品一次只可放一個產品生產者消費者

只要倉庫未滿，生產者就可以把產品放入倉庫。只要倉庫未空，消費者就可以從倉庫中取走物品。問題描述：inout01234567891011in:下一個可供投放產品的緩沖區,in:=(in+1)modn；

out:下一個可供獲取產品的緩沖區,out:=(out+1)modn。若(in+1)modn=out，有界緩沖區滿；若in=out，有界緩沖區空。環形緩沖池設一個長度為n的有界緩沖區：（以n=12為例）問題分析：這是一個同步與互斥共存的問題。1.生產者—消費者問題是一個同步問題。即生產者和消費者之間滿足如下條件：消費者想接收數據時，有界緩沖區中至少有一個單元是滿的。生產者想發送數據時，有界緩沖區中至少有一個單元是空的。故設置兩個信號量：empty：說明空緩沖區的數目，初值為有界緩沖區的大小N。full：說明已用緩沖區的數目，初值為０。

2.

由于有界緩沖區是臨界資源，因此，各生產者進程和各消費者進程之間必須互斥執行。故設置一個互斥信號量mutex，其初值為１。問題的解：Varmedex,empty,full:semaphore;buffer:array[0,1,…n-1]ofitem;in,out:integer;Beginmetex:=1;empty:=n;full:=0;in:=0;out:=0;Parbegin

procedure:……

consumer:……ParendendConsumer：

beginrepeat

P(full);P(mutex);

從Buffer[out]取產品;out=(out+1)modn;

V(mutex);V(empty);…

消費產品;…untilfalse;endProducter：

begin

repeat…

生產產品;

…

P(empty);P(mutex);

往Buffer[in]放產品;in=(in+1)modn;

V(mutex);V(full);untilfalse;end有五個哲學家圍坐在一圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每兩人之間放一只筷子。2.4.2哲學家就餐問題問題描述：每個哲學家的行為是思考，感到饑餓，然后吃通心粉；吃完后繼續思考。為了吃通心粉，每個哲學家必須拿到兩只筷子，并且每個人只能直接從自己的左邊或右邊去取筷子。問題的解：repeat

P(fork[i]);P(fork[(i+1)mod5])；

…

進食；

…

V(fork[i]);V(fork[(i+1)mod5])；

…

思考；

…untilfalse設fork[5]為5個信號量（分別表示每支筷子），初值均為1。此解可以保證互斥使用筷子，但會產生死鎖。為防止死鎖發生可采取的措施：

最多允許4個哲學家同時去拿左邊的筷子；僅當一個哲學家左右兩邊的筷子都可用時，才允許他拿筷子進餐；（

）給所有哲學家編號，奇數號的哲學家必須首先拿左邊的筷子，偶數號的哲學家則反之。信號量集——AND型信號量集AND型信號量集的基本思想：在一個原語中申請整段代碼需要的多個臨界資源，要么全部分配給它，要么一個都不分配。AND型信號量集P原語為Swait；

AND型信號量集V原語為Ssignal。采用AND信號量集解決哲學家就餐問題repeat

Swait(fork[i],fork[(i+1)mod5])；

…

進食；

…

Ssignal(fork[i],fork[(i+1)mod5])；

…

思考；

…untilfalse設fork[5]為5個信號量（分別表示每支筷子），初值為均1。2.4.3讀者-寫者問題問題描述：

有兩組并發進程——讀者和寫者，共享一組數據區。要求：允許多個讀者同時執行讀操作；任一寫者在完成寫操作之前不允許其它讀者或寫者工作(讀寫文件)；寫者執行寫操作前，應讓已有的寫者和讀者全部退出。如果讀者來：若無讀者、寫者，則新讀者可以讀；若有寫者等待，但有其它讀者正在讀，則新讀者也可以讀；若有寫者寫，則新讀者等待。如果寫者來：若無讀者，則新寫者可以寫；若有讀者，則新寫者等待；若有其它寫者，則新寫者等待。問題分析：問題的解：整形變量readcount表示正在讀的讀者數目，初值為0。信號量w用于保證讀者和寫者、寫者和寫者之間的互斥,初值為1。信號量mutex用于保證對readcount這個臨界資源的互斥修改，初值為1。讀者：beginrepeat

P(mutex);readcount:=readcount+1;ifreadcount=1thenP(w);

V(mutex); …

執行讀操作；

…

P(mutex);readcount:=readcount-1;ifreadcount=0thenV(w);

V(mutex);untilfalseend寫者：beginrepeat

P(w);

執行寫操作；

V(w);untilfalseend【思考題】

桌上有一空盤，最多允許存放一只水果。爸爸可向盤中放一個蘋果或放一個桔子，兒子專等吃盤中的桔子，女兒專等吃蘋果。試用P、V操作實現爸爸、兒子、女兒三個并發進程的同步與互斥。提示：設置一個信號量表示可否向盤中放水果，一個信號量表示可否取桔子，一個信號量表示可否取蘋果。問題的解：Daughter:repeatP(Sa)；取蘋果；

V(S);

吃蘋果;untilfalseSon:repeatP(So)；取桔子；

V(S);

吃桔子;untilfalseFather:repeatP(S);

將水果放入盤中;if桔子

thenV(So);elseV(Sa);untilfalse

設置三個信號量S、So、Sa，初值分別為1、0、0。分別表示可否向盤中放水果，可否取桔子，可否取蘋果。【思考題】

有一個倉庫，可以存放A和B兩種產品，但要求：（1）每次只能存入一種產品（A或B）；（2）－N＜A產品數量－B產品數量＜M；其中，N和M是正整數。試用P、V操作描述產品A與B的入庫過程。提示：設兩個信號量Sa、Sb。Sa表示允許A產品比B產品多入庫的數量；Sb表示允許B產品比A產品多入庫的數量設兩個信號量Sa、Sb，初值分別為M-1，N-1Sa表示允許A產品比B產品多入庫的數量Sb表示允許B產品比A產品多入庫的數量設互斥信號量mutex，初值為1。問題的解：B產品入庫進程：repeat

P(Sb);P(mutex);B產品入庫

V(mutex);V(Sa);

…

消費產品;…untilfalseA產品入庫進程：repeat…

生產產品;…

P(Sa);

P(mutex);A產品入庫

V(mutex);

V(Sb);untilfalse2.5管程機制2.5.1管程的基本概念2.5.2利用管程解決生產者-消費者問題2.5.1管程的基本概念為什么引入管程？把分散在各進程中的臨界區集中起來進行管理；防止進程有意或無意的違法同步操作；便于用高級語言來書寫程序，也便于程序正確性驗證。管程的基本概念：一個管程定義了一個數據結構和能為并發進程所執行（在該數據結構上）的一組操作，這組操作能同步進程和改變管程中的數據。管程的特點：

(1)管程內的局部變量只能被局部于管程內的過程所訪問；反之亦然，即局部于管程內的過程只能訪問管程內的變量。

(2)任何進程只能通過調用管程提供的過程入口進入管程。

(3)任一時刻，最多只能有一個進程在管程中執行。typemonitor-name=monitorvariabledeclarations

procedureentryP1(…);

begin…end;

procedureentryP2(…);

begin…end;

…

procedureentryPn(…);

begin…end;

begin

initializationcode;

end管程的語法局部于管程的共享變量說明對該數據結構進行操作的一組過程對局部于管程的數據設置初始值管程的組成部分共享數據…一組操作過程初始化代碼進入隊列條件(不忙)隊列管程的示意圖：

當進程通過管程請求臨界資源未能滿足時，將排在隊列上等待。等待的原因可能有多個，為了區分它們，引入條件變量condition。每個condition表示一種等待原因。

針對條件變量x，x.wait將自己阻塞在x隊列中，x.signal將x隊列中的一個進程喚醒。條件變量：2.5.2利用管程解決生產者-消費者問題PC管程描述：TypeProducer-Consumer=monitorVarbuffer：array[0,…,n-1]ofitem；count，in，out：integer；notempty，notfull：condition；procedureentryput(item);beginifcount>=nthennotfull.wait;buffer(in):=nextp;in:=(in+1)modn;count:=count+1；

ifnotempty.queuethennotempty.signal;end;procedureentryget(item);beginifcount<=0thennotempty.wait;nextc:=buffer(out);out:=(out+1)modn;count:=count-1；

ifnotfull.queuethennotfull.signal;end;Beginin:=0;out:=0;count:=0Endproducer：beginrepeatproduceanitem；

PC.put(item)；

untilfalse；endconsumer：beginrepeat

PC.get(item)；

consumetheitem；

untilfalse;end生產者和消費者描述：2.6進程通信2.6.1進程通信的類型2.6.2消息緩沖隊列通信機制

進程之間互相交換信息的工作稱為進程通信。進程通信的類型：低級通信：歸結為進程之間的互斥和同步，一般只傳送少量信息（信號量）。缺點：效率低，通信對用戶不透明。高級通信：能夠高效傳輸大量數量數據的通信方式。又分為三類：共享存儲器系統、消息傳遞系統、管道通信系統。2.6.1進程通信的類型1.共享存儲器系統

相互通訊的進程通過共享數據結構和共享存儲區進行通訊，可進一步分為：

基于共享數據結構的通信方式進程之間通過某種數據結構，如緩沖池進行通信，屬于低級通信方式。如生產者-消費者問題中的有界緩沖區。

基于共享存儲區的通信方式為了傳送大量信息，在存儲器中劃出一塊共享存儲區，諸進程可通過對共享存儲區進行讀或寫來實現通信，屬高級通信方式。2.消息傳遞系統

使用最廣泛的一種進程通信機制。進程間的數據交換以消息或報文為單位，程序員直接利用一組通信命令（原語）來實現通信。操作系統隱藏了通信的實現細節，簡化了通信程序編制的復雜性。（1）直接通信方式兩條通信原語：Send（Receiver，message）;Receive（Sender，message）;

例如：Send（p2，m1）;Receive（p1，m1）;發送進程可直接將消息發送給目標進程。消息傳遞系統的分類：——直接通信方式和間接通信方式repeat

…

produceaniteminnextp;

…

send(consumer,nextp);

untilfalse;利用直接通信原語解決生產者-消費者問題：repeat

receive(producer,nextc);

…

consumetheiteminnextc;

untilfalse;producer：consumer：

（2）間接通信方式

進程間發送或接收消息通過信箱進行，消息可被理解成信件。也稱信箱通信。兩條通信原語：

Send（mailbox，message）；

Receive（mailbox，message）；注意：用戶不必寫出接收進程標識符，從而可以向不知名的進程發送消息；另外，消息在信箱中可以安全的保存，只允許核準的目標用戶隨時讀取，可實現非實時通信。發送進程A

…郵箱體

郵箱頭接收進程B

信箱由信箱頭和由若干格子組成的信箱體組成。信箱中每個格子存放一封信，信箱中格子的數目和每格的大小在創建信箱時確定。進程間的通信要滿足如下條件：

a.

發送進程發送消息時，郵箱中至少要有一個空格存放該消息。

b.

接收進程接收消息時，郵箱中至少要有一個消息存在。3.管道（Pipe）通信系統

所謂管道，是指用于連接一個讀進程和一個寫進程以實現它們之間通信的一個共享文件，又稱pipe文件。發送進程以字符流形式把大量數據送入管道，接收進程從管道中接收數據，所以叫管道通信。管道的實質是一個共享文件，基本上可借助于文件系統的機制實現，包括（管道）文件的創建、打開、關閉和讀寫。讀寫進程相互協調，必須做到：

互斥：進程對通信機構的使用應該互斥，一個進程正在使用某個管道寫入或讀出數據時，另一個進程就必須等待。

同步：管道長度有限,發送信息和接收信息之間要實現正確的同步關系。當寫進程把一定數量的數據寫入pipe，就去睡眠等待，直到讀進程取走數據后，把它喚醒。

確定對方是否存在：發送者和接收者雙方必須能夠知道對方是否存在，如果對方已經不存在，就沒有必要再發送信息。寫進程共享文件讀進程管道通信的思想：（1）發送進程可以源源不斷的從pipe一端寫入數據流，在規定的pipe文件的最大長度（如4096字節）范圍內，每次寫入的信息長度是可變的；（2）接收進程在需要時可以從pipe的另一端讀出數據，讀出單位長度也是可變的。2.6.2消息緩沖隊列通信機制

消息緩沖隊列通信機制通過內存中公用的消息緩沖區進行進程通信，屬于直接通信方式。發送進程利用send原語將消息直接發送給接收進程；接收進程利用receive原語接收消息。（1）消息緩沖區的數據結構typemessageBuffer=record

sender；發送者ID;size；消息長度;text；消息正文;next；消息隊列指針;end1.消息緩沖隊列通信機制中的數據結構（2）PCB中有關通信的數據項typePCB=record…mq;消息隊列首指針;mutex;消息隊列互斥信號量;sm;消息隊列資源信號量;…end2.用P、V操作來實現Send原語proceduresend(receiver,a)

begin

getbuf(a.size,i);

i.sender:=a.sender;i.size:=a.size;

i.text:=a.text;

i.next:=0;

getid(PCBset,receiver.j);

P(j.mutex);

insert(j.mq,i);

V(j.mutex);

V(j.sm);

end根據a.size申請緩沖區i;將發送區a中的信息復制到消息緩沖區之中;獲得接收進程內部標識符;將消息緩沖區插入消息隊列;3.用P、V操作來實現Receive原語procedurereceive(b)

begin

j:=internalname;

P(j.sm);

P(j.mutex);

remove(j.mq,i);

V(j.mutex);

b.sender:=i.sender;b.size:=i.size;

b.text:=i.text;

releasei;end

j為接收進程內部的標識符；將消息隊列中第一個消息移出；將消息緩沖區i中的信息復制到接收區b;

將消息緩沖i歸還給系統;mqmutexsmSend(B,a)sender:Asize:5text:Hellosender:Asize:5text:Hellonext:0receive(b)sender:Asize:5text:Hello發送區a進程A進程B接收區bPCB(B)第一消息緩沖區ba2.7線程線程的引入:引入進程的目的是為了使多個程序并發執行，以改善資源利用率、提高系統吞吐量。引入線程則是為了減少程序并發執行時的所付出的時空開銷。進程的兩個基本屬性：進程是一個可擁有資源的基本單位。進程同時又是一個可獨立調度和分派的基本單位。線程的屬性:輕型實體：線程自己基本不擁有系統資源，只擁有少量必不可少的資源：程序計數器、一組寄存器、棧。獨立調度和分派的基本單位：在引入線程的OS中，線程是進程中的一個實體，是被系統獨立調度和分派的基本單位。可并發執行：同一進程中的多個線程之間可以并發執行，不同進程中的線程也能并發執行。共享進程資源：它可與同屬一個進程的其它線程共享進程所擁有的全部資源。引入線程的好處:創建一個新線程花費時間少（結束亦如此）；兩個線程的切換花費時間少；因為同一進程內的線程共享內存和文件，因此它們之間相互通信無須調用內核；適合多處理機系統。3.1處理機調度的基本概念3.1.1高級、中級和低級調度3.1.2調度隊列模型3.1.3選擇調度方式和調度算法的若干原則高級調度：又稱為作業調度或長程調度。用于決定把后備隊列中的哪些作業調入內存，為它們創建進程、分配必要的資源，再將新創建的進程排在就緒隊列上，準備執行。在批處理系統