計算機操作系統(tǒng)第四版期末復(fù)習(xí)知識點匯總附習(xí)題

第一章引論

①為什么發(fā)明計算機系統(tǒng)：方便、有效、可擴充、開放

計算機系統(tǒng)作用：做接口、管理資源、資源的抽象

發(fā)展計算機系統(tǒng)的動力：提高利用率、更加方便、應(yīng)用.體系.硬件更新都要跟上

②計算機系統(tǒng)發(fā)展史

一、無操作系統(tǒng)

(-)人工操作：單用戶、CPU.內(nèi)存長期空閑

(二)脫機輸入/輸出(OFF-LINEI/O):裝好卡片再上機。節(jié)約CPU空閑時間、提高

I/O速度

二、單道批操作系統(tǒng)

描述：有個監(jiān)督程序?qū)⒋艓系淖鳂I(yè)調(diào)入計算機

缺點：I/O太慢，CPU太快

三、多道批操作系統(tǒng)

描述：A在I/O,B趁機CPU

優(yōu)點：肯定提高資源利用率、系統(tǒng)吞吐量變大

缺點：每個程序都要很久才處理完(作業(yè)要排隊)、無交互能力

未解難題：內(nèi)存、處理機爭用、I/O設(shè)備、文件的組織和管理、作業(yè)管理、用戶和系統(tǒng)的

接口

四、分時系統(tǒng)

描述：解決人機交互問題

優(yōu)點：終于有人機交互、多用戶共享主機

實際問題：由于多用戶，所以要有"多路卡"、作業(yè)直接入內(nèi)存、有個“時間片"調(diào)度作

業(yè)

特征：多路、獨立、及時（用戶可接受）、交互

五、實時系統(tǒng)

描述：工業(yè)（武器）控制系統(tǒng)、信息查詢系統(tǒng)、多媒體系統(tǒng)、嵌入式系統(tǒng)

類型1:周期性實時：真的很周期；非周期性實時：有開始截止時間和完成截止時間

類型2:硬實時：工業(yè)、武器系統(tǒng)；軟實時：信息查詢系統(tǒng)和多媒體系統(tǒng)

與分時系統(tǒng)比較：多路、獨立、及時（毫秒級）、交互、可靠

六、微機時代

（-）單用戶單任務(wù)：8位機的CP/M、16位機的MS-DOS

（二）單用戶多任務(wù)：目前的32位系統(tǒng)，如Windows

（三）多用戶多任務(wù)：UNIX、Solaris.Linux

③操作系統(tǒng)共同特性：

一、并發(fā)

（一）并發(fā)和并行宏觀上一樣，

并發(fā)：單處理機系統(tǒng)，微觀上交替運行

并行：多處理機系統(tǒng)，微觀上同時運行

（二）引入進程

進程：在系統(tǒng)中能獨立運行并作為資源分配的基本單位，由機器指令、數(shù)據(jù)和堆棧等組成,

能獨立運行的活動實體

特點：用進程就可以并發(fā)執(zhí)行了

二、共享

（-）互斥共享方式

例子：臨界資源，打印機、磁帶機

描述：你要先申請才能獲得資源

（二）同時訪問方式

描述：微觀上還是并發(fā)

例子：多用戶磁盤設(shè)備

條件：系統(tǒng)允許進程并發(fā)、系統(tǒng)能有效管理資源

三、虛擬

（-）時分復(fù)用技術(shù)（利用空閑時間服務(wù)其他用戶）

虛擬處理機技術(shù)：分身之術(shù)

虛擬設(shè)備：又是分身之術(shù)，騙用戶以為有專人服務(wù)

時分復(fù)用：速度：＜1/N

（二）空分復(fù)用技術(shù)

描述：將程序、電話線分成若干部分，然后各部分分時進入內(nèi)存運行

空分復(fù)用：空間：＜1/N

四、異步

描述：因為要并發(fā)，所以需要一個機制調(diào)度進程

④操作系統(tǒng)主要功能

一、處理機管理功能

（-）進程控制

描述：要并發(fā)，就要進程、要進程，就要管理

（二）進程同步

進程互斥方式：臨界資源要互斥

進程同步方式：合作完成共同任務(wù)，同步機構(gòu)要協(xié)調(diào)先后次序（信號量控制）

（三）進程通信

描述：對合作進程而言，需要交換信息。當(dāng)他們處于同一計算機系統(tǒng)時，通常采用直接通

信的方式。

例子：輸入進程、計算進程、打印進程，需要信息交換

（四）調(diào)度

作業(yè)調(diào)度：選擇作業(yè)、建立進程、分配資源、插入就緒隊列

進程調(diào)度：從就緒隊列中選出進程，分配CPU

二、存儲器管理功能

（-）內(nèi)存分配

任務(wù)：分配空間、減少碎片、追加內(nèi)存空間

方式：靜態(tài)分配，裝入內(nèi)存時確定，不允許追加、不允許移動；動態(tài)分配，允許追加、允

許移動

（二）內(nèi)存保護

任務(wù)1:每道程序只在自己的內(nèi)存空間運行，互不干擾

任務(wù)2:不允許用戶程序訪問操作系統(tǒng)程序和數(shù)據(jù)、也不允許用戶程序轉(zhuǎn)移到非共享的其

他用戶程序中執(zhí)行

（三）地址映射

任務(wù)：存儲器要負(fù)責(zé)地址映射，在硬件支持下完成

（四）內(nèi)存擴充

描述：用虛擬存儲技術(shù)，從邏輯上擴充內(nèi)存容量

任務(wù)1:請求-調(diào)入功能

任務(wù)2:置換功能

三、設(shè)備管理功能

任務(wù)1:完成用戶進程的I/O請求：分配I/O設(shè)備，完成I/O操作

任務(wù)2:提高CPU和I/O利用率：提高I/O速度，方便用戶使用I/O設(shè)備

（-）緩沖管理

描述：在內(nèi)存中設(shè)置緩沖區(qū)（CPU高速性和I/O低速性）

例子：單緩沖機制、雙向同時傳送數(shù)據(jù)的雙緩沖機制、多個設(shè)備共同使用的公用"緩沖池"

機制

（二）設(shè)備分配

描述：在系統(tǒng)中設(shè)置"設(shè)備控制表"、"控制器控制表"等數(shù)據(jù)結(jié)構(gòu)，用于記錄設(shè)備和控

制器等標(biāo)識符和狀態(tài)。根據(jù)表就知道指定設(shè)備當(dāng)前是否可用、忙碌。分配時，針對不同設(shè)

備要有不同"分配方式"，對獨占設(shè)備還要考慮分配后是否安全

（三）設(shè)備處理

描述：CPU向設(shè)備控制器發(fā)出I/O命令，要求完成I/O操作、反之，CPU接收控制器發(fā)

出的中斷請求，并響應(yīng).處理

四、文件管理功能

描述：管理用戶、系統(tǒng)文件，方便使用；保證安全性

（-）文件儲存空間管理

背景：多用戶環(huán)境下，用戶自己管理文件存儲，會困難和低效

任務(wù)1:為每個文件分配外存空間、提高外存利用率、進而提高存取速度

任務(wù)2:系統(tǒng)中設(shè)置數(shù)據(jù)結(jié)構(gòu)，記錄文件存儲空間使用情況，以供分配時參考

任務(wù)3:分配和回收

（二）目錄管理

任務(wù)1:為每個文件建立目錄項，包括文件名、屬性、物理位置等，以實現(xiàn)按名存取

任務(wù)2:實現(xiàn)文件共享。

任務(wù)3:提供目錄查詢手段

（三）文件讀/寫管理和保護

文件讀/寫管理：根據(jù)用戶請求，從外存中讀取數(shù)據(jù)，或?qū)?shù)據(jù)寫入外存

文件保護：防止未經(jīng)核準(zhǔn)的用戶存取文件、防止冒名頂替存取文件、防止以不正確方式使

用文件

五、操作系統(tǒng)與用戶之間的接口

（-）用戶接口

描述：方便用戶直接.間接控制自己的作業(yè)

聯(lián)機用戶接口：等待用戶鍵入命令

