四、存儲(chǔ)管理

存儲(chǔ)管理為了確保計(jì)算機(jī)有足夠的內(nèi)存處理數(shù)據(jù)；確保程序可以從可用內(nèi)存中獲取一部分內(nèi)存使用；確保程序可以歸還使用后的內(nèi)存以供其他程序使用。

4.1 存儲(chǔ)管理之內(nèi)存分配與回收

內(nèi)存分配的過程：單一連續(xù)分配（已經(jīng)過時(shí)）、固定分區(qū)分配、動(dòng)態(tài)分區(qū)分配（根據(jù)實(shí)際需要，動(dòng)態(tài)的分配內(nèi)存）。 動(dòng)態(tài)分區(qū)分配算法：

1. 首次適應(yīng)算法：分配內(nèi)存時(shí)，從開始順序查找適合內(nèi)存區(qū)，若無合適內(nèi)存區(qū)，則分配失敗，每次從頭部開始，使得頭部地址空間不斷被劃分；
2. 最佳適應(yīng)算法：要求空閑區(qū)鏈表按照容量大小排序，遍歷以找到最佳適合的空閑區(qū)（會(huì)留下越來越多的內(nèi)部碎片）。
3. 快速適應(yīng)算法：要求有多個(gè)空閑區(qū)鏈表，每個(gè)空閑區(qū)鏈表存儲(chǔ)一種容量的空閑區(qū)。

內(nèi)存回收的過程：

1. 回收區(qū)在空閑區(qū)下方：不需要新建空閑鏈表節(jié)點(diǎn)；只需要把空閑區(qū)1的容量增大即可；
2. 回收區(qū)在空閑區(qū)上方：將回收區(qū)與空閑區(qū)合并；新的空閑區(qū)使用回收區(qū)的地址；
3. 回收區(qū)在空閑區(qū)中間方：將空閑區(qū)1、空閑區(qū)2和回收區(qū)合并；新的空閑區(qū)使用空閑區(qū)1的地址；
4. 僅僅剩余回收區(qū)：為回收區(qū)創(chuàng)建新的空閑節(jié)點(diǎn)；插入到相應(yīng)的空閑區(qū)鏈表中去；

4.2 存儲(chǔ)管理之段頁式存儲(chǔ)管理

頁式存儲(chǔ)管理：將進(jìn)程邏輯空間等分成若干大小的頁面，相應(yīng)的把物理內(nèi)存空間分成與頁面大小的物理塊，以頁面為單位把進(jìn)程空間裝進(jìn)物理內(nèi)存中分散的物理塊。

頁面大小應(yīng)該適中，過大難以分配，過小內(nèi)存碎片過多；頁面大小通常是512B~8K；

現(xiàn)代計(jì)算機(jī)系統(tǒng)中，可以支持非常大的邏輯地址空間(232~264)，具有32位邏輯地址空間的分頁系統(tǒng)，規(guī)定頁面大小為4KB，則在每個(gè)進(jìn)程頁表中的頁表項(xiàng)可達(dá)1M(2個(gè)20)個(gè)，如果每個(gè)頁表項(xiàng)占用1Byte，故每個(gè)進(jìn)程僅僅頁表就要占用1MB的內(nèi)存空間。

段式存儲(chǔ)管理：將進(jìn)程邏輯空間分成若干段（不等分），段的長度由連續(xù)邏輯的長度決定。

頁式和者段式存儲(chǔ)管理相比：

1. 段式存儲(chǔ)和頁式存儲(chǔ)都離散地管理了進(jìn)程的邏輯空間；
2. 頁是物理單位，段是邏輯單位；
3. 分頁是為了合理利用空間，分段是滿足用戶要求頁大小由硬件固定，段長度可動(dòng)態(tài)變化；
4. 頁表信息是一維的，段表信息是二維的；

