軟體設計師之作業系統萬字大總結（莽起來）

軟體設計師之作業系統

• • • 1.概述
    • 2.程序管理
    • • 2.1 程序的狀态
      • 2.2 前趨圖
      • 2.3 程序的同步與互斥
      • 2.4 PV操作
      • 2.5 死鎖
      • 2.6 銀行家算法
    • 3. 存儲管理
    • • 3.1 分區存儲組織
      • 3.2 段頁式存儲
      • • 3.2.1 頁式存儲組織
        • 3.2.2 段式存儲組織
        • 3.2.3 段頁式存儲組織
      • 3.3 快表
      • 3.4 頁面置換算法
    • 4. 檔案管理
    • • 4.1 索引檔案結構
      • 4.2 檔案和樹形目錄結構
      • 4.3 空閑存儲空間的管理
    • 5. 裝置管理
    • • 5.1 資料傳輸控制方式
      • 5.2 虛裝置與SPOOLING技術
    • 6. 微核心作業系統

1.概述

• 管理系統的硬體、軟體、資料i資源
• 控制程式運作
• 人機之間的接口
• 應用軟體與硬體之間的接口

作業系統具備哪些方面的管理職能：

• 程序管理
  • 程序的狀态
  • 前趨圖
  • PV操作
  • 死鎖問題
• 存儲管理
  • 段頁式存儲
  • 頁面置換算法
• 檔案管理
  • 索引檔案
  • 位示圖
• 作業管理
• 裝置管理
• 微核心作業系統

2.程序管理

2.1 程序的狀态

程序狀态是指在作業系統當中對程序進行管理的時候為程序指定的幾種狀态，以便于給程序配置設定相應的資源把它管理起來。

• 

2.2 前趨圖

哪些任務可以并行，哪些任務有前後關系。

2.3 程序的同步與互斥

• 互斥：在同一時刻，隻允許某一個程序使用這個資源。就如：千軍萬馬過獨木橋。

  

• 同步：速度上有差異，在一定情況停下等待。

  

• 互斥的反義詞是共享；同步的反義詞是異步。

• 

2.4 PV操作

• 臨界資源：程序間需要互斥方式對其進行共享的資源，如列印機、錄音帶機等
• 臨界區：每個程序中通路臨界資源的那段代碼稱為臨界區
• 信号量：是一種特殊的變量

• 在沒有加入PV操作時，不管是先進行生産者還是消費者都會出現問題，比如先進行消費者，是沒有生産者的，緩沖區裡沒有東西，就不能消費。

  

  • 加入PV操作後再來看
    • 先進行生産者：這時候s1 = 0，不是<0，進行下面的操作，s2 = 1；之後如果在進行生産者操作，這時候s1 = -1，是<0的，就會被放入程序的等待隊列，并将此程序阻塞起來；接下來進行消費者：s2 = 0，繼續往下執行，s1 = 0，這個時候就去隊列裡把阻塞的激活，也就是生産者激活了，這樣就能繼續執行了。
    • 先進行消費者，此時s2 = -1，是不能繼續往下走的。
• PV操作所解決的問題，其實是并發性能之間限制關系的問題的解決
• 例題：

  

  • P(Sn)與V(Sn)這一對信号量就表明最多允許n個購書者進入，因為這個一旦多一個人進來，就會進行阻塞。

  • 

  • V就相當于喚醒，而P就是阻塞，V可以喚醒P。
  • 在進行解題時，假設先進行某個問題，會面臨什麼問題，怎麼使用PV操作進行可以解決這個問題，就是正确答案了。

• 

• 例題：

  

  caa
• 不妨先标一下信号量，遵循從左到右，從上到下。箭頭的起點位置時V操作，箭頭的終點位置時P操作。

2.5 死鎖

死鎖：系統當中有一系列的資源，有一系列需要用到這些資源的程序，這些程序需要系統給它配置設定資源才能夠運作。如果說系統在某一時刻發現系統中所有能用的資源都已經配置設定出去了，而所有的程序都沒辦法去完成它本身的職責任務，進而釋放該有的資源，這就會産生死鎖。

• 程序管理時作業系統的核心，但如果設計不當，就會出現死鎖的問題。如果一個程序在等待一件不可能發生的事情，則程序就死鎖了，而如果一個或多個程序産生死鎖，就會造成系統死鎖。
• 例：系統有3個程序：A，B，C。這3個程序都需要5個系統資源，系統至少有多少個資源，才不可能發生死鎖？
• 公式：至少需要k * （n - 1）+1個資源，其中k為程序數量，n為需要的系統資源量

2.6 銀行家算法

死鎖有四大條件，這4個條件缺一不可：

• 互斥
• 保持和等待：各個程序會保持自己的資源并且會等待别人釋放更多的資源給自己
• 不剝奪：系統不會去把配置設定給其他程序的資源剝奪掉配置設定給某個資源
• 環路等待： A等B，B等C，C等A

  • 

• 死鎖的預防：打破四大條件
• 死鎖的避免：
  • 有序資源配置設定法
  • 銀行家算法

• 銀行家算法：配置設定資源的原則

  配置設定資源出去的時候要考慮能不能把資源按時收回來，如果仔細評估後發現收不回來，銀行家就不會放這筆資源出去。

  • 當一個程序對資源的對打需求量不超過系統中的資源數時可以接納該程序。
  • 程序可以分期請求資源，但請求的總數不能超過最大需求量
  • 當系統現有的資源不能滿足程序尚需資源數時，對程序的請求可以推遲配置設定，但總能使程序在有限的時間裡得到資源。
• 例題：

  

  • 

  • 也可以通過驗證其他選項來進行驗證，

    

