JPS63201743A - データ処理システム・ネットワークのためのキャッシング方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 以下の順序で本発明を説明する。

Ａ　産業上の利用分野 Ｂ　従来技術（第２図、第３図、第４図）Ｃ発明が解決
しようとする問題点 Ｄ　問題点を解決するための手段 Ｅ　実施例 Ｅｌ　分散システムの特徴 Ｅ２　ファイル・システムのマウント方法Ｅ′５　仮想
ファイル・システム間の関係（第１図、第５図、第６図
、第７図、第８ 図、第９図、第１０図、第１１図、第 １２図、第１３図、第１４図、第１５ 図、第１６図、第１７図、第１８図、 第１９図、第２０図） Ｆ　発明の効果 Ａ　産業上の利用分野 本発明は一般に分散データ処理システムのための動作の
改良、具体的にはローカル・エリア・ネットワーク（Ｌ
ＡＮ）もしくは大域ネットワーク（ＷＡＮ）によって相
互接続された多重プロセッサ・システムのためのオペレ
ーティング・システムの改良に関する。本発明に従う改
良によって、ファイルがシステム中のどこにあっても、
システム中のプロセッサによるファイルをアクセスする
ためのファイル中ディレクトリ・キャッシングの効率が
増大する。

Ｂ　従来技術 本発明はネットワーク中に相互接続された複数のプロセ
ッサによって特徴付けられる分散データ処理システムに
関する。実際に実施される時は、本発明はＩＢＭのシス
テム・ネットワーク・アーキテクチュア（ＳＮＡ）、具
体的にはＳＮＡ　　ＬＵ６．２拡張プログラム間通信（
ＡＰＰＣ）によりて相互接続される複数のＩＢＭ　　Ｒ
Ｔ（遠隔端末）ＰＣ（パーソナル・コンピュータ）上で
稼動する。

ＳＮＡはそのリンク・レベルとしてゼロックス（）（ｅ
ｒｏｘ）社によって開発されたローカル・エリア・ネッ
トワーク（ＬＡＮ）であるイーサ・ネット１　（Ｅｔｈ
ｅｒｎｅｔ　　１）もしくは５ＤＬＣ（同期データ・リ
ンク制御）を使用する。イーサ・ネット・ローカル・エ
リア・ネットワークを含むローカル・エリア・ネットワ
ークの簡単な説明は１９８３年プレンティス・ホール社
の発行者ロバート。

Ｊ、ブラドレによる著書ラレー、Ｅ、ジヨルダン及びブ
ルース・チャーチル著「ＩＢＭ　　ＰＣのための通信及
びネットワーキングＪ　（Ｌａｒｒｙ　Ｅ、　Ｊｏｒｄ
ａｎａｎｄ　　Ｂｒｕｃｅ　　Ｃｈｕｒｃｈｉｌｌ　”
　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓａｎｄ　Ｎｅｔｗｏｒ
ｋｉｎｇ　　ｆｏｒ　ｔｈｅ　　ＩＢＭ　　ＰＣ”、ｐ
ｕｂｌｉｓｈｅｄ　　ｂｙ　Ｒｏｂｅｒｔ　　Ｊ、Ｂｒ
ａｄｙ　（ａＰｒｅｎｔｉｃｅ−Ｈａｌｌ　　ｃｏｍｐ
ａｎｙ）（１９８３））に見出される。コンピュータの
ための通信システム、具体的にＳＮＡ及び５ＤＬＣのよ
り明確な説明は１９７８年アデイソンーウエスリ社刊の
本Ｒ０Ｊ、シプサ著［分散システムのための通信アーキ
テクチュアＪ　（Ｒ，Ｊ、　Ｃｙｐｓｅｒ”Ｃｏｍｍｕ
ｎｉｃａｔｉｏｎｓＡｒｃｈｉｔｅｃｔｕｒｅ　　ｆｏ
ｒ　　ＤｉｓｔｒｉｂｕｔｅｄＳｙｓｔｅｍｓ　、１ｐ
ｕｂｌｉａ’ｈｅｄ　　ｂｙ　Ａｄｄｉａｏｎ−Ｗｅｓ
ｌｅｙ　（１９７８））に見出される。しかしながら本
発明はイーサ・ネット・ローカル・エリア・ネットワー
クもしくはＩＢＭのＳＮＡ以外のネットワークによって
相互接続されるＩＢＭ　　ＲＴＰＣ以外の他の及び異な
るコンピュータを使用して実施できることを理解された
い。

上述のように、以下説明する本発明は通信ネットワーク
中の分散データ処理システムに向けられる。このような
環境で、ネットワーク中のノードにある各プロセッサは
どのノードにファイルが存在するかにかかわらず、ネッ
トワーク中のすべてのファイルをアクセスできる。第２
図に示したように分散ネットワーク環境１は通信リンク
もしくはネットワーク６によって接続された２以上のノ
ードＡ、Ｂ及びＣより成ることができる。ネットワーク
３は上述のようにローカル・エリア・ネットワーク（Ｌ
ＡＮ）もしくは大域ネットワーク（ＷＡＮ）でよい。後
者はシステムの他のノードもしくはＳＮＡネットワーク
への交換もしくは専用テレプロセシング（Ｔ、Ｐ　）接
続より成る。ノードＡ、ＢもしくはＣのうち任意のノー
ドには、上述のＩＢＭ　　ＲＴ　　ＰＣのような処理シ
ステム１０Ａ、１０Ｂもしくは１０Ｃが存在する。この
ようなシステム１０Ａ１１０Ｂ及び１０Ｃの各々は単一
ユーザ・システムもしくは多重ユーザーシステムでよく
、ネットワーク３を使用してネットワーク中の遠隔ノー
ドに存在するファイルをアクセスする能力を有する。た
とえば、局所ノードＡに存在する処理システム１０Ａは
遠隔ノードＢ及びＣにあるファイル５Ｂ及び５Ｃをアク
セスできる。

遠隔ノードをアクセスする際に遭遇する問題は先ず独立
型のシステムがどのようにしてファイルにアクセスする
かを調べることによって明らかになろう。第３図に示し
た独立型システム１０において、オペレーティング・シ
ステム（Ｏ８）１１中の局所バッファ１２はパーソナル
・コンビュータ中のハード・ファイルもしくはディスク
のようす永久メモリ２とユーザ・アドレス・スペース１
４の間で転送されるデータをバッファするのに使用され
る。オペレーティング・システム１１中の局所バッファ
１２は又局所キャッシュもしくはカーネル中バッファと
呼ばれる。局所キャッシュはメモリ（に移動した）常駐
ディスクによって最も良く理解できる。データはディス
ク上で持っていたものと同じ物理的特性を保持する。し
かしながら、情報は現在主システム・メモリ中において
達成される速度に極めて近い、より速いデータ転送速度
にする可能性のある媒体中に存在する。

独立型システムにおいて、カーネル・バッファ１２は装
置番号と装置内の局所ブロック番号（ＬＢＮ）で指定さ
れるブロック１５によって識別される。リード（読取り
）システム・コール１６が発生される時は、これは第４
図の段階１０１に示したようにファイル５のファイル記
述子及びファイル５内のバイト範囲とともに発生される
。オペレーティング・システム（ｏｓ）１１はこの情報
を受取りこれを段階１０２で装置番号及び装置中の論理
ブロック番号（ＬＢＮ）に変換する。次にオペレーティ
ング・システム１１は装置番号及び論理ブロック番号に
従ってキャッシュ１２を読取る（段階１０３）。

ディスク２から読取られたデータはキャッシュ・ブロッ
ク１５が必要になる迄キャッシュ・ブロック１５中に保
持される。この結果処理システム１０上で実行されてい
るアプリケーション・プログラム４からの相継ぐ読取り
要求は、前はディスクから読取っていた同じデータをデ
ィスク２からでなくキャッシュ１２からアクセスする。

キャッシュからの読取りはディスクをアクセスするより
も時間がかからず、従ってキャッシュから読取ることに
よって、アプリケージヨシ４のパホーマンスが改善され
る。明らかに、アクセスすべきデータがキャッシュ中に
存在しない時には、ディスク・アクセスを行わなければ
ならないが、この要求はまれにしか生じない。

同じようにアプリケーション４から書込まれるデータは
直ちにディスク２上に保管されず、キャッシュ１２上に
書込まれる。これによっても時間が節約され、アプリケ
ーション４のノ（ホーマンスが改善される。キャッシュ
１２中の修正されたデータ・ブロックはオペレーティン
グ・システム１１の制御によって定期的にディスク２上
に保管される。

本発明を実施する環境であるＡＩＸオペレーティング・
システムを利用する独立型システム中でのキャッシュの
使用はシステム−ディスクの全体的にパホーマンスを改
善し、相継ぐディスクの読取り及び書込みディスク動作
の除去によってアクセス時間を最小にする。

第２図に示した分散ネットワーク環境では、局所ノード
Ｃ中の処理システム１０ＣがノードＡからファイル５Ａ
ｅ読取る２つの方法が存在する。

１つの方法では、処理システム１０Ｃは全ファイル５Ａ
ｅコピーでき、これをあたかもノードＣに存在する局所
ファイル５Ｃであるかのように読取ることができる。こ
の方法でファイルを読取ると、仮にノードＢにおける他
の処理システム１０Ｂが、たとえばファイル５Ａがノー
ドＣでコピーされた後にファイル５Ａを変更すると間勉
が生ずる。処理システム１０Ｃはファイル５Ａになされ
た最新の変更にアクセスできていない。

処理システム１０ＣがノードＡにあるファイル５Ａにア
クセスする他の方法は、ノードＣにある処理システムが
必要とする時に一度に１ブロツク読取ることである。こ
の方法の問題は各読取り毎にネットワークの通信リンク
６を介して、ファイルの存在するノードＡに進まなけれ
ばならない点　　、にある。相継ぐ読取りごとにデータ
を送ることは時間がかかる。

ネットワークを介するファイルのアクセスは上述のよう
に２つの競合する問題を提示する。１つの問題は相継ぐ
読取り及び書込みのためにネットワークを介してデータ
を転送するのに要する時間にかかわる。他方ファイル・
データをノードに記憶してネットワークのトラヒックを
減少すると、ファイルの完全性が失われる。たとえば、
いくつかのノードの１つがファイルに書込み中であると
、このファイルにアクセスする他のノードは書込まれた
ばかりの最新の更新ファイルをアクセスできない。この
ような理由で、ファイルの完全性が失われ、ノードは正
しくない古いファイルにアクセスすることになる。本明
細書で、用語「サーバー（奉仕者）」はファイルを永久
的に記憶している処理システムを示し「クライエント（
依頼者）」はこのファイルにアクセスして処理する任意
の他の処理システムを意味するのに使用する。以下説明
する本発明は分散した情報を管理する問題に対する解決
を与えるオペレーティング・システムの一部である。

ＵＮＩＸオペレーティング・システム環境における分散
データ処理システムを支援する他の方法も知られている
。たとえば、サン・マイクロシステム社はＮｅｔｗｏｒ
ｋ　Ｆｉｌｅ　　Ｓｙｓｔｅｍ　（ネットワーク・ファ
イル・システムＮＦＳ）’ｉミリリースており、ベル・
ラボラ）　ＩＩ社はＲｅｍｏｔｅＦｉｌｅ　　Ｓｙｓｔ
ｅｍ（遠隔ファイル・システムＲＦＳ）を開発している
。サン・マイクロシステム社のＮＦＳはＵＳＥＮＩＸｌ
　９Ｂ６年夏期技術会議兼展示会で発表された議事録Ｓ
、　Ｒ，フライマン著）’Ｖｎｏｄｅｓ　：　Ｓｕｎ　
Ｕｎｉｘにおける多重ファイル・システム型のためのア
ーキテクチュア」第２３８−第２４７頁（Ｓ、Ｒ，Ｋｌ
ｅｉｍａｎ。

