考研計算機專業(yè)課強化班《操作系統(tǒng)》《計算機網(wǎng)絡》《計算機組成原理》

-PAGE156--PAGE157-《操作系統(tǒng)》第一章操作系統(tǒng)概述1.1操作系統(tǒng)的目標和作用1.1.1操作系統(tǒng)的目標目標：1.方便性。不需要人人都是程序員2.有效性。工作協(xié)調(diào)高效3.可擴充性。各自獨立發(fā)展4.開放性。移植和互操作1.1.2操作系統(tǒng)的作用1.OS作為用戶與計算機硬件系統(tǒng)之間的接口OS處于用戶與計算機硬件系統(tǒng)之間，用戶通過OS來使用計算機系統(tǒng)。（從用戶角度來看，來操縱計算機。）(1)命令輸入。形式又分為以下幾種：命令行（CommandLineInput）：由OS提供的一組聯(lián)機命令（語言），用戶可通過鍵盤輸入有關命令，來直接操縱計算機系統(tǒng)。圖形用戶界面（GUI）：用戶通過顯示設備上的窗口和圖標來操縱計算機系統(tǒng)和運行自己的程序。自然輸入方式（NUI）：用戶通過語音識別輸入來操縱計算機系統(tǒng)和運行自己的程序。(2)系統(tǒng)調(diào)用方式（SystemCall）。OS提供了一組系統(tǒng)調(diào)用，用戶可在自己的應用程序中通過相應的使用編程調(diào)用API1.1.3推動操作系統(tǒng)發(fā)展的主要動力1.不斷提高計算機資源利用率2.方便用戶3.器件的不斷更新?lián)Q代4.計算機體系結構的不斷發(fā)展用戶的需求是推動OS發(fā)展的根本動力2.OS作為計算機系統(tǒng)資源的管理者在一個計算機系統(tǒng)中通常都含有各種各樣的硬件和軟件資源。需要空間和時間來使用這些資源，OS合理調(diào)配和使用。（這是從管理者的角度來看）3.OS用作擴展機、虛擬機隱藏了計算機具體細節(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.脫機輸入/輸出(Off-LineI/O)方式這種脫機I/O方式的主要優(yōu)點如下：(1)減少了CPU的空閑時間。(2)提高I/O速度。

1.2.2單道批處理系統(tǒng)1.單道批處理系統(tǒng)(SimpleBatchProcessingSystem)的處理過程2.單道批處理系統(tǒng)的特征該系統(tǒng)的主要特征如下：(1)自動性。(2)順序性。(3)單道性。1.2.3多道批處理系統(tǒng)1.多道程序設計的基本概念多道批處理系統(tǒng)(MultiprogrammedBatchProcessingSystem)。在該系統(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)(TimeSharingSystem)的產(chǎn)生如果說，推動多道批處理系統(tǒng)形成和發(fā)展的主要動力，是提高資源利用率和系統(tǒng)吞吐量，那么，推動分時系統(tǒng)形成和發(fā)展的主要動力，則是用戶的需求。用戶的需求具體表現(xiàn)在以下幾個方面：(1)人機交互。(2)共享主機。(3)便于用戶上機。2.分時系統(tǒng)實現(xiàn)中的關鍵問題分時系統(tǒng)性能好壞的主要指標是響應時間。(1)及時接收。(2)及時處理。(3)符合使用習慣。在OS中引入多道程序設計技術可帶來以下好處：(1)提高CPU的利用率。(2)可提高內(nèi)存和I/O設備利用率。(3)增加系統(tǒng)吞吐量。2.多道批處理系統(tǒng)的特征(1)多道性。(2)無序性。(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設備管理問題。(4)文件管理問題。(5)作業(yè)管理問題。3.分時系統(tǒng)的特征(1)多路性。(2)獨立性。(3)及時性。(4)交互性。1.2.5實時系統(tǒng)實時系統(tǒng)(Real-TimeSystem)是指系統(tǒng)能及時(或即時)響應外部事件的請求，在規(guī)定的間內(nèi)完成對該事件的處理，并控制所有實時任務協(xié)調(diào)一致地運行。1.3操作系統(tǒng)的基本特性1.3.1并發(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)中的所謂虛擬，是指通過某種技術把一個物理實體變?yōu)槿舾蓚€邏輯上的對應物。1.3.4異步性(Asynchronism)在多道程序環(huán)境下，多個進程是以停停走走的方式運行。失去封閉性第二章進程管理2.1進程的基本概念2.1.1程序的順序執(zhí)行及其特征2.1.2前趨圖前趨圖(PrecedenceGraph)是一個有向無循環(huán)圖，記為DAG(DirectedAcyclicGraph)，用于描述進程之間執(zhí)行的前后關系。2.1.3程序的并發(fā)執(zhí)行及其特征2.1.4進程的特征與狀態(tài)OneprogramwhichhasanindependentfunctionworksoncertaindatasetdynamicallyandallocateresourcesdynamicallyWhatisaprocess?一個具有一定獨立功能的程序?qū)δ硞€數(shù)據(jù)集合上的一次動態(tài)執(zhí)行過程和資源分配過程Code，Data，ProcessTableTheDifferenceBetweenProcessandProgramProcessisdynamic,andtheprogramisstaticProcessistemporary,theprogramispermanenceTheelementsofprocessandprogramisdifferentCodeData–PTTherelationshipsofprocessandprogramarecomplexCreateSystemcall2.進程的三種基本狀態(tài)1)就緒(Ready)狀態(tài)2)執(zhí)行狀態(tài)3)阻塞狀態(tài)2.1.5進程控制塊1.進程控制塊的作用進程控制塊的作用是記錄一個獨立運行的進程的基本信息。或者說，OS是根據(jù)PCB來對并發(fā)執(zhí)行的進程進行控制和管理的。2.進程控制塊中的信息3.進程控制塊的組織方式1)鏈接方式2)索引方式2.2進程控制2.2.1進程的創(chuàng)建(1)用戶登錄。(2)作業(yè)調(diào)度。(3)提供服務。(4)應用請求。(1)申請空白PCB。(2)為新進程分配資源。(3)初始化進程控制塊。(4)將新進程插入就緒隊列，如果進程就緒隊列能夠接納新進程，便將新進程插入就緒隊列。2.進程的終止過程(1)根據(jù)被終止進程的標識符，從PCB集合中檢索出該進程的PCB，從中讀出該進程的狀態(tài)。(2)若被終止進程正處于執(zhí)行狀態(tài)，應立即終止該進程的執(zhí)行，并置調(diào)度標志為真，用于指示該進程被終止后應重新進行調(diào)度。(3)若該進程還有子孫進程，還應將其所有子孫進程予以終止，以防他們成為不可控的進程。(4)將被終止進程所擁有的全部資源，或者歸還給其父進程，或者歸還給系統(tǒng)。(5)將被終止進程(它的PCB)從所在隊列(或鏈表)中移出，等待其他程序來搜集信息。2.2.2進程的終止1)正常結束（自愿的）2)異常結束普通錯誤退出（自愿的）致命錯誤退出（非自愿的）3)外界干預（非自愿的）2.2.3進程的阻塞與喚醒1.引起進程阻塞和喚醒的事件1)請求系統(tǒng)服務2)啟動某種操作3)新數(shù)據(jù)尚未到達4)無新工作可做2.2.4進程的掛起與激活2.3進程同步2.3.1進程同步的基本概念1.兩種形式的制約關系(1)間接相互制約關系。(2)直接相互制約關系。2.臨界資源(CriticalResource)3.臨界區(qū)(criticalsection)一個飛機訂票系統(tǒng)，兩個終端，運行T1、T2進程T1：……read(x);ifx>=1thenx:=x-1;write(x);……T2：……read(x);ifx>=1thenx:=x-1;write(x);……CriticalRegionsComingdatablocksSynchronization4.同步機制應遵循的規(guī)則(1)空閑讓進。(2)忙則等待。(3)有限等待。(4)讓權等待。(Peterson’sAlgorithm)：先修改、后檢查、后修改者等待正確的算法turn=j;描述可進入的進程（同時修改標志時）在進入?yún)^(qū)先修改后檢查，并檢查并發(fā)修改的先后：檢查對方flag，如果不在臨界區(qū)則自己進入－－空閑則入否則再檢查turn：保存的是較晚的一次賦值，則較晚的進程等待，較早的進程進入－－先到先入，后到等待MutualExclusionwithBusyWaitingEnteringandleavingacriticalregionusingtheTSLinstructionSleepandWakeupProducer-consumerproblemwithfatalracecondition2.3.2信號量機制1.整型信號量最初由Dijkstra把整型信號量定義為一個整型量，僅能通過初始化和兩個標準的原子操作(AtomicOperation)wait(S)和signal(S)來訪問。兩個操作被分別稱為P、V操作(primitive)。wait(S):whileS≤0donoopS∶=S-1;signal(S):S∶=S+1;2.記錄型信號量在整型信號量機制中的wait操作，只要是信號量S≤0，就會不斷地測試。因此，該機制并未遵循讓權等待的準則，而是使進程處于忙等的狀態(tài)。記錄型信號量機制，則是一種不存在忙等現(xiàn)象的進程同步機制。但在采取了讓權等待的策略后，又會出現(xiàn)多個進程等待訪問同一臨界資源的情況。為此，在信號量機制中，除了需要一個用于代表資源數(shù)目的整型變量value外，還應增加一個進程鏈表L，用于鏈接上述的所有等待進程。記錄型信號量是由于它采用了記錄型的數(shù)據(jù)結構而得名的。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進入就緒隊列;}SemaphoresTheproducer-consumerproblemusingsemaphoresMonitorsExampleofamonitor2.4經(jīng)典進程的同步問題2.4.1生產(chǎn)者消費者問題1.利用記錄型信號量解決生產(chǎn)者消費者問題DiningPhilosophersPhilosopherseat/thinkEatingneeds2forksPickoneforkatatimeHowtopreventdeadlock2.4.2哲學家進餐問題讓奇數(shù)號的哲學家先取右手邊的筷子，讓偶數(shù)號的哲學家先取左手邊的筷子。send(i)beginifimod2=0thenelse{{P(c[i]);P(c[i+1mod5]);P(c[i+1mod5]);P(c[i]);eat;eat;V(c[i+1mod5]);V(c[i]);V(c[i]);V(c[i+1mod5]);}}end2.4.3讀者寫者問題讀者-寫者問題描述TheReadersandWritersProblem1.利用記錄型信號量解決讀者寫者問題

