會計學1操作系統處理機管理處理機管理處理機管理主要介紹操作系統對于CPU的管理，分為作業管理和進程管理兩部分。第1頁/共76頁作業步完成整個作業的執行，往往要分為若干個步驟，每個步驟稱之為一個“作業步”。作業步的劃分通常以數據依賴關系來確定，即上一步驟的輸出結果是下一步驟執行所需要的輸入數據。例如：一個C語言程序的執行可分為編譯—>連接—>運行三個步驟。編譯步驟將源程序編譯成.obj的中間代碼；連接步驟將中間代碼轉化為可執行代碼，執行步驟運行可執行代碼。第2頁/共76頁作業管理操作系統將用戶提交的作業輸入到輔助存儲器，并按照一定的調度策略，選擇合適的作業進入內存執行，直至完成的管理過程。作業管理貫穿整個作業的生命周期。第3頁/共76頁作業狀態（P31）

提交狀態——作業及說明書提交給系統管理員，等待輸入輔助存儲器；后備狀態——作業被輸入到輔助存儲器中，等待調度程序挑選進入內存；運行狀態——作業被調度程序選中，加載進入內存執行；完成狀態——作業執行完畢，系統回收所有資源。第4頁/共76頁作業狀態轉化圖作業輔存主機結束用戶把作業提交給系統操作人員操作人員把作業輸入到輔助存儲器操作系統把作業加載進入內存作業執行完畢，系統回收資源提交后備運行完成作業狀態：第5頁/共76頁后備作業和作業控制塊被接納到輔助存儲器的作業，在沒有投入運行之前，被稱為后備作業。系統在接納后備作業的時候，會為其建立一個作業控制塊（JobControlBlock）。所有后備作業的JBC形成一個后備作業隊列。作業控制塊（JCB）包括了作業說明書的主要內容，也包括一些作業狀態等信息。（P31圖2-18）第6頁/共76頁作業執行的兩種調度系統執行作業通常分為兩個階段：1、系統從輔存中選擇合適的作業進入內存，屬于作業調度。2、系統對已經在內存中的作業分配處理機，屬于進程調度。第7頁/共76頁作業調度

操作系統按照一定的策略，將“后備狀態”的作業調入內存中準備執行的行為，稱之為作業調度。從作業位置變化角度看，作業調度是把要執行的作業從輔助存儲器調入內存的行為。第8頁/共76頁作業調度的原則公平對待后備隊列中的每一個作業進入內存的作業能均衡地使用資源力爭在單位時間內為更多的作業服務，提高吞吐能力第9頁/共76頁作業平均周轉時間

假設第i個作業進入后備狀態的時刻為Si,執行完畢的時刻為Wi，則該作業周轉的時間為：Ti=Wi-Si

在系統中如果有n個作業，則平均周轉時間為：T=∑(Ti)/n

平均周轉時間值越小，表示作業平均等待的時間越短。第10頁/共76頁經典的作業調度算法FCFS——先來先服務（FirstComeFirstServed

）SJF——短作業優先(SortestJobFirst)HRRF——最高相應比優先(HighestResponseRatioFirst)第11頁/共76頁FCFS按照作業進入后備隊列的先后次序作為運行的先后次序。這與我們排隊處理各種事情的理念是一樣的。在一般情況下，在后備隊列等待時間最長的將被調度進入內存運行。但是如果此時該作業所需的資源無法獲得滿足，將會被推遲選中。

第12頁/共76頁例題1有三個作業，分別于第0秒、第1.5秒、第2.5秒分別進入后備隊列，他們所需CPU時間分別為：2秒、6秒、30秒，按照FCFS調度算法，計算這三個作業的平均周轉時間。第13頁/共76頁例題1平均周轉時間T1=2秒T2=0.5+6=6.5秒（從1.5—2秒等待作業A完成)T3=5.5+30=35.5秒(從2.5—8秒等待作業B完成)則：T=(T1+T2+T3)/3=(2+6.5+35.5)/3=15(秒)第14頁/共76頁例題2有三個作業，分別于第0秒、第1.5秒、第2.5秒分別進入后備隊列，他們所需CPU時間分別為：30秒、6秒、2秒，按照FCFS調度算法，計算這三個作業的平均周轉時間。第15頁/共76頁例題2平均周轉時間T1=30秒T2=28.5+6=34.5秒（從1.5—30秒等待作業A完成)T3=33.5+2=35.5秒(從2.5—36秒等待作業A和B完成)則：T=(T1+T2+T3)/3=(30+34.5+35.5)/3=33.33(秒)第16頁/共76頁結果比較比較上面兩個例子可以得出：在大作業先行到達后備時，使用FCFS調度策略，可能導致系統作業的平均周轉時間較長，也就是說如果小作業到達略微遲一點點，就可能要等待很長時間。如果只要執行一分鐘的作業需要等待10小時，是一件令人痛苦的事。第17頁/共76頁SJF——短作業優先

