OS-ディスクスケジューリングアルゴリズム

じっけん7ディスクスケジューリングアルゴリズム
ディスクスケジューリングは、マルチプログラム設計のコンピュータシステムでは、各プロセスがディスクの読み取り/書き込み操作の要求を絶えず提出する可能性があります.これらのプロセスの送信要求の速度がディスク応答よりも速い場合があるため、ディスクデバイスごとに待機キューを作成する必要があります.一般的なディスクスケジューリングアルゴリズムには、次の4つがあります.
先来先サービスアルゴリズム(FCFS)
最短シーク時間優先アルゴリズム(SSTF)
スキャンアルゴリズム(SCAN)
循環走査アルゴリズム(CSCAN)
例:あるディスクに200個の柱面があると仮定し、番号は0-199であり、143号柱面にアクセスするリクエスト者にサービスを提供した後、現在125号柱面にアクセスするリクエストサービスを提供していると同時に、いくつかのリクエスト者がサービスを待っていて、それらが毎回アクセスする柱面番号は86147、91177、94150102175130、先着順サービスアルゴリズム(FCFS)First Come First Service
これは比較的簡単なディスクスケジューリングアルゴリズムです.プロセス要求に従ってディスクにアクセスする順序でスケジュールされます.このアルゴリズムの利点は、公平で簡単であり、各プロセスのリクエストが順次処理され、あるプロセスのリクエストが長期にわたって満たされないことはありません.このアルゴリズムは、トラッキングを最適化していないため、ディスクへのアクセス要求が比較的多い場合、デバイス・サービスのスループットを低下させ、平均トラッキング時間が長くなる可能性がありますが、各プロセスがサービスを得る応答時間の変化幅は小さいです.
先着順サービス(125)86.147.91.177.94.150.22.175.130
2、最短シーク時間優先アルゴリズム(SSTF)Shortest Seek Time First
このアルゴリズムは、アクセスされたトラックが現在のヘッドが存在するトラックから最も近い距離にあることを要求し、各トラックの探索時間を最も短くするプロセスを選択し、このアルゴリズムは比較的良好なスループットを得ることができるが、平均トラック探索時間が最も短いことを保証することはできない.その欠点は、ユーザのサービス要求に対する応答機会が均等ではないため、応答時間の変化幅が大きいことである.サービス要求が多い場合、内外エッジトラックに対する要求は無期限に遅延され、一部の要求の応答時間は予想できない.
最短シーク時間優先(125)130.147.150.175.177.102.94.91.86
3、スキャンアルゴリズム(SCAN)エレベーターのスケジューリング
走査アルゴリズムは,アクセスしたいトラックと現在のトラックとの距離だけでなく,ヘッドの現在の移動方向をより優先的に考慮した.たとえば、ヘッドが内側から外側に移動している場合、スキャンアルゴリズムによって選択された次のアクセスオブジェクトは、現在のトラックの外にあり、最も近いトラックであるべきである.このように内側から外側へのアクセスは、より外側のトラックがアクセスする必要がなくなるまで、アームを外側から内側へ移動します.この場合も,アクセスするトラックが現在のトラック内にあり,飢餓現象の発生を回避するプロセスを選択するたびにスケジューリングされる.このアルゴリズムでは、磁気ヘッドの移動の法則がエレベータの運転に似ているため、エレベータスケジューリングアルゴリズムとも呼ばれる.このアルゴリズムは,最短チャネル時間優先アルゴリズムのサービスが中間トラックと応答時間の変化が比較的大きいという欠点を基本的に克服し,最短チャネル時間優先アルゴリズムの利点,すなわちスループットが大きく,平均応答時間が小さいが,揺動式の走査法であるため,両側トラックがアクセスされる周波数は依然として中間トラックより低い.
エレベータスケジューリング(125)102.94.91.86.130.1147.150.1175.177
4.循環スキャンアルゴリズム(CSCAN)
サイクルスキャンアルゴリズムはスキャンアルゴリズムの改良である.トラックへのアクセス要求が均一に分散されている場合、磁気ヘッドがディスクの一端に到達し、逆方向に移動すると、磁気ヘッドの後に落ちるアクセス要求は比較的少ない.これは、これらのトラックが処理されたばかりであり、ディスクの他端の要求密度がかなり高く、これらのアクセス要求の待ち時間が長いためであり、この場合を解決するために、サイクルスキャンアルゴリズムは、ヘッドの一方向移動を規定する.例えば、内側から外側へのみ移動し、磁気ヘッドが最も外側のアクセスされたトラックに移動すると、磁気ヘッドは直ちに最も内側のアクセスしようとするトラックに戻り、最小トラック番号が最大トラック番号に続いてサイクルを構成し、走査を行う.
サイクルスキャン(125)130.147.1150.175.177.86.94.102
5、平均トラック距離
現在の磁気ヘッドが67番であると仮定すると、98,25,63,97,56,51,55,55,55,6の順でアクセスする必要がある.
FIFOアルゴリズムのサービスシーケンスは,98,25,63,97,56,51,55,55,6である.
ヘッド移動の総距離distance=
(98-67)+(98-25)+(63-25)+(97-63)+(97-56)+(56-51)+(55-51)+(55-55)+(55-6)
SSTFアルゴリズムのサービスシーケンスは,63,56,55,55,51,25,6,97,98である.
ヘッド移動の総距離distance=
(67-63)+(63-56)+(56-55)+(55-55)+(55-51)+(51-25)+(25-6)+(97-6)+(98-97)
SCANアルゴリズムのサービスシーケンスは63,56,55,55,51,25,6,97,98である.
ヘッド移動の総距離distance=
(67-63)+(63-56)+(56-55)+(55-55)+(55-51)+(51-25)+(25-6)+(97-6)+(98-97)
ここで例を挙げるのはよくないことを発見して、SSTFとSCANアルゴリズムのサービスシーケンスは意外にも同じで、
ああ!
CSCANアルゴリズムのサービスシーケンスは,63,56,55,55,51,25,6,98,97である.
ヘッド移動の総距離distance=
(67-63)+(63-56)+(56-55)+(55-55)+(55-51)+(51-25)+(25-6)+(100-98)+(98-97)
6、参照コード

