JP2007080240A - ファイル割り当てテーブルのアクセス手法 - Google Patents

Abstract

【課題】ファイル割り当てテーブル（FAT）をアクセスする手法を開示する。
【解決手段】本発明の一特徴によれば、外部記憶装置からのFATがインタフェースにおいて得られた後、外部記憶装置内のファイルに割り当てられるクラスタのリンク・リストが抽出される。クラスタのリンク・リストにおけるクラスタの隣接領域がパック・レコードに圧縮され、各々は、第１のクラスタの位置情報と、クラスタの隣接領域の長さ情報とを含み、パック・レコードは、ランダム・アクセス・メモリに順番に記憶される。外部記憶装置内のFATへのアクセスをインタフェースが管理することに依拠することによって、機器におけるプロセッサは、アクセス要求のみを送り、よって、FATをアクセスする間に他のタスクを行うよう解放される。
【選択図】図８

Description

本発明は、データ処理に関し、特に、ファイル割り当てテーブルを更に効率的に管理する装置及び方法に関する。

FATファイル・システムは、周知であり、内容を本明細書及び特許請求の範囲に援用する、IBMによる西暦1988年公表のIBM DISK OPERATING SYSTEM TECHNICAL REFERENCEをはじめとするいくつかの文献に記載されている。簡潔に述べれば、FATファイル・システムでは、ディスクが512バイトのセクタのクラスタに分割される。ファイルがファイル長によって1つ又は複数のクラスタに記憶される。ディスクは、ブート・レコードと、ファイル割り当てテーブル（FAT）と、ルート・ディレクトリと、サブディレクトリ及びファイルを含むデータ領域とを更に含む。ディレクトリは、ツリー構造のディレクトリ・システムである。特定のファイルは、それがあるドライブと、ディレクトリ・パスと、ファイル名、例えば、c:/dir1/dir2/filename.ext、を規定することによって探索される。

図１は、FATファイル・システムのディスク形式の構成図を示す。次にFATファイル・システムを簡単に説明する。FATファイル・システムは、FAT割り当てテーブル（FAT）を中心に展開する。各論理ブリュームは、それ自体のFATと関連付けられ、FATは、2つの重要な役目を担う、すなわち、割り当て装置のリンク・リストの形式でボリューム上のファイル毎の割り当て情報を含み、作成又は拡張されるファイルへ割り当てるうえで自由状態にある割り当てクラスタを示す。ディスクがFATファイル・システムによってフォーマッティングされる場合、ブート・セクタはセクタ0に書き込まれる。これには、1つ又は複数のファイル割り当てテーブルが続く。各ファイル割り当てテーブルは、フォーマッティングされたディスクの1つ又は複数の定義可能なFAT記憶装置上に物理的に配置される。定義可能なFAT記憶装置は通常、外部ディスク記憶装置上の512バイトのセクタであるが、FAT記憶装置の容量は、256バイトや1024バイトなどのように、512バイトを上回っても下回ってもよい。ファイル割り当てテーブルにはルート・ディレクトリが続く。ルート・ディレクトリにはボリューム・ファイルが続く。ブート・セクタは、ブート・パラメータ・ブロックすなわちBPBとして表す領域におけるボリューム、ドライブ番号及びボリュームID、FAT毎セクタ数、更にはブートストラップ・ルーチンなどの種々の記述情報を含む。

ファイル割り当てテーブルは、ディスク上の割り当て可能クラスタに直接相当するフィールドに分割される。第１の２つのFATエントリは予約されており、残りのFATエントリは、相当するディスク・クラスタの使用を記述する。ルート・ディレクトリにおける各ファイルのエントリは、FATへのエントリ・ポイントとして用いる、そのファイルに割り当てられる第１のクラスタの番号を含む。そのエントリ・ポイントから先は、各FATフィールドは、クラスタ終了マークに達するまでの、ファイルにおける次のクラスタの番号を含む。図２は、ファイルに割り当てられるクラスタのリンク・リストを特に示す、ファイル割り当てテーブル部分の例を示す。

