分時系統(tǒng)

1. 多路性：系統(tǒng)允許將多臺終端同時連接到一臺主機上迈倍，并按分時原則為每個用戶服務(wù)
2. 獨立性：各用戶在各自的終端上操作互不影響
3. 及時性：用戶的請求能在短時間內(nèi)得到響應
4. 交互性：用戶可通過終端與系統(tǒng)進行廣泛的人機對話（即請求系統(tǒng)提供各種服務(wù)）

開始截止時間：指某任務(wù)在某時間以前必須開始執(zhí)行
完成截止時間：指某任務(wù)在某時間以前必須完成
硬實時任務(wù)：必須滿足任務(wù)對截至時間的要求拉宗，否則可能出現(xiàn)難以預測的后果
軟實時任務(wù)：有截止時間但并不嚴格赔桌，偶爾錯過了也不會造成什么大的影響

實時系統(tǒng)與分時系統(tǒng)特征的比較：

1. 多路性：分時系統(tǒng)中的多路性都表現(xiàn)為系統(tǒng)按分時原則為多個終端用戶服務(wù)；實時控制系統(tǒng)的多路性則是指系統(tǒng)周期性的對多路現(xiàn)場信息進行采集，以及對多個對象或多個執(zhí)行機構(gòu)進行控制
2. 獨立性：二者差不多
3. 及時性：一個是依據(jù)人所能接受等待的時間確定君躺，一個是以控制對象所要求的截止時間來確定
4. 交互性：實時系統(tǒng)中，人與系統(tǒng)的交互性僅局限于訪問系統(tǒng)中某些特定的專用服務(wù)程序
5. 可靠性：分時系統(tǒng)要求系統(tǒng)可靠开缎，而實時系統(tǒng)要求系統(tǒng)高度可靠

• 單用戶單任務(wù)操作系統(tǒng)：CP/M MS-DOS
• 單用戶多任務(wù)操作系統(tǒng)：window
• 多用戶多任務(wù)操作系統(tǒng)：UNIX LINUX

• 并行性：指兩個或多個事件在同一時刻發(fā)生
• 并發(fā)性：指兩個或多個事件都在同一時間間隔內(nèi)發(fā)生

并發(fā)和共享時多用（多任務(wù)）OS的兩個最基本的特征

• 時分復用技術(shù)
• 空分復用技術(shù)
  時分復用技術(shù)（多道程序技術(shù)）是通過利用處理機的空閑時間運行其他程序棕叫，提高了運行處理機的利用率，空分復用技術(shù)奕删，則是利用存儲器的空閑時間分區(qū)域存放和運行其他的多道程序俺泣，以此來提高內(nèi)存的利用率

處理及管理功能：

1. 進程控制：創(chuàng)建進程，分配資源完残，結(jié)束進程等
2. 進程同步
3. 進程通信
4. 調(diào)度

微內(nèi)核OS系統(tǒng)

基本概念

1. 足夠小的內(nèi)核
2. 基于客戶/服務(wù)器模式
3. 應用“機制與策略分離”原理
4. 采用面向?qū)ο蠹夹g(shù)

前驅(qū)圖

有向無循環(huán)圖伏钠，可記為DAG：用于描述進程之間執(zhí)行的先后順序
進程（或程序）之間的前驅(qū)關(guān)系可用“->”表示

如果進程Pi和Pj存在著前驅(qū)關(guān)系，可表示為（Pi谨设，Pj）屬于->熟掂，也可以寫作Pi->Pj
表示Pj開始執(zhí)行前Pi必須完成，此時稱Pi是Pj的直接前驅(qū)扎拣，Pj是Pi的直接后繼
沒有前驅(qū)的結(jié)點稱為初始結(jié)點赴肚，沒有后繼的結(jié)點稱為中止結(jié)點

程序順序執(zhí)行時的特征

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

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

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

進程的定義

進程控制塊：PCB
由程序段、相關(guān)的數(shù)據(jù)段和PCB三部分便構(gòu)成了進程實體（又稱進程映像）二蓝，簡稱為進程
==創(chuàng)建進程實質(zhì)是創(chuàng)建進程實體中P的CB誉券，而撤銷進程實質(zhì)就是撤銷進程的PCB==
進程的特征：

1. 動態(tài)性
2. 并發(fā)性
3. 獨立性
4. 異步性

進程的三種基本狀態(tài)

1. 就緒狀態(tài)（Ready）
2. 執(zhí)行狀態(tài)（Running）
3. 阻塞狀態(tài)（Block）

就緒狀態(tài) 被進程調(diào)度 執(zhí)行
執(zhí)行 時間片用完 就緒
阻塞 I/O完成 就緒
執(zhí)行 I/O請求 阻塞

創(chuàng)建狀態(tài)：

