計算機操作系統(tǒng)第四版期末復習知識點匯總附習題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)專心-專注-專業(yè)精選優(yōu)質(zhì)文檔-傾情為你奉上專心-專注-專業(yè)第一章 引論為什么發(fā)明計算機系統(tǒng)：方便、有效、可擴充、開放計算機系統(tǒng)作用：做接口、管理資源、資源的抽象發(fā)展計算機系統(tǒng)的動力：提高利用率、更加方便、應用.體系.硬件更新都要跟上計算機系統(tǒng)發(fā)展史一、無操作系統(tǒng)（一）人工操作：單用戶、CPU. 內(nèi)存長期空閑（二）脫機輸入/輸出（OFF-LINE I/0）：裝好卡片再上機。節(jié)約CPU空閑時間、提高I/O速度二、單道批操作系統(tǒng)描述：有個監(jiān)督程序?qū)⒋艓系淖鳂I(yè)調(diào)入計算機缺點：I/O太慢，CPU太快三、多道批操作系統(tǒng)描述：A在I/0，

2、B趁機CPU優(yōu)點：肯定提高資源利用率、系統(tǒng)吞吐量變大缺點：每個程序都要很久才處理完（作業(yè)要排隊）、無交互能力未解難題：內(nèi)存、處理機爭用、I/O設(shè)備、文件的組織和管理、作業(yè)管理、用戶和系統(tǒng)的接口四、分時系統(tǒng)描述：解決人機交互問題優(yōu)點：終于有人機交互、多用戶共享主機實際問題：由于多用戶，所以要有“多路卡”、作業(yè)直接入內(nèi)存、有個“時間片”調(diào)度作業(yè)特征：多路、獨立、及時（用戶可接受）、交互五、實時系統(tǒng)描述：工業(yè)（武器）控制系統(tǒng)、信息查詢系統(tǒng)、多媒體系統(tǒng)、嵌入式系統(tǒng)類型1：周期性實時：真的很周期；非周期性實時：有開始截止時間和完成截止時間類型2：硬實時：工業(yè)、武器系統(tǒng)；軟實時：信息查詢系統(tǒng)和多媒體系統(tǒng)與

3、分時系統(tǒng)比較： 多路、獨立、及時（毫秒級）、交互、可靠六、微機時代（一）單用戶單任務：8位機的CP/M、16位機的MS-DOS（二）單用戶多任務：目前的32位系統(tǒng)，如Windows（三）多用戶多任務：UNIX、Solaris、Linux操作系統(tǒng)共同特性：一、并發(fā)（一）并發(fā)和并行宏觀上一樣，并發(fā)：單處理機系統(tǒng)，微觀上交替運行并行：多處理機系統(tǒng)，微觀上同時運行（二）引入進程進程：在系統(tǒng)中能獨立運行并作為資源分配的基本單位，由機器指令、數(shù)據(jù)和堆棧等組成，能獨立運行的活動實體特點：用進程就可以并發(fā)執(zhí)行了二、共享（一）互斥共享方式例子：臨界資源，打印機、磁帶機描述：你要先申請才能獲得資源（二）同時訪問方

4、式描述：微觀上還是并發(fā)例子：多用戶磁盤設(shè)備條件：系統(tǒng)允許進程并發(fā)、系統(tǒng)能有效管理資源三、虛擬（一）時分復用技術(shù)（利用空閑時間服務其他用戶）虛擬處理機技術(shù)：分身之術(shù)虛擬設(shè)備：又是分身之術(shù)，騙用戶以為有專人服務時分復用：速度：1/N（二）空分復用技術(shù)描述：將程序、電話線分成若干部分，然后各部分分時進入內(nèi)存運行空分復用：空間：1/N四、異步描述：因為要并發(fā)，所以需要一個機制調(diào)度進程操作系統(tǒng)主要功能一、處理機管理功能（一）進程控制描述：要并發(fā)，就要進程、要進程，就要管理（二）進程同步進程互斥方式：臨界資源要互斥進程同步方式：合作完成共同任務，同步機構(gòu)要協(xié)調(diào)先后次序（信號量控制）（三）進程通信描述：對合

5、作進程而言，需要交換信息。當他們處于同一計算機系統(tǒng)時，通常采用直接通信的方式。例子：輸入進程、計算進程、打印進程，需要信息交換（四）調(diào)度作業(yè)調(diào)度：選擇作業(yè)、建立進程、分配資源、插入就緒隊列進程調(diào)度：從就緒隊列中選出進程，分配CPU二、存儲器管理功能（一）內(nèi)存分配任務：分配空間、減少碎片、追加內(nèi)存空間方式：靜態(tài)分配，裝入內(nèi)存時確定，不允許追加、不允許移動；動態(tài)分配，允許追加、允許移動（二）內(nèi)存保護任務1：每道程序只在自己的內(nèi)存空間運行，互不干擾任務2：不允許用戶程序訪問操作系統(tǒng)程序和數(shù)據(jù)、也不允許用戶程序轉(zhuǎn)移到非共享的其他用戶程序中執(zhí)行（三）地址映射任務：存儲器要負責地址映射，在硬件支持下完成（

6、四）內(nèi)存擴充描述：用虛擬存儲技術(shù)，從邏輯上擴充內(nèi)存容量任務1：請求-調(diào)入功能任務2：置換功能三、設(shè)備管理功能任務1：完成用戶進程的I/O請求：分配I/O設(shè)備，完成I/O操作任務2：提高CPU和I/O利用率：提高I/O速度，方便用戶使用I/O設(shè)備（一）緩沖管理描述：在內(nèi)存中設(shè)置緩沖區(qū)（CPU高速性和I/O低速性）例子：單緩沖機制、雙向同時傳送數(shù)據(jù)的雙緩沖機制、多個設(shè)備共同使用的公用“緩沖池”機制（二）設(shè)備分配描述：在系統(tǒng)中設(shè)置“設(shè)備控制表”、“控制器控制表”等數(shù)據(jù)結(jié)構(gòu)，用于記錄設(shè)備和控制器等標識符和狀態(tài)。根據(jù)表就知道指定設(shè)備當前是否可用、忙碌。分配時，針對不同設(shè)備要有不同“分配方式”，對獨占設(shè)備

7、還要考慮分配后是否安全（三）設(shè)備處理描述：CPU向設(shè)備控制器發(fā)出I/O命令，要求完成I/O操作、反之，CPU接收控制器發(fā)出的中斷請求，并響應.處理四、文件管理功能描述：管理用戶、系統(tǒng)文件，方便使用；保證安全性（一）文件儲存空間管理背景：多用戶環(huán)境下，用戶自己管理文件存儲，會困難和低效任務1：為每個文件分配外存空間、提高外存利用率、進而提高存取速度任務2：系統(tǒng)中設(shè)置數(shù)據(jù)結(jié)構(gòu)，記錄文件存儲空間使用情況，以供分配時參考任務3：分配和回收（二）目錄管理任務1：為每個文件建立目錄項，包括文件名、屬性、物理位置等，以實現(xiàn)按名存取任務2：實現(xiàn)文件共享。任務3：提供目錄查詢手段（三）文件讀/寫管理和保護文件讀

8、/寫管理：根據(jù)用戶請求，從外存中讀取數(shù)據(jù)，或?qū)?shù)據(jù)寫入外存文件保護：防止未經(jīng)核準的用戶存取文件、防止冒名頂替存取文件、防止以不正確方式使用文件五、操作系統(tǒng)與用戶之間的接口（一）用戶接口描述：方便用戶直接.間接控制自己的作業(yè)聯(lián)機用戶接口：等待用戶鍵入命令脫機用戶接口：一開始就提供作業(yè)說明書，直到作業(yè)結(jié)束語句圖形用戶接口：移動鼠標選擇菜單項（二）程序接口描述：舊系統(tǒng)用匯編語言寫，所以只有匯編語言的才能直接使用系統(tǒng)調(diào)用；如果是高級語言，就用一一對應的庫函數(shù)六、現(xiàn)代操作系統(tǒng)的新功能（一）系統(tǒng)安全描述：確保存儲和傳送數(shù)據(jù)的保密性、完整性和系統(tǒng)可用性，要用幾種技術(shù)技術(shù)：認證技術(shù)、密碼技術(shù)、訪問控制技術(shù)、反

