文章較長，建議收藏！！！

一、概述

基本特征

1. 并發(fā)

并發(fā)是指宏觀上在一段時間內(nèi)能同時運行多個程序，而并行則指同一時刻能運行多個指令。

并行需要硬件支持，如多流水線、多核處理器或者分布式計算系統(tǒng)。

操作系統(tǒng)通過引入進(jìn)程和線程，使得程序能夠并發(fā)運行。

2. 共享

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

有兩種共享方式：互斥共享和同時共享。

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

3. 虛擬

虛擬技術(shù)把一個物理實體轉(zhuǎn)換為多個邏輯實體。

主要有兩種虛擬技術(shù)：時分復(fù)用技術(shù)和空分復(fù)用技術(shù)。

多個進(jìn)程能在同一個處理器上并發(fā)執(zhí)行使用了時分復(fù)用技術(shù)，讓每個進(jìn)程輪流占有處理器，每次只執(zhí)行一小個時間片并快速切換。

虛擬內(nèi)存使用了空分復(fù)用技術(shù)，它將物理內(nèi)存抽象為地址空間，每個進(jìn)程都有各自的地址空間。地址空間的頁被映射到物理內(nèi)存，地址空間的頁并不需要全部在物理內(nèi)存中，當(dāng)使用到一個沒有在物理內(nèi)存的頁時，執(zhí)行頁面置換算法，將該頁置換到內(nèi)存中。

4. 異步

異步指進(jìn)程不是一次性執(zhí)行完畢，而是走走停停，以不可知的速度向前推進(jìn)。

基本功能

1. 進(jìn)程管理

進(jìn)程控制、進(jìn)程同步、進(jìn)程通信、死鎖處理、處理機調(diào)度等。

2. 內(nèi)存管理

內(nèi)存分配、地址映射、內(nèi)存保護(hù)與共享、虛擬內(nèi)存等。

3. 文件管理

文件存儲空間的管理、目錄管理、文件讀寫管理和保護(hù)等。

4. 設(shè)備管理

完成用戶的 I/O 請求，方便用戶使用各種設(shè)備，并提高設(shè)備的利用率。

主要包括緩沖管理、設(shè)備分配、設(shè)備處理、虛擬設(shè)備等。

系統(tǒng)調(diào)用

如果一個進(jìn)程在用戶態(tài)需要使用內(nèi)核態(tài)的功能，就進(jìn)行系統(tǒng)調(diào)用從而陷入內(nèi)核，由操作系統(tǒng)代為完成。

Linux 的系統(tǒng)調(diào)用主要有以下這些：

TaskCommands

進(jìn)程控制	fork(); exit(); wait();
進(jìn)程通信	pipe(); shmget(); mmap();
文件操作	open(); read(); write();
設(shè)備操作	ioctl(); read(); write();
信息維護(hù)	getpid(); alarm(); sleep();
安全	chmod(); umask(); chown();

大內(nèi)核和微內(nèi)核

1. 大內(nèi)核

大內(nèi)核是將操作系統(tǒng)功能作為一個緊密結(jié)合的整體放到內(nèi)核。

由于各模塊共享信息，因此有很高的性能。

2. 微內(nèi)核

由于操作系統(tǒng)不斷復(fù)雜，因此將一部分操作系統(tǒng)功能移出內(nèi)核，從而降低內(nèi)核的復(fù)雜性。移出的部分根據(jù)分層的原則劃分成若干服務(wù)，相互獨立。

在微內(nèi)核結(jié)構(gòu)下，操作系統(tǒng)被劃分成小的、定義良好的模塊，只有微內(nèi)核這一個模塊運行在內(nèi)核態(tài)，其余模塊運行在用戶態(tài)。

因為需要頻繁地在用戶態(tài)和核心態(tài)之間進(jìn)行切換，所以會有一定的性能損失。

中斷分類

1. 外中斷

由 CPU 執(zhí)行指令以外的事件引起，如 I/O 完成中斷，表示設(shè)備輸入/輸出處理已經(jīng)完成，處理器能夠發(fā)送下一個輸入/輸出請求。此外還有時鐘中斷、控制臺中斷等。

2. 異常

由 CPU 執(zhí)行指令的內(nèi)部事件引起，如非法操作碼、地址越界、算術(shù)溢出等。

3. 陷入

在用戶程序中使用系統(tǒng)調(diào)用。

二、進(jìn)程管理

進(jìn)程與線程

1. 進(jìn)程

進(jìn)程是資源分配的基本單位。

進(jìn)程控制塊?(Process Control Block, PCB)?描述進(jìn)程的基本信息和運行狀態(tài)，所謂的創(chuàng)建進(jìn)程和撤銷進(jìn)程，都是指對 PCB 的操作。

下圖顯示了 4 個程序創(chuàng)建了 4 個進(jìn)程，這 4 個進(jìn)程可以并發(fā)地執(zhí)行。

2. 線程

線程是獨立調(diào)度的基本單位。

一個進(jìn)程中可以有多個線程，它們共享進(jìn)程資源。

