操作系統(tǒng)基礎(chǔ)必備知識(shí)

時(shí)間：2024-01-27 12:28:07 懷健20由分享

今天給大家推薦兩份大佬們總結(jié)的 PDF，一份是計(jì)算機(jī)基礎(chǔ)知識(shí)，一份是操作系統(tǒng)，反正帥地看完之后，和面試官聊天，都有點(diǎn)飄了，廢話不多說,下面就讓小編帶你去看看哪些操作系統(tǒng)必備基礎(chǔ)知識(shí)，希望能幫助到大家!

操作系統(tǒng)基礎(chǔ)知識(shí)

操作系統(tǒng)是計(jì)算機(jī)體系中必不可少的核心系統(tǒng)軟件，其他軟件(如編輯程序、匯編程序、編譯程序、數(shù)據(jù)庫管理系統(tǒng)等系統(tǒng)軟件，以及大量應(yīng)用軟件)是建立在操作系統(tǒng)的基礎(chǔ)上，并在操作系統(tǒng)的統(tǒng)一管理和支持下運(yùn)行。操作系統(tǒng)是用戶與計(jì)算機(jī)之間的橋梁，用戶可以通過操作系統(tǒng)提供的功能訪問計(jì)算機(jī)系統(tǒng)中的軟硬件資源。操作系統(tǒng)的作用是通過資源管理提高計(jì)算機(jī)系統(tǒng)的效率，改善人機(jī)界面，為用戶提供有好的工作環(huán)境。有效地組織和管理系統(tǒng)中的各種軟硬件資源，合理的組織計(jì)算機(jī)系統(tǒng)工作流程，控制程序的執(zhí)行，并且向用戶提供一個(gè)良好的工作環(huán)境和友好的接口。

簡單的說，操作系統(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è)管理。下面說說處理機(jī)管理中的一些基礎(chǔ)知識(shí)。

三態(tài)模型五態(tài)模型

在多道程序環(huán)境的系統(tǒng)中，存在多個(gè)可以一起進(jìn)行(并發(fā)執(zhí)行)的進(jìn)程，因此必然會(huì)存在進(jìn)程之間的通信問題。

進(jìn)程間的通信主要有同步、互斥、調(diào)度、死鎖、信號(hào)量機(jī)制等問題

進(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)( 資源空閑就用)、無空則等( 沒有資源就等一會(huì))、有限等待(不能一直等下去)、讓權(quán)等待(實(shí)在進(jìn)不去就走吧)。

為了解決進(jì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ù)都放在這里)、消息傳遞模式(提供原語直接操作)和管道通信(在兩個(gè)進(jìn)程之間加個(gè)管道，有消息都放在那自取)。

死鎖是指兩個(gè)進(jìn)程互相要求對(duì)方已經(jīng)占用的資源，否則同時(shí)進(jìn)入臨界區(qū)的時(shí)候就會(huì)出現(xiàn)問題。就好像有的國家手里有技術(shù)但沒有勞動(dòng)力，別的國家有勞動(dòng)力沒有技術(shù)，兩個(gè)國家都不讓步，這不就出現(xià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)度的算法一般有先來先服務(wù)(FCFS，按照順序來，很好理解)、時(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)通過引入進(jìn)程和線程，使得程序能夠并發(fā)運(yùn)行。

2. 共享

共享是指系統(tǒng)中的資源可以被多個(gè)并發(fā)進(jìn)程共同使用。

有兩種共享方式：互斥共享和同時(shí)共享。

互斥共享的資源稱為臨界資源，例如打印機(jī)等，在同一時(shí)間只允許一個(gè)進(jìn)程訪問，需要用同步機(jī)制來實(shí)現(xiàn)對(duì)臨界資源的訪問。

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. 什么是堆和棧?說一下堆棧都存儲(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è)完全就不放一塊來講，數(shù)據(jù)結(jié)構(gòu)中棧和隊(duì)列才是好基友，我想新手也很容易區(qū)分。