9、病毒技術(shù)（二）網(wǎng)絡(luò)的功能和服務功能：網(wǎng)絡(luò)通信、資源管理、應用互操作（三）支持多媒體功能：接納控制功能、實時調(diào)度、多媒體文件的存儲OS結(jié)構(gòu)設(shè)計一、傳統(tǒng)操作系統(tǒng)結(jié)構(gòu)（一）無結(jié)構(gòu)操作系統(tǒng)又名：整體系統(tǒng)結(jié)構(gòu)（二）模塊化結(jié)構(gòu)OS基本概念：又名：模塊-接口法描述：有模塊、子模塊、接口模塊獨立性：標準：內(nèi)聚性越高，模塊獨立性越高、耦合度越低，模塊獨立性越高優(yōu)點：提高設(shè)計正確性.可理解性和可維護性、增強可適應性、加快加速過程缺點：接口難以滿足需求、無序（三）分層式結(jié)構(gòu)OS基本概念：有序分層，自底向上法鋪設(shè)中間層優(yōu)點：易保證系統(tǒng)正確性、易擴充和易維護缺點：系統(tǒng)效率降低二、客戶/服務器模式(Client/Serv

10、er Model)簡介（一）客戶/服務器模式的由來、組成和類型組成：客戶機、服務器、網(wǎng)絡(luò)系統(tǒng)（二）客戶/服務器之間的交互描述：客戶發(fā)送請求消息、服務器接收消息、服務器回送消息、客戶機接收消息（三）客戶/服務器模式的優(yōu)點描述：數(shù)據(jù)分布處理和存儲、便于集中管理、靈活性和可擴充性、易于改編應用軟件三、面向?qū)ο蟮某绦蛟O(shè)計（一）OOP的基本概念描述：抽象，具體事物為對象對象：封裝好對象類：創(chuàng)建多個相似對象繼承：繼承父類，增加部分（二）OOP的優(yōu)點描述：“重用”提高產(chǎn)品質(zhì)量和生產(chǎn)率、使系統(tǒng)具有更好的易修改性和易擴展性、易于保證系統(tǒng)“正確性”和“可靠性”四、微內(nèi)核OS結(jié)構(gòu)描述：支持多處理機例子：卡內(nèi)基梅隆的

11、Mach OS、Windows 2000/XP（一）基本概念描述：足夠小的內(nèi)核、基于C/S模式、應用“機制與策略分離”原理、采用OOP技術(shù)（二）基本功能描述：進程管理、低級存儲器管理、中斷和陷入處理（三）優(yōu)點描述：提高可擴展性、增強可靠性、可移植性強、提供對分布式系統(tǒng)的支持、融入OOP（四）缺點描述：效率降低第二章 進程描述與控制前趨圖與程序執(zhí)行一、前趨圖與程序執(zhí)行（一）前趨圖描述：前一個做完，才到后一個做、禁止循環(huán)二、順序執(zhí)行描述：一個跟一個特征：順序、封閉（獨占資源）、可再現(xiàn)三、并發(fā)執(zhí)行描述：互不依賴才能并發(fā)執(zhí)行特征：間斷、失去封閉、不可再現(xiàn)進程的描述一、進程的定義和特征進程實體：程序段、

12、相關(guān)的數(shù)據(jù)段和PCB定義：進程是進程實體的運行過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位特征：動態(tài)、并發(fā)、獨立、異步二、進程的基本狀態(tài)及轉(zhuǎn)換進程的三基態(tài)：就緒（只欠CPU）、執(zhí)行、阻塞（因故無法繼續(xù)執(zhí)行）三態(tài)轉(zhuǎn)換：如圖新增兩態(tài)：創(chuàng)建狀態(tài)、終止狀態(tài)五態(tài)轉(zhuǎn)換：如圖三、掛起操作和進程狀態(tài)的轉(zhuǎn)換掛起原因：終端用戶需要、父進程請求、負荷調(diào)節(jié)、操作系統(tǒng)需要引入掛起后的三態(tài)轉(zhuǎn)換：如圖引入掛起后的五態(tài)轉(zhuǎn)換：如圖四、進程管理中的數(shù)據(jù)結(jié)構(gòu)用于管理控制的數(shù)據(jù)結(jié)構(gòu)：每個資源、進程都有一個數(shù)據(jù)結(jié)構(gòu)用于表征實體資源信息表、進程信息表，包括：標識、描述、狀態(tài)等和一批指針，通過指針能夠鏈接成隊列，便于查找分類：內(nèi)存表、設(shè)備

13、表、文件表、進程表PCB的作用：作為獨立運行基本單位的標識、能實現(xiàn)間斷運行、提供進程管理所需的信息、實現(xiàn)與其他進程的同步與通信PCB的信息：進程標識符（內(nèi)外部）、處理機狀態(tài)、進程調(diào)度信息、進程控制信息PCB組織方式：線性方式、鏈接方式、索引方式進程控制一、操作系統(tǒng)內(nèi)核描述：常駐內(nèi)存的模塊目的：保護軟件、提高OS運行效率系統(tǒng)態(tài)、管態(tài)、內(nèi)核態(tài)：高特權(quán)、訪問所有寄存器.存儲區(qū)、傳統(tǒng)OS都在系統(tǒng)態(tài)運行用戶態(tài)、目態(tài)：低特權(quán)、執(zhí)行指定指令.訪問指定寄存器和存儲區(qū)支撐功能：中斷處理、時鐘管理、原語操作資源管理功能：進程管理、存儲器管理、設(shè)備管理二、進程的創(chuàng)建層次結(jié)構(gòu)：UNIX有父子關(guān)系，Windows只有控

14、制與被控制關(guān)系進程圖：描述家庭關(guān)系的圖引起創(chuàng)建進程的事件：用戶登錄、作業(yè)調(diào)度、提供服務（譬如打印）、應用請求進程的創(chuàng)建：申請空白PCB、分配物理.邏輯資源、初始化PCB、如果能插入就緒，就插三、進程的終止引起進程終止的事件：正常結(jié)束、異常結(jié)束、外界干預進程的終止過程：根據(jù)標識符、終止執(zhí)行.立即調(diào)度、子孫終止、資源歸還、移出隊列四、進程的阻塞與喚醒引起進程阻塞和喚醒的事件：向系統(tǒng)請求共享資源失敗、等待某操作完成、新數(shù)據(jù)尚未到達、等待新任務到達進行阻塞過程：發(fā)生上述的某事件，就進入block過程，主動將狀態(tài)改為阻塞，PCB插入阻塞隊列（分類插入），處理機分配給另一就緒進程，切換，并保留被阻塞進程的

15、處理機狀態(tài)進程喚醒過程：由釋放資源的進程調(diào)用wakeup原語，即移出阻塞隊列，合作/相關(guān)的進程中安排wakeup五、進程的掛起與激活進程的掛起：活動靜止，suspend原語進程正在執(zhí)行，就轉(zhuǎn)向調(diào)度程序重新調(diào)度進程的激活過程：從外存調(diào)入active原語到內(nèi)存，檢查進程現(xiàn)行狀態(tài)，靜止活動搶占調(diào)度策略：靜止就緒進程就緒隊列，比較當前進程優(yōu)先度，有機會立即剝奪當前進程運行進程同步描述：能夠并發(fā)、改善利用率、提高吞吐量、但使系統(tǒng)復雜一、進程同步的基本概念制約關(guān)系：間接相互制約關(guān)系、直接相互制約關(guān)系間接相互制約關(guān)系：互斥共享直接相互制約關(guān)系：合作共享，異步性要做好臨界資源：生產(chǎn)者-消費者問題、臨界區(qū)、：進

