操作系统原理之磁盘调度

标签：操作系统原理

磁盘调度算法

磁盘调度（Disk scheduling）是由操作系统完成的，用于安排到达磁盘的 I/O 请求。磁盘调度也被称为 I/O 调度（I/O scheduling）。

磁盘调度的重要性在于：

多个 I/O 请求可能由不同的进程到达，而磁盘控制器（disk controller）一次只能提供一个 I/O 请求。因此，其他 I/O 请求需要在等待队列中等待，并需要进行调度。
两个或更多的请求可能彼此相距甚远，因此会导致更大的磁盘臂运动（disk arm movement）。
硬盘（Hard drives）是计算机系统中最慢的部分之一，因此需要以一种有效的方式进行访问。

有许多磁盘调度算法（Disk Scheduling Algorithms），但在讨论这些算法之前，让我们快速看一下一些重要的术语。

寻道时间（Seek Time）：寻道时间是指将磁盘臂定位到要读或写数据的指定轨道上所需的时间。因此，能提供最小平均寻道时间（minimum average seek time）的磁盘调度算法是更好的。
旋转延时（Rotational Latency）。旋转延迟是指磁盘所需的扇区旋转到某一位置所需的时间，这样它就可以访问读 / 写头。因此，能提供最小旋转延迟的磁盘调度算法是更好的。注：平均旋转延迟通常被认为是 1/2*旋转延迟 。
传输时间（Transfer Time）：传输时间是传输数据的时间。它取决于磁盘的旋转速度和要传输的字节数。
磁盘访问时间（Disk Access Time）。磁盘访问时间是指： Disk Access Time = Seek Time + Rotational Latency + Transfer Time 。
磁盘响应时间（Disk Response Time）。响应时间是指一个请求等待执行其 I/O 操作所花费的平均时间。平均响应时间（Average Response time）是所有请求的响应时间。差异响应时间（Variance Response Time）是衡量单个请求在平均响应时间方面得到服务的情况。因此，能提供最小差异响应时间的磁盘调度算法是更好的。

FCFS：先到先服务

FCFS 是所有磁盘调度算法中最简单的一种。在 FCFS 中，请求是按照它们到达磁盘队列的顺序来处理的。让我们借助一个例子来理解这一点。

假设请求的顺序是 (82,170,43,140,24,16,190)，读 / 写头的当前位置是：50，所以，总的寻道时间 = (82-50)+(170-82)+(170-43)+(140-43)+(140-24)+(24-16)+(190-16)=642 。

优势：

每个请求都得到了公平的机会
没有无限期的推迟

弊端：

没有尝试优化寻道时间
可能无法提供最好的服务

SSTF：最短寻道时间优先

在 SSTF（最短寻道时间优先，Shortest Seek Time First）中，寻道时间最短的请求被优先执行。因此，每个请求的寻道时间在队列中被提前计算，然后根据计算出的寻道时间来安排它们。因此，靠近磁盘臂（disk arm）的请求将首先被执行。SSTF 无疑是对 FCFS 的一种改进，因为它减少了平均响应时间，增加了系统的吞吐量。让我们借助一个例子来了解一下。

假设请求的顺序是：(82,170,43,140,24,16,190)，读 / 写头的当前位置是：50。所以，总的寻道时间 = (50-43)+(43-24)+(24-16)+(82-16)+(140-82)+(170-140)+(190-170)=208 。

优势：

比 FCFS 调度算法的性能更好。
吞吐量增加。这种算法用于批量处理系统，在这种系统中吞吐量更为重要。
它有较少的平均响应和等待时间。

劣势：

提前计算搜索时间的开销
如果一个请求的寻道时间比传入的请求长，可能会导致饥饿现象（Starvation）。因为它倾向于容易到达的请求，而忽略了远处的请求。
差异响应时间大，缺乏可预测性，因为 SSTF 只对某些请求有利
切换方向会使速度变慢。

算法：

