一、緒論

1.OS概述

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

• 操作系統(tǒng)是硬件和用戶/應(yīng)用之間的橋梁
• 操作系統(tǒng)管理硬件，為應(yīng)用和用戶服務(wù)
• 操作系統(tǒng)是裁判、魔法師、膠帶
  • 裁判：讓?xiě)?yīng)用之間隔離使用資源（用戶態(tài)和內(nèi)核態(tài)的設(shè)計(jì)）
  • 魔法師：讓?xiě)?yīng)用感受到似乎獨(dú)占所有的硬件資源
  • 膠帶：縫合了上層應(yīng)用和底層硬件之間的gap，包括硬件的接口會(huì)改變、硬件的功能會(huì)進(jìn)化、應(yīng)用也會(huì)改變，操作系統(tǒng)給應(yīng)用提供了一個(gè)統(tǒng)一的接口

2.CPU概述

OS與CPU之間頻繁的進(jìn)行交互，因此了解CPU的組成非常必要

二、Boot,Process,Kernel

1.BIOS

BIOS是一種固件，固件是一種軟件，和普通軟件和操作系統(tǒng)都不一樣，通常放在不可改的存儲(chǔ)器上面；

BIOS是第一個(gè)機(jī)器啟動(dòng)以后會(huì)運(yùn)行的軟件，BIOS主要執(zhí)行以下的操作：

2.Bootloader

bootloader是OS的一部分，一般認(rèn)為OS=bootloader+kernel；

bootloader主要完成下面的操作

關(guān)于bootloader和BIOS的區(qū)別

Q：為什么BIOS不直接load整個(gè)OS？

A：因?yàn)锽IOS只能load很小的一部分的數(shù)據(jù)（歷史的包袱），并且BIOS需要保持最簡(jiǎn)化的功能（固件最簡(jiǎn)化）；

3.雙模式

實(shí)模式和保護(hù)模式的區(qū)別 - 歷史的包袱，因?yàn)橛布粩嘌莼僮飨到y(tǒng)需要兼容，甚至硬件之間也要相互兼容；

保護(hù)模式能夠真正的保護(hù)進(jìn)程的一些信息；

實(shí)模式和保護(hù)模式實(shí)際上是CPU運(yùn)行的兩種狀態(tài)，實(shí)模式下一般只能訪問(wèn)16bit的數(shù)據(jù)，為了訪問(wèn)更高位數(shù)的數(shù)據(jù)并兼容16bit出現(xiàn)了保護(hù)模式；

4.進(jìn)程

4.1 進(jìn)程定義

進(jìn)程的定義：一個(gè)程序的運(yùn)行時(shí)，包含一些權(quán)限限制

Q：進(jìn)程和普通程序的區(qū)別？

A：

4.2 PCB

4.3 進(jìn)程&內(nèi)存

對(duì)一個(gè)進(jìn)程/程序來(lái)說(shuō)似乎獨(dú)占所有硬件資源，一般進(jìn)程會(huì)分為幾個(gè)段，其中堆向上生長(zhǎng)，棧向下生長(zhǎng)

注：這里討論的地址都是虛擬地址，一個(gè)可執(zhí)行的程序已經(jīng)指定好了段的大小等信息；

5.雙模態(tài)

操作系統(tǒng)設(shè)計(jì)了雙模態(tài)的概念，即CPU在執(zhí)行的時(shí)候可選擇兩種狀態(tài)，其中內(nèi)核態(tài)擁有更高的權(quán)限，能夠做更多的事情；

雙模態(tài)由OS和硬件共同實(shí)現(xiàn)，其中硬件主要完成以下四部分的功能

5.1 特權(quán)指令

特權(quán)指令：只有CPU在內(nèi)核態(tài)的時(shí)候才能執(zhí)行

一個(gè)不嚴(yán)謹(jǐn)?shù)恼f(shuō)法是，影響其他進(jìn)程的指令就是特權(quán)指令

如何執(zhí)行特權(quán)指令呢？讓操作系統(tǒng)幫進(jìn)程執(zhí)行特權(quán)指令，其中系統(tǒng)調(diào)用是操作系統(tǒng)暴露給用戶態(tài)程序的一些接口

如果程序執(zhí)行了特權(quán)指令會(huì)被檢測(cè)到并kill

5.2 內(nèi)存保護(hù)

硬件需要提供的第二部分是內(nèi)存保護(hù)，使得地址是隔離的

5.2.1 分段

分段法是最簡(jiǎn)單的方法，每個(gè)程序使用bounds大小的內(nèi)存空間，缺點(diǎn)是共享、碎片化問(wèn)題

5.2.2 分頁(yè)

因?yàn)榉侄未嬖诤艽蟮膯?wèn)題，所以現(xiàn)代操作系統(tǒng)一般都使用分頁(yè)的方法；

由硬件(CPU)來(lái)執(zhí)行虛擬地址到物理地址之間的映射，由軟件OS來(lái)決定映射的策略；

OS和CPU的中間體就是頁(yè)表，頁(yè)表存在內(nèi)存中；

一般多個(gè)進(jìn)程的kernel代碼都是相同的，映射到同一塊區(qū)域

Q：為什么內(nèi)核代碼存放在高地址空間？

