計(jì)算機(jī)基礎(chǔ)-騰訊操作系統(tǒng)

1、技能樹.IT修真院：付 輝操作系統(tǒng)課程安排1. 操作系統(tǒng)概述，進(jìn)程與線程2. 處理機(jī)調(diào)度算法、進(jìn)程同步3. 內(nèi)存管理4. 文件管理、I/O管理內(nèi)存管理雖然內(nèi)存容量在不斷增長，但仍然不可能將所有用戶進(jìn)程和系統(tǒng)所需要的全部程序和數(shù)據(jù)放入主存中，因此操作系統(tǒng)必須將內(nèi)存空間進(jìn)行合理的劃分和有效的動態(tài)分配。內(nèi)存管理包括：內(nèi)存的分配與回收，地址轉(zhuǎn)換，邏輯地址轉(zhuǎn)換成物理地址，利用虛擬存儲技術(shù)擴(kuò)充內(nèi)存等內(nèi)容大綱1、程序裝入和鏈接2、連續(xù)分配管理方式3、非連續(xù)分配管理方式4、虛擬內(nèi)存管理 (1)用戶程序的處理步驟1 程序裝入和鏈接在多道程序環(huán)境下，要使程序運(yùn)行，必須創(chuàng)建進(jìn)程，而創(chuàng)建進(jìn)程就要將程序和數(shù)據(jù)裝入內(nèi)存。

2、一個(gè)用戶源程序要變?yōu)樵趦?nèi)存中可執(zhí)行的程序，通常要進(jìn)行以下處理：編譯：由編譯程序?qū)⒂脩粼闯绦蚓幾g成若干個(gè)目標(biāo)模塊。鏈接：由鏈接程序?qū)⒛繕?biāo)模塊和相應(yīng)的庫函數(shù)鏈接成裝入模塊。裝入：由裝入程序?qū)⒀b入模塊裝入內(nèi)存。 (2) 程序的鏈接1 程序裝入和鏈接 靜態(tài)鏈接方式是一種事先鏈接方式，即在程序運(yùn)行之前，先將各目標(biāo)模塊及它們所需的庫函數(shù)，鏈接成一個(gè)完整的裝入模塊(執(zhí)行文件)，以后不再拆開。模塊ACALL B;RETURN;模塊BCALL C;RETURN;模塊CRETURN;0L-10M-10N-10L-1LL+M-1L+ML+M+N-1模塊CReturn模塊B “L+M”Return模塊A “L”Ret

3、urn缺點(diǎn)：不便于對目標(biāo)模塊的修改和更新；無法實(shí)現(xiàn)對目標(biāo)模塊的共享。 (2) 程序的鏈接1 程序裝入和鏈接裝入時(shí)動態(tài)鏈接方式 指將一組目標(biāo)模塊在裝入內(nèi)存時(shí)，邊裝入邊鏈接的方式。運(yùn)行時(shí)動態(tài)鏈接方式 在程序運(yùn)行中需要某些目標(biāo)模塊時(shí)，才對它們進(jìn)行鏈接的方式。具有高效且節(jié)省內(nèi)存空間的優(yōu)點(diǎn)。便于實(shí)現(xiàn)對目標(biāo)木塊的共享、便于修改和更新。 (3) 程序的裝入1 程序裝入和鏈接絕對裝入編譯時(shí)根據(jù)目標(biāo)程序?qū)Ⅰv留在內(nèi)存中的某個(gè)位置，從而將產(chǎn)生絕對地址的目標(biāo)代碼。目標(biāo)代碼根據(jù)程序中的地址放入對應(yīng)的內(nèi)存中。此時(shí)邏輯地址和物理地址相同，絕對裝入指適用于單道程序環(huán)境?？芍囟ㄎ谎b入多個(gè)程序的起始地址都從0開始，程序中的其他地

