【正文】 6．目前常用的目錄結(jié)構(gòu)是哪種結(jié)構(gòu)。（4）允許文件共享。（3）允許文件重名。合理地組織目錄結(jié)構(gòu)，可加快目錄的檢索速度，從而提高文件的存取速度。這是目錄管理最基本的功能，也是文件系統(tǒng)向用戶提供的最基本的服務(wù)。操作系統(tǒng)對文件目錄管理通常有以下幾方面的要求：（1）實現(xiàn)“按名存取”。包括文件的建立日期及時間、上次存取文件的日期及時間、當(dāng)前的使用信息等。分別給出文件主、伙伴用戶、一般用戶的存取權(quán)限。其中用戶名主要是指文件主和授權(quán)用戶；而物理地址的內(nèi)容通常與文件的物理結(jié)構(gòu)有關(guān)，對于連續(xù)文件和鏈接文件，應(yīng)說明起始盤塊號，而對于索引文件，應(yīng)給出其索引塊號。（1）基本信息。然后再把索引表本身存放在另一個盤塊中，把這個存放索引表的盤塊稱為索引塊，并把索引塊的盤塊號作為文件的物理地址填入文件目錄項中。根據(jù)對鏈接指針處理方式的不同，鏈接文件又可分為隱式鏈接和顯示鏈接兩種。（2）鏈接文件：把一個邏輯上連續(xù)的文件分散存放在多個不要求連續(xù)的盤塊中，再使用鏈接指針將這多個可能不連續(xù)的盤塊鏈接起來，這樣形成的物理文件稱為鏈接文件。顯然，這種文件結(jié)構(gòu)保證了文件中邏輯記錄的順序與外存中文件占用盤塊的順序的一致性。3．什么是文件的物理結(jié)構(gòu)？文件的物理結(jié)構(gòu)有哪些？各有什么特點？參考答案：文件的物理結(jié)構(gòu)又稱為文件的存儲結(jié)構(gòu)，是指文件在外存上的存儲組織形式，它與存儲介質(zhì)的物理特性、文件的存取方法以及所采用的存儲空間的分配方式都有關(guān)。2．什么是文件的邏輯結(jié)構(gòu)？文件的邏輯結(jié)構(gòu)有哪些？參考答案：文件的邏輯結(jié)構(gòu)是從用戶觀點出發(fā)所觀察到的文件結(jié)構(gòu)，它獨立于文件的物理特性，用戶也是按照邏輯結(jié)構(gòu)來使用文件的。所謂文件系統(tǒng)是指被管理的文件、對文件進(jìn)行管理的一組軟件以及實現(xiàn)管理功能所需要的數(shù)據(jù)結(jié)構(gòu)的總體。（3）傳輸時間Tt：把數(shù)據(jù)從磁盤讀出或向磁盤寫入所需要的時間，它與磁盤的轉(zhuǎn)速以及要讀/寫的字節(jié)數(shù)有關(guān)。（2）旋轉(zhuǎn)延遲時間Tr：是指定扇區(qū)旋轉(zhuǎn)到磁頭下面所需要的時間，與磁盤轉(zhuǎn)速有直接關(guān)系，設(shè)r為磁盤轉(zhuǎn)速，則Tr平均＝1/(2r)。當(dāng)要求讀信息時，由輸入井讀程序從輸入井中找出作業(yè)所需信息并傳送給作業(yè)；當(dāng)作業(yè)要求輸出信息時，由輸出井寫程序把輸出信息存放到輸出井中。（3）井管理程序。預(yù)輸入程序的任務(wù)是預(yù)先把作業(yè)的全部信息輸入到磁盤上的輸入井中保存，作業(yè)執(zhí)行時只需從輸入井中讀入相關(guān)信息，而不必啟動輸入設(shè)備。這是在磁盤上開辟的兩個大的存儲區(qū)，輸入井用于預(yù)先存放從I/O設(shè)備輸入的各作業(yè)的全部信息，輸出井用于暫時存放各運行作業(yè)的輸出信息。參考答案：SPOOLing系統(tǒng)包括輸入井和輸出井、預(yù)輸入程序和緩輸出程序、井管理程序幾個部分，如圖4－6所示。重復(fù)上述過程，直到請求打印隊列為空，緩輸出程序就阻塞等待新的打印請求。如果還有其他用戶進(jìn)程請求打印輸出，系統(tǒng)仍可接收該請求，同樣為該進(jìn)程做上述兩件事。共享打印機是SPOOLing技術(shù)的典型應(yīng)用。④當(dāng)輸出進(jìn)程要輸出時，便從輸出隊列取得一個裝滿輸出數(shù)據(jù)的緩沖區(qū)，輸出其中的數(shù)據(jù)，數(shù)據(jù)輸出完后，再將其掛到空緩沖隊列末尾。②當(dāng)計算進(jìn)程需要輸入數(shù)據(jù)進(jìn)行計算時，便從輸入隊列取得一個緩沖區(qū)，從中提取數(shù)據(jù)進(jìn)行計算，數(shù)據(jù)用完后再將其掛到空緩沖隊列末尾。為管理方便，將所有緩沖區(qū)組織成三個隊列：①空緩沖隊列：由空緩沖區(qū)組成；②輸入隊列：由裝滿輸入數(shù)據(jù)的緩沖區(qū)組成；③輸出隊列：由裝滿輸出數(shù)據(jù)的緩沖區(qū)組成。（2）減少對CPU的中斷頻率，放寬CPU對中斷響應(yīng)時間的限制。8． 為什么要引入緩沖？簡述緩沖池的實現(xiàn)機制。另外，驅(qū)動程序與設(shè)備所采用的I/O控制方式緊密相關(guān)，如常用的中斷驅(qū)動方式和DMA方式的驅(qū)動程序就明顯不同。例如，可以為相同的多個終端配置一個驅(qū)動程序。參考答案：設(shè)備驅(qū)動程序最大的特點是與硬件特性緊密相關(guān)，它包括了所有與設(shè)備相關(guān)的代碼，因而其中的部分代碼必須用匯編語言編寫。當(dāng)進(jìn)程分配到設(shè)備、控制器和通道后，就可以進(jìn)行數(shù)據(jù)傳輸工作了。當(dāng)把控制器分配給進(jìn)程后，從該控制器的控制表中找到與其相連的通道的控制表，從其“狀態(tài)”字段可知該通道是否忙碌。若控制器忙，將該進(jìn)程插入控制器等待隊列；否則，將該控制器分配給進(jìn)程。（2）分配控制器。若設(shè)備忙，則查找第二個該類設(shè)備的控制表，僅當(dāng)所有該類設(shè)備都忙時，才把進(jìn)程插入該類設(shè)備的等待隊列上。（1）分配設(shè)備。 6． 簡述獨占設(shè)備的分配過程。（4） 通道控制方式，通道控制方式與DMA方式類似，也是一種以內(nèi)存為中心，實現(xiàn)設(shè)備與內(nèi)存直接進(jìn)行數(shù)據(jù)交換的控制方式。（3） DMA方式，主要用于塊設(shè)備的I/O控制。5． I/O控制方式有哪幾種？各有什么特點？參考答案：I/O控制方式包括：（1） 程序直接控制方式，用于早期沒有中斷硬件技術(shù)的系統(tǒng)中，其缺點是CPU與設(shè)備完全串行工作，而設(shè)備的速度遠(yuǎn)低于CPU，致使CPU大部分時間處于等待狀態(tài)，嚴(yán)重降低了CPU的利用率。3． 什么是設(shè)備獨立性？引入設(shè)備獨立性有什么好處？參考答案：用戶在編程時使用的設(shè)備與程序運行時實際使用的設(shè)備無關(guān)，稱為“設(shè)備獨立性”，設(shè)備獨立性能提高系統(tǒng)進(jìn)行設(shè)備分配時的適應(yīng)性和靈活性。第四章習(xí)題1． 設(shè)備管理的主要功能是什么？參考答案：設(shè)備管理的主要功能是：設(shè)備分配、緩沖管理、設(shè)備處理。16． 在一個請求分頁系統(tǒng)中，假設(shè)一個作業(yè)的頁面走向為4，3，2，1，4，3，5，4，3，2，1，5，若分配給該作業(yè)的物理塊數(shù)為4，假設(shè)當(dāng)前沒有任何頁面在內(nèi)存，分別采用FIFO和LRU頁面置換算法，試計算在運行過程中發(fā)生的缺頁次數(shù)和缺頁率，并比較所得結(jié)果。（1）計算邏輯地址9016所對應(yīng)的物理地址；（2）對邏輯地址12300，試給出其物理地址的轉(zhuǎn)換過程。15． 在一個請求分頁系統(tǒng)中，內(nèi)存容量為1MB，被劃分為256塊，每塊為4KB。（4） 最少使用（LFU）置換算法：該算法是LRU算法的近似算法。（3） 最近未使用（NUR）置換算法：該算法又被稱為Clock置換算法，是LRU算法的近似算法。（2） 最近最久未使用（LRU）置換算法：LRU置換算法是根據(jù)頁面調(diào)入內(nèi)存后的使用情況來選擇淘汰頁的，即它總是選擇最近一段時間內(nèi)最長時間沒有被訪問的頁面予以淘汰。14． 在請求分頁系統(tǒng)中，常用的頁面置換算法有哪些？各有何特點？參考答案：在請求分頁系統(tǒng)中，常用的頁面置換算法及其特點描述如下：（1） 先進(jìn)現(xiàn)出（FIFO）頁面置換算法：這是一種最簡單的置換算法，它總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。13． 在請求分頁系統(tǒng)中，頁表應(yīng)包括哪些數(shù)據(jù)項？每項的作用是什么？參考答案：在請求分頁系統(tǒng)中，頁表應(yīng)包括：頁號、物理塊號、狀態(tài)位、訪問位、修改位、外存地址。從用戶角度看，該系統(tǒng)所具有的內(nèi)存容量比實際內(nèi)存容量大得多，但這只是用戶的一種感覺，是虛的，故而得名虛擬存儲器。進(jìn)行地址轉(zhuǎn)換時，首先檢查段號是否超出段表長度，如果是，產(chǎn)生越界中斷；否則，使用段號檢索段表，找到對應(yīng)的段表項后，從中得到該段的頁表始址和頁表長度，再檢查頁號是否超出頁表長度，如果是，產(chǎn)生越界中斷；否則，使用頁號檢索頁表，找到對應(yīng)的頁表項后，從中得到該頁對應(yīng)的物理塊號，再與頁內(nèi)地址一起組成物理地址。（2）邏輯地址（4，800） 使用段號4查找段表，找到對應(yīng)的表項后，用段內(nèi)地址800與段長進(jìn)行比較，沒有越界，計算物理地址＝段始址＋段內(nèi)地址＝5400＋800＝620011． 簡述段頁式系統(tǒng)的地址變換過程。計算下列邏輯地址所對應(yīng)的物理地址：（0，311），（1，120），（2，230），（4，800）。 表3－3 作業(yè)頁表 表3－4 作業(yè)段表 表3－5 作業(yè)頁表頁號塊號段號段始址段長頁號塊號狀態(tài)03021006300151191350018012012102200150233136312003003－04154540011204－0參考答案：（1）邏輯地址378： 頁號＝378/4096＝0 頁內(nèi)地址＝378MOD4096＝378 用頁號0查找頁表，找到對應(yīng)的塊號為3，則物理地址為： 物理地址＝塊號頁面大小＋頁內(nèi)地址＝34096＋378＝12666 （2）邏輯地址15034： 頁號＝15034/4096＝3 頁內(nèi)地址＝5700MOD4096＝2746 用頁號3查找頁表，找到對應(yīng)的塊號為6，則物理地址為： 物理地址＝塊號頁面大?。搩?nèi)地址＝64096＋2746＝27322 （3）邏輯地址5700： 頁號＝5700/4096＝1 頁內(nèi)地址＝5700MOD4096＝1604 用頁號1查找頁表，找到對應(yīng)的塊號為9，則物理地址為： 物理地址＝塊號頁面大?。搩?nèi)地址＝94096＋1604＝38468 （4）邏輯地址30000： 頁號＝30000/4096＝7 頁內(nèi)地址＝30000MOD4096＝1328 用頁號3查找頁表，發(fā)現(xiàn)越界，發(fā)出越界中斷信號，終止程序運行。9． 在一分頁系統(tǒng)中，頁面大小為4KB，某個已裝入內(nèi)存的作業(yè)的頁表如表3－3所示。若未越界，則用段號檢索段表，找到對應(yīng)的表項后，從中得到該段的基址和段長，然后檢查段內(nèi)地址是否超出該段的段長，若超出，則發(fā)出“地址越界”中斷，停止執(zhí)行該指令。在系統(tǒng)中設(shè)置了一個段表寄存器，用于存放當(dāng)前執(zhí)行進(jìn)程的段表在內(nèi)存的始址和段表長度。8． 簡述分段系統(tǒng)的地址變換過程。（2） 頁的大小固定且由系統(tǒng)決定，是由機器硬件實現(xiàn)的；而段的長度卻不固定，決定于用戶所編寫的程序，通常由編譯程序在對源程序進(jìn)行編譯時，根據(jù)信息的性質(zhì)來劃分?？筛鶕?jù)下式由塊號計算出物理地址： 物理地址＝塊號塊長（即頁面大?。?頁內(nèi)地址7． 分頁和分段存儲管理有何區(qū)別？參考答案：（1）頁是信息的物理單位，分頁是為實現(xiàn)離散分配方式，以減少內(nèi)存的外零頭，提供內(nèi)存的利用率。與此同時，將邏輯地址中的頁內(nèi)地址直接送入物理地址寄存器的塊內(nèi)地址字段中，便得到了物理地址。每當(dāng)CPU要訪問內(nèi)存時，地址變換機構(gòu)會自動將邏輯地址分為頁號和頁內(nèi)地址兩部分，然后將頁號與頁表長度進(jìn)行比較，若頁號不小于頁表長度，說明本次所訪問的地址已超越進(jìn)程的地址空間，產(chǎn)生“地址越界”中斷，并停止執(zhí)行該指令。參考答案：在系統(tǒng)中設(shè)置了一個頁表寄存器，用于存放當(dāng)前執(zhí)行進(jìn)程的頁表在內(nèi)存的始址和頁表長度。引入對換的目的是為了提高內(nèi)存的利用率。已分配F1（100KB）已分配F2（50KB） 圖3－18 內(nèi)存使用情況示意圖參考答案：（1） 采用最先適應(yīng)算法分配：已分配作業(yè)A（30KB）作業(yè)B（70KB）已分配作業(yè)C（50KB）（2） 采用最優(yōu)適應(yīng)算法分配：已分配作業(yè)B（70KB）F1（30KB）已分配作業(yè)A（30KB）F2（20KB） 作業(yè)C沒有足夠的空閑分區(qū)分配，只有等待系統(tǒng)回收到足夠空閑內(nèi)存后再裝入內(nèi)存。4． 在可變分區(qū)存儲管理中，設(shè)作業(yè)A（30KB），作業(yè)B（70KB），作業(yè)C（50KB）依次請求內(nèi)存分配，內(nèi)存現(xiàn)有兩個空閑區(qū)：F1（100KB）和F2（50KB），如圖3－18所示。（3）最壞適應(yīng)算法。從所有空閑分區(qū)中挑選一個大小能滿足作業(yè)要求的最小分區(qū)，這樣可以保證不去分割一個更大的分區(qū)，使裝入大作業(yè)時比較容易得到滿足。該算法可能將大的空閑分區(qū)分割成多個小分區(qū)，從而使系統(tǒng)產(chǎn)生很多小得無法再用的“碎片”。該算法要求空閑分區(qū)表按各分區(qū)起始地址遞增的順序排列。（4）回收分區(qū)（記為R）與其前后的空閑分區(qū)（分別記為F1和F2）均不鄰接：在空閑分區(qū)表中增加一條記錄，該空閑分區(qū)的始址和大小，即為R的始址和大小。（2）回收分區(qū)（記為R）與其后面的空閑分區(qū)（記為F2）鄰接：合并R與F2，修改空閑分區(qū)表中F2的大小，即加上R的大小，始址不變。動態(tài)重定位是把程序裝入內(nèi)存后，并不立即將程序中的邏輯地址轉(zhuǎn)換為物理地址，而是在CPU執(zhí)行每一條指令時進(jìn)行地址轉(zhuǎn)換，程序裝入內(nèi)存后可移動位置，不必連續(xù)存放在一起，但是需要硬件地址變換機構(gòu)的支持。它有靜態(tài)重定位和動態(tài)重定位兩種方式。同樣，在進(jìn)行進(jìn)程切換時，需要保存當(dāng)前進(jìn)程的執(zhí)行環(huán)境，設(shè)置和恢復(fù)被調(diào)度進(jìn)程的執(zhí)行環(huán)境，而線程切換只需保存和設(shè)置少量寄存器的內(nèi)容，不涉及存儲管理方面的操作，因而進(jìn)程切換的開銷也遠(yuǎn)大于線程切換的開銷。（4）系統(tǒng)開銷。線程基本上不擁有資源（只有一點運行時必不可少的資源），但它可以訪問其所屬進(jìn)程的全部資源。（3）擁有資源。（2）并發(fā)性。而在引入線程后，則把線程作為調(diào)度和執(zhí)行的基本單位，把進(jìn)程作為資源分配和擁有的基本單位，把傳統(tǒng)進(jìn)程的兩個屬性分開，使線程輕裝運行，從而顯著提高系統(tǒng)的并發(fā)程度。（1）調(diào)度。在引入線程的操作系統(tǒng)中，通常一個進(jìn)程擁有若干個線程，至少也有一個線程。線程具有許多傳統(tǒng)進(jìn)程的特征，故又稱為輕型進(jìn)程。29． 什么是線程？簡述與進(jìn)程的區(qū)別和聯(lián)系。產(chǎn)生死鎖的必要條件有：互斥條件、占有且等待條件、不可剝奪條件、循環(huán)等待條件。 表2－6 各進(jìn)程到達(dá)就緒隊列的時刻、運行時間及優(yōu)先級進(jìn)程到達(dá)時刻運行時間優(yōu)先級P1P2P3P40123837121324參考答案：(1) 非搶占式優(yōu)先級調(diào)度算法調(diào)度順序進(jìn)程優(yōu)先級到達(dá)時刻運行時間開始時