BigBasti's Blog About Me & my Digital Lifestyle

Asynchrone Programmierung mit Threads Teil 1

In diesem ersten Teil dieser Serie möchte ich auf die Theorie hinter der Asynchronen Programmierung zu Sprechen kommen, Vor- und Nachteile dieser und auf Probleme, die dabei entstehen können.

Bild 1: Mooresches Gesetz grafisch dargestellt (klicken zum vergrößern) Quelle: Wikipedia

Wenn man mal auf die letzten Jahre schaut, sieht man eine starke Entwicklung der Computerrechenpower, zB. 1998 galt ein Computer mit 500 MHz noch als sehr leistungsfähig. Bis heute gilt auch noch (naja zumindest fast) das Mooresche Gesetz, welches besagt, dass alle 2 Jahre sich die Schaltkreise auf einem Chip (CPU) verdoppeln und somit auch die Leistung.

Da die Rechenleistung der Computer stetig stieg, war es für Programmierer meist nicht nötig, bzw. gab es keine Anreize die Software effizienter zu gestalten, denn mit jedem neuen Computer lief auch das Programm schneller!

Doch heute sind wir an einer Grenze angekommen, an der es kaum noch möglich ist eine einzelne CPU leistungsfähiger zu machen, und somit stagnieren wir zur Zeit bei ca 3 - 4 GHz bei  SongleCore CPUs. (Ich selbst habe vor ca 6 Jahren geschätzt, dass die Marke von 5 GHz nicht mehr überschritten wird.)

Da man die Transistorenzahl auf den Chips nicht mehr erhöhen kann bedient sich die Industrie einem Trick. Sie bauen einfach zwei (oder mehr) CPUs in eine. Das ganze nennt sich dann DualCore. Man hat also zwei echte von einander unabhängig arbeitende CPUs.

Bild 2: Im Windows Taskmanager sieht man die 2 CPUs bei der Arbeit (oben)

Das Problem hierbei ist nur, dass man nun zwar zwei Kerne hat, diese aber nicht schneller geworden sind! So hat man zB. 2x 2,2 GHz was aber nicht heißt, dass die Rechenleistung dieser CPU bei 4,4 Ghz liegt!

Denn ein Programm läuft standardmäßig nur auf einem Kern, und da dieser nicht schneller geworden ist läuft das Programm darauf genauso schnell wie auf einem SingleCore 2,2 GHz Prozessor! (Natürlich ist das nicht ganz wahr, sicher läuft das Programm auf dem DualCore etwas schneller, da das System andere Prozesse auf den zweiten Kern auslagert, aber der Performancegewinn ist nicht enorm!)

Also sind wir Programmierer nun gezwungen unsere Software so zu gestalten, dass diese möglichst alle Kerne der CPU auslasten. Also Parallelprogrammierung anwenden!

Doch das ist leider leichter gesagt als getan, denn es gibt viele Steine die da in dem Weg liegen und viele Kleinigkeiten die man beachten muss! Der Anfang ist aber verschiedene Abläufe des Programms in einzelne Threads aufzuteilen.

Zunächsteinmal muss man wissen, dass nicht jedes Programm in Threads aufgeteilt werden kann (dazu gleich mehr) und desweiteren muss man verstehen, dass egal wieviele Prozessoren ein Computer hat man ein Programm nicht unendlich schnell machen kann!

Daher ist die Aussage "je mehr Kerne desto schneller das Programm" falsch! Warum das so ist werde ich nun erklären!

Sehen wir uns eine vereinfachte Programmkette an:

Darstellung 1: Sequentieller Programmablauf

Hier steht "T" für Thread und "P" für Prozedur.

Da jedes Programm einen klaren Einstiegspunkt haben muss (was hier P1 ist) kann dieser schon mal nicht in einen zweiten Thread ausgelagert werden. Der Endpunkt der meist alle Ressourcen freigibt ist der Punkt wo alles zusammenläuft, daher kann dieser auch nicht ausgelagert/aufgeteilt werden!

