【基本・応用情報技術者】論理回路

資格資格-基本情報技術者試験資格-応用情報技術者試験

こんにちは。たろすです。

今回は論理回路について説明します。

論理式の知識が前提になるので、論理式がわかっていない方はこちらから押さえておきましょう。

talosta.hatenablog.com

論理ゲートの種類
- AND
- OR
- NOT
- NAND
- NOR
- XOR
例題
- 問題
- 解説
おわりに
おすすめの学習本

論理ゲートの種類

論理ゲートは6種類あります。

基本情報技術者試験や応用情報技術者試験ではMIL記号と呼ばれる表記で論理回路が書かれているのですが、それぞれの記号がなにを表しているのかは提示されるため必ずしも覚える必要はありません。

ただ時間をかけないためにも覚えることを推奨します。

AND

f:id:talosta:20210607154658p:plain

$X = A \cdot B$ を表しています。

OR

f:id:talosta:20210607154933p:plain

$X = A + B$ を表しています。

NOT

f:id:talosta:20210607155110p:plain

$X = \overline{A}$ を表しています。

NAND

f:id:talosta:20210607155327p:plain

$X = \overline{A \cdot B}$ を表しています。

NOR

f:id:talosta:20210607155432p:plain

$X = \overline{A + B}$ を表しています。

XOR

f:id:talosta:20210607155537p:plain

$X = A \oplus B$ を表しています。

例題

論理回路図を使った問題を解いてみましょう。

問題

図に示すディジタル回路と等価な論理式はどれか。ここで，論理式中の"・"は論理積，"＋"は論理和，XはXの否定を表す。

f:id:talosta:20210607160836p:plain

ア． $X = A \cdot B + \overline{A \cdot B}$
イ． $X = A \cdot B + \overline{A} \cdot \overline{B}$
ウ． $X = A \cdot \overline{B} + \overline{A} \cdot B$
エ． $X = (\overline{A} + B) \cdot (A + \overline{B})$

（出典：平成29年度秋期基本情報技術者試験午前問23）

解説

各ゲートの入力と出力を見ていきましょう。

二つのNOTゲートにはそれぞれ $A$ と $B$ が入力され、 $\overline{A}$ と $\overline{B}$ が出力されます。

f:id:talosta:20210607162019p:plain

一つ目のORゲートには $\overline{A}$ と $\overline{B}$ が入力され、 $\overline{A} + \overline{B}$ が出力されます。

f:id:talosta:20210607162857p:plain

上側のANDゲートには $A$ と $\overline{A} + \overline{B}$ が入力され、 $A(\overline{A} + \overline{B})$ が出力されます。

下側のANDゲートには $B$ と $\overline{A} + \overline{B}$ が入力され、 $B(\overline{A} + \overline{B})$ が出力されます。

f:id:talosta:20210607162932p:plain

最後のORゲートには $A(\overline{A} + \overline{B})$ と $B(\overline{A} + \overline{B})$ が入力され、 $A(\overline{A} + \overline{B}) + B(\overline{A} + \overline{B})$ が出力されます。

f:id:talosta:20210607163019p:plain

もちろん選択肢にこの回答はないため、変形する必要があります。

$\begin{eqnarray} A(\overline{A} + \overline{B}) + B(\overline{A} + \overline{B}) &=& A \cdot \overline{A} + A \cdot \overline{B} + \overline{A} \cdot B + B \cdot \overline{B} \\ &=& 0 + A \cdot \overline{B} + \overline{A} \cdot B + 0 \\ &=& A \cdot \overline{B} + \overline{A} \cdot B \end{eqnarray}$

したがって答えはウになります。

おわりに

今回は論理回路について説明しました。

毎回1問は出るのでできるようにしておきましょう。

あわせて読みたい

talosta.hatenablog.com

【基本・応用情報技術者】ラウンドロビン方式

資格資格-基本情報技術者試験資格-応用情報技術者試験

こんにちは。たろすです。

今回はスケジューリングの方式のひとつ、ラウンドロビン方式について説明をします。

スケジューリングの説明は以下の記事でしています。

https://talosta.hatenablog.com/entry/schedulingtalosta.hatenablog.com

ラウンドロビン方式
例題
- 問題
- 解説
おわりに
おすすめの学習本

ラウンドロビン方式

プロセスにCPUを割り当てられる時間（=タイムクォンタム）が決められており、タイムクォンタム分実行したら待ち行列の最後尾に並べる方式です。

ラウンドロビン方式は基本情報技術者試験や応用情報技術者試験でよく問われます。

なぜかというと、他の方式と比べると複雑だからです。

なので例題を解きながら詳しく見ていきましょう。

例題

問題

