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