QQ 和瀏覽器是兩個進(jìn)程，瀏覽器進(jìn)程里面有很多線程，例如 HTTP 請求線程、事件響應(yīng)線程、渲染線程等等，線程的并發(fā)執(zhí)行使得在瀏覽器中點擊一個新鏈接從而發(fā)起 HTTP 請求時，瀏覽器還可以響應(yīng)用戶的其它事件。

3. 區(qū)別

Ⅰ 擁有資源

進(jìn)程是資源分配的基本單位，但是線程不擁有資源，線程可以訪問隸屬進(jìn)程的資源。

Ⅱ 調(diào)度

線程是獨立調(diào)度的基本單位，在同一進(jìn)程中，線程的切換不會引起進(jìn)程切換，從一個進(jìn)程中的線程切換到另一個進(jìn)程中的線程時，會引起進(jìn)程切換。

Ⅲ 系統(tǒng)開銷

由于創(chuàng)建或撤銷進(jìn)程時，系統(tǒng)都要為之分配或回收資源，如內(nèi)存空間、I/O 設(shè)備等，所付出的開銷遠(yuǎn)大于創(chuàng)建或撤銷線程時的開銷。類似地，在進(jìn)行進(jìn)程切換時，涉及當(dāng)前執(zhí)行進(jìn)程 CPU 環(huán)境的保存及新調(diào)度進(jìn)程 CPU 環(huán)境的設(shè)置，而線程切換時只需保存和設(shè)置少量寄存器內(nèi)容，開銷很小。

Ⅳ 通信方面

線程間可以通過直接讀寫同一進(jìn)程中的數(shù)據(jù)進(jìn)行通信，但是進(jìn)程通信需要借助 IPC。

進(jìn)程狀態(tài)的切換

• 就緒狀態(tài)（ready）：等待被調(diào)度

• 運行狀態(tài)（running）

• 阻塞狀態(tài)（waiting）：等待資源

應(yīng)該注意以下內(nèi)容：

• 只有就緒態(tài)和運行態(tài)可以相互轉(zhuǎn)換，其它的都是單向轉(zhuǎn)換。就緒狀態(tài)的進(jìn)程通過調(diào)度算法從而獲得 CPU 時間，轉(zhuǎn)為運行狀態(tài)；而運行狀態(tài)的進(jìn)程，在分配給它的 CPU 時間片用完之后就會轉(zhuǎn)為就緒狀態(tài)，等待下一次調(diào)度。

• 阻塞狀態(tài)是缺少需要的資源從而由運行狀態(tài)轉(zhuǎn)換而來，但是該資源不包括 CPU 時間，缺少 CPU 時間會從運行態(tài)轉(zhuǎn)換為就緒態(tài)。

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

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

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

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

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

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

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

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

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

長作業(yè)有可能會餓死，處于一直等待短作業(yè)執(zhí)行完畢的狀態(tài)。因為如果一直有短作業(yè)到來，那么長作業(yè)永遠(yuǎn)得不到調(diào)度。

1.3 最短剩余時間優(yōu)先 shortest remaining time next（SRTN）

按估計剩余時間最短的順序進(jìn)行調(diào)度。

2. 交互式系統(tǒng)

交互式系統(tǒng)有大量的用戶交互操作，在該系統(tǒng)中調(diào)度算法的目標(biāo)是快速地進(jìn)行響應(yīng)。

2.1 時間片輪轉(zhuǎn)

將所有就緒進(jìn)程按 FCFS 的原則排成一個隊列，每次調(diào)度時，把 CPU 時間分配給隊首進(jìn)程，該進(jìn)程可以執(zhí)行一個時間片。當(dāng)時間片用完時，由計時器發(fā)出時鐘中斷，調(diào)度程序便停止該進(jìn)程的執(zhí)行，并將它送往就緒隊列的末尾，同時繼續(xù)把 CPU 時間分配給隊首的進(jìn)程。

時間片輪轉(zhuǎn)算法的效率和時間片的大小有很大關(guān)系：

• 因為進(jìn)程切換都要保存進(jìn)程的信息并且載入新進(jìn)程的信息，如果時間片太小，會導(dǎo)致進(jìn)程切換得太頻繁，在進(jìn)程切換上就會花過多時間。

• 而如果時間片過長，那么實時性就不能得到保證。

2.2 優(yōu)先級調(diào)度

為每個進(jìn)程分配一個優(yōu)先級，按優(yōu)先級進(jìn)行調(diào)度。

為了防止低優(yōu)先級的進(jìn)程永遠(yuǎn)等不到調(diào)度，可以隨著時間的推移增加等待進(jìn)程的優(yōu)先級。

2.3 多級反饋隊列

一個進(jìn)程需要執(zhí)行 100?個時間片，如果采用時間片輪轉(zhuǎn)調(diào)度算法，那么需要交換 100?次。

多級隊列是為這種需要連續(xù)執(zhí)行多個時間片的進(jìn)程考慮，它設(shè)置了多個隊列，每個隊列時間片大小都不同，例如 1,2,4,8,..。進(jìn)程在第一個隊列沒執(zhí)行完，就會被移到下一個隊列。這種方式下，之前的進(jìn)程只需要交換 7 次。

