磁盘调度策略介绍与实现

发表于 | 分类于

磁盘调度基础

磁盘是一种大容量低成本的存储设备，其支持随机存取。机械硬盘的物理结构如下所示：图片来源

磁盘物理结构

如图所示，磁盘由多个盘片和读写磁头臂组成。盘面被分为多个同心圆，称为磁道；每个磁道又被划分为多个独立的逻辑区域，被称为扇区，扇区容量一般是512byte，有些较大为4Kbyte。每个磁道上扇区的数量可能相同也可能不相同，由于外圈长度比较大，为了提高密度可以划分更多的扇区。

磁盘在设计时根据磁头是否在磁道之间移动可大致分为以下两种：

1. 固定头磁盘，每条磁道都有读写磁头，磁头被安装在刚性磁臂上，可并行读写磁道
2. 移动头磁盘，每个盘面只有一个磁头，磁头需要能在不同磁道之间移动，读写速度较慢

磁盘调度主要是针对移动头磁盘的读写时间优化。

磁盘访问时间

磁盘在读写的时候主要经历如下过程：启动磁臂->移动磁头到指定磁道->扇区移动到磁头下方->读取数据。因此磁盘访问时间主要如下几部分组成：

1. 寻道时间Ts，Ts=m*n"+s，s为启动磁臂时间，n为跨越磁道数，m为一常数，和具体磁盘有关
2. 旋转延迟时间Tr，指扇区移动到磁头下花费的时间
3. 传输时间Tt，为数据读写所花费的时间，如果每次读写字节数为b，旋转速度为r，磁道字节数为N，则Tt=b/(rN)

从上述可得出整个读写期间共花费Ta=Ts+Tr+Tt，其中前两项一般与读取的数据量无关，且是整个时间中的大头。

磁盘调度策略

由于读写总花费时间中寻道时间和旋转延迟占比比较大，因此从这两方面出发优化读写效率。对于旋转延迟一般和磁盘转速有关，因此主要提高转速。寻道时间则主要从寻道策略中优化，因此主要形成如下几种磁盘调度策略：

1. 先来先服务（FCFS，First Come First Served）
2. 最短寻道时间优先（SSTF，Shortest Seek Time First）
3. 扫描算法（SCAN）
4. 循环扫描算法（CSCAN）
5. NStepSCAN以及FSCAN算法

一下分别详细介绍各种调度算法。

先来先服务

先来先服务是一种非常简单的算法，其按照请求的顺序依次处理，其优点是简单公平，但是由于没有对寻道时间进行任何优化，因此致使平均寻道时间比较大。这些特点使得FCFS算法不太适用于需要进行频繁读写的场合。其基本实现模拟代码如下所示。

1
2
3
4
5
6
7
8
9
10
11
12
int FCFS(vector<int> &serveArray, int startPosition)
{
	if (serveArray.size() <=0) return 0;
	int nowPosition = startPosition;
	int sum = 0;
	for (size_t i = 0; i < serveArray.size(); i++) {
		int tmp = serveArray[i] - nowPosition;
		sum += tmp > 0 ?  tmp :-tmp;
		nowPosition = serveArray[i];
	}
	return sum;
}

最短寻道时间优先

最短寻道时间优先是指在请求队列中优先满足离当前位置最近的磁道，使得每次寻道时间最短，即简单的贪心思想，但是这样并不能保证平均寻道时间最短。最短寻道时间优先策略一般优于先来先服务策略，但是可能发生饥饿现象，这是由于每次都选择离当前位置最近的磁道，对于离的比较的远的请求可能一直得不到服务。最短寻道时间优先模拟代码如下所示。

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
int SSTF(vector<int> &serveArray, int startPosition)
{
	if (serveArray.size() <= 0) return 0;
	int leftIndex = 0, rightIndex = 0;
	sort(serveArray.begin(), serveArray.end());
	for (leftIndex = 0; leftIndex < int(serveArray.size()) && startPosition > serveArray[leftIndex]; leftIndex++) ;
	rightIndex = leftIndex; --leftIndex;

	int sum = 0; int nowPosition = startPosition;
	while (leftIndex >= 0 || rightIndex < int(serveArray.size())) {
		if (leftIndex >= 0 && rightIndex < int(serveArray.size())) {
			if (abs(serveArray[leftIndex]-nowPosition) < abs(serveArray[rightIndex]-nowPosition)) {
				sum += abs(serveArray[leftIndex]-nowPosition); 
				nowPosition = serveArray[leftIndex];
				--leftIndex;
			}
			else {
				sum += abs(serveArray[rightIndex]-nowPosition); 
				nowPosition = serveArray[rightIndex];
				++rightIndex;
			}
		}
		else if (leftIndex >= 0) {
			sum += abs(serveArray[leftIndex]-nowPosition); 
			nowPosition = serveArray[leftIndex];
			--leftIndex;
		}
		else if (rightIndex < int(serveArray.size())) {
			sum += abs(serveArray[rightIndex]-nowPosition); 
			nowPosition = serveArray[rightIndex];
			++rightIndex;
		}
	}
	return sum;
}

