【操作系统】磁盘调度算法（FCFS、SSTF、SCAN 和 C-LOOK 调度策略）

Lab Week 18 实验报告

实验内容：硬盘调度

• 编写一个 C 程序模拟实现课件 Lecture25 中的硬盘磁头调度算法，包括
  • FCFS、SSTF、SCAN 和 C-LOOK 调度策略。
  • 固定一个硬盘柱面数；
  • 输入一批随机的硬盘柱面请求序列，计算各个调度策略下的磁头移动平均总距离 (假设磁头运动是理想匀速的，可以把移动距离看作是移动时间，将总时间除以请求数得到平均响应时间)。
• 分析上述实验结果。

I. 硬盘磁头调度算法

由于内存通常太小而且不能永久保存所有数据和程序，因此计算机系统必须提供外存来备份内存。现代计算机系统采用磁盘（硬盘）作为信息（程序与数据）的主要在线存储介质。换句话说，硬盘或磁盘为现代计算机系统提供大量外存。

磁盘是表面涂有磁性物质的物理盘片，通过磁头（导体线圈）从磁盘存取数据，在读/写期间，磁头固定，磁盘在下面高速旋转。磁盘盘面上的数据存储在一组同心圆中，称为磁道。每个磁道和磁头一样宽，一个盘面上有上千个磁道。磁道又分为几百个扇区，每个扇区固定存储大小，因此越往内的扇区密度越高。

磁盘地址由（柱面号，盘面号，扇区号）表示。

操作系统的职责之一是有效使用硬件。对于磁盘驱动器，满足这个要求具有较快的访问速度和较宽的磁盘带宽。

对于磁盘，访问时间包括两个主要部分：

• 寻道时间：是磁臂移动磁头到包含目标扇区的柱面的时间；
• 旋转延迟：是磁盘旋转目标扇区到磁头下的额外时间；

在这部分，我们针对寻道时间来进行优化，通过不同的磁头调度算法，分析优化的情况。

1. 先来先服务（First Come First Served, FCFS）算法

FCFS算法根据进程请求访问磁盘的先后顺序进行调度，这是最简单的磁盘调度算法，虽然这种算法比较公平，但是它通常并不提供最快的服务。

实现代码：

//设置磁道请求
void set_request(int *cylinders, int *request, int req_num){
    for(int i = 0; i < req_num; i++){
        int req_id = request[i];
        cylinders[req_id]++; //对应的磁道请求数加1
    }
}
1
2
3
4
5
6
7

代码说明：

该函数对磁道表cylinders的请求进行设置，如果该磁道存在请求，那么将其对应的表项值加一，以此类推；

