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