JPH09106327A - データ転送スケジューリング方法 - Google Patents

Abstract

(57)【要約】 【解決手段】 トラックNo.3、No.2、No.1、No.4の順に
アクセス要求があった場合に、ハードディスク２に記憶
されたデータを読み出すヘッド１のシーク方向の順にこ
のアクセス要求を並べる。次に、何らかの原因でプライ
オリティが高いアクセス要求をその先頭に移動させて順
番を替える。その後、データ読み出しと転送を実行す
る。 【効果】 シーク方向を考慮したアクセス順の最適化を
行うとともに、所定のプライオリティを考慮した順序の
入れ替えをすることにより、リアルタイム性を要求され
るデータの転送レートを基準のレベルに維持する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、記憶媒体に格納さ
れた動画データ等をネットワーク経由で複数のユーザー
に対しリアルタイムに転送する場合のデータ転送スケジ
ューリング方法に関する。

【０００２】

【従来の技術】例えば、ビデオオンデマンドシステムで
は、ハードディスクや光ディスク等に格納された動画デ
ータを、複数のユーザーの要求に対応してネットワーク
経由でリアルタイムに転送する。このデータが動画や音
声等によるものの場合、これをユーザー側でスムーズに
再生できるためには、一定の転送レートで転送する必要
がある。もし、一定時間内のデータ転送量が不十分だと
再生画像等が途切れてしまう。また、転送量が多すぎる
と逆にユーザーのデータ受取り処理に負荷がかかって再
生に悪影響を与える。

【０００３】このようなデータ供給を行うビデオサーバ
は、データを記憶する記憶媒体と、ネットワークを経由
してこのデータをユーザーに転送する制御部と、複数の
ユーザーからの要求に対応してデータの転送スケジュー
ルを組み立てるスケジューリング機能部を備えている。
そして、データ転送にあたっては、ＦＩＦＯ方式、即ち
先にデータ転送要求があったデータを最先にアクセスし
順にデータ転送処理を行う方式や、ＳＣＡＮ方式、即ち
データ転送要求を一定期間まとめて記憶媒体に対する複
数のアクセスを効率良く最適化する方式が採用されてい
た。

【０００４】なお、記憶媒体はハードディスク等から構
成され、データの読み出しはヘッドをそのハードディス
ク上で移動させるシーク動作が伴う。従って、このシー
ク方向にデータのアクセス順を設定すると、アクセスの
最適化が可能となる。

【０００５】

【発明が解決しようとする課題】ところで、上記のよう
な従来のデータ転送スケジューリング方法には次のよう
な解決すべき課題があった。先に転送要求があったデー
タを先にアクセスする方法では、各ユーザーに対する転
送レートが均一化される利点があるが、記憶媒体のヘッ
ドはその都度ランダムに移動し、シーク方向を考慮した
場合のアクセス効率が悪くなるという欠点がある。

【０００６】また、ＳＣＡＮ方式は、記憶媒体のシーク
動作を考慮した場合のアクセス処理効率化を図ることが
できるが、その一方でアクセス要求が発生してから実際
のアクセスが行われるまでの時間がまちまちになり、場
合によっては比較的長くなるものも生じ、リアルタイム
処理の維持が容易でないという問題があった。

【０００７】

【課題を解決するための手段】本発明は以上の点を解決
するため次の構成を採用する。 〈構成１〉複数のユーザーからのデータ転送要求を受け
付けて、そのデータを記憶媒体から読み出して、リアル
タイム性を必要とするデータ転送要求を満たすデータ転
送スケジューリングを行う場合において、順に受付られ
たデータ転送要求を保留して、その要求を記憶媒体のヘ
ッドシーク方向に順に並べ、いずれかのプライオリティ
の高いデータ転送要求を前の方の順番に移動して、デー
タ読み出しと転送を実行する。

【０００８】〈説明〉各ユーザーに対するデータの転送
は、適当な量ずつ順に交互に行う。記憶媒体は、データ
読み出しの際にヘッド等の機構を移動させてシークしな
がら読みだす構成のものである。このシーク順に要求を
並べ直してから読み出しをすると、ヘッドの無駄な移動
を無くし、読み出しの最適化ができる。ただし、優先度
の高いものはその列から抜き出して順番を前の方に繰り
上げる。先に順番を繰り上げてから残りを並べ替えても
良い。

【０００９】〈構成２〉複数のユーザーからのデータ転
送要求を受け付けて、そのデータを記憶媒体から読み出
して、リアルタイム性を必要とするデータ転送要求を満
たすデータ転送スケジューリングを行う場合において、
順に受付られたデータ転送要求を保留して、その要求を
記憶媒体のヘッドシーク方向に順に並べ、いずれかのデ
ータ転送要求に対する応答時間が予め定めた閾値以上あ
るときは、その要求を前の方の順番に移動して、データ
読み出しと転送を実行する。