每個隊列優(yōu)先權(quán)也不同，最上面的優(yōu)先權(quán)最高。因此只有上一個隊列沒有進(jìn)程在排隊，才能調(diào)度當(dāng)前隊列上的進(jìn)程。

可以將這種調(diào)度算法看成是時間片輪轉(zhuǎn)調(diào)度算法和優(yōu)先級調(diào)度算法的結(jié)合。

3. 實時系統(tǒng)

實時系統(tǒng)要求一個請求在一個確定時間內(nèi)得到響應(yīng)。

分為硬實時和軟實時，前者必須滿足絕對的截止時間，后者可以容忍一定的超時。

進(jìn)程同步

1. 臨界區(qū)

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

為了互斥訪問臨界資源，每個進(jìn)程在進(jìn)入臨界區(qū)之前，需要先進(jìn)行檢查。

//?entry?section //?critical?section; //?exit?section

2. 同步與互斥

• 同步：多個進(jìn)程按一定順序執(zhí)行；

• 互斥：多個進(jìn)程在同一時刻只有一個進(jìn)程能進(jìn)入臨界區(qū)。

3. 信號量

信號量（Semaphore）是一個整型變量，可以對其執(zhí)行 down 和 up 操作，也就是常見的 P 和 V 操作。

• down??:?如果信號量大于?0?，執(zhí)行?-1 操作；如果信號量等于?0，進(jìn)程睡眠，等待信號量大于?0；

• up?：對信號量執(zhí)行?+1 操作，喚醒睡眠的進(jìn)程讓其完成 down 操作。

down 和 up 操作需要被設(shè)計成原語，不可分割，通常的做法是在執(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ù)量可以使用信號量來進(jìn)行統(tǒng)計，這里需要使用兩個信號量：empty 記錄空緩沖區(qū)的數(shù)量，full 記錄滿緩沖區(qū)的數(shù)量。其中，empty 信號量是在生產(chǎn)者進(jìn)程中使用，當(dāng) empty 不為?0?時，生產(chǎn)者才可以放入物品；full 信號量是在消費者進(jìn)程中使用，當(dāng) full 信號量不為?0?時，消費者才可以取走物品。

注意，不能先對緩沖區(qū)進(jìn)行加鎖，再測試信號量。也就是說，不能先執(zhí)行 down(mutex)?再執(zhí)行 down(empty)。如果這么做了，那么可能會出現(xiàn)這種情況：生產(chǎn)者對緩沖區(qū)加鎖后，執(zhí)行 down(empty)?操作，發(fā)現(xiàn) empty =?0，此時生產(chǎn)者睡眠。消費者不能進(jìn)入臨界區(qū)，因為生產(chǎn)者對緩沖區(qū)加鎖了，消費者就無法執(zhí)行 up(empty)?操作，empty 永遠(yuǎn)都為?0，導(dǎo)致生產(chǎn)者永遠(yuǎn)等待下，不會釋放鎖，消費者因此也會永遠(yuǎn)等待下去。

#define?N?100 typedef?int?semaphore; semaphore?mutex?=?1; semaphore?empty?=?N; semaphore?full?=?0;void?producer()?{while(TRUE)?{int?item?=?produce_item();down(&empty);down(&mutex);insert_item(item);up(&mutex);up(&full);} }void?consumer()?{while(TRUE)?{down(&full);down(&mutex);int?item?=?remove_item();consume_item(item);up(&mutex);up(&empty);} }

4. 管程

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

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

monitor?ProducerConsumerinteger?i;condition?c;procedure?insert();begin//?...end;procedure?remove();begin//?...end; end?monitor;

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

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

使用管程實現(xiàn)生產(chǎn)者-消費者問題?

//?管程 monitor?ProducerConsumercondition?full,?empty;integer?count?:=?0;condition?c;procedure?insert(item:?integer);beginif?count?=?N?then?wait(full);insert_item(item);count?:=?count?+?1;if?count?=?1?then?signal(empty);end;function?remove:?integer;beginif?count?=?0?then?wait(empty);remove?=?remove_item;count?:=?count?-?1;if?count?=?N?-1?then?signal(full);end; end?monitor;//?生產(chǎn)者客戶端 procedure?producer beginwhile?true?dobeginitem?=?produce_item;ProducerConsumer.insert(item);end end;//?消費者客戶端 procedure?consumer beginwhile?true?dobeginitem?=?ProducerConsumer.remove;consume_item(item);end end;

經(jīng)典同步問題

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

1. 讀者-寫者問題

允許多個進(jìn)程同時對數(shù)據(jù)進(jìn)行讀操作，但是不允許讀和寫以及寫和寫操作同時發(fā)生。

一個整型變量 count 記錄在對數(shù)據(jù)進(jìn)行讀操作的進(jìn)程數(shù)量，一個互斥量 count_mutex 用于對 count 加鎖，一個互斥量 data_mutex 用于對讀寫的數(shù)據(jù)加鎖。

