JPH1091466A - タスクスケジューリング方法及び装置 - Google Patents

タスクスケジューリング方法及び装置

Info

Publication number
JPH1091466A
JPH1091466A JP9075054A JP7505497A JPH1091466A JP H1091466 A JPH1091466 A JP H1091466A JP 9075054 A JP9075054 A JP 9075054A JP 7505497 A JP7505497 A JP 7505497A JP H1091466 A JPH1091466 A JP H1091466A
Authority
JP
Japan
Prior art keywords
task
tasks
video
procedure
class
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
JP9075054A
Other languages
English (en)
Inventor
Banu Ozden
オズデン バヌ
Rajeev Rastogi
ラストギー ラジーフ
Abraham Silberschatz
シルバースチャッツ アブラハム
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Nokia of America Corp
Original Assignee
Lucent Technologies Inc
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Lucent Technologies Inc filed Critical Lucent Technologies Inc
Publication of JPH1091466A publication Critical patent/JPH1091466A/ja
Pending legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N7/00—Television systems
    • H04N7/16—Analogue secrecy systems; Analogue subscription systems
    • H04N7/173—Analogue secrecy systems; Analogue subscription systems with two-way working, e.g. subscriber sending a programme selection signal
    • H04N7/17309—Transmission or handling of upstream communications
    • H04N7/17336—Handling of requests in head-ends

