第一章 操作系統(tǒng)引論

1.1 操作系統(tǒng)的目標(biāo)和作用

1.1.1 操作系統(tǒng)的目標(biāo)

1. 方便性：系統(tǒng)可以使用編譯命令將用戶采用高級語言書寫的程序翻譯為機器代碼
2. 有效性：提高資源利用率和系統(tǒng)吞吐量
3. 可擴充性：增添模塊
4. 開放性：彼此兼容

1.1.2 操作系統(tǒng)的作用

1. OS作為用戶與計算機硬件間的接口
2. OS作為計算機系統(tǒng)資源的管理者
3. OS實現(xiàn)了對計算機資源的抽象

即：用戶通過IO管理OS帝洪，OS可以進(jìn)行對計算機的資源管理和抽象

1.1.3 操作系統(tǒng)發(fā)展的主要動力

1. 不斷提高計算機資源利用率
2. 方便用戶
3. 器件的不斷更新迭代
4. 計算機體系結(jié)構(gòu)的不斷發(fā)展
5. 不斷提出新的應(yīng)用需求

1.2 操作系統(tǒng)的發(fā)展過程

1.2.1 未配置操作系統(tǒng)的計算機系統(tǒng)

1. 人工操作方式
2. 脫機輸入輸出方式

1.2.2 單道批處理系統(tǒng)

把作業(yè)以脫機方式輸入到磁帶上双藕，并在系統(tǒng)中配上監(jiān)督程序，在它的控制下摘符，使這批作業(yè)能夠被連續(xù)處理购啄。

單道批處理系統(tǒng)是在解決人機矛盾和CPU與IO設(shè)備速度不匹配的矛盾過程中形成的烤送，旨在提高系統(tǒng)資源的利用率和系統(tǒng)吞吐量

缺點

單道批處理系統(tǒng)最主要的缺點是不能充分地利用系統(tǒng)資源歼指。（要等待I/O操作完成，CPU才能工作）

1.2.3 多道批處理系統(tǒng)

用戶所提交的作業(yè)先存放在外存上评姨，排成一個隊列难述，稱為后備隊列，然后由作業(yè)調(diào)度程序按一定的算法從后被隊列中選擇若干個作業(yè)調(diào)入內(nèi)存吐句，使其共享CPU和系統(tǒng)中的各種資源

優(yōu)點

1. 資源利用率高
2. 系統(tǒng)吞吐量大

缺點

1. 平均周轉(zhuǎn)時間長
2. 無交互能力

需要解決的問題

1. 處理機爭用
2. 內(nèi)存分配和保護(hù)
3. IO設(shè)備分配
4. 文件的組織和管理
5. 作業(yè)管理
6. 用戶與系統(tǒng)接口的問題

操作系統(tǒng)的定義

操作系統(tǒng)是一組能夠有效地組織和管理計算機硬件和軟件資源胁后，合理地對各類作業(yè)進(jìn)行調(diào)度，以及方便用戶使用的程序的集合嗦枢。

1.2.4 分時系統(tǒng)

分時系統(tǒng)是指在一臺主機上連接了多個配有顯示器和鍵盤終端并由此組成的系統(tǒng)攀芯，該系統(tǒng)允許多個用戶同時通過自己的終端，以交互方式使用計算機文虏，共享主機中的資源侣诺。

要解決的關(guān)鍵問題

1、及時接收： 配置多路卡氧秘，它可以實現(xiàn)分時多路復(fù)用年鸳。
2、及時處理： 人機交互的關(guān)鍵在于丸相，用戶鍵入命令后阻星，能對自己的作業(yè)及其運行及時地實施控制，或進(jìn)行修改。采用方式如下：
（1）. 作業(yè)直接進(jìn)入內(nèi)存：因為作業(yè)在磁盤上不能運行妥箕，所以作業(yè)應(yīng)直接進(jìn)入內(nèi)存。
（2）. 采用輪轉(zhuǎn)運行方式：引入時間片的概念更舞，每個作業(yè)每次只能運行一個時間片畦幢，然后就暫停運行试疙，系統(tǒng)立即調(diào)度下一個作業(yè)運行渺鹦。如果在一個不長的時間能使所有的作業(yè)都執(zhí)行一個時間片的時間派歌，便可使每個用戶都能及時地與自己的作業(yè)進(jìn)行交互收津，從而可使用戶的請求得到及時響應(yīng)肾档。

特征

1. 多路性
2. 獨立性
3. 及時性
4. 交互性

1.2.5 實時系統(tǒng)

實時系統(tǒng)是指系統(tǒng)能夠及時響應(yīng)外部事件的請求眠寿，在規(guī)定的時間內(nèi)完成對該事件的處理尚困，并控制所有實時任務(wù)協(xié)調(diào)一致地運行椎例。

類型

1. 工業(yè)（武器）控制系統(tǒng)
2. 信息查詢系統(tǒng)
3. 多媒體系統(tǒng)
4. 嵌入式系統(tǒng)

實時任務(wù)的類型：

1. 周期性實時任務(wù)和非周期性任務(wù)
2. 硬實時任務(wù)和軟實時任務(wù)

特征

1. 多路性
2. 獨立性
3. 及時性
4. 交互性
5. 可靠性

1.2.6 微機操作系統(tǒng)的發(fā)展

單用戶單任務(wù)操作系統(tǒng)：MS-DOS
單用戶多任務(wù)操作系統(tǒng)：Windows
多用戶多任務(wù)操作系統(tǒng)：UNIX OS原杂、Linux OS

1.3 操作系統(tǒng)的基本特性

1.3.1 并發(fā)

并發(fā)性

操作系統(tǒng)正是有了這一特征印颤，才使得OS能有效地提高系統(tǒng)中的資源利用率，增加系統(tǒng)的吞吐量穿肄。

并行與并發(fā)：并行性是指兩個及以上的時間在同一時刻發(fā)生年局，并發(fā)性是指兩個及以上的時間在同一時間間隔內(nèi)發(fā)生。

引入進(jìn)程：進(jìn)程是指在系統(tǒng)中能獨立運行并作為資源分配的基本單位咸产，進(jìn)程 = 1組機器指令 + 數(shù)據(jù) + 堆棧矢否，是一個能獨立運行的活動實體。多個進(jìn)程之間可以并發(fā)執(zhí)行和交換信息脑溢。事實上僵朗，進(jìn)程和并發(fā)是現(xiàn)代操作系統(tǒng)中最重要的基本概念，也是操作系統(tǒng)運行的基礎(chǔ)屑彻。

共享性

1. 互斥共享方式：系統(tǒng)中某些資源在規(guī)定的一段時間內(nèi)只允許一個進(jìn)程訪問該資源验庙。因此，系統(tǒng)建立了互斥訪問機制酱酬。
2. 同時訪問方式：系統(tǒng)中某些資源允許一段時間內(nèi)多個進(jìn)程“同時”對它們進(jìn)行訪問壶谒。“同時”是宏觀意義上的膳沽，而在微觀上這些進(jìn)程對該資源的訪問是交替進(jìn)行的汗菜。

并發(fā)性和共享性是多用戶OS的兩個最基本的特征，它們也是互為存在的條件挑社。沒并發(fā)就沒共享陨界，沒共享就沒并發(fā)。

虛擬性

在OS中痛阻，把通過某種技術(shù)將一個物理實體變?yōu)槿舾蓚€邏輯上的對應(yīng)物的功能稱為“虛擬”菌瘪。前者是實的，即實際存在的，而后者是虛的俏扩，是用戶感覺上的東西糜工。
虛擬技術(shù)：

1. 時分復(fù)用技術(shù)：該技術(shù)能提高資源利用率的根本原因在于，它利用某設(shè)備為一個用戶服務(wù)的空閑時間录淡，又轉(zhuǎn)去為其他用戶服務(wù)捌木，使設(shè)備得到最充分的利用。
   （1）. 虛擬處理機技術(shù)
   （2）. 虛擬設(shè)備技術(shù)

2. 空分復(fù)用技術(shù)：如果說嫉戚，多道程序技術(shù)（時分復(fù)用技術(shù)）是通過處理機的空閑時間運行其它程序刨裆，提高了處理機的利用率，那么彬檀，空分復(fù)用技術(shù)則是利用存儲器的空閑空間分區(qū)域存放和運行其它的多道程序帆啃，以此來提高內(nèi)存的利用率。

異步性

進(jìn)程是以人們不可預(yù)知的速度向前推進(jìn)的窍帝，此即進(jìn)程的異步性努潘。

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

1.4.1 處理機管理功能

1. 進(jìn)程控制
2. 進(jìn)程同步
3. 進(jìn)程通信
4. 調(diào)度

1.4.2 存儲器管理功能

1. 內(nèi)存分配
2. 內(nèi)存保護(hù)
3. 地址映射
4. 內(nèi)存擴充

1.4.3 設(shè)備管理功能

1. 緩沖管理
2. 設(shè)備分配
3. 設(shè)備處理

1.4.4 文件管理功能

1. 文件存儲空間的管理
2. 目錄管理
3. 文件的讀/寫管理和保護(hù)

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

1. 用戶接口
2. 程序接口

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

1. 系統(tǒng)安全
2. 網(wǎng)絡(luò)的功能和服務(wù)
3. 支持多媒體

第二章 進(jìn)程的描述與控制

2.1 前驅(qū)圖和程序執(zhí)行

2.1.1 前趨圖

為了能更好的描述程序的順序和并發(fā)，我們用一個有向無循環(huán)圖來表示盯桦，此圖記為DAG慈俯，用于描述進(jìn)程之間執(zhí)行的先后順序

2.1.2 程序順序執(zhí)行

1. 程序的順序執(zhí)行
   每一個程序段完成特定的功能，在執(zhí)行時需要按照某種先后次序順序執(zhí)行

   
   
   image.png

2. 程序順序執(zhí)行的特征
   2.1 順序性：處理機嚴(yán)格按程序規(guī)定的順序執(zhí)行拥峦，即每一操作必須在下一操作開始前結(jié)束
   2.2 封閉性：程序在封閉環(huán)境下運行贴膘，即運行時程序獨占全機資源
   2.3 可再現(xiàn)性：指只要程序執(zhí)行時環(huán)境和初始條件相同，當(dāng)程序重復(fù)執(zhí)行時略号，不論從頭到尾不停頓還是走走停停刑峡，結(jié)果都相同

2.1.3 程序并發(fā)執(zhí)行

1. 程序順序執(zhí)行時，雖然可以給程序員帶來方便玄柠，但系統(tǒng)資源利用率很低突梦，為此，引入多道程序技術(shù)羽利，使程序或程序間能并發(fā)執(zhí)行宫患。然而并非所有程序都能并發(fā)執(zhí)行，事實上只有不存在前趨關(guān)系的程序之間才有可能并發(fā)執(zhí)行这弧，否則無法并發(fā)執(zhí)行

