前言

北大《操作系統(tǒng)原理》課堂筆記帚豪，大綱如下：

1. 操作系統(tǒng)概述
2. 操作系統(tǒng)運(yùn)行環(huán)境
3. 進(jìn)程線(xiàn)程模型
4. 處理器調(diào)度
5. 同步機(jī)制
6. 存儲(chǔ)模型
7. 文件系統(tǒng)
8. I/O系統(tǒng)
9. 死鎖

操作系統(tǒng)概述

1. 執(zhí)行程序：通過(guò)調(diào)度選中程序開(kāi)始執(zhí)行瓦糕，在執(zhí)行過(guò)程中蜜徽，不斷陷入操作系統(tǒng)提供各種服務(wù)支持，再調(diào)度選中程序顽耳，直到完成
2. 功能：有效（充分利用CPU坠敷、內(nèi)存、磁盤(pán)等資源）射富、合理（公平的資源管理策略）膝迎、易用（用戶(hù)界面和編程接口）
3. 作用：管理資源（硬件、軟件）胰耗、向用戶(hù)提供服務(wù)（創(chuàng)建弄抬、執(zhí)行、IO宪郊、統(tǒng)計(jì)）掂恕、對(duì)硬件機(jī)器擴(kuò)展（屏蔽硬件細(xì)節(jié)、提供虛擬機(jī)器界面）
4. 特征：并發(fā)（處理多個(gè)同時(shí)性活動(dòng)）弛槐、共享（非同時(shí)互斥共享懊亡、同時(shí)共享有限系統(tǒng)資源）、虛擬（映射為若干邏輯實(shí)體）乎串、隨機(jī)（不可預(yù)知運(yùn)行次序）
5. 典型架構(gòu)（用戶(hù)態(tài)店枣、內(nèi)核態(tài)）：Windows（硬件抽象、設(shè)備驅(qū)動(dòng)叹誉、內(nèi)核鸯两、圖形窗口、執(zhí)行體长豁、內(nèi)核態(tài)可調(diào)用接口钧唐、服務(wù)分發(fā)器、DLL）匠襟、Unix（硬件控制層钝侠、調(diào)度、進(jìn)程間通信酸舍、存儲(chǔ)管理帅韧、內(nèi)存管理、文件系統(tǒng)啃勉、設(shè)備驅(qū)動(dòng)忽舟、系統(tǒng)調(diào)用接口）、Linux（進(jìn)程淮阐、調(diào)度叮阅、虛擬內(nèi)存、物理內(nèi)存管理枝嘶、各種設(shè)備驅(qū)動(dòng)帘饶、網(wǎng)絡(luò)模塊、陷入異常模塊群扶、中斷處理模塊及刻、系統(tǒng)調(diào)用接口） 、Android（Linux內(nèi)核竞阐、系統(tǒng)庫(kù)和Android運(yùn)行時(shí)系統(tǒng)缴饭、應(yīng)用程序框架、應(yīng)用程序）
6. 分類(lèi)：批處理（Spooling緩存I/O到磁盤(pán)）骆莹、分時(shí)（時(shí)間片颗搂、追求響應(yīng)時(shí)間、交互式）幕垦、實(shí)時(shí)（嚴(yán)格時(shí)間丢氢、高可靠）傅联、個(gè)人計(jì)算機(jī)（使用方便）、網(wǎng)絡(luò)（通信疚察、資源共享）蒸走、分布式（多機(jī)協(xié)同完成一項(xiàng)任務(wù)）、嵌入式（特定裝置中的軟硬件系統(tǒng)）

操作系統(tǒng)運(yùn)行環(huán)境

1. CPU：運(yùn)算器貌嫡、控制器比驻、通用寄存器、控制和狀態(tài)寄存器（PC岛抄、IR别惦、PSW）、高速緩存
2. CPU狀態(tài)：內(nèi)核態(tài)（特權(quán)指令R0）夫椭、用戶(hù)態(tài)（用戶(hù)R3）
3. 中斷／異常機(jī)制：CPU暫停當(dāng)前執(zhí)行程序掸掸，保留現(xiàn)場(chǎng)，硬件自動(dòng)轉(zhuǎn)去處理程序益楼，處理完后回到斷點(diǎn)猾漫，繼續(xù)被打斷的程序
4. 事件：中斷響應(yīng)外部事件，異步處理感凤，總是返回下一條指令悯周，如I/O、時(shí)鐘陪竿、硬件故障禽翼；異常源于內(nèi)部正在執(zhí)行的程序，同步處理族跛，分為陷入闰挡、故障、終止礁哄，如系統(tǒng)調(diào)用长酗、頁(yè)故障、斷點(diǎn)桐绒、權(quán)限保護(hù)夺脾、程序
5. 中斷響應(yīng)（硬件）：指令周期末掃描中斷寄存器，CPU切換到內(nèi)核態(tài)茉继，保存現(xiàn)場(chǎng)（PSW+PC）咧叭，通過(guò)中斷碼查中斷向量表（中斷處理程序入口+處理機(jī)狀態(tài)字），推送中斷處理程序入口到寄存器
6. 中斷處理程序（軟件）：保存相關(guān)寄存器信息烁竭，分析發(fā)生原因菲茬。執(zhí)行處理功能，恢復(fù)現(xiàn)場(chǎng)
7. 系統(tǒng)調(diào)用：用戶(hù)在編程時(shí)可以調(diào)用的操作系統(tǒng)功能，如進(jìn)程控制婉弹、通信睬魂、文件使用、目錄操作马胧、設(shè)備管理汉买、信息維護(hù)
8. 程序調(diào)用：應(yīng)用程序可以通過(guò)庫(kù)函數(shù)和API進(jìn)入系統(tǒng)調(diào)用，也可直接引發(fā)系統(tǒng)調(diào)用佩脊，系統(tǒng)調(diào)用再調(diào)用對(duì)應(yīng)內(nèi)核函數(shù)
9. 系統(tǒng)調(diào)用設(shè)計(jì)：中斷／異常機(jī)制（支持系統(tǒng)調(diào)用服務(wù)的實(shí)現(xiàn)），陷入指令（引發(fā)異常垫卤，用戶(hù)態(tài)切換到內(nèi)核態(tài)）威彰，系統(tǒng)調(diào)用號(hào)和參數(shù)（不同系統(tǒng)調(diào)用的編號(hào)），系統(tǒng)調(diào)用表（服務(wù)程序的入口地址）穴肘，參數(shù)傳遞（陷入指令自帶歇盼、通用寄存器、內(nèi)存中專(zhuān)用堆棧區(qū)）
10. 系統(tǒng)調(diào)用過(guò)程：CPU執(zhí)行到特殊的陷入指令评抚；中斷硬件保護(hù)現(xiàn)場(chǎng)豹缀，通過(guò)門(mén)描述符（段選擇符+偏移量）查系統(tǒng)調(diào)用表；轉(zhuǎn)入查到的系統(tǒng)調(diào)用總?cè)肟诔绦蚩Ｗo(hù)現(xiàn)場(chǎng)邢笙，保存參數(shù)到內(nèi)核堆棧，通過(guò)系統(tǒng)調(diào)用號(hào)查系統(tǒng)調(diào)用表侍匙；執(zhí)行查到的系統(tǒng)調(diào)用例程氮惯；恢復(fù)現(xiàn)場(chǎng)，返回用戶(hù)程序