”Ｖｎｏｄｅｓ　：　Ａｎ　　Ａｒｃｈｉｔｅｃｔｕｒ
ｅ　　ｆｏｒＭｕｌｔｉｐｌｅ　　Ｆｉｌｅ　　Ｓｙｓ
ｔｅｍ　Ｔｙｐｅｓ　　１ｎＳｕｎ　Ｕｎｉｘ、ＵＳＥ
ＮＩＸｌ　９８６　ＳｕｍｍｅｒＴｅｃｈｎｉｃａｌ　
　Ｃｏｎｆｅｒｅｎｃｅ　ａｎｄ　Ｅｘｈｉｂｉｔｉｏ
ｎ。

ｐｐ、２３８−２４９）、１９８５年ＵＳＥＮＩＸ会議
議事録ラッセル・サンドバーブ等著［サン・ネットワー
ク・ファイルシステムの設計及び具体例１　（Ｒｕ５ｓ
ｅｌ　　Ｓａｎｄｂｅｒｇ　　ｅｔ　　ａｌ、、Ｄｅｓ
ｉｇｎ　　ａｎｄ　　Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ　
　ｏｆｔｈｅ　　Ｓｕｎ　Ｎｅｔｗｏｒｋ　Ｆｉｌｅｓ
ｓｙｓｔｅｍ”、Ｃｏｎｆｅｒｅｎｃｅ　　Ｐｒｏｃｅ
ｅｄｉｎｇｓ、Ｕｓｅｎｉｘ１９８５、ｐｐ、　１１９
−１３０　）、ジョメン・チャン著「ＮＦＳにネットワ
ーク・ロッキング・サービスを与えるステータス・モニ
タ」、ダン暑つオルシュ等著［サン・ネットワーク・フ
ァイル・システム環境観」第１１７−１２４頁（Ｄａｎ
Ｗａｌｓｈ　　ｅｔ　　ａｌ、　Ｑｖｅｒｖｉｅｗ　ｏ
ｆ　　ｔｈｅＳｕｎ　Ｎｅｔｗｏｒｋ　Ｆｉｌｍ　Ｓｙ
ｓｔｅｍ”、ｐｐ、１１７−１２４）、ジョメイ・チャ
ン著「サンネット」第７１−７５頁（ＪｏＭｅ　ｉ　　
Ｃｈａｎｇｌｏ。

５ｕｎＮｅｔ”、ｐｐ、７ｌ−７５）及びプラトレイ・
テイラ著「サン環境における安全ネットワーキング」第
２８−３６頁（Ｂｒａｄｌｅｙ　Ｔａｙｌｏｒ。

”　５ｅｃｕｒｅ　　Ｎｅｔｗｏｒｋｉｎｇ　　ｉｎ　
　ｔｈｅ　　ＳｕｎＥｎｖｉｒｏｎｍｅｎｔ”、ｐｐ、
　２　ｓ−３６）を含む一連の出版物に説明されている
。ＡＴ＆ＴＲＦＳについても、１９８６年６月ジョーシ
ア州アトランタ市で開催されたＵＳＥＮＩＸ会議の議事
録アンドリウ、Ｐ、リフキン等著ＪＲＦＳアーキテクチ
ュアの概観Ｊ　（Ａｎｄｒｅｗ　Ｐ、　Ｒｉｆｋｉｎ　
　ｅｔａｌ、　、”ＲＦＳ　　Ａｒｃｈｉｔｅｃｔｕｒ
ａｌ　Ｏｖｅｒｖｉｅｗ”ＵＳ　ＥＮＩＸ　　Ｃｏｎｆ
ｅｒｅｎｃｅ　　Ｐｒｏｃｅｅｄｉｎｇｓ。

Ａｔ１ａｎｔａ、Ｇｅｏｒｇｉａ（Ｊｕｎｅ　　１９８
６　）、ｐｐ、１＝１２）、リチャード・ハミルトン等
著［遠隔ファイル・シェアリングの管理者の見地」第１
−９頁（Ｒｉ　ｃｈａｒｄ　Ｈａｍｉｌ　ｔｏｎ　ｅ　
ｔ　ａｌ、、Ａｎ　　Ａｄｍｉｎｉｓｔｏｒ’ｓ　　Ｖ
ｉｅｗ　　ｏｆ　　ＲｅｍｏｔｅＦｉｌｍ　Ｓｈａｒｉ
ｎｇ”、ｐｐ、１−９）、トム拳ホートン等著［ファイ
ル・システム・スイッチ」ｐｐ。

１−２　（Ｔｏｍ　Ｈｏｕｇｈｔｏｎ　　ｅｔ　　ａｌ
。、ＦｉｌｅＳｙｓｔｅｍｓ　　５ｗ１ｔｃｈ”、ｐｐ
、１−２）及びディピッドＪ、オランダ等著「システム
Ｖ中のネットワーキングのためのフレームワーク」第１
−８頁（Ｄａｖｉｄ　　Ｊ、０１ａｎｄｅｒ　　ｅｔ　
　ａｌ、、　ＩＩ　ＡＦｒａｍｅｗｏｒｋ　　ｆｏｒ　
　Ｎｅｔｗｏｒｋｉｎｇ　　ｉｎ　　ＳｙｓｔｅｍＶ”
、ｐｐ、１−８）を含む一連の出版物に説明がなされて
いる。

本発明が具体化される、サン・マイクロシステムズ社の
ＮＦＳと異なる分散サービス拳システムの１つの特徴は
、たとえばサン社の方法が実質的に無国籍マシーンを設
計した点にある。さらに具体的には、分散システムにお
けるサーバーは無国籍サーバーであるように設計されて
いる。このことはサーバーがクライエントのノードに関
して、どのクライエント・ノードがサーバーのファイル
に開放されているか、クライエントの処理が読取り専用
もしくは読取り書込みモードのどちらでファイルを開い
ているかどうか、もしくはクライエントがファイルのバ
イト範囲についてロックしたかどうかを示す情報のよう
な任意の情報を記憶していないことを意味する。この具
体例はサーバーの設計を簡単にする。それはクライエン
トが失敗した時もしくはサーバーにクライエントがサー
バーの資源についての要求を解除したことを適切に知ら
せないでオフ・ラインに進んだ時に生じ得る誤り回復状
態を処理しなくてよいからである。本発明が具体化され
る分散サービス・システムの設計では全（異なる方法が
使用される。さらに具体的には、本発明の分散サービス
・システムは多国籍サーバーの具体化として特徴付けら
れる。

本明細書に説明される多国籍サーバーは誰がそのファイ
ルを使用中であるか、どのようにファイルが使用されつ
つあるかについての情報を保持する。そのためにはサー
バーは何等かの手段でクライエントとの接触が失われた
ことを検出し、クライエントに関する累積国籍情報が廃
棄できるようにしなければならない。本明細書で説明す
るキャッシュの管理戦略は、しかしながら、サーバーが
このような国籍情報を保持しない限り具体化できない。

キャッシュの管理は以下説明するように、サーバーのフ
ァイルの開放の要求を発生したクライエント・ノードの
数及びこれ等の開放時の読取り／書込みモードによって
影響される。

さらに具体的には、ファイル経路名の分析がしばしば行
われるので、この分析は効果的に行われなければならな
い。ファイル名を使用する各システム・コール、たとえ
ばマウント（接続）もしくは開放するにはディレクトリ
を読んでファイルの名前の経路の各要素を探索すること
が必要である。

ファイル名を使用するたびに多くのディレクトリを読取
らなければならないというパホーマンス上のペナルティ
はディレクトリの一部が遠隔ノードにある分散環境にお
いてはさらに厳しくなる。

成るＵＮＩＸ（ＵＮＩＸは米国におけるＡＴＴベル研究
所の商標）の具体例はこれ等がファイルの名を分析に使
用する各度にディレクトリの項目を記憶（キャッシュ）
する。前にキャッシュされた項目と共通の経路部分を有
する名前を有する同じファイル（単、複）についてのそ
の後のファイル名分析はキャッシュ中にディレクトリの
項目を見出すことができるので高速に実行される。キャ
ッシュ中にディレクトリの項目を見出すことはディレク
トリを読取り及び探索するよりも高速である。それは（
１）ディレクトリ・キャッシュが探索のために最適化さ
れているオペレーティング・システムによって保持され
る特殊データ構造であること（２）キャッシュはメモリ
に保持されているが、ディレクトリはファイル・システ
ムから読取る必要があること、及び（３）キャッシュは
通常調べるのに制限された数の項目を有することによる
。ディレクトリ・キャッシュは最も最近使用した、従っ
て最も有用である可能性の高いディレクトリ項目を保持
している。

ディレクトリ・キャッシュを使用する際にオペレーティ
ング・システムが当面する２つの主な問題が存在する。

キャッシュの内容はディレクトリの内容と一貫性が保持
されなくてはならず、キャッシュは太き（なりすぎては
ならない。キャッシュの一貫性が保持されることは重要
である。キャッシュが、ファイルのｉノード番号をたと
えば４５と指定したが、ディレクトリがおそら（ＭＶ（
移動）指令によって変更されてファイルの実際のｉノー
ド番号が６２になっていたとすると、ファイル名の分析
によって間違ったファイルを指摘し、開放動作は指摘さ
れたものと異なるファイルを開（。もしキャッシュが任
意に成長できるならば、結果的に大きくなりすぎてこれ
を探索するのに必要とされる時間がパホーマンスを劣化
させることになる。

独立型のシステムにおいては、オペレーティング・シス
テム自体がディレクトリに対するすべての変更に責任が
あり、オペレーティング・システムはディレクトリ・キ
ャッシュから変更された任意の項目を除去でき、常にデ
ィレクトリ・キャッシュに一貫性のある項目を残すこと
ができる。キャッシュが一杯になると、ある項目を除去
して新らしい項目のために余地を残すことができる。余
地を作るために除去される項目の選択は厳密でないが、
最も最近使用した項目を残すと、パホーマンスは通常は
とんど影響を受けない。独立型のシステムの場合にはデ
ィレクトリ・キャッシングの主要な問題はこのようにし
て処理されるので独立Ｍ 型のＡＩＸ　　　を含むい（つかのＵＮ工ＸＴＭ具体例
もディレクトリ・キャッシングを行う。

独立型システムのための解決手段は分散環境では使用で
きない。ディレクトリ・キャッシュはクライエント・ノ
ードに保持されており、他のサーバー・ノード中のブイ
レフ）　ＩＪの変更は一貫しないキャッシュ項目を生ず
る。各サーバーにおける各ディレクトリの変更を各クラ
イエントのキャッシング・ディレクトリの項目に知らせ
ることによって一貫性を保持する試みはネットワークを
これ等のメツセージで一杯にし、ディレクトリ・キャッ
シングから得られるバホーマンスの利点をそこなう。

Ｃ発明が解決しようとする問題点 本発明の目的はネットワーク中のファイル・ディレクト
リの情報をキャッシングする能力を与え、その有効性を
保証し、変更がなされていない期間中はこの情報を不必
要に、非効果的に更新しないことによってネットワーク
中のファイル・ディレクトリをアクセスする時の動作効
率を改良することにある。

Ｄ　問題点を解決するための手段 本発明に従い、ネットワーク中で互に接続された複数の
データ処理システムのための改良されたディレクトリの
キャッシング技法が与えられる。

