并發(fā)與并行

一組在邏輯上互相獨立的程序或程序段在執(zhí)行過程中執(zhí)行時間在客觀時間上的重疊赋荆。
并行執(zhí)行是指一組程序按獨立的，異步的速度執(zhí)行、并發(fā)執(zhí)行不等于時間上的重疊咳秉。
（并行是指同一時刻可以做多件事情，并發(fā)是指同一時間間隔內(nèi)做多件事情）

進程的概念

經(jīng)典定義：
1.進程是可以并發(fā)執(zhí)行的計算部分

2. 進程是一個獨立的鸯隅、可以調(diào)度的活動
3. 進程是一個抽象實體澜建，當(dāng)它執(zhí)行某個任務(wù)時，將需要分配和釋放各種資源
4. 一個進程是一個逐一執(zhí)行的操作

進程與程序區(qū)別
進程是動態(tài)的蝌以，程序是靜態(tài)的
進程有一定的生命周期霎奢，程序是指令的集合
一個程序可以對應(yīng)多個進程，一個進程只能對應(yīng)一個程序
程序可以作為一種軟件資源長期保存著饼灿，而進程是一次執(zhí)行過程幕侠，是暫時的

進程的五個特性
1.動態(tài)性：創(chuàng)建時產(chǎn)生，由調(diào)度而執(zhí)行碍彭，得不到資源而暫停執(zhí)行晤硕，有撤銷而消亡
2.并發(fā)性：多個進程實體同存于主存中
（引入進程的目的悼潭，程序是不能并發(fā)執(zhí)行的）
3.獨立性：進程實體是一個能獨立運行的基本單位，也是系統(tǒng)中獲得資源和獨立調(diào)度的基本單位
4.異步性：進程按各自獨立的舞箍，不可預(yù)知的速度向前推進（導(dǎo)致程序執(zhí)行的不可再現(xiàn)性）
5.結(jié)構(gòu)特征：進程實體是由程序段舰褪、數(shù)據(jù)段、進程控制塊三部分構(gòu)成疏橄，又稱進程映像/進程上下文（context）


進程的基本狀態(tài)

進程的狀態(tài)轉(zhuǎn)換圖

有些還存在兩個額外狀態(tài)：新狀態(tài)和終止?fàn)顟B(tài)

進程狀態(tài)轉(zhuǎn)換圖

進程控制塊PCB
1.概念：是操作系統(tǒng)用于記錄和刻畫進程狀態(tài)及有關(guān)信息的數(shù)據(jù)結(jié)構(gòu)占拍，也是操作系統(tǒng)控制和管理進程的主要依據(jù)。

進程控制塊

進程的控制（創(chuàng)建、撤銷彰导、阻塞與喚醒）

進程控制原語

原語：一組系統(tǒng)命令
要么全部執(zhí)行蛔翅，要么不執(zhí)行，不存在中間狀態(tài)

進程的創(chuàng)建（調(diào)用創(chuàng)建原語來實現(xiàn)）

$$進程創(chuàng)建
\begin{cases}
& \text{系統(tǒng)生成時位谋，會創(chuàng)建一些系統(tǒng)進程（用來分配系統(tǒng)資源和管理工作）}\
& \text{用戶作業(yè)山析，由操作系統(tǒng)的作業(yè)調(diào)度程序為之創(chuàng)建相應(yīng)的進程}
\end{cases}$$

進程的撤銷

1.既可撤銷具有指定標(biāo)識符的過程，又可撤銷一個優(yōu)先級中的所有進程
2.一個進程被撤銷時掏父，必須從系統(tǒng)隊列中移出笋轨，釋放并歸還所有系統(tǒng)資源，同時也有審查是否有子孫進程损同，如果有子孫進程也有一起予以撤銷

進程的阻塞和喚醒

1.當(dāng)一個進程出現(xiàn)等待事件時翩腐，該進程調(diào)用阻塞原語將自己阻塞

阻塞原語執(zhí)行過程

喚醒原語執(zhí)行過程

進程的調(diào)度

1.必要性：解決多個進程爭奪少數(shù)CPU資源的問題
2.功能：
（1）記錄系統(tǒng)中所有進程的執(zhí)行情況
（2）選擇占有CPU的進程
（3）CPU分配給進程，即進行進程上下文切換
（4）回收CPU
3.進程調(diào)度算法
先來先服務(wù)/FCFS
按照進程進入就緒隊列的先后次序選擇占用處理器的進程

