uestc操作系統(tǒng)指導(dǎo)教案

操作系統(tǒng)輔導(dǎo)

湯子贏、哲風(fēng)屏、湯小丹

1第一章操作系統(tǒng)引論

操作系統(tǒng)的目標(biāo)、作用和模型l

操作系統(tǒng)——是裸機(jī)上的第一層軟件，它是對硬件系統(tǒng)功能的首次擴(kuò)充，是填補(bǔ)人與機(jī)器之間的鴻溝。用戶計(jì)算機(jī)OS2

操作系統(tǒng)的目標(biāo)●

設(shè)置操作系統(tǒng)的目的：

1、方便性:操作系統(tǒng)使計(jì)算機(jī)更易于使用

2、有效性:操作系統(tǒng)允許以更有效的方式使用計(jì)算機(jī)系統(tǒng)資源。

3、可擴(kuò)展性:在操作系統(tǒng)中,允許有效地開發(fā)，測試和引進(jìn)新的系統(tǒng)功能。

4、開放性:實(shí)現(xiàn)應(yīng)用程序的可移植性和互操作性,要求具有統(tǒng)一的開放的環(huán)境。3

OS的作用●計(jì)算機(jī)用戶需要的用戶命令由OS實(shí)現(xiàn)的所有用戶命令所構(gòu)成的集合常被人們稱為OS的Interface(用戶接口)；有時(shí)也稱為命令接口。

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

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

圖形形式：因直觀而易記但不靈活。●應(yīng)用軟件需要的SystemCall(系統(tǒng)調(diào)用)

由OS實(shí)現(xiàn)的所有系統(tǒng)調(diào)用所構(gòu)成的集合被人們稱為程序接口或應(yīng)用編程接口(ApplicationProgrammingInterface,API)。4●操作系統(tǒng)作為計(jì)算機(jī)系統(tǒng)資源管理者。1、處理機(jī)管理：分配和控制CPU。2、存儲器管理：內(nèi)存分配與回收。3、I/O設(shè)備管理：I/O設(shè)備的分配與操縱。4、文件管理：文件的存取、共享和保護(hù)?！癫僮飨到y(tǒng)用作擴(kuò)充機(jī)器功能，使其便于使用，這種只安裝了OS的機(jī)器又稱為虛擬機(jī)。5

操作系統(tǒng)的發(fā)展6無操作系統(tǒng)時(shí)的計(jì)算機(jī)系統(tǒng)1、

人工操作方式一臺計(jì)算機(jī)的所有資源由用戶獨(dú)占，降低了計(jì)算機(jī)資源利用率，人操作慢，出現(xiàn)了嚴(yán)重的人機(jī)矛盾。2、

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

若處理機(jī)調(diào)度程序每次進(jìn)行狀態(tài)轉(zhuǎn)換需要的時(shí)間為1ms，試畫出按多道程序運(yùn)行的時(shí)間關(guān)系圖。并計(jì)算完成這三道程序共使用了多少時(shí)間？并計(jì)算比單道運(yùn)行節(jié)省多少時(shí)間？

BC11答：多道程序運(yùn)行時(shí)間關(guān)系圖如下圖所示：由圖可計(jì)算出在多道程序運(yùn)行下執(zhí)行了196ms的時(shí)間，而在單道運(yùn)行的時(shí)間為：30＋1+40＋1＋10＋1+60＋1＋30＋1＋16＋1+20＋1＋40＋1＋20＝274ms多道運(yùn)行的時(shí)間為：30+1+40+1+10+1+20+1+30+1+40+1+20=196則多道程序比單道程序節(jié)省的時(shí)間為：

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

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

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

13

分時(shí)系統(tǒng)分時(shí)系統(tǒng)實(shí)現(xiàn)中的關(guān)鍵問題：及時(shí)接收：實(shí)現(xiàn)多個用戶的信息及時(shí)接收。及時(shí)處理：及時(shí)控制作業(yè)的運(yùn)行。

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

Ti=NQ+To.s+Twap改善響應(yīng)時(shí)間的方法采用重入碼減少信息的對換量采用虛擬存儲技術(shù),減少信息對換量15實(shí)時(shí)系統(tǒng)●所謂實(shí)時(shí)系統(tǒng)：是計(jì)算機(jī)及時(shí)響應(yīng)外部事件的請求，在規(guī)定的時(shí)間內(nèi)完成對該事件的處理，并控制所有實(shí)時(shí)設(shè)備和實(shí)時(shí)任務(wù)協(xié)調(diào)一致的運(yùn)行。一、實(shí)時(shí)系統(tǒng)分為兩類

