1、處理器管理第1頁，共102頁，2022年，5月20日，13點7分，星期二處理器管理的地位第2頁，共102頁，2022年，5月20日，13點7分，星期二主要內容3.1 進程的引入3.2進程的概念3.3進程控制3.4線程3.5處理器調度3.6調度算法3.7處理器調度和實時調度第3頁，共102頁，2022年，5月20日，13點7分，星期二程序的執行方式(順序)順序執行特征：順序性、封閉性、可再現性I1C1P1I2C2P2第4頁，共102頁，2022年，5月20日，13點7分，星期二程序的執行方式(并發)并發執行I1I2I3I4C1C2C3C4P1P2P3P4t第5頁，共102頁，2022年，5月20

2、日，13點7分，星期二程序的執行方式(并發)特征第6頁，共102頁，2022年，5月20日，13點7分，星期二與并發有關的錯誤第7頁，共102頁，2022年，5月20日，13點7分，星期二3.2 進程的概念問題引入 程序這個靜態概念已不能如實反映程序并發執行過程的特征。為了深刻描述程序動態執行過程的性質，人們引入“進程（Process）”概念。第8頁，共102頁，2022年，5月20日，13點7分，星期二3.2 進程的概念程序在處理機上執行時所發生的活動(Dijkstra)。是一個容器，該容器用以聚集相關資源。（）進程是一個具有獨立功能的程序關于某個數據集合的一次運行活動。是系統進行資源分配和

3、調度的單位。第9頁，共102頁，2022年，5月20日，13點7分，星期二3.2 進程的概念操作級:圖形窗口界面:一個窗口就是一個進程打開窗口：建立一個進程關閉窗口：一個進程結束字符命令界面:一條命令一般就是一個進程命令行尾回車:一個進程開始命令執行結束(下一命令提示符出現):一個進程結束編程級：進程建立：“建立進程”函數或系統調用進程結束：“撤消進程”函數或系統調用，或者程序的正常或非正常結束。第10頁，共102頁，2022年，5月20日，13點7分，星期二進程和程序的區別 程序靜態的， 進程是動態的。 程序和進程的組成不同：進程=程序+數據+PCB 程序的存在是永久的，程序的存在是暫時的。

4、 一個程序可以對應多個進程，一個進程可包含多個程序。第11頁，共102頁，2022年，5月20日，13點7分，星期二進程的特征動態性：進程是個動態的概念，有一定的生命周期，要經歷創建、執行、撤銷過程。 結構性 ：它由進程控制塊、程序段和數據段組成 。并發性 ：在一個系統內可以同時存在多個進程，它們通過交替使用處理器，從而實現并發執行。異步性：指進程之間在交替使用計算機資源時沒有強制的順序，按各自獨立的、不可預知的速度向前推進 。獨立性：進程是系統分配資源和進行調度的獨立單位。第12頁，共102頁，2022年，5月20日，13點7分，星期二3.2.2 進程的狀態 進程從創建而產生至撤銷而消亡的整

5、個生命周期，可用一組狀態加以刻畫，按進程在執行過程中的狀況至少定義三種不同的進程狀態： 運行態（Running） 就緒狀態（Ready） 阻塞狀態（Blocked）當前進程已經分配到CPU，它的程序正在處理機上執行的狀態。已具備運行條件，但因為其他進程正在占用CPU,使它暫時不能運行而處于等待分配CPU的狀態。進程因等待某種事件發生（例如等待I/O操作完成，等待其他進程發來的信號）而暫時不能運行的狀態，也就是說，處于阻塞狀態的進程尚不具備運行條件，即使CPU空閑它也無法使用。第13頁，共102頁，2022年，5月20日，13點7分，星期二3.2.2 進程的狀態引起進程狀態轉換原因就緒- 運行時

