存儲(chǔ)器管理

存儲(chǔ)器的層次結(jié)構(gòu)

• 存儲(chǔ)器的層次結(jié)構(gòu)：寄存器-高速緩存-主存-磁盤緩存-磁盤-可移動(dòng)存儲(chǔ)介質(zhì)
• 可執(zhí)行存儲(chǔ)器：寄存器和主存：存放于其中的數(shù)據(jù)只需要load或者store指令即可或者
• 對(duì)于輔存的訪問需要I/O設(shè)備的參與，將涉及到中斷、設(shè)備驅(qū)動(dòng)、以及物理設(shè)備的運(yùn)行，消耗時(shí)間比較多
• 存儲(chǔ)器管理主要負(fù)責(zé)對(duì)可執(zhí)行存儲(chǔ)器的分配、回收以及提供在存儲(chǔ)器層次間數(shù)據(jù)移動(dòng)的管理機(jī)制
• 主存儲(chǔ)器：用于保存運(yùn)行時(shí)的程序和數(shù)據(jù)，CPU控制部件只能從主存儲(chǔ)器中取得指令和數(shù)據(jù)，數(shù)據(jù)能夠從主存儲(chǔ)器讀取并且裝入到寄存器中，或者從寄存器存入到主存儲(chǔ)器
• 寄存器：寄存器訪問速度最快，與CPU接近，用于加速存儲(chǔ)器的訪問速度：如通用寄存器存放操作數(shù)，或者用地址轉(zhuǎn)換寄存器加快地址轉(zhuǎn)換速度等
• 高速緩存：容量遠(yuǎn)大于寄存器，但比內(nèi)存小兩到三個(gè)寄存器，根據(jù)局部性原理，將主存中經(jīng)常訪問到的信息存放在高速緩存中，用于減少對(duì)主存的訪問次數(shù)
• 磁盤緩存：I/O的速度遠(yuǎn)低于主存的訪問速度，所以經(jīng)常將一部分頻繁使用的磁盤數(shù)據(jù)存放在磁盤緩沖中，可以減少磁盤的訪問次數(shù)，利用主存中的存儲(chǔ)空間，來暫時(shí)存放從磁盤中讀取的數(shù)據(jù)(也可以說主存就是輔存的高速緩存)

程序的裝入和鏈接

• 程序的裝入

  • 絕對(duì)裝入方式
    • 編譯時(shí)，直接產(chǎn)生絕對(duì)地址，絕對(duì)裝入程序按照裝入模塊中的地址，將程序和數(shù)據(jù)進(jìn)行裝入，裝入后，程序中的邏輯地址與實(shí)際內(nèi)存地址完全相同
    • 只能將目標(biāo)模塊裝入到內(nèi)存中事先指定的位置，只適用于單道程序環(huán)境
  • 可重定位裝入方式
    • 多道程序環(huán)境中，所得到的目標(biāo)模塊的起始地址通常是從0開始，裝入內(nèi)存時(shí)，所有地址需要根據(jù)程序裝入的首地址進(jìn)行重新修改，由于地址是在裝入時(shí)一次性完成的，以后不再改變，故也稱為靜態(tài)重定位方式
    • 不允許在運(yùn)行時(shí)在內(nèi)存中移動(dòng)位置(此時(shí)的所有地址已經(jīng)轉(zhuǎn)化為絕對(duì)地址了)
  • 動(dòng)態(tài)運(yùn)行時(shí)裝入方式
    • 將裝入模塊裝入內(nèi)存后，并不直接將相對(duì)地址轉(zhuǎn)化為絕對(duì)地址，而是將地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時(shí)才進(jìn)行，所以，裝入后的地址依舊是相對(duì)地址，但需要提供一個(gè)重定位寄存器，用于加快地址轉(zhuǎn)換的速度