システム中の局所即ちクライエント・データ処理システ
ムが遠隔の即ちサーバー・データ処理システムに単位の
ディレクトリ情報を質問する時は、サーバー・システム
はサーバー・システムのディレクトリの構造のその後の
変更に応答して関連ディレクトリ情報の追加の単位を自
動的にクライエント・システムに送ることができる。も
し複数の可能な理由の１つのためにサーバー・システム
がクライエント・システムの更新を続けることができな
い時には、サーバー・システムはクライエント・システ
ムにこの事実を通知し、これによってクライエント・シ
ステムはこの経路に関連して前に記憶したディレクトリ
・キャッシュ項目を自分自身で除去できる。それはクラ
イエント・システムがこのキャッシュされた経路情報を
現在正しいともはや考えることができないからである。

サーバー・システムがディレクトリ経路の更新情報をも
はや送り続けることができない可能性のある理由は、（
１）サーバーの処理資源の一般的飽和、（２）ディレク
トリのキャッシング更新機能に割当てられているサーバ
ー処理資源の飽和、（３）サーバー・システムトクライ
エント・システム間で信用ある通信リンクが現在利用で
きないこと、（４）たとえばサーバー・システムで保守
サービスを可能ならしめるために、サーバー・システム
を通信ネットワークから切断する必要性及び（５）クラ
イエント・システムから最近照会がないことである。

サーバー・システムが複数のクライエントの更新中に、
その更新機能を遂行するための資源がほぼ尽きた状態に
なると、サーバーは最近最も照会が少なかったクライエ
ントにこのことを、システムのパホーマンスがこの更新
能力を中断してもほとんど影響を受けることがないとい
うことを根拠して知らせる。

Ｅ　実施例 Ｅｌ　分散システムの特徴 以下マシンのファイルを管理する論理装置を修正して、
い（つかの異なるマシン中に物理的に存在するファイル
を局所ファイル会システムの一部であるように見せる分
散ファイル・システムを構成する時に遭遇する問題の解
決方法を説明する。

説明される具体例はＡＩＸオペレーティング・システム
のファイル・システムの拡張である。このオペレーティ
ング・システムについての詳細については上述の技術論
文を参照されたい。以下、ＡＩＸファイル◆システムの
概念の特殊な知識、ツリー（木）構造化されたファイル
・システム、ディレクトリ、及びｉノードを含むファイ
ル・システム組織を仮定している。

本発明の論議に関連するファイル・システムの主な特徴
を次に示す。

（ａ）　　個々のファイル・システム上の各ファイルは
そのｉノード番号によって一意的に識別される。

（ｂ）　　ディレクトリはファイルであり、従ってディ
レクトリはそのｉノード番号によって一意的に識別され
る。

註：ある場合には、ディレクトリとディレクトリでない
ファイル（たとえば、単にオリジナル・データを含むフ
ァイル、もしくは特殊ファイルもしくはパイプのような
ＵＮＩＸ誘導オペレーティング・システムによって支援
される他の型のファイル）を区別する必要がある。

本明細書では用語「単純ファイル」を非ディレクトリ型
のファイルを示すのに使用する。特にことわらないかぎ
り、用語「ファイル」はディレクトリ・ファイルもしく
は単純ファイルのいずれかを意味し、用語「ディレクト
リ」はディレクトリ・ファイルを意味する。

（ｃ）ディレクトリは次の形式の項目の配列体を含む。

名前−ｉノード番号 ここでｉノード番号は単純ファイルもしくは他のディレ
クトリのｉノード番号である。

註：ディレクトリは他のディレクトリを含み、この他の
ディレクトリは他のディレクトリもしくは単純ファイル
を含むことができる。

従ってディレクトリを多（のレベルの子孫のディレクト
リを含む部分ツリーの根とみなし、ツリーの葉を単純フ
ァイルとみなすことができる。

本明細書で用語１子孫」は特定のディレクトリの下のフ
ァイル・ツリー中に存在するすべてのファイルを意味し
、他のディレクトリを通って達することのできるものも
含む。ディレクトリの１直接子孫」とはその名前がディ
レクトリに現われるファイル（単純ファイルもしくはデ
ィレクトリ）のみをさす。

（ｄ）　　規約によって、ファイル・システムの根のデ
ィレクトリのｉノード番号はｉノード番号２とする。

Ｅ２　ファイル・システムのマウント方法法に伝統的な
ＵＮＩＸオペレーティング・システムが全ファイル・シ
ステムのマウント（連結取付け）を使用してファイル・
ツリーを形成する方法及びこのようなファイル・ツリー
の経路をたどる方法について説明する。

装置のファイル・システムの内の経路「／ｄｉｒ１／ｄ
ｉｒ２／ファイル」をたどるときは次の段階を含む。

（１）ｉノード番号２によって識別されるファイル（装
置のルート・ディレクトリ）を読取る。

（２）名前＝ｄｉｒ１の項目を求めてディレクトリを探
索する。

（３）ｄｉｒｌに関連するｉノード番号によって識別さ
れるファイル（これは経路中の次のディレクトリである
）を読取る。

（４）　　名前＝ｄｉｒ２の項目を求めてディレクトリ
を探索する。

（５）　　ｄｉｒ２に関連するｉノード番号によって識
別されるファイル（これは経路中の次のディレクトリで
ある）を読取る。

（６）名前＝ファイルの項目を求めてディレクトリを探
索する。

（７）　　このディレクトリ中のファイルに関連するｉ
ノード番号は経路「／ｄｉｒ　１／ｄｉｒ　２／ファ；
イル」によって識別される単純ファイルのｉノード番号
である。

個々のファイル・システムに常駐するファイル・ツリー
はこれからノードの総合ファイル・ツリーが構成される
ビルデング・ブロック（積み木）である。特定の装置（
たとえば、ハード・ファイルの区画）がノードの根ファ
イル・システムヲ含む装置として指定される。他の装置
上に存在するファイル・ツリーはマウント動作によって
ノードのファイル・ツリーに付は加えることができる。

マウント動作にとって２つの主要なパラメータは（１）
マウントさるべき装置の名前及び（２）装置のファイル
・ツリーをマウントするディレクトリ迄の経路である。

このディレクトリはすでにノード・ファイル・ツリーの
１部でなくてはならず、もしくはこのディレクトリはす
でに（マウント動作によって）ノード・ファイル・ツリ
ーに付は加えられたファイル・システム中のディレクト
リでなくてはならない。

マウントが達成された後に、元々マウントしたディレク
トリを流れていた経路はマウントされたファイル・シス
テムのルートのｉノ、−ドを通って流れる。マウント動
作は次のように進行する。

（１）マウント点迄の経路に従い、マウントされた装置
によってカバーさるべきディレクトリの装置の名前及び
ｉノード番号を求める。

（２）次のものを含むデータ構造を形成する。

（ａ）　　カバーされるディレクトリの装置の名前及び
ｉノード番号 （ｂ）　　マウントされる装置の名前 ノードの総合ファイル・ツリー中で従う経路は（ａ）マ
ウントするｉノード（即ち勿論この経路の終り）迄、装
置のファイル・ツリー中の経路に従う（ｂ）−族マウン
ト点に遭遇するとマウント・データ構造を使用してどの
装置が経路中の次に来るかを決定し、（ｃ）マウント構
造中に示された装置中のｉノード２（ルートｉノード）
の経路に従い始めることより成る。

マウント・データ構造は非持久性であり、これ等はディ
スク上に記憶されることはない。所望のマウントのリス
トは初期プログラム・ロード（ＩＰＬ）の１部としてマ
シンの電源がオンにされる度に再発生しなければならな
い。以上の説明は伝統的なＵＮＩＸオペレーティング・
システムカ全ファイル・システムのマウントを使用して
ファイル・ツリーを形成する方法及びこのようなファイ
ル・ツリー中の経路を従う方法を示したものである。こ
のような具体例は装置上に常駐する全ファイル・システ
ムのマウンティングだけに制限される。本明細書及び上
述の参考論文に示された仮想ファイル・システムは（１
）装置のマウントを可能ならしめる他にファイル（ディ
レクトリもしくは単純ファイル）のマウントを可能なら
しめることによって装置上に常駐するファイル・システ
ムの１部をマウントすること及び（２）すでにファイル
・ツリーの１部になっているディレクトリ上に遠隔もし
くは局所ディレクトリをマウントすることを可能ならし
める。本発明はすでにファイル・ツリーの１部である単
純ファイル上に単純ファイル（遠隔もしくは局所の）を
マウントすることを可能ならしめることによって仮想フ
ァイル・システムの概念を補強する。

仮想ファイル・システムでは、特定の装置ファイル・シ
ステムに対して遂行される動作は明らかにノードの総合
ファイル・ツリーの構成及び使用を処理する動作とは区
別される。ノードの仮想ファイル・システムは局所及び
遠隔ファイルの両方にアクセスできる。

局所ファイルの管理は遠隔ファイルの管理よりも簡単で
ある。このため、仮想ファイル・システムの論議は２つ
の部分に分けられる。第１の部分は局所の動作だけを説
明する。この部分は遠隔動作を説明するための基本を与
える。同じデータ構造及び動作が遠隔及び局所動作の両
方に使用される。局所動作は独立型の動作に関連するデ
ータ及び手順の部面を説明する。遠隔動作についての論
議は遠隔動作に関連する情報を付は加えるにとどめ、局
所動作のセクションでなされた説明は繰返さない。

Ｅ３　仮想ファイル・システム間の関係第５図は仮想フ
ァイル・システムのデータ構造間に存在する関係を示す
。マウント動作毎に新らしい仮想ファイル・システム（
ｖｆＳ）のデータ構造が形成される。この構造の基本要
素は（、）この仮想ファイル・システムの根のＶノード
（仮想ノード）へのポインタ（たとえばブロック２１か
らブロック２３への矢印）及び（ｂ）この仮想ファイル
・システムが形成された時にマウントしたＶノードへの
ポインタ（たとえばブロック２５からブロック２４への
矢印）である。

ｉノードを仮想ファイル・システムのファイル・システ
ム独立部分で表現する必要が生じた時は、これをＶノー
ドで表わす。この構造の主な要素は次のものである。

（ａ）■ノードを含むｖｆｓへのポインタ（たとえばブ
ロック２２からブロック２１への矢印）（ｂ）　　この
Ｖノード上にマウントするｖｆｓへのポインタ（たとえ
ばブロック２４からブロック２５への矢印）。しかしな
がら、すべてのＶノードが仮想ファイル・システムのた
めのマウント点ではない。即ち空ポインタはこのＶノー
ドがマウント点でないことを示すことに注意されたい。

（ｃ）代理ｉノードもしくは実ｉノードへのポインタ（
たとえばブロック２６からブロック３２への矢印） （ｄ）　　ノード表項目へのポインタ（このポインタは
ファイルが遠隔ファイルである時にだけ非空ポインタで
ある） 他のＵＮＩＸオペレーティング・システムと同じように
ＡＩＸオペレーティング・システムはこのシステムが使
用中の各ｉノードに関する情報を含むメモリ常駐表を保
持している。たとえばファイルが開かれる時は、そのｉ
ノードがディスクから読取られ、そのｉノードの情報の
部分集合がある追加の情報とともにｉノード表中に記憶
される。

ｉノード表の項目の主要要素は（ａ）ファイル・アクセ
ス構造リストのヘッドへのポインタ及び（ｂ）ディスク
ｉノードからの情報（その詳細はここでは関係ない）で
ある。