【００１０】〈説明〉応答時間とは、データ転送要求が
あってから実際にデータを読みだして転送をする時刻迄
の時間をいう。この時間が一定以上長いとリアルタイム
性が確保できないから、その要求の順番を繰り上げる。

【００１１】〈構成３〉複数のユーザーからのデータ転
送要求を受け付けて、そのデータを記憶媒体から読み出
して、リアルタイム性を必要とするデータ転送要求を満
たすデータ転送スケジューリングを行う場合において、
順に受付られたデータ転送要求を保留して、その要求を
記憶媒体のヘッドシーク方向に順に並べ、予め、各デー
タ転送要求ごとに、その転送を必要とする時刻をデッド
ライン時刻として登録しておき、いずれかのデータ転送
要求に対する応答時刻が、登録されたデッドライン時刻
以後になると予測されるときは、その要求を前の方の順
番に移動して、データ読み出しと転送を実行する。

【００１２】〈説明〉データ転送要求に対する応答時刻
が登録されたデッドライン時刻以後になると、リアルタ
イム性が確保できないから、その要求の順番を繰り上げ
る。

【００１３】

【発明の実施の形態】以下、本発明の実施の形態を具体
例を用いて説明する。 〈具体例１〉図１は、具体例１の方法の概略説明図であ
る。図の（ａ）は、横軸に時刻を取り、実際のハードデ
ィスクのアクセス要求とこれに対応するアクセス順とを
表したものである。また、（ｂ）は、ハードディスクの
平面図を示し、シーク方向等の説明を行うために設け
た。まず、図の（ｂ）に示すように、ハードディスク２
には動画や音声等、リアルタイム性を要求される各種の
データが格納されているものとする。これが図示しない
ネットワークを通じて複数のユーザーに対し転送され
る。ここで、そのデータ読み出しのために設けられたヘ
ッド１は、矢印Ａの方向に移動してデータの読み出しを
おこなう。この方向をシーク方向と呼んでいる。このシ
ーク方向はヘッド１のスタート位置に応じて内周から外
周に向かう方向、あるいは外周から内周に向かう方向に
その都度設定される。このハードディスク２のトラック
ナンバーを図の左側に示すように、例えば内側からNo.
1，No.2，No.3、No.4と呼ぶことにする。

【００１４】ここで、このようなハードディスク２のア
クセスは、例えばシーク方向が内側から外側に向かう場
合には、そのトラックナンバー順に１，２，３，４と
し、データをこの順にアクセスすることが効率上最適で
ある。従って、例えば図（ａ）に示すようなトラックN
o.3，No.2，No.1，No.4に記入されたデータをアクセス
するようなアクセス要求があった場合でもこれを保留し
ておき、シーク順に並べ替えを行ってアクセスを行う。
即ち、時刻ｔ１〜時刻ｔ４までに受け付けたアクセス要
求を時刻ｔ５〜時刻ｔ８までに実行する場合に、アクセ
ス順をトラックナンバーに合わせて１，２，３，４とい
うように並べ替えている。

【００１５】ところが、これだけでは、例えば時刻ｔ１
にアクセス要求を行ったユーザーに対するアクセスは時
刻ｔ７になり、その応答時間が長くなるという問題があ
る。このとき、例えばこのトラックNo.3のデータのアク
セス要求に対する応答時間が一定時間以内に制限されて
いるような場合、予めこのアクセス要求にプライオリテ
ィを設定する。そして、他のアクセス要求より優先して
アクセスするという設定を行う。例えば時刻ｔ５，ｔ
６，ｔ７，ｔ８の順にトラックNo.3，２，１，４のアク
セス要求があった場合に、まずシーク方向にNo.1，２，
３，４とアクセス要求を並べ替えるとともに、プライオ
リティの高いNo.3のアクセス要求を取り出して先頭へ移
動させる。

【００１６】そして、時刻ｔ９，ｔ１０，ｔ１１，ｔ１
２において、それぞれトラックNo.3，No.1，No.2，No.4
の順にアクセスを実行する。このとき、トラックNo.3の
アクセスはヘッドのシーク方向を無視して行い、その後
のトラックNo.1，No.2，No.4のアクセスはシーク方向順
に最適化を図るといった処置となる。以上により、プラ
イオリティの高いものは優先してアクセスを行い、その
他のものはシーク方向を考慮したアクセスの最適化が行
われる。

