計算機(jī)操作系統(tǒng)專升本重要課件1-1往年考試題型和分?jǐn)?shù)1.單選題25-30分,25-15小題2.填空題20分，10個空3.簡答題20-25分，4-5小題4.綜合題30分,3大題1-2往年考試特色04年,05年,06年1.選擇題分布在各個章節(jié),兼顧整個教材，考核主要側(cè)重基本概念和知識點(diǎn)例1.SPOOLING是利用_____為用戶提供虛擬的輸入/輸出設(shè)備的。A.主存B.磁盤C.輸入機(jī)D.寄存器例2.在不使用快表的分頁式存儲管理中，訪問一個數(shù)據(jù)需要訪問_____次內(nèi)存。A.1B.2C.3D.41-2往年考試特色2.填空題延續(xù)選擇題的風(fēng)格，一般情況下是對選擇題的進(jìn)一步補(bǔ)充，但還是集中在重要知識點(diǎn)上.例1.把允許幾個作業(yè)在執(zhí)行期間交替使用的設(shè)備成為_______設(shè)備。例2.內(nèi)存與外存進(jìn)行信息交換的單位是___參考P1221-2往年考試特色3.04年的簡答題各章一題，集中在基本概念和知識點(diǎn)，標(biāo)明為“理解”。05年的簡答題相當(dāng)于描述題帶有分析味道，側(cè)重理解和邏輯性。06年的簡答題考核主要知識點(diǎn)，輔助理解分析。1-2往年考試特色例1.簡述操作系統(tǒng)的基本特征例2.簡述引起死鎖的四個必要條件例3.簡述SPOOLING系統(tǒng)的基本組成例4.計算機(jī)有了通道后，如何實(shí)現(xiàn)CPU與外射的并行工作?例5.什么是設(shè)備獨(dú)立性?該特性有什么優(yōu)點(diǎn)?例6.網(wǎng)絡(luò)操作系統(tǒng)和分布式操作系統(tǒng)的主要區(qū)別是什么?1-2往年考試特色4.這幾年的綜合題側(cè)重考核：進(jìn)程通信的P/V操作

存儲管理的缺頁中斷和計算作業(yè)調(diào)度,平均周轉(zhuǎn)時間計算分頁式系統(tǒng)的地址映射1-2往年考試特色例1.某分頁存儲管理系統(tǒng),頁內(nèi)地址為11位,邏輯地址為24位。請問:(1)每頁有多少字節(jié)?(2)邏輯地址空間有多少頁?(3)邏輯地址3456對應(yīng)的物理地址是多少?頁號塊號081112263102……2-1復(fù)習(xí)的基本過程：

全面復(fù)習(xí)(細(xì)致地看一遍書)

(形成線索/框架)重點(diǎn)復(fù)習(xí)(針對提綱擴(kuò)大范圍)(達(dá)到一看就知道)習(xí)題強(qiáng)化(試題/補(bǔ)充/模擬)(透過題目復(fù)習(xí))2-2復(fù)習(xí)的基本要求：

OS是一門理論性和實(shí)踐性很強(qiáng)的課程，絕大部分都可作為考試的內(nèi)容，但是從課程性質(zhì)和考核大綱而言，必須重視的是：

基本概念和知識點(diǎn)、

基本理論(思想)、

基本算法和計算技巧。2-3可參考的復(fù)習(xí)方式

1.按章通過知識點(diǎn)和問題展開復(fù)習(xí)內(nèi)容，力求較為全面地掌握基本概念、原理、方法，達(dá)到能分析問題和解決問題。 2.強(qiáng)調(diào)OS的五大功能作為線索，掌握其中的重要理論和算法 3.通過習(xí)題強(qiáng)化，并反思第一章操作系統(tǒng)概述-線索

計算機(jī)系統(tǒng)的構(gòu)成軟件系統(tǒng)硬件系統(tǒng)系統(tǒng)應(yīng)用OS,語言處理,DBMS五大部分主機(jī),CPU？發(fā)展的五個階段？OS是否和計算機(jī)同時誕生?為什么會產(chǎn)生OS?怎么產(chǎn)生?定義(描述)/地位/特點(diǎn)/接口管理功能OS類型/特點(diǎn)作業(yè)管理處理機(jī)管理存儲器管理設(shè)備管理文件管理批處理(單/多)單獨(dú)自封/多共自封分時--多道+分時:多交獨(dú)及前臺/后臺作業(yè)實(shí)時--系統(tǒng)(限定/規(guī)定)高可靠性+高及時性網(wǎng)絡(luò)操作系統(tǒng):功能：網(wǎng)絡(luò)通信,資源管理,網(wǎng)絡(luò)服務(wù),網(wǎng)絡(luò)接口分布式OS特征：透明性,可靠性,高性能,可伸縮性第一章操作系統(tǒng)概述—線索第一章操作系統(tǒng)概述-問題

1.計算機(jī)系統(tǒng)由什么構(gòu)成?

2.誰提出計算機(jī)硬件的五大結(jié)構(gòu)？五大結(jié)構(gòu)包括哪些?

3.軟件按照功能可以分為哪兩類？

4.操作系統(tǒng)產(chǎn)生的簡單歷程

5.操作系統(tǒng)的雛形是什么?

6.什么是多道程序設(shè)計？

7.操作系統(tǒng)形成的標(biāo)志是什么?4.操作系統(tǒng)產(chǎn)生的簡單歷程

純手工->手工批處理->監(jiān)督程序->中斷和多道程序設(shè)計引入->批處理系統(tǒng)

->OS基本成型

5.操作系統(tǒng)的雛形--批處理監(jiān)督程序

6.多道程序設(shè)計：允許多個程序(作業(yè))同時進(jìn)入計算機(jī)內(nèi)存并啟動，交替計算(運(yùn)行)的方法。提升計算機(jī)使用效率

7.現(xiàn)代操作系統(tǒng)形成的標(biāo)志:多道程序系統(tǒng)的出現(xiàn)8.操作系統(tǒng)的一種描述（定義）

9.操作系統(tǒng)的地位和作用圖解

10.操作系統(tǒng)的功能分解

11.現(xiàn)代操作系統(tǒng)的特征，基本特征

