操作系統(tǒng)復(fù)習(xí)題計(jì)11修正

1、操作系統(tǒng)的功能：進(jìn)程管理存儲(chǔ)器管理設(shè)備管理文件管理用戶接口2、說明單道批處理系統(tǒng)和多道批處理的特點(diǎn)及優(yōu)缺點(diǎn)單道批處理系統(tǒng)：內(nèi)存中只有一道作業(yè)，可以成批處理作業(yè)。 特點(diǎn)：自動(dòng)性、順序性、單道性。優(yōu)點(diǎn)：減少等待人工操作的時(shí)間。缺點(diǎn)：作業(yè)獨(dú)占CPU，CPU等待I/O使得CPU利用率低。多道批處理系統(tǒng)：與單道批處理系統(tǒng)相比：多道程序駐留內(nèi)存；CPU不再空閑等待I/O。特點(diǎn)：多道性、無序性、調(diào)度性、復(fù)雜性優(yōu)點(diǎn)：提高CPU利用率；提高內(nèi)存和I/O設(shè)備的利用率；增加系統(tǒng)的吞吐量：吞吐量指系統(tǒng)在單位時(shí)間內(nèi)所完成的總工作量。缺點(diǎn)：平均周轉(zhuǎn)時(shí)間長；缺乏交互能力3、說明指令執(zhí)行的過程在每個(gè)指令周期開始的時(shí)候，處理器從存儲(chǔ)器中取

一條指令，在典型的處理器中，程序計(jì)數(shù)器（PC）保存有下一次要取的指令地址。除非接收到別的指

示，否則處理器在每次完成取指令后總是對(duì)PC增一，使它能夠按順序取得下一條指令。（即位于下一個(gè)

高端存儲(chǔ)器地址的指令）.取到的指令被放置在處

理器中的指令寄存器（IR）中。指令中包含確定處

理器將要采取動(dòng)作的位，處理器解釋指令并執(zhí)行要

求的動(dòng)作。4、什么是邏輯地址？什么是物理地址？

一個(gè)應(yīng)用程序（源程序）經(jīng)編譯后，通常會(huì)形成若干個(gè)目標(biāo)程序；這些目標(biāo)程序再經(jīng)過鏈接便形成了可裝入程序。這些程序的地址都是從“0”開始的，程序中的其它地址都是相對(duì)于起始地址計(jì)算的；由這些地址形成的地址范圍稱為“地址空間”，其中的地址稱為“邏輯地址”或“相對(duì)地址”。由內(nèi)存中的一系列單元所限定的地址范圍稱為“內(nèi)存空間”，其中的地址稱為“物理地址”。5、什么是實(shí)時(shí)計(jì)算？什么是實(shí)時(shí)系統(tǒng)？實(shí)時(shí)計(jì)算是這樣一類計(jì)算：計(jì)算的正確性不僅依賴于系統(tǒng)計(jì)算的邏輯結(jié)果，還依賴于產(chǎn)生這個(gè)結(jié)果的時(shí)間。實(shí)時(shí)系統(tǒng)是支持實(shí)時(shí)計(jì)算的系統(tǒng)。6、什么是嵌入式系統(tǒng)？什么是嵌入式操作系統(tǒng)？嵌入式操作系統(tǒng)的特征是什么？答：嵌入式系統(tǒng)是宿主于非計(jì)算機(jī)設(shè)備中的計(jì)算機(jī)系統(tǒng)。嵌入式操作系統(tǒng)是運(yùn)行于嵌入式設(shè)備中的操作系統(tǒng)。嵌入式操作系統(tǒng)具有以下特征：（1）小巧；（2）實(shí)時(shí)性；（3）可裝卸；（4）固化代碼；（5）弱交互性；（6）強(qiáng)穩(wěn)定性；（7）統(tǒng)一的接口。7、什么是并發(fā)？什么是共享？它們有什么關(guān)系？

并發(fā)是指兩個(gè)或多個(gè)事件在同一時(shí)間間隔內(nèi)發(fā)生。

共享是指系統(tǒng)中的資源可供內(nèi)存中多個(gè)并發(fā)執(zhí)行的進(jìn)程共同使用。

并發(fā)和共享是操作系統(tǒng)的兩個(gè)最基本的特征，它們又是互為存在的條件。一方面，資源共享是以程序的并發(fā)執(zhí)行為條件的，若系統(tǒng)不允許程序并發(fā)執(zhí)行，自然不存在資源共享問題。另一方面，若系統(tǒng)不能對(duì)資源共享實(shí)施有效管理，則也必然將影響程序的并發(fā)執(zhí)行，甚至根本無法并發(fā)執(zhí)行。8、什么是進(jìn)程?比較進(jìn)程與程序進(jìn)程的定義定義1：進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上的運(yùn)行過程。定義2：進(jìn)程是由正文段、用戶數(shù)據(jù)段以及系統(tǒng)數(shù)據(jù)段共同組成的一個(gè)執(zhí)行環(huán)境。比較進(jìn)程與程序區(qū)別：程序是靜態(tài)的概念，進(jìn)程是動(dòng)態(tài)的概念程序是永久的，進(jìn)程是暫時(shí)存在的