• 程序的鏈接

  • 靜態(tài)鏈接
    • 程序運(yùn)行之前，將各個(gè)目標(biāo)模塊以及它們所需要的庫函數(shù)，鏈接成一個(gè)完整的裝配模塊，以后不再拆開
  • 裝入時(shí)動(dòng)態(tài)鏈接
    • 裝入內(nèi)存時(shí)，邊裝入邊鏈接
  • 運(yùn)行時(shí)動(dòng)態(tài)鏈接
    • 運(yùn)行時(shí)需要該模塊，再進(jìn)行鏈接

連續(xù)分配方式

• 連續(xù)分配方式：為一個(gè)用戶分配一個(gè)連續(xù)的內(nèi)存空間

  • 單一連續(xù)分配

    • 只能用于單用戶、單任務(wù)的操作系統(tǒng)中
    • 把內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)

  • 固定分區(qū)分配

    • 最簡單的可運(yùn)行于多道程序的內(nèi)存管理方式，將內(nèi)存用戶空間劃分為若干個(gè)固定大小的區(qū)域，每個(gè)分區(qū)中只能裝入一道作業(yè)
    • 適用于控制多個(gè)相同對(duì)象的控制系統(tǒng)中
    • 劃分分區(qū)的方法
      • 分區(qū)大小相等
        • 所有的內(nèi)存分區(qū)大小相等
        • 缺乏靈活性
      • 分區(qū)大小不等
        • 將內(nèi)存分區(qū)劃分為多個(gè)較小分區(qū)、適量的中等分區(qū)以及少量的大分區(qū)
    • 內(nèi)存分配
      • 將分區(qū)按大小進(jìn)行排隊(duì)，并為之建立一張分區(qū)使用表，各表項(xiàng)包括：每個(gè)分區(qū)的起始地址、大小以及狀態(tài)，分配時(shí)掃描該表，找到滿足對(duì)應(yīng)項(xiàng)則進(jìn)行分配

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

    • 根據(jù)進(jìn)程的實(shí)際需要，動(dòng)態(tài)為其分配內(nèi)存空間
    • 分區(qū)分配中的數(shù)據(jù)結(jié)構(gòu)
      • 空閑分區(qū)表：系統(tǒng)中設(shè)置一張空閑分區(qū)表，用于記錄每個(gè)分區(qū)的使用情況，每個(gè)分區(qū)占一個(gè)表項(xiàng)，包括：分區(qū)序號(hào)，分區(qū)起始地址，分區(qū)的大小等數(shù)據(jù)項(xiàng)
      • 空閑分區(qū)鏈
    • 分區(qū)分配算法
      • 首次適應(yīng)算法(FF)
        • 要求空閑分區(qū)鏈按照地址遞增的次序鏈接，分配內(nèi)存時(shí)，從鏈?zhǔn)组_始順序查找，直到找到滿足為止
      • 循環(huán)首次適應(yīng)算法(next fit)
        • 分配空間時(shí)，從上一次找到的空閑分區(qū)的下一空閑分區(qū)開始查找，直到找到一個(gè)滿足要求的空閑分區(qū)
      • 最佳適應(yīng)算法(best fit)
        • 將所有空閑分區(qū)按照其容量從小到大的順序形成一空閑分區(qū)鏈，找到大小剛剛好的分區(qū)進(jìn)分配
      • 最壞適應(yīng)算法(worst fit)
        • 掃描整個(gè)分區(qū)表，挑選最大一個(gè)空閑分區(qū)進(jìn)行分配
      • 快速適應(yīng)算法(quick fit)
        • 將空閑分區(qū)根據(jù)其容量的大小進(jìn)行分類，對(duì)每一類具有相同容量的所有空閑分區(qū)，單獨(dú)設(shè)置一個(gè)空閑分區(qū)鏈表，同時(shí)設(shè)置一張管理索引表，每一個(gè)表項(xiàng)對(duì)應(yīng)一個(gè)空閑分區(qū)鏈
    • 分區(qū)分配操作
      • 分配內(nèi)存
        從空閑分區(qū)表中查找分區(qū)，如果滿足，則將其分配出去(如果剩余大小小于預(yù)定大小，則直接分配，而不分割該分區(qū)，否則，分割該分區(qū))
      • 回收內(nèi)存
        • 如果插入點(diǎn)與回收分區(qū)相鄰，則將其合并即可
        • 如果不相鄰，則在空閑鏈中新建項(xiàng)，并且填寫相關(guān)信息
    • 伙伴系統(tǒng)
      • 無論已經(jīng)分配的分區(qū)還是空閑分區(qū)，其大小均為2的k次冪( 1 <= k <= m ,其中1表示最小分配，m表示最大分配，通常m為整個(gè)可分配內(nèi)存空間的大小)，將空閑分區(qū)根據(jù)分區(qū)大小進(jìn)行分類，對(duì)于每一類具有相同大小的所有空閑分區(qū)，單獨(dú)設(shè)置一個(gè)空閑分區(qū)雙向鏈表，這樣，空閑分區(qū)形成k個(gè)空閑分區(qū)鏈表
      • 當(dāng)需要分配大小為n是，先計(jì)算2^(i-1) <= n <= 2^i，然后在i鏈表里查找，找到則分配，找不到則在i+1鏈表中查找，并且現(xiàn)將i+1分區(qū)分為兩個(gè)大小i的分區(qū)，一個(gè)用于分配，一個(gè)用于加入i鏈表
      • 回收時(shí)也需要多次合并，如果存在i，則將其余回收的i合并到i+1中

  • 動(dòng)態(tài)重定位分區(qū)分配

    • 緊湊/拼接：通過移動(dòng)內(nèi)存那種作業(yè)的位置，把原來多個(gè)分散的小分區(qū)拼接成一個(gè)大分區(qū)的方式，每次緊湊之后，都需要對(duì)移動(dòng)了的程序或者數(shù)據(jù)進(jìn)行重定位

  • 對(duì)換：把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù)調(diào)出到外存上，以便騰出足夠的內(nèi)存空間，再把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù)調(diào)入內(nèi)存

    • 整體對(duì)換/進(jìn)程對(duì)換
    • 頁面對(duì)換/分段對(duì)換
    • 對(duì)換空間的管理
      • 把外存分為文件區(qū)(離散分配)和對(duì)換區(qū)(連續(xù)分配)，前者用于存放文件，后者用于存放從內(nèi)存中換出的進(jìn)程
      • 系統(tǒng)應(yīng)該配置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，用于記錄外存的使用情況：空閑分區(qū)表/空閑分區(qū)鏈，保存兩項(xiàng)內(nèi)容：對(duì)換區(qū)的首址(盤塊號(hào))及大小(盤塊數(shù))
    • 進(jìn)程的換出與換入
      • 進(jìn)程的換出：選擇處于阻塞態(tài)且優(yōu)先級(jí)最低的進(jìn)程作為換出進(jìn)程，然后啟動(dòng)磁盤，將該進(jìn)程的程序和數(shù)據(jù)傳送到磁盤的對(duì)換分區(qū)上，如果傳送過程未出錯(cuò)，則回收該進(jìn)程所占空間，并且對(duì)該進(jìn)程的進(jìn)程控制塊做出相應(yīng)的修改
      • 進(jìn)程的換入：系統(tǒng)應(yīng)該定時(shí)查看所有進(jìn)程的狀態(tài)，從中找出就緒狀態(tài)但已換出的進(jìn)程，將其中換出時(shí)間最長的進(jìn)程換入內(nèi)存