ファイル・アクセス構造リストはどのノードが開いたフ
ァイルを有するかについての情報、これ等の開放のモー
ド（読取り専用もしくは読取り一書込み）についての情
報を記録する。ファイルを開いている各ノードには別個
のファイル・アクセス構造が存在する。この状態情報に
よってサーバーはどのように各クライエントがサーバー
のファイルを使用しているかを知ることができる。

ファイル・システムはこれに対して遂行される動作のセ
ットを支援する。処理は次のようにファイル・システム
動作を遂行することによってファイル・システムと相互
作用する。

（１）ユーザは（おそら（）ある入力パラメータを与え
て動作の１つを呼出す。

（２）ファイル・システム論理装置が動作を遂行する。

動作によってファイル−システムの内部状態が変ること
がある。

（３）ファイル・システム論理装置が呼出したユーザに
返答する。この返答はおそら（ある復帰パラメータであ
る。

ファイル・システムでなされる動作はｖｎ動作もしくは
ｖｎ　　ｏｐｓと呼ばれる。いくつかのｖｎｏｐｓがあ
るが、ここでの説明にとって重要なものを次に説明する
。

（ＶＮルックアップ〕 ｖｎルックアップ動作ではファイル働システム中の経路
に従う際の主な繰返し段階はディレクトリ中の経路の構
成要素の名前を探知すること及び関連ｉノード番号を使
用してチェーン中の次のファイルを探知することである
。局所ファイルに行われるｖｙ１ルックアップの動作の
ための擬似コードを次にあげる。

機能ルックアップ 入カニディレクトリＶノード・ポインタディレクトリ中
で探索する名前 出カニ名前を見出したファイル／　ｄ　ｉ　ｒへのＶノ
ードΦポインタ ディレ、クトリのＶノード・ポインタをｉノード・ポイ
ンタに変換する（Ｖ）−ドのポインタを使用する）。

ディレクトリのｉノードをロックする。

もしくディレクトリ中の探索が許可されていないならば
） ディレクトリのｉノードをアンロック 誤りを戻す ディレクトリ中に名前を探索する もしく見出されたら） 名前のためのファイル・ハンドルを形成（ディレクトリ
の項目に見出されたｉノードを使用） ファイル・ハンドルのためのＶノードへのポインタを求
める。

ディレクトリのｉノードをアンロック ポインタをＶノードに戻す。

そうでないならば（見出されないならば）ディレクトリ
のｉノードをアンロック 誤りを戻す 〔ルックアップＰＮ） ルックアップルｎ動作は経路に従う機能である。

その入力は経路（たとえば「／ｄｉｒ　１　／　ｄｉｒ
２／ファイル」）であり、その復帰はファイルを表わす
Ｖノードへのポインタである。ルックアップｐｎ・　は
ｖｎルックアップを呼出して１つのディレクトリを読取
り、次にチェックしてｖｎルックアップによって戻され
たＶノードがマウントしたかどう　　。

かを知る。もしそのＶノードがマウントしていなければ
、ルックアップｐｎが同じファイル・システム中のｖｎ
ルックアップを呼出す。もしＶノードがマウントしてい
ると、ルックアップｐｎはマウントされたファイル・シ
ステム（たとえば第５図のブロック２４）からマウント
されたファイル・システム（たとえば第５図のブロック
２５）へのポインタに従う。このｖｆｓからは根Ｖノー
ド（たとえば第５図のブロック２６）へのポインタに従
う。もしこのＶノードがディレクトリで単純ファイルで
なければ、新らしいｖｎルックアップを発生して、入力
としてこのｖｆｓのルー）ｖノード及び経路中の次の要
素を構成する名前を与える。ルックアップルｎ機能のた
めの擬似コードを下にあげる。

機能ルックアップｐｎ 入カニ経路の名前 出カニ指名されたＶノードへのポインタもしく経路の最
初の文字が１１１であると）、探索のための現在のＶノ
ードはユーザの根のディレクトリである。

そうでないと、探索されている現在のＶノードはユーザ
の現在のディレクトリＶノードである。

反復する。

もしく経路の次の要素が６１．″ならば）（現在のＶ）
−ドは仮想ファイル・システムの根であるから） 現在のＶノードはこの仮想ファイル・システムをマウン
トするＶノードとなる。

もしくマウントするＶノードがないならば）誤りを戻す
。”０．°′はファイル・システムの過去の根である。

ｖｎルックアップを使用して現在のＶノードの経路要素
をルックアップする。

もしく　ｖｎルックアップが経路要素を見出すと） 現在のＶノードはｖｎルックアップによって戻されたＶ
ノードとなる。

（現在のＶノードはマウントされているので）、 マウントされた仮想ファイル・システムを表わすｖｆｓ
構造への現在のＶノードのポインタに従う。

現在のＶノードがマウントされたｖｆｓの根Ｖノードと
なる。

そうでない時は、ｖｎルックアップはファイルの要素を
戻すことはできない（誤り）。

探索は失敗する。

以上の動作を（追加の経路がなくなる迄）反復する。

戻る（現在のＶノード）。

次にファイルへの経路に従いディレクトリをマウントす
るシナリオを説明することによって動作を説明する。先
ず、ファイルに向う経路に従うものとして、アプリケー
ション・プロセスがファイ／ｌ／”　／　ｕ　／　ｄｅ
ｐｔ　５４／ステータス“のためのシステム・コール（
開放）を発生したものとする。

仁の要求は第５図を参照して以下に説明するようにオペ
レーティング・システムで達成される（基本的にＵＮＩ
Ｘオペレーティング・システムと変らない動作について
の詳細はここでは説明しない）。

次の仮定を行う。先ずブロック２１によって示したｖｆ
ｓを根の仮想ファイル・システムであるものとする。次
にファイル°＋／ｕ”をＶノード・ブロック２４及び１
ノード・ブロック３１によって表わす。第３に、前のマ
ウント動作である装置のファイル・システムがディレク
トリ゛Ｉ／ｕ”上にマウントされているものとする。こ
のマウントはブロック２５によって表わされるｖｆｓを
形成したものである。第４に、ディレクトリ及びファイ
ルのすべてが同じ装置上にあるものとする。第５に、次
に示すディレクトリの項目が指示されたディレクトリ中
に存在するものとする。

ディレクトリ ｉノード番号　　　名前　　　　ｉノード番号２　　　
　　　”　ｕ　”　　　　　　１５４５　　　　”ｄｅ
ｐｔ５４”　　　７１７１　　　　″ステータス”　　
　　１２システム・コールを具体化するコードがこの経
路に従うルックアップｐｎを呼出す。ルックアップｐｎ
は根仮想ファイルΦシステムのルートＶノード（ブロッ
ク２３）で開始し、このＶノードによって表わされたデ
ィレクトリ・ファイル中の名前″ｕ”をルックアップす
るｖｎルックアップを呼出す。ｖｎルックアップはこの
ディレクトリ中に名前”ｕ”がブロック３１中でｉノー
ド１５と関連していることを見出す。ｖｎルックアップ
はポインタをｉノード１５に関連するＶノードに戻さな
ければならない。この動作を行うために、ｉノード１５
がｉノード表中にもたらされる。次にこれがチェックさ
れて親のｖｆｓ中にすでにこのＶノードに対するＶノー
ドが存在するかどうかを知る（入力Ｖノード（ブロック
２６）は親のｖｆｓに向うポインタを有する）。この場
合は存在する。

次にｖｎルックアップは根のｖｆｓ（ブロック２１）中
にＶノードを見出し、ポインタをこのＶノードに戻す。

ルックアップｐｎは戻されたＶノードが親のｖｆｓ中で
マウントするノードであることを発見する。ポインタは
Ｖノード（ブロック２４）からマウントされるｖｆｓ（
ブロック２５）に向う「マウント・オーバ」ポインタで
ある。ルックアップｐｎは新らしいｖｆｓ（ブロック２
５）の根Ｖノードへの「根Ｖノード」ポインタに従う。

ルックアップｐｎはここで再びｖｎルックアップを呼出
す。今度はルートｖノード（ブロック２６）へのポイン
タ及び名前”　ｄｅｐｔ　５４　”を入力する。

上述のように、ｖｎルックアップはディレクトリを読取
り、この名前に関するｉノードを見出し、親ｖｆｓ（ブ
ロック２５）中のこのｉノードに対するＶノードを見出
すか、形成して、ポインタをこのＶノードに戻す。ルッ
クアップｐｎはもう一度ｖｎルックアップを呼出し、見
出したばかりのディレクトリのためのＶノード及び名前
「ステータス」を入力する。ｖｎルックアップはディレ
クトリを読取り、名前（ブロック３４）に関連するｉノ
ードを見出し、親ｖｆｓ（ブロック２５）中のこのｉノ
ードのためのＶノード（ブロック２８）を見出すか、ポ
インタをこのＶノードに戻す、システム・コールを具体
化するコードはここでこのファイルに対して要求された
動作を遂行する。

ここでアプリケーション・プロセスがマウント・システ
ム・コールを発生して、ディレクトリ”／　ｕ　／　ｆ
　ＯＯ”の上にファイル″ｕ　／　ｇ　ｏ　ｒ　ｐ”を
マウントするものと仮定する。次のシナリオはどのよう
にしてこの要求がオペレーティング・システムによって
達成されるかを説明するものである、（再び、ＵＮＩＸ
オペレーティング・システムと基本的に変らない動作は
詳細には説明しない）。

このシナリオは初期条件を表わす第６図、最終条件を表
わす第７図を参照して次の仮定を用いて説明する。先ず
、ブロック４１によって表わすｖｆｓをルートの仮想フ
ァイル・システムとし、第２に、含まれるディレクトリ
及びファイルのすべては同じ装置上にあるものとする。

第３に次のディレクトリの項目が示されたディレクトリ
に存在するものとする。

ディレクトリ ｉノード番号　　　名前　　　　ｉノード番号２　　　
　　　　”ｕ”　　　　　　　１５２　　　　　　”　
ｅ　ｔ　ｃ”　　　　　８３ｉ　ｓ　　　　　　”ｇｏ
ｒｐ”　　　　　９２８３　　　　　　”ｆｏｏ”　　
　　　７５７５　　　　ｆｉｌｅｌ”　　　　　８９マ
ウント・システム・コールを具体化するコードは次の動
作を行う。ルックアップｐｎが呼出され、マウントすべ
きファイル、”ｅｔｃ／ｆｏｏ”への経路に従う。この
動作の完了時に、ルー）ｖｆｓ（ブロック４１）は’　
／　ｅ　ｔ　ｃ　／　ｆ　ｏ　ｏ”のためのＶノード（
ブロック４４）を含み、ブロック４４はルー）ｖｆｓ（
ブロック４５）を指すポインタ及びｉノード７５のため
のｉノード表項目（ブロック４５）を指すポインタを有
する。ルックアップｐｎが呼出されて、マウントされる
べきファイル゛／ｅ　ｔ　ｃ　／　ｇ　ａ　ｒ　ｐ　”
への経路に従う。この動作の完了時に、ルートｖｆａ（
ブロック４１）はルートｖｆａ（ブロック４１）へのポ
インタ及びｉノード９２のためのｉノード表項目（ブロ
ック４８）へのポインタを有する”　／　ｅ　ｔｃ　／
　ｇｏｒｐ　”　（ブロック４９）のためのＶノードを
含む。ここでマウント論理装置が先ず新らしいｖｆｓ（
ブロック４６）を形成し次にその親ｖｆｓ（ブロック４
６）へ戻すポインタ及びｖｆｓのルートｉノード（ｉノ
ード９２、ブロック４８）へのポインタを有するとのｖ
ｆｓ（ブロック４６）をルートｖノード（ブロック４７
）を形成する。「マウント・オーバ」ポインタはルート
ｖｆｓ（ブロック４１）中のカバーされるＶノード（ブ
ロック４４）に設置され、その上にマウントするＶノー
ド（ブロック４４）へのポインタが新らしいｖｆｓ中に
設置される。

