分時系統(tǒng)

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

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

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

1. 多路性：分時系統(tǒng)中的多路性都表現(xiàn)為系統(tǒng)按分時原則為多個終端用戶服務(wù)；實時控制系統(tǒng)的多路性則是指系統(tǒng)周期性的對多路現(xiàn)場信息進(jìn)行采集，以及對多個對象或多個執(zhí)行機構(gòu)進(jìn)行控制
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的兩個最基本的特征

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

處理及管理功能：

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

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

基本概念

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

前驅(qū)圖

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

如果進(jì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)性

進(jìn)程的定義

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

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

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

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

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

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

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

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

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

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

掛起原語Suspend 激活原語Active

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

PCB的具體作用

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

進(jìn)程控制塊中的信息：

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

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

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

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

支撐功能

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

資源管理功能

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

引起進(jìn)程終止的事件

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

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

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

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

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

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

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

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

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

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

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

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

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

P、V操作(原子操作)

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

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

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

利用信號量實現(xiàn)進(jìn)程互斥
為使多個進(jìn)程能互斥地訪問某臨界資源，只需為該資源設(shè)置--互斥信號量mutex，并設(shè)其初始值為1，然后將進(jìn)程訪問該資源的臨界區(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

進(jìn)程的兩個基本屬性：

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

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

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

進(jìn)程與線程的比較

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

線程運行的三個狀態(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)度（又稱為 進(jìn)程調(diào)度 或 短程調(diào)度）
   • 調(diào)度對象 ==進(jìn)程==
   • 內(nèi)存中處理（分配處理機）
3. 中級調(diào)度（內(nèi)存調(diào)度）
   • 目的：提高內(nèi)存利用率和系統(tǒng)吞吐量
   • 內(nèi)存 調(diào)出 外存

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

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

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

• 響應(yīng)時間塊
• 均衡性

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

• 截止時間的保證
• 可預(yù)測性

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

• 作業(yè)：一個比程序更為廣泛的概念。不僅包含了通常的程序和數(shù)據(jù)，而且還應(yīng)配有一份作業(yè)說明書，系統(tǒng)根據(jù)說明書來對程序的運行進(jìn)行控制。在批處理系統(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īng)比優(yōu)先調(diào)度算法（HRRN）

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

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

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

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

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

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

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

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

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

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

優(yōu)先級倒置

例如：高優(yōu)先級的進(jìn)程P3由于和低優(yōu)先級P1的共享資源的原因，必須等待P1運行完成后才能運行，而二者之間，由于優(yōu)先級調(diào)度算法，P2搶占了P1資源，而P3又搶占了P2的資源，導(dǎo)致P3進(jìn)程因P1進(jìn)程被阻塞了，又由于P2的存在，而延長了P3被阻塞的時間，只有等待P2進(jìn)程運行完成后，p1運行，再最后P3運行

死鎖

死鎖的定義

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

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

處理死鎖的方法

1. 預(yù)防死鎖
2. 避免死鎖
3. 檢測死鎖
4. 解除死鎖

銀行家算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• 分頁存儲管理方式

相應(yīng)的將內(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)：從進(jìn)程發(fā)出指定邏輯地址的訪問請求，經(jīng)過地址變換，到在內(nèi)存中找到對應(yīng)的實際物理地址單位并取出數(shù)據(jù)，所需要花費的總時間，稱為內(nèi)存的有效訪問時間

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

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

1. 頁是信息的物理單位，分段存儲管理方式中的段則是信息的邏輯單位
2. 頁的大小固定且由系統(tǒng)決定，段的長度卻不固定，決定于用戶所編寫的程序，通常由編譯程序在對源程序在對源程序進(jìn)行編譯時，根據(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ù)或指令

虛擬存儲器的基本工作情況：基于局部原理，應(yīng)用程序在運行之前沒有必要將之全部裝入內(nèi)存，而僅需將那些當(dāng)前要運行的少數(shù)頁面或段先裝入內(nèi)存便可運行，其余部分暫留在攀上。程序在運行時，如果他要訪問的頁已調(diào)入內(nèi)存，便可繼續(xù)執(zhí)行下去，但如果程序索要訪問的頁尚未調(diào)入內(nèi)存，便發(fā)出缺頁中斷請求，此時OS將利用請求調(diào)頁功能將它們調(diào)入內(nèi)存，以使進(jìn)程能繼續(xù)執(zhí)行下去。如果此時內(nèi)存已滿，無法在裝入新的，還需使用頁的置換功能，將內(nèi)存匯總暫時不用的頁調(diào)至盤上，騰出所需的空間，調(diào)入要訪問的頁入內(nèi)存。

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

虛擬存儲器：具有請求調(diào)入功能和置換功能，能從邏輯上對應(yīng)內(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)存容量遠(yuǎn)大于實際內(nèi)存容量

頁面置換算法：

• 最佳置換算法（OPT）

理想上的算法

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

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

工作集：
指再某段時間間隔里，進(jìn)程實際所要訪問頁面的集合。

”抖動“的預(yù)防方法

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

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

4. 選擇暫停的進(jìn)程

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

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

產(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. 終端處理程序：用于保存被終端進(jìn)程的CPU環(huán)境，轉(zhuǎn)入相應(yīng)的中斷處理程序進(jìn)行處理，處理完畢再恢復(fù)被中斷進(jìn)程的現(xiàn)場后，返回到被終端的進(jì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ā)來的中斷信號的一種響應(yīng)
2. 陷入：CPU內(nèi)部時間所引起的中斷

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

1. 中斷向量表

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

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

對多中斷源的處理方式

1. 禁止（屏蔽）中斷

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

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

DMA工作過程

當(dāng)CPU要從磁盤讀入以數(shù)據(jù)塊時，便向磁盤控制器發(fā)送一條讀命令。該命令被送入命令寄存器CR中。同時，需要將本次要讀入數(shù)據(jù)在內(nèi)存的起始目標(biāo)地址送入內(nèi)存地址寄存器MAR中，將要讀數(shù)據(jù)的字（節(jié)）數(shù)送入數(shù)據(jù)計數(shù)器DC中。還需將磁盤中的源地址直接送至DMA控制器的I/O控制邏輯上。然后啟動DMA控制器進(jìn)行數(shù)據(jù)傳送。以后，CPU便可去處理其他任務(wù)，整個數(shù)據(jù)傳送過程由DMA控制器進(jìn)行控制。當(dāng)DMA控制器已從磁盤中讀入一個字（節(jié)）的數(shù)據(jù)，并送入數(shù)據(jù)寄存器DR后，再挪用一個存儲走起，將該字（節(jié)）傳送到MAR所指示的內(nèi)存單元中。然后便對MAR內(nèi)容加1，將DC內(nèi)容減1，若減1后DC內(nèi)容不為0，標(biāo)識傳送未完，便繼續(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è)備分配程序的改進(jìn)

不同于以上使用物理設(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. 輸入進(jìn)程和輸出進(jìn)程
4. ＃管理程序

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

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

緩沖引入的原因：

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

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

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

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

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

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

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

1. 固定磁頭磁盤：

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

2. 移動頭磁盤

每一個盤面僅配有一個磁頭，也被裝入磁臂中，為了能訪問該盤面上的所有此導(dǎo)，該磁頭必須能移動以進(jìn)行尋道。因此，移動磁頭僅能以串行方式讀/寫，指示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)度算法）

磁頭從當(dāng)前方向一直移動到邊緣，再調(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. 文件主標(biāo)識符
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é)點

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

外存的組織方式

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

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

2. 連接組織方式

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

3. 索引組織方式

FAT12

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

簇

一組相鄰的扇區(qū)，在FAT中它是作為一個虛擬山區(qū)。在進(jìn)行盤塊分區(qū)時，以簇作為分配的基本單位。簇的大小一般是2n個盤塊，例如當(dāng)一個簇僅有一個扇區(qū)時，磁盤的最大容量為8MB，當(dāng)一個簇包含了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ù)一致性