Strict real-time systems design over multiprocessor-based platforms

En las últimas décadas, la digitalización y automatización han tenido un rol determinante en el desarrollo económico. Cada vez más procesos y actividades están siendo impulsadas por la adopción de nuevas tecnologías, ofreciendo mayores cotas de bienestar. Muchas de estas tecnologías, incluyen el uso de computadores embarcados. Su aplicación se da en, entre otros, sectores como las telecomunicaciones, el transporte, la producción industrial, o la sanidad y la educación, más recientemente. Desde los modernos teléfonos móviles inteligentes a los sistemas de seguridad electrónicos cada vez más extendidos en la industria automovilística, la influencia de los computadores embarcados es cada vez mayor en nuestro día a día. Muchos de estos sistemas se encargan de manejar sistemas críticos, en los que un fallo puede poner en peligro vidas humanas o causar graves pérdidas económicas. Es por ello que estos sistemas presentan requisitos muy estrictos con el objetico de prevenir tan dramáticas consecuencias. Entre ellos se encuentran los requisitos temporales. Estos requisitos implican que la respuesta del sistema, para ser válida no solo ha de ser correcta, si no además producida dentro de unos parámetros temporales determinados. En esta tesis se pretende contribuir al estado de la técnica en el desarrollo de estos sistemas con requisitos temporales estrictos sobre plataformas multiprocesador. Si bien estas modernas plataformas ofrecen una mayor capacidad de cómputo, también presentan mayores dificultades a la hora de alcanzar los estrictos requisitos que imponen los entornos en los que los sistemas embarcados operan. En concreto, esta tesis se centra en el análisis temporal de estos sistemas basados en plataformas multiprocesador. La principal contribución es el estudio y definición del protocolo Multiprocessor resource sharing Protocol (MrsP por sus siglas en inglés). Este protocolo, en esencia, intenta trasladar a los sistemas multiprocesador los conocimientos y técnicas ya empleados satisfactoriamente en los actuales sistemas monoprocesador. Esto se sustancia en el uso del protocolo de techo de prioridad como método de planificación del uso de procesador, arbitrando el acceso a recursos compartidos entre procesadores mediante cerrojos con espera activa. Al realizarse este acceso y espera al techo de prioridad local del recurso, son potencialmente desalojables. Para limitar las consecuencias de un posible desalojo de una tarea durante su acceso al recuros, el protocolo incorpora un mecanismo de ayuda por el cual las tareas haciendo espera activa pueden colaborar con la tarea desalojada localmente a completar su acceso. Las contribuciones de esta tesis incluyen la formalización de un análisis más exacto para el protocolo MrsP, al tener en cuenta la habitual heterogeneidad en los tiempos de acceso a los recursos en función de la acción a llevar a cabo. Posteriormente se extiende el protocolo para dar soporte a la anidación de accesos a recursos compartidos. Para ello, primero se definen las reglas que rigen estos accesos anidados, ofreciendose posteriormente dos métodos para demostrar el cumplimiento de los requisitos temporales. El primero permite realizar dicho análisis con un conocimiento limitado de los patrones de acceso a recursos compartidos. El segundo permite, a partir de un conocimiento completo de dichos patrones, obtener un análisis más ajustado, permitiendo demostrar la viabilidad de un mayor número de sistemas. Estas contribuciones han sido contrastadas mediante un completo trabajo de evaluación publicado durante la investigación que aquí se recoge. En esta tesis, ese trabajo se ve complementado con el análisis del segmento de vuelo de una misión espacial. En la sección de evaluación se detalla el análisis del sistema mediante el protocolo MrsP, el cual se compara con el análisis de una implementación de dicho sistema en un monoprocesador, así como en un multiprocesador utilizando un protocolo comparable. ----------ABSTRACT---------- In the past decades the digitalization and automation have played a key role in the economic growth and development. An increasing number of activities supporting the levels of welfare achieved are based on the adoption of modern technologies in which computers have enabled higher service levels: communications, transportation, industrial production, health care or education are some examples. Nowadays energy production and distribution are controlled by computer systems, as well as our daily communications via mobile phones and emails, and we rely on many electronic-driven safety measures now standard in the automotive industry. Most of these embedded computer systems are in charge of controlling complex critical systems concerning human lives and business viability. These systems present strict requirements to ensure proper behaviour. Some of these requirements address non-functional aspects, as the temporal correctness of the system. In other words, for some relevant computer-controlled systems it is not only important to produce the correct output but also to produce it on time. This dissertation aims to contribute on the development of systems with strict temporal requirements based on multiprocessor platform. Modern hardware technology has enabled the massive production of processors incorporating more than one computation unit per chip, increasing the overall computer performance. These new platforms present, however, a set of challenges to achieve the required reliability according to the critical environments in which they operate. In this dissertation the temporal analysis of real-time systems based on multiprocessor platforms is addressed. In particular it contributes in a number of ways on the de_nition and study of a new scheduling protocol, the Multiprocessor resource sharing Protocol (MrsP). This protocol aims to transfer the most successful approaches from monoprocessor theory and practice in combination with the most promising techniques for strict multiprocessor real-time systems design. This is substantiated in the use of ceiling priority and equivalent stack resource policies as task dispatching strategies with a preemptable spinlocking mechanism for shared resource access arbitration. Global spin delay interference is mitigated by a novel helping mechanism, based on the cooperative completion of resource accesses locally preempted. Speci_c contributions addressed in this work include the formalization of a more exact timing analysis based on the heterogeneity of access times present in practice. The task model is then completed with support for nested resource access patterns, including means for analysing this task model with two scheduling analysis based on the well known response time analysis technique. These two di_erent analysis can prove the system feasibility with di_erent degrees of system knowledge: while the su_cient analysis enables testing the schedulability of the system with reduced knowledge of resource access patterns, a tighter, less pessimistic analysis can achieved when all shared resource access patterns have been fully characterized. These contributions are supported by the extensive evaluation work already published. The evaluation section of this dissertation complements that work with the analysis of the ight segment of a space mission which is then compared with that of a traditional monoprocessor approach as well as with a comparable multiprocessor protocol