3 0 0 0 大規模分散システムのためのグループメンバシップ・プロトコル
分散システムにおいて、複数のプロセスやプロセッサをメンバとして一括して制御、管理するグループ機構は、負荷分散やファイルレプリケーション等のシステムレベルのサービスから、分散データベース、グループウェア等のアプリケーションに至るまで、重要な用途を持つ。本論文では、グループは動的に変化し、グループの生成、消滅、メンバの加入、削除を繰り返すものとする。そのため、各メンバが、所属グループの最新のメンバシップを把握し、そのメンバシップを更新できる操作が必要となる。以下では、大規模広域分散システムへの適用を想定し、(1)大域的なロックやタイムスタンプを用いない、(2)メッセージの送受信順序の不一致に対応する、(3)特定の制御メンバを必要としない(完全分散型)、(4)更新操作は非封鎖型である、ことを特徴としたグループメンバシップ・プロトコルの方式を提案する。
2 0 0 0 OA 左再帰に対応するPackrat Parserの実装
- 著者
- 後藤 勇太 木山 真人 芦原 評
- 雑誌
- 夏のプログラミング・シンポジウム2011報告集
- 巻号頁・発行日
- pp.49-55, 2012-01-06
構文解析法でPackrat Parsingという手法がある.Packrat Parsingは,再帰下降構文解析にメモ化を組み合わせた手法であり,バックトラックや無限先読みを用いた解析において,線形時間で解析可能である.しかし,左再帰を含む文法は解析不可能である.そこで,従来は左再帰を含む文法を解析する際,左再帰部分を等価な右再帰に変換し,解析を行っていた.だが文法の変換を行うと構文木の構造が変化してしまう.また,特定の左再帰は変換できない.たとえば,閉路が存在する文法である.よって,この手法では解析できない文法がある.Alessandro Warthらは,左再帰を含む文法を,右再帰への変換無しに解析を可能にした.しかし,Alessandroらの手法では,同一の入力位置で左再帰が複数発生する文法において,特定の入力の解析に失敗する.そこで本研究では,左再帰を含む文法を右再帰への変換無しに解析でき,かつ従来手法の問題点に対応するPackrat Parserを提案・実装し,評価を行った.
2 0 0 0 OA 大規模並列システムにおける大域的ページ配置方針の性能評価
- 著者
- 宮田 忠明 正木 宏和 芦原評 清水謙多郎
- 雑誌
- 情報処理学会研究報告システムソフトウェアとオペレーティング・システム(OS)
- 巻号頁・発行日
- vol.1997, no.77(1997-OS-076), pp.73-78, 1997-08-21
本論文では,分散メモリ型大規模並列システムにおける大域的ページ配置方針について論じる.各ノードの主記憶を仮想記憶の一時的な退避先として割り当てる大域的ページ配置方式は,従来の仮想記憶におけるディスクアクセスをより高速なノード間のメモリアクセスに置き換えることができる.限定されたノードにしかディスクを持たない大規模並列システムでは,大域的ページ配置は特に有効と考えられる.本論文では,状態情報の収集,置き換えページの選択,ページを転送するノードの選択などについて,大規模システムを想定した大域的ページ配置の様々な方針を提案し,これらの性能をシミュレーションを用いて比較・評価する.
- 著者
- 後藤 勇太 白田 佳章 木山 真人 芦原 評
- 出版者
- 情報処理学会
- 雑誌
- 情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)
- 巻号頁・発行日
- vol.4, no.3, pp.84-93, 2011-06-29
構文解析法で Packrat Parsing という手法がある.Packrat Parsing は,再帰下降構文解析にメモ化を組み合わせた手法であり,バックトラックや無限先読みを用いた解析において,線形時間で解析可能である.しかし,左再帰を含む文法は解析不可能である.そこで,従来は左再帰を含む文法を解析する際,左再帰部分を等価な右再帰に変換し,解析を行っていた.だが文法の変換を行うと構文木の構造が変化してしまう.また,特定の左再帰は変換できない.たとえば,閉路が存在する文法である.よって,この手法では解析できない文法がある.Warth らは,左再帰を含む文法を,右再帰への変換なしに解析を可能にした.しかし,Warth らの手法では,同一の入力位置で左再帰が複数発生する文法において,特定の入力の解析に失敗する.また,構文木の構造が意図したものとは異なるという問題がある.そこで本研究では,更新検知を用いて,左再帰を含む文法を右再帰への変換なしに解析でき,かつ従来手法の 2 つの問題点に対応する Packrat Parser を提案・実装し,評価を行った.Packrat Parsing is a kind of parsing method. Packrat Parsing is a combination of Recursive Descent Parsing and memoization that can parse backtracking and unlimited look-ahead in linear parse time. However, Packrat Parsing cannot parse left recursive grammars. Thus, traditional method transforms left recursive grammars into right recursive grammars. Unfortunately, syntax tree is changed by the transforming. Moreover, particular left recursive grammars cannot be transformed. Traditional method cannot parse particular grammars. Warth, et al. made possible to support left recursive grammars without transforming in Packrat Parsing. However, the method cannot parse some grammars that have multiple left recursions at an input position. Furthermore, syntax tree is be unintended consequence when the method parses particular grammars. This paper presents imprementation and evaluation of Packrat Parser with Update Detection that possible to support left recursive grammars without transforming, and grammars that have multiple left recursions at an input position.
1 0 0 0 消費資源を含むシステムにおけるデッドロック検出
- 著者
- 芦原 評 清水 謙多郎
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会論文誌 (ISSN:18827764)
- 巻号頁・発行日
- vol.38, no.7, pp.1379-1388, 1997-07-15
- 参考文献数
- 9
特定の故障箇所が存在しないにもかかわらずシステムの永久停止をもたらすデッドロックは計算機システムにおける重要な問題である.デッドロック検出問題は,排他的に使用可能な資源群とそれを要求するプロセス群からなる一般資源システムの状態グラフ還元問題としてモデル化されるが,使用すると消滅する消費資源を含むシステムでのデッドロック検出問題は一般にはNP完全であり,その重要性にもかかわらず注目されることが少なかった.本論文では,消費資源を含むシステムに一定の制限を加えることで,3つのクラスにおいて多項式時間内でのデッドロック検出が可能であることを示す.Deadlock detection in computer systems can be modeled as a graph reduction problem of general resource systems,which consist of processes,reusable resources and consumable resources.Deadlock detection in reusable resource systems is well known.If all resources in the system are released after use,the problem has polynomial-time solutions.However,the problem is NP-complete in general resource systems with consumable resources,units of which vanish after use.This paper provides three special cases of systmes with consumable resources for which polynomial-time deadlock detection algorithms exist.It is shown that those three factors,(1) consumable resources with non-trivial selections in the allocation of currently available units,(2) processes which request more than one unit and (3) resources which wait for more than one process,are all necessary for the problem to be NP-complete.