四、存儲管理

存儲管理為了確保計算機有足夠的內存處理數據；確保程序可以從可用內存中獲取一部分內存使用；確保程序可以歸還使用后的內存以供其他程序使用。

4.1 存儲管理之內存分配與回收

內存分配的過程：單一連續分配（已經過時）、固定分區分配、動態分區分配（根據實際需要，動態的分配內存）。 動態分區分配算法：

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

內存回收的過程：

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

4.2 存儲管理之段頁式存儲管理

頁式存儲管理：將進程邏輯空間等分成若干大小的頁面，相應的把物理內存空間分成與頁面大小的物理塊，以頁面為單位把進程空間裝進物理內存中分散的物理塊。

頁面大小應該適中，過大難以分配，過小內存碎片過多；頁面大小通常是512B~8K；

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

段式存儲管理：將進程邏輯空間分成若干段（不等分），段的長度由連續邏輯的長度決定。

頁式和者段式存儲管理相比：

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

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

4.3 存儲管理之虛擬內存

虛擬內存概述：是操作系統內存管理的關鍵技術，使得多道程序運行和大程序運行成為現實，把程序使用內存劃分，將部分暫時不使用的內存放置在輔存，實際是對物理內存的擴充。

局部性原理：指CPU訪問存儲器時，無論是存取指令還是存取數據，所訪問的存儲單元都趨于聚集在一個較小的連續區域中。

虛擬內存的置換算法：先進先出（FIFO）、最不經常使用（LFU）、最近最少使用（LRU）

虛擬內存的特征：

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

4.4 Linux的存儲管理

Buddy內存管理算法：經典的內存管理算法，為解決內存外碎片的問題，算法基于計算機處理二進制的優勢具有極高的效率。

Linux交換空間：交換空間（Swap）是磁盤的一個分區，Linux內存滿時，會把一些內存交換至Swap空間，Swap空間是初始化系統時配置的。

Swap空間與虛擬內存的對比：

五、文件管理

5.1 操作系統的文件管理

文件的邏輯結構：

• 邏輯結構的文件類型：有結構文件（文本文件，文檔，媒體文件）、無結構文件（二進制文件、鏈接庫）。
• 順序文件：按順序放在存儲介質中的文件，在邏輯文件當中存儲效率最高，但不適合存儲可變長文件。
• 索引文件：為解決可變長文件存儲而發明，需要配合索引表存儲。

輔存的存儲空間分配：

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

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

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

Linux的文件系統：FAT、NTFS（對FAT進行改進）、EXT2/3/4（擴展文件系統，Linux的文件系統）

六、設備管理

I/O設備的基本概念：將數據輸入輸出計算機的外部設備；

廣義的IO設備：

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

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

SPOOLing技術：虛擬設備技術，把同步調用低速設備改為異步調用，在輸入、輸出之間增加了排隊轉儲環節(輸入井、輸出井)，SPoOLing負責輸入（出）井與低速設備之間的調度，邏輯上，進程直接與高速設備交互，減少了進程的等待時間。

七、實現支持異步任務的線程池

線程池：線程池是存放多個線程的容器，CPU調度線程執行后不會銷毀線程，將線程放回線程池重新利用。

使用線程池的原因：

1. 線程是稀缺資源 ，不應該頻繁創建和銷毀；
2. 架構解耦，業務創建和業務處理解耦，更加優雅；
3. 線程池是使用線程的最佳實踐。

實現線程安全的隊列Queue

• 隊列：用于存放多個元素，是存放各種元素的“池”。
• 實現的基本功能：獲取當前隊列元素數量，往隊列放入元素，往隊列取出元素。
• 注意：隊列可能有多個線程同時操作，因此需要保證線程安全，如下兩種情況：

實現基本任務對象Task

實現的基本功能：任務參數，任務唯一標記（UUID），任務具體的執行邏輯

實現任務處理線程ProcessThread：任務處理線程需要不斷地從任務隊列里取任務執行，任務處理線程需要有一個標記，標記線程什么時候應該停止。

實現的基本功能：基本屬性（任務隊列、標記），線程執行的邏輯（run），線程停止（stop）。

實現任務處理線程池Pool：存放多個任務處理線程，負責多個線程的啟停，管理向線程池的提交任務，下發給線程去執行。

實現的基本過程：基本屬性，提交任務（put，batch_put），線程啟停（start，join），線程池大小（size）。

實現異步任務處理AsyncTask：給任務添加一個標記，任務完成后，則標記為完成；任務完成時可直接獲取任務運行結果；任務未完成時，獲取任務結果，會阻塞獲取線程。

主要實現的兩個函數：設置運行結果（set_result），獲取運行結果（get_result)