進(jìn)程的概念，組成，特征：

進(jìn)程：是動(dòng)態(tài)的，是程序的一次執(zhí)行過程

PCB：PCB是進(jìn)程存在的唯一標(biāo)識(shí)，當(dāng)進(jìn)程被創(chuàng)建時(shí)，操作系統(tǒng)為其創(chuàng)建PCB,當(dāng)進(jìn)程結(jié)束時(shí)，會(huì)回收其PCB。

組成：

組織：

進(jìn)程的特征：

進(jìn)程時(shí)資源分配，接受調(diào)度的基本單位

進(jìn)程的狀態(tài)與轉(zhuǎn)換：

進(jìn)程控制：

概念：進(jìn)程控制就是要實(shí)現(xiàn)進(jìn)程狀態(tài)轉(zhuǎn)換

狀態(tài)切換必改變標(biāo)志位，如何實(shí)現(xiàn)呢？我們引入了原語(yǔ)。

PCB狀態(tài)位的改變和進(jìn)入相關(guān)隊(duì)列就可以用原語(yǔ)實(shí)現(xiàn)

各原語(yǔ)可以實(shí)現(xiàn)怎樣的狀態(tài)轉(zhuǎn)換，各原語(yǔ)大概做了哪些事情（重理解，不必死記硬背）

進(jìn)程通信：

進(jìn)程通信：

進(jìn)程通信：進(jìn)程之間的信息交換

進(jìn)程通信——共享存儲(chǔ)

進(jìn)程通信——管道通信

進(jìn)程通信———消息傳遞

總結(jié)框圖：

線程概念和多線程模型：

線程：輕量級(jí)的進(jìn)程

線程是一個(gè)基本的CPU執(zhí)行單元，也是程序執(zhí)行流的最小單位。引入線程后，不僅進(jìn)程之間可以并發(fā)，進(jìn)程內(nèi)的各線程之間也可以并發(fā)，從而提升了系統(tǒng)的并發(fā)度，使得一個(gè)進(jìn)程內(nèi)也可以并發(fā)處理各種任務(wù)（如QQ視頻，文字聊天，傳文件）

引入線程后，進(jìn)程只作為除CPU之外的系統(tǒng)資源分配單元（如打印機(jī)，內(nèi)存地址空間都是分配給進(jìn)程的），進(jìn)程不再是調(diào)度的基本單位。

引入線程后發(fā)生的變化：

多線程模型：

多對(duì)一：

一對(duì)一：

多對(duì)多：

處理機(jī)調(diào)度的概念、層次：

當(dāng)有一堆任務(wù)要處理，但由于資源有限，這些事情沒法同時(shí)處理。這就需要確定某種規(guī)則來(lái)決定處理這些任務(wù)的順序，這就是調(diào)度研究的問題。

處理機(jī)調(diào)度，就是從就緒隊(duì)列中按照一定的算法選擇一個(gè)進(jìn)程并將處理機(jī)及分配給它運(yùn)行，以實(shí)現(xiàn)進(jìn)程的并發(fā)執(zhí)行。

高級(jí)調(diào)度：

中級(jí)調(diào)度：

七狀態(tài)模型：

低級(jí)調(diào)度：

三種調(diào)度的對(duì)比：

知識(shí)總結(jié)：

進(jìn)程調(diào)度的時(shí)機(jī)、切換與過程調(diào)度方式：

調(diào)度算法的評(píng)價(jià)指標(biāo)：

調(diào)度算法：

1先來(lái)先服務(wù)：

2短作業(yè)優(yōu)先：

非搶占式算法：

搶占式算法：

對(duì)比非搶占式的短作業(yè)優(yōu)先算法，顯然搶占式的這幾個(gè)指標(biāo)又要更低。

高響應(yīng)比優(yōu)先算法：

調(diào)度算法：

時(shí)間片輪轉(zhuǎn)：

如果時(shí)間片太大，使得每個(gè)進(jìn)程都可以在一個(gè)時(shí)間片內(nèi)就完成，則時(shí)間片輪轉(zhuǎn)調(diào)度算法就退化為先來(lái)先服務(wù)調(diào)度算法，并且會(huì)增大進(jìn)程響應(yīng)時(shí)間。因此，時(shí)間片不能太大。

另一方面，進(jìn)程調(diào)度，切換是有時(shí)間代價(jià)的（保存，恢復(fù)運(yùn)行環(huán)境），因此如果時(shí)間片太小，會(huì)導(dǎo)致進(jìn)程切換過于頻繁，系統(tǒng)會(huì)花大量時(shí)間來(lái)處理進(jìn)程切換，從而導(dǎo)致實(shí)際用于進(jìn)程執(zhí)行的時(shí)間比例少?？梢姇r(shí)間片也不能太小。

優(yōu)先級(jí)調(diào)度算法：

多級(jí)反饋隊(duì)列調(diào)度算法：

進(jìn)程同步，進(jìn)程互斥：

進(jìn)程互斥的軟件實(shí)現(xiàn)方法：

1單標(biāo)志法：

