操作系統引論

操作系統定義

操作系統是一組控制和管理計算機軟硬件資源、合理地對各類作業進行調度以及方便用戶使用的程序集合。

操作系統是位于硬件層之上，所有其它系統軟件層之下的一個系統軟件，使得管理系統中的各種軟件和硬件資源得以充分利用，方便用戶使用計算機系統。

操作系統的目標

1. 方便性
2. 有效性
3. 開放性
4. 可擴充性

操作系統的作用

1. 用戶與計算機硬件系統之間的接口處理機
2. 計算機資源的管理者
3. 擴充裸機資源的軟件
4. 計算機工作流程的組織者

無操作系統時的計算機系統

• 人工操作方式
  特點：無任何軟件、獨占性、串行性缺點：用戶獨占全機，CPU等待人工操作待解決的問題：人機矛盾，CPU和I/O設備速度不匹配解決：脫機I/O、批處理
• 脫機輸入輸出方式
  解決了CPU和設備之間不匹配的矛盾

單道批處理系統

在內存中僅存一道作業區運行，運行結束 或出錯，才自動調整另一道作業運行

1. 自動性
2. 順序性
3. 單道性

優點：減少人工操作，解決了作業的自動接續
缺點：平均周轉時間長，沒有交互能力

多道批處理系統

在內存中存放多道作業運行，運行結束或出錯，自動調度內存中的另一道作業運行

1. 多道性
2. 調度性
3. 無序性

優點：提高了CPU的利用率，提高內存和I/O設備利用率，增加系統吞吐率
缺點：平均周轉時間長，沒有交互能力

分時系統

1. 多路性
2. 獨立性
3. 及時性
4. 交互性

產生原因：用戶需要人機交互、共享主機，便于用戶上機
實現方法：簡單分時系統，前后臺分時系統，多道分時系統

實時系統

計算機及時響應外部事件的請求，在規定的時間內完成對該事件的處理，并控制所有實時設備和實時任務協調一致的運行

1. 多路性
2. 獨立性
3. 及時性
4. 交互性
5. 可靠性

操作系統的基本特征

1. 并發（最重要的特征）
2. 共享（和并發同為操作系統最基本的特征，二者互為存在的條件）
3. 虛擬（以并發和共享為前提）
4. 異步（并發和共享的必然結果）

操作系統的功能

1. 處理機管理
2. 存儲器管理
3. 文件管理
4. 設備管理
5. 提供友好的用戶接口

處理機管理

主要是對處理機的分配和運行進行管理

1. 進程控制
2. 進程同步
3. 進程通信：共享存儲器、消息、管道等。
4. 進程調度

存儲器管理

主要是對多道程序的運行提供良好的環境

1. 內存分配
2. 內存保護
3. 地址映射
4. 內存擴充

設備管理

主要是完成用戶的I/O請求

1. 緩沖管理
2. 設備分配
3. 設備處理

文件管理

主要是希望用戶能方便、安全地使用各種信息資源

1. 文件存儲空間的管理
2. 目錄管理
3. 文件的讀寫管理和保護

提供友好的用戶接口

主要是方便用戶使用計算機

1. 命令接口
2. 程序接口
3. 圖形用戶接口

操作系統的結構設計

1. 整體式系統（無結構操作系統）
   缺陷：① 設計出的操作系統既龐大又雜亂，缺乏清晰的程序結構。 ② 編制出的程序錯誤很多，給調試工作帶來很多困難；增加了維護人員的負擔
2. 模塊化結構
   優點：① 提高了OS設計的正確性、可理解性和可維護性。② 增強了0S的可適應性。 ③ 加速了OS的開發過程。缺點：① 對模塊的劃分及對接口的規定要精確描很困難 。 ② 從功能觀點來劃分模塊時，未能將共享資源和獨占資源加以區別；
3. 分層式結構
   每一層實現一組基本概念及其相關的基本屬性，各層實現不依賴其以上各層所提供的概念及其屬性，只依賴其直接下層所提供的概念及屬性，每一層對其上各層隱藏其下各層的存在
4. 微內核結構
   優點：① 增強了系統的可擴展性 ② 增強了系統的可靠性，可移植性好 ③ 提供了對分布式系統的支持缺點：運行效率有所降低（消息傳遞開銷+模式切換開銷）

進程管理

程序的順序執行

1. 順序性
2. 封閉性
3. 可再現性

程序的并發執行

1. 間斷性
2. 失去封閉性
3. 不可再現性

應用級并發是指若干應用程序的并發執行。
系統級并發是指操作系統自身軟件的并發執行。

進程

引入進程的目的是為了使程序正確地并發執行
特征：
1. 結構特征
2. 動態性（基本特征）（程序是靜態的）
3. 并發性
4. 獨立性
5. 異步性

定義：
進程是進程實體的運行過程，它是系統進行資源分配和調度的一個獨立單位。

為使程序（含數據）能獨立運行，應為之配置一個專門的數據結構即進程控制塊（PCB）
由程序段、相關的數據段和PCB三部分便構成了進程實體
創建進程 ，實質上是創建進程實體中的PCB；撤消進程 ，實質上是撤消進程的PCB

進程狀態

1. 就緒
2. 執行
3. 阻塞
4. 掛起

進程狀態轉換

就緒 - 運行：進程調度
運行 - 就緒：高優先級任務搶占，時間片用完
運行 - 阻塞：I/O請求，等待資源/事件
阻塞 - 就緒：I/O完成，得到資源/觸發事件
阻塞 - 掛起：終端用戶請求，父進程請求，負荷調節需要，操作系統需要
掛起 - 就緒：**原語

特殊狀態:
靜止就緒，靜止阻塞（上述的掛起）。
活動就緒/執行掛起得到靜止就緒，靜止就緒通過**原語得到活動就緒。
靜止阻塞通過**原語得到活動阻塞，靜止阻塞通過釋放得到靜止就緒。
狀態轉換

 

進程控制塊

為使程序（含數據）能獨立運行，應為之配置一個專門的數據結構即進程控制塊（PCB）
PCB是進程存在的唯一標志

通常包含下列信息：
1. 進程標識符：內部標識符，外部標識符
2. 處理機狀態：通用寄存器、PC、PSW、SP
3. 進程調度和控制信息

PCB的常用組織形式：線性方式、鏈接方式和索引方式。

進程同步

基本概念

1. 臨界資源：一次僅允許一個進程訪問的資源
2. 臨界區：訪問臨界資源的那段代碼

用來實現互斥的同步機制的準則

1. 空閑讓進
2. 忙則等待
3. 有限等待
4. 讓權等待

實現機制

1. 信號量機制
2. 管程

信號量機制

類型：
1. 整型信號量
2. 記錄型信號量
3. AND型信號量（要么全部分配到進程，要么一個也不分配）
4. 信號量集（在每次分配時，采用信號量集來控制，可以分配多個單位的資源）

應用：
1. 用于實現前趨關系
2. 用于實現互斥

管程

管程是由一組局部的變量對局部變量進行操作的一組過程以及對局部變量進行初始化的語句序列構成的一個軟件模塊，它可用來實現進程同步。

進程通信

• 低級通信：進程之間的互斥和同步，由于其所交換的信息量少而被歸結為低級通信
• 高級通信：是指用戶可直接利用操作系統所 提供的一組通信命令高效地傳送大量數據的 一種通信方式

進程通信的類型

常用的高級進程通信機制：
1. 共享存儲器系統
（基于共享數據結構/共享存儲區）
2. 消息傳遞系統
直接通信方式：對稱尋址方式，非對稱尋址方式
間接通信方式：信箱，消息緩沖隊列通信機制
3. 管道通信
4. 客戶機–服務器系統
套接字，遠程過程調用和遠程方法調用

線程

進程的兩個特點：資源所有權，調度/執行。調度和分派的部分通常稱為線程或輕便進程，而資源所有權的部分通常稱為進程。

屬性：
1. 輕型實體
2. 獨立調度和分派的基本單位
3. 可并發執行
4. 共享進程資源

多線程OS中的進程屬性：(1) 作為系統資源分配的單位。 (2) 可包括多個線程。 (3) 進程不是一個可執行的實體。

分類：
1. 用戶級線程，用戶級線程在用戶空間實現，無需得到內核的支持，調度算法由線程庫提供。
2. 內核支持線程，內核支持線程的TCB被它的保存在核心空間中，它的運行需獲得內核的支持。
3. （用戶級線程和核心級線程的結合，LWP）