A：歷史的包袱 – 方便進(jìn)程用戶態(tài)從低地址處理

5.3 時(shí)間片中斷

5.4 CPL

6.小結(jié)

三、context switch

上下文切換，主要講解用戶空間和內(nèi)核空間的上下文切換（這個(gè)話是老師的原話，但是我感覺(jué)和上下文切換完全沒(méi)有關(guān)系）

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

有三種可能CPU會(huì)從用戶態(tài)切換到內(nèi)核態(tài)

1.1 中斷

中斷處理對(duì)用戶來(lái)說(shuō)是不可見(jiàn)的，對(duì)進(jìn)程的狀態(tài)不會(huì)影響；

中斷向量表

中斷向量表是在實(shí)模式下使用的，中斷向量表一般保存在一個(gè)固定的位置

中斷描述符表

中斷描述符表IDT是在保護(hù)模式下使用的，有更多專有名詞，其中的每個(gè)元素稱為一個(gè)門(mén)，一共有256個(gè)門(mén)，中斷描述符表不是在固定的位置，通常其位置存放在一個(gè)寄存器IDTR中，該寄存器的值可以動(dòng)態(tài)加載

Q：具體如何從中斷發(fā)生定位到中斷處理程序？

A：首先IDTR會(huì)指向中斷描述符表的開(kāi)始位置，接著根據(jù)中斷號(hào)找到中斷描述符表中對(duì)應(yīng)的項(xiàng)，在項(xiàng)中提取出offset，因?yàn)榉侄蔚脑蚩赡苓€需要加上一個(gè)基地址，就可以找到相應(yīng)的中斷處理程序

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-42EHQ7GP-1678871761625)(https://img2023.cnblogs.com/blog/2922190/202301/2922190-20230111133719282-1962803577.png)]

Q：如何知道中斷號(hào)呢？如何知道現(xiàn)在發(fā)生的是第幾號(hào)中斷呢？

A：只有硬件知道，硬件層面會(huì)通知這個(gè)中斷是第幾號(hào)；

中斷向量表和中斷描述符表的區(qū)別，首先它們的共性是可以實(shí)現(xiàn)隔離，所有用戶態(tài)的代碼要進(jìn)入內(nèi)核態(tài)只有這幾道門(mén)，這兩個(gè)表決定了門(mén)的數(shù)量和種類，因此在寫(xiě)內(nèi)核的時(shí)候只需要保證這幾個(gè)門(mén)的安全性即可

中斷屏蔽

不是所有的中斷都必須要發(fā)生，操作系統(tǒng)可以mask一些中斷，有些中斷可以屏蔽有些不可以；

中斷屏蔽只是推遲了中斷的發(fā)生，并不是直接忽略的中斷的發(fā)生；

中斷棧

在內(nèi)核的中斷處理程序在處理中斷的時(shí)候需要棧，這個(gè)棧放在內(nèi)核態(tài)（因?yàn)橛脩魬B(tài)的棧會(huì)被修改）；

如果沒(méi)有中斷產(chǎn)生的時(shí)候中斷棧是空的，因?yàn)椴恍枰幚砣魏问虑椋?/p>

操作系統(tǒng)中的中斷棧的計(jì)算公式

數(shù)字1的原因是第一次中斷就是我們常見(jiàn)的中斷，將用戶態(tài)轉(zhuǎn)換為內(nèi)核態(tài)，一般情況下可以在一層中斷的基礎(chǔ)上嵌套實(shí)現(xiàn)第二層中斷，這個(gè)中斷可以共享第一次的中斷棧，二第三層中斷一般不被允許直接導(dǎo)致OS重啟；

每一個(gè)線程或者進(jìn)程都會(huì)有一個(gè)自己的中斷棧，是為了使得操作系統(tǒng)能夠更好的處理不同進(jìn)程/線程的中斷（多個(gè)進(jìn)程可能同時(shí)產(chǎn)生中斷）

2.從內(nèi)核態(tài)到用戶態(tài)

如下情況（或者方式）會(huì)導(dǎo)致CPU從內(nèi)核態(tài)切換到用戶態(tài)

3.X86概述

X86使用的是分段

其中CS寄存器的值只能使用以下指令改變

3.1 X86的中斷處理

當(dāng)中斷/異常/系統(tǒng)調(diào)用發(fā)生的時(shí)候，硬件會(huì)進(jìn)行如下操作

Q：為什么需要臨時(shí)寄存器？

A：因?yàn)榈谌角袚Q棧是修改SS:ESP的地址，如果沒(méi)有臨時(shí)寄存器就根本不能保護(hù)現(xiàn)場(chǎng)即回不去之前的狀態(tài)了

硬件處理之前的棧狀態(tài)

硬件處理之后的棧狀態(tài)

中斷發(fā)生的時(shí)候硬件會(huì)做上面的事，OS會(huì)做什么操作呢？

Q：專門(mén)的寄存器指向當(dāng)前棧，但是為什么沒(méi)有專門(mén)指向堆的寄存器？

A：因?yàn)椴恍枰赶驐Ｊ且驗(yàn)镺S需要用到棧，但是堆是用戶自己操控的；

四、OS Interfaces and Syscalls

