Sistemas Operacionais

Aula 5: Implementando Exclusão Mútua

Exclusão Mútua

 
while (!fim) {
  seção_não_crítica;
  lock();
  seção_crítica;
  unlock();
}
Uma solução para o problema tem que satisfazer:

Mas não se sabe nada sobre a velocidade de execução de cada processo.

Dois Processos

Exclusão mútua via software

Algoritmo 1: Software

lock()
{
  while (vez != i);
};

unlock()
{
  vez = j;
};

Dois Processos

Algoritmo 1:

 Propriedades:

Problema:

Dois Processos

Algoritmo 2:

 
lock()
{
  quer_entrar[i] = 1;
  while (quer_entrar[j]);
};

unlock()
{
  quer_entrar[i] = 0;
};

Dois Processos

Algoritmo 2:

 Propriedades:

Dois Processos

Algoritmo 3:

 
lock()
{
  quer_entrar[i] = 1;
  vez = j;
  while
    (quer_entrar[j] && turn == j);
};

unlock()
{
  quer_entrar[i] = 0;
};

Dois Processos

Algoritmo 3:

 Propriedades:

Múltiplos Processos

Algoritmo do padeiro:

Múltiplos Processos

 
lock()
{
  escolhendo[i] = 1;
  numero[i] = max(numero[0..n-1]) + 1;
  escolhendo[i] = 0;
  for (j = 0; j < n; j++) {
    while (escolhendo[j]);
    while ((numero[j] != 0) &&
           (numero[j],j)<(numero[i],i));
  };
}

unlock()
{
  numero[i] = 0;
};

aonde (a,b) < (c,d) se (a < c) ou (a = c e b < d)

Múltiplos Processos

Correto porque:

Exclusão Mútua via Hardware

Desabilitando Interrupções

 Em um uniprocessador operações serão atômicas se não houver troca de contexto.

Trocas de contexto acontecem quando o escalonador é chamado: por eventos internos ou eventos externos:

Vantagem: simples e eficiente.

Desvantagens:

Desabilitando Interrupções

 Mas que fica fácil fica:

lock()
{
  disable_interrupts();
};

unlock()
{
  enable_interrupts();
};

Desabilitando Interrupções

 Uma maneira mais eficiente de se implementar exclusão mútua desabilitando interrupções é:

int M = 0;
lock(M)
{
  disable_interrupts();
  while (M) {
    enable_interrupts();
    disable_interrupts();
  };
  M = 1;
  enable_interrupts();
};

unlock(M)
{
  disable_interrupts();
  M = 0;
  enable_interrupts();
};

Read-Modify-Write

 Em multiprocessadores desabilitar interrupções não funciona.

A maioria dos processadores modernos implementa alguma forma de read-modify-write:

Exemplos:

Test & Set

 Implementando exclusão mútua:

int M = 0;
lock(M)
{
  while (test&set(M) == 1);
};

unlock(M)
{
  M = 0;
};

Hardware X Software

 Se é tão mais simples acessar exclusão mútua via hardware, porque estudar via software ?

Camas e Chaves

 Vários outros tipos de primitiva para sincronização existem:

Camas e Chaves

 Com estas primitivas pode-se implementar outras mais complexas. Por exemplo, exclusão mútua com mínimo de busy waiting:

better_lock(M)
{
  lock(M.guard);
  if (!M.free) {
    sleep(M.bed, M.guard);
    M.free = 0;
  } else {
    unlock(M.guard);
  };
}

better_unlock(M)
{
  lock(M.guard);
  M.free = 1;
  wakeup(M.bed);
  unlock(M.guard);
}

Semáforos

 Semáforos são variáveis inteiras que são acessadas somente através de duas operações atômicas wait (P) e signal (V):

wait(S)
{
  while (S <= 0);
  S--;
};

signal(S)
{
  S++;
};

Exclusão Mútua usando Semáforos

 
int S = 1;
lock(S)
{
  wait(S);
};

unlock(S)
{
  signal(S);
};

Exclusão Mútua: Resumo