Serrure (informatique) - Lock (computer science)

En informatique , un verrou ou mutex ( par exclusion mutuelle ) est une primitive de synchronisation : un mécanisme qui impose des limites d' accès à une ressource lorsqu'il existe de nombreux threads d' exécution . Un verrou est conçu pour appliquer une stratégie de contrôle de concurrence d' exclusion mutuelle , et avec une variété de méthodes possibles, il existe plusieurs implémentations uniques pour différentes applications.

Les types

Généralement, les verrous sont des verrous consultatifs , où chaque thread coopère en acquérant le verrou avant d'accéder aux données correspondantes. Certains systèmes implémentent également des verrous obligatoires , où une tentative d'accès non autorisé à une ressource verrouillée forcera une exception dans l'entité tentant d'effectuer l'accès.

Le type de verrou le plus simple est un sémaphore binaire . Il fournit un accès exclusif aux données verrouillées. D'autres schémas fournissent également un accès partagé pour la lecture des données. D'autres modes d'accès largement mis en œuvre sont l'exclusivité, l'intention d'exclure et l'intention de mettre à niveau.

Une autre façon de classer les verrous est ce qui se passe lorsque la stratégie de verrouillage empêche la progression d'un thread. La plupart des conceptions de verrouillage bloquent l' exécution du thread demandant le verrou jusqu'à ce qu'il soit autorisé à accéder à la ressource verrouillée. Avec un verrou tournant , le thread attend simplement ("tourne") jusqu'à ce que le verrou soit disponible. Ceci est efficace si les threads sont bloqués pendant une courte période, car cela évite la surcharge de la replanification des processus du système d'exploitation. Elle est inefficace si le verrou est maintenu pendant une longue période ou si la progression du thread qui détient le verrou dépend de la préemption du thread verrouillé.

Les verrous nécessitent généralement une prise en charge matérielle pour une mise en œuvre efficace. Ce support prend généralement la forme d'une ou plusieurs instructions atomiques telles que « test-and-set », « fetch-and-add » ou « compare-and-swap ». Ces instructions permettent à un seul processus de tester si le verrou est libre et, s'il est libre, d'acquérir le verrou en une seule opération atomique.

Les architectures monoprocesseur ont la possibilité d'utiliser des séquences d'instructions ininterrompues - en utilisant des instructions spéciales ou des préfixes d'instructions pour désactiver temporairement les interruptions - mais cette technique ne fonctionne pas pour les machines à mémoire partagée multiprocesseurs . Une prise en charge appropriée des verrous dans un environnement multiprocesseur peut nécessiter une prise en charge matérielle ou logicielle assez complexe, avec des problèmes de synchronisation importants.

La raison pour laquelle une opération atomique est requise est la simultanéité, où plus d'une tâche exécute la même logique. Par exemple, considérons le code C suivant :

if (lock == 0) {
    // lock free, set it
    lock = myPID;
}

L'exemple ci-dessus ne garantit pas que la tâche possède le verrou, car plusieurs tâches peuvent tester le verrou en même temps. Étant donné que les deux tâches détecteront que le verrou est libre, les deux tâches tenteront de définir le verrou, sans savoir que l'autre tâche définit également le verrou. Les algorithmes de Dekker ou de Peterson sont des substituts possibles si les opérations de verrouillage atomique ne sont pas disponibles.

