操作系統輔導

湯子贏、哲風屏、湯小丹

1第一章操作系統引論

操作系統的目標、作用和模型l

操作系統——是裸機上的第一層軟件，它是對硬件系統功能的首次擴充，是填補人與機器之間的鴻溝。用戶計算機OS2

操作系統的目標●

設置操作系統的目的：

1、方便性:操作系統使計算機更易于使用

2、有效性:操作系統允許以更有效的方式使用計算機系統資源。

3、可擴展性:在操作系統中,允許有效地開發，測試和引進新的系統功能。

4、開放性:實現應用程序的可移植性和互操作性,要求具有統一的開放的環境。3

OS的作用●計算機用戶需要的用戶命令由OS實現的所有用戶命令所構成的集合常被人們稱為OS的Interface(用戶接口)；有時也稱為命令接口。

命令的表示形式： 字符形式：較靈活但因繁瑣而難記；

菜單形式：(試圖在字符終端上提供友好的用戶界面)

圖形形式：因直觀而易記但不靈活。●應用軟件需要的SystemCall(系統調用)

由OS實現的所有系統調用所構成的集合被人們稱為程序接口或應用編程接口(ApplicationProgrammingInterface,API)。4●操作系統作為計算機系統資源管理者。1、處理機管理：分配和控制CPU。2、存儲器管理：內存分配與回收。3、I/O設備管理：I/O設備的分配與操縱。4、文件管理：文件的存取、共享和保護。●操作系統用作擴充機器功能，使其便于使用，這種只安裝了OS的機器又稱為虛擬機。5

操作系統的發展6無操作系統時的計算機系統1、

人工操作方式一臺計算機的所有資源由用戶獨占，降低了計算機資源利用率，人操作慢，出現了嚴重的人機矛盾。2、

脫機輸入輸出方式在外圍計算機的控制下，實現輸入輸出。主要解決了CPU與設備之間不匹配的矛盾7單道批處理系統1、在內存中僅存一道作業運行，運行結束或出錯，才自動調另一道作業運行。2、單道批處理系統主要特征：自動性、順序性、單道性。3、單道批處理系統主要優點：減少人工操作，解決了作業的自動接續。4、單道批處理系統主要缺點：平均周轉時間長，沒有交互能力。8多道批處理系統一、多道程序的概念：在內存中存放多道作業運行，運行結束或出錯，自動調度內存中的另一道作業運行。●多道程序帶來的好處：1、提高CPU的利用率。2、提高內存和I/O設備利用率。3、增加系統吞吐率。9二、多道批處理系統主要特征：多道性、無序性、調度性（進程調度和作業調度）。三、多道批處理的主要優點：提高了資源利用率和吞吐能力。多道批處理的主要缺點：平均周轉時間長，沒有交互能力。10例1．設在內存中有三道程序A、B和C，按A、B、C的優先次序運行，其內部計算和I／O操作時間由下圖給出。

若處理機調度程序每次進行狀態轉換需要的時間為1ms，試畫出按多道程序運行的時間關系圖。并計算完成這三道程序共使用了多少時間？并計算比單道運行節省多少時間？

BC11答：多道程序運行時間關系圖如下圖所示：由圖可計算出在多道程序運行下執行了196ms的時間，而在單道運行的時間為：30＋1+40＋1＋10＋1+60＋1＋30＋1＋16＋1+20＋1＋40＋1＋20＝274ms多道運行的時間為：30+1+40+1+10+1+20+1+30+1+40+1+20=196則多道程序比單道程序節省的時間為：

274一196＝78msA30B40A10B20C20B16C20CPUA40B30C40I/O12分時操作系統(time-sharingsystem)——70年代中期至今

“分時”的含義：分時是指多個用戶分享使用同一臺計算機。多個程序分時共享硬件和軟件資源。

分時(TimeSharing)操作系統的工作方式是：一臺主機連接了若干個終端，每個終端有一個用戶在使用。用戶交互式地向系統提出命令請求，系統接受每個用戶的命令，采用時間片輪轉方式處理服務請求，并通過交互方式在終端上向用戶顯示結果。用戶根據上步結果發出下道命。分時操作系統將CPU的時間劃分成若干個片段，稱為時間片。操作系統以時間片為單位，輪流為每個終端用戶服務。每個用戶輪流使用一個時間片而使每個用戶并不感到有別的用戶存在。

13

分時系統分時系統實現中的關鍵問題：及時接收：實現多個用戶的信息及時接收。及時處理：及時控制作業的運行。

14分時系統的特征：多路性：同時有多個用戶使用一臺計算機，宏觀上看是多個人同時使用一個CPU，微觀上是多個人在不同時刻輪流使用CPU。獨立性：用戶感覺不到計算機為其他人服務，就像整個系統為他所獨占。及時性：系統對用戶提出的請求及時響應。交互性：用戶根據系統響應結果進一步提出新請求(用戶直接干預每一步)。“影響響應時間的若干因素:

Ti=NQ+To.s+Twap改善響應時間的方法采用重入碼減少信息的對換量采用虛擬存儲技術,減少信息對換量15實時系統●所謂實時系統：是計算機及時響應外部事件的請求，在規定的時間內完成對該事件的處理，并控制所有實時設備和實時任務協調一致的運行。一、實時系統分為兩類

1、實時控制系統

2、實時信息處理系統二、實時任務的類型

1、按任務執行是否為周期性來劃分

2、按截止時間來劃分16

三、實時系統的特征

1、多路性：能對多個對象進行控制。

2、獨立性：獨立運行，不混淆，不破壞。

3、交互性：僅限于訪問系統中某些特定的專用服務程序。

4、可靠性：高可靠性，應具有過載防護能力。

5、及時性：不同的系統要求不一樣，控制對象必須在截止時間內完成。17操作系統的定義OS就是一個“大管家”，可以這樣去定義：是一組控制和管理計算機硬件和軟件資源、合理地對各類作業進行調度以及方便用戶的程序的集合。18操作系統的基本特征現代OS的四個基本特征：1、并發2、共享3、虛擬4、異步并發是最重要的特征，其它特征都以并發為前提。19并發并發——并行性和并發性，并發執行的過程。