進(jìn)程線(xiàn)程模型

1. 并發(fā)程序：一段時(shí)間內(nèi)想暗，單處理器上多個(gè)程序同時(shí)處于開(kāi)始運(yùn)行但未結(jié)束狀態(tài)妇汗，且次序不是事先確定的
2. 進(jìn)程：程序的一次執(zhí)行，正在運(yùn)行程序的抽象说莫、將CPU虛擬為多個(gè)杨箭，系統(tǒng)資源分配單位，每個(gè)具有獨(dú)立地址空間储狭，操作系統(tǒng)將CPU調(diào)度給進(jìn)程
3. 進(jìn)程控制塊PCB：進(jìn)程描述（PID互婿、用戶(hù)標(biāo)識(shí)、進(jìn)程組關(guān)系）晶密、進(jìn)程控制（狀態(tài)擒悬、優(yōu)先級(jí)、入口地址稻艰、隊(duì)列指針）懂牧、資源和使用狀況（存儲(chǔ)空間、文件）、CPU現(xiàn)場(chǎng)（進(jìn)程不執(zhí)行時(shí)保存寄存器值僧凤、指向頁(yè)表的指針）
4. 進(jìn)程狀態(tài)：運(yùn)行（占用CPU）畜侦、就緒（CPU不空閑）、等待／阻塞（等待某事）躯保；創(chuàng)建（信息設(shè)置完但資源有限）旋膳、終止（統(tǒng)計(jì)信息、回收資源）途事；掛起（分就緒掛起和阻塞掛起验懊，回收內(nèi)存存磁盤(pán)，條件允許后可激活）
5. 進(jìn)程隊(duì)列：每類(lèi)進(jìn)程狀態(tài)有一個(gè)或多個(gè)隊(duì)列尸变，元素為PCB义图，進(jìn)程狀態(tài)改變就是換隊(duì)
6. 進(jìn)程控制：利用完成某種功能的不允許中斷的控制原語(yǔ)，轉(zhuǎn)換進(jìn)程狀態(tài)
7. Unix進(jìn)程控制操作：fork（復(fù)制調(diào)用進(jìn)程創(chuàng)建）召烂、exec（新代碼覆蓋原地址空間創(chuàng)建）碱工、wait（主動(dòng)阻塞）、exit（撤銷(xiāo)奏夫，回收資源和PCB）
8. 進(jìn)程層次結(jié)構(gòu)：進(jìn)程由其他進(jìn)程創(chuàng)建怕篷，Unix進(jìn)程家族樹(shù)以init為根，Windows中各進(jìn)程的地位相同
9. 進(jìn)程地址空間：內(nèi)核地址空間酗昼、用戶(hù)地址空間（代碼段廊谓、數(shù)據(jù)段、堆仔雷、共享庫(kù)蹂析、棧）
10. 進(jìn)程映像：進(jìn)程地址空間、硬件寄存器碟婆、PCB及各種數(shù)據(jù)結(jié)構(gòu)电抚、進(jìn)入進(jìn)程時(shí)所需的內(nèi)核棧
11. 上下文context切換：CPU硬件狀態(tài)從一個(gè)進(jìn)程換到另一個(gè)，運(yùn)行的進(jìn)程硬件狀態(tài)保存在CPU寄存器上竖共，不運(yùn)行時(shí)保存在PCB中蝙叛，之后可推送至CPU寄存器
12. 引入線(xiàn)程：應(yīng)用需要（如Web服務(wù)器）、減少開(kāi)銷(xiāo)（創(chuàng)建和切換花費(fèi)時(shí)間少公给，通信無(wú)需內(nèi)核）借帘、提升性能（多處理器）
13. 線(xiàn)程與進(jìn)程：線(xiàn)程是進(jìn)程中的運(yùn)行實(shí)體，CPU的調(diào)度單位淌铐，增加了多個(gè)執(zhí)行序列
14. 線(xiàn)程屬性：ID肺然、狀態(tài)、上下文腿准、棧指針际起；共享進(jìn)程的地址空間和其他資源拾碌；程序以單線(xiàn)程進(jìn)程開(kāi)始，線(xiàn)程由線(xiàn)程創(chuàng)建和撤銷(xiāo)
15. 線(xiàn)程的實(shí)現(xiàn)：Unix是用戶(hù)級(jí)線(xiàn)程街望，內(nèi)核無(wú)法感知線(xiàn)程存在校翔，切換較快，但同進(jìn)程的線(xiàn)程不能分到多CPU上灾前，阻塞會(huì)阻塞整個(gè)進(jìn)程防症；Windows是內(nèi)核級(jí)線(xiàn)程，內(nèi)核中包含線(xiàn)程表哎甲，調(diào)度以線(xiàn)程為單位蔫敲；Solaris為混合模型，線(xiàn)程創(chuàng)建在用戶(hù)空間炭玫，調(diào)度在內(nèi)核
16. Pthread：POSIX多線(xiàn)程編程接口燕偶，線(xiàn)程協(xié)商誰(shuí)上CPU；如yield函數(shù)主動(dòng)讓出CPU
17. 進(jìn)程特性：并發(fā)（任何進(jìn)程都可和其他同時(shí)推進(jìn)）础嫡、動(dòng)態(tài)（生命周期中切換狀態(tài)）、獨(dú)立（資源）酝惧、交互（進(jìn)程間產(chǎn)生關(guān)系）榴鼎、異步（進(jìn)程獨(dú)立不可預(yù)知的推進(jìn)）、進(jìn)程映像（程序+數(shù)據(jù)+棧+PCB）
18. 可重入程序：純代碼晚唇，執(zhí)行不改變巫财，調(diào)用它的進(jìn)程提供數(shù)據(jù)區(qū)；大部分進(jìn)程和線(xiàn)程只有可重入程序才可以運(yùn)行

處理器調(diào)度