操作系統(tǒng)給應(yīng)用/用戶提供了非常多的功能

1.進(jìn)程管理

1.1 Windows中的API

在Windows下通常使用CreateProcess這個(gè)API來(lái)創(chuàng)建進(jìn)程

1.2 Linux中的API

在Linux中會(huì)使用fork()和exec()函數(shù)創(chuàng)建一個(gè)新的進(jìn)程；

1.2.1 fork()

fork沒(méi)有任何參數(shù)，會(huì)完全拷貝一個(gè)當(dāng)前進(jìn)程，返回值為0則是子進(jìn)程，父進(jìn)程會(huì)得到子進(jìn)程的進(jìn)程ID，是一個(gè)大于0的值，父進(jìn)程和子進(jìn)程之間唯一的區(qū)別就是返回值不同，父進(jìn)程和子進(jìn)程不共享地址空間，但是它們的地址空間的值完全相同；

Q：為什么父進(jìn)程和子進(jìn)程的環(huán)境相同還需要拷貝再賦值？

A：實(shí)際上這涉及Linux的優(yōu)化問(wèn)題，并不會(huì)是簡(jiǎn)單的值拷貝；

1.2.2 exec()

exec將會(huì)從磁盤(pán)下載并執(zhí)行一個(gè)程序，需要注意的是exec不會(huì)創(chuàng)建任何新的進(jìn)程；

并不是每個(gè)fork后面都需要緊跟一個(gè)exec，例如瀏覽器中打開(kāi)新的tag實(shí)際就是打開(kāi)一個(gè)新的進(jìn)程，但是這個(gè)進(jìn)程實(shí)際上是和原來(lái)的進(jìn)程使用的同一套代碼，就不需要再load一個(gè)新的程序

Linux中除了fork()和exec()以外，還有其他輔助函數(shù)

2.輸入/輸出

OS除了提供進(jìn)程管理功能，還提供I/O功能；

計(jì)算機(jī)有很多I/O設(shè)備，最簡(jiǎn)單的管理方法就是給每一個(gè)設(shè)備一個(gè)系統(tǒng)調(diào)用，但是Unix將所有的設(shè)備抽象為文件，好處是接口簡(jiǎn)潔、統(tǒng)一；

有文件就有相應(yīng)的結(jié)構(gòu)體來(lái)描述，Unix中使用文件描述符來(lái)描述，文件描述符本質(zhì)上就是一個(gè)int類型的值；

怎么使用int值來(lái)描述文件？操作系統(tǒng)有一個(gè)文件描述符表，每一個(gè)文件描述符可以在里面尋址到相應(yīng)的文件的信息；

需要注意的是每個(gè)進(jìn)程都有自己的文件描述符表，只有打開(kāi)的文件才有文件描述符（文件描述符是open函數(shù)的返回值，一個(gè)文件可以被open多次）；

2.1 通用輸入/輸出API

注意點(diǎn)：

• 每一類設(shè)備都對(duì)應(yīng)一類文件描述符；
• 要求所有的文件先打開(kāi)再使用；
• 文件描述符是有上下文的，多次read會(huì)累加進(jìn)行；
• 以字節(jié)為單位進(jìn)行操作；
• 內(nèi)核對(duì)讀寫(xiě)操作有緩沖作用；
• 每一個(gè)文件描述符都要close幫助垃圾回收；

open

close

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-eTzFgsrO-1678871761636)(https://img2023.cnblogs.com/blog/2922190/202301/2922190-20230111133920955-1933871181.png)]

read

write

3.系統(tǒng)調(diào)用的設(shè)計(jì)

對(duì)應(yīng)用來(lái)說(shuō)操作系統(tǒng)看起來(lái)就是提供了很多的函數(shù)（系統(tǒng)調(diào)用）而已，設(shè)計(jì)系統(tǒng)調(diào)用難點(diǎn)是如何保證內(nèi)核態(tài)的安全性，Unix中的系統(tǒng)調(diào)用基本都是如下流程實(shí)現(xiàn)

Q：如果不拷貝，內(nèi)核可以直接訪問(wèn)用戶態(tài)的參數(shù)嗎？

A：當(dāng)然可以，內(nèi)核的權(quán)限高于用戶；

Q：為什么參數(shù)一定要拷貝到內(nèi)核的內(nèi)存中？

A：直接使用會(huì)出現(xiàn)一些問(wèn)題，本質(zhì)上就是用戶態(tài)的代碼隨時(shí)可能被改變不安全，所以一般不建議；

Q：可不可以先檢查再拷貝？

A：如果在檢查以后再拷貝進(jìn)來(lái)就沒(méi)辦法修改了（內(nèi)核態(tài)的代碼不能修改），容易導(dǎo)致系統(tǒng)漏洞；

五、threads

1.線程抽象

Q：為什么需要線程？

• 線程通常和并發(fā)聯(lián)系在一起，并發(fā)是指多個(gè)任務(wù)同時(shí)進(jìn)行；

  • 多任務(wù)和并發(fā)：多任務(wù)強(qiáng)調(diào)不同的任務(wù)，并發(fā)一般側(cè)重多個(gè)任務(wù)“同時(shí)”執(zhí)行；

  • 并發(fā)和并行：并行是真正的同時(shí)執(zhí)行；

• 有些程序在邏輯上就應(yīng)該是實(shí)現(xiàn)并發(fā)的（代碼自上而下執(zhí)行很別扭）

• 某些線程不應(yīng)該影響另一些線程的體驗(yàn)：前臺(tái)線程和后臺(tái)線程分離執(zhí)行

• 多線程/多進(jìn)程可以使用多個(gè)核

  • 并不是核越多越快，可能還有其他的瓶頸比如CPU、存儲(chǔ)等速度限制

• 其他線程阻塞的時(shí)候可以讓CPU一直保持忙碌狀態(tài)

線程定義：一個(gè)可以被單獨(dú)調(diào)度的順序執(zhí)行序列，即線程可以隨便被掛起、恢復(fù)

線程就是同一個(gè)進(jìn)程中不同的函數(shù)，可以交替執(zhí)行，線程是操作系統(tǒng)最小的調(diào)度單位；

1.1 線程的特點(diǎn)

線程之間不會(huì)共享?xiàng)?，因?yàn)闂Ｊ菆?zhí)行的上下文，線程是被單獨(dú)調(diào)用的，不能共享上下文；