16、入?yún)^(qū)、臨界區(qū)、退出區(qū)、剩余區(qū)同步機制應遵循的規(guī)則：空閑讓進、忙則等待、有限等待、讓權(quán)等待二、硬件同步機制關(guān)中斷：缺點多：濫用關(guān)中斷.造成嚴重后果、關(guān)中斷時間過長、不適用于多CPU系統(tǒng)（因為一個處理器關(guān)中斷并不能防止進程在其他處理器上執(zhí)行相同的臨界段代碼）Test-and-Set：不斷測試lock，如果是FALSE，就進入臨界區(qū)，并lock = TRUE；否則測試到TS(s) = TRUESwap指令：一直等，直到key = TRUE但以上都不符合“讓權(quán)等待”原則三、信號量機制整形信號量：S0，就一直等，直到釋放互斥資源記錄型信號量：整形信號量不符合“讓權(quán)等待”原則。如果有資源，就分配，如果無，

17、就插入阻塞隊列；釋放資源，如果有等待，就激活AND型信號量：一口氣全分配信號量集：有多個信號量（S信號量,至少要t個,每次分配d個）四、信號量的應用利用信號量實現(xiàn)進程互斥：mutex = ( -1, 0, 1）= （無，一臨一阻隊， 一臨一信隊）利用信號量實現(xiàn)前趨關(guān)系：需要的信號量被占用了，就這樣實現(xiàn)五、管程機制描述：為解決信號量機制分散、容易死鎖的問題，發(fā)明新同步工具管程定義：定義一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一組操作，這組操作能同步進程和改變管程中的數(shù)據(jù)組成：管程名稱、數(shù)據(jù)結(jié)構(gòu)的說明、對數(shù)據(jù)結(jié)構(gòu)進行操作的過程、初始化的語句特性：模塊化、抽象數(shù)據(jù)類型、信息掩蔽管程與進程

18、不同：都有數(shù)據(jù)結(jié)構(gòu)，一個公.一個私、管程操作同步.初始化.進程順序執(zhí)行、管程為解決互斥資源.進程實現(xiàn)并發(fā)性、進程調(diào)用管程.進程主動.管程被動、管程不能并發(fā).進程能并發(fā)、管程是OS的一個資源管理模塊.進程有動態(tài)性條件變量：增加一個條件變量，萬一發(fā)生意外，在管程中被掛起或被阻塞，下一個進程都可以繼續(xù)執(zhí)行經(jīng)典進程的同步問題一、生產(chǎn)者-消費者問題記錄型信號量解決：如果緩沖區(qū)空，而且能夠獲取信號量，就投放產(chǎn)品；如果緩沖區(qū)有產(chǎn)品，而且能夠獲取信號量，就消費AND信號量解決：一口氣全分配管程解決：利用管程只有一個進程能夠使用的屬性二、哲學家進餐問題記錄型信號量解決：先拿左.后那右、先放左.后放右解決死鎖：最

19、多4人取筷子、先檢查.有左右筷子才能取、奇左右.偶右左AND信號量解決：一口氣全分配三、讀者-寫者問題描述：可以多讀一、一旦開始寫.就不能讀或?qū)懹涗浶托盘柫拷鉀Q：讀操作：等rmutex就是為了改readcount無人讀？看看是否在寫.等wmutexreadcount+自增完成.rmutex還你讀讀讀等rmutex為了自減readcount無人讀？可以寫了.還你wmutex寫操作：等wmutex.即無讀無寫寫完.還你wmutex利用信號量集機制：讀：限制reader個數(shù)如果mx是1.就讀最后釋放一個reader個數(shù)寫：如果mx是1.并且讀者數(shù)為0.就寫寫完釋放mx進程通信一、進程通信類型共享存儲

20、器系統(tǒng)：某些數(shù)據(jù)結(jié)構(gòu)和共享存儲區(qū)、管道通信系統(tǒng)、消息傳遞系統(tǒng)、C-S系統(tǒng)二、消息傳遞通信的實現(xiàn)方式（一）直接消息傳遞系統(tǒng)1.直接通信原語：對稱尋址方式、非對稱尋址方式2.消息格式：較短的減少系統(tǒng)處理和存儲的開銷、較長可以方便3.進程同步方式：發(fā)塞收塞（進程間緊密同步.無緩沖）、發(fā)通收塞（平常狀態(tài)）、發(fā)通收通（發(fā)生某事件無法繼續(xù)運行）、（無發(fā)塞收通）4.通信鏈路：用“建立連接”原語建立通信鏈路.用完拆、用“發(fā)送命令”原語建立鏈路，還分單向和雙向（二）信箱通信（間接）1.定義：是數(shù)據(jù)結(jié)構(gòu).分信箱頭和信箱體2.原語：創(chuàng)建和撤銷. 發(fā)送和接收3.類型：私用、公用（操作系統(tǒng)創(chuàng)建）、共享（進程創(chuàng)建）4.進

21、程之間的關(guān)系：一對一、多對一、一對多、多對多三、直接消息傳遞系統(tǒng)實例消息緩沖隊列通信機制中的數(shù)據(jù)結(jié)構(gòu)：利用數(shù)據(jù)結(jié)構(gòu)式消息緩沖區(qū)、在PCB增加有關(guān)通信的數(shù)據(jù)項原語：設(shè)置發(fā)送區(qū)、申請PCB(B)的緩沖區(qū)i、復制到緩沖區(qū)、插入消息隊列、移出消息隊列、復制到接收區(qū)、釋放緩沖區(qū)線程的基本概念描述：就是為了提高程序并發(fā)執(zhí)行的程度一、線程的引入進程的兩個基本屬性：進程是一個可擁有資源的獨立單位、進程同時是一個可獨立調(diào)度和分派的基本單位進程并發(fā)執(zhí)行所需的時空開銷：創(chuàng)建進程、撤銷進程、進程切換線程作為調(diào)度和分派的基本單位：線程輕裝上陣二、線程與進程比較調(diào)度的基本單位：線程是調(diào)度和分派的基本單位、跨進程，會切換進

22、程并發(fā)性：線程的合作.能夠并發(fā)擁有資源：有TCB.但只是必不可少、保證獨立運行的資源獨立性：同一進程的不同線程共享進程的內(nèi)存地址空間和資源系統(tǒng)開銷：因為輕裝.所以減少開銷、提升速度支持多處理機系統(tǒng)：對多線程進程，多個線程可以分配到多個處理機上三、線程的狀態(tài)和線程控制塊線程運行的三個狀態(tài)：和進程一樣線程控制塊TCB：標識符、一組寄存器、運行狀態(tài)、優(yōu)先級、線程專有存儲區(qū)、信號屏蔽、堆棧指針多線程OS中的進程屬性：進程是可擁有資源的基本單位、多個線程可并發(fā)執(zhí)行、進程已不是可執(zhí)行的實體線程的實現(xiàn)一、線程的實現(xiàn)方式內(nèi)核支持線程KLT：優(yōu)點：內(nèi)核調(diào)度同一進程多個線程并行執(zhí)行、一個線程阻塞.其他線程占有處理

23、機、支持小數(shù)據(jù)結(jié)構(gòu)和堆棧.切換較快開銷小、內(nèi)核本身采用多線程技術(shù).提高系統(tǒng)執(zhí)行速度和效率用戶級線程ULT：優(yōu)點：無需內(nèi)核.節(jié)省模式切換的開銷、調(diào)度算法進程專用、與OS無關(guān).甚至可以在操作系統(tǒng)平臺實現(xiàn) 缺點：一個線程阻塞.同進程的其他線程都會塞、只有一個CPU.只有一個線程能執(zhí)行、按進程分配.不公平組合方式：多對一模型：優(yōu)點：開銷小、缺點：一塞進程全塞、只有一線程訪問內(nèi)核、多線程不能同時在多個處理機上運行一對一模型：一個用戶級線程映射到一個內(nèi)核支持線程多對多模型：一對一和多對一的結(jié)合二、線程的實現(xiàn)內(nèi)核支持線程的實現(xiàn)：創(chuàng)建線程、保存信息、調(diào)度和切換線程、撤銷線程、回收資源用戶級線程的實現(xiàn)：運行時系

