JPH0760415B2 - マルチタスキング・データ処理システム - Google Patents

マルチタスキング・データ処理システム

Info

Publication number
JPH0760415B2
JPH0760415B2 JP3273551A JP27355191A JPH0760415B2 JP H0760415 B2 JPH0760415 B2 JP H0760415B2 JP 3273551 A JP3273551 A JP 3273551A JP 27355191 A JP27355191 A JP 27355191A JP H0760415 B2 JPH0760415 B2 JP H0760415B2
Authority
JP
Japan
Prior art keywords
queue
priority
request
pending
service
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.)
Expired - Lifetime
Application number
JP3273551A
Other languages
English (en)
Other versions
JPH04264947A (ja
Inventor
フェリックス・ミロ
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.)
International Business Machines Corp
Original Assignee
International Business Machines Corp
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 International Business Machines Corp filed Critical International Business Machines Corp
Publication of JPH04264947A publication Critical patent/JPH04264947A/ja
Publication of JPH0760415B2 publication Critical patent/JPH0760415B2/ja
Anticipated expiration legal-status Critical
Expired - Lifetime legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/48—Program initiating; Program switching, e.g. by interrupt
    • G06F9/4806—Task transfer initiation or dispatching
    • G06F9/4843—Task transfer initiation or dispatching by program, e.g. task dispatcher, supervisor, operating system
    • G06F9/4881—Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
    • G06F3/061—Improving I/O performance
    • G06F3/0613—Improving I/O performance in relation to throughput
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0638—Organizing or formatting or addressing of data
    • G06F3/064—Management of blocks
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
    • G06F3/0655—Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices
    • G06F3/0659—Command handling arrangements, e.g. command buffers, queues, command scheduling
    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
    • G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
    • G06F3/0601—Interfaces specially adapted for storage systems
    • G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
    • G06F3/0671—In-line storage system
    • G06F3/0673—Single storage device
    • G06F3/0674—Disk device

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Human Computer Interaction (AREA)
  • Software Systems (AREA)
  • Multi Processors (AREA)
  • Signal Processing For Digital Recording And Reproducing (AREA)

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明は、マルチタスキング・デ
ータ処理システムに関し、具体的にはこのシステムのデ
ィスク記憶装置に関する入出力機能のスケジューリング
に関する。
【０００２】
【従来の技術】本明細書で頻繁に使用する用語を以下で
定義する。各機能に関するより詳しい情報は、刊行物
“ＩＢＭ Ｏｐｅｒａｔｉｎｇ Ｓｙｓｔｅｍ／２（Ｉ
ＢＭ及びＯＳ／２はインターナショナル・ビジネス・マ
シーンズ・コーポレーションの商標）Ｐｒｏｇｒａｍｍ
ｉｎｇ Ｔｏｏｌｓ ａｎｄ Ｉｎｆｏｒｍａｔｉｏ
ｎ，Ｖｅｒｓｉｏｎ １．２ Ｐｒｏｇｒａｍｍｉｎｇ
Ｇｕｉｄｅ”、１９８９年刊に出ている。オペレーテ
ィング・システム／２は、本明細書ではＯＳ／２とも称
する。ＡＰＩ（適用業務プログラム・インターフェー
ス）−オペレーティング・システムと適用業務プログ
ラムの間のプログラミング・インターフェース。デバイ
ス・ドライバ−周辺装置を制御するため、たとえばデ
ィスク記憶装置に対してデータ転送を方向付けるための
動作を実行するプログラム。フォアグラウンド・プログ
ラム−マルチタスキング・システムのユーザが現在対
話中の相手となるプログラム。リンク式リスト待ち行列
−連続するデータ項目の位置がその項目中のポインタ
情報によって示される、順に並べられたデータ項目の待
ち行列。１重リンク式リストでは、項目ポインタは一方
向に連続する項目のみを指すが、２重リンク式リスト待
ち行列では、項目ポインタは両方向に指す。マルチタス
キング（多重タスク処理）−データ処理システム内で
の複数の適用業務または複数の適用業務部分の並行処
理。ＲＢＡ（相対ブロック・アドレス）−ディスク記
憶装置上の記憶位置を定義する値。この値の大きさは、
装置上のトラック及びシリンダの位置と直接関係付ける
ことができる。サービス・カーネル−プログラム・タ
スクによって開始された要求にサービスするため、ＡＰ
Ｉとデバイス・ドライバの間で動作するＯＳ／２のモジ
ュール。サービス待ち行列−装置によって実行される
入出力機能を並べるため、関連するディスク・ドライブ
装置に関して、オペレーティング・システムとディスク
デバイス・ドライバとによって維持される待ち行列。タ
スク要求パケット−入出力サービスなどの必要とされ
る動作を開始するためにプログラム・タスクからオペレ
ーティング・システムのサービス・カーネルに渡される
要求情報の単位。スレッド−タスクまたは処理内の実
行の単位。
【０００３】現在のマルチタスキング・データ処理シス
テム、たとえばオペレーティング・システムＯＳ／２の
バージョン１．０、１．１、１．２のもとで動作するシ
ステムでは、ディスク記憶装置に関する入出力動作は、
この機能が実行されるのを待っているタスクの相対的な
緊急度とは本質的に無関係な順序でスケジューリングさ
れている。
【０００４】たとえば、ＯＳ／２のバージョン１．０、
１．１、１．２では、ディスク装置に関する入出力動作
は、アドレス順に並べられる。すなわち、入出力要求
は、ディスクの読み書きヘッドが現在の移動方向で動作
を続けている間に到達可能な目標記憶位置を有する待機
中の全ての要求にサービスできるように設計された位置
の順序で、関連するサービス待ち行列内に配列される。
この順序に関する規則は、上昇するエレベータは、既に
通過した階からのサービス要求は無視して、選択された
全ての階に到達するまで上昇し続け、下降するエレベー
タは、既に通過した階からの要求は無視して、選択され
た全ての階で止まるという、よく知られているビルのエ
レベータの順序規則に類似している。同様に、従来技術
のＯＳ／２システムでは、ディスク入出力要求は、目標
とするディスク記憶位置を表す関連するＲＢＡ（相対ブ
ロック・アドレス）の昇順及び降順に、交互に待ち行列
に入れられる。
【０００５】このようなシステムでは、特定のディスク
・ドライブを対象とする入出力要求は、そのドライブに
関連する、１重リンク式リスト・サービス待ち行列中に
保持される。次にサービスを受ける要求は、必ず待ち行
列の先頭に位置する要求である。関連するドライブの読
み書きヘッドが、ディスクに対するＲＢＡ位置が増加す
る方向に移動している間、その方向で到達可能な（まだ
ヘッドが通過していない）ＲＢＡ位置を指定する要求
は、待ち行列内に先頭からＲＢＡ位置が増加する順序で
置かれ、読み書きヘッドの方向が逆になった後に始めて
到達可能なＲＢＡ位置を指定する要求は、ＲＢＡ位置が
減少する順序で待ち行列内に配列される。要求を待ち行
列に入れることを担当するオペレーティング・システム
のサービス・カーネルは、同じドライブを指定する別の
要求を受け取ったとき、（サービスを受けるために待ち
行列から最後に除去された２つの要求のＲＢＡから）読
み書きヘッドの現在の位置と移動方向を決定し、受け取
った要求を、その待ち行列の、他の待機中の要求と列を
そろえて「アドレス順」にサービスを受けられる位置に
入れる。
【０００６】したがって、読み書きヘッドが、ＲＢＡデ
ィスク位置が増加する方向に移動しており、サービス待
ち行列の先頭にある要求が、読み書きヘッドの動きを反
転させずに到達可能なディスクの位置を表すＲＢＡを有
する場合、このような到達可能なＲＢＡ位置を有する待
機中の、全ての要求は、待ち行列の先頭から順に、要求
のＲＢＡ値が昇順に並んだブロックに入れられる。読み
書きヘッドの方向を変えずに到達可能な位置を表すＲＢ
Ａを有する、新たに出された要求は全て、そのブロック
中で要求のＲＢＡの昇順が保たれるように、その先頭ブ
ロックに挿入される。ヘッドが既に通過した位置を表す
ＲＢＡを有する新しい要求は、要求のＲＢＡが降順に並
んだ、第２のブロックに入れられる。従って、最初のブ
ロック内の全ての要求がサービスを受けた後に、読み書
きヘッドの方向が反転し、第２のブロック内の要求が続
けてサービスを受ける。
【０００７】このようなアドレス順は、全ての要求がサ
ービスを受けることを有効に保証するけれども、この種
の要求に関連するタスクの優先度は全く考慮されないの
で、効率的なサービスを保証することにはならない。す
なわち、心臓の手術とリアルタイムで関連するディスク
入出力要求が、レクリエーション・ゲームの続行に関連
する要求より優遇されない。その上、どんなシステム中
でもディスク入出力要求の提示速度は、メモリの制約に
反比例して増大し（すなわち、システムのメモリが小さ
いほど、ディスクのアクセスが頻繁になる。）、同時に
処理されるタスクの数に比例して増大する傾向があるの
で、明らかに、メモリ容量が小規模で、効率的に利用さ
れるマルチタスキング・システムでは、システムのユー
ザがシステムの使用に望ましくない制約を設けることが
必要となるほど、ディスク入出力要求にサービスする際
の平均遅延が大きくなるであろう。
【０００８】
【発明が解決しようとする課題】本発明の目的は、マル
チタスキング・データ処理システムのディスク入出力動
作をスケジューリングするための改良された方法及び手
段を提供することにある。これに関連する目的は、優先
順位の高いタスクに関連する要求が、優先順位の低いタ
スクに関連する要求よりも先にサービスを受ける、スケ
ジューリング方式を提供することである。
【０００９】本発明の他の目的は、優先順位の高いタス
クに関連する要求のサービスが、優先順位の低いタスク
に関連する要求よりも優先されるが、優先順位の低いタ
スクが不当に「サービスを渇望する」（過剰な遅延時間
の間サービスを受けられない）ことのない、マルチタス
キング・システムのディスク入出力動作の改良されたス
ケジューリングを提供することである。
【００１０】本発明の他の目的は、フォアグラウンド・
タスクに関連する要求をバックグラウンド・タスクに関
連する要求よりも優先して扱いながら、各タスクの優先
順位に従って、かかるシステムにおける入出力要求のサ
ービスに優先順位を付けることである。
【００１１】本発明の他の目的は、対応する優先順位を
有するタスクに関して、サービスを受けるために待機中
の要求が、要求にサービスする全体的処理能力がスピー
ドアップする特別の順序で待ち行列内で並べられ、サー
ビスを受けるために選択されるように、かかるシステム
におけるディスク入出力要求のサービスに優先順位を付
けることである。
【００１２】本発明の他の目的は、余り大きくないメモ
リ容量と比較的大きなタスク負荷を有するシステムで、
要求がアドレス順にサービスを受けるほぼ同等の構成の
システムに比べて全ての要求に対してより速いサービス
処理能力を提供するように、ディスク入出力要求のサー
ビスに優先順位を付ける方法及び手段を提供することで
ある。
【００１３】
【課題を解決するための手段】本発明の上記及びその他
の目的は、処理システム内の各物理的ディスク・ドライ
ブ（ハード・ドライブ、フロッピー・ドライブなど）に
関する１組の優先順位の順に並べられた要求保留待ち行
列を提供することによって、実現される。所与のドライ
ブを対象とする要求は、その要求が関連するタスクの優
先度クラスに対応するサービス優先順位を有する保留待
ち行列に入れられる。各待ち行列は、２重にリンクされ
たリスト待ち行列であり、各待ち行列に入れられた要求
は、それに関連するＲＢＡ（相対ブロック・アドレス）
値（この値は、入出力動作の目標となる当該のドライブ
上の記憶位置を定義する）がその待ち行列の一端に対し
て昇順に並ぶような位置に置かれる。
【００１４】サービス待ち行列内の最後の要求がディス
ク・ドライブに指名されると、サービスを受ける「準備
のできた」（空ではない）優先順位が最高の保留待ち行
列からサービス待ち行列に要求が移される。優先順位が
最高の「準備のできた」待ち行列が、優先順位が最高の
保留待ち行列（ここでは、ＦＩＦＯ 保留待ち行列と言
う）以外のものであるときは、単一の要求が、準備ので
きた当該の待ち行列の両端のうちの選択された一方から
移される。この選択は、２つの末端要求のＲＢＡとディ
スクの読み書きヘッドの現在位置（この現在位置は、サ
ービス待ち行列から最後に指名された要求のＲＢＡから
推論される）の「近接度」の判定に基づいて行われる。
【００１５】本発明の好ましい実施例では、１０個１組
の保留待ち行列が各物理的ディスク・ドライブに割り当
てられる。各組の１０個の待ち行列のうちの９個は、タ
スクに割り当てられる優先度クラスの９個の異なるグル
ープと関連付けて配列される。残り１つの待ち行列は、
前述の優先順位が最高のＦＩＦＯ保留待ち行列である。
本発明に独自のものと思われる特別の「渇望ブースト」
処理中、ＦＩＦＯ保留待ち行列は、優先順位の低い待ち
行列からだけ要求を受け取る。その処理では、保留待ち
行列内の「最古の」要求が所定の「渇望時間」よりも長
い間待たされていると判定されたとき、その待ち行列内
の全ての要求が、優先順位が次に高い保留待ち行列に、
すなわち優先順位が次に高い空いた保留待ち行列に、あ
るいは優先順位が中間の全ての保留待ち行列が空ではな
い場合はＦＩＦＯ保留待ち行列にブロック転送される。
その保留待ち行列が要求転送前に空でない場合は、転送
された要求は、ＦＩＦＯ待ち行列の末尾にある要求に連
結される。
【００１６】前述の待ち行列は、オペレーティング・シ
ステムのサービス・カーネルによって管理される。ディ
スク・ドライブが入出力動作の準備ができたとき、サー
ビス・カーネルは、その関連するデバイス・ドライバか
ら警告を受け、サービス待ち行列内の次の要求を指名す
る（要求はその待ち行列からＦＩＦＯ（先入れ先出し）
順に指名される）。要求が指名された後、サービス待ち
行列が空であり、保留待ち行列が空でない場合、サービ
ス・カーネルは、優先順位が最高の空でない保留待ち行
列からサービス待ち行列に１つまたは複数の要求を移
す。ＦＩＦＯ保留待ち行列が空でない場合、その待ち行
列内の全ての要求が、サービス待ち行列にブロック転送
される。サービス待ち行列が空になった時にＦＩＦＯ待
ち行列が空であり、かつ優先順位がより低い保留待ち行
列がそのとき空でない場合は、ＦＩＦＯ保留待ち行列に
比べて優先順位が次に高い空でない保留待ち行列からサ
ービス待ち行列に単一の要求が移される。優先順位が次
に高いその待ち行列が複数の要求を含む場合は、その待
ち行列のＲＢＡの先頭と末尾にある要求中で指定された
ＲＢＡが、読み書きヘッドの現位置と比較され、その位
置に最も近いＲＢＡを有する要求が選択される。好まし
い実施例では、比較される要求ＲＢＡは「末端ＲＢＡ」
（その要求中で指定されるＲＢＡを、その要求中で指定
されるファイルの長さだけ増加させた値）であり、選択
される要求は、末端ＲＢＡ値に最も近い値を有する要求
である。
【００１７】ＦＩＦＯ保留待ち行列以外の各保留待ち行
列に入れられた要求は、その待ち行列の一端（後述の実
施例では先頭）から順に要求ＲＢＡの昇順を保つような
位置に並べられる。したがって、ＦＩＦＯ保留待ち行列
内の要求は、優先順位の低い保留待ち行列から移された
１個または複数の要求ブロックから構成され、各ブロッ
ク内の要求はそのＲＢＡの順序（たとえば後述の実施例
では昇順）を保つような位置に置かれる。
【００１８】オペレーティング・システムのサービス・
カーネルに提示される各ディスク入出力要求は、関連す
るタスクの基本優先度クラスに対応する優先順位指示を
有する。サービス・カーネルは、目標のディスク・ドラ
イブに関連する１組の保留待ち行列のうちの選択された
１つの保留待ち行列に各要求を入れる。選択される待ち
行列は、タスクの優先順位指示に対応する、またはそれ
よりも高い優先順位を有するものである（但し、ＦＩＦ
Ｏ保留待ち行列ではない）。フォアグラウンド・タスク
に関連する入出力要求は、対応する、またはより高い優
先順位の保留待ち行列に入れられ、バックグラウンド・
タスクに関連する入出力要求は、対応する優先順位の保
留待ち行列だけに入れられる。したがって、所与の優先
度クラスのタスクについて、フォアグラウンド・タスク
に関連する入出力要求は、バックグラウンド・タスクに
関連する要求よりも有利なサービスを受ける傾向があ
る。
【００１９】各待ち行列内で要求がＲＢＡ順の位置に並
べられる、優先順位を付けた保留待ち行列のこの階層配
置の特徴は、要求が、関連するタスクの優先度クラスに
従って有効にサービスを受けるように優先順位を付けら
れ、末端ＲＢＡのディスクの読み書きヘッドに対する相
対的近接度に基づいてサービスを受けるべく選択可能と
なり、その結果、選択を行う際に任意の待ち行列内で最
も迅速に位置が検出できる２つの要求を検討するだけで
よい。
【００２０】前述の特徴の全てが、従来技術の「アドレ
ス順」を使用するほぼ同等の構成のシステムに比べてタ
スク処理能力を大幅に改善する働きをする。
【００２１】好ましい実施例では、サービス優先順位の
ランクが最高（ＦＩＦＯ）レベルと最低（ＩＤＬＥ）レ
ベルの間にある各組の保留待ち行列は、サブセットとし
て緊急（ＴＣ）待ち行列及び通常（ＲＧ）待ち行列を含
む。緊急待ち行列は、通常待ち行列よりも、デバイス・
ドライバ・サービスに関してより高い優先順位にランク
付けされる。緊急待ち行列及び通常待ち行列はそれぞ
れ、緊急優先度クラス及び通常の非緊急優先度クラスの
タスクに関連する要求を受け取る。ＩＤＬＥ保留待ち行
列に送られる要求は、通常の非緊急優先度クラスよりも
低い非緊急優先度クラスを有するタスクに関連するもの
である。
【００２２】優先順位を付けた保留待ち行列の前述の配
置は、上記の「渇望」操作処理、要求ＲＢＡの配列、及
び上記で特徴付けた先頭と末尾の近接度による選択とあ
いまって、要求にサービスする効率を最適にし、それに
付随して全体的タスク処理能力を最適に改善する。この
配置により、（前述の入出力要求サービスのアドレス順
配列を使用するほぼ同等の構成のシステムに比べて）３
％から５％程度の処理能力の増加が得られる。
【００２３】本発明の上記その他の特徴、目的、態様及
び利点は、下記に詳述する説明及び特許請求の範囲を考
慮することにより十分に理解されよう。
【００２４】
【実施例】１. システム環境 図１を参照すると、本発明を使用すると有利な典型的な
マルチタスキング・データ処理システム環境１は、マイ
クロプロセッサ２、メモリ・サブシステム３（通常は１
個以上のランダム・アクセス・メモリ・バンク及び図示
してない直接記憶アクセス制御装置を含む）、バス４、
及びディスク記憶サブシステム５（通常は、図示してな
い制御装置及び１台以上のディスク・ドライブを含む）
を含んでいる。周知の形の基本入出力システム（ＢＩＯ
Ｓ）「ファームウェア」２ａが、マイクロプロセッサに
付随している。このファームウェアは、サブシステム３
に関連する記憶アドレス・スペースの読取り専用メモリ
（ＲＯＭ）部分に記憶される。当技術分野で周知のよう
に、バス４は、情報信号を交換するために要素１ないし
３及び５を結合する。このシステムで典型的なユーザ入
力装置（キーボード、マウスなど）、及び本発明を理解
するために重要とは考えられないその他のシステム要素
は、図示してない。
【００２５】システムの立上げ時に、サブシステム５の
ディスク記憶スペースの利用、及びサブシステム５と記
憶サブシステム３の間での情報の移動を管理するため、
ＯＳ／２システムの既存のバージョンの一つなどのマル
チタスキング・オペレーティング・システム・プログラ
ム６が、メモリ・サブシステム３にロードされる。オペ
レーティング・システムは、マイクロプロセッサがマル
チタスキングモードで動作できるように、記憶サブシス
テム５とメモリ・サブシステム３の間でプログラム及び
データの動的転送を行う。
【００２６】２. 従来技術のマルチタスキング・オペ
レーティング・システムによるディスク入出力要求の操
作 図２ないし図４は、ＯＳ／２システムの既存のバージョ
ンによるディスク入出力要求の、上記従来技術によるア
ドレス順の配列を示す。これらのＯＳ／２システムで
は、アプリケーション・プログラム及びユーティリティ
が、適用業務プログラム・インタフェース（ＡＰＩ）２
０を介してオペレーティング・システムとインタフェー
スされる。アプリケーション及びユーティリティからの
ディスク入出力要求は、ＡＰＩを通ってオペレーティン
グ・システムのサービス・カーネル２２に送られる。カ
ーネル２２は、各要求を、その要求中で指定されるディ
スク・ドライブに関連するサービス待ち行列２４に入れ
る。サブシステム５の各物理的ディスク・ドライブ（ハ
ード・ファイル、フロッピー・ディスクなど）ごとに別
々のサービス待ち行列が維持される。各ドライブに関連
するデバイス・ドライバのソフトウェア・モジュール２
６からの「装置準備完了」指示に応答して、待ち行列２
４から一時に１個ずつ要求が取り出され、（ＢＩＯＳを
介して）指定されたディスク・ドライブの図示してない
制御装置に指名される。
【００２７】図３及び図４は、従来技術の待ち行列構造
２４内の要求が、どのようにして分類可能な位置に置か
れ、「アドレス順」にサービスを受けるかを示す簡略化
した図である。これらの従来技術のシステムのサービス
待ち行列２４は、１重リンク式リスト待ち行列として構
築され、その中に、要求がサービス・カーネルによって
分類可能に入れられ、装置による動作のために、要求が
その先頭からサービス・カーネルによって一時に１個ず
つ指名される。サービス待ち行列２４が空のとき、サー
ビス・カーネルが受け取った、関連する装置に関係する
次の要求が、サービス待ち行列の先頭に置かれる。次の
要求を受け取った時に、その待ち行列が空でない場合
は、サービス・カーネルは、その要求によって指定され
るＲＢＡとその待ち行列内に既に存在する要求によって
指定されるＲＢＡの関係によって決定される待ち行列内
の位置に、その要求を入れる。この関係は、その関連す
るディスク・ドライブの読み書きヘッドの移動方向を暗
示する。
【００２８】受け取った要求は、待機中の要求の「アド
レス順」によるサービスを維持するように、すなわち読
み書きヘッドによってその移動方向を反転せずに到達可
能なＲＢＡを有する待機中の全ての要求が、その方向に
ヘッドが移動している間サービスを受け、また読み書き
ヘッドの方向が反転した後は、反転方向で到達可能なＲ
ＢＡを有する待機中の要求が連続してサービスを受けら
れるように、サービス待ち行列内に配置される。
【００２９】図３及び図４の例では、（最近に待ち行列
からはずされた要求のＲＢＡが３２０であり、その前に
除去された要求のＲＢＡが１１０であったので）読み書
きヘッドは、ＲＢＡが増加する方向に移動しているもの
と仮定する。サービス待ち行列は、まだサービスを受け
ていない要求を５個含む。まだサービスを受けていない
要求のうちの２個は、４３０及び１０００の値のＲＢＡ
を有し、これは、読み書きヘッドによって方向を変えず
に現位置（ＲＢＡが３２０以上）から到達可能な記憶位
置を表し、他の３個の要求は、３２０未満のＲＢＡ値
（具体的にはＲＢＡ値１２６、１８０及び３１０）を有
し、それは読み書きヘッドの方向を変えないと到達でき
ない記憶位置を表している。
【００３０】このヘッドの「昇順」の移動方向で到達可
能なＲＢＡを有する要求は、ＲＢＡが“４３０，１００
０”の昇順を形成するようにその待ち行列内に置かれ、
読み書きヘッドを反転しないと到達不能なＲＢＡを有す
る要求は、ＲＢＡが降順に「３１０、１８０及び１２
６」と並ぶように待ち行列内に置かれる。したがって、
待ち行列内にそれ以上要求が入れられなかった場合は、
読み書きヘッドがこのＲＢＡの昇順方向に移動している
間、先頭に最も近い２個の要求がディスクに指名され、
残り３個のうちの最初の要求が指名されると、読み書き
ヘッドは、方向を変えて反対方向に進むようになり、そ
してヘッドは、最後の３個の要求のＲＢＡ記憶位置に次
々に到達する。
【００３１】図３及び図４ は、待ち行列が図３に示し
た状態にある時に要求を受け取ると仮定して、ＲＢＡ値
が７５２の新しい要求がサービス待ち行列内のどこに置
かれるかを示す。図３では、新しい要求は待ち行列の上
方の外部に示され、図４では、新しい要求は待ち行列内
の適切な「アドレス順」の位置に示されている。
【００３２】３. 本発明のディスク入出力スケジュー
リング−概要 図５に示すように、本発明は、システムの各物理的ディ
スク・ドライブに関して１組の（複数の）保留待ち行列
３４及びサービス待ち行列３６を維持するために、修正
されたサービス・カーネル３２を使用することを企図し
ている。サービス待ち行列３６は、従来技術のサービス
待ち行列とは、その要求が、（要求が、待ち行列に入れ
られた順序とは無関係な順序でサービスを受ける）分類
されたエレベータ順ではなく、ＦＩＦＯベースでサービ
スを受ける点で異なっている。
【００３３】ドライバ３８から装置準備完了の指示を受
け取ると、サービス・カーネル３２は、サービス待ち行
列３６の先頭から要求を指名し、それによってサービス
待ち行列が空になった場合、保留待ち行列３４からの要
求をサービス待ち行列に移そうとする。そのとき少なく
とも１個の保留待ち行列が「準備完了」（空ではない）
である場合、優先順位が最高のこの準備のできた待ち行
列を見つけ、その保留待ち行列から（以下に詳細に記述
するようにして）サービス待ち行列に一つまたは全ての
要求を移す。保留待ち行列がその時全て空であった場合
は、サービス・カーネルは、次に受け取った要求を直接
サービス待ち行列に前送りする。
【００３４】４．本発明のディスク入出力スケジューリ
ング−詳細 図６ないし図１１は、本発明の保留待ち行列の好ましい
構成の編成及び使い方を示す。保留待ち行列とそのタス
クの優先順位の関連を、図６に示す。個々の保留待ち行
列内での要求の順序を、図７及び８に示す。新しく受け
取った要求を保留待ち行列に入れるためにサービス待ち
行列によって実行される動作を、図９に示す。サービス
・カーネルによって実行される、保留待ち行列に関する
サービス渇望動作及び優先順位ブースト動作を、図１０
に示す。図１１は、条件付きで保留待ち行列からサービ
ス待ち行列に要求を移すためにサービス・カーネルによ
って実行される動作を示す。
【００３５】図６を参照すると、保留待ち行列は、優先
順位の降順で、ＦＩＦＯ，ＴＣ＿４，ＴＣ＿３，ＴＣ＿
２，ＴＣ＿１，ＲＧ＿４，ＲＧ＿３，ＲＧ＿２，ＲＧ＿
１，ＩＤＬＥの名称を有する、２重リンク式リスト（図
７及び８に更に詳しく示す）である。ＦＩＦＯ保留待ち
行列は、図１０に関して後述する渇望優先順位ブースト
処理中、優先順位がより低い待ち行列からのみ要求を受
け取る。その他の保留待ち行列は、タスクの優先度クラ
スに対応する優先順位を有し、対応する優先順位を有す
るタスクに関連する新しい要求を受け取る。ＦＩＦＯ待
ち行列とＩＤＬＥ待ち行列の中間の優先順位を有する待
ち行列も、後述の渇望ブースト処理中、優先順位がより
低い待ち行列から要求を受け取る資格がある。
【００３６】ＯＳ／２システムでは、プログラマがタス
クに優先度クラスを割り当てる。タスクの優先度クラス
は、９６クラスまで割当て可能であり、３２個の時間依
存型のタスク・クラスからなるグループ（優先順位の降
順でＴＣ３１−ＴＣ００）、３２個の標準型（中間）の
タスク優先度クラスからなるグループ（優先順位の降順
でＲＧ３１−ＲＧ００）、及び３２個の空き時間型（最
低）の優先度クラスからなるグループ（降順でＩＤＬＥ
３１−ＩＤＬＥ００）の３つのグループに大別される。
【００３７】待ち行列ＴＣ＿ｎ（ｎ＝１−４）は、図６
に示す４つのサブグループ中のＴＣ３１−ＴＣ００のタ
スクに関連する新規の要求を受け取る。すなわち、ＴＣ
＿４は、タスク優先順位ＴＣ２４−ＴＣ３１に関連する
新規の要求を受け取る。ＴＣ＿３は、タスク優先順位Ｔ
Ｃ１６−ＴＣ２３に関連する新規の要求を受け取る。Ｔ
Ｃ＿２は、タスク優先順位ＴＣ０８−ＴＣ１５に関連す
る要求を受け取る。そして、ＴＣ＿１は、ＴＣ００−Ｔ
Ｃ０７に関連する要求を受け取る。緊急クラスのフォア
グラウンド・タスクに関連する要求は、同じ優先順位を
もつバックグラウンド・タスクに関連する要求よりも優
遇される。したがって、クラスＴＣ００−ＴＣ３１（図
６のＴＣ／ｆｇｎｄ）の全てのフォアグラウンド・タス
クに関連する新規の要求は、全てＴＣ＿４（優先順位が
最高の時間依存型待ち行列）に送られる。
【００３８】同様に、待ち行列ＲＧ＿ｎ（ｎ＝１−４）
は、図６の４つの主要なサブグループのうちの中間（標
準優先順位）の範囲ＲＧ３１−ＲＧ００内のタスクに関
連する新しい要求を受け取る。ＲＧ＿４は、タスク優先
順位ＲＧ２４−ＲＧ３１に関連する新しい要求を受け取
る。ＲＧ＿３は、タスク優先順位ＲＧ１６−１２Ｇ２３
に関連する要求を受け取る。ＲＧ＿２は、タスク優先順
位ＲＧ０８−ＲＧ１５に関連する要求を受け取る。標準
（中間）クラスのフォアグラウンド・タスクに関連する
要求は、優遇される。したがって、クラスＲＧ００−Ｒ
Ｇ３１（図６のＲＧ／ｆｎｄ）のどれに含まれるフォア
グラウンド・タスクに関連する新しい要求も全てＲＧ＿
４（優先順位が最高の通常待ち行列）に移される。
【００３９】図７は、ＦＩＦＯ待ち行列以外の各保留待
ち行列内に要求がどのように配置されるかを示す。図７
に示すように、各待ち行列は、アンカ・テーブル６０と
称する２重リンク式リストとして構築される。アンカ６
０は、少なくとも所与の処理セッション中は固定された
ままとなる、システム・メモリ内のあるアドレスに位置
する。待ち行列が少なくとも２個の要求を含むとき、ア
ンカ６０は、先頭の要求６１と末尾の要求６２の位置を
示すポインタを含んでいる。中間の位置にある要求を６
３で示し、連続する要求位置の間の２重リンクを６４に
示す。要求の位置６１ないし６３は、システム・メモリ
内の任意の位置でよいことを理解されたい。要求は、図
に示すように、そのＲＢＡ値が末尾に向う方向に増加す
るように、待ち行列内に配置される。
【００４０】アンカは、迅速に（直接）先頭と末尾の要
求の位置を見つけるための指示を提供する他に、（個々
の要求のパケットを見つけて調べることなく）待ち行列
の状況を迅速に確認するための他の重要情報をも提供す
る。それには、（図１０に関して後で考察する）渇望サ
ービスに関するタイムアウト因子を表す最大待ち時間
（ＭａｘＷａｉｔＴｉｍｅ）、待ち行列が、空になった
後で要求を受け取るとき、最大待ち時間因子だけ増加さ
れる現時刻（Ｐｒｅｓｅｎｔ Ｔｉｍｅ ＯｆＤａｙ）
であるタイムスタンプ（ＴｉｍｅＳｔａｍｐ）機能、そ
して後述するように渇望条件が検出されたとき現在の待
ち行列の内容を移す先の待ち行列を示すために使用され
るブースト待ち行列（ＢｏｏｓｔＱ）機能が含まれる。
個々の待ち行列アンカに加えて、メモリ内には、各物理
的ディスク・ドライブについて、そのドライブに関連す
る全ての待ち行列のセット、関連するデバイス・ドライ
バの処理状況、サービス待ち行列から最近に指名された
要求の処理を完了した後のそのドライブの読み書きヘッ
ドのＲＢＡ位置、及び優先順位が最高の空でない保留待
ち行列の識別を示す、入出力構造テーブル（ＩＯＳｔｒ
ｕｃ）が維持される。
【００４１】図８に示すように、ＦＩＦＯ保留待ち行列
も、末端要求の位置を含む重要パラメータを示すアンカ
を有する、２重リンク式リスト待ち行列として構築され
る。ＦＩＦＯ待ち行列は、後で考察する（図１０）渇望
操作の結果として、優先順位の低い待ち行列からのみ要
求を受け取る。要求は渇望ブースト中にこの待ち行列に
ブロック転送されるので、ＦＩＦＯ待ち行列内に要求が
あるとき、それは一つ以上のブロックからなり、各ブロ
ック内で、（要求が複数あるとき）要求は（先頭から）
ＲＢＡが増加する順に並んでいる。
【００４２】所与のディスク・ドライブＭを対象とする
入出力要求を受け取ったとき、オペレーティング・シス
テムのサービス・カーネルによって実行される動作を、
図９に示す。図の例では、要求は、優先度クラスがＴＣ
０７のタスクＮに関連するものであると仮定する。要求
パケット中の情報から、サービス・カーネルは、目標の
ドライブ及び関連するタスク優先順位を確認する（ステ
ップ７０）。次に、カーネルは、関連するタスクがオペ
レーティング・システムのフォアグラウンド中で処理中
であるか否かを、やはり要求パケット中の情報から確認
する（ステップ７２）。そのタスクがフォアグラウンド
中のものである場合は、その要求を保留待ち行列ＴＣ＿
４Ｍ（ドライブＭに関連する優先順位が最高の緊急保留
待ち行列）に入れる動作ステップ７４が実行される。タ
スクがフォアグラウンド中のものでない場合は、その要
求を待ち行列ＴＣ＿１Ｍ（通常はクラスＴＣ００−ＴＣ
０７のタスクに関連する緊急保留待ち行列）に入れる動
作ステップ７６が実行される。
【００４３】前に指摘したように、優先度クラスに分類
された保留待ち行列内の要求は、そのＲＢＡが待ち行列
の末尾に向かって増加するように各待ち行列内で並べら
れる。したがって、このような配列が、要求入力動作ス
テップ７４及び７６中に維持されることが理解される。
動作ステップ７４または７６を完了すると、サービス・
カーネルは、図１０に関して次に述べる、渇望検査及び
選択的ブースト処理を実行する。
【００４４】渇望検査処理（図１０のステップ８０−９
０）では、サービス・カーネルは、まずステップ８０
で、（当該の待ち行列アンカ中の状況情報を調べること
によって）要求（図９の例ではＴＣ＿４Ｍであると仮定
される）を入れたばかりの保留待ち行列が、その入力前
に空であったかどうか判定する。待ち行列が前に空であ
った場合は、この待ち行列に関してそれ以上の渇望検査
は必要なく、新しいタイムスタンプ（現時刻＋この待ち
行列に対する最大待ち時間因子に等しい）が計算され、
当該の待ち行列アンカに入れられる（ステップ８２）。
このとき、カーネルは、ステップ８４から始まる動作を
続行し、渇望サービスを必要とする、優先順位が次に低
い待ち行列を見つけ出そうとする。
【００４５】ステップ８０で、要求を入れたばかりの待
ち行列が前に空でなかったことをカーネルが検出した場
合、カーネルは、当該の各アンカのタイムスタンプを現
時刻と比較して、最大待ち時間に関連するタイムアウト
因子が経過したかどうか判定する（ステップ８６）。タ
イムスタンプが現時刻よりも大きい場合、タイムアウト
は終了していず、したがってさらに検査は不要であり、
カーネルはステップ８４に進んで、優先順位のより低い
待ち行列を検査する。タイムスタンプが現時刻よりも小
さい場合（ステップ８６のＹ）、最大待ち時間タイムア
ウトが過ぎており、ステップ８７を実行して、渇望条件
があるかどうか待ち行列内の個々の要求パケットを検査
する。
【００４６】待ち行列内の個々の要求パケットを更に検
査する必要があるのは、最初に記録されたタイムスタン
プは、以前に空になっていた待ち行列に要求を入れる動
作（ステップ８２）に関連するものであり、このように
して入れた要求は、関連するタイムスタンプを変更せず
に、いつでもサービス待ち行列に移すことができる（下
記の図１１に関する考察を参照されたい）はずだからで
ある。したがって、アンカのタイムスタンプは、待ち行
列の真の状況（すなわち、「最も古い」要求の経過時
間）を反映していない。そして、各要求パケットは、入
力の時間と最大待ち時間の合計であるタイムスタンプを
有する。個々のタイムスタンプが全て現時刻より小さく
ない場合（ステップ８７のＮ出口）、その待ち行列は渇
望されていず、カーネルは、ステップ８４に進む（この
とき、カーネルは、アンカのタイムスタンプ値を最も古
い／最小の個別タイムスタンプの値に等しく設定す
る）。いずれかの個別タイムスタンプが現時刻よりも小
さい場合は（ステップ８７のＹ出口）、そのタイムアウ
トが過ぎており、待ち行列は「渇望」条件にあると見な
される。次にサービス・カーネルはステップ９２以降の
ブースト処理を実行し、渇望待ち行列の内容を優先順位
が次に高い「適格」保留待ち行列に移す。
【００４７】ＦＩＦＯ待ち行列（「常に適格」）以外の
「適格」保留待ち行列は、空であるか、あるいはそのＲ
ＢＡが全て渇望待ち行列の末尾の要求のＲＢＡよりも高
い要求またはその待ち行列の先頭の要求のＲＢＡよりも
低い要求をこのとき含んでいるものである。更に、ステ
ップ９２の、「優先順位が次に高い、適格待ち行列」の
探索は、渇望待ち行列のアンカ中で指定される「ブース
ト目標待ち行列」から始まる。（これによって、渇望待
ち行列をブーストするとき、システムは優先順位が隣接
する待ち行列を飛ばすことができるようになる。）
【００４８】ステップ９２で見つかった、優先順位が次
に高い適格待ち行列が、ＦＩＦＯ保留待ち行列である
か、それとも別の（優先順位が中間の）待ち行列である
か（それぞれ判断ステップ９４でＹまたはＮ）に応じ
て、システムは、渇望待ち行列の内容をＦＩＦＯ待ち行
列または見つかった別の待ち行列に転送（ブースト）
（それぞれステップ９６または９８）し、渇望待ち行列
を空にリセットする。渇望待ち行列内の要求が転送され
る先の適格待ち行列が、その転送前に空でなかった場合
は、渇望待ち行列の要求は、その適格待ち行列の一端に
ブロックとして連結される。当該の適格待ち行列がＦＩ
ＦＯ待ち行列である場合は、渇望待ち行列の要求は、Ｆ
ＩＦＯ待ち行列の末尾に連結される。当該の適格待ち行
列がＦＩＦＯ待ち行列以外のものである場合は、渇望待
ち行列の要求は、（図７により）転送の後、当該の適格
待ち行列内のＲＢＡの順序を先頭から末尾まで昇順に保
つのに適した、適格待ち行列のどちらの末端にでも連結
される。
【００４９】待ち行列は２重リンク式リストなので、ブ
ロック転送ステップ９６または９８は、ただ先頭／末尾
ポインタの情報を渇望待ち行列のアンカから選択された
適格待ち行列のアンカに移し、必要なら適格待ち行列の
連結位置にある要求パケットを、互いにクロスリンクす
るように修正するだけで実施できる。
【００５０】見つかった適格待ち行列が、転送前に空で
なく、かつＦＩＦＯ待ち行列である場合、渇望待ち行列
のアンカ中の末尾ポインタが、ＦＩＦＯ待ち行列のアン
カ中の末尾ポインタに取って代わり、連結位置にある要
求パケット（転送前にＦＩＦＯ待ち行列の末尾にあった
もの）が、互いにクロスリンクするように修正される
（すなわち、転送前にＦＩＦＯ待ち行列の末尾にあった
要求パケットと渇望待ち行列の先頭にあった要求パケッ
トが、そのように修正される）。
【００５１】見つかった適格待ち行列がＦＩＦＯ待ち行
列以外のものであり、かつ転送前に空でなかった場合、
渇望待ち行列のアンカ中の、選択された末端（先頭また
は末尾）ポインタが、別の適格待ち行列のアンカ中の当
該のポインタに取って代わり、その別の適格待ち行列の
連結位置にある、新たに互いに隣接する位置にくる要求
パケットが、互いにクロスリンクするように修正され
る。したがって、渇望要求が、その別の適格待ち行列の
先頭に連結される（全ての渇望要求のＲＢＡが、その別
の待ち行列内に以前にあった全ての要求のＲＢＡの値よ
りも小さい）場合、渇望待ち行列のアンカ中の先頭ポイ
ンタが、その別の適格待ち行列のアンカ中の新しい先頭
ポインタになり、以前には渇望待ち行列及びその別の待
ち行列内の、末尾にあった要求と先頭にあった要求が、
クロスリンクするように修正される。逆に、渇望待ち行
列がその別の待ち行列の末尾に連結される（全ての渇望
要求のＲＢＡが、以前にこの別の待ち行列内にあった全
ての要求のＲＢＡよりも大きい）場合は、渇望待ち行列
のアンカ中の末尾ポインタが、その別の待ち行列のアン
カ中の以前の末尾ポインタに取って代わり、渇望待ち行
列の当該の以前の先頭の要求と別の待ち行列の末尾の要
求が、クロスリンクするように修正される。
【００５２】渇望要求を優先順位が中間の空でない適格
待ち行列に連結する際に、ＲＢＡを昇順に保つ理由は、
先頭の近接度の判定に従って、当該の待ち行列の一端か
らサービス待ち行列への要求の選択を可能にするためで
ある（以下の図１１の考察を参照のこと）。
【００５３】図１１は、要求がどのようにして保留待ち
行列からサービス待ち行列に移されるかを示している。
サービス・カーネルは、ドライブが入出力動作の準備が
できたときにサービス待ち行列によって与えられる「ド
ライブ準備完了」の指示を、ディスク・ドライブに関す
るデバイス・ドライバから受け取ると（ステップ１１
０）、当該の入出力動作を初期設定するために、関連す
るサービス待ち行列から先頭の要求を指名する（待ち行
列からはずす）。サービス待ち行列が、その要求を指名
した後に空になる場合（判断ステップ１１２でＹ）、カ
ーネルは、準備ができている（空でない）優先順位が最
高の保留待ち行列を見つけ出そうとし、それが見つかっ
た場合、１個または複数の要求をそこからサービス待ち
行列に移す。（動作１２０以降）
【００５４】全ての保留待ち行列が空ではなかった場
合、サービス・カーネルは、ＦＩＦＯ待ち行列が空かど
うかを判定する。ＦＩＦＯ待ち行列の準備ができている
場合（判断ステップ１２２でＹ）、その要求が全て、既
存のＲＢＡの順にサービス待ち行列にブロック転送さ
れ、ＦＩＦＯ待ち行列は空にリセットされる（ステップ
１２４）。優先順位が最高の準備ができている待ち行列
が、ＦＩＦＯ待ち行列以外のものである場合は（判断ス
テップ１２２でＮ）、唯一つの要求が、その別の待ち行
列の先頭または末尾からサービス待ち行列に移され、そ
の別の待ち行列内の標識が、（新しい先頭または末尾の
要求の位置を示すように）修正される（ステップ１２
６）。
【００５５】ステップ１２６における先頭の要求か末尾
の要求かの選択は、関連するディスク・ドライブの読み
書きヘッドの現在位置に関する近接度の判定に従って行
われる。先頭及び末尾の要求中の「末端ＲＢＡ」（「末
端ＲＢＡ」とは、ＲＢＡと当該の要求パケット中で指定
された転送ブロックの長さの合計である。）が、最近に
（ステップ１１０で）ディスク・ドライブに指名された
要求の末端ＲＢＡと比較され、後者の最終ＲＢＡの値
が、関連する入出力構造テーブルに記録され、読み書き
ヘッドの現在位置の指示として有効に働く。読み書きヘ
ッドの位置に近接したＲＢＡをもつ先頭または末尾の要
求は、サービス待ち行列（の先頭）に移される。
【００５６】
【発明の効果】本発明により、マルチタスキング・デー
タ処理システムのディスク入出力動作をスケジュールす
るための改良された方法及び手段を提供できる。
【図面の簡単な説明】
【図１】本発明を適用すると有利な典型的な従来技術の
データ処理システムを示す図である。
【図２】上記で広義に説明した「エレベータ順」によ
る、従来技術によるディスク入出力要求のサービスを具
体例で示した図である。
【図３】上記で広義に説明した「エレベータ順」によ
る、従来技術によるディスク入出力要求のサービスを具
体例で示した図である。
【図４】上記で広義に説明した「エレベータ順」によ
る、従来技術によるディスク入出力要求のサービスを具
体例で示した図である。
【図５】共通ディスク・ドライブを指定する入出力要求
用の保留待ち行列及びサービス待ち行列の構造を概略的
に示した図である。
【図６】本発明による優先度ランクを付けた保留待ち行
列の好ましい構造を示す図である。
【図７】図６に示したＴＣ、ＲＧ及びＩＤＬＥ保留待ち
行列内における、ＲＢＡの昇順による入出力要求の配置
を示す図である。
【図８】図６に示したＦＩＦＯ保留待ち行列内における
入出力要求の順序配置を示す図である。
【図９】図６に示した保留待ち行列に関して、オペレー
ティング・システムのサービス・カーネルによって実行
される、要求待ち行列化処理を示す図である。
【図１０】図６に示した保留待ち行列に関して、オペレ
ーティング・システムのサービス・カーネルによって実
行される、渇望前送り処理を示す図である。
【図１１】サービス待ち行列内の要求に伴うデバイス・
ドライバからの信号に応答して、図６の保留待ち行列か
ら図５に示すサービス待ち行列に要求を移すために、サ
ービス・カーネルによって行われる転送処理を示す図で
ある。
【符号の説明】
２０ 適用業務プログラム・インターフェース（ＡＰ
Ｉ） ３２ サービス・カーネル ３４ 保留待ち行列 ３６ サービス待ち行列 ３８ デバイス・ドライバ