-并行性是指兩個或多個事件在同一時刻發生。

-并發性是指兩個或多個事件在同一時間間隔內發生。任務共行

-從宏觀上看，任務共行是指系統中有多個任務同時運行

-從微觀上看，任務共行是指單處理機系統中的任務并發（TaskConcurrency：即多個任務在單個處理機上交替運行）或多處理機系統中的任務并行（TaskParallelism：即多個任務在多個處理機上同時運行）。20共享所謂共享是指系統中的資源可供內存中多個并發執行的進程共同使用。1、互斥共享方式：

-把在一段時間內只允許一個進程訪問的資源，稱為臨界資源。

-系統中的臨界資源可以提供給多個進程使用，但一次僅允許一個進程使用，稱為互斥共享方式。例如打印機。212、同時訪問方式：

-從宏觀上看，資源共享是指多個任務可以同時使用系統中的軟硬件資源

-從微觀上看，資源共享是指多個任務可以交替互斥地使用系統中的某個資源。例如磁盤。22虛擬所謂虛擬是指通過某種技術把一個物理實體變為若干個邏輯上的對應物。虛擬處理機：分時實現虛擬設備：SPOOLING技術虛擬存儲器：虛擬存儲管理實現23異步性異步性——是指進程以異步的方式執行，進程是以人們不可預知的速度向前推進。內存中的每個進程何時執行,何時暫停,以怎樣的速度向前推進,每道程序總共需要多少時間才能完成等,都是不可預知的

24操作系統的結構設計

操作系統是一個大型系統軟件，其結構已經歷了四代的變革：整體式結構、核心結構和層次結構。

25整體式結構是指將整個操作系統作為一個整體運行操作系統時，不能響應其他中斷。核心結構是指把操作系統分為外殼部分和核心部分。CPU在執行外殼部分時，可以響應其他中斷；而在執行核心部分時，禁止響應中斷。通常核心部分只是操作系統的一小部分，每次運行時間較短。核心部分通常包括進程控制和調度，進程的通信原語中斷和中斷處理，時鐘處理，外設驅動等。層次結構是把操作系統的功能分層，每層有明確的功能，提供接口與上下層聯系，上層軟件調用下層軟件提供的服務。對層次結構實現功能描述的另一種方法是把層次畫為同心圓，內層的環比外層的環有較高的特權，當外層環的過程調用內層環的過程時要進行嚴格的檢查。操作系統的核心和層次結構如圖所示。2627第二章

進程的描述與控制

28一、

相關概念

1、

前趨圖——有向無循環的圖。表示程序執行的偏序關系。

2、程序的順序執行——嚴格按照程序給定的順序執行，僅當前一個執行結束才執行后一個。

3、

程序的順序的特征：

①

順序性

②封閉性

③可再現性

4、程序的并發執行——是指兩個或兩個以上程序段在執行的時間上是重疊的，即使這種重疊只有一小部分，則稱這些程序為共行執行。295、程序并發執行的特征：

①間斷性

②失去封閉性

③不可再現性例2：若程序Pa、Pb和Pc單獨執行時間分別Ta、Tb和Tc

，Ta=1小時，Tb=1.5小時，Tc=2小時，其中處理機工作時間分別為Ta=10分鐘，Tb=15分鐘，Tc=35分鐘。如果采用多道程序設計的方法，讓Ta、Tb和Tc并行工作，假定處理機利用率達到60%，另加20分鐘系統開銷，請問系統效率能提高百分之幾？

30答：Ta、Tb和Tc并行工作共用CPU時間：（10+15+35）/60%=100Ta、Tb和Tc順序工作共用CPU時間：（60+90+120）=270系統效率提高：（270-（100+20））/270=150/270=55.5%31二、

進程的基本概念

1、進程的定義——可并發執行的程序在一個數據集合上的運行過程。（程序、數據、進程控制塊）

2、進程的基本特征

①

動態性

②

并發性

③

獨立性

④

異步性

⑤

交往性

3、

進程的基本狀態及其轉變32進程的三種基本狀態及其轉換

334、

進程控制塊——描述和控制進程運行，系統為每個進程定義的一個數據結構。5、進程控制塊的組織方式進程描述信息處理機狀態信息進程的調度信息進程的控制信息進程控制塊是操作系統最重要的數據結構，是進程存在的唯一標志。進程控制表。6、進程的掛起狀態

34三、

進程控制1、進程管理

進程圖：表明進程的創建關系，創建的進程和被創建的進程可以并發執行。2、引起進程創建的原因

①用戶登錄：為終端用戶建立進程。

②作業調度：選中的作業建立進程。

③提供服務：為用戶提供的服務進程。例如：I/O進程等。④

應用請求：應用程序自己創建的進程。3、原語：由若干條指令構成，用于完成一定功能的一個過程。不允許被中斷的程序段，不許并發執行。4、原子操作（原子性）：一個操作中的所有動作，要么全做，要么全不做。是一個不可分割的操作。35創建原語撤銷原語阻塞原語喚醒原語掛起與激活原語36

5、

線程的基本概念（1）

線程：一個被調度和分派的基本單位并可獨立運行的實體。（2）

線程分類：

①內核支持線程：依賴于內核進行控制和管理。

②用戶級線程：在用戶級創建、撤消和切換。（3）

在引入線程的OS中，則把線程作為調度和分派的基本單位，而把進程作為資源的擁有的基本單位。（4）

在同一進程中的線程切換不會引起進程切換。（5）在不同一進程中的線程切換會引起進程切換。

37

進程同步的基本概念1、

進程的相互制約

①間接相互制約——資源共享引起互斥關系

②

直接相互制約——相互合作引起進程同步2、

