JPH0782444B2 - タスクスケジユ−ル方式 - Google Patents
タスクスケジユ−ル方式Info
- Publication number
- JPH0782444B2 JPH0782444B2 JP25821086A JP25821086A JPH0782444B2 JP H0782444 B2 JPH0782444 B2 JP H0782444B2 JP 25821086 A JP25821086 A JP 25821086A JP 25821086 A JP25821086 A JP 25821086A JP H0782444 B2 JPH0782444 B2 JP H0782444B2
- Authority
- JP
- Japan
- Prior art keywords
- task
- resource
- overhead
- ratio
- processor
- 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 - Fee Related
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
Landscapes
- Engineering & Computer Science (AREA)
- Software Systems (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
Description
【発明の詳細な説明】 〔産業上の利用分野〕 本発明はメモリを共用するマルチプロセッサシステムに
おけるタスクのスケジューリング方式に関するものであ
る。
おけるタスクのスケジューリング方式に関するものであ
る。
タスクスケジューリング方式において、従来は先入れ先
出し方式、プライオリティによる方式、プロセッサ使用
時間の長いタスクよりI/Oの多いタスクを優先する方
式、処理時間の目標値を守るように処理順序を変える方
式等があった。これら方式では、タスクのリソース使用
状況および要求状況は考慮されていなかった。また、特
願昭61−133641号に示すようにタスク切り換えオーバー
ヘッドが十分小の場合はプライオリティを無視してリソ
ースを使用するタスクをいずれかのプロセッサで必ず処
理していることにより将来のリソースネックを防止して
スループットを向上させることができる。
出し方式、プライオリティによる方式、プロセッサ使用
時間の長いタスクよりI/Oの多いタスクを優先する方
式、処理時間の目標値を守るように処理順序を変える方
式等があった。これら方式では、タスクのリソース使用
状況および要求状況は考慮されていなかった。また、特
願昭61−133641号に示すようにタスク切り換えオーバー
ヘッドが十分小の場合はプライオリティを無視してリソ
ースを使用するタスクをいずれかのプロセッサで必ず処
理していることにより将来のリソースネックを防止して
スループットを向上させることができる。
従来の方式においては、タスクがリソースを解放する都
度タスクの再スケジュールを行っていた。この方式では
タスク切り換えのオーバーヘッドが小さい場合は最大の
スループットを実現できるが、オーバーヘッドの大きい
場合処理能力が低下してしまう。
度タスクの再スケジュールを行っていた。この方式では
タスク切り換えのオーバーヘッドが小さい場合は最大の
スループットを実現できるが、オーバーヘッドの大きい
場合処理能力が低下してしまう。
本発明は上記の目的のため、従来のタスクキューの他に
リソース待ちキューを追加する。リソース競合時は、リ
ソース待ちキューにタスクを入れる。タスクスケジュー
ル時に、リソースが使用中かどうかを調べ、リソース未
使用ならリソース待ちキュー中のタスクをまずスケジュ
ールする。また、タスクがリソースを解放した場合、他
にリソース待ちをしているタスクがあればタスク切り換
えを行うべきかをあらかじめ設定したフラグによって決
定する。このフラグをタスク切り換えオーバーヘッドと
タスクのリソース占有解放の一周期のオーバーヘッドの
比較によって設定する手段を持つ。
リソース待ちキューを追加する。リソース競合時は、リ
ソース待ちキューにタスクを入れる。タスクスケジュー
ル時に、リソースが使用中かどうかを調べ、リソース未
使用ならリソース待ちキュー中のタスクをまずスケジュ
ールする。また、タスクがリソースを解放した場合、他
にリソース待ちをしているタスクがあればタスク切り換
えを行うべきかをあらかじめ設定したフラグによって決
定する。このフラグをタスク切り換えオーバーヘッドと
タスクのリソース占有解放の一周期のオーバーヘッドの
比較によって設定する手段を持つ。
本発明の作用は、メモリを共用するプロセッサ上のタス
クスケジューラにおいてタスクが複数の排他リソースを
高い割合で使用する場合、これらリソースを待っている
タスクがある時に、タスクがリソースを解放した場合に
リソース待ちをしているタスクに切り換えるかどうか
を、タスク切り換えオーバーヘッドを考慮して決めるこ
とにより、将来発生し得るプロセッサのアイドルを防止
しつつ、タスク切り換えオーバーヘッドによる性能の低
下を防止する。
クスケジューラにおいてタスクが複数の排他リソースを
高い割合で使用する場合、これらリソースを待っている
タスクがある時に、タスクがリソースを解放した場合に
リソース待ちをしているタスクに切り換えるかどうか
を、タスク切り換えオーバーヘッドを考慮して決めるこ
とにより、将来発生し得るプロセッサのアイドルを防止
しつつ、タスク切り換えオーバーヘッドによる性能の低
下を防止する。
以下、本発明の一実施例を説明する。第１図は、本発明
のタスクスケジューラの概要図である。タスクスケジュ
ーラ1.は、各タスクの終了時リソースの占有解放時ある
いは入出力要求時などに、次に処理するタスクを選択し
起動するために起動される。本実施例ではリソースとし
て以下の条件を満足するものを想定する。リソースの要
求はプロセッサを割り当てられているタスクからのみ行
う。タスクの入出力要求時などタスクがプロセッサを割
り当て可能でない状態になる時は必ずリソースを解放す
ることにより、リソースは現在プロセッサを割り当てら
れている、あるいは割り当て可能で中断されているタス
クのみが占有している。
のタスクスケジューラの概要図である。タスクスケジュ
ーラ1.は、各タスクの終了時リソースの占有解放時ある
いは入出力要求時などに、次に処理するタスクを選択し
起動するために起動される。本実施例ではリソースとし
て以下の条件を満足するものを想定する。リソースの要
求はプロセッサを割り当てられているタスクからのみ行
う。タスクの入出力要求時などタスクがプロセッサを割
り当て可能でない状態になる時は必ずリソースを解放す
ることにより、リソースは現在プロセッサを割り当てら
れている、あるいは割り当て可能で中断されているタス
クのみが占有している。
タスクの状態遷移は第２図に示すように行われる。タス
クは生成されるとレディ状態10.に入り、リソース非占
有実行状態11.で終了する（この処理は図示せず）。レ
ディ状態10.のタスクはタスクスケジューラによりリソ
ース非占有実行状態11.に入る。リソース非占有実行状
態11.のタスクがリソースを使用する時、リソース占有
処理が成功した場合はリソース占有実行状態12.に、失
敗した場合はリソース待ち状態13.に入る。リソース占
有実行状態12.でリソース解放時は、リソース解放処理
により他にリソース待ちタスクで使用可能なものがある
場合でディパッチフラグ20.がオンならレディ状態10.
に、そうでなければリソース非占有実行状態11.に入
る。リソース待ち状態13.のタスクはタスクスケジュー
ラにより選択された場合にリソース占有実行状態12.と
なる。リソース非占有実行状態11.、およびリソース占
有実行状態12.でタスク中断が発生した場合、中断処理
によりそれぞれレディ状態10.、およびリソース占有中
断状態14.に入る。リソース占有中断状態14.のタスクは
タスクスケジューラに選択された場合、リソース占有実
行状態12.に戻る。なお、第１図ではリソース占有中断
状態のタスクはリソース待ちキューの先頭に置かれる。
クは生成されるとレディ状態10.に入り、リソース非占
有実行状態11.で終了する（この処理は図示せず）。レ
ディ状態10.のタスクはタスクスケジューラによりリソ
ース非占有実行状態11.に入る。リソース非占有実行状
態11.のタスクがリソースを使用する時、リソース占有
処理が成功した場合はリソース占有実行状態12.に、失
敗した場合はリソース待ち状態13.に入る。リソース占
有実行状態12.でリソース解放時は、リソース解放処理
により他にリソース待ちタスクで使用可能なものがある
場合でディパッチフラグ20.がオンならレディ状態10.
に、そうでなければリソース非占有実行状態11.に入
る。リソース待ち状態13.のタスクはタスクスケジュー
ラにより選択された場合にリソース占有実行状態12.と
なる。リソース非占有実行状態11.、およびリソース占
有実行状態12.でタスク中断が発生した場合、中断処理
によりそれぞれレディ状態10.、およびリソース占有中
断状態14.に入る。リソース占有中断状態14.のタスクは
タスクスケジューラに選択された場合、リソース占有実
行状態12.に戻る。なお、第１図ではリソース占有中断
状態のタスクはリソース待ちキューの先頭に置かれる。
第３図に処理の流れを示すように、タスクスケジューラ
1.は、まず、リソース使用中フラグ2.を見て他のプロセ
ッサが当該リソースを使用中でなければリソース待ちキ
ュー3.の先頭のタスクを取り出しスケジュールする。ス
ケジュールすべきタスクがなければ、レディキュー4.よ
りタスクをスケジュールする。
1.は、まず、リソース使用中フラグ2.を見て他のプロセ
ッサが当該リソースを使用中でなければリソース待ちキ
ュー3.の先頭のタスクを取り出しスケジュールする。ス
ケジュールすべきタスクがなければ、レディキュー4.よ
りタスクをスケジュールする。
タスクからリソースの占有解放を行う場合次のようにす
る。第４図に示すように占有要求時、リソース使用中フ
ラグがONならリソース待ちキュー3.へ入る。そしてタス
クスケジューラへ行く。
る。第４図に示すように占有要求時、リソース使用中フ
ラグがONならリソース待ちキュー3.へ入る。そしてタス
クスケジューラへ行く。
解放時は第５図に示すように、ディスパッチフラグ20.
がONで他のリソース待ちキュー中のタスクがあるならば
自タスクを中断し、そのタスクを起動するためタスクス
ケジューラへ行く。
がONで他のリソース待ちキュー中のタスクがあるならば
自タスクを中断し、そのタスクを起動するためタスクス
ケジューラへ行く。
タスク中断処理は第６図に示すように、タスクがリソー
スを使用中であればリソース待ちキューの先頭に、そう
でなければレディキューに入れる。
スを使用中であればリソース待ちキューの先頭に、そう
でなければレディキューに入れる。
第７図はディスパッチフラグ20.の設定処理を示す。あ
らかじめ与えられたディスパッチ一回当たりのダイナミ
ックステップ数と、タスクの一回当たりのリソース占有
処理ステップ数＋リソース非占有処理ステップ数の比
が、あらかじめ定められた比例定数よりも大きければデ
ィパッチフラグをオフに設定し、小さければオンに設定
する。
らかじめ与えられたディスパッチ一回当たりのダイナミ
ックステップ数と、タスクの一回当たりのリソース占有
処理ステップ数＋リソース非占有処理ステップ数の比
が、あらかじめ定められた比例定数よりも大きければデ
ィパッチフラグをオフに設定し、小さければオンに設定
する。
本発明によれば、ディスパッチオーバーヘッドの小さい
時、リソースの競合による性能の低下を防止し、ディス
パッチオーバーヘッドの大きな時、逆にディスパッチを
防止することにより、システムのタスク処理能力を最大
にすることを可能にした。
時、リソースの競合による性能の低下を防止し、ディス
パッチオーバーヘッドの大きな時、逆にディスパッチを
防止することにより、システムのタスク処理能力を最大
にすることを可能にした。
第１図は本発明の一実施例によるタスクスケジューラの
処理概要図、第２図はタスクの状態遷移図、第３図はタ
スクスケジューラの処理の流れ図、第４図はリソース占
有時の処理の流れ図、第５図はリソース解放時の処理の
流れ図、第６図はタスク中断処理の流れ図、第７図はデ
ィスパッチフラッグ設定の処理の流れ図である。 〔符号の説明〕 1.タスクスケジューラ、2.リソース使用中フラグ、3.リ
ソース待ちキュー、4.レディキュー、5.リソーステーブ
ル、10.レディ状態、11.リソース非占有実行状態、12.
リソース占有実行状態、13.リソース待ち状態、14.リソ
ース占有中断状態、20.ディスパッチフラグ。
処理概要図、第２図はタスクの状態遷移図、第３図はタ
スクスケジューラの処理の流れ図、第４図はリソース占
有時の処理の流れ図、第５図はリソース解放時の処理の
流れ図、第６図はタスク中断処理の流れ図、第７図はデ
ィスパッチフラッグ設定の処理の流れ図である。 〔符号の説明〕 1.タスクスケジューラ、2.リソース使用中フラグ、3.リ
ソース待ちキュー、4.レディキュー、5.リソーステーブ
ル、10.レディ状態、11.リソース非占有実行状態、12.
リソース占有実行状態、13.リソース待ち状態、14.リソ
ース占有中断状態、20.ディスパッチフラグ。
Claims (2)
- 【請求項１】主メモリを共用する複数のプロセッサを有
するマルチプロセッサシステム上で、共通のリソースを
交互に排他使用する複数のタスクをスケジュールするた
めのタスクスケジュール方法において、プロセッサ上で
実行中のタスクが前記リソースの使用を終了したことに
応じて、タスク切り替えのオーバヘッドとタスクのリソ
ース占有、開放の一周期の処理のオーバヘッドとの比が
予め与えられた値を越えるか否か判定し、該判定の結
果、前記オーバヘッドの比が前記予め与えられた比より
も大きい場合に、前記リソースを開放したタスクを継続
して前記プロセッサ上で実行させ、前記オーバヘッドの
比が前記予め与えられた比よりも小さい場合に、前記タ
スクの実行を中断し、他のタスクを実行させることを特
徴とするタスクスケジュール方式。 - 【請求項２】前記リソースの使用待ちの状態にあるタス
クが存在する場合、前記他のタスクとして、前記リソー
ス待ちのタスクを優先的に割り当てることを特徴とする
特許請求の範囲第１項記載のタスクスケジュール方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP25821086A JPH0782444B2 (ja) | 1986-10-31 | 1986-10-31 | タスクスケジユ−ル方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP25821086A JPH0782444B2 (ja) | 1986-10-31 | 1986-10-31 | タスクスケジユ−ル方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPS63113738A JPS63113738A (ja) | 1988-05-18 |
| JPH0782444B2 true JPH0782444B2 (ja) | 1995-09-06 |
Family
ID=17317044
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP25821086A Expired - Fee Related JPH0782444B2 (ja) | 1986-10-31 | 1986-10-31 | タスクスケジユ−ル方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0782444B2 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US12487849B2 (en) | 2022-05-17 | 2025-12-02 | Toyota Jidosha Kabushiki Kaisha | Resource management device, method, and computer program for resource management |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN121411409B (zh) * | 2025-12-26 | 2026-03-13 | 大连致胜科技有限公司 | 一种车载域控的智能测试设备协同控制系统 |
-
1986
- 1986-10-31 JP JP25821086A patent/JPH0782444B2/ja not_active Expired - Fee Related
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US12487849B2 (en) | 2022-05-17 | 2025-12-02 | Toyota Jidosha Kabushiki Kaisha | Resource management device, method, and computer program for resource management |
Also Published As
| Publication number | Publication date |
|---|---|
| JPS63113738A (ja) | 1988-05-18 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3678414B2 (ja) | 多重プロセッサ・システム | |
| US6779182B1 (en) | Real time thread dispatcher for multiprocessor applications | |
| JP2005508550A (ja) | ダイナミックランダムアクセスメモリデバイスへの要求をスケジュールする方法及び装置 | |
| JPH0782444B2 (ja) | タスクスケジユ−ル方式 | |
| JP2667575B2 (ja) | タスクスケジューリング方式 | |
| JPH0644234B2 (ja) | タスク管理装置 | |
| JPS636655A (ja) | タスクスケジユ−ル方式 | |
| JPS62290958A (ja) | タスクスケジユ−ル方式 | |
| JPH0640315B2 (ja) | 中央処理装置割り当て制御方式 | |
| JPH1074150A (ja) | プロセススケジューリング方法ならびにそのためのプロセススケジューリング装置およびプログラム記憶媒体 | |
| JPS63300326A (ja) | トランザクション実行スケジュ−ル方式 | |
| JPS6316775B2 (ja) | ||
| JPH0612394A (ja) | プロセススケジュール方式 | |
| JPH11249917A (ja) | 並列型計算機及びそのバッチ処理方法及び記録媒体 | |
| JPH0586574B2 (ja) | ||
| WO1992003783A1 (en) | Method of implementing kernel functions | |
| JPH03182937A (ja) | マルチタスクシステムのタスク管理機構 | |
| JPS63301332A (ja) | ジョブ実行方式 | |
| JPH09282185A (ja) | リアルタイムシステムおよびその資源管理方法 | |
| WO1992003784A1 (en) | Scheduling method for a multiprocessing operating system | |
| JPS62271147A (ja) | タスク制御方法 | |
| JPS5924349A (ja) | マルチタスク計算機システムのタスクスケジユ−ル方式 | |
| JPH0128418B2 (ja) | ||
| JPS6079461A (ja) | 負荷分散方式 | |
| JPH08272728A (ja) | 中央処理装置の使用権配分最適化方法及び中央処理装置の使用権配分最適化システム |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |