C（C++）操作系统磁盘调度算法

1.种类：
在操作系统中基本的调度算法包括以下4类：
（1）先来先服务算法（FCFS）
FCFS顾名思义就是：按照作业提交或进程变为就绪状态的先后次序，分派CPU； 当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式），这是最简单的磁盘调度算法。总结成一句话就是：先来的先执行。
特点：比较有利于长作业，而不利于短作业。 有利于CPU繁忙的作业，而不利于I/O繁忙的作业。
（2）最短查找（寻道）时间优先算法（SSTF）
SSTF：考虑I/O请求之间的区别，总是先执行查找时间最短的请求，与FCFS算法相比有较好的寻道功能。简单来说就是每次总是寻找离当前磁头相差最小的执行。
特点：改善了磁盘平均服务时间，但造成某些访问请求长期等待得不到服务。
（3）电梯调度算法/扫描算法（SCAN）
SCAN：移动臂每次沿一个方向移动，扫过所有柱面，遇到最近的I/O请求便进行处理，直至到达最后一个柱面后再向相反的方向移动回来。

特点：克服了最短寻道优先的缺点，既考虑了距离，同时又考虑了方向。
（4）循环扫描算法（CSCAN）
CSCAN：他的思想是，访问完最里边一个要求服务的序列之后，从最外层的序号楷书往里走，即始终保持一个方向。
2.代码实现：
在这里四个算法都使用Print()函数输出，SSTF、SCAN、SCAN都依赖于FCFS算法。即对上述三个算法做相应的变换使其利用FCFS的方式输出。

• 输出函数Print()
  此函数有三个参数，第一个数组arr[]中存储着所有等待的柱面号，trackNumber代表当前磁头所在的位置，m是等待着的柱面号的个数。依次遍历将移动的距离累加在sum中。

void Print(int arr[maxsize],int trackNumber,int m){
    int i,j,sum=0;

     cout<<"移动次序\t"<<"当前柱面号\t"<<"下一个柱面号\t"<<"移动距离\t"<<"已移动距离"<<endl;
     for(i=0;i<m;i++){
        if(i==0){
                sum+=abs(arr[i]-trackNumber);
            cout<<i+1<<"  \t\t"<<trackNumber<<"  \t\t"<<arr[i]<<"  \t\t"<<abs(arr[i]-trackNumber)<<"  \t\t"<<sum<<endl;

        }

        else{ sum+=abs(arr[i]-arr[i-1]);
            cout<<i+1<<"  \t\t"<<arr[i-1]<<"  \t\t"<<arr[i]<<"  \t\t"<<abs(arr[i]-arr[i-1])<<"  \t\t"<<sum<<endl;

        }

     }

     cout<<"移动总柱面数为："<<sum<<endl;
}

• 先来先服务算法（FCFS）
  基本思想： 因为FCFS本就是按照作业的提交次序执行的所以只需调用Print()函数即可：
  代码：

 void FCFS(int arr[maxsize],int trackNumber,int m)
{
	 Print(arr,trackNumber,m);
}

• 最短查找（寻道）时间优先算法（SSTF）
  基本思想：SSTF即考虑I/O请求之间的区别，总是先执行查找时间最短的请求。第一个数组a[]中存储着所有等待的柱面号，now代表当前磁头所在的位置，n是等待着的柱面号的个数。依次对数组a进行遍历，每次将与当前磁头距离最近的存在数组next[]中，此时的next中就是SSTF的执行次序，然后调用Print()函数依次输出。
  代码：

void SSTF(int a[],int n,int now){
	int i,min,k=0,first=now;
	int flag;//最短路径的下标
	int t=n;
	int next[maxsize],length[maxsize];
	int visit[maxsize]={0};//访问数组，已经访问过的为1
	//寻道n次
	while(t--){
		min=999999;
		//找没有访问过的中最近的
		for(i=0;i<n;i++){
			if(visit[i])
				continue;
			if(abs(a[i]-now)<min){
				flag=i;
				min=abs(a[i]-now);
			}
		}
		length[k]=min;//移动的距离
		next[k++]=a[flag];//下一个被访问的磁道号
		visit[flag]=1;//访问过的置1
		now=a[flag];//磁道移动到当前位置
	}
	Print(next,first,n);

}

