操作系統(tǒng)引論

操作系統(tǒng)定義

操作系統(tǒng)是一組控制和管理計(jì)算機(jī)軟硬件資源、合理地對(duì)各類(lèi)作業(yè)進(jìn)行調(diào)度以及方便用戶使用的程序集合。

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

操作系統(tǒng)的目標(biāo)

1. 方便性
2. 有效性
3. 開(kāi)放性
4. 可擴(kuò)充性

操作系統(tǒng)的作用

1. 用戶與計(jì)算機(jī)硬件系統(tǒng)之間的接口處理機(jī)
2. 計(jì)算機(jī)資源的管理者
3. 擴(kuò)充裸機(jī)資源的軟件
4. 計(jì)算機(jī)工作流程的組織者

無(wú)操作系統(tǒng)時(shí)的計(jì)算機(jī)系統(tǒng)

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

單道批處理系統(tǒng)

在內(nèi)存中僅存一道作業(yè)區(qū)運(yùn)行，運(yùn)行結(jié)束 或出錯(cuò)，才自動(dòng)調(diào)整另一道作業(yè)運(yùn)行

1. 自動(dòng)性
2. 順序性
3. 單道性

優(yōu)點(diǎn)：減少人工操作，解決了作業(yè)的自動(dòng)接續(xù)
缺點(diǎn)：平均周轉(zhuǎn)時(shí)間長(zhǎng)，沒(méi)有交互能力

多道批處理系統(tǒng)

在內(nèi)存中存放多道作業(yè)運(yùn)行，運(yùn)行結(jié)束或出錯(cuò)，自動(dòng)調(diào)度內(nèi)存中的另一道作業(yè)運(yùn)行

1. 多道性
2. 調(diào)度性
3. 無(wú)序性

優(yōu)點(diǎn)：提高了CPU的利用率，提高內(nèi)存和I/O設(shè)備利用率，增加系統(tǒng)吞吐率
缺點(diǎn)：平均周轉(zhuǎn)時(shí)間長(zhǎng)，沒(méi)有交互能力

分時(shí)系統(tǒng)

1. 多路性
2. 獨(dú)立性
3. 及時(shí)性
4. 交互性

產(chǎn)生原因：用戶需要人機(jī)交互、共享主機(jī)，便于用戶上機(jī)
實(shí)現(xiàn)方法：簡(jiǎn)單分時(shí)系統(tǒng)，前后臺(tái)分時(shí)系統(tǒng)，多道分時(shí)系統(tǒng)

實(shí)時(shí)系統(tǒng)

計(jì)算機(jī)及時(shí)響應(yīng)外部事件的請(qǐng)求，在規(guī)定的時(shí)間內(nèi)完成對(duì)該事件的處理，并控制所有實(shí)時(shí)設(shè)備和實(shí)時(shí)任務(wù)協(xié)調(diào)一致的運(yùn)行

1. 多路性
2. 獨(dú)立性
3. 及時(shí)性
4. 交互性
5. 可靠性

操作系統(tǒng)的基本特征

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

操作系統(tǒng)的功能

1. 處理機(jī)管理
2. 存儲(chǔ)器管理
3. 文件管理
4. 設(shè)備管理
5. 提供友好的用戶接口

處理機(jī)管理

主要是對(duì)處理機(jī)的分配和運(yùn)行進(jìn)行管理

1. 進(jìn)程控制
2. 進(jìn)程同步
3. 進(jìn)程通信：共享存儲(chǔ)器、消息、管道等。
4. 進(jìn)程調(diào)度

存儲(chǔ)器管理

主要是對(duì)多道程序的運(yùn)行提供良好的環(huán)境

1. 內(nèi)存分配
2. 內(nèi)存保護(hù)
3. 地址映射
4. 內(nèi)存擴(kuò)充

設(shè)備管理

主要是完成用戶的I/O請(qǐng)求

1. 緩沖管理
2. 設(shè)備分配
3. 設(shè)備處理

文件管理

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

1. 文件存儲(chǔ)空間的管理
2. 目錄管理
3. 文件的讀寫(xiě)管理和保護(hù)

提供友好的用戶接口

主要是方便用戶使用計(jì)算機(jī)

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

操作系統(tǒng)的結(jié)構(gòu)設(shè)計(jì)

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

進(jìn)程管理

程序的順序執(zhí)行

1. 順序性
2. 封閉性
3. 可再現(xiàn)性

程序的并發(fā)執(zhí)行

1. 間斷性
2. 失去封閉性
3. 不可再現(xiàn)性

應(yīng)用級(jí)并發(fā)是指若干應(yīng)用程序的并發(fā)執(zhí)行。
系統(tǒng)級(jí)并發(fā)是指操作系統(tǒng)自身軟件的并發(fā)執(zhí)行。

進(jìn)程

引入進(jìn)程的目的是為了使程序正確地并發(fā)執(zhí)行
特征：
1. 結(jié)構(gòu)特征
2. 動(dòng)態(tài)性（基本特征）（程序是靜態(tài)的）
3. 并發(fā)性
4. 獨(dú)立性
5. 異步性

定義：
進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過(guò)程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。

為使程序（含數(shù)據(jù)）能獨(dú)立運(yùn)行，應(yīng)為之配置一個(gè)專(zhuān)門(mén)的數(shù)據(jù)結(jié)構(gòu)即進(jìn)程控制塊（PCB）
由程序段、相關(guān)的數(shù)據(jù)段和PCB三部分便構(gòu)成了進(jìn)程實(shí)體
創(chuàng)建進(jìn)程 ，實(shí)質(zhì)上是創(chuàng)建進(jìn)程實(shí)體中的PCB；撤消進(jìn)程 ，實(shí)質(zhì)上是撤消進(jìn)程的PCB

進(jìn)程狀態(tài)

1. 就緒
2. 執(zhí)行
3. 阻塞
4. 掛起

進(jìn)程狀態(tài)轉(zhuǎn)換

就緒 - 運(yùn)行：進(jìn)程調(diào)度
運(yùn)行 - 就緒：高優(yōu)先級(jí)任務(wù)搶占，時(shí)間片用完
運(yùn)行 - 阻塞：I/O請(qǐng)求，等待資源/事件
阻塞 - 就緒：I/O完成，得到資源/觸發(fā)事件
阻塞 - 掛起：終端用戶請(qǐng)求，父進(jìn)程請(qǐng)求，負(fù)荷調(diào)節(jié)需要，操作系統(tǒng)需要
掛起 - 就緒：**原語(yǔ)

特殊狀態(tài):
靜止就緒，靜止阻塞（上述的掛起）。
活動(dòng)就緒/執(zhí)行掛起得到靜止就緒，靜止就緒通過(guò)**原語(yǔ)得到活動(dòng)就緒。
靜止阻塞通過(guò)**原語(yǔ)得到活動(dòng)阻塞，靜止阻塞通過(guò)釋放得到靜止就緒。
狀態(tài)轉(zhuǎn)換

 

進(jìn)程控制塊

為使程序（含數(shù)據(jù)）能獨(dú)立運(yùn)行，應(yīng)為之配置一個(gè)專(zhuān)門(mén)的數(shù)據(jù)結(jié)構(gòu)即進(jìn)程控制塊（PCB）
PCB是進(jìn)程存在的唯一標(biāo)志

通常包含下列信息：
1. 進(jìn)程標(biāo)識(shí)符：內(nèi)部標(biāo)識(shí)符，外部標(biāo)識(shí)符
2. 處理機(jī)狀態(tài)：通用寄存器、PC、PSW、SP
3. 進(jìn)程調(diào)度和控制信息

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

進(jìn)程同步

基本概念

1. 臨界資源：一次僅允許一個(gè)進(jìn)程訪問(wèn)的資源
2. 臨界區(qū)：訪問(wèn)臨界資源的那段代碼

用來(lái)實(shí)現(xiàn)互斥的同步機(jī)制的準(zhǔn)則

1. 空閑讓進(jìn)
2. 忙則等待
3. 有限等待
4. 讓權(quán)等待

實(shí)現(xiàn)機(jī)制

1. 信號(hào)量機(jī)制
2. 管程

信號(hào)量機(jī)制

類(lèi)型：
1. 整型信號(hào)量
2. 記錄型信號(hào)量
3. AND型信號(hào)量（要么全部分配到進(jìn)程，要么一個(gè)也不分配）
4. 信號(hào)量集（在每次分配時(shí)，采用信號(hào)量集來(lái)控制，可以分配多個(gè)單位的資源）

應(yīng)用：
1. 用于實(shí)現(xiàn)前趨關(guān)系
2. 用于實(shí)現(xiàn)互斥

管程

管程是由一組局部的變量對(duì)局部變量進(jìn)行操作的一組過(guò)程以及對(duì)局部變量進(jìn)行初始化的語(yǔ)句序列構(gòu)成的一個(gè)軟件模塊，它可用來(lái)實(shí)現(xiàn)進(jìn)程同步。

進(jìn)程通信

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

進(jìn)程通信的類(lèi)型

常用的高級(jí)進(jìn)程通信機(jī)制：
1. 共享存儲(chǔ)器系統(tǒng)
（基于共享數(shù)據(jù)結(jié)構(gòu)/共享存儲(chǔ)區(qū)）
2. 消息傳遞系統(tǒng)
直接通信方式：對(duì)稱(chēng)尋址方式，非對(duì)稱(chēng)尋址方式
間接通信方式：信箱，消息緩沖隊(duì)列通信機(jī)制
3. 管道通信
4. 客戶機(jī)–服務(wù)器系統(tǒng)
套接字，遠(yuǎn)程過(guò)程調(diào)用和遠(yuǎn)程方法調(diào)用

線程

進(jìn)程的兩個(gè)特點(diǎn)：資源所有權(quán)，調(diào)度/執(zhí)行。調(diào)度和分派的部分通常稱(chēng)為線程或輕便進(jìn)程，而資源所有權(quán)的部分通常稱(chēng)為進(jìn)程。

屬性：
1. 輕型實(shí)體
2. 獨(dú)立調(diào)度和分派的基本單位
3. 可并發(fā)執(zhí)行
4. 共享進(jìn)程資源

多線程O(píng)S中的進(jìn)程屬性：(1) 作為系統(tǒng)資源分配的單位。 (2) 可包括多個(gè)線程。 (3) 進(jìn)程不是一個(gè)可執(zhí)行的實(shí)體。

分類(lèi)：
1. 用戶級(jí)線程，用戶級(jí)線程在用戶空間實(shí)現(xiàn)，無(wú)需得到內(nèi)核的支持，調(diào)度算法由線程庫(kù)提供。
2. 內(nèi)核支持線程，內(nèi)核支持線程的TCB被它的保存在核心空間中，它的運(yùn)行需獲得內(nèi)核的支持。
3. （用戶級(jí)線程和核心級(jí)線程的結(jié)合，LWP）

內(nèi)核支持線程