6、間一到，調度程序選擇一個新的進程運行運行- 就緒運行進程用完了時間片；運行進程被中斷，因為一高優先級進程處于就緒狀態第14頁，共102頁，2022年，5月20日，13點7分，星期二3.2.2 進程的狀態引起進程狀態轉換原因運行- 阻塞當一進程所需的東西必須等待時對一資源的訪問尚不能進行初始化I/O 且必須等待結果等待某一進程提供輸入阻塞- 就緒當所等待的事件發生時第15頁，共102頁，2022年，5月20日，13點7分，星期二3.2.2 進程的狀態進程三種狀態的轉換第16頁，共102頁，2022年，5月20日，13點7分，星期二3.2.2 進程的狀態 有一個計算機科學家，有一天女兒過生日，想親

7、手給女兒做一個生日蛋糕。所以他就找了一本有關做蛋糕的食譜，買了一些原料，面粉、雞蛋、糖、香料等，然后邊看邊學邊做。 食譜程序；科學家CPU； 原料數據；做蛋糕進程； 這時小兒子哭著跑進來，說手被蜜蜂蟄了。教授只好把蛋糕先放在一邊。他在食譜上做了個標記，把狀態信息記錄了起來。然后又去找了一本醫療手冊，查到了相關的內容，按照上面的指令一步步地執行。當傷口處理完之后，又回到廚房繼續做蛋糕。 CPU從一個進程（做蛋糕）切換到另一個進程（醫療救護）。第17頁，共102頁，2022年，5月20日，13點7分，星期二3.2.2 進程的狀態五狀態模型：新建態就緒態：允許進入運行態完成態：執行完第18頁，共10

8、2頁，2022年，5月20日，13點7分，星期二3.2.2 進程的狀態問題出現進程掛起（suspend） 進程不斷創建，系統資源已不滿足進程運行的要求，系統就必須把某些進程掛起，即將進程對換到磁盤中，暫時不參與進程調度，已達到平衡操作系統負荷的目的。引起進程掛起原因(P45-46：(1)-(4)第19頁，共102頁，2022年，5月20日，13點7分，星期二掛起（Suspend):把一個進程從內存轉到外存。激活（Activate）:把一個進程從外存轉到內存。第20頁，共102頁，2022年，5月20日，13點7分，星期二引入掛起狀態后的七狀態模型第21頁，共102頁，2022年，5月20日，1

9、3點7分，星期二Linux進程的狀態 D Uninterruptible sleep (usually IO)R Running or runnable (on run queue)S Interruptible sleep (waiting for an event to complete)T Stopped, either by a job control signal or because it is being traced.X dead (should never be seen)Z Defunct (zombie) process, terminated but not reape

10、d by its parent. high-priority (not nice to other users)N low-priority (nice to other users)L has pages locked into memory (for real-time and custom IO)s is a session leaderl is multi-threaded (using CLONE_THREAD, like NPTL pthreads do)+ is in the foreground process group第22頁，共102頁，2022年，5月20日，13點7分

11、，星期二例題 1如果系統中有N個進程，運行的進程最多幾個，最少幾個；就緒進程最多幾個最少幾個；等待進程最多幾個，最少幾個？ 解答：在單處理機系統中，處于運行狀態的進程最多為1個，最少為0個；處于就緒進程最多為N-1個，最少為0個；處于阻塞的進程最多為N個，最少為0個。 2. 有沒有這樣的狀態轉換，為什么？ （1） 等待運行； （2） 就緒等待第23頁，共102頁，2022年，5月20日，13點7分，星期二3.2.3 進程控制塊進程描述進程控制塊程序和數據組成了進程的實體（靜態文本）需要一個數據結構來描述進程當前狀態、本身特性、對資源的占用以及調度信息等，即進程控制塊（Process Contr

12、ol Block,PCB）進程程序+數據+PCB第24頁，共102頁，2022年，5月20日，13點7分，星期二3.2.3 進程控制塊第25頁，共102頁，2022年，5月20日，13點7分，星期二3.2.3 進程控制塊PCB是進程存在的唯一標志；PCB常駐內存pid進程狀態現場優先級阻塞原因程序地址同步機制資源清單鏈接指針第26頁，共102頁，2022年，5月20日，13點7分，星期二CPU在進程之間的切換第27頁，共102頁，2022年，5月20日，13點7分，星期二PCB的組織鏈表：同一狀態的進程其PCB組成一鏈表，多個狀態對應多個不同的鏈表。各狀態的進程形成不同的鏈表：就緒鏈表、阻塞鏈

