操作系統(tǒng)導論

1、1第第0章章 操作系統(tǒng)導論操作系統(tǒng)導論內(nèi)容內(nèi)容：操作系統(tǒng)簡介操作系統(tǒng)簡介行程管理行程管理處理機排班處理機排班內(nèi)存管理內(nèi)存管理虛擬內(nèi)存管理虛擬內(nèi)存管理輸入輸入/輸出裝置管理輸出裝置管理文件系統(tǒng)管理文件系統(tǒng)管理20-1操作系統(tǒng)簡介操作系統(tǒng)簡介內(nèi)容內(nèi)容何謂操作系統(tǒng)何謂操作系統(tǒng)計算機系統(tǒng)的架構(gòu)計算機系統(tǒng)的架構(gòu)操作系統(tǒng)的功能操作系統(tǒng)的功能操作系統(tǒng)的種類操作系統(tǒng)的種類第0-1章 操作系統(tǒng)簡介3操作系統(tǒng)簡介操作系統(tǒng)簡介(1)0-1-1何謂操作系統(tǒng)何謂操作系統(tǒng) ？用戶與計算機硬件間的溝通橋梁，提供使用者個執(zhí)行及操作程序的環(huán)境，讓用戶用戶與計算機硬件間的溝通橋梁，提供使用者個執(zhí)行及操作程序的環(huán)境，讓用戶能夠很方

2、便且迅速的操作計算機能夠很方便且迅速的操作計算機主機與操作系統(tǒng)主機與操作系統(tǒng)MS-DOS操作系統(tǒng)操作系統(tǒng) 單一使用者單一使用者/單一工作單一工作 的工作平臺的工作平臺Windows操作系統(tǒng)操作系統(tǒng) Win95.98.Me是單一使用者是單一使用者/多工作多工作 的平臺的平臺 WinNT開始開始 是多使用者是多使用者/多工作多工作 的平臺的平臺Linux操作系統(tǒng)操作系統(tǒng) 完全免費且于網(wǎng)絡上公開原始碼的操作系統(tǒng)完全免費且于網(wǎng)絡上公開原始碼的操作系統(tǒng) Fedora4主機與操作系統(tǒng)主機與操作系統(tǒng)5計算機系統(tǒng)的架構(gòu)計算機系統(tǒng)的架構(gòu)硬件（含韌體）硬件（含韌體）硬件為計算機的實體裝置，包含內(nèi)存、磁盤驅(qū)動器、磁

3、帶機、屏幕、鍵盤、鼠標硬件為計算機的實體裝置，包含內(nèi)存、磁盤驅(qū)動器、磁帶機、屏幕、鍵盤、鼠標等設備；這些設備都需透過適當?shù)尿?qū)動程序來操作等設備；這些設備都需透過適當?shù)尿?qū)動程序來操作般計算機都將管理程序刻錄在主板上的般計算機都將管理程序刻錄在主板上的EPROM，并保持隨時可以啟動，稱之為，并保持隨時可以啟動，稱之為【韌體韌體】(Firmware)核心核心依照韌體提供的功能，編寫一些較容易鏈接的函數(shù)，以供其他程序鏈接并透過它依照韌體提供的功能，編寫一些較容易鏈接的函數(shù)，以供其他程序鏈接并透過它來存取接口設備，這些函數(shù)的整合體稱為來存取接口設備，這些函數(shù)的整合體稱為【核心核心】(Kernel)外殼外

4、殼編寫可以存取核心的程序，好讓般使用者操作，這就是編寫可以存取核心的程序，好讓般使用者操作，這就是【外殼外殼】(Shell)應用程序應用程序用戶利用核心與外殼的標準接口程序來編寫應用軟用戶利用核心與外殼的標準接口程序來編寫應用軟體體(Application Program)，大部，大部分情況與硬件無關，程序設計師可以完全不用理會周邊硬件分情況與硬件無關，程序設計師可以完全不用理會周邊硬件6計算機系統(tǒng)架構(gòu)計算機系統(tǒng)架構(gòu)7系統(tǒng)程序與系統(tǒng)呼叫系統(tǒng)程序與系統(tǒng)呼叫我們會將硬件控制程序與最基本的計算機運作程序整合成一個稱之為我們會將硬件控制程序與最基本的計算機運作程序整合成一個稱之為【系系統(tǒng)程序統(tǒng)程序】(

5、System Program)，該程序提供計算機最根本的運作平臺，再由，該程序提供計算機最根本的運作平臺，再由此平臺擴充功能，整合個強大的此平臺擴充功能，整合個強大的【操作系統(tǒng)操作系統(tǒng)】系統(tǒng)程序提供許多關于外圍設備的函數(shù)，一般稱為系統(tǒng)程序提供許多關于外圍設備的函數(shù)，一般稱為【系統(tǒng)呼叫系統(tǒng)呼叫】(System call)，藉由這些函數(shù)的呼叫，用戶就可以輕易存取接口設備，藉由這些函數(shù)的呼叫，用戶就可以輕易存取接口設備我們習慣將常駐于內(nèi)存的庫存函數(shù)稱為我們習慣將常駐于內(nèi)存的庫存函數(shù)稱為核心核心，因為這些函數(shù)隨時會被，因為這些函數(shù)隨時會被呼叫呼叫通常通常Unix/Linux的核心可讓用戶選擇所欲加載的

