プログラミング備忘録
プログラミングの問題を記録する予定
スポンサーサイト
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
--------(--:--) :
スポンサー広告
:
このページのトップへ
デッドロック検出
デッドロックの検出。与えられたロック順序がデッドロックを起こしうるかどうかを判定する。
判定だけ。今後の課題は人間に優しい出力にすることと、1スレッドに1つのロック順序しかないことを前提としている部分の修正。
実際の実行環境においてどれだけレアなケースであっても検出できることが強み。
これだけだと拾えないケースもある。
#include
#include
#include
#include
#include
using namespace std;
typedef int SyncObjectIndex;
typedef int LockedObjectMaps;
typedef vector
LockLine;
typedef pair
Node;
#define SYNC_OBJECT_MAX 32
bool check( vector
lockLines )
{
typedef set
NodeSet;
typedef map
AdjacentMap;
typedef map
CommonNodeMap;
NodeSet nodes;
AdjacentMap adjacent;
NodeSet commonNode[SYNC_OBJECT_MAX];
NodeSet childNode[SYNC_OBJECT_MAX];
Node rootNode(-1,0);
for( int i = 0; i < lockLines.size(); ++i )
{
Node prev = rootNode;
Node node(0,0);
for( int j = 0; j < lockLines[i].size(); ++j )
{
SyncObjectIndex obj = lockLines[i][j];
node.first = obj;
if( (1<
{
continue;
}
nodes.insert( node );
adjacent[prev].insert( node );
commonNode[obj].insert( node );
if( prev != rootNode )
{
childNode[prev.first].insert( node );
}
prev = node;
node.second |= 1 << obj;
}
}
for( SyncObjectIndex parent = 0; parent < SYNC_OBJECT_MAX; ++parent )
{
for( NodeSet::iterator i = commonNode[parent].begin(); i != commonNode[parent].end(); ++i )
{
for( NodeSet::iterator j = childNode[parent].begin(); j != childNode[parent].end(); ++j )
{
if( (i->second&j->second) != 0 || *i == *j )
{
continue;
}
adjacent[*i].insert(*j);
}
}
}
for( NodeSet::iterator i = nodes.begin(); i != nodes.end(); ++i )
{
for( NodeSet::iterator j = nodes.begin(); j != nodes.end(); ++j )
{
if( adjacent[*j].find(*i) != adjacent[*j].end() )
{
for( NodeSet::iterator k = nodes.begin(); k != nodes.end(); ++k )
{
if( adjacent[*i].find(*k) != adjacent[*i].end() )
{
adjacent[*j].insert(*k);
}
}
}
}
}
for( NodeSet::iterator i = nodes.begin(); i != nodes.end(); ++i )
{
if( adjacent[*i].find(*i) != adjacent[*i].end() )
{
return true;
}
}
return false;
}
int main()
{
LockLine ab; ab.push_back(0); ab.push_back(1);
LockLine ba; ba.push_back(1); ba.push_back(0);
LockLine bc; bc.push_back(1); bc.push_back(2);
LockLine ca; ca.push_back(2); ca.push_back(0);
LockLine dca; dca.push_back(3); dca.push_back(2); dca.push_back(0);
LockLine dbc; dbc.push_back(3); dbc.push_back(1); dbc.push_back(2);
LockLine ac; ac.push_back(0); ac.push_back(2);
LockLine abc; abc.push_back(0); abc.push_back(1); abc.push_back(2);
LockLine bca; bca.push_back(1); bca.push_back(2); bca.push_back(0);
LockLine cab; cab.push_back(2); cab.push_back(0); cab.push_back(1);
LockLine cba; cba.push_back(2); cba.push_back(1); cba.push_back(0);
{
vector
tmp;
tmp.push_back(abc);
tmp.push_back(bca);
cout << check(tmp) << endl;
}
{
vector
tmp;
tmp.push_back(ab);
cout << check(tmp) << endl;
}
{
vector
tmp;
tmp.push_back(ab);
tmp.push_back(ac);
cout << check(tmp) << endl;
}
{
vector
tmp;
tmp.push_back(ab);
tmp.push_back(ba);
cout << check(tmp) << endl;
}
{
vector
tmp;
tmp.push_back(cab);
tmp.push_back(cba);
cout << check(tmp) << endl;
}
{
vector
tmp;
tmp.push_back(ab);
tmp.push_back(bc);
tmp.push_back(ca);
cout << check(tmp) << endl;
}
{
vector
tmp;
tmp.push_back(ab);
tmp.push_back(dbc);
tmp.push_back(dca);
cout << check(tmp) << endl;
}
return 0;
}
スポンサーサイト
2010-10-23(19:32) :
マルチスレッド
:
コメント 0
:
トラックバック 0
このページのトップへ
前の記事
«
ホーム
»
次の記事
トラックバック
この記事にトラックバックする(FC2ブログユーザー)
このページのトップへ
コメントの投稿
名前
タイトル
メールアドレス
URL
本文
パスワード
非公開コメント
管理者にだけ表示を許可する
このページのトップへ
« 前の記事
ホーム
次の記事 »
このページのトップへ
検索フォーム
ユーザータグ
ICPC
2009
国内予選
ゲームプログラミング
カテゴリ
未分類 (1)
ICPC 国内予選 (9)
ICPC アジア地区予選 (2)
TopCoder (5)
ゲーム (1)
マルチスレッド (2)
アロケータ (12)
データ構造 (9)
メモリデバッガ (2)
メモリ (1)
tips (1)
アセンブラ (1)
最新記事
大小比較の関数の最適化 (04/09)
赤黒木 高速化版 (02/04)
C++での簡易コルーチン(2) (08/17)
C++での簡易コルーチン (08/16)
FixedAllocator メモ (01/07)
月別アーカイブ
2013/04 (1)
2013/02 (1)
2012/08 (2)
2012/01 (5)
2011/12 (1)
2011/11 (3)
2011/05 (2)
2011/02 (1)
2011/01 (1)
2010/12 (4)
2010/11 (4)
2010/10 (2)
2010/09 (1)
2010/08 (7)
2010/07 (1)
2010/06 (1)
2010/05 (1)
2010/04 (1)
2009/08 (2)
2009/07 (5)
最新コメント
最新トラックバック
リンク
管理画面
このブログをリンクに追加する
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。