作業系統存儲器管理之連續、頁式、段式、段頁式存儲器管理方式

基本記憶體配置設定方案

4.3 連續配置設定存儲管理方式

連續配置設定方式，是指為一個使用者程式配置設定一個連續的記憶體空間。

4.3.1單一連續配置設定

• 記憶體分為兩個區域：系統區，使用者區。應用程式裝入到使用者區，可使用使用者區全部空間。
• 最簡單，适用于單使用者、單任務的OS。
• 優點：易于管理。

• 缺點：

  對要求記憶體空間少的程式，造成記憶體浪費；

  程式全部裝入，很少使用的程式部分也占用記憶體

4.3.2固定分區配置設定

1、基本原理及技術

• 系統提前把記憶體分為一些大小相等或不等的分區(partition)，每個程序占用一個分區。作業系統占用其中一個分區。
• 特點：适用于多道程式系統和分時系統
  • 支援多個程式并發執行
• 問題：可能存在内碎片。
  • 内碎片：分區之内未被利用的空間
  • 外碎片：分區之間難以利用的空閑分區（通常是小空閑分區）。

2、劃分分區的方法

• 分區大小相等：隻适合于多個相同程式的并發執行（處理多個類型相同的對象）。缺乏靈活性。
• 分區大小不等：多個小分區、适量的中等分區、少量的大分區。根據程式的大小，配置設定目前空閑的、适當大小的分區。

  

• 優點：易于實作，開銷小。
• 缺點：
  • 内碎片造成浪費
  • 分區總數固定，限制了并發執行的程式數目。
• 可以和覆寫、交換技術配合使用。
• 采用的資料結構：分區表－記錄分區的大小和使用情況

  

• 當有一使用者程式要裝入時，由記憶體配置設定程式檢索該表；
• 從中找出一個能滿足要求的、尚未配置設定的分區；
• 将之配置設定給該程式，然後将該表項中的狀态置為“已配置設定”；
• 若未找到大小足夠的分區，則拒絕為該使用者程式配置設定記憶體。

4.3.3動态分區配置設定

• 動态建立分區：
  • 在裝入程式時按其初始要求配置設定；
  • 或在其執行過程中通過系統調用進行配置設定或改變分區大小。
• 優點：沒有内碎片。
• 缺點：有外碎片；
• 動态分區配置設定是根據程序的實際需要，動态地為之配置設定記憶體空間。
• 在實作過程中涉及三個問題：
  • 分區配置設定中的資料結構
  • 分區配置設定算法
  • 分區配置設定操作

1、分區配置設定中的資料結構

• 空閑分區表

  記錄每個空閑分區的情況。每個空閑分區占一個表目，表目中包括分區序号、分區始址及分區的大小等資料項。

• 空閑分區鍊：

  

2、常用的配置設定算法

• 基于順序搜尋的分區配置設定算法：
  • (1) 首次适應算法FF(First Fit)
  • (2) 循環首次适應算法NF(Next Fit)
  • (3) 最佳适應算法BF(Best Fit)
  • (4) 最差适應算法WF(Worst Fit)

首次适應算法FF(First Fit)

（最先比對法(first-fit)）首址遞增排列。

• 優點：優先利用記憶體低址部分。
• 缺點：低址部分不斷劃分，産生小碎片；每次查找從低址部分開始，增加了查找的開銷。

循環首次适應算法NF(Next Fit)

（下次比對法(next-fit)）

• 為實作算法，需要：

  設定一起始查尋指針

  采用循環查找方式

• 優點：使記憶體空閑分區分布均勻，減少查找的開銷
• 缺點：缺乏大的空閑分區

最佳适應算法(best-fit)

（最佳比對法(best-fit) ）

• 空閑區按大小遞增排列！

  缺點：産生許多難以利用的小空閑區（外碎片）

最差适應算法(worst-fit)

（最壞比對法(worst-fit) ）

• 空閑區按大小遞減排列！
  • 不會留下太多的小空閑分區；
  • 但較大的空閑分區不被保留。

