Upatissa

エンジニアへの転職のために学習したことを投稿しています。

「データベース」 ⑤ トランザクション管理と排他制御

目次

データベースの不整合

データベースは、複数の人が共有して利用することが出来るものです。
しかし、複数の人が同時にデータベースを読み書きした場合、内容の変更が正しく反映されず、不整合が生じる恐れがあります。

例として、以下のような「在庫表」を使って商品の在庫状況を管理する場合を取り上げたいと思います。

f:id:Upatissa:20210110180903p:plain
在庫表

商品が購入された場合、商品在庫を購入数分減らし、データベースを更新します。

このような仕組みに従って、同じ商品が同時に購入された場合、更新処理がどのように行われるか考えてみたいと思います。

例えば、A4ノートが5冊ずつ同時に購入された場合、更新処理の様子は以下の図のようになります。

f:id:Upatissa:20210110221247p:plain
データベースの不整合

この図から分かる通り、データベースを共有する複数の利用者によって同時に処理が行われれると、処理結果が同期されないため、不整合が生じてしまいます。

このような問題を防ぎ、データベースを正しく扱うことが出来るようにする管理手法がトランザクション管理排他制御です。

トランザクション管理とは何か

データベースの一連の処理をまとめたものをトランザクションと呼びます。

先ほどの例の中では、在庫表(データベース)を確認したり、更新したりする処理がありました。
これらの一連の処理が1つのトランザクションとして扱われます。

f:id:Upatissa:20210110232527p:plain
トランザクション

データベースは、更新処理をトランザクション単位で管理しています。

排他制御とは何か

排他制御とは、トランザクションが行われているデータをロックして、他の利用者が干渉出来ないようにする制御です。

f:id:Upatissa:20210111075805p:plain
排他制御

排他制御を行うことで、先ほどの例のように、データベースの使用中に他者によってデータの更新が行われることを防ぐことが出来ます。
その結果、データベースの不整合が生じる恐れがなくなります。

排他制御には、共有ロック専有ロックの2つがあり、他者によるデータの書き込みまたは読み込みを制限します。

共有ロック

共有ロックは、他者によるデータの読み込みは制限しませんが、書き込みを制限します。

f:id:Upatissa:20210111080511p:plain
共有ロック

専有ロック

専有ロックは、他者によるデータの読み込みと書き込みの両方を制限します。

f:id:Upatissa:20210111081035p:plain
専有ロック

デッドロック

排他制御によって、データベースの不整合を未然に防ぐことが出来ますが、データベースがロックされてしまうことによって生じる弊害も存在します。その1つがデッドロックです。

デッドロックとは、複数のユーザがそれぞれ異なるデータにアクセスし、トランザクションによるロックをかけている状態で、そこからさらに別のユーザが使用中のデータにアクセスしようとした結果、互いにロックが解除されるのを待ち続けることになってしまう状態のことです。

例えば、ある大学の学生の学生番号や氏名、所属学部のIDを一覧にした「学生表」と、学部IDに対応する学部名を一覧にした「学部表」という2つの表があるとします。

これらの2つの表それぞれに対して、ユーザAとユーザBがアクセスし、さらにもう1つの表にアクセスしようとした場合、互いのトランザクションによってロックがかかってしまっているため、アクセスすることが出来なくなってしまいます。

f:id:Upatissa:20210111102751p:plain
デッドロック

ACID特性

データベースを管理するDBMS(データベース管理システム)では、トランザクションまたはその結果が4つの特性を備えている必要があるとされています。
それぞれの特性の頭文字を取り、これらをACID特性と呼びます。

Atomicity(原子性)

トランザクションはデータベースに対する一連の処理をまとめたものです。しかし、それらのうち一部だけが実行され、残りが未実行であるような中途半端な場合はデータベースへ反映することを許容しない、という考え方です。
つまり、トランザクションの一連の処理が全て正常に終了してからデータベースに反映するということになります。

Consistency(一貫性)

データベースの内容が矛盾しないように一貫性を保つという考え方です。
つまり、トランザクションの結果がデータベースに矛盾を生じさせないような内容である必要があります。

Isolation(隔離性)

先ほどの「データの不整合」の部分で触れましたが、複数のトランザクションが同時に実行される場合、データの不整合が生じる恐れがあるため、排他制御を確実に行い、他のトランザクションによって影響を受けないように隔離しておくという考え方です。

Durability(耐久性)

正常に終了したトランザクションの結果が、障害の発生によってデータベースから失われないようにしておく、という考え方です。
言い換えると、データベースを復旧するための手段を確立しておく必要があるということになります。

ストアドプロシージャ

データベースはSQL文によって操作されますが、一連の操作手順(SQL文)を1つのプログラムとしてまとめておき、データベース管理システム側にあらかじめ保存しておくことをストアドプロシージャと呼びます。

クライアントサーバシステムにおいて、サーバ側に保存されたストアドプロシージャは、クライアントから名前を指定されるだけで実行されます。

f:id:Upatissa:20210111151117p:plain
ストアドプロシージャとクライアントサーバシステム

ストアドプロシージャは、SQL文が束になっているため、1文ずつネットワークに流す必要が無く、負荷を軽減することが出来ます。
また、ストアドプロシージャはSQL文の解析が済んだ即実行可能な形式となっているため、処理速度の向上を図ることも出来ます。

このように、あらかじめSQL文をストアドプロシージャとして保存しておくことにより、SQL文を1つずつ実行させるよりも多くのメリットがあります。

参考にさせて頂いた書籍

きたみりゅうじ 『キタミ式イラストIT塾 基本情報技術者平成31/01年』 技術評論社 2019年

学習してみて

今回はデータベースを健全に保ったり、効率良く利用するための仕組みについて学習しました。
データベースは多数のユーザと共有出来ることで価値をもたらしますが、その一方で不整合が発生したり、書き換えられたりするリスクもあることが分かりました。
ACID特性のように、データベースという1つのシステムにはそれが要求する特性が存在します。このことを理解した上で活用することが出来るようになりたいと思います。

「データベース」 ③ SQL

目次

SQLとは何か

SQL(Structured Query Language)とは、ユーザがDBMS(データベース管理システム)に指示を伝えるための言語です。

SQLにはDBMSに命令するための様々な命令文が用意されています。
SQLの命令文は、以下の表のような役割を持つデータ定義言語データ操作言語に大別されます。

SQLの命令文 命令文の分類 役割
CREATE文
など
データ定義言語 スキーマの定義
表の作成など
SELECT文
INSERT文
UPDATE文
DELETE文
など
データ操作言語 データの抽出・挿入
更新・削除等の操作

ユーザによって入力されたSQLの命令文を受けて、DBMSは該当するデータを抽出したり、返却したりする処理を行います。

命令文の書式

