操作系統(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. 可擴充性。各自獨立發(fā)展4. 開放性。移植和互操作1.1.2 操作系統(tǒng)的作用1. OS作為用戶與計算機硬件系統(tǒng)之間的接口OS處于用戶與計算機硬件系統(tǒng)之間，用戶通過OS來使用計算機系統(tǒng)。(從用戶角度來看，來操縱計算機。)(1) 命令輸入。形式又分為以下幾種：命令行(Comma nd Line In put ):由OS提供的一組聯(lián)機命令(語言)，用戶可通過鍵盤輸 入有關(guān)命令，來直接操縱計算機系統(tǒng)。圖形用戶界面( GUI )：用戶通過顯示設(shè)備上的窗口

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

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

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

5、haring System) 的產(chǎn)生 如果說，推動多道批處理系統(tǒng)形成和發(fā)展的主要動力，是提高資源利用率和系統(tǒng)吞吐量， 那么，推動分時系統(tǒng)形成和發(fā)展的主要動力，則是用戶的需求。用戶的需求具體表現(xiàn)在以 下幾個方面：(1) 人機交互。(2) 共享主機。(3) 便于用戶上機。2. 分時系統(tǒng)實現(xiàn)中的關(guān)鍵問題 分時系統(tǒng)性能好壞的主要指標(biāo)是響應(yīng)時間。(1) 及時接收。(2) 及時處理。(3) 符合使用習(xí)慣。在 OS 中引入多道程序設(shè)計技術(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)缺點(1) 資源利用率高。(2) 系統(tǒng)吞吐量大。(3) 平均周轉(zhuǎn)時間長。(4) 無交互能力。4. 多道批處理系統(tǒng)需要解決的問題(1) 處理機管理問題。(2) 內(nèi)存管理問題。(3) I/O 設(shè)備管理問題。(4) 文件管理問題。(5) 作業(yè)管理問題。3. 分時系統(tǒng)的特征(1) 多路性。 (2) 獨立性。 (3) 及時性。 (4) 交互性。1.2.5 實時系統(tǒng)實時系統(tǒng) (Real-Time System) 是指系統(tǒng)能及時 ( 或即時 ) 響應(yīng)外部事件的請求，在規(guī)定的間 內(nèi)完成對該事件的處理，并控制所有實時任務(wù)協(xié)調(diào)一致地運行。1.3 操作系統(tǒng)的基本特性1.3.1

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

8、及其特征2.1.2 前趨圖前趨圖 (Precedence Graph) 是一個有向無循環(huán)圖，記為 DAG(Directed Acyclic Graph) ， 用于描述進程之間執(zhí)行的前后關(guān)系。2.1.3 程序的并發(fā)執(zhí)行及其特征2.1.4 進程的特征與狀態(tài)One program which has an independent function works on certain data set dynamically and allocate resources dynamically What is a process? 一個具有一定獨立功能的程序?qū)δ硞€數(shù)據(jù) 集合上的一次動態(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. 進程的三種基本狀態(tài)1) 就緒 (Ready) 狀態(tài) 2) 執(zhí)行狀態(tài) 3) 阻塞狀態(tài)2.1.5 進程控制塊1. 進程控制塊的作用進程控制塊的作用是記錄一個獨立運行的進程的基本信息?；蛘哒f，OS是根據(jù)PCB來對并發(fā)執(zhí)行的進程進行控制和管理的。2. 進程控制塊中的信息3. 進程控制塊的組織方式1) 鏈接方式 2) 索引方式2.2 進程控制2.2.1 進程的創(chuàng)建(1) 用戶登錄。(2) 作業(yè)調(diào)度。(3) 提供服務(wù)。(4) 應(yīng)用請求。(1) 申請空白 PCB。(2) 為新進程分配資源。(3) 初始化進程控制塊。(4) 將新進程插入就緒隊列，如果進程就緒隊列能夠接納新進程，便將新進程插入就 緒隊列。

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