typedef?int?semaphore; semaphore?count_mutex?=?1; semaphore?data_mutex?=?1; int?count?=?0;void?reader()?{while(TRUE)?{down(&count_mutex);count++;if(count?==?1)?down(&data_mutex);?//?第一個讀者需要對數(shù)據(jù)進(jìn)行加鎖，防止寫進(jìn)程訪問up(&count_mutex);read();down(&count_mutex);count--;if(count?==?0)?up(&data_mutex);up(&count_mutex);} }void?writer()?{while(TRUE)?{down(&data_mutex);write();up(&data_mutex);} }

以下內(nèi)容由?@Bandi Yugandhar 提供。

The first case may result Writer to starve. This case favous Writers i.e no writer, once added to the queue, shall be kept waiting longer than absolutely necessary(only when there are readers that entered the queue before the writer).

int?readcount,?writecount;???????????????????//(initial?value?=?0) semaphore?rmutex,?wmutex,?readLock,?resource;?//(initial?value?=?1)//READER void?reader()?{ <ENTRY?Section>down(&readLock);?????????????????//??reader?is?trying?to?enterdown(&rmutex);??????????????????//???lock?to?increase?readcountreadcount++;?????????????????if?(readcount?==?1)??????????down(&resource);??????????????//if?you?are?the?first?reader?then?lock??the?resourceup(&rmutex);??????????????????//release??for?other?readersup(&readLock);?????????????????//Done?with?trying?to?access?the?resource<CRITICAL?Section> //reading?is?performed<EXIT?Section>down(&rmutex);??????????????????//reserve?exit?section?-?avoids?race?condition?with?readersreadcount--;???????????????????????//indicate?you're?leavingif?(readcount?==?0)??????????//checks?if?you?are?last?reader?leavingup(&resource);??????????????//if?last,?you?must?release?the?locked?resourceup(&rmutex);??????????????????//release?exit?section?for?other?readers }//WRITER void?writer()?{<ENTRY?Section>down(&wmutex);??????????????????//reserve?entry?section?for?writers?-?avoids?race?conditionswritecount++;????????????????//report?yourself?as?a?writer?enteringif?(writecount?==?1)?????????//checks?if?you're?first?writerdown(&readLock);???????????????//if?you're?first,?then?you?must?lock?the?readers?out.?Prevent?them?from?trying?to?enter?CSup(&wmutex);??????????????????//release?entry?section<CRITICAL?Section>down(&resource);????????????????//reserve?the?resource?for?yourself?-?prevents?other?writers?from?simultaneously?editing?the?shared?resource//writing?is?performedup(&resource);????????????????//release?file<EXIT?Section>down(&wmutex);??????????????????//reserve?exit?sectionwritecount--;????????????????//indicate?you're?leavingif?(writecount?==?0)?????????//checks?if?you're?the?last?writerup(&readLock);???????????????//if?you're?last?writer,?you?must?unlock?the?readers.?Allows?them?to?try?enter?CS?for?readingup(&wmutex);??????????????????//release?exit?section }

We can observe that every reader is forced to acquire ReadLock. On the otherhand, writers doesn’t need to lock individually. Once the first writer locks the ReadLock, it will be released only when there is no writer left in the queue.

From the both cases we observed that either reader or writer has to starve. Below solutionadds the constraint that no thread shall be allowed to starve; that is, the operation of obtaining a lock on the shared data will always terminate in a bounded amount of time.

int?readCount;??????????????????//?init?to?0;?number?of?readers?currently?accessing?resource//?all?semaphores?initialised?to?1 Semaphore?resourceAccess;???????//?controls?access?(read/write)?to?the?resource Semaphore?readCountAccess;??????//?for?syncing?changes?to?shared?variable?readCount Semaphore?serviceQueue;?????????//?FAIRNESS:?preserves?ordering?of?requests?(signaling?must?be?FIFO)void?writer() {?down(&serviceQueue);???????????//?wait?in?line?to?be?servicexs//?<ENTER>down(&resourceAccess);?????????//?request?exclusive?access?to?resource//?</ENTER>up(&serviceQueue);???????????//?let?next?in?line?be?serviced//?<WRITE>writeResource();????????????//?writing?is?performed//?</WRITE>//?<EXIT>up(&resourceAccess);?????????//?release?resource?access?for?next?reader/writer//?</EXIT> }void?reader() {?down(&serviceQueue);???????????//?wait?in?line?to?be?serviceddown(&readCountAccess);????????//?request?exclusive?access?to?readCount//?<ENTER>if?(readCount?==?0)?????????//?if?there?are?no?readers?already?reading:down(&resourceAccess);?????//?request?resource?access?for?readers?(writers?blocked)readCount++;????????????????//?update?count?of?active?readers//?</ENTER>up(&serviceQueue);???????????//?let?next?in?line?be?servicedup(&readCountAccess);????????//?release?access?to?readCount//?<READ>readResource();?????????????//?reading?is?performed//?</READ>down(&readCountAccess);????????//?request?exclusive?access?to?readCount//?<EXIT>readCount--;????????????????//?update?count?of?active?readersif?(readCount?==?0)?????????//?if?there?are?no?readers?left:up(&resourceAccess);?????//?release?resource?access?for?all//?</EXIT>up(&readCountAccess);????????//?release?access?to?readCount }

2. 哲學(xué)家進(jìn)餐問題

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

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

#define?N?5void?philosopher(int?i)?{while(TRUE)?{think();take(i);???????//?拿起左邊的筷子take((i+1)%N);?//?拿起右邊的筷子eat();put(i);put((i+1)%N);} }

為了防止死鎖的發(fā)生，可以設(shè)置兩個條件：

• 必須同時拿起左右兩根筷子；

• 只有在兩個鄰居都沒有進(jìn)餐的情況下才允許進(jìn)餐。

#define?N?5 #define?LEFT?(i?+?N?-?1)?%?N?//?左鄰居 #define?RIGHT?(i?+?1)?%?N????//?右鄰居 #define?THINKING?0 #define?HUNGRY???1 #define?EATING???2 typedef?int?semaphore; int?state[N];????????????????//?跟蹤每個哲學(xué)家的狀態(tài) semaphore?mutex?=?1;?????????//?臨界區(qū)的互斥 semaphore?s[N];??????????????//?每個哲學(xué)家一個信號量void?philosopher(int?i)?{while(TRUE)?{think();take_two(i);eat();put_two(i);} }void?take_two(int?i)?{down(&mutex);state[i]?=?HUNGRY;test(i);up(&mutex);down(&s[i]); }void?put_two(i)?{down(&mutex);state[i]?=?THINKING;test(LEFT);test(RIGHT);up(&mutex); }void?test(i)?{?????????//?嘗試拿起兩把筷子if(state[i]?==?HUNGRY?&&?state[LEFT]?!=?EATING?&&?state[RIGHT]?!=EATING)?{state[i]?=?EATING;up(&s[i]);} }

進(jìn)程通信

進(jìn)程同步與進(jìn)程通信很容易混淆，它們的區(qū)別在于：

• 進(jìn)程同步：控制多個進(jìn)程按一定順序執(zhí)行；

• 進(jìn)程通信：進(jìn)程間傳輸信息。

進(jìn)程通信是一種手段，而進(jìn)程同步是一種目的。也可以說，為了能夠達(dá)到進(jìn)程同步的目的，需要讓進(jìn)程進(jìn)行通信，傳輸一些進(jìn)程同步所需要的信息。

1. 管道

管道是通過調(diào)用 pipe 函數(shù)創(chuàng)建的，fd[0]?用于讀，fd[1]?用于寫。

#include?<unistd.h> int?pipe(int?fd[2]);

它具有以下限制：

• 只支持半雙工通信（單向交替?zhèn)鬏?#xff09;；

• 只能在父子進(jìn)程中使用。

2. FIFO

也稱為命名管道，去除了管道只能在父子進(jìn)程中使用的限制。

#include?<sys/stat.h> int?mkfifo(const?char?*path,?mode_t?mode); int?mkfifoat(int?fd,?const?char?*path,?mode_t?mode);

FIFO 常用于客戶-服務(wù)器應(yīng)用程序中，FIFO 用作匯聚點，在客戶進(jìn)程和服務(wù)器進(jìn)程之間傳遞數(shù)據(jù)。

3. 消息隊列

相比于 FIFO，消息隊列具有以下優(yōu)點：

• 消息隊列可以獨立于讀寫進(jìn)程存在，從而避免了 FIFO 中同步管道的打開和關(guān)閉時可能產(chǎn)生的困難；

• 避免了 FIFO 的同步阻塞問題，不需要進(jìn)程自己提供同步方法；

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

4. 信號量

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

5. 共享存儲

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

需要使用信號量用來同步對共享存儲的訪問。

多個進(jìn)程可以將同一個文件映射到它們的地址空間從而實現(xiàn)共享內(nèi)存。另外 XSI 共享內(nèi)存不是使用文件，而是使用使用內(nèi)存的匿名段。

6. 套接字

與其它通信機制不同的是，它可用于不同機器間的進(jìn)程通信。

三、死鎖

必要條件

• 互斥：每個資源要么已經(jīng)分配給了一個進(jìn)程，要么就是可用的。

• 占有和等待：已經(jīng)得到了某個資源的進(jìn)程可以再請求新的資源。

• 不可搶占：已經(jīng)分配給一個進(jìn)程的資源不能強制性地被搶占，它只能被占有它的進(jìn)程顯式地釋放。

• 環(huán)路等待：有兩個或者兩個以上的進(jìn)程組成一條環(huán)路，該環(huán)路中的每個進(jìn)程都在等待下一個進(jìn)程所占有的資源。

處理方法

主要有以下四種方法：

• 鴕鳥策略

• 死鎖檢測與死鎖恢復(fù)

• 死鎖預(yù)防

• 死鎖避免

鴕鳥策略

把頭埋在沙子里，假裝根本沒發(fā)生問題。

因為解決死鎖問題的代價很高，因此鴕鳥策略這種不采取任務(wù)措施的方案會獲得更高的性能。

當(dāng)發(fā)生死鎖時不會對用戶造成多大影響，或發(fā)生死鎖的概率很低，可以采用鴕鳥策略。

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

死鎖檢測與死鎖恢復(fù)

不試圖阻止死鎖，而是當(dāng)檢測到死鎖發(fā)生時，采取措施進(jìn)行恢復(fù)。

1. 每種類型一個資源的死鎖檢測

上圖為資源分配圖，其中方框表示資源，圓圈表示進(jìn)程。資源指向進(jìn)程表示該資源已經(jīng)分配給該進(jìn)程，進(jìn)程指向資源表示進(jìn)程請求獲取該資源。

圖 a 可以抽取出環(huán)，如圖 b，它滿足了環(huán)路等待條件，因此會發(fā)生死鎖。

每種類型一個資源的死鎖檢測算法是通過檢測有向圖是否存在環(huán)來實現(xiàn)，從一個節(jié)點出發(fā)進(jìn)行深度優(yōu)先搜索，對訪問過的節(jié)點進(jìn)行標(biāo)記，如果訪問了已經(jīng)標(biāo)記的節(jié)點，就表示有向圖存在環(huán)，也就是檢測到死鎖的發(fā)生。

2. 每種類型多個資源的死鎖檢測

上圖中，有三個進(jìn)程四個資源，每個數(shù)據(jù)代表的含義如下：

• E 向量：資源總量

• A 向量：資源剩余量

• C 矩陣：每個進(jìn)程所擁有的資源數(shù)量，每一行都代表一個進(jìn)程擁有資源的數(shù)量

• R 矩陣：每個進(jìn)程請求的資源數(shù)量

進(jìn)程 P1?和 P2?所請求的資源都得不到滿足，只有進(jìn)程 P3?可以，讓 P3?執(zhí)行，之后釋放 P3?擁有的資源，此時 A =?(2 2 2 0)。P2?可以執(zhí)行，執(zhí)行后釋放 P2?擁有的資源，A =?(4 2 2 1)?。P1?也可以執(zhí)行。所有進(jìn)程都可以順利執(zhí)行，沒有死鎖。

算法總結(jié)如下：

每個進(jìn)程最開始時都不被標(biāo)記，執(zhí)行過程有可能被標(biāo)記。當(dāng)算法結(jié)束時，任何沒有被標(biāo)記的進(jìn)程都是死鎖進(jìn)程。

尋找一個沒有標(biāo)記的進(jìn)程 Pi，它所請求的資源小于等于 A。

如果找到了這樣一個進(jìn)程，那么將 C 矩陣的第 i 行向量加到 A 中，標(biāo)記該進(jìn)程，并轉(zhuǎn)回 1。

如果沒有這樣一個進(jìn)程，算法終止。

3. 死鎖恢復(fù)

• 利用搶占恢復(fù)

• 利用回滾恢復(fù)

• 通過殺死進(jìn)程恢復(fù)

死鎖預(yù)防

在程序運行之前預(yù)防發(fā)生死鎖。

1. 破壞互斥條件

例如假脫機打印機技術(shù)允許若干個進(jìn)程同時輸出，唯一真正請求物理打印機的進(jìn)程是打印機守護(hù)進(jìn)程。

2. 破壞占有和等待條件

一種實現(xiàn)方式是規(guī)定所有進(jìn)程在開始執(zhí)行前請求所需要的全部資源。

3. 破壞不可搶占條件

4. 破壞環(huán)路等待

給資源統(tǒng)一編號，進(jìn)程只能按編號順序來請求資源。

死鎖避免

在程序運行時避免發(fā)生死鎖。

1. 安全狀態(tài)

圖 a 的第二列 Has 表示已擁有的資源數(shù)，第三列 Max 表示總共需要的資源數(shù)，Free 表示還有可以使用的資源數(shù)。從圖 a 開始出發(fā)，先讓 B 擁有所需的所有資源（圖 b），運行結(jié)束后釋放 B，此時 Free 變?yōu)?5（圖 c）；接著以同樣的方式運行 C 和 A，使得所有進(jìn)程都能成功運行，因此可以稱圖 a 所示的狀態(tài)時安全的。

