[專業課]——作業系統複習

目标

• 前言
• 基本概念
• CPU排程
• 程序
• 線程
• 程序的互斥和同步
• 管程
• 死鎖
• 記憶體
• 檔案
• IO

前言

王道

基本概念

計算機系統:

• 沒有應用程式，使用者也可以和作業系統做簡單互動
• OS是一種最基本的系統軟體；控制和管理硬體和軟體等計算機資源；為使用者、軟體提供簡單的服務

  

OS的功能:

(計算機資源的管理)

• 檔案管理
• 記憶體管理
• CPU排程
• 裝置管理

(為使用者和應用程式提供服務)

• 指令接口
  • 聯機指令：互動式的指令行（如CMD）
  • 脫機指令：批處理（一堆預先寫好的指令行，如.bat檔案）
• 程式接口:作業系統預先提供的（由系統調用組成，程式接口=系統調用，作業系統預制好的一些“API”供你調用）
• GUI界面

OS的特征:

• 并發性（程式運作）
  • 并發：宏觀上是同時發生的，但微觀上是交替發生的。多道程式技術與os的并發一起誕生。
  • 并行：兩個或多個事件在同一時刻發生
• 共享性（資源通路）
  • 互斥共享：同一時間隻允許同一程序通路該資源
  • 同時共享：同一時間隻允許多個程序“同時”通路該資源
• 虛拟化：把實際存在的實體上的實體抽象成多個邏輯上存在的對應物，而使用者能夠感受到的就是邏輯上的
  • 利用輔存增加CPU的容量（空分複用技術）
  • 時間片輪轉，看似同時處理多個程序（時分複用技術）
• 異步：一個程序不是一下子執行完的，而是走走停停。有了并發，才有了異步。

OS的分類

• 單道批處理系統:記憶體中隻有一個作業（解決了IO和CPU速度不比對的沖突，存在資源使用率低的缺點）
• 多道批處理系統:記憶體中有多個作業，通過作業排程交替運作（解決了資源使用率低的缺點，存在互動性不高的缺點）
• 分時作業系統:時間片輪轉地為多個使用者服務，提高了互動能力（解決了互動性的問題）

OS的運作機制:

• 指令:CPU識别和執行的最基本指令
  • 特權指令：核心态（管态）下運作
  • 非特權指令：使用者态（目态）、核心态下運作
• 兩種CPU狀态：
  • 核心态：可運作特權、非特
  • 使用者态：可運作非特
• 兩種程式：
  • 核心程式：運作特權指令，實作了OS的核心功能
  • 應用程式：運作非特權指令

OS的核心:

• 大核心:時鐘管理、中斷、原語+檔案管理、記憶體管理、CPU管理、裝置管理…
  • 缺點：代碼混亂，難以維護
  • 優點：執行的效率高
• 微核心:隻實作時鐘管理、中斷、原語這些核心功能
  • 缺點：頻繁地在使用者态和核心态進行切換，性能低
  • 優點：結構清晰，友善維護

中斷:

• 中斷發生時，CPU暫停運作，CPU進入核心态，由作業系統對中斷進行處理
• 中斷的分類:
  • 内中斷:信号來自目前正在CPU中執行的指令
    • 自願中斷：
    • 強迫中斷： 硬體問題：缺頁？記憶體不夠？ 軟體問題：整數除0？
  • 外中斷:來自外部裝置
• 外中斷的處理過程：
  • 執行完一個指令，CPU要檢查是否有外中斷
  • 檢測到中斷，則儲存被中斷程序的CPU環境（如程式狀态字、程式計數器、通用寄存器等）
  • CPU轉為核心态，根據中斷信号類型，轉入響應的中斷處理程式
  • 退出核心态，恢複儲存的CPU環境，繼續執行程序

系統調用:作業系統定義的一些函數，供使用者程式調用。核心功能需要特權指令來完成，是以隻能運作在核心态

• 功能：也就是OS中，提供使用者的簡單服務的那四個功能+程序通信
• 系統調用與庫函數的差別:有的庫函數是簡單的函數，有的則需要調用到系統調用函數（建立檔案…）

CPU排程

排程的分類:

• 進階排程（作業）:從外存隊列的作業中選擇進行建立程序，到達記憶體，進入就緒隊列
• 中級排程（記憶體）:記憶體中的程序被暫時調到外存，進入挂起隊列；再從挂起隊列中調回記憶體
• 低級排程（程序）:程序執行

程序排程的分類

• 非剝奪式
• 剝奪式:如果一個程序正在CPU上執行，此時有一個優先級更高的程序進入就緒隊列，則被搶占

排程算法的名額:

• CPU使用率 = CPU忙碌時間 / 總時間
• 系統吞吐量 = 總共完成了多少道作業 / 總時間
• 周轉時間
  • 作業周轉時間 = 作業完成時間 - 作業到達時間
  • 平均周轉時間 = 周轉時間之和 / 作業數
  • 帶權周轉時間 = 作業周轉時間 / 作業實際運作時間
  • 平均帶權周轉時間 = 帶權周轉時間之和 / 作業數
• 等待時間
  • 等待時間 = 周轉時間 - 運作時間-IO服務時間（如果有的話）
  • 平均等待時間 = 等待時間之和 / 作業數
• 響應時間：使用者送出請求到首次響應的時間
• 相應比：（等待時間+運作時間） / 運作時間

排程算法:

• 先來先服務（FCFS）：

  

  • 優點:算法簡單、公平
  • 缺點:對長作業比較有利，對短作業不利
  • 不會導緻饑餓
• 短作業優先(非搶占式)（Shortest Job First）:

  

• 搶占式短作業優先

  

  

  • 優點:最短的平均等待時間和周轉時間
  • 缺點:
    • 對短作業有利，對長作業不利
    • 會導緻饑餓
• 時間片輪轉排程算法(分時)
  • 時間片太大：退化成先來先服務，響應時間長
  • 時間片太小：程序切換過于頻繁
  • 不會導緻饑餓
• 優先級排程算法（搶占、非搶占）
  • 靜态優先級
  • 動态優先級：如：高響應比排程算法 ：每一次排程都計算相應比=已經等待時間+運作時間 / 運作時間，然後選取相應比最大的那一個
• 多級回報隊列:
  • 有k個時間片從小到大、優先級從高到低的回報隊列
  • 新程序到達時，先進入第一個隊列，按照先來先服務依次運作，運作完一個時間片之後若還沒有完成，則被放入下一個隊列的隊尾，如果目前就是最後一個隊列，則放入目前隊列的隊尾
  • 搶占式的排程。新程序到達時，正在運作的更下層隊列中的程序會被搶占。
  • 會導緻饑餓

程序

程序的定義:

• 程序是程式（程序實體）的一次執行
• 系統進行資源配置設定、排程的最基本機關

程序的組成：

• 程式段
• 資料段
• PCB:作業系統對其進行管理需要的各種資訊(pid\uid…)，是程序存在的唯一标志

程序的組織（多個程序）:

• 連結方式：按照程序的狀态（執行、等待…）建立多個隊列，OS持有指向各個隊列的指針
• 索引方式：隊列替換成指針（隊列中的每一個程序有各自的索引指針）

程序的特征

• 并發性：
• 異步性：
• 結構性：由資料段、程式段、PCB組成
• 獨立性：獨立接受資源配置設定、獨立接受排程的最基本機關
• 動态性：是程式（程序實體）的一次動态執行

程序的狀态與轉換：

• 三種狀态：
  • 運作态:正在CPU中運作的程序
  • 就緒态:已經具備運作資源，正在等待CPU
  • 阻塞态:等待某種資源
  • 建立态
  • 終止态
• 狀态的轉換:

  

  程序控制：
• 建立原語：建立空白PCB，為其配置設定資源，放入就緒隊列
• 終止原語：運作->終止
• 阻塞原語：運作->阻塞
• 喚醒原語：阻塞->就緒
• 切換原語：運作->就緒；就緒->運作

程序通信：無法直接通路對方