タイムクウォンタムが2秒のラウンドロビン方式で処理されるタイムシェアリングシステムにおいて，プロセス1～3が逐次生成されるとき，プロセス2が終了するのはプロセス2の生成時刻から何秒後か。ここで，各プロセスはCPU処理だけで構成され，OSのオーバヘッドは考慮しないものとする。また，新しいプロセスの生成と中断されたプロセスの再開が同時に生じた場合には，新しく生成されたプロセスを優先するものとする。

プロセス	生成時刻	単独で処理された場合の時間
1	0秒後	5秒
2	3秒後	7秒
3	6秒後	5秒

ア．12
イ．14
ウ．16
エ．17

（出典：平成28年度秋期応用情報技術者試験午前問19）

解説

まず最初に生成時刻が0秒後のプロセス1が実行されます。

タイムクォンタムは2秒なので2秒間だけ実行されます。

f:id:talosta:20210529111525p:plain
待ち行列：プロセス1

しかし、プロセス1がタイムクォンタムを使い切った時点で他のプロセスはまだ生成されていません。

したがって、もう一度プロセス1が実行されます。

プロセス1を実行している間にプロセス2も生成されます。

f:id:talosta:20210529111841p:plain
待ち行列：プロセス2、プロセス1

プロセス2が生成されて待ち行列の先頭に並んでいるため、次はプロセス2が実行されます。

さらに、プロセス2がタイムクォンタムを使い切ると同時にプロセス3が生成されます。

f:id:talosta:20210529112623p:plain
待ち行列：プロセス1、プロセス2（、プロセス3）

問題文に「新しいプロセスの生成と中断されたプロセスの再開が同時に生じた場合には，新しく生成されたプロセスを優先するものとする」

とあるので、次はプロセス3が実行され、タイムクォンタムを使い切ると待ち行列の最後尾に並びます。

f:id:talosta:20210529113106p:plain
待ち行列：プロセス1、プロセス2、プロセス3

続いて、待ち行列の先頭のプロセス1が実行されます。

ただし、プロセス1の残り時間は1秒なので、1秒だけ実行されます。

f:id:talosta:20210529113735p:plain
待ち行列：プロセス2、プロセス3

後はプロセス2とプロセス3を交互に繰り返していきます。

f:id:talosta:20210529114039p:plain
待ち行列：プロセス3、プロセス2

f:id:talosta:20210529114417p:plain
待ち行列：プロセス2、プロセス3

f:id:talosta:20210529114542p:plain
待ち行列：プロセス3、プロセス2

f:id:talosta:20210529114704p:plain
待ち行列：プロセス2

f:id:talosta:20210529114831p:plain
待ち行列：なし

プロセス2の生成時刻は3、終了時刻は17なので答えは「イ．14」になります。

おわりに

今回はラウンドロビン方式について説明しました。

スケジューリング方式の中でも比較的問われやすいので覚えておきましょう。

あわせて読みたい

talosta.hatenablog.com

【基本・応用情報技術者】スケジューリング

資格資格-基本情報技術者試験資格-応用情報技術者試験

こんにちは。たろすです。

今回はスケジューリングの説明をします。

プロセス
スケジューリング
おわりに
おすすめの学習本

プロセス

スケジューリングの説明する前にプロセスについて説明します。

プロセスはプログラムを実行する際に、CPUが処理する実行単位です。

プロセスは以下の状態をとります。

待ち状態：CPUが割り当てられても実行できない状態

実行可能状態：CPUが割り当てられれば実行できる状態

実行状態：CPUが割り当てられていて実行中の状態

これらの状態は図のような関係性にあります。

f:id:talosta:20210529100605p:plain

スケジューリング

プロセスをどのような順番で処理するかを決めることです。

スケジューリングにはいくつか種類があるので、それぞれ説明していきます。

到着順方式

名前の通り、到着順（=実行可能状態になった順）に実行していく方式です。

優先度順方式

各プロセスに予め優先度を設定しておき、優先度が高いものから実行していく方式です。

優先度順方式には静的優先度順方式と動的優先度順方式があります。

静的優先度順方式は優先度が一度決められたら変わることはありません。

動的優先度順方式は実行可能状態の時間が長いほど、プロセスの優先度を高く設定し直します。

処理時間順方式

所持時間が短いものから実行していく方式です。

ラウンドロビン方式

プロセスにCPUを割り当てられる時間（=タイムクォンタム）が決められており、タイムクォンタム分実行したら待ち行列の最後尾に並べる方式です。

おわりに

今回はスケジューリングの説明をしました。

ラウンドロビン方式はよく問われるので、次回詳しく説明します。

あわせて読みたい

talosta.hatenablog.com

【基本・応用情報技術者】直列接続システムと並列接続システムの稼働率

