[開課學院]: 資電學院 [開課系所]: 資訊系 [課程名稱]: 作業系統(一) [老師名稱]: 戴嬋玲 老師 [開課學期]: 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