臨界資源：一次僅允許一個進程使用的資源稱為臨界資源。（排他性資源）3、臨界區：訪問臨界資源的那段代碼稱為臨界區。4、

同步機制應遵循的準則：

①空閑讓進——充分利用資源

②忙則等待——保證同步與互斥

③有限等待————防止陷入“死等”

④

讓權等待——防止陷入“忙等”

38

…

進入控制臨界區解除限制

…互斥的加鎖實現：臨界區有空閑和占有兩個狀態

whilelock=1doskiplock=1;

臨界區

lock=0;

借助硬件來實現39信號量機制

1、

經典信號量——表示資源的物理實體。

2、

記錄型信號量——更有效的利用資源，解決忙等的問題。

3、

AND型信號量機制——防止系統出現不安全性。

①

AND型信號量機制的概念化（見P72-6行或P43）

②Swait操作（SP操作）：（見P72或P43）

③

Ssignal操作（SV操作）：（見P72或P43）

4、

信號量應用實例

①互斥②前趨③同步40信號量為一個整數，我們設這個信號量為：sem。很顯然，我們規定在sem大于等于零的時候代表可供并發進程使用的資源實體數，sem小于零的時候，表示正在等待使用臨界區的進程的個數。根據這個原則，在給信號量附初值的時候，我們顯然就要設初值大于零。P原語操作的動作是：（1）sem減1；（2）若sem減1后仍大于或等于零，則進程繼續執行；（3）若sem減1后小于零，則該進程被阻塞后進入與該信號相對應的隊列中，然后轉進程調度。V原語操作的動作是：（1）sem加1；（2）若相加結果大于零，則進程繼續執行；（3）若相加結果小于或等于零，則從該信號的等待隊列中喚醒一等待進程，然后再返回原進程繼續執行或轉進程調度。需要提醒大家一點就是P,V操作對于每一個進程來說，都只能進行一次。而且必須成對使用。且在P,V愿語執行期間不允許有中斷的發生。41一、經典信號量（整型信號量）P操作Wait(s):whiles<=0dono-op;s:=s-1;

V操作signal(s):S:=s+1;42二、記錄型信號量讓權等待結構體：整形變量，進程鏈表Typesemaphore=recordvalue:integer;l:listofprocess;endWait(s):vars:semaphore;begins.value:=s.value-1;ifs.value<0thenblock(s.l)End43Signal(s):vars:semaphore;begins.value:=s.value+1;ifs.value<=0thenwakeup(s.l)end44信號量操作：

1)初始化

2)P操作

a)S--

b)if(S<0)在Q隊列中睡眠

else進入

3)V操作

a)S++

b)if(S<=0)喚醒一睡眠進程(等待隊列中有進程在睡眠)

else繼續

P操作可以理解為申請資源，V操作可以理解為釋放資源，45

利用信號量和PV操作實現進程互斥的一般模型是：進程P1

進程P2

……

進程Pn……

……

……P（S）；

P（S）；

P（S）；臨界區；

臨界區；

臨界區；V（S）；

V（S）；

V（S）；……

……

……

……

其中信號量S用于互斥，初值為1。

使用PV操作實現進程互斥時應該注意的是：（1）每個程序中用戶實現互斥的P、V操作必須成對出現，先做P操作，進臨界區，后做V操作，出臨界區。若有多個分支，要認真檢查其成對性。（2）P、V操作應分別緊靠臨界區的頭尾部，臨界區的代碼應盡可能短，不能有死循環。（3）互斥信號量的初值一般為1。

46

利用信號量和PV操作實現進程同步PV操作是典型的同步機制之一。用一個信號量與一個消息聯系起來，當信號量的值為0時，表示期望的消息尚未產生；當信號量的值非0時，表示期望的消息已經存在。用PV操作實現進程同步時，調用P操作測試消息是否到達，調用V操作發送消息。

使用PV操作實現進程同步時應該注意的是：

（1）分析進程間的制約關系，確定信號量種類。在保持進程間有正確的同步關系情況下，哪個進程先執行，哪些進程后執行，彼此間通過什么資源（信號量）進行協調，從而明確要設置哪些信號量。

（2）信號量的初值與相應資源的數量有關，也與P、V操作在程序代碼中出現的位置有關。

（3）同一信號量的P、V操作要成對出現，但它們分別在不同的進程代碼中。47【例1】生產者-消費者問題在多道程序環境下，進程同步是一個十分重要又令人感興趣的問題，而生產者-消費者問題是其中一個有代表性的進程同步問題。下面我們給出了各種情況下的生產者-消費者問題，深入地分析和透徹地理解這個例子，對于全面解決操作系統內的同步、互斥問題將有很大幫助。（1）一個生產者，一個消費者，公用一個緩沖區。定義兩個同步信號量：empty——表示緩沖區是否為空，初值為1。full——表示緩沖區中是否為滿，初值為0。48生產者進程while(TRUE){

生產一個產品;

P(empty);

產品送往Buffer;

V(full);

}消費者進程while(TRUE){

P(full);

從Buffer取出一個產品;

V(empty);

消費該產品;

}49（2）一個生產者，一個消費者，公用n個環形緩沖區。定義兩個同步信號量：empty——表示緩沖區是否為空，初值為n。full——表示緩沖區中是否為滿，初值為0。

設緩沖區的編號為1～n1，定義兩個指針in和out，分別是生產者進程和消費者進程使用的指針，指向下一個可用的緩沖區。50生產者進程while(TRUE){

生產一個產品;

P(empty);

產品送往buffer(in);

in=(in+1)modn;

V(full);

}消費者進程while(TRUE){P(full);

從buffer(out)中取出產品;

out=(out+1)modn;

V(empty);

消費該產品;

}

51（3）一組生產者，一組消費者，公用n個環形緩沖區