3. 存儲管理

3.1 分區存儲組織

某計算機系統的記憶體大小為128k，采用可變分區配置設定方式進行記憶體配置設定，目前系統的記憶體分塊情況如下圖所示，現有作業4申請記憶體9張，幾種不同的的存儲配置設定算法在配置設定中，會産生什麼樣的結果呢

• 首次适應法：從上到下，找到能容納作業的第一個塊
• 最佳适應法：從上到下，找到能容納作業并且留下的空間的最少的塊
• 最差适應法：從上到下，找到記憶體最大的塊，就是它
• 循環首次适應法：将剩餘的塊稱為一個循環，比如第一次用25k的記憶體分塊，第二次就用28k的記憶體分塊

3.2 段頁式存儲

3.2.1 頁式存儲組織

• 把使用者程式分成等分大小的頁

• 

  • 頁面大小為4k，确定為2 ^ 12，有12位，這是2進制的，轉換成16進制，就是需要3位，也就是A29，頁号為5對應的頁幀号（實體塊号）為6，最終敲定答案為6A29H。
  • 狀态位為0說明通路的頁面不在記憶體，為1的是在記憶體中的。然後淘汰的時候就需要看通路位，通路位為1的是不能淘汰的，也就是淘汰頁号為1的。

3.2.2 段式存儲組織

3.2.3 段頁式存儲組織

3.3 快表

快表是放在cache中，慢表是放在記憶體中。

• 快表是一塊小容量的相聯存儲器（Associative Memory），由高速緩存器組成，速度快，并且可以從硬體上保證按内容并行查找，一般用來存放目前通路最頻繁的少數活動頁面的頁号。

3.4 頁面置換算法

• 最優（Optimal，OPT）算法
  • 從主存中移出永遠不再需要的頁面；如無這樣的頁面存在，則選擇最長時間不需要通路的頁面。于所選擇的被淘汰頁面将是以後永不使用的，或者是在最長時間内不再被通路的頁面，這樣可以保證獲得最低的缺頁率。
• 随機（RAND）算法
• 先進先出（FIFO）算法：有可能産生“抖動”，例如，432143543215序列，用3個頁面，比4個缺頁要少。
  • 是最簡單的頁面置換算法。這種算法的基本思想是：當需要淘汰一個頁面時，總是選擇駐留主存時間最長的頁面進行淘汰，即先進入主存的頁面先淘汰。其理由是：最早調入主存的頁面不再被使用的可能性最大。
• 最近最少使用（LRU）算法：不會”抖動“
  • 利用局部性原理，根據一個作業在執行過程中過去的頁面通路曆史來推測未來的行為。它認為過去一段時間裡不曾被通路過的頁面，在最近的将來可能也不會再被通路。是以，這種算法的實質是：當需要淘汰一個頁面時，總是選擇在最近一段時間内最久不用的頁面予以淘汰。

• 例題：

• 例題：

  

  AC

  沒有使用快表這就表示需要在記憶體中查一下表，然後在讀取

  指令是一次性讀入，隻産生一次中斷；而資料是有兩個頁，這個是需要兩次的

4. 檔案管理

4.1 索引檔案結構

位址對應盤塊，盤塊對應内容

• 由上圖可知：直接索引是4k * 13 = 54k
• 如果規定0-9前面10個節點為直接索引，一共是4k * 10 = 40k
• 第11個采取一級簡介索引：第10個節點指向的實體盤塊：一級間接索引是4k * 1024
• 二級間接索引是4k * 1024 * 1024

邏輯塊号往往是從0開始算的，一個塊中存放的是256個。

4.2 檔案和樹形目錄結構

主要考察的是相對路徑和絕對路徑的概念。

4.3 空閑存儲空間的管理

在磁盤上面會有大量的空間，我們需要把空閑的空間管理起來，以便某一個檔案想要申請相應的存儲空間的時候能夠由依據的相應的配置設定相應的存儲空間。

分為以下幾類

• 空閑區表法（空閑檔案目錄）
  • 我們用一個表來記錄哪個表是空閑的的，以便把它管理起來
• 空閑連結清單法
  • 是把這些空閑區都鍊起來，鍊成一條連結清單，需要進行空間配置設定的時候，從這條連結清單上劃出相應的空間來

• 位示圖法

  畫圖，1表示的區域已經被占用，0表示的區域表示空閑。

  

• 成組連結法
  • 成組也分鍊

5. 裝置管理

5.1 資料傳輸控制方式

主要是指的記憶體和外設之間的資料傳輸問題，解決這一問題有集中方案。分别是程式控制方式，程式中斷方式，DMA方式，通道，輸入輸出處理機。

• 程式控制方式：這是最低級的方式，也是CPU介入最多的方式，資料的傳輸控制很多時候都需要CPU的介入。就比如現在問你東西做完了嗎？你說沒有，很可能過了很長一段時間了再來問做完了嗎？你說我老早就完成了
• 程式中斷方式：如果外設完成了相應程式的資料的傳輸釋出，這個時候會發一個中斷出來，系統就會做下一步的處理。
• DMA：直接存取控制方式。有專門的DMA控制器，隻要是外設和記憶體之間的資料交換，過程之中就由這個控制器去管控，CPU隻要在開頭的時候做一個介入即可。中間由DMA來。完成之後再由CPU接手

5.2 虛裝置與SPOOLING技術

SPOOLING技術：核心在于開辟了緩存區，把輸入和輸出的資料先緩存起來，這樣就解決了外設的低速和記憶體之間的高速這樣的一個差距

6. 微核心作業系統

以上是學習過程中的學習筆記