扫描算法

扫描算法又称为电梯调度算法，其考虑请求磁道与当前磁道的距离和磁头当前移动的方向，在某一方向上一直访问下去直到没有更远的请求磁道，接着才调转方向。这个过程非常类似于电梯运行方式。由于磁头会一直向一个方向移动直到无更远访问请求，因此扫描算法不会发生饥饿现象，但是可能发生磁臂粘滞现象。以下是基本的模拟代码。

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
int SACN(vector<int> &serveArray, int startPosition)
{
	if (serveArray.size() <= 0) return 0;
	int leftIndex = 0, rightIndex = 0;
	sort(serveArray.begin(), serveArray.end());
	for (leftIndex = 0; leftIndex < int(serveArray.size()) && startPosition > serveArray[leftIndex]; leftIndex++) ;
	rightIndex = leftIndex; --leftIndex;

	int sum = 0; int nowPosition = startPosition;
	if (leftIndex >= 0 && rightIndex < int(serveArray.size())) {
		if (abs(serveArray[leftIndex]-nowPosition) < abs(serveArray[rightIndex]-nowPosition)) {
			while (leftIndex >= 0) {
				sum += abs(serveArray[leftIndex]-nowPosition); 
				nowPosition = serveArray[leftIndex]; --leftIndex;
			}

			while (rightIndex < int(serveArray.size())) {
				sum += abs(serveArray[rightIndex]-nowPosition); 
				nowPosition = serveArray[rightIndex]; ++rightIndex;
			}
				
		}
		else {
			while (rightIndex < int(serveArray.size())) {
				sum += abs(serveArray[rightIndex]-nowPosition); 
				nowPosition = serveArray[rightIndex]; ++rightIndex;
			}

			while (leftIndex >= 0) {
				sum += abs(serveArray[leftIndex]-nowPosition); 
				nowPosition = serveArray[leftIndex]; --leftIndex;
			}
		}
	}
	else if (leftIndex >= 0) {
		while (leftIndex >= 0) {
			sum += abs(serveArray[leftIndex]-nowPosition); 
			nowPosition = serveArray[leftIndex]; --leftIndex;
		}
	}
	else if (rightIndex < int(serveArray.size())) {
		sum += abs(serveArray[rightIndex]-nowPosition); 
		nowPosition = serveArray[rightIndex]; ++rightIndex;
	}
	return sum;
}

循环扫描算法

循环扫描算法和扫描算法最大的区别是规定磁头采用单向移动的模式，比如规定从里向外移动。这种方式可以减少对刚越过磁道发生请求的响应时间。以下是基本的模拟代码，假定采用磁道号增加的方向的扫描方式。

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
int CSACN(vector<int> &serveArray, int startPosition)
{
	if (serveArray.size() <= 0) return 0;
	int leftIndex = 0, rightIndex = 0;
	sort(serveArray.begin(), serveArray.end());
	for (leftIndex = 0; leftIndex < int(serveArray.size()) && startPosition > serveArray[leftIndex]; leftIndex++) ;
	rightIndex = leftIndex; --leftIndex;

	int sum = 0; int nowPosition = startPosition;
	if (rightIndex < int(serveArray.size())) {
		while (rightIndex < int(serveArray.size())) {
			sum += abs(serveArray[rightIndex]-nowPosition); 
			nowPosition = serveArray[rightIndex]; ++rightIndex;
		}
		int i = 0;
		while (i <= leftIndex) {
			sum += abs(serveArray[i]-nowPosition);
			nowPosition = serveArray[i]; ++i;
		}
	}
	else {
		int i = 0;
		while (i <= leftIndex) {
			sum += abs(serveArray[i]-nowPosition);
			nowPosition = serveArray[i]; ++i;
		}
	}
	return sum;
}

