西安交通大學(xué)操作系統(tǒng)+有答案

1、西安交通大學(xué)考試題成績課程操作系統(tǒng)原理（A 卷）學(xué)院考試日期年月日專業(yè)班號姓名學(xué)號期中期末注意：請將答案全部寫在答題紙上，寫在試卷和草稿紙上無效。一名詞解釋（每小題3 分，共 15 分）1. 信號量： 信號量是表示資源的實(shí)體，是一個(gè)與隊(duì)列有關(guān)的整型變量，其值僅能由P、V操作來改變。2. 死鎖： 死鎖是系統(tǒng)中一組進(jìn)程，該組進(jìn)程中的每一個(gè)進(jìn)程都占用了某些資源，而又都在無限等待該組中其它進(jìn)程釋放資源， 它們都無法向前推進(jìn)， 稱此時(shí)系統(tǒng)處于死鎖狀態(tài)或系統(tǒng)產(chǎn)生了死鎖。3. 系統(tǒng)調(diào)用：系統(tǒng)調(diào)用是操作系統(tǒng)為了擴(kuò)充機(jī)器功能、 增強(qiáng)系統(tǒng)能力、方便用戶使用而建立的。它作為操作系統(tǒng)與用戶編程時(shí)使用的接口。4. 虛擬

2、存儲器： 根據(jù)局部性原理，一個(gè)作業(yè)在運(yùn)行之前，沒有必要把全部作業(yè)裝入內(nèi)存，而僅將那些當(dāng)前要運(yùn)行的那部分頁面或段， 先裝入內(nèi)存便可啟動運(yùn)行， 其余部分暫時(shí)留在磁盤上 ,程序在運(yùn)行時(shí)如果用到時(shí)再裝入。這樣，便可使一個(gè)大的用戶程序在較小的內(nèi)存空間中運(yùn)行，也可使內(nèi)存中同時(shí)裝入更多的進(jìn)程并發(fā)執(zhí)行。從用戶角度看，該系統(tǒng)所具有的內(nèi)存容量，將比實(shí)際內(nèi)存容量大得多，人們把這樣的存儲器稱為虛擬存儲器。5. 設(shè)備獨(dú)立性： 為了提高 OS的可適應(yīng)性和可擴(kuò)展性， 目前幾乎所有的 OS都實(shí)現(xiàn)了設(shè)備的獨(dú)立性（也稱為設(shè)備無關(guān)性） 。其基本思想是：用戶程序不直接使用物理設(shè)備名（或設(shè)備的物理地址），而只能使用邏輯設(shè)備名；而系統(tǒng)在

3、實(shí)際執(zhí)行時(shí)，將邏輯設(shè)備名轉(zhuǎn)換為某個(gè)具體的物理設(shè)備名，實(shí)施 I/O 操作。二填空（每空 1 分，共 20 分）1.現(xiàn)代操作系統(tǒng)的兩個(gè)最基本的特征是并發(fā)性 和 共享性 。2.產(chǎn)生死鎖的必要條件是：互斥條件、請求保持 、不可剝奪條件和環(huán)路等待。3.磁盤存儲器空閑存儲空間的常用管理方法有：空閑表法，空閑鏈表法和位示圖。4.活動頭磁盤的訪問時(shí)間包括尋道時(shí)間、旋轉(zhuǎn)等待（延遲）時(shí)間和傳輸時(shí)間。5. 采用交換技術(shù)獲得好處是以犧牲時(shí)間 和 空間 為代價(jià)的。6.實(shí)現(xiàn)虛擬存儲器的理論基礎(chǔ)是局部性原理。7.在操作系統(tǒng)中引入線程的主要目的是提高系統(tǒng)效率、提高系統(tǒng)資源利用率、減少進(jìn)程并發(fā)執(zhí)行時(shí)所付出的時(shí)空開銷，使OS 具

4、有更好的并發(fā)性。8.在分區(qū)分配算法中，首次適應(yīng)算法傾向于優(yōu)先利用內(nèi)存中低地址部分的空閑分區(qū)。9. 在進(jìn)程中，訪問 臨界資源 的代碼稱為臨界區(qū)。10. 進(jìn)程控制塊的初始化工作包括初始化標(biāo)識符信息、 初始化處理機(jī)狀態(tài)信息和 進(jìn)程調(diào)度和控制信息 。11. I/O 進(jìn)行設(shè)備分配時(shí)所需的表格主要有系統(tǒng)設(shè)備表、設(shè)備控制表、控制器控制表和通道控制表。12.一臺計(jì)算機(jī)有 13 臺磁帶機(jī)，它們由 N 個(gè)進(jìn)程競爭使用，每個(gè)進(jìn)程可能需要4 臺磁帶機(jī)。 N 最大為 4 時(shí)系統(tǒng)沒有死鎖危險(xiǎn)。13.頁式存儲管理中，一個(gè)由4 個(gè)頁面，每頁有 512 個(gè)字節(jié)組成的邏輯空間，把它裝入到有32 個(gè)物理塊的存儲器中， 邏輯地址需要