12.操作系統(tǒng)的接口

13.單道/多道批處理操作系統(tǒng)的特點(diǎn)

14.分時操作系統(tǒng)的概念和特點(diǎn)

15.實(shí)時操作系統(tǒng)的概念和特點(diǎn)

16.網(wǎng)絡(luò)操作系統(tǒng)的概念,功能和特點(diǎn)8.操作系統(tǒng)是位于計算機(jī)硬件之上的第一層系統(tǒng)軟件，是整個計算機(jī)系統(tǒng)的核心；它控制和管理計算機(jī)軟硬件資源，合理、高效、安全地組織計算機(jī)的工作流程并方便用戶使用計算機(jī)

10.操作系統(tǒng)的五大功能

作業(yè)管理-處理機(jī)管理-存儲管理-設(shè)備管理-文件管理

程序和數(shù)據(jù)存放的方式是什么?11.現(xiàn)代操作系統(tǒng)的特征，基本特征

并發(fā)性、共享性、虛擬性、異步性

12.操作系統(tǒng)的接口

操作接口(作業(yè)),程序接口(系統(tǒng)調(diào)用)

13.單道/多道批處理操作系統(tǒng)的特點(diǎn)

單獨(dú)自封；多共自封

14.分時操作系統(tǒng)的概念和特點(diǎn)

多道+分時技術(shù)，多交獨(dú)及

15.實(shí)時操作系統(tǒng)的概念和特點(diǎn)

實(shí)時：限定的時間內(nèi)做出響應(yīng)

高可靠性+高及時性16網(wǎng)絡(luò)：把地理上分散、功能獨(dú)立的計算機(jī)和終端設(shè)備，通過通信線路連接，達(dá)到數(shù)據(jù)通信和資源共享目的的一種計算機(jī)系統(tǒng)。

在網(wǎng)絡(luò)范圍內(nèi)，用于管理網(wǎng)絡(luò)通信和共享資源，協(xié)調(diào)各計算機(jī)上任務(wù)的運(yùn)行，并向用戶提供統(tǒng)一的，有效方便的網(wǎng)絡(luò)接口的程序集合稱為網(wǎng)絡(luò)操作系統(tǒng)。計算機(jī)+通信技術(shù)功能：網(wǎng)絡(luò)通信，資源管理，提供網(wǎng)絡(luò)服務(wù)，提供網(wǎng)絡(luò)接口

特點(diǎn)：自治性,分散性,互聯(lián)性,統(tǒng)一性單道程序引入多道程序怎么描述多道程序運(yùn)行的本質(zhì)特點(diǎn)？引入進(jìn)程第二章處理機(jī)管理—線索進(jìn)程描述？分類？特點(diǎn)？狀態(tài)？構(gòu)成?三態(tài)如何轉(zhuǎn)化？注意此處的邏輯關(guān)系！是否需要三類隊列？每類各多少？構(gòu)成三部分,PCB的內(nèi)容決定把CPU分配給哪個進(jìn)程？分配多長時間？回收處理機(jī)FCFS先來先服務(wù)RR時間片輪轉(zhuǎn)優(yōu)先數(shù)|多級隊列---------------------------------------------------時間：剝奪與不可剝奪原語：進(jìn)程管理原語接口:指令/系統(tǒng)調(diào)用管態(tài)/目態(tài)/訪管作業(yè)及JCB作業(yè)的四個狀態(tài)作業(yè)調(diào)度算法相關(guān)計算二.CPU管理的二級調(diào)度–線索進(jìn)程調(diào)度作業(yè)調(diào)度決定哪些作業(yè)參與CPU競爭？第二章處理機(jī)管理

1.單道程序執(zhí)行特征{獨(dú)占,順序,再現(xiàn)}

2.多道系統(tǒng)下程序運(yùn)行的特征

{并發(fā),制約(間接/直接),狀態(tài)多變}

3.進(jìn)程的概念和構(gòu)成，進(jìn)程分類

4.PCB結(jié)構(gòu)包含{標(biāo)識,說明,現(xiàn)場,管理}

5.進(jìn)程的特征{動態(tài),并發(fā),制約,生命期,可執(zhí)行同一程序}

6.系統(tǒng)進(jìn)程和用戶進(jìn)程關(guān)系

7.進(jìn)程的三種基本狀態(tài)以及變遷過程8.為了管理進(jìn)程需要哪些控制隊列?

N個進(jìn)程，如何分布在上述隊列中？

各個隊列的個數(shù)是多少？

9.進(jìn)程調(diào)度的任務(wù)是什么？

10.進(jìn)程調(diào)度的算法有哪些？

11.什么是先來先服務(wù)調(diào)度算法?

如何理解先來先服務(wù)？進(jìn)程會一直占用CPU直到運(yùn)行完畢嗎?

是不是以啟動進(jìn)程并到達(dá)就緒隊列的時間為準(zhǔn)？還是以每次進(jìn)入就緒隊列的時間為準(zhǔn)？12.什么是時間片輪轉(zhuǎn)調(diào)度算法?

討論時間片大/小的關(guān)系?

時間片可以小于一個終端請求受理時間嗎?

FCFS與RR有什么區(qū)別?

13.什么是優(yōu)先數(shù)調(diào)度算法?

優(yōu)先級與優(yōu)先數(shù)的關(guān)系如何？

優(yōu)先數(shù)有靜態(tài)和動態(tài),各有什么特點(diǎn)？

系統(tǒng)進(jìn)程的優(yōu)先數(shù)如何?

I/O約束的進(jìn)程優(yōu)先數(shù)高好還是低好?

UNIX系統(tǒng)采用的是優(yōu)先數(shù)調(diào)度算法嗎?14.什么是多級隊列調(diào)度算法?

剛創(chuàng)建的進(jìn)程進(jìn)入哪一級就緒隊列?

阻塞態(tài)出來的進(jìn)程進(jìn)入哪一級就緒隊列?

時間片滿的進(jìn)程進(jìn)入哪一級就緒隊列?

如果有更高級別的進(jìn)程在就緒隊列中，此時處于運(yùn)行的進(jìn)程會被搶用CPU嗎？

被搶用CPU的進(jìn)程進(jìn)入哪一級就緒隊列?