24、統(tǒng)：用于管理和控制線程的函數(shù)的集合，這些函數(shù)駐留用戶空間.并作為用戶級線程與內(nèi)核之間的接口內(nèi)核控制線程：連接到LWP，連接到LWP的線程才能與內(nèi)核通信三、線程的創(chuàng)建和終止線程的創(chuàng)建：初始化線程、創(chuàng)建后返回線程標識符線程的終止：終止線程用函數(shù)或系統(tǒng)調(diào)用終止操作.但有些線程被建立就會一直執(zhí)行。大多數(shù)OS，線程被中止后并不立即釋放所占資源，只有“其他線程”執(zhí)行分離函數(shù)才會分離資源，才能被其他線程利用。雖然未釋放的資源也可以被其他線程使用，但要有個“等待線程終止”的連接命令作保險.否則一直阻塞第三章 處理機調(diào)度與死鎖處理機調(diào)度的層次和調(diào)度算法的目標描述：作業(yè)可能要經(jīng)歷多級處理機調(diào)度一、處理機調(diào)度層次（

25、一）高級調(diào)度（長程調(diào)度/作業(yè)調(diào)度）對象是作業(yè)、決定將外存中處于后備隊列的作業(yè)調(diào)入內(nèi)存.創(chuàng)建進程和分配資源.并放入就緒隊列、主要存在于多道批處理系統(tǒng)，分時和實時系統(tǒng)不設(shè)置高級調(diào)度（二）低級調(diào)度（進程調(diào)度/短程調(diào)度）對象是進程（/內(nèi)核級線程）、決定就緒隊列哪個進程獲得處理機、多道批.分時和實時都要配置（三）中級調(diào)度（內(nèi)存調(diào)度）（存儲器的對換功能）對象是暫時不能運行的進程、把這些進程調(diào)到外存.設(shè)為掛起狀態(tài)、一有條件.稍微有空就變?yōu)榫途w狀態(tài)分級按運行頻率劃分二、處理機調(diào)度算法的目標（一）共同目標提高資源利用率、公平、平衡、策略強制執(zhí)行（二）批處理系統(tǒng)目標處理機利用率高、平均周轉(zhuǎn)時間短、系統(tǒng)吞吐量高（三

26、）分時系統(tǒng)目標響應時間快、均衡性（四）實時系統(tǒng)目標截止時間保證、可預測性作業(yè)與作業(yè)調(diào)度一、批處理系統(tǒng)中的作業(yè)（一）作業(yè)和作業(yè)步作業(yè)：包括程序.數(shù)據(jù)和作業(yè)說明書、在批處理系統(tǒng).作業(yè)是基本單位從外存調(diào)入內(nèi)存作業(yè)步：獨立步驟（二）作業(yè)控制塊（JCB）包括作業(yè)標識、用戶名稱、用戶賬號、作業(yè)類型、作業(yè)狀態(tài)、調(diào)度信息、資源需求、資源使用情況等流程：進入系統(tǒng)創(chuàng)建JCB根據(jù)類型放到后備隊列等待調(diào)度入內(nèi)存根據(jù)JCB和作業(yè)說明書控制完成回收資源.撤銷JCB（三）作業(yè)運行的三個階段和三種狀態(tài)收容階段-后備狀態(tài)、運行階段-運行狀態(tài)、完成階段-完成狀態(tài)二、作業(yè)調(diào)度的主要任務也叫：接納調(diào)度考慮：接納多少作業(yè)、接納哪些作業(yè)

27、三、先來先服務FCFS和短作業(yè)優(yōu)先SJF調(diào)度算法（一）先來先服務FCFS就這樣.完成或阻塞才分配到其他進程、實際中和其他算法結(jié)合使用有利于長作業(yè)（進程），不利于短作業(yè)（進程）（二）短作業(yè)優(yōu)先SJF實際用得多、要預知作業(yè)運行時間、長作業(yè)、緊迫作業(yè)不利、無人機交互四、優(yōu)先級調(diào)度算法和高響應比優(yōu)先調(diào)度算法（一）優(yōu)先級調(diào)度算法外部賦予作業(yè)優(yōu)先級（二）高響應比優(yōu)先調(diào)度算法集SJF.FCFS的優(yōu)點.兼顧長作業(yè)、但要做相應比計算.增加系統(tǒng)開銷（Exp.做過類似）進程調(diào)度一、進程調(diào)度的任務、機制和方式（一）進程調(diào)度的任務保存處理機的現(xiàn)場信息、按某種算法選取進程、把處理器分配給進程（二）進程調(diào)度機制排隊器：插入

28、就緒隊列分配器：從就緒隊列取出.分配處理機上下文切換器：保存、裝入新的CPU現(xiàn)場信息等內(nèi)容（三）進程調(diào)度方式非搶占方式：只有完成或因某事無法繼續(xù)運行、I/O、執(zhí)行了原語操作如block，才會引起進程調(diào)度優(yōu)點：簡單、開銷小、適用大多數(shù)批處理系統(tǒng)搶占方式：對分時系統(tǒng)而言.有人機交互、對實時系統(tǒng)而言.能滿足任務需求主要原則：優(yōu)先權(quán)原則、短進程優(yōu)先原則、時間片原則二、輪轉(zhuǎn)調(diào)度算法（一）輪轉(zhuǎn)法（RR）的基本原理按FCFS策略排成就緒隊列，每隔一定時間就產(chǎn)生一次中斷（二）進程切換時機時間片未用完就完成：馬上調(diào)度隊首進程.啟動新時間片時間片完還沒完成：中斷.進程被調(diào)到就緒隊列隊尾（三）時間片大小的確定太短有

29、利于短進程、太長退化為FCFS算法.要計算平均周轉(zhuǎn)時間（帶權(quán)周轉(zhuǎn)時間）三、優(yōu)先級調(diào)度算法（一）優(yōu)先級調(diào)度算法的類型非搶占式和搶占式（二）優(yōu)先級的類型確定優(yōu)先級的依據(jù)：靜態(tài)優(yōu)先級：進程類型（系統(tǒng)進程優(yōu)先權(quán)高于用戶進程優(yōu)先權(quán)）、進程對資源的需求（少則優(yōu)先）、用戶需求（緊迫程度、花費）動態(tài)優(yōu)先級：先賦予優(yōu)先級，隨著進程推進或等待時間增加而改變四、多隊列調(diào)度算法將一條就緒隊列拆分成多條，各有各調(diào)度算法五、多級反饋隊列調(diào)度算法（一）調(diào)度機制多條就緒隊列、隊列內(nèi)使用FCFS算法.一個時間片未完成就放到下一個隊列的末尾.最后一個隊列用RR方式、按隊列優(yōu)先級調(diào)度.前隊列空才到本隊列運行（二）調(diào)度算法的性能終端

30、型用戶、短批處理作業(yè)用戶、長批處理作業(yè)用戶六、基于公平原則調(diào)度算法（一）保證調(diào)度算法保證處理機公平分配功能：跟蹤進程已經(jīng)執(zhí)行的處理時間、該時間除以n、計算實際處理時間和應獲得時間之比、比較比率、比率最低的獲得處理機（二）公平分享調(diào)度算法考慮多用戶實時調(diào)度描述：實時系統(tǒng)有兩種實時任務HRT和SRT一、實現(xiàn)實時調(diào)度的基本條件（一）提供必要信息就緒時間、開始截止和完成截止時間、處理時間、資源要求、優(yōu)先級（二）系統(tǒng)處理能力強（處理時間i/周期時間i）總和 1. 未考慮任務切換花費的時間還應該留有余地提高系統(tǒng)處理能力的途徑：單處理機系統(tǒng)增強處理能力.顯著減少每個任務的處理時間、多處理機系統(tǒng).就變成（處理