程序與進(jìn)程的存在實(shí)體不同.程序是指令的集合，進(jìn)程是由正文段、用戶數(shù)據(jù)段、系統(tǒng)數(shù)據(jù)段構(gòu)成的實(shí)體。聯(lián)系：

進(jìn)程是程序的一次執(zhí)行，進(jìn)程總是對(duì)應(yīng)一個(gè)特定的程序，執(zhí)行程序的代碼，一個(gè)進(jìn)程必然對(duì)應(yīng)一個(gè)程序。

一個(gè)程序可以對(duì)應(yīng)多個(gè)進(jìn)程。同一個(gè)程序段可以在不同的數(shù)據(jù)集合上運(yùn)行，因而構(gòu)成若干個(gè)不同的進(jìn)程。9、為什么要引入進(jìn)程這個(gè)概念？進(jìn)程存在的標(biāo)志是什么？

為了跟蹤描述程序的并發(fā)執(zhí)行，當(dāng)允許程序并發(fā)執(zhí)行時(shí)，并發(fā)執(zhí)行的程序可能是同一個(gè)程序在不同數(shù)據(jù)集合上的執(zhí)行，也可能是不同的程序在不同數(shù)據(jù)集合上的執(zhí)行，它們共享系統(tǒng)資源，用程序已不能方便地描述程序的并發(fā)執(zhí)行，所以引入了進(jìn)程的概念。標(biāo)志：進(jìn)程控制塊10、什么是進(jìn)程控制塊？舉例說明操作系統(tǒng)是如何利用進(jìn)程控制塊中的信息來管理進(jìn)程的？

進(jìn)程控制塊是進(jìn)程實(shí)體的一部分，是操作系統(tǒng)中最重要的記錄型數(shù)據(jù)結(jié)構(gòu)，PCB中記錄了操作系統(tǒng)所需要的，用于描述進(jìn)程情況及控制進(jìn)程運(yùn)行所需的全部信息。

例：Linux2.6.11內(nèi)核進(jìn)程控制塊task_struct的time_slice字段用來記錄進(jìn)程在CPU上的運(yùn)行時(shí)間，當(dāng)進(jìn)程被進(jìn)程調(diào)度程序選中開始運(yùn)行時(shí)，內(nèi)核為time_slice賦初值，每當(dāng)產(chǎn)生一次時(shí)鐘中斷，當(dāng)前運(yùn)行進(jìn)程的time_slice值減1，當(dāng)time_slice值減為0時(shí)，內(nèi)核為進(jìn)程設(shè)置調(diào)度標(biāo)志，并重新進(jìn)行一次進(jìn)程調(diào)度。內(nèi)核利用進(jìn)程控制塊的time_slice字段跟蹤和控制進(jìn)程在CPU上的執(zhí)行時(shí)間，以防止進(jìn)程超時(shí)使用CPU，獨(dú)占CPU資源。11、什么是操作系統(tǒng)內(nèi)核？操作系統(tǒng)內(nèi)核主要完成什么功能？

操作系統(tǒng)內(nèi)核是計(jì)算機(jī)硬件的第一次擴(kuò)充，內(nèi)核執(zhí)行OS與硬件關(guān)系密切，執(zhí)行頻率高的模塊，常駐

內(nèi)存。

不同的OS內(nèi)核包括的功能不同，多數(shù)OS內(nèi)核包括下述功能：?支撐功能：中斷處理、時(shí)鐘管理、原語操作?

資源管理功能：進(jìn)程管理、存儲(chǔ)器管理、設(shè)備管理12、操作系統(tǒng)在什么時(shí)候創(chuàng)建進(jìn)程？操作系統(tǒng)如何創(chuàng)建一個(gè)進(jìn)程？舉例說明操作系統(tǒng)創(chuàng)建進(jìn)程的過程和進(jìn)程執(zhí)行的功能。引起創(chuàng)建進(jìn)程的事件1、用戶登錄2、作業(yè)調(diào)度3、提供服務(wù)4、應(yīng)用請(qǐng)求進(jìn)程的創(chuàng)建調(diào)用創(chuàng)建新進(jìn)程的原語來創(chuàng)建進(jìn)程，一般步驟為：1、申請(qǐng)空白PCB。2、為新進(jìn)程分配資源。3、初始化進(jìn)程控制塊。4、將新進(jìn)程插入就緒隊(duì)列。統(tǒng)的啟動(dòng)和系統(tǒng)中進(jìn)程的出現(xiàn)13、說明什么是中斷？單重中斷的處理過程是什么？

