JPH02226427A - タスクの終了判定方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） 本発明は、並列に動作するタスク群によって実現される
仕事の終了判定方法に関する。

（従来の技術） 近年、計算機システムに関する要求の多様化および技術
の高度化にともなって、システムが大規模化かつ複雑化
する傾向があり、分散して各種タスクを実行する処理シ
ステムの需要が高まっている。

このようなシステムにおいては、タスクは自由に任意の
数の子タスクを生成し仕事を子タスクに引き継ぐので、
子タスクおよび子タスクが再帰的に生成する子孫タスク
の終了を知る機能が必要になる。このために、従来では
集中管理方式がとられた。この集中管理方式では、タス
ク管理部を設け、タスクはタスク管理部に対して、子タ
スク生成の依頓、タスク終了の通知を行い、タスク管理
部から子孫タスクの終了通知を受けるものである。

（発明が解決しようとする課題） ところで、このような集中管理方式では、タスク数の増
大に伴う管理オーバヘッドの増大を招いたり、集中管理
の故障がシステムダウンにつながるといった分散システ
ムの特徴を損なう原因になるという問題が生じる。

本発明はこのような問題点に鑑みてなされたもので、そ
の目的とするところは集中管理部を用いずにタスクの仕
事の終了を判定するタスク終了判定方法を提供すること
にある。

［発明の構成］ （課題を解決するための手段） 前記目的を達成するために、第１の発明はツリー状のタ
スク群の初代のタスクの重みをＯでない整数Ｘとする過
程と、もととなるタスクから分岐するタスクの重みを（
前記もととなるタスクの重み）×（分岐の数）で算出す
る過程と、あるタスクから分岐しているタスクのうち末
端のタスクの重みの逆数の和が、前記あるタスクの重み
の逆数に一致すると前記あるタスクの終了と判定する過
程と、を具備することを特徴とするタスクの終了判定方
法である。

また第２の発明はツリー状のタスク群の最大分岐数Ｎを
検出する過程と、第０代のタスクの重みρをρ−（Ｎ）
　　　として算出する過程と、各タスクｉに対してＭｌ
　−Ｎ−（そのタスクの分岐数）を算出する過程と、末
端以外のタスクｌに対してその子タスクの重みρｌとし
、ｍ−Σ（１／ρｉｘ　Ｍ　ｉ　）を算出する過程と、
末端のタスクｉに対してＬ−Σ１／ρを算出する過程と
、Ｌ十ｍが１と一致すると、タスクの終了と判定する過
程と、を具備することを特徴とするタスクの終了判定方
法である。

（作用） 第１の発明は仕事全体の終了を判定するのではなく、仕
事の一部分の終了を判定することができる。

第２の発明ではできるだけ少ない負荷、すなわちできる
だけ少ない記憶領域の消費でタスクの終了を判定できる
。

（実施例） 以下図面に基づいて本発明の実施例を詳細に説明する。

第１図は本発明の一実施例が適用される計算機システム
の構成図である。同図に示されるようにサイトｌａ、ｌ
ｂ・・・が−列に接続された構成となっており、各サイ
ト例えばサイト１ａは演算回路３ａ、タスク制御装置Ｉ
￥５ａ、タスク情報管理装置７ａ、タスクの仕事終了判
定装置９ａを具０１する。

演算回路３ａ、３ｂ・・・はタスクを実行するものであ
る。

タスク制御装置５ａ、５ｂ・・・はタスクの制御を行っ
たり、終了通知の交換を行ったりする。

タスク情報管理装置７ａ、７ｂ・・・はタスク情報を管
理するものである。

第２図はこのタスク情報管理装置７ａ・・・によって記
憶されるタスク情報テーブルのフォーマットを示す。同
図に示されるようにこのタスク情報テーブルにはタスク
名、タスクの重み、タスクの終了通知先−覧が書込まれ
る。

タスクの仕事終了判定装置９ａ％　９ｂ・・・はタスク
の仕事の終了判定を行うもので、第３図に示すようなタ
スクの終了判定テーブルを記憶している。

このタスクの仕事終了判定テーブルにはタスク名、終了
時値、現在値が書込まれるが、現在値は分数の形で分子
、分母が別々に記憶されるので、現在値の更新時に除算
、小数の使用を避けることができ、丸め誤差を排除でき
る。

