操作系統(tǒng)講義

1、操作系統(tǒng)第一章 操作系統(tǒng)概述1.1 操作系統(tǒng)的目標(biāo)和作用1.1.1 操作系統(tǒng)的目標(biāo)目標(biāo)：1. 方便性。不需要人人都是程序員2. 有效性。工作協(xié)調(diào)高效3. 可擴(kuò)充性。各自獨(dú)立發(fā)展4. 開放性。移植和互操作1.1.2 操作系統(tǒng)的作用1. OS作為用戶與計(jì)算機(jī)硬件系統(tǒng)之間的接口OS處于用戶與計(jì)算機(jī)硬件系統(tǒng)之間，用戶通過OS來使用計(jì)算機(jī)系統(tǒng)。(從用戶角度來看，來操縱計(jì)算機(jī)。)(1) 命令輸入。形式又分為以下幾種：命令行(Comma nd Line In put ):由OS提供的一組聯(lián)機(jī)命令(語言)，用戶可通過鍵盤輸 入有關(guān)命令，來直接操縱計(jì)算機(jī)系統(tǒng)。圖形用戶界面( GUI )：用戶通過顯示設(shè)備上的窗口

2、 和圖標(biāo)來操縱計(jì)算機(jī)系統(tǒng)和運(yùn)行自己的程序。自然輸入方式( NUI )：用戶通過語音識(shí)別輸 入來操縱計(jì)算機(jī)系統(tǒng)和運(yùn)行自己的程序。(2) 系統(tǒng)調(diào)用方式(System Call )。OS提供了一組系統(tǒng)調(diào)用，用戶可在自己的應(yīng)用程序中 通過相應(yīng)的使用編程調(diào)用 API1.1.3 推動(dòng)操作系統(tǒng)發(fā)展的主要?jiǎng)恿?. 不斷提高計(jì)算機(jī)資源利用率2. 方便用戶3. 器件的不斷更新?lián)Q代4. 計(jì)算機(jī)體系結(jié)構(gòu)的不斷發(fā)展用戶的需求是推動(dòng)OS發(fā)展的根本動(dòng)力2. OS 作為計(jì)算機(jī)系統(tǒng)資源的管理者在一個(gè)計(jì)算機(jī)系統(tǒng)中通常都含有各種各樣的硬件和軟件資源。需要空間和時(shí)間來使用這些資源，OS合理調(diào)配和使用。(這是從管理者的角度來看)3.

3、OS用作擴(kuò)展機(jī)、虛擬機(jī)隱藏了計(jì)算機(jī)具體細(xì)節(jié)，為用戶展現(xiàn)的是一臺(tái)虛擬機(jī)，功能上擴(kuò) 展了幾個(gè)功能部件的組合。 (這是從發(fā)展的角度來看) Government1.2 操作系統(tǒng)的發(fā)展過程1.2.1 無操作系統(tǒng)的計(jì)算機(jī)系統(tǒng)1. 人工操作方式從第一臺(tái)計(jì)算機(jī) ENIAC 誕生(1945 年 2 月)到 50 年代中期的計(jì)算機(jī)，屬于第一代。這種人 工操作方式有以下兩方面的缺點(diǎn)： (1) 用戶獨(dú)占全機(jī)。 (2) CPU 等待人工操作。2. 脫機(jī)輸入/輸出(Of-Line I/O)方式這種脫機(jī)I/O方式的主要優(yōu)點(diǎn)如下：(1) 減少了 CPU的空閑時(shí)間。(2)提高I/O速度。1.2.2 單道批處理系統(tǒng)1. 單道批處

4、理系統(tǒng) (Simple Batch Processing System)的處理過程2. 單道批處理系統(tǒng)的特征 該系統(tǒng)的主要特征如下： (1) 自動(dòng)性。 (2) 順序性。 (3) 單道性。1.2.3 多道批處理系統(tǒng)1. 多道程序設(shè)計(jì)的基本概念多道批處理系統(tǒng) (Multiprogrammed Batch Processing System) 。在該系統(tǒng)中，用戶所提 交的作業(yè)都先存放在外存上并排成一個(gè)隊(duì)列，稱為后備隊(duì)列；然后，由作業(yè)調(diào)度程序按一 定的算法從后備隊(duì)列中選擇若干個(gè)作業(yè)調(diào)入內(nèi)存，使它們共享CPU 和系統(tǒng)中的各種資源。這種調(diào)度稱之為作業(yè)調(diào)度。1.2.4 分時(shí)系統(tǒng)1. 分時(shí)系統(tǒng) (Time S

5、haring System) 的產(chǎn)生 如果說，推動(dòng)多道批處理系統(tǒng)形成和發(fā)展的主要?jiǎng)恿?，是提高資源利用率和系統(tǒng)吞吐量， 那么，推動(dòng)分時(shí)系統(tǒng)形成和發(fā)展的主要?jiǎng)恿?，則是用戶的需求。用戶的需求具體表現(xiàn)在以 下幾個(gè)方面：(1) 人機(jī)交互。(2) 共享主機(jī)。(3) 便于用戶上機(jī)。2. 分時(shí)系統(tǒng)實(shí)現(xiàn)中的關(guān)鍵問題 分時(shí)系統(tǒng)性能好壞的主要指標(biāo)是響應(yīng)時(shí)間。(1) 及時(shí)接收。(2) 及時(shí)處理。(3) 符合使用習(xí)慣。在 OS 中引入多道程序設(shè)計(jì)技術(shù)可帶來以下好處：(1) 提高CPU的利用率。(2) 可提高內(nèi)存和 I/O 設(shè)備利用率。(3) 增加系統(tǒng)吞吐量。2. 多道批處理系統(tǒng)的特征(1) 多道性。 (2) 無序性。

