操作系統(tǒng)原理-磁盤管理實(shí)驗(yàn)

廣州大學(xué)學(xué)生實(shí)驗(yàn)報(bào)告開課學(xué)院及實(shí)驗(yàn)室：計(jì)算機(jī)科學(xué)與工程實(shí)驗(yàn)室 2014年12月13日學(xué)院計(jì)算機(jī)科學(xué)與教育軟件學(xué)院年級(jí)/專業(yè)/班姓名學(xué)號(hào)實(shí)驗(yàn)課程名稱操作系統(tǒng)實(shí)驗(yàn)成績(jī)實(shí)驗(yàn)項(xiàng)目名稱磁盤管理實(shí)驗(yàn)指導(dǎo)老師張艷玲一、實(shí)驗(yàn)?zāi)康牧私獠僮飨荡疟P調(diào)度策略的特點(diǎn)及幾種尋道優(yōu)化策略的優(yōu)缺點(diǎn)。二、實(shí)驗(yàn)器材1、計(jì)算機(jī)一臺(tái)。2、MacOSX三、實(shí)驗(yàn)內(nèi)容要求模擬先來(lái)先服務(wù)法（First-Come,First-Served，F(xiàn)CFS），最短尋道時(shí)間優(yōu)先法（ShortestSeekTimeFirst，SSTF），電梯法三種磁盤調(diào)度算法，輸入為一組請(qǐng)求訪問磁道序列，輸出為每種調(diào)度算法的磁頭移動(dòng)軌跡和移動(dòng)的總磁道數(shù)。四、實(shí)驗(yàn)步驟、記錄和結(jié)果實(shí)驗(yàn)并沒要求使用何種語(yǔ)言實(shí)現(xiàn)，于是我使用了我較擅長(zhǎng)的語(yǔ)言O(shè)bjective-C，并在實(shí)現(xiàn)算法的基礎(chǔ)上，實(shí)現(xiàn)了可視化的效果，通過(guò)iphone顯示磁頭路徑軌跡，可以很清晰看出該算法的特性和驗(yàn)證是否正確。程序運(yùn)行截圖如下：默認(rèn)啟動(dòng)是采用書本上的隊(duì)列數(shù)據(jù)，使用FCFS：SSTFLOOK（電梯）由上圖可見，根據(jù)算法計(jì)算的結(jié)果和顯示的路徑都跟書本的一致，證明正確無(wú)誤。分析：FCFSFCFS算法雖然保證了公平性，但是通常來(lái)說(shuō)響應(yīng)時(shí)間是最長(zhǎng)的，由上圖可見，移動(dòng)的總磁道數(shù)相比SSTF相差高達(dá)640-236=404。是SSTF的2.7倍。SSTF：SSTF算法關(guān)鍵在于尋找離讀寫磁頭的當(dāng)前柱面最近的請(qǐng)求（從而使尋道時(shí)間最短），因此代碼實(shí)現(xiàn)關(guān)鍵在于計(jì)算起點(diǎn)到其他點(diǎn)的最短距離。部分關(guān)鍵代碼片段：while(i>=0||j<sort.count){if(i>=0&&j>=sort.count){//剩下前半部分[resultaddObject:sort[i]];i--;continue;}if(j<sort.count&&i<0){//剩下后半部分[resultaddObject:sort[j]];j++;continue;}intn1=[sort[i]intValue];intn2=[sort[j]intValue];if(abs(n1-num)>abs(n2-num)){//將距離最小的插入隊(duì)列[resultaddObject:sort[j]];num=[sort[j]intValue];j++;}else{[resultaddObject:sort[i]];num=[sort[i]intValue];i--;}}SSTF實(shí)現(xiàn)了比FCFS更高的吞吐量和更短的尋道時(shí)間。但是缺點(diǎn)也是很明顯的，SSTF并不能像FCFS一樣保證公平性。根據(jù)算法的特性可推知，它的尋道模式往往是高度局部化的，如果新到達(dá)的請(qǐng)求聚集在中央柱面附近，那么磁道兩端則會(huì)需要極大的響應(yīng)時(shí)間，遠(yuǎn)離讀寫磁頭的請(qǐng)求可能出現(xiàn)饑餓現(xiàn)象。隨機(jī)生成請(qǐng)求隊(duì)列，可見當(dāng)如下情況的時(shí)候，SSTF的兩端會(huì)出現(xiàn)較為極端的響應(yīng)時(shí)間。LOOK（電梯）LOOK算法的表現(xiàn)雖然很像SSTF，但是很好地避免了SSTF會(huì)產(chǎn)生的饑餓現(xiàn)象。通常能夠具有較短的尋道時(shí)間。下圖使用的數(shù)據(jù)跟上圖SSTF中的一樣，經(jīng)對(duì)比可見，采用LOOK能少移動(dòng)55磁道數(shù)。根據(jù)LOOK的特性：當(dāng)前方向的請(qǐng)求完成后，立馬折回完成新方向的請(qǐng)求。則算法實(shí)現(xiàn)方面關(guān)健點(diǎn)主要集中在磁頭方向的折回。部分關(guān)鍵代碼片段：//產(chǎn)生隨機(jī)方向BOOLisToLeft=arc4random()%2;NSComparisonResultorder=isToLeft?NSOrderedAscending:NSOrderedDescending;//找到起點(diǎn)位置intloc=0;for(NSNumber*numinsort){if([numisEqual:source[0]])break;loc++;}//復(fù)制一份排序后的結(jié)果到resultresult=[NSMutableArrayarrayWithArray:sort];for(inti=loc-1;i>=0;i--){[resultaddObject:result[i]];//把起點(diǎn)前一位的磁道加到最后[resultremoveObjectAtIndex:i];//移除該位置數(shù)據(jù)}心得體會(huì)