6、函數(shù)，這是的核心可讓用戶選擇所欲加載的函數(shù)，這是Unix/Linux系統(tǒng)最系統(tǒng)最引以為傲的地方，而引以為傲的地方，而widows就望塵莫及就望塵莫及8操作系統(tǒng)的功能操作系統(tǒng)的功能控制程序（控制程序（Control program）OS提供控制所有接口設備的功能提供控制所有接口設備的功能人機界面（人機界面（User-machine interface）使用者透過使用者透過OS所提供的人機接口工具方便的操作計算機所提供的人機接口工具方便的操作計算機此類型工具大多稱之為此類型工具大多稱之為【命令命令】(command)延伸機器（延伸機器（Extended machine）使用者不需利用使用者不需利用

7、0/1操作計算機，只要使用接近人類的語言就可以控制計操作計算機，只要使用接近人類的語言就可以控制計算機，進一步讓計算機更接近人類的邏輯思維來處理事務算機，進一步讓計算機更接近人類的邏輯思維來處理事務資源管理者（資源管理者（Resource manager）負責將負責將CPU、內(nèi)存空間、磁盤空間、打印機與數(shù)據(jù)等資源分配給用戶程序，、內(nèi)存空間、磁盤空間、打印機與數(shù)據(jù)等資源分配給用戶程序，為了避免沖突發(fā)生，為了避免沖突發(fā)生，OS必須快速且合適地分配資源必須快速且合適地分配資源9操作系統(tǒng)的種類操作系統(tǒng)的種類批處理系統(tǒng)（批處理系統(tǒng)（Batch processing system）早期計算機資源昂貴，多利

8、用整批方式輸入給系統(tǒng)一起處理早期計算機資源昂貴，多利用整批方式輸入給系統(tǒng)一起處理多元處理系統(tǒng)（多元處理系統(tǒng)（Multi-programming system）多個程序同時存在內(nèi)存中，多個程序同時存在內(nèi)存中，CPU以某選定策略輪流執(zhí)行這些程序以某選定策略輪流執(zhí)行這些程序用戶會感覺好像多個程序同時被執(zhí)行用戶會感覺好像多個程序同時被執(zhí)行(實際某時刻只有個程序執(zhí)行實際某時刻只有個程序執(zhí)行)分時處理系統(tǒng)（分時處理系統(tǒng)（Time-sharing system）將將CPU運行時間運行時間平均分配平均分配給每一個用戶，讓多個程序可以共享給每一個用戶，讓多個程序可以共享CPU所以無論程序大小，只要小段的時間用完

9、，而不論工作是否執(zhí)行完畢，所以無論程序大小，只要小段的時間用完，而不論工作是否執(zhí)行完畢，都必須要換下一個程序使用都必須要換下一個程序使用10操作系統(tǒng)的種類操作系統(tǒng)的種類多任務處理系統(tǒng)（多任務處理系統(tǒng)（Multi-task system）多處理機系統(tǒng)（多處理機系統(tǒng)（Multi-processor system）部計算機中有多個部計算機中有多個CPU同時處理同時處理 提供快速運算環(huán)境提供快速運算環(huán)境實時系統(tǒng)（實時系統(tǒng)（Real-time system）每個程序都有其優(yōu)先權(quán)每個程序都有其優(yōu)先權(quán)(優(yōu)先順序優(yōu)先順序)，優(yōu)先權(quán)高的工作有優(yōu)先處理的特權(quán)，優(yōu)先權(quán)高的工作有優(yōu)先處理的特權(quán)必須在限定的時間內(nèi)完成，

10、否則逾時可能不具任何實質(zhì)意義必須在限定的時間內(nèi)完成，否則逾時可能不具任何實質(zhì)意義11行程管理行程管理(1)內(nèi)容內(nèi)容何謂行程何謂行程 ？行程的生命周期行程的生命周期行程的同步行程的同步行程的死結(jié)行程的死結(jié)行程的通訊行程的通訊12行程管理行程管理(2)何謂行程何謂行程(Process)？行程行程-執(zhí)行中的程序，屬于主動組件執(zhí)行中的程序，屬于主動組件 程序程序?qū)儆诒粍咏M件屬于被動組件行程在執(zhí)行當中，會根據(jù)需要產(chǎn)生其他子行程行程在執(zhí)行當中，會根據(jù)需要產(chǎn)生其他子行程(Child Process)，交付給子，交付給子行程所要執(zhí)行的工作行程所要執(zhí)行的工作行程又可分為行程又可分為【操作系統(tǒng)行程操作系統(tǒng)行程】與

11、與【使用者行程使用者行程】 操作系統(tǒng)行程執(zhí)行操作系統(tǒng)行程執(zhí)行系統(tǒng)程序代碼系統(tǒng)程序代碼 使用者行程執(zhí)行使用者行程執(zhí)行使用者程序代碼使用者程序代碼13行程的特性與現(xiàn)象行程的特性與現(xiàn)象行程的特性行程的特性行程序一個動態(tài)的概念行程序一個動態(tài)的概念行程是程序與數(shù)據(jù)的結(jié)合體行程是程序與數(shù)據(jù)的結(jié)合體行程可并行處理行程可并行處理 CPU速度夠快，可視為所有行程都正在執(zhí)行中速度夠快，可視為所有行程都正在執(zhí)行中行程的現(xiàn)象行程的現(xiàn)象以象棋為范例以象棋為范例行程間會互相競爭行程間會互相競爭 因為因為CPU次僅能執(zhí)行一個行程，所以系統(tǒng)中的行程可能需要經(jīng)過競爭，次僅能執(zhí)行一個行程，所以系統(tǒng)中的行程可能需要經(jīng)過競爭，才能得