在這個問題中，不僅生產者與消費者之間要同步，而且各個生產者之間、各個消費者之間還必須互斥地訪問緩沖區。定義四個信號量：empty——表示緩沖區是否為空，初值為n。full——表示緩沖區中是否為滿，初值為0。mutex1——生產者之間的互斥信號量，初值為1。mutex2——消費者之間的互斥信號量，初值為1。

設緩沖區的編號為1～n1，定義兩個指針in和out，分別是生產者進程和消費者進程使用的指針，指向下一個可用的緩沖區。

52生產者進程while(TRUE){

生產一個產品;

P(empty);

P(mutex1);

產品送往buffer(in);

in=(in+1)modn;

V(mutex1);

V(full);

}消費者進程while(TRUE){P(full);

P(mutex2);

從buffer(out)中取出產品;

out=(out+1)modn;

V(mutex2);

V(empty);

消費該產品;

}

53需要注意的是無論在生產者進程中還是在消費者進程中，兩個P操作的次序不能顛倒。應先執行同步信號量的P操作，然后再執行互斥信號量的P操作，否則可能造成進程死鎖。

54【例2】桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果，也可向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規定當盤空時一次只能放一只水果供吃者取用，請用P、V原語實現爸爸、兒子、女兒三個并發進程的同步。分析在本題中，爸爸、兒子、女兒共用一個盤子，盤中一次只能放一個水果。當盤子為空時，爸爸可將一個水果放入果盤中。若放入果盤中的是桔子，則允許兒子吃，女兒必須等待；若放入果盤中的是蘋果，則允許女兒吃，兒子必須等待。本題實際上是生產者-消費者問題的一種變形。這里，生產者放入緩沖區的產品有兩類，消費者也有兩類，每類消費者只消費其中固定的一類產品。

解：在本題中，應設置三個信號量S、So、Sa，信號量S表示盤子是否為空，其初值為l；信號量So表示盤中是否有桔子，其初值為0；信號量Sa表示盤中是否有蘋果，其初值為0。同步描述如下：55intS＝1;intSa＝0;intSo＝0;

main()

{

cobegin

father();

/*父親進程*/

son();

/*兒子進程*/

daughter();

/*女兒進程*/

coend

}

father()

{

while(1)

{

P(S);

將水果放入盤中;

if（放入的是桔子）V(So);

else

V(Sa);

}

}

56son()

{

while(1)

{

P(So);

從盤中取出桔子;

V(S);

吃桔子;

}

}

daughter()

{

while(1)

{

P(Sa);

從盤中取出蘋果;

V(S);

吃蘋果;

}

}57四個進程A、B、C、D都要讀一個共享文件F，系統允許多個進程同時讀文件F。但限制是進程A和進程C不能同時讀文件F，進程B和進程D也不能同時讀文件F。為了使這四個進程并發執行時能按系統要求使用文件，現用PV操作進行管理，請回答下面的問題：

（1）應定義的信號量及初值：

。

（2）在下列的程序中填上適當的P、V操作，以保證它們能正確并發工作：

A()

B()

C()

D()

{

{

{

{

[1];

[3];

[5];

[7];

readF;

readF;

readF;

readF;

[2];

[4];

[6];

[8];

}

}

}

}

58（1）定義二個信號量S1、S2，初值均為1，即：S1=1，S2=1。其中進程A和C使用信號量S1，進程B和D使用信號量S2。（2）從[1]到[8]分別為：P(S1)V(S1)P(S2)V(S2)P(S1)V(S1)P(S2)V(S2)

59讀者-寫者問題-問題描述一個數據文件或記錄/數據對象，可以被多個進程共享。其中有些進程要求讀；而另一些進程要求對數據對象進行寫或修改。允許多個讀進程同時讀一個共享對象，但不允許寫進程與讀進程或其他寫進程同時訪問共享對象。所謂讀者—寫著問題(theReader-WriterProblem)是指保證寫進程必須與其他進程互斥地訪問共享對象的同步問題。該問題首先在1971年又Courtois等人解決。

60為實現Reader與Writer進程間在讀或寫時的互斥而設置了一個互斥信號量Wmutex。另外，再設置一個整型變量Readcount表示正在讀的進程數目。由于只要有一個Reader進程在讀，便不允許Writer進程去寫。因此，僅當Readcount=0，表示尚無Reader進程在讀時，Reader進程才需要執行Wait(Wmutex)操作。若wait(Wmutex)操作成功，Reader進程便可去讀，相應地，做Readcount+1操作。同理，僅當Reader進程在執行了Readcount減1操作后其值為0時，才須執行signal(Wmutex)操作，以便讓Writer進程寫。又因為Readcount是一個可被多個Reader進程訪問的臨界資源，因此，應該為它設置一個互斥信號量rmutex。61讀者-寫者問題可描述如下：varrmutex,wmutex:semaphore:=1,1;readcount:integer:=0;62哲學家進餐問題-問題描述有五個哲學家，他們的生活方式是交替地進行思考和進餐。哲學家們共用一張圓桌，分別坐在周圍的五張椅子上。在圓桌上有五個碗和五支筷子，平時哲學家進行思考，饑餓時便試圖取用其左、右靠他最近的筷子，只有當他拿到兩支筷子時才能進餐。進餐畢，放下筷子又繼續思考。經分析可知，放在桌子上的筷子是臨界資源，在一段時間內只允許一位哲學家使用。為了實現對筷子的互斥使用，可以用一個信號量表示一只筷子，由這五個信號量構成信號量數組。其描述如下varchopstick:array[0..4]ofsemaphore;

63所有信號量均被初始化為1，第i位哲學家的活動可描述為：repeatwait(chopstick[i]);wait(chopstick[(i+1)mod5]);eat;signal(chopstick[i]);signal(chopstick[(i+1)mod5]);think;untilfalse;

