Face à estagnação da tecnologia uniprocessador registada na passada década, aos principais fabricantesde microprocessadores encontraram na tecnologia multi-core a resposta `as crescentesnecessidades de processamento do mercado. Durante anos, os desenvolvedores de software viramas suas aplicações acompanhar os ganhos de performance conferidos por cada nova geraçãode processadores sequenciais, mas `a medida que a capacidade de processamento escala em funçãodo número de processadores, a computação sequencial tem de ser decomposta em várias partesconcorrentes que possam executar em paralelo, para que possam utilizar as unidades de processamentoadicionais e completar mais rapidamente.A programação paralela implica um paradigma completamente distinto da programação sequencial.Ao contrário dos computadores sequenciais tipificados no modelo de Von Neumann, aheterogeneidade de arquiteturas paralelas requer modelos de programação paralela que abstraiamos programadores dos detalhes da arquitectura e simplifiquem o desenvolvimento de aplicaçõesconcorrentes. Os modelos de programação paralela mais populares incitam os programadores aidentificar instruções concorrentes na sua lógica de programação, e a especificá-las sob a formade tarefas que possam ser atribuídas a processadores distintos para executarem em simultâneo.Estas tarefas são tipicamente lançadas durante a execução, e atribuídas aos processadores pelomotor de execução subjacente. Como os requisitos de processamento costumam ser variáveis, enão são conhecidos a priori, o mapeamento de tarefas para processadores tem de ser determinadodinamicamente, em resposta a alterações imprevisíveis dos requisitos de execução.`Amedida que o volume da computação cresce, torna-se cada vez menos viável garantir assuas restrições temporais em plataformas uniprocessador. Enquanto os sistemas de tempo real secomeçam a adaptar ao paradigma de computação paralela, há uma crescente aposta em integrarexecuções de tempo real com aplicações interativas no mesmo hardware, num mundo em quea tecnologia se torna cada vez mais pequena, leve, ubíqua, e portável. Esta integração requersoluções de escalonamento que simultaneamente garantam os requisitos temporais das tarefas detempo real e mantenham um nível aceitável de QoS para as restantes execuções. Para tal, torna-seimperativo que as aplicações de tempo real paralelizem, de forma a minimizar os seus temposde resposta e maximizar a utilização dos recursos de processamento. Isto introduz uma novadimensão ao problema do escalonamento, que tem de responder de forma correcta a novos requisitosde execução imprevisíveis e rapidamente conjeturar o mapeamento de tarefas que melhorbeneficie os critérios de performance do sistema.A técnica de escalonamento baseado em servidores permite reservar uma fração da capacidade de processamento para a execução de tarefas de tempo real, e assegurar que os efeitos de latênciana sua execução não afectam as reservas estipuladas para outras execuções. No caso de tarefasescalonadas pelo tempo de execução máximo, ou tarefas com tempos de execução variáveis,torna-se provável que a largura de banda estipulada não seja consumida por completo. Paramelhorar a utilização do sistema, os algoritmos de partilha de largura de banda (capacity-sharing)doam a capacidade não utilizada para a execução de outras tarefas, mantendo as garantias deisolamento entre servidores.Com eficiência comprovada em termos de espaço, tempo, e comunicação, o mecanismo dework-stealing tem vindo a ganhar popularidade como metodologia para o escalonamento de tarefascom paralelismo dinâmico e irregular. O algoritmo p-CSWS combina escalonamento baseadoem servidores com capacity-sharing e work-stealing para cobrir as necessidades de escalonamentodos sistemas abertos de tempo real. Enquanto o escalonamento em servidores permitepartilhar os recursos de processamento sem interferências a nível dos atrasos, uma nova políticade work-stealing que opera sobre o mecanismo de capacity-sharing aplica uma exploração deparalelismo que melhora os tempos de resposta das aplicações e melhora a utilização do sistema.Esta tese propõe uma implementação do algoritmo p-CSWS para o Linux. Em concordânciacom a estrutura modular do escalonador do Linux, ´e definida uma nova classe de escalonamentoque visa avaliar a aplicabilidade da heurística p-CSWS em circunstâncias reais. Ultrapassadosos obstáculos intrínsecos `a programação da kernel do Linux, os extensos testes experimentaisprovam que o p-CSWS ´e mais do que um conceito teórico atrativo, e que a exploração heurísticade paralelismo proposta pelo algoritmo beneficia os tempos de resposta das aplicações de temporeal, bem como a performance e eficiência da plataforma multiprocessador.
展开▼