脫機用戶接口：一開始就提供作業(yè)說明書，直到作業(yè)結(jié)束語句

圖形用戶接口：移動鼠標(biāo)選擇菜單項

（二）程序接口

描述：舊系統(tǒng)用匯編語言寫，所以只有匯編語言的才能直接使用系統(tǒng)調(diào)用；如果是高級語

言，就用——對應(yīng)的庫函數(shù)

六、現(xiàn)代操作系統(tǒng)的新功能

（一）系統(tǒng)安全

描述：確保存儲和傳送數(shù)據(jù)的保密性、完整性和系統(tǒng)可用性，要用幾種技術(shù)

技術(shù)：認(rèn)證技術(shù)、密碼技術(shù)、訪問控制技術(shù)、反病毒技術(shù)

（二）網(wǎng)絡(luò)的功能和服務(wù)

功能：網(wǎng)絡(luò)通信、資源管理、應(yīng)用互操作

（三）支持多媒體

功能：接納控制功能、實時調(diào)度、多媒體文件的存儲

⑤OS結(jié)構(gòu)設(shè)計

一、傳統(tǒng)操作系統(tǒng)結(jié)構(gòu)

(-)無結(jié)構(gòu)操作系統(tǒng)

又名：整體系統(tǒng)結(jié)構(gòu)

(-)模塊化結(jié)構(gòu)os

基本概念：

又名：模塊-接口法

描述：有模塊、子模塊、接口

模塊獨立性：

標(biāo)準(zhǔn)：內(nèi)聚性越高，模塊獨立性越高、耦合度越低，模塊獨立性越高

優(yōu)點：提高設(shè)計正確性.可理解性和可維護性、增強可適應(yīng)性、加快加速過程

缺點：接口難以滿足需求、無序

(三)分層式結(jié)構(gòu)OS

基本概念：有序分層，自底向上法鋪設(shè)中間層

優(yōu)點：易保證系統(tǒng)正確性、易擴充和易維護

缺點：系統(tǒng)效率降低

二、客戶/服務(wù)器模式(Client/serverModel)簡介

(-)客戶/服務(wù)器模式的由來、組成和類型

組成：客戶機、服務(wù)器、網(wǎng)絡(luò)系統(tǒng)

(二)客戶/服務(wù)器之間的交互

描述：客戶發(fā)送請求消息、服務(wù)器接收消息、服務(wù)器回送消息、客戶機接收消息

(三)客戶/服務(wù)器模式的優(yōu)點

描述：數(shù)據(jù)分布處理和存儲、便于集中管理、靈活性和可擴充性、易于改編應(yīng)用軟件

三、面向?qū)ο蟮某绦蛟O(shè)計

(-)OOP的基本概念

描述：抽象，具體事物為對象

對象：封裝好

對象類：創(chuàng)建多個相似對象

繼承：繼承父類，增加部分

(-)OOP的優(yōu)點

描述："重用"提高產(chǎn)品質(zhì)量和生產(chǎn)率、使系統(tǒng)具有更好的易修改性和易擴展性、易于保

證系統(tǒng)"正確性"和"可靠性"

四、微內(nèi)核os結(jié)構(gòu)

描述：支持多處理機

例子：卡內(nèi)基?梅隆的MachOS、Windows2000/XP

(-)基本概念

描述：足夠小的內(nèi)核、基于C/S模式、應(yīng)用"機制與策略分離"原理、采用OOP技術(shù)

(二)基本功能

描述：進程管理、低級存儲器管理、中斷和陷入處理

(三)優(yōu)點

描述：提高可擴展性、增強可靠性、可移植性強、提供對分布式系統(tǒng)的支持、融入OOP

(四)缺點

描述：效率降低

第二章進程描述與控制

①前趨圖與程序執(zhí)行

一、前趨圖與程序執(zhí)行

（-）前趨圖

描述：前一個做完，才到后一個做、禁止循環(huán)

二、順序執(zhí)行

描述：一個跟一個

特征：）1面序、封閉（獨占資源）、可再現(xiàn)

三、并發(fā)執(zhí)行

描述：互不依賴才能并發(fā)執(zhí)行

特征：間斷、失去封閉、不可再現(xiàn)

②進程的描述

一、進程的定義和特征

進程實體：程序段、相關(guān)的數(shù)據(jù)段和PCB

定義：進程是進程實體的運行過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位

特征：動態(tài)、并發(fā)、獨立、異步

二、進程的基本狀態(tài)及轉(zhuǎn)換

進程的三基態(tài)：就緒（只欠CPU）、執(zhí)行、阻塞（因故無法微賣執(zhí)行）

三態(tài)轉(zhuǎn)換：如圖

新增兩態(tài)：創(chuàng)建狀態(tài)、終止?fàn)顟B(tài)

五態(tài)轉(zhuǎn)換：如圖

三、掛起操作和進程狀態(tài)的轉(zhuǎn)換

掛起原因：終端用戶需要、父進程請求、負(fù)荷調(diào)節(jié)、操作系統(tǒng)需要

引入掛起后的三態(tài)轉(zhuǎn)換：如圖

必

耿

引入掛起后的五態(tài)轉(zhuǎn)換：如圖

就緒

掛起阻塞

四、進程管理中的數(shù)據(jù)結(jié)構(gòu)

進程名O

進程標(biāo)識符e送程4O,

用戶幺

標(biāo)識符信息用戶標(biāo)識用戶號

父進程

家族聯(lián)系

子進程

前用寄存器

處理機狀態(tài)信息（現(xiàn)指令il做器

場）程序狀態(tài)字

用戶棧指針

進程狀態(tài)

進程優(yōu)先敷（級/權(quán)）

進程調(diào)度信息

等待收因

調(diào)度算法步效等

程序和數(shù)燃的地址

進程同步和熱值機制

進程控制信息

青■精電

能按指計

重新執(zhí)行時，能從斷點繼續(xù)執(zhí)行.（

它們是用戶程序可以訪

問的,用于留存信息

通用寄存器一

指令計數(shù)器-存放要訪問的下一條

處理機狀態(tài)信息（現(xiàn)場）指令的地址

程序狀態(tài)字、

用戶棧指計

其中含有狀態(tài)信息，

如條件碼、執(zhí)行方式、

中斷屏蔽標(biāo)志等,

存放過程和系統(tǒng)調(diào)

用參數(shù)及調(diào)用地址

指明進程的當(dāng)前狀態(tài)，

3）進程調(diào)度信息作為進程調(diào)度和對換時

的依據(jù)]

描述進程使用處

進程狀態(tài)"

理機的優(yōu)先級別

進程優(yōu)先數(shù)（級/權(quán)）的一個整數(shù)

進程調(diào)度信息

等待原因

調(diào)度算法參數(shù)釘7；由執(zhí)行狀態(tài)轉(zhuǎn)變

一尸D為阻塞狀態(tài)所等

待發(fā)生的事件J

進程調(diào)度所需的其他

信息，如等待CPI的

時間總和。

__________________

指進程的程序和數(shù)據(jù)

所在的內(nèi)存或外存地

@）址^.

程序和數(shù)據(jù)的地址/

進程同步和通信機制

-at?R

資源清單

鏈接啊%、\

資源管理功能：進程管理、存儲器管理、設(shè)備管理

二、進程的創(chuàng)建

層次結(jié)構(gòu)：UNIX有父子關(guān)系，Windows只有控制與被控制關(guān)系

進程圖：描述家庭關(guān)系的圖

引起創(chuàng)建進程的事件：用戶登錄、作業(yè)調(diào)度、提供服務(wù)（譬如打?。?yīng)用請求

進程的創(chuàng)建：申請空白PCB、分配物理.邏輯資源、初始化PCB、如果能插入就緒，就插

三、進程的終止

引起進程終止的事件：正常結(jié)束、異常結(jié)束、外界干預(yù)

進程的終止過程：根據(jù)標(biāo)識符、終止執(zhí)行.立即調(diào)度、子孫終止、資源歸還、移出隊列

四、進程的阻塞與喚醒

引起進程阻塞和喚醒的事件：向系統(tǒng)請求共享資源失敗、等待某操作完成、新數(shù)據(jù)尚未到