5、211 位二進(jìn)制數(shù)來表示， 絕對地址需要214位二進(jìn)制數(shù)來表示。14.CPU 調(diào)度的任務(wù)是從就緒隊(duì)列中選擇一個(gè)進(jìn)程，把 CPU 分配給它。15.交換技術(shù)與虛擬存儲管理技術(shù)允許進(jìn)程部分裝入內(nèi)存就可以執(zhí)行。三判斷題，正確用T 表示，錯誤用 F 表示（每題 1 分，共 10 分）。1，分時(shí)系統(tǒng)中，時(shí)間片設(shè)得越小，則平均響應(yīng)時(shí)間越短。F2，一個(gè)進(jìn)程的狀態(tài)發(fā)生變化總會引起其他一些進(jìn)程的狀態(tài)發(fā)生變化。F3，為提高對換空間的利用率，一般對其采用離散的分配方式。T4，隱式鏈接結(jié)構(gòu)可以提高文件存儲空間的利用率，但不適合文件的隨機(jī)存取。T5，設(shè)備的獨(dú)立性是指每類設(shè)備有自己的設(shè)備驅(qū)動程序。F6，虛擬設(shè)備是指允許用戶

6、使用比系統(tǒng)中具有的物理設(shè)備更多的設(shè)備。T7，在內(nèi)存中就緒等待接受調(diào)度的進(jìn)程組成了等待隊(duì)列。F8，磁盤文件的訪問時(shí)間與磁頭的位置無關(guān)。F9，系統(tǒng)調(diào)用的執(zhí)行不能被中斷。F10，系統(tǒng)處于不安全狀態(tài)必然導(dǎo)致死鎖。F四簡答題（共25 分）1. 什么是文件目錄？文件目錄中包含哪些信息？常用的目錄結(jié)構(gòu)形式有哪幾種？（6 分）答：文件目錄記錄文件的管理信息，也稱文件控制塊FCB（ File Control Block ， FCB）。文件目錄通常包含以下三類內(nèi)容：（1）有關(guān)的文件結(jié)構(gòu)信息：邏輯結(jié)構(gòu)信息和物理結(jié)構(gòu)信息。（2）有關(guān)文件的管理信息 ：文件建立的日期和時(shí)間、文件要求保留的日期和時(shí)間、上一次存取文件的日期

7、和時(shí)間等 。（3）文件的存取控制權(quán)限信息：文件主（本人）所具有的存取權(quán)限；文件主、同組用戶所具有的存取權(quán)限；其它用戶的存取權(quán)限。常用的文件目錄結(jié)構(gòu)有： 單級目錄結(jié)構(gòu) （或稱簡單文件目錄）、二級目錄結(jié)構(gòu)和多級目錄結(jié)構(gòu)。共3頁第1 頁2. 畫出批處理系統(tǒng)作業(yè)和進(jìn)程的狀態(tài)和變遷圖，說明作業(yè)調(diào)度、進(jìn)程調(diào)度在每種狀態(tài)變遷中的功能。（ 7 分）SPOOLing 輸入程序SPOOLing 輸出程序執(zhí)行狀態(tài)運(yùn)行等度待提交后備調(diào)事完成程到件狀態(tài)進(jìn)狀態(tài)狀態(tài)預(yù)輸入完成作業(yè)調(diào)度片創(chuàng)建用戶進(jìn)程間作業(yè)運(yùn)行結(jié)束緩輸出時(shí)就緒阻塞撤消用戶進(jìn)程I/O 完成作業(yè)調(diào)度功能：作業(yè)調(diào)度程序負(fù)責(zé)作業(yè)從“后備狀態(tài)”到“執(zhí)行狀態(tài)”以及從“執(zhí)行

8、狀態(tài)”到“完成狀態(tài)”的轉(zhuǎn)換。作業(yè)調(diào)度程序?yàn)樽鳂I(yè)分配的是一臺虛擬的邏輯處理機(jī)。通常作業(yè)調(diào)度程序具有以下功能： 記錄系統(tǒng)中各個(gè)作業(yè)的情況，系統(tǒng)為每個(gè)作業(yè)建立一個(gè)作業(yè)控制塊。 按照某種調(diào)度算法從后備作業(yè)隊(duì)列中挑選作業(yè)。調(diào)度算法的好壞直接關(guān)系到系統(tǒng)的性能。調(diào)度時(shí)可以選擇對資源需求不同的作業(yè)進(jìn)行合理搭配，使得系統(tǒng)中各部分資源得到均衡利用。 為選中的作業(yè)分配內(nèi)存和外設(shè)等資源。作業(yè)調(diào)度程序在挑選作業(yè)進(jìn)程中要調(diào)用存儲管理程序和設(shè)備管理程序中的某些功能。 為選中的作業(yè)建立相應(yīng)的進(jìn)程。 作業(yè)結(jié)束后進(jìn)行善后處理工作。如輸出必要的信息，收回該作業(yè)所占有的全部資源，撤消該作業(yè)相關(guān)的全部進(jìn)程和該作業(yè)的JCB。進(jìn)程調(diào)度功能

