./四、計算題1．有以下三個作業(yè),分別采用先來先服務(wù)和短作業(yè)優(yōu)先作業(yè)調(diào)度算法。試問它們的平均周轉(zhuǎn)時間各是什么？是否還可以給出一種更好的調(diào)度算法,使其平均周轉(zhuǎn)時間優(yōu)于這兩種調(diào)度算法？作業(yè)到達(dá)時間所需CPU時間10.0820.4431.01解：〔1采用先來先服務(wù)作業(yè)調(diào)度算法時的實施過程如下。作業(yè)到達(dá)時間所需CPU時間開始時間完成時間周轉(zhuǎn)時間10.080.08.08.020.448.012.011.631.0112.013.012.0這時,作業(yè)的調(diào)度順序是1→2→3。其平均周轉(zhuǎn)時間為：〔8+11.6+12/3=10.53〔2采用短作業(yè)優(yōu)先作業(yè)調(diào)度算法時的實施過程如下。作業(yè)到達(dá)時間所需CPU時間開始時間完成時間周轉(zhuǎn)時間10.080.08.08.031.018.09.08.020.449.013.012.6這里要注意,在作業(yè)1運(yùn)行完畢進(jìn)行作業(yè)調(diào)度時,作業(yè)2和3都已經(jīng)到達(dá)。由于是實行短作業(yè)優(yōu)先作業(yè)調(diào)度算法,因此先調(diào)度作業(yè)3運(yùn)行,最后調(diào)度作業(yè)2運(yùn)行。所以,這時的作業(yè)調(diào)度順序是1→3→2。其平均周轉(zhuǎn)時間為：〔8+8+12.6/3=9.53〔3還可以有更好的作業(yè)調(diào)度算法,使其平均周轉(zhuǎn)時間優(yōu)于這兩種調(diào)度算法。例如,如果知道在作業(yè)1后面會來兩個短作業(yè),那么作業(yè)1到達(dá)后,先不投入運(yùn)行。而是等所有作業(yè)到齊后,再按照短作業(yè)優(yōu)先作業(yè)調(diào)度算法進(jìn)行調(diào)度,具體實施過程如下。作業(yè)到達(dá)時間所需CPU時間開始時間完成時間周轉(zhuǎn)時間31.011.02.01.020.442.06.05.610.086.014.014.0這時的作業(yè)調(diào)度順序是3→2→1。其平均周轉(zhuǎn)時間為：〔1+5.6+14/3=6.872．有一組作業(yè),它們的到達(dá)時間和所需CPU時間如下所示,分別采用先來先服務(wù)和短作業(yè)優(yōu)先作業(yè)調(diào)度算法,給出它們的調(diào)度順序、作業(yè)周轉(zhuǎn)時間以及平均周轉(zhuǎn)時間。作業(yè)號到達(dá)時間所需CPU時間19:0070分鐘29:4030分鐘39:5010分鐘410:105分鐘解：〔1采用先來先服務(wù)作業(yè)調(diào)度算法時的實施過程如下：作業(yè)號到達(dá)時間所需CPU時間開始時間完成時間周轉(zhuǎn)時間19:0070分鐘9:0010:1070分鐘29:4030分鐘10:1010:4060分鐘39:5010分鐘10:4010:5060分鐘410:105分鐘10:5010:5545分鐘這時,作業(yè)的調(diào)度順序是1→2→3→4,其平均周轉(zhuǎn)時間為：〔70+60+60+45/4=58.75〔2采用短作業(yè)優(yōu)先作業(yè)調(diào)度算法時的實施過程如下：作業(yè)號到達(dá)時間所需CPU時間開始時間完成時間周轉(zhuǎn)時間19:0070分鐘9:0010:1070分鐘410:105分鐘10:1010:155分鐘39:5010分鐘10:1510:2535分鐘29:4030分鐘10:2510:5575分鐘這時,作業(yè)的調(diào)度順序是1→4→3→2,其平均周轉(zhuǎn)時間為：〔70+5+35+75/4=46.25三、簡答題1.對臨界區(qū)的管理應(yīng)遵循哪些基本準(zhǔn)則？答：為了合理利用臨界資源,保證進(jìn)程互斥地進(jìn)入臨界區(qū),對臨界區(qū)的管理應(yīng)遵循以下準(zhǔn)則：〔1空閑讓進(jìn)。當(dāng)無進(jìn)程處于臨界區(qū)時,表明臨界資源處于空閑狀態(tài),應(yīng)允許一個請求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū),以有效地利用臨界資源。〔2忙則等待。當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時,表明臨界資源正在被訪問,因而其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待,以保證對臨界資源的互斥訪問?！?有限等待。對要求訪問臨界資源的進(jìn)程,應(yīng)保證在有限時間內(nèi)能進(jìn)入自己的臨界區(qū),以免陷入"死等"狀態(tài)?！?讓權(quán)等待。當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時,應(yīng)立即釋放處理機(jī),以免進(jìn)程陷入"忙等"狀態(tài)。2.什么是死鎖？死鎖的預(yù)防措施有哪些？答：死鎖是指多個并發(fā)執(zhí)行的進(jìn)程因競爭系統(tǒng)資源而造成的一種僵局,若無外力作用,這些進(jìn)程都將無法向前推進(jìn)。由于產(chǎn)生死鎖的4個必要條件必須同時存在,系統(tǒng)才會產(chǎn)生死鎖,所以,只要使4個必要條件中至少有一個不能成立,就可以達(dá)到預(yù)防死鎖的目的。〔1破壞"請求和保持"條件,優(yōu)點是簡單、易于實現(xiàn)且很安全；〔2破壞"不剝奪"條件,在采用這種方法預(yù)防死鎖時,進(jìn)程是在需要資源時才提出請求。這樣,一個已經(jīng)保持了某些資源的進(jìn)程,當(dāng)它再提出新的資源要求而不能立即得到滿足時,必須釋放它已經(jīng)保持的所有資源,待以后需要時再重新申請。這種預(yù)防死鎖方法,實現(xiàn)起來比較復(fù)雜,且要付出很大代價。〔3破壞"循環(huán)等待"條件,在這種方法中規(guī)定,系統(tǒng)將所有的資源按類型進(jìn)行線形排隊,并賦予不同的序號。這種預(yù)防死鎖的策略與前兩種策略比較,其資源利用率和系統(tǒng)吞吐量,都有較明顯的改善。由于互斥性是某些資源的固有特性,所以一般不破壞互斥條件。3.進(jìn)程之間有哪些基本的通信方式？分別有什么特點？答：進(jìn)程通信根據(jù)交換信息量的多少分為高級通信和低級通信。低級通信一般只傳送一個或幾個字節(jié)的信息,以達(dá)到控制進(jìn)程執(zhí)行速度的作用〔如P、V操作；高級通信則要傳送大量數(shù)據(jù),目的不是為了控制進(jìn)程的執(zhí)行速度,而是為了交換信息。高級進(jìn)程通信方式有很多種,大致可歸為三類：共享存儲器、管道通信和消息傳遞?！?共享存儲器：在內(nèi)存種分配一片空間作為共享存儲區(qū)。需要進(jìn)行通信的進(jìn)程把它附加到自己的地址空間中,不需要時則把它取消。〔2管道通信：它是連接兩個命令的一個打開文件。一個命令向該文件中寫入數(shù)據(jù),為寫者；另一個命令從該文件中讀出數(shù)據(jù),為讀者。〔3消息傳遞：它以消息為單位在進(jìn)程間進(jìn)行數(shù)據(jù)交換。三、簡答題1.將一個程序裝入內(nèi)存通常有哪幾種方式？答：〔1絕對裝入方式。絕對裝入方式是由裝入程序根據(jù)裝入模塊中的地址將程序和數(shù)據(jù)裝入內(nèi)存。程序中所使用的絕對地址,既可在編譯或匯編時給出,也可由程序員直接賦予。采用絕對裝入方式的前提是地址空間的容量要足夠且可用。這種方式對于單道程序是可行的。但對于多道程序來講,程序員需要準(zhǔn)確地了解內(nèi)存分區(qū)及使用的情況,正確定位程序或數(shù)據(jù)的內(nèi)存地址,避免沖突的發(fā)生,而且一旦程序或數(shù)據(jù)被修改后,可能需要改變程序中的所有地址?！?可重定位裝入方式?？芍囟ㄎ谎b入又稱靜態(tài)重定位裝入,裝入程序根據(jù)內(nèi)存當(dāng)前的實際使用情況,將裝入模塊裝入到內(nèi)存適當(dāng)?shù)牡胤?地址變換在裝入時一次完成。這種方式采用相對地址來存放程序和數(shù)據(jù)。一般設(shè)定程序的地址空間從0開始,當(dāng)需要裝入該程序時,通過轉(zhuǎn)換來確定它們在內(nèi)存中的實際位置?！?動態(tài)運(yùn)行時裝入方式。動態(tài)運(yùn)行時裝入又稱動態(tài)重定位裝入,在把裝入模塊裝入內(nèi)存后,并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址,而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進(jìn)行。因此,裝入內(nèi)存后的所有地址都仍是相對地址。為使地址轉(zhuǎn)換不影響指令的執(zhí)行速度,這種方式需要特殊硬件的支持。2.簡述基本分頁存儲管理的主要優(yōu)缺點。答：基本分頁存儲管理的主要優(yōu)點有：不要求作業(yè)或進(jìn)程的程序和數(shù)據(jù)在內(nèi)存中連續(xù)存放,從而有效地解決了碎片問題；提高了內(nèi)存的利用率,又有利于組織多道程序運(yùn)行。主要缺點有：采用動態(tài)地址轉(zhuǎn)換機(jī)構(gòu)降低了CPU的速度；由于作業(yè)的地址空間不一定是存儲塊的整數(shù)倍,因而最后一個存儲塊往往是裝不滿的,即出現(xiàn)了塊內(nèi)碎片問題；要求運(yùn)行的作業(yè)必須全部裝入內(nèi)存才能運(yùn)行,如果現(xiàn)有的空閑塊不足以滿足該作業(yè)的要求,作業(yè)只能等待,浪費了內(nèi)存空閑空間。3.什么是虛擬存儲器？虛擬存儲器具有哪些特征？答：所謂虛擬存儲器,是指具有請求調(diào)入功能和置換功能,把內(nèi)存和外存結(jié)合起來使用,能從邏輯上對內(nèi)存容量加以擴(kuò)充的一種存儲器系統(tǒng)。其邏輯容量和內(nèi)存大小無直接關(guān)系,主要由內(nèi)存容量和外存容量之和所決定,其運(yùn)行速度接近于內(nèi)存速度,而成本卻又接近于外存。虛擬存儲器的特征可以概括為以下4點：〔1離散性：裝入虛擬存儲器的進(jìn)程都是離散存放的,這是虛擬存儲器的基礎(chǔ)?！?多次性：一個作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行,即在作業(yè)運(yùn)行時沒必要將其全部裝入,只需將當(dāng)前要運(yùn)行的那部分程序和數(shù)據(jù)裝入內(nèi)存,以后每當(dāng)運(yùn)行到尚未調(diào)入的那部分程序時,再將它調(diào)入?！?對換性：允許在作業(yè)的運(yùn)行過程中進(jìn)行換進(jìn)、換出。在進(jìn)程運(yùn)行期間,允許將那些暫不使用的程序和數(shù)據(jù),從內(nèi)存調(diào)至外存的對換區(qū)〔換出,待以后需要時再將它們從外存調(diào)至內(nèi)存〔換進(jìn)。〔4虛擬性：指能夠從邏輯上擴(kuò)充內(nèi)存容量,虛擬出一個較大的邏輯空間,使用戶所看到的內(nèi)存容量遠(yuǎn)大于實際內(nèi)存容量。4.簡述分頁與分段的區(qū)別。答：分段和分頁的區(qū)別：段式管理和頁式管理都采用離散分配方式,且地址轉(zhuǎn)換都需要硬件的支持。但它們也存在以下幾個方面的不同：〔1頁是信息的物理單位,分頁是為了提高內(nèi)存的利用率,與源程序的邏輯結(jié)構(gòu)無關(guān),由系統(tǒng)自動完成,對用戶是不可見的；段是信息的邏輯單位,分段是為了滿足用戶的需要,段對用戶是可見的?！?頁的大小固定不變,由系統(tǒng)決定,頁只能以頁大小的整數(shù)倍地址開始；段的大小不固定,由用戶編寫的程序決定,段可以從內(nèi)存的任何地址開始?！?分頁的邏輯地址空間是一維的,用一個記憶符就可以表示一個地址；分段的地址空間是二維的,為了標(biāo)志一個地址,用戶必須給出段號和段內(nèi)地址?！?頁是信息的物理單位,頁的共享和保護(hù)受到限制；段是信息的邏輯單位,段可以充分實現(xiàn)共享和保護(hù)?！?段式管理與分區(qū)管理一樣可能產(chǎn)生內(nèi)存碎片,而頁式管理則能很好地消除碎片。5.常用的頁面置換算法有哪幾種？試比較它們的優(yōu)缺點。答：常用的頁面置換算法有最佳置換算法、先進(jìn)先出置換算法、最近最久未使用置換算法和Clock置換算法。最佳置換算法性能最好,是一種理想情況下的頁面置換算法,但無法實現(xiàn)；先進(jìn)先出置換算法簡單,易實現(xiàn),性能最差,可能出現(xiàn)Belady現(xiàn)象,淘汰駐留內(nèi)存時間最長的頁面,不實用；最近最久未使用置換算法性能較好,是對最佳置換算法最好的逼近,根據(jù)歷史信息選擇淘汰頁面,常被采用,但對硬件要求較高；Clock置換算法易發(fā)生缺頁中斷。6．試述缺頁中斷與一般中斷的區(qū)別。答：在計算機(jī)系統(tǒng)中,由于某些事件的出現(xiàn),打斷了當(dāng)前程序的運(yùn)行,而使CPU去處理出現(xiàn)的事件,這稱為"中斷"。通常,計算機(jī)的硬件結(jié)構(gòu)都是在執(zhí)行完一條指令后,去檢查有無中斷事件發(fā)生的。如果有,那么就暫停當(dāng)前程序的運(yùn)行,而讓CPU去執(zhí)行操作系統(tǒng)的中斷處理程序,這叫"中斷響應(yīng)"。CPU在處理完中斷后,如果不需要對CPU重新進(jìn)行分配,那么就返回被中斷進(jìn)程的程序繼續(xù)運(yùn)行；如果需要進(jìn)行CPU的重新分配,那么操作系統(tǒng)就會去調(diào)度新進(jìn)程。由上面的講述可以看出,缺頁中斷與一般中斷的區(qū)別如下?！?兩種中斷產(chǎn)生的時刻不同：缺頁中斷是在執(zhí)行一條指令中間時產(chǎn)生的中斷,并立即轉(zhuǎn)去處理；而一般中斷則是在一條指令執(zhí)行完畢后,當(dāng)硬件中斷裝置發(fā)現(xiàn)有中斷請求時才去響應(yīng)和處理?！?處理完畢后的歸屬不同：缺頁中斷處理完后,仍返回到原指令去重新執(zhí)行,因為那條指令并未執(zhí)行；而一般中斷則是或返回到被中斷進(jìn)程的下一條指令去執(zhí)行,因為上一條指令已經(jīng)執(zhí)行完了,或重新調(diào)度,去執(zhí)行別的進(jìn)程程序。三、簡答題1.在操作系統(tǒng)的設(shè)備管理中,為什么要引入緩沖？答：引入緩沖的主要原因有如下幾點：〔1引入緩沖可以進(jìn)一步改善CPU和I/O設(shè)備之間速度不匹配的情況?！?可以協(xié)調(diào)邏輯記錄大小和物理記錄大小不一致的問題?！?緩沖技術(shù)的引入還可以減少對CPU的中斷次數(shù),放寬CPU對中斷響應(yīng)時間的限制。2.簡述SPOOLing系統(tǒng)的主要特點。答：〔1提高了I/O的速度。從對低速I/O設(shè)備進(jìn)行的I/O操作變?yōu)閷斎刖蜉敵鼍牟僮?如同脫機(jī)操作一樣,提高了I/O速度,緩和了CPU與低速I/O設(shè)備速度不匹配的矛盾?！?將獨占設(shè)備改造為共享設(shè)備。因為在SPOOLing系統(tǒng)中,實際上并沒為任何進(jìn)程分配設(shè)備,而只是在輸入井或輸出井中為進(jìn)程分配一個存儲區(qū)和建立一張I/O請求表。這樣,便把獨占設(shè)備改造為共享設(shè)備?！?實現(xiàn)了虛擬設(shè)備功能。多個進(jìn)程同時使用一個獨享設(shè)備,而對每一進(jìn)程而言,都認(rèn)為自己獨占這一設(shè)備,不過,該設(shè)備是邏輯上的設(shè)備。3.磁盤調(diào)度算法有哪幾種？各自的特點是什么？〔1先來先服務(wù)<FCFS>。這是一種最簡單的磁盤調(diào)度算法。它根據(jù)進(jìn)程請求訪問磁盤的先后次序進(jìn)行調(diào)度。此算法的優(yōu)點是公平、簡單,且每個進(jìn)程的請求都能依次地得到處理,不會出現(xiàn)某一進(jìn)程的請求長期得不到滿足的情況。但此算法由于未對尋道進(jìn)行優(yōu)化,致使平均尋道時間可能較長?！?最短尋道時間優(yōu)先<SSTF>。該算法選擇這樣的進(jìn)程：其要求訪問的磁道與當(dāng)前磁頭所在的磁道距離最近,以使每次的尋道時間最短。但這種算法不能保證平均尋道時間最短?！?掃描<SCAN>算法。既能獲得較好的尋道性能,又能防止"饑餓"現(xiàn)象,故被廣泛用于大、中、小型機(jī)器和網(wǎng)絡(luò)中的磁盤調(diào)度。但SCAN也存在這樣的問題：當(dāng)磁頭剛從里向外移動而越過了某一磁道時,恰好又有一進(jìn)程請求訪問此磁道,這時,該進(jìn)程必須等待,待磁頭繼續(xù)從里向外,然后再從外向里掃描完所有要訪問的磁道后,才處理該進(jìn)程的請求,致使該進(jìn)程的請求被大大地推遲?！?循環(huán)掃描<CSCAN>算法。為了減少SCAN算法的延遲問題,CSCAN算法規(guī)定磁頭單向移動,例如,只是自里向外移動,當(dāng)磁頭移到最外的磁道并訪問后,磁頭立即返回到最里的欲訪問的磁道,亦即將最小磁道號緊接著最大磁道號構(gòu)成循環(huán),進(jìn)行循環(huán)掃描。三、簡答題1．簡述文件的概念及分類。答：文件是在邏輯上具有完整意義的信息集合,是信息的一種組織形式,是存儲在外存上的具有標(biāo)志名的一組相關(guān)信息的集合。也可以說文件是一組相似記錄的集合,它被用戶和應(yīng)用程序看作是一個實體,并可以通過名字訪問。常見的文件分類有以下幾種：按文件用途分類：〔1系統(tǒng)文件；〔2庫文件；〔3用戶文件。按存取控制權(quán)限分類：〔1只讀文件；〔2讀/寫文件；〔3可執(zhí)行文件；〔4不保護(hù)文件。按存放時限分類：〔1臨時文件；〔2永久文件；〔3檔案文件。按文件的信息流向分類：〔1輸入文件；〔2輸出文件；〔3輸入/輸出文件。按文件的組織形式分類：〔1普通文件；〔2目錄文件；〔3特殊文件。2.簡述文件、記錄和數(shù)據(jù)項三者間的關(guān)系。答：數(shù)據(jù)項是計算機(jī)中操作系統(tǒng)處理的最小信息單位,是基本數(shù)據(jù)單元；記錄是相關(guān)數(shù)據(jù)項的集合；文件是一組相似記錄的集合,它被用戶和應(yīng)用程序看作是一個實體,并可以通過名字訪問。即：文件是相關(guān)"記錄"的集合,而記錄是相關(guān)"數(shù)據(jù)項"的集合,數(shù)據(jù)項是文件中不可再分解的最小"數(shù)據(jù)單位"。3.文件控制塊包含哪些內(nèi)容？答：FCB一般應(yīng)該包括以下內(nèi)容：<1>有關(guān)文件存取控制的信息。如文件名、用戶名、文件主存取權(quán)限、授權(quán)者存取權(quán)限、文件類型和文件屬性,即讀寫文件、執(zhí)行文件、只讀文件等。<2>有關(guān)文件結(jié)構(gòu)的信息。文件的邏輯結(jié)構(gòu),如記錄類型、記錄個數(shù)、記錄長度、成組因子數(shù)等。文件的物理結(jié)構(gòu),如文件所在設(shè)備名,文件物理結(jié)構(gòu)類型,記錄存放在外存的相對位置或文件第一塊的物理塊號,也可指出文件索引的所在位置等。<3>有關(guān)文件使用信息。它包括已打開該文件的進(jìn)程數(shù)、文件被修改的情況、文件當(dāng)前大小等。<4>有關(guān)文件管理信息。如文件建立日期、文件最近修改日期、文件訪問日期、文件保留日期、記賬信息等。4.簡述文件目錄的作用。答：文件目錄一般包含文件控制塊和索引結(jié)點。文件目錄是文件系統(tǒng)的關(guān)鍵數(shù)據(jù)結(jié)構(gòu),它是文件系統(tǒng)實現(xiàn)"按名存取"的重要手段。為實現(xiàn)"按名存取",必須建立文件名與外存空間中的物理地址的對應(yīng)關(guān)系,體現(xiàn)這種對應(yīng)關(guān)系的數(shù)據(jù)結(jié)構(gòu)稱為文件目錄。5.什么是文件的邏輯結(jié)構(gòu)？答：文件的邏輯結(jié)構(gòu)就是從用戶觀點出發(fā)所見到的文件結(jié)構(gòu),通常分為兩種形式——記錄式文件和流式文件。記錄式文件在邏輯上總是被看成一組順序的記錄集合,是一種有結(jié)構(gòu)的文件組織。它又分成定長記錄文件和變長記錄文件。流式文件又稱無結(jié)構(gòu)文件,是指文件內(nèi)部不再劃分記錄。它是由一組相關(guān)信息組合成的有序字符流。6.簡述文件的檢索過程。答：每當(dāng)建立一個新文件時,系統(tǒng)就要為它設(shè)立一個FCB,其中記錄了這個文件的所有屬性信息。多個文件的FCB便組成了文件目錄,文件目錄也用文件形式保存起來,這個文件就是目錄文件。當(dāng)用戶要求存取某個文件時,系統(tǒng)查找目錄文件,先找到相對應(yīng)的文件目錄,然后,比較文件名就可以找到所尋文件的文件控制塊FCB〔文件目錄項,再通過FCB指出的文件的文件信息相對位置或文件信息首塊物理位置等,就能依次存取文件信息。7.簡述文件存儲空間管理的幾種常用的方法的優(yōu)缺點。答：文件存儲空間管理的幾種常用的方法：空閑表法、空閑鏈表法、位示圖法、成組鏈接法?？臻e表法在內(nèi)存分配上,雖然很少采用連續(xù)分配方式,然而在外在的管理中,由于它具有較高的分配速度,可以減少訪問磁盤的I/O頻率,因而在諸多分析方式中仍然占有一席之地?？臻e鏈表法是將所有空閑盤區(qū)拉成一條空閑鏈表。根據(jù)構(gòu)成鏈所用基本元素的不同,可以把鏈表分成兩種形式?？臻e盤塊鏈：這種方法的優(yōu)點是分配和回收一個盤塊的過程非常簡單,但在為一個文件分配盤塊時,可能要多次重復(fù)操作?？臻e盤區(qū)鏈：這是將磁盤上的所有空閑盤區(qū)〔每個盤區(qū)可包含若干個盤塊拉成一條鏈。在每個盤區(qū)上,除含有用于指示下一個空閑盤區(qū)的指針外,還應(yīng)有能指明本盤區(qū)大小〔盤塊數(shù)的信息。分配盤區(qū)的方法與內(nèi)存的動態(tài)分區(qū)分配類似,通常采用首次適應(yīng)算法。在回收盤區(qū)時,同樣也要將回收區(qū)與相鄰的空閑盤區(qū)合并。在采用首次適應(yīng)算法時,為了提高對空閑盤區(qū)的檢索速度,可以采用顯式鏈接方法,即在內(nèi)存中為空閑盤區(qū)建立一張鏈表。由于空閑表和空閑鏈表法在分配和回收空閑塊時,都需在外存上查找空閑塊號或鏈接塊號,這需經(jīng)過設(shè)備管理程序啟動外設(shè)才能完成。為提高空閑表的分配、回收速度,可以采用位示圖進(jìn)行管理。空閑表和空閑鏈表法不適用于大型文件系統(tǒng),因為這會使空閑塊表或空閑塊鏈太長。成組鏈接法是一種結(jié)合上述兩種方法而形成的空閑塊管理方法。通常在UNIX/Linux系統(tǒng)中采用。它的實現(xiàn)方法是：將若干個空閑塊歸為一組,將每組中的所有空閑塊號放入其前一組的第一個空閑塊號指示的磁盤塊中,而將第一組中的所有空閑塊號放入文件系統(tǒng)的超級塊中的空閑塊號表中。8．為什么在使用文件之前,總是先將其打開后再用？答：有關(guān)文件的信息都存放在該文件的FCB里,只有找到文件的FCB,才能獲得它的一切信息。但FCB是在磁盤里。因此,只要對文件進(jìn)行操作,就要到磁盤里去找它的FCB。這種做法,無疑影響了文件操作的執(zhí)行速度。正因為如此,操作系統(tǒng)才考慮在對文件進(jìn)行操作前,先將其打開,把文件的FCB內(nèi)容復(fù)制到內(nèi)存中來。這樣,查找文件的FCB,就不必每次都要去訪問磁盤。9.簡述常見的文件保護(hù)方法。答：通常,可以采用存取控制矩陣、存取控制表、權(quán)限表和口令等方法,來達(dá)到保護(hù)文件不受侵犯的目的。參見教材。二、簡答題1.簡述數(shù)據(jù)加密模型的含義。答：數(shù)據(jù)加密過程就是通過加密系統(tǒng)把原始的數(shù)字信息〔明文,通過數(shù)據(jù)加密系統(tǒng)的加密方法將其變換成與明文完全不同的數(shù)字信息〔密文的過程。密文經(jīng)過網(wǎng)絡(luò)傳輸?shù)竭_(dá)目的地后,再用數(shù)據(jù)加密系統(tǒng)的解密方法將密文還原成為明文。一個數(shù)據(jù)加密模型如下圖所示。它由4部分組成：〔1明文〔plaintext：被加密的文本稱為明文?！?密文〔ciphertext：加密后的文本稱為密文?！?加密〔解密算法：用于實現(xiàn)從明文〔密文到密文〔明文轉(zhuǎn)換的公式、規(guī)則或程序?！?密鑰：是一個具有特定長度的數(shù)字串,密鑰的值是從大量的隨機(jī)數(shù)中選取的。密鑰是加密和解密算法中的關(guān)鍵參數(shù)。2.簡述系統(tǒng)安全性的內(nèi)容與性質(zhì)。答：系統(tǒng)安全性包括３個方面的內(nèi)容,即邏輯安全、物理安全和安全管理。其中,邏輯安全是指系統(tǒng)中信息資源的安全；物理安全是指系統(tǒng)設(shè)備及相關(guān)設(shè)施受到物理保護(hù),使之免遭破壞或丟失；安全管理包括各種安全管理的政策和機(jī)制。邏輯安全包括以下幾方面:〔1保密性；〔2完整性；〔3可用性：要保證計算機(jī)網(wǎng)絡(luò)系統(tǒng)的安全、可靠,必須保證系統(tǒng)實體有安全的物理環(huán)境條件。這個安全的物理環(huán)境條件是指機(jī)房及其設(shè)施的安全,主要包括以下內(nèi)容：〔1計算機(jī)系統(tǒng)的環(huán)境條件?！?機(jī)房場地環(huán)境的選擇?！?機(jī)房的安全防護(hù)。系統(tǒng)安全性的性質(zhì)：系統(tǒng)安全問題涉及的面較廣,不僅與系統(tǒng)中所使用的硬件、軟件設(shè)備的安全性能有關(guān),而且與構(gòu)造系統(tǒng)時所采用的方法有關(guān),從而導(dǎo)致系統(tǒng)安全問題的性質(zhì)更為復(fù)雜,主要表現(xiàn)為多面性、動態(tài)性、層次性和適度性。3.簡要說明DES加密處理的過程。答：第一階段：先將明文分出64位的明文段,然后對64位明文段做初始易位處理,得到ｘ,將其左移32位,記為L0,右移32位,記為R0。第二階段：對初始易位結(jié)果X0進(jìn)行16次迭代處理,每一次使用56位加密密鑰Ki。輸出的左32位Li是輸入的右32位Ri-1的復(fù)制；而輸出的右32位Ri,則是在密鑰Ki的控制下,對輸入的右32位Ri-1做函數(shù)f的變換后的結(jié)果,再與輸入的左32位Li-1進(jìn)行異或運(yùn)算而形成的,即：Li=Ri－1Ri=f<Ri－1,Ki>⊕Li－1第三階段：把經(jīng)過16次迭代處理的結(jié)果<64位>的左32位與右32位互易位置。第四階段：進(jìn)行初始易位的逆變換。4.使用哪些方法可以提高用戶認(rèn)證的安全性？答：用以提高用戶認(rèn)證的安全性的方法有：使用加密技術(shù)和身份驗證、數(shù)字簽名、生物標(biāo)志的認(rèn)證技術(shù)、智能卡識別技術(shù)等。5.列舉幾種采用生物識別技術(shù)的認(rèn)證。答：指紋或聲音、智能卡。6.簡述如何進(jìn)行職業(yè)道德教育與法制建設(shè)。答：〔1為了保證計算機(jī)系統(tǒng)的安全,對從事計算機(jī)工作人員的職業(yè)道德教育也是十分重要的。國家必須制定出有關(guān)的準(zhǔn)則,從管理制度及社會宣傳教育等各方面綜合考慮加以解決。所有計算機(jī)用戶,特別是管理者,除了要加強(qiáng)業(yè)務(wù)學(xué)習(xí)外,更需要加強(qiáng)道德修養(yǎng)?！?由于計算機(jī)犯罪已經(jīng)是造成對國家安全、社會穩(wěn)定、財產(chǎn)金融、經(jīng)濟(jì)建設(shè)、私人保密權(quán)利等的巨大威脅,因此,國家必須從法律和政策上采取有效對策。而且,由于計算機(jī)犯罪的最大特點是高技術(shù)智能犯罪,對于熟悉計算機(jī)的人,掌握作案技術(shù)很容易,而且盜竊大量錢財和信息不易被發(fā)現(xiàn),甚至不留痕跡,這給偵破工作帶來了極大困難。這一犯罪特點也給傳統(tǒng)法律提出了新的問題,因為,原有法規(guī)中的內(nèi)容,用于裁定計算機(jī)犯罪時已很不適應(yīng),甚至有點牽強(qiáng)附會。因此,有必要制定新的法規(guī)?？傊?要想保證系統(tǒng)的安全,除了需要發(fā)展安全技術(shù)外,更需要培養(yǎng)用戶的安全意識,加強(qiáng)計算機(jī)專業(yè)人員的職業(yè)道德教育,以及完善防范計算機(jī)犯罪的法制建設(shè)。四、計算題1．有兩個用戶進(jìn)程A和B,在執(zhí)行過程中都要使用系統(tǒng)中同一臺打印機(jī)輸出各自的計算結(jié)果?！?試說明A、B兩進(jìn)程之間存在什么樣的制約關(guān)系？〔2為保證這兩個進(jìn)程能正確地打印出各自的結(jié)果,試寫出利用記錄型信號量機(jī)制實現(xiàn)進(jìn)程的同步算法。答：〔1A、B兩進(jìn)程之間存在互斥的制約關(guān)系。因為打印機(jī)屬于臨界資源,必須一個進(jìn)程使用完之后另一個進(jìn)程才能使用。〔2設(shè)mutex用于互斥的信號量,初值為1。進(jìn)程A進(jìn)程B......P<mutex>P<mutex>申請打印機(jī)申請打印機(jī)使用打印機(jī)使用打印機(jī)V<mutex>V<mutex>......2．有一個閱覽室,共有100個座位,用一張表來管理它,每個表目記錄座號和讀者姓名。讀者進(jìn)入時要先在表上登記,退出時要注銷登記。試用信號量及其P、V操作來描述各個讀者"進(jìn)入"和"注銷"工作之間的同步關(guān)系。解：在管理讀者"進(jìn)入"和"注銷"閱覽室的工作中,存在這樣一些制約關(guān)系：〔1100個座位是讀者共同使用的資源,因此要用一個資源分配信號量來管理它；〔2讀者"進(jìn)入"閱覽室時,要申請座位。只有申請到座位才能進(jìn)入,否則應(yīng)該等待到座位的釋放；〔3沒有讀者時,不能做"注銷"工作,必須等到有了讀者才能做。因此,可以設(shè)置兩個信號量：S1：初值為100,管理座位的分配；S2：初值為0,控制"注銷"與"進(jìn)入"間取得同步。"進(jìn)入"與"注銷"兩個進(jìn)程的流程如下圖所示。在讀者進(jìn)入時,調(diào)用"進(jìn)入"進(jìn)程,通過P<S1>來申請座位。如果申請到,就可以辦理閱覽手續(xù)。如果100個座位都申請完畢,那么第101個讀者就只有在關(guān)于S1的隊列上等待,等到有人調(diào)用"注銷"進(jìn)程執(zhí)行V<S1>。在有讀者離去時,就調(diào)用"注銷"進(jìn)程。四、計算題1.若在一基本分頁存儲管理系統(tǒng)中,某作業(yè)的頁表如下所示：頁號塊號01232316已知頁面大小為1024字節(jié),試將邏輯地址1011、2148、4000、5012轉(zhuǎn)化為相應(yīng)的物理地址。解：物理地址由頁號P和頁內(nèi)地址W兩部分組成,P等于邏輯地址除以頁面大小的除數(shù),W等于邏輯地址除以頁面大小的余數(shù),物理塊號和頁面大小相同。則邏輯地址為1011的物理地址算法如下：P=[1011/1024]=0,W=1011,據(jù)頁表可知頁號為0的頁對應(yīng)的是物理塊號為2的塊,所以物理地址=2*1024+1011=3059；同理,邏輯地址為2148的物理地址：P=[2148/1024]=2,W=100。頁號為2對應(yīng)物理塊號1,物理地址=1*1024+100=1124；邏輯地址為4000的物理地址：P=[4000/1024]=3,W=904。頁號為3對應(yīng)物理塊號6,物理地址=6*1024+904=7048；邏輯地址為5012的物理地址：P=[5012/1024]=4。頁號為4的頁面在頁表中沒有,所以要產(chǎn)生頁面中斷,請求將外存中的頁面調(diào)入內(nèi)存。2．在可變分區(qū)存儲管理中,按地址法組織當(dāng)前的空閑分區(qū),其大小分別為10KB,4KB,20KB,18KB,7KB,9KB,12KB和15KB,現(xiàn)在依次有3個存儲請求為12KB,10KB,9KB,問使用最先適應(yīng)算法時的分配情形如何