上の表にある通り、SQLには様々な命令文がありますが、それらを使う際には決められた書式に従う必要があります。

これ以降では、データベースの使用目的に合わせてSQLの命令文の書式を紹介ていきたいと思います。

データの抽出

SQLでデータベースから特定のデータを抽出するには、「SELECT文」という命令文を使用します。
SELECT文とは、文字通り「選ぶ」という意味の「SELECT」から始まる文で、データベースから抽出したい内容に応じて以下の3点を指定します。

抽出する列名
抽出する表名
抽出する条件
(※必要無い場合は省略可)

このことを踏まえて、様々な抽出方法について取り上げていきたいと思います。

① 列の抽出(射影)

列を抽出する場合、まず最初に列名と表名を指定します。
列名は、SELECTの後に記入することで指定出来ます。
表名は、FROM句という句の後に記入することで指定出来ます。

このような書式に従うと、SQL文は次のようになります。

SELECT (列名)
FROM (表名)

例えば、以下のような商品表があるとします。

f:id:Upatissa:20210102153632p:plain
商品表

この表から商品名の列を抽出したい場合、SQL文は次のようになります。

SELECT 商品名
FROM 商品表

このSQL文による抽出結果は以下の通りです。

f:id:Upatissa:20210102154539p:plain
列の抽出

② 全ての列の抽出

表の全ての列を抽出する場合には、SELECTの後の列を指定する部分に「*(アスタリスク)」を入れて次のようなSQL文にします。

SELECT *
FROM (表名)

先ほどの商品表から全ての列を取り出したい場合、SQL文は次のようになります。

SELECT *
FROM 商品表

このSQL文による抽出結果は以下の通りです。

f:id:Upatissa:20210103220855p:plain
全ての列の抽出

③ 行の抽出(選択)

行を抽出する場合、先に列名と表名を指定し、その後WHERE句という句を使って抽出したい行の条件を指定します。
条件を絞り込む必要がない場合は、WHERE句以降を省略することが出来ます。

このような書式に従うと、SQL文は次のようになります。

SELECT (列名)
FROM (表名)
WHERE (条件)

WHERE句以降の条件の部分は、比較演算子を用いて以下の表のように指定することが出来ます。

比較演算子 意味
左辺と右辺が等しい 単価=500
(単価が500円である)
左辺が右辺より大きい 単価>500
(単価が500円より大きい)
>= 左辺が右辺以上 単価>=500
(単価が500円以上)
左辺が右辺より小さい 単価<500
(単価が500円より小さい)
<= 左辺が右辺以下 単価<=500
(単価が500円以下)
<> 左辺と右辺が等しくない 単価<>500
(単価が500円でない)

例えば、商品表のうち、単価が500円以上となる商品の行を抜き出したいとします。

この場合、対象となる行全体を抽出するため、「*」を使って全ての列を指定します。そして、比較演算子「>=」を使って次のようなSQL文とします。

SELECT *
FROM 商品表
WHERE >= 500

このSQL文による抽出結果は以下の通りです。

f:id:Upatissa:20210104110528p:plain
特定の行の抽出

④ 条件の組み合わせ

WHERE句以降で指定した条件は、論理演算子を使って複数組み合わせることが出来ます。

例として、条件Aと条件Bという2つの条件がある場合の論理演算を取り上げたいと思います。

論理積「(条件A)かつ(条件B)」

条件Aと条件Bの両方を満たす場合、つまり「(条件A)かつ(条件B)」を表現するには、論理積「AND」を使って次のようなSQL文にします。

SELECT (列名)
FROM (表名)
WHERE (条件A) AND (条件B)

例えば、商品表の中から単価が200円より大きく、かつ300円未満の商品の行を抽出したい場合、SQL文は次のようになります。

SELECT *
FROM 商品表
WHERE 単価>200 AND 単価<300

このSQL文による抽出結果は以下の通りです。

f:id:Upatissa:20210104123827p:plain
複数の条件による抽出 「AND(論理積)」

論理和「(条件A)または(条件B)」

条件Aと条件Bのいずれか一方を満たす場合、つまり「(条件A)または(条件B)」を表現するには、論理積「OR」を使って次のようなSQL文にします。

SELECT (列名)
FROM (表名)
WHERE (条件A) OR (条件B)

例えば、商品表の中から単価が200円以下、または3000円より大きい商品の行を抽出したい場合、SQL文は次のようになります。

SELECT *
FROM 商品表
WHERE 単価<=200 OR 単価>3000

このSQL文による抽出結果は以下の通りです。

f:id:Upatissa:20210104204007p:plain
複数の条件による抽出 「OR(論理和)」

否定「(条件A)でない」

条件を満たしていない場合、つまり「(条件A)でない」を表現するためには、否定「NOT」を使って次のようなSQL文にします。

SELECT (列名)
FROM (表名)
WHERE NOT (条件A)


演算子の優先順位

これまで取り上げてきた3種類の演算子には優先順位があり、
NOT > AND > OR
という順に優先されます。

例えば、「((条件A)かつ(条件B))の否定」を取ろうとして

NOT (条件A) AND (条件B)

とした場合、NOT演算子はAND演算子よりも優先されます。 そのため、条件Aと条件Bの両方に対してではなく、条件AのみにNOT演算子が適用されます。
だから、「((条件A)の否定)かつ(条件B)」という結果になってしまいます。

このように、優先順位が低い演算子を、優先順位が高い演算子よりも先に適用させたい場合には、優先順位が低い演算子を含む内容をカッコでひとまとまりにすると先に適用することが出来ます。

したがって、「((条件A)かつ(条件B))の否定」を取る場合には

NOT(条件A)AND(条件B)

とすれば良いということになります。


このことを踏まえて、例えば、商品表から「単価が200円以下、または3000円より大きい」という条件を満たさない商品の行を取得したい場合、SQL文は次のようになります。

SELECT *
FROM 商品表
WHERE NOT (単価<=200 OR 単価>3000)

このSQL文による抽出結果は以下の通りです。

f:id:Upatissa:20210104215522p:plain
複数の条件による抽出 「NOT(否定)」

表の結合

関係データベースでは、様々な表を組み合わせてデータを効率良く管理します。
そのためには、複数に分離した表を結合させる操作が必要になります。

SQLでは、SELECT文のFROM句とWHERE句で結合したい表名と結合させる列名を指定すると、表同士を結合させることが出来ます。

例えば、表Aと表Bという2つの表を、表Aのcという列と表Bのcという列で結合させる場合、記号「,(コンマ)」、「.(ドット)」、「=(イコール)」を使い、SQL文で次のように表現します。

SELECT (列名)
FROM 表A,表B
WHERE 表A.c = 表B.c

(※今回の例では「c」という、表Aと表Bに存在する同じ名前の列同士の結合を取り上げています。しかし、必ずしも結合する列名が同じでなければならないというわけではありません。)

