操作系統(tǒng)目錄

• 1、什么是操作系統(tǒng)
• 2、計(jì)算機(jī)操作系統(tǒng)的基本特征
• • 2.1、并發(fā)
  • 2.2、共享
  • 2.3、虛擬
  • 2.4、異步
• 3、操作系統(tǒng)的發(fā)展
• 4、OS的運(yùn)行機(jī)制和體系結(jié)構(gòu)
• • 4.1、運(yùn)行機(jī)制
  • • 4.1.1、兩種指令
    • 4.1.2、兩種狀態(tài)
    • 4.1.3、兩種程序
  • 4.2、體系結(jié)構(gòu)
• 5、中斷和異常
• • 5.1、中斷機(jī)制的由來(lái)
  • 5.2、中斷機(jī)制的流程
  • 5.3、中斷機(jī)制的重點(diǎn)
  • 5.4、中斷的分類(lèi)
• 6、系統(tǒng)調(diào)用
• 7、進(jìn)程
• • 7.1、進(jìn)程的定義和組成
  • 7.2、進(jìn)程的組織方式
  • 7.3、進(jìn)程的特征
  • 7.4、進(jìn)程的狀態(tài)
  • 7.5、進(jìn)程狀態(tài)的切換
  • 7.6、進(jìn)程的控制
• 8、線程
• • 8.1、線程的簡(jiǎn)介和引入后發(fā)生的變化
  • 8.2、線程的屬性
  • 8.3、線程的實(shí)現(xiàn)方式和多線程模型
• 9、處理機(jī)調(diào)度
• • 9.1、進(jìn)程調(diào)度方式
  • 9.2、進(jìn)程調(diào)度時(shí)機(jī)
  • 9.3、調(diào)度算法的評(píng)價(jià)指標(biāo)
  • 9.4、調(diào)度算法
  • • 9.4.1、先來(lái)先服務(wù)
    • 9.4.2、短作業(yè)優(yōu)先
    • 9.4.3、高響應(yīng)比優(yōu)先
    • 9.4.4、時(shí)間片輪轉(zhuǎn)調(diào)度算法
    • 9.4.5、優(yōu)先級(jí)調(diào)度算法
    • 9.4.6、多級(jí)反饋調(diào)度算法
  • 9.4、進(jìn)程同步和進(jìn)程異步
  • • 9.4.1、進(jìn)程同步
    • 9.4.2、進(jìn)程互斥
  • 9.5、進(jìn)程互斥的軟件實(shí)現(xiàn)方式
  • 9.6、進(jìn)程互斥的硬件實(shí)現(xiàn)方式
• 10、信號(hào)量
• • 10.1、信號(hào)量機(jī)制
  • • 10.1.1、整型信號(hào)量
    • 10.1.2、記錄型信號(hào)量
    • 10.1.3、信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程互斥
    • 10.1.3、信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程同步
  • 10.2、生產(chǎn)者消費(fèi)者問(wèn)題
• 11、死鎖
• • 11.1、產(chǎn)生死鎖的原因和必要條件
• 12、存儲(chǔ)器管理
• • 12.1、多級(jí)存儲(chǔ)器結(jié)構(gòu)
  • 12.2、程序的裝入和鏈接
  • • 12.2.1、程序的裝入
    • 12.2.2、程序的鏈接
  • 12.3、連續(xù)分配方式
  • • 12.3.1、單一連續(xù)分配
    • 12.3.2、固定分區(qū)分配
    • 12.3.3、動(dòng)態(tài)分區(qū)分配

---

1、什么是操作系統(tǒng)

計(jì)算機(jī)操作系統(tǒng)是管理計(jì)算機(jī)硬件與軟件資源的計(jì)算機(jī)程序

---

????????????????????????????????????????????????

2、計(jì)算機(jī)操作系統(tǒng)的基本特征

2.1、并發(fā)

容易混淆的概念：并發(fā)和并行

并發(fā)：多個(gè)任務(wù)在同一時(shí)間間隔內(nèi)發(fā)生，注意在宏觀上是同時(shí)發(fā)生，但在微觀上實(shí)際是交替發(fā)生的

并行：多個(gè)任務(wù)在同一時(shí)刻同時(shí)發(fā)生

2.2、共享

系統(tǒng)中的資源可以被多個(gè)并發(fā)執(zhí)行的進(jìn)程一起使用

互斥共享方式：某一個(gè)時(shí)間段內(nèi)，只允許一個(gè)進(jìn)程對(duì)該資源進(jìn)行訪問(wèn)（例如攝像頭）
同時(shí)共享方式：某一個(gè)時(shí)間段內(nèi)，允許多個(gè)進(jìn)程對(duì)該資源進(jìn)行訪問(wèn)（例如磁盤(pán)）
注意“同時(shí)”其實(shí)本質(zhì)上是在該時(shí)間段內(nèi)，多個(gè)進(jìn)程對(duì)資源交替訪問(wèn)（即分時(shí)共享）

2.3、虛擬

什么是虛擬：虛擬就是將一個(gè)物理實(shí)體變?yōu)槿舾蓚€(gè)邏輯上的對(duì)應(yīng)物

怎么理解呢？