12、到才能得到CPU資源，所以會涉及行程的排班問題資源，所以會涉及行程的排班問題14行程生命周期行程生命周期因為同時間僅有一個行程被選入執(zhí)行，所以一個行程從產(chǎn)生到執(zhí)行完畢因為同時間僅有一個行程被選入執(zhí)行，所以一個行程從產(chǎn)生到執(zhí)行完畢通常需要幾回合的執(zhí)行周期才可以完成。通常需要幾回合的執(zhí)行周期才可以完成。執(zhí)行狀態(tài)執(zhí)行狀態(tài)(Running state) 行程執(zhí)行中行程執(zhí)行中預備狀態(tài)（預備狀態(tài)（Ready state） 行程已經(jīng)取得所需的資源，正準備進入行程已經(jīng)取得所需的資源，正準備進入CPU執(zhí)行執(zhí)行等待狀態(tài)（等待狀態(tài)（Wait state） 在執(zhí)行當中可能因為無法獲得某些資源或者逾時退出執(zhí)行，就會進入

13、等待在執(zhí)行當中可能因為無法獲得某些資源或者逾時退出執(zhí)行，就會進入等待停止狀態(tài)（停止狀態(tài)（Stop state） 行程執(zhí)行完畢，等待被注銷行程執(zhí)行完畢，等待被注銷死結(jié)狀態(tài)（死結(jié)狀態(tài)（Deadlock state） 行程可能在等待一個永遠無法獲得的資源，并繼續(xù)無止境等待行程可能在等待一個永遠無法獲得的資源，并繼續(xù)無止境等待15行程生命周期行程生命周期16行程生命周期行程生命周期掛起等待狀態(tài)（掛起等待狀態(tài)（Suspend waited state） 當當CPU工作負荷過重且難以承受時，會選擇某些行程將其掛起，并進入掛起等待狀工作負荷過重且難以承受時，會選擇某些行程將其掛起，并進入掛起等待狀態(tài)。甚至行

14、程的程序與數(shù)據(jù)可能會被置換出去到外部輔助內(nèi)存態(tài)。甚至行程的程序與數(shù)據(jù)可能會被置換出去到外部輔助內(nèi)存(Swap out)掛起預備狀態(tài)（掛起預備狀態(tài)（Suspend ready state） 被掛起的行程欲再次進入運行時間，須先到掛起預備狀態(tài)，然后等待進入預備狀態(tài)。被掛起的行程欲再次進入運行時間，須先到掛起預備狀態(tài)，然后等待進入預備狀態(tài)。17行程的命令行程的命令建立（建立（fork）Fork系統(tǒng)呼叫會產(chǎn)生一個子系統(tǒng)呼叫會產(chǎn)生一個子行程行程(Child Process)，產(chǎn)生行程者稱為父行程，產(chǎn)生行程者稱為父行程停止（停止（stop）撤銷（撤銷（destroy）無論行程是正常停止或非正常停止，都需藉

15、由撤銷命令釋回行程所占用的無論行程是正常停止或非正常停止，都需藉由撤銷命令釋回行程所占用的內(nèi)存空間與相關資源內(nèi)存空間與相關資源阻斷（阻斷（block）行程從執(zhí)行狀態(tài)行程從執(zhí)行狀態(tài) 等待狀態(tài)等待狀態(tài)喚醒（喚醒（wakeup）行程從等待狀行程從等待狀態(tài)態(tài)預備狀態(tài)預備狀態(tài)掛起（掛起（suspend）激活（激活（activate）藉由激活讓系統(tǒng)重新配置內(nèi)存空間以執(zhí)行該行程藉由激活讓系統(tǒng)重新配置內(nèi)存空間以執(zhí)行該行程18行程生命周期行程生命周期19臨界區(qū)間臨界區(qū)間(Critical Section)臨界區(qū)間臨界區(qū)間就是指就是指共享區(qū)域共享區(qū)域 以交通系統(tǒng)為例，臨界區(qū)間就是交叉入口以交通系統(tǒng)為例，臨界區(qū)間就

16、是交叉入口 以程序而言，臨界區(qū)間就是整體變量以程序而言，臨界區(qū)間就是整體變量(Global Variable) Ex.SUM變量次只能允許個行程執(zhí)行，否則會有競爭條件變量次只能允許個行程執(zhí)行，否則會有競爭條件(Race Condition)出現(xiàn)出現(xiàn)測試與設定（測試與設定（Test-And-Set, TAS） K=flag; If (flag = 0) flag = 1;/flag =表示該資源已經(jīng)被取用表示該資源已經(jīng)被取用20行程同步行程同步號志與號志與P/V操作操作(Semaphore)多重資源多重資源S：可使用資源數(shù)量：可使用資源數(shù)量P(S)：取得共享資源：取得共享資源 if S 0 th

17、en S = S-1 else Waiting .V(S)：釋放共享資源：釋放共享資源 S = S +1 wakeup process21行程的死結(jié)預防行程的死結(jié)預防互斥（互斥（mutual exclusion）除非資源取之不盡用之不竭，否則不可能達到資源互斥的需求除非資源取之不盡用之不竭，否則不可能達到資源互斥的需求占用與等候（占用與等候（hold and wait）行程占用一個資源，而另個行程在等待被占用的資源行程占用一個資源，而另個行程在等待被占用的資源有可能發(fā)生有可能發(fā)生【饑餓現(xiàn)象饑餓現(xiàn)象】不可搶先（不可搶先（no pre-emption）循環(huán)式等候（循環(huán)式等候（circular wa

