tailieunhanh - Digitale Hardware/ Software-Systeme- Part 16

Digitale Hardware/ Software-Systeme- P16:Getrieben durch neue Technologien und Anwendungen wird der Entwurf eingebetteter Systeme zunehmend komplexer. Dabei ist eine Umsetzung als Hardware/Software- System heutzutage der Stand der Technik. Die Minimierung von Fehlern im Entwurf dieser Systeme ist aufgrund deren Komplexit¨at eine der zentralen Herausforderungen unserer heutigen Zeit. Bereits heute wird mehr Aufwand in die Verifikation, also in die U¨ berpru¨fung der Korrektheit, eines eingebetteten Systems gesteckt als in den eigentlichen Entwurf | 444 7 Software-Verifikation a CPU T T T T T n 0 n 1 n 2 n 4 V1 V2 V1 V2 V1 V2 V1 V2 V1 V2 n 0 T V . . n 1 T V 0 12 3 4 5 6 7 8 9 10 11 T b CPU Td V1 Td V1 n 0 n 1 z V1 V2 V1 V2 V1 V2 n 0 Td V2 1 1 1 1 1 1 0123456789 1 11 T Abb. . Iterative dynamische Ablaufplane a mit der EDF-Strategie und b mit dem RMS-Algorithmus Ratenmonotone Ablaufplanung Unter dem Begriff ratenmonotone Ablaufplanung engl. rate-monotonic scheduling RMSs haben Liu und Layland ein präemptives Ablaufplanungsverfahren beschrieben das den Prozessen statische Prioritaten nach folgendem Prinzip zuweist vi habe größere Prioritat als Vj falls P vi P vj . Also wahlt man die Prioritat statisch beispielsweise proportional zur gegebenen Rate eines Prozesses Kehrwert der Periode . Prozesse mit kleinerer Periode werden also hoher priorisiert als Prozesse mit größerer Periode. Dies gilt also unabhangig von den Ausführungszeiten der Prozesse. Bei Ankunft eines Prozesses hoherer Prioritat wird der laufende Prozess unterbrochen. Beispiel . Abbildung zeigt einen mit der RMS-Strategie gewonnenen Ablaufplan für das in Beispiel vorgestellte Problem. Liu und Layland zeigten dann dass der RMS-Algorithmus unter allen Algorithmen mit statischen Prioritaten für den von ihnen angenommen Fall r vi P vi immer einen gültigen Ablaufplan bestimmt falls ein solcher existiert. Beispiel . Aus diesem Ergebnis lasst sich schließen dass es keinen Algorithmus mit festen Prioritaten gibt der für das Problem aus Beispiel alle Deadlines erfüllt da der RMS-Algorithmus keinen solchen Ablaufplan bestimmt hat. Nun lasst sich allerdings ein einfaches hinreichendes Kriterium angeben wann der RMS-Algorithmus immer einen Ablaufplan findet der alle Deadlines erfüllt Zeitanalyse 445 Theorem Liu und Layland . Gegeben sei ein Ablaufplanungsproblem nach Definition mit der Eigenschaft Vvi e V t v P vi . Die Menge von Prozessen kann unter Erfüllung aller Deadlines mit dem RMS-Algorithmus geplant werden .