虛擬存儲(chǔ)器技術(shù)：虛擬存儲(chǔ)器技術(shù)用來(lái)解決內(nèi)存不夠的問(wèn)題（空分復(fù)用技術(shù)）
比如我電腦上一共4GB的運(yùn)行內(nèi)存，IDEA占用了2個(gè)G、py占用2個(gè)G…且不說(shuō)系統(tǒng)占用的內(nèi)存，加起來(lái)肯定超過(guò)了4個(gè)G；所以這就用到了虛擬存儲(chǔ)器技術(shù)(此處不做過(guò)多深入了解）

虛擬處理器技術(shù)：CPU的虛擬化技術(shù)可以使單CPU模擬多CPU并行（時(shí)分復(fù)用技術(shù)）
微觀上是處理機(jī)在各個(gè)微小的時(shí)間內(nèi)交替的為各個(gè)程序服務(wù)（時(shí)間的微化處理）；比如我能夠同時(shí)打開(kāi)idea、chrome、vx等等

如果丟失了并發(fā)，那么虛擬就無(wú)任何意義（因?yàn)槿绻麤](méi)有并發(fā)，沒(méi)次只運(yùn)行一個(gè)程序即可）

2.4、異步

在多道程序的環(huán)境下，系統(tǒng)是允許多個(gè)程序并發(fā)執(zhí)行的，由于資源的有限性，不可能所有的程序都能一貫到底的

比如進(jìn)程A和進(jìn)程B都要使用打印機(jī)，當(dāng)進(jìn)程A先獲得打印機(jī)的使用權(quán)時(shí)，那么進(jìn)程B只能等待；只有當(dāng)進(jìn)程A歸還打印機(jī)，進(jìn)程B才能繼續(xù)執(zhí)行。就像這樣程序中間可能有間斷，受到其他程序的影響，不知道何時(shí)執(zhí)行結(jié)束，這就是程序的異步性。

---

????????????????????????????????????????????????

3、操作系統(tǒng)的發(fā)展

1、手工操作階段

人機(jī)速度不匹配，資源利用極低

2、批道處理階段

Ⅰ、單批道處理系統(tǒng)：
引入脫機(jī)輸入\輸出技術(shù)（磁帶完成），緩解人機(jī)速度不匹配問(wèn)題，提高了資源的利用率；但只允許一個(gè)程序運(yùn)行，cpu大部分時(shí)間仍在等待IO，資源利用率依舊很低

Ⅱ、多批道處理系統(tǒng)：
每次向內(nèi)存中輸入多道程序，并發(fā)執(zhí)行
提高了資源利用率，但無(wú)人機(jī)交互功能）

3、分時(shí)操作系統(tǒng)

增加了人家交互功能，以時(shí)間片為單位為各個(gè)人作業(yè)服務(wù)
缺點(diǎn)是不能及時(shí)處理緊急任務(wù)

4、實(shí)時(shí)操作系統(tǒng)

能夠優(yōu)先響應(yīng)一些緊急任務(wù)，不需要時(shí)間片排隊(duì)

硬實(shí)時(shí)操作系統(tǒng)：必須在嚴(yán)格的時(shí)間內(nèi)完成處理（防空系統(tǒng)）
軟實(shí)時(shí)操作系統(tǒng)：可以偶爾違反時(shí)間規(guī)定

5、網(wǎng)絡(luò)操作系統(tǒng)

6、分布式操作系統(tǒng)

7、個(gè)人操作系統(tǒng)

---

????????????????????????????????????????????????

4、OS的運(yùn)行機(jī)制和體系結(jié)構(gòu)

4.1、運(yùn)行機(jī)制

4.1.1、兩種指令

指令就是cpu能夠執(zhí)行的最基本的單位，一行代碼可能轉(zhuǎn)換多條指令

那么cpu是怎么判斷執(zhí)行哪條指令呢？請(qǐng)看4.1.2

4.1.2、兩種狀態(tài)

處于用戶(hù)態(tài)時(shí)，cpu只能執(zhí)行非特權(quán)指令
處于和心態(tài)時(shí)，cpu可以執(zhí)行特權(quán)指令和非特權(quán)指令

使用程序狀態(tài)寄存器來(lái)標(biāo)識(shí)當(dāng)前處理器處于什么狀態(tài)

4.1.3、兩種程序

4.2、體系結(jié)構(gòu)

大內(nèi)核：將系統(tǒng)的主要功能作為內(nèi)核，運(yùn)行在核心態(tài)
優(yōu)點(diǎn)：高性能
缺點(diǎn)：代碼里龐大、結(jié)構(gòu)混亂、難以維護(hù)

微內(nèi)核：只把最基本的留在內(nèi)核
優(yōu)點(diǎn)：代碼量小、結(jié)構(gòu)清晰、容易維護(hù)
缺點(diǎn)：需要在用戶(hù)態(tài)和核心態(tài)之間來(lái)回切換，性能低

????????????????????????????????????????????????

5、中斷和異常

5.1、中斷機(jī)制的由來(lái)

由于串行效率極低，所有引入了中斷機(jī)制，從而實(shí)現(xiàn)了并發(fā)執(zhí)行
一旦發(fā)送中斷，就意味著需要操作系統(tǒng)的介入；因?yàn)橛脩?hù)程序是不允許直接執(zhí)行特權(quán)指令的。

5.2、中斷機(jī)制的流程

我們知道在并發(fā)執(zhí)行的過(guò)程中，是以時(shí)間片輪轉(zhuǎn)法來(lái)實(shí)現(xiàn)的
比如2個(gè)程序一同執(zhí)行

1、當(dāng)程序1在用戶(hù)態(tài)執(zhí)行完一個(gè)時(shí)間片時(shí)，cpu就會(huì)收到計(jì)時(shí)器發(fā)出的中斷信號(hào)，然后cpu就會(huì)切換到核心態(tài)將cpu的使用權(quán)限交給操作系統(tǒng)管理

2、此時(shí)操作系統(tǒng)內(nèi)核開(kāi)始對(duì)中斷信號(hào)進(jìn)行處理，發(fā)現(xiàn)是過(guò)了一個(gè)時(shí)間片，然后操作系統(tǒng)會(huì)把cpu的使用權(quán)交還給用戶(hù)進(jìn)程，然后程序2就會(huì)在用戶(hù)態(tài)下執(zhí)行

