【手続補正書】
【提出日】平成17年6月17日(2005.6.17)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
プロセッサとメモリとを備えたコンピュータシステムで実行される方法であって、スレッド優先度に基づいて相互に関連して格納された複数の第１のスレッドを備えた実行キューを管理する方法において、
単一のスレッドを前記実行キューに挿入する時間に等しい決定性の時間内で、実行キューの優先度に基づくスケジューリングセマンティックを維持する方法により、優先度でソートされた複数の第２のスレッドを実行キューに関連付けること
を備えたことを特徴とする方法。
【請求項２】
前記複数の第２のスレッドは、ルートスレッドを備え、前記複数の第２のスレッドを実行キューに関連付けることは、
前記実行キューに前記ルートスレッドのみを挿入すること
をさらに備えたことを特徴とする請求項１に記載の方法。
【請求項３】
前記複数の第２のスレッドを実行キューに関連付けることは、
いかなる付加的な他のキューアクセスとは無関係に、前記実行キューに前記複数の第２のスレッド内の各スレッドを挿入すること
をさらに備えたことを特徴とする請求項１に記載の方法。
【請求項４】
前記複数の第２のスレッドを実行キューに関連付けることは、
前記実行キューに前記複数の第２のスレッドのルートスレッドのみを挿入すること
をさらに備えたことを特徴とする請求項１に記載の方法。
【請求項５】
前記複数の第２のスレッドを実行キューに関連付けることは、
前記実行キューに前記複数の第２のスレッドのルートスレッドのみを挿入し、
前記ルートスレッドを前記実行キューから削除することと、
前記ルートスレッドを削除することに応じて、前記実行キューに前記複数の第２のスレッドの次のスレッドを挿入して、実行キューの優先度に基づくスケジューリングセマンティックが保たれることと
をさらに備えたことを特徴とする請求項１に記載の方法。
【請求項６】
前記実行キューに前記複数の第２のスレッドのルートスレッドを挿入することと、
実行のために前記ルートスレッドを前記実行キューから削除することと、
前記ルートスレッドを削除することに応じて、およびいかなる付加的な他のキューアクセスとは無関係に、前記実行キューに前記複数の第２のスレッドの次のスレッドを挿入することと
をさらに備えたことを特徴とする請求項１に記載の方法。
【請求項７】
実行キューを管理するシステムであって、前記実行キューは、複数の第１のスレッドを備え、前記複数の第１のスレッドの各々は、各々優先度を有し、前記複数の第１のスレッドが格納されて、低い優先度を有するスレッドより前に高い優先度を有するスレッドが前記実行キューから削除されるように構成されたシステムにおいて、
前記実行キューおよびコンピュータ実行可能命令を格納するメモリと、
メモリに作用するように接続され、前記コンピュータ実行可能命令を実行するように構成されたプロセッサと、
単一のスレッドを前記実行キューに挿入する時間に等しい時間内で、実行キューの優先度に基づくスケジューリングセマンティックを維持して、優先度でソートされた複数の第２のスレッドを実行キューに関連付けることと
を備えたことを特徴とするシステム。
【請求項８】
前記実行キューに前記複数の第２のスレッドを関連付けることは、単一の他のキューアクセスとは無関係に実行されることを特徴とする請求項７に記載のシステム。
【請求項９】
前記複数の第２のスレッドは、前記複数の第２のスレッドのうち１または複数の他のスレッドに作用するように接続されたルートスレッドを備え、前記１または複数の他のスレッドは、ルートノードの優先度と比較して低い優先度または等しい優先度である優先度を各々有することを特徴とする請求項７に記載のシステム。
【請求項１０】
前記実行キューに前記複数の第２のスレッドを関連付けることは、
前記実行キューに前記複数の第２のスレッドのルートスレッドのみを挿入すること
をさらに備えたことを特徴とする請求項７に記載のシステム。
【請求項１１】
前記実行キューに前記複数の第２のスレッドを関連付けることは、
前記実行キューに前記複数の第２のスレッドのルートスレッドのみを挿入すること
をさらに備えたことを特徴とする請求項７に記載のシステム。
【請求項１２】
前記複数の第１のスレッドは、第１のリンクドリストデータ構造であり、
前記複数の第２のスレッドは、前記複数の第２のスレッドのうち１または複数の他のスレッドに作用するように接続されたルートスレッドを備えた第２のリンクドリストデータ構造であり、
単一の挿入操作は、前記第１のリンクドリストデータ構造に前記ルートノードを挿入することを備えた操作である
ことを特徴とする請求項７に記載のシステム。
【請求項１３】
前記実行キューに前記複数の第２のスレッドを関連付けることは、
前記実行キューに前記複数の第２のスレッドのルートスレッドのみを挿入し、
前記ルートスレッドを前記実行キューから削除することと、
前記ルートスレッドを削除することに応じて、前記実行キューに前記複数の第２のスレッドの次のスレッドを挿入して、実行キューの優先度に基づくスケジューリングセマンティックが保たれることと
をさらに備えたことを特徴とする請求項７に記載のシステム。
【請求項１４】
前記プロセッサは、
前記実行キューに前記複数の第２のスレッドのルートスレッドを挿入し、
実行のために前記ルートスレッドを前記実行キューから削除し、
前記ルートスレッドを削除することに応じて、およびいかなる付加的な他のキューアクセスとは無関係に、前記実行キューに前記複数の第２のスレッドの次のスレッドを挿入するためのコンピュータプログラム命令を実行するように構成されていることを特徴とする請求項７に記載のシステム。
【請求項１５】
スレッド優先度に基づいて相互に関連して格納された実行キューを管理するコンピュータ実行可能命令を備えたコンピュータ読み取り可能な媒体であって、
優先度でソートされた複数の第２のスレッドにおいて、単一のスレッドを前記実行キューに挿入する時間に等しく、スレッドの数とは無関係な決定性の時間内で、前記実行キューの優先度に基づくスケジューリングセマンティックを維持する方法により、前記複数の第２のスレッドを前記実行キューに関連付ける命令を備えたことを特徴とするコンピュータ読み取り可能な媒体。
【請求項１６】
前記複数の第２のスレッドは、前記複数の第２のスレッドのうち１または複数の他のスレッドに作用するように接続されたルートスレッドを備え、前記関連付ける命令は、
前記複数の第１のスレッドに前記ルートスレッドのみを挿入し、前記複数の第２のスレッドを表すこと
をさらに備えたことを特徴とする請求項１５に記載のコンピュータ読み取り可能な媒体。
【請求項１７】
前記複数の第１のスレッドは、第１のリンクドリストデータ構造であり、
前記複数の第２のスレッドは、前記複数の第２のスレッドのうち１または複数の他のスレッドに作用するように接続されたルートスレッドを備えた第２のリンクドリストデータ構造であり、
前記決定性の時間は、前記第１のリンクドリストデータ構造に前記ルートノードを挿入する単一の挿入操作の結果であることを特徴とする請求項１５に記載のコンピュータ読み取り可能な媒体。
【請求項１８】
前記関連付ける命令は、
前記複数の第１のスレッドに前記複数の第２のスレッドのルートスレッドのみを挿入することをさらに備え、
前記コンピュータ実行可能命令は、
前記ルートスレッドを前記実行キューから削除することと、
前記ルートスレッドを削除することに応じて、前記実行キューの優先度に基づくスケジューリングセマンティックを維持する方法により、前記複数の第１のスレッドに前記複数の第２のスレッドの次のスレッドを挿入することと
をさらに備えたことを特徴とする請求項１５に記載のコンピュータ読み取り可能な媒体。
【請求項１９】
前記次のスレッドを挿入する命令は、他のキューとは無関係に実行されることを特徴とする請求項１８に記載のコンピュータ読み取り可能な媒体。
【請求項２０】
前記関連付ける命令は、
前記複数の第１のスレッドに前記複数の第２のスレッドのルートスレッドを挿入することと、
実行のために前記ルートスレッドを前記複数の第１のスレッドから削除することと、
前記ルートスレッドを削除することに応じて、他の異なるキューへの付加的なアクセスとは無関係に、前記複数の第１のスレッドに前記複数の第２のスレッドの次のスレッドを挿入することと
をさらに備えたことを特徴とする請求項１５に記載のコンピュータ読み取り可能な媒体。
【請求項２１】
実行キューデータ構造を備えたコンピュータ読み取り可能な媒体であって、前記実行キューデータ構造は、
スレッド優先度に関連して格納された複数の第１のスレッドを備えた第１の次元データフィールドと、
スレッド優先度に基づいて格納された複数の第２のスレッドを備えた第２の次元データフィールドであって、前記複数の第２のスレッドは、ルートスレッドおよび１または複数の他のスレッドを備えた第２の次元データフィールドと
を備えたことを特徴とするコンピュータ読み取り可能な媒体。