1. 進程的定義

? 在引入多道程序技術之后,為了方便對各個任務進行管理,引入了進程和進程實體的概念.

? 進程只是一種概念,是一個程序在處理機上運行是發(fā)生的所有活動(動態(tài)性).是系統(tǒng)進行資源分配的一個獨立單位.

? 而我們通常所講的進程是指進程實體.之前的進程是進程實體的運行過程.

? 每一個進程實體都有==其進程控制塊PCB,程序段==(所要執(zhí)行的程序代碼)和==數(shù)據(jù)段==(執(zhí)行任務需要的變量,運算數(shù)據(jù)).

(1). PCB

• 進程描述信息
  • 進程標識符PID
  • 用戶標識符UID
• 進程控制和管理信息
  • 進程當前狀態(tài)
  • 進程優(yōu)先級
• 資源分配清單
  • 程序段指針
  • 數(shù)據(jù)段指針
  • 分配的各種硬件資源
• 處理機相關信息
  • 各種寄存器的值

(2). 進程的組織

1). 鏈接方式

? 操作系統(tǒng)按照進程的狀態(tài)將PCB分為多個隊列,操作系統(tǒng)持有指向各個隊列的指針.

? 執(zhí)行指針,就緒隊列指針,阻塞隊列指針

2). 索引方式

? 根據(jù)進程狀態(tài)的不同,建立幾張索引表,操作系統(tǒng)持有指向各個索引表的指針.

? 索引表中的表項指向PCB

? 執(zhí)行指針,就緒表指針,阻塞表指針

(3). 進程的特性

• 動態(tài)性:進程是動態(tài)的產(chǎn)生,變化和消亡的,只是一次執(zhí)行過程.
• 并發(fā)性:內(nèi)存中有多個進行實體,可并發(fā)執(zhí)行
• 獨立性:進程是能獨立運行,獨立獲得資源,獨立接受調(diào)度的基本單位
• 異步性:各個進程之間的執(zhí)行不需要等待
• 結構性:每個進程的結構都是一致的,都是PCB+程序段+數(shù)據(jù)段

2. 進程狀態(tài)和轉換

(1). 進程的三種基本狀態(tài):

• 運行態(tài):當前得到CPU資源的進程(多核處理機可以同時有多個進程處于運行態(tài),被稱為并行運行)
• 就緒態(tài):得到了所需的所有資源,但是還沒有被分配CPU運行時間,所以沒有運行的進程
• 阻塞態(tài):在等待某一時間(分配資源,等待硬盤操作等等)而沒有運行的進程

(2). 另外兩種狀態(tài):

• 創(chuàng)建態(tài):進程剛剛被創(chuàng)建的狀態(tài)
• 終止態(tài):進程被撤銷時的狀態(tài)

(3). 狀態(tài)的轉換

1574566849150

? 進程在創(chuàng)建時是創(chuàng)建態(tài),一經(jīng)創(chuàng)建立即進入就緒態(tài).當就緒態(tài)的線程被分配到了CPU執(zhí)行時間時,進入運行態(tài),運行態(tài)的進程使用完被分配的時間或者CPU被強占后重新變成就緒態(tài).運行態(tài)的進程當使用==系統(tǒng)調(diào)用==申請系統(tǒng)資源或者等待某個事件發(fā)生時,進入阻塞態(tài),阻塞態(tài)的進程在得到資源或者響應的事件發(fā)生后會進入就緒態(tài)等待分配CPU運行時間.

3. 進程控制

? 進程控制就是實現(xiàn)進程狀態(tài)的轉換.

? 進程控制是通過PCB在就緒隊列和阻塞隊列中的出隊和入隊實現(xiàn)的.其中使用==原語保證進程控制的原子性==.而==原語則是采用關中斷和開中斷兩個指令實現(xiàn)的==.

進程控制相關的原語都做了3件事情:

• 更新PCB中的信息
  • 修改進程狀態(tài)標志
  • 保存運行環(huán)境或者從PCB恢復運行環(huán)境
• 將PCB插入到相應的狀態(tài)隊列
• 分配/回收資源

4. 進程通信

? 進程通信就是進程時間的信息交換.但進程之間的內(nèi)存空間是相互獨立的.進程間通信保證了進程間的安全通信.

(1). 共享存儲

? 操作系統(tǒng)為兩個進程分配一片可以共享訪問的內(nèi)存空間,兩個進程可以使用這個共享空間進行信息交換.

? 兩個進程對共享空間的訪問必須是互斥的.

1). 基于數(shù)據(jù)結構的共享

? 速度較慢,是一種低級的通信方式

2). 基于存儲區(qū)的共享

? 由兩個進程決定共享空間中的數(shù)據(jù)格式,相比之下這種方式速度更快,是一種更高級的通信方式.

(2). 管道通信

? 在兩個進程中開辟一個管道,用于信息的傳輸.

? 管道只能由一個進程填滿,再由一個進程全部取出.一個管道不能雙向通信.(半雙工)

? 各個進程對管道的訪問互斥.

(3). 消息傳遞

? 進程之間以格式化消息傳遞信息,進程使用==消息的發(fā)送和接收原語==進行數(shù)據(jù)交換

1). 直接通信方式

? 發(fā)送進程直接將消息掛到接收進程的消息緩沖隊列上

2). 間接通信方式

? 消息先發(fā)送到中間實體中,消息頭中包含了消息的接收進程等等信息.

? 接收進程會主動在中間實體中查閱信息.

5. 線程

(1). 線程的概念

? 線程是一個基本的CPU執(zhí)行單元,也是程序執(zhí)行流的最小單位.

? 線程間的并發(fā)不需要切換進程環(huán)境,系統(tǒng)開銷小.

線程的特性:

• 線程是處理機調(diào)度的單位
• 多核CPU可以同時運行不同的多個線程
• 線程有線程ID,線程控制塊TCB
• 線程也有就緒,阻塞,運行三態(tài)
• 線程不占有系統(tǒng)資源
• 同一個進程的線程共享進程的內(nèi)存空間

(2). 線程的實現(xiàn)方式

? 用戶級線程:由應用程序通過線程庫實現(xiàn).用戶級線程的線程切換可以再用戶態(tài)下完成,無需操作系統(tǒng)的干預.

? 內(nèi)核級線程:線程的管理工作由操作系統(tǒng)內(nèi)核完成,所以線程的切換都需要在核心態(tài)下完成.

(3). 多線程模型

• 多對一模型:一個進程的多個用戶級線程映射到一個內(nèi)核級線程
  • 優(yōu)點:用戶級線程的切換不需要CPU切換到核心態(tài)
  • 缺點:用戶級線程一旦被阻塞,整個進程都會被阻塞
• 一對一模型:每一個用戶級線程都對應一個內(nèi)核級線程
  • 優(yōu)點:一個線程被阻塞后,別的線程還可以繼續(xù)執(zhí)行,并發(fā)能力強
  • 缺點:管理成本高
• 多對多模型:n個用戶級線程映射到m和內(nèi)核級線程(n >= m)
  • 克服了多對一模型并發(fā)度不高的確定,也克服了一對一模型中進程管理開銷太大的缺點

6. 處理機調(diào)度

(1). 高級調(diào)度

? 也叫作業(yè)調(diào)度,將作業(yè)從外存(磁盤,硬盤,U盤等等)調(diào)入內(nèi)存(內(nèi)存條)中,顯示的應用于早起的批處理程序.

? 準確的講:高級調(diào)度按照一定原則從后備隊列的作業(yè)中挑選出一個,為它們分配內(nèi)存等必要資源,并建立響應的進程(建立PCB),并使它們獲得競爭處理機的權利.