【００１７】〈具体例２〉図２は、具体例２の方法の概
略説明図である。具体例１では、例えばオペレータの指
定や適当な指示の入力によって一定のユーザーのデータ
転送要求に対し個別に高いプライオリティを設定するよ
うにした。ところが、各ユーザーに対する転送レートは
ほぼ一定のものが要求され、しかもアクセスの最適化に
よりあるユーザーについて必要な転送レートが維持でき
なくなることがある。これを自動的に修正しプライオリ
ティを上げる操作がこの具体例２による方法である。

【００１８】即ち、まず図２に示すように、アクセス要
求が発生した予定時刻とアクセスの最適化を図った場合
の各要求に対応する実際のアクセスの時刻との差を演算
する。例えば、図のNo.3のアクセス要求は時刻ｔ１に発
生し、時刻ｔ７に受け付けられてアクセスされる。その
間の時間は図に示すように６となる。また、時刻ｔ２に
発生したNo.2のアクセス要求は、時刻ｔ６にアクセスが
実行されることから応答時間は４となる。また、時刻ｔ
３に発生したNo.1のアクセス要求は、同様にして応答時
間が２となる。

【００１９】更に、時刻ｔ４に発生したNo.4のアクセス
要求の応答時間は４となる。このようにして、応答時間
を演算し予測した場合に、例えば平均的な時間として４
あるいは５を閾値に設定しておき、これとそれぞれの応
答時間とを比較する。そして、応答時間がこの閾値より
長いものは図１に示したようなプライオリティを設定し
て、アクセス順の最適化を行った後に、そのプライオリ
ティの高いものを前に移動させる。結果は、図１に示し
た具体例と全く同様になるが、この具体例２では、こう
して応答時間が一定以上長いかどうかによって自動的に
プライオリティを設定する。

【００２０】〈具体例３〉図３は、具体例３の方法の概
略説明図である。この図も、図１や図２を用いて説明し
たものと同様の形式で記載されている。この例では、そ
れぞれのアクセス要求に対しデッドライン時刻を設定す
る。このデッドライン時刻というのは、いつまでにアク
セスを行わなければならないかを指定する時刻のことで
ある。例えば、この図の例では、時刻ｔ５にトラックN
o.3のアクセス要求が行われ、そのデッドライン時刻が
ｔ１０に設定されている。また、時刻ｔ６に発生したト
ラックNo.2のアクセス要求は時刻ｔ１１をデッドライン
時刻としている。

【００２１】時刻ｔ７に発生したトラックNo.1のアクセ
ス要求は時刻ｔ１２をデッドライン時刻とし、時刻ｔ８
に発生したNo.4のアクセス要求は時刻ｔ１３をデッドラ
イン時刻としている。このような要求を受け付けた後、
これまでの例と同様に、まずヘッドのシーク方向を考慮
したアクセス要求の並べ替えが行われる。従って、図に
示すように、No.1，No.2，No.3，No.4の順にアクセス要
求が並べ替えられる。そして、その後、このままではデ
ッドライン時刻を過ぎてアクセスが行われるものがある
かどうかを調べる。

【００２２】この例では、トラックNo.3のアクセス要求
は放置すれば、時刻ｔ１１に実際のアクセスがされ、デ
ッドライン時刻を過ぎてしまう。そこで、このアクセス
要求を先頭に移動させる。この処理によって、デッドラ
イン時刻ｔ１０より前にアクセスが行われる。また、そ
の他のアクセス要求についても、それぞれデッドライン
要求以前にアクセスが実行される。これによって、応答
時間の長くなるものを救済し、かつアクセスの最適化を
行うことができる。

【００２３】〈各具体例の動作フローチャート〉以下、
各具体例を実施した場合の基本的な動作の流れを順にフ
ローチャートを用いて説明する。まず、図４は、具体例
１の動作フローチャートである。ステップＳ１におい
て、時刻がきたかどうかの判断がされる。この時刻とい
うのは、一定の周期でアクセス要求をまとめ、その要求
の並べ替え等を行っているため、その区切りを定める時
刻のことである。この周期毎にステップＳ１の判断が行
われる。時刻がこなければステップＳ２に進み、アクセ
ス要求を待つ。アクセス要求がくればステップＳ３にお
いて、その要求をスタックする。即ち、要求を一旦保留
して記憶する。そして、時刻がきた場合にはステップＳ
１からステップＳ４に移り、並べ替えを開始する。即
ち、まずプライオリティの高いものを先頭に取り出して
おき、ステップＳ５において、その他の要求をディスク
のシーク順、即ち内周から外周に向かう方向あるいは外
周から内周の方向に向かう順に並べ替える。そして、ス
テップＳ６において、並べ替えた順にデータをアクセス
しデータを返す。

【００２４】なお、この例では、まずプライオリティの
高いものを取り出してから並べ替えを行ったが、先に並
べ替えをしてからプライオリティの高いものを取り出す
ようにしても差し支えない。