我想需要區(qū)分的情況肯定不是在數(shù)據(jù)結(jié)構(gòu)話題下，而大多是在 OS 關(guān)于不同對(duì)象的內(nèi)存分配這塊上。

簡單講的話，在 C 語言中：

int a[N]; // go on a stackint__ a = (int __)malloc(sizeof(int) __ N); // go on a heap

7. 如何理解分布式鎖?

分布式鎖，是控制分布式系統(tǒng)之間同步訪問共享資源的一種方式。在分布式系統(tǒng)中，常常需要協(xié)調(diào)他們的動(dòng)作。如果不同的系統(tǒng)或是同一個(gè)系統(tǒng)的不同主機(jī)之間共享了一個(gè)或一組資源，那么訪問這些資源的時(shí)候，往往需要互斥來防止彼此干擾來保證一致性，在這種情況下，便需要使用到分布式鎖。

二、進(jìn)程管理

1. 進(jìn)程與線程

1. 進(jìn)程

進(jìn)程是資源分配的基本單位，用來管理資源(例如：內(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)程是資源分配的基本單位，但是線程不擁有資源，線程可以訪問隸屬進(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ù)的一致性。而線程間可以通過直接讀/寫同一進(jìn)程中的數(shù)據(jù)段(如全局變量)來進(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)程通過調(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)。

進(jìn)程只能自己阻塞自己，因?yàn)橹挥羞M(jìn)程自身才知道何時(shí)需要等待某種事件的發(fā)生

3. 進(jìn)程調(diào)度算法

不同環(huán)境的調(diào)度算法目標(biāo)不同，因此需要針對(duì)不同環(huán)境來討論調(diào)度算法。

1. 批處理系統(tǒng)

批處理系統(tǒng)沒有太多的用戶操作，在該系統(tǒng)中，調(diào)度算法目標(biāo)是保證吞吐量和周轉(zhuǎn)時(shí)間(從提交到終止的時(shí)間)。

1.1 先來先服務(wù)

先來先服務(wù) first-come first-serverd(FCFS)

按照請(qǐng)求的順序進(jìn)行調(diào)度。

有利于長作業(yè)，但不利于短作業(yè)，因?yàn)槎套鳂I(yè)必須一直等待前面的長作業(yè)執(zhí)行完畢才能執(zhí)行，而長作業(yè)又需要執(zhí)行很長時(shí)間，造成了短作業(yè)等待時(shí)間過長。

1.2 短作業(yè)優(yōu)先

短作業(yè)優(yōu)先 shortest job first(SJF)

按估計(jì)運(yùn)行時(shí)間最短的順序進(jìn)行調(diào)度。