將CPU占用時間短的作業放在優先運行的位置上，可以提高系統的周轉率，這就是SJF調度策略。SJF調度策略不考率作業進入后備的時間順序，只考慮作業對CPU的時間需求。第18頁/共76頁SJF調度策略的例子有A、B、C三個作業分別在第0、7、10秒進入后備，申請CPU時間為20秒、40秒、10秒，假如系統在第10秒后開始作業調度，按照SJF調度策略，不考慮進入后備的順序，只考慮后備作業對CPU時間的需求量，調入運行順序為C->A->B。第19頁/共76頁SJF算法的缺點但如果在系統運行過程中，仍不斷有短作業進入后備，則長作業前面就不斷有“插隊”的，在極端情況下造成長作業永遠得不到運行，這對長作業是不公平的。因此希望有一種算法能兼顧作業申請CPU時間和在輔存中已等待時間這兩方面的因素。第20頁/共76頁HRRF——最高相應比優先

最高相應比優先

(HighestResponse_ratioFirst)將作業在后備區已經等待的時間與該作業申請需要的處理器時間相除，得出一個稱之為“響應比”系數：

響應比=已等待時間／申請CPU時間如果一個作業的響應比大，要么該作業需要的時間短，要么該作業已經在后備區等待了足夠長的時間。第21頁/共76頁例題（P33例2-5）有5個作業到達后備時間如下表：作業到達時間所需CPU時間110.1(0)0.7210.3(0.2)0.5310.5(0.4)0.4410.6(0.5)0.4510.7(0.6)0.2第22頁/共76頁FCFS調入順序1、2、3、4、55432100.20.40.60.71.21.622.20.5t1=0.7t2=0.7+0.5-0.2=1t3=0.7+0.5+0.4-0.4=1.2t4=0.7+0.5+0.4+0.4-0.5=1.5t5=0.7+0.5+0.4+0.4+0.2-0.6=1.6T=(0.7+1+1.2+1.5+1.6)/5=1.2第23頁/共76頁SJF調入順序1、5、3、4、20.50.70.91.31.72.2t1=0.7t5=0.7+0.2-0.6=0.3t3=0.7+0.2+0.4-0.4=0.9t4=0.7+0.2+0.4+0.4-0.5=1.2t2=0.7+0.2+0.4+0.4+0.5-0.2=20243510.20.40.6T=(0.7+0.3+0.9+1.2+2)/5=1.02第24頁/共76頁HRRF調入順序1、2、5、3、40.50.71.21.41.82.2t1=0.7R2=1t2=0.7+0.5-0.2=1R5=3t5=0.7+0.5+0.2-0.6=0.8R3=2t3=0.7+0.5+0.2+0.4-0.4=1.4R4=3.25t4=0.7+0.5+0.2+0.4+0.4-0.5=1.70435210.20.40.6T=(0.7+1+0.8+1.4+1.7)/5=1.12第25頁/共76頁環境對調度的影響P33例2-6，只要內存許可就調入作業，并采用FCFS調度算法：作業到達時間所需CPU時間所需內存量110.10.715K210.30.570K310.50.450K410.60.420K510.70.210k調入順序為：1、2、5、4、3第26頁/共76頁前臺后臺你排隊去買火車票，假如買一張票，需要花費10秒鐘，如果在你前面的某個人要買500張票，你以及在后面排隊的人將會感覺很糟糕。售票員把這個單子接下來，并請他明天來取，然后繼續為后面買零票的顧客服務。只在窗口沒有人排隊的空閑時間里，售票員才來處理500張票的單子。第27頁/共76頁人們為解決各種不同的問題，編寫各種不同的程序，有的計算量大，有的計算量小；有的需要經常性信息交互，有的不需要信息交互。在分時操作系統中把那些運行時間短、交互頻繁的作業，賦予較高的運行級別，優先保證其CPU時間片，稱為前臺作業。把計算量大而且基本沒有交互會話的作業，放在較低的運行級別上，只是在沒有前臺作業運行或沒有交互請求時，才去運行它們，稱之為后臺作業。

