我們從功能、組成、特征、結(jié)構(gòu)4個方面對操作系統(tǒng)進(jìn)行介紹。
1）功能：
從用戶角度講，操作系統(tǒng)是一個管理應(yīng)用程序的控制程序，管理應(yīng)用程序；
從資源管理角度講，操作系統(tǒng)是管理外設(shè)、分配資源，對底層硬件管理服務(wù)的資源管理器。
操作系統(tǒng)把CPU、內(nèi)存、硬盤抽象成進(jìn)程、地址空間、文件來供應(yīng)用程序使用。層次上在硬件和應(yīng)用程序之間。開機啟動的進(jìn)程稱為守護(hù)進(jìn)程，開機不啟動的進(jìn)程需要用戶跟操作系統(tǒng)交互，交互工具為shell，linux、Windows、安卓的界面都屬于shell，而不是內(nèi)核，我們主要研究在shell之下的kernel。
2）組成：
kernel-操作系統(tǒng)內(nèi)部組件，包括：CPU調(diào)度器；物理內(nèi)存管理；虛擬內(nèi)存管理；文件系統(tǒng)管理；中斷處理與設(shè)備驅(qū)動。
3）特征：
OS kernel：并發(fā)；共享（同時訪問、互斥共享）；虛擬（利用多道程序設(shè)計技術(shù)，讓每個用戶都認(rèn)為計算機專門為它服務(wù)）；異步（程序的執(zhí)行是斷斷續(xù)續(xù)的，只要運行環(huán)境相同，不同次執(zhí)行輸出的結(jié)果相同）。
并發(fā)：在一段時間內(nèi)有多個程序運行
并行：在同一個時間點有多個程序執(zhí)行（有多個CPU才能并行）
時鐘信號中斷幫助操作系統(tǒng)完成時間片的分時調(diào)度
4）結(jié)構(gòu)：
單體：由各模塊組成一個整體，模塊之間通過函數(shù)調(diào)用來實現(xiàn)訪問
微內(nèi)核：盡量把內(nèi)核功能移動到用戶空間，內(nèi)核只放中斷處理、消息傳遞，文件系統(tǒng)、內(nèi)存管理、網(wǎng)絡(luò)協(xié)議棧都是放在外圍以進(jìn)程的形式存在，服務(wù)之間不是通過函數(shù)調(diào)用而是通過內(nèi)核的消息傳遞機制實現(xiàn)，是一種松耦合架構(gòu)。通過地址隔離，不同應(yīng)用程序無法惡意破壞對方的地址空間，架構(gòu)有很強的靈活性，但是內(nèi)核消息傳遞犧牲了一部分性能。
外核：內(nèi)核分成兩塊，一塊跟硬件打交道，完成硬件的復(fù)制，另一個libos跟應(yīng)用打交道，每一個libos更一個專門的應(yīng)用打交道，都可以訪問sokernel。
虛擬化：榨取硬件性能的一種方式，使得多操作系統(tǒng)共享硬件資源。圖一傳統(tǒng)架構(gòu)，圖二有VMM的虛擬架構(gòu)，VMM將單獨的機器接口轉(zhuǎn)換成很多的幻象，每個接口（虛擬機）是一個原始計算機系統(tǒng)的有效副本，并完成所有的處理器指令。
操作系統(tǒng)啟動：
DISK：存放OS
BIOS：基本I/O處理系統(tǒng)，POST（加電自檢），尋找顯卡和執(zhí)行BIOS，檢查完畢后，把BootLoader從硬盤放到內(nèi)存中，BootLoader一般放到硬盤第一個區(qū)間。
Bootloader：從硬盤加載OS到內(nèi)存，CPU的控制權(quán)由BootLoader掌控，找到操作系統(tǒng)的起始扇區(qū)和操作系統(tǒng)長度，把操作系統(tǒng)讀到內(nèi)存中，CPU控制權(quán)交給OS。
中斷、異常、系統(tǒng)調(diào)用：
1）特征：
面向外設(shè)使用中斷和I/O來處理，面向應(yīng)用程序使用系統(tǒng)調(diào)用和異常來提供相應(yīng)功能。
系統(tǒng)調(diào)用：應(yīng)用程序主動向OS提出服務(wù)請求。system call
異常：應(yīng)用程序在執(zhí)行過程中產(chǎn)生意想不到的問題，使得操作系統(tǒng)不得不完成相應(yīng)的操作。
中斷：來源于外設(shè)，不同硬件設(shè)備的計時器和網(wǎng)絡(luò)中斷
在計算機運行中，內(nèi)核時被信任的第三方，只有內(nèi)核可以執(zhí)行特權(quán)指令。
2）三者區(qū)別：
產(chǎn)生源頭：中斷：外設(shè)；異常：應(yīng)用程序意想不到的行為；系統(tǒng)調(diào)用：應(yīng)用程序請求操作系統(tǒng)提供服務(wù)。
處理時間：中斷：異步（不知道什么時候產(chǎn)生）；異常：同步；系統(tǒng)調(diào)用：發(fā)出請求式同步，返回結(jié)果是異步或同步。
響應(yīng)：中斷：持續(xù)，對用戶應(yīng)用程序是透明的；異常：殺死或重新執(zhí)行意想不到的程序指令；系統(tǒng)調(diào)用：等待和持續(xù)
處理動作：中斷：（1）硬件：設(shè)置中斷標(biāo)記，將內(nèi)部、外部事件設(shè)置中斷標(biāo)記，中斷號；（2）軟件：保存被打斷執(zhí)行現(xiàn)場，便于恢復(fù)；根據(jù)中斷號處理相應(yīng)的中斷，處理完之后清楚中斷標(biāo)記，會不被打斷程序現(xiàn)場。
異常：異常ID號，殺死程序或服務(wù)彌補工作重新執(zhí)行應(yīng)用程序指令。
系統(tǒng)調(diào)用：程序訪問主要通過高層次的API而不是直接進(jìn)行系統(tǒng)調(diào)用，如Win32 API、POSIX API等，通常情況下，與每個系統(tǒng)調(diào)用相關(guān)的序號，系統(tǒng)調(diào)用接口根據(jù)這些序號來維護(hù)表的索引；系統(tǒng)調(diào)用接口調(diào)用內(nèi)核態(tài)中預(yù)期的系統(tǒng)調(diào)用，并返回系統(tǒng)調(diào)用的狀態(tài)和任何其他的返回值；用戶不需要知道系統(tǒng)調(diào)用是如何實現(xiàn)的，只需要獲取API和了解操作系統(tǒng)將返回什么結(jié)果，操作系統(tǒng)接口的細(xì)節(jié)大部分隱藏在API中，通過運行程序支持的庫來管理（包括編譯器的庫來創(chuàng)建函數(shù)集合），應(yīng)用程序發(fā)生系統(tǒng)調(diào)用的時候會切換到內(nèi)核態(tài)，會有新的堆棧，增加系統(tǒng)開銷，但是安全。
跨越操作系統(tǒng)邊界的開銷：在執(zhí)行時間上的開銷超過程序調(diào)用。
開銷：建立中斷/異常/系統(tǒng)調(diào)用號與對應(yīng)服務(wù)例程映射關(guān)系的初始化開銷；建立內(nèi)核堆棧；驗證參數(shù)；內(nèi)核態(tài)映射到用戶態(tài)地址空間更新頁面映射權(quán)限；內(nèi)核獨立地址空間，TLB。
在操作系統(tǒng)中管理內(nèi)存的不同辦法：程序重定位、分段、分頁、虛擬內(nèi)存、按需分頁虛擬內(nèi)存等，內(nèi)存管理實現(xiàn)高度依賴于硬件，即操作系統(tǒng)必須知道內(nèi)存架構(gòu)，通過MMU處理CPU的內(nèi)存訪問請求。
地址空間：分為物理地址空間、邏輯地址空間（運行的程序看到的空間），CPU通過MMU實現(xiàn)邏輯地址到物理地址的映射。
地址轉(zhuǎn)換大致過程：程序的變量是一種符號表示的內(nèi)存地址，通過編譯器變成邏輯內(nèi)存地址，再通過CPU的MMU單元映射到物理內(nèi)存地址。操作系統(tǒng)設(shè)置邏輯地址空間的基址和界限，對程序進(jìn)行地址安全檢查，保證程序內(nèi)存訪問安全。
內(nèi)存分配：1）連續(xù)地址分配；2）非連續(xù)地址分配
1）連續(xù)地址分配：首次適配，最優(yōu)適配，最差適配
該方法會產(chǎn)生外部碎片，針對于外部碎片主要有壓縮式內(nèi)存碎片管理和交換式碎片管理兩種優(yōu)化方法。
2）非連續(xù)地址分配：解決連續(xù)內(nèi)存分配外碎片問題，主要有分段式、分頁式、段頁式內(nèi)存分配方法
分段：把主程序、子程序、共享程序、棧、堆等根據(jù)應(yīng)用程序運行特點不同，從堆、運行棧、程序數(shù)據(jù)、庫、用戶代碼等不同層面把程序劃分成不同的段，操作系統(tǒng)建設(shè)和維護(hù)包含起始地址和長度的段表，通過在邏輯地址中設(shè)置段號和段內(nèi)位移，之后通過MMU映射到物理內(nèi)存空間。
分頁：分頁需要操作系統(tǒng)初始化時建立和維護(hù)頁表，頁表中存儲頁號和頁內(nèi)偏移，把邏輯地址和物理地址都劃分成大小固定且相等的頁，頁幀是物理頁，頁幀由頁幀號和頁幀偏移組成，page是邏輯頁，由頁號和頁內(nèi)偏移組成，把程序分成頁，CPU通過查找pagetable頁號獲取幀號，邏輯頁內(nèi)偏移和物理頁內(nèi)偏移相同，幀號加頁內(nèi)偏移獲得物理地址。
頁表page-table：每個程序有一個頁表來實現(xiàn)邏輯地址到物理地址的映射，如果頁表很大，那么其不適合放到CPU中，放到內(nèi)存中也會開銷很大。目前使用兩種方法，來緩解頁表很大造成的開銷：1）TLB：內(nèi)存管理單元MMU中有TLB緩存，TLB使用關(guān)聯(lián)內(nèi)存實現(xiàn)，具備快速訪問性能，如果TLB命中，物理頁號快速獲取，如果沒有，對應(yīng)表項更新到TLB中。2）多級頁表：把page-num分成兩塊，先查找一級頁表獲取二級頁表起始地址，找到二級頁表項獲取對應(yīng)幀號frame-num，映射到最終物理地址。通過這種方式，使不存在物理邏輯映射關(guān)系的pagetable不需要放到內(nèi)存中。多級頁表也是類似實現(xiàn)原理。
段頁式：結(jié)合分段和分頁，先把程序以分段的形式來進(jìn)行劃分，再在分段基礎(chǔ)上就不同段進(jìn)行分頁劃分，完成邏輯地址到物理地址的映射。
1）覆蓋技術(shù)：把程序按照自身的邏輯結(jié)構(gòu)，劃分為若干個功能相對獨立的程序模塊，不會同時執(zhí)行的模塊共享同一塊內(nèi)存區(qū)域，按照時間先后順序來運行。用分時的方式來共享某一塊內(nèi)存空間，需要常駐內(nèi)存的功能模塊進(jìn)行管理和調(diào)度。覆蓋在如何劃分覆蓋關(guān)系、換入換出的時間開銷都比較大。
2）交換技術(shù)：將暫時不能 運行的程序放到外存，從而獲得空閑內(nèi)存空間。操作系統(tǒng)把一個進(jìn)程的整個地址空間的內(nèi)容保存到外存中（換出swap out），而將外存中的某個進(jìn)程的地址空間讀到內(nèi)存中（換入swap in）。換入換出內(nèi)容的大小為整個程序的地址空間。換入換出的開銷比較大，在確實內(nèi)存不夠的情況下才使用這種方式，并減少換入換出的次數(shù)。
3）虛存技術(shù)：（虛擬內(nèi)存管理技術(shù)）根據(jù)程序的局部性原理，在程序的執(zhí)行過程中的一個較短時間內(nèi)，所執(zhí)行的指令地址和指令操作地址局限在一定區(qū)域內(nèi)，把執(zhí)行的程序段存入到物理內(nèi)存中，沒執(zhí)行到的程序段放到外存中，以分段或分頁等形式。以分頁為例，在其基礎(chǔ)上需要增加請求調(diào)頁和頁面置換功能。即在用戶程序調(diào)入內(nèi)存中的時候，不是將所有頁面都裝入內(nèi)存，而只是裝入部分頁面就可以啟動程序，在運行過程中，如果發(fā)現(xiàn)要運行的程序或要訪問的數(shù)據(jù)不在內(nèi)存中，則向系統(tǒng)發(fā)出缺頁中斷，系統(tǒng)在處理這個中斷時，將外存中響應(yīng)的頁面調(diào)入內(nèi)存，使得該程序能夠繼續(xù)運行。
虛擬內(nèi)存管理的頁面置換算法：
功能：當(dāng)缺頁中斷發(fā)生，需要調(diào)入新的頁面而內(nèi)存已滿是，選擇內(nèi)存當(dāng)中哪個物理頁面被置換。
目標(biāo)：盡可能地減少頁面的換入換出次數(shù)（即缺頁中斷次數(shù)）。具體來說，把未來不再使用的或短時期內(nèi)較少使用的頁面換出，通常只能在局部性原理指導(dǎo)下依據(jù)過去的統(tǒng)計數(shù)據(jù)來進(jìn)行預(yù)測。
頁面鎖定：在頁表中添加鎖定標(biāo)志位，把用于描述必須常駐內(nèi)存的操作系統(tǒng)的關(guān)鍵部分或時間關(guān)鍵的應(yīng)用進(jìn)程鎖定不進(jìn)行換入換出。
（1）局部頁置換算法：局部頁面置換算法只置換本進(jìn)程內(nèi)的物理頁面，進(jìn)程中一個頁面進(jìn)內(nèi)存，就代表一個頁面已經(jīng)被替換出內(nèi)存，所以一個進(jìn)程所占用的物理頁面的總數(shù)是確定的。
1）最優(yōu)頁面置換算法：當(dāng)一個缺頁中斷發(fā)生時，對于保存在內(nèi)存中的每一個邏輯頁面，計算在它下一次訪問之前需要等待的時間，從中選擇等待時間最長的頁面置換。一種理想情況，實際系統(tǒng)中無法實現(xiàn)。根據(jù)未來推測未來。
2）先見先出算法：選擇在內(nèi)存中駐留時間最長的頁面并置換。性能較差，換出的頁可能是經(jīng)常訪問的頁，且有Belady現(xiàn)象。
3）最近最久未使用算法：當(dāng)缺頁中斷時，選擇最久未使用的頁面并置換。最優(yōu)置換算法的一個近似，根據(jù)過去推測未來。
4）時鐘頁面置換算法：跟LRU類似，對FIFO的一種改進(jìn)，用頁表項中的訪問位，當(dāng)一個頁面被裝入內(nèi)存時，把該位初始化為0，如果該頁面被訪問，則設(shè)為1，把各個頁面組織成環(huán)形鏈表（類似時鐘表面），把指針執(zhí)行最老的頁面（最先進(jìn)來），當(dāng)發(fā)生缺頁中斷時，考察指針?biāo)赶虻淖罾享撁?，如果它的訪問位為0，立即換出，如果訪問位為1則置為0，指針往下移動一格，直到找到被置換頁面，然后指針移動到它的下一格。
二次機會法：修改clock算法，使它允許臟頁總是在一次時鐘頭掃描中保留下來，同時使用臟位和使用位指導(dǎo)置換，減少對硬盤的訪問。
5）最不常用算法：當(dāng)一個缺頁中斷發(fā)生時，選擇訪問次數(shù)最少的那個頁面，并置換。
Belady現(xiàn)象：
Belady現(xiàn)象：在采用FIFO算法時，有時會出現(xiàn)分配的物理頁面增加，缺頁率反而提高的異常現(xiàn)象。FIFO算法的置換特征與進(jìn)程訪問內(nèi)存的動態(tài)特征是矛盾的，與置換算法的目標(biāo)是不一致的（即替換較少使用的頁面），因此被置換出去的頁面并不一定是進(jìn)程不會訪問的。
LRU、FIFO、Clock的比較：
LRU算法和FIFO本質(zhì)上都是先進(jìn)先出的思路，只不過LRU是針對頁面的最近訪問時間來進(jìn)行排序，所以需要在每一次頁面訪問的時候動態(tài)地調(diào)整各個頁面之間的先后順序；而FIFO是針對頁面內(nèi)存的時間來進(jìn)行排序，這個時間是固定不變的，所以各頁面之間的先后順序是固定的。如果一個頁面在進(jìn)入內(nèi)存后沒有被訪問，那么它的最近訪問時間就是它進(jìn)入內(nèi)存的時間。換句話說，如果內(nèi)存中的所有頁面都未訪問過，那么LRU算法就退化為FIFO算法。Clock算法是LRU的一種近似，用了一些硬件的bit來模擬訪問時間和先后順序，開銷較小。
（2）全局頁置換算法：全局頁面置換算法置換內(nèi)存中所有可換出的物理頁面，即換進(jìn)內(nèi)存的是進(jìn)程A的頁面，換出內(nèi)存的可能是進(jìn)程B的頁面，所以進(jìn)程在內(nèi)存中占用的頁面總數(shù)是可變的。
1）工作集置換算法：工作集表示為二元函數(shù)W（t,△），t為當(dāng)前時刻，△為頁面訪問時間窗口，工作集就是在t-△到t的這段時間內(nèi)所有訪問頁面的集合。常駐集是在當(dāng)前時刻，進(jìn)程實際駐留在內(nèi)存當(dāng)中的頁面集合。工作集置換算法就是說每次訪問內(nèi)存時，就把不存在于工作集中的頁面從內(nèi)存中換出，不管這次訪問缺頁與否。
2）缺頁率頁面置換算法：訪問內(nèi)存不缺頁時，就把相應(yīng)的頁面的引用為設(shè)置為1。缺頁時，就把當(dāng)前時間和上次缺頁的時間相減計算時間間隔，如果時間間隔大于給定窗口的話，就說明缺頁率過低了，進(jìn)程在內(nèi)存中的物理頁面數(shù)太多了，進(jìn)程并發(fā)度下降，CPU效率會降低，需要置換出去一些頁面。如果時間間隔小于給定窗口的話，就說明缺頁率過高，把缺頁的添加進(jìn)內(nèi)存。缺頁率置換算法只在缺頁時才進(jìn)行頁面的增加或減少。在缺頁中斷的時候可以把置換的過程部分提交給硬件進(jìn)行處理，提高了性能。
抖動問題：隨著駐留內(nèi)存的進(jìn)程數(shù)目增加，分配給每個進(jìn)程的物理頁面數(shù)不斷減小，缺頁率不斷上升，造成進(jìn)程物理頁面太少，不能包含工作集，造成大量缺頁，頻繁置換，進(jìn)程運行速度變慢等問題。操作系統(tǒng)需要選擇適當(dāng)?shù)倪M(jìn)程數(shù)目和進(jìn)程需要的物理頁面數(shù)。
進(jìn)程
進(jìn)程：一個具有獨立功能的程序在一個數(shù)據(jù)集合上的一次動態(tài)的執(zhí)行過程。
進(jìn)程包括：程序的代碼；程序處理的數(shù)據(jù)；程序計數(shù)器中的值，指示下一條將運行的指令；一組通用的寄存器的值，堆棧；一組系統(tǒng)資源等一個運行的程序的所有狀態(tài)信息。
程序是產(chǎn)生進(jìn)程的基礎(chǔ)，程序的每次運行構(gòu)成不同的進(jìn)程，進(jìn)程是程序功能的體現(xiàn)。多次執(zhí)行一個程序可以產(chǎn)生多個進(jìn)程，通過調(diào)用關(guān)系，一個進(jìn)程可以包括多個程序。
進(jìn)程是動態(tài)的，程序是靜態(tài)的；程序是有序的代碼集合，進(jìn)程是程序的執(zhí)行，進(jìn)程擁有核心態(tài)/用戶態(tài)。進(jìn)程是一個狀態(tài)變化過程，進(jìn)程是暫時的，程序是永久的。CPU可以根據(jù)具體情況切換不同的進(jìn)程，完成不同的功能。
進(jìn)程的特點：
1）動態(tài)性：可動態(tài)地創(chuàng)建、結(jié)束進(jìn)程；
2）并發(fā)性：進(jìn)程可以被獨立調(diào)度并占用處理機運行；
3）獨立性：不同進(jìn)程的工作不相影響；
4）制約性：因訪問共享數(shù)據(jù)/資源或進(jìn)程間同步產(chǎn)生制約。
操作系統(tǒng)為每一個進(jìn)程維護(hù)了一個PCB（Process Control Block），用來保存與該進(jìn)程有關(guān)的各種狀態(tài)信息。
進(jìn)程控制結(jié)構(gòu)
進(jìn)程控制塊PCB有以下三大類信息：
1）進(jìn)程標(biāo)識信息。2）處理機狀態(tài)信息保存區(qū)。3）進(jìn)程控制信息。
進(jìn)程的生命周期：
進(jìn)程創(chuàng)建：系統(tǒng)初始化；用戶請求創(chuàng)建一個新進(jìn)程；正在運行的進(jìn)程執(zhí)行了創(chuàng)建進(jìn)程的系統(tǒng)調(diào)用。
進(jìn)程運行：內(nèi)核選擇一個就緒的進(jìn)程，讓它占用處理機并執(zhí)行。
進(jìn)程等待（阻塞）：1、請求并等待系統(tǒng)服務(wù)，無法馬上完成。2、啟動某種操作，無法馬上完成。3、需要數(shù)據(jù)沒有到達(dá)。進(jìn)程只能自己阻塞自己，因為只有進(jìn)程自身才能知道何時需要等待某種事件的發(fā)生。
進(jìn)程喚醒：1、被阻塞進(jìn)程需要的資源可以滿足。2、被阻塞進(jìn)程等待的事件到達(dá)。3、將該進(jìn)程的PCB插入到就緒隊列。進(jìn)程只能被別的進(jìn)程或操作系統(tǒng)喚醒。
進(jìn)程結(jié)束：1、正常退出。2、錯誤退出。3、致命錯誤。4、被其他進(jìn)程殺死。
進(jìn)程的基本狀態(tài)：
1）運行狀態(tài)：一個進(jìn)程正在處理機上運行時。
2）就緒狀態(tài)：一個進(jìn)程獲得了除處理機外的一切所需資源，一旦得到處理機即可運行。
3）等待狀態(tài)：一個進(jìn)程正在等待某一事件而暫停運行時。
4）創(chuàng)建狀態(tài)：一個進(jìn)程正在創(chuàng)建，還沒被轉(zhuǎn)到就緒狀態(tài)之前。
5）結(jié)束狀態(tài)：一個進(jìn)程正在從操作系統(tǒng)中消失的狀態(tài)。
進(jìn)程掛起：進(jìn)程在掛起時，意味著進(jìn)程沒有占用內(nèi)存空間，掛起狀態(tài)的進(jìn)程映射到磁盤空間上。
阻塞掛起狀態(tài)：進(jìn)程在外存等待某事件的出現(xiàn)。
就緒掛起狀態(tài)：進(jìn)程在外存，但只要進(jìn)入內(nèi)存即可運行。
線程
線程是進(jìn)程當(dāng)中的一條執(zhí)行流程。
進(jìn)程管理資源，把進(jìn)程的執(zhí)行過程拆出來由線程執(zhí)行，進(jìn)程由資源管理和線程執(zhí)行。進(jìn)程可以有多個線程，線程可以共享進(jìn)程的系統(tǒng)資源。線程控制結(jié)構(gòu)TCB。
優(yōu)點：一個進(jìn)程可以同時存在多個線程；各線程之間可以并發(fā)執(zhí)行；各線程之間可以共享地址空間和文件等資源。
缺點：一個線程崩潰會導(dǎo)致其所屬進(jìn)程所有線程的崩潰。
進(jìn)程線程比較：
進(jìn)程是資源分配的單位，線程是CPU調(diào)度的單位。進(jìn)程擁有完成的資源平臺，線程只獨享不可少的資源，如寄存器和棧；線程同樣具有就緒、阻塞、執(zhí)行三種基本狀態(tài)；線程能減少并發(fā)執(zhí)行的時間和空間開銷，線程創(chuàng)建時間比進(jìn)程短，線程終止時間比進(jìn)程短，同一進(jìn)程內(nèi)的線程切換時間比進(jìn)程短，由于同一個進(jìn)程的各線程共享內(nèi)存和文件資源，可直接進(jìn)行不通過內(nèi)核的通信。
上下文：context，寄存器中的信息。
多個進(jìn)程同時處于內(nèi)存，當(dāng)一個進(jìn)程必須等待時，OS從該進(jìn)程拿走CPU使用權(quán)交給其他進(jìn)程，進(jìn)程執(zhí)行從一個IO區(qū)間(I/O burst)開始，隨后進(jìn)入一個CPU區(qū)間(CPU burst)并反復(fù)，進(jìn)程循環(huán)地在CPU執(zhí)行和I/O等待兩個狀態(tài)間切換，直到通過系統(tǒng)請求終止最后一個CPU burst。
搶占&非搶占
CPU調(diào)度決策發(fā)生在4種情況下：
1) 進(jìn)程從運行(running)狀態(tài)切換到等待(waiting)狀態(tài)；
2) 進(jìn)程從運行(running)狀態(tài)切換到就緒(ready)狀態(tài)；
3) 進(jìn)程從等待(waiting)狀態(tài)切換到就緒(ready)狀態(tài)；
4) 進(jìn)程終止
非搶占(nonpreemptive)調(diào)度方案：a.k.a. 協(xié)作(cooperative)調(diào)度方案，一旦CPU分配給一個進(jìn)程，該進(jìn)程會一直使用CPU直到進(jìn)程終止或切換到等待狀態(tài)，該方案中調(diào)度只發(fā)生在1、4兩種情況下。
否則稱為搶占(preemptive)調(diào)度方案。
調(diào)度準(zhǔn)則
用于分析比較CPU調(diào)度算法的準(zhǔn)則可包括
1）CPU使用率(CPU utilization)：理論上為0%~100%，真實系統(tǒng)一般為40%~90%。
2）吞吐量(Throughput)：一個時間單位內(nèi)所完成進(jìn)程的數(shù)量。
3）周轉(zhuǎn)時間(Turnaround time)：一個進(jìn)程從提交到完成的所用時間。
4）等待時間(Waiting time)：進(jìn)程在就緒隊列中等待所用時間之和。
5）響應(yīng)時間(response time)：從提交請求到產(chǎn)生第一響應(yīng)的所用時間。
需要使CPU utilization和throughput最大化，turnaround time、waiting time和response time最小化。絕大多數(shù)情況下需要優(yōu)化平均值，有些情況下需要優(yōu)化最大值、最小值或response time方差等。
調(diào)度算法
1）FCFS，先到先服務(wù)調(diào)度算法(first-come, first-served (FCFS) scheduling algorithm)：先請求CPU的進(jìn)程先分配到CPU，通常用FIFO隊列實現(xiàn)。 FCFS策略平均等待時間通常較長，不適用于time-sharing系統(tǒng)。
2）SJF （提供最短平均等待時間）最短作業(yè)有限調(diào)度算法(shortest-job-first (SJF) scheduling algorithm)：每個進(jìn)程與其下一個CPU burst關(guān)聯(lián)。當(dāng)CPU空閑時，將它分配給具有最短CPU burst的進(jìn)程。
3）優(yōu)先級調(diào)度算法(priority scheduling algorithm)：每個進(jìn)程都與一個優(yōu)先級(priority)關(guān)聯(lián)，CPU被分配給具有最高priority的進(jìn)程，相同priority的進(jìn)程按FCFS順序調(diào)度。
4）RR （適合分時/交互系統(tǒng)）
時間片(time quantum, a.k.a. time slice)：一個較小的時間單元，通常為10~100ms。
輪轉(zhuǎn)法調(diào)度算法(round-robin (RR) scheduling algorithm)：專門為time-sharing系統(tǒng)設(shè)計，CPU調(diào)度程序循環(huán)就緒隊列，為每個進(jìn)程分配不超過一個time quantum的CPU。
5）多級隊列調(diào)度算法(multilevel queue scheduling algorithm)：將就緒隊列劃分成多個獨立隊列，每個隊列有自己的調(diào)度算法。進(jìn)程根據(jù)自身屬性被永久分配到對應(yīng)的一個隊列。常用模型：前臺交互隊列使用RR，和后臺批處理隊列使用FCFS。
6）多級反饋隊列調(diào)度算法(multilevel feedback queue scheduling algorithm)：根據(jù)CPU burst的特點區(qū)分進(jìn)程。如果進(jìn)程使用過多CPU時間則轉(zhuǎn)移到更低隊列，在低priority隊列中等待時間過長的進(jìn)程可被轉(zhuǎn)移到高priority隊列。
臨界區(qū)
多個線程在同時調(diào)用函數(shù)時可能會產(chǎn)生問題，可能會產(chǎn)生問題的這部分代碼稱之為臨界區(qū)（Critical Section）。
根據(jù)臨界區(qū)是否會產(chǎn)生問題，函數(shù)可分為：
線程安全函數(shù)被多個線程同時調(diào)用也沒有問題，但是非線程安全函數(shù)就可能會引發(fā)問題。
大多數(shù)標(biāo)準(zhǔn)函數(shù)都是線程安全函數(shù)，我們不需要自己區(qū)分線程安全函數(shù)與非線程安全函數(shù)。
線程存在的問題和臨界區(qū)
任何內(nèi)存空間只要是被線程同時訪問，就有可能發(fā)生問題。為了解決這個臨界區(qū)的問題其實很簡單，就是不讓不同線程同時訪問一個變量。而實現(xiàn)這個就是線程同步。
線程同步可以解決兩方面的情況：
互斥量 Mutual Exclusion
表示不允許多個線程同時訪問，互斥量主要用于解決線程同步的問題。
我們通過互斥量實現(xiàn)互斥鎖，在一個線程在訪問變量時就將他鎖住，而等到訪問完畢再釋放這把鎖。當(dāng)其他線程預(yù)備進(jìn)入臨界區(qū)時，如果發(fā)現(xiàn)有其他線程已經(jīng)進(jìn)入臨界區(qū)。將使這個函數(shù)阻塞，一直到那個線程結(jié)束使用臨界區(qū)。如果線程退出臨界區(qū)時，沒有調(diào)用unlock函數(shù)，那么其他線程將一直處于阻塞狀態(tài)，這種情況就是死鎖。
互斥量lock，unlock函數(shù)的頻繁調(diào)用使程序的執(zhí)行效率降低，所以應(yīng)該對于不同的程序適當(dāng)?shù)目紤]是應(yīng)該擴(kuò)大還是縮小臨界區(qū)。
信號量 Semaphore
與互斥量的開鎖與解鎖相比。信號量就是給一個信號，看是否復(fù)合條件能通過，當(dāng)它的值大于0時，表示當(dāng)前可用資源的數(shù)量；當(dāng)它的值小于0時，其絕對值表示等待使用該資源的進(jìn)程個數(shù)。信號量本質(zhì)上是一個計數(shù)器（不設(shè)置全局變量是因為進(jìn)程間是相互獨立的，而這不一定能看到，看到也不能保證++引用計數(shù)為原子操作）,用于多進(jìn)程對共享數(shù)據(jù)對象的讀取，它和管道有所不同，它不以傳送數(shù)據(jù)為主要目的，它主要是用來保護(hù)共享資源（信號量也屬于臨界資源），使得資源在一個時刻只有一個進(jìn)程獨享。一般來說，信號量S>=0時，S表示可用資源的數(shù)量。執(zhí)行一次P操作意味著請求分配一個單位資源，因此S的值減1；當(dāng)S<0時，表示已經(jīng)沒有可用資源，請求者必須等待別的進(jìn)程釋放該類資源，它才能運行下去。而執(zhí)行一個V操作意味著釋放一個單位資源，因此S的值加1；若S<0，表示有某些進(jìn)程正在等待該資源，因此要喚醒一個等待狀態(tài)的進(jìn)程，使之運行下去。
PV操作是典型的同步機制之一， PV操作與信號量的處理相關(guān)，P表示通過的意思，V表示釋放的意思。PV操作即可實現(xiàn)同步，也可以實現(xiàn)互斥。
由于信號量只能進(jìn)行兩種操作等待和發(fā)送信號，即P(sv)和V(sv),他們的行為是這樣的：
（1）P(sv)：如果sv的值大于零，就給它減1；如果它的值為零，就掛起該進(jìn)程的執(zhí)行
（2）V(sv)：如果有其他進(jìn)程因等待sv而被掛起，就讓它恢復(fù)運行，如果沒有進(jìn)程因等待sv而掛起，就給它加1.
在信號量進(jìn)行PV操作時都為原子操作（因為它需要保護(hù)臨界資源），單指令的操作稱為原子的，單條指令的執(zhí)行不會被打斷。
舉例：
信號量就是在一個叫做互斥區(qū)的門口放一個盒子，盒子里面裝著固定數(shù)量的小球，每個線程過來的時候，都從盒子里面摸走一個小球，然后進(jìn)入互斥區(qū)，出來的時候，再把小球放回盒子里。如果一個線程走過來一摸盒子，一個球都沒有，就只能站在門口等一個線程出來放回來一個球，再進(jìn)去。由于小球的數(shù)量是固定的，那么互斥區(qū)里面的最大線程數(shù)量就是固定的，不會出現(xiàn)進(jìn)入太多線程把互斥區(qū)給擠爆了的情況。這是用信號量做并發(fā)量限制。
另外一些情況下，小球是一次性的，線程拿走一個進(jìn)了門，就把小球扔掉了，這樣用著用著小球就沒了，不過有另外一些線程（一般叫做生產(chǎn)者）會時不時過來往盒子里再放幾個球，這樣就可以有新的線程（一般叫做消費者）進(jìn)去了，放一個球進(jìn)一個線程，這是信號量做同步功能。
死鎖
多個進(jìn)程在運行過程中因爭奪資源而造成的一種僵局，當(dāng)進(jìn)程處于這種僵持狀態(tài)時，若無外力作用，它們都將無法再向前推進(jìn)。
產(chǎn)生死鎖的四個必要條件：
1）互斥條件：進(jìn)程要求對所分配的資源進(jìn)行排它性控制，即在一段時間內(nèi)某資源僅為一進(jìn)程所占用。
2）請求和保持條件：當(dāng)進(jìn)程因請求資源而阻塞時，對已獲得的資源保持不放。
3）不剝奪條件：進(jìn)程已獲得的資源在未使用完之前，不能剝奪，只能在使用完時由自己釋放。
4）環(huán)路等待條件：在發(fā)生死鎖時，必然存在一個進(jìn)程--資源的環(huán)形鏈。
預(yù)防死鎖：
避免死鎖：
基本概念
存儲容量 = 磁頭數(shù)×磁道（柱面）數(shù)×每道扇區(qū)數(shù) ×每扇區(qū)字節(jié)數(shù)
磁盤的類型
按照磁頭是否需要移動進(jìn)行分類：
固定頭磁盤
對于同一盤面上的不同磁道我們都有相應(yīng)位置固定的磁頭進(jìn)行讀寫，如上圖中的黑色磁頭和藍(lán)色磁頭分別讀取一個磁道，對多條磁道進(jìn)行讀寫的時候，磁頭不需要移動位置。所以對于一個盤面上的多條磁道可以并行進(jìn)行讀取，訪問速度較快。同樣價格也較高。
移動頭磁盤
對于移動頭磁盤，它的磁頭是可以沿著徑向臂進(jìn)行徑向移動，所以只需要使用一個磁頭就可以訪問所有的磁道。但是同一時間只能訪問一個磁道，只能實現(xiàn)順序讀寫，讀寫速度較慢，但是造價較低。計算機中使用的磁盤大多數(shù)都是移動頭磁盤。
磁盤調(diào)度
當(dāng)有大量磁盤I/O請求時，恰當(dāng)選擇調(diào)度順序，以降低完成這些I/O服務(wù)的總時間。
磁盤調(diào)度方式主要有以下兩種：
由于旋轉(zhuǎn)調(diào)度算法較為簡單，只是按照扇區(qū)距離磁頭的位置的偏差來進(jìn)行調(diào)度。所以下面將以移臂調(diào)度為講解。
移臂調(diào)度算法
1）先來先服務(wù)FCFS(First-Come, First Served)
假設(shè)當(dāng)前磁道在100號磁道，磁頭正向磁道號增加的方向（由外向里）移動?，F(xiàn)依次有如下磁盤請求隊列：23，376， 205，132， 61， 190， 29， 4， 40。
則磁盤調(diào)度順序和尋道距離為：
23，376， 205，132， 61， 190， 29， 4， 40
Ts = (100-23) + (376-23) + (376-205) + (205-132) + ... + (40-4)
平均尋道距離 = Ts / 9 。
由于先來新服務(wù)算法并沒有對磁盤訪問進(jìn)行優(yōu)化，所以它可能會得到比較長的尋道距離。
2）最短尋道時間優(yōu)先算法SSTF
在選擇下一條磁道的時候總是訪問與當(dāng)前磁盤距離最近的磁盤進(jìn)行訪問。
對于上例，其磁盤調(diào)度順序和尋道距離為：
132 , 190, 205, 61, 40, 29, 23, 4, 376
Ts = (132-100) + (190-132) + (205-190) + ... + (23-4) + (376-4)
最短尋道距離優(yōu)先可以保障每一次的尋道距離最短，但是不能夠保障最后系統(tǒng)得到的平均尋道距離最短。如最后 4 到 376 的磁盤尋道跨度就非常大。
它也存在著一下幾個問題：
3）掃描(SCAN)算法（又稱為電梯算法）
它是目前操作系統(tǒng)中用的比較廣泛的一種磁盤移臂調(diào)度算法。
其在對下一條磁道進(jìn)行選擇時，需要判斷：
同樣，對于上例，其磁盤調(diào)度順序和尋道距離為：
132，190， 205，376， 61, 40, 29, 23, 4
Ts = (132-100) + (190-132) + (205-190) + (376-205) + (376-61) + (61-40) +... + (23-4)
4）N-Step-SCAN算法 (N步掃描算法)
它是為了克服掃描算法和最短尋道時間有限算法的“磁臂粘著”現(xiàn)象而引入的。
“磁臂粘著”現(xiàn)象就是指當(dāng)系統(tǒng)不斷的提出對當(dāng)前磁道的訪問，那么磁頭會一直處于該磁道上進(jìn)行磁道訪問請求，導(dǎo)致其它磁道的訪問被推遲的現(xiàn)象。
N步掃描算法的算法思想：將磁盤請求隊列分成若干個長度為N的子隊列，磁盤調(diào)度將按FCFS算法依次處理這些子隊列； 而每處理一個子隊列時又采用SCAN算法。
如對于上例，若其子隊列的長度為4，則可以分為3個隊列：
它就會首先處理第一個隊列中的四個磁道請求，再處理第二個隊列和最后的第三個隊列。其對于每一個隊列的處理都是按照掃描算法來進(jìn)行處理。
5）FSCAN算法
該算法實質(zhì)上是N步SCAN算法的簡化， 它只將磁盤請求隊列分成兩個子隊列：
① 由當(dāng)前所有請求磁盤形成的隊列，由磁盤調(diào)度按SCAN算法進(jìn)行處理。
② 在掃描期間，將新出現(xiàn)的所有磁盤I/O請求， 放入另一個等待處理的請求隊列。
如上例，先把所有的磁盤請求放在第一個隊列中，對其應(yīng)用掃描算法進(jìn)行磁盤調(diào)度。若訪問過程中出現(xiàn)的新的磁盤請求就放在下面的新隊列中，當(dāng)?shù)谝粋€隊列全部訪問完，再處理第二個隊列。
6）旋轉(zhuǎn)調(diào)度算法
當(dāng)同一磁道（柱面）上有多個扇區(qū)請求時，總是選取與當(dāng)前讀寫頭最近的那個I/O請求，使旋轉(zhuǎn)圈數(shù)最少。
例：對磁盤訪問的5個請求，若磁頭在1號柱面，先按SCAN算法做移臂調(diào)度（柱面號排序），再進(jìn)行旋轉(zhuǎn)調(diào)度（塊號排序），則調(diào)度順序如下：
聯(lián)系客服