18、it）個行程等個行程個行程等個行程22行程的通訊行程的通訊阻斷傳送（阻斷傳送（Blocking Send）傳送端一直等到接收端接收訊息為止傳送端一直等到接收端接收訊息為止無阻斷傳送無阻斷傳送 （Nonblocking send）傳送端送出訊息，無須等待接收端接收，馬上可以重新操作傳送端送出訊息，無須等待接收端接收，馬上可以重新操作阻斷接收（阻斷接收（Blocking Receive）接收端一直等到有訊息出現(xiàn)接收端一直等到有訊息出現(xiàn)無阻斷接收（無阻斷接收（nonblocking Receive）接收端收到訊息或指示無有效數(shù)據(jù)接收端收到訊息或指示無有效數(shù)據(jù) Send (A, message) Re

19、ceive (B, message)23訊息緩沖通訊訊息緩沖通訊訊息緩沖通訊訊息緩沖通訊分時系統(tǒng)的任一時間只有一個行程會被啟動，欲達到兩個行程直接通訊是不可能的。分時系統(tǒng)的任一時間只有一個行程會被啟動，欲達到兩個行程直接通訊是不可能的。可以將傳送行程欲傳送給接收行程的訊息直接投入信箱內(nèi)，接收行程再由信箱讀取信可以將傳送行程欲傳送給接收行程的訊息直接投入信箱內(nèi)，接收行程再由信箱讀取信息，所謂息，所謂信箱信箱就是主存儲器的某區(qū)塊空間，又稱為就是主存儲器的某區(qū)塊空間，又稱為【訊息緩沖器訊息緩沖器】 Send (A, message) Receive (A, message)24管道通訊管道通訊管道通

20、訊管道通訊(Pipe)主要缺點是容量有所限制，針對大量傳輸往往會發(fā)生緩沖器空間不足的問主要缺點是容量有所限制，針對大量傳輸往往會發(fā)生緩沖器空間不足的問題。題。原則上共享檔案只允許相互通訊的兩行程使用，并不分享給其他行程原則上共享檔案只允許相互通訊的兩行程使用，并不分享給其他行程250-3處理機排班處理機排班(1)內(nèi)容內(nèi)容何謂處理機排班？何謂處理機排班？先到先服務排班先到先服務排班最短工作優(yōu)先排班最短工作優(yōu)先排班最高等級優(yōu)先排班最高等級優(yōu)先排班循環(huán)點名排班循環(huán)點名排班多層次隊列排班多層次隊列排班多層次反饋隊列排班多層次反饋隊列排班26處理機排班處理機排班何謂處理機排班何謂處理機排班一部主機系統(tǒng)可

21、以有很多個行程同時處于執(zhí)行狀態(tài)，但是一部主機系統(tǒng)可以有很多個行程同時處于執(zhí)行狀態(tài)，但是CPU在任一在任一時間內(nèi)僅能處理一個行程時間內(nèi)僅能處理一個行程，所以所以CPU如何由多個行程中選擇一個行程如何由多個行程中選擇一個行程執(zhí)行執(zhí)行排班的重要因素排班的重要因素 CPU使用率使用率(Utilization) CPU的等待是資源浪費，所以使用率越高越好的等待是資源浪費，所以使用率越高越好 輸出量輸出量(Throughput) 回復時間回復時間(Turnaround time) 行程工作進入計算機系統(tǒng)到執(zhí)行完畢離開計算機這一段時間稱之行程工作進入計算機系統(tǒng)到執(zhí)行完畢離開計算機這一段時間稱之 等候時間等候

22、時間(Waiting time) 般行程備般行程備CPU執(zhí)行的時間不會太長，大部分都是花在排班等候執(zhí)行的時間不會太長，大部分都是花在排班等候CPU27處理機排班處理機排班先到先服務排班先到先服務排班(First Come First Served, FCFS)最基本也是最簡單的排班方法最基本也是最簡單的排班方法系統(tǒng)只要挪出一個隊列系統(tǒng)只要挪出一個隊列器器(Queue)，將所有進入等待執(zhí)行的行程依序排，將所有進入等待執(zhí)行的行程依序排列，先進入者排在前面，后到者排在后面列，先進入者排在前面，后到者排在后面萬一所選擇的行程運行時間很長，或者甚至發(fā)生萬一所選擇的行程運行時間很長，或者甚至發(fā)生死結(jié)死結(jié)現(xiàn)

23、象，將可現(xiàn)象，將可能導致整個系統(tǒng)停頓能導致整個系統(tǒng)停頓28處理機排班處理機排班最短工作優(yōu)先排班最短工作優(yōu)先排班(Shortest Job First, SJF)在目前所產(chǎn)生的行程當在目前所產(chǎn)生的行程當中中，選擇最短運行時間的行程優(yōu)先處理，選擇最短運行時間的行程優(yōu)先處理所以必須有預估每一行程所需運行時間的能力，一但行程產(chǎn)生后，就會所以必須有預估每一行程所需運行時間的能力，一但行程產(chǎn)生后，就會依照所預估運行時間的長短插入行程隊列器中適當位置等待執(zhí)行依照所預估運行時間的長短插入行程隊列器中適當位置等待執(zhí)行 缺點缺點 預估行程的運行時間并不容易預估行程的運行時間并不容易 針對較長時間的行程可能需耗費更