• 申請一個空白的PCB，并向PCB中填寫用于控制和管理進程的信息
• 為進程分配運行時所必須的資源
• 把繼承轉(zhuǎn)入就緒狀態(tài)并插入就緒隊列中刊愚，若進程所需資源尚不能滿足踊跟，則其仍為創(chuàng)建狀態(tài)
  終止狀態(tài)
• 等待操作系統(tǒng)進行善后處理
• 將其PCB清零，并將PCB空間返還系統(tǒng)

掛起操作的引入（將進程由內(nèi)存移到外存）：基于系統(tǒng)和用戶的如下需要

1. 終端用戶的需要
2. 父進程的需要
3. 負荷調(diào)節(jié)的需要
4. 操作系統(tǒng)的需要

引入掛起原語操作后三個進程狀態(tài)的轉(zhuǎn)換

掛起原語Suspend 激活原語Active

1. 活動就緒->禁止就緒
2. 活動阻塞->靜止阻塞
3. 靜止就緒->活動就緒
4. 靜止阻塞->活動阻塞

PCB的具體作用

1. 作為獨立運行基本單位的標志（==PCB是進程存在于系統(tǒng)中的唯一標識==）
2. 能實現(xiàn)間斷性運行方式
3. 提供進程管理所需要的信息
4. 提供進程調(diào)度所需要的信息
5. 實現(xiàn)與其他進程的同步與通信

進程控制塊中的信息：

1. 進程標識符
   1. 外部標識符
   2. 內(nèi)部標識符
2. 處理及狀態(tài)
3. 進程調(diào)度信息
4. 進程控制信息

進程控制塊的組織方式：1.線性方式 2.鏈接方式 3.索引方式

系統(tǒng)操作內(nèi)核

• 系統(tǒng)態(tài)（管態(tài)）
• 用戶態(tài)（目態(tài)）

支撐功能

• 中斷處理
• 時鐘管理
• 原語管理

資源管理功能

• 進程管理
• 存儲器管理
• 設(shè)備管理

引起進程終止的事件

• 正常結(jié)束
• 異常處理
• 外界干預

終止進程時還應將其所有子孫進程都終止鸥诽，以防其成為不可控的進程商玫，將所有終止進程的資源歸還給其父進程或系統(tǒng)

兩種形式的制約關(guān)系

1. 間接相互制約關(guān)系（互斥）

對于臨界資源（又稱為共享資源箕憾，互斥資源）必須保證多個進程對之只能互斥地訪問

2. 直接相互制約關(guān)系（同步）

多個進程為完成同一項任務(wù)而相互合作

由于存在著上述兩類相互制約關(guān)系，進程在運動過程中能否獲得處理及運行與以怎樣的熟讀運行拳昌，并不能由進程自身所控制厕九，即進程的異步性

臨界區(qū)：在每個進程中訪問臨界資源的那段代碼稱為臨界區(qū)

一個訪問臨界資源的循環(huán)進程描述：

while(TRUE)
{
    進入?yún)^(qū)
    臨界區(qū)
    推出區(qū)
    剩余區(qū)
}

同步機制應遵循的規(guī)則

• 空閑讓進
• 忙則等待
• 有限等待
• 讓權(quán)等待

P、V操作(原子操作)

wait(S) :P （S減1）
signal(S):V （S加1）

1. 整型信號量（未遵循“讓權(quán)等待”）
2. 信號記錄量
3. AND型信號量
4. 信號量集

AND同步機制的基本思想：將繼承在整個運行過程中需要的所喲資源地回，一次性全部分配給進程扁远，待進程使用完后在一起釋放

利用信號量實現(xiàn)進程互斥
為使多個進程能互斥地訪問某臨界資源，只需為該資源設(shè)置--互斥信號量mutex刻像，并設(shè)其初始值為1畅买，然后將進程訪問該資源的臨界區(qū)CS置于wait(mutex)和signal(mutex)操作之間即可。
利用信號量實現(xiàn)前驅(qū)關(guān)系：

實例：實現(xiàn)下圖的前驅(qū)關(guān)系  
p1(){S1;signal(a);siganl(b);}  
p2(){wait(a);S2;signal(c);signal(d);}  
p3(){wait(b);S3;signal(e)}  
p4(){wait(c);S4;signal(f)}  
p5(){wait(d);S5;signal(g)}  
p6(){wait(e);wait(f);wait(g);S6;}  
main(){
    semaphore a,b,c,d,e,f,g;
    a.value = b.value = c.value = 0;
    d.value = e.value =0;
    f.value = gi.value = 0;
    cobegin
    p1();p2();p3();p4();p5();p6();
    coend
}

graph LR
s1-->s2
s2-->s5
s2-->s4
s4-->s6
s5-->s6
s1-->s3

進程的兩個基本屬性：

1. 進程是一個可擁有資源的獨立單位
2. 進程是一個可獨立調(diào)度和分配的基本單位