4、址都是相對于起始地址的。裝入時(shí)將目標(biāo)程序中的指令和數(shù)據(jù)的相對地址轉(zhuǎn)換成裝入位置的物理地址，該過程成為重定位。這種地址變換是裝入時(shí)一次完成的，稱為靜態(tài)重定位。 (3) 程序的裝入1 程序裝入和鏈接動態(tài)運(yùn)行時(shí)裝入程序裝入內(nèi)存時(shí)，不立即把相對地址轉(zhuǎn)換成絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行。故裝入內(nèi)存后的所有地址均為相對地址。2 連續(xù)分配管理方式通常將主存劃分成兩個(gè)分區(qū):低地址分區(qū)用于駐留操作系統(tǒng)，以及中斷向量。用戶進(jìn)程駐留在高地址分區(qū)。系統(tǒng)為程序分配的內(nèi)存都是一個(gè)連續(xù)的地址空間。又分為：單一連續(xù)分配，固定分區(qū)分配和動態(tài)分區(qū)分配。 (1) 單一連續(xù)分配2 連續(xù)分配管理方式最簡單的一

5、種存儲管理方式，但只能用于單用戶、單任務(wù)的OS中。存儲管理方法：將內(nèi)存分為系統(tǒng)區(qū)（內(nèi)存低端，分配給OS用）和用戶區(qū)（內(nèi)存高端，分配給用戶用）。采用靜態(tài)分配方式，即作業(yè)一旦進(jìn)入內(nèi)存，就要等待它運(yùn)行結(jié)束后才能釋放內(nèi)存。主要特點(diǎn)：管理簡單，只需小量的軟件和硬件支持，便于用戶了解和使用。但因內(nèi)存中只裝入一道作業(yè)運(yùn)行，內(nèi)存空間浪費(fèi)大，各類資源的利用率也不高。 (1) 單一連續(xù)分配2 連續(xù)分配管理方式一個(gè)容量為256KB的內(nèi)存，操作系統(tǒng)占用32KB，剩下224KB全部分配給用戶作業(yè)，如果一個(gè)作業(yè)僅需64KB，那么就有160KB的存儲空間被浪費(fèi)。操作系統(tǒng)作業(yè)0KB32KB96KB256KB-1分配給用戶的空

6、間 (2) 固定分區(qū)分配2 連續(xù)分配管理方式是最早使用的一種可運(yùn)行多道程序的存儲管理方法。內(nèi)存空間的劃分：將內(nèi)存空間劃分為若干個(gè)固定大小的分區(qū)，每個(gè)分區(qū)可裝入一道用戶進(jìn)程。分區(qū)的大小可以相等，也可以不等，但事先必須確定，在運(yùn)行時(shí)不能改變。即分區(qū)大小及邊界在運(yùn)行時(shí)不能改變。系統(tǒng)需建立一張分區(qū)說明表或使用表，以記錄分區(qū)號、分區(qū)大小、分區(qū)的起始地址及狀態(tài)（已分配或未分配）。 (2) 固定分區(qū)分配2 連續(xù)分配管理方式os用戶程序p4p1p20k20k56k65k125k135k區(qū)號大小起址狀態(tài)136k20k已分配29k56k未分配360k65k已分配410k125k已分配分區(qū)說明表有些程序太大放不進(jìn)任

7、何一個(gè)分區(qū)；內(nèi)存利用率低，存在分區(qū)內(nèi)部有空間浪費(fèi)，稱為內(nèi)部碎片。 (3) 動態(tài)分區(qū)分配2 連續(xù)分配管理方式不事先將內(nèi)存劃分成一塊塊的分區(qū)，而是在作業(yè)進(jìn)入內(nèi)存時(shí)，根據(jù)作業(yè)的大小動態(tài)地建立分區(qū)，并使分區(qū)的大小正好適應(yīng)作業(yè)的需要。因此系統(tǒng)中分區(qū)的大小是可變的，分區(qū)的數(shù)目也是可變的。 (3) 動態(tài)分區(qū)分配2 連續(xù)分配管理方式動態(tài)分區(qū)最開始分配時(shí)是很好的，但是之后會導(dǎo)致內(nèi)存中出現(xiàn)很多小的內(nèi)存塊。稱為外部碎片?？?空閑區(qū)（Hole） 可用內(nèi)存塊；內(nèi)存中遍布不同大小的空閑區(qū)。當(dāng)進(jìn)程進(jìn)入系統(tǒng)時(shí)，就為其尋找足夠大的空閑區(qū)。操作系統(tǒng)需要維護(hù)的信息包括：a) 已分配分區(qū)（表） b) 自由分區(qū) (hole) (3)