1、實(shí)時(shí)控制系統(tǒng)

2、實(shí)時(shí)信息處理系統(tǒng)二、實(shí)時(shí)任務(wù)的類型

1、按任務(wù)執(zhí)行是否為周期性來劃分

2、按截止時(shí)間來劃分16

三、實(shí)時(shí)系統(tǒng)的特征

1、多路性：能對多個對象進(jìn)行控制。

2、獨(dú)立性：獨(dú)立運(yùn)行，不混淆，不破壞。

3、交互性：僅限于訪問系統(tǒng)中某些特定的專用服務(wù)程序。

4、可靠性：高可靠性，應(yīng)具有過載防護(hù)能力。

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

-并行性是指兩個或多個事件在同一時(shí)刻發(fā)生。

-并發(fā)性是指兩個或多個事件在同一時(shí)間間隔內(nèi)發(fā)生。任務(wù)共行

-從宏觀上看，任務(wù)共行是指系統(tǒng)中有多個任務(wù)同時(shí)運(yùn)行

-從微觀上看，任務(wù)共行是指單處理機(jī)系統(tǒng)中的任務(wù)并發(fā)（TaskConcurrency：即多個任務(wù)在單個處理機(jī)上交替運(yùn)行）或多處理機(jī)系統(tǒng)中的任務(wù)并行（TaskParallelism：即多個任務(wù)在多個處理機(jī)上同時(shí)運(yùn)行）。20共享所謂共享是指系統(tǒng)中的資源可供內(nèi)存中多個并發(fā)執(zhí)行的進(jìn)程共同使用。1、互斥共享方式：

-把在一段時(shí)間內(nèi)只允許一個進(jìn)程訪問的資源，稱為臨界資源。

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

-從宏觀上看，資源共享是指多個任務(wù)可以同時(shí)使用系統(tǒng)中的軟硬件資源

-從微觀上看，資源共享是指多個任務(wù)可以交替互斥地使用系統(tǒng)中的某個資源。例如磁盤。22虛擬所謂虛擬是指通過某種技術(shù)把一個物理實(shí)體變?yōu)槿舾蓚€邏輯上的對應(yīng)物。虛擬處理機(jī)：分時(shí)實(shí)現(xiàn)虛擬設(shè)備：SPOOLING技術(shù)虛擬存儲器：虛擬存儲管理實(shí)現(xiàn)23異步性異步性——是指進(jìn)程以異步的方式執(zhí)行，進(jìn)程是以人們不可預(yù)知的速度向前推進(jìn)。內(nèi)存中的每個進(jìn)程何時(shí)執(zhí)行,何時(shí)暫停,以怎樣的速度向前推進(jìn),每道程序總共需要多少時(shí)間才能完成等,都是不可預(yù)知的

24操作系統(tǒng)的結(jié)構(gòu)設(shè)計(jì)

操作系統(tǒng)是一個大型系統(tǒng)軟件，其結(jié)構(gòu)已經(jīng)歷了四代的變革：整體式結(jié)構(gòu)、核心結(jié)構(gòu)和層次結(jié)構(gòu)。

25整體式結(jié)構(gòu)是指將整個操作系統(tǒng)作為一個整體運(yùn)行操作系統(tǒng)時(shí)，不能響應(yīng)其他中斷。核心結(jié)構(gòu)是指把操作系統(tǒng)分為外殼部分和核心部分。CPU在執(zhí)行外殼部分時(shí)，可以響應(yīng)其他中斷；而在執(zhí)行核心部分時(shí)，禁止響應(yīng)中斷。通常核心部分只是操作系統(tǒng)的一小部分，每次運(yùn)行時(shí)間較短。核心部分通常包括進(jìn)程控制和調(diào)度，進(jìn)程的通信原語中斷和中斷處理，時(shí)鐘處理，外設(shè)驅(qū)動等。層次結(jié)構(gòu)是把操作系統(tǒng)的功能分層，每層有明確的功能，提供接口與上下層聯(lián)系，上層軟件調(diào)用下層軟件提供的服務(wù)。對層次結(jié)構(gòu)實(shí)現(xiàn)功能描述的另一種方法是把層次畫為同心圓，內(nèi)層的環(huán)比外層的環(huán)有較高的特權(quán)，當(dāng)外層環(huán)的過程調(diào)用內(nèi)層環(huán)的過程時(shí)要進(jìn)行嚴(yán)格的檢查。操作系統(tǒng)的核心和層次結(jié)構(gòu)如圖所示。2627第二章

