Technisches Anwendungsgebiet Die vorliegende Erfindung betrifft eine Prozessor- architektur, bei der der Zugriff auf einen Speicher über Zeiger erfolgt, die auf Objekte verweisen.

Die Beherrschung der Komplexität von Software ist die größte Herausforderung bei der Software-Entwick- lung. Qualitativ hochwertige und zuverlässige Systeme sind nur dann realisierbar, wenn es gelingt, Software in überschaubare und beherrschbare Module zu zerlegen und abstrakt zu beschreiben. Um dies zu erreichen, werden seit einigen Jahren objektorientierte Program- miersprachen eingesetzt.

Ein zentrales Problem bei der Implementierung objektorientierter Programmiersprachen ist die dyna- mische Speicherverwaltung. Einige wenige objekt- orientierte Sprachen wie z. B. C++ bauen noch auf manuelle Speicherverwaltung, d. h. dass Speicher unter der Verantwortung des Programmierers sowohl angefordert als auch wieder frei gegeben wird. Dieser Ansatz hat jedoch den Nachteil, dass die problemangepasste, natürliche Modellierung eines Systems oft nicht möglich ist, da beim Entwurf des Systems auch die Speicher- verwaltung realisiert werden muss. Weiterhin ist die manuelle Freigabe von Speicher Ursache einer ganzen Klasse von Programmfehlern. Wird bspw. ein Speicher- bereich freigegeben, obwohl noch Verweise auf diesen Speicherbereich existieren, kann dies im weiteren Programmablauf katastrophale Folgen nach sich ziehen.

Besonders gravierend ist hierbei, dass die Folgen der durch die noch existenten Zeiger auf den bereits frei gegebenen Speicherbereich (sog. dangling references) verursachten Fehler von vielen Faktoren abhängen und deshalb kaum zu reproduzieren und nur schwer zu loka- lisieren sind. Aus diesen Gründen bauen fast alle modernen Programmiersprachen, wie bspw. Java, auf dynamische Speicherverwaltung mit automatischer Speicherbereinigung (sog. garbage collection). In Systemen mit dieser dynamischen Speicherverwaltung können Speicherbereiche nicht unter Verantwortung des Programms zurück gegeben werden. Statt dessen gibt ein Speicherbereiniger (garbage collector) die Speicher- bereiche automatisch erst dann frei, wenn sie von einem Programm sicher nicht mehr referenziert werden. Dadurch können prinzipbedingt keine"dangling references" auftreten. Weiterhin erhöht der Einsatz dieser Technik die Produktivität der Programmierer, da diese sich nun vollständig der Lösung des eigentlichen Problems widmen können. Schließlich ist die erstellte Software von höherer Qualität, da die Wahrscheinlichkeit versteckter Programmfehler in einem System mit dynamischer Spei- cherverwaltung deutlich geringer ist als in einem System mit manueller Speicherverwaltung.

Stand der Technik Für die automatische Freigabe dynamisch angelegter Speicherbereiche existieren zahlreiche Algorithmen, die dem Fachmann unter den Begriffen Reference Counting, Copying und Mark Sweep Collection bekannt sind. Für einen Überblick über diese Algorithmen wird auf R.

Jones, R. Lins :"Garbage Collection : Algorithms for Automatic Dynamic Memory Management", John Wiley & Sons, 1996, verwiesen.

Einfache Implementierungen dieser Algorithmen unterbrechen das Anwendungsprogrammm für die gesamte Dauer eines Speicherbereinigungszyklus. Sie verursachen in der Regel lange und unvorhersehbare Pausen in der Programmausführung und sind deshalb nicht für inter- aktive Systeme oder Echtzeitumgebungen geeignet.

Inkrementelle und nebenläufige Verfahren erlauben es, die Programmausführung während eines Speicherberei- nigungszyklus fortzusetzen. Sie erfordern allerdings die Synchronisation zwischen Anwendungsprogramm und Speicherbereiniger. Die Kosten dieser Synchronisation in Software sind jedoch erheblich, da, je nach verwen- detem Verfahren, entweder vor jedem Laden eines Zeigers (read barrier) oder vor jedem Speichern eines Zeigers (write barrier) eine kurze Codesequenz eingefügt werden muss, um festzustellen, ob das zugehörige Objekt vom Speicherbereiniger bereits bearbeitet wurde.

Viele inkrementelle Verfahren werden als"echt- zeitfähig"beschrieben, weil die vom Speicherbereiniger verursachten Pausen in den meisten Fällen zu kurz sind, um vom Anwender registriert zu werden. Harte Echtzeit- fähigkeit erfordert jedoch die Garantie einer konstan- ten oberen Schranke für die Antwortzeit eines Systems.

Da software-basierte Verfahren in der Regel auf nicht unterbrechbare Operationen wie die Untersuchung aller Zeiger der Wurzelmenge (Register und Stapel) oder die Bearbeitung eines vollständigen Objekts angewiesen sind, genügen sie harten Echtzeitanforderungen nicht.

Es sind zwar Software-Lösungen bekannt, die ohne ato-

mare Operationen unbeschränkter Dauer auskommen, jedoch ist der Overhead dieser Lösungen an Rechenzeit und Speicher erheblich.

Ein grundsätzliches Problem aller Techniken zur automatischen Speicherbereinigung besteht im Auffinden und Identifizieren von Zeigern. Wenn Zeiger nicht ein- deutig von Nicht-Zeigern unterschieden werden können, so lässt sich lediglich eine konservative Speicher- bereinigung durchführen. Dies bedeutet, dass jedes Bitmuster, das einen Zeiger darstellen könnte, auch als Zeiger betrachtet werden muss, um die Freigabe von noch in Benutzung befindlichem Speicher zu vermeiden. Bei einer konservativen Speicherbereinigung dürfen daher keine kompaktierenden Verfahren eingesetzt werden, die Objekte verschieben und Zeiger aktualisieren. Ohne kom- paktierende Verfahren wird der Speicher jedoch fragmen- tiert.

