場合 - みる会図書館

1. UNIX MAGAZINE 2003年5月号

特集・プログラミング入門なお、この処理をおこなう際に、探索文字列の末尾の文字に対する引・算はしていません。もし探索文字列の末尾の文字を調べているときに不一致が発生するのであれは、の文字ではないことは明らかです。ほかの場所で不一致が発生した場合も、探索文字列の末尾の文字を不一致の発生した位置に移動する必要はありません。移動しなけれはならないのは、不一致が発生した場所よりも左側にある探索文字列内の文字だからです。このように、末尾の文字を考慮する必要はないため、 skip 配列の言算には含まれていません。不一致を検出したときは、この配列を使って、探索文字列をどれだけ進めてよいのかを匐十ヾます。この配列に↑巒内されている値は、探索文字列の末尾の文字を十ヾていて不一致が発生したときにどれだけ動かしてよいかを表しているので、実際に移動する際には、末尾から何文字目を処理している状態なのかを考慮に入れたうえで移動する必要があります。このために作った関数は次のようなものです。 search(char *t , char *s) int 図 9 同じ文字か複数回出現する場合 a 図 10 a 図 11 a b a b a a e a b b a e i をインクリメントした場合 b a b a a a b b 2 文字進めた場合 b a b a a a b e a e b d d e d a a a a e int i , j ; int tlen, slen; tlen = strlen(t) ; strlen(s) ; slen 1 while (i く = tlen for (j SIen if (j くの return i ; slen) 1 ; j > = 0 return ー 1 ; if (skip[(int)t[i + j]] く十十・ else i + = skip[(int)t[i + j] & & sCj] (slen ー 1 slen ー j) この関数では、 i は文字列のインデックスとして、 j は探索文字列のインデックスとして利用しています。ます、 i を文字列のう巨頁に設定し、探索文字列の末尾から調べるために j を slen—l から 0 になるまでデクリメントしながら繰り返します。ここでチェックするのは文字列の一分と探索文字列が -- ー・致していることです。もし、探索文字列のすべてが・一致していれは、内側のループを終えたとき UNIX MAGAZINE 2003.5 に j の値は負の数になるはすです。この場合には、一致した文字列の地可立置を表す i の値を返します。不一致が発生した場合にも内側のループを終了します。このとき、 j の値は 0 以 E で、不一致が発生した文字は探索文字列側が s[j] 、文字列側が t[i + j] となります。こで、文字列側の不一致文字に対応する skip 配列の値が slen—j よりも小さい、つまり skip 配列に登録されている値を言 fr 算するために利用した文字か不一致文字よりも右側にある場合には、たんに i をインクリメントします。それ以外の場合、つまり skip 配列に登録されている値を計算するために利用した文字か不一致文字よりも左側にあれは、その文字のところまですらすために skip 配列の値を i に加えます。 skip 配列に登録されている値を計算するために利用した文字か不一致文字よりも右側にある場合、実際には 1 文字より多く移動させられる場合があります。図 9 の例を見てください。不一致が発生している文字列の文字は a です。この探索文字列では、 skip 「 a'] は 1 となっています。これは注目点よりも右にある文字 a に対して引・算された値です。の場合、さきほどのプログラムでは i をインクリメントしているので、次の探索の様子は図 10 のようになります。しかし、文字 a は探索文字列の注目点よりも 2 文字左まで存在しないので、実際には 2 文字進めることができま 95

2. UNIX MAGAZINE 2003年5月号

tsort コマンドにはオフションがいくつか用意されており、いすれも依存関係の循環を検出したときの重川乍を制御するためのものです。ー 1 は、依存関係の循環を発見したときに、それらの循環のなかから最長のものをみつけるためのオプションです。 -d は、循環が発生した原因をより詳しく表示し、循環を解消する丁掛かりを提供します。最後の一 q は、上記の 2 つのオフションとは考え方が異なります。これは、循環があってもそれをエラーとして扱わすに処理を続けるためのオプションです。こで、 tsort コマンドの生い立ちを紹介しておきましよう。もともと、 tsort はライプラリに登録するファイルの順番を決めるために使われるコマンドでした。ライプラリへの追加はファイル単位でおこなわれます。このとき、ファイルに含まれる複数の関数はまとめて追加することになります。あるライプラリ関数をプログラムのなかて利用すると、その関数が含まれるファイルがライプラリ・ファイルから取り出され、プログラムのリンク時に結合されます。ここで問題となるのは、プログラムで用いられるライプラリ関数自身が、別のライプラリ関数を利用することがある点です。このような場合には、間接的に利用されるライプラリ関数もリンク時に結合する必要があります。これらの関数か同じライプラリに登録されているとき、間接的に利用するライプラリ関数のはうか現在処理している場所より後ろにオ内されていれは、ライプラリを一度処理するだけで必要な関数をすべて結合することができます。しかし、現在処理している場所よりも前にオ内されていると、もう一度ライプラリ全体を処理しなけれは結合できません。プログラムが printf 関数を利用する場合を考えてみましよう。 printf 関数は、内部で write 関数を呼び出しています。 libc ライプラリに printf 、 write の順にオ内されている場合、プログラム側で printf 関数が必要なときに libc ライプラリを前から順番に処理していってそれを結合します。この段階で write 関数も必要なことが分かりますが、そのまま libc ライプラリの処理を進めていけばこれも結合できます。一方、 write 、 printf の順に登録されている場合はどうでしよう。 libc ライプラリを処理していき、 printf 関数を結合するところまでは同じです。しかし、 write 関数が必要なことが分かった段階で、 libc ファイルの write 関数 114 か登録されている場所はすでに処理を終えているため、のまま libc ファイルの末尾まて処理しても write 関数を結合することはできません。けっきよく、もう一度 libc ライプラリを : 麪頁から処理しなおさなければなりません。このような条件下で、できるかぎり 1 回の処理でリンク作業を終らせるには、ライプラリ関数間の依存関係を抽出し、その関係がイ尉寺される順番でライプラリに登録すればよいでしよう。この順番を引算するために作られたのが tsort 関数です。現在はライプラリ内にインデックスが作成されているので、後ろに登録された関数から前に登録されている関数を呼び出せないといった制限はありません。したがって、 tsort 関数は当初の彳難リを終えたわけですが、コマンド自体は残り、オプションも当時の名残をとどめています。 -q オフションが作られたのは、ライプラリを構築する際にやむをえす循環か生じるような場合に、いちいち工ラーか報告されるのを避けるためでしよう。このオプションを指定すると、ライプラリに登録するファイルの順番を決める際に循環カ吽しても、エラーメッセージを表示しないようになります。 tsort コマンドでのテータベースの利用 tsort コマンドでは、入力として・与えられたグラフの情報をイ寺しておかなけれは、、出力を引算することができません。 tsort コマンドは、このグラフの情報を一尉寺するためにデータベースを利用しています。データベースを検索するときのキーになるのは、ノードの名前です。データベース検索の結果として得られるデータ構造には、ノードに必要帯に ( たとえば、そのノードから出ているアークの一覧など ) か含まれています。こて利用しているデータ構造は、もちろん構造体の形式で定義されています。しかも、あるノードから出るアークの数はあらかしめ決定できないため、データ構造としてはポインタ寺し、その先に複数のアークを登録できるようにしています。また、データ構造のなかにはノードの名前も含まれますが、これも長さによって実際に占める領域のサイズが変わります。こで扱うデータ構造は可変長のデータであつまり、り、固定長のデータを登録するデータベースには向いてい UNIX MAGAZINE 2003.5

3. UNIX MAGAZINE 2003年5月号

特集 SoIaris 9 の管理と運用図 17 パッチのインストール兄認 op@blade$ showrev —p ー grep 112785 Patch: 112785 ー 12 Obs01etes : Requires : lncompatibles : SUNWxwp1x , SUNWxwman , SUNWxwinc , SUNWxws1b , SUNWxwsrv Patch: 112785 ー 04 Obs01etes : Requires : lncompatibles : Packages : Packages : SUNWxwf nt , SUNWxwp1t , SUNWxwpIt , SUNWxwsrv コードが表示された場合は、 /var/sadm/install-data/ Solaris-9-Recommended 」 og ファイルを参照して原因をヾ、適切な対策を講しる必要がある。パッチのインストールカ鮗了したら、システムを再起動する。推奨パッチクラスタにはカーネルのパッチが含まれていることも多いので、 : 起動は避けられない。システムにインストールされているパッチは、 showrev —p で一覧表示できる。 Sun では、、、パッチ番号ーリリース番号 " という形式でパッチ名を管理している。そのため、あるパッチがシステムにインストールされているかを調べるには、図 17 のように showrev コマンドの出力から grep コマンドでパッチ番号を検索すれはよい。この図の例では、 X ウインドウ・システム用パッチのリリース 12 とリリース 04 か、適用されていることが分かる。新しいリリースは、つねに旧いリリースを完全に含むので、リリース 12 の適用前にリリース 04 を適用しておく必喫はないにの例の場合は、おそらくパッチクラスタを 2 回インストールしたのであろう ) 。バッチのバックアウト残念ながら、パッチがつねに完全であるとはかぎらない。パッチ自体にバグがあり、適用することによってシステムの重乍がおかしくなることもある。あるいは、パッチの適用によってコマンドの設定方法や挙動が以前とは異なってしまう場合もある。不幸にしてパッチに不具合があったときは、 patchrm コマンドを用いてパッチを適用する前の状態に戻す ( バックアウトする ) ことができる。ただし、パッチをバックアウトするには、当然ながら、パッチ適用前のファイルをバックアップしてあることか則提となる。図 16 の例のように、オプションを付けすに install-cluster を実行した場合は、 /var/adm ディレクトリにパッチをバックアウトするためのファイルがバックアップされている。 48 パッチの適用後になんらかの不具合が生じたときは、ます、どのパッチが原因なのかを突き止めねばならない。これはなかなか面倒なイ業である。だが、経験を積んで、システムのどこに何があり、ドキュメントのどこに何か書いてあるかが分かるようになると、調査も効率的におこなえるようになる。おおまかな手順は、次のようになる。 1. マニュアルを読み、異常な重川乍をしているコマンドがどのパッケージに含まれるかを調べる。オンライン・マニュアルのツ朝匠くにある AVAILABILITY ( 和文では、使用条件 " ) 、または末尾近くの ATTRIBUTE ( 和文では、、属性 " ) という項目に、属するパッケージか書かれている。たとえば、 X のフォントサーバーの重川乍がおかしいとしたら、、 man xfs" を夫行し、 SUNWxwfs パッケージに含まれていることを突き止める。 2. showrev—p コマンドを実行し、そのノヾッケージを変更しているパッチ番号を調べる。上記の例であ川ま次のようにする。 op@fire$ showrev -p ー grep SUNWxwfs Patch: 113923 ー 02 ObsoIetes : Requires : lncompatibles : Packages : SUNWxwfs 3. パッチの README ファイルを読んで変更点を石忍する。このファイルは、 /var/sadm/patch ディレクトリの下に保管されている。パッチに依存関係がある場合などは README に明記されているはすなので、十分に確認する。 4. 、、あたり " をつけたら、 patchrm コマンドでパッチをバックアウトする。 root@fire$ patchrm 113923 ー 02 これはごく単純な例だが (f 列示したパッチが不正なわけではない ) 、パッチがいくつも適用されているパッケージや、含まれるファイルの多いパッケージなどの場合は、どのパッチが原因かを突き止めるだけでもかなりの手間がかかる。試行錯誤を繰り返すとサービスの停止時間カ張くなりがちなので、次に紹介する solaris Live Upgrade を UNIX MAGAZINE 2003.5

4. UNIX MAGAZINE 2003年5月号

特集・プログラミング入門り返します。もう文字列か残っていないという状態になったときには、目自勺の探索文字列が含まれなかったことになるため、文字列が存雀しないことを示す一 1 を返します。 while (i く = tlen) { if (hs (t) return 」 ; ()t + ASIZE * PRIME * b) % PRIME; ()t * ASIZE + t [ i + + ] ) ht return ー 1 ; % PRIME; ハッシュ値の更新においては、すでに計算してあるハッシュ値から、ハッシュ値の引算に関与・しなくなる先頭の文字 ( 新 ) による景彡響をなくすために減算し、全体を ASIZE 倍したあとに新たな末尾の文字 (t[i]) の景斧加えるために加算しています。最初の行の計算で ASIZE x PRIME を加えているのは、その直後の減算により全体が負の数になってしまうのを避けるためです。残念ながら、負の数の値に対する剰余演算の結果が正の数になる処理系と負の数になる処理系があるため、どちらの処理系でも正しく動作するようによけいな値を加えています。ここで加えた値は、最後に剰余演算によって消えてしまうので、この値を加えたためにおかしくなるようなことはありません。こで作成したプログラムは、 0 ( m 十れ ) で動作します。ところが、厳密にはこのプログラムは正しくありません。というのも、ハッシュ値カ尊しい場合に文字列が一一致していると判断していますが、これはかならずしも真ではありません、で 1 ・算しているのはあくまでハッシュ値ですから、ハッシュの衝突か起きる場合もあります。そのため、実際にはハッシュ値か等しいときにかならす文字列自身の上交をおこなう必要があります。文字列の上師交をおこなって等しいときにのみ、探索文字列を検出したとするのです。ノ、ツシュ値カ尊しいときに文字列を石忍するコードを付けると、最悪の場合の引算量は 0 ( m れ ) となってしまいます。これは、すべての部分文字列のハッシュ値か 1 司し値になった場合を考えてみれは分かると思います。すべての部分文字列を調べるために広そのそれぞれについて文字列自身か等しいかどうかを調べるために m の手間がかかるので、けっきよく 0 ( れ m ) となってしまいます。しかし実 98 際には、さきはども述べたように PRIME を大きな値にできるため、ハッシュの衝突はほとんど発生しないようにすることができます。したがって、実用的には 0 ( rn 十れ ) と考えても間題はありません。実際のプログラミングにあたってこれまでみてきたように、同じ問題を鮹夬するにも複数の去があります。実際に間題を解決するためには何をすれはよいのでしようか。最初にやるべきことは間題の整理問題の整理と分析ーロに探索といっても、前回までにとりあげた、あるデータ集合のなかから単一のデータを探しだす方法と、今回紹介した文字列のなかから探索文字列を探しだす方法では、利用するアルゴリズムか異なります。文字列のなかからある探索文字列を探しだすために普通の探索のアルゴリズムを使おうとすれは、探索文字列の長さ倍の領域や時間がかかるでしよう。というのも、通常のでは、要素がキーの値と等しいかどうかは 1 回の上交で判定できるという前提て考えてきました。しかし文字列探索の場合には、それぞれの文字の上交に対して手間を言算します。単純に考えても、上交のために探索文字列の長さ倍の手間がかかってしまうはすです。領域についても同様です。文字列として捉えれば途中のどこから始まっても同しだということが分かりますが、通常の探索ではそれぞれのデータが独立して存在しているものと仮定しています。すると、なえられた文字列から取り出すことが可能な探索文字列と同じ長さのすべての文字列か存在するものとして処理を進めることになるでしよう。この場合には、領域カ甘架索文字列の長さ倍必要になってしまうわけです。間題を分析して、どのような処理が可能かを検詞することも重要になります。探索が必要となる場面は、これまでみてきたようなデータの探索や文字列架索といった基本的な問題だけとはかぎりません。一見すると、もっと複雑にみえるような間題の場合もあります。たとえは、 DNA のなかから特定の遺伝子の部分を抽出 UNIX MAGAZINE 2003.5

5. UNIX MAGAZINE 2003年5月号

•Xserve 情報を利用してファイルへのアクセスが許可されたり、プリンタなどのテンヾイスか利用できるかどうかか決定されたりします。これらの情報を個々のシステムか独自に管理していたのでは、整合生をイ尉寺したり、データの新規登録などをおこなうたびに大変な手間がかかります。そこで、これらをサーバーに集中させ、、、ディレクトリ・ドメイン " と呼はれる大きな 1 つのデータベースとして扱うガ去が考案されました。このディレクトリ・ドメインにあるデータを検索したり取得したりすることを、、、ディレクトリ・サーピス " といいます。代表的なディレクトリ・サービスには、 Sun か発した NIS (YP) や Windows 2000 の Active Directory などがあります。 Open Directory とは、 Mac OS X におけるディレクトリ・サーピスのアーキテクチャです。 Open Direc- tory では、下記のものをディレクトリ・ドメインとして利用できます。・そのコンピュータ自体、およびその他の MacOSX Server のディレクトリ・ドメイン・ Apple 以汐トのサーノヾーの LDAP (Lightweight Di- rectory Access Protocol) ディレクトリ・ドメインと Active Directory ドメインを含むはかのサーノヾーのディレクトリ・ドメイン 8 BSD UNIX て利用されている /etc/passwd や /etc/group な 11 のウインドウか現れます。さきほどの Server As- 成功すると、このユーティリティの概要が示され、図スワードを訊かれます。これらを正しく入力して認証が設定するサーバーのホスト名、管理者のユーサー名とパータ上で Open Directory Assistant を起測けると、 Open Directory を成疋してみましよう。管理コンピそれでは、 Open Directory Assistant を使ってことによってディレクトリ・サーピスを実現しています。を、一己のディレクトリ・ドメインから検索、取得する Open Directory では、プロセスから要求された情報バーなどのネットワーク・サービスビス検出プロトコルによって認識されたファイルサー Protocol) 、 SMB (Server Message Block) サー・ Rendezvous 、 AppleTalk 、 SLP (Server Location ・コンピュータに置かれた BSD 設定ファイル 8 20 どのファイルのことてす。図 11 場所場所認 0 ディレクトツの使用方法 0 設定・セキィ 0 、仕上ツオープンディレクトリアシスタントサーバのアドしスとサプネットは、デイしクトリサービス - を使用するための設定方法に影響します。サーバで一時的なア、ドレスまたはサプネットを使用する場合は、使用できる設定オョンが制限されます。必要にじて、後でもう一度オープンディレクトリアシスタントを実し、ディレクトリの使用方法の設定を変更できます。 04 時的なアドしスとサプネットを使用しています @固定のアドレスとサプネットを使用していますサーバ serve.kyoto-wu. ac. jp 192.168.174.16 続けるには、右矢印をクリックします。図 12 ディレクトリ吏用方法テイしクトリの使用方法オープンアイレクトリアシスタントサーバでアイしクトリ情報を吸うには、 3 つの方法がありま、場所。既存のデイしクトリシステムからデイしクトリ情報を取得か、ほかのコンビュータに情報を提供するデイしクトリのホスとして使用するか、サーバ自体でのみ使用できる共有さ 0 、ディレクトリの使用方法 \ 0 設定セキューイ 0 社上げれなし一カルアイレクトリを使用することができます。サーバはまのことを行います 0 既存のシステムからディレクトリ情報を取得する @共有されないローカルディレクトリを使用する 0 かのコンピュータにアイレクトリ情報を提供する続けるには、右矢印をクリックします。 sistant の場合と同様、ウインドウの左側に乍業の手順か書かれています。このウインドウでは、サーバーに付けられた IP アドレスカ個定的なものか第勺なものかを答えます。ウインドウ内の説明にあるように、どちらの不頁の IP アドレスを使っているかによって、利用可能なサービスに若干の違いカ吽します。適切な IP アドレスの種別を尺すると、図 12 のウィンドウか現れます。このサーノヾーを NetInfo や Active Directory などの既存のシステムに参加させたいときは、一番上の、、既存のシステムからディレクトリ情報を取得する " を選びます。一方、このサーバー上て豸虫自のディレクトリメインを作成する場合は、下 2 つのうちのどちらかを選択します。このとき、そのディレクトリ・ドメインをほかのコンピュータにも利用させたければ一番下の、、はかのコンピュータにディレクトリ↑帯長を提供する " を、のサーバー以外では使わないのなら 2 番目の、、共有され UNIX MAGAZINE 2003.5

6. UNIX MAGAZINE 2003年5月号

特集・プログラミング入門いのて探索文字列の長さぶんだけ進めることができます。次の上交は文字 c で、これは一致しますから、その左の文字を比較することになります。ここでは不一致が発生します。このとき、不一致の E{ した文字である a は探索文字列の左側にあるため、探索文字列に含まれるもっとも右の a か現在注目している位置にくるように探索文字列を移動します。この例では、探索文字列が 1 文字ぶん右へ移動することになります。さらに探索文字列の末尾を上交すると、今度も不一一致が発生します。不一一致の発生した文字はやはり a ですが、今度は 2 文字ふ、ん探索文字列を移動することになります。すると、ちょうど目的の探索文等冽と -- ーー・致する部分になるため、 c 、 b 、 a と 3 文字を上交することて探索文字列か文字列に含まれていることが分かります。 BM 法のポイントは、文字列探索においては探索文字列に含まれない文字が多数存在するという点です。文字列の探索をおこなっていく際に、最初の文字を上交したときにそれか探索文字列に含まれないものであれは、一気に探索文字列ぶんを進めてしまうことができます。多くの場合に探索文字列ぶんを進めることができるのであれは、探索にかかる手間はれ + m となるのです。 BM 法で窈架索にかかる手間は、最悪の場合を考えるとアルゴリズムの引・算量としては力すくの探索 1 去と変わらない 0 ( れ m ) です。しかし、上記のように多くの場合にはれ + rn の手間で探索をおこなうことができます。一般的には、探索文字列カ張けれは長いほど BM 法による探索は高速になります。前述の KMP 法とくらべても、実際にはある程度の長さ ( 5 文字程度 ) 以 E の探索文字列であれは、 BM 法を用いるはうか効率がよいといわれています。それでは、この BM 法を実現するプログラムをみてみましよう。 KMP 法では、不一致を発見したときにそれが探索文字列の何文字目なのかにもとづいてどこから探索を再開したらよいかを示す next 配列を計算しました。今度は、どの文字が不一致文字となったかによってどれだけ進めてよいのかを表す skip 配列を準備することになります。さきほどの abc という探索文字列の場合、 a は 2 、 b は 1 、それ以外はすべて 3 となっている配列を準備します。 BM 法の実現 94 この配列を作成するのは簡単です。最初に配列自身を宣言する必要がありますが、今回は文字列として 8 ビットの文字すべてを考えましよう。そのため、配列のサイズとしては 256 ( 28 ) を用います。 #define ASIZE 256 int VOid skip [ASIZE] ; search—sub(char *s) i nt i nt 1en len; strlen(s) ; for (i = 0 ; i く ASIZE; i + + ) skip [i] 1e ; for (i = 0 ; i く 1en ー 1 ; skip[(int)s[i]] len 1 ます、配列のすべての要素を文字列の長さに設定します。つまり、ほとんどの場合には文字列の長さぶんを進めることができるわけです。このあと、探索文字列に使われている文字について特別な処理をおこないます。特別な処理といっても、しつはたいした処理ではありません。探索文字列の i 文字目にその文字があれは、、、探索文字列の長さー i ー 1 " を skip 配列に↑褓内すればよいのです。探索文字列に同し文字が 2 つあったときには、右側の文字に対して言算した値をイ褓内します。右側の文字と左側の文字とでは、右側の文字に対する値のほうか移動する量が少なくなります。左側の文字に対して引・算した値を採用すると、本当は - ーー - - 数するかもしれない場所を通り越して移動してしまう可能性があります。そのため、もっとも右にある文字に対して計算した値を skip 配列にオ褓内するようにします。このために、探索文字列の : 頁から、すべての文字について順番に値を計算し、 skip 配列にオ褓内しています。同じ文字が複数存在する場合、最初は左側にある文字に対する値かオ褓内されますが、あとから右側にある文字に対して引算した値かオ褓内されるため、すべての計算カ鮗了したあとは一 - 一番右にある文字に対する値かオ褓内されていることになります。 UNIX MAGAZINE 2003.5

7. UNIX MAGAZINE 2003年5月号

図 22 /opt を / にまとめるとき認ウインドウ編集 ( りオアション⑨ ktive Bcot. Ewiroment ・ - ris9.-202 ー地 T 〉 Size ( ) 物 t POint 0 10 4 ( 3 /var 21 9 2 /emrt/hoce 7 8192 /opt ufs 特集 SoIaris 9 の管理と運用いなけ川ま、ファイルのコピーになんらかの間題があったことになる。その場合は、いったん新しい環竟を削除し、ディスクスライスの割当て容量などを石忍したうえで作業を最初からやりなおす。パッチのインストール新たに作成した工竟に対してパッチやアップグレードをインストールする場合は、 luupgrade コマンドを使う ( または、ⅲコマンドの Upgrade メニューを j 尺 ) 。これ以降の作業は比較的単純なので、 luupgrade コマンドについて説明する。 luupgrade は、新しい環境を構 F4 新 F6 ロ田 AD E.% F2 F3 SLICE PRItn CÆtEL D 乢 E SPLIT M 正 CLR 町」 HELP CffJICE SAVE 成しているディスクスライスを作業用にマウントし、そこに対して所定のコマンドを実行する働きをする。パッチのドキュメントには、、新しい竟を有効に ( 図 23 ) 。なお、適用や OS のアップグレードなどでは、その後におこなする際におこなうファイル上交などのために、使用中のデう同期処理のためのデータベースを更新しておく必要があイスク容量に対して約 30 % 増しのスライスサイズが必要 " る。したがって、新しい竟のファイルをいきなり操作すと書かれている。るわけにはいかない。 format コマンドを終了すると、ⅲコマンドの画面に新しい環竟 0 ンヾッチを適用するには、次のようにする。戻る。次は、システムファイルかオ褓内されているファイルシス luupgrade -t —n 環境名 -s ノヾッチファイノレのノヾスパッチ名テムを新しい竟のどのディスクスライスに置くかを指定する。 / にカーソルを合わせて F2 CHOICE を押すと、未、パッチファイルのパス " は、糸寸パスで指定しないと工使用のディスクスライスか表示されるので、 / ファイルシラーになる。複数のパッチを指定する場合は、パッチ名をステムを置きたいディスクスライスを〕尺する ( 図 24 ) 。空白で区切って列挙す川まよい。同様に、 / var ファイルシステムを置くディスクスライ -t オプションによってパッチの適用を指定された luup- スも指定する ( 図 25 ) 。必要があれば、アプリケーション grade コマンドは、内部で patchadd コマンドを繰り返をインストールしたファイルシステムに対して新しいディし呼び出して新しい竟にパッチを適用していく ( 図 27 ) 。スクスライスを指定し、そのファイルシステムを、、切り替そのため、推奨パッチクラスタをインストールする場合でえて " 使うようにすることもできる。も、付属の install-cluster スクリプトは使えない。さいこれで指定は完了である。すぐにファイルシステムのコわい、 luupgrade コマンドは指定された ) でパッチを適ピーをおこなうときは F3 SAVE を、あとでコピーする用していくので、推奨パッチに付属する patch-order ファときは F7 SCHEDULE を押す。後者を尺すると、 at イルをそのまま、、パッチリスト " として使用すれはよい。コマンドを用いてコピー竹璞を実行する時刻の入力を求め適用済みのパッチや、そのシステムに不要なパッチが含られる。どちらの場合も、ファイルのコピーと上交に必要まれていた場合は、推奨パッチクラスタの install-cluster なデータベースを作成するためにかなりの日判肋ゞかかる。よりも詳しいエラーメッセージか表示さそのパッチのコピー作業カ鮗了すると再度ⅲコマンドの画面に戻る適用はスキップされる。ので、 Exit お尺してプログラムを終了する。 lustatus アップグレードコマンドでファイルのコピー状態を石忍したら ( 図 26 。 lu ーを使ってもよい ) 、新しい環コマンドの Status メニュ Solaris 8 からは、機能強化された OS が、、アップデー境の変更イ乍業に進む。ト・リリース " と呼ばれるかたちでリリースされるようになった。 SoIaris9 でも、約 3 カ月に 1 回の割合でアップ新しい工韆竟の CompIete ステータスが、 yes" になって 0 : 工ミュレータヘルプ c0t0d0s0 c0t2d0sl c 此 0 /opt 1 ærged /. PI mnfim? (), 司 : c % 1 c 0dCs7 Size(t'ß) 聞 t P /var / expo れ月に / 叩し 3 51 UNIX MAGAZINE 2003.5

8. UNIX MAGAZINE 2003年5月号

NO 引 CE 図 14 言聢終了と再起動仕上げオープンデイしクトリアシスタントによって、サーバでのアイし 0 なうこ、トリの使用方法が正常に設定されました。朝場所ディレクトリの使用方法新し、設定を適用するために、サーバを再起動してください。 0 設定 0 仕上図 13 パスワード・サーパーの設定オープンディレクトリアシスタントセキュリティアイレクトリの使用方法と同様に、サーパからバスワードおよ認証情報にアクセスするには、」っの一般的な方法がありまほかのシステムから情報を取得するか、ほかのシステムに情報を提供するか、ユーザしコードの一部として情報をローカルに存およびアクセスすることができます。オープンディレクトリアシスタント ' ー 000 もなうこ、や場所ディレクドの使用方法セキィ 0 仕上げ , パスワー ; ドおよび認証情報は次のように様作されます 0 ほ々、のシステムから取得する 0 ほ小のシステムに提供する @子」ザしコードとしてローカルに保存およびアクセスする続けるには、右矢印をクリックします。ないローカルディレクトリを使用する " を選びます。次は、、、パスワード・サーバー " に関する設定です ( 図 13 ) 。パスワード・サーーとは、ユーサーのパスワードを一元管理するサーバーのことで、 MD5 や SHA-I などによるユーザー認証をおこないます。 ( 亟」 ) 色三壅の一すでに別のパスワード・サーバーがあり、このサーノヾーでのユーサー認証もそこに統合するときは一番上のいて説明します。このような設定の変更には、管理コン、、ほかのシステムから取得する " を、このサーバーで新たピューター E で Server Settings や Workgroup Man- にパスワード・サーバーを起動する場合は、、ほかのシス ager を利用します。テムに提供する " を、パスワード・サーバーを使わない server Settings では各種サーピスの開始やイ亭止、詳ときは、、ユーサレコードとしてローカルに保存およびア細なオプション設定などが、 Workgroup Manager でクセスする " を選びます。はアカウントやグルーフ。の」助日や削除、変更、ファイルパスワード・サーバーを利用するように Open Direc- 共有のための共有ポイントの成疋やパーミ、、ノンヨンク ) 言殳 tory を設定すると、ディレクトリ・ドメインにはパス定などがおこなえます。ワードではなく、パスワード・サーバーによって割り当 server Settings や Workgroup Manager など、稼てられた ID が保存されます。図 13 の一番下の項目を動中の Mac OS X Server に接続して操作するアプリ選んだ場合だけ、パスワードはディレクトリ・ドメインケーションを起動けると、図 15 のようなウインドウがに直接保存されます。表示さ接続先サーバー名とユーザー名、パスワード以 E の設定力鮗了すると、さきほどと同様に、 Open の入力を求められます。もちろん、こでそのサーバー Directory の設定内容をテキストファイルとして保存すの管理権限をもつューサー名とパスワードを正しく入力るためのウインドウが表示されます。これを終えると、しなければ、設定変更などはできません。図 14 のように再起動を促されます。たとえば、 Server Settings を利用した場合、一信己の正常に再起動できれば、初期設定はひとます終了でューサー認証に成功すると図 16 のようなウインドウが表示されます。これは、 Mac OS X Server か驃準で提す。供するサーピスをアイコンで表示し、目的別にタブに分けたものです。ここでサーピスを表すアイコンをクリックすると、田な設定をおこなうためのウインドウか現れるイ督みになっています。すでに動いているサービスサーバーのネノ期匿がすんだところで、、、ファイル共に関しては、アイコンの右下に小さし長のマークカ咐有 " を例に、設定終了後にサーピスを起動ける方法につ UNIX MAGAZINE 2003.5 図 15 、 vorkgroup Manager てサーパーに接続ワークグルーブマネージャの接読アドしス : xserve. kyoto—wu ・ ac.jp ユーザ名 : miyasita バスワード : コキーチェーンに追加する 0 0 0 サーバーの設定変更 21

9. UNIX MAGAZINE 2003年5月号

特集・プログラミング入門殞則のループでは文字列全体に対してルーフすると述べましたが、実際には文字列の長さから探索文字列の長さを引いたぶんまでをループしています。う可立置がこれよりも後ろになると、探索文字列の長さぶんの文字か残っていないため、この部分には探索文字列カ唸まれないことか明らかだからです。もちろん、文字列の長さすべてについて探索を実行してもかまいませんが、ありえない場合を幇餘することで無駄な処理をおこなわないようにしています。それでは、このアルゴリズムの計算量を考えてみましょう。、、最悪の場合 " は、すべての位置から探索文字列の長さぶん上交をおこなう場合です。ただし、、、すべての位置から " といってもれではありません。末尾の rn に満たない部分は調べないので、れ一 rn 十 1 通りあることになります。そして、探索文字列の長さは m ですから、 rn(n ー m 十 1 ) 回程度の上師交が必要になります。通常、文字列の探索をおこなう場合にはれにくらべて m は十分小さいと考えてよいので、けっきよく 0 ( れ m ) となります。この最悪の場合となるような入力は、探索文字列とつねに一致しつつ、最後の文字でかならず異なってしまうという場合です。つまり、文字列は単一の文字か連続したものであり、探索文字列としては単一の文字カ里続し、その後ろに別の文字が付いたものが与えられた場合になります。たとえば、文字列 : 00000000000000000000000000000000000 探索文字列 : 00001 などと指定された場合か最悪の入力であり、その手間は上て言算したような値になります。さきはどのプログラムは、アルゴリズムをそのままプログラムに変換したものなので、すこし工夫すればアルゴリズムを変えすにプログラムを高速化することができます。最悪の入力を考えると、内側のループを毎回佃度も実行することはありますが、はとんどの場合には麪頁の文字の比較のみで一致しないことか判明すると思います。そこで、探索文字列の地頁文字をあらかしめ取り出しておいて、その文字だけは特別に上交をおこない、それか等しいときに限って探索文字列の 2 文字目以降をヾるというガ去が使えます。また、線幵架索を高速化するために使われる番兵の手法こでも利用できます。たとえば、文字列の後ろに探は、 UNIX MAGAZIN E 2003.5 索文字列を連結しておけは、探索はかならすそこで成功するわけですから、文字列の長さを調べる必要はなくなります。逆に、探索文字列の後ろにどの文字とも一致しない文字 ( 文字列に出現しない文字 ) を加え、文字列と探索文字列との比較がかならずその文字で失敗するようにしておくこともできます。この場合には、上交が失敗したときにそれまでに成功していた上交の回数か、探索が失敗したときに調べていた探索文字列内の文字を確認することで、探索文字列のすべてが含まれているかどうかカ吩かります。ただし、実際にプログラムを作成してみたところ、番兵として末尾に探索文字列を追加するガ去を用いたバージョンでは、それほど高速化されませんでした。というのも、文字列の末尾に新たに文字を追加しなければならないので、末尾をみつけるために ) 巨頁から順に 1 文字すっチェックする必要があるからです。この作業にかかる手間が番兵を利用することで省ける手間とくらべて小さくないため、さはど高速化にはつながらなかったわけです。文字列の末尾がすぐに分かるような場合には有効なのですが、そうでない場合には注意して用いる必要があります。また、無理に 2 重ループを作らなくても、ループの内部でおこなう更新処理を工夫すれば、 1 重のループ構造とす while (t Ci] ! = ) \ 0 , ) { int i , j ; search(char *t , char *s) int ることもできます。 if (t [i] if (s[j] } else { return ー 1 ; , \ 0 ' ) return i ただし、ループが 1 重になったからといって、計算量も 0 ( れ rn ) からたとえは〇 ( れ ) に下がるわけではありません。あくまでもループのまわし方を変えただけであって、最悪の場合に 0 ( れ m ) の手間がかかるのは同しです。 89

10. UNIX MAGAZINE 2003年5月号

図 10 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1056 1057 1058 1051 1052 1053 1054 1055 連載 / IPv6 の実装ー⑩ IPv4/IPv6 以外のアドレス・ファミリーの場合のタ里 default : family) ) ; "unknown address family=%d. \ " ipseclog( (LOG—DEBUG, "key-allocsa: continue ; goto found ; break; sizeof(sin) ; SI Ⅱ . Sin_len bcopy(dst , &sin. sin—addr, sizeof(sin. sin—addr)) ; if (key—sockaddrcmp ( (struct sockaddr*)&sin, (struct sockaddr * ) &sav—> sah—>saidx. dst , 0 ) ! = 0 ) continue ; 芝芋点では、 IPv4 と IPv6 以外のアドレス・ファミリーの SAD 工ントリ検索には対応していません ( 図 10 ) 。 1077 splx(s) ; 1078 return NULL ; 検索条「牛に適合する SAD 工ントリが発見できなかった場合、 1080 1081 1082 1086 1087 1 , 078 行目で NULL を返します。 found : splx(s) ; sav—>refcnt 十十 ; SAD 工ントリはアドレス・ファミリーに依存しないため、 IPv4 アドレスをもつ場合もあれは、 IPv6 アドレスをもつ場合もあります。 key-allocsa() の呼出し時に検索条件としてアドレス・ファミリー (family) を指定しているので、確認中の SAD 工ントリカ甘旨定されたアドレス・ファミリーの終点アドレスをもっているかを調べます。 key-allocsa() で IPv4 アドレス・ファミリーの検索か指定されている場合は、確認中の SAD 工ントリが IPv4 アドレスをもっていると仮定して上交します。 keysock- addrcmp() はアドレス・ファミリーに応して 2 つのアドレスを上交する関数です。 1059 case AF_INET6 : 条件に適合する SAD 工ントリがみつかったら、 SAD 工ントリの参照カウンタ (sav->refcnt) を増やし、発見したエントリを返します。 SAD 工ントリは参照カウンタて管理されるため、 key- allocsa() で検索した SAD 工ントリが不要になったら keyfreesav() て解放しなけれはなりません。 1117 void 1118 key—freesav(sav) 1119 1120 { struct secasvar 1060 1061 1062 1063 if (key-sockaddrcmp ( (struct sockaddr * ) dst , (struct sockaddr *)&sav—> sah—>saidx . dst, 0 ) ! = 0 ) continue ; break; keyffreesav() は解放する SAD 工ントリへのポインタを引数にとります。 1 , 059 ~ 1 , 063 行目は IPv6 の SAD 工ントリの検索カ甘旨定されている場合のアドレス上交です。 IPv4 の場合はいったん sockaddr-in 構造体に上交対象となるアドレスをコピーしており、 IPv6 の場合 ( 鹵耐妾 key-sockaddr- cmp() を呼び出しています。これは旧いコードの名残で、現在は IPv4 でも単純に keysockaddrcmp() を呼び出すだけで動胙します。 UNIX MAGAZINE 2003.5 1125 1130 1131 1133 1134 } sav—>refcnt— if (sav—>refcnt = の key—delsav(sav) ; return ; 1 , 125 行目で参照カウンタ (sav->refcnt) を減らします。カウンタが 0 になった場合、その SAD 工ントリは誰からも利用されていないことになるため、 key-delsav で SAD 工ントリを削除します。 75