13、表第28頁，共102頁，2022年，5月20日，13點7分，星期二鏈表執行指針就緒隊列指針阻塞隊列指針1PCB90PCB89PCB77PCB6PCB58PCB40PCB33PCB24PCB1PCB的組織第29頁，共102頁，2022年，5月20日，13點7分，星期二PCB的組織索引表：同一狀態的進程歸入一個index表（由index指向PCB），多個狀態對應多個不同的index表各狀態的進行形成不同的索引表：就緒索引表、阻塞索引表第30頁，共102頁，2022年，5月20日，13點7分，星期二3.2.3 進程控制塊PCB的組織索引表執行指針就緒表指針阻塞表指針PCB7PCB6PCB5PCB4P

14、CB3PCB2PCB1第31頁，共102頁，2022年，5月20日，13點7分，星期二補充PCB和進程的代碼數據放在一起嗎？系統態和用戶態系統空間和用戶空間第32頁，共102頁，2022年，5月20日，13點7分，星期二3.3 進程控制OS如何管理和控制進程必須知道進程的位置（依賴于所使用的存儲管理方案）必須知道進程的屬性（PCB）必須能夠創建、撤銷進程必須能夠改變進程的狀態第33頁，共102頁，2022年，5月20日，13點7分，星期二 進程控制的職責： 進程的創建 進程的撤消 進程的阻塞與喚醒 進程控制是通過執行各種原語來實現的。3.3 進程控制第34頁，共102頁，2022年，5月20日

15、，13點7分，星期二原語是由若干條機器指令構成的、用于完成特定功能的一段程序。原語在執行過程中是不可分割的。（P47）3.3 進程控制第35頁，共102頁，2022年，5月20日，13點7分，星期二3.3.3 進程的創建進程圖引起創建進程的事件進程的創建過程123第36頁，共102頁，2022年，5月20日，13點7分，星期二3.3.3 進程的創建ABCDEIJFHLMKGABCDEIJFHLMKG第37頁，共102頁，2022年，5月20日，13點7分，星期二入口查PCB鏈表有空PCB取空表PCB(i)填PCB(i)相應項PCB(i)入就緒隊列PCB(i)入進程家族返回創建失敗YN第38頁，

16、共102頁，2022年，5月20日，13點7分，星期二進程創建#include #include pid_t fork(void);功能：創建一個新的進程。返回值：在子進程中為0，在父進程中為子進程ID，出錯為-1第39頁，共102頁，2022年，5月20日，13點7分，星期二進程創建該函數被調用一次，但返回兩次。兩次返回的區別是子進程的返回值是0，而父進程的返回值則是子進程的進程ID一般來說，在fork之后是父進程先執行還是子進程先執行是不確定的。這取決于內核所使用的調度算法。新創建的子進程是父進程的完全克隆,會復制父進程的數據段、堆、棧空間（共享代碼段） 。第40頁，共102頁，2022年

17、，5月20日，13點7分，星期二進程相關術語init 進程領養：當父進程在子進程結束前結束，子進程變成了孤兒進程，孤兒進程被init進程收養，子進程的父進程就變成了init進程。僵尸進程當子進程在父進程結束前結束，如果父進程沒有釋放子進程的資源(默認)，那么子進程就變成了一個僵尸進程。第41頁，共102頁，2022年，5月20日，13點7分，星期二進程創建第42頁，共102頁，2022年，5月20日，13點7分，星期二3.3.4 引起進程終止的事件壽終：進程運行完自行退出自殺：進程因錯誤而自行退出第43頁，共102頁，2022年，5月20日，13點7分，星期二3.3.2 引起進程終止的事件他殺

18、：進程被其它進程強行殺死或由用戶殺死處決：進程因異常而強行終結第44頁，共102頁，2022年，5月20日，13點7分，星期二 檢索相應的PCB，讀其狀態 若處于執行狀態，則終止執行 若有子孫進程則終止子孫進程 釋放終止進程的全部資源 將PCB從隊列中移出3.3.4 進程的終止過程第45頁，共102頁，2022年，5月20日，13點7分，星期二入口查進程鏈表有此PCB釋放該進程所占資源釋放該PCB結構本身返回出錯處理有子進程無有有無第46頁，共102頁，2022年，5月20日，13點7分，星期二3.3.3 進程的阻塞與喚醒1、引起進程阻塞的事件2、進程阻塞的過程3、進程喚醒的過程4、喚醒原語的