24、多的等待時間，甚至永遠無法執(zhí)針對較長時間的行程可能需耗費更多的等待時間，甚至永遠無法執(zhí)行到，而產(chǎn)生行到，而產(chǎn)生饑餓現(xiàn)象饑餓現(xiàn)象29處理機排班處理機排班最高等級優(yōu)先排班最高等級優(yōu)先排班(Highest Priority First, HPF)依照優(yōu)先權(quán)等級由高而低逐一執(zhí)行依照優(yōu)先權(quán)等級由高而低逐一執(zhí)行當行程不斷產(chǎn)生的同時，一些較低優(yōu)先權(quán)的行程，可能會不斷受到排擠，當行程不斷產(chǎn)生的同時，一些較低優(yōu)先權(quán)的行程，可能會不斷受到排擠，造成需要更長的等待時間，甚至在某些情況可能永遠執(zhí)行不到，這就是造成需要更長的等待時間，甚至在某些情況可能永遠執(zhí)行不到，這就是饑餓現(xiàn)象。饑餓現(xiàn)象。30處理機排班處理機排班(6

25、)循環(huán)點名排班循環(huán)點名排班(Round-Robin Timesharing, RRT)無論無論FCFS、SJF、HPF都是完成一個行程之后，才選擇下一個行程來都是完成一個行程之后，才選擇下一個行程來執(zhí)行，所以若是某一行程占用時間過久或者執(zhí)行當中發(fā)生死結(jié)現(xiàn)象，執(zhí)行，所以若是某一行程占用時間過久或者執(zhí)行當中發(fā)生死結(jié)現(xiàn)象，將會導致系統(tǒng)效率低落將會導致系統(tǒng)效率低落每一個行程只會執(zhí)行一小段時間，時間一到，系統(tǒng)會停止行程繼續(xù)執(zhí)每一個行程只會執(zhí)行一小段時間，時間一到，系統(tǒng)會停止行程繼續(xù)執(zhí)行且儲存該行程的所有狀態(tài)，然后由行且儲存該行程的所有狀態(tài)，然后由Queue選擇一個行程執(zhí)行，以此選擇一個行程執(zhí)行，以此類推

26、，直到所有行程執(zhí)行完畢為止類推，直到所有行程執(zhí)行完畢為止 分割時間片段夠小，所有行程就會有并行的感覺，但先決條件是分割時間片段夠小，所有行程就會有并行的感覺，但先決條件是CPU速度要夠快，否則太短的時間片段會造成耗費在行程前置作速度要夠快，否則太短的時間片段會造成耗費在行程前置作業(yè)時間比例太大導致效能嚴重低落業(yè)時間比例太大導致效能嚴重低落31處理機排班處理機排班多層次隊列排班多層次隊列排班(Multi-Level Queue, MLQ)依照優(yōu)先等級分成幾個不同型態(tài)依照優(yōu)先等級分成幾個不同型態(tài)每一個隊列器內(nèi)的行程具有相同等級的優(yōu)先權(quán)每一個隊列器內(nèi)的行程具有相同等級的優(yōu)先權(quán)系統(tǒng)依照其優(yōu)先權(quán)高低逐一

27、執(zhí)行系統(tǒng)依照其優(yōu)先權(quán)高低逐一執(zhí)行 可想而知很容易造成肌餓現(xiàn)象可想而知很容易造成肌餓現(xiàn)象32處理機排班處理機排班多層次反饋隊列排班多層次反饋隊列排班(Multi-Level Feedback Queue, MLFQ)基于前者會產(chǎn)生饑餓現(xiàn)象，所以加上會自動提升優(yōu)先等級的功能基于前者會產(chǎn)生饑餓現(xiàn)象，所以加上會自動提升優(yōu)先等級的功能 低優(yōu)先權(quán)的會隨時間慢慢提升等級，所以最后一定會被執(zhí)行到低優(yōu)先權(quán)的會隨時間慢慢提升等級，所以最后一定會被執(zhí)行到33處理器排班范例處理器排班范例分別就先到先服務、最短工作優(yōu)先排班、循環(huán)點名排班分別就先到先服務、最短工作優(yōu)先排班、循環(huán)點名排班(時間量時間量=1)、優(yōu)先、優(yōu)先權(quán)排

28、班權(quán)排班算出回復時間算出回復時間算出等候時間算出等候時間34回復時間回復時間等候時間等候時間350-4內(nèi)存管理內(nèi)存管理(1)內(nèi)容內(nèi)容內(nèi)存種類內(nèi)存種類基本概念基本概念內(nèi)存分配內(nèi)存分配分區(qū)管理分區(qū)管理分頁管理分頁管理分段管理分段管理段頁式管理段頁式管理36內(nèi)存種類內(nèi)存種類主存儲器主存儲器主板上的半導體內(nèi)存主板上的半導體內(nèi)存(SRAM、DRAM、ROM)CPU可以直接存取內(nèi)存上的程序或數(shù)據(jù)可以直接存取內(nèi)存上的程序或數(shù)據(jù)外部內(nèi)存外部內(nèi)存大多指外接的磁盤、光盤、磁帶等輔助內(nèi)存，通常存放大多指外接的磁盤、光盤、磁帶等輔助內(nèi)存，通常存放CPU暫不執(zhí)行暫不執(zhí)行的程序或數(shù)據(jù)的程序或數(shù)據(jù)CPU無法直接執(zhí)行外部內(nèi)存

29、所存取的程序無法直接執(zhí)行外部內(nèi)存所存取的程序一般而言當內(nèi)存不足儲存所有行程時，會將一些暫不執(zhí)行的程序儲存一般而言當內(nèi)存不足儲存所有行程時，會將一些暫不執(zhí)行的程序儲存于外部內(nèi)存，當需要使用時，再由外部內(nèi)存移入主存儲器讓于外部內(nèi)存，當需要使用時，再由外部內(nèi)存移入主存儲器讓CPU執(zhí)行執(zhí)行370-4內(nèi)存管理內(nèi)存管理(3)0-4-2基本概念基本概念主要工作主要工作 邏輯地址空間邏輯地址空間,而不受實際空間限制而不受實際空間限制 多個行程同時駐留于主存儲器內(nèi)，提升系統(tǒng)效能多個行程同時駐留于主存儲器內(nèi)，提升系統(tǒng)效能考慮四個問題考慮四個問題 主存儲器分配主存儲器分配 地址映像地址映像 由邏輯地址對應至實體地址

