- 処理装置の高速化に関する技術
- 命令の読み出しから実行までを複数のステージに分け各ステージを並行して実行することで、複数の命令を少しずつ段階をずらしながら同時実行することができるため処理効率が向上する
- CPUのパイプライン処理を有効に機能させるには分岐命令を少なくするようにプログラミングする
-
パイプラインの深さをD、パイプラインピッチをP秒とすると、I個の命令をパイプラインで実行するのに要する時間を表す式(パイプラインの各ステージは1ピッチで処理されるものとし、パイプラインハザードについては考慮しない)
(I+D-1)xP - 遅延分岐
分岐命令に引き続く幾つかの命令を実行してから実際の分岐を行う - ストール
パイプライン制御において必要なデータが確定しない場合の時などに、処理を途中停止すること - パイプラインハザード
パイプライン制御の障害となるもの- データハザード
先行する命令の処理結果を反映しているかどうかが保証されないこと - 制御ハザード
分岐命令の為に、先読みした命令が無駄になること - 構造ハザード
データの読み込みと命令取り出しが同時になり、データバスの競合が発生すること
- データハザード
- スーパスカラ
MPUの高速化技術の一つ
プロセッサ内部の演算装置を複数個用意し、それぞれが同時にパイプライン処理を実行することで、同時に複数の命令を実行可能し、高速化を図る方式 - 投機実行
パイプラインの性能を向上させるための技法のひとつで、分岐条件の結果が決定する前に、分岐先を予測して命令を実行する
- プログラムの実行時に利用される記憶領域
- スタック領域：サブルーチンの戻りアドレスの退避
- ヒープ領域：割当ての順序と開放の順序に関連のないデータ
- CPUのレジスタ：アクセス時間の最も短い記憶装置
- メモリリーク
アプリケーションやOSのバグなどが原因で、動作中に確保した主記憶が開放されないことであり、これが発生すると主記憶中の利用できる部分が減少する - オーバレイ
あらかじめプログラムを幾つかの単位に分けて補助記憶に格納しておき、プログラムの指定に基づいて主記憶との間で出し入れをする - ページング
主記憶とプログラムを固定長の単位に分割し、効率よく記憶管理する。これによって、少ない主記憶で大きなプログラムの実行を可能にする - スワッピング
プログラムを一時的に停止させ、使用中の主記憶の内容を補助記憶に退避する。再開時には、退避した内容を主記憶に再ロードし、元の状態に戻す。
スワッピングが頻繁に発生する場合の対策：主記憶を増設する- スワップアウト（ロールアウト）：優先度の高いプログラムの実行のために、主記憶で実行中のプログラムやデータを補助記憶に待避すること
- スワップイン（ロールイン）：優先度の高いプログラムやデータを主記憶に読み込むこと
- ガーベジコレクション
記憶領域の動的な割り当て及び開放を繰り返しによって発生したどこからも利用されない記憶領域を再び利用可能にする処理
フラグメンテーションの発生によって、合計としては十分な空きメモリ領域があるにもかかわらず、必要とするメモリ領域を獲得できなくなることがある - メモリインタリーブ
コンピュータの高速化技術の一つ
主記憶を複数の独立して動作するグループ（バンク）やアクセス単位に分け、連続したメモリ領域を割り当て、この複数の領域へ並列にアクセスするすることで高速化する方式 - マルチプログラムの多重度の設定を過度に小さくした場合に発生する現象
主記憶の使用率が下がる - 入出力制御
- プログラム制御方式
プロセッサのレジスタを経由して、主記憶装置と入出力装置の間でデータ転送を行う方式 - DMA制御方式
プロセッサ(CPU)を介さずに、システムデバイスなどに接続されたデータ転送専用のハードウェアによって、主記憶装置と入出力装置の間で直接転送を行う方式
シングル転送モードでは、転送ごとにバスの専有権がMPUに返却される
仮想記憶のページサイズを超えてDMA転送を行う場合、誤ったエリアに書き込まれる可能性がある - チャネル制御方式
DMA制御方式の一方式であり、入出力専用のハードウェアがデータ転送制御のためのプログラムを主記憶から自立的に読み出して入出力装置を制御することによって、並行処理の度合いを高めることができる
- プログラム制御方式
- アドレス空間
一つのプロセス内のすべてのスレッドが共有するもの - アドレス指定方法
- 即値オペランド
命令読み出し後のメモリ参照を行わずにデータを取り出すもの - ハッシュ法
関数を用いてレコードのキー値からレコードの格納アドレスを求めることによってアクセスする方法
キーの関数値によって格納場所を決める - シノニム
直接編成ファイルへのレコードの追加で、複数のレコードキー値が同一のレコードアドレスに変換されてしまう現象のこと
シノニムが発生して本来指定されたレコードアドレスに格納できないキー値をシノニムレコードという
- 即値オペランド
- 主記憶領域の使用率を下げるためにデスクトップ上の利用頻度の少ないアイコンを削除したり、不要なウインドウを閉じる
- 入力管理におけるバッファキャッシュ
一度アクセスしたデータブロックは再利用される可能性が高いので、入出力に利用したバッファ領域をすぐには開放せずにしばらく保持する
- 仮想記憶方式によって得られる効果
主記憶の見かけの容量が拡大する - ページング方式
- ページ
仮想記憶方式の一つで仮想アドレス空間を固定長の領域に分割して管理するときの固定長の領域のこと - ページサイズ
コンピュータのアーキテクチャによって取り得るサイズが定められている - ページテーブルから得られる情報
ページが割り付けられている主記憶の実アドレス - ほとんどのプログラムのサイズがページサイズの半分以下のシステムにおいて、ページサイズを半分にしたときに予想されるもの（システムは主記憶が不足しがちで、多重度やスループットなどはシステム性能の限界で運用しているものとする）
ページ内の無駄な空き領域が減少するので、主記憶不足が緩和される - アドレスを変換する処理の順序
- アクセス対象の仮想記憶アドレスに対応するページテーブルの先頭アドレスを得る
- ページテーブルを検索し、該当ページの状態を調べる
- ページフォールトならばページイン処理を行う
- ページ内変位を加えて、求める主記憶アドレスを得る
- ページテーブルに必要な領域の大きさ
ページング方式の仮想記憶において、あるプロセスが仮想アドレス空間全体に対応したページテーブルを持つ場合
2^xバイト = 2^(L-N+E)
(仮想アドレス空間の大きさ：2^Lバイト、ページサイズ：2^Nバイト、ページテーブルの各エントリの大きさ：2^Eバイト）
- ページ
- セグメント方式
主記憶にロールインするときに空き領域がない場合、OSは不要なセグメントをローアウトしてから、該当のセグメントをロールインする - スラッシング
- 仮想記憶システムにおいて実記憶の容量が十分でない場合、プログラムの多重度を増加させるとシステムのオーバヘッドが増加し、アプリケーションのプロセッサ使用率が減少する状態
- ページング方式の仮想記憶において、ページ置き換えの発生頻度が高くなり、システムの処理能力が急激に低下する現象
- 対策：ジョブの多重度を下げて、メモリの使用を制御する
- ページ入れ替え
- LRU(Least Recently Used)
仮想記憶の管理のページ入れ替え方式の一つ
最近参照されていないページは近い将来にも参照される可能性が小さいという推測に基づいて、最後に使われてからの経過時間が最も長いページ（最終参照時刻が最も古いもの）を置き換える - LIFO(Last In Fast Out：後入先出法)
再帰的な処理を実現するための記憶管理方式
実行途中の状態を保存する - FIFO(First In First Out：先入先出法)
仮想記憶のページ置き換えアルゴリズムの一つ
仮想記憶の管理のページ入れ替え方式のうち、古く格納した順に取り出す方式
ある種のページ参照列に対して、割当て主記憶量を増やすと、かえってページフォールトの回数が増加する - LFU(Least Frequency Used)
参照回数が最も少ないものを入れ替えるもの
- LRU(Least Recently Used)
- 記憶保護
仮想記憶方式において、仮想アドレスと物理アドレスとを対応付けするアドレス変換機能に付加情報を与えることで、実現が容易になるもの - ページフォールト
ページ方式の仮想記憶システムにおいて、そこに必要なページ（プログラムやデータ）が主記憶にない状態のこと
- SRAM
フリップフロップ回路を利用した高速なメモリ - DRAM
コンデンサに電荷を蓄えた状態か否かによって1ビットを表現する。主記憶としてよく用いられる
SRAMと比較してビットあたりの面積を小さくできるので、高集積化に適している
構造が単純なので、高集積化することができ、ビット単価を安くできる - フラッシュメモリ
半導体を利用した不揮発性メモリの一種で、電気信号によってデータの書換え、消去が可能なメモリであり、電源を切っても内容を保持できる
USBメモリやSDカード、デジタルカメラで撮影した画像データの保存などに使われる - DDR-SDRAM
クロック信号の立ち上がりと立下りの両方に同期して、データを読み出す
- 使用目的
主記憶へのアクセス速度とプロセッサの処理速度の差を埋める - 効果
主記憶から読み出したデータをキャッシュメモリに保持し、CPUが後で同じデータを読み出すときのデータ転送を高速に行う - 主記憶全域をランダムにアクセスするプログラムでは、キャッシュメモリの効果は小さくなる
- プロセッサにデータを読み込むときにキャッシュメモリがヒットしなかった場合、キャッシュメモリ制御装置は主記憶から所要のデータをブロック転送し、キャッシュメモリに読み込む
- 1次キャッシュと2次キャッシュ
最初にアクセスされるものを1次、そこに必要な情報がない場合に次にアクセスされるものを2次と呼ぶ
- ライトスルー方式
データの書き込み命令実行時に、プロセッサがキャッシュメモリと主記憶の両方にデータを書き込む方式
データをキャッシュメモリと主記憶の両方に同時に書き込むので、主記憶の内容が常に最新となる - ライトバック方式
キャッシュメモリだけを書き換えておき、主記憶の書き換えはブロックの入れ替え時に行う方式
同一番地に繰り返して書き込む場合は、主記憶へのアクセス回数が少なくて済むが、キャッシュメモリと主記憶の不一致状態が続くことがある - フルアソシアティブ
主記憶のデータをキャッシュメモリの空いている任意の場所に配置する - ダイレクトマッピング
主記憶のアドレスから配置するキャッシュのアドレスが一意に決められており、配置するキャッシュのアドレスに別のデータがあればキャッシュには入らない
他のマッピング方式に比べハードウェアが簡単であるが、ヒット率は低くなる可能性がある - セットアソシアティブ
CPUと主記憶の間に置かれるキャッシュメモリにおいて、主記憶のあるブロックをキャッシュメモリの複数の特定ブロックと対応付ける方式
- ECC
メモリアクセスの信頼性を高めるための方式で、データ誤りの自動訂正が可能なもの
- ハミング符号
メモリの誤り制御方式で、2ビットの誤り検出機能と、1ビットの誤り訂正機能を持たせるために用いられる
- 配列は、添え字によってデータを任意の順序で読み出すことができる
- 木構造
階層の上位から下位に節点をたどることによって、データを取り出すことができる- 根付き木
根と呼ばれる特別な接点から木の枝が分かれるように、幾つかの辺が伸び、その先の接点からさらに辺が伸びるということが繰り返されてできた構造-
３種類のポインタ
ポインタが指す相手がいないときはNILが設定される
・接点ｖの親を指すポインタ
・接点ｖの第１子を指すポインタ
・接点ｖの兄弟を指すポインタ
-
３種類のポインタ
-
2分探索木
データの個数が４倍になると、最大探索回数は２回増える
要求量以上の大きさを持つ未使用領域のうちで最小のものを割り当てる最良適合（best-fit）アルゴリズムを用いる場合、未使用領域を管理するためのデータ構造として、メモリ割当て時の処理時間がもっとも短い -
B木
索引部の各ノードのキー値を中心にして、小さい側のレコード数と大きい側のレコード数の比率が、ある範囲内に収まるように動的に再配置しながら格納する -
完全2分木
すべての葉が同じ深さであり、かつ、葉以外のすべての節点が二つの子をもつ要素数ｎの木
どの部分木をとっても左の子孫は親より小さく、右の子孫は親より大きいという関係が保たれている
2分木で探索する場合、ある要素を探索するときの最大比較回数のオーダ：log2n
- 根付き木
-
ハッシュインデックス
B木インデックスと比較して、不等号の条件検索が困難である
- 桁落ち
値がほぼ等しい浮遊小数点数同士の減算において、有効桁が減るために発生する誤差 - 桁上げ
浮動小数点表示において、仮数部の最上位桁が０以外になるように、桁あわせする操作 - 情報落ち
- 絶対値の大きな値と小さな値の加減算をしたときに、絶対値の小さな値が無視されること
- 数多くの数値の加減算を行う場合、情報落ちを防ぐには、絶対値の小さなものから順番に計算するとよい
- 丸め誤差
浮動小数点形式で表現された数値の演算結果において、数表現の桁数に限度があるので、最下位けたより小さい部分について四捨五入や切り上げ、切捨てを行うことによって生じる - 符号なしの2進整数の最大値
１バイトのデータで0のビット数と1のビット数が等しいもののうち符号なしの2進整数として見たときに最大になるものを10進整数として表すと240となる - 8ビットで表される符号なし2進数xが16の倍数であるかどうかを調べる方法
xと2進数00001111のビットごとの論理積をとった結果が0である - 四則演算の式の書き方
- 前置記法：演算子をオペランドの前に書く方法
- 中置記法：演算子をオペランドの間に書く方法
- 後置記法（逆ポーランド記法）：演算子をオペランドの後に書く方法
- 論理演算
AND(論理積)
A・BA B 出力 0 0 0 0 1 0 1 0 0 1 1 1 OR(論理和)
X OR Y = (X NAND Y)NAND(Y NAND Y)
A+BA B 出力 0 0 0 0 1 1 1 0 1 1 1 1 NOT(否定)
AA 出力 0 1 1 0 NAND(否定論理積)
二つの入力と一つの出力を持つ論理回路で、
二つの入力A,Bがともに1のときだけ、
出力Xが0になる
X NAND Y = NOT(X AND Y)
A・BA B 出力 0 0 1 0 1 1 1 0 1 1 1 0 NOR(否定論理和)
A+BA B 出力 0 0 1 0 1 0 1 0 0 1 1 0 XOR(排他的論理和)
A・B＋A・BA B 出力 0 0 0 0 1 1 1 0 1 1 1 0
- 負の整数を表現する代表的な方法
- 2の補数による表現
負数を2の補数で表す16ビットの符号付き固定小数点数の最小値を表すビット列を16進数として表すと8000となる - 1の補数による表現
- 絶対値に符号をつけた表現（左端ビットが0の場合は正、1の場合は負）
- 2の補数による表現
- 浮動小数点表示法における仮数が正規化されている理由
有効数字の桁数を最大に保つため
- スケジューリング方式
- 特定のタスクがCPU資源の割当てを待ち続ける可能性が高いタスクスケジューリング方式
処理予定時間が最も短いタスクから処理を実行する
現在実行中の処理が完結するか、又は何らかの要因によって中断されたとき、次のタスクを開始する - タイムスライシング
CPUの処理時間を微小時間に分割し、それを実行可能な状態にあるタスクに順に割り当てること - ラウンドロビン方式
要求された順番にCPUを割当て、割り当てられた時間を使い切った後は、待ち行列の末尾に回す方式
一定時間ごとにタイマ割り込みを発生させ、実行可能の待ち行列に先頭タスクにCPU資源を割り当てる -
プリエンプティブな処理：ラウンドロビン
プリエンプティブ方式を実現するには、OSがプロセスを強制的に切り替えて実行する機構が必要になる - ノンプリエンプティブな処理：到着順
- 特定のタスクがCPU資源の割当てを待ち続ける可能性が高いタスクスケジューリング方式
- ジョブとジョブステップ
ジョブはコンピュータで実行されるひとまとまりの処理であり、一つ以上のジョブステップから構成される
ジョブステップは、CPU割当てを受ける単位であるタスク又はプロセスから構成される - スレッドとプロセス
同一アドレス空間に含まれているスレッド間の通信は、プロセス間の通信と比較して高速に行われる - プロセス（タスク）管理におけるスレッド
プログラム実行単位を規定する情報（コンテクスト）を切り替える際、プログラムカウンタおよびレジスタ群は切り換えるが、記憶空間はそのままとするもの - 時間監視処理の対象
資源の開放待ち - デバイスドライバをアプリケーションタスクとして作成する場合、通常のタスクと異なり、割込み処理をそのタスク内に定義する
- セマフォ
- 共有資源を管理する手段
- 共用資源を使用するタスク間の排他制御方法として、割り込み禁止よりもセマフォを使用することで、共用資源を使用するタスクだけを排他制御の対象にできる
- P操作：資源のロックを行う
- V操作：待ち状態のプロセスがあれば、そのプロセスをひとつ実行可能状態へ移す（アンロック）
- プログラム制御
- リエントラント（再入可能）
-
リアルタイムシステムにおいて、複数のタスク/プロセスから並行して呼び出される共用ライブラリのプログラムに要求される性質
- 互いに干渉することなく並行して処理することができる
- 複数のタスクから並行して実行されても、それぞれのタスクに正しい結果を返す
- 処理が終了していないプログラムが、別のプログラムから再度呼び出された時に、プログラムが正しく実行される
- 再入可能プログラムを実現するためには、プログラムを手続き部分とデータ部分に分解して、データ部分をプロセスごとにもつ必要がある
- 再入可能プログラムは、局所変数をタスク単位に格納しなければならない
-
リアルタイムシステムにおいて、複数のタスク/プロセスから並行して呼び出される共用ライブラリのプログラムに要求される性質
- リカーシブ（再帰可能）
自分自身を呼び出すことが可能 - リユーザブル（再使用可能）／シリアルリユーザブル（逐次再使用可能）
処理中に、初期値を持つ領域の値を変える場合は、領域を初期値に戻してから処理を終了する必要がある - リロケータブル（再配置可能）
プログラムを実行するために主記憶に読み込んだとき、ロード位置に対応してプログラム内のアドレス情報を補正すること
- リエントラント（再入可能）
- タスクの状態遷移
- 状態遷移
- 実行状態→待ち状態：入出力命令の発行、ページフォールトの発生
- 実行状態→実行可能状態：CPU時間切れ、優先順位の高いタスクが実行可能になった
- 実行可能状態→実行状態：ディスパッチ
- 待ち状態→実行可能状態：入出力完了による割り込み
- 実行状態のタスクがプリエンプションによって他のタスクに実行を中断され、再び実行状態となるまでの状態の変化
実行状態→実行可能状態→実行状態
- メールボックスの受信待ちのタスクが実行状態に遷移する契機となるもの
受信待ちタスクよりも低い優先順位のタスクが同じメールボックスにメッセージを送信した - マルチタスクで動作するコンピュータにおけるタスクの状態遷移で、実行状態のタスクが実行可能状態に遷移するもの
自分より優先度の高いタスクが実行可能状態となった
リアルタイムOSにおいて、優先度の低いタスクが優先度の高いタスクの実行を阻害するのは、優先度の低いタスクが獲得している資源を、優先度の高いタスクがタスクが獲得要求した場合
- 状態遷移
ソートアルゴリズム
- シェルソート
ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し、更に間隔を詰めて同様の操作を行い、間隔が１になるまでこれを繰り返す- データ数÷３ → Ｈとする
- データ列を互いにＨ要素分だけ離れた要素からなる部分列とし、それぞれの部分列を挿入法を用いて整列する
- Ｈ÷３ → Ｈとする
- Ｈが０であればデータ列の整列は完了し、０でなければ２に戻る
- クイックソート
分割統治法を適用した整列（ソート）アルゴリズム
中間的な基準値を決めて、それよりも大きな値を集めた区分と小さな値を集めた区分に要素を振り分ける- 適当な基準値を選び、それより小さな値のグループと大きな値のグループにデータを分割する
- 同様にしてグループの中で基準値を選び、それぞれのグループを分割する
- この操作を繰り返していく方法
- ヒープソート
未整列の部分を順序木に構成し、そこから最大値又は最小値を取り出して既整列の部分に移す。
これらの操作を繰り返して、未整列部分を縮めていく - バブルソート
隣り合う要素を比較して、大小の順が逆であれば、それらの要素を入れ替えるという操作を繰り返して行う - 単純挿入法
ｎ個のデータを整列するとき、比較回数が最悪の場合でO（n^2)、最良の場合でO(n)となる
- クロック周波数
- クロック周波数によって CPU の命令実行タイミングが変化する
- クロック周波数が高くなるほどパソコンの命令実行速度が向上する
- CPUのクロック周波数と、主記憶を接続するシステムバスのクロック周波数は同一でなくてもよい
- 命令デコーダ
プロセッサの制御機構に分類されるもの - 密結合マルチプロセッサ
複数の同種のプロセッサが主記憶を共有し、単一のOSで制御されることによって処理能力を高めるコンピュータシステムの構成
システム内のタスクは、基本的にどのプロセッサでも実行できるので、細かい単位で負荷を分散することで処理能力を向上させる- 密結合マルチプロセッサシステム環境で動作するOS
各タスクはどのプロセッサでも実行できるのでタスク間で同期を取る機能が必要になる - シングルプロセッサシステムの性能と比較したとき、主記憶のアクセスに対する排他制御のため、密結合マルチプロセッサ1台あたりの性能が低下する
- 主記憶へのアクセス競合のため、結合マルチプロセッサの性能が、1台当たりのプロセッサの性能とプロセッサ数の積に等しくならない
- 密結合マルチプロセッサシステム環境で動作するOS
- 疎結合マルチプロセッサ
主記憶を共有せずにプロセッサごとに主記憶を占有し、プロセッサ間は高速なネットワークで結合する - オーバードライブプロセッサ
CPUに装着することで機能を強化することのできるデバイス - マイクロプロセッサの省電力技術
CMOSを使用したプロセッサでは、動作周波数を低くすることによって、論理反転時の電流が減少し、消費電力を少なくすることができる - コプロセッサ
マイクロプロセッサの性能を強化するための特定分野に特化した補助プロセッサ - MPU
- RISCアーキテクチャのMPUの特徴
ハードウェア回路とパイプラインの技術を使い、1命令あたりおおよそ1クロックで実行できる
パイプライン処理に適している - ウェイト機能とレディ機能の使い方
アクセス速度の遅いメモリにMPUを同期させる - ターゲットMPUのシミュレータ
マイコン応用システム開発のデバッグ段階で使用するツール
ソフトウェアのデバッグをクロス開発環境で行える - MPUがもつウェイト機能とレディ機能の使い方
アクセス速度の遅いメモリにMPUを同期させる
- RISCアーキテクチャのMPUの特徴
- MIMD
商用超並列コンピュータの多くが採用しているマルチプロセッサの処理方式の一つで、プロセッサごとに異なる命令を並列に実行させる - SIMD
複数のデータに対して一つの命令で同じ処理を並列に行う
ファイルシステム内の特定のファイルを指定するためには、ディレクトリパスを指定する
親ディレクトリと子ディレクトリの間では、親から子へ、子から親への両方向の参照が可能である
- ファイル、フィールド（項目）、レコードの関係
ファイル＞レコード＞フィールド
- ファイル管理
- 磁気ディスクの空き容量を管理している領域管理テーブル、ファイル名やファイルの実体を示すディレクトリ、そしてファイルの実体などの関連した情報を磁気ディスクに作成する
- コンピュータのシステムダウンが起きたとしても、ファイルシステムに障害を引き起こすことのない書き込み順序
領域管理テーブル→ファイル実体→ディレクトリ
- フラグメンテーション
- ディスクに対して書き込みと削除を繰り返し行なうことで、ディスク内でのファイルの配置が不連続になること
- フラグメンテーションを解消するには、専用ツールなどを使用して、フラグメンテーションが発生したファイルを連続した領域に再配置すればよい
-
ファイル作成時に、一つの連続領域でなく、小さく分断された領域が割り当てられたので、ファイルのアクセス効率が低下している場合の対策
ファイルや空きを連続した領域に割り当て直す -
磁気ディスクのデフラグメンテーションをすることによって、期待できる効果
ファイルを連続的に読み込むときのアクセス時間が短くなる -
デフラグメンテーション
物理的に分散して格納されているファイルを連続した領域に再配置する処理
- 論理フォーマット
- OS固有のファイルシステムの管理領域や実際に記録されるデータの論理的な位置を設定する
- ファイル領域割当て方式のうち、連続したブロックにすき間なく格納する方式と比較したときの、ブロックをリンクで連結する方式の特徴
ファイルの作成と削除を繰り返しても、ファイルに割り当てられない無駄な領域が発生しない