Request 数组代表一个存储已被请求的轨道的索引的数组。head 是磁盘磁头的位置。
找到请求阵列中所有轨道与磁头的正向距离（positive distance）。
从请求数组中找到一个还没有被访问 / 服务过的并且与头部的距离最小的轨道。
用这个距离来增加总的寻道次数。
当前被服务的轨道位置现在成为新的磁头位置。
转到步骤 2，直到请求阵列中的所有轨道都被服务过。

实现:

Python

# Python3 program for implementation of
# SSTF disk scheduling

# Calculates difference of each
# track number with the head position
def calculateDifference(queue, head, diff):
 for i in range(len(diff)):
  diff[i][0] = abs(queue[i] - head)
 
# find unaccessed track which is
# at minimum distance from head
def findMin(diff):

 index = -1
 minimum = 999999999

 for i in range(len(diff)):
  if (not diff[i][1] and
    minimum > diff[i][0]):
   minimum = diff[i][0]
   index = i
 return index
 
def shortestSeekTimeFirst(request, head):   
  if (len(request) == 0):
   return
  
  l = len(request)
  diff = [0] * l
  
  # initialize array
  for i in range(l):
   diff[i] = [0, 0]
  
  # count total number of seek operation 
  seek_count = 0
  
  # stores sequence in which disk
  # access is done
  seek_sequence = [0] * (l + 1)
  
  for i in range(l):
   seek_sequence[i] = head
   calculateDifference(request, head, diff)
   index = findMin(diff)
   
   diff[index][1] = True
   
   # increase the total count
   seek_count += diff[index][0]
   
   # accessed track is now new head
   head = request[index]
 
  # for last accessed track
  seek_sequence[len(seek_sequence) - 1] = head
  
  print("Total number of seek operations =",
         seek_count)
              
  print("Seek Sequence is")
  
  # print the sequence
  for i in range(l + 1):
   print(seek_sequence[i])
 
# Driver code
if __name__ =="__main__":
 
 # request array
 proc = [176, 79, 34, 60,
   92, 11, 41, 114]
 shortestSeekTimeFirst(proc, 50)

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

SCAN：扫描算法

在 SCAN 算法中，盘臂向一个特定的方向移动，并为其路径上的请求提供服务，在到达盘的末端后，它反转方向，再次为其路径上的请求提供服务。因此，这种算法像电梯一样工作，因此也被称为电梯算法（elevator algorithm）。因此，在中间位置的请求得到更多的服务，而那些在磁盘臂后面到达的请求将不得不等待。

假设要处理的请求是：82,170,43,140,24,16,190，而读 / 写臂在 50，并且还给出了磁盘臂应该 "向大值"（towards the larger value）移动。所以，总的寻道时间 = (199-50)+(199-16)=332 。

优势：

这种算法简单易懂。
SCAN 算法没有饿死现象。
这种算法比 FCFS 调度算法更好。
高吞吐量
响应时间的差异性低
平均响应时间小

劣势：

实现起来比较复杂。
这种算法是不公平的，对于刚刚被磁盘臂访问过的地点的请求，等待时间长
它使磁头一直移动到磁盘的末端，这样一来，在磁臂位置之前到达的请求将立即得到服务，但在磁臂位置之后到达的其他一些请求将不得不等待请求的完成。

算法：

让 Request 数组代表一个数组，存储已被请求的轨道的索引，按其到达时间的升序排列。head 是指磁盘磁头的位置。direction 表示磁头是向左还是向右移动。
在磁头移动的方向上，逐一服务所有轨道。
计算轨道与磁头的绝对距离，用这个距离来增加总的寻道次数。
当前服务的轨道位置现在成为新的磁头位置。直到我们到达磁盘的某一端。
如果我们到达了磁盘的末端，则反转方向，继续执行，直到请求阵列中的所有轨道都被服务过。

实现：

python

# Python3 program to demonstrate
# SCAN Disk Scheduling algorithm
size = 8
disk_size = 200

