Spinlocks e semáforos

Este projeto faz parte do PPOS v2.

O objetivo deste projeto é implementar spinlocks e semáforos clássicos em nosso sistema:

• Spinlock: controle de exclusão mútua baseado em espera ocupada e instruções atômicas do processador;
• Semáforo clássico: controle de exclusão mútua eficiente e justo, conforme a definição de Dijkstra.

O spinlock é um controle de exclusão mútua baseado em espera ocupada. Para implementá-lo, sugere-se usar operações atômicas sobre números inteiros. As operações de travar e destravar devem ser implementadas:

void spin_lock (int *lock);
 
void spin_unlock (int *lock);

O spinlock é representado por um inteiro lock, cujo valor inicial em 0 (zero) indica que a trava está livre.

Cada semáforo é representado por uma estrutura semaphore_t que deve ser definida no arquivo kernel/semaphore.c. Essa estrutura contém um contador, uma fila e um inteiro para o controle de concorrência no acesso ao semáforo (spinlock).

As funções a seguir estão declaradas em semaphore.h e devem ser implementadas em semaphore.c:

struct semaphore_t *sem_create(int value);

Cria um semáforo com o valor inicial value e uma fila vazia. A chamada retorna um ponteiro para o semáforo ou NULL em caso de erro.

int sem_down (struct semaphore_t *s)

Realiza a operação Down no semáforo apontado por s. Esta chamada pode ser bloqueante: caso o contador do semáforo seja negativo, a tarefa corrente é suspensa, inserida no final da fila do semáforo e a execução volta ao dispatcher; caso contrário, a tarefa continua a executar sem ser suspensa.

Se a tarefa for suspensa, ela será acordada mais tarde, quando uma outra tarefa liberar o semáforo (através da operação sem_up) ou caso o semáforo seja destruído (operação sem_destroy).

A chamada retorna 0 em caso de sucesso ou -1 em caso de erro (semáforo não existe ou foi destruído).

int sem_up (struct semaphore_t *s)

Realiza a operação Up no semáforo apontado por s. Esta chamada não é bloqueante (a tarefa que a executa não perde o processador). Se houverem tarefas aguardando na fila do semáforo, a primeira da fila deve ser acordada e retornar à fila de tarefas prontas.

A chamada retorna 0 em caso de sucesso ou -1 em caso de erro (semáforo não existe ou foi destruído).

int sem_destroy (struct semaphore_t *s)

Destrói o semáforo apontado por s, acordando todas as tarefas que aguardavam por ele.

A chamada retorna 0 em caso de sucesso ou -1 em caso de erro.

Caso duas tarefas tentem acessar o mesmo semáforo simultaneamente, podem ocorrer condições de disputa nas variáveis internas dos semáforos. Por isso, as funções que implementam os semáforos devem ser protegidas usando um mecanismo de exclusão mútua.

Obviamente não podemos usar semáforos para resolver esse problema … Por isso, deve ser usado um mecanismo mais primitivo, como o spinlock.

Os seguintes arquivos são relevantes para este projeto:

• kernel/semaphore.c: implementação de spinlocks e semáforos
• test/pingpong-semaphore.c: programa de teste simples
• test/pingpong-semaphore-stress.c: programa de teste exaustivo
• test/pingpong-semaphore*.txt: saídas esperadas dos testes

• Duração estimada: 4 horas.
• Dependências:
  • Tarefas cooperativas
  • Despachante de tarefas
  • Preempção por Tempo
  • Tarefas que esperam
  • Tarefas que dormem