線程--作為調(diào)度和分派的基本單位

不同于進程细睡，將 調(diào)度和分派 與 擁有資源 谷羞，這兩個屬性分開

進程與線程的比較

1. 調(diào)度的基本單位：
   • 傳統(tǒng)的OS中，進程是作為獨立調(diào)度和分派的基本單位溜徙，每次被調(diào)度時湃缎，都需要進行上下文切換開銷較大
   • 在引入線程的OS中，把賢臣作為調(diào)度和分派的基本單位蠢壹，因而線程是能獨立運行的基本單位嗓违，當線程切換時，僅需保存和設(shè)置少量寄存器內(nèi)容图贸，切換代價遠低于進程
   • ==在同一進程中蹂季，線程的切換不會引起線程的切換，但從一個進程中的線程切換到另一個線程中的線程時疏日，必然會引起進程的切換==
2. 并發(fā)性：不僅線程之間可以并發(fā)執(zhí)行偿洁，一個進程中的多個線程間亦可并發(fā)執(zhí)行
3. 擁有資源：線程本身并不擁有系統(tǒng)資源，而是僅有一點必不可少的沟优、能保證獨立運行的資源
4. 獨立性：線程之間的獨立性低于進程之間的獨立性涕滋，因為每個進程都擁有一個獨立的地址控件和其他資源，除了共享變量外挠阁，不允許其他進程的訪問
5. 系統(tǒng)開銷：線程開銷低于進程開銷
6. 支持多處理機系統(tǒng)：對于多線程進程宾肺，就可以將一個進程中的多各線程分配到多個處理及上，使它們并行執(zhí)行鹃唯，加速進程的完成

線程運行的三個狀態(tài)：

1. 執(zhí)行狀態(tài)
2. 就緒狀態(tài)
3. 阻塞狀態(tài)

線程控制塊（TCB）

處理機調(diào)度的層次

1. 高級調(diào)度（又稱為 長程調(diào)度 或 作業(yè)調(diào)度 ）
   • 調(diào)度對象為 ==作業(yè)==
   • 外存 調(diào)入 內(nèi)存
2. 低級調(diào)度（又稱為 進程調(diào)度 或 短程調(diào)度）
   • 調(diào)度對象 ==進程==
   • 內(nèi)存中處理（分配處理機）
3. 中級調(diào)度（內(nèi)存調(diào)度）
   • 目的：提高內(nèi)存利用率和系統(tǒng)吞吐量
   • 內(nèi)存 調(diào)出 外存

進程調(diào)度的運行頻率最高

CPU的利用率 = cpu有效工作時間/（cpu有效工作時間+cpu空閑等待時間）

分時系統(tǒng)的目標：

• 響應時間塊
• 均衡性

實時系統(tǒng)的目標

• 截止時間的保證
• 可預測性

作業(yè)和作業(yè)步

• 作業(yè)：一個比程序更為廣泛的概念爱榕。不僅包含了通常的程序和數(shù)據(jù)瓣喊，而且還應配有一份作業(yè)說明書坡慌，系統(tǒng)根據(jù)說明書來對程序的運行進行控制。在批處理系統(tǒng)中藻三，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存
• 作業(yè)步：作業(yè)的么一個加工步驟稱為 一個作業(yè)步

作業(yè)控制塊（JCB）
作業(yè)運行的三個階段和三種狀態(tài)

1. 收容階段：后備狀態(tài)
2. 運行階段：運行狀態(tài)
3. 完成階段：完成狀態(tài)

作業(yè)的調(diào)度算法

1. 先來先服務(wù)調(diào)度算法（FCFS）
2. 短作業(yè)優(yōu)先的調(diào)度算法（SJF）
3. 優(yōu)先級調(diào)度算法（PSA）
4. 高響應比優(yōu)先調(diào)度算法（HRRN）

   優(yōu)先權(quán) = （等待時間+要求服務(wù)時間）/要求服務(wù)時間
   - 如果作業(yè)的等待時間相同洪橘，則要求服務(wù)的時間啊俞短跪者，其優(yōu)先權(quán)俞高
   - 當要求服務(wù)的時間相同時，作業(yè)的優(yōu)先權(quán)又決定于其等待的時間
   - 對于長作業(yè)的優(yōu)先級可以雖等待時間的增加而提高

進程調(diào)度的任務(wù)：

1. 保存處理間的現(xiàn)場信息
2. 按某種算法選取進程
3. 把處理器分配給進程

進程調(diào)度方式：

1. 非搶占方式
   • 正在執(zhí)行的進程運行完畢熄求，或因發(fā)生某時間而使其無法再繼續(xù)運行
   • 正在執(zhí)行中的進程因提出I/O請求而暫停執(zhí)行
   • 在進程通信或同步過程中渣玲，執(zhí)行了某種原語操作