中斷是改變處理器執(zhí)行指令順序的一種事件。這樣的事件與CPU芯片內(nèi)外部硬件電路產(chǎn)生的電信號(hào)相對(duì)應(yīng)。

中斷機(jī)制的工作原理是：計(jì)算機(jī)在執(zhí)行程序的過程中，當(dāng)出現(xiàn)異常情況或特殊請(qǐng)求時(shí)，計(jì)算機(jī)停止現(xiàn)行程序的運(yùn)行，轉(zhuǎn)向?qū)@些異常情況或特殊請(qǐng)求的處理，處理結(jié)束后再返回到現(xiàn)行程序的間斷處。單重中斷處理過程如下圖：14、時(shí)鐘中斷信號(hào)是如何產(chǎn)生的？時(shí)鐘中斷處理程序（時(shí)鐘驅(qū)動(dòng)程序）的功能是什么？時(shí)鐘中斷信號(hào)的產(chǎn)生：時(shí)鐘軟件—時(shí)鐘驅(qū)動(dòng)程序（時(shí)鐘中斷處理程序）的功能：?

維護(hù)日期、時(shí)間?

遞減時(shí)間片并檢查是否為零，防止進(jìn)程運(yùn)行超時(shí)?

對(duì)CPU的使用情況記帳?

遞減報(bào)警計(jì)數(shù)器。15、什么是進(jìn)程的就緒態(tài)、阻塞態(tài)、執(zhí)行態(tài)？在什么情況下發(fā)生三種狀態(tài)的轉(zhuǎn)換？就緒狀態(tài)：進(jìn)程一但獲得CPU就可以投入運(yùn)行的狀態(tài)。執(zhí)行狀態(tài)：進(jìn)程獲得CPU正在運(yùn)行的狀態(tài)。阻塞狀態(tài):進(jìn)程由于等待資源或某個(gè)事件的發(fā)生而暫停執(zhí)行的狀態(tài)。等待的事件發(fā)生cpu時(shí)間片用完就緒阻塞執(zhí)行獲得CPU等待某事件發(fā)生16、說明阻塞和喚醒的過程進(jìn)程阻塞過程1、暫停進(jìn)程的執(zhí)行，將進(jìn)程的狀態(tài)改為阻塞態(tài)2、將進(jìn)程插入相應(yīng)的阻塞隊(duì)列3、轉(zhuǎn)進(jìn)程調(diào)度例程，重新進(jìn)行進(jìn)程調(diào)度進(jìn)程喚醒過程1、將進(jìn)程從阻塞隊(duì)列中移出2、將進(jìn)程狀態(tài)由阻塞改為就緒3、將進(jìn)程插入就緒隊(duì)列17、什么是系統(tǒng)態(tài)和用戶態(tài)

用戶態(tài)執(zhí)行：用戶空間是指用戶進(jìn)程所處的地址空間，當(dāng)一個(gè)進(jìn)程在用戶空間執(zhí)行時(shí)，稱該進(jìn)程在用戶態(tài)執(zhí)行。

系統(tǒng)態(tài)執(zhí)行：系統(tǒng)核心空間是指含有一切系統(tǒng)核心代碼的地址空間，當(dāng)進(jìn)程處于具有執(zhí)行系統(tǒng)核心代碼的權(quán)力之狀態(tài)時(shí)，稱為進(jìn)程處于系統(tǒng)態(tài)執(zhí)行。18、什么是系統(tǒng)調(diào)用？舉例說明系統(tǒng)調(diào)用的執(zhí)行過程。答：系統(tǒng)調(diào)用是一群預(yù)先定義好的模塊,它們提供一條管道讓應(yīng)用程序或一般用戶能由此得到操作系統(tǒng)核心程序的服務(wù)。例：以Linux系統(tǒng)的系統(tǒng)調(diào)用為例說明系統(tǒng)調(diào)用的執(zhí)行過程如下：保存系統(tǒng)調(diào)用號(hào)執(zhí)行INT

0x80,進(jìn)程陷入內(nèi)核態(tài)執(zhí)行0X80中斷處理程序，以系統(tǒng)調(diào)用號(hào)為索引，在系統(tǒng)調(diào)用表中找到系統(tǒng)調(diào)用實(shí)現(xiàn)例程的起始地址。執(zhí)行系統(tǒng)調(diào)用例程，返回用戶態(tài)。19、為什么在操作系統(tǒng)中引入進(jìn)程同步機(jī)制？在多道程序環(huán)境下，進(jìn)程之間可能存在兩種關(guān)系：?

