iT邦幫忙

0

【小白馬的OS筆記】(11)paging, segement- 地址轉換的問題整理

【小白馬的OS筆記】(3)中,我們講到了paging 的技術,
透過page table將使用者視角的logical address映射到 physical address,
然而在真實的電腦作業系統中,
實際上還會再多一層轉換,
叫做segmentation,
這邊放個精美的投影片講解圖:

https://ithelp.ithome.com.tw/upload/images/20191117/20117114nSfPg83s0J.png

首先,使用者寫程式所看到的變數地址稱為「logical address」,
先透過segmentation將logical address映射至「linear address」,
再透過paging 將「linear address」映射至「physical address」。
你可能會覺得很奇怪,
為什麼要有兩層的地址轉換?
直接將「logical address」映射至「physical address」不行嗎?
這要從記憶體管理會碰到的一個問題- 「碎片化」(fragmentaion)說起了。

碎片化(fragmentaion),用停車場的例子聯想

想像你的記憶體是個停車場
記憶體存放的程式則是車子
但因程式大小不同,猶如有不同大小的車子,
如摩拖車、家用汽車、大卡車、…之類的。
這時,你會兩種方法可以管理你的停車場:

  1. 為停車位劃分一格一格固定大小的車位
  2. 不劃分車位,只要有空間就可以停車。

當然,這兩種方式都會造成一些問題,

  1. 如果是劃分一格一格固定大小的車位,為了讓所有車種都可以停進停車格上,車位可不能劃太小,你大概要把車位劃的讓大卡車停的進來。但是,這樣當摩拖車停在車位上時,對於那個停車格來說便有很大一塊空間是浪費的,這個現象稱為「內部碎片化」(internal fragmentaion)
  2. 如果是不劃分車位,只要有空間就可以停車。假設一開始來了一輛大卡車,然後一台摩拖車緊接著停在大卡車旁,然後一輛家用汽車停在摩拖車旁邊。這時摩拖車可能事情辦完被騎走了,你會發現大卡車和家用汽車中間就留下了一些空間泿費(原本停摩拖車的空間),這種車子和車子間的空間浪費則稱為「外部碎片化」(external fragmentaion)。

為什麼不只用paging?

對於記憶體管理來說,paging只能解決「外部碎片化」的問題,
因為paging將使用者的地址切成一塊塊固定大小,
猶如停車位劃分一格一格固定大小的車位,
車位和車位間是可以沒有間隙的,所以這樣不會有「外部碎片」。

segmentation則是解決內部碎片的問題,
較符合使用者的視角,
比如說將使用者程式相近的地址打包成一個page啦。
以停車格的比喻來說,
就是我發現其實大卡車的停車格可以停下3台摩拖車,
先將3台摩拖車映射到同一塊地址,
再將他們停到同一個停車位,
以解決內部碎片的問題。

所以現代OS的地址映射有segementation, paging兩層哦,
於是乎地址如何轉換的問題也是熱門的考題,
以下試著整理。

熱門題一、為什麼要結合segementation, paging一起用?

【清大102年期中考-OS】
Briefly explain why the modern general purpose OS use both segmentation and paging to manage physical memory?

小馬的答案:

  • Segmentation: 為了與使用者的view一致,可以解決Internal fragmentation
  • Paging: 可以做好硬體管理,使資源使用率提升,可以解決External fragmentation

熱門題二、單獨paging的地址查找

【課堂範例題】
If Page size is 1KB(2^10 bytes) and Page 2 map to frame 5. Given 13 bits logical address: p=2, d=20 (in decimal), how to translate it to physical address?

小馬的答案:
根據題目,地址在二進位底下有13個bits,因為page大小占10個bits。表示前三個bits 用來存page number(p),後十個bits用來存page offset(d)。題目說Page 2 對應到 frame 5,因此真實記憶體位置(physical address)就是5串接上20了(記得把5和20轉換成二進位)。

5 = 101 (in binary for 3 bits)
20 = 0,000,010,100 (in binary for 10 bits)
故答案為: 1,010,000,010,100

熱門題三、理解地址位元數數量的意義

開始講題前,先帶個重要概念給大家,
logical memory裡面的page數量,
與physical meomory裡面的frame數量不必一樣多。

  • page的數量與一支程式的虛擬記憶體(logical/virtual memory)大小有關
  • frame的數量與真實記憶體(physical memory)的大小有關

【課堂範例題】
Given 32 bits logical address, 36 bits physical address and 4KB page size, what does it mean?
(對了,真實考試並不會這樣考,「what does it mean?」這問題太過空泛,本題只是練習解讀可以從題目得到什麼資訊)