2. 程序并發(fā)執(zhí)行的特征
   2.1 間斷性：由于共享系統(tǒng)資源娃闲，為完成同一任務(wù)而相互合作，使得并發(fā)執(zhí)行的程序之間形成了相互制約的關(guān)系匾浪，導(dǎo)致“執(zhí)行——暫突拾铮——執(zhí)行”的活動規(guī)律
   2.2 失去封閉性：當(dāng)處理機已被分配給某個進(jìn)程運行時，其他程序必須等待蛋辈，顯然程序已經(jīng)失去了封閉性
   2.3 不可再現(xiàn)性：程序經(jīng)過多次執(zhí)行后属拾，即使執(zhí)行的初始環(huán)境相同，但是得到的結(jié)果不同

2.2 進(jìn)程的描述

2.2.1 進(jìn)程的定義和特征

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

2. 進(jìn)程的特征
   2.1 動態(tài)性：有生命周期渐白，是實體的執(zhí)行過程
   2.2 并發(fā)性：多個進(jìn)程實體存在于內(nèi)存中尊浓，并能在一段時間內(nèi)同時運行
   2.3 獨立性：進(jìn)程實體是一個能獨立運行，獨立獲得資源和獨立接受調(diào)度的基本單位纯衍。凡未建立PCB的程序都不能作為一個獨立的單位運行
   2.4 異步性：各自獨立眠砾，不可預(yù)知的速度向前推進(jìn)。為了使進(jìn)程在并發(fā)時仍可使結(jié)果再現(xiàn)托酸，配備了同步機制

2.2.2 進(jìn)程的基本狀態(tài)及轉(zhuǎn)換

三種基本狀態(tài)的轉(zhuǎn)換：

image.png

就緒狀態(tài)：進(jìn)程已處于準(zhǔn)備好運行的狀態(tài)，分配到除CPU以外的所有必要資源后柒巫，只要獲得CPU即可執(zhí)行

執(zhí)行狀態(tài)：進(jìn)程已經(jīng)獲得CPU励堡，程序正在執(zhí)行的狀態(tài)

阻塞狀態(tài)：指正在執(zhí)行的進(jìn)程由于發(fā)生某事件暫時無法繼續(xù)執(zhí)行時的狀態(tài)，即阻塞

引入創(chuàng)建和終止?fàn)顟B(tài)：

image.png

創(chuàng)建狀態(tài)：申請一個空白PCB堡掏，并向PCB中填寫用于控制和管理進(jìn)程的信息应结，然后為該進(jìn)程分配運行時所必須的資源，最后把該進(jìn)程轉(zhuǎn)入就緒狀態(tài)并插入就緒隊列中

終止?fàn)顟B(tài)：首先等待操作系統(tǒng)進(jìn)行善后處理泉唁，最后將PCB清零鹅龄，并將PCB空間返回系統(tǒng)。當(dāng)一個進(jìn)程達(dá)到自然結(jié)束點亭畜，或出現(xiàn)了無法克服的錯誤扮休，或被操作系統(tǒng)終結(jié)，它將進(jìn)入終止?fàn)顟B(tài)拴鸵，清零PCB并將空白PCB返回給系統(tǒng)

引入掛起操作：

image.png

掛起操作：為了系統(tǒng)和用戶觀察分析進(jìn)程的需要玷坠，引入了掛起操作，線程被掛起時意味著此時進(jìn)程處于靜止?fàn)顟B(tài)劲藐。如果進(jìn)程正在執(zhí)行八堡，它將暫停執(zhí)行。如果原本處于就緒狀態(tài)聘芜，則進(jìn)程此時不接受調(diào)度

掛起操作引入的原因：

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

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

1. 操作系統(tǒng)中用于管理控制的數(shù)據(jù)結(jié)構(gòu)
   計算機系統(tǒng)中兄渺，每個資源和每個進(jìn)程都設(shè)置了一個數(shù)據(jù)結(jié)構(gòu)，用于表征其實體汰现，稱之為資源信息表或進(jìn)程信息表挂谍，其中包含了資源或進(jìn)程的標(biāo)識，描述服鹅，狀態(tài)等信息以及一批指針凳兵，通過指針將同類資源或進(jìn)程的信息表，或者統(tǒng)一進(jìn)程所占用的資源信息表分類連接成不同的隊列企软，便于操作系統(tǒng)進(jìn)行查找

OS管理的數(shù)據(jù)結(jié)構(gòu)一般分為：內(nèi)存表庐扫，設(shè)備表，文件表，用于進(jìn)程管理的進(jìn)程表

2. 進(jìn)程控制塊PCB的作用
   2.1 作為獨立運行基本單位的標(biāo)志
   2.2 能實現(xiàn)間斷性運行方式：有了PCB之后形庭，系統(tǒng)就可將CPU現(xiàn)場信息保存在被中斷進(jìn)程的PCB中铅辞，供該進(jìn)程再次被調(diào)度執(zhí)行時恢復(fù)CPU現(xiàn)場時使用。
   2.3 提供進(jìn)程管理所需要的信息
   2.4 提供進(jìn)程調(diào)度所需要的信息
   2.5 實現(xiàn)與其它進(jìn)程的同步與通信

3. 進(jìn)程控制塊中的信息
   3.1 進(jìn)程標(biāo)識符：唯一地標(biāo)識一個進(jìn)程萨醒，通常有兩種標(biāo)識符
   （1）. 外部標(biāo)識符：方便用戶對進(jìn)程進(jìn)行訪問
   （2）. 內(nèi)部標(biāo)識符：方便系統(tǒng)對進(jìn)程地使用斟珊，賦予每一個進(jìn)程一個唯一的數(shù)字標(biāo)識
   3.2 處理及狀態(tài)：也稱為處理機的上下文，主要是處理機的各種內(nèi)存中的內(nèi)容組成的富纸，包括通用寄存器囤踩，指令計數(shù)器，程序狀態(tài)字PSW晓褪，用戶棧指針
   3.3 進(jìn)程調(diào)度信息：信息包括進(jìn)程狀態(tài)堵漱，進(jìn)程優(yōu)先級，進(jìn)程調(diào)度所需的其他信息涣仿，事件阻塞原因
   3.4 進(jìn)程控制信息：信息包括程序和數(shù)據(jù)的地址勤庐，進(jìn)程同步和通信機制，資源清單好港，鏈接指針

4. 進(jìn)程控制塊的組織方式
   為了有效管理組織PCB愉镰，主要方式有以下三種
   4.1 線性方式：將所有PCB放在一張表中，每次查找掃描整張表
   4.2 鏈接方式

   
   
   image.png

4.3 索引方式

image.png

2.3 進(jìn)程控制

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

絕大多數(shù)OS內(nèi)核都包含了以下兩大方面功能

支撐功能

提供給OS其他眾多模塊所需要的一些基本功能钧汹，以便支撐這些模塊工作丈探，最基本的三種支撐功能為：

1. 中斷處理：最基本的功能，是整個OS賴以活動的基礎(chǔ)
2. 時鐘管理：內(nèi)核的基本功能崭孤，進(jìn)程時長控制
3. 原語操作：若干條指令組成类嗤，完成一定功能的一個過程，是原子操作辨宠，執(zhí)行時不可被中斷

資源管理功能

1. 進(jìn)程管理：進(jìn)程調(diào)度與分派遗锣，放在內(nèi)核中，提高性能
2. 存儲器管理：存儲器管理軟件的運行頻率較高嗤形，放在內(nèi)核中精偿，保證有較高的運行速度
3. 設(shè)備管理：與硬件緊密相關(guān)，放在內(nèi)核中

2.3.2 進(jìn)程的創(chuàng)建

1. 進(jìn)程的層次結(jié)構(gòu)

OS中允許一個進(jìn)程創(chuàng)建另一個進(jìn)程嗎赋兵，通常把創(chuàng)建進(jìn)程的進(jìn)程叫做父進(jìn)程笔咽，被創(chuàng)建的進(jìn)程稱為子進(jìn)程，如UNIX中霹期，進(jìn)程與其子孫進(jìn)程共同組成一個家族

子進(jìn)程可以繼承父進(jìn)程的所有資源叶组，如父進(jìn)程打開的文件，所分配到的緩沖區(qū)历造。子進(jìn)程被撤銷時甩十，資源歸還給父進(jìn)程船庇。此外撤銷父進(jìn)程時，也應(yīng)撤銷其所有子進(jìn)程

值得注意的是Windows不存在任何進(jìn)程層次結(jié)構(gòu)的概念侣监，所有進(jìn)程地位相同鸭轮。如果一個進(jìn)程創(chuàng)建另外的進(jìn)程時創(chuàng)建進(jìn)程獲得了一個句柄，作用相當(dāng)于一個令牌橄霉，可以用來控制被創(chuàng)建的進(jìn)程窃爷，句柄是可以傳遞的，因此進(jìn)程不再是層次關(guān)系姓蜂，而是獲得句柄與否按厘，控制與被控制的關(guān)系

2. 進(jìn)程圖

image.png

3. 引起創(chuàng)建進(jìn)程的事件

為使程序之間能并發(fā)運行，應(yīng)先為他們創(chuàng)建進(jìn)程钱慢，導(dǎo)致一個進(jìn)程去創(chuàng)建另一個進(jìn)程的典型事件有4種

1. 用戶登錄
2. 作業(yè)調(diào)度
3. 提供服務(wù)
4. 應(yīng)用請求

4. 進(jìn)程的創(chuàng)建流程

1. 申請空白PCB：為新進(jìn)程申請獲得唯一的數(shù)字標(biāo)識刻剥，并從PCB集合種索取一個空白PCB

2. 為新進(jìn)程分配其所需的資源：包括各種物理邏輯資源，如內(nèi)存滩字，文件，IO設(shè)備等御吞。這些資源從OS本身或僅從父進(jìn)程獲得麦箍，新進(jìn)程對這些資源的需求詳情也要提前告知OS或其父進(jìn)程

3. 初始化進(jìn)程控制塊PCB：
   初始化標(biāo)識信息，將系統(tǒng)分配的標(biāo)識符和父進(jìn)程標(biāo)識符填入新PCB中
   初始化處理機狀態(tài)信息陶珠，使程序計數(shù)器指向程序入口地址挟裂，使棧幀指向棧頂
   初始化處理機控制信息，將進(jìn)程的狀態(tài)設(shè)置為就緒狀態(tài)或靜止就緒狀態(tài)揍诽，對于優(yōu)先級通常是將他們設(shè)置為最低優(yōu)先級

4. 如果進(jìn)程就緒隊列能夠接納新進(jìn)程诀蓉，便將新進(jìn)程插入就緒隊列

2.3.3 進(jìn)程的終止

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

1. 正常結(jié)束：任務(wù)完成，準(zhǔn)備退出
2. 異常結(jié)束：越界錯暑脆，保護(hù)錯渠啤，非法指令，特權(quán)指令錯添吗，運行超時沥曹，等待超時，算數(shù)運算錯碟联，IO故障等
3. 外界干預(yù)：程序外界請求而終止運行妓美，如操作系統(tǒng)干預(yù)，父進(jìn)程請求鲤孵，父進(jìn)程終止等

2. 進(jìn)程的終止過程