2. 搶占式方式
   • 優(yōu)先權(quán)原則
   • 短進程優(yōu)先原則
   • 時間片原則

輪轉(zhuǎn)調(diào)度算法

實時調(diào)度的實現(xiàn)：
提供必要信息

1. 就緒時間
2. 開始截止時間和完成截止時間
3. 處理時間
4. 資源要求
5. 優(yōu)先級

最低松弛度優(yōu)先算法（LLF）

松弛度最低的任務(wù)排在最前面（緊急程度越高，松弛度越低）
松弛度 = 必須完成時間 - 其本身的運行時間 - 當前時間

優(yōu)先級倒置

例如：高優(yōu)先級的進程P3由于和低優(yōu)先級P1的共享資源的原因弟晚，必須等待P1運行完成后才能運行忘衍，而二者之間，由于優(yōu)先級調(diào)度算法卿城，P2搶占了P1資源枚钓，而P3又搶占了P2的資源，導致P3進程因P1進程被阻塞了瑟押，又由于P2的存在搀捷，而延長了P3被阻塞的時間，只有等待P2進程運行完成后多望，p1運行嫩舟，再最后P3運行

死鎖

死鎖的定義

如果一組進程中的每一個進程都在等待僅由改組進程中的其他進程才能引發(fā)的四件，那馬改組進程是死鎖的
產(chǎn)生死鎖的必要條件

1. 互斥條件
2. 請求和保持條件
3. 不可搶占條件
4. 循環(huán)等待條件

處理死鎖的方法

1. 預防死鎖
2. 避免死鎖
3. 檢測死鎖
4. 解除死鎖

銀行家算法

1. 數(shù)據(jù)結(jié)構(gòu)
   1. 可利用資源向量Avaliable
   2. 最大需求矩陣Max
   3. 分配矩陣Allocation
   4. 需求矩陣Need

死鎖定理：
S為死鎖狀態(tài)的充分條件是：當且僅當S狀態(tài)的資源分配圖是不可完全簡化的怀偷。

該充分條件被稱為：死鎖定理

常采用的解除死鎖的兩種方法：

1. 搶占資源：從一個或多個進程中搶占足夠數(shù)量的資源家厌，分配給死鎖進程，以解除死鎖狀態(tài)
2. 終止（撤銷）進程：終止一個或多各死鎖進程椎工，直至打破循環(huán)環(huán)路像街，是系統(tǒng)從死鎖狀態(tài)中走出

用戶程序要在系統(tǒng)中運行，必須先將它裝入內(nèi)存晋渺，然后再將其轉(zhuǎn)變?yōu)橐愿骺梢詧?zhí)行的程序镰绎，通常要經(jīng)過以下幾個步驟：

1. 編譯：對源程序進行編譯，形成若干個目標模塊
2. 鏈接：由鏈接程序?qū)⒕幾g后形成的一組目標模塊以及它們所需要的庫函數(shù)鏈接一起木西，形成一個完整的裝入模塊
3. 裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存

重定位：在裝入時對目標程序中指令和數(shù)據(jù)地址的修改過程稱為 重定位

連續(xù)分配方式可分為四類：

• 單一連續(xù)分配
• 固定分區(qū)分配
• 動態(tài)分區(qū)分配
• 動態(tài)可重定位分區(qū)分配算法

基于順序搜索的動態(tài)分區(qū)分配算法

• 首次適應算法（FF）
• 循環(huán)首次適應算法（NF）
• 最佳適應算法（BF）
• 最壞適應算法（WF）

動態(tài)重定位：程序在執(zhí)行時畴栖，真正訪問的內(nèi)存地址是相對地址與重定位寄存器終端地址相加而形成的

根據(jù)在離散分配時所分配地址空間的基本單位的不同，又可以將離散分配分為以下三種：

• 分頁存儲管理方式

相應的將內(nèi)存空間分為若干個物理塊或頁框八千，頁和塊的大小相同

• 分段存儲管理方式
• 段頁式存儲管理方式

分頁地址中的地址結(jié)構(gòu)：

31 12|11 0
頁號P | 位移量W
前一段位頁號 P吗讶，后一部分為位移量W，即頁內(nèi)地址

頁表的作用是：實現(xiàn)從頁號到物理塊號的地址映射恋捆。

由于頁表是存放在內(nèi)存中的照皆，這使CPU在沒存取一個數(shù)據(jù)時，都要兩次訪問內(nèi)存
第一次是訪問內(nèi)存中的頁表沸停，從中找到指定頁的物理塊號膜毁，再將塊號與頁內(nèi)偏移量W拼接，形成物理地址。第二次訪問內(nèi)存時瘟滨，才是從第一次所得地址中獲得所需數(shù)據(jù)候醒。

