第二章 系統程序同步學習
說明:
程序同步機制的任務:是對多個相關程序在執行次序上進行協調,使并發執行的諸程序之間能夠按照一定的規則或者時序共享系統資源。使程式的執行有可再現性。
一、程序同步的基本概念
1.1程序之間的制約關系:
1.間接互相制約關系
程序之間通過對系統臨界資源的競争導緻其互相制約,是以多個程序需要互斥通路系統資源。
2.直接互相制約關系
在應用程式中,為了完成某個任務而建立的多個程序之間的互相合作,在該程式下的共享臨界資源被該應用程式建立的程序中使用,這些程序将會産生直接的互相制約關系。
1.2臨界資源:
系統中可以被共享的資源,在系統調用中,每個程序通路臨界資源的代碼段稱為“臨界區”。對臨界資源的通路應該先檢查該資源是否被占用,如果被占用的話繼續等待,否則進入臨界區,執行代碼。
可以用一個while循環描述循環程序對臨界資源的通路:
whil(TRUE){
進入區
臨界區
退出區
剩餘區
}
比如著名的“生産者---消費者問題”。在協調程序之間共享資源的問題上應該有一定的規則,實作程序互斥地進入自己的臨界區
同步機制應該遵循的規則:
1.空閑讓進:當無程序處于臨界區,表明臨界資源處于空閑狀态,可以允許一個請求進入臨界區的程序立即進入自己的臨界區,有效地利用臨界資源。。
2.忙則等待:當已有程序進入臨界區時,其他試圖進入臨界區的程序必須等待,保證對臨界資源的互斥通路。
3.有限等待:對要求通路臨界資源的程序,應該保證在有限時間内能進入自己的臨界區,避免陷入“死等”狀态。
4.讓權等待:當程序不能進入自己的臨界區時,應該立即釋放處理機,避免陷入“忙等”狀态。
1.2硬體同步機制
使用一些特殊的指令對臨界區進行控制。相當于上鎖,和開鎖。
1.利用關中斷實作互斥。
1.優點
程序在臨界區執行期間,計算機系統不響應中斷,因而不會引發排程,也就不會發生程序或者線程切換。保證了對鎖的測試和關鎖操作的連續性和完整性,
2.缺點:
1濫用關中斷權利可能引發嚴重後果。
2關中斷時間過長,會影響系統效率,限制了處理器交叉執行的能力。
3這種方法不适用于多CPU系統。
2.利用Test-and-Set指令實作互斥
利用硬體指令:測試并建立TS實作互斥。
3.利用swap指令實作程序互斥,也叫對換指令
1.3信号量機制
适用信号量機制控制程序對系統資源的通路
信号量機制有三種:
1.整型信号量機制
2.記錄型信号量機制
3.信号量集機制
整型信号量
1.使用一個整數表示空閑資源總數(也叫資源信号量)
2.如果是非負值表示目前的空閑資源數
3.為負值其絕對值表示目前等待臨界區的程序數
4.初值大于0
兩個原子操作:
Wait(s),signal(s),也可以用P (s),V(s)操作表示。
記錄型信号量
1.整型信号量中的wait操作可能會使程序處在忙等的狀态,是以使用記錄型信号量實作“讓權等待”的原則。還應該增加一個程序連結清單指針list,用于連結上述的所有等待程序。
AND型信号量機制
解決多個程序需要共享多個系統資源的情況,其基本原理是:
将程序在整個運作過程中所需的全部資源,一次性地配置設定給程序,等程序使用完畢後再一起釋放,隻要有一個資源未能配置設定給程序,其他有可能為之配置設定的資源也不會配置設定。
注意:使用信号量機制實作程序互斥wait(mutext)和signal(mutext)必須成對出現
缺少wait(mutext):将會導緻系統混亂,不能保證對臨界資源的互斥通路。
缺少signal(mutext):将會使臨界資源永遠不會釋放,進而使等待該資源的程序不能被喚醒。
1.4 管程機制介紹
背景提出:信号量機制在通路臨界資源的程序中都必須自己同步wait(s),和signal(s),這使大量的同步操作分散在各個程序中,給系統管理帶來麻煩,而且會因為同步操作使用不當導緻系統死鎖。是以管程是一種新的程序同步工具
定義:代表共享資源的資料結構以及由于對該共享資料結構實施操作的一組過程所組成的資源管理程式共同構成了系統的資源管理子產品,稱之為管程。
Hansan的定義:一個管程定義了一個資料結構和能為并發程序所執行(在該資料結構上)的一組操作,這組操作能同步程序和改變管程中的資料。
是以我們可以知道管程由四個部分構成:
1.管程的名稱
2.局部于管程中的共享資料結構說明
3.對該資料結構進行操作的一組過程。
4.對局部于管程中的共享資料設定初始值的語句。
說明:1.管程被請求和釋放資源的程序所調用。
2.管程包含了面向對象的思想,将表征共享資源的資料結構及其對資料結構操作的一組過程,包括同步機制,都集中并封裝在一個對象内部,隐藏了實作細節,封裝于管程内部的資料結構僅能被封裝于管程内部的過程所通路。
3相反的,封裝于管程内部的過程也僅能通路管程内部的資料結構,所有程序要通路臨界資源時,都隻能通過管程間接通路,而管程每次隻準許一個程序進入管程,執行管程内的過程,實作了程序的互斥。
管程的特性:
1.子產品化:即管程是一個基本程式機關,可以單獨編譯。
2.抽象資料類型;指管程中不僅有資料,而且有對資料的操作。
3.資訊掩蔽:指管程中的資料結構隻能被管程中的過程通路,這些過程也是在管程内部定義的,供管程外的程序調用。
1.5管程與程序的比較
管程 | 程序 | |
定義資料結構 | 公共資料類型(如消息隊列) | 私有資料結構PCB |
操作資料結構 | 由順序程式執行有關操作 | 進行同步操作和初始化操作 |
設定目的 | 實作系統的并發性 | 解決共享資源的互斥使用問題 |
工作方式 | 被動(被程序調用) | 主動方式 |
并發性 | 不能并發執行 | 可以并發執行 |
動态性 | 是作業系統中的一個資源管理子產品,供程序調用 | 建立--->消亡,具有動态性 |
二、程序之間的通信
說明:程序之間需要傳送大量的資料,而前面講述的程序的互斥與同步都必須由程式員實作,非常不友善。
是以發展出了幾種進階的程序通信機制。
2.1共享存儲器系統
兩種類型:基于共享資料結構的方式和基于共享存儲區的方式
2.2管道通信系統
讀程序和寫程序之間的通信。是以需要提供三個方面的協調能力:
1.互斥(管道在某個時刻隻能被一個程序擁有)
2.同步(該程序釋放管道資源後,另外一個程序能夠知道)
3.确定對方是否存在。
2.3消息傳遞系統
1.根據實作方式不同可以分為兩類:
1.直接通信方式:發送程序利用OS所提供的發送原語,直接把消息發送目标程序。
2.間接通信方式:是指發送和接受程序,都通過共享中間實體(稱為郵箱)的方式進行消息的接受和傳遞。
2.4客戶機---伺服器系統
1套接字(socket)
2.遠端過程調用和遠端方法調用(RPC)
三、作業系統中的線程
1.在作業系統中引入線程是為了使OS有更好的并發性,減少程式在并發執行時所付出的時空開銷。
2.程序的兩個屬性:
1.程序是一個可擁有資源的獨立機關。
2.可獨立排程和分派的基本機關。
3.線程是作為排程和分派的基本機關。
4.線程與程序之間的比較
程序 | 線程 | |
排程的基本機關 | 傳統OS中程序是作為獨立排程和分派的基本機關 | 引入線程的OS中,線程作為排程和分派的基本機關 |
并發性 | 都有 | |
擁有資源 | 擁有系統配置設定的資源 | 沒有系統資源,但是可以共享所屬程序的資源 |
獨立性 | 獨立性較高 | 獨立性較低 |
系統開銷 | 程序的活動中系統開銷較大 | 開銷較低 |
支援多處理機系統 | 分為單線程程序和多線程程序 | 多處理機OS引入了多線程 |
5.線程運作時的三種狀态:
1.執行狀态:線程已經獲得處理機正在運作。
2.就緒狀态:線程隻等待CPU即可執行
3.阻塞狀态:線程因為某些事件而受到阻礙處于暫停狀态。
線程之間的狀态轉換和程序之間的狀态轉換是一樣的。
6.線程控制塊TCB
系統為每個線程配置了一個線程控制塊TCB,将所有用于控制和管理線程的資訊記錄線上程控制塊中
包括:
1.線程标示符--->線程的名字(唯一)
2.一組寄存器(包括程式計數器PC,狀态寄存器,通用寄存器的内容)
3.線程的運作狀态
4.優先級
5.線程專有存儲區:線程切換的現場保護和與該線程相關的資訊。
6.信号屏蔽:對某些信号屏蔽。
7.堆棧指針:線程中用于儲存局部變量和傳回位址的堆棧。