配置設定算法對比

• 首次适應算法
  • 将位址最小的夠用的空間配置設定出去
• 下次适應算法
  • 從上次配置設定位置開始搜尋
  • 将位址最小的夠用的空間配置設定出去
• 最佳适應算法
  • 将夠用的長度最小的空間配置設定出去
• 最差适應算法
  • 将夠用的長度最大的空間配置設定出去

    

3、分區配置設定操作

• 配置設定記憶體
• 設請求的分區大小為u.size，
• 表中每個空閑分區的大小表示為m.size，
• 若m.size- u.size≤size(最小門檻值)，
• 将整個分區配置設定給請求者，
• 否則從分區中按請求的大小劃出一塊記憶體空間配置設定，
• 餘下部分留在空閑鍊中，将配置設定區首址傳回給調用者。

  

4、回收記憶體（四種情況）

• 當程序運作完畢釋放記憶體時，系統根據回收區首址，在空閑分區鍊(表)中找到相應插入點；
• 此時可能有四種情況：

  

  • (1) 回收區與插入點的前一個分區F1鄰接：将回收區與F1合并，修改F1的表項的分區大小
  • (2) 回收區與插入點的後一個分區F2鄰接：将回收區與F2合并，修改F2的表項的首址、分區大小
  • (3) 回收區與插入點的前後兩個分區F1、F2鄰接：将三個分區合并，使用F1的表項和F1的首址，取消F2的表項，大小為三者之和
  • (4) 回收區既不與F1鄰接，又不與F2鄰接：為回收區單獨建立新表項，填寫回收區的首址與大小，根據其首址插到空閑鍊中的适當位置

5、基于索引搜尋的分區配置設定算法

當系統很大時，系統中的記憶體分區可能會很多，相應的空閑分區表或鍊就可能很長，這時采用順序搜尋分區方法可能會很慢。

★快速适應算法：

将空閑分區，按其容量大小，進行分類，對于每一類的所有空閑分區，單獨設立一個空閑分區連結清單

★夥伴系統：

分區大小均為2的k次幂，将空閑分區按分區的大小進行分類，并單獨設立一個空閑分區雙向連結清單。

• 夥伴的定義

  滿足以下三個條件的稱為夥伴：

  • 1）兩個塊大小相同；
  • 2）兩個塊位址連續；
  • 3）兩個塊必須是同一個大塊中分離出來的；
• 一種經典的記憶體配置設定方案
• 主要思想：将記憶體按2的幂進行劃分，組成若幹空閑塊連結清單；查找該連結清單找到能滿足程序需求的最佳比對塊。
• 算法：
  • 首先将整個可用空間看作一塊： 2U
  • 假設程序申請的空間大小為 s，如果滿足
  • 2U-1 < s <= 2U，則配置設定整個塊
  • 否則，将塊劃分為兩個大小相等的夥伴，大小為2U-1
  • 一直劃分下去直到産生大于或等于 s 的最小塊

• 配置設定算法

  當使用者申請大小為n的記憶體請求,在可利用空閑表上尋找結點大小與n相比對的表

  • 表非空，配置設定表中第一個記憶體塊
  • 表空，從更大的非空表中查找，直到找到一個空閑塊，切割出所需要大小的塊
  • 未配置設定部分，插入到相應的空閑表中

• 回收算法

  判斷夥伴是否為空閑塊(回收算法需了解釋放的塊大小)

  • 否，将釋放的空閑塊插入到相應表中；
  • 是，找到夥伴，夥伴出隊，合并
  • 合并後，判斷合并後的塊的夥伴是否是空閑塊，如果是，繼續合并成更大的塊。依次重複，直到歸并後的塊的夥伴不空閑。再插入到相應的空閑塊表中。