進(jìn)程的描述與控制

28一、

相關(guān)概念

1、

前趨圖——有向無循環(huán)的圖。表示程序執(zhí)行的偏序關(guān)系。

2、程序的順序執(zhí)行——嚴(yán)格按照程序給定的順序執(zhí)行，僅當(dāng)前一個執(zhí)行結(jié)束才執(zhí)行后一個。

3、

程序的順序的特征：

①

順序性

②封閉性

③可再現(xiàn)性

4、程序的并發(fā)執(zhí)行——是指兩個或兩個以上程序段在執(zhí)行的時(shí)間上是重疊的，即使這種重疊只有一小部分，則稱這些程序?yàn)楣残袌?zhí)行。295、程序并發(fā)執(zhí)行的特征：

①間斷性

②失去封閉性

③不可再現(xiàn)性例2：若程序Pa、Pb和Pc單獨(dú)執(zhí)行時(shí)間分別Ta、Tb和Tc

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

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

進(jìn)程的基本概念

1、進(jìn)程的定義——可并發(fā)執(zhí)行的程序在一個數(shù)據(jù)集合上的運(yùn)行過程。（程序、數(shù)據(jù)、進(jìn)程控制塊）

2、進(jìn)程的基本特征

①

動態(tài)性

②

并發(fā)性

③

獨(dú)立性

④

異步性

⑤

交往性

3、

進(jìn)程的基本狀態(tài)及其轉(zhuǎn)變32進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換

334、

進(jìn)程控制塊——描述和控制進(jìn)程運(yùn)行，系統(tǒng)為每個進(jìn)程定義的一個數(shù)據(jù)結(jié)構(gòu)。5、進(jìn)程控制塊的組織方式進(jìn)程描述信息處理機(jī)狀態(tài)信息進(jìn)程的調(diào)度信息進(jìn)程的控制信息進(jìn)程控制塊是操作系統(tǒng)最重要的數(shù)據(jù)結(jié)構(gòu)，是進(jìn)程存在的唯一標(biāo)志。進(jìn)程控制表。6、進(jìn)程的掛起狀態(tài)

34三、

進(jìn)程控制1、進(jìn)程管理

進(jìn)程圖：表明進(jìn)程的創(chuàng)建關(guān)系，創(chuàng)建的進(jìn)程和被創(chuàng)建的進(jìn)程可以并發(fā)執(zhí)行。2、引起進(jìn)程創(chuàng)建的原因

①用戶登錄：為終端用戶建立進(jìn)程。

②作業(yè)調(diào)度：選中的作業(yè)建立進(jìn)程。

③提供服務(wù)：為用戶提供的服務(wù)進(jìn)程。例如：I/O進(jìn)程等。④

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

5、

線程的基本概念（1）

線程：一個被調(diào)度和分派的基本單位并可獨(dú)立運(yùn)行的實(shí)體。（2）

線程分類：

①內(nèi)核支持線程：依賴于內(nèi)核進(jìn)行控制和管理。

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

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

在同一進(jìn)程中的線程切換不會引起進(jìn)程切換。（5）在不同一進(jìn)程中的線程切換會引起進(jìn)程切換。

37

進(jìn)程同步的基本概念1、

進(jìn)程的相互制約

①間接相互制約——資源共享引起互斥關(guān)系

②

直接相互制約——相互合作引起進(jìn)程同步2、

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

同步機(jī)制應(yīng)遵循的準(zhǔn)則：

①空閑讓進(jìn)——充分利用資源

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

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

④

讓權(quán)等待——防止陷入“忙等”

38

…

進(jìn)入控制臨界區(qū)解除限制

…互斥的加鎖實(shí)現(xiàn)：臨界區(qū)有空閑和占有兩個狀態(tài)

whilelock=1doskiplock=1;

臨界區(qū)

lock=0;

借助硬件來實(shí)現(xiàn)39信號量機(jī)制

1、

經(jīng)典信號量——表示資源的物理實(shí)體。

2、

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

3、