資源共享?

相互合作進(jìn)程同步的任務(wù)就是：在資源共享的情況下：保證諸進(jìn)程以互斥的方式訪問臨界資源—必須以互斥方式訪問的共享資源；在相互合作的關(guān)系中：進(jìn)程同步的主要任務(wù)是保證相互合作的諸進(jìn)程在執(zhí)行次序上協(xié)調(diào)。相互合作的進(jìn)程可能同時(shí)存在資源共享的關(guān)系。20、實(shí)現(xiàn)進(jìn)程互斥的基本原理是什么？

進(jìn)程互斥的目的是使進(jìn)程以互斥的方式訪問臨界資源，只要能使進(jìn)程以互斥的方式進(jìn)入臨界區(qū)就能夠保證進(jìn)程對(duì)臨界資源的互斥訪問。所以，可以通過在臨界區(qū)前加進(jìn)入?yún)^(qū)代碼，在臨界區(qū)后面加退出區(qū)代碼來實(shí)現(xiàn)進(jìn)程的互斥。臨界區(qū)是每個(gè)進(jìn)程中訪問臨界資源的那段代碼。進(jìn)入?yún)^(qū)是檢查是否可以進(jìn)入臨界區(qū)并對(duì)臨界區(qū)“加鎖”的代碼。退出區(qū)是釋放臨界區(qū)訪問權(quán)的代碼。21、說明記錄型信號(hào)量的物理意義

s.value>=0時(shí)，s.value的值表示資源數(shù)量；

s.value<0時(shí)，|s.value|的值表示某資源的等待隊(duì)列進(jìn)程的數(shù)量。22、寫出記錄型信號(hào)量的代碼描述答：記錄型信號(hào)量的數(shù)據(jù)類型Type

semaphore=record資源數(shù)量阻塞隊(duì)列Value:integerL:list

of

processendprocedure

wait(s)var

s:semaphorebegins.value:=s.value-1;if

s.value<0

thenblock(s.L)end.procedure

signal(s)var

s:semaphorebegins.value:=s.value+1;if

s.value<=0

thenwakeup(s.L)end.23、利用記錄型信號(hào)量機(jī)制寫出生產(chǎn)者-消費(fèi)者問題的進(jìn)程同步算法描述。24、利用記錄型信號(hào)量機(jī)制寫出讀者-寫者問題的同步算法描述。答案見教材。25、為什么在生產(chǎn)者-消費(fèi)者問題中wait操作的順序不能顛倒？

如果生產(chǎn)者和消費(fèi)者進(jìn)程都先通過執(zhí)行wait(mutex)申請(qǐng)公共緩沖池的互斥訪問權(quán)，然后通過申請(qǐng)資源信號(hào)量申請(qǐng)空緩沖區(qū)或裝滿產(chǎn)品的緩沖區(qū)，當(dāng)緩沖池滿時(shí)，若生產(chǎn)者進(jìn)程先申請(qǐng)到公共緩沖池的互斥訪問權(quán)，然后申請(qǐng)空緩沖區(qū)，因緩沖池中沒有空緩沖區(qū)，生產(chǎn)者進(jìn)程阻塞。消費(fèi)者進(jìn)程因無法申請(qǐng)到公共緩沖池的互斥訪問權(quán)，也會(huì)被阻塞。生產(chǎn)者進(jìn)程等待消費(fèi)者進(jìn)程釋放空緩沖區(qū)，消費(fèi)者進(jìn)程等待生產(chǎn)者進(jìn)程釋放公共緩沖池的互斥訪問權(quán)，進(jìn)程因互相等待對(duì)方釋放資源而處于不能執(zhí)行的僵持狀態(tài)。26、什么是進(jìn)程調(diào)度算法？

進(jìn)程調(diào)度算法：從多個(gè)就緒進(jìn)程中選擇一個(gè)進(jìn)程并為它分配cpu的算法。27、引起進(jìn)程調(diào)度的原因有哪些？

正在執(zhí)行的進(jìn)程執(zhí)行完畢；進(jìn)程阻塞；正在運(yùn)行的進(jìn)程時(shí)間片用完；在支持搶占式調(diào)度的系統(tǒng)中有優(yōu)先權(quán)高的進(jìn)程到來；中斷返回。28、說明什么是多級(jí)隊(duì)列調(diào)度算法、多級(jí)隊(duì)列調(diào)度：多級(jí)隊(duì)列調(diào)度是根據(jù)作業(yè)的性質(zhì)或類型的不同將就緒進(jìn)程隊(duì)列再分為若干個(gè)獨(dú)立子隊(duì)列，各個(gè)作業(yè)固定地分屬于一個(gè)隊(duì)列，每個(gè)隊(duì)列采用一種算法，不同的隊(duì)列可采用不同的調(diào)度算法。

