[考古] 作業系統（一）/戴嬋玲/98上 期末考
[開課學院]: 資電學院
[開課系所]: 資訊系
[課程名稱]: 作業系統(一)
[老師名稱]: 戴嬋玲 老師
[開課學期]: 981
[類型]: 98-1期末考
一、解釋名詞(25%)
(a)Fragmentation (b)spin lock (c)atomic transaction
(d)Belady's anomaly (e)TLB
二、問答題(75%)
1.Bakery演算法如下，請
(a)說明這個演算法。(5%)
(b)列出解決臨界區間(critical section)問題的三
個必要條件。(5%)
(c)證明Bakery演算法滿足
三個必要條件。(10%)
do{
choosing[i]=true;
number[i]=max(number[0],number[1],....,number[n-1])+1;
choosing[i]=false;
for(j=0;j<n;j++){
while(choosing[j]);
while((number[j]!=0)&&(number[j],j<number[i],i));
}
critical section
number[i]=0;
remainder section
}while(1);
2.伺服器可針對同時連線的用戶個數加以限制。例如，伺服器希望無論何時最多只
有N個socket connection。一但到達N個socket connection，伺服器就不接受再進
來的連線請求，除非任一個已經連線的用戶端結束。
請寫出此用來控制連線請求的假碼(pseudo code)，並說明伺服器如何利用號誌(sem
aphore)來限制同時連線的socket個數? (10%)
3.請比較分頁(paging)和分段(segmentation)記憶體管理模式，它們的邏輯位址轉換
成實際位址的方法有何相似與相異之處? (10%)
4.請說明反轉分頁表(inverted page table)和一般分頁表的建立方式有何差別？
它們各自的優缺點為何？ (10%)
5.關於最佳換置法(Optimal algorithm) (10%)
(a) 舉例說明它的置換方式
(b) 為何它不適合實作?其主要目的為何?
6.當行程只分配到4個頁框(frame)時，以下的分頁取代法(page replacement algorithm)
會發生幾次的分頁失誤(page fault)？請寫出分頁失誤發生時的記憶體內容，並標示將
取代哪一個分頁。(建議同學採用課本的方式作答。)參照字串(reference string)如下:
(15%)
１，２，３，４，５，６，２，１，２，３，７，６，３，２，１，２，３，６
(a)LRU(近來最少使用替換法)
(b)LRU近似法中的Second Chance Algorithm(第二次機會替換法)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.170.119.76