3、程序2執(zhí)行過(guò)程序可能需要進(jìn)程輸出操作，但是輸入\輸出屬于特權(quán)指令，程序是沒(méi)法進(jìn)行直接使用的；所以需要通過(guò)內(nèi)中斷的方式請(qǐng)求操作系統(tǒng)完成輸出工作；此時(shí)和第一步一樣-》cpu切換到和心態(tài)-》將使用權(quán)交給操作系統(tǒng)

5.3、中斷機(jī)制的重點(diǎn)

1、當(dāng)中斷發(fā)生時(shí)，cpu立即進(jìn)入核心態(tài)
2、當(dāng)中斷機(jī)制發(fā)生后，當(dāng)前進(jìn)程會(huì)進(jìn)入暫停狀態(tài)，交由操作系統(tǒng)內(nèi)核對(duì)中斷信號(hào)進(jìn)行處理
3、不同的中斷信號(hào)，會(huì)進(jìn)行不同的中斷處理

發(fā)生了中斷，意味著需要操作系統(tǒng)的介入管理；而管理工作一般要包含輸入輸出、進(jìn)程切換等特權(quán)指令；因此cpu需要從用戶(hù)態(tài)切換為核心態(tài)，使得操作系統(tǒng)獲得了計(jì)算機(jī)的控制權(quán)，有了中斷機(jī)制才能實(shí)現(xiàn)程序的并發(fā)執(zhí)行

用戶(hù)態(tài)-》核心態(tài) ：中斷是唯一途徑
核心態(tài)-》用戶(hù)態(tài)：只需通過(guò)一個(gè)設(shè)置程序特權(quán)字的標(biāo)識(shí)為用戶(hù)態(tài)即可

5.4、中斷的分類(lèi)