達(dá)、等待新任務(wù)到達(dá)

進行阻塞過程：發(fā)生上述的某事件，就進入block過程，主動將狀態(tài)改為阻塞，PCB插入

阻塞隊列（分類插入），處理機分配給另一就緒進程，切換，并保留被阻塞進程的處理機

狀態(tài)

進程喚醒過程：由釋放資源的進程調(diào)用wakeup原語，即移出阻塞隊列，合作/相關(guān)的進

程中安排wakeup

五、進程的掛起與激活

進程的掛起：活動-靜止，suspend原語進程正在執(zhí)行，就轉(zhuǎn)向調(diào)度程序重新調(diào)度

進程的激活過程：從外存調(diào)入active原語到內(nèi)存，檢查進程現(xiàn)行狀態(tài)，靜止一活動

搶占調(diào)度策略：靜止就緒進程一就緒隊列，比較當(dāng)前進程優(yōu)先度，有機會立即剝奪當(dāng)前進

程運行

④進程同步

描述：能夠并發(fā)、改善利用率、提高吞吐量、但使系統(tǒng)復(fù)雜

一、進程同步的基本概念

制約關(guān)系：間接相互制約關(guān)系、直接相互制約關(guān)系

間接相互制約關(guān)系：互斥共享

直接相互制約關(guān)系：合作共享，異步性要做好

臨界資源：生產(chǎn)者-消費者問題、

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

同步機制應(yīng)遵循的規(guī)則：空閑讓進、忙則等待、有限等待、讓權(quán)等待

二、硬件同步機制

關(guān)中斷：缺點多：濫用關(guān)中斷.造成嚴(yán)重后果、關(guān)中斷時間過長、不適用于多CPU系統(tǒng)

(因為一個處理器關(guān)中斷并不能防止進程在其他處理器上執(zhí)行相同的臨界段代碼)

Test-and-Set:不斷測試lock,如果是FALSE,就進入臨界區(qū)，并lock==TRUE;否則

測試到TS(s)==TRUE

Swap指令：一直等，直至!|key==TRUE

但以上都不符合"讓權(quán)等待"原則

三、信號量機制

進入?yún)^(qū)的代碼用來檢查臨界資源是否

一個訪問臨界資茯正在被其它進程使用，若正在被訪問.

則不能進入臨界區(qū)，若未被訪問，則

可進入臨界區(qū)，并設(shè)置訪問標(biāo)志為真。

\___________________

While(1)

{entrysection;〃進入?yún)^(qū)“

criticalsection;〃臨界區(qū)

exitsection;〃退出區(qū)、

remaindersection；〃剩余吟福界區(qū)正在被訪.

1:的標(biāo)志設(shè)置為假。

整形信號量：s<o,就一直等，直到釋放互斥資源

記錄型信號量：整形信號量不符合"讓權(quán)等待"原則。如果有資源，就分配，如果無，就

插入阻塞隊列；釋放資源，如果有等待，就激活

AND型信號量：一口氣全分配

信號量集：有多個信號量(S信號量，至少要t個，每次分配d個)

——wlit(mutex)和signal(mutex)必須成對出班一

缺少wait(mutex)不能保證對臨鼻資源的互斥訪啰

少signal(nutex)會使臨界資源永遠(yuǎn)不被釋放大

而使因等待該資源而阻塞的進程不能被喚醒。

procedurewait(S)

varS:semaphore;

beginn

S.value:=S.value-l;

ifS.value<0thenblock(S.L)

end

1）S.value>0表示有S.value個資源可用，S.value=0表

示無資源可用。

2）執(zhí)行S.vahie?l表示請求分配一個S代表的資源；

3）若S.vahievO,表示系統(tǒng)已無該類資源，申請者阻塞。

:時，IS.vahiel表示該信號量上阻塞的進程數(shù)；

proceduresignal(S)

varS:semaphore;

begin

S.value:=S.value+l;

ifS.value<0thenwakeup(S.L);物理含義:

end

1）執(zhí)行s.vahie+1表示進程釋放一個S代表的資源，；

2）若s.valuev=0,表示尚有進程因等待S代表的資源而處

二阻塞狀態(tài)，所以應(yīng)喚醒其中之一。

寺殊情況：當(dāng)S.value的初值為1,此時的信號量轉(zhuǎn)化為

反斥信號量。

四、信號量的應(yīng)用

利用信號量實現(xiàn)進程互斥：mutex=（-1,0,1）=（無，一1臨一阻隊，一臨一信隊）

利用信號量實現(xiàn)前趨關(guān)系：需要的信號量被占用了，就這樣實現(xiàn)

用P、V操作實現(xiàn)進程同步與互斥結(jié)論：

1)P、V操作必須成對出現(xiàn)，有一個P操作就有一個V

操作。

當(dāng)為互斥操作時，它們同處于一個進程。

當(dāng)為同步操作時，則不在同一進程。

2)一個同步P操作與一個互斥P操作在一起時，同步P

操作在互斥P操作前。而兩個V操作順序無關(guān)緊要。

五、管程機制

描述：為解決信號量機制分散、容易死鎖的問題，發(fā)明新同步工具——管程

定義：定義一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程所執(zhí)行(在該數(shù)據(jù)結(jié)構(gòu)上)的一組操作，這組操

作能同步進程和改變管程中的數(shù)據(jù)

組成：管程名稱、數(shù)據(jù)結(jié)構(gòu)的說明、對數(shù)據(jù)結(jié)構(gòu)進行操作的過程、初始化的語句

特性：模塊化、抽象數(shù)據(jù)類型、信息掩蔽

管程與進程不同：都有數(shù)據(jù)結(jié)構(gòu),一個公.一個私、管程操作同步.初始化.進程順序執(zhí)行、

管程為解決互斥資源.進程實現(xiàn)并發(fā)性、進程調(diào)用管程.進程主動.管程被動、管程不能并發(fā).

進程能并發(fā)、管程是os的一個資源管理模塊.進程有動態(tài)性

條件變量：增加一個條件變量，萬一發(fā)生意外，在管程中被掛起或被阻塞"下一個進程都

可以繼續(xù)執(zhí)行

⑤經(jīng)典進程的同步問題

一、生產(chǎn)者-消費者問題

記錄型信號量解決：如果緩沖區(qū)空，而且能夠獲取信號量，就投放產(chǎn)品；如果緩沖區(qū)有產(chǎn)

品，而且能夠獲取信號量，就消費

AND信號量解決：一口氣全分配

管程解決：利用管程只有一個進程能夠使用的屬性

二、哲學(xué)家進餐問題

記錄型信號量解決：先拿左.后那右、先放左.后放右

解決死鎖：最多4人取筷子、先檢查.有左右筷子才能取、奇左右.偶右左

AND信號量解決：一口氣全分配

三、讀者-寫者問題

描述：可以多讀一、一旦開始寫.就不能讀或?qū)?/p>

記錄型信號量解決：

讀操作：等rmutex就是為了改readcount一無人讀？看看是否在寫.等

wmutex—readcount++T■自增完成.rmutex還你一讀讀讀一等rmutex為了自減

readcount一無人讀?可以寫了.還你wmutex

寫操作：等wmutex.即無讀無寫一寫完.還你wmutex

利用信號量集機制：

讀：限制reader個數(shù)—如果mx是1.就讀一最后釋放一reader個數(shù)

寫：如果mx是1.并且讀者數(shù)為0.就寫一寫完釋放mx

⑥進程通信

一、進程通信類型

共享存儲器系統(tǒng)：某些數(shù)據(jù)結(jié)構(gòu)和共享存儲區(qū)、管道通信系統(tǒng)、消息傳遞系統(tǒng)、C-S系統(tǒng)

二、消息傳遞通信的實現(xiàn)方式

（-）直接消息傳遞系統(tǒng)

1.直接通信原語：對稱尋址方式、非對稱尋址方式

2.消息格式：較短的減少系統(tǒng)處理和存儲的開銷、較長可以方便

3.進程同步方式：發(fā)塞收塞（進程間緊密同步.無緩沖）、發(fā)通收塞（平常狀態(tài)）、發(fā)通收

通（發(fā)生某事件無法繼續(xù)運行）、（無發(fā)塞收通）

