1.前趨圖和程序執(zhí)行
1）前趨圖：
有向無循環(huán)圖 （關注的是前趨關系，不能有循環(huán)）
2）程序順序執(zhí)行的特征：
1.順序性 2.封閉性 3.可再現(xiàn)性
3）程序的并發(fā)執(zhí)行：
要符合前趨關系，并發(fā)不是隨意的
特征：1.間斷性? ?2.失去封閉性 3.不可再現(xiàn)性
2.進程的描述
1）進程的定義：
進程實體的運行過程，是系統(tǒng)進行資源分配和調度的一個獨立單位。
2）進程的特征：
1.結構性? 2. 動態(tài)性? 3.并發(fā)性 4.獨立性 5.異步性
3）進程的基本狀態(tài)：
1.就緒狀態(tài)? 2.執(zhí)行狀態(tài)? ?3.阻塞狀態(tài)
4）掛起操作原因：
（1）終端用戶的需要
（2）父進程請求
（3）負荷調節(jié)的需要
（4）操作系統(tǒng)的需要
5）進程控制塊PCB
進程實體：
代碼段+數(shù)據(jù)段+PCB
定義：
存放進程的管理和控制信息的數(shù)據(jù)結構
作用：
（1）作為獨立運行基本單位的標志
（2）能實現(xiàn)間斷性運行方式
（3）提供進程管理所需要的信息
（4）提供進程調度所需要的信息
（5）實現(xiàn)與其他進程的同步與通信
PCB中的信息：
（1）進程標識等信息
（2）處理機狀態(tài)信息
（3）進程調度信息
（4）進程控制信息
PCB信息的存放：
常駐內存的PCB區(qū)
采用的數(shù)據(jù)結構：PCB結構體，PCB鏈表或隊列
PCB的組織方式：
（1）線性方式 （2）鏈接方式 （3）索引方式
3.進程控制
1）操作系統(tǒng)內核：
支撐功能：
1.中斷處理? ?2.時鐘管理? ? 3.原語操作
資源管理功能：
1.進程管理? ? ?2. 存儲器管理? ? ?3. 設備管理?
2）進程的創(chuàng)建：（原語操作，不可被打斷）
（1） 申請空白PCB
（2）為新進程分配其運行所需的資源
（3）初始化進程控制塊
（4）將新進程插入到就緒隊列
3）進程的終止：（原語操作，不可被打斷）
1.正常結束? ? 2.異常結束? 3.外界干預
4）進程的阻塞
（1）向系統(tǒng)請求共享資源失敗
（2）等待某種操作的完成
（3）新數(shù)據(jù)尚未到達
（4）等待新任務的到達
4.進程同步
使并發(fā)執(zhí)行的諸進程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。
1）進程同步的兩種形式的制約關系：
間接相互制約關系
直接相互制約關系
2）訪問臨界資源的循環(huán)進程：
while（true）
{
進入區(qū)
臨界區(qū)
退出區(qū)
剩余區(qū)
}
3）同步機制應遵循的原則：
（1）空閑讓進：資源使用最基本原則
（2）忙則等待：保證互斥
（3）有限等待：合適時被喚醒防止死等
（4）讓權等待：能主動釋放CPU防止死等
4）控制同步的關鍵？
不被打斷的進行標志值的判斷和修改
5）信號量機制
（1）整型信號量
1.信號量定義為一個整型量
2.根據(jù)初始情況賦相應的值
3.僅能通過兩個原子操作來訪問
4.? P操作 ：
wait（s）:
while s<=0? do no-op;
s:=s-1;
V操作:
?signal(s):
s:s+1;
（2)記錄型信號量：
1.記錄型數(shù)據(jù)結構：整型變量value? ?進程鏈表L
2.value>0,表示當前可用資源的數(shù)量
value<=0,其絕對值表示等待使用該資源的進程數(shù)，即在該信號量隊列上排隊的PCB的個數(shù)
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個資源，當現(xiàn)有資源數(shù)少于d時，不予分配
（2）Swait（S,1,1）:此時的信號量集已蛻化為一般的記錄型信號量（S>1時）或互斥信號量（S=1時）
（3）Swait（S,1,0）:這是一種很特殊且很有用的信號量操作。當S>=1時，允許多個進程進入某特定區(qū)；當S變?yōu)?后，將阻止任何進程進入特定區(qū)。換言之，它相當于一個可控開關。
6）信號量的應用
（1）實現(xiàn)有序
1.前趨關系
2.為每隊前趨關系設置一個同步信號量S，并賦初值為0
p1: C1;signal(s);
p2:wait(s);C2;
3.控制同步順序的注意點
①信號量值為0的點是限制的關鍵
②成對使用P、V原語（在有先后關系的兩個進程中），不能次序錯誤，重復或遺漏。
5.經典進程的同步問題
1）生產者-消費者問題
（1）無論生產者、消費者使用緩沖池時應保證互斥使用（互斥信號量mutex ）
（2）生產者和消費者間交叉有序：
有序的控制最根源在產品數(shù)量上。
設置兩個信號量：分別針對生產者、消費者設置不同的信號量，empty和full分別表示緩沖池中空緩沖池和滿緩沖池（即產品）的數(shù)量。
empty、full兩者有天然的數(shù)量關系，在PV控制下值不斷變化，但在值等于0的點上是控制順序的關鍵。
2）哲學家進餐問題
（1）記錄型信號量解決就餐問題：
筷子是臨界資源，在一段時間內只允許一個哲學家使用。為實現(xiàn)對筷子的互斥使用，用一個信號量表示一只筷子，五個信號量構成信號量數(shù)組。
? ? 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.數(shù)量控制：至多只允許有四位哲學家同時去拿左邊的筷子，最終能保證至少有一位哲學家能夠進餐，并在用畢后釋放出他用過的兩只筷子，從而使更多的哲學家能夠進餐。
---限制并發(fā)執(zhí)行的進程數(shù)
2.規(guī)定奇數(shù)號哲學家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數(shù)號哲學家則相反。按此規(guī)定，將是1、2號哲學家競爭1號筷子；3、4號哲學家競爭3號筷子。即5位哲學家都先競爭奇數(shù)號筷子。獲得后，再去競爭偶數(shù)號筷子。最后總會有一位哲學家能獲得兩只筷子而進餐。
3.僅當哲學家的左右兩只筷子均可用時，才允許他拿起筷子進餐。
---采用AND信號量。
3）讀者-寫者問題
（1）利用記錄型信號量
為實現(xiàn)Reader與Writer進程間在讀或寫時的互斥而設置了兩個互斥信號量wmutex和rmutex。另外，再設置一個整型變量readcount表示正在讀的進程數(shù)目。
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）修改、維護困難：易讀性差，任一修改都可能影響全局；測試期間發(fā)現(xiàn)錯誤困難，即使發(fā)現(xiàn)錯誤也不容易定位出錯位置。
2）管程的組成
（1）一組局部變量
（2）對局部變量操作的一組過程
（3）對局部變量進行初始化的語句。（聯(lián)想面向對象中的類）
