Je dois concevoir une structure de données à utiliser dans un environnement multi-threadé. L'API de base est simple: élément d'insertion, éliminez l'élément, récupérez l'élément, vérifiez que cet élément existe. La mise en œuvre de la structure utilise un verrouillage implicite pour garantir l'atomicité d'un seul appel d'une API. Après avoir mis en œuvre cela, il est devenu évident que ce dont j'ai vraiment besoin, c'est d'atomicité dans plusieurs appels d'API. Par exemple, si un appelant doit vérifier l'existence d'un élément avant d'essayer de l'insérer, il ne peut pas le faire atomique même si chaque appel d'API est em> atomique: if(!data_structure.exists(element)) {
data_structure.insert(element);
}
5 Réponses :
Vous créez un mécanisme de verrouillage externe (mauvais) ou de redéfinir l'API, comme et, lorsqu'il s'agit de tels types de collecte de base, vous devez vérifier si votre langue de choix leur offre déjà dans sa bibliothèque standard.
[EDIT] Pour clarifier: le verrouillage externe est mauvais pour l'utilisateur de la classe, car elle introduit une autre source de bugs potentiels. Oui, lorsque les considérations de performance font en effet des choses pire pour les structures de données simultanées qu'elles sont synchronisées de l'extérieur, mais ces cas sont rares, puis ils ne peuvent généralement être résolus / optimisés que par des personnes de beaucoup plus de connaissances / d'expérience que moi.
putifabsent . Cette dernière approche est par exemple utilisée pour Java's Structures de données simultanées.
Pourquoi le verrouillage extérieur est-il mauvais? Il se peut que l'utilisateur de l'API connaisse davantage lorsque les choses doivent être verrouillées (par exemple, vous pourriez avoir une instance de la collection qui n'est même pas partagée entre les threads). Pour des raisons de performance, il peut être parfaitement raisonnable d'utiliser un verrouillage extérieur.
@Michaeal: oui, vrai. Mais le verrouillage externe déplace le fardeau de l'utilisateur d'une structure de données. Tout dépend de l'utilisateur. Mais, vous avez raison, un verrouillage externe est requis dans certains cas, mais j'utiliserais même une structure de données unis non simultanée et tout verrouille à l'extérieur.
@frunsi, c'est un bon point ... un objet devrait soit être un threadsafe entièrement ou pas-à-tout. Lorsque je pensais à un verrouillage extérieur, j'ai supposé que la base de données serait faite non simultanée, mais maintenant que je relisons le poste, je vois que l'auteur proposait une sorte d'hybride, ce qui serait très méchant.
Désolé pour le bowvote. Je voudrais le remettre, mais je ne me laisserai donc pas le faire, maintenant.
Oui, cela m'est arrivé trop une fois; Donc, vous ne vous permettez que de refaire votre vote dans un délai imparti ou après une modification substantielle (ou tout autre édition, ne savez pas). J'espère avoir eu le problème de performance un peu mieux maintenant avec le texte ajouté.
Qu'en est-il de déplacer l'existence de vérifier dans la méthode Évidemment, vous pouvez également retourner une exception, ou une instance d'un objet et compliquer votre vie à partir de là ..
Mais s'il vous plaît, ne comptez pas sur l'utilisateur définissant leurs propres serrures. . k / code>? Un client l'appelle et s'il renvoie faux vous savez que quelque chose s'est mal passé. Tout comme ce que MALLOC () est en plain vieux C - retour null si échoué, définissez errno .
Parfois, c'est cher pour créer un élément à insérer. Dans ces scénarios, vous ne pouvez pas vraiment vous permettre de créer régulièrement des objets qui pourraient déjà exister au cas où ils le feraient.
Une approche est pour la méthode Dans une langue Raii, comme C ++, vous pouvez utiliser une classe Smart Stack pour encapsuler le curseur renvoyé afin qu'il retire automatiquement si le code d'appel ne s'engage pas. En Java, c'est un peu plus différé avec la méthode Une autre approche est que l'appelant crée l'objet qui n'est pas présent, mais que pour échouer occasionnellement dans l'insertion réelle si un autre thread a "remporté la course". Voici comment, par exemple, les mises à jour MEMCACHE sont effectuées. Cela peut très bien fonctionner. insertifabsent () pour renvoyer un "curseur" verrouillé - il insère un porte-endroit dans la structure interne de sorte qu'aucun autre fil ne puisse croire qu'il est absent, mais n'insère pas le nouvel objet. L'espace réservé peut contenir une serrure de sorte que d'autres threads qui souhaitent accéder à cet élément particulier doivent attendre qu'il soit inséré.
finaliser () , mais peut toujours fonctionner.
Tout d'abord, vous devriez vraiment séparer vos préoccupations. Vous avez deux choses à craindre:
Je suggère fortement que vous utilisiez une interface ou une classe de base virtuelle qui représente le type de datructtructure que vous implémentez. Créez une implémentation simple qui ne fait aucun verrouillage, du tout. Ensuite, créez une deuxième implémentation qui enveloppe la première implémentation et ajoute le verrouillage sur dessus. Cela permettra une implémentation plus performante où le verrouillage n'est pas nécessaire et simplifiera grandement votre code.
On dirait que vous mettez en œuvre une sorte de dictionnaire. Une chose que vous pouvez faire est de fournir des méthodes qui ont une sémantique équivalente à la déclaration combinée. Par exemple, En d'autres termes, ma recommandation serait de déterminer quelles combinaisons de méthodes sont fréquemment utilisées et créent simplement des méthodes d'API qui effectuent cette combinaison d'opérations atomiquement. setingdefault est une fonction raisonnable à fournir qui définira une valeur uniquement si la clé correspondante n'existe pas déjà dans le dictionnaire.
dans une mode de style Raii, vous pouvez créer des objets accessor / poignée (ne sait pas comment son appelé, existe probablement un modèle de ceci), par ex. Une liste:
template <typename T>
class List {
friend class ListHandle<T>;
// private methods use NO locking
bool _exists( const T& e ) { ... }
void _insert( const T& e ) { ... }
void _lock();
void _unlock();
public:
// public methods use internal locking and just wrap the private methods
bool exists( const T& e ) {
raii_lock l;
return _exists( e );
}
void insert( const T& e ) {
raii_lock l;
_insert( e );
}
...
};
template <typename T>
class ListHandle {
List<T>& list;
public:
ListHandle( List<T>& l ) : list(l) {
list._lock();
}
~ListHandle() {
list._unlock();
}
bool exists( const T& e ) { return list._exists(e); }
void insert( const T& e ) { list._insert(e); }
};
List<int> list;
void foo() {
ListHandle<int> hndl( list ); // locks the list as long as it exists
if( hndl.exists(element) ) {
hndl.insert(element);
}
// list is unlocked here (ListHandle destructor)
}
C'est une overkill ... S'il veut utiliser des serrures du tout, il pourrait simplement écrire un insertif> méthode: BOOL insertifnotfound (Element T) {verrouillage (); essayez {if (! data_tructure.exists (élément)) {data_structure.insert (élément); retourne vrai; } retourner false} enfin {verrouillage.unlock (); }}
@Lirik: Que ce soit surkill ou ne dépend pas beaucoup d'utilisation. Dans la pratique, je n'utilise pas du tout des structures de données "simultanentes", mais travaillez avec un verrouillage externe plus ou moins. Mais cette chose est logique, si vous avez des exigences plus complexes que insertif [non] trouvé (ces cas d'utilisation existent), alors de cette façon va bien. De plus, la surkilleuse sera optimisée, de sorte que c'est juste beaucoup de dactylographie.
@frunsi insertifnotfound est principalement connu sous le nom de Putifabsent qui est une méthode courante dans des structures de données simultanentes (clarifiant-moi là-bas, je suis sûr que vous avez vu). Donc, votre alternative à une structure de données simultanée est un verrouillage externe?
@Lirik: Mon alternative est fournie dans ma réponse, dans les détails! Lisez-le ... La réponse est contenue. putifabsent et / ou tout autre doifblabla Les méthodes sont correctes pour les cas habituels et vous aident à résoudre la plupart des problèmes, mais ma méthode (encore une fois, lisez ma réponse) est un général Solution.
À propos de vous Modifier: Pensez à la situation, où le pointeur à l'élément stocké est retourné et que d'autres threads essaient de supprimer cet élément de Data_Structure. Vous avez au moins besoin de choisir quel comportement doit être mis en œuvre du modèle de verrouillage OOF. Erreur de retour pour filtrer en essayant de supprimer l'objet? Attendez que l'objet devienne non référencé, etc.