29、說明選擇調(diào)度方式和調(diào)度算法的原則。答：可以下面的準(zhǔn)則作為選擇依據(jù)：周轉(zhuǎn)時(shí)間短響應(yīng)時(shí)間快截止時(shí)間的保證系統(tǒng)吞吐量高處理機(jī)利用率好30、說明什么是時(shí)間片輪轉(zhuǎn)調(diào)度算法？系統(tǒng)設(shè)計(jì)時(shí)如何確定時(shí)間片的大??？時(shí)間片大小的通常范圍值是多少？

答：在采用時(shí)間片輪轉(zhuǎn)調(diào)度算法的系統(tǒng)中，系統(tǒng)為進(jìn)程分配一定長度的時(shí)間片，每當(dāng)進(jìn)程在CPU上連續(xù)運(yùn)行的時(shí)間等于一個(gè)時(shí)間片長度，操作系統(tǒng)在時(shí)鐘中斷處理過程中會(huì)搶占CPU，進(jìn)行進(jìn)程切換，用新的就緒進(jìn)程替代當(dāng)前進(jìn)程，被替換的當(dāng)前進(jìn)程重新回到就緒隊(duì)列中。

在為調(diào)度程序確定時(shí)間片的大小時(shí)，通常要考慮到以下幾個(gè)因素：系統(tǒng)對(duì)響應(yīng)時(shí)間的要求；就緒隊(duì)列中進(jìn)程的數(shù)目；系統(tǒng)的處理能力；時(shí)間片是一個(gè)較小的時(shí)間單元，通常為10ms到100ms。31、什么是基于優(yōu)先權(quán)的進(jìn)程調(diào)度算法？在基于優(yōu)先權(quán)的進(jìn)程調(diào)度算法中如何為進(jìn)程給定優(yōu)先權(quán)值？

答：系統(tǒng)中的每個(gè)進(jìn)程都有一個(gè)與之關(guān)聯(lián)的優(yōu)先權(quán)，系統(tǒng)將CPU分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程。優(yōu)先權(quán)的類型分為靜態(tài)優(yōu)先權(quán)和動(dòng)態(tài)優(yōu)先權(quán)。靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)在創(chuàng)建時(shí)確定，在進(jìn)程的整個(gè)運(yùn)行期間保持不變。靜態(tài)優(yōu)先權(quán)值通?？梢愿鶕?jù)進(jìn)程的類型、進(jìn)程需要的資源數(shù)量、用戶的要求來設(shè)定。動(dòng)態(tài)優(yōu)先權(quán)進(jìn)程創(chuàng)建時(shí)被賦予的優(yōu)先權(quán)，隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變。動(dòng)態(tài)優(yōu)先權(quán)調(diào)度算法可以使系統(tǒng)獲得更好的調(diào)度性能。

32、什么是實(shí)時(shí)進(jìn)程的松弛度？正在運(yùn)行進(jìn)程的松弛度會(huì)發(fā)生變化嗎？在采用LLF調(diào)度算法的系統(tǒng)中如何解決松弛度相同的進(jìn)程調(diào)度問題？

答：參看p103最低松弛度優(yōu)先LLF（Least

LaxityFirst)算法一節(jié)。正在運(yùn)行進(jìn)程的松弛度不會(huì)發(fā)生變化。

