Please enable JavaScript.
Coggle requires JavaScript to display documents.
Capítulo 11, Mecanismos de Coordenação: Este capítulo apresenta…
Capítulo 11
Gabriel Bérti - 2127938
Luis Felipe Moro Coelho - 2128020
Mecanismos de Coordenação:
Este capítulo apresenta mecanismos de sincronização mais sofisticados, como os semáforos e
mutexes
, que atendem os requisitos de eficiência e justiça.
Semáforos:
Dijkstra propôs o semáforo, um mecanismo de coordenação eficiente e flexível para o controle da exclusão mútua entre
n
tarefas, entre outros usos.
Apesar de antigo, o semáforo continua sendo o mecanismo de sincronização
mais utilizado na construção de aplicações concorrentes
, sendo
usado de forma explícita ou como base
na construção de mecanismos de coordenação mais abstratos, como os monitores.
Um semáforo pode ser visto como uma variável composta
s
que contém uma fila de tarefas
s.queue
, inicialmente vazia, e um contador inteiro
s.counter
, cujo valor inicial depende de como o semáforo será usado. O conteúdo interno do semáforo não é diretamente acessível ao programador; para manipulá-lo devem ser usadas as seguintes
operações atômicas:
down(s)
: Decrementa o contador interno
s.counter
e o testa: se ele for negativo, a tarefa solicitante é adicionada à fila do semáforo (
s.queue
) e suspensa.
Caso contrário, a chamada
down(s)
retorna e a tarefa pode continuar sua execução.
up(s)
: Incrementa o contador interno
s.counter
e o testa: um contador negativo ou nulo indica que há tarefa(s) suspensa(s) naquele semáforo. A primeira tarefa da fila
s.queue
é então devolvida à fila de tarefas prontas, para retomar sua execução
assim que possível.
Esta chamada não é bloqueante
Semáforos podem ser usados para o controle da exclusão mútua em seções críticas. Para tal, basta usar
down(s)
para solicitar acesso a uma seção crítica e
up(s)
para liberá-la. O semáforo
s
deve ser inicializado em 1, para que somente uma tarefa consiga entrar na seção crítica de cada vez.
Além das operações
down
e
up
, deve existir uma operação
init
para inicializar o semáforo, que defina o valor inicial do contador (a fila inicia vazia).
As operações de acesso aos semáforos são geralmente implementadas pelo núcleo do sistema operacional e oferecidas como chamadas de sistema. É importante observar que observar que elas
devem ser atômicas
, para evitar condições de disputa sobre as variáveis internas do semáforo e proteger sua integridade.
Eficiência:
As tarefas que aguardam o semáforos são suspensas e não consomem processador; quando o semáforo é liberado, somente a primeira tarefa da fila de semáforos é acordada.
Justiça:
A fila de tarefas do semáforo obedece uma política FIFO, garantindo que as tarefas receberão o semáforo na ordem das solicitações.
Independência:
somente as tarefas que solicitaram o semáforo através da operação
down(s)
são consideradas na decisão de quem irá obtê-lo.
Semáforos estão disponíveis na maioria dos sistemas operacionais e linguagens de programação. O padrão POSIX define várias funções em C para a criação e manipulação de semáforos.
Mutexes:
Muitos ambientes de programação, bibliotecas de threads e até mesmo núcleos de sistema proveem uma
versão simplificada de semáforos
, na qual o contador só assume dois valores possíveis:
livre (1)
ou
ocupado (0)
. Esses semáforos simplificados são chamados de
mutexes
(uma abreviação de
mutual exclusion
), semáforos binários ou simplesmente
locks
(travas).
Os sistemas Windows oferecem chamadas em C/C++ para gerenciar
mutexes
, como
CreateMutex, WaitForSingleObject e ReleaseMutex
.
Mutexes
estão disponíveis na maior parte das linguagens de programação de uso geral, como C, C++, Python, Java, C#, etc.
Variáveis de Condição:
Quando uma tarefa aguarda uma condição, ela é colocada para dormir até que outra tarefa a avise de que aquela condição se tornou verdadeira. Assim, a tarefa não precisa testar continuamente uma condição, evitando esperas ocupadas.
Uma variável de condição está associada a uma condição lógica que pode ser aguardada por uma tarefa, como a conclusão de uma operação, a chegada de um pacote de rede ou o preenchimento de um
buffer
.
O uso de variáveis de condição é simples: a condição desejada é associada a uma variável de condição
c
. Uma tarefa aguarda essa condição através do operador
wait(c)
, ficando suspensa enquanto espera. A tarefa em espera será acordada quando outra tarefa perceber que a condição se tornou verdadeira e informar isso através do operador
signal(c)
(ou notify(c))
.
Internamente, uma variável de condição possui uma fila de tarefas
c.queue
que aguardam a condição
c
. Além disso, a variável de condição deve ser usada em conjunto com um
mutex
, para garantir a exclusão mútua sobre o estado da condição representada por
c.
wait, signal e broadcast
(que sinaliza todas as tarefas que estão aguardando a condição
c
).
Os operadores sobre variáveis de condição também
devem ser executados de forma atômica.
Deve-se ter em mente que a variável de condição
não contém
a condição propriamente dita, apenas permite efetuar a sincronização sobre uma condição.
Semântica de Hoare
:
A operação
signal(c)
fazia com que a tarefa sinalizadora perdesse imediatamente o mutex e o processador, que eram entregues à primeira tarefa da fila de
c.
Esse comportamento interfere diretamente no escalonador de processos, sendo
indesejável em sistemas operacionais de uso geral.
As
implementações modernas
de variáveis de condição adotam outro comportamento, denominado
semântica Mesa
, que foi inicialmente proposto na linguagem de programação concorrente
Mesa
.
Nessa semântica, a operação
signal(c)
apenas “acorda” uma tarefa que espera pela condição, sem suspender a execução da tarefa corrente.
As variáveis de condição estão presentes no padrão POSIX, através de operadores como
pthread_cond_wait (cond, mutex), pthread_cond_signal (cond)
e
pthread_cond_broadcast (cond)
.
O padrão POSIX adota a semântica
Mesa
Monitores:
Um monitor é uma estrutura de sincronização que requisita e libera a seção crítica associada a um recurso de forma transparente, sem que o programador tenha de se preocupar com isso. Um monitor consiste dos
seguintes elementos:
Ao usar semáforos ou
mutexes
, um programador precisa identificar explicitamente os pontos de sincronização necessários em seu programa, ela se torna inviável e suscetível a erros em sistemas mais complexos.
Um recurso compartilhado, visto como um conjunto de variáveis internas ao monitor.
Um conjunto de procedimentos e funções que permitem o acesso a essas variáveis;
Um
mutex
ou semáforo para controle de exclusão mútua; cada procedimento de
acesso ao recurso deve obter o
mutex
antes de iniciar e liberá-lo ao concluir;
Um invariante sobre o estado interno do recurso.
A definição formal de monitor prevê e existência de um
invariante
, ou seja, uma condição sobre as variáveis internas do monitor que deve ser sempre verdadeira. Entretanto, a maioria das implementações de monitor não suporta a definição de invariantes.
De certa forma, um monitor pode ser visto como um objeto que encapsula o recurso compartilhado, com procedimentos (métodos) para acessá-lo.
No monitor execução dos procedimentos é feita com exclusão mútua entre eles. As operações de obtenção e liberação do
mutex
são inseridas automaticamente pelo compilador do programa
em todos os pontos de entrada e saída do monitor (no início e final de cada procedimento), liberando o programador dessa tarefa e assim evitando erros.
Variáveis de condição podem ser usadas no interior de monitores (na verdade,
os dois conceitos nasceram juntos).
Todavia, devido às restrições da
semântica Mesa
, um procedimento que executa a operação
signal
em uma variável de condição deve concluir e sair imediatamente do monitor, para garantir que o invariante associado ao
estado interno do monitor seja respeitado.
Monitores estão presentes em várias linguagens de programação, como Ada, C#, Eiffel, Java e Modula-3.