8、動態(tài)分區(qū)分配2 連續(xù)分配管理方式按照一定的分配算法從空閑分區(qū)中選出一個(gè)滿足作業(yè)需求的分區(qū)分配給作業(yè)，如果這個(gè)空閑分區(qū)的容量比作業(yè)申請的空間要大，則將該分區(qū)一分為二，一部分分配給作業(yè)，剩下的部分仍然留在空閑分區(qū)表（鏈）中，同時(shí)修改空閑分區(qū)表（鏈）中相應(yīng)的信息。目前常用分配算法有：首次適應(yīng)算法最佳適應(yīng)算法最大適應(yīng)算法鄰近適應(yīng)算法 (3) 動態(tài)分區(qū)分配-首次適應(yīng)算法2 連續(xù)分配管理方式將空閑分區(qū)（塊）按地址遞增的順序排列，每次分配內(nèi)存時(shí)，總是從空閑分區(qū)表（鏈）首開始順序查找，直到找到第一個(gè)滿足其大小要求的空閑分區(qū)為止。然后再按照作業(yè)大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請求者，余下的空閑分區(qū)仍留在空

9、閑分區(qū)表（鏈）中。優(yōu)先利用內(nèi)存低地址部分的空閑分區(qū),從而保留了高地址部分的大空閑區(qū)。但由于低地址部分不斷被劃分,致使低地址端留下許多難以利用的很小的空閑分區(qū)(碎片或零頭),而每次查找又都是從低地址部分開始,這無疑增加了查找可用空閑分區(qū)的開銷。 (3) 動態(tài)分區(qū)分配-最佳適應(yīng)算法2 連續(xù)分配管理方式空閑分區(qū)表/鏈按容量大小遞增的次序排列。在進(jìn)行內(nèi)存分配時(shí)，從空閑分區(qū)表/鏈的首開始順序查找，直到找到第一個(gè)滿足其大小要求的空閑分區(qū)為止。按這種方式為作業(yè)分配內(nèi)存，就能把既滿足作業(yè)要求又與作業(yè)大小最接近的空閑分區(qū)分配給作業(yè)。如果該空閑分區(qū)大于作業(yè)的大小，則與首次適應(yīng)算法相同，將剩余空閑分區(qū)仍留在空閑分區(qū)

10、表/鏈中。 (1) 引入原因3 非連續(xù)分配管理方式在連續(xù)分區(qū)存儲管理中，要求把進(jìn)程放在一個(gè)連續(xù)的存儲區(qū)中，因而會產(chǎn)生許多碎片。解決方法代價(jià)高。允許將作業(yè)/進(jìn)程離散放到多個(gè)不相鄰接的分區(qū)中，就可以避免拼接?；谶@一思想產(chǎn)生了以下的離散分配方式：分頁存儲管理分段存儲管理段頁式存儲管理 (2)分頁存儲管理-基本概念3 非連續(xù)分配管理方式進(jìn)程物理地址空間可以不連續(xù)；將內(nèi)存物理空間劃分成固定大小的塊 (大小通常為2的若干次冪，如 512B，4096B)，稱為頁框。將邏輯空間分成與物理塊同樣大小的頁（pages）。系統(tǒng)建立一張空閑頁框表，用以維護(hù)系統(tǒng)中的自由空間。當(dāng)需要執(zhí)行一個(gè)大小為 n 頁的進(jìn)程時(shí)，就在