Zur Vermeidung dieser Problematik und zur Durch- führung einer exakten Speicherbereinigung wird ein großer Aufwand bei der Suche und Identifizierung von Zeigern betrieben. Bei vielen objektorientierten Spra- chen können Zeiger in Objekten über Typbeschreibungen (type descriptors) identifiziert werden, die in jedem Objekt enthalten sind. Die Lokalisierung von Zeigern im Programmstapel sowie in den Prozessorregistern ist jedoch schwieriger, insbesondere im Zusammenhang mit optimierenden Compilern. Es ist zwar möglich, Daten- strukturen zu unterhalten, in denen die Stapelpositio- nen und die Prozessorregister angegeben sind, die momentan Zeiger enthalten, jedoch sind die Kosten zur Aktualisierung derartiger Datenstrukturen während der Programmausführung sehr hoch. Aus diesem Grund ver-

wenden die meisten software-basierten Verfahren vom Compiler erzeugte Tabellen, die die Lage der Zeiger im Programmstapel sowie in den Registern beschreiben. Für jeden Programmpunkt, an dem eine Speicherbereinigung durchgeführt werden könnte, wird ein Satz derartiger Tabellen erstellt. Die Realisierung dieser Technik führt jedoch zu einem beträchtlichen Aufblähen des Programmcodes. Weiterhin müssen Echtzeitsysteme sicher stellen, dass zu suspendierende Threads den nächsten derartigen Programmpunkt innerhalb einer begrenzten Zeitspanne erreichen.

Mit den bisher bestehenden Systemen, die in erster Linie auf eine automatische Speicherbereinigung in Software setzen, müssen somit zahlreiche Probleme bewältigt werden. Dies beruht vor allem darauf, dass die Software Funktionen nachbilden muss, die die zugrunde liegende Hardware nicht zur Verfügung stellt.

Viele Probleme hinsichtlich Effizienz und Echtzeit- fähigkeit können behoben werden, wenn der Prozessor selbst die automatische Speicherbereinigung ganz oder teilweise in Hardware durchführt. Dafür ist es jedoch zwingend erforderlich, dass der Prozessor Zeiger iden- tifizieren kann.

Im Folgenden werden von den zahlreichen bekannten Architekturen lediglich zwei beispielhaft angeführt, die eine exakte Zeigeridentifizierung und/oder automa- tische Speicherbereinigung unterstützen und für den Gegenstand der vorliegenden Erfindung von Bedeutung sind.

So sind seit 1966 Architekturen bekannt, die sog.

Capabilities an Stelle von direkten Zeigern einsetzen, um Speicherbereiche zu adressieren. Capabilities ent- halten Angaben zur Zugangsberechtigung und Identifizie- rung von Objekten. Sie enthalten nicht die physikali- sche Adresse des Objekts, sondern einen Verweis auf einen Deskriptor, der den Ort, die Größe sowie weitere Eigenschaften des Objekts beschreibt. Ein Beispiel für einen Prozessor mit einer derartigen Architektur ist der Intel iAPX 432, wie er bspw. in H. M. Levy : "Capability-Based Computer Systems", Digital Press, 1984, Seiten 159-186, beschrieben ist. In dieser Architektur wird eine Capabilitiy durch einen zweistu- figen Abbildungsprozess mit dem zugehörigen Objekt assoziiert. Für jedes Objekt existiert ein eindeutiger Eintrag in einer Objekttabelle, der den Ort, die Größe und den Zustand des Objekts beschreibt. Jedes Objekt besteht aus zwei Bereichen : Einem Datenbereich und einem Bereich für Capabilities. Auf diese Weise wird eine exakte Capability-Identifizierung ermöglicht.

Durch das Fehlen eines Registersatzes und die doppelt indirekte Adressierung eines Objekts über Capabilities und Objektdeskriptoren ist der iAPX 432 äußerst ineffizient. Weiterhin führt er selbst keine automatische Speicherbereinigung durch. Die Speicher- bereinigung muss in Software erfolgen und ist nicht echtzeitfähig.

Alle bekannten Verfahren zur Identifizierung von direkten Zeigern verwenden in jedem Speicherwort ein spezielles Kennzeichnungsbit (tag) zur Unterscheidung von Zeigern und Nicht-Zeigern. Ein Beispiel dafür ist das in der US 5,560, 003 A beschriebene System und Hard-

ware-Modul für inkrementelle Speicherbereinigung in Echtzeit, das sich aus zwei Speicherbänken und einem Lokalprozessor zusammensetzt, der die Speicherbereini- gung durchführt. Jede Speicherbank wird von einem sog.

Objektraum-Manager unterstützt, der bei jedem Speicher- zugriff die Startadresse des entsprechenden Objekts ermittelt. Aufgrund seiner Komplexität muss dieser Objektraum-Manager als getrenntes ASIC realisiert werden, das eine ähnliche Chipfläche beansprucht wie der Speicher selbst. Ein derartiges System ist sehr kostspielig. Weiterhin verursacht die Identifizierung von Zeigern mit Hilfe von Kennzeichnungsbits zusätz- lichen Aufwand in Form von Rechenzeit und Speicherbe- darf.

Wegen der ständig steigenden Komplexität der Soft- ware in eingebetteten Systemen werden seit einigen Jahren große Anstrengungen unternommen, die Vorteile der automatischen Speicherbereinigung auch diesem wirt- schaftlich wichtigen Bereich zugänglich zu machen.

Gerade in diesem Bereich der modernen Informationstech- nik werden die größten Stückzahlen erzielt. Da die Produktzyklen durch ständige Innovation immer kürzer werden, steigt die Nachfrage nach robusten und echt- zeitfähigen Plattformen für eingebettete Systeme für moderne objektorientierte Sprachen ständig. Allerdings wird die automatische Speicherbereinigung für diese Anwendungen in den meisten Fällen noch immer als ein Luxus betrachtet, den man sich trotz der unumstrittenen Vorteile der automatischen Speicherbereinigung nicht leisten kann.