(軟件中斷就是比如1/0，外設(shè)就是比如IO完成就會(huì)發(fā)送中斷信號(hào)）

核心：內(nèi)中斷和外中斷怎么進(jìn)行區(qū)分

內(nèi)中斷是發(fā)生在cpu內(nèi)部，是當(dāng)前執(zhí)行的指令有關(guān)
外中斷是發(fā)生在cpu外部，與當(dāng)前執(zhí)行的指令無(wú)關(guān)

外中斷的處理流程

1、執(zhí)行完每個(gè)指令之后，cpu都會(huì)檢查是否有外中斷信號(hào)
2、如何有則保護(hù)中斷進(jìn)程的環(huán)境（程序狀態(tài)字、寄存器、計(jì)數(shù)器等）
3、根據(jù)中斷信號(hào)轉(zhuǎn)入執(zhí)行相應(yīng)的中斷處理程序
4、恢復(fù)原進(jìn)程的環(huán)境

????????????????????????????????????????????????

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

什么是系統(tǒng)調(diào)用？

系統(tǒng)調(diào)用是操作系統(tǒng)提供給應(yīng)用程序的接口

系統(tǒng)調(diào)用的作用是什么？

系統(tǒng)中的各種共享資源由操作系統(tǒng)統(tǒng)一掌管，所以在應(yīng)用程序當(dāng)中，所有與資源相關(guān)的操作都必須以系統(tǒng)調(diào)用的方式請(qǐng)求操作系統(tǒng)進(jìn)行處理；這樣可以保證系統(tǒng)的安全性和穩(wěn)定性。

由于需要一些特權(quán)指令，所以系統(tǒng)調(diào)用是在核心態(tài)下完成的

比如我們高級(jí)語(yǔ)言里面的Read(“a.txt”）函數(shù)，這個(gè)Read底層封裝了系統(tǒng)調(diào)用復(fù)雜的實(shí)現(xiàn)細(xì)節(jié)

????????????????????????????????????????????????

7、進(jìn)程

7.1、進(jìn)程的定義和組成

1.為什么會(huì)產(chǎn)生進(jìn)程?

1.1.最初的計(jì)算機(jī)每次只能執(zhí)行一個(gè)指令，這樣的效率非常低下
1.2.后來(lái)出現(xiàn)了批處理系統(tǒng)，程序員可以將一串指令一次性交給計(jì)算機(jī)，這樣雖然相比最初的計(jì)算機(jī)提高了效率，但是內(nèi)存中始終只允許一個(gè)程序；
1.3.所以進(jìn)程的概念就誕生了

2.進(jìn)程是什么?

進(jìn)程是應(yīng)用程序在內(nèi)存中分配的空間，各個(gè)進(jìn)程互不干擾，每個(gè)進(jìn)程保持著程序每一時(shí)刻的運(yùn)行狀態(tài)

特點(diǎn)：此時(shí)cpu采用時(shí)間片輪轉(zhuǎn)的方式運(yùn)行進(jìn)程

操作系統(tǒng)在每一個(gè)程序運(yùn)行之前，都會(huì)在內(nèi)存中為程序配置一個(gè)數(shù)據(jù)結(jié)構(gòu)，稱(chēng)之為進(jìn)程控制塊（PCB），用來(lái)描述進(jìn)程的各種信息

另外進(jìn)程實(shí)體(進(jìn)程映像)包含數(shù)據(jù)段、程序段、PCB組成。（操作系統(tǒng)相關(guān)的數(shù)據(jù)都存放在PCB中，程序運(yùn)行的代碼存放在程序段中，程序運(yùn)行所需的相關(guān)數(shù)據(jù)存放在數(shù)據(jù)段中）

7.2、進(jìn)程的組織方式

鏈接方式和索引方式很類(lèi)似，只不過(guò)索引方式是使用了一個(gè)中間表來(lái)實(shí)現(xiàn)；而鏈接方式就相當(dāng)于鏈表中的頭節(jié)點(diǎn)

7.3、進(jìn)程的特征

7.4、進(jìn)程的狀態(tài)

在計(jì)算機(jī)運(yùn)行的過(guò)程中，可能有多個(gè)進(jìn)程運(yùn)行；此時(shí)有的進(jìn)程或許正在被cpu運(yùn)行，有的或許在等待；所以說(shuō)進(jìn)程可能處于不同的狀態(tài)。

注意
在單核處理機(jī)中，每一個(gè)時(shí)刻最多有一個(gè)進(jìn)程正在運(yùn)行；在多核處理機(jī)中，每一個(gè)時(shí)刻可以有多個(gè)進(jìn)程正在運(yùn)行。

其實(shí)還有另外兩種狀態(tài)

7.5、進(jìn)程狀態(tài)的切換

7.6、進(jìn)程的控制

進(jìn)程控制簡(jiǎn)單了說(shuō)就是完成進(jìn)程狀態(tài)之間的轉(zhuǎn)換

使用原語(yǔ)完成進(jìn)程控制，（原語(yǔ)就是必須一氣呵成，中間不允許進(jìn)行中斷；比如如果進(jìn)程在轉(zhuǎn)換過(guò)程中由于中斷沒(méi)有進(jìn)入其他相應(yīng)的隊(duì)列就會(huì)造成難以想象的后果）

原語(yǔ)采用“開(kāi)中斷”和“關(guān)中斷”兩個(gè)指令完成進(jìn)程控制
進(jìn)程狀態(tài)轉(zhuǎn)換過(guò)程中，首先會(huì)執(zhí)行關(guān)中斷，如果在途中遇到中斷指令，則會(huì)被忽略；直到遇到開(kāi)中斷結(jié)束。

????????????????????????????????????????????????

8、線程

8.1、線程的簡(jiǎn)介和引入后發(fā)生的變化

概述

線程是輕量級(jí)的進(jìn)程，是cpu資源調(diào)度的基本單位

引入線程前后的變化

資源分配、調(diào)度：引入線程前，進(jìn)程是資源分配、調(diào)度的基本單位；引入線程后，進(jìn)程是資源分配的基本單位，線程是調(diào)度的基本單位
并發(fā)性：引入線程前，只能在進(jìn)程間并發(fā)；引入線程后，線程間也能進(jìn)行并發(fā)
系統(tǒng)開(kāi)銷(xiāo)：引入線程前，進(jìn)程之間的切換開(kāi)銷(xiāo)大；引入線程后線程在進(jìn)程內(nèi)部進(jìn)行切換的開(kāi)銷(xiāo)小

8.2、線程的屬性

線程是cpu調(diào)度的基本單位
多核計(jì)算機(jī)中，各個(gè)線程可以占用不同的cpu
每個(gè)線程都有一個(gè)線程ID、線程控制塊（TCB）
線程也有就緒、運(yùn)行、阻塞三種基本狀態(tài)
線程幾乎不擁有系統(tǒng)資源
同一進(jìn)程的不同線程共享進(jìn)程資源

8.3、線程的實(shí)現(xiàn)方式和多線程模型

實(shí)現(xiàn)方式

在用戶(hù)級(jí)線程和內(nèi)核級(jí)線程中，可以采用組合的方式，將n個(gè)用戶(hù)級(jí)線程映射到m個(gè)內(nèi)核級(jí)線程（n>=m)

注意：內(nèi)核級(jí)線程才是處理機(jī)分配的基本單位

多線程模型

多對(duì)一
一對(duì)一
多對(duì)多

????????????????????????????????????????????????

9、處理機(jī)調(diào)度

簡(jiǎn)介：從就緒隊(duì)列中按照一定的算法選擇一個(gè)進(jìn)程并將處理機(jī)分配給它運(yùn)行，以實(shí)現(xiàn)進(jìn)程的并發(fā)執(zhí)行

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

三種調(diào)度方式高級(jí)調(diào)度按一定的原則從外存上處于后備隊(duì)列的作業(yè)中挑選一個(gè)作業(yè)，給他們分配資源，建立相應(yīng)的進(jìn)程，使得它們獲得處理機(jī)的權(quán)限中級(jí)調(diào)度利用虛擬存儲(chǔ)器技術(shù)，將暫時(shí)不能運(yùn)行的進(jìn)程調(diào)到外存準(zhǔn)備。等它具備了運(yùn)行條件且內(nèi)存空閑時(shí)，再重新調(diào)入內(nèi)存，外存到內(nèi)存（創(chuàng)建態(tài)-》就緒態(tài)暫時(shí)調(diào)到外存的進(jìn)程狀態(tài)處于掛起狀態(tài)。PCB不會(huì)被調(diào)入外存，PCB記錄了進(jìn)程數(shù)據(jù)在外存中存放的位置等信息。被掛起的進(jìn)程的PCB被放到掛起隊(duì)列中，從外存到內(nèi)存（掛起態(tài)-》阻塞態(tài)）低級(jí)調(diào)度按照某種策略從就緒隊(duì)列種選取一個(gè)進(jìn)程，將處理機(jī)分配給它，從內(nèi)存到cpu

9.2、進(jìn)程調(diào)度時(shí)機(jī)

臨界區(qū)是？訪問(wèn)臨界資源的那段代碼
臨界資源是？一段時(shí)間內(nèi)只允許一個(gè)進(jìn)程訪問(wèn)，各進(jìn)程互斥訪問(wèn)

當(dāng)進(jìn)程訪問(wèn)普通臨界資源時(shí)是可以進(jìn)行調(diào)度與切換的

9.3、調(diào)度算法的評(píng)價(jià)指標(biāo)

1、cpu利用率：作業(yè)在外存后備隊(duì)列的時(shí)間（高級(jí)調(diào)度）
2、系統(tǒng)吞吐量：進(jìn)程在就緒隊(duì)列的時(shí)間（低級(jí)調(diào)度）
3、周轉(zhuǎn)時(shí)間：進(jìn)程執(zhí)行的時(shí)間、等待IO的時(shí)間
4、等待時(shí)間：

公式：帶權(quán)周轉(zhuǎn)時(shí)間=作業(yè)周轉(zhuǎn)時(shí)間/作業(yè)實(shí)際的運(yùn)行的時(shí)間 =（作業(yè)完成時(shí)間-作業(yè)提交時(shí)間）/作業(yè)實(shí)際運(yùn)行的時(shí)間

9.4、調(diào)度算法

9.4.1、先來(lái)先服務(wù)

算法思想：從公屏上的角度考慮
算法規(guī)則：按照作業(yè)/進(jìn)程先到達(dá)的先后順序進(jìn)行服務(wù)
作業(yè)/進(jìn)程調(diào)度：用于作業(yè)調(diào)度時(shí)，先考慮哪個(gè)作業(yè)進(jìn)入后備隊(duì)列；用于進(jìn)程調(diào)度時(shí)，先考慮哪個(gè)進(jìn)程先到達(dá)就緒隊(duì)列
是否可搶占：非搶占式算法
優(yōu)點(diǎn)：公平
缺點(diǎn)：對(duì)短作業(yè)不利

模擬FCFS調(diào)度算法(先來(lái)先服務(wù)）沒(méi)錯(cuò)，是篇好文章！：https://blog.csdn.net/Kevinnsm/article/details/115013353

9.4.2、短作業(yè)優(yōu)先

算法思想：追求最少的平均等待時(shí)間
算法規(guī)則：最短的作業(yè)/進(jìn)程優(yōu)先得到服務(wù)（前提的進(jìn)程已經(jīng)到達(dá)）
作業(yè)/進(jìn)程調(diào)度：都可以
是否可搶占：SJF和SPF是非搶占式算法(SRTN為搶占式算法-時(shí)間最短）
優(yōu)點(diǎn)：最短的平均等待時(shí)間
缺點(diǎn)：對(duì)長(zhǎng)作業(yè)不利
如果是一直有短作業(yè)，就會(huì)造成長(zhǎng)作業(yè)一直等待

短作業(yè)最短時(shí)間優(yōu)先原則（SRTN）為搶占式的，平均等待時(shí)間最短

9.4.3、高響應(yīng)比優(yōu)先

算法思想：綜合考慮作業(yè)/進(jìn)程的等待時(shí)間和要求服務(wù)的時(shí)間
算法規(guī)則：每次調(diào)度前計(jì)算每個(gè)作業(yè)的響應(yīng)比，選擇響應(yīng)比最高的作業(yè)服務(wù)
是否搶占：否（只有當(dāng)前作業(yè)主動(dòng)放棄處理機(jī)才會(huì)進(jìn)行調(diào)度）
優(yōu)點(diǎn)：綜合比較好

高響應(yīng)比=（等待時(shí)間+服務(wù)時(shí)間)/服務(wù)時(shí)間

9.4.4、時(shí)間片輪轉(zhuǎn)調(diào)度算法

1、算法思想：處理機(jī)輪流的為每個(gè)進(jìn)程服務(wù)，每個(gè)進(jìn)程在一定時(shí)間內(nèi)都可以得到響應(yīng)
2、算法規(guī)則：按照各個(gè)進(jìn)程到達(dá)就緒隊(duì)列的順序，輪流讓每個(gè)進(jìn)程執(zhí)行一個(gè)時(shí)間片(如100ms)，如果說(shuō)某個(gè)進(jìn)程在這個(gè)時(shí)間內(nèi)沒(méi)有執(zhí)行完，則會(huì)被剝奪處理機(jī)，放到就緒隊(duì)列進(jìn)行等待
3、是否用于作業(yè)/進(jìn)程調(diào)度：用于進(jìn)程調(diào)度，因?yàn)橹挥挟?dāng)作業(yè)放到內(nèi)存建立了相應(yīng)的進(jìn)程才能被分配時(shí)間片
4、是否搶占：屬于搶占式算法，當(dāng)進(jìn)程沒(méi)執(zhí)行完也會(huì)被剝奪處理機(jī)(由時(shí)鐘裝置發(fā)出時(shí)鐘中斷通知時(shí)間已到）
5、優(yōu)點(diǎn)：公平、響應(yīng)快，適用于分時(shí)操作系統(tǒng)
6、缺點(diǎn)：進(jìn)程頻繁切換需要一定的開(kāi)銷(xiāo)，另外不能區(qū)分任務(wù)的緊急程度
7、是否會(huì)導(dǎo)致饑餓：不會(huì)導(dǎo)致饑餓
注意事項(xiàng)（時(shí)間片過(guò)大或過(guò)小會(huì)有什么影響?)

