計算機操作系統與安全復習筆記

1 緒論

操作系統目標: 方便性; 有效性; 可擴充性; 開放性.
作用: 用戶與計算機硬件系統之間的接口; 計算機資源的管理者; 實現了對計算機資源的抽象; 計算機工作流程的組織者.
多道程序設計: 內存中同時存放若干個作業, 使其共享系統資源且同時運行; 單處理機環境下宏觀上并行, 微觀上交替執行.
多道批處理系統: 資源利用率高; 系統吞吐量大; 平均周轉時間長; 無交互能力.
多道程序協調問題: 處理機爭用; 內存分配和保護; I/O 設備分配; 文件組織和管理; 用戶與系統接口.
分時系統: 一臺主機上連接多個終端同時允許多個用戶通過各自終端交互使用并共享資源, 作業提交時直接進入內存并按時間片輪轉運行; 多路性, 獨立性, 及時性, 交互性.
實時系統: 將時間作為關鍵參數, 能及時響應外部事件請求在規定時間內完成處理, 并控制所有實時任務協調一致運行.
基本特性: 并發; 共享(互斥共享; 同時訪問); 虛擬(CPU; 存儲器; 設備); 異步.
主要功能: 處理機管理(進程控制, 同步, 通信, 調度); 存儲器管理(內存分配, 保護, 擴充; 地址映射); 設備管理(分配, 處理; 緩沖); 文件管理(存儲空間; 目錄; 讀/寫); 提供接口(用戶接口; 程序接口); (系統安全; 網絡服務; 多媒體存儲).

2 CPU 虛擬化

進程狀態轉換圖
帶掛起的進程狀態轉換圖

進程: 進程實體的運行過程, 系統進行資源分配和調度的獨立單位; 動態性, 并發性, 獨立性, 異步性.
掛起: 進程處于靜止狀態, 暫時不接受調度直到被激活.
PCB(進程控制塊): 標識符; 處理機狀態(通用寄存器; 指令計數器; 程序狀態字; 用戶棧指針); 調度信息(狀態; 優先級; 事件/阻塞原因); 控制信息(程序和數據地址; 同步和通信; 資源清單; 鏈接指針).
組織方式: 線性表; 鏈接隊列; 索引表.
內核態: 支撐功能(中斷處理; 時鐘管理; 原語操作); 資源管理功能(進程管理; 存儲器管理; 設備管理).
高級通信: 共享存儲器(共享數據結構; 共享存儲區); 管道; 消息傳遞(直接; 間接); C/S(客戶機-服務器).
線程: 同一進程中可以切換線程, 僅需保存和設置少量寄存器內容, 系統開銷遠小于進程切換; 同一或不同進程中線程均可并發執行; 同一進程內線程共享進程擁有的資源和地址空間, 線程間不獨立且不擁有系統資源; 多線程支持多處理機并行執行.
TCB(線程控制塊): 標識符; 寄存器; 狀態; 優先級; 專有存儲區; 信號屏蔽; 堆棧指針.

