デッドロック検出

デッドロックの検出。与えられたロック順序がデッドロックを起こしうるかどうかを判定する。
判定だけ。今後の課題は人間に優しい出力にすることと、１スレッドに１つのロック順序しかないことを前提としている部分の修正。
実際の実行環境においてどれだけレアなケースであっても検出できることが強み。

これだけだと拾えないケースもある。

<br /><br />#include <iostream><br />#include <vector><br />#include <map><br />#include <set><br />#include <stdlib.h><br /><br />using namespace std;<br /><br /><br />typedef int SyncObjectIndex;<br />typedef int LockedObjectMaps;<br /><br />typedef vector<SyncObjectIndex> LockLine;<br /><br />typedef pair<SyncObjectIndex,LockedObjectMaps> Node;<br /><br />#define SYNC_OBJECT_MAX 32<br /><br />bool check( vector<LockLine> lockLines )<br />{<br /> <br /> typedef set<Node> NodeSet;<br /> typedef map<Node,NodeSet> AdjacentMap;<br /> typedef map<SyncObjectIndex,NodeSet> CommonNodeMap;<br /> <br /> NodeSet nodes;<br /> AdjacentMap adjacent;<br /> NodeSet commonNode[SYNC_OBJECT_MAX];<br /> NodeSet childNode[SYNC_OBJECT_MAX];<br /><br /> Node rootNode(-1,0);<br /><br /> for( int i = 0; i < lockLines.size(); ++i )<br /> {<br /> Node prev = rootNode;<br /> Node node(0,0);<br /><br /> for( int j = 0; j < lockLines[i].size(); ++j )<br /> {<br /> SyncObjectIndex obj = lockLines[i][j];<br /><br /> node.first = obj;<br /><br /> if( (1<<obj) & node.second )<br /> {<br /> continue;<br /> }<br /><br /> nodes.insert( node );<br /> adjacent[prev].insert( node );<br /> commonNode[obj].insert( node );<br /><br /> if( prev != rootNode )<br /> {<br /> childNode[prev.first].insert( node );<br /> }<br /><br /> prev = node;<br /> node.second |= 1 << obj;<br /> }<br /> }<br /><br /> for( SyncObjectIndex parent = 0; parent < SYNC_OBJECT_MAX; ++parent )<br /> {<br /> for( NodeSet::iterator i = commonNode[parent].begin(); i != commonNode[parent].end(); ++i )<br /> {<br /> for( NodeSet::iterator j = childNode[parent].begin(); j != childNode[parent].end(); ++j )<br /> {<br /> if( (i->second&j->second) != 0 || *i == *j )<br /> {<br /> continue;<br /> }<br /><br /> adjacent[*i].insert(*j);<br /> }<br /> }<br /> }<br /><br /> for( NodeSet::iterator i = nodes.begin(); i != nodes.end(); ++i )<br /> {<br /> for( NodeSet::iterator j = nodes.begin(); j != nodes.end(); ++j )<br /> {<br /> if( adjacent[*j].find(*i) != adjacent[*j].end() )<br /> {<br /> for( NodeSet::iterator k = nodes.begin(); k != nodes.end(); ++k )<br /> {<br /> if( adjacent[*i].find(*k) != adjacent[*i].end() )<br /> {<br /> adjacent[*j].insert(*k);<br /> }<br /> }<br /> }<br /> }<br /> }<br /> <br /> for( NodeSet::iterator i = nodes.begin(); i != nodes.end(); ++i )<br /> {<br /> if( adjacent[*i].find(*i) != adjacent[*i].end() )<br /> {<br /> return true;<br /> }<br /> }<br /><br /> return false;<br />}<br /><br /><br />int main()<br />{<br /> LockLine ab; ab.push_back(0); ab.push_back(1);<br /> LockLine ba; ba.push_back(1); ba.push_back(0);<br /> LockLine bc; bc.push_back(1); bc.push_back(2);<br /> LockLine ca; ca.push_back(2); ca.push_back(0);<br /> LockLine dca; dca.push_back(3); dca.push_back(2); dca.push_back(0);<br /> LockLine dbc; dbc.push_back(3); dbc.push_back(1); dbc.push_back(2);<br /> LockLine ac; ac.push_back(0); ac.push_back(2);<br /> LockLine abc; abc.push_back(0); abc.push_back(1); abc.push_back(2);<br /> LockLine bca; bca.push_back(1); bca.push_back(2); bca.push_back(0);<br /> LockLine cab; cab.push_back(2); cab.push_back(0); cab.push_back(1);<br /> LockLine cba; cba.push_back(2); cba.push_back(1); cba.push_back(0);<br /><br /><br /> {<br /> vector<LockLine> tmp;<br /> tmp.push_back(abc);<br /> tmp.push_back(bca);<br /> cout << check(tmp) << endl;<br /> }<br /><br /><br /> {<br /> vector<LockLine> tmp;<br /> tmp.push_back(ab);<br /> cout << check(tmp) << endl;<br /> }<br /><br /> {<br /> vector<LockLine> tmp;<br /> tmp.push_back(ab);<br /> tmp.push_back(ac);<br /> cout << check(tmp) << endl;<br /> }<br /><br /> {<br /> vector<LockLine> tmp;<br /> tmp.push_back(ab);<br /> tmp.push_back(ba);<br /> cout << check(tmp) << endl;<br /> }<br /><br /> {<br /> vector<LockLine> tmp;<br /> tmp.push_back(cab);<br /> tmp.push_back(cba);<br /> cout << check(tmp) << endl;<br /> }<br /><br /> {<br /> vector<LockLine> tmp;<br /> tmp.push_back(ab);<br /> tmp.push_back(bc);<br /> tmp.push_back(ca);<br /> cout << check(tmp) << endl;<br /> }<br /><br /> {<br /> vector<LockLine> tmp;<br /> tmp.push_back(ab);<br /> tmp.push_back(dbc);<br /> tmp.push_back(dca);<br /> cout << check(tmp) << endl;<br /> }<br /><br /> return 0; <br />}<br />