即無(wú)論 是用戶進(jìn)程中的線程，還是系統(tǒng)進(jìn)程中的線程，他們 的創(chuàng)建、撤消和切換等，是依靠?jī)?nèi)核實(shí)現(xiàn)的。
在內(nèi)核空間中為每一個(gè)內(nèi)核支持線程設(shè)置了一個(gè)線 程控制塊TCB，內(nèi)核是根據(jù)該控制塊而感知某線程的 存在的，并對(duì)其加以控制

優(yōu)點(diǎn)

(1) 在多處理器系統(tǒng)中，內(nèi)核能夠同時(shí)調(diào)度同一進(jìn)程中多 個(gè)線程并行執(zhí)行；
(2) 如果進(jìn)程中的一個(gè)線程被阻塞了，內(nèi)核可以調(diào)度該進(jìn) 程中的其它線程占有處理器運(yùn)行，也可以運(yùn)行其它進(jìn)程 中的線程；
(4) 內(nèi)核本身也可以采用多線程技術(shù)，可以提高系統(tǒng)的執(zhí) 行速度和效率。

缺點(diǎn)

對(duì)于線程切換而言，其模式切換的開(kāi)銷(xiāo)較大，在同一個(gè)進(jìn)程中，從一個(gè)線程切換到另一個(gè)線程時(shí) ，需要從用戶態(tài)轉(zhuǎn)到內(nèi)核態(tài)進(jìn)行，這是因?yàn)橛脩暨M(jìn)程的線程在用戶態(tài)運(yùn)行，而線程調(diào)度和管理是 在內(nèi)核實(shí)現(xiàn)的，系統(tǒng)開(kāi)銷(xiāo)較大。

實(shí)現(xiàn)

在僅設(shè)置了內(nèi)核支持線程的OS中，一種可能的線程控制方法是，系統(tǒng)在創(chuàng)建一個(gè)新進(jìn)程時(shí)，便為它分配 一個(gè)任務(wù)數(shù)據(jù)區(qū)PTDA（Per Task Data area),其中包括若干個(gè)線程控制塊TCB空間

用戶級(jí)線程

用戶級(jí)線程僅存在于用戶空間中。對(duì)于這種線程的創(chuàng)建、撤消、線程之間的同步與通信等功能，都無(wú)須內(nèi)核來(lái)實(shí)現(xiàn)。

• 由應(yīng)用程序完成所有線程的管理
  通過(guò)線程庫(kù)(用戶空間)：一組管理線程的函數(shù)線程庫(kù)來(lái) 提供一個(gè)線程運(yùn)行管理系統(tǒng)（運(yùn)行系統(tǒng)）
• 內(nèi)核不知道線程的存在
• 線程切換不需要核心態(tài)特權(quán)
• 調(diào)度算法可以是進(jìn)程專(zhuān)用的

優(yōu)點(diǎn)

線程切換不調(diào)用內(nèi)核
調(diào)度是應(yīng)用程序特定的：可以選擇最好的算法
可運(yùn)行在任何操作系統(tǒng)上（只需要線程庫(kù)），可以在一 個(gè)不支持線程的OS上實(shí)現(xiàn)

缺點(diǎn)

大多數(shù)系統(tǒng)調(diào)用會(huì)引起進(jìn)程阻塞，并且是進(jìn)程中所有線 程將被阻塞
內(nèi)核只將處理器分配給進(jìn)程，同一進(jìn)程中的兩個(gè)線程不 能同時(shí)運(yùn)行于兩個(gè)處理器上

實(shí)現(xiàn)

所有用戶級(jí)線程都具有相同的數(shù)據(jù)結(jié)構(gòu)，它們都運(yùn)行在一個(gè)中間系統(tǒng)上
（1）運(yùn)行時(shí)系統(tǒng)
是用于管理和控制線程的函數(shù)的集合，又稱(chēng)為線程庫(kù)。
（2）內(nèi)核控制線程

線程的同步

這種線程又稱(chēng)為輕型進(jìn)程LWP（Light Weight Process ）
1. 互斥鎖
2. 條件變量
3. 信號(hào)量機(jī)制

使用線程的優(yōu)點(diǎn)

1. 在一個(gè)已有進(jìn) 程 中 創(chuàng) 建 一 個(gè) 新 線 程 比 創(chuàng) 建 一 個(gè)全新進(jìn)程所需的時(shí)間少。
2. 終止一個(gè)線程比終止一個(gè)進(jìn)程花費(fèi)的時(shí)間少 。
3. 線程間切換比進(jìn)程間切換花費(fèi)的時(shí)間少。
4. 線程提高了不同的執(zhí)行程序間通信的效率 。同一個(gè)進(jìn)程中的 線程共享存儲(chǔ)空間和文件，它們無(wú)需調(diào)用內(nèi)核就可以互相通信。

進(jìn)程同步經(jīng)典問(wèn)題

處理機(jī)調(diào)度和死鎖

調(diào)度的目標(biāo)：
1、提高處理機(jī)的利用率
2、提高系統(tǒng)吞吐量
3、盡量減少進(jìn)程的響應(yīng)時(shí)間
4、防止進(jìn)程長(zhǎng)期得不到運(yùn)行

調(diào)度方式和算法的選擇，取決于操作系統(tǒng)的類(lèi)型及其目標(biāo)。

選擇準(zhǔn)則（面向系統(tǒng)）：
1. 系統(tǒng)吞吐量
2. 處理機(jī)利用率
3. 各類(lèi)資源的平衡利用

選擇準(zhǔn)則（面向用戶）：
1. 周轉(zhuǎn)時(shí)間
2. 響應(yīng)時(shí)間
3. 截止時(shí)間的保證
4. 優(yōu)先權(quán)原則

三級(jí)調(diào)度

高級(jí)調(diào)度

又稱(chēng)為作業(yè)調(diào)度或長(zhǎng)程調(diào)度，作業(yè)（JOB）是用戶在一次算題過(guò)程中或一次事務(wù)處理中，要求計(jì)算機(jī)系統(tǒng)所做的工作的集合 。

批處理系統(tǒng)需要有作業(yè)調(diào)度，分時(shí)和實(shí)時(shí)系統(tǒng)無(wú)需此調(diào)度

多道程序度：即允許多少個(gè)作業(yè)同時(shí)在內(nèi)存中運(yùn)行。
周轉(zhuǎn)時(shí)間：從作業(yè)被提交給系統(tǒng)開(kāi)始，到作業(yè)完成為 止的這段時(shí)間間隔。
吞吐量：是指在單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)

中級(jí)調(diào)度

它按一定的算法將外存中已具備運(yùn)行條件的進(jìn)程換入內(nèi)存，而將內(nèi)存中某些處于阻塞狀態(tài)的某些進(jìn)程換出至外存（阻塞->掛起）。

中級(jí)調(diào)度的目的是為了解決內(nèi)存緊張問(wèn)題。

低級(jí)調(diào)度

又稱(chēng)為進(jìn)程調(diào)度或短程調(diào)度。是最基本的調(diào)度，在三種類(lèi)型的操作系統(tǒng)中都必須配置它。（批處理、分時(shí)和實(shí)時(shí)）
分為：
1. 非搶占方式
2. 搶占方式，原則：1）優(yōu)先權(quán)原則 2）短作業(yè)優(yōu)先原則 3）時(shí)間片原則

三個(gè)基本原則：
（1）排隊(duì)器
（2）分派器（調(diào)度程序）
（3）上下文切換機(jī)制

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

調(diào)度算法

先來(lái)先服務(wù)-FCFS

按照作業(yè)/進(jìn)程進(jìn)入系統(tǒng)的先后次序，遵循先進(jìn)入系統(tǒng)者先調(diào)度。
優(yōu)點(diǎn)：
1. 有利于長(zhǎng)作業(yè)/進(jìn)程
2. 有利于CPU繁忙型作業(yè)/進(jìn)程

缺點(diǎn)：
1. 不利于短作業(yè)/進(jìn)程，尤其是來(lái)的較晚的短作業(yè)/進(jìn)程
2. 不利于I/O繁忙型作業(yè)/進(jìn)程

用于批處理系統(tǒng)，不適于分時(shí)系統(tǒng)

短作業(yè)/進(jìn)程優(yōu)先算法-SJF/SPF

按照運(yùn)行時(shí)間長(zhǎng)短進(jìn)行調(diào)度，運(yùn)行時(shí)間越短越優(yōu)先調(diào)度。不可搶占。
優(yōu)點(diǎn)：
1. 能有效降低作業(yè)/進(jìn)程的平均等待時(shí)間
2. 提高系統(tǒng)的吞吐量

缺點(diǎn)：
1. 不利于長(zhǎng)作業(yè)/進(jìn)程
2. 未考慮作業(yè)/進(jìn)程緊迫程度，不能保證緊迫作業(yè)/進(jìn)程被及時(shí)處理
3. 運(yùn)行時(shí)間無(wú)法準(zhǔn)確估計(jì)，不能真正保證短作業(yè)/進(jìn)程優(yōu)先
4. 無(wú)法實(shí)現(xiàn)人機(jī)交互

高優(yōu)先權(quán)優(yōu)先算法-HPF

分類(lèi)：
1. 靜態(tài)優(yōu)先權(quán)，簡(jiǎn)單易行，開(kāi)銷(xiāo)小，但是不夠精確，還可能導(dǎo)致低優(yōu)先權(quán)作業(yè)/進(jìn)程長(zhǎng)期得不到調(diào)度
2. 動(dòng)態(tài)優(yōu)先權(quán)，更好的調(diào)度性能，可防止長(zhǎng)作業(yè)/進(jìn)程長(zhǎng)期壟斷處理機(jī)

高響應(yīng)比優(yōu)先調(diào)度算法-HRRN

響應(yīng)比/優(yōu)先權(quán)=等待時(shí)間+要求服務(wù)時(shí)間要求服務(wù)時(shí)間=響應(yīng)時(shí)間要求服務(wù)時(shí)間響應(yīng)比/優(yōu)先權(quán)=等待時(shí)間+要求服務(wù)時(shí)間要求服務(wù)時(shí)間=響應(yīng)時(shí)間要求服務(wù)時(shí)間

此處的要求服務(wù)時(shí)間，準(zhǔn)確來(lái)說(shuō)是指剩余的需要服務(wù)的時(shí)間。

HRRN是介于FCFS和SJF/SPF之間的一種這種算法，相比于SJF/SPF有著更低的吞吐量和更高的系統(tǒng)開(kāi)銷(xiāo)。

對(duì)短作業(yè)有利，一定程度上是先來(lái)先服務(wù)，也對(duì)長(zhǎng)作業(yè)有利，但由于計(jì)算響應(yīng)比，會(huì)增加系統(tǒng)開(kāi)銷(xiāo)。

時(shí)間片輪轉(zhuǎn)算法-RR

系統(tǒng)將所有就緒進(jìn)程按先來(lái)先服務(wù)原則排成隊(duì)列。
就緒進(jìn)程直接置于隊(duì)尾，若此時(shí)正處于某一進(jìn)程的時(shí)間片，該進(jìn)程是位于隊(duì)首的

