第0章作业系导论

1、1第第 0 章章 作業系統導論作業系統導論內容內容： 作業系統簡介作業系統簡介 行程管理行程管理 處理機排班處理機排班 記憶體管理記憶體管理 虛擬記憶體管理虛擬記憶體管理 輸入輸入/輸出裝置管理輸出裝置管理 檔案系統管理檔案系統管理20-1 作業系統簡介作業系統簡介 內容內容 何謂作業系統何謂作業系統 電腦系統的架構電腦系統的架構 作業系統的功能作業系統的功能 作業系統的種類作業系統的種類第 0-1 章 作業系統簡介3作業系統簡介作業系統簡介 (1)0-1-1 何謂作業系統何謂作業系統 ？使用者與電腦硬體間的溝通橋樑，提供使用者個執行及操作程式的環境，讓使用使用者與電腦硬體間的溝通橋樑，提供使

2、用者個執行及操作程式的環境，讓使用者能夠很方便且迅速的操作電腦者能夠很方便且迅速的操作電腦主機與作業系統主機與作業系統ms-dos 作業系統作業系統 單一使用者單一使用者 / 單一工作單一工作 的工作平台的工作平台windows 作業系統作業系統 win 95.98.me是單一使用者是單一使用者 / 多工作多工作 的平台的平台 win nt開始開始 是多使用者是多使用者 / 多工作多工作 的平台的平台linux 作業系統作業系統 完全免費且於網路上公開原始碼的作業系統完全免費且於網路上公開原始碼的作業系統 fedora4主機與作業系統主機與作業系統5電腦系統的架構電腦系統的架構硬體（含韌體）硬

3、體（含韌體）硬體為電腦的實體裝置，包含記憶體、磁碟機、磁帶機、螢幕、鍵盤、滑鼠等設硬體為電腦的實體裝置，包含記憶體、磁碟機、磁帶機、螢幕、鍵盤、滑鼠等設備；這些設備都需透過適當的驅動程式來操作備；這些設備都需透過適當的驅動程式來操作般電腦都將管理程式燒錄在主機板上的般電腦都將管理程式燒錄在主機板上的eprom，並保持隨時可以啟動，稱之為，並保持隨時可以啟動，稱之為【韌體】【韌體】(firmware)核心核心依照韌體提供的功能，編寫一些較容易連結的函數，以供其他程式連結並透過它依照韌體提供的功能，編寫一些較容易連結的函數，以供其他程式連結並透過它來存取周邊設備，這些函數的整合體稱為【核心】來存取

4、周邊設備，這些函數的整合體稱為【核心】(kernel)外殼外殼編寫可以存取核心的程式，好讓般使用者操作，這就是【外殼】編寫可以存取核心的程式，好讓般使用者操作，這就是【外殼】(shell)應用程式應用程式使用者利用核心與外殼的標準介面程式來編寫應用軟體使用者利用核心與外殼的標準介面程式來編寫應用軟體(application program) ，大部分情況與硬體無關，程式設計師可以完全不用理會周邊硬體大部分情況與硬體無關，程式設計師可以完全不用理會周邊硬體6電腦系統架構電腦系統架構7系統程式與系統呼叫系統程式與系統呼叫我們會將硬體控制程式與最基本的電腦運作程序整合成一個稱之為【系統我們會將硬體控

5、制程式與最基本的電腦運作程序整合成一個稱之為【系統程式】程式】(system program) ，該程式提供電腦最根本的運作平台，再由此平，該程式提供電腦最根本的運作平台，再由此平台擴充功能，整合個強大的【作業系統】台擴充功能，整合個強大的【作業系統】系統程式提供許多關於週邊設備的函數，一般稱為【系統呼叫】系統程式提供許多關於週邊設備的函數，一般稱為【系統呼叫】(system call) ，藉由這些函數的呼叫，使用者就可以輕易存取周邊設備，藉由這些函數的呼叫，使用者就可以輕易存取周邊設備我們習慣將常駐於記憶體的庫存函數稱為核心，因為這些函數隨時會我們習慣將常駐於記憶體的庫存函數稱為核心，因為這