內核支持線程

即無論 是用戶進程中的線程，還是系統進程中的線程，他們 的創建、撤消和切換等，是依靠內核實現的。
在內核空間中為每一個內核支持線程設置了一個線 程控制塊TCB，內核是根據該控制塊而感知某線程的 存在的，并對其加以控制

優點

(1) 在多處理器系統中，內核能夠同時調度同一進程中多 個線程并行執行；
(2) 如果進程中的一個線程被阻塞了，內核可以調度該進 程中的其它線程占有處理器運行，也可以運行其它進程 中的線程；
(4) 內核本身也可以采用多線程技術，可以提高系統的執 行速度和效率。

缺點

對于線程切換而言，其模式切換的開銷較大，在同一個進程中，從一個線程切換到另一個線程時 ，需要從用戶態轉到內核態進行，這是因為用戶進程的線程在用戶態運行，而線程調度和管理是 在內核實現的，系統開銷較大。

實現

在僅設置了內核支持線程的OS中，一種可能的線程控制方法是，系統在創建一個新進程時，便為它分配 一個任務數據區PTDA（Per Task Data area),其中包括若干個線程控制塊TCB空間

用戶級線程

用戶級線程僅存在于用戶空間中。對于這種線程的創建、撤消、線程之間的同步與通信等功能，都無須內核來實現。

• 由應用程序完成所有線程的管理
  通過線程庫(用戶空間)：一組管理線程的函數線程庫來 提供一個線程運行管理系統（運行系統）
• 內核不知道線程的存在
• 線程切換不需要核心態特權
• 調度算法可以是進程專用的

優點

線程切換不調用內核
調度是應用程序特定的：可以選擇最好的算法
可運行在任何操作系統上（只需要線程庫），可以在一 個不支持線程的OS上實現

缺點

大多數系統調用會引起進程阻塞，并且是進程中所有線 程將被阻塞
內核只將處理器分配給進程，同一進程中的兩個線程不 能同時運行于兩個處理器上

實現

所有用戶級線程都具有相同的數據結構，它們都運行在一個中間系統上
（1）運行時系統
是用于管理和控制線程的函數的集合，又稱為線程庫。
（2）內核控制線程

線程的同步

這種線程又稱為輕型進程LWP（Light Weight Process ）
1. 互斥鎖
2. 條件變量
3. 信號量機制

使用線程的優點

1. 在一個已有進 程 中 創 建 一 個 新 線 程 比 創 建 一 個全新進程所需的時間少。
2. 終止一個線程比終止一個進程花費的時間少 。
3. 線程間切換比進程間切換花費的時間少。
4. 線程提高了不同的執行程序間通信的效率 。同一個進程中的 線程共享存儲空間和文件，它們無需調用內核就可以互相通信。

進程同步經典問題

處理機調度和死鎖

調度的目標：
1、提高處理機的利用率
2、提高系統吞吐量
3、盡量減少進程的響應時間
4、防止進程長期得不到運行

調度方式和算法的選擇，取決于操作系統的類型及其目標。

選擇準則（面向系統）：
1. 系統吞吐量
2. 處理機利用率
3. 各類資源的平衡利用

選擇準則（面向用戶）：
1. 周轉時間
2. 響應時間
3. 截止時間的保證
4. 優先權原則

三級調度

高級調度

又稱為作業調度或長程調度，作業（JOB）是用戶在一次算題過程中或一次事務處理中，要求計算機系統所做的工作的集合 。

批處理系統需要有作業調度，分時和實時系統無需此調度

多道程序度：即允許多少個作業同時在內存中運行。
周轉時間：從作業被提交給系統開始，到作業完成為 止的這段時間間隔。
吞吐量：是指在單位時間內系統所完成的作業數

中級調度

它按一定的算法將外存中已具備運行條件的進程換入內存，而將內存中某些處于阻塞狀態的某些進程換出至外存（阻塞->掛起）。

中級調度的目的是為了解決內存緊張問題。

低級調度

又稱為進程調度或短程調度。是最基本的調度，在三種類型的操作系統中都必須配置它。（批處理、分時和實時）
分為：
1. 非搶占方式
2. 搶占方式，原則：1）優先權原則 2）短作業優先原則 3）時間片原則

三個基本原則：
（1）排隊器
（2）分派器（調度程序）
（3）上下文切換機制

低級調度的功能：
(1)按某種算法選取進程（調度）。
(2)保存處理機的現場信息（上下文切換第一步驟）
(3) 把處理器分配給進程（上下文切換第二步驟）

調度算法

先來先服務-FCFS

按照作業/進程進入系統的先后次序，遵循先進入系統者先調度。
優點：
1. 有利于長作業/進程
2. 有利于CPU繁忙型作業/進程

缺點：
1. 不利于短作業/進程，尤其是來的較晚的短作業/進程
2. 不利于I/O繁忙型作業/進程

用于批處理系統，不適于分時系統

短作業/進程優先算法-SJF/SPF

按照運行時間長短進行調度，運行時間越短越優先調度。不可搶占。
優點：
1. 能有效降低作業/進程的平均等待時間
2. 提高系統的吞吐量

缺點：
1. 不利于長作業/進程
2. 未考慮作業/進程緊迫程度，不能保證緊迫作業/進程被及時處理
3. 運行時間無法準確估計，不能真正保證短作業/進程優先
4. 無法實現人機交互

高優先權優先算法-HPF

分類：
1. 靜態優先權，簡單易行，開銷小，但是不夠精確，還可能導致低優先權作業/進程長期得不到調度
2. 動態優先權，更好的調度性能，可防止長作業/進程長期壟斷處理機

高響應比優先調度算法-HRRN

響應比/優先權=等待時間+要求服務時間要求服務時間=響應時間要求服務時間響應比/優先權=等待時間+要求服務時間要求服務時間=響應時間要求服務時間

此處的要求服務時間，準確來說是指剩余的需要服務的時間。

HRRN是介于FCFS和SJF/SPF之間的一種這種算法，相比于SJF/SPF有著更低的吞吐量和更高的系統開銷。

對短作業有利，一定程度上是先來先服務，也對長作業有利，但由于計算響應比，會增加系統開銷。

時間片輪轉算法-RR

系統將所有就緒進程按先來先服務原則排成隊列。
就緒進程直接置于隊尾，若此時正處于某一進程的時間片，該進程是位于隊首的

多級反饋隊列調度算法-FB

原理：
1. 設置多個就緒隊列，并為各個隊列賦予不同的優先級
2. 一個新進程進入內存后，首先將它放入第一隊列的末尾，按FCFS原則排隊等待調度
3. 僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行

調度過程：
1. 按優先級由高到低設置多個隊列RQ0 ，RQ1 … RQn ，高優先級隊列時間片小
2. 剛進入系統的進程按FCFS放入最高的RQ0中
3. 進程一次時間片沒執行完，就降至下一級隊列，以此類 推，降至最低優先級隊列后，一直在此隊列中不再下降
4. 系統優先調度高優先級隊列中的進程，僅當RQ0 空閑時才調度RQ1 隊列進程，以此類推
5. 如果是搶占式，當前時間片未用完時有進程進入高優先級隊列時，將當前進程置于其所在隊列的末尾，而后開始執行高優先級隊列的時間片

實時調度

常用的調度方式：
1. 非搶占式輪轉調度方式
2. 非搶占式優先權調度方式
3. 搶占式調度優先權調度方式
4. 立即搶占的優先權調度方式
由上往下，響應時間數量級逐個降低，要求更為嚴格，所需資源也更多。

常用的高優先權優先的實時調度算法：
1. 最早截止時間優先算法-EDF，截止時間越早越優先。
2. 最低松弛度優先算法-LLF，松弛度：截止時間-剩余所需時間-當前時間，主要用于可搶占調度方式，當松弛度為0時，必須立即搶占CPU。

產生死鎖的原因

1. 競爭資源
2. 進程推進順序非法

m個同類資源被n個進程共享，設一個進程最多可以請求多x個資源
m > n * (x-1) 時，系統不會發生死鎖。

產生死鎖的必要條件

1. 互斥條件
2. 請求與保持條件
3. 不剝奪條件
4. 環路等待條件

處理死鎖的基本辦法

預防死鎖

