Alexander Züpke

• Real-time operating systems for mixed-criticality systems must support different types of software, such as real-time applications and general purpose applications, and, at the same time, must provide strong spatial and temporal isolation between independent software components. Therefore, state-of-the-art real-time operating systems focus mainly on predictability and bounded worst-case behavior. However, general purpose operating systems such as Linux often feature more efficient---but less deterministic---mechanisms that significantly improve the average execution time. This thesis addresses the combination of the two contradicting requirements and shows thread synchronization mechanisms with efficient average-case behavior, but without sacrificing predictability and worst-case behavior. This thesis explores and evaluates the design space of fast paths in the implementation of typical blocking synchronization mechanisms, such as mutexes, condition variables, counting semaphores, barriers, or message queues. The key technique here is to avoid unnecessary system calls, as system calls have high costs compared to other processor operations available in user space, such as low-level atomic synchronization primitives. In particular, the thesis explores futexes, the state-of-the-art design for blocking synchronization mechanisms in Linux that handles the uncontended case of thread synchronization by using atomic operations in user space and calls into the kernel only to suspend and wake up threads. The thesis also proposes non-preemptive busy-waiting monitors that use an efficient priority ceiling mechanism to prevent the lock holder preemption problem without using system calls, and according low-level kernel primitives to construct efficient wait and notify operations. The evaluation shows that the presented approaches improve the average performance comparable to state-of-the-art approaches in Linux. At the same time, a worst-case timing analysis shows that the approaches only need constant or bounded temporal overheads at the operating system kernel level. Exploiting these fast paths is a worthwhile approach when designing systems that not only have to fulfill real-time requirements, but also best-effort workloads.
• Echzeitbetriebssysteme für Systeme mit gemischten Kritikalitäten müssen unterschiedliche Arten von Software, wie z.B. Echtzeitanwendungen und Allzweckanwendungen, gleichzeitig unterstützen. Dabei müssen sie eine solide räumliche und zeitliche Isolation zwischen unabhängigen Softwarekomponenten bieten. Daher fokussieren sich aktuelle Echtzeitbetriebssysteme hauptsächlich auf Vorhersagbarkeit und ein berechenbares Worst-Case-Verhalten. Allerdings bieten Allzweck-Betriebssysteme wie Linux häufig effizientere, aber weniger deterministische Mechanismen, welche die durchschnittliche Ausführungszeit signifikant erhöhen. Diese Thesis befasst sich mit der Kombination der beiden gegensätzlichen Anforderungen und zeigt Mechanismen zur Thread-Synchronisation mit einem effizienten Durchschnittsverhalten, ohne jedoch die Vorhersagbarkeit und das Worst-Case-Verhalten zu beeinträchtigen. Diese Thesis untersucht und bewertet den Entwurfsraum von Abkürzungen (engl. fast paths) bei der Umsetzung von typischen blockierenden Synchronisationsmechanismen wie Mutexen, Bedingungsvariablen, Zähl-Semaphoren, Barrieren oder Nachrichtenwarteschlangen. Der Ansatz ist dabei, unnötige Systemaufrufe zu vermeiden. Systemaufrufe haben im Vergleich zu anderen Prozessoroperationen, die im Benutzermodus verfügbar sind, wie z.B. atomaren Operationen, höhere Kosten. Insbesondere erforscht die Thesis Futexe, ein aktuelles Design für blockierende Synchronisationsmechanismen in Linux, welches den konkurrenzfreien Fall der Synchronisierung mithilfe atomarer Operationen im Benutzermodus löst und den Kern nur aufruft, um Threads zu suspendieren und aufzuwecken. Die Thesis untersucht auch nicht-unterbrechbare Monitore mit aktivem Warten. Dort wird ein effizienter Mechanismus mit Prioritätsschranken verwendet, um das sogenannte Lock-Holder-Preemption-Problem ohne Systemaufrufe zu vermeiden. Ebenfalls werden passende niedere Kernprimitive beschrieben, die effiziente Warte- und Benachrichtigungsoperationen ermöglichen. Die Evaluation zeigt, dass die vorgestellten Ansätze die durchschnittliche Leistung vergleichbar zu aktuellen Ansätzen in Linux verbessern. Gleichzeitig zeigt eine Analyse des Worst-Case Zeitverhaltens, dass die Ansätze nur konstante oder begrenzte zeitliche Mehraufwände auf der Ebene des Betriebssystemkerns benötigen. Die Nutzung dieser Abkürzungen ist ein lohnender Ansatz für den Entwurf von Systemen, die nicht nur Echtzeitanforderungen erfüllen, sondern auch Allzweckanwendungen gut unterstützen sollen.