基本的分頁存儲(chǔ)管理方式

頁面和頁表

• 頁面
  • 頁面和物理塊
    • 分頁存儲(chǔ)管理是將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片，稱之為頁面或者頁，并且為各頁編號(hào)，相應(yīng)的，也把內(nèi)存空間分成與頁面大小相同的若干個(gè)存儲(chǔ)塊，稱之為物理塊或者頁框，同樣為其編號(hào)，為進(jìn)程分配內(nèi)存時(shí)，以塊為單位將進(jìn)程中的若干頁分別裝入到多個(gè)可以不相鄰的物理塊中，由于進(jìn)程的最后一頁經(jīng)常裝不滿一塊而形成不可利用的碎片，稱之為頁內(nèi)碎片
    • 頁面大小：頁面大小應(yīng)該適中，且大小應(yīng)該是2的冪，通常是512B~8KB
• 地址結(jié)構(gòu)：分為兩個(gè)部分(頁號(hào)P以及位移量W(頁內(nèi)地址))
• 頁表：為了保證進(jìn)程能夠正確的運(yùn)行，也就是能在內(nèi)存中找到每個(gè)頁面所對(duì)應(yīng)的物理塊，系統(tǒng)需要為每個(gè)進(jìn)程建立一個(gè)頁表，記錄了進(jìn)程空間中所有頁以及其對(duì)應(yīng)的物理頁的情況