9、：進(jìn)程調(diào)度主要任務(wù)是實(shí)現(xiàn)進(jìn)程從“就緒狀態(tài)”到“運(yùn)行狀態(tài)” 的轉(zhuǎn)變。它按照確定的進(jìn)程調(diào)度算法從就緒隊(duì)列中選擇一個(gè)進(jìn)程， 讓它占有 CPU 運(yùn)行。進(jìn)程調(diào)度程序?yàn)樽鳂I(yè)分配的是一臺真實(shí)的物理處理機(jī)。3. 操作系統(tǒng)為用戶提供哪些接口？它們的區(qū)別是什么？（ 5 分）操作系統(tǒng)為用戶提供了兩類接口。 一類是命令級接口， 供用戶組織和控制作業(yè)的執(zhí)行和管理計(jì)算機(jī)系統(tǒng)。 另一類是程序級接口， 供編程人員使用操作系統(tǒng)提供的系統(tǒng)調(diào)用來請求操作系統(tǒng)提供服務(wù)。4. 在一個(gè)不允許發(fā)生死鎖的系統(tǒng)中，通常會采用靜態(tài)方法或動態(tài)方法，請描述這兩種方法的原理，并分別給出一個(gè)典型算法。（7 分）答：保證系統(tǒng)不進(jìn)入死鎖狀態(tài)的靜態(tài)策略， 它

10、是在采用的資源分配策略中使發(fā)生死鎖的四個(gè)條件中的任何一個(gè)條件不成立，就可以預(yù)防死鎖的發(fā)生。如采用資源的靜態(tài)分配策略，要求每一個(gè)進(jìn)程在開始執(zhí)行前就要申請它所需要的全部資源， 僅當(dāng)系統(tǒng)能滿足進(jìn)程的資源申請要求時(shí)才把資源分配給進(jìn)程，該進(jìn)程才能開始執(zhí)行 （注意， 所有并發(fā)執(zhí)行的進(jìn)程要求的資源總和不能超過系統(tǒng)擁有的資源數(shù)） 。采用靜態(tài)分配策略后， 進(jìn)程在執(zhí)行中不再申請資源，因而，不會出現(xiàn)占有了某些資源再等待另一些資源的情況，即破壞了第二個(gè)條件（占有和等待條件）的出現(xiàn)，從而防止死鎖的發(fā)生。死鎖避免是保證系統(tǒng)不進(jìn)入死鎖狀態(tài)的動態(tài)策略。與死鎖預(yù)防策略不同，它不是對進(jìn)程申請資源施加任何限制，而是對于進(jìn)程發(fā)出的資

11、源申請加以動態(tài)檢查，并根據(jù)檢查結(jié)果決定是否分配資源。Dijkstra （ 1965 ）提出了一種能夠避免死鎖的調(diào)度方法，稱為銀行家算法。 銀行家算法是把操作系統(tǒng)比作銀行家， 操作系統(tǒng)管理的各種資源比作銀行的周轉(zhuǎn)資金， 申請資源的進(jìn)程比作向銀行借款的借款人。 銀行家占有有限的資金， 他不可能滿足所有客戶的請求， 但可以滿足一部分客戶的借款請求， 等這些客戶歸還后， 又可把這筆資金借給其他客戶， 其原則是不能使銀行家的錢被借完， 使資金無法周轉(zhuǎn)。五（ 10 分）假定一個(gè)磁盤有200 個(gè)柱面（編號 0-199），磁盤請求隊(duì)列由對如下柱面的請求序列構(gòu)成： 50, 60, 30, 18, 90, 165

12、, 150, 38, 12, 190.已知磁頭當(dāng)前位于 95 號柱面，移動方向?yàn)橄騼?nèi)。1.如果系統(tǒng)采用 SSTF 算法進(jìn)行調(diào)度，那么系統(tǒng)處理完上述所有的磁盤請求所需的尋道距離是多少？2.如果系統(tǒng)采用 SCAN 算法進(jìn)行調(diào)度，那么系統(tǒng)處理完上述所有的磁盤請求所需的尋道距離是多少？SSTFSCAN序號次序移動距離序號次序移動距離190511505526030216515350103190254381249010053085603061812650107126738128150138830891651591812101902510126移動總距離 = 261移動總距離 = 273第 2頁西安交通大學(xué)