TheSleepingBarberProblemTheSleepingBarberProblemSolutiontosleepingbarberproblemSharedmemory(共享內(nèi)存)Message(消息機制)Pipe(管道)Signal(信號)Socket(套接字)InterprocessCommunication2.5進程通信2.5.1進程通信的類型1.共享存儲器系統(tǒng)(SharedMemorySystem)(1)基于共享數(shù)據(jù)結構的通信方式。(2)基于共享存儲區(qū)的通信方式。2.消息傳遞系統(tǒng)(Messagepassingsystem)在消息傳遞系統(tǒng)中，進程間的數(shù)據(jù)交換，是以格式化的消息(message)為單位的；在計算機網(wǎng)絡中，又把message稱為報文。程序員直接利用系統(tǒng)提供的一組通信命令(原語)進行通信。3.管道(Pipe)通信管道是指用于連接一個讀進程和一個寫進程以實現(xiàn)他們之間通信的一個共享文件，又名pipe文件。這種方式首創(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,m1)表示將消息m1發(fā)送給接收進程P2;而原語Receive(P1，m1)則表示接收由P1發(fā)來的消息m1。不指定發(fā)送者的接收原語可表示為：Receive(id,message);利用直接通信原語，解決生產(chǎn)者消費者問題。repeat…produceaniteminnextp;…send(consumer,nextp);untilfalse;repeatreceive(producer,nextc);…consumetheiteminnextc;untilfalse;MessagePassing.Theproducer-consumerproblemwithNmessages2.間接通信方式(1)信箱的創(chuàng)建和撤消。(2)消息的發(fā)送和接收。Send(mailbox,message);將一個消息發(fā)送到指定信箱；Receive(mailbox,message);從指定信箱中接收一個消息；3.進程同步方式(1)發(fā)送進程阻塞、接收進程阻塞。(2)發(fā)送進程不阻塞、接收進程阻塞。(3)發(fā)送進程和接收進程均不阻塞。2.6線程2.6.1線程的基本概念為使程序能并發(fā)執(zhí)行，系統(tǒng)還必須進行以下的一系列操作。1)創(chuàng)建進程2)撤消進程3)進程切換1.線程的引入TheThreadModel(a)Threeprocesseseachwithonethread(b)OneprocesswiththreethreadsForExampleTheThreadModelEachthreadhasitsownstack2.線程的屬性(1)輕型實體（容易創(chuàng)建和撤銷）。(2)獨立調(diào)度和分派的基本單位。(3)可并發(fā)執(zhí)行。(4)共享進程資源。(5)適應硬件的發(fā)展TheThreadModelItemssharedbyallthreadsinaprocessItemsprivatetoeachthread