破壞死鎖必要條件的后三者之一，互斥條件因為一些資源固有特性的限制，難以破壞，對于打印機這樣的設備可以通過SPOOLing技術對互斥條件予以破壞。
1. 破壞“請求與保持”條件，規定所有進程都必須一次性申請運行過程所需的全部資源，會造成資源浪費嚴重和更多更久的進程阻塞。
2. 破壞“不剝奪”條件，規定一個已經保持了某些資源的進程，在提出新的資源請求而不能立即得到滿足時，必須釋放它已經獲得的所有資源，方法實現復雜且開銷大。
3. 破壞“環路等待“條件，將系統資源按類型賦予不同的序號，當進程要獲取多種資源時必須按序號逐個獲取資源。會限制新設備類型的增加，由于有些進程使用資源的順序與規定的順序不同，會造成資源的浪費。

避免死鎖

將系統狀態分為安全狀態和不安全狀態，安全狀態一定不會產生死鎖，不安全狀態可能會產生死鎖。
允許進程動態申請資源，系統分配資源前進行安全性檢查，若分配會導致系統進入不安全狀態，則不予以分配。

銀行家算法，根本思想：當某個進程提出資源請求，并請求資源小于等于它實際所需資源時，檢查是否存在一條路徑可以在資源分配后，剩余的進程仍然可以完全結束。
數據結構：
1. 可用資源向量 Available
2. 最大需求矩陣Max
3. 分配矩陣Allocation
4. 需求矩陣Need
5. 工作向量work
6. 工作向量Finish

死鎖的檢測與解除

系統定時進行死鎖的檢測，當判明將發生死鎖或已經發生死鎖時，進行死鎖的解除。

死鎖的檢測：
1. 判斷的現有的資源能否讓現有的進程全部正常結束，不能則認為將發生死鎖。
2. 周期性檢測進程阻塞時間，當其超過某一時間后，認為該進程為死鎖進程。

死鎖的解除：
1. 剝奪資源
2. 撤銷進程

存儲器管理

三級存儲：
1. 高速緩存cache
2. 內存RAM
3. 磁盤

五級存儲：
1. 寄存器
2. 高速緩存
3. 內存
4. 磁盤緩存
5. 磁盤

存儲分配的三種方式：
1. 直接指定
2. 靜態分配方式
3. 動態分配方式

程序的裝入

1. 絕對裝入方式
   編譯程序產生實際存儲地址（絕對地址）的目標模塊邏輯地址與實際內存地址完全相同
2. 可重定位裝入方式
   重定位（地址映射/地址變換），根據地址變換進行的時間及采用技術手段不同，分為：
3. 靜態重定位
   地址變化在裝入內存時一次完成，優點：不需要硬件支持，可以裝入有限多道程序。缺點：一個程序通常需要占用連續的內存空間，程序裝入內存后不能移動，不易實現共享。
4. 動態重定位
   地址變換在程序執行時進行，在硬件地址變換機構的支持下，對每條指令或數據的訪問自動進行地址變換。優點：主存使用更加靈活，幾個作業共享一個程序段的單個副本比較容易，可以向用戶提供一個比主存的存儲空間大得多的地址空間而用戶無需考慮覆蓋結構。缺點：需要附加硬件支持，實現存儲器管理的軟件比較復雜。
5. 動態運行時裝入方式

程序的鏈接

1. 靜態鏈接
2. 裝入時動態鏈接
3. 運行時動態鏈接

運行時動態鏈接是目前最常使用的鏈接方式

存儲器管理的目的

1. 主存儲器的分配和管理
2. 提高主存儲器的利用率
3. “擴充”主存容量
4. 存儲保護

存儲器保護

1. 自動地址修改
2. 0頁，1頁尋址
3. 界限寄存器

連續分配方式

1. 單一連續分配方式
2. 分區式分配方式
3. 可重定位分區分配

單一連續分配方式

內存中僅駐留一道用戶程序，整個用戶區為一個用戶獨 占。 ?內存分為兩個區域：系統區，用戶區。
應用程序裝入到用戶區，可使用用戶區全部空間。

分區式分配方式

算法復雜，回收分區時系統開銷大。
1. 固定分區分配
（1）分區大小不等（2）分區大小相等
建立分區說明表，內存分配程序檢索分區說明表，找出合適分區后修改分區狀態。
優點：易于實現，開銷小
缺點：內碎片造成浪費，分區總數固定，限制了并發執行的程序數目，存儲空間的利用率太低。
2. 動態分區分配
1. 分區數目固定
2. 分區數目大小均不固定

數據結構：空閑分區表 / 空閑分區鏈

分區分配算法

基于順序搜索：
1. 最佳適應算法
2. 最壞適應算法
3. 首次適應算法
4. 循環首次（下次）適應算法

基于索引搜素：
1. 快速適應算法
2. 伙伴系統

最佳適應算法

總是尋找其大小最接近作業所要求的存儲區域。即使作業放入后剩下的零頭最小。

優點：
遇到大作業到來時，作業要求的存儲區域就比較容易得到滿足。
缺點：
產生空白區較多，且空白區較小無法使用（可干脆將整個區域劃分給申請的作業。
回收分區時插入到合適的位置較為費時。

為了加快查找速度，應將存儲空間中所有的空白 區按其大小遞增的順序鏈接起來，組成一空白區鏈 (Free List)。

最壞適應算法

它在為作業選擇存儲區域時，總是尋找最大的空白區。在劃分后剩下的空白區也是最大的，因而對以后的分配很可能仍然是有用的，這是該算法的一個優點。

但是，由于最大的空白塊總是首先被分配而進行劃分，當有大的作業時，其存儲空間的申請往往得不到滿足，這是該算法的一個缺點。

為了支持這個算法的實現，空白塊應以大小遞減的順序鏈接起來。

首次適應算法

每個空白區按其在存儲空間中地址遞增的順序鏈在 一起，即每個后繼空白區的起始地址總是比前者的 大。在為作業分配存儲區域時，從這個空白區鏈的 始端開始查找，選擇第一個足以滿足請求的空白塊， 而不管它究竟有多大。
這個選擇的空白區被分成兩部分。 一部分與請求的大小相等，分配給作業；剩下的部分留在空白區鏈中。顯然，這個算法傾向于優先利用存儲空間中低址部分的空白區。

優點：
算法簡單，查找速度快，大作業到來時也比較容易得到滿足

缺點：
會留下較多無法使用的空白區，存儲空間利用率不高。較小空白區集中在前端，較大空白區在尾端，導致找到合適的空白區的速度降低。

下次適應算法

我們把存儲空間中空白區構成一個循環鏈。每次為存儲請求查找合適的分區時，總是從上次查找結束的地方開始，只要找到一個足夠大的空白區，就將它劃分后分配出去。

優點：存儲空間的利用更加均衡。

快速適應算法

將空閑分區根據其容量大小進行分類，對于每一 類具有相同容量的所有空閑分區，單獨設立一個空閑分區鏈表。

在內存中設立一張管理分區類型，并記錄 了該類型空閑分區鏈表表頭的索引表，該表的每一個表項記錄了對應類型空閑分區鏈表表頭的指針。

在內存中設立一張管理分區類型，并記錄了該類型空閑分區鏈表表頭的索引表，該表的每一個表項記錄了對應類型空閑分區鏈表表頭的指針。

優點：
查找效率高。
該算法在進行空閑分區分配時，不會對任何分區產生 分割，所以能保留大的分區，滿足對大空間的需求， 也不會產生內存碎片。（外碎片）

缺點：
在分區歸還主存時算法復雜，系統開銷較大。
該算法在分配空閑分區時是以進程為單位，一個分區 只屬于一個進程，因此在為進程所分配的一個分區中 ，或多或少地存在一定的浪費。空閑分區劃分越細， 浪費則越嚴重。（內碎片）

伙伴系統

進程請求大小為n的存儲空間時，
首先計算一個 i 值，使 2 i－1 < n ≤ 2 i ；
在空閑分區大小為 2 i 的空閑分區鏈表中查找。 if 找到，即把該空閑分區分配給進程。 else 在分區大小為2 i＋1 的空閑分區鏈表中尋找; //表明長度為2 i 的空閑分區已經耗盡 if 找到大小為2 i＋1 的空閑分區 把該空閑分區分為相等的兩個分區（一對伙 伴），其中一個用于分配，另一個加入分區大 小為 2 i 的空閑分區鏈表中。 else 查找大小為2 i＋2 的空閑分區……

哈希算法

利用哈希快速查找的優點，以及空閑分區在可利 用空間表中的分布規律，建立哈希函數，構造一 張哈希表，以空閑分區大小為關鍵字，每一個表 項記錄了一個對應的空閑分區鏈表表頭指針。

