Estou lendo a programação The Art of Multiprocessor e tentando entender seu conceito de bloqueios inconsistentes. Especificamente, na página 37 , a definição 2.8.1 de um bloqueio inconsistente não está clara para mim, assim como o Lema 2.8.1.
Definição 2.8.1. Um estado de objeto de bloqueio s é inconsistente em qualquer estado global em que algum encadeamento esteja na seção crítica, mas o estado de bloqueio é compatível com um estado global no qual nenhum encadeamento está na seção crítica ou está tentando entrar.
Lema 2.8.1 Nenhuma implementação de bloqueio sem conflito pode entrar em um estado inconsistente.
Prova:
Suponha que o objeto Bloquear esteja em um estado inconsistente s, em que nenhum encadeamento esteja na seção crítica ou tentando entrar. Se o encadeamento B tentar entrar na seção crítica, ele deverá ter êxito, pois a implementação é livre de impasse.
Suponha que o objeto Lock esteja em um estado inconsistente s, em que A esteja na seção crítica. Se o encadeamento B tentar entrar na seção crítica, ele deverá bloquear até que A saia. Temos uma contradição, porque B não pode determinar se A está na seção crítica.
O que eu não entendo:
- Ser inconsistente significa apenas que, se um thread estiver em uma seção crítica, não há como outros tópicos saberem sobre ele?
- Qual é a contradição em uma prova de lema? Digamos que o encadeamento A esteja em uma seção crítica e o bloqueio esteja em um estado inconsistente. O que impede que outro thread substitua e adquira o estado do bloqueio?
fonte
Respostas:
"inconsistente" aqui significa basicamente que a implementação interna não está refletindo a realidade da ativação do encadeamento e da disponibilidade do bloqueio. também conhecido como "defeituoso". ou seja, não está funcionando corretamente como uma trava de linha. por exemplo, a trava pode indicar "ativo", mas nenhuma linha adquiriu a trava ou a trava indica "inativo", mas algumas linhas adquiriram uma trava.
a contradição é que, de acordo com o "impasse", um bloqueio será adquirido por pelo menos algum segmento que o solicite. mas se estiver em um estado inconsistente, algum encadeamento estará em execução, mas o bloqueio indicará que nada está bloqueado. mas qualquer novo encadeamento não poderá obter o bloqueio (sem executar ao mesmo tempo que A).
observe uma ruga / sutileza de uma referência on-line [1] que coincide com a exposição do livro (mesmos autores):
[1] Sincronização multiprocessador e estruturas de dados concorrentes Maurice Herlihy / Nir Shavit
fonte