HDDのアクセス時間とスケジューリング
要求の順序と転送単位を変え、ヘッド移動・回転待ち・転送の時間を分けて計算します。
説明
HDDでは読み書きする位置へヘッドを移すシーク、目的のセクタが回ってくるまでの回転待ち、データ本体の転送が必要です。連続転送の速度が高くても、小さい要求で機械的な待ちを毎回払うと全体は遅くなります。
7200rpm、転送速度100MB/sの仮定を使い、4KiBの要求を4か所へ出します。先着順と近い位置を優先する順序でヘッド移動を計算し、要求をまとめた場合も比較します。装置内の実際の配置はLBAだけから直接分からないため、ここでは位置番号を明示したモデルです。
1回転数から待ち時間を求める
7200rpmは1分に7200回転です。1回転の時間を求め、開始位相が一様なら平均回転待ちはその半分とします。
rpm = 7200仮定する回転数; revolution_ms = 60000/rpm1回転のミリ秒; mean_rotation_ms = revolution_ms/2一様な開始位相での平均; revolution_ms,mean_rotation_ms回転時間と平均待ち1回転は約8.333ms、平均回転待ちは約4.167msです。常に半回転待つという意味ではなく、位相を一様とした平均です。要求順序で位相が変わる場合までこの値だけで表せるわけではありません。
2データ転送だけの時間
4KiBは4096バイト、100MB/sは毎秒100000000バイトとします。秒をミリ秒へ直して求めます。
request_bytes = 4096; bytes_per_second = 100_000_000要求サイズと転送速度; transfer_ms = 1000*request_bytes/bytes_per_second転送に必要なミリ秒; transfer_ms,mean_rotation_ms/transfer_ms転送時間と待ちとの比転送本体は0.04096msです。平均回転待ちはその約102倍になります。小さいランダムI/Oでは、転送レートだけを見ても所要時間を説明できません。
3ヘッド移動を要求順に記録
開始位置50、要求位置10・90・20・80を使います。移動距離は前の位置との差の絶対値です。
start = 50; requests = [10,90,20,80]開始位置と先着順の要求; positions = [start]+requests開始位置を先頭へ; fcfs_moves = [(a,b,abs(b-a)) for a,b in zip(positions,positions[1:])]各移動の距離; fcfs_moves,sum(distance for a,b,distance in fcfs_moves)移動表と合計先着順の移動は40・80・70・60、合計250です。同じ4要求でも、遠い位置を往復する順序になっています。
4シーク・回転待ち・転送を合算
1回のシークを2ms+距離×0.05msとする簡単なモデルです。各要求に平均回転待ちと転送時間を加えます。
seek_ms = lambda distance: 2+0.05*distance仮定するシーク時間; fcfs_seek = sum(seek_ms(distance) for a,b,distance in fcfs_moves)全シーク; fcfs_total = fcfs_seek+4*(mean_rotation_ms+transfer_ms)回転待ちと転送を加算; fcfs_seek,fcfs_total内訳と合計シーク合計20.5ms、全体約37.33msです。固定の2msは移動の開始・整定などをまとめた仮定で、実機のシーク時間が距離に単純比例するという仕様ではありません。
5近い要求から選ぶ
現在位置から最も近い未処理要求を選ぶSSTFを計算します。同距離なら位置番号の小さい方を選びます。
def nearest_order(start,requests):開始位置と要求列
pending = list(requests)未処理のコピー
head = start現在位置
moves = []移動履歴
while pending:全件が終わるまで
target = min(pending,key=lambda x:(abs(x-head),x))最短距離・同距離なら小さい位置
moves.append((head,target,abs(target-head)))移動を記録
pending.remove(target)処理済みを除く
head = target現在位置を更新
return moves移動表次の選択は直前の完了位置から決めます。開始位置50からは20と80が同距離なので、今回の規則では20を選びます。
6同じ要求数で待ちを比較
SSTFの移動距離と合計時間を、先着順と同じ時間モデルで計算します。
sstf_moves = nearest_order(start,requests)近い順に並べる; sstf_total = sum(seek_ms(d) for a,b,d in sstf_moves)+4*(mean_rotation_ms+transfer_ms)同じモデルで合計; sstf_moves,sum(d for a,b,d in sstf_moves),sstf_total,fcfs_total-sstf_total順序・距離・時間・短縮量移動順は20→10→80→90、総距離120、全体約30.83msです。シークは短くなりましたが、回転待ちの位相まで最適化した結果ではありません。実際の装置は内部キューや物理配置も考慮します。
7連続範囲をまとめて転送する
64KiBを4KiBずつ16回、毎回独立の位置合わせ待ちがある場合と、一回の連続転送で読む場合を比べます。各位置合わせはシーク2msと平均回転待ちとします。
chunk_count = 16合計64KiB; separate_ms = chunk_count*(2+mean_rotation_ms+transfer_ms)各要求で位置合わせ; combined_ms = 2+mean_rotation_ms+chunk_count*transfer_ms一回の連続転送; separate_ms,combined_ms仮定ごとの時間約99.32msと6.82msです。後者は位置合わせを一度で済ませる仮定なので差が大きくなります。実際にはOSや装置が小要求を結合したりキャッシュしたりするため、API呼出し16回が必ず16回の機械待ちになるとは限りません。
8短い移動の優先と遠い要求の待ち
遠い位置90の要求が待っている間、現在位置に近い1〜5が順次到着する例です。各回の距離を比較します。
near_arrivals = [1,2,3,4,5]; heads = [0]+near_arrivals[:-1]新しい要求と直前の位置; [(head,near,abs(near-head),abs(90-head)) for head,near in zip(heads,near_arrivals)]現在位置・新要求・近傍距離・遠方距離各回で新しい近傍要求の距離1が選ばれ、90は待ち続けます。近傍要求が途切れなければ飢餓につながるため、待ち時間の上限や一定方向への走査を考える方式もあります。総移動の短さと公平性は別の評価軸です。
まとめ
小さい要求では、転送本体よりシークや回転待ちが支配的になることがあります。
要求順序と結合によって機械的な待ちを減らせますが、モデルの仮定を確認します。
近傍優先の総移動削減と、遠い要求を待たせない公平性を両方考慮します。
操作履歴と解説を振り返れます。
Python 3
rpm = 7200; revolution_ms = 60000/rpm; mean_rotation_ms = revolution_ms/2; revolution_ms,mean_rotation_ms(8.333333333333334, 4.166666666666667)
request_bytes = 4096; bytes_per_second = 100_000_000; transfer_ms = 1000*request_bytes/bytes_per_second; transfer_ms,mean_rotation_ms/transfer_ms(0.04096, 101.72526041666667)
start = 50; requests = [10,90,20,80]; positions = [start]+requests; fcfs_moves = [(a,b,abs(b-a)) for a,b in zip(positions,positions[1:])]; fcfs_moves,sum(distance for a,b,distance in fcfs_moves)([(50, 10, 40), (10, 90, 80), (90, 20, 70), (20, 80, 60)], 250)
seek_ms = lambda distance: 2+0.05*distance; fcfs_seek = sum(seek_ms(distance) for a,b,distance in fcfs_moves); fcfs_total = fcfs_seek+4*(mean_rotation_ms+transfer_ms); fcfs_seek,fcfs_total(20.5, 37.330506666666665)
def nearest_order(start,requests):
pending = list(requests)
head = start
moves = []
while pending:
target = min(pending,key=lambda x:(abs(x-head),x))
moves.append((head,target,abs(target-head)))
pending.remove(target)
head = target
return movessstf_moves = nearest_order(start,requests); sstf_total = sum(seek_ms(d) for a,b,d in sstf_moves)+4*(mean_rotation_ms+transfer_ms); sstf_moves,sum(d for a,b,d in sstf_moves),sstf_total,fcfs_total-sstf_total([(50, 20, 30), (20, 10, 10), (10, 80, 70), (80, 90, 10)], 120, 30.83050666666667, 6.4999999999999964)
chunk_count = 16; separate_ms = chunk_count*(2+mean_rotation_ms+transfer_ms); combined_ms = 2+mean_rotation_ms+chunk_count*transfer_ms; separate_ms,combined_ms(99.32202666666667, 6.822026666666667)
near_arrivals = [1,2,3,4,5]; heads = [0]+near_arrivals[:-1]; [(head,near,abs(near-head),abs(90-head)) for head,near in zip(heads,near_arrivals)][(0, 1, 1, 90), (1, 2, 1, 89), (2, 3, 1, 88), (3, 4, 1, 87), (4, 5, 1, 86)]
演習完了