FATシステムは、パソコン、ノートブック・コンピュータに用いられているだけでなく、ディジタル音楽プレイヤ及びカメラ、携帯情報端末(PDA)、ビデオカメラ、携帯電話機等などの特定の比較的小型の消費者向け電子製品にも用いられている。一般的に、ハード・ディスク、メモリ・カードや外部機構装置に記憶されているファイルをアクセスする場合、FATは、コンピュータのROMや消費者向電子製品のバッファ記憶装置にまず読み込まれなければならない。FATの情報によって、中央処理装置（CPU）は、外部記憶装置上に記憶されている所望のファイルをアクセスする旨の適切なアクセス・コマンドを記憶装置に送る。

FATは、通常用いられるパソコン（PC）やノートブック・コンピュータに常時確保するのに十分容量が小さいものであり得る。しかし、FATは、一部の比較的小型の消費者向電子製品（例えば、PDA）のバッファ記憶装置に常時保持するには容量が比較的大き過ぎる状態になり得るものであり、よって、機器のシステム性能及びデータ・スループットを低下させる。いずれにせよ、PCであってもノートブックであっても消費者向電子製品であっても機器における中央処理装置はFATを直接管理し、それによって、CPUの一部のリソースを占有し、行ううえでCPUのリソースを必要とする他のタスクの性能を悪化させる。

よって、CPUのリソースに対する影響が最小で、更に効率的にファイル割り当てテーブルをアクセスする手法に対する必要性が存在する。

この部分は、本発明の一部の特徴を要約する目的のためのものであり、好ましい実施例の一部を簡単に紹介するというものである。本明細書のこの部分や要約書、本発明の名称における簡略化や省略を、この部分、要約書や名称の目的をわかりにくくしないようにするよう行い得る。そうした簡略化や省略は、本発明の範囲を限定することを意図するものでない。

一般的に、本発明は、ファイル割り当てテーブル（FAT）をアクセスする手法に係わる。本発明の一特徴によれば、外部記憶装置からFATがインタフェースにおいて得られた後、外部記憶装置におけるファイルに割り当てられるクラスタのリンク・リストが抽出される。クラスタのリンク・リストにおけるクラスタの隣接領域がパック・レコードに圧縮され、各々は、第１クラスタの位置情報とクラスタの隣接領域の長さ情報とを含み、パック・レコードは、ランダム・アクセス・メモリに順番に記憶される。外部記憶装置におけるFATへのアクセスをインタフェースが管理することに依拠することによって、機器におけるプロセッサは、アクセス要求のみを送り、更に、FATをアクセス中に他のタスクを行うよう解放される。

本発明は、ハードウェア及びソフトウェアにおいてシステム、装置又は方法として実施し得る。一実施例によれば、本願の方法はファイル割り当てテーブル（FAT）をアクセスする方法であり、この方法は、FATを外部記憶装置から得る工程と、外部記憶装置におけるファイルに割り当てられるクラスタのリンク・リストを抽出する工程と、クラスタのリンク・リストにおけるクラスタの隣接領域をパック・レコードに圧縮する工程とを備え、各々は、第１のクラスタの位置情報とクラスタの隣接領域の長さ情報とを含み、更に、パック・レコードをランダム・アクセス・メモリに順番に記憶する工程を備える。

一実施例によれば、本願の装置は、ファイル割り当てテーブル（FAT）をアクセスする装置であり、この装置は、FATを外部記憶装置から得て、外部記憶装置におけるファイルに割り当てられるクラスタのリンク・リストを抽出するFATアクセス装置と、クラスタのリンク・リストにおけるクラスタの隣接領域をパック・レコードに圧縮する圧縮装置とを備え、各々は、第１のクラスタの位置情報とクラスタの隣接領域の長さ情報とを含み、更に、パック・レコードをランダム・アクセス・メモリに順番に記憶する結果記憶装置を備える。