Ausgehend von diesem Stand der Technik besteht die Aufgabe der vorliegenden Erfindung darin, eine Prozes- sorarchitektur für objektbasierte und objektorientierte Programme anzugeben, die eine kostengünstige exakte Zeigeridentifizierung ermöglicht und somit den Weg für eine effiziente und echtzeitfähige automatische Speicherbereinigung freigibt, die ganz oder teilweise in Hardware realisiert werden kann.

Darstellung der Erfindung Die Aufgabe wird mit der Prozessorarchitektur gemäß Patentanspruch 1 gelöst. Vorteilhafte Ausge- staltungen der Prozessorarchitektur sind Gegenstand der Unteransprüche oder lassen sich aus der nachfolgenden Beschreibung sowie den Ausführungsbeispielen entnehmen.

Im Rahmen der vorliegenden Patentanmeldung wird der Begriff Wort als Dateneinheit verstanden, die mittels einer einzigen Prozessoranweisung aus dem Spei- cher geladen oder im Speicher abgelegt werden kann.

Unter einem Objekt wird eine zusammenhängende Menge an Speicherworten verstanden, in der jedes Wort exklusiv einem einzelnen Objekt angehört. Unter einem Zeiger wird ein Wort verstanden, das auf ein Objekt verweist.

Der Begriff Null repräsentiert einen fest vorgegebenen Zeigerwert, der benutzt wird, um auf kein Objekt zu verweisen.

Bei der vorliegenden Prozessorarchitektur für objektbasierte und objektorientierte Programme erfolgt der Zugriff auf den Speicher ausschließlich über Zeiger, die direkt auf Objekte verweisen. Ein Objekt wird in einem zusammenhängenden Speicherbereich exklu-

siv abgelegt, d. h. die von zwei Objekten belegten Speicherbereiche dürfen sich nicht überlappen. In jedem Objekt werden Zeiger in einem Zeigerbereich und Daten in einem Datenbereich getrennt voneinander abgelegt.

Darüber hinaus werden in jedem Objekt Informationen über die Länge des Zeigerbereichs und die Länge des Datenbereichs abgelegt. Diese Längeninformationen werden nachfolgend als Attribute bezeichnet. Mit Hilfe der Attribute ist es jederzeit möglich, die Größe eines Objekts zu bestimmen und die Zeiger und Daten in einem Objekt eindeutig voneinander abzugrenzen.

Die vorliegende Prozessorarchitektur stellt getrennte Zeigerregister-und Datenregistersätze zur Verfügung. Dabei sind Zeigerregister ausschließlich für Operationen mit Objekten wie bspw. für Speicherzugriffe vorgesehen und werden nicht für andere Aufgaben verwen- det. Dadurch wird insbesondere sichergestellt, dass keine beliebigen Werte in Zeigerregister geschrieben werden und keine arithmetischen Operationen mit Zeiger- registern durchgeführt werden können.

Die Zeiger in den Zeigerbereichen der Objekte und in den Zeigerregistern enthalten direkt die Adresse der Objekte im Speicher.

Mit der vorliegenden objektbasierten Prozessor- architektur wird auf diese Weise eine strikte Trennung von Zeigern und Nicht-Zeigern (Daten) realisiert, sodass eine exakte Zeigeridentifizierung ohne die Not- wendigkeit von Kennzeichnungsbits möglich ist. Durch diese von der Hardware sicher gestellte exakte Identi- fizierbarkeit der Zeiger in den Prozessorregistern und im Speicher lässt sich eine automatische Speicherberei- nigung auf Prozessorebene integrieren, die ganz oder

teilweise in Hardware implementiert werden kann. Auf dieser Grundlage werden echtzeitfähige Systeme mit automatischer Speicherbereinigung möglich, die beson- ders effizient implementiert werden können. So ist weder für den Speicherbereinigungsalgorithmus selbst noch für die erforderliche Synchronisation zwischen Prozessor und Speicherbereiniger Software erforderlich, die auf dem Prozessor ausgeführt werden muss. Der Pro- zessor muss lediglich einen Teil der Speicherbandbreite an den Speicherbereiniger abtreten.

Ein weiterer Vorteil der Architektur besteht darin, dass die Speicherbereinigung ohne die Koope- ration des Compilers und/oder des Laufzeitsystems auskommt und deshalb besonders robust implementiert werden kann.

Der Hardware-Aufwand für die Realisierung der Speicherbereinigung ist gemessen am Aufwand für den Prozessor selbst vergleichsweise gering. Aus diesem Grund können solche Prozessoren genauso wirtschaftlich wie herkömmliche Mikroprozessoren oder Mikrocontroller hergestellt werden.

Vorzugsweise wird bei der vorliegenden Prozessor- architektur durch den Prozessor gewährleistet, dass jedes als Zeiger identifizierte Wort entweder die Adresse eines existierenden Objekts beinhaltet oder Null ist. Bei dieser bevorzugten Ausgestaltung wird durch die Prozessorarchitektur somit die feste Regel (Systeminvariante) eingehalten, dass einerseits jedes Speicherwort oder Register dahingehend identifiziert werden kann, ob es ein Zeiger ist oder nicht, und andererseits jeder Zeigerwert entweder Null ist oder die Adresse eines existierenden Objekts enthält. Durch

das Einhalten dieser Systeminvariante wird die exakte Identifizierung der Zeiger im System zu jedem Taktzeit- punkt ermöglicht.

Vorzugsweise werden neue Objekte durch einen speziellen Objekterzeugungsbefehl angelegt, dem die Attribute des anzulegenden Objekts als Parameter übergeben werden. Dieser Objekterzeugungsbefehl initia- lisiert alle Zeiger des Zeigerbereichs mit dem Null- Wert, bevor auf das Objekt zugegriffen werden kann. Auf diese Weise wird die Systeminvariante nicht verletzt.