定義：如果沒有死鎖發(fā)生，并且即使所有進(jìn)程突然請求對資源的最大需求，也仍然存在某種調(diào)度次序能夠使得每一個進(jìn)程運行完畢，則稱該狀態(tài)是安全的。

安全狀態(tài)的檢測與死鎖的檢測類似，因為安全狀態(tài)必須要求不能發(fā)生死鎖。下面的銀行家算法與死鎖檢測算法非常類似，可以結(jié)合著做參考對比。

2. 單個資源的銀行家算法

一個小城鎮(zhèn)的銀行家，他向一群客戶分別承諾了一定的貸款額度，算法要做的是判斷對請求的滿足是否會進(jìn)入不安全狀態(tài)，如果是，就拒絕請求；否則予以分配。

上圖 c 為不安全狀態(tài)，因此算法會拒絕之前的請求，從而避免進(jìn)入圖 c 中的狀態(tài)。

3. 多個資源的銀行家算法

上圖中有五個進(jìn)程，四個資源。左邊的圖表示已經(jīng)分配的資源，右邊的圖表示還需要分配的資源。最右邊的 E、P 以及 A 分別表示：總資源、已分配資源以及可用資源，注意這三個為向量，而不是具體數(shù)值，例如 A=(1020)，表示 4 個資源分別還剩下 1/0/2/0。