1. 根據(jù)被終止進(jìn)程的標(biāo)識符
2. 若被終止進(jìn)程正處于執(zhí)行狀態(tài)
3. 若該進(jìn)程還有子孫進(jìn)程
4. 將被終止進(jìn)程所擁有的全部資源或者歸還給父進(jìn)程
5. 將被終止進(jìn)程從所在隊列中移出

2.3.4 進(jìn)程的阻塞和喚醒

1. 引起進(jìn)程阻塞和喚醒的事件

1. 向系統(tǒng)請求共享資源失敗
2. 等待某種操作的完成
3. 新數(shù)據(jù)尚未到達(dá)
4. 等待新任務(wù)的到達(dá)

2. 進(jìn)程阻塞過程

正在執(zhí)行的進(jìn)程壶栋，如果發(fā)生了上述某事件，進(jìn)程便通過調(diào)用阻塞原語block將自己阻塞普监，可見阻塞是一種主動行為贵试。進(jìn)入block過程后琉兜，由于該進(jìn)程還處于執(zhí)行狀態(tài)，所以應(yīng)先立即停止執(zhí)行锡移，把進(jìn)程控制塊中的先行狀態(tài)由執(zhí)行改為阻塞呕童，并將PCB插入到阻塞隊列

3. 進(jìn)程喚醒過程

當(dāng)被阻塞的進(jìn)程所期待的事件發(fā)生時，有關(guān)進(jìn)程調(diào)用喚醒原語wakeup淆珊，將等待中的進(jìn)程喚醒夺饲。wakeup的執(zhí)行過程是首先把被阻塞的進(jìn)程從等待該事件的阻塞隊列中移出，將其PCB中的現(xiàn)行狀態(tài)由阻塞改為就緒施符，然后將PCB插入到就緒隊列中

注意的是往声，block和wakeup是一對作用相反的原語，使用時必須成對使用戳吝，否則線程將因阻塞而無法被喚醒浩销，再無機會運行

2.3.5 進(jìn)程的掛起與激活

1. 進(jìn)程的掛起

當(dāng)系統(tǒng)中出現(xiàn)進(jìn)程掛起事件時，OS調(diào)用掛起原語suspend將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起听哭。suspend的執(zhí)行過程是首先檢查被掛起進(jìn)程的狀態(tài)慢洋，若處于活動就緒狀態(tài)，便將其改為靜止就緒陆盘。對于活動阻塞狀態(tài)的進(jìn)程普筹，則改為靜止阻塞。為了方便父進(jìn)程考察該進(jìn)程的運行狀態(tài)隘马，把該進(jìn)程的PCB復(fù)制到指定內(nèi)存區(qū)域太防。最后若被掛起的進(jìn)程正在執(zhí)行，則轉(zhuǎn)向調(diào)度程序重新調(diào)度

2. 進(jìn)程的激活過程

當(dāng)系統(tǒng)中發(fā)生激活進(jìn)程的事件時酸员，OS調(diào)用激活原語active蜒车，將指定進(jìn)程激活。先將進(jìn)程從外存調(diào)入內(nèi)存幔嗦，檢查進(jìn)程的現(xiàn)行狀態(tài)酿愧。若是靜止就緒，則改為活動就緒邀泉。若為靜止阻塞寓娩，則改為活動阻塞。加入采用搶占式調(diào)度策略呼渣，每當(dāng)有靜止就緒進(jìn)程被激活而插入就緒隊列時棘伴，便應(yīng)檢查是否要進(jìn)行重新調(diào)度，即由調(diào)度程序?qū)⒈患せ畹倪M(jìn)程與當(dāng)前進(jìn)程兩者的優(yōu)先級進(jìn)行比較屁置，如果被激活的進(jìn)程優(yōu)先級低焊夸，則不必重新調(diào)度，否則蓝角，立即剝奪當(dāng)前進(jìn)程的運行阱穗，把處理機分配給剛剛被激活的進(jìn)程

2.4 進(jìn)程同步

OS中引入進(jìn)程后饭冬，一方面使系統(tǒng)中多道程序并發(fā)執(zhí)行，有效改善資源利用率和系統(tǒng)吞吐量揪阶，但也使得系統(tǒng)變得復(fù)雜昌抠，不妥善處理，會使程序結(jié)果存在不確定性

2.4.1 進(jìn)程同步的基本概念

進(jìn)程同步機制的主要任務(wù)是對多個相關(guān)程序在執(zhí)行次序上進(jìn)行協(xié)調(diào)鲁僚，使并發(fā)執(zhí)行的進(jìn)程間能很好的互相合作炊苫，共享資源，從而使程序有可再現(xiàn)性

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

多道程序環(huán)境下冰沙，對于同處于一個系統(tǒng)中的多個進(jìn)程侨艾，由于他們共享系統(tǒng)中的資源，或為完成某一任務(wù)而合作拓挥，他們之間可能存在著以下兩種形式的制約關(guān)系

1. 間接相互制約：由于程序并發(fā)執(zhí)行時共享系統(tǒng)資源唠梨，使這些并發(fā)執(zhí)行的程序之間形成相互制約的關(guān)系，對于一些臨界資源必須保證多個進(jìn)程對其只能互斥的進(jìn)行訪問侥啤，由此形成了資源共享的所謂間接相互制約的關(guān)系
2. 直接相互制約：為了完成某任務(wù)而建立兩個或多個進(jìn)程当叭，這些進(jìn)程將為完成同一項任務(wù)而相互合作。進(jìn)程間的直接制約關(guān)系就是源于它們之間的相互合作

另外盖灸，在多道程序環(huán)境下科展，由于存在上述兩類相互制約關(guān)系，進(jìn)程在運行過程中能否獲得處理及運行與以怎樣的速度運行糠雨，并不能由進(jìn)程自身控制，此即異步性徘跪。由此產(chǎn)生對共享變量或數(shù)據(jù)結(jié)構(gòu)等資源不正確的訪問次序甘邀，從而造成結(jié)果不一致。為杜絕這種差錯垮庐，則必須對進(jìn)程的執(zhí)行次序進(jìn)行協(xié)調(diào)松邪，保證按順序執(zhí)行。

2. 臨界資源和臨界區(qū)

不論是硬件臨界資源還是軟件臨界資源哨查，多個線程必須互斥地進(jìn)行訪問逗抑，每個進(jìn)程中訪問臨界資源的代碼就是臨界區(qū)。為此寒亥，每個線程在進(jìn)入臨界區(qū)前應(yīng)先對欲訪問的臨界資源進(jìn)行檢查邮府，看它是否被訪問，這段代碼叫進(jìn)入?yún)^(qū)溉奕。相應(yīng)的褂傀，在臨界區(qū)后也要加上一段代碼，稱為退出區(qū)加勤。其余部分叫做剩余區(qū)仙辟，代碼描述如下：

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

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

1. 空閑讓進(jìn)：無進(jìn)程處于臨界區(qū)時同波，資源空閑歉井，允許進(jìn)入
2. 忙則等待：已有線程進(jìn)入臨界區(qū)偷遗，臨界資源正在被訪問， 其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待粥航，保證互斥訪問
3. 有限等待：對要求訪問臨界資源的進(jìn)程粟焊，應(yīng)保證在有限時間內(nèi)能進(jìn)入自己的臨界區(qū)冤狡，防止“死等狀態(tài)”
4. 讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時，應(yīng)立即釋放處理機吆玖，以免進(jìn)程陷入“忙等”狀態(tài)

2.4.2 硬件同步機制

關(guān)中斷

是實現(xiàn)互斥的最簡單方法之一筒溃。在進(jìn)入鎖測試之前關(guān)閉中斷，直到完成鎖測試并上鎖之后才能打開中斷沾乘。

利用Test-and-Set指令實現(xiàn)互斥

硬件指令怜奖，測試并建立，以實現(xiàn)互斥

Swap指令實現(xiàn)進(jìn)程互斥

對換指令翅阵，用于交換兩個字的內(nèi)容

2.4.3 信號量機制

信號量S是一個整數(shù)歪玲，S大于等于零是代表可供并發(fā)進(jìn)程使用的資源實體數(shù)，當(dāng)S小于零時則表示正在等待使用臨界區(qū)的進(jìn)程數(shù)掷匠，Dijkstra同時提出了對信號量操作的PV原語

P原語操作的動作是：

1. S減1滥崩；
2. 若S減1后仍大于或等于零，則進(jìn)程繼續(xù)執(zhí)行讹语；
3. 若S減1后小于零钙皮，則該進(jìn)程被阻塞后進(jìn)入與該信號相對應(yīng)的隊列中，然后轉(zhuǎn)進(jìn)程調(diào)度

V原語操作的動作是：

1. S加1顽决；
2. 若相加結(jié)果大于零短条，則進(jìn)程繼續(xù)執(zhí)行；
3. 若相加結(jié)果小于或等于零才菠，則從該信號的等待隊列中喚醒一等待進(jìn)程茸时，然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度

PV操作對于每一個進(jìn)程來說，都只能進(jìn)行一次赋访，而且必須成對使用可都。在PV原語執(zhí)行期間不允許有中斷的發(fā)生

2.5 經(jīng)典的進(jìn)程同步問題

2.5.1 生產(chǎn)者消費者問題

輸入時，輸入進(jìn)程是生產(chǎn)者蚓耽，計算機進(jìn)程是消費者渠牲。輸出時，計算機進(jìn)程是生產(chǎn)者步悠，打印進(jìn)程是消費者

2.5.2 哲學(xué)家進(jìn)餐問題

五個哲學(xué)家公用一張圓桌嘱兼，分別坐在周圍五張椅子上。在圓桌上由五個碗和五只筷子贤徒，他們的生活方式是交替的進(jìn)行思考和進(jìn)餐芹壕，平時一個哲學(xué)家進(jìn)行思考汇四，饑餓時拿取其左右靠他最近的筷子，只有在他拿到兩只筷子時才能進(jìn)餐踢涌，進(jìn)餐后則繼續(xù)思考

2.5.3 讀者寫者問題

一個數(shù)據(jù)文件或記錄被多個進(jìn)程共享通孽，我們把只要求度該文件的進(jìn)程稱為讀者，其他進(jìn)程稱為寫者睁壁。允許多個進(jìn)程同時讀一個共享對象背苦，因為讀操作不會使數(shù)據(jù)文件混亂。但不允許一個寫者進(jìn)程和其他讀者進(jìn)程或?qū)懻哌M(jìn)程同時訪問共享對象潘明，因為這種訪問會引起混亂行剂。所以這個問題是指保證一個寫者進(jìn)程必須與其他進(jìn)程互斥地訪問共享對象的同步問題，常被用來測試新同步原語

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

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

調(diào)度實質(zhì)上是一種資源的分配钳降，處理機調(diào)度是對處理機資源的分配厚宰，調(diào)度算法是指根據(jù)處理機分配策略所規(guī)定的處理機分配算法。

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

1. 高級調(diào)度

高級調(diào)度又稱長程調(diào)度遂填，作業(yè)調(diào)度铲觉。調(diào)度對象是作業(yè)。根據(jù)算法將外存上處于后備隊列中的哪幾個作業(yè)調(diào)入內(nèi)存吓坚，為他們分配資源撵幽，創(chuàng)建進(jìn)程。主要用于多批道處理系統(tǒng)礁击，分時系統(tǒng)和實時系統(tǒng)不設(shè)置高級調(diào)度