11、內(nèi)存中尋找 n 自由頁框，并將進(jìn)程裝入其中。為進(jìn)程設(shè)置一張頁表，記錄頁編號和頁框編號的對應(yīng)關(guān)系。實(shí)現(xiàn)邏輯地址向物理地址的轉(zhuǎn)換。 (2)分頁存儲管理頁表3 非連續(xù)分配管理方式Page 3Page 2Page 1Page 0Page 0Page 3Page 1Page 2邏輯地址空間物理內(nèi)存空間頁框號0123456710734塊號321頁號頁表頁內(nèi)碎片0123頁號 (2)分頁存儲管理地址結(jié)構(gòu)及頁表3 非連續(xù)分配管理方式CPU生成的邏輯地址被自動分成:頁號 (p) 用作訪問頁表的索引，頁表內(nèi)保存每頁在內(nèi)存中的物理地址（塊號）頁內(nèi)偏移量 (w) 與物理塊號一同構(gòu)成實(shí)際的內(nèi)存物理地址。頁號頁內(nèi)偏移量pw

12、021426頁號 塊號 012m作業(yè)的地址空間 .0123456內(nèi)存空間頁表 (2)分頁存儲管理-地址變換機(jī)構(gòu)3 非連續(xù)分配管理方式為了能將用戶地址空間中的邏輯地址變換為內(nèi)存空間中的物理地址，在系統(tǒng)中必須設(shè)置地址變換機(jī)構(gòu)。地址變換結(jié)構(gòu)的基本任務(wù)為：實(shí)現(xiàn)邏輯地址向物理地址的轉(zhuǎn)換（頁號-頁框號）。地址變換借助頁表來完成。 (2)分頁存儲管理-存在的問題3 非連續(xù)分配管理方式采用純分頁內(nèi)存分配方式， CPU每存取一個(gè)指令/數(shù)據(jù)時(shí)，需要兩次訪問內(nèi)存，一次訪問頁表，一次物理地址存取數(shù)據(jù)。引入一種能快速搜索的高速緩沖存儲器-快表?？毂恚阂环N特殊高速緩沖存儲器；內(nèi)容-為頁表中的一部分或全部。 CPU產(chǎn)生的邏

13、輯地址的頁首先在快表中尋找，若找到（命中），就找出其對應(yīng)的物理塊；若未找到（未命中），再到頁表中找其對應(yīng)的物理塊，并將之復(fù)制到快表。 若快表中內(nèi)容滿，則按某種算法淘汰某些頁。 (2)分頁存儲管理-快表3 非連續(xù)分配管理方式有些處理器設(shè)計(jì)為快表和主存同時(shí)查找，如果快表命中，則主存查找終止。一般塊表的命中率達(dá)90%以上。 (3)段式存儲管理3 非連續(xù)分配管理方式引入分段存儲管理方式， 主要是為了滿足用戶和程序員。程序是程序段的集合：程序段可以是：main program, procedure/ method, object等。因此進(jìn)程地址形成了一個(gè)二維空間，段名和段內(nèi)偏移量。分段的優(yōu)點(diǎn)：方便編程：

14、按邏輯關(guān)系分為若干個(gè)段，每個(gè)段從0編址，并有名字和長度，訪問的邏輯地址由段名和段內(nèi)偏移量決定。信息共享和保護(hù)：共享和保護(hù)是以信息為邏輯單位，頁是存儲信息的物理單位，段卻是信息的邏輯單位。動態(tài)增長：實(shí)際應(yīng)用中，某些段（數(shù)據(jù)段）會不斷增長，前面的存儲管理方法均難以實(shí)現(xiàn)。 (3)段式存儲管理地址結(jié)構(gòu)及段表3 非連續(xù)分配管理方式每個(gè)進(jìn)程都有一張邏輯空間與主存空間映射的段表。段表項(xiàng)記錄該段在主存中的起始地址和段的長度。段號段內(nèi)偏移量sw (3)段式存儲管理-地址變換機(jī)構(gòu)3 非連續(xù)分配管理方式為了能將用戶地址空間中的邏輯地址變換為內(nèi)存空間中的物理地址，在系統(tǒng)中必須設(shè)置地址變換機(jī)構(gòu)。 (4)段頁式存儲管理3