Landscapes

  • Engineering & Computer Science (AREA)
  • Multimedia (AREA)
  • Signal Processing (AREA)
  • Television Signal Processing For Recording (AREA)
  • Two-Way Televisions, Distribution Of Moving Picture Or The Like (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Multi Processors (AREA)

Abstract

(57)【要約】 【課題】 ビデオスケジューリングの容易なストライピ
ング方式の提供。 【解決手段】 予め定められた個数のプロセッサ１１を
有するビデオ・サーバ１０においてビデオに対応するノ
ン・プリエンプティブなタスクグループの周期的スケジ
ューリングにおいて、各タスクは予め定められた周期で
始まり、且つ時間間隔によって隔てられたサブタスクの
セットを有する。このタスクグループをスケジューリン
グするために、単一のプロセッサ上でスケジューリング
可能なタスク・グループについては、これを１個以上の
互いに素のタスクセットに分割し、タスクの周期の最大
公約数を用いてこのグループのタスクのスケジューリン
グの可能性を点検する。互いに素のタスクに属する２個
以上のサブタスクが同じタイムスロットに割り当てられ
なければ、このグループのタスクはスケジューリング可
能である。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、一般的にはビデオ
・オン・デマンド・サービスに関し、詳しくはディスク
・ストライピング手法を用いたビデオ・サーバに関す
る。 （関連出願）本出願は米国特許出願第０８/６２４,０１
３号（Ozden 8-8-13）（名称：Method and Apparatus f
or Providing Enhanced Pay Per View in a Video Serv
er） （本出願と同時に出願）及び米国特許出願第０８/４９
２,３１５号（名称：Coarse-Grained Disk Striping Me
thod for Use in Video Server Environments）（上記
出願は各々少なくとも１名の発明者を共有し、又出願人
が同一である）に関連する。ここに上記各米国出願を本
出願の参考文献とする。
【０００２】
【従来の技術】近年、ネットワーク関連技術並びにビデ
オ（映像、又は映像プログラム）のディジタル化及び圧
縮に関連する技術の両方に重要な進歩が生じている。例
えば、毎秒当たり数ギガビットのデータを光ファイバ・
ネットワーク上で、ＭＰＥＧ−１のような圧縮規格を用
いて伝送することが今や可能であり、伝送に要する帯域
幅も比較的狭い。このような進歩の結果として、ビデオ
・オン・デマンド、オンライン個人指導（チュートリア
ル）、対話型テレビ等、ビデオ・データの通信ネットワ
ーク上での伝送に関わる適用事例としてのサービスが多
数出現している。
【０００３】ビデオ・サーバは、上記サービスの供与に
必要な重要構成要素の１つである。サービスによって
は、ビデオ・サーバは、幾百ものビデオ・プログラムを
格納（記憶）することと、顧客に数百から数千のビデオ
についてのデータを同時に伝送することとが要求され
る。すぐ判るように、伝送レート（速度）は一般に、ビ
デオ・サーバが用いる圧縮手法によって決まる固定レー
トを取る。例えば、ＭＰＥＧ−１についての伝送速度は
約１．５Ｍｂｐｓである。
【０００４】映像、例えば映画及びその他のオン・デマ
ンドのプログラム、はビデオ・サーバのランダム・アク
セス・メモリ（ＲＡＭ）から顧客に伝送される。しか
し、ビデオ・データはその量が膨大である（例えば、１
００分の長さのＭＰＥＧ−１ビデオは約１．１２５ＧＢ
の格納容積（記憶容量）を要するという性質と、ＲＡＭ
が比較的高いコストがかかることとから、ＲＡＭへのビ
デオ・データの格納は実行不可能な程度に高価なものに
なる。
【０００５】ビデオ・データのビデオ・サーバへの格納
をよい費用効果で行う別案としては、ＲＡＭの代わりに
磁気又は光ディスクを用いる手法がある。しかし、ディ
スクに格納されたビデオ・データを顧客に伝送するに
は、その前にビデオ・データをＲＡＭに取り出す必要が
ある。又、現在の磁気又は光ディスクは、記憶容量に限
度があり（例えば１ＧＢ〜９ＧＢ）、磁気又は光ディス
クからＲＡＭへデータを取り出す際の転送速度も比較的
低い（例えば３０Ｍｂｐｓ〜６０Ｍｂｐｓ）。
【０００６】この記憶容量の限度は、ビデオ・サーバ上
で格納できるビデオの個数に影響し、更に転送速度の低
さと相まって、同時に取り出せるビデオの個数に影響を
与える。
【０００７】任意に選択された１個のディスク上にビデ
オ・データ全体を格納する単純な格納方式を用いた場
合、人気の高いビデオ・プログラムを格納するディスク
が、サポート能力を超えたリクエスト（要求）で過負荷
になる一方、人気の低いプログラムを格納するディスク
は遊び（アイドル）状態にある、というような結果にな
る可能性が高い。このような方式においては、ディスク
帯域幅が有効に利用されないことになる。すぐ判るよう
に、ディスク帯域幅とは、或る時間長さの間に１個のデ
ィスクから取り出すことのできるデータの量を意味す
る。
【０００８】ディスクがアイドル状態であったり、ディ
スクヘッドが位置決め中であったりして、ディスクから
データが取り出されないときには、ディスク帯域幅は利
用されておらず、したがって無駄にされていると考えら
れる。ディスク帯域幅が有効に利用されないと、ビデオ
・サーバがサポートすることができるビデオ・データ同
時進行ストリームの個数に悪影響を与える。
【０００９】ディスク帯域幅をより有効に利用するため
に、負荷を多数のディスクにわたって均一に配分する、
すなわちビデオ・データを複数のディスク上に配置する
種々の方式が考え出された。複数のディスクにわたって
ビデオ・データを格納する方式で人気のあるものの１つ
は、周知のディスク・ストライピング手法である。
【００１０】この手法は、互いに連続する論理データユ
ニット（ストライプ・ユニットと称する）を複数の個別
にアクセス可能なディスクに、順次に配分するものであ
る。ディスク・ストライピング手法においては又、複数
のディスクにわたって負荷を均一に配分できるほかに、
１個のビデオについての多数の同時進行ストリームを、
ビデオの複製を必要とせずにサポートすることが可能で
ある。
【００１１】未処理すなわち処理待ちのビデオ要求は概
して、それらの要求が受領された順に、すなわち先入れ
先出し（ＦＩＦＯ）方式でビデオ・サーバによって処理
される。同時要求の個数が、そのビデオ・サーバによる
サポートの可能な同時進行ストリームの個数より少ない
か又は遥かに多くはない場合には、全ての処理待ち要求
に対して良好な全体応答時間を得ることが可能である。
【００１２】しかし、同時要求の個数がビデオ・サーバ
によるサポートの可能な同時進行ストリームの個数を遥
かに超えることが一般的なビデオ・オン・デマンド（Ｖ
ＯＤ）環境においては、先入れ先出し方式を用いて全て
の処理待ち要求に対して良好な全体応答時間を得ること
は不可能である。
【００１３】より良好な全体応答時間を得るために、強
化ペイ・パー・ビュー（ＥＰＰＶ）方式として知られる
手法が、ケーブル放送会社のようなビデオ・オン・デマ
ンド環境によって採用された。この強化ペイ・パー・ビ
ュー方式を利用して、ビデオ・サーバは、固定時間間隔
又は周期でビデオ・ストリームを取り出し、顧客に伝送
する。この方式の下では、１個の要求に対する平均応答
時間は、固定時間間隔の半分で、最も遅い応答時間は、
固定時間間隔と同じになる。
【００１４】更に、人気の高いビデオを高い頻度で取り
出し、人気の低いビデオを低い頻度で取り出すことによ
り、より良好な全体平均応答時間が達成できる。究極的
には、ビデオが取り出される周期と正確な時間を顧客に
知らせることによって、応答時間をゼロにまですること
が可能である。
【００１５】
【発明が解決しようとする課題】強化ペイ・パー・ビュ
ー方式を用いているビデオ・サーバ上でビデオの組み合
わせ（ビデオ・セット）をスケジューリングすることが
可能であっても、新たなビデオ・ストリームを開始させ
る正確なスケジュールを定めるのは困難がある。このこ
とは、特に、周期及び計算時間すなわちビデオ又はその
セグメントを伝送するのに要する時間が任意の場合にそ
うである。
【００１６】目標は、同時に伝送されるようにスケジュ
ーリングされたビデオ・ストリームの個数がそのビデオ
・サーバによってサポートが可能な同時伝送ビデオ・ス
トリームの最大数を超えないように、そのビデオ・セッ
トをスケジューリングすることである。
【００１７】強化ペイ・パー・ビュー方式においてビデ
オをスケジューリングすることには、「多項式アルゴリ
ズムが与えられていないために解が困難(NP-hard)」 の
ような、解を得るための複雑さがある。すなわち、スケ
ジューリングされるビデオの個数と、ビデオの伝送に用
いられるプロセッサの個数とが増加するにつれて、ビデ
オを周期的にスケジューリングする際の複雑さが増大す
る。
【００１８】したがって、強化ペイ・パー・ビュー方式
を用いているビデオ・サーバ上でのビデオのスケジュー
リングを有効に行うことが可能な方法及び装置が必要と
されている。
【００１９】
【課題を解決するための手段】本発明は、ビデオ・サー
バにおいて強化ペイ・パー・ビュー方式を可能にする方
法を提供するものである。具体的には、本発明の方法
は、ｐ個のプロセッサを有するビデオ・サーバにおいて
ビデオに対応するノン・プリエンプティブなタスクＴ
（Ｔｉで表す）からなるタスクグループＧを周期的にス
ケジューリングする。これらのタスクＴi は各々、予め
定められた周期Ｐi（ｉ番目のＰ）で始まり、且つ時間
間隔Ｆによって隔てられたｗi 個のサブタスクを有す
る。
【００２０】このタスクグループＧ内のタスクＴi をス
ケジューリングするのに、本発明は４種類の手順を利用
する。第１の手順においては、１つのサーバに含まれる
タスクグループＧのタスクが、単一のプロセッサ上でス
ケジューリングすることが可能でないタスクからなるタ
スク・サブグループＧ１と可能なタスクからなるタスク
・サブグループＧ２との２個のタスクサブグループ（又
は簡単に、サブグループ）に分割される。この第１の手
順は次に、サブグループＧ１及びＧ２の両方を別個にス
ケジューリングすることを試みる。
【００２１】単一のプロセッサ上でスケジューリングす
ることが可能でないサブグループ、すなわちサブグルー
プＧ１については、第１の手順が、ｐ’個のプロセッサ
上でタスクをスケジューリングする。単一のプロセッサ
上でスケジューリングすることが可能なサブグループ、
すなわちサブグループＧ２については、第１の手順は、
第２の手順を呼び出し、残りのＰ”個のプロセッサの各
々について１個のサブセットＧ２−ｙが存在するように
サブグループＧ２をサブセットＧ２−ｙに分割させる。
【００２２】各サブセットＧ２−ｙについて、第１の手
順は、第３の手順を呼び出し、そのサブセットＧ２−ｙ
がスケジューリング可能であるかどうかを判断させる。
第３の手順は、第４の手順を用いて、第３の手順による
サブセットＧ２−ｙのスケジューリング可能性の判断を
援助させる。
【００２３】もし第４の手順が、サブセットＧ２−ｙが
スケジューリング可能でないと判断し、第３の手順が、
その同じサブセットＧ２−ｙが更に分割可能であると判
断した場合、第３の手順は第２の手順を呼び出し、その
サブセットＧ２−ｙを更にサブ・サブセットＳv に分割
させる。
【００２４】サブセットＧ２−ｙが分割された後、第３
の手順が自分自身を呼びだし、スケジューリング可能性
の再判断を行う。本発明は、第２のスケジューリング手
法によってタスクのサブグループ、サブセット等がスケ
ジューリング可能か又はもはや分割可能でないと判断さ
れるまで、タスクのサブグループ、サブセット等を反復
して分割する。
【発明の実施の形態】
【００２５】図１１に、本発明に基づく、ビデオ・オン
・デマンド（ＶＯＤ）サービスを提供するためのビデオ
・サーバ１０を示す。ビデオ・サーバ１０は、プロセッ
サ１１−１〜１１−ｐとサイズＤのＲＡＭバッファメモ
リ１２とデータ格納ユニット１３とからなるコンピュー
タシステムである。
【００２６】データ格納ユニット１３は、複数のビデオ
（ビデオ・プログラム）Ｖi （i ＝１，．．．，Ｎにお
いてそれぞれ個々のビデオを示す）、又は互いに連鎖状
に連続する複数のビデオＶi （以下、スーパ・ビデオ＾
Ｖh と称する）（h ＝１，．．．，Ｐにおいてそれぞれ
個々のスーパ・ビデオを示す）、からなるスーパ・ビデ
オ・グループを、望ましくは圧縮された形で格納するた
めの複数のディスク１３−１〜１３−ｍからなる。
【００２７】尚、＾Ｖh は、本来Ｖh の直上に＾を配置
する表記を用いるところを、便宜上これに代わる簡易表
記として用いる（以下同様）。
【００２８】データ格納ユニット１３は更に、ビデオＶ
i をディスク１３−１〜１３−ｍからＲＡＭバッファメ
モリ１２へ取り出すためのディスク・ヘッド（図示しな
い）からなる。尚、プロセッサの個数を示すｐの値は、
ＲＡＭバッファメモリのサイズＤ、ディスクの個数ｍ、
及び取り出されるデータの量に依る。ｐの値の定め方に
ついては下に述べる。
【００２９】プロセッサ１１−１〜１１−ｐは、１箇所
以上の受信者（顧客）１５に予め定められた速度（ｒ
disp）で高速のネットワーク１４を介して伝送するよう
に作動する。しかし、ビデオＶi が伝送可能になる前
に、ビデオＶi をまずディスク１３−１〜１３−ｍから
ＲＡＭバッファメモリ１２（ビデオＶi は最終的にはこ
こから伝送される）へ取り出す必要がある。
【００３０】ディスク１３−１〜１３−ｍからＲＡＭバ
ッファメモリ１２へ（又はＲＡＭバッファメモリ１２か
ら顧客へ）のビデオＶi の連続転送状態の流れを本明細
書では「ストリーム」と称する。ディスク１３−１〜１
３−ｍから同時に（並行して）取り出すことのできるビ
デオＶi すなわち同時ストリーム、の個数は、ＲＡＭバ
ッファメモリ１２のサイズＤによって制約される。すな
わち、ＲＡＭバッファメモリのサイズが、取り出し可能
な同時ストリームの個数に直接比例する。
【００３１】多数の同時ストリームを取り出すように、
すなわちサポートするように作動するビデオ・サーバで
は、顧客によるビデオ要求に対して、より良好な全体応
答時間が得られる。理想的なのは、ビデオ・サーバが、
顧客からの同時要求の全てに対して要求受領時に即時に
サポートを行うのに十分なサイズＤのＲＡＭバッファメ
モリを備えることである。このような理想的な状態にお
いては、ビデオ・サーバは、顧客要求に対してその応答
時間がゼロである（ゼロ応答時間を有する）と表現され
る。
【００３２】しかし、ビデオ・サーバ当たりの同時要求
の個数が大きいビデオ・オン・デマンド環境において
は、要求に即時にサービスを行うのに必要なＲＡＭバッ
ファメモリのサイズを備えるには、実現不可能なほどの
高いコストがビデオ・サーバにかかることとなる。この
ような環境においては、要求の個数が、ビデオ・サーバ
の同時ストリーム伝送能力を遥かに超過するため、全体
応答時間に悪影響を及ぼすこととなる。
【００３３】より良好な全体応答時間を得るために、ケ
ーブル放送会社のようなビデオ・オン・デマンド環境に
おいては、周期的にビデオＶi を取り出して顧客に伝送
するための、強化ペイ・パー・ビュー（ＥＰＰＶ）方式
として知られる非常に有効な手法が採用された。
【００３４】［強化ペイ・パー・ビュー（ＥＰＰＶ）方
式］強化ペイ・パー・ビュー方式は、ラウンドと称する
時間長さによって表される周期Ｐi で新たなストリーム
を取り出して顧客に伝送する手法に関わる。例えば、或
る（ｉ番目の）ラウンド（ｒi で表す）から始めて、新
たなビデオＶi のストリームについてのデータ取り出し
は、ｒi 、ｒi ＋Ｐi 、ｒi ＋２Ｐi 、等のラウンドの
間に開始される。
【００３５】しかし、周期Ｐi 及び利用可能なＲＡＭバ
ッファメモリのサイズに依っては、周期Ｐi でビデオＶ
i についてのデータ取り出しをおこなうことは必ずしも
可能ではない。ビデオ・サーバによって周期的にビデオ
を取り出すことが可能かどうかを判断するすなわち定め
る問題は、或る１個のマルチプロセッサ上で周期的なタ
スク（Ｔi と称する）をスケジューリングする問題と同
じである。
【００３６】文献（J.A.Stankovic and K.Ramamritham,
"Hard Real-time Systems" published in IEEE Comput
er Society Press, Los Alamitos, California, 1988）
を参照されたい。
【００３７】本出願の目的上、タスクＴi （又はタスク
＾Ｔh ）は、単一ディスク上でビデオＶi （又はスーパ
・ビデオ＾Ｖh ）の１個のストリームに属する全てのデ
ータを取り出すジョブに対応する。
【００３８】尚、強化ペイ・パー・ビュー方式は、同時
要求の個数が、ビデオ・サーバによってサポートされる
同時ストリームの個数よりも遥かに多くはない環境や、
ビデオ要求が無作為であるために種々のビデオについて
の周期を定めることが困難な環境には不適切である。
【００３９】［ディスク・ストライピング］本発明によ
れば、ディスク・ストライピング手法を用いるビデオ・
サーバにおいて強化ペイ・パー・ビュー方式を供与する
新しい方法及び装置が提供される。ディスク・ストライ
ピング手法は、ディスク帯域幅がより有効に利用される
ようにビデオを多数のディスクにわたって分散させる手
法に関わる。
【００４０】具体的には、ディスク・ストライピング手
法は、互いに連続する論理データユニット（ストライプ
・ユニットと称する）を複数の個別にアクセス可能なデ
ィスクに、連鎖状に配分するものである。
【００４１】図２にディスク・ストライピング手法の例
示説明図を示す。図２に示すように、ビデオ２０がサイ
ズｓｕを有するｚ個のストライプ・ユニット２２−１〜
２２−ｚに分割される。各ストライプ・ユニットを、Ｖ
i,j（Ｖiのj番目のストライプ・ユニット） で表す。こ
こにｊ＝１，．．．，ｚの場合のＶi,j は、ビデオＶi
の特定のストライプ・ユニットを意味する。
【００４２】説明の便宜上、本発明を、関連する米国特
許出願第０８/４９２,３１５号（名称：Coarse-Grained
Disk Striping Method For Use In Video server Envi
ronments）に開示されている特定の、すなわち、きめを
細かくしたディスク・ストライピング手法及びきめを粗
くしたディスク・ストライピング手法に関連して述べる
が、このことが、本発明をこれら特定のディスク・スト
ライピング手法に限定するものと解釈してはならない。
【００４３】（「きめを細かくした」ディスク・ストラ
イピング手法）図３に、ビデオＶi を格納し、取り出す
ための「きめを細かくした（Fine-Grained）」ディスク
・ストライピング手法（以下、FＧストライピング手法
とも表記）を例示する。図３に示すようなこのＦＧスト
ライピング手法において、１個以上のビデオＶi に属す
るストライプ・ユニットＶi,j （３２−１〜３２−ｍ）
が、順次にディスク３０−１〜３０−ｍ上に隣接して格
納される。すなわち、ストライプ・ユニットＶi,1（３
２ー１）〜Ｖi,m（３２ーｍ）がディスク３０−１〜３
０−ｍにそれぞれ格納され、ストライプ・ユニットＶi,
1+m（３２−（１＋ｍ））〜Ｖi,2・m（３２−２・ｍ）
がディスク３０−１〜３０−ｍにそれぞれ格納され、以
下順次同様に格納される。
【００４４】そして、互いに連続するｍ個のストライプ
・ユニットからなる各グループが、それぞれのディスク
の同じ相対位置に格納される。例えば、ストライプ・ユ
ニットＶi,1〜Ｖi,mがディスク３０−１〜３０−ｍの第
１トラックにそれぞれ格納され、ストライプ・ユニット
Ｖi,1+m〜Ｖi,2・mがディスク３０−１〜３０−ｍの第２
トラックにそれぞれ格納され、以下同様に格納される。
【００４５】各ビデオＶi は望ましくは、各ディスク３
０−１〜３０−ｍについて、同じビデオＶi に属するス
トライプ・ユニットの個数（ｗi で表す）がどのディス
クでも同じになるような、ｍの倍数である長さｌi(エルア
イ) を有するようにする。これは、末尾に広告又は埋草
ビデオを付加することによって実現できる。
【００４６】同じビデオに属する、１つのディスク上の
ストライプ・ユニットのグループを本説明では、ブロッ
クと称する。したがって、各ブロックは、その同じビデ
オＶi に属するｗi 個のストライプ・ユニットを有す
る。
【００４７】本ＦＧストライピング手法においては、ビ
デオＶi の各ストリームについてのデータが、同時に全
てのディスク・ヘッドを用いてディスク１３−１〜１３
−ｍから取り出される。具体的には、各ディスク・ヘッ
ドが、一連のラウンドｒi の間に、各ストリームについ
てそれぞれのディスク上の同じ相対位置からサイズｓｕ
のストライプ・ユニットを取り出す。
【００４８】すなわち、各ストリームについて１個のラ
ウンドｒi の間に取り出されるデータの量が、そのビデ
オＶi に属し互いに連続するｍ個のストライプ・ユニッ
トからなるグループを形成する。ｍ個のストライプ・ユ
ニットからなるグループは各々、ビデオＶi の、サイズ
ｄを有する部分（又は、サイズｄ部分）を形成する。言
い換えれば、ｍ・ｓｕ＝ｄである。
【００４９】尚、ビデオＶi の１個のストリームについ
てのデータが取り出される間のラウンドの個数は、次式
［数１］で表され、ここに、ｌi(エルアイ) はビデオＶi の
長さに対応する。したがって、ビデオＶi の各ストリー
ムは、［数１］で表される個数のサイズｄ部分からなる
と見ることができる。
【数１】
【００５０】ビデオＶi の新たなストリームが開始され
るときには、サイズ２・ｄのバッファメモリが割り付け
られる。このことよって、新たなストリームの各々につ
いてのサイズｄ部分の同時取り出し及び伝送が可能とな
る。しかし、新たなストリームのデータ伝送は、割り付
けられたバッファメモリにビデオＶi の第１のサイズｄ
部分の全部が取り出されるまでは開始されないことに留
意を要する。
【００５１】例えば、もしラウンドｌi(エルアイ) を、割り
付けられたバッファメモリにビデオＶi の第１のサイズ
ｄ部分が取り出される時間長さとした場合、顧客への第
１のサイズｄ部分の速度ｒdispでの伝送は、ラウンド２
i までは開始されない。第１のサイズｄ部分のデータの
伝送に要する時間は、ラウンドｒi の時間長さに対応す
る。言い換えれば、ラウンドｒi の時間長さはｄ／ｒ
dispである。
【００５２】更に、ビデオＶi の第１のサイズｄ部分が
伝送されるラウンド２i の間に、ビデオＶi の第２のサ
イズｄ部分が、割り付けられたバッファメモリに取り出
される。
【００５３】一般的には、各ラウンドｒi についてビデ
オＶi の次のサイズｄ部分が、割り付けられたバッファ
メモリに取り出される。そして、割り付けられたバッフ
ァメモリに現に在駐している同じビデオＶi の前のサイ
ズｄ部分が、その割り付けられたバッファメモリから伝
送される。このサイズｄ部分の取り出し及び伝送を同時
に行う動作は、ビデオＶi 全体が取り出され伝送される
まで継続される。
【００５４】尚、ビデオＶi の次のサイズｄ部分の取り
出しは、ビデオＶi の前のサイズｄ部分の伝送の完了時
と同時に又は完了時より前に完了する必要がある。すな
わち、サイズｄ部分１個の取り出し時間は、サイズｄ部
分の伝送時間に等しいか又はそれよりも短くなければな
らない。言い換えれば、データ取り出しは、ラウンドｒ
i の時間で完了する必要がある。
【００５５】このことが要求される理由は、全てのビデ
オについてのデータが速度ｒdispの連続ストリームとし
て顧客に伝送されることを確実にする必要があるからで
ある。各ラウンドｒi 内にデータ取り出しが完了しない
場合には、ビデオストリームが中断する結果となる。
【００５６】ビデオＶi の各ストリームについてデータ
が取り出されるサイズ増分（データ取り出し量）は、均
一、すなわち値ｄで、この値は望ましくは、ＲＡＭバッ
ファメモリのサイズＤとビデオＶi がストライピングさ
れるディスクの個数ｍとに基づいて、ビデオ・サーバに
よってサポートすることのできる同時ストリームの個数
が最大になるように計算される。本ＦＧストライピング
手法については、値ｄは次の数式［数２］で与えられ
る。
【００５７】
【数２】
【００５８】１個のビデオ・サーバによってサポートす
ることのできる同時ストリームの個数を最大にするには
又、ビデオ・サーバ内のプロセッサの個数も関連する。
前に述べたように、各プロセッサ１１−１〜１１−ｐは
速度ｒdispでデータを伝送するように作動する。ラウン
ドｒi の時間長さがｄ／ｒdispであるので、各プロセッ
サ１１−１〜１１−ｐはラウンドｒi 当たり１個のサイ
ズｄ部分しか伝送できない。
【００５９】したがって、１個のビデオ・サーバによっ
てサポートすることのできる同時ストリームの最大個数
（ｑmax で表す）は、プロセッサの個数ｐによって制限
される。前に述べたように本発明においては、ｐの値
は、ＲＡＭバッファメモリのサイズＤ、ディスクの個数
ｍ、及び取り出されるデータの量すなわちサイズｄ部分
に基づいて、ビデオ・サーバによってサポートすること
のできる同時ストリームの個数が最大になるように計算
される。
【００６０】本ＦＧストライピング手法については、プ
ロセッサの個数ｐは、次の数式［数３］で与えられる。
これは、そのビデオ・サーバによってサポートすること
のできる同時ストリームの個数を最大にするのに必要な
最小個数である。言い換えれば、ｐ＝ｑmax である。
【００６１】
【数３】
【００６２】ビデオＶi の同時ストリームの各々につい
てのデータが、処理待ちの顧客要求からの各ラウンドに
ついてビデオ・サーバによって組み立てられたサービス
リストに基づいてディスクから取り出される。サービス
リストは、データがビデオＶi のストリームについて現
に取り出されつつあるそのビデオＶi のストリームの索
引である。より具体的には、サービスリストは、データ
が現に取り出されつつある箇所すなわちそのビデオＶi
の各ストリームについてのディスク上のストライプ・ユ
ニットの相対位置を表示する。
【００６３】尚、もしストライプ・ユニットが、同じビ
デオＶi には属するが異なるストリームについての異な
るストライプ・ユニットである場合には、サービスリス
トには、これら異なるストライプ・ユニットのデータ取
り出しを表示するエントリが含まれる。更に、サービス
リスト上の各ビデオＶi の各ストリームは全て、そのラ
ウンドの完了前に取り出しを完了する必要があり、そう
でない場合には、ビデオＶi のストリームが中断すると
いうことに留意を要する。
【００６４】本ＦＧストライピング手法においては、前
に述べたように各ディスク・ヘッドがそれぞれのディス
ク上の同じ相対位置にあるストライプ・ユニットを同時
に取り出すので、ｍ個のディスク・ヘッドの全てに対す
る、どのストライプ・ユニットを取り出すべきかの指令
は１個のサービスリストだけによって与えられる。
【００６５】サービスリスト上のエントリの個数（ｑで
表す）は、取り出されつつある同時ストリームの個数を
反映する。このことを考慮すると、サービスリスト上の
エントリの個数は、そのビデオ・サーバによってサポー
トすることのできる同時ストリームの最大個数を決して
超えてはならない。すなわち、ｑ≦ｑmax である。
【００６６】しかし、サービスリスト上のビデオ・エン
トリの個数ｑがｑmax を超えないという事実だけでは、
サービスリストに記入されているビデオＶi がｐ個のプ
ロセッサ上でスケジューリングすることが可能であると
の保証にはならない。スケジュールの衝突すなわち競合
は一般に、ビデオＶi の新たなストリームが始まる個々
の周期に起因する。
【００６７】本ＦＧストライピング手法においては、ビ
デオＶi についてのデータ取り出しをスケジューリング
する問題は、ｐ個のプロセッサ上で周期Ｐ1,...,Ｐn と
計算時間Ｃi とを有するノン・プリエンプティブ・タス
クＴ1,...,Ｔn をスケジューリングするのと同じであ
る。
【００６８】前に述べたように、タスクＴi は、単一デ
ィスク上でビデオＶi の１個のストリームに属する全て
のデータを取り出すジョブに対応する。この定義を本Ｆ
Ｇストライピング手法に適用すると、タスクＴi は、１
個のディスクから同じビデオＶi に属するｗi 個のスト
ライプ・ユニットからなるストライプ・ユニット・ブロ
ックを取り出す作業、例えばディスク３０−１からＶi,
j〜Ｖi,1+w・mのストライプ・ユニットを取り出す作業か
ら構成されることになる。
【００６９】タスクＴi を完了するに要する時間を、計
算時間Ｃi と称し、ラウンドを単位として表す。本ＦＧ
ストライピング手法においては、計算時間Ｃi は１個の
ディスク上でビデオＶi に属するストライプ・ユニット
・ブロック全体を取り出すのに要するラウンドの個数に
等しい。すなわち次の数式で表される関係となる。
【数４】
【００７０】尚、単位計算時間を有する周期的タスクが
単一のプロセッサ上でスケジューリング可能かどうかを
定めるという、より簡単な問題でも、解を得るには「NP
-hard」 レベルの複雑さがあることが、文献（S.Barua
h, et al."International Computer Symposium, Taiwa
n," pages 315-320, published 1990） に示されてい
る。ここに、「NP-hard」 は、技術的に周知の用語で、
「多項式アルゴリズムが与えられていないために解が困
難(NP-hard)」 のような、解を得るための複雑さのレベ
ルを意味する。
【００７１】（第１の「きめを粗くした」ディスク・ス
トライピング手法）図４に、ビデオＶi を格納し、取り
出すための第１の「きめを粗くした（Coarse-Graine
d）」ディスク・ストライピング手法（以下、第１のＣ
Ｇストライピング手法とも表記）を例示する。第１のＣ
Ｇストライピング手法は、下に述べる点を除いてはＦＧ
ストライピング手法に全ての面で類似する。
【００７２】図４に示すように、１個以上のスーパ・ビ
デオ＾Ｖh （すなわち互いに連鎖状に連続する複数のビ
デオからなるスーパ・ビデオ・グループ）に属するスト
ライプ・ユニット＾Ｖh,j （４２−１〜４２−ｍ）が、
順次にディスク４０−１〜４０−ｍ上に隣接して格納さ
れる。
【００７３】ＦＧストライピング手法と対照的に、この
第１のＣＧストライピング手法におけるストライプ・ユ
ニットのサイズｓｕは、ｄより大きく、望ましくはｄに
等しい。各スーパ・ビデオ＾Ｖh を構成する各ビデオＶ
i は全て、望ましくは、ｄとｍとの倍数である長さ＾ｌ
i(エルアイ) を有し、この長さは、各ディスクがそのスーパ
・ビデオ＾Ｖh に属するｗh 個のストライプ・ユニット
からなるブロックを有するような長さにする。
【００７４】ＣＧストライピング手法は次の点でＦＧス
トライピング手法と根本的に異なる。すなわち、ＣＧス
トライピング手法においては一般に、１度に１個のディ
スク・ヘッドを用いてスーパ・ビデオ＾Ｖh の各ストリ
ームについてのデータを取り出す点である。このように
する理由は、本ＣＧストライピング手法においては各ス
トライプ・ユニットのサイズがｓｕ＝ｄであるからであ
る。これは、各ストライプ・ユニットのサイズがｓｕ＝
ｄ／ｍであるＦＧストライピング手法と対照的である。
【００７５】第１のＣＧストライピング手法の、互いに
連続するラウンドｒh において、同じスーパ・ビデオ＾
Ｖh に属する互いに連続するストライプ・ユニットが、
互いに連続するディスクからそれぞれのディスク・ヘッ
ドによって取り出される。例えば、ストライプ・ユニッ
トＶh,1 （４２ー１）が第１のラウンドにおいてディス
ク４０−１から取り出され、ストライプ・ユニットＶh,
2 （４２ー２）が第２のラウンドにおいてディスク４０
−２から取り出される（以下同様）。
【００７６】ＦＧストライピング手法と異なり、第１の
ＣＧストライピング手法においては、１個のディスク上
の同じスーパ・ビデオ＾Ｖh に属する隣接するストライ
プ・ユニットがＦ個のラウンドの時間間隔を置いて取り
出される。
【００７７】具体的には、第１のＣＧストライピング手
法においては、互いに連続するストライプ・ユニットが
ｍ個のディスク上に順次に格納されるので、同じ１個の
ディスク上の隣接するストライプ・ユニットは、ｍ個の
ラウンドの時間間隔を置いて取り出される。例えば、ス
トライプ・ユニット４２−１が第１のラウンドにおいて
ディスク４０−１から取り出され、ディスク４０−１上
の次のストライプ・ユニット、すなわちストライプ・ユ
ニット４２−１＋ｍは（１＋ｍ）番目のラウンドにおい
て取り出される。
【００７８】この第１のＣＧストライピング手法におい
ては、全てのディスク・ヘッドについて、それぞれ別個
のサービスリストがビデオ・サーバによって用意され
る。したがって、サービスリストはｍ個存在する。これ
らのサービスリスト上の各エントリは、単一のディスク
から取り出されつつあるデータのサイズｄ部分を表示す
る。これは、ＦＧストライピング手法においては各エン
トリが、取り出されつつあるデータのディスク当たりの
サイズｓｕ＝ｄ／ｍ部分を表示すると対照的である。
【００７９】この第１のＣＧストライピング手法におい
ては、各エントリはデータのサイズｄ部分１個の取り出
しを表示するので、各エントリについて１個のプロセッ
サが必要である。もしｑdisk・maxを１個のサービスリス
ト上のエントリの最大個数とした場合、ｑdisk・max・ｍ
は、そのビデオ・サーバがサポートできる同時ストリー
ムの最大個数を意味する。
【００８０】言い換えれば、この第１のＣＧストライピ
ング手法において、ビデオ・サーバがサポートできる同
時ストリームの個数を最大にするためのプロセッサの最
小必要個数はｐ＝ｑdisk・max・ｍである。この値ｐの定
め方については下で述べる。１個のサービスリスト中の
エントリの個数をｑdiskで表す。
【００８１】第１のＣＧストライピング手法では、各ラ
ウンドｒh の終わりの時点で、第１のディスクを除く全
てのディスクについてのサービスリストは、それぞれの
ディスクの前のディスクのサービスリストに合わせて設
定される。例えば、ラウンド１におけるディスク３０−
１についてのサービスリストが、ラウンド２におけるデ
ィスク３０−２についてのサービスリストになる。
【００８２】この理由は、次のラウンドにおいて取り出
されることになるビデオの互いに連続するサイズｄ部分
が位置する次のディスク上での相対位置が、前のサイズ
ｄ部分が位置した前のディスク上での相対位置と同じた
めである。そして、各ラウンドの都度新しいサービスリ
ストを与えられるのは第１のディスクだけである。
【００８３】したがって、もし第１のディスクについて
のサービスリストに含まれるスーパ・ビデオ＾Ｖh のエ
ントリに関してデータ取り出しのスケジューリングが可
能な場合には、その後に連続するラウンドｒh における
他のディスクでも同じスーパ・ビデオ＾Ｖh についてデ
ータ取り出しのスケジューリングが可能である。
【００８４】第１のＣＧストライピング手法において
は、値ｄは次の数式［数５］で与えられる。
【００８５】
【数５】
【００８６】ディスクはｍ個あるので、取り出し可能な
スーパ・ビデオ＾Ｖh のサイズｄ部分の最大値は、ｑ
disk・max・ｍである。ＦＧストライピング手法と同様
に、第１のＣＧストライピング手法において必要とされ
るプロセッサの個数は、ＲＡＭバッファメモリのサイズ
Ｄとディスクの個数ｍと取り出し可能な最大データ量と
に基づいて計算される。第１のＣＧストライピング手法
においては、このプロセッサの個数ｐは次の式で表され
る。
【００８７】
【数６】
【００８８】第１のＣＧストライピング手法において、
スーパ・ビデオ＾Ｖh についてのデータを周期的に取り
出す問題は、ｐ個のプロセッサ上で、ｗh 個の互いに連
続しないストライプ・ユニットを有するタスク＾Ｔh 、
すなわち＾Ｔ1,...,＾ＴR をスケジューリングする問題
と同じである。各タスク＾Ｔh はｗh 個のサブ・タスク
を有し、各サブ・タスクは単位計算時間を有する。Ｆ個
のラウンドからなる時間間隔が、同じタスクＴh に属す
る隣接するサブ・タスク間に挿入される。
【００８９】すなわち、タスク＾Ｔh についての計算時
間＾Ｃh は、ｗh 個のラウンドに（ｗh −１）個のラウ
ンドを加えたもの、すなわち（２ｗh −１）個のラウン
ドとなる。尚、単一のサブ・タスクを有するタスクを１
個のマルチプロセッサ上でスケジューリングするとい
う、より簡単な問題でも解を得るには「NP-hard」 レベ
ルの複雑さがあることが、上記の文献（S.Baruah, et a
l.）に示されている。
【００９０】（第２の「きめを粗くした」ディスク・ス
トライピング手法）図５に、ビデオＶi を格納し、取り
出すための第２の「きめを粗くした（Coarse-Graine
d）」ディスク・ストライピング手法（以下、第２のＣ
Ｇストライピング手法とも表記）を例示する。第２のＣ
Ｇストライピング手法は、下に述べる点を除いてはＦＧ
ストライピング手法に全ての面で類似する。
【００９１】第１のＣＧストライピング手法とは対照的
に、第２のＣＧストライピング手法においては、１個以
上のスーパ・ビデオ＾Ｖh に属するｗh 個のストライプ
・ユニット＾Ｖh,j からなるブロック（５２−１〜５２
−ｍ）が、順次にディスク５０−１〜５０−ｍ上に隣接
して格納される。ここに、ｗh は次の式で与えられ、同
式中の＾ｌh はスーパ・ビデオ＾Ｖh の長さに対応す
る。
【数７】
【００９２】第２のＣＧストライピング手法において
は、ｗh の値はスーパ・ビデオ＾Ｖhの各ブロック全て
にわたって同一である。各スーパ・ビデオ＾Ｖh の長さ
＾ｌhはｗh の倍数で、その値は、スーパ・ビデオ＾Ｖh
のブロックが格納されている各ディスクが、各スーパ
・ビデオ＾Ｖh についての互いに連続するｗh 個のスト
ライプ・ユニットからなるブロックを有するような、ｗ
h の倍数である。
【００９３】各スーパ・ビデオ＾Ｖh の全てについて、
第１のｗh 個のストライプ・ユニットはディスク５０−
１に格納される。互いに連続するｗh 個のストライプ・
ユニットからなる次に続くブロックは次に続くディスク
に格納される。
【００９４】第１のＣＧストライピング手法と同様に、
第２のＣＧストライピング手法においては、１個のディ
スク・ヘッドを用いて同じディスクからスーパ・ビデオ
＾Ｖh のサイズｄ部分のストライプ・ユニットが、或る
ラウンドｒh から始めて、次に続く＾Ｐh 個のラウンド
の時間長さの間に取り出される。
【００９５】第１のＣＧストライピング手法と異なり、
むしろＦＧストライピング手法に似て、第２のＣＧスト
ライピング手法においては、同じスーパ・ビデオ＾Ｖh
ストリームについて同じディスクから互いに連続するラ
ウンドにおいてデータを取り出す作業を、ｗh 個のスト
ライプ・ユニットからなるブロック全体がそのディスク
から取り出されるまで継続する。
【００９６】例えば、第１のｗh 個のラウンドにおいて
ストライプ・ユニット５２−１〜５２−ｗh がディスク
５０−１から取り出され、次のｗh 個のラウンドにおい
てストライプ・ユニット５２−１＋ｗh 〜５２−２・ｗ
h がディスク５０−２から取り出される（以下同様）。
したがって、同じタスク＾Ｔh に属する隣接するサブ・
タスク間にＦ個のラウンドの時間間隔が挿入されてはい
ない。
【００９７】同じタスク＾Ｔh の、互いに連続するサブ
・タスク間に時間間隔が挿入されていないので、第２の
ＣＧストライピング手法においてビデオを周期的にスケ
ジューリングする問題は、ＦＧストライピング手法にお
いてビデオを周期的にスケジューリングする問題に類似
する。これは、周期＾Ｐi すなわち＾Ｐ1,...,＾ＰR及
び計算時間＾Ｃh を有するノン・プリエンプティブなタ
スク＾Ｔ1,...,＾ＴRをスケジューリングする問題であ
る。
【００９８】第２のＣＧストライピング手法において
は、各タスク＾Ｔi は、互いに連続するｗh 個のストラ
イプ・ユニットを取り出す作業から構成される。すなわ
ち、サブ・タスクはｗh 個存在する。計算時間＾Ｃh は
ｗh 個のラウンドの時間長さに等しい。
【００９９】［スケジューリング手法］下に設けた項目
において、ビデオについてのデータを多数のプロセッサ
上で周期的に取り出すときに生じる、スケジューリング
に関する２つの基本的な問題に対するスケジューリング
手法を説明する。概していえば、スケジューリング手法
は、タスクがスケジューリング可能かどうかを定める作
業と、もしスケジューリング可能であると判断された場
合には、タスクの開始時間をスケジューリングする作業
とに関わる。
【０１００】（第１のスケジューリング手法）第１のス
ケジューリング手法は、強化ペイ・パー・ビュー方式を
用いるビデオ・サーバにおいてＦＧストライピング手法
及び第２のＣＧストライピング手法を用いた際に生じる
スケジューリング問題を取り扱う。
【０１０１】具体的には、第１のスケジューリング手法
は、ｐ個のプロセッサ上で、周期Ｐi すなわちＰ1,...,
Ｐn 又は＾Ｐ1,...,＾ＰR 及び計算時間Ｃi（又は＾
Ｃh）を有するノン・プリエンプティブなタスクＴi す
なわちＴ1,...,Ｔn 又は＾Ｔ1,...,＾ＴR をスケジュー
リングするための有効な方法を提供するものである。
【０１０２】尚、説明を分かりやすくするために、第１
のスケジューリング手法についての以下の記述はＦＧス
トライピング手法に関して行うこととするが、第１のス
ケジューリング手法は、下に特記する場合を除いては第
２のＣＧストライピング手法にも等しく適用することが
可能である。
【０１０３】ＦＧストライピング手法においては、第１
のスケジューリング手法は、ｐ個のプロセッサを有する
ビデオ・サーバが、１個のサービスリストに含まれるビ
デオのグループを処理するように作動するかどうかを定
める。そうであるためには、その１個のサービス・リス
ト上の全てのビデオがｐ個のプロセッサ上でスケジュー
リング可能でなければならない。これは、ｍ個のサービ
ス・リストがある第２のＣＧストライピング手法の場合
と異なる点である。
【０１０４】第２のＣＧストライピング手法に適用した
場合には、第１のスケジューリング手法は、ｐ個のプロ
セッサを有するビデオ・サーバが、（ｐ／ｍ）個のプロ
セッサ上で第１のディスクに属するサービス・リストに
含まれるビデオを処理するように作動するかどうかを定
める。したがって、第２のＣＧストライピング手法にお
いては、第１のスケジューリング手法は、第１のディス
クに属するサービス・リスト上のビデオが、（ｐ／ｍ）
個のプロセッサ上でスケジューリング可能かどうかを定
める。
【０１０５】第１のスケジューリング手法は、ＦＧスト
ライピング手法及び第２のＣＧストライピング手法を用
いる際に生じるスケジューリング問題を取り扱うのに、
３種類の手順を利用する。
【０１０６】これら３種類のうちの第１の手順（「手順
１」と称する）では、１個のタスク・グループ（Ｇで表
す）を構成するタスクが、１個未満のプロセッサ上でス
ケジューリングすることが可能でないかどうかによって
Ｇ１とＧ２との２個のタスク・サブグループ（サブグル
ープ）に分割される。ここに、もし１個以上のタスクが
同じプロセッサ上でスケジューリング可能な場合に、そ
のタスクは１個未満のプロセッサ上でスケジューリング
可能であると定義する。
【０１０７】「手順１」は次に、サブグループＧ１及び
Ｇ２の両方を別個にスケジューリングすることを試み
る。１個未満のプロセッサ上でスケジューリングするこ
とが可能でないサブグループをＧ１で表すと、このサブ
グループＧ１については、「手順１」が、ｐ’個のプロ
セッサ上でタスクをスケジューリングする。尚、ｐ＝
ｐ’＋ｐ”。ここに、ｐはそのビデオ・サーバ内のプロ
セッサの個数である。
【０１０８】１個未満のプロセッサ上でスケジューリン
グすることが可能なサブグループをＧ２で表すと、この
サブグループＧ２については、「手順１」が、上記３種
類のうちの第２の手順（「分割手順」と称する）を呼び
出し、残りのｐ”個のプロセッサの各々について１個の
サブセットＧ２−ｙが存在するようにサブグループＧ２
を更にサブセットＧ２−ｙに分割させる。
【０１０９】次に「手順１」は、各サブセットＧ２−ｙ
が１個のプロセッサ上でスケジューリング可能であるか
どうかの第１回の判断を行う。もしサブセットＧ２−ｙ
が１個のプロセッサ上でスケジューリング可能である場
合、「手順１」はサブセットＧ２−ｙ内のタスクのスケ
ジューリングを行う。
【０１１０】そうでない場合には、「手順１」は、第３
の手順（「タスク・スケジューリング手順１」（又は簡
単に、「ＴＳ手順１」）と称する）を呼び出し、第１回
の判断でスケジューリング可能でないと判断された、そ
のサブセットＧ２−ｙのスケジューリング可能性につい
て第２回の判断を行わせる。
【０１１１】もし「ＴＳ手順１」が、サブセットがスケ
ジューリング可能でないと判断し、且つそのサブセット
が更に分割可能であると判断した場合、「ＴＳ手順１」
は「分割手順」を呼び出し、そのサブセットＧ２−ｙを
更にサブ・サブセットＳv に分割させる。
【０１１２】サブセットＧ２−ｙがサブ・サブセットに
分割された後、「ＴＳ手順１」が自身を呼び出し、分割
されたサブセットＧ２−ｙに属する各サブ・サブセット
Ｓvの全てに対しスケジューリング可能性についての上
記第２回の判断作業を再実行する。この手法は、反復分
割として知られている。
【０１１３】この、タスクのサブグループ、サブセッ
ト、サブ・サブセット等の反復分割は、タスクのサブグ
ループ、サブセット、サブ・サブセット等がスケジュー
リング可能であると、又はもはや再分割可能でないと、
第１のスケジューリング手法が判断するまで、第１のス
ケジューリング手法によって継続される。
【０１１４】図６〜図１０に、ＦＧストライピング手法
を用いたビデオ・サーバについてのサービスリストに含
まれるビデオ・グループのスケジューリング、すなわち
周期Ｐ1,...,ＰN 及び計算時間Ｃ1,...,ＣN を有するノ
ン・プリエンプティブなタスクＴ1,...,ＴN のスケジュ
ーリング、を行うための「手順１」の例示流れ図を示
す。
【０１１５】図６のステップ６００において、グループ
Ｇ内のタスクＴi （i＝１,...,Ｎ）とｐの値とに対応す
るデータが、ビデオ・サーバのＲＡＭバッファメモリ内
に読み込まれる。グループＧに対応するデータには、タ
スクＴi、 周期Ｐi、 及び計算時間Ｃi、 すなわち｛Ｔ
i,Ｐi,Ｃi｝ が含まれる。尚、第２のＣＧストライピン
グ手法においては、ＲＡＭバッファメモリ内に読み込ま
れるｐの値はｐ／ｍとなる。
【０１１６】ステップ６０５において、タスクＴi が、
それぞれの対応する周期Ｐi 及び計算時間Ｃi に基づい
てサブグループＧ１及びＧ２に分類される。自身の周期
Ｐiより大きいか等しい値の計算時間Ｃi を有するタス
クＴi は、１個未満のプロセッサ上でスケジューリング
可能でない。
【０１１７】その理由は、これらのタスクが１個のプロ
セッサ全体を独占するか又は自身と競合する、すなわち
同時に２個以上のタスク・ストリームがプロセッサによ
る取り扱いを要求するからである。これらのタスクはサ
ブグループＧ１に入れられ、タスクＴx と表す。すなわ
ちＴx ∈Ｇ１である。
【０１１８】自身の周期Ｐi より小さい値の計算時間Ｃ
i を有するタスクＴi は、１個未満のプロセッサ上でス
ケジューリング可能である。これらのタスクはサブグル
ープＧ２に入れられ、タスクＴy と表す。すなわちＴy
∈Ｇ２である。
【０１１９】「例１」を用いて第１のスケジューリング
手法を説明する。次に列記する値ｐとサービスリスト内
のタスクＴi とに対応するデータがステップ６００にお
いてＲＡＭバッファメモリ内に読み込まれる。すなわ
ち、ｐ＝６、｛Ｔ1,４,８｝、｛Ｔ2,４,１｝、 ｛Ｔ3,
４,１｝、 ｛Ｔ4,３,７｝、 ｛Ｔ5,６,１｝、 及び｛Ｔ
6,６,１｝ である。
【０１２０】ステップ６０５において、タスクＴ1 及び
Ｔ4 はサブグループＧ１に属するものとして分類され
る。すなわちＧ１＝｛Ｔ1,Ｔ4｝ である。又タスク
Ｔ2、Ｔ3、Ｔ5、 及びＴ6 はサブグループＧ２に属する
ものとして分類される。すなわちＧ２＝｛Ｔ2,Ｔ3,
Ｔ5，Ｔ6｝ である。
【０１２１】ステップ６１０〜６３６において、「手順
１」が、ｐ’個のプロセッサ上でサブグループＧ１に属
するタスクＴx のスケジューリングを行う。ここに、
ｐ’はタスクＴx ∈Ｇ１の全てを取り扱うのに要するプ
ロセッサの個数である。ステップ６１０において、ｐ’
の値は初期値としてゼロに設定される。
【０１２２】ステップ６２０において、タスクＴx ∈Ｇ
１の各々全てについてループ６２０が開始される。具体
的には、ステップ６２５において、ループ６２０内の現
タスクＴx によって必要とされるプロセッサの個数ｐx
を、ループ６２０が次式を用いて定める。
【数８】
【０１２３】ループ６２０は次にステップ６３０におい
て、現在のｐx の値をｐ’に加えて、サブグループＧ１
によって必要とされるプロセッサの総数を累進的に定
め、ステップ６３５において、現タスクＴx が予め定め
られた時間、望ましくは時間ゼロ（ラウンドで表す）す
なわちＳＴx ＝０に開始するように現タスクＴx をスケ
ジューリングする。ループ６２０は、各タスクＴx ∈Ｇ
１の全てについてプロセッサ要件及び開始時間が定めら
れたときに終了する。
【０１２４】ループ６２０の各ステップを「例１」に適
用して、次のことが定められた。すなわちタスクＴ１及
びＴ４がそれぞれ２個及び３個のプロセッサ必要とし、
時間ゼロにおいて開始するようにスケジューリングされ
た。したがって、サブグループＧ１に対して５個のプロ
セッサが用いられる。すなわち、ｐ’＝５である。
【０１２５】各タスクＴx の全てについてループ６２０
が完了するか又はもしサブグループＧ１に属するタスク
Ｔx がない場合、「手順１」はステップ６４５（図７）
に進み、ここでタスクＴy ∈Ｇ２をスケジューリングす
るのに利用可能なプロセッサの個数ｐ”を定める。
【０１２６】ステップ６４６において、もしｐ”がゼロ
より小さい場合、タスクＴx ∈Ｇ１を取り扱うのに必要
なプロセッサの総数は不十分で、「手順１」はステップ
６４７に進み、ここで「スケジューリング不可能」のメ
ッセージを返し、次にステップ６８５（図１０）でプロ
セスを終結する。
【０１２７】ステップ６４６において、もしｐ”がゼロ
より小さくない場合「手順１」はステップ６４８に進
み、ここでサブグループＧ２に属するタスクＴy がある
かどうかが定められる。もしない場合「手順１」はステ
ップ６４８ａに進み、ここでステップ６８５に進むよう
に命令され、ステップ６８５でプロセスを終結する。
【０１２８】ステップ６４８において、もしサブグルー
プＧ２に属するタスクＴy がある場合には「手順１」は
ステップ６４８ｂに進み、ここでタスクＴy ∈Ｇ２を取
り扱うために利用可能なプロセッサがあるかどうかが点
検される。もしない場合（ｐ”＝０）「手順１」はステ
ップ６４８ｃに進み、ここで「スケジューリング不可
能」のメッセージを返し、次にステップ６８５へ進んで
プロセスを終結する。
【０１２９】ステップ６４８ｂにおいて、もしタスクＴ
y ∈Ｇ２を取り扱うために利用可能なプロセッサがある
場合には、「手順１」は、利用可能なプロセッサの各々
に対して１個のサブセットＧ２−ｙが存在するようにタ
スクＴy ∈Ｇ２をサブセットＧ２−ｙに分割する作業に
進む（ここにｙ＝１,...,ｐ”）。
【０１３０】図８に示すように、ステップ６４９におい
て「手順１」は、タスクＴy について利用可能なプロセ
ッサの個数を点検する。もしｐ”が１の場合、全てのタ
スクＴy は、その利用可能な１個のプロセッサ上でスケ
ジューリングする必要がある。そして「手順１」はステ
ップ６５０に進み、ここでサブセットＧ２−１がサブグ
ループＧ２に等しく設定されて、「手順１」はステップ
６６０に進む。
【０１３１】もしｐ”が１でない場合には、「手順１」
はステップ６４９からステップ６５１及び６５５に進
み、ここで「分割手順」が呼び出されて、サブグループ
Ｇ２をｐ”個の、互いに共通な部分のない（以下、素、
と称する）サブセットＧ２−ｙに反復分割する。「分割
手順」については下に詳しく述べる。
【０１３２】「例１」において、サブグループＧ２につ
いて利用可能なプロセッサの個数は１個である。したが
って、ステップ６５０において、サブセットＧ２−１が
サブグループＧ２、すなわち｛Ｔ2,Ｔ3,Ｔ5，Ｔ6｝に等
しくセットされる。サブセットＧ２−ｙ内のタスクをＴ
dと表す（ここにｄ＝１,...,ｎ）。すなわち、Ｔd ∈Ｇ
２−ｙである。
【０１３３】ステップ６６０において、各サブセットＧ
２−ｙ全てについてループ６６０が開始され、スケジュ
ーリング可能性、すなわち各サブセットＧ２−ｙが１個
のプロセッサ上でスケジューリング可能かどうか、の第
１回の判断がなされる。ステップ６７０（図９）におい
て、次の定理（「定理１」と称する）が「手順１」内で
適用される。
【０１３４】すなわち「もしＣ1＋...＋Ｃn≦ｇｃｄ
（Ｐ1＋...＋Ｐn）である場合、タスクＴ1,...,Ｔn は
単一のプロセッサ上でスケジューリングすることが可能
である。ここに、ｇｃｄ（Ｐ1＋...＋Ｐn） は周期Ｐd
の最大公約数であり、各タスクＴ1,...,Ｔn についての
開始時間ＳＴ1,...,ＳＴn は、前にスケジューリングさ
れたタスクＴd の計算期間Ｔd を加算すること、すなわ
ち次式の値を求めることによって定められるという定理
である。
【０１３５】
【数９】 同式において、０≦ｄ’＜ｄである。尚、ｄ＝１の場
合、スケジューリングされた最初のタスクＴ1 は、時間
ゼロにおいて開始される。
【０１３６】もし或るサブセットＧ２−ｙが「定理１」
を満足する場合、そのサブセットＧ２−ｙ内の各タスク
Ｔd は次式で表す開始時間においてスケジューリングす
ることが可能である。同式において、Ｑは任意の正の整
数であり、各Ｔd は、最大公約数（ｇｃｄ）に等しい各
時間長さ（ｇｃｄ時間長さ、とも称する）内に１個以上
のラウンドをその専用として留保する。
【数１０】
【０１３７】尚、「定理１」を満足させなくても、サブ
セットＧ２−ｙが１個のプロセッサ上でスケジューリン
グすることができないと確定されるわけではない。
【０１３８】図１１は、「定理１」の有効性を証明する
例示説明図である。ここで、周期Ｐ8 ＝３、Ｐ9 ＝３、
Ｐ10＝６と計算時間Ｃ8 ＝Ｃ9 ＝Ｃ10＝１とを有するタ
スクＴ8、 Ｔ9、 Ｔ10を考える。ｇｃｄ（３,３,６）は
３、計算時間の和は３、そして「定理１」が満足され
る。ＳＴd を表す次式を用いて、タスクＴ8、 Ｔ9、 Ｔ
10の新たなストリームが、それぞれラウンド０、１、及
び２において開始するようにスケジューリングされる。
【数１１】
【０１３９】図１１に示すように単一のプロセッサ上で
タスクＴ8、Ｔ9、Ｔ10を取り扱うためのスケジュールが生
成される。具体的には各ｇｃｄ時間長さ内で第１、第２
及び第３のラウンドがタスクＴ8、Ｔ9、Ｔ10による専用と
してそれぞれ留保される。
【０１４０】すなわちラウンド０、３、６、９、１２及
び１５がタスクＴ8 に対応する新しいストリームの開始
用に留保され、ラウンド１、４、７、１０、１３及び１
６がタスクＴ9 に対応する新しいストリームの開始用に
留保され、ラウンド２、８及び１４がタスクＴ10に対応
する新しいストリームの開始用に留保される。
【０１４１】尚、ラウンド５、１１、及び１７も、これ
らのラウンドにおいて新しいストリームは開始されない
けれども、タスクＴ10による専用として対応する新しい
ストリームの開始用に留保される。したがって、各ｇｃ
ｄ時間長さ内にラウンドを留保することによって、スケ
ジューリング競合が防止される。
【０１４２】「例１」において、計算時間の和は４で、
最大公約数は２である。このため、「定理１」は満足さ
れず、「手順１」はステップ６７６（図１０）へ進む。
【０１４３】図９に示すように、もしループ６６０にお
いて「定理１」が現サブセットＧ２−ｙについて満足さ
れる場合、「手順１」はステップ６７１〜６７５に進
み、ここで次にステップ６８１（図１０）へ進む前に、
ループ６７２が、次式を用いて各Ｔd ∈Ｇ２−ｙについ
て開始時間を定める。
【数１２】
【０１４４】具体的には、ループ６７２が、前のタスク
の開始時間を加算してループ６７２における現タスクに
ついての開始時間を定める。ループ６７２の処理が完了
すると、「手順１」はステップ６８１に進み、ここでル
ープ６６０が完了かどうかを定める。もし「定理１」が
現サブセットＧ２−ｙについて満足されない場合には、
「手順１」はステップ６７６及び６８０に進み、「手順
１」を満足させなかったサブセットＧ２−ｙについてス
ケジューリングの可能性に関する第２回の判断を行う段
取りとなる。
【０１４５】まず図１０に示すようにステップ６７６に
おいて、「手順１」は、２つの条件「（１）ＣG2-yが
Ｃd∈Ｇ２−ｙより大きいか又は等しい、すなわちＣ
G2-y≧Ｃd 及び（２）ＣG2-yが各Ｐd に、均等に分割さ
れる、すなわち（ＣG2-y ｍｏｄＰd）＝０」 を満足さ
せるＣG2-yの最小値を求める。もしこれらの条件が満足
されない場合、「手順１」はステップ６７７において、
「スケジューリング不可能」のメッセージを返して、プ
ロセス終結する。
【０１４６】もしステップ６７６において、これらの条
件が満足される場合には、「手順１」はステップ６８０
に進み、ここで「タスク・スケジューリング（ＴＳ）手
順１」が呼び出されて、「定理１」を満足させられなか
ったサブセットＧ２−ｙについてスケジューリングの可
能性に関する第２回の判断を行う。
【０１４７】ステップ６７６及び６８０の手順を「例
１」に適用すると、ＣG2-yの最小値は１に等しく設定さ
れ、サブセットＧ２−１についてスケジューリングの可
能性に関する第２回の判断を行うために「タスク・スケ
ジューリング手順１」が呼び出される。
【０１４８】図１２〜図１５に、「タスク・スケジュー
リング手順１」（「ＴＳ手順１」）の例示流れ図を示
す。図１２に示すように、ステップ８００において「Ｔ
Ｓ手順１」が、データをサブグループＧ３内のタスクＴ
e 及びＣG3として読み取る。すなわち、「手順１」から
のタスクＴd ∈Ｇ２−ｙ及びＣG2-yが、それぞれ「ＴＳ
手順１」によって、タスクＴe ∈Ｇ３及びＣG3として読
み取られる。
【０１４９】尚、サブセットＧ２−ｙについての「手順
１」から「タスク・スケジューリング（ＴＳ）手順１」
へのこの呼び出しによって呼び出された「ＴＳ手順１」
を、第１回呼び出しの「ＴＳ手順１」と称する。
【０１５０】ステップ８０５（図１２）〜ステップ８２
４（図１３）において「ＴＳ手順１」が、タスクＴe を
サイズＣG3のｇ個の貯蔵箇所（ビン）Ｂ−ｘに詰め分け
る（パッキングする）ことによって、スケジューリング
可能性の第２回判断を行う。ここに、計算時間Ｃe に応
じてｘ＝１,...,ｇ である。ステップ８０５において、
ｇの値が式ｇ＝（ｇｃｄ（Ｐ1,...,Ｐn））/ＣG3を用い
て定められ、ステップ８１０において、タスクＴe がビ
ンＢ−ｘにパッキングされる。
【０１５１】ステップ８１０において望ましくは、タス
クＴe が計算時間Ｃe に応じた降順に並べられ、次いで
並べ順に１度に１タスクづつ１個のビンＢ−ｘに割り当
てられる。この場合のビンは、そのビン内の、前に割り
当てられたタスクＴe の計算時間Ｃe の和が最小になる
ようなビンである。対（ｘ,ａ）によって特定のタスク
Ｔe がパッキングされた後のそのタスクＴe の位置を表
示することとする。ここに、ｘはビン番号、ａはタスク
Ｔe のビンｘ底部からの距離を計算時間で表した値であ
る。
【０１５２】ステップ８０５〜８１０を「例１」に適用
すると、値ｇは２に設定され、ビンＢ−１は底部から頂
部までタスクＴ2 及びＴ5 を収納し、ビンＢ−２は底部
から頂部までタスクＴ3 及びＴ6 を収納することにな
る。
【０１５３】ステップ８２０において、各ビンが点検さ
れてビンＢ−ｘに割り当てられたタスクＴe についての
計算時間Ｃe の和がＣG3の値より小さいか又は等しいか
が定められる。もしステップ８２０の条件が各ビンＢ−
ｘについて満足される場合、サブグループＧ３に属する
タスクＴe は互いに競合せず、スケジューリングが可能
である。その場合、「ＴＳ手順１」は図１３のステップ
８２１〜８２４に進み、ここでループ８２１における各
タスクＴe ∈Ｇ３について開始時間ＳＴe が定められ
る。
【０１５４】具体的にはステップ８２２において、ルー
プ８２１における現タスクＴe について開始時間ＳＴe
が、式ＳＴe ＝（ＣG3・ｘ）＋ａを用いてその対（ｘ，
ａ）に応じて計算される。各タスクＴe について開始時
間ＳＴe が定められると、これらの開始時間はステップ
８２４において呼び出し側プログラムに返される。尚呼
び出し側プログラムは、後に述べるように「手順１」、
又は前のレベルの呼び出し点の「タスク・スケジューリ
ング手順１」のいずれかである。
【０１５５】ステップ８２０の条件が満足されない場合
には、タスクＴe ∈Ｇ３について、後のレベルの「ＴＳ
手順１」が呼び出される。その場合には「ＴＳ手順１」
が、サブグループＧ３のサブセットＳv （ｖ＝１,...,
ｇ)への分割を反復して試み、それから各サブセットＳ
v について「ＴＳ手順１」を呼び出すことによって、各
サブセットＳv 内のタスクのスケジューリングを試み
る。
【０１５６】ステップ８２０の条件を満足させないタス
クＴe ∈Ｇ３のグループについては、「ＴＳ手順２」が
ステップ８２５（図１３）に進み、ここでサブグループ
Ｇ３の更なる反復分割が可能かどうかが定められる。も
しステップ８２５においてｇの値が１の場合、サブグル
ープＧ３を更に反復分割することはできない。そしてス
テップ８２６において呼び出し側プログラムに対して
「スケジューリング不可能」のメッセージが返される。
【０１５７】もしステップ８２５においてｇの値が１で
ない場合には、図１４のステップ８３０において、サブ
グループＧ３内のデータがサブグループ、￣Ｇ３に、す
なわち｛Ｔe,Ｐe,Ｃe｝ から｛￣Ｔe,￣Ｐe,￣Ｃe｝ に
変形される。ここに、 ｛￣Ｔe,￣Ｐe,￣Ｃe｝＝｛Ｔe,
Ｐe/ｇ,Ｃe｝である。そしてステップ８３５において、
「分割手順」が呼び出されてサブグループ￣Ｇ３をサブ
セットＳv に反復分割する（尚、￣Ｔe は、本来Ｔe の
直上に￣を配置する表記を用いるところを、便宜上これ
に代わる簡易表記として用いる（以下同様））。
【０１５８】「例１」において、ビンＢ−１に対する計
算時間Ｃ2 及びＣ5 の和、並びにビンＢ−２に対する計
算時間Ｃ3 及びＣ6 の和はいずれも２で、値１のＣG3よ
り大きい。すなわち、ステップ８２０（図１２）の条件
は満足されない。したがって、「例１」のタスクＴe に
対応するデータは、分割される前にステップ８３０にお
いて変形される。変形されたデータは、｛￣Ｔ2,4/2,
１｝、｛￣Ｔ3,4/2,１｝、｛￣Ｔ5,6/2,１｝及び｛￣Ｔ
6,6/2,１｝となる。
【０１５９】「分割手順」の呼び出しから戻ると、「Ｔ
Ｓ手順１」はステップ８４０及び８４５において、後の
レベルで自身を呼び出して、各サブセットＳv のスケジ
ューリングを試みる。各サブセットＳv についての「Ｔ
Ｓ手順１」の自身に対する呼び出しからなるこの第１の
呼び出しグループを、第２レベルの「ＴＳ手順１」呼び
出し、と称する。尚、第２レベルの「ＴＳ手順１」呼び
出しにおいては、タスク￣Ｔe∈Ｓvに対応するデータ
が、後のレベルの呼び出しで呼び出された「ＴＳ手順
１」によりＴe ∈Ｇ３として読み取られる。
【０１６０】「スケジューリング不可能」のメッセージ
又は開始時間が前のレベルの呼び出しで呼び出された
「ＴＳ手順１」に返されるまでは、第２レベルの「ＴＳ
手順１」呼び出しが、第３レベルの「ＴＳ手順１」呼び
出しに至り、第３レベルの「ＴＳ手順１」呼び出しが、
第４レベルの「ＴＳ手順１」呼び出しに至る等、次のレ
ベルの「ＴＳ手順１」呼び出しが順次発動される。
【０１６１】前に述べたように、レベル１の呼び出し
は、ステップ６８０において「ＴＳ手順１」が「手順
１」によって呼び出されたときに発生する。ステップ８
５０において「ＴＳ手順１」が、いずれかのレベルの呼
び出しで呼び出された「ＴＳ手順１」によって「スケジ
ューリング不可能」のメッセージが返されたかどうかが
定められる。
【０１６２】もしこのようなメッセージが返された場
合、タスクＴy ∈Ｇ２はｐ”個のプロセッサ上でスケジ
ューリング不可能と見なされ、「ＴＳ手順１」がステッ
プ８５１において、「スケジューリング不可能」のメッ
セージを呼び出し側のプログラムに返す。
【０１６３】もしステップ８４５における前のレベルの
呼び出しで呼び出された「ＴＳ手順１」に対して、開始
時間が「ＴＳ手順１」によって返される場合には、ステ
ップ８６０（図１５）において、開始時間が次の計算式
を用いて合体された後呼び出し側プログラムに返され
る。 （計算式）ＳＴe＝Ｒ・ｇ・ＣG3＋（ｖ−１）・ＣG3＋Ｙ。
【０１６４】式中Ｒは次式で表され、Ｔe＝￣Ｔe、１≦
ｖ≦ｇ、Ｙ＝￣(ＳＴe)−Ｒ・ＣG3、そして￣(ＳＴe)
は、ステップ８４５において後のレベルの「ＴＳ手順
１」によって返される開始時間である（￣(ＳＴe) は、
ＳＴe の直上に￣を配置した表記と同義の簡易表記であ
る）。
【数１３】
【０１６５】尚、ＣG3の値は、後の「ＴＳ手順１」呼び
出しプロセスの全てを通じて同じ値を取り続ける。
【０１６６】図１６〜１９は「分割手順」の例示流れ図
である。図１６に示すように、ステップ９００において
「分割手順」がデータを、タスク・グループＧ４内のタ
スクＴj、 及びｇ、として読み取る。「分割手順」は、
周期の最大公約数ｇｃｄ（Ｐ1,...,Ｐn） と計算時間Ｃ
j の和との差である余裕値に応じて、タスクＴj ∈Ｇ４
をサブセットＳv に順次割り当てる。
【０１６７】スケジューリング可能であるためには、各
サブセットＳv は、負でない余裕値を有する必要があ
る。すなわち、或るサブセット内の周期Ｐj の最大公約
数が同じサブセット内の計算時間の和よりも大きいか又
は等しいことを要する。
【０１６８】したがって、「分割手順」の目標は、全て
のサブセットが負でない余裕値を有するようにタスクＴ
j をサブセットＳv に割り当てることである。「分割手
順」は、この目標を達成するために、サブセットＳv の
余裕値の全体値を最大化する。尚、ｇｃｄ（Ｐ1,...,Ｐ
n）は、ｇｃｄ（Ｔ1,...,Ｔn）とも表す。
【０１６９】ステップ９０５〜９８０において、「分割
手順」は、タスク・グループＧ４からタスクＴj を空き
サブセットＳv の各々に割り当てる。すぐ判るように、
サブセットはタスクを割り当てられていない場合に、空
きである、と称する。
【０１７０】各空きサブセットＳv に割り当てられたタ
スクＴj は、もしそのタスクＴj が空きでないサブセッ
トＳ1,...,Ｓv-1 に割り当てられた場合に余裕値が最小
になるような特定のタスクＴj ∈Ｇ４である。
【０１７１】ステップ９０５において「分割手順」は、
第１のタスクＴj ∈Ｇ４をサブセットＳ1 に割り当て
る。具体的には「分割手順」が、もしタスクＴj ∈Ｇ４
がサブセットＳ1 に割り当てられたとした場合のサブセ
ットＳ1 についての余裕値を点検し、次にステップ９１
０において、もしサブセットＳ1 に割り当てられたとし
た場合に余裕値が最小になるようなタスクＴs がサブセ
ットＳ1 に割り当てられ、タスク・グループＧ４から除
去される。
【０１７２】言い換えれば、タスクＴs は、各タスクＴ
j ∈Ｇ４について ｇｃｄ（Ｐs）−Ｃs ≦ ｇｃｄ（Ｐ
j）−Ｃj であるようなタスク・グループＧ４内のタス
クである。
【０１７３】「例１」においては、タスク￣Ｔe が、余
裕値が１になるのでサブセットＳ1に割り当てられる。
タスク￣Ｔ3、 Ｔ5 及びＴ6 はそれぞれ、余裕値が１、
２及び２になる。
【０１７４】ステップ９３０においてループ９３０が開
始され、ここで、残っている空きサブセットＳv の各々
に１度に１タスクづつ割り当てが行われる。尚、ループ
９３０の開始時点においてはサブセットＳ2,...,Ｓg は
空きである。ループ９３０はタスクＴj ∈Ｇ４を空きサ
ブセットの各々に仮の余裕値に応じて割り当てる。
【０１７５】具体的には、ステップ９３０〜９６５にお
いて「割付手順」が、タスクＴj を空きでない各サブセ
ットＳv、 すなわちＳ1,...,Ｓv-1 に仮に割り当て、空
きでない各サブセットＳv についての余裕値をｍａｘ
［Ｔj］ と称する配列（アレイ）に格納する。
【０１７６】ステップ９３５においてループ９３５が開
始され、ここで、各タスクＴj についてアレイｍａｘ
［Ｔj］ が生成される。ステップ９４０において「割付
手順」が、もしループ９３５の現タスクＴj がサブセッ
トＳ1 に割り当てられたとした場合のサブセットＳ1 に
ついての余裕値が定められる。このような余裕値が、ア
レイｍａｘ［Ｔj］ に格納される。
【０１７７】図１７のステップ９５０においてループ９
５０が開始され、ここで、現タスクＴj が空きでない他
のサブセットＳ2,...,Ｓv-1 に割り当てられたとした場
合のこれらのサブセットＳ2,...,Ｓv-1 についての仮の
余裕値が定められる。このような余裕値が、それぞれの
アレイｍａｘ［Ｔj］ に格納される。
【０１７８】現タスクＴj についてループ９３５が完了
すると、「分割手順」は図１８のす９６５〜９７０に進
み、ここで「分割手順」がアレイｍａｘ［Ｔj］ を比較
して、各タスクＴj ∈Ｇ４について、ｍａｘ［Ｔu］≦
ｍａｘ［Ｔj］ となるようなタスク・グループＧ４内の
タスクＴu を見出す。言い換えれば、「分割手順」が最
小可能余裕値を、アレイｍａｘ［Ｔj］ を通して探索す
る。
【０１８０】次にステップ９７５において、タスクＴu
がループ９３０の現空きサブセットＳv に割り当てら
れ、タスク・グループＧ４から除去される。ループ９３
０は空きサブセットＳv が残らなくなるまで反復実行さ
れる。
【０１７９】「例１」においては、タスク￣Ｔ5 はサブ
セットＳ1 に割り当てられる。理由は、もしサブセット
Ｓ1 に割り当てられたとした場合のタスク￣Ｔ5 の余裕
値が−１になるからである。タスク￣Ｔ3 及び￣Ｔ6 に
ついては、もしサブセットＳ1 に割り当てられたとした
場合の余裕値はそれぞれゼロ及び−１となる。
【０１８１】ループ９３５が完了すると、ステップ９８
２〜９９２において、残りのまだ割り当てられていない
タスクＴj ∈Ｇ４が、サブセットＳv についての余裕値
の全体が最大になるようにサブセットＳv に割り当てら
れる。すなわち、ステップ９８２において各タスクＴj
∈Ｇ４の全てについてループ９８２が開始される。
【０１８２】ループ９８２が図１９のステップ９８４〜
９８８において、現タスクＴj ∈Ｇ４を空きでない各サ
ブセットＳv に仮に割り当て、各サブセットＳv につい
ての余裕値を定める。ステップ９９０において、余裕値
が最大になったサブセットＳv にタスクＴj が割り当て
られる。ステップ９８２〜９９２は、各タスクＴj が全
て割り当てられるまで反復実行される。全てのタスクＴ
j が割り当てられると、ステップ９９４において、各サ
ブセットＳv を形成するタスクＴj を表示するデータが
呼び出し側プログラムに返される。
【０１８３】ステップ９８２〜９９２を「例１」に適用
すると、もしタスク￣Ｔ3 がサブセットＳ1 及びＳ2 に
に割り当てられたとした場合の余裕値がそれぞれゼロ及
び１になるので、タスク￣Ｔ3 はサブセットＳ1 に割り
当てられる。又もしタスク￣Ｔ6 がサブセットＳ1 及び
Ｓ2 に割り当てられたとした場合の余裕値がそれぞれ−
２及び＋１になるので、タスク￣Ｔ6 はサブセットＳ2
に割り当てられる。
【０１８４】このようにして、Ｓ1 ＝｛￣Ｔ2,￣
Ｔ3｝、 そしてＳ2 ＝｛￣Ｔ5,￣Ｔ6｝ となる。これ
で、手順はステップ８４０における呼び出し側プログラ
ムの「タスク・スケジューリング（ＴＳ）手順１」に戻
される。すると、第２のレベルの「ＴＳ手順１」の呼び
出しが、サブセットＳ1 ＝｛￣Ｔ2,￣Ｔ3｝、 及びＳ2
＝｛￣Ｔ5,￣Ｔ6｝ について行われる。
【０１８５】これらの第２のレベルの呼び出しにおいて
は、「タスク・スケジューリング（ＴＳ）手順２」のス
テップ８０５〜８２４の命令によって、サブセットＳ１
及びＳ２ がスケジューリング可能であることが定め
られ、開始時間、￣(ＳＴ2)＝０、 ￣(ＳＴ3)＝１、 ￣
(ＳＴ5)＝０、 ￣(ＳＴ6)＝１、 がステップ８５０にお
ける第１のレベルの「ＴＳ手順１」の呼び出しに返され
る。
【０１８６】開始時間、￣(ＳＴe) は次に、ステップ８
６０において合体され、ステップ６８０（図１０）で第
１のレベルの「ＴＳ手順１」の呼び出しに返される。開
始時間を合体させることによって、次の開始時間Ｓ
Ｔe、 すなわちＳＴ2 ＝０、ＳＴ3 ＝2、 ＳＴ5 ＝1、
ＳＴ6 ＝3、 が得られる。
【０１８７】（第２のスケジューリング手法）第２のス
ケジューリング手法は、強化ペイ・パー・ビュー方式を
用いるビデオ・サーバにおいて第１の「きめを粗くした
（ＣＧ）」ストライピング手法を用いた際に生じるスケ
ジューリング問題を取り扱う。
【０１８８】具体的には、第２のスケジューリング手法
は、ｐ個のプロセッサ上で、周期Ｐi を有するノン・プ
リエンプティブなタスクＴi をスケジューリングするた
めの有効な方法を提供するものであって、ここにタスク
Ｔi は、各々単位計算時間を有し且つ時間間隔Ｆで隔て
られたｗi 個のサブタスクからなる。
【０１８９】第２のスケジューリング手法は、第１のＣ
Ｇストライピング手法を用いる際に生じるスケジューリ
ング問題を取り扱うのに、４種類の手順を利用する。
【０１９０】これら４種類のうちの第１の手順（「手順
２」と称する）では、１個のタスク・グループ（Ｇで表
す）を構成するタスクが、単一のプロセッサ上でスケジ
ューリングすることが可能でないかどうかによってＧ１
とＧ２との２個のタスク・サブグループ（又は簡単に、
サブグループ）に分割される。
【０１９１】「手順２」は次に、サブグループＧ１及び
Ｇ２の両方を別個にスケジューリングすることを試み
る。単一のプロセッサ上でスケジューリングすることが
可能でないサブグループをＧ１で表すと、このサブグル
ープＧ１については、「手順２」が、ｐ’個のプロセッ
サ上でタスクをスケジューリングする。
【０１９２】単一のプロセッサ上でスケジューリングす
ることが可能なサブグループをＧ２で表すと、このサブ
グループＧ２については、「手順２」が、上記４種類の
うちの第２の手順（「分割手順」と称する）を呼び出
し、残りのｐ”個のプロセッサの各々について１個のサ
ブセットＧ２−ｙが存在するようにサブグループＧ２を
更にサブセットＧ２−ｙに分割させる。
【０１９３】各サブセットＧ２−ｙについて、「手順
２」が上記４種類のうちの第３の手順（「タスク・スケ
ジューリング手順２」（又は簡単に、「ＴＳ手順２」）
と称する）を呼び出してスケジューリングの可能性を定
めさせる。「ＴＳ手順２」は上記４種類のうちの第４の
手順（スケジューリング可能かどうかを点検する「スケ
ジューリング点検手順」（又は簡単に、「Ｓ点検手
順」）と称する）を呼び出し、サブセットＧ２−ｙのス
ケジューリングの可能性を定める援助をさせる。
【０１９４】もし「Ｓ点検手順」が、サブセットＧ２−
ｙはスケジューリング可能でないと定め、且つ「ＴＳ手
順２」が、同じサブセットＧ２−ｙが更に分割可能であ
ると定めた場合、「ＴＳ手順２」が「分割手順」を呼び
出し、そのサブセットＧ２−ｙを更にサブ・サブセット
Ｓv に分割させる。サブセットＧ２−ｙが分割された
後、「ＴＳ手順２」が自身を呼び出し、スケジューリン
グ可能性の再判断作業を行う。
【０１９５】この、タスクのサブグループ、サブセット
等の分割は、タスクのサブグループ、サブセット等がス
ケジューリング可能であると、又はもはや再分割可能で
ないと、第２のスケジューリング手法が判断するまで、
第２のスケジューリング手法によって反復して実行され
る。
【０１９６】図２０〜図２２に、第１のＣＧストライピ
ング手法を用いたビデオ・サーバについてのサービスリ
ストにあるビデオのスケジューリング、すなわち各々単
位計算時間と周期Ｐ1,...,ＰN とを有し時間間隔Ｆで隔
てられたｗi 個のサブタスクからなるノン・プリエンプ
ティブなタスクＴ1,...,ＴN のスケジューリング、を行
うための「手順２」の例示流れ図を示す。
【０１９７】図２０のステップ１０００において、グル
ープＧ内のタスクＴi （i＝１,...,Ｎ）とｐの値とに対
応するデータが、ビデオ・サーバのＲＡＭバッファメモ
リ内に読み込まれる。ｐの値は、第２のスケジューリン
グ手法で用いる場合には、第１のスケジューリング手法
の場合と異なり１個のディスクを取り扱うのに要するプ
ロセッサの個数を表す。
【０１９８】タスク・グループＧについてのデータに
は、タスクＴi、 単位計算時間を有するサブタスクの個
数ｗi、 周期Ｐi、 及び時間間隔Ｆ、すなわち｛Ｔi,ｗ
i,Ｐi,Ｆ｝が含まれる。尚、第１のＣＧストライピング
手法においては、同じタスクに属する隣接するサブタス
ク間の時間間隔がＦである。
【０１９９】タスクによっては、１個のタスクＴi を周
期的にスケジューリングするのに、そのサブタスクのい
くつかを同時にスケジューリングする必要がある場合が
ある。その結果、このようなタスクＴi は単一のプロセ
ッサ上でのスケジューリングができなくなる。その例示
のため「例２」について説明する。
【０２００】今、周期Ｐi ＝４、ｗi ＝３、時間間隔Ｆ
＝６、を有するタスクＴi を考えると、Ｔ1 の第１のス
トリームについて３個のサブタスクが、ラウンド０、６
および１２、でそれぞれスケジューリングされる。Ｐ1
＝４であるので、Ｔ1 の第３のストリームについての第
１のサブタスクは再度ラウンド１２においてスケジュー
リングする必要がある。したがって、ラウンド１２にお
いて競合が生じ、タスクＴ1 は単一のｐ上ではスケジュ
ーリングできない。
【０２０１】スケジューリング１００５において、タス
クＴi が、同じタスクＴi に属する２個以上のサブタス
クが競合するかどうか、すなわち同時にスケジューリン
グされるかどうか、によって分類される。タスクＴi の
分類は、次の条件を用いて行う。すなわち、タスクＴi
に属する各１個のサブタスクｒ及びサブタスクｓについ
て、（（ｒ−１）・Ｆ）ｍｏｄ Ｐi ＝ （（ｓ−１）・
Ｆ）ｍｏｄ Ｐi、の式を満足するかどうかの条件であ
る。ここに、１≦ｒ≦ｗi、 １≦ｓ≦ｗi、 及びｒ≠
ｓ、である。
【０２０２】もしこの式が満足される場合、サブタスク
ｒ及びｓは同時にスケジューリングされることになるの
でスケジューリングの競合が生じ、したがってタスクＴ
i は単一のプロセッサ上でスケジューリングできない。
単一のプロセッサ上でスケジューリングできないタスク
は、サブグループＧ１に分類される。
【０２０３】タスクＴi が単一のプロセッサ上でスケジ
ューリング可能であるためには、タスクＴi 内のサブタ
スクｒ及びｓのいかなる組み合わせも上記の条件式を満
足させてはならない。単一のプロセッサ上でスケジュー
リングできるタスクは、サブグループＧ２に分類され
る。
【０２０４】ステップ１０１０〜１０３０において、
「手順２」がタスクＴi ∈Ｇ１について必要なプロセッ
サの個数を定める。ステップ１０１０において、ｐ’の
値、すなわちすべてのタスクＴi ∈Ｇ１をスケジューリ
ングするのに要するプロセッサの個数が、初期値ゼロに
設定される。ステップ１０１５において、各タスクＴi
∈Ｇ１をスケジューリングするのに要するプロセッサの
個数ｐi を計算するループ１０１５が開始される。
【０２０５】ステップ１０２０において、ループ１０１
５内の現タスクＴi についての値ｐi が計算される。具
体的には、値ｐi は、タスクＴi 内の各サブタスク全て
について式（（ｒ−１）・Ｆ）ｍｏｄ Ｐiを用いて最も
頻繁に得られる値に依る。或る１個のタスクＴi ∈Ｇ１
について上記の式で最も頻繁に得られる値の頻度数が、
そのタスクＴi ∈Ｇ１をスケジューリングするのに要す
るプロセッサの個数である。
【０２０６】ステップ１０２５及び１０２６において、
現値ｐi がｐ’に加算され、現タスクＴi についての開
始時間がゼロに設定される。上記の式（（ｒ−１）・
Ｆ）ｍｏｄ Ｐiを「例２」に適用すると、３個のサブタ
スク、すなわちｒ＝１、２及び３についてそれぞれ０、
２及び０の値が定められる。タスクＴ2 については値ゼ
ロが最も頻繁に得られたので、タスクＴ2 について必要
なプロセッサの個数は、値ゼロの頻度数、すなわち２に
等しい。
【０２０７】ステップ１０２５において、各タスクＴi
∈Ｇ１全てについて値ｐi がｐ’に累進的に加算され、
ステップ１０２６において、タスクＴi ∈Ｇ１について
の開始時間ＳＴi がゼロに設定される。
【０２０８】ループ１０１５が完了するか又はもしタス
クＴi がない場合、図２１に示すように「手順２」はス
テップ１０４０に進み、ここで、タスクＴi ∈Ｇ２をス
ケジューリングするために利用可能なプロセッサの個
数、すなわち値ｐ”＝ｐ−ｐ’が定められる。
【０２０９】ステップ１０４５において、もし値ｐ”が
ゼロより小さい場合、タスクＴi ∈Ｇ２をスケジューリ
ングするのに十分な個数のプロセッサがないことになる
ので、「手順２」はステップ１０４６に進み、ここで
「スケジューリング不可能」のメッセージを返し、ステ
ップ１０８０で終結する。もし値ｐ”がゼロより小さく
ないい場合には、「手順２」はステップ１０５０に進
み、ここで、スケジューリングすべきタスクＴi ∈Ｇ２
があるかどうかが点検される。
【０２１０】もしタスクＴi ∈Ｇ２がない場合、「手順
２」はステップ１０５１に進み、ここで、ステップ１０
８０に進むよう命令され、そこで終結する。もしタスク
Ｔi∈Ｇ２がある場合には、「手順２」はステップ１０
５５に進み、ここで、タスクＴi ∈Ｇ２をスケジューリ
ングするために利用可能なプロセッサがあるかどうかが
点検される。
【０２１１】もしｐ”＝０の場合、タスクＴi ∈Ｇ２を
スケジューリングするために利用可能なプロセッサがな
いことになるので、「手順２」はステップ１０５６に進
み、ここで「スケジューリング不可能」のメッセージを
返し、ステップ１０８０で終結する。もしｐ”＝０でな
い場合には、「手順２」はステップ１０６０（図２２）
に進み、ここで、サブグループＧ２をサブセットＧ２−
ｙに分割すべきかどうかを定める。
【０２１２】もし分割を要しない、すなわちｐ”＝１の
場合、「手順２」はステップ１０６１において、サブセ
ットＧ２−１をサブグループＧ２に等しく設定する。そ
うでない場合には、ｐ”＞１であり、「手順２」はステ
ップ１０６５〜１０７０において「分割手順」を呼び出
し、タスクＴi ∈Ｇ２をｐ”個の、素のサブセットＧ２
−ｙ（ｙ＝１,...,ｐ”） に分割させる。
【０２１３】タスクＴi ∈Ｇ２の分割が終わると、「手
順２」はステップ１０７５において、各サブセットＧ２
−ｙについて「タスク・スケジューリング（ＴＳ）手順
２」を呼び出し、ここで第２のスケジューリング手法
が、タスクＴi ∈Ｇ２がｐ”個のプロセッサ上でスケジ
ューリング可能かどうかを定める。
【０２１４】図２３〜図２４に、「タスク・スケジュー
リング手順２」（「ＴＳ手順２」）の例示流れ図を示
す。図２３に示すように、ステップ１１００において
「ＴＳ手順２」が、データをサブグループＧ３に属する
タスクＴh 及び値Ｆとして読み取る。ステップ１１０１
において「ＴＳ手順２」が、スケジューリング可能かど
うかを点検する「スケジューリング点検手順」（又は簡
単に、「Ｓ点検手順」）と称する）を呼び出し、サブグ
ループＧ３内のタスクＴh がスケジューリング可能かど
うかを定めさせる。
【０２１５】ステップ１１０５において「ＴＳ手順２」
は、「スケジューリング不可能」のメッセージ、又は開
始時間のセットが、「Ｓ点検手順」によって返されたか
どうかを点検する。もし開始時間のセットが返された場
合、「ＴＳ手順２」がステップ１１０６において、その
開始時間のセットを呼び出し側プログラムに返す。そう
でない場合には、「ＴＳ手順２」はステップ１１１０
（図２３）〜ステップ１１３５（図２４）に進み、ここ
で「ＴＳ手順２」が、サブグループＧ３を反復分割す
る。
【０２１６】ステップ１１１０において「ＴＳ手順２」
が、値ｇをサブグループＧ３における周期Ｐh の最大公
約数に等しく設定する。ステップ１１１５（図２３）〜
ステップ１１３５（図２４）において「ＴＳ手順２」
が、サブグループＧ３が分割可能でないか、すなわちｇ
＝１かどうかを定める。もしサブグループＧ３が分割可
能、すなわちｇ＞１の場合、「ＴＳ手順２」がサブグル
ープＧ３をサブセットＳv （ｖ＝１,...,ｇ） に反復分
割し、それから各サブセットＳv について自身を呼び出
す。
【０２１７】尚、ステップ１１２０において、タスクＴ
h ∈Ｇ３に対応するデータが｛Ｔh,ｗh,Ｐh,Ｆ｝から
｛￣Ｔh,￣ｗh,￣Ｐh,￣Ｆ｝に変形される。ここに、
｛￣Ｔh,￣ｗh,￣Ｐh,￣Ｆ｝＝｛Ｔh,ｗh,Ｐh/g,Ｆ/
ｇ｝ である。ステップ１１１５〜１１３５は図１３及
び１４に類似である。
【０２１８】ステップ１１４０〜１１４５において「Ｔ
Ｓ手順２」が、後のレベルで呼び出された「ＴＳ手順
２」によってステップ１１３５において返されたデータ
を点検する。もし後のレベルで呼び出された「ＴＳ手順
２」によって返されたデータが「スケジューリング不可
能のメッセージ」である場合、現に呼び出されている
「ＴＳ手順２」がステップ１１４１において、「スケジ
ューリング不可能のメッセージ」を呼び出し側プログラ
ムに返す。
【０２１９】もし「スケジューリング不可能のメッセー
ジ」でない場合には、現に呼び出されている「ＴＳ手順
２」が、後のレベルで呼び出された「ＴＳ手順２」によ
って各サブセット内のタスクについての開始時間のセッ
トが返されたものとする。これによって、現に呼び出さ
れている「ＴＳ手順２」が、ステップ１１４５におい
て、後のレベルで呼び出された「ＴＳ手順２」によって
返された開始時間のセットを合体して、タスクＴh ∈Ｇ
３についての開始時間を得る。
【０２２０】開始時間のセットの合体には次の式：ＳＴ
h＝（￣(ＳＴh)・ｇ）＋（ｖ−１） を用いる。ここに、￣(ＳＴh) はタスク￣Ｔh ∈Ｓv に
ついての開始時間、そして１≦ｖ≦ｇである。Ｔh につ
いての合体された開始時間は、次に呼び出し側プログラ
ムに返される。
【０２２１】図２５〜図２７に、「スケジューリング
（Ｓ）点検手順」の例示流れ図を示す。この手順は、タ
イムスロットのアレイを形成して、サブタスクをこれら
のタイムスロットに、競合が生じないように割り当てる
ことによって、スケジューリング可能かどうかを定め
る。図２５に示すように、ステップ１２００において
「Ｓ点検手順」が、データをサブグループＧ４に属する
タスクＴh 及び値Ｆとして読み取る。
【０２２２】ステップ１２０１において「Ｓ点検手順」
が、０〜ｇ−１の番号を付したｇ個のタイムスロットを
有するアレイを形成する。値ｇはサブグループＧ４の周
期の最大公約数に等しい。ステップ１２０５において、
各タイムスロットに「空き」とマークする。これは、こ
れらのタイムスロットにサブタスクが割り当てられてい
ないことを意味する。
【０２２３】ステップ１２１０〜１２５０において「Ｓ
点検手順」が、次の２つの条件が成立するように各タス
ク及びそのサブタスクをタイムスロットアレイに割り当
てることを試みる。これら２つの条件は、（１）もし或
るタスクの或るサブタスクがタイムスロットｊに割り当
てられた場合、そのタスクの次のサブタスク（もしある
場合）がタイムスロット（ｊ＋Ｆ）ｍｏｄ ｇ ；及び
（２）異なるタスクに属する２個のサブタスクが同じタ
イムスロットに割り当てられることがない、という条件
である。
【０２２４】上記２つの条件を満足させるようなサブタ
スクのタイムスロットへの割り当ては、有効な割り当て
である。
【０２２５】ステップ１２１０において、タスクＴh ∈
Ｇ４がサブタスクの個数ｗh の降順に並べられる。ステ
ップ１２１５において各タスクＴh ∈Ｇ４についてルー
プ１２１５が開始される。具体的には、ループ１２１５
が各タスクＴh ∈Ｇ２−ｙについてのサブタスクｒを個
々に並べ順に、ステップ１２０１で形成されたアレイの
タイムスロットｊに割り当てる（ｊ＝０,...,ｇ−
１）。
【０２２６】ステップ１２２０において、タイムスロッ
ト０がサブタスクｒを割り当てられる最初のタイムスロ
ットになるように、値ｊをゼロに設定することによっ
て、ループ１２１５が開始される。
【０２２７】ステップ１２２５においてループ１２２５
が各タイムスロットｊ＜ｇの全てに対して開始される。
具体的には、ループ１２２５が、ループ１２１５の現タ
スクＴh に属する各サブタスクｒの全てについて、タイ
ムスロット（ｊ＋ｋ・Ｆ）ｍｏｄ ｇ がサブタスクｒを
割り当てる空きがあるかどうかを累進的に点検する（ｋ
＝ｒ−１、すなわちｋ＝０,...,ｗh−１）。
【０２２８】図２６に示すように、ステップ１２３０に
おいて、並べ順に第１のタスクＴh、すなわち最大個数
のサブタスクを有するタスク、の第１のサブタスクｒが
第１のタイムスロット０に割り当てられるように、値ｋ
をゼロに設定することによって、ループ１２２５が開始
される。
【０２２９】ステップ１２３５及び１２４０においてル
ープ１２３５が、各サブタスクｒの全て（第１のサブタ
スクを除く）すなわちｋ＜ｗh−１ について開始され、
現タスクＴh に属するサブタスクｒが、ループ１２２５
におけるｊの現値についてのタイムスロット（ｊ＋ｋ・
Ｆ）ｍｏｄ ｇ に対して割り当て可能かどうかが定めら
れる。
【０２３０】もし「Ｓ点検手順」が、ステップ１２４０
において、ループ１２３５における現サブタスクｒがｊ
の現値についてのタイムスロット（ｊ＋ｋ・Ｆ）ｍｏｄ
ｇへの割り当てに成功すると定めた場合、「Ｓ点検手
順」は次のサブタスクｒについて同じｊの値でループ１
２３５を再び実行する。
【０２３１】他方もし「Ｓ点検手順」が、ループ１２３
５の現サブタスクｒのタイムスロット（ｊ＋ｋ・Ｆ）ｍ
ｏｄ ｇ への割り当てができないと定めた場合には、
「Ｓ点検手順」はループ１２３５を出てステップ１２４
５に進み、ここで、ｊの現値がｊ＋１に更新される。次
にステップ１２５０において、もし「Ｓ点検手順」が、
更新されたｊの現値、すなわちｊ＋１が値ｇに等しいと
定めた場合、ループ１２２５は終結し、ステップ１２５
５において「スケジューリング不可能」のメッセージが
呼び出し側プログラムに返される。
【０２３２】もし更新されたｊの現値、すなわちｊ＋１
が値ｇに等しくない場合には、「Ｓ点検手順」はステッ
プ１２５０からステップ１２２５に戻り、ここで、更新
されたｊの現値についてのタイムスロット（ｊ＋ｋ・
Ｆ）ｍｏｄ ｇ が、ループ１２１５の現タスクＴh に属
するサブタスクｒを割り当てる空きがあるかどうかを定
める。
【０２３３】もしループ１２１５の現タスクＴh のサブ
タスクｒについてループ１２３５が成功裡に完了した場
合、「Ｓ点検手順」は、対応するタイムスロット（ｊ＋
ｋ・Ｆ）ｍｏｄ ｇ がｊの現値について空きがあると定
めたことになる。これにより、「Ｓ点検手順」は、ステ
ップ１２３５からステップ１２６０に進み、ここで、現
タスクＴh のサブタスクｒがタイムスロット（ｊ＋ｋ・
Ｆ）ｍｏｄ ｇ に割り当てられる。
【０２３４】次に「Ｓ点検手順」はステップ１２６５に
おいて、サブグループＧ４内の次のタスクＴh について
ループ１２１５を再び実行するよう命令される。「スケ
ジューリング不可能」のメッセージを返すことなく各タ
スクＴh ∈Ｇ４の全てについてループ１２１５を完了
後、「Ｓ点検手順」はステップ１２７０に進み、ここ
で、各タスクＴh ∈Ｇ４の最初のサブタスクについての
開始時間を「ＴＳ手順２」に返す。
【０２３５】以上の説明は、本発明の実施例による例示
を目的とし、本発明をビデオ・サービスにおけるノン・
プリエンプティブなタスクの周期的スケジューリングに
関する特定の実施例について記述したものであるが、こ
れによって本発明の適用がビデオ・サービスに限定され
るものではなく、あくまで本発明の一般原理を述べるた
めに適用分野の一例として例示したに過ぎない。この技
術分野の当業者であれば、本発明の種々の変形例あるい
は他分野への適用を考え得るが、それらはいずれも本発
明の技術的範囲に包含される。
【０２３６】
【発明の効果】以上述べたごとく、本発明によれば、新
方式のストライピング処理を用いるので、強化ペイ・パ
ー・ビュー方式を用いるビデオ・サーバ上でビデオのス
ケジューリング行う際に、新たなビデオ・ストリームを
開始させる正確なスケジュールを、従来技術と異なり、
非常に容易に設定できる。又、同時に伝送されるように
スケジューリングされたビデオ・ストリームの個数が、
そのビデオ・サーバによるサポートが可能な同時伝送ビ
デオ・ストリームの最大数を超えないように、スケジュ
ーリングすることが可能である。
【０２３７】このように、従来は処理が複雑であった強
化ペイ・パー・ビュー方式におけるビデオのスケジュー
リングを効率よく容易に行うことが可能となる。
【図面の簡単な説明】
【図１】本発明に基づく、ビデオ・オン・デマンド・サ
ービスを提供するためのビデオ・サーバを示すブロック
図である。
【図２】ディスク・ストライピングの例示説明図である
【図３】ビデオＶi を格納し、取り出すための「きめを
細かくした（ＦＧ）」ディスク・ストライピング手法の
例示説明図である
【図４】ビデオＶi を格納し、取り出すための第１の
「きめを粗くした（ＣＧ）」ディスク・ストライピング
手法の例示説明図である
【図５】ビデオＶi を格納し、取り出すための第２の
「きめを粗くした（ＣＧ）」ディスク・ストライピング
手法の例示説明図である
【図６】ビデオ・サーバにおいて計算時間Ｃi 及び周期
Ｐi を有するタスクをスケジューリングするための手順
の例示流れ図である（図６〜図１０で構成）。
【図７】ビデオ・サーバにおいて計算時間Ｃi 及び周期
Ｐi を有するタスクをスケジューリングするための手順
の例示流れ図である（図６〜図１０で構成）。
【図８】ビデオ・サーバにおいて計算時間Ｃi 及び周期
Ｐi を有するタスクをスケジューリングするための手順
の例示流れ図である（図６〜図１０で構成）。
【図９】ビデオ・サーバにおいて計算時間Ｃi 及び周期
Ｐi を有するタスクをスケジューリングするための手順
の例示流れ図である（図６〜図１０で構成）。
【図１０】ビデオ・サーバにおいて計算時間Ｃi 及び周
期Ｐi を有するタスクをスケジューリングするための手
順の例示流れ図である（図６〜図１０で構成）。
【図１１】「定理１」の有効性を証明する例示説明図で
ある。
【図１２】周期よりも長い計算時間を有する図６〜図１
０におけるタスクグループをスケジューリングするため
の手順の例示流れ図である（図１２〜図１５で構成）。
【図１３】周期よりも長い計算時間を有する図６〜図１
０におけるタスクグループをスケジューリングするため
の手順の例示流れ図である（図１２〜図１５で構成）。
【図１４】周期よりも長い計算時間を有する図６〜図１
０におけるタスクグループをスケジューリングするため
の手順の例示流れ図である（図１２〜図１５で構成）。
【図１５】周期よりも長い計算時間を有する図６〜図１
０におけるタスクグループをスケジューリングするため
の手順の例示流れ図である（図１２〜図１５で構成）。
【図１６】タスクグループを分割するための手順の例示
流れ図である（図１６〜図１９で構成）。
【図１７】タスクグループを分割するための手順の例示
流れ図である（図１６〜図１９で構成）。
【図１８】タスクグループを分割するための手順の例示
流れ図である（図１６〜図１９で構成）。
【図１９】タスクグループを分割するための手順の例示
流れ図である（図１６〜図１９で構成）。
【図２０】各々が単位計算時間と周期Ｐh と時間間隔Ｆ
とを有するサブタスク、からなるタスクをスケジューリ
ングするための手順の例示流れ図である（図２０〜図２
２で構成）。
【図２１】各々が単位計算時間と周期Ｐh と時間間隔Ｆ
とを有するサブタスク、からなるタスクをスケジューリ
ングするための手順の例示流れ図である（図２０〜図２
２で構成）。
【図２２】各々が単位計算時間と周期Ｐh と時間間隔Ｆ
とを有するサブタスク、からなるタスクをスケジューリ
ングするための手順の例示流れ図である（図２０〜図２
２で構成）。
【図２３】１個未満のプロセッサ上でスケジューリング
可能な図２０〜図２２におけるタスクグループをスケジ
ューリングするための手順の例示流れ図である（図２３
〜図２４で構成）。
【図２４】１個未満のプロセッサ上でスケジューリング
可能な図２０〜図２２におけるタスクグループをスケジ
ューリングするための手順の例示流れ図である（図２３
〜図２４で構成）。
【図２５】一連のタイムスロットを用いて、図２０〜図
２２におけるタスクをスケジューリングするための手順
の例示流れ図である（図２５〜図２７で構成）。
【図２６】一連のタイムスロットを用いて、図２０〜図
２２におけるタスクをスケジューリングするための手順
の例示流れ図である（図２５〜図２７で構成）。
【図２７】一連のタイムスロットを用いて、図２０〜図
２２におけるタスクをスケジューリングするための手順
の例示流れ図である（図２５〜図２７で構成）。
【符号の説明】
１０ ビデオ・サーバ １１−１〜１１−ｐ プロセッサ １２ ＲＡＭバッファ・メモリ １３ データ格納ユニット １３−１〜１３−ｍ ディスク １４ ネットワーク １５ 受信者（顧客） １６ ビデオ ２２−１〜２２−ｚ、３２−１〜３２−ｗ・ｍ、４２−
１〜４２−ｗ・ｍ、５２−１〜５２−ｗ・ｍ、 ストラ
イプ・ユニット ３０−１〜３０−ｍ、４０−１〜４０−ｍ、５０−１〜
５０−ｍ ディスク ７０ スケジュール
───────────────────────────────────────────────────── フロントページの続き (71)出願人 596077259 600 Ｍｏｕｎｔａｉｎ Ａｖｅｎｕｅ, Ｍｕｒｒａｙ Ｈｉｌｌ， Ｎｅｗ Ｊｅ ｒｓｅｙ 07974−0636Ｕ．Ｓ．Ａ. (72)発明者 ラジーフ ラストギー アメリカ合衆国，07974 ニュージャージ ー，ニュー プロヴィデンス，リヴィング ストン アヴェニュー 229 (72)発明者 アブラハム シルバースチャッツ アメリカ合衆国，07901 ニュージャージ ー，ユニオン，ニュー イングランド ア ヴェニュー 67エー