6、些函數隨時會被呼叫被呼叫 通常通常unix/linux的核心可讓使用者選擇所欲載入的函數，這是的核心可讓使用者選擇所欲載入的函數，這是unix/linux系統系統最引以為傲的地方，而最引以為傲的地方，而widows就望塵莫及就望塵莫及8作業系統的功能作業系統的功能控制程式（控制程式（control program） os提供控制所有周邊設備的功能提供控制所有周邊設備的功能人機介面（人機介面（user-machine interface） 使用者透過使用者透過os所提供的人機介面工具方便的操作電腦所提供的人機介面工具方便的操作電腦 此類型工具大多稱之為【命令】此類型工具大多稱之為【命令】(com

7、mand)延伸機器（延伸機器（extended machine） 使用者不需利用使用者不需利用0/1操作電腦，只要使用接近人類的語言就可以控制電腦，操作電腦，只要使用接近人類的語言就可以控制電腦，進一步讓電腦更接近人類的邏輯思維來處理事務進一步讓電腦更接近人類的邏輯思維來處理事務資源管理者（資源管理者（resource manager） 負責將負責將cpu、記憶體空間、磁碟空間、印表機與資料等資源分配給使用者、記憶體空間、磁碟空間、印表機與資料等資源分配給使用者程式，為了避免衝突發生，程式，為了避免衝突發生，os必須快速且合適地分配資源必須快速且合適地分配資源9作業系統的種類作業系統的種類批次

8、處理系統（批次處理系統（batch processing system） 早期電腦資源昂貴，多利用整批方式輸入給系統一起處理早期電腦資源昂貴，多利用整批方式輸入給系統一起處理多元處理系統（多元處理系統（multi-programming system） 多個程式同時存在記憶體中，多個程式同時存在記憶體中，cpu以某選定策略輪流執行這些程式以某選定策略輪流執行這些程式 使用者會感覺好像多個程式同時被執行使用者會感覺好像多個程式同時被執行(實際某時刻只有個程式執行實際某時刻只有個程式執行)分時處理系統（分時處理系統（time-sharing system） 將將cpu執行時間執行時間平均分配平均分

9、配給每一個使用者，讓多個程式可以共享給每一個使用者，讓多個程式可以共享cpu 所以無論程式大小，只要小段的時間用完，而不論工作是否執行完畢，所以無論程式大小，只要小段的時間用完，而不論工作是否執行完畢，都必須要換下一個程式使用都必須要換下一個程式使用10作業系統的種類作業系統的種類多工處理系統（多工處理系統（multi-task system）多處理機系統（多處理機系統（multi-processor system） 部電腦中有多個部電腦中有多個cpu同時處理同時處理 提供快速運算環境提供快速運算環境即時系統（即時系統（real-time system） 每個程式都有其優先權每個程式都有其優先

10、權(優先順序優先順序) ，優先權高的工作有優先處理的特權，優先權高的工作有優先處理的特權 必須在限定的時間內完成，否則逾時可能不具任何實質意義必須在限定的時間內完成，否則逾時可能不具任何實質意義11行程管理行程管理 (1)內容內容 何謂行程何謂行程 ？ 行程的生命週期行程的生命週期 行程的同步行程的同步 行程的死結行程的死結 行程的通訊行程的通訊12行程管理行程管理 (2)何謂行程何謂行程 (process)？ 行程行程-執行中的程式，屬於主動元件執行中的程式，屬於主動元件 程式程式 屬於被動元件屬於被動元件 行程在執行當中，會根據需要產生其他子行程行程在執行當中，會根據需要產生其他子行程(c

11、hild process)，交付給子，交付給子行程所要執行的工作行程所要執行的工作 行程又可分為【作業系統行程】與【使用者行程】行程又可分為【作業系統行程】與【使用者行程】 作業系統行程執行系統程式碼作業系統行程執行系統程式碼 使用者行程執行使用者程式碼使用者行程執行使用者程式碼13行程的特性與現象行程的特性與現象行程的特性行程的特性 行程式一個動態的概念行程式一個動態的概念 行程是程式與資料的結合體行程是程式與資料的結合體 行程可並行處理行程可並行處理 cpu速度夠快，可視為所有行程都正在執行中速度夠快，可視為所有行程都正在執行中行程的現象行程的現象 以象棋為範例以象棋為範例 行程間會互相競

12、爭行程間會互相競爭 因為因為cpu次僅能執行一個行程，所以系統中的行程可能需要經過競爭，次僅能執行一個行程，所以系統中的行程可能需要經過競爭，才能得到才能得到cpu資源，所以會涉及行程的排班問題資源，所以會涉及行程的排班問題14行程生命週期行程生命週期因為同時間僅有一個行程被選入執行，所以一個行程從產生到執行完畢因為同時間僅有一個行程被選入執行，所以一個行程從產生到執行完畢通常需要幾回合的執行周期才可以完成。通常需要幾回合的執行周期才可以完成。 執行狀態執行狀態 (running state) 行程執行中行程執行中 預備狀態（預備狀態（ready state） 行程已經取得所需的資源，正準備進

