待ち行列モデル(平成24年春期 午前2問目)
待ち行列モデルは、銀行のATMに並ぶ顧客の列，レジに並ぶ顧客の列などのように順番待ちの行列を確率モデル化したものです。情報処理の分野ではトランザクションがサーバ処理を待つケースなどがあり、システムの性能評価の1つとして待ち行列モデルを用いて「待ち時間」や「待ち行列」の長さなどの計算を行うことがあります。 「M/M/1」の部分はケンドール記号という確率分布記号を用いて
到着分布／サービス時間分布／窓口の数
の組合せでモデルを表現します。「M」はMarkovianの略で到着がポアソン分布となるランダム型，到着間隔は指数分布に従うことを表しています。
確率分布には次のように離散型と連続型があります。 離散型確率分布 サイコロを投げた時に出る目の数字(1,2,3…)など確率変数が不連続(離散)の場合の確率分布。 連続型確率分布 時間や距離など確率変数が連続している場合の確率分布。 M/M/1の待ち行列モデルにおいては、到着率は確率変数(人数)が離散値なので離散型確率分布の「ポアソン分布」，サービス時間分布は確率分布が連続値(時間)なので連続型確率分布の「指数分布」ということを覚えておきましょう。
キャッシュメモリのマッピング
イレクトマップ(マッピング)
キャッシュメモリへの割付方式のひとつで、主記憶のアドレスにハッシュ演算を行い、その結果から対応するキャッシュメモリのアドレスを算出します。ハッシュ演算で計算するので主記憶のアドレスとキャッシュメモリのアドレスが１対１で対応します。
フルアソシアティブ
主記憶のブロックが、キャッシュメモリのどのブロックにも対応付けられる方式です。 ハッシュ演算の結果によらずどこにも書き込めるので、キャッシュメモリの使用率が向上にしますが、ダイレクトマッピングよりも計算にかかるオーバーヘッドが増加し、システムの仕組みを複雑になってしまうデメリットもあります。
セットアソシアティブ
連続したキャッシュブロックをセットとしてまとめ、その中であればどこのブロックでも格納できるようにした方式です。 ダイレクトマッピングでは、ハッシュ関数で算出されたブロックに既にデータが存在する場合には追い出しが発生しますが、セットアソシアティブでは、一つのセットに複数のブロックがあるので追い出しをしなくてもデータを格納できます。 詳しく
スーパースカラ
複数のパイプラインを用いて，同時に複数の命令を実行可能にすることによって高速化を図る方式である。 詳しく
