文章目錄
- 作業系統
-
- 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死鎖
死鎖:多個程序因競争資源而造成的一種僵局,互相等待,若無外力作用,這些程序都無法進行
死鎖産生的原因
系統資源的競争,程序推進順序非法
死鎖産生的必要條件:互斥,不剝奪,請求并保持,循環等待,産生死鎖必須四個條件都滿足
死鎖的處理政策
死鎖預防:破壞四個必要條件之一
避免死鎖:動态配置設定過程,用某種方法阻止系統進入不安全狀态
銀行家算法:最大需求矩陣,配置設定矩陣,需求矩陣,
死鎖檢測與解除:不采取任何限制性措施
資源配置設定圖,(檢測是否發生死鎖)進入資源的有向邊分為請求邊,資源到程序的有向邊為配置設定邊
死鎖定理,找出一條有向邊與它相連,且對應資源的申請數量小于系統中空閑資源數量,消去它,如此循環,一直簡化,若不能完全簡化,則發生死鎖。