def SCAN(arr, head, direction):

 seek_count = 0
 distance, cur_track = 0, 0
 left = []
 right = []
 seek_sequence = []

 # Appending end values
 # which has to be visited
 # before reversing the direction
 if (direction == "left"):
  left.append(0)
 elif (direction == "right"):
  right.append(disk_size - 1)

 for i in range(size):
  if (arr[i] < head):
   left.append(arr[i])
  if (arr[i] > head):
   right.append(arr[i])

 # Sorting left and right vectors
 left.sort()
 right.sort()

 # Run the while loop two times.
 # one by one scanning right
 # and left of the head
 run = 2
 while (run != 0):
  if (direction == "left"):
   for i in range(len(left) - 1, -1, -1):
    cur_track = left[i]

    # Appending current track to
    # seek sequence
    seek_sequence.append(cur_track)

    # Calculate absolute distance
    distance = abs(cur_track - head)

    # Increase the total count
    seek_count += distance

    # Accessed track is now the new head
    head = cur_track
   
   direction = "right"
 
  elif (direction == "right"):
   for i in range(len(right)):
    cur_track = right[i]
    
    # Appending current track to seek
    # sequence
    seek_sequence.append(cur_track)

    # Calculate absolute distance
    distance = abs(cur_track - head)

    # Increase the total count
    seek_count += distance

    # Accessed track is now new head
    head = cur_track
   
   direction = "left"
  
  run -= 1

 print("Total number of seek operations =",
  seek_count)

 print("Seek Sequence is")

 for i in range(len(seek_sequence)):
  print(seek_sequence[i])

# Driver code

# request array
arr = [ 176, 79, 34, 60,
  92, 11, 41, 114 ]
head = 50
direction = "left"

SCAN(arr, head, direction)

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

CSCAN：循环扫描算法

在 SCAN 算法中，磁盘臂在颠倒方向后再次扫描已经扫描过的路径。因此，可能会有太多的请求在另一端等待，或者在扫描的端有零个或几个请求在等待。

这些情况在 CSCAN 算法中得到了避免，在该算法中，磁盘臂没有扭转方向，而是去了磁盘的另一端，并从那里开始处理请求。因此，磁盘臂以循环（circular）方式移动，这种算法也类似于 SCAN 算法，因此它被称为 C-SCAN（循环 SCAN，Circular SCAN）。

例子：

假设要处理的请求是：82,170,43,140,24,16,190。而读写臂在 50，并且还给出了磁盘臂应该 "向大值" 移动。所以，总的寻道时间 = (199-50)+(199-0)+(43-0)=391 。

优势：

与 SCAN 相比，它提供了更好的响应时间和统一的等待时间。
在中度和重度负荷下工作良好。

劣势：

对处于极端位置的轨道的服务请求可能不公平。
与 SCAN 算法相比，它有更多的寻道移动（seek movements）。

实现：

python

# Python3 program to demonstrate
# C-SCAN Disk Scheduling algorithm
size = 8
disk_size = 200


def CSCAN(arr, head):

 seek_count = 0
 distance = 0
 cur_track = 0
 left = []
 right = []
 seek_sequence = []

 # Appending end values
 # which has to be visited
 # before reversing the direction
 left.append(0)
 right.append(disk_size - 1)

 # Tracks on the left of the
 # head will be serviced when
 # once the head comes back
 # to the beggining (left end).
 for i in range(size):
  if (arr[i] < head):
   left.append(arr[i])
  if (arr[i] > head):
   right.append(arr[i])

 # Sorting left and right vectors
 left.sort()
 right.sort()

 # First service the requests
 # on the right side of the
 # head.
 for i in range(len(right)):
  cur_track = right[i]

  # Appending current track
  # to seek sequence
  seek_sequence.append(cur_track)

  # Calculate absolute distance
  distance = abs(cur_track - head)

  # Increase the total count
  seek_count += distance

  # Accessed track is now new head
  head = cur_track

 # Once reached the right end
 # jump to the beggining.
 head = 0

 # adding seek count for head returning from 199 to 0
 seek_count += (disk_size - 1)

 # Now service the requests again
 # which are left.
 for i in range(len(left)):
  cur_track = left[i]

  # Appending current track
  # to seek sequence
  seek_sequence.append(cur_track)

  # Calculate absolute distance
  distance = abs(cur_track - head)

  # Increase the total count
  seek_count += distance

  # Accessed track is now the new head
  head = cur_track

 print("Total number of seek operations =",
  seek_count)
 print("Seek Sequence is")
 print(*seek_sequence, sep="\n")