13、入行程已經取得所需的資源，正準備進入cpu執行執行 等待狀態（等待狀態（wait state） 在執行當中可能因為無法獲得某些資源或者逾時退出執行，就會進入等待在執行當中可能因為無法獲得某些資源或者逾時退出執行，就會進入等待 停止狀態（停止狀態（stop state） 行程執行完畢，等待被註銷行程執行完畢，等待被註銷 死結狀態（死結狀態（deadlock state） 行程可能在等待一個永遠無法獲得的資源，並繼續無止境等待行程可能在等待一個永遠無法獲得的資源，並繼續無止境等待15行程生命週期行程生命週期16行程生命週期行程生命週期掛起等待狀態（掛起等待狀態（suspend waited sta

14、te） 當當cpu工作負荷過重且難以承受時，會選擇某些行程將其掛起，並進入掛起等待狀工作負荷過重且難以承受時，會選擇某些行程將其掛起，並進入掛起等待狀態。甚至行程的程式與資料可能會被置換出去到外部輔助記憶體態。甚至行程的程式與資料可能會被置換出去到外部輔助記憶體(swap out)掛起預備狀態（掛起預備狀態（suspend ready state） 被掛起的行程欲再次進入執行階段，須先到掛起預備狀態，然後等待進入預備狀態。被掛起的行程欲再次進入執行階段，須先到掛起預備狀態，然後等待進入預備狀態。17行程的命令行程的命令建立（建立（fork） fork系統呼叫會產生一個子行程系統呼叫會產生一個子

15、行程(child process) ，產生行程者稱為父行程，產生行程者稱為父行程停止（停止（stop）撤銷（撤銷（destroy） 無論行程是正常停止或非正常停止，都需藉由撤銷命令釋回行程所佔用的無論行程是正常停止或非正常停止，都需藉由撤銷命令釋回行程所佔用的記憶體空間與相關資源記憶體空間與相關資源阻斷（阻斷（block） 行程從執行狀態行程從執行狀態 等待狀態等待狀態喚醒（喚醒（wakeup） 行程從等待狀態行程從等待狀態預備狀態預備狀態掛起（掛起（suspend）激活（激活（activate） 藉由激活讓系統重新配置記憶體空間以執行該行程藉由激活讓系統重新配置記憶體空間以執行該行程18行程

16、生命週期行程生命週期19臨界區間臨界區間(critical section)臨界區間臨界區間 就是指共享區域就是指共享區域 以交通系統為例，臨界區間就是交叉入口以交通系統為例，臨界區間就是交叉入口 以程式而言，臨界區間就是整體變數以程式而言，臨界區間就是整體變數(global variable) ex.sum 變數次只能允許個行程執行，否則會有競爭條件變數次只能允許個行程執行，否則會有競爭條件(race condition)出現出現 測試與設定（測試與設定（test-and-set, tas） k=flag; if (flag = 0) flag = 1;/flag = 表示該資源已經被取用表

17、示該資源已經被取用20行程同步行程同步號誌與號誌與 p/v 操作操作 (semaphore) 多重資源多重資源 s：可使用資源數量：可使用資源數量 p(s) ：取得共享資源：取得共享資源 if s 0 then s = s-1 else waiting . v(s) ：釋放共享資源：釋放共享資源 s = s +1 wakeup process21行程的死結預防行程的死結預防互斥（互斥（mutual exclusion） 除非資源取之不盡用之不竭，否則不可能達到資源互斥的需求除非資源取之不盡用之不竭，否則不可能達到資源互斥的需求佔用與等候（佔用與等候（hold and wait） 行程佔用一個資

18、源，而另個行程在等待被佔用的資源行程佔用一個資源，而另個行程在等待被佔用的資源 有可能發生【饑餓現象】有可能發生【饑餓現象】不可搶先（不可搶先（no pre-emption）循環式等候（循環式等候（circular wait） 個行程等個行程個行程等個行程22行程的通訊行程的通訊阻斷傳送（阻斷傳送（blocking send） 傳送端一直等到接收端接收訊息為止傳送端一直等到接收端接收訊息為止無阻斷傳送無阻斷傳送 （nonblocking send） 傳送端送出訊息，無須等待接收端接收，馬上可以重新操作傳送端送出訊息，無須等待接收端接收，馬上可以重新操作阻斷接收（阻斷接收（blocking re

