1.前趨圖和程序執行
1）前趨圖：
有向無循環圖 （關注的是前趨關係，不能有循環）
2）程序順序執行的特徵：
1.順序性 2.封閉性 3.可再現性
3）程序的併發執行：
要符合前趨關係，併發不是隨意的
特徵：1.間斷性 2.失去封閉性 3.不可再現性
2.進程的描述
1）進程的定義：
進程實體的運行過程，是系統進行資源分配和調度的一個獨立單位。
2）進程的特徵：
1.結構性 2. 動態性 3.併發性 4.獨立性 5.異步性
3）進程的基本狀態：
1.就緒狀態 2.執行狀態 3.阻塞狀態
4）掛起操作原因：
（1）終端用戶的需要
（2）父進程請求
（3）負荷調節的需要
（4）操作系統的需要
5）進程控制塊PCB
進程實體：
代碼段+數據段+PCB
定義：
存放進程的管理和控制信息的數據結構
作用：
（1）作為獨立運行基本單位的標誌
（2）能實現間斷性運行方式
（3）提供進程管理所需要的信息
（4）提供進程調度所需要的信息
（5）實現與其他進程的同步與通信
PCB中的信息：
（1）進程標識等信息
（2）處理機狀態信息
（3）進程調度信息
（4）進程控制信息
PCB信息的存放：
常駐內存的PCB區
採用的數據結構：PCB結構體，PCB鏈表或隊列
PCB的組織方式：
（1）線性方式 （2）鏈接方式 （3）索引方式
3.進程控制
1）操作系統內核：
支撐功能：
1.中斷處理 2.時鐘管理 3.原語操作
資源管理功能：
1.進程管理 2. 存儲器管理 3. 設備管理
2）進程的創建：（原語操作，不可被打斷）
（1） 申請空白PCB
（2）為新進程分配其運行所需的資源
（3）初始化進程控制塊
（4）將新進程插入到就緒隊列
3）進程的終止：（原語操作，不可被打斷）
1.正常結束 2.異常結束 3.外界干預
4）進程的阻塞
（1）向系統請求共享資源失敗
（2）等待某種操作的完成
（3）新數據尚未到達
（4）等待新任務的到達
4.進程同步
使併發執行的諸進程之間能有效地共享資源和相互合作，從而使程序的執行具有可再現性。
1）進程同步的兩種形式的制約關係：
間接相互制約關係
直接相互制約關係
2）訪問臨界資源的循環進程：
while（true）
{
進入區
臨界區
退出區
剩餘區
}
3）同步機制應遵循的原則：
（1）空閒讓進：資源使用最基本原則
（2）忙則等待：保證互斥
（3）有限等待：合適時被喚醒防止死等
（4）讓權等待：能主動釋放CPU防止死等
4）控制同步的關鍵？
不被打斷的進行標誌值的判斷和修改
5）信號量機制
（1）整型信號量
1.信號量定義為一個整型量
2.根據初始情況賦相應的值
3.僅能通過兩個原子操作來訪問
4. P操作 ：
wait（s）:
while s<=0 do no-op;
s:=s-1;
V操作:
signal(s):
s:s+1;
（2)記錄型信號量：
1.記錄型數據結構：整型變量value 進程鏈表L
2.value>0,表示當前可用資源的數量
value<=0,其絕對值表示等待使用該資源的進程數，即在該信號量隊列上排隊的PCB的個數
3.P操作：
wait（）：
s.value()=s.value()-1；
if s.value（）<0 then block(s,L)
V操作:
signal():
s.value()=s.value()+1;
if s.value<=0 then wakeup(s,L)
（3)AND型信號量
設置互斥的信號量：Dmutex、Emutex，令它們的初值為1
（4）信號量集
（1）Swait(S,d,d）:此時在信號量集中只有一個信號量S，但允許它每次申請d個資源，當現有資源數少於d時，不予分配
（2）Swait（S,1,1）:此時的信號量集已蛻化為一般的記錄型信號量（S>1時）或互斥信號量（S=1時）
（3）Swait（S,1,0）:這是一種很特殊且很有用的信號量操作。當S>=1時，允許多個進程進入某特定區；當S變為0後，將阻止任何進程進入特定區。換言之，它相當於一個可控開關。
6）信號量的應用
（1）實現有序
1.前趨關係
2.為每隊前趨關係設置一個同步信號量S，並賦初值為0
p1: C1;signal(s);
p2:wait(s);C2;
3.控制同步順序的注意點
①信號量值為0的點是限制的關鍵
②成對使用P、V原語（在有先後關係的兩個進程中），不能次序錯誤，重複或遺漏。
5.經典進程的同步問題
1）生產者-消費者問題
（1）無論生產者、消費者使用緩衝池時應保證互斥使用（互斥信號量mutex ）
（2）生產者和消費者間交叉有序：
有序的控制最根源在產品數量上。
設置兩個信號量：分別針對生產者、消費者設置不同的信號量，empty和full分別表示緩衝池中空緩衝池和滿緩衝池（即產品）的數量。
empty、full兩者有天然的數量關係，在PV控制下值不斷變化，但在值等於0的點上是控制順序的關鍵。
2）哲學家進餐問題
（1）記錄型信號量解決就餐問題：
筷子是臨界資源，在一段時間內只允許一個哲學家使用。為實現對筷子的互斥使用，用一個信號量表示一隻筷子，五個信號量構成信號量數組。
Var chopstick: array [0, …, 4] of semaphore;
所有信號量均被初始化為1。.
第i 位哲學家的活動可描述為：
repeat
wait(chopstick[ i ]);//當哲學家飢餓時，總先拿起左邊的筷子，再拿起右邊的筷子
wait(chopstick[ ( i +1) mod 5] );
…
eat;
…
signal(chopstick[ i ]);//當哲學家飢餓時，總先拿起左邊的筷子，再拿起右邊的筷子
signal(chopstick[ ( i +1) mod 5] );
…
think;
until false;
(2)就餐死鎖問題
解決方法：
1.數量控制：至多隻允許有四位哲學家同時去拿左邊的筷子，最終能保證至少有一位哲學家能夠進餐，並在用畢後釋放出他用過的兩隻筷子，從而使更多的哲學家能夠進餐。
---限制併發執行的進程數
2.規定奇數號哲學家先拿他左邊的筷子，然後再去拿右邊的筷子；而偶數號哲學家則相反。按此規定，將是1、2號哲學家競爭1號筷子；3、4號哲學家競爭3號筷子。即5位哲學家都先競爭奇數號筷子。獲得後，再去競爭偶數號筷子。最後總會有一位哲學家能獲得兩隻筷子而進餐。
3.僅當哲學家的左右兩隻筷子均可用時，才允許他拿起筷子進餐。
---採用AND信號量。
3）讀者-寫者問題
（1）利用記錄型信號量
為實現Reader與Writer進程間在讀或寫時的互斥而設置了兩個互斥信號量wmutex和rmutex。另外，再設置一個整型變量readcount表示正在讀的進程數目。
semaphore rmutex=1,wmutex=1;
int readcount=0;
void reader(){
do{
wait（rmutex）; //rmutex=0
if（readcount==0）wait(wmutex); //wmutex=0
readcount++;
signal(rmutex);
……
perform read operation；
……
wait（rmutex）;
readcount--;
if（readcount==0）signal(wmutex);
signal(rmutex);
}while（TRUE）；
}
(2)利用信號量集
6.管程機制
（把信號量及其操作原語“封裝”在一個對象內部）
1）信號量機制的不足：
（1）正確性分析困難
（2）分散的P、V操作：易出錯，使用不當可能導致死鎖
（3）修改、維護困難：易讀性差，任一修改都可能影響全局；測試期間發現錯誤困難，即使發現錯誤也不容易定位出錯位置。
2）管程的組成
（1）一組局部變量
（2）對局部變量操作的一組過程
（3）對局部變量進行初始化的語句。（聯想面向對象中的類）
閱讀更多 有一天我會成功 的文章