次に独立型の動作のためのデータ構造を説明する。ここ
で本発明を支援するオペレーティング・システムを具体
化する、第２図に示したものと類似の分散システムを示
す第１図を参照する。第１図の参照番号は第２図及び第
３図中の対応する部品と同一番号が使用されている。次
の説明で、用語サーバーはファイルが永久的に記憶され
るノードを示すのに使用され、用語クライエントはこの
ファイルにアクセスするプロセスを有する他のノードを
意味するのに使用される。しかしながら、サーバーとい
う用語はある局所ネットワーク・システム中に使用され
る専用サーバーという用語を意味していないことに注意
されたい。本発明が具体化される分散サービス・システ
ムはシステム中の任意の個所に存在するファイルをアク
セスするシステム中の異なるノードで走行する広範囲の
種々のアプリケーションを支援する真の分散システムで
ある。

第１図に示されている分散システムのためのデータ構造
は第８図に示され、そのデータ構造の要素は第９Ａ図乃
至第９Ｆ図に示されている。第１３図は局所即ちクライ
エント・システムに存在する代表的なディレクトリ・ツ
リー構造、第１４図は第１３図のクライエント・ツリー
構造及びクライエント・システムによってアクセスされ
る遠隔即ちサーバー・ディレクトリ・ツリー構造の例を
示す。第８図を参照するに、クライエント・ノードは遠
隔サーバー・ノードに存在するファイルにアクセスでき
る。このようなりライエンドはサーバーのファイルの１
つをマウントすることによってサーバーのファイルにア
クセスする。クライエント・ノードでは、遠隔マウント
動作によって形成されるデータ構造が次のようにして局
所のエンティティをマウントすることによって形成され
るデータ構造と比較される。局所的な場合と丁度同じよ
うに、遠隔マウントはクライエント・ノード（たとえば
、ブロック５４）中にｖｆｓを形成する。ｉノード表項
目はしかしながら、遠隔ファイルからのｉノード情報を
含まない。その代り、ｉノード表項目は代理（Ｓ）ｉノ
ードを含む。この代理ｉノードは遠隔ｉノードを表わし
ている。

サーバー・ノードで、あるデータ構造体が構成され、ど
のようにして遠隔メートがそのファイルを使用中である
かについての状態情報を記憶することが可能になる。さ
らに具体的に説明すると、各サーバーはダミイｖｆｓ（
たとえばブロック７１）によって、遠隔クライエントに
よって開かれたファイルを保持するｖｆｓを与えること
ができる。

ダミイｖｆｓはサーバーのファイル・ツリーの一部では
ない。遠隔ノードによって開かれている各ファイルにつ
いて、サーバーのダミイｖｆｓ中にはＶノード（たとえ
ば、ブロック７４）が存在する。

遠隔ノードによって開かれている各ファイルはサーバー
のｉノード表（たとえば、ブロック８５）中にｉノード
表項目を有する。このｉノード表の項目はサーバーにお
ける局所プロセスがファイルを開いたために存在するも
のと同じである。たとえば、遠隔が開いたために表中に
存在するブロック８４はサーバーにおける動作のために
表中に存在するブロック８８と同じ構造を有する。

クライエント及びサーバーがサーバー・ファイルについ
て通信する時は、ファイルを識別する方法が必要である
。これはファイル・ハンドルによって行われる。クライ
エントの要求によってサーバーが特定のファイルの宛先
を返答する時は（遠隔開放要求の場合）、このファイル
はファイル・ハンドルで識別される。ファイル・ハンド
ルは次のフィールド、即ち装置の番号、ｉノード番号及
びｉノード発生番号を含む。

ファイル・ハンドルの必要性を次のシナリオによって説
明する。クライエントがサーバーに要求して、その返答
としてファイル・ハンドルを受取ったものとする。クラ
イエントはこのファイル・ハンドルを記憶する。サーバ
ーにおけるあるアクティビティによってこのファイルが
削除され、ｉノード・スロットが他のファイルのために
再使用されているものとする。クライエントは記憶した
ファイル・ハンドルを使用してサーバーに要求する。サ
ーバーはファイル・ハンドルを受取り、新らしいファイ
ルについて動作を行う。この動作は受諾できない動作で
ある。

この欠点はｉノード発生番号の使用によって防止される
。ｉノード発生番号はｉノード中のフィールドとしてデ
ィスク上に記憶できる。サーバーがファイルを削除する
時、これはｉノード発生番号をインクレメントする。も
し要求がサーバーに達すると、ファイル・ハンドルが分
離され、装置番号と１ノ一ド番号を使用して、ｉノード
を探知する。次にファイル・ハンドルのｉノード発生番
号がｉノードのｉノード発生番号と比較される。

もしこれ等の番号が異なると、要求は拒否される。

クライエントが遠隔サーバー上に存在するファイルを開
きたい時には、ネットワーク転送機構を使用して、サー
バーとの接続を確立する。このファイルに関するその後
のトランザクション（たとえば、読取り、書込み等）は
この接続上を流れる。

ノードはその表中の項目（たとえばブロック７０）を使
用して、この遠隔ノードの現存する接続に関する情報を
記録する。

ネットワーク中の１つのノードが他のノードに要求して
それ自身のために遂行できる動作の数には制限がある。

これ等の動作はｄｆａ　　ｏｐｓ　　と呼ばれる。ノー
ドが他のノードを要求する時は、次の動作が生ずる。先
ず要求する側のノードがどのｄｆｓ動作を要求中である
かを指定し、この要求に適切なパラメータを含むメツセ
ージを添えて送る。次に受信側のノードがこの要求を受
取り、指定された動作を遂行する。最後に、受信ノード
はそのｄｆｓ動作に適した返答パラメータを含むメツセ
ージを送る。

局所ノード内のファイル・システムに発生するｖｎ　　
ｏｐｓとネットワーク上で発生するｄｆｓ　　ｏｐｓ間
には密接な相互関係が存在する。遠隔ファイル上の代表
的な動作は次の通りである。先ず、局所カーネルはファ
イルが遠隔もしくは局所のいずれで動作を受けているか
を知らないで、ｖｎ　　ｏｐを発生する。第２に、ファ
イルが遠隔ノードに存在するので、ファイル・システム
を具体化するコードは対応するｄｆｓ　　ｏｐをファイ
ルを保持するノードに送る。もしこのファイルが局所フ
ァイルである場合には、動作が遂行され、復帰パラメー
タが戻され、タスクが完了することに注意されたい。

第３に、ファイルを保持するノードはｄｆｓ動作要求を
受取り、その局所ファイル・システムに、対応するｖｎ
動作を遂行することを要求する。このｖｎ　ｏｐかもの
復帰パターンがｄｆｓ　　ｏｐのための復帰パラメータ
を構成するのに使用される。

第４に、要求したノードはサーバー・ノードからのｄｆ
ｓ　　ｏｐの返答を受取り、ｄｆ、ｓ　　ｏｐ復帰パラ
メータを使用し、元のｖｎ動作要求に対する復帰パラメ
ータを構成する。

この動作を、遠隔ファイルを局所ファイル上にマウント
し、ファイルへの経路をたどるシナリオで説明する。

最初のシナリオにおいて、クライエント−ノード中のア
プリケーション・プロセスがマウント・システム・コー
ルを発生して、サーバー−／−トのファイル゛’　／ｕ
　７ｇ　ａ　ｒ　ｐ　”を局所クライエント・ファイル
°’　／　ｅ　ｔ　ｃ　／　ｆ　ｏ　ｏ”上にマウント
する。

次のシナリオはこの要求をどのようにして達成されるか
を説明する。このシナリオは初期条件を表わす第１０図
、最終条件を表わす第１１図を参照して、次の仮定によ
って説明する。ブロック５１によって表わされたｖｆｓ
はクライエントのファイル・ツリーのルートの仮想ファ
イル−システムであり、含まれるすべてのディレクトリ
及びファイルは同一装置上にあるものとする。指示され
たディレクトリ中には次の項目が存在する。

サーバーのノードのディレクトリ ｉノード番号　　　　名前　　　　ｉノード番号２　　
　　　　　”ｕ”　　　　　　　１５１５　　　　　“
’ｇｏｒｐ”９２ ９２　　　　　”ｆｉｌｅ２”　　　　　ｔ５７クライ
エント・ノードのディレクトリ ｉノード番号　　　名前　　　　ｉノード番号２″ｅｔ
ｃ”　　　　　８６ ８６　　　　　°’ｆｏｏ”　　　　　７５マウント・
システム・コールを具体化するコードがルックアップｐ
ｎを呼出し、”　ｅ　ｔ　ｃ　／　ｆ　ｏ　ｏ　”上に
マウントされるファイル迄の経路に従う。この動作が完
了すると、ルー）　ｖｆｓ　（ブロック５１）は根ｖｆ
ｓ　（ブロック５１）へのポインタ、ｉノード７５のた
めのｉノード表項目（ブロック６１）へのポインタを有
する”　／　ｅ　ｔ　ｃ　／　ｆ　ｏ　ｏ　”のための
Ｖノード（ブロック５３）を含んでいる。

マウントされるファイルは遠隔ノード中に存在するので
、ｄｆｓマウント要求がサーバー・ノードに発生されて
、マウントされるオブジェクトへの経路として°ｕ　／
　ｇ　Ｏｒ　ｐ　”−を通過する。ｄｆｓマウント要求
を受取ると、サーバー・ノードはルックアップｐｎを呼
出して、マウントされるファイル°“／　ｕ　／　ｇ　
Ｏｒ　ｐ”への経路に従う。このルックアップ動作が完
了すると、サーバー・ノードの根ｖｆＳ（ブロック７１
）はこの根ｖｆｓへのポインタ及びｉノード９２のため
のｉノード表項目へのポインタを有する°“／　ｕ　／
　ｇ　Ｏｒ　ｐ　”のためのＶノード７４を含んでいる
。サーバーはｉノード７５（装置０、ｉノード９２）中
の情報を使用して、ファイル″／　ｕ　／　ｇ　Ｏｒ　
ｐ　”のためのファイル・ハンドルを構成する。サーバ
ーはこのファイル・ハンドルをｄｆｓマウント要求への
返答として戻し、Ｖノード及びｉノードを解放する。最
後に、クライエントはｄｆｓマウント要求に対する返答
としてのファイル・ハンドルを受取り、次のように新ら
しい仮想ファイル・システムを形成するのに必要な動作
を遂行する。

（、）　　新らしいｖｆｓ　　（ブロック５４）を形成
する。

（ｂ）　　とのｖｆｓのために、親ｖｆｓ　　（ブロッ
ク５４）へ戻すポインタ及びｖｆｓのルートｉノード（
ブロック６２）へのポインタを有するルートＶノード（
ブロック５５）を形成する。このｖｆｓのルート・ノー
ドは遠隔ファイルであるから、ルートＶノードからポイ
ントされるｉノードは代理ｉノードである。この代理ｉ
ノードはクライエントのｄｆｓマウント要求に応答して
サーバーが戻したファイル・ノ・ンドルを含んでいる。

（ｃ）　　ルートｖｆｓ（ブロック５１）中にカバーさ
れるＶノード（ブロック５３）中にマウント・オーバー
・ポインタを設定する。

（ｄ）　　新らしいｖｆｓ　　（ブロック５４）中に、
マウントするＶノード（ブロック５６）へのポインタを
設定する。