19、ceive） 接收端一直等到有訊息出現接收端一直等到有訊息出現無阻斷接收（無阻斷接收（nonblocking receive） 接收端收到訊息或指示無有效資料接收端收到訊息或指示無有效資料 send (a, message) receive (b, message)23訊息緩衝通訊訊息緩衝通訊訊息緩衝通訊訊息緩衝通訊分時系統的任一時間只有一個行程會被啟動，欲達到兩個行程直接通訊是不可能的。分時系統的任一時間只有一個行程會被啟動，欲達到兩個行程直接通訊是不可能的。可以將傳送行程欲傳送給接收行程的訊息直接投入信箱內，接收行程再由信箱讀取信可以將傳送行程欲傳送給接收行程的訊息直接投入信箱內，接收行程

20、再由信箱讀取信息，所謂信箱就是主記憶體的某區塊空間，又稱為【訊息緩衝器】息，所謂信箱就是主記憶體的某區塊空間，又稱為【訊息緩衝器】 send (a, message) receive (a, message)24管道通訊管道通訊管道通訊管道通訊(pipe)主要缺點是容量有所限制，針對大量傳輸往往會發生緩衝器空間不足的問主要缺點是容量有所限制，針對大量傳輸往往會發生緩衝器空間不足的問題。題。原則上共享檔案只允許相互通訊的兩行程使用，並不分享給其他行程原則上共享檔案只允許相互通訊的兩行程使用，並不分享給其他行程250-3 處理機排班處理機排班 (1)內容內容 何謂處理機排班？何謂處理機排班？ 先到

21、先服務排班先到先服務排班 最短工作優先排班最短工作優先排班 最高等級優先排班最高等級優先排班 循環點名排班循環點名排班 多層次佇列排班多層次佇列排班 多層次反饋佇列排班多層次反饋佇列排班26處理機排班處理機排班何謂處理機排班何謂處理機排班 一部主機系統可以有很多個行程同時處於執行狀態，但是一部主機系統可以有很多個行程同時處於執行狀態，但是cpu在任一在任一時間內僅能處理一個行程，所以時間內僅能處理一個行程，所以cpu 如何由多個行程中選擇一個行程如何由多個行程中選擇一個行程執行執行 排班的重要因素排班的重要因素 cpu 使用率使用率 (utilization) cpu的等待是資源浪費，所以使用

22、率越高越好的等待是資源浪費，所以使用率越高越好 輸出量輸出量 (throughput) 回覆時間回覆時間 (turnaround time) 行程工作進入電腦系統到執行完畢離開電腦這一段時間稱之行程工作進入電腦系統到執行完畢離開電腦這一段時間稱之 等候時間等候時間 (waiting time) 般行程備般行程備cpu執行的時間不會太長，大部分都是花在排班等候執行的時間不會太長，大部分都是花在排班等候cpu27處理機排班處理機排班先到先服務排班先到先服務排班(first come first served, fcfs) 最基本也是最簡單的排班方法最基本也是最簡單的排班方法 系統只要挪出一個佇列器

23、系統只要挪出一個佇列器(queue) ，將所有進入等待執行的行程依序，將所有進入等待執行的行程依序排列，先進入者排在前面，後到者排在後面排列，先進入者排在前面，後到者排在後面 萬一所選擇的行程執行時間很長，或者甚至發生死結現象，將可萬一所選擇的行程執行時間很長，或者甚至發生死結現象，將可能導致整個系統停頓能導致整個系統停頓28處理機排班處理機排班最短工作優先排班最短工作優先排班 (shortest job first, sjf) 在目前所產生的行程當中，選擇最短執行時間的行程優先處理在目前所產生的行程當中，選擇最短執行時間的行程優先處理 所以必須有預估每一行程所需執行時間的能力，一但行程產生後

24、，就會所以必須有預估每一行程所需執行時間的能力，一但行程產生後，就會依照所預估執行時間的長短插入行程佇列器中適當位置等待執行依照所預估執行時間的長短插入行程佇列器中適當位置等待執行 缺點缺點 預估行程的執行時間並不容易預估行程的執行時間並不容易 針對較長時間的行程可能需耗費更多的等待時間，甚至永遠無法執針對較長時間的行程可能需耗費更多的等待時間，甚至永遠無法執行到，而產生飢餓現象行到，而產生飢餓現象29處理機排班處理機排班最高等級優先排班最高等級優先排班 (highest priority first, hpf) 依照優先權等級由高而低逐一執行依照優先權等級由高而低逐一執行 當行程不斷產生的同