? 作業(yè)調(diào)入時會建立相應的PCB,作業(yè)調(diào)出時才會撤銷PCB.

(2). 中級調(diào)度

? 虛擬存儲技術:將一部分磁盤空間劃為交換區(qū),內(nèi)存中暫時不會用到的數(shù)據(jù)會移動到這里進行存儲,以節(jié)省內(nèi)存空間.

? 暫時被調(diào)到外存中等待的進程狀態(tài)被稱為掛起狀態(tài).

? 中級調(diào)度就是決定要將那個處于掛起狀態(tài)的進程重新==調(diào)入==內(nèi)存.

(3). 線程狀態(tài)的七狀態(tài)模型

1574579668356

(4). 低級調(diào)度

? 低級調(diào)度也叫進程調(diào)度,是按照某一種策略從就緒隊列中選取一個進程,將處理機分配給它.

(5). 聯(lián)系和對比

1574579844676

7. 進程調(diào)度

(1). 進程調(diào)度的時機

? 當前運行的進程==主動==放棄處理機:進程正常終止,發(fā)生異常,主動請求阻塞(等待I/O)

? 當前運行的進程==被動==放棄處理機:分配的時間片用完,有更緊急的事情處理(中斷),被強占CPU資源

不能進行進程調(diào)度的情況:

• 處理中斷的過程中
• 處于內(nèi)核程序臨界區(qū)中(普通臨界區(qū)可以被調(diào)度)
• 原子操作過程中(原語)

(2). 進程調(diào)度的方式

• 搶占式
  • 只允許進程主動放棄處理機
  • 實現(xiàn)簡單,系統(tǒng)開銷小
  • 無法及時處理緊急任務,適合早期的批處理程序
• 非搶占式
  • 當一個進程在處理機上運行時,出現(xiàn)了另一個更緊急的進程需要使用處理機,那么此時運行的進程會讓出CPU權限.
  • 可以優(yōu)先處理更緊急的進程,也可實現(xiàn)讓各進程按時間片輪流執(zhí)行的功能
  • 適用于分時操作系統(tǒng),實時操作系統(tǒng)

(3). 調(diào)度算法的評價指標

• CPU利用率 = 忙碌時間/總時間
• 系統(tǒng)吞吐量 = 完成的作業(yè)數(shù)量/花費時間
• 周轉時間 = 作業(yè)完成時間-作業(yè)提交時間
  • 平均周轉時間 = 各作業(yè)周轉時間之和/作業(yè)數(shù)
  • 帶權周轉時間 = 作業(yè)周轉時間/作業(yè)實際運行時間(永遠大于1)
  • 平均帶權周轉時間 = 各作業(yè)帶權周轉時間之和/作業(yè)數(shù)

(4). 調(diào)度算法

1). 先來先服務(FCFS)

? 按照作業(yè)到達后背隊列的順序進行執(zhí)行,不可搶占,不會發(fā)生饑餓

? 優(yōu)點:公平,實現(xiàn)簡單

? 缺點:對長作業(yè)有利,對短作業(yè)不利

2). 短作業(yè)優(yōu)先(SJF)

? 每次選擇作業(yè)時,選擇當前所有作業(yè)中最短的作業(yè)執(zhí)行.當作業(yè)時間一致時,先執(zhí)行早到達的.會導致饑餓

? 優(yōu)點:平均等待時間和平均周轉時間短

? 缺點:對短作業(yè)有利,對長作業(yè)不利,會產(chǎn)生饑餓現(xiàn)象

3). 高響應比優(yōu)先(HRRN)

? 每次選擇作業(yè)是計算響應比((等待時間+要求服務時間)/要求服務時間).(響應比<=1)

? 綜合考慮等待時間和運行時間,無明顯缺點.不會導致饑餓.

4). 時間片輪轉(RR)

? 時間片是將CPU每次分配的時間設置為一樣的,公平地為每個進程輪流(根據(jù)作業(yè)到達的順序)分配時間片.