當進行空閑分區分配時，根據所需空閑分區大小， 通過哈希函數計算，即得到在哈希表中的位置， 從中得到相應的空閑分區鏈表，實現最佳分配策 略。

可重定位分區分配

緊湊

解決零頭問題的辦法，將內存中的所有作業進行移動，使它們全都相鄰接，這樣，可把原來分散的多個小分區合成一個大分區。這種技術稱為存儲器的“緊湊”。

動態重定位

在動態運行時裝入的方式中，作業裝入內存后的所有地址都仍然是相對地址，將相對地址轉換為物理地址的工作，被推遲到程序指令要真正執行時進行。

動態重定位分區分配法是利用分區的“拼接”(對空白區而言)或“緊湊”(作業程序而言)技術 解決“零頭”。

對換

對換指把內存中暫不能運行的進程或暫時不用和程序和數據，換到外存上，以騰出足夠的內存空間，把已具備運行條件的進程，或進程所需要的程序和數據，換入內存。

對換是系統行為，是提高內存的利用率的有效措施。
- 整體對換（進程對換）
- 頁面對換（分段對換）

為實現對換，系統需要三方面的功能：
對換空間的管理
進程的換入
換出

對換空間的管理

外存被分為兩部分， 文件區和對換區，文件區用于存放文件，它采取離散分配方式。 對換（續） 即一個文件可根據當前外存的使用情況 ， 被分成多塊 ，分別存儲到不鄰接的多個存儲區域中 ，用指針相連。 對換區存放從內存換出的進程 ，它們在外存的存放時間較短，換入 、換出頻繁。對對換區的管理，采用連續分配方式 。

分配算法可以是首次適應算法、循環首次適應算 法和最佳適應算法。

進程的換出和換入

1、換出（swap out）
①選擇：首先選擇阻塞或睡眠狀態的進程，若有多個，按優先級由低到高進行選擇。若沒有此狀態進程，則選擇就緒狀態的，仍然按優先級由低到高進行選擇。
②為避免某進程被頻繁的換入換出，還應考慮進程在內存中的駐留時間，優先選擇駐留時間長的進程。

2、換入（swap in）
①從 PCB集合中查找“就緒且換出”的進程，有多個，則選擇換出時間最長的。
②根據進程大小申請內存，成功則讀入，否則要先執行換出，再換入。
③若還有可換入進程，則轉向①。直至無“就緒且換出”進程或無法獲得足夠內存空間為止。

離散分配方式

程序在內存中不一定連續存放。

1）離散的基礎
• 分頁(Pages)：將程序地址空間分頁
• 分塊(Frames)：將內存空間分塊
2）離散分配的體現
• 內存一塊可以裝入程序一頁
• 連續的多個頁不一定裝入連續的多個塊中 •
注：系統中頁塊的大小是不變的。

根據離散時的基本單位不同，可分為三種：
分頁存儲管理
分段存儲管理
段頁式存儲管理

優點：沒有外零頭，僅有小于一個頁面的內零頭

分頁存儲管理

注意：
頁面或頁，是邏輯空間的概念
物理塊或頁框，是內存空間/物理空間的概念

頁表，每個進程對應 1 個頁表，描述該進程的各頁面在內存中對應的物理塊號。 包括頁號、物理塊號，存放在主存的系統專用區。（ 平時存于PCB中，要運行時才裝入PTR中）

作業表，整個系統1張，記錄作業的頁表情況，包含進程號、頁表長度、頁表始址等信息。

空閑塊表，整個系統1張，記錄主存當前空閑塊。

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ地址變換過程（非快表）

（1）根據邏輯地址,計算出頁號和頁內偏移量；
（2）從PTR中得到頁表首址，然后檢索頁表，查找指定頁面對應的頁框號；
（3）用頁框號乘以頁面大小獲得其對應的起始 地址，并將其送入物理地址的高端。
（4）將頁內偏移量送入物理地址低端，形成完整的物理地址。

快表

為了提高地址變換速度，為進程頁表設置一個專用的高速緩沖存儲器，稱為快表 TLB(Translation Lookaside Buffer)，或聯想存儲器（Associative Memory）。專門保存當前進程最近訪問過的一組頁表項。

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ地址變換過程（快表）

根據邏輯地址中的頁號 ， 查找快表中是否存在對應的頁表項。
若快表中存在該表項，稱為命中（hit），取出其中的頁框號， 加上頁內偏移量 ，計算出物理地址。
若快表中不存在該頁表項 ， 稱為命中失敗 ， 則再查找頁表， 找到邏輯地址中指定頁號對應的頁框號。 同時， 更新快表， 將該表項插入快表中。并計算物理地址.

訪問內存的有效時間 EAT

定義：從進程發出指定邏輯地址的訪問請求，經過地址變換，再到內存中找到對應的物理單元并取出數據，所花費的總時間。

多級頁表

存儲大頁表，① 采用離散分配方式來解決難以找到一塊連續的大內存空間的問題，（即引入兩級頁表），② 只將當前需要的部分頁表項調入內存， 其余的 頁表項仍駐留在磁盤上，需要時再調入。

對于要求連續的內存空間來存放頁表的問題：

可將頁表進行分頁，并離散地將各個頁面分別存放在不同的物理塊中，

同樣也要為離散分配的頁表再建立一張頁表，稱為外層頁表(Outer Page Table)，在每個頁表項中記錄了頁表分頁的物理塊號。

反置頁表

（1）IPT是為主存中的每一個物理塊建立一個頁表項并按照塊號排序；
（2）該表每個表項包含正在訪問該物理塊的進程標識、頁號及特征位,用來完成主存物理塊到訪問進程的頁號的轉換。

地址轉換過程（反置頁表）

邏輯地址給出進程標識和頁號,用它們去比較 IPT, 若整個反 置 頁表中未能找到匹配的頁表項 , 說明該頁不在主存, 產生請求調 頁中斷 , 請求操作系統調入;否則，該表項的序號便是物理塊號,塊號加上位移，便形成物理地址。

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ分頁存儲管理的優點

• 減少碎片
• 程序不必連續存放，便于裝入
• 便于管理
• 能實現動態鏈接

分頁存儲管理的缺點

• 程序必須全部裝入內存，才可以運行
• 操作系統必須為每一個任務都維護一張頁面，開銷比較大，簡單的頁面結構已經不能滿足要求，必須設計更復雜的結構，如：多級頁表結構、哈希頁表結構、反置頁表

分段式存儲管理

1. 方便編程
   模塊化程序設計的分段結構
2. 分段共享
   段是信息的邏輯單位，可以為共享過程建立一個獨立的段，更便于實現程序和數據的共享。
3. 分段保護
   對內存中的信息的保護，同樣也是對信息的邏輯單位進行保護。采用分段存儲管理，對實現保護，將是更有效和方便。
4. 動態鏈接
   程序運行時，先將主程序所對應的目標程序裝入內存并啟動運行，當運行過程中又需要調用某段時，才將該段調入內存并進行鏈接。
5. 動態增長
   在實際使用中，往往有些段，特別是數據段會隨著程序的運行不斷增大，而這種增長事先并不知曉會增長到多大，采用其它存儲管理方式是難以應付的，而分段存儲管理卻能較好的解決這一問題。

分段系統的基本原理

1. 分段
   作業地址空間按邏輯信息的完整性被劃分為若干個段；段內的地址空間是連續的。實現分段管理的關鍵在于，如何保證分段 (二維)地址空間中的一個作業在線性(一維)的存儲空間中正確運行。也就是說，如何把分段地址結構變換成線性的地址結構，和分頁管理一樣，可采用動態重定位技術，即通過地址變換機構來實現。
2. 段表
   為每個分段分配一個連續的分區，而進程中的各個段可以離散地移入內存中不同的分區中。實現從邏輯段到物理內存區的映射。每個表項（段描述子）至少有三個數據項：段長、主存起始地址和存取控制。
3. ΔΔ地址變換機構
   ①根據段表寄存器的內容找到該作業的段表地址；②利用有效地址中的段號2作為檢索段表的索引，得到該段在主存的起始地址；③將段的主存起始地址和位移量W相加， 即得訪問主存的物理地址。

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ分段存儲管理的優點

1. 沒有內碎片，外碎片可以通過內存緊縮來消除
2. 便于改變進程占用空間的大小

分段存儲管理的缺點

1. 進程全部裝入內存

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ分頁與分段的主要區別