• 共享存儲：兩個程序共享資源，是一種互斥共享
• 管道通信：開辟一個緩沖區。一個程序寫，另一個程序讀
• 消息傳遞：
  • 直接通信方式：每一個程序維護自己的消息隊列
  • 間接通信方式：信箱作為中轉

線程

程序和程序可以并發，程序内部能否并發？引入線程之後，1. 程序内部（線程）的并發度 2. 線程管理（使用者态-》核心态的時間） 是兩個需要權衡的因素

線程：了解為輕量的程序，處理機排程的最小機關（資源配置設定的最小單元依然是程序），增加了程序内部的并發度

• 線程的分類:
  • 隻支援使用者級線程的系統（多對一映射）：【使用者層面】多個使用者級線程；【核心層面】一個核心級線程（程序）。
    • 優點：線程之間的切換不需要系統調用，僅在使用者态完成，系統開銷小
    • 缺點：并行度差
  • 支援核心級線程的系統：【使用者層面】多個使用者級線程；【核心層面】多個核心級線程。
    • 一對一的映射：
      • 優點：并發度高
      • 缺點：系統開銷大
    • 多對多的映射：
      • 優點：兼顧

程序的互斥和同步

臨界資源：一種互斥共享資源，一個時間隻能被一個程序通路

• 通路臨界資源的過程如下:
  • 進入區：程序檢查是否能夠通路這個臨界資源，若能通路，則上鎖
  • 臨界區：實際通路臨界資源的代碼
  • 退出區：用完，解鎖
• 通路臨界資源(程序互斥)的三個原則：
  • 空則讓進
  • 忙則等待
  • 有限等待：不發生饑餓
  • 讓權等待: 一旦不能在臨界區時，馬上釋放CPU

程序同步和互斥：

• 同步：程序的執行有先後關系
• 互斥：程序互斥地通路同一個臨界資源

互斥的軟體實作：

• 單标志法：
  • 大緻思路：設定一個标志，0表示目前0号程序能通路臨界資源，1表示…。對于0号程序，一開始通過while(flag!=0)來決定是否是等待、還是占用。
  • 缺點：flag的初始值決定了程序的通路順序，若flag初始化為0，必須要等到0程序通路完，其它程序才有可能通路，違背了**”空則讓進“**的原則，

    

• 雙标志先檢查法：增加一個标志位
  • 大緻思路： 增設一個标志位，解決單标志法中空則讓進不滿足的問題
  • 缺點：進入區中的1. 判斷另一程序是否占用資源 2. 給目前程序上鎖 不是一個原語，會導緻兩個程序同時占用一個臨界資源，違背了**”忙則等待“**的原則。

    

• 雙标志後檢查法：将1. 判斷 2. 上鎖的順序颠倒
  • 缺點：其實和上一種方法一樣，兩個程序一起上鎖，就違背了**”空則讓進“、”有限等待“**的原則。

    

• Peterson算法：再增加一個标志，表示可以優先讓給哪一個程序
  • 大緻思想：舉一個現實生活中的例子：我想用吹風機（上鎖），但如果你想用，我會優先給你用（謙讓），但如果此時你雖然也想用吹風機（上鎖），但你也表示如果我想用的話會優先給我用（謙讓）。雖然此時雙方都陷入循環，但在我的下一次循環判斷時，發現了對方的謙讓，于是我可以退出循環，先用這個吹風機。

    

  • 缺點：由于while的存在，會違背**”讓權等待“**的原則。

信号量：使用原語來對信号量進行操作，實作程序的同步和互斥

• 原語 :wait（P）（檢視資源（檢查）+修改信号量（上鎖）是一個函數）和signal（V）（釋放資源），徹底解決單标志、雙标志、peterson的不足。

  

• 整型信号量：用一個整數型的變量來表示某種資源的數量。wait(資源)；臨界區；signal(資源)。缺點：無法進入臨界區的程序會一直執行wait中的while，違背了讓權等待。
• 記錄型信号量：增加一個等待隊列。如果一個程序暫時無法占用資源，該程序就被加入到該資源所對應的信号量的等待隊列中，進而避免了while循環，滿足了讓權等待原則。

  

