連載 / UN Ⅸの道具箱ーの 受け付けるインターフェイスやポートの指定 表 5 sshd-config での寺間オ諚方法 時間 表記 算機が複数のインターフェイスをもっていたり、ェ れ秒 ハまたは、れ イリアスの機能などによって複数の IP アドレスをもって れ分 nm または nM nh または nH いる場合、特定のアドレスのみ SSH の接続を受け付けた nd または nD れ日 いことがあります。このような場合、 ListenAddress れ週 nw またはれ、 V や Port というパラメータで接続を受け付けるアドレス ・ HostKey を指定することができます。それぞれ次のようにホスト ホスト認証に使われるホスト秘密鍵の場所を指定しま 名 ()P アドレス ) やポート番号を指定します。 ListenAd- す。デフォルトでは、 SSHI の鍵が /etc/ssh/ssh-host dress では : で区切ってポート番号も同時に指定できま -key で、 SSH2 の建が /etc/ssh/ssh-host-rsa-key で す。 IPv6 アドレスとポート番号を同時に指定する場合は す。 アドレスを、、「と、、 ] " で囲みます。 IPv6 アドレスのみを コマンドライン・オプションの一 h オフションてオ旨定す 指定する場合は [ ] は不要です。 ることもできます。ホスト秘靆は、スーパーユーザー ListenAddress ホスト名 以外がアクセス可能になっていてはいけません。 ListenAddress IPv4 アドレス : ポ ート番号 ListenAddress IPv6 アドレス ] : ホ ート番号 ・ AuthorizedKeyFiIe Port 22 ユーサー認証に使われる公開鍵をオ褓内するファイルで、 なお、一度に複数のアドレスやポートを指定すること 絶対パスかホーム・ディレクトリからの相対パスで指 はできません。複数のアドレスやポートで接続を受け付 定します。デフォルトでは . sshauthorized-keys です。 ける場合には、受け付けるアドレスごとに 1 行すっ指定 引数内では以下の文字か特別な意味をもちます。 する必要があります。デフォルトでは、 ListenAddress % % : 、、 % " に置換される。 は、、 0.0.0.0 " ( すべてのアドレスで受け付ける ) に、 port %h : ューサーのホーム・ディレクトリを表す。 は、、 22 " になっています。 %u : ューザー名を表す。 sftp の利用 ・ KeyRegenerationIntervaI SSH2 では、 ftp に SSH による暗号化機能を追加した SSHI で、サーバー鍵を再生成する時間を指定します。 sftp というファイル転送コマンドか利用できますが、サー この鍵はメモリ上にのみ置かれ、ファイルには保存さ バー側で使えるように設定しなけれはなりません。そのた れません。 0 を指定すると一度も再生成されません。デ めのパラメータが Subsystem です。引数にはサプシス フォルトの値は 3 , 600 秒です。鍵の再生成は、計算機 テムの名前 (sftp) と、その実行コマンドの場所を指定し への侵入によって盗聴されたセッションを解読された ます。デフォルトでは何も指定されませんが、 sftp を利用 り、鍵を盜まれないようにするためにおこなわれます。 したい場合は次のように書くとよいでしよう (sftp-server なお、日判日窈旨定ガ去は表 5 のようになっています。組 の場所はインストールエ竟に合わせてください ) 。 み合わせて使うこともでき、たとえば 1 日判り 30 分を指 定するには、、 1h30m " や、、 90m " などと書きます。 Subsystem sftp ・ ServerKeyBits その他のパラメータ SSHI で用いるサーバー鍵のビット数を指定します。最 小値は、、 512 " で、デフォルトは、、 768 " です。大きい値 sshd-config では、このはかにもさまざまなパラメータ を指定するほど安全になりますが、通信の暗号イ復号 を設定できます。 にかかる日判りも長くなります。 各嶷に関するもの 接糸寺間制御に関するもの 公開鍵の場所や共通暗号に用いる鍵に関するパラメー タです。 クライアントの生忍や認時の待ち時間などに関す 一三卩 /usr/libexec/sftp—server UNIX MAGAZINE 2003.9 97