64上述解法可保證不會有兩個相鄰的哲學家同時進餐/互斥使用中間的筷子，但有引起死鎖的可能。可采取以下幾種解決方法：(1)至多只允許有四位哲學家同時去拿左邊的筷子，最終能保證至少有一位哲學家能夠進餐，并在用畢時能釋放出他用過的兩只筷子，從而使更多的哲學家能夠進餐。(2)僅當哲學家的左、右兩只筷子均可用時，才允許他拿起筷子進餐。(3)規定奇數號哲學家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數號哲學家則相反。按此規定，將是1、2號哲學家競爭1號筷子；3、4號哲學家競爭3號筷子。即五位哲學家都先競爭奇數號筷子，獲得后，再去競爭偶數號筷子，最后總會有一位哲學家能獲得兩只筷子而進餐。65在哲學家進餐問題中，要求每個哲學家先獲得兩個臨界資源(筷子)后方能進餐，這在本質上就是前面所介紹的AND同步問題，故用AND信號量機制可獲得最簡潔的解法。66三、AND型信號量機制死鎖67四、信號量集機制68管程機制信號量機制是一種方便而有效的進程同步機制，但每個要訪問臨界資源的進程須自備wait和signal操作。這樣不僅給系統管理造成麻煩，而且還會因同步操作使用不當而導致死鎖，甚至產生與時間有關的錯誤，例如：1、顛倒wait和signal操作導致臨界資源被同時訪問；2、signal誤寫為wait操作，導致任何進程無法訪問臨界資源，發生死鎖；3、遺漏wait操作會導致多個進程同時訪問臨界資源，遺漏signal則導致其他進程無法進入臨界區。基于以上情況，1971年DIjkstra提出了秘書“進程”機制。1973年Hansan和Hoare又講“秘書”進程思想發展為“管程”概念，把并發進程間的同步操作分別集中在相應的管程中。

69管程由三部分組成：①局部于管程的共享變量說明；②對該數據結構進行操作的一組過程；③對局部于管程的數據設置初始值的語句。此外，還須為管程賦予一個名字。7071條件變量在管程機制中，引起進程等待的原因可能很多，為了區別他們，有引入了條件變量condition。管程中對每個條件變量，都須予以說明，其形式為：Varx,y:condition。該變量應置于wait和signal之前，即可表示為X.wait和X.signal。例如，由于共享數據被占用而使調用進程等待，該條件變量的形式為：nonbusy:condition。此時，wait原語應改為nonbusy.wait，相應地，signal應改為nonbusy.signal。應當指出，X.signal操作的作用，是重新啟動一個被阻塞的進程，但如果沒有被阻塞的進程，則X.signal操作不產生任何后果。這與信號量機制中的signal操作不同。因為，后者總是要執行s:=s+1操作，因而總會改變信號量的狀態。72如果有進程Q處于阻塞狀態，當進程P執行了X.signal操作后，怎樣決定由哪個進行執行，哪個等待，可采用下述兩種方式之一進行處理：(1)P等待，直至Q離開管程或等待另一條件。(2)Q等待，直至P離開管程或等待另一條件。采用哪種處理方式，當然是各執一詞。但是Hansan卻采用了第一種處理方式。73利用管程解決PC問題-基本思想在利用管程方法來解決生產者-消費者問題時，首先便是為它們建立一個管程，并命名為Proclucer-Consumer，或簡稱為PC。其中包括兩個過程：(1)put(item)過程。生產者利用該過程將自己生產的產品投放到緩沖池中，并用整型變量count來表示在緩沖池中已有的產品數目，當count≥n時，表示緩沖池已滿，生產者須等待。(2)get(item)過程。消費者利用該過程從緩沖池中取出一個產品，當count≤0時，表示緩沖池中已無可取用的產品，消費者應等待74進程通信進程通信的類型：低級通信和高級通信

(1)高級通信方式：

①共享存儲器系統：共享數據結構、共享存儲器區通信方式

②消息傳遞系統：直接通信方式——通過收發原語間接通信方式——通過信箱實現信息交換

③管道通信（2）管道通信具有三方面的協調能力：

①雙方同時存在

②

同步關系

③

互斥使用管道75第三章

調度與死鎖一、調度的類型

1、高級調度

2、

低級調度：非搶占式、搶占式搶占式：時間片原則、優先權原則、短作業優先原則

3、

中級調度76二、

面向用戶的準則1、

周轉時間短：平均周轉時間、平均帶權周轉時間2、

響應時間快3、

截止時間的保證4、

優先權準則

77三、面向系統的準則1、

系統的吞吐量2、

CPU的利用率好3、

各類資源平衡使用78調度的算法1、

先來先服務調度的算法2、

短作業優先調度的算法3、

時間片輪轉調度的算法（分時）或簡單輪轉調度的算法4、

優先權調度的算法：非搶占式、搶占式

①靜態優先權

②動態優先權795、

響應比高者優先調度的算法：

RP=1+等待時間/服務時間6、多級隊列調度算法：例如，前臺、后臺7、多級反饋隊列調度算法（見P108或P80）

實時系統的調度算法

在實時系統中，廣泛采用搶占式調度方式80

死鎖的基本概念1、

何謂死鎖？（見P119或P90）2、

產生死鎖原因：

①

競爭資源

②

推進順序不當3、

產生死鎖的必要條件

①互斥

②請求和保持

③不剝奪

④環路等待條件

81

4、

處理死鎖的基本方法

①

預防死鎖：設置某些限制條件，破壞四個條件。

②

避免死鎖：資源動態分配，防止進入不安全狀態。

③

檢測死鎖：設置檢查機構，定時檢查系統是否出現死鎖。

④解除死鎖：已出現死鎖。

82例.

假定系統中有五個進程{P0，P1，P2，P3，P4}和三類資源{A，B，C}，每一種資源的數量分別為10、5、7，在T0時刻的資源分配情況如下圖所示。在此基礎上P0進程發出請求向量{1，2，0}，問系統是否能將資源分配給P0進程？如能為P0分配資源則給出安全系列，否則給出解除死鎖的方法。

進程MaxABCAllocationABCNeedABCAvailableABCP0753010743332P1322200122

P2902302600

P3222211011

P4433002431