13、考試題六（10 分） 設(shè)正在處理器上執(zhí)行的一個(gè)進(jìn)程的頁表如下表所示，表中的虛頁號和物理塊號是十進(jìn)制數(shù)，起始頁號（塊號）均為0。所有的地址均是存儲器字節(jié)地址。頁的大小為1024 字節(jié)。1. 詳述在設(shè)有快表的請求分頁存儲管理系統(tǒng)中， 一個(gè)虛地址轉(zhuǎn)換成物理內(nèi)存地址的過程。2. 下列十進(jìn)制虛地址對應(yīng)于什么物理地址： 5579，2232進(jìn)程的頁表虛頁號狀態(tài)位訪問位修改位物理塊號01104111172000-310024000-51010注： 當(dāng)某頁被訪問時(shí)，其訪問位置1。答： 1.1判斷是否越界，若是，則中斷，否則，繼續(xù)。2查找快表，若找著頁表項(xiàng)，則修改訪問位等，形成物理地址，結(jié)束。否則， 繼續(xù)。3查找

14、頁表，若找著頁表項(xiàng)，則修改訪問位等，形成物理地址，將該頁表項(xiàng)放入快表中，結(jié)束。否則，產(chǎn)成缺頁中斷，繼續(xù)。4若內(nèi)存不滿，則將找著的頁從外存調(diào)入內(nèi)存。否則，置換一頁出內(nèi)存，然后將找著的頁從外存調(diào)入內(nèi)存5修改頁表2十進(jìn)制虛地址 5579 對應(yīng)（ 5，459），由于虛頁號 5 對應(yīng) 0 塊，所以虛地址 5579 的物理地址是 459。十進(jìn)制虛地址 2232 對應(yīng)（ 2，184），虛頁號為 2，對應(yīng)的頁不在內(nèi)存中，故發(fā)出缺頁中斷。七（10 分） 某數(shù)據(jù)處理系統(tǒng)由數(shù)據(jù)采集、數(shù)據(jù)計(jì)算和數(shù)據(jù)輸出三個(gè)進(jìn)程組成，采集進(jìn)程把采集到的數(shù)據(jù)送入由M 個(gè)緩沖塊組成的輸入緩沖區(qū)（每次向一個(gè)緩沖塊送數(shù)據(jù)），計(jì)算進(jìn)程從輸入緩沖

15、區(qū)取數(shù)據(jù)計(jì)算（每次取一個(gè)緩沖塊的數(shù)據(jù)），并將計(jì)算結(jié)果送入到由N 個(gè)緩沖塊組成的輸出緩沖區(qū)（每次向一個(gè)緩沖塊送數(shù)據(jù)），輸出進(jìn)程每次從輸出緩沖區(qū)取一個(gè)結(jié)果輸出。編寫利用信號量機(jī)制實(shí)現(xiàn)的三者之間同步算法，要求寫出信號量的含義和初值。答.本題是采集進(jìn)程、數(shù)據(jù)計(jì)算進(jìn)程和數(shù)據(jù)輸出三個(gè)進(jìn)程共享二個(gè)緩沖區(qū)M和 N 。其中采集進(jìn)程是生產(chǎn)者，數(shù)據(jù)計(jì)算進(jìn)程既是生產(chǎn)者又是消費(fèi)者，數(shù)據(jù)輸出是消費(fèi)者。設(shè)置如下信號量和初值：mutex1:=mutex2:=1;avail1:=avail2:=1;full1:=full2:=0;這里 mutex1 和 mutex2 是兩個(gè)公用信號量，用于控制進(jìn)程對緩沖區(qū)M 和緩沖區(qū) N 這兩

16、個(gè)臨界資源訪問的互斥。avail1、full1 、avail2 和 full2 為兩組私用信號量，分別對應(yīng)兩個(gè)緩沖區(qū)，其中avail1 、 avail2 初值分別為m,n，表示可以利用的緩沖區(qū)數(shù)目；full1 、 full2的初值為0，表示存在于緩沖區(qū)內(nèi)的數(shù)據(jù)的個(gè)數(shù)為0。通過對這兩組私用信號量和P、V 操作，就實(shí)現(xiàn)了進(jìn)程的同步。采集進(jìn)程、數(shù)據(jù)計(jì)算進(jìn)程和數(shù)據(jù)輸出三個(gè)進(jìn)程協(xié)作解決問題的流程為:BEGINPARBEGIN采集進(jìn)程L1 ： read from disk;P(avail1);P(mutex1);put to buffer 1;V(full1);V(mutex1);goto L1;數(shù)據(jù)計(jì)算進(jìn)程L2 ： P(full1);