Séance de cours

Registres et linéarisabilité

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Description

Cette séance de cours couvre la puissance des registres dans le contexte de la linéarisation, en discutant des opérations de mise à jour et de numérisation, ainsi que des concepts d'algorithmes sans verrou et sans attente. Il se penche également sur l'algorithme SCAN, en explorant sa mise en œuvre et ses applications pratiques.

Source officielle

Concepts associés (11)

Non-blocking algorithm

In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking implementations. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress. "Non-blocking" was used as a synonym for "lock-free" in the literature until the introduction of obstruction-freedom in 2003.

Linearizability

In concurrent programming, an operation (or set of operations) is linearizable if it consists of an ordered list of invocation and response events, that may be extended by adding response events such that: The extended list can be re-expressed as a sequential history (is serializable). That sequential history is a subset of the original unextended list. Informally, this means that the unmodified list of events is linearizable if and only if its invocations were serializable, but some of the responses of the serial schedule have yet to return.

Verrou (informatique)

Un verrou informatique permet de s'assurer qu'une seule personne, ou un seul processus accède à une ressource à un instant donné. Ceci est souvent utilisé dans le domaine des accès à des fichiers sur des systèmes d'exploitation multi-utilisateur, car si deux programmes modifient un même fichier au même moment, le risque est de : provoquer des erreurs dans un des deux programmes, voire dans les deux ; laisser le fichier en fin de traitement dans une complète incohérence ; endommager le fichier manipulé.

Attente active

L’attente active, en génie logiciel, ou polling (parfois appelée aussi « scrutation ») est une technique de programmation que les processus utilisent lorsqu'ils vérifient de façon répétée si une condition est vraie, comme l'attente d'une entrée (clavier ou autre) ou encore la libération d'un verrou. Cette technique peut également être utilisée pour mettre en attente un programme pour une durée déterminée. Cela était nécessaire sur d'anciens systèmes d'exploitation dont le matériel sous-jacent ne proposait pas de méthode spécifique pour suspendre l'exécution du flot d'instruction pendant une période déterminée.

Read-copy-update

In computer science, read-copy-update (RCU) is a synchronization mechanism that avoids the use of lock primitives while multiple threads concurrently read and update elements that are linked through pointers and that belong to shared data structures (e.g., linked lists, trees, hash tables). Whenever a thread is inserting or deleting elements of data structures in shared memory, all readers are guaranteed to see and traverse either the older or the new structure, therefore avoiding inconsistencies (e.g.

Afficher plus

Séances de cours associées (9)

Anonymous Concurrent Computing

Explore l'informatique concurrente anonyme, couvrant les compteurs, les instantanés et les algorithmes de consensus.

Synchronisation sans verrouillage : perspectives pratiques

Explore l'importance de la synchronisation sans verrouillage pour obtenir une faible latence dans les systèmes distribués et discute des solutions pratiques pour la génération d'identificateurs uniques et les files d'attente de messagerie.

Synchronisation : Serrures et barrières

Explore les principes de synchronisation à l'aide de verrous et de barrières, en mettant l'accent sur des implémentations matérielles efficaces et des mécanismes de coordination tels qu'OpenMP.

Le pouvoir des registres

Couvre les implémentations sans attente d'objets atomiques, en se concentrant sur les compteurs et les instantanés, en discutant des idées clés pour renforcer l'atomicité et la liberté d'attente.

Synchronisation sans verrouillage : performances et évolutivité

Explore la synchronisation sans verrouillage pour des performances et une évolutivité dans les systèmes distribués, couvrant la génération d'identifiants uniques, les files d'attente de messagerie et les lectures RDMA atomiques.

Afficher plus

Concepts associés (11)

Non-blocking algorithm

Linearizability

Verrou (informatique)

Attente active

Read-copy-update

Afficher plus