ここで上述の遠隔マウント（サーバーの／ｕ／ｇｏｒｐ
をクライエントの／　ｅ　ｊ　ｅ　／　ｆ　ＯＯ上にマ
ウントする）を実行した後にクライエントのプロセスカ
システム・コールを発生して、ファイル“′／ｅｔｃ／
ｆｏｏ／ファイル２”′に操作する。以下のシナリオで
は、ブロック番号は初期条件を表わす第１１図、及び開
放動作後のシステムの状態を表わす第１２図を参照する
。最初に、システム・コールを具体化するコードがルッ
クアップｐｎを呼出してその経路に従う。ルックアップ
ｐｎはルート仮想ファイル−システム（ブロック５１）
のルー）ｖノード（ブロック５２）から始まって、ｖｎ
ルックアップを呼出し、このＶノードによって表わされ
るディレクトリ・ファイル中の名前ＩＩ　ｕＩ＋をルッ
クアップする。ｖｎルックアップはディレクトリ中に名
前“°Ｕ″がｉノード１５と関連していることを見出す
。ｖｎルックアップはｉノード１５のためのルート仮想
ファイル・システム中にＶノード及びｉノードを構成し
、ルックアップｐｎにこのＶノードへのポインタを戻す
。ルックアップｐｎは再びｖｎルックアップを呼出して
、今度は名前°“ｆｏｏ”をｉノード１５によって識別
されるディレクトリ中にルックアップする。ｖＨルック
アップは指示されたディレクトリを読取り名前Ｎｆ００
１１がブロック６１中のｉノード７５に関連することを
知る。根のｖｆｓ（ブロック５１）中にはすでにこのｉ
ノード（ブロック６１）のためのＶノード（ブロック５
３）が存在するので、ｖｎルックアップはこのＶノード
へのポインタを戻す。ルックアップｐｎは従って次のｖ
ｆｓ（ブロック５４）へのマウント・オーバー・ポイン
タに従い、次に仮想ファイル・システムのルートＶノー
ド（ブロック５５）へのルートＶノード・ポインタに従
う。ここでルックアップｐｎは経路の次のエレメント（
ファイル２）のためのｖｎルックアップを呼出し、ブロ
ック５５及び名前ファイル２へのポインタのｖｎルック
アップを与える。探索しているディレクトリは遠隔ノー
ド中に存在し、クライエント代理ｉノード（ブロック６
２）中に記憶されているファイル・ハンドルによって識
別される。ｖｙ１ルックアップはｄｆｓルックアップを
ファイルを保持しているサーバーに発生してディレクト
リ及びルックアップされるべき名前（ファイル２）を識
別するファイル・ハンドルを送る。

サーバーはｄｆｓルックアップを受取って、このファイ
ル・ハンドルを使用して読取られるべきディレクトリを
識別し、ｖｎルックアップを発生してこのディレクトリ
中の名前ファイル２を探索する。ｖｎルックアップはｉ
ノード６７のためのダミイ仮想ファイル・システム中に
Ｖノード及びｉノードを構成する。このＶノードのため
のポインタをルックアップｐｎに戻す。ｄｆｓルックア
ップはｖｎルックアップによって戻されたデータ構造中
の情報を使用してｉノード６７によって識別さ　、れる
ファイルのためのファイル・ノ為ンドルを構成する。サ
ーバーはこのファイル・ハンドルをｄｆｓルックアップ
要求に対する返答としてクライエントに戻し、Ｖノード
及びｉノードを解放する。クライエント中ではＶノード
（ブロック５５）及び代理ｉノード（ブロック６３）が
見出されたファイルのために形成される。ファイル２は
経路の最後の部分であるから、ルックアップｐｎはその
呼び手に発見されたＶノード（ブロック５５）へのポイ
ンタを戻す。システム・コールを具体化するコードはこ
こでこのファイルに対して要求されていた動作を遂行す
る。

各サーバーはノード表と呼ばれる構造中にサーバーに接
続される遠隔ノードのリストを保持している。ノード表
は他のノードに対する接続についての情報及びクライエ
ントのキャッシュ・ディレクトリ情報についての情報を
含む。サーバーによってサーバーのディレクトリの項目
がキャッシングすることが予想されているノードはノー
ド表中にそのようにマークされる。サーバーはクライエ
ントカキャッシング中のディレクトリ項目を確実には知
らず（たとえばクライエントのキャッシュは第１のサー
バーの項目のすべてを押出して他のサーバーの項目が充
満されている）、サーバーは消極的で、要求したクライ
エント・ノードからのルックアップが、そのクライエン
トにキャッシュされた項目を生じたものと信じている。

サーバー中のディレクトリに変更があると、サーバーは
ｄｆｓ　　ｆｓアドバイスｒｐｓを使用して、そのサー
バーのディレクトリの項目をキャッシュしていると信じ
ているすべてのクライエントに、サーバー中の一部のデ
ィレクトリの項目が変更されたことを知らせる。サーバ
ー中のディレクトリに変更があったことを示すｄｆｓ　
　ｆｓアドバイスｒｐｓメツセージはディレクトリの項
目をキャッシングしていることが予想されていることを
示すノード表中のすべてのノードに送られる。ｄｆｓｆ
ｓアドバイスｒｐｓをクライエント・ノードに送った後
に、クライエント・ノードのためのノード表項目が更新
され、そのクライエントがサーバーのディレクトリ項目
をキャッシュしていないことが示される。このよりなｄ
ｆｓ　　ｆｓ　アドバイスｒｐｓｋ受取ったクライエン
トはｄｆｓ　　ｆｓアドバイスｒｐｓを送ったサーバー
中のディレクトリに対応するすべての項目をそのキャッ
シュから除去する。サーバーによってクライエントにｄ
ｆｓ　　ｆｓアドバイスｒｐｓが送られたサーバーはこ
のクライエントからの次のルックアップｒｐｓを受取る
迄は追加のｄｆｓ　　ｆｓアドバイスｒｐｓをクライエ
ントに送らない。クライエントからルックアップｒｐｓ
を受取ると、サーバーはそのクライエントのためのノー
ド表項目にディレクトリ項目をキャッシング中としてマ
ークする。サーバーのノード表は固定サイズのものでよ
い。利用できるスペースがな（て新らしいクライエント
をノード表に追加したい場合には、接続使用カウントが
０である表中の古い項目はこのクライエントにｄｆｓ　
　ｆｓアドバイスｒｐｓを送ることによって除去できる
。

このようにして、サーバーの最も新らしいユーザだけが
ディレクトリの項目をキャッシュする。ｄｆｓｆｓアド
バイスｒｐｓを受取ることによって、キャッシュを除去
する以外に、クライエントはもはやサーバーから必要な
ｄｆｓ　　ｆｓアドバイスｒｐａを受取ることがないの
で、サーバーのｎｉｄ　（ノード識別）接続が標準以下
（パッド）とマークされた時、即ちｎｉｄのための良好
（グツド）な接続が除去された時は、サーバーのｎｉｄ
のためのすべての項目をディレクトリ・キャッシュから
除去する。

クライエントがディレクトリ項目をキャッシュしている
ことを示すノード表中の項目はサーバーとエントリのク
ライエント間の接続の使用を示していす、接続の使用の
カウントをインクレメントできない。同じように、クラ
イエントのキャッシュ中にあるサーバーのディレクトリ
・データはその使用カウントがインクレメントされる対
応する接続を生じない。従って、クライエント及びサー
バー間の接続はクライエントがサーバーのディレクトリ
の項目を現在キャッシングしているというだけでは保持
できない。０になった使用カウントを有する接続を除去
する前に、クライエントがサーバーのディレクトリ項目
をキャッシュすることが予想されるならば、サーバーは
接続の他端にあるクライエントにｄｆｓ　　ｆｓアドバ
イスｒｐｓを送る。接続が失われても重大な問題は生じ
ない。接続がないとサーバーはクライエントに関するこ
とを忘れる。クライエントは標準以下の接続を発見する
時にそのキャッシュを除去することに注意されたい。で
きるだけ早く接続が標準以下であることを発見するため
に、クライエントは空のＲＰＣ。

即ち何ごとも伝えないが、接続使用カウントが０である
場合でも、最近使用されていす、通信プロセスが接続状
態に保持されていることを示す任意の接続を介して２つ
のノードが依然ＲＰＣを送受できるという事実を示すＲ
ＰＣを送る。

次の第１表はサーバー〇ノード表中に現われる情報の例
を示す。ノード表中の各ノードｉｄに対して、識別され
るノードがディレクトリ情報をキャッシュできることを
示す簡単なフラグ（フラグがＹ）もしくは識別されるノ
ードが任意の情報をキャッシュしないことを示す簡単な
フラグ（フラグがＮ）が存在する。この例では、ノード
５は任意のディレクトリ情報をキャッシュしていす、従
って、サーバーにおいてディレクトリが変化した時もｄ
ｆｓ　　ｆｓアドバイスｒｐｓは必要でないが、ノード
２０はディレクトリの情報をキャッシュ中であると信じ
られるので、サーバーのディレクトリが改名されるか削
除されたサブディレクトリを有する時はｄｆｓ　　ｆｓ
アドバイスｒｐａを送らなければならない。

第　　　１　　　表 ノードｉｄ　　キャッシング中？　他の接続情報第２表
はディレクトリ・キャッシュ中に記憶される種類のデー
タの例を示す。この例では３つの異なるノード、即ちｉ
ｄが１２．２０及び５２を有するノードが情報をキャッ
シュ中であることに注意されたい。ノード１２の場合に
は同じ名前”　ｂ　ｉ　ｎ″”を有する２つの項目が存
在する。この事はノード１２中の２つの異なるディレク
トリ中にこの名前”ｂｉｎ”′が生ずるので可能である
。この場合はおそら（Ａ　Ｉ　Ｘ　”Ｍシステム中の２
つの共通ディレクトリである／　ｂ　ｉ　ｎ及び／　ｕ
　ｓ　ｒ　／　ｂ　ｉ　ｎを表わす、ファイル・ハンド
ル１７７及び１２３を有するディレクトリが存在する。

ツリー要素、ノードｉｄ１ディレクトリ・ファイル・ハ
ンドル及び名前は一緒になってディレクトリ・キャッシ
ュを探索する時の探索キイを形成する。ディレクトリ・
キャッシュの探索をスピード・アップするために、使用
される実際のデータ構造はより複雑になっている。

高速探索のための情報を構成するための普通に使用され
ている方法のうち任意のものが使用できる。

第６表及び第１７図に示されている方法はディレクトリ
・キャッシュの探索をスピード・アップするのにハツシ
ュ表を使用している。

第６表は、ディレクトリ・キャッシュの項目が上述の４
つのフィールドに加えて次の２対のリンク・フィールド
を使用することを示す。（１）項目を前後リストと呼ぶ
２重リンク・リストにリンクするのに使用する前後のフ
ィールド及び（２）すべての項目を新旧リストと呼ばれ
る１つの追加の２重リンク・リストにリンクするのに使
用される新、旧フィールド。２重リンク・リストは挿入
及び除去を簡単に行うのに使用される。項目をリストの
始めもしくは終りに移動するためには、項目は現在の位
置から取出されてリストの始めもしくは終りに挿入され
る。各項目は２つのリスト、即ち複数の前後リストのう
ちのある１つ及び単一の新旧リストの上に存在する。

第　　　６　　　表 第１７図はこれ等の項目のリストが完全なディレクトリ
・キャッシュ中に組織化される方法を示す。リストのす
べては２重にリンクされているが、図面を明瞭にするた
めに、順方向リスト・ポインタしか、示されていない。