Somit können schon 2 von unseren 7 Prozeduren nicht ausgelagert werden und müssen sequentiell (nacheinander) ablaufen. Gut, schauen wir uns mal die restlichen 5 Prozeduren an.

Ein Programm kommt nicht ohne sequentielle Abläufe aus, da es oft so ist, dass eine Prozedur mit Ergebnissen einer anderen Prozedur arbeitet. Logischerweise können diese zwei Prozeduren nicht parallel laufen.

Für dieses Beispiel nehmen wir an, dass jeder Thread auf einer eigenen CPU laufen würde!

Für unser Beispiel denken wir uns mal, dass P4 mit Ergebnissen von P3 arbeitet und diese daher nicht parallelisiert werden können. Somit fallen wieder 2 Prozeduren aus, die man parallelisieren könnte.

Desweiteren benötigt P6 die Daten aller Prozeduren die davor liefen und kann daher auch nicht ausgelagert werden!

Somit bleiben uns zwei Prozeduren, die wir in einen andren Thread packen könnten. Was ca. so aussehen würde:

Darstellung 2: Asynchroner Programmablauf mit 2 Threads

Wie man sieht konnten wir in diesem Programm P2 und P5 erfolgreich in einen zweiten Thread auslagern. Doch was heißt das für unser Programm? hier ein kleines Rechenbeispiel:

Nehmen wir an, dass jede Prozedur eine Laufzeit von 5 Sekunden hat, das würde bedeuten, dass unser Programm wie in Darstellung 1 aufgeführt 35 Sekunden benötigen würde, um durch zulaufen.

Da bei dem Programm aus Darstellung 2, 2 Prozeduren "Parallel" ablaufen, verringert sich die Zeit auf 25 Sekunden. Also eine Ersparnis von knapp 30 %!

Natürlich ist das hier eine Ausnahme, denn es wird wohl kein Programm geben, dessen Prozeduren alle Gleichschnell sind, was uns zu unserem Nächsten Problem führt!

Denn wenn die Prozeduren nicht alle gleich schnell sind kann es zu Verzögerungen kommen! Das ist so, als wenn man Einen Tisch bauen will, und bestellt die Tischbeine bei Amazon und die Tischplatte bei Ebay. Den Tisch wirklich zusammenbauen kann man erst wenn beide Teile da sind! Fehlt eins der Teile muss man warten bis das andere auch ankommt!

Wenn wir das nun auf unser Programm aus Darstellung 2 beziehen heißt das, P6 erst weiter machen kann, wenn sowohl P4 als auch P5 Abgeschlossen sind! Wenn P4 zB. schneller fertig ist dann pausiert der erste Thread solange bis der zweite fertig ist! Dies kann zu unangenehmen Effekten führen, die das Programm sogar verlangsamen können statt es zu beschleunigen!

Wenn P2 und P5 also 6 Sekunden benötigen würden statt 5 würde die Laufzeit unseres Programms sich um 2 Sekunden verlängern also 27!

Nun könnte man aber sagen, P2 und P5 sind ja nicht von einander abhängig also lagere ich diese zwei Prozeduren auch noch aus:

Darstellung 3: Asynchroner Programmablauf mit 3 Threads

Hier müsste P6 auf die Fertigstellung von P4, P2 und P5 warten!

Das würde allerdings nur Sinn machen, wenn die Prozeduren P2 und P5 in der Summe länger brauchen würden als P3 und P4! Denn wenn P2 und P5 zusammen schneller sind als als P3 und P4 würde dieses erneute Auslagern nichts bringen, da sie sowieso schneller fertig wären als P3 und P4!

Wie man sieht wurde unser Programm durch die Auslagerunggen von Prozeduren um fast ein Drittel schneller! Aber man sieht auch, dass unser Programm auch nicht schneller werden würde wenn man 10 oder 100 CPUs hätte! Da wir sowieso nur 2 CPUs benutzen bringen uns die restlichen CPUs nichts da wir unser Programm nicht weiter aufteilen können!