多級(jí)反饋隊(duì)列調(diào)度算法-FB

原理：
1. 設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)
2. 一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，按FCFS原則排隊(duì)等待調(diào)度
3. 僅當(dāng)?shù)谝魂?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行

調(diào)度過(guò)程：
1. 按優(yōu)先級(jí)由高到低設(shè)置多個(gè)隊(duì)列RQ0 ，RQ1 … RQn ，高優(yōu)先級(jí)隊(duì)列時(shí)間片小
2. 剛進(jìn)入系統(tǒng)的進(jìn)程按FCFS放入最高的RQ0中
3. 進(jìn)程一次時(shí)間片沒(méi)執(zhí)行完，就降至下一級(jí)隊(duì)列，以此類(lèi) 推，降至最低優(yōu)先級(jí)隊(duì)列后，一直在此隊(duì)列中不再下降
4. 系統(tǒng)優(yōu)先調(diào)度高優(yōu)先級(jí)隊(duì)列中的進(jìn)程，僅當(dāng)RQ0 空閑時(shí)才調(diào)度RQ1 隊(duì)列進(jìn)程，以此類(lèi)推
5. 如果是搶占式，當(dāng)前時(shí)間片未用完時(shí)有進(jìn)程進(jìn)入高優(yōu)先級(jí)隊(duì)列時(shí)，將當(dāng)前進(jìn)程置于其所在隊(duì)列的末尾，而后開(kāi)始執(zhí)行高優(yōu)先級(jí)隊(duì)列的時(shí)間片

實(shí)時(shí)調(diào)度

常用的調(diào)度方式：
1. 非搶占式輪轉(zhuǎn)調(diào)度方式
2. 非搶占式優(yōu)先權(quán)調(diào)度方式
3. 搶占式調(diào)度優(yōu)先權(quán)調(diào)度方式
4. 立即搶占的優(yōu)先權(quán)調(diào)度方式
由上往下，響應(yīng)時(shí)間數(shù)量級(jí)逐個(gè)降低，要求更為嚴(yán)格，所需資源也更多。

常用的高優(yōu)先權(quán)優(yōu)先的實(shí)時(shí)調(diào)度算法：
1. 最早截止時(shí)間優(yōu)先算法-EDF，截止時(shí)間越早越優(yōu)先。
2. 最低松弛度優(yōu)先算法-LLF，松弛度：截止時(shí)間-剩余所需時(shí)間-當(dāng)前時(shí)間，主要用于可搶占調(diào)度方式，當(dāng)松弛度為0時(shí)，必須立即搶占CPU。

產(chǎn)生死鎖的原因

1. 競(jìng)爭(zhēng)資源
2. 進(jìn)程推進(jìn)順序非法

m個(gè)同類(lèi)資源被n個(gè)進(jìn)程共享，設(shè)一個(gè)進(jìn)程最多可以請(qǐng)求多x個(gè)資源
m > n * (x-1) 時(shí)，系統(tǒng)不會(huì)發(fā)生死鎖。

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

1. 互斥條件
2. 請(qǐng)求與保持條件
3. 不剝奪條件
4. 環(huán)路等待條件

處理死鎖的基本辦法

預(yù)防死鎖

破壞死鎖必要條件的后三者之一，互斥條件因?yàn)橐恍┵Y源固有特性的限制，難以破壞，對(duì)于打印機(jī)這樣的設(shè)備可以通過(guò)SPOOLing技術(shù)對(duì)互斥條件予以破壞。
1. 破壞“請(qǐng)求與保持”條件，規(guī)定所有進(jìn)程都必須一次性申請(qǐng)運(yùn)行過(guò)程所需的全部資源，會(huì)造成資源浪費(fèi)嚴(yán)重和更多更久的進(jìn)程阻塞。
2. 破壞“不剝奪”條件，規(guī)定一個(gè)已經(jīng)保持了某些資源的進(jìn)程，在提出新的資源請(qǐng)求而不能立即得到滿足時(shí)，必須釋放它已經(jīng)獲得的所有資源，方法實(shí)現(xiàn)復(fù)雜且開(kāi)銷(xiāo)大。
3. 破壞“環(huán)路等待“條件，將系統(tǒng)資源按類(lèi)型賦予不同的序號(hào)，當(dāng)進(jìn)程要獲取多種資源時(shí)必須按序號(hào)逐個(gè)獲取資源。會(huì)限制新設(shè)備類(lèi)型的增加，由于有些進(jìn)程使用資源的順序與規(guī)定的順序不同，會(huì)造成資源的浪費(fèi)。

避免死鎖

將系統(tǒng)狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，安全狀態(tài)一定不會(huì)產(chǎn)生死鎖，不安全狀態(tài)可能會(huì)產(chǎn)生死鎖。
允許進(jìn)程動(dòng)態(tài)申請(qǐng)資源，系統(tǒng)分配資源前進(jìn)行安全性檢查，若分配會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則不予以分配。

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

死鎖的檢測(cè)與解除

系統(tǒng)定時(shí)進(jìn)行死鎖的檢測(cè)，當(dāng)判明將發(fā)生死鎖或已經(jīng)發(fā)生死鎖時(shí)，進(jìn)行死鎖的解除。

死鎖的檢測(cè)：
1. 判斷的現(xiàn)有的資源能否讓現(xiàn)有的進(jìn)程全部正常結(jié)束，不能則認(rèn)為將發(fā)生死鎖。
2. 周期性檢測(cè)進(jìn)程阻塞時(shí)間，當(dāng)其超過(guò)某一時(shí)間后，認(rèn)為該進(jìn)程為死鎖進(jìn)程。

死鎖的解除：
1. 剝奪資源
2. 撤銷(xiāo)進(jìn)程

存儲(chǔ)器管理

三級(jí)存儲(chǔ)：
1. 高速緩存cache
2. 內(nèi)存RAM
3. 磁盤(pán)

五級(jí)存儲(chǔ)：
1. 寄存器
2. 高速緩存
3. 內(nèi)存
4. 磁盤(pán)緩存
5. 磁盤(pán)

存儲(chǔ)分配的三種方式：
1. 直接指定
2. 靜態(tài)分配方式
3. 動(dòng)態(tài)分配方式

程序的裝入

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

程序的鏈接

1. 靜態(tài)鏈接
2. 裝入時(shí)動(dòng)態(tài)鏈接
3. 運(yùn)行時(shí)動(dòng)態(tài)鏈接

運(yùn)行時(shí)動(dòng)態(tài)鏈接是目前最常使用的鏈接方式

存儲(chǔ)器管理的目的

1. 主存儲(chǔ)器的分配和管理
2. 提高主存儲(chǔ)器的利用率
3. “擴(kuò)充”主存容量
4. 存儲(chǔ)保護(hù)

存儲(chǔ)器保護(hù)

1. 自動(dòng)地址修改
2. 0頁(yè)，1頁(yè)尋址
3. 界限寄存器

連續(xù)分配方式

1. 單一連續(xù)分配方式
2. 分區(qū)式分配方式
3. 可重定位分區(qū)分配

單一連續(xù)分配方式

內(nèi)存中僅駐留一道用戶程序，整個(gè)用戶區(qū)為一個(gè)用戶獨(dú) 占。 ?內(nèi)存分為兩個(gè)區(qū)域：系統(tǒng)區(qū)，用戶區(qū)。
應(yīng)用程序裝入到用戶區(qū)，可使用用戶區(qū)全部空間。

分區(qū)式分配方式

算法復(fù)雜，回收分區(qū)時(shí)系統(tǒng)開(kāi)銷(xiāo)大。
1. 固定分區(qū)分配
（1）分區(qū)大小不等（2）分區(qū)大小相等
建立分區(qū)說(shuō)明表，內(nèi)存分配程序檢索分區(qū)說(shuō)明表，找出合適分區(qū)后修改分區(qū)狀態(tài)。
優(yōu)點(diǎn)：易于實(shí)現(xiàn)，開(kāi)銷(xiāo)小
缺點(diǎn)：內(nèi)碎片造成浪費(fèi)，分區(qū)總數(shù)固定，限制了并發(fā)執(zhí)行的程序數(shù)目，存儲(chǔ)空間的利用率太低。
2. 動(dòng)態(tài)分區(qū)分配
1. 分區(qū)數(shù)目固定
2. 分區(qū)數(shù)目大小均不固定

數(shù)據(jù)結(jié)構(gòu)：空閑分區(qū)表 / 空閑分區(qū)鏈

分區(qū)分配算法

基于順序搜索：
1. 最佳適應(yīng)算法
2. 最壞適應(yīng)算法
3. 首次適應(yīng)算法
4. 循環(huán)首次（下次）適應(yīng)算法

基于索引搜素：
1. 快速適應(yīng)算法
2. 伙伴系統(tǒng)

最佳適應(yīng)算法

總是尋找其大小最接近作業(yè)所要求的存儲(chǔ)區(qū)域。即使作業(yè)放入后剩下的零頭最小。

優(yōu)點(diǎn)：
遇到大作業(yè)到來(lái)時(shí)，作業(yè)要求的存儲(chǔ)區(qū)域就比較容易得到滿足。
缺點(diǎn)：
產(chǎn)生空白區(qū)較多，且空白區(qū)較小無(wú)法使用（可干脆將整個(gè)區(qū)域劃分給申請(qǐng)的作業(yè)。
回收分區(qū)時(shí)插入到合適的位置較為費(fèi)時(shí)。

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

最壞適應(yīng)算法

它在為作業(yè)選擇存儲(chǔ)區(qū)域時(shí)，總是尋找最大的空白區(qū)。在劃分后剩下的空白區(qū)也是最大的，因而對(duì)以后的分配很可能仍然是有用的，這是該算法的一個(gè)優(yōu)點(diǎn)。

但是，由于最大的空白塊總是首先被分配而進(jìn)行劃分，當(dāng)有大的作業(yè)時(shí)，其存儲(chǔ)空間的申請(qǐng)往往得不到滿足，這是該算法的一個(gè)缺點(diǎn)。

為了支持這個(gè)算法的實(shí)現(xiàn)，空白塊應(yīng)以大小遞減的順序鏈接起來(lái)。

首次適應(yīng)算法

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

優(yōu)點(diǎn)：
算法簡(jiǎn)單，查找速度快，大作業(yè)到來(lái)時(shí)也比較容易得到滿足

缺點(diǎn)：
會(huì)留下較多無(wú)法使用的空白區(qū)，存儲(chǔ)空間利用率不高。較小空白區(qū)集中在前端，較大空白區(qū)在尾端，導(dǎo)致找到合適的空白區(qū)的速度降低。

下次適應(yīng)算法

我們把存儲(chǔ)空間中空白區(qū)構(gòu)成一個(gè)循環(huán)鏈。每次為存儲(chǔ)請(qǐng)求查找合適的分區(qū)時(shí)，總是從上次查找結(jié)束的地方開(kāi)始，只要找到一個(gè)足夠大的空白區(qū)，就將它劃分后分配出去。