第４図は本実施例におけるタスク群を示すもので、同図
に示されるようにタスク１、タスク１１、タスク１２、
タスク１１１、タスク１１２、タスク１１３がツリー状
に形成される。

すなわち、タスク１はタスク１１．１２の２個の子タス
クに仕事を分割して引き継ぎ、終了し、さらにタスク１
１はタスク１１１、タスク１１２、タスク１１３の３個
の子タスクに仕１１を分割して引き継ぎ、終了するが、
タスク１２、タスク１１１、タスク１１２、タスク１１
３は子タスクに仕事を引き継がずに終了する。

また、タスク１．１２．１１２はサイト１ａで実行され
、タスク１１．１１１．１１３はサイト１ｂで実行され
る。

この時、なんらかの理由でタスク１の仕事の終了判定が
必要ならば、タスク１を実行したサイト〕ａのタスクの
仕事終了判定装置９ａは、タスク１の全子孫タスクが終
了した時、すなわちタスク１．１１．１２．１１１．１
１２．１１３の６タスク全てが終了したときに、タスク
１の仕事が終了したと判断する。

以下このような動作をフローチャートに従って詳細に説
明する。

第５図はタスクの起動時におけるタスク情報管理装置７
ａ、７ｂ・・・の動作を示すフローチャートであり、第
６図はタスクの起動時におけるタスクの仕事終了判定装
置９ａ、９ｂ・・・の動作を示すフローチャートであり
、第７図はタスクが子タスクに仕事を引き継いで終了す
る時のタスク制御装置５　ａ　ｓ　５　ｂ・・・の動作
を示すタローチャートであり、第８図はタスクが子タス
クに仕事を引き継いで終了する時のタスク情報管理装置
７ａ、７ｂ・・・の動作を示すフローチャートであり、
第９図はタスクが子タスクに仕事を引き継いで終了する
時のタスクの仕事終了判定装置９ａ、９ｂ・・・の動作
を示すフローチャートである。

まず、初代のタスク１の重みの値Ｘとして１、終了通知
が必要なタスク名が無い状態（この状態はタスク１が仕
事の終了判定が必要なタスクの子孫タスクでは無い場合
に起こり得る）で、サイト１ａで起動されたとすると、
タスク１の起動時にサイト１ａのタスク情報管理装置７
ａが第１０図に示すようにタスク情報管理テーブルにタ
スクの重みの値として「１」、終了通知が必要なタスク
名無しとして登録する（ステップ５０１）。

同時に、サイト１ａのタスクの仕事終了判定装置９ａが
、タスク］が仕事の終了判定が必要であるので（ステッ
プ６０１）、第１１図に示すようにタスクの仕事判定テ
ーブルにタスク１の仕事終了判定情報として、終了時値
にタスク１の重みの値である「１」を登録し、現在値と
して「０」を分子「０」、分母「１」の形で登録する（
ステップ６０２）。

この現在値は、将来タスク１の子孫タスクが終了する度
に更新され、現在値が終了時値と等しくなったときに仕
事が終了したと判定するためのものである。

その後、タスク１の処理が済むと、タスク１１、タスク
１２に仕！１「を引き継いでタスク１を終了する要求が
タスク１からタスク制御装置５　ａに出され、タスク制
御装置５ａは、タスク１の重みの値と、終了の通知先を
タスク情報管理装置７ａとに聞き（ステップ７０１）、
それに答えてタスク情報管理装置７ａが重みの値として
「１」、終了の通知先は無いことを返す（ステップ８０
１）。この時、さらにタスク情報管理装置７ａは、タス
ク１に関する情報をタスク管理情報より削除する（ステ
ップ８０２）。