注意
運行時間較長的進程先進入可能會影響到后面進程的等待時間
例：
A（3ms）膏燃，B（3ms）茂卦，C（24ms）
輸入順序1：{A，B组哩，C}
調(diào)入順序2：{C等龙，A，B}
問：兩次調(diào)入順序不同三個進程的平均等待時間伶贰？
（1）A等待0ms蛛砰，B等待3ms，C等待3+3ms黍衙，所有進程得到響應(yīng)的總共時間是9ms泥畅，三個進程的平均等待時間是9/3=3ms
（2）C等待0ms，A等待24ms琅翻，B等待24+3ms位仁，所有進程得到響應(yīng)的總共時間是0+24+27=51ms柑贞，所有進程的平均等待是51/3=17ms

優(yōu)先數(shù)調(diào)度算法
為每個進程確定一個優(yōu)先數(shù)，進程調(diào)度總是讓具有最高優(yōu)先數(shù)的進程先使用處理器（若優(yōu)先數(shù)相同則采用FCFS）

優(yōu)先數(shù)的確定
1.靜態(tài)法：進程執(zhí)行前就確定優(yōu)先數(shù)
2.動態(tài)法：隨著進程的執(zhí)行聂抢，優(yōu)先數(shù)不斷變化

提高經(jīng)常使用外圍設(shè)備的進程的優(yōu)先數(shù)（有利于并行能力）
提高較長時間未使用處理器的就緒進程的優(yōu)先數(shù)（縮短等待處理器的平均時間）

調(diào)度
1.非搶占式：優(yōu)先數(shù)高的進程占用了處理器钧嘶，等其主動讓出處理器或由于自身原因主動讓出處理器，才重新按優(yōu)先數(shù)選擇另一個進程占用處理器
2.可搶占式：某個進程在處理器上運行時琳疏，一旦有一個具有更高優(yōu)先數(shù)的進程進入就緒隊列有决，就把處理器讓給更高優(yōu)先數(shù)的進程先使用
**優(yōu)先數(shù)的確定
系統(tǒng)進程的優(yōu)先數(shù)＞用戶進程的優(yōu)先數(shù)
重要計算問題的進程優(yōu)先數(shù)＞一般計算問題的進程優(yōu)先數(shù)
交互式作業(yè)進程的優(yōu)先數(shù)＞批處理作業(yè)進程的優(yōu)先數(shù)

時間片輪轉(zhuǎn)調(diào)度算法
CPU處理時間分成固定大小的時間片，輪流來空盼，如果時間片用完進程還未結(jié)束书幕，也得重新排到就緒隊列的末尾等待再次調(diào)度

時間片輪轉(zhuǎn)調(diào)度

時間片太長$\mapsto$變成FCFS
時間片太短$\mapsto$進程上下文切換次數(shù)增加$\mapsto$加重系統(tǒng)開銷

時間片q的選擇：
q=R/N(R是系統(tǒng)對響應(yīng)時間的要求；N是進程數(shù))

多級反饋隊列調(diào)度算法/MLFQ
設(shè)置多個就緒隊列
各個隊列的優(yōu)先權(quán)不同(第一個隊列的優(yōu)先權(quán)最高我注，逐個降低)
各個隊列的時間片大小不同（優(yōu)先權(quán)越高的隊列時間片越邪粗洹）
當(dāng)前隊列的某個進程在時間片內(nèi)沒有完成就進入下一個隊列的末尾
當(dāng)某個隊列為空時才會調(diào)度下一個隊列
處理機在第i隊為謀進程服務(wù)時迟隅，如果有新進程進入優(yōu)先權(quán)較高的隊列（i之前）但骨，則處理機就去處理i之前的那個新進程了奔缠，正在運行的進程被放到i隊伍的末尾（可憐哈哈哈哈）

多級反饋隊列調(diào)度算法

優(yōu)點闷哆、
對與分時交互型短作業(yè)$\mapsto$周轉(zhuǎn)時間短
長作業(yè)$\mapsto$輪轉(zhuǎn)方式運行嘀倒，不必?fù)?dān)心長期得不到處理

4.調(diào)度算法的選擇
（1）處理器利用率（盡量讓CPU處于忙碌狀態(tài)）
（2）吞吐量
（3）等待時間（盡可能減少）
（4）響應(yīng)時間（盡可能減少）

進程的同步與互斥

進程的互斥

與時間有關(guān)的錯誤
由于并發(fā)進程執(zhí)行的隨機性灌危，由于貢獻了資源/變量，在不同時刻或執(zhí)行速度的不同或外界的影響藕帜，交替訪問資源/變量的時候可能造成結(jié)果不正確
1.臨界區(qū)：并發(fā)進程中與共享變量有關(guān)的程序段
相關(guān)臨界區(qū)：多個并發(fā)進程中涉及相同共享變量的那些程序段
2.解決方案：
如果有進程在相關(guān)臨界區(qū)執(zhí)行的時候就不讓另一個進程進入相關(guān)臨界區(qū)
任何一個進入臨界區(qū)執(zhí)行的進程必須在有限的時間內(nèi)退出臨界區(qū)
有進程退出臨界區(qū)應(yīng)讓一個等待進入臨界區(qū)的進程進入它的臨界區(qū)