【００２５】図５は、具体例２の動作フローチャートで
ある。このステップＳ１〜ステップＳ３の処理は図４に
示したものと全く同様である。そして、ステップＳ４で
は、まず順番の並べ替えを行ってヘッドのシーク順に見
た最適化を行う。その後、ステップＳ５において、応答
時間が長時間になるものは順番を変更し、全体として平
均的な時間でアクセスできるように並べ替えを行う。そ
の後、ステップＳ６で並べ替えた順にデータをアクセス
し、データ転送を行う。なお、この例でも予め応答時間
が長いものは先に順番を繰り上げておき、残りのものに
ついてヘッドのシーク方向を考慮した並べ替えを行うよ
うにしてもよい。

【００２６】図６は、具体例３の動作フローチャートで
ある。このフローチャートのステップＳ１〜ステップＳ
３は、具体例１と具体例２の内容と全く同様である。そ
して、ステップＳ４に移り、ここで予め登録されたデッ
ドライン時刻の早い順に要求を並べ替える。そして、ス
テップＳ５において、先頭の要求のディスク位置を例え
ばＡに設定する。ディスク位置というのはディスク上の
ヘッドシーク位置のことをいい、トラックナンバーに相
当する。そして、ステップＳ６でこのデッドライン時刻
までに他の読込みができる余裕があるかどうかを判断す
る。もし、余裕があればステップＳ７において、ディス
ク位置Ａまでに移動するディスク位置で読み込むことの
できる要求があるかどうかを判断する。要求があればそ
のステップＳ８において、その要求を先に読むようにス
ケジュールする。

【００２７】また、ステップＳ６で他の読込みができる
余裕が無い場合やステップＳ７で移動するディスク位置
で読み込む要求が無い場合には、ステップＳ９に移り、
要求がまだ他にあるかどうかを判断する。他にあればス
テップＳ１１で、次に早い要求のディスク位置をＡに設
定する。そして、再びステップＳ６に戻る。このような
手順によって先に図３を用いて説明したようなデッドラ
イン時刻を越えない範囲で、要求並べ替えの最適化が行
われる。こうして並べ替えが終了すると、ステップＳ９
からステップＳ１０に移り、順にデータをアクセスし、
データ転送を実行する。なお、この並べ替え方法は図の
例に限らず、デッドライン時刻を考慮した各種の方法に
して差し支えない。

【図面の簡単な説明】

【図１】具体例１の方法の概略説明図である。

【図２】具体例２の方法の概略説明図である。

【図３】具体例３の方法の概略説明図である。

【図４】具体例１の動作フローチャートである。

【図５】具体例２の動作フローチャートである。

【図６】具体例３の動作フローチャートである。

【符号の説明】

１ ヘッド ２ ハードディスク

Claims (3)

【特許請求の範囲】
1. 【請求項１】 複数のユーザーからのデータ転送要求を
   受け付けて、そのデータを記憶媒体から読み出して、リ
   アルタイム性を必要とするデータ転送要求を満たすデー
   タ転送スケジューリングを行う場合において、 順に受付られたデータ転送要求を保留して、その要求を
   記憶媒体のヘッドシーク方向に順に並べ、 いずれかのプライオリティの高いデータ転送要求を前の
   方の順番に移動して、データ読み出しと転送を実行する
   ことを特徴とするデータ転送スケジューリング方法。
2. 【請求項２】 複数のユーザーからのデータ転送要求を
   受け付けて、そのデータを記憶媒体から読み出して、リ
   アルタイム性を必要とするデータ転送要求を満たすデー
   タ転送スケジューリングを行う場合において、 順に受付られたデータ転送要求を保留して、その要求を
   記憶媒体のヘッドシーク方向に順に並べ、 いずれかのデータ転送要求に対する応答時間が予め定め
   た閾値以上あるときは、その要求を前の方の順番に移動
   して、データ読み出しと転送を実行することを特徴とす
   るデータ転送スケジューリング方法。
3. 【請求項３】 複数のユーザーからのデータ転送要求を
   受け付けて、そのデータを記憶媒体から読み出して、リ
   アルタイム性を必要とするデータ転送要求を満たすデー
   タ転送スケジューリングを行う場合において、 順に受付られたデータ転送要求を保留して、その要求を
   記憶媒体のヘッドシーク方向に順に並べ、 予め、各データ転送要求ごとに、その転送を必要とする
   時刻をデッドライン時刻として登録しておき、 いずれかのデータ転送要求に対する応答時刻が、登録さ
   れたデッドライン時刻以後になると予測されるときは、
   その要求を前の方の順番に移動して、データ読み出しと
   転送を実行することを特徴とするデータ転送スケジュー
   リング方法。