2. 低級調(diào)度

低級調(diào)度又稱短程調(diào)度或進(jìn)程調(diào)度盐杂。調(diào)度對象是進(jìn)程。根據(jù)算法決定就緒隊列中的哪個進(jìn)程獲得處理機哆窿，由分派程序?qū)⑻幚頇C分配給選中的進(jìn)程链烈，是一種最基本的調(diào)度，在多批道處理更耻，分時，實時三種OS中都必須設(shè)置

3. 中級調(diào)度

中級調(diào)度又稱內(nèi)存調(diào)度捏膨，目的是提高內(nèi)存利用率和系統(tǒng)吞吐量秧均，運行頻率介于上述兩種之間

上述三種調(diào)度中，進(jìn)程調(diào)度運行頻率最高号涯，僅10~100ms便進(jìn)行一次目胡，因此稱為短程調(diào)度。為避免占用太多CPU時間链快，不宜將進(jìn)程調(diào)度算法設(shè)計復(fù)雜誉己。

作業(yè)調(diào)度往往發(fā)生在一批作業(yè)已經(jīng)運行完畢退出系統(tǒng)，需要重新調(diào)入一批作業(yè)進(jìn)入內(nèi)存時域蜗，作業(yè)調(diào)度的周期較長巨双，大約幾分鐘一次噪猾，因此稱為長程調(diào)度。由于其運行頻率較低筑累，故允許作業(yè)調(diào)度算法花費較多時間

中級調(diào)度運行頻率基本處于兩種調(diào)度之間袱蜡，因此稱為中級調(diào)度

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

1. 處理機調(diào)度算法的共同目標(biāo)

1.1 資源利用率：CPU利用率 = CPU有效工作時間 / (CPU有效工作時間 + CPU空閑等待時間)

1.2 公平性：應(yīng)使諸進(jìn)程獲得合理的CPU時間，不發(fā)生饑餓現(xiàn)象

1.3 平衡性： 使CPU和各種外設(shè)都能經(jīng)常處于忙碌狀態(tài)

1.4 策略強制執(zhí)行： 如安全策略慢宗，只要需要坪蚁，必須予以準(zhǔn)確執(zhí)行

2. 批處理系統(tǒng)的目標(biāo)

2.1 平均周轉(zhuǎn)時間短：平均周轉(zhuǎn)時間可描述為 T = (1 / n) * (T1 + T2 + T3 + ... + Ti)。平均帶權(quán)周轉(zhuǎn)時間可描述為 W = T / Ts镜沽，Ts為系統(tǒng)為其提供服務(wù)的時間
2.2 系統(tǒng)吞吐量高
2.3 處理機利用率高

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

1. 響應(yīng)時間快
2. 均衡性

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

1. 截至?xí)r間的保證
2. 可預(yù)測性

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

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

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

1. 作業(yè)：作業(yè)是一個比程序更廣泛的概念敏晤，不僅包含了通常的程序和數(shù)據(jù)，還應(yīng)配有一份作業(yè)說明書缅茉，系統(tǒng)根據(jù)說明書對程序運行進(jìn)行控制嘴脾，在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的
2. 作業(yè)步：作業(yè)運行期間宾舅，每個作業(yè)都必須經(jīng)過若干個相對獨立又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果统阿，每一個加工步驟叫做作業(yè)步

2. 作業(yè)控制塊

每當(dāng)一個作業(yè)進(jìn)入系統(tǒng)，作業(yè)注冊程序為該作業(yè)創(chuàng)建一個作業(yè)控制塊JCB筹我，根據(jù)作業(yè)類型扶平，放入對應(yīng)的作業(yè)后備隊列等待調(diào)度。作業(yè)結(jié)束時蔬蕊，系統(tǒng)負(fù)責(zé)回收并撤銷

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

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

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

1. 接納多少作業(yè)
2. 接納哪些作業(yè)

3.2.3 先來先服務(wù)（FCFS） & 短作業(yè)優(yōu)先（SJF）

FCFS：最簡單的調(diào)度算法结澄，作業(yè)調(diào)度和進(jìn)程調(diào)度都可用。當(dāng)采用該算法時岸夯，系統(tǒng)按照作業(yè)到達(dá)的先后次序來進(jìn)行調(diào)度麻献，或者說它是優(yōu)先考慮在系統(tǒng)中等待時間最長的作業(yè)，而不管該作業(yè)所需執(zhí)行時間的長短猜扮。

SJF：由于短作業(yè)實際上占很大比例勉吻，為了能使其比長作業(yè)優(yōu)先進(jìn)行，便以作業(yè)長短計算優(yōu)先級旅赢，作業(yè)越短齿桃，其調(diào)度優(yōu)先級越高。分別可用于作業(yè)調(diào)度和進(jìn)程調(diào)度

SJF算法優(yōu)缺點：

1. 必須預(yù)知作業(yè)的運行時間
2. 對長作業(yè)非常不利煮盼，長作業(yè)的周轉(zhuǎn)時間會明顯地增長
3. 采用FCFS算法時短纵，人—機無法實現(xiàn)交互
4. 該調(diào)度算法完全未考慮作業(yè)的緊迫程度，故不能保證緊迫性作業(yè)能得到及時處理

3.2.4優(yōu)先級調(diào)度算法（PSA） & 高響應(yīng)比優(yōu)先調(diào)度算法（HRRN）

PSA：基于作業(yè)的緊迫程度僵控，由外部賦予優(yōu)先級香到，系統(tǒng)從后備隊列中選擇若干個優(yōu)先級最高的作業(yè)放入內(nèi)存

HRRN：既照顧了短作業(yè)，又不致使長作業(yè)的等待時間過長，從而改善了處理機調(diào)度的性能悠就。

image.png

由上述公式可以看出：

1. 如果作業(yè)的等待時間相同千绪，則要求服務(wù)的時間愈短，其優(yōu)先權(quán)越高理卑，類似于SJF算法翘紊，有利于短作業(yè)
2. 當(dāng)要求服務(wù)的時間相同時，等待時間越長的優(yōu)先權(quán)越高藐唠，類似于FCFS算法
3. 對于長作業(yè)的優(yōu)先級帆疟，可以隨等待時間的增加而增高，當(dāng)其等待時間足夠長時宇立，也可以獲得處理機踪宠，因此該算法實現(xiàn)了較好的折中。但利用該算法的每次進(jìn)行調(diào)度之前妈嘹，都需要先做響應(yīng)比的計算柳琢，會增加系統(tǒng)開銷

3.3 進(jìn)程調(diào)度

進(jìn)程調(diào)度是對OS系統(tǒng)性能影響最大的調(diào)度

3.3.1 進(jìn)程調(diào)度的任務(wù)，機制和方式

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

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

2. 進(jìn)程調(diào)度機制

進(jìn)程調(diào)度機制中润脸，有下面三個基本部分

1. 排隊器：提高進(jìn)程調(diào)度效率柬脸，如下策略排成一個或多個隊列，以便調(diào)度程序能盡快找到它毙驯，以后每當(dāng)有一個進(jìn)程轉(zhuǎn)變?yōu)榫途w狀態(tài)時倒堕，排隊器便將它插入到相應(yīng)的就緒隊列

2. 分派器：根據(jù)進(jìn)程調(diào)度程序所選定的進(jìn)程，將其從就緒隊列中取出爆价，然后進(jìn)行從分派器道新選出的進(jìn)程間的上下文切換垦巴，將處理機分配給新選出的進(jìn)程

3. 上下文切換器：對處理機進(jìn)行切換時，會發(fā)生兩對上下文的切換操作
   3.1 第一對上下文切換時铭段，OS保存當(dāng)前進(jìn)程的上下文骤宣，把當(dāng)前進(jìn)程的處理機寄存器內(nèi)容保存到該進(jìn)程的進(jìn)程控制塊的相應(yīng)單元，再裝入分派程序的上下文序愚，以便分派程序運行
   3.2 第二對上下文切換時是移除分派程序的上下文憔披，而把新選進(jìn)程的CPU現(xiàn)場信息裝入到處理機的各個相應(yīng)寄存器中，以便新選進(jìn)程運行

   
   
   image.png

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

1. 非搶占方式 ：采用這種調(diào)度方式時爸吮，一旦把處理機分配給某進(jìn)程后芬膝，就一直讓它運行下去，絕不會因為時鐘中斷或者任何其它原因去搶占當(dāng)前正在運行進(jìn)程的處理機拗胜，直至該進(jìn)程完成蔗候，或者發(fā)生某事件而被阻塞時怒允，才把處理機分配給其他進(jìn)程埂软。

采用該方式引起調(diào)度的因素有：

1. 正在執(zhí)行的進(jìn)程運行完畢或者因發(fā)生某事件而使其無法再繼續(xù)運行
2. 正在執(zhí)行中的進(jìn)程因提出I/O請求而暫停運行
3. 在進(jìn)程通信或同步過程中，執(zhí)行了某種原語操作，如Block原語勘畔。

這種調(diào)度方式的優(yōu)點是實現(xiàn)簡單所灸，系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)炫七。但不能用于分時系統(tǒng)和大多數(shù)實時系統(tǒng)爬立。

2. 搶占方式：這種調(diào)度方式允許調(diào)度程序根據(jù)某種原則，去暫停某個正在執(zhí)行的進(jìn)程万哪，將已分配給該進(jìn)程的處理機重新分配給另一進(jìn)程∠姥保現(xiàn)代OS廣泛采用搶占方式。對于批處理系統(tǒng)奕巍，該方式可以防止一個長進(jìn)程長時間地占用處理機吟策，以確保處理機能為所有進(jìn)程提供更為公平的服務(wù)。在分時系統(tǒng)中的止，只有使用搶占方式才有可能實現(xiàn)人—機交互檩坚。在實時系統(tǒng)中，搶占方式能滿足實時任務(wù)的需求诅福。但搶占方式比較復(fù)雜匾委，所需付出的系統(tǒng)開銷也比較大

“搶占”不是一種任意性行為，必須遵循一定的原則

1. 優(yōu)先權(quán)原則：允許優(yōu)先級高的新線程搶占當(dāng)前進(jìn)程的處理機
2. 短進(jìn)程優(yōu)先原則：新到的短進(jìn)程可以搶占當(dāng)前長進(jìn)程的處理機
3. 時間片原則：各進(jìn)程按時間片輪轉(zhuǎn)運行氓润，時間片用完后則停止該進(jìn)程執(zhí)行

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

該算法假設(shè)所有作業(yè)優(yōu)先級都相同（但實際并非如此）赂乐，采用非常公平的處理機分配方式，讓就緒隊列上的每個進(jìn)程每次僅運行一個時間片旺芽，如果就緒隊列上有n個進(jìn)程沪猴，則每個進(jìn)程每次大約都可獲得1/n的處理機時間

基本原理