1. 可見與不可見
   • “分頁”是系統活動，用戶無法介入，頁的大小 固定；• “分段”是用戶可見的，段大小可變。
2. 物理單位與邏輯單位
   • 頁是信息的物理單位，不是完整的邏輯單位；• 段是完整的邏輯信息單位。
3. 地址空間
   • 分頁的用戶程序地址空間是一維的，是單一線性 空間；• 分段的用戶程序地址空間是二維的。
4. 分頁是為了提高內存利用率，或者說是系統管理的需要。分段是為了更好地滿足用戶需求。
5. 分頁，用戶不關心，頁的長度由機器地址結構。分段，用戶或編輯程序確定，段的最大長度由位移量字段的位數決定。

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ信息共享

分頁系統實現段的共享比較困難
分段易于實現段的共享和段的保護

分段的共享是通過兩個作業段表的相應表目都指向 COS過程的同一物理副本來實現的

段頁式存儲管理方式

1. 分頁管理內存管理效率高
   沒有外零頭內零頭小
2. 分段管理符合模塊化思想
   每個分段都具備完整的功能方便代碼共享、保護

原理：分段和分頁相結合。

內存劃分：按頁式存儲管理方案。
內存分配：以頁為單位進行離散分配。
由于段頁式系統給作業地址空間增加了另一級結構，現在 地址空間是由段號S、段內頁號P和頁內相對地址(位移量 )W構成。

地址變換：
設置段表、段內頁表
① 首先，從段表寄存器從獲得進程段表的起始地址，根據該地址，查找進程的段表。
② 然后，根據邏輯地址指定的段號檢索段表，找到對應段的頁表起始地址。
③ 再根據邏輯地址中指定的頁號檢索該頁表， 找到對應頁所在的物理塊號。
④ 最后，用物理塊號加上邏輯地址中指定的頁內偏移量，形成物理地址。

一個段就是一個頁表

在段頁式存儲管理方式中，每訪問一 次數據，需訪問三次內存。
第一次訪問內存中的段表
第二次訪問內存中的頁表
第三次訪問相應數據。大大降低了訪問速度。
解決方法： 可以設置快表，表項應包括段號、頁號、物理 塊號。

綜合了分段和分頁技術的優點，既能有效地利用存儲空間，又能方便用戶進行程序設計。
但是，實現段頁式存儲管理系統需要增加硬件成本，系統的復雜度和管理開銷也大大增加。
因此，段頁式存儲管理技術適合于大、中型計算機系統，不太適合小型、微型計算機系統。

如何提高內存利用率

離散分配、對換機制、動態鏈接、虛擬存儲器、存儲器共享

虛擬存儲器

物理上擴充內存：
增加硬件投入，收機器自身和成本的限制

從邏輯上擴充內存：
對換技術（解決了“駐留性”問題）
覆蓋技術（解決了“一次性”問題）
虛擬存儲器技術（依據程序執行的局部性原理）

程序的執行總是局部性的，表現在時間局部性和空間局部性

定義

虛擬存儲器：是指具有請求調入功能和置換功能，能從邏輯上對內存容量加以擴充的一種存儲器系統。

限制

1. 指令中地址的字長
2. 外存的容量（對換區）

特征

1. 多次性
   多次性是指一個作業被分成多次調入內存運行。
2. 對換性
   虛擬性是以多次性和對換性為基礎的；而多次性和對換性又必須建立在離散分配的基礎上。
3. 虛擬性
   虛擬性是指能夠從邏輯上擴充內存容量，使用戶所看到的內存容量遠大于實際內存容量。

典型問題

如果系統花費大量的時間把程序和數據頻繁地換入和換出內存而不是執行用戶指令，那么，稱系統出現了抖動。出現抖動現象時，系統顯得非常繁忙， 但是吞吐量很低，甚至產出為零。

根本原因：選擇的頁面或段不恰當。

實現方式

1. 請求分頁存儲管理系統
2. 請求分段存儲管理系統
3. 請求段頁式存儲管理系統

請求分頁存儲管理系統

請求分頁存儲管理方式是在純分頁系統的基礎上，增加 了部分頁裝入、請求調頁、頁面置換功能。

實現請求頁式存儲管理系統，需要一定的硬件支持。除了需要一定容量的內存和外存對換區之外，還需要請求頁表機制、缺頁中斷機構和地址變換機構。

地址變換機制：
在純分頁系統的基礎上，為實現虛擬存儲器增加了某些功能：
某頁在外存的情況（狀態位＝0），需要增加產生和處理缺 頁中斷、請求調頁和頁面置換的功能。
訪問某頁時，還應修改其訪問位；對某頁如果執行寫操作， 還應設置修改位為1。

1. 確定最小物理塊數
   最小物理塊數：是指能保證進程正常運行所需的最少物理塊 數。若系統為某進程所分配的物理塊數少于此值時，進程將 無法運行。
2. 內存分配策略
   固定分配：指為每個進程分配固定物理塊數，進程在整個運行期間不變。局部置換：指進程運行過程中若發生缺頁，只能從進程本身所擁有的物理塊中選擇一頁換出，再調入所需頁。全局置換：指若空閑隊列已空，而又發生缺頁中斷時，從內存空間中的任意進程所擁有的物理塊中選擇一頁換出。固定分配，局部置換可變分配，全局置換可變分配，局部置換
3. 物理塊分配算法
   平均分配算法按比例分配考慮優先權的分配算法（部分）

頁面調入策略

1. 請求調頁策略
   缺頁中斷時，由系統將所缺的頁調入內存。但每次請求 只調入一頁。優點：容易實現。缺點：對外存I/O次數多，開銷較大，容易產生抖動現象。
2. 預調頁策略
   將預計不久之后會被訪問的程序或數據所在的頁面，提先調入內存。 缺頁中斷時，系統為進程裝入指定的頁面以及與之相臨的多個頁面。優點：提高調頁的I/O效率。缺點：若局部性很差，預先裝入的很多頁面不會很快被引用，并會占用大量的內存空間，反而降低系統的效率。預調頁的成功率僅約50％。常用于首次調入時，由程序員指出應該先調入的頁面。

外存要分為文件區和對換區。對換區為取得較快的速度，采用連續分配方式，且對換區所規定盤塊較大。

1. 系統擁有足夠的對換區空間，這時可以全部從對換區調入所需頁面，以提高調頁的速度。
2. 系統缺少足夠的對換區空間，這時凡是不會被修改的 文件，都直接從文件區調入；
   而當換出這些頁面時，由于它們未被修改而不必再將它 們重寫到磁盤（換出），以后再調入時，仍從文件區直 接調入。但對于那些可能被修改的部分，在將它們換出時，便須 調到對換區，以后需要時，再從對換區調入。
3. UNIX方式。
   由于與進程有關的文件都放在文件區，故凡是未運行 過的頁面，都應從文件區調入。 對于曾經運行過但又被換出的頁面，由于是被放在對換區，因此在下次調入時，應從對換區調入。

頁面置換算法

把未來不再使用的或短期內較少使用的頁面調出，通 常只能在局部性原理指導下依據過去的統計數據進行預測。 要避免“抖動”（Thrashing）（又稱顛簸）

1. 最佳置換算法
   選擇永不再用或者在最長時間內不再被訪問的頁面換出。優點：缺頁率最低，性能最好。缺點：依賴于對將來頁面訪問序列的了解，因此無法實 現。所以此算法只是一 個理想的算法，或稱為“目標”， 只能用來評價其它算法的優劣。
2. 先進先出算法
   選擇最先進入內存，即在內存中駐留時間最久的頁面換出。優點：實現簡單；缺點：不考慮程序的動態性，與進程實際運行的規律不 相適應。
3. 最近最久未使用算法
   選擇最近一段時間內最久不用的頁面予以淘汰。性能接近最佳算法。頁表的訪問字段，用以記錄自上次訪問以來所經歷的時間T。 每次都選擇現有頁面中T值最大的頁面置換。為了記錄頁面使用時間的先后關系，引入硬件支持：寄存器，為每個在內存中的頁面配置一個移位寄存器，當進程 訪問它時，將其寄存器的最高位置1。且定時信號每隔一 定時間將寄存器右移一位。 具有最小數值的寄存器所對應的頁面，就是最近最久未使用的頁面。棧，利用棧保存當前（最近）使用的各個頁面頁面號。 若棧中有該頁號則將其從原位置移出，壓入棧頂；若棧中沒有該頁號且棧滿，則將棧底頁號對應頁置換出，將新頁號壓入棧頂。
