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