From 0e6f616cea14987335a31ac4ecc9bb91a69f5e9e Mon Sep 17 00:00:00 2001 From: jmoore Date: Fri, 25 Jul 2008 03:30:52 +0000 Subject: adding deadlock avoidance protocol files --- ACE/ace/Basic_P_Strategy.cpp | 6 + ACE/ace/Basic_P_Strategy.h | 97 +++++++++++++++ ACE/ace/Basic_P_Strategy.inl | 37 ++++++ ACE/ace/DA_Strategy_Base.cpp | 5 + ACE/ace/DA_Strategy_Base.h | 181 +++++++++++++++++++++++++++ ACE/ace/DA_Strategy_Base.inl | 83 +++++++++++++ ACE/ace/Live_P_Strategy.cpp | 5 + ACE/ace/Live_P_Strategy.h | 55 +++++++++ ACE/ace/Live_P_Strategy.inl | 246 +++++++++++++++++++++++++++++++++++++ ACE/ace/k_Efficient_P_Strategy.cpp | 5 + ACE/ace/k_Efficient_P_Strategy.h | 188 ++++++++++++++++++++++++++++ ACE/ace/k_Efficient_P_Strategy.inl | 124 +++++++++++++++++++ 12 files changed, 1032 insertions(+) create mode 100644 ACE/ace/Basic_P_Strategy.cpp create mode 100644 ACE/ace/Basic_P_Strategy.h create mode 100644 ACE/ace/Basic_P_Strategy.inl create mode 100644 ACE/ace/DA_Strategy_Base.cpp create mode 100644 ACE/ace/DA_Strategy_Base.h create mode 100644 ACE/ace/DA_Strategy_Base.inl create mode 100644 ACE/ace/Live_P_Strategy.cpp create mode 100644 ACE/ace/Live_P_Strategy.h create mode 100644 ACE/ace/Live_P_Strategy.inl create mode 100644 ACE/ace/k_Efficient_P_Strategy.cpp create mode 100644 ACE/ace/k_Efficient_P_Strategy.h create mode 100644 ACE/ace/k_Efficient_P_Strategy.inl diff --git a/ACE/ace/Basic_P_Strategy.cpp b/ACE/ace/Basic_P_Strategy.cpp new file mode 100644 index 00000000000..7e7fdce2301 --- /dev/null +++ b/ACE/ace/Basic_P_Strategy.cpp @@ -0,0 +1,6 @@ +#include "ace/Basic_P_Strategy.h" + +#if !defined (__ACE_INLINE__) +//#include "ace/Basic_P_Strategy.inl" +#endif /* __ACE_INLINE__ */ + diff --git a/ACE/ace/Basic_P_Strategy.h b/ACE/ace/Basic_P_Strategy.h new file mode 100644 index 00000000000..4686c755f77 --- /dev/null +++ b/ACE/ace/Basic_P_Strategy.h @@ -0,0 +1,97 @@ +// -*- C++ -*- + +//============================================================================= +/** + * @file Basic_P_Strategy.h + * + * + * + * + * + * @author Paul Oberlin + */ +//============================================================================= + +#ifndef ACE_BASIC_P_STRATEGY_H +#define ACE_BASIC_P_STRATEGY_H + +#include /**/ "ace/pre.h" + +#include "ace/DA_Strategy_Base.h" + +#if !defined (ACE_LACKS_PRAGMA_ONCE) +# pragma once +#endif /* ACE_LACKS_PRAGMA_ONCE */ + +ACE_BEGIN_VERSIONED_NAMESPACE_DECL + +template +class Basic_P_Strategy : public DA_Strategy_Base { + + //The annotations consist of an identifier and a resource cost value + +public: + Basic_P_Strategy(int maxThreads); + virtual ~Basic_P_Strategy(); + virtual int is_deadlock_potential(AnnotationId handle); + virtual void grant(AnnotationId handle); + virtual void release(AnnotationId upcall_handle); +private: + int t_r; +}; + +ACE_END_VERSIONED_NAMESPACE_DECL + +//#if defined (__ACE_INLINE__) +//#include "ace/Basic_P_Strategy.inl" +//#endif /* __ACE_INLINE__ */ + + +template +ACE_INLINE +Basic_P_Strategy::Basic_P_Strategy(int maxThreads) +:DA_Strategy_Base(maxThreads), + t_r(maxThreads) +{ +} + +template +ACE_INLINE +Basic_P_Strategy::~Basic_P_Strategy() +{ + +} + +template +ACE_INLINE +int Basic_P_Strategy::is_deadlock_potential(AnnotationId handle) +{ + int annotation = get_annotation(handle); + if (annotation > t_r) + { + return annotation - t_r; + } + + return 0; +} + +template +ACE_INLINE +void Basic_P_Strategy::grant(AnnotationId handle) +{ + --t_r; +} + +template +ACE_INLINE +void Basic_P_Strategy::release(AnnotationId upcall_handle) +{ + ++t_r; +} + + + +#include /**/ "ace/post.h" + +#endif /* ACE_BASIC_P_STRATEGY_H */ + diff --git a/ACE/ace/Basic_P_Strategy.inl b/ACE/ace/Basic_P_Strategy.inl new file mode 100644 index 00000000000..67290328c14 --- /dev/null +++ b/ACE/ace/Basic_P_Strategy.inl @@ -0,0 +1,37 @@ + +template +ACE_INLINE +Basic_P_Strategy::Basic_P_Strategy(int maxThreads) +:DA_Strategy_Base(maxThreads), + t_r(maxThreads) +{ +} + +template +ACE_INLINE +Basic_P_Strategy::~Basic_P_Strategy() +{ + +} + +template +ACE_INLINE +bool Basic_P_Strategy::is_deadlock_potential(AnnotationId handle) +{ + int annotation = get_annotation(handle); + return !(annotation < t_r); +} + +template +ACE_INLINE +void Basic_P_Strategy::grant(AnnotationId handle) +{ + --t_r; +} + +template +ACE_INLINE +void Basic_P_Strategy::release(AnnotationId upcall_handle) +{ + ++t_r; +} diff --git a/ACE/ace/DA_Strategy_Base.cpp b/ACE/ace/DA_Strategy_Base.cpp new file mode 100644 index 00000000000..d0e484a700e --- /dev/null +++ b/ACE/ace/DA_Strategy_Base.cpp @@ -0,0 +1,5 @@ +#include "ace/DA_Strategy_Base.h" + +#if !defined (__ACE_INLINE__) +//#include "ace/DA_Strategy_Base.inl" +#endif /* __ACE_INLINE__ */ \ No newline at end of file diff --git a/ACE/ace/DA_Strategy_Base.h b/ACE/ace/DA_Strategy_Base.h new file mode 100644 index 00000000000..761f33a52ce --- /dev/null +++ b/ACE/ace/DA_Strategy_Base.h @@ -0,0 +1,181 @@ +// -*- C++ -*- + +//============================================================================= +/** + * @file DA_Strategy_Base.h + * + * + * + * The Deadlock Avoidance Strategy Base (DA_Strategy_Base) class + * is an abstract base class for Strategies that implement deadlock + * avoidance algorithms. This class provides interfaces for passing + * annotations for call graph annotations, number of available threads, as well + * as methods to determine whether a call is safe to make. + * + * + * @author Paul Oberlin + */ +//============================================================================= + +#ifndef DA_STRATEGY_BASE_H +#define DA_STRATEGY_BASE_H + +#include /**/ "ace/pre.h" +#include "ace/Hash_Map_Manager.h" +#include "ace/Thread_Mutex.h" +#include "ace/Atomic_Op_T.h" + +#if !defined (ACE_LACKS_PRAGMA_ONCE) +# pragma once +#endif /* ACE_LACKS_PRAGMA_ONCE */ + +class ACE_Event_Handler; + +template +class DA_Strategy_Base { + + public: + + //The annotations consist of an identifier and a resource cost value +typedef ACE_Hash_Map_Entry HASH_EH_ENTRY; + + +typedef ACE_Hash_Map_Manager_Ex, + ACE_Equal_To, + ACE_Thread_Mutex> HASH_ANNOTATIONS_MAP; + +typedef ACE_Hash_Map_Iterator_Ex, + ACE_Equal_To, + ACE_Thread_Mutex> HASH_ANNOTATIONS_ITER; + +typedef ACE_Hash_Map_Const_Iterator_Ex, + ACE_Equal_To, + ACE_Thread_Mutex> HASH_ANNOTATIONS_CONST_ITER; + +typedef ACE_Hash_Map_Reverse_Iterator_Ex, + ACE_Equal_To, + ACE_Thread_Mutex> HASH_ANNOTATIONS_REVERSE_ITER; + +typedef HASH_ANNOTATIONS_MAP Annotations_Table; + + + DA_Strategy_Base(int maxThreads); + virtual ~DA_Strategy_Base(); + + virtual int is_deadlock_potential(AnnotationId handle)=0; + virtual void grant(AnnotationId handle)=0; + virtual void release(AnnotationId upcall_handle)=0; + int get_max_threads() { return num_avail_threads_.value();} + HASH_ANNOTATIONS_CONST_ITER get_annotations_iter() const; + virtual int get_annotation (AnnotationId handle) const; + virtual int add_annotation (AnnotationId handle, int annotation); + virtual int remove_annotation (AnnotationId handle); + virtual int set_annotations_table (const HASH_ANNOTATIONS_REVERSE_ITER& table); + +private: + HASH_ANNOTATIONS_MAP annotations_repo_; + ACE_RW_Thread_Mutex lock_; + ACE_Atomic_Op num_avail_threads_; + +}; + +//#if defined (__ACE_INLINE__) +//#include "ace/DA_Strategy_Base.inl" +template +ACE_INLINE +DA_Strategy_Base::DA_Strategy_Base (int maxThreads) + :num_avail_threads_ (maxThreads) +{ +} + +template +ACE_INLINE +DA_Strategy_Base::~DA_Strategy_Base() +{ +} + +template +ACE_INLINE int +DA_Strategy_Base::get_annotation (AnnotationId id) const +{ + int annotation; + if (annotations_repo_.find (id, annotation) == -1) + return -1; + else return annotation; +} + +template +ACE_INLINE int +DA_Strategy_Base::set_annotations_table ( + const HASH_ANNOTATIONS_REVERSE_ITER& table) +{ + HASH_ANNOTATIONS_REVERSE_ITER iter(table); + int rc=0; + + for (;!(iter.done()); iter++) + { + rc = annotations_repo_.bind((*iter).ext_id_, (*iter).int_id_); + if (rc != 0) break; + } + + return rc; +} + +template +ACE_INLINE int +DA_Strategy_Base::add_annotation (AnnotationId id, int annotation) +{ + int rc; + if (annotation > num_avail_threads_.value()) { + rc = -1; + ACE_ERROR ((LM_ERROR, + ACE_TEXT ("%p.\n"), + ACE_TEXT ("DA_Strategy_Base annotation may not exceed number of threads"))); + } else { + rc = annotations_repo_.bind (id, annotation); + } + /* + ACE_DEBUG ((LM_DEBUG, "In add_annotation\n")); + HASH_ANNOTATIONS_CONST_ITER iter(annotations_repo_); + for (;!(iter.done()); iter++) + { + ACE_DEBUG ((LM_DEBUG, "%d-%d\n", (*iter).ext_id_, (*iter).int_id_)); + } + */ + return rc; +} + +template +ACE_INLINE ACE_Hash_Map_Const_Iterator_Ex, + ACE_Equal_To, + ACE_Thread_Mutex> +DA_Strategy_Base::get_annotations_iter() const +{ + + return annotations_repo_.begin(); +} + +template +ACE_INLINE int +DA_Strategy_Base::remove_annotation (AnnotationId id) +{ + return annotations_repo_.unbind (id); +} + + +//#endif /* __ACE_INLINE__ */ + +#include /**/ "ace/post.h" + +#endif /* DA_STRATEGY_BASE_H */ + diff --git a/ACE/ace/DA_Strategy_Base.inl b/ACE/ace/DA_Strategy_Base.inl new file mode 100644 index 00000000000..be3e999e798 --- /dev/null +++ b/ACE/ace/DA_Strategy_Base.inl @@ -0,0 +1,83 @@ +template +ACE_INLINE +DA_Strategy_Base::DA_Strategy_Base (int maxThreads) + :num_avail_threads_ (maxThreads) +{ +} + +template +ACE_INLINE +DA_Strategy_Base::~DA_Strategy_Base() +{ +} + +template +ACE_INLINE int +DA_Strategy_Base::get_annotation (AnnotationId id) const +{ + int annotation; + if (annotations_repo_.find (id, annotation) == -1) + return -1; + else return annotation; +} + +template +ACE_INLINE int +DA_Strategy_Base::set_annotations_table ( + const HASH_ANNOTATIONS_REVERSE_ITER& table) +{ + HASH_ANNOTATIONS_REVERSE_ITER iter(table); + int rc=0; + + for (;!(iter.done()); iter++) + { + rc = annotations_repo_.bind((*iter).ext_id_, (*iter).int_id_); + if (rc != 0) break; + } + + return rc; +} + +template +ACE_INLINE int +DA_Strategy_Base::add_annotation (AnnotationId id, int annotation) +{ + int rc; + if (annotation > num_avail_threads_.value()) { + rc = -1; + ACE_ERROR ((LM_ERROR, + ACE_TEXT ("%p.\n"), + ACE_TEXT ("DA_Strategy_Base annotation may not exceed number of threads"))); + } else { + rc = annotations_repo_.bind (id, annotation); + } + /* + ACE_DEBUG ((LM_DEBUG, "In add_annotation\n")); + HASH_ANNOTATIONS_CONST_ITER iter(annotations_repo_); + for (;!(iter.done()); iter++) + { + ACE_DEBUG ((LM_DEBUG, "%d-%d\n", (*iter).ext_id_, (*iter).int_id_)); + } + */ + return rc; +} + +template +ACE_INLINE ACE_Hash_Map_Const_Iterator_Ex, + ACE_Equal_To, + ACE_Thread_Mutex> +DA_Strategy_Base::get_annotations_iter() const +{ + + return annotations_repo_.begin(); +} + +template +ACE_INLINE int +DA_Strategy_Base::remove_annotation (AnnotationId id) +{ + return annotations_repo_.unbind (id); +} + diff --git a/ACE/ace/Live_P_Strategy.cpp b/ACE/ace/Live_P_Strategy.cpp new file mode 100644 index 00000000000..9b14b27dbcb --- /dev/null +++ b/ACE/ace/Live_P_Strategy.cpp @@ -0,0 +1,5 @@ +#include "ace/Live_P_Strategy.h" + +#if !defined (__ACE_INLINE__) +#include "ace/Live_P_Strategy.inl" +#endif /* __ACE_INLINE__ */ \ No newline at end of file diff --git a/ACE/ace/Live_P_Strategy.h b/ACE/ace/Live_P_Strategy.h new file mode 100644 index 00000000000..729e3efc69a --- /dev/null +++ b/ACE/ace/Live_P_Strategy.h @@ -0,0 +1,55 @@ +// -*- C++ -*- + +//============================================================================= +/** + * @file Live_P_Strategy.h + * + * + * + * + * + * @author Paul Oberlin + */ +//============================================================================= + +#ifndef ACE_LIVE_P_STRATEGY_H +#define ACE_LIVE_P_STRATEGY_H + +#include /**/ "ace/pre.h" + +#include "ace/DA_Strategy_Base.h" +#include "ace/RB_Tree.h" +#include "ace/Mutex.h" + +#if !defined (ACE_LACKS_PRAGMA_ONCE) +# pragma once +#endif /* ACE_LACKS_PRAGMA_ONCE */ + +//forward decl +class Live_P_Tree; + +template +class Live_P_Strategy : public DA_Strategy_Base { + + //The annotations consist of an identifier and a resource cost value + +public: + Live_P_Strategy(int maxThreads); + virtual ~Live_P_Strategy(); + virtual int is_deadlock_potential(AnnotationId handle); + virtual void grant(AnnotationId handle); + virtual void release(AnnotationId upcall_handle); +private: + Live_P_Tree* tree_pimpl_; + bool min_illegal_is_computed_; + int min_illegal_; + ACE_Mutex computation_mutex_; + +}; +#if defined (__ACE_INLINE__) +#include "ace/Live_P_Strategy.inl" +#endif /* __ACE_INLINE__ */ + +#include /**/ "ace/post.h" + +#endif /* ACE_LIVE_P_STRATEGY_H */ diff --git a/ACE/ace/Live_P_Strategy.inl b/ACE/ace/Live_P_Strategy.inl new file mode 100644 index 00000000000..f1dd3f7936a --- /dev/null +++ b/ACE/ace/Live_P_Strategy.inl @@ -0,0 +1,246 @@ +#include +#include "ace/RB_Tree.h" +/* + Much of this is credited to "Efficient Distrubuted Deadlock + Avoidance with Liveness Guarentees" by Sanchez, Sipma, and Manna, + EMSOFT 2006 +*/ + +struct AnnotationNode { + AnnotationNode() + :count(0), size(0), larger(0), larger_me(0), larger_left(INT_MAX), larger_right(INT_MAX) + { + } + int count; //number of processes with this annotation + int size; //total number of processes in subtree including this node + int larger; //minimum of larger_left, larger_me, and, larger_right + int larger_me; + int larger_left; + int larger_right; +}; + +namespace { + + int min(int a, int b) { + return (a < b)? a : b; + } + + int MIN_THREE(int a, int b, int c) { + return (a < b) ? min(a,c) : min(b,c); + } + +} + +class Live_P_Tree : public ACE_RB_Tree, ACE_Thread_Mutex> { + +public: + Live_P_Tree(int maxThreads); + virtual ~Live_P_Tree(); + int bind(const int& ext_id); + int unbind (const int &ext_id); + int calc_max() const; +protected: + void RB_rotate_right(ACE_RB_Tree_Node *x); + void RB_rotate_left(ACE_RB_Tree_Node *x); +private: + void recalculate_augmentation(ACE_RB_Tree_Node* nodePtr); + void recalculate_augmentation_up(ACE_RB_Tree_Node* x); + int calc_max_i(ACE_RB_Tree_Node* nodePtr, int extra) const; + int T_; +}; + +ACE_INLINE +Live_P_Tree::Live_P_Tree(int maxThreads) +:ACE_RB_Tree, ACE_Thread_Mutex>(), + T_(maxThreads) { + +} + +ACE_INLINE +Live_P_Tree::~Live_P_Tree() { +} + +ACE_INLINE +int +Live_P_Tree::bind(const int& ext_id) +{ + ACE_RB_Tree_Node* entry = 0; + int returnVal = -1; //return error unless we return + //something else from the parent unbind + RB_SearchResult result = LEFT; + entry = find_node (ext_id, result); + // If there is a matching node, don't add a new one, just mod the existing one + if (entry && result == EXACT) { + entry->item().count++; + } else { + returnVal = ACE_RB_Tree, + ACE_Thread_Mutex>::bind(ext_id, + AnnotationNode(), + entry); + } + recalculate_augmentation_up(entry); + return returnVal; +} + +void +Live_P_Tree::RB_rotate_right (ACE_RB_Tree_Node *x) +{ + ACE_RB_Tree, ACE_Thread_Mutex>::RB_rotate_right(x); + recalculate_augmentation_up(x); + +} + +void +Live_P_Tree::RB_rotate_left (ACE_RB_Tree_Node *x) +{ + ACE_RB_Tree, ACE_Thread_Mutex>::RB_rotate_left(x); + recalculate_augmentation_up(x); +} + +ACE_INLINE +int +Live_P_Tree::unbind(const int& ext_id) +{ + ACE_RB_Tree_Node* entry = 0; + RB_SearchResult result = LEFT; + int returnVal = -1; //return error unless we return + //something else from the parent unbind + entry = find_node (ext_id, result); + // If there is a matching node, don't add a new one, just mod the existing one + if (entry && result == EXACT) { + if (--(entry->item().count) == 0) { + entry = entry->parent(); + returnVal = ACE_RB_Tree, ACE_Thread_Mutex>::unbind(ext_id); + } + } else { + //exception? probably bad if we try to unbind something not in the tree + } + if (entry) { + recalculate_augmentation_up(entry); + } + return returnVal; +} + + +ACE_INLINE void +Live_P_Tree::recalculate_augmentation(ACE_RB_Tree_Node* nodePtr) { + + AnnotationNode placeholderNode; + AnnotationNode& node = nodePtr->item(); + AnnotationNode& left = nodePtr->left() ? placeholderNode : nodePtr->left()->item(); + AnnotationNode& right = nodePtr->right() ? placeholderNode : nodePtr->right()->item(); + + // (1) size + node.size = left.size + right.size + node.count; + + // (2) larger_me + node.larger_me = T_ - (node.count + right.size + nodePtr->key()); + + // (3) larger_right + node.larger_right = right.larger; + + // (4) larger_left + node.larger_left = left.larger - (right.size + node.count); + + //(5) larger + node.larger = MIN_THREE(node.larger_me, node.larger_left, node.larger_right); +} + +ACE_INLINE void +Live_P_Tree::recalculate_augmentation_up(ACE_RB_Tree_Node* x) { + while (x) { + recalculate_augmentation(x); + x = x->parent(); + } +} + +ACE_INLINE int +Live_P_Tree::calc_max() const { +// //note: need to add get_root method to RB_Tree + return 0;//calc_max_i(get_root(), 0); +} + +ACE_INLINE int +Live_P_Tree::calc_max_i(ACE_RB_Tree_Node* nodePtr, int extra) const { + AnnotationNode& n = nodePtr->item(); + + if ( n.larger_left - extra==0) { + return calc_max_i(nodePtr->left(), extra + nodePtr->right()->item().size + n.count); } + else if (n.larger_me - extra==0) { return (nodePtr->key()); } + else if (n.larger_right - extra==0) { return calc_max_i(nodePtr->right(), extra); } + else { return T_; } +} + +template +ACE_INLINE +Live_P_Strategy::Live_P_Strategy(int maxThreads) +:DA_Strategy_Base(maxThreads), + min_illegal_is_computed_(false), + min_illegal_(0) +{ +} + +template +ACE_INLINE +Live_P_Strategy::~Live_P_Strategy() +{ +} + + + +template +ACE_INLINE +int +Live_P_Strategy::is_deadlock_potential(AnnotationId handle) +{ + int annotation = get_annotation(handle); + computation_mutex_.acquire(); + if (!min_illegal_is_computed_) + { + if (tree_pimpl_->current_size() > 1) + { + min_illegal_ = tree_pimpl_->calc_max(); + } + min_illegal_is_computed_ = true; + } + computation_mutex_.release(); + + if (annotation >= min_illegal_) + { + return annotation - min_illegal_ + 1; + } + + return 0; +} + +template +ACE_INLINE +void +Live_P_Strategy::grant(AnnotationId handle) +{ + int annotation = get_annotation(handle); + //since the state of the tree is involved in calculation + //of max, we must aquire the lock before changing the + //structure of the tree + computation_mutex_.acquire(); + tree_pimpl_->bind(annotation); + min_illegal_is_computed_ = false; + computation_mutex_.release(); +} + +template +ACE_INLINE +void +Live_P_Strategy::release(AnnotationId handle) +{ + //since the state of the tree is involved in calculation + //of max, we must aquire the lock before changing the + //structure of the tree + computation_mutex_.acquire(); + min_illegal_is_computed_ = false; + int annotation = get_annotation(handle); + tree_pimpl_->unbind(annotation); + computation_mutex_.release(); +} diff --git a/ACE/ace/k_Efficient_P_Strategy.cpp b/ACE/ace/k_Efficient_P_Strategy.cpp new file mode 100644 index 00000000000..f7459611efb --- /dev/null +++ b/ACE/ace/k_Efficient_P_Strategy.cpp @@ -0,0 +1,5 @@ +#include "ace/k_Efficient_P_Strategy.h" + +#if !defined (__ACE_INLINE__) +//#include "ace/k_Efficient_P_Strategy.inl" +#endif /* __ACE_INLINE__ */ \ No newline at end of file diff --git a/ACE/ace/k_Efficient_P_Strategy.h b/ACE/ace/k_Efficient_P_Strategy.h new file mode 100644 index 00000000000..846c234323d --- /dev/null +++ b/ACE/ace/k_Efficient_P_Strategy.h @@ -0,0 +1,188 @@ +// -*- C++ -*- + +//============================================================================= +/** + * @file k_Efficient_P_Strategy.h + * + * + * + * + * + * @author Paul Oberlin + */ +//============================================================================= + +#ifndef ACE_K_EFFICIENT_P_STRATEGY_H +#define ACE_K_EFFICIENT_P_STRATEGY_H + +#include /**/ "ace/pre.h" + +#include "ace/DA_Strategy_Base.h" +#include "ace/Mutex.h" +#include + +#if !defined (ACE_LACKS_PRAGMA_ONCE) +# pragma once +#endif /* ACE_LACKS_PRAGMA_ONCE */ + +template +class k_Efficient_P_Strategy : public DA_Strategy_Base { + + //The annotations consist of an identifier and a resource cost value + +public: + //note: k must be less than maxThreads + k_Efficient_P_Strategy(int maxThreads, int k); + virtual ~k_Efficient_P_Strategy(); + virtual int is_deadlock_potential(AnnotationId handle); + virtual void grant(AnnotationId handle); + virtual void release(AnnotationId upcall_handle); +private: + int compute_min_illegal(); + int get_min_illegal(); + int min_illegal_; + ACE_Mutex computation_mutex_; + int k_; + bool min_illegal_is_computed_ ; + std::vector a; + std::vector A; +}; +//#if defined (__ACE_INLINE__) +//#include "ace/k_Efficient_P_Strategy.inl" +//#endif /* __ACE_INLINE__ */ + +ACE_BEGIN_VERSIONED_NAMESPACE_DECL + +template +ACE_INLINE +k_Efficient_P_Strategy::k_Efficient_P_Strategy(int maxThreads, int k) +:DA_Strategy_Base(maxThreads), + k_(k) + { + a.resize(k_ + 1); + A.resize(k_ + 1); + for (int i=0; i +ACE_INLINE +k_Efficient_P_Strategy::~k_Efficient_P_Strategy() +{ + +} + +template +ACE_INLINE +int k_Efficient_P_Strategy::is_deadlock_potential(AnnotationId handle) +{ + int annotation = DA_Strategy_Base::get_annotation(handle); + + int min_illegal = get_min_illegal(); + if (annotation >= min_illegal) + { + return annotation - min_illegal + 1; + } + + return 0; +} + +template +ACE_INLINE +int +k_Efficient_P_Strategy::compute_min_illegal() +{ + int T = this->get_max_threads(); + for (int i=0; i0) { + return (T - A[k_]); + } + return T; +} + +template +ACE_INLINE +int +k_Efficient_P_Strategy::get_min_illegal() +{ + computation_mutex_.acquire(); + if (!min_illegal_is_computed_) { + min_illegal_ = compute_min_illegal(); + min_illegal_is_computed_ = true; + } + computation_mutex_.release(); + return min_illegal_; +} + +template +ACE_INLINE +void k_Efficient_P_Strategy::grant(AnnotationId handle) +{ + int annotation = get_annotation(handle); + computation_mutex_.acquire(); + if (annotation < k_) + { + a[annotation] ++; + for (int i=0; i<=annotation; ++i) + { + A[i]++; + } + } + else + { + a[k_] ++; + for (int i=0; i<=k_ ; ++i) + { + A[i]++; + } + } + min_illegal_is_computed_ = false; + computation_mutex_.release(); +} + +template +ACE_INLINE +void k_Efficient_P_Strategy::release(AnnotationId handle) +{ + int annotation = get_annotation(handle); + computation_mutex_.acquire(); +/* if (annotation < k ) { + assert(a[annotation]>0); + } else { + assert(a[k] >0); + } +*/ + if (annotation < k_) + { + a[annotation] --; + for (int i=0; i<=annotation; ++i) + { + A[i]--; + } + } + else + { + a[k_] --; + for (int i=0; i<=k_ ; ++i) + { + A[i]--; + } + } + min_illegal_is_computed_ = false; + computation_mutex_.release(); +} + + +ACE_END_VERSIONED_NAMESPACE_DECL + +#include /**/ "ace/post.h" + +#endif /* ACE_BASIC_P_STRATEGY_H */ diff --git a/ACE/ace/k_Efficient_P_Strategy.inl b/ACE/ace/k_Efficient_P_Strategy.inl new file mode 100644 index 00000000000..b1fe2c17a18 --- /dev/null +++ b/ACE/ace/k_Efficient_P_Strategy.inl @@ -0,0 +1,124 @@ +ACE_BEGIN_VERSIONED_NAMESPACE_DECL + +template +ACE_INLINE +k_Efficient_P_Strategy::k_Efficient_P_Strategy(int maxThreads, int k) +:DA_Strategy_Base(maxThreads), + k_(k) + { + a.resize(k_ + 1); + A.resize(k_ + 1); + for (int i=0; i +ACE_INLINE +k_Efficient_P_Strategy::~k_Efficient_P_Strategy() +{ + +} + +template +ACE_INLINE +bool k_Efficient_P_Strategy::is_deadlock_potential(AnnotationId handle) +{ + int annotation = DA_Strategy_Base::get_annotation(handle); + return (annotation >= get_min_illegal()); +} + +template +ACE_INLINE +int +k_Efficient_P_Strategy::compute_min_illegal() +{ + int T = this->get_max_threads(); + for (int i=0; i0) { + return (T - A[k_]); + } + return T; +} + +template +ACE_INLINE +int +k_Efficient_P_Strategy::get_min_illegal() +{ + computation_mutex_.acquire(); + if (!min_illegal_is_computed_) { + min_illegal_ = compute_min_illegal(); + min_illegal_is_computed_ = true; + } + computation_mutex_.release(); + return min_illegal_; +} + +template +ACE_INLINE +void k_Efficient_P_Strategy::grant(AnnotationId handle) +{ + int annotation = get_annotation(handle); + computation_mutex_.acquire(); + if (annotation < k_) + { + a[annotation] ++; + for (int i=0; i<=annotation; ++i) + { + A[i]++; + } + } + else + { + a[k_] ++; + for (int i=0; i<=k_ ; ++i) + { + A[i]++; + } + } + min_illegal_is_computed_ = false; + computation_mutex_.release(); +} + +template +ACE_INLINE +void k_Efficient_P_Strategy::release(AnnotationId handle) +{ + int annotation = get_annotation(handle); + computation_mutex_.acquire(); +/* if (annotation < k ) { + assert(a[annotation]>0); + } else { + assert(a[k] >0); + } +*/ + if (annotation < k_) + { + a[annotation] --; + for (int i=0; i<=annotation; ++i) + { + A[i]--; + } + } + else + { + a[k_] --; + for (int i=0; i<=k_ ; ++i) + { + A[i]--; + } + } + min_illegal_is_computed_ = false; + computation_mutex_.release(); +} + + +ACE_END_VERSIONED_NAMESPACE_DECL \ No newline at end of file -- cgit v1.2.1