? 根據(jù)時鐘裝置發(fā)出的時鐘中斷來進行搶占,所以是搶占式的.

? 不會導致饑餓.

? 優(yōu)點:公平,響應快,適用與分時操作系統(tǒng)

? 缺點:不區(qū)分任務的緊急程度,由于高頻度的進程切換會有一定開銷.

? 時間片過短會導致開銷過大,時間片過長會導致退化成先來先服務.

5). 優(yōu)先級調(diào)度算法

? 按照優(yōu)先級進行選擇

? 優(yōu)點:區(qū)分任務的緊急成都,適用于實時操作系統(tǒng)

? 缺點:可能導致饑餓.

6). 多級反饋隊列

? 設置多級隊列,優(yōu)先級從高到低,時間片從小到大.

? 新進程直接進入一級隊列

? 分配完時間片進入下一級隊列,被處理機搶占的進程重新回到自己所在的隊列尾.

? 當前一級隊列為空時,才會為下一級隊列中的進程分配時間片.

? 到最后一級的隊列就不會再向下降級了.

? 優(yōu)點:公平,可以靈活調(diào)整對進程的偏好程度(不降級的設置)

? 缺點:會造成饑餓

8. 實現(xiàn)進程互斥

(1). 軟件實現(xiàn)

1). 單標志法

? 在一個進程訪問完臨界區(qū)后將權限給另一個進程.

? 當一個進程一直不訪問臨界區(qū),那么另一個進程也無法訪問.違背空閑讓進

2). 雙標志先檢查法

? 兩個進程都有一個標志位

? 進入臨界區(qū)前會先進行標志位檢查,然后將另一個進程的標志位改為等待

? 退出臨界區(qū)將另一個進程的標志位改為可以訪問

? 進入臨界區(qū)和對其他進程上鎖不是原子操作,所以可能造成多個進程同時進入臨界區(qū).違反忙則等待

3). 雙標志后檢查法

? 對標志的自旋檢查放在了更改另一個進程標志位之后.

? 可能兩個進程都更改了彼此的標志位,違反了空閑讓進和有限等待.

4). Peterson算法

? 設置一個變量表示那個進程優(yōu)先進入臨界區(qū),在標志位檢查之前更改為對方

1. 主動爭取
2. 主動謙讓
3. 檢查自己是不是最后謙讓的那個進程,如果是則讓出機會.

(2). 硬件實現(xiàn)

1). 中斷屏蔽

? 原語的實現(xiàn)方式

? 簡單高效,但不適合用戶進程,內(nèi)核態(tài)不可隨意暴露給用戶

2). TestAndSet指令

? 原子性的進行上鎖和檢查操作

3). Swap指令

? 原子性的交換兩個值

? 邏輯上與TAS指令一樣

8. 信號量機制

? 信號量其實就是一個變量,可以用來表示系統(tǒng)中的某種資源的數(shù)量.

? 使用wait(S)原語減少一個信號量(相當于獲取鎖),使用signal(S)原語增加一個信號量(解鎖).

? 通常也簡稱為P(S),V(S)操作

(1). 整型信號量

? 信號量為整型變量

? wait(S)操作自旋等待信號量大于0時,信號量-1,退出

? signal(S)操作給信號量+1

(2). 記錄型信號量

? 信號量中除了定義整型信號量值,還定義了等待隊列.

? wait(S)先設置信號量的值減一,然后判斷當前信號量的狀態(tài),如果小于零,將當前進程添加到等待隊列

? signal(S)先設置信號量的值加一,然后判斷信號量的值小于等于0,從等待隊列中喚醒第一個進程

可以解決讓權等待

(3). 信號量實現(xiàn)互斥

? 在臨界區(qū)前面加上P操作,后面加上V操作.

(4). 信號量實現(xiàn)同步