6、(3) 調(diào)度性。3. 多道批處理系統(tǒng)的優(yōu)缺點(diǎn)(1) 資源利用率高。(2) 系統(tǒng)吞吐量大。(3) 平均周轉(zhuǎn)時(shí)間長。(4) 無交互能力。4. 多道批處理系統(tǒng)需要解決的問題(1) 處理機(jī)管理問題。(2) 內(nèi)存管理問題。(3) I/O 設(shè)備管理問題。(4) 文件管理問題。(5) 作業(yè)管理問題。3. 分時(shí)系統(tǒng)的特征(1) 多路性。 (2) 獨(dú)立性。 (3) 及時(shí)性。 (4) 交互性。1.2.5 實(shí)時(shí)系統(tǒng)實(shí)時(shí)系統(tǒng) (Real-Time System) 是指系統(tǒng)能及時(shí) ( 或即時(shí) ) 響應(yīng)外部事件的請(qǐng)求，在規(guī)定的間 內(nèi)完成對(duì)該事件的處理，并控制所有實(shí)時(shí)任務(wù)協(xié)調(diào)一致地運(yùn)行。1.3 操作系統(tǒng)的基本特性1.3.1

7、 并發(fā) (Concurrence) 并行性和并發(fā)性是既相似又有區(qū)別的兩個(gè)概念，并行性是指兩個(gè)或多個(gè)事件在同一時(shí)刻發(fā) 生；而并發(fā)性是指兩個(gè)或多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生。最基本的特征！1.3.2 共享 (Sharing) 在操作系統(tǒng)環(huán)境下，所謂共享是指系統(tǒng)中的資源可供內(nèi)存中多個(gè)并發(fā)執(zhí)行的進(jìn)程( 線程 )共同使用。1.3.3 虛擬 (Virtual) 操作系統(tǒng)中的所謂虛擬，是指通過某種技術(shù)把一個(gè)物理實(shí)體變?yōu)槿舾蓚€(gè)邏輯上的對(duì)應(yīng)物。1.3.4 異步性 (Asynchronism) 在多道程序環(huán)境下，多個(gè)進(jìn)程是以停停走走的方式運(yùn)行。失去封閉性第二章進(jìn)程管理2.1 進(jìn)程的基本概念2.1.1 程序的順序執(zhí)行

8、及其特征2.1.2 前趨圖前趨圖 (Precedence Graph) 是一個(gè)有向無循環(huán)圖，記為 DAG(Directed Acyclic Graph) ， 用于描述進(jìn)程之間執(zhí)行的前后關(guān)系。2.1.3 程序的并發(fā)執(zhí)行及其特征2.1.4 進(jìn)程的特征與狀態(tài)One program which has an independent function works on certain data set dynamically and allocate resources dynamically What is a process? 一個(gè)具有一定獨(dú)立功能的程序?qū)δ硞€(gè)數(shù)據(jù) 集合上的一次動(dòng)態(tài)執(zhí)行過程和資源分配

9、過程Code， Data， Process Table The Difference Between Process and Program Process is dynamic, and the program is static Process is temporary, the program is permanenceThe eleme nts of process and program is differe nt Code Data PT The relati on shipsof process and program are complex Create System call

10、2. 進(jìn)程的三種基本狀態(tài)1) 就緒 (Ready) 狀態(tài) 2) 執(zhí)行狀態(tài) 3) 阻塞狀態(tài)2.1.5 進(jìn)程控制塊1. 進(jìn)程控制塊的作用進(jìn)程控制塊的作用是記錄一個(gè)獨(dú)立運(yùn)行的進(jìn)程的基本信息?；蛘哒f，OS是根據(jù)PCB來對(duì)并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。2. 進(jìn)程控制塊中的信息3. 進(jìn)程控制塊的組織方式1) 鏈接方式 2) 索引方式2.2 進(jìn)程控制2.2.1 進(jìn)程的創(chuàng)建(1) 用戶登錄。(2) 作業(yè)調(diào)度。(3) 提供服務(wù)。(4) 應(yīng)用請(qǐng)求。(1) 申請(qǐng)空白 PCB。(2) 為新進(jìn)程分配資源。(3) 初始化進(jìn)程控制塊。(4) 將新進(jìn)程插入就緒隊(duì)列，如果進(jìn)程就緒隊(duì)列能夠接納新進(jìn)程，便將新進(jìn)程插入就 緒隊(duì)列。

11、2. 進(jìn)程的終止過程(1) 根據(jù)被終止進(jìn)程的標(biāo)識(shí)符， 從PCB集合中檢索出該進(jìn)程的 PCB從中讀出該進(jìn)程的狀態(tài)。(2) 若被終止進(jìn)程正處于執(zhí)行狀態(tài)，應(yīng)立即終止該進(jìn)程的執(zhí)行，并置調(diào)度標(biāo)志為真，用于 指示該進(jìn)程被終止后應(yīng)重新進(jìn)行調(diào)度。(3) 若該進(jìn)程還有子孫進(jìn)程，還應(yīng)將其所有子孫進(jìn)程予以終止，以防他們成為不可控的進(jìn) 程。(4) 將被終止進(jìn)程所擁有的全部資源，或者歸還給其父進(jìn)程，或者歸還給系統(tǒng)。(5) 將被終止進(jìn)程 (它的 PCB) 從所在隊(duì)列 (或鏈表 )中移出，等待其他程序來搜集信息。2.2.2 進(jìn)程的終止1) 正常結(jié)束(自愿的)2) 異常結(jié)束 普通錯(cuò)誤退出(自愿的) 致命錯(cuò)誤退出(非自愿的)3