本発明の目的、特徴及び効果の１つとして、ファイル割り当てテーブルの効率的なアクセス手法を備えるというものがある。

本発明の他の目的、特徴及び効果は、添付図面とともに検討する、以下の、その実施例の詳細説明を検討することによって明らかになる。

本発明のこれらや他の特徴、局面及び効果は、以下の記載、本特許請求の範囲及び添付図面に関して更に分かるようになるものである。

本発明の詳細説明は、本発明において想定される装置又はシステムの動作に直接的又は間接的に類似した手順、工程、論理ブロック、処理や他の記号表現によって概ね提示される。こうした記述や表現は、自らの成果の本質を当該技術分野における他の当業者に最も効果的に伝えるよう当業者によって通常用いられる。

本明細書及び特許請求の範囲における「one embodiment」や「an embodiment」への言及は、当該実施例に関して説明する特定の特徴、構造又は特性を本発明の少なくとも一実施例に含めることができるということを意味する。本明細書における種々の箇所において「in one embodiment」の句が生起することは必ずしも、全てが同じ実施例を表すものでなく、他の実施例と独立排他的に別個の実施例又は代替的な実施例を表すものでもない。更に、本発明の1つ又は複数の実施例を表す、プロセス・フローチャート又はプロセス図におけるブロックの順序や、連番の使用は、本来的に、何れかの特定の順序を示すものでも本発明における何れかの制約を示唆するものでもない。

従来技術では、FATは、機器、特に、携帯電話機やPDAなどの携帯型の機器のバッファ記憶空間に常時保持するには容量が比較的大きすぎる状態になる。FATをアクセスするよう、機器のプロセッサの制御下でFATをバッファ記憶装置にばらばらにページングしなければならず、よって、機器自体のシステム性能及びデータ・スループットが低下する。しかし、ファイルに割り当てられる、限定されたバッファ記憶装置の大量のボリュームを占有する多くの、クラスタの隣接領域が存在することが分かる。例えば、図3を参照すれば、ファイルに割り当てられるクラスタの番号は、a、a+1、a+2、a+3、b、b+1、b+2、b+3、c+1、c+2、c+3、c+4、dの各々であり、a、b、c、dは異なる自然数を表す。本発明の一特徴によれば、FATをランダム・アクセス・メモリにおいて圧縮して、プロセッサ上の計算量の負担を受けることなくアクセス効率を向上させる。本発明の別の特徴では、インタフェースとして加速式装置を外部記憶装置と機器（又はそのプロセッサ）との間に備える。加速式装置は、プロセッサが他のタスクを行ううえで解放されるようにアクセス動作を管理するよう構成される。

次に図5を参照すれば、501で、FATが外部記憶装置から得られ、ファイルに割り当てられるクラスタのリンク・リストがFATから抽出される。図3に示すファイルに割り当てられるクラスタのリンク・リストは、a、a+1、a+2、a+3、b、b+1、b+2、b+3、c+1、c+2、c+3、c+4、dである。502では、クラスタのリンク・リストのクラスタの隣接領域が、その位置情報及び長さ情報を含むパック・レコードに圧縮される。位置情報は、例えば、第１クラスタというクラスタ番号を含む。例えば、図４Bを参照すれば、第１の、クラスタの隣接領域を、a、a+1、a+2、a+3として示すので、第１のパック・レコードは、第１のクラスタの位置情報としてのaと、長さ情報としての4を含む。

502では、他の、クラスタの隣接領域があればそれをパック・レコードに圧縮することができる。503では、クラスタのリンク・リストの代わりにパック・レコードが、クラスタの隣接領域がクラスタのリンク・リストに配置されている順序でランダム・アクセス・メモリに記憶される。504では、ファイルは、クラスタのリンク・リストではなくパック・レコードによってホスト・プロセッサによってアクセスされる。例証した実施例では、クラスタのリンク・リストのパック形式は、クラスタの隣接領域の特性を利用して、クラスタのリンク・リストのボリュームを削減する。