4. clock置換算法（輪轉算法）
   該算法只考慮某頁是否已經使用過，未考慮使用的時間，稱為“最近未用算法”當某頁被訪問時，其訪問位被置為1。置換算法尋找訪問位=0的頁面作為被置換頁。指針經過的訪問位為1的頁重新置0，最后指針停留在被置換頁的下一個頁。若查找一遍后沒有訪問位是0的頁面，則返隊首。

改進：考慮置換代價。選擇換出頁面時，既要是未使用過的頁面， 又要是未被修改過的頁面。把同時滿足兩條件的頁面作為首選淘汰的頁。
5. 最不常用算法
最少使用置換算法LFU（Least Frequently Used)選擇 到當前時間為止被訪問次數最少的頁面被置換。
6. 頁面緩沖算法

有效訪問時間

設內存讀寫周期為t，查找快表時間為λ，缺頁中斷處理時間為?，引入快表命中率為α，缺頁中斷率為f，則有效訪問內存時間為：

EAT=λ+αt+(1−α)[f(t+?+λ)+(1−f)(t+λ)+t]EAT=λ+αt+(1−α)[f(t+?+λ)+(1−f)(t+λ)+t]

抖動

1. 局部抖動
2. 全局抖動

產生原因：
進程分配的物理塊太少
置換算法選擇不當
全局置換使抖動傳播

消除抖動的辦法：
采取局部置換策略
基于工作集的物理塊分配策略
L=S準則
掛起若干進程

輸入輸出系統

基本功能：
• 1、隱藏物理設備的細節
• 2、與設備的無關性
• 3、提供處理機和I/O設備的利用率（并行操作）
• 4、對I/O設備進行控制（四種控制方式）
• 5、確保對設備的正確共享（設備的共享屬性）
• 6、錯誤處理

總體設計目標是高效性和通用性。
(1)I/O設備與CPU的并發性；
(2)簡單抽象、清晰而統一的接口。

I/O系統接口

1. 塊設備接口
   信息的存取以數據塊為單位，有結構設備。如磁盤
2. 流設備接口
   基本單位是字符，無結構設備。 如交互式終端、打印機。
3. 網絡通信接口

I/O設備和設備控制器

I/O系統：用于實現數據輸入、輸出及數據存儲的系統。

I/O設備

類型

(1)按設備的使用特性分類
存儲設備
輸入/輸出設備

(2)按傳輸速率分類
低速設備
中速設備
高速設備

(3)按設備的共享屬性分類
獨占設備(臨界資源 )
共享設備
虛擬設備

設備與控制器之間的接口

三種信號：
（1）數據信號：雙向，有緩存
（2）控制信號：控制器發給設備；要求其完成相 關操作
（3）狀態信號：傳送指示設備當前狀態的信號；

設備控制器

設備控制器是一個可編址的設備，可控制多個設 備并為它們編址,以實現I/O設備和計算機之間的 數據交換，減輕CPU的負擔。

設備控制器可分為控制塊設備的控制器和控制字 符設備的控制器兩類。

功能：接收CPU命令，控制I/O設備工作，解放CPU

組成：設備控制器與處理機的接口，設備控制器與設備的接口和I/O邏輯

I/O通道

是一種特殊處理機，專門負責輸入/輸出工作，具有 執行I/O指令的能力。主要目的是為了建立獨立的 I/O操作，使有關對I/O操作的組織、管理及其結束 處理也獨立于CPU。

總線系統

中斷機構和中斷處理程序

把引起中斷的事件稱為“中斷源”
對出現的事件進行處理的程序稱為 “ 中斷處理程序”

CPU在每條指令執行周期的最后時刻掃描中斷寄存器， 詢問是否有中斷信號

處理過程

中斷處理過程
–喚醒被阻塞的驅動程序進程
–保護被中斷進程CPU環境
–轉入相應的設備處理程序
–中斷處理(特性)
–恢復被中斷進程的現場

設備驅動程序

設備驅動程序功能：
(1)接收由I/O進程發來的命令和參數, 并將命令中的抽象 要求轉換為具體要求。
(2)檢查用戶I/O請求的合法性,了解I/O設備的狀態,傳遞有 關參數,設置設備的工作方式。
(3)發出I/O命令并檢查設備狀態。
(4)及時響應由控制器或通道發來的中斷請求并處理。

設備驅動程序的特點：
(1)驅動程序主要是指在請求I/O的進程與設備控制器之間 的一個通信和轉換程序。
(2)驅動程序與設備控制器和I/O設備的硬件特性緊密相關 ,因而對不同類型的設備應配置不同的驅動程序。
(3)驅動程序與I/O設備所采用的I/O控制方式緊密相關， 常用中斷驅動和DMA方式。
(4)由于驅動程序與硬件緊密相關,因而其中的一部分必須 用匯編語言書寫。
(5)驅動程序允許可重入。

設備處理方式：
(1)為每一類設備設置一個進程,專門用于執行這類設 備的I/O操作 。
(2)在整個系統中設置一個I/O進程,專門用于執行系統 中所有各類設備的I/O操作。
(3)不設置專門的設備處理進程,而只為各類設備設置 相應的設備處理程序(模塊),供用戶進程或系統進程調用

I/O控制方式：

• 程序I/O方式 (programmed I/O) CPU and Device can not work in parallel
• 中斷方式 (interrupt) CPU and device can work in parallel, too many interrupts for CPU
  中斷I/O比程序I/O方式高效，但以字/字節為傳輸單位。 每完成一個字/字節的傳輸，設備均要向CPU請求一次中斷
• 直接存儲器訪問方式 (DMA) DMA controller in charge of block i/o
  數據傳輸的基本單位是數據塊DMA控制器的組成： 1. 主機與DMA控制器的接口； 2. DMA控制器與塊設備的接口； 3. I/O控制邏輯。
• 通道方式 (channel)
  CPU僅在I/O操作的開始和結束時花費少量時間處理與I/O 有關的工作。實現CPU、通道和I/O設備三者的并行操作，從而更有效 地提高整個系統的資源利用率

設備獨立性

含義：應用程序獨立于具體使用的物理設備，即是指用 戶在編程序時所使用的設備與實際設備無關。

引入邏輯設備和物理設備這兩個概念。
在應用程序中,使用邏輯設備名稱來請求使用某類設備;而系統在實際執行時,還必須使用物理設備名稱。

設備獨立性的優點
(1)設備分配時的靈活性
(2)易于實現I/O重定向

設備獨立性軟件主要功能：
(1)執行所有設備的公有操作
(2)向用戶層(或文件層)軟件提供統一接口

設備分配

（1）設備控制表DCT
（2）控制器控制表、通道控制表和系統設備表

虛擬設備是利用某種技術把獨占設備改造成可由多個進程共享的設備。

用戶層的I/O軟件

用戶程序通過調用對應的庫函數使用系統調用。

SPOOLing技術將一臺物理I/O設備虛擬為多臺邏輯I/O 設備，同樣允許多個用戶共享一臺物理I/O設備。
(1)脫機輸入、輸出技術
(2) 在主機的直接控制下，實現脫機輸入、輸出功能，此時的外圍操作與CPU對數據的處理同時進行。

SPOOLing技術

SPOOLing技術將一臺物理I/O設備虛擬為多臺邏輯I/O 設備，同樣允許多個用戶共享一臺物理I/O設備。

組成

輸入井和輸出井
輸入緩沖區和輸出緩沖區(內存中)
輸入進程SPi 和輸出進程SP0
井管理程序

輸出：（打印） a.進程n請求——>SPo為進程n在輸出井中分配空間——> 將數據由進程緩沖區轉到輸出井——>生成一打印請求 表掛打印請求隊列。 b.打印機空——>查打印請求表中的任務——> 取輸出井 中對應的數據——>輸出緩沖區——>打印

緩沖區管理

(1)緩和CPU與I/O設備間速度不匹配的矛盾。
(2)減少對CPU的中斷頻率,放寬對CPU中斷響應 時間的限制。
(3)解決數據粒度不匹配的問題。
(4)提高CPU和I/O設備之間的并行性。

提前讀，延后寫，操作系統中介紹的都是軟件緩沖區

單緩沖

一個緩沖區，CPU 和外設輪流使用， 一方處理完之后接著等待對方處理

C和T可并行，M和C或M和T不能并行，因此處理一塊數據時間：Max(C,T)+M
（C為工作區處理數據，M為緩沖區傳送到工作區，T為I/O設備輸入到緩沖區）