Claims (29)

    【特許請求の範囲】
  1. 【請求項１】 第１のプロセッサ・サブグループを有す
    るサーバ装置上で、ノン・プリエンプティブなタスクグ
    ループを周期的にスケジューリングするための、タスク
    スケジューリング方法であって、該タスクが、予め定め
    られた周期Ｐで始まり、且つ時間間隔Ｆによって隔てら
    れたｗ個のサブタスクを有し、該ノン・プリエンプティ
    ブなタスクグループが、単一のプロセッサ上で個別にス
    ケジューリングすることが可能な第１のクラスのタスク
    からなる、ようなタスクグループスケジューリング方法
    において、該方法が、 前記第１のクラスのタスクを１個以上のタスク素セット
    に分割するステップと、 もし異なるタスクに属する２個以上のサブタスクが同じ
    タイムスロットに割り当てられない場合に前記第１のク
    ラスのタスクはスケジューリングすることが可能である
    と定義したときに、前記タスクについての周期Ｐの最大
    公約数を用いて前記第１のクラスのタスクをスケジュー
    リングすることが可能であるかどうかを判断するステッ
    プと、からなることを特徴とする、タスクグループスケ
    ジューリング方法。
  2. 【請求項２】 前記第１のクラスのタスクをスケジュー
    リングすることが可能であるかどうかを判断する前記ス
    テップが、 ｇが或るタスク素セット内のタスクについての周期Ｐの
    最大公約数を表すと定義したときに、ｇ個のタイムスロ
    ットからなるタイムスロット部分内で該タスク素セット
    をスケジューリングすることが可能であるかどうかを判
    断するステップからなることを特徴とする請求項１の方
    法。
  3. 【請求項３】 前記タスク素セットをスケジューリング
    することが可能であるかどうかを判断する前記ステップ
    が、 もし或るタイムスロットがサブタスクを割り当てられて
    いない場合に該タイムスロットは空きであると定義した
    ときに、ｇ個のタイムスロットからなる前記タイムスロ
    ット部分内のタイムスロットが空きでサブタスクを割り
    当てることが可能であるかどうかを判断するステップか
    らなる、ことを特徴とする請求項２の方法。
  4. 【請求項４】 前記タスク素セットをスケジューリング
    することが可能であるかどうかを判断する前記ステップ
    が、 ｒ＝１，．．．，ｗ、 ｋ＝ｒ−１、ｊ’が０とｇ−１
    との間の予め定められた値、であると定義したときに、
    ｇ個のタイムスロットからなる前記タイムスロット部分
    内の空きタイムスロット（ｊ’＋Ｆ・ｋ）ｍｏｄ ｇ
    に、或るタスク素セット内の第１のタスクのサブタスク
    ｒを割り当てるステップからなる、ことを特徴とする請
    求項２の方法。
  5. 【請求項５】 前記第１のタスクが、最大個数のサブタ
    スクｒを有する前記タスク素セット内のタスクであるこ
    とを特徴とする請求項４の方法。
  6. 【請求項６】 前記タスク素セットをスケジューリング
    することが可能であるかどうかを判断する前記ステップ
    が、 ｊが、前記予め定められた値ｊ’を除く０とｇ−１との
    間の値、であると定義したときに、前記タスク素セット
    内の別のタスクのサブタスクｒを割り当てられていない
    タイムスロット（ｊ＋Ｆ・ｋ）ｍｏｄ ｇ が、空きで該
    サブタスクｒを割り当てることが可能であるかどうかを
    判断するステップからなる、ことを特徴とする請求項４
    の方法。
  7. 【請求項７】 前記タスク素セットをスケジューリング
    することが可能であるかどうかを判断する前記ステップ
    が、 もし前記タイムスロット（ｊ＋Ｆ・ｋ）ｍｏｄ ｇ が空
    きである場合に、前記タイムスロット（ｊ＋Ｆ・ｋ）ｍ
    ｏｄ ｇ に、前記タスク素セット内の前記別のタスクの
    前記サブタスクｒを割り当てるステップからなる、こと
    を特徴とする請求項６の方法。
  8. 【請求項８】 前記タスク素セットをスケジューリング
    することが可能であるかどうかを判断する前記ステップ
    が、 前記タイムスロット（ｊ＋Ｆ・ｋ）ｍｏｄ ｇ が空きで
    あるかどうかを判断する前記ステップと、前記別のタス
    クの前記サブタスクｒを割り当てる前記ステップとを、
    割り当てられていないサブタスクｒが残らなくなるまで
    反復するステップからなることを特徴とする請求項７の
    方法。
  9. 【請求項９】 前記タスク素セットをスケジューリング
    することが可能であるかどうかを判断する前記ステップ
    が、 前記タスク素セット内の前記タスクを分類してｗ個のサ
    ブタスクｒによる分類順序を形成するステップからなる
    ことを特徴とする請求項７の方法。
  10. 【請求項１０】 前記タスク素セット内の前記タスクの
    前記サブタスクｒが、前記分類順序によって前記タイム
    スロット（ｊ＋Ｆ・ｋ）ｍｏｄ ｇ に割り当てられるこ
    とを特徴とする請求項９の方法。
  11. 【請求項１１】 前記方法が更に、 前記サブタスクｒが、割り当てられた前記タイムスロッ
    トを用いて前記サブタスクｒをスケジューリングするス
    テップからなることを特徴とする請求項７の方法。
  12. 【請求項１２】 前記方法が更に、 前記サブタスクのスケジュールを合体させて前記第１の
    クラスのタスク内の前記タスクについてのスケジュール
    を得るステップからなることを特徴とする請求項１１の
    方法。
  13. 【請求項１３】 前記タスク素セットをスケジューリン
    グすることが可能であるかどうかを判断する前記ステッ
    プが、 もしｇが１よりも大きく且つ前記タイムスロット（ｊ＋
    Ｆ・ｋ）ｍｏｄ ｇ が空きでない場合に、周期Ｐと時間
    間隔Ｆによって隔てられたサブタスクとを有する前記タ
    スク素セットを、周期Ｐ／ｇと時間間隔Ｆ／ｇによって
    隔てられたサブタスクとを有するｇ個のタスク素サブセ
    ットに分割するステップからなることを特徴とする請求
    項６の方法。
  14. 【請求項１４】 前記方法が更に、 もし或るタスクに属する２個以上のサブタスクが同じタ
    イムスロットに割り当てられない場合にそのタスクは単
    一のプロセッサ上でスケジューリングすることが可能で
    あると定義したときに、或るタスクを単一のプロセッサ
    上でスケジューリングすることが可能であるかどうかを
    判断するステップからなることを特徴とする請求項１の
    方法。
  15. 【請求項１５】 もし或るタスクに属する２個以上のサ
    ブタスクが同じタイムスロットに割り当てられる場合に
    そのタスクは単一のプロセッサ上でスケジューリングす
    ることが可能でないと定義したときに、前記ノン・プリ
    エンプティブなタスクグループが、単一のプロセッサ上
    でスケジューリングすることが可能でない第２のクラス
    のタスクからなることを特徴とする請求項１の方法。
  16. 【請求項１６】 前記方法が更に、 サブタスクｒの各々について数式（（ｒ−１）・Ｆ）ｍ
    ｏｄ Ｐ によって最も頻繁に得られる値を用いて前記第
    ２のクラスのタスクによって要求されるプロセッサの個
    数を計算するステップからなることを特徴とする請求項
    １５の方法。
  17. 【請求項１７】 前記方法が更に、 前記第２のクラスのタスク内の各タスクについて、予め
    定められた開始時刻をスケジューリングするステップか
    らなることを特徴とする請求項１５の方法。
  18. 【請求項１８】 前記タスクが、計算時間を有し、 前記第１のクラスのタスクを分割する前記ステップが、 前記タスク素セット内の前記周期の最大公約数からその
    タスク素セット内の前記計算時間の和を差し引くことに
    よって余裕値が定められると定義されるとき、前記タス
    ク素セットについての余裕値が最大になるように前記タ
    スクを前記タスク素セットに割り当てるステップからな
    ることを特徴とする請求項１の方法。
  19. 【請求項１９】 前記タスクが、計算時間を有し、 前記第１のクラスのタスクを分割する前記ステップが、 第１のタスクが、もし第１の空きタスク素セットに割り
    当てられた場合に前記第１のクラスのタスク内の他のタ
    スクについての余裕値より小さいか等しい余裕値を与え
    るような、前記第１のクラスのタスク内のタスクである
    と定義され、該余裕値が、前記タスク素セット内の前記
    周期の最大公約数からそのタスク素セット内の前記計算
    時間の和を差し引くことによって定められると定義され
    るときに、該第１のタスクを、該第１の空きタスク素セ
    ットに割り当てるステップと、 前記第１のクラスのタスク内の割り当てられていないタ
    スクが、もし空きでないタスク素セットに割り当てられ
    た場合に前記第１のクラスのタスク内の割り当てられて
    いないタスクについての余裕値より小さいか等しい余裕
    値を与えるように、該割り当てられていないタスクを、
    空きタスク素セットに割り当てるステップと、 前記割り当てられていないタスクを割り当てるステップ
    を、空きタスク素セットが残らなくなるまで反復するス
    テップと、 前記第１のクラスのタスク内の割り当てられていない又
    は指定されていないタスクが指定された、空きでないタ
    スク素セットが、もし該割り当てられていない又は指定
    されていないタスクが他の空きでないタスク素セットに
    指定された場合に最大の余裕値を与えるタスク素セット
    であるように、該割り当てられていない又は指定されて
    いないタスクを該空きでないタスク素セットに指定する
    ステップと、 割り当てられていない又は指定されていないタスクを指
    定する前記ステップを、前記第１のクラスのタスク内の
    全てのタスクが割り当てられ又は指定されてしまうまで
    反復するステップと、からなることを特徴とする請求項
    １の方法。
  20. 【請求項２０】 前記第１のプロセッサ・サブグループ
    がｐ”個のプロセッサを有し、もしｐ”が１より大きい
    場合に前記第１のクラスのタスクがｐ”以下の個数のタ
    スク素セットに分割される、ことを特徴とする請求項１
    の方法。
  21. 【請求項２１】 前記サーバ装置が、映像に対応するタ
    スクを実行するためのビデオ・サーバであることを特徴
    とする請求項１の方法。
  22. 【請求項２２】 タスクを周期的にプログラミングする
    ためのサーバ装置であって、該サーバ装置が第１のプロ
    セッサ・サブグループからなり、該タスクが周期Ｐiで
    始まり、且つ時間間隔Ｆによって隔てられたｗ個のサブ
    タスクを有するような、タスクプログラミング用サーバ
    装置において、該装置が、 単一のプロセッサ上で個別にスケジューリングすること
    が可能なタスクからなる第１のクラスのタスクを１個以
    上のタスク素セットに分割するための手段と、 異なるタスクに属する２個以上のサブタスクが同じタイ
    ムスロットに割り当てられるかどうかを、前記タスクに
    ついての周期Ｐの最大公約数を用いて確認することによ
    って、前記第１のクラスのタスクをスケジューリングす
    ることが可能であるかどうかを判断するための手段と、
    からなることを特徴とする、タスクプログラミング用サ
    ーバ装置。
  23. 【請求項２３】 前記第１のクラスのタスクをスケジュ
    ーリングすることが可能であるかどうかを判断するため
    の前記手段が、 ｇが或るタスク素セット内のタスクについての周期Ｐの
    最大公約数を表すと定義したときに、ｇ個のタイムスロ
    ットからなるタイムスロット部分内で該タスク素セット
    をスケジューリングすることが可能であるかどうかを判
    断するための手段からなることを特徴とする請求項２２
    の装置。
  24. 【請求項２４】 前記タスク素セットをスケジューリン
    グすることが可能であるかどうかを判断するための前記
    手段が、 ｒ＝１，．．．，ｗ、 ｋ＝ｒ−１、ｊ’が０とｇ−１
    との間の予め定められた値、であると定義したときに、
    ｇ個のタイムスロットからなる前記タイムスロット部分
    内の空きであるタイムスロット（ｊ’＋Ｆ・ｋ）ｍｏｄ
    ｇ に、或るタスク素セット内の第１のタスクのサブタ
    スクｒを割り当てるための手段からなることを特徴とす
    る請求項２３の装置。
  25. 【請求項２５】 前記タスク素セットをスケジューリン
    グすることが可能であるかどうかを判断するための前記
    手段が、 ｊが、前記予め定められた値ｊ’を除く０とｇ−１との
    間の値、であると定義したときに、前記タスク素セット
    内の別のタスクのサブタスクｒを割り当てられていない
    タイムスロット（ｊ＋Ｆ・ｋ）ｍｏｄ ｇ が、空きで該
    サブタスクｒを割り当てることが可能であるかどうかを
    判断するための手段からなることを特徴とする請求項２
    ４の装置。
  26. 【請求項２６】 前記装置が更に、 もし或るタスクに属する２個以上のサブタスクが同じタ
    イムスロットに割り当てられない場合にそのタスクは単
    一のプロセッサ上でスケジューリングすることが可能で
    あると定義したときに、或るタスクを単一のプロセッサ
    上でスケジューリングすることが可能であるかどうかを
    判断するための手段からなることを特徴とする請求項２
    ２の装置。
  27. 【請求項２７】 前記装置が更に、 サブタスクｒの各々について、数式（（ｒ−１）・Ｆ）
    ｍｏｄ Ｐ によって最も頻繁に得られる値を用いて、第
    ２のクラスのタスク内のタスクによって要求されるプロ
    セッサの個数を計算するための手段からなり、該第２の
    クラスのタスクが、単一のプロセッサ上でスケジューリ
    ングすることが可能でないタスクからなることを特徴と
    する請求項２６の装置。
  28. 【請求項２８】 前記第１のクラスのタスクを分割する
    ための前記手段が、 前記タスク素セット内の前記周期の最大公約数からその
    タスク素セット内の前記計算時間の和を差し引くことに
    よって余裕値が定められると定義されるときに、前記タ
    スク素セットについての余裕値が最大になるように前記
    タスクを前記タスク素セットに割り当てるための手段か
    らなることを特徴とする請求項２２の装置。
  29. 【請求項２９】 前記サーバ装置が、映像プログラミン
    グに対応するタスクを実行するためのビデオ・サーバで
    あることを特徴とする請求項２２の装置。