31、時間i/周期時間i）總和 N（三）采用搶占式調(diào)度機制執(zhí)行完關(guān)鍵程序和臨界區(qū)后，能及時將自己阻塞起來，以釋放處理機（四）具有快速切換機制對中斷的快速響應能力、快速的任務分派能力二、實時調(diào)度算法的分類根據(jù)任務性質(zhì)：H/S根據(jù)調(diào)度方式：非搶占式/搶占式（一）非搶占式調(diào)度算法輪轉(zhuǎn)、優(yōu)先調(diào)度，不適合實時系統(tǒng)。進程自動放棄處理機，才進行調(diào)度。（二）搶占式調(diào)度算法基于時鐘中斷的搶占式優(yōu)先級調(diào)度算法：等待時鐘中斷發(fā)生才剝奪當前任務的執(zhí)行立即搶占優(yōu)先調(diào)度算法：好快好快.只要任務未處于臨界區(qū).就立即剝奪當前任務執(zhí)行優(yōu)先權(quán)原則、短作業(yè)（進程）優(yōu)先原則、時間片原則。三、最早截止時間優(yōu)先EDF算法非搶占式調(diào)度方式用于非

32、周期實時任務：開始截止時間早的排前搶占式調(diào)度方式用于周期實時任務：最早截止時間優(yōu)先算法四、最低松弛度優(yōu)先LLF算法 緊急程度越高，優(yōu)先級越高。五、優(yōu)先級倒置（一）優(yōu)先級倒置的形成（二）優(yōu)先級倒置的解決方法繼承動態(tài)優(yōu)先級的方法：P3繼承P1的優(yōu)先級.一方面避免P2搶占處理機、另一方面釋放mutex資源死鎖概述一、資源問題指互斥資源、不可被搶占的資源（一）可重用性資源和消耗性資源可重用性資源：一個只能分配給一個進程使用、順序為請求.使用.釋放、數(shù)目相對固定.運行期間不能創(chuàng)建或刪除可消耗性資源：在進程運行中數(shù)目不斷變化.可為0、可以不斷創(chuàng)建.放入緩沖區(qū)、可以由進程創(chuàng)建.使用并不再返回資源類（二）可搶

33、占性資源和不可搶占性資源可搶占性資源：可以被其他進程搶占.如CPU和主存不可搶占性資源：一旦分配給進程就不能強制收回.要做到底二、計算機系統(tǒng)中的死鎖（一）競爭不可搶占性資源引起死鎖我要你的，你要我的，形成環(huán)路，死鎖（二）競爭可消耗資源引起死鎖譬如消息通信機制.先讀后寫.就會死鎖（三）進程推進順序不當引起死鎖競爭不可搶占性資源引起死鎖的翻版.多畫了一個圖三、死鎖的定義、必要條件和處理方法（一）死鎖的定義這組死鎖進程都在等其他進程釋放所占資源（二）產(chǎn)生死鎖的必要條件互斥條件：一段時間只被一個進程占用請求和保持條件：進程已經(jīng)保持至少一個條件.但有提出新資源請求不可搶占條件：只能在進程用完才能釋放循環(huán)

34、等待條件：存在循環(huán)鏈（三）處理死鎖的方法預防死鎖：設(shè)置限制條件.破壞產(chǎn)生死鎖四個必要條件來預防避免死鎖：在資源動態(tài)分配時.用防止系統(tǒng)進入不安全狀態(tài)檢測死鎖：通過檢測機構(gòu)及時檢測死鎖.采取適當措施以解脫解除死鎖：撤銷進程.回收資源.分配給處于阻塞的進程防范逐漸減弱.但資源利用率提高.進程因資源因素而阻塞的頻度下降預防死鎖一、破壞“請求和保持”條件保證：進程請求資源時，不持有不可搶占資源第一種協(xié)議：一次性全部申請，從而破壞“請求條件”、缺點是資源被嚴重浪費.進程饑餓第二種協(xié)議：先釋放資源.再請求新資源二、破壞“不可搶占”條件當保持了某些不可搶占資源后.提出新資源請求不得滿足.就必須釋放已經(jīng)保持的資

35、源.等需要時再申請缺點：增加周轉(zhuǎn)時間、增加系統(tǒng)開銷、降低系統(tǒng)吞吐量三、破壞“循環(huán)等待”條件總有一個進程占據(jù)了較高序號的資源.此后它繼續(xù)申請的資源必然是空閑的避免死鎖一、系統(tǒng)安全狀態(tài)（一）安全狀態(tài)計算一個資源分配的安全性.如果分配不會導致不安全狀態(tài).才可將資源分配給進程（二）安全狀態(tài)之例（三）由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換二、利用銀行家算法避免死鎖（一）銀行家算法中的數(shù)據(jù)結(jié)構(gòu)Availalbe、Max、Allocation、Need（二）銀行家算法睇wiki“銀行家算法”條目聲明：Request是請求向量Request Need, 否則出錯Request Available, 否則P等待系統(tǒng)試探分

36、配資源給P, 并執(zhí)行Availalbe -= Requeset; Allocation+= Request; Need -= Request死鎖的檢測與解除一、死鎖的檢測（一）資源分配圖圓圈代表進程、方格代表一類資源、邊代表資源分配（二）死鎖的定理簡化資源分配圖.如果不能完全簡化.就會死鎖（三）死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)類似于銀行家算法？二、死鎖的解除常用兩種方法：搶占資源、終止/撤銷進程（一）終止進程的方法終止所有死鎖進程：會功虧一簣逐個終止進程：找到代價最小.考慮優(yōu)先級、已執(zhí)行時間.還需的時間、已用資源、交互式還是批處理式（二）付出代價最小的死鎖解除算法很不實際第四章 存儲器管理存儲器的層次結(jié)構(gòu)

37、一、多層結(jié)構(gòu)的存儲器系統(tǒng)CPU寄存器；高速緩存Cache、主存儲器RAM、磁盤緩存；固定磁盤、可移動存儲介質(zhì)二、可執(zhí)行存儲器就是CPU寄存器和主存.訪問很快二、主存儲器與寄存器（一）主存儲器又叫主存or內(nèi)存.相比CPU執(zhí)行速度.它還是很慢.所以引入寄存器和高速緩存（二）寄存器完全與CPU協(xié)同工作.但好貴三、高速緩存和磁盤緩存（一）高速緩存?zhèn)浞葜鞔嬷休^常用的數(shù)據(jù).以減少CPU對主存儲器的訪問次數(shù)（二）磁盤緩存因為磁盤I/O速度遠低于主存訪問速度.所以設(shè)置磁盤緩存來暫存頻繁使用的一部分磁盤數(shù)據(jù)和信息程序的裝入和鏈接用戶程序要在OS中運行.要先裝入內(nèi)存.再轉(zhuǎn)換為一個可執(zhí)行程序：編譯、鏈接、裝入一、程

38、序的裝入（一）絕對裝入方式當OS很小.且僅能運行單道程序時.完全有可能知道程序駐留在內(nèi)存的位置.那么就可以產(chǎn)生絕對地址的目標代碼（二）可重定位裝入方式（靜態(tài)重定位）多道程序下.邏輯地址和物理地址不同.要加上起始地址.但只在進程裝入時一次完成.故稱為靜態(tài)重定位.可裝到內(nèi)存任何允許位置（三）動態(tài)運行時的裝入方式需要重定位寄存器，運行時允許移動二、程序的鏈接（一）靜態(tài)鏈接方式要解決：對相對地址進行修改（子程序的相對地址）、變換外部調(diào)用符號（生成可執(zhí)行文件后不再拆開.又叫靜態(tài)鏈接方式）（二）裝入時動態(tài)鏈接便于修改和更新（各模塊分開存放）、便于實現(xiàn)對目標模塊的共享（靜態(tài)每個應用模塊必有目標模塊的拷貝.無