AND型信號量機(jī)制——防止系統(tǒng)出現(xiàn)不安全性。

①

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

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

③

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

4、

信號量應(yīng)用實(shí)例

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

V操作signal(s):S:=s+1;42二、記錄型信號量讓權(quán)等待結(jié)構(gòu)體：整形變量，進(jìn)程鏈表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隊(duì)列中睡眠

else進(jìn)入

3)V操作

a)S++

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

else繼續(xù)

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

利用信號量和PV操作實(shí)現(xiàn)進(jìn)程互斥的一般模型是：進(jìn)程P1

進(jìn)程P2

……

進(jìn)程Pn……

……

……P（S）；

P（S）；

P（S）；臨界區(qū)；

臨界區(qū)；

臨界區(qū)；V（S）；

V（S）；

V（S）；……

……

……

……

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

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

46

利用信號量和PV操作實(shí)現(xiàn)進(jìn)程同步PV操作是典型的同步機(jī)制之一。用一個信號量與一個消息聯(lián)系起來，當(dāng)信號量的值為0時(shí)，表示期望的消息尚未產(chǎn)生；當(dāng)信號量的值非0時(shí)，表示期望的消息已經(jīng)存在。用PV操作實(shí)現(xiàn)進(jìn)程同步時(shí)，調(diào)用P操作測試消息是否到達(dá)，調(diào)用V操作發(fā)送消息。

使用PV操作實(shí)現(xiàn)進(jìn)程同步時(shí)應(yīng)該注意的是：

（1）分析進(jìn)程間的制約關(guān)系，確定信號量種類。在保持進(jìn)程間有正確的同步關(guān)系情況下，哪個進(jìn)程先執(zhí)行，哪些進(jìn)程后執(zhí)行，彼此間通過什么資源（信號量）進(jìn)行協(xié)調(diào)，從而明確要設(shè)置哪些信號量。

（2）信號量的初值與相應(yīng)資源的數(shù)量有關(guān)，也與P、V操作在程序代碼中出現(xiàn)的位置有關(guān)。

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

生產(chǎn)一個產(chǎn)品;

P(empty);

產(chǎn)品送往Buffer;

V(full);

}消費(fèi)者進(jìn)程while(TRUE){

P(full);

從Buffer取出一個產(chǎn)品;

V(empty);

消費(fèi)該產(chǎn)品;

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

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

生產(chǎn)一個產(chǎn)品;

P(empty);

產(chǎn)品送往buffer(in);

in=(in+1)modn;

V(full);

}消費(fèi)者進(jìn)程while(TRUE){P(full);

從buffer(out)中取出產(chǎn)品;

out=(out+1)modn;

V(empty);

消費(fèi)該產(chǎn)品;

}

51（3）一組生產(chǎn)者，一組消費(fèi)者，公用n個環(huán)形緩沖區(qū)

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

設(shè)緩沖區(qū)的編號為1～n1，定義兩個指針in和out，分別是生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程使用的指針，指向下一個可用的緩沖區(qū)。

52生產(chǎn)者進(jìn)程while(TRUE){

生產(chǎn)一個產(chǎn)品;

P(empty);

P(mutex1);

產(chǎn)品送往buffer(in);

in=(in+1)modn;

V(mutex1);

V(full);

}消費(fèi)者進(jìn)程while(TRUE){P(full);

P(mutex2);

從buffer(out)中取出產(chǎn)品;

out=(out+1)modn;

V(mutex2);

V(empty);

消費(fèi)該產(chǎn)品;

}

53需要注意的是無論在生產(chǎn)者進(jìn)程中還是在消費(fèi)者進(jìn)程中，兩個P操作的次序不能顛倒。應(yīng)先執(zhí)行同步信號量的P操作，然后再執(zhí)行互斥信號量的P操作，否則可能造成進(jìn)程死鎖。

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

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

main()

{

cobegin

father();

/*父親進(jìn)程*/

son();

/*兒子進(jìn)程*/

daughter();

/*女兒進(jìn)程*/

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四個進(jìn)程A、B、C、D都要讀一個共享文件F，系統(tǒng)允許多個進(jìn)程同時(shí)讀文件F。但限制是進(jìn)程A和進(jìn)程C不能同時(shí)讀文件F，進(jìn)程B和進(jìn)程D也不能同時(shí)讀文件F。為了使這四個進(jìn)程并發(fā)執(zhí)行時(shí)能按系統(tǒng)要求使用文件，現(xiàn)用PV操作進(jìn)行管理，請回答下面的問題：

（1）應(yīng)定義的信號量及初值：

。

（2）在下列的程序中填上適當(dāng)?shù)腜、V操作，以保證它們能正確并發(fā)工作：

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。其中進(jìn)程A和C使用信號量S1，進(jìn)程B和D使用信號量S2。（2）從[1]到[8]分別為：P(S1)V(S1)P(S2)V(S2)P(S1)V(S1)P(S2)V(S2)

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

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

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

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

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

