操作系统 - SSTF 磁盘调度
磁盘调度算法 用于确定磁盘的输入/输出 (I/O) 请求的处理顺序。在本章中，我们将通过示例和练习题讨论 最短寻道时间优先 (SSTF) 磁盘调度算法。
- 最短寻道时间优先 (SSTF) 磁盘调度
- SSTF 磁盘调度算法示例
- SSTF 磁盘调度算法实现
- SSTF 磁盘调度算法练习题
- SSTF 磁盘调度算法的优缺点
最短寻道时间优先 (SSTF) 磁盘调度
最短寻道时间优先 (SSTF) 磁盘调度算法选择距离磁盘磁头当前位置最近的请求。这意味着寻道时间最短的请求将优先处理。这与请求的到达顺序无关。
SSTF 被认为比 FCFS 磁盘调度算法更优，因为它减少了总磁头移动距离，从而减少了寻道时间。然而，在某些情况下，它可能导致饥饿现象，即如果某些请求远离当前磁头位置，它们可能永远得不到服务。
算法步骤
- 从 磁盘磁头 的当前位置开始。
- 计算所有挂起请求与当前磁头位置的距离，并将它们存储在 最小堆 中。
- 现在，最小堆的顶元素 就是寻道时间最短的请求。将磁盘磁头移动到该请求并处理它。
- 从最小堆中移除已处理的请求。
- 重复这些步骤，直到所有请求都被处理。
SSTF 磁盘调度算法示例
假设磁盘请求按以下顺序到达：98, 183, 37, 122, 14, 124, 65, 67。磁盘磁头的初始位置在磁道 53。下图显示了使用 SSTF 磁盘调度算法处理上述请求序列时磁盘磁头的移动情况 −
现在，要使用 SSTF 算法计算总磁头移动距离，可以按照以下步骤进行：
$$\mathrm{\text{磁头初始位置} \:=\: 53}$$
$$\mathrm{\text{请求序列} = 98,\,183,\,37,\,122,\,14,\,124,\,65,\,67}$$
$$\mathrm{\text{从 } 53 \text{ 移动到 } 65: |53-65| = 12}$$
$$\mathrm{\text{从 } 65 \text{ 移动到 } 67: |65-67| = 2}$$
$$\mathrm{\text{从 } 67 \text{ 移动到 } 37: |67-37| = 30}$$
$$\mathrm{\text{从 } 37 \text{ 移动到 } 14: |37-14| = 23}$$
$$\mathrm{\text{从 } 14 \text{ 移动到 } 98: |14-98| = 84}$$
$$\mathrm{\text{从 } 98 \text{ 移动到 } 122: |98-122| = 24}$$
$$\mathrm{\text{从 } 122 \text{ 移动到 } 124: |122-124| = 2}$$
$$\mathrm{\text{从 } 124 \text{ 移动到 } 183: |124-183| = 59}$$
现在，通过将所有单个磁头移动距离相加，可以计算总磁头移动距离。另外，平均寻道长度可以通过总磁头移动距离除以请求数量来计算。
$$\mathrm{\text{总磁头移动距离} = 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59}$$
$$\mathrm{ = 236 \text{ 磁道}}$$
$$\mathrm{\text{平均寻道长度} = \frac{\text{总磁头移动距离}}{\text{请求数量}} }$$
$$\mathrm{= \frac{236}{8} = 29.5 \text{ 磁道}}$$
对于相同的请求序列和初始磁头位置，FCFS 算法的总磁头移动距离为 640 磁道（在 FCFS 章节中计算）。您可以看到，SSTF 只需 236 磁道。这表明 SSTF 算法比 FCFS 算法更优化和高效。
SSTF 磁盘调度算法的实现
以下是如何在 Python/C++/Java 中实现 SSTF 磁盘调度算法 −
import heapq
def sstf_disk_scheduling(requests, head):
total_head_movement = 0
seek_sequence = []
requests = requests.copy()
while requests:
distances = [(abs(head - req), req) for req in requests]
heapq.heapify(distances)
shortest_distance, closest_request = heapq.heappop(distances)
total_head_movement += shortest_distance
head = closest_request
seek_sequence.append(closest_request)
requests.remove(closest_request)
return total_head_movement, seek_sequence
# 示例用法
requests = [98, 183, 37, 122, 14, 124, 65, 67]
initial_head = 53
total_movement, sequence = sstf_disk_scheduling(requests, initial_head)
print("Total Head Movement:", total_movement)
print("Seek Sequence:", sequence)
上述代码的输出如下 −
Total Head Movement: 236 Seek Sequence: [65, 67, 37, 14, 98, 122, 124, 183]
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
pair<int, vector<int>> sstf_disk_scheduling(vector<int> requests, int head) {
int total_head_movement = 0;
vector<int> seek_sequence;
while (!requests.empty()) {
auto closest = min_element(requests.begin(), requests.end(),
[head](int a, int b) {
return abs(a - head) < abs(b - head);
});
total_head_movement += abs(*closest - head);
head = *closest;
seek_sequence.push_back(*closest);
requests.erase(closest);
}
return { total_head_movement, seek_sequence };
}
int main() {
vector<int> requests = { 98, 183, 37, 122, 14, 124, 65, 67 };
int initial_head = 53;
auto [total_movement, sequence] = sstf_disk_scheduling(requests, initial_head);
cout << "Total Head Movement: " << total_movement << endl;
cout << "Seek Sequence: ";
for (int req : sequence) {
cout << req << " ";
}
cout << endl;
return 0;
}
上述代码的输出如下 −
Total Head Movement: 236 Seek Sequence: 65 67 37 14 98 122 124 183
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SSTFDiskScheduling {
public static Pair sstfDiskScheduling(List<Integer> requests, int head) {
int totalHeadMovement = 0;
List<Integer> seekSequence = new ArrayList<>();
while (!requests.isEmpty()) {
final int currentHead = head;
int closestRequest = Collections.min(
requests,
(a, b) -> Integer.compare(Math.abs(a - currentHead), Math.abs(b - currentHead))
);
totalHeadMovement += Math.abs(closestRequest - head);
head = closestRequest;
seekSequence.add(closestRequest);
requests.remove(Integer.valueOf(closestRequest));
}
return new Pair(totalHeadMovement, seekSequence);
}
public static void main(String[] args) {
List<Integer> requests = new ArrayList<>(List.of(98, 183, 37, 122, 14, 124, 65, 67));
int initialHead = 53;
Pair result = sstfDiskScheduling(requests, initialHead);
System.out.println("Total Head Movement: " + result.totalHeadMovement);
System.out.println("Seek Sequence: " + result.seekSequence);
}
}
class Pair {
int totalHeadMovement;
List<Integer> seekSequence;
Pair(int totalHeadMovement, List<Integer> seekSequence) {
this.totalHeadMovement = totalHeadMovement;
this.seekSequence = seekSequence;
}
}
上述代码的输出如下 −
Total Head Movement: 236 Seek Sequence: [65, 67, 37, 14, 98, 122, 124, 183]
SSTF 磁盘调度中的练习题
题目 1： 给定以下磁盘请求：45, 23, 89, 12, 67，磁盘磁头初始位置在磁道 30。使用 SSTF 磁盘调度算法计算总磁头移动距离。
答案： 我们有，
$$\mathrm{\text{磁头初始位置} = 30}$$
$$\mathrm{\text{请求序列} = 45,\,23,\,89,\,12,\,67}$$
现在，我们可以逐步计算总磁头移动距离 −
$$\mathrm{\text{从 } 30 \text{ 移动到 } 23: |30-23| = 7}$$
$$\mathrm{\text{从 } 23 \text{ 移动到 } 12: |23-12| = 11}$$
$$\mathrm{\text{从 } 12 \text{ 移动到 } 45: |12-45| = 33}$$
$$\mathrm{\text{从 } 45 \text{ 移动到 } 67: |45-67| = 22}$$
$$\mathrm{\text{从 } 67 \text{ 移动到 } 89: |67-89| = 22}$$
现在，我们可以通过将所有单个磁头移动距离相加来计算总磁头移动距离。
$$\mathrm{\text{总磁头移动距离} = 7 + 11 + 33 + 22 + 22 = 105}$$
题目 2： 给定以下磁盘请求：150, 30, 90, 10, 70。如果磁盘磁头初始位置在磁道 50，假设每个磁道的寻道时间为 0.1 ms，求寻道时间。
答案： 我们有，
$$\mathrm{\text{磁头初始位置} = 50}$$
$$\mathrm{\text{请求序列} = 150,\,30,\,90,\,10,\,70}$$
首先逐步计算总磁头移动距离 −
$$\mathrm{\text{从 } 50 \text{ 移动到 } 70: |50-70| = 20}$$
$$\mathrm{\text{从 } 70 \text{ 移动到 } 90: |70-90| = 20}$$
$$\mathrm{\text{从 } 90 \text{ 移动到 } 30: |90-30| = 60}$$
$$\mathrm{\text{从 } 30 \text{ 移动到 } 10: |30-10| = 20}$$
$$\mathrm{\text{从 } 10 \text{ 移动到 } 150: |10-150| = 140}$$
$$\mathrm{\text{总磁头移动距离} = 20 + 20 + 60 + 20 + 140 = 260}$$
因此，总磁头移动距离为 260 个磁道。现在，寻道时间可以通过将总磁头移动距离乘以每个磁道的寻道时间来计算。
$$\mathrm{\text{寻道时间} = \text{总磁头移动距离} \times \text{每个磁道的寻道时间} }$$
$$\mathrm{= 260 \times 0.1 = 26 \text{ ms}}$$
因此，寻道时间为 26 ms。
SSTF 磁盘调度算法的优缺点
该算法的优点是：
- 平均寻道时间在所有磁盘调度算法中最低。
- 资源利用更高效
该算法的缺点是 −
- 如果某些请求距离当前磁头位置较远，可能会导致这些请求饥饿。
- 与 FCFS 相比，实现更复杂。
- 需要知道所有挂起请求才能做出最优决策。