根據(jù)FCFS策略，將所有的就緒進(jìn)程排成一個就緒隊列采章，設(shè)置一定時間間隔產(chǎn)生一次中斷运嗜，激活系統(tǒng)中的進(jìn)程調(diào)度程序，完成一次調(diào)度悯舟，將CPU分配給隊首進(jìn)程担租。該進(jìn)程運行完畢時再將CPU分配給此時的隊首進(jìn)程，所有進(jìn)程在一個確定時間段內(nèi)都可獲得一次CPU執(zhí)行

進(jìn)程切換時機

1. 若時間片尚未用完抵怎，正在運行的進(jìn)程就已經(jīng)完成奋救，立即激活調(diào)度程序，將它從就緒隊列中刪除反惕，再調(diào)度就緒隊列中隊首的進(jìn)程運行尝艘，并啟動一個新的時間片
2. 在一個時間片用完時，計時器中斷處理程序被激活姿染。如果進(jìn)程尚未運行完畢背亥，調(diào)度程序?qū)阉屯途w隊列的末尾

時間片大小的確定

在RR算法中，時間片大小的確定對系統(tǒng)性能有很大的影響，如果選擇很小的時間片狡汉，將有利于短作業(yè)娄徊，因為它能夠在該時間片內(nèi)完成。但時間片小盾戴，意味著會頻繁地執(zhí)行進(jìn)程調(diào)度和進(jìn)程上下文的切換寄锐，這無疑會增加系統(tǒng)的開銷。反之尖啡，如果時間片選擇得太長橄仆，且為使每個進(jìn)程都能在一個時間片內(nèi)完成，RR算法便退化為FCFS算法衅斩，無法滿足短作業(yè)和交互式用戶的需求沿癞。一個較為可取的時間片大小使略大于一次典型的交互所需要的時間，使大多數(shù)交互式進(jìn)程能在一個時間片內(nèi)完成矛渴，從而獲得很小的響應(yīng)時間

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

將處理機分配給就緒隊列中優(yōu)先級最高的進(jìn)程椎扬，該算法進(jìn)一步分為以下兩種

1. 非搶占式優(yōu)先級調(diào)度算法：一旦處理機分配給就緒隊列中的最高優(yōu)先級進(jìn)程后，該進(jìn)程一直執(zhí)行下去直到結(jié)束具温，系統(tǒng)才將處理機分配給下一優(yōu)先級最高的進(jìn)程運行

2. 搶占式優(yōu)先級調(diào)度算法：把處理機分配給優(yōu)先級最高的進(jìn)程蚕涤，使之執(zhí)行，但在運行期出現(xiàn)了另一個優(yōu)先級更高的進(jìn)程铣猩，就分配給這個優(yōu)先級更高的進(jìn)程運行

優(yōu)先級的類型

1. 靜態(tài)優(yōu)先級：創(chuàng)建進(jìn)程時確定揖铜，整個運行期保持不變。確定優(yōu)先級的依據(jù)有進(jìn)程類型达皿，用戶要求天吓，和進(jìn)程對資源的需求三方面

2. 動態(tài)優(yōu)先級：創(chuàng)建進(jìn)程時，賦予一個優(yōu)先級峦椰，其值隨著進(jìn)程推進(jìn)或等待的時間增加而改變龄寞，獲得更好的調(diào)度性能

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

彌補不同用戶對進(jìn)程調(diào)度不同要求，該算法將系統(tǒng)中的進(jìn)程就緒隊列從一個拆分為若干個汤功，將不同類型或性質(zhì)的進(jìn)程固定分配在不同的就緒隊列中物邑，不同的就緒隊列采用不同的調(diào)度算法，一個就緒隊列中的進(jìn)程可以設(shè)置在不同的優(yōu)先級滔金，不同的就緒隊列本身也可以設(shè)置不同的優(yōu)先級色解。因此，系統(tǒng)可以針對不同用戶進(jìn)程的需求餐茵，很容易提供多種調(diào)度策略科阎。

3.3.5 多級反饋隊列

前面的一些算法都有一定的局限性，此算法不必事先知道各進(jìn)程的運行時間忿族，還可以較好地滿足各類型進(jìn)程的需要锣笨，是目前公認(rèn)的比較好的算法

調(diào)度機制

1. 設(shè)置多個就緒隊列：第一個隊列優(yōu)先級最高刚梭，第二個次之，其余隊列的優(yōu)先級逐個降低票唆。優(yōu)先級越高的隊列中，時間片越小屹徘。例如第二個隊列的時間片要比第一個的時間片長一倍走趋，第i+1個隊列要比第i個的時間片長一倍
2. 每個隊列都采用FCFS算法，當(dāng)輪到某個隊列的某個進(jìn)程執(zhí)行時噪伊，如它能在該時間片內(nèi)完成簿煌，便可撤離系統(tǒng)，否則調(diào)度程序?qū)⑵滢D(zhuǎn)入下一個隊列等待調(diào)度鉴吹，以此類推姨伟，當(dāng)進(jìn)程最后被降到第n個隊列后，在第n個隊列中便采取按RR方式運行

3. 按隊列優(yōu)先級調(diào)度豆励。調(diào)度程序首先調(diào)度最高優(yōu)先級隊列中的諸進(jìn)程運行夺荒， 僅當(dāng)?shù)?~（i-1）所有隊列均空時，才會調(diào)度第i隊列中的進(jìn)程運行良蒸。如果處理機正在第i隊列中為某進(jìn)程服務(wù)時又有新進(jìn)程進(jìn)入任一優(yōu)先級較高的隊列技扼，此時須立即把正在運行的進(jìn)程放回到第i隊列的末尾，而把處理機分配給新到的高優(yōu)先級進(jìn)程

   
   
   image.png

調(diào)度性能

1. 終端型用戶嫩痰。由于終端型用戶提交的作業(yè)多屬于交互型作業(yè)剿吻，通常較小，系統(tǒng)只要能使這些作業(yè)在第一隊列規(guī)定的時間片內(nèi)完成串纺，便可使終端型用戶感到滿意
2. 短批處理作業(yè)用戶丽旅。對于這類作業(yè)，如果可在第一隊列中執(zhí)行完成纺棺，便獲得與終端型作業(yè)一樣的響應(yīng)時間榄笙。對于稍長的短作業(yè)，也只需在第二和第三隊列各執(zhí)行一時間片完成祷蝌，其周轉(zhuǎn)時間仍然較短
3. 長批處理作業(yè)用戶办斑。對于長作業(yè)，它將依次在第1杆逗，2乡翅，…，n個隊列中運行罪郊，然后再按輪轉(zhuǎn)方式運行蠕蚜，用戶不必?fù)?dān)心其作業(yè)長期得不到處理

3.4 實時調(diào)度

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

提供必要的信息

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

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

提高系統(tǒng)處理能力途徑有二：一是采用單處理機系統(tǒng)，增強處理能力悔橄。二是采用多處理機系統(tǒng)

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

滿足HRT任務(wù)對截止時間的要求

4. 具有快速切換機制

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

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

1. 非搶占式調(diào)度算法
2. 搶占式調(diào)度算法

3.4.3 最早截止時間優(yōu)先算法（EDF）

根據(jù)任務(wù)的最早截止時間為優(yōu)先級靶累，結(jié)束越早腺毫，優(yōu)先級越高

3.5 死鎖概述

資源問題

1. 可重用性資源：可供用戶重復(fù)使用多次的資源，每個可重用性資源中的單元只能分配給一個進(jìn)程使用挣柬，不允許多個進(jìn)程共享

2. 可消耗性資源（臨時性資源）：它是在進(jìn)程運行期間潮酒，由進(jìn)程動態(tài)地創(chuàng)建和消耗的，可消耗性資源通常是由生產(chǎn)者進(jìn)程創(chuàng)建邪蛔，由消費者進(jìn)程消耗

3. 可搶占性資源：某進(jìn)程在獲得這類資源后急黎，該資源又可以再被其它進(jìn)程或系統(tǒng)搶占。CPU和主存均屬于可搶占性資源侧到。這類資源不會引起死鎖

4. 不可搶占性資源：一旦系統(tǒng)把某資源分配給該進(jìn)程后勃教，就不能將它強行收回，只能在進(jìn)程用完后自行釋放

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

通常是源于多個進(jìn)程對資源的爭奪

1. 對不可搶占資源進(jìn)行爭奪時會引起死鎖
2. 對可消耗性資源進(jìn)行爭奪時會引起死鎖
3. 進(jìn)程推進(jìn)順序不當(dāng)會引起死鎖匠抗。

3.5.3 死鎖定義故源，必要條件和處理方法

死鎖的定義

如果一組進(jìn)程中的每一個進(jìn)程都在等待僅由改組進(jìn)程中的其它進(jìn)程才能引發(fā)的事件，那么該組進(jìn)程是死鎖的汞贸。

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

只要下面四個條件任意一個不成立死鎖都不會發(fā)生

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

處理死鎖的方法

1. 預(yù)防死鎖
2. 避免死鎖
3. 檢測死鎖
4. 解除死鎖
   從上到下對死鎖的防范程度逐漸減弱绳军，但對應(yīng)的是資源利用率的提高，以及進(jìn)程因資源因素而阻塞的頻度下降（即并發(fā)程度提高）

3.6 預(yù)防死鎖

預(yù)防死鎖是破壞一個或幾個產(chǎn)生死鎖的必要條件來避免死鎖發(fā)生矢腻，由于互斥條件是非共享設(shè)備所必須的删铃，不僅不能改變，還要加以保證踏堡，因此猎唁，主要是破壞產(chǎn)生死鎖的后三個條件。

3.6.1 破壞“請求和保持”條件

第一種協(xié)議

所有進(jìn)程在開始運行之前顷蟆，必須一次性地申請其在整個運行過程中所需的全部資源诫隅。只要有一種資源不能滿足進(jìn)程的要求，即使其它所需的各資源都空閑也不分配給該進(jìn)程帐偎，而讓該進(jìn)程等待

優(yōu)點：簡單逐纬，易行，安全
缺點：資源被嚴(yán)重浪費削樊，使進(jìn)程經(jīng)常會發(fā)生饑餓現(xiàn)象

第二種協(xié)議

它允許一個進(jìn)程只獲得運行初期所需的資源后豁生，便開始運行。進(jìn)程運行過程中再逐步釋放已分配給自己的漫贞、且已用畢的全部資源甸箱，然后再請求新的所需資源。

優(yōu)點：更快完成任務(wù)迅脐，提高利用率芍殖，減少饑餓幾率

3.6.2 破壞“不可搶占”條件

當(dāng)一個已經(jīng)保持了某些不可被搶占資源的進(jìn)程，提出新的資源請求而不能得到滿足時谴蔑，它必須釋放已經(jīng)保持的所有資源豌骏，待以后需要時再重新申請龟梦。

缺點：延長了進(jìn)程的周轉(zhuǎn)時間，增加了系統(tǒng)開銷窃躲，降低了系統(tǒng)吞吐量

3.6.3 破壞“循環(huán)等待”條件

一個能保證“循環(huán)等待”條件不成立的方法是计贰，對系統(tǒng)所有資源類型進(jìn)行線性排序，并賦予不同的序號蒂窒，之后規(guī)定每個進(jìn)程必須按序號遞增的順序請求資源躁倒。

