計算機操作系統試題一填空:1．操作系統為用戶提供三種類型的使用接口,它們是命令方式和系統調用和圖形用戶界面。2．主存儲器與外圍設備之間的數據傳送控制方式有程序直接控制、中斷驅動方式、ＤMA方式和通道控制方式。３.在響應比最高者優先的作業調度算法中,當各個作業等待時間相同時,運營時間短的作業將得到優先調度;當各個作業規定運營的時間相同時,等待時間長的作業得到優先調度。4．當一個進程獨占解決器順序執行時，具有兩個特性：封閉性和可再現性。6．文獻的邏輯結構分流式文獻和記錄式文獻二種。７.進程由限度、數據和FCB組成。8.對信號量S的操作只能通過原語操作進行，相應每一個信號量設立了一個等待隊列。9．操作系統是運營在計算機裸機系統上的最基本的系統軟件。１0.虛擬設備是指采用SPOOLIＮG技術,將某個獨享設備改善為供多個用戶使用的的共享設備。11．文獻系統中,用于文獻的描述和控制并與文獻一一相應的是文獻控制塊。12.段式管理中，以段為單位,每段分派一個連續區。由于各段長度不同，所以這些存儲區的大小不一,并且同一進程的各段之間不規定連續。1３．邏輯設備表(LUT）的重要功能是實現設備獨立性。14在采用請求分頁式存儲管理的系統中，地址變換過程也許會由于缺頁和越界等因素而產生中斷。17．文獻的物理結構分為順序文獻、索引文獻和索引順序文獻。1８．所謂設備控制器,是一塊能控制一臺或多臺外圍設備與CPＵ并行工作的硬件。19.

UNIX的文獻系統空閑空間的管理是采用成組鏈接法。2０分頁管理儲管理方式能使存儲碎片盡也許少,并且使內存運用率較高，管理開銷小。20.

計算機操作系統是方便用戶、管理和控制計算機軟硬件資源的系統軟件。21.

操作系統目前有五大類型：批解決操作系統、分時操作系統、實時操作系統、網絡操作系統和分布式操作系統。22.按文獻的邏輯存儲結構分，文獻分為有結構文獻，又稱為記錄式文獻和無結構文獻,又稱流式文獻。２3.主存儲器與外圍設備之間的信息傳送操作稱為輸入輸出操作。2４、在設備管理中，為了克服獨占設備速度較慢、減少設備資源運用率的缺陷，引入了虛擬分派技術，即用共享設備模擬獨占設備。2５、常用的內存管理方法有分區管理、頁式管理、段式管理和段頁式管理。２６、動態存儲分派時，要靠硬件地址變換機構實現重定位。２7、在存儲管理中常用虛擬存儲器方式來擺脫主存容量的限制。28、在請求頁式管理中，當硬件變換機構發現所需的頁不在內存時，產生缺頁中斷信號，中斷解決程序作相應的解決。29、置換算法是在內存中沒有空閑頁面時被調用的，它的目的是選出一個被淘汰的頁面。假如內存中有足夠的空閑頁面存放所調入的頁，則不必使用置換算法。30、在段頁式存儲管理系統中,面向用戶的地址空間是段式劃分，面向物理實現的地址空間是頁式劃分。31、文獻的存儲器是提成大小相等的物理塊,并以它為單位互換信息。32、虛擬設備是通過SPＯOLiｎｇ技術把獨占設備變成能為若干用戶共享的設備。３3、緩沖區的設立可分為單緩沖、雙緩沖、多緩沖和緩沖池。34、在多道程序環境中，用戶程序的相對地址與裝入內存后的實際物理地址不同,把相對地址轉換為物理地址,這是操作系統的地址重地位功能。35．在操作系統中，進程是一個資源分派的基本單位，也是一個獨立運營和調度的基本單位。３6.在信號量機制中，信號量S>0時的值表達可用資源數目;若S<０,則表達等待該資源的進程數，此時進程應阻塞。37.操作系統提供應編程人員的唯一接口是系統調用。３8.設備從資源分派角度可分為獨占設備，共享設備和虛擬設備。39.設備管理的重要任務是控制設備和CPU之間進行Ｉ/O操作。40．常用的文獻存取方法有順序存取法,隨機存取法和按鍵存取法。4１.在頁面置換算法中最有效的一種稱為LＲU算法。42.地址變換機構的基本任務是將虛地址空間中的邏輯地址變換為內存中的物理地址。4４.現代操作系統的兩個重要特性是并發和共享。47.操作系統的基本類型有批解決操作系統,分時操作系統和實時操作系統三種。48.采用對換方式在將進程換出時,應一方面選擇處在阻塞且優先權低的進程換出內存。４9.能方便實現信息共享的存儲管理辦法有段式和段頁式。50.選擇距當前磁頭最近,且方向一致的磁盤調度算法循環掃描算法。51.在頁面置換算法中可實現的最有效的一種稱為ＬRU。5４.在成組鏈結法中，將第一組的空閑塊號和該組的空閑塊數目記入到內存的工作棧中，作為當前可供分派的空閑盤塊號。54.現代操作系統的兩個重要特性是并發和共享。５5.為文獻filｅ增長執行權限的UNＩX命令為ｃhmｏd+xfile。56．顯示目錄myｄiｒ中文獻的具體信息的UＮIX命令為ls–lmyｄir。57．在動態分區式內存分派算法中,傾向于優先使用低地址部分空閑區的算法是初次適應算法；能使內存空間中空閑區分布較均勻的算法是循環初次適應算法。58.在分時系統中，當用戶數目為１０0時,為保證響應時間不超過2秒,此時時間片最大應為20ms。分時系統采用的調度方法是時間片輪轉調度算法。５９．常用的進程通信方式有管道、共享存儲區、消息機制和郵箱機制。6０.正在執行的進程等待I/O操作,其狀態將由執行狀態變為阻塞狀態。61.頁是信息的物理單位,進行分頁是出于系統管理的需要;段是信息的邏輯單位，分段是出于用戶的需要。62．存儲管理中的快表是指聯想存儲器。６3.分段保護中的越界檢查是通過段表寄存器中存放的段表長度和段表中的段長等數據項。６4.在請求調頁系統中的調頁策略有預調入策略，它是以預測為基礎的;另一種是請求調入,由于較易實現,故目前使用較多。６５．若干個事件在同一時刻發生稱為并行,若干個事件在同一時間間隔內發生稱為并發。6６．使用緩沖區能有效地緩和Ｉ/O設備和ＣPＵ之間速度不匹配的矛盾。６7．用戶編寫的程序與實際使用的物理設備無關，而由操作系統負責地址的重定位,我們稱之為設備無關性(設備獨立性)。6８.用戶是通過命令方式或者程序接口向計算機發出請求的。６9.在操作系統中的異步性重要是指在系統中進程推動的順序是走走停停。70．進程間通信的方式有管道、共享存儲區和消息傳遞方式。71．計算機操作系統是方便用戶、管理和控制計算機系統資源的系統軟件。７２.在多道程序環境中,用戶程序的相對地址與裝入內存后的實際物理地址不同，把相對地址轉換為物理地址，這是操作系統的地址重地位功能。

7３.操作系的動態分區管理內存分派算法有初次適應算法、循環初次適應算法、和最佳適應算法。7４．動態存儲分派時,要靠硬件地址變換機構實現重定位。75．在存儲管理中常用虛擬存儲器方式來擺脫主存容量的限制。76.在請求頁式管理中,當硬件變換機構發現所需的頁不在內存時，產生缺頁中斷信號,中斷解決程序作相應的解決。７７.置換算法是在內存中沒有空閑頁面時被調用的,它的目的是選出一個被淘汰的頁面。假如內存中有足夠的空閑頁面存放所調入的頁，則不必使用置換算法。78．在段頁式存儲管理系統中,面向用戶的地址空間是段式劃分,面向物理實現的地址空間是頁式劃分。79．文獻的存儲器是提成大小相等的物理塊，并以它為單位互換信息。8０.通道是一個獨立于ＣPU的專管Ｉ／Ｏ的解決機，它控制

設備與內存之間的信息互換。81.緩沖區的設立可分為單緩沖、雙緩沖、循環緩沖和緩沖池。其中關于緩沖池的操作有提取輸入、提取輸出、收容輸入和收容輸出。82．操作系統為用戶編程所提供的接口是系統調用。83.文獻的邏輯結構分為流式文獻、順序文獻、索引文獻和索引順序文獻。8４.進程由程序、數據和PCB組成。8５．一張1.4４M的軟盤,其FAT表占的空間為2.16K。86.緩沖池涉及空白緩沖隊列、裝滿輸入數據的緩沖隊列和裝滿輸出數據的緩沖隊列三種隊列。８7.在生產者—消費者問題中,消費者進程的兩個ｗaｉt原語的對的順序為Wait(fuｌl)；和ｗaiｔ(mutex);。88．段式管理中,提供二維維的地址結構。以段為單位進行空間分派,每段分派一個連續內存區。8９.邏輯設備表（LUＴ)的重要功能是實現邏輯設備到物理設備的映射。9０．在一個請求分頁系統中,假如系統分派給一個作業的物理塊數為3,且此作業的頁面走向為2，3,２，1，5,2,4,5，3,2,5，2。OＴP算法的頁面置換次數為3,LRU算法的頁面置換次數為4,CLOCＫ算法的頁面置換次數為５?。9１.設單CＰU環境下，有三道作業，它們的提交時間及運營時間如下表：作業提交時間(單位：基本時間單位)運營時間(單位:基本時間單位)J１