タスク制御装置５ａは、タスク１の重みと終了通知先を
受は取ると、子タスクに仕事を引き継ぐので（ステップ
７０２）、タスク１１、タスク１２の重みの値をタスク
１の重みの値であるｒｌＪに起動する子タスクの数であ
る「２」を乗じた「２」としくステップ７０３）、タス
ク１は仕づ［の終了判定が必要であるので（ステップ７
０４）終了通知先タスク名をサイト１ａのタスク１とし
て（ステップ７０５）、タスク１１、タスク１２を起動
する（ステップ７０７）。（この時、タスク１１はサイ
ト１ｂのタスク’４ｒＱ　？ａ　装置５ｂ通じてサイト
１ｂで起動し、タスク１２はサイト１ａで起動したとす
る。） タスク１１の起動時には、サイト１ｂのタスク情報管理
装置７ｂによって、第１２図に示されるようにタスク情
報テーブルにタスク１１の情報がタスクの重みの値「２
」、終了通知が必要なタスク名がタスク１として登録さ
れる（ステップ５０１）。また、この場合はタスク１１
は仕事の終了判定が必要なタスクではないので、サイト
１ｂのタスクの仕事終了判定装置９ｂにおいては、なに
も行われない（ステップ６０２）。

その後タスク１１の処理が済むと、タスク１１１とタス
ク１１２とタスク１１３に仕艷Ｎを引き継いでタスク１
１を終了する要求がタスク１１からタスク制御装置５ｂ
に出され、タスク制御装置５ｂは、タスク１１の重みの
値と、終了の通知先をタスク情報管理装置７ｂに聞き（
ステップ７０１）工みの値として「２」、終了の通知先
としてサイト１ａのタスク１を得る（ステップ８０１）
。この時、タスク情報管理装置５ｂでは、タスク１１に
関する情報をタスク管理情報より削除する（ステップ８
０２）。

タスク１１の重みと終了通知先を受は取ったタスク制御
装置５ｂは、子タスクに仕事を引き継ぐので（ステップ
７０２）、タスク１１１、タスク１１２、タスク１１３
の重みの値をタスク１１の重みの値である「２コに起動
する子タスクの数である「３」を乗じた「６」としくス
テップ７０３）タスク１１は仕事の終了判定が必要でな
いので（ステップ７０４）、終了通知先タスク名を変更
せずにサイト１ａのタスク１として（ステップ７０６）
、タスク１１１、タスク１１２、タスク１１３を起動す
る（ステップ７０７）。（この時、タスク１１１とタス
ク１１３はサイト１ｂのタスク制御装置５ｂを通じてサ
イト１ｂで起動し、タスク１１２はサイト１ａで起動し
たとする）一方、タスク１２の起動時にもタスク１１の
場合と同様な操作が行われるが、タスク１２の処理が済
むと、子タスクに仕事を引き継がずにタスク１２を終了
するので、タスク制御装置５ａは、まずタスク１１の場
合と同様にタスク１１の重みの値と、終了の通知先をタ
スク情報管理装置７ａに聞き（ステップ７０１）　、重
みの値として「２」、終了の通知先としてサイト１ａの
タスク１を得る（ステップ８０１）。この時、タスク情
報管理装置７ａでは、タスク１１に関する情報をタスク
管理情報より削除する（ステップ８０２）。

次に、タスク１２の場合は子タスクに仕１ｔを引き継が
ないので（ステップ７０２）、子タスクの起動は行わず
に、サイトｌａ（自サイト）のタスク１にタスク１２の
終了通知としてタスク１２の重みである値「２」を送る
（ステップ７０８）。

すると、サイト１ａのタスクの仕事終了判定装置９ａに
おいて第１３図に示されるようにタスク１の現在値０／
１に、通知された値の逆数である１／２を加えた値を通
分演算により求めて分子を「１」、分母を「２」とする
（ステップ９０１）。

この値は、終了時値の１と等しくないので（ステップ９
０２）、まだタスク１の仕事は終了したと判断されない
。

タスク１１１、タスク１１２、タスク１１３に関しては
、タスク終了時に、サイト１ａのタスク１に各タスクの
終了通知として、タスクの重みである値「６」がそれぞ
れ送られる。これらの終了通知として送られた値は、サ
イト１ａのタスクの仕事終了判定装置９ａにおいてタス
ク１の現在値に加えられて、分子「２」分母「３」、分
子「５」分母「６」と現在値が変化し、最後に分子「１
」分母「１」になったときに終了時値である「１」と現
在値が等しくなったので（ステップ９０２）、タスク１
の仕事が終了したと判定される（ステップ９０３）。

