Instituto de Computação - UNICAMP

MC504 - Sistemas Operacionais

Segundo Semestre de 2014

Islene Calciolari Garcia

Projeto 1: Animação do Modus Hall Problem

O livro The Little Book on Semaphores, de Allen B. Downey, tem uma excelente lista de problemas multithread. Em semestres anteriores de MC504/MC514 foram escritas animações para vários destes problemas. Neste semestre, iremos estudar e animar pela primeira vez o Modus Hall Problem.

Neste problema, grupos rivais devem atravessar um caminho estreito. Poderá passar o grupo que tiver maior número de pessoas. No texto do livro (páginas 178 a 182), os grupos são denominados heathen e prude e se referem a grupos de estudantes da universidade de Olin. Na sua animação, você pode escolher ilustrar os grupos de maneira diferente.

Você deve implementar uma animação de um destes problemas que permita:

Boa visão do estado global da aplicação
Boa visão das mudanças de estado
Alteração de parâmetros (permita variar, por exemplo, a razão entre o número de elementos dos dois grupos)

Não é necessário utilizar recursos gráficos. Sua animação pode ser uma sequência de saídas com caracteres ASC. Sua implementação deve ser em C e utilizar pthreads.

Para se acostumar com o estilo do livro, veja um vídeo interessante com a explicação do problema do Papai Noel.

Sugestão de algoritmo

Este código foi retirado do livro The Little Book on Semaphores:

Variáveis

1  heathens = 0
2  prudes = 0
3  status = 'neutral'
4  mutex = Semaphore(1)
5  heathenTurn = Semaphore(1)
6  prudeTurn = Semaphore(1)
7  heathenQueue = Semaphore(0)
8  prudeQueue = Semaphore(0)

Pseudo-código para os heathens

 1  heathenTurn.wait()
 2  heathenTurn.signal()
 3 
 4  mutex.wait()
 5  heathens++
 6
 7  if status == 'neutral':
 8      status = 'heathens rule'
 9      mutex.signal()
10  elif status == 'prudes rule':
11      if heathens > prudes:
12         status = 'transition to heathens'
13         prudeTurn.wait()
14      mutex.signal()
15      heathenQueue.wait()
16  elif status == 'transition to heathens':
17     mutex.signal()
18     heathenQueue.wait()
19  else
20     mutex.signal()
21
22  # cross the field
23 
24  mutex.wait()
25  heathens--
26
27  if heathens == 0:
28     if status == 'transition to prudes':
29        prudeTurn.signal()
30     if prudes:
31        prudeQueue.signal(prudes)
32        status = 'prudes rule'
33     else:
34        status = 'neutral'
35
36  if status == 'heathens rule':
37      if prudes > heathens:
38          status = 'transition to prudes'
39          heathenTurn.wait()
40
41  mutex.signal()

Você acha que este código está correto? O que acontece quando várias threads são interrompidas na linha 3? Você proporia algum outro algoritmo?

Data de entrega

O projeto deverá ser entregue até o dia 27 de outubro via Moodle (ainda não configurado). Apenas um membro de cada grupo deverá fazer a entrega.

Dicas

Compile seu programa com:

gcc -g -pthread

E utilize o gdb para depurar.

Caso seu código contenha vários arquivos, inclua um Makefile.