為了提高地址變換速度，可在地址變換機構(gòu)中共增設(shè)一個具有并行查尋能力的特殊高速和緩沖寄存器杂瘸，又稱為”聯(lián)想寄存器“倒淫，或稱為”快表“
內(nèi)存的有效訪問時間（EAT)：從進程發(fā)出指定邏輯地址的訪問請求，經(jīng)過地址變換败玉，到在內(nèi)存中找到對應的實際物理地址單位并取出數(shù)據(jù)敌土，所需要花費的總時間，稱為內(nèi)存的有效訪問時間

EAT = t+t = 2t t為訪問一次內(nèi)存所需的時間

分頁和分段的主要區(qū)別

1. 頁是信息的物理單位运翼，分段存儲管理方式中的段則是信息的邏輯單位
2. 頁的大小固定且由系統(tǒng)決定纯赎，段的長度卻不固定，決定于用戶所編寫的程序南蹂，通常由編譯程序在對源程序在對源程序進行編譯時犬金，根據(jù)信息的性質(zhì)來劃分
3. 分頁的用戶程序地址空間是一維的，完全是系統(tǒng)的行為六剥，而分段是用戶的行為晚顷，故在分段系統(tǒng)中，用戶程序的地址空間是二維的

段頁是存儲管理方式：
地址結(jié)構(gòu)由段號疗疟，段內(nèi)頁號该默，頁內(nèi)地址三部分組成

獲得一條指令或數(shù)據(jù)，需三次訪問內(nèi)存策彤。第一次訪問內(nèi)存中的段表栓袖，獲得頁表始值，第二次訪問內(nèi)存中的頁表店诗，從中取出該頁所在的物理塊號裹刮，并將該塊號和頁內(nèi)地址一起形成指令或數(shù)據(jù)的物理地址，第三次訪問才是真正的數(shù)據(jù)或指令

虛擬存儲器的基本工作情況：基于局部原理庞瘸，應用程序在運行之前沒有必要將之全部裝入內(nèi)存捧弃，而僅需將那些當前要運行的少數(shù)頁面或段先裝入內(nèi)存便可運行，其余部分暫留在攀上擦囊。程序在運行時违霞，如果他要訪問的頁已調(diào)入內(nèi)存，便可繼續(xù)執(zhí)行下去瞬场，但如果程序索要訪問的頁尚未調(diào)入內(nèi)存买鸽，便發(fā)出缺頁中斷請求，此時OS將利用請求調(diào)頁功能將它們調(diào)入內(nèi)存贯被，以使進程能繼續(xù)執(zhí)行下去眼五。如果此時內(nèi)存已滿妆艘，無法在裝入新的，還需使用頁的置換功能弹砚，將內(nèi)存匯總暫時不用的頁調(diào)至盤上双仍，騰出所需的空間枢希，調(diào)入要訪問的頁入內(nèi)存桌吃。

這樣，便可使一個大的用戶程序在較小的內(nèi)存空間中運行苞轿，也可在內(nèi)存中同時裝入更多的進程茅诱，使它們并發(fā)執(zhí)行

虛擬存儲器：具有請求調(diào)入功能和置換功能，能從邏輯上對應內(nèi)存容量加以擴充的一種存儲器系統(tǒng)
虛擬存儲器的特征：

1. 多次性

可以分次將程序和數(shù)據(jù)放入內(nèi)存

2. 對換性

程序運行期間搬卒，允許將暫不使用的代碼和數(shù)據(jù)從內(nèi)存調(diào)至外存的兌換去瑟俭，待以后需要以后再從外存調(diào)入內(nèi)存

3. 虛擬性：從邏輯上擴充內(nèi)存容量，使用戶所看到的內(nèi)存容量遠大于實際內(nèi)存容量

頁面置換算法：

• 最佳置換算法（OPT）

理想上的算法

• 先進先出算法（FIFO）
• 最近最久未使用置換算法（LRU）
• 最近最少使用置換算法（LFU）

產(chǎn)生”抖動“的原因：
同時在系統(tǒng)中運行的進程太多契邀，由此分配給每一個進程的物理塊太少摆寄，不能滿足進程正常運行的基本要求，致使每個進程再運行時坯门，頻繁地出現(xiàn)缺頁微饥，必須請求系統(tǒng)將所缺之頁調(diào)入內(nèi)存，導致調(diào)入調(diào)出的進程數(shù)目增加古戴，使處理及的利用率急劇下降并趨于0

工作集：
指再某段時間間隔里欠橘，進程實際所要訪問頁面的集合。

”抖動“的預防方法

1. 采取局部置換策略：當某進程發(fā)生缺頁時现恼，只能在分配給自己的內(nèi)存空間內(nèi)進行置換肃续，不允許從其他進程去獲得新的物理快
2. 把工作集算法融入到處理機調(diào)度中
3. 利用”L=S“準則調(diào)節(jié)缺頁率

L 是缺頁之間的平均時間 S 是平均缺頁服務(wù)時間（用于置換一個頁面所需的時間）
如果L<<S，則說明缺頁叉袍，缺頁的速度超過磁盤的處理能力

