作者A4P8T6X9 (殘廢的名偵探)
看板Grad-ProbAsk
標題Re: [資工][OS] VM/ monitor/ deadlock/ page table
時間Wed Sep 24 12:50:51 2014
※ 引述《qoojordon (穎川琦)》之銘言：
: 幾個觀念請教與確認:
: Q1: micro kernel的兩個問題
: 已知觀念:
: 將kernel模組化後 , 去除不必要的一些服務 , 儘保留必要的服務(如Process Mgt.)
: 稱之為micro kernel
: 優點: 1.擴展性高 2,更安全實用
: Q1-1 : 被去除的服務可以在 user mode 以 system software 或 Library的方式提
: 提供服務
: 問題:原本在kernel的服務如果被拉到user mode以上述的方式呈現,是否會有功能
: 被閹割的問題呢?(例:原本在kernel提供的security服務如果被拉到user mode後
: ,它的提供的功能會不會不如原本在kernel時強大?)
不會，我覺得看如何 implement。
: Q1-2 : 大多的書面資料都要提到micro kernel安全度較高的優點
: 問題:延續Q1-1 , 不太能理解為甚麼部份重要服務被拉出kernel還能維持比較好的
: 安全性? 如Q1-1的例子 , 把security拉到user mode做 , 萬一user mode下他
: 提供的security服務亂搞 , 系統不就掛了嗎 ?
它的安全性是指如果服務掛掉，不會整個 kernel 掛掉，所以整體相對穩定。
: Q2: multiprocessor , multicore , multithread 名詞概念確認
: 已知觀念: thread 是OS分配CPU資源的最小單位 , 使用thread帶來的好處我是參考
: 網路上估到的這張架構http://ppt.cc/HW~B
: 問題: 這張圖和我自己本身的理解差不多 , 以下分為幾點說明 , 請板友指正是否有錯
: 誤
: 1. core代表每個prcessor上的運算晶片(所以core≧processor)
: 2. 分配thread的單位應該是core
: ->使用thread的好處在於同一process的程式空間有locality的特性,所以
: 位在同一個processor上的不同thread才能發揮multithreading的最大效益
: ->倘若現在同一process的兩個thread被丟到不同processor的core上,就拿不
: 到使用thead的好處 ? (還是只是不能發揮最大效益? 所以好處是 ?)
首先可能會有兩個 core 共用的 cache，再者有的 process 可能會有完全可以平行的部
分，所以分到不同 core 上，會有平行的好處。
然後現在普遍是單一 processor 然後多 core，不太會有很多個 preocessor。
: Q3: deadlock章節中有一個定裡:
: n個process共用m個resource , 不產生dealock有兩個條件
: 1.每個Pi的最大資源需求(記為MAXi) < m
: 2. MAXi 總和 ＜ m+n
: 問題: 若現在m=10 , 每個process最大資源需求為3 , 最大n為何?
: 3n<10+n
: 2n<10 , 最大n=4
: <我自己舉的反例>
: 倘若我取n=5 , 也能找到一組process順序是能不產生deadlock的, 如下例:
: 10個resource分配如右: 3 , 3 , 2 ,1 ,1(依序為P1,P2....P5分配到的資源)
: 依 P1 P2 P3 P4 P4的順序執行 , 可以順利取得資源 , 系統是UnSafe但不會
: Deadlock , 請問我這樣說明有盲點嗎 ? 感覺這裡定理不太能求最大值...是
: 不是我誤解了甚麼
這有點像是特例，但是這個定理是說明絕對不會陷入死結，只要 unsafe就有可能死結所以
不好。再者，這個定理可以用鴿籠原理來更好理解，如果每一個 process 都拿不能滿足的
最多，以你的例子來說相當於總共需要 2n，只要總共需要的比全部少，那麼就一定可以解
，只要一個解之後就一定不會陷入死結。
: Q4 : 記憶體管理中的邏輯位址(LA)轉換概念 , 與虛擬記憶體概念中的虛擬位址(VA)
: Q4-1: 以我目前的理解來說 , LA和VA是在描述相同的東西 , 而他們怎麼和實體位址(PA)
: 對映是page table的工作 , 對每個process而言 ,LA的是下面哪種狀況?
: P1佔8KB , P2佔32KB , 系統執行時 , 他們的LA應該是?
: 狀況一: 皆用處理器處理的位元數視為LA (32bits作業系統就是32bits表示LA)
: 狀況二: 依據Process不同而使用不同的LA , 以上述狀況為例 , P1的LA是13bits
: P2為15bits
: 狀況三: 狀況一,二的折衷版本,LA一樣都視為32bits,只是對於不同的process有
: 效的bits數不同 , 以P1為例 , 超過13bits之後的bits表示的LA對P1而
: 言都沒有意義
虛擬位址長度是固定的，它是用來對應真正的 page 存在哪。
: Q4-2: 承4-1 , 同樣都是指LA = 15的記憶體空間 , 對P1與P2而言是否代表相同意思?
: 我自己的回答: LA都是15對P1,P2來說沒有辦法比較 , 要透過他們各自的page
: table轉換成PA比較才有意義 , 若PA相同 , 此時的狀況可視為shared memory
right
: Q5 : Page Table有三個減少它佔用記憶體空間的方法 , 以下敘述是否有誤
: Q5-1: multi level的方式對於virtual space小的程式而言才有好的效果 , 若virtual
: space很大的程式 , 他還是要存很多筆的位址轉換 , 並不會因為multi level的
: 方法縮小page table使用的空間?
其實不然，如果不分層的話，假設整體只有一層，所以每個 process OS都要存那一層，所
以很浪費空間，但是如果分兩層，可以只存第一層跟有用的第二層，相對省空間，唯一的
缺點只有在把完全的虛擬記憶體空間塞滿，這樣會多一份第一層，但無傷大雅。
且分層的好處是，也可以把第二層分散在記憶體中，更加有彈性。
或許這樣還不夠明白，我可以舉個例子來說。
假設記憶體是 4GB，假設 4KB一個 PAGE，那麼總共會有 2^30 = 1048576個PAGE。
如果每一個 page table entry 是 4 bytes，那麼總共要 4194304 bytes = 4MB 的連續記
憶體空間大小放 page table，但大部分的程式並不需要完全使用 4G，假設一個程式只要
512 MB，那麼只需要 131072 個 page entry 相當於 512KB就夠了，可是只有一層還是要
花 4MB，相當浪費。
如果用兩層，假設第一層有 1024 entry 也就是 4 KB，那麼只要視情況增加第二層且每
一個第二層都可以描述 4MB 其實也不小了，即使全部用完，那也只是多花了 4KB存第一
層，瑕不掩瑜。
: Q5-2: Inverted page table這種方式是否只要OS自己maintain一份即可 ?
: 因為它的轉換方式是 <Process ID , page NO> , 大家的page No一樣多 ,
: Process ID 又提供判斷是不是自己的轉址依據 , 所以只要OS存一份給
: 所有的process查就好?
right
: Q6 : TLB , BHT , BTB 是否都為cache ?
: 我自己查的資料是 cache:TLB , BTB
: BHT 張凡寫 小型記憶體....所以是memory = =?
memory 跟 cache 本質上是一樣的阿，memory 就是硬碟的 cache，所以沒必要強分他們。
: Q7 : monitor觀念 與 semaphore實作monitor
: Q7-1:monitor是否能夠解決同步問題 , 取決於設計的該資料結構的人是否能給予
: condition變數正確的初值 ?
如果是 condition monitor 是的。
: Q7-2:用semaphore實作Hoare monitor不太懂
: 目前理解 : signal的不當使用會造成monitor違反mutual exclusive ,
: Hoare的做法為若Q被P signal而進入monitor中運行 , 那麼
: P必須等到Q wait或 完成才能重新進入monitor
: (參考圖片http://ppt.cc/bl9C)
: 下方為恐龍書上的實作方式
: 請問上述的 P , Q 分別是對應到參考圖片的哪個位置?
: 目前我是這樣對映:
: P-> entry queue圖片左半部 -> 用next記錄
: Q-> c.v. waiting queue -> x記錄
: 製作 x.wait
: (1) x_count = x_count + 1
: (2) if next_count ＞ 0 then signal(next);
: (3) else signal(mutex);
: (4) wait(x-sem);
: (5) x_count = x_count -1;
: (1)~(3) : Q即將要block , 所以先把有機會signal自己的人拉進monitor ?
: (4) : 將Q卡住是為block ?
: 製作 x.signal
: (1) if x_count ＞ 0 then
: (2) begin
: (3) next_count = next_count + 1;
: (4) signal(x-sem);
: (5) wait(next);
: (6) next_count = next_count - 1;
: (7) end
: 如果x被signal代表要先把monitor裡面的procedure拉出來 , 請問(4)(5)
: 兩行的狀況是指 Q要被signal所以先把P拉出去block ?
是
: 問題敘述有點長 , 先謝謝各位了
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.29.128
※ 文章網址: http://www.ptt.cc/bbs/Grad-ProbAsk/M.1411534253.A.B15.html
推 j897495: 謝謝A.5的舉例 讓我觀念更清楚了 09/24 14:41
推 qoojordon: 謝謝A4紙大大 , Q7-2我自己稍微釐清好一點再問 , 感覺 09/24 22:13
→ qoojordon: 我懂一半 , 只是抓不太到他具體的東西套用到例子是甚麼 09/24 22:14
→ qoojordon: 狀況 09/24 22:14
推 HiltonCool: 你可以把P想成Q的救命恩人，當初是P救Q讓Q進入monitor 09/25 00:13
→ HiltonCool: 當Q執行到一半又要被block時(無論自願或被迫)，它應該 09/25 00:14
→ HiltonCool: 要救的是救命恩人P，而不是下一個Q 09/25 00:15
→ HiltonCool: 對P來說，當有Q到的時候，它會將自己block，讓Q進入 09/25 00:18
→ HiltonCool: monitor，這是洪逸上課舉的例子，我覺得可以幫助理解 09/25 00:19