1. CPU調(diào)度：在合適的調(diào)度時(shí)機(jī)哩陕，按調(diào)度算法平项，調(diào)度就緒隊(duì)列中的進(jìn)程進(jìn)CPU
2. 調(diào)度時(shí)機(jī)：內(nèi)核對(duì)中斷／異常／系統(tǒng)調(diào)用處理后，就緒隊(duì)列改變引發(fā)重新調(diào)度悍及，如進(jìn)程終止闽瓢、創(chuàng)建、運(yùn)行轉(zhuǎn)入阻塞心赶、運(yùn)行轉(zhuǎn)入就緒
3. 進(jìn)程切換：切換全局頁(yè)目錄加載新的地址空間扣讼，切換內(nèi)核棧和硬件上下文；進(jìn)程A切換到B缨叫，保存A上下文環(huán)境椭符，更新A的PCB，A移至合適隊(duì)列耻姥，B設(shè)為運(yùn)行態(tài)销钝，從B的PCB恢復(fù)上下文
4. 調(diào)度算法考慮：優(yōu)先級(jí)與優(yōu)先數(shù)？多級(jí)就緒隊(duì)列如何組織琐簇？是否搶占蒸健？I/O密集或CPU密集友好？時(shí)間片長(zhǎng)度？
5. 不同系統(tǒng)的調(diào)度算法：批處理處理看重吞吐量纵装、周轉(zhuǎn)時(shí)間浪规、CPU利用率始花、平衡（先來(lái)先服務(wù)FCFS、最短作業(yè)優(yōu)先SJF、最短剩余時(shí)間優(yōu)先SRTN昔善、最高響應(yīng)比優(yōu)先HRRN）；交互式系統(tǒng)看重響應(yīng)時(shí)間塘秦、平衡（輪轉(zhuǎn)Round-Robin定踱、最高優(yōu)先級(jí)HPF、多級(jí)反饋隊(duì)列Feedback瓶籽、類(lèi)似SJF的最短進(jìn)程優(yōu)先SPN）
6. 優(yōu)先級(jí)反轉(zhuǎn)：搶占式最高優(yōu)先級(jí)調(diào)度時(shí)匠童，高優(yōu)先級(jí)受制于低優(yōu)先級(jí)（如臨界區(qū)等待），而低優(yōu)先級(jí)被運(yùn)行時(shí)間較長(zhǎng)的中優(yōu)先級(jí)進(jìn)程搶占塑顺，導(dǎo)致高優(yōu)先級(jí)無(wú)法上CPU
7. 多級(jí)反饋隊(duì)列：多個(gè)就緒隊(duì)列汤求，順次優(yōu)先級(jí)遞減，時(shí)間片遞增严拒，每個(gè)隊(duì)列內(nèi)部按時(shí)間片輪轉(zhuǎn)扬绪；新建進(jìn)程進(jìn)一級(jí)隊(duì)列，用完時(shí)間片進(jìn)下一級(jí)就緒隊(duì)列裤唠；因阻塞進(jìn)入等待隊(duì)列的進(jìn)程在等待完畢后挤牛，回到原級(jí)別的就緒隊(duì)列，但可設(shè)置時(shí)間片是否重新分配种蘸，加入隊(duì)首或隊(duì)尾
8. 系統(tǒng)調(diào)度算法：Unix動(dòng)態(tài)優(yōu)先數(shù)墓赴，5.3BSD多級(jí)反饋隊(duì)列，Linux搶占式調(diào)度航瞭，Windows基于優(yōu)先級(jí)的搶占式多任務(wù)調(diào)度
9. Windows線(xiàn)程調(diào)度：調(diào)度單位是線(xiàn)程诫硕，基于動(dòng)態(tài)優(yōu)先級(jí)的搶占式調(diào)度，結(jié)合時(shí)間配額的調(diào)整沧奴；引發(fā)調(diào)度的條件除線(xiàn)程終止痘括、創(chuàng)建、運(yùn)行轉(zhuǎn)入阻塞滔吠、運(yùn)行轉(zhuǎn)入就緒外纲菌，還有線(xiàn)程優(yōu)先級(jí)改變和親和處理機(jī)集合改變
10. 線(xiàn)程優(yōu)先級(jí)提升：I/O完成、信號(hào)量或事件等待結(jié)束疮绷、前臺(tái)進(jìn)程的線(xiàn)程完成等待翰舌、窗口被喚醒、饑餓超時(shí)
11. 調(diào)度算法對(duì)比：

同步機(jī)制