長作業(yè)有可能會(huì)餓死，處于一直等待短作業(yè)執(zhí)行完畢的狀態(tài)。因?yàn)槿绻恢庇卸套鳂I(yè)到來，那么長作業(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 (先來先服務(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ì)花過多時(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語言中文網(wǎng)

4. 進(jìn)程同步

1. 臨界區(qū)

對(duì)臨界資源進(jìn)行訪問的那段代碼稱為臨界區(qū)。

為了互斥訪問臨界資源，每個(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 是來源于兩個(gè)荷蘭語詞匯，P() ---prolaag (荷蘭語，嘗試減少的意思)，V() ---verhoog(荷蘭語，增加的意思)

信號(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ì)成原語，不可分割，通常的做法是在執(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)者問題

問題描述：使用一個(gè)緩沖區(qū)來保存物品，只有緩沖區(qū)沒有滿，生產(chǎn)者才可以放入物品;只有緩沖區(qū)不為空，消費(fèi)者才可以拿走物品。

因?yàn)榫彌_區(qū)屬于臨界資源，因此需要使用一個(gè)互斥量 mutex 來控制對(duì)緩沖區(qū)的互斥訪問。

為了同步生產(chǎn)者和消費(fèi)者的行為，需要記錄緩沖區(qū)中物品的數(shù)量。數(shù)量可以使用信號(hào)量來進(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)量。也就是說，不能先執(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ū)加鎖了，也就無法執(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. 管程

管程 (英語：Monitors，也稱為監(jiān)視器) 是一種程序結(jié)構(gòu)，結(jié)構(gòu)內(nèi)的多個(gè)子程序(對(duì)象或模塊)形成的多個(gè)工作線程互斥訪問共享資源。

使用信號(hào)量機(jī)制實(shí)現(xiàn)的生產(chǎn)者消費(fèi)者問題需要客戶端代碼做很多控制，而管程把控制的代碼獨(dú)立出來，不僅不容易出錯(cuò)，也使得客戶端代碼調(diào)用更容易。

管程是為了解決信號(hào)量在臨界區(qū)的 PV 操作上的配對(duì)的麻煩，把配對(duì)的 PV 操作集中在一起，生成的一種并發(fā)編程方法。其中使用了條件變量這種同步機(jī)制。

c 語言不支持管程，下面的示例代碼使用了類 Pascal 語言來描述管程。示例代碼的管程提供了 insert() 和 remove() 方法，客戶端代碼通過調(diào)用這兩個(gè)方法來解決生產(chǎn)者-消費(fèi)者問題。

monitor ProducerConsumer integer i; condition c; procedure insert(); begin // ... end; procedure remove(); begin // ... end;end monitor;

管程有一個(gè)重要特性：在一個(gè)時(shí)刻只能有一個(gè)進(jìn)程使用管程。進(jìn)程在無法繼續(xù)執(zhí)行的時(shí)候不能一直占用管程，否者其它進(jìn)程永遠(yuǎn)不能使用管程。

管程引入了條件變量以及相關(guān)的操作：wait() 和 signal() 來實(shí)現(xiàn)同步操作。對(duì)條件變量執(zhí)行 wait() 操作會(huì)導(dǎo)致調(diào)用進(jìn)程阻塞，把管程讓出來給另一個(gè)進(jìn)程持有。signal() 操作用于喚醒被阻塞的進(jìn)程。

使用管程實(shí)現(xiàn)生產(chǎn)者-消費(fèi)者問題

// 管程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)典同步問題

生產(chǎn)者和消費(fèi)者問題前面已經(jīng)討論過了。

1. 讀者-寫者問題

允許多個(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)餐問題

五個(gè)哲學(xué)家圍著一張圓桌，每個(gè)哲學(xué)家面前放著食物。哲學(xué)家的生活有兩種交替活動(dòng)：吃飯以及思考。當(dāng)一個(gè)哲學(xué)家吃飯時(shí)，需要先拿起自己左右兩邊的兩根筷子，并且一次只能拿起一根筷子。

____方案一：____下面是一種錯(cuò)誤的解法，考慮到如果所有哲學(xué)家同時(shí)拿起左手邊的筷子，那么就無法拿起右手邊的筷子，造成死鎖。

#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ì)拿叉子的過程進(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ī)變化?？尚校侨f全之策

方案四：互斥訪問。正確，但每次只允許一人進(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)，來描述每個(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ì)它的訪問應(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)程同步是一種目的。也可以說，為了能夠達(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 原語的使用格式如下：

Send(Receiver,message);//發(fā)送一個(gè)消息message給接收進(jìn)程ReceiverReceive(Sender,message);//接收Sender進(jìn)程發(fā)送的消息message

間接通信

間接通信方式是指進(jìn)程之間的通信需要通過作為共享數(shù)據(jù)結(jié)構(gòu)的實(shí)體。該實(shí)體用來暫存發(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. 管道

管道是通過調(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 的同步阻塞問題，不需要進(jìn)程自己提供同步方法;

讀進(jìn)程可以根據(jù)消息類型有選擇地接收消息，而不像 FIFO 那樣只能默認(rèn)地接收。

4. 信號(hào)量

它是一個(gè)計(jì)數(shù)器，用于為多個(gè)進(jìn)程提供對(duì)共享數(shù)據(jù)對(duì)象的訪問。

5. 共享內(nèi)存

允許多個(gè)進(jìn)程共享一個(gè)給定的存儲(chǔ)區(qū)。因?yàn)閿?shù)據(jù)不需要在進(jìn)程之間復(fù)制，所以這是最快的一種 IPC。

需要使用信號(hào)量用來同步對(duì)共享存儲(chǔ)的訪問。

多個(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è)線程需要訪問同一個(gè)共享變量，誰拿到了鎖(獲得了訪問權(quán)限)，誰就可以執(zhí)行。

while輪詢的方式

在這種方式下，ThreadA 不斷地改變條件，ThreadB 不停地通過 while 語句檢測(cè)這個(gè)條件 (list.size()==5) 是否成立，從而實(shí)現(xiàn)了線程間的通信。但是這種方式會(huì)浪費(fèi) CPU 資源。

之所以說它浪費(fèi)資源，是因?yàn)?JVM 調(diào)度器將 CPU 交給 ThreadB 執(zhí)行時(shí)，它沒做啥 “有用” 的工作，只是在不斷地測(cè)試某個(gè)條件是否成立。

就類似于現(xiàn)實(shí)生活中，某個(gè)人一直看著手機(jī)屏幕是否有電話來了，而不是：在干別的事情，當(dāng)有電話來時(shí)，響鈴?fù)ㄖ猅A電話來了。

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) ：命名管道克服了管道沒有名字的限制，因此，除具有管道所具有的功能外，它還允許無親緣關(guān) 系進(jìn)程間的通信。命名管道在文件系統(tǒng)中有對(duì)應(yīng)的文件名。命名管道通過命令mkfifo或系統(tǒng)調(diào)用mkfifo來創(chuàng)建。

信號(hào)(Signal) ：信號(hào)是比較復(fù)雜的通信方式，用于通知接受進(jìn)程有某種事件發(fā)生，除了用于進(jìn)程間通信外，進(jìn)程還可以發(fā)送信號(hào)給進(jìn)程本身;Linux除了支持Unix早期信號(hào)語義函數(shù)sigal外，還支持語義符合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)承載信息量少，管道只能承載無格式字節(jié)流以及緩沖區(qū)大小受限等缺

共享內(nèi)存：使得多個(gè)進(jìn)程可以訪問同一塊內(nèi)存空間，是最快的可用IPC形式。是針對(duì)其他通信機(jī)制運(yùn)行效率較低而設(shè)計(jì)的。往往與其它通信機(jī)制，如信號(hào)量結(jié)合使用，來達(dá)到進(jìn)程間的同步及互斥。

內(nèi)存映射(mapped memory) ：內(nèi)存映射允許任何多個(gè)進(jìn)程間通信，每一個(gè)使用該機(jī)制的進(jìn)程通過把一個(gè)共享的文件映射到自己的進(jìn)程地址空間來實(shí)現(xiàn)它。

信號(hào)量(semaphore) ：主要作為進(jìn)程間以及同一進(jìn)程不同線程之間的同步手段。

套接口(Socket) ：更為一般的進(jìn)程間通信機(jī)制，可用于不同機(jī)器之間的進(jìn)程間通信。起初是由Unix系統(tǒng)的BSD分支開發(fā)出來的，但現(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)通過PCB的存在而感知進(jìn)程的存在。系統(tǒng)通過 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 )來識(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)程來創(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 是通過模擬中斷返回來實(shí)現(xiàn)特權(quán)級(jí)的變化以及創(chuàng)建 0 號(hào)進(jìn)程，通過將 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，由此可以用來區(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)程中返回，這兩次的返回值是不一樣的。

下面給出的示例程序用來創(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)看來是地位平等的兩個(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ù)段和堆棧段。但是代碼段是只讀的，不存在被修改的問題，因此這一個(gè)段可以讓父子進(jìn)程共享，以節(jié)省存儲(chǔ)空間，如下圖所示。

下面給出一個(gè)示例來說明這個(gè)問題。該程序定義了一個(gè)全局變量 global、一個(gè)局部變量 stack 和一個(gè)指針 heap。該指針用來指向一塊動(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ù)來創(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ù)，也可以用來創(chuàng)建一個(gè)子進(jìn)程，只不過新進(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ù)與其說是產(chǎn)生了一個(gè)進(jìn)程，還不如說是產(chǎn)生了一個(gè)線程。

vfork() 函數(shù)產(chǎn)生的子進(jìn)程一定比父進(jìn)程先運(yùn)行，也就是說父進(jìn)程調(diào)用了 vfork() 函數(shù)后會(huì)等待子進(jìn)程運(yùn)行后再運(yùn)行。

下面的示例程序用來驗(yàn)證以上兩點(diǎn)。在子進(jìn)程中，我們先讓其休眠 2 秒以釋放 CPU 控制權(quán)，在前面的 fork() 示例代碼中我們已經(jīng)知道這樣會(huì)導(dǎo)致其他線程先運(yùn)行，也就是說如果休眠后父進(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í)際的意義，只是用來覆蓋函數(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)

通過上面的程序運(yùn)行結(jié)果可以看出，一個(gè)進(jìn)程運(yùn)行正常，打印出了預(yù)期結(jié)果，而另一個(gè)進(jìn)程似乎出了問題，發(fā)生了段錯(cuò)誤。出現(xiàn)這種情況的原因可以用下圖來分析一下：

左邊這張圖說明調(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ù)，其棧幀覆蓋了原來 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 中可以通過 echo $? 來檢查退出狀態(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)的庫函數(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。

也就是說，用戶可以將自己的有效用戶 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)程是通過父進(jìn)程創(chuàng)建的，子進(jìn)程在創(chuàng)建新的進(jìn)程。子進(jìn)程的結(jié)束和父進(jìn)程的運(yùn)行是一個(gè)異步過程，即父進(jìn)程永遠(yuǎn)無法預(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)程。

問題及危害

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)程通過 wait / waitpid 來取時(shí)才釋放。但這樣就導(dǎo)致了問題，如果進(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)過的階段。如果子進(jìn)程在exit()之后，父進(jìn)程沒有來得及處理，這時(shí)用 ps 命令就能看到子進(jìn)程的狀態(tài)是 Z。如果父進(jìn)程能及時(shí)處理，可能用 ps 命令就來不及看到子進(jìn)程的僵尸狀態(tài)，但這并不等于子進(jìn)程不經(jīng)過僵尸狀態(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)程退出之后的事情，則一概不聞不問，這樣，系統(tǒng)運(yùn)行上一段時(shí)間之后，系統(tǒng)中就會(huì)存在很多的僵死進(jìn)程，倘若用 ps 命令查看的話，就會(huì)看到很多狀態(tài)為 Z 的進(jìn)程。嚴(yán)格地來說，僵死進(jìn)程并不是問題的根源，罪魁禍?zhǔn)资钱a(chǎn)生出大量僵死進(jìn)程的那個(gè)父進(jìn)程。因此，當(dāng)我們尋求如何消滅系統(tǒng)中大量的僵死進(jìn)程時(shí)，答案就是把產(chǎn)生大量僵死進(jìn)程的那個(gè)元兇槍斃掉(也就是通過 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)程解決辦法

