吉林大學(xué)操作系統(tǒng)課件作業(yè)解析2

1、#1n某請(qǐng)求分頁(yè)管理系統(tǒng)中，頁(yè)表保存在內(nèi)存器中。若有一個(gè)可用的空頁(yè)或被置換的頁(yè)未被修改，則它處理一個(gè)缺頁(yè)中斷需要8ms；若被置換的頁(yè)已被修改，則處理一缺頁(yè)中斷因 增加寫(xiě)回外存的時(shí)間而需要20ms，一次內(nèi)存的存取時(shí)間為1ns。假設(shè)70%被置換的頁(yè)被修改過(guò)，為保證有效訪(fǎng)問(wèn)時(shí)間不超過(guò)12ns，可接受的最大缺頁(yè)率是多少？n解：設(shè)缺頁(yè)率為f,內(nèi)存訪(fǎng)問(wèn)時(shí)間為t 缺頁(yè)中斷處理的平均時(shí)間t1=8(1-70%)+2070%=16.4ms 有效訪(fǎng)問(wèn)時(shí)間=t+f(t1+t)+(1-f)t12 所以：f1/1640000#2n已知一個(gè)采用LRU置換算法的請(qǐng)求分頁(yè)存儲(chǔ)管理系統(tǒng)中，頁(yè)面大小為4KB，內(nèi)存訪(fǎng)問(wèn)速度為100n

2、s/次，快表訪(fǎng)問(wèn)速度為20ns/次，缺頁(yè)中斷處理時(shí)間是25ms/次。今有一長(zhǎng)度為30KB的進(jìn)程P進(jìn)入系統(tǒng)，分配給P的存儲(chǔ)塊有3塊，進(jìn)程的所有頁(yè)面都是在該進(jìn)程運(yùn)行中動(dòng)態(tài)裝入。若訪(fǎng)問(wèn)快表的命中率為20%，對(duì)應(yīng)于下述頁(yè)面訪(fǎng)問(wèn)序列： 7、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、7、0、1 計(jì)算20個(gè)頁(yè)面的平均有效訪(fǎng)問(wèn)時(shí)間是多少？n解：訪(fǎng)問(wèn)這20個(gè)頁(yè)面時(shí)缺頁(yè)次數(shù)為12次，缺頁(yè)率為f=12/20=60%， a為快表命中率，t為內(nèi)存訪(fǎng)問(wèn)時(shí)間，t1為中斷處理時(shí)間， 為快表訪(fǎng)問(wèn)時(shí)間 EAT=(+t) a+( +t)0.4+(+t+t1) 0.6+t (1- a)pipe(fd)int f