以上の動作を第１４図によって簡単に要約して説明する
。タスク１の重みＸとして「１」が用いられる。タスク
１は分岐の数が「２」であるので、タスク１１およびタ
スク１２の重みが「２」となる。タスク１１は分岐の数
が「２」であるので、タスク１１１．１１２．１１３の
重みはタスク１１の重み「２」に分岐の数「３」をかけ
た「６」となる。

末端のタスクであるタスク１２．１１１．１１２．１１
３はそれぞれ子タスクがないので、タスクが終了したか
否かは、これらのタスクの重みの逆数を加え合せる。す
な１っち、 １／２＋１／６＋１／６＋１／６を計算すると「１」と
なるので、これらのタスクの重みの逆数の和がｒｌＪ　
　（−１／Ｘ）で、タスクの仕事が終了したと判定され
る。

このように本実施例によれば、集中管理部を介在せずに
任意のサイトのタスクの仕事の終了判定を行うことがで
きるので、従来のように集中管理部の故障がシステムダ
ウンにつながるといった不都合を回避することができる
。

また、第４図に示すツリー状のタスクにおいて、途中の
タスク１１の仕事が終了したことを判定することもでき
る。この場合、タスク１１の重みは「２」であり、タス
ク１１１．１１２．１１３の重みはそれぞれ「６」であ
ることには変わりがない。タスク１１の仕す「の終了判
定には、タスク１１１．１１２．１１３の重みの逆数の
和がタスク１１の重みの逆数に一致したか否かで判定す
る。

すなわち、タスク１１１．１１２．１１３の重みはそれ
ぞれ「６」であり、 １／６＋１／６＋１／６を計算すると「１／２」となり
、これがタスク１１の重みの逆数と一致するので、この
時点でタスク１１の仕事が終了したものと判定する。

このように本実施例では、仕事全体の終了のみでなく仕
事の一部分（部分仕事）を処理する任意かつ複数のタス
クの部分仕事終了を判定することができる。

第１５図は別のツリー状のタスク群を示すもので、第４
図に示すものに比してタスク１２の子タスクとしてタス
ク１２１．１２２．１２３．１２４．１２５が存在して
いる場合を示しおり、他の実施例では、このようなツリ
ー状のタスクの終了の判定を行なうものである。第１５
図に示すツリー状のタスク群のなかで最大の分岐数Ｎは
タスク１２の「５」である。従ってタスク１の正みρを
「１」とし、第２世代のタスク１１．１２の重みρは「
５」となり、第３世代のタスク１１１．１１２．１１３
．１２１．１２２．１２３．１２４．１２５の重みρは
５Ｘ５−２５となる。

第１７図の右欄は他の実施例によるタスクの終了判定方
法を示すものであり、この図に従って説明する。（尚、
第１７図の左欄は第１の発明による終了判定を示すもの
である。） タスク１においては、２つの分岐があるので（最大分岐
数）−（自らの分岐数）を引いたＭｌとして、 が終了タスク個数となる。そして、タスク１の子タスク
の重みは「５」であるので、現在値の分子分母の値を「
３」、「５」とする。

タスク１１において、自らの分岐数が「３」であるので
最大分岐数−自らの分岐数の値はＭｌは、となり、終了
タスク個数が「２」となる。また、タスク１１の子タス
クの工みは２５である。そして、タスク１における現在
値３１５にこの２／２５を加えた１　７／２５が現在値
（−ｍ　）記憶される。

タスク１２においては、自らの分岐数が「５」であるの
で最大分岐数−自らの分岐数の値Ｍｉが「０」となるの
で、終了タスク個数も「０」となる。したがって現在値
（−ｍ）は、ｒｌ　７／２５Ｊのままである。

末端のタスク１１１．１１２、・・・１２５の重みはそ
れぞれ「２５」であるので、現在１ｉ１１７／２５（−
ｍ）に各タスクの正みの逆数ｒｌ／２５Ｊが順次演算さ
れる。

そして、タスク１２５が終了した場合には、現在値は２
５／２５−１となる。

したがって現在値が「１」となった時点で、このタスク
群の仕事が終了したとみなす。