3.7 避免死鎖：

當(dāng)系統(tǒng)進(jìn)入不安全狀態(tài)之后，就有可能進(jìn)入死鎖狀態(tài)刘绣。相反，只要系統(tǒng)處于安全狀態(tài)挣输，系統(tǒng)便不會進(jìn)入死鎖狀態(tài)纬凤。

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

安全狀態(tài)

安全狀態(tài)指系統(tǒng)能按某種進(jìn)程推進(jìn)順序為每個進(jìn)程分配所需的資源，直至滿足每個進(jìn)程對資源的最大需求撩嚼，使每個進(jìn)程可以順利完成

3.7.2 銀行家算法避免死鎖

image.png

image.png

image.png

image.png

此處書上內(nèi)容過多停士，難以總結(jié)，圖片摘自知乎 @Fdaxiong大熊

3.8 死鎖的檢測與解除

如果在系統(tǒng)中，既不采取死鎖預(yù)防措施，也未配有死鎖避免算法榜苫，系統(tǒng)很可能會發(fā)生死鎖竹习，此時系統(tǒng)應(yīng)該提供兩個算法

1. 死鎖檢測算法：該方法用于檢測系統(tǒng)狀態(tài)，以確定系統(tǒng)中是否發(fā)生了死鎖
2. 死鎖解除算法：當(dāng)認(rèn)定系統(tǒng)中發(fā)生了死鎖碍庵，利用該算法可將系統(tǒng)從死鎖狀態(tài)中解脫出來

3.8.1 死鎖的檢測

為了能對系統(tǒng)中是否發(fā)生了死鎖進(jìn)行檢測，系統(tǒng)中必須保存有關(guān)資源的請求和分配信息，提供一種算法薄辅，利用這些信息來檢測系統(tǒng)是否已進(jìn)入死鎖狀態(tài)

資源分配圖

該圖是由一組結(jié)點N和一組邊E所組成的一個對偶G = （N，E）抠璃，它具有下述形式的定義和限制

1. 把N分為兩個互斥的子集站楚，即一組進(jìn)程結(jié)點P和一組資源節(jié)點R。N = P U R

2. 凡屬于E中的一個邊e搏嗡，都連接著P中的一個節(jié)點和R中的一個節(jié)點

   
   
   image.png
   
   

   我們用圓圈代表一個進(jìn)程窿春，用方框代表一類資源。由于一種類型的資源可能有多個采盒，我們用方框中的一個點代表一類資源中的一個資源旧乞。此時請求邊是由進(jìn)程指向方框中中的Rj，而分配邊則應(yīng)始于方框中的一個點

死鎖定理

利用把資源分配圖加以簡化的方法磅氨，來檢測當(dāng)系統(tǒng)處于S狀態(tài)時是否為死鎖狀態(tài)良蛮。簡化后若能消去圖中所有邊，使所有進(jìn)程的結(jié)點都成為孤立結(jié)點悍赢，則稱為可完全簡化圖决瞳，反之則稱為不可完全簡化圖货徙，同樣可以證明S為死鎖狀態(tài)的充分條件是：當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡化的，該充分條件稱為死鎖定理

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

1. 可利用資源向量Available
2. 不占用資源的進(jìn)程記入L表中
3. 從進(jìn)程集合中找到一個Request小于等于Work的進(jìn)程皮胡，將其資源分配圖簡化釋放資源痴颊，增加工作向量Work += Allocation，記入L表中
4. 若不能把所有進(jìn)程都計入L表中屡贺，便表明系統(tǒng)狀態(tài)S的資源分配圖是不可完全簡化的蠢棱，因此發(fā)生死鎖

3.8.2 死鎖的解除

如果利用死鎖檢測算法檢測出在系統(tǒng)中發(fā)生死鎖，應(yīng)立即解除死鎖甩栈，常用解除死鎖的方式有兩種

1. 搶占資源：從一個或多個進(jìn)程中搶占足夠數(shù)量的資源泻仙，分配給死鎖進(jìn)程，以解除死鎖狀態(tài)
2. 終止進(jìn)程：終止系統(tǒng)中的一個或多個死鎖進(jìn)程量没，直至打破循環(huán)環(huán)路玉转，使系統(tǒng)從死鎖狀態(tài)中解脫出來

終止進(jìn)程的方法

1. 終止所有死鎖進(jìn)程：這是最簡單的方法，但是代價很大殴蹄，因為有的進(jìn)程可能已經(jīng)運行了很久
2. 逐個終止進(jìn)程：按照某種順序溫和的終止進(jìn)程究抓，直到有足夠的資源打破循環(huán)等待，把系統(tǒng)從死鎖狀態(tài)中解脫出來袭灯。但是該方法所付出的代價可能也很大刺下，因為每終止一個進(jìn)程都需要用死鎖檢測算法確定系統(tǒng)死鎖是否已經(jīng)被解除，若未解除還需要再終止另一個進(jìn)程

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

1. 找到付出代價最小的終止順序稽荧，但成本高的算法：
   1.1 先從死鎖進(jìn)程組中取出一個橘茉，形成第一層終止，若有n個死鎖進(jìn)程姨丈，則有n個第一層
   1.2 再從n個第一層中取一個捺癞，形成第二層終止，每個第一層又有n-1個第二層終止
   1.3 如此循環(huán)构挤，直到解除死鎖髓介，將各層的總代價計算，得到最小的終止順序

2. 一種比較有效的算法：
   2.1 找到死鎖進(jìn)程組中筋现，終止代價最小的唐础，將其從死鎖進(jìn)程組中刪去
   2.2 再從新的死鎖進(jìn)程組中，找到終止代價最小的矾飞，刪去
   2.3 如此循環(huán)一膨，直到解除死鎖

第四章 存儲器管理

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

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

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

image.png

對于通用計算機而言，存儲層次至少應(yīng)具有三級：最高層為CPU寄存器洒沦，中間為主存豹绪，最底層是輔存，層次越高申眼，訪問速度越快瞒津，價格也越高蝉衣，相應(yīng)的配置存儲容量則越小。CPU寄存器和主存都是操作系統(tǒng)所管轄范圍巷蚪，掉電后信息丟失病毡，輔存屬于可移動設(shè)備，存儲的信息可以被長期保存

可執(zhí)行存儲器

寄存器和主存儲器也被稱為可執(zhí)行存儲器屁柏，操作系統(tǒng)的存儲管理負(fù)責(zé)對可執(zhí)行存儲器的分配啦膜，回收，以及提供在存儲層次間數(shù)據(jù)移動的管理機制

4.1.2 主存儲器和寄存器

主存儲器

主存儲器簡稱內(nèi)存或主存淌喻，是計算機系統(tǒng)中的主要部件僧家，用于保存進(jìn)程運行時的程序和數(shù)據(jù)，也稱可執(zhí)行存儲器裸删。通常八拱，處理機都是從主存儲器中取得指令和數(shù)據(jù)的，并將其所取得的指令放入指令寄存器中烁落，而將其所讀取的數(shù)據(jù)裝入到數(shù)據(jù)寄存器中乘粒，或者反之豌注，將寄存器中的數(shù)據(jù)存入到主存儲器伤塌。由于主存儲器的訪問速度遠(yuǎn)低于CPU執(zhí)行指令的速度，為了緩和這一矛盾轧铁，在計算機系統(tǒng)中引入了寄存器和高速緩存

寄存器

寄存器具有與處理機相同的速度每聪，故對寄存器的訪問速度最快，完全能與CPU協(xié)調(diào)工作齿风，但價格十分昂貴药薯，因此容量不能做得很大

4.1.3 高速緩存和磁盤緩存

高速緩存

高速緩存用于緩和內(nèi)存與處理機速度不匹配問題，它是介于寄存器和存儲器之間的存儲器救斑，主要用于備份主存中較常用的數(shù)據(jù)童本，以減少處理機對主存儲器的訪問次數(shù)，這樣可大幅度提高程序執(zhí)行速度脸候。高速緩存容量遠(yuǎn)大于寄存器穷娱，而比內(nèi)存約小兩到三個數(shù)量級左右。訪問速度快于主存儲器运沦，同時由于速度快價格也越貴泵额，在現(xiàn)有計算機體系中設(shè)置了兩級或多級高速緩存，緊靠內(nèi)存的一級高速緩存的速度最高携添，而容量最小嫁盲，二級高速緩存的容量稍大，速度也稍低

高速緩存涉及到局部性原理：程序執(zhí)行時將呈現(xiàn)出局部性規(guī)律烈掠，即在一較短的時間內(nèi)羞秤，程序的執(zhí)行僅局限于某個部分

磁盤緩存

由于目前磁盤的I/O速度遠(yuǎn)低于對主存的訪問速度缸托，為了緩和兩者之間在速度上的不匹配，而設(shè)置了磁盤緩存锥腻，主要用于暫時存放頻繁使用的一部分磁盤數(shù)據(jù)和信息嗦董，以減少訪問磁盤的次數(shù)

但磁盤緩存與高速緩存不同，它是利用主存中的部分存儲空間暫時存放從磁盤中讀出或（寫入）的信息瘦黑。主存也可以看作是輔存的高速緩存京革，因為，輔存中的數(shù)據(jù)必須復(fù)制到主存方能使用幸斥，反之匹摇，數(shù)據(jù)也必須先存在主存中，才能輸出到輔存

一個文件的數(shù)據(jù)可能先后出現(xiàn)在不同層次的存儲器中

4.2 程序的裝入和鏈接

用戶程序要在系統(tǒng)中運行甲葬，必須先將他裝入內(nèi)存廊勃，然后再將其轉(zhuǎn)變?yōu)橐粋€可以執(zhí)行的程序，通常都要經(jīng)過以下幾個步驟：

1. 編譯：由編譯程序?qū)τ脩粼闯绦蜻M(jìn)行編譯经窖，形成若干個目標(biāo)模塊坡垫。
2. 鏈接：由鏈接程序?qū)⒕幾g后形成的一組目標(biāo)模塊以及它們所需要的庫函數(shù)鏈接在一起，形成一個完整的裝入模塊画侣。

3. 裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存冰悠。

   
   
   image.png

4.2.1 程序的裝入

絕對裝入方式

當(dāng)計算機系統(tǒng)很小，且僅能運行單道程序時配乱，完全有可能知道程序?qū)Ⅰv留在內(nèi)存的什么位置溉卓，此時可以采用絕對裝入方式。用戶程序經(jīng)編譯后搬泥，將產(chǎn)生絕對地址（物理地址）的目標(biāo)代碼

可重定位裝入方式：

在多道程序環(huán)境下桑寨，編譯程序不可能預(yù)知經(jīng)編譯后所得到的目標(biāo)模塊應(yīng)放在內(nèi)存何處。此時忿檩，不可能再用絕對裝入方式尉尾，而應(yīng)采用可重定位裝入方式，它可以根據(jù)內(nèi)存的具體情況將裝入模塊裝入到內(nèi)存的適當(dāng)位置