檢查一個狀態(tài)是否安全的算法如下：

• 查找右邊的矩陣是否存在一行小于等于向量 A。如果不存在這樣的行，那么系統(tǒng)將會發(fā)生死鎖，狀態(tài)是不安全的。

• 假若找到這樣一行，將該進(jìn)程標(biāo)記為終止，并將其已分配資源加到 A 中。

• 重復(fù)以上兩步，直到所有進(jìn)程都標(biāo)記為終止，則狀態(tài)時安全的。

如果一個狀態(tài)不是安全的，需要拒絕進(jìn)入這個狀態(tài)。

四、內(nèi)存管理

虛擬內(nèi)存

虛擬內(nèi)存的目的是為了讓物理內(nèi)存擴充成更大的邏輯內(nèi)存，從而讓程序獲得更多的可用內(nèi)存。

為了更好的管理內(nèi)存，操作系統(tǒng)將內(nèi)存抽象成地址空間。每個程序擁有自己的地址空間，這個地址空間被分割成多個塊，每一塊稱為一頁。這些頁被映射到物理內(nèi)存，但不需要映射到連續(xù)的物理內(nèi)存，也不需要所有頁都必須在物理內(nèi)存中。當(dāng)程序引用到不在物理內(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)存技術(shù)允許該計算機運行一個 64K 大小的程序。

