（不定期更新）
操作系統(tǒng)概述
操作系統(tǒng)的四個(gè)特性
并發(fā)：同時(shí)存在多個(gè)運(yùn)行的程序，
共享：系統(tǒng)中資源供多個(gè)并發(fā)進(jìn)程同時(shí)使用。
虛擬：處理器分時(shí)共享，虛擬存儲(chǔ)器等械馆。
異步：多道導(dǎo)致程序以不可預(yù)知的速度向前推進(jìn)。
操作系統(tǒng)提供的服務(wù)
進(jìn)程管理武通，文件管理霹崎，存儲(chǔ)管理，輸入輸出設(shè)備管理
中斷和系統(tǒng)調(diào)用
中斷：計(jì)算機(jī)在執(zhí)行程序過程中冶忱，由于出現(xiàn)了某些特殊事情尾菇，CPU暫停當(dāng)前程序的執(zhí)行，轉(zhuǎn)而去處理這一事件囚枪。
系統(tǒng)調(diào)用：用戶在程序中調(diào)用操作系統(tǒng)所提供的一些子功能派诬。
用戶自編程序運(yùn)行在用戶態(tài)，操作系統(tǒng)內(nèi)核程序運(yùn)行在內(nèi)核態(tài)链沼。從用戶態(tài)進(jìn)入核心態(tài)就是通過中斷和異常實(shí)現(xiàn)的默赂。
進(jìn)程管理
進(jìn)程的狀態(tài)與轉(zhuǎn)換
- 就緒 -> 運(yùn)行：處于就緒態(tài)的進(jìn)程被調(diào)度，獲得處理機(jī)資源（分派處理機(jī)時(shí)間片）括勺。
- 運(yùn)行 -> 就緒：運(yùn)行時(shí)間片到或有更高優(yōu)先級(jí)的進(jìn)程就緒缆八。
- 運(yùn)行 -> 阻塞：當(dāng)進(jìn)程請(qǐng)求某一資源（如外設(shè)）的使用和分配或等待某一事件的發(fā)生（如I/O操作完成）時(shí)。
- 阻塞 -> 就緒：進(jìn)程等待的事件到來疾捍，中斷處理程序把相應(yīng)的進(jìn)程狀態(tài)由阻塞態(tài)轉(zhuǎn)為就緒態(tài)耀里。
進(jìn)程和線程的區(qū)別
進(jìn)程：是進(jìn)程實(shí)體的一次運(yùn)行，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位拾氓。引入進(jìn)程是為了使多個(gè)程序可以并發(fā)執(zhí)行。
線程：是比進(jìn)程更小的獨(dú)立運(yùn)行的基本單位底哥，可以看做輕量級(jí)的進(jìn)程（具有輕型實(shí)體咙鞍、獨(dú)立調(diào)度分派單位，可并發(fā)執(zhí)行趾徽，共享進(jìn)程資源等屬性）引入目的是為了減少程序在并發(fā)執(zhí)行過程中的開銷续滋。
對(duì)比
- 調(diào)度方面：線程是獨(dú)立的調(diào)度和分派單位，而進(jìn)程是資源的擁有單位孵奶。由于線程不擁有資源疲酌，因此可以顯著提高并發(fā)度及減小切換開銷。
- 并發(fā)性：進(jìn)程間可以并發(fā)，一個(gè)進(jìn)程內(nèi)多個(gè)線程也可以并發(fā)朗恳。
- 系統(tǒng)開銷：創(chuàng)建或撤銷進(jìn)程時(shí)湿颅，系統(tǒng)要為之創(chuàng)建或回收PCB、系統(tǒng)資源等粥诫，切換時(shí)也需要保存和恢復(fù)CPU環(huán)境油航。二線程的切換至需要保存和恢復(fù)少量的寄存器，開銷較小怀浆。
- 通信方面：進(jìn)程間通信需要IPC谊囚，而同一進(jìn)程的多個(gè)線程由于共享地址空間，可直接讀取進(jìn)程數(shù)據(jù)段（如全局變量）來通信执赡。
進(jìn)程通信
共享存儲(chǔ)
低級(jí)方式是基于數(shù)據(jù)結(jié)構(gòu)的共享镰踏，高級(jí)方式是基于存儲(chǔ)區(qū)的共享。需要使用同步互斥工具（如P操作沙合、V操作）對(duì)共享空間進(jìn)行讀寫控制奠伪。
消息傳遞
直接通信方式：直接把消息掛到接收進(jìn)程的消息隊(duì)列
間接通信方式：掛到某個(gè)中間實(shí)體，接收進(jìn)程找到實(shí)體接收消息灌诅，類似電子郵件芳来。
管道通信
利用一種特殊的pipe文件連接兩個(gè)進(jìn)程。
進(jìn)程調(diào)度
調(diào)度原因：合理處理計(jì)算機(jī)軟硬件資源猜拾。
- 先來先服務(wù)FCFS
- 短作業(yè)優(yōu)先
- 高響應(yīng)比優(yōu)先：響應(yīng)比 = （等待時(shí)間 + 要求服務(wù)時(shí)間）/ 要求服務(wù)時(shí)間
- 時(shí)間片輪轉(zhuǎn)調(diào)度RR
- 多級(jí)反饋隊(duì)列調(diào)度：時(shí)間片輪轉(zhuǎn)調(diào)度算法和優(yōu)先級(jí)調(diào)度算法的綜合和發(fā)展即舌。
設(shè)置多個(gè)就緒隊(duì)列并為每個(gè)隊(duì)列設(shè)置不同的優(yōu)先級(jí)，第一個(gè)隊(duì)列優(yōu)先級(jí)最高挎袜，其余依次遞減顽聂。優(yōu)先級(jí)越高的隊(duì)列分配的時(shí)間片越短，進(jìn)程到達(dá)之后按FCFS放入第一個(gè)隊(duì)列盯仪，如果調(diào)度執(zhí)行后沒有完成紊搪，那么放到第二個(gè)隊(duì)列尾部等待調(diào)度，如果第二次調(diào)度仍然沒有完成全景，放入第三隊(duì)列尾部…耀石。只有當(dāng)前一個(gè)隊(duì)列為空的時(shí)候才會(huì)去調(diào)度下一個(gè)隊(duì)列的進(jìn)程。
進(jìn)程同步
同步原則
- 空閑讓進(jìn)
- 忙則等待
- 有限等待：對(duì)要求訪問臨界資源的進(jìn)程爸黄，需要在有限時(shí)間內(nèi)進(jìn)入臨界區(qū)滞伟，防止死等。
- 讓權(quán)等待：當(dāng)進(jìn)程無法進(jìn)入臨界區(qū)時(shí)炕贵，需要釋放處理機(jī)梆奈，防止忙等。
同步解決方案
信號(hào)量：利用PV操作實(shí)現(xiàn)互斥称开。
管程：由一組數(shù)據(jù)及定義在這組數(shù)據(jù)之上的對(duì)這組數(shù)據(jù)的操作組成的軟件模塊亩钟。
經(jīng)典的進(jìn)程同步問題
- 生產(chǎn)者-消費(fèi)者問題
- 哲學(xué)家就餐
- 讀者-寫者問題
死鎖
產(chǎn)生原因：非剝奪資源的競(jìng)爭(zhēng)和進(jìn)程的不恰當(dāng)推進(jìn)順序乓梨。
死鎖產(chǎn)生四個(gè)條件：互斥條件，請(qǐng)求和保持條件清酥，不可剝奪條件扶镀，環(huán)路等待條件。
死鎖處理
- 預(yù)防死鎖：破壞產(chǎn)生死鎖的4個(gè)必要條件中的一個(gè)或者多個(gè)总处。
- 避免死鎖：防止系統(tǒng)進(jìn)入不安全狀態(tài)(可能產(chǎn)生死鎖的狀態(tài))狈惫，如銀行家算法。
- 檢測(cè)死鎖：利用死鎖定理化簡(jiǎn)資源分配圖以檢測(cè)死鎖存在鹦马。
- 解除死鎖：資源剝奪法胧谈，撤銷進(jìn)程法，進(jìn)程回退法荸频。
內(nèi)存管理
連續(xù)分配
單一連續(xù)分配
分配到內(nèi)存固定區(qū)域菱肖，只適合單任務(wù)系統(tǒng)。
固定分區(qū)分配
分配到內(nèi)存不同固定區(qū)域旭从，分區(qū)可以相等也可以不等稳强。
動(dòng)態(tài)分區(qū)分配
- 首次適應(yīng)(First Fit)：按地址從小到大為序，分配第一個(gè)符合條件的分區(qū)和悦。
- 最佳適應(yīng)(Best Fit)：按空間從小到大為序退疫，分配第一個(gè)符合條件的分區(qū)。
- 最壞適應(yīng)(Worst Fit)：按地址從大到小為序鸽素，分配第一個(gè)符合條件的分區(qū)褒繁。
- 臨近適應(yīng)：與首次適應(yīng)相似，從上次查完的位置開始找馍忽。
非連續(xù)分配
基本分頁
要一個(gè)頁表來記錄邏輯地址和實(shí)際存儲(chǔ)地址之間的映射關(guān)系棒坏，以實(shí)現(xiàn)從頁號(hào)到物理塊號(hào)的映射。
分頁管理引入了快表機(jī)制
分頁管理還可以采用兩級(jí)頁表或多級(jí)頁表的方法遭笋。
基本分段
分段是為了滿足程序員在編寫代碼的時(shí)候的一些邏輯需求(比如數(shù)據(jù)共享坝冕，數(shù)據(jù)保護(hù)，動(dòng)態(tài)鏈接等)
對(duì)比：頁是信息的物理單位瓦呼，是出于系統(tǒng)內(nèi)存利用率的角度提出的喂窟；段是信息的邏輯單位，是出于用戶角度提出的央串。頁的大小是固定的谎替，由系統(tǒng)決定；段的大小是不確定的蹋辅，由用戶決定。
段頁式
基本分段和基本分頁的結(jié)合
虛擬內(nèi)存
在程序裝入時(shí)挫掏，可以將程序的一部分裝入內(nèi)存侦另，而將其余部分留在外存，就可以啟動(dòng)程序執(zhí)行。在程序執(zhí)行過程中褒傅，當(dāng)所訪問的信息不在內(nèi)存時(shí)弃锐，由操作系統(tǒng)將所需要的部分調(diào)入內(nèi)存,然后繼續(xù)執(zhí)行程序。
操作系統(tǒng)將內(nèi)存中暫時(shí)不使用的內(nèi)容換出到外存上殿托，從而騰出空間存放將要調(diào)入內(nèi)存的信息霹菊。這樣，系統(tǒng)好像為用戶提供了一個(gè)比實(shí)際內(nèi)存大得多的存儲(chǔ)器支竹，稱為虛擬存儲(chǔ)器旋廷。
置換算法
- 最佳置換算法（OPT）：選擇以后不用的頁面換出。只具有理論意義礼搁，用來評(píng)價(jià)其他置換算法饶碘。
- 先進(jìn)先出算法（FIFO）：每次淘汰最早調(diào)入的頁面。
- 最近最久未使用算法（LRU）
- Clock算法：頁面設(shè)置一個(gè)訪問位馒吴，并將頁面鏈接為一個(gè)環(huán)形隊(duì)列扎运，頁面被訪問的時(shí)候訪問位設(shè)置為1。如果當(dāng)前指針?biāo)疙撁嬖L問為為0饮戳，那么置換豪治，否則將其置為0。
- 改進(jìn)型Clock算法：在Clock算法的基礎(chǔ)上添加一個(gè)修改位扯罐。
