On time-deterministic multicore virtualization techniques

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Ciência da Computação, Florianópolis, 2018.A complexidade crescente dos sistemas de tempo real aliada aos avanços nas tecnologias de processadores está proporcionando o uso de arquiteturas multiprocessadas também no domínio de tempo real embarcado. Como consequência, funcionalidades que eram implementadas utilizando-se hardware dedicado agora estão sendo implementadas por uma coleção de tarefas executando em um sistema operacional de tempo real. A mudança de hardware dedicado para multiprocessadores, os quais compartilham tanto memória como Entrada e Saída (do inglês, Input/Output - I/O), levanta questões complexas sobre o isolamento espacial e temporal de tarefas. Neste cenário, máquinas virtuais executando sobre um hypervisor representam uma solução bem estabelecida com respeito ao isolamento espacial, uma vez que cada máquina virtual utiliza o seu próprio espaço de endereçamento e é protegida das demais por meio de uma Unidade de Gerenciamento de Memória (do inglês, Memory Management Unit - MMU). Isolamento temporal, entretanto, tem sido alvo de intensa pesquisa ultimamente. Escalonamento tempo real, tratamento de interrupção multinível e troca de contexto com precisão de ciclo são exemplos de técnicas incorporadas neste cenário. Entretanto, isolamento temporal ainda não foi completamente explorado, assim como diversos aspectos de arquiteturas multiprocessadas tem sido insuficientemente investigados. Este trabalho investiga o impacto de interferência temporal que um domínio pode causar em outro enquanto executando em um cenário onde memória Cache de Último Nível (do inglês, Last-level Cache - LLC) e interconexões (de memória e de I/O) são compartilhadas. Um sistema de criticalidade mista é levado em consideração o qual é composto por dois níveis de criticalidade: LO (baixo / não crítico) e HI (alto / temporalmente crítico). São considerados dois tipos de domínios, domínios-HI que executam tarefas temporalmente críticas (tarefas-HI) e domínios-LO que executam tarefas não críticas (tarefas-LO). Em um determinado instante do tempo, o sistema pode operar em modo LO ou modo HI, dependendo da interferência temporal que é percebida. Enquanto o sistema está operando em modo LO, ambas as tarefas-LO e tarefas-HI podem executar. Enquanto o sistema está operando em modo HI, todas as tarefas-LO são suspensas e somente tarefas-HI são permitidas a executar. Um mecanismo para ligar e desligar dispositivos de I/O é empregado para reduzir a interferência causada por contenção nas interconexões. A semântica do desligamento de dispositivos depende da classe do dispositivo e se ele é físico ou virtual. Por exemplo, enquanto o desligamento de uma Unidade Central de Processamento Física (do inglês, Physical Central Processing Unit - PCPU) implica em alterar os níveis de tensão e corrente elétrica enviados ao dispositivo, o desligamento de uma Unidade Central de Processamento Virtual (do inglês, Virtual Central Processing Unit - VCPU) pode significar apenas suspender a thread do hypervisor utilizada para implementar a VCPU em questão. Este trabalho introduz uma abordagem de modelagem que captura os requisitos de processamento e I/O de tarefas periódicas de um sistema operacional convidado (as quais compõem um domínio) e as abstrai em um Modelo de Recursos de Domínio (do inglês, Domain Resource Model - DRM). Um DRM define as reservas de recursos (I/O e processamento) disponíveis a um domínio como também o período de recarga destas reservas. Escalonabilidade de domínio é então definida comparando a demanda gerada pelas tarefas do sistema operacional convidado com a reserva que é provida pelo DRM. Escalonabilidade de sistema é definida compondo a reserva de todos os DRMs em conjunto e verificando se a plataforma de hardware subjacente é capaz de atendê-la. É assumido que os requisitos dos domínios-HI são sempre conhecidos, enquanto os requisitos dos domínios-LO podem ser conhecidos ou não. Também é assumido que a topologia física empregada (composta por processadores, dispositivos de I/O e suas interconexões) é conhecida. É conhecida também a alocação física, isto é, quais domínios utilizam quais recursos. A abordagem de modelagem proposta possui duas fases principais, uma em tempo de projeto e outra em tempo de execução. Durante a fase de projeto, domínios-HI e domínios-LO conhecidos executam e os eventos relacionados ao overhead são medidos, como o número de faltas na LLC e o tempo de contenção nas interconexões. Tais informações são utilizadas para inflar os requisitos das tarefas de sistema operacional convidado e para computar DRMs cientes de overhead. Durante tempo de execução, novos domínios podem ser admitidos no sistema desde que eles não rompam com a escalonabilidade de domínios-HI em modo HI nem com a escalonabilidade de sistema. Durante tempo de execução, informação relacionada ao overhead é continuamente monitorada e usada para inflar a reserva dos domínios e na execução de testes de escalonabilidade destes. Sempre que é detectado que algum domínio-HI se tornará não escalonável em modo LO, o sistema muda de modo LO para modo HI evitando que domínios-HI percam deadlines. O sistema muda de volta para modo LO sempre que a interferência decresce a ponto de domínios-HI serem escalonáveis novamente em modo LO. A abordagem de modelagem proposta, baseada no DRM, foi avaliada em domínios com requisitos de processamento e I/O distintos e com níveis de criticalidade distintos. As avaliações abordam não apenas tempo de projeto, como também simulam mudanças em tempo de execução, mostrando como a admissão de novos domínios pode impactar na escalonabilidade. A abordagem proposta foi avaliada de acordo com decisões de escalonamento frente a mudanças na quantidade de interferência percebida como o número de faltas na LLC e mudanças na topologia física na medida em que dispositivos eram ligados ou desligados. A abordagem proposta foi também avaliada quanto ao uso de recursos físicos. Comparando a abordagem proposta com o modelo de Recursos Periódicos de Multiprocessados (do inglês, Multiprocessor Periodic Resource - MPR), a abordagem proposta apresenta uma maior demanda por PCPUs, pois ela utiliza PCPUs para implementar não somente VCPUs de execução como também VCPUs que tratam operações de I/O. No entanto, ao comparar decisões de escalonamento, a abordagem proposta apresenta melhores resultados que MPR uma vez que a abordagem proposta é ciente de overhead e pode escolher desligar domínios-LO evitando que domínios-HI percam deadlines em modo HI.Abstract : The growing complexity of real-time systems and the advances in processor technology are enabling the use of multicore architectures also in the real-time embedded system domain. As a consequence, features that used to be implemented using dedicated hardware are now being implemented by a collection of tasks running on a Real-time Operating System (RTOS). The shift from dedicated hardware to multicore processors, which share both I/O and memory, raises complex issues about the spatial and temporal isolation of tasks. In this scenario, Virtual Machines atop a hypervisor is a well-established solution with respect to spatial isolation, since each Virtual Machine (VM) uses its own address space and are protected from each other by ordinary MMUs. Temporal isolation, however, has been a subject of intense research lately. Real-time scheduling, multi-level interrupt handling, and cycle-accurate context switching are examples of techniques incorporated in this scenario. However, temporal isolation has not been fully explored yet, and several aspects of multicore architectures have been poorly investigated. This work investigates the impact of temporal interference that a domain can cause on another while running in a scenario where Last-level Cache (LLC) and interconnects (memory and I/O) are shared. It is taken into account a mixed criticality system, composed of two levels of criticality LO (non-critical) and HI (time-critical). Two types of domains are considered, HI-domains that run time-critical tasks (HI-tasks), and LO-domains that run non-critical tasks (LO-tasks). In a given moment of time, the system can operate either in LO or HI mode depending on the perceived temporal interference. While the system is operating in LO mode, both LO-tasks and HI-tasks can execute. While the system is running in HI mode, all LO-tasks are suspended, and only HI-tasks are allowed to run. A mechanism of powering ON and OFF I/O devices is employed to reduce the interference caused by the interconnect contention. The semantics of powering OFF devices depends on the device class, and on either the device is physical or virtual. For instance, while the powering OFF of a Physical Central Processing Unit (PCPU) means to change the voltage and electric current levels that are sent to the device, the powering OFF of a Virtual Central Processing Unit (VCPU) means to suspend the hypervisor thread employed to implement such a VCPU. This work introduces a modeling approach, which captures the processing and I/O requirements of periodic guest Operating System (OS) tasks that compose a domain and abstracts them into a Domain Resouce Model (DRM). A DRM defines the resource (CPU and I/O) budgets available to a domain as well the replenishment periods of such budgets. Domain schedulability is then defined by comparing the demand generated by the guest OS tasks to the budget supplied by the DRM. System schedulability is defined by composing the budget of all DRMs together, and by checking whether the underlying physical platform is able to attend them. It is assumed that requirements of HI-domains are always known, while the requirements of LO-domains can be known or not. It is also assumed that the employed physical topology (composed by processors, I/O devices, and their interconnections) is known. The physical allocation it is also known (i.e. whiches domains use whiches resources). The proposed modeling approach has two main phases, one at design time and other at runtime. During the design phase, HI-domains and known LO-domains execute and overhead related events are measured, such as the number of LLC misses, and the interconnect contention time. Such information is used to inflate the requirements of guest OS tasks and to compute overhead-aware DRMs. During runtime, new domains might be admitted in the system as long they do not disrupt the schedulability of HI-domains in HI mode neither the system schedulability. During runtime, overhead information is monitored continuously and used to inflate the budget of domains and to run scheduling test of domains. Whenever is detected that some HI-domain will become unschedulable in LO mode, there is a HI to LO mode switch, preventing HI-domains from missing deadlines. The system switches back to LO mode whenever the interference decreases and HI-domains are schedulable again in LO mode. The proposed modeling approach, based on DRM, was evaluated for domains with distinct processing and I/O requirements, and distinct criticality levels. The evaluations comprise not only design time requirements but simulate changes in the runtime scenario, showing how the admission of new domains can impact with the schedulability. The proposed approach was evaluated according to scheduling decisions facing changes in the perceived interference such as the number of LLC misses, and changes in the physical topology as devices were powered ON and OFF. The proposed approach was evaluated also regarding the use of physical resources. Comparing the proposed approach with the Multiprocessor Periodic Resource (MPR) modeling, it presents a higher PCPU demand since it uses PCPUs for implementing not only execution VCPUs but also for implementing VCPUs that handle I/O operations. However, while comparing scheduling decisions, the proposed approach presents better results than MPR since the proposed approach is overhead-aware and can choose to power OFF LO domains avoiding deadline misses of HI-domains in HI mode