操作系統(tǒng)基礎(chǔ)必備知識(shí)
今天給大家推薦兩份大佬們總結(jié)的 PDF，一份是計(jì)算機(jī)基礎(chǔ)知識(shí)，一份是操作系統(tǒng)，反正帥地看完之后，和面試官聊天，都有點(diǎn)飄了，廢話不多說(shuō),下面就讓小編帶你去看看哪些操作系統(tǒng)必備基礎(chǔ)知識(shí)，希望能幫助到大家!
操作系統(tǒng)基礎(chǔ)知識(shí)
操作系統(tǒng)是計(jì)算機(jī)體系中必不可少的核心系統(tǒng)軟件，其他軟件(如編輯程序、匯編程序、編譯程序、數(shù)據(jù)庫(kù)管理系統(tǒng)等系統(tǒng)軟件，以及大量應(yīng)用軟件)是建立在操作系統(tǒng)的基礎(chǔ)上，并在操作系統(tǒng)的統(tǒng)一管理和支持下運(yùn)行。操作系統(tǒng)是用戶與計(jì)算機(jī)之間的橋梁，用戶可以通過(guò)操作系統(tǒng)提供的功能訪問(wèn)計(jì)算機(jī)系統(tǒng)中的軟硬件資源。操作系統(tǒng)的作用是通過(guò)資源管理提高計(jì)算機(jī)系統(tǒng)的效率，改善人機(jī)界面，為用戶提供有好的工作環(huán)境。有效地組織和管理系統(tǒng)中的各種軟硬件資源，合理的組織計(jì)算機(jī)系統(tǒng)工作流程，控制程序的執(zhí)行，并且向用戶提供一個(gè)良好的工作環(huán)境和友好的接口。
簡(jiǎn)單的說(shuō)，操作系統(tǒng)就是運(yùn)行在計(jì)算機(jī)硬件和軟件(其他系統(tǒng)軟件和應(yīng)用軟件)之間的一個(gè)系統(tǒng)軟件，它的主要作用就是讓計(jì)算機(jī)能夠運(yùn)行的很好的同時(shí)讓你覺得也不錯(cuò)。
操作系統(tǒng)分為這么幾種：批處理操作系統(tǒng)、分時(shí)操作系統(tǒng)、實(shí)時(shí)操作系統(tǒng)、網(wǎng)絡(luò)操作系統(tǒng)、分布式操作系統(tǒng)、嵌入式操作系統(tǒng)、微機(jī)操作系統(tǒng)(這個(gè)我們就比較常見了，比如Linux、Windows、Unix、手機(jī)上的基于Unix的安卓系統(tǒng)等等)。
操作系統(tǒng)的功能可分為5大部分：處理機(jī)(CPU)管理、文件管理、存儲(chǔ)管理、設(shè)備管理和作業(yè)管理。下面說(shuō)說(shuō)處理機(jī)管理中的一些基礎(chǔ)知識(shí)。
三態(tài)模型 五態(tài)模型
在多道程序環(huán)境的系統(tǒng)中，存在多個(gè)可以一起進(jìn)行(并發(fā)執(zhí)行)的進(jìn)程，因此必然會(huì)存在進(jìn)程之間的通信問(wèn)題。
進(jìn)程間的通信主要有同步、互斥、調(diào)度、死鎖、信號(hào)量機(jī)制等問(wèn)題
進(jìn)程間的同步 多個(gè)進(jìn)程都是獨(dú)立進(jìn)行的，有的時(shí)候需要在某些地方協(xié)調(diào)一下，比如進(jìn)程A在生產(chǎn)一個(gè)原件，進(jìn)程B要加工這個(gè)原件，這時(shí)候就需要進(jìn)程B等待進(jìn)程A完成后才能開始進(jìn)行，這就是進(jìn)程之間的同步。
進(jìn)程間的互斥 這就是指兩個(gè)進(jìn)程都想用同一個(gè)資源，但是這個(gè)資源同時(shí)只能被一個(gè)進(jìn)程使用。這就是進(jìn)程之間的互斥，這些有限的資源叫做臨界資源。要使用這些臨界資源的程序段就叫做臨界區(qū)，對(duì)臨界區(qū)的管理原則是：有空即進(jìn)( 資源空閑就用)、 無(wú)空則等( 沒有資源就等一會(huì))、 有限等待(不能一直等下去)、 讓權(quán)等待(實(shí)在進(jìn)不去就走吧)。
為了解決進(jìn)程間的同步與互斥的問(wèn)題，荷蘭學(xué)者Dijkstra提出了信號(hào)量的機(jī)制， 發(fā)展到現(xiàn)在主要有整型信號(hào)量、記錄型信號(hào)量和信號(hào)量集機(jī)制。在引入了信號(hào)量機(jī)制后，為了提高通信效率，能夠大量傳輸數(shù)據(jù)，系統(tǒng)引入了高級(jí)通信方式，主要分為共享存儲(chǔ)方式(找一塊區(qū)域，把數(shù)據(jù)都放在這里)、消息傳遞模式(提供原語(yǔ)直接操作)和管道通信(在兩個(gè)進(jìn)程之間加個(gè)管道，有消息都放在那自取)。
死鎖是指兩個(gè)進(jìn)程互相要求對(duì)方已經(jīng)占用的資源，否則同時(shí)進(jìn)入臨界區(qū)的時(shí)候就會(huì)出現(xiàn)問(wèn)題。就好像有的國(guó)家手里有技術(shù)但沒有勞動(dòng)力，別的國(guó)家有勞動(dòng)力沒有技術(shù)，兩個(gè)國(guó)家都不讓步，這不就出現(xiàn)問(wèn)題了嘛。
進(jìn)程調(diào)度分為三級(jí)， 高級(jí)、中級(jí)和低級(jí)調(diào)度。其中，高級(jí)調(diào)度是決定哪個(gè)進(jìn)程可以進(jìn)入就緒狀態(tài);中級(jí)調(diào)度決定哪個(gè)就緒的進(jìn)程可以進(jìn)入內(nèi)存以便獲得CPU;低級(jí)調(diào)度決定處于內(nèi)存中的進(jìn)程哪個(gè)可以得到CPU，是操作系統(tǒng)中最活躍、最重要的調(diào)度程序。進(jìn)程調(diào)度的算法一般有先來(lái)先服務(wù)(FCFS，按照順序來(lái)，很好理解)、時(shí)間片輪轉(zhuǎn)(每個(gè)進(jìn)程只能運(yùn)行一段時(shí)間，到時(shí)間就等待，一般時(shí)間片分為固定和可變的時(shí)間片)、優(yōu)先級(jí)調(diào)度(優(yōu)先級(jí)越高的程序越早執(zhí)行唄)、多級(jí)反饋調(diào)度。
由于進(jìn)程是一個(gè)比較獨(dú)立的單元，總是這么切換、創(chuàng)建、銷毀的開銷太大，所以引入線程這一概念，可以認(rèn)為進(jìn)程就是有好幾個(gè)線程組成的，值得一提的是線程也有就緒、運(yùn)行、阻塞三種狀態(tài)，所以進(jìn)程也被稱為“輕量級(jí)進(jìn)程”。
操作系統(tǒng)基礎(chǔ)知識(shí)
注意：操作系統(tǒng)是掌握計(jì)算機(jī)的核心知識(shí)，一定要好好學(xué)啊。
一、概述
1. 操作系統(tǒng)基本特征
1. 并發(fā)
并發(fā)是指宏觀上在一段時(shí)間內(nèi)能同時(shí)運(yùn)行多個(gè)程序，而并行則指同一時(shí)刻能運(yùn)行多個(gè)指令。
并行需要硬件支持，如多流水線或者多處理器。
操作系統(tǒng)通過(guò)引入進(jìn)程和線程，使得程序能夠并發(fā)運(yùn)行。
2. 共享
共享是指系統(tǒng)中的資源可以被多個(gè)并發(fā)進(jìn)程共同使用。
有兩種共享方式：互斥共享和同時(shí)共享。
互斥共享的資源稱為臨界資源，例如打印機(jī)等，在同一時(shí)間只允許一個(gè)進(jìn)程訪問(wèn)，需要用同步機(jī)制來(lái)實(shí)現(xiàn)對(duì)臨界資源的訪問(wèn)。
3. 虛擬
虛擬技術(shù)把一個(gè)物理實(shí)體轉(zhuǎn)換為多個(gè)邏輯實(shí)體。
利用多道程序設(shè)計(jì)技術(shù)，讓每個(gè)用戶都覺得有一個(gè)計(jì)算機(jī)專門為他服務(wù)。
主要有兩種虛擬技術(shù)：時(shí)分復(fù)用技術(shù)和空分復(fù)用技術(shù)。例如多個(gè)進(jìn)程能在同一個(gè)處理器上并發(fā)執(zhí)行使用了時(shí)分復(fù)用技術(shù)，讓每個(gè)進(jìn)程輪流占有處理器，每次只執(zhí)行一小個(gè)時(shí)間片并快速切換。
4. 異步
異步指進(jìn)程不是一次性執(zhí)行完畢，而是走走停停，以不可知的速度向前推進(jìn)。
但只要運(yùn)行環(huán)境相同，OS需要保證程序運(yùn)行的結(jié)果也要相同。
2. 操作系統(tǒng)基本功能
1. 進(jìn)程管理
進(jìn)程控制、進(jìn)程同步、進(jìn)程通信、死鎖處理、處理機(jī)調(diào)度等。
2. 內(nèi)存管理
內(nèi)存分配、地址映射、內(nèi)存保護(hù)與共享、虛擬內(nèi)存等。
3. 文件管理
文件存儲(chǔ)空間的管理、目錄管理、文件讀寫管理和保護(hù)等。
4. 設(shè)備管理
完成用戶的 I/O 請(qǐng)求，方便用戶使用各種設(shè)備，并提高設(shè)備的利用率。
主要包括緩沖管理、設(shè)備分配、設(shè)備處理、虛擬設(shè)備等。
4. 大內(nèi)核和微內(nèi)核
1. 大內(nèi)核
大內(nèi)核是將操作系統(tǒng)功能作為一個(gè)緊密結(jié)合的整體放到內(nèi)核。
由于各模塊共享信息，因此有很高的性能。
2. 微內(nèi)核
由于操作系統(tǒng)不斷復(fù)雜，因此將一部分操作系統(tǒng)功能移出內(nèi)核，從而降低內(nèi)核的復(fù)雜性。移出的部分根據(jù)分層的原則劃分成若干服務(wù)，相互獨(dú)立。
在微內(nèi)核結(jié)構(gòu)下，操作系統(tǒng)被劃分成小的、定義良好的模塊，只有微內(nèi)核這一個(gè)模塊運(yùn)行在內(nèi)核態(tài)，其余模塊運(yùn)行在用戶態(tài)。
因?yàn)樾枰l繁地在用戶態(tài)和核心態(tài)之間進(jìn)行切換，所以會(huì)有一定的性能損失。
5. 中斷分類
1. 外中斷
由 CPU 執(zhí)行指令以外的事件引起，如 I/O 完成中斷，表示設(shè)備輸入/輸出處理已經(jīng)完成，處理器能夠發(fā)送下一個(gè)輸入/輸出請(qǐng)求。此外還有時(shí)鐘中斷、控制臺(tái)中斷等。
2. 異常
由 CPU 執(zhí)行指令的內(nèi)部事件引起，如非法操作碼、地址越界、算術(shù)溢出等。
6. 什么是堆和棧?說(shuō)一下堆棧都存儲(chǔ)哪些數(shù)據(jù)?
棧區(qū)(stack)— 由編譯器自動(dòng)分配釋放 ，存放函數(shù)的參數(shù)值，局部變量的值等。其操作方式類似于數(shù)據(jù)結(jié)構(gòu)中的棧。
堆區(qū)(heap) — 一般由程序員分配釋放， 若程序員不釋放，程序結(jié)束時(shí)可能由OS回收 。
數(shù)據(jù)結(jié)構(gòu)中這兩個(gè)完全就不放一塊來(lái)講，數(shù)據(jù)結(jié)構(gòu)中棧和隊(duì)列才是好基友，我想新手也很容易區(qū)分。
我想需要區(qū)分的情況肯定不是在數(shù)據(jù)結(jié)構(gòu)話題下，而大多是在 OS 關(guān)于不同對(duì)象的內(nèi)存分配這塊上。
簡(jiǎn)單講的話，在 C 語(yǔ)言中：
int a[N]; // go on a stackint__ a = (int __)malloc(sizeof(int) __ N); // go on a heap
7. 如何理解分布式鎖?
分布式鎖，是控制分布式系統(tǒng)之間同步訪問(wèn)共享資源的一種方式。在分布式系統(tǒng)中，常常需要協(xié)調(diào)他們的動(dòng)作。如果不同的系統(tǒng)或是同一個(gè)系統(tǒng)的不同主機(jī)之間共享了一個(gè)或一組資源，那么訪問(wèn)這些資源的時(shí)候，往往需要互斥來(lái)防止彼此干擾來(lái)保證一致性，在這種情況下，便需要使用到分布式鎖。
二、進(jìn)程管理
1. 進(jìn)程與線程
1. 進(jìn)程
進(jìn)程是資源分配的基本單位，用來(lái)管理資源(例如：內(nèi)存，文件，網(wǎng)絡(luò)等資源)
進(jìn)程控制塊 (Process Control Block, PCB) 描述進(jìn)程的基本信息和運(yùn)行狀態(tài)，所謂的創(chuàng)建進(jìn)程和撤銷進(jìn)程，都是指對(duì) PCB 的操作。(PCB是描述進(jìn)程的數(shù)據(jù)結(jié)構(gòu))
下圖顯示了 4 個(gè)程序創(chuàng)建了 4 個(gè)進(jìn)程，這 4 個(gè)進(jìn)程可以并發(fā)地執(zhí)行。
2. 線程
線程是獨(dú)立調(diào)度的基本單位。
一個(gè)進(jìn)程中可以有多個(gè)線程，它們共享進(jìn)程資源。
QQ 和瀏覽器是兩個(gè)進(jìn)程，瀏覽器進(jìn)程里面有很多線程，例如 HTTP 請(qǐng)求線程、事件響應(yīng)線程、渲染線程等等，線程的并發(fā)執(zhí)行使得在瀏覽器中點(diǎn)擊一個(gè)新鏈接從而發(fā)起 HTTP 請(qǐng)求時(shí)，瀏覽器還可以響應(yīng)用戶的其它事件。
3. 區(qū)別
(一)擁有資源
進(jìn)程是資源分配的基本單位，但是線程不擁有資源，線程可以訪問(wèn)隸屬進(jìn)程的資源。
(二)調(diào)度
線程是獨(dú)立調(diào)度的基本單位，在同一進(jìn)程中，線程的切換不會(huì)引起進(jìn)程切換，從一個(gè)進(jìn)程內(nèi)的線程切換到另一個(gè)進(jìn)程中的線程時(shí)，會(huì)引起進(jìn)程切換。
(三)系統(tǒng)開銷
由于創(chuàng)建或撤銷進(jìn)程時(shí)，系統(tǒng)都要為之分配或回收資源，如內(nèi)存空間、I/O 設(shè)備等，所付出的開銷遠(yuǎn)大于創(chuàng)建或撤銷線程時(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)容，開銷很小。
(四)通信方面
進(jìn)程間通信 (IPC) 需要進(jìn)程同步和互斥手段的輔助，以保證數(shù)據(jù)的一致性。而線程間可以通過(guò)直接讀/寫同一進(jìn)程中的數(shù)據(jù)段(如全局變量)來(lái)進(jìn)行通信。
2. 進(jìn)程狀態(tài)的切換(生命周期)
就緒狀態(tài)(ready)：等待被調(diào)度
運(yùn)行狀態(tài)(running)
阻塞狀態(tài)(waiting)：等待資源
應(yīng)該注意以下內(nèi)容：
只有就緒態(tài)和運(yùn)行態(tài)可以相互轉(zhuǎn)換，其它的都是單向轉(zhuǎn)換。就緒狀態(tài)的進(jìn)程通過(guò)調(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)換而來(lái)，但是該資源不包括 CPU 時(shí)間，缺少 CPU 時(shí)間會(huì)從運(yùn)行態(tài)轉(zhuǎn)換為就緒態(tài)。
進(jìn)程只能自己阻塞自己，因?yàn)橹挥羞M(jìn)程自身才知道何時(shí)需要等待某種事件的發(fā)生
3. 進(jìn)程調(diào)度算法
不同環(huán)境的調(diào)度算法目標(biāo)不同，因此需要針對(duì)不同環(huán)境來(lái)討論調(diào)度算法。
1. 批處理系統(tǒng)
批處理系統(tǒng)沒有太多的用戶操作，在該系統(tǒng)中，調(diào)度算法目標(biāo)是保證吞吐量和周轉(zhuǎn)時(shí)間(從提交到終止的時(shí)間)。
1.1 先來(lái)先服務(wù)
先來(lái)先服務(wù) first-come first-serverd(FCFS)
按照請(qǐng)求的順序進(jìn)行調(diào)度。
有利于長(zhǎng)作業(yè)，但不利于短作業(yè)，因?yàn)槎套鳂I(yè)必須一直等待前面的長(zhǎng)作業(yè)執(zhí)行完畢才能執(zhí)行，而長(zhǎng)作業(yè)又需要執(zhí)行很長(zhǎng)時(shí)間，造成了短作業(yè)等待時(shí)間過(guò)長(zhǎng)。
1.2 短作業(yè)優(yōu)先
短作業(yè)優(yōu)先 shortest job first(SJF)
按估計(jì)運(yùn)行時(shí)間最短的順序進(jìn)行調(diào)度。
長(zhǎng)作業(yè)有可能會(huì)餓死，處于一直等待短作業(yè)執(zhí)行完畢的狀態(tài)。因?yàn)槿绻恢庇卸套鳂I(yè)到來(lái)，那么長(zhǎng)作業(yè)永遠(yuǎn)得不到調(diào)度。
1.3 最短剩余時(shí)間優(yōu)先
最短剩余時(shí)間優(yōu)先 shortest remaining time next(SRTN)
按估計(jì)剩余時(shí)間最短的順序進(jìn)行調(diào)度。
2. 交互式系統(tǒng)
交互式系統(tǒng)有大量的用戶交互操作，在該系統(tǒng)中調(diào)度算法的目標(biāo)是快速地進(jìn)行響應(yīng)。
2.1 時(shí)間片輪轉(zhuǎn)
將所有就緒進(jìn)程按 FCFS (先來(lái)先服務(wù)) 的原則排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把 CPU 時(shí)間分配給隊(duì)首進(jìn)程，該進(jìn)程可以執(zhí)行一個(gè)時(shí)間片。當(dāng)時(shí)間片用完時(shí)，由計(jì)時(shí)器發(fā)出時(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ì)花過(guò)多時(shí)間。
2.2 優(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í)。
2.3 多級(jí)反饋隊(duì)列
如果一個(gè)進(jìn)程需要執(zhí)行 100 個(gè)時(shí)間片，如果采用時(shí)間片輪轉(zhuǎn)調(diào)度算法，那么需要交換 100 次。
多級(jí)隊(duì)列是為這種需要連續(xù)執(zhí)行多個(gè)時(shí)間片的進(jìn)程考慮，它設(shè)置了多個(gè)隊(duì)列，每個(gè)隊(duì)列時(shí)間片大小都不同，例如 1,2,4,8,..。進(jìn)程在第一個(gè)隊(duì)列沒執(zhí)行完，就會(huì)被移到下一個(gè)隊(duì)列。這種方式下，之前的進(jìn)程只需要交換 7 次。
每個(gè)隊(duì)列優(yōu)先權(quán)也不同，最上面的優(yōu)先權(quán)最高。因此只有上一個(gè)隊(duì)列沒有進(jìn)程在排隊(duì)，才能調(diào)度當(dāng)前隊(duì)列上的進(jìn)程。
可以將這種調(diào)度算法看成是時(shí)間片輪轉(zhuǎn)調(diào)度算法和優(yōu)先級(jí)調(diào)度算法的結(jié)合。
3. 實(shí)時(shí)系統(tǒng)
實(shí)時(shí)系統(tǒng)要求一個(gè)請(qǐng)求在一個(gè)確定時(shí)間內(nèi)得到響應(yīng)。
分為硬實(shí)時(shí)和軟實(shí)時(shí)，前者必須滿足絕對(duì)的截止時(shí)間，后者可以容忍一定的超時(shí)。
參考資料：
操作系統(tǒng)典型調(diào)度算法_C語(yǔ)言中文網(wǎng)
4. 進(jìn)程同步
1. 臨界區(qū)
對(duì)臨界資源進(jìn)行訪問(wèn)的那段代碼稱為臨界區(qū)。
為了互斥訪問(wèn)臨界資源，每個(gè)進(jìn)程在進(jìn)入臨界區(qū)之前，需要先進(jìn)行檢查。
// entry section// critical section;// exit section
2. 同步與互斥
同步：多個(gè)進(jìn)程按一定順序執(zhí)行;
互斥：多個(gè)進(jìn)程在同一時(shí)刻只有一個(gè)進(jìn)程能進(jìn)入臨界區(qū)。
3. 信號(hào)量
P 和 V 是來(lái)源于兩個(gè)荷蘭語(yǔ)詞匯，P() ---prolaag (荷蘭語(yǔ)，嘗試減少的意思)，V() ---verhoog(荷蘭語(yǔ)，增加的意思)
信號(hào)量(Semaphore)是一個(gè)整型變量，可以對(duì)其執(zhí)行 down 和 up 操作，也就是常見的 P 和 V 操作。
down : 如果信號(hào)量大于 0 ，執(zhí)行 -1 操作;如果信號(hào)量等于 0，進(jìn)程睡眠，等待信號(hào)量大于 0;(阻塞)
up ：對(duì)信號(hào)量執(zhí)行 +1 操作，喚醒睡眠的進(jìn)程讓其完成 down 操作。(喚醒)
down 和 up 操作需要被設(shè)計(jì)成原語(yǔ)，不可分割，通常的做法是在執(zhí)行這些操作的時(shí)候屏蔽中斷。
如果信號(hào)量的取值只能為 0 或者 1，那么就成為了 互斥量(Mutex) ，0 表示臨界區(qū)已經(jīng)加鎖，1 表示臨界區(qū)解鎖。
typedef int semaphore;semaphore mutex = 1;void P1() { down(&mutex); // 臨界區(qū) up(&mutex);}void P2() { down(&mutex); // 臨界區(qū) up(&mutex);}
使用信號(hào)量實(shí)現(xiàn)生產(chǎn)者-消費(fèi)者問(wèn)題
問(wèn)題描述：使用一個(gè)緩沖區(qū)來(lái)保存物品，只有緩沖區(qū)沒有滿，生產(chǎn)者才可以放入物品;只有緩沖區(qū)不為空，消費(fèi)者才可以拿走物品。
因?yàn)榫彌_區(qū)屬于臨界資源，因此需要使用一個(gè)互斥量 mutex 來(lái)控制對(duì)緩沖區(qū)的互斥訪問(wèn)。
為了同步生產(chǎn)者和消費(fèi)者的行為，需要記錄緩沖區(qū)中物品的數(shù)量。數(shù)量可以使用信號(hào)量來(lái)進(jìn)行統(tǒng)計(jì)，這里需要使用兩個(gè)信號(hào)量：empty 記錄空緩沖區(qū)的數(shù)量，full 記錄滿緩沖區(qū)的數(shù)量。其中，empty 信號(hào)量是在生產(chǎn)者進(jìn)程中使用，當(dāng) empty 不為 0 時(shí)，生產(chǎn)者才可以放入物品;full 信號(hào)量是在消費(fèi)者進(jìn)程中使用，當(dāng) full 信號(hào)量不為 0 時(shí)，消費(fèi)者才可以取走物品。
注意，不能先對(duì)緩沖區(qū)進(jìn)行加鎖，再測(cè)試信號(hào)量。也就是說(shuō)，不能先執(zhí)行 down(mutex) 再執(zhí)行 down(empty)。如果這么做了，那么可能會(huì)出現(xiàn)這種情況：生產(chǎn)者對(duì)緩沖區(qū)加鎖后，執(zhí)行 down(empty) 操作，發(fā)現(xiàn) empty = 0，此時(shí)生產(chǎn)者睡眠。消費(fèi)者不能進(jìn)入臨界區(qū)，因?yàn)樯a(chǎn)者對(duì)緩沖區(qū)加鎖了，也就無(wú)法執(zhí)行 up(empty) 操作，empty 永遠(yuǎn)都為 0，那么生產(chǎn)者和消費(fèi)者就會(huì)一直等待下去，造成死鎖。
#define N 100typedef int semaphore;semaphore mutex = 1;semaphore empty = N;semaphore full = 0;void producer() { while(TRUE){ int item = produce_item(); // 生產(chǎn)一個(gè)產(chǎn)品 // down(&empty) 和 down(&mutex) 不能交換位置，否則造成死鎖 down(&empty); // 記錄空緩沖區(qū)的數(shù)量，這里減少一個(gè)產(chǎn)品空間 down(&mutex); // 互斥鎖 insert_item(item); up(&mutex); // 互斥鎖 up(&full); // 記錄滿緩沖區(qū)的數(shù)量，這里增加一個(gè)產(chǎn)品 }}void consumer() { while(TRUE){ down(&full); // 記錄滿緩沖區(qū)的數(shù)量，減少一個(gè)產(chǎn)品 down(&mutex); // 互斥鎖 int item = remove_item(); up(&mutex); // 互斥鎖 up(&empty); // 記錄空緩沖區(qū)的數(shù)量，這里增加一個(gè)產(chǎn)品空間 consume_item(item); }}
4. 管程
管程 (英語(yǔ)：Monitors，也稱為監(jiān)視器) 是一種程序結(jié)構(gòu)，結(jié)構(gòu)內(nèi)的多個(gè)子程序(對(duì)象或模塊)形成的多個(gè)工作線程互斥訪問(wèn)共享資源。
使用信號(hào)量機(jī)制實(shí)現(xiàn)的生產(chǎn)者消費(fèi)者問(wèn)題需要客戶端代碼做很多控制，而管程把控制的代碼獨(dú)立出來(lái)，不僅不容易出錯(cuò)，也使得客戶端代碼調(diào)用更容易。
管程是為了解決信號(hào)量在臨界區(qū)的 PV 操作上的配對(duì)的麻煩，把配對(duì)的 PV 操作集中在一起，生成的一種并發(fā)編程方法。其中使用了條件變量這種同步機(jī)制。
c 語(yǔ)言不支持管程，下面的示例代碼使用了類 Pascal 語(yǔ)言來(lái)描述管程。示例代碼的管程提供了 insert() 和 remove() 方法，客戶端代碼通過(guò)調(diào)用這兩個(gè)方法來(lái)解決生產(chǎn)者-消費(fèi)者問(wèn)題。
monitor ProducerConsumer integer i; condition c; procedure insert(); begin // ... end; procedure remove(); begin // ... end;end monitor;
管程有一個(gè)重要特性：在一個(gè)時(shí)刻只能有一個(gè)進(jìn)程使用管程。進(jìn)程在無(wú)法繼續(xù)執(zhí)行的時(shí)候不能一直占用管程，否者其它進(jìn)程永遠(yuǎn)不能使用管程。
管程引入了 條件變量 以及相關(guān)的操作：wait() 和 signal() 來(lái)實(shí)現(xiàn)同步操作。對(duì)條件變量執(zhí)行 wait() 操作會(huì)導(dǎo)致調(diào)用進(jìn)程阻塞，把管程讓出來(lái)給另一個(gè)進(jìn)程持有。signal() 操作用于喚醒被阻塞的進(jìn)程。
使用管程實(shí)現(xiàn)生產(chǎn)者-消費(fèi)者問(wèn)題
// 管程monitor ProducerConsumer condition full, empty; integer count := 0; condition c; procedure insert(item: integer); begin if count = N then wait(full); insert_item(item); count := count + 1; if count = 1 then signal(empty); end; function remove: integer; begin if count = 0 then wait(empty); remove = remove_item; count := count - 1; if count = N -1 then signal(full); end;end monitor;// 生產(chǎn)者客戶端procedure producerbegin while true do begin item = produce_item; ProducerConsumer.insert(item); endend;// 消費(fèi)者客戶端procedure consumerbegin while true do begin item = ProducerConsumer.remove; consume_item(item); endend;
5. 經(jīng)典同步問(wèn)題
生產(chǎn)者和消費(fèi)者問(wèn)題前面已經(jīng)討論過(guò)了。
1. 讀者-寫者問(wèn)題
允許多個(gè)進(jìn)程同時(shí)對(duì)數(shù)據(jù)進(jìn)行讀操作，但是不允許讀和寫以及寫和寫操作同時(shí)發(fā)生。讀者優(yōu)先策略
Rcount：讀操作的進(jìn)程數(shù)量(Rcount=0)
CountMutex：對(duì)于Rcount進(jìn)行加鎖(CountMutex=1)
WriteMutex：互斥量對(duì)于寫操作的加鎖(WriteMutex=1)
Rcount = 0;semaphore CountMutex = 1;semaphore WriteMutex = 1;void writer(){ while(true){ sem_wait(WriteMutex); // TO DO write(); sem_post(WriteMutex); }}// 讀者優(yōu)先策略void reader(){ while(true){ sem_wait(CountMutex); if(Rcount == 0) sem_wait(WriteMutex); Rcount++; sem_post(CountMutex); // TO DO read(); sem_wait(CountMutex); Rcount--; if(Rcount == 0) sem_post(WriteMutex); sem_post(CountMutex); }}
2. 哲學(xué)家進(jìn)餐問(wèn)題
五個(gè)哲學(xué)家圍著一張圓桌，每個(gè)哲學(xué)家面前放著食物。哲學(xué)家的生活有兩種交替活動(dòng)：吃飯以及思考。當(dāng)一個(gè)哲學(xué)家吃飯時(shí)，需要先拿起自己左右兩邊的兩根筷子，并且一次只能拿起一根筷子。
____方案一：____下面是一種錯(cuò)誤的解法，考慮到如果所有哲學(xué)家同時(shí)拿起左手邊的筷子，那么就無(wú)法拿起右手邊的筷子，造成死鎖。
#define N 5 // 哲學(xué)家個(gè)數(shù)void philosopher(int i) // 哲學(xué)家編號(hào)：0 - 4{ while(TRUE) { think(); // 哲學(xué)家在思考 take_fork(i); // 去拿左邊的叉子 take_fork((i + 1) % N); // 去拿右邊的叉子 eat(); // 吃面條中…. put_fork(i); // 放下左邊的叉子 put_fork((i + 1) % N); // 放下右邊的叉子 }}
方案二：對(duì)拿叉子的過(guò)程進(jìn)行了改進(jìn)，但仍不正確
#define N 5 // 哲學(xué)家個(gè)數(shù)while(1) // 去拿兩把叉子{ take_fork(i); // 去拿左邊的叉子 if(fork((i+1)%N)) { // 右邊叉子還在嗎 take_fork((i + 1) % N);// 去拿右邊的叉子 break; // 兩把叉子均到手 } else { // 右邊叉子已不在 put_fork(i); // 放下左邊的叉子 wait_some_time(); // 等待一會(huì)兒 }}
方案三：等待時(shí)間隨機(jī)變化?？尚?，但非萬(wàn)全之策
#define N 5 // 哲學(xué)家個(gè)數(shù)while(1) // 去拿兩把叉子{ take_fork(i); // 去拿左邊的叉子 if(fork((i+1)%N)) { // 右邊叉子還在嗎 take_fork((i + 1) % N);// 去拿右邊的叉子 break; // 兩把叉子均到手 } else { // 右邊叉子已不在 put_fork(i); // 放下左邊的叉子 wait_random_time( ); // 等待隨機(jī)長(zhǎng)時(shí)間 }}
方案四：互斥訪問(wèn)。正確，但每次只允許一人進(jìn)餐
semaphore mutex // 互斥信號(hào)量，初值1void philosopher(int i) // 哲學(xué)家編號(hào)i：0-4 { while(TRUE){ think(); // 哲學(xué)家在思考 P(mutex); // 進(jìn)入臨界區(qū) take_fork(i); // 去拿左邊的叉子 take_fork((i + 1) % N); // 去拿右邊的叉子 eat(); // 吃面條中…. put_fork(i); // 放下左邊的叉子 put_fork((i + 1) % N); // 放下右邊的叉子 V(mutex); // 退出臨界區(qū) }}
正確方案如下：
為了防止死鎖的發(fā)生，可以設(shè)置兩個(gè)條件(臨界資源)：
必須同時(shí)拿起左右兩根筷子;
只有在兩個(gè)鄰居都沒有進(jìn)餐的情況下才允許進(jìn)餐。
//1. 必須由一個(gè)數(shù)據(jù)結(jié)構(gòu)，來(lái)描述每個(gè)哲學(xué)家當(dāng)前的狀態(tài)#define N 5#define LEFT i // 左鄰居#define RIGHT (i + 1) % N // 右鄰居#define THINKING 0#define HUNGRY 1#define EATING 2typedef int semaphore;int state[N]; // 跟蹤每個(gè)哲學(xué)家的狀態(tài)//2. 該狀態(tài)是一個(gè)臨界資源，對(duì)它的訪問(wèn)應(yīng)該互斥地進(jìn)行semaphore mutex = 1; // 臨界區(qū)的互斥//3. 一個(gè)哲學(xué)家吃飽后，可能要喚醒鄰居，存在著同步關(guān)系semaphore s[N]; // 每個(gè)哲學(xué)家一個(gè)信號(hào)量void philosopher(int i) { while(TRUE) { think(); take_two(i); eat(); put_tow(i); }}void take_two(int i) { P(&mutex); // 進(jìn)入臨界區(qū) state[i] = HUNGRY; // 我餓了 test(i); // 試圖拿兩把叉子 V(&mutex); // 退出臨界區(qū) P(&s[i]); // 沒有叉子便阻塞}void put_tow(i) { P(&mutex); state[i] = THINKING; test(LEFT); test(RIGHT); V(&mutex);}void test(i) { // 嘗試拿起兩把筷子 if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) { state[i] = EATING; V(&s[i]); // 通知第i個(gè)人可以吃飯了 }}
6. 進(jìn)程通信
進(jìn)程同步與進(jìn)程通信很容易混淆，它們的區(qū)別在于：
進(jìn)程同步：控制多個(gè)進(jìn)程按一定順序執(zhí)行
進(jìn)程通信：進(jìn)程間傳輸信息
進(jìn)程通信是一種手段，而進(jìn)程同步是一種目的。也可以說(shuō)，為了能夠達(dá)到進(jìn)程同步的目的，需要讓進(jìn)程進(jìn)行通信，傳輸一些進(jìn)程同步所需要的信息。
__ 進(jìn)程通信方式
直接通信
發(fā)送進(jìn)程直接把消息發(fā)送給接收進(jìn)程，并將它掛在接收進(jìn)程的消息緩沖隊(duì)列上，接收進(jìn)程從消息緩沖隊(duì)列中取得消息。
Send 和 Receive 原語(yǔ)的使用格式如下：
Send(Receiver,message);//發(fā)送一個(gè)消息message給接收進(jìn)程ReceiverReceive(Sender,message);//接收Sender進(jìn)程發(fā)送的消息message
間接通信
間接通信方式是指進(jìn)程之間的通信需要通過(guò)作為共享數(shù)據(jù)結(jié)構(gòu)的實(shí)體。該實(shí)體用來(lái)暫存發(fā)送進(jìn)程發(fā)給目標(biāo)進(jìn)程的消息。
發(fā)送進(jìn)程把消息發(fā)送到某個(gè)中間實(shí)體中，接收進(jìn)程從中間實(shí)體中取得消息。這種中間實(shí)體一般稱為信箱，這種通信方式又稱為信箱通信方式。該通信方式廣泛應(yīng)用于計(jì)算機(jī)網(wǎng)絡(luò)中，相應(yīng)的通信系統(tǒng)稱為電子郵件系統(tǒng)。
1. 管道
管道是通過(guò)調(diào)用 pipe 函數(shù)創(chuàng)建的，fd[0] 用于讀，fd[1] 用于寫。
#include int pipe(int fd[2]);
它具有以下限制：
只支持半雙工通信(單向傳輸);
只能在父子進(jìn)程中使用。
2. 命名管道
也稱為命名管道，去除了管道只能在父子進(jìn)程中使用的限制。
#include int mkfifo(const char __path, mode_t mode);int mkfifoat(int fd, const char __path, mode_t mode);
FIFO 常用于客戶-服務(wù)器應(yīng)用程序中，F(xiàn)IFO 用作匯聚點(diǎn)，在客戶進(jìn)程和服務(wù)器進(jìn)程之間傳遞數(shù)據(jù)。
3. 消息隊(duì)列
間接(內(nèi)核)
相比于 FIFO，消息隊(duì)列具有以下優(yōu)點(diǎn)：
消息隊(duì)列可以獨(dú)立于讀寫進(jìn)程存在，從而避免了 FIFO 中同步管道的打開和關(guān)閉時(shí)可能產(chǎn)生的困難;
避免了 FIFO 的同步阻塞問(wèn)題，不需要進(jìn)程自己提供同步方法;
讀進(jìn)程可以根據(jù)消息類型有選擇地接收消息，而不像 FIFO 那樣只能默認(rèn)地接收。
4. 信號(hào)量
它是一個(gè)計(jì)數(shù)器，用于為多個(gè)進(jìn)程提供對(duì)共享數(shù)據(jù)對(duì)象的訪問(wèn)。
5. 共享內(nèi)存
允許多個(gè)進(jìn)程共享一個(gè)給定的存儲(chǔ)區(qū)。因?yàn)閿?shù)據(jù)不需要在進(jìn)程之間復(fù)制，所以這是最快的一種 IPC。
需要使用信號(hào)量用來(lái)同步對(duì)共享存儲(chǔ)的訪問(wèn)。
多個(gè)進(jìn)程可以將同一個(gè)文件映射到它們的地址空間從而實(shí)現(xiàn)共享內(nèi)存。另外 XSI 共享內(nèi)存不是使用文件，而是使用使用內(nèi)存的匿名段。
6. 套接字
與其它通信機(jī)制不同的是，它可用于不同機(jī)器間的進(jìn)程通信。
7. 線程間通信和進(jìn)程間通信
線程間通信
synchronized同步
這種方式，本質(zhì)上就是 “共享內(nèi)存” 式的通信。多個(gè)線程需要訪問(wèn)同一個(gè)共享變量，誰(shuí)拿到了鎖(獲得了訪問(wèn)權(quán)限)，誰(shuí)就可以執(zhí)行。
while輪詢的方式
在這種方式下，ThreadA 不斷地改變條件，ThreadB 不停地通過(guò) while 語(yǔ)句檢測(cè)這個(gè)條件 (list.size()==5) 是否成立 ，從而實(shí)現(xiàn)了線程間的通信。但是這種方式會(huì)浪費(fèi) CPU 資源。
之所以說(shuō)它浪費(fèi)資源，是因?yàn)?JVM 調(diào)度器將 CPU 交給 ThreadB 執(zhí)行時(shí)，它沒做啥 “有用” 的工作，只是在不斷地測(cè)試某個(gè)條件是否成立。
就類似于現(xiàn)實(shí)生活中，某個(gè)人一直看著手機(jī)屏幕是否有電話來(lái)了，而不是：在干別的事情，當(dāng)有電話來(lái)時(shí)，響鈴?fù)ㄖ猅A電話來(lái)了。
wait/notify機(jī)制
當(dāng)條件未滿足時(shí)，ThreadA 調(diào)用 wait() 放棄 CPU，并進(jìn)入阻塞狀態(tài)。(不像 while 輪詢那樣占用 CPU)
當(dāng)條件滿足時(shí)，ThreadB 調(diào)用 notify() 通知線程 A，所謂通知線程 A，就是喚醒線程 A，并讓它進(jìn)入可運(yùn)行狀態(tài)。
管道通信
java.io.PipedInputStream 和 java.io.PipedOutputStream進(jìn)行通信
進(jìn)程間通信
管道(Pipe) ：管道可用于具有親緣關(guān)系進(jìn)程間的通信，允許一個(gè)進(jìn)程和另一個(gè)與它有共同祖先的進(jìn)程之間進(jìn)行通信。
命名管道(named pipe) ：命名管道克服了管道沒有名字的限制，因此，除具有管道所具有的功能外，它還允許無(wú)親緣關(guān) 系 進(jìn)程間的通信。命名管道在文件系統(tǒng)中有對(duì)應(yīng)的文件名。命名管道通過(guò)命令mkfifo或系統(tǒng)調(diào)用mkfifo來(lái)創(chuàng)建。
信號(hào)(Signal) ：信號(hào)是比較復(fù)雜的通信方式，用于通知接受進(jìn)程有某種事件發(fā)生，除了用于進(jìn)程間通信外，進(jìn)程還可以發(fā)送 信號(hào)給進(jìn)程本身;Linux除了支持Unix早期信號(hào)語(yǔ)義函數(shù)sigal外，還支持語(yǔ)義符合Posix.1標(biāo)準(zhǔn)的信號(hào)函數(shù)sigaction(實(shí)際上，該函數(shù)是基于BSD的，BSD為了實(shí)現(xiàn)可靠信號(hào)機(jī)制，又能夠統(tǒng)一對(duì)外接口，用sigaction函數(shù)重新實(shí)現(xiàn)了signal函數(shù))。
消息(Message)隊(duì)列 ：消息隊(duì)列是消息的鏈接表，包括Posix消息隊(duì)列system V消息隊(duì)列。有足夠權(quán)限的進(jìn)程可以向隊(duì)列中添加消息，被賦予讀權(quán)限的進(jìn)程則可以讀走隊(duì)列中的消息。消息隊(duì)列克服了信號(hào)承載信息量少，管道只能承載無(wú)格式字節(jié)流以及緩沖區(qū)大小受限等缺
共享內(nèi)存 ：使得多個(gè)進(jìn)程可以訪問(wèn)同一塊內(nèi)存空間，是最快的可用IPC形式。是針對(duì)其他通信機(jī)制運(yùn)行效率較低而設(shè)計(jì)的。往往與其它通信機(jī)制，如信號(hào)量結(jié)合使用，來(lái)達(dá)到進(jìn)程間的同步及互斥。
內(nèi)存映射(mapped memory) ：內(nèi)存映射允許任何多個(gè)進(jìn)程間通信，每一個(gè)使用該機(jī)制的進(jìn)程通過(guò)把一個(gè)共享的文件映射到自己的進(jìn)程地址空間來(lái)實(shí)現(xiàn)它。
信號(hào)量(semaphore) ：主要作為進(jìn)程間以及同一進(jìn)程不同線程之間的同步手段。
套接口(Socket) ：更為一般的進(jìn)程間通信機(jī)制，可用于不同機(jī)器之間的進(jìn)程間通信。起初是由Unix系統(tǒng)的BSD分支開發(fā)出來(lái)的，但現(xiàn)在一般可以移植到其它類Unix系統(tǒng)上：linux和System V的變種都支持套接字。
8. 進(jìn)程操作
Linux的進(jìn)程結(jié)構(gòu)可由三部分組成：
代碼段(程序)
數(shù)據(jù)段(數(shù)據(jù))
堆棧段(控制塊PCB)
進(jìn)程控制塊是進(jìn)程存在的惟一標(biāo)識(shí)，系統(tǒng)通過(guò)PCB的存在而感知進(jìn)程的存在。系統(tǒng)通過(guò) PCB 對(duì)進(jìn)程進(jìn)行管理和調(diào)度。PCB 包括創(chuàng)建進(jìn)程、執(zhí)行進(jìn)程、退出進(jìn)程以及改變進(jìn)程的優(yōu)先級(jí)等。
一般程序轉(zhuǎn)換為進(jìn)程分以下幾個(gè)步驟：
內(nèi)核將程序讀入內(nèi)存，為程序分配內(nèi)存空間
內(nèi)核為該進(jìn)程分配進(jìn)程標(biāo)識(shí)符 PID 和其他所需資源
內(nèi)核為進(jìn)程保存 PID 及相應(yīng)的狀態(tài)信息，把進(jìn)程放到運(yùn)行隊(duì)列中等待執(zhí)行，程序轉(zhuǎn)化為進(jìn)程后可以被操作系統(tǒng)的調(diào)度程序調(diào)度執(zhí)行了
在 UNIX 里，除了進(jìn)程 0(即 PID=0 的交換進(jìn)程，Swapper Process)以外的所有進(jìn)程都是由其他進(jìn)程使用系統(tǒng)調(diào)用 fork 創(chuàng)建的，這里調(diào)用 fork 創(chuàng)建新進(jìn)程的進(jìn)程即為父進(jìn)程，而相對(duì)應(yīng)的為其創(chuàng)建出的進(jìn)程則為子進(jìn)程，因而除了進(jìn)程 0 以外的進(jìn)程都只有一個(gè)父進(jìn)程，但一個(gè)進(jìn)程可以有多個(gè)子進(jìn)程。操作系統(tǒng)內(nèi)核以進(jìn)程標(biāo)識(shí)符(Process Identifier，即 PID )來(lái)識(shí)別進(jìn)程。進(jìn)程 0 是系統(tǒng)引導(dǎo)時(shí)創(chuàng)建的一個(gè)特殊進(jìn)程，在其調(diào)用 fork 創(chuàng)建出一個(gè)子進(jìn)程(即 PID=1 的進(jìn)程 1，又稱 init)后，進(jìn)程 0 就轉(zhuǎn)為交換進(jìn)程(有時(shí)也被稱為空閑進(jìn)程)，而進(jìn)程1(init進(jìn)程)就是系統(tǒng)里其他所有進(jìn)程的祖先。
進(jìn)程0：Linux引導(dǎo)中創(chuàng)建的第一個(gè)進(jìn)程，完成加載系統(tǒng)后，演變?yōu)檫M(jìn)程調(diào)度、交換及存儲(chǔ)管理進(jìn)程?！ ∵M(jìn)程1：init 進(jìn)程，由0進(jìn)程創(chuàng)建，完成系統(tǒng)的初始化. 是系統(tǒng)中所有其它用戶進(jìn)程的祖先進(jìn)程。
Linux中 1 號(hào)進(jìn)程是由 0 號(hào)進(jìn)程來(lái)創(chuàng)建的，因此必須要知道的是如何創(chuàng)建 0 號(hào)進(jìn)程，由于在創(chuàng)建進(jìn)程時(shí)，程序一直運(yùn)行在內(nèi)核態(tài)，而進(jìn)程運(yùn)行在用戶態(tài)，因此創(chuàng)建 0 號(hào)進(jìn)程涉及到特權(quán)級(jí)的變化，即從特權(quán)級(jí) 0 變到特權(quán)級(jí) 3，Linux 是通過(guò)模擬中斷返回來(lái)實(shí)現(xiàn)特權(quán)級(jí)的變化以及創(chuàng)建 0 號(hào)進(jìn)程，通過(guò)將 0 號(hào)進(jìn)程的代碼段選擇子以及程序計(jì)數(shù)器EIP直接壓入內(nèi)核態(tài)堆棧，然后利用 iret 匯編指令中斷返回跳轉(zhuǎn)到 0 號(hào)進(jìn)程運(yùn)行。
創(chuàng)建一個(gè)進(jìn)程
進(jìn)程是系統(tǒng)中基本的執(zhí)行單位。Linux 系統(tǒng)允許任何一個(gè)用戶進(jìn)程創(chuàng)建一個(gè)子進(jìn)程，創(chuàng)建成功后，子進(jìn)程存在于系統(tǒng)之中，并且獨(dú)立于父進(jìn)程。該子進(jìn)程可以接受系統(tǒng)調(diào)度，可以得到分配的系統(tǒng)資源。系統(tǒng)也可以檢測(cè)到子進(jìn)程的存在，并且賦予它與父進(jìn)程同樣的權(quán)利。
Linux系統(tǒng)下使用 fork() 函數(shù)創(chuàng)建一個(gè)子進(jìn)程，其函數(shù)原型如下：
#include pid_t fork(void);
在討論 fork() 函數(shù)之前，有必要先明確父進(jìn)程和子進(jìn)程兩個(gè)概念。除了 0 號(hào)進(jìn)程(該進(jìn)程是系統(tǒng)自舉時(shí)由系統(tǒng)創(chuàng)建的)以外，Linux 系統(tǒng)中的任何一個(gè)進(jìn)程都是由其他進(jìn)程創(chuàng)建的。創(chuàng)建新進(jìn)程的進(jìn)程，即調(diào)用 fork() 函數(shù)的進(jìn)程就是父進(jìn)程，而新創(chuàng)建的進(jìn)程就是子進(jìn)程。
fork() 函數(shù)不需要參數(shù)，返回值是一個(gè)進(jìn)程標(biāo)識(shí)符 (PID)。對(duì)于返回值，有以下 3 種情況：
對(duì)于父進(jìn)程，fork() 函數(shù)返回新創(chuàng)建的子進(jìn)程的 ID。
對(duì)于子進(jìn)程，fork() 函數(shù)返回 0。由于系統(tǒng)的 0 號(hào)進(jìn)程是內(nèi)核進(jìn)程，所以子進(jìn)程的進(jìn)程標(biāo)識(shí)符不會(huì)是0，由此可以用來(lái)區(qū)別父進(jìn)程和子進(jìn)程。
如果創(chuàng)建出錯(cuò)，則 fork() 函數(shù)返回 -1。
fork() 函數(shù)會(huì)創(chuàng)建一個(gè)新的進(jìn)程，并從內(nèi)核中為此進(jìn)程分配一個(gè)新的可用的進(jìn)程標(biāo)識(shí)符 (PID)，之后，為這個(gè)新進(jìn)程分配進(jìn)程空間，并將父進(jìn)程的進(jìn)程空間中的內(nèi)容復(fù)制到子進(jìn)程的進(jìn)程空間中，包括父進(jìn)程的數(shù)據(jù)段和堆棧段，并且和父進(jìn)程共享代碼段(寫時(shí)復(fù)制)。這時(shí)候，系統(tǒng)中又多了一個(gè)進(jìn)程，這個(gè)進(jìn)程和父進(jìn)程一模一樣，兩個(gè)進(jìn)程都要接受系統(tǒng)的調(diào)度。
注意：由于在復(fù)制時(shí)復(fù)制了父進(jìn)程的堆棧段，所以兩個(gè)進(jìn)程都停留在了 fork() 函數(shù)中，等待返回。因此，fork() 函數(shù)會(huì)返回兩次，一次是在父進(jìn)程中返回，另一次是在子進(jìn)程中返回，這兩次的返回值是不一樣的。
下面給出的示例程序用來(lái)創(chuàng)建一個(gè)子進(jìn)程，該程序在父進(jìn)程和子進(jìn)程中分別輸出不同的內(nèi)容。
#include #include #include int main(void){ pid_t pid; // 保存進(jìn)程ID pid = fork(); // 創(chuàng)建一個(gè)新進(jìn)程 if(pid < 0){ // fork出錯(cuò) printf("fail to fork\n"); exit(1); } else if(pid == 0){ // 子進(jìn)程 // 打印子進(jìn)程的進(jìn)程ID printf("this is child, pid is : %u\n", getpid()); } else{ // 打印父進(jìn)程和其子進(jìn)程的進(jìn)程ID printf("this is parent, pid is : %u, child-pid is : %u\n", getpid(), pid); } return 0;}
程序運(yùn)行結(jié)果如下：
$ ./forkParent, PID: 2598, Sub-process PID: 2599Sub-process, PID: 2599, PPID: 2598
由于創(chuàng)建的新進(jìn)程和父進(jìn)程在系統(tǒng)看來(lái)是地位平等的兩個(gè)進(jìn)程，所以運(yùn)行機(jī)會(huì)也是一樣的，我們不能夠?qū)ζ鋱?zhí)行先后順序進(jìn)行假設(shè)，先執(zhí)行哪一個(gè)進(jìn)程取決于系統(tǒng)的調(diào)度算法。如果想要指定運(yùn)行的順序，則需要執(zhí)行額外的操作。正因?yàn)槿绱?，程序在運(yùn)行時(shí)并不能保證輸出順序和上面所描述的一致。
getpid() 是獲得當(dāng)前進(jìn)程的pid，而 getppid() 則是獲得父進(jìn)程的 id。
父子進(jìn)程的共享資源
子進(jìn)程完全復(fù)制了父進(jìn)程的地址空間的內(nèi)容，包括堆棧段和數(shù)據(jù)段的內(nèi)容。子進(jìn)程并沒有復(fù)制代碼段，而是和父進(jìn)程共用代碼段。這樣做是存在其合理依據(jù)的，因?yàn)樽舆M(jìn)程可能執(zhí)行不同的流程，那么就會(huì)改變數(shù)據(jù)段和堆棧段，因此需要分開存儲(chǔ)父子進(jìn)程各自的數(shù)據(jù)段和堆棧段。但是代碼段是只讀的，不存在被修改的問(wèn)題，因此這一個(gè)段可以讓父子進(jìn)程共享，以節(jié)省存儲(chǔ)空間，如下圖所示。
下面給出一個(gè)示例來(lái)說(shuō)明這個(gè)問(wèn)題。該程序定義了一個(gè)全局變量 global、一個(gè)局部變量 stack 和一個(gè)指針 heap。該指針用來(lái)指向一塊動(dòng)態(tài)分配的內(nèi)存區(qū)域。之后，該程序創(chuàng)建一個(gè)子進(jìn)程，在子進(jìn)程中修改 global、stack 和動(dòng)態(tài)分配的內(nèi)存中變量的值。然后在父子進(jìn)程中分別打印出這些變量的值。由于父子進(jìn)程的運(yùn)行順序是不確定的，因此我們先讓父進(jìn)程額外休眠2秒，以保證子進(jìn)程先運(yùn)行。
#include #include #include // 全局變量，在數(shù)據(jù)段中int global;int main(){ pid_t pid; int stack = 1; // 局部變量，在棧中 int __ heap; heap = (int __)malloc(sizeof(int)); // 動(dòng)態(tài)分配的內(nèi)存，在堆中 __heap = 2; pid = fork(); // 創(chuàng)建一個(gè)子進(jìn)程 if(pid < 0){ // 創(chuàng)建子進(jìn)程失敗 printf("fail to fork\n"); exit(1); } else if(pid == 0){ // 子進(jìn)程，改變各變量的值 global++; // 修改棧、堆和數(shù)據(jù)段 stack++; (__heap)++; printf("the child, data : %d, stack : %d, heap : %d\n", global, stack, __heap); exit(0); // 子進(jìn)程運(yùn)行結(jié)束 } // 父進(jìn)程休眠2秒鐘，保證子進(jìn)程先運(yùn)行 sleep(2); // 輸出結(jié)果 printf("the parent, data : %d, stack : %d, heap : %d\n", global, stack, __heap); return 0;}
程序運(yùn)行效果如下：
$ ./forkIn sub-process, global: 2, stack: 2, heap: 3In parent-process, global: 1, stack: 1, heap: 2
由于父進(jìn)程休眠了2秒鐘，子進(jìn)程先于父進(jìn)程運(yùn)行，因此會(huì)先在子進(jìn)程中修改數(shù)據(jù)段和堆棧段中的內(nèi)容。因此不難看出，子進(jìn)程對(duì)這些數(shù)據(jù)段和堆棧段中內(nèi)容的修改并不會(huì)影響到父進(jìn)程的進(jìn)程環(huán)境。
fork()函數(shù)的出錯(cuò)情況
有兩種情況可能會(huì)導(dǎo)致fork()函數(shù)出錯(cuò)：
系統(tǒng)中已經(jīng)有太多的進(jìn)程存在了
調(diào)用fork()函數(shù)的用戶進(jìn)程太多了
一般情況下，系統(tǒng)都會(huì)對(duì)一個(gè)用戶所創(chuàng)建的進(jìn)程數(shù)加以限制。如果操作系統(tǒng)不對(duì)其加限制，那么惡意用戶可以利用這一缺陷攻擊系統(tǒng)。下面是一個(gè)利用進(jìn)程的特性編寫的一個(gè)病毒程序，該程序是一個(gè)死循環(huán)，在循環(huán)中不斷調(diào)用fork()函數(shù)來(lái)創(chuàng)建子進(jìn)程，直到系統(tǒng)中不能容納如此多的進(jìn)程而崩潰為止。下圖展示了這種情況：
#include int main(){ while(1) fork(); /__ 不斷地創(chuàng)建子進(jìn)程，使系統(tǒng)中進(jìn)程溢滿 __/ return 0;}
創(chuàng)建共享空間的子進(jìn)程
進(jìn)程在創(chuàng)建一個(gè)新的子進(jìn)程之后，子進(jìn)程的地址空間完全和父進(jìn)程分開。父子進(jìn)程是兩個(gè)獨(dú)立的進(jìn)程，接受系統(tǒng)調(diào)度和分配系統(tǒng)資源的機(jī)會(huì)均等，因此父進(jìn)程和子進(jìn)程更像是一對(duì)兄弟。如果父子進(jìn)程共用父進(jìn)程的地址空間，則子進(jìn)程就不是獨(dú)立于父進(jìn)程的。
Linux環(huán)境下提供了一個(gè)與 fork() 函數(shù)類似的函數(shù)，也可以用來(lái)創(chuàng)建一個(gè)子進(jìn)程，只不過(guò)新進(jìn)程與父進(jìn)程共用父進(jìn)程的地址空間，其函數(shù)原型如下：
#include pid_t vfork(void);
vfork() 和 fork() 函數(shù)的區(qū)別有以下兩點(diǎn)：
vfork() 函數(shù)產(chǎn)生的子進(jìn)程和父進(jìn)程完全共享地址空間，包括代碼段、數(shù)據(jù)段和堆棧段，子進(jìn)程對(duì)這些共享資源所做的修改，可以影響到父進(jìn)程。由此可知，vfork() 函數(shù)與其說(shuō)是產(chǎn)生了一個(gè)進(jìn)程，還不如說(shuō)是產(chǎn)生了一個(gè)線程。
vfork() 函數(shù)產(chǎn)生的子進(jìn)程一定比父進(jìn)程先運(yùn)行，也就是說(shuō)父進(jìn)程調(diào)用了 vfork() 函數(shù)后會(huì)等待子進(jìn)程運(yùn)行后再運(yùn)行。
下面的示例程序用來(lái)驗(yàn)證以上兩點(diǎn)。在子進(jìn)程中，我們先讓其休眠 2 秒以釋放 CPU 控制權(quán)，在前面的 fork() 示例代碼中我們已經(jīng)知道這樣會(huì)導(dǎo)致其他線程先運(yùn)行，也就是說(shuō)如果休眠后父進(jìn)程先運(yùn)行的話，則第 1 點(diǎn)則為假;否則為真。第 2 點(diǎn)為真，則會(huì)先執(zhí)行子進(jìn)程，那么全局變量便會(huì)被修改，如果第 1 點(diǎn)為真，那么后執(zhí)行的父進(jìn)程也會(huì)輸出與子進(jìn)程相同的內(nèi)容。代碼如下：
//@file vfork.c//@brief vfork() usage#include #include #include int global = 1;int main(void){ pid_t pid; int stack = 1; int __heap; heap = (int ___________malloc(sizeof(int)); ___________eap = 1; pid = vfork(); if (pid < 0) { perror("fail to vfork"); exit(-1); } else if (pid == 0) { //sub-process, change values sleep(2);//release cpu controlling global = 999; stack = 888; ___________eap = 777; //print all values printf("In sub-process, global: %d, stack: %d, heap: %d\n",global,stack,___________eap); exit(0); } else { //parent-process printf("In parent-process, global: %d, stack: %d, heap: %d\n",global,stack,___________eap); } return 0;}
程序運(yùn)行效果如下：
$ ./vforkIn sub-process, global: 999, stack: 888, heap: 777In parent-process, global: 999, stack: 888, heap: 777
在函數(shù)內(nèi)部調(diào)用vfork
在使用 vfork() 函數(shù)時(shí)應(yīng)該注意不要在任何函數(shù)中調(diào)用 vfork() 函數(shù)。下面的示例是在一個(gè)非 main 函數(shù)中調(diào)用了 vfork() 函數(shù)。該程序定義了一個(gè)函數(shù) f1()，該函數(shù)內(nèi)部調(diào)用了 vfork() 函數(shù)。之后，又定義了一個(gè)函數(shù) f2()，這個(gè)函數(shù)沒有實(shí)際的意義，只是用來(lái)覆蓋函數(shù) f1() 調(diào)用時(shí)的棧幀。main 函數(shù)中先調(diào)用 f1() 函數(shù)，接著調(diào)用 f2() 函數(shù)。
#include #include #include int f1(void){ vfork(); return 0;}int f2(int a, int b){ return a+b;}int main(void){ int c; f1(); c = f2(1,2); printf("%d\n",c); return 0;}
程序運(yùn)行效果如下：
$ ./vfork3Segmentation fault (core dumped)
通過(guò)上面的程序運(yùn)行結(jié)果可以看出，一個(gè)進(jìn)程運(yùn)行正常，打印出了預(yù)期結(jié)果，而另一個(gè)進(jìn)程似乎出了問(wèn)題，發(fā)生了段錯(cuò)誤。出現(xiàn)這種情況的原因可以用下圖來(lái)分析一下：
左邊這張圖說(shuō)明調(diào)用 vfork() 之后產(chǎn)生了一個(gè)子進(jìn)程，并且和父進(jìn)程共享堆棧段，兩個(gè)進(jìn)程都要從 f1() 函數(shù)返回。由于子進(jìn)程先于父進(jìn)程運(yùn)行，所以子進(jìn)程先從 f1() 函數(shù)中返回，并且調(diào)用 f2() 函數(shù)，其棧幀覆蓋了原來(lái) f1() 函數(shù)的棧幀。當(dāng)子進(jìn)程運(yùn)行結(jié)束，父進(jìn)程開始運(yùn)行時(shí)，就出現(xiàn)了右圖的情景，父進(jìn)程需要從 f1() 函數(shù)返回，但是 f1() 函數(shù)的棧幀已經(jīng)被 f2() 函數(shù)的所替代，因此就會(huì)出現(xiàn)父進(jìn)程返回出錯(cuò)，發(fā)生段錯(cuò)誤的情況。
由此可知，使用 vfork() 函數(shù)之后，子進(jìn)程對(duì)父進(jìn)程的影響是巨大的，其同步措施勢(shì)在必行。
退出進(jìn)程
當(dāng)一個(gè)進(jìn)程需要退出時(shí)，需要調(diào)用退出函數(shù)。Linux 環(huán)境下使用 exit() 函數(shù)退出進(jìn)程，其函數(shù)原型如下：
#include void exit(int status);
exit() 函數(shù)的參數(shù)表示進(jìn)程的退出狀態(tài)，這個(gè)狀態(tài)的值是一個(gè)整型，保存在全局變量 $ ? 中，在 shell 中可以通過(guò) echo $? 來(lái)檢查退出狀態(tài)值。
注意：這個(gè)退出函數(shù)會(huì)深入內(nèi)核注銷掉進(jìn)程的內(nèi)核數(shù)據(jù)結(jié)構(gòu)，并且釋放掉進(jìn)程的資源。
exit函數(shù)與內(nèi)核函數(shù)的關(guān)系
exit 函數(shù)是一個(gè)標(biāo)準(zhǔn)的庫(kù)函數(shù)，其內(nèi)部封裝了 Linux 系統(tǒng)調(diào)用 exit() 函數(shù)。兩者的主要區(qū)別在于 exit() 函數(shù)會(huì)在用戶空間做一些善后工作，例如清理用戶的 I/O 緩沖區(qū)，將其內(nèi)容寫入 磁盤文件等，之后才進(jìn)入內(nèi)核釋放用戶進(jìn)程的地址空間;而 exit() 函數(shù)直接進(jìn)入內(nèi)核釋放用戶進(jìn)程的地址空間，所有用戶空間的緩沖區(qū)內(nèi)容都將丟失。
設(shè)置進(jìn)程所有者
每個(gè)進(jìn)程都有兩個(gè)用戶 ID，實(shí)際用戶 ID 和有效用戶 ID。通常這兩個(gè) ID 的值是相等的，其取值為進(jìn)程所有者的用戶 ID。但是，在有些場(chǎng)合需要改變進(jìn)程的有效用戶 ID。Linux 環(huán)境下使用 setuid() 函數(shù)改變一個(gè)進(jìn)程的實(shí)際用戶ID和有效用戶ID，其函數(shù)原型如下：
#include int setuid(uid_t uid);
setuid() 函數(shù)的參數(shù)表示改變后的新用戶 ID，如果成功修改當(dāng)前進(jìn)程的實(shí)際用戶 ID 和有效用戶 ID，函數(shù)返回值為 0;如果失敗，則返回 -1。只有兩種用戶可以修改進(jìn)程的實(shí)際用戶 ID 和有效用戶 ID：
根用戶：根用戶可以將進(jìn)程的實(shí)際用戶 ID 和有效用戶 ID 更換。
其他用戶：其該用戶的用戶 ID 等于進(jìn)程的實(shí)際用戶 ID 或者保存的用戶 ID。
也就是說(shuō)，用戶可以將自己的有效用戶 ID 改回去。這種情況多出現(xiàn)于下面的情況：一個(gè)進(jìn)程需要具有某種權(quán)限，所以將其有效用戶 ID 設(shè)置為具有這種權(quán)限的用戶 ID，當(dāng)進(jìn)程不需要這種權(quán)限時(shí)，進(jìn)程還原自己之前的有效用戶 ID，使自己的權(quán)限復(fù)原。下面給出一個(gè)修改的示例：
#include #include #include int main(void){ FILE __fp; uid_t uid; uid_t euid; uid = getuid(); /__ 得到進(jìn)程的實(shí)際用戶ID __/ euid = geteuid(); /__ 得到進(jìn)程的有效用戶ID __/ printf("the uid is : %d\n", uid); printf("the euid is : %d\n", euid); if(setuid(8000) == -1){ /__ 改變進(jìn)程的實(shí)際用戶ID和有效用戶ID __/ perror("fail to set uid"); exit(1); } printf("after changing\n"); uid = getuid(); /__ 再次得到進(jìn)程的實(shí)際用戶ID __/ euid = geteuid(); /__ 再次得到進(jìn)程的有效用戶ID __/ printf("the uid is : %d\n", uid); printf("the euid is : %d\n", euid); return 0;}
程序運(yùn)行效果如下：
$./setuidthe uid is : 0the euid is : 0after changingthe uid is : 8000the euid is : 8000
本節(jié)參考：
《后臺(tái)開發(fā)：核心技術(shù)與應(yīng)用實(shí)踐》
《Linux+C程序設(shè)計(jì)大全》十一章：進(jìn)程控制
9. 孤兒進(jìn)程和僵尸進(jìn)程
基本概念
我們知道在 Unix/Linux 中，正常情況下，子進(jìn)程是通過(guò)父進(jìn)程創(chuàng)建的，子進(jìn)程在創(chuàng)建新的進(jìn)程。子進(jìn)程的結(jié)束和父進(jìn)程的運(yùn)行是一個(gè)異步過(guò)程，即父進(jìn)程永遠(yuǎn)無(wú)法預(yù)測(cè)子進(jìn)程 到底什么時(shí)候結(jié)束。當(dāng)一個(gè)進(jìn)程完成它的工作終止之后，它的父進(jìn)程需要調(diào)用 wait() 或者 waitpid() 系統(tǒng)調(diào)用取得子進(jìn)程的終止?fàn)顟B(tài)。
孤兒進(jìn)程：一個(gè)父進(jìn)程退出，而它的一個(gè)或多個(gè)子進(jìn)程還在運(yùn)行，那么那些子進(jìn)程將成為孤兒進(jìn)程。孤兒進(jìn)程將被 init 進(jìn)程(進(jìn)程號(hào)為1)所收養(yǎng)，并由 init 進(jìn)程對(duì)它們完成狀態(tài)收集工作____。____
僵尸進(jìn)程：一個(gè)進(jìn)程使用 fork 創(chuàng)建子進(jìn)程，如果子進(jìn)程退出，而父進(jìn)程并沒有調(diào)用 wait 或 waitpid 獲取子進(jìn)程的狀態(tài)信息，那么子進(jìn)程的進(jìn)程描述符仍然保存在系統(tǒng)中。這種進(jìn)程稱之為僵尸進(jìn)程。
問(wèn)題及危害
Unix 提供了一種機(jī)制可以保證只要父進(jìn)程想知道子進(jìn)程結(jié)束時(shí)的狀態(tài)信息，就可以得到。這種機(jī)制就是：在每個(gè)進(jìn)程退出的時(shí)候，內(nèi)核釋放該進(jìn)程所有的資源，包括打開的文件，占用的內(nèi)存等。但是仍然為其保留一定的信息(包括進(jìn)程號(hào) the process ID，退出狀態(tài) the termination status of the process，運(yùn)行時(shí)間 the amount of CPU time taken by the process 等)。直到父進(jìn)程通過(guò) wait / waitpid 來(lái)取時(shí)才釋放。但這樣就導(dǎo)致了問(wèn)題，如果進(jìn)程不調(diào)用 wait / waitpid 的話， 那么保留的那段信息就不會(huì)釋放，其進(jìn)程號(hào)就會(huì)一直被占用，但是系統(tǒng)所能使用的進(jìn)程號(hào)是有限的，如果大量的產(chǎn)生僵死進(jìn)程，將因?yàn)闆]有可用的進(jìn)程號(hào)而導(dǎo)致系統(tǒng)不能產(chǎn)生新的進(jìn)程。此即為僵尸進(jìn)程的危害，應(yīng)當(dāng)避免。
孤兒進(jìn)程是沒有父進(jìn)程的進(jìn)程，孤兒進(jìn)程這個(gè)重任就落到了 init 進(jìn)程身上，init 進(jìn)程就好像是一個(gè)民政局，專門負(fù)責(zé)處理孤兒進(jìn)程的善后工作。每當(dāng)出現(xiàn)一個(gè)孤兒進(jìn)程的時(shí)候，內(nèi)核就把孤 兒進(jìn)程的父進(jìn)程設(shè)置為 init，而 init 進(jìn)程會(huì)循環(huán)地 wait() 它的已經(jīng)退出的子進(jìn)程。這樣，當(dāng)一個(gè)孤兒進(jìn)程凄涼地結(jié)束了其生命周期的時(shí)候，init 進(jìn)程就會(huì)代表黨和政府出面處理它的一切善后工作。因此孤兒進(jìn)程并不會(huì)有什么危害。
任何一個(gè)子進(jìn)程(init除外)在exit() 之后，并非馬上就消失掉，而是留下一個(gè)稱為僵尸進(jìn)程 (Zombie) 的數(shù)據(jù)結(jié)構(gòu)，等待父進(jìn)程處理。這是每個(gè)子進(jìn)程在結(jié)束時(shí)都要經(jīng)過(guò)的階段。如果子進(jìn)程在exit()之后，父進(jìn)程沒有來(lái)得及處理，這時(shí)用 ps 命令就能看到子進(jìn)程的狀態(tài)是 Z。如果父進(jìn)程能及時(shí)處理，可能用 ps 命令就來(lái)不及看到子進(jìn)程的僵尸狀態(tài)，但這并不等于子進(jìn)程不經(jīng)過(guò)僵尸狀態(tài)。如果父進(jìn)程在子進(jìn)程結(jié)束之前退出，則子進(jìn)程將由 init 接管。init 將會(huì)以父進(jìn)程的身份對(duì)僵尸狀態(tài)的子進(jìn)程進(jìn)行處理。
僵尸進(jìn)程危害場(chǎng)景：
例如有個(gè)進(jìn)程，它定期的產(chǎn)生一個(gè)子進(jìn)程，這個(gè)子進(jìn)程需要做的事情很少，做完它該做的事情之后就退出了，因此這個(gè)子進(jìn)程的生命周期很短，但是，父進(jìn)程只管生成新的子進(jìn)程，至于子進(jìn)程退出之后的事情，則一概不聞不問(wèn)，這樣，系統(tǒng)運(yùn)行上一段時(shí)間之后，系統(tǒng)中就會(huì)存在很多的僵死進(jìn)程，倘若用 ps 命令查看的話，就會(huì)看到很多狀態(tài)為 Z 的進(jìn)程。嚴(yán)格地來(lái)說(shuō)，僵死進(jìn)程并不是問(wèn)題的根源，罪魁禍?zhǔn)资钱a(chǎn)生出大量僵死進(jìn)程的那個(gè)父進(jìn)程。因此，當(dāng)我們尋求如何消滅系統(tǒng)中大量的僵死進(jìn)程時(shí)，答案就是把產(chǎn)生大 量僵死進(jìn)程的那個(gè)元兇槍斃掉(也就是通過(guò) kill 發(fā)送 SIGTERM 或者 SIGKILL 信號(hào)啦)。槍斃了元兇進(jìn)程之后，它產(chǎn)生的僵死進(jìn)程就變成了孤兒進(jìn)程，這些孤兒進(jìn)程會(huì)被 init 進(jìn)程接管，init 進(jìn)程會(huì) wait() 這些孤兒進(jìn)程，釋放它們占用的系統(tǒng)進(jìn)程表中的資源，這樣，這些已經(jīng)僵死的孤兒進(jìn)程就能瞑目而去了。
測(cè)試代碼
孤兒進(jìn)程測(cè)試程序如下所示：
#include #include #include #include int main(){ pid_t pid; //創(chuàng)建一個(gè)進(jìn)程 pid = fork(); //創(chuàng)建失敗 if (pid < 0) { perror("fork error:"); exit(1); } //子進(jìn)程 if (pid == 0) { printf("I am the child process.\n"); //輸出進(jìn)程ID和父進(jìn)程ID printf("pid: %d\tppid:%d\n",getpid(),getppid()); printf("I will sleep five seconds.\n"); //睡眠5s，保證父進(jìn)程先退出 sleep(5); printf("pid: %d\tppid:%d\n",getpid(),getppid()); printf("child process is exited.\n"); } //父進(jìn)程 else { printf("I am father process.\n"); //父進(jìn)程睡眠1s，保證子進(jìn)程輸出進(jìn)程id sleep(1); printf("father process is exited."); } return 0;}
僵尸進(jìn)程測(cè)試程序如下所示：
#include #include #include #include int main(){ pid_t pid; pid = fork(); if (pid < 0) { perror("fork error:"); exit(1); } else if (pid == 0) { printf("I am child process.I am exiting.\n"); exit(0); } printf("I am father process.I will sleep two seconds\n"); //等待子進(jìn)程先退出 sleep(2); //輸出進(jìn)程信息 system("ps -o pid,ppid,state,tty,command"); printf("father process is exiting.\n"); return 0;}
測(cè)試結(jié)果如下所示：
僵尸進(jìn)程解決辦法
通過(guò)信號(hào)機(jī)制
子進(jìn)程退出時(shí)向父進(jìn)程發(fā)送SIGCHILD信號(hào)，父進(jìn)程處理SIGCHILD信號(hào)。在信號(hào)處理函數(shù)中調(diào)用wait進(jìn)行處理僵尸進(jìn)程
fork兩次
將子進(jìn)程成為孤兒進(jìn)程，從而其的父進(jìn)程變?yōu)?init 進(jìn)程，通過(guò) init 進(jìn)程可以處理僵尸進(jìn)程
10. 守護(hù)進(jìn)程
Linux Daemon(守護(hù)進(jìn)程)是運(yùn)行在后臺(tái)的一種特殊進(jìn)程。它獨(dú)立于控制終端并且周期性地執(zhí)行某種任務(wù)或等待處理某些發(fā)生的事件。它不需要用戶輸入就能運(yùn)行而且提供某種服務(wù)，不是對(duì)整個(gè)系統(tǒng)就是對(duì)某個(gè)用戶程序提供服務(wù)。Linux系統(tǒng)的大多數(shù)服務(wù)器就是通過(guò)守護(hù)進(jìn)程實(shí)現(xiàn)的。常見的守護(hù)進(jìn)程包括系統(tǒng)日志進(jìn)程syslogd、 web服務(wù)器httpd、郵件服務(wù)器sendmail和數(shù)據(jù)庫(kù)服務(wù)器mysqld等。
守護(hù)進(jìn)程一般在系統(tǒng)啟動(dòng)時(shí)開始運(yùn)行，除非強(qiáng)行終止，否則直到系統(tǒng)關(guān)機(jī)都保持運(yùn)行。守護(hù)進(jìn)程經(jīng)常以超級(jí)用戶(root)權(quán)限運(yùn)行，因?yàn)樗鼈円褂锰厥獾亩丝?1-1024)或訪問(wèn)某些特殊的資源。
一個(gè)守護(hù)進(jìn)程的父進(jìn)程是init進(jìn)程，因?yàn)樗嬲母高M(jìn)程在fork出子進(jìn)程后就先于子進(jìn)程exit退出了，所以它是一個(gè)由init繼承的孤兒進(jìn)程。守護(hù)進(jìn)程是非交互式程序，沒有控制終端，所以任何輸出，無(wú)論是向標(biāo)準(zhǔn)輸出設(shè)備stdout還是標(biāo)準(zhǔn)出錯(cuò)設(shè)備stderr的輸出都需要特殊處理。
守護(hù)進(jìn)程的名稱通常以d結(jié)尾，比如sshd、xinetd、crond等
編寫守護(hù)進(jìn)程的一般步驟步驟：
在父進(jìn)程中執(zhí)行 fork 并 exit 推出;
在子進(jìn)程中調(diào)用 setsid 函數(shù)創(chuàng)建新的會(huì)話;
在子進(jìn)程中調(diào)用 chdir 函數(shù)，讓根目錄 / 成為子進(jìn)程的工作目錄;
在子進(jìn)程中調(diào)用umask函數(shù)，設(shè)置進(jìn)程的umask 為 0;
在子進(jìn)程中關(guān)閉任何不需要的文件描述符。
11. 上下文切換
上下文切換，有時(shí)也稱做進(jìn)程切換或任務(wù)切換，是指CPU從一個(gè)進(jìn)程或線程切換到另一個(gè)進(jìn)程或線程。在操作系統(tǒng)中，CPU 切換到另一個(gè)進(jìn)程需要保存當(dāng)前進(jìn)程的狀態(tài)并恢復(fù)另一個(gè)進(jìn)程的狀態(tài)：當(dāng)前運(yùn)行任務(wù)轉(zhuǎn)為就緒(或者掛起、刪除)狀態(tài)，另一個(gè)被選定的就緒任務(wù)成為當(dāng)前任務(wù)
三、死鎖
資源分類：(1)可重用資源;(2)消耗資源
1. 什么是死鎖
造成死鎖的原因就是多個(gè)線程或進(jìn)程對(duì)同一個(gè)資源的爭(zhēng)搶或相互依賴。一個(gè)最簡(jiǎn)單的解釋就是你去面試，面試官問(wèn)你告訴我什么是死鎖，我就錄用你，你回答面試官你錄用我，我告訴你。
如果一個(gè)進(jìn)程集合里面的每個(gè)進(jìn)程都在等待只能由這個(gè)集合中的其他一個(gè)進(jìn)程(包括他自身)才能引發(fā)的事件，這種情況就是死鎖。
這個(gè)定義可能有點(diǎn)拗口，下面用一個(gè)簡(jiǎn)單例子說(shuō)明。
資源 A、B，進(jìn)程 C、D 描述如下：
資源 A 和資源 B，都是不可剝奪資源，現(xiàn)在進(jìn)程 C 已經(jīng)申請(qǐng)了資源 A，進(jìn)程 D 也申請(qǐng)了資源 B，進(jìn)程 C 接下來(lái)的操作需要用到資源 B，而進(jìn)程 D 恰好也在申請(qǐng)資源A，進(jìn)程 C、D 都得不到接下來(lái)的資源，那么就引發(fā)了死鎖。
然后套用回去定義：如果一個(gè)進(jìn)程集合里面(進(jìn)程 C 和進(jìn)程 D)的每個(gè)進(jìn)程(進(jìn)程 C 和進(jìn)程 D)都在等待只能由這個(gè)集合中的其他一個(gè)進(jìn)程(對(duì)于進(jìn)程 C，他在等進(jìn)程 D;對(duì)于進(jìn)程 D，他在等進(jìn)程 C)才能引發(fā)的事件(釋放相應(yīng)資源)。
這里的資源包括了軟的資源(代碼塊)和硬的資源(例如掃描儀)。資源一般可以分兩種：可剝奪資源(Preemptable)和不可剝奪資源 (Nonpreemptable)。一般來(lái)說(shuō)對(duì)于由可剝奪資源引起的死鎖可以由系統(tǒng)的重新分配資源來(lái)解決，所以一般來(lái)說(shuō)大家說(shuō)的死鎖都是由于不可剝奪資源所引起的。
2. 死鎖的必要條件
互斥：每個(gè)資源要么已經(jīng)分配給了一個(gè)進(jìn)程，要么就是可用的。
占有和等待：已經(jīng)得到了某個(gè)資源的進(jìn)程可以再請(qǐng)求新的資源。
不可搶占：已經(jīng)分配給一個(gè)進(jìn)程的資源不能強(qiáng)制性地被搶占，它只能被占有它的進(jìn)程顯式地釋放。
循環(huán)等待：有兩個(gè)或者兩個(gè)以上的進(jìn)程組成一條環(huán)路，該環(huán)路中的每個(gè)進(jìn)程都在等待下一個(gè)進(jìn)程所占有的資源。
3. 死鎖的處理方法
1. 處理死鎖的策略
鴕鳥策略
把頭埋在沙子里，假裝根本沒發(fā)生問(wèn)題。
因?yàn)榻鉀Q死鎖問(wèn)題的代價(jià)很高，因此鴕鳥策略這種不采取任務(wù)措施的方案會(huì)獲得更高的性能。當(dāng)發(fā)生死鎖時(shí)不會(huì)對(duì)用戶造成多大影響，或發(fā)生死鎖的概率很低，可以采用鴕鳥策略。
大多數(shù)操作系統(tǒng)，包括 Unix，Linux 和 Windows，處理死鎖問(wèn)題的辦法僅僅是忽略它。
檢測(cè)死鎖并且恢復(fù)。
仔細(xì)地對(duì)資源進(jìn)行動(dòng)態(tài)分配，以避免死鎖。
通過(guò)破除死鎖四個(gè)必要條件之一，來(lái)防止死鎖產(chǎn)生。
2. 死鎖檢測(cè)與死鎖恢復(fù)
不試圖阻止死鎖，而是當(dāng)檢測(cè)到死鎖發(fā)生時(shí)，采取措施進(jìn)行恢復(fù)。
(一)每種類型一個(gè)資源的死鎖檢測(cè)
上圖為資源分配圖，其中方框表示資源，圓圈表示進(jìn)程。資源指向進(jìn)程表示該資源已經(jīng)分配給該進(jìn)程，進(jìn)程指向資源表示進(jìn)程請(qǐng)求獲取該資源。
圖 a 可以抽取出環(huán)，__ b，它滿足了環(huán)路等待條件，因此會(huì)發(fā)生死鎖。
每種類型一個(gè)資源的死鎖檢測(cè)算法是通過(guò)檢測(cè)有向圖是否存在環(huán)來(lái)實(shí)現(xiàn)，從一個(gè)節(jié)點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索，對(duì)訪問(wèn)過(guò)的節(jié)點(diǎn)進(jìn)行標(biāo)記，如果訪問(wèn)了已經(jīng)標(biāo)記的節(jié)點(diǎn)，就表示有向圖存在環(huán)，也就是檢測(cè)到死鎖的發(fā)生。
(二)每種類型多個(gè)資源的死鎖檢測(cè)
上圖中，有三個(gè)進(jìn)程四個(gè)資源，每個(gè)數(shù)據(jù)代表的含義如下：
E 向量：資源總量
A 向量：資源剩余量
C 矩陣：每個(gè)進(jìn)程所擁有的資源數(shù)量，每一行都代表一個(gè)進(jìn)程擁有資源的數(shù)量
R 矩陣：每個(gè)進(jìn)程請(qǐng)求的資源數(shù)量
進(jìn)程 P1 和 P2 所請(qǐng)求的資源都得不到滿足，只有進(jìn)程 P3 可以，讓 P3 執(zhí)行，之后釋放 P3 擁有的資源，此時(shí) A = (2 2 2 0)。P2 可以執(zhí)行，執(zhí)行后釋放 P2 擁有的資源，A = (4 2 2 1) 。P1 也可以執(zhí)行。所有進(jìn)程都可以順利執(zhí)行，沒有死鎖。
算法總結(jié)如下：
每個(gè)進(jìn)程最開始時(shí)都不被標(biāo)記，執(zhí)行過(guò)程有可能被標(biāo)記。當(dāng)算法結(jié)束時(shí)，任何沒有被標(biāo)記的進(jìn)程都是死鎖進(jìn)程。
尋找一個(gè)沒有標(biāo)記的進(jìn)程 Pi，它所請(qǐng)求的資源小于等于 A。
如果找到了這樣一個(gè)進(jìn)程，那么將 C 矩陣的第 i 行向量加到 A 中，標(biāo)記該進(jìn)程，并轉(zhuǎn)回 1。
如果沒有這樣一個(gè)進(jìn)程，算法終止。
(三)死鎖恢復(fù)
利用搶占恢復(fù)
利用回滾恢復(fù)
通過(guò)殺死進(jìn)程恢復(fù)
3. 死鎖預(yù)防
在程序運(yùn)行之前預(yù)防發(fā)生死鎖，確保系統(tǒng)永遠(yuǎn)不會(huì)進(jìn)入死鎖狀態(tài)。
(一)破壞互斥條件
例如假脫機(jī)打印機(jī)技術(shù)允許若干個(gè)進(jìn)程同時(shí)輸出，唯一真正請(qǐng)求物理打印機(jī)的進(jìn)程是打印機(jī)守護(hù)進(jìn)程。(把互斥地封裝成可以同時(shí)訪問(wèn)的，例如：打印機(jī)的緩存)
(二)破壞占有和等待條件
一種實(shí)現(xiàn)方式是規(guī)定所有進(jìn)程在開始執(zhí)行前請(qǐng)求所需要的全部資源。
但是，這種策略也有如下缺點(diǎn)：
在許多情況下，一個(gè)進(jìn)程在執(zhí)行之前不可能知道它所需要的全部資源。這是由于進(jìn)程在執(zhí)行時(shí)是動(dòng)態(tài)的，不可預(yù)測(cè)的;
資源利用率低。無(wú)論所分資源何時(shí)用到，一個(gè)進(jìn)程只有在占有所需的全部資源后才能執(zhí)行。即使有些資源最后才被該進(jìn)程用到一次，但該進(jìn)程在生存期間卻一直占有它們，造成長(zhǎng)期占著不用的狀況。這顯然是一種極大的資源浪費(fèi);
降低了進(jìn)程的并發(fā)性。因?yàn)橘Y源有限，又加上存在浪費(fèi)，能分配到所需全部資源的進(jìn)程個(gè)數(shù)就必然少了。
(三)破壞不可搶占條件
允許進(jìn)程強(qiáng)行從占有者那里奪取某些資源。就是說(shuō)，當(dāng)一個(gè)進(jìn)程已占有了某些資源，它又申請(qǐng)新的資源，但不能立即被滿足時(shí)，它必須釋放所占有的全部資源，以后再重新申請(qǐng)。它所釋放的資源可以分配給其它進(jìn)程。這就相當(dāng)于該進(jìn)程占有的資源被隱蔽地強(qiáng)占了。這種預(yù)防死鎖的方法實(shí)現(xiàn)起來(lái)困難，會(huì)降低系統(tǒng)性能。
(四)破壞循環(huán)等待
實(shí)行資源有序分配策略。采用這種策略，即把資源事先分類編號(hào)，按號(hào)分配，使進(jìn)程在申請(qǐng)，占用資源時(shí)不會(huì)形成環(huán)路。所有進(jìn)程對(duì)資源的請(qǐng)求必須嚴(yán)格按資源序號(hào)遞增的順序提出。進(jìn)程占用了小號(hào)資源，才能申請(qǐng)大號(hào)資源，就不會(huì)產(chǎn)生環(huán)路，從而預(yù)防了死鎖。這種策略與前面的策略相比，資源的利用率和系統(tǒng)吞吐量都有很大提高，但是也存在以下缺點(diǎn)：
限制了進(jìn)程對(duì)資源的請(qǐng)求，同時(shí)給系統(tǒng)中所有資源合理編號(hào)也是件困難事，并增加了系統(tǒng)開銷;
為了遵循按編號(hào)申請(qǐng)的次序，暫不使用的資源也需要提前申請(qǐng)，從而增加了進(jìn)程對(duì)資源的占用時(shí)間。
4. 死鎖避免
在程序運(yùn)行時(shí)避免發(fā)生死鎖，在使用前進(jìn)行判斷，只允許不會(huì)出現(xiàn)死鎖的進(jìn)程請(qǐng)求資源。
(一)安全狀態(tài)
圖 a 的第二列 Has 表示已擁有的資源數(shù)，第三列 Max 表示總共需要的資源數(shù)，F(xiàn)ree 表示還有可以使用的資源數(shù)。從圖 a 開始出發(fā)，先讓 B 擁有所需的所有資源(圖 b)，運(yùn)行結(jié)束后釋放 B，此時(shí) Free 變?yōu)?5(圖 c);接著以同樣的方式運(yùn)行 C 和 A，使得所有進(jìn)程都能成功運(yùn)行，因此可以稱圖 a 所示的狀態(tài)時(shí)安全的。
定義：如果沒有死鎖發(fā)生，并且即使所有進(jìn)程突然請(qǐng)求對(duì)資源的最大需求，也仍然存在某種調(diào)度次序能夠使得每一個(gè)進(jìn)程運(yùn)行完畢，則稱該狀態(tài)是安全的。
安全狀態(tài)的檢測(cè)與死鎖的檢測(cè)類似，因?yàn)榘踩珷顟B(tài)必須要求不能發(fā)生死鎖。下面的銀行家算法與死鎖檢測(cè)算法非常類似，可以結(jié)合著做參考對(duì)比。
(二)單個(gè)資源的銀行家算法
一個(gè)小城鎮(zhèn)的銀行家，他向一群客戶分別承諾了一定的貸款額度，算法要做的是判斷對(duì)請(qǐng)求的滿足是否會(huì)進(jìn)入不安全狀態(tài)，如果是，就拒絕請(qǐng)求;否則予以分配。
不安全狀態(tài)，因此算法會(huì)拒絕之前的請(qǐng)求，從而避免進(jìn)入圖 c 中的狀態(tài)。
(三)多個(gè)資源的銀行家算法
有五個(gè)進(jìn)程，四個(gè)資源。左邊的圖表示已經(jīng)分配的資源，右邊的圖表示還需要分配的資源。最右邊的 E、P 以及 A 分別表示：總資源、已分配資源以及可用資源，注意這三個(gè)為向量，而不是具體數(shù)值，例如 A=(1020)，表示 4 個(gè)資源分別還剩下 1/0/2/0。
檢查一個(gè)狀態(tài)是否安全的算法如下：
查找右邊的矩陣是否存在一行小于等于向量 A。如果不存在這樣的行，那么系統(tǒng)將會(huì)發(fā)生死鎖，狀態(tài)是不安全的。
假若找到這樣一行，將該進(jìn)程標(biāo)記為終止，并將其已分配資源加到 A 中。
重復(fù)以上兩步，直到所有進(jìn)程都標(biāo)記為終止，則狀態(tài)時(shí)安全的。
如果一個(gè)狀態(tài)不是安全的，需要拒絕進(jìn)入這個(gè)狀態(tài)。
4. 如何在寫程序的時(shí)候就避免死鎖
所謂的死鎖呢，發(fā)生的主要原因在于了有多個(gè)進(jìn)程去競(jìng)爭(zhēng)資源，也就是同時(shí)去搶占。
可以自己寫一個(gè)支持多線程的消息管理類，單開一個(gè)線程訪問(wèn)獨(dú)占資源，其它線程用消息交互實(shí)現(xiàn)間接訪問(wèn)。這種機(jī)制適應(yīng)性強(qiáng)、效率高，更適合多核環(huán)境。
四、內(nèi)存管理
1. 虛擬內(nèi)存
虛擬內(nèi)存的目的是為了讓物理內(nèi)存擴(kuò)充成更大的邏輯內(nèi)存，從而讓程序獲得更多的可用內(nèi)存。
為了更好的管理內(nèi)存，操作系統(tǒng)將內(nèi)存抽象成地址空間。每個(gè)程序擁有自己的地址空間，這個(gè)地址空間被分割成多個(gè)塊，每一塊稱為一頁(yè)。這些頁(yè)被映射到物理內(nèi)存，但不需要映射到連續(xù)的物理內(nèi)存，也不需要所有頁(yè)都必須在物理內(nèi)存中。當(dāng)程序引用到一部分不在物理內(nèi)存中的地址空間時(shí)，由硬件執(zhí)行必要的映射，將缺失的部分裝入物理內(nèi)存并重新執(zhí)行失敗的指令。
從上面的描述中可以看出，虛擬內(nèi)存允許程序不用將地址空間中的每一頁(yè)都映射到物理內(nèi)存，也就是說(shuō)一個(gè)程序不需要全部調(diào)入內(nèi)存就可以運(yùn)行，這使得有限的內(nèi)存運(yùn)行大程序稱為可能。例如有一臺(tái)計(jì)算機(jī)可以產(chǎn)生 16 位地址，那么一個(gè)程序的地址空間范圍是 0~64K。該計(jì)算機(jī)只有 32KB 的物理內(nèi)存，虛擬內(nèi)存技術(shù)允許該計(jì)算機(jī)運(yùn)行一個(gè) 64K 大小的程序。
2. 分頁(yè)系統(tǒng)地址映射
內(nèi)存管理單元(MMU)：管理著地址空間和物理內(nèi)存的轉(zhuǎn)換。
頁(yè)表(Page table)：頁(yè)(地址空間)和頁(yè)框(物理內(nèi)存空間)的映射表。例如下圖中，頁(yè)表的第 0 個(gè)表項(xiàng)為 010，表示第 0 個(gè)頁(yè)映射到第 2 個(gè)頁(yè)框。頁(yè)表項(xiàng)的最后一位用來(lái)標(biāo)記頁(yè)是否在內(nèi)存中。
下圖的頁(yè)表存放著 16 個(gè)頁(yè)，這 16 個(gè)頁(yè)需要用 4 個(gè)比特位來(lái)進(jìn)行索引定位。因此對(duì)于虛擬地址(0010 000000000100)，前 4 位是用來(lái)存儲(chǔ)頁(yè)面號(hào)，而后 12 位存儲(chǔ)在頁(yè)中的偏移量。
(0010 000000000100)根據(jù)前 4 位得到頁(yè)號(hào)為 2，讀取表項(xiàng)內(nèi)容為(110 1)，它的前 3 為為頁(yè)框號(hào)，最后 1 位表示該頁(yè)在內(nèi)存中。最后映射得到物理內(nèi)存地址為(110 000000000100)。
3. 頁(yè)面置換算法
在程序運(yùn)行過(guò)程中，如果要訪問(wèn)的頁(yè)面不在內(nèi)存中，就發(fā)生缺頁(yè)中斷從而將該頁(yè)調(diào)入內(nèi)存中。此時(shí)如果內(nèi)存已無(wú)空閑空間，系統(tǒng)必須從內(nèi)存中調(diào)出一個(gè)頁(yè)面到磁盤對(duì)換區(qū)中來(lái)騰出空間。
頁(yè)面置換算法和緩存淘汰策略類似，可以將內(nèi)存看成磁盤的緩存。在緩存系統(tǒng)中，緩存的大小有限，當(dāng)有新的緩存到達(dá)時(shí)，需要淘汰一部分已經(jīng)存在的緩存，這樣才有空間存放新的緩存數(shù)據(jù)。
頁(yè)面置換算法的主要目標(biāo)是使頁(yè)面置換頻率最低(也可以說(shuō)缺頁(yè)率最低)。
1. 最佳
Optimal
所選擇的被換出的頁(yè)面將是最長(zhǎng)時(shí)間內(nèi)不再被訪問(wèn)，通?？梢员ＷC獲得最低的缺頁(yè)率。
是一種理論上的算法，因?yàn)闊o(wú)法知道一個(gè)頁(yè)面多長(zhǎng)時(shí)間不再被訪問(wèn)。
舉例：一個(gè)系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并有如下頁(yè)面引用序列：
開始運(yùn)行時(shí)，先將 7, 0, 1 三個(gè)頁(yè)面裝入內(nèi)存。當(dāng)進(jìn)程要訪問(wèn)頁(yè)面 2 時(shí)，產(chǎn)生缺頁(yè)中斷，會(huì)將頁(yè)面 7 換出，因?yàn)轫?yè)面 7 再次被訪問(wèn)的時(shí)間最長(zhǎng)。
2. 最近最久未使用
LRU, Least Recently Used
雖然無(wú)法知道將來(lái)要使用的頁(yè)面情況，但是可以知道過(guò)去使用頁(yè)面的情況。LRU 將最近最久未使用的頁(yè)面換出。
為了實(shí)現(xiàn) LRU，需要在內(nèi)存中維護(hù)一個(gè)所有頁(yè)面的鏈表。當(dāng)一個(gè)頁(yè)面被訪問(wèn)時(shí)，將這個(gè)頁(yè)面移到鏈表表頭。這樣就能保證鏈表表尾的頁(yè)面時(shí)最近最久未訪問(wèn)的。
因?yàn)槊看卧L問(wèn)都需要更新鏈表，因此這種方式實(shí)現(xiàn)的 LRU 代價(jià)很高。
3. 最近未使用
NRU, Not Recently Used
每個(gè)頁(yè)面都有兩個(gè)狀態(tài)位：R 與 M，當(dāng)頁(yè)面被訪問(wèn)時(shí)設(shè)置頁(yè)面的 R=1，當(dāng)頁(yè)面被修改時(shí)設(shè)置 M=1。其中 R 位會(huì)定時(shí)被清零?？梢詫㈨?yè)面分成以下四類：
R=0，M=0
R=0，M=1
R=1，M=0
R=1，M=1
當(dāng)發(fā)生缺頁(yè)中斷時(shí)，NRU 算法隨機(jī)地從類編號(hào)最小的非空類中挑選一個(gè)頁(yè)面將它換出。
NRU 優(yōu)先換出已經(jīng)被修改的臟頁(yè)面(R=0，M=1)，而不是被頻繁使用的干凈頁(yè)面(R=1，M=0)。
4. 先進(jìn)先出
FIFO, First In First Out
選擇換出的頁(yè)面是最先進(jìn)入的頁(yè)面。
該算法會(huì)將那些經(jīng)常被訪問(wèn)的頁(yè)面也被換出，從而使缺頁(yè)率升高。
5. 第二次機(jī)會(huì)算法
FIFO 算法可能會(huì)把經(jīng)常使用的頁(yè)面置換出去，為了避免這一問(wèn)題，對(duì)該算法做一個(gè)簡(jiǎn)單的修改：
當(dāng)頁(yè)面被訪問(wèn) (讀或?qū)? 時(shí)設(shè)置該頁(yè)面的 R 位為 1。需要替換的時(shí)候，檢查最老頁(yè)面的 R 位。如果 R 位是 0，那么這個(gè)頁(yè)面既老又沒有被使用，可以立刻置換掉;如果是 1，就將 R 位清 0，并把該頁(yè)面放到鏈表的尾端，修改它的裝入時(shí)間使它就像剛裝入的一樣，然后繼續(xù)從鏈表的頭部開始搜索。
6. 時(shí)鐘
Clock
第二次機(jī)會(huì)算法需要在鏈表中移動(dòng)頁(yè)面，降低了效率。時(shí)鐘算法使用環(huán)形鏈表將頁(yè)面鏈接起來(lái)，再使用一個(gè)指針指向最老的頁(yè)面。
4. 分段
虛擬內(nèi)存采用的是分頁(yè)技術(shù)，也就是將地址空間劃分成固定大小的頁(yè)，每一頁(yè)再與內(nèi)存進(jìn)行映射。
下圖為一個(gè)編譯器在編譯過(guò)程中建立的多個(gè)表，有 4 個(gè)表是動(dòng)態(tài)增長(zhǎng)的，如果使用分頁(yè)系統(tǒng)的一維地址空間，動(dòng)態(tài)增長(zhǎng)的特點(diǎn)會(huì)導(dǎo)致覆蓋問(wèn)題的出現(xiàn)。
分段的做法是把每個(gè)表分成段，一個(gè)段構(gòu)成一個(gè)獨(dú)立的地址空間。每個(gè)段的長(zhǎng)度可以不同，并且可以動(dòng)態(tài)增長(zhǎng)。
5. 段頁(yè)式
程序的地址空間劃分成多個(gè)擁有獨(dú)立地址空間的段，每個(gè)段上的地址空間劃分成大小相同的頁(yè)。這樣既擁有分段系統(tǒng)的共享和保護(hù)，又擁有分頁(yè)系統(tǒng)的虛擬內(nèi)存功能。
6. 分頁(yè)與分段的比較
對(duì)程序員的透明性：分頁(yè)透明，但是分段需要程序員顯示劃分每個(gè)段。
地址空間的維度：分頁(yè)是一維地址空間，分段是二維的。
大小是否可以改變：頁(yè)的大小不可變，段的大小可以動(dòng)態(tài)改變。
出現(xiàn)的原因：分頁(yè)主要用于實(shí)現(xiàn)虛擬內(nèi)存，從而獲得更大的地址空間;分段主要是為了使程序和數(shù)據(jù)可以被劃分為邏輯上獨(dú)立的地址空間并且有助于共享和保護(hù)。
五、設(shè)備管理
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面上的磁場(chǎng)轉(zhuǎn)換為電信號(hào)(讀)，或者將電信號(hào)轉(zhuǎn)換為盤面的磁場(chǎng)(寫);
制動(dòng)手臂(Actuator arm)：用于在磁道之間移動(dòng)磁頭;
主軸(Spindle)：使整個(gè)盤面轉(zhuǎn)動(dòng)。
2. 磁盤調(diào)度算法
讀寫一個(gè)磁盤塊的時(shí)間的影響因素有：
旋轉(zhuǎn)時(shí)間(主軸旋轉(zhuǎn)磁盤，使得磁頭移動(dòng)到適當(dāng)?shù)纳葏^(qū)上)
尋道時(shí)間(制動(dòng)手臂移動(dòng)，使得磁頭移動(dòng)到適當(dāng)?shù)拇诺郎?
實(shí)際的數(shù)據(jù)傳輸時(shí)間
其中，尋道時(shí)間最長(zhǎng)，因此磁盤調(diào)度的主要目標(biāo)是使磁盤的平均尋道時(shí)間最短。
1. 先來(lái)先服務(wù)
FCFS, First Come First Served
按照磁盤請(qǐng)求的順序進(jìn)行調(diào)度
公平對(duì)待所有進(jìn)程
在有很多進(jìn)程的情況下，接近隨機(jī)調(diào)度的性能
優(yōu)點(diǎn)是公平和簡(jiǎn)單。缺點(diǎn)也很明顯，因?yàn)槲磳?duì)尋道做任何優(yōu)化，使平均尋道時(shí)間可能較長(zhǎng)。
2. 最短尋道時(shí)間優(yōu)先
SSTF, Shortest Seek Time First
優(yōu)先調(diào)度與當(dāng)前磁頭所在磁道距離最近的磁道。
雖然平均尋道時(shí)間比較低，但是不夠公平。如果新到達(dá)的磁道請(qǐng)求總是比一個(gè)在等待的磁道請(qǐng)求近，那么在等待的磁道請(qǐng)求會(huì)一直等待下去，也就是出現(xiàn)饑餓現(xiàn)象。具體來(lái)說(shuō)，兩邊的磁道請(qǐng)求更容易出現(xiàn)饑餓現(xiàn)象。
3. 電梯算法
SCAN
電梯總是保持一個(gè)方向運(yùn)行，直到該方向沒有請(qǐng)求為止，然后改變運(yùn)行方向。
電梯算法(掃描算法)和電梯的運(yùn)行過(guò)程類似，總是按一個(gè)方向來(lái)進(jìn)行磁盤調(diào)度，直到該方向上沒有未完成的磁盤請(qǐng)求，然后改變方向。
因?yàn)榭紤]了移動(dòng)方向，因此所有的磁盤請(qǐng)求都會(huì)被滿足，解決了 SSTF 的饑餓問(wèn)題。
六、鏈接
1. 編譯系統(tǒng)
以下是一個(gè) hello.c 程序：
#include int main(){ printf("hello, world\n"); return 0;}
在 Unix 系統(tǒng)上，由編譯器把源文件轉(zhuǎn)換為目標(biāo)文件。
gcc -o hello hello.c
這個(gè)過(guò)程大致如下：
1. 預(yù)處理階段 (Preprocessing phase)
預(yù)處理(cpp)根據(jù)以字符 # 開頭的命令，修改原始的 C 程序，生成擴(kuò)展名為 .i 的文件。
$ gcc -E hello.c -o hello.i
2. 編譯階段 (Compilation phase)
編譯器(cc1)將文本文件 hello.i 翻譯成文本文件 hello.s，它包含一個(gè)匯編語(yǔ)言程序。
$ gcc -S hello.i -o hello.s
3. 匯編階段 (Assembly phase)
編譯器(as)將 hello.s 翻譯成機(jī)器語(yǔ)言指令，把這些指令打包成一種叫做可重定位目標(biāo)程序(relocatable object program)的格式，并將結(jié)果保存在目標(biāo)文件 hello.o 中。
$ as hello.s -o hello.o
4. 鏈接階段 (Linking phase)
printf 函數(shù)是標(biāo)準(zhǔn) C 庫(kù)中的一個(gè)函數(shù)，在 printf.o 這個(gè)單獨(dú)預(yù)編譯好的目標(biāo)文件中。連接器(ld)將 printf.o 和 hello.o 合并，結(jié)果得到 hello 可執(zhí)行目標(biāo)文件。
$ gcc hello.o -o hello
2. 靜態(tài)鏈接
靜態(tài)連接器以一組可重定向目標(biāo)文件為輸入，生成一個(gè)完全鏈接的可執(zhí)行目標(biāo)文件作為輸出。鏈接器主要完成以下兩個(gè)任務(wù)：
符號(hào)解析：每個(gè)符號(hào)對(duì)應(yīng)于一個(gè)函數(shù)、一個(gè)全局變量或一個(gè)靜態(tài)變量，符號(hào)解析的目的是將每個(gè)符號(hào)引用與一個(gè)符號(hào)定義關(guān)聯(lián)起來(lái)。
重定位：鏈接器通過(guò)把每個(gè)符號(hào)定義與一個(gè)內(nèi)存位置關(guān)聯(lián)起來(lái)，然后修改所有對(duì)這些符號(hào)的引用，使得它們指向這個(gè)內(nèi)存位置。
3. 目標(biāo)文件
可執(zhí)行目標(biāo)文件：可以直接在內(nèi)存中執(zhí)行;
可重定向目標(biāo)文件：可與其它可重定向目標(biāo)文件在鏈接階段合并，創(chuàng)建一個(gè)可執(zhí)行目標(biāo)文件;
共享目標(biāo)文件：這是一種特殊的可重定向目標(biāo)文件，可以在運(yùn)行時(shí)被動(dòng)態(tài)加載進(jìn)內(nèi)存并鏈接;
4. 動(dòng)態(tài)鏈接
靜態(tài)庫(kù)有以下兩個(gè)問(wèn)題：
當(dāng)靜態(tài)庫(kù)更新時(shí)那么整個(gè)程序都要重新進(jìn)行鏈接;
對(duì)于 printf 這種標(biāo)準(zhǔn)函數(shù)庫(kù)，如果每個(gè)程序都要有代碼，這會(huì)極大浪費(fèi)資源。
共享庫(kù)是為了解決靜態(tài)庫(kù)的這兩個(gè)問(wèn)題而設(shè)計(jì)的，在 Linux 系統(tǒng)中通常用 .so 后綴來(lái)表示，Windows 系統(tǒng)上它們被稱為 DLL。它具有以下特點(diǎn)：
在給定的文件系統(tǒng)中一個(gè)庫(kù)只有一個(gè)文件，所有引用該庫(kù)的可執(zhí)行目標(biāo)文件都共享這個(gè)文件，它不會(huì)被復(fù)制到引用它的可執(zhí)行文件中;
在內(nèi)存中，一個(gè)共享庫(kù)的 .text 節(jié)(已編譯程序的機(jī)器代碼)的一個(gè)副本可以被不同的正在運(yùn)行的進(jìn)程共享。
操作系統(tǒng)必備基礎(chǔ)知識(shí)相關(guān)文章：
★ 計(jì)算機(jī)操作系統(tǒng)通常具有的五大功能