文章目錄
- 作業系統
-
- c2 程序管理
-
- 2.1程序與線程
- 2.2處理機排程
- 2.3程序同步
- 2.4死鎖
作業系統
c2 程序管理
2.1程序與線程
程序概念與特征
程序：便更好的描述和控制程式的并發執行，實作作業系統的并發性與共享性。
PCB：程序控制塊，描述程序的基本情況預計運作狀态，進而控制和管理程序。
程式段，相關資料段和PCB三部分構成了程序映像（實體）。
建立程序：建立程序中的PCB，撤銷程序：撤銷PCB
程序映像是靜态的，程序是動态的
程序是程序實體的運作過程，是系統進行資源配置設定的一個獨立機關。
特征：動态性，并發性，獨立性，異步性，結構性
程序的狀态與切換
運作态，就緒态，阻塞态，建立态，結束态
程序控制：把程序控制用的程式段稱為原語
程序建立：配置設定唯一程序辨別号–>申請空白PCB，申請成功則程序建立成功
程序終止：正常結束，異常結束，外界幹擾；資源釋放，子程序撤銷，從PCB隊列中删除
程序阻塞：等待某種操作，由系統自動執行阻塞（Block）原語，變為阻塞态；
隻有處于運作态的程序才能變成阻塞态
程序喚醒：阻塞程序所期待的時間發生了，将阻塞态程序切換為就緒态，喚醒原語（Wakeup）；
程序切換：處理機從一個程序轉到另一個程序運作；利用系統調用進入核心，再由核心中的相應處理程式完成。
排程：決策行為，如排程算法；切換：執行行為。先有資源的排程，然後才有程序的切換。
程序的組織：PCB，程式段，資料段
PCB：程序描述資訊，程序控制和管理資訊，資源配置設定清單，處理機相關資訊
程式段：能被程序排程程式調到CPU執行的代碼段；程式可被多個程序共享。
資料段：原始資料或者加工後的資料
程序的通信
PV操作是低級通信方式，進階通信方式，以較高的效率傳輸大量資料
共享存儲：A與B中間有一箱子，AB通信通過箱子進行，A将資訊放入箱子，B從箱子取走。
直接消息傳遞：A直接将消息送到B手中
間接消息傳遞：A将消息放到B的郵箱中，B從郵箱取出
管道通信
固定大小的緩沖區，讀程序可能比寫程序快；
半雙工通信，不能兩端同時進行，寫滿通知都程序讀；
讀資料是一次性操作，一旦被讀取就抛棄。
實作父子程序互動通信，需要定義兩個管道。
線程
線程：基本的CPU執行單元，程式執行流的最小單元，線程ID，PC，寄存器以及堆棧組成。
是程序的一個實體，被系統獨立排程和分派的基本機關，線程隻擁有一部分必不可少的資源，共享程序的全部資源。同一程序的多個線程可以并發執行。就緒。阻塞。運作三種狀态。
比較：程序是擁有資源的最基本機關，線程是獨立排程的基本機關。
同一程序，線程切換不會導緻程序切換。
線程實作方式：使用者級線程，核心級線程
使用者級線程，線程管理相關操作都由應用程式完成，核心意識不到線程存在
核心級線程：線程管理由核心完成，應用程式沒有線程管理代碼，隻有一個程式設計接口
多線程模型：同時支援使用者線程和核心線程
多對一模型：多個使用者級線程映射道一個核心線程
一對一模型：每個使用者線程映射到一個核心線程
多對多模型：n------m，m<=n
2.2處理機排程
排程的概念
處理機排程是按照一定的算法，就緒隊列中選擇一個程序配置設定處理機給它，實作程序的并發執行
排程的層次
作業排程：進階排程，記憶體和輔存之間的排程，每個作業隻調入一次，調出一次，多道批處理系統， 執行頻率低。
中級排程：記憶體排程，提高記憶體使用率和系統吞吐量，挂起，當具備運作條件時，重新調入記憶體，并 修改為就緒态。
程序排程：低級排程，從就緒隊列中選取一個程序，将處理機配置設定給它。作業系統的最基本排程，
頻率很高。
三級排程的關系
作業排程為程序活動做準備，程序排程使程序正常活動起來，中級排程将暫時不能運作的程序挂起
作業排程次數少，程序排程頻率高
程序排程最基本的，不可或缺
排程的時機切換與過程
不能進行排程和切換的情況：進行中斷過程中，程序在核心程式臨界區中，原子操作時
程序排程的方式
非剝奪與剝奪排程方式
排程的基本原則
CPU使用率，系統吞吐量，周轉時間，等待時間，響應時間
周轉時間=作業完成時間-作業送出時間
平均周轉時間
帶權周轉時間=作業周轉時間/作業實際運作時間
平均帶權周轉時間
典型的排程算法
先來先服務（FCFS）//對長作業有利，有利于CPU繁忙型作業，不利于IO型作業
**短作業優先（SJF）**排程算法 //對長作業不利，平均等待時間，周轉時間最少
優先級排程算法：非剝奪/剝奪式程序排程算法，靜态優先級，動态優先級
優先級：系統程序>使用者程序，互動型程序>非互動型程序，IO型程序>計算型程序
高響應比優先級排程算法：
等待時間相同時，有利于短作業，要求服務時間相同時，等待時間越長，響應比越高
對于長作業，随等待時間增加而提高，克服了饑餓狀态，兼顧了長作業
時間片輪轉排程算法：适用于分時系統。時間片足夠大=先來先服務，時間片很小，頻繁切換，開銷 增大。
多組回報隊列排程算法：融合了前幾種的優點，動态調整程序優先級和時間片大小
設定多個就緒隊列，賦予不同優先級，各隊列時間片帶下不同，逐級遞增
新程序進入記憶體，先到第一隊列的末尾(FCFS)，若一個時間片内沒完成，
則放到第二隊列…,當第一隊列為空時，才運作第二隊列…,可被剝奪！
優勢：短作業優點，周轉時間短，長作業不會長期得不到執行。
2.3程序同步
程序同步基本概念
多道程式環境下，程序是并發執行的，不同程序之間存在着互相制約關系。為了協調這種制約關系
臨界資源：對臨界資源的使用必須互斥進行，通路臨界資源的那段代碼稱為臨界區。
進入區：進入區檢查是否可以進入臨界區，設定通路标志
臨界區：通路臨界資源的那段代碼，臨界端
退出區：将正在通路臨界區的标志清除
剩餘區：代碼中剩餘部分
同步：直接制約關系，協調工作次序發送等待，傳遞資訊等，源于程序的互相合作
互斥：間接制約關系，通過臨界資源進行制約
空閑讓進，忙則等待，有限等待，讓權等待
臨界區實作互斥的基本方法
軟體實作：單标志法，設定一個通路辨別
雙标志法先檢查，檢查對方标志，再置自己标志
雙标志法後檢查，先置自己标志，在檢查對方标志
Peterson’s Algorithm，防止兩個程序進入臨界區無限等待
硬體實作方式：中斷屏蔽方法， 硬體指令方法
信号量
信号量機制用來解決互斥與同步問題，隻能被兩個标準的原語wait(S),signal(S)通路，也記為PV操作
整型信号量，資源數目的整型量S
記錄型信号量，不存在忙等的程序同步機制，資源數目＋程序連結清單
分析進行同步和互斥問題的方法步驟
關系分析：找出問題中的程序數，分析同步互斥關系
整理思路：找出關鍵點，寫出PV操作的大緻順序
設定信号量：設定初值，完善整理
管程
管程，抽象為資料結構，包括管程名稱，内部共享資料結構的說明，一組操作過程，設定初始值語句
管程把對共享資源的操作封裝起來，每次隻允許一個程序進入管程
條件變量，阻塞的原因，每個條件變量儲存了一個等待隊列
經典同步問題
生産者-消費者問題，讀者-寫者問題，哲學家程序問題，吸煙者問題
2.4死鎖
死鎖：多個程序因競争資源而造成的一種僵局，互相等待，若無外力作用，這些程序都無法進行
死鎖産生的原因
系統資源的競争，程序推進順序非法
死鎖産生的必要條件：互斥，不剝奪，請求并保持，循環等待，産生死鎖必須四個條件都滿足
死鎖的處理政策
死鎖預防：破壞四個必要條件之一
避免死鎖：動态配置設定過程，用某種方法阻止系統進入不安全狀态
銀行家算法：最大需求矩陣，配置設定矩陣，需求矩陣，
死鎖檢測與解除：不采取任何限制性措施
資源配置設定圖，（檢測是否發生死鎖）進入資源的有向邊分為請求邊，資源到程序的有向邊為配置設定邊
死鎖定理，找出一條有向邊與它相連，且對應資源的申請數量小于系統中空閑資源數量，消去它，如此循環，一直簡化，若不能完全簡化，則發生死鎖。