優(yōu)點(diǎn)：存儲(chǔ)空間的利用更加均衡。

快速適應(yīng)算法

將空閑分區(qū)根據(jù)其容量大小進(jìn)行分類(lèi)，對(duì)于每一 類(lèi)具有相同容量的所有空閑分區(qū)，單獨(dú)設(shè)立一個(gè)空閑分區(qū)鏈表。

在內(nèi)存中設(shè)立一張管理分區(qū)類(lèi)型，并記錄 了該類(lèi)型空閑分區(qū)鏈表表頭的索引表，該表的每一個(gè)表項(xiàng)記錄了對(duì)應(yīng)類(lèi)型空閑分區(qū)鏈表表頭的指針。

在內(nèi)存中設(shè)立一張管理分區(qū)類(lèi)型，并記錄了該類(lèi)型空閑分區(qū)鏈表表頭的索引表，該表的每一個(gè)表項(xiàng)記錄了對(duì)應(yīng)類(lèi)型空閑分區(qū)鏈表表頭的指針。

優(yōu)點(diǎn)：
查找效率高。
該算法在進(jìn)行空閑分區(qū)分配時(shí)，不會(huì)對(duì)任何分區(qū)產(chǎn)生 分割，所以能保留大的分區(qū)，滿足對(duì)大空間的需求， 也不會(huì)產(chǎn)生內(nèi)存碎片。（外碎片）

缺點(diǎn)：
在分區(qū)歸還主存時(shí)算法復(fù)雜，系統(tǒng)開(kāi)銷(xiāo)較大。
該算法在分配空閑分區(qū)時(shí)是以進(jìn)程為單位，一個(gè)分區(qū) 只屬于一個(gè)進(jìn)程，因此在為進(jìn)程所分配的一個(gè)分區(qū)中 ，或多或少地存在一定的浪費(fèi)。空閑分區(qū)劃分越細(xì)， 浪費(fèi)則越嚴(yán)重。（內(nèi)碎片）

伙伴系統(tǒng)

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

哈希算法

利用哈希快速查找的優(yōu)點(diǎn)，以及空閑分區(qū)在可利 用空間表中的分布規(guī)律，建立哈希函數(shù)，構(gòu)造一 張哈希表，以空閑分區(qū)大小為關(guān)鍵字，每一個(gè)表 項(xiàng)記錄了一個(gè)對(duì)應(yīng)的空閑分區(qū)鏈表表頭指針。

當(dāng)進(jìn)行空閑分區(qū)分配時(shí)，根據(jù)所需空閑分區(qū)大小， 通過(guò)哈希函數(shù)計(jì)算，即得到在哈希表中的位置， 從中得到相應(yīng)的空閑分區(qū)鏈表，實(shí)現(xiàn)最佳分配策 略。

可重定位分區(qū)分配

緊湊

解決零頭問(wèn)題的辦法，將內(nèi)存中的所有作業(yè)進(jìn)行移動(dòng)，使它們?nèi)枷噜徑?，這樣，可把原來(lái)分散的多個(gè)小分區(qū)合成一個(gè)大分區(qū)。這種技術(shù)稱(chēng)為存儲(chǔ)器的“緊湊”。

動(dòng)態(tài)重定位

在動(dòng)態(tài)運(yùn)行時(shí)裝入的方式中，作業(yè)裝入內(nèi)存后的所有地址都仍然是相對(duì)地址，將相對(duì)地址轉(zhuǎn)換為物理地址的工作，被推遲到程序指令要真正執(zhí)行時(shí)進(jìn)行。

動(dòng)態(tài)重定位分區(qū)分配法是利用分區(qū)的“拼接”(對(duì)空白區(qū)而言)或“緊湊”(作業(yè)程序而言)技術(shù) 解決“零頭”。

對(duì)換

對(duì)換指把內(nèi)存中暫不能運(yùn)行的進(jìn)程或暫時(shí)不用和程序和數(shù)據(jù)，換到外存上，以騰出足夠的內(nèi)存空間，把已具備運(yùn)行條件的進(jìn)程，或進(jìn)程所需要的程序和數(shù)據(jù)，換入內(nèi)存。

對(duì)換是系統(tǒng)行為，是提高內(nèi)存的利用率的有效措施。
- 整體對(duì)換（進(jìn)程對(duì)換）
- 頁(yè)面對(duì)換（分段對(duì)換）

為實(shí)現(xiàn)對(duì)換，系統(tǒng)需要三方面的功能：
對(duì)換空間的管理
進(jìn)程的換入
換出

對(duì)換空間的管理

外存被分為兩部分， 文件區(qū)和對(duì)換區(qū)，文件區(qū)用于存放文件，它采取離散分配方式。 對(duì)換（續(xù)） 即一個(gè)文件可根據(jù)當(dāng)前外存的使用情況 ， 被分成多塊 ，分別存儲(chǔ)到不鄰接的多個(gè)存儲(chǔ)區(qū)域中 ，用指針相連。 對(duì)換區(qū)存放從內(nèi)存換出的進(jìn)程 ，它們?cè)谕獯娴拇娣艜r(shí)間較短，換入 、換出頻繁。對(duì)對(duì)換區(qū)的管理，采用連續(xù)分配方式 。

分配算法可以是首次適應(yīng)算法、循環(huán)首次適應(yīng)算 法和最佳適應(yīng)算法。

進(jìn)程的換出和換入

1、換出（swap out）
①選擇：首先選擇阻塞或睡眠狀態(tài)的進(jìn)程，若有多個(gè)，按優(yōu)先級(jí)由低到高進(jìn)行選擇。若沒(méi)有此狀態(tài)進(jìn)程，則選擇就緒狀態(tài)的，仍然按優(yōu)先級(jí)由低到高進(jìn)行選擇。
②為避免某進(jìn)程被頻繁的換入換出，還應(yīng)考慮進(jìn)程在內(nèi)存中的駐留時(shí)間，優(yōu)先選擇駐留時(shí)間長(zhǎng)的進(jìn)程。

2、換入（swap in）
①?gòu)?PCB集合中查找“就緒且換出”的進(jìn)程，有多個(gè)，則選擇換出時(shí)間最長(zhǎng)的。
②根據(jù)進(jìn)程大小申請(qǐng)內(nèi)存，成功則讀入，否則要先執(zhí)行換出，再換入。
③若還有可換入進(jìn)程，則轉(zhuǎn)向①。直至無(wú)“就緒且換出”進(jìn)程或無(wú)法獲得足夠內(nèi)存空間為止。

離散分配方式

程序在內(nèi)存中不一定連續(xù)存放。

1）離散的基礎(chǔ)
• 分頁(yè)(Pages)：將程序地址空間分頁(yè)
• 分塊(Frames)：將內(nèi)存空間分塊
2）離散分配的體現(xiàn)
• 內(nèi)存一塊可以裝入程序一頁(yè)
• 連續(xù)的多個(gè)頁(yè)不一定裝入連續(xù)的多個(gè)塊中 •
注：系統(tǒng)中頁(yè)塊的大小是不變的。

根據(jù)離散時(shí)的基本單位不同，可分為三種：
分頁(yè)存儲(chǔ)管理
分段存儲(chǔ)管理
段頁(yè)式存儲(chǔ)管理

優(yōu)點(diǎn)：沒(méi)有外零頭，僅有小于一個(gè)頁(yè)面的內(nèi)零頭

分頁(yè)存儲(chǔ)管理

注意：
頁(yè)面或頁(yè)，是邏輯空間的概念
物理塊或頁(yè)框，是內(nèi)存空間/物理空間的概念

頁(yè)表，每個(gè)進(jìn)程對(duì)應(yīng) 1 個(gè)頁(yè)表，描述該進(jìn)程的各頁(yè)面在內(nèi)存中對(duì)應(yīng)的物理塊號(hào)。 包括頁(yè)號(hào)、物理塊號(hào)，存放在主存的系統(tǒng)專(zhuān)用區(qū)。（ 平時(shí)存于PCB中，要運(yùn)行時(shí)才裝入PTR中）

作業(yè)表，整個(gè)系統(tǒng)1張，記錄作業(yè)的頁(yè)表情況，包含進(jìn)程號(hào)、頁(yè)表長(zhǎng)度、頁(yè)表始址等信息。

空閑塊表，整個(gè)系統(tǒng)1張，記錄主存當(dāng)前空閑塊。

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

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

快表

為了提高地址變換速度，為進(jìn)程頁(yè)表設(shè)置一個(gè)專(zhuān)用的高速緩沖存儲(chǔ)器，稱(chēng)為快表 TLB(Translation Lookaside Buffer)，或聯(lián)想存儲(chǔ)器（Associative Memory）。專(zhuān)門(mén)保存當(dāng)前進(jìn)程最近訪問(wèn)過(guò)的一組頁(yè)表項(xiàng)。

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

根據(jù)邏輯地址中的頁(yè)號(hào) ， 查找快表中是否存在對(duì)應(yīng)的頁(yè)表項(xiàng)。
若快表中存在該表項(xiàng)，稱(chēng)為命中（hit），取出其中的頁(yè)框號(hào)， 加上頁(yè)內(nèi)偏移量 ，計(jì)算出物理地址。
若快表中不存在該頁(yè)表項(xiàng) ， 稱(chēng)為命中失敗 ， 則再查找頁(yè)表， 找到邏輯地址中指定頁(yè)號(hào)對(duì)應(yīng)的頁(yè)框號(hào)。 同時(shí)， 更新快表， 將該表項(xiàng)插入快表中。并計(jì)算物理地址.

訪問(wèn)內(nèi)存的有效時(shí)間 EAT

定義：從進(jìn)程發(fā)出指定邏輯地址的訪問(wèn)請(qǐng)求，經(jīng)過(guò)地址變換，再到內(nèi)存中找到對(duì)應(yīng)的物理單元并取出數(shù)據(jù)，所花費(fèi)的總時(shí)間。

多級(jí)頁(yè)表

存儲(chǔ)大頁(yè)表，① 采用離散分配方式來(lái)解決難以找到一塊連續(xù)的大內(nèi)存空間的問(wèn)題，（即引入兩級(jí)頁(yè)表），② 只將當(dāng)前需要的部分頁(yè)表項(xiàng)調(diào)入內(nèi)存， 其余的 頁(yè)表項(xiàng)仍駐留在磁盤(pán)上，需要時(shí)再調(diào)入。

對(duì)于要求連續(xù)的內(nèi)存空間來(lái)存放頁(yè)表的問(wèn)題：

可將頁(yè)表進(jìn)行分頁(yè)，并離散地將各個(gè)頁(yè)面分別存放在不同的物理塊中，

同樣也要為離散分配的頁(yè)表再建立一張頁(yè)表，稱(chēng)為外層頁(yè)表(Outer Page Table)，在每個(gè)頁(yè)表項(xiàng)中記錄了頁(yè)表分頁(yè)的物理塊號(hào)。

反置頁(yè)表