19、執行過程第47頁，共102頁，2022年，5月20日，13點7分，星期二引起進程阻塞的事件啟動某種操作請求系統服務新數據尚未到達無新工作可做第48頁，共102頁，2022年，5月20日，13點7分，星期二 執行狀態的進程調用阻塞原語 進程變為阻塞狀態 PCB進入阻塞隊列 轉進程調度程序，進行切換進程阻塞的過程第49頁，共102頁，2022年，5月20日，13點7分，星期二被阻塞進程期待的事件發生。由發現者進程調用喚醒原語 喚醒阻塞進程。阻塞進程進入就緒狀態。進程喚醒的過程第50頁，共102頁，2022年，5月20日，13點7分，星期二3.3 進程控制Linux進程控制原語:進程創建 fork進

20、程監控 ps進程終止 kill第51頁，共102頁，2022年，5月20日，13點7分，星期二3.4 線程線程的引入進程：資源分配單位和CPU調度單位缺點：時間空間開銷大，限制并發度的提高將程序塊的執行從進程中分離出來程序塊執行需要單獨的：執行狀態：寄存器內容、棧、局部內存程序塊執行不需要單獨的：進程資源：如文件、頁表內容等多線程：將一個程序分成多個并發的活動（程序塊）第52頁，共102頁，2022年，5月20日，13點7分，星期二3.4 線程進程=線程+資源集進程作為擁有資源的基本單位，線程是系統調度的基本單位。第53頁，共102頁，2022年，5月20日，13點7分，星期二3.4 線程進程

21、和線程資源所有權（Process）調度的實體（Thread）第54頁，共102頁，2022年，5月20日，13點7分，星期二3.4 線程線程描述線程狀態（運行、就緒、等待）一個執行棧未運行時保存的線程上下文、靜態存儲局部變量對內存和其他進程資源的訪問與該進程中其他線程共享資源第55頁，共102頁，2022年，5月20日，13點7分，星期二3.4 線程用戶級線程由應用程序（線程庫）實現線程管理（POSIX Pthreads、Win32 threads）內核感覺不到線程的存在優點共享一個進程用戶空間中，線程管理不需要內核模式的切換可運行任何OS上，內核無需修改。缺點全阻塞不能運用多處理技術第56頁

22、，共102頁，2022年，5月20日，13點7分，星期二3.4 線程用戶級線程第57頁，共102頁，2022年，5月20日，13點7分，星期二內核級線程（在處理機上被調度和執行的對象）由內核實現線程管理克服了用戶級線程的缺點線程切換需要到內核的模式切換3.4 線程第58頁，共102頁，2022年，5月20日，13點7分，星期二內核級線程3.4 線程第59頁，共102頁，2022年，5月20日，13點7分，星期二3.4 線程第60頁，共102頁，2022年，5月20日，13點7分，星期二程序、進程、線程的比較程序：一組有序指令的集合進程：系統分配資源的基本單位線程：處理機調度的基本單位3.4 線

23、程第61頁，共102頁，2022年，5月20日，13點7分，星期二3.4 線程多線程編程優點：響應程度高資源共享經濟多處理器體系結構利用第62頁，共102頁，2022年，5月20日，13點7分，星期二第63頁，共102頁，2022年，5月20日，13點7分，星期二第64頁，共102頁，2022年，5月20日，13點7分，星期二3.5 處理器調度請思考：我們是如何確定在任意時刻到底哪個進程執行，哪個不執行呢？進程管理的一個主要任務就是選擇下一個要運行的進程。第65頁，共102頁，2022年，5月20日，13點7分，星期二要解決的問題WHAT:按什么原則分配CPU 進程調度算法WHEN:何時分配C