線程共享地址空間但是不共享?xiàng)?、寄存器（上下文）?/p>

線程的執(zhí)行速度是不可預(yù)測(cè)的，因?yàn)樗S時(shí)可能被掛起（同步問(wèn)題）

1.2 線程&進(jìn)程

1.3 線程API

1.4 線程的生命周期

2.線程實(shí)現(xiàn)

2.1 TCB

和進(jìn)程控制塊類似，線程也有控制塊

Q：一個(gè)進(jìn)程可以有很多線程，那么線程的棧的大小有限制嗎？

A：棧的大小實(shí)際上和遞歸的深度有關(guān)，在內(nèi)核中，因?yàn)橐幚碇袛嗨孕枰袛鄺＃且驗(yàn)楸容^簡(jiǎn)潔所以中斷棧不需要很大；

同一個(gè)進(jìn)程中的線程共享代碼和地址空間、全局變量，因?yàn)榫€程共享地址空間，所以可能會(huì)導(dǎo)致一些危險(xiǎn)；

線程如何實(shí)現(xiàn)呢？這里循序漸進(jìn)，先講內(nèi)核中如何實(shí)現(xiàn)線程，再講用戶態(tài)如何實(shí)現(xiàn)線程，需要注意的是內(nèi)核線程永遠(yuǎn)運(yùn)行在內(nèi)核態(tài)，其數(shù)據(jù)也存放在內(nèi)核空間中，由內(nèi)核態(tài)線程可以擴(kuò)展到用戶態(tài)線程；

2.2 內(nèi)核線程的實(shí)現(xiàn)

2.2.1 創(chuàng)建線程

下面這段代碼是一個(gè)簡(jiǎn)單的在內(nèi)核中創(chuàng)建線程的例子

2.2.2 刪除線程

怎么刪除一個(gè)線程？只需要把這個(gè)線程從List中刪除即可，再將相應(yīng)的空間釋放掉

綜上，一個(gè)線程不能銷毀自己?。?！解決辦法是使用其他線程來(lái)幫助自己free掉finished的list中的線程；

2.2.3 線程切換

主要分為兩種切換方式，一種是主動(dòng)切換，另一種是被動(dòng)切換（中斷、異常）；

注意這里的線程切換不是指CPU狀態(tài)的切換，因?yàn)閮?nèi)核線程只能運(yùn)行在內(nèi)核態(tài)，這里指的是將一個(gè)正在運(yùn)行的內(nèi)核線程掛起，運(yùn)行另一個(gè)內(nèi)核線程；

主動(dòng)切換的流程如下

實(shí)例代碼如下

被動(dòng)切換的流程相對(duì)簡(jiǎn)單

2.3 用戶線程的實(shí)現(xiàn)

實(shí)現(xiàn)用戶態(tài)的多線程主要有如下幾種方法：

假如要實(shí)現(xiàn)一個(gè)用戶態(tài)的create_thread函數(shù)

第二種方式就是完全使用用戶態(tài)下的庫(kù)函數(shù)，整個(gè)過(guò)程沒(méi)有內(nèi)核的參與，庫(kù)維護(hù)了用戶空間所需的一切狀態(tài)；

Q：如何使得在用戶態(tài)下實(shí)現(xiàn)并發(fā)的多線程？

A：操作系統(tǒng)并不知道用戶線程的存在，內(nèi)核線程可以實(shí)現(xiàn)線程的并發(fā)是基于時(shí)間片的中斷，但是用戶態(tài)根本感知不到時(shí)間片的中斷（時(shí)間片是內(nèi)核的東西），一個(gè)解決辦法是主動(dòng)讓出，或者是搶占式的upcall

Q：用戶態(tài)線程如何切換程序指針或棧指針呢？

A：用戶態(tài)線程改變PC下一條指令使用jump指令實(shí)現(xiàn)，改變棧指針很簡(jiǎn)單，直接修改寄存器的值即可；

下面總結(jié)用戶線程和內(nèi)核線程的異同

六、Address Translation

1.地址翻譯概述