（1）IPT是為主存中的每一個(gè)物理塊建立一個(gè)頁(yè)表項(xiàng)并按照塊號(hào)排序；
（2）該表每個(gè)表項(xiàng)包含正在訪問(wèn)該物理塊的進(jìn)程標(biāo)識(shí)、頁(yè)號(hào)及特征位,用來(lái)完成主存物理塊到訪問(wèn)進(jìn)程的頁(yè)號(hào)的轉(zhuǎn)換。

地址轉(zhuǎn)換過(guò)程（反置頁(yè)表）

邏輯地址給出進(jìn)程標(biāo)識(shí)和頁(yè)號(hào),用它們?nèi)ケ容^ IPT, 若整個(gè)反 置 頁(yè)表中未能找到匹配的頁(yè)表項(xiàng) , 說(shuō)明該頁(yè)不在主存, 產(chǎn)生請(qǐng)求調(diào) 頁(yè)中斷 , 請(qǐng)求操作系統(tǒng)調(diào)入;否則，該表項(xiàng)的序號(hào)便是物理塊號(hào),塊號(hào)加上位移，便形成物理地址。

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ分頁(yè)存儲(chǔ)管理的優(yōu)點(diǎn)

• 減少碎片
• 程序不必連續(xù)存放，便于裝入
• 便于管理
• 能實(shí)現(xiàn)動(dòng)態(tài)鏈接

分頁(yè)存儲(chǔ)管理的缺點(diǎn)

• 程序必須全部裝入內(nèi)存，才可以運(yùn)行
• 操作系統(tǒng)必須為每一個(gè)任務(wù)都維護(hù)一張頁(yè)面，開(kāi)銷(xiāo)比較大，簡(jiǎn)單的頁(yè)面結(jié)構(gòu)已經(jīng)不能滿足要求，必須設(shè)計(jì)更復(fù)雜的結(jié)構(gòu)，如：多級(jí)頁(yè)表結(jié)構(gòu)、哈希頁(yè)表結(jié)構(gòu)、反置頁(yè)表

分段式存儲(chǔ)管理

1. 方便編程
   模塊化程序設(shè)計(jì)的分段結(jié)構(gòu)
2. 分段共享
   段是信息的邏輯單位，可以為共享過(guò)程建立一個(gè)獨(dú)立的段，更便于實(shí)現(xiàn)程序和數(shù)據(jù)的共享。
3. 分段保護(hù)
   對(duì)內(nèi)存中的信息的保護(hù)，同樣也是對(duì)信息的邏輯單位進(jìn)行保護(hù)。采用分段存儲(chǔ)管理，對(duì)實(shí)現(xiàn)保護(hù)，將是更有效和方便。
4. 動(dòng)態(tài)鏈接
   程序運(yùn)行時(shí)，先將主程序所對(duì)應(yīng)的目標(biāo)程序裝入內(nèi)存并啟動(dòng)運(yùn)行，當(dāng)運(yùn)行過(guò)程中又需要調(diào)用某段時(shí)，才將該段調(diào)入內(nèi)存并進(jìn)行鏈接。
5. 動(dòng)態(tài)增長(zhǎng)
   在實(shí)際使用中，往往有些段，特別是數(shù)據(jù)段會(huì)隨著程序的運(yùn)行不斷增大，而這種增長(zhǎng)事先并不知曉會(huì)增長(zhǎng)到多大，采用其它存儲(chǔ)管理方式是難以應(yīng)付的，而分段存儲(chǔ)管理卻能較好的解決這一問(wèn)題。

分段系統(tǒng)的基本原理

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

Δ" role="presentation" style="box-sizing: border-box; position: relative;">ΔΔ分段存儲(chǔ)管理的優(yōu)點(diǎn)

1. 沒(méi)有內(nèi)碎片，外碎片可以通過(guò)內(nèi)存緊縮來(lái)消除
2. 便于改變進(jìn)程占用空間的大小

分段存儲(chǔ)管理的缺點(diǎn)

1. 進(jìn)程全部裝入內(nèi)存

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

1. 可見(jiàn)與不可見(jiàn)
   • “分頁(yè)”是系統(tǒng)活動(dòng)，用戶無(wú)法介入，頁(yè)的大小 固定；• “分段”是用戶可見(jiàn)的，段大小可變。
2. 物理單位與邏輯單位
   • 頁(yè)是信息的物理單位，不是完整的邏輯單位；• 段是完整的邏輯信息單位。
3. 地址空間
   • 分頁(yè)的用戶程序地址空間是一維的，是單一線性 空間；• 分段的用戶程序地址空間是二維的。
4. 分頁(yè)是為了提高內(nèi)存利用率，或者說(shuō)是系統(tǒng)管理的需要。分段是為了更好地滿足用戶需求。
5. 分頁(yè)，用戶不關(guān)心，頁(yè)的長(zhǎng)度由機(jī)器地址結(jié)構(gòu)。分段，用戶或編輯程序確定，段的最大長(zhǎng)度由位移量字段的位數(shù)決定。

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

分頁(yè)系統(tǒng)實(shí)現(xiàn)段的共享比較困難
分段易于實(shí)現(xiàn)段的共享和段的保護(hù)

分段的共享是通過(guò)兩個(gè)作業(yè)段表的相應(yīng)表目都指向 COS過(guò)程的同一物理副本來(lái)實(shí)現(xiàn)的

段頁(yè)式存儲(chǔ)管理方式

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

原理：分段和分頁(yè)相結(jié)合。

內(nèi)存劃分：按頁(yè)式存儲(chǔ)管理方案。
內(nèi)存分配：以頁(yè)為單位進(jìn)行離散分配。
由于段頁(yè)式系統(tǒng)給作業(yè)地址空間增加了另一級(jí)結(jié)構(gòu)，現(xiàn)在 地址空間是由段號(hào)S、段內(nèi)頁(yè)號(hào)P和頁(yè)內(nèi)相對(duì)地址(位移量 )W構(gòu)成。

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

一個(gè)段就是一個(gè)頁(yè)表

在段頁(yè)式存儲(chǔ)管理方式中，每訪問(wèn)一 次數(shù)據(jù)，需訪問(wèn)三次內(nèi)存。
第一次訪問(wèn)內(nèi)存中的段表
第二次訪問(wèn)內(nèi)存中的頁(yè)表
第三次訪問(wèn)相應(yīng)數(shù)據(jù)。大大降低了訪問(wèn)速度。
解決方法： 可以設(shè)置快表，表項(xiàng)應(yīng)包括段號(hào)、頁(yè)號(hào)、物理 塊號(hào)。

綜合了分段和分頁(yè)技術(shù)的優(yōu)點(diǎn)，既能有效地利用存儲(chǔ)空間，又能方便用戶進(jìn)行程序設(shè)計(jì)。
但是，實(shí)現(xiàn)段頁(yè)式存儲(chǔ)管理系統(tǒng)需要增加硬件成本，系統(tǒng)的復(fù)雜度和管理開(kāi)銷(xiāo)也大大增加。
因此，段頁(yè)式存儲(chǔ)管理技術(shù)適合于大、中型計(jì)算機(jī)系統(tǒng)，不太適合小型、微型計(jì)算機(jī)系統(tǒng)。

如何提高內(nèi)存利用率

離散分配、對(duì)換機(jī)制、動(dòng)態(tài)鏈接、虛擬存儲(chǔ)器、存儲(chǔ)器共享

虛擬存儲(chǔ)器

物理上擴(kuò)充內(nèi)存：
增加硬件投入，收機(jī)器自身和成本的限制

從邏輯上擴(kuò)充內(nèi)存：
對(duì)換技術(shù)（解決了“駐留性”問(wèn)題）
覆蓋技術(shù)（解決了“一次性”問(wèn)題）
虛擬存儲(chǔ)器技術(shù)（依據(jù)程序執(zhí)行的局部性原理）

程序的執(zhí)行總是局部性的，表現(xiàn)在時(shí)間局部性和空間局部性

定義

虛擬存儲(chǔ)器：是指具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。

限制

1. 指令中地址的字長(zhǎng)
2. 外存的容量（對(duì)換區(qū)）

特征

1. 多次性
   多次性是指一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行。
2. 對(duì)換性
   虛擬性是以多次性和對(duì)換性為基礎(chǔ)的；而多次性和對(duì)換性又必須建立在離散分配的基礎(chǔ)上。
3. 虛擬性
   虛擬性是指能夠從邏輯上擴(kuò)充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠(yuǎn)大于實(shí)際內(nèi)存容量。

典型問(wèn)題

如果系統(tǒng)花費(fèi)大量的時(shí)間把程序和數(shù)據(jù)頻繁地?fù)Q入和換出內(nèi)存而不是執(zhí)行用戶指令，那么，稱(chēng)系統(tǒng)出現(xiàn)了抖動(dòng)。出現(xiàn)抖動(dòng)現(xiàn)象時(shí)，系統(tǒng)顯得非常繁忙， 但是吞吐量很低，甚至產(chǎn)出為零。

根本原因：選擇的頁(yè)面或段不恰當(dāng)。

實(shí)現(xiàn)方式

1. 請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)
2. 請(qǐng)求分段存儲(chǔ)管理系統(tǒng)
3. 請(qǐng)求段頁(yè)式存儲(chǔ)管理系統(tǒng)

請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)

請(qǐng)求分頁(yè)存儲(chǔ)管理方式是在純分頁(yè)系統(tǒng)的基礎(chǔ)上，增加 了部分頁(yè)裝入、請(qǐng)求調(diào)頁(yè)、頁(yè)面置換功能。

實(shí)現(xiàn)請(qǐng)求頁(yè)式存儲(chǔ)管理系統(tǒng)，需要一定的硬件支持。除了需要一定容量的內(nèi)存和外存對(duì)換區(qū)之外，還需要請(qǐng)求頁(yè)表機(jī)制、缺頁(yè)中斷機(jī)構(gòu)和地址變換機(jī)構(gòu)。

地址變換機(jī)制：
在純分頁(yè)系統(tǒng)的基礎(chǔ)上，為實(shí)現(xiàn)虛擬存儲(chǔ)器增加了某些功能：
某頁(yè)在外存的情況（狀態(tài)位＝0），需要增加產(chǎn)生和處理缺 頁(yè)中斷、請(qǐng)求調(diào)頁(yè)和頁(yè)面置換的功能。
訪問(wèn)某頁(yè)時(shí)，還應(yīng)修改其訪問(wèn)位；對(duì)某頁(yè)如果執(zhí)行寫(xiě)操作， 還應(yīng)設(shè)置修改位為1。

1. 確定最小物理塊數(shù)
   最小物理塊數(shù)：是指能保證進(jìn)程正常運(yùn)行所需的最少物理塊 數(shù)。若系統(tǒng)為某進(jìn)程所分配的物理塊數(shù)少于此值時(shí)，進(jìn)程將 無(wú)法運(yùn)行。
