【正文】 若快表的命中率是85%，則有效存取時(shí)間為多少？若快表命中率為50%，那么有效存取時(shí)間為多少？解答：（1）分頁需要訪問2次，第一次訪問頁表，第二次執(zhí)行訪內(nèi)操作(2’)；分段需要訪問2次，第一次訪問段表，第二次執(zhí)行訪內(nèi)操作；段頁式需要訪問3次，第一次訪問段表，第二次訪問頁表，第三次執(zhí)行訪內(nèi)操作(2’)。這種現(xiàn)象稱為Belady現(xiàn)象。若在主存中為每一作業(yè)進(jìn)程開辟3頁，對(duì)于題中的頁面訪問過程，其頁面調(diào)度過程如下所示4 3 2 1 4 3 5 4 3 2 1 5頁面1 4 4 4 1 1 1 5 5 5 5 5 5頁面2 3 3 3 4 4 4 4 4 2 2 2頁面3 2 2 2 3 3 3 3 3 1 1缺頁中斷 F F F F F F F F F (3’)1） 該作業(yè)運(yùn)行中總共出現(xiàn)9次缺頁(1’)2） 在主存擁有4頁，又將產(chǎn)生10次缺頁(1’)。某作業(yè)運(yùn)行中使用的操作數(shù)所在的頁號(hào)依次為：4，3，2，1，4，3，5，4，3，2，1，5。(3’)6有一虛擬存儲(chǔ)系統(tǒng)，采用先進(jìn)先出（FIFO）的頁面淘汰算法。1MB的空間可劃分為512個(gè)2KB的塊，每個(gè)塊用9個(gè)二進(jìn)制位表示(2’)。故描述邏輯空間需要16位(2’)。1） 寫出邏輯地址的格式2） 若不考慮訪問權(quán)限位，進(jìn)程的頁表有多少項(xiàng)？每項(xiàng)至少多少位？3） 如果物理空間減少一半，頁表結(jié)構(gòu)應(yīng)作怎樣的改？答：1）邏輯空間32頁，占5個(gè)二進(jìn)制位。(3’)因此地址為8762的物理地址為14*512+58=7226。(2’)虛地址223CH轉(zhuǎn)換成十進(jìn)制數(shù)為8762，由8762/512可得，其頁號(hào)為17，頁內(nèi)地址為58。查頁表可知，其主存塊號(hào)為8。假定某時(shí)刻用戶頁表中虛頁號(hào)和物理塊號(hào)對(duì)照表如下：虛頁號(hào) 0 2 5 17 20物理塊號(hào) 5 20 8 14 36求虛地址0A3CH、223CH分別對(duì)應(yīng)的物理地址。(3’)系統(tǒng)為運(yùn)行進(jìn)程分配4個(gè)主存塊，采用LRU算法，因此可以列表給出進(jìn)程的缺頁情況： 0 2 1 7 6 0 8 3 4 3 2 0 1 2 0 2 1 7 6 0 8 3 4 3 2 0 1 2 0 2 1 7 6 0 8 3 4 3 2 0 1 0 2 1 7 6 0 8 8 4 3 2 0 0 2 1 7 6 0 0 8 4 3 3 F F F F F F F F F S F F F S (5’)由上表可見，被淘汰的頁依次為0，2，1，7，6，0，8，4。答：首先將邏輯地址變換成頁號(hào)。一個(gè)程序大小為1200字，可能的訪問序列如下： 10，205，110，735，603，50，815，314，432，320，225，80，130，270系統(tǒng)采用LRU算法。如果采用LRU算法，缺頁率是多少？如果采用最優(yōu)淘汰算法，其缺頁率又是多少？解: 該序列的頁面走向?yàn)椋?、0、3。綜合題1考慮下面頁面走向：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í)，試問LRU,FIFO,OPT三種置換算法的缺頁次數(shù)各是多少？（注意，所有內(nèi)存最初都是空的，凡第1次用到的頁面都產(chǎn)生一次缺頁）答：LRU1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 61 1 1 4 4 4 5 5 5 1 1 1 7 7 7 2 2 2 2 2 2 2 2 2 1 1 1 2 2 2 2 2 6 6 6 1 1 1 6 3 3 3 3 3 6 6 6 6 3 3 3 3 3 3 3 3 3 (2’)FIFO1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 61 1 1 4 4 4 4 6 6 6 6 3 3 3 3 2 2 2 2 6 2 2 2 2 1 1 1 2 2 2 2 7 7 7 7 1 1 1 1 3 3 3 3 5 5 5 1 1 1 1 6 6 6 6 6 3 3 (2’)OPT1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 61 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 7 7 7 2 2 2 2 2 3 4 4 4 5 6 6 6 6 6 6 6 6 6 1 1 1 6 (2’)內(nèi)存塊數(shù) 置換算法 FIFO LRU OPT3 16 15 11 (3’)2考慮下面存儲(chǔ)訪問序列，該程序大小為460字：10，11，104，170，73，309，185，245，246，434，458，364 設(shè)頁面大小是100字，請(qǐng)給出該訪問序列的頁面走向。 一旦檢測(cè)到抖動(dòng)，操作系統(tǒng)要選擇一個(gè)進(jìn)程讓它掛起，把它的頁面寫出去，把它占用的內(nèi)存塊分給別的進(jìn)程。若有足夠多的額外塊，就可以裝入并啟動(dòng)另外的進(jìn)程。整個(gè)系統(tǒng)的頁面替換非常頻繁，以致大部分機(jī)器時(shí)間都用在來回進(jìn)行的頁面調(diào)度上，只有一小部分時(shí)間用于進(jìn)程的實(shí)際運(yùn)算方面。 利用工作集模型可防止抖動(dòng)，也可以進(jìn)行頁面置換。 然而，頁是信息的物理單位，在一頁中可能存在邏輯上互相獨(dú)立的兩組或多組信息，各有不同的使用方式和存取權(quán)限，因而，對(duì)分頁難以進(jìn)行共享和保護(hù)。這樣，任何共享的信息就可以單獨(dú)成為一段。 請(qǐng)求分頁技術(shù)是在簡(jiǎn)單分頁技術(shù)基礎(chǔ)上發(fā)展起來的，兩者根本區(qū)別是：請(qǐng)求分頁提供虛擬存儲(chǔ)器，而簡(jiǎn)單分頁系統(tǒng)并未提供虛擬存儲(chǔ)器。9請(qǐng)求分頁技術(shù)的基本思想是什么？它與簡(jiǎn)單分頁技術(shù)之間有何根本區(qū)別？答：請(qǐng)求分頁技術(shù)的基本思想是：當(dāng)一個(gè)進(jìn)程的部分頁面在內(nèi)存時(shí)就可調(diào)度它運(yùn)行；在運(yùn)行過程中若用到的頁面尚未在內(nèi)存，則把它們動(dòng)態(tài)換入內(nèi)存。這樣，物理地址寄存器中的內(nèi)容就是由二者拼接成的實(shí)際訪問內(nèi)存地址，從而完成了從邏輯地址到物理地址的轉(zhuǎn)換。 邏輯地址轉(zhuǎn)換成物理地址的過程是:用頁號(hào)P去檢索頁表，從頁表中得到該頁的物理塊號(hào)，把它裝入物理地址寄存器中。7在分頁系統(tǒng)中頁面大小由誰決定？頁表的作用是什么？如何將邏輯地址轉(zhuǎn)換成物理地址？答:在分頁系統(tǒng)中頁面大小由硬件決定。 ③分頁的作業(yè)地址空間是一維的，分段的作業(yè)的地址空間是二維的。 分段和分頁都是非連續(xù)的存儲(chǔ)管理方法， 分頁和分段的主要區(qū)別有： ①頁是信息的物理單位，段是信息的邏輯單位。6什么是分頁？什么是分段？二者有何主要區(qū)別？答：分頁是由系統(tǒng)將一個(gè)進(jìn)程的邏輯地址空間劃分成若干大小相等的部分，每一部分稱做一個(gè)頁面。 5引入虛擬存儲(chǔ)器后，除了獲得主存“擴(kuò)充”的好處，還有什么好處？答：引入虛存后，程序的地址空間都是虛地址的集合，只有在程序運(yùn)行中通過硬件地址轉(zhuǎn)換機(jī)構(gòu)和操作系統(tǒng)的相應(yīng)軟件，才能將虛地址變換成主存的實(shí)地址，這將為主存的分配帶來更大的靈活性。離散分配——不必占用連續(xù)的內(nèi)存空間,而是”見縫插針”。 虛擬存儲(chǔ)器的基本特征是:虛擬擴(kuò)充——不是物理上,而是邏輯上擴(kuò)充了內(nèi)存容量。當(dāng)執(zhí)行指令時(shí)，如果地址合法，則將相對(duì)地址與基址寄存器中的地址相加，所得結(jié)果就是真正要訪問的內(nèi)存地址；如果地址越界，則發(fā)出相應(yīng)中斷，進(jìn)行處理 。3動(dòng)態(tài)重定位分區(qū)管理方式中如何實(shí)現(xiàn)虛實(shí)地址映射？答：作業(yè)裝入內(nèi)存時(shí)，是將該用戶的程序和數(shù)據(jù)原封不動(dòng)地裝入到內(nèi)存中 。內(nèi)部碎片出現(xiàn)在一個(gè)分區(qū)的內(nèi)部（即被浪費(fèi)的空間），如固定分區(qū)法會(huì)產(chǎn)生內(nèi)部碎片 。 2說明內(nèi)部碎片和外部碎片的不同之處答：內(nèi)存中出現(xiàn)的其容量太小、無法被利用的小分區(qū)稱作碎片 。每個(gè)分區(qū)只可裝入一道作業(yè)。簡(jiǎn)答題1解釋固定分區(qū)法和動(dòng)態(tài)分區(qū)法的基本原理。23實(shí)存實(shí)存是指計(jì)算機(jī)配置的物理存儲(chǔ)器，它直接向cpu提供程序和數(shù)據(jù)。而把外存中的某個(gè)（或某些）作業(yè)移到相應(yīng)的主存區(qū)，并使其投入運(yùn)行。這樣的高速緩沖存儲(chǔ)器就是快表。這樣使計(jì)算機(jī)的處理速度降低約一倍。20快表又叫“聯(lián)想存儲(chǔ)器”。19程序局部性原理在相對(duì)短的一段時(shí)間內(nèi)，進(jìn)程集中在一組子程序或循環(huán)中之行，導(dǎo)致所有的存儲(chǔ)器訪問局限于進(jìn)程地址空間的一個(gè)固定子集。18工作集工作集是一個(gè)進(jìn)程在某一小段時(shí)間內(nèi)訪問頁面的集合。由于所有這些頁面都正在使用，所以剛被淘汰出去的頁很快又被訪問，因而要把它重新調(diào)入。即如果一個(gè)進(jìn)程沒有一定數(shù)量的內(nèi)存塊，它很快就發(fā)生缺頁。16虛擬存儲(chǔ)器虛擬存儲(chǔ)器是用戶能作為可編程內(nèi)存對(duì)待的虛擬存儲(chǔ)空間，在這種計(jì)算機(jī)系統(tǒng)中實(shí)現(xiàn)了用戶邏輯存儲(chǔ)器與物理存儲(chǔ)器的分離，它是操作系統(tǒng)給用戶提供的一個(gè)比真實(shí)內(nèi)存空間大得多的地址空間。14動(dòng)態(tài)分區(qū)法各個(gè)分區(qū)是在相應(yīng)作業(yè)要求進(jìn)入內(nèi)存時(shí)才建立的，使其大小恰好適應(yīng)作業(yè)的大小。12可重定位地址當(dāng)含有它的程序被重定位時(shí)，將隨之被調(diào)整的一種地址。10碎片在分區(qū)法中，內(nèi)存出現(xiàn)許多容量太小、無法被利用的小分區(qū)稱作“碎片”。如固定分區(qū)法會(huì)產(chǎn)生內(nèi)部碎片。7動(dòng)態(tài)重定位在程序執(zhí)行期間，每次訪問內(nèi)存之前進(jìn)行的重定位。5重定位把邏輯地址轉(zhuǎn)變?yōu)閮?nèi)存物理地址的過程叫做重定位。3邏輯地址空間由程序中邏輯地址組成的地址范圍叫做邏輯地址空間。 作業(yè)名 到達(dá)時(shí)間 估計(jì)運(yùn)行時(shí)間/min 優(yōu)先數(shù) 1 8:00 40 4 2 8:20 30 2 3 8:30 50 3 4 8:50 20 5(1) 列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及完成時(shí)間(2) 計(jì)算作業(yè)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間解答：(1)作業(yè)進(jìn)入內(nèi)存時(shí)間與結(jié)束時(shí)間如下所示：(`4’=1’*4) 作業(yè)名 進(jìn)入內(nèi)存時(shí)間 結(jié)束時(shí)間 1 8:00 9:10 2 8:20 8:50 3 9:10 10:00 4 8:50 10:20 (2)各作業(yè)的周轉(zhuǎn)時(shí)間為： (`4’=1’*4)作業(yè)A：9:10 – 8:00 = 70 min作業(yè)B：8:50 – 8:20 = 30 min作業(yè)C：10:00 – 8:30 = 90 min作業(yè)D：10:20 – 8:50 = 90 min 作業(yè)的平均周轉(zhuǎn)時(shí)間為：(70+30+90+90)/4=70 min (1’)作業(yè)的平均帶權(quán)周轉(zhuǎn)時(shí)間為：(70/40+30/30+90/50+90/20)/4= min (1’)名詞解釋1物理地址內(nèi)存中各存儲(chǔ)單元的地址由統(tǒng)一的基地址順序編址，這種地址稱為物理地址。 當(dāng)x9，作業(yè)的運(yùn)行順序應(yīng)為C(3),D(5),B(6),A(9),E(x)4有一個(gè)具有如下作業(yè)流的批處理處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先，進(jìn)程調(diào)度采用基于優(yōu)先數(shù)的搶先式調(diào)度算法。 當(dāng)5=x=6時(shí)，作業(yè)的運(yùn)行順序應(yīng)為C(3),D(5),E(x),B(6),A(9)。 (5’) 下面對(duì)x的取值進(jìn)行討論：(`5’=1’*5) 當(dāng)0x=3時(shí)，作業(yè)的運(yùn)行順序應(yīng)為E(x),C(3),D(5),B(6),A(9)。解：①D C B A8:00 8:20 8:30 8:50 9:10 10:00 10:20(4’)② (`6’=1’*6)JOB ts tsr te TA 8:00 8:00 9:10 70B 8:20 8:20 8:50 30C 8:30 9:10 10:00 90D 8:50 8:50 10:20 90 70 3有A、B、C、D、E，共5個(gè)待運(yùn)行作業(yè)，各自估計(jì)的運(yùn)行時(shí)間為9，6，3，5，x。要求：①列出所有作業(yè)進(jìn)入內(nèi)存的時(shí)間及結(jié)束時(shí)間。表49 作業(yè)列表作業(yè)名 到達(dá)時(shí)間 預(yù)估計(jì)時(shí)間（分鐘） 優(yōu)先數(shù)A 8:00 40 10B 8:20 30 5C 8:30 50 8D 8:50 20 12其中給出的作業(yè)優(yōu)先數(shù)即為相應(yīng)進(jìn)程的優(yōu)先數(shù)。 ①用一個(gè)執(zhí)行時(shí)間圖描述使用非搶占式優(yōu)先級(jí)算法時(shí)各自執(zhí)行這些作業(yè)的情況： ②對(duì)于該算法，各個(gè)作業(yè)的周轉(zhuǎn)時(shí)間是多少?平均周轉(zhuǎn)時(shí)間是多少？③對(duì)于該算法，各個(gè)作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間是多少？平均帶權(quán)周轉(zhuǎn)時(shí)間是多少？解：⑴ 非搶占式優(yōu)先級(jí) J1 J4 J3 J5 J20 10 11 13 18 19(3’) ⑵和⑶ 非搶占式優(yōu)先級(jí) (`7’=1’*7)JOB ts tr te T WJ1 0 10 10 10 1J2 1 1 19 18 18J3 2 2 13 11 J4 3 1 11 8 J5 4 5 18 14 2在一個(gè)有兩道作業(yè)的批處理系統(tǒng)中，作業(yè)調(diào)度采用短作業(yè)優(yōu)先級(jí)調(diào)度算法，進(jìn)程調(diào)度采用搶占式優(yōu)先級(jí)調(diào)度算法。 綜合題1假定在單CPU條件下要執(zhí)行的作業(yè)如下表所示。當(dāng)運(yùn)行進(jìn)程要等待某一事件時(shí)，就讓出cpu，進(jìn)入相應(yīng)的阻塞隊(duì)列，并進(jìn)行進(jìn)程調(diào)度。 作業(yè)調(diào)度從外存的后背隊(duì)列中選擇一批作業(yè)調(diào)入內(nèi)存，為它們創(chuàng)建進(jìn)程，這些進(jìn)程被送入就緒隊(duì)列。 5作業(yè)調(diào)度與進(jìn)程調(diào)度之間有什么差別？二者間如何協(xié)調(diào)工作？答：作業(yè)調(diào)度與進(jìn)程調(diào)度之間的差別主要是：作業(yè)調(diào)度是宏觀調(diào)度，它所選擇的作業(yè)只是具有獲得處理機(jī)的資格，但尚未占有處理機(jī)，不能立即在其上實(shí)際運(yùn)行；而進(jìn)程調(diào)度是