Notas de Aula - MAC 5755 - Sistemas Operacionais Distribuídos

Aula 10 - 14/9/2001

Controle de Concorrência

• Um dos objetivos do SO é multiplexar os recursos da máquina
• Mas acesso simultâneo ou concorrente a recursos pode gerar inconsistências
• São necessários mecanismos para garantir acesso exclusivo a recursos compartilhados
• regiões críticas / exclusão mútua
• Por outro lado, temos que minimizar as regiões críticas pois elas eliminam possibilidades de execução concorrente e degradam desempenho.
• mecanismos: semáforos, monitores. variáveis condicionais, locks.

Semáforos

• Dijkstra (1965)
• operação P: indica entrada em região crítica
• operação V: indica saída de região crítica
• pode ser binário (se há um só recurso) ou não (se há mais recursos)
• No UNIX:
• #include <sys/sem.h>
• semget () - cria novo semáforo
• semop ()  - operações em semáforo
• possível desvantagem: dificuldade de programação, facilidade em criar erros de programação

Locks

• tradução: bloqueio
• operações: lock e unlock
• duas semânticas:
• busy wait (espera ocupada) - spinlock, spinning
• É mais rápido mas desperdiça recursos
• blocking lock (que bloqueia)
• Mais demorado para perceber que lock foi liberado mas mais eficiente em termos de aproveitamento do processador
• para implementar, hardware precisa fornecer operação test-and-set

Monitores

• Hoare (1974)
• agrupa procedimentos (funções, métodos) dentro de um módulo
• o monitor garante que só um procedimento dentro de cada módulo é executado em um determinado instante
• Em geral, é implementado pelo compilador usando um semáforo binário
• vantagem: facilita a vida do programador, mais difícil de levar a erros
• É a abordagem usada por Java:
• Classes e métodos podem receber o atributo synchronized e passar a se comportar como um monitor.
• A implementação é feita através de um lock por objeto.

Variáveis Condicionais

• Similares a semáforos mas um pouco diferentes.
• Em geral, são usadas por threads que colaboram entre si.
• Em java:
• uma variável condicional (implícita) por objeto
• wait - faz com que o thread seja bloqueado a espera de que algo aconteça
• notify - notifica ao primeiro thread bloqueado naquele objeto que algo aconteceu
• notifyall - notifica todos threads bloqueados naquele objeto que algo aconteceu
• Exemplo:

 class Fila {
         [...]
         public synchronized void Adiciona (int val)
         {
             while (proximo(ultimo) == primeiro) {
                 try { wait(); } // fila lotada
                 catch (InterruptedException e) {}
             }
             buff[ultimo] = val;
             ultimo = proximo(ultimo);
            notify();
         }

         public synchronized int Remove ()
         {
             while (primeiro == ultimo) {
                 try { wait(); } // fila vazia
                 catch (InterruptedException e) {}
             }
             int ret = buff[primeiro];
             primeiro = proximo(primeiro);
            notify();
             return ret;
         }
}

ACE

• biblioteca para C++ implementando semáforos, variáveis condicionais e locks
• independente de sistema operacional (casca em cima do SO)

Controle de Concorrência em Sistemas Distribuídos

1. Gerenciamento Centralizado de Locks

• Mensagens enviadas:
1. Criação de novo lock (p/ 1 região crítica) C -> S
2. Solicitação de acesso a uma determinada região crítica C -> S
3. Colocado na fila (é opcional mas ajuda a detectar se servidor está respondendo ou não) S -> C
4. Permissão de acesso concedida S -> C
5. Lock liberado C -> S
• Desvantagens
• não escalável (congetionamento em torno do servidor de locks)
• ponto único de falha
• Exemplo: Solaris (Sun NFS Lock Manager)

2. Gerenciamento Distribuído de Locks

• Mensagens enviadas:
1. Solicitação de entrada em região crítica; enviada para todos os participantes
• usando comunicação de grupo
• mensagem da forma request(id do processo, nome da região crítica, timestamp);
2. Concedida; enviado por recebedores da mensagem de solicitação
• Colocado na fila; enviado por quem está dentro da região crítica (usando o lock)
• quando sai da região, envia um Concedida para o primeiro da fila
• Políticas para entrada na região crítica:
1. unanimidade
2. maioria
• Para maiores detalhes, ver Tanenbaum DOS.

3. Passagem de Bastão

• Forma-se um anel lógico e um bastão (token) é passado de nó em nó.
• Só quem tem o bastão pode entrar na região crítica.
• vantagem: + simples de implementar, +simples para o programador
• problemas:
1. Como descobrir se o bastão foi perdido ou se simplesmente está sendo usado em outros nós?
2. E se o nó com o bastão cai?
3. Como manter um anel lógico mesmo com nós falhando?
4. Como identificar e acrescentar novos nós ao anel?
• possíveis soluções:
• um ou mais nós fazem um monitoramento do anel para saber quais nós estão ativos e quais não estão
• quando um nó cai, isso pode ser detectado facilmente por um vizinho quando este tenta passar o bastão
• pode-se usar algoritmos de eleição para escolher um nó para ser o coordenador
• se o coordenador falha, escolhe-se um novo coordenador dinamicamente

Referências

Capítulo 5 do Galli, seção 3.2 do Tanenbaum, e capítulo 6 do Sinha