木構造と仮想

総合科目「ネットワーク社会を支える情報技術入門 II」、2011年10月03日

                                       筑波大学システム情報工学研究科／電子・情報工学系
                                       新城 靖
                                       <yas @ cs.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.softlab.cs.tsukuba.ac.jp/~yas/gen/it-2011-10-03
あるいは、次のページから手繰っていくこともできます。
http://www.softlab.cs.tsukuba.ac.jp/~yas/gen/
http://www.cs.tsukuba.ac.jp/~yas/

印刷配布資料 http://www.softlab.cs.tsukuba.ac.jp/~yas/gen/it-2011-10-03 /it-2011-10-03 .pdf

■木構造

木構造（tree structure）というのは、コンピュータ・サイエン ス（情報学類、情報科学類で学ぶ学問）でよく使われる用語である。分野によっては、同じ ものを階層構造（hierarchical structure）という言葉で表現す ることが好まれる。ドイツ語語源の、ヒエラルヒー(Hierarchie)という言葉が 使われることもある。

木構造の例を、大学の組織を使って説明する(図1)。

• 木構造は、節と枝からできている。
• 特別な節として、根(root)が１個ある。
• 末端の節を葉(leaf)と言う。
• 木構造では、ある節から別の節までの道が１通りしかない。
• つながっている節と節で、根に近いものを親、そうでない ものを子という。

• 筑波大学が木の根にあたる。根からは、何本かの学群の枝が出ている。 コンピュータ・サイエンスでは、木の根を上に書く習慣がある。
• 情報学群の節には、情報科学類、情報メディア創成学類、知識情報・図書館学類の子の節がある。 情報学群の親は、筑波大学である。
• 学群は中間節、学類は葉(端節)である。

◆字下げによる木の表現

筑波大学

• ・・・
• 社会・国際学群
  • 社会学類
  • 国際総合学類
• 理工学群
  • 数学類
  • ・・・
  • 工学システム学類
• 情報学群
  • 情報科学類
  • 情報メディア創成学類
  • 知識情報・図書館学類
• ・・・
• ・・・

◆区切り文字入り表記

筑波大学情報学群情報科学類

コンピュータの中で、文字列（文字の並び）で木構造上の位置を表現する時に は、節が分かりやすくために、はっきりと区切りを入れて表現することがよく 行われる。

筑波大学．情報学群．情報科学類

筑波大学／情報学群／情報科学類

情報科学類．情報学群．筑波大学

区切り文字としては、「．」（点）、「／」（スラッシュ）、「＼」（バック スラッシュ）、「￥」（円記号）などがよく使われる。単語を並べる時に、木 の根に近いほうから書く流儀と遠い方から書く流儀がある。

◆木の例

コンピュータでは、次のような場所で木構造が使われている。

• ファイルの名前
• インターネット上のコンピュータの名前
• 電子メールのアドレス
• World Wide Web のアドレス (URL)
• ネットワーク・ニュースのニュース・グループの名前
• さまざまなメニュー

コンピュータ以外では、次のような場所で木構造が使われている。

• 分類（生物、図書館の本）
• 住所
• 会社組織、官僚機構
• １つの文
• １つの文書

◆文の構造

Time flies like an arrow.

◆英語の文法

1. S V
2. S V C
3. S V O
4. S V O O
5. S V O C

<sentence> ::= <simple sentence> '.'
        または <compound sentence> '.'
        または <compound-complex sentence> '.'

<simple sentence> ::=  <clause>

<compound sentence> ::=
           <clause>  ','  <FANBOYS>  <clause>
    または <clause>  ';'  <transition word> <clause>
    または <clause>  ','  <conjunctive> <clause>

<complex sentence> ::=
           <dependent clause> ',' <independent clause>
    または <independent clause>   <dependent clause>

<compound-complex sentence> ::=
    <clause> <dependent clause>

<dependent clause> ::=  <subordinate> <clause>

<subordinate> ::=
           <subordinate-adj> または <subordinate-adv>
    または <subordinate-noun>

<subordinate-adj> ::=
    who または whom または that または which

<subordinate-adv> ::= after または before または because
    または although または since

<subordinate-adv> ::= that または whether

<clause> ::= 基本５文型で表せるもの

<FANBOYS> ::=
    for または and または not または but または
    or または yet または so

<conjunctive> ::=
    <subordinate conjunction> または <coordinate conjunction>
    または  <conjunctive adverb>

<subordinate conjunction> ::= as, if, that など

<coordinate conjunction> ::= and, but, or, for など

<conjunctive adverb> ::= however, nevertheless,
                         still, then など

◆文書の木

• 章立て。章、節、項。
• 箇条書き。箇条書きの中に箇条書き。
• パラグラフ

◆ディレクトリの木

ディレクトリは、全体では 木構造(tree structure) になっている。階層化ディレクトリ（hierarchical directory）と呼ばれるこ ともある。

◆パス名

ファイルの名前の表現には、「パス名」がよくつかわれる。パス (path)とい うのは、道の意味である。パス名では、どの道を通ればよいかの道順を示すこ とでファイルの名前を表現する。