段頁式存儲(chǔ)管理：現(xiàn)將邏輯空間按照段式管理分成若干段，再將內(nèi)存空間按照頁式管理分成若干頁，分頁可以有效提高內(nèi)存利用率，分段可以更好的滿足用戶需求。

4.3 存儲(chǔ)管理之虛擬內(nèi)存

虛擬內(nèi)存概述：是操作系統(tǒng)內(nèi)存管理的關(guān)鍵技術(shù)，使得多道程序運(yùn)行和大程序運(yùn)行成為現(xiàn)實(shí)，把程序使用內(nèi)存劃分，將部分暫時(shí)不使用的內(nèi)存放置在輔存，實(shí)際是對物理內(nèi)存的擴(kuò)充。

局部性原理：指CPU訪問存儲(chǔ)器時(shí)，無論是存取指令還是存取數(shù)據(jù)，所訪問的存儲(chǔ)單元都趨于聚集在一個(gè)較小的連續(xù)區(qū)域中。

虛擬內(nèi)存的置換算法：先進(jìn)先出（FIFO）、最不經(jīng)常使用（LFU）、最近最少使用（LRU）

虛擬內(nèi)存的特征：

• 多次性：無需再作業(yè)運(yùn)行時(shí)一次性全部裝入內(nèi)存，而是允許被分成多次調(diào)入內(nèi)存；
• 對換性：無需在作業(yè)運(yùn)行時(shí)一直常駐內(nèi)存，而是允許在作業(yè)運(yùn)行過程中，將作業(yè)換入、換出；
• 虛擬性：從邏輯上擴(kuò)充了內(nèi)存的容量，使用戶看到的內(nèi)存用來，遠(yuǎn)大于實(shí)際的容量；

4.4 Linux的存儲(chǔ)管理

Buddy內(nèi)存管理算法：經(jīng)典的內(nèi)存管理算法，為解決內(nèi)存外碎片的問題，算法基于計(jì)算機(jī)處理二進(jìn)制的優(yōu)勢具有極高的效率。

Linux交換空間：交換空間（Swap）是磁盤的一個(gè)分區(qū)，Linux內(nèi)存滿時(shí)，會(huì)把一些內(nèi)存交換至Swap空間，Swap空間是初始化系統(tǒng)時(shí)配置的。

Swap空間與虛擬內(nèi)存的對比：

五、文件管理

5.1 操作系統(tǒng)的文件管理

文件的邏輯結(jié)構(gòu)：

• 邏輯結(jié)構(gòu)的文件類型：有結(jié)構(gòu)文件（文本文件，文檔，媒體文件）、無結(jié)構(gòu)文件（二進(jìn)制文件、鏈接庫）。
• 順序文件：按順序放在存儲(chǔ)介質(zhì)中的文件，在邏輯文件當(dāng)中存儲(chǔ)效率最高，但不適合存儲(chǔ)可變長文件。
• 索引文件：為解決可變長文件存儲(chǔ)而發(fā)明，需要配合索引表存儲(chǔ)。

輔存的存儲(chǔ)空間分配：

• 輔存的分配方式：連續(xù)分配（讀取文件容易，速度快）、鏈接分配（隱式鏈接和顯式鏈接）、索引分配
• 輔存的存儲(chǔ)空間管理：空閑表、空閑鏈表、位示圖。

目錄樹：使得任何文件或目錄都有唯一的路徑。

Linux文件的基本操作：參考鏈接

Linux的文件系統(tǒng)：FAT、NTFS（對FAT進(jìn)行改進(jìn)）、EXT2/3/4（擴(kuò)展文件系統(tǒng)，Linux的文件系統(tǒng)）

六、設(shè)備管理

I/O設(shè)備的基本概念：將數(shù)據(jù)輸入輸出計(jì)算機(jī)的外部設(shè)備；

廣義的IO設(shè)備：