12、) 外界干預(yù)(非自愿的)2.2.3 進(jìn)程的阻塞與喚醒1. 引起進(jìn)程阻塞和喚醒的事件1 )請(qǐng)求系統(tǒng)服務(wù)2) 啟動(dòng)某種操作3) 新數(shù)據(jù)尚未到達(dá)4) 無新工作可做2.2.4 進(jìn)程的掛起與激活2.3 進(jìn)程同步2.3.1 進(jìn)程同步的基本概念1. 兩種形式的制約關(guān)系(1) 間接相互制約關(guān)系。(2) 直接相互制約關(guān)系。2. 臨界資源 (Critical Resource)3. 臨界區(qū) (critical section)一個(gè)飛機(jī)訂票系統(tǒng)，兩個(gè)終端，運(yùn)行T1、T2 進(jìn)程T1 ：read(x); if x>=1 then x:=x-1; write(x);T2： read(x); if x>=1 t

13、hen x:=x-1; write(x);Critical Regions Coming data blocks Synchronization4. 同步機(jī)制應(yīng)遵循的規(guī)則(1) 空閑讓進(jìn)。(2) 忙則等待。(3) 有限等待。(4) 讓權(quán)等待。 (Peterson ' s Algorithm) ： 先修改、后檢查、后修改者等待正確的算法 turn=j; 描述可進(jìn)入的進(jìn)程(同時(shí)修改標(biāo)志時(shí)) 在進(jìn)入?yún)^(qū)先修改后檢查，并檢查并發(fā)修改的先后： 檢查對(duì)方 flag ， 如果不在臨界區(qū)則自己進(jìn)入空閑則入 否則再檢查 turn ： 保存的是較晚的一次賦值，則較晚的進(jìn) 程等待，較早的進(jìn)程進(jìn)入先到先入，后到

14、等待Mutual Exclusion with Busy Waiting Entering and leaving a critical region using the TSL instructionSleep andWakeupProducer-consumer problem with fatal race condition2.3.2 信號(hào)量機(jī)制1. 整型信號(hào)量最初由 Dijkstra 把整型信號(hào)量定義為一個(gè)整型量， 僅能通過初始化和兩個(gè)標(biāo)準(zhǔn)的原子操作 (Atomic Operation) wait(S) 和 signal(S) 來訪問。兩個(gè)操作被分別稱為P、 V 操作(primiti

15、ve) 。wait(S): while S < 0 do no opS： =S-1;sig nal(S): S : =S+1;2. 記錄型信號(hào)量在整型信號(hào)量機(jī)制中的 wait操作，只要是信號(hào)量SW 0，就會(huì)不斷地測試。因此，該機(jī)制并未遵循讓權(quán)等待的準(zhǔn)則，而是使進(jìn)程處于忙等的狀態(tài)。記錄型信號(hào)量機(jī)制，則是一種不 存在忙等現(xiàn)象的進(jìn)程同步機(jī)制。但在采取了讓權(quán)等待的策略后，又會(huì)出現(xiàn)多個(gè)進(jìn)程等待訪 問同一臨界資源的情況。為此，在信號(hào)量機(jī)制中，除了需要一個(gè)用于代表資源數(shù)目的整型 變量value夕卜，還應(yīng)增加一個(gè)進(jìn)程鏈表L,用于鏈接上述的所有等待進(jìn)程。記錄型信號(hào)量是由于它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)而得名的。

16、P 原語 wait(s); down(s); P(s)-s.count; /表示申請(qǐng)一個(gè)資源 ;if (s.count <0)/ 表示沒有空閑資源 ; 調(diào)用進(jìn)程進(jìn)入等待隊(duì)列 s.queue; 阻塞調(diào)用進(jìn)程 ;V 原語 signal(s); up(s); V(s)+s.count; / 表示釋放一個(gè)資源；if (s.count <= 0) / 表示有進(jìn)程處于阻塞狀態(tài)； 從等待隊(duì)列 s.queue 中取出一個(gè)進(jìn)程 P; 進(jìn)程 P 進(jìn)入就緒隊(duì)列 ; SemaphoresThe producerconsumer problem using semaphores Monitors Examp

17、le of a monitor2.4 經(jīng)典進(jìn)程的同步問題2.4.1 生產(chǎn)者消費(fèi)者問題1. 利用記錄型信號(hào)量解決生產(chǎn)者消費(fèi)者問題 Dining Philosophers Philosophers eat/think Eating needs 2 forks Pick one fork at a time How to prevent deadlock2.4.2 哲學(xué)家進(jìn)餐問題 讓奇數(shù)號(hào)的哲學(xué)家先取右手邊的筷子，讓偶數(shù)號(hào)的哲學(xué)家先取左手邊的筷子。 send(i) begin if i mod 2 = 0 then else P(ci); P(ci+1 mod 5);P(ci+1 mod 5); P

18、(ci); eat; eat;V(ci+1 mod 5); V (ci);V (ci); V(ci+1 mod 5); end2.4.3 讀者寫者問題 讀者 - 寫者問題描述The Readersand WritersProblem1. 利用記錄型信號(hào)量解決讀者寫者問題The Sleeping Barber ProblemThe SleepingBarberProblemSolution to sleepingbarber problemShared memory( 共享內(nèi)存 )Message( 消息機(jī)制 )Pipe( 管道 )Signal( 信號(hào) )Socket( 套接字 )Interpro

