1. 進(jìn)程與線程
1) 進(jìn)程概念：由程序和代碼、進(jìn)程空間、系統(tǒng)資源、棧區(qū)組成，為對進(jìn)程管理，通過PCB實現(xiàn)。
2) 進(jìn)程的狀態(tài)和轉(zhuǎn)換：創(chuàng)建，就緒，運行，阻塞，結(jié)束。
① 由空到創(chuàng)建：第一個進(jìn)程有系統(tǒng)初始化產(chǎn)生，以后有父進(jìn)程通過創(chuàng)建進(jìn)程的系 統(tǒng)調(diào)用產(chǎn)生。
② 創(chuàng)建到就緒：創(chuàng)建完成后，進(jìn)入就緒狀態(tài)。
③ 就緒到運行：被調(diào)度程序選中，分配到處理機上執(zhí)行。
④ 運行到結(jié)束：調(diào)用結(jié)束進(jìn)程系統(tǒng)調(diào)用或者異常流產(chǎn)，進(jìn)行結(jié)束。
⑤ 運行到就緒：時間片到或者被高優(yōu)先級進(jìn)程打斷
⑥ 運行到等到：通過系統(tǒng)調(diào)用，請求某種資源，未得到，處于等待狀態(tài)；系統(tǒng)調(diào)用是目態(tài)到管態(tài)的過程。
⑦ 等待到就緒：等待的事件來臨
3) 進(jìn)程控制：
① 進(jìn)程創(chuàng)建與終結(jié)：主要有初始化PCB表，置進(jìn)程為就緒狀態(tài)。
② 模式切換：兩種模式，目態(tài)和管態(tài)；劃分的理由是保護(hù)操作系統(tǒng)和操作系統(tǒng)的數(shù)據(jù)表格不被可能出錯的程序破壞。從管態(tài)到目態(tài)是通過操作系統(tǒng)內(nèi)核程序修改程序狀態(tài)字實現(xiàn)，從目態(tài)到管態(tài)是通過異常（也叫自陷、例外、內(nèi)中斷，不可屏蔽，有指令出錯或者缺頁觸發(fā)）或者外中斷（有硬件產(chǎn)生，可屏蔽）。（內(nèi)中斷和外中斷，統(tǒng)稱中斷）；進(jìn)程從目態(tài)到管態(tài)，只需保存進(jìn)程的處理機信息。進(jìn)行切換，要保存進(jìn)程空間信息。
③ 進(jìn)程切換：保存處理機信息，修改進(jìn)程控制塊，修改存儲管理數(shù)據(jù)。
4) 作業(yè)與進(jìn)程的關(guān)系
① 批處理系統(tǒng)中作業(yè)與進(jìn)程的關(guān)系：由SPooling輸入進(jìn)程將作業(yè)放入輸入井，成為后備作業(yè)，由作業(yè)調(diào)度程序選擇后備作業(yè)，創(chuàng)建根進(jìn)程；可以有根進(jìn)程創(chuàng)建更多的子進(jìn)程，共同完成作業(yè)，由作業(yè)終止程序終至完成的作業(yè)，隨后將作業(yè)送入輸出井，有輸出進(jìn)程把數(shù)據(jù)送入打印機。
② 分時系統(tǒng)中作業(yè)與進(jìn)程的關(guān)系：用戶通過命令語句逐條地與系統(tǒng)應(yīng)答式地輸入命令，提交作業(yè)步驟。
③ 交互式地提交批作業(yè)：系統(tǒng)有專門的調(diào)度程序，負(fù)責(zé)從作業(yè)隊列中，選取作業(yè)，為選取的作業(yè)創(chuàng)建根進(jìn)程，執(zhí)行作業(yè)說明書中的命令.
5) 進(jìn)程通信，方法：共享存儲方法（需要進(jìn)行pv操作，由于進(jìn)程空間相對獨立的，因此要通過特殊的系統(tǒng)調(diào)用實現(xiàn)）；消息傳遞方式（通過發(fā)送和接受原語實現(xiàn)通信）
6) 多線程概念與多線程模型：進(jìn)程只作為除cpu以外的資源；線程則作為處理機的分配單位。
2. 處理機調(diào)度
1) 調(diào)度的基本概念
① 高級調(diào)度：從外存上等候調(diào)度的作業(yè)中，選擇一個調(diào)入內(nèi)存，分配資源，創(chuàng)建進(jìn)程，掛到就緒隊列上。
② 中級調(diào)度：把暫時無法運行的進(jìn)程調(diào)入外存，減少內(nèi)存空間的浪費；等內(nèi)存空間空閑，把外存有條件的進(jìn)程重新調(diào)入內(nèi)存。引入中級調(diào)度，主要提高內(nèi)存使用率和提高系統(tǒng)的吞吐量。調(diào)度出去的進(jìn)程為掛起狀態(tài)；中級調(diào)度實質(zhì)為兌換。
③ 低級調(diào)度：進(jìn)程調(diào)度。
2) 進(jìn)程調(diào)度的方式：
① 剝奪式調(diào)度：有優(yōu)先級原則，時間片原則。
② 非剝奪式調(diào)度：除進(jìn)程運行結(jié)束或者進(jìn)入阻塞狀態(tài)以外，進(jìn)程一直占用處理機。
3) 進(jìn)程主動放棄處理機的原因有：
① 進(jìn)程執(zhí)行完畢
② 進(jìn)程進(jìn)入阻塞狀態(tài)
4) 在可剝奪的進(jìn)程調(diào)度中，新就緒的進(jìn)程會按照某種原則，剝奪正在運行的進(jìn)程的處理機，進(jìn)程申請調(diào)度的時機，有以下情況：
① 中斷處理完畢，引起某個進(jìn)程變成就緒狀態(tài)。
② 進(jìn)程釋放臨界區(qū)，引起等待該臨界區(qū)的進(jìn)程就緒
③ 當(dāng)進(jìn)程發(fā)生系統(tǒng)調(diào)用，引起某個時間發(fā)生，導(dǎo)致其他等待進(jìn)程就緒。
④ 引起其他任何原因?qū)е逻M(jìn)程為就緒態(tài)時。
總之，當(dāng)有新進(jìn)程就緒時，引發(fā)進(jìn)程調(diào)度的申請。
5) 在可剝奪式進(jìn)程調(diào)度系統(tǒng)中，即便沒有新的就緒進(jìn)程，為了使所有就緒進(jìn)程占用處理機，可在下述情況下申請進(jìn)程調(diào)度：
① 時鐘中斷發(fā)生，時間片到，其他進(jìn)程請求調(diào)度。
② 任何引起優(yōu)先級發(fā)生變化時，應(yīng)請求重新調(diào)度。
操作系統(tǒng)并不一定要在引發(fā)進(jìn)程調(diào)度原因時，馬上進(jìn)行進(jìn)程調(diào)度。
6) 進(jìn)程的調(diào)度、切換、時機：一般來說，請求調(diào)度--->調(diào)度----->切換，三個事件應(yīng)該一氣呵成；但在現(xiàn)在操作系統(tǒng)中，不能進(jìn)行進(jìn)程的調(diào)度與切換的情況有：
① 處理中斷過程中。
② 進(jìn)程在操作系統(tǒng)那內(nèi)核臨界區(qū)中。
③ 其他需要完全屏蔽中斷的原子操作過程中。
在上述的過程中，引發(fā)調(diào)度的條件，并不能馬上進(jìn)行調(diào)度，系統(tǒng)只是設(shè)置請求調(diào)度標(biāo)志，等走出上述過程后，才進(jìn)行調(diào)度和切換。應(yīng)當(dāng)進(jìn)行進(jìn)程調(diào)度和切換的時機如下：
<1>,發(fā)生引起調(diào)度事件，且當(dāng)前進(jìn)程進(jìn)入阻塞狀態(tài)，可馬上進(jìn)行調(diào)度（若os只有在這種情況下進(jìn)行調(diào)度，說明os是非剝奪調(diào)度。）
<2>,當(dāng)中斷處理結(jié)束或者自陷處理結(jié)束后，返回被中斷進(jìn)程的用戶態(tài)程序現(xiàn)場前，若置上請求調(diào)度標(biāo)志，即可馬上進(jìn)行調(diào)度與切換。（實現(xiàn)了剝奪式調(diào)度）
切換往往是在調(diào)度之后發(fā)生的；典型的進(jìn)程切換需要保存原進(jìn)程當(dāng)前切換點的現(xiàn)場信息，恢復(fù)被調(diào)度進(jìn)程的現(xiàn)場信息。現(xiàn)場信息有：PC，PS，其他寄存器的內(nèi)容、內(nèi)核棧指針，進(jìn)程存儲空間的指針。
為了進(jìn)行進(jìn)程現(xiàn)場切換，操作系統(tǒng)內(nèi)核將原進(jìn)程的上述信息推入當(dāng)前進(jìn)程的內(nèi)核棧保存它們，并跟新堆棧指針。內(nèi)核從新進(jìn)程的內(nèi)核棧中裝入新進(jìn)程的現(xiàn)場信息，還要更新當(dāng)前進(jìn)程空間的指針，并且作廢處理機聯(lián)想存儲器中有關(guān)原進(jìn)程的信息。在內(nèi)核完成清除工作后，重新設(shè)置PC寄存器，控制轉(zhuǎn)到新進(jìn)程的程序，開始運行。
7) 調(diào)度的基本準(zhǔn)則：
① 從用戶角度：周轉(zhuǎn)時間段，響應(yīng)時間短，截止時間的保證
② 從系統(tǒng)角度：吞吐量達(dá)；處理機利用率高；各類資源平衡利用。
8) 調(diào)度算法：
① 先來先服務(wù)調(diào)度算法（可不剝奪式調(diào)度）
② 優(yōu)先級調(diào)度算法，兩種，非可剝奪式優(yōu)先級調(diào)度算法和可剝奪式優(yōu)先級調(diào)度算法。
③ 時間片輪轉(zhuǎn)算法發(fā)：先采用先來先服務(wù)，然后時間片到，把進(jìn)程掛到就緒隊列的末尾。時間片太大，那么將退化為先來先服務(wù)算法；若時間片太小，那么切換過于頻繁，處理機開銷變大，效率降低。
④ 短進(jìn)行優(yōu)先調(diào)度：優(yōu)先選擇運行時間短的小進(jìn)程。（不可剝奪方式）
短進(jìn)程優(yōu)先算法和先來先服務(wù)算法都是非剝奪的，因此不能用于分時系統(tǒng)中，這是因為不能對用戶及時響應(yīng)。
⑤ 最高響應(yīng)比優(yōu)先算法：對短進(jìn)程優(yōu)先的改進(jìn)，屬于非可剝奪式算法。按照此算法，每個進(jìn)程都有一個優(yōu)先數(shù)，該優(yōu)先數(shù)不但是要求的服務(wù)時間的函數(shù)，而且是該進(jìn)程得到的服務(wù)所花費的等待時間的函數(shù)。進(jìn)程的動態(tài)優(yōu)先計算公式：優(yōu)先數(shù) = （等到時間+請求服務(wù)時間）/（情感求服務(wù)時間），請求服務(wù)時間是分母，故對短進(jìn)程有利，他的優(yōu)先數(shù)高，可以優(yōu)先運行。但由于等待時間是分子，故長進(jìn)程等待較長的時間，從而提高其調(diào)度優(yōu)先數(shù)，被分給了處理機。進(jìn)程一旦得到錘擊，他就一直運行到進(jìn)程完成，中間不被搶占。可以看出“等待時間+請求服務(wù)時間”就是系統(tǒng)對作業(yè)的響應(yīng)時間。
⑥ 多級反饋隊列調(diào)度算法:采用多級隊列，每級隊列的優(yōu)先級不同，優(yōu)先級大的隊列，時間片短。除最后一級別采用時間片輪轉(zhuǎn)法后，其他的隊列采用先進(jìn)先出算法。
3. 進(jìn)程同步
1) 同步關(guān)系，互斥關(guān)系；臨界資源；臨界區(qū)
2) 實現(xiàn)臨界段問題的硬件方法：
① 屏蔽中斷
② Test_and_set指令
③ Swap指令
④ 信號量
⑤ 管程：由一組同步變量和使用同步變量的過程組成；是更高級的同步與互斥的抽象，但其解決同步與互斥的能力低于信號量機制。
4. 死鎖：在一個進(jìn)程集合里面，若每個進(jìn)程都在等待某些釋放資源的時間的發(fā)生，而這些事件又必須有這個進(jìn)程集合中的某些進(jìn)程產(chǎn)生，就成這些集合處于死鎖狀態(tài)。
1) 死鎖條件：
① 互斥。必須需要使用互斥的資源
② 占用等待。
③ 非剝奪
④ 循環(huán)等待
2) 死鎖處理策略：
① 死鎖防止：通過應(yīng)用編程或者資源設(shè)計破壞死鎖條件。
② 死鎖避免：分配資源時，通過判斷如果滿足這次資源分配后，仍存在一條路徑，使系統(tǒng)不會進(jìn)入死鎖狀態(tài)，如果沒有這種路徑，則拒絕分配。
3) 死鎖防止：
① 破壞互斥條件
② 破壞占有等待條件
③ 破壞非剝奪條件
④ 破壞循環(huán)等待條件
4) 死鎖避免：銀行家算法
5) 死鎖檢測與解除：
① 檢測：定時運行死鎖檢測程序。
② 解除：刪除某個進(jìn)程，釋放資源。
信號量機制相關(guān)代碼：
//整型信號量
wait(S)
{
while(S<=0);
S--;
}
signal(S)
{
S++;
}
由于整型信號量不滿足進(jìn)程同步的第四個原則“讓權(quán)等待”；當(dāng)wait操作時若信號量S<=0，那么就會不斷的循環(huán)測試S的值，不會釋放CPU,記錄型信號量可以解決這個問題：
// 記錄型信號量
typedef struct
{
int value;
struct process * L;
}semaphore;
void wait(semaphore S)
{
S.value--;
if(S.value<0)
{
add this process to S.L;
block(S.L);
}
}
void signal(semaphore S)
{
S.value++;
if(S.value<=0)
{
remove a process P from S.L;
wakeup(P);
}
}
以下舉出幾個經(jīng)典的同步問題：
1，生產(chǎn)者消費者問題
問題描述：生產(chǎn)進(jìn)程和消費進(jìn)程共享大小為n的緩沖區(qū)，只要緩沖區(qū)沒有滿，生產(chǎn)者就可以把產(chǎn)品放入緩沖區(qū)；只要緩沖區(qū)不空，消費者就可以從緩沖區(qū)中取出消息。
Semaphore mutex = 1;
Semaphore empty = n;
Semaphore full = 0;
producer()
{
while(1)
{
make a product;
wait(empty);
wait(mutex);
add a product to buffer;
signal(mutex);
signal(full);
}
}
consumer(){
while(1)
{
wait(full);
wait(mutex);
remove a product from buffer;
signal(mutex);
signal(empty);
}
}
2,讀者寫者問題
問題描述：若干個讀者和一個寫著共享一個文件，寫著在這個文件上寫的時候不允許有讀者讀，黨讀者在讀這個文件的時候，不允許寫。
int count = 0; //記錄讀者的數(shù)量
semaphore mutex = 1; //更新cout變量用
semaphore rw = 1; //讀者和寫著互斥訪問
writer()
{
while(1)
{
wait(rw);
writing;
signal(rw);
}
}
reader()
{
while(1)
{
wait(mutex);
if(count == 0) //若當(dāng)前沒有讀者，申請閱讀
wait(rw);
count++;
signal(mutex);
reading;
wait(mutex);
count--;
if(count == 0) //若當(dāng)前沒有讀者，釋放信號量，寫者可以進(jìn)入
signal(rw);
signal(mutex);
}
}
3，打印機問題，問題描述：3個并發(fā)進(jìn)程，共享打印機，只有一個緩沖區(qū)，R從輸入設(shè)備讀信息，讀出后，放入緩沖區(qū)；進(jìn)程M在緩沖區(qū)中加工信息；進(jìn)程p把加工后的信息，輸出；
Semaphore m1 = 0; //是否有未被處理的數(shù)據(jù)
Semaphore m2 = 0; //是否有被處理的數(shù)據(jù)
Semaphore empty = 1;
Semaphore mutex = 1;
R()
{
while(1)
{
wait(empty);
wait(mutex);
put data to buffer;
signal(mutex);
signal(m1);
}
}
M()
{
while(1)
{
wait(m1);
wait(mutex);
process the data;
signal(mutex);
signal(m2);
}
}
P()
{
wait(m2);
wait(mutex);
output the data;
wait(mutex);
wait(empty);
}