# Driver code


# request array
arr = [176, 79, 34, 60,
 92, 11, 41, 114]
head = 50

print("Initial position of head:", head)

CSCAN(arr, head)

LOOK

它与 SCAN 磁盘调度算法类似，不同的是磁盘臂尽管走到了磁盘的末端，但只走到磁头前面的最后一个要服务的请求，然后只从那里反转方向。因此，它防止了由于不必要的穿越到磁盘末端而产生的额外延迟。

例子：

假设要处理的请求是：82,170,43,140,24,16,190。而读写臂在 50，并且还给出了磁盘臂应该 "向大值" 移动。总的寻道时间 = (190-50)+(190-16)=314 。

实现：

python

# Python3 program to demonstrate
# LOOK Disk Scheduling algorithm
size = 8
disk_size = 200

def LOOK(arr, head, direction):
 
 seek_count = 0
 distance = 0
 cur_track = 0

 left = []
 right = []

 seek_sequence = []

 # Appending values which are
 # currently at left and right
 # direction from the head.
 for i in range(size):
  if (arr[i] < head):
   left.append(arr[i])
  if (arr[i] > head):
   right.append(arr[i])

 # Sorting left and right vectors
 # for servicing tracks in the
 # correct sequence.
 left.sort()
 right.sort()

 # Run the while loop two times.
 # one by one scanning right
 # and left side of the head
 run = 2
 while (run):
  if (direction == "left"):
   for i in range(len(left) - 1, -1, -1):
    cur_track = left[i]

    # Appending current track to
    # seek sequence
    seek_sequence.append(cur_track)

    # Calculate absolute distance
    distance = abs(cur_track - head)

    # Increase the total count
    seek_count += distance

    # Accessed track is now the new head
    head = cur_track

   # Reversing the direction
   direction = "right"
   
  elif (direction == "right"):
   for i in range(len(right)):
    cur_track = right[i]

    # Appending current track to
    # seek sequence
    seek_sequence.append(cur_track)

    # Calculate absolute distance
    distance = abs(cur_track - head)
    
    # Increase the total count
    seek_count += distance

    # Accessed track is now new head
    head = cur_track

   # Reversing the direction
   direction = "left"
   
  run -= 1

 print("Total number of seek operations =",
  seek_count)
 print("Seek Sequence is")

 for i in range(len(seek_sequence)):
  print(seek_sequence[i])

# Driver code

# Request array
arr = [ 176, 79, 34, 60, 92, 11, 41, 114 ]
head = 50

direction = "right"

print("Initial position of head:", head)

LOOK(arr, head, direction)

CLOOK

由于 LOOK 与 SCAN 算法相似，CLOOK 也与 CSCAN 磁盘调度算法相似。在 CLOOK 中，尽管磁盘臂走到了尽头，但它只走到最后一个要服务的请求，然后从那里走到另一端的最后请求。因此，它也防止了由于不必要的穿越到磁盘末端而产生的额外延迟。

例子：

假设要处理的请求是：82,170,43,140,24,16,190。而读写臂在 50，并且还给出了磁盘臂应该 "向较大的值" 移动。总的寻道时间 = (190-50)+(190-16)+(43-16) =341 。

实现：

Python

# Python3 implementation of the approach
size = 8
disk_size = 200