它能保證主機(jī)與外設(shè)的較高利用率嗎？

各級就緒隊列采用何種調(diào)度算法？

15.進(jìn)程調(diào)度的兩種基本方式是什么?

搶先式，不可搶先式A.什么情況下會引發(fā)進(jìn)程調(diào)度程序執(zhí)行一個進(jìn)程從運(yùn)行到阻塞[一定]一個進(jìn)程從運(yùn)行到就緒[可能]一個進(jìn)程從阻塞到就緒[可能]一個進(jìn)程正常結(jié)束撤銷后[一定]B.FCFS屬于—[可剝奪，不可剝奪]調(diào)度而時間片輪轉(zhuǎn)法屬于________C.優(yōu)先數(shù)調(diào)度的調(diào)度方式是否兩種方式都可以?D.進(jìn)程模型中CPU調(diào)度和分配資源的基本單位是什么?16.為什么需要原語?什么是原語？

用什么方式實(shí)現(xiàn)原語？

17.特權(quán)指令,管態(tài),目態(tài),系統(tǒng)調(diào)用,用戶程序,訪管指令，它們相互關(guān)系如何？

源程序—系統(tǒng)調(diào)用編譯成訪管指令+功能編碼CPU執(zhí)行該指令，產(chǎn)生軟中斷陷入操作系統(tǒng)(目態(tài)到管態(tài))找到響應(yīng)的系統(tǒng)調(diào)用程序入口地址執(zhí)行相應(yīng)功能返回中斷點(diǎn)(注意:進(jìn)程可能已切換)

18.系統(tǒng)調(diào)用與一般程序調(diào)用的關(guān)系19.什么是作業(yè)？作業(yè)步？JCB?

20.什么是后備作業(yè)？后備作業(yè)隊列?

后備作業(yè)是否參與CPU的競爭?

21.什么是作業(yè)調(diào)度？它和進(jìn)程調(diào)度關(guān)系如何？高級調(diào)度—低級調(diào)度

22.作業(yè)的生命期經(jīng)歷哪些狀態(tài)?

提交—后備—運(yùn)行—完成

23.作業(yè)調(diào)度的原則

公平—均衡使用資源—高吞吐能力

什么是周轉(zhuǎn)時間？表征系統(tǒng)吞吐能力

Ti=完成時間-到達(dá)系統(tǒng)時間(后備)24.作業(yè)調(diào)度算法{FIFO,短作業(yè)優(yōu)先,高響應(yīng)比優(yōu)先}的思想和應(yīng)用

25.為什么說高響應(yīng)比優(yōu)先是FIFO和短作業(yè)優(yōu)先的折中？

26.短作業(yè)總能得到最小的平均周轉(zhuǎn)時間嗎？如果能條件是什么？

27.處于阻塞態(tài)的進(jìn)程，當(dāng)它所等待事件發(fā)生時(完成)，一定會變成就緒態(tài)并插入就緒隊列嗎？28.一個分時系統(tǒng)，允許10個終端用戶同時工作，時間片100ms，對于用戶的每個請求，CPU需要300ms進(jìn)行處理,那么一個用戶提出兩次請求的時間間隔最少是多少？

29.三個先后到達(dá)的進(jìn)程A,B,C分別需要24ms,3ms,3ms,如果按照FCFS的方式進(jìn)行進(jìn)程調(diào)度，請問平均等待時間是多少？平均等待時間為平均周轉(zhuǎn)時間30.作業(yè)分析

忽略系統(tǒng)調(diào)用時間，用三種作業(yè)調(diào)度算法確定作業(yè)調(diào)用順序，并計算各自的周轉(zhuǎn)時間和總的周轉(zhuǎn)時間作業(yè)號達(dá)到時間CPU時間18.81.529.50.839.01.0FCFS:1->3->2

1 8.8 10.3 1.5

2 9.5 12.1 2.6

3 9.0 11.3 2.3

平均周轉(zhuǎn)時間=(1.5+2.6+2.3)/3=32/15

短作業(yè):1->2->3 同F(xiàn)IFO

1 8.8 10.3 1.5

2 9.5 11.1 1.6

3 9.0 12.1 2.1

平均周轉(zhuǎn)時間=(1.5+1.6+2.1)/3=26/15高響應(yīng)比:1->3->2

1 8.8 10.3 1.5

2 9.5 12.1 2.6

3 9.0 11.3 2.3

平均周轉(zhuǎn)時間=(1.5+2.6+2.3)/3=32/15

作業(yè)1到達(dá)后先執(zhí)行，到了10.3的時候作業(yè)2和3都已經(jīng)達(dá)到，此時計算可知：作業(yè)2響應(yīng)比=0.8/0.8=1

作業(yè)3響應(yīng)比=1.3/1.0=1.3

所以先執(zhí)行作業(yè)3后執(zhí)行作業(yè)2 31.總內(nèi)存量100K,進(jìn)程不在內(nèi)存中移動,內(nèi)存連續(xù)分配；按照FCFS算法調(diào)度作業(yè)和進(jìn)程，請計算各周轉(zhuǎn)時間，平均周轉(zhuǎn)時間(忽略其它時間)。內(nèi)存分布.作業(yè)到達(dá)CPU時間內(nèi)存量110.10.715K210.30.570K310.50.450K410.60.420K510.70.210K作業(yè)到達(dá)CPU裝入開始完成周轉(zhuǎn)110.10.710.110.110.80.7210.30.510.310.811.31.0310.50.411.311.511.91.4410.60.411.311.912.31.7510.70.210.711.311.50.8平均周轉(zhuǎn)時間=1.12作業(yè)115k

作業(yè)270k

作業(yè)510k

5k

15k

作業(yè)270k

作業(yè)510k

5k作業(yè)350k

作業(yè)420k

15k

作業(yè)510k

5k實(shí)存分配虛存分配第三章存儲管理—線索固定分區(qū)可變分區(qū)實(shí)存頁式虛存頁式虛擬存儲器缺頁中斷頁面淘汰基本思想內(nèi)存怎么分割地址重定位/映射內(nèi)存分配與回收內(nèi)存保護(hù)內(nèi)存擴(kuò)充內(nèi)存利用率:碎片主要問題：大(多)程序,小內(nèi)存,裝不下;內(nèi)存利用率主要技術(shù)：覆蓋技術(shù),(交)對換技術(shù),虛存技術(shù)本章掌握基本概念：重定位,碎片,頁,塊,頁表,快表