如果時(shí)間片過(guò)大，每個(gè)進(jìn)程都有可能在一個(gè)時(shí)間片內(nèi)執(zhí)行完畢，那么該算法就會(huì)退回到先來(lái)先服務(wù)算法，會(huì)增大系統(tǒng)響應(yīng)時(shí)間，所以時(shí)間片不能過(guò)大

如果時(shí)間片過(guò)小，進(jìn)程之間就會(huì)頻繁的進(jìn)行切換，浪費(fèi)大量的時(shí)間，進(jìn)程處理的時(shí)間比例就會(huì)下降，所以時(shí)間片不能過(guò)小

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

1、算法思想：根據(jù)任務(wù)的緊急程序來(lái)決定處理順序（用于實(shí)時(shí)操作系統(tǒng)）
2、算法規(guī)則：每個(gè)作業(yè)/進(jìn)程都有優(yōu)先級(jí)，調(diào)度時(shí)選擇優(yōu)先級(jí)高的作業(yè)/進(jìn)程
3、用于作業(yè)/進(jìn)程調(diào)度：既可用于進(jìn)程調(diào)度，又可以用于作業(yè)調(diào)度
4、是否搶占式：既有搶占式又有非搶占式
5、優(yōu)點(diǎn)：區(qū)分任務(wù)緊急程度，常用于實(shí)時(shí)操作系統(tǒng)；可以動(dòng)態(tài)的調(diào)整對(duì)各個(gè)作業(yè)/進(jìn)程的偏好程度
6、缺點(diǎn)：若有源源不斷地優(yōu)先級(jí)進(jìn)程進(jìn)來(lái)，有可能會(huì)導(dǎo)致優(yōu)先級(jí)較低地進(jìn)程饑餓
7、是否導(dǎo)致饑餓：有可能導(dǎo)致饑餓