25、時，一些較低優先權的行程，可能會不斷受到排擠，當行程不斷產生的同時，一些較低優先權的行程，可能會不斷受到排擠，造成需要更長的等待時間，甚至在某些情況可能永遠執行不到，這就是造成需要更長的等待時間，甚至在某些情況可能永遠執行不到，這就是飢餓現象。飢餓現象。30處理機排班處理機排班 (6)循環點名排班循環點名排班 (round-robin timesharing, rrt) 無論無論fcfs、sjf、hpf都是完成一個行程之後，才選擇下一個行程來都是完成一個行程之後，才選擇下一個行程來執行，所以若是某一行程佔用時間過久或者執行當中發生死結現象，執行，所以若是某一行程佔用時間過久或者執行當中發生死結

26、現象，將會導致系統效率低落將會導致系統效率低落 每一個行程只會執行一小段時間，時間一到，系統會停止行程繼續執每一個行程只會執行一小段時間，時間一到，系統會停止行程繼續執行且儲存該行程的所有狀態，然後由行且儲存該行程的所有狀態，然後由queue選擇一個行程執行，以此選擇一個行程執行，以此類推，直到所有行程執行完畢為止類推，直到所有行程執行完畢為止 分割時間片段夠小，所有行程就會有並行的感覺，但先決條件是分割時間片段夠小，所有行程就會有並行的感覺，但先決條件是cpu速度要夠快，否則太短的時間片段會造成耗費在行程前置作速度要夠快，否則太短的時間片段會造成耗費在行程前置作業時間比例太大導致效能嚴重低落

27、業時間比例太大導致效能嚴重低落31處理機排班處理機排班多層次佇列排班多層次佇列排班 (multi-level queue, mlq) 依照優先等級分成幾個不同型態依照優先等級分成幾個不同型態 每一個佇列器內的行程具有相同等級的優先權每一個佇列器內的行程具有相同等級的優先權 系統依照其優先權高低逐一執行系統依照其優先權高低逐一執行 可想而知很容易造成肌餓現象可想而知很容易造成肌餓現象32處理機排班處理機排班多層次反饋佇列排班多層次反饋佇列排班 (multi-level feedback queue, mlfq) 基於前者會產生飢餓現象，所以加上會自動提升優先等級的功能基於前者會產生飢餓現象，所以

28、加上會自動提升優先等級的功能 低優先權的會隨時間慢慢提升等級，所以最後一定會被執行到低優先權的會隨時間慢慢提升等級，所以最後一定會被執行到33處理器排班範例處理器排班範例分別就先到先服務、最短工作優先排班、循環點名排班分別就先到先服務、最短工作優先排班、循環點名排班(時間量時間量=1) 、優先、優先權排班權排班 算出回覆時間算出回覆時間 算出等候時間算出等候時間34回覆時間回覆時間等候時間等候時間350-4 記憶體管理記憶體管理 (1)內容內容 記憶體種類記憶體種類 基本概念基本概念 記憶體分配記憶體分配 分區管理分區管理 分頁管理分頁管理 分段管理分段管理 段頁式管理段頁式管理36記憶體種類

29、記憶體種類主記憶體主記憶體 主機板上的半導體記憶體主機板上的半導體記憶體 (sram、dram、rom) cpu可以直接存取記憶體上的程式或資料可以直接存取記憶體上的程式或資料外部記憶體外部記憶體 大多指外接的磁碟、光碟、磁帶等輔助記憶體，通常存放大多指外接的磁碟、光碟、磁帶等輔助記憶體，通常存放cpu暫不執暫不執行的程式或資料行的程式或資料 cpu無法直接執行外部記憶體所存取的程式無法直接執行外部記憶體所存取的程式 一般而言當記憶體不足儲存所有行程時，會將一些暫不執行的程式儲一般而言當記憶體不足儲存所有行程時，會將一些暫不執行的程式儲存於外部記憶體，當需要使用時，再由外部記憶體移入主記憶體讓