(1)高級通信方式：

①共享存儲器系統(tǒng)：共享數(shù)據(jù)結(jié)構(gòu)、共享存儲器區(qū)通信方式

②消息傳遞系統(tǒng)：直接通信方式——通過收發(fā)原語間接通信方式——通過信箱實(shí)現(xiàn)信息交換

③管道通信（2）管道通信具有三方面的協(xié)調(diào)能力：

①雙方同時(shí)存在

②

同步關(guān)系

③

互斥使用管道75第三章

調(diào)度與死鎖一、調(diào)度的類型

1、高級調(diào)度

2、

低級調(diào)度：非搶占式、搶占式搶占式：時(shí)間片原則、優(yōu)先權(quán)原則、短作業(yè)優(yōu)先原則

3、

中級調(diào)度76二、

面向用戶的準(zhǔn)則1、

周轉(zhuǎn)時(shí)間短：平均周轉(zhuǎn)時(shí)間、平均帶權(quán)周轉(zhuǎn)時(shí)間2、

響應(yīng)時(shí)間快3、

截止時(shí)間的保證4、

優(yōu)先權(quán)準(zhǔn)則

77三、面向系統(tǒng)的準(zhǔn)則1、

系統(tǒng)的吞吐量2、

CPU的利用率好3、

各類資源平衡使用78調(diào)度的算法1、

先來先服務(wù)調(diào)度的算法2、

短作業(yè)優(yōu)先調(diào)度的算法3、

時(shí)間片輪轉(zhuǎn)調(diào)度的算法（分時(shí)）或簡單輪轉(zhuǎn)調(diào)度的算法4、

優(yōu)先權(quán)調(diào)度的算法：非搶占式、搶占式

①靜態(tài)優(yōu)先權(quán)

②動態(tài)優(yōu)先權(quán)795、

響應(yīng)比高者優(yōu)先調(diào)度的算法：

RP=1+等待時(shí)間/服務(wù)時(shí)間6、多級隊(duì)列調(diào)度算法：例如，前臺、后臺7、多級反饋隊(duì)列調(diào)度算法（見P108或P80）

實(shí)時(shí)系統(tǒng)的調(diào)度算法

在實(shí)時(shí)系統(tǒng)中，廣泛采用搶占式調(diào)度方式80

死鎖的基本概念1、

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

產(chǎn)生死鎖原因：

①

競爭資源

②

推進(jìn)順序不當(dāng)3、

產(chǎn)生死鎖的必要條件

①互斥

②請求和保持

③不剝奪

④環(huán)路等待條件

81

4、

處理死鎖的基本方法

①

預(yù)防死鎖：設(shè)置某些限制條件，破壞四個條件。

②

避免死鎖：資源動態(tài)分配，防止進(jìn)入不安全狀態(tài)。

③

檢測死鎖：設(shè)置檢查機(jī)構(gòu)，定時(shí)檢查系統(tǒng)是否出現(xiàn)死鎖。

④解除死鎖：已出現(xiàn)死鎖。

82例.

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

進(jìn)程MaxABCAllocationABCNeedABCAvailableABCP0753010743332P1322200122

P2902302600

P3222211011

P4433002431

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

進(jìn)程MaxABCAllocationABCNeedABCAvailableABCP0753130

62312(3)753P1321200122(2)623

P2902302600

(4)1055P3222211011(1)

423P4433002431(5)1057

84第四章

存儲器管理

85

一、程序的裝入

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

2、可重定位裝入方式（靜態(tài)重定位）

重定位——把在裝入時(shí)對目標(biāo)程序中的指令和數(shù)據(jù)地址的修改過程稱為重定位。

3、動態(tài)運(yùn)行時(shí)裝入方式（動態(tài)重定位）