JP9075054A 1996-03-27 1997-03-27 タスクスケジューリング方法及び装置 Pending JPH1091466A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US624011 1996-03-27
US08/624,011 US5964829A (en) 1996-03-27 1996-03-27 Method and apparatus for providing enhanced pay per view in a video server employing a coarse-grained striping scheme

Publications (1)

Publication Number Publication Date
JPH1091466A true JPH1091466A (ja) 1998-04-10

Family

ID=24500254

Family Applications (1)

Application Number Title Priority Date Filing Date
JP9075054A Pending JPH1091466A (ja) 1996-03-27 1997-03-27 タスクスケジューリング方法及び装置

Country Status (4)

Country Link
US (1) US5964829A (ja)
EP (1) EP0798926A2 (ja)
JP (1) JPH1091466A (ja)
CA (1) CA2196471C (ja)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2001101150A (ja) * 1999-09-30 2001-04-13 Toshiba Corp データ処理装置及びデータ処理方法
JP2010516125A (ja) * 2007-01-11 2010-05-13 トムソン ライセンシング コンテンツ通信のためのシステム及び方法
JP2013211897A (ja) * 2007-09-19 2013-10-10 Chinese Univ Of Hong Kong 要求応答並列ビデオサーバにおける負荷分散及び受付予定管理

