點(diǎn)擊上方藍(lán)色字體，選擇“標(biāo)星公眾號(hào)”
優(yōu)質(zhì)文章，第一時(shí)間送達(dá)
一、操作系統(tǒng)簡介：
1、什么是操作系統(tǒng)：
操作系統(tǒng)本質(zhì)上是一個(gè)運(yùn)行在計(jì)算機(jī)上的軟件程序 ，管理著計(jì)算機(jī)硬件和軟件資源，為計(jì)算機(jī)硬件和軟件提供了一種中間層，使應(yīng)用軟件和硬件進(jìn)行分離，屏蔽了硬件層的復(fù)雜性，讓我們把關(guān)注點(diǎn)更多放在軟件應(yīng)用上。操作系統(tǒng)的主要功能有：
（1）進(jìn)程管理：進(jìn)程管理的主要作用就是任務(wù)調(diào)度，以及進(jìn)程的創(chuàng)建銷毀、阻塞喚醒、進(jìn)程同步、進(jìn)程通信、死鎖處理等功能。
（2）內(nèi)存管理：內(nèi)存分配與回收、地址映射、虛擬內(nèi)存以及頁面的置換
（3）文件管理：有效地管理文件的存儲(chǔ)空間，合理地組織和管理文件系統(tǒng)，為文件訪問和文件保護(hù)提供更有效的方法及手段。
（4）設(shè)備管理：根據(jù)確定的設(shè)備分配原則對(duì)設(shè)備進(jìn)行分配，使設(shè)備與主機(jī)能夠并行工作，為用戶提供良好的設(shè)備使用界面。
2、什么是用戶態(tài)和內(nèi)核態(tài)：
用戶態(tài)和系統(tǒng)態(tài)是操作系統(tǒng)的兩種運(yùn)行狀態(tài)：
內(nèi)核態(tài)：內(nèi)核態(tài)運(yùn)行的程序可以訪問計(jì)算機(jī)的任何數(shù)據(jù)和資源，不受限制，包括外圍設(shè)備，比如網(wǎng)卡、硬盤等。處于內(nèi)核態(tài)的 CPU 可以從一個(gè)程序切換到另外一個(gè)程序，并且占用 CPU 不會(huì)發(fā)生搶占情況。
用戶態(tài)：用戶態(tài)運(yùn)行的程序只能受限地訪問內(nèi)存，只能直接讀取用戶程序的數(shù)據(jù)，并且不允許訪問外圍設(shè)備，用戶態(tài)下的 CPU 不允許獨(dú)占，也就是說 CPU 能夠被其他程序獲取。
將操作系統(tǒng)的運(yùn)行狀態(tài)分為用戶態(tài)和內(nèi)核態(tài)，主要是為了對(duì)訪問能力進(jìn)行限制，防止隨意進(jìn)行一些比較危險(xiǎn)的操作導(dǎo)致系統(tǒng)的崩潰，比如設(shè)置時(shí)鐘、內(nèi)存清理，這些都需要在內(nèi)核態(tài)下完成
二、進(jìn)程與線程：
1、進(jìn)程與線程的區(qū)別：
（1）一個(gè)程序至少有一個(gè)進(jìn)程，一個(gè)進(jìn)程至少有一個(gè)線程，線程是依賴于進(jìn)程存在的，線程是一個(gè)進(jìn)程中代碼的不同的執(zhí)行路線；
（2）進(jìn)程是對(duì)運(yùn)行時(shí)程序的封裝，是操作系統(tǒng)進(jìn)行資源調(diào)度和分配的最小單位，實(shí)現(xiàn)了操作系統(tǒng)的并發(fā)；線程是程序執(zhí)行的最小單位，是CPU調(diào)度和分派的基本的單位，實(shí)現(xiàn)進(jìn)程內(nèi)部的并發(fā)。
（3）資源與內(nèi)存空間：進(jìn)程是資源分配的基本單位，線程不擁有資源；進(jìn)程之間擁有相互獨(dú)立的內(nèi)存單位，但是同一個(gè)進(jìn)程下的各個(gè)線程之間共享程序的內(nèi)存空間，（包括代碼段、數(shù)據(jù)集、堆等)及一些進(jìn)程級(jí)的資源(如打開文件和信號(hào))，某進(jìn)程內(nèi)的線程在其它進(jìn)程不可見；
（4）系統(tǒng)開銷：創(chuàng)建或銷毀進(jìn)程時(shí)，系統(tǒng)都要為之分配或回收資源，如內(nèi)存空間、I/O 設(shè)備等；而線程只需要堆棧指針以及程序計(jì)數(shù)器就可以了，開銷遠(yuǎn)小于創(chuàng)建或撤銷進(jìn)程時(shí)的開銷。在進(jìn)行進(jìn)程切換時(shí)，涉及當(dāng)前執(zhí)行進(jìn)程 CPU 環(huán)境的保存及新調(diào)度進(jìn)程 CPU 環(huán)境的設(shè)置，而線程切換時(shí)只需保存和設(shè)置少量寄存器內(nèi)容，開銷很小。
（5）通信：線程間可以通過直接讀寫同一進(jìn)程中的數(shù)據(jù)進(jìn)行通信，但是進(jìn)程通信需要借助IPC。
2、進(jìn)程的五種狀態(tài)：
（1）創(chuàng)建狀態(tài)：進(jìn)程剛被創(chuàng)建，尚未進(jìn)入就緒隊(duì)列。創(chuàng)建進(jìn)程需要兩個(gè)步驟：即為新進(jìn)程分配所需要的資源和空間，設(shè)置進(jìn)程為就緒態(tài)，并等待調(diào)度執(zhí)行。
（2）就緒狀態(tài)：進(jìn)程已獲得除CPU以外的所需的一切資源，一旦得到CPU資源即可運(yùn)行；
（3）運(yùn)行狀態(tài)：進(jìn)程正在處理器上面運(yùn)行
（4）阻塞狀態(tài)：進(jìn)程正在等待某一事件而暫停運(yùn)行，如等待某資源或者等待 IO 操作完成，即使CPU 空閑，該進(jìn)程也不能運(yùn)行；
（5）終止?fàn)顟B(tài)：進(jìn)程達(dá)到正常結(jié)束點(diǎn)或因其他原因被終止，下一步將被撤銷。 終止一個(gè)進(jìn)程需要兩個(gè)步驟：先等待操作系統(tǒng)或相關(guān)的進(jìn)程進(jìn)行善后處理；然后回收占用的資源并被系統(tǒng)刪除。
只有就緒態(tài)和運(yùn)行態(tài)可以相互轉(zhuǎn)換，其它的都是單向轉(zhuǎn)換。就緒狀態(tài)的進(jìn)程通過調(diào)度算法從而獲得 CPU 時(shí)間，轉(zhuǎn)為運(yùn)行狀態(tài)；而運(yùn)行狀態(tài)的進(jìn)程，在分配給它的 CPU 時(shí)間片用完之后就會(huì)轉(zhuǎn)為就緒狀態(tài)，等待下一次調(diào)度。
阻塞狀態(tài)是缺少需要的資源從而由運(yùn)行狀態(tài)轉(zhuǎn)換而來，但是該資源不包括 CPU 時(shí)間，缺少 CPU 時(shí)間會(huì)從運(yùn)行態(tài)轉(zhuǎn)換為就緒態(tài)。
3、進(jìn)程的調(diào)度算法：
（1）先來先服務(wù)：按照請(qǐng)求的順序進(jìn)行調(diào)度，使用隊(duì)列實(shí)現(xiàn)。有利于長作業(yè)，但不利于短作業(yè)，因?yàn)槎套鳂I(yè)必須一直等待前面的長作業(yè)執(zhí)行完畢才能執(zhí)行，而長作業(yè)又需要執(zhí)行很長時(shí)間，造成了短作業(yè)等待時(shí)間過長。
（2）最短作業(yè)優(yōu)先：按照估計(jì)運(yùn)行時(shí)間最短的順序進(jìn)行調(diào)度。有利于短作業(yè)，但長作業(yè)有可能餓死，處于一直等待短作業(yè)執(zhí)行完畢的狀態(tài)，因?yàn)榭赡芤恢庇卸套鳂I(yè)到來，那么長作業(yè)永遠(yuǎn)得不到調(diào)度。
（3）最短剩余時(shí)間優(yōu)先：按估計(jì)剩余時(shí)間最短的順序進(jìn)行調(diào)度。
（4）時(shí)間片輪轉(zhuǎn)：將所有就緒進(jìn)程按 FCFS 的原則排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把 CPU 時(shí)間分配給隊(duì)首進(jìn)程，該進(jìn)程可以執(zhí)行一個(gè)時(shí)間片。當(dāng)時(shí)間片用完時(shí)，調(diào)度程序便停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾，同時(shí)繼續(xù)把 CPU 時(shí)間分配給隊(duì)首的進(jìn)程。
時(shí)間片輪轉(zhuǎn)算法的效率和時(shí)間片的大小有很大關(guān)系：因?yàn)檫M(jìn)程切換都要保存進(jìn)程的信息并且載入新進(jìn)程的信息，如果時(shí)間片太小，會(huì)導(dǎo)致進(jìn)程切換得太頻繁，在進(jìn)程切換上就會(huì)花過多時(shí)間。而如果時(shí)間片過長，那么實(shí)時(shí)性就不能得到保證。
（5）優(yōu)先級(jí)調(diào)度：為每個(gè)進(jìn)程分配一個(gè)優(yōu)先級(jí)，按優(yōu)先級(jí)進(jìn)行調(diào)度。為了防止低優(yōu)先級(jí)的進(jìn)程永遠(yuǎn)等不到調(diào)度，可以隨著時(shí)間的推移增加等待進(jìn)程的優(yōu)先級(jí)。
（6）多級(jí)反饋隊(duì)列調(diào)度算法：可以將這種調(diào)度算法看成是時(shí)間片輪轉(zhuǎn)調(diào)度算法和優(yōu)先級(jí)調(diào)度算法的結(jié)合。它設(shè)置了多個(gè)隊(duì)列，每個(gè)隊(duì)列時(shí)間片大小都不同，進(jìn)程在第一個(gè)隊(duì)列沒執(zhí)行完，就會(huì)被移到下一個(gè)隊(duì)列。
實(shí)施過程：
① 設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。在優(yōu)先權(quán)越高的隊(duì)列中，為每個(gè)進(jìn)程所規(guī)定的執(zhí)行時(shí)間片就越小。
② 當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先放入第一隊(duì)列的末尾，按FCFS原則排隊(duì)等候調(diào)度。如果他能在一個(gè)時(shí)間片中完成，便可撤離；如果未完成，就轉(zhuǎn)入第二隊(duì)列的末尾，在同樣等待調(diào)度…… 如此下去，當(dāng)一個(gè)長作業(yè)（進(jìn)程）從第一隊(duì)列依次將到第n隊(duì)列（最后隊(duì)列）后，便按第n隊(duì)列時(shí)間片輪轉(zhuǎn)運(yùn)行。
③ 僅當(dāng)?shù)谝魂?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行；僅當(dāng)?shù)?到第（i-1）隊(duì)列空時(shí)， 才會(huì)調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行，并執(zhí)行相應(yīng)的時(shí)間片輪轉(zhuǎn)。
④ 如果處理機(jī)正在處理第i隊(duì)列中某進(jìn)程，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列， 則此新隊(duì)列搶占正在運(yùn)行的處理機(jī)，并把正在運(yùn)行的進(jìn)程放在第i隊(duì)列的隊(duì)尾。
4、進(jìn)程的通信方式：
（1）匿名管道 pipe：用于具有親緣關(guān)系的進(jìn)程間的通信；
（2）有名管道 named pipe：可以用于無親緣關(guān)系的進(jìn)程間的通信，可以實(shí)現(xiàn)本機(jī)任意兩個(gè)進(jìn)程間的通信
（3）信號(hào) signal：用于通知和接收進(jìn)程某個(gè)事件已經(jīng)發(fā)生。
（4）消息隊(duì)列 Message Queuing ：消息隊(duì)列是消息的鏈表，具有特定的格式，存放在內(nèi)存中并由消息隊(duì)列標(biāo)識(shí)符標(biāo)識(shí)。消息隊(duì)列克服了信號(hào)傳遞信息量少，管道只能承載無格式字節(jié)流以及緩沖區(qū)大小受限等缺點(diǎn)。管道和消息隊(duì)列的通信數(shù)據(jù)都是先進(jìn)先出的原則，但消息隊(duì)列可以實(shí)現(xiàn)消息的隨機(jī)查詢,消息不一定要以先進(jìn)先出的次序讀取,也可以按消息的類型讀取，比 FIFO 更有優(yōu)勢。
（5）信號(hào)量 semophore：信號(hào)量是一個(gè)計(jì)數(shù)器，可以用來控制多個(gè)進(jìn)程對(duì)共享資源的訪問。意圖在于進(jìn)程間同步。這種通信方式主要用于解決與同步相關(guān)的問題并避免競爭條件。
（6）共享內(nèi)存 Shared memory：多個(gè)進(jìn)程可以訪問同一塊內(nèi)存空間，不同進(jìn)程可以及時(shí)看到對(duì)方進(jìn)程中對(duì)共享內(nèi)存中數(shù)據(jù)的更新。這種方式需要依靠某種同步操作，如互斥鎖和信號(hào)量等。它是針對(duì)其他進(jìn)程間通信方式運(yùn)行效率低而專門設(shè)計(jì)的。
（7）套接字 socket：與其他通信機(jī)制不同的是，socket 可用于不同機(jī)器間的進(jìn)程通信。套接字是支持 TCP/IP 的網(wǎng)絡(luò)通信的基本操作單元，可以看做是不同主機(jī)之間的進(jìn)程進(jìn)行雙向通信的端點(diǎn)。
5、線程的七種狀態(tài)：
在 JVM 中，可以將線程劃分為以下幾種狀態(tài)：創(chuàng)建(new)、就緒(runnable/start)、運(yùn)行(running)、阻塞(blocked)、等待(waiting)、時(shí)間等待(time waiting) 和 消亡(dead/terminated)。在某一時(shí)刻，一個(gè)線程只能處于一種狀態(tài)。
6、線程間同步的方式：
（1）臨界區(qū) CriticalSection：在任意時(shí)刻只允許一個(gè)線程對(duì)共享資源進(jìn)行訪問，如果有多個(gè)線程試圖訪問公共資源，那么在有一個(gè)線程進(jìn)入后，其他試圖訪問公共資源的線程將被掛起，并一直等到進(jìn)入臨界區(qū)的線程離開，臨界區(qū)在被釋放后，其他線程才可以搶占。
（2）互斥量 Mutex：采用互斥對(duì)象機(jī)制。只有擁有互斥對(duì)象的線程才有訪問公共資源的權(quán)限，因?yàn)榛コ鈱?duì)象只有一個(gè)，所以能保證公共資源不會(huì)同時(shí)被多個(gè)線程訪問。當(dāng)前擁有互斥對(duì)象的線程處理完任務(wù)后必須將線程交出，以便其他線程訪問該資源?；コ鈱?duì)象和臨界區(qū)對(duì)象非常相似，但是互斥量允許在進(jìn)程間使用，而臨界區(qū)只限制于同一進(jìn)程的各個(gè)線程之間使用，但是更節(jié)省資源，更有效率。
（3）信號(hào)量 semophore：信號(hào)量其實(shí)就是一個(gè)計(jì)數(shù)器，限制了同一時(shí)刻訪問同一資源的最大線程數(shù)。如果這個(gè)計(jì)數(shù)達(dá)到了零，則所有對(duì)這個(gè)Semaphore類對(duì)象所控制的資源的訪問嘗試都被放入到一個(gè)隊(duì)列中等待，直到超時(shí)或計(jì)數(shù)值不為零為止。
（4）事件 Event，wait/notify：事件機(jī)制，允許一個(gè)線程在處理完一個(gè)任務(wù)后，主動(dòng)喚醒另一個(gè)線程執(zhí)行任務(wù)，通過通知操作的方式來保持線程的同步。
三、死鎖：
在兩個(gè)或以上并發(fā)進(jìn)程中，如果每個(gè)進(jìn)程持有某種資源并且都等待別的進(jìn)程釋放它們保持著的資源，在未改變這種狀態(tài)之前都不能向前推進(jìn)，稱這一組進(jìn)程產(chǎn)生了死鎖，也就是多個(gè)進(jìn)程無限期的阻塞、相互等待的一種狀態(tài)。
1、死鎖的四個(gè)必要條件：
（1）互斥條件：一個(gè)資源每次只能被一個(gè)進(jìn)程使用。此時(shí)若有其他進(jìn)程請(qǐng)求該資源，則請(qǐng)求進(jìn)程只能等待。
（2）請(qǐng)求與保持條件：進(jìn)程已經(jīng)獲得了至少一個(gè)資源，但是又提出新的資源請(qǐng)求，而該資源已經(jīng)被其他進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程被阻塞，但對(duì)自己已獲得的資源保持不放。即當(dāng)一個(gè)進(jìn)程等待其他進(jìn)程是，繼續(xù)占有已經(jīng)分配的資源。
（3）不可剝奪條件：進(jìn)程所獲得的資源在未使用完畢之前，不能被其他進(jìn)程強(qiáng)行奪走，只能由獲得該資源的進(jìn)程釋放。
（4）循環(huán)等待條件：若干進(jìn)程間形成首尾相接的循環(huán)等待資源的關(guān)系。
2、處理死鎖的基本策略：
常用的處理死鎖的方法有：死鎖預(yù)防、死鎖避免、死鎖檢測、死鎖解除、鴕鳥策略。
（1）死鎖的預(yù)防：基本思想就是確保死鎖發(fā)生的四個(gè)必要條件中至少有一個(gè)不成立：
① 破除資源互斥條件
② 破除“請(qǐng)求與保持”條件：實(shí)行資源預(yù)分配策略，進(jìn)程在運(yùn)行之前，必須一次性獲取所有的資源。缺點(diǎn)：在很多情況下，無法預(yù)知進(jìn)程執(zhí)行前所需的全部資源，因?yàn)檫M(jìn)程是動(dòng)態(tài)執(zhí)行的，同時(shí)也會(huì)降低資源利用率，導(dǎo)致降低了進(jìn)程的并發(fā)性。
③ 破除“不可剝奪”條件：允許進(jìn)程強(qiáng)行從占有者那里奪取某些資源。當(dāng)一個(gè)已經(jīng)保持了某些不可被搶占資源的進(jìn)程，提出新的資源請(qǐng)求而不能得到滿足時(shí)，它必須釋放已經(jīng)保持的所有資源，待以后需要時(shí)再重新申請(qǐng)。這意味著進(jìn)程已經(jīng)占有的資源會(huì)被暫時(shí)被釋放，或者說被搶占了。
④ 破除“循環(huán)等待”條件：實(shí)行資源有序分配策略，對(duì)所有資源排序編號(hào)，按照順序獲取資源，將緊缺的，稀少的采用較大的編號(hào)，在申請(qǐng)資源時(shí)必須按照編號(hào)的順序進(jìn)行，一個(gè)進(jìn)程只有獲得較小編號(hào)的進(jìn)程才能申請(qǐng)較大編號(hào)的進(jìn)程。
（2）死鎖避免：
死鎖預(yù)防通過約束資源請(qǐng)求，防止4個(gè)必要條件中至少一個(gè)的發(fā)生，可以通過直接或間接預(yù)防方法，但是都會(huì)導(dǎo)致低效的資源使用和低效的進(jìn)程執(zhí)行。而死鎖避免則允許前三個(gè)必要條件，但是通過動(dòng)態(tài)地檢測資源分配狀態(tài)，以確保循環(huán)等待條件不成立，從而確保系統(tǒng)處于安全狀態(tài)。所謂安全狀態(tài)是指：如果系統(tǒng)能按某個(gè)順序?yàn)槊總€(gè)進(jìn)程分配資源（不超過其最大值），那么系統(tǒng)狀態(tài)是安全的，換句話說就是，如果存在一個(gè)安全序列，那么系統(tǒng)處于安全狀態(tài)。銀行家算法是經(jīng)典的死鎖避免的算法。
（3）死鎖檢測：
死鎖預(yù)防策略是非常保守的，他們通過限制訪問資源和在進(jìn)程上強(qiáng)加約束來解決死鎖的問題。死鎖檢測則是完全相反，它不限制資源訪問或約束進(jìn)程行為，只要有可能，被請(qǐng)求的資源就被授權(quán)給進(jìn)程。但是操作系統(tǒng)會(huì)周期性地執(zhí)行一個(gè)算法檢測前面的循環(huán)等待的條件。死鎖檢測算法是通過資源分配圖來檢測是否存在環(huán)來實(shí)現(xiàn)，從一個(gè)節(jié)點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索，對(duì)訪問過的節(jié)點(diǎn)進(jìn)行標(biāo)記，如果訪問了已經(jīng)標(biāo)記的節(jié)點(diǎn)，就表示有存在環(huán)，也就是檢測到死鎖的發(fā)生。
（1）如果進(jìn)程-資源分配圖中無環(huán)路，此時(shí)系統(tǒng)沒有死鎖。
（2）如果進(jìn)程-資源分配圖中有環(huán)路，且每個(gè)資源類中只有一個(gè)資源，則系統(tǒng)發(fā)生死鎖。
（3）如果進(jìn)程-資源分配圖中有環(huán)路，且所涉及的資源類有多個(gè)資源，則不一定會(huì)發(fā)生死鎖。
（4）死鎖解除：
死鎖解除的常用方法就是終止進(jìn)程和資源搶占，回滾。所謂進(jìn)程終止就是簡單地終止一個(gè)或多個(gè)進(jìn)程以打破循環(huán)等待，包括兩種方式：終止所有死鎖進(jìn)程和一次只終止一個(gè)進(jìn)程直到取消死鎖循環(huán)為止；所謂資源搶占就是從一個(gè)或者多個(gè)死鎖進(jìn)程那里搶占一個(gè)或多個(gè)資源。
（5）鴕鳥策略：
把頭埋在沙子里，假裝根本沒發(fā)生問題。因?yàn)榻鉀Q死鎖問題的代價(jià)很高，因此鴕鳥策略這種不采取任何措施的方案會(huì)獲得更高的性能。當(dāng)發(fā)生死鎖時(shí)不會(huì)對(duì)用戶造成多大影響，或發(fā)生死鎖的概率很低，可以采用鴕鳥策略。大多數(shù)操作系統(tǒng)，包括 Unix，Linux 和 Windows，處理死鎖問題的辦法僅僅是忽略它。
3、活鎖：
某些情況下，當(dāng)進(jìn)程意識(shí)到它不能獲取所需要的下一個(gè)鎖時(shí)，就會(huì)嘗試禮貌的釋放已經(jīng)獲得的鎖，然后等待非常短的時(shí)間再次嘗試獲取。可以想像一下這個(gè)場景：當(dāng)兩個(gè)人在狹路相逢的時(shí)候，都想給對(duì)方讓路，相同的步調(diào)會(huì)導(dǎo)致雙方都無法前進(jìn)。
現(xiàn)在假想有一對(duì)并行的進(jìn)程用到了兩個(gè)資源。它們分別嘗試獲取另一個(gè)鎖失敗后，兩個(gè)進(jìn)程都會(huì)釋放自己持有的鎖，再次進(jìn)行嘗試，這個(gè)過程會(huì)一直進(jìn)行重復(fù)。很明顯，這個(gè)過程中沒有進(jìn)程阻塞，但是進(jìn)程仍然不會(huì)向下執(zhí)行，這種狀況我們稱之為活鎖。
四、內(nèi)存管理：
1、內(nèi)存連續(xù)分配算法：
為了能將用戶程序裝入內(nèi)存，必須為它分配一定大小的內(nèi)存空間。連續(xù)分配算法是最早出現(xiàn)的分配方式，該分配方式為用戶程序在內(nèi)存中分配一個(gè)連續(xù)的內(nèi)存空間。連續(xù)分配方式可以分為四類：單一連續(xù)分配、固定分區(qū)分配、動(dòng)態(tài)分區(qū)分配 和 動(dòng)態(tài)可重定位分區(qū)分配。
（1）單一連續(xù)分配：
內(nèi)存在此方式下分為系統(tǒng)區(qū)和用戶區(qū)，系統(tǒng)區(qū)僅提供給操作系統(tǒng)使用，通常在低地址部分；用戶區(qū)是為用戶提供的、除系統(tǒng)區(qū)之外的內(nèi)存空間。這種方式無需進(jìn)行內(nèi)存保護(hù)。
這種方式的優(yōu)點(diǎn)是簡單、無外部碎片，可以釆用覆蓋技術(shù)，不需要額外的技術(shù)支持。缺點(diǎn)是只能用于單用戶、單任務(wù)的操作系統(tǒng)中，有內(nèi)部碎片，存儲(chǔ)器的利用率極低。
（2）固定分區(qū)分配：
將用戶內(nèi)存空間劃分為若干個(gè)固定大小的區(qū)域（分區(qū)大小可以相等也可以不等），每個(gè)分區(qū)只裝入一道作業(yè)。 當(dāng)有空閑分區(qū)時(shí)，便可以再從外存的后備作業(yè)隊(duì)列中，選擇適當(dāng)大小的作業(yè)裝入該分區(qū)，如此循環(huán)。
這種分區(qū)方式存在兩個(gè)問題：一是程序可能太大而放不進(jìn)任何一個(gè)分區(qū)中，這時(shí)用戶不得不使用覆蓋技術(shù)來使用內(nèi)存空間；二是主存利用率低，當(dāng)程序小于固定分區(qū)大小時(shí)，也占用了一個(gè)完整的內(nèi)存分區(qū)空間，存在稱為內(nèi)部碎片。
（3）動(dòng)態(tài)分區(qū)分配：
該分區(qū)方法不預(yù)先劃分內(nèi)存劃，而是在進(jìn)程裝入內(nèi)存時(shí)，根據(jù)進(jìn)程的大小動(dòng)態(tài)地建立分區(qū)，并使分區(qū)的大小正好適合進(jìn)程的需要，因此分區(qū)的大小和數(shù)目是可變的。在進(jìn)程裝入主存時(shí)，如果內(nèi)存中有多個(gè)足夠大的空閑塊，操作系統(tǒng)必須確定分配哪個(gè)內(nèi)存塊給進(jìn)程使用，這就是動(dòng)態(tài)分區(qū)的分配策略，常見的分配策略有：
① 首次適應(yīng)算法：從空閑分區(qū)鏈?zhǔn)组_始查找，直至找到一個(gè)能滿足其大小需求的空閑分區(qū)為止。然后再按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存分配給請(qǐng)求者。
該算法傾向于使用內(nèi)存中低地址部分的空閑分區(qū)，在高地址部分的空閑分區(qū)非常少被利用，從而保留了高地址部分的大空閑區(qū)。為以后到達(dá)的大作業(yè)分配大的內(nèi)存空間創(chuàng)造了條件。缺點(diǎn)在于低址部分不斷被劃分，留下許多內(nèi)存碎片，并且每次查找都從低址部分開始，會(huì)增加查找的開銷。
② 循環(huán)首次適應(yīng)算法：在為進(jìn)程分配內(nèi)存空間時(shí)，不再每次從鏈?zhǔn)组_始查找，而是從上次找到的空閑分區(qū)開始查找，直至找到一個(gè)能滿足需求的空閑分區(qū)，并從中劃出一塊來分給作業(yè)。
該算法能使空閑中的內(nèi)存分區(qū)分布得更加均勻，缺點(diǎn)是將會(huì)缺乏大的空閑分區(qū)。
（3）最佳適應(yīng)算法：把既能滿足需求，又是最小的空閑分區(qū)分配給作業(yè)。
為了加速查找，需要將所有的空閑區(qū)按照大小排序后，以遞增順序形成一個(gè)空白鏈。這樣每次找到的第一個(gè)滿足需求的空閑區(qū)，必然是最優(yōu)的，因?yàn)槊看畏峙浜笫Ｓ嗟目臻g一定是最小的，缺點(diǎn)是在于內(nèi)存中將留下許多難以利用的小空閑區(qū)。同時(shí)每次分配后必須重新排序，這也帶來了一定的開銷。
（4）最差適應(yīng)算法：按分區(qū)大小遞減的順序形成空閑區(qū)鏈，分配時(shí)直接從空閑區(qū)鏈的第一個(gè)空閑分區(qū)中分配，如果第一個(gè)空閑分區(qū)不能滿足，那么再?zèng)]有空閑分區(qū)能滿足需要。在大空閑區(qū)中放入程式后，剩下的空閑區(qū)常常也非常大，于是還能裝下一個(gè)較大的新程式。
該算法克服了最佳適應(yīng)算法留下的許多小碎片的不足，但缺點(diǎn)是保留大的空閑區(qū)的可能性減小了，而且空閑區(qū)回收也和最佳適應(yīng)算法相同復(fù)雜。
2、虛擬內(nèi)存：
連續(xù)分配方式會(huì)形成許多“碎片”，雖然可以通過“緊湊”方法將碎片拼接成可用的大塊空間，但開銷很大，如果允許將一個(gè)進(jìn)程分散地裝入到許多不相鄰的分區(qū)中，便可以充分利用內(nèi)存，而無須再進(jìn)行“緊湊”?；谶@一思想而產(chǎn)生了離散分配方式：分頁存儲(chǔ)管理、分段存儲(chǔ)管理、段頁式存儲(chǔ)管理。而實(shí)現(xiàn)這種離散式分配的基礎(chǔ)就是虛擬內(nèi)存。
虛擬內(nèi)存是為了讓物理內(nèi)存擴(kuò)充成更大的邏輯內(nèi)存，讓程序獲得更多的可用內(nèi)存。實(shí)現(xiàn)的前提是應(yīng)用程序在運(yùn)行之前沒有必要將頁面或段全部裝入內(nèi)存，僅需將那些當(dāng)前運(yùn)行所需的少數(shù)頁面或段先裝入內(nèi)存，其余部分暫留在磁盤上。
虛擬內(nèi)存的基本思想是：每個(gè)程序擁有自己的地址空間，這個(gè)空間被分為大小相等的多個(gè)塊，稱為頁，每個(gè)頁都是一段連續(xù)的地址。這些頁被映射到物理內(nèi)存，但并不是所有的頁都必須在內(nèi)存中才能運(yùn)行程序。當(dāng)程序引用到一部分在物理內(nèi)存中的地址空間時(shí)，由硬件立刻進(jìn)行必要的映射；當(dāng)程序引用到一部分不在物理內(nèi)存中的地址空間時(shí)，由操作系統(tǒng)負(fù)責(zé)將缺失的部分裝入物理內(nèi)存并重新執(zhí)行失敗的命令。
這樣，對(duì)于進(jìn)程而言，邏輯上似乎有很大的內(nèi)存空間，實(shí)際上其中一部分對(duì)應(yīng)物理內(nèi)存上的一塊(稱為幀，通常頁和幀大小相等)，還有一些沒加載在內(nèi)存中的對(duì)應(yīng)在硬盤上。
虛擬內(nèi)存的好處在于：
3、頁面置換算法：
在進(jìn)程運(yùn)行的過程中，如果所要訪問的頁面不在內(nèi)存，則需把他們調(diào)入內(nèi)存，但是如果內(nèi)存已無空閑空間時(shí)，系統(tǒng)必須從內(nèi)存中調(diào)出一頁程序或者數(shù)據(jù)送到磁盤的對(duì)換區(qū)中。這時(shí)，把選擇換出頁面的算法稱為頁面置換算法。
（1）最佳頁面替換算法（OPT）：被換出的頁面將是最長時(shí)間內(nèi)不再被訪問的，通常可以保證獲得最低的缺頁率。是一種理論上的算法，因?yàn)闊o法知道一個(gè)頁面多長時(shí)間不再被訪問。
（2）最近最少使用（LRU）：淘汰最近一段時(shí)間內(nèi)最久未被使用的頁面。
（3）最近未使用（NRU）：
每個(gè)頁面都有兩個(gè)狀態(tài)位：R 與 M，當(dāng)頁面被訪問時(shí)設(shè)置頁面的 R=1，當(dāng)頁面被修改時(shí)設(shè)置 M=1。其中 R 位會(huì)定時(shí)被清零?？梢詫㈨撁娣殖梢韵滤念悾?/span>
R=0，M=0
R=0，M=1
R=1，M=0
R=1，M=1
當(dāng)發(fā)生缺頁中斷時(shí)，NRU 算法隨機(jī)地從類編號(hào)最小的非空類中挑選一個(gè)頁面將它換出。
NRU 優(yōu)先換出已經(jīng)被修改的臟頁面（R=0，M=1），而不是被頻繁使用的干凈頁面（R=1，M=0）。
（4）先進(jìn)先出（FIFO）：淘汰在內(nèi)存中駐留時(shí)間最長的頁。
（5）第二機(jī)會(huì)算法（SCR）：
FIFO 算法可能會(huì)把經(jīng)常使用的頁面置換出去，為了避免這一問題，對(duì)該算法做一個(gè)簡單的修改：當(dāng)頁面被訪問 (讀或?qū)? 時(shí)設(shè)置該頁面的 R 位為 1。需要替換的時(shí)候，檢查最老頁面的 R 位。如果 R 位是 0，那么這個(gè)頁面既老又沒有被使用，可以立刻置換掉；如果是 1，就將 R 位清 0，并把該頁面放到鏈表的尾端，修改它的裝入時(shí)間使它就像剛裝入的一樣，然后繼續(xù)從鏈表的頭部開始搜索。
（6）時(shí)鐘頁面替換算法（Clock）：
第二次機(jī)會(huì)算法需要在鏈表中移動(dòng)頁面，降低了效率。時(shí)鐘算法與SCR算法思路一致。只是用循環(huán)隊(duì)列來構(gòu)造頁面隊(duì)列，隊(duì)列指針指向可能被淘汰的頁面。如果隊(duì)列指針指向的頁的“引用位”為1，則將其置為0，同時(shí)隊(duì)列指針指向下一個(gè)頁。
4、顛簸/抖動(dòng)：
顛簸本質(zhì)上是指頻繁的頁調(diào)度行為，具體來講，進(jìn)程發(fā)生缺頁中斷，這時(shí)，必須置換某一頁。然而，其他所有的頁都在使用，它置換一個(gè)頁，但又立刻再次需要這個(gè)頁。因此，會(huì)不斷產(chǎn)生缺頁中斷，導(dǎo)致整個(gè)系統(tǒng)的效率急劇下降，這種現(xiàn)象稱為顛簸（抖動(dòng)）。
內(nèi)存顛簸的解決策略包括：
如果是因?yàn)轫撁嫣鎿Q策略失誤，可以修改替換算法來解決這個(gè)問題；
如果是因?yàn)檫\(yùn)行的程序太多，造成程序無法同時(shí)將所有頻繁訪問的頁面調(diào)入內(nèi)存，則要降低多道程序的數(shù)量；
否則，還剩下兩個(gè)辦法：終止該進(jìn)程或增加物理內(nèi)存容量
五、文件系統(tǒng)：
1、磁盤的物理結(jié)構(gòu)：
磁盤面（Platter）：一個(gè)磁盤有多個(gè)盤面；
磁道（Track）：盤面上的圓形帶狀區(qū)域，一個(gè)盤面可以有多個(gè)磁道；
扇區(qū)（Track Sector）：磁道上的一個(gè)弧段，一個(gè)磁道可以有多個(gè)扇區(qū)，它是最小的物理儲(chǔ)存單位，目前主要有 512 bytes 與 4 K 兩種大??；
磁頭（Head）：與盤面非常接近，能夠?qū)⒈P面上的磁場轉(zhuǎn)換為電信號(hào)（讀），或者將電信號(hào)轉(zhuǎn)換為盤面的磁場（寫）；
機(jī)械臂桿（Actuator arm）：用于在磁道之間移動(dòng)磁頭；
轉(zhuǎn)軸（Spindle）：使整個(gè)盤面轉(zhuǎn)動(dòng)。
在磁盤上定位某個(gè)物理記錄需要知道其柱面號(hào)、磁頭號(hào)以及扇區(qū)號(hào)。定位物理記錄時(shí)，磁頭到達(dá)指定扇區(qū)的時(shí)間稱為查找時(shí)間， 選擇磁頭號(hào)并旋轉(zhuǎn)至指定扇區(qū)的時(shí)間稱為 搜索延遲。
2、磁盤調(diào)度算法：
讀寫一個(gè)磁盤塊的時(shí)間的影響因素有：
尋道時(shí)間（制動(dòng)手臂移動(dòng)，使得磁頭移動(dòng)到適當(dāng)?shù)拇诺郎希?/span>
旋轉(zhuǎn)時(shí)間（主軸轉(zhuǎn)動(dòng)盤面，使得磁頭移動(dòng)到適當(dāng)?shù)纳葏^(qū)上）
實(shí)際的數(shù)據(jù)傳輸時(shí)間
其中，尋道時(shí)間最長，因此磁盤調(diào)度的主要目標(biāo)是使磁盤的平均尋道時(shí)間最短。
（1）先來先服務(wù)（FCFS）：按照磁盤請(qǐng)求的順序進(jìn)行調(diào)度。優(yōu)點(diǎn)是公平和簡單，缺點(diǎn)也很明顯，因?yàn)槲磳?duì)尋道做任何優(yōu)化，使平均尋道時(shí)間可能較長。
（2）最短尋道時(shí)間優(yōu)先（SSTF）：優(yōu)先調(diào)度與當(dāng)前磁頭所在磁道距離最近的磁道。雖然平均尋道時(shí)間比較低，但是不夠公平。如果新到達(dá)的磁道請(qǐng)求總是比一個(gè)在等待的磁道請(qǐng)求近，那么在等待的磁道請(qǐng)求會(huì)一直等待下去，也就是出現(xiàn)饑餓現(xiàn)象。具體來說，兩端的磁道請(qǐng)求更容易出現(xiàn)饑餓現(xiàn)象。
（3）電梯算法（SCAN）：電梯算法和電梯的運(yùn)行過程類似，總是按一個(gè)方向來進(jìn)行磁盤調(diào)度，直到該方向上沒有未完成的磁盤請(qǐng)求，然后改變方向。因?yàn)榭紤]了移動(dòng)方向，因此所有的磁盤請(qǐng)求都會(huì)被滿足，解決了 SSTF 的饑餓問題。
六、IO篇：
1、Unix 常見的IO模型：
對(duì)于一次IO訪問（以read舉例），數(shù)據(jù)會(huì)先被拷貝到操作系統(tǒng)內(nèi)核的緩沖區(qū)中，然后才會(huì)從操作系統(tǒng)內(nèi)核的緩沖區(qū)拷貝到應(yīng)用程序的地址空間。所以說，當(dāng)一個(gè)read操作發(fā)生時(shí)，它會(huì)經(jīng)歷兩個(gè)階段：
正式因?yàn)檫@兩個(gè)階段，linux系統(tǒng)產(chǎn)生了下面五種網(wǎng)絡(luò)模式的方案：
阻塞式IO模型(blocking IO model)
非阻塞式IO模型(noblocking IO model)
IO復(fù)用式IO模型(IO multiplexing model)
信號(hào)驅(qū)動(dòng)式IO模型(signal-driven IO model)
異步IO式IO模型(asynchronous IO model)
對(duì)于這幾種 IO 模型的詳細(xì)說明，可以參考這篇文章：https://juejin.cn/post/6942686874301857800#heading-13
其中，IO多路復(fù)用模型指的是：使用單個(gè)進(jìn)程同時(shí)處理多個(gè)網(wǎng)絡(luò)連接IO，他的原理就是select、poll、epoll 不斷輪詢所負(fù)責(zé)的所有 socket，當(dāng)某個(gè)socket有數(shù)據(jù)到達(dá)了，就通知用戶進(jìn)程。該模型的優(yōu)勢并不是對(duì)于單個(gè)連接能處理得更快，而是在于能處理更多的連接。
2、select、poll 和 epoll 之間的區(qū)別：
（1）select：時(shí)間復(fù)雜度 O(n)
select 僅僅知道有 I/O 事件發(fā)生，但并不知道是哪幾個(gè)流，所以只能無差別輪詢所有流，找出能讀出數(shù)據(jù)或者寫入數(shù)據(jù)的流，并對(duì)其進(jìn)行操作。所以 select 具有 O(n) 的無差別輪詢復(fù)雜度，同時(shí)處理的流越多，無差別輪詢時(shí)間就越長。
（2）poll：時(shí)間復(fù)雜度 O(n)
poll 本質(zhì)上和 select 沒有區(qū)別，它將用戶傳入的數(shù)組拷貝到內(nèi)核空間，然后查詢每個(gè) fd 對(duì)應(yīng)的設(shè)備狀態(tài)， 但是它沒有最大連接數(shù)的限制，原因是它是基于鏈表來存儲(chǔ)的。
（3）epoll：時(shí)間復(fù)雜度 O(1)
epoll 可以理解為 event poll，不同于忙輪詢和無差別輪詢，epoll 會(huì)把哪個(gè)流發(fā)生了怎樣的 I/O 事件通知我們。所以說 epoll 實(shí)際上是事件驅(qū)動(dòng)（每個(gè)事件關(guān)聯(lián)上 fd）的。
select，poll，epoll 都是 IO 多路復(fù)用的機(jī)制。I/O 多路復(fù)用就是通過一種機(jī)制監(jiān)視多個(gè)描述符，一旦某個(gè)描述符就緒（一般是讀就緒或者寫就緒），就通知程序進(jìn)行相應(yīng)的讀寫操作。但 select，poll，epoll 本質(zhì)上都是同步 I/O，因?yàn)樗麄兌夹枰谧x寫事件就緒后自己負(fù)責(zé)進(jìn)行讀寫，也就是說這個(gè)讀寫過程是阻塞的，而異步 I/O 則無需自己負(fù)責(zé)進(jìn)行讀寫，異步 I/O 的實(shí)現(xiàn)會(huì)負(fù)責(zé)把數(shù)據(jù)從內(nèi)核拷貝到用戶空間。
版權(quán)聲明：本文為博主原創(chuàng)文章，遵循 CC 4.0 BY-SA 版權(quán)協(xié)議，轉(zhuǎn)載請(qǐng)附上原文出處鏈接和本聲明。
本文鏈接：
https://blog.csdn.net/a745233700/article/details/85995095