當(dāng)兩個(gè)任務(wù)的松弛度相同時(shí)，應(yīng)該調(diào)度哪個(gè)進(jìn)程，需要其它條件的支持，比如任務(wù)的優(yōu)先權(quán)、截止時(shí)間等。33、什么是死鎖？引起死鎖的原因是什么？死鎖是由于多個(gè)進(jìn)程競爭共享資源而引起的進(jìn)程不能向前推進(jìn)的僵死狀態(tài)。產(chǎn)生死鎖的原因是：1、競爭共享資源；2、進(jìn)程推進(jìn)順序不當(dāng)；34、以生產(chǎn)者-消費(fèi)者問題為例說明死鎖是如何產(chǎn)生的。答：如果生產(chǎn)者和消費(fèi)者進(jìn)程都先通過執(zhí)行wait(mutex)申請(qǐng)公共緩沖池的互斥訪問權(quán)，然后通過申請(qǐng)資源信號(hào)量申請(qǐng)空緩沖區(qū)或裝滿產(chǎn)品的緩沖區(qū)，當(dāng)緩沖池滿時(shí)，若生產(chǎn)者進(jìn)程先申請(qǐng)到公共緩沖池的互斥訪問權(quán)，然后申請(qǐng)空緩沖區(qū)，因緩沖池中沒有空緩沖區(qū)，生產(chǎn)者進(jìn)程阻塞。消費(fèi)者進(jìn)程因無法申請(qǐng)到公共緩沖池的互斥訪問權(quán)，也會(huì)被阻塞。生產(chǎn)者進(jìn)程等待消費(fèi)者進(jìn)程釋放空緩沖區(qū)，消費(fèi)者進(jìn)程等待生產(chǎn)者進(jìn)程釋放公共緩沖池的互斥訪問權(quán)，進(jìn)程因互相等待對(duì)方釋放資源而處于不能執(zhí)行的僵持狀態(tài)。35、死鎖的四個(gè)必要條件是什么？死鎖預(yù)防的基本原理是什么？答：死鎖的四個(gè)必要條件是互斥條件請(qǐng)求和保持條件不剝奪條件環(huán)路等待條件死鎖預(yù)防的基本原理是：破環(huán)死鎖的四個(gè)必要條件之一36、說明銀行家算法的流程；教材p126圖5-3及p128圖5-437、什么是首次適應(yīng)算法？什么是最佳適應(yīng)算法？首次適應(yīng)算法FF：在采用空閑分區(qū)鏈作為數(shù)據(jù)結(jié)構(gòu)時(shí)，F(xiàn)F算法要求空閑分區(qū)鏈以地址遞增的次序鏈接。在進(jìn)行內(nèi)存分配時(shí)，從鏈?zhǔn)组_始順序查找，直至找到一個(gè)能滿足其大小要求的空閑分區(qū)為止。然后，再按照作業(yè)的大小，從該分區(qū)中劃出一塊內(nèi)存空間分配給請(qǐng)求者，余下的空閑分區(qū)仍留在空閑鏈中。最佳適應(yīng)算法：該算法每次為作業(yè)分配內(nèi)存，總是把既能滿足要求、又是最小的空閑分區(qū)分配給作業(yè)，避免了“大材小用”。為了加速尋找，該算法要求將所有的空閑區(qū)，按其大小以遞增的順序形成一空閑區(qū)。這樣，第一次找到的滿足要求的空閑區(qū)，必然是最優(yōu)的。38、說明分頁存儲(chǔ)管理的原理將一個(gè)進(jìn)程的邏輯地址空間分成若干個(gè)大小相等的片，稱為頁面或頁,將內(nèi)存空間分成與頁相同大小的若干個(gè)存儲(chǔ)塊，稱為物理塊,每個(gè)進(jìn)程頁面存在一個(gè)內(nèi)存物理塊中,頁號(hào)連續(xù)的頁面可以離散存放在物理塊號(hào)不連續(xù)的物理塊中.利用頁表實(shí)現(xiàn)邏輯地址到物理地址的映射.39、若給定一個(gè)邏輯地址空間的地址為A,系統(tǒng)頁面大小為L，請(qǐng)寫出A所對(duì)應(yīng)的頁號(hào)P和頁內(nèi)偏移地址W的運(yùn)算式；說明分頁存儲(chǔ)管理的地址映射過程。答：若A為邏輯地址，L為頁面大小，P為頁號(hào)，W為頁內(nèi)偏移量，有以下計(jì)算關(guān)系：P=INT(A/L)W=

MOD