9.4.6、多級(jí)反饋調(diào)度算法

1、算法思想：對(duì)上面的五種調(diào)度算法進(jìn)行折中
2、算法規(guī)則：設(shè)置多級(jí)就緒隊(duì)列，各級(jí)隊(duì)列優(yōu)先級(jí)從高到低，時(shí)間片從小到大
3、用于作業(yè)/進(jìn)程調(diào)度：用于進(jìn)程調(diào)度
4、是否搶占式：搶占式算法
5、優(yōu)點(diǎn)：對(duì)各個(gè)進(jìn)程公平（FCFS)，每個(gè)新到達(dá)的進(jìn)程都能被很快響應(yīng)(RR)，短進(jìn)程只需要很少的時(shí)間就能夠完成(SPF)，可靈活調(diào)整各個(gè)對(duì)進(jìn)程的偏好程度
6、是否導(dǎo)致饑餓：會(huì)

9.4、進(jìn)程同步和進(jìn)程異步

9.4.1、進(jìn)程同步

進(jìn)程具有異步性的特征，并發(fā)的進(jìn)程總是以各自獨(dú)立、不可預(yù)知的速度向前推進(jìn)。

比如管道通信：寫(xiě)的一端向管道寫(xiě)入數(shù)據(jù)，讀的一段從管道讀取數(shù)據(jù)。因此寫(xiě)進(jìn)程必須在讀進(jìn)程之前執(zhí)行，否者就會(huì)造成阻塞（因此推進(jìn)順序必須是寫(xiě)順序->讀順序）

9.4.2、進(jìn)程互斥

進(jìn)程在并發(fā)執(zhí)行的過(guò)程中，不可避免的需要共享一些資源(比如攝像頭、打印機(jī))

在某一個(gè)時(shí)間段內(nèi)，只允許一個(gè)進(jìn)程進(jìn)行訪問(wèn)的資源稱(chēng)為臨界資源

實(shí)現(xiàn)進(jìn)程互斥需要遵循以下幾個(gè)條件

1、空閑讓進(jìn)
2、忙則等待
3、有限等待
4、讓權(quán)等待

9.5、進(jìn)程互斥的軟件實(shí)現(xiàn)方式

1、單標(biāo)志法
2、雙標(biāo)志位先檢查法
3、雙標(biāo)志位后檢查法
4、perterson算法

9.6、進(jìn)程互斥的硬件實(shí)現(xiàn)方式

1、中斷屏蔽：利用開(kāi)中斷/關(guān)中斷指令完成（一旦某個(gè)進(jìn)程執(zhí)行了關(guān)中斷后就不允許其他進(jìn)程進(jìn)行中斷，也就不可能會(huì)發(fā)生進(jìn)程切換；然后就可以獨(dú)自的訪問(wèn)臨界區(qū)，直到執(zhí)行開(kāi)中斷之后。其他進(jìn)程才能訪問(wèn)臨界資源）
…
關(guān)中斷
臨界資源
開(kāi)中斷
…
優(yōu)點(diǎn)：簡(jiǎn)單、高效
缺點(diǎn)：不適用于多處理機(jī)，因?yàn)橛锌赡芏鄠€(gè)處理機(jī)上的某個(gè)進(jìn)程都要訪問(wèn)臨界資源，那么由于每個(gè)處理機(jī)都可以執(zhí)行中斷，所以會(huì)出現(xiàn)多個(gè)進(jìn)程同時(shí)訪問(wèn)臨界資源的情況；然后開(kāi)中斷/關(guān)中斷屬于特殊指令，一般用于內(nèi)核級(jí)進(jìn)程

2、TS指令：TSL指令是用硬件實(shí)現(xiàn)的，不允許被中斷

3、swap指令

10、信號(hào)量

10.1、信號(hào)量機(jī)制

10.1.1、整型信號(hào)量

可以使用信號(hào)量來(lái)表示系統(tǒng)中某個(gè)資源的數(shù)量，通常使用原語(yǔ)中的wait和signal來(lái)實(shí)現(xiàn)

#如何使用信號(hào)量來(lái)定義系統(tǒng)中的資源呢？

1.初始化
2.P操作
3.V操作

初始化：

int S = 1 //（假設(shè)初始化打印機(jī)的數(shù)量為1）

P操作：

void wait(S) {while(S<=0);S=S-1; }

V操作

void signal(S){S=S+1 }

…
P操作
使用臨界資源
V操作
…