Families Citing this family (14)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2000505983A (ja) * 1996-12-23 2000-05-16 コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ データ流を供給するための方法および系
US6330609B1 (en) 1997-11-07 2001-12-11 Lucent Technologies, Inc. Admission control system and method for media-on-demand servers
US6615408B1 (en) 1999-01-15 2003-09-02 Grischa Corporation Method, system, and apparatus for providing action selections to an image referencing a product in a video production
US6473804B1 (en) * 1999-01-15 2002-10-29 Grischa Corporation System for indexical triggers in enhanced video productions by redirecting request to newly generated URI based on extracted parameter of first URI
US6742019B1 (en) * 1999-07-23 2004-05-25 International Business Machines Corporation Sieved caching for increasing data rate capacity of a heterogeneous striping group
US7606883B1 (en) 2000-05-11 2009-10-20 Thomson Licensing Method and system for controlling and auditing content/service systems
US8037492B2 (en) * 2000-09-12 2011-10-11 Thomson Licensing Method and system for video enhancement transport alteration
US6823394B2 (en) 2000-12-12 2004-11-23 Washington University Method of resource-efficient and scalable streaming media distribution for asynchronous receivers
US7249357B2 (en) * 2001-08-20 2007-07-24 Silicon Graphics, Inc. Transparent distribution and execution of data in a multiprocessor environment
WO2004090683A2 (en) * 2003-03-31 2004-10-21 Avaya Technology Corp. System and method for efficient scheduling of periodic phenomena
US7643636B2 (en) 2003-09-03 2010-01-05 Motorola, Inc. Managing multiple cryptographic periods in a single cryptographic group
US7594228B2 (en) * 2003-09-23 2009-09-22 Lam Siu H Method and apparatus to perform task scheduling
DE102005010580A1 (de) * 2005-03-04 2006-09-07 Inchron Gmbh Verfahren zur Echtzeitanalyse eines Systems
JP5308127B2 (ja) * 2008-11-17 2013-10-09 株式会社豊田中央研究所 給電システム

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2723653B1 (fr) * 1994-08-11 1996-09-13 Cegelec Procede pour ordonnancer des taches successives qui ne subissent que des contraintes du type delais

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2001101150A (ja) * 1999-09-30 2001-04-13 Toshiba Corp データ処理装置及びデータ処理方法
JP2010516125A (ja) * 2007-01-11 2010-05-13 トムソン ライセンシング コンテンツ通信のためのシステム及び方法
US8732777B2 (en) 2007-01-11 2014-05-20 Thomson Licensing System and method for content communication
JP2013211897A (ja) * 2007-09-19 2013-10-10 Chinese Univ Of Hong Kong 要求応答並列ビデオサーバにおける負荷分散及び受付予定管理
JP2013211896A (ja) * 2007-09-19 2013-10-10 Chinese Univ Of Hong Kong 要求応答並列ビデオサーバにおける負荷分散及び受付予定管理