• 按照使用特性分類：存儲(chǔ)設(shè)備（內(nèi)存、磁盤、U盤）和交互IO設(shè)備（鍵盤、顯示器、鼠標(biāo)）；
• 按照信息交換分類：塊設(shè)備（磁盤、SD卡）和字符設(shè)備（打印機(jī)、shell終端）；
• 按照設(shè)備共享屬性分類：獨(dú)占設(shè)備，共享設(shè)備，虛擬設(shè)備；
• 按照傳輸速率分類：低速設(shè)備，高速設(shè)備；

IO設(shè)備的緩沖區(qū)：減少CPU處理IO請求的頻率，提高CPU與IO設(shè)備之間的并行性。

SPOOLing技術(shù)：虛擬設(shè)備技術(shù)，把同步調(diào)用低速設(shè)備改為異步調(diào)用，在輸入、輸出之間增加了排隊(duì)轉(zhuǎn)儲(chǔ)環(huán)節(jié)(輸入井、輸出井)，SPoOLing負(fù)責(zé)輸入（出）井與低速設(shè)備之間的調(diào)度，邏輯上，進(jìn)程直接與高速設(shè)備交互，減少了進(jìn)程的等待時(shí)間。

七、實(shí)現(xiàn)支持異步任務(wù)的線程池

線程池：線程池是存放多個(gè)線程的容器，CPU調(diào)度線程執(zhí)行后不會(huì)銷毀線程，將線程放回線程池重新利用。

使用線程池的原因：

1. 線程是稀缺資源 ，不應(yīng)該頻繁創(chuàng)建和銷毀；
2. 架構(gòu)解耦，業(yè)務(wù)創(chuàng)建和業(yè)務(wù)處理解耦，更加優(yōu)雅；
3. 線程池是使用線程的最佳實(shí)踐。

實(shí)現(xiàn)線程安全的隊(duì)列Queue

• 隊(duì)列：用于存放多個(gè)元素，是存放各種元素的“池”。
• 實(shí)現(xiàn)的基本功能：獲取當(dāng)前隊(duì)列元素?cái)?shù)量，往隊(duì)列放入元素，往隊(duì)列取出元素。
• 注意：隊(duì)列可能有多個(gè)線程同時(shí)操作，因此需要保證線程安全，如下兩種情況：

實(shí)現(xiàn)基本任務(wù)對象Task

實(shí)現(xiàn)的基本功能：任務(wù)參數(shù)，任務(wù)唯一標(biāo)記（UUID），任務(wù)具體的執(zhí)行邏輯

實(shí)現(xiàn)任務(wù)處理線程ProcessThread：任務(wù)處理線程需要不斷地從任務(wù)隊(duì)列里取任務(wù)執(zhí)行，任務(wù)處理線程需要有一個(gè)標(biāo)記，標(biāo)記線程什么時(shí)候應(yīng)該停止。

實(shí)現(xiàn)的基本功能：基本屬性（任務(wù)隊(duì)列、標(biāo)記），線程執(zhí)行的邏輯（run），線程停止（stop）。

實(shí)現(xiàn)任務(wù)處理線程池Pool：存放多個(gè)任務(wù)處理線程，負(fù)責(zé)多個(gè)線程的啟停，管理向線程池的提交任務(wù)，下發(fā)給線程去執(zhí)行。

實(shí)現(xiàn)的基本過程：基本屬性，提交任務(wù)（put，batch_put），線程啟停（start，join），線程池大?。╯ize）。

實(shí)現(xiàn)異步任務(wù)處理AsyncTask：給任務(wù)添加一個(gè)標(biāo)記，任務(wù)完成后，則標(biāo)記為完成；任務(wù)完成時(shí)可直接獲取任務(wù)運(yùn)行結(jié)果；任務(wù)未完成時(shí)，獲取任務(wù)結(jié)果，會(huì)阻塞獲取線程。

主要實(shí)現(xiàn)的兩個(gè)函數(shù)：設(shè)置運(yùn)行結(jié)果（set_result），獲取運(yùn)行結(jié)果（get_result)