第二章、程序管理

文章目錄

• 一、程序與線程
• • 1、程序的定義、特征、組成、組織
  • • （1） 程序的定義
    • （2） 程序的特征
    • （3） 程序的組成
    • （4） 程序的組織
  • 2、程序的狀态與轉換
  • • （1） 總覽
    • （2） 原語實作程序控制
  • 3、線程概念與多線程模型
  • • （1） 概述
    • （2） 線程屬性
    • （3） 線程的實作方式
    • （4） 多線程模型
  • 4、程序與線程的差別與聯系
  • 5、程序間通信
  • • （1） 管道
    • （2） 共享記憶體
    • （3） 消息隊列
    • （4） 信号量
    • （5） Socket
• 二、處理機排程
• • 1、概覽
  • 2、排程的基本概念
  • 3、排程的三個層次
  • • （1） 作業排程（進階排程）
    • （2） 記憶體排程（中級排程）
    • （3） 程序排程（低級排程）
    • （4） 程序的挂起與七狀态模型
    • （5） 三層排程的聯系與對比
  • 4、程序排程的時機
  • • （1）什麼時候需要程序排程
    • （2）什麼時候不能進行程序排程
    • （3）OS核心程式臨界區與普通臨界區的程序排程情況
  • 5、程序排程的方式
  • 6、程序切換過程
  • 7、排程算法評價名額
  • • （1） CPU使用率
    • （2）系統吞吐量
    • （3）周轉時間
    • （4）等待時間
    • （5）響應時間
  • 8、排程算法對比
  • • （1）FCFS —— 先到先服務
    • （2）SJF —— 短作業優先
    • （3）HRRN —— 高響應比優先
    • （4）前三種排程算法對比
    • （5）時間片輪轉排程算法
    • （6）優先級排程算法
    • （7）多級回報隊列排程算法
    • （8）後三種排程算法對比
• 三、程序同步與互斥
• • 1、概覽
  • 2、概念
  • • （1）程序同步
    • （2）程序互斥
  • 3、臨界區資源互斥通路的軟體實作方法
  • • （1）思維導圖
    • （2）單标志法
    • （3）雙标志先檢查法
    • （4）雙标志後檢查法
    • （5）Perterson算法
  • 4、臨界區資源互斥通路的硬體實作方法
  • • （1）思維導圖
    • （2）中斷屏蔽方法
    • （3）TestAndSet指令
    • （4）Swap指令
  • 5、信号量機制
  • • （1）思維導圖
    • （2）為什麼引入
    • （3）什麼是信号量機制
    • （4）整形信号量
    • （5）記錄型信号量
    • （6）一個例子
    • （7）記錄型信号量知識點總結
  • 6、信号量機制實作程序的互斥、同步與前驅關系
  • • （1）思維導圖
    • （2）信号量實作程序互斥
    • （3）信号量實作程序同步
    • （4）信号量實作前驅關系
  • 7、管程
  • • （1）思維導圖
    • （2）為什麼引入管程
    • （3）管程的組成及基本特征
    • （4）管程實作生産着消費者問題
    • （5）Java中類似于管程的機制
• 四、死鎖
• • 1、概覽
  • 2、什麼是死鎖
  • 3、死鎖、饑餓、死循環之間的差別
  • 4、死鎖的産生
  • • （1）死鎖産生的必要條件
    • （2）什麼時候會發生死鎖
  • 5、死鎖的處理政策
  • • （1）預防死鎖
    • • ① 破壞互斥條件
      • ② 破壞不可剝奪條件
      • ③ 破壞請求和保持條件
      • ④ 破壞循環等待條件
    • （2）避免死鎖
    • • ① 什麼是安全序列
      • ② 安全序列、安全狀态、不安全狀态 與 死鎖 聯系
      • ③ 如何避免進入不安全狀态 —— 銀行家算法
      • ④ 代碼實作
    • （3）死鎖的檢測
    • （4）死鎖的解除

一、程序與線程

1、程序的定義、特征、組成、組織

（1） 程序的定義

• 程序是 一個具有一定獨立功能的程式在一個資料集上的一次動态執行的過程，是作業系統進行資源配置設定和排程的一個獨立機關，是應用程式運作的載體。
• 程序曾經是分時系統的基本運作機關； 在面向程序設計的系統（如早期的UNIX）中，程序是程式的基本執行實體； 在面向線程設計的系統（如當代多數作業系統）中，程序本身不是基本運作機關，而是線程的容器。

（2） 程序的特征

（3） 程序的組成

而其中最重要的就是程序控制塊PCB（Process Control Block）

• PCB是程序存在的唯一标志。
• PCB通常包含的内容：

• 

（4） 程序的組織

① 連結方式

② 索引方式

2、程序的狀态與轉換

（1） 總覽

（2） 原語實作程序控制

① 總覽

