第二章：操作系統(tǒng)運行機制

考試內(nèi)容：

1.?內(nèi)核態(tài)與用戶態(tài)

2.?中斷與異常

3.?系統(tǒng)調(diào)用接口

4.?存儲系統(tǒng)

5.?I/O系統(tǒng)

6.?時鐘（clock）

1.?CPU的構(gòu)成與基本工作方式

（1）處理器

運算器：實現(xiàn)指令中的算術(shù)和邏輯運算

控制器：控制程序運行的流程

一系列寄存器：用戶可見寄存器；控制和狀態(tài)寄存器

高速緩存：處于CPU和物理內(nèi)存之間

（2）寄存器

用戶可見寄存器：

①數(shù)據(jù)寄存器

②地址寄存器

③條件寄存器

控制和狀態(tài)寄存器：

①程序計數(shù)器（PC）

②指令寄存器（IR）

③程序狀態(tài)字（PSW）

（3）處理器狀態(tài)

管態(tài)（特權(quán)態(tài)、系統(tǒng)態(tài)、核心態(tài)）；目態(tài)（普通態(tài)、用戶態(tài)）

or核心狀態(tài)；管理狀態(tài)；用戶程序狀態(tài)（目標狀態(tài)）

目態(tài)→中斷 轉(zhuǎn)換→管態(tài) ????管態(tài)→設(shè)置PSW（修改程序狀態(tài)字）→目態(tài)

補充：程序狀態(tài)字

條件碼：反應(yīng)指令執(zhí)行后的結(jié)果特征

中斷屏蔽碼：指出是否允許中斷

CPU的工作狀態(tài)碼：管態(tài)、目態(tài)的轉(zhuǎn)換

2.?中斷

（1）中斷特點：

隨機

可恢復(fù)

自動處理

（2）中斷系統(tǒng)的組成：

硬件中斷裝置

軟件中斷處理程序

（3）中斷的分類

①廣義中斷：

中斷（外中斷）：

I/O中斷

時鐘中斷

硬件故障中斷

異常（內(nèi)中斷）：

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

缺頁異常

斷點指令

其他程序性異常（eg.算術(shù)溢出）

②狹義中斷：

中斷：與正執(zhí)行命令無關(guān)，可屏蔽

異常：與正執(zhí)行命令有關(guān)，不可屏蔽

總結(jié)：常見的中斷有

I/O中斷

時鐘中斷

硬件故障中斷

程序性中斷

系統(tǒng)調(diào)用（訪管中斷）

（4）中斷寄存器

中斷掃描機構(gòu)檢測

中斷信號規(guī)定值為1——中斷

中斷信號規(guī)定值為0——無

由中斷位組成

（5）影響中斷次序的技術(shù)：

中斷優(yōu)先級

中斷屏蔽

3.?系統(tǒng)調(diào)用組成程序接口：用戶取得OS服務(wù)的唯一途徑

系統(tǒng)調(diào)用與一般過程調(diào)用的區(qū)別：運行在不同的系統(tǒng)狀態(tài)

①系統(tǒng)調(diào)用（調(diào)：用戶態(tài) ?被調(diào)：系統(tǒng)態(tài)）

②一般過程調(diào)用（調(diào)與被調(diào)都相同）

4.?存儲保護功能：

界地址寄存器（界限寄存器）

存儲鍵

5.?I/O控制方式

通道（I/O處理機）

DMA技術(shù)：成塊

緩沖技術(shù)：解決部件間速度不匹配問題——單緩沖區(qū)；多緩沖區(qū)（Cache）技術(shù)

6.?時鐘→由硬件提供

（1）時鐘工作

多道程序→死循環(huán)→防止機時浪費：提高CPU利用率

分時系統(tǒng)→間隔時鐘→時間片輪轉(zhuǎn)

實時系統(tǒng)

（2）時鐘分類

硬件時鐘

軟件時鐘

（3）時鐘用途分類

絕對時鐘

相對時鐘（間隔時鐘）：eg.定時

?

第三章：進程線程模型（重點）

考試內(nèi)容：

1.?并發(fā)環(huán)境與多道程序設(shè)計

2.?進程的基本概念，進程控制塊（PCB）

3.?進程狀態(tài)及狀態(tài)轉(zhuǎn)換

4.?進程控制：創(chuàng)建、撤銷、阻塞、喚醒