調度層次: 高級/長程/作業(多道批處理); 低級/短程/進程; 中級/內存(即對換).
共同目標: 資源利用率(有效工作時間占比); 公平性(無進程"饑餓"); 平衡性(各資源經常處于忙碌狀態); 策略強制執行(安全).
批處理目標: 平均周轉時間(作業提交到完成的時間間隔); 系統吞吐量(單位時間內完成的作業數); 處理機利用率.
分時目標: 響應時間(用戶請求到處理的時間間隔); 均衡性(響應時間與請求復雜性相適應).
實時目標: 截止時間(開始執行或完成的最遲時間); 可預測性.
FCFS(先來先服務).
SJF(短作業優先): 運行時間短的優先; 必須預知運行時間, 長作業會"饑餓", 人機難以交互, 完全未考慮緊迫程度.
PSA(優先級調度).
HRRN(高響應比調度): 優先權 $=$ 響應時間 $/$ 要求服務時間; 短作業優先, 同時避免長作業"饑餓".
進程調度: 就緒進程 $\to$ 排隊器 $\to$ 就緒隊列 $\to$ 分派器 $\to$ 上下文切換器 $\to$ 處理機.
非搶占式: 處理機分配給某進程后直至進程完成或發生某事件而阻塞時才會將處理機分配給其他進程.
搶占原則: 優先權; 短進程優先; 時間片輪轉.
RR(時間片輪轉): 按照 FCFS 策略排序為就緒隊列, 從隊首開始依次令進程執行一個時間片, 時間片內執行完正常終止, 否則中斷并將進程送入隊尾.
MFQ(多級反饋隊列): 多個就緒隊列優先級從高到低, 從第一個隊列的隊首開始依次令進程執行一個時間片, 時間片內執行完正常終止, 否則中斷并將進程送入最后一個隊列的隊尾; 僅當當前隊列前所有隊列均空閑時, 才會執行當前隊列.
保證調度: 保證每個進程都能獲得相同的處理機時間; 跟蹤計算所有進程實際已執行時間和應獲得的處理機時間之比, 比值最小的進程一直運行直到超過最接近其的比值為止.
公平分享調度: 考慮不同用戶而非單純進程得到的處理機時間占比.
實時調度基本條件: 提供必要信息(就緒時間, 開始截止時間/完成截止時間, 處理時間, 資源要求, 優先級); 系統處理能力強( $\sum_{i=1}^m\frac{C_i}{P_i}\leq N$ , $m$ 個周期性 HRT(硬實時任務), 處理時間為 $C_i$ , 周期時間為 $P_i$ , 處理機個數為 $N$ ); 搶占式調度; 快速切換機制(快速中斷響應; 快速任務分派).
EDF(最早截止時間優先): 可采用搶占或非搶占.
LLF(最低松弛度優先): 松弛度 $=$ 完成截止時間 $?$ 處理時間 $?$ 當前時間.
優先級倒置(PIP): 高優先級進程因互斥或同步被低優先級延遲或阻塞; 可采用非搶占式調度, 或動態優先級繼承(被阻塞的進程繼承導致阻塞進程的優先級一直保持到重新就緒).

3 內存虛擬化

裝入內存: 絕對裝入(單道程序); 可重定位裝入(不允許程序運行時在內存中移動位置, 裝入時一次性完成地址變換); 動態運行時裝入.
鏈接: 靜態鏈接; 裝入時動態鏈接; 運行時動態鏈接.
內部碎片: 程序小于固定分區大小時也會占用一個完整的分區空間, 分區內部存在空間浪費.
分區說明表/空閑分區表: 分區號; 分區大小; 分區起址; 狀態.
空閑分區鏈(雙向鏈表): 前向指針; 前狀態位; 后向指針; 后狀態位; 分區大小.
內存回收: 有相鄰的空閑分區時合并, 不分配新表項只修改分區大小或分區起址; 無相鄰的空閑分區時單獨建立新表項.
順序搜索: FF(首次適應; 從頭開始); NF(循環首次適應; 從上次空閑位置開始); BF(最佳適應; 滿足要求的最小空閑分區); WF(最壞適應; 從最大的空閑區中分割).
索引搜索: QF(快速適應; 根據空閑分區大小分類, 每類中所有空閑分區單獨設立空閑分區鏈); BS(伙伴系統; 已分配及空閑分區大小均為 $2^k$ ; 地址為 $x$ 的內存塊的伙伴塊地址為 $x+2^k$ ( $x\equiv 0({\rm mod}\ 2^{k+1})$ 時) 或 $x-2^k$ ( $x\equiv 2^k({\rm mod}\ 2^{k+1})$ 時)); Hash(根據所需空閑分區大小計算 Hash 值(Hash 表中位置)從中得到空閑分區鏈表).
“緊湊”/“拼湊”: 外部碎片較多無法裝入大作業時, 將內存中所有作業移動使得全部相鄰接, 將原本多個分散空閑小區分拼接成一個打分去.
動態重定位: 重定位寄存器存放程序或數據在內存中的起始地址, 訪問地址 $=$ 相對地址 $+$ 重定位地址; "緊湊時"無需修改程序, 只需用新地址修改重定位地址即可.
覆蓋(同一作業或進程): 用戶空間分為固定區和若干覆蓋區, 活躍部分在固定區, 其余部分按調用關系分段; 即將訪問的段調入覆蓋區, 其他段在外存中, 需要時調入覆蓋區并覆蓋現有段.
對換(不同作業或進程): 換入, 將準備好競爭處理機的程序從輔存移入主存; 換出, 將處于阻塞狀態的程序從主存移到輔存.