用戶看到的所有地址都是虛擬地址，從虛擬地址到物理地址有一個(gè)轉(zhuǎn)換的過(guò)程，被稱為地址翻譯，地址翻譯并不僅僅做翻譯的事

地址翻譯的目標(biāo)如下

地址翻譯需要硬件和操作系統(tǒng)同時(shí)協(xié)作實(shí)現(xiàn)；

地址翻譯主要有兩種實(shí)現(xiàn)方式，分別是分段和分頁(yè)，一般分段都使用16為操作系統(tǒng)，分頁(yè)一般使用32位操作系統(tǒng)進(jìn)行講解；

在分段和分頁(yè)同時(shí)存在的情況下，虛擬地址經(jīng)過(guò)分段后稱為線性地址，線性地址經(jīng)過(guò)分頁(yè)過(guò)后才是物理地址；

2.分段

2.1 分段表

在實(shí)模式下不存在分段表

2.2 X86視角

X86規(guī)定程序只能有6個(gè)段，并且規(guī)定了每個(gè)段怎么使用，默認(rèn)會(huì)添加段前綴

2.2.1 實(shí)模式

最多能訪問(wèn)2²⁰的物理地址，并且同一個(gè)物理地址可能有多種組合情況；

2.2.2 保護(hù)模式

保護(hù)模式下，分段表被稱為GDT全局描述符表和LDT局部描述符表

2.3 小結(jié)

分段很強(qiáng)大，主要有以下功能

分段最大的問(wèn)題就是很容易產(chǎn)生碎片化

3.分頁(yè)

分頁(yè)和分段最大的區(qū)別就是分頁(yè)將物理地址分為一個(gè)個(gè)固定大小的頁(yè)，以頁(yè)位單位進(jìn)行內(nèi)存的映射；

頁(yè)表用于實(shí)現(xiàn)虛擬頁(yè)和內(nèi)存頁(yè)之間的映射，記錄了每一個(gè)虛擬頁(yè)對(duì)應(yīng)的物理頁(yè)；使用頁(yè)不再需要bound這個(gè)限制，因?yàn)轫?yè)的大小已經(jīng)固定；使用分頁(yè)后，在虛擬地址看起來(lái)連續(xù)的頁(yè)在物理地址上幾乎是完全隨機(jī)的；

分頁(yè)的好處：

• 在分配內(nèi)存的時(shí)候非常方便，直接以頁(yè)為單位分配即可；

• 分頁(yè)很容易實(shí)現(xiàn)內(nèi)存的共享，將頁(yè)表項(xiàng)映射到同一個(gè)物理頁(yè)；

下圖是一個(gè)最基本的分頁(yè)的地址翻譯的過(guò)程，使用的是一級(jí)頁(yè)表

當(dāng)我們限定地址的大小為32bit的時(shí)候，需要會(huì)計(jì)算頁(yè)表和物理頁(yè)的大小

可以看到一個(gè)頁(yè)表大小為4MB，很多進(jìn)程甚至都用不到4MB，而且每一個(gè)進(jìn)程都需要這么大的頁(yè)表，無(wú)疑會(huì)造成浪費(fèi)，所以現(xiàn)代操作系統(tǒng)出現(xiàn)了多級(jí)頁(yè)表

Q：本質(zhì)上二級(jí)頁(yè)表并沒(méi)有增大邏輯地址或者物理地址，二級(jí)頁(yè)表是怎么節(jié)省空間的呢？

A：這是因?yàn)榻柚讼∈栊裕徽{(diào)用需要的頁(yè)表即可；

Q：在上下文切換的時(shí)候（指的是進(jìn)程），什么也需要切換？

A：CR3寄存器的值，也就是頁(yè)目錄的起始地址；

3.1 頁(yè)目錄

3.2 頁(yè)表

每個(gè)進(jìn)程和內(nèi)核都有自己的頁(yè)表，因?yàn)榈刂犯綦x，但是線程是共享地址空間的所以線程共享頁(yè)表（頁(yè)目錄同理）；

3.3 MMU

整個(gè)翻譯的過(guò)程是由一個(gè)被稱為MMU的硬件完成，不是操作系統(tǒng)實(shí)現(xiàn)的（因?yàn)椴僮飨到y(tǒng)實(shí)現(xiàn)地址翻譯非常緩慢）；

PS：頁(yè)的大小非常重要，頁(yè)太小會(huì)導(dǎo)致頁(yè)表非常大（頁(yè)變多了），頁(yè)表太大會(huì)浪費(fèi)空間；

3.4 缺頁(yè)中斷

簡(jiǎn)單理解缺頁(yè)中斷就是CPU/MMU在進(jìn)行映射的時(shí)候發(fā)現(xiàn)內(nèi)存中并不存在與邏輯頁(yè)對(duì)應(yīng)的物理頁(yè)；

出現(xiàn)缺頁(yè)中斷的情況：頁(yè)表項(xiàng)不存在（最后一個(gè)比特為0）、權(quán)限不足、頁(yè)表不存在（最后一個(gè)比特為0）；

3.5 COW

這個(gè)概念的全稱是Copy-on-Write，是Linux中節(jié)省空間的做法