In einer Weiterbildung für harte Echtzeitanforde- rungen wird der Objekterzeugungsbefehl unterbrechbar implementiert, wobei beim Abbruch eines Objekterzeu- gungsbefehls unvollständig initialisierte Objekte derart erzeugt werden, dass der unterbrochene Objekter- zeugungsbefehl zu einem späteren Zeitpunkt fortgesetzt werden kann und dass unvollständig initialisierte Objekte vom Prozessor in eindeutiger Weise gekennzeich- net werden.

Vorzugsweise werden von der Prozessorarchitektur konstante Objekte unterstützt, die bereits vor dem Programmstart als Teil eines nur lesbaren Speicherbe- reiches existieren. Zeiger auf konstante Objekte werden vom Prozessor in eindeutiger Weise gekennzeichnet.

Vorzugsweise wird bei der vorliegenden Prozessor- architektur in bekannter Weise ein Bereich des Spei- chers für einen Programmstapel reserviert. Der Pro- grammstapel wird hierbei in einen Zeigerstapelbereich und einen Datenstapelbereich unterteilt, wobei jeweils die erste nicht vom Stapel belegte Position durch einen

Stapelindex angegeben wird, der in je einem reservier- ten Datenregister verwaltet wird.

Werden mehrere Stapel verwendet, so werden die Stapelindizes der momentan inaktiven Stapel vorzugs- weise als Attribute in den zugehörigen Stapelobjekten abgelegt. Weiterhin werden die Stapelobjekte als sog. statische Objekte vorzugsweise nicht im Heap, sondern in einem vom Betriebssystem verwalteten statischen Speicherbereich abgelegt und Zeiger auf derartige Objekte (statische Zeiger) in besonderer Weise gekenn- zeichnet.

Zur effizienten Implementierung der Prozessorar- chitektur wird jedes Zeigerregister vorzugsweise von einem Attributregister begleitet, in dem die Attribute des Objekts abgelegt werden, die zu dem mit dem Zeiger im Zeigerregister referenzierten Objekt gehören. Bei dieser Ausgestaltung ist eine zusätzliche Pipeline- Stufe zum Laden der Attribute vorgesehen. Weiterhin wird in dieser Pipeline-Stufe vorzugsweise ein Attri- but-Cache zur Beschleunigung der Zugriffe eingesetzt.

Alle weiteren für die Programmausführung erforder- lichen Pipeline-Stufen und Funktionseinheiten sowie die üblichen Optimierungen wie bspw. Instruktions-und Daten-Caches oder Einheiten zur Sprungvorhersage können bei einer Implementierung der vorliegenden Prozessorar- chitektur gemäß des Standes der Technik realisiert werden.

Kurze Beschreibung der Zeichnungen Die erfindungsgemäße Prozessorarchitektur wird nachfolgend anhand eines Ausführungsbeispiels in Ver-

bindung mit den Zeichnungen eingehend erläutert.

Hierbei zeigen : Fig. 1 schematisch das Registermodell der vorliegenden Prozessorarchitektur ; Fig. 2 schematisch das Objektmodell der vorliegenden Prozessorarchitektur ; Fig. 3 schematisch die Realisierung des Programmstapels als Stapelobjekt ; Fig. 4 eine Tabelle mit einer Klassifi- kation der zeigerbezogenen Befehle ; Fig. 5 ein Beispiel für die Realisierung des Objektlayouts für die vorlie- genden Prozessorarchitektur ; Fig. 6 schematisch ein Zeigerregister mit Attributen ; Fig. 7 ein Beispiel für die Realisierung einer Pipeline für die vorliegende Prozessorarchitektur (vereinfachte Darstellung) ; Fig. 8 die Zerlegung zeigerbezogener Be- fehle auf die Stufen einer Pipeline gemäß Figur 7 ; und Fig. 9 eine schematische Darstellung eines Beispiels der vorliegenden Vorrichtung.

Wege zur Ausführung der Erfindung Im Folgenden wird ein Beispiel für eine Ausgestal- tung der erfindungsgemäßen Prozessorarchitektur be-

schrieben, die vor allem auf der Zielsetzung basiert, eine exakte Zeigeridentifizierung ohne die Verwendung von Kennzeichnungsbits (tags) zu erreichen, einen allgemein verwendbaren RISC-Befehlsatz zu Grunde zu legen, der effizient implementiert werden kann, sowie keine unteilbaren Operationen vorauszusetzen, deren Ausführungszeit einige Taktzyklen übersteigt.

Die dargestellte Prozessorarchitektur garantiert die Systeminvariante, dass 1. jedes Speicherwort oder Register dahingehend identifiziert werden kann, ob es einen Zeiger dar- stellt oder nicht, und 2. jeder Zeigerwert entweder Null ist oder eindeu- tig einem existierenden Objekt zugeordnet ist.

Die vorliegende Prozessorarchitektur stellt ge- trennte Daten-und Zeigerregistersätze bereit, wie dies in Figur 1 schematisch verdeutlicht wird. Die im rech- ten Teil dargestellten Datenregister werden als Mehr- zweckregister eingesetzt, während die im linken Teil dargestellten Zeigerregister für den Zugriff auf Objek- te im Speicher genutzt werden. Np gibt hierbei die An- zahl der Zeigerregister, Nd die Anzahl der Datenregi- ster an. Um der Systeminvariante zu genügen, muss sichergestellt werden, dass es nicht möglich ist, beliebige Werte in Zeigerregister zu schreiben, wie bspw. den Wert eines Datenregisters in ein Zeigerre- gister zu kopieren oder arithmetische Operationen mit Zeigerregistern durchzuführen.

