Comment une opération de déverrouillage/verrouillage sur un mutex peut-elle être plus rapide qu'une extraction de mémoire?

Question

Norvig affirme qu'une opération de verrouillage ou de déverrouillage de mutex ne prend qu'un quart du temps nécessaire pour effectuer un chargement à partir de la mémoire.

Cette answer explique qu'un mutex est essentiellement un drapeau et une file d'attente et qu'il suffirait de quelques instructions pour retourner le drapeau sur un mutex non contesté.

1. Je suppose que, si une autre CPU ou noyau essaie de verrouiller ce mutex, il faut attendre la ligne de cache à écrire de nouveau dans la mémoire (si cela n'a pas déjà le cas) et de sa propre lecture de la mémoire pour obtenir l'état du drapeau. Est-ce exact? Quelle est la différence, si c'est un noyau différent par rapport à un processeur différent? Donc les états Norvig ne sont que pour un mutex non contesté où le CPU ou le noyau essayant l'opération a déjà ce drapeau dans son cache et la ligne de cache n'est pas sale?

Answer 1

Un PC typique gère un CPU x86, les processeurs d'Intel peuvent effectuer le verrouillage entièrement sur les caches:

si la zone de mémoire étant bloquée lors d'une opération de verrouillage est mis en cache dans le processeur effectue l'opération LOCK comme mémoire de réécriture et est complètement contenue dans une ligne de cache, le processeur ne peut pas affirmer le signal LOCK # sur le bus. Au lieu de cela, il modifiera l'emplacement de mémoire en interne et permettra à son mécanisme de cohérence de mémoire cache de s'assurer que l'opération est effectuée de manière atomique. Cette opération est appelée «verrouillage de la mémoire cache».
Le mécanisme de cohérence de la mémoire cache empêche automatiquement deux ou plusieurs processeurs qui ont mis en cache la même zone de mémoire de modifier simultanément les données dans cette zone.

^{De Intel Software Developer Manual 3, Section 8.1.4}

Le mécanisme de cohérence de mémoire cache est une variante du protocole MESI.
Dans un tel protocole, avant qu'une unité centrale puisse écrire dans un emplacement mis en cache, elle doit avoir la ligne correspondante dans l'état exclusif (E).
Cela signifie qu'une seule unité centrale à la fois a un emplacement mémoire donné dans un état sale.
Lorsque d'autres processeurs souhaitent lire le même emplacement, l'UC propriétaire retarde ces lectures jusqu'à ce que l'opération atomique soit terminée.
Il suit ensuite le protocole de cohérence pour transmettre, invalider ou réécrire la ligne.

Dans le scénario ci-dessus, un verrou peut être effectué plus rapidement qu'une charge non mise en cache.

Ces périodes sont cependant un peu hors tension et sûrement obsolètes.
Ils sont destinés à donner ordre, avec un ordre de grandeur, parmi les opérations typiques.
Le timing d'un hit L1 est un peu étrange, il n'est pas plus rapide que l'exécution typique d'une instruction (qui ne peut être décrite en elle-même avec un seul nombre).
Le manuel d'optimisation Intel rapporte, pour un ancien CPU comme Sandy Bridge, un temps d'accès L1 de 4 cycles alors qu'il y a beaucoup d'instructions avec une latence de 4 cycles de moins.

Je prendrais ces chiffres avec un grain de sel, en évitant de trop raisonner dessus.
La leçon Norvig a essayé de nous apprendre est: le matériel est en couches, le plus proche (d'un point de vue topologique) à la CPU, le plus rapide.
Ainsi, lors de l'analyse d'un fichier, un programmeur doit éviter de déplacer les données vers un fichier, mais plutôt de réduire la pression d'E/S.
Les uns s'appliquent lors du traitement d'un tableau, la localité améliorera les performances. Notez cependant que ceux-ci sont techniquement, micro-optimisations and the topic is not as simple as it appears.

---

Divide général, le matériel dans ce qui est: l'intérieur du noyau (registres), à l'intérieur du CPU (caches, peut-être pas la LLC), dans la prise (GPU, LLC), derrière le bus dédié périphériques (mémoire, autres processeurs), derrière un bus générique (PCIe - périphériques internes comme les cartes réseau), derrière deux bus ou plus (périphériques USB, disques) et dans un autre ordinateur entièrement (serveurs).