地址變換機(jī)構(gòu)

• 基本的地址變換機(jī)構(gòu)
  • 在系統(tǒng)中設(shè)置一個(gè)頁表寄存器，存放頁表在內(nèi)存中的起始地址和頁表的長度，未執(zhí)行時(shí)，該信息保存在PCB中，調(diào)度時(shí)，將其裝入頁表寄存器
  • 查找時(shí)，先根據(jù)邏輯地址以及頁表地址(頁表寄存器)得出對(duì)應(yīng)頁表項(xiàng)的地址，然后讀取其內(nèi)容，獲得對(duì)應(yīng)的物理塊，然后再通過計(jì)算，得到對(duì)應(yīng)的物理塊地址
• 具有快表的地址變換結(jié)構(gòu)
  • 快表TLB：用于存放當(dāng)前訪問的頁表項(xiàng)
  • 查找時(shí)，先看當(dāng)前快表中是否有該項(xiàng)，如果有，則直接使用該項(xiàng)，如果沒有，則按照前面內(nèi)容查找，然后將其緩存在快表中
• 兩級(jí)和多級(jí)頁表
  外層頁表中存放內(nèi)層頁表的物理地址，借助外層頁表寄存器即可讀出外層頁表的，然后計(jì)算得到內(nèi)層頁表，然后可以去取出對(duì)應(yīng)的物理塊地址

基本分段存儲(chǔ)管理方式

• 引入分段存儲(chǔ)管理方式的目的
  • 方便編程：將作業(yè)進(jìn)行分段，每個(gè)段都是從0開始，并且有自己的長度以及名字
  • 信息共享：段的共享
  • 信息保護(hù)
  • 動(dòng)態(tài)增長：段的長度可以自由變換
  • 動(dòng)態(tài)鏈接

分段系統(tǒng)的基本原理

• 段地址結(jié)構(gòu)：段號(hào) 段內(nèi)地址
• 段表：系統(tǒng)為每個(gè)段分配一個(gè)連續(xù)的分區(qū)，而進(jìn)程中的各個(gè)段可以離散地移入不同的分區(qū)中

分段與分頁的區(qū)別

• 頁是信息的物理單位，分頁是為實(shí)現(xiàn)離散分配方式，以消減內(nèi)存的外零頭，提高內(nèi)存的利用率，分頁僅僅是系統(tǒng)管理的需要而不是用戶的需要，段是信息的邏輯單位，它含有一組意義相對(duì)完整的信息，分段的目的是為了更好地滿足用戶的需要
• 頁的大小固定且由系統(tǒng)決定，在系統(tǒng)中只能有一種大小的頁，段的長度是不確定的，主要取決于用戶的程序，通常由編譯程序在對(duì)源程序進(jìn)行編譯時(shí)，根據(jù)信息的性質(zhì)劃分

段頁式存儲(chǔ)管理

• 基本原理：分段和分頁的結(jié)合，先將程序進(jìn)行分段，再把每個(gè)段分成若干個(gè)頁，并為每個(gè)段賦予一個(gè)段名

虛擬存儲(chǔ)器的基本概念