83安全P3(1)->p1(2)->p0(3)->p2(4)->p4(5)

進程MaxABCAllocationABCNeedABCAvailableABCP0753130

62312(3)753P1321200122(2)623

P2902302600

(4)1055P3222211011(1)

423P4433002431(5)1057

84第四章

存儲器管理

85

一、程序的裝入

1、絕對裝入方式直接用物理地址編制程序。

2、可重定位裝入方式（靜態重定位）

重定位——把在裝入時對目標程序中的指令和數據地址的修改過程稱為重定位。

3、動態運行時裝入方式（動態重定位）

作業在存儲空間的位置，也是裝入時確定的，但在作業運行過程中，每次存訪內存之前，將程序的地址（邏輯地址）變為內存的物理地址。這種變換是依靠硬件地址變換機構、自動連續實施，這樣程序在內存的地址是可變的，可申請臨時空間。86二、程序的鏈接

1、

靜態鏈接——事先進行鏈接，以后不再拆開的鏈接方式，稱為靜態鏈接。

2、

裝入時動態鏈接——編譯后的目標模塊，是在裝入內存時，邊裝入，邊鏈接的。

3、運行時動態鏈接——將某些目標模塊的鏈接推遲到執行時才進行，即在執行過程中，若發現一個被調用模塊尚未裝入內存時，再由操作系統去找到該模塊，將它裝入內存，并把它鏈接到調用者模塊上。

4、靜態鏈接需要共享目標模塊的拷貝，而動態鏈接不需要共享目標模塊的拷貝。87三、連續分配存儲管理方式

1、

固定式分區

2、

動態分區分配——根據用戶實際需要，動態的分配連續空間。

l拼接技術

3、

動態重定位分區分配——采用動態重定位技術的分區分配。

l

緊湊技術88四、分區管理的算法1、

首次適應算法：每個空白區按地址順序鏈接在一起，表頭指向第一個空白區。2、

循環首次適應算法：將空白區構成循環鏈表。表頭指向當前開始查找的第一個空白區。3、

最佳適應算法：空白區按尺寸大小遞增順序構成隊列。表頭指向第一個空白區。89五、對換技術

（交換技術）

就是將主存中的信息以文件的形式寫入到輔存，接著將指定的信息從輔存讀入主存，并將控制轉給它，讓其在系統上運行。90六、分頁存儲器管理1、在分頁存儲管理方式中，一個進程的邏輯地址空間分成若干個大小相等的片，稱為頁面。內存空間也分成與頁相同大小的存儲塊，并將進程的每一個頁面離散地存儲在內存的任一物理塊中，建立相應的頁表，由系統實現進程的正確運行。2、快表——為了提高地址變換速度，可在地址變換機構中，增設一個具有并行查尋能力的特殊高速緩沖存儲器，稱為快表。91

例：有一頁式系統，其頁表存放在主存中：①如果對主存的一次存取需要1.5μs,試問實現一次頁面訪問的存取時間是多少?②如果系統加有快表,平均命中率為85%,當頁表項在快表中時,其查找時間忽略為0,

試問此時的存取時間是多少?92答：若頁表存放在主存中，則要實現一次頁面訪問需兩次訪問主存：一次是訪問頁表，確定所存取頁面的物理地址（稱為定位）。第二次才根據該地址存取頁面數據。■頁表在主存的存取訪問時間

=1.5*2=3(μs)■增加快表后的存取訪問時間

=0.85*1.5+(1-0.85)*2*1.5=1.725(μs)93七、分段存儲管理①在分段存儲管理方式中，一個作業的地址空間分成若干個段，每一段定義了一組邏輯信息，則為每個段分配連續的分區，而進程中的各段可以離散地存儲在內存中不同的分區中，建立相應的段表，由系統實現進程的正確運行。

②分頁與分段存儲管理的區別？答：P160或P12194八、段頁式管理（1）

基本思想（見P162或P123）（2）地址變換機構（見P164或P124）95虛擬存儲管理1、

虛擬存儲器的概念？

使用虛擬存儲管理技術，用戶將會感覺到系統的內存空間比實際內存大。系統的可用內存空間并非計算機系統中的實際物理內存，它包含物理內存及一部分磁盤空間。習慣上，人們把這種用戶感覺上存在但實際上并不存在的內存稱為虛擬內存。962、

請求分頁存儲管理方式基本思想

在請求分頁存儲管理方式中，不限定把進程的整個地址空間全部裝入主存，而只要求把當前需要的一部分裝入主存，由系統實現進程的正確運行，其它的頁面當需要時才去調用。這樣實現了主存的“擴充”。地址變換機構（見P170或P129）頁面的管理：

①頁面調入策略

●請求式調頁

●預先調頁97②頁面置換算法：

●FIFO

例如,P175或P134

●最近最久不用頁面置換算法LRU

例如,(P176或P135)●簡單的Clock置換算法例如,(P178或P136)3、系統抖動？（P183-18行）983、

請求分段存儲管理方式（1）

基本思想

在請求分段存儲管理方式中，把作業的所有分段的副本保存在輔存中，當其運行時，只要求把當前需要的一段或數段裝入主存，其它的段當需要時才裝入，由系統實現進程的正確運行。這樣實現了主存的“擴充”。（2）地址變換機構（見P186或P139）

●分段保護：越界檢查（段長值）存取控制檢查99例1.頁式系統中地址結構長度為24位，頁面大小為1K，作業地址空間為5K，該作業的各頁依次存放在2,9,7,5,11號物理塊中,相對地址2000處有一條指令Store1,4500，請給出該作業的頁表，該指令的物理單元和數據存放的物理單元。頁號幀號021927354112000對應為111，1101，0000物理單元為：100111，1101，0000即：1024×9＋976＝101924500對應為：1024×11+404100例2.在一個請求頁式存儲系統中，一個程序的頁面走向為4，3，2，1，4，3，5，4，3，2,1，5，并采用LRU頁面置換算法。假設分配給該程序的存儲塊數M分別為3和4時，求出在防問過程中發生的缺頁次數和缺率，比較所得結果，從中得到什么啟發？101第五章