虛擬存儲器,缺頁中斷,異常現(xiàn)象,抖動覆蓋，交換，頁淘汰,局部性原理內(nèi)存管理方法：A.每種存儲管理方法的基本思想，地址映射，優(yōu)缺點(diǎn)

B.空閑區(qū)的管理和分配算法C.頁面淘汰和缺頁中斷計算：地址映射,缺頁率計算1.內(nèi)存空間=物理地址空間，絕對地址空間

2.程序空間=邏輯地址空間，相對地址空間

3.CPU怎么訪問內(nèi)存存儲器?

4.一個程序的生命周期經(jīng)歷了哪些過程

5.什么是地址重定位?它有哪些形式？

6.靜態(tài)重定位的特點(diǎn)是什么?

能在內(nèi)存中移動嗎?

重定位需要硬件支持嗎?

在內(nèi)外存的程序相同嗎？

重定位工作是一次性完成嗎?

7.PCB中有沒有程序地址的說明信息?

該地址常稱為起始地址,它是程序段的起址嗎?

什么是碎片？內(nèi)/外碎片？8.單一連續(xù)分區(qū)存儲管理

內(nèi)存如何分區(qū)?系統(tǒng)區(qū)和用戶區(qū)

用戶區(qū)全部分配給一個程序嗎?

采用何種地址重定位?

如何實(shí)現(xiàn)內(nèi)存的存儲保護(hù)？可以采用一個界限寄存器法

會造成內(nèi)存浪費(fèi)嗎?

缺點(diǎn){單道,內(nèi)部碎片,問題未解決}

如何運(yùn)行大程序?覆蓋—擴(kuò)充內(nèi)存

如何模擬實(shí)現(xiàn)多任務(wù)?交換技術(shù)9.固定分區(qū)存儲管理

內(nèi)存如何分區(qū)?系統(tǒng)區(qū)和用戶區(qū)

用戶區(qū)如何劃分?這種劃分固定嗎?

每個分區(qū)的管理結(jié)構(gòu)如何安排?

采用地址重定位的方式是什么?

如何實(shí)現(xiàn)內(nèi)存的存儲保護(hù)？可以采用上下界限寄存器法

會造成內(nèi)存浪費(fèi)嗎?

缺點(diǎn){內(nèi)/外部碎片,無法移動}

采用什么策略將空閑分區(qū)分配給多個進(jìn)程針對多個隊列和1個隊列兩種情況.10.可變分區(qū)存儲管理

內(nèi)存如何分區(qū)?系統(tǒng)區(qū)和用戶區(qū)

用戶區(qū)根據(jù)什么劃分?

每個分區(qū)的管理結(jié)構(gòu)如何安排?

采用地址重定位的方式是什么?

該重定位需要硬件支持嗎？如何映射

產(chǎn)生的空閑塊采用什么方式合并？

空閑區(qū)的分配算法，出發(fā)點(diǎn)是什么?

如何實(shí)現(xiàn)內(nèi)存的存儲保護(hù)？可以采用上下界限寄存器法

缺點(diǎn){外部碎片,分區(qū)合并耗時}11.分頁式存儲管理(實(shí)存頁模式)

內(nèi)存如何劃分?程序如何劃分?

固定分區(qū)思想+動態(tài)重定位技術(shù)

什么是塊?什么是頁?頁表？

內(nèi)存塊表？進(jìn)程頁表?

重定位方式?如何映射?

地址換算公式：

相對地址/塊長=頁號

相對地址%塊長=頁內(nèi)偏移

形成地址對(頁號,頁內(nèi)偏移)查進(jìn)程頁表

得到塊號拼合絕對地址(塊號，頁內(nèi)偏移)

訪問物理內(nèi)存CPU訪問寄存器和內(nèi)存的速度差異這個矛盾導(dǎo)致快表的引入。這也印證了局部性原理

快表的命中率表征了性能的高低

快表的工作方式快在哪里?

內(nèi)存塊的分配與回收{(diào)存儲分塊法,位圖法,單鏈表法}

特點(diǎn){分塊,不連續(xù)全部裝入,動態(tài)重定位}

缺點(diǎn){半頁浪費(fèi),全部裝入}12.虛存

作用：解決了內(nèi)存的擴(kuò)充問題，滿足大程序的裝入。

什么是虛擬存儲器？大小如何確定?

什么是虛擬地址空間?

應(yīng)用：利用虛存思想的管理主要有：虛存頁式，段式，段頁式

需要解決兩個主要問題：

如何發(fā)現(xiàn)某個頁不在內(nèi)存？

內(nèi)存空閑塊不足無法裝入程序頁怎么辦？13.請求分頁式存儲管理

思想：不要求程序頁全部并連續(xù)地裝入內(nèi)存塊中,可以只載入其中的一部分,其它頁保存在輔存中,需要的時候通過缺頁中斷載入內(nèi)存中,如果內(nèi)存不夠則產(chǎn)生頁面淘汰以便裝入新的頁。

新的頁表結(jié)構(gòu)

{頁號,塊號,缺頁中斷位,輔存地址}

通常缺頁中斷位=1表示頁在內(nèi)存,否則發(fā)出缺頁中斷，請求載入外存頁

輔存地址：記錄頁在外存的地址P74-75A.缺頁中斷處理過程

B.缺頁中斷同一般的中斷有何區(qū)別?何時產(chǎn)生？中斷完成后回到哪里？

C.缺頁中斷率=缺頁次數(shù)/總頁數(shù)

影響缺頁率的因素：{分配給程序的內(nèi)存塊數(shù),頁面尺寸,程序的實(shí)現(xiàn)}頁面淘汰算法

內(nèi)存空閑塊不足，必須選擇已分配的內(nèi)存塊，調(diào)出內(nèi)存，才能裝入調(diào)入頁面.

這就是頁面淘汰，它由缺頁中斷引起.

問題：

1.選擇誰?

2.會出現(xiàn)異?；蚨秳?顛簸現(xiàn)象嗎?