4. 選擇暫停的進程

I/O軟件的層次結(jié)構(gòu)

1. 用戶層I/O軟件：實現(xiàn)用戶交互的接口始锚，用戶可直接調(diào)用該層所提供的、與I/O操作有關(guān)的庫函數(shù)對設(shè)備進行操作

產(chǎn)生I/O請求喳逛，格式化I/O疼蛾，Spooling

2. 設(shè)備獨立性軟件：用于實現(xiàn)用戶程序與設(shè)備驅(qū)動器的統(tǒng)一接口、設(shè)備命名艺配、設(shè)備的保護以及設(shè)備的分配與釋放等察郁，同時為設(shè)備管理和數(shù)據(jù)傳送提供必要的存儲空間

映射、保護转唉、分塊皮钠、緩沖、分配

3. 設(shè)備驅(qū)動程序：與硬件直接相關(guān)赠法，用于具體實現(xiàn)系統(tǒng)對設(shè)備發(fā)出的操作指令麦轰，驅(qū)動I/Oshebei工作的驅(qū)動程序

設(shè)置設(shè)備驅(qū)動器：檢查狀態(tài)

4. 終端處理程序：用于保存被終端進程的CPU環(huán)境乔夯，轉(zhuǎn)入相應的中斷處理程序進行處理，處理完畢再恢復被中斷進程的現(xiàn)場后款侵，返回到被終端的進程

5. 硬件：執(zhí)行I/O操作

I/O系統(tǒng)的分層：

1. 中斷處理程序：處于I/O系統(tǒng)的底層
2. 設(shè)備驅(qū)動程序：處于I/O系統(tǒng)的次底層
3. 設(shè)備獨立性軟性

I/O設(shè)備的類型：

1. 按使用特性分類：
   1. 存儲設(shè)備（外存等）
   2. I/O設(shè)備（鍵盤）
2. 按傳輸速率分類
   1. 低速設(shè)備（鍵盤等）
   2. 中速設(shè)備（打印機等）
   3. 高速設(shè)備（磁帶機等）

中斷和陷入

1. 中斷：CPU對I/O設(shè)備發(fā)來的中斷信號的一種響應
2. 陷入：CPU內(nèi)部時間所引起的中斷

中斷向量表和中斷優(yōu)先級

1. 中斷向量表

為了處理上的方便末荐，通常是為每種設(shè)備配以相應的中斷處理程序，并把該程序的入口地址放在中斷向量表的一個表項中新锈，并為每一個設(shè)備的中斷請求規(guī)定一個中斷號甲脏，直接對應于中斷向量表的一個表項中

2. 中斷優(yōu)先級

對多中斷源的處理方式

1. 禁止（屏蔽）中斷

當處理機再處理一個中斷時，將屏蔽掉所有的中斷妹笆，即對于新到的中斷暫時不理块请，讓它們處于等待狀態(tài)

2. 嵌套中斷
   1. 當同時有多個不同優(yōu)先級的中斷請求時，Cpu響應最高優(yōu)先級的中斷請求
   2. 高優(yōu)先級的中斷請求可以搶占正在運行的低優(yōu)先級中斷的處理及拳缠，類似于基于優(yōu)先級的搶占式進程調(diào)度

DMA工作過程

當CPU要從磁盤讀入以數(shù)據(jù)塊時墩新，便向磁盤控制器發(fā)送一條讀命令。該命令被送入命令寄存器CR中窟坐。同時海渊，需要將本次要讀入數(shù)據(jù)在內(nèi)存的起始目標地址送入內(nèi)存地址寄存器MAR中，將要讀數(shù)據(jù)的字（節(jié)）數(shù)送入數(shù)據(jù)計數(shù)器DC中哲鸳。還需將磁盤中的源地址直接送至DMA控制器的I/O控制邏輯上臣疑。然后啟動DMA控制器進行數(shù)據(jù)傳送。以后帕胆，CPU便可去處理其他任務(wù)朝捆，整個數(shù)據(jù)傳送過程由DMA控制器進行控制。當DMA控制器已從磁盤中讀入一個字（節(jié)）的數(shù)據(jù)懒豹，并送入數(shù)據(jù)寄存器DR后芙盘，再挪用一個存儲走起，將該字（節(jié)）傳送到MAR所指示的內(nèi)存單元中脸秽。然后便對MAR內(nèi)容加1儒老，將DC內(nèi)容減1，若減1后DC內(nèi)容不為0记餐，標識傳送未完驮樊，便繼續(xù)傳送下一個字（節(jié)）；否則片酝，由DMA控制器發(fā)出中斷請求囚衔。

DMA控制器由三部分組成：主機與DMA控制器的接口；DMA控制器與塊設(shè)備的接口雕沿；I/O控制邏輯