3、d2;1. 分配一個(gè)內(nèi)存分配一個(gè)內(nèi)存inode，(i_count=2);2. 分配分配2個(gè)個(gè)file表項(xiàng)表項(xiàng)(f_flag分別為分別為Pipe R和和Pipe W，讀，讀/寫(xiě)指針寫(xiě)指針 f_offset為為0）3. 分配分配2個(gè)個(gè)u_ofile表項(xiàng)表項(xiàng), 分別指向分別指向2個(gè)個(gè)file表項(xiàng)；表項(xiàng)；4. 返回返回2個(gè)文件描述符個(gè)文件描述符fd0,fd1, 分別為分別為u_ofile中的中的2個(gè)入口。個(gè)入口。UNIX：創(chuàng)建管道文件：創(chuàng)建管道文件 i_addr i_count (2) f_flag (R pipe)f_offset (0)f_inodepf_count (1)f_flag (W pi

4、pe)f_offset (0)f_inodepf_count (1)內(nèi)存內(nèi)存inode表表內(nèi)存內(nèi)存file表表fd0fd1u_ofile表表進(jìn)程執(zhí)行進(jìn)程執(zhí)行pipe(fd)之后之后 i_addr i_count (2) f_flag (R pipe)f_offset (0)f_inodepf_count (2)f_flag (W pipe)f_offset (0)f_inodepf_count (2)內(nèi)存內(nèi)存inode表表內(nèi)存內(nèi)存file表表fd0fd1u_ofile表表fork創(chuàng)建子進(jìn)程創(chuàng)建子進(jìn)程1之后之后fd0fd1父進(jìn)程父進(jìn)程:子進(jìn)程子進(jìn)程1: i_addr i_count (2) f_

5、flag (R pipe)f_offset (0)f_inodepf_count (3)f_flag (W pipe)f_offset (0)f_inodepf_count (3)內(nèi)存內(nèi)存inode表表內(nèi)存內(nèi)存file表表fd0fd1u_ofile表表fork創(chuàng)建子進(jìn)程創(chuàng)建子進(jìn)程2之后之后fd0fd1父進(jìn)程父進(jìn)程:子進(jìn)程子進(jìn)程1:子進(jìn)程子進(jìn)程2:fd0fd1 i_addr i_count (2) f_flag (R pipe)f_offset (0)f_inodepf_count (2)f_flag (W pipe)f_offset (0)f_inodepf_count (2)內(nèi)存內(nèi)存inod

6、e表表內(nèi)存內(nèi)存file表表fd0fd1u_ofile表表父進(jìn)程父進(jìn)程close(fd0),close(fd1)fd0fd1父進(jìn)程父進(jìn)程:子進(jìn)程子進(jìn)程1:子進(jìn)程子進(jìn)程2:fd0fd1 i_addr i_count (2) f_flag (R pipe)f_offset (0)f_inodepf_count (2)f_flag (W pipe)f_offset (0)f_inodepf_count (1)內(nèi)存內(nèi)存inode表表內(nèi)存內(nèi)存file表表fd0fd1u_ofile表表子進(jìn)程子進(jìn)程1(讀者讀者) : close(fd1)fd0fd1父進(jìn)程父進(jìn)程:子進(jìn)程子進(jìn)程1:子進(jìn)程子進(jìn)程2:fd0fd1

7、i_addr i_count (2) f_flag (R pipe)f_offset (0)f_inodepf_count (1)f_flag (W pipe)f_offset (0)f_inodepf_count (1)內(nèi)存內(nèi)存inode表表內(nèi)存內(nèi)存file表表fd0fd1u_ofile表表子進(jìn)程子進(jìn)程2(寫(xiě)者寫(xiě)者) : close(fd0)fd0fd1父進(jìn)程父進(jìn)程:子進(jìn)程子進(jìn)程1:子進(jìn)程子進(jìn)程2:fd0fd1 i_addr i_count (2) f_flag (R pipe)f_offsetf_inodepf_count (1)f_flag (W pipe)f_offsetf_inode

8、pf_count (1)內(nèi)存內(nèi)存inode表表內(nèi)存內(nèi)存file表表u_ofile表表子進(jìn)程子進(jìn)程2(寫(xiě)寫(xiě)) : write(fd1,buf1,count1)子進(jìn)程子進(jìn)程1(讀讀) : read(fd0,buf0,count0)父進(jìn)程父進(jìn)程:子進(jìn)程子進(jìn)程1:子進(jìn)程子進(jìn)程2:fd0fd1fd0fd1fd0fd1write(fd1,)read(fd0,) 盤(pán)塊盤(pán)塊(有緩沖有緩沖) i_addr i_count (1) f_flag (R pipe)f_offsetf_inodepf_count (1)f_flag (W pipe)f_offsetf_inodepf_count (0)內(nèi)存內(nèi)存inod

9、e表表內(nèi)存內(nèi)存file表表u_ofile表表子進(jìn)程子進(jìn)程2(寫(xiě)完寫(xiě)完) :close(fd1)父進(jìn)程父進(jìn)程:子進(jìn)程子進(jìn)程1:子進(jìn)程子進(jìn)程2:fd0fd1fd0fd1fd0fd1close(fd1)read(fd0,) 盤(pán)塊盤(pán)塊(有緩沖有緩沖) i_addr i_count (0) f_flag (R pipe)f_offsetf_inodepf_count (0)f_flag (W pipe)f_offsetf_inodepf_count (0)內(nèi)存內(nèi)存inode表表內(nèi)存內(nèi)存file表表u_ofile表表子進(jìn)程子進(jìn)程1(讀完讀完) :close(fd0)父進(jìn)程父進(jìn)程:子進(jìn)程子進(jìn)程1:子進(jìn)程子進(jìn)

10、程2:fd0fd1fd0fd1fd0fd1close(fd1)close(fd0)Pipe文件同步與互斥文件同步與互斥npipe讀寫(xiě)同步讀寫(xiě)同步n寫(xiě)滿(mǎn)：寫(xiě)者等待，讀出后喚醒寫(xiě)滿(mǎn)：寫(xiě)者等待，讀出后喚醒n讀空：讀者等待，寫(xiě)入后喚醒讀空：讀者等待，寫(xiě)入后喚醒n讀寫(xiě)關(guān)閉讀寫(xiě)關(guān)閉n所有讀者關(guān)閉所有讀者關(guān)閉(沒(méi)有讀者沒(méi)有讀者)：向管道寫(xiě)入數(shù)據(jù)：向管道寫(xiě)入數(shù)據(jù)沒(méi)有意義，寫(xiě)時(shí)返回錯(cuò)誤信號(hào)沒(méi)有意義，寫(xiě)時(shí)返回錯(cuò)誤信號(hào)n所有寫(xiě)者關(guān)閉所有寫(xiě)者關(guān)閉(沒(méi)有寫(xiě)者沒(méi)有寫(xiě)者)：讀者立即返回：讀者立即返回n讀寫(xiě)互斥讀寫(xiě)互斥ni_flag|ILOCK(保證進(jìn)程互斥使用管道保證進(jìn)程互斥使用管道)管道通訊的局限性管道通訊的局限性n只有

11、相關(guān)進(jìn)程只有相關(guān)進(jìn)程(同一家族進(jìn)程同一家族進(jìn)程)能通訊能通訊n先創(chuàng)建管道先創(chuàng)建管道n再創(chuàng)建子進(jìn)程再創(chuàng)建子進(jìn)程, 子進(jìn)程繼承父進(jìn)程打開(kāi)的文子進(jìn)程繼承父進(jìn)程打開(kāi)的文件件(包括管道文件包括管道文件)n管道是沒(méi)有名字的文件管道是沒(méi)有名字的文件n所有進(jìn)程都關(guān)閉后即被撤銷(xiāo)所有進(jìn)程都關(guān)閉后即被撤銷(xiāo)n設(shè)系統(tǒng)磁盤(pán)只有一個(gè)移動(dòng)磁頭，磁道由外向內(nèi)編號(hào)為：0、1、2、199；磁頭移動(dòng)一個(gè)磁道所需時(shí)間為1毫秒；每個(gè)磁道有 16 個(gè)扇區(qū)；磁盤(pán)轉(zhuǎn)速R=6000r/min. 系統(tǒng)對(duì)磁盤(pán)設(shè)備的I/O請(qǐng)求采用凍結(jié)掃描（Freezing Scan，F(xiàn)SCAN）調(diào)度算法，每個(gè)請(qǐng)求讀/寫(xiě)磁道上的1個(gè)扇區(qū)。假設(shè)磁頭在由外向內(nèi)的移動(dòng)過(guò)程中

12、、從20ms時(shí)刻開(kāi)始，正處理服務(wù)隊(duì)列中最后一個(gè)102磁道的I/O請(qǐng)求，并且在45ms時(shí)刻處理完該I/O請(qǐng)求。設(shè)有磁的I/O請(qǐng)求序列如下表所示：磁道：70, 130, 50, 112, 125, 120, 80, 30, 60, 40, 90, 20, 110到達(dá)時(shí)間：23, 29, 31, 37, 41, 43, 47, 51, 53, 57, 59, 61, 71問(wèn) 題： 寫(xiě)出給定I/O請(qǐng)求序列的調(diào)度序列，并計(jì)算磁頭的移動(dòng)量； 對(duì)給定I/O請(qǐng)求序列，計(jì)算：總尋道時(shí)間（啟動(dòng)時(shí)間忽略）、總旋轉(zhuǎn)延遲時(shí)間、總傳輸時(shí)間和總訪(fǎng)問(wèn)處理時(shí)間。解：（1）調(diào)度序列為（不包括括號(hào)內(nèi)的磁道）(102)1121201

13、25130(199)7050(0)203040608090110磁頭移動(dòng)量=(112-102)+(120-112)+(125-120)+(130-125)+(199-130)+(199-70)+(70-50)+(50-0)+(20-0)+(30-20)+(40-30)+(60-40)+(80-60)+(90-80)+(110-90)=10+8+5+5+69+129+20+50+20+10+10+20+20+10+20=406（磁道）（2）總尋道時(shí)間=1406=406（ms）一次訪(fǎng)盤(pán)的旋轉(zhuǎn)時(shí)間=1/(2R)=1/(26000/min)=1/(2(100/s)=0.005(秒)=5(ms)請(qǐng)求序列

14、共13次訪(fǎng)盤(pán)，總旋轉(zhuǎn)延遲時(shí)間=513=65(ms)1次訪(fǎng)盤(pán)的傳輸時(shí)間=1/(R16)=1/(6000/min)16)=10/16=0.625(ms)13次訪(fǎng)盤(pán)總傳輸時(shí)間=0.62513=8.125(ms)總訪(fǎng)盤(pán)處理時(shí)間=406+65+8.125=479.125(ms) 某文件系統(tǒng)空間的最大容量為4TB(1TB= B),以磁盤(pán)塊為基本分配單位，磁盤(pán)塊大小為1KB，文件控制塊FCB包含一個(gè)512B的索引表區(qū)，請(qǐng)回答下列問(wèn)題。 1）假設(shè)索引表區(qū)僅采用直接索引結(jié)構(gòu)，索引表保存文件所占用的磁盤(pán)快號(hào)，索引表項(xiàng)中塊號(hào)占多少字節(jié)？可支持的單個(gè)文件最大長(zhǎng)度是多少字節(jié)？ 2）假設(shè)索引表區(qū)采用如下結(jié)構(gòu)：第0-7字節(jié)采用格式表示文件創(chuàng)建時(shí)預(yù)分配的連續(xù)存儲(chǔ)空間。起始?jí)K號(hào)占6B，塊數(shù)占2B，剩余504字節(jié)采用直接索引結(jié)構(gòu)，一個(gè)索引項(xiàng)占6B，則可支持的單個(gè)文件最大長(zhǎng)度是多少字節(jié)？為了使單個(gè)文件的長(zhǎng)度達(dá)到最大，請(qǐng)指出起始?jí)K號(hào)和塊數(shù)分別所占字節(jié)數(shù)的合理值并說(shuō)明理由。402解：1）文件系統(tǒng)所能容納的磁盤(pán)塊總數(shù)為4TB/1KB=,因此物理塊的地址需要32位，所以索引項(xiàng)中塊號(hào)最少占32/8=4B。當(dāng)索引表區(qū)采用直接索引結(jié)構(gòu)時(shí)，F(xiàn)CB中能容納512/4=128個(gè)索引項(xiàng)，所以系統(tǒng)科支持的單個(gè)文件最大長(zhǎng)度是128*1KB=