Sistemas Operacionais

Aula 6: Primitivas de Sincronização

lock/unlock

sleep/wakeup

Sleep/Wakeup

 
struct bed {
  wait_queue queue;
}

sleep(b, k) {
  currentproc->state = BLOCKED;
  insert_queue(b->queue, currentproc);
  unlock(k);
  schedule();
  lock(k);
}

wakeup(b) {
  p = remove_queue(b->queue);
  if (p != NULL)
    p->state = READY;
}

Exclusão mútua sem busy waiting

 
struct better_mutex {
  mutex k;
  bed b;
  int free;
}

better_lock(k) {
  lock(k->mutex);
  if (!k->free)
    sleep(k->bed, k->mutex);
  k->free = 0;
  unlock(k->mutex);
}

better_unlock(k);
  lock(k->mutex);
  k->free = 1;
  wakeup(k->bed);
  unlock(k->mutex);
}

Semáforos

Monitores

 As primitivas de sincronização vistas até agora são de baixo nível:

Monitores tentam resolver este problema fornecendo primitivas de mais alto nível.

Monitores são módulos de programação:

Variáveis só podem ser acessadas por funções do módulo;

Somente uma função pode ser executada a cada instante (exclusão mútua).

Mensagens

As primitivas estudadas exigem memória compartilhada, que nem sempre está disponível:

Mensagens exigem apenas um canal de comunicação entre processadores: Mais geral.

Não se assume nada:

Mensagens

 Mas o grande problema é o tempo de envio:

Sincronização é complicada porque nunca se tem certeza se a mensagem já chegou ou não.

Primitivas:

Mensagens podem ser ``blocantes'' ou não.

Produtor/Consumidor e Mensagens

void producer() {
  message m, ack;
  while(TRUE) {
    receive(consumer, &ack);
    produce_item(&m);
    send(consumer, &m);
  }
}

void consumer() {
  message m, ack;
  send(producer, &ack);
  while(TRUE) {
    receive(producer, &m);
    consume_item(m);
    send(producer, &m); 
  }
}

Exclusão Mútua e Mensagens

 Produtor/consumidor ficou bem mais simples com mensagens.

Mas e exclusão mútua ???

Mensagens

Porque utilizar mensagens?

Mensagens

 Mensagens podem variar nas seguintes dimensões:

Relação entre mailboxes e processos:

Quantidade de "buffering":

Mensagens

 Operações blocantes versus não-blocantes:

Formas adicionais de espera:

Mensagens X Memória Compartilhada

 As abordagens utilizando mensagens e dados compartilhados têm o mesmo poder de expressão.

Remote Procedure Call

 Chamada de procedimento não local:

P0: chama f(a, b, c) durante sua execução

P1: servidor: loop infinito esperando pedidos de execução de f.

P0			P1
...
f(a, b, c);
send(p1, a, b, c);	receive(p, a, b, c);
			r = f(a, b, c);
receive(r);		send(p, r);
...

Sincronização no Linux

 
struct wait_queue {
  struct task_struct *task;
  struct wait_queue *next;
};

void add_wait_queue(queue, entry);
void remove_wait_queue(queue, entry);
Wait queues são modificadas por rotinas de interrupção. Por causa disto elas só podem ser acessadas através das rotinas acima.

Um processo esperando por um evento é colocado na wait_queue correspondente:

sleep/wakeup no Linux

 
void sleep_on(struct wait_queue **queue)
{
  struct wait_queue entry={current,NULL}
  current->state = TASK_UNINTERRUPTABLE;
  add_wait_queue(queue, &entry);
  schedule();
  remove_wait_queue(queue, &entry);
}

void wake_up(struct wait_queue **queue)
{
  struct wait_queue *p = *queue;
  do {
    p->task->state = TASK_RUNNING;
    p = p->next;
  } while (p != *queue);
}

Semáforos no Linux

 
struct semaphore {
  int count;
  struct wait_queue *wait;
};

void wait(struct semaphore *sem)
{
  while (sem->count <= 0)
    sleep_on(sem->wait);
  sem->count--;
}

void signal(struct semaphore *sem)
{
  sem->count++;
  wake_up(&sem->wait);
}