第一章：引論操作系統(tǒng)是運(yùn)行在內(nèi)核態(tài)的軟件，為程序猿提供資源集抽象以及管理硬件1.1.2主要任務(wù)：記錄那個(gè)程序在用什么資源，管理資源分配，評估使用代價(jià)，調(diào)節(jié)沖突1.3.11.操作系統(tǒng)必須知道所有的寄存器，以便中斷時(shí)保存進(jìn)度2.用戶程序在用戶態(tài)運(yùn)行時(shí)，僅允許執(zhí)行至靈級的一個(gè)子集，一般不能調(diào)用IO和內(nèi) 存保護(hù)指令3.陷阱：a.用于執(zhí)行系統(tǒng)調(diào)用b.多數(shù)由硬件引起，用于警告異常 4.超線程：無并行處理，線程切換納秒級1.3.2存儲器 1.寄存器（和CPU一樣快）-》高速緩存（多級緩存）-》主存（RAMROMEEROM閃存）1.3.3 上下文切換：多道程序系統(tǒng)中從一個(gè)程序切換到另一個(gè)程序1.3.5 1.設(shè)備驅(qū)動程序：控制IO設(shè)備，與控制器對話并收發(fā)命令 2.設(shè)備存儲器：映射到操作空間 A．優(yōu)點(diǎn)：不需要特定IO指令 B．缺點(diǎn)：占地址空間（8088） 3.實(shí)現(xiàn)輸入輸出的方法： A．忙等待：設(shè)備驅(qū)動循環(huán)檢查IO B．操作完成時(shí)中斷 C．使用特殊的直接存儲器訪問芯片DMA1.3.6 1.USB：通用串行總線，鍵盤鼠標(biāo)等慢速設(shè)備1.3.7啟動1.加電-》BIOS檢查硬件-》BIOS查詢啟動設(shè)備（設(shè)備第一扇區(qū)用啟動簽名才可以作為啟動設(shè)備）-》硬盤第一區(qū)（MBR），分區(qū)表，超級塊等1.5.1進(jìn)程 1.本質(zhì)：正在執(zhí)行的程序的實(shí)例，地址空間（coreimage進(jìn)程可讀寫，有數(shù)據(jù)和堆棧）。 2.相關(guān)：資源集（寄存器，報(bào)警，文件清單等） 3.容許運(yùn)行一個(gè)程序所需要所有信息的容器 4.UID與GID1.5.3 1.IO設(shè)備的分類： A．塊設(shè)備：硬盤，可隨機(jī)讀取 B．字符特殊文件：鍵盤鼠標(biāo) 2．管道：虛文件，連接進(jìn)程1.6系統(tǒng)調(diào)用 1.用戶程序與操作系統(tǒng)交互：處理抽象 2.能進(jìn)入內(nèi)核的過程調(diào)用 用戶態(tài)切換到核心態(tài)三種方法：中斷，異常，系統(tǒng)調(diào)用 3.TRAP指令：副作用切換到內(nèi)核態(tài)1.7.3微內(nèi)核 1.高可靠性，把操作系統(tǒng)劃分成小的，定義良好的模塊，只有微內(nèi)核運(yùn)行在內(nèi)核，其他 是普通用戶程序 2.設(shè)備驅(qū)動：崩潰不會導(dǎo)致系統(tǒng)死機(jī) 3.機(jī)制與策略分離第二章：進(jìn)程與線程2.1進(jìn)程模型 1.多道程序設(shè)計(jì)：CPU在多個(gè)程序之間快速切換 2.UNIX:開始是相同，之后不同。Windows：一直不同。 3.進(jìn)程退出的原因：1.正常退出；2.出錯(cuò)退出；（異常處理）3.嚴(yán)重錯(cuò)誤；（非法指令，引用錯(cuò)誤內(nèi)存，除零錯(cuò)誤）4.被殺死 4.進(jìn)程層次 Windows:沒有層次的概念，所有進(jìn)程地位相同 Linux：進(jìn)程及進(jìn)程的子女們組成進(jìn)程組 5.進(jìn)程的三種狀態(tài)： 1.運(yùn)行態(tài)（實(shí)際占用CPU） 2.就緒態(tài)（可運(yùn)行） 3.阻塞態(tài)（等待外部事件）6.進(jìn)程表：儲存進(jìn)程狀態(tài)（程序計(jì)數(shù)器，堆棧指針，內(nèi)存分配狀況，打開的文件狀態(tài)。賬號等）7.中斷向量：與每一個(gè)IO類關(guān)聯(lián)1.中斷發(fā)生時(shí)，中斷硬件程序?qū)⑦M(jìn)程表中的重要數(shù)據(jù)壓入堆棧，計(jì)算機(jī)跳到中斷向量的地址2.匯編語言設(shè)置新的堆棧（無法用C語言這類高級語言來描述） 8.多道程序設(shè)計(jì) 1.假設(shè)一個(gè)進(jìn)程等待IO與停留在CPU的時(shí)間比為p，n個(gè)進(jìn)程時(shí)，CPU使用率為 使用率=1–p^n2.2線程（/way_testlife/archive/2011/04/16/2018312.html進(jìn)程與線程） 1.定義：傳統(tǒng)操作系統(tǒng)中，每個(gè)進(jìn)程有一個(gè)地址空間和一個(gè)控制線程 2.線程將應(yīng)用程序分解成可以并行運(yùn)行的多個(gè)順序線程 3.使用多線程的原因： 1.并行實(shí)體共享同一個(gè)地址空間和所有可用數(shù)據(jù)的能力 2.線程更輕量級，所以他們比進(jìn)程更快創(chuàng)建和撤銷3.同時(shí)需要大量IO和CPU計(jì)算時(shí)，多線程允許多個(gè)活動彼此重疊進(jìn)行，從而加快執(zhí)行速度4.多核系統(tǒng)中，多線程可以真正實(shí)現(xiàn)并行 5.例子：多線程/單線程web服務(wù)器1.第三種設(shè)計(jì)（有限狀態(tài)機(jī)：并行，非阻塞系統(tǒng)調(diào)用，【中斷】）：唯一的線程對請求進(jìn)行考察，如果需要IO，則啟動一個(gè)非阻塞IO，服務(wù)器在表格里記錄當(dāng)前請求，然后處理下一個(gè)事項(xiàng)。 6.線程模型 1.進(jìn)程：集中程序運(yùn)行的相關(guān)資源（地址空間，全局變量等） 2.線程：程序計(jì)數(shù)器，寄存器，堆棧，共享的地址空間，多個(gè)線程的執(zhí)行能力。 7.線程之間沒有保護(hù)： 1.不可能 2.不需要（線程之間是合作關(guān)系） 8.每個(gè)線程都有自己的堆棧 9.thread_yield：不同于進(jìn)程，線程無法使用時(shí)鐘中斷強(qiáng)制線程讓出CPU 10.線程引入的問題 1.fork系統(tǒng)調(diào)用是否應(yīng)該復(fù)制子線程 2.共享文件沖突4線程實(shí)現(xiàn) 1.用戶空間實(shí)現(xiàn) 1．每個(gè)進(jìn)程需要有其專門的線程表，由運(yùn)行時(shí)系統(tǒng)管理 2.優(yōu)點(diǎn) 1.可以在不支持線程的操作系統(tǒng)上實(shí)現(xiàn)多線程 2.線程切換速度快（調(diào)用運(yùn)行時(shí)系統(tǒng)的過程，不需要刷新和上下文切換） 3.允許每個(gè)進(jìn)程有自己定制的調(diào)度算法 4.有較好的拓展性（內(nèi)核線程需要固定的表格空間和堆?？臻g） 3.缺點(diǎn) 1.某個(gè)線程進(jìn)行阻塞調(diào)用會引起所有其他線程阻塞 1.使用非阻塞系統(tǒng)調(diào)用 2.阻塞提前通知（select系統(tǒng)調(diào)用） 2.頁面故障阻塞其他線程3.除非線程放棄CPU，否則其他線程（包括調(diào)度線程）無法運(yùn)行（沒有時(shí)鐘中斷） 1.運(yùn)行時(shí)系統(tǒng)也給與時(shí)鐘中斷：不好，不可能而且開銷大 2.內(nèi)核線程 1.內(nèi)核有記錄所有線程的線程表 2.使用環(huán)保方法回收線程 3.在線程級別使用調(diào)度算法：如果線程的操作比較多，會帶來很大的開銷 4.信號：是發(fā)給進(jìn)程的。當(dāng)多個(gè)線程注冊時(shí)，會出問題 3.混合實(shí)現(xiàn)1.使用內(nèi)核級線程，將用戶級線程與某些或全部內(nèi)核線程多路復(fù)用（很靈活）4.調(diào)度機(jī)制 1.內(nèi)核給每個(gè)進(jìn)程安排一定數(shù)量的虛擬處理器并且讓運(yùn)行時(shí)系統(tǒng)分到線程上 2.進(jìn)程被阻塞后，內(nèi)核通知運(yùn)行時(shí)系統(tǒng)（upcall） 3.根據(jù)中斷決定是否繼續(xù) 5.彈出式線程 1.一個(gè)消息的到達(dá)導(dǎo)致系統(tǒng)創(chuàng)造新的線程處理消息-》彈出式線程 2.優(yōu)點(diǎn)：沒有歷史，創(chuàng)建迅速 6.重寫單線程代碼 1.私有的全局變量 2.可重入的庫 1.重寫整個(gè)庫 2.為每個(gè)過程提供wrapper，標(biāo)志該庫正在被使用中 3.信號：內(nèi)核不知道用戶級線程，因此不容易將信號發(fā)給正確的線程 4.堆棧管理：內(nèi)核不了解線程，無法自動增長，可能會造成線程堆棧出錯(cuò)。2.3進(jìn)程間通信 1.三個(gè)基礎(chǔ)問題 1.進(jìn)程如何把信息傳遞給另一個(gè)· 2.確保兩個(gè)或多個(gè)進(jìn)程在關(guān)鍵活動中不會交叉 3.進(jìn)程執(zhí)行的正確順序 2.競爭條件：兩個(gè)或多個(gè)進(jìn)程讀寫共享數(shù)據(jù)，最后結(jié)果取決于進(jìn)程執(zhí)行的精確時(shí)序。 3.臨界區(qū)：多個(gè)進(jìn)程中訪問共享區(qū)域的程序段 1.互斥：不能同時(shí)多個(gè)進(jìn)程使用共享變量或者文件 2.臨界區(qū)解決方案四個(gè)條件 1.任何兩個(gè)進(jìn)程不能同時(shí)處于臨界區(qū) 2.不應(yīng)對CPU的數(shù)量和速度有任何的假設(shè) 3.臨界區(qū)外的程序不應(yīng)阻塞其他程序 4.不能使程序無限期等待進(jìn)入臨界區(qū) 3.解決方案（基于忙等待：進(jìn)程如不能進(jìn)入互斥區(qū)，則會一直原地等待） 缺點(diǎn)：可能導(dǎo)致優(yōu)先級反轉(zhuǎn)問題浪費(fèi)CPU用戶級線程會一直忙等待，從而沒用辦法讓擁有鎖的線程運(yùn)行 1.屏蔽中斷：進(jìn)程進(jìn)入臨界區(qū)之后屏蔽所有中斷（CPU不會切換） 評價(jià)：不好的方案 1.不能把屏蔽中斷的權(quán)力交給用戶進(jìn)程（不打開中斷則系統(tǒng)會終止） 2.多處理器時(shí)不能解決互斥 2.鎖變量：共享鎖，程序在進(jìn)入臨界區(qū)之前檢查鎖的值評價(jià)：無法解決臨界區(qū)問題3.嚴(yán)格輪換法評價(jià)：可以解決，但為忙等待。只有有理由認(rèn)為等待時(shí)間很短的情況下才使用忙等待（鎖被稱為自旋鎖）2．在一個(gè)進(jìn)程比另一個(gè)進(jìn)程慢很多的情況下，不好（違反條件三） 4.Peterson解法 評價(jià)：可以解決，滿足四大條件 5.TSL指令（硬件解法） TSLRXLOCK：測試并加鎖，把LOCK值讀到RX并在LOCK上存入1。原子操作 可以阻止所有處理器訪問LOCK（屏蔽中斷只能屏蔽本地處理器） 4．睡眠——喚醒方案（進(jìn)程無法進(jìn)入臨界區(qū)時(shí)會阻塞）‘ 1.原語：生產(chǎn)者——消費(fèi)者問題：一個(gè)發(fā)給未睡眠進(jìn)程的信號丟失了 2.解決方案1.喚醒等待位：喚醒時(shí)生產(chǎn)者置1，消費(fèi)者睡眠前檢查該位，若為1，則清除該位并繼續(xù)保持清醒（不好，多進(jìn)程時(shí)需多個(gè)等待位）2.信號量（semaphore）：檢查數(shù)值，修改變量等應(yīng)為原子操作1.在進(jìn)入一個(gè)關(guān)鍵代碼段之前，線程必須獲取一個(gè)信號量；一旦該關(guān)鍵代碼段完成了，那么該線程必須釋放信號量。其它想進(jìn)入該關(guān)鍵代碼段的線程必須等待直到第一個(gè)線程釋放信號量。2．實(shí)現(xiàn)方法：操作系統(tǒng)在執(zhí)行以上事務(wù)時(shí)屏蔽中斷3.另一種用途：互斥鎖3.互斥鎖：只需要一個(gè)二進(jìn)制位與忙等待差異：在未獲得鎖時(shí)，調(diào)用另外的線程如何共享鎖？共享數(shù)據(jù)結(jié)構(gòu)可以存放在內(nèi)核并且只能用系統(tǒng)調(diào)用訪問讓進(jìn)程與其他的進(jìn)程共享部分地址空間條件變量允許線程因?yàn)槟承┪催_(dá)到的原因而阻塞允許被阻塞而等待的線程原子性進(jìn)行經(jīng)常與互斥量一起使用：讓一個(gè)線程鎖住一個(gè)互斥量，當(dāng)他不能獲得期待結(jié)果時(shí)等待一個(gè)條件變量。有另外一個(gè)線程發(fā)信號喚醒。條件變量不會存在于內(nèi)存（發(fā)出后丟失）5.管程：一個(gè)數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù) 1.任何一個(gè)時(shí)刻管程里只能有一個(gè)活動的進(jìn)程 2.第二個(gè)進(jìn)程將被掛起直到活躍進(jìn)程離開3.如果一個(gè)條件變量上有若干程序在等待，則執(zhí)行signal操作以后，系統(tǒng)只能從中任選一個(gè)恢復(fù)4.實(shí)現(xiàn)：JAVAsynchronized關(guān)鍵字5.劣勢1．操作系統(tǒng)是C寫的，沒有管程的概念 2.分布式系統(tǒng)無法避免 6．消息傳遞 1.使用系統(tǒng)調(diào)用send和receive 2.潛在問題：消息丟失，消息認(rèn)證，消息傳遞速率低 3.編址方法 1.為每個(gè)進(jìn)程分配一個(gè)唯一的地址 2.引入新的數(shù)據(jù)結(jié)構(gòu)：信箱。消息發(fā)往信箱。（解決消費(fèi)者生產(chǎn)者問題）7.屏障：在每個(gè)階段結(jié)尾安放屏障，當(dāng)一個(gè)進(jìn)程達(dá)到屏障時(shí)，它被屏障阻攔，直到所有進(jìn)程都達(dá)到屏障2．4調(diào)度 1.定義：多個(gè)進(jìn)程就緒是，CPU選擇下一個(gè)將要執(zhí)行的進(jìn)程的方法。2.進(jìn)程行為：IO密集型（web服務(wù)器）和CPU密集型（象棋軟件）。越來越多的軟件傾向于IO密集型，應(yīng)該多運(yùn)行這類進(jìn)程以保持CPU使用率 3.何時(shí)調(diào)度： 1.創(chuàng)建新進(jìn)程時(shí)，應(yīng)該先調(diào)度父進(jìn)程還是子進(jìn)程 2.進(jìn)程退出時(shí) 3.進(jìn)程阻塞時(shí)（IO，信號量等） 4.IO中斷發(fā)生時(shí) 4．調(diào)度算法定義: 1.搶占式：挑選一個(gè)進(jìn)程，并且讓進(jìn)程運(yùn)行某個(gè)固定時(shí)段的最大值，之后掛起 2.非搶占式：挑選一個(gè)進(jìn)程，讓進(jìn)程運(yùn)行直到其阻塞或者自動釋放CPU 5.調(diào)度算法目標(biāo)（所有系統(tǒng)）： 1.公平：每個(gè)進(jìn)程公平的CPU份額 2.策略強(qiáng)制執(zhí)行：所宣布的策略執(zhí)行 3.平衡：系統(tǒng)所有部分都忙碌 6.調(diào)度算法分類： 1．批處理：處理周期性作業(yè)，廣泛的商業(yè)應(yīng)用 1.調(diào)度算法目標(biāo)： 1.吞吐量throughout：系統(tǒng)每小時(shí)完成的作業(yè)數(shù)量2.周轉(zhuǎn)時(shí)間turnaroundtime:從一個(gè)批處理作業(yè)提交時(shí)刻開始直到作業(yè)完成時(shí)刻位置的平均時(shí)間3.CPU利用率 2.具體調(diào)度算法： 1.先來先服務(wù)（first-come） 優(yōu)點(diǎn)：易于理解，便于實(shí)現(xiàn) 缺點(diǎn)：同時(shí)運(yùn)行IO密集型和CPU密集型程序時(shí)效率低下2.最短作業(yè)優(yōu)先（不可搶占） 1.計(jì)算公式：T= 2.只有所有作業(yè)都可同時(shí)運(yùn)行且運(yùn)行時(shí)間可以預(yù)知的情況下 才能使用 3.最短剩余時(shí)間優(yōu)先：最短作業(yè)優(yōu)先的搶占版1.新作業(yè)到達(dá)時(shí)，整個(gè)時(shí)間與當(dāng)前進(jìn)程的時(shí)間做比較，運(yùn)行剩余時(shí)間較少的作業(yè) 2.交互式系統(tǒng) 1.調(diào)度算法目標(biāo)： 1.響應(yīng)時(shí)間：發(fā)出指令到相應(yīng)的時(shí)間 2.均衡性：滿足用戶的期望 2.具體調(diào)度算法 1.輪轉(zhuǎn)調(diào)度：最古老，最簡單，最公平，使用最廣 1．每個(gè)進(jìn)程被分配時(shí)間片，時(shí)間片結(jié)束時(shí)切換進(jìn)程 2.時(shí)間片 1．過長：對短命令的交互請求時(shí)間變長 2.過短：過多進(jìn)程切換，降低CPU效率 2.優(yōu)先級調(diào)度：每個(gè)進(jìn)程賦予優(yōu)先級，優(yōu)先級高的進(jìn)程先執(zhí)行1.使IO進(jìn)程良好運(yùn)行的算法：進(jìn)程優(yōu)先級為1/f，其中f是進(jìn)程在上一時(shí)間片中實(shí)際運(yùn)行的比例（IO進(jìn)程會得到較高優(yōu)先級）2.多優(yōu)先級隊(duì)列：低優(yōu)先級可能出現(xiàn)饑餓現(xiàn)象 3.多級隊(duì)列1.實(shí)現(xiàn)方法：最高優(yōu)先級的進(jìn)程獲得1個(gè)時(shí)間片，之后優(yōu)先級下降并在下次運(yùn)行時(shí)獲得兩倍的時(shí)間片 4.最短進(jìn)程優(yōu)先 1.根據(jù)過去進(jìn)程運(yùn)行時(shí)間預(yù)測并執(zhí)行估計(jì)運(yùn)行時(shí)間2．老化算法：當(dāng)前測量值和先前估計(jì)值進(jìn)行加權(quán)平均（1/2比較好，右移一位即可） 5.保證調(diào)度：每個(gè)進(jìn)程獲得1/n的時(shí)間6．彩票調(diào)度：向進(jìn)程提供各種系統(tǒng)資源的彩票，某些進(jìn)程可以協(xié)作獲得更多彩票。不錯(cuò)的方法7．公平分享調(diào)度：每個(gè)用戶獲得等量的CPU時(shí)間 3.實(shí)時(shí)系統(tǒng) 1.調(diào)度算法目標(biāo)： 1.滿足截止時(shí)間：避免丟失數(shù)據(jù) 2.可預(yù)測性：在多媒體系統(tǒng)中避免品質(zhì)降低 2.分類 硬實(shí)時(shí)：必須滿足絕對的截止時(shí)間 軟實(shí)時(shí)：雖然不希望偶爾錯(cuò)失，但是可以容忍周期性時(shí)間公式M個(gè)周期時(shí)間，事件i以周期Pi發(fā)生，需要用Ci的CPU時(shí)間，那么這個(gè)系統(tǒng)可調(diào)度的條件是 i=1 7.調(diào)度機(jī)制與策略：將調(diào)度機(jī)制與調(diào)度策略分離 例子：系統(tǒng)使用優(yōu)先級調(diào)度，但是把賦予優(yōu)先級的行為委托給進(jìn)程。 8．線程調(diào)度 1.用戶級線程：內(nèi)核不知道線程，用戶進(jìn)程調(diào)用專門定制的線程調(diào)度程序 2.內(nèi)核級線程：時(shí)間片。2.5經(jīng)典IPC(Inter-ProcessCommunication)問題 1.哲學(xué)家進(jìn)餐 1.隨機(jī)事件解法：可能因?yàn)椴豢煽康碾S機(jī)數(shù)字而失敗 2.讀者-寫者問題：不能讓寫者無法寫入數(shù)據(jù)第三章存儲管理3.1無存儲器抽象：程序直接訪問物理內(nèi)存 1.不能在內(nèi)存里【同時(shí)】運(yùn)行多個(gè)程序 2.實(shí)現(xiàn)并行可采用多線程編程：不現(xiàn)實(shí) 3.運(yùn)行多道程序的方法 1.交換：保證一個(gè)時(shí)刻只有一個(gè)程序在內(nèi)存里 2.特殊硬件：防止進(jìn)程相互干擾 缺點(diǎn)：不能直接使用絕對物理地址，裝載器需要一定方法分別地址和常數(shù) 4.一些問題 1.用戶系統(tǒng)如果可以尋址內(nèi)存的每個(gè)字節(jié)，就有可能破壞操作系統(tǒng) 2.多道程序運(yùn)行非常困難3.2地址空間抽象1.概念：一個(gè)進(jìn)程可用于尋址內(nèi)存的一套地址集合，一般獨(dú)立與其他進(jìn)程的地址空間，除某些情況下需要共享2.解決方法 1.動態(tài)重定位：基址寄存器和界限寄存器 缺點(diǎn)：，每次訪問都需要加法和比較運(yùn)算 2.交換技術(shù)：將一個(gè)進(jìn)程完整調(diào)入內(nèi)存，使其運(yùn)行一段時(shí)間后再存回硬盤 1.換入后使用硬件重定位 2．產(chǎn)生空洞，需要內(nèi)存緊縮 3.現(xiàn)代程序需要內(nèi)存較多，但是硬盤速度慢，交換時(shí)間長 4.注意：進(jìn)程大小如果增長，需要輔助手段。解決方案：移入時(shí)分配額外內(nèi)存，再次交換出去時(shí)不交換額外的。 3.空閑內(nèi)存管理 1.位圖存儲：每個(gè)字需要1位位圖 優(yōu)點(diǎn)：空間少 缺點(diǎn)：分配內(nèi)存時(shí)需要在位圖里尋找指定長度的0串，費(fèi)時(shí)。2.鏈表管理：維護(hù)一個(gè)記錄已分配內(nèi)存段和空閑內(nèi)存段的鏈表，每個(gè)鏈表的節(jié)點(diǎn)或包含一個(gè)進(jìn)程，或者兩進(jìn)程之間的空閑區(qū) 優(yōu)點(diǎn)：進(jìn)程終止或者被換出是鏈表的更新非常直接 具體分配方法：首次適配firstfit：沿列表搜索直到找到一個(gè)足夠大的空間下次適配nextfit：首次適配之后，從上次結(jié)束的地方開始搜索。（性能略低于首次適配）最佳適配bestfit：搜索整個(gè)鏈表，找出能容納進(jìn)程的最小空閑區(qū)。（速度較慢，會產(chǎn)生大量無用的小空閑區(qū)）最差適配worstfit：分配最大的空閑區(qū)（也不好）為進(jìn)程和空閑區(qū)保存單獨(dú)鏈表優(yōu)點(diǎn)：提高分配算法速度缺點(diǎn)：增加內(nèi)存復(fù)雜度和內(nèi)存釋放速度變慢快速適配quickfit：為常用大小的空閑去維護(hù)單獨(dú)的鏈表3.3虛擬內(nèi)存1.基本思想：每個(gè)程序擁有自己的地址空間，這個(gè)空間被分割成許多塊，每一塊稱作一頁page，page被映射到物理內(nèi)存，但是只有某些頁真正在內(nèi)存中。操作系統(tǒng)調(diào)用不存在頁面的時(shí)候，引發(fā)缺頁中斷2.分頁技術(shù)1.有程序產(chǎn)生的地址被稱為虛擬地址，它們被稱為虛擬地址空間。地址空間里的單元成為頁面，在物理內(nèi)存對應(yīng)的單元稱為頁框pageframe。2.是用虛擬內(nèi)存時(shí)，地址不是送到內(nèi)存總線，而被送到內(nèi)存管理單元(memorymanagementunit,MMU)MMU將虛擬地址映射成物理地址。內(nèi)存對MMU一無所知例子：16位虛擬地址對應(yīng)15位物理地址，輸入的虛擬地址被分為4位頁面和12位偏移量，在頁表中查詢，之后組成15位實(shí)際地址3.頁表 1.本質(zhì)：一個(gè)把虛擬頁面映射成頁框的函數(shù) 2.頁表項(xiàng)的結(jié)構(gòu) 1.頁框號 2.在/不在位 3.保護(hù)位 4.訪問位和修改位 5.禁止高速緩存位：對映射到設(shè)備寄存器的頁面非常重要3.不在內(nèi)存的頁面的硬盤地址不是頁表的一部分：缺頁中斷時(shí)，該頁面的磁盤地址等信息保存在操作系統(tǒng)的內(nèi)部軟件上 4.加速分頁 1.主要問題虛擬地址到物理地址的映射必須非?？烊绻摂M地址很大，頁表也會很大2.極端解決方案 1.頁表全部在寄存器里 優(yōu)點(diǎn)：簡單，映射過程中不需要訪問內(nèi)存缺點(diǎn)：頁表很大時(shí)代價(jià)高昂，每一次上下文切換都必須裝載整個(gè)頁表，性能低 2.頁表全在內(nèi)存里 優(yōu)點(diǎn)：上下文切換快 缺點(diǎn)：每條指令執(zhí)行都需要訪問內(nèi)存 3.現(xiàn)實(shí)解決方法 1.轉(zhuǎn)換檢測緩沖區(qū)translationlookasidebuffer，TLB 1．本質(zhì)：把虛擬地址直接映射成物理地址的小型硬件 2.使用：傳入的虛擬頁號并行匹配 3.未命中：MMU未檢查到有效匹配項(xiàng)，則進(jìn)行頁表查詢，從TLB淘汰一 個(gè)表項(xiàng)，并用新頁表項(xiàng)代替 4.軟失效：頁面不在TLB但是在內(nèi)存：更新TLB，幾納秒 硬失效：頁面不在內(nèi)存：缺頁中斷，磁盤IO，幾毫秒 4.大內(nèi)存頁表 1.多級頁表：32位虛擬地址劃分成頁表1，頁表2，偏移量三部分原因：避免全部頁表一直在內(nèi)存（一般程序只有少量的正文段，數(shù)據(jù)段和堆棧段，中間是大量空洞，訪問空洞時(shí)強(qiáng)制缺頁中斷并發(fā)信號） 2.倒排頁表（invertedpagetable，64位機(jī)器）：每一個(gè)頁框?qū)?yīng)一個(gè)頁面 優(yōu)點(diǎn)：節(jié)省空間缺點(diǎn)：從虛擬地址到物理地址的轉(zhuǎn)換困難（必須搜索整個(gè)表項(xiàng)來尋找（進(jìn)程，虛擬頁面）對）解決方案：建立一張散列表，用虛擬地址來散列，相同hash值的表鏈在一起3.4頁面置換算法：缺頁中斷時(shí)，操作系統(tǒng)必須淘汰一個(gè)舊頁面/web服務(wù)器淘汰一個(gè)高速緩存項(xiàng) 1.最優(yōu)頁面置換算法：用X條指令后才會用到來標(biāo)記頁面，置換X最大的頁面 優(yōu)點(diǎn)：已知最好算法缺點(diǎn)：不可能實(shí)現(xiàn)2.最近未使用頁面置換算法（notresentlyused，NRU）：啟動進(jìn)程時(shí)，系統(tǒng)把頁面的訪問位(R)和修改位(M)置零，R位被定期清零，以區(qū)別最近是否訪問過。頁面分為4類： 1．沒有被訪問和修改 2.沒有被訪問，已修改 3.被訪問，沒有修改 4.訪問修改NRU算法在類標(biāo)號最小的非空集里挑選一個(gè)頁面淘汰 優(yōu)點(diǎn)：簡單易實(shí)現(xiàn) 缺點(diǎn)：性能不是最好的3.先進(jìn)先出頁面置換算法（FIFO）：淘汰最老頁面，可能會淘汰很有用的，不單純使用 4.第二次機(jī)會頁面置換算法（secondchance）：檢查最老頁面的R位，如果是0，置 換之，否則清零并把該頁面放到鏈表尾端。 本質(zhì)：找尋一個(gè)最近的時(shí)鐘間隔以來沒有被訪問過的頁面 5.時(shí)鐘頁面置換算法（clock）：第二次機(jī)會頁面的時(shí)鐘版 6.最近最少使用頁面置換算法(LRU,LeastRecentlyUsed)實(shí)現(xiàn)方法：需要在內(nèi)存里維護(hù)所有頁面的鏈表，最近最多的使用的頁面在表頭，最近最少的頁面在表尾缺點(diǎn)：每次訪問內(nèi)存都必須更新整個(gè)鏈表，費(fèi)時(shí)特殊硬件實(shí)現(xiàn)方法：64位計(jì)數(shù)器C，每個(gè)頁表都有一個(gè)計(jì)數(shù)器，每次執(zhí)行完以后加1，缺頁中斷時(shí)置換計(jì)數(shù)器最小的頁面N*N矩陣。初值為0，訪問頁框k時(shí)，硬件首先把k行的位都設(shè)置成，再把k列的位都設(shè)置成0。任何時(shí)刻二進(jìn)制數(shù)值最小的行對應(yīng)頁面會被置換 7.軟件模擬的LRU1.最不常用算法（NFU）：每個(gè)頁面與軟件計(jì)數(shù)器相連，每次時(shí)鐘中斷是操作系統(tǒng)掃描所有頁面并將R位加到計(jì)數(shù)器上，置換計(jì)數(shù)器值最小的頁面缺點(diǎn)：記憶太久，操作系統(tǒng)可能會置換有用的頁面2.老化算法aging：在R位加入之前，計(jì)數(shù)器右移一位（相當(dāng)于過去訪問次數(shù)*1/2）,然后把R加到計(jì)數(shù)器最左邊。置換計(jì)數(shù)器值最小的頁面。 缺點(diǎn)：不能確定時(shí)鐘滴答中哪個(gè)頁面被先訪問 計(jì)數(shù)器只有有限位數(shù)，限制了其對以往頁面的記錄（實(shí)際中一般夠用） 8.工作集頁面置換算法 1．定義：一個(gè)進(jìn)程當(dāng)前正在使用的頁面的集合稱為工作集 2.分頁系統(tǒng)會設(shè)法跟蹤工作集，在進(jìn)程運(yùn)行之前就預(yù)先調(diào)頁 3．大多數(shù)進(jìn)程不會均勻訪問地址空間，而是一小部分頁面 4.缺頁中斷時(shí)，淘汰不在工作集的頁面。 5.近似：過去的t秒實(shí)際運(yùn)行時(shí)間中進(jìn)程所訪問的頁面的集合 6.算法： 9.工作集時(shí)鐘頁面置換算法：工作集算法的時(shí)鐘版本 10.小結(jié)：最好的算法是老化算法和工作集時(shí)鐘算法3.5分頁系統(tǒng)的設(shè)計(jì)問題 1.局部分配策略與全局分配策略 1．局部算法可以有效地為每個(gè)進(jìn)程分配固定的內(nèi)存片段 例子：工作集,FIFO,LRU 2.全局算法在可運(yùn)行進(jìn)程之間動態(tài)分配頁面，通常工作更好。 例子：FIFO,LRU1.為進(jìn)程分配相等的份額：不好，對大進(jìn)程不公平，應(yīng)該給每個(gè)進(jìn)程分配最小的頁框數(shù)2.PFF：監(jiān)測缺頁率，保證每個(gè)進(jìn)程的PFF在可控范圍內(nèi)。 2.負(fù)載控制：換成進(jìn)程時(shí)考慮其特性（IO密集或者CPU密集） 3.頁面大小 小頁面：更多頁面更大頁表，更多缺頁中斷，內(nèi)部碎片少，分配時(shí)效率高 大頁面：反之 計(jì)算公式：P= 4.分離的指令空間和數(shù)據(jù)空間：獨(dú)立分頁 5.共享頁面 1.共享I空間頁面 2.共享頁面時(shí)，換出進(jìn)程不應(yīng)換出共享頁面：使用專門的數(shù)據(jù)結(jié)構(gòu)記錄共享頁面 3.共享數(shù)據(jù)：寫時(shí)復(fù)制 6.共享庫1.windows：DLL文件，連接器沒有加載函數(shù)，而是一小段可以在運(yùn)行時(shí)綁定函數(shù)的存根里程stubroutine2.優(yōu)點(diǎn)：共享庫中一個(gè)函數(shù)被修正：不需要重新編譯程序3.問題：編譯共享庫時(shí)，不產(chǎn)生使用絕對地址的指令 7.內(nèi)存映射文件：進(jìn)程發(fā)起一個(gè)系統(tǒng)調(diào)用，把一個(gè)文件映射到虛擬地址的一部分。 映射共享頁面時(shí)不會實(shí)際讀入頁面，而在其訪問頁面時(shí)才會每次一頁的讀入。 8.清除策略 1.分頁守護(hù)進(jìn)程：保證有足夠空閑頁框供給 2.實(shí)現(xiàn)方法：雙指針時(shí)鐘，前指針由分頁守護(hù)進(jìn)程控制 9.虛擬內(nèi)存接口：允許程序員控制內(nèi)存映射 1.可以允許兩個(gè)或多個(gè)進(jìn)程共享一部分內(nèi)存 2.實(shí)現(xiàn)高性能的消息傳遞系統(tǒng)：發(fā)送進(jìn)程清除映射，接收進(jìn)程建立映射3.6分頁系統(tǒng)的實(shí)現(xiàn) 1.上下文切換：重置MMU，刷新TLB，裝載頁表 2.缺頁中斷處理 1.陷入內(nèi)核，保存程序計(jì)數(shù)器 2.調(diào)用匯編例程保存其他寄存器 3.操作系統(tǒng)查看寄存器或者分析指令判斷所缺頁面 4.操作系統(tǒng)檢查虛擬地址是否有效，若是則啟動頁面置換算法更換頁面 5.如果頁面被修改過，啟動IO，標(biāo)記該頁面，上下文切換 6.啟動IO裝載缺失頁面 7.頁表更新，恢復(fù)堆棧和寄存器，重啟被中斷進(jìn)程3.指令備份：使用隱藏的內(nèi)部寄存器，在每條指令執(zhí)行之前，把程序計(jì)數(shù)器的內(nèi)容復(fù)制過來4.鎖定內(nèi)存頁面：鎖住正在進(jìn)行IO的頁面或者在內(nèi)核緩沖區(qū)完成所有IO5.后備存儲 1.UNIX：swap交換區(qū)：沒有文件系統(tǒng) 2.進(jìn)程啟動前必須初始化交換區(qū) 3.實(shí)現(xiàn)方法 1.將整個(gè)進(jìn)程復(fù)制到交換區(qū)：進(jìn)程可能增長 2.直到換出時(shí)才分配交換區(qū)：內(nèi)存中每個(gè)頁面都要記錄磁盤地址交換分區(qū)：windows使用大文件空間不足時(shí)拋棄程序正文或者共享庫6.策略與機(jī)制分離：更多的模塊化代碼和更好的適應(yīng)性，更多的陷入內(nèi)核1.三部分：底層MMU處理程序，內(nèi)核的缺頁中斷處理程序，用戶空間的外部頁面調(diào)度程序 2.問題：外部調(diào)度程序無權(quán)訪問頁面的R位和M位 1.把相應(yīng)數(shù)據(jù)映射到或者傳遞給外部調(diào)度程序 2.把頁面置換算法放在內(nèi)核3.7分段：在機(jī)器上提供多個(gè)獨(dú)立的地址空間，長度從0到某個(gè)整數(shù)，可以動態(tài)改變 1.段是邏輯實(shí)體，不會同時(shí)包含不同類型的內(nèi)容，不是定長的 2.1維地址中，修改過程會影響其他無關(guān)地址的起始地址 3.比較 4.純分段的實(shí)現(xiàn)：可能會有碎片，需要內(nèi)存緊縮 5.分頁與分段結(jié)合 1.虛擬地址分為段號和段內(nèi)地址，其中段內(nèi)地址里有頁號和頁內(nèi)偏移量 2.先找段找頁面找虛擬地址 3.實(shí)例：奔騰處理器 1.虛擬內(nèi)存的核心：局部描述符表LDT和全局描述符表GDT 2.利用選擇子可以同時(shí)實(shí)現(xiàn)純分頁/分段和混合模式 3.保護(hù)環(huán)：越級調(diào)用第四章文件系統(tǒng)4.1文件 1.拓展名：UNIX任意，WINDOWS注冊 2.二進(jìn)制文件：魔數(shù)，放在二進(jìn)制文件頭 3.文件存?。喉樞虼嫒。ù艓ВS機(jī)存?。ㄓ脖P，seek） 4.文件操作：open：把文件屬性和磁盤地址裝進(jìn)內(nèi)存，方便后續(xù)的快速調(diào)用（fd）4.2目錄1.軟連接：目錄的datablock加一條記錄，新生成一個(gè)文件（i節(jié)點(diǎn)，datablock里是被鏈接目錄的路徑），可以鏈接目錄，可以跨文件系統(tǒng)（轉(zhuǎn)儲時(shí)需要注意） 2.硬鏈接：目錄的datablock加一條記錄，指向現(xiàn)有文件i節(jié)點(diǎn)。只能鏈接文件，不能跨文件系統(tǒng)4.3文件系統(tǒng)的實(shí)現(xiàn) 1.磁盤0號扇區(qū)：MBR，引導(dǎo)計(jì)算機(jī)啟動·，之后分區(qū)表，之后superblock 2.文件的實(shí)現(xiàn) 1.連續(xù)分配：CD-ROM，DVD 優(yōu)勢：實(shí)現(xiàn)簡單，記錄第一塊的磁盤地址和塊數(shù)即可；讀操作性能好 劣勢：磁盤上會出現(xiàn)大量碎片；創(chuàng)建文件時(shí)必須知道文件大小 2.鏈表分配：每個(gè)塊的第一個(gè)字作為下一塊的指針 優(yōu)勢：沒有內(nèi)部碎片劣勢：隨機(jī)讀取非常慢，必須先讀之前的n-1塊；塊的大小不再是2的整數(shù)次冪，降低系統(tǒng)運(yùn)行效率 3.內(nèi)存中采用表的鏈表分配（FAT，每個(gè)磁盤的指針字放在內(nèi)存里） 優(yōu)勢：加速隨機(jī)存儲 劣勢：必須把整個(gè)表放在內(nèi)存里，對大硬盤不合適 4.i節(jié)點(diǎn)（UNIX）：只有對應(yīng)文件打開的時(shí)候，i節(jié)點(diǎn)才在內(nèi)存中 優(yōu)勢：占用內(nèi)存較少 劣勢：需要磁盤塊個(gè)數(shù)會超過i節(jié)點(diǎn)大小：i節(jié)點(diǎn)可以指向更多的i節(jié)點(diǎn) 3.目錄的實(shí)現(xiàn) 1.UNIX:文件屬性在i節(jié)點(diǎn)里。Windows：文件屬性在目錄里 2.長文件名 1.長度限制：浪費(fèi)大量目錄空間 2.目錄項(xiàng)固定部分：長度，數(shù)據(jù)項(xiàng)等。下一個(gè)進(jìn)來的文件不一定符合空隙 一個(gè)目錄項(xiàng)可能分布在多個(gè)頁面上，讀取時(shí)會有頁面故障目錄項(xiàng)固定長度，文件名在目錄后的堆中優(yōu)點(diǎn)：移走文件后，總有新文件可以加進(jìn)來；文件名不需要從字邊界開始缺點(diǎn)：管理堆+頁面故障仍然存在 3.查找文件名：線性查找或者使用散列表 1.散列表：查找迅速，管理復(fù)雜（可以加入高速緩存） 4.共享文件 5.日志結(jié)構(gòu)文件系統(tǒng)LFS1.基礎(chǔ)思想：將整個(gè)磁盤化成一個(gè)日志，每隔一段時(shí)間，緩存在內(nèi)存中所有未進(jìn)行的寫操作都被放到一個(gè)獨(dú)立的段中，并寫到日志末尾（難以找到I節(jié)點(diǎn)）2．清理線程：定期掃描日志進(jìn)行磁盤壓縮 6.日志文件系統(tǒng)：NTFS，ext3 1.基本思想：保存記錄文件系統(tǒng)下一步要做什么，防止崩潰導(dǎo)致的不一致2.基本實(shí)現(xiàn)：日志文件系統(tǒng)先寫一個(gè)日志，列出要進(jìn)行的動作。然后進(jìn)行操作，成功之后擦出日志。若系統(tǒng)崩潰，日志系統(tǒng)會重新開始行動。3.寫入日志的操作必須是冪等的：只要有必要，可以重復(fù)多次，不會帶來破壞4.原子事務(wù) 7.虛擬文件系統(tǒng)：建立初衷NFS1.基本思想：抽象出所有文件系統(tǒng)都共有的部分，并且將這部分代碼放在單獨(dú)一層，該層調(diào)用底層的實(shí)際文件系統(tǒng)來具體管理數(shù)據(jù)2.裝新文件系統(tǒng)時(shí)，必須向VFS提供需要的函數(shù)地址的列表3.v節(jié)點(diǎn)：VFS在fdt中為調(diào)用進(jìn)程創(chuàng)建一個(gè)入口，并指向一個(gè)新的v節(jié)點(diǎn)。之后VFS返回文件描述符。讀文件時(shí)，VFS讀v節(jié)點(diǎn)，然后功能指針，最后實(shí)際文件系統(tǒng)的入口函數(shù)4.4文件系統(tǒng)的管理和優(yōu)化 1.磁盤空間管理 1.塊大小 大塊：浪費(fèi)大量磁盤空間（低空間利用率） 小塊：多次尋道和旋轉(zhuǎn)延遲，降低性能（低數(shù)據(jù)率） 不存在合理的平衡方案。磁盤空間越來越大，應(yīng)使用大塊 2.記錄空閑塊 1.磁盤塊鏈表，每個(gè)塊含255個(gè)空閑塊塊號和指向下一個(gè)記錄塊的地址 優(yōu)化：記錄連續(xù)空塊 問題：指針塊滿或者空的時(shí)候，小型讀寫操作會引起大量IO 解決：拆分滿了的指針快，保證內(nèi)存里有一個(gè)半滿的指針塊2.位圖：磁盤塊會比較緊密的聚集在一起，可以調(diào)進(jìn)內(nèi)存 3.磁盤配額：配額表 2.文件系統(tǒng)備份 1.問題： 1.備份整個(gè)文件系統(tǒng)還是只備份部分文件 2.增量儲備？ 3.壓縮：單個(gè)壞點(diǎn)可能導(dǎo)致解壓縮失敗 4.活動系統(tǒng)的文件備份 5.其他非技術(shù)性問題 2.方案 1.物理轉(zhuǎn)儲：復(fù)制磁盤塊，萬無一失，簡單快速 1.未使用的磁盤塊無需備份 2.壞塊不應(yīng)轉(zhuǎn)儲 3.不能增量存儲，不能恢復(fù)特定文件 2.邏輯轉(zhuǎn)儲：恢復(fù)一個(gè)或幾個(gè)目錄 1.轉(zhuǎn)儲通向修改過文件或目錄的路徑上的所有目錄 1.為了能把轉(zhuǎn)儲的文件和目錄整體恢復(fù)到新文件系統(tǒng)中 2.可以對單個(gè)文件進(jìn)行增量恢復(fù) 2.算法實(shí)例 第一階段：檢查所有目錄項(xiàng)，標(biāo)記所有的目錄和每一個(gè)修改過的文件第二階段：掃描目錄樹，若某個(gè)目錄里沒有修改過的文件或者目錄，去除它第三階段，轉(zhuǎn)儲所有被標(biāo)記的目錄和文件 3.問題 1.空閑塊列表需要從0開始構(gòu)造 2.UNIX文件包含空洞，不應(yīng)轉(zhuǎn)儲 3.特殊文件不應(yīng)轉(zhuǎn)儲 3.文件系統(tǒng)一致性 1.塊的一致性1.方法：構(gòu)造兩張表，計(jì)數(shù)器都初始化為0，第一個(gè)表的計(jì)數(shù)器跟蹤該塊在文件中的出現(xiàn)次數(shù)，第二個(gè)跟蹤該塊在空閑表的出現(xiàn)個(gè)數(shù)。若一致，則對任意一塊，其必只在一張表里的計(jì)數(shù)為1，一張為02.不一致的解決方法 1.都是0：加回空閑表 2.空閑表出現(xiàn)多次：重新建立空閑表 3.文件中出現(xiàn)多次：分配一空閑塊，復(fù)制該塊內(nèi)容，將其插入到文件中 2.文件的一致性1.方法：構(gòu)造一張表，計(jì)數(shù)器都初始化為0，計(jì)數(shù)器跟蹤該文件在目錄中的出現(xiàn)次數(shù)，對比其i節(jié)點(diǎn)個(gè)數(shù)。若文件系統(tǒng)一致，則統(tǒng)計(jì)數(shù)據(jù)也應(yīng)一致2.不一致的解決方法：把i節(jié)點(diǎn)連接計(jì)數(shù)設(shè)置正確 4.文件系統(tǒng)的性能 1.高速緩存：減少磁盤訪問速度 1.常用管理算法：檢查全部讀請求，查看是否有相應(yīng)塊在高速緩存里 2.散列：加快尋找3.與分頁相比，訪問不頻繁，所以可以精確實(shí)現(xiàn)LRU（可能導(dǎo)致關(guān)鍵塊沒有被及時(shí)寫回磁盤）4.Windows：高速緩存被修改的塊被立即寫回內(nèi)存（通寫高速緩存）5.UNIX：每30s寫回一次 2.塊提前讀：需要用到之前提前寫進(jìn)高速緩存，提高命中率 1.只適用于順序存儲文件（可以跟蹤文件行為判定） 3.減少磁盤臂運(yùn)動1.塊簇技術(shù)：用連續(xù)塊簇做分配單位，但讀取和高速緩存時(shí)仍使用塊，尋道次數(shù)減半2.在磁盤中間儲存i節(jié)點(diǎn)：平均尋道時(shí)間減半（沒看懂point在哪里。。。。） 5.磁盤碎片整理 1.windows：把文件碎片整合，放在一個(gè)連續(xù)的空間以提高讀取效率。 2.linux：不需要4.5文件系統(tǒng)實(shí)例 1.CD-ROM：不需要記錄空閑塊，不能刪除1.ISO9660：16塊前導(dǎo)，可放引導(dǎo)信息等。第17塊存放基本卷描述符，不能使用大寫字母，數(shù)字等2.RockRidge拓展(UNIX)：NM拓展，允許無限長名字，權(quán)限拓展域等3.Joliet拓展(Windows)：長文件名等 2.MS-DOS文件系統(tǒng)：FAT 1.后面的數(shù)字代表磁盤地址位數(shù)（簇大小） 3.UNIXV7:1.UNIX的i節(jié)點(diǎn)含文件大小，三個(gè)時(shí)間，所有者，所在組，保護(hù)信息，計(jì)數(shù)等信息2.大文件使用多個(gè)連接塊第五章：輸入/輸出5.1I/O硬件原理 1.IO設(shè)備 1.塊設(shè)備：傳輸一塊為單位，每個(gè)塊可獨(dú)立讀寫，可尋址 2.字符設(shè)備：以字符為單位，不可尋址 2.設(shè)備控制器 1.低層次接口，控制設(shè)備 3.內(nèi)存映射IO 1.IO端口，形成IO空間，操作系統(tǒng)使用特殊指令訪問 優(yōu)缺點(diǎn)把下面反過來2.把所有控制寄存器映射到內(nèi)存空間，每一個(gè)寄存器有唯一內(nèi)存地址，并且保證不會有內(nèi)存被分配 優(yōu)點(diǎn)：不需要特殊的IO指令來讀寫設(shè)備寄存器（C/C++沒有實(shí)現(xiàn)IN或OUT的指令）不需要特殊的保護(hù)機(jī)制阻止用戶進(jìn)程執(zhí)行IO（只需要操作系統(tǒng)不把映射的地址空間交給用戶）可以引用內(nèi)存空間的每一條指令都可以用在控制寄存器（TEST等）缺點(diǎn)：硬件必須針對某個(gè)頁面具有選擇性禁用高速緩存的能力所有內(nèi)存和IO都必須檢測所有的引用 對于單獨(dú)內(nèi)存總線的解決方法：全部引用發(fā)到內(nèi)存，響應(yīng)失敗再給IO內(nèi)存總線放置探查設(shè)備，放過潛在指向所關(guān)注IO設(shè)備的地質(zhì)在PCI橋芯片中過濾地址（pentium的設(shè)計(jì)）3.工作原理：CPU把地址放置在總線上，由內(nèi)存或者IO設(shè)備來響應(yīng) 4.直接存儲器存取DMA：獨(dú)立于CPU訪問系統(tǒng)總線 1.結(jié)構(gòu)：一個(gè)內(nèi)存地址寄存器，一個(gè)字節(jié)計(jì)數(shù)寄存器，多個(gè)控制寄存器2.沒有DMA時(shí)的運(yùn)作：控制器從磁盤把數(shù)據(jù)讀入內(nèi)部緩沖區(qū)，計(jì)算校驗(yàn)和，之后給操作系統(tǒng)中斷，讓操作系統(tǒng)把數(shù)據(jù)讀入內(nèi)存 1.內(nèi)部緩沖使校驗(yàn)錯(cuò)誤更早被發(fā)現(xiàn)2.一旦硬盤開始工作，讀入的數(shù)據(jù)是固定速率。塊被放入內(nèi)部緩沖區(qū)時(shí)，DMA啟動之前不需要訪問主線，簡化控制器設(shè)計(jì) 3.DMA運(yùn)作 1.CPU對DMA控制器進(jìn)行編程 2.DMA在總線上向磁盤發(fā)起讀請求 3.磁盤控制器把數(shù)據(jù)寫到內(nèi)存 4.磁盤控制器發(fā)控制信號給DMA控制器，DMA決定是否繼續(xù)讀 5.讀結(jié)束，DMA發(fā)中斷給CPU，CPU從內(nèi)存讀數(shù)據(jù) 4.DMA可以一次處理多路信號 5.周期竊?。篋MA從CPU處偷走一個(gè)總線周期以讀取一個(gè)字 6.突發(fā)模式：DMA發(fā)起一連串傳送，阻塞CPU和其他設(shè)備優(yōu)點(diǎn)：效率高缺點(diǎn)：可能阻塞很久 7.DMA可以把數(shù)據(jù)復(fù)制到自己的緩沖區(qū)，再復(fù)制到內(nèi)存 優(yōu)點(diǎn)：更加靈活，可以實(shí)現(xiàn)內(nèi)存到內(nèi)存 缺點(diǎn)：需要兩個(gè)總線周期 8.弊端：DMA比CPU慢，可能降低效率 5.中斷1.中斷控制器置起信號，并在地址線上放置數(shù)字（指向中斷向量），之后重開中斷控制器并保存程序計(jì)數(shù)器和其他寄存器 1.保存在內(nèi)部寄存器：中斷控制器之后無法獲得應(yīng)答，直到所有信息被讀出 可能丟失中斷或數(shù)據(jù) 2.保存在堆棧（大部分的做法） 1.用戶堆棧：堆棧指針不合法，缺頁錯(cuò)誤等（此時(shí)無法進(jìn)行缺頁中斷） 2.系統(tǒng)堆棧：涉及到MMU,TLB等，浪費(fèi)時(shí)間 2.中斷向量：新的中斷表格的索引，開始中斷服務(wù)例程 3.精確中斷與不精確中斷 1.原因：現(xiàn)代CPU的流水線和并行 2.精確中斷：中斷時(shí)將機(jī)器留在一個(gè)明確狀態(tài) 1.程序計(jì)數(shù)器保存在已知位置 2.之前的所有指令都執(zhí)行完畢，之后的指令都沒有開始 3.PC所指向的指令狀態(tài)已知3.不能滿足要求的是不精確中斷：需要記錄大量內(nèi)部狀態(tài)，中斷響應(yīng)和恢復(fù)很慢4.解決方法 1.某些類型的中斷是精確的，或者用戶可以強(qiáng)制精確 缺點(diǎn)：日志，影子副本等操作降低性能 2.使用精確中斷：犧牲芯片性能5.2IO軟件性能 1.IO軟件目標(biāo) 1.設(shè)備獨(dú)立性：命令執(zhí)行不需要指定設(shè)備 2.統(tǒng)一命名：所有文件都是用路徑名尋址 3.錯(cuò)誤處理：盡可能在硬件層面解決 4.同步阻塞驅(qū)動與異步中斷驅(qū)動：操作系統(tǒng)掛起IO程序使物理異步IO變成同步 5.緩沖：大量復(fù)制，影響性能 6.共享設(shè)備與獨(dú)立設(shè)備：死鎖 2.程序控制IO：操作系統(tǒng)輪詢IO設(shè)備，忙等待（嵌入式系統(tǒng)中較好） 優(yōu)點(diǎn)：簡單 缺點(diǎn)：低效 3.中斷驅(qū)動IO：等待IO設(shè)備時(shí)調(diào)用其他例程 缺點(diǎn)：中斷發(fā)生在每個(gè)IO操作上，浪費(fèi)CPU時(shí)間 4.DMA的IO 優(yōu)點(diǎn)：中斷只發(fā)生在每次緩沖區(qū)操作 缺點(diǎn)：DMA慢于CPU，可能降低效率5.3IO軟件的層次 1.中斷處理程序 1.應(yīng)該被深隱藏：將啟動一個(gè)IO操作的驅(qū)動程序阻塞，直到IO完成且產(chǎn)生中斷 手段有：信號量上執(zhí)行down，條件變量wait，信息上receive 2.具體執(zhí)行：需要設(shè)置頁表，MMU，TLB等 2.設(shè)備驅(qū)動程序：每個(gè)連接到計(jì)算機(jī)的IO設(shè)備都需要特定代碼來驅(qū)動1.通常必須是操作系統(tǒng)內(nèi)核的一部分。（也可以不是：隔離內(nèi)核與操作系統(tǒng)使內(nèi)核不受干擾） 2.大多數(shù)操作系統(tǒng)都定義了一個(gè)所有設(shè)備都必須支持的標(biāo)準(zhǔn)接口3.功能：初始化，電源管理，接受上方與設(shè)備無關(guān)的軟件發(fā)出的抽象讀寫請求并執(zhí)行之4.具體實(shí)現(xiàn) 1.啟動時(shí)檢查輸入?yún)?shù) 2.檢查設(shè)備是否在用 3.將命令寫到控制寄存器 4.命令發(fā)出后 1．驅(qū)動程序阻塞自身之后中斷到來解除阻塞 2、無延遲，不需要阻塞 5.操作完成后檢查錯(cuò)誤5.驅(qū)動程序必須是可重入的6.熱插拔：內(nèi)核重新分配資源，撤除舊資源，適當(dāng)位置填入新資源 3.與設(shè)備無關(guān)的IO軟件 1.設(shè)備驅(qū)動程序的統(tǒng)一接口：是所有IO和驅(qū)動設(shè)備看起來或多或少是相同的1.實(shí)現(xiàn)：對于每一種設(shè)備，操作系統(tǒng)定義一組驅(qū)動程序必須支持的函數(shù)。通過表格調(diào)用這些函數(shù) 2.設(shè)備保護(hù) 2.緩沖 1.在用戶空間里設(shè)置一個(gè)緩沖區(qū) 優(yōu)點(diǎn)：效率高 缺點(diǎn)：緩沖區(qū)可能被調(diào)出分頁；如果釘住，可用頁面池會減小 2.在內(nèi)核空間和用戶空間里都設(shè)置一個(gè)緩沖區(qū) 內(nèi)核緩沖區(qū)填滿的的時(shí)候，將包含用戶緩沖區(qū)的頁面調(diào)入內(nèi)存 優(yōu)點(diǎn)：效率更高 缺點(diǎn)：調(diào)入內(nèi)存時(shí)無法緩沖數(shù)據(jù) 3.在用戶空間設(shè)置兩個(gè)緩沖區(qū)：解決所有問題 4.循環(huán)緩沖區(qū) 5.缺點(diǎn)：多次復(fù)制會降低效率 3.錯(cuò)誤報(bào)告：許多錯(cuò)誤是設(shè)備特定的并且必須由適當(dāng)?shù)尿?qū)動程序來處理 1.編程錯(cuò)誤：返回錯(cuò)誤代碼給調(diào)用者 2.實(shí)際IO錯(cuò)誤：由驅(qū)動程序決定做什么 4.分配與釋放專有設(shè)備：某些設(shè)備在任意給定的時(shí)刻只能由一個(gè)進(jìn)程使用1.要求進(jìn)程在代表設(shè)備的特殊文件直接執(zhí)行open操作：如果不可用，open會失敗2.更復(fù)雜的方法：對請求和釋放特殊設(shè)備有特殊的機(jī)制：試圖得到不可用的設(shè)備可以將將被阻塞并放到一個(gè)特殊隊(duì)列里 5.與設(shè)備無關(guān)的塊大?。簯?yīng)該由與設(shè)備無關(guān)的軟件隱藏并提供同一塊大小 4.用戶空間的IO軟件：某些獨(dú)立于內(nèi)核的程序 1.系統(tǒng)調(diào)用通常是由庫過程實(shí)現(xiàn) 2.假脫機(jī)：多道程序處理獨(dú)占IO設(shè)備的方法守護(hù)進(jìn)程與假脫機(jī)目錄：進(jìn)程打印文件時(shí)，首先要生成整個(gè)文件，并將其放在假脫機(jī)目錄下，最后由守護(hù)進(jìn)程打印5.4盤 1.盤的硬件 1.磁盤：IDE與SATA 1.重疊尋道：控制器能否同時(shí)控制兩個(gè)或多個(gè)驅(qū)動器尋道 2.隱藏細(xì)節(jié)：軟件工作時(shí)仿佛存在x柱面，y磁頭和z扇區(qū)，由控制器將請求 實(shí)際硬件 3.邏輯塊尋址：磁盤扇區(qū)從0開始編號，不管磁盤的幾何規(guī)格 2.RAID：獨(dú)立磁盤冗余陣列1．基本思想：將一個(gè)裝滿了磁盤的盒子安裝到計(jì)算機(jī)，用RAID控制器替換磁盤控制卡，將數(shù)據(jù)復(fù)制到整個(gè)RAID上以獲得更好的性能和可靠性（并行操作）2.0級RAID：將連續(xù)的條帶以輪轉(zhuǎn)方式寫到全部驅(qū)動器上RAID控制器會把命令解析成單獨(dú)的命令，以正確的順序?qū)⒚顚?yīng)四塊磁盤中的一塊且并行操作，最后在內(nèi)存里正確裝配數(shù)據(jù) 優(yōu)點(diǎn)：性能杰出，簡單明了 缺點(diǎn)：1.對于每次請求一個(gè)扇區(qū)的操作系統(tǒng)，效率低 2.可靠性比單塊硬盤差 3.1級RAID：同0級原理一樣，但是復(fù)制所有磁盤 優(yōu)點(diǎn)：讀性能高了一倍；出色的容錯(cuò)性和恢復(fù)速度 缺點(diǎn)：寫操作性能下降 4.2級RAID：以字節(jié)為單位 優(yōu)點(diǎn)：巨大的數(shù)據(jù)率 缺點(diǎn)：所有控制器旋轉(zhuǎn)同步，單位時(shí)間內(nèi)校驗(yàn)漢明碼等5.3級RAID：2級RAID的簡化版，使用奇偶檢驗(yàn)驅(qū)動器為每個(gè)數(shù)據(jù)字建立奇偶檢驗(yàn) 優(yōu)點(diǎn)：巨大的數(shù)據(jù)率，奇偶校驗(yàn)碼可以用來改正錯(cuò)誤 缺點(diǎn)：所有控制器旋轉(zhuǎn)同步6.4級RAID：使用條帶，用獨(dú)立的奇偶校驗(yàn)驅(qū)動器 優(yōu)點(diǎn)：損失的保護(hù)：崩潰的驅(qū)動器數(shù)據(jù)可以通過異或回復(fù) 缺點(diǎn)：1.對于微小更新性能較差：必須讀取舊數(shù)據(jù)并計(jì)算更新校驗(yàn)值 2.奇偶驅(qū)動器負(fù)擔(dān)沉重7.5級RAID：將奇偶檢驗(yàn)條帶分散到每一個(gè)驅(qū)動器 優(yōu)點(diǎn)：降低奇偶驅(qū)動器負(fù)擔(dān) 缺點(diǎn)：回復(fù)崩潰驅(qū)動器非常復(fù)雜 3.CD-ROM：更高的記錄密度 1.使用凹陷/凸起的過渡來記錄1，平緩記錄0。數(shù)據(jù)寫在連續(xù)螺旋里2.黃皮書：CD-ROM的標(biāo)準(zhǔn) 主要是數(shù)據(jù)格式化與糾錯(cuò)能力3.尋道：CD-ROM的尋道非常困難：軟件計(jì)算一個(gè)近似位置，激光頭在四周尋找前導(dǎo)區(qū)4.綠皮書：補(bǔ)充了圖形以及在相同扇區(qū)保存交錯(cuò)音頻視頻和數(shù)據(jù)的能力 對多媒體CD-ROM非常重要 4.CD-R：可刻錄CD 1.激光光束遇到染料時(shí)破壞其化學(xué)鍵 2.橘皮書：允許CD-R逐漸增長式寫入 3.防止盜版復(fù)制 1.將CD-R上所有文件的長度記錄為幾G字節(jié) 2.在挑選出來的扇區(qū)故意使用錯(cuò)誤的ECC，期望CD復(fù)制程序會改正錯(cuò)誤 3.使用非標(biāo)準(zhǔn)間隙 5.CD-RW：可重寫CD：三種激光使合金處于三種形態(tài) 6.DVD：數(shù)字通用光盤 1.與CD的差別：容量提高7倍 1.更小的凹痕 2.更密的螺旋 3.紅色激光（需要第二個(gè)激光器才能同時(shí)讀取CD和DVD） 2.下一代DVD：HDDVDVsBlu-rayDVD（藍(lán)光DVD獲勝，2009） 2.磁盤格式化 1.硬盤由一疊鋁，合金或者玻璃組成 2.低級格式化 1.扇區(qū)由前導(dǎo)碼，數(shù)據(jù)和ECC組成 2.前導(dǎo)碼 1.以一定的位模式開始 2.包含柱面，扇區(qū)號和其他信息 3.柱面斜進(jìn)cylinderskew：改善性能，一次讀取多個(gè)磁道 取決于驅(qū)動器的幾何規(guī)模 4.結(jié)果：磁盤容量減小，取決于前導(dǎo)碼，扇區(qū)間隙，ECC大小和備用扇區(qū)數(shù)量 5.單交錯(cuò)：為了給控制器時(shí)間以便完成校驗(yàn)及將數(shù)據(jù)從緩沖區(qū)復(fù)制到內(nèi)存 5.雙交錯(cuò)：單交錯(cuò)的進(jìn)化3.高級格式化：對分區(qū)執(zhí)行，設(shè)置一個(gè)前導(dǎo)塊，空閑存儲管理，根目錄和空文件系統(tǒng)。還要將一個(gè)代碼放置在分區(qū)表項(xiàng)以指示文件系統(tǒng)。 3.磁盤臂調(diào)度算法：默認(rèn)實(shí)際硬盤的虛擬幾何規(guī)格和實(shí)際相同 1.讀寫時(shí)間影響因素 1.尋道時(shí)間（主導(dǎo)地位） 2.旋轉(zhuǎn)延遲 3.實(shí)際數(shù)據(jù)傳輸時(shí)間 2.尋道時(shí)間優(yōu)化算法 1.最短尋道優(yōu)先SSF：處理與磁頭最近的請求 優(yōu)點(diǎn)：效率高 缺點(diǎn)：兩邊的區(qū)域請求得到的服務(wù)較差，不公平 2.電梯算法：磁盤臂向一個(gè)方向移動并處理沿途請求，到達(dá)盡頭后轉(zhuǎn)向 優(yōu)點(diǎn)：公平，且對于任意一組請求，移動長度的上界都是柱面數(shù)的兩倍3.電梯算法改：處理完最高編號的請求后磁盤臂移動到最低編號的請求并繼續(xù)向上4.如果軟件可以檢查磁頭下方的扇區(qū)號：驅(qū)動程序發(fā)出請求讀寫下一次要通過磁頭的扇區(qū) 3.旋轉(zhuǎn)時(shí)間優(yōu)化算法：未完成的請求用扇區(qū)號排序4.多驅(qū)動器優(yōu)化算法：為每個(gè)驅(qū)動器維護(hù)一個(gè)請求表，空閑下來的驅(qū)動器立刻發(fā)尋道請求，當(dāng)傳輸結(jié)束時(shí)檢查是否有驅(qū)動器在正確柱面上 1.在：開始讀寫 2.不在：發(fā)出新的尋道命令 4.整體優(yōu)化：一次讀出多個(gè)扇區(qū)并緩存 硬盤緩沖區(qū)：獨(dú)立于操作系統(tǒng)，通常保存沒有實(shí)際請求的塊 4.錯(cuò)誤處理 1.壞塊處理 1.控制器處理 1.壞塊映射到新塊 2.壞塊映射到下一塊，所有之后的數(shù)據(jù)塊向后順移 優(yōu)點(diǎn)：一次讀寫可以讀出整個(gè)扇區(qū) 缺點(diǎn)：扇區(qū)包含數(shù)據(jù)時(shí)開銷較大：重寫前導(dǎo)碼和所有數(shù)據(jù) 2.操作系統(tǒng)處理：必須有壞扇區(qū)列表，或者自己測試硬盤 1.創(chuàng)建一個(gè)包含壞扇區(qū)列表的文件 2.對應(yīng)用軟件隱藏壞塊 2.機(jī)械臂故障：驅(qū)動程序發(fā)出重校準(zhǔn)命令，讓磁盤臂向最外面移動 其他：控制器在芯片置起一個(gè)引腳，使自身當(dāng)前動作清除并復(fù)位需要均勻位留時(shí)不能校準(zhǔn)：AV盤，不會重新校準(zhǔn)5.穩(wěn)定存儲器：得到寫命令時(shí)，磁盤要么正確寫數(shù)據(jù)，要么什么都不寫，保持完整 1.模型假設(shè)1.在磁盤寫一個(gè)塊時(shí)，操作要么正確，要么錯(cuò)誤，錯(cuò)誤可以在隨后的讀操作里通過檢查ECC發(fā)現(xiàn)2.一個(gè)被正確寫入的扇區(qū)可能會自發(fā)變壞3.CPU可能出故障，導(dǎo)致寫操作崩潰 2.實(shí)現(xiàn)：使用一對完全相同的硬盤，對應(yīng)的塊一起工作 1.穩(wěn)定寫：先寫在驅(qū)動器1上，然后讀回檢測正確（失敗N次后使用備用塊）。 再在驅(qū)動器2上寫，直到都成功2.穩(wěn)定讀：先在驅(qū)動器1上讀，如果ECC錯(cuò)誤n次，失敗則讀驅(qū)動器23.崩潰恢復(fù)：程序掃描兩個(gè)硬盤對應(yīng)的快 1.ECC都正確，內(nèi)容一樣：什么都不做 2.ECC都正確，內(nèi)容不同：用驅(qū)動器1的覆蓋2的 3.ECC有一個(gè)是錯(cuò)誤的：用正確的塊覆蓋錯(cuò)誤的塊 3.優(yōu)化：在穩(wěn)定寫期間跟蹤被寫的塊 1.用CMOS非易失性存儲器存儲塊號 2.把塊號使用穩(wěn)定寫保存到一個(gè)特殊區(qū)域5.5時(shí)鐘：維護(hù)時(shí)間，并防止進(jìn)程壟斷CPU 1.時(shí)鐘硬件：有晶體振蕩器、計(jì)數(shù)器和存儲寄存器組成 1.操作模式 1.一次完成：將存儲寄存器的值復(fù)制到計(jì)數(shù)器，倒數(shù)到0后發(fā)出中斷 2．方波模式：中斷后存儲寄存器的值自動復(fù)制，循環(huán)進(jìn)行 2.優(yōu)點(diǎn)：軟件控制頻率 3.備用電路防止丟失時(shí)間（UTC協(xié)調(diào)世界時(shí)） 2.時(shí)鐘驅(qū)動程序 1.任務(wù)列表 1.維護(hù)日時(shí)間 1.使用64位計(jì)數(shù)器 2.使用秒維護(hù)的日時(shí)間 3.對時(shí)鐘滴答計(jì)數(shù)，相對于系統(tǒng)開啟時(shí)間，實(shí)際時(shí)間=日時(shí)間+計(jì)數(shù) 2.防止進(jìn)程超時(shí)運(yùn)行：時(shí)鐘將從時(shí)間片數(shù)值遞減，到0后調(diào)度其他進(jìn)程 3.給CPU運(yùn)行時(shí)間記賬 1.進(jìn)程啟動時(shí)，系統(tǒng)啟動另外一個(gè)輔助時(shí)鐘計(jì)時(shí) 2.在全局變量中維護(hù)一個(gè)指針指向當(dāng)前正在運(yùn)行的表項(xiàng)，每一個(gè)時(shí)鐘滴答讓當(dāng)前進(jìn)程表項(xiàng)的計(jì)數(shù)器加1缺點(diǎn)：多次發(fā)生中斷的進(jìn)程盡管工作不多，仍然要付出整個(gè)滴答 4.處理用戶進(jìn)程提出的alarm系統(tǒng)調(diào)用 1.例子：網(wǎng)絡(luò)傳包，特定時(shí)間無ACK則重發(fā) 2.實(shí)現(xiàn) 1.為每個(gè)請求設(shè)置單獨(dú)的時(shí)鐘2.維護(hù)一張表，記錄所有未完成的計(jì)時(shí)器信號時(shí)刻以及下一個(gè)信號的時(shí)刻3.在鏈表里把所有未完成的請求按時(shí)間順序鏈接 5.為系統(tǒng)本身的各個(gè)部分提供監(jiān)視器1.例子：調(diào)用硬盤時(shí)如果硬盤沒有旋轉(zhuǎn)，則開啟電機(jī)并設(shè)置一個(gè)時(shí)間足夠長的監(jiān)視定時(shí)器，以便在速度合適后中斷 6.完成概要剖析，監(jiān)視和信息收集 3.時(shí)鐘軟件：避免時(shí)鐘中斷的開銷1.實(shí)現(xiàn)：內(nèi)核運(yùn)行時(shí)在返回用戶態(tài)之前，它都應(yīng)檢查軟件是否到期。若到期則執(zhí)行被調(diào)度的事件而無需切換內(nèi)核態(tài)，因?yàn)橄到y(tǒng)已在內(nèi)核態(tài)2.使用場合 1.系統(tǒng)調(diào)用 2.TLB未命中 3.頁面故障 4.IO中斷 5.CPU變成空閑5.6用戶界面：鼠標(biāo)、鍵盤和顯示器 1.輸入軟件1.鍵盤：包含一個(gè)微處理器，鍵被按下/釋放時(shí)候發(fā)出中斷并由驅(qū)動程序收集數(shù)據(jù) 1.鍵盤軟件 1.非規(guī)范模式：驅(qū)動程序接受輸入并原封不動地向上層傳遞 2.規(guī)范模式：驅(qū)動程序處理所有行內(nèi)編輯，只把矯正后的行傳給上級 2.回顯：在顯示器上顯示輸入的字符 3.特殊處理：折行，制表符和回車（UNIX），回車換行（Windows） 2.鼠標(biāo) 1.橡皮球鼠標(biāo)：通過橡皮球滾動定位 2.光學(xué)鼠標(biāo) 3.鼠標(biāo)步mickey：最小的移動單位 2.輸出軟件： 1.文本窗口 轉(zhuǎn)義序列：移動光標(biāo)并在光標(biāo)處插入/刪除字符的命令集 2.X窗口系統(tǒng)：非常好的移植性、靈活性和拓展性，運(yùn)行在用戶空間 1.X客戶：運(yùn)行程序，收發(fā)命令 2.X服務(wù)器：收集鍵盤鼠標(biāo)數(shù)據(jù)并將輸出寫在鍵盤上（必須運(yùn)行在本機(jī)） 3.X是一個(gè)窗口系統(tǒng)而不是GUI：編寫窗口需要Xlib 4.窗口管理不是X系統(tǒng)的一部分 5.高度事件驅(qū)動 6.資源：保存一定信息的數(shù)據(jù)結(jié)構(gòu)，可共享，生命周期短。 3.GUI：WIMP窗口、圖表、菜單和指向設(shè)備 1.輸出送往特殊的電路板：圖形適配器2.面向消息：鍵盤或鼠標(biāo)的輸入被系統(tǒng)捕獲并轉(zhuǎn)化成消息，送到正在被訪問的窗口所屬于的程序3.兩種調(diào)用程序的方法 1.發(fā)送消息到窗口 2.投遞消息到消息隊(duì)列4.總結(jié)：windows程序創(chuàng)建窗口，每個(gè)窗口有一個(gè)類對象，與每個(gè)程序相關(guān)聯(lián)的是一個(gè)消息隊(duì)列和一組處理過程，最終程序的行為由到來的事件驅(qū)動 4.位圖 1.windows元文件：聚集一組對GDI過程的調(diào)用，描述一個(gè)復(fù)雜的圖畫 適用于windows程序之間傳輸圖畫DIB：解決位圖不能跨設(shè)備縮放等問題5.字體：TrueType字體1.不是位圖而是輪廓，每個(gè)點(diǎn)都是相當(dāng)于原點(diǎn)，所以容易進(jìn)行縮放：只需要每個(gè)坐標(biāo)乘以比例因子2.柵格化：以任何的期望率把字體轉(zhuǎn)化成位圖5.7瘦客戶機(jī)：高性能的云端運(yùn)算 1.分布式機(jī)器的不便之處 1.必須維護(hù)大容量的硬盤和復(fù)雜的軟件 2.定期備份 3.不容易資源共享 2.基本思想：從客戶端剝離一切智能和軟件，只將其作為顯示器 3.五條命令 1.Copy：顯示器從視頻RAM的一個(gè)部分移動數(shù)據(jù)到另一個(gè)部分 2.sfill：單一像素值填充一個(gè)區(qū)域 3.pfill：復(fù)制一個(gè)模式到某區(qū)域 4.bitmap：由前景色和后景色的區(qū)域5.8電源管理：關(guān)閉不用的組件或者是應(yīng)用程序減少耗能1.硬件問題：將硬件設(shè)置成多種狀態(tài)——工作，睡眠，休眠和關(guān)閉，每一個(gè)狀態(tài)都比前一個(gè)耗能少，但是喚醒時(shí)間和耗能多2.操作系統(tǒng)問題 1.顯示器：背光照明 解決方法：顯示器有若干區(qū)域組成，能夠獨(dú)立開啟關(guān)閉 2.硬盤：維持高速旋轉(zhuǎn) 1.一段時(shí)間不用后關(guān)閉：重新啟動硬盤耗能較多 2.在RAM里維護(hù)大容量的高速緩存 3.操作系統(tǒng)發(fā)送硬盤狀態(tài)消息給程序，使它們自由決定寫操作時(shí)間 3.CPU 1.降低電壓：慢速運(yùn)行更有效率 4.內(nèi)存 1.刷新或者關(guān)閉高速緩存 2.將主存寫進(jìn)磁盤，然后關(guān)閉主存：較長加載時(shí)間 5.無線通信 解決方法：計(jì)算機(jī)關(guān)閉無線設(shè)備時(shí)發(fā)消息給基站，讓基站緩存信息 6.熱量管理：風(fēng)扇 解決方法：操作系統(tǒng)監(jiān)視溫度，達(dá)到閾值后啟動風(fēng)扇7.電池管理 解決方法：操作系統(tǒng)持續(xù)監(jiān)控電池，并改變其工作參數(shù) 8.應(yīng)用程序接口解決方法：Windows使用ACPI高級電源管理接口給驅(qū)動程序發(fā)送命令，減少他們的能耗 3.應(yīng)用程序：退化用戶體驗(yàn) 例子：彩色視頻使用黑白等第六章死鎖6.1資源：需要排他使用的對象 1.分類 1.可搶占資源：可以從擁有它的進(jìn)程中搶占而不會產(chǎn)生任何副作用：存儲器 2.不可搶占資源：不引起計(jì)算錯(cuò)誤的前提下不能搶占它 2.假設(shè)：如果某個(gè)進(jìn)程請求資源，它將休眠3.用戶管理資源的方法：為每個(gè)資源配置一個(gè)信號量：使用down獲取資源，使用資源，用up釋放6.2死鎖概述1.規(guī)范定義：一個(gè)進(jìn)程集合中的每個(gè)進(jìn)程都在等待只能有該進(jìn)程集合中的其他進(jìn)程才能引發(fā)的事件，該進(jìn)程集合就是死鎖的2.資源死鎖：等待的時(shí)間是釋放其他進(jìn)程所占有的資源3.死鎖的四個(gè)必要條件：死鎖時(shí)四個(gè)條件一定滿足 1.互斥條件：每個(gè)資源要么已經(jīng)被分配，要么可用 2.占有和等待條件：已經(jīng)得到資源的進(jìn)程可以再申請其它資源 3.不可搶占條件：已經(jīng)分配的資源只能被顯式釋放而不能被搶占4.環(huán)路等待條件：死鎖發(fā)生時(shí)一定有進(jìn)程環(huán)路出現(xiàn)，其中每個(gè)進(jìn)程都在等待下一個(gè)進(jìn)程所占有的資源 4.死鎖建模：有向圖表示資源被占用/請求資源，環(huán)路表示死鎖 5.處理死鎖的算法 1.鴕鳥算法：忽略死鎖問題 如果解決死鎖的代價(jià)超過了收益，忽略它是明智的選擇 2.死鎖檢測和恢復(fù) 1.每種類型一個(gè)資源的死鎖檢測：只需要一個(gè)有向圖里尋找環(huán)路的算法 2.每種類型多個(gè)資源的死鎖檢測： 1.算法描述尋找一個(gè)沒有標(biāo)記的進(jìn)程P（標(biāo)記后表示能執(zhí)行，不會死鎖），且R矩陣該行的向量小于A：尋找有資源請求且可被當(dāng)前資源滿足的進(jìn)程找到：把C矩陣的i行向量加到A中，標(biāo)記該進(jìn)程，跳到1找不到：結(jié)束沒有標(biāo)記過的進(jìn)程都是死鎖的 2.檢查時(shí)間 1.有資源請求時(shí) 優(yōu)點(diǎn)：發(fā)現(xiàn)早 缺點(diǎn)：占用CPU時(shí)間 2.每隔K分鐘檢查一次 3.當(dāng)CPU使用率低于閾值的時(shí)候檢查：死鎖時(shí)進(jìn)程無法運(yùn)行 3.從死鎖中恢復(fù) 1.搶占恢復(fù)：臨時(shí)轉(zhuǎn)移資源，取決于進(jìn)程的特性2.回滾恢復(fù)：使用檢查點(diǎn)記錄進(jìn)程狀態(tài)，死鎖時(shí)回滾到最近的檢查點(diǎn)，并把資源分配給一個(gè)死鎖進(jìn)程3.殺死進(jìn)程 1.殺死集合中的進(jìn)程，直到死鎖消失 2.殺死集合外的進(jìn)程，把其持有的資源送給死鎖集合 注意：有可能的話最好殺死可以重頭再來并且沒有副作用的進(jìn)程 3.死鎖避免 1.資源軌跡圖 2.安全狀態(tài)與不安全狀態(tài)1.安全：即使所有當(dāng)前進(jìn)程都突然請求最大需求資源，仍然存在某種調(diào)度算法使得每一個(gè)進(jìn)程都能運(yùn)行完畢。2.不安全：不能保證所有的進(jìn)程都能運(yùn)行完，但不是死鎖 3.單個(gè)資源的銀行家算法對每一個(gè)請求進(jìn)行檢查，看滿足它是否會達(dá)到安全狀態(tài)。是，則滿足；不是則推遲滿足這一請求 4.多個(gè)資源的銀行家算法 檢查右邊矩陣中是否有一行，其沒有被滿足的資源數(shù)小于或等于A存在：滿足這一行的請求，標(biāo)記進(jìn)程，資源加到向量A上不存在：要么所有進(jìn)程被標(biāo)記，要么死鎖5.評價(jià)：該算法雖然很有意義但是缺乏使用價(jià)值，因?yàn)楹苌儆羞M(jìn)程在運(yùn)行前就知道所需資源最大值，而且進(jìn)程數(shù)不固定，可用的資源也會變得不可用 4.破壞死鎖的條件 1.破壞互斥條件。如果資源不被一個(gè)進(jìn)程獨(dú)占，則不會死鎖：假脫機(jī) 2.破壞占有和等待條件：禁止已持有資源的進(jìn)程在等待其他進(jìn)程 1.規(guī)定所有進(jìn)程在開始執(zhí)行時(shí)請求所需的全部資源 缺點(diǎn)：1. 很多進(jìn)程只有在運(yùn)行時(shí)才知道需要的資源數(shù)量 2.資源利用率低，請求后的資源可能被閑置 2.請求新資源時(shí)，先釋放老資源，再請求所需的全部資源 3.破壞不可搶占條件：不是所有的資源都能做到虛擬化 4.破壞環(huán)路等待條件1.保證每個(gè)進(jìn)程只能占有一個(gè)資源，請求新資源時(shí)必須釋放舊的（不可接受）2.將所有資源標(biāo)號，進(jìn)程可在任何時(shí)刻提出請求，但是所有請求必須按升序標(biāo)號來/不能請求比當(dāng)前占有資源更低編號的資源，不能改變順序。6.3其他問題 1.兩階段加鎖：第一階段，進(jìn)程對所有記錄加鎖；第二階段，更新記錄并釋放鎖 注意：對于一個(gè)進(jìn)程缺少某個(gè)資源就重置它，是不可接受的 2.通信死鎖： 1.進(jìn)程A向B發(fā)出通信消息，消息丟失，兩方都阻塞。 解決方法：超時(shí)重發(fā)2.路由器互相發(fā)送環(huán)路，沒有可用的緩沖區(qū)：死鎖 3.活鎖：忙等待的死鎖，雖然進(jìn)程在運(yùn)行，但是只能空耗CPU時(shí)間 4.評價(jià)：比起限制所有用戶去使用資源，大多數(shù)人更愿意接受一次偶然的死鎖 5.饑餓：某些調(diào)度算法使優(yōu)先級低的進(jìn)程無法被服務(wù)第七章多媒體操作系統(tǒng) 7.1.多媒體技術(shù)簡介 1.多媒體特點(diǎn) 1.極高的數(shù)據(jù)率：需要進(jìn)行壓縮 2.實(shí)時(shí)回放 2.影響因素 1.顫動jitter：傳輸率的變化，必須精確控制 2.服務(wù)質(zhì)量：平均帶寬，可用峰值帶寬，最大和最小延遲，位丟失概率 保證方法：預(yù)先為每一個(gè)新到的客戶預(yù)留資源（進(jìn)入控制算法）7.2多媒體文件 1.數(shù)字電影：由一個(gè)視頻文件，多個(gè)音頻文件（語言），多個(gè)包含字幕的文本文件 1.DVD：32種語言的字幕 2.文件系統(tǒng)需要跟蹤每個(gè)多媒體文件的多個(gè)子文件 1.用新的數(shù)據(jù)結(jié)構(gòu)列出每個(gè)子文件 2.保持子文件同步的某種辦法 2.視頻編碼 *運(yùn)動平滑性：每秒圖像數(shù)。閃爍：每秒刷新屏幕的次數(shù) 1.模擬視頻1.黑白電視：攝像機(jī)用一個(gè)電子束對圖像進(jìn)行橫向掃描并緩慢向下移動，記錄電子束經(jīng)過處光的強(qiáng)度，掃描終點(diǎn)后電子束折回，稱為一幀（逐行掃描） 1.場：針對每秒25幀會讓人感覺閃動 方法：不是從上到下，而先顯示奇數(shù)幀，再顯示偶數(shù)幀，半幀稱為場 2.每秒50場無閃動：隔行掃描2.彩色視頻：三色光各使用一個(gè)電子束兼容黑白電視：RGB信號線組合成亮度（人類更敏感）和兩個(gè)色度信號2.數(shù)字視頻 1.幀的序列，每一幀由像素組成 2.消除閃爍：使用逐行掃描，每一幀刷新2-3遍 現(xiàn)實(shí)應(yīng)用：幀率為每秒25幀，但是計(jì)算機(jī)把每幀繪制兩次3.音頻編碼：奈奎斯特法則，以2f為頻率采樣7.3視頻壓縮 1.編碼和解碼算法的不對稱性：多媒體文件只需要編碼一次，但需要解碼多次 1.速度和硬件不對稱：可以接受緩慢而昂貴的編碼+快速的解碼 2.不必須是100%可逆：所有多媒體系統(tǒng)都是有損的 2.JPEG標(biāo)準(zhǔn)：靜態(tài)照片編碼方式（對于800*640而言）1.塊預(yù)制：有損。用色度和亮度構(gòu)造矩陣，壓縮色度矩陣（人對色度不敏感），發(fā)圖像分塊（亮度矩陣4800塊，色度矩陣1200塊）2.對所有矩陣使用DCT離散余線變化：有損，超越數(shù)和浮點(diǎn)數(shù)的舍入3.量化：有損。去除不重要的DCT參數(shù)4.將每一塊的左上角原點(diǎn)值以它與前一塊中相應(yīng)元素相插的量減小5.將矩陣元素線性化并對得到的列表進(jìn)行行程長度編碼6.使用huffman編碼對列表中的數(shù)字編碼以進(jìn)行傳輸總結(jié)：解碼時(shí)間與編碼基本等同 3.MEPG標(biāo)準(zhǔn)：動態(tài)圖像編碼 1.空間冗余：每幀使用JPEG編碼 2.時(shí)間冗余：互相連續(xù)的幀幾乎都是相同的 3.MEPG實(shí)現(xiàn) 1.原理：I幀，B幀和P幀2.I幀：使用JPEG編碼的靜態(tài)圖像，全分辨率的亮度和半分辨率的色度，每秒1個(gè)或者兩個(gè)i幀 周期性出現(xiàn)的重要性：觀眾收看是隨機(jī)的，如果所有的幀都依賴第一幀，那么錯(cuò)過第一幀就不能再對視頻解碼任何一幀接受錯(cuò)誤都會導(dǎo)致視頻無法再解碼快進(jìn)或倒帶時(shí)解碼器不得不計(jì)算每一幀3.P幀：基于宏塊思想，對幀間差進(jìn)行編碼。搜索上一幀中的宏塊進(jìn)行編碼 1.宏塊：亮度16*16，色度8*8的矩陣2.MPEG沒有規(guī)定如何搜索，搜索多遠(yuǎn)和計(jì)算匹配好壞實(shí)現(xiàn)方式：在前一幀的當(dāng)前位置及所有在x方向偏移m，y方向偏移n的位置搜索宏塊，計(jì)算最高得分。3.找到宏塊后，針對差值進(jìn)行編碼，再用JPEG編碼 4.B幀：同P幀基本一致，但是同時(shí)基于過去和未來的一幀 5.為了對B幀編碼，必須在內(nèi)存里使用充足的緩沖7.4音頻壓縮 1.波形壓縮：信號通過傅里葉變換成頻率分量，對每一個(gè)振幅用簡短的二進(jìn)制編碼 2.感知編碼：尋找人類聽覺系統(tǒng)的特點(diǎn)。結(jié)果在示波器上不相同，但是聽起來沒有區(qū)別 1.頻段屏蔽：一個(gè)頻段內(nèi)響亮的聲音遮掩另一頻段中柔和的聲音 2.暫時(shí)屏蔽：響亮聲音撤去后，仍有一段時(shí)間耳朵無法接受到柔和聲音 3.原理：人們沒必要對功率在可聽閾值（也就是聽不到）的聲音編碼4.應(yīng)用：MP3編碼，對聲音做傅里葉變換得到頻率，之后傳遞不被屏蔽掉的頻率7.5多媒體進(jìn)程調(diào)度1.調(diào)度同質(zhì)進(jìn)程：服務(wù)器支持固定數(shù)量的電影，所有電影都有相同的幀率，視頻分辨率和其他參數(shù)1.實(shí)現(xiàn)：對每一部電影存在一個(gè)線程，其工作是每次從磁盤中讀取電影的一幀并傳送給用戶。使用輪轉(zhuǎn)調(diào)度并有定時(shí)機(jī)制，確保每一進(jìn)程以恰當(dāng)?shù)念l率運(yùn)行2.主控時(shí)鐘：每秒滴答適當(dāng)?shù)拇螖?shù)，所有進(jìn)程以相同的次序運(yùn)行。評價(jià)：只要進(jìn)程足夠少，所有工作都能在一幀內(nèi)完成。 2.一般實(shí)時(shí)調(diào)度： 1.現(xiàn)實(shí)：用戶數(shù)目和幀大小不斷變化，不同的電影會有不同的分辨率 2.模型：多個(gè)進(jìn)程競爭CPU，每個(gè)進(jìn)程有自己的工作量和最終時(shí)限3.進(jìn)程可以搶占。傳輸緩沖區(qū)在很少的幾個(gè)突發(fā)中被填滿，最終時(shí)限到來之前有完全滿的緩沖區(qū) 4.靜態(tài)算法：預(yù)先分配固定的優(yōu)先級，否則是動態(tài)算法。 3.速率單調(diào)調(diào)度RMS：適用于可搶占的周期性進(jìn)程的經(jīng)典靜態(tài)實(shí)時(shí)調(diào)度算法 1.前提條件 1.每個(gè)周期性進(jìn)程必須在周期內(nèi)完成 2.沒有進(jìn)程依賴于其他進(jìn)程 3.每一次進(jìn)程在突發(fā)中都需要相同的CPU時(shí)間量 4.任何非周期性進(jìn)程都沒有最終開銷 5.進(jìn)程搶占即可發(fā)生而沒有系統(tǒng)開銷（是系統(tǒng)建模更容易）2.實(shí)現(xiàn)：RMS分配進(jìn)程一個(gè)固定的優(yōu)先級，優(yōu)先級等于進(jìn)程觸發(fā)事件的頻率，與進(jìn)程的速率成正比。調(diào)度程序總運(yùn)行優(yōu)先級最高的進(jìn)程，必要時(shí)可以搶占當(dāng)前進(jìn)程3.只能工作在CPU利用率不太高的時(shí)候，最大利用率不少于ln2。3進(jìn)程時(shí)利用率為0.808，保證算法可運(yùn)行 4.最早最終實(shí)現(xiàn)優(yōu)先調(diào)度EDF:動態(tài)算法 1.不要求進(jìn)程是周期的，也不要求相同的CPU突發(fā)時(shí)間。2.實(shí)現(xiàn)：只要一個(gè)進(jìn)程需要CPU時(shí)間，就宣布它的到來和最終時(shí)限。EDF維持一個(gè)按進(jìn)程最終時(shí)限排序的進(jìn)程列表，EDF運(yùn)行第一個(gè)（最終最早時(shí)限）進(jìn)程。新進(jìn)程就緒時(shí)，系統(tǒng)檢查其時(shí)限是否在當(dāng)前進(jìn)程之前，若是則搶占當(dāng)前進(jìn)程。3.平局解決：當(dāng)前進(jìn)程繼續(xù)運(yùn)行，不承擔(dān)切換的代價(jià)4.只要CPU利用率小于100%，對于任意一組進(jìn)程總保證可以工作7.6多