② 程序控制大緻圖解

③ 程序建立原語

④ 程序終止原語

⑤ 程序喚醒和阻塞原語（必須成對出現，成對使用）

⑥ 程序切換原語

3、線程概念與多線程模型

（1） 概述

（2） 線程屬性

（3） 線程的實作方式

線程的實作分為兩類：使用者級線程(User-Level Thread,UTL)和核心級線程(Kernel-Level Thread, KTL)l。核心級線程又稱核心支援的線程。

① 使用者級線程

② 核心級線程

③ 特殊的組合方式及重點注意

（4） 多線程模型

① 多對一模型

② 一對一模型

③ 多對多模型

此種模型效率是三種模型中最好的

4、程序與線程的差別與聯系

（4）差別

5、程序間通信

為什麼要引入程序間通信：

• 各程序擁有的位址空間獨立
• 為保證安全，一個程序不能通路另一個程序的位址空間
• 程序之間時常需要互相交換資料

程序間通信方式主要有五種：管道、共享記憶體、消息隊列、信号量、Socket

（1） 管道

管道，通常指無名管道，是UNIX系統IPC最古老的方式。管道分為無名管道 和 命名管道 兩種 ， 除了建立、打開、删除的方式不同外，這兩種管道幾乎是一樣的。他們都是通過核心緩沖區實作資料傳輸。

特點：

• 單管道為半雙工，要實作雙向同時傳輸可通過建立雙管道實作
• 隻能用于具有親緣關系的程序之間的通信
• 管道的實質為核心緩沖區，程序以先進先出的方式從緩沖區存取資料
• 寫滿才能讀，讀完才能寫
• 一個資料隻能被讀一次，讀出以後便在緩沖區不複存在了

（2） 共享記憶體

共享記憶體允許兩個或多個程序共享一個給定的存儲區，這一段存儲區可以被兩個或兩個以上的程序映射至自身的位址空間中，一個程序寫入共享記憶體的資訊，可以被其他使用這個共享記憶體的程序，通過一個簡單的記憶體讀取錯做讀出，進而實作了程序間的通信。

采用共享記憶體進行通信的一個主要好處是效率高，因為程序可以直接讀寫記憶體，而不需要任何資料的拷貝，對于像管道和消息隊裡等通信方式，則需要再核心和使用者空間進行四次的資料拷貝，而共享記憶體則隻拷貝兩次：一次從輸入檔案到共享記憶體區，另一次從共享記憶體到輸出檔案。

共享記憶體有兩種實作方式：

1、基于資料結構的共享

2、基于存儲區的共享

（3） 消息隊列

消息隊列，就是一個消息的連結清單，是一系列儲存在核心中消息的清單。使用者程序可以向消息隊列添加消息，也可以向消息隊列讀取消息。

消息隊列與管道通信相比，其優勢是對每個消息指定特定的消息類型，接收的時候不需要按照隊列次序，而是可以根據自定義條件接收特定類型的消息。

（4） 信号量

信号量（semaphore）與已經介紹過的 IPC 結構不同，它是一個計數器。信号量用于實作程序間的互斥與同步，而不是用于存儲程序間通信資料。

1、特點

• 信号量用于程序間同步，若要在程序間傳遞資料需要結合共享記憶體。
• 信号量基于作業系統的 PV 操作，程式對信号量的操作都是原子操作。
• 每次對信号量的 PV 操作不僅限于對信号量值加 1 或減 1，而且可以加減任意正整數。
• 支援信号量組。

2、原型

• 最簡單的信号量是隻能取 0 和 1 的變量，這也是信号量最常見的一種形式，叫做二值信号量（Binary Semaphore）。而可以取多個正整數的信号量被稱為通用信号量。

Linux 下的信号量函數都是在通用的信号量數組上進行操作，而不是在一個單一的二值信号量上進行操作。

（5） Socket

适合同一主機的不同程序間和不同主機的程序間進行全雙工網絡通信。在所有提供了TCP/IP協定棧的作業系統中幾乎都提供了socket，而所有這樣作業系統，對套接字的程式設計方法幾乎是完全一樣的，即“網絡程式設計”。

二、處理機排程

1、概覽

2、排程的基本概念

3、排程的三個層次

（1） 作業排程（進階排程）

（2） 記憶體排程（中級排程）

（3） 程序排程（低級排程）

（4） 程序的挂起與七狀态模型

（5） 三層排程的聯系與對比

4、程序排程的時機

（1）什麼時候需要程序排程

（2）什麼時候不能進行程序排程

（3）OS核心程式臨界區與普通臨界區的程序排程情況

5、程序排程的方式

• 所謂程序排程方式，是指當某個程序正在處理機上執行時，若有某個更為重要或緊迫的程序需要處理，即有優先權更高的程序進入就緒隊列，此時應如何配置設定處理機。

  

6、程序切換過程