Claims (6)

    【特許請求の範囲】
  1. 【請求項１】ＣＰＵと、メモリ・サブシステム及びディ
    スク記憶サブシステムと、上記ＣＰＵによって処理中の
    タスクに関して出される入出力要求に従って上記ディス
    ク記憶サブシステムの入出力動作をスケジューリングす
    る手段とを含む、マルチタスキング・データ処理システ
    ムにおいて、該スケジューリング手段が、上記記憶サブ
    システムの１台のディスク・ドライブと一義的に関連付
    けられ、上記ディスク・ドライブによって実行される入
    出力動作を指定する入出力要求を記憶する働きをする複
    数の待ち行列からなり、一つのサービス待ち行列と少な
    くとも一つの保留待ち行列とを含む待ち行列セットと、
    上記サービス待ち行列に記憶された要求にＦＩＦＯ方式
    でサービスし、サービスを受ける各要求に応答して、そ
    の要求によって指定され、上記の関連するディスク・ド
    ライブによって実行される入出力動作を指名するため
    の、上記サービス待ち行列に結合されたデバイス・ドラ
    イバ手段であって、上記サービス待ち行列が空のときを
    検出する手段と、その状態に関連して空の指示を行う手
    段とを含むデバイス・ドライバ手段と、上記の少なくと
    も一つの保留待ち行列に結合された、上記の処理中のタ
    スクに関して新しく出された入出力要求を受け取り、上
    記要求が、上記の少なくとも一つの保留待ち行列内で、
    それに関して要求が出されるタスクの優先度クラスに関
    連付けて位置が並べられた、分類済みの位置順で上記要
    求を上記の少なくとも一つの保留待ち行列に記憶するた
    めの手段と、上記の少なくとも一つの保留待ち行列及び
    上記サービス待ち行列に結合された、上記の少なくとも
    一つの保留待ち行列内の上記要求のタスク配列に少なく
    とも部分的に基づいた順序で、上記の少なくとも一つの
    保留待ち行列から上記サービス待ち行列に要求を選択的
    に転送するための転送手段であって、上記の少なくとも
    一つの保留待ち行列が空でないときを検出する手段を含
    む転送手段と、を有し、上記の処理中のタスクが、少な
    くとも一つの第１の優先度クラスと、少なくとも一つ
    の、第１の優先度クラスよりも低い優先順位のクラスを
    表す第２の優先度クラスを有し、かつ上記の少なくとも
    一つの保留待ち行列が、優先順位が最高の保留待ち行列
    と、少なくとも一つの第１の優先順位の保留待ち行列
    と、少なくとも一つの第２の優先順位の保留待ち行列と
    を含み、上記の受け取った要求を上記の少なくとも一つ
    の保留待ち行列に記憶する上記手段が、第１の優先度ク
    ラス及び第２の優先度クラスのタスクに関連する要求
    を、それぞれ上記の少なくとも一つの第１の優先順位の
    保留待ち行列及び上記の少なくとも一つの第２の優先順
    位の保留待ち行列に記憶するように適合されており、上
    記の少なくとも一つの保留待ち行列から上記サービス待
    ち行列に上記要求を転送する上記手段が、上記の各サー
    ビス待ち行列の空の指示に応答して、優先順位が最高の
    保留待ち行列が空でない場合は、上記の優先順位が最高
    の保留待ち行列から上記サービス待ち行列に要求を転送
    し、優先順位が最高の待ち行列が空であり、かつ第１の
    優先順位の保留待ち行列が空でない場合は、上記の少な
    くとも一つの第１の優先順位の待ち行列からサービス待
    ち行列に要求を転送し、また優先順位が最高の待ち行列
    と第１の優先順位の待ち行列が空であり、かつ第２の優
    先順位の保留待ち行列が空でない場合は、上記の第２の
    優先順位の待ち行列からサービス待ち行列に要求を転送
    することを特徴とする、マルチタスキング・データ処理
    システム。
  2. 【請求項２】さらに第２の優先順位の保留待ち行列及び
    第１の優先順位の保留待ち行列内でサービス渇望条件を
    検出するための渇望処理手段を含み、上記条件が、所定
    の時間より長い間、当該の保留待ち行列中に要求が保持
    されているときに発生し、上記条件が検出された待ち行
    列から、選択された優先順位がより高い待ち行列に要求
    を転送するためのものである、請求項１に記載のマルチ
    タスキング・データ処理システム。
  3. 【請求項３】上記の処理中のタスクの優先度クラスが、
    時間依存型優先度クラスの少なくとも第１と第２のグル
    ープと、標準型優先度クラスの少なくとも第１と第２の
    グループとを含み、上記クラスが、降順で、第１時間依
    存型第２時間依存型第１標準型第２標準型の相対的優先
    度ランクを有し、上記の少なくとも一つの保留待ち行列
    が、優先順位が最高の保留待ち行列と、第１及び第２の
    時間依存型優先順位の保留待ち行列と、第１及び第２の
    標準型優先順位の保留待ち行列とを含み、降順で、最高
    の優先順位第１時間依存型優先順位第２時間依存型優先
    順位第１標準型優先順位第２標準型優先順位のサービス
    に関する相対的優先度ランクを有し、上記の受け取った
    要求を上記の少なくとも一つの保留待ち行列に記憶する
    ための上記手段が、第１時間依存型クラスまたは第２時
    間依存型クラスのグループに分類される優先順位をもつ
    フォアグラウンド・タスクに関連する要求を上記の第１
    時間依存型保留待ち行列に記憶し、第１標準型クラスま
    たは第２標準型クラスのグループに分類される優先順位
    をもつフォアグラウンド・タスクに関連する要求を上記
    の第１通常保留待ち行列に記憶し、第１時間依存型、第
    ２時間依存型、第１標準型、及び第２標準型クラスのグ
    ループに分類される優先順位をもつバックグラウンド・
    タスクに関連する要求をそれぞれ、上記の第１時間依存
    型、第２時間依存型、第１標準型及び第２標準型保留待
    ち行列に記憶するというスケジュールに従って上記要求
    を記憶するように適合されており、上記の少なくとも一
    つの保留待ち行列から上記サービス待ち行列に要求を転
    送するための転送手段が、上記サービス待ち行列の空の
    指示に応答して、少なくとも一つの上記保留待ち行列が
    空でないとき、優先順位が最高の空でない保留待ち行列
    から上記サービス待ち行列に要求を転送することを特徴
    とする、請求項１に記載のマルチタスキング・データ処
    理システム。
  4. 【請求項４】時間依存型保留待ち行列及び標準型保留待
    ち行列がそれぞれ、２重リンク式リスト待ち行列として
    構成されることを特徴とする、請求項３に記載のマルチ
    タスキング・データ処理システム。
  5. 【請求項５】上記の各要求が、入出力動作が実行される
    べき上記の関連するディスク・ドライブ内の相対的ブロ
    ック記憶アドレスを示すＲＢＡ情報を含み、上記の受け
    取った要求を上記保留待ち行列に記憶するための手段
    が、上記の時間依存型保留待ち行列及び標準型保留待ち
    行列に要求を入れる際、待ち行列内の全ての要求のＲＢ
    Ａ値を当該の待ち行列の一端に対して昇順に位置が並ん
    だ状態に保つように、入れられる要求を待ち行列内の他
    の要求に対して相対的に位置決めするように動作し、上
    記デバイス・ドライバの指示手段が、上記サービス待ち
    行列から最後に除去された要求のＲＢＡ値を示し、かつ
    間接的に上記ディスク・ドライブ内の読み書きヘッド・
    アセンブリの現在位置を示すＲＢＡ指示を、上記サービ
    ス待ち行列の空の指示と一緒に提供し、上記保留待ち行
    列から上記サービス待ち行列に要求を転送する手段が、
    上記の時間依存型保留待ち行列または上記の標準型保留
    待ち行列からある要求を転送のために除去するとき、当
    該の待ち行列の一端または他の端から除去される要求
    を、上記サービス待ち行列から最後に除去された要求の
    上記ＲＢＡ値の上記指示によって示される、上記の関連
    するディスク・ドライブ内の上記読み書きヘッド・アセ
    ンブリの現在位置に最も近いＲＢＡ値を有する要求が選
    択されるように、近接計算の決定に基づいて選択するよ
    うに動作することを特徴とする、請求項４に記載のマル
    チタスキング・データ処理システム。
  6. 【請求項６】ＣＰＵと、メモリ・サブシステム及びディ
    スク記憶サブシステムと、上記ＣＰＵによって処理中の
    タスクに関して出される入出力要求に従って上記ディス
    ク記憶サブシステムの入出力動作をスケジューリングす
    る手段とを含む、マルチタスキング・データ処理システ
    ムにおいて、該スケジューリング手段が、上記記憶サブ
    システムの１台のディスク・ドライブと一義的に関連付
    けられ、上記ディスク・ドライブによって実行される入
    出力動作を指定する入出力要求を記憶する働きをする複
    数の待ち行列からなり、一つの１重リンク式リスト・サ
    ービス待ち行列と、サービスに関する所定の相対優先順
    位を有する複数の２重リンク式リスト保留待ち行列とを
    含み、上記保留待ち行列が、上記システムによって処理
    中のタスクの優先順位に関連するサービス優先順位を有
    する複数の待ち行列と、いかなるタスクの優先順位とも
    関連しない、他の保留待ち行列のサービス優先順位より
    も高いサービス優先順位を有するＦＩＦＯ保留待ち行列
    とを含む、待ち行列セットと、上記サービス待ち行列に
    結合された、上記サービス待ち行列に記憶された要求に
    ＦＩＦＯ方式でサービスし、サービスを受ける各要求に
    応答して、その要求によって指定され、上記の関連する
    ディスク・ドライブによって実行される入出力動作を指
    名するための、デバイス・ドライバ手段と、上記の少な
    くとも一つの保留待ち行列に結合された、関連するタス
    クの優先度クラスの指示と、それに関して当該の入出力
    動作が実行される上記ディスク・ドライブ上の記憶位置
    を示すＲＢＡ（相対ブロック・アドレス）値とを含む、
    上記の処理中のタスクに関して新しく出された入出力要
    求を受け取る手段と、上記の保留待ち行列要求受取り手
    段と協働して、受け取った当該の要求中のＲＢＡ情報と
    当該の保留待ち行列に現在保持されている要求中のＲＢ
    Ａ情報とに応じて、当該の待ち行列中の要求が、当該の
    保留待ち行列の一端に対してＲＢＡ値が昇順の値の列を
    形成するように位置が並んだ状態に保たれるように選択
    された、受け取った当該の要求中で示されるタスクの優
    先順位に対応するサービス優先順位を有する上記ＦＩＦ
    Ｏ保留待ち行列以外の上記保留待ち行列の選択された位
    置に上記の受け取った各要求を入れる手段と、上記保留
    待ち行列と上記サービス待ち行列とに結合された、サー
    ビス待ち行列が現在空であるとのデバイス・ドライバか
    らの指示に応答して、上記の保留待ち行列のうちで優先
    順位が最高の空でない保留待ち行列から上記サービス待
    ち行列に一つまたは複数の要求を選択的に転送する手段
    であって、ＦＩＦＯ保留待ち行列が空でない場合は、上
    記ＦＩＦＯ保留待ち行列から上記サービス待ち行列に全
    ての要求を転送し、そうでない場合、すなわちＦＩＦＯ
    保留待ち行列が空であり、かつ別の保留待ち行列が空で
    ない場合は、優先順位が次に高い空でない保留待ち行列
    から、上記手段によって行われる、当該の優先順位が次
    に高い空でない保留待ち行列の先頭及び末尾にある要求
    のＲＢＡ値と上記デバイス・ドライバによって最後にサ
    ービスを受けた要求のＲＢＡ値との比較に基づく近接度
    の判定に基づいて、当該の優先順位が次に高い空でない
    保留待ち行列の先頭または末尾から選択された、一つの
    要求を転送する手段と、上記の受け取った要求を保留待
    ち行列に入れるための手段に結合された、上記要求が入
    れられつつある保留待ち行列、または優先順位がより低
    い保留待ち行列のいずれかにサービス渇望条件が存在す
    るかどうかを判定し、かつ上記渇望条件を有する待ち行
    列から、選択された優先順位がより高い保留待ち行列
    に、すなわち上記ＦＩＦＯ保留待ち行列より優先順位が
    低い上記保留待ち行列のうちの優先順位が次に高い空の
    待ち行列、あるいは優先順位が中間の全ての保留待ち行
    列が空ではない場合は、上記のＦＩＦＯ保留待ち行列に
    全ての要求を転送するための渇望ブースト手段とを含
    み、転送される上記の要求が、上記ＦＩＦＯ保留待ち行
    列に転送されるとき、転送時に上記保留待ち行列が空で
    ない場合は、上記待ち行列の末尾に連結されるという、
    特徴を有するマルチタスキング・データ処理システム。