4.通信鏈路：用"建立連接"原語建立通信鏈路.用完拆、用"發(fā)送命令"原語建立鏈路，

還分單向和雙向

（二）信箱通信（間接）

1.定義：是數(shù)據(jù)結(jié)構(gòu).分信箱頭和信箱體

2.原語：創(chuàng)建和撤銷.發(fā)送和接收

3.類型：私用、公用（操作系統(tǒng)創(chuàng)建）、共享（進程創(chuàng)建）

4.進程之間的關(guān)系：一對一、多對一、一對多、多對多

三、直接消息傳遞系統(tǒng)實例

消息緩沖隊列通信機制中的數(shù)據(jù)結(jié)構(gòu)：利用數(shù)據(jù)結(jié)構(gòu)式消息緩沖區(qū)、在PCB增加有關(guān)通信

的數(shù)據(jù)項

原語：設(shè)置發(fā)送區(qū)、申請PCB（B）的緩沖區(qū)i、復(fù)制到緩沖區(qū)、插入消息隊列、移出消息隊

列、復(fù)制到接收區(qū)、釋放緩沖區(qū)

⑦線程的基本概念

描述：就是為了提高程序并發(fā)執(zhí)行的程度

一、線程的引入

進程的兩個基本屬性：進程是一個可擁有資源的獨立單位、進程同時是一個可獨立調(diào)度和

分派的基本單位

進程并發(fā)執(zhí)行所需的時空開銷：創(chuàng)建進程、撤銷進程、進程切換

線程一作為調(diào)度和分派的基本單位：線程輕裝上陣

二、線程與進程比較

調(diào)度的基本單位：線程是調(diào)度和分派的基本單位、跨進程，會切換進程

并發(fā)性：線程的合作.能夠并發(fā)

擁有資源：有TCB.但只是必不可少、保證獨立運行的資源

獨立性：同一進程的不同線程共享進程的內(nèi)存地址空間和資源

系統(tǒng)開銷：因為輕裝.所以減少開銷、提升速度

支持多處理機系統(tǒng)：對多線程進程，多個線程可以分配到多個處理機上

三、線程的狀態(tài)和線程控制塊

線程運行的三個狀態(tài)：和進程一樣

線程控制塊TCB:標(biāo)識符、一組寄存器、運行狀態(tài)、優(yōu)先級、線程專有存儲區(qū)、信號屏蔽、

堆棧指針

多線程OS中的進程屬性：進程是可擁有資源的基本單位、多個線程可并發(fā)執(zhí)行、進程已

不是可執(zhí)行的實體

⑧線程的實現(xiàn)

一、線程的實現(xiàn)方式

內(nèi)核支持線程KLT:

優(yōu)點：內(nèi)核調(diào)度同一進程多個線程并行執(zhí)行、一個線程阻塞.其他線程占有處理機、支持小

數(shù)據(jù)結(jié)構(gòu)和堆棧.切換較快開銷小、內(nèi)核本身采用多線程技術(shù)提高系統(tǒng)執(zhí)彳亍速度和效率

用戶級線程ULT:

優(yōu)點：無需內(nèi)核.節(jié)省模式切換的開銷、調(diào)度算法進程專用、與OS無關(guān).甚至可以在操作系

統(tǒng)平臺實現(xiàn)

缺點：一個線程阻塞.同進程的其他線程都會塞、只有一個CPU.只有一個線程能執(zhí)行、按

進程分配.不公平

組合方式：

多對一模型：優(yōu)點：開銷小、缺點：一塞進程全塞、只有一線程訪問內(nèi)核、多線程不能同

時在多個處理機上運行

一對一模型：一個用戶級線程映射到一個內(nèi)核支持線程

多對多模型：一對一和多對一的結(jié)合

二、線程的實現(xiàn)

內(nèi)核支持線程的實現(xiàn)：創(chuàng)建線程、保存信息、調(diào)度和切換線程、撤銷線程、回收資源

用戶級線程的實現(xiàn)：

運行時系統(tǒng)：用于管理和控制線程的函數(shù)的集合，這些函數(shù)駐留用戶空間.并作為用戶級線

程與內(nèi)核之間的接口

內(nèi)核控制線程：連接到LWP,連接到LWP的線程才能與內(nèi)核通信

對于設(shè)置了用戶級線程的系統(tǒng)，調(diào)度仍以進程為單

位進行。例若進程A中包含1個用戶級線程，進程B包含

假如系統(tǒng)設(shè)置的是內(nèi)核支持線程，則調(diào)度便是以線

程為單位進行。例若進程A中包含1個內(nèi)核支持線程，進

三、線程的創(chuàng)建和終止

線程的創(chuàng)建：初始化線程、創(chuàng)建后返回線程標(biāo)識符

線程的終止：終止線程用函數(shù)或系統(tǒng)調(diào)用終止操作.但有些線程被建立就會一直執(zhí)行。大多

數(shù)os,線程被中止后并不立即釋放所占資源，只有“其他線程"執(zhí)行分離函數(shù)才會分離

資源，才能被其他線程利用。雖然未釋放的資源也可以被其他線程使用，但要有個"等待

線程終止”的連接命令作保險.否則一直阻塞

第三章處理機調(diào)度與死鎖

①處理機調(diào)度的層次和調(diào)度算法的目標(biāo)

描述：作業(yè)可能要經(jīng)歷多級處理機調(diào)度

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

(-)高級調(diào)度(長程調(diào)度/作業(yè)調(diào)度)

對象是作業(yè)、決定將外存中處于后備隊列的作業(yè)調(diào)入內(nèi)存.創(chuàng)建進程和分配資源.并放入就緒

隊列、主要存在于多道批處理系統(tǒng)，分時和實時系統(tǒng)不設(shè)置高級調(diào)度

（二）低級調(diào)度（進程調(diào)度;短程調(diào)度）

對象是進程（/內(nèi)核級線程）、決定就緒隊列哪個進程獲得處理機、多道批.分時和實時都

要配置

（三）中級調(diào)度（內(nèi)存調(diào)度）（存儲器的對換功能）

對象是暫時不能運行的進程、把這些進程調(diào)到外存.設(shè)為掛起狀態(tài)、一有條件.稍微有空就變

為就緒狀態(tài)

★分級按運行頻率劃分

二、處理機調(diào)度算法的目標(biāo)

（一）共同目標(biāo)

提高資源利用率、公平、平衡、策略強制執(zhí)行

（二）批處理系統(tǒng)目標(biāo)

處理機利用率高、平均周轉(zhuǎn)時間短、系統(tǒng)吞吐量高

］「3

,平均周轉(zhuǎn)時間描述沏T=-

作業(yè)的周轉(zhuǎn)時間T與系統(tǒng)為它提供服務(wù)的時間戛之比,

即為777小稱為帶權(quán)周轉(zhuǎn)時間，而平均帶權(quán)周轉(zhuǎn)時間則

可表示為：

nT

W=-洋

ni=l1Si

（三）分時系統(tǒng)目標(biāo)

響應(yīng)時間快、均衡性

（四）實時系統(tǒng)目標(biāo)

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

②作業(yè)與作業(yè)調(diào)度

一、批處理系統(tǒng)中的作業(yè)

（一）作業(yè)和作業(yè)步

作業(yè)：包括程序.數(shù)據(jù)和作業(yè)說明書、在批處理系統(tǒng).作業(yè)是基本單位從外存調(diào)入內(nèi)存

作業(yè)步：獨立步驟

（二）作業(yè)控制塊（JCB）

包括作業(yè)標(biāo)識、用戶名稱、用戶賬號、作業(yè)類型、作業(yè)狀態(tài)、調(diào)度信息、資源需求、資源

使用情況等

流程：進入系統(tǒng)一創(chuàng)建JCBT根據(jù)類型放到后備隊列等待調(diào)度T入內(nèi)存T根據(jù)JCB和作業(yè)

說明書控制一完成T回收資源.撤銷JCB

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

收容階段-后備狀態(tài)、運行階段-運行狀態(tài)、完成階段-完成狀態(tài)

二、作業(yè)調(diào)度的主要任務(wù)