頁面淘汰中可能涉及到頁面保存的問題，因此需要在頁表結(jié)構(gòu)中加入相應(yīng)的管理信息：{引用位,改變位}分別標(biāo)志在某個時間段是否被引用，是否被修改。頁淘汰相關(guān)算法：

FIFO先進(jìn)先出

LRU最近最久未用頁面淘汰

LFU最近最少用頁面淘汰

OPT最優(yōu)頁面淘汰

例子：頁面走向4,3,2,1,4,3,5,4,3,2,1,5在程序頁面為3和4時,分別采用FIFO,LRU算法，計算缺頁序列和缺頁中斷率。并分析FIFO是否會產(chǎn)生異常現(xiàn)象。頁面走向：4,3,2,1,4,3,5,4,3,2,1,5

FIFO頁面為3時9/12頁面4時10/12

432143555211432111543215

4321433352243222154321

43214443554333215432

123456789444321543

LRU頁面為3時10/12頁面為4時8/12

432143543215432143543215

4321435432143214354321

43214354324321435432

12345678910432111543問題1：在請求分頁模式中，分配給程序A的內(nèi)存為M塊，頁面走向共P頁，其中有N個不同的頁面，初始無任何頁在內(nèi)存中。問無論采用何種算法,缺頁中斷次數(shù)的下界是多少

缺頁中斷次數(shù)的上界是多少？

問題2：實(shí)存頁模式中，塊長2k，如果一個程序的相對地址空間為0—5129則分配給該程序的內(nèi)存空間為多少字節(jié)？浪費(fèi)了多少?問題3：實(shí)存頁模式下，內(nèi)存總量65536字節(jié),塊4k，一程序代碼段長32768字節(jié),數(shù)據(jù)段長16386字節(jié),棧段長15870字節(jié),規(guī)定不允許一個塊內(nèi)包含兩個段的內(nèi)容，請問能為該程序分配空間嗎?如果塊長為512字節(jié)呢?

問題4：假定CPU訪問內(nèi)存的時間為200ns,訪問快表的時間為40ns，命中率為90%，請問進(jìn)行一次內(nèi)存存取的平均時間是多少?比純粹采用頁表方式下降了多少?問題5：CPU訪問頁表100ns,快表20ns,希望將一次存取內(nèi)存的平均時間控制在140ns內(nèi)，請問命中率是多少?

問題6：系統(tǒng)內(nèi)存劃分成8塊，塊長4k，某程序虛擬地址空間劃分成16頁，如下表，為列出者不在內(nèi)存。

頁號塊號頁號塊號計算如下虛擬地址

0244的絕對地址

11532041008300

2695

30117問題7：可變分區(qū)中,按地址法組織空閑分區(qū),

大小分別為10k,4k,20k,18k,7k,9k,12k,15k

現(xiàn)依次有三個請求12k,10k,9k問采用最先適應(yīng)，最佳適應(yīng)，最壞適應(yīng)該如何分配?

地址法：分區(qū)按照起始地址從小到大排序

尺寸法：分區(qū)按照大小從小到大排序補(bǔ)1:設(shè)正在處理器上執(zhí)行的一個進(jìn)程的頁表如下，表中的虛頁號和物理塊號是十進(jìn)制數(shù)，起始頁號（塊號）均為0。頁的大小為1024字節(jié)。

①詳述在設(shè)有快表的請求分頁存儲管理系統(tǒng)中,一個虛地址轉(zhuǎn)換成物理地址的過程。

②下列虛地址對應(yīng)于什么物理地址：5499，2021

虛頁號狀態(tài)位訪問位修改位物理塊號

0 1 1 0 4

1 1 1 1 7

2 0 0 0 -

3 1 0 0 2

4 0 0 0 -

5 1 0 1 0 1.略

2.5499/1024=5余379，則虛頁號=5，頁內(nèi)偏移為379

則物理地址為：1024*0+379=3792021/1024=0余997，則虛頁號=0，頁內(nèi)偏移為997

則物理地址為：1024*4+997=5093補(bǔ)2:在一個采用頁式虛擬存儲管理的系統(tǒng)中，有一用戶作業(yè)，它依次要訪問的字地址序列是：115，228，120，88，446，102，321，432，260，167，若該作業(yè)的第0頁已經(jīng)裝入主存，現(xiàn)分配給該作業(yè)的主存共300字，頁的大小為100字，請回答下列問題：

（1）按FIFO調(diào)度算法將產(chǎn)生__次缺頁中斷，依次淘汰的頁號為__，缺頁中斷率為___。（2）按LRU調(diào)度算法將產(chǎn)生_____

次缺頁中斷，依次淘汰的頁號為____

，缺頁中斷率為___

。

計算的頁號為：0,1,2,1,0,4,1,3,4,2,11）按FIFO調(diào)度算法將產(chǎn)生5次缺頁中斷依次淘汰的頁號為：0，1，2缺頁中斷率為：5/10=50%2）按LRU調(diào)度算法將產(chǎn)生6次缺頁中斷；依次淘汰的頁號為：2，0，1，3缺頁中斷率為：6/10=60%第三章小結(jié)重要內(nèi)容： 每種管理方案思想,所用的數(shù)據(jù)結(jié)構(gòu)優(yōu)缺點(diǎn),特別是頁式；地址映射;可變分區(qū)中的分配和回收算法；缺頁中斷及頁淘汰計算；設(shè)備設(shè)備分配數(shù)據(jù)傳輸方式第四章設(shè)備管理范疇,分類引入設(shè)備管理?設(shè)備管理的目標(biāo)設(shè)備管理的功能用戶發(fā)出I/O請求I/O管理程序接受設(shè)備驅(qū)動完成I/O設(shè)備中斷處理請求I/O管理程序接受1.接受用戶請求2.組織管理I/O的進(jìn)行3.I/O完成后的善后處理I/O處理步驟SDTDCT—DCBCOCTCHCT絕對/相對號設(shè)備類/設(shè)備表磁臂調(diào)度程序循環(huán)測試中斷方式DMA方式—竊取總線通道方式—CPU與I/O并行緩沖和SPOOLING系統(tǒng)基本概念：設(shè)備,設(shè)備獨(dú)立性,移臂調(diào)度