(※また、結合する列名が異なっている場合、列名の違いから表を特定することが出来るため、「表A.c」のような「表名.」の部分を省略することが出来ます。)

例えば、商品の受注数を示した受注明細表と商品表を、「受注明細表の商品コード」列と「商品表の商品コード」列で結合させる場合、SQL文は次のようになります。

SELECT *
FROM 受注明細表,商品表
WHERE 受注明細表.商品コード = 商品表.商品コード

このSQL文による実行結果は以下の通りです。

f:id:Upatissa:20210104230321p:plain
表同士の結合

データの整列

これまでの方法で抽出したようなデータを整列させるためには、ORDER BY句という句を使います。
具体的には、ORDER BY句以降で整列に使う列を指定し、さらに整列させる順番(昇順・降順)を指定します。

SQL文は次のように表現します。

SELECT (列名)
FROM (表名)
WHERE (条件)
ORDER BY (整列に使う列名) ASC
(※昇順) または DESC(※降順)

ORDER BY句の ASC は列を昇順で並べ、DESC は降順で並べます。

例えば、先ほどの「表同士の結合」で結合させた図を、さらに「単価」の列で昇順に整列させる場合、SQL文は次のようになります。

SELECT *
FROM 受注明細表,商品表
WHERE 受注明細表.商品コード = 商品表.商品コード ORDER BY 単価 ASC

このSQL文による実行結果は以下の通りです。

f:id:Upatissa:20210105230058p:plain
表同士の結合と整列

このように、抽出結果のうち、1列を指定して整列させる以外にも、複数の列を指定して整列させることが出来ます。

例えば、結合させて新たに作られた表を、まず「数量」の列で昇順に整列させ、その状態からさらに「単価」で降順に整列させる場合、SQL文は次のようになります。

SELECT *
FROM 受注明細表,商品表
WHERE 受注明細表.商品コード = 商品表.商品コード ORDER BY 数量 ASC,単価 DESC

このSQL文による実行結果は以下の通りです。

f:id:Upatissa:20210105234604p:plain
表同士の結合と複数列の整列

関数による集計

SQLによってデータを抽出する際に、集計を行う集合関数と呼ばれる関数があります。
以下の表のような集合関数を使うと、列の最大値や平均値、行数などを求めることが出来ます。

関数 役割
MAX(列名) 列の最大値を求める
MIN(列名) 列の最小値を求める
AVG(列名) 列の平均値を求める
SUM(列名) 列の合計を求める
COUNT(*) 行数を求める
COUNT(列名) 値が入っている行数を求める

集合関数を用いたSQL文は次のように表現します。

SELECT (集合関数) (関数を用いる列名)
FROM (表名)

例えば、商品表の単価の最大値を求めたい場合、SQL文は次のようになります。

SELECT MAX 単価
FROM 商品表

このSQL文による実行結果は以下の通りです。

f:id:Upatissa:20210108081657p:plain
集合関数(MAX)の実行

データのグループ化と集合関数

列のうち、特定のカテゴリーや内容が一致するものを1つのグループにして扱いやすくすることをグループ化と呼びます。

グループ化は、GROUP BY句という句を用います。
具体的には、GROUP BY句の後にグループ化したい列名を指定します。
こうすることで、指定した列のうち、特定のカテゴリーや内容が一致するものを1つのグループにすることが出来ます。

さらに、グループ化によってまとめられたデータに対し、集合関数を用いるとグループ単位でデータの特徴を求めることが出来ます。

グループ化と集合関数を用いたSQL文は次のようになります。

SELECT (グループ化したい列名), (集合関数)
FROM (表名)
GROUP BY (グループ化したい列名)

例えば、商品のカテゴリーを示す「カテゴリー」列がある商品表をカテゴリーごとに分類し、各カテゴリーに属する商品数を数える場合、SQL文は次のようになります。

SELECT カテゴリー, count(*)
FROM 商品表
GROUP BY カテゴリー

このSQL文による実行結果は以下の通りです。

f:id:Upatissa:20210109194649p:plain
データのグループ化

グループ化と絞り込み

データをグループ化した後、各グループに対し一定の条件を設けて絞り込みを行うことが出来ます。

絞り込みは、HAVING句を使用します。
具体的には、先ほどのグループ化のSQL文の後にHAVING句を記入し、さらにその後に続けて絞り込みを行うための条件を指定します。

絞り込むための条件は集合関数や比較演算子を組み合わせて表現します。

グループ化と絞り込みを用いたSQL文は次のようになります。

SELECT (グループ化したい列名), (集合関数)
FROM (表名)
GROUP BY (グループ化したい列名)
HAVING (絞り込み条件)

例として、先ほどの商品表を取り上げたいと思います。
まず、先ほどの「データのグループ化」と同様に、商品をカテゴリーごとにグループ化します。
そして、集合関数AVGを用いて各カテゴリーの平均単価を求めます。
さらに、HAVING句で平均単価が2000円より大きいという条件を指定し、この条件を満たすグループを絞り込みたいと思います。

SELECT カテゴリー, AVG (単価)
FROM 商品表
GROUP BY カテゴリー
HAVING AVG (単価) > 2000

このSQL文による実行結果は以下の通りです。

f:id:Upatissa:20210109204719p:plain
データのグループ化と絞り込み

この過程の図では、消耗品以外のカテゴリーの平均単価については触れられていないため、全カテゴリーの平均単価を以下の図に示します。

f:id:Upatissa:20210109211647p:plain
各カテゴリーの平均単価

参考にさせて頂いた書籍

きたみりゅうじ 『キタミ式イラストIT塾 基本情報技術者平成31/01年』 技術評論社 2019年

学習してみて

今回は、データベースを操作するための言語、SQLについて学習しました。
データベースを自在に操作することができる分、基本的な句だけでも色々なものがありますね。
基本的な操作をある程度把握したら使い慣れるまで繰り返し練習してみるのが一番良いのではないかと思います。

データを扱うことが出来るようになれば、様々なデータの傾向を掴んだり、直感では分からないような因果関係・相関関係を明らかにすることが出来ると思います。
様々な可能性のある領域で、個人的にも興味のある領域なので、今後もますます学習を深めていきたい領域だと感じました。

「データベース」 ② 各種キーと正規化

目次

各種キーの特徴

主キー

データベースを扱う場合、目的の行を特定するための情報が必要になります。この情報のことをキーと呼びます。

データベースにはキーが必ず含まれています。
その中でも、関係データベースの表の中で行を特定するために必要なキーのことを主キーと呼びます。

しかし、全ての情報が主キーになり得るわけではありません。
ある情報が主キーとして扱われるためには、2つの条件を満たしている必要があります。
1つ目の条件は、表の中で内容が重複していないことであり、2つ目は、空白でないことです。