通常燥透，把在裝入時對目標(biāo)程序中指令和數(shù)據(jù)地址的修改過程稱為重定位沙咏。又因為地址變換通常是在進(jìn)程裝入時一次完成的，以后不再改變兽掰，故稱為靜態(tài)重定位

動態(tài)運行時的裝入方式：

動態(tài)運行時的裝入程序在把裝入模塊裝入內(nèi)存后芭碍，并不立即把裝入模塊中的邏輯地址轉(zhuǎn)換為物理地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進(jìn)行孽尽。因此窖壕，裝入內(nèi)存后的所有地址都仍是邏輯地址

4.2.2 程序的鏈接

源程序經(jīng)過編譯后，可得到一組目標(biāo)模塊。鏈接程序的功能是將這組目標(biāo)模塊以及它們所需要的庫函數(shù)裝配成一個完整的裝入模塊瞻讽。在對目標(biāo)模塊進(jìn)行鏈接時鸳吸，根據(jù)進(jìn)行鏈接的時間不同，可把鏈接分成如下三種

靜態(tài)鏈接方式

在程序運行之前速勇，先將各目標(biāo)模塊及它們所需的庫函數(shù)鏈接成一個完整的裝配模塊晌砾，以后不再拆開

需要解決的問題：

1. 對相對地址進(jìn)行修改

2. 變換外部調(diào)用符號

   
   
   image.png

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

將用戶源程序編譯后所得到的一組目標(biāo)模塊，在裝入內(nèi)存時烦磁，采用邊裝入邊鏈接的鏈接方式养匈。即在裝入一個目標(biāo)模塊時若發(fā)生一個外部模塊調(diào)用事件，將引起裝入程序去找出相應(yīng)的外部目標(biāo)模塊都伪，并將它裝入內(nèi)存呕乎，還要按照圖4-4所示的方式修改目標(biāo)模塊中的相對地址

優(yōu)點：

1. 便于修改和更新
2. 便于實現(xiàn)對目標(biāo)模塊的共享

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

在執(zhí)行過程中，當(dāng)發(fā)現(xiàn)一個被調(diào)用模塊尚未被裝入內(nèi)存時陨晶，立即由OS去找到該模塊猬仁，并將之裝入內(nèi)存，將其鏈接到調(diào)用者模塊上先誉。凡在執(zhí)行過程中未被用到的目標(biāo)模塊湿刽，都不會被調(diào)入內(nèi)存和被鏈接到裝入模塊上，這樣不僅能加快程序的裝入過程褐耳，而且可節(jié)省大量的內(nèi)存空間

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

4.3.1 單一連續(xù)分配

在單道程序環(huán)境下诈闺，當(dāng)時的存儲管理方式是把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分，系統(tǒng)區(qū)僅提供給OS使用漱病，它通常是放在內(nèi)存的低址部分买雾。而在用戶區(qū)內(nèi)存中把曼，僅裝有一道用戶程序杨帽，即整個內(nèi)存的用戶空間由該程序獨占

4.3.2 固定分區(qū)分配

為了能在內(nèi)存中裝入多道程序，且使這些程序之間又不會發(fā)生相互干擾嗤军，于是將整個用戶空間劃分為若干個固定大小的區(qū)域注盈，在每個分區(qū)中只裝入一道作業(yè)

劃分分區(qū)的方法

1. 分區(qū)大小相等
   缺點是缺乏靈活性，即當(dāng)程序太小時叙赚，會造成內(nèi)存空間的浪費老客。當(dāng)程序太大時，一個分區(qū)又不足以裝入該程序震叮，致使該程序無法運行胧砰。盡管如此，對于利用一臺計算機同時控制多個相同對象的場合苇瓣，因為這些對象所需的內(nèi)存空間大小往往相同尉间，這種劃分方式比較方便和實用

2. 分區(qū)大小不等
   為了增加存儲器分配的靈活性，應(yīng)將存儲器分區(qū)劃分為若干個大小不等的分區(qū)

內(nèi)存分配

為了便于內(nèi)存分配，通常將分區(qū)按其大小進(jìn)行排隊哲嘲，并為之建立一張分區(qū)使用表贪薪，其中各表項包括每個分區(qū)的起始地址、大小及狀態(tài)（是否已分配）

image.png

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

也叫可變分區(qū)分配眠副，它是根據(jù)進(jìn)程的實際需要画切，動態(tài)地為之分配內(nèi)存空間。在實現(xiàn)動態(tài)分區(qū)分配時囱怕，將涉及到分區(qū)分配中所用的數(shù)據(jù)結(jié)構(gòu)霍弹，分區(qū)分配算法和分區(qū)的分配與回收操作這樣三方面的問題

數(shù)據(jù)結(jié)構(gòu)

常用數(shù)據(jù)結(jié)構(gòu)有以下兩種形式

1. 空閑分區(qū)表：設(shè)置一張空閑分區(qū)表，用于記錄每個空閑分區(qū)的情況

2. 空閑分區(qū)鏈：實現(xiàn)對空閑分區(qū)的分配和鏈接娃弓，每個分區(qū)的起始部分設(shè)置一些用于控制分區(qū)分配的信息

動態(tài)分區(qū)分配算法

把一個新作業(yè)裝入內(nèi)存庞萍，必須按照一定的算法，從上述兩種數(shù)據(jù)結(jié)構(gòu)中選出一分區(qū)分配給該作業(yè)忘闻，由此钝计，產(chǎn)生了順序式搜索算法和索引式搜索算法

分區(qū)分配的操作

1. 分配內(nèi)存：從數(shù)據(jù)結(jié)構(gòu)中找到所需大小的分區(qū)，劃分給請求者

2. 回收內(nèi)存：進(jìn)程運行完畢后釋放內(nèi)存齐佳，系統(tǒng)根據(jù)回收區(qū)的首地址私恬，從空閑區(qū)鏈表中找到相應(yīng)的插入點，此時可能出現(xiàn)四種情況之一
   2.1 回收區(qū)與插入點的前一個空閑分區(qū)F1相鄰接炼吴，此時應(yīng)將回收區(qū)與插入點的前一分區(qū)合并本鸣，不必為回收分區(qū)分配新表項，而只需修改其前一分區(qū)的大小
   2.2 回收分區(qū)與插入點的后一空閑分區(qū)F2相鄰接硅蹦，此時也可將兩分區(qū)合并荣德，形成新的空閑分區(qū)，但用回收區(qū)的首地址作為新空閑區(qū)的首地址童芹，大小為兩者大小之和
   2.3 回收區(qū)同時與插入點前后兩個分區(qū)鄰接涮瞻，此時將三個分區(qū)合并，使用F1的表項和F1的首地址假褪，取消F2的表項署咽，大小為三者之和
   2.4 回收區(qū)既不與F1鄰接，又不與F2鄰接生音，這時應(yīng)為回收區(qū)單獨建立一個新表項宁否，填寫回收區(qū)的首地址和大小，并根據(jù)其首地址插入到空閑鏈表中的適當(dāng)位置

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

這種算法適用于不太大的系統(tǒng)

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

此算法要求空閑分區(qū)分鏈以地址遞增的次序鏈接缀遍，分配內(nèi)存時慕匠，從鏈?zhǔn)组_始順序查找，直到找到一個大小能滿足要求的空閑分區(qū)為止域醇，再按照作業(yè)的大小台谊，從該分區(qū)中劃出一塊內(nèi)存空間冤寿，分配給請求者，剩下的空閑分區(qū)仍留在空閑鏈中青伤。

若從鏈?zhǔn)组_始直到鏈尾都不能找到一個能滿足要求的分區(qū)督怜，則表明系統(tǒng)中已經(jīng)沒有足夠的內(nèi)存分配給該進(jìn)程，內(nèi)存分配失敗狠角，返回

每次查找都是從低地址部分開始的号杠，無疑會增加查找可用空閑分區(qū)的開銷

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

為避免低地址部分出現(xiàn)很多很小的空閑分區(qū)，以及減少查找可用空閑分區(qū)的開銷丰歌，此算法每次從上次找到的空閑分區(qū)的下一個空閑分區(qū)開始查找姨蟋，直到找到一個能滿足要求的空閑分區(qū)，并采用循環(huán)查找的方式立帖，如果最后一個空閑分區(qū)的大小仍不能滿足要求眼溶，則返回第一個空閑分區(qū)。

減少了查找空閑分區(qū)的開銷晓勇，但這樣會缺乏大的空閑分區(qū)

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

每次為作業(yè)分配內(nèi)存時堂飞，總是把能滿足要求又是最小的空閑分區(qū)分配給作業(yè)，避免大材小用绑咱。為了加速尋找绰筛，該算法要求將所有的空閑分區(qū)按容量從小到大的順序形成一空閑分區(qū)鏈，這樣描融，第一次找到的分區(qū)必然是最佳的铝噩。

但是這樣會在存儲器中留下許多難以利用的碎片

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

與最佳適應(yīng)正好相反，掃描整個鏈表時窿克，總是挑選一個最大的空閑區(qū)骏庸，從中分割一部分存儲空間給作業(yè)使用

優(yōu)點是可以使剩下的空閑分區(qū)不至于太小，產(chǎn)生碎片的可能性最小年叮，對中小作業(yè)有利具被。同時效率很高，該算法要求所有空閑分區(qū)按從大到小排列谋右，查找時只需要看第一個分區(qū)能否滿足作業(yè)要求即可

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

適用于大硬猫、中型系統(tǒng)

快速適應(yīng)算法（QF）

也稱為分類搜索算法补箍，將空閑分區(qū)根據(jù)容量大小進(jìn)行分類改执，對于每一類具有相同容量的所有空閑分區(qū)，單獨設(shè)立一個空閑分區(qū)鏈表

搜索時分兩步坑雅。第一步根據(jù)進(jìn)程長度辈挂，從索引表中去尋找能容納它的最小空閑區(qū)鏈表。第二步是從鏈表中取下第一塊進(jìn)行分配即可裹粤。

進(jìn)行空閑分區(qū)分配時不會對任何分區(qū)產(chǎn)生分割终蒂，能保留大分區(qū)，滿足對大空間的需求，也不會產(chǎn)生內(nèi)存碎片拇泣，查找效率高噪叙。但也有缺點在于為了有效合并分區(qū)，分區(qū)歸還時算法復(fù)雜霉翔，系統(tǒng)開銷較大睁蕾，為進(jìn)程分配一個分區(qū)中或多或少存在浪費，典型的以空間換時間

伙伴系統(tǒng)（BS）

算法規(guī)定不論分區(qū)已分配或空閑债朵，大小均為2的k次冪子眶，系統(tǒng)運行過程中由于不斷劃分形成若干個不連續(xù)的空閑分區(qū)，將這些空閑分區(qū)按分區(qū)大小進(jìn)行分類序芦。對于具有相同大小的所有空閑分區(qū)單獨設(shè)立一個空閑分區(qū)雙向鏈表臭杰，這樣不同大小的空閑分區(qū)形成了k個空閑分區(qū)鏈表