• 分析
  • 可以很快找到空閑塊；
  • 避免了外碎片問題；
  • 申請記憶體總是以2n位元組滿足要求，存在内碎片； 例如：申請130位元組，會分得256位元組; 申請1514位元組，會分得2048位元組
  • 申請/釋放可能會導緻連續切塊/合并，影響系統效率；例如：
    • 目前隻有一塊空閑，塊大小1M, 最小配置設定機關32B；
    • 現申請40位元組：
  • 會導緻14次切塊，用完立即歸還，導緻14次合并；
  • 如果程式循環式申請40位元組，然後歸還記憶體，會導緻系統頻繁忙碌。

★雜湊演算法：

構造一張以空閑分區大小為關鍵字的哈希表，該表的每一個表項記錄了一個對應的空閑分區連結清單表頭指針。

4.3.4動态重定位分區配置設定

1. 動态重定位的引入

• 解決碎片：将記憶體中的所有作業進行移動，使它們全部鄰接，這樣可把原來分散的小分區拼接成大分區，這種方法稱為“拼接”或“緊湊”。
• 缺點：使用者程式在記憶體中的位址發生變化，必須重定位。

  

• 緊縮技術
  • 記憶體緊縮(compaction)：将各個占用分區向記憶體一端移動。使各個空閑分區聚集在另一端，然後将各個空閑分區合并成為一個空閑分區。
    • 優點：消除外碎片。
    • 缺點：對占用分區進行記憶體資料搬移占用CPU時間；重定位需要硬體支援。
    • 緊縮時機：每個分區釋放後；記憶體配置設定找不到滿足條件的空閑分區時。

2、動态重定位的實作

位址變換過程是在程式執行過程期間，随着對每條指令的通路自動進行的，稱為動态重定位。

• 可重定位分區配置設定方式主要特點
  • 可以充分利用存儲區中的“零頭/碎片”，提高主存的使用率。
  • 但拼接/緊縮會使系統開銷加大。

4.4 對換（Swapping）

多道程式環境下存在的問題：

• 阻塞程序占據大量記憶體空間
• 許多作業在外存而不能進入記憶體運作

對換定義

所謂“對換”，是指把記憶體中暫時不能運作的程序或者暫時不用的程式和資料，調到外存上，以便騰出足夠的記憶體空間，再把已具備運作條件的程式和資料，調入記憶體。

• 分類：
  • 整體對換(或程序對換)：以整個程序為機關
  • 頁面對換或分段對換：以頁或段為機關

實作程序對換，系統必須具備的功能

對換空間的管理

程序的換出

過程：系統首先選擇處于阻塞狀态且優先級最低的程序作為換出程序，然後啟動盤塊，将該程序的程式和資料傳送到磁盤的對換區。

程序的換入

程序的換入

系統應定時檢視所有程序的狀态，從中找出**“就緒”狀态但已換出的程序，将換出最久的程序**作為換入程序，将之換入。

覆寫技術與對換技術

• 覆寫技術：把使用者作業分成若幹段，使主段成為作業執行過程中經常使用的資訊，其他段不同時工作。作業執行時，把主段常駐主存區，其他段輪流裝入覆寫區執行之。
• 對換技術：讓多個使用者作業輪流進入主存器(轉入、轉出)執行。
• 覆寫主要在同一個作業或同一個程序内進行。
• 對換主要是在程序或作業之間進行。覆寫隻能覆寫那些與覆寫程式段無關的程式段。

4.5 分頁存儲管理方式

4.5.1 分頁存儲管理的基本方法

• 将程式的邏輯位址空間劃分為固定大小的頁;
• 實體記憶體劃分為固定大小的塊（頁架）;
• 程式加載時，配置設定其所需的所有頁，這些頁不必連續。需要CPU的硬體支援。

  

• 優點：
  • 沒有外碎片，每個内碎片不超過頁大小。
  • 一個程式不必連續存放。
  • 便于改變程式占用空間的大小。即随着程式運作而動态生成的資料增多，位址空間可相應增長。
• 缺點：程式全部裝入記憶體。

  

  

頁面和實體塊