? 初始信號量為0,先進行的操作后面進行V操作,后進行的操作之前進行P操作.

1574586484003

9. 進程同步問題

(1). 生產(chǎn)者消費者問題

1574591548639

? 出現(xiàn)空閑位和生產(chǎn)者放入商品是同步關系 ===> 同步信號量 semaphore empty = n

? 緩沖區(qū)中出現(xiàn)商品與消費者拿出商品是同步關系 ===> 同步信號量 semaphore full = 0

? 所有進程之間都是互斥關系 ===> 互斥信號量 semaphore mutex = 1

? ==互斥信號量的P操作要在同步信號量的P操作之后進行==,防止已經(jīng)獲得了同步鎖,但是緩沖區(qū)已滿或者空,就死鎖了.

(2). 多生產(chǎn)者多消費者問題

1574593201391

? 父親放蘋果和女兒吃蘋果是同步關系 ===> 同步信號量 semaphore apple = 0

? 母親放橘子和兒子吃橘子是同步關系 ===> 同步信號量 semaphore orange = 0

? 盤子為空和父親母親放入水果是同步關系 ===> 同步信號量 semaphore plate = 1(盤子中可以放入的水果數(shù))

1574593597436

(3). 吸煙者問題

1574593703419

? 還是生產(chǎn)者消費者的問題

? 組合一的數(shù)量 ===> 同步信號量 semaphore offer1 = 0

? 組合二的數(shù)量 ===> 同步信號量 semaphore offer2 = 0

? 組合三的數(shù)量 ===> 同步信號量 semaphore offer3 = 0

? 抽煙是否完成 ===> 同步信號量 semaphore finish = 0

(4). 哲學家進餐問題

1574595010949

思路一:只能有4個哲學家同時用餐,總有一個哲學家可以拿到兩只筷子

思路二:奇數(shù)哲學家先拿左邊筷子,偶數(shù)哲學家先拿右邊筷子,會有一哲學家沒有筷子被阻塞

思路三:加鎖,同時拿兩雙筷子

10. 死鎖

(1). 什么是死鎖

? 線程之間持有資源并且循環(huán)等待其他資源而相互阻塞的情況.

(2). 死鎖產(chǎn)生的必要條件

• 互斥條件:資源只能被一個進程使用,不能共享
• 不可剝奪條件:資源被一個進程占有之后不能被其他進程剝奪
• 請求和保持條件:進程得到一個資源之后提出了新的獲取資源的請求,但同時不放棄自己已經(jīng)擁有的資源
• 循環(huán)等待條件:存在資源的循環(huán)等待鏈

(3). 避免死鎖

1). 安全序列,安全狀態(tài)和死鎖

? 系統(tǒng)按照這種序列分配資源,每個進程都能順利完成.

? 只要能找出一個安全序列,系統(tǒng)就是安全狀態(tài),安全序列可能有多個

? 安全狀態(tài)可以轉化為不安全狀態(tài)(分配資源給進程,空閑資源減少),不安全狀態(tài)也可以轉化為安全狀態(tài)(進程歸還資源).

2). 銀行家算法

? 在資源分配之前,預先判斷這次分配是否會導致系統(tǒng)進入不安全的狀態(tài),從而決定是否答應本次資源分配請求.

image-20191229175617683

安全性檢查:

1. 循環(huán)檢查某一進程最多需要的資源是否能被滿足,如果可以就分配給它,換取已經(jīng)分配給這個進程的所有資源(進程歸還資源),如果不行就跳過.
2. 如果若干輪循環(huán)之后,所有的進程都能被滿足分配資源的請求,那么認為當前狀態(tài)是安全的,上一步進程的順序就是安全序列

銀行家算法中,會有一個進程向系統(tǒng)申請一定的資源,要做的就是系統(tǒng)減去這些資源之后(那么肯定要先判斷本次申請能否滿足),進行安全性檢查,判斷分配資源之后是否會不安全.