Blocking analysis of spin locks under partitioned fixed-priority scheduling

Abstract

Partitioned fixed-priority scheduling is widely used in embedded multicore real-time systems. In multicore systems, spin locks are one well-known technique used to synchronize conflicting accesses from different processor cores to shared resources (e.g., data structures). The use of spin locks can cause blocking. Accounting for blocking is a crucial part of static analysis techniques to establish correct temporal behavior. In this thesis, we consider two aspects inherent to the partitioned fixed-priority scheduling of tasks sharing resources protected by spin locks: (1) the assignment of tasks to processor cores to ensure correct timing, and (2) the blocking analysis required to derive bounds on the blocking. Heuristics commonly used for task assignment fail to produce assignments that ensure correct timing when shared resources protected by spin locks are used. We present an optimal approach that is guaranteed to find such an assignment if it exists (under the original MSRP analysis). Further, we present a well-performing and inexpensive heuristic. For most spin lock types, no blocking analysis is available in prior work, which renders them unusable in real-time systems. We present a blocking analysis approach that supports eight different types and is less pessimistic than prior analyses, where available. Further, we show that allowing nested requests for FIFO- and priority-ordered locks renders the blocking analysis problem NP-hard.

Partitioned Fixed-Priority Scheduling ist in eingebetteten Multicore-Echtzeitsystemen weit verbreitet. In Multicore-Systemen sind Spinlocks ein bekannter Mechanismus um konkurrierende Zugriffe von unterschiedlichen Prozessorkernen auf geteilte Resourcen (z.B. Datenstrukturen) zu koordinieren. Bei der Nutzung von Spinlocks können Blockierungen auftreten, die in statischen Analysetechniken zum Nachweis des korrekten zeitlichen Verhaltens eines Systems zu berücksichtigen sind. Wir betrachten zwei Aspekte von Partitioned Fixed-Priority Scheduling in Verbindung mit Spinlocks zum Schutz geteilter Resourcen: (1) die Zuweisung von Tasks zu Prozessorkernen unter Einhaltung zeitlicher Vorgaben und (2) die Analyse zur Entwicklung oberer Schranken für die Blockierungsdauer. Übliche Heuristiken finden bei der Nutzung von Spinlocks oft keine Taskzuweisung, bei der die Einhaltung zeitlicher Vorgaben garantiert ist. Wir stellen einen optimalen Ansatz vor, der dies (mit der ursprünglichen MSRP Analyse) garantiert, falls eine solche Zuweisung existiert. Zudem präsentieren wir eine leistungsfähige Heuristik. Die meisten Arten von Spinlocks können mangels Analyse der Blockierungsdauer nicht für Echtzeitsysteme verwendet werden. Wir stellen einen Analyseansatz vor, der acht Spinlockarten unterstützt und weniger pessimistische Schranken liefert als vorherige Analysen, soweit vorhanden. Weiterhin zeigen wir, dass die Analyse bei verschachtelten Zugriffen mit FIFO- und prioritäts-geordneten Locks ein NP-hartes Problem ist.