• 分頁存儲管理是将一個程序的邏輯位址空間分成若幹個大小相等的片稱為頁，并為各頁加以編号，從0開始。
• 同時把記憶體空間分成與頁面相同大小的若幹個存儲塊，稱為塊。
• 在為程序配置設定記憶體時，以塊為機關将程序的若幹個頁分别裝入到多個可以不相鄰的實體塊中。
• 程序的最後一頁經常裝不滿而形成**“頁内碎片”**。

  

位址結構

• 劃分是由系統自動完成的，對使用者是透明的

• 假定位址長度32位:

  每頁的大小為4KB , 即：0~11位為位移量(頁内位址)

  則：12 ~31位為頁号，位址空間最多允許有1M頁（是記憶體總共支援這麼多頁，還是一個程序支援這麼多頁）

頁号與頁内偏移的計算

• 若給定一個邏輯位址空間中的位址為A，頁面大小為L，則:
  • 頁号： P=INT[A/L]
  • 頁内位址： d=[A] MOD L
• 例如：系統頁面大小為1KB，設A=2170B，則:P=2，d=122

4.5.2 位址變換機構

1. 基本的位址變換機構：

• 實作從邏輯位址到實體位址的轉換，其任務是借助于頁表，将邏輯位址中的頁号轉換為記憶體中的實體塊号。
• 頁表可以由一組專門的寄存器來實作，一個頁表項用一個寄存器。但寄存器成本高，系統頁表可能很大，是以頁表大多常駐記憶體。
• 在系統中隻設定一個頁表寄存器PTR，在其中存放頁表在記憶體中的始址和頁表的長度。

  

  

位址轉換步驟

• 當邏輯位址為十進制時：
  • 求出邏輯位址的頁号 = 邏輯位址 / 頁面大小
  • 求出頁内偏移量 = 邏輯位址 % 頁面大小
  • 用頁号查頁表，得到塊号；
  • 求出實體位址 = 塊号 * 頁面大小 + 頁内偏移
• 當邏輯位址為十六進制/八進制/二進制時:
  • 把邏輯位址轉為二進制；
  • 按頁的大小分離出頁号和頁内偏移量（ 高位部分為頁号，低位部分為頁内偏移量 ）；
  • 以頁号查頁表，得到實體位址的塊号；
  • 将邏輯位址的頁内偏移量直接複制到實體位址的塊内偏移量上；
  • 把塊号轉為二進制，進而得出實體位址，再轉回16/8進制。

2.具有快表的位址變換機構

• CPU在每存取一個資料時，需要兩次通路記憶體：
  • 第一次：通路頁表，找到指定頁的實體塊号，将塊号與頁内偏移量拼接形成實體位址。
  • 第二次：從第一次所得位址中獲得所需資料，或向此位址中寫入資料。
  • 缺點：處理速度降低！
  • 解決方法：在位址變換機構中，增設一個具有并行查尋能力的特殊高速緩沖寄存器，稱為**“聯想存儲器”或“快表”**。（預設先通路塊表再通路頁表，如同時通路會給出備注）

    

• 有效通路記憶體的時間

  T=PTLB（TTLB+TM）+ （1-PTLB ）（ TTLB + 2TM ）

  其中,PTLB為快表的命中率,TTLB為快表的通路時間, TM為記憶體的通路時間

  

4.5.3 有效通路記憶體的時間

T=a*（λ+t）+ （1-a）*（ λ+2t ）

=aλ+at+(1-a)(λ+t)+(1-a)t

=aλ+(1-a)(λ+t)+t

（ 第四版P142）

其中,a為快表的命中率, λ為快表的通路時間, t為記憶體的通路時間

4.5.4兩級和多級頁表

• 現代計算機系統都支援非常大的邏輯位址空間(232~264)，頁表就非常大，需占用較大的位址空間。
• 例如：一個具有32位邏輯位址空間的分頁系統，規定頁面大小為4KB即212B，則每個程序頁表的頁表項可達1M個，若每個頁表項占用4個位元組，則每個程序的頁表就要占據4MB的記憶體空間，而且要求連續存放。

1. 兩級頁表