前臺作業和后臺作業

第28頁/共76頁課后練習討論：有時貌似公平的解決方案，也有不合理的地方，因此沒有絕對的公平合理。今天所學的三個調度算法就是一個例證。結合自己在平時生活中見到或親身經歷的情況，談談想法。復習：教材P32—P37的內容。作業：有A、B、C、D四個作業，分別于0秒、2秒、2.5秒、6秒進入系統后備隊列，他們分別申請CPU時間8秒、4秒、20秒、5秒。請參照教材的做法，分別給出在FCFS、SJF、HRRF調度算法下的作業周轉時間表和平均周轉時間。第29頁/共76頁程序的概念

程序是人們為了讓計算機完成某項任務，按照執行時間順序而編寫的指令序列。

第30頁/共76頁程序的特點連續執行——人們在編寫時都假設，自己的程序將一次執行完畢。獨占資源——人們在編寫時都假設，自己的程序將無條件享有所需要的各種資源。過程再現——人們在編寫時都假設，當程序重復運行時，每一時刻的狀態和結果都能夠重復再現。第31頁/共76頁單道程序執行執行的連續性——程序一次執行完畢，不被打斷。資源的獨占性——程序獨自享有所需要的各種資源。結果的再現性——程序重復運行時，每一時刻的狀態和結果都將能夠再現。第32頁/共76頁多道程序執行在多道程序并發執行的情況下，程序的上述三個特點都不存在了，相反呈現出下面的特征：程序執行是斷斷續續的；程序與其它程序共享資源；程序的執行過程不可再現。第33頁/共76頁１、程序執行的不連續性輸入輸出執行等待CPU321單道程序執行：321多道程序執行（以分時系統為例）：第34頁/共76頁2、與其它程序共享資源從上例可以看出，多道程序在執行時，一個程序要與其它程序共享CPU資源，實際上，在多道程序運行時，包括內存、外部設備在內的各種資源都需要共享（競爭），在后面的內存管理和設備管理章節中會有更詳細的闡述。第35頁/共76頁3、程序執行過程不可再現例如一輛汽車從事從A地到B地貨物運輸，雖然每次運輸時車型、運輸的物品、行駛的線路都相同，但由于各種交通因素的影響（其它車輛干擾、交通信號控制），每次行駛過程都與以前不同，是獨一無二的、不可再現的。同樣，一個程序的執行過程受到在內存中的其他程序的影響和制約。如果把該程序再次投入運行，盡管自身的代碼、數據、需求都沒有變化，但由于內存中其它程序數量及狀態的變化，影響該程序的執行過程，相對應的每個時刻的狀態而言，本次執行過程有別于過去任何一次執行過程，而且是不可再現的。第36頁/共76頁多道程序運行的特點執行的并發性——從宏觀上看，內存中有多個程序同時執行。相互的制約性——一個程序占用的資源，會影響到其他程序的運行。狀態的多變性——程序時而運行，時而停止等待，走走停停。第37頁/共76頁進程概念的引入為了更準確地表述在多道程序環境中程序運行的特點，就引入了進程（Process）的概念。通俗地講，進程就是進行中的程序。第38頁/共76頁進程的定義（P15)“進程”是指一個程序在給定數據集上的一次執行過程，是操作系統進行資源分配和運行調度的獨立單位第39頁/共76頁進程和程序的關系（1）相對于程序而言，“進程”是對程序運行的動態描述。教材中把程序比喻成電影拷貝，把進程比作一次放映過程（P15），從一個方面說明了程序和進程之間的關系：即進程是計算機程序的實際執行過程。第40頁/共76頁進程和程序的關系（2）我們還可以這樣理解：從事從A地到B地貨物運輸，我們要制定一個運輸計劃，如用什么車輛、什么時候裝貨、什么時候出發、行駛線路、行駛速度等等，這個計劃就是程序，而每一次的實際運輸過程就是一個進程。當一次運輸結束時，這個進程的生命周期就結束了。第41頁/共76頁進程和程序的區別（1）程序是靜態的——程序是命令代碼的集合，存在于紙上或輔助存儲器中（沒進入內存）。進程是動態的——進程存在于內存中，并且正在某個特定的數據集合上運行。第42頁/共76頁進程和程序的區別（2）程序不會實際獲得資源——雖然程序中表明了對資源的需求，但由于尚未被加載執行，操作系統不會為程序分配資源。進程能實際獲得資源——操作系統向每個進程分配資源，包括需要的CPU時間、內存、外部設備等。如果多個用戶同時執行同一個程序，則該程序將會發起多個獨立的進程，操作系統將為每個進程分別分配所需資源。第43頁/共76頁進程的特征進程是動態的（在執行中）進程有生命周期（程序沒有）進程具有并發性（同時進行）進程會相互制約（互相影響）多個進程可以由同一個程序發起舉例：在任務管理器的進程列表中查看不同用戶同時執行PowerPoint程的進程。第44頁/共76頁進程的分類用戶進程——由用戶的應用程序發起的進程系統進程——由操作系統發起的進程（如調度、資源分配和回收）Windows中，由操作系統發起的系統進程，用戶名為System，由用戶發起的進程則使用該用戶的名稱。第45頁/共76頁進程的基本狀態運行狀態——進程獲得CPU時間，正在運行著。阻塞狀態——如果運行狀態的進程因某種事件（如等待I/O操作完成）而暫時停止運行，進程就變成阻塞狀態，也稱“等待狀態”。就緒狀態——進程已經具備運行條件（如I/O操作已經完成，可以進一步往下執行），但此時CPU正被別的進程占用，此時的進程就處于就緒狀態。第46頁/共76頁進程狀態轉換運行→阻塞：處于運行中的進程，由于某種原因（等待I/O操作結束或等待某些信號），導致該進程無法繼續運行，則變為阻塞狀態，并根據阻塞原因安排到相應的隊列中。運行→就緒：運行中的進程，由于此次分配給它的時間片用完，則被轉變成就緒狀態，安排在就緒隊列中。阻塞→就緒：當引起一個進程阻塞的原因被解決，該進程滿足可以繼續運行的條件，則被轉變成就緒狀態，安排在就緒隊列中。第47頁/共76頁運行就緒阻塞獲得CPU時間時間片用完等待的事件已發生，可以繼續運行需要等待某個事件發生進程狀態轉換示例圖第48頁/共76頁課后作業進程是什么，進程和程序有哪些不同？闡述進程基本狀態及其相互轉化條件，畫出進程狀態轉化圖。處于阻塞狀態的進程能不能轉化成運行狀態，為什么？處于就緒狀態的進程能不能轉化成阻塞狀態，為什么？第49頁/共76頁寄存器寄存器是中央處理器的組成部分,擁有非常高的讀寫速度，是CPU內部高速存貯部件，用來暫存指令、數據、地址。常用的寄存器包含有程序計數器(PC)、指令寄存器(IR)，地址寄存器、通用寄存器等。第50頁/共76頁高速緩存—Cache高速緩存（cache）是集成在CPU中的特殊的存儲器子系統，其中復制了頻繁使用的數據，以利于CPU快速訪問。當處理器引用內存中的某地址時，高速緩沖存儲器首先檢查是否存有該地址。如果存有該地址，則將相應保存的數據放入處理器；如果沒有保存該地址，則進行常規的存儲器訪問。因為訪問高速緩存比訪問內存速度快，所以當訪問高速緩存“命中率”高，可以提高系統處理速度。