資格資格-基本情報技術者試験資格-応用情報技術者試験

こんにちは。たろすです。

今回は直列接続システムと並列接続システムの稼働率の説明をします。

稼働率とは？という方はこちらからご覧ください。

https://talosta.hatenablog.com/entry/rasistalosta.hatenablog.com

直列接続システムの稼働率
並列接続システムの稼働率
例題
- 問題
- 解答
おわりに
おすすめの学習本

直列接続システムの稼働率

図のように機器Aと機器Bが直列接続になっている場合、機器Aと機器Bはどちらも稼働していないとシステムとして稼働しているとは言えません。

f:id:talosta:20210522102700p:plain

したがって、システム全体としての稼働率は以下のように求められます。

$システムの稼働率 = 機器Aの稼働率 \times 機器Bの稼働率$

機器が3つ、4つと直列で接続されている場合もすべての稼働率を掛け合わせることでシステム全体の稼働率を算出できます。

並列接続システムの稼働率

図のように機器Aと機器Bが並列接続になっている場合、機器Aと機器Bのどちらかが稼働していればシステムは稼働していると言えます。

f:id:talosta:20210522103504p:plain

つまり、システム全体の稼働率は機器Aと機器Bの両方が稼働していない確率を1から引くことで算出できます。

機器が稼働していない確率は(1 - 機器の稼働率)で求められるので、システムの稼働率は以下の式で求められます。

$システムの稼働率 = 1- (1 - 機器Aの稼働率) \times (1 - 機器Bの稼働率)$

機器が3つ、4つと並列で接続されている場合もすべての機器の稼働していない確率（1 - 機器の稼働率）を掛け合わせて1から引くことで全体の稼働率を算出できます。

例題

基本情報技術者試験や応用情報技術者試験で実際に出てくるような問題を解いてみます。

問題

機器AのMTBFは990時間、MTTRは10時間である。また、機器BのBTBFは980時間、MTTRは20時間である。機器Aと機器Bを用いて以下の図のようなシステムを構成したときのシステム全体の稼働率を求めよ。

f:id:talosta:20210522104517p:plain

解答

まず、機器Aと機器Bのそれぞれの稼働率を求めます。

$\begin{eqnarray} 機器Aの稼働率 &=& \frac{990}{990 + 10} \\ &=& 0.99 \end{eqnarray}$

$\begin{eqnarray} 機器Bの稼働率 &=& \frac{980}{980 + 20} \\ &=& 0.98 \end{eqnarray}$

次に並列部分の稼働率を求めます。

$\begin{eqnarray} 並列部分の稼働率 &=& 1 - (1 - 0.99) \times (1 - 0.98) \\ &=& 1 - 0.01 \times 0.02 \\ &=& 0.9998 \end{eqnarray}$

続いて、機器Ａと機器Ｂの並列部分を一つの機器とみなして機器Ｃとします。

f:id:talosta:20210522105302p:plain

するとこのシステムは稼働率0.9998の機器Cと稼働率0.99の機器Aが直列接続されていると考えることができます。

したがって、システム全体の稼働率は

$\begin{eqnarray} システム全体の稼働率 &=& 0.9998 \times 0.99 \\ &=& 0.989802 \end{eqnarray}$

となります。

おわりに

今回は応用的な稼働率の計算を行いました。

よく出るのでしっかり覚えておきましょう。

あわせて読みたい

talosta.hatenablog.com

【基本・応用情報技術者】システムの信頼性評価

資格資格-基本情報技術者試験資格-応用情報技術者試験

こんにちは。たろすです。

今回はシステムの信頼性評価について説明します。

信頼性評価指標
- MTBF（Mean Time Btween Failures：平均故障間隔）
- MTTR（Mean Time To Repair：平均修理時間）
稼働率の計算
例題
- 問題
- 解答
おわりに
おすすめの学習本

信頼性評価指標

システムの信頼性評価の指標としてよく使われるものを二つ挙げます。

MTBF（Mean Time Btween Failures：平均故障間隔）

故障してから次に故障するまでの時間の平均値です。

MTBFが大きければ大きいほど故障しにくいと言えます。

つまり大きいほど良いです。

MTTR（Mean Time To Repair：平均修理時間）

故障してから復旧するまでの時間の平均値です。

MTTRが大きければ大きいほど復旧に時間がかかると言えます。

つまり小さいほど良いです。

稼働率の計算

基本情報技術者試験や応用情報技術者試験では稼働率の計算問題がよく出てきます。

稼働率は以下の式で求められます。

$稼働率 = \frac{MTBF}{MTBF + MTTR}$

式を言語化すると「全体の時間に占めるMTBF（稼働している時間）の割合」です。

それでは例題を解いてみましょう。

例題

問題