Besonders Sinn macht es Prozeduren auszulagern, die viel Zeit in Anspruch nehmen. Denn wenn man solche Prozeduren Sequentiell abarbeitet blockieren diese den Ganzen Ablauf! Besonders Schleifen machen das ganz gerne!

Wenn man zb. eine Grafische Oberfläche hat und eine lange Prozedur im selben Thread (der auch die GUI verwaltet) startet, reagiert diese solange nicht mehr bis diese Prozedur durchgelaufen ist! Dann sieht man meist folgendes:

Bild 3: Man beachte das "Keine rückmeldung"

Um das zu verhindern sollte man längere Schleifen und Rechenoperationen immer in einen Hintergrund Thread verschieben damit die Oberfläche weiterhin bedienbar bleibt!

Ansich ist Threading sehr nützlich wir haben nun einige Vorteile kennengelernt wie den Performancegewinn, aber auch Nachteile gefunden, wie etwa Verzögerungen. Aber auch bei der Programmierung von Threads gibts einige Gefahren die man nur durch genaues Debuggen finden kann!

An dieser Stelle möchte ich ein Beispiel bringen, welches die Problematik darstellt!

Nehmen wir an, wir haben ein Programm, dass für ein Ehepaar das Konto verwaltet! Jeder der beiden hat dabei seinen eigenen Thread, der für den Ehepartner das Geld vom Konto abhebt! Die Hauptaufgabe unseres Programms ist es dafür zu sorgen, dass man das Konto nicht überbelastet also mehr abhebt als drauf ist!

Ein typischer Programmablauf wäre dann wie folgt:

### Programmstart
Verbinde mit Konto
Frage wieviel Geld abgehoben werden soll
speichere den gewünschten Betrag in Variable $Betrag
Prüfe ob $Betrag kleiner ist als der Betrag auf dem Konto
Wenn genug Geld auf dem Konto vorhanden ist
Hebe $Betrag vom Konto ab
Trenne Verbindung
### Programmende

Beide Threads (von beiden Ehepartnern) laufen dabei Parallel, damit der eine nicht waren muss und immer sofort Zugriff hat.

Auf den ersten Blick sieht das Programm sicher aus, man prüft ob genug Geld auf dem Konto ist bevor was abgehoben wird. Totsicher - oder?

Eigentlich ja, wenn das Programm nur in einem Thread laufen würde! Denn es könnte ja zu dem Fall kommen, dass beide Ehepartner gleichzeitig Geld abheben wollen:

Nehmen wir an auf dem Konto sind 100 Euro!

Dann würde folgendes passieren: Beide wollen 70 Euro abheben, nun würden die Threads "gleichzeitig" prüfen, ob genug Geld auf dem Konto ist. Und da sie beide "gleichzeitig" prüfen und noch keiner Geld abgehoben hat ist die Bedingung erfüllt und beide Threads heben 70 Euro vom Konto ab, da sie ja vorher geprüft haben, ob genug Geld da war - und es war ja auch genug da!

Als Ergebnis hätten wir einen neuen Kontostand von -40 Euro - genau das was wir mit dem Programm verhindern wollten!

Ähnliche Probleme können auftreten, wenn mehrere Threads mit mit der selben Datenquelle arbeiten. Wenn zB. Thread 1 eine Datei löscht auf die Thread 2 noch zugreifen will, stürzt das Programm mit einer Exception ab!

Man müss also Möglichkeiten suchen solche Probleme zu erkennen und vorzubeugen! Das werde ich dann im Teil 2 dieser Serie an Hand von ein paar Beispielen behandeln!