2. 內(nèi)存分配策略
   固定分配：指為每個(gè)進(jìn)程分配固定物理塊數(shù)，進(jìn)程在整個(gè)運(yùn)行期間不變。局部置換：指進(jìn)程運(yùn)行過(guò)程中若發(fā)生缺頁(yè)，只能從進(jìn)程本身所擁有的物理塊中選擇一頁(yè)換出，再調(diào)入所需頁(yè)。全局置換：指若空閑隊(duì)列已空，而又發(fā)生缺頁(yè)中斷時(shí)，從內(nèi)存空間中的任意進(jìn)程所擁有的物理塊中選擇一頁(yè)換出。固定分配，局部置換可變分配，全局置換可變分配，局部置換
3. 物理塊分配算法
   平均分配算法按比例分配考慮優(yōu)先權(quán)的分配算法（部分）

頁(yè)面調(diào)入策略

1. 請(qǐng)求調(diào)頁(yè)策略
   缺頁(yè)中斷時(shí)，由系統(tǒng)將所缺的頁(yè)調(diào)入內(nèi)存。但每次請(qǐng)求 只調(diào)入一頁(yè)。優(yōu)點(diǎn)：容易實(shí)現(xiàn)。缺點(diǎn)：對(duì)外存I/O次數(shù)多，開(kāi)銷(xiāo)較大，容易產(chǎn)生抖動(dòng)現(xiàn)象。
2. 預(yù)調(diào)頁(yè)策略
   將預(yù)計(jì)不久之后會(huì)被訪問(wèn)的程序或數(shù)據(jù)所在的頁(yè)面，提先調(diào)入內(nèi)存。 缺頁(yè)中斷時(shí)，系統(tǒng)為進(jìn)程裝入指定的頁(yè)面以及與之相臨的多個(gè)頁(yè)面。優(yōu)點(diǎn)：提高調(diào)頁(yè)的I/O效率。缺點(diǎn)：若局部性很差，預(yù)先裝入的很多頁(yè)面不會(huì)很快被引用，并會(huì)占用大量的內(nèi)存空間，反而降低系統(tǒng)的效率。預(yù)調(diào)頁(yè)的成功率僅約50％。常用于首次調(diào)入時(shí)，由程序員指出應(yīng)該先調(diào)入的頁(yè)面。

外存要分為文件區(qū)和對(duì)換區(qū)。對(duì)換區(qū)為取得較快的速度，采用連續(xù)分配方式，且對(duì)換區(qū)所規(guī)定盤(pán)塊較大。

1. 系統(tǒng)擁有足夠的對(duì)換區(qū)空間，這時(shí)可以全部從對(duì)換區(qū)調(diào)入所需頁(yè)面，以提高調(diào)頁(yè)的速度。
2. 系統(tǒng)缺少足夠的對(duì)換區(qū)空間，這時(shí)凡是不會(huì)被修改的 文件，都直接從文件區(qū)調(diào)入；
   而當(dāng)換出這些頁(yè)面時(shí)，由于它們未被修改而不必再將它 們重寫(xiě)到磁盤(pán)（換出），以后再調(diào)入時(shí)，仍從文件區(qū)直 接調(diào)入。但對(duì)于那些可能被修改的部分，在將它們換出時(shí)，便須 調(diào)到對(duì)換區(qū)，以后需要時(shí)，再?gòu)膶?duì)換區(qū)調(diào)入。
3. UNIX方式。
   由于與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行 過(guò)的頁(yè)面，都應(yīng)從文件區(qū)調(diào)入。 對(duì)于曾經(jīng)運(yùn)行過(guò)但又被換出的頁(yè)面，由于是被放在對(duì)換區(qū)，因此在下次調(diào)入時(shí)，應(yīng)從對(duì)換區(qū)調(diào)入。

頁(yè)面置換算法

把未來(lái)不再使用的或短期內(nèi)較少使用的頁(yè)面調(diào)出，通 常只能在局部性原理指導(dǎo)下依據(jù)過(guò)去的統(tǒng)計(jì)數(shù)據(jù)進(jìn)行預(yù)測(cè)。 要避免“抖動(dòng)”（Thrashing）（又稱(chēng)顛簸）

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

改進(jìn)：考慮置換代價(jià)。選擇換出頁(yè)面時(shí)，既要是未使用過(guò)的頁(yè)面， 又要是未被修改過(guò)的頁(yè)面。把同時(shí)滿足兩條件的頁(yè)面作為首選淘汰的頁(yè)。
5. 最不常用算法
最少使用置換算法LFU（Least Frequently Used)選擇 到當(dāng)前時(shí)間為止被訪問(wèn)次數(shù)最少的頁(yè)面被置換。
6. 頁(yè)面緩沖算法

有效訪問(wèn)時(shí)間

設(shè)內(nèi)存讀寫(xiě)周期為t，查找快表時(shí)間為λ，缺頁(yè)中斷處理時(shí)間為?，引入快表命中率為α，缺頁(yè)中斷率為f，則有效訪問(wèn)內(nèi)存時(shí)間為：

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

抖動(dòng)

1. 局部抖動(dòng)
2. 全局抖動(dòng)

產(chǎn)生原因：
進(jìn)程分配的物理塊太少
置換算法選擇不當(dāng)
全局置換使抖動(dòng)傳播

消除抖動(dòng)的辦法：
采取局部置換策略
基于工作集的物理塊分配策略
L=S準(zhǔn)則
掛起若干進(jìn)程

輸入輸出系統(tǒng)

基本功能：
• 1、隱藏物理設(shè)備的細(xì)節(jié)
• 2、與設(shè)備的無(wú)關(guān)性
• 3、提供處理機(jī)和I/O設(shè)備的利用率（并行操作）
• 4、對(duì)I/O設(shè)備進(jìn)行控制（四種控制方式）
• 5、確保對(duì)設(shè)備的正確共享（設(shè)備的共享屬性）
• 6、錯(cuò)誤處理

總體設(shè)計(jì)目標(biāo)是高效性和通用性。
(1)I/O設(shè)備與CPU的并發(fā)性；
(2)簡(jiǎn)單抽象、清晰而統(tǒng)一的接口。

I/O系統(tǒng)接口

1. 塊設(shè)備接口
   信息的存取以數(shù)據(jù)塊為單位，有結(jié)構(gòu)設(shè)備。如磁盤(pán)
2. 流設(shè)備接口
   基本單位是字符，無(wú)結(jié)構(gòu)設(shè)備。 如交互式終端、打印機(jī)。
3. 網(wǎng)絡(luò)通信接口

I/O設(shè)備和設(shè)備控制器

I/O系統(tǒng)：用于實(shí)現(xiàn)數(shù)據(jù)輸入、輸出及數(shù)據(jù)存儲(chǔ)的系統(tǒng)。

I/O設(shè)備

類(lèi)型

(1)按設(shè)備的使用特性分類(lèi)
存儲(chǔ)設(shè)備
輸入/輸出設(shè)備

(2)按傳輸速率分類(lèi)
低速設(shè)備
中速設(shè)備
高速設(shè)備

(3)按設(shè)備的共享屬性分類(lèi)
獨(dú)占設(shè)備(臨界資源 )
共享設(shè)備
虛擬設(shè)備

設(shè)備與控制器之間的接口

三種信號(hào)：
（1）數(shù)據(jù)信號(hào)：雙向，有緩存
（2）控制信號(hào)：控制器發(fā)給設(shè)備；要求其完成相 關(guān)操作
（3）狀態(tài)信號(hào)：傳送指示設(shè)備當(dāng)前狀態(tài)的信號(hào)；

設(shè)備控制器

設(shè)備控制器是一個(gè)可編址的設(shè)備，可控制多個(gè)設(shè) 備并為它們編址,以實(shí)現(xiàn)I/O設(shè)備和計(jì)算機(jī)之間的 數(shù)據(jù)交換，減輕CPU的負(fù)擔(dān)。

設(shè)備控制器可分為控制塊設(shè)備的控制器和控制字 符設(shè)備的控制器兩類(lèi)。

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

組成：設(shè)備控制器與處理機(jī)的接口，設(shè)備控制器與設(shè)備的接口和I/O邏輯

I/O通道

是一種特殊處理機(jī)，專(zhuān)門(mén)負(fù)責(zé)輸入/輸出工作，具有 執(zhí)行I/O指令的能力。主要目的是為了建立獨(dú)立的 I/O操作，使有關(guān)對(duì)I/O操作的組織、管理及其結(jié)束 處理也獨(dú)立于CPU。

總線系統(tǒng)

中斷機(jī)構(gòu)和中斷處理程序

把引起中斷的事件稱(chēng)為“中斷源”
對(duì)出現(xiàn)的事件進(jìn)行處理的程序稱(chēng)為 “ 中斷處理程序”

CPU在每條指令執(zhí)行周期的最后時(shí)刻掃描中斷寄存器， 詢問(wèn)是否有中斷信號(hào)

處理過(guò)程

中斷處理過(guò)程
–喚醒被阻塞的驅(qū)動(dòng)程序進(jìn)程
–保護(hù)被中斷進(jìn)程CPU環(huán)境
–轉(zhuǎn)入相應(yīng)的設(shè)備處理程序
–中斷處理(特性)
–恢復(fù)被中斷進(jìn)程的現(xiàn)場(chǎng)

設(shè)備驅(qū)動(dòng)程序

設(shè)備驅(qū)動(dòng)程序功能：
(1)接收由I/O進(jìn)程發(fā)來(lái)的命令和參數(shù), 并將命令中的抽象 要求轉(zhuǎn)換為具體要求。
(2)檢查用戶I/O請(qǐng)求的合法性,了解I/O設(shè)備的狀態(tài),傳遞有 關(guān)參數(shù),設(shè)置設(shè)備的工作方式。
(3)發(fā)出I/O命令并檢查設(shè)備狀態(tài)。
(4)及時(shí)響應(yīng)由控制器或通道發(fā)來(lái)的中斷請(qǐng)求并處理。

設(shè)備驅(qū)動(dòng)程序的特點(diǎn)：
(1)驅(qū)動(dòng)程序主要是指在請(qǐng)求I/O的進(jìn)程與設(shè)備控制器之間 的一個(gè)通信和轉(zhuǎn)換程序。
(2)驅(qū)動(dòng)程序與設(shè)備控制器和I/O設(shè)備的硬件特性緊密相關(guān) ,因而對(duì)不同類(lèi)型的設(shè)備應(yīng)配置不同的驅(qū)動(dòng)程序。
(3)驅(qū)動(dòng)程序與I/O設(shè)備所采用的I/O控制方式緊密相關(guān)， 常用中斷驅(qū)動(dòng)和DMA方式。
(4)由于驅(qū)動(dòng)程序與硬件緊密相關(guān),因而其中的一部分必須 用匯編語(yǔ)言書(shū)寫(xiě)。
(5)驅(qū)動(dòng)程序允許可重入。