設備管理一、

I/O系統的組成

1、I/O系統的結構102（1）

設備①獨占設備——在一段時間內只允許一個用戶訪問的設備。②共享設備——在一段時間內允許多個用戶訪問的設備。③

虛擬設備——將一臺獨占物理設備變換為若干臺邏輯設備。103（2）設備控制器①是CPU與I/O設備之間的接口，它接收從CPU發來的命令，并控制I/O設備工作。②設備控制器是可編址設備。當用于控制多臺設備時，則具有多個地址。104（3）通道

●通道控制方式的引入①DMA方式顯著地減少了CPU的干預。②當CPU要完成一組相關的讀（或寫）操作及有關控制時，只需向I/O通道發送一條I／O指令。③通道接到該指令后，通過執行通道程序便可完成CPU指定的I／O任務。④可實現CPU、通道和I／O設備三者的并行操作，從而更有效地提高整個系統的資源利用率。⑤而當我們需要一次去讀多個數據塊且將它們分別傳送到不同的內存區域，或者相反時；則須由CPU分別發出多條I／O指令及進行多次中斷處理，才能完成。105●通道分類：①字節多路通道106②數組選擇通道——按數組方式進行數據傳送，但在一段時間內只能為一臺設備占用，執行一道通道程序。③數組多路通道——按數組方式進行數據傳送，但能為多臺設備占用，高速的進行數據傳送。107二、