(A/L)分頁存儲(chǔ)管理的地址映射過程說明如下：進(jìn)程執(zhí)行，PCB塊中頁表起始地址和頁表長度送頁表寄存器。CPU訪問邏輯單元a。由分頁地址變換機(jī)構(gòu)自動(dòng)將a分為頁號(hào)和頁內(nèi)地址兩部分由硬件檢索機(jī)構(gòu)搜索頁表，得到物理塊號(hào)。搜索原理：頁號(hào)對(duì)應(yīng)的頁表項(xiàng)地址=頁表始地址+頁表項(xiàng)長度*頁號(hào)。(頁表項(xiàng)中存有物理塊號(hào))。物理塊號(hào)和頁內(nèi)地址送物理地址寄存器。{內(nèi)存進(jìn)程PCB頁表起始地址頁表長度進(jìn)程執(zhí)行時(shí)頁表寄存器硬件檢索搜索0

3頁表1

72

8頁表頁表始址+頁號(hào)*頁表項(xiàng)長度=頁號(hào)的頁表項(xiàng)在內(nèi)存中的地址a的物理塊號(hào)分頁地址變換a的頁號(hào)a的頁內(nèi)地址進(jìn)程訪存(如：CPU訪存從進(jìn)程提供的邏輯單元中取數(shù)時(shí))a為邏輯地址。物理地址寄存器a的物理地址(=物理塊首地址+頁內(nèi)地址)物理塊首地址=物理塊號(hào)*塊大小頁表起始地址頁表長度40、什么是快表？說明引入快表后的地址映射過程。答：快表是為了提高CPU訪存速度而采用的專用緩存，用來存放最近被訪問過的頁表項(xiàng)。引入快表后的地址映射過程：CPU產(chǎn)生邏輯地址后，將該邏輯地址所在的頁號(hào)提交給TLB。查找TLB，如果找到頁號(hào)，則把該頁所在的物理塊號(hào)用于形成物理地址。否則（TLB失效），查找內(nèi)存頁表，從內(nèi)存頁表中找到相應(yīng)的頁表項(xiàng)，讀取頁面所在的物理塊號(hào)，以形成物理地址。如果所查找的頁表項(xiàng)不在TLB中，在訪問完內(nèi)存頁表后，要把找到的頁表項(xiàng)中的頁號(hào)和物理塊號(hào)寫到TLB中。如果TLB中的條目已滿，操作系統(tǒng)會(huì)根據(jù)某種策略（如：最近最少使用替換）選擇一個(gè)TLB中的條目，用剛訪問的頁表項(xiàng)信息替換選中的這個(gè)TLB條目。41、若CPU訪問內(nèi)存的速度為120ns,訪問TLB的速度為20ns,試比較有TLB和無TLB系統(tǒng)的有效訪問時(shí)間。答案見教材P160頁例4.42、請(qǐng)分別說明使用一級(jí)頁表和二級(jí)頁表的地址映射過程。答：使用一級(jí)分頁的地址映射過程見37題使用二級(jí)頁表的地址映射的過程如下：對(duì)于給定的邏輯地址A，由硬件從中分離出外部頁號(hào)p1、外層頁內(nèi)地址p2、頁內(nèi)地址d。由頁表寄存器的值和外部頁號(hào)p1，從存放外層頁表的物理塊中找到頁表分頁所在的物理塊號(hào)。、由頁表分頁所在的物理塊號(hào)和外層頁內(nèi)地址p2，從存放頁表分頁的物理塊中找到進(jìn)程頁面所在的物理塊號(hào)。、由A所在的進(jìn)程頁面的物理塊號(hào)×物理塊大小+頁內(nèi)地址d得到A的物理地址。43、說明分段存儲(chǔ)管理中的地址變換過程。答：若已知邏輯單元的地址為S:d，求相應(yīng)物理地址的步驟概括如下：以段號(hào)S做索引，從段表中找到段號(hào)為S的段表項(xiàng)。

從找到的段表項(xiàng)中讀出S段的基地址和段大?。ǘ谓缦蓿?。

如果d≤段大小，則將段基址與段內(nèi)偏移d相加，得到與邏輯單元S:d相應(yīng)的物理單元地址。44、分頁和分段機(jī)制的主要區(qū)別是什么？答：主要區(qū)別是：1、頁是按物理單位劃分的,段是按邏輯單位劃分的。2、頁的大小是固定的，段的大小不固定。3、分頁的地址空間是一維的，分段的地址空間是二維的。45、引入段頁式存儲(chǔ)管理方式的原因是什么？答：為了使存儲(chǔ)系統(tǒng)既具有分段系統(tǒng)便于編程、分段共享、易于保護(hù)、可動(dòng)態(tài)鏈接等一系列優(yōu)點(diǎn)；又能象分頁系統(tǒng)那樣很好地解決內(nèi)存的外部碎片問題，以及為各個(gè)分段可離散地分配內(nèi)存等問題，引入了“段頁式系統(tǒng)”。46、什么是虛擬存儲(chǔ)系統(tǒng)？虛擬存儲(chǔ)系統(tǒng)有什么特征？答：虛擬存儲(chǔ)系統(tǒng)是指具有請(qǐng)求調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量進(jìn)行擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。47、熟悉頁面置換策略和各種置換算法48、舉例說明進(jìn)程擁有的最小物理塊數(shù)與哪些因素有關(guān)？保證進(jìn)程正常運(yùn)行所需要的最少物理塊數(shù)與計(jì)算機(jī)的硬件結(jié)構(gòu)有關(guān)，取決于指令的格式、功能和尋址方式。例如：一個(gè)支持16位指令格式的機(jī)器，采用直接尋址方式，用高8位表示操作碼，低8位表示操作數(shù)，如果內(nèi)存單元以一個(gè)8位字節(jié)作為一個(gè)編址單元，當(dāng)采用直接尋址方式時(shí)，上面的指令本身可能涉及兩個(gè)頁面，操作數(shù)部分的地址可能涉及第三個(gè)頁面，這樣的的情況下，至少要為進(jìn)程分配三個(gè)物理塊，才能保證進(jìn)程正常執(zhí)行。如果采用間接尋址方式，操作數(shù)部分的地址指向的內(nèi)存單元中存放的是另外一個(gè)地址，這時(shí)指令涉及的頁面數(shù)最多可能達(dá)到四個(gè)（假設(shè)地址和數(shù)據(jù)都只占一個(gè)字節(jié)），即：指令本身可能涉及兩個(gè)頁面，操作數(shù)部分的地址可能涉及第三個(gè)頁面，操作數(shù)地址中存放的內(nèi)存地址可能涉及第四個(gè)頁面。這時(shí)，系統(tǒng)必須為進(jìn)程分配至少四個(gè)物理塊才能保證進(jìn)程正常執(zhí)行。49、說明請(qǐng)求分頁機(jī)制中的頁表中各字段的含義和用途答：對(duì)頁表項(xiàng)中的各字段說明如下：–頁號(hào)：作為地址映射時(shí)的索引。–物理塊號(hào)：頁面在物理內(nèi)存中的物理塊編號(hào)。–狀態(tài)位P：用來標(biāo)識(shí)頁面是否在內(nèi)存中。–訪問字段A：用于記錄頁面最近被訪問的情況。–修改位M：用于標(biāo)識(shí)頁面最近是否被修改過。–外存地址：用于指出頁面在外存中的地址。50、為什么選擇最近既沒有被訪問也沒有被修改的頁面作為淘汰頁？答：因?yàn)樽罱鼪]有被訪問的頁面在將來被訪問的可能性小，選擇這樣的頁面換出能降低缺頁率。沒有被修改的頁面換出時(shí)不需要把頁面內(nèi)容寫回磁盤，避免了訪問磁盤造成的時(shí)間開銷。51、在虛擬存儲(chǔ)系統(tǒng)中，若進(jìn)程在內(nèi)存中占3塊（開始時(shí)為空），當(dāng)執(zhí)行訪問頁號(hào)序列為1、2、3、4、1、2、5、1、2、3、4、5、6時(shí)，請(qǐng)畫出分別采用LRU和FIFO置換算法的置換圖。答案參考P190-191頁52.舉例說明文件系統(tǒng)所能管理的文件大小是由什么決定的？例如：FAT12采用12位文件分配表，簇塊大小是連續(xù)的四個(gè)扇區(qū)，可以管理的磁盤容量是。4096clusters×4sectors×512bytes