図6を参照すれば、FATアクセス装置は、ホスト・プロセッサが直接アクセスすることができるFATアクセス装置601と、圧縮装置602と、結果記憶装置603とを備える。FATアクセス装置601は、外部記憶装置600に記憶されるFATをアクセスし、ファイルに割り当てられるクラスタのリンク・リストを抽出するよう形成される。FATアクセス装置601の例は、以下の段落に詳細に説明することとする図７に示す。圧縮装置602は、クラスタのリンク・リストをパック・レコードに圧縮するよう形成される。結果記憶装置603は、パック・レコードを記憶するよう形成される。したがって、ホスト・プロセッサは、クラスタのリンク・リストではなくパック・レコードによって外部記憶装置におけるファイルをアクセスすることができる。

圧縮装置602によって行われる502での圧縮処理は、
クラスタの隣接領域の第１のクラスタの位置情報としてFATアクセス装置601から、図3におけるaなどの、クラスタのリンク・リストの第１のクラスタ番号を得て、クラスタの隣接領域のLENGTH情報の値を１に設定する工程と、
次のクラスタ番号をFATアクセス装置601から得て、次のクラスタ番号に第１のクラスタ番号が隣接しているかを判定する工程と、
判定結果が肯定の場合は、LENGTH情報の値を１増加させ、最後の工程を繰り返し、判定結果が否定の場合は、次の、クラスタの隣接領域の第１のクラスタの位置情報として次のクラスタ番号を設定し、終了情報に達するまで上記工程を繰り返す工程とを含む。

外部記憶装置と機器のホスト・プロセッサとの間の通信インタフェースを備えるFATアクセス装置601の例を図7に示す。FAT管理を加速式装置300に置くことによって、ホスト・プロセッサは、外部記憶装置がアクセスされている時点で行う必要がある他のタスクを行うよう解放される。

一実施例では、FATアクセス装置601は、中央制御装置（CCU）301、FAT記憶セクタ算出装置（FAT記憶セクタCU）302、FAT記憶セクタ・アクセス装置（FAT記憶セクタAU）303、バッファ304、データ事前アクセス装置305及び結果保存装置306を備える。なお、FATアクセス装置601は外部記憶装置に組み込まれてもよく、ホスト・プロセッサ（図示せず）とともに1つのチップに一体化されてもよく、物理的な構造において外部記憶装置及びホスト・プロセッサから分離されてもよい。バッファ304は通常、512バイトのボリュームを有するが、1024バイトや2048バイト等などの何れかの所定の容量を有し得る。

ホスト・プロセッサが、外部記憶装置内のファイルを読み取る旨の読み取りアクセス要求を行うと、外部記憶装置のルート・ディレクトリに含まれており、オブジェクト・ファイルに割り当てられる開始クラスタ番号が加速式装置300に送られる。好ましくは図7にとともに理解される図8を次に参照すれば、801では、CCU301が、オブジェクト・ファイルの開始クラスタ番号を得て、それをFAT記憶セクタCU302に送る。802では、FAT記憶セクタCU302は、開始クラスタ番号が記憶されているFAT記憶セクタの番号を算出し、算出結果をFAT記憶セクタAU303に送る。図示した実施例では、FAT記憶セクタCU302の算出は、

の式を参照し、LBAはFATの一部が記憶されているFAT記憶セクタの番号を表し、FAT_start
は、FAT記憶セクタの開始番号を表し、Indexはクラスタ・インデックス番号を表し、開始クラスタ番号は、第１のクラスタ・インデックス番号としての役目を担い、Size_sectorは、512バイト、1024バイト、2048バイト、4096バイトなどの各FAT記憶セクタのボリュームを表し、Len_unitは、各クラスタ番号によって占められるボリュームを表す。FAT12、FAT16及びFAT32における各クラスタ番号は、3バイトと、4バイトと、8バイトとの各々を占める。