UNIX類進程操作的應(yīng)用（fork()、exec()、wait()、signal()）

5.?線程的基礎(chǔ)概念，線程的實現(xiàn)機制，Pthread線程包的使用

6.?進程的同步與互斥：信號量及PV操作，管程，Pthreads中的同步互斥機制

7.?進程間通信

8.?處理機調(diào)度

1.?順序執(zhí)行特征：

順序性

封閉性

程序執(zhí)行結(jié)果的確定性

程序結(jié)果的可行性

2.?多道程序特點：

獨立性

隨機性

資源共享性

3.?并發(fā)特征：

并發(fā)程序在執(zhí)行期間具有相互制約關(guān)系

程序與計算不再一一對應(yīng)

并發(fā)執(zhí)行結(jié)果不可再現(xiàn)

eg.k=5 ?A：k=k-1 ?B：Print k；k=k+3

①先A后B：k=4；k=4；k=7

②先B后A：k=5；k=8；k=7

③先B再A后B：k=5；k=4；k=7

4.?進程：動態(tài)（正在執(zhí)行的程序）——系統(tǒng)進程；用戶進程

程序：靜態(tài)

5.?（1）進程特性：

并發(fā)性、動態(tài)性（最基本特征）

獨立性

交往性

異步性

（2）進程組成：

程序

數(shù)據(jù)

進程控制塊（PCB）

（3）進程控制塊（PCB）：

信息：

調(diào)度信息——當前

現(xiàn)場信息——運行

PCB表組織方式：

線性方式

索引方式

鏈接方式

6.?進程的基本狀態(tài)（不同設(shè)置進程狀態(tài)數(shù)不同）：進程是資源擁有的基本單位

（1）三狀態(tài)：（線程的基本狀態(tài)）

就緒狀態(tài)

運行狀態(tài)（單處理器；多處理器）

等待狀態(tài)

（2）五狀態(tài)：

前面的三狀態(tài)

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

結(jié)束狀態(tài)

（3）七狀態(tài)：

前面的五狀態(tài)

掛起狀態(tài)（內(nèi)存→外存）

激活狀態(tài)（外存→內(nèi)存）

7.?進程狀態(tài)間的轉(zhuǎn)換：

新狀態(tài)→就緒狀態(tài)：就緒隊列能接納新的進程

就緒狀態(tài)→執(zhí)行狀態(tài)：算法，處于執(zhí)行……=當前狀態(tài)

執(zhí)行狀態(tài)→阻塞狀態(tài)：發(fā)生某種事件

執(zhí)行狀態(tài)→就緒狀態(tài)：時間片結(jié)束；優(yōu)先權(quán)較低

阻塞狀態(tài)→就緒狀態(tài)：需資源得到滿足或完成輸入輸出響應(yīng)

執(zhí)行狀態(tài)→終止狀態(tài)：正常結(jié)束或異常錯誤結(jié)束

8.?進程控制特定功能原語：

創(chuàng)建原語

撤銷原語

阻塞原語

喚醒原語

補充：阻塞發(fā)生的原因???喚醒事件

請求系統(tǒng)服務(wù) ????→ ???得到滿足

啟動某種操作 ????→ ???完成

新數(shù)據(jù)尚未到達 ??→ ???到達

無新工作可做 ????→ ???有新

9.?線程實現(xiàn)機制

用戶級線程

內(nèi)核級線程

混合實現(xiàn)方式

10.?線程與進程的比較：

（1）調(diào)度并發(fā)性

進程間并發(fā)執(zhí)行

一個進程中的多個線程間并發(fā)

（2）擁有資源

線程不擁有系統(tǒng)資源，但線程可訪問屬于進程的資源

（3）系統(tǒng)開銷

進程切換的開銷遠大于線程

11.?（1）線程、進程調(diào)度算法：

先來先服務(wù)調(diào)度算法（FCFS）：最簡單、非搶占式、利于長進程

最短作業(yè)優(yōu)先調(diào)度算法（SPF）：就緒、運行時間最短、非搶占式、不利于長進程

最短剩余時間優(yōu)先調(diào)度算法：搶占式、動態(tài)

時間片輪轉(zhuǎn)調(diào)度算法（RR）：分時系統(tǒng)、時鐘中斷、輪轉(zhuǎn)規(guī)則、交互進程

最高優(yōu)先級調(diào)度算法