作業(yè)在存儲空間的位置，也是裝入時(shí)確定的，但在作業(yè)運(yùn)行過程中，每次存訪內(nèi)存之前，將程序的地址（邏輯地址）變?yōu)閮?nèi)存的物理地址。這種變換是依靠硬件地址變換機(jī)構(gòu)、自動連續(xù)實(shí)施，這樣程序在內(nèi)存的地址是可變的，可申請臨時(shí)空間。86二、程序的鏈接

1、

靜態(tài)鏈接——事先進(jìn)行鏈接，以后不再拆開的鏈接方式，稱為靜態(tài)鏈接。

2、

裝入時(shí)動態(tài)鏈接——編譯后的目標(biāo)模塊，是在裝入內(nèi)存時(shí)，邊裝入，邊鏈接的。

3、運(yùn)行時(shí)動態(tài)鏈接——將某些目標(biāo)模塊的鏈接推遲到執(zhí)行時(shí)才進(jìn)行，即在執(zhí)行過程中，若發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時(shí)，再由操作系統(tǒng)去找到該模塊，將它裝入內(nèi)存，并把它鏈接到調(diào)用者模塊上。

4、靜態(tài)鏈接需要共享目標(biāo)模塊的拷貝，而動態(tài)鏈接不需要共享目標(biāo)模塊的拷貝。87三、連續(xù)分配存儲管理方式

1、

固定式分區(qū)

2、

動態(tài)分區(qū)分配——根據(jù)用戶實(shí)際需要，動態(tài)的分配連續(xù)空間。

l拼接技術(shù)

3、

動態(tài)重定位分區(qū)分配——采用動態(tài)重定位技術(shù)的分區(qū)分配。

l

緊湊技術(shù)88四、分區(qū)管理的算法1、

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

循環(huán)首次適應(yīng)算法：將空白區(qū)構(gòu)成循環(huán)鏈表。表頭指向當(dāng)前開始查找的第一個空白區(qū)。3、

最佳適應(yīng)算法：空白區(qū)按尺寸大小遞增順序構(gòu)成隊(duì)列。表頭指向第一個空白區(qū)。89五、對換技術(shù)

（交換技術(shù)）

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

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

試問此時(shí)的存取時(shí)間是多少?92答：若頁表存放在主存中，則要實(shí)現(xiàn)一次頁面訪問需兩次訪問主存：一次是訪問頁表，確定所存取頁面的物理地址（稱為定位）。第二次才根據(jù)該地址存取頁面數(shù)據(jù)?！鲰摫碓谥鞔娴拇嫒≡L問時(shí)間

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

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

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

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

虛擬存儲器的概念？

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

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

在請求分頁存儲管理方式中，不限定把進(jìn)程的整個地址空間全部裝入主存，而只要求把當(dāng)前需要的一部分裝入主存，由系統(tǒng)實(shí)現(xiàn)進(jìn)程的正確運(yùn)行，其它的頁面當(dāng)需要時(shí)才去調(diào)用。這樣實(shí)現(xiàn)了主存的“擴(kuò)充”。地址變換機(jī)構(gòu)（見P170或P129）頁面的管理：

①頁面調(diào)入策略

●請求式調(diào)頁

●預(yù)先調(diào)頁97②頁面置換算法：

●FIFO

例如,P175或P134

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

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

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

基本思想

在請求分段存儲管理方式中，把作業(yè)的所有分段的副本保存在輔存中，當(dāng)其運(yùn)行時(shí)，只要求把當(dāng)前需要的一段或數(shù)段裝入主存，其它的段當(dāng)需要時(shí)才裝入，由系統(tǒng)實(shí)現(xiàn)進(jìn)程的正確運(yùn)行。這樣實(shí)現(xiàn)了主存的“擴(kuò)充”。（2）地址變換機(jī)構(gòu)（見P186或P139）

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

設(shè)備管理一、

I/O系統(tǒng)的組成

1、I/O系統(tǒng)的結(jié)構(gòu)102（1）

設(shè)備①獨(dú)占設(shè)備——在一段時(shí)間內(nèi)只允許一個用戶訪問的設(shè)備。②共享設(shè)備——在一段時(shí)間內(nèi)允許多個用戶訪問的設(shè)備。③

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

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

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

通道是通過執(zhí)行通道程序，并與設(shè)備控制器共同實(shí)現(xiàn)對I／O設(shè)備的控制的。通道程序是由一系列通道指令（或稱為通道命令）所構(gòu)成的。通道又稱為特殊的處理機(jī)。108三、