803では、FAT記憶セクタAU303は、802で判定されるFAT記憶セクタにおけるFATの一部を読み出し、FATの一部をバッファ304に送る。604では、事前アクセス装置305は、第１のクラスタ・インデックス番号としてみなされる開始クラスタ番号に含まれる内容を読み出す。805では、CCU301は、開始クラスタ番号に含まれる内容を読み取り、それを結果保存装置306に記憶する。806では、CCU301は、開始クラスタ番号に含まれる内容をFAT記憶セクタCU303に次のクラスタ・インデックス番号として送って、終了クラスタ・マークに達するまで上記工程を繰り返す。806で終了クラスタ・マークに達すると、オブジェクト・ファイルに割り当てられるクラスタのエンティティ・リンク・リストが結果保存装置306に収集され、FATアクセス装置601の読み取りアクセス手順が終了する。

本発明の重要な特徴の１つとして、アクセス要求が行われる前にホスト・プロセッサにFAT全体が送られる訳でなく、その代わりに、他のタスクを行うようホスト・プロセッサが解放されるようにFATが加速式装置によって管理されるということがある。他の特徴、便益及び効果は、本発明の上記詳細説明から分かり得る。

本発明は、ある程度の特定性をもって十分詳細に説明した。本願の実施例の開示は例として行ったに過ぎず、部分の配置及び組み合わせにおける種々の変更を、本特許請求の範囲記載の本発明の技術思想及び範囲から逸脱することなく行使し得るということが当業者に分かるものである。よって、本発明の範囲は、実施例の上記説明よりも本特許請求の範囲によって規定される。

FATファイル・システムのディスク形式を示す図である。 ファイルに割り当てられるクラスタのリンク・リストを特に示す、ファイル割り当てテーブルの断片の例を示す図である。 ファイルに割り当てられるクラスタのリンク・リストの別の例を示す図である。 図3に示すクラスタのリンク・リストのパケット形式を示す図である。 FATのクラスタのリンク・リストを圧縮するパック方法を示す図である。 FATのクラスタのリンク・リストを圧縮するパック装置を示す図である。 クラスタのリンク・リストを外部記憶装置から得るFATアクセス装置を略示する構成図である。 外部記憶装置におけるFATへのFATアクセス装置の読み取りアクセスの動作手順を示す流れ図である。

符号の説明

300 加速式装置
301 中央制御装置
302 FAT記憶セクタ算出装置
303 FAT記憶セクタ・アクセス装置
304 バッファ
305 事前アクセス装置
306 結果保存装置
307 結果記憶装置
310 外部記憶装置
3011 読み取りサブユニット
3012 新規作成サブユニット
3013 改訂サブユニット
3014 削除サブユニット
600 外部記憶装置
601 FATアクセス装置
602 圧縮装置
603 結果記憶装置

Claims (9)

1. ファイル割り当てテーブル（FAT）をアクセスする方法であって、
   前記FATを外部記憶装置から得る工程と、
   前記外部記憶装置内のファイルに割り当てられるクラスタのリンク・リストを抽出する工程と、
   前記クラスタのリンク・リストにおけるクラスタの隣接領域をパック・レコードに圧縮する工程とを備え、
   該パック・レコード各々は、第１のクラスタの位置情報と、クラスタの隣接領域の長さ情報とを含み、
   更に、前記パック・レコードをランダム・アクセス・メモリに順番に記憶する工程を備えることを特徴とする方法。