7、排程算法評價名額

（1） CPU使用率

（2）系統吞吐量

（3）周轉時間

（4）等待時間

（5）響應時間

8、排程算法對比

（1）FCFS —— 先到先服務

（2）SJF —— 短作業優先

• 非搶占式（SJF）

  

• 搶占式（SRTN）

  

  

（3）HRRN —— 高響應比優先

（4）前三種排程算法對比

（5）時間片輪轉排程算法

• 時間片為 2 舉栗子

  

  

• 時間片為 5 舉栗子

  

• 可能出現的問題

  

  

（6）優先級排程算法

• 搶占式例子

  

• 非搶占式例子

  

• 補充

  

（7）多級回報隊列排程算法

• 舉個例子

  

（8）後三種排程算法對比

三、程序同步與互斥

1、概覽

2、概念

（1）程序同步

• 同步也稱為直接制約關系。
• 在多道程式環境下，程序是并發執行的，不同程序之間存在着不同的互相制約關系。為了協調程序之間的互相制約關系,如等待、傳遞資訊等，引入了程序同步的概念。程序同步是為了解決程序的異步問題。
• 異步性：程序具有異步性的特征。異步性是指，各并發執行的程序以各自獨立的、不可預知的速度向前推進。

一個簡單的例子來了解這個概念。

例如，讓系統計算1 + 2x3，假設系統産生兩個程序: 一個是加法程序，一個是乘法程序。要讓計算結果是正确的，一定要讓加法程序發生在乘法程序之後,但實際上作業系統具有異步性,若不加以制約，加法程序發生在乘法程序之前是絕對有可能的，是以要制定一定的機制去限制加法程序，讓它在乘法程序完成之後才發生。

（2）程序互斥

• 程序互斥指當一個程序通路某臨界資源時，另一個想要通路該臨界資源的程序必須等待。目前通路臨界資源的程序通路結束，釋放該資源之後，另一個程序才能去通路臨界資源。

在這裡需複習一下臨界資源的概念。

我們把一個時間段内隻允許一個程序使用的資源稱為臨界資源。許多實體裝置(比如攝像頭、列印機)都屬于臨界資源。此外還有許多變量、資料、記憶體緩沖區等都屬于臨界資源。

• 對臨界資源的通路，必須互斥地進行。

  

• 為了禁止兩個程序同時進入臨界區，需遵循以下 準則

  

3、臨界區資源互斥通路的軟體實作方法

（1）思維導圖

• 軟體實作方法的思想：在進入區設定并檢查一些标志 來标明是否有程序在臨界區中,若已有程序在臨界區，則在進入區通過循環檢查進行等待，程序離開臨界區後則在退出區修改标志。入區通過循環檢查進行等待，程序離開臨界區後則在退出區修改标志。

  

（2）單标志法

（3）雙标志先檢查法

（4）雙标志後檢查法

（5）Perterson算法

4、臨界區資源互斥通路的硬體實作方法

（1）思維導圖

（2）中斷屏蔽方法

（3）TestAndSet指令

• 執行TSL指令時，它的内部運轉邏輯：
  • 假設lock現在為false，代表臨界資源A空閑，那麼我就可以通路這個資源，同時将lock=true，提醒别的程序，這個臨界資源A我正在使用，讓他們等等
  • 假設lock為true，代表臨界資源正在有人使用，是以我必須等待，并且将lock=true，并不影響什麼，是以沒關系，隻是為了讓lock為false時可以上鎖，将上鎖與檢查在一個TSL指令完成。

（4）Swap指令

5、信号量機制

（1）思維導圖

（2）為什麼引入

• 為了更好地解決程序互斥與同步問題

  

（3）什麼是信号量機制

（4）整形信号量

（5）記錄型信号量

（6）一個例子

（7）記錄型信号量知識點總結

6、信号量機制實作程序的互斥、同步與前驅關系

（1）思維導圖

（2）信号量實作程序互斥

（3）信号量實作程序同步

（4）信号量實作前驅關系

7、管程

（1）思維導圖

（2）為什麼引入管程

（3）管程的組成及基本特征

（4）管程實作生産着消費者問題

（5）Java中類似于管程的機制

四、死鎖

1、概覽

2、什麼是死鎖

3、死鎖、饑餓、死循環之間的差別

4、死鎖的産生

（1）死鎖産生的必要條件

（2）什麼時候會發生死鎖

5、死鎖的處理政策

（1）預防死鎖

① 破壞互斥條件

② 破壞不可剝奪條件

③ 破壞請求和保持條件

④ 破壞循環等待條件

（2）避免死鎖

① 什麼是安全序列

② 安全序列、安全狀态、不安全狀态 與 死鎖 聯系

③ 如何避免進入不安全狀态 —— 銀行家算法

④ 代碼實作

（3）死鎖的檢測

（4）死鎖的解除