L'utilisation imprudente des verrous peut entraîner un blocage ou un blocage . Un certain nombre de stratégies peuvent être utilisées pour éviter ou récupérer des interblocages ou des livelocks, à la fois au moment de la conception et au moment de l' exécution . (La stratégie la plus courante consiste à standardiser les séquences d'acquisition de verrous afin que les combinaisons de verrous interdépendants soient toujours acquises dans un ordre "en cascade" spécifiquement défini.)

Certaines langues prennent en charge les verrous syntaxiquement. Voici un exemple en C# :

public class Account // This is a monitor of an account
{
    private decimal _balance = 0;
    private object _balanceLock = new object();

    public void Deposit(decimal amount)
    {
        // Only one thread at a time may execute this statement.
        lock (_balanceLock)
        {
            _balance += amount;
        }
    }

    public void Withdraw(decimal amount)
    {
        // Only one thread at a time may execute this statement.
        lock (_balanceLock)
        {
            _balance -= amount;
        }
    }
}

Le code lock(this)peut entraîner des problèmes si l'instance est accessible publiquement.

Semblable à Java , C# peut également synchroniser des méthodes entières, en utilisant l'attribut MethodImplOptions.Synchronized.

[MethodImpl(MethodImplOptions.Synchronized)]
public void SomeMethod()
{
    // do stuff
}

Granularité

Avant d'être initié à la granularité des verrous, il faut comprendre trois concepts sur les verrous :

• surcharge de verrouillage : les ressources supplémentaires pour l'utilisation des verrous, comme l'espace mémoire alloué aux verrous, le temps CPU pour initialiser et détruire les verrous, et le temps pour acquérir ou libérer les verrous. Plus un programme utilise de verrous, plus la surcharge associée à l'utilisation est importante ;
• conflit de verrouillage : cela se produit chaque fois qu'un processus ou un thread tente d'acquérir un verrou détenu par un autre processus ou thread. Plus les verrous disponibles sont précis, moins il est probable qu'un processus/un thread demande un verrou détenu par l'autre. (Par exemple, verrouiller une ligne plutôt que la table entière, ou verrouiller une cellule plutôt que la ligne entière.) ;
• deadlock : situation dans laquelle chacune d'au moins deux tâches attend un verrou que l'autre tâche détient. À moins que quelque chose ne soit fait, les deux tâches attendront éternellement.

Il existe un compromis entre la diminution de la surcharge de verrouillage et la diminution des conflits de verrouillage lors du choix du nombre de verrous en synchronisation.

Une propriété importante d'un verrou est sa granularité . La granularité est une mesure de la quantité de données que le verrou protège. En général, le choix d'une granularité grossière (un petit nombre de verrous, chacun protégeant un grand segment de données) entraîne moins de surcharge de verrouillage lorsqu'un seul processus accède aux données protégées, mais de moins bonnes performances lorsque plusieurs processus s'exécutent simultanément. C'est à cause de l'augmentation des conflits de verrouillage . Plus le verrou est grossier, plus la probabilité qu'il arrête un processus non lié est élevée. Inversement, l'utilisation d'une granularité fine (un plus grand nombre de verrous, chacun protégeant une assez petite quantité de données) augmente la surcharge des verrous eux-mêmes mais réduit les conflits de verrous. Le verrouillage granulaire où chaque processus doit détenir plusieurs verrous à partir d'un ensemble commun de verrous peut créer des dépendances de verrou subtiles. Cette subtilité peut augmenter le risque qu'un programmeur introduise sans le savoir un blocage .

Dans un système de gestion de base de données , par exemple, un verrou pourrait protéger, par ordre de granularité décroissante, une partie d'un champ, un champ, un enregistrement, une page de données ou une table entière. Une granularité grossière, telle que l'utilisation de verrous de table, a tendance à donner les meilleures performances pour un seul utilisateur, tandis qu'une granularité fine, telle que les verrous d'enregistrement, a tendance à donner les meilleures performances pour plusieurs utilisateurs.

Verrous de base de données

Les verrous de base de données peuvent être utilisés pour garantir la synchronisation des transactions. c'est-à-dire que lors du traitement simultané des transactions (transactions entrelacées), l'utilisation de verrous à 2 phases garantit que l'exécution simultanée de la transaction s'avère équivalente à un certain ordre en série de la transaction. Cependant, les blocages deviennent un effet secondaire malheureux du verrouillage des bases de données. Les interblocages sont soit évités en prédéterminant l'ordre de verrouillage entre les transactions, soit détectés à l'aide de graphiques d'attente . Une alternative au verrouillage pour la synchronisation de la base de données tout en évitant les blocages implique l'utilisation d'horodatages globaux totalement ordonnés.

Il existe des mécanismes utilisés pour gérer les actions de plusieurs utilisateurs simultanés sur une base de données, le but est d'éviter les mises à jour perdues et les lectures modifiées. Les deux types de verrouillage sont le verrouillage pessimiste et le verrouillage optimiste :

• Verrouillage pessimiste : un utilisateur qui lit un enregistrement avec l'intention de le mettre à jour place un verrou exclusif sur l'enregistrement pour empêcher d'autres utilisateurs de le manipuler. Cela signifie que personne d'autre ne peut manipuler cet enregistrement jusqu'à ce que l'utilisateur libère le verrou. L'inconvénient est que les utilisateurs peuvent être verrouillés pendant très longtemps, ralentissant ainsi la réponse globale du système et provoquant de la frustration.

Où utiliser le verrouillage pessimiste : il est principalement utilisé dans les environnements où les conflits de données (le degré de requête des utilisateurs au système de base de données à un moment donné) sont importants ; où le coût de la protection des données via les verrous est inférieur au coût de l'annulation des transactions, en cas de conflits de simultanéité. La concurrence pessimiste est mieux mise en œuvre lorsque les temps de verrouillage seront courts, comme dans le traitement programmatique des enregistrements. La simultanéité pessimiste nécessite une connexion permanente à la base de données et n'est pas une option évolutive lorsque les utilisateurs interagissent avec des données, car les enregistrements peuvent être verrouillés pendant des périodes relativement longues. Il n'est pas approprié pour une utilisation dans le développement d'applications Web.

• Verrouillage optimiste : cela permet à plusieurs utilisateurs simultanés d'accéder à la base de données tandis que le système conserve une copie de la lecture initiale effectuée par chaque utilisateur. Lorsqu'un utilisateur souhaite mettre à jour un enregistrement, l'application détermine si un autre utilisateur a modifié l'enregistrement depuis sa dernière lecture. Pour ce faire, l'application compare la lecture initiale conservée en mémoire à l'enregistrement de la base de données pour vérifier les modifications apportées à l'enregistrement. Toute divergence entre la lecture initiale et l'enregistrement de la base de données enfreint les règles de concurrence et amène donc le système à ignorer toute demande de mise à jour. Un message d'erreur est généré et l'utilisateur est invité à recommencer le processus de mise à jour. Il améliore les performances de la base de données en réduisant le nombre de verrouillages requis, réduisant ainsi la charge sur le serveur de base de données. Il fonctionne efficacement avec les tables qui nécessitent des mises à jour limitées car aucun utilisateur n'est verrouillé. Cependant, certaines mises à jour peuvent échouer. L'inconvénient est les échecs de mise à jour constants dus aux volumes élevés de demandes de mise à jour de plusieurs utilisateurs simultanés - cela peut être frustrant pour les utilisateurs.

Où utiliser le verrouillage optimiste : cela est approprié dans les environnements où il y a peu de conflits pour les données, ou où un accès en lecture seule aux données est requis. La concurrence optimiste est largement utilisée dans .NET pour répondre aux besoins des applications mobiles et déconnectées, où le verrouillage des lignes de données pendant des périodes prolongées serait infaisable. De plus, le maintien des verrous d'enregistrement nécessite une connexion permanente au serveur de base de données, ce qui n'est pas possible dans les applications déconnectées.

Désavantages

La protection des ressources basée sur les verrous et la synchronisation thread/processus présentent de nombreux inconvénients :

• Conflit : certains threads/processus doivent attendre qu'un verrou (ou tout un ensemble de verrous) soit libéré. Si l'un des threads détenant un verrou meurt, se bloque, se bloque ou entre dans une boucle infinie, les autres threads attendant le verrou peuvent attendre indéfiniment.
• Surcoût : l'utilisation de verrous ajoute un surcoût pour chaque accès à une ressource, même lorsque les chances de collision sont très rares. (Cependant, toute chance pour de telles collisions est une condition de course .)
• Débogage : les bogues associés aux verrous dépendent du temps et peuvent être très subtils et extrêmement difficiles à reproduire, tels que les interblocages .
• Instabilité : l'équilibre optimal entre la surcharge de verrouillage et la contention de verrouillage peut être unique au domaine du problème (application) et sensible à la conception, à la mise en œuvre et même aux modifications architecturales du système de bas niveau. Ces soldes peuvent changer au cours du cycle de vie d'une application et peuvent entraîner des changements considérables à mettre à jour (rééquilibrer).
• Composabilité : les verrous sont uniquement composables (par exemple, gérer plusieurs verrous simultanés afin de supprimer atomiquement l'élément X de la table A et d'insérer X dans la table B) avec un support logiciel (overhead) relativement élaboré et une parfaite adhérence par la programmation d'applications à des conventions rigoureuses.
• Inversion de priorité : un thread/processus de faible priorité détenant un verrou commun peut empêcher les threads/processus de haute priorité de continuer. L'héritage de priorité peut être utilisé pour réduire la durée d'inversion de priorité. Le protocole de plafond de priorité peut être utilisé sur des systèmes monoprocesseurs pour minimiser la durée d'inversion de priorité dans le pire des cas, ainsi que pour éviter les blocages .
• Convoyage : tous les autres threads doivent attendre si un thread détenant un verrou est déprogrammé en raison d'une interruption de tranche de temps ou d'un défaut de page.

Certaines stratégies de contrôle de la concurrence évitent tout ou partie de ces problèmes. Par exemple, un entonnoir ou des jetons de sérialisation peuvent éviter le plus gros problème : les blocages. Les alternatives au verrouillage incluent des méthodes de synchronisation non bloquantes , comme les techniques de programmation sans verrouillage et la mémoire transactionnelle . Cependant, de telles méthodes alternatives nécessitent souvent que les mécanismes de verrouillage réels soient mis en œuvre à un niveau plus fondamental du logiciel d'exploitation. Par conséquent, ils peuvent uniquement soulager le niveau de l' application des détails de la mise en œuvre des verrous, les problèmes énumérés ci-dessus devant toujours être traités sous l'application.

Dans la plupart des cas, un verrouillage approprié dépend de la fourniture par le CPU d'une méthode de synchronisation de flux d'instructions atomiques (par exemple, l'ajout ou la suppression d'un élément dans un pipeline nécessite que toutes les opérations simultanées nécessitant d'ajouter ou de supprimer d'autres éléments dans le canal soient suspendues pendant la manipulation du contenu de la mémoire nécessaire pour ajouter ou supprimer l'élément spécifique). Par conséquent, une application peut souvent être plus robuste lorsqu'elle reconnaît les charges qu'elle impose à un système d'exploitation et est capable de reconnaître gracieusement le signalement de demandes impossibles.

Manque de composabilité

L'un des plus gros problèmes de la programmation basée sur les verrous est que "les verrous ne composent pas ": il est difficile de combiner de petits modules corrects basés sur des verrous dans des programmes plus grands tout aussi corrects sans modifier les modules ou au moins connaître leurs composants internes. Simon Peyton Jones (un défenseur de la mémoire transactionnelle logicielle ) donne l'exemple suivant d'application bancaire : concevoir une classe Account qui permet à plusieurs clients simultanés de déposer ou de retirer de l'argent sur un compte ; et donner un algorithme pour transférer de l'argent d'un compte à un autre. La solution basée sur les verrous à la première partie du problème est :

class Account:
    member balance: Integer
    member mutex: Lock

    method deposit(n: Integer)
           mutex.lock()
           balance ← balance + n
           mutex.unlock()

    method withdraw(n: Integer)
           deposit(−n)

La deuxième partie du problème est beaucoup plus compliquée. Une routine de transfert correcte pour les programmes séquentiels serait

function transfer(from: Account, to: Account, amount: integer)
    from.withdraw(amount)
    to.deposit(amount)

Dans un programme concurrent, cet algorithme est incorrect car lorsqu'un thread est à mi-chemin du transfert , un autre peut observer un état dans lequel le montant a été retiré du premier compte, mais pas encore déposé sur l'autre compte : de l'argent a disparu du système. Ce problème ne peut être complètement résolu qu'en prenant des verrous sur les deux comptes avant de modifier l'un des deux comptes, mais les verrous doivent ensuite être pris selon un ordre global arbitraire pour éviter les blocages :

function transfer(from: Account, to: Account, amount: integer)
    if from < to    // arbitrary ordering on the locks
        from.lock()
        to.lock()
    else
        to.lock()
        from.lock()
    from.withdraw(amount)
    to.deposit(amount)
    from.unlock()
    to.unlock()

Cette solution se complique lorsque davantage de verrous sont impliqués et que la fonction de transfert doit connaître tous les verrous, afin qu'ils ne puissent pas être masqués .

Support linguistique

Les langages de programmation varient dans leur prise en charge de la synchronisation :

• Ada fournit des objets protégés qui ont des sous-programmes ou des entrées protégés visibles ainsi que des rendez-vous.
• La norme ISO/IEC C fournit une API standard d'exclusion mutuelle (verrouillages) depuis C11 . La norme ISO/IEC C++ actuelle prend en charge les fonctionnalités de threading depuis C++11 . Le standard OpenMP est pris en charge par certains compilateurs et permet de spécifier des sections critiques à l'aide de pragmas. L' API pthread POSIX prend en charge le verrouillage. Visual C++ fournit l' attribut des méthodes à synchroniser, mais cela est spécifique aux objets COM dans l' architecture Windows et le compilateur Visual C++ . C et C++ peuvent facilement accéder à toutes les fonctionnalités de verrouillage du système d'exploitation natif.synchronize
• C# fournit le lockmot - clé sur un thread pour garantir son accès exclusif à une ressource.
• VB.NET fournit un SyncLockmot - clé comme le mot - clé de C# lock.
• Java fournit le mot-clé synchronizedpour verrouiller des blocs de code, des méthodes ou des objets et des bibliothèques comportant des structures de données sécurisées pour la concurrence.
• Objective-C fournit le mot-clé @synchronizedpour mettre des verrous sur des blocs de code et fournit également les classes NSLock, NSRecursiveLock et NSConditionLock ainsi que le protocole NSLocking pour le verrouillage.
• PHP fournit un verrouillage basé sur les fichiers ainsi qu'une Mutexclasse dans l' pthreadsextension.
• Python fournit un mécanisme mutex de bas niveau avec une Lockclasse du threadingmodule.
• La norme ISO/IEC Fortran (ISO/IEC 1539-1:2010) fournit le lock_typetype dérivé dans le module intrinsèque iso_fortran_envet les instructions lock/ unlockdepuis Fortran 2008 .
• Ruby fournit un objet mutex de bas niveau et aucun mot-clé.
• Rust fournit la Mutex<T>structure.
• L'assembly x86 fournit le LOCKpréfixe sur certaines opérations pour garantir leur atomicité.
• Haskell implémente le verrouillage via une structure de données modifiable appelée MVar, qui peut être vide ou contenir une valeur, généralement une référence à une ressource. Un thread qui veut utiliser la ressource « prend » la valeur du MVar, le laissant vide, et le remet lorsqu'il a terminé. Tenter de prendre une ressource à partir d'un vide MVarentraîne le blocage du thread jusqu'à ce que la ressource soit disponible. Comme alternative au verrouillage, une implémentation de mémoire transactionnelle logicielle existe également.

Voir également

• Section critique
• Verrouillage vérifié
• Verrouillage de fichiers
• Algorithmes sans verrouillage et sans attente
• Moniteur (synchronisation)
• Exclusion mutuelle
• Motif de verrouillage en lecture/écriture
• Sémaphore (programmation)

Les références

Liens externes

• Tutoriel sur les serrures et les sections critiques