JP3273551A 1990-10-26 1991-09-26 マルチタスキング・データ処理システム Expired - Lifetime JPH0760415B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US07/605,054 US5220653A (en) 1990-10-26 1990-10-26 Scheduling input/output operations in multitasking systems
US605054 1990-10-26

Publications (2)

Publication Number Publication Date
JPH04264947A JPH04264947A (ja) 1992-09-21
JPH0760415B2 true JPH0760415B2 (ja) 1995-06-28

Family

ID=24422076

Family Applications (1)

Application Number Title Priority Date Filing Date
JP3273551A Expired - Lifetime JPH0760415B2 (ja) 1990-10-26 1991-09-26 マルチタスキング・データ処理システム

Country Status (4)

Country Link
US (1) US5220653A (ja)
EP (1) EP0488501A3 (ja)
JP (1) JPH0760415B2 (ja)
CA (1) CA2051186A1 (ja)

Families Citing this family (118)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO1992006057A1 (en) * 1990-10-03 1992-04-16 Fujitsu Limited System for controlling issue of input/output instruction in data processing system
JPH0512093A (ja) * 1991-07-05 1993-01-22 Nec Corp フアイルブロツク排他解除方式
US5630128A (en) * 1991-08-09 1997-05-13 International Business Machines Corporation Controlled scheduling of program threads in a multitasking operating system
US5410677A (en) * 1991-12-30 1995-04-25 Apple Computer, Inc. Apparatus for translating data formats starting at an arbitrary byte position
US5887196A (en) * 1991-12-30 1999-03-23 Apple Computer, Inc. System for receiving a control signal from a device for selecting its associated clock signal for controlling the transferring of information via a buffer
US5640599A (en) * 1991-12-30 1997-06-17 Apple Computer, Inc. Interconnect system initiating data transfer over launch bus at source's clock speed and transfering data over data path at receiver's clock speed
US5848297A (en) * 1991-12-30 1998-12-08 Apple Computer, Inc. Control apparatus for maintaining order and accomplishing priority promotion in a computer interconnect
JPH05257851A (ja) * 1991-12-30 1993-10-08 Apple Computer Inc データの転送の順序を制御させる装置
US5485586A (en) * 1992-01-10 1996-01-16 Digital Equipment Corporation Queue based arbitration using a FIFO data structure
US5657471A (en) * 1992-04-16 1997-08-12 Digital Equipment Corporation Dual addressing arrangement for a communications interface architecture
US5588134A (en) * 1992-09-25 1996-12-24 Amdahl Corporation System for establishing priority among selected tasks based on location of tasks and sequence that the tasks were stored whereas task is always stored in location with the lowest available address
US5659690A (en) * 1992-10-15 1997-08-19 Adaptec, Inc. Programmably configurable host adapter integrated circuit including a RISC processor
US5581784A (en) * 1992-11-17 1996-12-03 Starlight Networks Method for performing I/O's in a storage system to maintain the continuity of a plurality of video streams
US5375202A (en) * 1993-01-04 1994-12-20 Xerox Corporation Dispatching and scheduling memory operations in an electronic printing system
EP0610677A3 (en) * 1993-02-12 1995-08-02 Ibm Communication device management module operating in two modes.
US5544318A (en) * 1993-04-16 1996-08-06 Accom, Inc., Asynchronous media server request processing system for servicing reprioritizing request from a client determines whether or not to delay executing said reprioritizing request
EP0739558B1 (en) * 1993-06-09 2003-04-16 BTG International Inc. Method and apparatus for multiple media digital communication system
US6738357B1 (en) 1993-06-09 2004-05-18 Btg International Inc. Method and apparatus for multiple media digital communication system
JP3549003B2 (ja) * 1993-08-31 2004-08-04 株式会社日立製作所 情報送出装置および情報送出／受信システム
US6256704B1 (en) * 1993-09-16 2001-07-03 International Business Machines Corporation Task management for data accesses to multiple logical partitions on physical disk drives in computer systems
US5437032A (en) * 1993-11-04 1995-07-25 International Business Machines Corporation Task scheduler for a miltiprocessor system
EP0654740A1 (de) * 1993-11-22 1995-05-24 Siemens Aktiengesellschaft Bussteuerung
US5684971A (en) * 1993-12-27 1997-11-04 Intel Corporation Reservation station with a pseudo-FIFO circuit for scheduling dispatch of instructions
DE69521549T2 (de) 1994-04-04 2001-10-25 Hyundai Electronics America, Milpitas Verfahren zur Verwaltung gemeinsamer Mittel mehrerer Verarbeitungseinheiten
US5732239A (en) * 1994-05-19 1998-03-24 Starlight Networks Method for operating a disk storage system which stores video data so as to maintain the continuity of a plurality of video streams
US5802394A (en) * 1994-06-06 1998-09-01 Starlight Networks, Inc. Method for accessing one or more streams in a video storage system using multiple queues and maintaining continuity thereof
US5603063A (en) * 1994-06-27 1997-02-11 Quantum Corporation Disk drive command queuing method using two memory devices for storing two types of commands separately first before queuing commands in the second memory device
JPH08212086A (ja) * 1994-09-30 1996-08-20 Microsoft Corp オフィスマシンのオペレーティングシステム及び方法
FR2727911A1 (fr) * 1994-12-08 1996-06-14 Valeo Vision Bague eclairante pour allume-cigares, en particulier pour vehicule automobile
US5613085A (en) * 1994-12-27 1997-03-18 International Business Machines Corporation System for parallel striping of multiple ordered data strings onto a multi-unit DASD array for improved read and write parallelism
US5854898A (en) 1995-02-24 1998-12-29 Apple Computer, Inc. System for automatically adding additional data stream to existing media connection between two end points upon exchange of notifying and confirmation messages therebetween
US5623692A (en) * 1995-05-15 1997-04-22 Nvidia Corporation Architecture for providing input/output operations in a computer system
US5805930A (en) * 1995-05-15 1998-09-08 Nvidia Corporation System for FIFO informing the availability of stages to store commands which include data and virtual address sent directly from application programs
JPH096633A (ja) * 1995-06-07 1997-01-10 Internatl Business Mach Corp <Ibm> データ処理システムに於ける高性能多重論理経路の動作用の方法とシステム
US5940612A (en) * 1995-09-27 1999-08-17 International Business Machines Corporation System and method for queuing of tasks in a multiprocessing system
US5754776A (en) * 1995-12-28 1998-05-19 Intel Corporation Re-prioritizing background data transfers in multipoint conferencing
US5925105A (en) * 1995-12-28 1999-07-20 Intel Corporation Preventing processor domination during background data transfer in multipoint conferencing
US5802282A (en) * 1995-12-28 1998-09-01 Intel Corporation Recovering missing data during background data transfer in multipoint conferencing
JP2950223B2 (ja) * 1996-01-12 1999-09-20 日本電気株式会社 データ読出装置
US5978856A (en) * 1996-01-26 1999-11-02 Dell Usa, L.P. System and method for reducing latency in layered device driver architectures
US5854941A (en) * 1996-05-31 1998-12-29 Acceleration Software International Corporation System for estimating access time by deriving from first and second rotational time from rotational time table based on logical address and head movement time
US5961623A (en) * 1996-08-29 1999-10-05 Apple Computer, Inc. Method and system for avoiding starvation and deadlocks in a split-response interconnect of a computer system
US5845318A (en) * 1996-10-28 1998-12-01 International Business Machines Corporation Dasd I/O caching method and application including replacement policy minimizing data retrieval and storage costs
US6393455B1 (en) 1997-03-28 2002-05-21 International Business Machines Corp. Workload management method to enhance shared resource access in a multisystem environment
US5991825A (en) * 1997-07-11 1999-11-23 International Business Machines Corporation System for handling missed revolution in a disk drive by aborting the execution of primary command and executing secondary command if a missed revolution occurs
US6202137B1 (en) * 1997-09-18 2001-03-13 Intel Corporation Method and apparatus of arbitrating requests to a multi-banked memory using bank selects
US5999963A (en) * 1997-11-07 1999-12-07 Lucent Technologies, Inc. Move-to-rear list scheduling
FR2771830B1 (fr) * 1997-12-03 2000-02-11 Remi Despres Dispositif de gestion partagee d'une ressource entre plusieurs utilisateurs
US6170042B1 (en) * 1998-02-24 2001-01-02 Seagate Technology Llc Disc drive data storage system and method for dynamically scheduling queued commands
US6411982B2 (en) * 1998-05-28 2002-06-25 Hewlett-Packard Company Thread based governor for time scheduled process execution
US6253262B1 (en) * 1998-09-11 2001-06-26 Advanced Micro Devices, Inc. Arbitrating FIFO implementation which positions input request in a buffer according to its status
US6253260B1 (en) * 1998-10-22 2001-06-26 International Business Machines Corporation Input/output data access request with assigned priority handling
US6292856B1 (en) 1999-01-29 2001-09-18 International Business Machines Corporation System and method for application influence of I/O service order post I/O request
US6378036B2 (en) * 1999-03-12 2002-04-23 Diva Systems Corporation Queuing architecture including a plurality of queues and associated method for scheduling disk access requests for video content
US6691208B2 (en) * 1999-03-12 2004-02-10 Diva Systems Corp. Queuing architecture including a plurality of queues and associated method for controlling admission for disk access requests for video content
JP3382176B2 (ja) * 1999-03-26 2003-03-04 株式会社東芝 要求処理方法および要求処理装置
US6317808B1 (en) * 1999-03-26 2001-11-13 Adc Telecommunications, Inc. Data storage system and method of routing or assigning disk write requests among a set of disks using weighted available disk space values
US6289376B1 (en) 1999-03-31 2001-09-11 Diva Systems Corp. Tightly-coupled disk-to-CPU storage server
US6874144B1 (en) 1999-04-05 2005-03-29 International Business Machines Corporation System, method, and program for implementing priority inheritance in an operating system
US6374319B1 (en) 1999-06-22 2002-04-16 Philips Electronics North America Corporation Flag-controlled arbitration of requesting agents
US6754736B1 (en) * 1999-06-23 2004-06-22 Fujitsu Limited Information processing apparatus, data inputting/outputting method, and program storage medium therefor
US6651125B2 (en) * 1999-09-28 2003-11-18 International Business Machines Corporation Processing channel subsystem pending I/O work queues based on priorities
US6986137B1 (en) * 1999-09-28 2006-01-10 International Business Machines Corporation Method, system and program products for managing logical processors of a computing environment
US8041754B1 (en) * 2000-01-22 2011-10-18 Intel Corporation Establishing thread priority in a processor or the like
US7103783B1 (en) * 2000-09-29 2006-09-05 Pinion Software, Inc. Method and system for providing data security in a file system monitor with stack positioning
US6834315B2 (en) * 2001-03-26 2004-12-21 International Business Machines Corporation Method, system, and program for prioritizing input/output (I/O) requests submitted to a device driver
US6651158B2 (en) * 2001-06-22 2003-11-18 Intel Corporation Determination of approaching instruction starvation of threads based on a plurality of conditions
US7454600B2 (en) 2001-06-22 2008-11-18 Intel Corporation Method and apparatus for assigning thread priority in a processor or the like
US20030093509A1 (en) * 2001-10-05 2003-05-15 Li Raymond M. Storage area network methods and apparatus with coordinated updating of topology representation
US7155716B2 (en) * 2002-03-08 2006-12-26 Intel Corporation Weighted and prioritized task scheduler
US6839817B2 (en) * 2002-04-24 2005-01-04 International Business Machines Corporation Priority management of a disk array
US9052944B2 (en) 2002-07-16 2015-06-09 Oracle America, Inc. Obstruction-free data structures and mechanisms with separable and/or substitutable contention management mechanisms
US7043567B2 (en) * 2002-07-22 2006-05-09 Seagate Technology Llc Method and apparatus for determining the order of execution of queued commands in a data storage system
US20040024856A1 (en) * 2002-07-30 2004-02-05 Gary Gere Method and system for a services environment management engine
US7065596B2 (en) 2002-09-19 2006-06-20 Intel Corporation Method and apparatus to resolve instruction starvation
US7114029B1 (en) 2002-10-31 2006-09-26 Western Digital Technologies, Inc. Disk drive employing a multi-phase rotational position optimization (RPO) algorithm
US7082494B1 (en) 2002-12-24 2006-07-25 Western Digital Technologies, Inc. Disk drive executing a preemptive multitasking operating system comprising tasks of varying priority
US7421694B2 (en) * 2003-02-18 2008-09-02 Microsoft Corporation Systems and methods for enhancing performance of a coprocessor
US7673304B2 (en) * 2003-02-18 2010-03-02 Microsoft Corporation Multithreaded kernel for graphics processing unit
US7444637B2 (en) * 2003-02-18 2008-10-28 Microsoft Corporation Systems and methods for scheduling coprocessor resources in a computing system
US6947051B2 (en) * 2003-02-18 2005-09-20 Microsoft Corporation Video memory management
US7380247B2 (en) * 2003-07-24 2008-05-27 International Business Machines Corporation System for delaying priority boost in a priority offset amount only after detecting of preemption event during access to critical section
US6987639B1 (en) 2003-09-30 2006-01-17 Western Digital Technologies, Inc. Disk drive modifying a rotational position optimization algorithm based on motor capability of a VCM
US7216021B2 (en) * 2003-10-30 2007-05-08 Hitachi, Ltd. Method, system and computer program for managing energy consumption
US20050138281A1 (en) * 2003-12-18 2005-06-23 Garney John I. Request processing order in a cache
US7061714B1 (en) 2003-12-19 2006-06-13 Western Digital Technologies, Inc. Disk drive modifying estimated seek times for a rotational position optimization algorithm based on change in estimated seek time parameter
US7254685B1 (en) 2004-06-15 2007-08-07 Emc Corporation Method for maintaining high performance while preserving relative write I/O ordering for a semi-synchronous remote replication solution
US20060112301A1 (en) * 2004-11-08 2006-05-25 Broadcom Corporation Method and computer program product to improve I/O performance and control I/O latency in a redundant array
US20060155543A1 (en) * 2005-01-13 2006-07-13 Korg, Inc. Dynamic voice allocation in a vector processor based audio processor
US7281086B1 (en) 2005-06-02 2007-10-09 Emc Corporation Disk queue management for quality of service
US7293136B1 (en) 2005-08-19 2007-11-06 Emc Corporation Management of two-queue request structure for quality of service in disk storage systems
JP2007079789A (ja) * 2005-09-13 2007-03-29 Nec Corp 計算機システム及びイベント処理方法
JP4792335B2 (ja) * 2006-06-16 2011-10-12 富士通株式会社 Ｒａｉｄ装置、ｒａｉｄ制御プログラムおよびキャッシュ管理方法
US8090903B2 (en) * 2008-01-18 2012-01-03 Microsoft Corporation Fair and dynamic disk input/output bandwidth distribution
WO2009113381A1 (ja) 2008-03-11 2009-09-17 日本電気株式会社 マルチプロセッサシステム、マルチプロセッサシステムのｏｓ間デバイス共有方法
US8504736B2 (en) * 2008-05-30 2013-08-06 Sony Computer Entertainment America Inc. File input/output scheduler
US8495403B2 (en) 2008-12-31 2013-07-23 Intel Corporation Platform and processor power management
US8090902B1 (en) 2009-05-22 2012-01-03 Western Digital Technologies, Inc. Disk drive adjusting command execution in response to control circuitry die temperature
US8356131B2 (en) 2009-10-25 2013-01-15 Sony Mobile Communications Ab System and method for controlling interruption of a process in electronic equipment based on priority of the process, and program
US8688880B2 (en) * 2010-06-23 2014-04-01 International Business Machines Corporation Centralized serialization of requests in a multiprocessor system
US8904115B2 (en) * 2010-09-28 2014-12-02 Texas Instruments Incorporated Cache with multiple access pipelines
US8464269B2 (en) * 2010-12-16 2013-06-11 International Business Machines Corporation Handling and reporting of object state transitions on a multiprocess architecture
JP5733680B2 (ja) * 2011-01-20 2015-06-10 日本電気株式会社 コマンド実行装置、コマンド実行システム、コマンド実行方法およびコマンド実行プログラム
US8385354B2 (en) * 2011-07-18 2013-02-26 Telefonaktiebolaget L M Ericsson (Publ) Scalable hardware mechanism to implement time outs for pending POP requests to blocking work queues
CN102739281B (zh) * 2012-06-30 2015-04-15 华为技术有限公司 一种调度的实现方法、装置及系统
US10248463B2 (en) * 2015-02-13 2019-04-02 Honeywell International Inc. Apparatus and method for managing a plurality of threads in an operating system
EP3126998A4 (en) * 2015-02-26 2017-11-29 Strato Scale Ltd. Ordering schemes for network and storage i/o requests for minimizing workload idle time and inter-workload interference
US10649766B2 (en) * 2015-06-05 2020-05-12 Unisys Corporation Dynamic replacement of software components
CN105139641B (zh) * 2015-09-29 2017-11-24 滴滴（中国）科技有限公司 一种基于WiFi中继站的车辆调度方法及系统
US10069949B2 (en) 2016-10-14 2018-09-04 Honeywell International Inc. System and method for enabling detection of messages having previously transited network devices in support of loop detection
KR101915944B1 (ko) * 2017-05-08 2018-11-08 주식회사 애포샤 클러스터 시스템에서의 클라이언트 요청 처리 방법, 상기 클라이언트 요청에 따른 입출력 처리 방법 및 장치
US10810086B2 (en) 2017-10-19 2020-10-20 Honeywell International Inc. System and method for emulation of enhanced application module redundancy (EAM-R)
KR102509487B1 (ko) * 2018-02-13 2023-03-14 에스케이하이닉스 주식회사 메모리 시스템 및 그것의 동작 방법
US10783026B2 (en) 2018-02-15 2020-09-22 Honeywell International Inc. Apparatus and method for detecting network problems on redundant token bus control network using traffic sensor
US10725941B2 (en) 2018-06-30 2020-07-28 Western Digital Technologies, Inc. Multi-device storage system with hosted services on peer storage devices
US10877810B2 (en) * 2018-09-29 2020-12-29 Western Digital Technologies, Inc. Object storage system with metadata operation priority processing
US12112040B2 (en) * 2021-08-16 2024-10-08 International Business Machines Corporation Data movement intimation using input/output (I/O) queue management
CN116737673B (zh) * 2022-09-13 2024-03-15 荣耀终端有限公司 嵌入式操作系统中文件系统的调度方法、设备及存储介质

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2181871A (en) 1985-09-17 1987-04-29 Codex Corp Sequencing of multiple tasks in a data processor