多級反饋隊列調(diào)度算法（MLF）

實時系統(tǒng)中方的調(diào)度算法

（2）進程調(diào)度層次：

高級調(diào)度

中級調(diào)度：調(diào)度算法

低級調(diào)度：進程調(diào)度

（3）調(diào)度算法設(shè)計原則：

面向用戶的原則——周轉(zhuǎn)時間短

面向系統(tǒng)的原則——系統(tǒng)吞吐量高

12.?進程間的關(guān)系：

（1）進程同步遵循原則：

空閑讓進

忙則等待

有限等待

讓權(quán)等待

（2）進程互斥（解決互斥，平等協(xié)商，進程管理者）：

①軟件算法：單標志算法；雙標志、先檢查算法；雙標志、后檢查算法；先修改、后檢查、后修改者等待算法

②硬件方法：TS指令；Swap指令

③操作系統(tǒng)方法：信號量（Dijkstra提出）

補充：資源共享程度的三個層次：

互斥

死鎖

饑餓

13.?臨界資源訪問過程：

進入?yún)^(qū)→臨界區(qū)→退出區(qū)→剩余區(qū)

14.?信號量：

（1）最常用：

整型信號量→整型變量：

①>0 可用資源數(shù)

②<0 阻塞進程數(shù)

③=0 資源已用完

（2）整型信號量的原語：

P操作：進入臨界區(qū)前——wait（s）

V操作：退出臨界區(qū)后——signal（s）≤0

15.?管程：

（1）管程的組成：

管程名稱

共享數(shù)據(jù)的說明

對該數(shù)據(jù)進行操作的一組過程

對共享數(shù)據(jù)設(shè)置初始值的語句

（2）管程的特征：

模塊化

抽象數(shù)據(jù)類型

信息隱蔽

（3）實現(xiàn)同步（進/線程的阻塞和喚醒）：

wait原語：阻塞

signal原語：喚醒隊首

16.?通信分類：

（1）低級通信

（2）高級通信（管道通信）：

共享內(nèi)存；消息機制（消息緩沖通信——直接；信箱通信方式——間接）；通過共享文件

補充：信箱通信：

（1）信箱通信操作：

創(chuàng)建原語

撤銷原語

發(fā)送原語

接收原語

（2）信箱分類：

私有信箱

共有信箱

共享信箱

17.?管道通信系統(tǒng)：首創(chuàng)UINX系統(tǒng)

讀進程 —（共享文件、連接）— 寫進程

?

第四章：存儲管理方案

考試內(nèi)容：

1.?存儲管理的基本概念，存儲管理的基本任務(wù)

2.?分區(qū)存儲管理方案

3.?覆蓋技術(shù)與交換技術(shù)

4.?虛存概念與虛擬存儲技術(shù)

5.?虛擬頁式存儲管理方案

1.?存儲體系：

（自下而上依次存取器存取時間減少、存取速度增加、每位存儲器成本增加、容量減少）

高速緩存器

內(nèi)存

外存

2.?存儲器：

（1）存儲器的組成：

內(nèi)存（空間）→系統(tǒng)區(qū)；用戶區(qū)

外存（輔助存儲器）

（2）存儲器管理任務(wù)：

內(nèi)存的分配和回收（實現(xiàn)方式）：位示圖表示法；空閑頁面表；空閑塊表

內(nèi)存共享：代碼共享；數(shù)據(jù)共享

存儲保護（內(nèi)容）地址越界保護；權(quán)限保護；存儲鍵保護→（目的）避免各程序間相互干擾

補充：內(nèi)存

（1）分配方式：

靜態(tài)分配

動態(tài)分配

（2）擴充內(nèi)存方式：

虛擬存儲技術(shù)（虛擬頁式——動態(tài)擴充內(nèi)存）

交互技術(shù)

3.?分區(qū)：

（1）固定分區(qū)：

全裝主存（虛擬存儲是部分），連續(xù)存儲空間，大小固定，數(shù)目固定（限制并發(fā)）

①主存分配：狀態(tài)“0”表可用

②主存回收：狀態(tài)“0”表空閑

（2）可變分區(qū)：

①主存空間分配（算法）：

最先適應(yīng)分配算法（FF）——地址遞增，找第一個作業(yè)的空閑區(qū)