# Function to perform C-LOOK on the request
# array starting from the given head
def CLOOK(arr, head):
 
 seek_count = 0
 distance = 0
 cur_track = 0

 left = []
 right = []

 seek_sequence = []

 # Tracks on the left of the
 # head will be serviced when
 # once the head comes back
 # to the beginning (left end)
 for i in range(size):
  if (arr[i] < head):
   left.append(arr[i])
  if (arr[i] > head):
   right.append(arr[i])

 # Sorting left and right vectors
 left.sort()
 right.sort()

 # First service the requests
 # on the right side of the
 # head
 for i in range(len(right)):
  cur_track = right[i]
  
  # Appending current track
  # seek sequence
  seek_sequence.append(cur_track)

  # Calculate absolute distance
  distance = abs(cur_track - head)

  # Increase the total count
  seek_count += distance

  # Accessed track is now new head
  head = cur_track

 # Once reached the right end
 # jump to the last track that
 # is needed to be serviced in
 # left direction
 seek_count += abs(head - left[0])
 head = left[0]

 # Now service the requests again
 # which are left
 for i in range(len(left)):
  cur_track = left[i]

  # Appending current track to
  # seek sequence
  seek_sequence.append(cur_track)

  # Calculate absolute distance
  distance = abs(cur_track - head)

  # Increase the total count
  seek_count += distance

  # Accessed track is now the new head
  head = cur_track

 print("Total number of seek operations =",
  seek_count)
 print("Seek Sequence is")

 for i in range(len(seek_sequence)):
  print(seek_sequence[i])

# Driver code

# Request array
arr = [ 176, 79, 34, 60,
  92, 11, 41, 114 ]
head = 50

print("Initial position of head:", head)

CLOOK(arr, head)

RSS

它代表着随机调度（random scheduling），就像它的名字一样，它是自然的。它用于调度涉及随机属性的情况，如随机处理时间、随机到期日期、随机权重和随机机器故障，这种算法就很适合。这就是为什么它通常被用于分析和模拟。

LIFO

在 LIFO（Last In, First Out）算法中，最新的工作在现有的工作之前得到服务，也就是说，在得到服务的请求中，最新的或最后进入的工作先得到服务，然后其余的按同样的顺序。

优点：

最大限度地提高位置性（locality）和资源利用率
对其他请求不公平，如果新的请求不断进入，就会造成旧的和现有的请求被饿死。

N-STEP SCAN

它也被称为 N-STEP LOOK 算法。在这个算法中，将为 N 个请求创建一个缓冲区。所有属于缓冲区的请求都会被一次性满足。同时，一旦缓冲区满了，就不会有新的请求被保留在这个缓冲区中，而是被发送到另一个缓冲区。现在，当这 N 个请求被服务后，另一个最重要的 N 个请求的时间就到了，这样，所有的请求都能得到保证的服务。

优点：

完全消除了请求的饥饿现象

FSCAN

该算法使用两个子队列。在扫描过程中，第一个队列中的所有请求都得到了服务，新进入的请求被添加到第二个队列中。所有新的请求都保持暂停状态，直到第一个队列中的现有请求得到服务。

优势：

FSCAN 和 N-Step-SCAN 可以防止 "臂粘性"（arm stickiness，I/O 调度中的现象，调度算法继续为当前扇区或附近的请求提供服务，而推迟其他请求）。

每种算法都有自己独特的方式。总体性能取决于请求的数量和类型。

操作系统原理之磁盘调度 #

目录 #

磁盘调度算法 #

FCFS：先到先服务 #

SSTF：最短寻道时间优先 #

SCAN：扫描算法 #

CSCAN：循环扫描算法 #

LOOK #

CLOOK #

RSS #

LIFO #

N-STEP SCAN #

FSCAN #

操作系统原理之磁盘调度

目录

磁盘调度算法

FCFS：先到先服务

SSTF：最短寻道时间优先

SCAN：扫描算法

CSCAN：循环扫描算法

LOOK

CLOOK

RSS

LIFO

N-STEP SCAN

FSCAN