1. 并發(fā)：進(jìn)程的執(zhí)行是間斷的冬骚，相對(duì)運(yùn)行速度不可預(yù)測(cè)椅贱，共享資源帶來(lái)制約性
2. 競(jìng)爭(zhēng)條件：多個(gè)進(jìn)程讀寫(xiě)共享數(shù)據(jù)時(shí)懂算，結(jié)果取決于進(jìn)程的精確時(shí)序
3. 進(jìn)程互斥：多個(gè)進(jìn)程的臨界區(qū)代碼對(duì)臨界資源的使用需要排他性，各進(jìn)程間競(jìng)爭(zhēng)使用這些共享資源
4. 臨界區(qū)：臨界區(qū)空則可進(jìn)入庇麦，但臨界區(qū)中至多一個(gè)進(jìn)程计技，臨界區(qū)外的進(jìn)程不能阻塞其他進(jìn)程進(jìn)臨界區(qū)，不能讓想進(jìn)臨界區(qū)的進(jìn)程無(wú)限等待
5. 軟件解決互斥：臨界區(qū)空閑標(biāo)志（free）山橄、進(jìn)區(qū)的用戶(hù)（turn）垮媒、各自進(jìn)區(qū)標(biāo)志（pturn+qturn）、dekker算法（turn+pturn+qturn）航棱、peterson（enter_region+leave_region/turn+interest[]）睡雇、
6. 硬件解決互斥：開(kāi)關(guān)中斷指令（特權(quán)指令、中斷屏蔽限制CPU并發(fā)饮醇、不適合多CPU）它抱、測(cè)試并加鎖指令（對(duì)總線(xiàn)加鎖）、交換指令（交換寄存器與鎖變量）
7. 忙等待：進(jìn)程在得到臨界區(qū)訪問(wèn)權(quán)前朴艰，在CPU持續(xù)測(cè)試而不做別的事观蓄；多處理器中使用自旋鎖測(cè)試，讓其他CPU改鎖狀態(tài)祠墅，切換代價(jià)反而比持續(xù)測(cè)試大
8. 進(jìn)程同步：多進(jìn)程中發(fā)生的事件存在時(shí)序關(guān)系蜘腌，需要協(xié)作完成任務(wù)
9. 生產(chǎn)者/消費(fèi)者問(wèn)題：生產(chǎn)者寫(xiě)入緩沖區(qū)，消費(fèi)者從緩沖區(qū)取數(shù)據(jù)饵隙，不能同時(shí)消費(fèi)和生產(chǎn)，緩沖區(qū)空不能消費(fèi)沮脖，緩沖區(qū)滿(mǎn)不能生產(chǎn)
10. 信號(hào)量：用于進(jìn)程間傳遞信息的整數(shù)值金矛，包含隊(duì)列；操作包括初始化（非負(fù)數(shù)）勺届，原語(yǔ)操作P（減）V（增）驶俊；二元信號(hào)量解決互斥，多值信號(hào)量解決同步
11. PV解決互斥：劃定臨界區(qū)免姿，初始化mutex為1饼酿，進(jìn)臨界區(qū)前執(zhí)行P申請(qǐng)資源胚膊，出臨界區(qū)后執(zhí)行V喚醒等待
12. PV解決生產(chǎn)者/消費(fèi)者：初始化mutex為1故俐，empty為空位，full為0紊婉；用mutex對(duì)緩沖區(qū)進(jìn)行PV解決互斥药版，用empty和full進(jìn)行PV解決同步
13. PV解決讀者/寫(xiě)者問(wèn)題：允許多個(gè)讀者同時(shí)讀，不允許同時(shí)讀寫(xiě)喻犁；針對(duì)w信號(hào)槽片，第一個(gè)讀前P何缓，最后一個(gè)讀完V，寫(xiě)前后PV还栓；針對(duì)讀者序列rc碌廓，也需要在修改或判斷前后用PV保護(hù)
14. Linux讀寫(xiě)鎖：每個(gè)執(zhí)行實(shí)體對(duì)臨界區(qū)的訪問(wèn)或讀或?qū)懀粫?huì)同時(shí)讀寫(xiě)剩盒，此時(shí)可應(yīng)用讀者/寫(xiě)者模型谷婆；如路由表中的讀寫(xiě)鎖
15. 管程：有自己名字的特殊模塊，由關(guān)于共享資源的數(shù)據(jù)結(jié)構(gòu)和在其上的操作過(guò)程組成勃刨，進(jìn)程可調(diào)用管程的過(guò)程以操作管程中的數(shù)據(jù)結(jié)構(gòu)波材；編譯器復(fù)雜管程的互斥，設(shè)置條件變量及等待喚醒操作解決同步問(wèn)題
16. 管程內(nèi)多進(jìn)程：若P喚醒Q身隐，則管程中同時(shí)存在活躍狀態(tài)的P和Q兩個(gè)進(jìn)程廷区；處理方法有Hoare（P等待Q）、Mesa（Q等待P）贾铝，Hansen并發(fā)pascal（讓喚醒是管程中最后可執(zhí)行操作）
17. 管程應(yīng)用：直接構(gòu)造條件變量恰當(dāng)?shù)墓艹滔肚幔靡延械耐綑C(jī)制間接構(gòu)造；C++不支持管程垢揩，Java支持類(lèi)似管程
18. Hoare管程：管程入口設(shè)置入口等待隊(duì)列玖绿，內(nèi)部設(shè)置緊急等待隊(duì)列放置喚醒進(jìn)程，P喚醒Q則P等待Q叁巨；wait(c)優(yōu)先喚醒緊急隊(duì)列隊(duì)首斑匪，再將進(jìn)程加入c鏈尾，signal(c)優(yōu)先喚醒c鏈?zhǔn)走M(jìn)入緊急等待隊(duì)列
19. Mesa管程：P喚醒Q則Q等待P锋勺，避免額外進(jìn)程切換開(kāi)銷(xiāo)蚀瘸；signal衍化到notify，進(jìn)程調(diào)度執(zhí)行前再次檢查條件庶橱，每個(gè)條件原語(yǔ)關(guān)聯(lián)監(jiān)視計(jì)時(shí)器超時(shí)即就緒贮勃，再衍化到broadcast使所有該條件隊(duì)列上等待的進(jìn)程進(jìn)入就緒隊(duì)列；Mesa優(yōu)于Hoare
20. Pthread中的同步機(jī)制：互斥變量保護(hù)臨界區(qū)Pthread_mutex_[init/destroy/lock/unlock/trylock]苏章；條件變量解決同步Pthread_cond_[init/destroy/wait/signal/broadcast]
21. 進(jìn)程間通信：消息傳遞寂嘉、共享內(nèi)存、管道枫绅、用于網(wǎng)絡(luò)分布式系統(tǒng)的套接字和遠(yuǎn)程過(guò)程調(diào)用
22. 消息傳遞：send原語(yǔ)泉孩，陷入內(nèi)核，操作系統(tǒng)復(fù)制到消息緩沖區(qū)并淋，并掛接消息到接受進(jìn)程的消息隊(duì)列指針棵譬；receive原語(yǔ)，操作系統(tǒng)將消息復(fù)制到接收進(jìn)程的地址空間
23. 共享內(nèi)存：物理內(nèi)存中建立一塊能夠共享的內(nèi)存空間预伺，將物理內(nèi)存空間映射到兩個(gè)進(jìn)程的地址空間订咸；利用讀者/寫(xiě)者問(wèn)題解決互斥
24. 管道：利用緩沖傳輸介質(zhì)內(nèi)存或文件連接兩個(gè)進(jìn)程曼尊；按字符流讀寫(xiě)，先進(jìn)先出脏嚷，解決互斥同步
25. Linux內(nèi)核同步機(jī)制：原子操作（不可分割）骆撇、屏障（一組線(xiàn)程都到達(dá)匯合點(diǎn)后再一起推進(jìn)）、自旋鎖父叙、信號(hào)量神郊、完成變量、互斥體等

存儲(chǔ)模型