通過信號(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)程，通過 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ù)器就是通過守護(hù)進(jìn)程實(shí)現(xiàn)的。常見的守護(hù)進(jìn)程包括系統(tǒng)日志進(jìn)程syslogd、 web服務(wù)器httpd、郵件服務(wù)器sendmail和數(shù)據(jù)庫服務(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)或訪問某些特殊的資源。

一個(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)程是非交互式程序，沒有控制終端，所以任何輸出，無論是向標(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è)資源的爭搶或相互依賴。一個(gè)最簡單的解釋就是你去面試，面試官問你告訴我什么是死鎖，我就錄用你，你回答面試官你錄用我，我告訴你。

如果一個(gè)進(jìn)程集合里面的每個(gè)進(jìn)程都在等待只能由這個(gè)集合中的其他一個(gè)進(jìn)程(包括他自身)才能引發(fā)的事件，這種情況就是死鎖。

這個(gè)定義可能有點(diǎn)拗口，下面用一個(gè)簡單例子說明。

資源 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 接下來的操作需要用到資源 B，而進(jìn)程 D 恰好也在申請(qǐng)資源A，進(jìn)程 C、D 都得不到接下來的資源，那么就引發(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)。一般來說對(duì)于由可剝奪資源引起的死鎖可以由系統(tǒng)的重新分配資源來解決，所以一般來說大家說的死鎖都是由于不可剝奪資源所引起的。

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ā)生問題。