• 例如： 32位邏輯位址空間，頁面大小為4KB(即12位)，若采用一級頁表機構，應有20位頁号，即頁表項應有1M個；在采用兩級頁表機構時，再對頁表進行分頁，使每頁包含210(即1024)個頁表項，最多允許有210個頁表分頁。即

  

  

  

2.多級頁表

• 兩級頁表對32位機器适用，64位呢？
  • 頁面大小為4KB即212B，還剩52位，按實體塊大小212B來劃分頁表(一個表項占4個位元組)，則剩餘42位用于外層頁号，此時外層頁表可能有4096G個頁表項，要占用16384GB的連續存儲空間;
  • 解決方法：采用多級頁表，将外層頁表再進行分頁。

    

• 為何引入多級頁表？多級頁表是否影響速度？
  • 為了使得大頁表也能夠不連續存放；
  • 減少大頁表所占用的存儲空間；
  • 多級頁表會降低位址映射的速度，但通過快表仍可以将效率保持在合理的範疇内。

反置頁表

• 了解即可

  在利用反置頁表進行位址變換時，是用程序标志符和頁号去檢索反置頁表；若檢索完整個頁表都未找到與之比對的頁表項，表明此頁此時尚未調入記憶體，對于具有請求調頁功能的存儲器系統應産生請求調頁中斷，若無此功能則表示位址出錯；如果檢索到與之比對的表項，則該表項的序号i便是該頁所在的實體塊号，将該塊号與頁内位址一起構成實體位址。

  雖然反置頁表可以有效地減少頁表占用的記憶體，然而該表中卻隻包含已經調入記憶體的頁面，并未包含那些未調入記憶體的各個程序的頁面，因而必須為每個程序建立一個外部頁表(External Page Table)，該頁表與傳統頁表一樣，當所通路的頁面在記憶體時并不通路這些頁表，隻是當不在主存時才使用這些頁表。該頁表中包含了頁面在外存的實體位置，通過該頁表可将所需要的頁面調入記憶體。

  由于在反置頁表中是為每一個實體塊設定一個頁表項的，通常頁表項的數目很大，從幾千項到幾萬項，要利用程序辨別符和頁号去檢索這樣大的線性表是相當費時的。于是又利用一種Hash表來檢索。

• 與傳統頁表相比，倒置頁表有什麼優勢？
  • 傳統頁表是面向程序邏輯位址空間的，即對應程序的每個邏輯頁面設定一個表項，當程序的位址空間很大時，頁表需占用很多的存儲空間，造成浪費；
  • 與經典頁表不同，反置頁表是面向記憶體實體塊的，即對應記憶體的每個實體塊設定一個表項，表項的序号就是實體塊号f，表項的内容則為程序辨別pid與邏輯頁号p的有序對；
  • 系統隻需設定一個反置頁表，為所有程序所共用。

頁的共享

• 共享代碼（資料）的實作方法

  被各程序共享的一段代碼（資料），由各程序相應的頁表項指向相同實體塊。

• 問題

  若共享資料與不共享資料劃在同一塊中，則：

  有些不共享的資料也被共享，不易保密

  當共享資料較大時，頁表項數同時大幅增加

頁的保護

• 頁式存儲管理系統提供了兩種方式：
  • 位址越界保護
  • 在頁表中設定保護位（定義操作權限：隻讀，讀寫，執行等）

4.6 分段存儲管理方式

4.6.1分段存儲管理方式的引入

• 引入分段存儲管理方式，主要是為了滿足使用者的一系列要求：
  • 友善程式設計：按邏輯關系分為若幹個段，每個段從0編址，并有名字和長度，通路的邏輯位址由段名和段内偏移量決定。
  • 資訊共享：共享是以資訊為邏輯機關，頁是存儲資訊的實體機關，段卻是資訊的邏輯機關。
  • 資訊保護：保護也是對資訊的邏輯機關進行保護的。
  • 動态連結：動态連結以段為機關。
  • 動态增長：實際應用中，某些段（資料段）會不斷增長，前面的存儲管理方法均難以實作。