19、cess Communication2.5 進(jìn)程通信 2.5.1 進(jìn)程通信的類型1. 共享存儲(chǔ)器系統(tǒng) (Shared Memory System)(1) 基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式。(2) 基于共享存儲(chǔ)區(qū)的通信方式。2. 消息傳遞系統(tǒng) (Message passing system) 在消息傳遞系統(tǒng)中，進(jìn)程間的數(shù)據(jù)交換， 是以格式化的消息 (message) 為單位的； 在計(jì)算機(jī)網(wǎng)絡(luò)中，又把 message 稱為報(bào) 文。程序員直接利用系統(tǒng)提供的一組通信命令 (原語 )進(jìn)行通信。3. 管道 (Pipe) 通信 管道是指用于連接一個(gè)讀進(jìn)程和一個(gè) 寫進(jìn)程以實(shí)現(xiàn)他們之間通信的一個(gè)共享文 件，又名 pi

20、pe 文件。這種方式首創(chuàng)于 UNIX 系統(tǒng)，由于它能有效地傳送大量數(shù)據(jù)，因 而又被引入到許多其它操作系統(tǒng)中。2.5.2 消息傳遞通信的實(shí)現(xiàn)方法1. 直接通信方式 通信命令 ( 原語 ) ： Send(Receiver, message); 發(fā)送一個(gè)消息給接收進(jìn)程； Receive(Sender, message); 接收 Sender 發(fā)來的消息；例如，原語Send(P2, ml)表示將消息ml發(fā)送給接收進(jìn)程 P2;而原語Receive(P1 , ml) 則表示接收由 P1 發(fā)來的消息 m1。不指定發(fā)送者的接收原語可表示為： Receive (id, message); 利用直接通信原語，解決

21、生產(chǎn)者消費(fèi)者問題。repeatproduce an item in nextp;send(consumer, nextp);until false; repeat receive(producer, nextc);consume the item in nextc; until false;Message Passing .The producerconsumer problem with N messages2. 間接通信方式(1) 信箱的創(chuàng)建和撤消。(2) 消息的發(fā)送和接收。Send( box, message); 將一個(gè)消息發(fā)送到指定信箱； Receive( box, message);

22、 從指定信箱中接收一個(gè)消息；3. 進(jìn)程同步方式(1) 發(fā)送進(jìn)程阻塞、接收進(jìn)程阻塞。(2) 發(fā)送進(jìn)程不阻塞、接收進(jìn)程阻塞。(3) 發(fā)送進(jìn)程和接收進(jìn)程均不阻塞。2.6 線程2.6.1 線程的基本概念 為使程序能并發(fā)執(zhí)行，系統(tǒng)還必須進(jìn)行以下的一系列操作。1) 創(chuàng)建進(jìn)程2) 撤消進(jìn)程3) 進(jìn)程切換1. 線程的引入The Thread Model(a) Three processes each with one thread(b) One process with three threads For Example The Thread Model Each thread has its own sta

23、ck2. 線程的屬性(1) 輕型實(shí)體(容易創(chuàng)建和撤銷) 。(2) 獨(dú)立調(diào)度和分派的基本單位。(3) 可并發(fā)執(zhí)行。(4) 共享進(jìn)程資源。(5) 適應(yīng)硬件的發(fā)展The Thread ModelItems shared by all threads in a processItems private to each thread3. 線程的狀態(tài)(1) 狀態(tài)參數(shù)。(2) 線程運(yùn)行狀態(tài)。5. 多線程OS中的進(jìn)程 在多線程OS中，進(jìn)程是作為擁有系統(tǒng)資源的基本單位，通常的進(jìn)程都包含多個(gè)線程并為它 們提供資源，但此時(shí)的進(jìn)程就不再作為一個(gè)執(zhí)行的實(shí)體。多線程OS中的進(jìn)程有以下屬性:(1) 作為系統(tǒng)資源分配的單位。

24、(2) 可包括多個(gè)線程。(3) 進(jìn)程不是一個(gè)可執(zhí)行的實(shí)體。4. 線程的創(chuàng)建和終止 在多線程OS環(huán)境下，應(yīng)用程序在啟動(dòng)時(shí)，通常僅有一個(gè)線程在執(zhí)行，該線程被人們稱為初 始化線程。它可根據(jù)需要再去創(chuàng)建若干個(gè)線程。終止線程的方式有兩種:一種是在線程完 成了自己的工作后自愿退出；另一種是線程在運(yùn)行中出現(xiàn)錯(cuò)誤或由于某種原因而被其它線 程強(qiáng)行終止。2.6.2 線程間的同步和通信1. 互斥鎖 (mutex) 互斥鎖是一種比較簡單的、用于實(shí)現(xiàn)線程間對(duì)資源互斥訪問的機(jī)制。2. 條件變量 Use of a barrier processes approaching a barrier all processes b

25、ut one blocked at barrier last process arrives, all are let through2.6.3 內(nèi)核支持線程和用戶級(jí)線程1. 內(nèi)核支持線程 這里所謂的內(nèi)核支持線程，也都同樣是在內(nèi)核的支持下運(yùn)行的，即無論是用戶進(jìn)程中的線 程，還是系統(tǒng)進(jìn)程中的線程，他們的創(chuàng)建、撤消和切換等，也是依靠內(nèi)核實(shí)現(xiàn)的。此外， 在內(nèi)核空間還為每一個(gè)內(nèi)核支持線程設(shè)置了一個(gè)線程控制塊，內(nèi)核是根據(jù)該控制塊而感知 某線程的存在的，并對(duì)其加以控制。Implementing Threads in the Kernel A threads package managed by the k