也叫：接納調(diào)度

考慮：接納多少作業(yè)、接納哪些作業(yè)

三、先來先服務(wù)FCFS和短作業(yè)優(yōu)先SJF調(diào)度算法

（-）先來先服務(wù)FCFS

就這樣.完成或阻塞才分配到其他進程、實際中和其他算法結(jié)合使用

有利于長作業(yè)（進程），不利于短作業(yè)（進程）

（二）短作業(yè)優(yōu)先SJF

實際用得多、要預(yù)知作業(yè)運行時間、長作業(yè)、緊迫作業(yè)不利、無人機交互

四、優(yōu)先級調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法

（一）優(yōu)先級調(diào)度算法

外部賦予作業(yè)優(yōu)先級

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

集SJF.FCFS的優(yōu)點.兼顧長作業(yè)、但要做相應(yīng)比計算.增加系統(tǒng)開銷（Exp.做過類似）

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

’-要求服務(wù)時間一要求服務(wù)時間

③進程調(diào)度

一、進程調(diào)度的任務(wù)、機制和方式

（-）進程調(diào)度的任務(wù)

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

（二）進程調(diào)度機制

排隊器：插入就緒隊列

分配器：從就緒隊列取出.分配處理機

上下文切換器：保存、裝入新的CPU現(xiàn)場信息等內(nèi)容

（三）進程調(diào)度方式

非搶占方式：只有完成或因某事無法繼續(xù)運行、I/O、執(zhí)行了原語操作如block,才會引起

進程調(diào)度

優(yōu)點：簡單、開銷小、適用大多數(shù)批處理系統(tǒng)

搶占方式：對分時系統(tǒng)而言.有人機交互、對實時系統(tǒng)而言.能滿足任務(wù)需求

主要原則：優(yōu)先權(quán)原則、短進程優(yōu)先原則、時間片原則

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

（-）輪轉(zhuǎn)法（RR）的基本原理

按FCFS策略排成就緒隊列，每隔一定時間就產(chǎn)生一次中斷

（二）進程切換時機

時間片未用完就完成：馬上調(diào)度隊首進程.啟動新時間片

時間片完還沒完成：中斷.進程被調(diào)到就緒隊列隊尾

（三）時間片大小的確定

太短有利于短進程、太長退化為FCFS算法.要計算平均周轉(zhuǎn)時間（帶權(quán)周轉(zhuǎn)時間）

三、優(yōu)先級調(diào)度算法

（-）優(yōu)先級調(diào)度算法的類型

非搶占式和搶占式

（二）優(yōu)先級的類型

確定優(yōu)先級的依據(jù)：

靜態(tài)優(yōu)先級：進程類型（系統(tǒng)進程優(yōu)先權(quán)高于用戶進程優(yōu)先權(quán)）、進程對資源的需求（少

則優(yōu)先）、用戶需求（緊迫程度、花費）

動態(tài)優(yōu)先級：先賦予優(yōu)先級，隨著進程推進或等待時間增加而改變

四、多隊列調(diào)度算法

將一條就緒隊列拆分成多條，各有各調(diào)度算法

五、多級反饋隊列調(diào)度算法

(-)調(diào)度機制

多條就緒隊列、隊列內(nèi)使用FCFS算法.一個時間片未完成就放到下一個隊列的末尾.最后一

個隊列用RR方式、按隊列優(yōu)先級調(diào)度.前隊列空才到本隊列運行

(二)調(diào)度算法的性能

終端型用戶、短批處理作業(yè)用戶、長批處理作業(yè)用戶

六、基于公平原則調(diào)度算法

(-)保證調(diào)度算法

保證處理機公平分配

功能：跟蹤進程已經(jīng)執(zhí)行的處理時間、該時間除以n、計算實際處理時間和應(yīng)獲得時間之

比、匕瞰比率、比率最低的獲得處理機

(二)公平分享調(diào)度算法

考慮多用戶

④實時調(diào)度

描述：實時系統(tǒng)有兩種實時任務(wù)——HRT和SRT

一、實現(xiàn)實時調(diào)度的基本條件

（一）提供必要信息

就緒時間、開始截止和完成截止時間、處理時間、資源要求、優(yōu)先級

（二）系統(tǒng)處理能力強

（處理時間i/周期時間i）總和＜1.未考慮任務(wù)切換花費的時間還應(yīng)該留有余地

提高系統(tǒng)處理能力的途徑：單處理機系統(tǒng)增強處理能力.顯著減少每個任務(wù)的處理時間、多

處理機系統(tǒng).就變成（處理時間i/周期時間i）總和＜N

（三）采用搶占式調(diào)度機制

執(zhí)行完關(guān)鍵程序和臨界區(qū)后，能及時將自己阻塞起來，以釋放處理機

（四）具有快速切換機制

對中斷的快速響應(yīng)能力、快速的任務(wù)分派能力

二、實時調(diào)度算法的分類

根據(jù)任務(wù)性質(zhì)：H/S

根據(jù)調(diào)度方式：非搶占式/搶占式

（-）非搶占式調(diào)度算法

輪轉(zhuǎn)、優(yōu)先調(diào)度，不適合實時系統(tǒng)。進程自動放棄處理機，才進行調(diào)度。

（二）搶占式調(diào)度算法

基于時鐘中斷的搶占式優(yōu)先級調(diào)度算法：等待時鐘中斷發(fā)生才剝奪當(dāng)前任務(wù)的執(zhí)行

立即搶占優(yōu)先調(diào)度算法：好快好快只要任務(wù)未處于臨界區(qū).就立即剝奪當(dāng)前任務(wù)執(zhí)行

優(yōu)先權(quán)原則、短作業(yè)(進程)優(yōu)先原則、時間片原則。

三、最早截止時間優(yōu)先EDF算法

非搶占式調(diào)度方式用于非周期實時任務(wù)：開始截止時間早的排前

搶占式調(diào)度方式用于周期實時任務(wù)：最早截止時間優(yōu)先算法

四、最低松弛度優(yōu)先LLF算法

緊急程度越高，優(yōu)先級越高。

松弛度二必須完成的時間點?本身所需運行時間?當(dāng)前時間:

五、優(yōu)先級倒置

(-)優(yōu)先級倒置的形成

(二)優(yōu)先級倒置的解決方法

繼承動態(tài)優(yōu)先級的方法：P3繼承P1的優(yōu)先級.一方面避免P2搶占處理機、另一方面釋放

mutex資源

⑤死鎖概述

一、資源問題

指互斥資源、不可被搶占的資源

(-)可重用性資源和消耗性資源

可重用性資源：一個只能分配給一個進程使用、順序為請求.使用.釋放、數(shù)目相對固定.運

行期間不能創(chuàng)建或刪除

可消耗性資源：在進程運行中數(shù)目不斷變化.可為0、可以不斷創(chuàng)建.放入緩沖區(qū)、可以由進

程創(chuàng)建.使用并不再返回資源類

（二）可搶占性資源和不可搶占性資源

可搶占性資源：可以被其他進程搶占.如CPU和主存

不可搶占性資源：一旦分配給進程就不能強制收回.要做到底

二、計算機系統(tǒng)中的死鎖

（-）競爭不可搶占性資源引起死鎖

我要你的，你要我的，形成環(huán)路，死鎖

（二）競爭可消耗資源引起死鎖

譬如消息通信機制.先讀后寫.就會死鎖

（三）進程推進順序不當(dāng)引起死鎖

競爭不可搶占性資源引起死鎖的翻版.多畫了一個圖

三、死鎖的定義、必要條件和處理方法

（-）死鎖的定義

這組死鎖進程都在等其他進程釋放所占資源

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

互斥條件：一段時間只被一個進程占用

請求和保持條件：進程已經(jīng)保持至少一個條件.但有提出新資源請求

不可搶占條件：只能在進程用完才能釋放

循環(huán)等待條件：存在循環(huán)鏈

（三）處理死鎖的方法

預(yù)防死鎖：設(shè)置限制條件.破壞產(chǎn)生死鎖四個必要條件來預(yù)防

避免死鎖：在資源動態(tài)分配時.用防止系統(tǒng)進入不安全狀態(tài)

