iT邦幫忙

0

【小黑馬作業系統考古】範圍: 恐龍書第八章~第九章

<撰文緣由>: 作業系統是當今資工重要科目,
然而讀了上課講義、恐龍書,
卻無法有效檢測自己讀懂了沒,
即便於網上找了考古題,
卻苦於無人整理正確答案,
無法知道自己是否理解正確。

小馬將整理自己一學期來修課及準備考試的心路歷程,
期由【小黑馬作業系統考古】整理真實考試常出現的問題,
幫助莘莘學子準備作業系統科目。
(如有發現答案有錯可不吝告訴小馬,小馬不勝感激)

<整理範圍>: 恐龍書第八章~第九章,內容涵蓋:
Ch8 記憶體管理 (memory management)
Ch9 虛擬記憶體 (virtual memory)

<分析>:
使用者寫程式所看到的地址(C語言的指標)稱為logical/virtual address,
並非在真實記憶體上的地址(physical address)。
第八章旨在OS如何處理記憶體中的地址轉換(logical-> physical),
第九章重點則在於記憶體和硬碟間如何做資料的搬移(keyword: page fault, page replacement algorithm)。

第八章-記憶體管理(以下題目與答案間刻意留白,方便有心練習的人先思考後再對答案)

基礎名詞解釋題

【清大101、102年期中考】
Briefly explain and compare the following terminologies:
(a) Dynamic linking vs. Dynamic loading
(b) Compile-time address binding vs. Runtime address binding






答案解析:
(a)

  • Dynamic loading是對一支process而言,在需要使用到函數時才讀進CPU中。
  • Dynamic linking是對於在很多支process之間,讓它們link相同的library,就不必每支process都存一個。

(b)

  • Compile-time address binding: process在complie 時就已經決定其在physical memory裡的地址
  • Runtime address binding: 當程式load到記憶體時,仍然是存「虛擬記憶體的位置」,直到程式真正執行才用paging的技術bind到「真實記憶體的位置」。
  • 優缺點比較: Compile-time address binding綁定實體記憶體位址的時間過早,對記體體空間的使用上不夠靈活; Runtime address binding透過paging的技術可以很好的解決這個問題,但會使得存取記憶體時間因此增加。

熱門題型一、TLB的觀念

【清大102年期中考】
(a) Explain what is TLB?
(b) Why TLB is often implemented by associative memory?






答案解析:
(a) TLB是為了加速page table查找的速度而設,是一種cache
(b) 因為associative memory以硬體實作,可以同時查找table的所有格子,以提升查找速度

【清大博士班資格考- 2018春】
Answer the following questions related to TLB(Translation Lookaside Buffer).
(a) Why TLB can improve system performance?
(b) Why TLB might need to be flushed after context switch?






答案解析:
(a) 因為查詢TLB比查詢page table還要來的省時間,一旦在TLB查到page與frame之間的對應,可以節省一次查詢page的時間。因此只要TLB hit ratio夠好,便能提升系統效能。
(b) 因為不同process之間的TLB是共用的。如果不刷新,那麼便會錯誤地讀取到其它process的資料。

熱門題型二、為什麼要真實系統結合segementation, paging一起用?

【清大102年期中考】
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年期中考】
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
    (可參考【小黑馬作業系統教室】(10)計算EMAT的題型)

改成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」

第九章-虛擬記憶體

熱門題型一、page fault相關問題

【清大博士班資格考- 2018春】
(a) What is page fault?
(b) What is segmentation fault?
(c) Why page fault handling is time consuming?
(d) What is thrashing?
(e) How OS can prevent thrashing?