39、法共享.但動態(tài)可以一個目標鏈接多個應用模塊）（三）運行時動態(tài)鏈接運行時發(fā)現(xiàn)沒有.就由OS去找這個模塊內(nèi)功加快程序裝入過程和節(jié)約大量內(nèi)存空間連續(xù)分配存儲管理方式一、單一連續(xù)分配分系統(tǒng)區(qū)和用戶區(qū).單用戶.單任務操作系統(tǒng)二、固定分區(qū)分配劃分分區(qū)的方法：大小相等（一臺計算機控制多臺相同冶煉爐）和大小不等內(nèi)存分配：通常按大小排隊.建立分區(qū)使用表.如果找不到大小足夠的分區(qū).就拒絕分配內(nèi)存三、動態(tài)分區(qū)分配動態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)：空閑分區(qū)表、空閑分區(qū)鏈動態(tài)分區(qū)分配算法：之后介紹4種分配算法和3中索引搜索算法分區(qū)分配操作：分配內(nèi)存、回收內(nèi)存四、基于順序搜索的動態(tài)分區(qū)分配算法（不太大系統(tǒng)）首次適應算法（FF）、

40、循環(huán)首次適應算法(NF)、最佳適應算法(BF)、最壞適應算法(WF)五、基于索引搜索的動態(tài)分區(qū)分配算法(大、中型系統(tǒng))快速適應算法（以空間換時間）、伙伴系統(tǒng)（合并回收與均勻分配）、哈希算法六、動態(tài)可重定位分區(qū)分配緊湊、動態(tài)重定位、動態(tài)重定位分區(qū)分配算法對換一、多道程序環(huán)境下的對換技術(shù)（一）對換的引入避免內(nèi)存全部被阻塞.外存卻有很多作業(yè)無法進入內(nèi)存（二）對換的類型整體對換（進程對換）、頁面對換（部分對換）支持虛擬存儲系統(tǒng)二、對換空間的管理（一）對換空間管理的主要目標文件區(qū)管理主要目標：先提高文件存儲空間的利用率.離散分配對換空間管理的主要目標：先提高換入換出的速度，連續(xù)分配方式（二）對換區(qū)空閑盤

41、塊管理中的數(shù)據(jù)結(jié)構(gòu)與內(nèi)存的相似（三）對換空間的分配與回收與內(nèi)存分配和回收雷同三、進程的換出與換入（一）進程的換出選擇被換出的進程：阻塞或睡眠狀態(tài)、優(yōu)先級最低、內(nèi)存駐留時間進程換出過程（二）進程的換入如果發(fā)現(xiàn)許多進程運行時缺頁且內(nèi)存緊張.才啟動對換程序.將部分進程調(diào)至外存如果缺頁率明顯減少.系統(tǒng)吞吐量已下降.則可以暫停運行對換程序分頁存儲管理方式其實分三種：分頁、分段、段頁式一、分頁存儲管理的基本方法（一）頁面和物理塊頁面：頁號頁面大小：太小.進程占用較多頁面、太多.碎片多、適中.1kB8kB（二）地址結(jié)構(gòu)頁號：P頁內(nèi)地址（偏移量）：d兩個都有公式計算（三）頁表從頁號到物理塊號的映射二、地址變換

42、機構(gòu)（一）基本的地址變換機構(gòu)如果發(fā)現(xiàn)頁號頁表長度.就引發(fā)越界中斷；否則頁表始址+頁號*頁表項長度=物理塊號（二）具有快表的地址變換機構(gòu)有個快表在高速緩存三、訪問內(nèi)存的有效時間EAT = t +t = 2t（內(nèi)存）EAT = a*+(t+)(1-a)+t = 2t+ - t* a（快表）四、兩級和多級頁表（一）兩級頁表（二）多級頁表五、反置頁表（一）反置頁表的引入（二）地址變換分段存儲管理方式一、分段存儲管理的基本方法（一）方便編程邏輯地址是由段名（段號）和段內(nèi)偏移量（段內(nèi)地址）決定的（二）信息共享段是信息的邏輯單位.簡化共享過程（三）信息保護就是可以加個標識.不允許讀寫（四）動態(tài)增長可以解決這

43、個問題（五）動態(tài)鏈接4.2.2二、分段系統(tǒng)的基本原理（一）分段每個段有一個段號，連續(xù)的分區(qū)（二）段表實現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射，段長和基址（三）地址變換機構(gòu)段表項數(shù)目比頁表項數(shù)目少.其所需的聯(lián)想存儲器相對較少.減少存取數(shù)據(jù)的時間（四）分頁和分段的主要區(qū)別頁是信息的物理單位.分頁是系統(tǒng)管理上的需要while 段是存儲管理方式中的邏輯單位.分段目的在于更好滿足用戶的需要頁大小固定.段大小不固定分頁的用戶程序地址是一維的.分段是二維的三、信息共享（一）分頁系統(tǒng)中對程序和數(shù)據(jù)的共享每個進程都有頁表.也都指向相同的物理塊號（二）分段系統(tǒng)中的程序和數(shù)據(jù)的共享可重入代碼是一種不允許任何進程對它進行修改的

44、代碼配以局部數(shù)據(jù)區(qū).把執(zhí)行中可能改變的部分拷貝到該數(shù)據(jù)區(qū).這樣執(zhí)行時只需對該數(shù)據(jù)區(qū)中的內(nèi)容修改即可四、段頁式存儲管理方式分段分頁.每段一個段名段號.比較.加法算段表段號得到頁號.(比較).加法算頁表頁號得到物理塊號.加頁內(nèi)地址得物理地址第五章 虛擬存儲器出現(xiàn)問題：作業(yè)很大、大量作業(yè)要求運行虛擬存儲器概述一、常規(guī)存儲管理方式的特征和局部性原理（一）常規(guī)存儲管理方式的特征傳統(tǒng)：一次性、駐留性（二）局部性原理絕大部分順序執(zhí)行、調(diào)用進度不超過5、循環(huán)結(jié)構(gòu)由少數(shù)指令構(gòu)成.但多次執(zhí)行、多對數(shù)據(jù)結(jié)構(gòu)的處理.這些處理局限于很小的部分時間、空間局限性（三）虛擬存儲器的基本工作情況將少數(shù)頁面或段先裝入內(nèi)存即可運行

45、二、虛擬存儲器的定義和特征（一）虛擬存儲器的定義有請求調(diào)入功能和置換功能.能邏輯上對內(nèi)存內(nèi)容加以擴充的一種存儲器系統(tǒng)（二）虛擬存儲器的特征多次性、對換性、虛擬性三、虛擬存儲器的實現(xiàn)方式（一）分頁請求系統(tǒng)硬件支持：請求分頁的頁表機制、缺頁中斷機制、地址變換機制實現(xiàn)請求分頁的軟件（二）請求分段系統(tǒng)硬件支持：請求分段的段表機制、缺段中斷機構(gòu)、地址變換機構(gòu)軟件支持請求分頁存儲管理方式一、請求分頁中的硬件支持（一）請求頁表機制（二）缺頁中斷機構(gòu)（三）地址變換機構(gòu)二、請求分頁中的內(nèi)存分配（一）最小物理塊數(shù)的確定（二）內(nèi)存分配策略策略：固定分配局部置換、可變分配全局置換、可變分配局部置換（三）物理塊分配算法

