一.(10分)某作業系統下合法的文件名為
device:name.extension
其中第一部分(device:)和第三部分(.extension)可預設,若device,name和extension都是字母串,長度不限,但至少為1,畫出實現這種文件名的確定有限自動機.
二.(10分)下面的二義文法描述命題演算公式,為他寫一個等價的非二義文法.
S->S and S|S or S|not S|p|q|(S)
三.(10分)把表達式
- (a+b)*(c+d)+(a+b+c)
翻譯成四元式.
四.(10分)由於文法二義引起的LR(1)分析動作衝突,可以根據消除二義的規則而得到LR(1)分析表,根據此表可以正確識別輸入串是否為響應語言的句子.對於非二義非LR(1)文法引起的LR(1)分析動作的衝突,是否也可以根據什麼規則來消除LR(1)分析動作的衝突而得到LR(1)分析表,並且根據此表識別相應語言的句子?若可以,你是否可以給出這樣的規則?
五.(10分)下面程序的結果是120.但是如果把第5行的abs(1)改成1的話,則程序結果為1.
試分析為什麼會有這不同的結果.
int fact()
{
static int i=5;
if(i=0) {return(1); }
else { i=i-1; return(( i+abs(1))*fact()); }
}
main(){
printf("factor or 5=%d\n",fact());
}
六.名詞解釋(每小題2分,共10分)
1) 線程 2)管程 3)管道 4)I/O重定向 5)動態地址重定位
七.填空(每空0.5分, 共10分)
1.為了賦予作業系統以某些特權,使得作業系統更加安全可靠地工作,實際作業系統中區分程序執行的兩種不同的運行狀態是___;___態程序不能執行特權指令.
2.引起進程調度的原因有:___,___和___.
3.在一個請求式頁式存儲系統中,一個程序的頁面走向為1,2,1,4,3,2,3,5,1,2,1,3.假定分配給該程序的存儲塊數為4,則採用FIFO,LRU和LFU 頁面置換算法時,訪向過程中的缺頁次數分別為___,___和___.
4.通道技術的引入,實現了___與___的並行;___與___的並行;___與___的並行.
5.設備分配程序除了向提出I/O請求的進程分配設備外,還要為他分配___,___和___
6.文件系統通常向用戶提供的接口有__接口和__接口.
7.UNIX文件系統中通過引入__索引結點來提高文件的檢索效率.
八.簡答題(共10分)
1.(5分)試述缺頁中斷的處理步驟;與一般中斷相比,主要的區別是什麼?
2.(5分)UNIX文件系統使用的地址索引結構是什麼?與一般的地址索引結構相比有什麼優點?付出的代價是什麼?
九.算法題(共10分)
遵循同步機制的四條準則,寫出用鎖機制實現的解決讀者--寫者問題的同步算法.
十.(10分)簡述UNIX系統V中塊設備數據緩衝池的管理技術,給出緩衝池的結構和緩衝區的分配與釋放操作.