檢測死鎖：通過檢測機構(gòu)及時檢測死鎖.采取適當(dāng)措施以解脫

解除死鎖：撤銷進程.回收資源.分配給處于阻塞的進程

防范逐漸減弱.但資源利用率提高.進程因資源因素而阻塞的頻度下降

⑥預(yù)防死鎖

一、破壞"請求和保持"條件

保證：進程請求

資源時，不持有不可搶占資源

第一種協(xié)議：一次性全部申請，從而破壞"請求條件"、缺點是資源被嚴(yán)重浪費.進程饑餓

第二種協(xié)議：先釋放資源.再請求新資源

二、破壞"不可搶占”條件

當(dāng)保持了某些不可搶占資源后提出新資源請求不得滿足.就必須釋放已經(jīng)保持的資源.等需

要時再申請

缺點：增加周轉(zhuǎn)時間、增加系統(tǒng)開銷、降低系統(tǒng)吞吐量

三、破壞“循環(huán)等待"條件

總有一個進程占據(jù)了較高序號的資源.此后它繼續(xù)申請的資源必然是空閑的

⑦避免死鎖

一、系統(tǒng)安全狀態(tài)

（-）安全狀態(tài)

計算一個資源分配的安全性.如果分配不會導(dǎo)致不安全狀態(tài).才可將資源分配給進程

（二）安全狀態(tài)之例

（三）由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換

二、利用銀行家算法避免死鎖

（-）銀行家算法中的數(shù)據(jù)結(jié)構(gòu)

Availalbe、Max、Allocation.Need

（二）銀行家算法

睇wiki"銀行家算法”條目

聲明：Request是請求向量

Request<Need,否則出錯

Request<Available,否則P等待

系統(tǒng)試探分配資源給P,并執(zhí)行Availalbe-=Requeset;Allocation+=Request;Need-

=Request

⑧死鎖的檢測與解除

一、死鎖的檢測

（-）資源分配圖

圓圈代表進程、方格代表一類資源、邊代表資源分配

（二）死鎖的定理

簡化資源分配圖.如果不能完全簡化.就會死鎖

死鎖狀態(tài)的充分條件是：當(dāng)?shù)﹥H當(dāng)資源分配圖是

不可完全簡化的（死鎖定理）。

（三）死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)

類似于銀行家算法？？？

二、死鎖的解除

常用兩種方法：搶占資源、終止/撤銷進程

（一）終止進程的方法

終止所有死鎖進程：會功虧一簫

逐個終止進程：找到代價最小.考慮優(yōu)先級、已執(zhí)行時間.還需的時間、已用資源、交互式還

是批處理式

（二）付出代價最小的死鎖解除算法

很不實際

為把系統(tǒng)從死鎖狀態(tài)中解脫出來，所花費的代價可