頁/頁面: 進程的邏輯地址空間分成若干大小相等的片; 邏輯地址 $A =$ 頁號 $P$ || 偏移量(頁內地址) $W$ , 頁面大小為 $L$ 時, $P=\lfloor\frac{A}{L}\rfloor$ , $W=A({\rm mod}\ L)$ .
塊/物理塊/頁框: 內存空間分成與頁面相同大小的若干個存儲塊; 物理地址 $=$ 塊號 || 偏移量(塊內地址).
頁表: 記錄頁號到塊號的映射.
兩次訪存: 第一次訪問內存得到物理地址; 第二次根據物理地址訪問對應內存單元.
TLB(快表/聯想寄存器): 具有并行查詢能力的特殊高速緩存寄存器, 為提高地址變換速度.
兩級頁表: 邏輯地址 $=$ 外層頁號 || 外層頁地址 || 頁內地址.
多級頁表: 建立索引而無需浪費主存空間存儲無用頁表項, 頂級頁表至多只有 $1$ 個頁面; 地址空間依舊為一維.
反置頁表: 為一個物理塊設置一個頁表項, 按照物理塊編號排序, 內容為頁號和所隸屬進程的標識符.
引入分段原因: 方便編程, 信息共享, 信息保護, 動態增長, 動態鏈接.
段表: 邏輯地址 $=$ 段號 || 段內地址; 段號, 段長, 基址; 段號超過段表長度或段內地址超過段長, 均產生越界中斷信號; 地址空間為二維.
段頁式: 邏輯地址 $=$ 段號 || 段內頁號 || 頁內地址; 每個段由若干頁面組成; 需要三次訪存; 地址空間為二維.

局部性原理: 時間局部性, 某個存儲單元被訪問過不久后可能會再次被訪問; 空間局部性, 某個存儲單元附近的存儲單元可能將被訪問.
虛擬存儲器: 具有請求調入功能和置換功能, 能從邏輯上對內存擴充; 多次性(多次裝入內存), 對換性, 虛擬性(邏輯上擴充內存).
請求頁表: 頁號 || 塊號 || 狀態位 $P$ (已分配/空閑) || 訪問字段 $A$ (一段時間內被訪問次數/最近多久未被訪問) || 修改位/臟位 $M$ || 外存地址.
缺頁中斷: 指令執行期間可能產生多次缺頁中斷, 屬于內部中斷.
請求段表: 段號/段名 || 段長 || 段基址 || 存取方式(僅執行/僅讀/可讀寫) || 訪問字段 $A$ || 修改位/臟位 $M$ || 存在位 $P$ (本段是否已調入內存) || 增補位(本段運行過程中是否動態增長) || 外存起址(起始盤塊號).
分段保護: 越界檢查, 段號超過段表長度或段內地址超過段長時越界中斷; 存取控制檢查, 不符合段要求的存取方式時中斷; 環境保護機構, 低編號環具有高優先權(OS 內核處于 0 號環), 僅可調用相同或高優先權服務, 僅可訪問相同或低優先權數據.

內存分配: 固定分配局部置換(物理塊數固定不變, 缺頁時在已分配的頁面中置換); 可變分配全局置換(物理塊數可變, 缺頁時分配保留的空閑物理塊, 無空閑時在全部進程的物理塊中置換); 可變分配局部置換(物理塊數可變, 缺頁時在已分配的頁面中置換).
物理塊分配: 平均分配; 按比例分配(頁面數占比); 考慮優先權分配.
調入時機: 預調頁(一次性調入若干相鄰頁, 但未必被適用); 請求調頁(僅在缺頁時調入).
調入過程: 發出缺頁中斷 $\to$ 所缺頁調入內存 $\to$ 修改頁表.
影響頁面對換效率的因素: 頁面置換算法; 寫回磁盤的頻率; 讀入內存的頻率.
PBA(頁面緩沖算法): 顯著降低頁面對換頻率, 可采用簡單的置換策略; 空閑頁面鏈表(空閑物理塊隊列; 換出時掛在隊尾), 修改頁面鏈表(修改物理塊隊列; 換出時掛在隊尾).
缺頁率: $f=\frac{F}{A}$ , $F$ 為調頁次數, $A$ 為頁面訪問總次數; 頁面越大, 分配物理塊數目越多, 程序局部性越好, 缺頁率越低.
最佳置換: 換出以后永不使用或在未來最長時間內不再訪問的頁面; 理論缺頁率最低.
FIFO(先進先出).
LRU(最近最久未使用): 訪問字段記錄頁面自上次被訪問以來經歷的時間; 換出訪問字段值最大的頁面.
LFU(最近最少使用): 在一定間隔內訪問時訪問位記為 “1”, 否則記為 “0”; 換出 FIFO 下訪問位值為 “0” 的頁面.
Clock/NRU(最近未使用): 某頁被訪問時訪問位記位 “1”; 缺頁時將 FIFO 下訪問位值為 “1” 的頁面修改為 “0”, 直到第一個訪問位值為 “0” 的頁面換出.
改進型 Clock: 換出已修改頁面代價較大; 訪問位 $A = 1$ 表示最近被訪問, 修改位 $M = 1$ 表示最近被修改; (1) 當前位置開始掃描尋找 $A = 0$ 且 $M = 0$ 的第一類頁面, 失敗時繼續 (2); (2) 重新掃描尋找 $A = 0$ 且 $M = 1$ 的第二類頁面, 并將途中所有頁面 $A$ 置為 “0”, 失敗時重復 (1).