In diesem ersten Teil dieser Serie möchte ich auf die Theorie hinter der Asynchronen Programmierung zu Sprechen kommen, Vor- und Nachteile dieser und auf Probleme, die dabei entstehen können. Bild 1: Mooresches Gesetz grafisch dargestellt (klicken zum vergrößern) Quelle: Wikipedia Wenn man mal auf die letzten Jahre schaut, sieht man eine starke Entwicklung der Computerrechenpower, zB. 1998 galt ein Computer mit 500 MHz noch als sehr leistungsfähig. Bis heute gilt auch noch (naja zumindest fast) das Mooresche Gesetz, welches besagt, dass alle 2 Jahre sich die Schaltkreise auf einem Chip (CPU) verdoppeln und somit auch die Leistung. Da die Rechenleistung der Computer stetig stieg, war es für Programmierer meist nicht nötig, bzw. gab es keine Anreize die Software effizienter zu gestalten, denn mit jedem neuen Computer lief auch das Programm schneller! Doch heute sind wir an einer Grenze angekommen, an der es kaum noch möglich ist eine einzelne CPU leistungsfähiger zu machen, und somit stagnier

    Public Function saveNodeState(ByVal tn As TreeNode, Optional ByVal retv As String = "") As String
        Dim retVal As String = retVal & retv
        'Jede Node in der übergebenen Node durchgenen
        For Each tnn As TreeNode In tn.Nodes
            'Prüfen, welche Nodes geöffnet sind und diesen zustand speichern
            ' 1 => offen
            ' 0 => geschlossen
            If tnn.Nodes.Count > 0 Then
                If tnn.IsExpanded Then
                    retVal = retVal & "1"
                Else
                    retVal = retVal & "0"
                End If
                'Hats der node weitere "kinder" ist es ein ordner
                'also diese node rekursiv an sich selbst übergeben!
                retVal = saveNodeState(tnn, retVal)
            End If
        Next
        Return retVal
    End Function

    Public Function loadNodeState(ByVal tn As TreeNode, Optional ByVal settings As String = "")
        'Jede Node in der übergebenen Node durchgenen
        'Den Zustand der Nodes wiederherstellen (Offen oder geschlossen)
        For Each tnn As TreeNode In tn.Nodes
            If tnn.Nodes.Count < 1 Then
                'Wenn der Node keine Kinder hat überspringen
            Else
                'Prüfen, ob der Node früher geöffnet war
                If settings <> "" Then
                    If settings.Substring(0, 1) = "1" Then
                        tnn.Expand()
                    End If
                    settings = settings.Substring(1, settings.Length - 1)
                End If

                'Hat der node weitere "kinder" ist es ein ordner
                'also diesen node rekursiv an sich selbst übergeben!
                settings = loadNodeState(tnn, settings)
            End If
        Next
        Return settings
    End Function