f:id:Upatissa:20201229233925p:plain
主キーに適した情報

例えば、上の図のように、社員に関する情報を一覧にした「社員表」と、学生に関する情報を一覧にした「学生表」があるとします。

それぞれの表の列に注目すると、社員や学生一人ひとりに割り当てられている「社員番号」や「学生番号」は、内容が重複せず、一意である情報であると言えます。
また、この両者は基本的に空白ではありません。
したがって、両者は主キーとして扱うのに最も適していると言えます。

複合キー

このように、表の一意な列1つのみで行を特定するのが主キーですが、複数の列を組み合わせることによっても行を特定することが出来る場合があります。

例えば、以下のような「入社年月」と「部署」、「名前(苗字)」、「生年月日」という4つの情報で社員をまとめた社員表があるとします。
この表には主キーになり得る社員番号が存在せず、列1つのみでは重複する可能性があるため、一意にはなりません。

f:id:Upatissa:20201231082818p:plain
複合キー

しかし、4つの列を組み合わせると行が一意になり、目的の社員を特定することが出来ます。
このように、複数の列を組み合わせて主キーとしたものを複合キーと呼びます。

外部キー

関係データベースでは、表と表を関係付けることによってデータを扱いやすくするという特徴があります。
しかし、表同士を関係付けるためには何らかの基準が必要になります。

この基準を説明するための例として、以下のような学生番号を主キーとした「学生表」と学部IDを主キーとした「学部表」について取り上げたいと思います。

f:id:Upatissa:20201231092245p:plain
学生表と学部表

ここで、学生表の「学部ID」という列について着目してみると、これは学部表の主キーである「学部ID」に対応しているということが分かります。

この関係を利用すると、学生表の学部IDを介して学部表の学部名を参照することが出来ます。
その結果、学生の学生番号が分かれば学部名を特定することが出来るようになります。

f:id:Upatissa:20201231090200p:plain
外部キー

このように、表同士を関係付けるため、他の表の主キーを参照する列のことを外部キーと呼びます。

正規化

正規化とは、データを取り扱う上で矛盾を生じさせないようにするために表を最適化させることです。

正規化には、以下のような4つの段階が存在します。

  • 非正規形
  • 第1正規形
  • 第2正規形
  • 第3正規形

正規化の過程を説明するために、同様の形式を持つ以下のような3種類の受注伝票を取り上げたいと思います。

f:id:Upatissa:20201231222413p:plain
受注表

非正規形

これらの3種類の受注表を受注Noごとに3行の表にすると次のようになります。

f:id:Upatissa:20210101083044p:plain
非正規形

この表は、行の長さがバラバラで、列の商品部分が繰り返しの形になったままになっています。

f:id:Upatissa:20210101083647p:plain
非正規形(詳細)

このように、データの元になる情報を、正規化せず単純に表にしたものを非正規形の表と呼びます。

関係データベースでは、非正規形の表を管理することは出来ません。

第1正規形

非正規形の繰り返しの部分を無くしたものが第1正規形という形式です。

f:id:Upatissa:20210101134744p:plain
第1正規形

正規化の過程では、繰り返しになっている商品部分をそのまま新しい行として挿入します。
そして、挿入された行に欠けている受注情報を補います。

この過程で、「金額」のように計算によって求めることが出来る部分については省略します。

関数従属と部分関数従属

第2正規形を説明するためには、列同士の関係を表現する関数従属部分関数従属について理解する必要があります。

関数従属

関数従属は、表の主キーや複合キーとそれ以外の列との関係を表すものです。

関数従属を説明するために、以下のような学生表と社員表を取り上げたいと思います。

f:id:Upatissa:20210101131201p:plain
関数従属

図の学生表では、主キーが決まることでそれ以外の列が特定されています。
そして、社員表では、複合キーが決まることでそれ以外の列が特定されています。

このように、主キーや複合キーの全体によってそれ以外の列の値が定まる関係のことを関数従属と呼びます。

部分関数従属

部分関数従属は、複合キーとそれ以外の列との関係を表すものです。

部分関数従属を説明するために、先ほどまで説明に使用していた受注表を取り上げたいと思います。

f:id:Upatissa:20210101131314p:plain
部分関数従属

この表において、行を特定するためには、「受注No.」と「商品コード」の2列からなる複合キーを用います。

ここで、これらの複合キーとそれ以外の列の関係に注目すると、2つの複合キーのうち一方によって他の列が特定できるということが分かります。

つまり、複合キー①の「受注No.」が分かれば、右に続く「受注日」と「得意先No.」と「得意先名称」が分かるということです。
同様に、複合キー②の「商品コード」が分かれば、右に続く「商品名」と「単価」が分かります。

このように、複合キーの一部で特定できる列との関係を部分関数従属と呼びます。

第2正規形

先ほどの第1正規形をさらに正規化させたものが第2正規形という形式です。
具体的には、第1正規形の部分関数従属になっている列を別の表に分離させたものが第2正規形です。

ここで、以下の図を使い、改めて第1正規形の部分関数従属を整理したいと思います。

f:id:Upatissa:20210101154251p:plain
第1正規形の部分関数従属

この図から分かるように、第1正規形では「受注No.」と「商品コード」にその他の列が部分関数従属しています。

この関係を利用して第2正規形に正規化すると次のようになります。

f:id:Upatissa:20210101153857p:plain
第2正規形

上の図では、部分関数従属していた列がそれぞれ「受注表」と「商品表」という2つの表へと分離させられていることが分かります。

この図には表示の関係で全ての商品と受注明細を載せていませんが、受注明細表の「受注No.」と「商品コード」を介してそれ以外の表を参照することが出来るようになっています。

第3正規形

第3正規形は、第2正規形で新たに作成された表のうち、主キー以外の列に関数従属している列を別の表に分離させたものです。

先ほどの第2正規形の3つの表を例とすると、第3正規形にすることが出来るのは、受注表の「得意先名称」になります。

なぜなら、「得意先名称」は受注表の主キーである「受注No.」に関数従属していないからです。
つまり、「得意先名称」は「得意先No.」によって定まるのであって、「受注No.」によって定まるのではないということです。

このことを踏まえて、受注表の「得意先名称」を「顧客表」として分離させたものが以下の図になります。

f:id:Upatissa:20210102002849p:plain
第3正規形

これらの正規化のプロセスを経ることによって、関係データベースは柔軟かつ効率的にデータを管理することが出来るようになります。

参考にさせて頂いた書籍

きたみりゅうじ 『キタミ式イラストIT塾 基本情報技術者平成31/01年』 技術評論社 2019年

学習してみて

今回は関係データベースの正規化について学習しました。
図を作成しながら学習を進めていったので言葉の意味だけを捉えるよりもイメージがしやすかったです。
しかし、それでもやはり以下のような関数従属と部分関数従属の違いの理解には時間がかかりました。