26、ernel2. 用戶級(jí)線程 用戶級(jí)線程僅存在于用戶空間中。對(duì)于這種線程的創(chuàng) 建、撤消、線程之間的同步與通信等功能，都無須利用 系統(tǒng)調(diào)用來實(shí)現(xiàn)。對(duì)于用戶級(jí)線程的切換，通常是發(fā)生在 一個(gè)應(yīng)用進(jìn)程的諸多線程之間，這時(shí)，也同樣無須內(nèi)核的 支持。由于切換的規(guī)則遠(yuǎn)比進(jìn)程調(diào)度和切換的規(guī)則簡單， 因而使線程的切換速度特別快。可見，這種線程是與內(nèi)核 無關(guān)的。Implementing Threads in User Space A user-level threads package Hybrid ImplementationsMultiplexing user-level threads onto kernel

27、level threadsThe Multithreading Revolution第三章處理機(jī)調(diào)度與死鎖3.1 處理機(jī)調(diào)度的基本概念Bursts of CPU usage alternate with periods of I/O waita CPU-bound processan I/O-bound process Scheduling Algorithm Goals3.1.1 高級(jí)、中級(jí)和低級(jí)調(diào)度Three level schedulingFCFSSJFHRFSRFFCFSSPFRRPS1. 高級(jí)調(diào)度 (High Scheduling) 宏觀調(diào)度在每次執(zhí)行作業(yè)調(diào)度時(shí)，都須做出以下兩個(gè)決定

28、。1) 接納多少個(gè)作業(yè) ?2) 接納哪些作業(yè) ?2. 低級(jí)調(diào)度 (Low Level Scheduling) 微觀調(diào)度1) 非搶占方式 (Non-preemptive Mode) 優(yōu)點(diǎn)：實(shí)現(xiàn)簡單、系統(tǒng)開銷小。調(diào)度時(shí)機(jī)： 正在執(zhí)行的進(jìn)程執(zhí)行完畢退出 發(fā)生某事件而被阻塞(外部原因) 執(zhí)行中的進(jìn)程提出阻塞請(qǐng)求(自我原因)2) 搶占方式 (Preemptive Mode) 優(yōu)點(diǎn)：處理及時(shí)，實(shí)現(xiàn)復(fù)雜 搶占的時(shí)機(jī)：具有搶先權(quán)的進(jìn)程創(chuàng)建就緒 具有搶先權(quán)的進(jìn)程被喚醒進(jìn)入就緒 具有搶先權(quán)的進(jìn)程從掛起進(jìn)入就緒3. 中級(jí)調(diào)度 (Intermediate-Level Scheduling) 中程調(diào)度 引入中級(jí)調(diào)度的主

29、要目的，是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。 中級(jí)調(diào)度的算法主要由內(nèi)存管理來實(shí)現(xiàn)，與高級(jí)調(diào)度和低級(jí)調(diào)度的算法不同。3.1.2 調(diào)度隊(duì)列模型1. 僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型2. 具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型3. 同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型3.1.3 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1. 面向用戶的準(zhǔn)則（1） 周轉(zhuǎn)時(shí)間短（批處理） 平均周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 W T/TS 而平均帶權(quán)周轉(zhuǎn)時(shí)間（2）響應(yīng)時(shí)間快（交互式系統(tǒng)）（3）截止時(shí)間的保證（實(shí)時(shí)系統(tǒng)）（4）優(yōu)先權(quán)準(zhǔn)則（特權(quán)處理）2. 面向系統(tǒng)的準(zhǔn)則（1） 系統(tǒng)吞吐量高（批處理）（2） 處理機(jī)利用率好（所有的）（3）各類資源的平衡利用（所有的

30、） 符合習(xí)慣思維（交互式） 具有前瞻預(yù)測（實(shí)時(shí)系統(tǒng)）3.2 調(diào)度算法3.2.1 先來先服務(wù)和短作業(yè) （ 進(jìn)程） 優(yōu)先調(diào)度算法1. 先來先服務(wù)調(diào)度算法2. 短作業(yè) （進(jìn)程 ）優(yōu)先調(diào)度算法FCFS的特點(diǎn)比較有利于長作業(yè)，而不利于短作業(yè)。有利于CPU繁忙的作業(yè)，而不利于I/O繁忙的作業(yè)。SJF 的特點(diǎn)優(yōu)點(diǎn)：比FCFS改善平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間，縮短作業(yè)的等待時(shí)間；提高系統(tǒng)的吞吐量;缺點(diǎn)： 對(duì)長作業(yè)非常不利，可能長時(shí)間得不到執(zhí)行；未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)先 級(jí)；難以準(zhǔn)確估計(jì)作業(yè)（進(jìn)程）的執(zhí)行時(shí)間，從而影響調(diào)度性能。SJF 的變型. “最短剩余時(shí)間優(yōu)先” SRT（ShortestRe

31、maining Time） 允許比當(dāng)前進(jìn)程剩余時(shí)間更短的進(jìn)程來搶占 . “最高響應(yīng)比優(yōu)先” HRRN（HighestResponse Ratio Next）響應(yīng)比 R = （ 等待時(shí)間 + 要求執(zhí)行時(shí)間 ） / 要 求執(zhí)行時(shí)間是FCFS和SJF的折衷3.2.2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法1. 優(yōu)先權(quán)調(diào)度算法的類型1）非搶占式優(yōu)先權(quán)算法2）搶占式優(yōu)先權(quán)調(diào)度算法2. 優(yōu)先權(quán)的類型1） 靜態(tài)優(yōu)先級(jí)創(chuàng)建進(jìn)程時(shí)就確定，直到進(jìn)程終止前都不改變。通常是一個(gè)整數(shù)。 依據(jù)：進(jìn)程類型(系統(tǒng)進(jìn)程優(yōu)先級(jí)較高)對(duì)資源的需求(對(duì) CPU和內(nèi)存需求較少的進(jìn)程，優(yōu)先級(jí)較高) 用戶要求(緊迫程度和付費(fèi)多少)2) 動(dòng)態(tài)優(yōu)先權(quán) 在創(chuàng)建進(jìn)

