在學習作業系統時總結了筆記，并分享出來，特别是藍色和紅色字型。有問題請及時聯系部落客：Alliswell_WP，轉載請注明出處。
參考書：《作業系統》谌衛軍等，清華大學出版社，2012年5月
參考視訊：清航全套計算機專業課視訊
目錄
1.程序（Process）
2.線程（Thread）
3.程序間通信
4.經典的IPC問題
5.程序排程
第二章 程序管理（程序三種狀态的轉換？如何共享資料？低級通信？進階通信？互斥（引入的原因及如何解決）？PV原語、經典的三大IPC問題及解決方案、程序排程的優先級、死鎖）
1.程序（Process）
為什麼使用程序？Why processes？
為了提高計算機系統中各種資源的使用率，現代作業系統廣泛采用多道程式技術（multi-programming），使多個程式同時在系統中存在并運作。
X86 CPU 寄存器
程式1 程式2
問題：硬體隻有一份，如何使這兩個程式同時運作？
為此，作業系統設計者提出了程序的概念。
什麼是程序？A process = a program in execution
一個程序應該包括：
-程式的代碼；
-程式的資料；
-CPU寄存器的值，如PC，用來訓示下一條将運作的指令、通用寄存器等；
-堆、棧；
-一組系統資源（如位址空間、打開的檔案）
總之，程序包含了正在運作的一個程式的所有狀态資訊。
擴充：棧的作用是什麼？儲存臨時資料、函數調用時來配置設定棧針來存放形參和局部變量
程序和程式的差別？
程式是靜态的，程序是動态的。
程序的特性
-動态性：程式的運作狀态在變，PC、寄存器、堆和棧等；
-獨立性：是一個獨立的實體，是計算機系統資源的使用機關。每一個程序在一個“虛拟計算機”上運作，每個程序都有“自己”的PC和内部狀态，運作時獨立于其他的程序（虛拟PC和實體PC）；
如何實作邏輯PC？
在記憶體開辟一段空間，實作不同程序實體PC和邏輯PC輪流切換。
引起程序建立的三個主要事件？
-系統初始化時；
-在一個正在運作的程序當中，執行了建立程序的系統調用；
-使用者請求建立一個新程序。
程序的三個基本狀态
-運作狀态（Running）：程序占有CPU，并在CPU上運作。處于此狀态的程序數目小于等于CPU的數目。
-就緒狀态（Ready）：程序已經具備運作條件，但由于CPU忙暫時不能運作，隻要分得CPU即可運作；
（萬事俱備隻欠東風，隻欠CPU）
-阻塞狀态（Blocked/Waited）：指程序因等待某種事件的發生而暫時不能運作的狀态（如I/O操作或程序同步），此時，即使CPU空閑，該程序也不能運作。
類比：修自行車……（運作——正在修；就緒——正在修别人的車，等空閑修；阻塞——壞零件，買回來才能修）
程序的狀态及其轉換
引起程序狀态轉換的具體原因如下：
運作态→等待态：等待使用資源；如等待外設傳輸；等待人工幹預。
等待态→就緒态：資源得到滿足；如外設傳輸結束；人工幹預完成。
運作态→就緒态：運作時間片到；出現有更高優先權程序。
就緒态—→運作态：CPU 空閑時選擇一個就緒程序。
問題：1）程序正常運作（未阻塞）時處于什麼狀态？運作态或就緒态
2）此頁正在講的PPT處于什麼狀态？阻塞态
3）是否有其他的狀态轉換？沒有，這三種隻有四種情況。
程式 = 資料結構 + 算法
描述程序的資料結構：程序控制塊（Process Control Block，PCB）。
系統為每個程序都維護了一個PCB，用來儲存與程序有關的各種狀态資訊。
PCB中的主要内容
系統用PCB來描述程序的基本情況以及運作變化的過程，PCB是程序存在的唯一标志。
程序的建立：為該程序生成一個PCB；
程序的終止：回收它的PCB；
程序的組織管理：通過對PCB的組織管理來實作；
狀态隊列
-由作業系統來維護一組隊列，用來表示系統當中所有程序的目前狀态；
-不同的狀态分别用不同的隊列來表示（運作隊列、就緒隊列、各種類型的阻塞隊列）；
-每個程序的PCB都根據它的狀态加入到相應的隊列當中，當一個程序的狀态發生變化時，它的PCB從一個狀态隊列中脫離出來，加入到另外一個隊列。
如何實作隊列？連結清單
2.線程（Thread）
為什麼要引入線程？
【案例】編寫一個MP3播放軟體。核心功能子產品有三個：1）從MP3音頻檔案當中讀取資料；2）對資料進行解壓縮；3）把解壓縮後的音頻資料播放出來。
單程序的實作方法
1 main()
2 {
3 while(TRUE)
4 {
5 Read();//I/O
6 Decompress();//CPU
7 Play();//I/O
8 }
9 }
10 Read(){……}//讀資料
11 Decompress(){……}//解壓縮
12 Play(){……}//播放 問題：1）播放出來的聲音能否連貫？2）各個函數之間不是并發執行，影響資源的使用效率；
多程序的實作方法
問題：程序之間如何通信，共享資料？
怎麼來解決這些問題？
需要提出一種新的實體，滿足一下特性：1）實體之間可以并發地執行；2）實體之間共享相同的位址空間；
這種實體就是：線程
程序 = 線程 + 資源平台
優點：1）一個程序可以同時存在多個線程；2）各個線程之間可以并發地執行；3）各個線程之間可以共享位址空間。
了解：為什麼CPU寄存器的值和棧的值不能共享？
3.程序間通信
需要讨論的問題：
-程序間如何通信呢，如何來互相傳遞資訊呢?
-當兩個或多個程序在通路共享資源時，如何確定它們不會互相妨礙——程序互斥問題；
-當程序之間存在着某種依存關系時，如何來調整它們運作的先後次序——程序同步問題。
生活中的例子：教室的座位——互斥、兩同學相約看電影——同步
程序間通信方式
-低級通信：隻能傳遞狀态和整數值（控制資訊）
-進階通信：能夠傳送任意數量的資料
如何實作通信？能否共享記憶體單元（全局變量或共享緩沖區）？
程序間互斥
産生的原因：1）程序宏觀上并發執行，依靠時鐘中斷來實作微觀上輪流執行；2）通路共享資源。
競争狀态（race condition)：兩個或多個程序對同一共享資料同時進行讀寫操作，而最後的結果是不可預測的，它取決于各個程序具體運作情況。
解決之道：在同一時刻，隻允許一個程序通路該共享資料，即如果目前已有一個程序正在使用該資料，那麼其他程序暫時不能通路。這就是互斥的概念。
（備注：例子有點問題？程序之間不可以共享資料！此例子不嚴謹）
實作互斥通路的四個條件
1）任何兩個程序都不能同時進入臨界區；
2）不能事先假定CPU的個數和運作速度；
3）當一個程序運作在它的臨界區外面時，不能妨礙其他的程序進入臨界區；
4）任何一個程序進入臨界區的要求應該在有限時間内得到滿足。
基于繁忙等待的互斥實作
1 #define FALSE 0
2 #define TRUE 1
3 #define N 2//程序的個數
4 int turn;//輪到誰？
5 int interested[N];//興趣數組，初始值均為FALSE
6 void enter_region(int process)//process=0或1
7 {
8 int other;//另外一個程序的程序号
9 other=1-process;
10 interested[process]=TRUE；//表明本程序感興趣
11 turn=process;//設定标志位
12 while( turn=process&& interested[other]=TRUE);
13 }
14 void leave_region(int process)
15 {
16 interested[process] = FALSE;//本程序已離開臨界區
17 } Peterson算法解決了互斥通路的問題，而且不會互相妨礙，可以完全正常地工作。
分析：
第一種情況：
P0在執行完other=1-process;後時鐘中斷；P1正常執行
全局變量：
turn： interested：[0]（0） [1]（0）
局部變量（棧）：
P0——process：0；other：1——>P0時鐘中斷
P1——process：1；other：0——interested：[0]（0） [1]（1）；turn：1——while循環條件不成立（interested[0]等于0，不等于1），卡不住，P1往下執行——>然後P0繼續執行；interested：[0]（1） [1]（1）；turn：0——while循環條件成立（turn等于process等于0；interested[1]等于1；），P0卡住，P0不能往下執行
——>P1進入，P0卡住
第二種情況：
P0在執行interested[process]=TRUE;後時鐘中斷；P1正常執行
全局變量：
turn： interested：[0]（0） [1]（0）
局部變量（棧）：
P0——process：0；other：1；interested：[0]（1） [1]（0）——>P0時鐘中斷
P1——process：1；other：0——interested：[0]（1） [1]（1）；turn：1——while循環條件成立（turn等于process等于1；interested[0]等于1；），P1卡住，P1不能往下執行——>然後P0繼續執行；turn：0——while循環條件成立（turn等于process等于0；interested[1]等于1；），P0卡住，P0不能往下執行——>然後P1繼續執行（在while處）；——while循環條件不成立（turn（0），不等于process（1）），P1卡不住，P1往下執行——>然後P0繼續執行——while循環條件成立（turn等于process等于0；interested[1]等于1；），P0卡住，P0不能往下執行
——>P1進入，P0卡住
核心：時鐘中斷；
解決方法：一步步執行
小結：以上的各種方法，都是基于繁忙等待（busy waiting)的政策，都可歸納為一種形式：當一個程序想要進入它的臨界區時，首先檢查一下是否允許它進入，若允許，就直接進入了；若不允許，就在那裡循環地等待，一直等到允許它進入。
缺點：1）浪費CPU時間；2)可能導緻預料之外的結果（如：一個低優先級程序位于臨界區中，這時有一個高優先級的程序也試圖進入臨界區）
問題步驟描述：
-一個低優先級的程序正在臨界區中；
-另一個高優先級的程序就緒了；
-排程器把CPU配置設定給高優先級的程序；
-該程序也想進入臨界區；
-高優先級程序将會循環等待，等待低優先級程序退出臨界區；
-低優先級程序無法獲得CPU，無法離開臨界區。
解決之道：
-當一個程序無法進入臨界區時，應該被阻塞起來（sleep）；
-當一個程序離開臨界區時，需要去喚醒（wake up)被阻塞的程序；
-克服了繁忙等待方法的兩個缺點（浪費CPU時間、可能死鎖）。
現有的程序互斥問題形式：兩個或多個程序都想進入各自的臨界區，但在任何時刻，隻允許一個程序進入臨界區。
新的程序互斥問題形式：兩個或多個程序都想進入各自的臨界區，但在任何時刻，隻允許N個程序同時進入臨界區（N≥1）。
如何解決？信号量PV操作
-1965年由著名的荷蘭計算機科學家Dijkstra提出，其基本思路是用一種新的變量類型（semaphore)來記錄目前可用資源的數量。
-semaphore的取值可正可負，正數表示目前空閑資源的數量，負數的絕對值表示正在等待進入臨界區的程序個數。
-信号量是由作業系統來維護的，使用者程序隻能通過初始化和兩個标準原語（P、V原語）來通路。初始化可指定一個非負整數，即空閑資源總數。
備注：原語就是函數
-P、V原語包含有程序的阻塞和喚醒機制，是以在程序等待進入臨界區時不會浪費CPU時間；
-P原語：申請一個空閑資源（把信号量減1），若成功，則退出；若失敗，則該程序被阻塞；
-V原語：釋放一個被占用的資源（把信号量加1），若發現有被阻塞的程序，則選擇一個喚醒之。
信号量和P、V原語的實作
信号量結構體類型的定義：
1 typedef struct
2 {
3 int count；//計數變量
4 struct PCB*queue；//程序等待隊列
5 }semaphore; P原語：申請一個資源
1 P( semaphore S)
2 {
3 --S.count；//表示申請一個資源；
4 if(S.count<0)//表示沒有空閑資源；
5 {
6 該程序進入等待隊列S.queue末尾；
7 阻塞該程序；
8 調用程序排程器；//OSSched(）
9 }
10 } V原語：釋放一個資源
1 V( semaphore S)
2 {
3 ++S.count；//表示釋放一個資源；
4 if(S.count<=0)//表示有程序被阻塞；
5 {
6 從等待隊列S.queue中取出一個程序；
7 把該程序改為就緒狀态，插入就緒隊列
8 }
9 } Windows 2000
-CreateSemaphore(建立信号量）
-WaitForSingleObject(P操作）
-ReleaseSemaphore(V操作）
μCOS-Ⅱ
-osSemCreate（建立信号量）
-osSemPend（P操作）
-osSemPost(V操作）
備注：互斥信号量初始化為1
分析：PV原語為什麼可以實作程序互斥通路？
原理：PV原語不會中斷
思考步驟：如果P1執行P(mutex);；--S.count後count為0，if判斷不成立，繼續往下執行，進入臨界區，發生了中斷（此時P1為就緒隊列）——>P2執行P(mutex);；--S.count後count為-1，if判斷成立，P2進入阻塞隊列；——>P3執行P(mutex);；--S.count後count為-2，if判斷成立，P3進入阻塞隊列——（此時就緒隊列：P1；阻塞隊列：P2——P3）
——>P1繼續執行，V(mutex);；++S.count；後count為-1，if判斷成立（把P2取出，阻塞改為就緒，P1就緒）——>P2繼續執行（接着上回P操作中if條件的最後），進入臨界區，然後V(mutex);；++S.count；後count為0，if判斷成立（把P3取出，阻塞改為就緒，P1，P2就緒） ——>P3繼續執行（接着上回P操作中if條件的最後），進入臨界區，然後V(mutex);；++S.count；後count為1，if判斷不成立，然後P3進入非臨界區——>P1、P2進入非臨界區
程序間的同步是指多個程序中發生的事件存在某種時序關系，是以在各個程序之間必須協同合作，互相配合，使各個程序按一定的速度執行，以共同完成某一項任務。
同步：合作。互斥：競争。
隻考慮基于信号量的同步問題。
考慮：（S初值為0）若先程序P1（先A，然後V(S)），S=1——>然後P2，P(S)，S=0，執行B——先A後B可以
（S初值為0）若先程序P2，P(S)，S=-1，卡住，不執行，P2阻塞——>然後執行P1（先A，在調用V(S)），S=0，喚醒B，執行B——先A後B可以
4.經典的IPC問題
1）生産者一消費者問題
2）哲學家就餐問題
3）讀者一寫者問題
用信号量來解決，主要問題：如何選擇信号量，如何安排P、V原語的順序。
1）生産者一消費者問題
兩個程序（生産者和消費者）共享一個公有的、固定大小的緩沖區，生産者不斷地制造産品，并把它放入緩沖區，而消費者不斷地把産品取出來，并且使用它。要求這兩個程序互相協調，正确地完成各自的工作。
問題分析
對于生産者程序：制造一個産品，當要送入緩沖區時，要檢查緩沖區是否有空位，若是，才可将産品送入緩沖區，并在必要時通知消費者；否則等待；
對于消費者程序：當它去取産品時，先要檢查緩沖區中是否有産品可取，若有，則取走一個，并在必要時通知生産者；否則等待。
這種互相等待，并互通資訊就是典型的程序同步。
同時，緩沖區是個臨界資源，是以，各個程序在使用緩沖區的時候，還是個互斥問題。
信号量的定義
semaphore BufferNum;//空閑的緩沖區個數，初值為N
semaphore ProductNum;//緩沖區當中的産品個數，初值為0
semaphore Mutex;//用于互斥通路的信号量，初值為1
1 main()
2 {
3 cobegin
4 producer()；
5 consumer()；
6 coend
7 } 生産者程序
1 void producer(void)
2 {
3 int item；
4 while(TRUE)
5 {
6 item=produce_item()；//制造一個産品
7 P(BufferNum);//是否有空閑緩沖區
8 P(Mutex)；//進入臨界區
9 insert_item(item);//産品放入緩沖區
10 V(Mutex);//離開臨界區
11 V(ProductNum);//新增了一個産品
12 }
13 } 消費者程序
1 void consumer(void)
2 {
3 int item;
4 while(TRUE)
5 {
6 P(ProductNum);//緩沖區中有無産品
7 P(Mutex)；//進入臨界區
8 item=remove_item()//從緩沖區取産品
9 V(Mutex)；//離開臨界區
10 V(BufferNum);//新增一個空閑緩沖區
11 consume_item(item)；//使用該産品
12 }
13 } 2）哲學家就餐問題
1965年，由Dijkstra提出并解決，後來逐漸成為該領域的一個經典問題，或者說，是一塊試金石，用來試驗新的程序同步方法的優劣。
每個哲學家的動作隻有兩種：進餐和思考。當一個哲學家感到饑餓時，他試圖去獲得他左邊和右邊的兩把叉子（一次取一把，順序無關），然後才能開始進餐。吃完以後，他需要把兩把叉子放回原處，然後繼續思考。
問題是：如何保證哲學家們的動作有序進行?如：不出現相鄰者同時要求進餐，也不出現有人永遠拿不到叉子。
方案一
1 #define N 5 //哲學家個數
2 void philosopher(int i)//哲學家編号：0-4
3 {
4 while(TRUE)
5 {
6 think()；//哲學家在思考
7 take_fork(i);//去拿左邊的叉子
8 take_fork((i+1)%N);//去拿右邊的叉子
9 eat()；//吃面條中.…
10 put_fork(i)；//放下左邊的叉子
11 put_fork((i+1)%N)；//放下右邊的叉子
12 }
13 } 問題：不正确，可能導緻死鎖。
方案二
1 semaphore mutex //互斥信号量，初值
2 void philosopher(int i)//哲學家編号i：0-4
3 {
4 while(TRUE)
5 {
6 think()；//哲學家在思考
7 P(mutex)；//進入臨界區
8 take_fork(i)；//去拿左邊的叉子
9 take_fork((i+1)%N)；//去拿右邊的叉子
10 eat()；//吃面條中…
11 put_fork(i);//放下左邊的叉子
12 put_fork((i+1)%N)；//放下右邊的叉子
13 V(mutex)；//退出臨界區
14 }
15 } 問題：互斥通路。正确，但每次隻允許一人進餐
方案2的缺點：它把就餐（而不是叉子)看成是必須互斥通路的臨界資源，是以會造成（叉子)資源的浪費。從理論上說，如果有五把叉子，應允許兩個不相鄰的哲學家同時進餐。
哲學家就餐問題的解答
思路（1）哲學家自己怎麼來解決這個問題?
指導原則：要麼不拿，要麼就拿兩把叉子。
-S1思考中…
-S2進入饑餓狀态；
-S3如果左鄰居或右鄰居正在進餐，等待；否則轉S4
-S4拿起兩把叉子；
-S5吃面條…
-S6放下左邊的叉子；
-S7放下右邊的叉子；
-S8新的一天又開始了，轉S1
思路（2）計算機程式怎麼來解決這個問題?
指導原則：不能浪費CPU時間；程序間互相通信。
-S1思考中…
-S2進入饑餓狀态；
-S3如果左鄰居或右鄰居正在進餐，進入阻塞狀态；否則轉S4
-S4拿起兩把叉子；
-S5吃面條..…
-S6放下左邊的叉子，看看左鄰居現在能否進餐（饑餓狀态、兩把叉子都在），若能則喚醒之；
-S7放下右邊的叉子，看看右鄰居現在能否進餐，若能，喚醒之；
-S8新的一天又開始了，轉S1
思路（3）怎麼樣來編寫程式?
1.必須有一個資料結構，來描述每個哲學家的目前狀态；
2.該資料結構是一個臨界資源，各個哲學家對它的通路應該互斥地進行——程序互斥；
一個哲學家吃飽後，可能要喚醒它的左鄰右舍，兩者之間存在着同步關系——程序同步；
資料結構的定義
1 #define N 5//哲學家個數
2 #define LEFT (G+N-1)%N//第個哲學家的左鄰居
3 #define RIGHT (i+1)%N //第i個哲學家的右鄰居
4 #define THINKING 0//思考狀态
5 #define HUNGRY 1//饑餓狀态
6 #define EATING 2//進餐狀态
7 int state[N];//記錄每個人的狀态
8 semaphore mutex;//互斥信号量，初值1
9 semaphore s[N];//每人一個信号量，0 函數philosopher的定義
1 void philosopher(int i)//i的取值：0到N-1
2 {
3 while(TRUE)//封閉式開發，一直循環
4 {
5 think(）;//思考中…
6 take_forks(i)；//拿到兩把叉子或被阻塞
7 eat()；//吃面條中…
8 put_forks(i)；//把兩把叉子放回原處
9 }
10 } 函數take_forks的定義
1 //功能：要麼拿到兩把叉子，要麼被阻塞起來。
2 void take_forks(inti)//i的取值：0到N-1
3 {
4 P(mutex)；//進入臨界區
5 state[i]=HUNGRY;//我餓了!
6 test(i)；//試圖拿兩把叉子
7 V(mutex)；/退出臨界區
8 P(s[i])；//沒有叉子便阻塞
9 } 函數test的定義
1 void test(int i)//i的取值：0到N-1
2 {
3 if(stateli]=HUNGRY &&state[LEFT]!=EATING &&state[RIGHT]!=EATING)
4 {
5 state[i]=EATING；//兩把叉子到手
6 V(s[i])；//第i人可以吃飯了
7 }
8 } 函數put_forks的定義
1 //功能：把兩把叉子放回原處，并在需要的時候，去喚醒左鄰右舍。
2 void put_ forks(int i)//i的取值：0到N-1
3 {
4 P(mutex)；//進入臨界區
5 state[i]=THINKING；//交出兩把叉子
6 test(LEFT)；//看左鄰居能否進餐
7 test(RIGHT)；//看右鄰居能否進餐
8 V(mutex)；//退出臨界區
9 } 3）讀者一寫者問題
問題描述：在一個航空定票系統當中，有很多個競争的程序想要通路（讀、寫）系統的資料庫。
通路規則是：在任何時候，可以允許多個程序同時來讀，但如果有一個程序想要更新（寫）該資料庫，則其他的任何程序都不能通路，包括讀者和寫者。問題是：怎麼樣來程式設計實作讀者和寫者。
問題分析
任何時候“寫者”最多隻允許一個，而“讀者”可以有多個：
-“讀一寫”是互斥的；
-“寫一寫”是互斥的；
-“讀一讀”是允許的；
基于讀者優先政策的方法
假設讀者來：
1)若有其它讀者在讀，則不論是否有寫者在等，新讀者都可以讀（讀者優先）：
2)若無讀者、笃者，則新讀者也可以讀：
3）若無讀者，且有寫者在寫，則新讀者等待：
假設寫者來：
1)若有讀者，則新寫者等待：
2）若有其它寫者，則新寫者等待：
3）若無讀者和寫者，則新寫者可以寫；
-需要設定一個計數器rc，用來記錄并發運作的讀者個數；
-對于各個讀者而言，該計數器是一個臨界資源，對它的通路必須互斥進行，是以設定一個互斥信号量S_mutex；
-對于各個寫者而言、寫者與所有的讀者而言，資料庫是一個臨界資源，對它的通路必須互斥地進行，是以設定一個互斥信号量S_db。
讀者——寫者問題的一個解答
int rc=0；//并發讀者的個數
semaphore S_mutex;//對rc的互斥信号量，初值1
semaphore S_db;//對資料庫的信号量，初值1
void writer(void)
{
think_up_data()；//生成資料，非臨界區
P(S_db)；//希望通路資料庫
write_data_base()；//更新資料庫
V(S_db)；//退出臨界區
} 1 void reader(void)
2 {
3 P(S_mutex)；//互斥地通路計數器rc
4 rc++；//新增了一個讀者
5 if(rc=1) P(S_db)；//如果是第一個讀者…
6 V(S_mutex)；//退出對rc的通路
7 read_data_base()；//讀取資料庫的内容
8 P(S_mutex)；//互斥地通路計數器rc
9 rc--；//減少一個讀者
10 if(rc=0) V(S_db);//如果是最後一個讀者
11 V(S_mutex);//退出對rc的通路
12 use_data_read()；//使用資料，非臨界區
13 } 測試幾個例子：
RRW——R1進入，R2進入，W1在writer中P(S_db)被擋住
RWR——R1進入，W1在writer中P(S_db)被擋住，R2進入（展現了讀者優先）
WRR——W1進入，R1在reader中if後的P(S_db)被擋住，R2在reader中P(S_mutex)被擋住
5.程序排程
在多道系統當中，往往有多個程序同時在記憶體中運作。在任何時刻，一個程序隻可能是以下三種狀态之一：
-運作狀态：該程序正在CPU上運作，每個CPU上最多隻能有一個程序在運作；
-就緒狀态：程序已經就緒，随時可以運作；
-阻塞狀态：如在某個信号量上被阻塞，等待I/O
與此相對應，作業系統會維護相應的狀态隊列。
要解決的問題
WHEN:何時配置設定CPU一排程的時機
WHAT:按什麼原則配置設定CPU一排程算法
HOW:如何配置設定CPU一程序的上下文切換
何時排程？
1）當一個新的程序被建立時，是執行新程序還是繼續執行父程序?
2）當一個程序運作完畢時；
3）當一個程序由于I/O、信号量或其他的某個原因被阻塞時；
4）當一個I/O中斷發生時，表明某個I/O操作已經完成，而等待該I/O操作的程序轉入就緒狀态；
5）在分時系統中，當一個時鐘中斷發生時。
兩種排程方式
不可搶占排程方式：一個程序若被選中，就一直運作下去，直到它被阻塞（I/O，或正在等待其他的程序），或主動地交出CPU。以上的情形1一3均可發生排程；
可搶占排程方式：當一個程序在運作時，排程程式可以打斷它。以上的情形1-5均可發生排程。
程序切換
程序切換時需要做哪些事情？
儲存CPU寄存器中的值！
排程算法（自己看）
-優先級算法（Priority Scheduling)：給每個程序設定一個優先級，然後在所有就緒程序中選擇優先級最高的那個程序去運作；
-SJF就是一個優先級算法，每個程序的優先級是它的CPU運作時間（時間越短，優先級越高）；
-分為可搶占和不可搶占兩種方式；各程序優先級的确定方式可分為靜态和動态兩種。
優先級的确定
-靜态優先級方式
基本思路：在建立程序時确定程序的優先級，并保持不變直到程序結束；
缺點：高優先級的程序一直占用CPU，低優先級的程序“饑餓”。
-I/O繁忙程序：讓其進入最高優先級隊列，以及時啟動/O操作。通常隻需一個小時間片，即可處理完一次I/O請求，然後轉入到阻塞隊列。