雙緩沖

兩個緩沖區，CPU和外設都可以連續處理而無需等待對方。要求CPU和外設的速度相近。

• 效率有所提高，且進一步平滑了傳輸峰值。
• 系統處理一塊數據的時間約為：MAX(C,T) • 收發可雙向同時傳送。

循環緩沖

增加緩沖區的數量以改善系統性能，這就是多緩沖區方式。
多個I/O緩沖區常常被組織成一個環形隊列，稱為循環緩沖。

緩沖池

上述三種緩沖區的組織形式僅適用于某種特定的 I/O進程和計算進程，屬于專用緩沖。
為了提高緩沖區的利用率，可以采用公共緩沖池
其中的緩沖區可為多個設備和進程服務

兩種緩沖池：分別用于塊型設備和字符型設備。

公用緩沖池，含有以下三種類型的緩沖區： ①空(閑)緩沖區； ②裝滿輸入數據的緩沖區； ③裝滿輸出數據的緩沖區。

為了管理上的方便，可將相同類型的緩沖區鏈成 一個隊列，于是可形成以下三個隊列：
（1）空緩沖隊列emq。 這是由空緩沖區所鏈成的隊列。
（2）輸入隊列inq。 這是由裝滿輸入數據的緩沖區所鏈成的隊列。
（3）輸出隊列outq 這是由裝滿輸出數據的緩沖區所鏈成的隊列。

磁盤存儲器的性能和調度

1、數據組織和格式：
•磁道號——磁頭號——扇區——字節

2、類型
1）固定頭磁盤： –每個磁道上有一個磁頭，快
2）移動頭磁盤： –每個盤面僅有一個磁頭，慢

• 信息記錄在磁道上，多個盤片，正反兩面都用來記 錄信息，每面一個磁頭
• 所有盤面中處于同一磁道號上的所有磁道組成一個 柱面
• 每個扇區大小為600字節（數據512字節）
• 物理地址形式： –柱面號 –磁頭號 –扇區號

訪問過程

由三個動作組成：
– 尋道 ：磁頭移動定位 到指定磁道
– 旋轉延遲：等待指定 扇區從磁頭下旋轉經過
– 數據傳輸：數據在磁 盤與內存之間的實際傳輸

磁盤訪問時間

磁盤訪問時間：
1）尋道時間：TS=m∗n+sTS=m∗n+s m：常量，n：磁道數，s：磁臂啟動時間。 對一般的磁盤， 其尋道時間將隨尋道距離的增加而 增大， 大體上是5-30 ms。
2）旋轉延遲時間： 指定扇區旋轉到磁頭下所需時間。 設每秒r轉，則Tr＝1/2rTr＝1/2r（均值） 對于7200轉/分，平均延遲時間為4.2ms
3）數據傳輸時間：Tt＝b/rNTt＝b/rN b：讀寫字節數 N：每道上的字節數

訪問時間：Ta=Ts+1/2r+b/rNTa=Ts+1/2r+b/rN

磁盤調度算法

• 先來先服務FCFS
  • 按訪問請求到達的先后次序服務• 優點：簡單，公平；• 缺點：效率不高，相鄰兩次請求可能會造成 最內到最外的柱面尋道，使磁頭反復移動， 增加了服務時間，對機械也不利
• 最短尋道時間優先SSTF
  優先選擇距當前磁頭最近的訪問請求進行服務，主要考慮尋道優先• 優點：改善了磁盤平均服務時間；• 缺點：造成某些訪問請求長期等待得不到 服務對 SSTF 算 法 略 加 修 改 后 所 形 成 的 SCAN 算法， 即可防止老進程出現“饑餓”現象。
• 掃描算法SCAN
  克服了最短尋道優先的缺點，既考慮了距離，同時 又考慮了方向當設備無訪問請求時，磁頭不動； 當有訪問請求時，磁頭按一個方向移動，在移動過程中對遇到的訪問請求進行服務，然后判斷該方向上是否還有訪問請求，如果有則繼續掃描； 否則改變移動方向，并為經過的訪問請求服務，如此反復當磁頭剛從里向外移動而越過了某一磁道時，恰好又 有一進程請求訪問此磁道，這時，該進程必須等待， 待磁頭繼續從里向外，然后再從外向里掃描完所有要 訪問的磁道后，才處理該進程的請求，致使該進程的 請求被大大地推遲。為了減少這種延遲，推出CSCAN 算法，規定磁頭單向移動。• 優點： SCAN 算法既能獲得較好的尋道性能，又能防止“饑餓” 現象，故被廣泛用于大、中、小型機器和網絡中的磁盤 調度。• 問題： –當磁頭剛從里向外移動而越過了某一磁道時，恰好又 有一進程請求訪問此磁道，這時，該進程必須等待， 待磁頭繼續從里向外，然后再從外向里掃描完所有要 訪問的磁道后，才處理該進程的請求，致使該進程的 請求被大大地推遲。 –為了減少這種延遲，推出CSCAN 算法，規定磁頭單向 移動。
• 循環掃描算法CSCAN
  • 電梯算法杜絕了饑餓，但當請求對磁道的分布是 均勻時，磁頭回頭，近磁頭端的請求很少（因為 磁頭剛經過），而遠端請求較多，這些請求等待 時間要長一些。• 總是自里向外移動。移動臂到達最后個一個柱面 后，立即帶動讀寫磁頭快速返回到最里的欲訪問 磁道。返回時不為任何的等待訪問者服務。返回 后可再次進行掃描

有一個或幾個進程對某一磁道有較高的訪 問頻率， 即這個(些)進程反復請求對某一磁道的I/O操作，從而壟斷了整個磁盤設備。 我們把這一現象稱為“磁臂粘著”(Armstickiness)。

實際系統相當普遍采用最短尋道時間優先算法， 因為它簡單有效，性價比好。

磁盤高速緩存

…

文件管理

文件系統的功能：
有效地管理文件的存儲空間；
管理文件目錄；
完成文件的讀/寫操作；
實現文件共享與保護；
為用戶提供交互式命令接口和程序調用接口。

文件系統

定義：
操 作 系 統 中 的 各 類 文件、 管 理 文 件 的 軟件， 以 及 管 理 文 件 所 涉 及 到 的 數據結 構等信息的集合

文件系統模型

分為三個層次：
1. 文件系統接口
2. 對對象操縱和管理的軟件集合
3. 對象及其屬性

文件類型

1. 用途
   系統文件用戶文件庫文件
2. 文件中的數據形式
   源文件目標文件可執行文件
3. 存取控制屬性
   只執行文件只讀文件讀寫文件
4. 組織形式和處理方式
   普通文件目錄文件特殊文件

文件的邏輯結構與訪問

對于任何一個文件，都存在著以下兩種形式的結構：
文件的邏輯結構(File Logical Structure),又稱 為文件組織，是用戶可以直接處理的數據及其 結構。
文件的物理結構， 又稱為文件的存儲結構， 是指文件在外存上的存儲組織形式。

文件邏輯結構的類型

1. 有結構文件 記錄有定長和不定長兩種
   1）順序文件：按某種順序排列的定長紀錄文件
   2）索引文件：按索引表查詢的不定長紀錄文件
   3）索引順序文件：以上兩者的結合
2. 無結構文件
   其長度以字節為單位。 可以把流式文件看作是記錄式文件的一個特例。

順序文件

第一種是串結構， 各記錄之間的順序與關鍵字無關。 通常的辦法是由時間來決定，即按存入時間的先后排列。

第二種情況是順序結構，指文件中的所有記錄按關鍵字 (詞)排列。是最常用的文件組織方式。

順序文件的優缺點
常 用 于 批 量 數 據 處 理 ， 這 時 文 件 的 訪 問 效 率最高。
是唯一、 同 時 適 合 在 磁 盤 和 磁 帶 中 存 儲 的 文件。
訪問效率比堆文件高。當文件較小，可以將文件全部裝入內存，利用某種快速的查找算法，如折半查找法、插值查找法等快 速查找指定的記錄。

索引文件

可為變長記錄文件建立一張索引表，對主文件中的每個記錄，在索引表中設有一個相應的表項， 用于記錄該記錄的長度L及指向該記錄的指針(指 向該記錄在邏輯地址空間的首址)。
由于索引表是按記錄鍵排序的，因此，索引表本身是一個定長記錄的順序文件，從而也就可以方便地實現直接存取。