32、程時(shí)賦予的優(yōu)先級(jí)，在進(jìn)程運(yùn)行過程中可 以自動(dòng)改變，以便獲得更好的調(diào)度性能 . 在就緒隊(duì)列中，等待時(shí)間延長則優(yōu)先級(jí)提高，從 而使優(yōu)先級(jí)較低的進(jìn)程在等待足夠的時(shí)間后，其優(yōu)先 級(jí)提高到可被調(diào)度執(zhí)行 進(jìn)程每執(zhí)行一個(gè)時(shí)間片，就降低其優(yōu)先級(jí)，從而 一個(gè)進(jìn)程持續(xù)執(zhí)行時(shí)，其優(yōu)先級(jí)降低到出讓 CPU3. 高響應(yīng)比優(yōu)先調(diào)度算法3.2.3 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法1. 時(shí)間片輪轉(zhuǎn)法 Round Robin Scheduling list of runnable processes list of runnable processes after B uses up its quantum2. 多級(jí)反饋隊(duì)列調(diào)度算法(

33、Round Robin with Multiple Feedback) 多級(jí)反饋隊(duì)列算法是時(shí)間片輪轉(zhuǎn)算法和優(yōu) 先級(jí)算法的綜合和發(fā)展。優(yōu)點(diǎn)： 為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時(shí)間而照顧 短進(jìn)程 為獲得較好的 I/O 設(shè)備利用率和縮短響應(yīng)時(shí)間而 照顧 I/O 型進(jìn)程 不必估計(jì)進(jìn)程的執(zhí)行時(shí)間，動(dòng)態(tài)調(diào)節(jié) A scheduling algorithm with four priority classes PS3. 多級(jí)反饋隊(duì)列調(diào)度算法的性能(1) 終端型作業(yè)用戶。(2) 短批處理作業(yè)用戶。(3) 長批處理作業(yè)用戶。3.2a 實(shí)時(shí)調(diào)度 Schedulable real-time system .Given

34、m periodic events event i occurs within period Pi and requires Ci secondsThen the load can only be handled if We will discuss in the multimedia OS3.3 產(chǎn)生死鎖的原因和必要條件3.3.1 產(chǎn)生死鎖的原因(1) 互斥資源分配不當(dāng)(2) 進(jìn)程間推進(jìn)順序不當(dāng)1. 競爭資源引起進(jìn)程死鎖1) 可剝奪和非剝奪性資源2) 競爭非剝奪性資源3) 競爭臨時(shí)性資源ResourcesExamples of computer resources-prin terstape

35、 drives-tablesProcesses need access to resources in reasonable orderSuppose a process holds resource A and requests resource Bat same time another process holds B and requests A both are blocked and remain soResources ResourcesResourcesTwo process resource trajectories2. 進(jìn)程推進(jìn)順序不當(dāng)引起死鎖Introduction to

36、DeadlocksFormal definition :A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can causeUsually the event is release of a currently held resourceNone of the processes can runrelease resourcesbe awakened3.3.2 產(chǎn)生死鎖的四個(gè)必要條件(1) 互斥條件(2)

37、 請(qǐng)求和保持條件(3) 不剝奪條件(4) 環(huán)路等待條件3.3.3 處理死鎖的基本方法(1) 忽略死鎖(2) 檢測和解除死鎖(3) 避免死鎖(4) 預(yù)防死鎖3.4 解決死鎖的方法3.4.1 忽略死鎖1. 鴕鳥算法死鎖發(fā)生的概率小解決死鎖的代價(jià)太大3.4.2 死鎖的檢測與解除 死鎖的檢測1. 資源分配圖 (Resource Allocation Graph)Detection with One Resource of EachTypeNote the resource ownership and requestsA cycle can be found within the grap

38、h, denoting deadlockT2. 死鎖定理3. 死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)Detection with Multiple Resource of EachTypeAn example for the deadlock detection algorithm 死鎖的解除(1) 剝奪資源 (2) 回溯到還原點(diǎn)(3) 撤消進(jìn)程 (4) 重起系統(tǒng)3.4.3 死鎖的避免 . 安全和不安全狀態(tài)安全狀態(tài)之例：假定系統(tǒng)中有三個(gè)進(jìn)程 P1、P2和P3,共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求10臺(tái)磁帶機(jī)，P2和P3分別要求4臺(tái)和9臺(tái)。假 設(shè)在TO時(shí)刻，進(jìn)程P1、P2和P3已分別獲得

39、5臺(tái)、2臺(tái)和2臺(tái)磁帶 機(jī)，尚有 3臺(tái)空閑未分配，如下表所示：進(jìn)程最大需求已分配可用P1P2P3104952 利用銀行家算法避免死鎖一個(gè)銀行家把他的固定資金( capital )貸給若干顧客。只要不出現(xiàn)一個(gè)顧客借走所有資金后還不夠，銀行家的 資金應(yīng)是安全的。銀行家需 一個(gè)算法保證借出去的資金 在有限時(shí)間內(nèi)可收回。3.4.4 預(yù)防死鎖1. 摒棄互斥條件2. 摒棄“請(qǐng)求和保持” 條件3. 摒棄“不剝奪” 條件4. 摒棄“環(huán)路等待” Attacking the Mutual Exclusion ConditionSome devices (such as printer) can b