30、的方法由邏輯地址對應至實體地址的方法 主存儲器保護主存儲器保護 分為系統(tǒng)程序與應用程序兩種地址空間，前者以儲存操作系統(tǒng)的核心分為系統(tǒng)程序與應用程序兩種地址空間，前者以儲存操作系統(tǒng)的核心程序或常駐系統(tǒng)呼叫為主，不允許使用者直接呼叫存取程序或常駐系統(tǒng)呼叫為主，不允許使用者直接呼叫存取 虛擬內(nèi)存虛擬內(nèi)存 將外部輔助內(nèi)存納入與主存儲器共同使用，讓用戶感覺主存儲器地址將外部輔助內(nèi)存納入與主存儲器共同使用，讓用戶感覺主存儲器地址空間猶如邏輯地址空間一般空間猶如邏輯地址空間一般38內(nèi)存分配內(nèi)存分配分配策略分配策略最先適合最先適合(First Fit, FF) 選擇第一個滿足請求容量的空閑區(qū)選擇第一個滿足請求

31、容量的空閑區(qū)最佳適合最佳適合(Best Fit, BF) 找出能滿足請求容量的最小空閑區(qū)找出能滿足請求容量的最小空閑區(qū)最壞適合最壞適合(Worst Fit, WF) 從所有空閑區(qū)找出能滿足請求的最大空閑區(qū)從所有空閑區(qū)找出能滿足請求的最大空閑區(qū)390-4內(nèi)存管理內(nèi)存管理(5)0-4-3內(nèi)存分配內(nèi)存分配(2)地址映像與保護地址映像與保護400-4內(nèi)存管理內(nèi)存管理(6)0-4-3內(nèi)存分配內(nèi)存分配(3)覆蓋覆蓋410-4內(nèi)存管理內(nèi)存管理(7)0-4-3內(nèi)存分配內(nèi)存分配(4)置換置換主存儲器與外部輔助內(nèi)存間交換程序或數(shù)據(jù)主存儲器與外部輔助內(nèi)存間交換程序或數(shù)據(jù) 置換出置換出(Swap out) 程序由主存

32、儲器移至輔助內(nèi)存程序由主存儲器移至輔助內(nèi)存 行程由等待狀態(tài)進入掛起狀態(tài)時行程由等待狀態(tài)進入掛起狀態(tài)時 主存儲器空間不足時主存儲器空間不足時 置換入置換入(Swap in) 程序由輔助內(nèi)存移入主存儲器程序由輔助內(nèi)存移入主存儲器 行程由掛起狀態(tài)進入等待狀態(tài)時行程由掛起狀態(tài)進入等待狀態(tài)時 某些程序被重新呼叫而須喚起時某些程序被重新呼叫而須喚起時42分區(qū)管理分區(qū)管理固定分區(qū)管理固定分區(qū)管理(靜態(tài)分區(qū)管理靜態(tài)分區(qū)管理)運作方式是將主存儲器分割成若干個固定區(qū)塊，各個運作方式是將主存儲器分割成若干個固定區(qū)塊，各個區(qū)塊可以不相等區(qū)塊可以不相等 容易產(chǎn)生內(nèi)部碎片容易產(chǎn)生內(nèi)部碎片(Internal Fragmen

33、tation)43分區(qū)管理分區(qū)管理可變分區(qū)管理可變分區(qū)管理(動態(tài)分區(qū)管理動態(tài)分區(qū)管理)系統(tǒng)一開始不會將內(nèi)存分割成固定區(qū)塊，而是作業(yè)欲加載時，再依系統(tǒng)一開始不會將內(nèi)存分割成固定區(qū)塊，而是作業(yè)欲加載時，再依照作業(yè)的大小分配一個適當?shù)膮^(qū)塊供其載入，且區(qū)塊大小剛好符合照作業(yè)的大小分配一個適當?shù)膮^(qū)塊供其載入，且區(qū)塊大小剛好符合作業(yè)大小作業(yè)大小440-4內(nèi)存管理內(nèi)存管理(10)0-4-5分頁管理分頁管理(1)分頁管理之概念分頁管理之概念作業(yè) A - 分頁 0作業(yè) A - 分頁 1作業(yè) A - 分頁 2作業(yè) A - 分頁 3作業(yè) A - 分頁 4作業(yè) A - 分頁 0作業(yè) B - 分頁 0作業(yè) B - 分頁

34、 1作業(yè) B - 分頁 2作業(yè) B - 分頁 3作業(yè) B - 分頁 4010分頁表分頁表主記憶體主記憶體12610.215316425.012113245332424作業(yè) B - 分頁 012.作業(yè) B - 分頁 113作業(yè) A - 分頁 215.作業(yè) A - 分頁 316作業(yè) B - 分頁 424.作業(yè) A - 分頁 425作業(yè) B - 分頁 332.作業(yè) B - 分頁 245.作業(yè) A作業(yè) A作業(yè) B作業(yè) B外部記憶體外部記憶體 (硬碟) (硬碟)作業(yè) A - 分頁 126450-4內(nèi)存管理內(nèi)存管理(11)0-4-5分頁管理分頁管理(2)地址映像地址映像CPU主記憶體主記憶體1220020

