Programmierungstechnik
Der Speicher (C++)
Fließkommazahlen (C++)
Multi-Prozessor-Programme (C++)
Threads - Nebenläufigkeit und Synchronisation (C++)
Character Encoding
Der Speicher (C++)
Suche nach Speicherlöchern
Entweder es wird Speicher nicht freigegeben und der Server wächst oder es wird versucht auf
freigegebenen Speicher zuzugreifen oder nochmal freizugeben.
In der zweiten Varianten kann der delete Operator überladen werden. Dann wird im Deleteoperator
der this-Zeiger auf Null gesetzt und ein zusätzlicher Zeiger bleibt auf der alten
Speicheradresse. Wenn der Deleteoperator betreten wird und der this-Zeiger schon auf Null steht
wird abgebrochen und ein Stacktrace ausgegeben, mit der Funktion, die diesen zweiten Aufruf
gemacht hat. Einige Compiler unterstützen die Ausgabe von Stacktraces.
In der ersten Variante muß mindestens der globale new Operator und der globale delete Operator,
besser auch alle Operatoren (new,delete) der Klassen, um die Fähigkeit erweitert werden,
daß mitgeschrieben wird an welcher Adresse Speicher angelegt wurde und wieviel und an
welcher Adresse Speicher freigegeben wurde. Aus den entstehenden Statistiken können Schlüsse
gezogen werden.
Performance bei der Speicherbelegung
Probleme entstehen, wenn ein Objekt in seiner Speicherbelegung stängig wächst, z.B. Stringobjekte,
die ständig mit append erweitert werden.
Durch das ständige Erweitern wird entweder der Speicher fragmentiert, das Objekt hält für jede
Erweiterung einen neuen mit new angelegten Speicherbereich oder das Objekt wird ständig umkopiert
in mit new neu angelegte Speicherbereiche. Es wird also ständig new aufgerufen.
Beispiel:
String s;
for (int i=0; i<1000; i++) {
s.append("so'n Mist"); // Erweiterung dynamisch auf dem Heap
}
Die erste Variante ist langsamer, wobei sich die Zeiten mit jedem append vergrößern (Aufschaukeln).
char s[1001];
for (int i=0; i<1000; i++) {
strcat(s, "so'n Mist"); // Erweiterung auf dem stack
}
Die zweite Variante hat konstante Zeiten für jedes Anhängen mit strcat.
Fließkommazahlen (C++)
Darstellung
Fließkommazahlen werden als Mantisse und Exponent dargestellt.
Der Teil vor dem Komma wird korrekt dargestellt. Der Teil nach dem Komma wird nur
korrekt dargestellt, wenn er im Dezimalzahlensystem abbildbar ist. Endliche Dezimalbrüche sind
nicht zwingend endliche Dualbrüche. Beispiel: die Zahle 23,46.
In der Anzeige wird oft gerundet, so daß diese Fehler nicht sichtbar werden.
Damit solche Fehler sichtbar werden, muß im Debugger auf Hexanzeige umgestellt werden.
Das bedeutet, das bestimmte Zahlen von Anfang an nicht so intern dargestellt werden, wie sie auf
der Eingabe erscheinen.
Solche Fehler in den letzten Stellen, können bei Multiplikationen auftreten, weil die kompletten
Mantissen multipliziert werden und im Produkt der Rest abgeschnitten werden muß, daraus folgt große
Mantissen erzeugen Fehler.
Bei der Division entstehen diese Fehler oft, bei der Subtraktion und Addition nicht.
Rundungsfehler
Beim Runden gibt es immer einen gefährlichen Bereich.
Konventielle Funktionen:
Variante 1:
Die Funktion schneidet die Nachkommastellen ab -> alle Werte zwischen 0,5 und 1 werden falsch gerundet (nach unten anstatt nach oben)
Variante 2:
Die Funktion rundet zwischen 0 und 0,5 auf 0 und zwischen 0,5 und 1 auf 1.
Das wäre ideal, ist aber in der Regel nicht verfügbar.
Für die Variante 1 gibt es folgende Lösung, mit variabler Genauigkeit für den
Vergleich zweier Zahlen x und y auf y Ganzzahliger Teiler von x:
x - y * floor((x / y) + 0,5) > 0,00..001
Damit kann eine beliebige Genauigkeit erreicht werden.
Die Genauigkeit sollte auf die maximale Precision des Datentyps eingestellt werden.
Anzahl der Vorkommastellen einer Zahl berechnen
Die Anzahl der Stellen nach dem Komma können bei Fließkommazahlen aufgrund der Darstellung auf
einem Rechner nicht bestimmt werden.
Für die Anzahl der Stellen vor dem Komma ist folgendes Template möglich:
template <class T>
long getVorkommastellen(T x) {
x = abs(x); //log10 auf negative Zahlen ist nicht möglich
if(x < 1) //log10 auf Zahlen kleiner 1 ist nicht möglich
//0 ginge auch
return 1;
else
return long(log10(x)) +1;
}
Aussagen über die Anzahl der Nachkommastellen einer Fließzahl
Alle Funktionen der Art, multipliziere mit Stellenzahl * 10 ziehe den Vorkommaanteil ab und
teste ob der Rest noch ungleich 0 ist, schlagen fehl, wenn ein Rundungsfehler auftritt.
Die folgende Funktion ist schon nicht schlecht:
bool classA::checkNachkommastellen(double value,
const unsigned short precision)
{
// zunächst Absolutwert bilden
if (value < 0.)
value = -value;
//bei mehr als 15 Stellen hab wir in double keinen Platz mehr in der
//Mantisse und da wir überall im Server nur double nutzen und kein
//größeres Format, würde die Funktion Quatsch berechnen
long digits = getDigitsInFrontOfDecimalPoint(value);
if(precision < 1 && digits == 15)
return true;
digits += precision;
if (digits > 15)
return false;
// die erlaubte Precision wird vor das Komma geschoben,
// weil der integrale Teil immer richtig dargestellt wird haben wir
// hier auch keine Fehler
value = value * pow(10, precision);
// der Vorkommaanteil wird abgezogen
value = value - (double)((long long)value);
// Ist der Wert kleiner als unsere Null-Grenze?
return value < eps;
}
Der Nachteil der ersten Variante:
Je größer die Precision umso kleiner wird der Bereich der
hinterm Komma übrig bleibt und den wir noch mit eps vergleichen können und unsere Aussage
wird sehr wackelig.
Besser ist:
bool classA::checkNachkommastellen(double value,
const unsigned short precision)
{
double tmpVal = 0;
static const double loge2 = log(2);
// zunächst Absolutwert bilden
if (value < 0.)
value = -value;
// die erlaubte Precision wird vor das Komma geschoben,
// gerundet und wieder zurueckgeschoben
tmpVal = (long long) (value * pow(10, precision)+0.5) /
pow(10, precision);
// der Vorkomma-Anteil wird abgezogen, negative Vorzeichen entfernt
value -= tmpVal;
if (value < 0.0)
value = -value;
// Der gerundete Rest muss jetzt kleiner sein als
// die noch gueltigen Bitstellen für einen double (abzueglich
// derer die fuer den ganzzahligen Anteil verbraten wurden) noch
// hergeben!
return value < pow(2, -(DBL_MANT_DIG - (int) (log(value)/loge2)));
}
DBL_MANT_DIG steht in float.h.
Multi-Prozessor-Programme (C++)
Für den Multi-Prozessor-Einsatz gibt es verschiedene Modelle.
Modell1, multi processor single memory:
Das Problem, wenn jeder Prozessor seinen eigenen Speicher hat, müssen die Daten zwischen den
einzelnen Prozessoren am Ende der Bearbeitungen ausgetauscht werden.
Modell2, multi processor shared memory:
Das Problem hierbei ist die Realisierung des wechselseitigen Zugriffs auf die Speicherresource
über Locks (Mutex = mutual exclusion).
In einen durch einen Lock geschützten Bereich kann nur ein Process eintreten, alle anderen müssen
warten. Das heißt die Arbeit serialisiert sich an dieser Stelle und ist nicht mehr parallel.
In einem shared memory ist das Allocieren von neuem Speicher ein besonderes Problem, weil wieder
alle warten. Die Serialisierung tritt beim Zugriff auf alle Resoucen auf. Außer dem Speicher
stellt der gemeinsame Zugriff auf eine Datei ein besonderes Problem dar. In Datenbanken existieren
meißt seperate Lösungen (multi user systeme).
Über Semaphoren besteht die Möglichkeit eine bestimmte Anzahl an Threads in einen geschützten
Bereich eintreten zu lassen, z.B.: es werden n Filedescriptoren zugelassen, wenn alle im Einsatz
sind blockiert die Semaphore alle weiteren Threads.
Probleme bei der Speicherbelegung durch Objektinstanziierung:
Jeder Thread hat einen eigenen Stack mit einer festen Größe (z.B. 1MB), wenn diese überschritten
wird gibt es einen Stackoverflow.
Auf diesem Stack legt ein Thread alle seine Variblen ab die:
1. als static erzeugt werden. Außer static Variablen in function bodys.
2. die nicht mit new erzeugt werden. Außer wenn im Konstruktor einer so erzeugten
Variablen new -Erzeugungen versteckt sind.
Die mit new erzeugten Variablen werden auf dem Heap abgelegt. Dieser stellt den shared memory dar.
Dabei wird eine entsprechende malloc - Routine aufgerufen. An dieser routine findet eine
Serialisierung statt (Problempunkt).
Threads - Nebenläufigkeit und Synchronisation (C++)
Synchronisation wird immer dann wichtig, wenn mehrere Threads auf die gleiche Adresse im Speicher
zugreifen. Das geschieht:
- wenn von mehrere Threads auf eine globale Variable zugegriffen wird,
- wenn ein Thread Instanzen einer Klasse XXX mit Klassenvariablen (static) nutzt,
es besteht die Gefahr des Zugriffs durch andere Threads,
die Instanzen der Klasse XXX nutzen (die Klassenvariablen sind für alle gleich (gleiche Speicheradressen))
- wenn Objektinstanzen oder Variablen von mehreren Threads referenziert werden,
die Instanzen werden also erzeugt und die Speicheradressen werden an andere Threads weitergegeben.
Typische Problemstellen sind also Singletons, Variablen die nicht vom Thread selber angelegt wurden, ...
Ein typisches Beispiel
Eine Klasse verwaltet eine statische Collection von Integern.
Eine Methode get() liefert einen Integerwert aus der Collection. Der Zugriff erfolgt über einen Schlüssel,
der innerhalb von get() berechnet wird. Die Methode führt also erst eine Berechnung des Schlüssel aus und
liefert dann den Ergebniswert aus der Collection über diesen Schlüssel.
Problem
Thread eins erstellt eine Instanz der Klasse und ruft get() auf. Die Methode berechnet den Schlüssel,
noch bevor der Zugriff auf die Collection erfolgt wird der Thread zufällig vom Scheduler auf wartend gesetzt und
ein zweiter Thread wird aktiviert. Dieser Thread löscht zufällig genau das Element aus der Collection,
für das wir in Thread eins einen Schlüssel in get() berechnet haben. Später wird Thread eins wieder vom
Scheduler aktiviert und versucht den Wert aus der Collection zu lesen und erzeugt eine Exception, weil der
Wert nicht mehr vorhanden ist ....
1. Lösung
Die einfachste Lösung besteht im setzten eines einfachen Mutex (Mutual Exclusion). Ein Mutex schützt
einen bestimmten Programmbereich und ist meist Teil der Sprachspezifikation. Im Beispiel könnte man
den Mutex auf get() setzten. Somit kann immer nur ein Thread in get() eintreten.
Solange der Thread get() nicht abgearbeitet hat, darf kein anderer Thread in get() eintreten.
Wenn also der zweite Thread den Eintrag in der Collection nur innerhalb von get() löschen kann,
sind wir sicher, weil dieser nicht zum Löschen in get() hinein kommt.
Problem der 1. Lösung
Wenn der zweite Thread aber (Normalfall) über eine andere Funktion delete() den Eintrag löschen kann,
stehen wir wieder vor dem alten Problem. Die Lösung besteht dann in komplexeren Synchronisationsstrukturen.
2. Lösung
Einige Bibliotheken bieten zur Synchronisation besondere Mutexklassen an. Ein Klasse instanziiert einen
solchen Mutex und mehrere Funktionen der Klasse werden über diesen einen Mutex abgesichert.
Somit kann ein Thread nur in eine gesicherte Funktion, wenn kein anderer Thread in irgendeiner anderen
durch diesen Mutex geschützten Funktion steckt. Ein nächster Schritt ist eine weitere Unterteilung in
Read- und Writemutex. Das Prinzip ist gleich dem vorherigen, nur kann die Mutexinstanz eine Funktion
zum Lesen oder zum Schreiben schützen. Ein Thread kann also eine Funktion zum Lesen betreten,
wenn kein anderer Thread in einer Schreibfunktion steckt. Es können also beliebig viele Threads gleichzeitig
Lesefunktionen betreten. Ein Thread kann aber nur dann in eine Schreibfunktion, wenn kein anderer
Thread in einer Lese- oder Schreibfunktion steht...
Character Encoding
ASCII
Die bekannteste Zeichenkodierung ist US-ASCII
(American Standard Code for Information Interchange), die von der ANSI (American National Standards Institute)
als ANSI X3.4 (1968) standardisiert wurde.
ASCII beschreibt einen Zeichensatz, der auf dem lateinischen Alphabet basiert.
ASCII beinhaltet ursprünglich einen Sieben-Bit-Code, was bedeutet, dass er binäre Ganzzahlen verwendet,
die mit sieben binären Ziffern dargestellt werden (entspricht 0 bis 127), um Informationen darzustellen.
Das 8. Bit wurde für Steuerfunktionen genutzt.
US-ASCII ist ausreichend, um lateinische und US-amerikanische
Texte, sowie Texte in einigen wenigen weiteren Sprachen zu kodieren.
Um auch andere europäische Sprachen zu codieren wurde von der ISO (International Organization for Standardization)
der internationale Standard ISO 646 (1972) erstellt.
Für die deutsche, die dänische und vierzehn weitere Sprachen sieht ISO 646 nationale Varianten vor,
die die US-ASCII-Zeichen:
#, $, @, [, \, ], , `, {, |, }, ,
durch nationale Zeichen ersetzen.
Die deutsche Variante ISO 646-DE
nimmt beispielsweise diese Ersetzungen vor:
@ = §, [ = Ä, \ = Ö, ] = Ü, { = ä, | = ö, } = ü, = ß.
ISO-Zeichensatz
Mitte der achtziger Jahre erweiterte die ECMA (European Computer Manufacturers Association)
den Zeichensatz US-ASCII zu einer Familie von Zeichensätzen,
mit denen die alphabetischen Schriftsysteme kodiert werden können.
Diese wurden inzwischen von der ISO unter dem Namen ISO 8859 kodierte Zeichensatzfamilie
übernommen und bestehen aus den Zeichensätzen ISO 8859-1 bis ISO 8859-15. Jeder
Zeichensatz ISO 8859-X umfasst die 128 US-ASCII-Zeichen und ergänzt sie um weitere 128 Zeichen.
Für die meisten westeuropäischen Sprachen, z.B. das Deutsche, Dänische oder Französische,
ist ISO 8859-1, auch ISO Latin-1 genannt, relevant.
ISO 8859-7 deckt das griechische Alphabet ab und
ISO-8859-15 ersetzt im wesentlichen das internationale Währungssymbol mit dem Eurozeichen.
Die sogenannte Code Page 1252 von Microsoft Windows ist in weiten Teilen identisch mit
ISO 8859-1, ersetzt aber einige Kontrollzeichen von ISO 8859-1 durch druckbare Zeichen, u.a.
das Eurozeichen.
Unicode
Anfang der neunziger Jahre kamen Unicode und ISO/IEC 10646 heraus. Das
Ziel dieser beiden äquivalenten Zeichenkodierungen ist Universalität, also Texte aus
sämtlichen Sprachen der Welt eindeutig zu kodieren. Die aktuellen Versionen
Unicode 3.0 und ISO/IEC10646-1:2000, kodieren 49.194 Zeichen, die alle modernen und viele
klassischen Sprachen abdecken. Unicode und ISO/IEC 10646 werden laufend um weitere
historisch bedeutsame Zeichen und Sprachen ergänzt.
Im Unicode werden die einzelnen Zeichensätze als Kodeeinheiten abgelegt.
Die erste Einheit bilden die Standard-ASCII-Zeichen gefolgt von Griechisch, Kyrillisch,
Hebräisch, Arabisch, ...
Das Ansprechen dieser Einheiten erfolgt durch das Encoding.
Encoding
Unicode hat 3 Kodierungsformate, die beschreiben in welcher Form die Bitwerte zu bewerten
sind.
In UTF8 werden Zeichen als Bytefolgen abgelegt. Wobei die Anzahl
an Bytes von den Zeichen abhängen. Für ASCII Zeichen wird nur ein Byte benötigt.
Für ein arabisches Zeichen wird mehr als ein Byte benötigt.
UTF 8 wird vor allem für HTML genutzt und kann von allen modernen Browsern dargestellt werden.
UTF16 ist ein Encoding für ein ausgewogenes Verhältnis zwischen Zugriffszeit und
Speicherplatz. Alle wichtigen Zeichen werden durch einen 2 Byte Wert dargestellt.
Alle übrigen Zeichen können durch ein 32 Bit Wert (4 Byte) dargestellt werden.
In UTF32 werden alle Zeichen durch einen 32 Bit Wert dargestellt.
Mehr als 2 ^ 32 Zeichen (4.294.967.296) können nicht dargestellt werden.
|