2025年大學(xué)《信息與計(jì)算科學(xué)》專業(yè)題庫——信息與計(jì)算科學(xué)的操作系統(tǒng)理論考試時(shí)間：______分鐘總分：______分姓名：______一、名詞解釋（每題3分，共15分）1.操作系統(tǒng)2.進(jìn)程3.臨界區(qū)4.虛擬內(nèi)存5.文件物理結(jié)構(gòu)二、簡答題（每題5分，共25分）1.簡述操作系統(tǒng)在計(jì)算機(jī)系統(tǒng)中的地位和作用。2.比較優(yōu)先級(jí)調(diào)度算法和先來先服務(wù)調(diào)度算法的主要區(qū)別。3.簡述使用信號(hào)量機(jī)制解決臨界區(qū)問題的基本思想。4.頁式存儲(chǔ)管理和段式存儲(chǔ)管理在地址轉(zhuǎn)換方面有何主要區(qū)別？5.簡述文件系統(tǒng)提供哪些基本功能。三、計(jì)算題（每題10分，共20分）1.設(shè)某系統(tǒng)有5個(gè)進(jìn)程，它們的到達(dá)時(shí)間和執(zhí)行時(shí)間如下表所示：|進(jìn)程編號(hào)|到達(dá)時(shí)間|執(zhí)行時(shí)間||:-------|:-------|:-------||P1|0|3||P2|1|6||P3|4|4||P4|6|5||P5|8|2|假設(shè)采用短作業(yè)優(yōu)先（SJF）調(diào)度算法（非搶占式），計(jì)算所有進(jìn)程的平均周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間。2.設(shè)內(nèi)存塊數(shù)為4，進(jìn)程所需內(nèi)存頁數(shù)分別為3頁、2頁、3頁。內(nèi)存采用頁式管理，初始時(shí)內(nèi)存為空。使用LRU頁面置換算法，模擬以下地址流（0,1,2,0,3,0,1,2,3,4）的缺頁情況。四、分析題（每題12分，共24分）1.設(shè)有四個(gè)進(jìn)程P0,P1,P2,P3需要共享一個(gè)臨界資源。若當(dāng)前只有P0進(jìn)入臨界區(qū)，試設(shè)計(jì)一個(gè)使用信號(hào)量S和P、V操作的同步協(xié)議，確保這四個(gè)進(jìn)程能正確地訪問臨界資源，并避免死鎖的發(fā)生。2.比較索引文件和索引順序文件（ISAM）在存儲(chǔ)空間利用率、讀寫速度和適用場(chǎng)景方面的優(yōu)缺點(diǎn)。試卷答案一、名詞解釋1.操作系統(tǒng)：是計(jì)算機(jī)系統(tǒng)中的系統(tǒng)軟件，它控制和管理計(jì)算機(jī)的硬件與軟件資源，合理地組織計(jì)算機(jī)的工作流程，為用戶使用計(jì)算機(jī)提供方便的接口，并保證計(jì)算機(jī)系統(tǒng)安全、高效、可靠地運(yùn)行。**解析思路：*定義應(yīng)包含操作系統(tǒng)的基本功能（資源管理、工作流程組織、接口提供）和目標(biāo)（方便用戶、高效可靠運(yùn)行）。2.進(jìn)程：是計(jì)算機(jī)系統(tǒng)中正在運(yùn)行的程序的一個(gè)實(shí)例。它是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位，具有動(dòng)態(tài)性、并發(fā)性、獨(dú)立性、異步性和結(jié)構(gòu)特征（地址空間、程序段、數(shù)據(jù)段、系統(tǒng)棧、進(jìn)程控制塊PCB）。**解析思路：*定義需點(diǎn)明進(jìn)程是程序執(zhí)行的過程，強(qiáng)調(diào)其作為資源分配和調(diào)度單位的角色，并提及進(jìn)程的主要特征。3.臨界區(qū)：指進(jìn)程中訪問共享變量的那一部分代碼片段，這部分代碼在同一時(shí)刻只能有一個(gè)進(jìn)程進(jìn)入執(zhí)行。**解析思路：*定義要明確指出臨界區(qū)是代碼片段，關(guān)鍵在于其訪問共享變量且互斥執(zhí)行的性質(zhì)。4.虛擬內(nèi)存：是一種讓計(jì)算機(jī)用戶感覺內(nèi)存容量比實(shí)際物理內(nèi)存更大的技術(shù)。它通過將內(nèi)存劃分為頁面或段，并將部分不常用的頁面或段暫時(shí)移到磁盤上的交換空間，從而使得更大規(guī)模的程序能夠運(yùn)行。**解析思路：*定義需說明虛擬內(nèi)存的效果（感覺內(nèi)存更大）及其實(shí)現(xiàn)方式（分頁/分段、部分移至磁盤）。5.文件物理結(jié)構(gòu)：指在物理存儲(chǔ)設(shè)備（通常是磁盤）上如何組織文件的數(shù)據(jù)塊。常見的有連續(xù)結(jié)構(gòu)（順序文件）、鏈接結(jié)構(gòu)（鏈接文件）和索引結(jié)構(gòu)（索引文件）。**解析思路：*定義要說明文件物理結(jié)構(gòu)是關(guān)于數(shù)據(jù)塊在磁盤上的組織方式，并提及常見類型。二、簡答題1.操作系統(tǒng)在計(jì)算機(jī)系統(tǒng)中的地位和作用：*操作系統(tǒng)是計(jì)算機(jī)系統(tǒng)中最核心的系統(tǒng)軟件，位于硬件與應(yīng)用程序之間，是計(jì)算機(jī)硬件和其他軟件的接口。*它負(fù)責(zé)管理計(jì)算機(jī)系統(tǒng)的所有硬件資源（如CPU、內(nèi)存、磁盤、I/O設(shè)備等），為應(yīng)用程序提供資源分配和使用的環(huán)境。*它通過進(jìn)程管理、內(nèi)存管理、文件管理、設(shè)備管理和系統(tǒng)接口等功能，提高了計(jì)算機(jī)系統(tǒng)的資源利用率，增強(qiáng)了系統(tǒng)的并行處理能力，為用戶提供了方便、有效、安全的工作平臺(tái)。*簡單來說，操作系統(tǒng)控制計(jì)算機(jī)的運(yùn)行，管理計(jì)算機(jī)的各種資源，并為用戶和應(yīng)用程序提供服務(wù)。**解析思路：*從定位（核心軟件、接口）、功能（資源管理、提供環(huán)境）、目標(biāo)（提高利用率、增強(qiáng)并行、方便用戶）等多個(gè)層面回答，覆蓋其核心作用。2.優(yōu)先級(jí)調(diào)度算法和先來先服務(wù)調(diào)度算法的主要區(qū)別：*調(diào)度依據(jù)不同：FCFS依據(jù)進(jìn)程到達(dá)的先后順序；優(yōu)先級(jí)調(diào)度依據(jù)進(jìn)程的優(yōu)先級(jí)。*調(diào)度結(jié)果不同：FCFS可能導(dǎo)致優(yōu)先級(jí)高的進(jìn)程等待時(shí)間過長（starvation）；優(yōu)先級(jí)調(diào)度可以確保高優(yōu)先級(jí)進(jìn)程優(yōu)先獲得CPU，但可能導(dǎo)致低優(yōu)先級(jí)進(jìn)程饑餓。*算法類型不同：FCFS屬于非搶占式；優(yōu)先級(jí)調(diào)度可以是搶占式或非搶占式。**解析思路：*對(duì)比兩個(gè)算法在調(diào)度規(guī)則、可能產(chǎn)生的效果（公平性、饑餓問題）以及是否搶占式等方面的差異。3.使用信號(hào)量機(jī)制解決臨界區(qū)問題的基本思想：*使用一個(gè)信號(hào)量S，初始值設(shè)為1。每個(gè)進(jìn)程在進(jìn)入臨界區(qū)前執(zhí)行P(S)操作（等待），在離開臨界區(qū)后執(zhí)行V(S)操作（釋放）。*P(S)操作會(huì)檢查S的值，若S>0，則將S減1，進(jìn)程繼續(xù)執(zhí)行；若S=0，則進(jìn)程暫停，放入等待隊(duì)列，等待其他進(jìn)程執(zhí)行V(S)。*V(S)操作會(huì)將S加1，若等待隊(duì)列中有進(jìn)程，則喚醒其中一個(gè)進(jìn)程。*這種機(jī)制確保了每次只有一個(gè)進(jìn)程能進(jìn)入臨界區(qū)，并且進(jìn)程進(jìn)入和離開臨界區(qū)的過程是原子操作，從而解決了臨界區(qū)問題。**解析思路：*描述使用信號(hào)量S及其初值，明確進(jìn)入（P(S)）和離開（V(S)）臨界區(qū)的操作，并解釋其如何保證互斥和進(jìn)程能夠退出。4.頁式存儲(chǔ)管理和段式存儲(chǔ)管理在地址轉(zhuǎn)換方面的主要區(qū)別：*地址劃分單位不同：頁式管理將用戶邏輯地址空間和物理內(nèi)存空間都劃分為固定大小的頁和塊（頁框），單位是頁/塊；段式管理將用戶邏輯地址空間劃分為大小可變的邏輯段（程序段、數(shù)據(jù)段等），單位是段。*地址轉(zhuǎn)換過程不同：頁式管理需要通過頁表（通常在內(nèi)存中）將邏輯頁號(hào)映射到物理塊號(hào)，地址變換涉及頁表基址、頁內(nèi)偏移、頁表項(xiàng)中的塊號(hào)；段式管理需要通過段表（通常在內(nèi)存中）將邏輯段號(hào)映射到物理內(nèi)存中的段起始地址（段基址），地址變換涉及段表基址、段內(nèi)偏移、段表項(xiàng)中的段基址。*內(nèi)存碎片不同：頁式管理會(huì)產(chǎn)生內(nèi)部碎片（分配的塊可能比請(qǐng)求的頁大），但無外部碎片（內(nèi)存空間是連續(xù)的）；段式管理可能產(chǎn)生外部碎片（不同段的剩余空間不連續(xù)），但無內(nèi)部碎片。**解析思路：*對(duì)比兩種管理方式在邏輯/物理空間劃分、地址轉(zhuǎn)換所需數(shù)據(jù)結(jié)構(gòu)（頁表/段表）和過程、以及產(chǎn)生的內(nèi)存碎片類型上的差異。5.文件系統(tǒng)提供的基本功能：*文件創(chuàng)建與刪除：提供創(chuàng)建新文件、刪除不再使用的文件的操作。*文件讀寫操作：允許用戶讀取文件內(nèi)容、寫入新內(nèi)容或修改現(xiàn)有內(nèi)容。*文件目錄管理：提供創(chuàng)建、刪除目錄，以及文件在目錄中的組織、查找功能。*文件屬性管理：存儲(chǔ)和設(shè)置文件的屬性信息（如讀寫權(quán)限、所有者、大小、創(chuàng)建時(shí)間等）。*文件共享與保護(hù)：提供機(jī)制讓多個(gè)用戶或進(jìn)程能共享訪問文件，并設(shè)置權(quán)限以保護(hù)文件不被未授權(quán)訪問或修改。*存儲(chǔ)空間管理：管理磁盤上的可用空間，分配空間給新文件，回收不再使用的空間。**解析思路：*列舉文件系統(tǒng)作為用戶與存儲(chǔ)設(shè)備之間的接口所提供的一系列管理文件和文件系統(tǒng)的操作與服務(wù)。三、計(jì)算題1.計(jì)算所有進(jìn)程的平均周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間：*周轉(zhuǎn)時(shí)間=完成時(shí)間-到達(dá)時(shí)間*帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/執(zhí)行時(shí)間*計(jì)算完成時(shí)間（按SJF非搶占式）：*P1:到達(dá)0，執(zhí)行3，完成時(shí)間=0+3=3*P5:到達(dá)8，但P1未完成，需等待，執(zhí)行2，完成時(shí)間=3+2=5*P3:到達(dá)4，但P1、P5未完成，需等待，執(zhí)行4，完成時(shí)間=5+4=9*P2:到達(dá)1，P1已完成，執(zhí)行6，完成時(shí)間=3+6=9*P4:到達(dá)6，P1、P5已完成，P3、P2未完成，執(zhí)行5，完成時(shí)間=9+5=14*計(jì)算周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間：*P1:周轉(zhuǎn)時(shí)間=3-0=3,帶權(quán)周轉(zhuǎn)時(shí)間=3/3=1*P5:周轉(zhuǎn)時(shí)間=5-8=-3(修正：應(yīng)為5-8=-3，但通常周轉(zhuǎn)時(shí)間非負(fù)，理解為P5完成時(shí)間5小于其到達(dá)時(shí)間8，表示它在P1完成后才到達(dá)并運(yùn)行，或理解為計(jì)算有誤，應(yīng)為P5等待P1完成，P1完成時(shí)間3，P5開始執(zhí)行時(shí)間3，P5執(zhí)行2，完成時(shí)間3+2=5。按此邏輯：P1完成時(shí)間3，P5到達(dá)時(shí)間8，P5開始執(zhí)行時(shí)間=max(3,8)=8，執(zhí)行時(shí)間2，完成時(shí)間=8+2=10。周轉(zhuǎn)時(shí)間=10-8=2，帶權(quán)周轉(zhuǎn)時(shí)間=2/2=1。*修正計(jì)算過程：**P1:到達(dá)0，執(zhí)行3，完成時(shí)間=0+3=3*P5:到達(dá)8，P1完成，執(zhí)行2，完成時(shí)間=3+2=5*P3:到達(dá)4，P1完成，執(zhí)行4，完成時(shí)間=3+4=7*P2:到達(dá)1，P1完成，執(zhí)行6，完成時(shí)間=3+6=9*P4:到達(dá)6，P1、P5完成，執(zhí)行5，完成時(shí)間=9+5=14*重新計(jì)算：*P1:完成時(shí)間3，周轉(zhuǎn)時(shí)間3，帶權(quán)周轉(zhuǎn)時(shí)間1*P5:到達(dá)8，P1完成時(shí)間3，開始執(zhí)行時(shí)間=max(3,8)=8，執(zhí)行2，完成時(shí)間=8+2=10，周轉(zhuǎn)時(shí)間=10-8=2，帶權(quán)周轉(zhuǎn)時(shí)間=2/2=1*P3:到達(dá)4，P1完成時(shí)間3，開始執(zhí)行時(shí)間=max(3,4)=4，執(zhí)行4，完成時(shí)間=4+4=8，周轉(zhuǎn)時(shí)間=8-4=4，帶權(quán)周轉(zhuǎn)時(shí)間=4/4=1*P2:到達(dá)1，P1完成時(shí)間3，開始執(zhí)行時(shí)間=max(3,1)=3，執(zhí)行6，完成時(shí)間=3+6=9，周轉(zhuǎn)時(shí)間=9-1=8，帶權(quán)周轉(zhuǎn)時(shí)間=8/6=4/3*P4:到達(dá)6，P1、P5完成時(shí)間3、10，P3完成時(shí)間8，P2完成時(shí)間9，開始執(zhí)行時(shí)間=max(3,6)=6，執(zhí)行5，完成時(shí)間=6+5=11，周轉(zhuǎn)時(shí)間=11-6=5，帶權(quán)周轉(zhuǎn)時(shí)間=5/5=1*平均周轉(zhuǎn)時(shí)間=(3+2+4+8/3+5)/5=(15+8/3)/5=(45+8)/15=53/15≈3.53*平均帶權(quán)周轉(zhuǎn)時(shí)間=(1+1+1+4/3+1)/5=(3+4/3)/5=(9+4)/15=13/15≈0.87**解析思路：*按照SJF非搶占式原則，模擬進(jìn)程執(zhí)行順序，依次計(jì)算每個(gè)進(jìn)程的完成時(shí)間，然后根據(jù)完成時(shí)間和到達(dá)時(shí)間計(jì)算周轉(zhuǎn)時(shí)間，再計(jì)算帶權(quán)周轉(zhuǎn)時(shí)間。注意處理進(jìn)程到達(dá)時(shí)間與前一進(jìn)程完成時(shí)間的關(guān)系，確定進(jìn)程的實(shí)際開始執(zhí)行時(shí)間。最后計(jì)算平均值。2.模擬LRU頁面置換算法的缺頁情況：*內(nèi)存塊數(shù)：4*地址流：0,1,2,0,3,0,1,2,3,4*初始狀態(tài)：[,,,](空)*0:缺頁，頁0裝入，[0,,,]，缺頁次數(shù)=1*1:缺頁，頁1裝入，[0,1,,]，缺頁次數(shù)=2*2:缺頁，頁2裝入，[0,1,2,]，缺頁次數(shù)=3*0:頁0已在內(nèi)存，不缺頁，[0,1,2,](頁序?yàn)?,1,2)*3:缺頁，需替換。檢查頁0(0),頁1(1),頁2(2)，均未訪問過最近一次（按順序）。按LRU，替換最久未訪問或剛訪問過的（或按地址流順序第一個(gè)）。這里按地址流順序，頁0是最早進(jìn)入的，替換頁0。[3,1,2,]，缺頁次數(shù)=4*0:缺頁，頁0裝入，替換頁3。檢查頁3(剛出),頁1(1),頁2(2)，頁0不在。裝入頁0。[0,1,2,3]，缺頁次數(shù)=5*1:頁1已在內(nèi)存，不缺頁，[0,1,2,3]*2:頁2已在內(nèi)存，不缺頁，[0,1,2,3]*3:頁3已在內(nèi)存，不缺頁，[0,1,2,3]*4:缺頁，需替換。檢查頁0(0),頁1(1),頁2(2),頁3(3)，均未訪問過最近一次。按地址流順序，頁0是最早進(jìn)入的，替換頁0。[4,1,2,3]，缺頁次數(shù)=6*最終缺頁次數(shù)：6**解析思路：*按照地址流順序逐個(gè)地址訪問。若地址已在內(nèi)存塊中，則不缺頁，并可能需要更新頁面使用情況（用于后續(xù)可能的替換決策）。若地址不在內(nèi)存塊中，則發(fā)生缺頁中斷。*對(duì)于LRU算法，需要知道最近最少使用的頁面。通常采用棧模擬或記錄頁面使用時(shí)間戳。*簡化模擬：在沒有更復(fù)雜機(jī)制時(shí)，可以按地址流順序，當(dāng)需要替換時(shí)，選擇按地址流首次出現(xiàn)順序最早（即最久未使用）的頁面進(jìn)行替換。或者，如果所有頁面都“最近”使用過（例如剛進(jìn)入），則替換第一個(gè)裝入的頁面。此處采用按地址流首次出現(xiàn)順序最早的原則進(jìn)行替換。模擬過程中記錄內(nèi)存中的頁面序列和每次缺頁后的狀態(tài)。四、分析題1.設(shè)計(jì)使用信號(hào)量S和P、V操作的同步協(xié)議：*信號(hào)量定義：定義信號(hào)量S，初始值S=1。*進(jìn)程P0、P1、P2、P3進(jìn)入臨界區(qū)的操作：1.`P(S)`;//等待操作，若S>0，S減1；若S=0，進(jìn)程暫停等待，釋放CPU。2.進(jìn)入臨界區(qū)。3.`V(S)`;//信號(hào)操作，S加1。若等待隊(duì)列中有進(jìn)程，則喚醒其中一個(gè)。4.離開臨界區(qū)。*分析：*當(dāng)?shù)谝粋€(gè)進(jìn)程（如P0）執(zhí)行`P(S)`時(shí)，S減為0，P0進(jìn)入臨界區(qū)。*后續(xù)進(jìn)程（如P1）執(zhí)行`P(S)`時(shí)，因S=0，P1被阻塞，放入等待隊(duì)列。*當(dāng)P0執(zhí)行`V(S)`時(shí)，S變?yōu)?，喚醒等待隊(duì)列中的P1。*P1隨后執(zhí)行`P(S)`，S減為0，P1進(jìn)入臨界區(qū)。*依此類推，每個(gè)進(jìn)程在進(jìn)入臨界區(qū)前必須執(zhí)行`P(S)`獲取許可（S減1），在退出時(shí)執(zhí)行`V(S)`釋放許可（S加1）。*由于`P(S)`和`V(S)`是原子操作，且每次`V(S)`至多喚醒一個(gè)阻塞進(jìn)程，因此任何時(shí)候最多只有一個(gè)進(jìn)程能在臨界區(qū)中執(zhí)行。*該協(xié)議滿足互斥（每次只有一個(gè)進(jìn)程在臨界區(qū)）、進(jìn)步（等待進(jìn)程最終能進(jìn)入臨界區(qū)，因只有進(jìn)程退出時(shí)才能調(diào)用`V(S)`）和有限等待（每個(gè)進(jìn)程最多等待一次`V(S)`操作）的性質(zhì)。**解析思路：*明確信號(hào)量的定義和初值。為每個(gè)進(jìn)程進(jìn)入臨界區(qū)設(shè)計(jì)固定的`P(S)`操作序列，為退出設(shè)計(jì)固定的`V(S)`操作序列。通過分析`P(S)`和`V(S)`的執(zhí)行過程，證明該協(xié)議能保證臨界區(qū)互斥（S的值保證互斥）和進(jìn)程進(jìn)步（等待隊(duì)列最終能被喚醒）。有限等待在此簡單模型中通常成立。2.比較索引文件和索引順序文件（ISAM）的優(yōu)缺點(diǎn)：*索引文件(IndexFile):*優(yōu)點(diǎn)：*提高查找速度：通過索引（通常是B樹等平衡樹結(jié)構(gòu)）可以快速定位文件記錄，查找效率高，接近對(duì)數(shù)時(shí)間復(fù)雜度。*支持隨機(jī)訪問：可以直接根據(jù)索引快速訪問特定記錄。*節(jié)省空間（相對(duì)直接文件）：對(duì)于記錄數(shù)量龐大、記錄大小不一或查詢不頻繁的文件，索引文件可能比將所有記錄按順序存儲(chǔ)的直接文件更節(jié)省存儲(chǔ)空間（索引本身占空間，但可能減少冗余）。*缺點(diǎn)：*需要額外空間：需要額外的空間來存儲(chǔ)索引結(jié)構(gòu)。*維護(hù)開銷：插入、刪除記錄時(shí)，需要更新索引結(jié)構(gòu)，維護(hù)成本較高。*讀取全部記錄效率低：如果需要順序讀取