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