拿fork舉例，子進(jìn)程和父進(jìn)程完全一樣，但是很可能子進(jìn)程執(zhí)行的動(dòng)作完全不同，因此浪費(fèi)大量時(shí)間在復(fù)制內(nèi)存上，使用COW在復(fù)制頁(yè)表的時(shí)候不會(huì)復(fù)制具體的內(nèi)存的值，簡(jiǎn)單來(lái)說(shuō)COW會(huì)檢查頁(yè)表項(xiàng)的比特來(lái)處理是否進(jìn)行寫(xiě)入操作，對(duì)應(yīng)的考題如下

3.6 小結(jié)

下面給出幾道練習(xí)題

4K是指一個(gè)物理頁(yè)的大小是2¹²bit，一共有多少個(gè)物理頁(yè)呢？一共有2¹⁰*2¹⁰的物理頁(yè)框，故計(jì)算得到最大尋址空間為4GB

Q：操作系統(tǒng)只能使用虛擬地址，那么操作系統(tǒng)如何知道一個(gè)虛擬地址的物理地址？

A：使用自映射，需要頁(yè)表項(xiàng)的物理地址就映射一次，需要頁(yè)目錄項(xiàng)的物理地址就映射兩次；

4.分段&分頁(yè)

實(shí)際上分段和分頁(yè)是可以合并使用的，邏輯/虛擬地址經(jīng)過(guò)分段稱為線性地址，線性地址經(jīng)過(guò)分頁(yè)之后變成物理地址

緩存是一個(gè)非常廣泛的概念（有各種各樣的緩存），本質(zhì)上是一段存儲(chǔ)，訪問(wèn)速度非?？?/p>

平均響應(yīng)時(shí)間如下

為什么需要緩存？存儲(chǔ)器的提升并沒(méi)有CPU的迭代速度快，緩存就是用于填補(bǔ)這部分的gap的

緩存命中率取決于時(shí)間局部性和空間局部性：

• 時(shí)間局部性：一個(gè)地址可能在短時(shí)間內(nèi)被訪問(wèn)多次；
• 空間局部性：要訪問(wèn)的內(nèi)容在上次訪問(wèn)內(nèi)容的附近；

緩存可以構(gòu)成如下架構(gòu)

常見(jiàn)的緩存如下

七、TLB and Cache

1.TLB

地址翻譯最大的缺點(diǎn)就是使得內(nèi)存的訪問(wèn)變慢；

TLB是在MMU內(nèi)部的一個(gè)加速地址翻譯的緩存，為什么地址翻譯可以被緩存？因?yàn)榫植啃栽恚?/p>

• 時(shí)間局部性：地址翻譯過(guò)程中會(huì)重復(fù)訪問(wèn)一個(gè)地址（for循環(huán)）；
• 空間局部性：訪問(wèn)的虛擬地址在原來(lái)地址的附近（代碼順序執(zhí)行）；

TLB中的翻譯實(shí)際上是以頁(yè)為單位，換句話來(lái)說(shuō)，地址翻譯都是以頁(yè)為單位；

TLB能夠很好的工作的原因就是因?yàn)槠涿新屎芨撸?/p>

TLB的工作過(guò)程非常簡(jiǎn)單：可以將TLB理解為具有如下三項(xiàng)的列表，分別是虛擬頁(yè)號(hào)（之所以不是虛擬地址是因?yàn)榈刂贩g是以頁(yè)對(duì)齊，因此只需要操作頁(yè)）、物理頁(yè)號(hào)和訪問(wèn)權(quán)限

1.1 TLB Lookup

通過(guò)引入TLB極大的減少了地址翻譯的時(shí)間

1.2 TLB Miss

TLB不命中的原因：頁(yè)沒(méi)有被訪問(wèn)過(guò)、TLB內(nèi)存有限等其他原因

如何解決TLB的Miss呢？當(dāng)我們按照完整的地址翻譯過(guò)程找到虛擬地址對(duì)應(yīng)的物理地址之后，需要將其更新到TLB中，現(xiàn)在基本上都讓硬件來(lái)完成更新的操作（因?yàn)橛布俣瓤欤?/p>

1.3 超頁(yè)

TLB最重要的一點(diǎn)就是需要保持一個(gè)非常高的命中率，如何進(jìn)一步提高TLB的命中率呢？頁(yè)大一點(diǎn)還是小一點(diǎn)更加容易命中？因?yàn)榇笠稽c(diǎn)可以導(dǎo)致頁(yè)更少，因此只需要緩存更少的頁(yè)即可，那么緩存命中的概率就更大；

超頁(yè)：向操作系統(tǒng)申請(qǐng)多個(gè)連續(xù)的極其大的頁(yè)（物理地址上連續(xù)），這在一定程度上能夠提高局部性原理，但是頁(yè)變大了不夠靈活浪費(fèi)空間，并且物理頁(yè)需要連續(xù)增加開(kāi)銷；

一個(gè)超頁(yè)在TLB中是對(duì)應(yīng)了一個(gè)TLB項(xiàng)（如果對(duì)應(yīng)多個(gè)TLB超頁(yè)就沒(méi)有存在的意義了，超頁(yè)可以看作是多個(gè)頁(yè)的集合體）；