當(dāng)分配內(nèi)存時，會優(yōu)先從需要分配的內(nèi)存塊鏈表上查找空閑內(nèi)存塊谚中，當(dāng)發(fā)現(xiàn)對應(yīng)大小的內(nèi)存塊都已經(jīng)被使用后渴杆，那么會從更大一級的內(nèi)存塊上分配一塊內(nèi)存，并且分成一半給我們使用宪塔，剩余的一半釋放到對應(yīng)大小的內(nèi)存塊鏈表上将塑。比如我們想要分配一個8KB大小的內(nèi)存，但是發(fā)現(xiàn)對應(yīng)大小的內(nèi)存已經(jīng)沒有了蝌麸，那么伙伴系統(tǒng)會從16KB的鏈表中查找一個空閑內(nèi)存塊点寥，分成兩個8KB大小，把其中的一個8KB大小返回給申請者使用来吩，剩下的8KB放到8KB對應(yīng)的內(nèi)存塊鏈表中進(jìn)行管理敢辩。更壞的一種情況是，系統(tǒng)發(fā)現(xiàn)16KB大小的連續(xù)內(nèi)存頁已經(jīng)沒有了弟疆，那么以此會向更高的32KB鏈表中查找戚长，如果找到了空閑內(nèi)存塊，那么就把32KB分成一個16KB和兩個8KB怠苔，16KB的內(nèi)存塊放到16KB的鏈表進(jìn)行管理同廉，兩個8KB的內(nèi)存塊一個返回給申請者，另一個放到8KB大小的鏈表進(jìn)行管理

當(dāng)釋放內(nèi)存時柑司，會掃描對應(yīng)大小的內(nèi)存塊鏈表迫肖，查看是否存在地址能夠連續(xù)在一起的內(nèi)存塊，如果發(fā)現(xiàn)有攒驰，那么就合并兩個內(nèi)存塊放置到更大一級的內(nèi)存塊鏈表上蟆湖，以此類推。比如我們釋放8KB大小的內(nèi)存玻粪，那么會從對應(yīng)的鏈表掃描是否有能夠合并的內(nèi)存塊隅津，如果有另一個8KB大小的內(nèi)存和我們使用的內(nèi)存地址連續(xù)诬垂，那么就合并它們組成一個16KB大小的內(nèi)存塊，然后接著掃描16KB大小的內(nèi)存塊鏈表伦仍，繼續(xù)查找合并的可能结窘，以此類推下去

哈希算法

上面兩種算法都是將空閑分區(qū)根據(jù)分區(qū)大小進(jìn)行分類，對于每一類具有相同大小的空閑分區(qū)單獨設(shè)立一個空閑分區(qū)表充蓝，查找時如果表項比較多會顯著增加時間開銷晦鞋。哈希算法就是利用哈希快速查找的優(yōu)點棺克，以及空閑分區(qū)在可利用空閑區(qū)表中的分布規(guī)律建立哈希函數(shù)悠垛，構(gòu)造一張以空閑分區(qū)大小為關(guān)鍵字的哈希表，該表的每一個表項記錄了一個對應(yīng)的空閑分區(qū)鏈表表頭指針

當(dāng)進(jìn)行空閑分區(qū)分配時根據(jù)所需空閑分區(qū)大小娜谊，通過哈希函數(shù)計算确买，得到在哈希表中的位置，從中得到相應(yīng)的空閑分區(qū)鏈表纱皆，實現(xiàn)最佳分配策略

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

緊湊

將內(nèi)存中所有大作業(yè)進(jìn)行移動湾趾，使得他們?nèi)苦徑樱@種方式叫緊湊派草。但是這種方式帶來的問題就是用戶程序在內(nèi)存中的位置發(fā)生了變化搀缠，為了解決這個問題，下面介紹動態(tài)重定位方法

動態(tài)重定位

地址變換過程是在程序執(zhí)行期間近迁，隨著對每條指令或數(shù)據(jù)的訪問自動進(jìn)行的艺普，稱為動態(tài)重定位。當(dāng)系統(tǒng)對內(nèi)存使用了緊湊鉴竭，而使若干程序從內(nèi)存的某處移到另一處時歧譬，不需要對程序進(jìn)行任何的修改，只要用該程序在內(nèi)存的新起始地址去置換原來的起始地址即可

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

與動態(tài)分區(qū)分配算法基本相同搏存，差別僅在于在這種分配算法中加入了緊湊

4.4 對換

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

把內(nèi)存中暫時不能運行的進(jìn)程或者暫時不用的程序和數(shù)據(jù)換出到外存瑰步，騰出足夠的空間，把已經(jīng)具備運行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)換入內(nèi)存璧眠，提高吞吐量

對換的類型

1. 整體對換
2. 頁面對換

4.5 分頁存儲管理方式

如果允許一個進(jìn)程直接分散的裝入許多不相鄰接的分區(qū)中缩焦，便可充分利用內(nèi)存空間，無須緊湊责静≡模基于這一思想產(chǎn)生了離散的分配方式

1. 分頁存儲管理方式
2. 分段存儲管理方式
3. 段頁式存儲管理方式

4.5.1 分頁存儲管理的基本方法

頁面和物理塊

1. 頁面：將進(jìn)程的邏輯地址空間分成若干頁，并為各頁加以編號泰演。相應(yīng)的呻拌，也把內(nèi)存的物理地址空間分成若干塊，同樣加以編號

2. 頁面大心阑馈：頁面過小可以減少內(nèi)存碎片藐握，有利于內(nèi)存利用率提高，但是另一方面會造成每個進(jìn)程占用較多頁面垃喊，導(dǎo)致進(jìn)程頁表過長猾普，占用內(nèi)存。此外本谜，還會降低換出效率初家。如果頁面過大又會使頁內(nèi)碎片增大，因此頁面大小應(yīng)該選擇適中乌助。且頁面大小應(yīng)該是2的冪

地址結(jié)構(gòu)

包含頁號和位移量

image.png

對某特定機器溜在，其地址結(jié)構(gòu)是一定的。若給定一個邏輯地址空間中地址為A他托，頁面大小為L掖肋，則頁號和頁內(nèi)地址d可按照下式求得

image.png

頁表

在分頁系統(tǒng)中，允許進(jìn)程的各個頁離散地存儲在內(nèi)存地任一物理塊中赏参，為保證進(jìn)程仍然能夠正確地運行志笼，即能在內(nèi)存中找到各個頁面所對應(yīng)地物理塊，系統(tǒng)又為每個進(jìn)程建立了一張頁面印象表把篓，簡稱頁表纫溃，它地作用是實現(xiàn)從頁號到物理塊號的地址映射

4.5.2 地址變換機構(gòu)

將邏輯地址轉(zhuǎn)變?yōu)槲锢淼刂?/p>

基本地址變換（直接地址映像）

借助頁表、頁表寄存器完成作業(yè)邏輯地址（虛地址）到內(nèi)存物理地址的變換

具有快表的地址變換

增設(shè)若干具有并行查詢能力的特殊高速緩沖寄存器（聯(lián)想寄存器\快表）韧掩，保存當(dāng)前執(zhí)行進(jìn)程的部分\全部頁表表目紊浩，

具體流程為：查快表，找到則訪問內(nèi)存直接得物理地址疗锐，沒找到則先訪問內(nèi)存查頁表再訪問內(nèi)存查到物理地址

分頁基本地址變換示例

image.png

具有快表的地址變換示例

image.png

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

指的是從進(jìn)程發(fā)出指定邏輯地址的訪問請求郎楼，經(jīng)過地址變換，到在內(nèi)存中找到對應(yīng)的實際物理地址單元并取出數(shù)據(jù)窒悔，所需要花費的總時間

4.5.4 兩級和多級頁表

兩級頁表

兩級頁表采用離散分配的方式呜袁，將頁表進(jìn)行分頁，然后將各個頁面分別存儲在不同的物理塊中以解決連續(xù)存儲的問題简珠。一級頁表被分成了若干個頁面分別存儲在不同的物理塊中阶界，另外一級頁表又叫做外層頁表，它是用來存儲剛剛所劃分的各個頁面的首地址聋庵，通過它我們就可以知道各個頁面所處的位置膘融。

以32位邏輯地址空間的分頁系統(tǒng)為例，如果采用一級頁表祭玉，那么頁表所占用的內(nèi)存空間是1MB氧映，而且必須是連續(xù)的。現(xiàn)在我們將頁表等分成1024份脱货，即產(chǎn)生了1024個頁面岛都，并且每個頁面有1024個表項（每個表項1B律姨，即每個頁面1KB），存儲的是頁號與物理塊號的映射關(guān)系臼疫；然后我們建立外層頁表择份，由于有1024個頁面精居，所以外層頁表有1024個表項（每個表項1B炬灭，外層頁表1KB），存儲的是各個頁面的首地址刽虹。這樣我們就實現(xiàn)了一個兩級頁表鸽斟，由于兩級頁表采用了離散分配的方式拔创，外層頁表和每個表項所對應(yīng)的頁面分別存儲在不同的物理塊中，解決了需要連續(xù)存儲的問題富蓄。

多級頁表

32位機上采用兩級頁表結(jié)構(gòu)是合適的剩燥，64位機上不一定，因此推出多級頁表

4.6 分段存儲管理方式

4.6.1 分段存儲管理方式的引入

方便編程

通常用戶把自己的作業(yè)按照邏輯關(guān)系劃分為若干段格粪，每段都從0開始編址躏吊，并且有自己的名字和長度。因此我們需要訪問的邏輯地址是由段名和段內(nèi)偏移量決定的帐萎，不僅使程序員方便編程比伏，也使程序非常直觀

信息共享

為該被共享過程建立一個獨立的段，極大的簡化了共享的實現(xiàn)

信息保護(hù)

分頁難以對頁面實行統(tǒng)一保護(hù)疆导，分段可以更有效的實現(xiàn)對信息的保護(hù)

動態(tài)增長

數(shù)據(jù)量增加導(dǎo)致數(shù)據(jù)段動態(tài)增長赁项，分段存儲可以較好的解決該問題

動態(tài)鏈接

動態(tài)鏈接以目標(biāo)程序作為鏈接的基本單位，因此分段存儲管理方式適合動態(tài)鏈接

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

分段

作業(yè)地址空間被劃分為若干段澈段，每段定義了一組邏輯信息悠菜，分段地址中的地址具有如下信息

image.png

段表

段表記錄了段與內(nèi)存位置的對應(yīng)關(guān)系，保存在內(nèi)存中败富，基址及長度由段表寄存器給出悔醋。

image.png

地址變換機構(gòu)

image.png

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

1. 頁是信息的物理單位

2. 頁的大小固定且由系統(tǒng)決定

3. 分頁的用戶程序地址空間是一維的

4.6.3 信息共享

允許若干進(jìn)程共享一個或多個分段，且對段的保護(hù)也十分簡單易行

4.6.4 段頁式存儲管理方式

將用戶程序分成若干段兽叮，并為每個段賦予一個段名芬骄，把每個段分成若干頁，地址結(jié)構(gòu)包括段號鹦聪、段內(nèi)頁號和頁內(nèi)地址三部分

image.png

地址變換過程

image.png

歡迎指正账阻。