• 电梯调度算法/扫描算法（SCAN）
  基本思想：此算法中的参数与上边相同，但有一点不同的是电梯调度算法区分方向。此算法的原理是先选择是往大（小）的方向移动，之后将arr[]数组中的磁道分为两部分即以现在的磁头为准则将大于它的存在一个数组中，将小于它的存在一个数组中，并用函数 BubbleSort1和 BubbleSort2对其排序。如果选择往大（小）的方向移动即比现在磁头所在柱面大的那个数组按从小到大（从大到小）的顺序排列，比它小的按从大到小（从小到大）的顺序排列。则它的执行次序就是：比它他大的那个数组+比它小的那个数组（比它他小的那个数组+比它大的那个数组）。然后调用Print()函数输出即可。
  代码：

void BubbleSort1(int *arr,int sz){
    int i = 0;
    int j = 0;

    for(i=0;i<sz-1;i++){
        for(j=0;j<sz-i-1;j++){
            if(arr[j]>arr[j+1]){
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

void BubbleSort2(int *arr,int sz){
    int i = 0;
    int j = 0;

    for(i=0;i<sz-1;i++){
        for(j=0;j<sz-i-1;j++){
            if(arr[j]<arr[j+1]){
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

void SCAN(int arr[],int number,int n){/*电梯调度算法（扫描算法）*/
    int count=0;
    int sum1=0,sum2=0;
    for(int i=0;i<n;i++){
        if(arr[i]>number)
            count++;
    }
    int arr1[count],arr2[n-count];
    int i1=0,i2=0;
    for(int i=0;i<n;i++){
        if(arr[i]>number){
            arr1[i1]=arr[i];
            i1++;
        }
        else{
            arr2[i2]=arr[i];
            i2++;
        }
    }

    cout<<"请选择1：往大的方向移动"<<endl;
    cout<<"请选择2：往小的方向移动"<<endl;
    int p;
    cin>>p;
    if(p==1){
             BubbleSort1(arr1,count);
        BubbleSort2(arr2,n-count);
        int ele_arr1[n];
        for(int i=0;i<n;i++){
            if(i<count)
                ele_arr1[i]=arr1[i];
            else
                ele_arr1[i]=arr2[i-count];
        }
        Print(ele_arr1,number,n);
    }
        else if(p==2){
                 BubbleSort1(arr1,count);
            BubbleSort2(arr2,n-count);
            int ele_arr2[n];
        for(int i=0;i<n;i++){
            if(i<n-count)
                ele_arr2[i]=arr2[i];
            else
                ele_arr2[i]=arr1[i-(n-count)];
        }
        Print(ele_arr2,number,n);
        }
        else
            cout<<"输入错误！"<<endl;
}

• 循环扫描算法（CSCAN）
  基本思想：CSCAN的具体思想和SCAN类似，只是它执行时必须到“头”，即多了一个最大柱面号。

代码：

void CSCAN(int arr[],int number,int n,int maxnumber){/*循环扫描算法*/
    int count=0;
    int sum=1;
    for(int i=0;i<n;i++){
        if(arr[i]>number)
            count++;
    }
    int arr1[count],arr2[n-count];
    int i1=0,i2=0;
    for(int i=0;i<n;i++){
        if(arr[i]>number){
            arr1[i1]=arr[i];
            i1++;
        }
        else{
            arr2[i2]=arr[i];
            i2++;
        }
    }
    int sum1=0,sum2=0;
      cout<<"请选择1：往大的方向移动"<<endl;
    cout<<"请选择2：往小的方向移动"<<endl;
    int p;
    cin>>p;
    if(p==1){
             BubbleSort1(arr1,count);
        BubbleSort1(arr2,n-count);
        int scf_arr1[n+1];
        for(int i=0;i<n+1;i++){
            if(i<count)
                scf_arr1[i]=arr1[i];
            else if(i==count)
                scf_arr1[i]=maxnumber;
            else
                scf_arr1[i]=arr2[i-count-1];
        }
        Print(scf_arr1,number,n+1);

    }
    else if(p==2){
         BubbleSort2(arr1,count);
    BubbleSort2(arr2,n-count);
     int scf_arr2[n+1];
        for(int i=0;i<=n;i++){
            if(i<n-count)
                scf_arr2[i]=arr2[i];
            else if(i==n-count)
                scf_arr2[i]=maxnumber;
            else
                scf_arr2[i]=arr1[i-(n-count)-1];
        }
        Print(scf_arr2,number,n+1);
    }
    else
        cout<<"错误！"<<endl;

}

整体代码如下：

#include <iostream>
#include<bits/stdc++.h>
#include<malloc.h>
#include<stdio.h>
#include<cstdlib>
#define maxsize 200
using namespace std;

void Print(int arr[maxsize],int trackNumber,int m){
    int i,j,sum=0;

     cout<<"移动次序\t"<<"当前柱面号\t"<<"下一个柱面号\t"<<"移动距离\t"<<"已移动距离"<<endl;
     for(i=0;i<m;i++){
        if(i==0){
                sum+=abs(arr[i]-trackNumber);
            cout<<i+1<<"  \t\t"<<trackNumber<<"  \t\t"<<arr[i]<<"  \t\t"<<abs(arr[i]-trackNumber)<<"  \t\t"<<sum<<endl;

        }

        else{ sum+=abs(arr[i]-arr[i-1]);
            cout<<i+1<<"  \t\t"<<arr[i-1]<<"  \t\t"<<arr[i]<<"  \t\t"<<abs(arr[i]-arr[i-1])<<"  \t\t"<<sum<<endl;

        }

     }

     cout<<"移动总柱面数为："<<sum<<endl;
}
/*先来先服务*/
void FCFS(int arr[maxsize],int trackNumber,int m)
{Print(arr,trackNumber,m);}


//最短寻道时间优先算法
void SSTF(int a[],int n,int now){
	int i,min,k=0,first=now;
	int flag;//最短路径的下标
	int t=n;
	int next[maxsize],length[maxsize];
	int visit[maxsize]={0};//访问数组，已经访问过的为1
	//寻道n次
	while(t--){
		min=999999;
		//找没有访问过的中最近的
		for(i=0;i<n;i++){
			if(visit[i])
				continue;
			if(abs(a[i]-now)<min){
				flag=i;
				min=abs(a[i]-now);
			}
		}
		length[k]=min;//移动的距离
		next[k++]=a[flag];//下一个被访问的磁道号
		visit[flag]=1;//访问过的置1
		now=a[flag];//磁道移动到当前位置
	}
	Print(next,first,n);

}

void BubbleSort1(int *arr,int sz){
    int i = 0;
    int j = 0;

    for(i=0;i<sz-1;i++){
        for(j=0;j<sz-i-1;j++){
            if(arr[j]>arr[j+1]){
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}
void BubbleSort2(int *arr,int sz){
    int i = 0;
    int j = 0;

    for(i=0;i<sz-1;i++){
        for(j=0;j<sz-i-1;j++){
            if(arr[j]<arr[j+1]){
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}
void SCAN(int arr[],int number,int n){/*电梯调度算法（扫描算法）*/
    int count=0;
    int sum1=0,sum2=0;
    for(int i=0;i<n;i++){
        if(arr[i]>number)
            count++;
    }
    int arr1[count],arr2[n-count];
    int i1=0,i2=0;
    for(int i=0;i<n;i++){
        if(arr[i]>number){
            arr1[i1]=arr[i];
            i1++;
        }
        else{
            arr2[i2]=arr[i];
            i2++;
        }
    }

    cout<<"请选择1：往大的方向移动"<<endl;
    cout<<"请选择2：往小的方向移动"<<endl;
    int p;
    cin>>p;
    if(p==1){
             BubbleSort1(arr1,count);
        BubbleSort2(arr2,n-count);
        int ele_arr1[n];
        for(int i=0;i<n;i++){
            if(i<count)
                ele_arr1[i]=arr1[i];
            else
                ele_arr1[i]=arr2[i-count];
        }
        Print(ele_arr1,number,n);
    }
        else if(p==2){
                 BubbleSort1(arr1,count);
            BubbleSort2(arr2,n-count);
            int ele_arr2[n];
        for(int i=0;i<n;i++){
            if(i<n-count)
                ele_arr2[i]=arr2[i];
            else
                ele_arr2[i]=arr1[i-(n-count)];
        }
        Print(ele_arr2,number,n);
        }
        else
            cout<<"输入错误！"<<endl;
}

void CSCAN(int arr[],int number,int n,int maxnumber){/*循环扫描算法*/
    int count=0;
    int sum=1;
    for(int i=0;i<n;i++){
        if(arr[i]>number)
            count++;
    }
    int arr1[count],arr2[n-count];
    int i1=0,i2=0;
    for(int i=0;i<n;i++){
        if(arr[i]>number){
            arr1[i1]=arr[i];
            i1++;
        }
        else{
            arr2[i2]=arr[i];
            i2++;
        }
    }
    int sum1=0,sum2=0;
      cout<<"请选择1：往大的方向移动"<<endl;
    cout<<"请选择2：往小的方向移动"<<endl;
    int p;
    cin>>p;
    if(p==1){
             BubbleSort1(arr1,count);
        BubbleSort1(arr2,n-count);
        int scf_arr1[n+1];
        for(int i=0;i<n+1;i++){
            if(i<count)
                scf_arr1[i]=arr1[i];
            else if(i==count)
                scf_arr1[i]=maxnumber;
            else
                scf_arr1[i]=arr2[i-count-1];
        }
        Print(scf_arr1,number,n+1);

    }
    else if(p==2){
         BubbleSort2(arr1,count);
    BubbleSort2(arr2,n-count);
     int scf_arr2[n+1];
        for(int i=0;i<=n;i++){
            if(i<n-count)
                scf_arr2[i]=arr2[i];
            else if(i==n-count)
                scf_arr2[i]=maxnumber;
            else
                scf_arr2[i]=arr1[i-(n-count)-1];
        }
        Print(scf_arr2,number,n+1);
    }
    else
        cout<<"错误！"<<endl;

}
int main()
{
    int n,number,choice,maxnumber,i;
    int brr[maxsize];
    cout<<"请输入等待访问的磁道的个数:"<<endl;
    cin>>n;
    int a[n];
    cout<<"请依次输入等待的"<<n<<"个柱面号："<<endl;
    for(int i=0;i<n;i++)
    cin>>a[i];
    cout<<"请输入当前磁头位置："<<endl;
    cin>>number;
    cout<<"***********************菜单***********************"<<endl;
     cout<<"*"<<"\t\t\t\t\t\t "<<"*"<<endl;
      cout<<"*"<<"\t\t\t\t\t\t "<<"*"<<endl;
      cout<<"*"<<"\t\t"<<"1.先来先服务算法"<<"\t\t "<<"*"<<endl;
      cout<<"*"<<"\t\t"<<"2.最短作业优先算法"<<"\t\t "<<"*"<<endl;
    cout<<"*"<<"\t\t"<<"3.电梯调度算法"<<"\t\t\t "<<"*"<<endl;
    cout<<"*"<<"\t\t"<<"4.循环扫描算法"<<"\t\t\t "<<"*"<<endl;
     cout<<"*"<<"\t\t"<<"5.退出"<<"\t\t\t\t "<<"*"<<endl;
    cout<<"*"<<"\t\t\t\t\t\t "<<"*"<<endl;
     cout<<"*"<<"\t\t\t\t\t\t "<<"*"<<endl;
      cout<<"*"<<"************************************************"<<"*"<<endl;
      while(true){
      cout<<"请选择要执行的算法"<<endl;
      cin>>choice;
      switch(choice){
        case 1:FCFS(a,number,n);break;
        case 2:SSTF(a,n,number);
                break;
        case 3:SCAN(a,number,n);break;
        case 4:cout<<"请输入最大磁头号："<<endl;
                cin>>maxnumber;
                CSCAN(a,number,n,maxnumber);break;
        case 5:exit(0);
      }
      }
    return 0;
}