Concorrência e Paralelismo
Objetivos
No final desta UC o estudante terá adquirido conhecimentos, aptidões e competências que lhe permitam:
Saber:
— Compreender os conceitos de concorrência e paralelismo, e como estes são úteis no processo de desenvolvimento de software;
— Identificar os modelos utilizados para resolver problemas recorrendo a sistemas multiprocessador;
— Conhecer os paradigmas utilizados no desenvolvimento de algoritmos em sistemas multiprocessador;
— Conhecer as linguagens, bibliotecas e ferramentas utilizadas no desenvolvimento de programas concorrentes;
- Compreender as propriedades de correção de sistemas concorrentes, e.g., linearização, progresso, justiça e deadlock-freedom.
- Compreender as propriedades da memória partilhada, e.g., construções de registos e snapshots atómicos.
- Ser capaz de avaliar a utilização de primitivas de sincronização usadas em estruturas de dados concorrentes, desde registos atómicos, protocolos de consenso e filas FIFO, até construções universais, como universalidade de consenso.
— Estar familiarizado com problemas de concorrência comuns e como os mitigar e evitar.
Saber Fazer:
— Identificar e explorar oportunidades para concorrência e paralelização num sistema de software;
— Particionar um problema em múltiplas tarefas para serem executadas num sistema concorrente.
— Raciocinar sobre o comportamento de sistemas concorrentes;
— Construir sistemas concorrentes corretos e eficientes;
- Aplicar padrões de programação, incluindo spin-locks, monitores, barreiras e work-stealing.
— Utilizar linguagens de programação como a Java e C e bibliotecas para desenvolver sistemas de software concorrentes;
- Desenvolver estruturas de dados concorrentes, e.g., listas ligadas, filas, pilhas, tabelas de dispersão e skiplists.
— Utilizar ferramentas de programação no desenvolvimento de aplicações concorrentes, incluindo as fases de desenho, implementação, depuração e instalação.
- Analisar padrões de sincronização, e.g., locks de grão grosso e fino, locks otimistas e lazy, sincronização não bloqueante e primitivas atómicas de sincronização.
— Prever e medir as características do desempenho de sistemas concorrentes.
Caracterização geral
Código
11158
Créditos
6.0
Professor responsável
João Manuel dos Santos Lourenço
Horas
Semanais - 4
Totais - 52
Idioma de ensino
Inglês
Pré-requisitos
A disponibilizar brevemente
Bibliografia
Bibliografia base:
• Herlihy, M., Shavit, N., Luchangco, V., & Spear, M. (2020).
The art of multiprocessor programming (2nd ed.).
Morgan Kaufmann. ISBN 978-0-12-415950-1.
Bibliografia complementar:
• Paul E. McKenney (2024).
Is Parallel Programming Hard, And, If So, What Can You Do About It?
Release v2024.12.27a. Meta Platforms, Inc. Available at https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.2024.12.27a.pdf
• Guerraoui, R., & Kuznetsov, P. (2018).
Algorithms for concurrent systems.
PPUR Presses Polytechniques.
Método de ensino
Aulas teóricas com exposição e debate dos conteúdos conceptuais cobertos na disciplina. Muitas destas aulas são conduzidas de forma interativa, onde os Estudantes são chamados a participar no debate de conceitos e partilha de experiências, que são depois condicionadas para se aproximarem dos temas em estudo e das soluções padrão para esses problemas. As aulas práticas endereçam os aspetos práticos do âmbito da unidade curricular, nomeadamente as técnicas, metodologias e ferramentas para o desenvolvimento de programas concorrentes corretos e com bom desempenho. Estas aulas são também utilizadas para apoiar os Estudantes no desenvolvimento do projeto em grupo da disciplina, que permite aos alunos consolidar, de forma mais autónoma, o conhecimento adquirido nas aulas teóricas.
Método de avaliação
Qualquer aluno envolvido numa fraude em qualquer elemento de avaliação (detetada imediatamente ou a posteriori) reprova na disciplina. Nestes casos será sempre tido em consideração o disposto no nº3 do artigo 10º do Regulamento de Avaliação da FCT NOVA.
Durante o semestre, nas aulas práticas, serão propostos exercícios que serão resolvidos individualmente ou em grupo. Estes exercícios não são avaliados.
Durante o semestre será desenvolvido um projeto em grupos de três estudantes. Este projeto será avaliado por critérios de grupo e critérios individuais. Esta avaliação contribuirá para a componente Avaliação Laboratorial (CLB) da classificação final da UC. Alunos que não subscrevam nenhum dos projetos submetidos para avaliação terão uma classificação de zero valores na CLB.
Durante o semestre serão realizados dois testes teórico-práticos individuais. Estes testes serão avaliados e contribuirão para a componente Avaliação Teórico-Prática (CTP) da classificação final da UC. Em caso de falta a um teste teórico-prático, o estudante terá zero valores na classificação desse teste.
No final do semestre, os estudantes que tenham reprovado à UC ficam habilitados a realizar um exame. O exame será avaliado e será considerado como a componente Avaliação Teórico-Prática (CTP) da classificação final da UC.
No final do semestre, os estudantes que já estejam aprovados à UC poderão (mediante inscrição prévia) realizar um exame de melhoria de nota. O exame será avaliado e será considerado como a componente Avaliação Teórico-Prática (CTP) da classificação final da UC.
Todos os testes e exames são escritos, presenciais e individuais, não sendo permitidos quaisquer materiais de consulta, nem acesso a telemóvel ou a calculadora.
Os estudantes que, abrangidos pelo Regulamento de Avaliação, não sejam obrigados a frequentar as aulas práticas, terão ainda assim de realizar o projeto em grupo e submetê-lo para avaliação na data prevista.
Avaliação:
— Componente Laboratorial (CLB): classificação obtida no projeto, na escala 0,00 a 20,00 valores (com duas casas decimais). Classificação mínima: CLB >= 9,5.
— Componente Teórico-Prática (CTP): média aritmética dos dois testes teórico-práticos, na escala 0,00 a 20,00 valores (com duas casas decimais). Classificação mínima: CTP >= 9,5.
— A não obtenção de classificação mínima na componente CLB ou CTP implica reprovação imediata à UC.
Classificação Final (CF):
• Média ponderada das componentes CLB (20%) e CTP (80%), arredondada às unidades.
Conforme o regulamento de avaliação da FCT, devido à inexistência de frequência neste ano letivo (e consequente alteração da fórmula de cálculo da classificação final) as frequências e respetivas classificações obtidas do ano passado não são consideradas.
Conteúdo
1. Introdução à concorrência e seus desafios.
2. Exclusão mútua: Tempo; Secções críticas; Locks; Equidade.
3. Objetos concorrentes: Correção; Progresso; Objetos sequenciais; Coerência quiescente e sequencial; Linearizabilidade.
4. Fundamentos da memória partilhada: Registos; Construções de registos; Snapshots atómicos.
5. Operações primitivas de sincronização: Monitores e condições; Spin locks; Locks leitor-escritor; Semáforos.
6. Universalidade do consenso: Universalidade; Construções universais não bloqueantes.
7. Contenção com Spin-Locks: Spin locks baseados em Test-And-Set; Backoff exponencial; Locks de fila e hierárquicos.
8. Estruturas de dados não bloqueantes: Listas; Filas; O problema ABA.
9. Memória Transacional: Transações e atomicidade; MT por software; MT por hardware.
10. Gestão de trabalho: Paralelismo; Escalonamento de multiprocessadores; Distribuição de trabalho; Futuros; Filas de espera de Work-Stealing.
11. Concorrência sem dados partilhados: mensagens, atores e objetos ativos.