2. 請求項1記載の方法であって、
   前記FATを得る工程は、前記外部記憶装置と、外部記憶装置をアクセスする装置内のプロセッサとの間のインタフェースを備えるアクセス装置によって行われ、
   該アクセス装置は、中央制御装置と、FAT記憶セクタ算出装置と、FAT記憶セクタ・アクセス装置と、バッファと結果保存装置とを備えることを特徴とする方法。
3. 請求項2記載の方法であって、
   前記FATを得る工程は、
   ホスト・プロセッサからのオブジェクト・ファイルが割り当てられる開始クラスタ番号を得て、該開始クラスタ番号を前記FAT記憶セクタ算出装置に第１のクラスタ・インデックス番号として前記中央制御装置によって送る工程と、
   前記FAT記憶セクタ算出装置によって、前記第１のクラスタ・インデックス番号に相当するFAT記憶セクタの番号を算出する工程と、
   前記FAT記憶セクタ・アクセス装置によって、前記算出結果による、前記FATの一部を前記バッファに読み込む工程と、
   前記第１のクラスタ・インデックス番号の内容を前記中央制御装置によって読み込む工程と、
   前記第１のクラスタ・インデックス番号の前記内容を、前記結果保存装置に前記中央制御装置によって記憶して、前記オブジェクト・ファイルに割り当てられるクラスタのリンク・リストを得て、かつ、前記第１のクラスタ・インデックス番号の前記内容を、前記FAT記憶セクタ算出装置に次のクラスタ・インデックス番号として送って、前記オブジェクト・ファイルの終了クラスタ・マークに達するまで相当する工程を繰り返す工程とを備えることを特徴とする方法。
4. 請求項1記載の方法であって、
   前記第１のクラスタの番号が該第１のクラスタの前記位置情報として設定されることを特徴とする方法。
5. 請求項1記載の方法であって、
   前記クラスタの隣接領域を圧縮する工程が、
   前記クラスタのリンク・リストの第１のクラスタ番号をクラスタの隣接領域の前記第１のクラスタの位置情報として得て、クラスタの隣接領域のLENGTH情報の値を1に設定する工程と、
   次のクラスタ番号を得て、該次のクラスタ番号に前記第１のクラスタ番号が隣接しているかを判定する工程と、
   前記第１のクラスタ番号が前記次のクラスタ番号に隣接している場合、前記LENGTH情報の前記値を１、増加させる工程又は
   前記第１のクラスタ番号が前記次のクラスタ番号に隣接していない場合、前記次のクラスタ番号を前記クラスタの次の隣接領域の前記第１のクラスタの前記位置情報として設定する工程とを備えることを特徴とする方法。
6. 請求項1記載の方法であって、
   ホスト・プロセッサが、前記クラスタのリンク・リストの代わりに前記パック・レコードによって前記ファイルをアクセスすることができることを特徴とする方法。
7. 請求項6記載の方法であって、
   前記第１のクラスタの位置情報と、前記クラスタの隣接領域の多くの前記長さ情報が、前記ホスト・プロセッサが直接アクセスすることができる結果記憶装置に記憶されることを特徴とする方法。
8. FATをアクセスする装置であって、
   前記FATを外部記憶装置から得て、該外部記憶装置内のファイルに割り当てられるクラスタのリンク・リストを抽出するFATアクセス装置と、
   前記クラスタのリンク・リストにおけるクラスタの隣接領域をパック・レコードに圧縮する圧縮装置とを備え、
   該パック・レコード各々は、第１のクラスタの位置情報と、クラスタの隣接領域の長さ情報とを含み、
   更に、前記パック・レコードをランダム・アクセス・メモリに順番に記憶する結果記憶装置を備えることを特徴とする装置。
9. 請求項8記載の装置であって、
   前記外部記憶装置と、装置のホスト・プロセッサとの間の通信インタフェースを備える前記アクセス装置が、中央制御装置と、FAT記憶セクタ算出装置と、FAT記憶セクタ・アクセス装置と、バッファと結果保存装置とを備えることを特徴とする装置。

Images