12、) 外界干預(yù)(非自愿的)2.2.3 進程的阻塞與喚醒1. 引起進程阻塞和喚醒的事件1 )請求系統(tǒng)服務(wù)2) 啟動某種操作3) 新數(shù)據(jù)尚未到達4) 無新工作可做2.2.4 進程的掛起與激活2.3 進程同步2.3.1 進程同步的基本概念1. 兩種形式的制約關(guān)系(1) 間接相互制約關(guān)系。(2) 直接相互制約關(guān)系。2. 臨界資源 (Critical Resource)3. 臨界區(qū) (critical section)一個飛機訂票系統(tǒng)，兩個終端，運行T1、T2 進程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. 同步機制應(yīng)遵循的規(guī)則(1) 空閑讓進。(2) 忙則等待。(3) 有限等待。(4) 讓權(quán)等待。 (Peterson ' s Algorithm) ： 先修改、后檢查、后修改者等待正確的算法 turn=j; 描述可進入的進程(同時修改標(biāo)志時) 在進入?yún)^(qū)先修改后檢查，并檢查并發(fā)修改的先后： 檢查對方 flag ， 如果不在臨界區(qū)則自己進入空閑則入 否則再檢查 turn ： 保存的是較晚的一次賦值，則較晚的進 程等待，較早的進程進入先到先入，后到

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 信號量機制1. 整型信號量最初由 Dijkstra 把整型信號量定義為一個整型量， 僅能通過初始化和兩個標(biāo)準(zhǔn)的原子操作 (Atomic Operation) wait(S) 和 signal(S) 來訪問。兩個操作被分別稱為P、 V 操作(primiti

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

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

17、le of a monitor2.4 經(jīng)典進程的同步問題2.4.1 生產(chǎn)者消費者問題1. 利用記錄型信號量解決生產(chǎn)者消費者問題 Dining Philosophers Philosophers eat/think Eating needs 2 forks Pick one fork at a time How to prevent deadlock2.4.2 哲學(xué)家進餐問題 讓奇數(shù)號的哲學(xué)家先取右手邊的筷子，讓偶數(shù)號的哲學(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. 利用記錄型信號量解決讀者寫者問題The Sleeping Barber ProblemThe SleepingBarberProblemSolution to sleepingbarber problemShared memory( 共享內(nèi)存 )Message( 消息機制 )Pipe( 管道 )Signal( 信號 )Socket( 套接字 )Interpro

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

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

21、生產(chǎn)者消費者問題。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); 將一個消息發(fā)送到指定信箱； Receive( box, message);

22、 從指定信箱中接收一個消息；3. 進程同步方式(1) 發(fā)送進程阻塞、接收進程阻塞。(2) 發(fā)送進程不阻塞、接收進程阻塞。(3) 發(fā)送進程和接收進程均不阻塞。2.6 線程2.6.1 線程的基本概念 為使程序能并發(fā)執(zhí)行，系統(tǒng)還必須進行以下的一系列操作。1) 創(chuàng)建進程2) 撤消進程3) 進程切換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) 輕型實體(容易創(chuàng)建和撤銷) 。(2) 獨立調(diào)度和分派的基本單位。(3) 可并發(fā)執(zhí)行。(4) 共享進程資源。(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) 線程運行狀態(tài)。5. 多線程OS中的進程 在多線程OS中，進程是作為擁有系統(tǒng)資源的基本單位，通常的進程都包含多個線程并為它 們提供資源，但此時的進程就不再作為一個執(zhí)行的實體。多線程OS中的進程有以下屬性:(1) 作為系統(tǒng)資源分配的單位。

24、(2) 可包括多個線程。(3) 進程不是一個可執(zhí)行的實體。4. 線程的創(chuàng)建和終止 在多線程OS環(huán)境下，應(yīng)用程序在啟動時，通常僅有一個線程在執(zhí)行，該線程被人們稱為初 始化線程。它可根據(jù)需要再去創(chuàng)建若干個線程。終止線程的方式有兩種:一種是在線程完 成了自己的工作后自愿退出；另一種是線程在運行中出現(xiàn)錯誤或由于某種原因而被其它線 程強行終止。2.6.2 線程間的同步和通信1. 互斥鎖 (mutex) 互斥鎖是一種比較簡單的、用于實現(xiàn)線程間對資源互斥訪問的機制。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)核支持線程和用戶級線程1. 內(nèi)核支持線程 這里所謂的內(nèi)核支持線程，也都同樣是在內(nèi)核的支持下運行的，即無論是用戶進程中的線 程，還是系統(tǒng)進程中的線程，他們的創(chuàng)建、撤消和切換等，也是依靠內(nèi)核實現(xiàn)的。此外， 在內(nèi)核空間還為每一個內(nèi)核支持線程設(shè)置了一個線程控制塊，內(nèi)核是根據(jù)該控制塊而感知 某線程的存在的，并對其加以控制。Implementing Threads in the Kernel A threads package managed by the k