3.線程的狀態(tài)(1)狀態(tài)參數(shù)。(2)線程運行狀態(tài)。5.多線程OS中的進程在多線程OS中，進程是作為擁有系統(tǒng)資源的基本單位，通常的進程都包含多個線程并為它們提供資源，但此時的進程就不再作為一個執(zhí)行的實體。多線程OS中的進程有以下屬性：(1)作為系統(tǒng)資源分配的單位。(2)可包括多個線程。(3)進程不是一個可執(zhí)行的實體。4.線程的創(chuàng)建和終止在多線程OS環(huán)境下，應用程序在啟動時，通常僅有一個線程在執(zhí)行，該線程被人們稱為初始化線程。它可根據(jù)需要再去創(chuàng)建若干個線程。終止線程的方式有兩種：一種是在線程完成了自己的工作后自愿退出；另一種是線程在運行中出現(xiàn)錯誤或由于某種原因而被其它線程強行終止。2.6.2線程間的同步和通信1.互斥鎖(mutex)互斥鎖是一種比較簡單的、用于實現(xiàn)線程間對資源互斥訪問的機制。2.條件變量Useofabarrierprocessesapproachingabarrierallprocessesbutoneblockedatbarrierlastprocessarrives,allareletthrough2.6.3內(nèi)核支持線程和用戶級線程1.內(nèi)核支持線程這里所謂的內(nèi)核支持線程，也都同樣是在內(nèi)核的支持下運行的，即無論是用戶進程中的線程，還是系統(tǒng)進程中的線程，他們的創(chuàng)建、撤消和切換等，也是依靠內(nèi)核實現(xiàn)的。此外，在內(nèi)核空間還為每一個內(nèi)核支持線程設置了一個線程控制塊，內(nèi)核是根據(jù)該控制塊而感知某線程的存在的，并對其加以控制。ImplementingThreadsintheKernelAthreadspackagemanagedbythekernel2.用戶級線程用戶級線程僅存在于用戶空間中。對于這種線程的創(chuàng)建、撤消、線程之間的同步與通信等功能，都無須利用系統(tǒng)調(diào)用來實現(xiàn)。對于用戶級線程的切換，通常是發(fā)生在一個應用進程的諸多線程之間，這時，也同樣無須內(nèi)核的支持。由于切換的規(guī)則遠比進程調(diào)度和切換的規(guī)則簡單，因而使線程的切換速度特別快?？梢?，這種線程是與內(nèi)核無關的。ImplementingThreadsinUserSpaceAuser-levelthreadspackageHybridImplementationsMultiplexinguser-levelthreadsontokernel-levelthreadsTheMultithreadingRevolution第三章處理機調(diào)度與死鎖3.1處理機調(diào)度的基本概念BurstsofCPUusagealternatewithperiodsofI/OwaitaCPU-boundprocessanI/O-boundprocessSchedulingAlgorithmGoals3.1.1高級、中級和低級調(diào)度ThreelevelschedulingFCFSSJFHRFSRFFCFSSPFRRPS1.高級調(diào)度(HighScheduling)宏觀調(diào)度在每次執(zhí)行作業(yè)調(diào)度時，都須做出以下兩個決定。1)接納多少個作業(yè)?2)接納哪些作業(yè)?2.低級調(diào)度(LowLevelScheduling)微觀調(diào)度1)非搶占方式(Non-preemptiveMode)優(yōu)點：實現(xiàn)簡單、系統(tǒng)開銷小。調(diào)度時機：①正在執(zhí)行的進程執(zhí)行完畢退出②發(fā)生某事件而被阻塞（外部原因）③執(zhí)行中的進程提出阻塞請求（自我原因）2)搶占方式(PreemptiveMode)優(yōu)點：處理及時，實現(xiàn)復雜搶占的時機：①具有搶先權的進程創(chuàng)建就緒②具有搶先權的進程被喚醒進入就緒③具有搶先權的進程從掛起進入就緒3.中級調(diào)度(Intermediate-LevelScheduling)中程調(diào)度引入中級調(diào)度的主要目的，是為了提高內(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)度算法的若干準則1.面向用戶的準則(1)周轉(zhuǎn)時間短（批處理）平均周轉(zhuǎn)時間帶權周轉(zhuǎn)時間WT/TS而平均帶權周轉(zhuǎn)時間(2)響應時間快（交互式系統(tǒng)）(3)截止時間的保證（實時系統(tǒng)）(4)優(yōu)先權準則（特權處理）2.面向系統(tǒng)的準則(1)系統(tǒng)吞吐量高（批處理）(2)處理機利用率好（所有的）(3)各類資源的平衡利用（所有的）符合習慣思維（交互式）具有前瞻預測（實時系統(tǒng)）3.2調(diào)度算法3.2.1先來先服務和短作業(yè)(進程)優(yōu)先調(diào)度算法1.先來先服務調(diào)度算法2.短作業(yè)(進程)優(yōu)先調(diào)度算法FCFS的特點比較有利于長作業(yè)，而不利于短作業(yè)。有利于CPU繁忙的作業(yè)，而不利于I/O繁忙的作業(yè)。SJF的特點優(yōu)點：比FCFS改善平均周轉(zhuǎn)時間和平均帶權周轉(zhuǎn)時間，縮短作業(yè)的等待時間；提高系統(tǒng)的吞吐量；缺點：對長作業(yè)非常不利，可能長時間得不到執(zhí)行；未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)先級；難以準確估計作業(yè)（進程）的執(zhí)行時間，從而影響調(diào)度性能。SJF的變型.“最短剩余時間優(yōu)先”SRT(ShortestRemainingTime)允許比當前進程剩余時間更短的進程來搶占.“最高響應比優(yōu)先”HRRN(HighestResponseRatioNext)響應比R=(等待時間+要求執(zhí)行時間)/要求執(zhí)行時間是FCFS和SJF的折衷3.2.2高優(yōu)先權優(yōu)先調(diào)度算法1.優(yōu)先權調(diào)度算法的類型1)非搶占式優(yōu)先權算法2)搶占式優(yōu)先權調(diào)度算法2.優(yōu)先權的類型1)靜態(tài)優(yōu)先級創(chuàng)建進程時就確定，直到進程終止前都不改變。通常是一個整數(shù)。依據(jù)：進程類型（系統(tǒng)進程優(yōu)先級較高）對資源的需求（對CPU和內(nèi)存需求較少的進程，優(yōu)先級較高）用戶要求（緊迫程度和付費多少）2)動態(tài)優(yōu)先權在創(chuàng)建進程時賦予的優(yōu)先級，在進程運行過程中可以自動改變，以便獲得更好的調(diào)度性能.在就緒隊列中，等待時間延長則優(yōu)先級提高，從而使優(yōu)先級較低的進程在等待足夠的時間后，其優(yōu)先級提高到可被調(diào)度執(zhí)行進程每執(zhí)行一個時間片，就降低其優(yōu)先級，從而一個進程持續(xù)執(zhí)行時，其優(yōu)先級降低到出讓CPU3.高響應比優(yōu)先調(diào)度算法3.2.3基于時間片的輪轉(zhuǎn)調(diào)度算法1.時間片輪轉(zhuǎn)法RoundRobinSchedulinglistofrunnableprocesseslistofrunnableprocessesafterBusesupitsquantum2.多級反饋隊列調(diào)度算法(RoundRobinwithMultipleFeedback)多級反饋隊列算法是時間片輪轉(zhuǎn)算法和優(yōu)先級算法的綜合和發(fā)展。優(yōu)點：為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時間而照顧短進程為獲得較好的I/O設備利用率和縮短響應時間而照顧I/O型進程不必估計進程的執(zhí)行時間，動態(tài)調(diào)節(jié)AschedulingalgorithmwithfourpriorityclassesPS3.多級反饋隊列調(diào)度算法的性能(1)終端型作業(yè)用戶。(2)短批處理作業(yè)用戶。(3)長批處理作業(yè)用戶。3.2a實時調(diào)度Schedulablereal-timesystem.GivenmperiodiceventseventioccurswithinperiodPiandrequiresCisecondsThentheloadcanonlybehandledifWewilldiscussinthemultimediaOS