木構造では、節、または、枝(道)に名前がついている。ファイル名は、区切り 文字で区切られた、節、または、枝の名前の並びになる。ファイルの名前を表 現する時の区切り文字としては、次のものがよく使われる。

• ／
• ＼
• ：

パス名の例:

• /home/s123456
• /usr/bin/emacs

◆世界最大の木構造:DNS(Domain Name System)

電子メールを送ったりWorld Wide Web のページを閲覧する時には、データの 送り先やデータを持っているコンピュータを指定する必要がある。 インターネットで使われている、コンピュータの名前を管理する仕組みは、 DNS(Domain Name System) と呼ばれている。 DNS では、膨大な数のコンピュータの名前を含む名前空間を階層的にドメイン （領域）に分割して管理している。

たとえば、次のような名前を考える。

azalea1.coins.tsukuba.ac.jp

「azalea1.coins.tsukuba.ac.jp」を 図8で考えると、次のようになる。

• 名前空間全体は、まず、af, al, ・・・, jp, ・・・, uk, zw というド メインに分割されいる。その中の jp を選ぶ。
• その中の jp ドメインは、ac, ad, co, ne, gr, or などのドメインに分 割されている。その中の ac を選ぶ。
• その中の ac ドメインは、ass, ・・・,tsukuba, ・・・, zokei 等のドメ インに分割されている。その中の tsukuba を選ぶ。
• tsukuba ドメインは、さらに cc, is, coins などのドメインに分割されて いる。その中の coins を選ぶ。
• 最後に、coins ドメインに azalea1 という名前が登録されている。

• まず根から出発する。
• 根の下の jp という節を選ぶ。
• その下の ac という節を選ぶ。
• その下の tsukuba という節を選ぶ。
• その下の coins という節を選ぶ。
• 最後に、その下の azalea1 という節(葉)を選ぶ。

■木構造の制約と問題点

大量の情報を保存するには、木構造を使うしかない。 しかし、、、

◆こうもりの分類問題

◆シンボリック・リンク／エイリアス／ショートカット

木構造は、ファイルを整理するのに非常に強力な構造である。しかし、それだ けでは、ファイルを整理するには不都合が起きる。それを解消するために、次 のような名前で呼ばれる仕組みが用意されている。

• エイリアス(alias, Macintosh)
• ショートカット(shortcut, Windows)
• シンボリック・リンク(symbolic link,UNIX)

◆図書の分類

• 木構造の各節は、(最大)10個の子供の節への枝を作る。 枝には、0から9の名前をつける。
• 根から枝をn個たどった場合、n個の数で表す。 例: 007.64 は、根から 0→0→7→6→4 とたどった枝を意味する。

• 木のバランスがとれていない。時代の変化について行けない。 兄弟の節で、自分より下の節の本の数が違う。 （例：コンピュータ系は、数が多いが、007.6 のように深い階層にある。）
• いくつかの種類がある。日本十進分類法、 デューイ十進分類法。
• １つの視点からの分類しかできない。コウモリの分類問題問題。

◆木構造を使わない図書の分類

◆ファセット(カテゴリ)をつかう分類

例: アパートの分類。次のような項目から任意の順で絞り込める。

• 住所
• 家賃
• 間取り
• 通勤時間
• 築年数

■仮想とは

◆コンピュータ由来の「仮想」の意味

• ソフトウェアの働きで作られている。
• 現実のもの(ハードウェア)と置き換え可能である。仮に取り替えても、 (ある範囲では)利用している側には気がつかれない。

類語：抽象(abstract)、論理(logical) (←→物理(physical))

反語：実(real)

■仮想記憶（virtual storage,仮想メモリ,virtual memory）

◆(物理的な)メモリ

メモリ(メインメモリ)、RAM(Random Access Memory)

実行中のプログラムを保持する。加工するデータを一時的に保持する。 ＩＣ（Integrated Circuit、シリコンという元素による半導 体で作られた電気回路）で作られているので、速い。 容量は、ハードディスクよりは小さい。値段が高い。 (揮発的(電源を切ると消えてしまう)。)

ハード・ディスク (HD(Hard Disk), HDD(Hard Disk Drive))

プログラムやデータをデータを保持する。 容量は、メモリより大きい。値段が安い。 (永続的である(電源を切っても残っている)。)

メモリには、数字で番地（アドレス）が付いている。番地を指定して、データ を保存する。番地を指定すると、データが取り出せる。

◆仮想記憶(仮想メモリ)

仮想記憶(仮想メモリ、virtual memory)とは、オペレーティングシステムの働きにより、実際に備えているメ モリ容量よりも大きなプログラムを動かすための仕組みである。

主記憶 (main memory, primary storage)

RAM で作る。小容量、高価。

二次記憶(secondary storage)

ハードディスクで作る。大容量、高価。

ページ

主記憶と二次記憶（ハードディスク）を固定長のブロックに分けたもの。 大きさは、4Kバイト-8Kバイトが一般的。

ページアウト

主記憶にある（当分使いそうにない）ページを、二次記憶へコピーする。

ページイン

二次記憶にある（現在必要とされている）ページを、主記憶へコピーする。