15、 非連續(xù)分配管理方式段頁式存儲管理是分段和分頁原理的結(jié)合，即先將用戶程序分成若干個(gè)段（段式），并為每一個(gè)段賦一個(gè)段名，再把每個(gè)段分成若干個(gè)頁（頁式）。其地址結(jié)構(gòu)由段號、段內(nèi)頁號、及頁內(nèi)位移三部分所組成。主程序段數(shù)據(jù)段子程序段04k8k12k16k04k8k04k8k12k用戶程序段號段內(nèi)頁號頁內(nèi)位移段表大小段表始址段表寄存器1403121110頁表始址狀態(tài)頁表大小段號1403121110狀態(tài)存儲塊#頁號操作系統(tǒng)段 表頁 表內(nèi) 存 (4)段頁式存儲管理-地址映射3 非連續(xù)分配管理方式 (1)基本概念4 虛擬內(nèi)存管理傳統(tǒng)存儲管理方式的特征：一次性（ 作業(yè)一次性全部裝入內(nèi)存后，才能運(yùn)行。作業(yè)很大，作

16、業(yè)很多？）；駐留性（運(yùn)行完之前，作業(yè)任何部分都不能換出）。Bill Joy（sun CEO）說：“在研究所時(shí)，我經(jīng)常開玩笑說高速緩存是計(jì)算機(jī)科學(xué)中唯一重要的思想?！?廣義來說，快表、頁高速緩存、虛擬內(nèi)存技術(shù)都屬于高速緩存技術(shù)。高速緩存技術(shù)都依賴于局部性原理。時(shí)間局限性。如果程序中的某條指令一旦執(zhí)行， 則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪問過， 則不久以后該數(shù)據(jù)可能再次被訪問。空間局限性。一旦程序訪問了某個(gè)存儲單元，在不久之后，其附近的存儲單元也將被訪問。 (1)基本概念4 虛擬內(nèi)存管理基于局部性原理，程序在運(yùn)行之前，沒有必要全部裝入內(nèi)存，僅須將當(dāng)前要運(yùn)行的頁（段）裝入內(nèi)存即可。運(yùn)行時(shí)，

17、如訪問的頁（段）在內(nèi)存中，則繼續(xù)執(zhí)行，如訪問的頁未在內(nèi)存中（缺頁或缺段），則利用OS的請求調(diào)頁（段）功能，將該頁（段）調(diào)入內(nèi)存。 如內(nèi)存已滿，則利用OS的頁（段）置換功能，按某種置換算法將內(nèi)存中的某頁（段）調(diào)至外存，從而調(diào)入需訪問的頁。 虛擬存儲的實(shí)現(xiàn)技術(shù)：請求分頁（Demand paging） 請求分段（Demand segmentation） (1)基本概念4 虛擬內(nèi)存管理虛擬存儲器是指僅把作業(yè)的一部分裝入內(nèi)存便可運(yùn)行作業(yè)的存儲管理系統(tǒng)，它具有請求調(diào)入功能和部分置換功能，能從邏輯上對內(nèi)存容量進(jìn)行擴(kuò)充，其邏輯容量由外存容量和內(nèi)存容量之和決定，其運(yùn)行速度接近于內(nèi)存，成本接近于外存。 (2)請求