関数従属している列や部分関数従属している列の従属先(主?)が複合キーである場合、関数従属している列の従属先は複合キー全体であるのに対し、部分関数従属している列の従属先は複合キーの一部である。

このように、関係データベースで正規化を上手く使いこなせるようになると様々な利点があるのではないかと思います。
日常的に見る様々な表やデータを正規化出来るか考えるようにしてみると良いかもしれませんね。

「データベース」 ① データベース管理システム(DBMS)

目次

データベース管理システム(DBMS)とは何か

コンピュータがアプリケーション等で使用するデータを蓄えておく場所がデータベース(DB)です。
データベースは、単にデータを蓄えるだけではなく、アプリケーション等の要求に合わせて必要な部分だけを抜き出したり、更新・削除したりすることも出来ます。

このようなデータベース操作の管理をしているのがデータベース管理システム(DBMS:Data Base Management System)です。

f:id:Upatissa:20201209075333p:plain
コンピュータにおけるデータベース管理システムの位置付け

つまり、データベース管理システムは、アプリケーションがデータベース上のデータを扱いやすくする役割を果たします。

関係型データベースの特徴

データの管理方法にはいくつか種類がありますが、今回はその中でも主流の関係型データベース(RDB:Relational Data Base)について取り上げたいと思います。

関係型データベースは、データをで管理するという特徴があります。
この表は、行と列から構成されていて、データ1件を1行で表現します。
また、データの追加や削除などの操作も基本的にデータ1件ずつ、行単位で行われます。

f:id:Upatissa:20201223223933p:plain
関係型データベースの構造

関係型データベースのもう1つの特徴は、データの扱い方・内容次第で表を分割し、それらを関係づけることが出来る点です。
この特徴は、これから取り上げる正規化関係演算で活用されています。

正規化

関係データベースでは、データに矛盾や重複が発生しないように表を最適化しておく必要があります。
例えば、同じ内容が複数箇所に入力されているような場合、内容自体が変更になると、それが入力されている全ての箇所を修正する必要があります。
しかし、もし修正に漏れがあったら、データとして不整合が生じてしまいます。

そこで、データの矛盾や重複を未然に防ぎ、より管理しやすくするために表を分離させます。このことを正規化と呼びます。

f:id:Upatissa:20201228104737p:plain
データベースの正規化

関係演算

データベースの表から特定の行や列を取り出したり、組み合わせることによって、新しい表を作る演算のことを関係演算と呼びます。
関係演算によって、記憶されているデータを活用しやすくすることが出来ます。

関係演算には選択射影、そして結合といった演算があります。

選択

選択とは、元の表から特定の条件を満たすを取り出す演算です。 図のように、関係演算によって一時的に作られる図のことをビュー表と呼びます。

f:id:Upatissa:20201228130804p:plain
選択

射影

射影とは、元の表から特定の条件を満たすを取り出す演算です。

f:id:Upatissa:20201229062137p:plain
射影

結合

結合とは、別々の表同士を共通する列を介して結合させる演算です。

f:id:Upatissa:20201229063237p:plain
結合

スキーマ

スキーマとは、データベースの仕様や構造を定義するものです。
標準的に、3層スキーマ構造を取ることがあります。
これは、データを外部スキーマ概念スキーマ内部スキーマという3層の定義に分けることによって独立性を高める仕組みです。

f:id:Upatissa:20201229074211p:plain
3層スキーマ構造

外部スキーマとは、ユーザやプログラムに対して必要なデータだけを提供するもので、ビュー表がこれに該当します。
プログラムの変更がデータに与える影響は、このスキーマまでになっています。

概念スキーマとは、データベースの表の定義を行うもので、データベース本体に当たります。
この層は、プログラムとハードウェアの両者に依存することが無いため、独立性を保っています。

内部スキーマとは、データを物理的に記憶させる方法を定義するもので、ハードウェア的な変更がデータに与える影響は、このスキーマまでになっています。

3層スキーマ構造をとることにより、例えば、外部スキーマのビュー表を変更したとしても、概念スキーマのデータベース本体は影響を受けません。
また、データを記憶するハードウェアの変更があったとしても、この影響は内部スキーマまでしか及びません。だから、この変更に合わせてプログラムを修正する必要はありません。

参考にさせて頂いた書籍

きたみりゅうじ 『キタミ式イラストIT塾 基本情報技術者平成31/01年』 技術評論社 2019年

学習してみて

今回からデータベースの学習に入りました。
スキーマにの3層構造にあるように、データベースはユーザやプログラム、ハードウェアなどの様々な主体で扱われますが、それらの整合性を保ちつつ、独立性を確保しなければなりません。
だから、データベースはとても複雑な立場にあるように感じられました。
このような複雑な要求に応えるためにデータベース管理システムが存在しているというわけですね。

今後は、今回少し触れたデータの正規化や操作について詳しく学習していきたいと思います。

「ファイルとディレクトリ」 ② 汎用コンピュータにおけるファイルの性質

目次

汎用コンピュータにおけるファイルとは

個人によって占有され、使用されるパソコン(PC : Personal Computer)の普及以前は、企業などが基幹業務で利用するような大型の汎用コンピュータが主流でした。
汎用コンピュータは、データを1件ずつレコードという単位で管理しています。そして、レコードの各項目をフィールドと呼び、レコードの集合によってファイルが構成されています。

f:id:Upatissa:20201221150331p:plain
汎用コンピュータにおけるファイルの構造

ファイルのアクセス方法

レコードの集合によって構成されているファイルにアクセスする方法として、以下の3種類があります。

  • 順次アクセス
  • 直接アクセス
  • 動的アクセス

順次アクセス

順次アクセスは、レコードを先頭から順にアクセスしていく方法です。
シーケンシャルアクセスとも呼ばれます。

f:id:Upatissa:20201221120605p:plain
順次アクセス(シーケンシャルアクセス)

直接アクセス

直接アクセスは、任意のレコードに直接アクセスする方法です。
ランダムアクセスとも呼ばれます。
このアクセス方法は、CDやハードディスクなどで利用されています。

f:id:Upatissa:20201221121552p:plain
直接アクセス(ランダムアクセス)

動的アクセス

動的アクセスは、順次アクセスと直接アクセスを組み合わせた方法です。
任意のレコードに直接アクセスし、そこから順番にアクセスします。

f:id:Upatissa:20201221122254p:plain
動的アクセス

ファイルの編成方法

このようなファイルにレコードを格納する方法として、以下の4種類があります。

  • 順編成ファイル
  • 直接編成ファイル
  • 索引編成ファイル
  • 区分編成ファイル

順編成ファイル