空間劃分（分段）

• 将使用者作業的邏輯位址空間劃分成若幹個大小不等的段（由使用者根據邏輯資訊的相對完整來劃分）。各段有段名（常用段号代替），首位址為0。

  

記憶體配置設定

• 在為作業配置設定記憶體時，以段為機關，配置設定一段連續的實體位址空間；段間不必連續。
  • 1、整個作業的邏輯位址空間是二維的，其邏輯位址由段号和段内位址組成；實體位址空間是一維的。
  • 2、需要CPU的硬體支援（位址變換機構）

    

4.6.2分段系統的基本原理

• 頁式管理把邏輯位址視為一維線性空間；
• 段式管理把邏輯位址視為二維空間。
• 将一個使用者程式的所有邏輯段從0開始編号，稱為段号；
• 每一段内的所有單元從0開始編址，稱為段内位址；
• 邏輯位址由段号和段内位址兩部分組成。
• 段式管理将程式的位址空間劃分為若幹個段(segment)，程式加載時，配置設定其所需的所有段（記憶體分區），這些段不必連續；實體記憶體的管理采用動态分區。需要CPU的硬體支援。
• 程式通過分段(segmentation)劃分為多個子產品，如代碼段、資料段、共享段。
  • 可以分别編寫和編譯
  • 可以針對不同類型的段采取不同的保護
  • 可以按段為機關來進行共享，包括通過動态連結進行代碼共享
• 優點：
  • 沒有内碎片，外碎片可以通過記憶體緊縮來消除。
  • 便于改變程序占用空間的大小。
• 缺點：程序全部裝入記憶體。

  

段表

• 記錄了段與記憶體位置的對應關系
• 段表常儲存在記憶體中
• 段表的基址及長度由段表寄存器給出：段表始址，段表長度
• 通路一個資料/指令需通路記憶體2次(段表一次,記憶體一次),是以也出現記憶體通路速度降低的問題。
• 二維的邏輯位址：段号，段内位址
• 許多編譯程式支援分段方式，自動根據源程式的情況産生若幹個段

分段位址變換機構

1.分段位址結構

由于整個作業的位址空間是分成多個段，因而是二維的，亦即，其邏輯位址由段号(段名)和段内位址所組成。

該位址結構允許一個作業最長有64K個段，每段的最大長度為64KB。

2.段表

• 段表可以存放在寄存器中，但更多的是存放在記憶體中。
• 段表可以實作從邏輯段到實體記憶體區的映射。
• 所需表目
  • （1）段表：每個程序一個
  • （2）總段表：系統一個
• 所需寄存器
  • （1）段表首位址寄存器：系統一個
  • （2）段表長度寄存器：系統一個
  • （3）快表：系統一組

3.位址變換機構

在系統中設定段表寄存器，用于存放段表始址和段表長度，以實作從程序的邏輯位址到實體位址的變換。

• 注意：當段表存放在記憶體中時，每通路一個資料，都需通路兩次記憶體，降低了計算機的速率。
• 解決方法：設定聯想寄存器（快表），用于儲存最近常用的段表項。

  

段的動态連結和裝配

所謂動态連結，是指在一個程式開始運作時，隻将主程式裝配好并調入記憶體，在程式運作過程中若要訪**問一個新的子產品時，再裝配此子產品，**并與主程式連結起來。

4.6.3資訊共享

• 分段系統的一個突出優點是易于實作段的共享，允許若幹個程序共享一個或多個分段，且對段的保護十分簡單易行。
• 分頁系統中雖然也能實作程式和資料的共享，但遠不如分段系統友善。
• 如果多個使用者程序或作業需要共享某段程式或資料，可以使用不同的段名，在各自的段表中填入已在記憶體中的共享段的起始位址，并設定适當的讀寫控制權，就可以做到共享一個記憶體段的資訊。
• 為什麼說分段系統較之分頁系統更易于實作資訊共享和保護？
  • 對分段式系統，被共享的程式或資料可作為單獨的一段。在實體上它是一段，在不同的程序中，可以對應不同的邏輯段，相對來說比較易于實作。
  • 對分頁管理，則要困難的多。首先，必須保證被共享的程式或資料占有整數塊，以便與非共享部分分開。其次，增加了程序的頁表長度。