1. 地址重定位：將邏輯／相對(duì)／虛擬地址趾唱，映射到物理／絕對(duì)／實(shí)地址涌乳；程序加載時(shí)用軟件靜態(tài)重定位，執(zhí)行每條指令時(shí)用內(nèi)存管理單元MMU動(dòng)態(tài)重定位
2. 物理內(nèi)存管理：數(shù)據(jù)結(jié)構(gòu)（位圖甜癞、空閑+已分配區(qū)表夕晓、空閑塊鏈表）；分配算法（首次適配悠咱、下次適配蒸辆、最佳適配、最差適配）
3. 伙伴系統(tǒng)：Linux底層內(nèi)存分配算法析既，內(nèi)存按2的整數(shù)次冪劃分躬贡，組成空閑塊鏈表，在鏈表中查找長(zhǎng)度大于等于申請(qǐng)空間且不大于其一半的空閑塊眼坏，內(nèi)存回收時(shí)遞歸合并空閑伙伴
4. 基本內(nèi)存管理方案：占據(jù)內(nèi)存連續(xù)空間（單一連續(xù)區(qū)拂玻、固定分區(qū)、可變分區(qū)）宰译，分布在內(nèi)存中不連續(xù)區(qū)域（頁(yè)式纺讲、段式、段頁(yè)式）
5. 單一連續(xù)區(qū)：?jiǎn)我怀绦颡?dú)占內(nèi)存囤屹，總是被加載到同一內(nèi)存地址
6. 固定分區(qū)：將內(nèi)存分割為若干連續(xù)分區(qū)，大小可不同但必須固定不變逢渔，每個(gè)分區(qū)裝載一個(gè)進(jìn)程
7. 可變分區(qū)：根據(jù)進(jìn)程需要肋坚，動(dòng)態(tài)分割出分區(qū)分配給進(jìn)程
8. 頁(yè)式：用戶(hù)地址空間劃分為大小相等的頁(yè)，內(nèi)存空間按頁(yè)大小劃分為多個(gè)頁(yè)框肃廓，分配單位是頁(yè)
9. 段式：用戶(hù)地址空間按自身邏輯劃分為若干段智厌，內(nèi)存空間劃分為若干個(gè)長(zhǎng)度不同的區(qū)域（可變分區(qū)），分配單位是段
10. 段頁(yè)式：用戶(hù)程序地址空間是段式盲赊，每段內(nèi)含有多頁(yè)铣鹏，內(nèi)存空間是頁(yè)式，分配單位是頁(yè)
11. 緊縮技術(shù)：在內(nèi)存中移動(dòng)程序哀蘑，將所有小的碎片合并為較大的空閑區(qū)诚卸，不能解決頁(yè)式管理造成的內(nèi)碎片
12. 覆蓋技術(shù)：將不會(huì)同時(shí)執(zhí)行的程序段共享同一塊內(nèi)存葵第，需要程序員顯式編程，現(xiàn)在很少用
13. 交換技術(shù)：將程序內(nèi)存中的堆棧（靜態(tài)數(shù)據(jù)一直在磁盤(pán)）合溺，在很少使用或內(nèi)存不夠時(shí)卒密，暫時(shí)移動(dòng)到磁盤(pán)上的交換區(qū)（swap／pagefile），讓外存中的程序占據(jù)其原有內(nèi)存
14. 空間增長(zhǎng)：進(jìn)程的數(shù)據(jù)段和棧段會(huì)持續(xù)增長(zhǎng)（堆向上棠赛，棧向下）哮奇，可預(yù)留一些空間供給它們同向或反向增長(zhǎng)
15. 虛擬存儲(chǔ)：進(jìn)程運(yùn)行時(shí)先將部分裝入內(nèi)存，另一部分暫留在磁盤(pán)睛约，執(zhí)行指令或訪問(wèn)數(shù)據(jù)時(shí)按需從磁盤(pán)調(diào)入內(nèi)存鼎俘；虛存構(gòu)建在存儲(chǔ)體系上，由操作系統(tǒng)調(diào)度各存儲(chǔ)器的使用辩涝；虛存大小與機(jī)器位數(shù)和磁盤(pán)大小有關(guān)
16. 存儲(chǔ)保護(hù)：每個(gè)進(jìn)程有獨(dú)立地址空間贸伐，訪問(wèn)合法地址范圍，權(quán)限合法
17. 虛擬頁(yè)式：虛擬存儲(chǔ)技術(shù)結(jié)合頁(yè)式存儲(chǔ)管理膀值；方式有請(qǐng)求調(diào)頁(yè)和預(yù)先調(diào)頁(yè)
18. 頁(yè)式映射：遞歸查找多級(jí)頁(yè)表起始地址棍丐，與頁(yè)內(nèi)偏移拼接為物理地址；頁(yè)表項(xiàng)中有效位代表是否已存入內(nèi)存
19. 反轉(zhuǎn)頁(yè)表：以物理內(nèi)存大小建立頁(yè)表沧踏，將虛擬地址的頁(yè)號(hào)部分哈希歌逢，指向反轉(zhuǎn)頁(yè)表的某個(gè)位置，借助鏈表解決沖突
20. 內(nèi)存管理單元MMU：查頁(yè)表和頁(yè)表項(xiàng)的功能位翘狱，將虛擬地址轉(zhuǎn)換為物理地址
21. 塊表TLB：由cache組成秘案，是按內(nèi)容并行查找的相聯(lián)存儲(chǔ)器，保存部分頁(yè)表項(xiàng)潦匈；MMU先查快表阱高，沒(méi)命中再查頁(yè)表
22. 頁(yè)錯(cuò)誤：地址轉(zhuǎn)換過(guò)程中硬件產(chǎn)生異常，包括缺頁(yè)茬缩、違反權(quán)限赤惊、地址指向未定義
23. 駐留集：給每個(gè)進(jìn)程分配的頁(yè)框數(shù)；可根據(jù)進(jìn)程類(lèi)型和需要的固定分配凰锡，或依據(jù)缺頁(yè)率評(píng)估的動(dòng)態(tài)分配
24. 置換策略：置換范圍為當(dāng)前進(jìn)程的駐留集叫局部置換未舟，內(nèi)存中所有未鎖定頁(yè)面都為候選叫全局置換；局部掂为、全局置換結(jié)合固定裕膀、動(dòng)態(tài)分配策略，共產(chǎn)生三種方案勇哗，局部固定昼扛、全局固定、全局動(dòng)態(tài)
25. 清除策略：從進(jìn)程駐留集中收回頁(yè)框欲诺；分頁(yè)守護(hù)程序抄谐，保證系統(tǒng)中總有一定數(shù)量的空頁(yè)框渺鹦；頁(yè)緩沖技術(shù)，不丟棄置換頁(yè)而是加入修改頁(yè)鏈表中斯稳，定期批量寫(xiě)回磁盤(pán)
26. 頁(yè)面置換算法：OPT（未來(lái)最遠(yuǎn)使用）海铆、NRU（LRU的粗略近似）、FIFO（先進(jìn)先出）挣惰、第二次機(jī)會(huì)（第一次先放隊(duì)尾）卧斟、時(shí)鐘（在環(huán)上移動(dòng)指針）、LRU（優(yōu)秀開(kāi)銷(xiāo)大）憎茂、老化（左置右移）珍语、工作集（保持活躍頁(yè)面的集合）
27. 影響缺頁(yè)次數(shù)：置換（磁盤(pán)調(diào)度頁(yè)面比運(yùn)行時(shí)間多產(chǎn)生顛簸），頁(yè)面大惺！（最優(yōu)值為2倍的程序規(guī)模乘頁(yè)表項(xiàng)再開(kāi)根）板乙，程序編制方法（多維數(shù)組），駐留集（平衡點(diǎn)）
28. Belady現(xiàn)象：FIFO算法拳氢，駐留集增大募逞，缺頁(yè)率可能反而增加
29. 內(nèi)存映射文件：用系統(tǒng)調(diào)用將文件映射到虛擬地址空間，訪問(wèn)文件就像訪問(wèn)大數(shù)組
30. 寫(xiě)時(shí)復(fù)制：父進(jìn)程創(chuàng)建子進(jìn)程后共享一塊標(biāo)記為寫(xiě)時(shí)復(fù)制的虛擬空間馋评，當(dāng)子進(jìn)程執(zhí)行自己代碼數(shù)據(jù)時(shí)放接，操作系統(tǒng)為其分配新的空間