設(shè)備處理方式：
(1)為每一類(lèi)設(shè)備設(shè)置一個(gè)進(jìn)程,專(zhuān)門(mén)用于執(zhí)行這類(lèi)設(shè) 備的I/O操作 。
(2)在整個(gè)系統(tǒng)中設(shè)置一個(gè)I/O進(jìn)程,專(zhuān)門(mén)用于執(zhí)行系統(tǒng) 中所有各類(lèi)設(shè)備的I/O操作。
(3)不設(shè)置專(zhuān)門(mén)的設(shè)備處理進(jìn)程,而只為各類(lèi)設(shè)備設(shè)置 相應(yīng)的設(shè)備處理程序(模塊),供用戶進(jìn)程或系統(tǒng)進(jìn)程調(diào)用

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方式高效，但以字/字節(jié)為傳輸單位。 每完成一個(gè)字/字節(jié)的傳輸，設(shè)備均要向CPU請(qǐng)求一次中斷
• 直接存儲(chǔ)器訪問(wèn)方式 (DMA) DMA controller in charge of block i/o
  數(shù)據(jù)傳輸?shù)幕締挝皇菙?shù)據(jù)塊DMA控制器的組成： 1. 主機(jī)與DMA控制器的接口； 2. DMA控制器與塊設(shè)備的接口； 3. I/O控制邏輯。
• 通道方式 (channel)
  CPU僅在I/O操作的開(kāi)始和結(jié)束時(shí)花費(fèi)少量時(shí)間處理與I/O 有關(guān)的工作。實(shí)現(xiàn)CPU、通道和I/O設(shè)備三者的并行操作，從而更有效 地提高整個(gè)系統(tǒng)的資源利用率

設(shè)備獨(dú)立性

含義：應(yīng)用程序獨(dú)立于具體使用的物理設(shè)備，即是指用 戶在編程序時(shí)所使用的設(shè)備與實(shí)際設(shè)備無(wú)關(guān)。

引入邏輯設(shè)備和物理設(shè)備這兩個(gè)概念。
在應(yīng)用程序中,使用邏輯設(shè)備名稱(chēng)來(lái)請(qǐng)求使用某類(lèi)設(shè)備;而系統(tǒng)在實(shí)際執(zhí)行時(shí),還必須使用物理設(shè)備名稱(chēng)。

設(shè)備獨(dú)立性的優(yōu)點(diǎn)
(1)設(shè)備分配時(shí)的靈活性
(2)易于實(shí)現(xiàn)I/O重定向

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

設(shè)備分配

（1）設(shè)備控制表DCT
（2）控制器控制表、通道控制表和系統(tǒng)設(shè)備表

虛擬設(shè)備是利用某種技術(shù)把獨(dú)占設(shè)備改造成可由多個(gè)進(jìn)程共享的設(shè)備。

用戶層的I/O軟件

用戶程序通過(guò)調(diào)用對(duì)應(yīng)的庫(kù)函數(shù)使用系統(tǒng)調(diào)用。

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

SPOOLing技術(shù)

SPOOLing技術(shù)將一臺(tái)物理I/O設(shè)備虛擬為多臺(tái)邏輯I/O 設(shè)備，同樣允許多個(gè)用戶共享一臺(tái)物理I/O設(shè)備。

組成

輸入井和輸出井
輸入緩沖區(qū)和輸出緩沖區(qū)(內(nèi)存中)
輸入進(jìn)程SPi 和輸出進(jìn)程SP0
井管理程序

輸出：（打?。?a.進(jìn)程n請(qǐng)求——>SPo為進(jìn)程n在輸出井中分配空間——> 將數(shù)據(jù)由進(jìn)程緩沖區(qū)轉(zhuǎn)到輸出井——>生成一打印請(qǐng)求 表掛打印請(qǐng)求隊(duì)列。 b.打印機(jī)空——>查打印請(qǐng)求表中的任務(wù)——> 取輸出井 中對(duì)應(yīng)的數(shù)據(jù)——>輸出緩沖區(qū)——>打印

緩沖區(qū)管理

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

提前讀，延后寫(xiě)，操作系統(tǒng)中介紹的都是軟件緩沖區(qū)

單緩沖

一個(gè)緩沖區(qū)，CPU 和外設(shè)輪流使用， 一方處理完之后接著等待對(duì)方處理

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

雙緩沖

兩個(gè)緩沖區(qū)，CPU和外設(shè)都可以連續(xù)處理而無(wú)需等待對(duì)方。要求CPU和外設(shè)的速度相近。

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

循環(huán)緩沖

增加緩沖區(qū)的數(shù)量以改善系統(tǒng)性能，這就是多緩沖區(qū)方式。
多個(gè)I/O緩沖區(qū)常常被組織成一個(gè)環(huán)形隊(duì)列，稱(chēng)為循環(huán)緩沖。

緩沖池

上述三種緩沖區(qū)的組織形式僅適用于某種特定的 I/O進(jìn)程和計(jì)算進(jìn)程，屬于專(zhuān)用緩沖。
為了提高緩沖區(qū)的利用率，可以采用公共緩沖池
其中的緩沖區(qū)可為多個(gè)設(shè)備和進(jìn)程服務(wù)

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

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

為了管理上的方便，可將相同類(lèi)型的緩沖區(qū)鏈成 一個(gè)隊(duì)列，于是可形成以下三個(gè)隊(duì)列：
（1）空緩沖隊(duì)列emq。 這是由空緩沖區(qū)所鏈成的隊(duì)列。
（2）輸入隊(duì)列inq。 這是由裝滿輸入數(shù)據(jù)的緩沖區(qū)所鏈成的隊(duì)列。
（3）輸出隊(duì)列outq 這是由裝滿輸出數(shù)據(jù)的緩沖區(qū)所鏈成的隊(duì)列。

磁盤(pán)存儲(chǔ)器的性能和調(diào)度

1、數(shù)據(jù)組織和格式：
•磁道號(hào)——磁頭號(hào)——扇區(qū)——字節(jié)

2、類(lèi)型
1）固定頭磁盤(pán)： –每個(gè)磁道上有一個(gè)磁頭，快
2）移動(dòng)頭磁盤(pán)： –每個(gè)盤(pán)面僅有一個(gè)磁頭，慢

• 信息記錄在磁道上，多個(gè)盤(pán)片，正反兩面都用來(lái)記 錄信息，每面一個(gè)磁頭
• 所有盤(pán)面中處于同一磁道號(hào)上的所有磁道組成一個(gè) 柱面
• 每個(gè)扇區(qū)大小為600字節(jié)（數(shù)據(jù)512字節(jié)）
• 物理地址形式： –柱面號(hào) –磁頭號(hào) –扇區(qū)號(hào)

訪問(wèn)過(guò)程

由三個(gè)動(dòng)作組成：
– 尋道 ：磁頭移動(dòng)定位 到指定磁道
– 旋轉(zhuǎn)延遲：等待指定 扇區(qū)從磁頭下旋轉(zhuǎn)經(jīng)過(guò)
– 數(shù)據(jù)傳輸：數(shù)據(jù)在磁 盤(pán)與內(nèi)存之間的實(shí)際傳輸

磁盤(pán)訪問(wèn)時(shí)間

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

訪問(wèn)時(shí)間：Ta=Ts+1/2r+b/rNTa=Ts+1/2r+b/rN

磁盤(pán)調(diào)度算法

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

有一個(gè)或幾個(gè)進(jìn)程對(duì)某一磁道有較高的訪 問(wèn)頻率， 即這個(gè)(些)進(jìn)程反復(fù)請(qǐng)求對(duì)某一磁道的I/O操作，從而壟斷了整個(gè)磁盤(pán)設(shè)備。 我們把這一現(xiàn)象稱(chēng)為“磁臂粘著”(Armstickiness)。

實(shí)際系統(tǒng)相當(dāng)普遍采用最短尋道時(shí)間優(yōu)先算法， 因?yàn)樗?jiǎn)單有效，性價(jià)比好。

磁盤(pán)高速緩存

…

文件管理

文件系統(tǒng)的功能：
有效地管理文件的存儲(chǔ)空間；
管理文件目錄；
完成文件的讀/寫(xiě)操作；
實(shí)現(xiàn)文件共享與保護(hù)；
為用戶提供交互式命令接口和程序調(diào)用接口。

文件系統(tǒng)

定義：
操 作 系 統(tǒng) 中 的 各 類(lèi) 文件、 管 理 文 件 的 軟件， 以 及 管 理 文 件 所 涉 及 到 的 數(shù)據(jù)結(jié) 構(gòu)等信息的集合

文件系統(tǒng)模型

分為三個(gè)層次：
1. 文件系統(tǒng)接口
2. 對(duì)對(duì)象操縱和管理的軟件集合
3. 對(duì)象及其屬性

文件類(lèi)型

1. 用途
   系統(tǒng)文件用戶文件庫(kù)文件
2. 文件中的數(shù)據(jù)形式
   源文件目標(biāo)文件可執(zhí)行文件
3. 存取控制屬性
   只執(zhí)行文件只讀文件讀寫(xiě)文件
4. 組織形式和處理方式
   普通文件目錄文件特殊文件

文件的邏輯結(jié)構(gòu)與訪問(wèn)

對(duì)于任何一個(gè)文件，都存在著以下兩種形式的結(jié)構(gòu)：
文件的邏輯結(jié)構(gòu)(File Logical Structure),又稱(chēng) 為文件組織，是用戶可以直接處理的數(shù)據(jù)及其 結(jié)構(gòu)。
文件的物理結(jié)構(gòu)， 又稱(chēng)為文件的存儲(chǔ)結(jié)構(gòu)， 是指文件在外存上的存儲(chǔ)組織形式。

文件邏輯結(jié)構(gòu)的類(lèi)型

1. 有結(jié)構(gòu)文件 記錄有定長(zhǎng)和不定長(zhǎng)兩種
   1）順序文件：按某種順序排列的定長(zhǎng)紀(jì)錄文件
   2）索引文件：按索引表查詢的不定長(zhǎng)紀(jì)錄文件
   3）索引順序文件：以上兩者的結(jié)合
2. 無(wú)結(jié)構(gòu)文件
   其長(zhǎng)度以字節(jié)為單位。 可以把流式文件看作是記錄式文件的一個(gè)特例。

順序文件

第一種是串結(jié)構(gòu)， 各記錄之間的順序與關(guān)鍵字無(wú)關(guān)。 通常的辦法是由時(shí)間來(lái)決定，即按存入時(shí)間的先后排列。

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

順序文件的優(yōu)缺點(diǎn)
常 用 于 批 量 數(shù) 據(jù) 處 理 ， 這 時(shí) 文 件 的 訪 問(wèn) 效 率最高。
是唯一、 同 時(shí) 適 合 在 磁 盤(pán) 和 磁 帶 中 存 儲(chǔ) 的 文件。
訪問(wèn)效率比堆文件高。當(dāng)文件較小，可以將文件全部裝入內(nèi)存，利用某種快速的查找算法，如折半查找法、插值查找法等快 速查找指定的記錄。

索引文件

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

索引順序文件

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

直接和哈希文件