虛擬設(shè)備,SPOOLING技術(shù)/系統(tǒng)緩沖,DMA,通道方法：獨(dú)占設(shè)備分配，移臂調(diào)度，數(shù)據(jù)傳輸控制方式計算：扇區(qū)與塊的對應(yīng),移臂調(diào)度第四章設(shè)備管理

1.什么是設(shè)備?

2.設(shè)備如何分類?

設(shè)備從屬關(guān)系：系統(tǒng)/用戶設(shè)備

分配特性：獨(dú)占,共享,虛擬

工作特性：輸入/輸出，存儲設(shè)備

3.磁盤基本構(gòu)造

扇區(qū)-磁道-柱面-盤面-盤片-盤片組-磁頭-移動臂P90

扇區(qū)弧長不等但是信息量相等磁盤存儲數(shù)據(jù)的方式：

先柱面0開始，然后磁道0開始，最后扇區(qū)0開始進(jìn)行順序存取。

假定每個柱面C個磁道,每個磁道S個扇區(qū)，如果給定柱面I,磁頭J,扇區(qū)K如何得到磁盤塊號呢？

B=k+S(J+I*C)

反之可以計算I,J,K;

令D=S*C,M=B/D,N=B%D

I=M,J=N/S,K=N%S例題：磁盤共100柱面，8磁道/柱面，8扇區(qū)/磁道，構(gòu)成地址(柱面,磁道,扇區(qū)),一文件6400個記錄，記錄大小同扇區(qū)，文件從(0,0,0)開始存放。

問題：

第3680個記錄應(yīng)放在磁盤的哪個位置?

地址（78,6,6）對應(yīng)的是哪個記錄?1:3680/(8*8)=57,3680%(8*8)=32

32/8=4,32%8=0==(57,4,0)

2:B=6+8*(6+78*8)=50464.設(shè)備管理的目標(biāo)

提高外部設(shè)備的利用率

為用戶提供方便統(tǒng)一的使用界面

5.設(shè)備管理的功能

提供一組I/O命令以便用戶程序調(diào)用，并獲得對外部設(shè)備的使用

進(jìn)行設(shè)備的分配和回收

對緩沖區(qū)管理

實(shí)現(xiàn)真正的I/O操作6.輸入輸出處理的步驟P91

用戶發(fā)出輸入輸出的I/O請求

I/O管理程序接受請求

調(diào)度設(shè)備驅(qū)動程序完成I/O操作

設(shè)備中斷處理程序處理請求

7.設(shè)備獨(dú)立性：通常用戶不指定特定的設(shè)備，而指定邏輯設(shè)備，使得用戶作業(yè)和物理設(shè)備獨(dú)立開，再通過其他途徑建立邏輯設(shè)備和物理設(shè)備之間的對應(yīng)關(guān)系，這種特性稱為設(shè)備獨(dú)立性返回8.管理設(shè)備的數(shù)據(jù)結(jié)構(gòu)

設(shè)備控制塊DCB

記錄設(shè)備的標(biāo)識,類型,狀態(tài),請求隊列指針,設(shè)備驅(qū)動程序地址等

系統(tǒng)設(shè)備表SDT

記錄系統(tǒng)所有的設(shè)備的DCB指針,設(shè)備標(biāo)識,類型等。中斷向量表IVT

控制器控制表COCT

通道控制表CHCT9.獨(dú)享設(shè)備一次只允許一個進(jìn)程使用的設(shè)備(排它性)，采用“靜態(tài)分配“

系統(tǒng)對各種不同類型的設(shè)備進(jìn)行內(nèi)部編號，以便區(qū)分，稱為絕對號.

用戶使用設(shè)備只考慮使用某種設(shè)備，而不是指定使用哪臺設(shè)備，所以用戶也可能對多臺設(shè)備進(jìn)行邏輯編號,以便區(qū)分，稱為相對號P97

系統(tǒng)設(shè)置兩種控制表：設(shè)備類表和設(shè)備表，以便實(shí)現(xiàn)用戶相對設(shè)備號和物理絕對號的對應(yīng)。

設(shè)備類表記錄設(shè)備類，總數(shù)，可用數(shù)，設(shè)備表地址

設(shè)備表記錄絕對號,狀態(tài),空閑情況,相對號,使用者等10.獨(dú)享設(shè)備的分配算法

FCFS優(yōu)先級高者先服務(wù)

注意：設(shè)備請求隊列的處理。

系統(tǒng)都是把設(shè)備分配給隊首進(jìn)程，因此第二種算法需要排序。

另外進(jìn)程使用完設(shè)備后，才從設(shè)備請求隊列中移出。11.磁盤的一次存取時間包含三部分

尋道時間(查找時間)，

延遲時間(等待時間),

傳輸時間

對于用戶的I/O請求序列，可以調(diào)整的有查找時間和等待時間;提高磁盤訪問效率主要通過：減少查找時間。 根據(jù)用戶作業(yè)發(fā)出的I/O請求的柱面位置，決定請求執(zhí)行的順序的調(diào)度稱為移臂調(diào)度 減少等待時間的調(diào)度為旋轉(zhuǎn)調(diào)度主要的移臂調(diào)度算法有：

FCFS最短查找時間優(yōu)先

電梯單向掃描習(xí)題P113

磁盤請求102220240638柱面先后到達(dá),移動臂移動一個柱面6ms,分別采用上述四種算法調(diào)度，各花多少查找時間？起始柱面20。(其中電梯算法先由外向里移動)(注意單向掃描的方向)

12.設(shè)備的構(gòu)造

I/O設(shè)備一般包含機(jī)械與電子兩部分

機(jī)械部分就是所謂的設(shè)備本身

電子部分通常稱為“設(shè)備控制器”或者適配器，其工作速度快，可連接多個相同類型的設(shè)備。

每種設(shè)備都通過一個控制器同CPU相連,因此CPU只同控制器溝通，控制器同設(shè)備溝通。13.數(shù)據(jù)傳輸方式

主要了解：主機(jī)與外設(shè)如何交換數(shù)據(jù),CPU作什么,數(shù)據(jù)傳輸完后如何告知CPU,CPU如何應(yīng)答等。

A.程序直控式

B.中斷方式