24、PU 進程調度時機HOW：如何分配CPU 進程調度方式 3.5 處理器調度第66頁，共102頁，2022年，5月20日，13點7分，星期二WHAT:選擇進程調度算法的標準CPU利用率用戶程序響應時間系統吞吐量公平合理設備利用率第67頁，共102頁，2022年，5月20日，13點7分，星期二WHEN:進程調度時機時間片過期進程退出進程阻塞I/O中斷發生第68頁，共102頁，2022年，5月20日，13點7分，星期二HOW:進程調度方式 1.非搶占方式:簡單，實時性差 2.搶占方式:（1）時間片原則（2）優先權原則（3）短作業優先原則。 第69頁，共102頁，2022年，5月20日，13點7分，星

25、期二處理器調度的層次第70頁，共102頁，2022年，5月20日，13點7分，星期二（1）CPU利用率 CPU利用率=CPU有效工作時間/CPU總運行時間=CPU有效工作時間/(CPU有效工作時間+ CPU空閑等待時間)（2）吞吐量（特別用于批處理） 使得單位時間內處理的作業數盡可能多。選擇調度算法的原則(面向系統)第71頁，共102頁，2022年，5月20日，13點7分，星期二（3）周轉時間 從作業提交給系統開始，到作業完成為止的時間間隔稱作作業周轉時間。 作業周轉時間： ti = tf - ts 實際上，ti 是作業在系統里等待時間和運行時間之和。 平均作業周轉時間:選擇調度算法的原則(面

26、向用戶)第72頁，共102頁，2022年，5月20日，13點7分，星期二（4）響應時間 交互式進程從提交一個請求到接收到響應之間的時間間隔。（5）公平性 確保每個用戶每個進程獲得合理的CPU份額和其它資源份額，不會出現餓死的情況。選擇調度算法的原則(面向用戶)第73頁，共102頁，2022年，5月20日，13點7分，星期二調度算法一(FCFS)1、先來先服務(First-come,first-served,FCFS) 最先進入就緒進程首先分配到CPU，FCFS策略可用FIFO隊列實現缺點：只顧及到等候時間，沒有考慮要求服務時間長短。（不利于短作業）第74頁，共102頁，2022年，5月20日，

27、13點7分，星期二例:如下一組進程P1、P2、P3，到達系統的先后順序分別如下面三圖所示，計算各種順序的平均周轉時間進程到達時間運行時間P1028P219P323進程到達時間運行時間P209P1128P323進程到達時間運行時間P303P219P1228第75頁，共102頁，2022年，5月20日，13點7分，星期二P1P2P3T=(28+36+38)/3=34P2P1P3T=(9+36+38)/3=27.6P3P2P1T=(3+11+38)/3=17.3可見，FCFS算法的平均作業周轉時間與作業提交及調度的順序有關。第76頁，共102頁，2022年，5月20日，13點7分，星期二調度算法二(

28、SJF)2、短作業優先（shortest-job-first,SJF） 以進入系統的作業所要求的CPU時間長短為標準，總是選取估計計算時間最短的作業投入運行。 第77頁，共102頁，2022年，5月20日，13點7分，星期二進程名到達時間運行時間P106P208P307P403采用SJF調度：P4P1P3P2T=13ms采用FCFS調度：P1P2P3P4T=16.25ms第78頁，共102頁，2022年，5月20日，13點7分，星期二SJF缺點： 難以精確估計作業所需CPU時間，如程序員估計過低，系統可能提前終止該作業。 忽視作業等待時間，由于系統不斷接受新作業，而調度算法又總選計算時間短的作

29、業投入運行，因此，使進入系統時間早但計算時間長的作業等待時間長，會出現饑餓現象。 第79頁，共102頁，2022年，5月20日，13點7分，星期二可搶占式SJF算法(SRTF) 當一個新作業到達就緒隊列，如果新作業需要的CPU時間短，則強行趕走當前作業，這種算法也叫最短剩余時間優先算法（shortest remaining time first,SRTF）。第80頁，共102頁，2022年，5月20日，13點7分，星期二進程名到達時間運行時間P108P214P329P435SRTF:P1P2P4P1P3T=13msSJF:P1P2P4P3T=14.25ms第81頁，共102頁，2022年，5月

