 |
01/03: |
Informações gerais, bibliografia, critério de aprovação, etc.
O que é programação concorrente. Motivação para o estudo de
programação concorrente.
|
|
05/03: |
Conceitos básicos: thread e
ação atômica. Hipóteses de
trabalho. A necessidade de sincronização. Exclusão mútua: o
problema da região crítica (PRC). O recurso de desabilitar
interrupções de hardware para "resolver" o PRC em sistemas com
uma só CPU. [Notas de aula: ps, pdf.]
|
|
08/03: |
Soluções do PRC com espera ocupada (busy waiting) e sem "ajuda
especial" do hardware. Primeira tentativa: alternância
estrita. Algoritmo de Dekker para 2 threads. Algoritmo de
Peterson (tie breaker) para 2 threads. [Notas de aula: ps, pdf.]
|
|
12/03: |
Tie breaker para n threads. Ações atômicas elementares
(fine-grained) e instruções de máquina. Exemplos de instruções
do x86 que não são atômicas. Ações atômicas em linguagens de alto
nível: a propriedade at-most-once. Notação para ações atômicas
"compostas" ou de granularidade grossa (coarse-grained). [Notas
de aula: ps, pdf.]
|
|
15/03: |
Exemplos de uso de ações atômicas de granularidade grossa para
fazer exclusão mútua e para sincronização condicional. Políticas
de escalonamento e justiça: políticas incondicionalmente justas,
fracamente justas e fortemente justas. [Notas de aula: ps, pdf.]
|
|
19/03: |
Instruções atômicas que fazem mais de um acesso a memória:
test-and-set, swap, incr, etc. Solução do PRC usando
test-and-set. Implementação de comandos await. A instrução
fetch-and-add e o algoritmo do ticket. [Notas de aula: ps, pdf.]
|
|
22/03: |
O bakery algorithm. [Notas de aula: ps, pdf.]
|
|
26/03: |
Semáforos. Implementação das primitivas P e V. Solução do
problema da região crítica usando semáforos. Solução do problema
dos produtores/consumidores (bounded buffer) usando
semáforos. [Notas de aula: ps,
pdf.]
|
|
29/03: |
Sinais (a maior parte da aula) e memória compartilhada no
Unix. [Notas de aula: ps, pdf.]
|
|
02/04: |
O problema dos leitores e escritores: solução que usa semáforos
e dá prioridade aos leitores. O problema dos filósofos: solução
com semáforos. [Notas de aula: ps, pdf.]
|
|
05/04: |
A técnica da "passagem de bastão" (secção 4.4 do livro do
Andrews). Solução do problema dos leitores e escritores usando
passagem de bastão. (Esta solução também dá prioridade aos
leitores, mas pode ser facilmente alterada para dar prioridade
aos escritores. Exercício: faça isso!) [Notas de aula: ps, pdf.]
|
|
16/04: |
Primeira prova.
|
|
19/04: |
Monitores. Solução do problema dos produtores/consumidores
(bounded buffer) usando um monitor. Implementação de um semáforo
com um monitor. Solução do problema dos leitores e escritores
usando um monitor.
|
|
23/04: |
Monitores: toda chamada a wait deve estar dentro
de um while. O problema do barbeiro (sleeping
barber). Conversa informal sobre o segundo exercício-programa e
sobre pthreads. [Notas de aula: ps, pdf.]
|
|
26/04: |
Continuação de pthreads. [Notas de aula: ps, pdf.] |
|
30/04: |
Disciplinas de sinalização em monitores: signal and
continue (esta é disciplina mais comum, usada por pthreads
e por Java threads), signal and wait, signal and
exit (também conhecida como signal and
return). Threads
em Java. |
|
03/05: |
Sincronização
em Java: locks de objetos, métodos e blocos
synchronized. Monitores
em Java: wait, notify e
notifyAll. |
|
07/05: |
Bounded buffer em Java. (Tradução da versão para monitores, sem
lidar direito com o fato de cada monitor Java tem só uma
"variável de condição". Tinha um bug que foi corrigido na
aula de 21/05). Semáforos em Java. |
|
10/05: |
Java: O pacote util.concurrent. As implementações
de algumas classes desse pacote: Mutex,
ReentrantLock, Semaphore e
WaiterPreferenceSemaphore. Comentários sobre as
implementações de FIFOSemaphore e
PrioritySemaphore (os detalhes ficaram para casa).
|
|
21/05: |
Conversa sobre o EP3. Discussão sobre um bug na versão Java do
bounded buffer. Correção: usar notifyAll em vez de
notify. |
|
24/05: |
O uso de synchronized em Java: recomendações do Doug
Lea. Before/after patterns: layering, adapters, subclassing.
Splitting synchronization: splitting classes, splitting locks.
Aninhamento de monitores e o nested monitor lockout.
|
|
31/05: |
Como evitar o nested monitor lockout. Revendo o bounded buffer
em Java; versões sem notifyAll: versão com semáforos (não vimos
o código desta versão) e versão com sincronização dividida entre
dois monitores.
|
|
04/06: |
Propriedades de safety e liveness. Desempenho e reusabilidade.
Exemplo: controle de concorrência no acesso a uma tablela de
hash. Três alternativas de granularidade: tabela toda, hash
bucket (uma lista ligada), ítem de hash bucket
ligada. Aplicação: gerenciador de locks de um SGBD.
|
Last modified: Fri Jun 15 18:26:23 BRST 2001