35、PTCRPTCRPdP (12)P (12)P (12)P (12).111001214513240.PMT145200dLALAPAPA145200 邏輯位址 邏輯位址 實體位址 實體位址越界中斷越界中斷程式範圍：00000 20FFF程式範圍：00000 20FFF460-4內(nèi)存管理內(nèi)存管理(12)0-4-6分段管理分段管理(1)實現(xiàn)原理實現(xiàn)原理作業(yè) A - 分段 0作業(yè) A - 分段 1作業(yè) A - 分段 2作業(yè) A - 分段 3作業(yè) A - 分段 0作業(yè) B - 分段 0作業(yè) B - 分段 1作業(yè) B - 分段 2010分段表分段表主記憶體主記憶體12610.2153160121132

36、45作業(yè) B - 分段 012.作業(yè) B - 分段 113作業(yè) A - 分段 215.作業(yè) A - 分段 316.作業(yè) B - 分段 2 26作業(yè) A作業(yè) A作業(yè) B作業(yè) B外部記憶體外部記憶體 (硬碟) (硬碟)分分段段大大小小不不一一定定相相等等.作業(yè) B - 分段 245470-4內(nèi)存管理內(nèi)存管理(13)0-4-6分段管理分段管理(2)地址映像地址映像CPU主記憶體主記憶體1220020STCRPdP (12)P (12).1010012145SMT145200dLAPA145200 邏輯位址 邏輯位址 實體位址 實體位址越界中斷越界中斷.100300SLbSNb越界中斷越界中斷dd48

37、0-4內(nèi)存管理內(nèi)存管理(14)0-4-7段頁式管理段頁式管理地址映像地址映像sdLALA 邏輯位址 邏輯位址 實體位址 實體位址分段表分段表作業(yè) A作業(yè) A.作業(yè) B作業(yè) B分頁表分頁表p.dspPAPACPU主記憶體主記憶體490-5虛擬內(nèi)存管理虛擬內(nèi)存管理(1)內(nèi)容內(nèi)容基本概念基本概念動態(tài)分頁管理動態(tài)分頁管理動態(tài)分段管理動態(tài)分段管理500-5虛擬內(nèi)存管理虛擬內(nèi)存管理(2)非虛擬內(nèi)存系統(tǒng)之特性非虛擬內(nèi)存系統(tǒng)之特性整體性整體性 一個行程的全部實體在執(zhí)行之前必須加載主一個行程的全部實體在執(zhí)行之前必須加載主存儲器內(nèi)存儲器內(nèi)駐留性駐留性 操作系統(tǒng)一但進入主存儲器內(nèi)，便一直駐留操作系統(tǒng)一但進入主存儲器

38、內(nèi)，便一直駐留直到執(zhí)行結(jié)束才離開直到執(zhí)行結(jié)束才離開連續(xù)性連續(xù)性 一個行程分配的是一連續(xù)的主存儲器空間一個行程分配的是一連續(xù)的主存儲器空間510-5虛擬內(nèi)存管理虛擬內(nèi)存管理(3)虛擬內(nèi)存管理的三個基本概念虛擬內(nèi)存管理的三個基本概念局部性局部性 只需將局部程序存放在主存儲器只需將局部程序存放在主存儲器置換性置換性 目前暫時不使用或今后不再使用的部份程序先置換出內(nèi)存目前暫時不使用或今后不再使用的部份程序先置換出內(nèi)存離散性離散性 行程占據(jù)的主存儲器空間可以不必完全連續(xù)行程占據(jù)的主存儲器空間可以不必完全連續(xù)三個管理策略三個管理策略載入策略載入策略-什么時候把需要的部份從外部存儲器加載主存儲器什么時候把需

39、要的部份從外部存儲器加載主存儲器分配策略分配策略決定把加載的行程放置在主存儲器何處決定把加載的行程放置在主存儲器何處淘汰策略淘汰策略置換策略置換策略(當主存儲器空間已滿或目前可用空間無法容納當主存儲器空間已滿或目前可用空間無法容納)520-5虛擬內(nèi)存管理虛擬內(nèi)存管理(4)0-5-2動態(tài)分頁管理動態(tài)分頁管理(1)管理技巧管理技巧 主存儲器劃分若干區(qū)塊主存儲器劃分若干區(qū)塊(block) 將程序劃分為若干頁將程序劃分為若干頁(page) 發(fā)生發(fā)生 “頁失誤中斷頁失誤中斷”,則置換入則置換入(swapping in) 主存儲器空間主存儲器空間不足不足,則置換出則置換出(swapping out)分頁表

40、字段分頁表字段駐留位元駐留位元主記憶體區(qū)塊主記憶體區(qū)塊外部儲存體位址外部儲存體位址控制訊息控制訊息530-5虛擬內(nèi)存管理虛擬內(nèi)存管理(5)0-5-2動態(tài)分頁管理動態(tài)分頁管理(2)頁失誤中斷程序頁失誤中斷程序主記憶體有空閒區(qū)塊虛擬頁不在主記憶體阻塞請求行程依照演算法選擇淘汰某一分頁 F該分頁是否修改過將分頁 F 寫入外部記憶體從外部記憶體讀入 P修改分頁表的駐留位元與位址喚醒請求行程是是是是否否否否54動態(tài)分頁管理動態(tài)分頁管理淘汰策略淘汰策略(算法算法)先進先出先進先出(First In First Out, FIFO) 最先進入內(nèi)存的那一頁會被移出最先進入內(nèi)存的那一頁會被移出最佳替換最佳替換

