オペレーティングシステム自動更新手順
本発明は、クライアントデバイス３０２、３０６、３０８、３１０、３１２内のオペレーティングシステムの差分更新に関する。デルタ更新ファイル１００が、旧インストールパーティションからポートするメモリ３２６内の新しいインストールパーティションに対して実行される操作の順序付きリストを含む。更新の差分を求め、クライアントデバイスに送信されるデータを圧縮するのに２値差分圧縮アルゴリズムを用いることができる。パーティション内のブロックが、循環して互いに依存する場合がある（Ｓ２０２、Ｓ２０４）。エッジがカットされ、サイクルが切断される。
【発明の詳細な説明】
【背景技術】
【０００１】
［関連出願の相互参照］
本出願は、２０１０年１月１２日に出願された米国仮出願第６１／２９４，２６６号の優先権を主張する。この米国仮出願の全体の開示内容は、引用することにより本明細書の一部をなすものとする。
【０００２】
オペレーティングシステム等のソフトウェアパッケージは、新しい特徴を導入し、誤りを訂正し、セキュリティ上の欠陥に対処するために、随時、更新することができる。大きなアプリケーションのファイルサイズのために、更新を有する完全に新しいパッケージを送信しインストールすることは不便又は非効率である場合がある。１つの解決策は、差分更新をクライアントに送信することである。差分更新は、従前のソフトウェアからの特定の変更のみをカバーしている。差分更新が正しく行われない場合、修正されたソフトウェアは、不十分に動作する場合もあるし、全く動作しない場合もある。
【発明の概要】
【０００３】
本発明は、包括的には、オペレーティングシステムに関する。より詳細には、本発明は、オペレーティングシステムのバージョンの更新に関する。
【０００４】
１つの実施の形態によれば、コンピュータ可読オペレーティングシステムの更新を生成する方法が提供される。該方法は、前記オペレーティングシステムの現バージョンのバージョン番号を特定するステップと、プロセッサを用いて、前記オペレーティングシステムの前記現バージョンを前記オペレーティングシステムの新バージョンに更新する操作の順序付きリストを作成するステップであって、前記プロセッサは、前記オペレーティングシステムの前記新バージョンに対して各通常ファイルにわたり反復を実行して、前記新バージョンに関連付けられた全てのデータブロックの前記順序付きリストを取得する、作成するステップと、前記プロセッサを用いて、差分更新ファイルが実際の更新ファイルであることを示すマジックナンバ指示子と、前記オペレーティングシステムの前記新バージョンを特定する新バージョン番号と、前記操作の順序付きリストを含むプロトコルバッファとを含む前記差分更新ファイルを組み立てるステップとを含む。
【０００５】
一例では、前記順序付きリスト内の１以上の操作は、それぞれ、データのチャンクを示すそれぞれのデータブロブに関連付けられる。ここで、前記差分更新ファイルは、前記それぞれのデータブロブを含むように組み立てられる。別の例では、前記順序付きリスト内の各操作は、クライアントデバイスのパーティションの１以上の特定のデータブロックに適用可能である。前記操作は、前記パーティション内の前記データブロックのうちの少なくとも１つが、前記オペレーティングシステムの前記新バージョンのための前記クライアントデバイスの新しいパーティション内の別のブロックにコピーされることになるコピー操作と、前記データブロックのうちの少なくとも所与の１つがメモリに読み込まれ、前記差分更新ファイルのデータブロブを用いて前記少なくとも１つの所与のデータブロックに対して差分ルーチンが実行される差分操作と、前記差分更新ファイルの選択されたデータブロブが前記新しいパーティション内の指定ブロックに書き込まれるように構成される置換操作と、圧縮されたデータブロブが前記差分更新ファイルに含まれ、前記オペレーティングシステムの前記新バージョンのための前記新しいパーティション内の選択された指定ブロックに書き込まれるように構成される解凍付き置換（replace with uncompression）操作とのうちの１以上のものを含む。
【０００６】
１つの代替形態では、前記順序付きリスト内の各操作は、ファイルオブジェクトに関連付けられ、前記方法は、ファイルオブジェクトごとにグラフ内に頂点を作成するステップと、各ブロックを表すベクトルを作成するステップとを更に含む。１つの変形形態では、前記方法は、各ブロックの前記ベクトルのリーダパラメータ及びライタパラメータを設定するステップと、異なるリーダ及びライタを有するブロックごとに、該ライタから該リーダへのエッジを前記グラフ内に作成するステップとを更に含む。前記エッジは、該エッジに関連付けられたソースファイル操作が開始する前に完了されるファイル操作を指し示す。一例では、各エッジは重みを有し、該重みは、そのエッジに関連付けられた前記グラフ内のブロックの数を特定する。別の例では、前記グラフがサイクルを含む場合、前記方法は、前記サイクルのそれぞれを切断するステップを更に含む。この場合、前記サイクルのうちの所与の１つを切断するステップは、前記所与のサイクルに関連付けられた最小重みのエッジを見つけることと、前記最小重みのエッジをカットすることとを含みうる。ここで、前記最小重みのエッジをカットすることは、エクステントをスクラッチスペースにコピーする操作を表す新しいノードを作成することと、前記最小重みのエッジのソースノードに前記新しいノードを指し示させることとを含みうる。そして、新しいコピー操作が該新しいコピー操作のコンシューマの前に行われることを保証するために、前記最小重みのエッジのデスティネーションノードから新しいエッジを作ることができる。
【０００７】
本発明の別の実施の形態によれば、コンピュータ可読オペレーティングシステムの更新を生成するデバイスが提供される。該デバイスは、前記オペレーティングシステムに関連付けられた差分更新情報を格納するメモリと、前記メモリに結合されたプロセッサとを備える。前記プロセッサは、前記オペレーティングシステムの現バージョンのバージョン番号を特定し、前記オペレーティングシステムの前記新バージョンに対して各通常ファイルにわたり反復を実行して、前記新バージョンに関連付けられた全てのデータブロックの前記順序付きリストを取得することを含めて、前記差分更新情報を用いて、前記オペレーティングシステムの前記現バージョンを前記オペレーティングシステムの新バージョンに更新する操作の順序付きリストを作成し、差分更新ファイルが実際の更新ファイルであることを示すマジックナンバ指示子と、前記オペレーティングシステムの前記新バージョンを特定する新バージョン番号と、前記操作の順序付きリストを含むプロトコルバッファとを含む前記差分更新ファイルを組み立て、前記差分更新ファイルを前記メモリに格納するように構成される。
【０００８】
一例では、前記順序付きリスト内の各操作は、ファイルオブジェクトに関連付けられ、前記プロセッサは、ファイルオブジェクトごとにグラフ内に頂点を作成し、各ブロックを表すベクトルを作成するように更に構成される。一代替形態では、前記プロセッサは、各ブロックの前記ベクトルのリーダパラメータ及びライタパラメータを設定し、異なるリーダ及びライタを有するブロックごとに、該ライタから該リーダへのエッジを前記グラフ内に作成するように更に構成される。前記エッジは、該エッジに関連付けられたソースファイル操作が開始する前に完了されるファイル操作を指し示す。この場合、前記グラフがサイクルを含む場合、前記プロセッサは、前記サイクルのそれぞれを切断するようにオプションで動作可能である。ここで、前記サイクルのうちの所与の１つを切断することは、前記所与のサイクルに関連付けられた最小重みのエッジを見つけることと、前記最小重みのエッジをカットすることとを含みうる。この場合、前記プロセッサは、エクステントをスクラッチスペースにコピーする操作を表す新しいノードを作成し、前記最小重みのエッジのソースノードに前記新しいノードを指し示させることによって前記最小重みのエッジをカットするように動作可能とすることができる。そして、新しいコピー操作が該新しいコピー操作のコンシューマの前に行われることを保証するために、前記最小重みのエッジのデスティネーションノードから新しいエッジを作ることができる。
【０００９】
更なる実施の形態では、有形のコンピュータ可読ストレージ媒体が、コンピュータプログラムのコンピュータ可読命令を格納する。前記命令は、コンピュータによって実行されると、コンピュータ可読オペレーティングシステムの更新を生成する方法を前記コンピュータに実行させる。前記方法は、前記オペレーティングシステムの現バージョンのバージョン番号を特定するステップと、プロセッサを用いて、前記オペレーティングシステムの前記現バージョンを前記オペレーティングシステムの新バージョンに更新する操作の順序付きリストを作成するステップであって、前記プロセッサは、前記オペレーティングシステムの前記新バージョンに対して各通常ファイルにわたり反復を実行して、前記新バージョンに関連付けられた全てのデータブロックの前記順序付きリストを取得する、作成するステップと、前記プロセッサを用いて、差分更新ファイルが実際の更新ファイルであることを示すマジックナンバ指示子と、前記オペレーティングシステムの前記新バージョンを特定する新バージョン番号と、前記操作の順序付きリストを含むプロトコルバッファとを含む前記差分更新ファイルを組み立てるステップとを含む。
【００１０】
一例では、前記順序付きリスト内の各操作は、ファイルオブジェクトに関連付けられ、前記方法は、ファイルオブジェクトごとにグラフ内に頂点を作成するステップと、各ブロックを表すベクトルを作成するステップとを更に含む。この場合、前記方法は、各ブロックの前記ベクトルのリーダパラメータ及びライタパラメータを設定するステップと、異なるリーダ及びライタを有するブロックごとに、該ライタから該リーダへのエッジを前記グラフ内に作成するステップとを更に含みうる。前記エッジは、該エッジに関連付けられたソースファイル操作が開始する前に完了されるファイル操作を指し示す。ここで、前記グラフがサイクルを含む場合、前記方法は、各所与のサイクルに関連付けられた最小重みのエッジを見つけるステップと、各サイクルの前記最小重みのエッジをカットすることとによって前記サイクルのそれぞれを切断するステップとを更に含みうる。前記最小重みのエッジをカットすることは、エクステントをスクラッチスペースにコピーする操作を表す新しいノードを作成することと、前記最小重みのエッジのソースノードに前記新しいノードを指し示させることとを含みうる。そして、新しいコピー操作が該新しいコピー操作のコンシューマの前に行われることを保証するために、前記最小重みのエッジのデスティネーションノードから新しいエッジを作ることができる。
【００１１】
更なる実施の形態では、クライアントデバイスが、オペレーティングシステムの現バージョンを格納するメモリと、前記メモリに結合されたプロセッサとを備える。前記プロセッサは、前記オペレーティングシステムの前記現バージョンの更新に関して遠隔デバイスに要求を送信し、ここで、該要求は、前記オペレーティングシステムの前記現バージョンを特定するバージョン番号を含み、前記遠隔デバイスから差分更新ファイルを受信し、ここで、該差分更新ファイルは、該差分更新ファイルが実際の更新ファイルであることを示すマジックナンバ指示子と、前記オペレーティングシステムの前記新バージョンを特定する新バージョン番号と、操作の順序付きリストを含むプロトコルバッファとを含み、前記マジックナンバを検証し、前記プロトコルバッファから前記操作の順序付きリストを抽出し、前記オペレーティングシステムの前記現バージョンを前記オペレーティングシステムの前記新バージョンに更新するために、前記操作の順序付きリストを実行することによって差分更新を実行するように構成される。
【００１２】
一例では、前記プロセッサは、前記差分更新ファイルが前記クライアントデバイスにストリーミングされている間に、前記メモリに前記差分更新ファイルを保存することなく、前記オペレーティングシステムの前記新バージョンへの前記オペレーティングシステムの前記差分更新を実行するように動作可能である。
【図面の簡単な説明】
【００１３】
【図１】本発明の態様によるファイルフォーマットを示す図である。
【図２】本発明の態様による、エッジをカットしてサイクルを切断するプロセスである。
【図３】本発明の態様による差分更新プロセスを示す図である。
【図４Ａ】本発明において用いるコンピュータシステムを示す図である。
【図４Ｂ】本発明において用いるコンピュータシステムを示す図である。
【発明を実施するための形態】
【００１４】
本発明の態様、特徴及び利点は、好ましい実施形態の以下の説明及び添付した図を参照して検討すると理解されるであろう。種々な図面における同じ参照符号は、同じ要素又は同様の要素を特定することができる。
【００１５】
オペレーティングシステムの随時異なる特徴が更新される。それらの更新は、あらかじめ規定された更新プロセスを実行するクライアントコンピュータに送信することができる。これは、クライアントに対するファイルの消去、変更及び／又は追加を伴うことができる。１つのプロセスでは、更新は、オペレーティングシステムプロバイダによって準備される。これは、差分更新ファイルを作成することを含みうる。差分更新ファイルは、どのような変更を行う必要があるかをクライアントに示す。そして、差分更新ファイルは、更新される各クライアントに送信される。クライアントは、望ましくは、ファイル内の操作を順次実行して更新を行う。
【００１６】
オペレーティングシステムを含むパーティションは、１以上のブロックとして構成することができ、各ブロックは、ファイル情報又はブックキーピング情報を含む。各ブロックは、例えば４ｋバイトとすることができるが、本発明は、これに限定されるものでもなければ、どの特定のブロックサイズにも限定されるものでもない。オペレーティングシステム自体は、コンピュータプロセッサ上で実行されるプログラム（例えば命令）及びデータを含み、コンピュータハードウェアリソースを管理し、様々なアプリケーションソフトウェアの効率的な実行のための共通のサービスを提供する。オペレーティングシステムを更新するとき、新しいパーティションを作成することができる。この新しいパーティションは、オペレーティングシステムの旧バージョンで事前にポピュレートされる。その結果得られた（ルートファイルシステムを包含する）インストールパーティション上の各ディスクブロックは、望ましくは、オペレーティングシステムベンダが（例えば、ベリファイドブートの場合）サーバ上で署名を受けることができるように、オペレーティングシステムベンダによって正確に（ビット単位で）指定される。
【００１７】
更新は可能な限り小さいことが望ましい。１つのシナリオでは、リブートすることなく、多くのデルタ（差分）更新をインストールすることができるように、更新は所定の位置に適用される。したがって、ユーザがバージョンＮにブートされ、Ｎ＋１がリリースされた場合、ユーザ（クライアント）は、Ｎ→Ｎ＋１に更新されたものをダウンロードし、その更新されたものをインストールする。そして、Ｎ＋２が登場したときでも、ユーザは依然としてＮ＋１にブートされる。そして、ユーザは、Ｎ＋１→Ｎ＋２更新をダウンロードし、その更新をＮ＋１上の所定の位置にインストールする。
【００１８】
一例では、クライアントは、更新サーバと連絡をとり、現在のインストールパーティション上にインストールされているシステムのバージョン番号を提供する。サーバは、クライアントにダウンロードされる増分（デルタ）更新をクライアントに提供する。デルタ更新ファイルは、インストールパーティションを旧（既存）バージョンから新バージョンにする、インストールパーティションに対して実行する操作の順序付きリストを含む。
【００１９】
望ましくは、更新ファイルは、クライアントによって実行される操作の順序付きリストである。各操作は、パーティションの特定のブロックに対して作用する。各操作は、デルタファイルの内部のオプションのデータ「ブロブ（blob）」を含みうる。用語「ブロブ」とは、バイトの任意の集まりを有することができる大きなデータチャンクを示す。「Ｃｏｐｙ（コピー）」、「Ｄｉｆｆ（ディフ）」、「Ｒｅｐｌａｃｅ（置換）」及び「Ｒｅｐｌａｃｅ ｗｉｔｈ Ｕｎｃｏｍｐｒｅｓｓｉｏｎ（解凍付き置換）」を含む数タイプのインストール操作がある。Ｃｏｐｙでは、現在のインストールパーティション内のブロックのうちの幾つかが新しいインストールパーティション内の他のブロックにコピーされる。Ｄｉｆｆの場合、幾つかのブロックがメモリ内に読み込まれ、付属のデータブロブを用いて２値差分ルーチンが実行される。その結果は、新しいインストールパーティション内の指定ブロックに書き込まれる。Ｒｅｐｌａｃｅの場合、付属のデータブロブが新しいインストールパーティション内の指定ブロックに書き込まれる。圧縮プロセスも実行することができ、圧縮プロセスにおいて、圧縮データブロブがクライアントに送信されて解凍され、その結果が新しいインストールパーティション内の指定ブロックに書き込まれる。この圧縮プロセスでは、Ｇｚｉｐ、Ｂｚｉｐ２又は別の圧縮アルゴリズムを用いることができる。
【００２０】
１つのシナリオでは、旧ファイルがインストールパーティションであることがパッチプログラムに指示される。プログラムにパーティション全体をメモリに読み込ませるのではなく、ファイルをメモリ内に入れるためにいずれのブロックを読み出すべきかがパッチプログラムに指示される。そして、パッチ操作がメモリ内で実行される。最後に、その結果は、デバイスの開始時ではないが、新しいインストールパーティションに直接書き込まれる。その代わり、プログラムは、いずれのブロックに結果を書き込むのかを伝えられる。
【００２１】
デルタ／差分更新ファイルは、以下の議論に従って生成することができる。更新ファイルフォーマットは、図１のファイルフォーマット１００に示されるようにすることができる。具体的には、フォーマットは、好ましくは、ファイルが実際に更新ファイルであることを示す「マジックナンバ」指示子又はサニティチェックを含む。一例では、マジックナンバは、「ＣｒＡＵ」等の短いフレーズの２値バージョンを含む４バイトを含む。次はバージョン番号であり、その後に、プロトコルバッファオフセット及び長さが続き、これらのそれぞれは８バイトとすることができる。プロトコルバッファそのものが次に続く。プロトコルバッファは、クライアントが順に実行する一連の命令である。次に、１以上のデータブロブが提供され、その後に、ファイル終端（ＥＯＦ）指示子が続く。順序はこの図に示されるようにすることができるが、所望の場合には、様々な構成要素を異なる順序にすることができる。
【００２２】
１つのシナリオでは、「エクステント」の概念が用いられる。エクステントはディスクブロックの連続した範囲である。例えば、ブロック｛１０，１１，１２，１３，１４，１５，１７，１８｝を指定するのではなく、｛（１０，６），（１７，２）｝（エクステントのリスト）を指定する方が簡単な場合がある。デルタ更新を生成する一例示のプロセスは、以下のとおりである。
【数１】
【００２３】
このマニフェスト（manifest）は、インストール操作のリストを示す。入力エクステントは、読み出されるブロックを示す。出力エクステントは、書き込まれるブロックを示す。
【００２４】
デルタ更新を生成するために、新しいファイルシステムに対して各通常ファイルにわたり反復が実行され、新しいファイルシステムが有する全てのデータブロックの順序付きリストが取得される。これは、以下のフォーマットを有するファイル構造に格納される。
【数２】
【００２５】
最終的に、各ファイルオブジェクトは、プロトコルバッファ内のＩｎｓｔａｌｌＯｐｅｒａｔｉｏｎ（インストール操作）メッセージに変換されることになる。ファイルごとに、該ファイルを圧縮する最適な方法を規定することが望ましい。４つのケースが存在する。１つのケースでは、ファイルは変化していない。他の３つのケースでは、ファイルは変化している。１つのシナリオでは、Ｂｚｉｐ２又は別の圧縮アルゴリズムを用いて、変化したファイルを最小サイズに圧縮することができる。別のシナリオでは、ファイルは変化しており、最小サイズに解凍される。第３のシナリオでは、ファイルは変化しており、最小のものをｂｉｎａｒｙ−ｄｉｆｆ（バイナリディフ）する。ファイルが新しい場合、これは、該ファイルがオペレーティングシステムの旧バージョンには存在しなかったことを意味するが、これらのケースのうちの２つのみが当てはまる。データは、全て送信することもできるし、圧縮して全て送信することもできる。
【００２６】
本発明の１つの態様によれば、ファイルオブジェクトごとにグラフに頂点が作成される。グラフとともに、ベクトルがインストールパーティション内の各ブロックを表すのに作成される。
【数３】
【００２７】
その後、プロセスは、各ファイルオブジェクト内の各ブロックを通過する。ブロックごとに、リーダパラメータ及びライタパラメータがブロックのベクトルについて設定される。
【００２８】
次に、反復がブロックのアレイを通して実行される。異なるリーダ及びライタ（ともに非ヌルである）を有するブロックごとに、エッジ（矢印）がライタからリーダへのグラフに作成される。（有向）グラフ内のエッジは、該エッジのソースファイル操作が開始する前に完了しなければならないファイル操作を指し示す。したがって、このプロセスは、異なるファイル操作によってブロックの読み出し及び書き込みの双方が行われる場合、該ブロックが書き込まれる前に読み出されることを確実にするように試みる。エッジはグラフ内のブロックを表し、したがって、エッジの重みはブロック数である。
【００２９】
このとき、結果は、サイクルを備えたグラフを有する可能性がある。サイクルは切断されるべきである。サイクルは、「Finding all the Elementary Circuits of a Directed Graph」（SIAM J. Comput., vol. 4 no. 1, March 1975）に述べられているようなDonald B. Johnsonの回路発見アルゴリズムを用いて見つけることができる。この文献の開示内容全体は、引用することにより本明細書の一部をなすものとする。サイクルは、「Tarjan's Strongly Connected Components Algorithm」（David Eppstein, Ed., Wikipedia）に述べられているようなTarjanのアルゴリズムを用いて見つけることもできる。この文献の開示内容全体は、引用することにより本明細書の一部をなすものとする。サイクルごとに、最小重みのエッジが見つけられカットされる。エッジは以下のようにカットすることができる。先ず、幾つかのエクステントをスクラッチスペースにコピーする操作を表す新しいノードを作成する。次に、エッジのソースノードに新しいノードを指し示させる。ここで、カットされたエッジのデスティネーションノードから新しいノードへのエッジを作成して、新しいコピー操作がコピーのコンシューマの前に行われることを強制することができる。好ましくは、エッジがカットされることによって表されるブロックからではなく、スクラッチスペースから読み出すように、カットされたエッジのデスティネーションノードを修正する。
【００３０】
エッジをカットしてサイクルを切断する一例は、図２のプロセス２００に示される。矢印は、指し示される側の操作が指し示す側の操作の前に行われる必要があり、指し示す側の操作が、指し示される側によって必要とされるデータを上書きするので、その順序で行われることを必要とすることを示す。この図に示すように、Ｓ２０２において、操作Ａが、ブロック３を読み出し、ブロック４を書き込む。そして、Ｓ２０４において、操作Ｂが、ブロック４を読み出し、ブロック１０を書き込む。サイクルは、ＡとＢとの間のエッジ（矢印２０６）をカットすることによって切断される。これは、ｔｅｍｐブロックＴを用いることによって行うことができる。したがって、図示するように、Ｓ２０８において、操作Ａが、ブロック３を読み出し、ブロック４を書き込む。Ｓ２１０において、操作Ｃが、ブロック４を読み出し、ブロックＴを書き込む。そして、Ｓ２１２において、操作Ｂ’が、ブロックＴを読み出し、ブロック１０を書き込む。サイクルが切断されると、トポロジカルソートを用いて全てのノードを順序付けることができる。それは、全てのファイルデータブロックのインストールをカバーしている。
【００３１】
一例では、Ｂ’−＞Ｃ−＞Ａ−＞Ｔｅｍｐにように、エッジを選んでカットすることが可能である。この場合、Ｔｅｍｐ操作は、ブロックＡをｔｅｍｐエリアにコピーする。ＢはＢ’に修正され、次に、Ｂ’はｔｅｍｐエリアから読み出される。一方、第２のエッジ（例えば、Ｃ−＞Ａ）が切断される場合、その結果は、Ｂ’−＞Ｃ−＞Ｔｅｍｐ２及びＡ’−＞Ｔｅｍｐとなる。この結果、２つの完全に独立したグラフが得られ、操作の最終的な順序は以下のように配列することができる。
Ｔｅｍｐ２（クライアントはこれを最初に実行する）
Ｃ
Ｂ’
Ｔｅｍｐ
Ａ’（クライアントはこれを最後に実行する）
【００３２】
しかしながら、この場合、Ｂ’は、Ｔｅｍｐ操作によって書き込まれたデータを読み出すが、ＴｅｍｐはＢ’の後に行われる。これは、Ａ−＞Ｂがエッジをカットされたときに行われたグラフ変換が、ＴｅｍｐがＢ’の前に行われなければならないことを特に明確に指定していなかったことから起こる場合がある。この状況を回避するために、別のエッジが、これを明示的にするために追加される。その結果は以下のようになる。
Ａ−＞Ｂ−＞Ｃ−＞Ａ（オリジナル）
Ａ−＞Ｂをカットして以下を取得する：
Ｂ’−＞Ｃ−＞Ａ−＞Ｔｅｍｐ＜−Ｂ’
次に、Ｃ−＞Ａをカットして以下を取得する：
Ｂ’−＞Ｃ'−＞Ｔｅｍｐ２＜−Ａ−＞Ｔｅｍｐ＜−Ｂ’
次に、操作の最終的な順序がグラフに基づいて選ばれ、操作は正しい順序で行われる。
【００３３】
例示のプロセスが図３に示されている。ステージ１において、ディスクイメージがスキャンされる。ブロックインデックス（０〜７）は、異なるイメージ（例えば、「ｓｈ」、「ｆｏｏ」、「ｂａｒ」及び「ｄｏｇ」）に関連付けることができる。新しいイメージは、同じブロック又は異なるブロックに関連付けることができる。したがって、ここでは、「ｆｏｏ」は、ブロック４の代わりにブロック２及び３に関連付けることができる。「ｓｈ」は、ブロック２及び３の代わりにブロック４及び５に関連付けることができる。「ｂａｒ」は、ブロック５の代わりにブロック６に関連付けることができる。そして、新しいイメージ「ｃａｔ」は、ブロック７に関連付けることができる。
【００３４】
ステージ２において、ファイル操作が作成される。これは、新しいパーティション上のファイルに対応する。この後に、ブロックベクトルが続く。ブロックベクトルは順序付きリストであり、ブロックベクトルにおいて、各要素は、所与のブロックのファイル操作を含む。各イメージは、１以上のソースブロック及び１以上のデスティネーションブロックを有することができる。したがって、「ｆｏｏ」のソースブロックはブロック４であり、「ｆｏｏ」のデスティネーションブロックは、「ｄｓｔ:（２，２）」として示され、これは、最初のブロックがブロック２であり、２つのブロックが割り当てられていることを示している。この部分は、各イメージをクライアントにどのように提供することができるのかも示している。したがって、ｆｏｏ及びｂａｒは、ｂｓｄｉｆｆ等の２値差分アルゴリズムを用いて提供することができ、ｓｈは、単にコピーのみすることができ、ｃａｔは、圧縮なしで全体を送信することができる。Ｂｓｄｉｆｆは２つのファイル間の差分を計算する既知のアルゴリズムである。
【００３５】
ステージ３に示すように、エッジ重み（例えば、１又は２）がブロック数に等しいグラフが作成される。ステージ４において、サイクルが切断される。望ましくは、サイクル（複数の場合もあり）は、各サイクルにおける最小重みエッジをカットすることによってカットされる。したがって、この例では、ｓｈからｆｏｏへの矢印（重み１を有する）を含むサイクルが切断され、修正されたｆｏｏ（ｆｏｏ’）が得られる。そして、ステージ５において、トポロジカルソートの結果得られた最終的な順序が示される。これは、クライアント上で実行される順序である。
【００３６】
クライアントは、ファイルデータを設定した後、残りのデータをアンジップして全て非ファイルデータブロックにする最終的なＩｎｓｔａｌｌＯｐｅｒａｔｉｏｎを用いて非ファイルデータブロックに上書きする。一般的な例では、これは、約２メガバイトの圧縮データである。このデータに対してデルタ圧縮プロセスを実行することが実現可能な場合がある。
【００３７】
（全ての操作をリストする）プロトコルバッファは、ファイルの先頭に現れるので、更新をディスクに保存する必要はない。更新は、サーバからのストリーミング中に適用することができる。更新がＯＳベンダによって署名されることを確実にすることが望ましい。システムは、更新の適用を開始することができ、デルタ更新シグネチャの検証後になるまで、更新をブート可能にマーキングしないことができる。
【００３８】
ここに提示した実施形態は、実際に最良の圧縮比を与えることがわかっている。これによって、オペレーティングシステムベンダは、将来の代替的な圧縮方式を用いることも可能になる。例えば、Ｇｏｏｇｌｅによって開発された１つのプロセスはＣｏｕｒｇｅｔｔｅであり、これは、ｂｓｄｉｆｆに取って代わることができる。
【００３９】
別の可能な解決策は、パーティション全体をデルタ圧縮することである。しかしながら、ｂｓｄｉｆｆは、そのメモリ要件が高すぎるために、このシナリオでは動作することができない。パッチ中、ｂｓｄｉｆｆは、オリジナルのファイル及び新しいファイルを格納するのに十分なメモリを必要とし、このメモリは１ギガバイトを超える場合がある。別のデルタ圧縮プログラムであるＸｄｅｌｔａは、スライディングウィンドウを用いる。テストにおいて、このＸｄｅｌｔａは、圧縮が不十分な結果となった（例えば、数百メガバイト）。更なる代替形態はｒｄｉｆｆを用いることであり、ｒｄｉｆｆは、変更されたブロックのみをデルタファイルに格納することによって動作する。ｒｄｉｆｆは、ブロックを整列する必要がないように、スライディングウィンドウを用いる。パーティション全体のｒｄｉｆｆデルタは、テストされると、１０４メガバイトであった。これは、上述した手順に従って用いることができるおよそ１０メガバイトを優に超えている。
【００４０】
今後、ファイルレベルにおいて、ｒｄｉｆｆスタイル（すなわち、ｒｓｙｎｃスタイル）のデルタ圧縮を用いることが可能な場合がある。これは、今後、ｂｓｄｉｆｆとともに用いることができる。
【００４１】
本発明の態様による更新手順は、以下の例示のコンピュータシステムを用いて実施することができる。図４Ａは、本発明において単独で用いることもできるし、ネットワークされた構成で用いることもできる様々なコンピューティングデバイスを示すコンピュータシステムの概略図を示している。例えば、この図は、複数のコンピュータ３０２、３０４、３０６及び３０８と、移動電話３１０及びＰＤＡ３１２等のポータブル電子デバイス等の他のタイプのデバイスとを有するコンピュータネットワーク３００を示している。しかしながら、本発明は、そのように限定されるものではなく、ネットブック及びパッド型ハンドヘルドコンピュータ（図示せず）を含む他のデバイスも用いることができる。そのようなデバイスは、ローカル接続若しくは直接接続３１４を介して相互接続することができ、及び／又はＬＡＮ、ＷＡＮ、インターネット等の通信ネットワーク３１６を介して結合することができる。通信ネットワーク３１６は、有線又は無線とすることができる。
【００４２】
各デバイスは、例えば、１以上の処理デバイスを含むことがあり、キーボード３１８及びマウス３２０等のユーザ入力、並びに／又はペン入力、ジョイスティック、ボタン、タッチスクリーン等の様々な他のタイプの入力デバイスに加えて、例えば、ＣＲＴ、ＬＣＤ、プラズマスクリーンモニタ、ＴＶ、プロジェクタ等を含みうるディスプレイ３２２を有することができる。各コンピュータ３０２、３０４、３０６及び３０８は、パーソナルコンピュータやサーバ等でありうる。単なる例として、コンピュータ３０２及び３０６は、パーソナルコンピュータとすることができる一方、コンピュータ３０４はサーバとすることができ、コンピュータ３０８はラップトップとすることができる。
【００４３】
図４Ｂに示すように、コンピュータ３０２及び３０４等の各コンピュータは、プロセッサ３２４、メモリ／ストレージ３２６及びコンピュータ内に通常存在する他の構成要素を含む。例えば、メモリ／ストレージ３２６は、プロセッサ３２４によってアクセス可能な情報を格納する。この情報は、プロセッサ３２４が実行することができる命令３２８と、プロセッサが検索、操作又は格納することができるデータ３３０とを含む。サーバにおける命令３２８は、１以上のクライアントデバイスによってインストールされる差分更新を作成する操作を含みうる。そして、クライアントデバイスにおける命令は、差分更新を実行する操作を含みうる。
【００４４】
データは、クライアントデバイスに対するサービスのためにデータベースに保持された１以上の差分更新を含みうる。メモリ／ストレージは、ハードドライブやＲＯＭやＲＡＭやＣＤ−ＲＯＭやフラッシュメモリや書き込み可能メモリ又は読み出し専用メモリ等の、プロセッサによってアクセス可能な情報を格納可能な任意のタイプのもの又は任意のデバイスでありうる。プロセッサ３２４は、Intel Corporation又はAdvanced Micro Devices社からのプロセッサ等の、任意の個数の既知のプロセッサを含みうる。代替的には、プロセッサは、ＡＳＩＣ又は他の処理デバイス等の、操作を実行する専用コントローラでありうる。
【００４５】
命令３２８は、プロセッサ（複数の場合もあり）によって直接的（マシンコード等）又は間接的（スクリプト等）に実行される任意の一組の命令を含みうる。その点について、用語「命令」、「ステップ」及び「プログラム」とは、本明細書では交換可能に用いることができる。命令は、オブジェクトコード又はソースコードのモジュール等、任意のコンピュータ言語又はフォーマットにより格納することができる。本発明による機能、方法及び命令のルーチンは、以下により詳細に説明される。
【００４６】
データ３３０は、命令３２８に従って、プロセッサ３２４が検索、格納又は修正することができる。データは、データ集合体として格納することができる。例えば、本発明は、どの特定のデータ構造によっても限定されないが、データは、コンピュータレジスタ、複数の異なるフィールド及びレコードを有するテーブルとしてリレーショナルデータベース、ＸＭＬ文書としてウェブページキャッシュ等に格納することができる。
【００４７】
データは、限定するものではないが２値、ＡＳＣＩＩ又はＵｎｉｃｏｄｅ等の任意のコンピュータ可読フォーマットにフォーマットすることもできる。その上、データは、説明文、独自のコード、ポインタ、他のメモリ（他のネットワークロケーションを含む）に格納されたデータへの参照子、又は関連データを計算するのに或る機能によって用いられる情報等、関連情報を特定するのに十分な任意の情報を含むことがある。さらに、所与のアイテムは、１以上のファイル、データベース、ウェブキャッシュに格納されたデータセット等を含みうる。データのサイズ及び内容に応じて、該データの一部ずつを別々に格納又は別の方法により保持することもできる。
【００４８】
プロセッサ３２４及びメモリ３２６は、図４Ｂでは、同じブロック内に存在するものとして機能的に示されているが、プロセッサ及びメモリは、実際には、同じ物理ハウジング又は物理ロケーション内に格納されることもあるし格納されないこともある複数のプロセッサ及びメモリを含みうることが理解されるであろう。例えば、命令及びデータの幾つか又は全ては、着脱可能なＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ又はフラッシュドライブ、及び読み出し専用コンピュータチップ内の他のものに格納することができる。命令及びデータの幾つか又は全ては、プロセッサから物理的に遠隔ではあるが、それでもプロセッサによってアクセス可能なロケーションに格納することができる。同様に、プロセッサは、実際には、並列に動作することもあるし動作しないこともあるプロセッサの集合体を含みうる。データは、分散させることができ、ハードドライブ等の複数のメモリ３２６にわたって格納することができる。
【００４９】
１つの態様では、サーバ３０４は、１以上のクライアントコンピュータ３０２、３０６及び／又は３０８、並びに移動電話３１０及びＰＤＡ３１２等のデバイスと通信することができる。各クライアントコンピュータ又は他のクライアントデバイスは、プロセッサ、メモリ及び命令、並びに１以上のユーザ入力デバイス３１８、３２０及びディスプレイ３２２等のユーザ出力デバイスを用いてサーバ３０４と同様に構成することができる。各クライアントコンピュータは、中央処理装置（「ＣＰＵ」）、ディスプレイ、ＣＤ−ＲＯＭドライブ若しくはＤＶＤドライブ、ハードドライブ、マウス、キーボード、タッチスクリーン、スピーカ、マイク、モデム及び／又は（電話やケーブル等の）ルータ、並びにこれらの要素を互いに接続するのに用いられる構成要素の全て等の、パーソナルコンピュータにおいて通常見られる全ての構成要素を有する、人による使用を対象とした汎用コンピュータとすることができる。
【００５０】
サーバ３０４、ユーザコンピュータ及び他のデバイスは、ネットワーク３１６を介する等により、他のコンピュータと直接通信及び間接通信が可能である。図４Ａ及び図４Ｂには少数のコンピューティングデバイスしか示されていないが、一般的なシステムは、各異なるコンピュータがネットワークの異なるノードに存在する、多数の接続されたサーバ及びクライアントを含むことができることが理解されるべきである。ネットワーク３１６、及び介在するノードは、１以上の企業に独自の通信プロトコル、Ｅｔｈｅｒｎｅｔ（登録商標）、ＷｉＦｉ、Ｂｌｕｅｔｏｏｔｈ（登録商標）又はＴＣＰ／ＩＰを用いるインターネット、イントラネット、仮想プライベートネットワーク、ワイドエリアネットワーク、ローカルネットワーク、プライベートネットワークを含む様々な構成及びプロトコルを備えうる。
【００５１】
任意の介在するノードを含むネットワークにわたる通信は、モデム（例えば、ダイヤルアップ又はケーブル）、ネットワークインタフェース及び無線インタフェース等、他のコンピュータへのデータの送信及び他のコンピュータからのデータの送信が可能な任意のデバイスによって容易にすることができる。サーバ３０４はウェブサーバでありうる。上述したように、情報が送信又は受信されると、或る利点が得られるが、本発明の他の態様は、情報のどの特定の送信方法にも限定されるものではない。例えば、幾つかの態様では、情報は、ディスク、テープ、ＣＤ−ＲＯＭ等の媒体を介して送信することもできるし、ダイヤルアップモデムを介して２つのコンピュータシステム間で直接送信することもできる。他の態様では、或る情報は、非電子フォーマットで送信することができ、システム内に手動で入力することができる。
【００５２】
その上、本明細書で説明したシステム及び方法によるコンピュータ及びユーザデバイスは、命令の処理と、人間及び他のコンピュータへのデータの送信と、人間及び他のコンピュータからのデータの送信とが可能な任意のデバイスを含みうる。他のコンピュータは、ローカルストレージ機能のないネットワークコンピュータと、ＰＤＡ３１２等のモデム付きＰＤＡと、移動電話３１０等のインターネット対応無線電話と、ネットブックと、パッド型ハンドヘルドコンピュータとを含む。
【００５３】
図４Ａに示すように、ネットワーク３００は、クライアントデバイスに差分更新をサービス提供する更新データベース３３２も含みうる。更新データベースは、サーバ３０４に直接的又は間接的に結合することができる。一代替形態では、更新データベース３３２は、サーバ３０４の一部とすることもできるし、別の方法でサーバ３０４に論理的に関連付けることもできる。
【００５４】
本明細書では、本発明を特定の実施形態に関して説明してきたが、これらの実施形態は本発明の原理及び用途の単なる例示にすぎないことが理解されるべきである。したがって、例示の実施形態に対して多数の修正を行うことができること、及び添付の特許請求の範囲によって規定される本発明の趣旨及び範囲から逸脱することなく他の構成を考案することができることが理解されるべきである。例えば、或る実施形態はオペレーティングシステムについて示されているが、本発明の態様による差分更新は、他のソフトウェアパッケージ、アプリケーション及びサービスとともに用いることができる。さらに、特定のプロセスが添付図面において特定の順序で示されているが、そのような順序が本明細書において明白に述べられていない限り、そのようなプロセスは、どの特定の順序にも限定されるものではなく、異なる順序で又は並列に実行することができる。そして、特に別段に指定がない限り、追加のプロセスを追加することもできるし、他のプロセスを省くこともできる。
【産業上の利用可能性】
【００５５】
本発明は、限定するものではないが、コンピュータシステム操作と、そのようなコンピュータシステムのアプリケーションの更新とを含む幅広い産業上の利用可能性を享有する。
【背景技術】
【０００１】
［関連出願の相互参照］
本出願は、２０１０年１月１２日に出願された米国仮出願第６１／２９４，２６６号の優先権を主張する。この米国仮出願の全体の開示内容は、引用することにより本明細書の一部をなすものとする。
【０００２】
オペレーティングシステム等のソフトウェアパッケージは、新しい特徴を導入し、誤りを訂正し、セキュリティ上の欠陥に対処するために、随時、更新することができる。大きなアプリケーションのファイルサイズのために、更新を有する完全に新しいパッケージを送信しインストールすることは不便又は非効率である場合がある。１つの解決策は、差分更新をクライアントに送信することである。差分更新は、従前のソフトウェアからの特定の変更のみをカバーしている。差分更新が正しく行われない場合、修正されたソフトウェアは、不十分に動作する場合もあるし、全く動作しない場合もある。
【発明の概要】
【０００３】
本発明は、包括的には、オペレーティングシステムに関する。より詳細には、本発明は、オペレーティングシステムのバージョンの更新に関する。
【０００４】
１つの実施の形態によれば、コンピュータ可読オペレーティングシステムの更新を生成する方法が提供される。該方法は、前記オペレーティングシステムの現バージョンのバージョン番号を特定するステップと、プロセッサを用いて、前記オペレーティングシステムの前記現バージョンを前記オペレーティングシステムの新バージョンに更新する操作の順序付きリストを作成するステップであって、前記プロセッサは、前記オペレーティングシステムの前記新バージョンに対して各通常ファイルにわたり反復を実行して、前記新バージョンに関連付けられた全てのデータブロックの前記順序付きリストを取得する、作成するステップと、前記プロセッサを用いて、差分更新ファイルが実際の更新ファイルであることを示すマジックナンバ指示子と、前記オペレーティングシステムの前記新バージョンを特定する新バージョン番号と、前記操作の順序付きリストを含むプロトコルバッファとを含む前記差分更新ファイルを組み立てるステップとを含む。
【０００５】
一例では、前記順序付きリスト内の１以上の操作は、それぞれ、データのチャンクを示すそれぞれのデータブロブに関連付けられる。ここで、前記差分更新ファイルは、前記それぞれのデータブロブを含むように組み立てられる。別の例では、前記順序付きリスト内の各操作は、クライアントデバイスのパーティションの１以上の特定のデータブロックに適用可能である。前記操作は、前記パーティション内の前記データブロックのうちの少なくとも１つが、前記オペレーティングシステムの前記新バージョンのための前記クライアントデバイスの新しいパーティション内の別のブロックにコピーされることになるコピー操作と、前記データブロックのうちの少なくとも所与の１つがメモリに読み込まれ、前記差分更新ファイルのデータブロブを用いて前記少なくとも１つの所与のデータブロックに対して差分ルーチンが実行される差分操作と、前記差分更新ファイルの選択されたデータブロブが前記新しいパーティション内の指定ブロックに書き込まれるように構成される置換操作と、圧縮されたデータブロブが前記差分更新ファイルに含まれ、前記オペレーティングシステムの前記新バージョンのための前記新しいパーティション内の選択された指定ブロックに書き込まれるように構成される解凍付き置換（replace with uncompression）操作とのうちの１以上のものを含む。
【０００６】
１つの代替形態では、前記順序付きリスト内の各操作は、ファイルオブジェクトに関連付けられ、前記方法は、ファイルオブジェクトごとにグラフ内に頂点を作成するステップと、各ブロックを表すベクトルを作成するステップとを更に含む。１つの変形形態では、前記方法は、各ブロックの前記ベクトルのリーダパラメータ及びライタパラメータを設定するステップと、異なるリーダ及びライタを有するブロックごとに、該ライタから該リーダへのエッジを前記グラフ内に作成するステップとを更に含む。前記エッジは、該エッジに関連付けられたソースファイル操作が開始する前に完了されるファイル操作を指し示す。一例では、各エッジは重みを有し、該重みは、そのエッジに関連付けられた前記グラフ内のブロックの数を特定する。別の例では、前記グラフがサイクルを含む場合、前記方法は、前記サイクルのそれぞれを切断するステップを更に含む。この場合、前記サイクルのうちの所与の１つを切断するステップは、前記所与のサイクルに関連付けられた最小重みのエッジを見つけることと、前記最小重みのエッジをカットすることとを含みうる。ここで、前記最小重みのエッジをカットすることは、エクステントをスクラッチスペースにコピーする操作を表す新しいノードを作成することと、前記最小重みのエッジのソースノードに前記新しいノードを指し示させることとを含みうる。そして、新しいコピー操作が該新しいコピー操作のコンシューマの前に行われることを保証するために、前記最小重みのエッジのデスティネーションノードから新しいエッジを作ることができる。
【０００７】
本発明の別の実施の形態によれば、コンピュータ可読オペレーティングシステムの更新を生成するデバイスが提供される。該デバイスは、前記オペレーティングシステムに関連付けられた差分更新情報を格納するメモリと、前記メモリに結合されたプロセッサとを備える。前記プロセッサは、前記オペレーティングシステムの現バージョンのバージョン番号を特定し、前記オペレーティングシステムの前記新バージョンに対して各通常ファイルにわたり反復を実行して、前記新バージョンに関連付けられた全てのデータブロックの前記順序付きリストを取得することを含めて、前記差分更新情報を用いて、前記オペレーティングシステムの前記現バージョンを前記オペレーティングシステムの新バージョンに更新する操作の順序付きリストを作成し、差分更新ファイルが実際の更新ファイルであることを示すマジックナンバ指示子と、前記オペレーティングシステムの前記新バージョンを特定する新バージョン番号と、前記操作の順序付きリストを含むプロトコルバッファとを含む前記差分更新ファイルを組み立て、前記差分更新ファイルを前記メモリに格納するように構成される。
【０００８】
一例では、前記順序付きリスト内の各操作は、ファイルオブジェクトに関連付けられ、前記プロセッサは、ファイルオブジェクトごとにグラフ内に頂点を作成し、各ブロックを表すベクトルを作成するように更に構成される。一代替形態では、前記プロセッサは、各ブロックの前記ベクトルのリーダパラメータ及びライタパラメータを設定し、異なるリーダ及びライタを有するブロックごとに、該ライタから該リーダへのエッジを前記グラフ内に作成するように更に構成される。前記エッジは、該エッジに関連付けられたソースファイル操作が開始する前に完了されるファイル操作を指し示す。この場合、前記グラフがサイクルを含む場合、前記プロセッサは、前記サイクルのそれぞれを切断するようにオプションで動作可能である。ここで、前記サイクルのうちの所与の１つを切断することは、前記所与のサイクルに関連付けられた最小重みのエッジを見つけることと、前記最小重みのエッジをカットすることとを含みうる。この場合、前記プロセッサは、エクステントをスクラッチスペースにコピーする操作を表す新しいノードを作成し、前記最小重みのエッジのソースノードに前記新しいノードを指し示させることによって前記最小重みのエッジをカットするように動作可能とすることができる。そして、新しいコピー操作が該新しいコピー操作のコンシューマの前に行われることを保証するために、前記最小重みのエッジのデスティネーションノードから新しいエッジを作ることができる。
【０００９】
更なる実施の形態では、有形のコンピュータ可読ストレージ媒体が、コンピュータプログラムのコンピュータ可読命令を格納する。前記命令は、コンピュータによって実行されると、コンピュータ可読オペレーティングシステムの更新を生成する方法を前記コンピュータに実行させる。前記方法は、前記オペレーティングシステムの現バージョンのバージョン番号を特定するステップと、プロセッサを用いて、前記オペレーティングシステムの前記現バージョンを前記オペレーティングシステムの新バージョンに更新する操作の順序付きリストを作成するステップであって、前記プロセッサは、前記オペレーティングシステムの前記新バージョンに対して各通常ファイルにわたり反復を実行して、前記新バージョンに関連付けられた全てのデータブロックの前記順序付きリストを取得する、作成するステップと、前記プロセッサを用いて、差分更新ファイルが実際の更新ファイルであることを示すマジックナンバ指示子と、前記オペレーティングシステムの前記新バージョンを特定する新バージョン番号と、前記操作の順序付きリストを含むプロトコルバッファとを含む前記差分更新ファイルを組み立てるステップとを含む。
【００１０】
一例では、前記順序付きリスト内の各操作は、ファイルオブジェクトに関連付けられ、前記方法は、ファイルオブジェクトごとにグラフ内に頂点を作成するステップと、各ブロックを表すベクトルを作成するステップとを更に含む。この場合、前記方法は、各ブロックの前記ベクトルのリーダパラメータ及びライタパラメータを設定するステップと、異なるリーダ及びライタを有するブロックごとに、該ライタから該リーダへのエッジを前記グラフ内に作成するステップとを更に含みうる。前記エッジは、該エッジに関連付けられたソースファイル操作が開始する前に完了されるファイル操作を指し示す。ここで、前記グラフがサイクルを含む場合、前記方法は、各所与のサイクルに関連付けられた最小重みのエッジを見つけるステップと、各サイクルの前記最小重みのエッジをカットすることとによって前記サイクルのそれぞれを切断するステップとを更に含みうる。前記最小重みのエッジをカットすることは、エクステントをスクラッチスペースにコピーする操作を表す新しいノードを作成することと、前記最小重みのエッジのソースノードに前記新しいノードを指し示させることとを含みうる。そして、新しいコピー操作が該新しいコピー操作のコンシューマの前に行われることを保証するために、前記最小重みのエッジのデスティネーションノードから新しいエッジを作ることができる。
【００１１】
更なる実施の形態では、クライアントデバイスが、オペレーティングシステムの現バージョンを格納するメモリと、前記メモリに結合されたプロセッサとを備える。前記プロセッサは、前記オペレーティングシステムの前記現バージョンの更新に関して遠隔デバイスに要求を送信し、ここで、該要求は、前記オペレーティングシステムの前記現バージョンを特定するバージョン番号を含み、前記遠隔デバイスから差分更新ファイルを受信し、ここで、該差分更新ファイルは、該差分更新ファイルが実際の更新ファイルであることを示すマジックナンバ指示子と、前記オペレーティングシステムの前記新バージョンを特定する新バージョン番号と、操作の順序付きリストを含むプロトコルバッファとを含み、前記マジックナンバを検証し、前記プロトコルバッファから前記操作の順序付きリストを抽出し、前記オペレーティングシステムの前記現バージョンを前記オペレーティングシステムの前記新バージョンに更新するために、前記操作の順序付きリストを実行することによって差分更新を実行するように構成される。
【００１２】
一例では、前記プロセッサは、前記差分更新ファイルが前記クライアントデバイスにストリーミングされている間に、前記メモリに前記差分更新ファイルを保存することなく、前記オペレーティングシステムの前記新バージョンへの前記オペレーティングシステムの前記差分更新を実行するように動作可能である。
【図面の簡単な説明】
【００１３】
【図１】本発明の態様によるファイルフォーマットを示す図である。
【図２】本発明の態様による、エッジをカットしてサイクルを切断するプロセスである。
【図３】本発明の態様による差分更新プロセスを示す図である。
【図４Ａ】本発明において用いるコンピュータシステムを示す図である。
【図４Ｂ】本発明において用いるコンピュータシステムを示す図である。
【発明を実施するための形態】
【００１４】
本発明の態様、特徴及び利点は、好ましい実施形態の以下の説明及び添付した図を参照して検討すると理解されるであろう。種々な図面における同じ参照符号は、同じ要素又は同様の要素を特定することができる。
【００１５】
オペレーティングシステムの随時異なる特徴が更新される。それらの更新は、あらかじめ規定された更新プロセスを実行するクライアントコンピュータに送信することができる。これは、クライアントに対するファイルの消去、変更及び／又は追加を伴うことができる。１つのプロセスでは、更新は、オペレーティングシステムプロバイダによって準備される。これは、差分更新ファイルを作成することを含みうる。差分更新ファイルは、どのような変更を行う必要があるかをクライアントに示す。そして、差分更新ファイルは、更新される各クライアントに送信される。クライアントは、望ましくは、ファイル内の操作を順次実行して更新を行う。
【００１６】
オペレーティングシステムを含むパーティションは、１以上のブロックとして構成することができ、各ブロックは、ファイル情報又はブックキーピング情報を含む。各ブロックは、例えば４ｋバイトとすることができるが、本発明は、これに限定されるものでもなければ、どの特定のブロックサイズにも限定されるものでもない。オペレーティングシステム自体は、コンピュータプロセッサ上で実行されるプログラム（例えば命令）及びデータを含み、コンピュータハードウェアリソースを管理し、様々なアプリケーションソフトウェアの効率的な実行のための共通のサービスを提供する。オペレーティングシステムを更新するとき、新しいパーティションを作成することができる。この新しいパーティションは、オペレーティングシステムの旧バージョンで事前にポピュレートされる。その結果得られた（ルートファイルシステムを包含する）インストールパーティション上の各ディスクブロックは、望ましくは、オペレーティングシステムベンダが（例えば、ベリファイドブートの場合）サーバ上で署名を受けることができるように、オペレーティングシステムベンダによって正確に（ビット単位で）指定される。
【００１７】
更新は可能な限り小さいことが望ましい。１つのシナリオでは、リブートすることなく、多くのデルタ（差分）更新をインストールすることができるように、更新は所定の位置に適用される。したがって、ユーザがバージョンＮにブートされ、Ｎ＋１がリリースされた場合、ユーザ（クライアント）は、Ｎ→Ｎ＋１に更新されたものをダウンロードし、その更新されたものをインストールする。そして、Ｎ＋２が登場したときでも、ユーザは依然としてＮ＋１にブートされる。そして、ユーザは、Ｎ＋１→Ｎ＋２更新をダウンロードし、その更新をＮ＋１上の所定の位置にインストールする。
【００１８】
一例では、クライアントは、更新サーバと連絡をとり、現在のインストールパーティション上にインストールされているシステムのバージョン番号を提供する。サーバは、クライアントにダウンロードされる増分（デルタ）更新をクライアントに提供する。デルタ更新ファイルは、インストールパーティションを旧（既存）バージョンから新バージョンにする、インストールパーティションに対して実行する操作の順序付きリストを含む。
【００１９】
望ましくは、更新ファイルは、クライアントによって実行される操作の順序付きリストである。各操作は、パーティションの特定のブロックに対して作用する。各操作は、デルタファイルの内部のオプションのデータ「ブロブ（blob）」を含みうる。用語「ブロブ」とは、バイトの任意の集まりを有することができる大きなデータチャンクを示す。「Ｃｏｐｙ（コピー）」、「Ｄｉｆｆ（ディフ）」、「Ｒｅｐｌａｃｅ（置換）」及び「Ｒｅｐｌａｃｅ ｗｉｔｈ Ｕｎｃｏｍｐｒｅｓｓｉｏｎ（解凍付き置換）」を含む数タイプのインストール操作がある。Ｃｏｐｙでは、現在のインストールパーティション内のブロックのうちの幾つかが新しいインストールパーティション内の他のブロックにコピーされる。Ｄｉｆｆの場合、幾つかのブロックがメモリ内に読み込まれ、付属のデータブロブを用いて２値差分ルーチンが実行される。その結果は、新しいインストールパーティション内の指定ブロックに書き込まれる。Ｒｅｐｌａｃｅの場合、付属のデータブロブが新しいインストールパーティション内の指定ブロックに書き込まれる。圧縮プロセスも実行することができ、圧縮プロセスにおいて、圧縮データブロブがクライアントに送信されて解凍され、その結果が新しいインストールパーティション内の指定ブロックに書き込まれる。この圧縮プロセスでは、Ｇｚｉｐ、Ｂｚｉｐ２又は別の圧縮アルゴリズムを用いることができる。
【００２０】
１つのシナリオでは、旧ファイルがインストールパーティションであることがパッチプログラムに指示される。プログラムにパーティション全体をメモリに読み込ませるのではなく、ファイルをメモリ内に入れるためにいずれのブロックを読み出すべきかがパッチプログラムに指示される。そして、パッチ操作がメモリ内で実行される。最後に、その結果は、デバイスの開始時ではないが、新しいインストールパーティションに直接書き込まれる。その代わり、プログラムは、いずれのブロックに結果を書き込むのかを伝えられる。
【００２１】
デルタ／差分更新ファイルは、以下の議論に従って生成することができる。更新ファイルフォーマットは、図１のファイルフォーマット１００に示されるようにすることができる。具体的には、フォーマットは、好ましくは、ファイルが実際に更新ファイルであることを示す「マジックナンバ」指示子又はサニティチェックを含む。一例では、マジックナンバは、「ＣｒＡＵ」等の短いフレーズの２値バージョンを含む４バイトを含む。次はバージョン番号であり、その後に、プロトコルバッファオフセット及び長さが続き、これらのそれぞれは８バイトとすることができる。プロトコルバッファそのものが次に続く。プロトコルバッファは、クライアントが順に実行する一連の命令である。次に、１以上のデータブロブが提供され、その後に、ファイル終端（ＥＯＦ）指示子が続く。順序はこの図に示されるようにすることができるが、所望の場合には、様々な構成要素を異なる順序にすることができる。
【００２２】
１つのシナリオでは、「エクステント」の概念が用いられる。エクステントはディスクブロックの連続した範囲である。例えば、ブロック｛１０，１１，１２，１３，１４，１５，１７，１８｝を指定するのではなく、｛（１０，６），（１７，２）｝（エクステントのリスト）を指定する方が簡単な場合がある。デルタ更新を生成する一例示のプロセスは、以下のとおりである。
【数１】
【００２３】
このマニフェスト（manifest）は、インストール操作のリストを示す。入力エクステントは、読み出されるブロックを示す。出力エクステントは、書き込まれるブロックを示す。
【００２４】
デルタ更新を生成するために、新しいファイルシステムに対して各通常ファイルにわたり反復が実行され、新しいファイルシステムが有する全てのデータブロックの順序付きリストが取得される。これは、以下のフォーマットを有するファイル構造に格納される。
【数２】
【００２５】
最終的に、各ファイルオブジェクトは、プロトコルバッファ内のＩｎｓｔａｌｌＯｐｅｒａｔｉｏｎ（インストール操作）メッセージに変換されることになる。ファイルごとに、該ファイルを圧縮する最適な方法を規定することが望ましい。４つのケースが存在する。１つのケースでは、ファイルは変化していない。他の３つのケースでは、ファイルは変化している。１つのシナリオでは、Ｂｚｉｐ２又は別の圧縮アルゴリズムを用いて、変化したファイルを最小サイズに圧縮することができる。別のシナリオでは、ファイルは変化しており、最小サイズに解凍される。第３のシナリオでは、ファイルは変化しており、最小のものをｂｉｎａｒｙ−ｄｉｆｆ（バイナリディフ）する。ファイルが新しい場合、これは、該ファイルがオペレーティングシステムの旧バージョンには存在しなかったことを意味するが、これらのケースのうちの２つのみが当てはまる。データは、全て送信することもできるし、圧縮して全て送信することもできる。
【００２６】
本発明の１つの態様によれば、ファイルオブジェクトごとにグラフに頂点が作成される。グラフとともに、ベクトルがインストールパーティション内の各ブロックを表すのに作成される。
【数３】
【００２７】
その後、プロセスは、各ファイルオブジェクト内の各ブロックを通過する。ブロックごとに、リーダパラメータ及びライタパラメータがブロックのベクトルについて設定される。
【００２８】
次に、反復がブロックのアレイを通して実行される。異なるリーダ及びライタ（ともに非ヌルである）を有するブロックごとに、エッジ（矢印）がライタからリーダへのグラフに作成される。（有向）グラフ内のエッジは、該エッジのソースファイル操作が開始する前に完了しなければならないファイル操作を指し示す。したがって、このプロセスは、異なるファイル操作によってブロックの読み出し及び書き込みの双方が行われる場合、該ブロックが書き込まれる前に読み出されることを確実にするように試みる。エッジはグラフ内のブロックを表し、したがって、エッジの重みはブロック数である。
【００２９】
このとき、結果は、サイクルを備えたグラフを有する可能性がある。サイクルは切断されるべきである。サイクルは、「Finding all the Elementary Circuits of a Directed Graph」（SIAM J. Comput., vol. 4 no. 1, March 1975）に述べられているようなDonald B. Johnsonの回路発見アルゴリズムを用いて見つけることができる。この文献の開示内容全体は、引用することにより本明細書の一部をなすものとする。サイクルは、「Tarjan's Strongly Connected Components Algorithm」（David Eppstein, Ed., Wikipedia）に述べられているようなTarjanのアルゴリズムを用いて見つけることもできる。この文献の開示内容全体は、引用することにより本明細書の一部をなすものとする。サイクルごとに、最小重みのエッジが見つけられカットされる。エッジは以下のようにカットすることができる。先ず、幾つかのエクステントをスクラッチスペースにコピーする操作を表す新しいノードを作成する。次に、エッジのソースノードに新しいノードを指し示させる。ここで、カットされたエッジのデスティネーションノードから新しいノードへのエッジを作成して、新しいコピー操作がコピーのコンシューマの前に行われることを強制することができる。好ましくは、エッジがカットされることによって表されるブロックからではなく、スクラッチスペースから読み出すように、カットされたエッジのデスティネーションノードを修正する。
【００３０】
エッジをカットしてサイクルを切断する一例は、図２のプロセス２００に示される。矢印は、指し示される側の操作が指し示す側の操作の前に行われる必要があり、指し示す側の操作が、指し示される側によって必要とされるデータを上書きするので、その順序で行われることを必要とすることを示す。この図に示すように、Ｓ２０２において、操作Ａが、ブロック３を読み出し、ブロック４を書き込む。そして、Ｓ２０４において、操作Ｂが、ブロック４を読み出し、ブロック１０を書き込む。サイクルは、ＡとＢとの間のエッジ（矢印２０６）をカットすることによって切断される。これは、ｔｅｍｐブロックＴを用いることによって行うことができる。したがって、図示するように、Ｓ２０８において、操作Ａが、ブロック３を読み出し、ブロック４を書き込む。Ｓ２１０において、操作Ｃが、ブロック４を読み出し、ブロックＴを書き込む。そして、Ｓ２１２において、操作Ｂ’が、ブロックＴを読み出し、ブロック１０を書き込む。サイクルが切断されると、トポロジカルソートを用いて全てのノードを順序付けることができる。それは、全てのファイルデータブロックのインストールをカバーしている。
【００３１】
一例では、Ｂ’−＞Ｃ−＞Ａ−＞Ｔｅｍｐにように、エッジを選んでカットすることが可能である。この場合、Ｔｅｍｐ操作は、ブロックＡをｔｅｍｐエリアにコピーする。ＢはＢ’に修正され、次に、Ｂ’はｔｅｍｐエリアから読み出される。一方、第２のエッジ（例えば、Ｃ−＞Ａ）が切断される場合、その結果は、Ｂ’−＞Ｃ−＞Ｔｅｍｐ２及びＡ’−＞Ｔｅｍｐとなる。この結果、２つの完全に独立したグラフが得られ、操作の最終的な順序は以下のように配列することができる。
Ｔｅｍｐ２（クライアントはこれを最初に実行する）
Ｃ
Ｂ’
Ｔｅｍｐ
Ａ’（クライアントはこれを最後に実行する）
【００３２】
しかしながら、この場合、Ｂ’は、Ｔｅｍｐ操作によって書き込まれたデータを読み出すが、ＴｅｍｐはＢ’の後に行われる。これは、Ａ−＞Ｂがエッジをカットされたときに行われたグラフ変換が、ＴｅｍｐがＢ’の前に行われなければならないことを特に明確に指定していなかったことから起こる場合がある。この状況を回避するために、別のエッジが、これを明示的にするために追加される。その結果は以下のようになる。
Ａ−＞Ｂ−＞Ｃ−＞Ａ（オリジナル）
Ａ−＞Ｂをカットして以下を取得する：
Ｂ’−＞Ｃ−＞Ａ−＞Ｔｅｍｐ＜−Ｂ’
次に、Ｃ−＞Ａをカットして以下を取得する：
Ｂ’−＞Ｃ'−＞Ｔｅｍｐ２＜−Ａ−＞Ｔｅｍｐ＜−Ｂ’
次に、操作の最終的な順序がグラフに基づいて選ばれ、操作は正しい順序で行われる。
【００３３】
例示のプロセスが図３に示されている。ステージ１において、ディスクイメージがスキャンされる。ブロックインデックス（０〜７）は、異なるイメージ（例えば、「ｓｈ」、「ｆｏｏ」、「ｂａｒ」及び「ｄｏｇ」）に関連付けることができる。新しいイメージは、同じブロック又は異なるブロックに関連付けることができる。したがって、ここでは、「ｆｏｏ」は、ブロック４の代わりにブロック２及び３に関連付けることができる。「ｓｈ」は、ブロック２及び３の代わりにブロック４及び５に関連付けることができる。「ｂａｒ」は、ブロック５の代わりにブロック６に関連付けることができる。そして、新しいイメージ「ｃａｔ」は、ブロック７に関連付けることができる。
【００３４】
ステージ２において、ファイル操作が作成される。これは、新しいパーティション上のファイルに対応する。この後に、ブロックベクトルが続く。ブロックベクトルは順序付きリストであり、ブロックベクトルにおいて、各要素は、所与のブロックのファイル操作を含む。各イメージは、１以上のソースブロック及び１以上のデスティネーションブロックを有することができる。したがって、「ｆｏｏ」のソースブロックはブロック４であり、「ｆｏｏ」のデスティネーションブロックは、「ｄｓｔ:（２，２）」として示され、これは、最初のブロックがブロック２であり、２つのブロックが割り当てられていることを示している。この部分は、各イメージをクライアントにどのように提供することができるのかも示している。したがって、ｆｏｏ及びｂａｒは、ｂｓｄｉｆｆ等の２値差分アルゴリズムを用いて提供することができ、ｓｈは、単にコピーのみすることができ、ｃａｔは、圧縮なしで全体を送信することができる。Ｂｓｄｉｆｆは２つのファイル間の差分を計算する既知のアルゴリズムである。
【００３５】
ステージ３に示すように、エッジ重み（例えば、１又は２）がブロック数に等しいグラフが作成される。ステージ４において、サイクルが切断される。望ましくは、サイクル（複数の場合もあり）は、各サイクルにおける最小重みエッジをカットすることによってカットされる。したがって、この例では、ｓｈからｆｏｏへの矢印（重み１を有する）を含むサイクルが切断され、修正されたｆｏｏ（ｆｏｏ’）が得られる。そして、ステージ５において、トポロジカルソートの結果得られた最終的な順序が示される。これは、クライアント上で実行される順序である。
【００３６】
クライアントは、ファイルデータを設定した後、残りのデータをアンジップして全て非ファイルデータブロックにする最終的なＩｎｓｔａｌｌＯｐｅｒａｔｉｏｎを用いて非ファイルデータブロックに上書きする。一般的な例では、これは、約２メガバイトの圧縮データである。このデータに対してデルタ圧縮プロセスを実行することが実現可能な場合がある。
【００３７】
（全ての操作をリストする）プロトコルバッファは、ファイルの先頭に現れるので、更新をディスクに保存する必要はない。更新は、サーバからのストリーミング中に適用することができる。更新がＯＳベンダによって署名されることを確実にすることが望ましい。システムは、更新の適用を開始することができ、デルタ更新シグネチャの検証後になるまで、更新をブート可能にマーキングしないことができる。
【００３８】
ここに提示した実施形態は、実際に最良の圧縮比を与えることがわかっている。これによって、オペレーティングシステムベンダは、将来の代替的な圧縮方式を用いることも可能になる。例えば、Ｇｏｏｇｌｅによって開発された１つのプロセスはＣｏｕｒｇｅｔｔｅであり、これは、ｂｓｄｉｆｆに取って代わることができる。
【００３９】
別の可能な解決策は、パーティション全体をデルタ圧縮することである。しかしながら、ｂｓｄｉｆｆは、そのメモリ要件が高すぎるために、このシナリオでは動作することができない。パッチ中、ｂｓｄｉｆｆは、オリジナルのファイル及び新しいファイルを格納するのに十分なメモリを必要とし、このメモリは１ギガバイトを超える場合がある。別のデルタ圧縮プログラムであるＸｄｅｌｔａは、スライディングウィンドウを用いる。テストにおいて、このＸｄｅｌｔａは、圧縮が不十分な結果となった（例えば、数百メガバイト）。更なる代替形態はｒｄｉｆｆを用いることであり、ｒｄｉｆｆは、変更されたブロックのみをデルタファイルに格納することによって動作する。ｒｄｉｆｆは、ブロックを整列する必要がないように、スライディングウィンドウを用いる。パーティション全体のｒｄｉｆｆデルタは、テストされると、１０４メガバイトであった。これは、上述した手順に従って用いることができるおよそ１０メガバイトを優に超えている。
【００４０】
今後、ファイルレベルにおいて、ｒｄｉｆｆスタイル（すなわち、ｒｓｙｎｃスタイル）のデルタ圧縮を用いることが可能な場合がある。これは、今後、ｂｓｄｉｆｆとともに用いることができる。
【００４１】
本発明の態様による更新手順は、以下の例示のコンピュータシステムを用いて実施することができる。図４Ａは、本発明において単独で用いることもできるし、ネットワークされた構成で用いることもできる様々なコンピューティングデバイスを示すコンピュータシステムの概略図を示している。例えば、この図は、複数のコンピュータ３０２、３０４、３０６及び３０８と、移動電話３１０及びＰＤＡ３１２等のポータブル電子デバイス等の他のタイプのデバイスとを有するコンピュータネットワーク３００を示している。しかしながら、本発明は、そのように限定されるものではなく、ネットブック及びパッド型ハンドヘルドコンピュータ（図示せず）を含む他のデバイスも用いることができる。そのようなデバイスは、ローカル接続若しくは直接接続３１４を介して相互接続することができ、及び／又はＬＡＮ、ＷＡＮ、インターネット等の通信ネットワーク３１６を介して結合することができる。通信ネットワーク３１６は、有線又は無線とすることができる。
【００４２】
各デバイスは、例えば、１以上の処理デバイスを含むことがあり、キーボード３１８及びマウス３２０等のユーザ入力、並びに／又はペン入力、ジョイスティック、ボタン、タッチスクリーン等の様々な他のタイプの入力デバイスに加えて、例えば、ＣＲＴ、ＬＣＤ、プラズマスクリーンモニタ、ＴＶ、プロジェクタ等を含みうるディスプレイ３２２を有することができる。各コンピュータ３０２、３０４、３０６及び３０８は、パーソナルコンピュータやサーバ等でありうる。単なる例として、コンピュータ３０２及び３０６は、パーソナルコンピュータとすることができる一方、コンピュータ３０４はサーバとすることができ、コンピュータ３０８はラップトップとすることができる。
【００４３】
図４Ｂに示すように、コンピュータ３０２及び３０４等の各コンピュータは、プロセッサ３２４、メモリ／ストレージ３２６及びコンピュータ内に通常存在する他の構成要素を含む。例えば、メモリ／ストレージ３２６は、プロセッサ３２４によってアクセス可能な情報を格納する。この情報は、プロセッサ３２４が実行することができる命令３２８と、プロセッサが検索、操作又は格納することができるデータ３３０とを含む。サーバにおける命令３２８は、１以上のクライアントデバイスによってインストールされる差分更新を作成する操作を含みうる。そして、クライアントデバイスにおける命令は、差分更新を実行する操作を含みうる。
【００４４】
データは、クライアントデバイスに対するサービスのためにデータベースに保持された１以上の差分更新を含みうる。メモリ／ストレージは、ハードドライブやＲＯＭやＲＡＭやＣＤ−ＲＯＭやフラッシュメモリや書き込み可能メモリ又は読み出し専用メモリ等の、プロセッサによってアクセス可能な情報を格納可能な任意のタイプのもの又は任意のデバイスでありうる。プロセッサ３２４は、Intel Corporation又はAdvanced Micro Devices社からのプロセッサ等の、任意の個数の既知のプロセッサを含みうる。代替的には、プロセッサは、ＡＳＩＣ又は他の処理デバイス等の、操作を実行する専用コントローラでありうる。
【００４５】
命令３２８は、プロセッサ（複数の場合もあり）によって直接的（マシンコード等）又は間接的（スクリプト等）に実行される任意の一組の命令を含みうる。その点について、用語「命令」、「ステップ」及び「プログラム」とは、本明細書では交換可能に用いることができる。命令は、オブジェクトコード又はソースコードのモジュール等、任意のコンピュータ言語又はフォーマットにより格納することができる。本発明による機能、方法及び命令のルーチンは、以下により詳細に説明される。
【００４６】
データ３３０は、命令３２８に従って、プロセッサ３２４が検索、格納又は修正することができる。データは、データ集合体として格納することができる。例えば、本発明は、どの特定のデータ構造によっても限定されないが、データは、コンピュータレジスタ、複数の異なるフィールド及びレコードを有するテーブルとしてリレーショナルデータベース、ＸＭＬ文書としてウェブページキャッシュ等に格納することができる。
【００４７】
データは、限定するものではないが２値、ＡＳＣＩＩ又はＵｎｉｃｏｄｅ等の任意のコンピュータ可読フォーマットにフォーマットすることもできる。その上、データは、説明文、独自のコード、ポインタ、他のメモリ（他のネットワークロケーションを含む）に格納されたデータへの参照子、又は関連データを計算するのに或る機能によって用いられる情報等、関連情報を特定するのに十分な任意の情報を含むことがある。さらに、所与のアイテムは、１以上のファイル、データベース、ウェブキャッシュに格納されたデータセット等を含みうる。データのサイズ及び内容に応じて、該データの一部ずつを別々に格納又は別の方法により保持することもできる。
【００４８】
プロセッサ３２４及びメモリ３２６は、図４Ｂでは、同じブロック内に存在するものとして機能的に示されているが、プロセッサ及びメモリは、実際には、同じ物理ハウジング又は物理ロケーション内に格納されることもあるし格納されないこともある複数のプロセッサ及びメモリを含みうることが理解されるであろう。例えば、命令及びデータの幾つか又は全ては、着脱可能なＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ又はフラッシュドライブ、及び読み出し専用コンピュータチップ内の他のものに格納することができる。命令及びデータの幾つか又は全ては、プロセッサから物理的に遠隔ではあるが、それでもプロセッサによってアクセス可能なロケーションに格納することができる。同様に、プロセッサは、実際には、並列に動作することもあるし動作しないこともあるプロセッサの集合体を含みうる。データは、分散させることができ、ハードドライブ等の複数のメモリ３２６にわたって格納することができる。
【００４９】
１つの態様では、サーバ３０４は、１以上のクライアントコンピュータ３０２、３０６及び／又は３０８、並びに移動電話３１０及びＰＤＡ３１２等のデバイスと通信することができる。各クライアントコンピュータ又は他のクライアントデバイスは、プロセッサ、メモリ及び命令、並びに１以上のユーザ入力デバイス３１８、３２０及びディスプレイ３２２等のユーザ出力デバイスを用いてサーバ３０４と同様に構成することができる。各クライアントコンピュータは、中央処理装置（「ＣＰＵ」）、ディスプレイ、ＣＤ−ＲＯＭドライブ若しくはＤＶＤドライブ、ハードドライブ、マウス、キーボード、タッチスクリーン、スピーカ、マイク、モデム及び／又は（電話やケーブル等の）ルータ、並びにこれらの要素を互いに接続するのに用いられる構成要素の全て等の、パーソナルコンピュータにおいて通常見られる全ての構成要素を有する、人による使用を対象とした汎用コンピュータとすることができる。
【００５０】
サーバ３０４、ユーザコンピュータ及び他のデバイスは、ネットワーク３１６を介する等により、他のコンピュータと直接通信及び間接通信が可能である。図４Ａ及び図４Ｂには少数のコンピューティングデバイスしか示されていないが、一般的なシステムは、各異なるコンピュータがネットワークの異なるノードに存在する、多数の接続されたサーバ及びクライアントを含むことができることが理解されるべきである。ネットワーク３１６、及び介在するノードは、１以上の企業に独自の通信プロトコル、Ｅｔｈｅｒｎｅｔ（登録商標）、ＷｉＦｉ、Ｂｌｕｅｔｏｏｔｈ（登録商標）又はＴＣＰ／ＩＰを用いるインターネット、イントラネット、仮想プライベートネットワーク、ワイドエリアネットワーク、ローカルネットワーク、プライベートネットワークを含む様々な構成及びプロトコルを備えうる。
【００５１】
任意の介在するノードを含むネットワークにわたる通信は、モデム（例えば、ダイヤルアップ又はケーブル）、ネットワークインタフェース及び無線インタフェース等、他のコンピュータへのデータの送信及び他のコンピュータからのデータの送信が可能な任意のデバイスによって容易にすることができる。サーバ３０４はウェブサーバでありうる。上述したように、情報が送信又は受信されると、或る利点が得られるが、本発明の他の態様は、情報のどの特定の送信方法にも限定されるものではない。例えば、幾つかの態様では、情報は、ディスク、テープ、ＣＤ−ＲＯＭ等の媒体を介して送信することもできるし、ダイヤルアップモデムを介して２つのコンピュータシステム間で直接送信することもできる。他の態様では、或る情報は、非電子フォーマットで送信することができ、システム内に手動で入力することができる。
【００５２】
その上、本明細書で説明したシステム及び方法によるコンピュータ及びユーザデバイスは、命令の処理と、人間及び他のコンピュータへのデータの送信と、人間及び他のコンピュータからのデータの送信とが可能な任意のデバイスを含みうる。他のコンピュータは、ローカルストレージ機能のないネットワークコンピュータと、ＰＤＡ３１２等のモデム付きＰＤＡと、移動電話３１０等のインターネット対応無線電話と、ネットブックと、パッド型ハンドヘルドコンピュータとを含む。
【００５３】
図４Ａに示すように、ネットワーク３００は、クライアントデバイスに差分更新をサービス提供する更新データベース３３２も含みうる。更新データベースは、サーバ３０４に直接的又は間接的に結合することができる。一代替形態では、更新データベース３３２は、サーバ３０４の一部とすることもできるし、別の方法でサーバ３０４に論理的に関連付けることもできる。
【００５４】
本明細書では、本発明を特定の実施形態に関して説明してきたが、これらの実施形態は本発明の原理及び用途の単なる例示にすぎないことが理解されるべきである。したがって、例示の実施形態に対して多数の修正を行うことができること、及び添付の特許請求の範囲によって規定される本発明の趣旨及び範囲から逸脱することなく他の構成を考案することができることが理解されるべきである。例えば、或る実施形態はオペレーティングシステムについて示されているが、本発明の態様による差分更新は、他のソフトウェアパッケージ、アプリケーション及びサービスとともに用いることができる。さらに、特定のプロセスが添付図面において特定の順序で示されているが、そのような順序が本明細書において明白に述べられていない限り、そのようなプロセスは、どの特定の順序にも限定されるものではなく、異なる順序で又は並列に実行することができる。そして、特に別段に指定がない限り、追加のプロセスを追加することもできるし、他のプロセスを省くこともできる。
【産業上の利用可能性】
【００５５】
本発明は、限定するものではないが、コンピュータシステム操作と、そのようなコンピュータシステムのアプリケーションの更新とを含む幅広い産業上の利用可能性を享有する。
【特許請求の範囲】
【請求項１】
コンピュータ可読オペレーティングシステムの更新を生成する方法であって、
前記オペレーティングシステムの現バージョンのバージョン番号を特定するステップと、
プロセッサを用いて、前記オペレーティングシステムの前記現バージョンを前記オペレーティングシステムの新バージョンに更新する操作の順序付きリストを作成するステップであって、前記プロセッサは、前記オペレーティングシステムの前記新バージョンに対して各通常ファイルにわたり反復を実行して、前記新バージョンに関連付けられた全てのデータブロックの前記順序付きリストを取得する、作成するステップと、
前記プロセッサを用いて、差分更新ファイルが実際の更新ファイルであることを示すマジックナンバ指示子と、前記オペレーティングシステムの前記新バージョンを特定する新バージョン番号と、前記操作の順序付きリストを含むプロトコルバッファとを含む前記差分更新ファイルを組み立てるステップと
を含んでなる、コンピュータ可読オペレーティングシステムの更新を生成する方法。
【請求項２】
前記順序付きリスト内の１以上の操作は、データのチャンクを示すそれぞれのデータブロブにそれぞれ関連付けられ、前記差分更新ファイルは、前記それぞれのデータブロブを含むように組み立てられるものである、請求項１に記載の方法。
【請求項３】
前記順序付きリスト内の前記各操作は、クライアントデバイスのパーティションの１以上の特定のデータブロックに適用可能であり、前記操作は、前記パーティション内の前記データブロックのうちの少なくとも１つが、前記オペレーティングシステムの前記新バージョンのための前記クライアントデバイスの新しいパーティション内の別のブロックにコピーされることになるコピー操作と、前記データブロックのうちの少なくとも所与の１つがメモリに読み込まれ、前記差分更新ファイルのデータブロブを用いて前記少なくとも１つの所与のデータブロックに対して差分ルーチンが実行される差分操作と、前記差分更新ファイルの選択されたデータブロブが前記新しいパーティション内の指定ブロックに書き込まれるように構成される置換操作と、圧縮されたデータブロブが前記差分更新ファイルに含まれ、前記オペレーティングシステムの前記新バージョンのための前記新しいパーティション内の選択された指定ブロックに書き込まれるように構成される解凍付き置換操作とのうちの１以上のものを含む、請求項１又は２に記載の方法。
【請求項４】
前記順序付きリスト内の前記各操作は、ファイルオブジェクトに関連付けられており、前記方法は、
前記ファイルオブジェクトごとにグラフ内に頂点を作成することと、
前記各ブロックを表すベクトルを作成することと、
を更に含む、請求項１〜３のいずれか１項に記載の方法。
【請求項５】
前記各ブロックの前記ベクトルのリーダパラメータ及びライタパラメータを設定するステップと、
異なるリーダ及びライタを有する前記ブロックごとに、該ライタから該リーダへのエッジを前記グラフ内に作成するステップであって、前記エッジは、該エッジに関連付けられたソースファイル操作が開始する前に完了されるファイル操作を指し示すものである、作成するステップと
を更に含む、請求項４に記載の方法。
【請求項６】
前記各エッジは重みを有し、該重みは、そのエッジに関連付けられた前記グラフ内のブロックの数を特定する、請求項５に記載の方法。
【請求項７】
前記グラフがサイクルを含む場合、前記方法は、
前記サイクルのそれぞれを切断するステップを更に含む、請求項５又は６に記載の方法。
【請求項８】
前記サイクルのうちの所与の１つを切断するステップは、
前記所与のサイクルに関連付けられた最小重みのエッジを見つけることと、
前記最小重みのエッジをカットすることと
を含むものである、請求項７に記載の方法。
【請求項９】
前記最小重みのエッジをカットすることは、
エクステントをスクラッチスペースにコピーする操作を表す新しいノードを作成することと、
前記最小重みのエッジのソースノードに前記新しいノードを指し示させることと
を含むものである、請求項８に記載の方法。
【請求項１０】
新しいコピー操作が該新しいコピー操作のコンシューマの前に行われることを保証するために、前記最小重みのエッジのデスティネーションノードから新しいエッジが作られるものである、請求項９に記載の方法。
【請求項１１】
コンピュータ可読オペレーティングシステムの更新を生成するデバイスであって、
前記オペレーティングシステムに関連付けられた差分更新情報を格納するメモリと、
前記メモリに結合されたプロセッサであって、
前記オペレーティングシステムの現バージョンのバージョン番号を特定し、
前記オペレーティングシステムの前記新バージョンに対して各通常ファイルにわたり反復を実行して、前記新バージョンに関連付けられた全てのデータブロックの前記順序付きリストを取得することを含めて、前記差分更新情報を用いて、前記オペレーティングシステムの前記現バージョンを前記オペレーティングシステムの新バージョンに更新する操作の順序付きリストを作成し、
差分更新ファイルが実際の更新ファイルであることを示すマジックナンバ指示子と、前記オペレーティングシステムの前記新バージョンを特定する新バージョン番号と、前記操作の順序付きリストを含むプロトコルバッファとを含む前記差分更新ファイルを組み立て、
前記差分更新ファイルを前記メモリに格納する、ように構成されるプロセッサと
を備えてなる、コンピュータ可読オペレーティングシステムの更新を生成するデバイス。
【請求項１２】
前記順序付きリスト内の前記各操作は、ファイルオブジェクトに関連付けられ、前記プロセッサは、
前記ファイルオブジェクトごとにグラフ内に頂点を作成し、
前記各ブロックを表すベクトルを作成する、
ように更に構成される、請求項１１に記載のデバイス。
【請求項１３】
前記プロセッサは、
前記各ブロックの前記ベクトルのリーダパラメータ及びライタパラメータを設定し、
異なるリーダ及びライタを有する前記ブロックごとに、該ライタから該リーダへのエッジを前記グラフ内に作成し、ここで、前記エッジは、該エッジに関連付けられたソースファイル操作が開始する前に完了されるファイル操作を指し示す、
ように更に構成される、請求項１２に記載のデバイス。
【請求項１４】
前記グラフがサイクルを含む場合、前記プロセッサは、前記サイクルのそれぞれを切断するように更に動作可能である、請求項１３に記載のデバイス。
【請求項１５】
前記サイクルのうちの所与の１つを切断することは、
前記所与のサイクルに関連付けられた最小重みのエッジを見つけることと、
前記最小重みのエッジをカットすることと
を含むものである、請求項１４に記載のデバイス。
【請求項１６】
前記プロセッサは、
エクステントをスクラッチスペースにコピーする操作を表す新しいノードを作成し、
前記最小重みのエッジのソースノードに前記新しいノードを指し示させる、
ことによって、前記最小重みのエッジをカットするように動作可能である、請求項１５に記載のデバイス。
【請求項１７】
新しいコピー操作が該新しいコピー操作のコンシューマの前に行われることを保証するために、前記最小重みのエッジのデスティネーションノードから新しいエッジが作られる、請求項１６に記載のデバイス。
【請求項１８】
コンピュータプログラムのコンピュータ可読命令が格納される有形のコンピュータ可読ストレージ媒体であって、前記命令は、コンピュータによって実行されると、コンピュータ可読オペレーティングシステムの更新を生成する手順を前記コンピュータに実行させ、前記手順は、
前記オペレーティングシステムの現バージョンのバージョン番号を特定する手順と、
プロセッサを用いて、前記オペレーティングシステムの前記現バージョンを前記オペレーティングシステムの新バージョンに更新する操作の順序付きリストを作成する手順であって、前記プロセッサは、前記オペレーティングシステムの前記新バージョンに対して各通常ファイルにわたり反復を実行して、前記新バージョンに関連付けられた全てのデータブロックの前記順序付きリストを取得する、作成する手順と、
前記プロセッサを用いて、差分更新ファイルが実際の更新ファイルであることを示すマジックナンバ指示子と、前記オペレーティングシステムの前記新バージョンを特定する新バージョン番号と、前記操作の順序付きリストを含むプロトコルバッファとを含む前記差分更新ファイルを組み立てる手順と
を含んでなる、コンピュータプログラムのコンピュータ可読命令が格納される有形のコンピュータ可読ストレージ媒体。
【請求項１９】
前記順序付きリスト内の前記各操作は、ファイルオブジェクトに関連付けられており、
前記ファイルオブジェクトごとにグラフ内に頂点を作成する手順と、
前記各ブロックを表すベクトルを作成する手順と
を更に含む、請求項１８に記載のストレージ媒体。
【請求項２０】
前記各ブロックの前記ベクトルのリーダパラメータ及びライタパラメータを設定する手順と、
異なるリーダ及びライタを有する前記ブロックごとに、該ライタから該リーダへのエッジを前記グラフ内に作成する手順であって、前記エッジは、該エッジに関連付けられたソースファイル操作が開始する前に完了されるファイル操作を指し示す、作成する手順と
を更に含む、請求項１９に記載のストレージ媒体。
【請求項２１】
前記グラフがサイクルを含む場合には、
各所与のサイクルに関連付けられた最小重みのエッジを見つけることと、
前記各サイクルの前記最小重みのエッジをカットすることと
によって前記サイクルのそれぞれを切断する手順を更に含む、請求項２０に記載のストレージ媒体。
【請求項２２】
前記最小重みのエッジをカットすることは、
エクステントをスクラッチスペースにコピーする操作を表す新しいノードを作成することと、
前記最小重みのエッジのソースノードに前記新しいノードを指し示させることと
を含むものである、請求項２１に記載のストレージ媒体。
【請求項２３】
新しいコピー操作が該新しいコピー操作のコンシューマの前に行われることを保証するために、前記最小重みのエッジのデスティネーションノードから新しいエッジが作られる、請求項２２に記載のストレージ媒体。
【請求項２４】
オペレーティングシステムの現バージョンを格納するメモリと、
前記メモリに結合されたプロセッサと
を備えてなる、クライアントデバイスであって、
前記プロセッサは、
前記オペレーティングシステムの前記現バージョンの更新に関して遠隔デバイスに要求を送信し、ここで、該要求は、前記オペレーティングシステムの前記現バージョンを特定するバージョン番号を含み、
前記遠隔デバイスから差分更新ファイルを受信し、ここで、該差分更新ファイルは、該差分更新ファイルが実際の更新ファイルであることを示すマジックナンバ指示子と、前記オペレーティングシステムの前記新バージョンを特定する新バージョン番号と、操作の順序付きリストを含むプロトコルバッファとを含み、
前記マジックナンバを検証し、
前記プロトコルバッファから前記操作の順序付きリストを抽出し、
前記オペレーティングシステムの前記現バージョンを前記オペレーティングシステムの前記新バージョンに更新するために、前記操作の順序付きリストを実行することによって差分更新を実行する、
ように構成されている、クライアントデバイス。
【請求項２５】
前記プロセッサは、前記差分更新ファイルが前記クライアントデバイスにストリーミングされている間に、前記メモリに前記差分更新ファイルを保存することなく、前記オペレーティングシステムの前記新バージョンへの前記オペレーティングシステムの前記差分更新を実行するように動作可能である、請求項２４に記載のクライアントデバイス。
【請求項１】
コンピュータ可読オペレーティングシステムの更新を生成する方法であって、
前記オペレーティングシステムの現バージョンのバージョン番号を特定するステップと、
プロセッサを用いて、前記オペレーティングシステムの前記現バージョンを前記オペレーティングシステムの新バージョンに更新する操作の順序付きリストを作成するステップであって、前記プロセッサは、前記オペレーティングシステムの前記新バージョンに対して各通常ファイルにわたり反復を実行して、前記新バージョンに関連付けられた全てのデータブロックの前記順序付きリストを取得する、作成するステップと、
前記プロセッサを用いて、差分更新ファイルが実際の更新ファイルであることを示すマジックナンバ指示子と、前記オペレーティングシステムの前記新バージョンを特定する新バージョン番号と、前記操作の順序付きリストを含むプロトコルバッファとを含む前記差分更新ファイルを組み立てるステップと
を含んでなる、コンピュータ可読オペレーティングシステムの更新を生成する方法。
【請求項２】
前記順序付きリスト内の１以上の操作は、データのチャンクを示すそれぞれのデータブロブにそれぞれ関連付けられ、前記差分更新ファイルは、前記それぞれのデータブロブを含むように組み立てられるものである、請求項１に記載の方法。
【請求項３】
前記順序付きリスト内の前記各操作は、クライアントデバイスのパーティションの１以上の特定のデータブロックに適用可能であり、前記操作は、前記パーティション内の前記データブロックのうちの少なくとも１つが、前記オペレーティングシステムの前記新バージョンのための前記クライアントデバイスの新しいパーティション内の別のブロックにコピーされることになるコピー操作と、前記データブロックのうちの少なくとも所与の１つがメモリに読み込まれ、前記差分更新ファイルのデータブロブを用いて前記少なくとも１つの所与のデータブロックに対して差分ルーチンが実行される差分操作と、前記差分更新ファイルの選択されたデータブロブが前記新しいパーティション内の指定ブロックに書き込まれるように構成される置換操作と、圧縮されたデータブロブが前記差分更新ファイルに含まれ、前記オペレーティングシステムの前記新バージョンのための前記新しいパーティション内の選択された指定ブロックに書き込まれるように構成される解凍付き置換操作とのうちの１以上のものを含む、請求項１又は２に記載の方法。
【請求項４】
前記順序付きリスト内の前記各操作は、ファイルオブジェクトに関連付けられており、前記方法は、
前記ファイルオブジェクトごとにグラフ内に頂点を作成することと、
前記各ブロックを表すベクトルを作成することと、
を更に含む、請求項１〜３のいずれか１項に記載の方法。
【請求項５】
前記各ブロックの前記ベクトルのリーダパラメータ及びライタパラメータを設定するステップと、
異なるリーダ及びライタを有する前記ブロックごとに、該ライタから該リーダへのエッジを前記グラフ内に作成するステップであって、前記エッジは、該エッジに関連付けられたソースファイル操作が開始する前に完了されるファイル操作を指し示すものである、作成するステップと
を更に含む、請求項４に記載の方法。
【請求項６】
前記各エッジは重みを有し、該重みは、そのエッジに関連付けられた前記グラフ内のブロックの数を特定する、請求項５に記載の方法。
【請求項７】
前記グラフがサイクルを含む場合、前記方法は、
前記サイクルのそれぞれを切断するステップを更に含む、請求項５又は６に記載の方法。
【請求項８】
前記サイクルのうちの所与の１つを切断するステップは、
前記所与のサイクルに関連付けられた最小重みのエッジを見つけることと、
前記最小重みのエッジをカットすることと
を含むものである、請求項７に記載の方法。
【請求項９】
前記最小重みのエッジをカットすることは、
エクステントをスクラッチスペースにコピーする操作を表す新しいノードを作成することと、
前記最小重みのエッジのソースノードに前記新しいノードを指し示させることと
を含むものである、請求項８に記載の方法。
【請求項１０】
新しいコピー操作が該新しいコピー操作のコンシューマの前に行われることを保証するために、前記最小重みのエッジのデスティネーションノードから新しいエッジが作られるものである、請求項９に記載の方法。
【請求項１１】
コンピュータ可読オペレーティングシステムの更新を生成するデバイスであって、
前記オペレーティングシステムに関連付けられた差分更新情報を格納するメモリと、
前記メモリに結合されたプロセッサであって、
前記オペレーティングシステムの現バージョンのバージョン番号を特定し、
前記オペレーティングシステムの前記新バージョンに対して各通常ファイルにわたり反復を実行して、前記新バージョンに関連付けられた全てのデータブロックの前記順序付きリストを取得することを含めて、前記差分更新情報を用いて、前記オペレーティングシステムの前記現バージョンを前記オペレーティングシステムの新バージョンに更新する操作の順序付きリストを作成し、
差分更新ファイルが実際の更新ファイルであることを示すマジックナンバ指示子と、前記オペレーティングシステムの前記新バージョンを特定する新バージョン番号と、前記操作の順序付きリストを含むプロトコルバッファとを含む前記差分更新ファイルを組み立て、
前記差分更新ファイルを前記メモリに格納する、ように構成されるプロセッサと
を備えてなる、コンピュータ可読オペレーティングシステムの更新を生成するデバイス。
【請求項１２】
前記順序付きリスト内の前記各操作は、ファイルオブジェクトに関連付けられ、前記プロセッサは、
前記ファイルオブジェクトごとにグラフ内に頂点を作成し、
前記各ブロックを表すベクトルを作成する、
ように更に構成される、請求項１１に記載のデバイス。
【請求項１３】
前記プロセッサは、
前記各ブロックの前記ベクトルのリーダパラメータ及びライタパラメータを設定し、
異なるリーダ及びライタを有する前記ブロックごとに、該ライタから該リーダへのエッジを前記グラフ内に作成し、ここで、前記エッジは、該エッジに関連付けられたソースファイル操作が開始する前に完了されるファイル操作を指し示す、
ように更に構成される、請求項１２に記載のデバイス。
【請求項１４】
前記グラフがサイクルを含む場合、前記プロセッサは、前記サイクルのそれぞれを切断するように更に動作可能である、請求項１３に記載のデバイス。
【請求項１５】
前記サイクルのうちの所与の１つを切断することは、
前記所与のサイクルに関連付けられた最小重みのエッジを見つけることと、
前記最小重みのエッジをカットすることと
を含むものである、請求項１４に記載のデバイス。
【請求項１６】
前記プロセッサは、
エクステントをスクラッチスペースにコピーする操作を表す新しいノードを作成し、
前記最小重みのエッジのソースノードに前記新しいノードを指し示させる、
ことによって、前記最小重みのエッジをカットするように動作可能である、請求項１５に記載のデバイス。
【請求項１７】
新しいコピー操作が該新しいコピー操作のコンシューマの前に行われることを保証するために、前記最小重みのエッジのデスティネーションノードから新しいエッジが作られる、請求項１６に記載のデバイス。
【請求項１８】
コンピュータプログラムのコンピュータ可読命令が格納される有形のコンピュータ可読ストレージ媒体であって、前記命令は、コンピュータによって実行されると、コンピュータ可読オペレーティングシステムの更新を生成する手順を前記コンピュータに実行させ、前記手順は、
前記オペレーティングシステムの現バージョンのバージョン番号を特定する手順と、
プロセッサを用いて、前記オペレーティングシステムの前記現バージョンを前記オペレーティングシステムの新バージョンに更新する操作の順序付きリストを作成する手順であって、前記プロセッサは、前記オペレーティングシステムの前記新バージョンに対して各通常ファイルにわたり反復を実行して、前記新バージョンに関連付けられた全てのデータブロックの前記順序付きリストを取得する、作成する手順と、
前記プロセッサを用いて、差分更新ファイルが実際の更新ファイルであることを示すマジックナンバ指示子と、前記オペレーティングシステムの前記新バージョンを特定する新バージョン番号と、前記操作の順序付きリストを含むプロトコルバッファとを含む前記差分更新ファイルを組み立てる手順と
を含んでなる、コンピュータプログラムのコンピュータ可読命令が格納される有形のコンピュータ可読ストレージ媒体。
【請求項１９】
前記順序付きリスト内の前記各操作は、ファイルオブジェクトに関連付けられており、
前記ファイルオブジェクトごとにグラフ内に頂点を作成する手順と、
前記各ブロックを表すベクトルを作成する手順と
を更に含む、請求項１８に記載のストレージ媒体。
【請求項２０】
前記各ブロックの前記ベクトルのリーダパラメータ及びライタパラメータを設定する手順と、
異なるリーダ及びライタを有する前記ブロックごとに、該ライタから該リーダへのエッジを前記グラフ内に作成する手順であって、前記エッジは、該エッジに関連付けられたソースファイル操作が開始する前に完了されるファイル操作を指し示す、作成する手順と
を更に含む、請求項１９に記載のストレージ媒体。
【請求項２１】
前記グラフがサイクルを含む場合には、
各所与のサイクルに関連付けられた最小重みのエッジを見つけることと、
前記各サイクルの前記最小重みのエッジをカットすることと
によって前記サイクルのそれぞれを切断する手順を更に含む、請求項２０に記載のストレージ媒体。
【請求項２２】
前記最小重みのエッジをカットすることは、
エクステントをスクラッチスペースにコピーする操作を表す新しいノードを作成することと、
前記最小重みのエッジのソースノードに前記新しいノードを指し示させることと
を含むものである、請求項２１に記載のストレージ媒体。
【請求項２３】
新しいコピー操作が該新しいコピー操作のコンシューマの前に行われることを保証するために、前記最小重みのエッジのデスティネーションノードから新しいエッジが作られる、請求項２２に記載のストレージ媒体。
【請求項２４】
オペレーティングシステムの現バージョンを格納するメモリと、
前記メモリに結合されたプロセッサと
を備えてなる、クライアントデバイスであって、
前記プロセッサは、
前記オペレーティングシステムの前記現バージョンの更新に関して遠隔デバイスに要求を送信し、ここで、該要求は、前記オペレーティングシステムの前記現バージョンを特定するバージョン番号を含み、
前記遠隔デバイスから差分更新ファイルを受信し、ここで、該差分更新ファイルは、該差分更新ファイルが実際の更新ファイルであることを示すマジックナンバ指示子と、前記オペレーティングシステムの前記新バージョンを特定する新バージョン番号と、操作の順序付きリストを含むプロトコルバッファとを含み、
前記マジックナンバを検証し、
前記プロトコルバッファから前記操作の順序付きリストを抽出し、
前記オペレーティングシステムの前記現バージョンを前記オペレーティングシステムの前記新バージョンに更新するために、前記操作の順序付きリストを実行することによって差分更新を実行する、
ように構成されている、クライアントデバイス。
【請求項２５】
前記プロセッサは、前記差分更新ファイルが前記クライアントデバイスにストリーミングされている間に、前記メモリに前記差分更新ファイルを保存することなく、前記オペレーティングシステムの前記新バージョンへの前記オペレーティングシステムの前記差分更新を実行するように動作可能である、請求項２４に記載のクライアントデバイス。
【図１】
【図４Ｂ】
【図２】
【図３】
【図４Ａ】
【図４Ｂ】
【図２】
【図３】
【図４Ａ】
【公表番号】特表２０１３−５１７５６５（Ｐ２０１３−５１７５６５Ａ）
【公表日】平成２５年５月１６日（２０１３．５．１６）
【国際特許分類】
【出願番号】特願２０１２−５４８９９８（Ｐ２０１２−５４８９９８）
【出願日】平成２３年１月１１日（２０１１．１．１１）
【国際出願番号】ＰＣＴ／ＵＳ２０１１／０２０７９０
【国際公開番号】ＷＯ２０１１／０８８０２２
【国際公開日】平成２３年７月２１日（２０１１．７．２１）
【出願人】（５０２２０８３９７）グーグル インコーポレイテッド (161)
【Ｆターム（参考）】
【公表日】平成２５年５月１６日（２０１３．５．１６）
【国際特許分類】
【出願日】平成２３年１月１１日（２０１１．１．１１）
【国際出願番号】ＰＣＴ／ＵＳ２０１１／０２０７９０
【国際公開番号】ＷＯ２０１１／０８８０２２
【国際公開日】平成２３年７月２１日（２０１１．７．２１）
【出願人】（５０２２０８３９７）グーグル インコーポレイテッド (161)
【Ｆターム（参考）】
[ Back to top ]