訪存情況	訪問有效時間(EAT)
被訪問頁在內存中, 對應頁表項在快表中	$\lambda+t$ , $\lambda$ 為查找快表時間, $t$ 為訪問實際物理地址時間
被訪問頁在內存中, 對應頁表項不在快表中	$2(\lambda+t)$
被訪問頁不在內存中	$\phi+2(\lambda+t)$ , $\phi$ 為缺頁中斷處理時間
無快表	$2 t$
僅考慮命中率	$\alpha(\lambda+t)+2(1-\alpha)(t+\lambda)$ , $\alpha$ 為命中率
僅考慮缺頁率	$t+f(\phi+t)+(1-f)t$ , $f$ 為缺頁率
考慮命中率及缺頁率	$\lambda+\alpha t+(1-\alpha)[t+f(\phi+\lambda+t)+(1-f)(\lambda+t)]$

4 并發

并發: 微觀上快速交替執行, 宏觀上并行.
同步: 并發執行的多個進程間按照一定規則或時序共享系統資源, 使程序執行具有可再現性.
臨界資源: 一次僅允許一個進程使用的資源.
臨界區: 進程中訪問臨界資源的代碼段.
同步規則: 空閑讓進, 忙則等待, 有限等待, 讓權等待(不"忙等": 不能進入臨界區時立即釋放虛擬機).
硬件實現: 關中斷; Test-and-Set/TS/TSL 或 Swap/Exchange/XCHG 指令(“忙等”).

// 整型信號量: 存在"忙等"
// P 操作: 請求資源
void wait(semaphore S){while(S<=0);S--
}
// V 操作: 釋放資源
void signal(semaphore S){S++;
}

// 記錄型信號量: 讓權等待
typedef struct {int value; // 正時表示剩余資源數量, 負時表示等待進程數struct process_control_block *list; // 進程等待隊列
} semaphore;
// P 操作
void wait(semaphore *S){S->value--;if(S->wait<0) block(S->list); // 沒有資源時當前進程加入到等待隊列
}
// V 操作
void signal(semaphore *S){S->value++;if(S->value<=0) wakeup(S->list); // 等待隊列還有進程時喚醒隊列中的進程
}