答案解析:
(a) 當一支process要存取自己的page,對應到page table裡的frame卻不在真實記憶體中,稱為page fault。
(b) 在程式內部存取到不該存取的地址?例如陣列宣告int a[4],卻存取a[4]這個位置。
(c) 因為一旦發生page fault,便要從disk將資料搬至memory,所以很耗時。
(d) 當處理程式的時間大於真正執行程式的時間,稱為thrashing。當multiprogramming的degree太高,導致physical memory的frame不夠時會發生。
(e)用working set model來解,記錄單獨一支程式最近△次使用的page的集合。舉例來說,若△=5,某個process最近5次access的page為1,1,3,3,2,則working set ={1,2,3}。
利用working set檢查所有程式(process)需要的frame數量的總和,如果此數大於physical memory裡可以容納的frame,表示multiprogramming的degree太高了,應該減少

【清大102年期中考】
(a) What is page fault?
(b) Describe the steps to handle a page fault.






答案解析:
(a) 當一支process要存取自己的page,對應的frame卻不在真實記憶體中,稱為page fault。
(b) 1. OS會先去disk中查找資料
2. 把資料放進記憶體中
3. 重設page table的valid bit=v
4. process重新進入工作

【某學校期中考題】
(a) 解釋為何page fault 極為耗時
(b) 說明如何以dirty bit解決此問題
(c) 解釋為何真實系統上的page fault可以很小?
(d) 若page size增加,說明帶來的優、缺點






答案解析:
(a) 因為OS必須到disk搬資料進memory,而access disk相當耗時
(b) 利用dirty bit記錄一個page是否修改過,若沒修改過的話則不必進入swap space
(c) 因為在真實系統中,常用到的page通常會放在附近
(d) 優點: 不容易發生page fault
缺點: 一旦發生page fault,需要的處理時間會變長

熱門題型二、page replacement algorithm的操作

【清大101年期中考】
Given a reference string 1,2,1,3,1,4,1,2,3,2. (reference string 指的便是剛剛比喻中會遇見的人) Please step-by-step show the references that cause pages faults with 3 memory frames using.
(a)FIFO
(b)Optimal
(c)LRU replacement algorithm






答案(這邊只寫page fault次數):
(a) 7
(b) 5
(c) 6

熱門題型三、thrashing的觀念,以及如何用working set 解決thrashing的問題

【清大博士班資格考- 2011春】
(a) What is thrashing?
(b) What is working set (WS) concept?
(c) Explain how the WS concept could be used to solve the thrashing problem.






答案解析:
(a) 當處理程式的時間大於真正執行程式的時間,稱為thrashing。當multiprogramming的degree太高,導致physical memory的frame不夠時會發生。
(b) 記錄單獨一支程式最近△次使用的page的集合。舉例來說,若△=5,某個process最近5次access的page為1,1,3,3,2,則working set ={1,2,3}。
(c) 利用working set檢查所有程式(process)需要的frame數量的總和,如果此數大數physical memory裡可以容納的frame,表示multiprogramming的degree太高了,應該減少。

【某學校期中考題】
(a) multiprogramming 系統為何能提升CPU使用率?
(b) 解釋為何multiprogramming的degree太高反使CPU使用率下降






答案解析:
(a)因為multi-programming system 可以在程式要做IO的時候發送interrupt打斷CPU,告訴OS可以換程式執行,以避免CPU idle,進而提高CPU使用率
(b)因為會造成thrashing現象: 當multi-programming的degree過高,physical memory的frame不夠用,使得程式處理paging的時間高於實際執行程式的時間

【某學校期中考題】
(a) 什麼是working set?
(b) working set 如何預防thrashing?
(c) 若working set的window size過大會有什麼潛在的問題?






答案解析:
(a)記錄單獨一支程式最近△次使用的page的集合。舉例來說,若△=5,某個process最近5次access的page為1,1,3,3,2,則working set ={1,2,3}。
(b) 利用working set檢查所有程式(process)需要的frame數量的總和,如果此數超過physical memory裡可以容納的frame,表示multiprogramming的degree太高了,應該減少。
(c) 若△太大,觀察到的是process長期所使用的frame,無法適應短期使用習慣突然改變的變化


尚未有邦友留言

立即登入留言