表示為：R（S）min=min{Cui}+min{Cuj）+min{Cul）+...

第四章存儲器管理

①存儲器的層次結(jié)構(gòu)

一、多層結(jié)構(gòu)的存儲器系統(tǒng)

CPU寄存器；

高速緩存Cache、主存儲器RAM、磁盤緩存；

固定磁盤、可移動存儲介質(zhì)

二、可執(zhí)行存儲器

就是CPU寄存器和主存.訪問很快

二、主存儲器與寄存器

(-)主存儲器

又叫主存or內(nèi)存.相比CPU執(zhí)行速度.它還是很慢.所以引入寄存器和高速緩存

(二)寄存器

完全與CPU協(xié)同工作.但好貴

三、高速緩存和磁盤緩存

(-)高速緩存

備份主存中較常用的數(shù)據(jù).以減少CPU對主存儲器的訪問次數(shù)

(二)磁盤緩存

因為磁盤I/O速度遠(yuǎn)低于主存訪問速度.所以設(shè)置磁盤緩存來暫存頻繁使用的一部分磁盤數(shù)

據(jù)和信息

②程序的裝入和鏈接

用戶程序要在OS中運行.要先裝入內(nèi)存.再轉(zhuǎn)換為一個可執(zhí)行程序：編譯、鏈接、裝入

一、程序的裝入

（-）絕對裝入方式

當(dāng)OS很小.且僅能運行單道程序時.完全有可能知道程序駐留在內(nèi)存的位置，那么就可以產(chǎn)

生絕對地址的目標(biāo)代碼

（二）可重定位裝入方式（靜態(tài)重定位）

多道程序下.邏輯地址和物理地址不同.要加上起始地址.但只在進程裝入時一次完成.故稱為

靜態(tài)重定位.可裝到內(nèi)存任何允許位置

嗷據(jù)地址和指多

地址都需要修附

（三）動態(tài)運行時的裝入方式

需要重定位寄存器，運行時允許移動

二、程序的鏈接

（一）靜態(tài)鏈接方式

要解決：對相對地址進行修改（子程序的相對地址）、變換外部調(diào)用符號＜生成可執(zhí)行文

件后不再拆開.又叫靜態(tài)鏈接方式）

（二）裝入時動態(tài)鏈接

便于修改和更新（各模塊分開存放）、便于實現(xiàn)對目標(biāo)模塊的共享（靜態(tài)每個應(yīng)用模塊必

有目標(biāo)模塊的拷貝.無法共享.但動態(tài)可以一個目標(biāo)鏈接多個應(yīng)用模塊）

（三）運行時動態(tài)鏈接

運行時發(fā)現(xiàn)沒有.就由OS去找這個模塊內(nèi)功加快程序裝入過程和節(jié)約大量內(nèi)存空間

③連續(xù)分配存儲管理方式

一、單一連續(xù)分配

分系統(tǒng)區(qū)和用戶區(qū)單用戶.單任務(wù)操作系統(tǒng)

二、固定分區(qū)分配

劃分分區(qū)的方法：大小相等（一臺計算機控制多臺相同冶煉爐）和大小不等

內(nèi)存分配：通常按大小排隊.建立分區(qū)使用表.如果找不到大小足夠的分區(qū).就拒絕分配內(nèi)存

三、動態(tài)分區(qū)分配

動態(tài)分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)：空閑分區(qū)表、空閑分區(qū)鏈

動態(tài)分區(qū)分配算法：之后介紹4種分配算法和3中索引搜索算法

分區(qū)分配操作：分配內(nèi)存、回收內(nèi)存

四、基于順序搜索的動態(tài)分區(qū)分配算法（不太大系統(tǒng)）

首次適應(yīng)算法（FF）、

優(yōu)點：保留了高址部分的大空閑區(qū)

缺點：低址部分會留下許多碎片

循環(huán)首次適應(yīng)算法（NF）、

優(yōu)點：使空閑分區(qū)分布得較均勻

缺點：缺乏大的空閑分區(qū)

最佳適應(yīng)算法（BF）、

優(yōu)點：可以避免“大材小用”

缺點：會留下許多碎片

最壞適應(yīng)算法（WF）

五、基于索引搜索的動態(tài)分區(qū)分配算法（大、中型系統(tǒng)）

快速適應(yīng)算法（以空間換時間）、伙伴系統(tǒng)（合并回收與均勻分配）、哈希算法

六、動態(tài)可重定位分區(qū)分配

緊湊、

“緊湊”而使程序移動時，只需用新

的起始地址置換原來的起始地址。

動態(tài)重定位、動態(tài)重定位分區(qū)分配算法

在動態(tài)分區(qū)分配算法的基礎(chǔ)上

增加了“緊湊”的功能

④對換

一、多道程序環(huán)境下的對換技術(shù)

（一）甜奐的引入

避免內(nèi)存全部被阻塞.外存卻有很多作業(yè)無法進入內(nèi)存

（二”搬的類型

整體對換（進程對換）、頁面對換（部分對換）——支持虛擬存儲系統(tǒng)

為了實現(xiàn)“進程對換”，系統(tǒng)必須實現(xiàn)三方面

功能：

(1)對換空間的管理

(2)進程的換出

(3)進程的換入。

二、對換空間的管理

(-)對換空間管理的主要目標(biāo)

文件區(qū)管理主要目標(biāo)：先提高文件存儲空間的利用率.離散分配

對換空間管理的主要目標(biāo)：先提高換入換出的速度，連續(xù)分配方式

(二”城區(qū)空閑盤塊管理中的數(shù)據(jù)結(jié)構(gòu)

與內(nèi)存的相似

(三)對奐空間的分配與回收

與內(nèi)存分配和回收雷同

三、進程的換出與換入

(一)進程的換出

選擇被換出的進程：阻塞或睡眠狀態(tài)、優(yōu)先級最低、內(nèi)存駐留時間

進程換出過程

(二)進程的換入

如果發(fā)現(xiàn)許多進程運行時缺頁且內(nèi)存緊張.才啟動對換程序.將部分進程調(diào)至外存

如果缺頁率明顯減少.系統(tǒng)吞吐量已下降.則可以暫停運行又搬程序

⑤分頁存儲管理方式

其實分三種：分頁、分段、段頁式

一、分頁存儲管理的基本方法

（—）頁面和物理塊

頁面：頁號

頁面大?。禾?進程占用較多頁面、太多.碎片多、適中.lkB~8kB

（二）地址結(jié)構(gòu)

頁號：P

頁內(nèi)地址（偏移量）：d

兩個都有公式計算

地址為A,頁而的大小，L,則頁號P和頁

9地址］

P=小咕］

d=［A\MODL

（三）頁表

從頁號到物理塊號的映射

二、地址變換機構(gòu)

（-）基本的地址變換機構(gòu)

如果發(fā)現(xiàn)頁號2頁表長度.就引發(fā)越界中斷；否則頁表始址+頁號*頁表項長度=物理塊號

（二）具有快表的地址變換機構(gòu)

有個快表在高速緩存

三、訪問內(nèi)存的有效時間

EAT=t+t=2t（內(nèi)存）

EAT=a*X+（t+A）（l-a）+t=2t+入-1*a（快表）

四、兩級和多級頁表

（-）兩級頁表

（二）多級頁表

五、反置頁表

（-）反置頁表的引入

（二）地址變換

⑥分段存儲管理方式

一、分段存儲管理的基本方法

（-）方便編程

邏輯地址是由段名（段號）和段內(nèi)偏移量（段內(nèi)地址）決定的

（二）信息共享

段是信息的邏輯單位.簡化共享過程

（三）信息保護

就是可以加個標(biāo)識.不允許讀寫

（四）動態(tài)增長

可以解決這個問題

（五）動態(tài)鏈接

4.2.2

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

（一）分段

每個段有一個段號，連續(xù)的分區(qū)

（二）段表

實現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射，段長和基址

（三）地址變換機構(gòu)

段表項數(shù)目比頁表項數(shù)目少.其所需的聯(lián)想存儲器相對較少.減少存取數(shù)據(jù)的時間

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

頁是信息的物理單位.分頁是系統(tǒng)管理上的需要

while段是存儲管理方式中的邏輯單位.分段目的在于更好滿足用戶的需要

頁大小固定.段大小不固定

分頁的用戶程序地址是一維的.分段是二維的

三、信息共享

分頁存儲管理能夠提高內(nèi)存的利用率。

分段存儲管理能很好地滿足用戶需要。

（-）分頁系統(tǒng)中對程序和數(shù)據(jù)的共享

每個進程都有頁表.也都指向相同的物理塊號

（二）分段系統(tǒng)中的程序和數(shù)據(jù)的共享

可重入代碼是一種不允許任何進程對它進行修改的代碼

配以局部數(shù)據(jù)區(qū).把執(zhí)行中可能改變的部分拷貝到該數(shù)據(jù)區(qū).這樣執(zhí)行時只需對該數(shù)據(jù)區(qū)中的

內(nèi)容修改即可

四、段頁式存儲管理方式

分段T分頁.每段一個段名

段號.比較.加法算段表段號一得到頁號.（比較）.加法算頁表頁號-得到物理塊號.加頁內(nèi)地址

T得物理地址

第五章虛擬存儲器

出現(xiàn)問題：作業(yè)很大、大量作業(yè)要求運行

①虛擬存儲器概述

一、常規(guī)存儲管理方式的特征和局部性原理

（-）常規(guī)存儲管理方式的特征

傳統(tǒng)：一次性、駐留性

（二）局部性原理

絕大部分順序執(zhí)行、調(diào)用進度不超過5、循環(huán)結(jié)構(gòu)由少數(shù)指令構(gòu)成.但多次執(zhí)行、多對數(shù)據(jù)

結(jié)構(gòu)的處理.這些處理局限于很小的部分

時間、空間局限性

(三)虛擬存儲器的基本工作情況

將少數(shù)頁面或段先裝入內(nèi)存即可運行

二、虛擬存儲器的定義和特征

(-)虛擬存儲器的定義

有請求調(diào)入功能和置換功能.能邏輯上對內(nèi)存內(nèi)容加以擴充的一種存儲器系統(tǒng)

(二)虛擬存儲器的特征

多次性、對換性、虛擬性

三、虛擬存儲器的實現(xiàn)方式

(-)分頁請求系統(tǒng)

硬件支持：請求分頁的頁表機制、缺頁中斷機制、地址變換機制

實現(xiàn)請求分頁的軟件

(二)請求分段系統(tǒng)

硬件支持：請求分段的段表機制、缺段中斷機構(gòu)、地址變換機構(gòu)

軟件支持

②請求分頁存儲管理方式

一、請求分頁中的硬件支持

(-)請求頁表機制

（二）缺頁中斷機構(gòu)

（三）地址變換機構(gòu)

二、請求分頁中的內(nèi)存分配

（-）最小物理塊數(shù)的確定

（二）內(nèi)存分配策略

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

（三）物理塊分配算法

算法：平均分配算法、按比例分配算法、考慮優(yōu)先權(quán)的分配算法

三、頁面調(diào)入策略

（-）何時調(diào)入頁面

預(yù)調(diào)頁策略：手動指出哪些頁要調(diào)入內(nèi)存、成功率偏低

請求調(diào)頁策略：一次調(diào)入一頁.須較大系統(tǒng)開銷

（二）從何處調(diào)入頁面

系統(tǒng)擁有足夠的對換區(qū)空間：進程進行前就把進程相關(guān)的文件拷貝到對換區(qū)

系統(tǒng)缺少足夠的對換區(qū)空間：未修改過的不到對換區(qū)以后要用再從文件區(qū)調(diào)入

UNIX方式：從文件區(qū)入.出到對換區(qū)、允許頁面共享

（三）頁面調(diào)入過程

???

（四）缺頁率

???

③頁面置換算法

抖動：一個進程在運行中把大部分時間都花費在頁面置換工作上

一、最佳置換算法和先進先出置換算法

（一）最佳置換算法（看未來）

要知道未來需要哪頁.實際上不可能

（二）先進先出頁面置換算法

剔走最老的頁

二、最近最久未使用和最少使用置換算法（LRU看過去）

（-）最近最久未使用

看最近的n個，最老的踢走

（-）LRU置換算法的硬件支持

寄存器：8位寄存器.R7~R0.R值最小的頁被踢出

棧：最新訪問的是棧頂

（三）最少使用置換算法

現(xiàn)實使用這個多.一旦訪問就在最高位置一

三、Clock置換算法

（一）簡單的CLOCK置換算法

也叫最近未使用算法.就是有個訪問位，1-0T換出

（二）改進型CLOCK置換算法

四類：AM=00~ll

第一步：先找00

第二步：再找01,并置所有頁0X

第三步：再找00,最后找01,一定找到

優(yōu)點：減少I/O

缺點：增加系統(tǒng)開銷

四、頁面緩沖算法

（-）影響頁面換進換出效率的若干因素

頁面置換算法、寫回磁盤的頻率、讀入內(nèi)存的頻率

（二）頁面緩沖算法PBA

顯著降低頁面換進、換出頻率，減少頁面換進換出的開銷

換入換出的開銷大幅減少，才能使用簡單的置換策略，如FIFO

要在內(nèi)存中設(shè)置：空閑頁面鏈表、修改頁面鏈表

五、訪問內(nèi)存的有效時間

如果考慮快表的命中率和缺頁率：EAT=.......

如果僅考慮缺頁率：EAT=

④"抖動”與工作集

一、多道程序度與"抖動”

（一）現(xiàn)象

先增后減

（二）原因

進程太多，物理塊不夠分

二、工作集

（一）工作集的基本概念

如果可以預(yù)知，就可以先調(diào)入內(nèi)存，大大降低缺頁率，從而顯著提高處理機利用率

（二）工作集的定義

引用的集合，類似FIFO

三、"抖動”的預(yù)防方法

（-）采取局部置換策略

"抖動”影響較小

（二）把工作集算法融入到處理機調(diào)度中

每個進程在內(nèi)存的駐留頁面是否足夠多，如果是就調(diào)入新作業(yè)、否則增加新物理塊

（三）利用L=S準(zhǔn)則調(diào)節(jié)缺頁率

缺頁之間的平均時間=平均缺頁服務(wù)時間

（四）選擇暫停的進程

先暫停優(yōu)先級最低的進程、在選擇并不重要，但較大的進程

⑤請求分段存儲管理方式

其實也類似于分頁，要硬件和軟件支持

一、請求分段中的硬件支持

（-）請求段表機制

段表項：段名、段長、段基址、存取方式、訪問字段A、修改位M、存在位P、增補位、

外存始址

A、M:改進型CLOCK置換算法

P:本段是否調(diào)入內(nèi)存

增補位：看是否做過動態(tài)增長

（二）缺段中斷機制（圖5-12）

萬一虛段S不在內(nèi)存中，就阻塞請求進程。如果沒有空閑區(qū)，就要拼接空閑區(qū)或者淘汰實

段以形成空閑區(qū)

之后讀入段S,修改段表及內(nèi)存空區(qū)鏈

（三）地址變換機構(gòu)

就是一個地址變換機構(gòu)

二、分段的共享和保護

（-）共享段表

共享進程計數(shù)count、存取控制字段、段號

（二）共享段的分配與回收

共享段的分配、共享段的回收

（三）分段保護

越界檢查、存取控制檢查、環(huán)保護機構(gòu)

第六章輸入輸出系統(tǒng)

①I/O系統(tǒng)的功能、模型和接口

一、I/O系統(tǒng)的基本功能

（-）隱藏物理設(shè)備的細(xì)節(jié)

（二）與設(shè)備的無關(guān)性

自動安裝并尋找驅(qū)動程序，即插即用

（三）提高處理機和I/O設(shè)備的利用率

讓處理機和I/O設(shè)備并行操作

（四）對I/O設(shè)備進行控制

這是驅(qū)動程序的功能

（五）確保對設(shè)備的正確共享

獨占設(shè)備：打印機、磁帶機

共享設(shè)備：磁盤

（六）錯誤處理

低級能夠解決就不向高級報告，請求高級軟件解決

二、I/O系統(tǒng)的層次結(jié)構(gòu)和模型

（-）1/0軟件的層次結(jié)構(gòu)

用戶層I/O軟件

設(shè)備獨立性軟件：映射、保護、分塊、緩沖、分配

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

中斷處理程序

（-）1/0系統(tǒng)中各種模塊之間的層次視圖

I/O系統(tǒng)上下接口（圖6-2）

I/O系統(tǒng)的分層：中斷處理程序-設(shè)備驅(qū)動程序-設(shè)備獨立性軟件

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

（-）塊設(shè)備接口

塊設(shè)備、隱藏磁盤二維結(jié)構(gòu)、抽象命令映射為低層操作

（二）流設(shè)備接口（Unix的）

字符設(shè)備：效率低、不可尋址

get和put操作：有緩沖區(qū)

in-control指令：互斥方式實現(xiàn)共享

（三）網(wǎng)絡(luò)通信接口

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

一、I/O設(shè)備

（-）1/0設(shè)備的類型

按使用特性：存儲設(shè)備、I/O設(shè)備（輸入輸出交互的）

按傳輸速率：低速、中速、高速

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

接口：數(shù)據(jù)信號線、控制信號線、狀態(tài)信號線

二、設(shè)備控制器

（-）設(shè)備控制器的基本功能

接收和識別命令、數(shù)據(jù)交換、標(biāo)識和報告設(shè)備的狀態(tài)、數(shù)據(jù)緩沖區(qū)、差錯控制

（二）設(shè)備控制器的組成

設(shè)備控制器與處理機的接口、設(shè)備控制器與設(shè)備的接口、I/O邏輯

三、內(nèi)存映像I/O

（一）利用特定的I/O指令

缺點：訪問內(nèi)存和訪問設(shè)備要兩種不同的指令

（二）內(nèi)存映像I/O

就是k為界限，04kwn-l,就是內(nèi)存地址;k>n,就是寄存器地址。統(tǒng)一了對內(nèi)存和對控

制器的訪問方法

四、I/O通道

（-）1/0通道設(shè)備的引入

這是一種特殊的處理機，但只局限于I/O相關(guān)的指令、而且沒有自己的內(nèi)存

（二）通道類型

字節(jié)多路通道：一個大水喉，多條小水管；一個換頭快，一個速率慢

數(shù)組選擇通道：利用率低

數(shù)組多路通道：甚至可以并行操作

（三）"瓶頸"問題

增加通路即可解決

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

一、中斷簡介

（-）中斷和陷入

中斷：由外部設(shè)備引起，暫停當(dāng)前程序，執(zhí)行中斷處理程序

陷入：CPU內(nèi)部事件引起的，多是出錯故障

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

中斷向量表：asm有學(xué)

中斷優(yōu)先級：現(xiàn)實中有多個中斷信號源，要規(guī)定不同優(yōu)先級

（三）對多中斷源的處理方式

屏蔽中斷：順序執(zhí)行。優(yōu)點簡單；缺點無視實時中斷請求

嵌套中斷：有個優(yōu)先級

二、中斷處理程序步驟

測定是否有未響應(yīng)中斷信號；

保護被中斷進程的CPU環(huán)境；

轉(zhuǎn)入相應(yīng)設(shè)備處理程序；

中斷處理；

恢復(fù)CPU現(xiàn)場并退出中斷

④設(shè)備驅(qū)動程序

一、設(shè)備驅(qū)動程序概述

（-）設(shè)備驅(qū)動程序的功能

接收命令和參數(shù)，并轉(zhuǎn)換為低層操作序列

檢直I/O合法性，了解I/O工作狀態(tài)，傳遞I/O設(shè)備操作有關(guān)參數(shù)，設(shè)置設(shè)備工作方式

及時響應(yīng)設(shè)備控制器發(fā)來的中斷請求，并根據(jù)中斷類型，調(diào)用響應(yīng)中斷處理程序

（二）設(shè)備驅(qū)動程序的特點

抽象的I/O請求轉(zhuǎn)換成具體的I/O操作，反映給I/O進程

和硬件特性緊密相關(guān)，終端驅(qū)動程序可以只有一個

常用控制方式：中斷驅(qū)動、DMA

一部分必須用匯編語言寫，很多驅(qū)動程序基本部分已經(jīng)固化在ROM

允許可重入

（三）設(shè)備處理方式

一類設(shè)備一個進程

一個I/O進程負(fù)責(zé)各類設(shè)備的I/O操作

只為各類設(shè)備設(shè)置相應(yīng)的設(shè)備驅(qū)動程序，供用戶或系統(tǒng)進程調(diào)用（目前用得最多）

二、設(shè)備驅(qū)動程序的處理過程

（一）1省由象要求轉(zhuǎn)換為具體要求

（二）對服務(wù)請求進行校驗

譬如要求打印機輸入數(shù)據(jù)

（三）檢查設(shè)備的狀態(tài)

檢測寄存器中的不同位，了解設(shè)備的狀態(tài)

（四）傳送必要參數(shù)

波特率、奇偶校驗等等參數(shù)

（五）啟動I/O設(shè)備

了解數(shù)據(jù)是否到達(dá)

三、對I/O設(shè)備的控制方式

（-）使用輪詢的可編程I/O方式

無限等待，好浪費CPU

（二）使用中斷的可編程I/O方式

百倍提高CPU利用率

（三）直接存儲器訪問方式

至少傳送一個數(shù)據(jù)塊，DMA方式提高CPU和