緩沖管理●

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

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

例如：

單緩沖、

雙緩沖、

循環(huán)緩沖、

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

四、

設(shè)備分配設(shè)備管理是通過一些數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)對其設(shè)備進(jìn)行管理和控制的。1。

設(shè)備控制表、通道控制表、系統(tǒng)設(shè)備表、控制器控制表2、設(shè)備分配中應(yīng)考慮的若干因素（1）設(shè)備的固有屬性：獨(dú)享設(shè)備、共享設(shè)備、虛擬設(shè)備

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

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

①初始化I/O設(shè)備

②

設(shè)備與進(jìn)程之間的數(shù)據(jù)傳送

③

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

早期磁盤調(diào)度算法

1、

先來先服務(wù)（見P261或P174）

2、

最短尋道時(shí)間優(yōu)先（見P261或P174

3、

掃描法（見P262或P175）

4、

循環(huán)掃描法（見P262或P175）

112第六章

文件系統(tǒng)113

一、

文件和文件系統(tǒng)的基本概念

1、

數(shù)據(jù)項(xiàng)——>記錄——>文件（見P228或P182圖）

2、

文件系統(tǒng)模型（見P229或P184圖）

3、

文件的操作（見P231或P185）

二、文件邏輯結(jié)構(gòu)

1、

順序文件（見P234或P187）

優(yōu)點(diǎn)：可以快速實(shí)現(xiàn)批量存取，可存儲在磁帶上缺點(diǎn)：增刪困難

2、

索引文件（見P235或P189）

優(yōu)點(diǎn)：實(shí)現(xiàn)直接存取、快速缺點(diǎn)：增加空間開銷

114三、

外存分配方法1.

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

優(yōu)點(diǎn)：結(jié)構(gòu)簡單，存取速度快。

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

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

優(yōu)點(diǎn)：插入、刪除方便，文件長度可變。

缺點(diǎn)：查找困難。3、

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

優(yōu)點(diǎn)：可以隨機(jī)存取。

缺點(diǎn)：增加空間的開銷。115四、

目錄管理

1、

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

2、

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

3、

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

缺點(diǎn)：查找速度慢、不允許重名、不便于實(shí)現(xiàn)文件共享

4、

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

l

當(dāng)前目錄——工作目錄

l

優(yōu)點(diǎn)：

①檢查速度快

②

不同目錄可以重名

③

不同用戶可使用不同名字，來訪問系統(tǒng)中的同一個共享文件。116●索引結(jié)點(diǎn)的引入在檢索目錄文件的過程中，只用到了文件名，僅當(dāng)找到一個目錄項(xiàng)（即其中的文件名與指定要查找的文件名相匹配）時(shí)，才需從該目錄項(xiàng)中讀出該文件的物理地址。而其它一些對該文件進(jìn)行描述的信息，在檢索目錄時(shí)一概不用，顯然，這些信息在檢索目錄時(shí)，不需調(diào)入內(nèi)存。為此，在有的系統(tǒng)中，如UNIX系統(tǒng)，便采用了把文件名與文件描述信息分開的辦法，亦即，使文件描述信息單獨(dú)形成一個稱為索引結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，簡稱為i結(jié)點(diǎn)。在文件目錄中的每個目錄項(xiàng)，僅由文件名和指向該文件所對應(yīng)的i結(jié)點(diǎn)的指針?biāo)鶚?gòu)成。

117

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

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

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

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

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

操作系統(tǒng)接口

119

用戶與操作系統(tǒng)的接口

操作系統(tǒng)

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

●用戶接口可以多種形式呈現(xiàn)在用戶面前：①一種是聯(lián)機(jī)命令形式，直接提供給用戶在終端上使用；②一種是系統(tǒng)調(diào)用形式，提供給用戶在編程時(shí)使用。人們通常把上述兩種形式分別稱為聯(lián)機(jī)命令接口和程序接口。一、

命令接口

命令接口由

命令解釋程序?qū)τ脩翩I入的命令進(jìn)行解釋，并轉(zhuǎn)入相應(yīng)的命令處理程序去執(zhí)行。二、

程序接口

1、系統(tǒng)調(diào)用——就是用戶在程序中調(diào)用操作系統(tǒng)所提供的一些子功能。