turn表示當(dāng)前允許進(jìn)入臨界區(qū)的進(jìn)程號(hào)，而只有當(dāng)前允許進(jìn)入臨界區(qū)的進(jìn)程在訪問了臨界區(qū)之后，才會(huì)修改turn值。也就是說(shuō)，對(duì)于臨界區(qū)的訪問，一定是按照p0->p1->p0->p1->.....這樣輪流訪問。這種必須輪流訪問帶來(lái)的問題是，如果此時(shí)允許進(jìn)入臨界區(qū)的進(jìn)程是p0，而p0一值不訪問臨界區(qū)，那么雖然此時(shí)臨界區(qū)空閑，但是不允許p1訪問。

因此，單標(biāo)志法主要存在的問題是：違背空閑讓進(jìn)原則；

2雙標(biāo)志先檢查法：

3雙標(biāo)志后檢查法：

兩個(gè)進(jìn)程都爭(zhēng)著想進(jìn)入臨界區(qū)，但是誰(shuí)也不讓誰(shuí)，最后誰(shuí)都無(wú)法進(jìn)入臨界區(qū)。

在考試時(shí)要識(shí)別出進(jìn)入?yún)^(qū)，并考慮進(jìn)程切換的情況。進(jìn)行具體問題具體分析。

4Peterson算法：

進(jìn)程互斥的硬件實(shí)現(xiàn)方法：

1.中斷屏蔽方法不適用于多處理機(jī)，某一進(jìn)程在訪問臨界區(qū)資源時(shí)，只是在該處理機(jī)下進(jìn)行關(guān)中斷，即該處理機(jī)不可進(jìn)行進(jìn)程切換。而其它處理機(jī)仍然可以訪問臨界區(qū)資源。

2.關(guān)/開中斷權(quán)限較高，只能在內(nèi)核態(tài)運(yùn)行。

不符合讓權(quán)等待：當(dāng)無(wú)法訪問臨界區(qū)時(shí)，會(huì)一直進(jìn)行條件判斷，占用處理機(jī)。

互斥鎖：

信號(hào)量機(jī)制：

檢查和上鎖用原語(yǔ)來(lái)實(shí)現(xiàn)

進(jìn)程p0：初始S=1，P操作，獲得資源，同時(shí)s--，即進(jìn)行上鎖操作；

進(jìn)程p1~pn：由于s=0，不斷執(zhí)行循環(huán)，占用處理機(jī)。

進(jìn)程p0：V操作，釋放資源，s++，解鎖，其他進(jìn)程可以獲得資源

信號(hào)量有其自身的物理含義：當(dāng)S>0時(shí)，其值表示要管理的某類資源的數(shù)量；當(dāng)S<0時(shí)，它的絕對(duì)值表示在相關(guān)隊(duì)列中等待的進(jìn)程個(gè)數(shù)。

左：如果在value--；之后S.value<0,則說(shuō)明當(dāng)前沒有相應(yīng)資源分配給當(dāng)前進(jìn)程，則把當(dāng)前進(jìn)程放入S.L指向的進(jìn)程等待隊(duì)列，從運(yùn)行態(tài)進(jìn)入阻塞態(tài)。

右：如果在S.value++之后，S.value<=0,則說(shuō)明還有進(jìn)程未獲得該資源。因此，wakeuo(S.L)喚醒阻塞隊(duì)列中的進(jìn)程，從阻塞態(tài)進(jìn)入就緒態(tài)

注：若考試中出現(xiàn)P(V),V(S)的操作，除非特別說(shuō)明，否則默認(rèn)為S為記錄型信號(hào)量。

用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥，同步，前驅(qū)關(guān)系：

訪問臨界資源的那段代碼叫作臨界區(qū)。

1.用semaphore定義的默認(rèn)為記錄型信號(hào)量

2.對(duì)不同的臨界資源，需要設(shè)置不同的互斥信號(hào)量

3.P,V操作成對(duì)出現(xiàn)

經(jīng)典同步互斥問題一：生產(chǎn)者消費(fèi)者問題

如果不互斥，則可能發(fā)生數(shù)據(jù)覆蓋。

pv操作題目分析步驟：

1.關(guān)系分析。找出題目中描述的各個(gè)流程，分析它們之間的同步互斥關(guān)系。

2.整體思路。根據(jù)各進(jìn)程的·操作流程確定P,V操作的大致順序。

有產(chǎn)品————消費(fèi)者才能消費(fèi)

緩沖區(qū)沒滿————生產(chǎn)者才能生產(chǎn)

生產(chǎn)一個(gè)產(chǎn)品，使用產(chǎn)品可以放在p,v操作之間，但會(huì)增加臨界區(qū)代碼長(zhǎng)度，影響系統(tǒng)效能。

經(jīng)典同步互斥問題二：多生產(chǎn)者多消費(fèi)者問題

原因在于：

本題中緩沖區(qū)大小為1，在任何時(shí)刻，apple,orange,plate三個(gè)同步信號(hào)量最多只有一個(gè)是1，因此在任何時(shí)刻，最多只有一個(gè)進(jìn)程的p操作不會(huì)被阻塞，并順利進(jìn)入臨界區(qū)。

經(jīng)典同步互斥問題三：吸煙者問題

經(jīng)典同步互斥問題四：讀者-寫者問題