文件系統(tǒng)

1. 文件：標(biāo)識(shí)為文件名，對(duì)用戶(hù)而言有完整的邏輯含義留特，對(duì)操作系統(tǒng)而言是信息項(xiàng)的序列
2. 文件系統(tǒng)：管理磁盤(pán)空間纠脾，實(shí)現(xiàn)按名存取（名字空間到磁盤(pán)空間的轉(zhuǎn)換）蜕青，共享及保護(hù)苟蹈，向用戶(hù)和I/O提供接口
3. 文件分類(lèi)：普通文件（包含用戶(hù)信息的ASCII或二進(jìn)制文件）、目錄文件（管理文件系統(tǒng)的系統(tǒng)文件）右核、特殊文件（字符／塊設(shè)備）慧脱、管道文件、套接字
4. 邏輯結(jié)構(gòu)：流式文件（字符）贺喝、記錄式文件（記錄）
5. 蔟：信息存儲(chǔ)菱鸥、分配、傳輸?shù)莫?dú)立物理塊單元
6. 磁盤(pán)結(jié)構(gòu)：物理地址由磁頭／盤(pán)面號(hào)搜变、磁道／柱面號(hào)、扇區(qū)號(hào)構(gòu)成针炉；扇區(qū)包括10B標(biāo)題挠他、512B數(shù)據(jù)、12~16B的ECC糾錯(cuò)信息
7. 磁盤(pán)中文件相關(guān)數(shù)據(jù)結(jié)構(gòu)：位圖（設(shè)置0/1）篡帕、空閑塊表（起始?jí)K號(hào)和空閑長(zhǎng)度）殖侵、空閑塊鏈表（每個(gè)節(jié)點(diǎn)含下一個(gè)指針）贸呢、成組鏈接法（從專(zhuān)用塊出發(fā)，每組首個(gè)空閑塊記錄下組的空閑塊號(hào)和塊數(shù)）
8. 文件控制塊FCB：包含管理文件所需的文件屬性或元數(shù)據(jù)拢军，包括名字楞陷、時(shí)間、地址茉唉、標(biāo)志等
9. 文件目錄：統(tǒng)一管理每個(gè)文件的元數(shù)據(jù)固蛾，完成名字到地址轉(zhuǎn)換；文件目錄以目錄文件的形式存儲(chǔ)在磁盤(pán)度陆；目錄項(xiàng)是FCB
10. 物理結(jié)構(gòu)：順序結(jié)構(gòu)艾凯、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)（存放索引表的索引塊地址放在FBC中）
11. 索引表的組織：索引表很大懂傀，需要多個(gè)物理快存儲(chǔ)時(shí)趾诗，可采用鏈接方式鏈接多個(gè)塊、上級(jí)索引表每個(gè)表項(xiàng)放置下級(jí)索引表地址的多級(jí)索引蹬蚁、或兩者結(jié)合的綜合模式
12. 文件卷：磁盤(pán)邏輯分區(qū)恃泪，由一個(gè)或多個(gè)蔟組成，包含2的整數(shù)次冪個(gè)扇區(qū)犀斋；格式化就是在文件卷上初始化元數(shù)據(jù)贝乎，建立文件系統(tǒng)
13. 分區(qū)內(nèi)容：引導(dǎo)區(qū)（引導(dǎo)操作系統(tǒng)所需信息，第一扇區(qū)）闪水、卷信息（總蔟數(shù)糕非、空閑蔟數(shù)和指針、空閑FCP數(shù)量和指針等）球榆、目錄文件（根目錄及其他目錄文件）朽肥、用戶(hù)文件
14. Unix文件系統(tǒng)布局：引導(dǎo)區(qū)、超級(jí)數(shù)據(jù)塊（文件系統(tǒng)結(jié)構(gòu)信息）持钉、空閑區(qū)管理（空閑表或相關(guān)結(jié)構(gòu)）衡招、i節(jié)點(diǎn)區(qū)、根目錄區(qū)
15. Windows中FAT系統(tǒng)布局：引導(dǎo)區(qū)（文件系統(tǒng)數(shù)據(jù)記錄）每强、文件分配表1（蔟的分配狀態(tài)始腾、標(biāo)注下一簇）、文件分配表2（1的鏡像）空执、根目錄浪箭、其他目錄和文件
16. 內(nèi)存中文件相關(guān)數(shù)據(jù)結(jié)構(gòu)：系統(tǒng)打開(kāi)文件表，整個(gè)系統(tǒng)一張辨绊，包括FCB（i節(jié)點(diǎn)）信息奶栖、引用計(jì)數(shù)、修改標(biāo)記；用戶(hù)打開(kāi)文件表宣鄙，保存在每個(gè)進(jìn)程的PCB中袍镀，包括文件描述符、打開(kāi)方式冻晤、讀寫(xiě)指針苇羡、系統(tǒng)打開(kāi)文件表索引
17. 目錄項(xiàng)分解：把FCB分為2部分，符號(hào)目錄項(xiàng)（文件名鼻弧、文件號(hào)）和基本目錄項(xiàng)（除文件名外所有字段设江，描述文件相關(guān)信息）；Unix中FCB=目錄項(xiàng)+i節(jié)點(diǎn)温数，每個(gè)文件由目錄項(xiàng)绣硝、i節(jié)點(diǎn)、若干磁盤(pán)塊構(gòu)成
18. Unix文件查找/a/b/c：超級(jí)數(shù)據(jù)塊中得到根目錄文件地址撑刺，根目錄文件中得到a的i節(jié)點(diǎn)地址鹉胖，a的i節(jié)點(diǎn)中得到a目錄文件地址，a目錄文件中得到b的i節(jié)點(diǎn)地址够傍，b的i節(jié)點(diǎn)中得到b目錄文件地址甫菠，b目錄文件中得到c的i節(jié)點(diǎn)地址，c的i節(jié)點(diǎn)中得到文件物理地址
19. FAT文件系統(tǒng)：按FAT表項(xiàng)字節(jié)數(shù)分為FAT12冕屯、FAT16寂诱、FAT32；FAT16根目錄大小固定安聘，不支持Unicode痰洒；目錄項(xiàng)都為32B，包含文件屬性和起始蔟號(hào)
20. 文件分配表FAT：可看作整數(shù)數(shù)組浴韭，每個(gè)整數(shù)代表磁盤(pán)分區(qū)的一個(gè)蔟號(hào)丘喻，記錄狀態(tài)和下一組蔟號(hào)
21. 解決長(zhǎng)文件名：使用不固定長(zhǎng)度的目錄項(xiàng)，添加長(zhǎng)度和結(jié)束標(biāo)志念颈；名字統(tǒng)一在堆存放泉粉，目錄項(xiàng)中包含指向堆內(nèi)的指針；FAT32的每個(gè)長(zhǎng)目錄項(xiàng)可保存13字符榴芳，長(zhǎng)目錄項(xiàng)前必須有一個(gè)普通的短目錄項(xiàng)
22. 文件操作：創(chuàng)建（建FCB嗡靡，分配存儲(chǔ)空間）；打開(kāi)（找目錄項(xiàng)窟感，更新共享計(jì)數(shù)讨彼，獲取文件描述符）；指針定位（fd查用戶(hù)打開(kāi)文件表找表項(xiàng)柿祈，設(shè)置讀寫(xiě)指針）哈误；讀文件（由文件描述符找FCB酣难，轉(zhuǎn)換為物理塊，申請(qǐng)緩沖區(qū)黑滴，進(jìn)行I/O）；重命名（修改FCB中的名字）
23. 一致性：磁盤(pán)塊寫(xiě)回內(nèi)存前出現(xiàn)故障紧索，元數(shù)據(jù)一致性被破壞袁辈；Unix中用兩個(gè)表記錄使用中的塊和空閑塊，對(duì)比修復(fù)一致性
24. 寫(xiě)入策略：同時(shí)考慮速度和一致性珠漂；通寫(xiě)晚缩、延遲寫(xiě)、可恢復(fù)寫(xiě)（日志媳危，如NTFS荞彼、ext3）
25. 訪問(wèn)控制：訪問(wèn)控制表（每個(gè)文件能被哪些用戶(hù)操作），能力表（每個(gè)用戶(hù)能操作哪些文件）待笑；用戶(hù)（owner鸣皂、group、other）暮蹂，操作（r寞缝、w、x仰泻、-）
26. 提高性能：目錄項(xiàng)分解荆陆、當(dāng)前目錄、磁盤(pán)碎片整理集侯、塊高速緩存（一式三份存在于磁盤(pán)被啼、內(nèi)存、緩存）棠枉、提前讀取浓体、合理分配磁盤(pán)空間（FCB與蔟同組）、磁盤(pán)調(diào)度术健、信息的優(yōu)化分布（磁道排列方式）汹碱、記錄的成組與分解（若干邏輯記錄組成一塊）、RAID等
27. 磁盤(pán)調(diào)度算法：FCFS荞估、最短尋道時(shí)間優(yōu)先咳促、SCAN（電梯）、C-SCAN（總是從0號(hào)向內(nèi)）勘伺、N-step-SCAN（每次服務(wù)n長(zhǎng)子隊(duì)列）跪腹、FSCAN（兩個(gè)隊(duì)列，新請(qǐng)求入另一個(gè)隊(duì)列）飞醉、旋轉(zhuǎn)調(diào)度（旋轉(zhuǎn)延遲）
28. RAID：獨(dú)立磁盤(pán)冗余矩陣冲茸，文件卷跨盤(pán)屯阀，用數(shù)據(jù)分條（如RAID0）并行I/O提高性能、用鏡像（如RAID1）和校驗(yàn)（如RAID4）提供容錯(cuò)