最新ポインタは新旧リストの始めを指示し、最旧ポイン
タは同じリストの終りを指摘している。ノ・ツシュ表は
前後リストの各々の始めへのポインタを含んでいる。

ハツシュ機能は任意のノードｉｄ１ディレクトリ・ファ
イル・ハンドル及び経路名前部分をノ・ツシュ表へのイ
ンデックスにハツシュするものとじて定義され易。ハツ
シュ表中の同じ位置にハツシュするすべての項目はハツ
シュ表中のこの位置のポインタによって指摘される同じ
前後リスト中で互に連結される。

本発明のディレクトリ像キャッシング動作を支持するの
に必要な次の４つの異なる動作が存在する。すなわち、
（１）サーバーのディレクトリ更新中のキャッシュの無
効化、（２）サーバーでルックアップ要求を処理中にキ
ャッシング中としてノードをマークする、（３）遠隔ル
ックアップ中にクライエントのディレクトリ・キャッシ
ュの使用、及び（４）クライエントが受取ったｄｆａ　
ｆｓアドバイスｒｐｓもしくはクライエントとサーバー
間の接続の故障に応答してキャッシュから項目を除去す
ることである。本明細書の説明はサーバーもしくはクラ
イエントとしてのノードの役割に焦点があてられるが、
多（のノードはあるファイルについてはクライエントと
して、他のファイルについてはサーバーとしての両方の
働きをする。従ってノードは一般にクライエント及びサ
ーバー動作の両方を支援する。

動作（１）：サーバーにおけるディレクトリ更新中のキ
ャッシュの無効化は次のように行われる。

もし項目が除去されるか再命名されつつある時に、 もし項目がサブディレクトリで単なるファイルでない時
は、 ノード表中の各行について もしこの行のクライエントがキャッシング中なら、 ｄｆｓ　　ｆｓアドレスをこの行のクライエントに送る
。

このクライエントを非キャッシングと してマーク ここで第１５図を参照するに、本発明のディレクトリ・
キャッシング技術に必要な動作を遂行する際のサーバー
における動作の流れ図が示されている。第１５図の動作
はクライエントのディレクトリ上にマウントされるファ
イル・システムの部分を有するサーバーで、ディレクト
リの内容が更新される名産に実行される。

段階２００で、テストがなされて、サーバーのディレク
トリ中の項目が除去もしくは再命名されつつあるかどう
かが判断される。除去中でなければこの動作は終る。そ
れは追加のディレクトリの内容に関する情報がサーバー
からクライエントに送り戻される必要がないからである
。段階２００で、サーバー・ディレクトリ中の項目が除
去もしくは再命名されつつあることがわかると、段階２
０１において、このサーバーのディレクトリの項目がキ
ャッシュ可能なものであるかどうかを判断するテストが
なされる。この項目はもしこれがすブディレクトリであ
るならばキャッシュ可能であり、単にファイルであるな
らばキャッシュ可能でない。項目がキャッシュ可能でな
い時には、動作はこの時点で終る。

項目がキャッシュ可能ならば、動作は段階２０２に進み
、この時点でノード表（第１表）の最初の行がアドレス
される。段階２０３でノード表中のこの行中のデータが
テストされ、この行に関連するクライエントがこのサー
バーのディレクトリ構造に関連する情報をキャッシング
中であるかどうかが判断される。クライエントがサーバ
ーのディレクトリ構造の任意の部分をアクセスした場合
はキャッシング中である。もしクライエントがキャッシ
ング中であるならば、段階２０４でｆｓアドバイス・メ
ツセージがこの行に関連するクライエントに送られ、ク
ライエントに対してこのサーバーに関連するそのディレ
クトリ・キャッシュ情報を消去するようにアドバイスす
る。段階２０５において、ノード表がマークされて、こ
のクライエントがもはやサブディレクトリ情報をキャッ
シュ中でないことが示され、段階２０６でノード表がチ
ェックされノード表中にさらに行が存在するかどうかが
判断される。これ以上性が存在しない時には、動作が終
りもしそれ以上の行がノード表中に存在する時には、段
階２０７で、ノード表中の次の行がアクセスされる。次
に動作は上述した段階２０３に戻る。もし段階２０６で
行のクライエントがキャッシング中でないことが見出さ
れると、動作は段階２０４及び２０５をバイパスして段
階２０６をジャンプし、ノード表中にさらに行が存在す
るかどうかが判断される。

従って、この特定の実施例ではサーバーにおいてディレ
クトリ構造に変更が生じた時には、クライエントはサー
バーに関連するすべてのキャッシュされたディレクトリ
情報を消去するようにアドバイスされる。代替実施例は
変更された特定の経路に関連するキャッシュされた項目
だけを消去するようにクライエントにアドバイスするこ
と、もしくはクライエントにこの経路に対する実際の変
更についてアドバイスすることを含む。

動作（２）ニルツクアップ要求中にディレクトリ情報を
キャッシュ中としてノードにマークする動作は次のよう
に遂行される。

あるクライエントによって要求されるルックアップ要求
を遂行する。

もし結果がディレクトリのためのファイル・ハンドルで
あるならば、 ／　クライエントはこれをキャッシュできる　／要求し
たクライエントのためのノード表の項目を見出す クライエントをディレクトリ情報をキャッシュ中として
マークする。

次に第１８図を参照すると、本発明のディレクトリ・キ
ャッシング技術に必要な動作を遂行するサーバーの動作
の詳細な流れ図が示されている。

第１８図に説明された動作は、以後サーバーとして働く
ノードによってルックアップ要求が受取られる度に実行
される。この要求はクライエントとして動作しているあ
る他のノードから受取られる。

段階２２０で、ルックアップ要求はディレクトリ・キャ
ッシング中でないものとして遂行される。

段階２２１で、任意の返答をルックアップを要求したク
ライエントに戻す前に、ルックアップの結果を調べる。

もしルックアップの結果である、ファイル・ハンドルが
クライエントによってキャッシュできるもの、即ちディ
レクトリのためのファイル・ハンドルである場合には、
実行は段階２２２に進む。ルックアップの結果が、通常
のファイルのためのファイル・ハンドルである時には、
クライエントはこの結果をキャッシュせず、動作は終る
。

この結果がキャッシュできる時は、動作は段階２２２に
進み、この時点で、要求を行ったクライエントのための
ノード表項目が見出される。段階２２６において、この
ノード表の項目が更新されて、対応するクライエントは
現在ディレクトリ情報をキャッシュ中であることが示さ
れる。段階２２３の後に動作が終了する。

従って、この特定の実施例では、サーバーは単に、クラ
イエントがあるディレクトリ情報をキャッシュ中である
と信じられるかどうかを示すプール代数値を記録する。

遠隔ルックアップ中のクライエントのディレクトリ・キ
ャッシュを使用する動作（３）は次のように動作する。

／＊経路の名前の分析中は、あるディレクトリは常に次
の経路の名前の要素の探索が生ずるディレクトリである
。最初、このディレクトリは根のディレクトリであるか
原経路に依存する現在のワーキング・ディレクトリであ
る。ルックアップｐｎにおける経路の名前の分析中に、
探索が生ずるディレクトリはそのＶノード・ポインタに
よって識別される。

＊／ ／＊これは遠隔ルックアップのための手段であるから、
探索さるべきディレクトリは遠隔ディレクトリである。

＊／ 一致した項目のためのブイレフ）　ＩＪ・キャッシュを
探索する。

もし項目が見出されると、 項目を新旧リストの始めに移動する。

そうでない時は ｄｆｓルックアップｒｐｓを使用して遠隔ルックアップ
を遂行する。もしルックアップの結果がキャッシュ可能
であると、 結果をディレクトリ・キャッシュの新旧リストの開始点
に挿入する。

第１９図を参照するに、本発明のディレクトリ・キャッ
シング技術に必要な動作を遂行する際のクライエントの
動作の詳細な流れ図が示されている。第１９図に示され
た動作はクライエントが遠隔ディレクトリ中の名前をル
ックアップしなければならない度に実行される。

段階２３０において、ディレクトリ・キャッシュが探索
される。この段階は以下より詳細に説明する。この探索
の結果は段階２３１でテストされる。もしこの探索の結
果が遠隔ブイレフ）　ＩＪにルックアップされたこの名
前のためのファイル・ハンドルであることを示すと、動
作は段階２３２に進む。段階２６２で、段階２３０中で
見出されたディレクトリ・キャッシュ項目が新旧リスト
の前面（一番若い方）に移動する。探索される度に項目
をリストの始めに移動することによって、最近使用した
項目がキャッシュ中に留まる可能性が生じ、最近はとん
ど使用されない項目は破棄される項目となる。リストは
２重にリンクされているので、新旧リストの始めに項目
を移動することは容易である。段階２３２の後に、動作
が終る。

段階２３１において、段階２３０の探索が失敗したこと
が判断されると、動作は段階２３３に進む。段階２３３
で、遠隔ルックアップを遂行するのに必要な動作（ｄｆ
　ｓ　）が遂行される。段階２３４で、段階２３３で遂
行された遠隔ルックアップの結果が検査される。この結
果がキャッシュ可能でない時、即ち結果が通常のファイ
ルのファイル・ハンドルである時は、動作が終る。

段階２３６中に戻って、ファイル・ハンドルがディレク
トリのファイル・ハンドルである時は、段階２３４はこ
のファイル・ハンドルがキャッシュ可能であると判断し
、動作は段階２３５に進行、する。段階２３５で、新旧
リストの終りにある項目が除去される。この項目はキャ
ッシュ中で最近はとんど使用しない即ち最も古い項目で
ある。段階２３６で、この項目はその特定の前後リスト
から除去される。段階２６７で段階２３０の探索中に使
用したノードｉｄ１ディレクトリ・ファイル・ハンドル
及び名前の値がハツシュ表中にハツシュされ、このハツ
シングの結果を使用してディレクトリ・キャッシュ・ハ
ツシュ表をインテックスし、指摘された前後リストを見
出す。段階２３８において、段階２３５中において得た
項目を段階２３７中で決定された前後リスト中に挿入し
、次にこの項目を段階２３０で得たノードｉｄ、デイレ
ク）　ＩＪ・ファイル・ハンドル及び名前の値並びに段
階２３３によって戻されたファイル・ハンドルで初期設
定する。段階２３８の後に、動作が終る。

クライエントで受取ったｄｆｓ　　ｆｓアドバイスｒｐ
ｅに応答してキャッシュから項目を除去する動作（４）
は次のように進行する。

／”ｄｆｓｆｓアドバイスｒｐｓを受取ることにより　
／ 新旧表中の各ディレクトリ・キャッシュ項目について、 もし項目がｄｆｓ　　ｆｓアドバイスｒｐｅの送り手の
ノードｉｄと同じノードｉｄを有するならば、 項目を新旧リストから除去して、項目を新旧リストの終
りに挿入し、 項目中のノードｉｄ値を０のノードｉｄにセットする。

ＡＩＸシステム中のどの実際のノードも０のノードｉｄ
を有することはないので、ディレクトリ・キャッシュの
項目のノードｉｄを０に初期設定することによって探索
中の項目との一致の成功が防止される。項目を新旧リス
トの終りに移動することによって、項目は新らしい値を
キャッシュすべき時に再使用可能になる。

第１６図を参照すると、本発明のブイレフ）　ＩＪ・キ
ャッシング技術に必要とされる動作を遂行する際のクラ
イエントの動作（４）の詳細な流れ図が示されている。

第１６図に示した動作はクライエントがｄｆｓ　　ｆｓ
アドバイスｒｐｅを受取る毎に実行される。