30、存於外部記憶體，當需要使用時，再由外部記憶體移入主記憶體讓cpu執行執行370-4 記憶體管理記憶體管理 (3)0-4-2 基本概念基本概念 主要工作主要工作 邏輯位址空間邏輯位址空間, 而不受實際空間限制而不受實際空間限制 多個行程同時駐留於主記憶體內，提升系統效能多個行程同時駐留於主記憶體內，提升系統效能 考慮四個問題考慮四個問題 主記憶體分配主記憶體分配 位址映射位址映射 由邏輯位址對應至實體位址的方法由邏輯位址對應至實體位址的方法 主記憶體保護主記憶體保護 分為系統程式與應用程式兩種位址空間，前者以儲存作業系統的核心分為系統程式與應用程式兩種位址空間，前者以儲存作業系統的核心程式或常駐

31、系統呼叫為主，不允許使用者直接呼叫存取程式或常駐系統呼叫為主，不允許使用者直接呼叫存取 虛擬記憶體虛擬記憶體 將外部輔助記憶體納入與主記憶體共同使用，讓使用者感覺主記憶體將外部輔助記憶體納入與主記憶體共同使用，讓使用者感覺主記憶體位址空間猶如邏輯位址空間一般位址空間猶如邏輯位址空間一般38記憶體分配記憶體分配分配策略分配策略 最先適合最先適合 (first fit, ff) 選擇第一個滿足請求容量的空閒區選擇第一個滿足請求容量的空閒區 最佳適合最佳適合 (best fit, bf) 找出能滿足請求容量的最小空閒區找出能滿足請求容量的最小空閒區 最壞適合最壞適合 (worst fit, wf)

32、從所有空閒區找出能滿足請求的最大空閒區從所有空閒區找出能滿足請求的最大空閒區390-4 記憶體管理記憶體管理 (5)0-4-3 記憶體分配記憶體分配 (2) 位址映射與保護位址映射與保護400-4 記憶體管理記憶體管理 (6)0-4-3 記憶體分配記憶體分配 (3) 覆蓋覆蓋410-4 記憶體管理記憶體管理 (7)0-4-3 記憶體分配記憶體分配 (4) 置換置換 主記憶體與外部輔助記憶體間交換程式或資料主記憶體與外部輔助記憶體間交換程式或資料 置換出置換出 (swap out) 程式由主記憶體移至輔助記憶體程式由主記憶體移至輔助記憶體 行程由等待狀態進入掛起狀態時行程由等待狀態進入掛起狀態時

33、 主記憶體空間不足時主記憶體空間不足時 置換入置換入 (swap in) 程式由輔助記憶體移入主記憶體程式由輔助記憶體移入主記憶體 行程由掛起狀態進入等待狀態時行程由掛起狀態進入等待狀態時 某些程序被重新呼叫而須喚起時某些程序被重新呼叫而須喚起時42分區管理分區管理固定分區管理固定分區管理 (靜態分區管理靜態分區管理) 運作方式是將主記憶體分割成若干個固定區塊，各個運作方式是將主記憶體分割成若干個固定區塊，各個區塊可以不相等區塊可以不相等 容易產生內部碎片容易產生內部碎片(internal fragmentation)43分區管理分區管理可變分區管理可變分區管理 (動態分區管理動態分區管理)

34、系統一開始不會將記憶體分割成固定區塊，而是作業欲載入時，再系統一開始不會將記憶體分割成固定區塊，而是作業欲載入時，再依照作業的大小分配一個適當的區塊供其載入，且區塊大小剛好符依照作業的大小分配一個適當的區塊供其載入，且區塊大小剛好符合作業大小合作業大小440-4 記憶體管理記憶體管理 (10)0-4-5 分頁管理分頁管理 (1) 分頁管理之概念分頁管理之概念作業 a - 分頁 0作業 a - 分頁 1作業 a - 分頁 2作業 a - 分頁 3作業 a - 分頁 4作業 a - 分頁 0作業 b - 分頁 0作業 b - 分頁 1作業 b - 分頁 2作業 b - 分頁 3作業 b - 分頁

35、4010分頁表分頁表主記憶體主記憶體12610.215316425.012113245332424作業 b - 分頁 012.作業 b - 分頁 113作業 a - 分頁 215.作業 a - 分頁 316作業 b - 分頁 424.作業 a - 分頁 425作業 b - 分頁 332.作業 b - 分頁 245.作業 a作業 a作業 b作業 b外部記憶體外部記憶體 (硬碟) (硬碟)作業 a - 分頁 126450-4 記憶體管理記憶體管理 (11)0-4-5 分頁管理分頁管理 (2) 位址映射位址映射cpu主記憶體主記憶體1220020ptcrptcrpdp (12)p (12)p (12

36、)p (12).111001214513240.pmt145200dlalapapa145200 邏輯位址 邏輯位址 實體位址 實體位址越界中斷越界中斷程式範圍：00000 20fff程式範圍：00000 20fff460-4 記憶體管理記憶體管理 (12)0-4-6 分段管理分段管理 (1) 實現原理實現原理作業 a - 分段 0作業 a - 分段 1作業 a - 分段 2作業 a - 分段 3作業 a - 分段 0作業 b - 分段 0作業 b - 分段 1作業 b - 分段 2010分段表分段表主記憶體主記憶體12610.215316012113245作業 b - 分段 012.作業 b