I/O系統(tǒng)

1. I/O管理：建立設(shè)備和內(nèi)存間的數(shù)據(jù)通道轴术，從應(yīng)用程序或文件系統(tǒng)獲得請(qǐng)求难衰，交由設(shè)備硬件響應(yīng)，過(guò)程由CPU控制
2. 設(shè)備分類(lèi)：塊設(shè)備（以塊尋址）逗栽、字符設(shè)備（速率低）盖袭；獨(dú)享設(shè)備（單進(jìn)程使用，可靜態(tài)或動(dòng)態(tài)分配）彼宠、共享設(shè)備（多進(jìn)程排隊(duì)分時(shí)共享）鳄虱、虛設(shè)備（共享設(shè)備模擬的獨(dú)占設(shè)備，如Spooling技術(shù)）
3. 管理目標(biāo)：按照用戶(hù)請(qǐng)求凭峡，控制設(shè)備完成與內(nèi)存間的數(shù)據(jù)交換拙已；建立方便、統(tǒng)一的獨(dú)立于設(shè)備的接口摧冀；提高CPU與設(shè)備倍踪、設(shè)備與設(shè)備的并行工作能力；保護(hù)數(shù)據(jù)的安全性索昂、完整性惭适、保密性
4. 硬件組成：機(jī)械部分是設(shè)備本身，物理裝置楼镐；電子部分是設(shè)備控制器癞志，完成端口編址、信號(hào)處理框产、緩沖
5. I/O地址：獨(dú)立編址凄杯，端口與內(nèi)存地址空間完全獨(dú)立，分配給I/O地址空間很少秉宿，操作不靈活戒突；內(nèi)存映像編址，將I/O端口看作存儲(chǔ)單元描睦，與內(nèi)存空間統(tǒng)一編址膊存，不能對(duì)控制寄存器高速緩存
6. 控制方式：可編程（輪詢(xún)，CPU忙等待）忱叭、中斷驅(qū)動(dòng)（操作結(jié)束后用中斷主動(dòng)通知驅(qū)動(dòng)）隔崎、DMA（直接存儲(chǔ)器訪問(wèn)，不通過(guò)CPU）
7. I/O演化：CPU控制->輪詢(xún)->中斷->DMA->單獨(dú)的處理器->擁有局部存儲(chǔ)器（本身已是計(jì)算機(jī)）
8. 軟件層次：用戶(hù)進(jìn)程I/O（用戶(hù)層執(zhí)行輸入輸出系統(tǒng)調(diào)用韵丑，準(zhǔn)備假脫機(jī)）爵卒、邏輯I/O（驅(qū)動(dòng)程序的統(tǒng)一接口，錯(cuò)誤報(bào)告撵彻，緩沖钓株，分配和釋放設(shè)備）实牡、設(shè)備驅(qū)動(dòng)程序（設(shè)置寄存器，檢查執(zhí)行狀態(tài)）轴合、中斷處理程序（完成后喚醒設(shè)備驅(qū)動(dòng)）
9. 設(shè)備獨(dú)立性：用戶(hù)編寫(xiě)程序時(shí)使用邏輯設(shè)備名创坞，由系統(tǒng)實(shí)現(xiàn)邏輯設(shè)備到物理設(shè)備的映射；操作系統(tǒng)設(shè)計(jì)I/O軟件時(shí)受葛，除直接與設(shè)備打交道的底層軟件外不依賴(lài)于硬件摆霉；設(shè)備分配靈活，易于實(shí)現(xiàn)I/O重定向
10. 緩沖技術(shù)：解決到達(dá)與離開(kāi)速度不匹配的問(wèn)題奔坟，提高CPU與I/O設(shè)備的并行性；按緩沖區(qū)位置有硬緩沖搭盾、軟緩沖咳秉，按緩沖池個(gè)數(shù)有單緩沖、雙緩沖鸯隅、緩沖池
11. 緩沖區(qū)：由緩沖控制塊和緩沖數(shù)據(jù)區(qū)組成澜建，相關(guān)數(shù)據(jù)結(jié)構(gòu)有空閑緩沖區(qū)隊(duì)列av鏈和設(shè)備緩沖隊(duì)列b鏈；開(kāi)始時(shí)在av鏈蝌以，開(kāi)始I/O請(qǐng)求時(shí)在I/O請(qǐng)求隊(duì)列和b鏈炕舵，完成I/O后在av鏈和b鏈
12. 設(shè)備管理數(shù)據(jù)結(jié)構(gòu)：描述設(shè)備的表格、建立同類(lèi)資源的隊(duì)列跟畅、面向I/O進(jìn)程的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)咽筋、建立I/O的隊(duì)列
13. 驅(qū)動(dòng)程序：每個(gè)設(shè)備驅(qū)動(dòng)程序管理一類(lèi)設(shè)備，從上層接受并釋放命令徊件，監(jiān)督執(zhí)行時(shí)可讓進(jìn)程等待也可以不等待奸攻；與操作系統(tǒng)、用于初始化的系統(tǒng)引導(dǎo)虱痕、設(shè)備都有接口
14. I/O進(jìn)程：系統(tǒng)級(jí)進(jìn)程睹耐，優(yōu)先級(jí)高；對(duì)于I/O請(qǐng)求部翘，用戶(hù)通過(guò)send發(fā)送給I/O進(jìn)程硝训，阻塞自己直到I/O完成并被喚醒，操作系統(tǒng)通過(guò)wakeup喚醒I/O進(jìn)程新思，完成時(shí)用戶(hù)要求的任務(wù)窖梁；對(duì)于I/O中斷，操作系統(tǒng)判斷為正常中斷則交給I/O進(jìn)程夹囚，異常則交給錯(cuò)誤處理程序
15. 提高性能：緩沖（減少CPU和I/O的速度差距）窄绒、異步I/O（等待I/O期間CPU可進(jìn)行其他操作）、DMA（CPU擺脫I/O）