41、希望被移出的分頁是最久不會再被參考的那一頁希望被移出的分頁是最久不會再被參考的那一頁最近最少使用最近最少使用(Least Recently Used, LRU) 淘汰最進最少使用的分頁淘汰最進最少使用的分頁最近最不常使用最近最不常使用(Least Frequently Used, LFU) 將過去參考頻率最低的分頁置換出去將過去參考頻率最低的分頁置換出去550-5虛擬內(nèi)存管理虛擬內(nèi)存管理(7)0-5-3動態(tài)分段管理動態(tài)分段管理分段表分段表 增加一個增加一個 “分段長分段長”駐留位元主記憶體區(qū)塊外部儲存體位址控制訊息分段長560-6輸入輸入/輸出管理輸出管理(1)內(nèi)容內(nèi)容基本概念基本概念輸入輸入

42、/輸出時機輸出時機字符與成組設備字符與成組設備緩沖器管理緩沖器管理I/O存取界面存取界面Spooling管理管理570-6輸入輸入/輸出管理輸出管理(2)0-6-1基本概念基本概念CPUCPU中中央央處處理理單單元元主記憶體 輸入/輸出裝置Data BusAddress Bus週邊裝置(如鍵盤)每一週邊設備對應一個 IO 裝置每一週邊設備對應一個 IO 裝置580-6輸入輸入/輸出管理輸出管理(3)0-6-2輸入輸入/輸出時機輸出時機(1) 詢問詢問(Polling) 讓讓CPU周期性的詢問周期性的詢問I/O裝置是否有數(shù)據(jù)進入，若有數(shù)據(jù)進入，裝置是否有數(shù)據(jù)進入，若有數(shù)據(jù)進入，CPU再讀取該外圍

43、設備上的數(shù)據(jù)再讀取該外圍設備上的數(shù)據(jù) 詢問間隔的長短詢問間隔的長短?監(jiān)督程式 (Monitor)IO 裝置(A)Add_AAdd_AData BusData BusIO 裝置(B)IO 裝置(C)IO 裝置(D)Add_BAdd_BAdd_CAdd_CAdd_DAdd_DData BusData BusScannerKeyboardMouseFaxCPU 詢問次序 :Add_A, Add_B, Add_C, ., Add_DCPU 詢問次序 :Add_A, Add_B, Add_C, ., Add_D590-6輸入輸入/輸出管理輸出管理(4)0-6-2輸入輸入/輸出時機輸出時機(2-1) 中斷

44、處理的運作程序中斷處理的運作程序 接口設備需要服務時才提出請求，將可省去不必要的詢問接口設備需要服務時才提出請求，將可省去不必要的詢問 透過透過I/O裝置送出一個中斷訊號給裝置送出一個中斷訊號給CPU，確認中斷需求后，會暫停目前正，確認中斷需求后，會暫停目前正在執(zhí)行的程序，并去執(zhí)行事先已準備好中斷程序在執(zhí)行的程序，并去執(zhí)行事先已準備好中斷程序 中斷服務完成后，中斷服務完成后，CPU會回到原先被中斷的地方繼續(xù)執(zhí)行未完成的程序會回到原先被中斷的地方繼續(xù)執(zhí)行未完成的程序CPU 接受中斷CPU 接受中斷暫停主程式暫停主程式TimeTime主程式主程式中斷中斷副程式副程式CPU 回復CPU 回復原來程式

45、原來程式600-6輸入輸入/輸出管理輸出管理(5)0-6-2輸入輸入/輸出時機輸出時機(2-2) 中斷處理的硬件連接中斷處理的硬件連接610-6輸入輸入/輸出管理輸出管理(6)0-6-2輸入輸入/輸出時機輸出時機(2-3) 中斷處理的中斷處理的I/O處理器功能處理器功能620-6輸入輸入/輸出管理輸出管理(7)0-6-2輸入輸入/輸出時機輸出時機(2-4) 多重外圍設備的中斷多重外圍設備的中斷CPUCPU中中央央處處理理單單元元Data BusAddress Bus中斷中斷控制器控制器中斷訊號中斷訊號 INT0INT0INT7IO IO 處理器處理器(0)(0)IO IO 處理器處理器(1)(

46、1)IO IO 處理器處理器(7)(7)INT1INT3INT7KeyboardFaxHub630-6輸入輸入/輸出管理輸出管理(8)0-6-2輸入輸入/輸出時機輸出時機(2-5) 內(nèi)存直接存取內(nèi)存直接存取(DMA) 接口設備直接與內(nèi)存之間做數(shù)據(jù)讀取或?qū)懭虢涌谠O備直接與內(nèi)存之間做數(shù)據(jù)讀取或?qū)懭?DMA控制器利用控制器利用CPU不使用總線的空閑時不使用總線的空閑時間間，取得其控制權(quán)并做數(shù)據(jù)的輸，取得其控制權(quán)并做數(shù)據(jù)的輸入與輸出動作，稱為入與輸出動作，稱為周期偷取周期偷取(Cycle Stealing)CPUCPU中中央央處處理理單單元元主記憶主記憶體體Data BusData BusAddress BusAddress BusDMADMA控制器控制器IO 處理器IO 處理器(磁碟控制(磁碟控制卡)卡)磁碟機磁碟機Control BusControl Bus640-6輸入輸入/輸出管理輸出管理(9)0-6-3字符與成組設備字符與成組設備區(qū)塊輸入?yún)^(qū)塊輸入/輸出裝置輸出裝置 串行或并列傳輸串行或并列傳輸字