37、 - 分段 113作業 a - 分段 215.作業 a - 分段 316.作業 b - 分段 2 26作業 a作業 a作業 b作業 b外部記憶體外部記憶體 (硬碟) (硬碟)分分段段大大小小不不一一定定相相等等.作業 b - 分段 245470-4 記憶體管理記憶體管理 (13)0-4-6 分段管理分段管理 (2) 位址映射位址映射cpu主記憶體主記憶體1220020stcrpdp (12)p (12).1010012145smt145200dlapa145200 邏輯位址 邏輯位址 實體位址 實體位址越界中斷越界中斷.100300slbsnb越界中斷越界中斷dd480-4 記憶體管理記憶體管

38、理 (14)0-4-7 段頁式管理段頁式管理 位址映射位址映射sdlala 邏輯位址 邏輯位址 實體位址 實體位址分段表分段表作業 a作業 a.作業 b作業 b分頁表分頁表p.dsppapacpu主記憶體主記憶體490-5 虛擬記憶體管理虛擬記憶體管理 (1)內容內容 基本概念基本概念 動態分頁管理動態分頁管理 動態分段管理動態分段管理500-5 虛擬記憶體管理虛擬記憶體管理 (2)非虛擬記憶體系統之特性非虛擬記憶體系統之特性 整體性整體性 一個行程的全部實體在執行之前必須載入主一個行程的全部實體在執行之前必須載入主記憶體內記憶體內 駐留性駐留性 作業系統一但進入主記憶體內，便一直駐留作業系統

39、一但進入主記憶體內，便一直駐留直到執行結束才離開直到執行結束才離開 連續性連續性 一個行程分配的是一連續的主記憶體空間一個行程分配的是一連續的主記憶體空間510-5 虛擬記憶體管理虛擬記憶體管理 (3)虛擬記憶體管理的三個基本概念虛擬記憶體管理的三個基本概念 局部性局部性 只需將局部程式存放在主記憶體只需將局部程式存放在主記憶體 置換性置換性 目前暫時不使用或今後不再使用的部份程式先置換出記憶體目前暫時不使用或今後不再使用的部份程式先置換出記憶體 離散性離散性 行程佔據的主記憶體空間可以不必完全連續行程佔據的主記憶體空間可以不必完全連續三個管理策略三個管理策略 載入策略載入策略 - 什麼時候把

40、需要的部份從外部儲存體載入主記憶體什麼時候把需要的部份從外部儲存體載入主記憶體 分配策略分配策略 決定把載入的行程放置在主記憶體何處決定把載入的行程放置在主記憶體何處 淘汰策略淘汰策略 置換策略置換策略(當主記憶體空間已滿或目前可用空間無法容納當主記憶體空間已滿或目前可用空間無法容納)520-5 虛擬記憶體管理虛擬記憶體管理 (4)0-5-2 動態分頁管理動態分頁管理 (1) 管理技巧管理技巧 主記憶體劃分若干區塊主記憶體劃分若干區塊 (block) 將程式劃分為若干頁將程式劃分為若干頁 (page) 發生發生 “頁失誤中斷頁失誤中斷 ”, 則置換入則置換入 (swapping in) 主記憶

41、體空間不足主記憶體空間不足, 則置換出則置換出 (swapping out) 分頁表欄位分頁表欄位駐留位元駐留位元主記憶體區塊主記憶體區塊外部儲存體位址外部儲存體位址控制訊息控制訊息530-5 虛擬記憶體管理虛擬記憶體管理 (5)0-5-2 動態分頁管理動態分頁管理 (2) 頁失誤中斷程序頁失誤中斷程序主記憶體有空閒區塊虛擬頁不在主記憶體阻塞請求行程依照演算法選擇淘汰某一分頁 f該分頁是否修改過將分頁 f 寫入外部記憶體從外部記憶體讀入 p修改分頁表的駐留位元與位址喚醒請求行程是是是是否否否否54動態分頁管理動態分頁管理淘汰策略淘汰策略(演算法演算法) 先進先出先進先出 (first in f

42、irst out, fifo) 最先進入記憶體的那一頁會被移出最先進入記憶體的那一頁會被移出 最佳替換最佳替換 希望被移出的分頁是最久不會再被參考的那一頁希望被移出的分頁是最久不會再被參考的那一頁 最近最少使用最近最少使用 (least recently used, lru) 淘汰最進最少使用的分頁淘汰最進最少使用的分頁 最近最不常使用最近最不常使用 (least frequently used, lfu) 將過去參考頻率最低的分頁置換出去將過去參考頻率最低的分頁置換出去550-5 虛擬記憶體管理虛擬記憶體管理 (7)0-5-3 動態分段管理動態分段管理 分段表分段表 增加一個增加一個 “分段