為了實現(xiàn)在主機與控制器之間成塊數(shù)據(jù)的直接交換练湿，必須在DMA控制器中，設(shè)置如下四類寄存器：

1. 命令/狀態(tài)寄存器CR
2. 內(nèi)存地址寄存器MAR
3. 數(shù)據(jù)寄存器DR
4. 數(shù)據(jù)計數(shù)器DC（存放本次CPU要讀或?qū)懙淖郑ü?jié)）數(shù)）

獨占設(shè)備的分配程序

1. 基本的設(shè)備分配程序
   1. 分配設(shè)備
   2. 分配控制器
   3. 分配通道
2. 設(shè)備分配程序的改進

不同于以上使用物理設(shè)備名分配审轮，使用邏輯設(shè)備名請求I/O肥哎，以獲得設(shè)備的獨立性

假脫機系統(tǒng)（Spooling）

如果說辽俗，通過躲到程序技術(shù)可將一臺物理CPU虛擬成為多臺邏輯CPU，從而允許多個用戶共享一臺主機篡诽，那么崖飘，通過假脫機技術(shù)，則可將一臺物理I/O設(shè)備虛擬成為多臺邏輯I/O設(shè)備杈女，這樣也就允許多個用戶共享一臺物理I/O設(shè)備

SPOOLing系統(tǒng)主要由以下四部分組成：

1. 輸入井和輸出＃
2. 輸入緩沖區(qū)和輸出緩沖區(qū)
3. 輸入進程和輸出進程
4. ＃管理程序

SPOOLing系統(tǒng)的特點：

1. 提高了I/O的速度
2. 將獨占設(shè)備改造為共享設(shè)備
3. 實現(xiàn)了虛擬設(shè)備功能

緩沖引入的原因：

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

• 單緩沖區(qū)
• 雙緩沖區(qū)（也稱為 緩沖對換）
• 環(huán)形緩沖區(qū)

多個緩沖區(qū) 多個指針
Nextg：指示計算進程下一個可用緩沖區(qū)G的指針；
Nexti：指示輸入進程下次可用的空緩沖區(qū)R的指針
Current：用于指示計算進程正在使用的緩沖區(qū)C的指針

Nexti指針和Nextg指針沿著順時針方向移動

Nexti指針追上Nextg指針碧信。意為著輸入進程輸入數(shù)據(jù)的速度大于計算進程處理數(shù)據(jù)的速度,已把全部可用的空緩沖區(qū)裝滿赊琳，再無緩沖區(qū)可用街夭，此時輸入進程應阻塞砰碴，直到計算進程把某個緩沖區(qū)的數(shù)據(jù)全部提取完，再喚醒輸入進程板丽。這種情況被稱為系統(tǒng)受計算限制

Nextg指針追上Nexti指針呈枉。意為輸入數(shù)據(jù)的速度低于計算進程處理數(shù)據(jù)的速度，使全部裝有輸入數(shù)據(jù)的緩沖區(qū)都被抽空埃碱。此時應阻塞計算進程猖辫。這種情況稱為系統(tǒng)受I/O限制

緩沖區(qū)與緩沖池的區(qū)別：
蝗蟲去僅僅是一組內(nèi)存塊的鏈表，而緩沖池則是包含了一個管理的數(shù)據(jù)結(jié)構(gòu)及一組操作函數(shù)的管理機制砚殿，用于管理多個緩沖區(qū)

1. 固定磁頭磁盤：

每條磁道上都有一讀/寫磁頭啃憎，所有的磁頭都被裝在一剛性臂中，通過這些磁頭可訪問所有各磁道似炎，并進行并行讀/寫辛萍，有效的提高了磁盤的I/O速度。這種結(jié)構(gòu)主要用于大容量磁盤上

2. 移動頭磁盤

每一個盤面僅配有一個磁頭羡藐，也被裝入磁臂中贩毕，為了能訪問該盤面上的所有此導，該磁頭必須能移動以進行尋道仆嗦。因此辉阶，移動磁頭僅能以串行方式讀/寫，指示I/O速度較慢瘩扼，但由于結(jié)構(gòu)簡單谆甜，廣泛用于中小型磁盤設(shè)備中。

磁盤訪問時間

1. 尋道時間

啟動磁臂的時間與磁頭移動n條磁道所花費的時間之和（占大份）

2. 旋轉(zhuǎn)延遲時間
3. 傳輸時間

磁盤調(diào)度算法

1. 先來先服務(wù)（FCFS）
2. 最短尋道服務(wù)時間（SSTF）

基于掃描的磁盤調(diào)度算法

1. 掃描算法（SCAN）（又稱為“電梯調(diào)度算法）

磁頭從當前方向一直移動到邊緣集绰，再調(diào)轉(zhuǎn)方向從邊緣到另一個

2. 循環(huán)掃描算法（CSCAN）