POST /wiki/Spezial:Search HTTP/1.1
Host: de.wikipedia.org
Content-Type: application/x-www-form-urlencoded
Content-Length: 24
search=Katzen&go=Artikel

    Public Function uploadPic(ByVal pic As Byte(), ByVal filename As String, ByVal user As String, ByVal pass As String)
        Dim encoding As String = "iso-8859-1"

        'Erzeugen einer einzigartigen identifikation
        Dim gui As String = Guid.NewGuid().ToString()

        'Diese wird für den Header und den footer der Daten benötigt
        Dim head As String = String.Format("--{0}", gui)
        Dim foot As String = String.Format("--{0}--", gui)

        'Einen Stringbuilder erstellen, in dem wir nun bequem die
        'benötigten POST Daten speichern können
        Dim contents As StringBuilder = New StringBuilder()

        'Benutzerdaten schreiben (benutzername)
        contents.AppendLine(head)
        contents.AppendLine(String.Format("Content-Disposition: form-data; name=""{0}""", "username"))
        contents.AppendLine()
        contents.AppendLine(user)

        'Benutzerdaten schreiben (passwort)
        contents.AppendLine(head)
        contents.AppendLine(String.Format("Content-Disposition: form-data; name=""{0}""", "password"))
        contents.AppendLine()
        contents.AppendLine(pass)

        'Header schreiben
        contents.AppendLine(head)
        'Bildinformationen schreiben, Bildkopf und die Binärdaten
        Dim fileHeader As String = String.Format("Content-Disposition: file; name=""{0}""; filename=""{1}""", "media", filename)
        Dim fileData As String = System.Text.Encoding.GetEncoding(encoding).GetString(pic)

        'Informationen zu dem Übergebenen Dateityp schreiben
        contents.AppendLine(fileHeader)
        contents.AppendLine(String.Format("Content-Type: {0}", "image/jpeg"))
        contents.AppendLine()
        contents.AppendLine(fileData)

        'Durch schreiben des footers signalisieren dass keine Daten mehr kommen
        contents.AppendLine(foot)

        MessageBox.Show(contents.ToString)

        'Stream Reader zum lesen der Antwort von Twitpic
        Dim reader As StreamReader
        Dim result As String
        Dim response As HttpWebResponse

        'Einen Webrequest zu der TwitPic API erstellen
        Dim request As HttpWebRequest = WebRequest.Create("http://twitpic.com/api/upload")

        'Die Auflagen die in der API beschreiben sind erfüllen:
        'API-Zitat:
        '---
        'Fields to post in:
        '(post data should be formatted as multipart/form-data)
        '---
        request.ContentType = String.Format("multipart/form-data; boundary={0}", gui)
        request.Method = "POST"

        'Die Daten die noch im Stringbuilder als String vorliegen
        'in das byte (Binär)-Format umwandeln, damit die API diese annimt
        Dim bytes As Byte() = System.Text.Encoding.GetEncoding(encoding).GetBytes(contents.ToString())
        request.ContentLength = bytes.Length

        'Einen Stream aus dem WebRequest erstellen
        Dim writer As Stream = request.GetRequestStream()

        'Die Binären Daten in den Strom schreiben
        writer.Write(bytes, 0, bytes.Length)
        response = request.GetResponse()

        'Antwort von Twitpic empfangen
        reader = New StreamReader(response.GetResponseStream)
        result = reader.ReadToEnd

        reader.Close()

        Return result
    End Function

    Public Function shortURL(ByVal langeURL As String)
        Dim retVal As String = ""

        'Für dem API Aufruf wird benötigt:
        '-> Die Versionsnummer (version)
        '-> ein Benutzername (login)
        '-> ein API-Schlüssel (apiKey)

        'Den API-Aufruf starten:
        Dim myRequest As WebRequest = WebRequest.Create _
            ("http://api.bit.ly/shorten?" & _
            "version=2.0.1" & _
            "&format=xml" & _
            "&longUrl=" & langeURL & _
            "&login=bitlyapidemo" & _
            "&apiKey=R_0da49e0a9118ff35f52f629d2d71bf07")

        Dim myResponse As WebResponse = myRequest.GetResponse

        'Den erzeugen Strom auslesen
        Dim myReader As StreamReader = _
                New StreamReader(myResponse.GetResponseStream)

        'Stream auslesen
        retVal = myReader.ReadToEnd

        myReader.Close()

        Return retVal
    End Function

    Public Function extractURL(ByVal response As String)
        'Ein XML-Dokument anhand der Antword von bit.ly erstellen:
        Dim myDoc As New XmlDocument
        myDoc.LoadXml(response)

        'Nun nehmen wir uns das Element raus, in dem die
        'neue kurze URL steht:
        Return myDoc.SelectSingleNode("/bitly/results/nodeKeyVal/shortUrl").InnerText
    End Function

    Public Function shortURL(ByVal langeURL As String)
        Dim retVal As String = ""

        'Den API-Aufruf starten:
        Dim myRequest As WebRequest = WebRequest.Create _
            ("http://tinyurl.com/api-create.php?url=" & langeURL)

        Dim myResponse As WebResponse = myRequest.GetResponse

        'Den erzeugen Strom auslesen
        Dim myReader As StreamReader = _
                New StreamReader(myResponse.GetResponseStream)

        'Stream auslesen
        retVal = myReader.ReadToEnd

        myReader.Close()

        Return retVal
    End Function

//PHP Code:
function TinyURL($u){
    return file_get_contents('http://tinyurl.com/api-create.php?url='.$u);
}