Ｊ2?J30

２

３7?4

2若采用短作業優先調度策略，作業單道串行運營時的調度順序為J1,J3,J2，平均周轉時間=8。９2．進程間通信的類型有：共享存儲區、管道機制、消息隊列和信箱機制。9３．在響應比最高者優先的作業調度算法中，當各個作業等待時間相同時，運營時間短的作業將得到優先調度;當各個作業規定運營的時間相同時，等待時間長的作業得到優先調度。9４.若干個等待訪問磁盤者依次要訪問的磁道為2０,44,40,４，8０，１2,76，移動臂當前位于40號柱面，則先來先服務算法的平均尋道長度為２92;最短尋道時間優先算法的平均尋道長度為120；掃描算法(當前磁頭移動的方向為磁道遞增)的平均尋道長度為116。95．系統為一個有6頁的進程分派4個物理塊，其頁表如下所示（時間單位：滴答),頁的大小為1K,請計算邏輯地址為0x17C8的物理地址。頁號 塊號?裝入時間 上次引用時間?Ｒ(讀）?M（修改)0?７?12６ ?２７9 ? 0 ０1 4 230 260? １ ?０２? 2?1２0? 272???1 ?13 9?1６0 ?280 １??１按CLOCK算法為0x03Ｃ８；按FＩＦＯ算法為0x０BC8；按LRU算法為0x07C8。96.有三個同時到達的作業Ｊ１,J2和Ｊ３，它們的執行時間分別是Ｔ1,T2和Ｔ3，且T1<T2＜Ｔ3。系統按單道方式運營且采用短作業優先算法，則平均周轉時間是（3*T1+２＊Ｔ2+Ｔ3)／3。97．位示圖是運用二進制的一個位來表達磁盤中一個盤塊的使用情況。９8.在ＳPＯOLing系統中，進程執行輸出的過程是:將進程產生的數據送到磁盤的輸出井,輸出程序再將數據提出，通過內存的輸出緩沖區送往輸出設備。9９、在請求分頁系統中，假如一個作業的頁面走向為1，2,3,4,１，2，5,1,２，3,4,５,當分派給該作業的物理塊數M為3,采用先進先出頁面置換算法時,訪問過程中發生的缺頁次數為:___＿＿__＿＿;采用最佳頁面置換算法時，缺頁次數為：＿__＿＿____；采用LRU頁面置換算法時，缺頁次數為：＿＿___＿___。(假定開始時，物理塊中為空）100.頁是信息的單位,進行分頁是出于的需要。段是信息的單位,分段是出于用戶的需要。1０1．進程和線程都是系統進行的基本單位,它們最大的區別在于。10２.將數據從設備送入緩沖池稱為：;將數據從緩沖池送入設備稱為:；10３．用戶程序必須通過方能取得操作系統的服務。104.假如信號量的當前值為３,表達可用的資源數目為3，假如信號量的當前值為-３，則表達。１05．Ｉ/Ｏ控制的方式有程序直接控制方式、中斷控制方式、DＭA方式和通道方式。106．在初次適應算法中，規定空閑分區按地址遞增順序鏈接成空閑分區鏈;在最佳適應算法中是按空閑分區從小到大順序形成空閑分區鏈。107．文獻的物理結構有順序文獻、鏈接文獻文獻和索引文獻三種。108.現代操作系統的特性是并發、共享、虛擬和異步性。1０９.產生死鎖的四個必要條件是互斥條件和請求和保持，不剝奪條件和環路條件。11０．操作系統的五大功能是CPU管理、存儲管理、設備管理、文獻系統和用戶接口。11１.在操作系統中進程和線程的區別是:擁有資源。1１2．文獻系統的基本任務是實現按名存取。113．靜態鏈接是在程序編譯時進行,動態鏈接是在執行時進行。1１4.文獻的保護是通過存取控制表來實現的。115．文獻共享的方式有基于索引結點的方式和運用符號鏈。116.UNＩX系統對空閑空間的管理方式采用_＿成組鏈接法＿_。117.能方便實現信息共享的存儲管理方法有和。1１８.操作系統為用戶提供兩種類型的使用接口，它們是命令接口和。１19.一次只允許一個進程訪問的資源叫臨界資源。１20．在操作系統中進程是一個擁有資源的單位，也是一個調度和執行的基本單位。121.假如信號量的當前值為4,則表達，假如信號量的當前值為-4，則表達。12２．在批解決兼分時的系統中，往往由分時系統控制的作業稱為前臺作業,而由批解決系統控制的作業稱為后臺作業。１23.操作系統為用戶提供兩種類型的使用接口，它們是操作員(或用戶）接口和程序員(或程序)接口。124．操作系統中，進程可以分為系統進程和用戶進程兩類。12５.用戶調用建立和打開（可互換順序)文獻操作來申請對文獻的使用權。126.主存儲器與外圍設備之間的信息傳送操作稱為輸入輸出操作。1２7．當一個進程獨占解決器順序執行時,具有兩個特性：封閉性和可再現性。128.ＵNIX的ｓhell有兩層含義，一是指由shelｌ命令組成的Shell命令語言；二是指該命令的解釋程序。129．操作系統是運營在計算機基本硬件（或：硬件）系統上的最基本的系統軟件。１30.程序經編譯或匯編以后形成目的程序，其指令的順序都是以零作為參考地址，這些地址稱為相對地址（或：邏輯地址、虛擬地址)。131.文獻的邏輯結構分字符流式文獻和記錄式文獻二種。132．一個作業從進入系統到運營結束，一般要經歷“后備”、“執行”和“完畢”三個不同狀態。１33．WiｎｄowsNT操作系統結構由兩個部分構成：一是保護子系統，另一是執行體。13４．目前硬盤中最常使用的兩種接口是IDE接口和SCSI接口。135.用戶規定計算機系統所做的工作的集合稱為作業。136.進程由限度、數據集合、進程控制塊及相關表格組成。1３7．對信號量S的操作只能通過P、V操作進行,相應每一個信號量設立了一個等待隊列。13８.在存貯器可變式分區管理中，對內存狀態的記錄和分派管理通常可采用表格法、位圖法和鏈表法。13９.虛擬設備是指采用某種I/O技術，將某個獨占設備改善為多個用戶可共享的設備。140．文獻系統中，用于文獻的描述和控制并與文獻一一相應的是文獻控制塊（或:ＦCB）。141．所謂通道,是一塊能控制一臺或多臺外圍設備與CPU并行工作的硬件。142．用戶是通過命令接口或者程序接口向計算機發出請求的。143．在所有主機操作系統都是UNIX系統的TCP／IP網絡中，進行遠程注冊的命令是rlｏgｉn。144．在TCP／IP網絡中,UNIX操作系統下發送電子郵件的命令是Mail。１45．操作系統的重要設計目的是方便用戶使用或界面和諧和系統能高效工作或資源運用率高。?146.當一個進程完畢了特定的任務后,系統收回這個進程所占的工作區或主存空間或資源和取消該進程的進程控制塊(PＣB）就撤消了該進程。?１47.單個分區存儲管理僅合用于個人計算機（單用戶）和專用計算機(單道，單作業)系統。?148．每個索引文獻都必須有一張索引表,其中每個登記項用來指出一個邏輯記錄的存放位置或指針或首地址。

１49.實現ＳPＯOL系統時必須在磁盤上辟出稱為輸入井和輸出井(可互換順序)的專門區域,以存放作業信息和作業執行結果。?１5０．一個抱負的作業調度算法應當是既能提高系統效率或吞吐量高及時得到計算結果又能使進入系統的作業周轉時間短等_。二、判斷題(×)1．并發性是指若干事件在同一時刻發生。（√）2．虛存容量的擴大是以犧牲CPＵ工作時間以及內、外存互換時間為代價的。（×)3．用戶為每個自己的進程創建PCB,并控制進程的執行過程。（√）４．樹型目錄結構可以解決文獻重名問題。（√）5.原語是一種不可分割的操作。(√）6．通道一旦被啟動就能獨立于CＰU運營，這樣可使CPU和通道并行操作。（√)7．頁式的地址是一維的，段式的地址是二維的（×）８．位示圖方法可用于磁盤的調度管理。(×)９.虛擬設備是指把一個物理設備變換成多個相應的邏輯設備,它通過邏輯設備表來實現的。(×)10．頁式管理易于實現不同進程間的信息共享。（√）11.在虛擬存儲方式下,程序員編制程序時不必考慮主存的容量,但系統的吞吐量在很大限度上依賴于主存儲器的容量；(×）12.可重定位分區管理可以對作業分派不連續的內存單元;（√）1３．采用動態重定位技術的系統,目的程序可以不經任何改動,而裝入物理內存；(×）1４．頁式存儲管理中，一個作業可以占用不連續的內存空間，而段式存儲管理，一個作業則是占用連續的內存空間。（×）15.線程是最小的擁有資源的單位。（√）1６．文獻系統最基本的功能是實現按名存取。（×)17．存取控制表是每個用戶一張,表白該用戶對不同文獻的存取權限。(×）１8．SPＯOLinｇ技術可以解決進程使用設備死鎖問題。（×）19．對于一個具有三級索引表的文獻,存取一個記錄需要訪問三次磁盤。（√)20．在I/O控制的多種方式中,傳輸速率高,對主機影響少的方式最佳。（×)21．進程可以刪除自己的PCB表。（×）22.可重定位分區法可以支持虛擬存儲器的技術。(×）２3.單級目錄結構可以解決文獻重名問題。(×)2４．分頁式存儲管理中,頁的大小是可以不相等的。（√)25．執行原語時不會響應任何中斷。(√)26.段頁式管理實現了段式、頁式兩種存儲方式的優勢互補。（√）２7．對臨界資源應采用互斥訪問方式來實現共享。(×)28.文獻系統中分派存儲空間的基本單位是記錄。（×)2９.外存對換空間保存的是虛擬內存管理系統調出的程序。(√)30.虛存容量的擴大是以犧牲CPU工作時間以及內、外存互換時間為代價的。四名詞解釋：１.原語：它是由若干條機器指令所構成,用以完畢特定功能的一段程序，為保證其操作的對的性,它應當是原子操作，即原語是一個不可分割的操作。2.設備獨立性：指用戶設備獨立于所使用的具體物理設備。即在用戶程序中要執行I/O操作時,只需用邏輯設備名提出I/O請求，而不必局限于某特定的物理設備。3.文獻的邏輯結構：又稱為文獻邏輯組織,是指從用戶觀點看到的文獻組織形式。它可分為兩類:記錄式文獻結構，由若干相關的記錄構成;流式文獻結構，由字符流構成。4.樹形結構目錄：運用樹形結構的形式,描述各目錄之間的關系。上級目錄與相鄰下級目錄的關系是1對n。樹形結構目錄可以較好地滿足用戶和系統的規定。5.操作系統：操作系統是控制和管理計算機硬件和軟件資源，合理地組織計算機的工作流程,以及方便用戶的程序的集合。其重要功能是實現解決機管理、內存管理、I/O設備管理、文獻管理和用戶接口。6．位示圖：它是運用一個向量來描述自由塊使用情況的一張表。表中的每個元素表達一個盤塊的使用情況，0表達該塊為空閑塊,１表達已分派。7．置換策略:虛擬式存儲管理中的一種策略。用于擬定應選擇內存中的哪一頁(段)換出到磁盤對換區,以便騰出內存。通常采用的置換算法都是基于把那些在最近的將來，最少也許被訪問的頁(段)從內存換出到盤上。8.用戶接口：操作系統提供應用戶和編程人員的界面和接口。涉及程序接口、命令行方式和圖形用戶界面。9.死鎖:指多個進程因競爭資源二導致的一種僵局,若無外力的作用,這些進程將永遠不能再向前推動。10.文獻系統:OS中負責管理和存取文獻信息的軟件機構。負責文獻的建立,撤消,存入，續寫，修改和復制,還負責完畢對文獻的按名存取和進行存取控制。11.進程:進程是程序在一個數據集合上的運營過程,是系統進行資源分派和調度的一個獨立的基本單位。１2.wait(s）原語wａit(s）:Begin?Ｌockoutｉnterｒupｔs;?ｓ＝ｓ–１;?Iｆs＜0ｔhen Ｂegin? ?Sｔatus(q）=bｌoｃｋed; ??Insert（WＬ，ｑ)；? Unlockiｎterrupｔｓ;Ｓchedulｅｒ;? End?Elsｅ? unlockinｔｅｒｒupts;Eｎd13.鏈接文獻邏輯文獻中的不同記錄可以存儲在離散的磁盤塊中。每個盤塊中都設立了一個指向下一個盤塊的鏈接指針，用這些指針可將一個文獻中的所有盤塊拉成一條鏈，而在文獻控制塊中的“文獻地址指針”便指向存放該文獻的第一個盤塊的編號。14.快表采用聯想存儲器加快查表速度,在地址變換機構中,加入一個高速,小容量、具有并行查詢能力的聯想存儲器,構成快表,存放正運營的作業的當前頁號和塊號。在快表中找到,直接進行地址轉換;未找到，則在主存頁表繼續查找,并把查到的頁號和塊號放入聯想存儲器的空閑單元中，如沒有，淘汰最先裝入的頁號。15．虛擬存儲器指具有請求調入功能和置換功能,能從邏輯上對內存容量進行擴充的一種存儲器系統。從用戶觀點看，虛擬存儲器具有比實際內存大得多的容量。這既方便了用戶,又提高了內存的運用率和系統的吞吐量。16．文獻目錄為了項用戶提供對文獻的存取控制及保護功能，而按一定規則對系統中的文獻名,（亦可包含文獻屬性)進行組織所形成的表,稱為目錄表或文獻目錄。1７．I／O控制：我們把從用戶進程的輸入/輸出請求開始,給用戶進程分派設備和啟動有關設備進行I/O操作，以及在I/O操作完畢之后響應中斷,進行善后解決為止的整個系統控制過程稱為I／O控制。18.緩沖池：這是具有多個緩沖區的公用緩沖器,其中的各個緩沖區可供多個進程或設備共享。為便于管理，通常把緩沖池中的緩沖區,按其性質的不同而構成若干個鏈表或隊列,如空緩沖隊列，輸入緩沖隊列等。１９．SPOOLＩNG:即同時聯機外圍操作，又稱脫機操作。在多道程序環境下,可運用多道程序中的一道程序，來模擬脫機的輸入輸出功能。即在聯機條件下，將數據從輸入設備傳送到磁盤，或從磁盤傳送到輸出設備。20．邏輯地址與物理地址:在具有地址變換機構的計算機中，允許程序中編排的地址和信息實際存放在內存中的地址有所不同。邏輯地址是指用戶程序經編譯后,每個目的模塊以０為基地址進行的順序編址。邏輯地址又稱相對地址。物理地址是指內存中各物理存儲單元的地址從統一的基地址進行的順序編址。物理地址又稱絕對地址,它是數據在內存中的實際存儲地址。21虛擬存儲器:答:虛擬存儲器是一種存儲管理技術，用以完畢用小的內存實現在大的虛空間中程序的運營工作。它是由操作系統提供的一個假想的特大存儲器。但是虛擬存儲器的容量并不是無限的,它由計算機的地址結構長度所擬定，此外虛存容量的擴大是以犧牲CPU工作時間以及內、外存互換時間為代價的。22．PＣB:23．聯想存儲器:２4．設備獨立性:25.系統調用：２６.設備驅動程序:五問答題1．在單解決機環境下，進程間有哪幾種通信方式，是如何實現的?1.作業調度：從一批后備作業中選擇一個或幾個作業，給它們分派資源，建立進程，掛入就緒隊列。執行完后,回收資源。進程調度:從就緒進程隊列中根據某個策略選取一個進程，使之占用CPＵ。互換調度:按照給定的原則和策略，將外存互換區中的進程調入內存,把內存中的非執行進程互換到外存互換區中。2．設備管理中的數據傳送控制方式有哪幾種?分別簡述如何實現的。2.程序直接控制：由用戶進程來直接控制內存或CPU和外設間的信息傳送。中斷方式：進程通過CPU發出指令啟動外設，該進程阻塞。當輸入完畢時,I／O控制器通過中斷請求線向ＣPU發出中斷信號，ＣPＵ進行中斷解決。DMA方式：在外設和內存之間開辟直接的數據互換通路。通道控制方式：ＣＰＵ發出啟動指令，指出通道相應的操作和I/O設備,該指令就可啟動通道并使該通道從內存中調出相應的通道指令執行。３.簡述進程的幾種狀態和引起狀態轉換的典型因素,以及相關的操作原語。３.進程的基本狀態有:新、就緒，阻塞,執行、掛起和終止六種。新到就緒：互換，創建原語就緒到執行:進程調度執行到阻塞:I/O請求,阻塞原語阻塞到就緒：I/O完畢，喚醒原語執行到就緒：時間片完阻塞到掛起:掛起原語掛起到就緒：喚醒原語執行到終止：進程執行完畢4.什么是段式存儲管理？它從邏輯地址到物理地址是怎么變換的？４．把程序按內容或構成關系提成段,每段有自己的名字。一個用戶作業或進程包含的段相應于一個二維虛擬儲存器。以段為單位分派內存，然后通過地址映射機構把邏輯地址轉換成物理地址。只將那些經常訪問的段駐留內存,其他的段放在外存，待需要時自動調入。地址變換過程:由虛地址中的段號為索引,查段表。找出該段在內存的起始地址,并將其和段內地址相加，從而得到物理地址。５．什么是請求頁式管理?能滿足用戶哪些需要？答:請求頁式管理的基本原理是將邏輯地址空間提成大小相同的頁，將存儲地址空間分塊,頁和塊的大小相等，通過頁表進行管理。頁式系統的邏輯地址分為頁號和頁內位移量。頁表涉及頁號和塊號數據項，它們一一相應。根據邏輯空間的頁號,查找頁表相應項找到相應的塊號,塊號乘以塊長，加上位移量就形成存儲空間的物理地址。每個作業的邏輯地址空間是連續的,重定位到內存空間后就不一定連續了。此外，頁表中還涉及特性位(指示該頁面是否在內存中）、外存地址、修改位（該頁的內容在內存中是否修改過）等。頁式存儲管理在動態地址轉換過程中需要擬定某一頁是否已經調入主存。若調入主存,則可直接將虛地址轉換為實地址，假如該頁未調入主存，則產生缺頁中斷,以裝入所需的頁。頁式存儲管理將不常用的頁面調出內存，使內存的運用率高；虛擬的容量大,用戶不必緊張內存不夠;不規定作業連續存放，有效地解決了“碎片”問題。6．在段頁式虛擬存儲系統中，不同進程之間是如何實現程序共享的？６．在系統內設立有系統段表，用戶段表指向系統段表，系統段表內有當前共享的用戶數。當用戶進程調入一個程序段之前,先查找系統段表，假如所需段存在，則將共享用戶數加一，在將此段登記在用戶進程段表中。當進程退出時，共享計數減一，最后一個用戶刪除共享代碼段。7．試比較內存管理和外存管理的異同點.答：重要任務：內存管理的重要任務是為多道程序的運營，提供良好的環境；而外存管理的重要任務則是為文獻提供存儲空間。基本功能：內存管理的基本功能包含了內存空間的分派、回收、內存保護、對換、內存擴充等方面;而對外存管理的基本功能則只是對外存空間的分派和回收。分派方式:它們都可采用連續分派或離散分派方式，且都以離散分派方式為主。分派算法或機制：對于連續分派方式，內存與外存管理中的分派和回收算法類似,重要有初次適應算法、循環初次適應算法等;在離散分派方式中，兩者采用的機制不同,內存管理重要是運用頁(段)表;而在外存管理中，則重要運用文獻分派表ＦＡT。8.SＰOOLing的含義是什么？試述ＳPOＯLing系統的特點、功能以及控制過程。答:SPOOＬing是SｉｍｕｌtａneousＰerｉｐheraｌOpeｒａtionOn－Liｎe(即外部設備聯機并行操作)的縮寫,它是關于慢速字符設備如何與計算機主機互換信息的一種技術，通常稱為“假脫機技術”。SPOＯLing技術是在通道技術和多道程序設計基礎上產生的,它由主機和相應的通道共同承擔作業的輸入輸出工作，運用磁盤作為后援存儲器，實現外圍設備同時聯機操作。SPOOLiｎg系統由專門負責I／O的常駐內存的進程以及輸入井、輸出井組成；它將獨占設備改造為共享設備,實現了虛擬設備功能。９.在生產者—消費者問題中，能否將生產者進程的wａiｔ(ｅmｐty）和ｗaｉt(muｔｅx)語句互換，為什么？不能。（2分)由于這樣也許導致系統死鎖。當系統中沒有空緩沖時,生產者進程的wａit(mutｅx）操作獲取了緩沖隊列的控制權,而waiｔ(ｅmptｙ)導致生產者進程阻塞，這時消費者進程也無法執行。(３分)1０．進程的基本狀態有哪些？這些狀態之間是如何轉換的？進程的基本狀態有：就緒,阻塞,執行三種。（2分）就緒到執行：進程調度執行到就緒：時間片完執行到阻塞:I/O請求或等待事件發生阻塞到就緒:Ｉ/O完畢或事件已發生(3分)11．什么是快表？它在地址轉換中起什么作用?快表是一個高速、具有并行查詢能力的聯想存儲器，用于存放正運營的進程的當前頁號和塊號，或者段號和段起始地址。（２分）加入快表后,在地址轉換時,一方面在快表中查找,若找到就直接進行地址轉換;未找到，則在主存頁表繼續查找,并把查到的頁號和塊號放入聯想存儲器中。快表的命中率很高,有效地提高了地址轉換的速度。（3分)1２．什么是設備獨立性,它是如何實現的?設備獨立性即應用程序獨立于使用的物理設備，在應用程序中使用邏輯設備名稱來請求使用某類設備。系統在執行時，是使用物理設備名稱。（３分)要實現設備獨立性必須由設備獨立性軟件完畢，涉及執行所有設備的公有操作軟件提供統一的接口，其中邏輯設備到物理設備的映射是由邏輯設備表ＬＵＴ完畢的。(2分）1３．文獻的物理結構有哪幾類，那種結構能支持大型文獻？文獻的物理結構有：順序文獻、鏈接文獻和索引文獻。（４分）其中索引文獻能支持大型文獻。(1分)１4．試說明和比較幾種文獻共享的方法繞彎路法:連訪法：運用基本文獻目錄實現文獻共享：基于索引節點的共享方法：運用符號鏈實現文獻共享：15.解決機調度分為哪三級？各自的重要任務是什么?答:作業調度:從一批后備作業中選擇一個或幾個作業,給它們分派資源，建立進程,掛入就緒隊列。執行完后,回收資源。進程調度:從就緒進程隊列中根據某個策略選取一個進程,使之占用CPU。互換調度:按照給定的原則和策略，將外存互換區中的進程調入內存,把內存中的非執行進程互換到外存互換區中。16.什么是高級調度、中級調度和低檔調度？答：作業調度:從一批后備作業中選擇一個或幾個作業，給它們分派資源,建立進程，掛入就緒隊列。執行完后,回收資源。進程調度：從就緒進程隊列中根據某個策略選取一個進程,使之占用CPU。互換調度：按照給定的原則和策略,將外存互換區中的進程調入內存，把內存中的非執行進程互換到外存互換區中。17.請描述請求頁式管理機制中的地址變換過程。１8.目前操作系統采用的目錄結構是什么？它具有什么優點？為了給用戶提供對文獻的存取控制及保護功能,而按一定規則對系統中的文獻名，（亦可包含文獻屬性)進行組織所形成的表，稱為目錄表或文獻目錄。目前操作系統采用的目錄結構是樹型目錄結構，它的優點有:有效地提高對目錄的檢索速度；允許文獻重名;便于實現文獻共享。19．什么是死鎖?產生死鎖的四個必要條件是什么?死鎖：當某進程提出資源申請后，使得系統中一些進程處在無休止的阻塞狀態，在無外力作用下,永遠不能再繼續前進。產生死鎖的必要條件：互斥條件:某段時間內某資源只能由一個進程使用。不剝奪條件:資源在未使用完前,不能被剝奪,由使用進程釋放。部分分派（請求和保持）:進程因請求資源而阻塞時,對已分派給它的資源保持不放。環路條件:發生死鎖時，有向圖必構成一環路。2０．什么是內存分頁存儲管理?它有什么特點?分頁存儲管理是將各進程的地址空間提成大小相等的頁，把內存的存儲空間也提成與頁大小相同的片，稱為物理塊。在分派存儲空間時，以塊為單位來分派。優點:有效解決存儲器的零頭問題,能在更高的限度上進行多道程序設計,從而相應提高了存儲器和ＣPU的運用率。缺陷：采用動態地址變換為增長計算機成本和減少CPＵ的速度。表格占內存空間，費時來管理表格。存在頁內碎片。作業動態的地址空間受內存容量限制。2１．說明進程的結構、特性和基本狀態。答:結構:ＰＣB(進程控制塊)+程序+數據集合。

特性:動態性、并發性、獨立性、制約性、結構性。

基本狀態:就緒態、執行態、等待態。22.在生產者—消費者問題中,假如缺少了signal（fuｌl)或sｉｇｎaｌ(ｅｍpｔy),對執行結果會有什么影響?23.頁式和段式內存管理有什么區別？如何才干實現共享和保護？答：段式與頁式存儲管理的比較如下表所示。段式頁式分段由用戶設計劃分,每段相應一個相應的的程序模塊,有完整的邏輯意義。分頁用戶看不見，由操作系統為內存管理劃分。段面是信息的邏輯單位頁面是信息的物理單位便于段的共享,執行時按需動態鏈接裝入。頁一般不能共享段長不等，可動態增長，有助于新數據增長。頁面大小相同，位置不能動態增長。二維地址空間：段名、段中地址；段號、段內單元號一維地址空間管理形式上象頁式,但概念不同往往需要多次缺頁中斷才干把所需信息完整地調入內存實現頁(段)的共享是指某些作業的邏輯頁號（段號）相應同一物理頁號(內存中該段的起始地址）。頁（段）的保護往往需要對共享的頁面（段）加上某種訪問權限的限制，如不能修改等；或設立地址越界檢查,對于頁內地址(段內地址)大于頁長(段長）的存取，產生保護中斷。２４.在哲學家算法中,是否能防止或解除死鎖？為什么？答：銀行家算法部分防止和解除死鎖，由于它只能根據安全狀態防止部分死鎖，沒有防止和解除所有死鎖的能力。25．在原語執行期間，是否可以響應中斷？為什么?答:原語執行期間可以響應中斷，只是不能進行進程切換。26.不同用戶的不同任務之間的進程是有臨界區？為什么？請舉例說明。答:完全也許有臨界區,如打印程序是可以由不同用戶的不同進程使用，但是只能有一個進程在某一時刻進入。27．文獻目錄有何作用？答：實現文獻目錄到物理地址的轉換。2８．什么是文獻的邏輯結構和物理結構?文獻的邏輯結構(文獻的組織):從用戶角度看到的文獻的全貌,也就是它的記錄結構，涉及流式文獻、順序文獻、索引文獻和索引順序文獻。文獻的物理結構(文獻的存儲結構）:文獻在外存上的存儲組織形式,涉及連續文獻、串聯文獻和索引文獻。29.請說明系統運用緩沖池進行輸入操作的過程。（7分)收容輸入:數據從設備輸入到緩沖池hiｎ=ｇet-bｕｆ（ｅmq)；數據裝入ｈin中;put－ｂuｆ（inq,hｉｎ):;提取輸入：數據從緩沖池輸入到內存ｓｉn=geｔ-buf(inq）；數據從siｎ中提走;put-buf（emq,sin);30.什么是虛擬存儲器，它有什么特點?答：虛擬存儲器是一種存儲管理技術,用以完畢用小的內存實現在大的虛空間中程序的運營工作。它是由操作系統提供的一個假想的特大存儲器。但是虛擬存儲器的容量并不是無限的,它由計算機的地址結構長度所擬定，此外虛存容量的擴大是以犧牲CＰＵ工作時間以及內、外存互換時間為代價的。3１．比較基于索引節點和基于符號鏈的文獻共享方法。(8分)答：基于索引節點的文獻共享是在文獻的目錄中填上需要共享文獻的索引節點的序號，在索引節點中加上用戶計數。基于符號鏈的文獻共享是建立一種特殊的鏈接文獻，內容為需要共享的文獻的途徑和名字，訪問該文獻時,根據途徑找到共享的文獻。基于索引節點的文獻共享訪問速度快,但也許使索引節點指針懸空；基于符號鏈的文獻共享安全,但訪問速度慢，要占用索引節點。六算法題1．這是一個從鍵盤輸入到打印機輸出的數據解決流圖,其中鍵盤輸入進程通過緩沖區buｆ1把輸入數據傳送給計算進程,計算進程把解決結果通過緩沖buf2傳送給打印進程。ｂuf１和ｂuｆ2為臨界資源,試寫出鍵盤輸入進程，計算進程及打印進程間的同步算法。（10分)輸入進程→buf1→計算進程→bｕｆ2→打印進程解答：從鍵盤輸入到打印機輸出的數據傳送過程，可以看作是由鍵盤輸入進程到計算進程，以及由計算進程到打印輸出進程這兩個數據傳送進程所組成。其中，對鍵盤輸入進程而言，計算進程是消費者進程;而對打印輸出進程而言，計算進程又是生產者進程。據此可將它們之間的同步問題描述如下：ｖａr：ｍｕtex1,mｕｔｅｘ2,emｐty１,empｔｙ2,full1，full2：=1，1，1,1,0，0;IP:ｂeginrepeatP(eｍｐty);P(mutex1);inpuｔａcｈａrｃteｒｆromkｅｙｂoａrd；Addtｏbuffer；V(mｕｔeｘ１);V（ｆull);untiｌｆalｓｅeｎdCP:ｂeginreｐｅaｔP(ｆull);P(muｔex１）；Tａkeａchaｒactorｆoｒmｂuffer1;Adｄtoch1；V（muｔex1）;V(emｐty1)；P(eｍｐty２)；Ｐ(mutex2);Taｋeaｃhaｒactorｆormch1;Ａddtoｂｕffer2;Ｖ(ｍuｔex２）;Ｖ(full2);uｎｔilfalseendOP：bｅginrepeａｔｐ(full２);P(ｍutex２）;Takeachａｒactorｆrｏmｂuffer2;Aｄｄtopriｎｔercontroler；startprinter;V(mｕteｘ2)；Ｖ(ｅmpty2）;ｕntilfalseｅnd2.設在一個頁面大小為１K的系統中，正在解決器上執行的一個進程的頁表如圖所示:頁號 狀態位?訪問位?修改位 物理塊號０ ?1??1 ?０? 41??1??1 1? 72 0 ?0? 0??-3 ?1 0? 0 ?２4? 0 ０ 0 -5??１ ０ １ 0起始頁號和塊號均為0。１．詳述在設有快表的請求分頁存儲管理系統中，一個虛地址轉換成物理內存地址的過程。2．下列虛地址(十進制)相應與什么物理地址:５449，2221。 解: （1０分)５４４９的物理地址為:329222１的物理地址為：2２2１3．設系統有三種類型的資源，數量為（4,2,２),系統中有進程A,Ｂ,C按如下順序請求資源：進程A申請(３，2，1)進程Ｂ申請（１，０，１）進程A申請（０，1，0）進程C申請(２,０,0）請你給出一和防止死鎖的資源剝奪分派策略,完畢上述請求序列,并列出資源分派過程，指明哪些進程需要等待，哪些資源被剝奪。(10分)解:(1０分)①分派策略為：當進程Pi申請ri類資源時，檢查ri中有無可分派的資源：有則分派給Pi;否則將Pi占有的資源所有釋放而進入等待狀態。(Pi等待原占有的所有資源和新申請的資源)②資源分派過程：剩余資源進程A:(3,2,1)(1，０，1)進程Ｂ:(1,0，1)(0，0，0)進程A:(0，１，0)（不滿足)(3，2,1）Ａ的所有資源被剝奪，A處在等待進程Ｃ:（2，0,0）（1,2,１)Ｃ,B完畢之后,Ａ可完畢。4．設公共汽車上,司機和售票員的活動分別是:司機:?啟動車輛? 售票員:?上乘客 ?正常行車? ? 關車門??到站停車? 售票? ? ?開車門 ? `下乘客在汽車不斷地到站,停車，行使過程中,這兩個活動有什么同步關系?并用wait和signal原語操作實現它們的同步。 ?解:BEＧINintegerstop,ruｎ;Stｏp:=０；Rｕn:=0;CＯBEＧＩＮDrivｅｒ:?BEＧIN L1：wａｉt(ｒｕn）； ??啟動車輛；正常行車;到站停車；? ?signａl（stoｐ);??? GotoL1;??ENＤConduｃtor: BEＧＩN L2： 上乘客; ?關車門;?? ?signal（rｕn);????售票;wait(stop);開車門;下乘客；ＧｏｔｏL2;EＮDCＯＥNＤEＮＤ５、某虛擬存儲器的用戶編程空間共3２1KB,內存為１6KB。假定某時刻一用戶頁表中已調入內存的頁面的頁號和物理塊號的對照表如下:頁號物理塊號152103447則邏輯地址0Ａ５Ｃ(Ｈ答：邏輯地址0A5CH）所相應的二進制表達形式是：０0001010０1０1１100，由于1K=210,下劃線部分前的編碼為00００10，表達該邏輯地址相應的頁號為3查頁表，得到物理塊號是4（十進制），即物理塊地址為:000１0010０0000000,拼接塊內地址00０0０００001０1110０,得０001001001011100,即125C（H)。６、某段表內容如下:段號段首地址段長度0１20Ｋ40K1760K3０K24８0K2０K３３70K20Ｋ

一邏輯地址為(2，154）的實際物理地址為多少?答：邏輯地址（２154)表達段號為2,即段首地址為480K，15４為單元號,則實際物理地址為４80Ｋ＋1５4。7、設系統中有三種類型的資源(A，B,C）和五個進程(P1,P2,P3,Ｐ4，Ｐ５）,A資源的數量為17，B資源的數量為5，Ｃ資源的數量為20。在T0時刻系統狀態如表1和表2所示。（共1０分）

系統采用銀行家算法實行死鎖避免策略。

①Ｔ0時刻是否為安全狀態?若是，請給出安全序列。

②在T0時刻若進程Ｐ2請求資源（0,3,４）,是否能實行資源分派？為什么？

③在②的基礎上，若進程P４請求資源（2,0，1），是否能實行資源分派?為什么?

④在③的基礎上,若進程P1請求資源(0,２，０）,是否能實行資源分派？為什么？

表１

Ｔ0時刻系統狀態

最大資源需求量已分派資源數量AＢCABCＰ1５59212P2５36402P３4011４05P44２5２04Ｐ54243１4表2

Ｔ0時刻系統狀態

ＡBC剩余資源數23３8.系統中有五個進程P1、Ｐ2、Ｐ3、Ｐ4、P5，有三種類型的資源：R１、R2、和Ｒ３。在T0時刻系統狀態如表所示。若采用銀行家算法實行死鎖避免策略，回答下列問題：(共9分,每小題３分)T０時刻是否為安全狀態?為什么?若這時Ｐ４請求資源(1,２,0）,是否能實行資源分派?為什么？在上面的基礎上,若進程P3請求資源(０,1,0），是否能實行資源分派？為什么？

T0時刻系統狀態已分派資源數量最大資源需求量Ｒ１R2R3R１R２R3P1００1001P22002７5P30０3６6５P411543５Ｐ5033０６5

R1R2R3剩余資源數330解：（共9分,每小題3分)Ｔ0時刻是安全的，安全序列為：P1,Ｐ４,P５，P２，P３P4請求資源（1，2,０),根據銀行家算法，預分派后系統是安全的,安全序列為:P１，P4，P5,P２,P３P3請求資源(１，1，0),根據銀行家算法,預分派后系統不安全，所以不能實行資源分派。

９.一個進程的大小占５個頁面,每頁的大小為1Ｋ,系統為它分派了3個物理塊。當前進程的頁表如圖所示:（共8分）??塊號? ?存在位P? 訪問位R??修改位M0x1Ｃ１10０x3Ｆ111-0000x5D１０0-000有那些頁面不在內存?(2分)請分別計算進程中虛地址為０x３B7、0x１2A5、0x１43２單元的物理地址(用十六進制表達）,并說明理由。（６分)解:（共８分）不在內存的是第2和４頁(按頁號),或第3和５頁(按序號)。(2分）0x３B7的物理地址=０x７3B7(2分)0x１２A5的物理地址＝０x17６A5,缺頁,換出第三頁。０x1432地址越界,犯錯。(2分）１0．系統運營有三個進程:輸入進程、計算進程和打印進程，它們協同完畢工作。輸入進程和計算進程之間共用緩沖區buffeｒ1,計算進程和打印進程之間共用緩沖區bufｆer２。輸入進程接受外部數據放入bｕfｆer1中;計算進程從buffer1中取出數據進行計算，然后將結果放入bｕffｅｒ2；打印進程從buffer2取出數據打印輸出。用算法描述這三個進程的工作情況,并用wａｉt和sigｎaｌ原語實現其同步操作。（共8分)解:（共8分)解答:輸入進程、計算進程和打印進程之間的同步問題描述如下:vaｒ:mutｅx1，mutex2,emｐｔy1,empty2,full1,full2:＝１,1,1,1，0，0;InP:ｂeginrepeatwait(eｍｐty１)；ｗaｉｔ(mutｅx１)；iｎpuｔaｄatafromkeｙboard;Aｄｄtobｕffer1;ｓｉｇnal(mｕtｅx1)；signal（ｆｕｌｌ１);untiｌｆaｌseendCalP:ｂｅgｉnrｅpeａｔｗaiｔ(full1）;wait(mutex1);Tａkeadataformbuffｅｒ1;Aｄｄｔoch1；signａｌ(mutex1);ｓignａl（ｅmｐty1);calcｕlatｅｃh1；waiｔ(ｅｍpty2)；ｗaｉt（mｕｔex２）;Ｔａkｅadataformch１；Addtobuffer２；sｉgnａl(mutex２);signal(fｕll2)；untilｆaｌseｅｎdOuｔＰ:beginｒepeａtwaｉt(ｆulｌ2);waｉt(ｍuｔex2);Ｔaｋeaｄatafｒｏmbuｆfer2;Ａddtopriｎtｅrｃontｒoler;siｇnal(mutｅx2）;ｓｉgnａl（eｍpty2);starｔprinteｒ；ｕｎtiｌｆaｌseend（評分標準：信號量設立2分，輸入進程、計算進程、打印進程各2分)１1.在一個請求分頁系統中，有一個長度為5頁的進程,假如系統為它分派3個物理塊，并且此進程的頁面走向為2，3，2，1，5,2,４,5，3，2，5,２。試用FＩＦO和ＬRU兩種算法分別計算出程序訪問過程中所發生的缺頁次數。（10分)解：FIFO:232１52４53252第１頁2２２５55333第2頁33３2225５第3頁１１１4442缺頁中斷次數=6LUR：2３2１５２453252第１頁２22２5５５3第2頁33５233５第3頁1１４4２2缺頁中斷次數=5１２.進程Ａ1,Ａ2,…，Aｎ通過K個緩沖區向進程B１,B2，…，Bｍ不斷地發送消息。發送和接受工作遵循如下規則:每個發送進程一次發送一個消息，寫入緩沖區,緩沖區大小與消息長度一致；對每個消息，B1，Ｂ2,…,Bｍ都需接受一次,讀入各自的數據區內；K個緩沖區都滿時,發送進程等待，沒有可讀的消息時，接受進程等待。試用waiｔ和signaｌ原語操作組織對的的發送和接受操作。(10分)解：BEGＩNInｔegerMｕtｅx,Avaiｌ[n］,Ｆulｌ[m];IntｅgｅrＩ;Mｕｔex:＝１;ＦORi：=1TOmDOBEＧＩＮAvail[Ｉ]:=k;Full[I]:=0；ENDPRＯCEDURESｅnｄ(K)IｎtegｅrI;BEGIN1３.一個進程的大小為5個頁面，為它分派了四個物理塊。當前每個塊的情況如下表所示（都為十進制數,且從0開始計數。）。當虛頁4發生缺頁時，使用下列的頁面置換算法,哪一個物理塊將被換出？并解釋因素.(１0分)頁號 ?塊號? 加載時間 訪問時間 訪問位R?修改位Ｍ2??0? ６0? 161??０ 11??1??13０? 16０ ?０? ０0 2 2６ 162? 1 ０3??3 ２0??1６3 1 １IFO算法LRＵ算法CLOCK算法當頁面的訪問串為:“４，０,0，0,2,4，2，1，0,3，2”的ＯPＴ解:１．換出第3號虛頁,由于它加載的時間最早;2.換出第1號虛頁，由于它最近最久沒被訪問;３．換出第1號虛頁，由于它最近既沒被訪問，又沒被修改;4.換出第3號虛頁,由于它離訪問點最遠。1４.用整型信號量描述在哲學家進餐問題中,至多允許4個哲學家同時進餐的算法。（1０分）解:ｐublｉcｃlassdiningｐhiｌosopherｓ{seｍaｐｈore[]fork=newseｍaphｏre[5](1）;ｓｅmaphorerooｍ=newsemａpｈore(4);ｉｎｔi;voidphilosoｐheｒ(inｔｉ){ｗhｉle(tｒuｅ)ｔhiｎk();wait(rooｍ);wａit(forｋ[i]);waiｔ(fork[(i+１)%５]);eaｔ（)；signaｌ(foｒｋ［(i+1）％5])；signal(fork[i］);signａｌ（rｏom）；? }voiｄｍain(){pａrbegin（pｈiloｓoｐher(0),ｐhilosophｅr(1),ｐhiloｓopｈer(２)，phｉlosopher(３),philｏsopher(4));? }??}1５．考慮一個有1５０個存儲器單元的系統,如下分派給三個進程:進程? 最大 ?占有————————————————————１?? ７0 ??45２???6０?? 403 ?6０ ? １5使用銀行家算法,以擬定下面的任何一個請求是否安全：ａ.第4個進程到達，最多需要6０個存儲單元,最初需要25個單元;ｂ．第4個進程到達，最多需要60個存儲單元,最初需要35個單元;假如安全給出安全序列；若不安全給出結果分派簡表。（10分）解：進程? 最大 ?占有??尚需??可用————————————————————————1 ? 70 ? 45? 25 ? 25?2 ??60???40? ?203 ? 60 ??１5 454 ? 6０ ?25 ? ３５安全序列為：１、2、3、4所以系統是安全的，可以進行分派。b.進程 最大??占有??尚需? 可用————————————————————————１?? 70 ??4５ ??２5 ?１5?2 6０? ?4０ ??203 ?60 15 ?454 ??60 ??35 ?25當前可用的資源不夠任何一個進程運營完畢，所以不安全。16．Jruasｓｉc公園有一個恐龍博物館和一個公園.有ｍ個旅客和n輛車,每輛車只能容納一個旅客。旅客在博物館逛了一會兒,然后排隊乘坐旅行車。當一輛車可用時，它載入一個旅客，然后繞公園行駛任意長的時間。假如ｎ輛車都已被旅客乘坐游玩,則想坐車的旅客需要等待;假如一輛車已經就緒,但沒有旅客等待,那么這輛車等待。使用信號量同步ｍ個旅客和n輛車的進程。（10分)解:vｉｓiｔors=m;? cａrs＝ｎ; muteｘ=1;Pvｉ（) Ｐci(){repeat?? ｛rｅpeatwait（caｒs)；???? wａit(vｉｓiｔorｓ）;wait（muｔex); waiｔ(ｍutｅx)；geton；? ?? stａrｔ；tｒaｖeｌl;?? ?? run；ｇｅtoｆf; ?? ? stoｐ;siｇnａl(cars); ? ??sｉgnal（visiｔoｒｓ);wａｉｔ(ｍuｔex)； ??ｗaｉt(ｍuteｘ)；unｔilfａlse；?? ?untilｆaｌse;}? ?? }17.讀者與寫者問題(reader--wｒiｔeｒprobｌems)(1０分)在計算機體系中，對一個共享文獻進行操作的進程可分為兩類：讀操作和寫操作，它們分別被稱為讀者和寫者。訪問該文獻時讀者和寫者,寫者和寫者間必須實現互斥。只有在沒有讀者訪問文獻時,寫者才允許修改文獻。或者寫者在修改文獻時不允許讀者去讀,否則會導致讀出的文獻內容不對的。試寫出算法描述讀者和寫者的問題。解：為了實現讀者與寫者的同步和互斥,我們設立一個信號量S，用于讀者與寫者之間或寫者與讀者之間的互斥，初值為“1”。用一個變量rc表達當前正在讀的讀者個數，當進程可以去讀或讀結束后都要改變rc的值，因此rc又成為若干讀進程的共享變量，它們必須互斥地修改ｒc。故必須定義另一個用于互斥的信號量Ｓr,初值也是“１”。讀者-－寫者問題可描述如下：Ｓ,Sｒ：semaｐhoｒe；intrc＝0；S=Sr=１；ｐroｃｅｓsＲeａderI（i=１,2,...,m）ｐrｏcessWriterj(j=1,2,...，k）beｇｉnbｅgiｎP(Ｓｒ);rｃ＝rc+１;P(S）；if(rc=＝1)P(S);WriｔｅｆileF;V（Sr);V(S);rｅａdfilｅF；ｅｎdＰ(Sｒ）；rc=tc-1;ｉf(ｒc＝=0)V(S)；Ｖ(Ｓr);ｅnｄ18、若干個等待訪問磁盤者依次要訪問的磁道為20，44,４0,4，80，12，７6,假設每移動一個磁道需要３毫秒時間,移動臂當前位于40號柱面,請按下列算法分別寫出訪問序列并計算為完畢上述各次訪問總共花費的尋道時間。（1)先來先服務算法；（2)最短尋道時間優先算法。（３）掃描算法（當前磁頭移動的方向為磁道遞增）（10分）解:(1)磁道訪問順序為:20,４4，４0,4,８0,12，76尋道時間=(20+24+4+3６+７6+６８+6４）＊3=29２*3=876(2）磁道訪問順序為:4０,44,20，12,4，７６,80尋道時間=(0+４＋24+8+8＋７2+4）*３=１２０＊3=3６０（3)磁道訪問順序為:4０,44,７6,80,20,１２，4尋道時間＝(0+４+3２+4+6０+8＋8）*3＝11６*３=34819、生產者和消費者問題（10分)有一組生產者P1，P2，……，PM和一組消費者C1，Ｃ2,……,ＣK，他們通過由n個環形緩沖區構成的緩沖池進行通信,生產者把產品放入緩沖區，消費者從緩沖區取產品來消費。請用wait和ｓignal原語實現他們的同步操作。解:生產者和消費者問題begｉnVarmutｅx，eｍpty，fｕll：seｍａｐｈｏre:=1，n,0;bｕｆｆｅr:array［0,…,n-1］ofitｅm;in,out：inｔeｇｅr：＝0，０;ｐａｒbegｉnproｄucｅr:?begｉｎ ??ｒeｐｅaｔ? ??producｅnextpｒoduct; ? ｗａit(emｐty）； ?wait(mｕｔex)； ?? ｂuffer(ｉｎ)：=nextp;?? iｎ:=（ｉｎ+1)ｍodn; ? sigｎaｌ（full); ?? signal(mutｅx）;? untilfalse；? ｅndcoｎsumer:begｉｎ ?repｅat ? ｗait(ｆull);? ?wait(mｕtｅx); ?ｎexｔc:=buｆfer(ouｔ);???ouｔ:=(out+1)mｏdn; ? ｓignal(empｔy); ?sigｎａl（muｔｅx); cｏnsｕmｅtｈｅiｔeminｎeｘtc; ? ｕnｔilｆalse; ?end?parenｄ enｄ2０、請用信號量描述哲學家進餐問題。（15分）解：哲學家進餐問題（1５分）publicｖｏidpｈｉlosoｐheｒ（inti){? whilｅ(true){? think(）； ? wait(fork[ｉ]）;???wait(ｆｏrk［(i+1)%5］); ??eat()； signａl(forｋ[（ｉ+1)%５]); sｉgnaｌ（forｋ［i]); } ?}21．今有三個并發進程R，M,P，它們共享了一個可循環使用的緩沖區B，緩沖區B共有N個單元。進程R負責從輸入設備讀信息，每讀一個字符后,把它存放在緩沖區B的一個單元中;進程M負責解決讀入的字符，若發現讀入的字符中有空格符，則把它改成“,”;進程Ｐ負責把解決后的字符取出并打印輸出。當緩沖區單元中的字符被進程P取出后，則又可用來存放下一次讀入的字符。請用PV操作為同步機制寫出它們能對的并發執行的程序。（10分)解:(１0分）beginVａrmutex，iｎput,caｌculatｅ，ｏutput：sｅmaphorｅ:=1,n,0，0;buffer:array[0，…,n-1]oｆitem；in,mid,ouｔ:integｅr：=0,０,0;proR(){ ｄｏ{? waｉｔ(iｎput);? ?waｉt(mutex）； buｆfeｒ(in）:=inpｕtdａta; ? ?iｎ：=（in+1)modn； ??signal（calcｕlate)；?? siｇnal(ｍｕtex); wｈiletrue； }proM(){?ｄo{ ? ｗait(calculａte)； ? ?ｗaｉt(ｍuteｘ）; ? ?buｆfer(middlｅ）:＝ｃalculatedatａ;?? ?miｄ：=(mid+１)ｍodn; signal（ｏuｔpｕt); ? ?ｓiｇｎaｌ（mutex);? ?}ｗhiｌｅｔruｅ；??｝ｐｒoＰ(){?ｄo{ ? wait(outpｕｔ);?? waｉt（mutｅｘ);? ??buｆｆeｒ(ｏｕｔ):=calcuｌatedata； ?? oｕt:=(ｏut+1)modｎ;?? ?siｇnal(inpｕt);?? ?signal(mｕｔex）；}whileｔrue; ?}22．理發店里有一位理發師、一把理發椅子和五把供等候理發的顧客坐的椅子。假如沒有顧客，理發師便在理發椅上睡覺。當一個顧客到來時,他必須先叫醒理發師,假如理發師正在理發時又有顧客來到,而假如有空椅子可坐，他們就坐下來等，假如沒有空椅子，他就離開。這里的問題是為理發師和顧客各編寫一段程序來描述他們行為，并用ｗaｉt和sｉgnal原語操作實現其同步。（１0分）解:理發師問題＃defineCHAIRＳ5/*為等候的顧客準備椅子數*/tyｐedefintseｍａphｏre;／＊運用你的想像力*/semｐｈorｅcuｓtｏmeｒs=0;/＊等候服務的顧客數*/seｍａphｏreｂarbers=０/*等候服務的理發師數*/semａphoremｕtｅｘ＝１;/*用于互斥＊/intwaiting=0;/＊還沒理發的等候顧客*／ｖoidbaｒｂeｒ（ｖoid）{wｈile（ＴRＵE){waiｔ(customers);/＊假如顧客數是0,則睡覺＊／wait(mutex);/＊規定進程等候*/waitiｎg=ｗａiting－1;/*等候顧客數減1＊／siｇnal(ｂａrbers）;/*一個理發師現在開始理發＊/siｇnａl(ｍuteｘ);/*釋放等候*/cut_ｈaｉr（);／*理發（非臨界區操作)＊/}voｉdcustｏmeｒs(ｖｏｉｄ）｛waiｔ(mutex）;if(waiting<CHAＩRＳ)｛ｗａｉting=ｗaｉting+1;siｇｎal(cuｓtｏmerｓ);ｓignaｌ（mｕtex)；wａit（ｂarbers）；}ｅlse{signａｌ(mｕtex)；}}23、根據如下的前趨圖寫出可并發執行的程序：(1０分)11234567解:（1０)評分:變量、進程、程序主體每項一分。vaｒa，b，c,d，ｅ，f,g,h,i:ｓｅmaphｏre:=0,0,0，0,0,0，0,0;bｅgin?ｐarbｅgｉn?beginＳ1;ｓiｇｎal(a);ｓignal（b);ｅnd begｉｎwaｉt（a）;S2;sｉgnａl(ｃ）；ｓignaｌ（d）;end bｅｇinwaiｔ(ｃ）;S3；sigｎal（e);sｉｇｎal（f);eｎｄ bｅginｗait(b);Ｓ4；sｉgnal（g);ｅnd?bｅginｗait(d)；ｗaｉt(ｅ)Ｓ5;signａｌ(ｈ）;ｅnｄ begｉnwaｉt(f);wａit(ｇ);S6;signａl（ｉ）;end?beｇiｎwait(ｈ);waiｔ(i);S7;ｅnd?parｅndeｎd2４、在公共汽車上，乘客上完后，售票員關門,駕駛員開車,售票員售票，到站汽車停穩后，售票員開門，乘客上下車，售票員和駕駛員之間密切配合，直到下班。請用信號量描述公共汽車上售票員與駕駛員的工作過程。(１0分）解：建立駕駛員和售票員兩進程,駕駛員進程執行過程如下：判售票員關門沒有開車到站后停車反復(1）-(3)售票員執行過程如下:判斷乘客上完沒有關門售票判車停穩沒有開門反復(1)-(5）2５、設某作業占有７個頁面,假如在主存中只允許裝入4個工作頁面(即工作集為4)，作業運營時，實際訪問頁面的順序是：1，2,3，6,4,7，3,2,１,4,7，5，6,5，2,1。試用ＦIFO、LＲU和CLＯCK頁面置換算法，列出各自的頁面淘汰順序和頁面置換次數。(10分）

解：ＦIＦO:?１,2，3,6，４，7，3,2,1,4,7,5，6，５，2，1111144４45５222277７７633322226６66１11頁面置換次數為：6次?LＲU：

１,2,３,６，4,7，３，２,1,4,7，5，6，5,２，１11114４４11