由于while(S<=0)循環(huán)，如果一旦資源不夠用，那么將要使用該資源的進(jìn)程就會(huì)一直處于忙等的狀態(tài)

10.1.2、記錄型信號(hào)量

typedef struct {int value; //記錄資源的數(shù)據(jù)struct process *L; //等待隊(duì)列 }node; void wait(node s){s.value--;if(s.value < 0) { //如果系統(tǒng)資源數(shù)據(jù)不夠，則將進(jìn)程由運(yùn)行態(tài)切換到阻塞態(tài)，并將其掛載到隊(duì)列中等待block(s.L)} } void signal(node s) {s.value++;if(s.value <= 0) {wakeUp(s.L) //如果某個(gè)進(jìn)程釋放資源后，發(fā)現(xiàn)還有等待的進(jìn)程，則使用wakeUp原語(yǔ)從隊(duì)列中喚醒一個(gè)進(jìn)程} }

一旦判斷系統(tǒng)資源數(shù)量為0，當(dāng)前進(jìn)程就會(huì)使用block原語(yǔ)將自己從運(yùn)行態(tài)切換到阻塞態(tài)，主動(dòng)放棄處理機(jī)，將自己掛到隊(duì)列中去；所以不會(huì)進(jìn)程不會(huì)出現(xiàn)忙等的狀態(tài)(一直占用cpu，卻沒(méi)做任何事情）

10.1.3、信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程互斥

1、設(shè)置互斥信號(hào)量（mutex =1）
2、執(zhí)行P(mutext)操作
3、訪問(wèn)臨界資源
4、執(zhí)行V(mutext)操作

semaphore = 1; P()... 臨界資源 V()....

10.1.3、信號(hào)量機(jī)制實(shí)現(xiàn)進(jìn)程同步

:TODO

10.2、生產(chǎn)者消費(fèi)者問(wèn)題

生產(chǎn)者每次生成生產(chǎn)一個(gè)產(chǎn)品放入緩沖區(qū)，消費(fèi)者每次從緩沖區(qū)消費(fèi)一個(gè)產(chǎn)品。

相關(guān)問(wèn)題

1、緩沖滿(mǎn)時(shí)，生產(chǎn)者不能放入產(chǎn)品
2、緩沖區(qū)空時(shí)，消費(fèi)者不能消費(fèi)產(chǎn)品
3、當(dāng)生產(chǎn)者并發(fā)執(zhí)行時(shí)，有可能向緩沖區(qū)的同一個(gè)空間放入產(chǎn)品，就會(huì)造成覆蓋的狀況，所以必須互斥地訪問(wèn)緩沖區(qū)

---

11、死鎖

11.1、產(chǎn)生死鎖的原因和必要條件

所謂死鎖就是多個(gè)進(jìn)程同時(shí)競(jìng)爭(zhēng)同一種資源而陷入僵局

1、產(chǎn)生死鎖的原因：

1.競(jìng)爭(zhēng)資源
2.進(jìn)程的推進(jìn)順序非法

詳細(xì)分析

Ⅰ、競(jìng)爭(zhēng)資源

系統(tǒng)中的資源分為兩類(lèi)：可剝奪性資源，非剝奪性資源；
1.可剝奪性資源，當(dāng)進(jìn)程獲得可剝奪性資源時(shí)，可以被優(yōu)先級(jí)較高的進(jìn)程搶占；另外存儲(chǔ)管理程序可以將一個(gè)進(jìn)程從內(nèi)存調(diào)到外存上；由此可以得出CPU和主存輸入可剝奪性資源
2.不可剝奪性資源：這一類(lèi)資源只能由進(jìn)程使用完后自行釋放，所以像打印機(jī)、磁帶機(jī)屬于不可剝奪性資源

從上面的兩種資源我們就可以得出，當(dāng)不可剝奪性資源數(shù)量不多時(shí)，如果多個(gè)進(jìn)程同時(shí)競(jìng)爭(zhēng)，則可能發(fā)生死鎖，因?yàn)檫@種資源進(jìn)程不能被搶占

Ⅱ、進(jìn)程推進(jìn)順序不當(dāng)

進(jìn)程在運(yùn)行中具有異步的特征

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

1、互斥條件：資源必須是互斥訪問(wèn)的（在同一段時(shí)間內(nèi)只能由一個(gè)進(jìn)程訪問(wèn)）
2、請(qǐng)求和保持條件：即進(jìn)程已經(jīng)占有了至少一個(gè)資源，然后又去請(qǐng)求另外一個(gè)資源，而另外一個(gè)資源剛好被占用；此時(shí)請(qǐng)求陷入阻塞，然后該進(jìn)程又不放棄自己占有的資源
3、不剝奪條件：即該進(jìn)程獲得的資源，在進(jìn)程主動(dòng)釋放前不能被搶占（可以理解為上面的不可剝奪性資源）
4、環(huán)路等待條件：進(jìn)程發(fā)生死鎖時(shí)形成了一個(gè)環(huán)形阻塞（p0等p1,p1等p2，p2等p0)

3、處理死鎖的基本方法

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

4、

Ⅰ、預(yù)防死鎖
摒棄請(qǐng)求和保持條件：這種方式直接在所有進(jìn)程運(yùn)行之前，一次性的將資源分配給進(jìn)程，此后不再進(jìn)行申請(qǐng)資源。這種方法缺點(diǎn)是極大的浪費(fèi)了系統(tǒng)資源，還有可能需求資源被其他進(jìn)程一直占用，遲遲不能執(zhí)行。