常規(guī)存儲(chǔ)器管理的特征

• 一次性：要求將作業(yè)全部裝入內(nèi)存后才能運(yùn)行
• 駐留性：作業(yè)裝入內(nèi)存后，便一直駐留在內(nèi)存中，直至作業(yè)運(yùn)行結(jié)束

虛擬存儲(chǔ)器：具有請(qǐng)求調(diào)入和置換功能，能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng)，其邏輯容量由內(nèi)存容量和外存容量之和所確定，其運(yùn)行速度接近于內(nèi)存速度，而成本接近于外存。

虛擬存儲(chǔ)器的實(shí)現(xiàn)方法

• 分頁請(qǐng)求系統(tǒng)：在分頁系統(tǒng)上增加了請(qǐng)求調(diào)頁功能和頁面置換功能，陸續(xù)地把要運(yùn)行的頁面調(diào)入內(nèi)存，同時(shí)把暫時(shí)不用的頁面換到外存上，置換時(shí)可以以頁面為單位
  • 硬件支持
    • 請(qǐng)求分頁的頁表機(jī)制
    • 缺頁中斷機(jī)制
    • 地址變換機(jī)構(gòu)
  • 實(shí)現(xiàn)請(qǐng)求分頁的軟件
• 請(qǐng)求分段系統(tǒng)：以分段機(jī)制為基礎(chǔ)，置換時(shí)以段為單位
  • 硬件支持
    • 請(qǐng)求分段的段表機(jī)制
    • 段中斷機(jī)構(gòu)
    • 地址變換機(jī)構(gòu)

虛擬存儲(chǔ)器的特征

• 多次性：一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存
• 對(duì)換性：允許作業(yè)在運(yùn)行過程中進(jìn)行換進(jìn)換出
• 虛擬性：從邏輯上擴(kuò)充了內(nèi)存容量

請(qǐng)求分頁存儲(chǔ)管理方式

請(qǐng)求分頁的硬件支持

• 頁表機(jī)制：將用戶空間的邏輯地址變換為內(nèi)存空間中的物理地址，需要多記錄狀態(tài)位，訪問字段，修改位，外存地址
• 缺頁中斷機(jī)制：一條指令在執(zhí)行期間可能會(huì)發(fā)生多次缺頁中斷，系統(tǒng)必須保證能保持多次中斷的狀態(tài)，并且保證最后能返回到中斷前產(chǎn)生缺頁中斷的指令處繼續(xù)執(zhí)行
• 地址變換機(jī)構(gòu)

內(nèi)存分配策略和分配算法

• 最小物理塊的確定：保證進(jìn)程正常運(yùn)行所需的最小物理塊
• 物理塊的分配策略
  • 固定分配局部置換
  • 可變分配全局置換
  • 可變分配局部置換
• 物理塊的分配算法
  • 平均分配算法
  • 按比例分配算法
  • 考慮優(yōu)先權(quán)的分配算法

調(diào)頁策略

• 請(qǐng)求頁面的時(shí)機(jī)
  • 預(yù)調(diào)頁策略：預(yù)計(jì)在不久之后需要訪問的頁面預(yù)先調(diào)入內(nèi)存
  • 請(qǐng)求調(diào)頁策略：運(yùn)行時(shí)根據(jù)需要調(diào)入
• 確定從何處調(diào)入頁面
  • 系統(tǒng)擁有足夠的對(duì)換區(qū)空間，可以全部從對(duì)換區(qū)調(diào)入所需頁面(在運(yùn)行之前，須將有關(guān)的文件從文件區(qū)拷貝直對(duì)換區(qū))
  • 系統(tǒng)缺乏足夠的對(duì)換空間：凡是不會(huì)修改的文件從文件區(qū)調(diào)入，可能修改部分，須將其調(diào)入到對(duì)換區(qū)
  • Unix方式：與進(jìn)程有關(guān)的文件都放在文件區(qū)，凡是未運(yùn)行過的頁面，都應(yīng)該從文件區(qū)調(diào)入，對(duì)于運(yùn)行過但又被換出的頁面，存放在對(duì)換區(qū)