死鎖

1. 死鎖：每個(gè)進(jìn)程無(wú)限等待被該組進(jìn)程中另一進(jìn)程占有的資源崔兴；與之對(duì)比彰导，活鎖為先加鎖再輪詢(xún)不阻塞不推進(jìn)蛔翅，饑餓是由于資源分配策略如優(yōu)先級(jí)導(dǎo)致得不到資源
2. 死鎖條件：互斥使用（資源獨(dú)占），占有且等待（部分分配）位谋，不可搶占（不可剝奪）山析，循環(huán)等待（進(jìn)程等待環(huán)路）
3. 資源分配圖：進(jìn)程是圓，資源類(lèi)是方掏父，資源實(shí)例是方框中黑點(diǎn)笋轨；申請(qǐng)邊（進(jìn)程鄙信，資源類(lèi)）表示進(jìn)程請(qǐng)求某類(lèi)資源躯畴，分配邊（資源實(shí)例，進(jìn)程）表示資源分配給某進(jìn)程
4. 死鎖定理：在資源分配圖中钢悲，無(wú)環(huán)路必?zé)o死鎖陶缺，有環(huán)路可能有死鎖钾挟，有環(huán)且資源類(lèi)只包含一個(gè)實(shí)例必有死鎖
5. 資源分配圖簡(jiǎn)化：找只有分配邊的資源，去掉邊分配給需要的進(jìn)程饱岸，自己變成孤點(diǎn)掺出；重復(fù)上述步驟，若最后所有都是孤點(diǎn)則無(wú)死鎖苫费，否則有死鎖
6. 解決死鎖：鴕鳥(niǎo)算法（不考慮死鎖）汤锨、死鎖預(yù)防（靜態(tài)分配）、死鎖避免（動(dòng)態(tài)評(píng)估）百框、死鎖檢測(cè)和解除
7. 死鎖預(yù)防：破壞死鎖必要條件闲礼；獨(dú)占轉(zhuǎn)為共享資源，一次性申請(qǐng)和分配铐维、主動(dòng)釋放部分分配位仁，操作系統(tǒng)幫助搶占，資源有序分配法（資源按熱度編號(hào)方椎，進(jìn)程按資源號(hào)增序請(qǐng)求）
8. 死鎖避免：對(duì)進(jìn)程發(fā)出的每一個(gè)能滿(mǎn)足的資源申請(qǐng)進(jìn)行動(dòng)態(tài)檢查聂抢，根據(jù)分配后系統(tǒng)是否為不安全狀態(tài)（死鎖）決定是否分配
9. 安全序列：進(jìn)程序列中任意進(jìn)程，它還需要的資源不超過(guò)當(dāng)前系統(tǒng)剩余資源與它之前的所有進(jìn)程占有資源的和棠众；此時(shí)系統(tǒng)為安全狀態(tài)琳疏，一定無(wú)死鎖，若不存在任何安全序列則為不安全狀態(tài)闸拿，一定導(dǎo)致死鎖
10. 銀行家算法：五類(lèi)數(shù)組available, max[i], allocation[i], need[i], request[i]空盼；當(dāng)進(jìn)程i提出request[i]時(shí)，若不大于available則將allocation[i]加request[i]新荤、available和need[i]減request[i]揽趾，此時(shí)判斷新?tīng)顟B(tài)是否安全，安全則分配否則等待
11. 死鎖檢測(cè)：允許死鎖發(fā)生苛骨，在資源不足篱瞎、利用率下降時(shí)或周期性檢測(cè)系統(tǒng)進(jìn)展判斷是否真的有死鎖發(fā)生苟呐；死鎖后解除死鎖并以最小的代價(jià)恢復(fù)系統(tǒng)運(yùn)行，可通過(guò)撤銷(xiāo)死鎖進(jìn)程組俐筋、回退再啟動(dòng)牵素、按某種原則逐一撤銷(xiāo)進(jìn)程或剝奪資源
12. 哲學(xué)家就餐：同步互斥問(wèn)題，五個(gè)哲學(xué)家日常行為是思考澄者，兩兩間放一只筷子笆呆，饑餓時(shí)要從左右取兩只筷子才可吃飯，都先拿右邊筷子時(shí)出現(xiàn)死鎖粱挡；解決方法包括最多允許四個(gè)哲學(xué)家赠幕、利用管程一次性拿兩只筷子、設(shè)置哲學(xué)家的三種狀態(tài)結(jié)合檢測(cè)和PV操作询筏、每個(gè)哲學(xué)家按筷子增序拿榕堰、由銀行家算法將最后的筷子分配給已拿到一只的人