摒棄不剝奪條件：這種方式是當(dāng)進(jìn)程正在使用某個(gè)資源時(shí)，如果其他進(jìn)程請(qǐng)求該資源，則占用該資源的線程立即釋放當(dāng)前資源。這種方式的缺點(diǎn)也很明顯，比如不可剝奪性資源打印機(jī)，如果某個(gè)進(jìn)程正在使用，如果中斷一次，那么兩次打印的信息可能不會(huì)連續(xù)。反復(fù)的申請(qǐng)和釋放資源，進(jìn)程運(yùn)行時(shí)間比例被大大縮小。

摒棄環(huán)形等待：這種方式是將資源類(lèi)型進(jìn)行線性排隊(duì)，給每個(gè)資源進(jìn)行編號(hào)。這個(gè)缺點(diǎn)是每個(gè)資源的使用順序可能不一樣

Ⅱ、避免死鎖
這種方式通過(guò)將系統(tǒng)始終處于安全狀態(tài)，這種方式可以獲得令人滿(mǎn)意的性能
這種方式主要考慮資源的分配順序，因?yàn)橘Y源數(shù)量不一致嘛

重點(diǎn)：銀行家算法避免死鎖

Ⅲ、檢測(cè)死鎖
通過(guò)用例分配圖檢測(cè)死鎖

Ⅳ、解除死鎖
通過(guò)剝奪資源和撤銷(xiāo)進(jìn)程來(lái)實(shí)現(xiàn)
（注意這個(gè)剝奪資源是從其他進(jìn)程剝奪其資源給死鎖進(jìn)程）

---

12、存儲(chǔ)器管理

12.1、多級(jí)存儲(chǔ)器結(jié)構(gòu)

cpu寄存器：寄存器
主存：高速緩存、主存、磁盤(pán)緩存
輔存：磁盤(pán)、可移動(dòng)存儲(chǔ)介質(zhì)

12.2、程序的裝入和鏈接

程序如果想要運(yùn)行，必須創(chuàng)建進(jìn)程，而創(chuàng)建進(jìn)程第一件事情肯定是將程序和數(shù)據(jù)加載到內(nèi)存中。而如何將一個(gè)程序變成一個(gè)可以在內(nèi)存中可執(zhí)行的程序，通常需要完成三部：編譯、鏈接、裝入

12.2.1、程序的裝入

1.絕對(duì)裝入方式：這種方式邏輯地址和實(shí)際內(nèi)存地址相同，故不需要對(duì)數(shù)據(jù)進(jìn)行更改
2.可重定位裝入方式：最后需要修改指令和數(shù)據(jù)
3.動(dòng)態(tài)運(yùn)行時(shí)裝入方式：可以任意改變?cè)趦?nèi)存中的位置

12.2.2、程序的鏈接

程序編譯之后形成了一系列的模塊，需要利用鏈接程序?qū)⒛繕?biāo)塊鏈接。形成裝入模塊
1.靜態(tài)鏈接：在程序運(yùn)行之前，將其鏈接成一個(gè)完整的模塊，以后不再分開(kāi)
2.裝入時(shí)動(dòng)態(tài)鏈接：在目標(biāo)模塊裝入內(nèi)存時(shí)，采用邊裝入邊鏈接的方式
3.運(yùn)行時(shí)動(dòng)態(tài)鏈接：在程序運(yùn)行過(guò)程中，需要某個(gè)模塊時(shí)，才對(duì)對(duì)其進(jìn)行鏈接

12.3、連續(xù)分配方式

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

這種存儲(chǔ)管理方式，把內(nèi)存分為系統(tǒng)區(qū)和用戶(hù)區(qū)；系統(tǒng)區(qū)處于內(nèi)存的地址部分，其余的是用戶(hù)區(qū)，提供給用戶(hù)使用

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

將內(nèi)存分位幾個(gè)固定大小的空間，劃分位幾個(gè)分區(qū)，就允許幾個(gè)作業(yè)并發(fā)運(yùn)行。當(dāng)某個(gè)作業(yè)運(yùn)行結(jié)束時(shí)，便可以從外存的后備隊(duì)列中選擇一個(gè)適當(dāng)大小的作業(yè)裝入該分區(qū)

缺乏靈活性、容易造成資源浪費(fèi)

12.3.3、動(dòng)態(tài)分區(qū)分配

根據(jù)實(shí)際的需要，動(dòng)態(tài)的分配空間；所以這涉及到三個(gè)問(wèn)題；數(shù)據(jù)結(jié)構(gòu)、分區(qū)分配算法、分區(qū)的分配和回收操作

1.數(shù)據(jù)結(jié)構(gòu)
空閑分區(qū)表：該表記錄空閑分區(qū)中的一些數(shù)據(jù)（分區(qū)始址和分區(qū)大小等）
空閑分區(qū)鏈：將所有空閑分區(qū)通過(guò)前后指針鏈接起來(lái)

2、分區(qū)分配算法
Ⅰ.首次適應(yīng)算法，該算法要去分區(qū)鏈以地址遞增的順序鏈接；分配內(nèi)存時(shí)從鏈?zhǔn)组_(kāi)始尋找，直到找到一個(gè)符合要求得分區(qū)，選擇合適的大小，余下的仍留在空閑鏈中。這種算法優(yōu)先利用低地址部分的空間，將高地址的大空間留給后續(xù)大作業(yè)，但是會(huì)在低地址部分留下很多小的空閑分區(qū)，然后分區(qū)時(shí)又是從低地址開(kāi)始的，查詢(xún)開(kāi)銷(xiāo)無(wú)疑增大

…飛速總結(jié)中 ?? ??

總結(jié)

以上是生活随笔為你收集整理的计算机操作系统还能这样玩？这一篇计算机操作系统的总结为你保驾护航（零风险、高质量、万字长文、建议收藏）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。