JPH05189251A - 多重タスク処理オペレーティング・システム及びそのコンピュータの動作方法 - Google Patents

多重タスク処理オペレーティング・システム及びそのコンピュータの動作方法

Info

Publication number
JPH05189251A
JPH05189251A JP4177766A JP17776692A JPH05189251A JP H05189251 A JPH05189251 A JP H05189251A JP 4177766 A JP4177766 A JP 4177766A JP 17776692 A JP17776692 A JP 17776692A JP H05189251 A JPH05189251 A JP H05189251A
Authority
JP
Japan
Prior art keywords
thread
program
class
threads
execution
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.)
Granted
Application number
JP4177766A
Other languages
English (en)
Other versions
JP2518998B2 (ja
Inventor
Joel A Farrell
ジョーエル・アラン・ファーレル
Stephen E Record
ステファン・エリオット・レコード
Brian K Wade
ブライアン・キース・ウェイド
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 JPH05189251A publication Critical patent/JPH05189251A/ja
Application granted granted Critical
Publication of JP2518998B2 publication Critical patent/JP2518998B2/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

Landscapes

  • Engineering & Computer Science (AREA)
  • Software Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Devices For Executing Special Programs (AREA)

Abstract

(57)【要約】 【目的】 アプリケーション・プログラムによりプログ
ラム・スレッドの遂行スケジュールに影響を与えてプロ
グラム・スレッドの遂行の最適化を図る。 【構成】 プログラム・スレッドにその優先権レベル及
びタスク指名クラス１６，１８，２０を割当て、オペレ
ーティング・システム１０はパラメータに基づき、各タ
スク指名クラスからの遂行に使用可能な最高優先権スレ
ッドをプロセッサの遂行リスト３２で待機させ、走行リ
ストの最高優先権スレッドを先に遂行し、アプリケーシ
ョン・プログラム・スレッドは他のスレッドが存在する
クラスを変更することができ、遂行するプログラム・ス
レッドは同一タスク指名クラスにある指定したスレッド
に対し任意に先を譲ることができ又はそれ自体使用で
き、走行リストに対する競合状態で、同一タスク指名ク
ラスの最高優先権スレッドを待ち行列で待機させるよう
スケジュールするようにしたことを特徴とする。

Description

【発明の詳細な説明】
【０００１】
【産業上の利用分野】本発明はコンピュータ・オペレー
ティング・システムに関し、特に多重タスク処理オペレ
ーティング・システムの遂行に対するコンピュータ・プ
ログラム・スレッドのスケジューリングに関する。
【０００２】
【従来の技術】単一のタスク処理オペレーティング・シ
ステムは永年の間使用されてきた。そのようなシステム
において、コンピュータ・プロセッサはコンピュータ・
プログラム又はプログラム・サブルーチンを直列に遂行
する。すなわち、前のプログラム又はサブルーチンが終
了するまで次のコンピュータ・プログラム又はプログラ
ム・サブルーチンの遂行は開始することができない。こ
の型のオペレーティング・システムは、遂行するコンピ
ュータ・プログラム又はサブルーチンは外部事象の発生
（データ又は資源が利用可能になる）を待たなければな
らない場合、プロセッサ時間を浪費するため、コンピュ
ータ・プロセッサの最適な使用を行うことができない。
この問題を解決するため、各コンピュータ・プログラム
を１以上のプログラム・スレッド（以下、単にスレッド
とも言う）０又は遂行ストリームに分割した多重タスク
処理又は多重スレッド化オペレーティング・システムが
開発された。そのようなプログラム・スレッドの各々は
特定のタスクを実行する。
【０００３】遂行中のスレッドが外部事象の発生を待た
なければならないと、コンピュータ・プロセッサは一度
に１つのみプログラム・スレッドを遂行することができ
る。すなわち、プログラム・スレッドは“非タスク指名
可能”となるが、非タスク指名可能が延期（Suspend)さ
れると、コンピュータ・プロセッサはそれ自体の使用を
最適化するため、同一又は異なるコンピュータ・プログ
ラムの他のプログラム・スレッドを遂行する。多重タス
ク処理オペレーティング・システムは、同一又は異なる
プログラム・スレッドを他のコンピュータ・プロセッサ
において平行に遂行することができると、その場合も多
重プロセッサ環境に拡張することができる。そのように
して、多重タスク処理オペレーティング・システムは１
以上のプロセッサの使用を最適化することはできるが、
アプリケーション・プログラムの開発者がプログラム・
スレッド遂行のスケジューリングに適切に影響を与える
ようにすることはできない。
【０００４】米国特許第４，３９５，７５７はアプリケ
ーション・プログラムの開発者が利用できる“信号装
置”（semaphone ）と称する情報構造を開示しており、
それは送信装置としてコンピュータの処理と事象又は資
源とを調整又は同期をとるように働く。信号装置は、そ
れらを利用する処理を待っている事象又は資源の存在を
示すか、それに代り、事象又は資源の存在を待っている
処理が存在することを示す。一度に１より多い事象又は
資源、又は処理が存在する場合、それらは、それぞれ事
象又は資源の突合せ、又は処理の突合せを待ちながら待
機するかもしれない。
【０００５】米国特許第４，６５８，３５１号は優先権
レベル及び信号装置を使用する多重タスク処理オペレー
ティング・システムのタスクの調整を開示している。走
行するべく作動可能な全タスクに対して複数のタスク待
ち行列が同一優先権レベルで設定される。タスク制御ブ
ロックはタスクの優先権レベルに対応するタスク待ち行
列に記憶され、各タスクを供給する。明らかに、各タス
ク待ち行列のタスク制御ブロックの順序は、対応するタ
スクが走行可能となった順序に従って定められる。各タ
スクはタスク待ち行列の相対的優先権に基づく順序及び
各タスク待ち行列のタスク制御ブロックの記憶場所に基
づく順序で遂行される。事象送信及びメッセージの進行
は“信号装置”によって操作される。
【０００６】分散型演算システムの第３国際会議議事録
によるジョン・ケー・アウスターフートの“並列システ
ムに対するスケジューリング方式”と称する刊行物（１
９８２年）は異なるクラスに組織されるプログラム・ス
レッドを開示している。時間“スライス”中、１クラス
又は１クラスのタスク指名可能なスレッドの断片からの
全タスク指名可能なプログラム・スレッドが同数のプロ
セッサで同時遂行される。時間スライスの終端におい
て、遂行する全スレッドは、他のタスク指名可能なスレ
ッドによって優先使用される。
【０００７】
【発明が解決しようとする課題】以上説明した方式は、
アプリケーション・プログラムの開発者が遂行順序に影
響を及ぼすことはできるが、更に大きくアプリケーショ
ン・プログラムの開発者が制御できるように改良するこ
とが重要であると思われる。一般に、オペレーティング
・システム開発者及びアプリケーション・プログラム開
発者のどちらにとっても、プログラム・スレッドの遂行
順序に従ってその制御が配置されると、オペレーション
の動作効率は減殺される。理想的には、オペレーティン
グ・システムはアプリケーション・プログラムによって
許されるものと同様に効率良い方法でプログラム・スレ
ッドの遂行をスケジュールするべきである。
【０００８】従って、本発明の目的はプログラム・スレ
ッドの遂行を最適化すると共に、後にアプリケーション
・プログラムが遂行するスケジュールに影響を与えるこ
とができる多重タスク処理オペレーティング・システム
を提供することである。本発明の他の目的は、単一プロ
セッサ及び多重プロセッサ・コンピュータ・システムの
どちらでもオペレーションすることができる上記の型の
多重タスク処理オペレーティング・システムを提供する
ことである。
【０００９】
【課題を解決するための手段】本発明による多重タスク
処理オペレーティング・システムはプログラム・スレッ
ドに対するパラメータを指定することにより、アプリケ
ーション・プログラム（及びその開発者）がアプリケー
ション・プログラムから得られるプログラム・スレッド
の遂行スケジュールに対して、影響を与えることができ
る。そのパラメータは各スレッドの優先権レベル及びそ
のプログラム・スレッドが存在するタスク指名クラスを
示す。これらパラメータに基づき、オペレーティング・
システムは下記方法で遂行するようプログラム・スレッ
ドをスケジュールする。オペレーティング・システムは
プロセッサによる遂行のため、各タスク指名クラスから
遂行のために使用可能な最高優先権プログラム・スレッ
ドを選択する。
【００１０】本発明の一機能によると、アプリケーショ
ン・プログラム・スレッドは他のプログラム・スレッド
が存在するタスク指名クラスを変更することができる。
又、本発明の他の特徴によると、遂行しているプログラ
ム・スレッドは同じタスク指名クラスの特定プログラム
・スレッドに対し任意に先を譲ることができ、又はタス
ク指名クラスの最高優先権使用可能スレッドに対し、そ
れ自体使用可能であり、走行リストに対する競合状態
で、走行リストにおける待機を許容する。これらの両機
能共、アプリケーション・プログラムがプログラム・ス
レッドの遂行スケジュールに対し影響を与えることがで
きる。
【００１１】
【実施例】以下、添付図面に基づき本発明の一実施例を
詳細に説明する。図１は全体的に１０で示した多重タス
ク処理オペレーティング・システムと、共同するコンピ
ュータ・プロセッサ１４ａ−１４ｃ及びアプリケーショ
ン・プログラム１２ａ−１２ｃとを示す。以下の図面に
おいて、同一番号で示すものは同一構成要素とみなすも
のとする。オペレーティング・システム１０は磁気ディ
スク又はテープのようなコンピュータ読出可能な媒体に
遂行可能な形式でプログラムされ、コンピュータ・メモ
リーにロードされ、１以上のＣＰＵで実行されるものが
好ましい。しかし、オペレーティング・システム１０又
はその部分は同等な他のハードウェアによって実施する
こともできる。
【００１２】オペレーティング・システム１０はパーソ
ナル・コンピュータ、本体（仮想計算機及び非仮想計算
機型式）、及びその他のものを含む各種多様な型のコン
ピュータ・システムに使用して、処理間通信、タイミン
グ・サービス、異常終了処理、追跡及び会計機能のよう
な標準機能を実行する。更に、オペレーティング・シス
テム１０は、本発明に基づき、１以上のＣＰＵ１４ａ−
１４ｃの効率良い使用と共に、１以上のアプリケーショ
ン・プログラム１２ａ−１２ｃを構成するアプリケーシ
ョン・プログラム・スレッドの遂行をスケジュールする
ようプログラムされる。オペレーティング・システム１
０は、アプリケーション・プログラムがそれらスレッド
の遂行のスケジュールに実質上影響を与えるようにする
ことが許される。
【００１３】アプリケーション・プログラム・スレッド
を遂行する処理を開始するため、アプリケーション・プ
ログラム１２ａ−１２ｃは各スレッド作成のため一度ス
レッド作成機能１５を呼出し、オペレーティング・シス
テムに対しそれぞれのアプリケーション・プログラムを
構成するスレッドを定義する。各スレッドはそれぞれの
アプリケーション・プログラムから直接得られた１列の
プログラム工程と、プログラム工程による呼出しに応答
してオペレーティング・システム１０から供給された他
のサブルーチンとから成り、１つの共通なストリームに
おいて遂行される。
【００１４】スレッド作成機能に対する呼出しは下記の
パラメータを含む。 １）スレッドの最初の命令のアドレス（このアドレスは
アプリケーション・プログラムがメモリーにロードされ
たときに決定される）。
【００１５】２）スレッドの初期優先権レベル。 ３）スレッドが存在するべきタスク指名クラスの表示。 ４）スレッドが使用又は処理するデータのような他のパ
ラメータ。
【００１６】アプリケーション・プログラム（アプリケ
ーション・プログラム開発者が書いた）はオペレーティ
ング・システム１０の下記原理に基づき各スレッドの優
先権及びタスク指名クラスを選択する。 （１）各タスク指名クラスからの最高優先権使用可能な
（すなわち、非ブロック及び非延期）スレッドを遂行の
ため走行リスト３２で待機させる。 （２）走行リストの最高優先権スレッドが最初に遂行さ
れる。
【００１７】（３）如何なるタスク指名クラスのスレッ
ドでも、同一タスク指名クラスの如何なる他の遂行中の
スレッドに優先使用することはできない。 （４）如何なるタスク指名クラスの非ブロック(Unblock
ed) 及び非延期(Unsuspended) スレッドでも、異なるタ
スク指名クラスの最低優先権遂行スレッドに優先使用す
ることができる。 （５）如何なるタスク指名クラスの遂行中のスレッドで
も、同一又は異なるタスク指名クラスにあるかもしれな
い最高優先権の非ブロック及び非延期スレッドに対する
制御を任意に放棄することができる。
【００１８】（６）遂行中のスレッドはそれ自体をブロ
ック化(Block) し、スレッドが非タスク指名可能状況に
遭遇すると、同一又は異なるタスク指名クラスから他の
スレッドに対する制御を失う。 “優先使用”（preemption）の語は、それ自体がＣＰＵ
の遂行する他のタスク指名可能なスレッドの代りをなす
１スレッドの行為を意味する。タスク指名クラスのスレ
ッドは同一又は異なるアプリケーション・プログラムの
一部であるか、又は１アプリケーション・プログラム内
の処理であるかもしれない。同様に、単一処理のスレッ
ドも異なるタスク指名クラスにあるかもしれない。
【００１９】呼出しに応答して、スレッド作成機能１５
（図５のステップ８６）はオペレーティング・システム
によって使用可能な形式にスレッドを記述するため、ス
レッド状態記述子（ＴＳＤ）１９を作成する。そのスレ
ッドがタスク指名クラスの最初のものであれば、スレッ
ド作成機能は、又スレッドが存在するタスク指名クラス
を記述するため、タスク指名クラス記述子（ＤＣＤ）を
作成する。各スレッドはスレッドを作成したアプリケー
ション・プログラムによって定義したいずれか１つの時
間中、１つのタスク指名クラスに存在する。
【００２０】典型的には、複数のアプリケーション・プ
ログラムを遂行するため、多くのタスク指名クラスが作
成されるが、図１は３クラスのタスク指名クラス１６，
１８，２０を例示する。スレッド作成機能は、又それら
の相対的優先権レベルの順序で各タスク指名クラスにＴ
ＳＤを位置付けし又は連鎖する（ステップ８８）。新た
に作成されたスレッドの優位権がそのクラスに既に存在
する１以上のスレッドの優先権に等しい場合、新たに作
成したスレッドのＴＳＤは同一優位権スレッドのＴＳＤ
の後のタスク指名クラス・リストに配置される。
【００２１】図２に示すように、各ＴＳＤ１９は、スレ
ッド・アドレス、遂行状態、タスク指名クラスの位置
（そのクラスの前及び次のＴＳＤを指定することによ
り）、及びスレッドのタスク指名クラス、優先権レベ
ル、及び状況、すなわち、ブロック、非ブロック、延
期、非延期等を識別する。各ＴＳＤは、又走行リスト３
２を形成するため、走行リスト内の前のＴＳＤ及び走行
リスト３２の次のＴＳＤを識別する。
【００２２】図３に示すように、ＤＣＤは“次”のＤＣ
Ｄを識別して、ＤＣＤと、タスク指名クラスの最高優先
権非ブロックおよび非延期スレッドである“現在”のＴ
ＳＤ（その時、現在と指定される）との間に連係を与え
る。現在のＴＳＤはＣＰＵ１４で現在遂行しているか、
又はＣＰＵが使用可能であるときに、ＣＰＵによる後続
遂行を待ちながら“走行”リスト３２に現在存在するか
のいずれかであるスレッドと識別される。ＤＣＤは、又
タスク指名クラス内の最高及び最低優先権スレッドに向
ける高ポインタ及び低ポインタを識別して、タスク指名
クラスを照会する“アンカー”を与える。
【００２３】図４はＴＳＤの連鎖及びＤＣＤの連係（特
定の順序にではなく）を示す図である。各タスク指名ク
ラス内のＴＳＤのすべてはリストの再順序付けを容易に
するため、二重連鎖に配列され、システム内のＤＣＤの
すべては単一連係方式で共に連係される。
【００２４】走行リスト３２は、ＣＰＵにおける走行の
ため待機している各タスク指名クラスからの現行スレッ
ドで構成される。図６に示すように、スレッドは走行リ
ストの最初及び最後のＴＳＤを示すアンカー３３からの
二重連鎖状態で優先権順に走行リストに配置される。走
行リスト内の２つのスレッドが同一レベルの優先権を持
つ場合、それらは走行リストに到着した時間順に位置付
けされ、後着は先着の後に配置される。
【００２５】以下の本発明の実施例では、各タスク指名
クラスからのスレッドを１度に１つのみ現在実行又は現
行（current ）とすることができることとして記述する
が、本発明の他の実施例においては、下記で詳細に記述
するように、各タスク指名クラスからのスレッドを１度
に１つより多く現行とすることができ、異なるＣＰＵで
同時に遂行することができる。
【００２６】ステップ８６，８８におけるスレッド作成
機能により各スレッドが作成され、タスク指名クラスに
組織された後、スレッド作成機能はスレッドが存在する
タスク指名クラスのＤＣＤを識別するプロモート（Prom
ote)原始機能３４ (図７に示す）を呼び出すことにより
スレッドのスケジューリングを開始する（図５のステッ
プ９２）。本発明のこの実施例においては、各タスク指
名クラスから１度に１スレッドのみを現行とすることが
できるので、図７の決定ブロック９８は、タスク指名ク
ラスからのＴＳＤが現在指定されているか否かを確認す
るため、識別されたタスク指名クラスのＤＣＤを読出す
ステップ１００に進行する。
【００２７】決定ブロック１０２においてイエスであれ
ば、決定ブロック１０００へ進み、現ＴＳＤがタスク指
名可能であれば、プロモート原始機能はそこからステッ
プ１０４へ分岐し、この好ましい実施例では、いかなる
タスク指名クラスのスレッドでも相対的優先権レベルに
関係なく、同一タスク指名クラスの現在流れている現行
スレッドを優先使用することができないから、現ＴＳＤ
を走行リストで待機させる。又、いかなるタスク指名ク
ラスのスレッドでも、同一タスク指名クラスからの他の
スレッドが現在走行している間は走行リストで待機させ
ることはできない。
【００２８】しかし、識別されたタスク指名クラスから
の現行と指定されたスレッドがない場合、プロモート原
始機能は後続する優先権レベル（その連鎖内の順序で）
の識別されたタスク指名クラス内のＴＳＤを読出し、ブ
ロックも延期もされていない最高優先権ＴＳＤを識別す
る（ステップ１０３）。そのようなスレッドが存在する
場合（決定ブロック１００１において）、または現行Ｔ
ＳＤとなり、プロモート原始機能はスケジュール原始機
能３６を呼出し、現行スレッドを識別する（ステップ１
０４）。スケジュール原始機能３６は、スレッドが既に
走行リストにあるか否かを確認する（図８の決定ブロッ
ク１０５）。
【００２９】ノーの場合、スケジュール原始機能は走行
リストに他のＴＳＤがある場合その優先権レベルを再検
討し（ステップ１０６）、走行リストに既に存在する他
のタスク指名クラスからの現行スレッドに対する優先権
順序に従い、現行リストのＴＳＤを走行リストで待機さ
せる（ステップ１０８）。スケジュール原始機能は呼出
機能（すなわち、この場合はプロモート原始機能）に戻
る（ステップ１１０）。プロモート原始機能は、それに
応答して、下記で詳細に記述する現行スレッド・カウン
トを更新して（ステップ１５０）、その呼出機能（この
場合、スレッド作成機能）に戻る。
【００３０】次に、スレッド作成機能はその機能を呼出
したスレッドのＤＣＤを識別するプロモート原始機能を
呼出す（ステップ９４）。図７及び８の各工程又はステ
ップは上記の他のタスク指名クラスのために繰返され
る。オペレーティング・システムはいまだ識別された現
行ＴＳＤを持たない各タスク指名クラスから最高優先権
の非ブロック及び非延期スレッド（ＴＳＤ）を選択し、
スレッド（ＴＳＤ）を現行スレッドとして表わし、走行
リスト３２でそのＴＳＤを待機させる。タスク指名クラ
スが遂行のために使用可能である（非ブロック、非延
期）スレッドを持たない場合、タスク指名クラスは走行
リストに供給されない。
【００３１】今、走行リストが変化したので、走行リス
トのスレッドは現在遂行中のスレッドより高い優先権を
持つことが可能である。故に、走行リストの全スレッド
は現在ＣＰＵに対して競争することが許される。従っ
て、スレッド作成機能は切替原始機能４６を呼出して、
走行リストの最高優先権ＴＳＤの遂行を開始する（ステ
ップ１１６）。切替原始機能の第１のステップは、スレ
ッドが現在ＣＰＵで遂行されているか否かを確認するこ
とである（図９の決定ブロック１１９）。
【００３２】イエスであれば、切替原始機能は共同する
ＣＰＵレジスタの内容を現行遂行中のスレッドのＴＳＤ
に複写することによって、現在遂行するスレッドの遂行
状態を保管する（ステップ１２０）。これらレジスタ
は、プログラム・スレッドが停止したプログラム・ステ
ップを表示し、プログラム・スレッドと共同する記憶デ
ータの位置を示す。この状態情報は後刻プログラム・ス
レッドの遂行再開始に必要である。切替原始機能が呼出
されたとき、ＣＰＵで現在遂行するスレッドがない場
合、決定ブロック１１９はステップ１２０を回避する。
【００３３】次に、切替原始機能は未スケジュール原始
機能３８を呼出し、最高優先権スレッドのＴＳＤを走行
リストから除去する。ステップ１０８において、スケジ
ュール原始機能が予め呼出されたため、上記の最高優先
権スレッドは必然的に走行リストの最初のスレッドとな
る。ＴＳＤが実際に走行リストにあることを照合した後
（図１３の決定ブロック２５６）、未スケジュール原始
機能は、走行リスト・アンカーと走行リストの第２の最
高優先権スレッドとの間の連鎖ポインタを相互に指示す
るよう変更し、最高優先権ＴＳＤを除外することによっ
てそれを除去する（ステップ２５７）。
【００３４】次に、未スケジュール原始機能は呼出機能
に戻り（ステップ２５９）、切替原始機能は走行リスト
から得られたスレッドの遂行状態をＣＰＵレジスタに記
憶し（ステップ１２４）、ＣＰＵがその最後の遂行期間
を通過してそのスレッドの処理を終了した点からＣＰＵ
にスレッドの遂行を再開始させる。これが最高優先権の
スレッドを遂行したか又はタスク指名された最初の場合
であれば、そのスレッドはその開始点から遂行する。
【００３５】以上説明した例は、異なるタスク指名クラ
スからのより高い優先権プログラム・スレッドによって
優先使用されるまで、そのスレッドはＣＰＵで走行し続
けることができるということを例示する。優先使用はプ
ロモート及び切替原始機能が呼出されたときはいつでも
発生することができる。プロモート及び原始機能は現在
遂行するスレッドがタスク指名可能であるときでさえ、
呼出すことができる。
【００３６】しかし、システム内の最高優先権スレッド
が現在ＣＰＵで遂行中であるものと同一のタスク指名ク
ラスからのものであると（この最高優先権スレッドは、
現在遂行するプログラム・スレッドが遂行を開始した後
に作成され、又は使用可能にされるため）、この最高優
先権スレッドは、現在遂行するスレッドがブロック化し
ない場合及びブロック化するまで、走行リストで待機せ
ず、それ自体又は他のプログラム・スレッドにより延期
されるか、又は削除される。これは本発明の目的に従
い、同一タスク指名クラス内のスレッド間を調整するも
のである。
【００３７】遂行スレッドは、それが継続することがで
きるようになるまでに満足しなければならないある状態
を待たなければならないときには、それ自体をブロック
化する。このような場合、同一又は異なるタスク指名ク
ラスの他のタスク指名可能なスレッドを遂行させること
ができ、それがＣＰＵを最適な効率の使用とすることが
できる。例えば、現在遂行するプログラム・スレッドが
待ち行列からデータを得ようとして、オペレーティング
・システム・サービスを実行するルーチンを呼出した
が、そのデータが使用可能でない場合、現在遂行するプ
ログラム・スレッドで遂行しているオペレーティング・
システム・サービス・ルーチンは下記方法により現在遂
行するプログラム・スレッドをブロック化するようプロ
グラムされる。
【００３８】オペレーティング・システム・サービス・
ルーチンはそれ自体を待ち行列で待つスレッドのリスト
に配置し、オペレーティング・システムのブロック原始
機能４５を呼出してそれ自体のスレッドをブロック化す
る。ブロック原始機能４５は、それに応答して、現在遂
行するプログラム・スレッドのＴＳＤにブロック状況フ
ィールドを設定し（図１０のステップ１７２）、タスク
指名クラスに現行スレッドがないということを示すよう
現在遂行するプログラム・スレッドのＤＣＤを更新する
（ステップ１７４）。そこで、ブロック原始機能は新た
にブロック化したスレッドのタスク指名クラスに対する
プロモート原始機能を呼出す（ステップ１７６）。
【００３９】プロモート原始機能は、現在このタスク指
名クラスに対する現行スレッドがないということを示す
ので、ステップ１０３において、ブロック化スレッドと
交換するための使用可能なスレッドを選択しなければな
らない。かくして、プロモート原始機能は、ステップ１
０４において呼出されたスケジュール原始機能４６と協
力して、それがある場合、タスク指名クラスからの非ブ
ロック及び非延期最高優先権プログラム・スレッドを走
行リストで待機させる。しかし、現在遂行するプログラ
ム・スレッドが現在ブロック化されているため、遂行の
ために立候補することができず、その優先権レベルに関
係なく、走行リストに複写することができない。
【００４０】次に、ブロック原始機能４４は切替原始機
能４６を呼出し、上記の方法に従い、ＣＰＵによる遂行
のため、走行リストの最高優先権スレッドを選択する。
現在遂行するスレッドのＴＳＤが現在走行リストにない
ため、後続遂行するためのスレッドを選択することがで
きず、ステップ１２０において、ＣＰＵから除去され
る。ブロック化されたものと同一のタスク指名クラスか
らの他のスレッドがその走行リストの最高優先権スレッ
ドであるかもしれず、その場合、それを遂行することが
できる。
【００４１】他のスレッドが後で待ち行列に対するデー
タを発生する場合、それは待ち行列のデータを待つプロ
グラム・スレッドのリストを検査する。そこで、データ
を発生したスレッドは待ち行列の待ちリストから待ちス
レッドを除去し、ブロック化した待ちスレッドのＴＳＤ
を識別する非ブロック原始機能４８を呼出すことによっ
て待ちスレッドを非ブロックにする。非ブロック原始機
能は、それに応答して、待ちスレッドＴＳＤ標識のブロ
ック表記を除去するよう変更し（図１１のステップ２０
７）、非ブロックスレッドのＴＳＤを検査することによ
り、現在非ブロック待ちスレッドのＴＳＤ（ＤＣＤに対
するポインタを含む）が存在するタスク指名クラスを確
認する（ステップ２０８）。
【００４２】次に、非ブロック原始機能は現在非ブロッ
クのスレッドのＤＣＤを識別するプロモート原始機能を
呼出す（ステップ２１０）。このときタスク指名クラス
が現行スレッドを持たない場合、上記の現在非ブロック
のスレッドか、又は同一タスク指名クラスからのより高
い優先権の非ブロック及び非延期スレッドを走行リスト
に複写する。プロモート原始機能から返信を受けた後、
非ブロック原始機能４８はデータを発生したスレッドの
タスク指名クラスを決定し（ステップ２１２）、プロモ
ート原始機能３４を呼出してデータを発生したスレッド
のタスク指名クラスを開始する（ステップ２１４）。
【００４３】プロモート原始機能３４が非ブロック原始
機能に戻った後、非ブロック原始機能は切替原始機能４
６を呼出して（ステップ２２０）、上記の方法に従い、
走行リストかＣＰＵのどちらかにある最高優先権スレッ
ドを遂行する。切替原始機能が非ブロック原始機能に戻
った後、非ブロック原始機能はその呼出機能（データ発
生スレッド）に戻る（ステップ２２１）。
【００４４】前述のように、ブロック原始機能は、資源
が使用可能になるか又は資源における他の事象の発生を
スレッドが待たなければならない場合、現在遂行するス
レッドで遂行しているサービス・ルーチンによってそれ
を呼出すことができる。スレッドは、又それ自体又は他
のスレッドによって、スレッドの遂行を停止するか、防
止するため、“延期”にすることができる。
【００４５】延期の目標であるスレッドは現在ＣＰＵで
遂行していることができ、ブロック状況か、非ブロック
状況にあり、及び走行リストに存在するか、又はタスク
指名クラス内の他の場所に存在してもよい。延期は同一
又は低い優先権を有する他のスレッドによってＣＰＵを
共用させるか、又は他の目的のために使用することがで
きる。例えば、ビデオ・スクリーンを更新するスレッド
はフレームを“凍結”するため延期することができる。
【００４６】各ＴＳＤはＴＳＤによって示される目標ス
レッドの延期を要求するプログラム・スレッドの数を示
す“延期カウンタ”フィールドを含む。そのカウンタが
０より大きい場合、ＴＳＤによって示されたスレッドが
延期される。
【００４７】プログラム（“延期する”）スレッドが目
標スレッドの延期を希望したとき、延期するスレッドは
目標スレッドの識別と共に図１２に示すスレッド延期(T
hreadSuspend) 機能５０を呼出す。最初、スレッド延期
機能は目標スレッドのＴＳＤの延期カウンタを増分する
（ステップ２５２）。延期するスレッドがそれ自体延期
していないと（決定ブロック２５３）、スレッド延期機
能は、目標スレッドが延期するスレッドと同一のタスク
指名クラスにあるか否かを確認する（決定ブロック２５
４）。イエスであれば、スレッド延期機能は未スケジュ
ール原始機能を呼出して（ステップ２５５）、それが走
行リストにある場合、その目標スレッドを走行リストか
ら除去する（図１３のステップ２５７及び決定ブロック
２５６）。
【００４８】目標スレッドは後に詳細に記述するよう
に、本発明による共同スケジューリング多重プロセッサ
の実施例による走行リストに存在することができるのみ
である。目標スレッドが同一タスク指名クラスにない場
合、決定ブロック２５４は、目標スレッドが現在ＣＰＵ
で遂行しているか否か（再び、多重プロセッサの実施例
において）をスレッド延期機能が確認する決定ブロック
２５８へ導く。ノーの場合、スレッド延期機能５０は目
標スレッドを識別する未スケジュール原始機能３８を呼
出し、目標スレッドが走行リストにある場合、目標スレ
ッドを走行リストから除去する（ステップ２５９）。
【００４９】スレッド延期機能は、返信を受けた後、目
標スレッドが現在そのクラスにあるか否かを確認し（決
定ブロック２６４）、イエスであれば、目標スレッドの
ＤＣＤの現行ＴＳＤフィールドを変更して現在スレッド
がないことを表示する（ステップ２６０）。次に、スレ
ッド延期機能はプロモート原始機能３４を呼出して、目
標スレッドのタスク指名クラスを開始する（ステップ２
６１）。目標スレッドが現在延期中であるから、延期も
ブロック化もしていない目標スレッドのタスク指名クラ
ス内の最高の次に高い優先権スレッドが現行となる。
【００５０】次に、プロモート原始機能はスケジュール
に原始機能を呼出して、延期スレッドのタスク指名クラ
スからの新たな現行スレッドを走行リストに複写する。
プロモート原始機能から返信を受けた後、スレッド延期
機能５０はプロモート原始機能を呼出し、目標スレッド
のタスク指名クラスからの新たなスレッドがより高い優
先権を所有するかもしれないので、延期するプログラム
・スレッドのタスク指名クラスを開始する（ステップ２
６２）。そこで、スレッド延期機能は切替原始機能を呼
出す（ステップ２６３）。
【００５１】再び、決定ブロック２５３に戻り、延期す
るスレッドがそれ自体を延期している場合、スレッド延
期機能は未スケジュール原始機能を呼出して、走行リス
トからそのＴＳＤを除去する。スレッド延期機能のＴＳ
Ｄが走行リストにあるべきではないが、そのステップは
保護のためである（ステップ２６５）。次に、スレッド
延期機能はそれ自体のＤＣＤの現行ＴＳＤフィールドを
変更して、スレッドが現在ないことを示し（ステップ２
６６）、それ自体のクラスを開始して（ステップ２６
７）、切替原始機能を呼出す（ステップ２６８）。
【００５２】延期したスレッドは走行することができな
いため、それ自体の延期カウンタ・フィールドを減分す
ることができない。それ故、延期したカウンタ・フィー
ルドを減分するには他のプログラム・スレッドに頼らな
ければならない。この、他のスレッドがＣＰＵ１４にお
いて走行し、延期スレッドの再開始を希望するときはス
レッド再開始機能５２を呼出して、延期スレッドを識別
する。スレッド再開始機能５２は、それに応答して、延
期したプログラム・スレッドのＴＳＤの延期カウンタ・
フィールドを減分する（図１４のステップ３０２）。
【００５３】カウントの値が０より大であると（決定ブ
ロック３０４）、スレッド再開始機能５２は現在遂行す
るプログラム・スレッドに戻る（ステップ３０６）。し
かし、延期カウンタ・フィールドが現在０カウント値を
示している場合、スレッド再開始機能５２はプロモート
原始機能３４を呼出して、以前延期したスレッドのタス
ク指名クラスを開始し、それによって再開始スレッドが
現行となるよう変更を行う（ステップ３０８）。
【００５４】スレッド再開始機能５２は、返信を受けた
後、プロモート原始機能を呼出して、現在遂行するプロ
グラム・スレッドのタスク指名クラスを開始する（ステ
ップ３１０）。再開始したスレッドは再開始するスレッ
ドより優先権が高いかもしれないので、スレッド再開始
機能５２は切替原始機能４６を呼出して（ステップ３１
２）、上記の方法に従い、最高優先権スレッドを走行リ
スト又はＣＰＵで遂行し、呼出機能に戻る（ステップ３
０６）。
【００５５】いずれにおいても常に注意するべきである
ように、現在遂行するプログラム・スレッドは他の機能
１５，４８，５０，５２，６０のいずれかによって行わ
れるプロモート及び切替機能の呼出しに従い、他のタス
ク指名クラスの他のより高い優先権を有するスレッドに
よって優先使用されることが可能である。
【００５６】スレッドが遂行を完了したとき、直接スレ
ッド削除機能６０を呼出すか、又はスレッド削除機能を
呼出すオペレーティング・システムに戻るか、どちらか
を行うことができる。スレッド削除機能６０は、その呼
出しに応答して、目標スレッドのＴＳＤを捜索し（図１
５のステップ４００）、呼出しているスレッドがそれ自
体を削除するか否かを確認する（決定ブロック４０
１）。
【００５７】イエスの場合、スレッド削除機能は、削除
するスレッド、又は目標スレッドが削除を開始したか
（又は、下記で述べるように、他のスレッドがスレッド
削除機能を呼出すようスレッドに強制したか）否かを確
認する（決定ブロック４０２）。他のスレッドが削除を
開始した場合、スレッド削除機能は開始したスレッドが
それ自体をブロック化するのを待ち（ステップ４０
３）、スレッド削除の通知を要求するすべての中核サブ
システムを呼出す（ステップ４０４）。
【００５８】次に、スレッド削除機能は目標ＴＳＤが存
在するタスク指名クラスからそれを除去する（ステップ
４０８）。タスク指名クラスが現在空きの場合（決定ブ
ロック４１０）、スレッド削除機能は同様にＤＣＤを割
振り解除する（ステップ４１２）。タスク指名クラスが
空きでない場合、スレッド削除機能は目標スレッドのタ
スク指名クラスに対するプロモート原始機能を呼出し
て、目標スレッドのタスク指名クラスからの他のスレッ
ドが現行となることを許容する（ステップ４１４）。返
信を受けた後、スレッド削除機能は関連する処理を構成
するスレッドのリストから目標スレッドのＴＳＤを除去
する（ステップ４１５）。
【００５９】削除されるスレッドが削除を開始した場合
（決定ブロック４１６）、スレッド削除機能は切替原始
機能を呼出して、他のスレッドを遂行する（ステップ４
１８）。しかし、他のスレッドが削除を開始した場合、
開始したスレッドのＴＳＤのブロック標識をリセット
し、プロモート原始機能を呼出して、切替原始機能を呼
出す前に開始したスレッドのタスク指名クラスでオペレ
ーションを行う。
【００６０】再び、決定ブロック４０１に戻り、削除の
目標とされるスレッドが呼出すスレッドではないが、そ
の代り、目標スレッドがあるＣＰＵで遂行中であるか、
又は現行でない場合（決定ブロック４６８）、スレッド
削除機能は削除するスレッドの識別を目標スレッドのＴ
ＳＤに記憶して（ステップ４１９）、目標スレッドの状
況を非ブロック及び非延期に変更する。それがそれぞれ
ブロック及び延期であった場合（ステップ４２０）、目
標スレッドが通常遂行を再開始する場所を示すフィール
ドの代りにスレッド削除機能のステップ４００の位置を
示すというように、目標スレッドの遂行状態を変更する
（ステップ４２１）。次に、スレッド削除機能は目標ス
レッドを未スケジュールにし（ステップ４２２）、目標
スレッドの優先権を格上げする。
【００６１】次に、スレッド削除機能は目標スレッドの
タスク指名クラスに対するプロモート原始機能を呼出し
（ステップ４２４）、終了を早くするため、呼出しスレ
ッドの優先権を格上げする（ステップ４２５）。次に、
スレッド削除機能はブロック原始機能４５を呼出し、削
除の完了を待つそれ自体をブロック化し（ステップ４２
８）、呼出すスレッドの優先権を記憶する（ステップ４
２９）。ステップ４２０−４２８の効果は、目標スレッ
ドをＣＰＵに進めて直ちに遂行させることである。遂行
を開始する際、ＣＰＵは上記のステップ４０４−４１８
の遂行を進行するが、考察するべき追加事項は、目標ス
レッドはそれ自体を削除する前に削除するスレッドを非
ブロックにしなければならないことのみである。
【００６２】オペレーティング・システム１０は、又ス
レッドの優先権を調節するために呼出すことができるス
レッド・セット優先権機能５５を含む。スレッド・セッ
ト優先権機能は、呼出しに応答して、０に等しいパラメ
ータ“ｆ”を設定し（ステップ５０１）、目標スレッド
が走行リストにあるか否かを確認する（決定ブロック５
０３）。イエスの場合、スレッド・セット優先権機能は
パラメータ“ｆ”を増分する（ステップ５０５）。次
に、その機能は“ｆ”を検査し（決定ブロック５０
７）、ｆ＝１であれば、目標を未スケジュールにする
（ステップ５０９）。次に、スレッド・セット優先権機
能はＴＳＤの優先権フィールドを呼出機能によって指定
されたレベルに変更し（ステップ５１１）、スレッドが
走行リストにあった場合（決定ブロック５１２）、目標
をスケジュールし（ステップ５１３）、呼出機能をスケ
ジュールし（ステップ５１５）、切替原始機能を呼出す
（ステップ５１７）。
【００６３】オペレーティング・システム１０は、又図
１７に示すスレッド・セット・タスク指名クラス機能５
３を含み、それ自体により呼出すスレッドをタスク指名
クラスに配置するか、又は他のスレッドを呼出すスレッ
ドと同一のタスク指名クラスに配置することができる
（決定ブロック６００）。前者の場合、スレッド・セッ
ト・タスク指名クラス機能は連鎖ポインタを変更するこ
とにより、呼出すスレッドの現行タスク指名クラスから
呼出すスレッドを除去し（ステップ６０２）、この現行
タスク指名クラスに対するプロモート原始機能を呼出し
（ステップ６０４）、新タスク指名クラスを作成し（ス
テップ６０６）、連鎖ポインタを変更することにより呼
出すスレッドのＴＳＤをタスク指名クラスに配置し（ス
テップ６０８）、新タスク指名クラスに対するプロモー
ト原始機能を呼出し（ステップ６１０）、最後に、切替
原始機能を呼出す（ステップ６１２）。
【００６４】後者の場合、スレッド・セット・タスク指
名クラス機能は目標スレッドの現行タスク指名クラスか
ら目標スレッドを除去し（ステップ６１４）、連鎖ポイ
ンタを変更することによって、この現行タスク指名クラ
スに対するプロモート原始機能を呼出し（ステップ６１
６）、未スケジュール原始機能を呼出すことにより走行
リストから（そこに待機している場合）目標スレッドの
ＴＳＤを除去し（ステップ６１８）、呼出すスレッドの
タスク指名クラスに対して目標スレッドのＴＳＤを加え
（ステップ６２０）、呼出すスレッドのタスク指名クラ
スに対するプロモート原始機能を呼出して（ステップ６
２２）、最後に切替原始機能を呼出す（ステップ６１
２）。
【００６５】オペレーティング・システム１０は、又そ
れ自体を延期又はブロック化することなく、又は非タス
ク指名可能となることなく、現在遂行するプログラム・
スレッドに対しＣＰＵの制御を放棄することを許す。現
在遂行するスレッドはスレッド譲与（ThreadYield)機能
を呼出して、スレッドＩＤで表示するそのクラスの特定
のスレッドが現行となること、又はそのタスク指名クラ
スの最高優先権の使用可能なスレッド（まだそれ自体で
あるかもしれない）が現行となることを要求することが
できる。
【００６６】後者の場合、スレッド譲与機能に対する呼
出しは、タスク指名クラスからの最も重要な作業（スレ
ッド）の遂行の許可を意図するものである。しかし、ど
ちらの場合も、スレッド譲与機能に対する呼出しは、タ
スク指名クラスの特定のスレッドか又は最高優先権のタ
スク指名可能なスレッドが直ちに遂行されることを保証
するものではなく、単に選ばれたスレッドが直ちに現行
となるのみである。
【００６７】アプリケーション・プログラムの開発者
は、同一タスク指名クラスの他のスレッドが遂行するべ
きであるプログラム・スレッドの如何なる点においても
スレッド譲与機能に対する呼出をコーディングすること
ができる。例えば、プログラム・スレッドが長走行であ
り、他のより高い優先権スレッドが長走行スレッドの遂
行中に使用可能になる可能性がある場合、長走行スレッ
ドはスレッド譲与機能に対する呼出しを含むことができ
る。
【００６８】図１８はスレッド譲与機能６１を示す図で
ある。呼出しを受けた後、スレッド譲与機能は、呼出し
が現行となるべきものと同一のクラスの特定（目標）の
プログラム・スレッドを指定するか否かを確認する（決
定ブロック７００）。イエスであれば、スレッド譲与機
能は、目標スレッドが同一のタスク指名クラスにあるこ
と（決定ブロック７０２）、及び目標スレッドが使用可
能又はタスク指名可能であること（決定ブロック７０
４）を検査する。
【００６９】両検査において真実の場合、スレッド譲与
機能は対応するＤＣＤの現行スレッド・フィールドを設
定して目標スレッドのＴＳＤを示し（ステップ７０
６）、目標スレッドのクラスを開始し（ステップ７０
８）、及び切替原始機能を呼出す（ステップ７１０）。
かくして、指定した目標スレッドは走行リストにプロモ
ートし、現在遂行するスレッドは切替原始機能が呼出さ
れたときには走行リストにないため、ＣＰＵから除去さ
れ、走行リストの最高優先権スレッドが遂行される。走
行リストのこの最高優先権スレッドは目標スレッドであ
ってもなくてもよい。
【００７０】再び、決定ブロック７００に戻り、スレッ
ド譲与機能に対する呼出しが特定の目標スレッドを指定
しない場合、スレッド譲与機能はＤＣＤの現行スレッド
・フィールドを０に設定し（ステップ７１２）、ステッ
プ７０８及び７１０へ飛越して、それぞれクラスをプロ
モートし、切替原始機能を呼出す。かくして、タスク指
名クラスの最高優先権使用可能スレッドは走行リストで
待機し、ＣＰＵを争う。スレッド譲与機能を呼出したス
レッドが最高優先権を持つ場合、このスレッドはまだ使
用可能であるため、現行とされる。
【００７１】本発明は、又複数のＣＰＵ１４ａ，１４
ｂ，１４ｃを利用して、同時に複数のプログラム・スレ
ッドを遂行することができる。複数ＣＰＵを使用するた
め、如何なるときも、１度に１つのＣＰＵのみが特定の
データ構造（ＴＳＤ，ＤＣＤ、又は走行リスト）を操作
することができることを保証する必要がある。さもない
と、無効のデータ構造を生じさせるかもしれない。従っ
て、１つのＣＰＵで走行するプログラム・スレッドはデ
ータ構造の操作を要求する場合、該データ構造に対する
ロック（Lock) を獲得するか、設定する。
【００７２】競合状態を避けるべく、ロックを１命令サ
イクルで取得するため、公知の比較及びスワップ命令を
使用する。それを設定したプログラム・スレッドによっ
てロックがリセットされるまで、他のＣＰＵで走行する
他のプログラム・スレッドはそのデータ構造を操作する
ことができない。読出モード・オペレーションにおい
て、このロックは他のプログラム・スレッドに対しデー
タ構造を読出すことはできるが更新を許さない読出モー
ドとして認識される。書込モード・オペレーションにお
いて、このロックはロック付データ構造の他の読出機能
又は書込機能によるアクセスを禁止する書込モードとし
て認識される。
【００７３】これらの形式のロッキング構造は公知であ
る。図１の実施例においては、すべてのＴＳＤ及びＤＣ
Ｄに対して１つの“スレッド”・ロックがあり、全走行
リストに対しては他の“スレッド”・ロックがある。そ
の結果、いずれかのＣＰＵで走行するプログラム・スレ
ッドがこれらの形式のデータ構造のいずれかに対するス
レッド・ロックの制御を取得した場合、いずれのＣＰＵ
で走行する他のプログラム・スレッドでもデータ構造の
いずれをも操作することはできない。
【００７４】ロックは上記の機能４５，４８，５０，５
２，６０に対して要求され、共同する原始機能３４，３
６，３８，４６が完了するまで維持される。多重プロセ
ッサ・オペレーションにおいて、すべての機能及び原始
機能は、切替、停止、及びスレッド削除の各機能を除
き、上記のように遂行される。
【００７５】切替原始機能４６が機能又はＣＰＵの１つ
で遂行する原始機能によって呼出されたときはいつで
も、切替原始機能はそれに応答して、呼出すスレッドの
ＣＰＵにおける遂行のため、走行リストから最高優先権
スレッドを供給する。その結果、走行リストからの複数
のスレッドが複数（Ｎ）のＣＰＵ１４において同時に遂
行することができる。
【００７６】Ｎ個のＣＰＵの各々が常に遂行するべきス
レッドを持つことを保証するため、システムは、各々が
最低優先権の１“空”スレッドを確実に含むようにした
Ｎ個のタスク指名クラスの特別セットを保持する。それ
らは、各タスク指名されたとき、これらスレッドは後述
するように他のＣＰＵによって割込みがかけられるま
で、ＣＰＵを遊休とするようプログラムされ、その後、
それらはプロモート及び切替機能を呼出して、空スレッ
ドの代りに遂行するＣＰＵのための生産スレッドを取得
する。
【００７７】延期又はスレッド削除機能の目標スレッド
はその目標スレッドを延期するか削除することを希望す
るときに、現在、まだ他のＣＰＵで遂行しているかもし
れないという別の問題もある。目標スレッドがもはや遂
行していないということを確認するまで、延期スレッド
の遂行を停止する必要がある。かくして、スレッド延期
機能は、目標スレッドが現在遂行しているか否かを確認
するため、目標スレッドのＴＳＤのプロセッサＩＤフィ
ールドを検査する（図１２の決定ブロック２５８）。ノ
ーの場合、スレッド延期機能は上記のように、単一プロ
セッサ環境において、目標スレッドを延期する。
【００７８】しかし、目標スレッドが現在多重プロセッ
サの実施において遂行している場合、スレッド延期機能
は目標スレッドのＣＰＵに対し割込みを送信して切替原
始機能を呼出す（ステップ２７２）。目標スレッドのＣ
ＰＵは、それに応答して、切替原始機能を呼出す割込コ
ードを走行する。スレッド延期機能は目標ＴＳＤのプロ
セッサＩＤフィールドにおいて、目標スレッドがもはや
遂行していないということを表示するのを待つ（ステッ
プ２７４）。そこで、スレッド延期機能はステップ２５
９に進み、前述の如き処理を続行する。
【００７９】スレッド削除機能が多重プロセッサ環境下
で呼出されたとき、スレッド削除機能は、ＴＳＤのプロ
セッサＩＤフィールドを読出すことによって、目標スレ
ッドが他のＣＰＵで現在遂行しているか否かの確認を行
う（図１５の決定ブロック４６８）。イエスであれば、
スレッド削除機能は目標スレッドのＣＰＵに対し割込み
を送信する（ステップ４７０）。割込みはそれ自体をブ
ロック化する目標スレッドに対する要求を含む。割込処
理機能はブロック(Block) 原始機能を呼出すことによ
り、要求に従うようプログラムされる。他方、スレッド
削除機能は目標スレッドのＴＳＤのプロセッサＩＤフィ
ールドを待つ（ステップ４７２）。目標スレッドがブロ
ック化された後、スレッド削除機能は上記のステップ４
０４に進行する。
【００８０】複数プロセッサ１４ａ−１４ｃを利用する
上記のオペレーション・モードは各タスク指名クラスか
ら１度に１スレッドのみを走行することを許す。これ
は、各タスク指名クラスに供給する優先使用規則を尊重
する一方、別のタスク指名クラスからの複数スレッドが
複数ＣＰＵで同時に走行することを可能にする。しか
し、本発明の他のオペレーション・モードでは、同一タ
スク指名クラスからの複数プログラム・スレッドが同時
に走行することを許容する。
【００８１】このオペレーション・モードにおいては、
アプリケーション・プログラムがタスク指名クラスを作
成するとき、そのアプリケーション・プログラムは同時
走行が許されているタスク指名クラスからの最大数のプ
ログラム・スレッドを指定する。この最大数は“最大現
行スレッド数”フィールドとしてＤＣＤ（図３）に記憶
される。ＤＣＤは、又現行ＴＳＤのリストと、現行スレ
ッドの数と、全スレッドに対するアンカーとを含む。
【００８２】例えば、スレッド作成、ブロック、非ブロ
ック、延期、再開始又はスレッド削除機能のようなタス
ク指名クラスに影響を与えるものを変更した後、プロモ
ート原始機能を呼出し、ＤＣＤからの最大現行スレッド
数、現行スレッドの数、現行スレッドのリストの読出し
に進む（図７の決定ブロック９８及びステップ１４
０）。現行スレッドが最大現行スレッド数より少い場合
（決定ブロック１４２）、プロモート原始機能３４は最
高優先権を有する１以上の追加の非ブロック及び非延期
プログラム・スレッドを選択して、現行スレッドをその
合計数が最大現行スレッド数と等しくなるように設定す
る（ステップ１４４）。
【００８３】次に、プロモート原始機能３４は、上記の
如く、ステップ４でスケジュール原始機能３６を（各追
加のスレッドに対して１回）呼出し、それらの追加ＴＳ
Ｄを走行リストに複写する。最後に、プロモート原始機
能３４は現行スレッドのフィールド数を更新し、現行ス
レッドの数を等しくして（ステップ１５０）、呼出機能
に戻る（ステップ１１２）。
【００８４】オペレーティング・システム１０の他の実
施例において、最少及び最大両プロセッサ・カウントに
よって各タスク指名クラスを特徴ずけることができる。
最少プロセッサ・カウントは、そのクラスのタスク指名
されるべき同時に遂行可能なスレッドに対して使用可能
でなければならないプロセッサの最少数を規定する。最
少数のプロセッサがこのクラスのスレッドに対して使用
可能でない場合、そのクラスのメンバーは走行が許され
ない。
【００８５】最大プロセッサ・カウントは、クラスのメ
ンバーの同時走行が許される最大プロセッサ数を指定し
て、そのクラスのスレッドの並列遂行の程度を制限す
る。最大プロセッサ・カウントが１の場合、クラスのメ
ンバーは明示の順序付けを伴う“共用ルーチン”のよう
に振舞い、最少のプロセッサ・カウントがクラスの大き
さに等しい場合、そのクラスは保証付共用スケジューリ
ングを持つ“任務部隊”として見ることができる。
【００８６】下記フィールドは最少及び最大プロセッサ
・カウントの属性を実施するため、各ＤＣＤに対して加
えられる。 ｍ−このクラスに対する最少プロセッサ・カウント；Ｍ
−このクラスに対する最大プロセッサ・カウント；ｘ−
この現在遂行するクラスからのスレッドの数；ｓ−この
（セッション）走行リスト３２におけるこのクラスから
のスレッドの数；ｃ−このクラスに対するクラス走行リ
スト７９８におけるスレッドの数。
【００８７】このクラス走行リストは走行リスト３２に
対し、類似して構成される追加の走行リストであり、最
少プロセッサ・カウントが１より大きいタスク指名クラ
スからのＴＳＤの収集に対するステージング・グラウン
ド（又は通過基地）として作用する。ＴＳＤはスレッド
の最少プロセッサ・カウントがセッション走行リストに
プロモートされ、スケジュールされるまでクラス走行リ
ストに集積される。
【００８８】上記変数及びパラメータの可能性ある値に
関する制約は下記の如きものである。 1 ＜＝ m ＜＝ 最少（M ，プロセッサの数）；x
＝ 0 又は m ＜＝ x ＜＝ M のどちら
か；x ＝ 0 の場合、 s ＝ 0 又は m ＜
＝ s ＜＝M のどちらか；x ＞ 0 の場合、
0 ＜＝ s ＜＝ M−ｘ；x ＝ 0 及び ｓ＝０
の場合、 ０ ＜＝ c ＜ m ；0 ＜ ｓ ＜
M−x の場合、 c ＝ 0 である。
【００８９】１より大きい最少プロセッサ・カウントを
持つタスク指名クラスに対するそのクラスの走行リスト
において、ＴＳＤを待期する処理を始めるためにプロモ
ート原始機能が呼出される。オペレーティング・システ
ム１０のこの実施例において、図７のステップ９８は、
最大現行数フィールドが最大プロセッサ・カウントに等
しく、１より大きいため、ステップ１４０に進む。ＤＣ
Ｄはステップ１４０において読出され、決定ブロック１
４２に進む。
【００９０】決定ブロック１４２において、現行スレッ
ドが最大プロセッサ・カウントより少いか否かの質問が
行われる。この“現行スレッド”の語は、クラス走行リ
ストのスレッドを加えた下記のようなセッション走行リ
ストから連鎖しているスレッドが加えられたセッション
走行リストのスレッドを意味する。現行スレッドが最大
プロセッサ・カウントより少い場合、追加の使用可能な
スレッドが現行として識別される（ステップ１４４）。
そこで、変更スケジュール原始機能５３ (図１９に例
示）は各追加の使用可能なスレッドのため、原スケジュ
ール原始機能の代りに呼出される（ステップ１４３）。
【００９１】決定ブロック８０２において、変更スケジ
ュール原始機能はｘ＝０及びｓ＝０かどうか、すなわ
ち、ＣＰＵで遂行しているか、又はセッション走行リス
ト３２で待機しているか、いずれかの状態のタスク指名
クラスからのスレッドがないか否かを確認する。ｘ＝０
及びｓ＝０であれば、変更スケジュール原始機能はクラ
ス走行リスト７９８に使用可能なＴＳＤの１つを待機さ
せ（ステップ８０４）、パラメータＣを増分する（ステ
ップ８０６）。クラス走行リストのＴＳＤの数が最少プ
ロセッサ・カウントより少い場合、決定ブロック８０８
は変更スケジュール原始機能の終了へ導く。
【００９２】上記の如く、遂行のため使用可能なタスク
指名クラスの各スレッドに対し、プロモート原始機能が
変更スケジュール原始機能を呼出し、これらのＴＳＤの
最初のｍ−１のためにステップ８０２−８０６が繰返さ
れる。変更スケジュール原始機能によってスケジュール
される次のＴＳＤのため、決定ブロック８０８は、後に
記述するように、変更スケジュール原始機能がセッショ
ン走行リスト３２のクラス走行リスト７９８を表わすス
テップ８１０に進み（ステップ８１０）、ｃに等しいパ
ラメータｓを設定し（ステップ８１２）、０に等しいパ
ラメータｃを設定し（ステップ８１４）、タスク走行リ
ストからセッション走行リストに対しこの代表的な伝送
を反映する。
【００９３】クラス走行リストからの１ＴＳＤがセッシ
ョン走行リストに待機したか、又はこのような１以上の
ＴＳＤが遂行し始めた後、及び他のＴＳＤがプロモート
した後、決定ブロック８０２は決定ブロック８１６に進
み、変更スケジュール原始機能は、このタスク指名クラ
スからの遂行するスレッドの数（存在する場合）とセッ
ション走行リストのこのタスク指名クラスからのスレッ
ドの数とを加えた数が最大プロセッサ・カウントより少
いか否かを確認する。
【００９４】イエスの場合、変更スケジュール原始機能
はこの最終ＴＳＤをセッション走行リスト３２に直接待
機させ（ステップ８１８）、この待合わせ又は待機に反
映するようパラメータｓを増分する（ステップ８２
０）。このタスク指名クラスからのセッション走行リス
トのスレッドの数と遂行するスレッドの数とが最大プロ
セッサ・カウントに等しくなるまで、ステップ８１８及
び８２０は同一タスク指名クラスからプロモートした各
追加のＴＳＤに対して繰返えされる。
【００９５】後にプロモートしたＴＳＤは（最大プロセ
ッサ・カウントが得られた後）クラス走行リストで待機
し（ステップ８２２）、パラメータｃは増分する（ステ
ップ８２４）。クラス走行リストからのＴＳＤがステッ
プ８１０及び８２２のセッション走行リストに表わす方
法は下記の如くｘ及びｓの値による。
【００９６】ａ．ｘ＝０ 及び ｓ＝ｍ の場合、ｍ個
の走行可能なＴＳＤの最低優先権のみが走行リストに現
われ、残るｍ−１個のＴＳＤはそれから連鎖される。こ
の構造は上記のステップ８１０の結果構成される。連鎖
ＴＳＤはセッション走行リストの一部とみなされ、切替
原始機能はこれら連鎖ＴＳＤを遂行するものとみなす。
この最低優先権スレッドが走行リストの最高優先権スレ
ッドであり、ＣＰＵがそれに対して使用可能になったと
きは、代表的なものから連鎖されている他のｍ−１個の
より高い優先権を有するスレッドはｍ−１個の低優先権
を有する他の遂行するスレッドを優先使用する。
【００９７】ｂ．ｘ＝０ 及び ｓ＞ｍ の場合、最初
のｍ個のＴＳＤは、上記同様、ｍ個の優先権ＴＳＤの最
低優先権によって表わされ、走行リストの位置が第ｍＴ
ＳＤの後にある残りのｓ−ｍ個のＴＳＤはセッション走
行リストで直接待機する。これら残りのｓ−ｍ個のＴＳ
Ｄの各々は、これらの優先権レベルが第ｍ ＴＳＤのレ
ベル以下であるか否かの表示の後、ステップ６１８にお
いて、セッション走行リストで直接待機する。 ｃ．ｘ＞＝ｍ の場合、クラスからのＴＳＤがＭ−ｘ個
まで優先権順にセッション走行リストに出現することが
できる。
【００９８】その第ｍスレッドが走行リストの最上部と
なった時点において、クラスはタスク指名される。この
点において、下記３つの場合が発生する。 １）ｍ個の遊休プロセッサが使用可能である。この場
合、ｍ個のＴＳＤは直ちにこれらｍ個のプロセッサを走
行することができる。
【００９９】２）ｉ＜ｍ個の遊休プロセッサと、タスク
指名を要求するクラスのｍ個の最高優先権スレッドより
低い優先権のｐ＝ｍ−ｉ個の他のプロセッサ走行スレッ
ドとがある。この場合、他のプロセッサの遂行するスレ
ッドは優先使用され、新クラスのｍ個のスレッドを走行
することができる。 ３）遊休及び優先使用可能なプロセッサの数がクラスを
走行させるに不十分である。前述の切替原始機能は下記
４つのオプションのいずれかを実施することによって、
この不足を処理するよう変更可能である。
【０１００】ａ．より高い優先権の１つが後にタスク指
名可能になるとしても、最初待っているクラスをタスク
指名するまで、いかなる他のＴＳＤのタスク指名をも拒
絶する。 ｂ．現在、如何なるより低い優先権のＴＳＤをタスク指
名することをも拒絶するが、より高い優先権のＴＳＤが
後にタスク指名可能となれば、通常のタスク指名規則を
再開始する。
【０１０１】ｃ．十分な他のプロセッサが使用可能とな
るときはいつでも、それを優先使用することができる意
向をもって、現在低い優先権のＴＳＤをタスク指名する
よう試み、より高い優先権のＴＳＤが後に使用可能とな
ると、通常のタスク指名規則を再開始する。 ｄ．作動可能なクラスがタスク指名されるまで、より低
い優先権のＴＳＤのみ（後に優先使用することができ
る）をタスク指名する。
【０１０２】切替原始機能に対する他の必要な変更は、
遂行するスレッドの数がｍ個以下に落ちようとしている
ときはいつでも、全クラスの遂行を停止することであ
る。これは、切替原始機能に対する呼出しに従い、ＣＰ
Ｕから除去されるスレッドの数も追跡することによって
実施される。
【０１０３】クラス走行リストの使用は、最少及び最大
両プロセッサ・カウントが１に等しいときは、クラス走
行リストが使用可能なスレッドのみを含み、その使用が
タスク指名の使用可能なスレッドの反復調査を避けるた
め、プロモート原始機能を最適化することができるとい
うことに注目するべきである。
【０１０４】以上、本発明によるオペレーティング・シ
ステムをその一実施例に基づき開示したが、本発明の範
囲から離れることなく、多くの代替及び変更が可能であ
ることは明らかである。
【０１０５】
【発明の効果】本発明は、以上説明したように構成した
ことにより、単一プロセッサ及び多重プロセッサ、どち
らのコンピュータ・システムでも使用可能であり、アプ
リケーション・プログラムによってプログラム・スレッ
ドの遂行スケジュールに影響を与えて、プログラム・ス
レッドの遂行順序を最適化するようにしたことにより、
オペレーション効率を最大に向上させることができた。
【図面の簡単な説明】
【図１】本発明の一実施例において遂行するプログラム
・スレッドをスケジュールする多重タスク処理オペレー
ティング・システムの各構成要素を示すブロック図
【図２】図１のオペレーティング・システムによって使
用するためプログラム・スレッドのパラメータを指定す
るよう作成されたスレッド状態記述子（ＴＳＤ）フィー
ルドを示す図
【図３】図１のスレッド状態記述子を組織するよう作成
されたタスク指名クラス記述子（ＤＣＤ）フィールドを
示す図
【図４】図１の各タスク指名クラス内のスレッド状態記
述子の相互に及び連鎖に対するタスク指名クラスのすべ
ての連係を示す図
【図５】図１のオペレーティング・システム内のスレッ
ド作成機能を示す流れ図
【図６】図１のオペレーティング・システム内で走行リ
ストを形成するようスレッド状態記述子の連鎖を示す図
【図７】図１のオペレーティング・システムのプロモー
ト原始機能を示す流れ図
【図８】図１のオペレーティング・システムのスケジュ
ール原始機能を示す流れ図
【図９】図１のオペレーティング・システムの切替原始
機能を示す流れ図
【図１０】図１のオペレーティング・システムのブロッ
ク原始機能を示す流れ図
【図１１】図１のオペレーティング・システムの非ブロ
ック原始機能を示す流れ図
【図１２】図１のオペレーティング・システムのスレッ
ド延期機能を示す流れ図
【図１３】図１のオペレーティング・システムの未スケ
ジュール原始機能を示す流れ図
【図１４】図１のオペレーティング・システムのスレッ
ド再開始機能を示す流れ図
【図１５】図１のオペレーティング・システムのスレッ
ド削除機能を示す流れ図
【図１６】図１のオペレーティング・システムのスレッ
ド・セット優先権機能を示す流れ図
【図１７】図１のオペレーティング・システムのスレッ
ド・セット・タスク指名クラス機能を示す流れ図
【図１８】図１のオペレーティング・システムのスレッ
ド放棄機能を示す流れ図
【図１９】図１のオペレーティング・システムの変更ス
ケジュール原始機能を示す流れ図
【符号の説明】
１０ 多重タスク処理オペレーティング・システム １２ａ，１２ｂ，１２ｃ アプリケーション・プログ
ラム １４ａ，１４ｂ，１４ｃ ＣＰＵ １５ スレッド作成機能 １６，１８，２０ タスク指名クラス １９ スレッド状態記述子（ＴＳＤ） ２２，２４，２６ タスク指名クラス記述子（ＤＣ
Ｄ） ３２ 走行リスト ３４ プロモート原始機能 ３６ スケジュール原始機能 ３８ 未スケジュール原始機能 ４５ ブロック機能 ４６ 切替機能 ４８ 非ブロック機能 ５０ スレッド延期機能 ５２ スレッド再開始機能 ５３ スレッド・セット・タスク指名クラス ５５ スレッド・セット優先権 ６０ スレッド削除機能
───────────────────────────────────────────────────── フロントページの続き (72)発明者 ステファン・エリオット・レコード アメリカ合衆国06877、コネチカット州、 リッジフィールド、ローリング・リッジ・ ロード、36番地 (72)発明者 ブライアン・キース・ウェイド アメリカ合衆国13732、ニューヨーク州、 アパラチン、ハイランド・ドライブ、９番 地

Claims (14)

    【特許請求の範囲】
  1. 【請求項１】 少くとも１つのクラスが複数のプログラ
    ム・スレッドを割当てることができるような複数のクラ
    スに対し多数のプログラム・スレッドを割当てる手段
    と、 前記プログラム・スレッドに対し優先権レベルを割当て
    る手段と、 前記クラスの各々における遂行のため使用可能な最高優
    先権プログラム・スレッドを遂行するため選択するよう
    に、前記プログラム・スレッドの遂行をスケジュールす
    る手段と、 アプリケーション・プログラム・スレッドからの要求に
    応答して、前記プログラム・スレッドの他の１つが割当
    てられるクラスを変更する手段とを含むことを特徴とす
    る多重タスク処理オペレーティング・システム。
  2. 【請求項２】 前記複数のクラスに対し多数のプログラ
    ム・スレッドを割当てる手段及び前記プログラム・スレ
    ッドに対し優先権レベルを割当てる手段は、アプリケー
    ション・プログラムによって指定されたパラメータに対
    する割当を基礎とすることを特徴とする請求項１記載の
    多重タスク処理オペレーティング・システム。
  3. 【請求項３】 前記変更する手段は要求するプログラム
    ・スレッドが割当てられているクラスに対し前記プログ
    ラム・スレッドの他の１つを割当てるようにしたことを
    特徴とする請求項１記載の多重タスク処理オペレーティ
    ング・システム。
  4. 【請求項４】 前記スケジュールする手段は前記遂行す
    るため選択されたプログラム・スレッドを該選択された
    プログラム・スレッドの相対的優先権に基づく順序に従
    い待ち行列で待機させることを特徴とする請求項１記載
    の多重タスク処理オペレーティング・システム。
  5. 【請求項５】 前記スケジュールする手段はあるクラス
    に割当てられているプログラム・スレッドに対し、他の
    クラスに割当てられているより低い優先権のプログラム
    ・スレッドの遂行を優先使用することを許すことを特徴
    とする請求項１記載の多重タスク処理オペレーティング
    ・システム。
  6. 【請求項６】 前記スケジュールする手段は遂行するた
    め使用可能な前記１つのクラスのプログラム・スレッド
    が前記１つのクラスの他のより低い優先権プログラム・
    スレッドの遂行を優先使用することを防止するようにし
    たことを特徴とする請求項１記載の多重タスク処理オペ
    レーティング・システム。
  7. 【請求項７】 各クラスに対し少くとも１つのプログラ
    ム・スレッドを割当て、少くとも１つの前記クラスに対
    し複数のプログラム・スレッドを割当てるように、複数
    のクラスに対し複数のプログラム・スレッドを割当て、 前記プログラム・スレッドの各々に対して優先権を割当
    て、 遂行のため使用可能な各前記クラスからの最高優先権プ
    ログラム・スレッドを遂行するため待ち行列で待機さ
    せ、 前記プログラム・スレッドの１つが割当てられるクラス
    を変更する要求をアプリケーション・プログラム・スレ
    ッドから受信し、 前記要求に応答して前記１つのプログラム・スレッドを
    割当てるクラスを変更する各工程から成ることを特徴と
    するコンピュータの動作方法。
  8. 【請求項８】 前記コンピュータの動作方法は、更に、 前記待ち行列からのプログラム・スレッドの１つを遂行
    し、 前記待ち行列からの前記１つのプログラム・スレッドの
    少くとも一部を遂行した後、前記待ち行列における他の
    クラスからのより高い優先権プログラム・スレッドによ
    る前記１つのプログラム・スレッドの遂行を優先使用す
    る各工程を含むことを特徴とする請求項７記載のコンピ
    ュータの動作方法。
  9. 【請求項９】 前記コンピュータの動作方法は、更に、 前記待ち行列からのプログラム・スレッドの１つを遂行
    し、 遂行のため使用可能であり、前記遂行しているプログラ
    ム・スレッドと同一クラスにあって、より高い優先権を
    有するプログラム・スレッドの他の１つが前記遂行して
    いるプログラム・スレッドの遂行を優先使用することを
    防止する各工程を含むことを特徴とする請求項７記載の
    コンピュータの動作方法。
  10. 【請求項１０】 複数のクラスの各々は少くとも１つの
    プログラム・スレッドが割当てられ、前記クラスの少く
    とも１つには複数のプログラム・スレッドを割当てるこ
    とができるよう複数のクラスに対し複数のプログラム・
    スレッドを割当てる手段と、 少くとも１つのプロセッサと、 遂行順序に影響を与えるよう前記プログラム・スレッド
    の各々に対して優先権を割当てる手段と、 少くとも一部前記クラスの各々におけるプログラム・ス
    レッドの相対的優先権レベルに基づき、前記プロセッサ
    による遂行のため前記クラスの各々から少くとも１つの
    使用可能なプログラム・スレッドを選択する手段と、 アプリケーション・プログラム・スレッドからの要求に
    応答して、他の前記プログラム・スレッドを割当てるク
    ラスを変更する手段とから成るコンピュータ・システ
    ム。
  11. 【請求項１１】 コンピュータ読出可能な記録媒体に格
    納され、コンピュータ・プロセッサに命令して遂行させ
    るプログラム命令方法であって、 コンピュータ・プロセッサに命令してプログラム・スレ
    ッド及び該プログラム・スレッドが存在するクラスの識
    別機能を受信し、 前記識別機能に基づき、前記プログラム・スレッドを前
    記クラスに割当て、 前記クラスの各々から遂行のためプログラム・スレッド
    の１つを選択し、 アプリケーション・プログラム・スレッドからの要求に
    応じ、他の１つの前記プログラム・スレッドのクラスを
    変更する各工程を含むコンピュータの動作方法。
  12. 【請求項１２】 少くとも１つのクラスは複数のプログ
    ラム・スレッドを割当てることができるようにされた複
    数のクラスに対し多数のプログラム・スレッドを割当て
    る手段と、 前記プログラム・スレッドに対し優先権を割当てる手段
    と、 遂行のため使用可能な各前記クラスの最高優先権プログ
    ラム・スレッドを遂行するため選択するように、前記プ
    ログラム・スレッドの遂行をスケジュールする手段と、 遂行中の前記プログラム・スレッドの１つからの要求に
    応答して、前記プログラム・スレッドの遂行を停止し、
    遂行のため使用可能な同一クラスからの特定のプログラ
    ム・スレッド又は遂行のため使用可能な同一クラスから
    の最高優先権プログラム・スレッドを遂行するため選択
    する各工程を含み、前記停止したプログラム・スレッド
    は遂行のため使用可能であることを特徴とする多重タス
    ク処理オペレーティング・システム。
  13. 【請求項１３】 各クラスに対し少くとも１つのプログ
    ラム・スレッドを割当て、少くとも１つの前記クラスに
    対し複数のプログラム・スレッドを割当てるように、複
    数のクラスに対し複数のプログラム・スレッドを割当
    て、 前記プログラム・スレッドの各々に対して優先権を割当
    て、 遂行のため使用可能な各クラスからの最高優先権プログ
    ラム・スレッドを遂行するため待ち行列で待機させ、 遂行中の前記プログラム・スレッドの１つからの要求に
    応答して、前記プログラム・スレッドの遂行を停止し、
    遂行のため使用可能な同一クラスからの特定のプログラ
    ム・スレッド又は遂行のため使用可能な同一クラスから
    の最高優先権プログラム・スレッドを選択し、前記選択
    されたプログラム・スレッドを前記待ち行列で待機さ
    せ、前記停止したプログラム・スレッドを遂行のため使
    用可能に維持する各工程を含むコンピュータの動作方
    法。
  14. 【請求項１４】 各クラスに対し少くとも１つのプログ
    ラム・スレッドを割当て、少くとも１つの前記クラスに
    対し複数のプログラム・スレッドを割当てるように、複
    数のプログラム・スレッドを複数のクラスに割当てる手
    段と、 少くとも１つのプロセッサと、 遂行順序に影響を与えるよう前記プログラム・スレッド
    の各々に対し優先権レベルを割当てる手段と、 少くとも一部は前記クラスの各々におけるプログラム・
    スレッドの相対的優先権レベルに基づき、前記プロセッ
    サによる遂行のため前記クラスの各々から少くとも１つ
    の使用可能なプログラム・スレッドを選択する手段と、 遂行中の前記プログラム・スレッドの１つからの要求に
    応答して、前記１つのプログラム・スレッドの遂行を停
    止し、遂行のため使用可能な同一クラスからの特定のプ
    ログラム・スレッド又は遂行のため使用可能な同一クラ
    スからの最高優先権プログラム・スレッドを選択し、前
    記選択されたプログラム・スレッドを待ち行列で待機さ
    せるようにした手段とを含み、前記停止したプログラム
    ・スレッドは遂行のため使用可能であることを特徴とす
    るコンピュータ・システム。
JP4177766A 1991-08-09 1992-06-12 多重タスク処理オペレ―ティング・システム及びそのコンピュ―タの動作方法 Expired - Lifetime JP2518998B2 (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US743541 1991-08-09
US07/743,541 US5630128A (en) 1991-08-09 1991-08-09 Controlled scheduling of program threads in a multitasking operating system

Publications (2)

Publication Number Publication Date
JPH05189251A true JPH05189251A (ja) 1993-07-30
JP2518998B2 JP2518998B2 (ja) 1996-07-31

Family

ID=24989186

Family Applications (1)

Application Number Title Priority Date Filing Date
JP4177766A Expired - Lifetime JP2518998B2 (ja) 1991-08-09 1992-06-12 多重タスク処理オペレ―ティング・システム及びそのコンピュ―タの動作方法

Country Status (3)

Country Link
US (1) US5630128A (ja)
EP (1) EP0527301A3 (ja)
JP (1) JP2518998B2 (ja)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8006244B2 (en) 2000-04-04 2011-08-23 International Business Machines Corporation Controller for multiple instruction thread processors

Families Citing this family (102)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6021425A (en) * 1992-04-03 2000-02-01 International Business Machines Corporation System and method for optimizing dispatch latency of tasks in a data processing system
US5379432A (en) * 1993-07-19 1995-01-03 Taligent, Inc. Object-oriented interface for a procedural operating system
SE9404294D0 (sv) * 1994-12-09 1994-12-09 Ellemtel Utvecklings Ab sätt och anordning vid telekommunikation
US6728959B1 (en) * 1995-08-08 2004-04-27 Novell, Inc. Method and apparatus for strong affinity multiprocessor scheduling
US6141677A (en) * 1995-10-13 2000-10-31 Apple Computer, Inc. Method and system for assigning threads to active sessions
CA2178898C (en) * 1996-06-12 2000-02-01 David Joseph Streeter Sequencing and error detection of template instantiations during compilation of c++ programs
DE69724736T2 (de) * 1996-10-25 2004-07-08 Fujitsu Services Ltd. Prozessablaufsteuerung
US5961583A (en) * 1996-11-22 1999-10-05 International Business Machines Corporation Method and system for using the event wait list anchor as a lock for events
US6212542B1 (en) * 1996-12-16 2001-04-03 International Business Machines Corporation Method and system for executing a program within a multiscalar processor by processing linked thread descriptors
US6073159A (en) * 1996-12-31 2000-06-06 Compaq Computer Corporation Thread properties attribute vector based thread selection in multithreading processor
US6009484A (en) * 1997-02-28 1999-12-28 Ncr Corporation Priority-based I/O task processing in computers
US6314530B1 (en) * 1997-04-08 2001-11-06 Advanced Micro Devices, Inc. Processor having a trace access instruction to access on-chip trace memory
US6359899B1 (en) * 1997-05-28 2002-03-19 Lucent Technologies Inc. Priority access for real-time traffic in contention-based networks
US6829764B1 (en) * 1997-06-23 2004-12-07 International Business Machines Corporation System and method for maximizing usage of computer resources in scheduling of application tasks
US6189023B1 (en) * 1997-09-30 2001-02-13 Tandem Computers Incorporated Simulating shared code thread modules with shared code fibers
US6212544B1 (en) * 1997-10-23 2001-04-03 International Business Machines Corporation Altering thread priorities in a multithreaded processor
US6697935B1 (en) 1997-10-23 2004-02-24 International Business Machines Corporation Method and apparatus for selecting thread switch events in a multithreaded processor
US6076157A (en) * 1997-10-23 2000-06-13 International Business Machines Corporation Method and apparatus to force a thread switch in a multithreaded processor
US6567839B1 (en) 1997-10-23 2003-05-20 International Business Machines Corporation Thread switch control in a multithreaded processor system
US5999963A (en) * 1997-11-07 1999-12-07 Lucent Technologies, Inc. Move-to-rear list scheduling
US6119170A (en) * 1997-12-29 2000-09-12 Bull Hn Information Systems Inc. Method and apparatus for TCP/IP multihoming on a host system configured with multiple independent transport provider systems
IL123512A0 (en) * 1998-03-02 1999-03-12 Security 7 Software Ltd Method and agent for the protection against hostile resource use access
US6920634B1 (en) * 1998-08-03 2005-07-19 International Business Machines Corporation Detecting and causing unsafe latent accesses to a resource in multi-threaded programs
US6418458B1 (en) * 1998-10-02 2002-07-09 Ncr Corporation Object-oriented prioritized work thread pool
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
US6874144B1 (en) * 1999-04-05 2005-03-29 International Business Machines Corporation System, method, and program for implementing priority inheritance in an operating system
US7424712B1 (en) 1999-04-30 2008-09-09 Sun Microsystems Inc System and method for controlling co-scheduling of processes of parallel program
US7043725B1 (en) * 1999-07-09 2006-05-09 Hewlett-Packard Development Company, L.P. Two tier arrangement for threads support in a virtual machine
JP2001076282A (ja) * 1999-09-02 2001-03-23 Canon Inc 情報処理装置およびその方法
US6662364B1 (en) * 1999-11-05 2003-12-09 Hewlett-Packard Company, L.P. System and method for reducing synchronization overhead in multithreaded code
US7418506B1 (en) * 1999-11-12 2008-08-26 International Business Machines Corporation Apparatus for connection management and the method therefor
US7577958B1 (en) * 1999-12-09 2009-08-18 Nortel Networks Limited Expediting an operation in a computer system
US7099855B1 (en) 2000-01-13 2006-08-29 International Business Machines Corporation System and method for electronic communication management
US6757897B1 (en) * 2000-02-29 2004-06-29 Cisco Technology, Inc. Apparatus and methods for scheduling and performing tasks
US8290768B1 (en) 2000-06-21 2012-10-16 International Business Machines Corporation System and method for determining a set of attributes based on content of communications
US9699129B1 (en) 2000-06-21 2017-07-04 International Business Machines Corporation System and method for increasing email productivity
US6408277B1 (en) * 2000-06-21 2002-06-18 Banter Limited System and method for automatic task prioritization
US7076275B1 (en) * 2000-10-13 2006-07-11 Palmsource, Inc. Method and system for single-step enablement of telephony functionality for a portable computer system
JP3810631B2 (ja) * 2000-11-28 2006-08-16 富士通株式会社 情報処理プログラムを記録した記録媒体
US7644057B2 (en) 2001-01-03 2010-01-05 International Business Machines Corporation System and method for electronic communication management
US20020092012A1 (en) * 2001-01-09 2002-07-11 Shah Alexandre K. Smart-caching system and method
US6845504B2 (en) * 2001-02-08 2005-01-18 International Business Machines Corporation Method and system for managing lock contention in a computer system
US7233998B2 (en) * 2001-03-22 2007-06-19 Sony Computer Entertainment Inc. Computer architecture and software cells for broadband networks
US6918116B2 (en) * 2001-05-15 2005-07-12 Hewlett-Packard Development Company, L.P. Method and apparatus for reconfiguring thread scheduling using a thread scheduler function unit
US7272232B1 (en) * 2001-05-30 2007-09-18 Palmsource, Inc. System and method for prioritizing and balancing simultaneous audio outputs in a handheld device
US7321568B2 (en) * 2001-06-01 2008-01-22 Texas Instruments Incorporated Realtime management of processing resources
US7093254B2 (en) * 2002-04-01 2006-08-15 International Business Machines Corporation Scheduling tasks quickly in a sequential order
GB2388213A (en) * 2002-04-30 2003-11-05 Innovation Ct Improvements relating to task dispatch in priority pre-emptive real-time operating systems
AU2003222977A1 (en) * 2002-04-30 2003-11-17 Livedevices Limited Dispatch in priority pre-emptive real-time operating systems
US20030236826A1 (en) * 2002-06-24 2003-12-25 Nayeem Islam System and method for making mobile applications fault tolerant
US7287254B2 (en) 2002-07-30 2007-10-23 Unisys Corporation Affinitizing threads in a multiprocessor system
US7673304B2 (en) 2003-02-18 2010-03-02 Microsoft Corporation Multithreaded kernel for graphics processing unit
US7039914B2 (en) * 2003-03-07 2006-05-02 Cisco Technology, Inc. Message processing in network forwarding engine by tracking order of assigned thread in order group
US7305681B2 (en) * 2003-03-20 2007-12-04 Nokia Corporation Method and apparatus for providing multi-client support in a sip-enabled terminal
US7389230B1 (en) 2003-04-22 2008-06-17 International Business Machines Corporation System and method for classification of voice signals
US7278141B2 (en) * 2003-04-23 2007-10-02 International Business Machines Corporation System and method for adding priority change value corresponding with a lock to a thread during lock processing
US8495002B2 (en) 2003-05-06 2013-07-23 International Business Machines Corporation Software tool for training and testing a knowledge base
US20050187913A1 (en) 2003-05-06 2005-08-25 Yoram Nelken Web-based customer service interface
US20040233934A1 (en) * 2003-05-23 2004-11-25 Hooper Donald F. Controlling access to sections of instructions
US7337443B2 (en) * 2003-06-30 2008-02-26 Microsoft Corporation Method and apparatus for processing program threads
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
US7496928B2 (en) * 2003-08-28 2009-02-24 Microsoft Corporation Method and system for moderating thread priority boost for I/O completion
US7690003B2 (en) * 2003-08-29 2010-03-30 Fuller Jeffrey C System and method for increasing data throughput using thread scheduling
US7516456B2 (en) 2003-09-25 2009-04-07 International Business Machines Corporation Asymmetric heterogeneous multi-threaded operating system
US20050071828A1 (en) * 2003-09-25 2005-03-31 International Business Machines Corporation System and method for compiling source code for multi-processor environments
US7549145B2 (en) * 2003-09-25 2009-06-16 International Business Machines Corporation Processor dedicated code handling in a multi-processor environment
US7389508B2 (en) * 2003-09-25 2008-06-17 International Business Machines Corporation System and method for grouping processors and assigning shared memory space to a group in heterogeneous computer environment
US7523157B2 (en) * 2003-09-25 2009-04-21 International Business Machines Corporation Managing a plurality of processors as devices
US7415703B2 (en) * 2003-09-25 2008-08-19 International Business Machines Corporation Loading software on a plurality of processors
US7475257B2 (en) 2003-09-25 2009-01-06 International Business Machines Corporation System and method for selecting and using a signal processor in a multiprocessor system to operate as a security for encryption/decryption of data
US7478390B2 (en) * 2003-09-25 2009-01-13 International Business Machines Corporation Task queue management of virtual devices using a plurality of processors
US7353517B2 (en) * 2003-09-25 2008-04-01 International Business Machines Corporation System and method for CPI load balancing in SMT processors
US7444632B2 (en) * 2003-09-25 2008-10-28 International Business Machines Corporation Balancing computational load across a plurality of processors
US7360218B2 (en) * 2003-09-25 2008-04-15 International Business Machines Corporation System and method for scheduling compatible threads in a simultaneous multi-threading processor using cycle per instruction value occurred during identified time interval
US7496917B2 (en) * 2003-09-25 2009-02-24 International Business Machines Corporation Virtual devices using a pluarlity of processors
US7451444B2 (en) * 2003-09-30 2008-11-11 Sas Institute Inc. Computer-implemented system and method for managing service agents
US7676809B2 (en) * 2003-10-09 2010-03-09 International Business Machines Corporation System, apparatus and method of enhancing priority boosting of scheduled threads
US20050108711A1 (en) * 2003-11-13 2005-05-19 Infineon Technologies North America Corporation Machine instruction for enhanced control of multiple virtual processor systems
JP4603256B2 (ja) * 2003-12-01 2010-12-22 日本電気株式会社 ユーザ認証システム
US7448037B2 (en) * 2004-01-13 2008-11-04 International Business Machines Corporation Method and data processing system having dynamic profile-directed feedback at runtime
US7475399B2 (en) * 2004-01-13 2009-01-06 International Business Machines Corporation Method and data processing system optimizing performance through reporting of thread-level hardware resource utilization
US7614053B2 (en) * 2004-02-20 2009-11-03 Sony Computer Entertainment Inc. Methods and apparatus for task management in a multi-processor system
US7565653B2 (en) * 2004-02-20 2009-07-21 Sony Computer Entertainment Inc. Methods and apparatus for processor task migration in a multi-processor system
US8028292B2 (en) * 2004-02-20 2011-09-27 Sony Computer Entertainment Inc. Processor task migration over a network in a multi-processor system
WO2005085994A2 (en) * 2004-02-24 2005-09-15 Koninklijke Philips Electronics N.V. Multi-tasking data processing system
US7487503B2 (en) 2004-08-12 2009-02-03 International Business Machines Corporation Scheduling threads in a multiprocessor computer
US7707556B1 (en) * 2004-09-29 2010-04-27 Oracle America, Inc. Method and system to measure system performance
US8516483B2 (en) * 2005-05-13 2013-08-20 Intel Corporation Transparent support for operating system services for a sequestered sequencer
US7403874B2 (en) * 2006-01-31 2008-07-22 Verigy (Singapore) Pte. Ltd. Method and system for prioritizing formatting actions of a number of data formatters
US7673181B1 (en) * 2006-06-07 2010-03-02 Replay Solutions, Inc. Detecting race conditions in computer programs
US7844970B2 (en) * 2006-08-22 2010-11-30 International Business Machines Corporation Method and apparatus to control priority preemption of tasks
US20110067015A1 (en) * 2008-02-15 2011-03-17 Masamichi Takagi Program parallelization apparatus, program parallelization method, and program parallelization program
TWI385634B (zh) * 2008-04-02 2013-02-11 Novatek Microelectronics Corp 用於一液晶顯示器控制器之微處理器裝置及相關方法
KR20130063825A (ko) * 2011-12-07 2013-06-17 삼성전자주식회사 운영체제에서 동적으로 선점 구간을 조정하는 장치 및 방법
GB2519080B (en) * 2013-10-08 2021-04-14 Arm Ip Ltd Scheduling function calls
US9348644B2 (en) * 2014-10-08 2016-05-24 International Business Machines Corporation Application-level dispatcher control of application-level pseudo threads and operating system threads
US10248463B2 (en) * 2015-02-13 2019-04-02 Honeywell International Inc. Apparatus and method for managing a plurality of threads in an operating system
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
GB2563587B (en) 2017-06-16 2021-01-06 Imagination Tech Ltd Scheduling tasks
US10810086B2 (en) 2017-10-19 2020-10-20 Honeywell International Inc. System and method for emulation of enhanced application module redundancy (EAM-R)
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
CN114356975B (zh) * 2022-01-04 2025-07-15 腾讯科技（深圳）有限公司 交通仿真数据推送方法、装置、介质及产品

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0460842A (ja) * 1990-06-29 1992-02-26 Toshiba Corp 計算機システム

Family Cites Families (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3648253A (en) * 1969-12-10 1972-03-07 Ibm Program scheduler for processing systems
FR2253421A5 (ja) * 1973-11-30 1975-06-27 Honeywell Bull Soc Ind
US4286322A (en) * 1979-07-03 1981-08-25 International Business Machines Corporation Task handling apparatus
US5168566A (en) * 1983-11-25 1992-12-01 Sharp Kabushiki Kaisha Multi-task control device for central processor task execution control provided as a peripheral device and capable of prioritizing and timesharing the tasks
US4980820A (en) * 1985-02-28 1990-12-25 International Business Machines Corporation Interrupt driven prioritized queue
US4642756A (en) * 1985-03-15 1987-02-10 S & H Computer Systems, Inc. Method and apparatus for scheduling the execution of multiple processing tasks in a computer system
US4912628A (en) * 1988-03-15 1990-03-27 International Business Machines Corp. Suspending and resuming processing of tasks running in a virtual machine data processing system
US5187790A (en) * 1989-06-29 1993-02-16 Digital Equipment Corporation Server impersonation of client processes in an object based computer operating system
US5129084A (en) * 1989-06-29 1992-07-07 Digital Equipment Corporation Object container transfer system and method in an object based computer operating system
US5297283A (en) * 1989-06-29 1994-03-22 Digital Equipment Corporation Object transferring system and method in an object based computer operating system
US5233611A (en) * 1990-08-20 1993-08-03 International Business Machines Corporation Automated function testing of application programs
US5220653A (en) * 1990-10-26 1993-06-15 International Business Machines Corporation Scheduling input/output operations in multitasking systems
US5247675A (en) * 1991-08-09 1993-09-21 International Business Machines Corporation Preemptive and non-preemptive scheduling and execution of program threads in a multitasking operating system

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH0460842A (ja) * 1990-06-29 1992-02-26 Toshiba Corp 計算機システム

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8006244B2 (en) 2000-04-04 2011-08-23 International Business Machines Corporation Controller for multiple instruction thread processors

Also Published As

Publication number Publication date
US5630128A (en) 1997-05-13
EP0527301A2 (en) 1993-02-17
JP2518998B2 (ja) 1996-07-31
EP0527301A3 (en) 1993-10-13

Similar Documents

Publication Publication Date Title
JP2518998B2 (ja) 多重タスク処理オペレ―ティング・システム及びそのコンピュ―タの動作方法
US5247675A (en) Preemptive and non-preemptive scheduling and execution of program threads in a multitasking operating system
US5469571A (en) Operating system architecture using multiple priority light weight kernel task based interrupt handling
US6021425A (en) System and method for optimizing dispatch latency of tasks in a data processing system
US9507631B2 (en) Migrating a running, preempted workload in a grid computing system
US6223204B1 (en) User level adaptive thread blocking
EP0661633B1 (en) Method and system for managing ownership of a released synchronization mechanism
US5339415A (en) Dual level scheduling of processes to multiple parallel regions of a multi-threaded program on a tightly coupled multiprocessor computer system
US5515538A (en) Apparatus and method for interrupt handling in a multi-threaded operating system kernel
JP5678135B2 (ja) オペレーティング・システム介入なしにｏｓ隔離シーケンサー上でスレッドをスケジューリングする機構
EP0767938B1 (en) Method for enforcing a hierarchical invocation structure in real time asynchronous software applications
US8161453B2 (en) Method and apparatus for implementing task management of computer operations
US5526521A (en) Method and system for process scheduling from within a current context and switching contexts only when the next scheduled context is different
JP2004288162A (ja) 同期タスクを利用したオペレーティングシステムアーキテクチャ
US20250004830A1 (en) Scheduling of threads for clusters of processors
US8528006B1 (en) Method and apparatus for performing real-time commands in a non real-time operating system environment
US20050066149A1 (en) Method and system for multithreaded processing using errands
US20250021380A1 (en) Thread scheduling including preemption of a thread in a kernel persona
JPH11212810A (ja) タイム・クアンタム共有方法および装置
US20240419485A1 (en) Thread state transitions
EP0544822B1 (en) Dual level scheduling of processes
WO2023241307A1 (zh) 管理线程的方法及装置
CN115098230B (zh) 管理线程的方法及装置
US20240419483A1 (en) Interrupt handling
CN120216124A (zh) 一种用户中断事件回调机制实现方法