索引順序文件

將順序文件中的所有記錄分為若干個組(例 如，50 個記錄為一個組)；
為順序文件建立一張索引表.
在索引表中為每組中的第一個記錄建立一 個索引項，其中含有該記錄的鍵值和指向該記錄的指針。

直接和哈希文件

直接文件
對于直接文件，則可根據給定的關鍵字值，直 接獲得指定記錄的物理地址。
關鍵字值本身就決定了記錄的物理地址。
這種由關鍵字值到記錄物理地址的轉換被稱為鍵值轉換。

文件目錄

文件目錄也是一種數據結構，用于標識系統中的 文件及其物理地址，供檢索時使用。

文件控制塊（FCB）

文件控制塊是操作系統為管理文件而設置的數據結構，存放了管理文件所需的所有信息（文件屬性）
1）基本信息類
文件名：文件標識符；
物理位置：存放文件的設備名 起始盤塊號 文件長度（盤塊數或字節數）
邏輯結構：有結構文件、無結構文件
物理結構：順序文件、鏈式文件、索引文件
2）存取控制信息類
文件主的存取權限
核準用戶的存取權限
一般用戶的存取權限
3）使用信息類
文件的建立日期和時間
文件上一次修改的日期和時間
當前使用信息（進程數、是否修改等）

文件目錄：把所有的FCB組織在一起，就構成 了文件目錄，即文件控制塊的有序集合。
目錄項：構成文件目錄的項目（目錄項就是 FCB）
目錄文件：為了實現對文件目錄的管理，通常將文件目錄以文件的形式保存在外存，這個文件就叫目錄文件。

索引結點

將文件的描述信息單獨形成稱為索引結點的數據結構，即 i 結點

1. 磁盤索引節點
   指存放在磁盤上的索引結點包括：文件主標識符文件類型文件存取權限文件物理地址文件長度文件鏈接計數文件存取時間
2. 內存索引節點
   指存放在內存的索引結點比磁盤索引節點增加了：索引結點編號狀態訪問計數文件所屬文件系統的邏輯設備號鏈接指針

目錄結構

1. 單級目錄結構
2. 二級目錄結構
   主文件目錄（MFD）用戶文件目錄（UFD）
3. 樹型目錄結構
   把三級或三級以上的目錄結構稱樹型目錄優點：層次結構清晰，便于管理和保護，有利于文件分類，解決重名問題，提高文件檢索速度，能進行存取權限的控制缺點：查找一個文件按路徑名逐層檢查，由于 每個文件都放在外存，多次訪盤影響速度

目錄查詢技術

查詢目錄有兩種方法：
線性檢索法
Hash 方法

文件共享

實現文件共享的方式：
基于索引結點的共享方式
利用符號鏈實現文件共享

利用URL實現文件共享

文件保護

存取控制機制
系統容錯技術（第八章）
后備系統（第八章）

存取控制機制

保護域
訪問矩陣
訪問矩陣的修改
訪問矩陣的實現
分級安全管理

磁盤存儲器的管理

外存的組織方式

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ連續分配

連續分配(Continuous Allocation)要求為每一 個文件分配一組相鄰接的盤塊。一組盤塊的地址 定義了磁盤上的一段線性地址。

把邏輯文件中的數據順序地存儲到物理上鄰接的各個數據塊中，這樣形成的物理文件可以進行順序存取。

連續分配的主要優點：
順序訪問容易。
順序訪問速度快。
連續分配的主要缺點：
要求有連續的存儲空間。
必須事先知道文件的長度。
不能靈活地插入和刪除記錄
不適應動態增長的文件

該 分 配 方 案 可 能 會 導 致 磁 盤 碎 片 ， 嚴 重 降 低外存空間的利用率。
解 決 方 法 之 一 ， 系 統 定 期 或 不 定 期 采 用 緊 湊 技術， 將 小 分 區 合 并 為 大 的 、 連 續 分 區 ， 將文件占用空間合并在一起。

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ鏈接分配

如果在將一個邏輯文件存儲到外存上時，并不要 求為整個文件分配一塊連續的空間，而是可以將 文件裝到多個離散的盤塊中。

采用鏈接分配方式時，可通過在每個盤塊上的鏈接指針，將同屬于一個文件的多個離散的盤塊鏈接成一個鏈表，把這樣形成的物理文件稱為鏈接文件。

1. 隱式鏈接
2. 顯式鏈接

問題：
(1) 不能支持高效的直接存取
(2) FAT需占用較大的內存空間

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ索引分配

1. 單級索引分配
2. 兩級索引分配

設文件系統采用兩級索引分配方式，如果每個盤塊的大小為1KB，每個盤塊號占4B，則單個文件的最大長度是多少？ 解：1個盤塊可有1KB/ 4B=256個索引項，則兩級索引下單個文件最大長度： 256*256*1KB=64MB

文件存儲空間的管理

存儲空間的基本分配單位是磁盤塊。
其分配方法與內存的分配有許多相似之處，即同樣可采取連續分配方式或離散分配方式。

動態跟蹤磁盤上的空閑塊數目和塊號，形成空閑塊登記表。
空閑塊登記表是盤塊分配和回收的依據。
空閑塊登記表有四種實現方案：

• 空閑表
  系統為外存上的所有空閑區建立一張空閑表， 每個空閑區對應于一個空閑表項適合于可變大小分區的連續分配方式
• 空閑鏈表
  這種空閑空間組織方法適合于非連續存儲文件。空閑盤塊鏈：將磁盤上的所有空閑空間，以盤塊為單位拉成一條鏈。空閑盤區鏈：將磁盤上的所有空閑盤區(每個盤區可包含若干個盤塊)拉成一條鏈。
• 位示圖法
  利用二進制位0、1表示存儲空間中存儲塊的使用狀態盤塊的分配：順序掃描位示圖，從中找出一個值為“0”的二進制位（空閑位），將所找到的空閑位號轉換成與之相應的空閑塊號： b=n*(i-1)+j b為對應的空閑塊的塊號 n為位示圖中每行的位數 i、j分別為空閑位在位示圖的行號、列號，修改位示圖：令map[i,j]＝1盤塊的回收：將回收盤塊的盤塊號轉換成位示圖中的行 號和列號 i=(b-1)DIV n+1 j=(b-1)MOD n+1，修改位示圖：令 map [i,j]＝0
• 成組鏈接法

操作系統接口

• 用戶接口
  聯機用戶接口脫機用戶接口
• 程序接口
  又稱應用編程接口API，允許運行程序調用操作系統的服務和功能。程序接口由一組系統調用（SystemCall)） 組成，用戶程序使用“系統調用”就可獲得操作系統的底層服務，使用或訪問系統的各種軟硬件資源。庫函數的目的是隱藏訪管指令細節， 使系統調用更象過程調用，但一般地說，庫函數屬于用戶程序而非系 統程序。

聯機命令接口

分時系統或個人計算機中，操作系統 向用戶提供了一組聯機命令，用戶可以 通過終端鍵入命令，以取得操作系統的 服務，并控制自己作業的運行，這樣的 接口稱為聯機命令接口 。

聯機命令接口應由終端處理程序、命令解釋程序及一組聯機命令構成。

Shell命令語言

Shell是UNIX與用戶的交互接口,是操作系統的最外層,稱為外殼
Shell既是一種命令語言,也是一種程序設計語言
Shell不是UNIX的核心程序,運行在用戶態

系統調用

系統調用指系統為用戶程序調用操作系統所提供的子程序。 它與一般的函數調用不同，系統調用是通過中斷方式轉向相應子程序的，它工作在核心態 （即特權方式），而一般函數調用，仍僅在用戶態下的地址轉移 。

系統調用與一般過程調用的區別：

1. 運行在不同的系統狀態
   一般過程調用，其調用程序和被調用程序 都運行在相同狀態：核心態或用戶態系統調用：調用程序在用戶態，被調用程 序在系統態
2. 狀態的轉換
3. 返回問題
   一般過程調用在被調用過程執行完后，回調用過程。搶占式調度的系統中，被調用過程執行完后，系統將對所有要求運行的進程進行優先級分析。如果調用進程仍有最高優先級，則返回到調用進程執行，否則，引起重新調度，讓優先級最高的進程 優先執行。此時，系統把調用進程放入就緒隊列。
4. 嵌套調用
   系統調用也允許嵌套調用，即在一被調用過程執行期間，可再利用系統調用命令調用另一系統調用，最大深度為