故障してから次に故障するまでの平均時間が990時間の機器がある。故障をすると復旧するまでに平均で10時間かかる。この機器の稼働率を答えよ。

解答

先程挙げた式に当てはめると以下のようになります。

$\begin{eqnarray} \frac{MTBF}{MTBF + MTTR} &=& \frac{990}{990 + 10} \\ &=& 0.99 \end{eqnarray}$

したがって答えは0.99です。

おわりに

今回はシステムの信頼性評価について説明し、簡単な稼働率の計算を行いました。

実際に出てくる問題はもう少しひねった問題になるので、それは次回説明します。

あわせて読みたい

talosta.hatenablog.com

【基本・応用情報技術者】ハミング符号による誤り訂正

資格資格-基本情報技術者試験資格-応用情報技術者試験

こんにちは。たろすです。

今回はハミング符号による誤り訂正について説明します。

ハミング符号とは
例題
- 問題
- 解答
おわりに
おすすめの学習本

ハミング符号とは

ハミング符号とは、データの伝送時に付加し、誤りを検知・訂正できる誤り訂正符号の一つ。
ハミング符号（Hamming code）とは - IT用語辞典 e-Words

とのことです。

誤り制御には検知しかできないものと訂正もできるものがあります。

ハミング符号は1ビットまでの誤りなら訂正もできます。

このような知識もよく問われるので覚えておきましょう。

例題

問題

さっそくですが例題を解いていきます。

応用情報技術者試験からの出題です。

ハミング符号とは，データに冗長ビットを付加して， 1ビットの誤りを訂正できるようにしたものである。ここでは，X1，X2，X3，X4の4ビットから成るデータに，3ビットの冗長ビットP3，P2，P1を付加したハミング符号 X1X2X3P3X4P2P1 を考える。付加ビットP1，P2，P3は，それぞれ
　　 $X1 \oplus X3 \oplus X4 \oplus P1＝0$
　　 $X1 \oplus X2 \oplus X4 \oplus P2＝0$
　　 $X1 \oplus X2 \oplus X3 \oplus P3＝0$
となるように決める。ここで⊕は排他的論理和を表す。
ハミング符号 1110011 には1ビットの誤りが存在する。誤りビットを訂正したハミング符号はどれか。

ア．0110011
イ．1010011
ウ．1100011
エ．1110111

（出典：平成30年度春期応用情報技術者試験午前問3）

解答

「ハミング符号 X1X2X3P3X4P2P1 を考える」とあり、ハミング符号は「1110011 」であることから、

X1=1
X2=1
X3=1
P3=0
X4=0
P2=1
P1=1

であることがわかります。

それでは3つの式に具体的な数字を入れていきます。

一番目の式は、

$X1 \oplus X3 \oplus X4 \oplus P1＝1 \oplus 1 \oplus 0 \oplus 1$

となります。

演算結果は1となり0になっていないので、X1かX3かX4が誤っていることがわかります。

二番目の式は

$X1 \oplus X2 \oplus X4 \oplus P2＝1 \oplus 1 \oplus 0 \oplus 1$

となります。

こちらも演算結果は1となり0になっていないので、X1かX2かX4が誤っていることがわかります。

三番目の式は

$X1 \oplus X2 \oplus X3 \oplus P3＝1 \oplus 1 \oplus 0 \oplus 1$

となります。

こちらも演算結果は1となり0になっていないので、X1かX2かX3が誤っていることがわかります。

三つの式すべてに誤っているビットが含まれていることがわかりました。

したがって、三つの式すべてに含まれているビットが誤っているビットであると断定できます。

つまり、誤っているビットはX1です。

以上より、答えは「1110011 」から先頭のビットを反転した「ア．0110011 」となります。

おわりに

今回はハミング符号による誤り訂正について説明しました。

難しくはないので確実に正解できるようにしておきましょう。

あわせて読みたい

talosta.hatenablog.com

【基本・応用情報技術者】オートマトンと状態遷移図

資格資格-基本情報技術者試験資格-応用情報技術者試験

こんにちは。たろすです。

今回はオートマトンと状態遷移図について説明します。

オートマトンとは
状態遷移図の読み方
例題
おわりに
おすすめの学習本

オートマトンとは

オートマトンは一定の規則に従って複数の内部状態の間を遷移する仮想的な機械で、現在の状態と入力の組み合わせを規則の中から探し出し、指定された次の状態へ遷移する。規則に該当する組み合わせがなければ同じ状態を維持する。規則は状態遷移表や状態遷移図として書き表すことができる。
オートマトン（状態機械）とは - IT用語辞典 e-Words

つまり、現在の状態にある入力を与えると特定の状態へ遷移する機械のことです。

オートマトンの問題では状態遷移図がよく使われます。