1.4 TLB Consistency

無(wú)論是什么緩存（包括TLB），都需要具備一個(gè)非常重要的概念，即一致性，原因就是避免緩存和內(nèi)存的值不同；

主要在一下情況需要保持一致性：進(jìn)程上下文切換、權(quán)限變換、TLB擊落（多處理器訪問(wèn)）；

進(jìn)程上下文切換

權(quán)限變換

當(dāng)改變了頁(yè)表的權(quán)限（權(quán)限降低，從可寫(xiě)改變成只讀），解決辦法是直接將整個(gè)TLB或者單個(gè)的TLB項(xiàng)丟棄；

權(quán)限增大的時(shí)候是不需要做什么事情的，miss之后重新去頁(yè)表中更新TLB即可；

TLB Shutdown

在多處理器系統(tǒng)中，如果多個(gè)處理器在跑同一個(gè)進(jìn)程的多個(gè)線程（內(nèi)核線程），它們的頁(yè)表是相同的（因?yàn)槭峭粋€(gè)進(jìn)程），但是它們的TLB不同，因?yàn)門(mén)LB在CPU的MMU中，多處理器意味著多個(gè)CPU當(dāng)然TLB也就不同，那么當(dāng)一個(gè)處理器將頁(yè)表改變過(guò)后，它不僅需要修改自己的TLB，還需要告知其它處理器對(duì)TLB進(jìn)行修改；

2.Cache

此處的Cache就是CPU和內(nèi)存之間的告訴緩存，塊是Cache中的單位，塊的大小取決于硬件的設(shè)計(jì)；

2.1 Cache Lookup

主要分為全相聯(lián)映射、直接映射和N路組相聯(lián)映射，理解這幾種映射需要做題；

2.1.1 直接映射

地址映射規(guī)則：將主存分區(qū)，每個(gè)區(qū)域內(nèi)的主存塊數(shù)與Cache內(nèi)的塊數(shù)相同；

1. 主存中的每一塊只能映射到Cache內(nèi)的固定行，規(guī)則為
   $$i=jmodm$$
   其中i為Cache的行號(hào)，j為主存的塊號(hào)，m為Cache的總塊數(shù)

2. 不使用替換算法，產(chǎn)生沖突直接替換原有內(nèi)容；

3. 為了在Cache中記住自己存儲(chǔ)的數(shù)據(jù)塊屬于主存中的哪一個(gè)區(qū)，Cache需要額外在Cache行中設(shè)置標(biāo)記字段，假設(shè)主存有256塊，Cache有8塊，則主存要?jiǎng)澐?2個(gè)區(qū)，Cache需要5位標(biāo)記字段來(lái)標(biāo)記區(qū)號(hào)，3位標(biāo)記Cache行號(hào)；

4. 使用直接映射，則CPU使用的內(nèi)存地址結(jié)構(gòu)為：

   

5. 地址變換過(guò)程為：先按照Cache行號(hào)找到Cache中的塊，接著用標(biāo)記字段與Cache中的區(qū)號(hào)/標(biāo)記進(jìn)行比較，如果相同則命中，使用塊內(nèi)地址在Cache中取出需要的數(shù)據(jù)；

2.1.2 全相聯(lián)映射

地址映射規(guī)則：主存的任意一塊可以映射到Cache中的任意一塊

1. 主存與緩存分成相同大小的數(shù)據(jù)塊。

2. 主存的某一數(shù)據(jù)塊可以裝入緩存的任意一塊空間中。

3. 為了在Cache中記住自己存儲(chǔ)的數(shù)據(jù)塊來(lái)自主存中的哪一塊，Cache需要額外在Cache行中設(shè)置標(biāo)記字段，假設(shè)主存有2048個(gè)地址塊，則Cache標(biāo)記字段的位數(shù)為11位

4. 假設(shè)使用全相聯(lián)映射，則CPU使用的內(nèi)存地址結(jié)構(gòu)為：

   

5. 地址變換過(guò)程為：先按照標(biāo)記找到存儲(chǔ)主存塊數(shù)據(jù)的Cache塊，若找到則代表命中，接著使用塊內(nèi)地址在Cache塊中取出需要的數(shù)據(jù)；

2.1.3 組相聯(lián)映射

地址映射規(guī)則：將主存分區(qū)，將Cache分組，要求主存的每個(gè)區(qū)的塊數(shù)與Cache的組數(shù)相同（主存中一個(gè)區(qū)分為4塊所以Cache中需要4組）

為了在Cache中記住自己存儲(chǔ)的數(shù)據(jù)塊來(lái)自主存中的哪一個(gè)區(qū)，Cache額外增加了標(biāo)記字段；

假設(shè)每組有r個(gè)Cache塊，則稱為r路組相聯(lián)；

1. Cache組間采用直接映射（主存塊存放到哪個(gè)組是固定的），組內(nèi)采用全相聯(lián)映射（主存塊存放到組內(nèi)的哪一行是靈活的）

組間直接映射規(guī)則：
$$Cache組號(hào)=主存塊號(hào)modcache組數(shù)$$
2.使用組相聯(lián)映射，CPU的內(nèi)存地址結(jié)構(gòu)為：