Das Speichermodell der vorliegenden Prozessor- architektur ist objektbasiert. Jedes Objekt setzt sich aus einem Datenbereich und einem Zeigerbereich zusam- men, die streng voneinander getrennt sind. Figur 2 zeigt den schematischen Aufbau eines derartigen Objekts mit den entsprechenden Zeigerworten im Zeigerbereich (linker Teil der Figur) und den Datenworten im Datenbereich (rechter Teil der Figur) des Objekts. Die Anzahl der Datenworte im Datenbereich wird mit dem 8- Attribut (8 2 0), die Anzahl der Zeiger im Zeigerbe- reich mit dem n-Attribut (vr z 0) beschrieben. Die durch die Attribute beschriebene Größe eines Objekts wird festgelegt, wenn das Objekt erzeugt wird und kann später nicht mehr geändert werden. Die Attribute sind Teil des Objekts und werden in diesem in einem geson- derten Attributbereich abgelegt.

Der für die vorliegende Prozessorarchitektur spezifische Teil des Befehlssatzes umfasst lediglich zeigerbezogene Befehle einschließlich Lade-und Spei- cherbefehle. Die Ausgestaltung anderer Befehle, wie bspw. arithmetischer Befehle oder von Befehlen zur Programmsteuerung kann unabhängig von der beschriebenen Architektur gewählt werden und ist nicht Teil der vor- liegenden Erfindung.

Der Befehlssatz der beschriebenen Architektur weist einen speziellen Objekterzeugungsbefehl auf, der zur Erzeugung eines neuen Objekts und eines Zeigers auf dieses Objekt dient. Der Objekterzeugungsbefehl (Allocate Object) erhält die Werte des s-und 8-Attri- buts für das zu erzeugende Objekt als Argumente und legt den Zeiger auf das neu erzeugte Objekt in einem

Zeigerregister ab. Jedes Zeigerwort im Zeigerbereich des erzeugten Objekts wird mit Null initialisiert, bevor der Zeiger auf das Objekt für das Programm sicht- bar wird. Es gibt keinen Befehl zum Löschen eines Objekts. Objekte können nur durch eine automatische Speicherbereinigung auf Prozessorebene gelöscht werden.

Lade-und Speicherbefehle werden für den Zugriff auf Worte innerhalb eines Objekts eingesetzt. Die Pro- zessorarchitektur stellt für den Zugriff auf Zeiger- worte und Datenworte unterschiedliche Lade-und Spei- cherbefehle zur Verfügung. Die"Lade Datum"-und "Speicher Datum"-Befehle bewegen Datenworte aus- schließlich zwischen Datenbereichen von Objekten und Datenregistern. Die"Lade Zeiger"-und"Speichere Zeiger"-Befehle bewegen Zeiger ausschließlich zwischen Zeigerbereichen von Objekten und Zeigerregistern. Die Lade-und Speicherbefehle identifizieren das Speicher- wort, auf das zugegriffen werden soll, mit Hilfe eines Zeigerregisters, das den Zeiger auf das Objekt enthält, und mit Hilfe eines ganzzahligen, positiven Index. Zur Berechnung der Indexwerte können-in Analogie zu den Adressierungsarten konventioneller Architekturen-ver- schiedene"Indizierungsarten"verwendet werden, die bspw. Datenregister, konstante Offsets und Skalierungs- faktoren verknüpfen.

Beim Zugriff auf ein Objekt müssen Bereichsüber- prüfungen durchgeführt werden, um sicherzustellen, dass keine Zugriffe auf Worte außerhalb des jeweils referen- zierten Objekts möglich sind. Solche Zugriffe können katastrophale Folgen nach sich ziehen und die Systemin- variante verletzen. Aus diesem Grund wird im Falle einer Bereichsüberschreitung der Speicherzugriff abge-

brochen und eine entsprechende Ausnahmebehandlung ein- geleitet. Aus ähnlichen Gründen werden Befehle abgebro- chen, die versuchen, einen Null-Zeiger zu dereferenzie- ren.

Die Attribute eines Objekts können durch zwei "Lese Attribute"-Befehle abgefragt werden.

Im Gegensatz zu der Vielzahl von"Register-zu- Register"-Befehlen, die in der Regel für Operationen auf Datenregister implementiert werden, wird durch die vorliegende Architektur ein stark beschränkter Satz von zwei Befehlen für zeigerbezogene"Register-zu- Register"-Befehle definiert. Der"Kopiere Zeiger"- Befehl kopiert den Inhalt eines Zeigerregisters in ein anderes Zeigerregister, während der"Vergleiche Zeiger"-Befehl überprüft, ob zwei Zeiger auf dasselbe Objekt verweisen.

Figur 4 zeigt eine Zusammenfassung der von der vorliegenden Prozessorarchitektur definierten zeiger- bezogenen Befehle und kategorisiert sie danach, ob sie Zeigerregister lesen, schreiben oder dereferenzieren.

Das Register, das jeweils gelesen, geschrieben oder dereferenziert wird, ist fett gedruckt.

Aufgrund der unstrukturierten und hochdynamischen Natur von Programmstapeln stellen diese eine der größten Herausforderungen hinsichtlich der Zeigeriden- tifizierung im Rahmen einer automatischen Speicherbe- reinigung dar. Bei der vorliegenden Prozessorarchitek- tur wird der Programmstapel als Stapelobjekt angesehen, das-wie jedes Objekt-einen Datenbereich und einen

Zeigerbereich aufweist und damit als zwei getrennte Stapel angesehen werden kann. Ein Zeigerregister wird reserviert, um den Zeiger auf das Stapelobjekt zu halten. In jedem der beiden Stapelbereiche wird ein Stapelindex eingesetzt, um den entsprechenden Bereich in den tatsächlichen Stapel und einen momentan unbeleg- ten Bereich einzuteilen. Der Stapelindex bezieht sich im vorliegenden Beispiel auf die erste unbelegte Spei- cherstelle. Ein Stapelindex von 0 repräsentiert einen leeren Stapel. Die beiden Stapelindizes werden als Datenstapelindex (dsix) und Zeigerstapelindex (psix) bezeichnet. Jeder dieser Indizes wird in einem speziell dafür reservierten Datenregister gehalten.

