7.2.1 ブロッキング
{吉沢3.2.1節} レコードの概念： OSが利用者プログラムに対して入出力機能を提供する際の入出力の基 本単位(i.e.１回の入出力操作でOSとの間で受け渡しするデータ)を論理レコード(logical
record)、またはレコードと呼ぶ。 '
&
$
% 補足：「レコード」という用語は次の様な意味で使わ
れることもある。
• ファイルを構成する際の 基本単位。
• プログラミングにおいて、関連するデータを1つ にまとめたもの。Pascal等では「レコード」と呼 ぶが、C言語では構造体と呼んでいる。
ブロッキング： 入出力実行回数を減らして総計の入出力時間を短縮させることをねらっ て、複数のレコードをまとめて1回の入出力を行う方法がある。これをブロッキングとい う。 (
ブロック · · · 入出力の単位となるレコードの集まり
ブロッキング・ファクタ · · · 1つのブロックの中のレコード数
7.2. ファイルアクセス高速化の工夫 53
レコード レコード
...
レコード ブロック磁気テープにブロック列を記録する場合： ブロックとブロックの間にIBG(Inter Block Gap)あるいはIRG (Inter Record Gap)と呼ばれる領域をおく。
=⇒磁気テープに格納される実効的なデータの割合= ブロックサイズ
ブロックサイズ+ IBGサイズ
ブロック ブロック ブロック ブロック
...
...
IBG IBG IBG IBG IBGブロッキング・ファクタをどう選ぶか？：
ブロッキング・ファクタが大きければ大きい程1つのレコードに対する平均のアクセス時 間を短くすることが出来る。 しかし、次の点も考慮しなければならない。
• ブロックの先頭レコードに対するアクセス時間が大きくなり過ぎないか？
• 入出力バッファのサイズが大きくなり過ぎないか？
• 実際のCPUオーバヘッドはどの程度になるのか。(ブロッキングの効果はどの程度か。)
'
&
$
% 補足：
1つのレコードに対する平均の アクセス時間の改善 (CPUオーバヘッドの改善)
tradeoff
←→
ブロックの先頭レコードに対する アクセス時間の改善 入出力バッファのサイズを小さくできる
7.2.2 バッファリング
{野口5.3節,吉沢3.2.2節,清水5.1–2節} 直接メモリアクセス(DMA, p.39)の様に入出力データを一旦主記憶内の特定の領域(バッ ファ,buffer)に蓄え、入出力要求と実際の入出力動作を非同期に行なう方式、すなわち
• 入出力コントローラによる バッファ←→入出力装置間のデータ転送と
• CPUによる プロセスの作業領域←→バッファ間のデータ転送
を並行して行なう方式を一般にバッファリングと呼ぶ。バッファリングによって、CPU はデータをバッファ上に出力するだけで次の処理に移れるようになり、実際に出力される まで待つ必要がなくなる。 '
&
$
% 補足：入力の場合は、応用プログラムからの入力要求に先だって、OS側
でバッファにデータを先読みし、次の入力要求に対して待ちが起こ らないようにする。但し、プログラムの動作を完全に予測すること はできないので、先読みが無駄に終ることもある。
1面バッファリング(single buffering)： 入力用,出力用に容量が1ブロックのバッファ が1面ずつ用意されている場合を考える。この場合に4つのブロックから構成されるファ イルを読み出そうとすると、
• DMAコントローラによる 磁気ディスク−→バッファ 間のデータ転送と
• CPUによる バッファ−→プロセスの作業領域 間のデータ転送
が入出力コントローラとCPUにより交互に繰り返される。
プロセス
磁気ディスク DMAコントローラ
主記憶
OS領域 入力用バッファ 出力用バッファ
作業領域 CPU
バス
これらの転送は
入出力コントローラが行なう これらの転送は CPUが行なう
'
&
$
% 注目：
DMAコントローラとCPUは(データ保全のため?) 同時に1つのバッファにアクセスしない。
この様に、容量が1ブロックのバッファが1個だとCPUが プロセスの作業領域←→バッ ファ 間のデータ転送を行っている間は(CPUに比べて低速な)入出力装置が遊んでしまう ことになる。
プロセスの 作業領域へ の転送 バッファへ のブロック の読み込み
ファイル読み出しにかかった時間 CPU
DMAコントローラ
待ち 待ち 待ち 待ち
遊び 遊
び 遊
び
2面バッファリング(double buffering)： 容量が1ブロックのバッファを2個用意し て、バッファが満杯になるか入出力要求が出されるかする毎にバッファを交互に切替えて 使うようにすれば、CPUがバッファにアクセスしている時にも入出力装置を動作させる ことが出来るようになる。
プロセスの 作業領域へ の転送 バッファ1へ のブロック の読み込み
ファイル読み出しにかかった時間 CPU
DMAコントローラ
待ち
バッファ2へ のブロック の読み込み
待ち 待ち 待ち
多面バッファリング： 出力の場合は、バッファの個数が多いほど出力待ちの可能性が少 なくなり、効率の良いプログラム実行が可能になる。一般に、複数個のバッファを用いた バッファリングを多面バッファリングと呼ぶ。
7.2. ファイルアクセス高速化の工夫 55
'
&
$
% 補足：
バッファリングに関しては、読む本によって用語の使い方が違う。例えば、
• 岩波情報科学辞典では、バッファを複数個もつことにより入出力の効率を上 げる方法を「バッファリング」と呼んでいる。
• 清水5.2節では、プロセス内の作業領域もバッファと見て、プロセス内の作業 領域とOS内に用意される転送用バッファを一組にして使用する方法を「ダ ブルバッファリング」と呼んでいる。
7.2.3 キャッシング
{吉沢3.2.3節} 外部記憶のブロックを一時的に置くための領域(キャッシュ,cache,と呼ぶ)を主記憶上 に用意し、そこに外部記憶上の頻繁にアクセスするブロック(ホットスポットと呼ぶ)を 保持する。 これをキャシング(caching)と言う。 (=⇒1.1節, 6.7節)
'
&
$
% p.6からの引用：
キャッシュ記憶： CPUから主記憶内のデータへのアクセス速度を見かけ上高 速化するための高速記憶。
• アクセスされた主記憶の情報はキャッシュ記憶内に一時的に格納され、近い 将来再びアクセスされた時はキャッシュ記憶から取り出される。
• メモリへのアクセス回数を抑えるため、キャッシュ記憶に無いデータをメモ リから読み込む場合には、必要とするデータだけでなく近くのデータも一 緒に読み込んで複製しておく。
• プログラムの実行は連続して進むことが多く、また、短い時間内では処理 するデータも一部のものに集中することが多い。[こういう性質をプログラ ムの局所参照性(program locality)と言う。吉沢p.191〜192を参照。] プ ログラムの実行が局所参照性を持っているので、キャッシュ記憶を用いるこ とによって主記憶内のデータへの実際上のアクセススピードを上げること が可能になる。
キャッシュを用いた場合の注意点：
• キャッシュ上の情報と磁気ディスクなどの記録媒体上の情報が一致しないことがある。
=⇒システムダウンの時は新しい情報が失われてしまう。
'
&
$
% 補足：
ブロックへの書き込みもキャッシュ上のブロックに対して行 う。従って、何らかの時点で、キャッシュ上の情報更新の結 果を記録媒体上に書き込まなければならない。
• キャッシュ内のブロック領域が不足した時にどのブロックを解放するかをうまく決め
ないといけない。 '
&
$
% 補足：
「最近使用されたブロックほど近い将来も再度参照される可 能性が高い」という仮定の下に、LRU(Least Recently Used) アルゴリズムで解放するブロックを決めることがある。
UNIXの場合：
• カーネルが自動的に入出力のキャッシングを行っている。
• 一般的なファイルアクセスを行っている場合はキャッシュに情報が存在する。
• キャッシュ上の情報と磁気ディスクなどの記録媒体上の情報の不一致を強制的に解消 するためには、システムコール sync( ) を実行する。