直接文件
對(duì)于直接文件，則可根據(jù)給定的關(guān)鍵字值，直 接獲得指定記錄的物理地址。
關(guān)鍵字值本身就決定了記錄的物理地址。
這種由關(guān)鍵字值到記錄物理地址的轉(zhuǎn)換被稱(chēng)為鍵值轉(zhuǎn)換。

文件目錄

文件目錄也是一種數(shù)據(jù)結(jié)構(gòu)，用于標(biāo)識(shí)系統(tǒng)中的 文件及其物理地址，供檢索時(shí)使用。

文件控制塊（FCB）

文件控制塊是操作系統(tǒng)為管理文件而設(shè)置的數(shù)據(jù)結(jié)構(gòu)，存放了管理文件所需的所有信息（文件屬性）
1）基本信息類(lèi)
文件名：文件標(biāo)識(shí)符；
物理位置：存放文件的設(shè)備名 起始盤(pán)塊號(hào) 文件長(zhǎng)度（盤(pán)塊數(shù)或字節(jié)數(shù)）
邏輯結(jié)構(gòu)：有結(jié)構(gòu)文件、無(wú)結(jié)構(gòu)文件
物理結(jié)構(gòu)：順序文件、鏈?zhǔn)轿募?、索引文?br />2）存取控制信息類(lèi)
文件主的存取權(quán)限
核準(zhǔn)用戶的存取權(quán)限
一般用戶的存取權(quán)限
3）使用信息類(lèi)
文件的建立日期和時(shí)間
文件上一次修改的日期和時(shí)間
當(dāng)前使用信息（進(jìn)程數(shù)、是否修改等）

文件目錄：把所有的FCB組織在一起，就構(gòu)成 了文件目錄，即文件控制塊的有序集合。
目錄項(xiàng)：構(gòu)成文件目錄的項(xiàng)目（目錄項(xiàng)就是 FCB）
目錄文件：為了實(shí)現(xiàn)對(duì)文件目錄的管理，通常將文件目錄以文件的形式保存在外存，這個(gè)文件就叫目錄文件。

索引結(jié)點(diǎn)

將文件的描述信息單獨(dú)形成稱(chēng)為索引結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，即 i 結(jié)點(diǎn)

1. 磁盤(pán)索引節(jié)點(diǎn)
   指存放在磁盤(pán)上的索引結(jié)點(diǎn)包括：文件主標(biāo)識(shí)符文件類(lèi)型文件存取權(quán)限文件物理地址文件長(zhǎng)度文件鏈接計(jì)數(shù)文件存取時(shí)間
2. 內(nèi)存索引節(jié)點(diǎn)
   指存放在內(nèi)存的索引結(jié)點(diǎn)比磁盤(pán)索引節(jié)點(diǎn)增加了：索引結(jié)點(diǎn)編號(hào)狀態(tài)訪問(wèn)計(jì)數(shù)文件所屬文件系統(tǒng)的邏輯設(shè)備號(hào)鏈接指針

目錄結(jié)構(gòu)

1. 單級(jí)目錄結(jié)構(gòu)
2. 二級(jí)目錄結(jié)構(gòu)
   主文件目錄（MFD）用戶文件目錄（UFD）
3. 樹(shù)型目錄結(jié)構(gòu)
   把三級(jí)或三級(jí)以上的目錄結(jié)構(gòu)稱(chēng)樹(shù)型目錄優(yōu)點(diǎn)：層次結(jié)構(gòu)清晰，便于管理和保護(hù)，有利于文件分類(lèi)，解決重名問(wèn)題，提高文件檢索速度，能進(jìn)行存取權(quán)限的控制缺點(diǎn)：查找一個(gè)文件按路徑名逐層檢查，由于 每個(gè)文件都放在外存，多次訪盤(pán)影響速度

目錄查詢技術(shù)

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

文件共享

實(shí)現(xiàn)文件共享的方式：
基于索引結(jié)點(diǎn)的共享方式
利用符號(hào)鏈實(shí)現(xiàn)文件共享

利用URL實(shí)現(xiàn)文件共享

文件保護(hù)

存取控制機(jī)制
系統(tǒng)容錯(cuò)技術(shù)（第八章）
后備系統(tǒng)（第八章）

存取控制機(jī)制

保護(hù)域
訪問(wèn)矩陣
訪問(wèn)矩陣的修改
訪問(wèn)矩陣的實(shí)現(xiàn)
分級(jí)安全管理

磁盤(pán)存儲(chǔ)器的管理

外存的組織方式

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

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

把邏輯文件中的數(shù)據(jù)順序地存儲(chǔ)到物理上鄰接的各個(gè)數(shù)據(jù)塊中，這樣形成的物理文件可以進(jìn)行順序存取。

連續(xù)分配的主要優(yōu)點(diǎn)：
順序訪問(wèn)容易。
順序訪問(wèn)速度快。
連續(xù)分配的主要缺點(diǎn)：
要求有連續(xù)的存儲(chǔ)空間。
必須事先知道文件的長(zhǎng)度。
不能靈活地插入和刪除記錄
不適應(yīng)動(dòng)態(tài)增長(zhǎng)的文件

該 分 配 方 案 可 能 會(huì) 導(dǎo) 致 磁 盤(pán) 碎 片 ， 嚴(yán) 重 降 低外存空間的利用率。
解 決 方 法 之 一 ， 系 統(tǒng) 定 期 或 不 定 期 采 用 緊 湊 技術(shù)， 將 小 分 區(qū) 合 并 為 大 的 、 連 續(xù) 分 區(qū) ， 將文件占用空間合并在一起。

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

如果在將一個(gè)邏輯文件存儲(chǔ)到外存上時(shí)，并不要 求為整個(gè)文件分配一塊連續(xù)的空間，而是可以將 文件裝到多個(gè)離散的盤(pán)塊中。

采用鏈接分配方式時(shí)，可通過(guò)在每個(gè)盤(pán)塊上的鏈接指針，將同屬于一個(gè)文件的多個(gè)離散的盤(pán)塊鏈接成一個(gè)鏈表，把這樣形成的物理文件稱(chēng)為鏈接文件。

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

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

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

1. 單級(jí)索引分配
2. 兩級(jí)索引分配

設(shè)文件系統(tǒng)采用兩級(jí)索引分配方式，如果每個(gè)盤(pán)塊的大小為1KB，每個(gè)盤(pán)塊號(hào)占4B，則單個(gè)文件的最大長(zhǎng)度是多少？ 解：1個(gè)盤(pán)塊可有1KB/ 4B=256個(gè)索引項(xiàng)，則兩級(jí)索引下單個(gè)文件最大長(zhǎng)度： 256*256*1KB=64MB

文件存儲(chǔ)空間的管理

存儲(chǔ)空間的基本分配單位是磁盤(pán)塊。
其分配方法與內(nèi)存的分配有許多相似之處，即同樣可采取連續(xù)分配方式或離散分配方式。

動(dòng)態(tài)跟蹤磁盤(pán)上的空閑塊數(shù)目和塊號(hào)，形成空閑塊登記表。
空閑塊登記表是盤(pán)塊分配和回收的依據(jù)。
空閑塊登記表有四種實(shí)現(xiàn)方案：

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

操作系統(tǒng)接口

• 用戶接口
  聯(lián)機(jī)用戶接口脫機(jī)用戶接口
• 程序接口
  又稱(chēng)應(yīng)用編程接口API，允許運(yùn)行程序調(diào)用操作系統(tǒng)的服務(wù)和功能。程序接口由一組系統(tǒng)調(diào)用（SystemCall)） 組成，用戶程序使用“系統(tǒng)調(diào)用”就可獲得操作系統(tǒng)的底層服務(wù)，使用或訪問(wèn)系統(tǒng)的各種軟硬件資源。庫(kù)函數(shù)的目的是隱藏訪管指令細(xì)節(jié)， 使系統(tǒng)調(diào)用更象過(guò)程調(diào)用，但一般地說(shuō)，庫(kù)函數(shù)屬于用戶程序而非系 統(tǒng)程序。

聯(lián)機(jī)命令接口

分時(shí)系統(tǒng)或個(gè)人計(jì)算機(jī)中，操作系統(tǒng) 向用戶提供了一組聯(lián)機(jī)命令，用戶可以 通過(guò)終端鍵入命令，以取得操作系統(tǒng)的 服務(wù)，并控制自己作業(yè)的運(yùn)行，這樣的 接口稱(chēng)為聯(lián)機(jī)命令接口 。

聯(lián)機(jī)命令接口應(yīng)由終端處理程序、命令解釋程序及一組聯(lián)機(jī)命令構(gòu)成。

Shell命令語(yǔ)言

Shell是UNIX與用戶的交互接口,是操作系統(tǒng)的最外層,稱(chēng)為外殼
Shell既是一種命令語(yǔ)言,也是一種程序設(shè)計(jì)語(yǔ)言
Shell不是UNIX的核心程序,運(yùn)行在用戶態(tài)

系統(tǒng)調(diào)用

系統(tǒng)調(diào)用指系統(tǒng)為用戶程序調(diào)用操作系統(tǒng)所提供的子程序。 它與一般的函數(shù)調(diào)用不同，系統(tǒng)調(diào)用是通過(guò)中斷方式轉(zhuǎn)向相應(yīng)子程序的，它工作在核心態(tài) （即特權(quán)方式），而一般函數(shù)調(diào)用，仍僅在用戶態(tài)下的地址轉(zhuǎn)移 。

系統(tǒng)調(diào)用與一般過(guò)程調(diào)用的區(qū)別：

1. 運(yùn)行在不同的系統(tǒng)狀態(tài)
   一般過(guò)程調(diào)用，其調(diào)用程序和被調(diào)用程序 都運(yùn)行在相同狀態(tài)：核心態(tài)或用戶態(tài)系統(tǒng)調(diào)用：調(diào)用程序在用戶態(tài)，被調(diào)用程 序在系統(tǒng)態(tài)
2. 狀態(tài)的轉(zhuǎn)換
3. 返回問(wèn)題
   一般過(guò)程調(diào)用在被調(diào)用過(guò)程執(zhí)行完后，回調(diào)用過(guò)程。搶占式調(diào)度的系統(tǒng)中，被調(diào)用過(guò)程執(zhí)行完后，系統(tǒng)將對(duì)所有要求運(yùn)行的進(jìn)程進(jìn)行優(yōu)先級(jí)分析。如果調(diào)用進(jìn)程仍有最高優(yōu)先級(jí)，則返回到調(diào)用進(jìn)程執(zhí)行，否則，引起重新調(diào)度，讓優(yōu)先級(jí)最高的進(jìn)程 優(yōu)先執(zhí)行。此時(shí)，系統(tǒng)把調(diào)用進(jìn)程放入就緒隊(duì)列。
4. 嵌套調(diào)用
   系統(tǒng)調(diào)用也允許嵌套調(diào)用，即在一被調(diào)用過(guò)程執(zhí)行期間，可再利用系統(tǒng)調(diào)用命令調(diào)用另一系統(tǒng)調(diào)用，最大深度為