特集・プログラミング入門 よいので、 drr 配列のその値の添字の場所にコピーしてお きます。これをすべてのカードに対しておこなうだけで す。最後に、 drr 配列から crr 配列にコピーしなおすこ とで、 crr 配列自身か整列された状態になるようにしてい ます。 あまりに簡単すぎて拍子抜けしたかもしれませんが、ち ゃんと順番どおりになるのですから、これも立派な整列法 の 1 つです。なお、この条件であれば、 0 ; i く NCARD; i + + ) fo て (i crr [i] としても正しい状態のものか得られます。しかし、これは 整列しているわけではありません。レコードのサイズが大 きく、一部の値がキーとなっている場合を考えれは、たん に数値を並べるだけでよいというものではないことが分か るでしよう。 トランプを例に説明しましたが、もちろんこのガ去はト ランプを並べるとき以外にも使えます。とくに、キーの値 が一一 - ・定範囲内にあることが分かっている場合は有効です。 たとえば、あるクラスで実施した試験の結果を出席番号順 に並べ替えるといったときにも使えます。この場合、試験 がカードで、出席番号がカードに書かれた数字に対応する わけです。 さて、この方法にかかる手間を考えてみましよう。 for ループが 2 つありますか : どちらも要素数、すなわちれ回 ループしています。つまり、このガ去であれは 0 ( れ ) の手 間で整列が可能ということになります。上記の七並べの例 からも分かるとおり、キーの値の示回川内にびっしりと 1 つ すつの要素がある場合には ( 実際には、たかだか 1 つの要 素がある場合 ) 、通常の整列法の限界を超えるような整列 が可能だということが分かります。 この制限をすこし緩めることもできます。どのキーの値 に対しても要素がたかだか 1 っという制限を外し、それぞ れのキーにいくつの要素があってもかまわないことにしま しよう。つまり、キーの値が NI までであり、要素数が N 個だとすると、、 > NI のケースにも対応するのです。 この場合には、前記の方法をそのまま適用するわけには いきません。こで、整列法の見方を変えてみましよう。 分配計数法 116 図 1 分酉十去を用いたプログラム VOid sort (void) int i , j ; for (j 0 ; j く M; for (i 0 ; i く for (j 1 ; j く M; m Cj ] + = m [j ー 1 ] ; for (i = N 1 ; brr[m[arr[i]]- for (i 0 ; i く 十十 ) i > = 0 ; arr[i] ; UNIX MAGAZINE 2003.9 回までと同様ですが、キーの値は M までに制限されてお ムを作ってみましよう ( 図 1 ) 。配列などの前提条負 : は前 counting) などと呼ばれます。この手法を用いてプログラ このようなアルゴリズムは、分配引嚶去 (distribution いことになります。 目的のレコードは 40 番目から 49 番目の要素とすればよ り、 150 というキーをもつレコードが 10 個あるのなら、 る場合、これよりも小さいキーをもつレコードが 40 個あ とするわけです。 150 というキーをもつレコードに注目す あるかを数え、そこからレコードを各内する ・あるキーの値よりも小さいキーをもつレコードがいくつ 数ある場合も簡単に拡張できます。つまり、 このような見方をすれは、あるキーをもつレコードか複 は 50 番目の要素とすれはよいことカ吩かります。 から 149 までの 50 個があります。そこで、このレコード ーをもつレコードよりも小さいキーをもつレコードは 100 と読み替えることができます。たとえは、、 150 というキ あるかを数え、そこにレコードをイ褓内する ・あるキーの値よりも小さいキーをもつレコードがいくつ れは、 100 を引いた位置に↑内しなけれはならないからです。 ーの値の範囲が 100 から 200 であれは、キーの値から ことを書きましたが、これは正確ではありません。もしキ さきはど、、キーの値と同じ場所にオ褓内する " という意味の brr[i] ; arr[i]

So な トラブいシューティング たとえば、 SystemV IPC のメッセージ通信では、シス テム全体での弭乂り待ちのメッセージ数がカーネル・パラ メータ MSGTQL で規定されている。このため、停止し ているアプリケーション自体に間題はなくても、はかのア プリケーションとの関係でこの制限に引っかかることがあ る。その場合、 msgsnd() でメッセージを送伺すると、停 止状態になるか工ラーを返して復帰するような仕様となっ ている。 ハングアップ 動作停止状態である。可能陸としては、排他制御におけ るデッドロック、アプリケーションがアクセス中のデバイ スの不具合などか原因と考えられる。 アプリケーションが同しルーチンをすっと実行し続けて ループ いる状態である。たいていは、 おこなう部分に間題がある。 異常終了 フログラムにおいて岐を アフリケーションのコーディングミスや OS のバ久 実行・エ韆竟の不通切な設定などにより、突然終了してしまっ た状態である。多くの場合、メッセージが出力されたり、 core ファイルが生成される。 メッセージの出力 アフリケーション自体は動いているが、メッセージが 出力されている状態である。アプリケーションからの意図 的なテンヾックフ。リント以外に、アプリケーションがアクセ ス中のシステムリソースからのメッセージである可能匪も ある。 / くフォーマンス氏下 システム全体ではなく、アプリケーション自体のパフ ォーマンスか低ードしている状態である。さまざまな原因が 考えられるため、多面的な調査が必要になる。 不具合の調査方法 アプリケーションの状態を調査するコマンドはたくさん あるが、以下では代表的なものをいくつか選んて概要を紹 介する。言岩田については、各コマンドのオンライン・マニュ アルなどを参照してはしい。 UNIX MAGAZINE 2003.9 proc tOOl Solaris 2.5 から提供されている。 OS のノヾージョンカを E がるごとに利用できるコマンドやオフションか増えている ので、利用する則に、、 man proc" として確認しておこう。 Solaris 8 からは、実行中のプロセスの清報だけでなく、 core ファイルの情報も抽出できるようになった。 Solaris 7 までは /usr/proc/bin の下に各コマンドが 置かれていたが、 SoIaris 8 以降は /usr/bin にオ褓内され ている。 トラブル・シューティングに使うおもなコマンドとして は、以下のものがある。 pstack : 実行した日点でプロセスか実行中の関数、シス テムコールの長か取得できる。フログラムが停止状態 にある場合に有効なコマンドである。 複数回実行することで、停止状態にあるのか、実行状態 にあるのかカ喇断できる。 pfiles : アフリケーションがどんなファイルをオーフンし ているかを表小する。 Solaris8 からは、ソケットの利 用しているポート番号か表示されるようになり、どのフ ロセスがどのネットワーク・ホートを使っているのかを 簡単に調査できるようになった。 psig : シグナルに対し、どのようなアクションをとるか が一一覧表示される。実行中のアプリケーションよりも、 core ファイルを対象にして利用されることが多い。 pldd . 実行中のアフリケーションがリンクしている共有 オプジェクトを表示する。 pmap : アフリケーションか利用しているメモリ資源に関 する情報を出力する。ー x オフション付きで実行すると、 そのアプリケーションがどのくらいの実メモリを使って いるかか不忍できる ( 図 2 ) 。 truss は、アプリケーションの実行状況をシステムコー ル・レベルで j 亦するコマンドである。障害の再現が・可能 な環境でこのコマンドを実行すれは、原因の特定に役立つ 多くの情報を取得することができる。 上刻青報として、うまく測胙する状態での truss の結果 があるとよい。 以下は、 truss を実行・する際によく利用するオフション である。 179

連載 / IJN Ⅸの道具箱ーの 図 2 PuTTY での X11 車医の設定 カテゴリ 0 : ドセッション ロング 三端末 キーボード ベル 、ウインドウ 拆る舞い 変換 色 Proxy Telnet ー Rlog in SSH トンネル ハグ PuTTY 設定 接統 三 SH トンネリングを管理するオプション 滝 1 フォワディング マ凶エウ理三ディンクを有川第る X ディスプレイの場所 loca 旧 os 印 ポートフォワーディング 「ローカルポートは他のホストカちの接続を受け入れる 0 「リモートボートも同様 (SSH v2 のみ ) ⑧ 新し、フォワードされるポートを追加 フォワードされたポート 表 1 公開鍵のオプション 書式 from= 7 れ一〃 s 广 comrnand== ” C07 〃 7 れ .0 れ d ” environment== ” NAME no-port-fowrarding no-X11-forwarding no-agent-forwarding no-pty = : ゼ a / れ e ” ・ from - 。フシ ' ョン permitopen= ”ん ost れのれ e 挈 0 ' 説明 クライアントのホストチ ェック 自重加勺にコマンド実行・ 工羅竟変数設定 ポートフォワードの禁止 X11 中幻の禁止 認証工ージェント中幻の 端末を割り当てない ポートフォワードの限定 をロー加い ) 0 リモート ( 印 クライアントの内容が表示されます。 この機能を利用するには、 ssh (slogin) の -X オフショ ンを使います。このオプションを付けてログインすると、 図 1 の、、暙号化 " て示した通信路が設定さオ L 、 XI い幻医の 準備か整います。書式は次のとおりです。 ssh —X remotehost こうしてログインしたシェルから kterm や Emacs な ど、 X ウインドウ・システムのプログラムを実行すると、 ローカルのディスプレイに表示されます。 PuTTY の場合は、疋の、、接続 " →、、 SSH" →、、 ネル " を表示し、、、 X11 フォワーディングを有効にする " にチェックを入れます ( 図 2 ) 。他の設定はとくに変史し なくてもかまいませんが、あらかじめ ASTEC-X などの X サーバーを起動しておく必要があります。ログイン後に kterm や Emacs を夫行すれは、ローカルの X サーバー で表示することができます ( 図 3 ) 。 公開鍵のオプション 7 月号では説明しませんでしたが、サーバー側に公開鍵 を登録する際に、表 1 に示すオプションを付けることがで きます。オプションは登録された鍵のう頁に追加し、複数 ある場合は、、 , " ( カンマ ) で区切ります。追加する際には、 Emacs やⅵなどのエデイタで手イ乍業て編集します。 それぞれの意床は次のようになっています。 90 このオフションは万が一を盗まれた場合に備えて、認 証できるホストを限定する際に使用します。ホスト名 や IP アドレスを指定し、ワイルドカードとして * と ? が使えます。 , で区切って複旨定すること もできます。なお、 : 麪頁に、、 ! " を付けると否定のパター ンとして扱わオ L 、そのホスト名からはこの公開鍵による 証はできなくなります。 川い ・ command 材 - ・フシ・ヨン 公開鍵にこのオフションカ咐いていると、認証が成功 したあと、自動的にそのコマンドが実行されます。コ マンドラインに ( ダブルクオート ) を入れたい場合 は、、 \ ' ' " とします。このオプションはリモート ・ノヾック アップなど、特定のイ乍業だけをしたいときに有効です。 ・ environment ・・フシ - ョン 訒証が成功したあと、環境変数に追加する文字列を指 山じ、 定できます。デフォルトではこのオプションは使えな いようになっているため、使用するには sshd の設定 で PermitUserEnvironment を yes" にしなけ れはなりません。 ・ no-port-forwarding 、 n0-Xl l-forwarding オフショ ン それぞれ、この鍵で言正した場合にポートフォワードや X11 軏医ができなくなります。ー L やー X オフション付 きでログインし、中幻医を試みてもエラーになります。 ・ no-agent-forwarding オフション 証工ージェントの転送か禁止されます。 山い ・ no-pty オフション 端末を割り当てなくなります。 command オフション と組み合わせて、特定のコマンドだけを実行させたい場 UNIX MAGAZINE 2003.9

連載 / UN Ⅸの道具箱ーの です。日旨する場合は、、 yes" 、しない場合は、、 n 。 " を指 定します。デフォルトは yes です。 ・ LoginG ・ raceTime ログイン時の猶了・嗤間を指定します。ューザーがここで 指定された時間内にログインできないと、 sshd はその 接続を切ります。デフォルト値は、、 120 " で、 0 にす ると制限時間はなくなります。 ・ PrintLastLog ューサーがログインしたとき、前回ログインした日付と 時刻を表示するかどうかを指定します。表示する場合 は、、 yes" 、しない場合は、、 no " です。デフォルトでは yes になっています。 ・ PrintMotd ューザーがログインしたとき、 /etc/motd ファイルの 内容を表示するかどうかを指定します。表示する場合 は、、 yes" 、しない場合は、、 n 。 " です。デフォルトでは yes になっています。 ・ StrictIV'Iodes ューサーがログインする前に、ユーサーの公開鍵や秘密 鍵などのファイルやホーム・ディレクトリのパーミッ ションをチェックするかどうかを指定します。チェッ クする場合は、、 yes" 、しないなら、、 n 。 " で、デフォルト では yes になっています。 このパラメータを yes にしている場合、 $HOME/. ssh ディレクトリや公開鍵を登録しているファイルが自分 以外も書込みできるようになっていると、公開鍵によ る認証をおこなわす、 UNIX パスワードによる認証に なってしまいます ( 図 12 ) 。 ・ UseLogin 対話的な認証の際に login(l) プログラムを用いるかど うかを指定します。これが有効 (yes) になっていると X11Forwarding による X クライアントの中幻医はお こなわれません。デフォルトは、、 n 。 " です。 暗号アルゴリズムに関するもの ・ Ciphers SSH2 で許可する暗号化アルゴリズムを指定します。複 旨定する場合はカンマで区切ります。デフォルトで は、、、 aes128-cbc,3des-cbc blowfish-cbc cast128-c bc,arcfour,aes192-cbc,aes256-cbc" です。 るパラメータです。 ・ ClientAIiveInterval sshd はネットワークの不調などによりクライアントが 切断されていないかどうかを石忍するため、一定日判ご とロ芯答要求を送ることができます。このパラメータは 佃ごとに応答要求を出すかを指定します。デフォル トは 0 で、応答要求を送りません。 SSH2 のみで有 効です。 ・ ClientAliveCountMax 上記の CIientAIiveInterval で孑旨定された応答要求メ ッセージに何回反応がなければセッションを終了する かを指定します。たとえば、 C1ientA1iveInterva1 C1ientA1iveCountMax と設定していた場合、 15 秒とに応答要求を送り、 4 回反応がなけれはセッションは切断されます。つまり、 応答要求に反応できないクライアントはおよそ 1 分後 に切断されます。 ClientAliveCountMax のデフォル ト値は 3 です。 ・ KeepAlive 上記 2 っとは別に、 TCP の keepalive メッセージを 送るかどうかの指定です。デフォルトは、、 yes' ( 送る ) になっています。 ・ MaxStartups 響証されていない段階の接続 ( 認証待ちの接続 ) をいく ロ・い っ受け付けるかを指定します。デフォルト値は、、 10 " で す。 ログイン時の辰舞いに関するもの ューザーがログインするときのサーバーの振舞いに関す るパラメータです。 このオフションで指定したファイルがユーサー認証の前 に表示されます。ューザー認証の前に警告メッセージな どのバナーを表示したいような場合に使用します。 デフォルトではノサーは表示されす ( 何も指定されてい ません ) 、 SSH2 でしか使用できません。 ・ compresslon SSH の通信内容を ) 疇宿して送受信するかどうかの設定 5 4 ご 98 UNIX MAGAZINE 2003.9

特集・プログラミング入門 クイックソートでおこなったのと同様、範囲の下限と上 限からそれぞれ交換すべきレコードを探し、実際に交換が 必要な場合にのみレコードを入れ替えるという処理をおこ なっています。入れ替えるものがあるあいだは f 。 r の無限 ループを繰り返しますが、入れ替えるものがなくなった (i が j 以 . E になった ) らループを抜けます。なお、図 9 のプ ログラムでは値の入替えをおこなっているため、整列に安 定性はありません ( 同し基数交去を使ったプログラムで も、図 8 には安定があります ) 。 ループの直後の if 文では、すべてのレコードのキーの ピットか立っていなかったときの処理をおこないます。 の場合、 for ループのなかの最初の while ループで i は j と等しくなります。つまり、次の while ループはまったく 実行されすに for の無限ループを終了します。この場合、 再帰呼出しをするときに low から j ー 1 までとすると、最 後のデータを取りこは、してしまいます。これを避けるため に、すべてのレコードについてヒ、ツトが立っていなかった 場合の処理をおこなっています。 分割できたら、それぞれのグループに対して再帰的に sortsub 関数を呼び出します。分割の時点で、ビットが 0 のレコードを前に、ビットが 1 のレコードを後ろに配置 しているため、再帰関数から返ってきたときには全体か整 列した状態になっています。ですから、最後に特別な処理 は必要ありません。 このプログラムをさらに高速化したけれは、クイック ソートで用いたテクニックをほばそのまま使うことができ ます。たとえは、 6 月号て紹介した、ある程度まで分割し たら挿 . ん尺法などを利用する方法を適用してもいいでし よう。あるいは、スタックを自分で管理するようにして、 再帰呼出しを区しに変更すれはさらに高速化できます。 基数交換法の手間 この当」法も、クイックソートと同しく分割統治アルゴ リズムを使っています。今回の場合には、再帰を 1 関匯 むたびに 10 進数であれは・ 10 イ固、ビットごとに処理する 場合は 2 個の部分間題に分けていきます。 勺的な場合を考えてみましよう。適度にはらけた入力 が与えられた場合、問題を分けれはほは均等に分割できる と考えられます。けっきよく、再界呼出しの系列によって 作られるヨ冓造の高さは、クイックソートのときと同様に UNIX MAGAZINE 2003.9 1 。 g れに比例するものになります。それぞれの呼出しにお いて、調べなけれはならない範囲すべてを処理するので、 こちらがれに比例する手間になります。これらを合わせ ると、最終的には 0 ( れ log れ ) の手間がかかることが分か ります。 しかし、基数交去の手間はつねに 0 ( れ log れ ) とはか ぎりません。最悪の入力が与えられた場合を考えてみまし よう。この方法では、すべてのレコードのキーか 1 司し値に なっているのが最悪の場合です。 基数交去を実行するときには、すべてのレコードが同 ーのグループにう嶽頁されてしまうため、いつまでたっても 処理するレコード数は変わりません。しかし、このような 場合にいつまでも再帰か終らないかというとそうではあり ません。基数交換法では、 10 進数としてみれは桁数、ピッ トごとの処理ならばビット数が、再帰を 1 つ進めるたびに 減っていきます。したがって、いつかは調べるところがな くなり、残ったレコードのキーの値カしいとみなして処 理できるようになります。キーの値となりうる可能陸のあ る最大値を m とすると、再帰呼出しを 1 隹むたびに、 これが 10 分の 1 や 2 分の 1 に減っていきます。つまり、 logm に比例する回数を実行することになります。この場 合も、再 ) 帚呼出しを 1 止んだすべての呼出しで、すべ てのレコードを処理するのは変わりません。したがって、 けっきよく基数交換法の手間は 0 ( れ 1 。 gm ) であるとみ ることができます。通常、要素数にくらべてキーの最灯直 のはうがかなり大きいため、平均的な場合よりも多くの手 間カ功、かることになります。 こで、〇記法のことを思い出してください。 0 言去で 手間を考えるときには定数部分は無視し、変化する部分が 大きい値に変わったときにどういう景グ礬があるかを表現し ています。上で注目したの値は、間題カ鴃まれば入力 に左右されません。キーとして int 型の値を使うと決めれ は・、 int 型の値を表現するために使われるビット数は問題 ごとに変わることはなく、どんな入力が与えられても同じ 値です。つまり、 m は定数とみることができます。 m が 定数であれは log m も定数ですから、〇記法を正確に使う のなら、 0 ( れ 1 。 gm ) は 0 ( れ ) と変わらないことになりま す。たしかに、同しキーの値のレコードが 1 , 000 個の場 合と 10 , 000 個の場合をくらべると手間は 10 倍になるの で、〇 ( れ ) というのは間違いありません。ところが、、は勺 123

特集・プログラミング入門 図 10 直接基去による整列 (a) もとのデータ (b) 下 1 桁目で整列 (c) 下 2 桁目で整列 (d) 下 3 桁目で整列 02 ■ 0000000 ' ■ 0000 ー■ 000 = 00 ■■■ 00000 0 ■ 000000 ■ 0 ' 2 ■ 0000 000 的な入力であれば 0 ( れ log れ ) なのに、最悪の場合を考え ます。たとえは、実数値をキーに使って整列をおこない たい場合などは、基数交換法をうまく適用するのは困難で ると〇 ( れ ) になるというのは、何か間違っているのでしょ す。このようなときも、クイックソートであればとくに問 うか。 題なく使えます。基数交去を利用する場合は、キーの値 れにくらべて m か大きい場合、 logn と logm では明 に制限があることを憶えておきましよう。 らかに I 。 grn のほうが大きくなるので、納得できると思い ます。ところが、 0 記法で考えるのは、れカ限まて大き くなったときに手間がどう変わるかです。その場合には、 明らかに rn よりもれのほうが大きくなります。こうなっ 基数交撫去では上の桁から順に整列をおこなっていきま たとき、勺の場合の手間を求める言算力法を変えなけれ したが、これとは逆に、下の桁から順に処理する去もあ はならなかったのです。本当にれか大きくなったときに ります。これを、直接基委去 (straight radix sort) と呼 は、爿弩勺の場合の手間も〇 ( れ ) となります。 びます。この方法では、最初に一番下の桁を用いて整列処 こで、れか極限まて大きくなったときではなく、実用 理をおこないます。その結果を次の桁を使って整列し、さ 的な範囲での生能をみておきましよう。上交の対象とする らに上の桁を、というように桁を上げていきます。最終的 のは、やはりクイックソートです。入力が本当にランダム にできあがった列は、ちゃんと順番に並んでいます。 にケえられるのなら、基数交去のほうがクイックソート まるで手品のようですが、これも例を使ってみていくこ よりもほんのわすか高速に重川します。しかし、ランダム とにしましよう。図 10 ー a に示した、 1 , 000 未満の整数 10 さがそれほどでもなけ川ま、クイックソートのはうか高速 個を昇順に整列することにします。 です。また、キーの値の範囲にくらべてレコード数か圧倒 このようなデータの下 1 桁だけを使って整列をおこな 的に多い場合は、さきはどみたように基数交換法のはうが うと、データは図 10 ー b のように並べ替えられます。 有利です。しかし、そのような状況になるということは、 さらにこの処理を下 2 桁目、下 3 桁目と続けていくと、 キーの値の範囲が上交的狭いからだともいえます。もしそ データの並びは図 10-c—d のように変わっていきます。 うならば、基数交換法ではなく、う己言楼去やピンソート 最糸勺にできあがる並びは、正しく昇順になっているこ を考慮してもよいでしよう。 0 ( れ ) で整列ができるう圸、 とが分かります。 去やビンソートは、キーの値の範囲に比例する大きさの 下 1 桁を使って整列したときは、当り前ですが、下 1 記應領域を用意しなけ川まならないため、範囲があまり大 きい場合には適用できません。しかし、それほど大きくな 桁は昇順に並んでいます。次に下 2 桁目を使って整列し いのであれば、真っ先ロ尺してもよいと思います。 たとき、注目したいのは下 2 桁目が同し値となっている データです。たとえば - ド 2 桁目が 0 となっている先頭 2 間題によっては、基数交換法が〕尺できないこともあり 直接基数法 124 UNIX MAGAZINE 2003.9

連載 / IJN Ⅸの道具箱ーの 図 11 ポートフォワードの自加 Enter passphrase for key ' /home/local/hoehoe/ . ssh/id_rsa ' localhost% slogin —L 10110 : popehost : 110 remotehost We1come to FreeBSD! remotehost% ¯C ssh> —L 10080:webhost : 80 Forwarding port . remotehost% ←ここで、 ~ C " を入力 ←追加する転送を入力 1. コマンドライン・オフション 2. ユーサーの設疋ファイル 3. システム・全 f 本の成疋ファイノレ ューサーの成正ファイルは、デフォルトでは $HOME/ . ssh/config です。システム全体の正ファイルは、通常 は /usr/local/etc/ssh-config にインストールされます。 ただし、パッケージ・システムや OS と同時にインスト ールされた場合は場戸励なることがあります。同レヾラ メータがみつかったときは、最初にみつかった値か有効に -i 鍵ファイル名 こでは重要と思われるオプションのみを説明します。 ssh には多くのコマンドライン・オフションがあるため、 コマンドライン・オプショ なります。 ン 94 などで使用します。 指定します。前回紹介した 2 段階のポートフォワード を受け付けるようになっている場合、このオフションで いますが、リモートホストでそれ以外のポートで SSH 通常、 SSH は 22 番ポートで受け付けるようになって -p ポート番号 name " の形式て指定することもできます。 します。ホスト名を指定する際に、、 username@host- とリモートホストでログイン名が異なる場合などに指定 ログイン時のログイン名を指定します。ローカルホスト ← I ログイン名 で指定します。 が、それ以外の秘密鍵を用いる場合にこのオプション /. ssh/id-rsa や $HOME/. ssh/id-dsa が使われます なら $HOME/. ssh/identity が、 SSH2 なら $HOME 公開鍵による認証の際、秘密鍵はデフォルトでは SSHI X11 転送をするかどうかを指定します。転送を許可す る場合は一 X を、許可しない場合は一 x を指定します。 —C すべてのデータを圧縮して送受信します。ポートフォ ワードや X11 転送での通信も ) 宿されます。ー宿には gzip(l) が使われます。ネットワーク帯域カ田い場合に 有効でしよう。 —F 設定ファイル名 デフォルトのユーザー設定ファイル ($HOME/. ssh/ config) とは別の設定ファイルを使いたい場合に指定し ます。 —L localport :remotehost:remoteport 前回紹介したホートフォワードをおこないます。 local- port カゞ remotehost の remoteport に中ムさオ L 、 lo- calport にアクセスすると remotehost の remote- port に接続されます。 —R localport:remotehost:remoteport —L とは逆で、 remotehost の remoteport を local- host に中幻医します。 remotehost の remoteport にア クセスすると localport に接続されます。 -L がローカ ルからリモートへの転送だとすると、一 R はリモートか らローカルへの転送といえます。 おもなオフションとその使い方を表 3 にまとめます。設 定ファイルは通常はほとんど利用することがないため、 こでは説明を省略します。詳しくはオンライン・マニュア ルを参照してください。 sshd の設定 sshd の成疋ファイルは sshd-config で、通常は /usr/ local/etc/sshd-config にインストールされます。このフ UNIX MAGAZINE 2003.9

特集・プログラミング入門 作成しなおすと、 ・フログラムか簡単になる ・ビット演算を用いて高速に評価できる といった効果から、高速な処理が可能になります。 2 進数を利用する場合、桁でのう第リは 0 か 1 のいすれか になります。つまり、 2 つにう第リするわけです。したがっ て、渡されたレコードの集合を大きいもの ( 1 のクルーカ と小さいもの ( 0 のグルーフ ) の 2 つに分割し、それぞれ を再帰的に処理して整列させ、整列済みの 2 つの列を連結 することで全体の整列をおこなうという処理になります。 これだけをみると、クイックソートとほとんど同じ処理で す。唯一異なるのは、集合の分割の基準です。クイック ソートの場合は、あるレコードを担售とし、そのキーの値 よりも大きいか小さいかでう第リしていました。一方、今回 の手法では特定の柝仂ゞ 1 か 0 かで分割します。作成して みると分かりますが、クイックソートの場合とそっくりの プログラムになるはすです。 それでは、ビットごとに処理をおこなう基数交去のフ ログラムをみていくことにしましよう ( 図 9 ) 。 実際に呼び出される sort 関数は、補助関数の sortsub を呼び出すだけのものです。このとき引数に渡すのは、処 理しなけれはならない示観月の下限と上限、何ビット目の値 によって集合を分割するかという値です。今度のプログラ ムでは、下限と上限は範川の両端の値を指定するので注意 してください。 N 個の要素がある場合には 0 から N ー 1 までにオ褓内されているので、指定する値は 0 と N ー 1 で あり、 N ではありません。分割に使うビットの位置を指定 する値としては、キーが int 型であることを想定していま す。したがって、 int 型の値の最上位のビットを指定する ために sizeof (int) に 8 ( 1 バイトに含まれるビット数 ) を掛け、さらに 1 を引いた値を言 t 算しています。 1 を引い ているのは、ビットの位置は 0 から数えるため、引かな いとはみ出してしまうからです。 厳密にいえは、この値は正しくありません。 int 型の値 の最ーヒ位のビットは符号を表すために用いられています。 キーの値に負の数が含まれていると、それは正の数よりも 大きい値として処理されてしまいます。ただ、今回はアル ゴリズムの動作をみるために作ったものなので、このあた りはご容赦ください。 1 , 122 if ( 10 > = high Ⅱ pos く 0 ) unsigned bit ; int i , j ; sortsub(int 10W , int high, int pos) void 図 9 ビットごとに処理する基数交キ去のプログラム swap(), j); if (i > = j) break; while ((arrCj] & bit) ! = 0 & & i く j) while ((arrCi] & bit) for ( ; 1 くく pos— bit j = high; 1 10W ; return ; 0 & & i く j) 1 , pos); sortsub(low, j if ( (arr Chigh] & bit) sortsub(j , void sort (void) sortsub(0, high, pos) ; N sizeof(int) * 8 1 ) ; 作業を受け持つ sortsub 関数は、再帰呼出しをおこな います。最初は、再帰呼出しを終了するための条件です。 引数の low と high カ尊しいときは、処理しなけ川まなら ないレコードが 1 つしかないことを表します。この場合に は、、すでに整列している " とみなせるため、再帰呼出しを 終了してかまいません。また、 low のほうが大きいときは レコードがないことになるので、この場合も処理はイ畯で す。処理すべきレコードがあっても、調べるビットか残っ ていないこともありえます。これは、同し値のキーをもつ レコードが複数あるときに発生します。この場合にはキー の値は完全に等しいため、これらのレコードを整列するこ とはできません。よって、この場合にも再帰呼出しを終了 させます。 次は、値の分割です。分割するための基鴟は引数として 渡されている p 。 s の位置にピットが立っているかどうか です。ビットごとの言紲里積のみで検査ができるようにこの ビットの位置を表す値を bit に引算しておきます。また、 UNIX MAGAZINE 2003.9

Red Hat Linux の ツールたち CUPS(2) 則回は、 CUPS (Common UNIX Printing System の基本的な使い方を紹介しました。 CUPS サーバーのプロードキャスト機能を利用すれは、 ネットワーク上のプリンタを管理する手間が大皜に軽減さ れることがお分かりいただけたと思います。これで、 PS (PostScript) プリンタを、、とりあえす " 使えるようにな りました。しかし、このままではプリンタ独自の機能は使 えません。また、家庭てイ吏うプリンタの多くは PS に対応 していないので、今回は、ネットワークエ韆竟からいったん 離れて次の 2 つの話題をとりあげます。 ・ PS フリンタ用 PPD (PostScript Printer Descrip- tion) ファイルの利用法 ・非 PS プリンタの利用法 PPD ファイルの入手と利用法 PS 形式のデータを PS プリンタに出力する場合には、 CUPS のプリンタ登剥芋に、、 PPD ファイルを利用しな い " 設定 1 にしておけば、とりあえす印刷はできます。 しかし、解像度の変更や両面印刷などが可能なプリンタ であれば、 CUPS からこれらを制御できたほうがよいの はもちろんです。これらの機能をフルに活用するには、そ のプリンタに合った PPD ファイルをインストールする 必要があります。さいわい、多くの PS プリンタについて は、 Windows または Macintosh 用のプリンタドライバ に含まれる PPD ファイルが CUPS でも使えます。 今回は、富士ゼロックスの DocuPrint 280 ( オフショ ンの PS 対応キットを組み込んでいます ) を例に、 Win- 1 プラウザ 1 「 . でイす - る場合、プリンタのメーカー名として *Raw" 、モデ ル名として、、 Raw Queue (en)" を邇尺します。 UNIX MAGAZINE 2003.9 dows 用のプリンタドライノヾに含まれる PPD ファイルを 利用する方法を紹介します。 PPD ファイルは、プリンタに刊属するドライバ CD に 含まれている場合もあ川ま、メーカーのサポートページで PPD ファイルを含むドライバのアーカイプ・ファイルが配 布されていることもあります。ただし、 Windows マシン などにドライバがインストールされているのなら、そこか らコピーしたはうがてっとり早いかもしれません。私は、 VMware のホスト OS (Windows (P) に DocuPrint 280 のドライバをインストールしていますが、これに対応 する PPD ファイルは、 C : *WINDOWS*system32*sp001*drivers*w32x86*=> FX280J21 . PPD でした ( 誌面の都合上、で折り返しています。以下同 様 ) 。サプディレクトリ名が異なることもあるので、よく分 からない場合は工クスプローラの検索機能を使い、拡張子 ppd" をキーとして Windows のシステムフォルダ ( 一 般には、 C:*WINDOWS もしくは C:*WINNT) 以下 を検索するといいでしよう。 適切な PPD ファイルを入手したら、これを CUPS の PPD データベース・ディレクトリ (Red Hat Linux 7.3 にイ寸属の CUPS の場合は /usr/share/cups/model) に コピーします。ただし、 PPD ファイルに日本語が含まれ ている場合は注意が必要です。 Windows や Macintosh で使用される文字コードは一 般にシフト JIS ですが、これをそのままコピーすると、プ ラウサでプリンタ設定画面を表示した際に日本語の部分が 文字化けして解読不能になります ( プラウサで、表示に使 用する文字コードをシフト JIS に指定しても改善されませ 129