void FCFS(int head, int *request, int *cylinders, int req_num){
    printf("===============FCFS=============\n");
    int move_sum = 0;
    memset(cylinders, 0, CYLINDER_MAX * sizeof(int));
    set_request(cylinders, request, req_num);//设置磁道请求
    printf("Head location: %d\n", head);
    printf("Processing sequence: ");
    printf("%d ", head);
    for(int i = 0; i < req_num; i++){
        int req_id = request[i];
        printf("%d ", req_id);
        cylinders[req_id]--;
        move_sum += abs(head - req_id); //计算移动距离
        head = req_id; //磁头移动
    }
    printf("\nAverage total distance of head movement = %d\n", move_sum);
    printf("Average average response time = %f\n\n", (double)(move_sum/req_num));


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

代码说明：

根据FCFS调度算法的原理，直接对请求序列从头到尾进行处理，并且计算磁头的移动距离和平均响应时间；

实验结果：

the queue with requests for cylinders: 98 183 37 122 14 124 65 67

the head's position of cylinder: 53

2. 最短寻道时间优先（Shortest Seek Time First, SSTF）算法

SSTF总是选择离当前磁头所在磁道最近的磁道，以便每次寻找的时间最短，在移动磁头到别处以便处理其他请求之前，处理靠近当前磁头位置的所有请求可能较为合理。

这种算法的缺陷是，若某磁头附近频繁地被添加请求，那么磁头会长时间在这附近工作，导致更远的磁道无期限地延迟，即“饥饿”。

实现代码：

void SSTF(int head, int *request, int *cylinders, int req_num){
    printf("===============SSTF=============\n");
    int move_sum = 0;
    int dis_list[req_num];
    int dis_idx[req_num];
    int init_head = head;
    for(int i = 0; i < req_num; i++){
        int dis = abs(head - request[i]);
        dis_list[i] = dis;
        dis_idx[i] = i;
    }
    memset(cylinders, 0, CYLINDER_MAX * sizeof(int));
    set_request(cylinders, request, req_num);
    printf("Head location: %d\n", head);
  
    //对dis_list从小到大进行排序，作为磁道请求序列
    for(int i = 0; i < req_num - 1; i++){
        for(int j = 0; j < req_num - i - 1; j++){
            if(dis_list[j] > dis_list[j+1]){
                int temp = dis_list[j];
                int temp_idx = dis_idx[j];
                dis_list[j] = dis_list[j+1];
                dis_idx[j] = dis_idx[j+1];
                dis_list[j+1] = temp;
                dis_idx[j+1] = temp_idx;
            } 
        }
    }
    printf("Processing sequence: ");
    printf("%d ", head);
    for(int i = 0; i < req_num; i++){
        int req_id = request[dis_idx[i]];
        printf("%d ", req_id);
        cylinders[req_id]--;
        move_sum += abs(head - req_id);
        head = req_id;
    }
    printf("\nAverage total distance of head movement = %d\n", move_sum);
    printf("Average average response time = %f\n\n", (double)(move_sum/req_num));

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

代码说明：

根据SSTF算法的原理，需要优先处理离磁头最近的请求，因此利用冒泡排序对磁头与请求的距离从小到大进行排序，距离记录在dis_list中，对应的请求的下标记录在dis_idx中，方便在排序之后取出请求的磁道数。

实验结果：

the queue with requests for cylinders: 98 183 37 122 14 124 65 67

the head's position of cylinder: 53

在SSTF调度策略中，输入8个磁道请求序列，指定磁头初始位置为53，最后得到磁头平均移动总距离为236，平均响应时间为29；

与FCFS调度策略相比，SSTF的平均移动总距离和平均响应时间均更优；

​

3. SCAN

对于扫描算法，磁臂从磁盘的一端开始，向另一端移动；在移过每个柱面时，处理请求。当到达磁盘的另一端时，磁头移动方向反转，并继续处理。磁头连续来回扫描磁盘。SCAN 算法有时称为电梯算法，因为磁头的行为就像大楼里面的电梯，先处理所有向上的请求，然后再处理相反方向的请求。

实现代码：

void SCAN(int head, int *request, int *cylinders, int req_num, int dir){
    if(dir != 1 && dir != 0){
        printf("Direction Error\n");
        return;
    }
    printf("===============SCAN=============\n");
    int move_sum = 0;
    int dis_list[req_num];
    int dis_idx[req_num];
    int pre_head = head;
    for(int i = 0; i < req_num; i++){
        int dis = abs(head - request[i]);
        dis_list[i] = dis;
        dis_idx[i] = i;
    }
    memset(cylinders, 0, CYLINDER_MAX * sizeof(int));
    set_request(cylinders, request, req_num);
    printf("Head location: %d\n", head);

    printf("Head moving sequence: ");
    printf("%d ", head);
    while(head >= 0 && head < CYLINDER_MAX){
        while(cylinders[head] > 0){
            printf("%d ", head);
            move_sum += abs(pre_head - head);
            pre_head = head;
            cylinders[head]--;
        }

        if(dir == 0) head--;
        else head++; 
    }
    if(head == -1) head++;
    else if(head == CYLINDER_MAX) head--;

    //移动到磁道尽头后, pre_head修改为head的位置,以便磁头换方向移动
    if(pre_head != head){
        printf("%d ", head);
        move_sum += abs(pre_head - head);
        pre_head = head;
    }
   
    if(dir == 1) dir = 0;
    else dir = 1;
  
		//反向移动磁头
    while(head >= 0 && head < CYLINDER_MAX){
        while(cylinders[head] > 0){
            printf("%d ", head);
            move_sum += abs(pre_head - head);
            pre_head = head;
            cylinders[head]--;
        }

        if(dir == 0) head--;
        else head++; 
    }

    printf("\nAverage total distance of head movement = %d\n", move_sum);
    printf("Average average response time = %f\n\n", (double)(move_sum/req_num));

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

代码说明：

根据SCAN调度算法的原理，通过while循环在磁道内让磁头按指定的方向进行移动，并且处理其中的请求，直到到达记录的磁道的尽头，之后调转磁头移动方向继续移动磁头，同样通过while循环来实现；

实验结果：

Head location: 100

Head moving sequence: 55 58 39 18 90 160 150 38 184

Head moving direction: right

在SCAN调度策略中，输入9个磁道请求序列，指定磁头初始位置为100，磁头向右移动（磁道号增大的方向），最后得到磁头平均移动总距离为280，平均响应时间为31；

与FCFS和SSTF调度策略相比，SCAN的平均移动总距离和平均响应时间均更优；

4. C-LOOK

基于SCAN算法，C-LOOK移动磁头从磁盘一端到磁盘另一端（磁臂只需移到一个方向的最远请求为止），并且处理行程上的请求，然而，当磁头到达另一端时，它立即返回到磁盘另一端最远的请求，而并不处理任何回程上的请求，然后从该最远的请求开始，继续往同一方向移动磁盘处理请求。

实现代码：

void C_LOOK(int head, int *request, int *cylinders, int req_num, int dir){
      if(dir != 1 && dir != 0){
        printf("Direction Error\n");
        return;
    }
    printf("===============C-LOOK=============\n");
    int move_sum = 0;
    int pre_head = head;
    int left = 0, right = 0;//记录最远两端的请求
    int flag = 0;
    memset(cylinders, 0, CYLINDER_MAX * sizeof(int));
    set_request(cylinders, request, req_num);
  
  	//获取最远两端的请求left和right
    for(int i = 0; i < CYLINDER_MAX; i++){
        if(cylinders[i] && !flag) {
            left = i;
            flag = 1;
        }
        if(flag && cylinders[i]){
            right = i;
        }
    }
  
    printf("Left Bound: %d, Right Bound: %d\n", left, right);
    printf("Head location: %d\n", head);

    printf("Head moving sequence: ");
    printf("%d ", head);
  
    while(head >= 0 && head < CYLINDER_MAX){
        //当磁头到达最远端的请求
        if(head == right && dir){ 
            cylinders[head]--;
            break;
        }
        if(head == left && !dir) {
            cylinders[head]--;
            break;
        }

        while(cylinders[head] > 0){
            printf("%d ", head);
            move_sum += abs(pre_head - head);
            pre_head = head;
            cylinders[head]--;
        }

        //磁头按指定方向移动
        if(dir == 0) head--;
        else head++; 
    }
    
    // 移动到磁道尽头后, pre_head修改为head的位置,以便磁头换方向移动
    if(pre_head != head){
        printf("%d ", head);
        move_sum += abs(pre_head - head);
        pre_head = head;
    }

    //直接移动到另一端最远的请求，过程中不处理请求
    if(dir == 1){
        head = left;
        cylinders[head]--;
    }
    else{
        head = right;
        cylinders[head]--;
    }
		printf("%d ", head);
    move_sum += abs(pre_head - head);
    pre_head = head;

    //磁头继续沿着最初指定的方向移动
    while(head >= 0 && head < CYLINDER_MAX){
        while(cylinders[head] > 0){
            printf("%d ", head);
            move_sum += abs(pre_head - head);
            pre_head = head;
            cylinders[head]--;
        }

        if(dir == 0) head--;
        else head++; 
    }

    printf("\nAverage total distance of head movement = %d\n", move_sum);
    printf("Average average response time = %f\n\n", (double)(move_sum/req_num));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

代码说明：

根据C-LOOK调度算法的原理，首先记录最远两端的请求，保存在变量left和right中，随后通过while循环在磁道内让磁头按指定的方向进行移动，并且处理其中的请求，直到到达记录的最远请求（按移动方向而定），之后将磁头移动到另外一端最远的请求处，从该请求开始继续按最初指定的方向移动磁头，同样通过while循环来实现；

实验结果：

Head location: 100

Head moving sequence: 55 58 39 18 90 160 150 38 184

Head moving direction: right

在C-LOOK调度策略中，输入9个磁道请求序列，指定磁头初始位置为100，磁头向右移动（磁道号增大的方向），最后得到磁头平均移动总距离为322，平均响应时间为35；

与FCFS和SSTF调度策略相比，C-LOOK的平均移动总距离和平均响应时间比FCFS和SSTF更优，但是比SCAN调度策略更差；

输入的柱面请求序列具有局部性分布：

Head location: 25

Head moving sequence: 20 30 12 20 30 12 20 30 12 30

Head moving direction: right

请求序列工作集 = {12, 20, 30}

从结果可知，C-LOOK的性能最优，SCAN的性能最差，从直观上来看，由于请求的序列的集中在12，20，30，而SCAN调度算法每次都需要将磁头移动到磁道尽头，这样就导致了移动距离相比其它三个算法更大；而C-LOOK中，磁头移动到请求序列的最远请求就停止，并且处理完该磁道的所有请求后再移动到其它请求处，所以大大减少了磁头移动的距离；SSTF的表现也相对较优；

Head location: 50

Head moving sequence: 10 100 5 10 100 5 10 100 5 10 100 5

Head moving direction: right

请求序列工作集 = {5, 10, 100}

在这个带有局部性的柱面请求序列中，工作集为 {5, 10, 100}，可以看到请求5和100之间的距离相对较大；

四种磁头调度算法中，SSTF的性能最优，因为在请求之间距离相对较远的情况下，SSTF总是选择离当前磁头最近的请求进行处理，因此避免了远距离的移动，进而提高性能；

可以看到FCFS的性能最差，总直观上来说，因为请求序列中磁道100和5的请求总是相邻出现的，而它们距离相对较大，所以磁头移动距离就大幅提升了；

II. FCFS、SSTF、SCAN 和 C-LOOK 调度策略的比较

在下表中对四种磁头调度算法的优缺点进行总结：

完整代码：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
#include<math.h>
#define CYLINDER_MAX 200 //最大磁道数
#define REQUEST_MAX 20  //最大请求数
 
 
//设置磁道请求
void set_request(int *cylinders, int *request, int req_num){
    for(int i = 0; i < req_num; i++){
        int req_id = request[i];
        cylinders[req_id]++; //对应的磁道请求数加1
    }
}

void FCFS(int head, int *request, int *cylinders, int req_num){
    printf("===============FCFS=============\n");
    int move_sum = 0;
    memset(cylinders, 0, CYLINDER_MAX * sizeof(int));
    set_request(cylinders, request, req_num);
    printf("Head location: %d\n", head);
    printf("Processing sequence: ");
    printf("%d ", head);
    for(int i = 0; i < req_num; i++){
        int req_id = request[i];
        printf("%d ", req_id);
        cylinders[req_id]--;
        move_sum += abs(head - req_id);
        head = req_id;
    }
    printf("\nAverage total distance of head movement = %d\n", move_sum);
    printf("Average average response time = %f\n\n", (double)(move_sum/req_num));


}

void SSTF(int head, int *request, int *cylinders, int req_num){
    printf("===============SSTF=============\n");
    int move_sum = 0;
    int dis_list[req_num];
    int dis_idx[req_num];
    int init_head = head;
    for(int i = 0; i < req_num; i++){
        int dis = abs(head - request[i]);
        dis_list[i] = dis;
        dis_idx[i] = i;
    }
    memset(cylinders, 0, CYLINDER_MAX * sizeof(int));
    set_request(cylinders, request, req_num);
    printf("Head location: %d\n", head);
    //对dis_list从小到大进行排序，作为磁道请求序列
    for(int i = 0; i < req_num - 1; i++){
        for(int j = 0; j < req_num - i - 1; j++){
            if(dis_list[j] > dis_list[j+1]){
                int temp = dis_list[j];
                int temp_idx = dis_idx[j];
                dis_list[j] = dis_list[j+1];
                dis_idx[j] = dis_idx[j+1];
                dis_list[j+1] = temp;
                dis_idx[j+1] = temp_idx;
            } 
        }
    }
    printf("Processing sequence: ");
    printf("%d ", head);
    for(int i = 0; i < req_num; i++){
        int req_id = request[dis_idx[i]];
        printf("%d ", req_id);
        cylinders[req_id]--;
        move_sum += abs(head - req_id);
        head = req_id;
    }
    printf("\nAverage total distance of head movement = %d\n", move_sum);
    printf("Average average response time = %f\n\n", (double)(move_sum/req_num));

}

void SCAN(int head, int *request, int *cylinders, int req_num, int dir){
    if(dir != 1 && dir != 0){
        printf("Direction Error\n");
        return;
    }
    printf("===============SCAN=============\n");
    int move_sum = 0;
    int pre_head = head;
    memset(cylinders, 0, CYLINDER_MAX * sizeof(int));
    set_request(cylinders, request, req_num);
    printf("Head location: %d\n", head);

    printf("Head moving sequence: ");
    printf("%d ", head);
    while(head >= 0 && head < CYLINDER_MAX){
        while(cylinders[head] > 0){
            printf("%d ", head);
            move_sum += abs(pre_head - head);
            pre_head = head;
            cylinders[head]--;
        }

        if(dir == 0) head--;
        else head++; 
    }
    if(head == -1) head++;
    else if(head == CYLINDER_MAX) head--;

    // 移动到磁道尽头后, pre_head修改为head的位置,以便磁头换方向移动
    if(pre_head != head){
        printf("%d ", head);
        move_sum += abs(pre_head - head);
        pre_head = head;
    }
   
    if(dir == 1) dir = 0;
    else dir = 1;

    while(head >= 0 && head < CYLINDER_MAX){
        while(cylinders[head] > 0){
            printf("%d ", head);
            move_sum += abs(pre_head - head);
            pre_head = head;
            cylinders[head]--;
        }

        if(dir == 0) head--;
        else head++; 
    }

    printf("\nAverage total distance of head movement = %d\n", move_sum);
    printf("Average average response time = %f\n\n", (double)(move_sum/req_num));

}


void C_LOOK(int head, int *request, int *cylinders, int req_num, int dir){
      if(dir != 1 && dir != 0){
        printf("Direction Error\n");
        return;
    }
    printf("===============C-LOOK=============\n");
    int move_sum = 0;
    int pre_head = head;
    int left = 0, right = 0;
    int flag = 0;
    memset(cylinders, 0, CYLINDER_MAX * sizeof(int));
    set_request(cylinders, request, req_num);
    for(int i = 0; i < CYLINDER_MAX; i++){
        if(cylinders[i] && !flag) {
            left = i;
            flag = 1;
        }
        if(flag && cylinders[i]){
            right = i;
        }
    }
    printf("Left Bound: %d, Right Bound: %d\n", left, right);
    printf("Head location: %d\n", head);

    printf("Head moving sequence: ");
    printf("%d ", head);
    while(head >= 0 && head < CYLINDER_MAX){
        //当磁头到达最远端的请求
        if(head == right && dir){ 
            cylinders[head]--;
            break;
        }
        if(head == left && !dir) {
            cylinders[head]--;
            break;
        }

        while(cylinders[head] > 0){
            printf("%d ", head);
            move_sum += abs(pre_head - head);
            pre_head = head;
            cylinders[head]--;
        }

        //磁头按指定方向移动
        if(dir == 0) head--;
        else head++; 
    }
    
    // 移动到磁道尽头后, pre_head修改为head的位置,以便磁头换方向移动
    if(pre_head != head){
        printf("%d ", head);
        move_sum += abs(pre_head - head);
        pre_head = head;
    }

    //直接移动到另一端最远的请求，过程中不处理请求
    if(dir == 1){
        head = left;
        cylinders[head]--;
        
    }
    else{
        head = right;
        cylinders[head]--;
    }
    printf("%d ", head);
    move_sum += abs(pre_head - head);
    pre_head = head;

    //磁头继续沿着指定方向移动
    while(head >= 0 && head < CYLINDER_MAX){
        while(cylinders[head] > 0){
            printf("%d ", head);
            move_sum += abs(pre_head - head);
            pre_head = head;
            cylinders[head]--;
        }

        if(dir == 0) head--;
        else head++; 
    }

    printf("\nAverage total distance of head movement = %d\n", move_sum);
    printf("Average average response time = %f\n\n", (double)(move_sum/req_num));

}


int main(){
    int request[REQUEST_MAX];
    int cylinders[CYLINDER_MAX];
    int N, head, dir;
    printf("Please enter the number of requests for cylinders: ");
    scanf("%d", &N);
    printf("Please enter the queue with requests for cylinders: ");
    for(int i =0 ; i < N; i++){
        scanf("%d", &request[i]);
    }

    printf("Please input the head's position of cylinder: ");
    scanf("%d", &head);

    printf("Please enter the moving direction of the head (0: left, 1: right): ");
    scanf("%d", &dir);
    printf("\n");

    FCFS(head, request, cylinders, N);
    SSTF(head, request, cylinders, N);
    SCAN(head, request, cylinders, N, dir);
    C_LOOK(head, request, cylinders, N, dir);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248