46、算法：平均分配算法、按比例分配算法、考慮優(yōu)先權(quán)的分配算法三、頁面調(diào)入策略（一）何時調(diào)入頁面預調(diào)頁策略：手動指出哪些頁要調(diào)入內(nèi)存、成功率偏低請求調(diào)頁策略：一次調(diào)入一頁.須較大系統(tǒng)開銷（二）從何處調(diào)入頁面系統(tǒng)擁有足夠的對換區(qū)空間：進程進行前就把進程相關(guān)的文件拷貝到對換區(qū)系統(tǒng)缺少足夠的對換區(qū)空間：未修改過的不到對換區(qū).以后要用再從文件區(qū)調(diào)入UNIX方式：從文件區(qū)入.出到對換區(qū)、允許頁面共享（三）頁面調(diào)入過程？（四）缺頁率？頁面置換算法抖動：一個進程在運行中把大部分時間都花費在頁面置換工作上 一、最佳置換算法和先進先出置換算法（一）最佳置換算法（看未來）要知道未來需要哪頁.實際上不可能（二）先進先出頁

47、面置換算法剔走最老的頁二、最近最久未使用和最少使用置換算法（LRU看過去）（一）最近最久未使用看最近的n個，最老的踢走（二）LRU置換算法的硬件支持寄存器： 8位寄存器.R7R0.R值最小的頁被踢出棧：最新訪問的是棧頂（三）最少使用置換算法現(xiàn)實使用這個多.一旦訪問就在最高位置一三、Clock置換算法（一）簡單的CLOCK置換算法也叫最近未使用算法.就是有個訪問位，10換出（二）改進型CLOCK置換算法四類：A M = 0 0 1 1第一步：先找 0 0第二步：再找 0 1，并置所有頁0 X第三步：再找0 0，最后找0 1，一定找到優(yōu)點：減少I/O缺點：增加系統(tǒng)開銷四、頁面緩沖算法（一）影響頁面

48、換進換出效率的若干因素頁面置換算法、寫回磁盤的頻率、讀入內(nèi)存的頻率（二）頁面緩沖算法PBA顯著降低頁面換進、換出頻率，減少頁面換進換出的開銷換入換出的開銷大幅減少，才能使用簡單的置換策略，如FIFO要在內(nèi)存中設(shè)置：空閑頁面鏈表、修改頁面鏈表五、訪問內(nèi)存的有效時間如果考慮快表的命中率和缺頁率：EAT = .如果僅考慮缺頁率：EAT = “抖動”與工作集一、多道程序度與“抖動”（一）現(xiàn)象先增后減（二）原因進程太多，物理塊不夠分二、工作集（一）工作集的基本概念如果可以預知，就可以先調(diào)入內(nèi)存，大大降低缺頁率，從而顯著提高處理機利用率（二）工作集的定義引用的集合，類似FIFO三、“抖動”的預防方法（一）

49、采取局部置換策略“抖動”影響較小（二）把工作集算法融入到處理機調(diào)度中每個進程在內(nèi)存的駐留頁面是否足夠多，如果是就調(diào)入新作業(yè)、否則增加新物理塊（三）利用L=S準則調(diào)節(jié)缺頁率缺頁之間的平均時間= 平均缺頁服務時間（四）選擇暫停的進程先暫停優(yōu)先級最低的進程、在選擇并不重要，但較大的進程請求分段存儲管理方式其實也類似于分頁，要硬件和軟件支持一、請求分段中的硬件支持（一）請求段表機制段表項：段名、段長、段基址、存取方式、訪問字段A、修改位M、存在位P、增補位、外存始址A、M：改進型CLOCK置換算法P：本段是否調(diào)入內(nèi)存增補位：看是否做過動態(tài)增長（二）缺段中斷機制 （圖5-12）萬一虛段S不在內(nèi)存中，就阻

50、塞請求進程。如果沒有空閑區(qū)，就要拼接空閑區(qū)或者淘汰實段以形成空閑區(qū)之后讀入段S，修改段表及內(nèi)存空區(qū)鏈（三）地址變換機構(gòu)就是一個地址變換機構(gòu)二、分段的共享和保護（一）共享段表共享進程計數(shù)count、存取控制字段、段號（二）共享段的分配與回收共享段的分配、共享段的回收（三）分段保護越界檢查、存取控制檢查、環(huán)保護機構(gòu)第六章 輸入輸出系統(tǒng)I/O系統(tǒng)的功能、模型和接口一、I/O系統(tǒng)的基本功能（一）隱藏物理設(shè)備的細節(jié)（二）與設(shè)備的無關(guān)性自動安裝并尋找驅(qū)動程序，即插即用（三）提高處理機和I/O設(shè)備的利用率讓處理機和I/O設(shè)備并行操作（四）對I/O設(shè)備進行控制這是驅(qū)動程序的功能（五）確保對設(shè)備的正確共享獨占設(shè)

51、備：打印機、磁帶機共享設(shè)備：磁盤（六）錯誤處理低級能夠解決就不向高級報告，請求高級軟件解決二、I/O系統(tǒng)的層次結(jié)構(gòu)和模型（一）I/O軟件的層次結(jié)構(gòu)用戶層I/O軟件設(shè)備獨立性軟件：映射、保護、分塊、緩沖、分配設(shè)備驅(qū)動程序：設(shè)置設(shè)備寄存器、檢查狀態(tài)中斷處理程序（二）I/O系統(tǒng)中各種模塊之間的層次視圖I/O系統(tǒng)上下接口（圖6-2）I/O系統(tǒng)的分層：中斷處理程序設(shè)備驅(qū)動程序設(shè)備獨立性軟件三、I/O系統(tǒng)接口（一）塊設(shè)備接口塊設(shè)備、隱藏磁盤二維結(jié)構(gòu)、抽象命令映射為低層操作（二）流設(shè)備接口（Unix的）字符設(shè)備：效率低、不可尋址get和put操作：有緩沖區(qū)in-control指令：互斥方式實現(xiàn)共享（三）網(wǎng)絡(luò)

52、通信接口I/O設(shè)備和設(shè)備控制器一、I/O設(shè)備（一）I/O設(shè)備的類型按使用特性：存儲設(shè)備、I/O設(shè)備（輸入輸出交互的）按傳輸速率：低速、中速、高速（二）設(shè)備與控制器之間的接口接口：數(shù)據(jù)信號線、控制信號線、狀態(tài)信號線二、設(shè)備控制器（一）設(shè)備控制器的基本功能接收和識別命令、數(shù)據(jù)交換、標識和報告設(shè)備的狀態(tài)、數(shù)據(jù)緩沖區(qū)、差錯控制（二）設(shè)備控制器的組成設(shè)備控制器與處理機的接口、設(shè)備控制器與設(shè)備的接口、I/O邏輯三、內(nèi)存映像I/O（一）利用特定的I/O指令缺點：訪問內(nèi)存和訪問設(shè)備要兩種不同的指令（二）內(nèi)存映像I/O就是k為界限，0kn-1，就是內(nèi)存地址；kn，就是寄存器地址。統(tǒng)一了對內(nèi)存和對控制器的訪問方法

53、四、I/O通道（一）I/O通道設(shè)備的引入這是一種特殊的處理機，但只局限于I/O相關(guān)的指令、而且沒有自己的內(nèi)存（二）通道類型字節(jié)多路通道：一個大水喉，多條小水管；一個換頭快，一個速率慢數(shù)組選擇通道：利用率低數(shù)組多路通道：甚至可以并行操作（三）“瓶頸”問題增加通路即可解決中斷機構(gòu)和中斷處理程序一、中斷簡介（一）中斷和陷入中斷：由外部設(shè)備引起，暫停當前程序，執(zhí)行中斷處理程序陷入：CPU內(nèi)部事件引起的，多是出錯故障（二）中斷向量表和中斷優(yōu)先級中斷向量表：asm有學中斷優(yōu)先級：現(xiàn)實中有多個中斷信號源，要規(guī)定不同優(yōu)先級（三）對多中斷源的處理方式屏蔽中斷：順序執(zhí)行。優(yōu)點簡單；缺點無視實時中斷請求嵌套中斷：有