Wenn das Stapelobjekt wie ein gewöhnliches Objekt behandelt wird, so kann das System nicht unterscheiden, ob ein Zeiger zum aktuell belegten Zeigerstapel oder zum unbelegten Teil des Zeigerstapelbereiches gehört.

Da jedes Wort im Zeigerstapelbereich als Zeiger identi- fiziert wird, kann der ungenutzte Bereich des Zeiger- stapelbereichs viele Zeiger enthalten, die auf nicht mehr benötigte Objekte zeigen. Ein Speicherbereiniger (garbage collector) könnte diese Objekte nicht frei geben, da noch Zeiger auf diese Objekte vorhanden sind.

Eine mögliche Lösung dieses Problems besteht darin, je- den Zeigerwert mit Null zu überschreiben, sobald der entsprechende Zeiger vom Stapel entfernt wird. Dies führt jedoch zu einem unerwünschten Overhead, insbeson- dere dann, wenn mehrere Zeiger vom Stapel entfernt werden sollen, wie das bspw. beim Abbau eines Stapel- rahmens am Ende eines Unterprogramms der Fall ist.

Für das hier beschriebene Beispiel einer vorteil- haften Ausgestaltung der Prozessorarchitektur wird daher eine Lösung gewählt, die die dynamische Größe

eines Stapels berücksichtigt. Hierbei wird das Stapel- objekt, wie in Figur 3 veranschaulicht, durch zwei Attributpaare beschrieben, von denen ein Paar (n, die aktuelle Stapelgröße und ein zweites Paar (H, A) die maximale Stapelgröße angibt. Das s-Attribut ent- spricht dabei dem Wert des Zeigerstapelindex psix, das 8-Attribut dem Wert des Datenstapelindex dsix. Die Stapelattribute n und A werden in Systemregistern gehalten, die für Anwenderprogramme nicht sichtbar sind. Hinsichtlich der Zeigeridentifizierung und der Systeminvariante werden lediglich Zeiger mit Indizes kleiner als z als Zeiger angesehen.

Speicherworte innerhalb des Stapels werden durch gewöhnliche Lade-und Speicherbefehle angesprochen.

Worte können vom Stapel entfernt werden, indem der Wert des entsprechenden Stapelindex mittels gewöhnlicher arithmetischer Befehle verringert wird. Zur Einhaltung der Systeminvariante wird zur Ablage eines Zeigers auf dem Zeigerstapel ein spezieller Befehl bereitgestellt, der in nicht unterbrechbarer Weise zuerst den Zeiger an der ersten unbelegten Speicherstelle des Zeigerstapel- bereiches ablegt und den Zeigerstapelindex erhöht. Dies ist gleichzeitig der einzige Befehl, mit dem der Zeigerstapelindex erhöht werden kann.

Bei der bisher beschriebenen Prozessorarchitektur kann ausschließlich über Zeiger auf den Speicher zuge- griffen werden, und die einzige Möglichkeit zur Erzeu- gung von Zeigern besteht im Anlegen neuer Objekte mit Hilfe des Objekterzeugungsbefehls. Es sollte jedoch auch möglich sein, auf konstante Daten zuzugreifen, die bspw. als Teil des Programmcodes bereits vor dem Start des Programmes existieren. Beispiele für solche kon-

stanten Daten sind konstante Zeichenketten oder vom Compiler generierte Strukturen wie bspw. Verzweigungs- tabellen oder Typbeschreibungen.

Das vorliegenden Beispiel einer vorteilhaften Ausgestaltung der Prozessorarchitektur führt daher konstante Objekte ein. Ein konstantes Objekt ist hierbei ein unveränderbares Objekt, das als Teil des Programmcodes oder in einem speziellen Bereich abge- speichert wird, der für konstante Objekte reserviert ist. Für die Erzeugung von Zeigern auf konstante Objekte, nachfolgend als konstante Zeiger bezeichnet, wird ein spezieller"Erzeuge konstanten Zeiger"-Befehl verwendet. Speicherzugriffe über konstante Zeiger sind auf Lesezugriffe beschränkt, und der Zeigerbereich eines konstanten Objekts darf ausschließlich konstante Zeiger oder Null-Zeiger enthalten. Konstante Objekte werden von gewöhnlichen Objekten durch ein p-Attribut unterschieden, das zur Unterscheidung spezieller Arten von Objekten bereitgestellt wird.

In vielen Systemen werden getrennte Programmstapel für unterschiedliche Betriebsarten wie bspw. Anwender- modus und Betriebssystemmodus verwendet. Darüber hinaus erfordern Systeme mit mehreren nebenläufigen Ausfüh- rungsfäden (multi-threaded systems) separate Programm- stapel für jeden Ausführungsfaden. Alle diese Stapel werden üblicherweise vom Betriebssystem verwaltet und befinden sich nicht in dem von der automatischen Spei- cherbereinigung überwachten Speicherbereich (Heap).

Um es dem Betriebssystem zu ermöglichen, Speicher- bereiche außerhalb des Heap-Speicherbereiches zu ver- walten, werden statische Objekte bereitgestellt. Stati- sche Objekte werden ausschließlich im Betriebssystem-

modus erzeugt und in einem speziell dafür vorgesehenen Speicherbereich angeordnet. Statische Objekte werden ebenfalls über das-Attribut identifiziert. Zeiger auf statische Objekte (statische Zeiger) sind für Anwender- programme niemals sichtbar.

Zur Einhaltung der Systeminvariante muss jeder Zeiger in einem neu erzeugten Objekt mit dem Null-Wert initialisiert werden, bevor der zugehörige Objekterzeu- gungsbefehl abgeschlossen werden kann. Deshalb ist die Ausführungszeit für den Objekterzeugungsbefehl nicht durch eine kleine Zeitkonstante begrenzt. Dies ist für harte Echtzeitanwendungen nicht akzeptabel.

Um den Objekterzeugungsbefehl unterbrechbar zu gestalten, werden in der beschriebenen vorteilhaften Ausgestaltung der Prozessorarchitektur uninitialisierte (genauer : unvollständig initialisierte) Objekte einge- führt. Uninitialisierte Objekte werden dann und nur dann erzeugt, wenn der Zuweisungsbefehl vor der Fertig- stellung eines Objekts unterbrochen wird. Zeiger auf uninitialisierte Objekte sind nur im Betriebssystem- modus sichtbar und dürfen niemals dereferenziert werden. Uninitialisierte Objekte werden-wie statische und konstante Objekte-durch das p-Attribut identifi- ziert.

Die beispielhaft beschriebene vorteilhafte Ausge- staltung der Prozessorarchitektur unterstützt folglich vier unterschiedliche Arten von Objekten : normale dyna- mische Objekte, uninitialisierte dynamische Objekte, konstante Objekte und statische Objekte. Das-Attribut wird zur Unterscheidung der Objektarten eingesetzt und kann einen der vier Werte (norm, uini, const, stat) an-

nehmen. In einer Implementierung der Architektur kann das p-Attribut im Zeiger auf ein Objekt und/oder im Objekt selbst abgelegt werden.

Normale dynamische Objekte und uninitialisierte dynamische Objekte befinden sich im Heap-Speicherbe- reich, statische Objekte im statischen Speicherbereich und konstante Objekte in dem für den Programmcode und/oder konstante Daten vorgesehenen Speicherbereich.

Da statische und uninitialisierte Objekte auf den Betriebssystemmodus beschränkt sind, werden sie als Systemobjekte bezeichnet.

Unter dem Gesichtspunkt der automatischen Speicherbereinigung können die vier Objektarten dadurch charakterisiert werden, wie sie von einem kompaktieren- den Speicherbereiniger behandelt werden. Gewöhnliche dynamische Objekte müssen nach Zeigern durchsucht und bei einer Kompaktierung verschoben werden. Statische Objekte müssen zwar nach Zeigern durchsucht, dürfen aber nicht verschoben werden. Uninitialisierte Objekte dagegen müssen während der Kompaktierung verschoben werden, dürfen aber nicht nach Zeigern durchsucht werden, da sie ungültige Zeiger enthalten können.

Schließlich müssen konstante Objekte vom Speicherberei- niger weder nach Zeigern durchsucht noch verschoben werden.

Eine mögliche Implementierung der vorgeschlagenen Prozessorarchitektur wird im Folgenden beispielhaft erläutert. Für die Implementierung wird eine Wortgröße von 32 Bit angenommen. Der Speicher ist byteweise adressierbar, um innerhalb des Datenbereiches auch Byte-und Halbwortzugriffe zu ermöglichen. Worte müssen an durch vier teilbaren Adressen ausgerichtet werden.

Ein beispielhaftes Layout eines Objekts im Speicher ist in der Figur 5 dargestellt. Jedes Objekt besteht aus einem Datenbereich, einem Zeigerbereich und einem Attributbereich. Aus Effizienzgründen sind die Objekte an durch acht teilbaren Adressen ausgerichtet, wodurch unter Umständen ein Füll-Bereich zwischen zwei Objekten erforderlich werden kann. Der Attributbereich, der für Nutzerprogramme unsichtbar ist, beinhaltet die n und 8-Attribute des Objekts. Aufgrund der Unter- stützung von Byte-und Halbwortoperanden ändert die vorliegende Implementierung die. Definition von s und 8 leicht, da sie nun die Anzahl von Bytes anstelle der Anzahl der Worte in dem entsprechenden Bereich be- schreiben.

Da z ein Vielfaches von vier sein muss, bleiben im Speicherwort, das für das s-Attribut verwendet wird, zwei Bits unbelegt. Diese können zur Ablage des- Attributs (oder Teilen davon) und/oder von einem Speicherbereiniger verwendet werden.

Die Zeiger enthalten direkt die physikalische Speicheradresse des Objekts. Da die Objekte nach Doppelworten ausgerichtet sind, belegt die Objekt- adresse lediglich 29 Bits eines Zeigerwortes. Die verbleibenden drei Bits können zur Ablage des p- Attributs (oder Teilen davon) und/oder von einem Speicherbereiniger verwendet werden.

Vor dem Zugriff auf ein Objekt müssen die Attri- bute des Objekts bekannt sein, da diese für die Bereichsüberprüfung vor dem Zugriff benötigt werden, und, im Falle eines Objektlayouts gemäß Figur 5, im

Falle eines Datenzugriffs zusätzlich für die Adresser- zeugung erforderlich sind.

Da das Laden der Attribute aus dem Speicher vor jedem Objektzugriff mit einem großen Overhead verbunden ist, wird jedem Zeigerregister ein Attributregister beigestellt, wie dies in der Figur 6 schematisch darge- stellt ist. Wenn ein Zeigerregister einen Wert enthält, der nicht Null ist, beinhaltet das korrespondierende Attributregister die Attribute des Objekts, auf das das Zeigerregister verweist. Auf diese Weise wird der Aufwand für die Dereferenzierung eines Zeigerregisters so gering wie der Aufwand für die Adresserzeugung in konventionellen Architekturen. Die Bereichsüberprüfung selbst ist mit keinen Leistungseinbußen verbunden, da sie parallel zur Adressberechnung durchgeführt werden kann.

Die Attributregister haben jedoch ihren Preis : Wenn ein Zeiger aus dem Speicher geladen wird, müssen auch die zugehörigen Attribute in die Attributregister geladen werden. Hinzu kommt, dass der Ort der Attribute im Speicher erst bekannt ist, wenn das Laden des Zeigers abgeschlossen ist.

Dieses Problem kann im Falle einer RISC-Architek- tur effizient durch eine zusätzliche Pipelinestufe nach der üblichen Speicherstufe gelöst werden. Diese zusätz- liche Stufe wird als Attributstufe bezeichnet und ver- wendet einen Attribut-Cache, um Attributzugriffe in den meisten Fällen ohne Leistungseinbußen auszuführen. Der Aufbau des Attribut-Cache ist dem eines gewöhnlichen Daten-Caches ähnlich. Der Attribut-Cache wird durch die oberen 29 Bits eines Zeigers adressiert und ermöglicht das Lesen oder Schreiben der s und 5-Attribute in einem

einzigen Schritt. Der wesentliche Unterschied zu einem Daten-Cache besteht in der Größe der Cache-Zeilen.

Während Cache-Zeilen in Daten-Caches üblicherweise 8 Worte umfassen, weist eine Zeile des Attribut-Cache eine Breite von 2 Worten auf und enthält lediglich die Attribute eines einzelnen Objekts.

Figur 7 zeigt die Grundstruktur der implemen- tierten Pipeline und Figur 8 die Zerlegung aller zeigerbezogenen Befehle auf die einzelnen Pipeline- Stufen. Zur Veranschaulichung wird die Abarbeitung der beiden aufwändigsten Befehle beispielhaft beschrieben.

1."Lade Zeiger"-Befehl : In der Ausführungsstufe der Pipeline berechnet die Adresserzeugungseinheit (AGU : Address Generation Unit) die Speicheradresse des zu ladenden Zeigers und führt parallel dazu die von der Architektur vorgeschriebenen Laufzeittests wie bspw. Bereichsüberprüfungen und Null- zeigertests durch. In der Speicherstufe wird die be- rechnete Adresse benutzt, um den Zeiger aus dem Objekt- Cache zu lesen. Der geladene Zeiger adressiert dann den Attribut-Cache, um die Attribute aus dem Objekt zu laden, auf das der geladene Zeiger zeigt. Schließlich wird der geladene Zeiger zusammen mit den geladenen Attributen in den Registersatz geschrieben.

2. Objekterzeugungsbefehl : Die Größe des zu erzeugenden Objekts wird mit Hilfe zweier Datenoperanden bestimmt, die aus der Dekodier- stufe in die Ausführungsstufe weitergereicht werden. In der Ausführungsstufe ist die Zeigererzeugungseinheit (PGU : Pointer Generation Unit) für die Erzeugung des

Zeigers auf das neue Objekt zuständig. Im Falle eines kompaktierenden Speicherbereinigers kann die PGU die Startadresse des neuen Objekts sehr einfach dadurch bestimmen, dass die Objektgröße zum Inhalt eines Systemregisters addiert wird, das stets auf das letzte belegte Wort in dem Bereich des Heaps zeigt, der für das Anlegen neuer Objekte verwendet wird. Die PGU wird durch die AGU unterstützt, die die für die Zeigerini- tialisierung erforderlichen Adressen erzeugt. Bei einem Objekt-Cache mit Cache-Zeilen von 8 Worten können in einem Taktzyklus bis zu 8 Zeigerworte gleichzeitig initialisiert werden. Auf diese Weise durchläuft der Erzeugungsbefehl die Ausführungsstufe ohne Verzögerung, wenn die Startadresse des Objekts innerhalb eines Takt- zyklus berechnet werden kann und wenn alle Zeiger im Objekt der gleichen Cache-Zeile angehören. Falls dies nicht der Fall ist, wird die Pipeline angehalten, bis die Initialisierung abgeschlossen ist oder eine Unter- brechung auftritt. Schließlich werden die Attribute des neu generierten Objekts in den Attribut-Cache und der Zeiger zusammen mit seinen Attributen in den Register- satz geschrieben. Falls ein unterbrochener Objekterzeu- gungsbefehl am Ende der Pipeline ankommt, wird der Zu- stand der unterbrochenen Objekterzeugung in ein System- register geschrieben und das unvollständig initiali- sierte Objekt mit dem p-Attribut für uninitialisierte Objekte gekennzeichnet. Die Initialisierung wird wieder aufgenommen, sobald der Ausführungskontext (Befehls- folgezähler, Systemregister) des unterbrochenen Pro- gramms wieder hergestellt ist.

Die Funktionsfähigkeit der vorgeschlagenen Archi- tektur wurde anhand eines funktionierenden Prototypen

nachgewiesen. In diesem Prototypen ist der Speicherbe- reiniger als mikroprogrammierter Koprozessor reali- siert, der eng mit der Pipeline des Hauptprozessors zusammenarbeitet. Die Synchronisation zwischen Pro- zessor und Koprozessor ist komplett in Hardware reali- siert. Der Prozessor und der Koprozessor für die Speicherbereinigung sind in VHDL beschrieben und gemeinsam für einem modernen programmierbareren Logikbausteins synthetisiert. Es existieren weiterhin ein prototypischer Java-Compiler sowie die Implementie- rung einer Untermenge der Java-Klassenbibliotheken für die Architektur.

Figur 9 zeigt eine schematische Darstellung eines Beispiels der vorliegenden Vorrichtung. Der Speicher- bereiniger wird in diesem Beispiel durch einen mikroprogrammierbaren Coprozessor 2 gebildet. In den Hauptprozessor 1 ist die erfindungsgemäße Prozessor- architektur implementiert. Ein Speicher-Controller 3 mit jeweils mehreren getrennten Ports für den Haupt- prozessor 1 und den Coprozessor 2 stellt die Verbindung zum Hauptspeicher her. Die Synchronisation zwischen Haupt-und Coprozessor findet auf unterschiedlichen Ebenen statt. Der Speicherbereiniger verriegelt oder räumt Zeilen des Daten-und Attribut-Caches, wenn nötig, um die Cache-Kohärenz zu gewährleisten. Eine in die Prozessor-Pipeline integrierte Hardware-Lese- barriere kann Interrupts im Speicherbereiniger triggern. Der Speicherbereiniger kann den Haupt- prozessor 1 auch stoppen, um kritische Bereiche im Mikrocode zu schützen.