40、e spooled only the printer daemon uses printer resource thus deadlock for printer eliminated Not all devices can be spooledPCB,HD .Principle: avoid assigning resource when not absolutely necessary as few processes as possible actually claim the resource Attacking the Hold and Wait ConditionRequire p

41、rocesses to request resources before startinga process never has to wait for what it needs .Problemsmay not know required resources at start of run also ties up resources other processes could be using Variation:process must give up all resources then request all immediately needed Attacking the No

42、Preemption Condition This is not a viable option Consider a process given the printer halfway through its job now forcibly take away printer!?Attacking the Circular Wait Condition Normally ordered resources A resource graph9 Summary of approaches to deadlock prevention 預(yù)防死鎖的各種分類對(duì)策 本章重要習(xí)題分析第四章存儲(chǔ)器管理4.

43、1 定位和重定位4.2 簡單連續(xù)分配方式4.3 基本頁式存儲(chǔ)管理方式4.4 基本段式存儲(chǔ)管理方式4.5 段頁式存儲(chǔ)管理4.6 虛擬存儲(chǔ)器4.7 請(qǐng)求式分頁的基本原理4.8 頁面置換算法Relocation and ProtectionCannot be sure where program will be loaded inmemoryaddress locations of variables, code routines cannot beabsolutemust keep a program out of other processes partitionsUse base and li

44、mit valuesaddress locations added to base value to map tophysical addressaddress locations larger than limit value is an error4.1 定位和重定位4.1.1 程序的裝入1. 絕對(duì)裝入方式 (Absolute Loading Mode) 程序中所使用的絕對(duì)地址，既可在編譯或匯編時(shí)給出，也可由程序員直接賦予。例如：ORG 1000Hdfb309adfb309a00f39761b3c446 00f39761b3c446 00f39762. 可重定位裝入方式 (Relocati

45、on Loading Mode)P1P2P3P4P53. 動(dòng)態(tài)運(yùn)行時(shí)裝入方式 (dynamic Run-time Loading) 動(dòng)態(tài)運(yùn)行時(shí)的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對(duì)地址轉(zhuǎn) 換為絕對(duì)地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。因此，裝入內(nèi)存后 的所有地址都仍是相對(duì)地址。4.1.2 程序的鏈接1. 靜態(tài)鏈接方式 (Static Linking) 在將這幾個(gè)目標(biāo)模塊裝配成一個(gè)裝入模塊時(shí)，須解決以下兩個(gè)問題：(1) 對(duì)相對(duì)地址進(jìn)行修改。(2) 變換外部調(diào)用符號(hào)。2. 裝入時(shí)動(dòng)態(tài)鏈接 (Load time Dynamic Linking) 裝入時(shí)動(dòng)態(tài)鏈接

46、方式有以下優(yōu)點(diǎn)：(1) 便于修改和更新。(2) 便于實(shí)現(xiàn)對(duì)目標(biāo)模塊的共享。3. 運(yùn)行時(shí)動(dòng)態(tài)鏈接 (Run-time Dynamic Linking)在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個(gè)被調(diào)用模塊尚未裝入內(nèi)存時(shí)，立即由OS去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的 內(nèi)存空間。4.2 簡單連續(xù)分配方式4.2.1 單一連續(xù)分配 這是最簡單的一種存儲(chǔ)管理方式，但只能用于單用戶、單任務(wù)的操作系統(tǒng)中。采用這種存 儲(chǔ)管理方式時(shí)，可把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內(nèi)存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內(nèi)存空間，提供給用戶使用。

47、Mono programmingThree simple ways of organizing memoryan operating system with one user process無分區(qū)4.2.2 固定分區(qū)分配1. 劃分分區(qū)的方法(1) 分區(qū)大小相等，即使所有的內(nèi)存分區(qū)大小相等。(2) 分區(qū)大小不等。2. 內(nèi)存分配等額固定分區(qū)差額固定分區(qū)Multiprogramming with Fixed PartitionsFixed memory partitionsseparate input queues for each partitionsingle input queue動(dòng)態(tài)分區(qū)4.

48、2.3 動(dòng)態(tài)分區(qū)分配 碎片 Hole1. 分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)(1) 空閑分區(qū)表。(2) 空閑分區(qū)鏈。Memory Management with BitMapsPart of memory with 5 processes, 3 holestick marks show allocation unitsshaded regions are freeCorresponding bit mapSame information as a listMemory Management with LinkedListsFour neighbor combinations for the terminat

49、ingprocess X Fragment碎片2. 分區(qū)分配算法(1) 首次適應(yīng)算法 FF。(2) 循環(huán)首次適應(yīng)算法。(3) 最佳適應(yīng)算法。(4) 最壞適應(yīng)算法。(5) 快速適應(yīng)算法。Pointer Coming a New process is 16K Worst fit4.2.4 可重定位分區(qū)分配1. 動(dòng)態(tài)重定位的引入2. 動(dòng)態(tài)重定位的實(shí)現(xiàn)3. 動(dòng)態(tài)重定位分區(qū)分配算法4.2.5 對(duì)換 (Swapping)1. 對(duì)換的引入2. 對(duì)換空間的管理3. 進(jìn)程的換出與換入(1) 進(jìn)程的換出。 每當(dāng)一進(jìn)程由于創(chuàng)建子進(jìn)程而需要更多的內(nèi)存空間， 但又無足夠的內(nèi)存空間等情況發(fā)生時(shí)，系統(tǒng)應(yīng)將某進(jìn)程換 出。(2

50、) 進(jìn)程的換入。 系統(tǒng)應(yīng)定時(shí)地查看所有進(jìn)程的狀態(tài)，從中找出就緒 狀態(tài)但已換出的進(jìn)程，將其中換出時(shí)間(換出到磁盤上 ) 最久的進(jìn)程作為換入進(jìn)程，將之換入，直至已無可換入的進(jìn) 程或無可換出的進(jìn)程為止。4.3 基本分頁存儲(chǔ)管理方式4.3.1 頁面與頁表1. 頁面1) 頁面和物理塊2) 頁面大小 在分頁系統(tǒng)中的頁面其大小應(yīng)適中。頁面若太小，一方面雖然可使內(nèi)存碎片減小，從而減 少了內(nèi)存碎片的總空間，有利于提高內(nèi)存利用率，但另一方面也會(huì)使每個(gè)進(jìn)程占用較多的 頁面，從而導(dǎo)致進(jìn)程的頁表過長，占用大量內(nèi)存；此外，還會(huì)降低頁面換進(jìn)換出的效率。 然而，如果選擇的頁面較大，雖然可以減少頁表的長度，提高頁面換進(jìn)換出的速