第１６図は本実施例におけるタスク制御装置の動作を示
すフローチャートであり、第７図に示す実施例に対して
ステップ１７０３が変更され、さらにステップ１７０８
が追加かされる。

ステップ１７０３はタスクの重みを演算する過程であり
、子タスクの重みに１タスク最大分割数（この場合「５
」）を乗じた値を子タスクの重みとするものである。

また、ステップ１７０８は自タスク終了通知先のサイト
のタスクの仕事終了判定装置に、子タスクの重みを１タ
スク最大分割数から起動した子タスクの数を減した個数
を送るものである。

本実施例の場合、終了値を通知先に送るフォーマットは
第１８図に示されるように、個数（終了タスク個数）が
追加される。

本実施例では、タスク１の現在値の分母を記憶するのに
必要な領域は最大値が「２５」であるので、１０ｇ２２
５ビツトですみ、第１の発明および第２の発明の実施例
では、最大値が「３０」となるので、１０ｇ２３０ビツ
ト必要であったのに比べて少なくなる。この記憶領域縮
小の効果は、子タスクへの分割の数が種々に変化する場
合、特に互いに索の関係にある数が多数歯まれた場合に
著しい。

［発明の効果コ 以上詳細に説明したように第１から第２の発明によれば
、集中管理部を介在せずに任意のサイトのタスクの仕事
の終了を判定できるので、従来のように集中管理部の故
障がシステムダウンにつながるといった不都合を回避す
ることができる。また、第１の発明によれば、仕事全体
の終了のみでなく、仕事の一部分を処理する任意かつ複
数のタスクの部分仕事終了を判定することができる。ま
た、第２の発明によれば同一の効果をできるだけ少ない
負荷をできるだけ少ない記憶領域の消費で行える。

【図面の簡単な説明】

第１図は本発明の実施例が適用される計算機システムの
構成を示すブロック図、第２図はタスク情報テーブルの
フォーマット図、第３図はタスクの仕事判定テーブルの
フォーマット図、第４図はツリー状のタスクの例を示す
図、第５図〜第９図は実施例の動作を示すフローチャー
ト、第１０図および第１２図は実施例の動作中のタスク
情報テーブルを示す図、第１１図および第１３図は実施
例動作中のタスクの仕事終了判定テーブルを示す図、第
１４図は実施例の概要を示す説明図、第１５図は別のタ
スク群の構成を示す図、第１６図は第２の発明の動作を
示すフローチャート、第１７図は第１５図に示すタスク
を実行した場合におけるタスクの終了判定を示す説明図
、第１８図は第２の発明における終了値を通知先に送る
時のフォーマット図である。 １ａ、１ｂ・・・・・・・・・サイト ３ａ、３ｂ・・・・・・・・・演算回路５ａ、５ｂ・・
・・・・・・・タスク制御装置７ａ、７ｂ・・・・・・
・・・タスク情報管理装置９ａ、９ｂ・・・・・・・・
・タスクの仕事終了判定装置出願人　　　　　　株式会
社　東芝

Claims (2)

【特許請求の範囲】
1. （１）ツリー状のタスク群の初代のタスクの重みを０で
   ない整数Ｘとする過程と、 もととなるタスクから分岐するタスクの重みを（前記も
   ととなるタスクの重み）×（分岐の数）で算出する過程
   と、 あるタスクから分岐しているタスクのうち末端のタスク
   の重みの逆数の和が、前記あるタスクの重みの逆数に一
   致すると前記あるタスクの終了と判定する過程と、 を具備することを特徴とするタスクの終了判定方法。
2. （２）ツリー状のタスク群の最大分岐数Ｎを検出する過
   程と、 第ｎ代のタスクの重みρを ρ＝（Ｎ）＾ｎ＾−＾１ として算出する過程と、 各タスクｉに対して Ｍｉ＝Ｎ−（そのタスクの分岐数） を算出する過程と、 末端以外のタスクｉに対してその子タスクの重みρｉと
   し、 ｍ＝Σ（１／ρｉ×Ｍｉ） を算出する過程と、 末端のタスクｉに対して Ｌ＝Σ１／ρを算出する過程と、 Ｌ＋ｍが１と一致すると、タスクの終了と判定する過程
   と、 を具備することを特徴とするタスクの終了判定方法。