18、分頁管理4 虛擬內(nèi)存管理分頁請求系統(tǒng)在分頁系統(tǒng)的基礎(chǔ)上，增加了請求調(diào)頁功能、頁面置換功能所形成的頁式虛擬存儲器系統(tǒng)。允許只裝入若干頁的用戶程序和數(shù)據(jù)，便可啟動運(yùn)行，以后在硬件支持下通過調(diào)頁功能和置換頁功能，陸續(xù)將要運(yùn)行的頁面調(diào)入內(nèi)存，同時(shí)把暫不運(yùn)行的頁面換到外存上，置換時(shí)以頁面為單位。 系統(tǒng)須設(shè)置相應(yīng)的硬件支持和軟件：硬件支持：請求分頁的頁表機(jī)制、缺頁中斷機(jī)構(gòu)和地址變換機(jī)構(gòu)。軟件：請求調(diào)頁功能和頁置換功能的軟件。 (2)請求分頁管理請求分頁的頁表機(jī)制4 虛擬內(nèi)存管理 （1）狀態(tài)位P：指示該頁是否已調(diào)入內(nèi)存。 （2）訪問字段A：記錄本頁在一段時(shí)間內(nèi)被訪問的次數(shù)或最近未被訪問的時(shí)間。 （3）修改位

19、M：表示該頁在調(diào)入內(nèi)存后是否被修改過。若修改過，則換出時(shí)需重寫至外存。 （4）外存地址：指出該頁在外存上的地址。頁號塊號狀態(tài)位訪問字段修改位外存地址 (2)請求分頁管理缺頁中斷機(jī)構(gòu)4 虛擬內(nèi)存管理在請求分頁系統(tǒng)中，當(dāng)訪問的頁不在內(nèi)存，便產(chǎn)生一缺頁中斷，請求OS將所缺頁調(diào)入內(nèi)存空閑塊，若無空閑塊，則需置換某一頁，同時(shí)修改相應(yīng)頁表表目。缺頁中斷與一般中斷的區(qū)別：（1）在指令執(zhí)行期間產(chǎn)生和處理中斷信號（2）一條指令在執(zhí)行期間，可能產(chǎn)生多次缺頁中斷邏輯地址空間主存(用戶區(qū))CPU邏輯地址快表主存(系統(tǒng)區(qū))運(yùn)行進(jìn)程頁表輔存缺頁中斷處理分解地址訪問MMU查快表命中不命中頁表命中發(fā)缺頁中斷調(diào)頁裝入、改表查頁

20、表運(yùn)行進(jìn)程頁表基址裝入快表運(yùn)行進(jìn)程映象進(jìn)程切換時(shí)裝入物理地址頁框 頁內(nèi)地址頁號 頁內(nèi)地址開始頁號頁表長度？CPU檢索快表NNY頁表項(xiàng)在快表中？訪問頁表頁在內(nèi)存？修改訪問位和修改位修改頁表形成物理地址地址變換結(jié)束越界中斷程序請求訪問一頁YN缺頁中斷處理Y保留CPU現(xiàn)場內(nèi)存滿嗎？將一頁從外存換入內(nèi)存OS命令CPU從外存讀缺頁啟動I/O硬件Y從外存中找到缺頁選擇一頁換出該頁被修改否？將該頁寫回外存修改頁表NYN (2)請求分頁管理頁面置換算法4 虛擬內(nèi)存管理實(shí)施頁面置換 按照某種策略從內(nèi)存中尋找某頁，將其換出，以騰出空間裝入請求頁面。希望得到一個(gè)算法，能保證系統(tǒng)的缺頁率最低。剛被淘汰出內(nèi)存的頁面，過后不久又要訪問它，需要再次將其調(diào)入，而該頁調(diào)入內(nèi)存后不入又再次被淘汰出內(nèi)存，然后又要訪問它，如此反復(fù)，使得系統(tǒng)把大部分時(shí)間用在了頁面的調(diào)進(jìn)換出上，而幾乎不能完成任何有效的工作，這種現(xiàn)象稱為抖動（又稱顛簸）。利用修改位 （