仮想記憶の基本的なアイディアは、高価な RAM の容量を、 安価なハードディスクを使って、「事実上」拡大する。 すぐに使うところだけを速いメモリ（ＩＣ）に、当分使わない所を、遅いハー ドディスクに置き、ディスクとメモリの内容を入れ替えながら仕事を進める。 この時、速いメモリを主記憶、遅いハードディスクを二次記憶とう。

仮想記憶を使うと、メモリが 1000 M バイトしかないコンピュータで、2000 M バイトのメモリを使うプログラムを実行することができるようになる。

もともとは、１つのプログラムで実際のメモリ容量以上のものを使うための仕 組みである。最近では、複数のプログラムが使うメモリの総量で考えることも ある。

■仮想計算機(virtual machine)

◆コンピュータの構成

• 1セットのハードウェア(実計算機)を1つのオペレーティング・システム(OS)が操作する。
• OSの上で複数のアプリケーション・プログラムが動作する。
• ハードウェアには、次のようなものが含まれる。
  • CPU
  • メモリ
  • 周辺装置(ハードディスク、ディスプレイ、キーボード、ネットワーク・カード)

◆仮想計算機

仮想計算機モニタは１個でも、複数の仮想計算機を作ることができる。

◆仮想計算機の利用方法

• もともと複数のコンピュータで行っていた仕事を1台の物理的なコンピュー タでこなすために集約する。
• 1台のコンピュータで、複数のオペレーティング・システム用の アプリケーション・プログラムを同時に利用する。
• ハードウェアが故障した時に、簡単に交換できるようにする。
• データのバックアップや、ソフトウェアのインストールを簡単にする。
• クラッシュに強くする。(書き込みを取り消すことができるハードディスクを使う。)
• オペレーティング・システムの開発環境として利用する。
• セキュリティを高める。

◆コンピュータの集約

• 1970年代: ハードウェアの価格が高い。 1つのハードウェアで複数のOSが走れば、 ハードウェアを買うお金が節約できる。
• 現在: コンピュータの高速化で、性能が余ってきた。もともとハードウェアｎ台でやっ ていた仕事を、ハードウェアとしては１台でこなせるようになってきた。 並列処理の逆。

◆ハイパーバイザ型とホスト型

ハイパーバイザ型

実計算機上で仮想計算機モニタが動作する。

ホスト型

実計算機上では普通のオペレーティング・システムが動作する。 仮想計算機モニタは、そのオペレーティング・システムの１つの アプリケーションとして動作する。

◆仮想計算機モニタの実例紹介

• Windows
• Linux

◆エミュレータとシミュレータ

エミュレータ

別のシステムで、本物のシステムと同じ動きを真似するソフト ウェア。本物は、必ずしもコンピュータ全体（計算機）でなくてもよい。

• Wine: Unix 上で Windows 用のプログラムを実行するためのプログラム。 Wine は、Windows のソフトウェア部分(システム・コールと実行時プログラム)をエミュレートする。
• 端末エミュレータ: 文字端末 の機能を全部、 または、部分的にエミュレートする。

シミュレータ

現実世界の予測に使うもの。数式でモデル化して計算で予測 する。実際にやるとコストがかかるもの、取り返しがつかないものをコンピュー タの中で実行する。現実の代わりにはならない。（エミュレータは、本物の代 わりに使える。シミュレータは、本物の代わりには使えない。）

• フライト・シミュレータ
• 地球シミュレータ

(文字)端末

◆セキュアVM/BitVisor

目標: オペレーティング・システムやアプリケーションに依存しない形でセキュ リティ機能を付加する。

• ＩＣカードがないと、オペレーティング・システムが起動しない。 盗難にあっても、他人には使われない。
• ハードディスクが自動的に暗号化される。 ハードディスクのが取り出されても、 情報漏えいが発生しない。
• 強制的に 仮想プライベート・ネットワーク に参加させ、ネットワーク通信を暗号化すると共に、 利用可能なネットワークを制限する。

http://www.bitvisor.org/ http://www.securevm.org/

■仮想記憶、仮想計算機以外の仮想

◆VPN(Virtual Private Network)

VPNを実現する技術:

• PPTP
• L2PT over IPsec
• Packetix VPN (SoftEther VPN)
• UT-VPN 　　http://utvpn.tsukuba.ac.jp/
• OpenVPN
• SSL-VPN

筑波大学では、学外から学内のサービス(Twins等)を利用するために使える。

• 学術情報メディアセンター　　 http://www.cc.tsukuba.ac.jp/network/access/vpn.html
• 情報科学類　　 http://www.coins.tsukuba.ac.jp/ce/ (手引きの中)

◆仮想ディスク(virtual disk)

• データを暗号化して保存する。
• 複数のファイルからなるソフトウェアを１まとめにする。
• CD-R などに書き込むためのファイルを一時的に蓄える。

◆仮想現実感(virtual reality)

人間が働き掛けると、現実と同じように応答する。感覚のフィードバックがある。

◆世俗的な「仮想」

• 仮想都市、仮想社会
• 仮想大学、仮想教官、仮想学生
• ・・・