因?yàn)榻鉀Q死鎖問題的代價(jià)很高，因此鴕鳥策略這種不采取任務(wù)措施的方案會(huì)獲得更高的性能。當(dāng)發(fā)生死鎖時(shí)不會(huì)對(duì)用戶造成多大影響，或發(fā)生死鎖的概率很低，可以采用鴕鳥策略。

大多數(shù)操作系統(tǒng)，包括 Unix，Linux 和 Windows，處理死鎖問題的辦法僅僅是忽略它。

檢測(cè)死鎖并且恢復(fù)。

仔細(xì)地對(duì)資源進(jìn)行動(dòng)態(tài)分配，以避免死鎖。

通過破除死鎖四個(gè)必要條件之一，來防止死鎖產(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è)算法是通過檢測(cè)有向圖是否存在環(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)，也就是檢測(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í)行過程有可能被標(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ù)

通過殺死進(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í)訪問的，例如：打印機(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è)的;

資源利用率低。無論所分資源何時(shí)用到，一個(gè)進(jìn)程只有在占有所需的全部資源后才能執(zhí)行。即使有些資源最后才被該進(jìn)程用到一次，但該進(jìn)程在生存期間卻一直占有它們，造成長期占著不用的狀況。這顯然是一種極大的資源浪費(fèi);