順編成ファイルでは、格納したいレコードを先頭からそのまま順に詰め込みます。
この編成法へのアクセスは、順次アクセスのみが可能になっています。
記憶領域に無駄がなく、一連のデータを処理するのに向いている一方、レコードの挿入や削除といった編集が難しいという特徴があります。

f:id:Upatissa:20201221132747p:plain
順編成ファイル

直接編成ファイル

直接編成ファイルでは、レコードの中のキーを利用することで、任意のレコードに対して直接アクセスすることが出来ます。
キーとは、レコードが格納されるファイルの中で重複することが無い一意の値のことを意味します。

f:id:Upatissa:20201221151211p:plain
直接編成ファイル

レコードが格納されるアドレス(場所)を指定する方法として直接アドレス方式間接アドレス方式の2つがあります。

直接アドレス方式

直接アドレス方式では、キーをそのまま格納アドレスとして用います。

f:id:Upatissa:20201221152947p:plain
直接アドレス方式

間接アドレス方式

直接アドレス方式では、キーをハッシュ関数という計算式によって計算し、格納アドレスを算出します。

f:id:Upatissa:20201223111226p:plain
間接アドレス方式

もし、この計算結果が重複すると、格納アドレスも重複してしまいます。
このような現象をシノニムと呼び、シノニムが発生したレコードをシノニムレコードと呼びます。
シノニムが発生した場合には、再計算して別々の場所に納めるため、その分だけアクセス速度が低下してしまいます。

索引編成ファイル

索引編成ファイルは、索引を格納している索引域という領域と、レコードが格納されている基本データ域、そして、基本レコード域への追加で入り切らなかったものが格納されるあふれ域の3つの領域で構成されています。

f:id:Upatissa:20201222221607p:plain
索引編成ファイル

目的のレコードへのアクセスは、索引を利用して直前まで直接アクセスを行い、それ以降順次アクセスで到達するようなパターンもあれば、先頭から順次アクセスして到達するようなパターンもあります。

区分編成ファイル

区分編成ファイルは、順編成ファイルを応用させた編成方法です。
これは、メンバという順編成ファイルを複数格納したメンバ域と、各メンバのアドレスを持つディレクトリ域の2つの領域から構成されています。

f:id:Upatissa:20201222233254p:plain
区分編成ファイル

ディレクトリ域は各メンバのアドレスを元に直接アクセスして、メンバ単位で管理することが出来ます。
また、各メンバ内は、順編成ファイルと同じ形式であるため、内部の個々のレコードに対しては順次アクセスを行います。

この編成方法は、メンバ単位の編集に向いています。
しかし、順編成ファイルと同様に、各レコードの編集を行うことは困難であるという特徴があります。

参考にさせて頂いた書籍

きたみりゅうじ 『キタミ式イラストIT塾 基本情報技術者平成31/01年』 技術評論社 2019年

学習してみて

今回は、汎用コンピュータのファイルについて学習しました。
汎用コンピュータのファイルは現在のファイルとは異なっていて、どちらかというとデータベースの方が近いように感じられました。
しかし、次回からデータベースの学習に入っていくので、そのきっかけとしてとても有益内容だったのではないかと思います。

「ファイルとディレクトリ」 ① ファイル・ディレクトリの役割と指定方法

目次

ファイルとは何か

コンピュータは様々なデータやプログラムを処理し、補助記憶装置に記憶しています。
しかし、何のまとまりも無い状態でただ単に保存しているだけでは、どこからどこまでが何のデータで何の意味があるのかが分からなくなってしまいます。
だから、様々なデータやプログラムを管理するためには、その意味や目的に合わせてひと固まりにしておくことが必要になります。
このひと固まりのことをファイルと呼びます。

様々なファイル形式

ファイルには、その用途や中身、使用されるアプリケーションに応じて様々な種類があります。 また、ファイルの形式によっては、様々なアプリケーションで共通して使用できるものがある一方で、特定のアプリケーションでしか使用出来ないものもあります。

また、画像や音声、動画などのマルチメディアデータは、膨大なデータ量になってしまうため、データサイズを小さくする圧縮を行うことがあります。
圧縮の過程で、元のデータを切り落としてしまうことにより、圧縮前と同じ状態に戻せないものがあります。これを不可逆圧縮と呼びます。
一方で、圧縮前と同じ状態に戻せるものを可逆圧縮と呼びます。

代表的なファイル形式をまとめたものが以下の表になります。

ファイル形式 性質
テキスト形式 文字を扱うことを目的としたファイル形式。
ワープロなどの文字を扱うアプリケーションでは
ほぼ必ず扱うことが出来る。
CSV形式 個々のデータを数字やカンマで区切り、
行と行を改行で区切ることが出来るファイル形式。
表形式のデータ保存に特化している。
PDF 画像が埋め込まれた書類を様々な環境下で
再現出来る電子文書のファイル形式。

【画像用のファイル】

ファイル形式 性質
BMP 画像を圧縮せずに保存するファイル形式。
劣化しないがサイズが大きくなる。
JPEG 写真を保存するのに向いている形式。
圧縮率が高く、フルカラーを扱えるが、
不可逆圧縮で圧縮率に応じて画質が劣化する。
GIF イラストやアイコンの保存に向いている形式。
可逆圧縮で画質が劣化しないが、
256色までしか扱えない。
PNG フルカラーを扱える上、可逆圧縮であり、
画質が劣化しない。
しかし、圧縮率はJPEGの方が高い。

【音声用のファイル】

ファイル形式 性質
MP3 音声を圧縮して保存するファイル形式。
非可聴域の信号を削り、データ量を削減している。
MIDI ディジタル楽器の演奏データを保存する形式。
このファイルにより、ディジタル楽器の演奏が可能。

【動画用のファイル】

ファイル形式 性質
MPEG 動画を圧縮して保存するファイル形式。
不可逆圧縮を行う。

ディレクト

補助記憶装置の中に記憶されているファイルを用途別に束ねて管理する、フォルダの役割を果たすのがディレクトです。
ディレクトには、ファイルだけではなく、他のディレクトリを入れることが出来ます。
ディレクトリの中にある他のディレクトリのことを、サブディレクトと呼びます。
こうすることで、補助記憶装置を階層構造(ツリー構造)で管理することが出来るようになります。
階層構造の最上位にあるディレクトリのことをルートディレクトと呼び、「/」もしくは「¥」で表します。

ディレクトリの種類

コンピュータの様々なディレクトリのうち、ユーザが現在開いて作業中であるディレクトリのことをカレントディレクトと呼びます。
カレントディレクトリから見て1階層上のディレクトリのことをディレクトと呼び、1階層下のサブディレクトリのことをディレクトと呼びます。

f:id:Upatissa:20201220075332p:plain
ディレクトリによる階層構造

ファイル・ディレクトリの指定方法