1.進程互斥：若干個進程要使用一個共享資源时甚，任何時刻只允許一個進程去使用，其他要使用的進程必須等待，直到那個進程使用完后釋放資源
2.進程互斥的管理辦法：PV操作 管程

PV操作
1.信號量S
S$\geq$0時树埠，代表可供并發(fā)進程使用的資源實體數(shù)
S＜0時，|S|表示正在等待使用資源實體的進程數(shù)毕匀。
2.操作原語P V
P操作意味著請求一個資源规个，V操作意味著釋放一個資源
P操作代表阻塞進程操作，V操作代表喚醒被阻塞進程的操作
3.步驟：
$$設(shè)互斥信號量S表示臨界區(qū)\longmapsto
\begin{cases}
無并發(fā)進程進入臨界區(qū)& \text{S=1}\
有一個并發(fā)進程進入臨界區(qū)進程& \text{S=0}\
有一個進入臨界區(qū)|S|個進程在等待進入& \text{S$\leq$0}
\end{cases}$$

進程同步（異步環(huán)境下）

異步環(huán)境：互相合作的一組并發(fā)進程，由于每個進程執(zhí)行的速度不同，又相互獨立，所以需要解決一個同步的問題

1.進程同步：并發(fā)進程之間存在一種制約關(guān)系箱季，一個進程的執(zhí)行依賴另一個進程的消息，當(dāng)一個進程沒有得到另一個進程的消息時應(yīng)等待，直到消息到達時才被喚醒

進程協(xié)作

錯誤
進程A速度＞進程B，可能在B沒取走記錄時A存入新的舔涎，造成記錄丟失
進程A速度＜進程B挟冠，可能在A沒存入新的記錄時B又取走知染，造成記錄重復(fù)加工
解決方法
互通消息
2.解決進程同步：PV操作

PV操作
1.信號量S
S=0時肋僧，代表期望的消息未產(chǎn)生
S$\ne$0時，表示期望的消息已存在
2.操作原語P V
P操作測試消息是否到達，V操作發(fā)送消息
3.步驟：
$$設(shè)互斥信號量S表示臨界區(qū)\longmapsto
\begin{cases}
無并發(fā)進程進入臨界區(qū)& \text{S=1}\
有一個并發(fā)進程進入臨界區(qū)進程& \text{S=0}\
有一個進入臨界區(qū)|S|個進程在等待進入& \text{S$\leq$0}
\end{cases}$$

3.時間上的同步問題

進程通信

$$進程通信
\begin{cases}
低級& \text{PV操作}\
高級 \begin{cases} 共享存儲器系統(tǒng)\ 消息傳遞系統(tǒng) \管道通信系統(tǒng) \end{cases}
\end{cases}$$

共享存儲器系統(tǒng)

1.基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式
在這種通信方式中嫌吠，要求諸進程公用某些數(shù)據(jù)結(jié)構(gòu)止潘，進程通過它們交換信息。這種通信方式是低效的辫诅，只適于傳遞少量數(shù)據(jù)凭戴。
2.基于共享存儲區(qū)的通信方式
為了傳輸大量數(shù)據(jù)，在存儲器中劃出了一塊共享存儲區(qū)炕矮，諸進程可通過對共享存儲區(qū)中的數(shù)據(jù)進行讀或?qū)憗韺崿F(xiàn)通信簇宽。這種通信方式屬于高級通信。

消息傳遞系統(tǒng)

消息傳遞系統(tǒng)中吧享，進程間的數(shù)據(jù)交換以消息為單位

$$實現(xiàn)方式\begin{cases} 直接通信方式\ 間接通信方式 \end{cases}$$
直接通信方式
可用send原語和receive原語來實現(xiàn)進程之間的通信魏割，
這兩個原語定義如下：
send（P，消息） 把一個消息發(fā)送給進程P钢颂。
receive（Q钞它，消息） 從進程Q接收一個消息。
間接通信方式
采用間接通信方式時殊鞭，進程間發(fā)送或接收消息通過一個共享的數(shù)據(jù)結(jié)構(gòu)——信箱來進行遭垛，消息可以被理解>成信件，每個信箱有一個唯一的標(biāo)識符
間接通信方式中的“發(fā)送”和“接收”原語的形式如下：
send（A操灿，信件） 把一個信件（消息）發(fā)送給信箱A
receive（A锯仪，信件） 從信箱A接收一封信件（消息）