降低了進(jìn)程的并發(fā)性。因?yàn)橘Y源有限，又加上存在浪費(fèi)，能分配到所需全部資源的進(jìn)程個(gè)數(shù)就必然少了。

(三)破壞不可搶占條件

允許進(jìn)程強(qiáng)行從占有者那里奪取某些資源。就是說，當(dāng)一個(gè)進(jìn)程已占有了某些資源，它又申請(qǐng)新的資源，但不能立即被滿足時(shí)，它必須釋放所占有的全部資源，以后再重新申請(qǐng)。它所釋放的資源可以分配給其它進(jìn)程。這就相當(dāng)于該進(jìn)程占有的資源被隱蔽地強(qiáng)占了。這種預(yù)防死鎖的方法實(shí)現(xiàn)起來困難，會(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)爭資源，也就是同時(shí)去搶占。

可以自己寫一個(gè)支持多線程的消息管理類，單開一個(gè)線程訪問獨(dú)占資源，其它線程用消息交互實(shí)現(xià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è)塊，每一塊稱為一頁。這些頁被映射到物理內(nèi)存，但不需要映射到連續(xù)的物理內(nèi)存，也不需要所有頁都必須在物理內(nèi)存中。當(dāng)程序引用到一部分不在物理內(nèi)存中的地址空間時(shí)，由硬件執(zhí)行必要的映射，將缺失的部分裝入物理內(nèi)存并重新執(zhí)行失敗的指令。