段階２５０において、新旧リストの始めの項目が見出さ
れる。この項目は第１７図で最新と名前の付されたポイ
ンタによって指摘される。段階２５１において、新旧リ
スト中の次の項目へのポインタが保管される。リストの
終りでは、このポインタは空である。段階２５２におい
て、この項目が検査される。もし項目のノードｉｄがｄ
ｆｓ　　ｆｓアドレスｒｐｅの送り手のノードｉｄと同
じならば（除去すべきものならば）、段階２５６．２５
４．２５５及び２５６に進む。そうでない時、即ちノー
ドｉｄが異なる時は、段階２５７に進む。

段階２５３で、この項目は新旧リストから除去される。

段階２５４でこの項目が属する前後リストから除去され
る。段階２５５でこの項目が新旧リストの終りに挿入さ
、れる。段階２５６でこの項目のノードｉｄが０にセッ
トされる。段階２５３．２５４．２５５及び２５６はア
クティブなキャッシュの要素から項目を効果的に除去し
、項目を再使用に利用可能にする。勿論、新旧リストの
終りへの道を見出した項目は、この過程によってここに
置かれなかった場合でも再使用に利用可能となる。項目
は探索される各席に新旧リストの始めに移動するので、
最近はとんど使用されなかった項目だけがリストの終り
に移動する。

段階２５７において、段階２５１で保管されたポインタ
が検査される。もしこれが項目へのポインタならば（さ
らに項目があるので）、動作は段階２５８に進行する。

段階２５８で、この項目は検査を受けている現在の項目
となり、動作は段階２５１に戻って続けられる。もし段
階２５７で段階２５１で保管したポインタが空であるこ
とがわかると、リストの終りに到達しているので、動作
が終る。

遠隔ルックアップ中にクライエントの側でディレクトリ
・キャッシュを使用する動作（６）はディレクトリ・キ
ャッシュの探索を必要とする。この探索は次のように進
行する。

／＊探索はディレクトリへの■ノード・ポインタ、ディ
レクトリを含むノードのためのノードｉｄ及び経路の名
前の一部である名前を使用して開始する。

＊／ ディレクトリのためのＶノード・ポインタをフアイル・
ハンドルに変換する。ファイル・ハンドルは代理ｉノー
ド中にあり、代理ｉノードはＶノード春ポインタによっ
て指摘されるＶノード構造のメンバによって指摘される
。

ノードｉｄ１ディレクトリ・ファイル・ハンドル及び名
前を使用してディレクトリ・キャッシュ・ハツシュ表中
にハツシュする。

計算されたハツシュによってインデックスされたハツシ
ュ表の要素によって指摘される前後リスト上の各項目に
ついて、 もし項目中のノードｉｄ１ディレクトリｅファイル・ハ
ンドル及び名前が探索しているこれ等と一致すると、 その項目中に発見されたファイル・ハンドルを戻す。

／＊この時点で一致が見出されないと、キャッシュ中に
は一致は存在しない。

＊／ 非発見を戻す。

第２０図を参照すると、本発明のディレクトリ・キャッ
シング技術によって必要な探索動作の詳細な流れ図が示
されている。第２０図の動作は第１９図の動作である段
階２６０が遂行される度に遂行される。。

この動作はノードｉｄ１ディレクトリへのＶノード・ポ
インタ及び名前（経路の名前の一部）によって開始する
。段階２７０で、ディレクトリへのＶノード・ポインタ
はファイル・ハンドルに変換される。これはＶノード・
ポインタによって指摘された構造を調べることによって
行われる。ファイル・ハンドルは代理ｉノード中にあり
、代理ｉノードはＶノード・ポインタによって指摘され
るＶノード構造のメンバによって指摘される。段階２７
１において、ノードｉｄ、段階２７０において決定され
たディレクトリ・ファイル・ハンドル及び名前がハツシ
ュされる。段階２７２で、このハツシュ値はディレクト
リ・ハツシュ表中にインデックスして前後リストの１つ
へのポインタを得るのに使用される。この特定のハツシ
ュ値のための前後リストが存在しない場合には、ノ・ツ
シュ表中に見出される値は空である。

段階２７３で、段階２７２中もしくは段階２７５中に見
出されるその後の繰返しにおいて見出されるポインタが
検査され、すべての項目が処理されたかどうかが判断さ
れる。もしすべての項目が処理されていると、動作は一
致キャッシュ項目が見出されなかったという表示によっ
て終る。もし少なくとも、処理さるべき１つ以上の項目
が存在すると、即ちポインタが空でないと、処理は段階
２７４に進む。

段階２７４において、項目が検査される。もしそのノー
ドｉｄ１ディレクトリ・ハンドル及び名前フィールドが
段階２７１中に存在される探索要求のこれ等と一致する
と、動作は終り項目中に見出されたファイル・ハンドル
が戻される。もし一致しないと、動作は段階２７５に進
む。段階２７５で、検査すべき次の項目へのポインタは
現在の項目の次と命名されたフィールドから得られる。

勿論、リストの終りには、次の項目は存在しない。

このことは次の段階２７３で判断される。

ファイルはしばしば再命名され除去される。上述したば
かりの方法では、サーバーはこれ等の共通の動作の１つ
が発生するたびに、ディレクトリの項目をキャッシュす
るすべてのクライエントにｄｆｓ　　ｆｓアドバイスｒ
ｐｓを送ることが要請される。このことはクライエント
・ノードがキャッシュされた情報の恩恵を長時間受けら
れないようにする。これ迄に説明された方法の増強はこ
の問題をなくする。

この増強方法はクライエント・ディレクトリ・ファイル
・ハンドルだけをキャッシングし、非ディレクトリ（通
常）ファイル・ハンドルをキャッシングしないものであ
る。非ディレクトリ・ファイルはしばしば削除もしくは
再指名されるが、ディレクトリ・ファイルはめったに削
除もしくは再指名されない。クライエントでディレクト
リのファイルの名前だけをキャッシュし、サーバーのデ
ィレクトリが削除もしくは再指名される時にだけ、クラ
イエントにｆｓアドバイス台メツセージを送ることによ
って、クライエントはキャッシュされたデータの無効化
が生ずる前にキャッシュした情報から長時間恩恵をこう
むることができる。たとえば経路の名前”　／　ａ　／
　ｌ）　／　ｃｎに従っであるファイルに達すると、ク
ライエントはａ″をその関連ファイル・ハンドルととも
にキャッシュし、Ｉｌ　ｂｌｌをその関連ファイル・ハ
ンドルとともにキャッシュし、キャッシュ゛１１はその
関連ファイル−ハンドルとともにキャッシュしない。通
常のファイルを指名する任意の経路の指名の最後の要素
をキャッシュしないことには否定的な効果もある。サー
バーのノード表情報はより細か（保持できる。補強手段
はサーバーのノード表中に各クライエントについてクラ
イエントがキャッシングするディレクトリのリストを保
持することである。

次にサーバー中のディレクトリへの変更によって、ｄｆ
ｓ　　ｆｓアドバイスｒｐｓが変更されたディレクトリ
の項目をキャッシングする可能性のあるクライエントに
送られ、クライエントが受取ったｄｆｓｆｓアドバイス
によって変更されたディレクトリに対するキャッシュ項
目だけが除去され、そのサーバーのだめの項目のすべて
は除去されない。

Ｆ　発明の効果 本発明に従い、ネットワーク中のファイル・ディレクト
リの情報をキャッシュしてその有効性を保証し、変更が
なされない期間中はこの情報を不必要に又非効率的に更
新しない能力を与えることによってネットワーク中のフ
ァイル・ディレクトリをアクセスする際の動作効率が太
いに改善される。

【図面の簡単な説明】

第１図は本発明に従う分散データ処理システムのブロッ
ク図である。第２図は本発明の方法を動作させるように
設計される従来の代表的な分散データ処理システムのブ
ロック図である。第３図は代表的な独立型プロセッサ・
システムのブロック図である。第４図はプロセッサ上で
走行しているアプリケーションによって読取りシステム
・コールが発せられる時にオペレーティング・システム
によって遂行される段階を示した流れ図である。 第５図は本発明を支援するオペレーティング・システム
によって遂行される局所ノードにおけるファイル動作に
至る経路に従うシナリオを示したデータ構造のブロック
図である。第６図及び第７図はオペレーティング・シス
テムによって遂行される時の、局所ノードにおけるマウ
ント・ファイル動作のためのシナリオの前及び後の条件
を示したデータ構造を示したブロック図である。第８図
は第１図に示した分散ファイル・システムのためのデー
タ構造のブロック図である。第９Ａ図、第９Ｂ図、第９
Ｃ図、第９Ｄ図、第９Ｅ図、及び第９Ｆ図は第８図に示
したデータ構造に使用されている要素の部品の働きを示
すブロック図である。第１０図、第１１図及び第１２図
はオペレーティング・システムによって遂行される時の
分散されるシステムの局所及び遠隔ノードにおけるマウ
ント・ファイル動作及び経路に従う動作のためのシナリ
オを示したデータ構造のブロック図である。第１３図は
局所即ちクライエント・システムに存在する代表的なデ
ィレクトリ・ツリー構造の図である。第１４図は第１６
図のクライエント・ディレクトリ・ツリー構造及びクラ
イエント・システムによってアクセスするのに使用され
る遠隔即ちサーバーのディレクトリ・ツリー構造を示し
た図である。第１５図は本発明の改良ディレクトリ・キ
ャッシング技術を使用するシステム中でディレクトリを
更新する際のサーバーにおける動作を示した流れ図であ
る。第１６図は本発明の改良されたディレクトリ・キャ
ッシング技術を使用するシステム中の、ｄｆｓ　　ｆｓ
アドバイスに応答するクライエントの動作を示した詳細
な流れ図である。第１７図はディレクトリ・キャッシュ
の内容を探索するのに使用するハツシュ表技術を示した
図である。第１８図は本発明の改良ディレクトリ・キャ
ッシング技術を使用したシステム中のｄｆｇルックアッ
プｒｐｅ要求に応答するサーバーの動作の詳細な流れ図
である。第１９図は本発明の改良ディレクトリ・キャッ
シング技術を使用するシステム中で遠隔ディレクトリ中
のファイルの名前をルックアップ中のクライエントの動
作の詳細な流れ図である。第２０図は本発明のディレク
トリ・キャッシュの探索動作の詳細な流れ図である。 １・・・・分散ネットワーク・システム、２Ａ１Ｂ。 Ｃ・・・・ディスク、６・・・・ネットワーク、４Ａ、
Ｂ。 Ｃ・・・・アプリケーション、５・・・・ファイル、１
０Ａ、Ｂ、Ｃ・・・・処理システム、ＩＩＡ、ＢｌＣ・
・・・オペレーティング・システム、１２Ａ、Ｂ、Ｃ・
・・・カーネル・バッファ、１３Ａ、ＢｌＣ・・・・プ
ロセス。 フライ１ント ｖｆｓ 局ＰＦｒ／を隔 サーＩぐ− −りねり− クライエニド 局所／を隔 サーノぐ− □第１１図 局所／Ｌ クライエシト 廿−八“− 第１２図

Claims (1)

1. 【特許請求の範囲】 第１のシステムによる第２のシステムのディレクトリ構
   造に関する質問に応答して上記第１のシステムが上記第
   ２のシステムのディレクトリ経路情報の第１の単位を保
   管するデータ処理システムのネットワークのためのディ
   レクトリのキヤッシング方法において、 上記第２のシステム中のディレクトリ構造のその後の変
   更に応答して、上記第２のシステムから上記第１のシス
   テムに自動的に通知を送る段階を有する、 データ処理システム・ネットワークのためのキヤッシン
   グ方法。