磁頭只能自里向外移動

文件系統(tǒng)的層次系統(tǒng)

1. 對象及其屬性
   1. 文件
   2. 目錄
   3. 磁盤（磁帶）存儲空間
2. 對對象操縱和管理的軟件集合
   1. I/O控制層
   2. 基本文件系統(tǒng)層
   3. 基本I/O管理程序
   4. 邏輯文件系統(tǒng)
3. 文件系統(tǒng)的接口
   1. 命令接口
   2. 程序接口

文件的邏輯結(jié)構(gòu)

1. 按文件是否有結(jié)構(gòu)分類规辱、
   1.有結(jié)構(gòu)文件
   1. 定長記錄
   >廣泛用于數(shù)據(jù)處理中
   2. 邊長記錄
   >廣泛用于許多商業(yè)領(lǐng)域
   2. 無結(jié)構(gòu)文件（流式文件）
2. 按文件的組織方式
   1. 順序文件
   2. 索引文件
   3. 索引順序文件

對于順序存儲設(shè)備，也只有順序文件才能被存儲并能有效的工作

文件控制塊和索引節(jié)點

==文件控制塊（FCB)==
三類信息：

1. 基本信息：
   1. 文件名
   2. 文件物理位置
   3. 文件邏輯結(jié)構(gòu)
   4. 文件的物理結(jié)構(gòu)
2. 存取控制信息
3. 使用信息

磁盤索引節(jié)點：

1. 文件主標識符
2. 文件類型
3. 文件存取權(quán)限
4. 文件物理地址
5. 文件長度
6. 文件連接計數(shù)
7. 文件存取時間

內(nèi)存索引結(jié)點

1. 索引節(jié)點編號
2. 狀態(tài)
3. 訪問計數(shù)
4. 文件所屬文件系統(tǒng)的邏輯設(shè)備號
5. 鏈接指針

樹形目錄
主目錄：稱為根目錄
數(shù)據(jù)文件：稱為樹葉
其他的目錄稱為：樹的結(jié)點

從樹根開始的路徑名稱為 絕對路徑名
從當前目錄開始直到數(shù)據(jù)文件為止的路徑名稱為 相對路徑名

外存的組織方式

1. 連續(xù)組織方式

優(yōu)點：
順序訪問容易
順序訪問速度快
缺點：
要求為一個文件分配連續(xù)的存儲空間
必須事先知道文件的長度

2. 連接組織方式

優(yōu)點：
消除了磁盤的外部碎片倒慧，提高了外存的利用率
對插入按摘、刪除和修改記錄都非常容易
能適應文件的動態(tài)增長包券，無需事先知道文件的大小
隱式鏈接 顯示鏈接

3. 索引組織方式

FAT12

每個FAT表項為12位，因此炫贤，在FAT表中最多允許有4096（2^12）個表項溅固，如果盤塊為基本單位，每個盤塊的大小為512字節(jié)兰珍，那么每個磁盤分區(qū)的容量為2MB(4096*512B)侍郭，一個物理磁盤能支持4個邏輯磁盤分區(qū)，所以相應的磁盤最大容量僅為8MB掠河。

簇

一組相鄰的扇區(qū)亮元，在FAT中它是作為一個虛擬山區(qū)。在進行盤塊分區(qū)時唠摹，以簇作為分配的基本單位爆捞。簇的大小一般是2n個盤塊，例如當一個簇僅有一個扇區(qū)時勾拉，磁盤的最大容量為8MB煮甥，當一個簇包含了8個扇區(qū)時，磁盤的最大容量為64MB
優(yōu)點：
能減少FAT表中項數(shù)藕赞，使FAT表占更少的存儲空間成肘，減少存取開銷
缺點：
造成更大的簇內(nèi)零頭（與存儲管理器中的頁內(nèi)零頭相似）（限制磁盤容量的主要原因）

FAT16

FAT12對磁盤容量限制的原因在于，F(xiàn)AT12表中的表項有限制斧蜕，即最多只允許2^12個双霍，如果我們將FAT表項中位數(shù)增為16，則最大表項數(shù)將增至2^16個批销，此時便能將一個磁盤分區(qū)分為2^16個簇,在FAT的每個粗重可以有的盤塊數(shù)為4洒闸，8。风钻。顷蟀。直到64。
由此可以得出管理的最大分區(qū)空間為2^16*64*512=2048MB

FAT32

在FAT有最小管理空間的限制骡技，F(xiàn)AT32卷必須至少有65537個簇鸣个，所以不支持容量小于512MB的分區(qū)
FAT32的單個文件長度也不能大于4GB
FAT43不能保持向下兼容

NTFS新特征

1. 使用64為磁盤地址
2. 在NTFS中可以很好地支持長文件名
3. 具有系統(tǒng)容錯功能
4. 能保證系統(tǒng)中地數(shù)據(jù)一致性