Qual é a relevância prática dos algoritmos de exclusão mútua de livros didáticos?

Houve uma boa quantidade de pesquisas sobre algoritmos de exclusão mútua - por exemplo, muitas delas são apresentadas em livros clássicos como The Art of Multiprocessor Programming , onde um capítulo inteiro é dedicado a eles.

Pergunto-me quais são as situações práticas em que alguém pode precisar desses algoritmos durante a engenharia de um sistema simultâneo, em vez de usar as primitivas de sincronização típicas fornecidas por idioma e sistema operacional (por exemplo, fornecidas pela biblioteca pthread)?

Posso pensar em muitos casos especiais em que imagino que as primitivas padrão não sejam especificamente ajustadas para elas, por exemplo, "um leitor frequente e um escritor pouco frequente", ou vice-versa, ou "exatamente uma operação de gravação, muitos leitores", etc. - algum dos algoritmos de exclusão mútua dos livros didáticos é significativamente melhor na prática nessas situações?

Em poucas palavras: quais algoritmos de exclusão mútua são de relevância prática para um engenheiro que já possui uma biblioteca típica de primitivos de simultaneidade fornecidos pela linguagem?

Resposta: nenhuma. Não é disso que trata as seções de The Art of Multiprocessor Program de Herlihy e Shavit. Nos capítulos sobre exclusão mútua, Herlihy e Shavit não oferecem alternativas à pthreadbiblioteca, estão mostrando como ele implementa o equivalente da pthreadbiblioteca.

O capítulo 2 de Herlihy e Shavit é intitulado "Exclusão mútua". Ele fornece uma variedade de algoritmos clássicos para implementar o equivalente pthread_mutex_lock()a apenas com memória compartilhada sequencialmente consistente. Minhas respostas https://cs.stackexchange.com/a/12632/7459 e https://cs.stackexchange.com/a/30249/7459 discutem a importância dessas implementações e apontam para uma que seja prática para use em máquinas que não possuem operações de sincronização de hardware internas. (Artigo de Lamport de 1987 na ACM Trans. On Computer Systems).

O capítulo 7 de Herlihy e Shavit fornece uma variedade de implementações de bloqueio de rotação e fila do equivalente a pthread_mutex_lock(), e o capítulo 8 se expande para discutir pthread_cond_t(variáveis ​​de condição), pthread_rwlock_t(bloqueios de leitor / gravador) e aborda brevementesemaphores . Pode haver situações em que pthread_rwlock_tpossa ser usado como uma alternativa pthread_lock_tpor razões de desempenho (mas geralmente não) e no Posix você precisa usar semaphorespara sincronização entre processos.

Os capítulos 9 a 16 discutem principalmente aplicativos (vários tipos de contêineres simultâneos). O capítulo 17 discute brevemente o equivalente a pthread_barrier_t.

Tudo isso dito, Herlihy e Shavit são dois dos proponentes mais vocais da memória transacional e uma variedade de tipos de sincronização sem bloqueio (e sem espera). Essas técnicas são consideradas alternativas à exclusão mútua em certos casos. Herlihy e Shavit espalham várias implementações sem bloqueio nos capítulos 9 a 16 e, em seguida, entram em detalhes sobre a memória transacional no capítulo 18.

A memória transacional e outras técnicas de sincronização sem bloqueio destinam-se a lidar com o problema de que alguns algoritmos mal projetados exigem que os threads mantenham suas seções críticas por um período muito longo. Atualmente, a memória transacional e a sincronização sem bloqueio não são alternativas práticas em nenhuma situação real, mas as técnicas para transformar estruturas de dados de bloqueio em estruturas de dados sem bloqueio são úteis na prática para minimizar a quantidade de tempo que uma estrutura de dados de bloqueio permanece crítica. seção. (Geralmente, você pode reduzir o tamanho da seção crítica para apenas algumas instruções da máquina.)