51、度，但卻 又會(huì)使頁內(nèi)碎片增大。因此，頁面的大小應(yīng)選擇得適中，且頁面大小應(yīng)是 2 的冪，通常為 512 B8 KB 。Page Size Small page size Advantages less internal fragmentationbetter fit for various data structures, code sections less unused program in memory Disadvantagesprograms need many pages, larger page tables0Page size large, the fragmentation b

52、igPage size small, the page table bigFragmentation 內(nèi)碎片Most program ' s pieces are less than 4KA. 0A. 1A. 2A.3B. 0B. 1B. 2C. 0C. 1C. 2C.3Page SizeOverhead due to page table and internal fragmentation.Wheres = average process size in bytes p = page size in bytes e = page entry Optimized when inter

53、nal fragmentation page table space2. 地址結(jié)構(gòu) 分頁地址中的地址結(jié)構(gòu)如下： 頁號(hào) P 位移量 W 31 12 11 0A,頁面的大小在這樣的環(huán)境下，頁對(duì)某特定機(jī)器， 其地址結(jié)構(gòu)是一定的。若給定一個(gè)邏輯地址空間中的地址為 為L,則頁號(hào)P和頁內(nèi)地址d可按下式求得：3. 頁表4.3.2 地址變換機(jī)構(gòu)1. 基本的地址變換機(jī)構(gòu)2. 具有快表的地址變換機(jī)構(gòu)4.3.3 兩級(jí)和多級(jí)頁表 現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間 (232264) 。表就變得非常大，要占用相當(dāng)大的內(nèi)存空間?？梢圆捎眠@樣兩個(gè)方法來解決這一問題： 采用離散分配方式來解決難以找到一塊連續(xù)的

54、大內(nèi)存空間的問題：只將當(dāng)前需要的部 分頁表項(xiàng)調(diào)入內(nèi)存，其余的頁表項(xiàng)仍駐留在磁盤上，需要時(shí)再調(diào)入。1. 兩級(jí)頁表 (Two-Level Page Table)邏輯地址結(jié)構(gòu)可描述如下：Windows 的多級(jí)頁表結(jié)構(gòu)2. 多級(jí)頁表對(duì)于 32 位的機(jī)器，采用兩級(jí)頁表結(jié)構(gòu)是合適的；但對(duì)于 64 位的機(jī)器，如果頁面大小仍采 用 4 KB 即 212 B ，那么還剩下 52 位，假定仍按物理塊的大小 (212 位) 來劃分頁表，則將余 下的42位用于外層頁號(hào)。此時(shí)在外層頁表中可能有4096 G個(gè)頁表項(xiàng)，要占用16384 GB的連續(xù)內(nèi)存空間。必須采用多級(jí)頁表，將外層頁表再進(jìn)行分頁，也是將各分頁離散地裝入到 不

55、相鄰接的物理塊中，再利用第 2 級(jí)的外層頁表來映射它們之間的關(guān)系。Inverted Page TablesComparison of a traditional page table with an invertedpage table4.4 基本分段存儲(chǔ)管理方式4.4.1 分段存儲(chǔ)管理方式的引入引入分段存儲(chǔ)管理方式，主要是為了滿足用戶和程序員的下述一系列需要：1) 方便編程2) 信息共享3) 信息保護(hù)4) 動(dòng)態(tài)增長5) 動(dòng)態(tài)鏈接4.4.2 分段系統(tǒng)的基本原理1. 分段分段地址中的地址具有如下結(jié)構(gòu)：段號(hào)段內(nèi)地址31 16 15 02. 段表4. 分頁和分段的主要區(qū)別(1) 頁是信息的物理單位，分頁是為實(shí)現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存 的利用率。或者說，分頁僅僅是由于系統(tǒng)管理的需要而不是用戶的需要。段則是信息的邏 輯單位，它含有一組其意義相對(duì)完整的信息。分段的目的是為了能更好地滿足用戶的需要。(2) 頁的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分為頁號(hào)和頁內(nèi)地址兩部分，是由 機(jī)器硬件實(shí)現(xiàn)的，因而在系統(tǒng)中只能有一種大小的頁面；而段的長度卻不固定，決定于用 戶所編寫的程序，通常由編譯程序在對(duì)源程序進(jìn)行編譯時(shí)，根據(jù)信息的性質(zhì)來劃分。(3) 分頁的作業(yè)地址空間是一維的，即單一的線性地址空間，程序員只需利用一個(gè)記憶符， 即可表示一個(gè)地址；而分段的作業(yè)地址空間則