=8M可以管理的文件最大也是8

M。53、舉例說明文件系統(tǒng)是如何實(shí)現(xiàn)文件的按名存取的。答：在類Unix操作系統(tǒng)中目錄文件中存有子目錄文件和用戶文件的文件名和i結(jié)點(diǎn)號(hào)，先以文件名為索引在

目錄文件中找到文件的i結(jié)點(diǎn)號(hào)，根據(jù)i結(jié)點(diǎn)號(hào)可以找

到該文件的i結(jié)點(diǎn)，其中包含了文件的屬性和地址信息。54、Ext2文件系統(tǒng)的一個(gè)i結(jié)點(diǎn)包括15個(gè)地址項(xiàng)，每個(gè)地址項(xiàng)存32位地址（4個(gè)字節(jié)），其中12個(gè)地址項(xiàng)存直接地址；一個(gè)地址項(xiàng)存一次間接地址；一個(gè)地址項(xiàng)存二次間接地址，一個(gè)地址項(xiàng)存三次間接地址。當(dāng)一個(gè)邏輯塊大小為4k時(shí)，

EXT2能管理的文件的最大長度是多少？答案參考教材：P211-212頁55、說明設(shè)備控制器的結(jié)構(gòu)和功能答：設(shè)備控制器的功能說明如下：接收和識(shí)別命令數(shù)據(jù)交換。將控制器對(duì)設(shè)備的控制命令傳送給設(shè)備控制器。設(shè)備狀態(tài)的了解和報(bào)告地址識(shí)別數(shù)據(jù)緩沖差錯(cuò)控制56、設(shè)備控制器的組成設(shè)備控制器的邏輯構(gòu)成主要包括以下三個(gè)部分：1、設(shè)備控制器與處理機(jī)的接口：數(shù)據(jù)線、控制線、地址線。2、設(shè)備控制器與設(shè)備的接口：設(shè)備與設(shè)備控制器接口中的三類信號(hào)為數(shù)據(jù)、狀態(tài)和控制信號(hào)。3、I/O邏輯：I/O