43、長分段長”駐留位元主記憶體區塊外部儲存體位址控制訊息分段長560-6 輸入輸入/輸出管理輸出管理 (1)內容內容 基本概念基本概念 輸入輸入/輸出時機輸出時機 字元與區塊裝置字元與區塊裝置 緩衝器管理緩衝器管理 i/o 存取介面存取介面 spooling 管理管理570-6 輸入輸入/輸出管理輸出管理 (2)0-6-1 基本概念基本概念cpucpu中中央央處處理理單單元元主記憶體 輸入/輸出裝置data busaddress bus週邊裝置(如鍵盤)每一週邊設備對應一個 io 裝置每一週邊設備對應一個 io 裝置580-6 輸入輸入/輸出管理輸出管理 (3)0-6-2 輸入輸入/輸出時機輸出時

44、機 (1) 詢問詢問 (polling) 讓讓cpu週期性的詢問週期性的詢問i/o裝置是否有資料進入，若有資料進入，裝置是否有資料進入，若有資料進入，cpu再讀取該週邊設備上的資料再讀取該週邊設備上的資料 詢問間隔的長短詢問間隔的長短?監督程式 (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_dcp

45、u 詢問次序 :add_a, add_b, add_c, ., add_d590-6 輸入輸入/輸出管理輸出管理 (4)0-6-2 輸入輸入/輸出時機輸出時機 (2-1) 中斷處理的運作程序中斷處理的運作程序 周邊設備需要服務時才提出請求，將可省去不必要的詢問周邊設備需要服務時才提出請求，將可省去不必要的詢問 透過透過i/o裝置送出一個中斷訊號給裝置送出一個中斷訊號給cpu，確認中斷需求後，會暫停目前正，確認中斷需求後，會暫停目前正在執行的程式，並去執行事先已準備好中斷程式在執行的程式，並去執行事先已準備好中斷程式 中斷服務完成後，中斷服務完成後，cpu會回到原先被中斷的地方繼續執行未完成的程

46、式會回到原先被中斷的地方繼續執行未完成的程式cpu 接受中斷cpu 接受中斷暫停主程式暫停主程式timetime主程式主程式中斷中斷副程式副程式cpu 回復cpu 回復原來程式原來程式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) 多重週邊設備的中斷多重週邊設備的中斷c

47、pucpu中中央央處處理理單單元元data busaddress bus中斷中斷控制器控制器中斷訊號中斷訊號 int0int0int7io io 處理器處理器(0)(0)io io 處理器處理器(1)(1)io io 處理器處理器(7)(7)int1int3int7keyboardfaxhub630-6 輸入輸入/輸出管理輸出管理 (8)0-6-2 輸入輸入/輸出時機輸出時機 (2-5) 記憶體直接存取記憶體直接存取 (dma) 周邊設備直接與記憶體之間做資料讀取或寫入周邊設備直接與記憶體之間做資料讀取或寫入 dma控制器利用控制器利用cpu不使用匯流排的空閒時間不使用匯流排的空閒時間，取得其控制權並做資料，取得其控制權並做資料的輸入與輸出動作，稱為週期偷取的輸入與輸出動作，稱為週期偷取(cycle stealing)cpucpu中中央央處處理理單單元元主記憶主記憶體體data busdata busaddress busaddress busdmadma控制器控制器io 處理器io 處理器(磁碟控制(磁碟控制卡)卡)磁碟機磁碟機control buscontrol bus640-6 輸入輸入/輸出管理輸出管理 (9)0-6-3 字元與區塊裝置字元與區塊裝置 區塊輸入區塊輸入/輸出裝置輸出裝置 串列或並列傳輸串列或並列傳輸 字元輸入字元輸入/輸出