C.直接存儲器存取/DMA方式

D.通道方式14.緩沖技術(shù)

主機(jī)與外設(shè)的速度不匹配，因此需要引入緩沖，以避免快等慢現(xiàn)象。

可以通過硬緩沖(寄存器)和軟緩沖(存儲單元)方式實(shí)現(xiàn)緩沖。

緩沖的形式：單，雙，多，池15.虛擬設(shè)備

采用軟件技術(shù)依靠大容量磁盤來模擬獨(dú)占設(shè)備使其變成共享設(shè)備，即用一種物理設(shè)備模擬另一種物理設(shè)備，稱這樣的設(shè)備為虛擬設(shè)備。

實(shí)現(xiàn)虛擬設(shè)備的軟硬件條件：

A.大容量磁盤，且與CPU能并行

B.多道程序設(shè)計16.實(shí)現(xiàn)SPOOLING系統(tǒng)

硬件上：在磁盤上劃分出兩個區(qū)域，一個為輸入井(存放多個作業(yè)全部信息的存儲空間)，一個為輸出井(存放每個作業(yè)運(yùn)行輸出的存儲空間)

軟件上：需要多道程序設(shè)計

因此將建立在多道程序設(shè)計基礎(chǔ)上的聯(lián)機(jī)外圍設(shè)備同時操作稱為SPOOLING技術(shù)。 將操作系統(tǒng)種實(shí)現(xiàn)虛擬設(shè)備的軟件功能模塊稱為SPOOLING系統(tǒng)。

功能模塊的三大部分：

A.預(yù)輸入程序輸入機(jī)到輸入井

B.緩輸出程序輸出輸出井中信息

C.井管理程序(包括井管理讀/寫管理程序)請求輸入/輸出設(shè)備工作時，讓井管理讀/寫代替輸入/輸出設(shè)備實(shí)現(xiàn)從輸入井/輸出井中讀取/輸出數(shù)據(jù)第四章小結(jié)重點(diǎn)掌握：

磁盤結(jié)構(gòu)---柱面，磁道，扇區(qū)

設(shè)備管理采用的數(shù)據(jù)結(jié)構(gòu)

獨(dú)享設(shè)備分配的數(shù)據(jù)結(jié)構(gòu)和算法

磁盤訪問時間—磁盤調(diào)度算法

設(shè)備構(gòu)成中的設(shè)備控制器

四種數(shù)據(jù)傳輸方式

為何引入緩沖?SPOOLING系統(tǒng)基本概念：文件，文件系統(tǒng)，文件結(jié)構(gòu)存取方式，F(xiàn)CB,目錄，保密,共享與保護(hù)(保護(hù)的方法),文件操作

基本理論算法：空閑空間管理方法,文件內(nèi)部實(shí)現(xiàn),文件地址映射計算：空閑空間計算，地址映射第五章文件管理

1.什么是文件？

具有完整邏輯意義的一組相關(guān)信息的集合稱為文件

2.什么是文件系統(tǒng)?

與文件管理相關(guān)的那部分軟件、被管理的文件以及管理所需要的數(shù)據(jù)結(jié)構(gòu)的總體稱為文件系統(tǒng)。3.文件的分類

性質(zhì)和用途:系統(tǒng)，用戶，庫

保護(hù)性質(zhì):只讀,讀寫,執(zhí)行,不保護(hù)

保護(hù)期限:臨時,檔案,永久

存取方式:順序存取,隨機(jī)存取

設(shè)備類型:磁盤,磁帶,打印

邏輯結(jié)構(gòu):流式,記錄式

物理結(jié)構(gòu):連續(xù),鏈接,索引

文件內(nèi)容:普通,目錄,特殊

4.文件的邏輯結(jié)構(gòu)

從用戶角度的組織文件的形式

文件呈現(xiàn)在用戶面前的形式

分類：流式文件記錄文件

5.文件的物理結(jié)構(gòu)

文件的存儲結(jié)構(gòu)，以記錄成組的形式將文件存在輔存上。

分類：順序，鏈接，索引

6.文件存取方式

A.順序存取按照記錄排列順序

連續(xù)文件，鏈接文件，索引文件

B.隨機(jī)存取以任何次序存放

連續(xù)文件，索引文件

7.磁盤存儲空間管理

A.位示圖

B.空閑區(qū)表

C.空閑塊鏈D.成組鏈接法

A.位示圖樣例（注意基于0）

111000000000000000001000如果此時對第2個字節(jié)的第4位訪問，則對應(yīng)的磁盤塊是多少？字節(jié)0字節(jié)1字節(jié)2一磁盤空間24K，塊長1K，前三個塊和第20塊已經(jīng)分配出去了，試畫出位示圖。8.文件控制塊FCB

{文件名，文件在輔存中的物理位置,

文件的邏輯結(jié)構(gòu)，物理結(jié)構(gòu),

存取控制信息，管理信息}

9.文件目錄將多個文件的FCB集中起來構(gòu)成文件目錄

另外文件目錄以文件的形式存放稱為目錄文件。

一級目錄,二級,多級(樹型層次)

二級以上解決了文件同名沖突注意：絕對路徑和相對路徑

按名存取，活動文件目錄

問題：從用戶角度出發(fā)，引入文件系統(tǒng)的主要目的是_______________。

10.文件的基本操作-按名存取

open(Fname,OpenMode)

read(Fname,3,A)

1.通過Fname查找文件目錄，找到文件的FCB指針進(jìn)而得到FCB結(jié)構(gòu)

2.進(jìn)行存取控制驗(yàn)證，是否合法

3.從邏輯地址轉(zhuǎn)化到物理地址

4.啟動設(shè)備

11.文件的使用

文件共享：一個文件可以被多個授權(quán)用戶共同使用。

A.多個可用，一次僅一個在用

B.多個用戶同時使用，最多保證一個可寫，其他可讀.

實(shí)現(xiàn)共享：

A.同一個文件的多個FCB副本

B.連接法(分離法/硬連接)

C.符號連接法

12.文件的保護(hù)

防止未經(jīng)授權(quán)的用戶使用文件，同時防止文件主自己錯誤使用文件而毀壞文件。

采用的方式：

A.存取控制矩陣用戶X文件—權(quán)限