#include  
#include  
#include  
using namespace std; 
typedef vector vInt; //  ，    
struct OrderItem 
{ 
    int Data; 
    bool IsVisited; 
}; 
typedef vector Order; 
Order InitOrder; 
vInt TrackOrder; 
vInt MoveDistance; 
double AverageDistance;

void InitDate(int &num);
inline void Init(int disk); //    （                   ）
void FCFS(int disk); 
void SSTF(int disk); 
void SCAN(int disk); 
void CSCAN(int disk); 
void Show(int disk);

int main() 
{ 
    int num; 
    InitDate(num); 
    char cmd; 
    do 
    { 
        cout<>type; 
        switch(type) 
        {   
case 1:FCFS(num);break; 
            case 2:SSTF(num);break; 
            case 3:SCAN(num);break; 
            case 4:CSCAN(num);break; 
        } 
        Show(num); 
        cout<>cmd; 
    }while(cmd!='n'); 
    return 0; 
}

inline void Init(int disk) 
{ 
    TrackOrder.clear(); 
    MoveDistance.clear(); 
    for(int i = 0; i < disk; i++) 
    { 
        InitOrder[i].IsVisited = false; 
    } 
}

void InitDate(int &num) 
{ 
    //ifstream cin("data.txt"); 
    cout<>num; 
    cout<>oi.Data; 
        oi.IsVisited = false; 
        InitOrder.push_back(oi); 
    } 
}

void FCFS(int disk) 
{ 
    cout<>start; 
    cout<0?t:-t); 
        InitOrder[i].IsVisited = true; 
        p = InitOrder[i].Data; 
     } 
}

void SSTF(int disk) 
{ 
    cout<>start; 
    cout<0? 
                p-InitOrder[j].Data:-(p-InitOrder[j].Data); 
                if(dif==0||temp>start; 
    cout<>dir; 
    cout<InitOrder[i].Data) 
            min = InitOrder[i].Data; 
    } 
    int p = start; 
    for(int k = 0; k< disk; k++) 
    { 
        int temp = 0; 
        for(int j = 0 ; j < disk; j++) 
        { 
            
if(cdir==0&&p>InitOrder[j].Data||cdir==1&&p0? 
                p-InitOrder[j].Data:-(p-InitOrder[j].Data); 
                if(dif==0||temp>start; 
    cout<>dir; 
    cout<InitOrder[i].Data) 
        { 
            min = InitOrder[i].Data; 
            mmin=i; 
        } 
    } 
    int p = start;//p            
    for(int k = 0; k < disk; k++) 
    { 
        int temp = 0; 
        for(int j = 0 ; j < disk; j++)//            
        { 
            
if(dir==0&&p>InitOrder[j].Data||dir==1&&p0? 
                (p-InitOrder[j].Data):(InitOrder[j].Data-p); 
                if(dif==-1||temp=0? 
                p-TrackOrder[mmin]:TrackOrder[mmin]-p); 
            curp = mmin; 
        } 
        
if(dir==1&&InitOrder[curp].Data==min&&InitOrder[mmax].IsVisited==false) 
        { 
            TrackOrder.push_back(max); 
            InitOrder[mmax].IsVisited = true; 
            MoveDistance.push_back(p-TrackOrder[mmin]>=0? 
                p-TrackOrder[mmin]:TrackOrder[mmin]-p); 
            curp = mmax; 
        } 
        p = InitOrder[curp].Data; 
        dif = -1; 
    } 
}

void Show(int disk) 
{ 
    cout<