Also Published As

Publication number Publication date
EP0798926A2 (en) 1997-10-01
CA2196471A1 (en) 1997-09-28
CA2196471C (en) 2001-07-24
US5964829A (en) 1999-10-12

Similar Documents

Publication Publication Date Title
JPH1051757A (ja) ビデオ・サーバにおいて高度なペイパーヴュー方式を提供するための方法および装置
JPH1091466A (ja) タスクスケジューリング方法及び装置
US6134596A (en) Continuous media file server system and method for scheduling network resources to play multiple files having different data transmission rates
Tang et al. On first fit bin packing for online cloud server allocation
CN1957329B (zh) 信号处理装置
Tseng et al. Data broadcasting and seamless channel transition for highly demanded videos
Ren et al. Clairvoyant dynamic bin packing for job scheduling with minimum server usage time
Tsai et al. Two heuristics for scheduling multiple projects with resource constraints
US12026518B2 (en) Dynamic, low-latency, dependency-aware scheduling on SIMD-like devices for processing of recurring and non-recurring executions of time-series data
CN109564528A (zh) 分布式计算中计算资源分配的系统和方法
CN109800092A (zh) 一种共享数据的处理方法、装置及服务器
CN112799820B (zh) 数据处理方法、装置、电子设备、存储介质及程序产品
US5940865A (en) Apparatus and method for accessing plural storage devices in predetermined order by slot allocation
US20100030931A1 (en) Scheduling proportional storage share for storage systems
Breitgand et al. Network aware virtual machine and image placement in a cloud
CN109324886A (zh) 集群资源调度方法和装置
CN119248669A (zh) 一种npu异构平台的内存分配方法及装置
Garofalakis et al. On periodic resource scheduling for continuous-media databases
Ozden et al. Periodic retrieval of videos from disk arrays
Shahabi et al. Continuous display of presentations sharing clips
CN115934247A (zh) 容器集合的分配方法及装置、非易失性存储介质
CN115204406A (zh) 一种量子计算模拟方法、量子电路模拟器及相关设备
Chang et al. 2D BubbleUp: Managing Parallel Disks for Media Servers.
CN118656209B (zh) 一种微服务负载均衡方法、装置、计算机设备及存储介质
CN119789226B (zh) 支持周期性与非周期性机器用户共存的无线资源分配方法、装置及系统