• 頁面調(diào)入過程
  • 未存在，則發(fā)出缺頁中斷，交給中斷處理程序處理，進(jìn)行調(diào)入，修改等操作

頁面置換算法

最佳優(yōu)先置換算法

最佳優(yōu)先置換算法是一種理想的算法，實(shí)際上很難實(shí)現(xiàn)，基本思想是：每次選擇以后不會(huì)再使用的頁面，或者是在最長未來時(shí)間內(nèi)不再被訪問的頁面進(jìn)行替換

先進(jìn)先出頁面置換算法

思想：淘汰最先進(jìn)入內(nèi)存的頁面，也就是選擇在內(nèi)存中駐留時(shí)間最久的頁面

最近最久未使用置換算法(LRU Least Recently Used)

思想：為每個(gè)頁面添加一個(gè)訪問字段，用來記錄一個(gè)頁面自上次被訪問以來所經(jīng)歷的時(shí)間t，當(dāng)淘汰一個(gè)頁面時(shí)，選擇現(xiàn)有頁面中其中t值最大的，即最近最久未使用的頁面進(jìn)行替換

需要硬件

• 寄存器：為每個(gè)頁面設(shè)置一個(gè)計(jì)數(shù)寄存器，每隔一定時(shí)間向右移動(dòng)一位，替換時(shí)選擇值最小的頁面進(jìn)行替換
• 棧：用于保存當(dāng)前使用的各個(gè)頁面的頁面號(hào)

Clock置換算法

由于LRU算法要求要有比較多的硬件支持，所以實(shí)際中不經(jīng)常使用，一般使用其替代算法如Clock算法等

• 簡單的Clock置換算法
  • 為每個(gè)頁設(shè)置一個(gè)訪問位，在將內(nèi)存中所有頁面都通過指針鏈接成一個(gè)循環(huán)隊(duì)列，每次從隊(duì)首開始檢查，如果發(fā)現(xiàn)訪問位為1，則將其設(shè)置為0，如果是0，則替換該頁，如果循環(huán)一遍還沒有找到，則再循環(huán)一次
• 改進(jìn)型Clock算法
  • 增加多一個(gè)置換代價(jià)，通過組合，有四種情況，如下
    • (A = 0, M = 0)：表示既沒有被訪問過，也沒有被修改過，最佳的淘汰頁
    • (A = 0, M = 1)：未被訪問過，但是已經(jīng)被修改過，不是很好的淘汰頁
    • (A = 1, M = 0)：被訪問過，但是未被修改過，有可能再被訪問
    • (A = 1, M = 1)：既被訪問過，也被修改過，可能再被訪問
  • 執(zhí)行過程
    1. 循環(huán)掃描，尋找A = 0， M = 0 的頁面，如果遇到，則選擇替換，第一次掃描不改變A
    2. 如果1失敗，也就是查找一周之后沒有找到第一類頁面，則開始第二輪掃描，尋找A = 0并且M = 1的頁面，將遇到的第一個(gè)作為淘汰頁，并且將所有掃描過的訪問位設(shè)置為0
    3. 如果2也失敗，則將所有訪問位設(shè)置為0，然后重復(fù)1，然后再重復(fù)2

最少使用算法(LFU Least Frequently Used)

基本思想同LRU

頁面緩沖算法(PBA)

思想：使用兩個(gè)隊(duì)列，一個(gè)空閑一個(gè)存放頁面，等到一定數(shù)量再將其寫入到磁盤上

請(qǐng)求分頁存儲(chǔ)管理方式

請(qǐng)求分段的硬件支持

• 段表機(jī)制：增加一些項(xiàng)，如：存取方式，訪問字段，修改位，存在位，增補(bǔ)位，外存地址
• 缺段中斷機(jī)構(gòu)
• 地址變換機(jī)構(gòu)