I/O控制方式1、程序I/O方式（查詢方式）(P203或P151）2、中斷驅動方式(P203或P152）3、DMA方式(P203或P153）4、I/O通道控制方式方式(P203或P154）

通道是通過執行通道程序，并與設備控制器共同實現對I／O設備的控制的。通道程序是由一系列通道指令（或稱為通道命令）所構成的。通道又稱為特殊的處理機。108三、

緩沖管理●

引入緩沖原因（見P207或P155）（1）緩和CPU與I／O設備間速度不匹配的矛盾。

（2）減少對CPU的中斷頻率，放寬對CPU中斷響應時間的限制。（3）提高CPU和I／O設備之間的并行性。

例如：

單緩沖、

雙緩沖、

循環緩沖、

緩沖池緩沖技術是以空間換取時間，而且只能在設備使用不均衡時起到平滑作用。109

四、

設備分配設備管理是通過一些數據結構來實現對其設備進行管理和控制的。1。

設備控制表、通道控制表、系統設備表、控制器控制表2、設備分配中應考慮的若干因素（1）設備的固有屬性：獨享設備、共享設備、虛擬設備

（2）設備的分配算法：FIFO、優先級高者優先（3）設備分配中的安全性3、設備固有屬性不同，其分配算法不同4、SPOOLING技術可將一臺物理設備虛擬為多臺邏輯設備，可為多個用戶所共享。

SPOOLing技術的核心思想是：在快速輔助存儲設備中建立I/O緩沖區用于緩存從慢速輸入設備流入內存的數據或緩存從內存流向慢速輸出設備的數據。110五、設備處理1、設備處理程序又稱為設備驅動程序，它是I/O進程與設備控制器之間的通信程序。

①初始化I/O設備

②

設備與進程之間的數據傳送

③

當數據傳完之后，將產生中斷信號將它換醒，進入中斷處理過程。2、中斷處理過程（見P224或P171）3、用戶請求設備使用的是邏輯設備名。由系統通過邏輯設備表實現邏輯設備到物理設備的映射。當更換物理設備時，用戶的程序不用改，僅修改邏輯設備表。111磁盤存儲器管理一、

早期磁盤調度算法

1、

先來先服務（見P261或P174）

2、

最短尋道時間優先（見P261或P174

3、

掃描法（見P262或P175）

4、

循環掃描法（見P262或P175）

112第六章

文件系統113

一、

文件和文件系統的基本概念

1、

數據項——>記錄——>文件（見P228或P182圖）

2、

文件系統模型（見P229或P184圖）

3、

文件的操作（見P231或P185）

二、文件邏輯結構

1、

順序文件（見P234或P187）

優點：可以快速實現批量存取，可存儲在磁帶上缺點：增刪困難

2、

索引文件（見P235或P189）

優點：實現直接存取、快速缺點：增加空間開銷

114三、

外存分配方法1.

連續分配——將文件信息存放在連續編號的物理塊中。（見P264圖9-6或P192）

優點：結構簡單，存取速度快。

缺點：長度事先確定，隨后不允許增加長度。2、

鏈接分配——將文件信息存放在非連續編號的物理塊中。(見P265圖9-7或P194）

優點：插入、刪除方便，文件長度可變。

缺點：查找困難。3、

索引分配（見P267、圖9-10或P195）

優點：可以隨機存取。

缺點：增加空間的開銷。115四、

目錄管理

1、

對文件目錄管理要求（見P236或P198）

2、

文件控制塊與文件目錄（見P237或P198）

3、

單級文件目錄（見P239或P201）

缺點：查找速度慢、不允許重名、不便于實現文件共享

4、

兩級目錄和多級目錄（見P240或P201）

l

當前目錄——工作目錄

l

優點：

①檢查速度快

②

不同目錄可以重名

③

不同用戶可使用不同名字，來訪問系統中的同一個共享文件。116●索引結點的引入在檢索目錄文件的過程中，只用到了文件名，僅當找到一個目錄項（即其中的文件名與指定要查找的文件名相匹配）時，才需從該目錄項中讀出該文件的物理地址。而其它一些對該文件進行描述的信息，在檢索目錄時一概不用，顯然，這些信息在檢索目錄時，不需調入內存。為此，在有的系統中，如UNIX系統，便采用了把文件名與文件描述信息分開的辦法，亦即，使文件描述信息單獨形成一個稱為索引結點的數據結構，簡稱為i結點。在文件目錄中的每個目錄項，僅由文件名和指向該文件所對應的i結點的指針所構成。

117

五、空閑存儲空間的管理方法

1、空閑表法（見P270或P205）

2、空閑鏈表法（見P271或P206）

3、位示圖法（見P271或P206）

4、成組鏈接法（見P272、或P207）118第七章

操作系統接口

119

用戶與操作系統的接口

操作系統

用戶處理結果輸出返回命令接口圖形接口程序接口120

●用戶接口可以多種形式呈現在用戶面前：①一種是聯機命令形式，直接提供給用戶在終端上使用；②一種是系統調用形式，提供給用戶在編程時使用。人們通常把上述兩種形式分別稱為聯機命令接口和程序接口。一、

命令接口

命令接口由

命令解釋程序對用戶鍵入的命令進行解釋，并轉入相應的命令處理程序去執行。二、

程序接口

1、系統調用——就是用戶在程序中調用操作系統所提供的一些子功能。

2、系統調用在本質上是應用程序請求OS內核完成某功能時的一種過程調用，但它是一種特殊的過程調用，它與一般的過程調用有下述幾方面的明顯差別：

121（1）運行在不同的系統狀態。一般的過程調用，其調用程序和被調用程序都運行在相同的狀態——系統態或用戶態；而系統調用與一般調用的最大區別就在于：調用程序是運行在用戶態，而被調用程序是運行在系統態。（2）通過軟中斷進入。由于一般的過程調用并不涉及到系統狀態的轉換，故可直接由調用過程轉向被調用過程。但在運行系統調用時，由于調用和被調用過程是工作在不同的系統狀態，因而不允許由調用過程直接轉向被調用過程。通常都是通過軟中斷機制（既訪管指令），先由用戶態轉換為系統態，經核心分析后，才能轉向相應的系統調用處理子程序。122（3）返回問題。在采用了搶占式（剝奪）調度方式的系統中，在被調用過程執行完后，要對系統中所有要求運行的進程做優先權分析。當調用進程仍具有最高優先級時，才返回到調用進程繼續執行；否則，將引起重新調度，以便讓優先權最高的進程優先執行。此時，將把調用進程放入就緒隊列。（4）嵌套調用。系統調用也可以嵌套進行，即在一個被調用過程的執行期間，還可以利用系統調用命令去調用另一個系統調用。當然，每個系統對嵌套調用的深度都有一定的限制，例如最大深度為6。

123三、

圖形用戶接口

①窗口是作為用戶與應用程序之間的交互接口

②應用程序可通過窗口向用戶展示系統所提供的各種服務及其需要用戶輸入的信息。

③用戶可通過窗口去查看和操作應用程序或文檔。

124研究生入學試題分析125

2000年操作系統入學試題

一、

單選題（每小題1分，共7分）1、線程是進程的實體，意味著（）

①線程在進程中是唯一的

②線程可以使用進程中的資源

③線程在運行中不能中斷

④在同一進程中的多個線程具有不同的地址空間

2、檢測死鎖的算法是在（）

①程序中申請資源時使用②死鎖出現之后使用

③死鎖即將出現時使用 ④定時檢查系統狀態時使用

3、在下列問題中，哪一個不是設備中應考慮的問題（）

①設備的固有屬性 ②與設備無關性

③安全性 ④及時性1264、在下列哪一個不是外存分配方式（）

①連續分配 ②鏈接分配

③互斥分配 ④索引分配5、聯想存儲器就是（）

①快表 ②頁表 ③段表 ④內存

6、磁盤為共享設備的主要原因是（）

①多個用戶可同時訪問磁盤

②磁盤空間可讓多個用戶共享

③磁盤可支持SPOOLING技術

④磁盤有多個磁頭7、指出以下非臨界資源（）

①變量②數據結構

③隊列④純代碼127二、填空題（每小題1分，共6分）1、用戶與操作系統的接口是：____和_______________。2、多處理機有兩種結構：_____和________.3、I/O控制方式________，____和________。4、產生死鎖的原因：______和_________。5、文件保護的方法有：_______，_________和___________。6、用于磁盤的主要調度算法有：__________，____________和____________。128

三、

判斷改錯題（每小題2分，共16分）

1、（ ）緩沖技術是以空間換時間，而且只能在設備使用均衡時起到平滑作用。

2、（ ）動態重定位與裝入時動態鏈接在概念上是相同的。

3、（ ）在分時系統中采用虛擬存儲技術可以改善響應時間。

4、（ ）在現代的分時系統中，邏輯處理機隱含了虛擬處理機的功能。

5、（ ）獨享設備與共享設備的屬性不同，其共享方式也不同。129

6、（ ）采用AND型信號量機制是為了防止系統的不安全。

7、（ ）如果一個站點既可以作為客戶，又可以作為服務器向其它站點提供服務，稱為客戶/服務器模式。

8、（ ）設備處理程序是I/O進程與設備控制器之間的通信程序。

130四、問答題（每小題7分，共21分）1、

為什么在頁式存儲管理中實現程序共享時，必須對共享程序給出相同的頁號，而段式存儲管理系統中實現程序共享時，共享段的段號是否一定要相同？如相同，為什么相同？如不相同，為什么不相同？131進程到達就緒隊列的時間執行時間P118P224P339P4452、

假定一個操作系統的進程調度采用搶占式短進程優先調度策略（單CPU），系統中各進程到達的時間如下表所示。請給出各進程的調度次序，并計算平均周轉時間和平均代權周轉時間。注：表中的時間均為基本單位時間。1320102030p1p2p3p418-1=176-2=427-3=2411-4=7133

2001年操作系統入學試題一、單項選擇題（每小題1分，共10分）

1.進程被阻塞以后，代表進程在阻塞隊列的是它的(

)

①文件控制塊②進程控制塊

③作業控制塊④設備控制塊

2.在以下哪種狀態下，作業已獲得虛處理機。（） ①提交狀態