54、個優(yōu)先級二、中斷處理程序步驟測定是否有未響應中斷信號；保護被中斷進程的CPU環(huán)境；轉(zhuǎn)入相應設(shè)備處理程序；中斷處理；恢復CPU現(xiàn)場并退出中斷設(shè)備驅(qū)動程序一、設(shè)備驅(qū)動程序概述（一）設(shè)備驅(qū)動程序的功能接收命令和參數(shù)，并轉(zhuǎn)換為低層操作序列檢查I/O合法性，了解I/O工作狀態(tài)，傳遞I/O設(shè)備操作有關(guān)參數(shù)，設(shè)置設(shè)備工作方式及時響應設(shè)備控制器發(fā)來的中斷請求，并根據(jù)中斷類型，調(diào)用響應中斷處理程序（二）設(shè)備驅(qū)動程序的特點抽象的I/O請求轉(zhuǎn)換成具體的I/O操作，反映給I/O進程和硬件特性緊密相關(guān)，終端驅(qū)動程序可以只有一個常用控制方式：中斷驅(qū)動、DMA一部分必須用匯編語言寫，很多驅(qū)動程序基本部分已經(jīng)固化在ROM允許

55、可重入（三）設(shè)備處理方式一類設(shè)備一個進程一個I/O進程負責各類設(shè)備的I/O操作只為各類設(shè)備設(shè)置相應的設(shè)備驅(qū)動程序，供用戶或系統(tǒng)進程調(diào)用（目前用得最多）二、設(shè)備驅(qū)動程序的處理過程（一）將抽象要求轉(zhuǎn)換為具體要求（二）對服務請求進行校驗譬如要求打印機輸入數(shù)據(jù)（三）檢查設(shè)備的狀態(tài)檢測寄存器中的不同位，了解設(shè)備的狀態(tài)（四）傳送必要參數(shù)波特率、奇偶校驗等等參數(shù)（五）啟動I/O設(shè)備 了解數(shù)據(jù)是否到達三、對I/O設(shè)備的控制方式（一）使用輪詢的可編程I/O方式無限等待，好浪費CPU（二）使用中斷的可編程I/O方式百倍提高CPU利用率（三）直接存儲器訪問方式至少傳送一個數(shù)據(jù)塊，DMA方式提高CPU和I/O之間的并

56、行程度（四）I/O通道控制方式使用通道程序完成CPU指定的I/O任務與設(shè)備無關(guān)的I/O軟件一、與設(shè)備無關(guān)軟件的基本概念（一）以物理設(shè)備名使用設(shè)備以前應用程序與物理設(shè)備直接相關(guān)（二）引入了邏輯設(shè)備名通過更換邏輯設(shè)備表即可改變顯示終端（三）邏輯設(shè)備名稱到物理設(shè)備名稱的轉(zhuǎn)換要搞一張邏輯設(shè)備表二、與設(shè)備無關(guān)的軟件（一）設(shè)備驅(qū)動程序的統(tǒng)一接口要有統(tǒng)一接口，同時抽象設(shè)備名要映射到適當?shù)尿?qū)動程序上（二）緩沖管理設(shè)置緩沖區(qū)，緩和CPU和I/O設(shè)備之間的速度矛盾、提高CPU利用率（三）差錯控制暫時性錯誤：只有連續(xù)多次出錯才報告上層，否則由設(shè)備驅(qū)動程序自己處理持久性錯誤：要查清發(fā)生錯誤的原因，避免以后再發(fā)生錯誤（

57、四）對獨立設(shè)備的分配與回收獨占設(shè)備要先申請（五）獨立于設(shè)備的邏輯數(shù)據(jù)塊注：與設(shè)備無關(guān)軟件功能：設(shè)備驅(qū)動程序的統(tǒng)一接口、緩沖、錯誤報告、分配與釋放專用設(shè)備、提高與設(shè)備無關(guān)的塊大小三、設(shè)備分配（一）設(shè)備分配中的數(shù)據(jù)結(jié)構(gòu)系統(tǒng)設(shè)備表SDT設(shè)備控制表DCT：類型、標識符、狀態(tài)、設(shè)備隊列隊首指針、重復執(zhí)行次數(shù)、指向控制表DCT的指針控制器控制表COCT通道控制表CHCT（二）設(shè)備分配時應考慮的因素設(shè)備固有屬性：獨占、共享、虛擬設(shè)備設(shè)備分配算法：FCFS、優(yōu)先級高優(yōu)先安全性：安全、不安全（三）獨占設(shè)備的分配程序獨占設(shè)備：分配設(shè)備、控制器、通道如果要設(shè)備無關(guān)地找設(shè)備，就要從SDT找DCT，再逐個測試安全性四、

58、邏輯設(shè)備名到物理設(shè)備名映射的實現(xiàn)（一）邏輯設(shè)備表LUT邏輯設(shè)備名、物理設(shè)備名、設(shè)備驅(qū)動程序的入口地址（二）邏輯設(shè)備表設(shè)置問題整個系統(tǒng)一張LUT（單用戶）或每個用戶一張LUT（多用戶）用戶層的I/O軟件一、系統(tǒng)調(diào)用與庫函數(shù)（一）系統(tǒng)調(diào)用使用系統(tǒng)調(diào)用I/O設(shè)備，用戶態(tài)內(nèi)核態(tài)用戶態(tài)（二）庫函數(shù)庫函數(shù)與調(diào)用程序接在一起二、假脫機系統(tǒng)（Spooling）（一）假脫機技術(shù)利用專門的外圍控制機，先將低速I/O設(shè)備上的設(shè)局傳送到高速磁盤上，或相反（二）SPOOLing的組成輸入井和輸出井、輸入緩沖區(qū)和輸出緩沖區(qū)、輸入進程和輸出進程、井管理程序（三）SPOOLing系統(tǒng)的特點提高I/O速度、將獨占設(shè)備改造為共享

59、設(shè)備、實現(xiàn)虛擬設(shè)備功能（四）假脫機打印機系統(tǒng)磁盤緩沖區(qū)、打印緩沖區(qū)、假脫機管理進程和假脫機打印進程（五）守護進程有個假脫機目錄，由守望進程按目錄文件依次完成各個進程設(shè)備的請求，就可以將一個獨占設(shè)備改為多個進程共享設(shè)備緩沖區(qū)管理一、緩沖的引入（一）緩和CPU與I/O設(shè)備間速度不匹配的矛盾速度有差距，都可以設(shè)置緩沖區(qū)（二）減少對CPU的中斷頻率（三）解決數(shù)據(jù)粒度不匹配的問題生產(chǎn)者生產(chǎn)的數(shù)量和消費者消費的數(shù)量差距（四）提高CPU和I/O設(shè)備之間的并行性CPU和打印機可以并行工作呢二、單緩沖區(qū)和雙緩沖區(qū)（一）單緩沖區(qū)緩沖區(qū)也會阻塞（二）雙緩沖區(qū)CPU執(zhí)行第一行中的命令時，用戶可以繼續(xù)向第二緩沖區(qū)輸入下

60、一行數(shù)據(jù)如果兩臺電腦只設(shè)置單緩沖，就要再設(shè)置一個接收緩沖區(qū)，一個發(fā)送緩沖區(qū)三、環(huán)形緩沖區(qū)（一）環(huán)形緩沖區(qū)的組成空區(qū)R，裝滿的區(qū)G，正在使用的現(xiàn)行工作緩沖區(qū)C；另外還有多個指針（二）環(huán)形緩沖區(qū)的使用Getbuf和Releasebuf（三）進程之間的同步問題Nexti趕上Nextg：輸入速度處理速度Nextg趕上Nexti：處理速度輸入速度四、緩沖池（一）緩沖池的組成專為生產(chǎn)者-消費者設(shè)置的，包含一個管理數(shù)據(jù)結(jié)構(gòu)和一組操作函數(shù)，管理多個緩沖區(qū)包括空白緩沖隊列、輸入隊列、輸出隊列（二）Getbuf過程和Putbuf過程設(shè)置MS(type)互斥訪問緩沖池隊列和RS(type)進程同步使用緩沖區(qū)（三）緩