現(xiàn)磁盤調(diào)度算法：從FCFS到LOOK的工程實(shí)踐)
1. 項目概述從理論到實(shí)踐的磁盤調(diào)度算法在操作系統(tǒng)的學(xué)習(xí)與實(shí)踐中磁盤調(diào)度算法是一個繞不開的核心話題。它不僅僅是教科書上的幾個公式和流程圖更是直接影響系統(tǒng)I/O性能、關(guān)乎用戶體驗(yàn)的關(guān)鍵技術(shù)。很多初學(xué)者包括當(dāng)年的我在學(xué)完FCFS、SSTF、SCAN這些算法后總覺得隔著一層紗——原理懂了但它是如何在一個“活”的系統(tǒng)里運(yùn)作的參數(shù)怎么調(diào)不同場景下到底選哪個這些問題光靠看書和做題很難有深刻的體會。這個項目的初衷就是親手“造”一個磁盤調(diào)度算法的模擬器。我們不依賴任何圖形界面庫或復(fù)雜的框架就用最純粹的C和標(biāo)準(zhǔn)庫中的vector容器把教科書上的算法從靜態(tài)的圖示變成動態(tài)的、可觀察、可測量的代碼。通過這個過程你會真正理解每個算法背后的“權(quán)衡”為什么SSTF可能導(dǎo)致饑餓SCAN和C-SCAN的“電梯”比喻到底體現(xiàn)在代碼的哪一行LOOK算法又是如何優(yōu)化了SCAN的機(jī)械臂移動當(dāng)你親手實(shí)現(xiàn)它們并看到不同的請求序列下磁頭移動總距離的顯著差異時那種對原理的領(lǐng)悟是無可替代的。更重要的是我們選擇vector作為核心數(shù)據(jù)結(jié)構(gòu)。它動態(tài)、靈活完美契合磁盤請求隊列隨時可能到來的新請求這一特性。通過這個項目你不僅能鞏固操作系統(tǒng)知識還能深入掌握C中vector的增刪查改、排序、迭代器使用等實(shí)戰(zhàn)技巧理解如何用合適的數(shù)據(jù)結(jié)構(gòu)優(yōu)雅地實(shí)現(xiàn)特定算法。這絕對是一舉兩得的練習(xí)。2. 核心概念與設(shè)計思路拆解在動手寫代碼之前我們必須把幾個關(guān)鍵概念和設(shè)計思路理清楚。這就像蓋房子前先畫好圖紙能避免后續(xù)很多返工。2.1 磁盤調(diào)度到底在解決什么問題想象一下磁盤的讀寫磁頭就像唱機(jī)的唱針磁盤表面被劃分為一個個同心圓的磁道。當(dāng)多個進(jìn)程同時發(fā)出讀寫磁盤的請求時這些請求的目標(biāo)磁道號我們稱之為“請求序列”可能是雜亂無章的。如果磁頭完全按照請求到達(dá)的先后順序FCFS去服務(wù)它可能會在磁盤表面“長途奔襲”從最外道跳到最內(nèi)道再跳回中間道導(dǎo)致大量的尋道時間磁頭移動到目標(biāo)磁道所需的時間。尋道時間是磁盤I/O中最耗時的部分因此磁盤調(diào)度算法的核心目標(biāo)就是重新排列服務(wù)這些請求的順序以最小化磁頭的平均尋道時間從而提高系統(tǒng)的整體吞吐量和響應(yīng)速度。2.2 算法家族巡禮特點(diǎn)與適用場景我們主要實(shí)現(xiàn)四種經(jīng)典算法它們各有千秋先來先服務(wù)FCFS最簡單最公平。按請求到達(dá)順序服務(wù)。但性能往往最差因?yàn)橥耆珱]有優(yōu)化尋道路徑。它的價值在于作為一個性能基準(zhǔn)Baseline其他算法的優(yōu)化效果可以與之對比。最短尋道時間優(yōu)先SSTF貪心算法。總是選擇當(dāng)前磁頭所在位置最近的那個請求進(jìn)行服務(wù)。性能通常比FCFS好很多。但它的致命缺點(diǎn)是可能導(dǎo)致饑餓Starvation。如果一個請求的磁道號離當(dāng)前磁頭始終很遠(yuǎn)而不斷有離得更近的新請求到來那么這個“遠(yuǎn)方”的請求可能永遠(yuǎn)得不到服務(wù)。掃描算法SCAN電梯算法磁頭在一個方向上移動服務(wù)沿途的所有請求直到到達(dá)該方向的最后一個磁道或邊界然后掉頭反向移動并服務(wù)請求。就像電梯上行時只響應(yīng)上行請求到了頂層再下行。它解決了SSTF的饑餓問題但對兩端請求的響應(yīng)時間不平均。循環(huán)掃描算法C-SCANSCAN的變種。磁頭單向移動比如只從內(nèi)向外服務(wù)沿途請求。到達(dá)終點(diǎn)后立即快速返回起點(diǎn)此過程不服務(wù)任何請求然后重新開始單向掃描。這樣對所有請求的響應(yīng)時間更公平。LOOK與C-LOOK算法這是SCAN和C-SCAN的優(yōu)化版。它們并不傻傻地走到物理邊界而是走到該方向上的最后一個請求的磁道就掉頭或返回。這避免了無意義的空跑是實(shí)際系統(tǒng)中更常用的策略。我們的實(shí)現(xiàn)將以LOOK和C-LOOK為重點(diǎn)。2.3 為什么選擇C和vectorC足夠底層能讓我們關(guān)注算法和數(shù)據(jù)結(jié)構(gòu)本身而不是被高級語言或框架的抽象所干擾。性能可控適合做這種偏底層的模擬。std::vector它是實(shí)現(xiàn)這個項目的“神器”。動態(tài)數(shù)組請求序列的長度是不固定的vector可以動態(tài)增長完美匹配。高效的隨機(jī)訪問算法中需要頻繁比較磁道號、計算距離vector通過下標(biāo)[]或迭代器的隨機(jī)訪問是O(1)復(fù)雜度效率極高。強(qiáng)大的STL算法支持我們可以方便地使用std::sort,std::find,std::lower_bound等算法來對請求隊列進(jìn)行排序和查找極大簡化代碼。模擬請求隊列我們可以用一個vectorint來代表待處理的請求隊列另一個vectorint來記錄服務(wù)完成的順序清晰直觀。設(shè)計思路我們將構(gòu)建一個DiskScheduler類。它至少需要包含當(dāng)前磁頭位置、請求序列、磁道總數(shù)等屬性。成員函數(shù)則包括各個調(diào)度算法的實(shí)現(xiàn)如schedule_FCFS(),schedule_SSTF()等每個函數(shù)都返回服務(wù)順序和總尋道距離。通過vector的靈活操作插入、刪除、排序、遍歷來模擬磁頭的移動和請求的服務(wù)過程。3. 核心數(shù)據(jù)結(jié)構(gòu)與算法實(shí)現(xiàn)細(xì)節(jié)接下來我們深入到代碼層面看看如何用vector這把“瑞士軍刀”來實(shí)現(xiàn)這些算法。我會先給出核心的數(shù)據(jù)結(jié)構(gòu)設(shè)計然后逐一剖析每個算法的實(shí)現(xiàn)要點(diǎn)和易錯點(diǎn)。3.1 數(shù)據(jù)結(jié)構(gòu)定義與初始化我們首先定義一個DiskScheduler類。這里做出一個關(guān)鍵設(shè)計決策不直接在原始請求序列上操作而是使用副本。因?yàn)槊總€調(diào)度算法都會改變請求的服務(wù)順序如果直接修改原始序列那么運(yùn)行完一個算法后原始序列就被破壞了無法再給下一個算法使用。#include iostream #include vector #include algorithm // 用于sort, min_element等 #include cmath // 用于abs #include climits // 用于INT_MAX class DiskScheduler { private: int currentHead; // 當(dāng)前磁頭位置 int totalTracks; // 磁盤總磁道數(shù)用于SCAN/C-SCAN判斷邊界 std::vectorint requestSequence; // 原始請求序列 public: // 構(gòu)造函數(shù) DiskScheduler(int startPos, int tracks, const std::vectorint requests) : currentHead(startPos), totalTracks(tracks), requestSequence(requests) { // 可以添加一些基本驗(yàn)證例如請求磁道號是否在有效范圍內(nèi)[0, totalTracks-1] for (int req : requests) { if (req 0 || req tracks) { std::cerr 警告請求磁道 req 超出有效范圍 [0, tracks-1 ]。 std::endl; } } } // 各調(diào)度算法函數(shù)將在這里聲明 std::pairstd::vectorint, int schedule_FCFS(); std::pairstd::vectorint, int schedule_SSTF(); std::pairstd::vectorint, int schedule_SCAN(char direction); // direction: inward or outward std::pairstd::vectorint, int schedule_CSCAN(char direction); std::pairstd::vectorint, int schedule_LOOK(char direction); std::pairstd::vectorint, int schedule_CLOOK(char direction); };注意totalTracks參數(shù)對于SCAN/C-SCAN是必要的因?yàn)樗鼈冃枰牢锢磉吔?和totalTracks-1。對于LOOK/C-LOOK理論上可以不需要但保留它有助于程序的完整性也可以用于請求的合法性校驗(yàn)。3.2 FCFS算法實(shí)現(xiàn)簡單但重要FCFS的實(shí)現(xiàn)是最直接的它幾乎不涉及vector的復(fù)雜操作但它是我們測試和比較的基準(zhǔn)。std::pairstd::vectorint, int DiskScheduler::schedule_FCFS() { std::vectorint scheduleOrder; // 記錄服務(wù)順序 int totalSeek 0; int head currentHead; // 使用局部變量不改變成員變量 for (int req : requestSequence) { scheduleOrder.push_back(req); totalSeek std::abs(head - req); // 計算尋道距離 head req; // 移動磁頭 } return {scheduleOrder, totalSeek}; }要點(diǎn)直接遍歷原始請求序列requestSequence。std::abs()用于計算絕對距離。返回一個pair包含服務(wù)順序和總尋道距離。這樣主函數(shù)可以方便地獲取結(jié)果并打印。3.3 SSTF算法實(shí)現(xiàn)貪心的陷阱SSTF的實(shí)現(xiàn)開始有趣起來。我們需要在剩余的請求中反復(fù)尋找離當(dāng)前磁頭最近的那個。std::pairstd::vectorint, int DiskScheduler::schedule_SSTF() { std::vectorint requests requestSequence; // 關(guān)鍵使用副本 std::vectorint scheduleOrder; int totalSeek 0; int head currentHead; while (!requests.empty()) { // 使用迭代器和min_element算法找到最小距離的請求 auto closestIt std::min_element(requests.begin(), requests.end(), [head](int a, int b) { return std::abs(a - head) std::abs(b - head); }); // 處理找到的請求 int closestTrack *closestIt; scheduleOrder.push_back(closestTrack); totalSeek std::abs(head - closestTrack); head closestTrack; // 關(guān)鍵步驟從待處理列表中刪除已服務(wù)的請求 requests.erase(closestIt); } return {scheduleOrder, totalSeek}; }核心技巧與避坑指南一定要用副本std::vectorint requests requestSequence;這行代碼至關(guān)重要。否則運(yùn)行一次SSTF后原始請求序列就空了。使用std::min_element與Lambda表達(dá)式這是C STL的優(yōu)雅之處。min_element返回指向最小元素的迭代器。我們傳入一個Lambda表達(dá)式作為自定義比較器比較的標(biāo)準(zhǔn)是到當(dāng)前head的距離。這比手動寫循環(huán)遍歷找最小值更簡潔、更不易出錯。刪除元素requests.erase(closestIt)用于刪除已服務(wù)的請求。注意erase會使指向被刪除元素及其后元素的迭代器失效但因?yàn)槲覀兠看窝h(huán)都重新調(diào)用min_element從頭查找所以沒有問題。如果要在循環(huán)中復(fù)用迭代器則需要更謹(jǐn)慎的處理如it requests.erase(it)的模式。3.4 LOOK算法實(shí)現(xiàn)高效的“電梯”LOOK是SCAN的優(yōu)化也是實(shí)際中最常用的算法之一。它的實(shí)現(xiàn)比SSTF稍復(fù)雜需要處理方向和對請求序列的排序。std::pairstd::vectorint, int DiskScheduler::schedule_LOOK(char direction) { std::vectorint requests requestSequence; // 使用副本 std::vectorint scheduleOrder; int totalSeek 0; int head currentHead; // 對請求排序這是LOOK/SCAN類算法的前提 std::sort(requests.begin(), requests.end()); // 確定初始掃描方向上的請求子集 // 使用lower_bound找到第一個大于等于head的位置 auto it std::lower_bound(requests.begin(), requests.end(), head); std::vectorint left(requests.begin(), it); // 小于head的請求逆序 std::vectorint right(it, requests.end()); // 大于等于head的請求 if (direction o || direction O) { // 向外磁道號增大 // 先服務(wù)右側(cè)向外的方向 for (int track : right) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } // 掉頭服務(wù)左側(cè)需要逆序因?yàn)榇蓬^向內(nèi)移動 std::reverse(left.begin(), left.end()); for (int track : left) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } } else { // 向內(nèi)磁道號減小默認(rèn)或i // 先服務(wù)左側(cè)需要逆序因?yàn)楫?dāng)前head在右側(cè)向左移動 std::reverse(left.begin(), left.end()); for (int track : left) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } // 掉頭服務(wù)右側(cè) for (int track : right) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } } return {scheduleOrder, totalSeek}; }實(shí)現(xiàn)解析與難點(diǎn)排序std::sort(requests.begin(), requests.end())。LOOK算法需要知道請求的全局分布排序是第一步。分割請求隊列使用std::lower_bound找到第一個不小于head的請求位置。它將排序后的隊列分割成left小于head和right大于等于head兩部分。lower_bound使用二分查找效率是O(log n)。方向處理這是最容易混淆的地方。代碼中通過direction參數(shù)控制初始移動方向。向外‘o’先遍歷right從小到大然后反轉(zhuǎn)left從大到小再遍歷。因?yàn)榈纛^后磁頭是向內(nèi)移動需要服務(wù)比當(dāng)前head此時已在最右更小的磁道所以left需要逆序。向內(nèi)‘i’先反轉(zhuǎn)left從大到小并遍歷然后遍歷right從小到大。原理類似。SCAN算法的實(shí)現(xiàn)如果你需要實(shí)現(xiàn)標(biāo)準(zhǔn)的SCAN走到物理邊界只需在LOOK的基礎(chǔ)上在服務(wù)完一個方向后先讓磁頭移動到邊界0或totalTracks-1并把這部分移動距離加到totalSeek中然后再掉頭。代碼結(jié)構(gòu)類似但增加了邊界移動的邏輯。3.5 C-LOOK算法實(shí)現(xiàn)更公平的循環(huán)C-LOOK是C-SCAN的優(yōu)化版實(shí)現(xiàn)上與LOOK類似但“掉頭”的邏輯不同。std::pairstd::vectorint, int DiskScheduler::schedule_CLOOK(char direction) { std::vectorint requests requestSequence; std::vectorint scheduleOrder; int totalSeek 0; int head currentHead; std::sort(requests.begin(), requests.end()); auto it std::lower_bound(requests.begin(), requests.end(), head); std::vectorint left(requests.begin(), it); std::vectorint right(it, requests.end()); if (direction o || direction O) { // 向外掃描 for (int track : right) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } // C-LOOK關(guān)鍵點(diǎn)從最左端重新開始而不是掉頭 // 如果左側(cè)有請求磁頭需要“快速返回”到左側(cè)第一個請求 if (!left.empty()) { totalSeek std::abs(head - left.front()); // 快速返回的距離 head left.front(); for (int track : left) { // 左側(cè)請求已經(jīng)是升序直接遍歷 scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } } } else { // 向內(nèi)掃描邏輯對稱 // 注意向內(nèi)掃描時left需要逆序從大到小服務(wù) std::reverse(left.begin(), left.end()); for (int track : left) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } // 快速返回到右側(cè)第一個請求 if (!right.empty()) { totalSeek std::abs(head - right.front()); head right.front(); for (int track : right) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } } } return {scheduleOrder, totalSeek}; }C-LOOK與LOOK的核心區(qū)別LOOK服務(wù)完一個方向后掉頭反向服務(wù)。C-LOOK服務(wù)完一個方向后直接跳到另一個方向的起始端快速返回然后繼續(xù)同方向掃描。在代碼中體現(xiàn)為服務(wù)完right后不是反轉(zhuǎn)left而是直接跳到left.front()然后順序服務(wù)left。這保證了所有請求的等待時間相對更公平。4. 完整模擬程序與測試案例分析有了核心算法函數(shù)我們需要一個主程序來驅(qū)動測試并直觀地展示不同算法的效果。我們將設(shè)計一個交互性較強(qiáng)的控制臺程序。4.1 主程序框架與交互設(shè)計#include iomanip // 用于格式化輸出 void printSchedule(const std::string algoName, const std::pairstd::vectorint, int result) { std::cout \n algoName 調(diào)度結(jié)果 std::endl; std::cout 服務(wù)順序: ; for (size_t i 0; i result.first.size(); i) { std::cout result.first[i]; if (i ! result.first.size() - 1) std::cout - ; } std::cout \n總尋道距離: result.second std::endl; std::cout 平均尋道長度: std::fixed std::setprecision(2) static_castdouble(result.second) / result.first.size() std::endl; } int main() { // 模擬參數(shù)設(shè)置 int startHead 100; int totalTracks 200; // 假設(shè)磁道號0-199 std::vectorint requests {55, 58, 39, 18, 90, 160, 150, 38, 184}; DiskScheduler scheduler(startHead, totalTracks, requests); std::cout 初始磁頭位置: startHead std::endl; std::cout 請求序列: ; for (int r : requests) std::cout r ; std::cout std::endl; // 測試不同算法 auto fcfsResult scheduler.schedule_FCFS(); printSchedule(FCFS, fcfsResult); auto sstfResult scheduler.schedule_SSTF(); printSchedule(SSTF, sstfResult); // LOOK算法可以測試不同方向 auto lookOutResult scheduler.schedule_LOOK(o); printSchedule(LOOK (向外), lookOutResult); auto lookInResult scheduler.schedule_LOOK(i); printSchedule(LOOK (向內(nèi)), lookInResult); auto clookResult scheduler.schedule_CLOOK(o); printSchedule(C-LOOK (向外), clookResult); return 0; }4.2 測試案例深度解析讓我們用上面的請求序列{55, 58, 39, 18, 90, 160, 150, 38, 184}磁頭起始于100號磁道來分析一下。FCFS結(jié)果 服務(wù)順序55 - 58 - 39 - 18 - 90 - 160 - 150 - 38 - 184 總尋道距離 |100-55||55-58||58-39||39-18||18-90||90-160||160-150||150-38||38-184| 4531921727010112146 498可以看到磁頭來回劇烈擺動從100跳到55向內(nèi)又跳到58向外再跳回39向內(nèi)……效率很低。SSTF結(jié)果從100開始最近的是90距離10服務(wù)90。從90開始最近的是58距離32但58和55都距離32這里就涉及min_element在距離相等時的選擇它會選擇第一個遇到的取決于vector的順序。假設(shè)先找到58服務(wù)58。從58開始最近的是55距離3服務(wù)55。從55開始最近的是39距離16但39和38呢同樣問題。假設(shè)先服務(wù)39。以此類推……最終順序可能是90, 58, 55, 39, 38, 18, 150, 160, 184。 總尋道距離會遠(yuǎn)小于FCFS可能約在200-250之間。但注意如果請求18一直離得很遠(yuǎn)而90、58、55附近不斷有新請求18可能被“餓死”。LOOK (向外) 結(jié)果排序后請求: [18, 38, 39, 55, 58, 90, 150, 160, 184]當(dāng)前head100lower_bound找到right[150, 160, 184]100left[18,38,39,55,58,90]100。向外掃描服務(wù)150, 160, 184。掉頭此時head184反轉(zhuǎn)left得到[90, 58, 55, 39, 38, 18]服務(wù)它們。 服務(wù)順序150 - 160 - 184 - 90 - 58 - 55 - 39 - 38 - 18 總尋道距離 (100-150)(150-160)(160-184)(184-90)(90-58)(58-55)(55-39)(39-38)(38-18) 5010249432316120 250這個距離比FCFS好很多并且沒有饑餓問題。C-LOOK (向外) 結(jié)果同LOOK先服務(wù)right: 150, 160, 184?？焖俜祷貜?84直接跳到left的第一個元素90。距離184-9094。然后順序服務(wù)left: 90, 58, 55, 39, 38, 18。 服務(wù)順序150 - 160 - 184 - 90 - 58 - 55 - 39 - 38 - 18 順序看起來和LOOK一樣注意雖然順序一樣但尋道距離的計算不同。在服務(wù)完184后LOOK是掉頭移動到90距離94而C-LOOK是“快速返回”到90距離也是94。在這個特定序列下兩者總距離巧合相同。但如果left的第一個請求不是90而是18那么LOOK掉頭需要從184走到18距離很大而C-LOOK快速返回的距離是184到18和LOOK一樣。但C-LOOK的設(shè)計哲學(xué)是單向循環(huán)對所有請求的響應(yīng)時間方差更小。通過這個對比你可以清晰地看到不同算法在同一組數(shù)據(jù)下的表現(xiàn)差異。動手修改請求序列和起始位置觀察結(jié)果的變化是理解這些算法行為的最佳方式。5. 性能考量、擴(kuò)展性與常見問題在實(shí)現(xiàn)基礎(chǔ)功能后我們可以從工程和優(yōu)化的角度思考更多。5.1 時間復(fù)雜度分析FCFS: O(n)只需一次遍歷。SSTF: O(n2)。因?yàn)槊看畏?wù)一個請求都需要在剩余列表中線性搜索min_element是O(k)k為剩余請求數(shù)最近的那個。對于n個請求總復(fù)雜度是n(n-1)...1 O(n2)。這是SSTF的一個缺點(diǎn)當(dāng)請求隊列很長時調(diào)度器本身的計算開銷會變大?？梢允褂脙?yōu)先隊列如std::priority_queue進(jìn)行優(yōu)化將查找最近請求的復(fù)雜度降到O(log n)總體復(fù)雜度降至O(n log n)。LOOK/C-LOOK/SCAN/C-SCAN: O(n log n)。主要開銷在于初始的排序std::sort其平均復(fù)雜度為O(n log n)。之后的掃描過程是線性的O(n)。因此對于請求數(shù)較多的情況這些算法的預(yù)處理開銷是值得的因?yàn)樗鼈兡芴峁└€(wěn)定、更優(yōu)的整體性能。5.2 如何模擬動態(tài)請求到達(dá)我們的實(shí)現(xiàn)是靜態(tài)的即所有請求一開始就已知。但在真實(shí)操作系統(tǒng)中請求是動態(tài)到達(dá)的。如何模擬一個簡單的思路是引入“時間”概念。我們可以維護(hù)一個“當(dāng)前時間”每個請求有一個“到達(dá)時間”。調(diào)度器在每個時刻只從“已到達(dá)”的請求中進(jìn)行調(diào)度。這需要更復(fù)雜的事件驅(qū)動模擬但核心的調(diào)度算法邏輯不變只是每次調(diào)度的候選集是“已到達(dá)且未服務(wù)”的請求子集。5.3 常見問題與調(diào)試技巧請求磁道號越界在構(gòu)造函數(shù)或添加請求時務(wù)必檢查磁道號是否在[0, totalTracks-1]范圍內(nèi)。否則在計算距離或判斷方向時可能出現(xiàn)邏輯錯誤?？照埱笮蛄刑幚砣绻鹯equestSequence為空你的算法函數(shù)應(yīng)該能優(yōu)雅處理返回空的服務(wù)順序和0尋道距離。在SSTF的while循環(huán)和LOOK的lower_bound前添加空判斷是個好習(xí)慣。方向參數(shù)校驗(yàn)schedule_LOOK和schedule_CSCAN中的direction參數(shù)應(yīng)該只接受有效的字符如‘i’, ‘I’, ‘o’, ‘O’并為無效輸入提供默認(rèn)值或錯誤提示。迭代器失效在SSTF中我們在循環(huán)內(nèi)調(diào)用了requests.erase(closestIt)。正如之前提到的這會使closestIt失效。因?yàn)槲覀兠看窝h(huán)都重新計算closestIt所以安全。但如果想優(yōu)化在刪除后使用erase返回的新的迭代器作為下一輪查找的起點(diǎn)需要小心處理邊界條件。浮點(diǎn)數(shù)比較計算平均尋道長度時注意整數(shù)除法會截斷小數(shù)。務(wù)必先轉(zhuǎn)換為double再相除并使用std::setprecision控制輸出精度?？梢暬{(diào)試對于復(fù)雜的序列在紙上畫出磁道軸手動模擬一遍算法的步驟再與程序輸出對比是排查邏輯錯誤最有效的方法。也可以在每個算法內(nèi)部添加一些調(diào)試輸出打印出每一步磁頭的位置和選擇的請求。5.4 項目擴(kuò)展方向這個基礎(chǔ)模擬器可以作為一個起點(diǎn)進(jìn)行很多有意義的擴(kuò)展實(shí)現(xiàn)更多算法如N-Step-SCAN將請求隊列分成長度為N的子隊列每個子隊列內(nèi)用SCAN、F-SCAN在掃描期間凍結(jié)新到的請求等本次掃描完再處理等。圖形化界面使用如Qt、SFML或簡單的Web前端Emscripten編譯到WebAssembly將調(diào)度過程動畫展示出來磁頭移動、請求服務(wù)過程一目了然。性能對比與統(tǒng)計分析自動生成大量隨機(jī)請求序列批量運(yùn)行所有算法統(tǒng)計平均尋道距離、平均響應(yīng)時間、標(biāo)準(zhǔn)差等指標(biāo)用圖表如控制臺打印表格或生成CSV文件直觀對比。集成到簡單OS模擬器中將這個磁盤調(diào)度模塊作為你編寫的簡易操作系統(tǒng)課程設(shè)計項目的一部分模擬進(jìn)程發(fā)出I/O請求并被調(diào)度的完整過程。通過這個從零實(shí)現(xiàn)磁盤調(diào)度算法的項目你收獲的遠(yuǎn)不止是幾個C函數(shù)。你深入理解了操作系統(tǒng)核心組件的工作原理掌握了用恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)vector實(shí)現(xiàn)復(fù)雜算法的方法并鍛煉了將理論轉(zhuǎn)化為實(shí)踐的能力。下次當(dāng)你聽到“電梯算法”或“磁盤調(diào)度”時你腦海中浮現(xiàn)的將不再是枯燥的定義而是一行行自己寫過的、讓磁頭高效移動的代碼。這才是真正意義上的“學(xué)會”。 C++實(shí)現(xiàn)磁盤調(diào)度算法：從FCFS到LOOK的工程實(shí)踐
1. 項目概述從理論到實(shí)踐的磁盤調(diào)度算法在操作系統(tǒng)的學(xué)習(xí)與實(shí)踐中磁盤調(diào)度算法是一個繞不開的核心話題。它不僅僅是教科書上的幾個公式和流程圖更是直接影響系統(tǒng)I/O性能、關(guān)乎用戶體驗(yàn)的關(guān)鍵技術(shù)。很多初學(xué)者包括當(dāng)年的我在學(xué)完FCFS、SSTF、SCAN這些算法后總覺得隔著一層紗——原理懂了但它是如何在一個“活”的系統(tǒng)里運(yùn)作的參數(shù)怎么調(diào)不同場景下到底選哪個這些問題光靠看書和做題很難有深刻的體會。這個項目的初衷就是親手“造”一個磁盤調(diào)度算法的模擬器。我們不依賴任何圖形界面庫或復(fù)雜的框架就用最純粹的C和標(biāo)準(zhǔn)庫中的vector容器把教科書上的算法從靜態(tài)的圖示變成動態(tài)的、可觀察、可測量的代碼。通過這個過程你會真正理解每個算法背后的“權(quán)衡”為什么SSTF可能導(dǎo)致饑餓SCAN和C-SCAN的“電梯”比喻到底體現(xiàn)在代碼的哪一行LOOK算法又是如何優(yōu)化了SCAN的機(jī)械臂移動當(dāng)你親手實(shí)現(xiàn)它們并看到不同的請求序列下磁頭移動總距離的顯著差異時那種對原理的領(lǐng)悟是無可替代的。更重要的是我們選擇vector作為核心數(shù)據(jù)結(jié)構(gòu)。它動態(tài)、靈活完美契合磁盤請求隊列隨時可能到來的新請求這一特性。通過這個項目你不僅能鞏固操作系統(tǒng)知識還能深入掌握C中vector的增刪查改、排序、迭代器使用等實(shí)戰(zhàn)技巧理解如何用合適的數(shù)據(jù)結(jié)構(gòu)優(yōu)雅地實(shí)現(xiàn)特定算法。這絕對是一舉兩得的練習(xí)。2. 核心概念與設(shè)計思路拆解在動手寫代碼之前我們必須把幾個關(guān)鍵概念和設(shè)計思路理清楚。這就像蓋房子前先畫好圖紙能避免后續(xù)很多返工。2.1 磁盤調(diào)度到底在解決什么問題想象一下磁盤的讀寫磁頭就像唱機(jī)的唱針磁盤表面被劃分為一個個同心圓的磁道。當(dāng)多個進(jìn)程同時發(fā)出讀寫磁盤的請求時這些請求的目標(biāo)磁道號我們稱之為“請求序列”可能是雜亂無章的。如果磁頭完全按照請求到達(dá)的先后順序FCFS去服務(wù)它可能會在磁盤表面“長途奔襲”從最外道跳到最內(nèi)道再跳回中間道導(dǎo)致大量的尋道時間磁頭移動到目標(biāo)磁道所需的時間。尋道時間是磁盤I/O中最耗時的部分因此磁盤調(diào)度算法的核心目標(biāo)就是重新排列服務(wù)這些請求的順序以最小化磁頭的平均尋道時間從而提高系統(tǒng)的整體吞吐量和響應(yīng)速度。2.2 算法家族巡禮特點(diǎn)與適用場景我們主要實(shí)現(xiàn)四種經(jīng)典算法它們各有千秋先來先服務(wù)FCFS最簡單最公平。按請求到達(dá)順序服務(wù)。但性能往往最差因?yàn)橥耆珱]有優(yōu)化尋道路徑。它的價值在于作為一個性能基準(zhǔn)Baseline其他算法的優(yōu)化效果可以與之對比。最短尋道時間優(yōu)先SSTF貪心算法。總是選擇當(dāng)前磁頭所在位置最近的那個請求進(jìn)行服務(wù)。性能通常比FCFS好很多。但它的致命缺點(diǎn)是可能導(dǎo)致饑餓Starvation。如果一個請求的磁道號離當(dāng)前磁頭始終很遠(yuǎn)而不斷有離得更近的新請求到來那么這個“遠(yuǎn)方”的請求可能永遠(yuǎn)得不到服務(wù)。掃描算法SCAN電梯算法磁頭在一個方向上移動服務(wù)沿途的所有請求直到到達(dá)該方向的最后一個磁道或邊界然后掉頭反向移動并服務(wù)請求。就像電梯上行時只響應(yīng)上行請求到了頂層再下行。它解決了SSTF的饑餓問題但對兩端請求的響應(yīng)時間不平均。循環(huán)掃描算法C-SCANSCAN的變種。磁頭單向移動比如只從內(nèi)向外服務(wù)沿途請求。到達(dá)終點(diǎn)后立即快速返回起點(diǎn)此過程不服務(wù)任何請求然后重新開始單向掃描。這樣對所有請求的響應(yīng)時間更公平。LOOK與C-LOOK算法這是SCAN和C-SCAN的優(yōu)化版。它們并不傻傻地走到物理邊界而是走到該方向上的最后一個請求的磁道就掉頭或返回。這避免了無意義的空跑是實(shí)際系統(tǒng)中更常用的策略。我們的實(shí)現(xiàn)將以LOOK和C-LOOK為重點(diǎn)。2.3 為什么選擇C和vectorC足夠底層能讓我們關(guān)注算法和數(shù)據(jù)結(jié)構(gòu)本身而不是被高級語言或框架的抽象所干擾。性能可控適合做這種偏底層的模擬。std::vector它是實(shí)現(xiàn)這個項目的“神器”。動態(tài)數(shù)組請求序列的長度是不固定的vector可以動態(tài)增長完美匹配。高效的隨機(jī)訪問算法中需要頻繁比較磁道號、計算距離vector通過下標(biāo)[]或迭代器的隨機(jī)訪問是O(1)復(fù)雜度效率極高。強(qiáng)大的STL算法支持我們可以方便地使用std::sort,std::find,std::lower_bound等算法來對請求隊列進(jìn)行排序和查找極大簡化代碼。模擬請求隊列我們可以用一個vectorint來代表待處理的請求隊列另一個vectorint來記錄服務(wù)完成的順序清晰直觀。設(shè)計思路我們將構(gòu)建一個DiskScheduler類。它至少需要包含當(dāng)前磁頭位置、請求序列、磁道總數(shù)等屬性。成員函數(shù)則包括各個調(diào)度算法的實(shí)現(xiàn)如schedule_FCFS(),schedule_SSTF()等每個函數(shù)都返回服務(wù)順序和總尋道距離。通過vector的靈活操作插入、刪除、排序、遍歷來模擬磁頭的移動和請求的服務(wù)過程。3. 核心數(shù)據(jù)結(jié)構(gòu)與算法實(shí)現(xiàn)細(xì)節(jié)接下來我們深入到代碼層面看看如何用vector這把“瑞士軍刀”來實(shí)現(xiàn)這些算法。我會先給出核心的數(shù)據(jù)結(jié)構(gòu)設(shè)計然后逐一剖析每個算法的實(shí)現(xiàn)要點(diǎn)和易錯點(diǎn)。3.1 數(shù)據(jù)結(jié)構(gòu)定義與初始化我們首先定義一個DiskScheduler類。這里做出一個關(guān)鍵設(shè)計決策不直接在原始請求序列上操作而是使用副本。因?yàn)槊總€調(diào)度算法都會改變請求的服務(wù)順序如果直接修改原始序列那么運(yùn)行完一個算法后原始序列就被破壞了無法再給下一個算法使用。#include iostream #include vector #include algorithm // 用于sort, min_element等 #include cmath // 用于abs #include climits // 用于INT_MAX class DiskScheduler { private: int currentHead; // 當(dāng)前磁頭位置 int totalTracks; // 磁盤總磁道數(shù)用于SCAN/C-SCAN判斷邊界 std::vectorint requestSequence; // 原始請求序列 public: // 構(gòu)造函數(shù) DiskScheduler(int startPos, int tracks, const std::vectorint requests) : currentHead(startPos), totalTracks(tracks), requestSequence(requests) { // 可以添加一些基本驗(yàn)證例如請求磁道號是否在有效范圍內(nèi)[0, totalTracks-1] for (int req : requests) { if (req 0 || req tracks) { std::cerr 警告請求磁道 req 超出有效范圍 [0, tracks-1 ]。 std::endl; } } } // 各調(diào)度算法函數(shù)將在這里聲明 std::pairstd::vectorint, int schedule_FCFS(); std::pairstd::vectorint, int schedule_SSTF(); std::pairstd::vectorint, int schedule_SCAN(char direction); // direction: inward or outward std::pairstd::vectorint, int schedule_CSCAN(char direction); std::pairstd::vectorint, int schedule_LOOK(char direction); std::pairstd::vectorint, int schedule_CLOOK(char direction); };注意totalTracks參數(shù)對于SCAN/C-SCAN是必要的因?yàn)樗鼈冃枰牢锢磉吔?和totalTracks-1。對于LOOK/C-LOOK理論上可以不需要但保留它有助于程序的完整性也可以用于請求的合法性校驗(yàn)。3.2 FCFS算法實(shí)現(xiàn)簡單但重要FCFS的實(shí)現(xiàn)是最直接的它幾乎不涉及vector的復(fù)雜操作但它是我們測試和比較的基準(zhǔn)。std::pairstd::vectorint, int DiskScheduler::schedule_FCFS() { std::vectorint scheduleOrder; // 記錄服務(wù)順序 int totalSeek 0; int head currentHead; // 使用局部變量不改變成員變量 for (int req : requestSequence) { scheduleOrder.push_back(req); totalSeek std::abs(head - req); // 計算尋道距離 head req; // 移動磁頭 } return {scheduleOrder, totalSeek}; }要點(diǎn)直接遍歷原始請求序列requestSequence。std::abs()用于計算絕對距離。返回一個pair包含服務(wù)順序和總尋道距離。這樣主函數(shù)可以方便地獲取結(jié)果并打印。3.3 SSTF算法實(shí)現(xiàn)貪心的陷阱SSTF的實(shí)現(xiàn)開始有趣起來。我們需要在剩余的請求中反復(fù)尋找離當(dāng)前磁頭最近的那個。std::pairstd::vectorint, int DiskScheduler::schedule_SSTF() { std::vectorint requests requestSequence; // 關(guān)鍵使用副本 std::vectorint scheduleOrder; int totalSeek 0; int head currentHead; while (!requests.empty()) { // 使用迭代器和min_element算法找到最小距離的請求 auto closestIt std::min_element(requests.begin(), requests.end(), [head](int a, int b) { return std::abs(a - head) std::abs(b - head); }); // 處理找到的請求 int closestTrack *closestIt; scheduleOrder.push_back(closestTrack); totalSeek std::abs(head - closestTrack); head closestTrack; // 關(guān)鍵步驟從待處理列表中刪除已服務(wù)的請求 requests.erase(closestIt); } return {scheduleOrder, totalSeek}; }核心技巧與避坑指南一定要用副本std::vectorint requests requestSequence;這行代碼至關(guān)重要。否則運(yùn)行一次SSTF后原始請求序列就空了。使用std::min_element與Lambda表達(dá)式這是C STL的優(yōu)雅之處。min_element返回指向最小元素的迭代器。我們傳入一個Lambda表達(dá)式作為自定義比較器比較的標(biāo)準(zhǔn)是到當(dāng)前head的距離。這比手動寫循環(huán)遍歷找最小值更簡潔、更不易出錯。刪除元素requests.erase(closestIt)用于刪除已服務(wù)的請求。注意erase會使指向被刪除元素及其后元素的迭代器失效但因?yàn)槲覀兠看窝h(huán)都重新調(diào)用min_element從頭查找所以沒有問題。如果要在循環(huán)中復(fù)用迭代器則需要更謹(jǐn)慎的處理如it requests.erase(it)的模式。3.4 LOOK算法實(shí)現(xiàn)高效的“電梯”LOOK是SCAN的優(yōu)化也是實(shí)際中最常用的算法之一。它的實(shí)現(xiàn)比SSTF稍復(fù)雜需要處理方向和對請求序列的排序。std::pairstd::vectorint, int DiskScheduler::schedule_LOOK(char direction) { std::vectorint requests requestSequence; // 使用副本 std::vectorint scheduleOrder; int totalSeek 0; int head currentHead; // 對請求排序這是LOOK/SCAN類算法的前提 std::sort(requests.begin(), requests.end()); // 確定初始掃描方向上的請求子集 // 使用lower_bound找到第一個大于等于head的位置 auto it std::lower_bound(requests.begin(), requests.end(), head); std::vectorint left(requests.begin(), it); // 小于head的請求逆序 std::vectorint right(it, requests.end()); // 大于等于head的請求 if (direction o || direction O) { // 向外磁道號增大 // 先服務(wù)右側(cè)向外的方向 for (int track : right) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } // 掉頭服務(wù)左側(cè)需要逆序因?yàn)榇蓬^向內(nèi)移動 std::reverse(left.begin(), left.end()); for (int track : left) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } } else { // 向內(nèi)磁道號減小默認(rèn)或i // 先服務(wù)左側(cè)需要逆序因?yàn)楫?dāng)前head在右側(cè)向左移動 std::reverse(left.begin(), left.end()); for (int track : left) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } // 掉頭服務(wù)右側(cè) for (int track : right) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } } return {scheduleOrder, totalSeek}; }實(shí)現(xiàn)解析與難點(diǎn)排序std::sort(requests.begin(), requests.end())。LOOK算法需要知道請求的全局分布排序是第一步。分割請求隊列使用std::lower_bound找到第一個不小于head的請求位置。它將排序后的隊列分割成left小于head和right大于等于head兩部分。lower_bound使用二分查找效率是O(log n)。方向處理這是最容易混淆的地方。代碼中通過direction參數(shù)控制初始移動方向。向外‘o’先遍歷right從小到大然后反轉(zhuǎn)left從大到小再遍歷。因?yàn)榈纛^后磁頭是向內(nèi)移動需要服務(wù)比當(dāng)前head此時已在最右更小的磁道所以left需要逆序。向內(nèi)‘i’先反轉(zhuǎn)left從大到小并遍歷然后遍歷right從小到大。原理類似。SCAN算法的實(shí)現(xiàn)如果你需要實(shí)現(xiàn)標(biāo)準(zhǔn)的SCAN走到物理邊界只需在LOOK的基礎(chǔ)上在服務(wù)完一個方向后先讓磁頭移動到邊界0或totalTracks-1并把這部分移動距離加到totalSeek中然后再掉頭。代碼結(jié)構(gòu)類似但增加了邊界移動的邏輯。3.5 C-LOOK算法實(shí)現(xiàn)更公平的循環(huán)C-LOOK是C-SCAN的優(yōu)化版實(shí)現(xiàn)上與LOOK類似但“掉頭”的邏輯不同。std::pairstd::vectorint, int DiskScheduler::schedule_CLOOK(char direction) { std::vectorint requests requestSequence; std::vectorint scheduleOrder; int totalSeek 0; int head currentHead; std::sort(requests.begin(), requests.end()); auto it std::lower_bound(requests.begin(), requests.end(), head); std::vectorint left(requests.begin(), it); std::vectorint right(it, requests.end()); if (direction o || direction O) { // 向外掃描 for (int track : right) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } // C-LOOK關(guān)鍵點(diǎn)從最左端重新開始而不是掉頭 // 如果左側(cè)有請求磁頭需要“快速返回”到左側(cè)第一個請求 if (!left.empty()) { totalSeek std::abs(head - left.front()); // 快速返回的距離 head left.front(); for (int track : left) { // 左側(cè)請求已經(jīng)是升序直接遍歷 scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } } } else { // 向內(nèi)掃描邏輯對稱 // 注意向內(nèi)掃描時left需要逆序從大到小服務(wù) std::reverse(left.begin(), left.end()); for (int track : left) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } // 快速返回到右側(cè)第一個請求 if (!right.empty()) { totalSeek std::abs(head - right.front()); head right.front(); for (int track : right) { scheduleOrder.push_back(track); totalSeek std::abs(head - track); head track; } } } return {scheduleOrder, totalSeek}; }C-LOOK與LOOK的核心區(qū)別LOOK服務(wù)完一個方向后掉頭反向服務(wù)。C-LOOK服務(wù)完一個方向后直接跳到另一個方向的起始端快速返回然后繼續(xù)同方向掃描。在代碼中體現(xiàn)為服務(wù)完right后不是反轉(zhuǎn)left而是直接跳到left.front()然后順序服務(wù)left。這保證了所有請求的等待時間相對更公平。4. 完整模擬程序與測試案例分析有了核心算法函數(shù)我們需要一個主程序來驅(qū)動測試并直觀地展示不同算法的效果。我們將設(shè)計一個交互性較強(qiáng)的控制臺程序。4.1 主程序框架與交互設(shè)計#include iomanip // 用于格式化輸出 void printSchedule(const std::string algoName, const std::pairstd::vectorint, int result) { std::cout \n algoName 調(diào)度結(jié)果 std::endl; std::cout 服務(wù)順序: ; for (size_t i 0; i result.first.size(); i) { std::cout result.first[i]; if (i ! result.first.size() - 1) std::cout - ; } std::cout \n總尋道距離: result.second std::endl; std::cout 平均尋道長度: std::fixed std::setprecision(2) static_castdouble(result.second) / result.first.size() std::endl; } int main() { // 模擬參數(shù)設(shè)置 int startHead 100; int totalTracks 200; // 假設(shè)磁道號0-199 std::vectorint requests {55, 58, 39, 18, 90, 160, 150, 38, 184}; DiskScheduler scheduler(startHead, totalTracks, requests); std::cout 初始磁頭位置: startHead std::endl; std::cout 請求序列: ; for (int r : requests) std::cout r ; std::cout std::endl; // 測試不同算法 auto fcfsResult scheduler.schedule_FCFS(); printSchedule(FCFS, fcfsResult); auto sstfResult scheduler.schedule_SSTF(); printSchedule(SSTF, sstfResult); // LOOK算法可以測試不同方向 auto lookOutResult scheduler.schedule_LOOK(o); printSchedule(LOOK (向外), lookOutResult); auto lookInResult scheduler.schedule_LOOK(i); printSchedule(LOOK (向內(nèi)), lookInResult); auto clookResult scheduler.schedule_CLOOK(o); printSchedule(C-LOOK (向外), clookResult); return 0; }4.2 測試案例深度解析讓我們用上面的請求序列{55, 58, 39, 18, 90, 160, 150, 38, 184}磁頭起始于100號磁道來分析一下。FCFS結(jié)果 服務(wù)順序55 - 58 - 39 - 18 - 90 - 160 - 150 - 38 - 184 總尋道距離 |100-55||55-58||58-39||39-18||18-90||90-160||160-150||150-38||38-184| 4531921727010112146 498可以看到磁頭來回劇烈擺動從100跳到55向內(nèi)又跳到58向外再跳回39向內(nèi)……效率很低。SSTF結(jié)果從100開始最近的是90距離10服務(wù)90。從90開始最近的是58距離32但58和55都距離32這里就涉及min_element在距離相等時的選擇它會選擇第一個遇到的取決于vector的順序。假設(shè)先找到58服務(wù)58。從58開始最近的是55距離3服務(wù)55。從55開始最近的是39距離16但39和38呢同樣問題。假設(shè)先服務(wù)39。以此類推……最終順序可能是90, 58, 55, 39, 38, 18, 150, 160, 184。 總尋道距離會遠(yuǎn)小于FCFS可能約在200-250之間。但注意如果請求18一直離得很遠(yuǎn)而90、58、55附近不斷有新請求18可能被“餓死”。LOOK (向外) 結(jié)果排序后請求: [18, 38, 39, 55, 58, 90, 150, 160, 184]當(dāng)前head100lower_bound找到right[150, 160, 184]100left[18,38,39,55,58,90]100。向外掃描服務(wù)150, 160, 184。掉頭此時head184反轉(zhuǎn)left得到[90, 58, 55, 39, 38, 18]服務(wù)它們。 服務(wù)順序150 - 160 - 184 - 90 - 58 - 55 - 39 - 38 - 18 總尋道距離 (100-150)(150-160)(160-184)(184-90)(90-58)(58-55)(55-39)(39-38)(38-18) 5010249432316120 250這個距離比FCFS好很多并且沒有饑餓問題。C-LOOK (向外) 結(jié)果同LOOK先服務(wù)right: 150, 160, 184?？焖俜祷貜?84直接跳到left的第一個元素90。距離184-9094。然后順序服務(wù)left: 90, 58, 55, 39, 38, 18。 服務(wù)順序150 - 160 - 184 - 90 - 58 - 55 - 39 - 38 - 18 順序看起來和LOOK一樣注意雖然順序一樣但尋道距離的計算不同。在服務(wù)完184后LOOK是掉頭移動到90距離94而C-LOOK是“快速返回”到90距離也是94。在這個特定序列下兩者總距離巧合相同。但如果left的第一個請求不是90而是18那么LOOK掉頭需要從184走到18距離很大而C-LOOK快速返回的距離是184到18和LOOK一樣。但C-LOOK的設(shè)計哲學(xué)是單向循環(huán)對所有請求的響應(yīng)時間方差更小。通過這個對比你可以清晰地看到不同算法在同一組數(shù)據(jù)下的表現(xiàn)差異。動手修改請求序列和起始位置觀察結(jié)果的變化是理解這些算法行為的最佳方式。5. 性能考量、擴(kuò)展性與常見問題在實(shí)現(xiàn)基礎(chǔ)功能后我們可以從工程和優(yōu)化的角度思考更多。5.1 時間復(fù)雜度分析FCFS: O(n)只需一次遍歷。SSTF: O(n2)。因?yàn)槊看畏?wù)一個請求都需要在剩余列表中線性搜索min_element是O(k)k為剩余請求數(shù)最近的那個。對于n個請求總復(fù)雜度是n(n-1)...1 O(n2)。這是SSTF的一個缺點(diǎn)當(dāng)請求隊列很長時調(diào)度器本身的計算開銷會變大?？梢允褂脙?yōu)先隊列如std::priority_queue進(jìn)行優(yōu)化將查找最近請求的復(fù)雜度降到O(log n)總體復(fù)雜度降至O(n log n)。LOOK/C-LOOK/SCAN/C-SCAN: O(n log n)。主要開銷在于初始的排序std::sort其平均復(fù)雜度為O(n log n)。之后的掃描過程是線性的O(n)。因此對于請求數(shù)較多的情況這些算法的預(yù)處理開銷是值得的因?yàn)樗鼈兡芴峁└€(wěn)定、更優(yōu)的整體性能。5.2 如何模擬動態(tài)請求到達(dá)我們的實(shí)現(xiàn)是靜態(tài)的即所有請求一開始就已知。但在真實(shí)操作系統(tǒng)中請求是動態(tài)到達(dá)的。如何模擬一個簡單的思路是引入“時間”概念。我們可以維護(hù)一個“當(dāng)前時間”每個請求有一個“到達(dá)時間”。調(diào)度器在每個時刻只從“已到達(dá)”的請求中進(jìn)行調(diào)度。這需要更復(fù)雜的事件驅(qū)動模擬但核心的調(diào)度算法邏輯不變只是每次調(diào)度的候選集是“已到達(dá)且未服務(wù)”的請求子集。5.3 常見問題與調(diào)試技巧請求磁道號越界在構(gòu)造函數(shù)或添加請求時務(wù)必檢查磁道號是否在[0, totalTracks-1]范圍內(nèi)。否則在計算距離或判斷方向時可能出現(xiàn)邏輯錯誤?？照埱笮蛄刑幚砣绻鹯equestSequence為空你的算法函數(shù)應(yīng)該能優(yōu)雅處理返回空的服務(wù)順序和0尋道距離。在SSTF的while循環(huán)和LOOK的lower_bound前添加空判斷是個好習(xí)慣。方向參數(shù)校驗(yàn)schedule_LOOK和schedule_CSCAN中的direction參數(shù)應(yīng)該只接受有效的字符如‘i’, ‘I’, ‘o’, ‘O’并為無效輸入提供默認(rèn)值或錯誤提示。迭代器失效在SSTF中我們在循環(huán)內(nèi)調(diào)用了requests.erase(closestIt)。正如之前提到的這會使closestIt失效。因?yàn)槲覀兠看窝h(huán)都重新計算closestIt所以安全。但如果想優(yōu)化在刪除后使用erase返回的新的迭代器作為下一輪查找的起點(diǎn)需要小心處理邊界條件。浮點(diǎn)數(shù)比較計算平均尋道長度時注意整數(shù)除法會截斷小數(shù)。務(wù)必先轉(zhuǎn)換為double再相除并使用std::setprecision控制輸出精度?？梢暬{(diào)試對于復(fù)雜的序列在紙上畫出磁道軸手動模擬一遍算法的步驟再與程序輸出對比是排查邏輯錯誤最有效的方法。也可以在每個算法內(nèi)部添加一些調(diào)試輸出打印出每一步磁頭的位置和選擇的請求。5.4 項目擴(kuò)展方向這個基礎(chǔ)模擬器可以作為一個起點(diǎn)進(jìn)行很多有意義的擴(kuò)展實(shí)現(xiàn)更多算法如N-Step-SCAN將請求隊列分成長度為N的子隊列每個子隊列內(nèi)用SCAN、F-SCAN在掃描期間凍結(jié)新到的請求等本次掃描完再處理等。圖形化界面使用如Qt、SFML或簡單的Web前端Emscripten編譯到WebAssembly將調(diào)度過程動畫展示出來磁頭移動、請求服務(wù)過程一目了然。性能對比與統(tǒng)計分析自動生成大量隨機(jī)請求序列批量運(yùn)行所有算法統(tǒng)計平均尋道距離、平均響應(yīng)時間、標(biāo)準(zhǔn)差等指標(biāo)用圖表如控制臺打印表格或生成CSV文件直觀對比。集成到簡單OS模擬器中將這個磁盤調(diào)度模塊作為你編寫的簡易操作系統(tǒng)課程設(shè)計項目的一部分模擬進(jìn)程發(fā)出I/O請求并被調(diào)度的完整過程。通過這個從零實(shí)現(xiàn)磁盤調(diào)度算法的項目你收獲的遠(yuǎn)不止是幾個C函數(shù)。你深入理解了操作系統(tǒng)核心組件的工作原理掌握了用恰當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)vector實(shí)現(xiàn)復(fù)雜算法的方法并鍛煉了將理論轉(zhuǎn)化為實(shí)踐的能力。下次當(dāng)你聽到“電梯算法”或“磁盤調(diào)度”時你腦海中浮現(xiàn)的將不再是枯燥的定義而是一行行自己寫過的、讓磁頭高效移動的代碼。這才是真正意義上的“學(xué)會”。