從上面的描述中可以看出，虛擬內(nèi)存允許程序不用將地址空間中的每一頁都映射到物理內(nèi)存，也就是說一個(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. 分頁系統(tǒng)地址映射

內(nèi)存管理單元(MMU)：管理著地址空間和物理內(nèi)存的轉(zhuǎn)換。

頁表(Page table)：頁(地址空間)和頁框(物理內(nèi)存空間)的映射表。例如下圖中，頁表的第 0 個(gè)表項(xiàng)為 010，表示第 0 個(gè)頁映射到第 2 個(gè)頁框。頁表項(xiàng)的最后一位用來標(biāo)記頁是否在內(nèi)存中。

下圖的頁表存放著 16 個(gè)頁，這 16 個(gè)頁需要用 4 個(gè)比特位來進(jìn)行索引定位。因此對(duì)于虛擬地址(0010 000000000100)，前 4 位是用來存儲(chǔ)頁面號(hào)，而后 12 位存儲(chǔ)在頁中的偏移量。

(0010 000000000100)根據(jù)前 4 位得到頁號(hào)為 2，讀取表項(xiàng)內(nèi)容為(110 1)，它的前 3 為為頁框號(hào)，最后 1 位表示該頁在內(nèi)存中。最后映射得到物理內(nèi)存地址為(110 000000000100)。

3. 頁面置換算法

在程序運(yùn)行過程中，如果要訪問的頁面不在內(nèi)存中，就發(fā)生缺頁中斷從而將該頁調(diào)入內(nèi)存中。此時(shí)如果內(nèi)存已無空閑空間，系統(tǒng)必須從內(nèi)存中調(diào)出一個(gè)頁面到磁盤對(duì)換區(qū)中來騰出空間。

頁面置換算法和緩存淘汰策略類似，可以將內(nèi)存看成磁盤的緩存。在緩存系統(tǒng)中，緩存的大小有限，當(dāng)有新的緩存到達(dá)時(shí)，需要淘汰一部分已經(jīng)存在的緩存，這樣才有空間存放新的緩存數(shù)據(jù)。

頁面置換算法的主要目標(biāo)是使頁面置換頻率最低(也可以說缺頁率最低)。

1. 最佳

Optimal

所選擇的被換出的頁面將是最長時(shí)間內(nèi)不再被訪問，通常可以保證獲得最低的缺頁率。

是一種理論上的算法，因?yàn)闊o法知道一個(gè)頁面多長時(shí)間不再被訪問。

舉例：一個(gè)系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并有如下頁面引用序列：

開始運(yùn)行時(shí)，先將 7, 0, 1 三個(gè)頁面裝入內(nèi)存。當(dāng)進(jìn)程要訪問頁面 2 時(shí)，產(chǎn)生缺頁中斷，會(huì)將頁面 7 換出，因?yàn)轫撁?7 再次被訪問的時(shí)間最長。

2. 最近最久未使用

LRU, Least Recently Used

雖然無法知道將來要使用的頁面情況，但是可以知道過去使用頁面的情況。LRU 將最近最久未使用的頁面換出。

為了實(shí)現(xiàn) LRU，需要在內(nèi)存中維護(hù)一個(gè)所有頁面的鏈表。當(dāng)一個(gè)頁面被訪問時(shí)，將這個(gè)頁面移到鏈表表頭。這樣就能保證鏈表表尾的頁面時(shí)最近最久未訪問的。

因?yàn)槊看卧L問都需要更新鏈表，因此這種方式實(shí)現(xiàn)的 LRU 代價(jià)很高。

3. 最近未使用

NRU, Not Recently Used

每個(gè)頁面都有兩個(gè)狀態(tài)位：R 與 M，當(dāng)頁面被訪問時(shí)設(shè)置頁面的 R=1，當(dāng)頁面被修改時(shí)設(shè)置 M=1。其中 R 位會(huì)定時(shí)被清零。可以將頁面分成以下四類：

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, First In First Out