最優(yōu)適應(yīng)分配算法（BF）——長度遞增，最小能裝作業(yè)的區(qū)，順序

最壞適應(yīng)分配算法（WF）——長度遞減，最大能裝作業(yè)的區(qū)，順序

下次分配算法

②主存空間回收

③總結(jié)：

動態(tài)分區(qū)，大小不變，數(shù)目不變

算法：移動技術(shù)（“碎片整理”）→開銷增加，有條件的

數(shù)目結(jié)構(gòu)：已分分區(qū)表；空閑分區(qū)表

分配：先小地址，排列一樣的，首次分配只有一個空閑區(qū)

④回收：

無上鄰，無下鄰：起始不變 ?空閑分區(qū)變大 ?數(shù)目+1

有上鄰，無下鄰：起始不變 ?空閑分區(qū)變大 ?數(shù)目不變

有下鄰，無上鄰：起始變? ? ?空閑分區(qū)變大 ?數(shù)目不變

有上鄰，有下鄰：起始不變 ?空閑分區(qū)變大 ?數(shù)目-1

4.?地址轉(zhuǎn)換（地址映射/重定位）：邏輯地址→物理地址

（1）分類：

靜態(tài)重定位：程序開始執(zhí)行前→絕對地址（一次性）

動態(tài)重定位：程序執(zhí)行過程中（多次）

（2）計算方法：

頁號=邏輯地址/頁長（商）

頁內(nèi)地址=邏輯地址mod頁長（余數(shù)）

物理地址=塊號*塊長+塊內(nèi)地址+用戶區(qū)地址+用戶區(qū)基址

→（邏輯地址 - 頁內(nèi)地址）/頁號=頁長=塊長

5.?頁式管理（可離散）：

（1）數(shù)據(jù)結(jié)構(gòu)：

主存分配表：存儲頁表在內(nèi)存中位置

位示圖：塊的可用與否，空閑塊數(shù)

頁表：存儲塊和頁的對應(yīng)關(guān)系

（2）特點：

有效解決“碎片”多的問題

位示圖、頁表→作業(yè)分配，硬件支持

頁的大小固定，使共享困難

（3）頁式虛擬存儲管理系統(tǒng)：

純分頁? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???位示圖

請求調(diào)頁功能? ? ? ? ? ? ???→數(shù)據(jù)結(jié)構(gòu)? ? ? ? ? ?頁表→分類：多級；散列 ；反置

頁面置換功能? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?主存分配表

①調(diào)入策略：請求調(diào)頁；預(yù)調(diào)頁

②置頁策略

③置換策略：固定分配局部置換；可變分配全局置換；可變分配局部置換

CPU在存取數(shù)據(jù)時，要訪問兩次

①訪問主存中的頁表，塊號與頁內(nèi)地址→物理地址

②根據(jù)①得到的物理地址，到主存中獲取數(shù)據(jù)

降低計算機處理速度→為提高速度：

快表（TLB）：頁式存儲管理快表存放 CACHE（高速緩存）

兩級頁表

6.?虛擬存儲管理方式：

（1）虛擬存儲器：

邏輯容量=最大容量（eg. 24位為2的24次方B）

物理容量=實際容量：

①主存+硬盤≤最大容量

②主存+硬盤＞最大容量

（2）頁面置換算法（→不合理：抖動）

先進先出置換算法（FIFO）：淘汰隊首的那一頁 貝萊迪異常（Belady）現(xiàn)象

最近最久未使用算法（LRU）：淘汰最近最久沒用的頁，程序局部性原理

最近最不經(jīng)常使用算法（LFU）：訪問計算器“1”；“0”

理想頁面置換算法（最佳OPT）：移出不需要、長時間不用的頁

最近未使用頁面置換算法（NRU）：

①第0類：沒訪問、沒修改

②第1類：沒訪問、被修改

③第2類：被訪問、沒修改

④第3類：被訪問、被修改

7.?缺頁中斷率：中斷次數(shù)/頁面訪問總次數(shù)

8.?段式存儲管理方式：

段內(nèi)地址＞段長為地址越界 ?段號不符為段號越界

段始址+段內(nèi)地址=物理地址 （段號，段內(nèi)地址）為邏輯地址

段頁式存儲管理方式：

感謝可愛帥氣的你們的關(guān)注和點贊(^_?)☆

（整理不易，可自用，不要二次復(fù)制到其他APP哦）