Um was es geht
Im Internet werden eine ganze Reihe von Projekten durchgeführt, in denen die
Rechenkapazität vieler Computer gebündelt wird um ein aufwändiges Problem zu
bearbeiten. Das bekannteste Projekt ist wahrscheinlich SETI, bei dem Computer auf der
ganzen Welt Daten des Radioteleskops Arecibo nach Signalen durchsuchen, die von
extraterrestrischen Intelligenzen stammen könnten. In einem anderen Projekt beteiligen
sich zahllose Internet-Nutzer an der Jagd auf große Primzahlen. Gemeinsam an all diesen
Projekten ist, dass ein zentraler Rechner - der Server - die Bemühungen vieler Teilnehmer
- der Clients - koordiniert. Er verteilt Aufträge und sammelt die Ergebnisse ein.
Wir haben versucht ein derartiges Projekt im Klassenraum nachzubilden. Zugegebenermaßen hatten wir weder die Kenntnisse noch die Zeit ein wirklich ungelöstes wissenschaftliches Problem anzupacken. Uns ging es in erster Linie darum zu lernen, wie man ein derartiges Projekt programmtechnisch lösen kann. Das Ziel unserer gemeinsamen Bemühungen war, eine möglichst lange Collatzfolge mit einer möglichst kleinen Startzahl zu finden. Das Collatzproblem ist nicht weltbewegend und sicher nicht jedem bekannt. Deshalb soll es zunächst vorgestellt werden.
Das Collatzproblem
Das Problem sieht wie ein Rechenspiel für Grundschüler aus. Man wählt eine natürliche
Zahl x und bildet daraus nach folgenden Regeln eine Reihe: Ist x gerade, so wird es
halbiert: die nächste Zahl der Reihe ist dann x/2. Ist x aber ungerade, so wird zum
dreifachen von x der Wert 1 addiert: die nächste Zahl der Reihe ist dann 3x+1. Jetzt
wendet man auf die neue Zahl dieselbe Regel an und macht das so lange bis man den Wert 1
erreicht hat. Die Anzahl der Reihenglieder bis zur abschließenden 1 heißt
"delay" der Startzahl x b.z.w. ihrer Collatzreihe.
Beispiel:
Für die Startzahl x = 3 ergibt sich die Reihe: 10, 5, 16, 8, 4, 2, 1. Bis zur 1 muss man
die Collatz-Vorschrift also 7 mal anwenden:
delay(3)=7.
Der mathematische Reiz dieses Zahlenspiels besteht darin, dass man nicht vorhersagen kann, welche Werte besonders lange Reihen produzieren. Man weiß auch nicht, ob es Zahlen gibt, deren Collatzreihen unendlich lang sind. Man hat noch keine gefunden und vermutlich gibt es auch keine. Damit es keine Missverständnisse gibt: Natürlich ist es klar, dass 21000 eine Reihe mit dem Delay 1000 produziert. Aber es gibt viel kleinere Zahlen als 21000, die längere Reihen produzieren. Und niemand weiß gegenwärtig, welche Zahl unterhalb 21000 die längste Reihe produziert. (Der Rekord aus dem Jahr 2002: Die Zahl 17026,512240,355369 hat einen Delay von 2042.)
Unser Projekt
Bei einem Unterrichtsprojekt kann man kaum erwarten, wirklich neue Rekordfolgen zu
finden. Unser Ziel war es vielmehr, möglichst lange Folgen ohne fremde Hilfe (d.h. ohne
Rückgriff auf Ergebnisse anderer) zu finden. Dazu haben wir uns auch keine raffinierten
Techniken überlegt, die es wahrscheinlich gibt. Wir haben letztlich in einem vorgegebenen
Intervall eine Folge nach der anderen aufgestellt und uns die Startzahl der längsten
Folge gemerkt. Wenn man die Suche nur mit einem einzelnen Computer durchführt, benötigt
man lediglich ein ganz einfaches Programm:
public class collatz{
public static void main(String[] args){
int ugrenze = (new Integer(args[0])).intValue();
int ogrenze = (new Integer(args[1])).intValue();
int maxlaenge=0;
int imax=0;
for(int i=ugrenze;i<=ogrenze;i++){
int alaenge=lcoll(i);
if(alaenge>maxlaenge){
maxlaenge=alaenge;
imax=i;
}
}
System.out.println("Länge "+maxlaenge+" für i = "+imax);
}
static int lcoll(int z){
int wert=0;
while(z!=1){
if(z%2==0) z=z/2;
else z=3*z+1;
wert++;
}
return wert;
}
}
Beim Programmstart werden die Grenzen des zu
durchsuchenden Bereichs als Argumente eingegeben. Das Programm durchläuft dass innerhalb
dieser Grenzen eine Schleife, in der jeweils die Methode lcoll(i) aufgerufen wird. Diese
bildet die Collatzreihe für die in ihrem Argument stehende Zahl i und gibt die Länge der
Reihe zurück. Zum Schluss wird der Startwert und der delay der längsten gefundenen Reihe
ausgegeben. Werden z.B. als Intervallgrenzen die Werte 1 und 1000 eingegeben, so gibt das
Programm das Ergebnis aus:
Länge 178 für i = 871
Gemeinsam rechnen mit CORBA
Um in einer vorgegebenen Zeit einen möglichst großen Bereich nach langen Collatzreihen
durchsuchen zu können, haben wir das "Suchprogramm" in einen Server- und einen
Client-Anteil aufgeteilt. Der Server organisiert dabei nur die Arbeit der Clients.
Wenn sich ein Client-Computer an ihn wendet, teilt er ihm einen Bereich zu, in dem dieser
nach langen Collatzreihen suchen soll. Dem nächsten Client teilt er einen anderen Bereich
zu u.s.w. Wenn ein Client den zugeteilten Bereich durchsucht hat, teilt er dem Server die
Länge und die Anfangszahl der längsten von ihm gefundenen Reihe mit. Der Server
vergleicht diesen Wert mit den anderen Ergebnissen, die er bisher erhalten hat und
bestimmt so den gemeinsamen Rekord aller Clients.
Die direkte Kommunikation zwischen den Clients und dem Server läuft über drei Methoden ab, die der Server bereitstellt und die vom Client aufgerufen werden können:
1. Die void-Methode zuteilung. Diese Methode ruft der Client zu Beginn der
Kommunikation mit dem Server auf. Über die Argumente von zuteilung erhält der Client vom
Server die Grenzen des zu durchsuchenden Zahlenbereichs.
2. Die void-Methode antwort. Über die Argumente dieser Methode teilt der Client dem
Server Anfangswert und Länge der längsten Collatzfolge im durchsuchten Zahlenbereich
mit.
3. Die boolean-Methode record. Der Client ruft diese Methode direkt nach antwort auf. Hat er einen neuen Rekord gemeldet, erhält er dafür die Bestätigung. Er kann mit dieser Methode aber auch sonst abfragen, was Anfangszahl und Länge der momentanen Rekordreihe sind.
Die drei Kommunikations-Methoden müssen zunächst in einer IDL Datei "corbcol.idl" deklariert werden.
module corbcol
{
interface collserv
{
void zuteilung( out long ug,out long og);
void antwort(in long imax,in long lmax);
boolean record(out long irec, out long lrec);
};
};
Die IDL-Datei definiert (wie die Bezeichnung IDL angibt) das Interface für die Client-
Server Verbindung. Deswegen sind dort auch nur die Kopfzeilen der Methoden angegeben und
nicht ihr Programm-Code. Der steht in der Servant-Klasse des Server-Programms. Die
IDL-Syntax weicht von der Java-Snytax ab. Das IDL "long" entspricht einem Java
"int" (IDL long long entspricht dem Java long). Die Zusätze "out" und
"in" bei den Argumenten geben an, ob beim Methodenaufruf die Argumente Werte vom
Server zum Client liefern (out) oder vom Client zum Server (in). in-Argumente sind
normale Werteparameter, während out-Argumente Referenzparameter sind, die in Java nicht
vorgesehen sind.
Um einen Referenzparameter zu imitieren, muss ein "out long" Argument durch ein
Objekt der Klasse IntHolder ersetzt werden. Das Feld value dieses Objekts kann dann vom
Clientprogramm wie ein Referenzparameter gelesen werden. Damit Client- und Server-Programm
des CORBA-Projekts auf die in der IDL-Datei festgelegten Eigenschaften der
Kommunikations-Methoden zugreifen können, muss die IDL-Datei in eine Reihe von
Java-Hilfsklassen verwandelt werden. Dazu ruft man mit einem Konsolenbefehl den im JDK
enthaltenen Compiler idlj auf.
(Hinweis: Die Datei corbcol.idl befindet sich im Ordner corbacoll ). Die Option -fall
bewirkt, dass idlj sowohl die Hilfsdateien für den Client als auch für den Server
erzeugt.
Für diese Hilfsdateien, in deren Namen der Interface-Bezeichner
"collserv" steht, erzeugt idlj einen Unterordner "corbcol" im
aktuellen Ordner. Nach der Erzeugung der Hilfsdateien können Client- und Server-Programm
des Projekts erstellt werden.
Das Serverprogramm.
import corbcol.*; import org.omg.CosNaming.*; import org.omg.CosNaming.NamingContextPackage.*; import org.omg.CORBA.*; import org.omg.PortableServer.*; import org.omg.PortableServer.POA;
class meinServant extends collservPOA {
int intlang=100000;
int irec=0, lrec=0;
int ugs=2,ogs=intlang;
boolean neurec=true;
public void zuteilung(IntHolder ug, IntHolder og){
ug.value=ugs;
og.value=ogs;
ugs=ogs+1;
ogs=ogs+intlang;
}
public void antwort(int imax, int lmax){
neurec=false;
if(lmax>lrec){
irec=imax;
lrec=lmax;
neurec=true;
}
}
public boolean record(IntHolder h_irec, IntHolder h_lrec){
h_irec.value=irec;
h_lrec.value=lrec;
return neurec;
}
}
public class collserver {
public static void main(String args[]) {
try{
// ORB erzeugen und initialisieren
ORB orb = ORB.init(args, null);
// POAManager aktivieren
POA rootpoa = POAHelper.narrow(orb.resolve_initial_references("RootPOA"));
rootpoa.the_POAManager().activate();
// Servantklasse beim ORB registrieren
meinServant collservRef = new meinServant();//Bezeichner des Interfaces
org.omg.CORBA.Object ref = rootpoa.servant_to_reference(collservRef);//Bezeichner des Interfaces
collserv href = collservHelper.narrow(ref);//Bezeichner des Interfaces
// Namens-Service erzeugen
org.omg.CORBA.Object objRef = orb.resolve_initial_references("NameService");
NamingContextExt ncRef = NamingContextExtHelper.narrow(objRef);
// Object Referenz an den IDL-Namen binden
NameComponent path[] = ncRef.to_name( "collserv" );//Bezeichner des Interfaces
ncRef.rebind(path, href);
//Ein Lebenszeichen geben
System.out.println("POAServer ist aktiv");
// auf Anfragen der Clients warten.
orb.run();
}
catch (Exception e) {
System.err.println("ERROR: " + e);
e.printStackTrace(System.out);
}
}
}
Für das Serverprogramm müssen zunächst die aus der IDL-Datei erzeugten Hilfsklassen (in corbcol) und eine Reihe von CORBA-Paketen importiert werden. Das Programm besteht aus zwei Klassen: der Servant-Klasse und der Makler-Klasse. Die Servantklasse muss von der Hilfsklasse collservPOA abgeleitet werden und stellt die Methoden zur Verfügung, die vom Client angefordert werden. Ihr Zweck wurde weiter oben schon erläutert. "zuteilung" übermittelt dem Client die Grenzen des zu untersuchenden Zahlenbereichs. "antwort" nimmt die vom Client bestimmten Werte für die längste Collatz-Reihe entgegen, vergleicht sie mit den momentanen Rekordwerten und aktualisiert diese ggf. "record" gibt die momentanen Rekord-Werte aus. Für die korrekte Buchhaltung werden noch einige Klassenvariablen verwendet.
Die Makler-Klasse besteht nur aus der main-Methode. Dort wird der Makler "orb" ( = object request broker) initialisiert, die vereinbarten Namen werden den zu makelnden Objekten zugewiesen und dann wird der "orb" gestartet und wartet auf Anforderungen der Clients. Im oben gezeigten Quellcode sind diejenigen Zeilen markiert, in denen der Name des Interfaces angegeben werden muss.
Damit der Servers korrekt arbeitet, muss sich
beim Kompilieren der Ordner mit den Hilfsdateien im classpath befinden:
Weiterhin muss vor dem Start des Servers der Namensserver tnameserv gestartet werden, der
sich ebenfalls im bin-Ordner des JDK befindet
Der hier gezeigte collserver hat keine Benutzerschnittstelle. Nach seinem Start meldet er lediglich: POAServer ist aktiv
Das Clientprogramm
import corbcol.*;//CORBA - Bezeichner des Moduls import org.omg.CosNaming.*;//CORBA import org.omg.CORBA.*;//CORBA import java.awt.*; import java.awt.event.*;
public class cocorcli extends Frame{
static collserv remote;//CORBA - Bezeichner des Interfaces
Button bthallo,btrec;
TextArea ta;
static int hoehe=300,breite=400;
public cocorcli(){
this.addWindowListener (new WindowAdapter(){
public void windowClosing(WindowEvent e){
dispose();
System.exit(0);
}
});
setSize(breite,hoehe);
setLayout(new FlowLayout());
add(bthallo=new Button("Server rufen"));
add(btrec=new Button("Rekord ausgeben"));
bthallo.addActionListener(new halloListener());
btrec.addActionListener(new halloListener());
add(ta=new TextArea(10,50));
ta.setText("");
ta.setEditable(false);
}
public class halloListener implements ActionListener{
public void actionPerformed(ActionEvent e){
Button werwars=(Button) e.getSource();
if(werwars==bthallo){
IntHolder ugh=new IntHolder();
IntHolder ogh=new IntHolder();
remote.zuteilung(ugh,ogh);//Remote Aufruf
bthallo.setEnabled(false);
int ug=ugh.value;
int og=ogh.value;
int maxlaenge=0;
int imax=0;
for(int i=ug;i<=og;i++){
int alaenge=lcoll(i);
if(alaenge>maxlaenge){
maxlaenge=alaenge;
imax=i;
}
}
remote.antwort(imax,maxlaenge);
IntHolder irech=new IntHolder();
IntHolder lrech=new IntHolder();
if (remote.record(irech,lrech))//Remote Aufruf
ta.append("Startzahl: "+irech.value+" delay: "+lrech.value+"\n");
bthallo.setEnabled(true);
}
if(werwars==btrec){
IntHolder irech=new IntHolder();
IntHolder lrech=new IntHolder();
remote.record(irech,lrech);//Remote-Aufruf
ta.append("Momentaner Rekord: "+irech.value+"/"+lrech.value+"\n");
}
}
}
static void makler(String args[]){
try{
// Broker erzeugen
ORB orb = ORB.init(args, null);
// Namesauflösung der Objektanforderng vorbereiten
org.omg.CORBA.Object objRef = orb.resolve_initial_references("NameService");
NamingContext ncRef = NamingContextHelper.narrow(objRef);
// Namensauflösung für die angeforderten Objekte
NameComponent nc = new NameComponent("collserv", "");//Bezeichner des Interfaces
NameComponent path[] = {nc};
remote = collservHelper.narrow(ncRef.resolve(path));//Bezeichner des Interfaces
}
catch (Exception e) {
System.out.println("Fehler : " + e) ;
e.printStackTrace(System.out);
}
}
public static void main(String args[]){
makler(args);//CORBA
cocorcli f = new cocorcli();
f.setVisible(true);
}
int lcoll(int zz){
long z=zz;
int wert=0;
while(z!=1){
if(z%2==0) z=z/2;
else z=3*z+1;
wert++;
}
return wert;
}
}
Beim Start muss als
Argument von main die Serveradresse angegeben werden:
(so sieht das in der RealJ-Programmierumgebung aus, sonst ist das eine Konsolen-Eingabe).
Diese Information kann man weglassen, wenn sich der Server
auf dem localhost befindet. Die main-Methode ruft als erstes die Methode makler
auf. Diese initialisiert wie beim Server einen "orb", der die Verbindung
zu dem vom Server herstellt und das Objekt "remote" erzeugt, das die
in der Servant-Klasse des Servers implementierten Methoden enthält. Dann wird
durch den Aufruf des Fensterkonstruktors "cocorcli" eine einfache
graphische Benutzeroberfläche erzeugt.
Die Rechenaktivitäten und die Remote-Aufrufe stecken in der (inneren) Listener-Klasse. Beim Anklicken des Buttons "Server rufen" (Verzweigung werwars==bthallo) wird die Servermethode "zuteilung" aufgerufen. Der Server schickt dann die Grenzen des zu untersuchenden Bereichs. Man beachte die Handhabung der IntHolder-Argumente. Dann macht das Client-Programm dasselbe wie das kurze lokale Programm, das im einleitenden Abschnitt beschrieben ist. Während der Rechenzeit des Clients ist der Button "Server rufen" deaktiviert, so dass kein neuer Bereich angefordert werden kann, solange der alte noch nicht durchsucht ist. Die Antworten des Servers werden in einer TextArea ausgegeben:
Eine Ausgabe erfolgt allerdings nur, wenn im zugewiesenen Bereich eine Reihe mit Rekordlänge entdeckt wurde oder wenn durch Klick auf den Button "Rekord ausgegeben" die Daten der Rekordreihe ausdrücklich angefordert wurden.
Bemerkungen zu Schluss
Es ist klar, dass das obige Programm noch an vielen Stellen verbessert werden
kann . Unser Ziel war es aber, mit CORBA funktionsfähige Programme zu erstellen,
mit denen mehrere Computer gemeinsam eine Aufgabe bearbeiten. Auf den ersten Blick
sieht CORBA schwierig und abschreckend aus. Aber die CORBA-Funktionalität
steckt fast völlig in den Makler-Methoden des Client- und das Servers-Programms.
Und die lassen sich leicht an unterschiedliche Problemstellungen anpassen: Man
muss eigentlich nur an den entsprechenden Stellen (die im oben angegebenen
Quellcode durch Kommentare bezeichnet sind) den Namen des jeweiligen
IDL-Interfaces angeben.