段的共享

共享段表

程序段表(n)->共享段表(1)->共享段(1)

段的保護

分頁和分段的主要差別

• 相似點：采用離散配置設定方式，通過位址映射機構實作位址變換
• 不同點：
  • 頁是資訊的實體機關，分頁是為了滿足系統的需要；段是資訊的邏輯機關，含有一組意義相對完整的資訊，分段是為了滿足使用者的需要。
  • 頁的大小固定且由系統确定，由系統把邏輯位址分為頁号和頁内位址，由機器硬體實作；段的長度不固定，取決于使用者程式，編譯程式對源程式編譯時根據資訊的性質劃分。
  • 分頁的作業位址空間是一維的；分段的作業位址空間是二維的。

    

段式和頁式存儲管理的位址結構相似，它們有什麼實質性差異?

• 頁式存儲管理提供連續的邏輯位址．由系統進行分頁；
• 而段式存儲管理中作業的分段是由使用者決定的，每段獨立程式設計，是以段間的邏輯位址是不連續的。

4.6.4段頁式存儲管理

• 段式優于頁式

  便于共享和保護

• 頁式優于段式

  消除“外碎片”問題

• 段頁式：結合二者優點

  每個程序包含若幹段

  每個段包含若幹頁

1.基本原理

• 記憶體空間劃分：(同頁式)

  靜态等長，2i, 稱為一塊。

  實體位址=(塊号,塊内位址)=(f,w)

• 程序空間劃分：

  一個程序<–>若幹個段

  一個段<–>若幹個頁

  邏輯位址=(段号, 邏輯頁号, 頁内位址)=(s,p,w)

  

  

  

所需表目

(1) 段表：每個程序一個

(2)頁表：每個段一個

所需寄存器

• (1)段表基址寄存器：儲存正運作程度段表首址；
• (2)段表限長寄存器：儲存正運作程式段表長度。

• (3)快表：一組聯想寄存器 (快段表+快頁表)

  -

  

三次訪存

• 第一次：通路記憶體中的段表，取得頁表始址；
• 第二次：通路記憶體中的頁表，取得該頁所在的實體塊号，将塊号與頁内位址形成實體位址；
• 第三次：通路上述位址，取出指令或資料。
• 缺點：訪存次數增加
• 解決方法：增設高速緩沖寄存器-快表

簡要比較各種存儲管理方法的功能和實作特點

• （1）連續配置設定：
  • 指為一個使用者程式配置設定一個連續的位址空間，包括單一連續配置設定方式和分區式配置設定方式；
  • 分區式配置設定方式分為固定分區和動态分區，固定分區是最簡單的多道程式的存儲管理方式，由于每個分區的大小固定，必然會造成存儲空間的浪費；
  • 動态分區是根據程序的實際需要，動态地為之配置設定連續的記憶體空間；
  • 常用四種配置設定算法: 首次适應算法FF，該法容易留下許多難以利用的小空閑分區，加大查找開銷；循環首次适應算法，該算法能使記憶體中的空閑分區分布均勻，但會緻使缺少大的空閑分區；最佳适應算法，該算法也易留下許多難以利用的小空閑區；最差适應算法，優點是可以提高了查找速度、避免形成太多碎片，缺點是分割大的空閑區後，再遇到較大的申請時，無法滿足的可能性較大。
• （2）離散配置設定方式：
  • 基于将一個程序直接分散地配置設定到許多不相鄰的分區中的思想，分為分頁式存儲管理、分段存儲管理和段頁式存儲管理；
  • 分頁式存儲管理旨在提高記憶體使用率，滿足系統管理的需要；
  • 分段式存儲管理則旨在滿足使用者(程式員)的需要，在實作共享和保護方面優于分頁式存儲管理；