2、系統(tǒng)調(diào)用在本質(zhì)上是應(yīng)用程序請求OS內(nèi)核完成某功能時(shí)的一種過程調(diào)用，但它是一種特殊的過程調(diào)用，它與一般的過程調(diào)用有下述幾方面的明顯差別：

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

123三、

圖形用戶接口

①窗口是作為用戶與應(yīng)用程序之間的交互接口

②應(yīng)用程序可通過窗口向用戶展示系統(tǒng)所提供的各種服務(wù)及其需要用戶輸入的信息。

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

124研究生入學(xué)試題分析125

2000年操作系統(tǒng)入學(xué)試題

一、

單選題（每小題1分，共7分）1、線程是進(jìn)程的實(shí)體，意味著（）

①線程在進(jìn)程中是唯一的

②線程可以使用進(jìn)程中的資源

③線程在運(yùn)行中不能中斷

④在同一進(jìn)程中的多個線程具有不同的地址空間

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

①程序中申請資源時(shí)使用②死鎖出現(xiàn)之后使用

③死鎖即將出現(xiàn)時(shí)使用 ④定時(shí)檢查系統(tǒng)狀態(tài)時(shí)使用

3、在下列問題中，哪一個不是設(shè)備中應(yīng)考慮的問題（）

①設(shè)備的固有屬性 ②與設(shè)備無關(guān)性

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

①連續(xù)分配 ②鏈接分配

③互斥分配 ④索引分配5、聯(lián)想存儲器就是（）

①快表 ②頁表 ③段表 ④內(nèi)存

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

①多個用戶可同時(shí)訪問磁盤

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

③磁盤可支持SPOOLING技術(shù)

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

①變量②數(shù)據(jù)結(jié)構(gòu)

③隊(duì)列④純代碼127二、填空題（每小題1分，共6分）1、用戶與操作系統(tǒng)的接口是：____和_______________。2、多處理機(jī)有兩種結(jié)構(gòu)：_____和________.3、I/O控制方式________，____和________。4、產(chǎn)生死鎖的原因：______和_________。5、文件保護(hù)的方法有：_______，_________和___________。6、用于磁盤的主要調(diào)度算法有：__________，____________和____________。128

三、

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

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

2、（ ）動態(tài)重定位與裝入時(shí)動態(tài)鏈接在概念上是相同的。

3、（ ）在分時(shí)系統(tǒng)中采用虛擬存儲技術(shù)可以改善響應(yīng)時(shí)間。

4、（ ）在現(xiàn)代的分時(shí)系統(tǒng)中，邏輯處理機(jī)隱含了虛擬處理機(jī)的功能。

5、（ ）獨(dú)享設(shè)備與共享設(shè)備的屬性不同，其共享方式也不同。129

6、（ ）采用AND型信號量機(jī)制是為了防止系統(tǒng)的不安全。

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

8、（ ）設(shè)備處理程序是I/O進(jìn)程與設(shè)備控制器之間的通信程序。

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

為什么在頁式存儲管理中實(shí)現(xiàn)程序共享時(shí)，必須對共享程序給出相同的頁號，而段式存儲管理系統(tǒng)中實(shí)現(xiàn)程序共享時(shí)，共享段的段號是否一定要相同？如相同，為什么相同？如不相同，為什么不相同？131進(jìn)程到達(dá)就緒隊(duì)列的時(shí)間執(zhí)行時(shí)間P118P224P339P4452、

假定一個操作系統(tǒng)的進(jìn)程調(diào)度采用搶占式短進(jìn)程優(yōu)先調(diào)度策略（單CPU），系統(tǒng)中各進(jìn)程到達(dá)的時(shí)間如下表所示。請給出各進(jìn)程的調(diào)度次序，并計(jì)算平均周轉(zhuǎn)時(shí)間和平均代權(quán)周轉(zhuǎn)時(shí)間。注：表中的時(shí)間均為基本單位時(shí)間。1320102030p1p2p3p418-1=176-2=427-3=2411-4=7133

2001年操作系統(tǒng)入學(xué)試題一、單項(xiàng)選擇題（每小題1分，共10分）

1.進(jìn)程被阻塞以后，代表進(jìn)程在阻塞隊(duì)列的是它的(

)

①文件控制塊②進(jìn)程控制塊

③作業(yè)控制塊④設(shè)備控制塊

2.在以下哪種狀態(tài)下，作業(yè)已獲得虛處理機(jī)。（） ①提交狀態(tài)