3.3產(chǎn)生死鎖的原因和必要條件3.3.1產(chǎn)生死鎖的原因(1)互斥資源分配不當(2)進程間推進順序不當1.競爭資源引起進程死鎖1)可剝奪和非剝奪性資源2)競爭非剝奪性資源3)競爭臨時性資源ResourcesExamplesofcomputerresources–printerstapedrives–tablesProcessesneedaccesstoresourcesinreasonableorderSupposeaprocessholdsresourceAandrequestsresourceBatsametimeanotherprocessholdsBandrequestsAbothareblockedandremainsoResourcesResourcesResourcesTwoprocessresourcetrajectories2.進程推進順序不當引起死鎖IntroductiontoDeadlocksFormaldefinition:AsetofprocessesisdeadlockedifeachprocessinthesetiswaitingforaneventthatonlyanotherprocessinthesetcancauseUsuallytheeventisreleaseofacurrentlyheldresourceNoneoftheprocessescan…–runreleaseresourcesbeawakened3.3.2產(chǎn)生死鎖的四個必要條件(1)互斥條件(2)請求和保持條件(3)不剝奪條件(4)環(huán)路等待條件3.3.3處理死鎖的基本方法(1)忽略死鎖(2)檢測和解除死鎖(3)避免死鎖(4)預防死鎖3.4解決死鎖的方法3.4.1忽略死鎖1.鴕鳥算法死鎖發(fā)生的概率小解決死鎖的代價太大3.4.2死鎖的檢測與解除死鎖的檢測1.資源分配圖(ResourceAllocationGraph)DetectionwithOneResourceofEachTypeNotetheresourceownershipandrequestsAcyclecanbefoundwithinthegraph,denotingdeadlockT2.死鎖定理3.死鎖檢測中的數(shù)據(jù)結構DetectionwithMultipleResourceofEachTypeAnexampleforthedeadlockdetectionalgorithm死鎖的解除(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臺。假設在T0時刻，進程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機，尚有3臺空閑未分配，如下表所示：進程最大需求已分配可用P1P2P310495223利用銀行家算法避免死鎖一個銀行家把他的固定資金（capital）貸給若干顧客。只要不出現(xiàn)一個顧客借走所有資金后還不夠，銀行家的資金應是安全的。銀行家需一個算法保證借出去的資金在有限時間內(nèi)可收回。3.4.4預防死鎖1.摒棄互斥條件2.摒棄“請求和保持”條件3.摒棄“不剝奪”條件4.摒棄“環(huán)路等待”AttackingtheMutualExclusionConditionSomedevices(suchasprinter)canbespooledonlytheprinterdaemonusesprinterresourcethusdeadlockforprintereliminatedNotalldevicescanbespooledPCB,HD.Principle:avoidassigningresourcewhennotabsolutelynecessaryasfewprocessesaspossibleactuallyclaimtheresourceAttackingtheHoldandWaitConditionRequireprocessestorequestresourcesbeforestartingaprocessneverhastowaitforwhatitneeds.ProblemsmaynotknowrequiredresourcesatstartofrunalsotiesupresourcesotherprocessescouldbeusingVariation:processmustgiveupallresourcesthenrequestallimmediatelyneededAttackingtheNoPreemptionConditionThisisnotaviableoptionConsideraprocessgiventheprinterhalfwaythroughitsjobnowforciblytakeawayprinter–!!??AttackingtheCircularWaitConditionNormallyorderedresourcesAresourcegraph9Summaryofapproachestodeadlockprevention預防死鎖的各種分類對策本章重要習題分析第四章存儲器管理4.1定位和重定位4.2簡單連續(xù)分配方式4.3基本頁式存儲管理方式4.4基本段式存儲管理方式4.5段頁式存儲管理4.6虛擬存儲器4.7請求式分頁的基本原理4.8頁面置換算法RelocationandProtectionCannotbesurewhereprogramwillbeloadedinmemoryaddresslocationsofvariables,coderoutinescannotbeabsolutemustkeepaprogramoutofotherprocessespartitionsUsebaseandlimitvaluesaddresslocationsaddedtobasevaluetomaptophysicaladdressaddresslocationslargerthanlimitvalueisanerror4.1定位和重定位4.1.1程序的裝入1.絕對裝入方式(AbsoluteLoadingMode)程序中所使用的絕對地址，既可在編譯或匯編時給出，也可由程序員直接賦予。例如：ORG1000Hdfb309adfb309a00f39761b3c44600f39761b3c44600f39762.可重定位裝入方式(RelocationLoadingMode)P1P2P3P4P53.動態(tài)運行時裝入方式(dynamicRun-timeLoading)動態(tài)運行時的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進行。因此，裝入內(nèi)存后的所有地址都仍是相對地址。4.1.2程序的鏈接1.靜態(tài)鏈接方式(StaticLinking)在將這幾個目標模塊裝配成一個裝入模塊時，須解決以下兩個問題：(1)對相對地址進行修改。(2)變換外部調(diào)用符號。2.裝入時動態(tài)鏈接(LoadtimeDynamicLinking)裝入時動態(tài)鏈接方式有以下優(yōu)點：(1)便于修改和更新。(2)便于實現(xiàn)對目標模塊的共享。3.運行時動態(tài)鏈接(Run-timeDynamicLinking)在執(zhí)行過程中，當發(fā)現(xiàn)一個被調(diào)用模塊尚未裝入內(nèi)存時，立即由OS去找到該模塊并將之裝入內(nèi)存，把它鏈接到調(diào)用者模塊上。這樣不僅可加快程序的裝入過程，而且可節(jié)省大量的內(nèi)存空間。4.2簡單連續(xù)分配方式4.2.1單一連續(xù)分配這是最簡單的一種存儲管理方式，但只能用于單用戶、單任務的操作系統(tǒng)中。采用這種存儲管理方式時，可把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用，通常是放在內(nèi)存的低址部分；用戶區(qū)是指除系統(tǒng)區(qū)以外的全部內(nèi)存空間，提供給用戶使用。MonoprogrammingThreesimplewaysoforganizingmemoryanoperatingsystemwithoneuserprocess無分區(qū)4.2.2固定分區(qū)分配1.劃分分區(qū)的方法(1)分區(qū)大小相等，即使所有的內(nèi)存分區(qū)大小相等。(2)分區(qū)大小不等。2.內(nèi)存分配等額固定分區(qū)差額固定分區(qū)MultiprogrammingwithFixedPartitionsFixedmemorypartitionsseparateinputqueuesforeachpartitionsingleinputqueue動態(tài)分區(qū)4.2.3動態(tài)分區(qū)分配碎片Hole1.分區(qū)分配中的數(shù)據(jù)結構(1)空閑分區(qū)表。(2)空閑分區(qū)鏈。MemoryManagementwithBitMapsPartofmemorywith5processes,3holestickmarksshowallocationunitsshadedregionsarefreeCorrespondingbitmapSameinformationasalistMemoryManagementwithLinkedListsFourneighborcombinationsfortheterminatingprocessXFragment碎片2.分區(qū)分配算法(1)首次適應算法FF。(2)循環(huán)首次適應算法。(3)最佳適應算法。(4)最壞適應算法。(5)快速適應算法。PointerComingaNewprocessis16KWorstfit4.2.4可重定位分區(qū)分配1.動態(tài)重定位的引入2.動態(tài)重定位的實現(xiàn)3.動態(tài)重定位分區(qū)分配算法4.2.5對換(Swapping)1.對換的引入2.對換空間的管理3.進程的換出與換入(1)進程的換出。每當一進程由于創(chuàng)建子進程而需要更多的內(nèi)存空間，但又無足夠的內(nèi)存空間等情況發(fā)生時，系統(tǒng)應將某進程換出。(2)進程的換入。系統(tǒng)應定時地查看所有進程的狀態(tài)，從中找出就緒狀態(tài)但已換出的進程，將其中換出時間(換出到磁盤上)最久的進程作為換入進程，將之換入，直至已無可換入的進程或無可換出的進程為止。4.3基本分頁存儲管理方式4.3.1頁面與頁表1.頁面1)頁面和物理塊2)頁面大小在分頁系統(tǒng)中的頁面其大小應適中。頁面若太小，一方面雖然可使內(nèi)存碎片減小，從而減少了內(nèi)存碎片的總空間，有利于提高內(nèi)存利用率，但另一方面也會使每個進程占用較多的頁面，從而導致進程的頁表過長，占用大量內(nèi)存；此外，還會降低頁面換進換出的效率。然而，如果選擇的頁面較大，雖然可以減少頁表的長度，提高頁面換進換出的速度，但卻又會使頁內(nèi)碎片增大。因此，頁面的大小應選擇得適中，且頁面大小應是2的冪，通常為512B~8KB。PageSizeSmallpagesizeAdvantageslessinternalfragmentationbetterfitforvariousdatastructures,codesectionslessunusedprograminmemoryDisadvantagesprogramsneedmanypages,largerpagetables0Pagesizelarge,thefragmentationbigPagesizesmall,thepagetablebigFragmentation內(nèi)碎片Mostprogram’spiecesarelessthan4KA.0A.1A.2A.3B.0B.1B.2C.0C.1C.2C.3PageSizeOverheadduetopagetableandinternalfragmentation.Wheres=averageprocesssizeinbytesp=pagesizeinbytese=pageentryOptimizedwheninternalfragmentationpagetablespace2.地址結構分頁地址中的地址結構如下：頁號P位移量W3112110對某特定機器，其地址結構是一定的。若給定一個邏輯地址空間中的地址為A，頁面的大小為L，則頁號P和頁內(nèi)地址d可按下式求得：3.頁表4.3.2地址變換機構1.基本的地址變換機構2.具有快表的地址變換機構4.3.3兩級和多級頁表現(xiàn)代的大多數(shù)計算機系統(tǒng)，都支持非常大的邏輯地址空間(232~264)。在這樣的環(huán)境下，頁表就變得非常大，要占用相當大的內(nèi)存空間?？梢圆捎眠@樣兩個方法來解決這一問題：①采用離散分配方式來解決難以找到一塊連續(xù)的大內(nèi)存空間的問題：②只將當前需要的部分頁表項調(diào)入內(nèi)存，其余的頁表項仍駐留在磁盤上，需要時再調(diào)入。1.兩級頁表(Two-LevelPageTable)邏輯地址結構可描述如下：Windows的多級頁表結構2.多級頁表對于32位的機器，采用兩級頁表結構是合適的；但對于64位的機器，如果頁面大小仍采用4KB即212B，那么還剩下52位，假定仍按物理塊的大小(212位)來劃分頁表，則將余下的42位用于外層頁號。此時在外層頁表中可能有4096G個頁表項，要占用16384GB的連續(xù)內(nèi)存空間。必須采用多級頁表，將外層頁表再進行分頁，也是將各分頁離散地裝入到不相鄰接的物理塊中，再利用第2級的外層頁表來映射它們之間的關系。InvertedPageTablesComparisonofatraditionalpagetablewithaninvertedpagetable4.4基本分段存儲管理方式4.4.1分段存儲管理方式的引入引入分段存儲管理方式，主要是為了滿足用戶和程序員的下述一系列需要：1)方便編程2)信息共享3)信息保護4)動態(tài)增長5)動態(tài)鏈接4.4.2分段系統(tǒng)的基本原理1.分段分段地址中的地址具有如下結構：段號段內(nèi)地址31161502.段表4.分頁和分段的主要區(qū)別(1)頁是信息的物理單位，分頁是為實現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存的利用率。或者說，分頁僅僅是由于系統(tǒng)管理的需要而不是用戶的需要。段則是信息的邏輯單位，它含有一組其意義相對完整的信息。分段的目的是為了能更好地滿足用戶的需要。(2)頁的大小固定且由系統(tǒng)決定，由系統(tǒng)把邏輯地址劃分為頁號和頁內(nèi)地址兩部分，是由機器硬件實現(xiàn)的，因而在系統(tǒng)中只能有一種大小的頁面；而段的長度卻不固定，決定于用戶所編寫的程序，通常由編譯程序在對源程序進行編譯時，根據(jù)信息的性質(zhì)來劃分。(3)分頁的作業(yè)地址空間是一維的，即單一的線性地址空間，程序員只需利用一個記憶符，即可表示一個地址；而分段的作業(yè)地址空間則是二維的，程序員在標識一個地址時，既需給出段名，又需給出段內(nèi)地址。4.5段頁式存儲管理方式4.5.1基本原理4.5.2地址變換過程4.6虛擬存儲器的基本概念4.6.1虛擬存儲器的引入1.常規(guī)存儲器管理方式的特征(1)一次性。(2)駐留性。2.局部性原理1968年，Denning.P指出：(1)程序執(zhí)行時，大多數(shù)情況下仍是順序執(zhí)行的。(2)過程調(diào)用將會使程序轉(zhuǎn)移，過程調(diào)用的深度在大多數(shù)情況下都不超過5。(3)程序中存在許多循環(huán)結構，它們將多次執(zhí)行。(4)程序中還包括許多對數(shù)據(jù)結構的處理，如對數(shù)組進行操作，它們往往都局限于很小的范圍內(nèi)。局限性又表現(xiàn)在下述兩個方面：(1)時間局限性。如果程序中的某條指令一旦執(zhí)行，則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪問過，則不久以后該數(shù)據(jù)可能再次被訪問。產(chǎn)生時間局限性的典型原因，是由于在程序中存在著大量的循環(huán)操作。(2)空間局限性。一旦程序訪問了某個存儲單元，在不久之后，其附近的存儲單元也將被訪問，即程序在一段時間內(nèi)所訪問的地址，可能集中在一定的范圍之內(nèi)，其典型情況便是程序的順序執(zhí)行。3.虛擬存儲器定義所謂虛擬存儲器，是指具有請求調(diào)入功能和置換功能，能從邏輯上對內(nèi)存容量加以擴充的一種存儲器系統(tǒng)。其邏輯容量由內(nèi)存容量和外存容量之和所決定，其運行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存?？梢?，虛擬存儲技術是一種性能非常優(yōu)越的存儲器管理技術，故被廣泛地應用于大、中、小型機器和微型機中。CPU及其存儲器的地址線寬度4.6.2虛擬存儲器的實現(xiàn)方法1.分頁請求系統(tǒng)(1)硬件支持。①請求分頁的頁表機制，它是在純分頁的頁表機制上增加若干項而形成的，作為請求分頁的數(shù)據(jù)結構；②缺頁中斷機構，即每當用戶程序要訪問的頁面尚未調(diào)入內(nèi)存時便產(chǎn)生一缺頁中斷，以請求OS將所缺的頁調(diào)入內(nèi)存③地址變換機構，它同樣是在純分頁地址變換機構的基礎上發(fā)展形成的。(2)實現(xiàn)請求分頁的軟件。PageTablesTypicalpagetableentryVirtualtimeandsoonOnlyformemorymappedI/OTheworsepagefaultshappensBeyondfault4.6.3虛擬存儲器的特征1.多次性對換性3.虛擬性4.7請求分頁存儲管理方式4.7.1請求分頁中的硬件支持1.頁表機制2.缺頁中斷機構3.地址變換機構4.7.2內(nèi)存分配策略和分配算法1.最小物理塊數(shù)的確定2.物理塊的分配策略在請求分頁系統(tǒng)中，可采取兩種內(nèi)存分配策略，即固定和可變分配策略。在進行置換時，也可采取兩種策略，即全局置換和局部置換。于是可組合出以下三種適用的策略。1)固定分配局部置換(FixedAllocation,LocalReplacement)2)可變分配全局置換(VariableAllocation,GlobalReplacement)3)可變分配局部置換(VariableAllocation,LocalReplacemen2)按比例分配算法根據(jù)進程的大小按比例分配物理塊的算法。如果系統(tǒng)中共有n個進程，每個進程的頁面數(shù)為Si，則系統(tǒng)中各進程頁面數(shù)的總和為：又假定系統(tǒng)中可用的物理塊總數(shù)為m，則每個進程所能分到的物理塊數(shù)為bi，將有：b應該取整，它必須大于最小物理塊數(shù)。3.物理塊分配算法1)平均分配算法3)考慮優(yōu)先權的分配算法在實際應用中，為了照顧到重要的、緊迫的作業(yè)能盡快地完成，應為它分配較多的內(nèi)存空間。通常采取的方法是把內(nèi)存中可供分配的所有物理塊分成兩部分：一部分按比例地分配給各進程；另一部分則根據(jù)各進程的優(yōu)先權，適當?shù)卦黾悠湎鄳蓊~后，分配給各進程在有的系統(tǒng)中，如重要的實時控制系統(tǒng)，則可能是完全按優(yōu)先權來為各進程分配其物理塊的。4.7.3調(diào)頁策略1.何時調(diào)入頁面1)預調(diào)頁策略2)請求調(diào)頁策略2.從何處調(diào)入頁面在請求分頁系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對換頁面的對換區(qū)。通常，由于對換區(qū)是采用連續(xù)分配方式，而事件是采用離散分配方式，故對換區(qū)的磁盤I/O速度比文件區(qū)的高。這樣，每當發(fā)生缺頁請求時，系統(tǒng)應從何處將缺頁調(diào)入內(nèi)存，可分成如下三種情況：(1)系統(tǒng)擁有足夠的對換區(qū)空間，這時可以全部從對換區(qū)調(diào)入所需頁面，以提高調(diào)頁速度。為此，在進程運行前，便須將與該進程有關的文件，從文件區(qū)拷貝到對換區(qū)。(2)系統(tǒng)缺少足夠的對換區(qū)空間，這時凡是不會被修改的文件，都直接從文件區(qū)調(diào)入；而當換出這些頁面時，由于它們未被修改而不必再將它們換出，以后再調(diào)入時，仍從文件區(qū)直接調(diào)入。但對于那些可能被修改的部分，在將它們換出時，便須調(diào)到對換區(qū)，以后需要時，再從對換區(qū)調(diào)入。(3)UNIX方式。由于與進程有關的文件都放在文件區(qū)，故凡是未運行過的頁面，都應從文件區(qū)調(diào)入。而對于曾經(jīng)運行過但又被換出的頁面，由于是被放在對換區(qū)，因此在下次調(diào)入時，應從對換區(qū)調(diào)入。由于UNIX系統(tǒng)允許頁面共享，因此，某進程所請求的頁面有可能已被其它進程調(diào)入內(nèi)存，此時也就無須再從對換區(qū)調(diào)入。Solaris存儲3.頁面調(diào)入過程每當程序所要訪問的頁面未在內(nèi)存時，便向CPU發(fā)出一缺頁中斷，中斷處理程序首先保留CPU環(huán)境，分析中斷原因后，轉(zhuǎn)入缺頁中斷處理程序。該程序通過查找頁表，得到該頁在外存的物理塊后，如果此時內(nèi)存能容納新頁，則啟動磁盤I/O將所缺之頁調(diào)入內(nèi)存，然后修改頁表。如果內(nèi)存已滿，則須先按照某種置換算法從內(nèi)存中選出一頁準備換出；如果該頁未被修改過，可不必將該頁寫回磁盤；但如果此頁已被修改，則必須將它寫回磁盤，然后再把所缺的頁調(diào)入內(nèi)存，并修改頁表中的相應表項，置其存在位為“1，并將此頁表項寫入快表中。在缺頁調(diào)入內(nèi)存后，利用修改后的頁表，去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。4.8頁面置換算法PagefaultforceschoicewhichpagemustberemovedmakeroomforincomingpageModifiedpagemustfirstbesavedunmodifiedjustoverwrittenBetternottochooseanoftenusedpagewillprobablyneedtobebroughtbackinsoon4.8.1最佳置換算法和先進先出置換算法1.最佳(Optimal)置換算法最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁面，將是以后永不使用的，或許是在最長(未來)時間內(nèi)不再被訪問的頁面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁率。OPT432143543215頁1432111555211頁243333333555頁34444444444xxxx√√x√√xx√共缺頁中斷7次2.先進先出(FIFO)頁面置換算法SecondChancePageReplacementAlgorithmOperationofasecondchancepagessortedinFIFOorderPagelistiffaultoccursattime20,AhasRbitset(numbersabovepagesareloadingtimes)TheClockPageReplacementAlgorithm2.改進型Clock置換算法由訪問位A和修改位M可以組合成下面四種類型的頁面：1類(A=0,M=0):表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁。2類(A=0,M=1)：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。3類(A=1,M=0)：最近已被訪問，但未被修改，該頁有可能再被訪問。4類(A=1,M=1):最近已被訪問且被修改，該頁可能再被訪問。1.簡單的Clock置換算法4.8.2Clock置換算法NotRecentlyUsedPageReplacementAlgorithmEachpagehasReferencebit,Modifiedbitbitsaresetwhenpageisreferenced,modifiedPagesareclassified1.notreferenced,notmodified2.notreferenced,modified3.referenced,notmodified4.referenced,modifiedNRUremovespageatrandomfromlowestnumberednonemptyclass4.8.3最近最久未使用(LRU)置換算法1.LRU(LeastRecentlyUsed)置換算法的描述2.LRU置換算法的硬件支持4.8.4其它置換算法1.最少使用(LFU：LeastFrequentlyUsed)置換算法2.頁面緩沖算法(PBA：PageBufferingAlgorithm)TheWorkingSetPageReplacementAlgorithmTheworkingsetisthesetofpagesusedbythekmostrecentmemoryreferencesw(k,t)isthesizeoftheworkingsetattime,tLocalityofreferenceTheWorkingSetPageReplacementAlgorithmTheworkingsetalgorithm0TheWSClockPageReplacementAlgorithmOperationoftheWSClockalgorithmReviewofPageReplacementAlgorithms4.8.5其它Belady’sAnomalyStackAlgorithmTheDistanceStringPredictingPageFaultRatesBelady'sAnomalyFIFOwith3pageframesFIFOwith4pageframesP'sshowwhichpagereferencesshowpagefaultsDESIGNISSUESFORPAGINGSYSTEMSLocalversusGlobalAllocationPoliciesLoadControlPageSizeSeparateInstructionandDataSpacesSharedPagesCleaningPolicyVirtualMemoryInterfaceLocalversusGlobalAllocationPoliciesOriginalconfigurationLocalpagereplacementGlobalpagereplacement7framesLocalversusGlobalAllocationPoliciesPagefaultrateasafunctionofthenumberofpageframesassignedLoadControlDespitegooddesigns,systemmaystillthrashWhenPFFalgorithmindicatessomeprocessesneedmorememorybutnoprocessesneedlessSolution:Reducenumberofprocessescompetingformemoryswaponeormoretodisk,divideuppagestheyheldreconsiderdegreeofmultiprogrammingSeparateInstructionandDataSpacesOneaddressspaceSeparateIandDspacesSharedPagesTwoprocessessharingsameprogramsharingitspagetableCleaningPolicyNeedforabackgroundprocess,pagingdaemonperiodicallyinspectsstateofmemoryWhentoofewframesarefreeselectspagestoevictusingareplacementalgorithmItcanusesamecircularlist(clock)asregularpagereplacementalgorithmbutwithdifferencepointerSegmentationwithPaging:PentiumPentiumcodesegmentdescriptorDatasegmentsdifferslightlySegmentationwithPaging:PentiumConversionofa(selector,offset)pairtoalinearaddressSegmentationwithPaging:PentiumMappingofalinearaddressontoaphysicaladdress15SegmentationwithPaging:PentiumProtectiononthePentium本章重要習題分析第五章設備管理5.1I/O系統(tǒng)5.2I/O控制方式5.3緩沖管理5.4設備分配5.5設備處理5.6磁盤存儲空間管理5.7IO管理的其它問題5.1I/O系統(tǒng)5.1.1I/O設備1.I/O設備的類型1)按傳輸速率分類2)按信息交換的單位分類3)按設備的共享屬性分類2.設備與控制器之間的接口PrinciplesofI/OHardwareSometypicaldevice,network,anddatabaseratesDeviceControllersI/Odeviceshavecomponents:mechanicalcomponentelectroniccomponentTheelectroniccomponentisthedevicecontrollermaybeabletohandlemultipledevicesController'stasksconvertserialbitstreamtoblockofbytesperformerrorcorrectionasnecessarymakeavailabletomainmemory5.1.2設備控制器1.設備控制器的基本功能1)接收和識別命令2)數(shù)據(jù)交換3)標識和報告設備的狀態(tài)4)地址識別5)數(shù)據(jù)緩沖6)差錯控制2.設備控制器的組成Memory-MappedI/O(1)SeparateI/OandmemoryspaceMemorymappedI/O.HybridCache?Memory-MappedI/O(2)(a)Asingle-busarchitecture(b)Adual-busmemoryarchitectureISABusMemory-MappedI/O(3)StructureofalargePentiumsystemNSDirectMemoryAccess(DMA)OperationofaDMAtransferInterruptsRevisitedHowinterruptshappens.Connectionsbetweendevicesandinterruptcontrolleractuallyuseinterruptlinesonthebusratherthandedicatedwires5.1.3I/O通道1.I/O通道(I/OChannel)設備的引入2.通道類型1)字節(jié)多路通道(ByteMultiplexorChannel)2)數(shù)組選擇通道(BlockSelectorChannel)3)數(shù)組多路通道(BlockMultiplexorChannel)3.“瓶頸問題ChannelmodeI/O5.1.4總線系統(tǒng)1.ISA和EISA總線1)ISA(IndustryStandardArchitecture)總線2)EISA(ExtendedISA)總線2.局部總線(LocalBus)1)VESA(VideoElectronicStandardAssociation)總線2)PCI(PeripheralComponentInterface)總線5.2I/O控制方式GoalsofI/OSoftwareDeviceindependenceprogramscanaccessanyI/Odevicewithoutspecifyingdeviceinadvance(floppy,harddrive,orCD-ROM)UniformnamingnameofafileordeviceastringoranintegernotdependingonwhichmachineErrorhandlinghandleasclosetothehardwareaspossible5.2I/O控制方式(續(xù))GoalsofI/OSoftwareSynchronousvs.asynchronoustransfersblockedtransfersvs.interruptdrivenBufferingdatacomingoffadevicecannotbestoredinfinaldestinationSharablevs.dedicateddevicesdisksaresharabletapedriveswouldnotbe5.2.1程序I/O方式5.2.2中斷驅(qū)動I/O控制方式WritingastringtotheprinterusinginterruptdrivenI/OCodeexecutedwhenprintsystemcallismadeInterruptserviceprocedure5.2.3直接存儲器訪問DMAI/O控制方式1.DMA(DirectMemoryAccess)控制方式的引入2.DMA控制器的組成5.2.4I/O通道控制方式1.I/O通道控制方式的引入5.3緩沖管理5.3.1緩沖的引入(1)緩和CPU與I/O設備間速度不匹配的矛盾。(2)減少對CPU的中斷頻率，放寬對CPU中斷響應時間的限制。(3)提高CPU和I/O設備之間的并行性。5.3.2單緩沖和雙緩沖1.單緩沖(SingleBuffer)2.雙緩沖(DoubleBuffer)5.3.3循環(huán)緩沖1.循環(huán)緩沖的組成5.3.4緩沖池(BufferPool)1.緩沖池的組成對于既可用于輸入又可用于輸出的公用緩沖池，其中至少應含有以下三種類型的緩沖區(qū)：①空(閑)緩沖區(qū)；②裝滿輸入數(shù)據(jù)的緩沖區(qū)；③裝滿輸出數(shù)據(jù)的緩沖區(qū)。為了管理上的方便，可將相同類型的緩沖區(qū)鏈成一個隊列，于是可形成以下三個隊列：（1）空緩沖隊列emq。(2)輸入隊列inq。(3)輸出隊列outq。2.緩沖區(qū)的工作方式5.4設備分配5.4.1設備分配中的數(shù)據(jù)結構1.設備控制表DCT2.控制器控制表、通道控制表和系統(tǒng)設備表User-SpaceI/OSoftwareSystemDeviceTableDeviceControlTableCOntrollerControlTableCHannelControlTableHardware5.4.2設備分配時應考慮的因素1.設備的固有屬性(1)獨享設備。(2)共享設備。(3)虛擬設備。2.設備分配算法(1)先來先服務。(2)優(yōu)先級高者優(yōu)先。3.設備分配中的安全性1)安全分配方式2)不安全分配方式5.4.3設備獨立性1.設備獨立性(DeviceIndependence)的概念為了提高OS的可適應性和可擴展性，在現(xiàn)代OS中都毫無例外地實現(xiàn)了設備獨立性，也稱為設備無關性。其基本含義是：應用程序獨立于具體使用的物理設備。為了實現(xiàn)設備獨立性而引入了邏輯設備和物理設備這兩個概念。在應用程序中，使用邏輯設備名稱來請求使用某類設備；而系統(tǒng)在實際執(zhí)行時，還必須使用物理設備名稱。因此，系統(tǒng)須具有將邏輯設備名稱轉(zhuǎn)換為某物理設備名稱的功能，這非常類似于存儲器管理中所介紹的邏輯地址和物理地址的概念。在實現(xiàn)了設備獨立性的功能后，可帶來以下兩方面的好處。1)設備分配時的靈活性2)易于實現(xiàn)I/O重定向Device-IndependentI/OSoftwareFunctionsofthedevice-independentI/OsoftwareUniforminterfacingfordevicedriversBufferingErrorreportingAllocatingandreleasingdedicatedevicesProvidingadeice-independentblocksize2.設備獨立性軟件1)執(zhí)行所有設備的公有操作2)向用戶層(或文件層)軟件提供統(tǒng)一接口I/OSoftwareLayersLayersoftheI/OSoftwareSystemUser-SpaceI/OSoftwareLayersoftheI/OsystemandthemainfunctionsofeachlayerDeviceDriversLogicalpositionofdevicedriversisshownhereCommunicationsbetweendriversanddevicecontrollersgoesoverthebus5.4.4獨占設備的分配程序1.基本的設備分配程序1)分配設備2)分配控制器3)分配通道2.設備分配程序的改進1)增加設備的獨立性2)考慮多通路情況5.4.5SPOOLing技術1.什么是SPOOLing為了緩和CPU的高速性與I/O設備低速性間的矛盾而引入了脫機輸入、脫機輸出技術。該技術是利用專門的外圍控制機，將低速I/O設備上的數(shù)據(jù)傳送到高速磁盤上；或者相反。事實上，當系統(tǒng)中引入了多道程序技術后，完全可以利用其中的一道程序，來模擬脫機輸入時的外圍控制機功能，把低速I/O設備上的數(shù)據(jù)傳送到高速磁盤上；再用另一道程序來模擬脫機輸出時外圍控制機的功能，把數(shù)據(jù)從磁盤傳送到低速輸出設備上。這樣，便可在主機的直接控制下，實現(xiàn)脫機輸入、輸出功能。此時的外圍操作與CPU對數(shù)據(jù)的處理同時進行，我們把這種在聯(lián)機情況下實現(xiàn)的同時外圍操作稱為SPOOLing(Simultan