30、20日，13點7分，星期二調度算法三(HRRF)3、高響應比優先調度（Highest Response Ratio First,HRRF) FCFS和SJF都是比較片面和調度算法，FCFS只考慮作業等候時間而忽視了作業計算時間，SJF正好相反，本算法是一種折衷算法，既考慮作業等待時間，又考慮作業運行時間，這樣既照顧了短作業又不使長作業等待時間過長，改進了調度性能。 第82頁，共102頁，2022年，5月20日，13點7分，星期二HRRF響應比=響應時間/要求服務時間 =（等待時間+運行時間）/運行時間 =1+等待時間/運行時間缺點：每次計算各道作業的響應比會有一定時間開銷，性能比SJF略差。第

31、83頁，共102頁，2022年，5月20日，13點7分，星期二作業名到達時間運行時間P1020P2515P3105P41510SJF:P1P3P4P2T=25msFCFS:P1P2P3P4T=28.75msHRRF:P1P3P2P4T=26.25ms第84頁，共102頁，2022年，5月20日，13點7分，星期二調度算法四 優先級調度算法優先級可以通過內部或外部方式來定義。內部優先級使用一些可測量數據以計算進程優先級。外部優先級是通過操作系統之外的準則來設置的。優先級調度可以是可搶占的或者非搶占的。第85頁，共102頁，2022年，5月20日，13點7分，星期二靜態優先級：創建進程時就確定，直

32、到進程終止前都不改變。通常是一個整數。依據：進程類型（系統進程優先級較高）對資源的需求（對CPU和內存需求少的優先級較高）用戶要求（緊迫程度和付費多少）動態優先級：在創建進程時賦予優先級，在進程運行過程中可以自動改變，以后便獲得更好的調度性能。如：在就緒隊列中等待時間延長則優先級提高，使優先級較低的進程在等待足夠了的時間后，其優先級提高到可被調度執行。進程每執行一個時間片，就降低其優先級。第86頁，共102頁，2022年，5月20日，13點7分，星期二進程名到達時間運行時間優先級P10103P2011P3024P4015P5052優先級調度算法P2P5 P1 P3 P4T=12第87頁，共10

33、2頁，2022年，5月20日，13點7分，星期二優先級調度算法缺點：無窮阻塞（indefinite blocking）或饑餓（starvation）解決方案之一:老化在1973年關閉MIT的IBM7094時，發現有一個低優先級進程是于1967年提交但是一直未運行第88頁，共102頁，2022年，5月20日，13點7分，星期二調度算法五(RR)4、輪轉法調度（Round-robin,RR） 系統將所有的進程按先進先出的原則排成一個隊列，將新來的進程加到就緒隊列的末尾，每當執行調度時，調度程序從就緒隊列中選第一個進程，分配一個時間片，將CPU分配給進程，時間片一般為10ms100ms。 第89頁，

34、共102頁，2022年，5月20日，13點7分，星期二RR進程需要CPU的時間小于一個時間片的時間： 進程本身會釋放CPU，進程調度程序接著處理就緒隊列的下一個進程。進程所需CPU的時間大于一個時間片的時間： 定時器會切斷當前進程，進行上下文切換，該進程被加到隊列尾部，接著進程調度程序選擇就緒隊列中的下一下進程。第90頁，共102頁，2022年，5月20日，13點7分，星期二進程名到達時間運行時間P1024P203P303RR(注：時間片為4ms)P1P2P3P1P1P1P1P1T=15.67ms第91頁，共102頁，2022年，5月20日，13點7分，星期二RR如果時間片太小，以至于大多數進程都不可能在一個時間片內運行完畢，切換就會頻繁，系統開銷顯著增大，所以，從系統效率來看，時間片取大一點好。如果時間片較大，那么，隨著就緒隊列里進程數目的增加，輪轉一次的總時間增大，亦即對每個進程的響應速度放慢了。 所以，時間片大小的確定要從進程個數，切換開銷，系統效率和響應時間等多方面考慮。第92頁，共102頁，2022年，5月20日，13點7分，星期二 例題：假如5個就緒進程其到達系統