os復(fù)習(xí)市公開課特等獎市賽課微課一等獎?wù)n件

經(jīng)典題目與模擬練習(xí)1第1頁一、進程并發(fā)：多個程序在一段時間內(nèi)同時發(fā)生進程是什么?與程序區(qū)分進程基本狀態(tài)進程控制塊PCB.進程創(chuàng)建、阻塞、終止過程2第2頁進程同時問題:源于進程相互制約關(guān)系：資源共享，有序合作同時概念：并發(fā)執(zhí)行諸進程之間能有效地共享資源和相互合作，從而使程序執(zhí)行含有可再現(xiàn)性?？刂仆瑫r四大標準臨界資源、臨界區(qū)信號量機制信號量操作原語wait、signal3第3頁經(jīng)典同時題目：生產(chǎn)者-消費者取、用類，計數(shù)控制+互斥哲學(xué)家進餐計數(shù)類、死鎖相關(guān)讀者-寫者有條件互斥類似經(jīng)典題目：單行路，同方向不互斥；異向互斥4第4頁信號量規(guī)律：分析同時關(guān)系、設(shè)置信號量初值、PV操作次序P、V操作成對出現(xiàn)多個進程對互斥同時，PV操作成對出現(xiàn)同進程中，初值為1多個進程有序同時，PV操作成對出現(xiàn)在不一樣進程中，有V操作進程可經(jīng)過控制先于有P操作進程執(zhí)行。初值依據(jù)應(yīng)用情況設(shè)置。5第5頁一閱覽室最多容納100人，讀者進入和離開都要在記錄表上登記，每次只允許一個人登記。怎樣編寫進程間同時關(guān)系。資源：空數(shù)N，記錄表S信號量n=N，mutex=1進程：讀者進程 wait（n） wait（mutex） 進入 signal（mutex） 閱讀后離開 signal（n）6第6頁吸煙者問題（Patil,1971)三個吸煙者在一間房間內(nèi)，還有一個香煙供給者。為了制造并抽掉香煙，每個吸煙者需要三樣?xùn)|西：煙草、紙和火柴。供給者有豐富貨物提供。三個吸煙者中，第一個有自己煙草，第二個有自己紙，第三個有自己火柴。供給者（隨機地）將兩樣?xùn)|西放在桌子上，允許一個吸煙者進行對健康不利吸煙。當吸煙者完成吸煙后喚醒供給者，供給者再放兩樣?xùn)|西在桌面上，然后喚醒另一個吸煙者。試為寫出進程同時關(guān)系。7第7頁主要是雙向有序同時問題吸煙者要由供給者觸發(fā)，s1=0而供給者再次供給也要靠吸煙者觸發(fā)，s2=1供者P（s2）隨機放物品V（s1）吸煙者P（s1）取物品V（s2）加三個控制物品計數(shù)信號量，完整程序以下8第8頁隨機放物品Randomnize; case=random(0,2); if(case==0){ V(tobacco); V(paper); V(smoker1); } elseif(case==1){ V(tobacco); V(match); V(smoker2); } elseif(cass==2){ V(paper); V(match); V(smoker3); }voidsmoker1(){while(1){ P(smoker1); V(match); P(tobacco); P(paper); P(match); //吸煙 V(seller) }}9第9頁二、CPU調(diào)度三級調(diào)度調(diào)度時機\搶占\算法計算調(diào)度程序運行時機：程序正常完成IO\PV阻塞時間片到新任務(wù)產(chǎn)生調(diào)度算法基本調(diào)度算法：FCFS，SJF，HPF，HRRN，RR，F(xiàn)B*實時調(diào)度10第10頁算法名稱特點方式FCFS最簡單不利于短作業(yè)非搶占SJF/SPF照料平均周轉(zhuǎn)時間不適于長作業(yè)非搶占/搶占HPF/HRRN優(yōu)先權(quán)考慮全方面非搶占/搶占RR及時響應(yīng)簡單時間片輪轉(zhuǎn)FB最綜合一個算法時間片輪轉(zhuǎn)/馬上搶占11第11頁某系統(tǒng)進程請求如右圖，畫出RR調(diào)度下調(diào)度過程圖。并計算平均周轉(zhuǎn)時間。設(shè)時間片為2。進程名開始時刻執(zhí)行時間A03B23C34D47ABCD012345678901234567890ACBCBDACDBA12第12頁死鎖相關(guān)概念與認識四個必要條件處理死鎖各種方法防止死鎖銀行家算法（相對預(yù)防死鎖，是一個軟限制。）安全狀態(tài)算法、計算13第13頁三、存放器管理連續(xù)分配單一連續(xù)、固定分區(qū)動態(tài)分區(qū)分配可重定位動態(tài)分區(qū)（有緊湊功效）離散分配分頁，地址轉(zhuǎn)換過程，計算分段虛擬概念：虛擬、局部性置換調(diào)度算法：缺頁次數(shù)（掉入次數(shù)） 缺頁率=缺頁次數(shù)/總頁面數(shù)14第14頁例分頁系統(tǒng)，主存容量64K，頁面大小1K。一個4K大作業(yè)，0-3頁分別分配到物理塊2、4、6、7中。該作業(yè)邏輯地址格式怎樣？十進制邏輯地址1023（B）轉(zhuǎn)換為物理地址畫出地址變換過程。答：即頁號與頁內(nèi)地址位數(shù)大小該作業(yè)4個頁面編號需要2位；每頁1K大小，即1K條指令編號需10位頁號頁內(nèi)地址11109 … 015第15頁邏輯地址10231023/1K=0余10230頁對應(yīng)物理塊2，所以物理地址是2*1K+1023=2048+1023=307101023頁表始址X頁表長度4頁表存放器

頁號塊號02142637X+02102316第16頁例虛擬內(nèi)存管理中LRU頁面置換算法設(shè)頁面走向以下，分配給該作業(yè)3個內(nèi)存塊，畫出置換過程圖，并計算缺頁率。458134465127613注意在旁邊對LRU棧次序?qū)崟r把握17第17頁四、文件管理文件結(jié)構(gòu)邏輯結(jié)構(gòu)：有結(jié)構(gòu)文件：次序，鏈接，索引物理結(jié)構(gòu)：已分配空間統(tǒng)計連續(xù)、鏈接、索引、混合索引分配方式 FAT表計算，索引文件大小計算，UNIX下混合索引空閑空間管理表、盤區(qū)\盤塊鏈、成組鏈接、位示圖目錄、共享18第18頁例：FAT與索引計算FAT表計算物理空間容量/盤塊大小=FAT表項個數(shù)個數(shù)決定位數(shù),決定每項大小個數(shù)*每項大小索引結(jié)點盤塊大小/盤塊號大小=可統(tǒng)計盤塊個數(shù)單索引下，一個索引結(jié)點能統(tǒng)計N個盤塊，則文件最大長度為：N*盤塊大小19第19頁例：混合索引分配方式計算FCB有13個地址項，0-9為直接地址，10為一次間接地址，11為二次間接地址，12為三次間接地址。若盤塊大小為512B，盤塊號需3B統(tǒng)計，每個盤塊最多存放170個盤塊地址。該文件系統(tǒng)文件最大允許多長？10+170+170*170+170*170*170=4942080塊=4942080*512B=2471040KB將文件字節(jié)偏移量15000轉(zhuǎn)換為物理塊號和塊內(nèi)偏移。15000/512=29余152。10=<29<=10+170.所以文件使用第29塊盤塊號，統(tǒng)計在FCB中10項，即一次間接地址索引盤塊中。從10項統(tǒng)計地址找到索引表，第19項即是要找物理塊。20第20頁若FCB已存在內(nèi)存，其它信息均在外存，訪問該文件某位置內(nèi)容，最少/最多需要幾次訪問磁盤？最少需訪問磁盤情況是直接尋址，直接讀FCB中統(tǒng)計地址，訪問磁盤1次即可最多需訪問磁盤情況是三次間接尋址過程，需讀三次間接索引塊中內(nèi)容，然后讀它里面統(tǒng)計二次接索引塊中內(nèi)容，再一次，最終才能取得文件信息實際地址。姑，最多情況需4次訪問磁盤。21第21頁外存空間管理空閑空間三種分配方式：連續(xù)、鏈接、索引空閑空間管理空閑表/鏈、位示土圖、成組鏈接成組鏈接22第22頁例：某系統(tǒng)采取成組鏈接法管理磁盤空閑空間，當前狀態(tài)以下列圖，問：還有多少空閑盤塊？若從當前狀態(tài)下，系統(tǒng)分配3個盤塊給某文件后，又刪除另一文件，回收了第700，711，703，788，701這5個盤塊。則磁盤空間狀態(tài)圖中鏈接情況又怎樣？23第23頁空閑盤塊成組鏈接示意圖7901-7999全部空閑盤塊，被分成若干個組設(shè)有10000個盤塊，每100個分為1組，則分成100個組。201-7999為文件區(qū)各組鏈接起來。301-400401-500……201-300299#202#201#數(shù)據(jù)空間302…400100301399#302#301#數(shù)據(jù)空間下一組指針可用塊數(shù)數(shù)據(jù)空間799