第51頁/共76頁隊列在操作系統中所講的隊列，一般是隊列鏈表，通常有單鏈和雙鏈形式。

第52頁/共76頁堆棧

堆棧具有先進后出的處理特點，在程序調用、中斷處理過程的開始和結束，經常會使用堆棧來保存和恢復返回地址。第53頁/共76頁中斷技術進程在執行過程中，如果時間片用完就應立即停止下來。但用戶進程并沒有配備計時功能，如何就能知道到時間片到了，如何就能停下來呢？這里用到的就是“中斷”技術。中斷技術是硬件和軟件配合，用來打斷當前正在執行的進程，轉而處理特定事務的技術。是計算機中非常重要的技術。第54頁/共76頁“中斷”在生活中的事例你正在做數學作業，忽然聽到敲門聲，有人給你送快件，于是你放下手頭的作業，轉去處理接收事宜，然后回來繼續從被打斷的地方做下去。第55頁/共76頁中斷的概念系統暫時停止正在運行的進程，強制轉去處理發生的事件，處理完畢后，再返回原進程執行的過程。處理發生事件的程序是事先設計好的，一般稱為“中斷服務程序”中斷服務進程與被中斷的進程是相互獨立的，不需要相互傳遞數據。第56頁/共76頁中斷處理過程