Family Cites Families (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0063186B1 (en) * 1981-03-16 1986-01-22 International Business Machines Corporation Improvements to digital data processing apparatus
US4525780A (en) * 1981-05-22 1985-06-25 Data General Corporation Data processing system having a memory using object-based information and a protection scheme for determining access rights to such information
JPS59188749A (ja) * 1983-04-12 1984-10-26 Toshiba Corp デ−タ転送制御方式
US4635187A (en) * 1983-12-19 1987-01-06 At&T Bell Laboratories Control for a multiprocessing system program process
US4688167A (en) * 1984-09-27 1987-08-18 Wang Laboratories, Inc. Screen manager for data processing system
US4807142A (en) * 1984-10-09 1989-02-21 Wang Laboratories, Inc. Screen manager multiple viewport for a multi-tasking data processing system
US4658351A (en) * 1984-10-09 1987-04-14 Wang Laboratories, Inc. Task control means for a multi-tasking data processing system
US4713754A (en) * 1984-10-09 1987-12-15 Wang Laboratories, Inc. Data structure for a document processing system
US4736318A (en) * 1985-03-01 1988-04-05 Wang Laboratories, Inc. Data processing system having tunable operating system means
JPS6227818A (ja) * 1985-07-30 1987-02-05 Nec Corp 入出力制御方式
US4779194A (en) * 1985-10-15 1988-10-18 Unisys Corporation Event allocation mechanism for a large data processing system
EP0257655B1 (en) * 1986-08-28 1994-07-06 Nec Corporation Multitask processing apparatus
US4980824A (en) * 1986-10-29 1990-12-25 United Technologies Corporation Event driven executive

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2181871A (en) 1985-09-17 1987-04-29 Codex Corp Sequencing of multiple tasks in a data processor

Also Published As

Publication number Publication date
EP0488501A3 (en) 1993-04-21
EP0488501A2 (en) 1992-06-03
JPH04264947A (ja) 1992-09-21
CA2051186A1 (en) 1992-04-27
US5220653A (en) 1993-06-15

Similar Documents

Publication Publication Date Title
JPH04264947A (ja) マルチタスキング・データ処理システム
US6735769B1 (en) Apparatus and method for initial load balancing in a multiple run queue system
US6993767B2 (en) System for preventing periodic load balancing if processor associated with lightest local run queue has benefited from idle processor load balancing within a determined time period
US7913034B2 (en) DRAM access command queuing
JP2002533807A (ja) 割込み／ソフトウエア制御スレッド処理
EP2300910B1 (en) Scheduler instances in a process
EP0732659A1 (en) Controlling (n+i) I/O channels with (n) data managers in a homogeneous software programming environment
US20050015768A1 (en) System and method for providing hardware-assisted task scheduling
US20070156955A1 (en) Method and apparatus for queuing disk drive access requests
US5568635A (en) Physical memory allocation system, program execution scheduling system, and information processor
JPH1091357A (ja) データ格納装置及びデータ格納方法
JPH0820963B2 (ja) 計算機システムを動作させる方法及び計算機システム
US6442648B1 (en) Method of and system for the dynamic scheduling of requests to access a storage system
JP2004078322A (ja) タスク管理システム、プログラム、記録媒体、及び制御方法
US11003495B2 (en) Dynamic access of task queues in a parallel processing system
US7472214B2 (en) Real-time embedded simple monitor method and computer product
CN112650449A (zh) 缓存空间的释放方法、释放系统、电子设备及存储介质
KR20010036644A (ko) 디지털 시그널 프로세서를 위한 실시간 제어 시스템
CN114461365A (zh) 一种进程调度处理方法、装置、设备和存储介质
US7562364B2 (en) Adaptive queue scheduling
US5530871A (en) Asynchronous input and output control system
CN109426562B (zh) 优先级加权轮转调度器
EP2280345A1 (en) A device for and a method of managing computer tasks
CN121263780A (zh) Gpu电路在上下文取消映射期间自上下文保存
WO2004061663A2 (en) System and method for providing hardware-assisted task scheduling