操作系統(tǒng)習(xí)題課

操作系統(tǒng)習(xí)題課1.何謂操作系統(tǒng)？配置操作系統(tǒng)的主要目的是什么？答：操作系統(tǒng)是管理系統(tǒng)資源、控制程序執(zhí)行，改善人機(jī)界面，提供各種服務(wù)，合理組織計(jì)算機(jī)工作流程和為用戶使用計(jì)算機(jī)提供良好運(yùn)行環(huán)境的一種系統(tǒng)軟件。配置操作系統(tǒng)的主要目標(biāo)可歸結(jié)為：Q方便用戶使用：OS通過提供用戶與計(jì)算機(jī)之間的友善接口來方便用戶使用。Q擴(kuò)大機(jī)器功能：OS通過擴(kuò)充改造硬件設(shè)施和提供新的服務(wù)來擴(kuò)大機(jī)器功能。Q管理系統(tǒng)資源：OS有效管理好系統(tǒng)中所有硬件軟件資源，使之得到充分利用。Q提高系統(tǒng)效率：OS合理組織好計(jì)算機(jī)的工作流程，以改進(jìn)系統(tǒng)性能和提高系統(tǒng)效率。Q構(gòu)筑開放環(huán)境：OS遵循有關(guān)國際標(biāo)準(zhǔn)來設(shè)計(jì)和構(gòu)造，以構(gòu)筑出一個(gè)開放環(huán)境。其含義主要是指：遵循有關(guān)國際標(biāo)準(zhǔn)(如開放的通信標(biāo)準(zhǔn)、開放的用戶接口標(biāo)準(zhǔn)、開放的線程庫標(biāo)準(zhǔn)等)；支持體系結(jié)構(gòu)的可伸縮性和可擴(kuò)展性；支持應(yīng)用程序在不同平臺上的可移植性和可互操作性。2.操作系統(tǒng)的主要特性有哪些？答：0并發(fā)性。并發(fā)性(concurrence)是指兩個(gè)或兩個(gè)以上的事件或活動(dòng)在同一時(shí)間間隔內(nèi)發(fā)生。操作系統(tǒng)是一個(gè)并發(fā)系統(tǒng)，并發(fā)性是它的重要特征，操作系統(tǒng)的并發(fā)性指它應(yīng)該具有處理和調(diào)度多個(gè)程序同時(shí)執(zhí)行的能力。多個(gè)I/O設(shè)備同時(shí)在輸入輸出；設(shè)備I/O和CPU計(jì)算同時(shí)進(jìn)行；內(nèi)存中同時(shí)有多個(gè)系統(tǒng)和用戶程序被啟動(dòng)交替、穿插地執(zhí)行，這些都是并發(fā)性的例子。發(fā)揮并發(fā)性能夠消除計(jì)算機(jī)系統(tǒng)中部件和部件之間的相互等待，有效地改善系統(tǒng)資源的利用率，改進(jìn)系統(tǒng)的吞吐率，提高系統(tǒng)效率。例如，一個(gè)程序等待I/O時(shí)，就出讓CPU，而調(diào)度另一個(gè)程序占有CPU執(zhí)行運(yùn)行。這樣，在程序等待C/O時(shí)，CPU便不會空閑，這就是并發(fā)技術(shù)。并發(fā)性雖然能有效改善系統(tǒng)資源的利用率，但卻會引發(fā)一系列的問題，使操作系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)變得復(fù)雜化。如：怎樣從一個(gè)運(yùn)行程序切換到另一個(gè)運(yùn)行程序？以什么樣的策略來選擇下一個(gè)運(yùn)行的程序?怎樣將各個(gè)運(yùn)行程序隔離開來，使之互不干擾，免遭對方破壞？怎樣讓多個(gè)運(yùn)行程序互通消息和協(xié)作完成任務(wù)？怎樣協(xié)調(diào)多個(gè)運(yùn)行程序?qū)Y源的競爭？多個(gè)運(yùn)行程序共享文件數(shù)據(jù)時(shí)，如何保證數(shù)據(jù)的一致性？操作系統(tǒng)必須具有控制和管理程序并發(fā)執(zhí)行的能力，為了更好的解決上述問題，操作系統(tǒng)必須提供機(jī)制和策略來進(jìn)行協(xié)調(diào)，以使各個(gè)并發(fā)進(jìn)程能順利推進(jìn)，并獲得正確的運(yùn)行結(jié)果。另外，操作系統(tǒng)還要合理組織計(jì)算機(jī)工作流程，協(xié)調(diào)各類硬軟件設(shè)施工作，充分提高資源的利用率，充分發(fā)揮系統(tǒng)的并行性，這些也都是在操作系統(tǒng)的統(tǒng)一指揮和管理下進(jìn)行的。采用了并發(fā)技術(shù)的系統(tǒng)又稱為多任務(wù)系統(tǒng)(multitaskingsystem)，計(jì)算機(jī)系統(tǒng)中，并發(fā)實(shí)際上是一個(gè)物理CPU在若干道程序之間多路復(fù)用，這樣就可以實(shí)現(xiàn)運(yùn)行程序之間的并發(fā)，以及CPU與I/O設(shè)備、I/O設(shè)備與I/O設(shè)備之間的并行，并發(fā)性的實(shí)質(zhì)是對有限物理資源強(qiáng)制行使多用戶共享以提高效率。在多處理器系統(tǒng)中，程序的并發(fā)性不僅體現(xiàn)在宏觀上，而且體現(xiàn)在微觀上(即在多個(gè)CPU上)也是并發(fā)的，又稱并行的。并行性(parallelism)是指兩個(gè)或兩個(gè)以上事件或活動(dòng)在同一時(shí)刻發(fā)生。在多道程序環(huán)境下，并行性使多個(gè)程序同一時(shí)刻可在不同CPU上同時(shí)執(zhí)行。而在分布式系統(tǒng)中，多臺計(jì)算機(jī)的并存使程序的并發(fā)性得到了更充分的發(fā)揮。可見并行性是并發(fā)性的特例，而并發(fā)性是并行性的擴(kuò)展。由于并發(fā)技術(shù)的本質(zhì)思想是：當(dāng)一個(gè)程序發(fā)生事件(如等待I/O)時(shí)出讓其占用的CPU而由另一個(gè)程序運(yùn)行，據(jù)此不難看出，實(shí)現(xiàn)并發(fā)技術(shù)的關(guān)鍵之一是如何對系統(tǒng)內(nèi)的多個(gè)運(yùn)行程序(進(jìn)程)進(jìn)行切換的技術(shù)。Q共享性(sharing)。共享性是操作系統(tǒng)的另一個(gè)重要特性。共享指操作系統(tǒng)中的資源(包括硬件資源和信息資源)可被多個(gè)并發(fā)執(zhí)行的進(jìn)程共同使用，而不是被一個(gè)進(jìn)程所獨(dú)占。出于經(jīng)濟(jì)上的考慮，一次性向每個(gè)用戶程序分別提供它所需的全部資源不但是浪費(fèi)的，有時(shí)也是不可能的?，F(xiàn)實(shí)的方法是讓操作系統(tǒng)和多個(gè)用戶程序共用一套計(jì)算機(jī)系統(tǒng)的所有資源，因而，必然會產(chǎn)生共享資源的需要。資源共享的方式可以分成兩種：第一種是互斥訪問。系統(tǒng)中的某些資源如打印機(jī)、磁帶機(jī)、卡片機(jī)，雖然它們可提供給多個(gè)進(jìn)程使用，但在同一時(shí)間內(nèi)卻只允許一個(gè)進(jìn)程訪問這些資源，即要求互相排斥地使用這些資源。當(dāng)一個(gè)進(jìn)程還在使用該資源時(shí)，其他欲訪問該資源的進(jìn)程必須等待，僅當(dāng)該進(jìn)程訪問完畢并釋放資源后，才允許另一進(jìn)程對該資源訪問。這種同一時(shí)間內(nèi)只允許一個(gè)進(jìn)程訪問的資源稱臨界資源，許多物理設(shè)備，以及某些數(shù)據(jù)和表格都是臨界資源，它們只能互斥地被共享。第二種是同時(shí)訪問。系統(tǒng)中還有許多資源，允許同一時(shí)間內(nèi)多個(gè)進(jìn)程對它們進(jìn)行訪問，這里“同時(shí)”是宏觀上的說法。典型的可供多進(jìn)程同時(shí)訪問的資源是磁盤，可重入程序也可被同時(shí)訪問。與共享性有關(guān)的問題是資源分配、信息保護(hù)、存取控制等，必須要妥善解決好這些問題。共享性和并發(fā)性是操作系統(tǒng)兩個(gè)最基本的特性，它們互為依存。一方面，資源的共享是因?yàn)槌绦虻牟l(fā)執(zhí)行而引起的，若系統(tǒng)不允許程序并發(fā)執(zhí)行，自然也就不存在資源共享問題。另一方面，若系統(tǒng)不能對資源共享實(shí)施有效管理，必然會影響到程序的并發(fā)執(zhí)行，甚至程序無法并發(fā)執(zhí)行，操作系統(tǒng)也就失去了并發(fā)性，導(dǎo)致整個(gè)系統(tǒng)效率低下。Q異步性(asynchronism)。操作系統(tǒng)的第三個(gè)特性是異步性，或稱隨機(jī)性。在多道程序環(huán)境中，允許多個(gè)進(jìn)程并發(fā)執(zhí)行，由于資源有限而進(jìn)程眾多，多數(shù)情況，進(jìn)程的執(zhí)行不是一貫到底，而是“走走停?！薄＠?，一個(gè)進(jìn)程在CPU上運(yùn)行一段時(shí)間后，由于等待資源滿足或事件發(fā)生，它被暫停執(zhí)行，CPU轉(zhuǎn)讓給另一個(gè)進(jìn)程執(zhí)行。系統(tǒng)中的進(jìn)程何時(shí)執(zhí)行？何時(shí)暫停？以什么樣的速度向前推進(jìn)？進(jìn)程總共要化多少時(shí)間執(zhí)行才能完成？這些都是不可預(yù)知的，或者說該進(jìn)程是以異步方式運(yùn)行的，其導(dǎo)致的直接后果是程序執(zhí)行結(jié)果可能不唯一。異步性給系統(tǒng)帶來了潛在的危險(xiǎn)，有可能導(dǎo)致進(jìn)程產(chǎn)生與時(shí)間有關(guān)的錯(cuò)誤，但只要運(yùn)行環(huán)境相同，操作系統(tǒng)必須保證多次運(yùn)行進(jìn)程，都會獲得完全相同的結(jié)果。操作系統(tǒng)中的隨機(jī)性處處可見，例如，作業(yè)到達(dá)系統(tǒng)的類型和時(shí)間是隨機(jī)的；操作員發(fā)出命令或按按鈕的時(shí)刻是隨機(jī)的；程序運(yùn)行發(fā)生錯(cuò)誤或異常的時(shí)刻是隨機(jī)的；各種各樣硬件和軟件中斷事件發(fā)生的時(shí)刻是隨機(jī)的等等，操作系統(tǒng)內(nèi)部產(chǎn)生的事件序列有許許多多可能，而操作系統(tǒng)的一個(gè)重要任務(wù)是必須確保捕捉任何一種隨機(jī)事件，正確處理可能發(fā)生的隨機(jī)事件，正確處理任何一種產(chǎn)生的事件序列，否則將會導(dǎo)致嚴(yán)重后果。Q虛擬性(virtual)。虛擬性是指操作系統(tǒng)中的一種管理技術(shù)，它是把物理上的一個(gè)實(shí)體變成邏輯上的多個(gè)對應(yīng)物，或把物理上的多個(gè)實(shí)體變成邏輯上的一個(gè)對應(yīng)物的技術(shù)。顯然，前者是實(shí)際存在的而后者是虛構(gòu)假想的，采用虛擬技術(shù)的目的是為用戶提供易于使用、方便高效的操作環(huán)境。例如，在多道程序系統(tǒng)中，物理2PU可以只有一個(gè)，每次也僅能執(zhí)行一道程序，但通過多道程序和分時(shí)使用CPU技術(shù)，宏觀上有多個(gè)程序在執(zhí)行，就好像有多個(gè)CPU在為各道程序工作一樣，物理上的一個(gè)CPU變成了邏輯上的多個(gè)CPU。Spooling技術(shù)可把物理上的一臺獨(dú)占設(shè)備變成邏輯上的多臺虛擬設(shè)備；窗口技術(shù)可把一個(gè)物理屏幕變成邏輯上的多個(gè)虛擬屏幕；通過時(shí)分或頻分多路復(fù)用技術(shù)可以把一個(gè)物理信道變成多個(gè)邏輯信道；IBM的VM技術(shù)把物理上的一臺計(jì)算機(jī)變成邏輯上的多當(dāng)進(jìn)程對信號量S執(zhí)行P、V操作時(shí)，S的值發(fā)生變化，當(dāng)S>0、S=0、和SvO時(shí)，其物理意義是什么？(注：P、V操作有時(shí)又稱為wait，signal)答：P操作相當(dāng)于申請一個(gè)資源，得不到阻塞；V操作相當(dāng)于歸還一個(gè)資源，如有等待該資源的進(jìn)程，則喚醒。S>0時(shí)S表示可使用的資源數(shù)或表示可使用資源的進(jìn)程數(shù)；S=0時(shí)S表示無資源可供使用或表示不允許進(jìn)程再進(jìn)入臨界區(qū)；SvO時(shí)S表示等待使用資源的進(jìn)程個(gè)數(shù)或表示等待進(jìn)入臨界區(qū)的進(jìn)程個(gè)數(shù)。作業(yè)調(diào)度和進(jìn)程調(diào)度各自的主要功能是什么？答：作業(yè)調(diào)度的主要功能是：記錄系統(tǒng)中各個(gè)作業(yè)的情況；按照某種調(diào)度算法從后備作業(yè)隊(duì)列中挑選作業(yè)；為選中的作業(yè)分配內(nèi)存和外設(shè)等資源；為選中的作業(yè)建立相應(yīng)的進(jìn)程；作業(yè)結(jié)束后進(jìn)行善后處理工作。進(jìn)程調(diào)度的主要功能是：保存當(dāng)前運(yùn)行進(jìn)程的現(xiàn)場；從就緒隊(duì)列中挑選一個(gè)合適進(jìn)程；為選中的進(jìn)程恢復(fù)現(xiàn)場。5?有三個(gè)用戶進(jìn)程A、B和C,在運(yùn)行過程中都要使用系統(tǒng)中的一臺打印機(jī)輸出計(jì)算結(jié)果。⑴試說明A、B、C進(jìn)程之間存在什么樣的制約關(guān)系？(2)為保證這三個(gè)進(jìn)程能正確地打印出各自的結(jié)果，請用信號量和P、V操作寫出各自的有關(guān)申請、使用打印機(jī)的代碼。要求給出信號量的含義和初值。答：(1)A、B、C三個(gè)進(jìn)程之間存在互斥的制約關(guān)系。因?yàn)榇蛴C(jī)屬于臨界資源，必須一個(gè)進(jìn)程使用完之后另一個(gè)進(jìn)程才能使用。(2)mutex:用于互斥的信號量，初值為1。各進(jìn)程的代碼如下：進(jìn)程A進(jìn)程B進(jìn)程CP(mutex)P(mutex)P(mutex)申請打印機(jī)申請打印機(jī)申請打印機(jī)使用打印機(jī)使用打印機(jī)使用打印機(jī)V(mutex)V(mutex)V(mutex)6?設(shè)有一臺計(jì)算機(jī)，有兩條I/O通道，分別接一臺卡片輸入機(jī)和一臺打印機(jī)。卡片機(jī)把一疊卡片逐一輸入到緩沖區(qū)B1中，加工處理后再搬到緩沖區(qū)B2中，并在打印機(jī)上打印結(jié)果(假定緩沖區(qū)僅能容納一張卡片信息)。問：系統(tǒng)要設(shè)幾個(gè)進(jìn)程來完成這個(gè)任務(wù)？各自的工作是什么？這些進(jìn)程間有什么樣的相互制約關(guān)系？用P、V操作寫出這些進(jìn)程的同步算法。分析我們畫一個(gè)草圖來幫助我們理解這道題：輸處輸從圖中可以看出，從“卡片機(jī)”到“打印機(jī)”共需要3個(gè)操作，即輸入、處理、輸出。這3個(gè)動(dòng)作就是完成任務(wù)的3個(gè)進(jìn)程。下面我們看看這些進(jìn)程之間有什么樣的制約關(guān)系。可以看出，這3個(gè)進(jìn)程之間是同步關(guān)系，合作完成從輸入到輸出的工作任務(wù)。對其中任何一個(gè)進(jìn)程，要處理好與其關(guān)聯(lián)的兩端設(shè)備的協(xié)調(diào)工作。以“輸入進(jìn)程”為例，它與卡片機(jī)和緩沖區(qū)B1關(guān)聯(lián)，將卡片機(jī)的卡片輸入到緩沖區(qū)B1,在不考慮卡片機(jī)的情況下，就要考慮緩沖區(qū)的情況，即是滿還是空，是空緩沖區(qū)，輸入進(jìn)程就可以輸入信息，如果緩沖區(qū)滿，則要等待“處理進(jìn)程”將B1中的信息取走，使之為空，輸入進(jìn)程才能繼續(xù)工作。依此類推，可以找出另外2個(gè)進(jìn)程的制約關(guān)系。一般來說，處理進(jìn)程同步需要2個(gè)信號量，“輸入進(jìn)程”和“處理進(jìn)程”同步，需要2個(gè)信號量，解決緩沖區(qū)B1的協(xié)調(diào)操作問題；而“處理進(jìn)程”和“輸出進(jìn)程”同步，還需要2個(gè)信號量，解決緩沖區(qū)B2的協(xié)調(diào)操作問題。因此，共需要4個(gè)信號量。本題中“處理進(jìn)程”的算法有一些難度，因?yàn)樗枰獏f(xié)調(diào)兩個(gè)緩沖區(qū)的工作，考慮的因素比較多，算法復(fù)雜些。答案系統(tǒng)可設(shè)三個(gè)進(jìn)程來完成這個(gè)任務(wù)：Input進(jìn)程負(fù)責(zé)從卡片輸入機(jī)上讀入卡片信息，輸入到緩沖區(qū)B1中；Process進(jìn)程負(fù)責(zé)從緩沖區(qū)B1中取出信息，進(jìn)行加工處理，之后將結(jié)果送到緩沖區(qū)B2中；Print進(jìn)程負(fù)責(zé)從緩沖區(qū)B2中取出信息，并在打印機(jī)上印出。Input進(jìn)程受Process進(jìn)程影響，B1放滿信息后Input進(jìn)程要等待：等Process進(jìn)程將其中信息全部取走，才能繼續(xù)讀入信息；Process進(jìn)程受Input進(jìn)程和Print進(jìn)程的約束：B1中信息放滿后Process進(jìn)程才可從中取出它們，且B2被取空后，Process進(jìn)程才可將加工結(jié)果送入其中；Print進(jìn)程受Process進(jìn)程的約束：B2中信息放滿后Print進(jìn)程才可從中取出它們，進(jìn)行打印。信號量含義及初值：B1full——緩沖區(qū)B1滿，初值為0;B1empty——緩沖區(qū)B1空，初值為1；B2full——緩沖區(qū)B2滿，初值為0；B2empty——緩沖區(qū)B2空，初值為1；Input：while(1){wait(B1empty);讀卡片中的信息，并將其放入緩沖區(qū)1中;signal(B1full);}Process:while(1){wait(B1full);從緩沖區(qū)1中取走數(shù)據(jù)，存放在臨時(shí)變量tmp中；signal(B1empty);處理tmp中的數(shù)據(jù)，將處理結(jié)果存放在變量result中；wait(B2empty)；將result中的結(jié)果放入緩沖區(qū)2;signal(B2full)；}Print:while(1){wait(B2full)；從緩沖區(qū)2中取走數(shù)據(jù)，存放在臨時(shí)變量tmp中；signal(B2empty)；打印tmp中的數(shù)據(jù)；}注：如果改變緩沖區(qū)的數(shù)量或者改變緩沖區(qū)的大小，題目的答案要做相應(yīng)地變化：假定緩沖區(qū)B1的大小為m，緩沖區(qū)B2的大小為n。則上述問題就演變?yōu)橥交コ鈫栴}了。Bifull緩沖區(qū)B1滿，初值為0;Biempty緩沖區(qū)B1空，初值為m;B2full——緩沖區(qū)B2滿，初值為0;B2empty——緩沖區(qū)B2空，初值為n;mutexi--緩沖區(qū)B1的互斥信號量，初值為1；mutex2--緩沖區(qū)B2的互斥信號量，初值為1；Input：while(1){wait(B1empty);wait(mutex1);讀卡片中的信息，并將其放入緩沖區(qū)1中;signal(mutex1);signal(B1full);}Process:while(1){wait(B1full);wait(mutex1);從緩沖區(qū)1中取走數(shù)據(jù)，存放在臨時(shí)變量tmp中；signal(mutex1);signal(B1empty)；處理tmp中的數(shù)據(jù)，將處理結(jié)果存放在變量result中;wait(B2empty)；wait(mutex2);將result中的結(jié)果放入緩沖區(qū)2;signal(mutex2);signal(B2full);}Print:while(1){wait(B2full);wait(mutex2);從緩沖區(qū)2中取走數(shù)據(jù)，存放在臨時(shí)變量tmp中；signal(mutex2);signal(B2empty);打印tmp中的數(shù)據(jù)；}對于如圖所示的交通圖，駁船在運(yùn)河里單向航行，汽車在公路上也是單向行駛。由于汽車要兩次跨越運(yùn)河。為了讓汽車和駁船能正常地行駛，在運(yùn)河上架設(shè)了兩座吊橋，當(dāng)汽車要跨越運(yùn)河時(shí)，吊橋必須放下；而當(dāng)駁船要航行時(shí)，吊橋必須吊起。試設(shè)計(jì)一種方案，保證汽車和駁船均能正常行駛。