分頁系統(tǒng)地址映射

內(nèi)存管理單元（MMU）管理著地址空間和物理內(nèi)存的轉(zhuǎn)換，其中的頁表（Page table）存儲著頁（程序地址空間）和頁框（物理內(nèi)存空間）的映射表。

一個虛擬地址分成兩個部分，一部分存儲頁面號，一部分存儲偏移量。

下圖的頁表存放著 16 個頁，這 16 個頁需要用 4 個比特位來進(jìn)行索引定位。例如對于虛擬地址（0010?000000000100），前 4 位是存儲頁面號 2，讀取表項內(nèi)容為（110 1），頁表項最后一位表示是否存在于內(nèi)存中，1 表示存在。后 12 位存儲偏移量。這個頁對應(yīng)的頁框的地址為?（110?000000000100）。

頁面置換算法

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

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

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

1. 最佳

OPT, Optimal replacement algorithm

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

是一種理論上的算法，因為無法知道一個頁面多長時間不再被訪問。

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

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

2. 最近最久未使用

LRU, Least Recently Used

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

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

因為每次訪問都需要更新鏈表，因此這種方式實現(xiàn)的 LRU 代價很高。

3. 最近未使用

NRU, Not Recently Used

每個頁面都有兩個狀態(tài)位：R 與 M，當(dāng)頁面被訪問時設(shè)置頁面的 R=1，當(dāng)頁面被修改時設(shè)置 M=1。其中 R 位會定時被清零?？梢詫㈨撁娣殖梢韵滤念?#xff1a;

• R=0，M=0

• R=0，M=1

• R=1，M=0

• R=1，M=1

當(dāng)發(fā)生缺頁中斷時，NRU 算法隨機地從類編號最小的非空類中挑選一個頁面將它換出。

NRU 優(yōu)先換出已經(jīng)被修改的臟頁面（R=0，M=1），而不是被頻繁使用的干凈頁面（R=1，M=0）。

4. 先進(jìn)先出

FIFO, First In First Out

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

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

5. 第二次機會算法

FIFO 算法可能會把經(jīng)常使用的頁面置換出去，為了避免這一問題，對該算法做一個簡單的修改：

當(dāng)頁面被訪問?(讀或?qū)??時設(shè)置該頁面的 R 位為 1。需要替換的時候，檢查最老頁面的 R 位。如果 R 位是?0，那么這個頁面既老又沒有被使用，可以立刻置換掉；如果是 1，就將 R 位清?0，并把該頁面放到鏈表的尾端，修改它的裝入時間使它就像剛裝入的一樣，然后繼續(xù)從鏈表的頭部開始搜索。

6. 時鐘

Clock

第二次機會算法需要在鏈表中移動頁面，降低了效率。時鐘算法使用環(huán)形鏈表將頁面連接起來，再使用一個指針指向最老的頁面。

分段

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

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

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

段頁式

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

分頁與分段的比較

• 對程序員的透明性：分頁透明，但是分段需要程序員顯示劃分每個段。

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

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

• 出現(xiàn)的原因：分頁主要用于實現(xiàn)虛擬內(nèi)存，從而獲得更大的地址空間；分段主要是為了使程序和數(shù)據(jù)可以被劃分為邏輯上獨立的地址空間并且有助于共享和保護(hù)。

五、設(shè)備管理

磁盤結(jié)構(gòu)

• 盤面（Platter）：一個磁盤有多個盤面；

• 磁道（Track）：盤面上的圓形帶狀區(qū)域，一個盤面可以有多個磁道；