B.存取控制表每個文件對用戶分組

C.權(quán)限表用戶可使用的文件集合

D.口令驗(yàn)證機(jī)制(常存入FCB中，易被破解)

13.文件的操作

創(chuàng)建申請存儲空間，生成文件FCB

打開將文件FCB存入活動文件目錄中

刪除收回文件的存儲空間，去掉FCB

關(guān)閉釋放FCB在活動目錄中的位置

讀/寫通過緩沖區(qū)進(jìn)行讀寫第五章小結(jié)理解如下內(nèi)容：

文件的組織形式有哪些?

OS采用什么形式實(shí)現(xiàn)文件的存儲?

OS如何滿足用戶的按名存取文件?

OS如何管理外存的空閑空間?

OS如何實(shí)現(xiàn)目錄?

OS如何實(shí)現(xiàn)文件的共享和保護(hù)?

OS如何實(shí)現(xiàn)I/O地址映射? 14.習(xí)題2

A.按記錄存放，則每兩個記錄間要留出間隙即1000個記錄，有999個間隙。則浪費(fèi)

999*0.6/(1000*160/800+999*0.6）

B.每5個一個間隙，共200組,199間隙

C.1000*0.6/x-1為間隙個數(shù)設(shè)為y

y/(1000*160/800+y)<=0.514.習(xí)題3

1425/250=5余165

1425/500=2余425

則可知在邏輯記錄5中，物理塊2中補(bǔ)充1：假定盤塊1K，每個盤塊號4B，文件索引節(jié)點(diǎn)的磁盤地址明細(xì)表如圖，將下列字節(jié)偏移量轉(zhuǎn)換成物理地址。9000，14000，350000補(bǔ)充2：磁盤的每個磁道分成9個塊，現(xiàn)有一個文件共有A,B,C,D,E,F,G,H,I共9個記錄，每個記錄的大小與塊的大小一致，設(shè)磁盤轉(zhuǎn)速為27ms/轉(zhuǎn)，每讀出一塊后需要2ms的處理時間。若忽略其他輔助時間，請問：

1。如果順序存放這些記錄并順序讀取，處理該文件要多少時間？

2。如果要順序讀取這個文件，記錄該如何存放使得整個處理時間最短？

這個題目很有技巧性，請大家注意順序讀取、處理時間和轉(zhuǎn)速的關(guān)系。 由題目所給條件可知，磁盤轉(zhuǎn)速27ms/每轉(zhuǎn)，每磁道存放9個記錄，因此讀出1個記錄的時間是27/9=3ms

1.讀出并處理記錄A需要5ms,此時讀寫磁頭已經(jīng)轉(zhuǎn)到了記錄B的中間，因此為了讀出記錄B，必須在轉(zhuǎn)將近一圈(從記錄B中間到記錄B頭）。以此類推，但是最后一個記錄的讀取與處理時間只要5ms，為什么？

所以總時間=8*(27+3)+(3+2)=245ms2.由于讀出并處理一個記錄需要5ms，當(dāng)讀出并處理A的時，不妨假設(shè)記錄A放在第1個盤塊中，讀寫頭已經(jīng)移到第2個盤塊的中間，為了順序讀取B記錄，應(yīng)該將B放在第3個盤塊中，如下表所示：

盤塊1 2 3 4 5 6 7 8 9記錄A F B G C H D I E

這樣，處理一個記錄并將磁頭移到下一個記錄的時間是：

3(讀出)+2(處理)+1(等待)=6ms

所以總共需要：6*8+5=53ms重要概念：臨界資源,臨界區(qū),同步/互斥,信號量,P/V操作,死鎖，低級通信和高級通信

基本方法:死鎖產(chǎn)生的四個必要條件 解決死鎖的策略

重要算法操作：P/V,銀行家算法第6章進(jìn)程間的制約關(guān)系1.進(jìn)程間的制約關(guān)系同步/互斥

進(jìn)程同步：兩個以上進(jìn)程基于某個條件來協(xié)調(diào)它們的活動

進(jìn)程互斥：若干進(jìn)程要使用同一共享資源時候，任何時刻最多允許一個進(jìn)程使用，其他要使用該資源的進(jìn)程必須等待，直到占用資源的進(jìn)程釋放該資源。2.臨界資源一次僅允許一個進(jìn)程使用的資源的

3.臨界區(qū)并發(fā)進(jìn)程中使用臨界資源的程序段

4.臨界區(qū)的執(zhí)行要互斥,并符合準(zhǔn)則

無空等待有空讓進(jìn)

擇一而入算法可行5.信號量用來解決并發(fā)進(jìn)程間同步與互斥的通用方法，通過一個非負(fù)整型變量S,外加一個隊列Vq與它關(guān)聯(lián)，S需要一個初值定義兩種操作：P操作和V操作

P(S):S=S-1

ifS<0該進(jìn)程阻塞，進(jìn)入Vq

else繼續(xù)運(yùn)行

V(S):S=S+1

ifS<=0喚醒Vq中的一個進(jìn)程

P/V操作以原語方式執(zhí)行(單CPU下，可用開關(guān)中斷實(shí)現(xiàn))根據(jù)P/V操作的特性，可以實(shí)現(xiàn)：

6.信號量+P/V操作保證進(jìn)程間互斥

取信號量初值為1,在使用臨界資源前執(zhí)行P操作，使用完后執(zhí)行V操作

7.實(shí)現(xiàn)同步

注意：有幾個不同的同步需求就得設(shè)置幾個信號量，初值都為0

8.實(shí)現(xiàn)資源分配

信號量的初值=資源的個數(shù)習(xí)題2：

S=100資源數(shù)量

Enter

while(true)do

if有人來則{P(S)登記}

Exit

while(true)do

if有人走則{取消登記V(S)}習(xí)題4：

SB=1表示空緩,SW1=0,SW2=0

Read操作

讀數(shù)P(SB)存數(shù)

if奇數(shù)V(SW1)elseV(SW2)

W 1操作

P(SW1)讀數(shù)并打印V(SB)

W2操作

P(SW2)讀數(shù)并打印V(SB)習(xí)題3：

S1=1S2=0S3=0

R

ReadP(S1)InputtoBV(S2)