中斷請求——由中斷發起方（中斷源）向系統發出請求中斷信號（IRQ）；斷點保護——將被中斷進程的指令計數器、狀態字寄存器等放入系統堆棧；中斷服務——確定中斷源，并轉向執行相應的中斷服務程序；恢復現場——將被中斷進程的指令計數器、狀態字寄存器等內容恢復；繼續執行——從斷點處開始繼續執行原來的程序。第57頁/共76頁中斷的優先級根據中斷服務的重要性，將各種中斷賦予不同的級別，在同時有兩個或兩個以上中斷請求時，只響應級別最高的，而其它低級別的中斷請求或等待或撤銷。第58頁/共76頁中斷嵌套在處理一個中斷服務的過程中，如果發生了級別更高的中斷請求，當前中斷服務進程也被中斷，CPU去執行更高級別的中斷服務，這就是中斷嵌套。第59頁/共76頁中斷屏蔽對于不允許中斷的進程（或進程片段），可以通過屏蔽指令對相關設備進行相應的設置，阻斷中斷請求鏈路，阻塞中斷請求信號，以達到不響應中斷的目的。例如下面介紹的“原語”，就是利用屏蔽的手段，以達到不被中斷的目的。第60頁/共76頁原語原語一般指最基本的不可分割的程序，這個程序一旦被啟動，就必須執行完，不能夠被中斷。通常在這個程序的開始處設置中斷屏蔽指令（關中斷），在末尾處設置撤銷屏蔽指令（開中斷）。第61頁/共76頁進程控制塊PCB（ProcessControlBlock）進程的執行是斷斷續續的，狀態也在不斷地發生變化，系統為了隨時掌握情況進程的變化，設置了一個隨時記載其狀態的信息載體——進程控制塊。每個程序從加載進入內存時，系統就為它創建了一個進程控制塊。

第62頁/共76頁進程控制塊的內容（P18）標識信息——記載進程名稱等；狀態信息——記載進程的狀態（運行/就緒/阻塞）、程序及數據在內存中的位置等；現場信息——記載進程被迫放棄CPU時，各種寄存器內容等，以便在重新獲得CPU時能恢復現場，繼續運行。管理信息——進程的優先級、隊列指針等。第63頁/共76頁進程控制塊隊列（P20圖2-6）

運行隊列——每個時刻只可能有一個進程處于運行狀態，故運行隊列中最多只有一個PCB

。就緒隊列——符合運行條件進程，將其PCB按一定的策略排列,等待獲得CPU。阻塞隊列——進程根據被阻塞的原因的不同，分別排在不同的隊列中，因此阻塞隊列有多個。第64頁/共76頁進程調度算法所謂進程調度算法，就是在就緒隊列中選擇相應的進程投入運行的調度策略。第65頁/共76頁先來先服務方法——

誰最先到達就緒隊列，誰先得到CPU。優點——

算法簡單，調度效率高缺點——平均等待時間可能較長，不利于對CPU時間要求短和I/O工作頻繁的進程。第66頁/共76頁時間片輪轉方法——每個運行的進程輪流獲得一個固定長短的CPU時間片。優點——調度算法