/運(yùn)河路公CZ1IZJIZJ叵樞槨歸出虻/運(yùn)河路公CZ1IZJIZJ叵樞槨歸出虻答：根據(jù)題目告訴我們的條件，可以畫出這個(gè)交通系統(tǒng)如下圖所示的一種通行狀態(tài)。在這種狀態(tài)下，吊橋A吊起，駁船正在通過吊橋A,船頭已抵達(dá)吊橋B。由于吊橋B上正有汽車通行，因此駁船等待吊橋B上的汽車下橋。而公路上的汽車又在等待駁船通過吊橋A,這時(shí)吊橋B上的汽車處于等待吊橋A放下的狀態(tài)。由此可見，此時(shí)駁船和汽車相互等待對方所占用的資源，顯然是發(fā)生了死鎖。用信號量的辦法可以有效地解決這個(gè)交通系統(tǒng)的死鎖問題。這里，首先將駁船和汽車抽象為并發(fā)進(jìn)程，吊橋A、B是并發(fā)進(jìn)程所共享的資源。為吊橋A、B分別設(shè)置一個(gè)信號量，信號量的值為1表示吊橋未被占用；信號量的值為0表示吊橋上正有汽車通行，或吊橋正被吊起、橋下有駁船通過。具體的解決方案有多種，其中最簡單的是當(dāng)并發(fā)進(jìn)程要通過吊橋時(shí)，首先檢測這兩個(gè)信號量是否同時(shí)為1，若是的話，則將這兩個(gè)信號量同時(shí)獲取，通過兩座吊橋，然后將兩個(gè)信號量釋放。如果進(jìn)程檢測到兩個(gè)信號量不同時(shí)為1，則等待，直至它們的值同時(shí)都為1。這個(gè)簡單方法能有效地解決死鎖問題，但并不能保證這個(gè)交通系統(tǒng)具有高的通行效率。對于這個(gè)交通系統(tǒng)，人們實(shí)際上通常采用的調(diào)度方法是：當(dāng)船首接近吊橋A時(shí)鳴笛，這時(shí)要通過吊橋A、但還未上橋的汽車不再上橋，等橋上的汽車下橋后，吊橋A吊起，讓駁船通過。當(dāng)船首接近吊橋B時(shí)，同樣應(yīng)先鳴笛，如吊橋B上沒有汽車，吊橋B吊起，讓駁船通過。對于汽車來說，在接近吊橋B時(shí)，應(yīng)判斷吊橋B是否處于放下狀態(tài)，如果是的話，還應(yīng)進(jìn)一步判斷吊橋A是否是吊起的。如果吊橋A是處在放下狀態(tài)，那么整條公路是通暢的，因此汽車可以上橋。如果此時(shí)吊橋A吊起，則應(yīng)判斷運(yùn)河對岸的公路上是否已經(jīng)排滿了汽車，如果是的話，則汽車不能上橋，原因在于如果汽車上了橋，由于前面的公路上已經(jīng)塞滿了汽車在等待吊橋A放下，因此汽車上了吊橋B后將無法下橋，此時(shí)會發(fā)生死鎖。我們根據(jù)這樣的調(diào)度方法寫出如下程序。/*programBargeAndAutomobile*/intbridge_A_up=0,bridge_A_up=0;//起先吊橋A、B都是放下的semaphoremutex_A=1,mutex_B=1;semaphoreload_num=K;//兩橋之間的公路上最多能容納K輛汽車voidbarge(inti)//駁船的程序{ApproachingBridgeA;//駁船駛近吊橋ABlowingawhistle;//鳴笛P(mutex_A);if(bridge_A_up==0)bridge_A_up=1;//吊橋A吊起ApproachingBridgeB;//駁船駛近吊橋BBlowingawhistle;//鳴笛P(mutex_B);if(bridge_B_up==0)bridge_B_up=1;//吊橋B吊起bargepassingBridgeA;//駁船通過吊橋AV(mutex_A);bargepassingBridgeB;//駁船通過吊橋BV(mutex_B);}voidautomobile(inti)//汽車i的程序{ApproachingBridgeB;//汽車駛近吊橋BP(load_num);P(mutex_B);if(bridge_B_up==1)//若吊橋B吊起bridge_B_up==0;//吊橋B放下GoontobridgeB;//汽車駛上吊橋BPassbridgeB;///汽車駛過吊橋BV(mutex_B);Goahead;P(mutex_A);if(bridge_A_up==1)//若吊橋A吊起bridge_A_up==0;//吊橋A放下GoontobridgeA;//汽車駛上吊橋AV(load_num);PassbridgeA;///汽車駛過吊橋AV(mutex_A);}voidmain(){parbegin(barge(1),barge(2),?,automobile(1),automobile(2),?);}下表給出作業(yè)l，2，3的提交時(shí)間和運(yùn)行時(shí)間。采用先來先服務(wù)調(diào)度算法和短作業(yè)優(yōu)先調(diào)度算法，試問作業(yè)調(diào)度次序和平均周轉(zhuǎn)時(shí)間各為多少？（時(shí)間單位小時(shí)，以十進(jìn)制進(jìn)行計(jì)算。）作業(yè)號提交時(shí)間運(yùn)行時(shí)間10.08.020.44.031.01.0分析解此題關(guān)鍵是要清楚系統(tǒng)中各道作業(yè)隨時(shí)間的推進(jìn)情況。我們用一個(gè)作業(yè)執(zhí)行時(shí)間圖來表示作業(yè)的執(zhí)行情況，幫助我們理解此題。采用先來先服務(wù)調(diào)度策略，其作業(yè)執(zhí)行時(shí)間圖如下：作業(yè)11作業(yè)3作業(yè)2f作業(yè)1二時(shí)間00.41.08.012.013.0時(shí)間作業(yè)提交時(shí)間各作業(yè)陸續(xù)完成時(shí)間采用短作業(yè)優(yōu)先調(diào)度策略，其作業(yè)執(zhí)行時(shí)間圖如下:作業(yè)作業(yè)3作業(yè)2章作業(yè)1二00.41.08.09.013.0時(shí)間作業(yè)提交時(shí)間各作業(yè)陸續(xù)完成時(shí)間另外，作業(yè)i的周轉(zhuǎn)時(shí)間片=作業(yè)完成時(shí)間一作業(yè)提交時(shí)間系統(tǒng)中n個(gè)作業(yè)的平均周轉(zhuǎn)時(shí)間T=QT）x1，其中Ti為作業(yè)i的周轉(zhuǎn)時(shí)ini=1間。解：采用先來先服務(wù)調(diào)度策略，則調(diào)度次序?yàn)閘、2、3。作業(yè)號提交時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間10.08.00.08.08.020.44.08.012.011.631.01.012.013.012.0平均周轉(zhuǎn)時(shí)間T=（8＋11.6＋12）73=10.53采用短作業(yè)優(yōu)先調(diào)度策略，則調(diào)度次序?yàn)閘、3、2。作業(yè)號提交時(shí)間運(yùn)行時(shí)間開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間10.08.00.08.08.031.01.08.09.08.020.44.09.013.012.6平均周轉(zhuǎn)時(shí)間T=(8+8+12.6)13=9.53今有三個(gè)批處理作業(yè)。第一個(gè)作業(yè)10:00到達(dá)，需要執(zhí)行2小時(shí)；第二個(gè)作業(yè)在10:10到達(dá)，需要執(zhí)行1小時(shí)；第三個(gè)作業(yè)在10:25到達(dá)，需要執(zhí)行25分鐘。分別采取如下兩種作業(yè)調(diào)度算法：調(diào)度算法1：作業(yè)號到達(dá)時(shí)間開始執(zhí)行時(shí)間執(zhí)行結(jié)束時(shí)間110:0010:0012:00210:1012:0013:00310:2513:0013:25調(diào)度算法2：作業(yè)號到達(dá)時(shí)間開始執(zhí)行時(shí)間執(zhí)行結(jié)束時(shí)間110:0011:5013:50210:1010:5011:50310:2510:2510;50計(jì)算各調(diào)度算法下的作業(yè)平均周轉(zhuǎn)時(shí)間。調(diào)度算法1是什么作業(yè)調(diào)度算法？分析作業(yè)的周轉(zhuǎn)時(shí)間=作業(yè)完成時(shí)間－作業(yè)提交時(shí)間。以調(diào)度算法1的作業(yè)2為例，其周轉(zhuǎn)時(shí)間=作業(yè)完成時(shí)間13:00－作業(yè)提交時(shí)間10:10，得到結(jié)果為2小時(shí)50分鐘，轉(zhuǎn)換為小時(shí)為2.83小時(shí)。轉(zhuǎn)換的目的是為了方便計(jì)算平均周轉(zhuǎn)時(shí)間。解：(1)采用調(diào)度算法1時(shí)：作業(yè)1的周轉(zhuǎn)時(shí)間為2小時(shí)；作業(yè)2的周轉(zhuǎn)時(shí)間為2.83小時(shí)；作業(yè)3的周轉(zhuǎn)時(shí)間為3小時(shí)；平均周轉(zhuǎn)時(shí)間為：(2+2.83+3)／3=2.61小時(shí)。采用調(diào)度算法2時(shí)：作業(yè)1的周轉(zhuǎn)時(shí)間為3.83小時(shí)；作業(yè)2的周轉(zhuǎn)時(shí)間為1.67小時(shí)；作業(yè)3的周轉(zhuǎn)時(shí)間為0.42小時(shí)；平均周轉(zhuǎn)時(shí)間為：(3.83+1.67+0.42)/3=1.97小時(shí)。(2)調(diào)度算法1是按照作業(yè)到達(dá)的先后次序執(zhí)行的，所以它是先來先服務(wù)調(diào)度算法?？紤]一個(gè)由8個(gè)頁面，每頁有1024個(gè)字節(jié)組成的邏輯空間，把它裝入到有32個(gè)物理塊的存儲器中，問：(1)邏輯地址需要多少二進(jìn)制位表示？(2)物理地址需要多少二進(jìn)制位表示？解因?yàn)轫撁鏀?shù)為8=23，故需要3位二進(jìn)制數(shù)表示。每頁有1024個(gè)字節(jié)，1024=210，于是頁內(nèi)地址需要10位二進(jìn)制數(shù)表示。32個(gè)物理塊，需要5位二進(jìn)制數(shù)表示(32=25)。頁的邏輯地址由頁號和頁內(nèi)地址組成，所以需要3+10=13位二進(jìn)制數(shù)表示。頁的物理地址由塊號和頁內(nèi)地址的拼接，所以需要5+10=15位二進(jìn)制數(shù)表示。分析在分頁存儲管理中，邏輯地址結(jié)構(gòu)如下圖所示。頁號p頁內(nèi)地址d它由兩個(gè)部分組成：前一部分表示該地址所在頁面的頁號p;后一部分表示頁內(nèi)地址(頁內(nèi)位移)d。頁號的地址位數(shù)決定了頁的多少，假設(shè)頁號有20位，則地址空間中最多可容納的頁面數(shù)為220，即1MB個(gè)頁面。頁內(nèi)地址位數(shù)確定了每頁的大小，若頁內(nèi)地址為12位，則每頁大小為212，即2KB。同理，物理地址中塊號的地址位數(shù)決定了塊的多少，由于頁式存儲管理內(nèi)存空間塊的大小與頁面大小相同，所以物理地址中塊內(nèi)地址與邏輯地址中的頁內(nèi)地址位數(shù)相同。若在一分頁存儲管理系統(tǒng)中，某作業(yè)的頁表如下所示。已知頁面大小為1024字節(jié)，試將邏輯地址1011，2148，4000，5012轉(zhuǎn)化為相應(yīng)的物理地址。頁號塊號02132136解本題中，為了描述方便，設(shè)頁號為P，頁內(nèi)位移為d,貝U：對于邏輯地址1011,p=int(1011/1024)=0,d=1011mod1024=1011。查頁表第0頁在第2塊，所以物理地址為1024x2+1011=3059。對于邏輯地址2148，p=int(2148/1024)=2，d=2148mod1024=100。查頁表第2頁在第1塊，所以物理地址為1024+100=1124。對于邏輯地址4000，p=int(4000/1024)=3，d=4000mod1024=928。查頁表第3頁在第6塊，所以物理地址為1024x6+928=7072。對于邏輯地址5012，p=int(5012/1024)=4，d=5012mod1024=916。因頁號超過頁表長度，該邏輯地址非法。12．考慮下述頁面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6當(dāng)內(nèi)存塊數(shù)量分別為3時(shí)，試問FIFO、LRU、OPT這三種置換算法的缺頁次數(shù)各是多少？解使用FIFO算法，缺頁次數(shù)是16;使用LRU算法，缺頁次數(shù)是15;使用OPT算法，缺頁次數(shù)是11。分析所有內(nèi)存塊最初都是空的，所以第一次用到的頁面都產(chǎn)生一次缺頁。當(dāng)內(nèi)存塊數(shù)量為3時(shí)：FIFO1,234,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6塊11114446663332226塊2222111222777111塊333355511166633缺頁xxxxxxxxxxxxxxxx因此，F(xiàn)IFO算法發(fā)生缺頁中斷的次數(shù)為16。在FIFO算法中，先進(jìn)入內(nèi)存的頁面被先換出。例如，當(dāng)頁6要調(diào)入時(shí)，內(nèi)存的狀態(tài)為4、1、5,考查頁6之前調(diào)入的頁面，分別為5、1、2、4、…，可見4為最先進(jìn)入內(nèi)存的，本次應(yīng)換出，然后把頁6調(diào)入內(nèi)存。LRU1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3，6

塊1塊2塊3缺頁1114塊1塊2塊3缺頁111422233XXXX452211XX551666122XXX132X773326XX223361XX236X因此，LRU算法發(fā)生缺頁中斷的次數(shù)為15。在LRU算法中，最近最少使用