階層構造になっているファイルまたはディレクトリを指定するための方法として、絶対パス相対パスの2種類があります。
どちらの指定方法も、指定する対象へ至るためのパス(経路)を記述します。

この2つの指定方法で異なっているのは、最初の出発点です。
絶対パスは、ルートディレクトリを出発点として指定対象へのパスを記述します。
一方、相対パスは、カレントディレクトリを出発点として指定対象へのパスを記述します。

ここで、絶対パス相対パスをより詳しく説明するために、以下のような階層構造について取り上げたいと思います。

f:id:Upatissa:20201221075350p:plain
階層構造

絶対パスの表記

例えば、絶対パスでファイルCを指定したい場合、ルートディレクトリが出発点になります。
そして、ディレクトリA、ディレクトリCを通り、ファイルCに到着するという経路になります。

これを文字にすると、「/ディレクトリA/ディレクトリC/ファイルC」となります。

f:id:Upatissa:20201221084945p:plain
絶対パスによるファイル指定

相対パスの表記

例えば、カレントディレクトリをディレクトリBとした状態から、相対パスでファイルCを指定したい場合、出発点はディレクトリBとなります。
そして、階層を1つ上り、親ディレクトリであるルートディレクトリを通り、ディレクトリA、ディレクトリCを通り、ファイルCに到着するという経路になります。

これを文字にするとき、カレントディレクトリは「.」、親ディレクトリは「..」で表します。
以上のことを踏まえると、「./../ディレクトリA/ディレクトリC/ファイルC」となります。

(※先頭のカレントディレクトリを表す「./」は省略することもできます。)

f:id:Upatissa:20201221085943p:plain
相対パスによるファイル指定

参考にさせて頂いた書籍

きたみりゅうじ 『キタミ式イラストIT塾 基本情報技術者平成31/01年』 技術評論社 2019年

学習してみて

今回は、日常的に使用しているファイルやディレクトリの役割と指定方法について学習しました。 普段当たり前のように使用しているので、そのありがたさを実感しにくいですが、コンピュータだけでなく、ユーザから見て情報を管理しやすくなっているのはファイルやディレクトリのおかげだと思います。
アドレス指定方式は使用する機会も非常に多いのでしっかりと押さえておきたいと思います。

「基本ソフトウェア」 ⑥ 仮想記憶管理

目次

物理的な記憶領域の課題

コンピュータの記憶領域は、主に主記憶装置と補助記憶装置によって構成されています。
この両者は物理的な記憶領域(実記憶)であるという点で共通しています。

しかし、物理的な記憶領域であるが故に、制約が常に付き纏っています。
つまり、両者には記憶容量に上限が存在していて、記憶領域を区画ごとに設定・管理する必要があるということです。

そのため、これらの物理的な記憶領域でプログラムを実行すると、様々な問題が発生します。
例えば、主記憶装置では記憶容量に制限があるために、それよりも大きなプログラムを実行することが出来ないという問題が発生します。
また、記憶領域を区画ごとに設定していることが原因で、記憶領域が断片化(フラグメンテーション)するという問題も発生します。

仮想記憶とは何か

このような物理的な記憶領域(実記憶)に対し、主記憶装置と補助記憶装置の記憶領域を合わせて作った仮想的な記憶領域を仮想記憶と呼びます。

