復(fù)習(xí)資料一、名詞解釋進程：進程是程序的一次執(zhí)行，該程序可與其他程序并發(fā)執(zhí)行。文件系統(tǒng)：指的是操作系統(tǒng)中與文件管理有關(guān)的那局部軟件和管理的文件以及管理所需要的一些數(shù)據(jù)集的總稱。進程控制塊：系統(tǒng)為了管理進程設(shè)置的一個專門的數(shù)據(jù)結(jié)構(gòu)，用它來記錄進程的外部特征，描述進程的運動變化過程。系統(tǒng)利用PCB來控制和管理進程，所以PCB是系統(tǒng)感知進程存在的唯一標(biāo)志。進程與PCB是一一對應(yīng)的。系統(tǒng)吞吐量：指的是系統(tǒng)在單位時間內(nèi)所完成的作業(yè)數(shù)目。文件控制塊：文件控制塊是操作系統(tǒng)為管理文件而設(shè)置的數(shù)據(jù)結(jié)構(gòu)，存放了為管理文件所需的所有有關(guān)信息。文件控制塊是文件存在的標(biāo)志。臨界區(qū)：每個進程中訪問臨界資源的那段代碼稱為臨界區(qū)。為了實現(xiàn)各進程對臨界資源的互斥訪問，應(yīng)保證各進程在各自進入自己的臨界區(qū)時互斥。虛擬存儲器：指具有請求功能和置換功能，能從邏輯上對內(nèi)存容量進行擴充的一種存儲器系統(tǒng)。邏輯地址：用戶程序經(jīng)過編譯或匯編形成的目標(biāo)代碼，通常采用相對地址形式，其首地址為零，其余指令中的地址都是相對首地址而定。這個相對地址就稱為邏輯地址或虛擬地址。存取權(quán)限：指的是允許用戶或用戶組對某文件進行訪問的權(quán)限。剝奪調(diào)度：當(dāng)一個進程正在執(zhí)行時，調(diào)度程序基于某種原那么，剝奪已分配給該進程的處理機，將它分配給其他進程并使之執(zhí)行。作業(yè)周轉(zhuǎn)時間：從作業(yè)進入系統(tǒng)開始，到作業(yè)完成并退出系統(tǒng)所經(jīng)歷的時間。多道程序：指在內(nèi)存中同時存放假設(shè)干個作業(yè)，并使它們同時運行的一種程序設(shè)計技術(shù)。在單機上，這些作業(yè)在宏觀上是同時運行的，而實質(zhì)上它們在交替運行。臨界區(qū)：每個進程中訪問臨界資源的那段代碼稱為臨界區(qū)。為了實現(xiàn)各進程對臨界資源的互斥訪問，應(yīng)保證各進程在各自進入自己的臨界區(qū)時互斥。靜態(tài)存儲分配：作業(yè)所需的內(nèi)存空間是在作業(yè)調(diào)入時分配的，在其整個運行期間，它一直占用，且不能再申請新的內(nèi)存空間，也不允許在內(nèi)存中移動。二、簡答題1.文件目錄的作用是什么？一個目錄項中應(yīng)包括哪些信息？答：計算機系統(tǒng)中的文件種類繁多，數(shù)量龐大，為了使用戶方便地找到所需文件，也為了系統(tǒng)更好地組織和管理文件，引入了文件目錄，因此文件目錄的主要作用就是負責(zé)對系統(tǒng)內(nèi)所有文件進行統(tǒng)一管理，使得用戶可以方便地按名存取文件。一個目錄項中應(yīng)包含的信息有文件名、有關(guān)文件結(jié)構(gòu)的信息、有關(guān)存儲控制信息、有關(guān)管理方面的信息等。2.進程的定義是什么？它最少有哪幾種狀態(tài)？答：進程是一個具有一定功能的程序關(guān)于某個數(shù)據(jù)集合的一次運行活動。一個進程最少有就緒、執(zhí)行和阻塞三種狀態(tài)。就緒狀態(tài)是指進程已獲得了除處理機以外的所有資源，一旦獲得處理機就可以立即執(zhí)行。執(zhí)行狀態(tài)是指進程獲得必要的資源并正在處理機上執(zhí)行。阻塞狀態(tài)是指進程由于發(fā)生某事件而暫時無法執(zhí)行下去，此時即使把處理機分配給該進程，它也無法運行。3.請給出操作系統(tǒng)的定義，并說明現(xiàn)代操作系統(tǒng)的根本特征是什么？答：操作系統(tǒng)是控制和管理計算機系統(tǒng)的硬件和軟件資源，合理地組織計算機工作流程以及方便用戶的程序集合?，F(xiàn)代操作系統(tǒng)的根本特征是：并發(fā)性、共享性和不確定性。4.作業(yè)調(diào)度的主要功能是什么？常用的作業(yè)調(diào)度算法有哪些？答：作業(yè)調(diào)度的主要功能包括：1〕記錄進入系統(tǒng)的各個作業(yè)情況；2〕從后備作業(yè)中挑選一些作業(yè)投入執(zhí)行；3〕為被選中的作業(yè)做好執(zhí)行前的準備工作；4〕在作業(yè)執(zhí)行結(jié)束或執(zhí)行過程中因某種原因需要撤離時，作業(yè)調(diào)度程序還要完成作業(yè)的善后處理工作。常用的作業(yè)調(diào)度算法有：1〕先來先效勞算法；2〕最短作業(yè)優(yōu)先算法；3〕響應(yīng)比高者優(yōu)先算法。5.試比擬分段式和分頁式存儲管理方式的主要差異。答：分頁是將一個進程的邏輯地址空間分成假設(shè)干大小相等的局部，每一局部稱作頁面。分段是一組邏輯信息的集合，即一個作業(yè)中相對獨立的局部。分頁和分段的主要區(qū)別是：①頁是信息的物理單位，段是信息的邏輯單位；②頁的大小是由系統(tǒng)固定的，段的長度因段而異，由用戶決定；③分頁的作業(yè)地址空間是一維的，分段的作業(yè)地址空間是二維的。6.什么是系統(tǒng)“抖動”？該如何處理系統(tǒng)抖動？答：系統(tǒng)“抖動”是指某些頁面被頻繁地裝入和調(diào)出主存的現(xiàn)象。通常應(yīng)通過選擇那些能夠減少和防止抖動現(xiàn)象的頁面調(diào)度算法來處理抖動現(xiàn)象。7.實時系統(tǒng)分為哪幾類？在設(shè)計中要考慮哪些問題？答：實時系統(tǒng)分為實時控制系統(tǒng)和實時信息系統(tǒng)。在設(shè)計時應(yīng)該考慮的因素有：對進程或用戶請求的及時響應(yīng)、根據(jù)不同的實時控制精度調(diào)整系統(tǒng)和用戶的交互能力、提高系統(tǒng)的平安可靠性〔實時時鐘控制、連續(xù)人機對話、過載的防護、高可靠性〕。8.Dijkstra的銀行家算法的根本思想是什么？它能夠用來解決實際中的死鎖問題嗎？為什么？答：Dijkstra的銀行家算法是解決死鎖問題的一種策略，其根本思想是在進行資源分配前，先計算該次分配后系統(tǒng)是否平安，假設(shè)平安那么分配，否那么拒絕分配。該算法理論意義很好，但實際中卻很難使用。因為算法所假設(shè)的條件〔例如，進程預(yù)知申請資源的最大數(shù)量等〕在實際環(huán)境中并不成立。故它很難被用在實際中解決死鎖問題。9.為什么要引入分時系統(tǒng)？分時系統(tǒng)的特點是什么？答：因為在批量處理系統(tǒng)中，單個作業(yè)占用CPU時間長，且用戶往往不可能一次性組織大量的作業(yè)，而且無法預(yù)計大量作業(yè)在運行過程中出現(xiàn)的意外情況，容易導(dǎo)致程序不易調(diào)試等缺點。為了提高系統(tǒng)對多用戶的支持，使用戶能夠像使用一個獨立終端那樣使用計算機設(shè)備，從而引入了分時系統(tǒng)。分時系統(tǒng)的特點是：設(shè)備同時性、操作獨立性、響應(yīng)及時性、用戶交互性。10．什么是臨界資源和臨界區(qū)？對臨界區(qū)管理的根本要求是什么？答：臨界資源指的是可共享的資源，但一次僅允許一個進程使用〔即獨占資源〕。臨界區(qū)是指并發(fā)進程中與共享變量有關(guān)的程序段。對臨界區(qū)管理的根本要求是：一次最多讓一個進程在臨界區(qū)執(zhí)行；任何一個進入臨界區(qū)執(zhí)行的進程必須在有限的時間內(nèi)退出臨界區(qū)；不能強迫一個進程無限地等待進入臨界區(qū)。三、應(yīng)用題1.內(nèi)存中有兩個空閑區(qū)F1和F2，如下圖〔陰影局部表示已經(jīng)占用的區(qū)域〕。F1為210KB，F(xiàn)2為110KB，另外依次有A、B、C三個作業(yè)請求加載運行，它們的內(nèi)存需求量分別是60KB、140KB和70KB，請畫出采用最先適應(yīng)算法和最正確適應(yīng)算法的內(nèi)存空間分配圖，并比擬二者的性能。已用F1已用F2性能比擬：請翻看書本。2.設(shè)有一個信箱只能存放一封信件，只要信箱為空，進程A就不斷產(chǎn)生信件并送入信箱，只要信箱中有信件，進程B就不斷從信箱中取走信件進行處理。初始時，信箱為空。試用P、V操作表達進程A、B之間的關(guān)系。信號量規(guī)那么：此題中，設(shè)置兩個信號量full、empty，信號量full表示信箱中的信件數(shù)目，其初值為0；信號量empty表示信箱中的空位置數(shù)目，其初值為1。解：此題信號量規(guī)那么：設(shè)置兩個信號量full、empty，信號量full表示信箱中的信件數(shù)目，其初值為0；信號量empty表示信箱中的空位置數(shù)目，其初值為1。semaphoreempty=1;semaphorefull=0;main(){cobeginA();&&送信進程B();&&取信進程Coend;}A(){while(true){產(chǎn)生一封信件；p(emtpy);將信件放入信箱中；v(full);&&喚醒取信進程取信}}B(){while(true){p(full);從信箱中取出一封信件；v(empty);&&喚醒送信進程送信處理信件；}}3.有一籠子，當(dāng)籠子為空時，獵人或農(nóng)民可將一只動物放入籠子。如果放入籠子的是老虎，那么允許動物園抓走老虎，飯店必須等待；如果放入籠子的是豬，那么飯店可抓走豬，動物園必須等待。請用P、V操作描述該同步關(guān)系。此題設(shè)置三個信號量：Scage表示籠子是否為空，初值為1，即籠子為空；Spig表示籠子中是否有豬，初值為0；Stiger表示籠子中是否有老虎，初值為0；解：semaphoreScage=1;semaphoreSpig=0;semaphoreStiger=0;main(){CobeginHunter();Peasant();Hotel();Zoo();CoendHunter()&&獵人{while(true){P(Scage);將老虎趕入籠中；V(Stiger);}}Peasant()&&農(nóng)民{while(true){P(Scage);將豬趕入籠中；V(Spig);}}Hotel()&&飯店{while(true){P(Spig);從籠中抓走豬；V(Scage);}}Zoo()&&動物園{while(true){P(Stiger);從籠中抓走老虎；V(Scage);}}4．5個進程合作完成某一任務(wù)，其前趨圖如以下圖所示，試說明這5個進程間的同步關(guān)系，并用P、V操作描述它。信號量規(guī)那么：b2表示進程S2是否可以開始執(zhí)行，初值為0b3表示進程S3是否可以開始執(zhí)行，初值為0b4表示進程S4是否可以開始執(zhí)行，初值為0b5表示進程S5是否可以開始執(zhí)行，初值為0S1S1S3S2S3S2S4S4S5S5解：semaphoreb2=0;semaphoreb3=0;semaphoreb4=0;semaphoreb5=0;main(){cobegin;S1();S2();S3();S4();S5();Coend;}S1(){v(b2);v(b3);}S2(){p(b2);v(b4);}S3(){p(b3);v(b4);}S4(){p(b4);p(b4);v(b5);}S5()p(b5);}5.假定系統(tǒng)中有五個進程｛P0,P1,P2,P3,P4｝和四類資源｛A,B,C,D｝，各種資源的數(shù)量分別為6，15，14，16，假設(shè)系統(tǒng)運行中出現(xiàn)如下表所示的資源分配情況，請問該系統(tǒng)是否平安？如果進程P2此時提出資源申請〔1，0，0，0〕，請問系統(tǒng)是否能將資源分配給它？為什么？表：系統(tǒng)資源分配表 資源進程AllocationNeedAvailableP0001200124644P110001750P213542356P306320652P400140656解：〔1〕利用平安性算法對此刻的資源分配情況進行分析，得到如下表所示的平安性檢測情況： 資源進程Work'Need'Allocation'Work'+Allocation'FinishP04644001200124656TureP346560652063241288TureP44128806560014412912TureP141291217501000512912TureP2512912235613546151416Ture由以上分析可知，該時刻存在著一個平安序列{P0，P3，P4，P1，P2}，故系統(tǒng)是平安的。〔2〕如果進程P2要求〔1，0，0，0〕，按銀行家算法進行檢查：Request2〔1，0，0，0〕<=Need2〔2，3，5，6〕Request2〔1，0，0，0〕<=Available〔1，6，2，2〕試分配并修改相應(yīng)數(shù)據(jù)結(jié)構(gòu)，由此形成的資源分配情況如下表所示： 資源進程Work''Need''Allocation''Work''+Allocation''FinishP03644001200123656TureP336560652063231288TureP43128806560014312912TureP131291217501000412912TrueP2412912135623546151416True由以上分析可知，可找到一個平安序列{P0，P3，P4，P1，P2}，故系統(tǒng)能立即滿足進程的要求。6．表1給出了作業(yè)1、2、3的到達時間和運行時間。采用短作業(yè)優(yōu)先調(diào)度算法，填寫以下表2，并計算平均周轉(zhuǎn)時間T為多少？知識：作業(yè)的周轉(zhuǎn)時間是指：從作業(yè)提交到作業(yè)完成之間的時間間隔。短作業(yè)優(yōu)先調(diào)度算法：總是從作業(yè)的后備隊列中挑選估計運行時間最短的作業(yè)作為下一個調(diào)度運行的對象。表1：作業(yè)號到達時間運行時間〔小時〕10：008h20：404h31：001h表2：短作業(yè)優(yōu)先算法作業(yè)號〔注意順序〕到達時間運行時間開始時間完成時間周轉(zhuǎn)時間平均周轉(zhuǎn)時間解：短作業(yè)優(yōu)先算法作業(yè)號〔注意順序〕到達時間運行時間開始時間完成時間周轉(zhuǎn)時間10:008h0:008:008h31:001h8:009:008h20:404h9:0013:0012.6h平均周轉(zhuǎn)時間T=(8+8+12.6)/3=9.537.有兩個程序，