// AND 型信號量: 進程需要多個不同臨界資源
// P 操作
void Swait(semaphore S1, ..., semaphore Sn){while(1){if(S1>=1 && ... && Sn>=1){S1--, ..., Sn--;break;} else /* 進程加入第一個沒有剩余資源關聯的等待隊列中 */}
}
// V 操作
void Ssignal(semaphore S1, ..., semaphore Sn){while(1){S1++, ..., Sn++;wakeup(S1); ... ; wakeup(Sn); // 所有資源關聯的等待隊列還有進程時喚醒隊列中的進程}
}

// 信號量集: 每類臨界資源有多個
// S 資源剩余數, t 資源分配下限(S >= t 時才分配), d 進程對資源需求量(S -= d)
void Swait(semaphore S1, semaphore t1, semaphore d1, ...);
void Ssignal(semaphore S1, semaphore d1, ...);Swait(S, d, d); // 一類資源但有多個
Swait(S, 1, 1); // S > 1 時退化為記錄型, S = 1 時退化為整型
Swait(S, 1, 0); // 可控開關: S >= 1 時允許多個進程進入某特定區; S = 0 后阻止所有進程進入

// 進程互斥
semaphore mutex = 1;  // 互斥
void Pi(){while(1){wait(mutex);/* 臨界代碼 */signal(mutex);}
}

// 生產者-消費者問題
semaphore mutex = 1 // 緩沖區互斥訪問
semaphore empty = N // 空閑緩沖區數量
semaphore full = 0 // 產品數量
// 生產進程一直向緩沖區輸入直至緩沖區滿
void producer(){while(1){/* 生產一個產品 */wait(empty);wait(mutex);/* 該產品放入緩沖區 */signal(mutex);signal(full);}
}
// 消費進程一直從緩沖區輸出直至緩沖區空
void consumer(){while(1){wait(full);wait(mutex);/* 從緩沖區取走一個產品 */signal(mutex);signal(empty);}
}

// 讀者-寫者問題
semaphore wmutex = 1; // 共享文件互斥訪問
semaphore rmutex = 1; // readcount 互斥訪問
semaphore readcount = 0; // 訪問共享文件的讀進程數量
// 多個讀進程可同時讀共享對象
void reader(){while(1){wait(rmutex);if(readcount == 0) wait(wmutex); // 第一個讀進程讀前加鎖readcount++;signal(rmutex);/* 讀文件 */wait(rmutex);readcount--;if(readcount == 0) signal(wmutex); // 最后一個讀進程讀后解鎖signal(rmutex);}
}
// 讀進程均和寫進程互斥
void writer(){while(1){wait(wmutex);/* 寫文件 */signal(wmutex);}
}

// 哲學家進餐問題
// 5 個哲學家中間有 5 只筷子, 僅當哲學家同時拿起左右 2 只筷子時才可以進餐
semaphore chopstick[5] = {1, 1, 1, 1, 1};
// 直接拿左拿右時會出現死鎖
void Phi(int i){wait(chopsitck[i]);wait(chopstick[(i + 1) % 5]);/* 吃飯 */signal(chopsitck[i]);signal(chopstick[(i + 1) % 5]);
}
// 最多只允許 4 個哲學家同時進餐
// 僅當哲學家可以同時拿起左右 2 只筷子時才可以拿筷子(任意時刻至多有 1 個哲學家嘗試拿筷子)
semaphore mutex = 1;
void Phi(int i){wait(mutex);wait(chopsitck[i]);wait(chopstick[(i + 1) % 5]);signal(mutex);/* 吃飯 */signal(chopsitck[i]);signal(chopstick[(i + 1) % 5]);
}
// 奇數號哲學家先拿左邊筷子再拿右邊筷子, 偶數號相反

死鎖: 一組進程中每個進程都在等待僅由該組中其他進程才能引發的事件.
產生原因: 競爭不可搶占性資源; 競爭可消耗資源; 進程推進順序不當.
必要條件: 互斥條件; 請求和保持條件(新請求的資源被占用時, 請求阻塞但不釋放已占用資源); 不可搶占條件(已占用資源只能在進程使用完后自行釋放); 循環等待條件(存在進程-資源循環鏈).
處理方法: 預防(設置限制以破除必要條件); 避免(不設限但資源分配時檢查); 檢測解除.
安全狀態: 系統能按照某種進程推行順序(安全序列)為每個進程分配所需資源, 直至滿足每個進程對資源的最大需求, 使每個進程均可順利完成.
死鎖避免(銀行家算法): 系統始終處于安全狀態即不會產生死鎖.
資源分配圖: 圓圈表示進程, 方框表示資源, 請求邊由進程指向資源, 分配邊由資源指向進程.
死鎖定理: 資源分配圖不可完全簡化時存在死鎖.
解除方法: 資源剝奪; 終止/撤銷進程; 進程回退.

數據結構
Available[m] 每類資源數量
Max[n][m] 每個進程所需的每類資源最大數量
Allocation[n][m] 當前每個進程已獲得的每類資源數量
Need[n][m] 當前每個進程還需獲得的每類資源數量
關系: Need[i][j] = Max[i][j] - Allocation[i][j]銀行家算法
RequestPi[m] 當前進程 Pi 資源請求每類資源數量
① 請求資源數不得超過宣布的最大值 RequestPi[j] <= Need[i][j] 
② 請求資源數不得超過剩余資源數 RequestPi[j] <= Available[j]
③ 嘗試分配資源并執行安全性檢查
Available[j] = Available[j] - RequestPi[j]
Allocation[i][j] = Allocation[i][j] - RequestPi[j]
Need[i][j] = Need[i][j] - RequestPi[j]安全性檢查
Work[m] = Available[m] 可提供給進程繼續運行所需的各類資源數目
Finish[n] 是否有足夠資源分配給進程使之運行完成
① 進程集合中找到一個進程滿足 Finish[i] = false, Need[i][j] <= Work[j]; 否則轉到 ③
② 該進程獲得資源后可順利運行完成, 并釋放獲取的資源, 并轉到 ①
Work[j] = Work[j] + Allocation[i][j]
Finish[i] = true;
③ 所有進程 Finish[i] = true 時處于安全狀態; 否則不安全

5 I/O

I/O 系統基本功能: 隱藏物理設備細節; 設備無關性/獨立性; 提高處理機和設備利用率; 控制設備; 確保設備共享正確性; 錯誤處理.
層次結構: 用戶層軟件(產生 I/O 請求; 格式化 I/O; SPOOLing) $\leftrightarrows$ (I/O 系統結構) 設備獨立性軟件(映射; 保護; 分塊; 緩沖; 分配) $\leftrightarrows$ 設備驅動程序(設置寄存器; 狀態檢查) $\leftrightarrows$ 中斷處理程序 $\leftrightarrows$ (RW/HW 接口, 軟件/硬件接口, 通道) 設備控制器 $\leftrightarrows$ (通路) 設備.
系統接口: 塊設備接口; 流設備接口(字符); 網絡通信接口.
設備: 存儲, I/O; 輸入, 輸出, 交互; 低速, 中速, 高速; 塊, 字符.
控制器基本功能: 接收和識別命令; 數據交換; 識別和報告設備狀態; 地址識別; 數據緩沖區; 差錯控制.
控制器組成: 與處理機接口(數據線, 地址線, 控制線); I/O 邏輯; 與設備接口(數據, 狀態信息, 控制信息).
通道: 專門負責 I/O 的處理機; 指令類型單一, 與 CPU 共享內存.
通道類型(信息交換方式): 字節多路(輪轉掃描, 不適合高速設備); 數組選擇(僅有一個分配型子通道, 設備獨占, 利用率低); 數組多路(多個非分配型子通道分時并行).
“瓶頸” 問題: 通道價格昂貴, 設置數量少而成為 I/O 瓶頸致使系統整體吞吐量下降; 增加設備到主機間通路而無需增加通道.
中斷處理程序: 響應中斷信號 $\to$ 保存現場 $\to$ 轉入設備處理程序 $\to$ 中斷處理 $\to$ 恢復現場并退出中斷.
驅動程序功能/過程: 抽象要求轉換為具體要求 $\to$ 校驗服務請求 $\to$ 檢查設備狀態 $\to$ 傳遞必要參數 $\to$ 啟動設備.
驅動程序特點: 設備無關軟件和控制器間通信轉換; 不同類型設備配置不同; 與設備采用的控制方式緊密相關; 基本部分固化在 ROM(只讀存儲器)中; 應允許可重入.
控制方式: 程序查詢(等待設備就緒定期詢問); 中斷(設備就緒時發出中斷請求; 以字為單位傳輸數據); DMA(直接存儲器訪問; 以塊為單位傳輸數據).

DMA: DMA請求 $\to$ 預處理 $\to$ 數據傳送 $\to$ 后處理.
預處理: 主存起始地址 $\to$ AR(主存地址計數器), I/O 設備地址 $\to$ DAR(設備地址計數器), 傳送長度 $\to$ WC(傳送長度計數器), 啟動 I/O 設備.
數據傳送: I/O 設備向數據緩沖器寫入數據直至將要溢出.
后處理: 將要溢出時發起中斷請求, CPU 或主存讀取數據.
傳送方式: 停止 CPU 訪存; DMA 和 CPU 交替訪存; 周期挪用/竊取(CPU 正在訪存時等待存取周期結束; 同時請求訪存時 DMA 優先).

I/O 重定向: 用于 I/O 操作的設備可以更換而不必改變應用程序.
設備無關性/獨立性: 應用程序獨立于具體使用的物理設備.
設備無關軟件: 設備驅動程序的統一接口; 緩沖管理; 差錯控制; 對獨立設備的分配與回收; 獨立于設備的邏輯數據塊.
SDT(系統設備表): 類型, 標識符, 指向 DCT 指針, 驅動程序入口地址.
DCT(設備控制表): 類型, 標識符, 狀態, 指向 COCT 指針, 重復執行次數/時間, 設備隊列隊首指針.
COCT(控制器控制表): 標識符, 狀態, 指向 CHCT 指針, 控制器隊列隊首指針, 控制器隊列隊尾指針.
CHCT(通道控制表): 標識符, 狀態, 指向 COCT 指針, 通道隊列隊首指針, 通道隊列隊尾指針.
設備分配考慮因素: 設備固有屬性; 分配算法; 安全性.
獨占設備分配程序: 分配設備 $\to$ 分配控制器 $\to$ 分配通道.
LUT(邏輯設備表): 實現邏輯設備名到物理設備名映射; 邏輯設備名, 物理設備名, 驅動程序入口地址.

假脫機技術(SPOOLing): 利用多道程序技術模擬脫機 I/O 系統, 以緩和主機高速性和設備低速性間的矛盾, 實現主機和設備的并行.
構成: 輸入井和輸出井(磁盤上開辟兩個區域模擬脫機輸入和脫機輸出); 輸入緩沖區和輸出緩沖區(內存中開辟兩個區域緩和主機和設備速度間的矛盾); 預輸入進程和輸出進程(模擬脫機輸入和脫機輸出時的外圍控制機); 井管理程序(控制作業和磁盤井之間的信息交換).
特點: 提高 I/O 速度; 獨占設備改為共享設備; 實現虛擬設備.
守護進程: 獨占設備改為共享設備時, 配置一個守護進程和假脫機文件隊列; 守護進程是允許使用該獨占設備的唯一進程, 使用設備時將文件放入假脫機文件隊列并喚醒守護進程, 守護進程執行完后繼續睡眠.
緩沖區引入原因: 緩和主機和設備速度間矛盾; 減少對 CPU 中斷頻率, 放寬對 CPU 中斷響應時間的限制; 解決數據粒度不匹配問題; 提高主機和設備間并行性.
單緩沖區: 處理每塊數據用時 $max\{C,T\}+M$ , 磁盤將該塊數據輸入緩沖區時間為 $T$ , 緩沖區中數據傳送到用戶區時間為 $M$ , CPU 處理數據時間為 $C$ .
雙緩沖區/緩沖區對換: 數據輸入第一緩沖區, 裝滿后轉向第二緩沖區, 此時第一緩沖區數據傳送到用戶區并由 CPU 處理; 處理每塊數據用時 $max\{C+M,T\}$ .
環行緩沖區: 多個大小相同的緩沖區組成環形隊列; 隊尾指針指向下一個空的緩沖區, 隊首指針指向計算進程下一個可用的已裝滿的緩沖區; 隊尾指針追上隊首指針時, 所有可用緩沖區均裝滿, 阻塞輸入進程; 隊首指針追上隊尾指針時, 已處理完所有緩沖區數據, 阻塞計算進程.
緩沖池: 管理多個緩沖區, 緩沖首部用于標識和管理, 緩沖體用于存放數據; 空白緩沖隊列, 輸入隊列, 輸出隊列; 收容輸入, 提取輸入, 收容輸出, 提取輸出.

磁盤組成: 盤面 $>$ 磁道(間隔) $>$ 扇區(間隔)控制信息 $+$ 數據 $>$ 字段(間距); 存儲數據前需將磁盤低級格式化; 高級格式化以設置引導塊, 空閑存儲管理, 根目錄, 文件系統.
訪問時間: 尋道時間 $T_s$ (磁頭移動到指定磁道) $+$ 旋轉延遲時間(指定扇區移動到磁頭下) $T_{\tau}+$ 傳輸時間 $T_t$ .
早期調度: FCFS(先來先服務); SSTF(最短尋道時間優先).
掃描調度: SCAN(掃描/電梯; 磁頭移動方向且距離最近優先, 移動方向無數據時切換方向); CSCAN(循環掃描; 單向移動且距離最近優先); NStepSCAN(請求隊列分成 $N$ 個子隊列, 每個子隊列使用 FCFS, 新請求放入其他隊列, 避免磁臂"粘著"); FSCAN(請求隊列分為當前隊列和掃描期間新請求的待處理隊列, 子隊列使用 SCAN).
提高磁盤 I/O 速度途徑: 高速緩存; 提前讀, 延遲寫, 優化物理塊分布, 使用虛擬盤; RAID(廉價磁盤冗余陣列).