• 使用信号量來實作程序互斥、程序同步：
  • 互斥：信号量初值為1
  • 同步：信号量初值為0，先運作的代碼之後進行V操作；後運作的代碼之前進行P操作

程序的生産者消費者問題：兩個程序。1. 對緩沖區有互斥關系，空滿兩對同步關系 2. 當緩沖區為空->full=0，生産者先執行，是以V(full)寫在生産者的臨界區之後；P(full)。。。 3. 當緩沖區為滿->empty=0，消費者先執行，是以V(empty)寫在消費者的臨界區之後；P(empty)。。。 4. 互斥寫在同步的裡面，考慮：此時empty=0，一定是消費者要先執行，而如果此時生産者執行，互斥信号量為0，則發生死鎖。5. 臨界區代碼盡可能少：

程序的多生産者多消費者問題（父親母親、女兒兒子，女兒吃父親放的蘋果，兒子吃母親放的橘子）：

• 互斥：盤子：mutex=1
• 同步：
  • 當放入蘋果後，女兒才能取蘋果：apple=0
  • 當放入橘子後，兒子才能取橘子：orange=0
  • 女兒、兒子取完之後（盤子空），父親、母親才能放水果：empty=1

    

    讀者寫者問題（兩個寫程序，兩個讀程序 ）：
• 讀者和寫者互斥、寫者和寫者互斥：rw=1的互斥信号量
• 讀者和寫者不需要互斥：count=0的互斥信号量
• count的臨界通路：mutex=1的互斥信号量
• 寫者的優先問題：w=1的互斥信号量

  

哲學家進餐問題：

1. 設定一個初始值為4的信号量，保證同一時刻最多有四個哲學家競争
2. 吃飯前，保證能夠同時拿到兩個筷子
3. 奇數位的哲學家優先拿左側，偶數位的哲學家優先拿右側

管程

信号量機制編寫程式好困難啊…

為臨界資源定義一個資料結構，并向外提供對其操作的函數。對于互斥，管程定義了入口隊列，確定同一之間隻有同一程序在管程中；而對于同步，管程定義conditions變量（如x、y等），當一個程序執行x.wait()時，該程序被挂起，知道有一個程序執行了x.signal，而當一個程序執行x.signal時，有三種情況 1. x變量上沒有挂起程序，則該操作無效 2. 有，挂起程序等待目前程序執行完，才開始執行 3. 有，目前程序等待挂起程序執行。

死鎖

在并發環境下，各個程序互相等待對方手中的資源，導緻各個程序都阻塞，無法向前推進

三個不同的概念：

• 死鎖：程序互相等待對方手中的資源，發生死鎖一定有兩個以上的程序，一定處于阻塞态
• 饑餓：發生饑餓的程序可能隻有一個，可能處于就緒态（得不到排程運作）；也可能處于阻塞态（得不到資源）
• 死循環：程序處于運作态（是你自己代碼寫得爛！！！而其它的是作業系統的問題）

死鎖的必要條件：

• 互斥：互斥共享的臨界資源
• 不可剝奪：程序還沒使用完資源，則不會被強行搶占
• 請求并保持：占有一定資源的程序，請求占有其它已被占有的資源而受阻後，依然保持自己的資源
• 循環等待鍊

死鎖的應對政策

• 死鎖的預防
  • 破壞互斥條件：
    • 思想：使用SPOOLing技術把互斥共享資源改成邏輯上同步共享的資源
    • 缺點：系統安全性差
  • 破壞不可剝奪條件：
    • 思想：作業系統能夠幫助程序強行剝奪
    • 缺點：實作麻煩；容易破壞之前正在運作的程序的環境；換來換去系統開銷大
  • 破壞請求并保持條件：
    • 思想：靜态資源配置設定法：程序運作之前，必須要申請到所有資源
    • 缺點：資源的使用率很低
  • 破壞循環等待條件：
    • 思想：順序資源配置設定法： 為資源編号，每一個程序隻能按照編号從小到大申請資源，一定不存在循環等待鍊
    • 缺點：編号順序不代表資源的需求順序，資源的使用率很低

記憶體

檔案

IO