26、ernel2. 用戶級線程 用戶級線程僅存在于用戶空間中。對于這種線程的創(chuàng) 建、撤消、線程之間的同步與通信等功能，都無須利用 系統(tǒng)調(diào)用來實現(xiàn)。對于用戶級線程的切換，通常是發(fā)生在 一個應(yīng)用進程的諸多線程之間，這時，也同樣無須內(nèi)核的 支持。由于切換的規(guī)則遠比進程調(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第三章處理機調(diào)度與死鎖3.1 處理機調(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 高級、中級和低級調(diào)度Three level schedulingFCFSSJFHRFSRFFCFSSPFRRPS1. 高級調(diào)度 (High Scheduling) 宏觀調(diào)度在每次執(zhí)行作業(yè)調(diào)度時，都須做出以下兩個決定

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

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

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

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

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

33、Round Robin with Multiple Feedback) 多級反饋隊列算法是時間片輪轉(zhuǎn)算法和優(yōu) 先級算法的綜合和發(fā)展。優(yōu)點： 為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時間而照顧 短進程 為獲得較好的 I/O 設(shè)備利用率和縮短響應(yīng)時間而 照顧 I/O 型進程 不必估計進程的執(zhí)行時間，動態(tài)調(diào)節(jié) A scheduling algorithm with four priority classes PS3. 多級反饋隊列調(diào)度算法的性能(1) 終端型作業(yè)用戶。(2) 短批處理作業(yè)用戶。(3) 長批處理作業(yè)用戶。3.2a 實時調(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) 進程間推進順序不當(dāng)1. 競爭資源引起進程死鎖1) 可剝奪和非剝奪性資源2) 競爭非剝奪性資源3) 競爭臨時性資源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. 進程推進順序不當(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)生死鎖的四個必要條件(1) 互斥條件(2)

37、 請求和保持條件(3) 不剝奪條件(4) 環(huán)路等待條件3.3.3 處理死鎖的基本方法(1) 忽略死鎖(2) 檢測和解除死鎖(3) 避免死鎖(4) 預(yù)防死鎖3.4 解決死鎖的方法3.4.1 忽略死鎖1. 鴕鳥算法死鎖發(fā)生的概率小解決死鎖的代價太大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) 回溯到還原點(3) 撤消進程 (4) 重起系統(tǒng)3.4.3 死鎖的避免 . 安全和不安全狀態(tài)安全狀態(tài)之例：假定系統(tǒng)中有三個進程 P1、P2和P3,共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和9臺。假 設(shè)在TO時刻，進程P1、P2和P3已分別獲得

39、5臺、2臺和2臺磁帶 機，尚有 3臺空閑未分配，如下表所示：進程最大需求已分配可用P1P2P3104952 利用銀行家算法避免死鎖一個銀行家把他的固定資金( capital )貸給若干顧客。只要不出現(xiàn)一個顧客借走所有資金后還不夠，銀行家的 資金應(yīng)是安全的。銀行家需 一個算法保證借出去的資金 在有限時間內(nèi)可收回。3.4.4 預(yù)防死鎖1. 摒棄互斥條件2. 摒棄“請求和保持” 條件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ù)防死鎖的各種分類對策 本章重要習(xí)題分析第四章存儲器管理4.

43、1 定位和重定位4.2 簡單連續(xù)分配方式4.3 基本頁式存儲管理方式4.4 基本段式存儲管理方式4.5 段頁式存儲管理4.6 虛擬存儲器4.7 請求式分頁的基本原理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. 絕對裝入方式 (Absolute Loading Mode) 程序中所使用的絕對地址，既可在編譯或匯編時給出，也可由程序員直接賦予。例如：ORG 1000Hdfb309adfb309a00f39761b3c446 00f39761b3c446 00f39762. 可重定位裝入方式 (Relocati

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

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

48、2.3 動態(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. 動態(tài)重定位的引入2. 動態(tài)重定位的實現(xiàn)3. 動態(tài)重定位分區(qū)分配算法4.2.5 對換 (Swapping)1. 對換的引入2. 對換空間的管理3. 進程的換出與換入(1) 進程的換出。 每當(dāng)一進程由于創(chuàng)建子進程而需要更多的內(nèi)存空間， 但又無足夠的內(nèi)存空間等情況發(fā)生時，系統(tǒng)應(yīng)將某進程換 出。(2

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

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

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

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