管道通信系統(tǒng)

1.管道，是指用于連接一個讀進程和一個寫進程趾盐，以實現(xiàn)它們之間通信的共享文件庶喜，又稱為pipe文件
2.為了協(xié)調(diào)雙方的通信，管道通信機制必須提供以下三方面的協(xié)調(diào)能力：（1）互斥救鲤；（2）同步久窟；（3）對方是否存在。

線程的概念

1.需要線程的目的：保持系統(tǒng)的并發(fā)性
2.為了減少額外開銷本缠，系統(tǒng)把進程的資源申請與調(diào)度執(zhí)行分開斥扛，線程是調(diào)度的基本單位，進程是資源申請與擁有的基本單位
3.概念：線程（Thread）是進程中的一個實體丹锹，是可獨立參與調(diào)度的基本單位
4.屬性：
并發(fā)
一個線程可以創(chuàng)建另一個
動態(tài)性（生命周期）
TCB（進程是PCB）
同一進程內(nèi)的線程共享同一地址空間
一個進程的線程對另外一個進程是不可見的
線程的通信是基于全局變量進行的
5.狀態(tài)（與進程類似）

運行
就緒
等待

線程調(diào)度

時間片輪轉(zhuǎn)算法
優(yōu)先權(quán)算法

進程與線程的區(qū)別（工廠的車間與工人）

1.進程作為資源的申請與擁有單位稀颁，線程作為調(diào)度的基本單位
2.線程在調(diào)度和切換上所花費的開銷比進程小得多
3.進程是獨立擁有資源的的一個基本單位，線程只擁有一點點運行中必要的資源
4.進程作為獨立擁有資源的基本單位楣黍，線程是獨立參與調(diào)度的基本單位

死鎖

1.概念：死鎖是多個進程因競爭資源而造成的一種僵局匾灶，若無外力作用，這些進程都將永遠不能再向前推進
2$$產(chǎn)生原因\begin{cases} 競爭資源\ 進程推進順序非法（請求與釋放資源順序不當(dāng)） \end{cases}$$

注意
以下兩種情況造成進程永遠等待不屬于我們要討論的死鎖問題：
（1）如果出現(xiàn)某個進程申請系統(tǒng)中不存在的資源或申請的資源數(shù)超過了系統(tǒng)擁有的最大資源數(shù)锡凝。
（2）由于硬件故障或程序性錯誤引起的循環(huán)等待

3.$$產(chǎn)生死鎖必要條件 \begin{cases} 互斥條件（進程互斥使用資源） \ 占有且等待條件（得不到需要的資源就不釋放占有的資源）\ 不剝奪條件（進程不能從另一進程搶奪資源）\ 循環(huán)等待條件（每個進程都在等待另一個進程所持有的資源） \end{cases}$$

4.對策：預(yù)防 避免 檢測 解除
預(yù)防
（1）靜態(tài)分配策略//破壞第二個必要條件
所謂靜態(tài)分配是指一個進程必須在執(zhí)行前就申請它所要的全部資源粘昨，并且直到它所要的資源都得到滿足后才開始執(zhí)行
（2）層次分配策略//破壞第四個必要條件
當(dāng)一個進程獲得了某一層的一個資源后，它想再申請該層中的另一個資源，必須先釋放該層中的已占用資源张肾。

避免

銀行家算法
先滿足請求資源較少的進程芭析，然后通過回收已經(jīng)完成的進程的資源，將系統(tǒng)可用資源進行積累吞瞪，以滿足請求資源較大的進程馁启。
把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金芍秆，進程向操作系統(tǒng)請求分配資源相當(dāng)于用戶向銀行家貸款惯疙，操作系統(tǒng)按照銀行家制定的規(guī)則為進程分配資源。
銀行家規(guī)則（Dijkstra）：
（1）當(dāng)一個用戶對資金的最大需求量不超過銀行家現(xiàn)有的資金時就可接納該用戶妖啥；
（2）用戶可以分期貸款霉颠，但貸款的總數(shù)不能超過最大需求量；
（3）當(dāng)銀行家現(xiàn)有的資金不能滿足用戶的尚需貸款數(shù)時荆虱，對用戶的貸款可推遲支付蒿偎，但總能使用戶在有限的時間里得到貸款；
（4）當(dāng)用戶得到所需的全部資金后怀读，一定能在有限的時間里歸還所有的資金诉位。

檢測
操作系統(tǒng)中的每一時刻的系統(tǒng)狀態(tài)都可以用進程—資源分配圖來表示，進程—資源分配圖是描述進程和資源間申請及分配關(guān)系的一種有向圖菜枷，可用以檢測系統(tǒng)是否處于死鎖狀態(tài)苍糠。