• 扇區(qū)（Track Sector）：磁道上的一個弧段，一個磁道可以有多個扇區(qū)，它是最小的物理儲存單位，目前主要有 512 bytes 與 4 K 兩種大小；

• 磁頭（Head）：與盤面非常接近，能夠?qū)⒈P面上的磁場轉(zhuǎn)換為電信號（讀），或者將電信號轉(zhuǎn)換為盤面的磁場（寫）；

• 制動手臂（Actuator arm）：用于在磁道之間移動磁頭；

• 主軸（Spindle）：使整個盤面轉(zhuǎn)動。

磁盤調(diào)度算法

讀寫一個磁盤塊的時間的影響因素有：

• 旋轉(zhuǎn)時間（主軸轉(zhuǎn)動盤面，使得磁頭移動到適當(dāng)?shù)纳葏^(qū)上）

• 尋道時間（制動手臂移動，使得磁頭移動到適當(dāng)?shù)拇诺郎?#xff09;

• 實際的數(shù)據(jù)傳輸時間

其中，尋道時間最長，因此磁盤調(diào)度的主要目標(biāo)是使磁盤的平均尋道時間最短。

1. 先來先服務(wù)

FCFS, First Come First Served

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

優(yōu)點是公平和簡單。缺點也很明顯，因為未對尋道做任何優(yōu)化，使平均尋道時間可能較長。

2. 最短尋道時間優(yōu)先

SSTF, Shortest Seek Time First

優(yōu)先調(diào)度與當(dāng)前磁頭所在磁道距離最近的磁道。

雖然平均尋道時間比較低，但是不夠公平。如果新到達(dá)的磁道請求總是比一個在等待的磁道請求近，那么在等待的磁道請求會一直等待下去，也就是出現(xiàn)饑餓現(xiàn)象。具體來說，兩端的磁道請求更容易出現(xiàn)饑餓現(xiàn)象。

3. 電梯算法

SCAN

電梯總是保持一個方向運行，直到該方向沒有請求為止，然后改變運行方向。

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

因為考慮了移動方向，因此所有的磁盤請求都會被滿足，解決了 SSTF 的饑餓問題。

六、鏈接

編譯系統(tǒng)

以下是一個 hello.c 程序：

#include?<stdio.h>int?main() {printf("hello,?world ");return?0; }

在 Unix 系統(tǒng)上，由編譯器把源文件轉(zhuǎn)換為目標(biāo)文件。

gcc?-o?hello?hello.c

這個過程大致如下：

• 預(yù)處理階段：處理以?#?開頭的預(yù)處理命令；

• 編譯階段：翻譯成匯編文件；

• 匯編階段：將匯編文件翻譯成可重定向目標(biāo)文件；

• 鏈接階段：將可重定向目標(biāo)文件和 printf.o 等單獨預(yù)編譯好的目標(biāo)文件進(jìn)行合并，得到最終的可執(zhí)行目標(biāo)文件。

靜態(tài)鏈接

靜態(tài)鏈接器以一組可重定向目標(biāo)文件為輸入，生成一個完全鏈接的可執(zhí)行目標(biāo)文件作為輸出。鏈接器主要完成以下兩個任務(wù)：

• 符號解析：每個符號對應(yīng)于一個函數(shù)、一個全局變量或一個靜態(tài)變量，符號解析的目的是將每個符號引用與一個符號定義關(guān)聯(lián)起來。

• 重定位：鏈接器通過把每個符號定義與一個內(nèi)存位置關(guān)聯(lián)起來，然后修改所有對這些符號的引用，使得它們指向這個內(nèi)存位置。

目標(biāo)文件

• 可執(zhí)行目標(biāo)文件：可以直接在內(nèi)存中執(zhí)行；

• 可重定向目標(biāo)文件：可與其它可重定向目標(biāo)文件在鏈接階段合并，創(chuàng)建一個可執(zhí)行目標(biāo)文件；

• 共享目標(biāo)文件：這是一種特殊的可重定向目標(biāo)文件，可以在運行時被動態(tài)加載進(jìn)內(nèi)存并鏈接；

動態(tài)鏈接

靜態(tài)庫有以下兩個問題：

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

• 對于 printf 這種標(biāo)準(zhǔn)函數(shù)庫，如果每個程序都要有代碼，這會極大浪費資源。

共享庫是為了解決靜態(tài)庫的這兩個問題而設(shè)計的，在 Linux 系統(tǒng)中通常用 .so 后綴來表示，Windows 系統(tǒng)上它們被稱為 DLL。它具有以下特點：

• 在給定的文件系統(tǒng)中一個庫只有一個文件，所有引用該庫的可執(zhí)行目標(biāo)文件都共享這個文件，它不會被復(fù)制到引用它的可執(zhí)行文件中；

• 在內(nèi)存中，一個共享庫的 .text 節(jié)（已編譯程序的機器代碼）的一個副本可以被不同的正在運行的進(jìn)程共享。

?

END

作者：CyC2018

鏈接：https://github.com/CyC2018/CS-Notes

總結(jié)

以上是生活随笔為你收集整理的听说面试又挂在计算机操作系统了？仔细看看这个！！！【强烈推荐】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。