選擇換出的頁面是最先進(jìn)入的頁面。

該算法會(huì)將那些經(jīng)常被訪問的頁面也被換出，從而使缺頁率升高。

5. 第二次機(jī)會(huì)算法

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í)鐘算法使用環(huán)形鏈表將頁面鏈接起來，再使用一個(gè)指針指向最老的頁面。

4. 分段

虛擬內(nèi)存采用的是分頁技術(shù)，也就是將地址空間劃分成固定大小的頁，每一頁再與內(nèi)存進(jìn)行映射。

下圖為一個(gè)編譯器在編譯過程中建立的多個(gè)表，有 4 個(gè)表是動(dòng)態(tài)增長的，如果使用分頁系統(tǒng)的一維地址空間，動(dòng)態(tài)增長的特點(diǎn)會(huì)導(dǎo)致覆蓋問題的出現(xiàn)。

分段的做法是把每個(gè)表分成段，一個(gè)段構(gòu)成一個(gè)獨(dú)立的地址空間。每個(gè)段的長度可以不同，并且可以動(dòng)態(tài)增長。

5. 段頁式

程序的地址空間劃分成多個(gè)擁有獨(dú)立地址空間的段，每個(gè)段上的地址空間劃分成大小相同的頁。這樣既擁有分段系統(tǒng)的共享和保護(hù)，又擁有分頁系統(tǒng)的虛擬內(nèi)存功能。

6. 分頁與分段的比較

對(duì)程序員的透明性：分頁透明，但是分段需要程序員顯示劃分每個(gè)段。

地址空間的維度：分頁是一維地址空間，分段是二維的。

大小是否可以改變：頁的大小不可變，段的大小可以動(dòng)態(tài)改變。

出現(xiàn)的原因：分頁主要用于實(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í)間最長，因此磁盤調(diào)度的主要目標(biāo)是使磁盤的平均尋道時(shí)間最短。

1. 先來先服務(wù)

FCFS, First Come First Served

按照磁盤請(qǐng)求的順序進(jìn)行調(diào)度

公平對(duì)待所有進(jìn)程

在有很多進(jìn)程的情況下，接近隨機(jī)調(diào)度的性能

優(yōu)點(diǎn)是公平和簡單。缺點(diǎn)也很明顯，因?yàn)槲磳?duì)尋道做任何優(yōu)化，使平均尋道時(shí)間可能較長。

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)象。具體來說，兩邊的磁道請(qǐng)求更容易出現(xiàn)饑餓現(xiàn)象。

3. 電梯算法

SCAN

電梯總是保持一個(gè)方向運(yùn)行，直到該方向沒有請(qǐng)求為止，然后改變運(yùn)行方向。

電梯算法(掃描算法)和電梯的運(yùn)行過程類似，總是按一個(gè)方向來進(jìn)行磁盤調(diào)度，直到該方向上沒有未完成的磁盤請(qǐng)求，然后改變方向。

因?yàn)榭紤]了移動(dòng)方向，因此所有的磁盤請(qǐng)求都會(huì)被滿足，解決了 SSTF 的饑餓問題。

六、鏈接

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è)過程大致如下：

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è)匯編語言程序。

$ gcc -S hello.i -o hello.s

3. 匯編階段 (Assembly phase)

編譯器(as)將 hello.s 翻譯成機(jī)器語言指令，把這些指令打包成一種叫做可重定位目標(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 庫中的一個(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)起來。

重定位：鏈接器通過把每個(gè)符號(hào)定義與一個(gè)內(nèi)存位置關(guān)聯(lián)起來，然后修改所有對(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)庫有以下兩個(gè)問題：

當(dāng)靜態(tài)庫更新時(shí)那么整個(gè)程序都要重新進(jìn)行鏈接;