課堂標準解答:

  • page table可容納的page 數量: 2^32/2^12 = 2^20 entries
  • frame的數量: 2^36/2^12 = 2^24 frames (frame跟page一樣大)
  • program的記憶體大小: 2^32= 4GB
  • 真實記憶體(physical memory)大小: 2^36= 64GB
  • page number的位元數數量: 2^20 pages -> 20bits
  • frame number的位元數數量: 2^24 frames -> 24bits
  • page offset的位元數數量: 4KB page size -> 12bits

熱門題四、segment與paging結合的地址轉換

【清大102年期中考-OS】
Consider a byte-addressable computer system with a 16-bit virtual address, total physical memory size 4KB, page size is 256Bytes, the maximum size of segment is 1KB. Given the following segment table, page table and a 16 bits hexadeciaml logical address "0C42", complete the address translation diagram below.
(i) segment table index
(ii) linear address (i.e. in binary form)
(iii) page table index
(iv) physical address (i.e. in binary form)

https://ithelp.ithome.com.tw/upload/images/20191117/20117114Xl9Kh0WUJU.png

(i)先將十六進位的地址"0C42"轉換為二進位的"0000 1100 0100 0010"。
由於maximum size of segment is 1KB(2^10),表示後面10個bits都是offset,前6個bits是segment table index,也就是000011(二進位)=3(十進位)
(ii)查表結果是「0110 0111 0111」(最上面當做「第0個」entry,由segmentation table由上往下數到「第3個」),linear address的算法是直接將我們的「segment offset」與查表相加。所以答案為
linear address = 「00 0100 0010」+「0110 0111 0111」=「0110 1011 1001」
(iii)由於題目說page size 256B(相當於2^8),表示在linear address的12bits中,後8個bits 是page offset,剩下的前4個bits是page index。故page index=0110(binary) = 6(decimal)。
(iv)查表結果為第6個page對應到第7個frame(注意表格最上方算「第0個page」)。故physical address= 0111 串接page offset,即「0111 1011 1001」。

綜合測驗題

【清大101年期中考-OS】
Consider a byte-addressable computer system with a 16-bit virtual address and total physical memory size 8KB. Let paging be implemented for the system with page size 128B. Please answer the following question:
(a) If use one-level paging, how many entries should be in a page table?

答案: 2^16/2^7 (2的7次方代表page size 128B)=2^9 entries

(b) If use inverted page table, how many entries should be in a page table?

答案: inverted page table的大小相當於physical memory,因此為
8KB/128B=2^13/2^7=2^6 entries

(c) Given a three-level paging, let the memory access time and TLB(translation lookaside buffer) access time be 500ns and 10ns, respectively. If the TLB hit ratio is 98%, what is the effective memory access time? (Only need to write down the equation)

答案: 如果是普通的one-level paging則是我們熟悉的問題:

  1. 如果透過TLB查到資料了,那麼我們就直接去physical memory就好,
    此時需要的時間為 10+500=510ns。
  2. 如果透過TLB查不到資料,我們要額外花一次時間查page table再去physical memory,
    此時需要的時間為 10+500+500=1010ns
    所以在one-level paging的狀況下EMAT=0.98*510+(1-0.98)*1010
    (可參考【小白馬的OS筆記】(4)的題型)

改成three-level paging的差別在於,
一旦需要查page table,所需要的memory access為三次,
故算式二「如果透過TLB查不到資料」的時間變為10+500*3+500=2010ns

此題答案應為EMAT=0.98*510+(1-0.98)*2010 ns

(d) Now consider to use the segment-paged scheme with each process can use at most 16 segments. Given the following segment table, page table and a 16 bits hexadecimal logical address "7482", complete the address translation diagram below.
(i) segment table index
(ii) linear address (i.e. in binary form)
(iii) page table index
(iv) physical address (i.e. in binary form)

https://ithelp.ithome.com.tw/upload/images/20191117/20117114jxwWEBhvlu.png

答案:
(i)先將十六進位的地址"7482"轉換為二進位的"0111 0100 1000 0010"。
題目說每個process最多可用16(=2^4) segments,表示對於16 bits 的虛擬地址來說,前4個bits用來表示第幾個segment,故segment index為0111(binary) = 7(decimal)
(ii)題目直接告訴我們查表結果是「0110 0111 0110」,linear address的算法是直接將我們的「segment offset」與查表相加。故
linear address = 「0100 1000 0010」+「0110 0111 0110」=「1010 1111 1000」
(iii)由於題目說page size 128B(相當於2^7),表示在linear address的12bits中,後7個bits 是page offset,剩下的前5個bits是page index。page index=10101(binary) = 21(decimal)。
(iv)physical address = 11 串接 page offset = 「01011 1111000」


尚未有邦友留言

立即登入留言