NStepSCAN与FSCAN算法

在SSTF、SCAN、CSCAN几种调度算法中，可能会由于频繁发生请求在当前磁道或附近致使磁头一直停留在附近或当前磁道中，导致对于某个磁道的请求垄断了整个磁盘设备，该现象称为磁盘粘滞，一般发生在高密度磁盘上。而NStepSCAN则将请求分成若干个长度为N的子队列，队列之间按照先来先服务的顺序，每个队列内按照SCAN算法处理，新请求插入其他队列（非当前处理队列）。如果N=1则退化成FCFS算法。

FSCAN算法和NStepSCAN区别主要是FSCAN算法只将请求分为两个队列，一个是当前处理队列以及在处理过程中新的请求队列。

两种算法的处理模拟代码如下：

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
int SACN(vector<int> &serveArray, int &nowPosition)
{
	if (serveArray.size() <= 0) return 0;
	int leftIndex = 0, rightIndex = 0;
	sort(serveArray.begin(), serveArray.end());
	for (leftIndex = 0; leftIndex < int(serveArray.size()) && nowPosition > serveArray[leftIndex]; leftIndex++) ;
	rightIndex = leftIndex; --leftIndex;

	int sum = 0;
	if (leftIndex >= 0 && rightIndex < int(serveArray.size())) {
		if (abs(serveArray[leftIndex]-nowPosition) < abs(serveArray[rightIndex]-nowPosition)) {
			while (leftIndex >= 0) {
				sum += abs(serveArray[leftIndex]-nowPosition); 
				nowPosition = serveArray[leftIndex]; --leftIndex;
			}

			while (rightIndex < int(serveArray.size())) {
				sum += abs(serveArray[rightIndex]-nowPosition); 
				nowPosition = serveArray[rightIndex]; ++rightIndex;
			}
				
		}
		else {
			while (rightIndex < int(serveArray.size())) {
				sum += abs(serveArray[rightIndex]-nowPosition); 
				nowPosition = serveArray[rightIndex]; ++rightIndex;
			}

			while (leftIndex >= 0) {
				sum += abs(serveArray[leftIndex]-nowPosition); 
				nowPosition = serveArray[leftIndex]; --leftIndex;
			}
		}
	}
	else if (leftIndex >= 0) {
		while (leftIndex >= 0) {
			sum += abs(serveArray[leftIndex]-nowPosition); 
			nowPosition = serveArray[leftIndex]; --leftIndex;
		}
	}
	else if (rightIndex < int(serveArray.size())) {
		sum += abs(serveArray[rightIndex]-nowPosition); 
		nowPosition = serveArray[rightIndex]; ++rightIndex;
	}
	return sum;
}

int NStepSCAN(vector<vector<int>> &serveArrays, int startPosition)
{
	int sum = 0;
	if (serveArrays.size() <= 0) return sum;
	
	for(size_t i = 0; i < serveArrays.size(); i++) {
		sum += SACN(serveArrays[i], startPosition);
	}
	return sum;
}

int FSCAN(vector<int> &serveArray, vector<int> &newArray, int startPosition)
{
	int sum = 0;
	sum += SACN(serveArray, startPosition);
	sum += SACN(newArray, startPosition);
	return sum;
}

磁盘调度总结

FCFS算法、SSTF算法、SCAN算法、CSCAN算法、NStepSCAN算法、FSCAN算法各有其优缺点，总结如下：

  • FCFS算法

    1. 优点：算法实现简单，公平
    2. 缺点：效率不高，相邻请求不能快速处理，磁头反复移动

  • SSTF算法

    1. 优点：采取贪心策略，优化平均寻道时间
    2. 缺点：可能导致饥饿现象

  • SCAN算法

    1. 优点：可以防止饥饿现象同时考虑到优化寻道时间
    2. 缺点：可能发生磁臂粘滞现象，某些请求可能会被严重推迟

  • CSCAN算法

    1. 优点：解决SCAN算法某些请求可能会被严重推迟的问题
    2. 缺点：由于单向移动，对于请求较少可能会出现返回时间的浪费

  • NStepSCAN算法

    1. 优点：避免磁臂粘滞的情况同时继承SCAN的优点
    2. 缺点：编程稍微复杂

  • FSCAN算法

    1. 优点：简化处理，实现较NStepSCAN算法更为简单
    2. 缺点：两个队列可能会稍增加平均寻道时间