? 標(biāo)記：主存區(qū)號(hào)的標(biāo)記 組號(hào)：Cache組的地址 塊內(nèi)地址：Cache中的字塊內(nèi)的地址

3.地址變換過(guò)程：首先使用組號(hào)找到Cache中的組，然后將標(biāo)記與該組所有Cache塊中的區(qū)號(hào)比較，如果相同則命中，使用塊內(nèi)地址取出需要的數(shù)據(jù)；

2.2 Cache Replacement

采用全相聯(lián)或組相聯(lián)映射方式的時(shí)候，從主存向Cache映射一個(gè)塊，當(dāng)Cache或Cache組中的空間被占滿時(shí)候，需要使用替換算法（直接映射沒(méi)有選擇直接替換，故不考慮替換算法）；

• 隨機(jī)算法：隨機(jī)確定要替換的Cache塊；
• FIFO算法：選擇最早調(diào)入的Cache進(jìn)行替換；

• LRU算法：

2.3 Cache Write Policies

Cache中的內(nèi)容是主存的副本，當(dāng)Cache中的內(nèi)容更新的時(shí)候，需要選擇寫(xiě)策略使得Cache與主存內(nèi)容保持一致；

2.3.1 全寫(xiě)法

也稱為寫(xiě)直通法、write-throught：

• 當(dāng)CPU對(duì)Cache寫(xiě)命中時(shí)，將數(shù)據(jù)同時(shí)寫(xiě)入Cache和主存；
• 當(dāng)Cache某塊需要替換時(shí)，不必將這塊寫(xiě)回主存（因?yàn)镃ache和主存隨時(shí)同步），直接用新調(diào)入的Cache塊覆蓋即可；

優(yōu)點(diǎn)是簡(jiǎn)單，隨時(shí)保持主存數(shù)據(jù)的正確性；

缺點(diǎn)是增加了訪存次數(shù)，降低了Cache效率，我們可以適當(dāng)在Cache和主存之間增加一個(gè)寫(xiě)緩沖 —— CPU同時(shí)將數(shù)據(jù)寫(xiě)入寫(xiě)緩沖和Cache，寫(xiě)緩沖再將內(nèi)容寫(xiě)入主存，由此解決速度不匹配的問(wèn)題；

2.3.2 寫(xiě)回法

write-back：

• 當(dāng)CPU對(duì)Cache寫(xiě)命中時(shí)，只修改Cache的內(nèi)容，不會(huì)立刻寫(xiě)入主存，只有當(dāng)該Cache塊被替換出的時(shí)候才寫(xiě)回主存；

這種方法減少了訪存次數(shù)，但是增加了不一致的風(fēng)險(xiǎn) —— 采用這種策略時(shí)每個(gè)Cache塊必須設(shè)置一個(gè)標(biāo)志位臟位以標(biāo)志此塊是否被CPU修改過(guò)；

上述兩種方法都應(yīng)對(duì)的是Cache寫(xiě)命中（也就是要修改的單元在Cache中）；

2.4 TLB&Cache

Q：Cache中的地址是虛擬地址還是物理地址？

A：從圖中可以知道是物理地址（從MMU中出來(lái)的都是物理地址）

如果Cache的命中率高但是TLB的命中率低則還是不能很好的協(xié)同工作，所以需要考慮如何使得TLB和Cache能夠協(xié)同工作

2.5 工作集

一個(gè)進(jìn)程需要工作，一般需要一塊內(nèi)存，該內(nèi)存的大小就是該進(jìn)程常駐在內(nèi)存中的大小，過(guò)大浪費(fèi)，過(guò)小需要不停的換入換出；

工作集的定義就是進(jìn)程在一段時(shí)間需要的內(nèi)存，可以適當(dāng)?shù)膶⒐ぷ骷旁贑ache中進(jìn)一步提升工作速度；

2.6 頁(yè)著色

當(dāng)Cache使用的是虛擬地址的時(shí)候會(huì)存在別名問(wèn)題，原因是操作系統(tǒng)和用戶程序可能對(duì)同一個(gè)物理地址使用兩種以上不同形式的虛擬地址來(lái)訪問(wèn)，這些地址被稱作別名，他們會(huì)導(dǎo)致同一個(gè)數(shù)據(jù)在使用虛擬地址的cache中存在兩個(gè)副本，如果其中一個(gè)數(shù)據(jù)被修改，那么另外一個(gè)就是錯(cuò)誤的；

解決別名問(wèn)題的方法之一就是使用頁(yè)著色：

• 如果強(qiáng)行要求別名的某些地址位相同，就可以用軟件很容易地解決這一問(wèn)題（如SUN公司的UNIX要求所有使用別名的地址最后18位都相同，這種限制被稱為頁(yè)著色）；
• 上述頁(yè)著色的限制使得容量不超過(guò)2^18字節(jié)（256KB）的直接映射Cache中不可能出現(xiàn)Cache塊有重復(fù)物理地址的情況，所有別名將被映射到同一Cache塊位置；

總結(jié)：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-777879.html

• 相同的color在內(nèi)存中離散存在；
• 相同的color在Cache中連續(xù)存在；

到了這里，關(guān)于北郵 操作系統(tǒng)期末復(fù)習(xí)（上）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！