仮想記憶は、実記憶のように実アドレス(物理アドレスで領域を管理するのではなく、論理的なメモリ、つまり仮想アドレス(論理アドレスで領域を管理します。

f:id:Upatissa:20201217112420p:plain
仮想記憶

プログラムの実行において、このような仮想記憶を使用することにより、見かけ上広大な記憶領域が利用出来るということになります。

仮想記憶によるフラグメンテーションの克服

実記憶でプログラムを実行するためには、物理的に連続した空き容量に読み込む必要がありました。
しかし、仮想記憶では物理的な制約がありません。
だから、仮想アドレスの範囲内であれば自由にプログラムを読み込むことが出来ます。

f:id:Upatissa:20201217112925p:plain
プログラムの読み込み

では、仮想記憶に読み込まれたプログラムはどこに行ったのかというと、実際には実記憶上に読み込まれています。
これだけでは、記憶領域の名前が変わっただけのように感じられるかもしれません。

しかし、仮想記憶の目的とは、実記憶のような物理的な記憶領域ではなく、仮想の記憶領域にプログラムなどをマッピング(対応付け・割り当て)することにあります。

だから、読み込まれるプログラムの立場からすると、物理的な制約が無い仮想記憶に読み込まれたように見えます。
しかし、実際には、仮想記憶の仮想アドレスと実記憶の物理アドレスは対応付けられていて、実記憶上に読み込まれているのです。

そして、この時、仮想アドレスと物理アドレスの対応付けの組み合わせは自由に設定することが出来ます

このように、仮想アドレスと実アドレスのマッピングを可能にしているのがメモリ変換ユニット(MMU:Memory Management Unit)というハードウェアです。
MMUによって仮想アドレスから実アドレスへの変換処理がなされ、プログラムは最終的に実記憶上に読み込まれることになります。
この変換処理の仕組みを動的アドレス変換機構(DAT:Dynamic Address Translator)と呼びます。

f:id:Upatissa:20201217120709p:plain
動的アドレス変換機構(DAT)

したがって、仮想記憶に読み込まれたプログラムは、記憶領域が連続しているか否かに関わらず、実記憶上の様々な場所に読み込むことが可能になります。

その結果、もし実記憶の記憶領域がフラグメンテーションを起こしていたとしても、物理的な配置を気にすることなくその隙間に読み込むということが出来るようになります。

仮想記憶による容量制限の克服

実記憶上でプログラムを実行する際、常に主記憶装置の容量という物理的な制約がありました。

しかし、仮想記憶では主記憶装置だけではなく、補助記憶装置も記憶領域と見なします。 だから、主記憶装置の容量制限を超えるような大きいサイズのプログラムであっても読み込むことが可能になります。

f:id:Upatissa:20201217130807p:plain
補助記憶装置を活用した動的アドレス変換機構(DAT)

このことから、仮想記憶とは、主記憶領域として使用できる見かけ上の容量を拡大させるための仕組みであると言うことが出来ます。

仮想記憶の実装方式(ページング方式)

仮想記憶をコンピュータに実装する方式は、「ページング方式」と「セグメント方式」の2つがあります。

本試験ではページング方式が取り上げられる傾向にあるようなので、ここではページング方式について取り上げたいと思います。

ページング方式とは、プログラムを固定長(一般的には4KB)の「ページ」という単位に分割して管理する方式です。

しかし、ページ単位でプログラムを取り扱うにしても、その機能によっては常に必要というわけではないものもあります。
だから、現在のOSでは、ページング方式の中でも、実行に必要なページだけを読み込むデマンドページングという方法が主流になっています。

デマンドページングでページを読み込む過程を示したものが以下の図になります。

f:id:Upatissa:20201218195758p:plain
ページング方式(デマンドページング)①

ページング方式では、ページを仮想記憶に読み込みます。
この方式において、仮想記憶の記憶領域はページ単位で分割されているため、補助記憶装置のページをそのまま仮想記憶に読み込むことが出来ます。

また、仮想記憶とは、実際には補助記憶装置と主記憶装置を合わせた記憶領域でした。
しかし、デマンドページングにおいて、この時点ではまだ主記憶装置にページを読み込んでいません。

ここで、コンピュータがプログラムのページAの機能を実行する予定であると仮定します。

f:id:Upatissa:20201218221405p:plain
ページング方式(デマンドページング)②

コンピュータがプログラムを実行するためには、必要なページが主記憶装置に存在していなければなりません。

しかし、この時点ではまだ、主記憶装置に実行予定のページAが読み込まれていません。
だから、このままプログラムを実行しようとすると、必要なページが実記憶装置上に見つからないことを意味するページフォールトという割り込みが発生します。

デマンドページングでは、この割り込みが発生してから実行対象となるページAだけを主記憶装置に読み込みます。
つまり、ページフォールトによってページの必要性が訴えられてから実行に必要なページだけを読み込むことになります。

ページテーブル

ページング方式では、最初に補助記憶装置上のページが仮想記憶に読み込まれます。 しかし、仮想記憶は、記憶領域が主記憶装置か補助記憶装置のうち、元々どちらのものであったかという物理的な区別をしません。

だから、そのままでは仮想記憶に読み込まれたページのうち、どのページが主記憶装置に読み込まれているのかを特定することが出来なくなくなってしまいます。

そこで、仮想記憶と主記憶装置に保存されているページを照らし合わせて特定することが出来るように、ページテーブルという対応表を使用します。
ページテーブルは、仮想記憶と主記憶装置の記憶領域の両者に紐付いています。
つまり、仮想記憶のアドレスにあたる仮想ページ番号に対応する主記憶装置の物理ページアドレスを控えているのです。

それだけではなく、仮想ページ番号ごとに読み込まれたページが存在しているか否かを示すフラグが設定されています。

f:id:Upatissa:20201219130635p:plain
ページテーブルの仕組み

このページテーブルを元に、「仮想記憶に読み込まれているが、主記憶装置上には読み込まれていないページ」が特定されます。
そして、それらのうち、もし実行に必要なページがあるならば、それだけを補助記憶装置から読み込みます。

このように、ページング方式で主記憶装置上に無いページを補助記憶装置から読み込むことを ページインと呼びます。

もし読み込み先の主記憶装置の空き容量が足りない場合には、いずれかのページを補助記憶装置に追い出して空き容量を作ります。
このことを ページアウトと呼びます。

主記憶装置の記憶容量が小さいと、ページアウトの頻度が高くなります。 ページアウトは、主記憶装置と低速の補助記憶装置間のやりとりであるため、頻度が高くなればそれだけ処理効率が悪くなってしまいます。
この現象をスラッシングと呼びます。

ページイン/アウト のアルゴリズム

主記憶装置に空き容量がない状態でさらにページを読み込むためにはページアウトを実行する必要があります。
しかし、またすぐに必要になるページをページアウトしてしまうと、再度読み込み(ページイン)が必要になり、かえって実行効率が悪くなってしまいます。
だから、プログラムをページング方式で実行するにあたって、ページインとページアウトが効率よく実行されるようなアルゴリズムをあらかじめ定めておく必要があります。

f:id:Upatissa:20201219145317p:plain
ページの置き換えアルゴリズムの必要性

ページ置き換えのために必要なアルゴリズムを説明するための例として、以下の図のような順序でページを読み込む場合を取り上げたいと思います。

f:id:Upatissa:20201219175237p:plain
ページ置き換え例

この例の順序に従い、補助記憶装置から主記憶装置にページを読み込んだ時の過程を以下の図に示します。

f:id:Upatissa:20201219203921p:plain
ページ置き換え過程①

ページをこの順で読み込むと、3番目のページCを読み込んだ時点で主記憶装置の記憶領域はいっぱいになってしまいます。
しかし、その後のページAとCは既に読み込み済みなので、再度そのまま読み込めば良いということになります。

f:id:Upatissa:20201219204453p:plain
ページ置き換え過程②

ところが、最後のページDを読み込むためには、既に読み込まれたページA・B・Cのうちのいずれか1つをページアウトさせなければなりません。
ここで、アルゴリズムに基づき、ページアウトさせるページを判断する必要性に迫られます。

ここで、この例を使って、ページ置き換えのアルゴリズムについて取り上げていきたいと思います。
ページ置き換えの判断基準となるアルゴリズムには以下の4種類があります。

  • FIFO (First In First Out)方式
  • LIFO (Last In First Out)方式
  • LRU (Least Recently Used)方式
  • LFU (Least Frequently Used)方式

FIFO (First In First Out)方式

FIFO方式では、最初にページインしたページ(First In)を追い出す対象にします。 この例において、最初にページインしたのはページAなので、この方式ではページAをページアウトさせることになります。

f:id:Upatissa:20201219212542p:plain
FIFO (First In First Out)方式

LIFO (Last In First Out)方式

LIFO方式では、最後にページインしたページ(Last In)を追い出す対象にします。 この例において、最後にページインしたのはページCなので、この方式ではページCをページアウトさせることになります。

f:id:Upatissa:20201219213857p:plain
LIFO (Last In First Out)方式

LRU (Least Recently Used)方式

LIFO方式では、最も長い間参照されていないページを追い出す対象にします。 この例において、最も長い間参照されていないのはページBなので、この方式ではページBをページアウトさせることになります。

f:id:Upatissa:20201219214811p:plain
LRU (Least Recently Used)方式

LFU (Least Frequently Used)方式

LFU方式では、最も参照回数が少ないページを追い出す対象にします。 この例において、最も参照回数が少ないのはページBなので、この方式ではページBをページアウトさせることになります。

f:id:Upatissa:20201219215514p:plain
LFU (Least Frequently Used)方式

参考にさせて頂いた書籍

きたみりゅうじ 『キタミ式イラストIT塾 基本情報技術者平成31/01年』 技術評論社 2019年

学習してみて

今回は、仮想記憶についての学習でした。
仮想記憶は主記憶装置と補助記憶装置の記憶領域を足し合わせたものであるということを意識しておけばそれほど難しい内容では無いかと思います。

しかし、学習しているうちに仮想記憶という第3の記憶領域が存在するかのように錯覚してしまい、ページング方式の仕組みが分からなくなってしまうことがありました。

今後また復習することになるかと思いますが、その場合にはこのことを思い出して、スムーズに理解することができるようになっておきたいと思います。