EINFÜHRUNG

Man kann einen Computer gemäss dem von Neumann-Modell als eine sequentielle Maschine auffassen, die auf Grund eines Programms in Zeitschritten Anweisung um Anweisung abarbeitet. In diesem Modell gibt es keine gleichzeitig ablaufenden Aktionen, also keine Parallelverarbeitung bzw. Nebenläufigkeit. Im täglichen Leben sind aber parallele Abläufe allgegenwärtig: So existiert und handelt jedes Lebewesen als eigenständiges Individuum und im menschlichen Körper laufen viele Prozesse gleichzeitig ab.

Die Vorteile der Parallelverarbeitung sind evident: Sie bringt eine enorme Leistungssteigerung, da Aufgaben in gleichen Zeitschlitzen gelöst werden. Zudem erhöht sich die Redundanz und Überlebenschance, da der Ausfall eines Teils nicht automatisch zum Versagen des ganzen Systems führt.

Das Parallelisieren von Algorithmen ist aber eine anspruchsvolle Herausforderung, die trotz grossen Anstrengungen noch immer in den Kinderschuhen steckt. Das Problem liegt vor allem daran, dass die Teilprozesse meist  geteilte Ressourcen verwenden und auf Ergebnisse anderer Prozesse warten müssen.

Unter einem Thread versteht man parallel laufender Code innerhalb desselben Programms und unter einem Prozess versteht man Code, der durch das Betriebssystem gesteuert parallel ausgeführt wird. Python bietet eine gute Unterstützung von beiden Arten der Parallelität. Hier betrachten wir aber nur die Verwendung von mehreren Threads, also das Multithreading.

MULTITHREADING IST EINFACHER ALS ES SCHEINT

In Python ist es sehr einfach, den Code einer deiner Funktionen von einem eigenen Thread ausführen zu lassen: Dazu importierst du das Modul threading und übergibst start_new_thread() den Funktionsnamen sowie eventuelle Parameterwerte, die du in ein Tupel verpackst. Der Thread beginnt sofort zu laufen und führt den Code deiner Funktion aus.

In deinem ersten Programm mit Threads sollen zwei Turtles unabhängig voneinander eine Treppe zeichnen. Dazu schreibst du eine beliebig benannte Funktion, hier mit paint() bezeichnet, die auch Parameter haben darf, beispielsweise hier die Turtle und ein Flag, das angibt, ob die Turtle eine Links- oder Rechtstreppe zeichnet. Der Funktion thread.start_new_thread() übergibst du als Parameter den Funktionsnamen und ein Tupel mit den Parameterwerten. Und schon geht's los!

from gturtle import *
import thread

def paint(t, isLeft):
    for i in range(16):
        t.forward(20)
        if isLeft:
            t.left(90)
        else:
            t.right(90)
        t.forward(20)
        if isLeft:
            t.right(90)
        else:
            t.left(90)
    
tf = TurtleFrame()
john = Turtle(tf)
john.setPos(-160, -160)
laura = Turtle(tf)
laura.setColor("red")
laura.setPenColor("red")
laura.setPos(160, -160)
thread.start_new_thread(paint, (john, False))
thread.start_new_thread(paint, (laura, True))

MEMO

THREAD ALS KLASSENINSTANZ ERZEUGEN, STARTEN

MEMO

THREAD BEENDEN

Ein einmal angestossener Thread kann nicht direkt mit einer Methode von aussen, also durch einen anderen Thread gestoppt werden. Um einen Thread anzuhalten, muss dafür gesorgt werden, dass die Methode run() zu Ende läuft. Darum ist eine nicht abbrechbare while-Schleife ist in der Methode run() eines Threads nie eine gute Idee. Statt dessen verwendest du für die while-Schleite eine globale boolesche Variable isRunning, die normalerweise auf True steht, aber von einem anderen Thread auf False gesetzt werden kann.

In deinem Programm führen beide Turtles eine Zufallsbewegung aus, bis sich eine der beiden über eine Kreisfläche hinausbewegt.

from threading import Thread
from random import random
import time
from gturtle import *

class TurtleAnimator(Thread):
    def __init__(self, turtle):
        Thread.__init__(self)
        self.t = turtle

    def run(self):
        while isRunning:
            self.t.forward(50 * random())
            self.t.left(-180 + 360 * random())

tf = TurtleFrame()
john = Turtle(tf)
laura = Turtle(tf)
laura.setColor("red")
laura.setPenColor("red")
laura.setPos(-200, 0)
laura.rightCircle(200)
laura.setPos(0, 0)
thread1 = TurtleAnimator(john)
thread2 = TurtleAnimator(laura)
isRunning = True
thread1.start() 
thread2.start()

while isRunning and not tf.isDisposed():
    if laura.distance(0, 0) > 200 or john.distance(0, 0) > 200:
        isRunning = False
    time.sleep(0.001)
tf.setTitle("Limit exceeded")

MEMO

THREAD ANHALTEN UND WEITERFÜHREN

Um einen Thread nur während einer bestimmten Zeit anzuhalten, kannst du mit einem globalen Flag isPaused die Aktionen in run() überspringen und später mit isPaused = False wieder weiterführen.

from threading import Thread
from random import random 
import time
from gturtle import *

class TurtleAnimator(Thread):
    def __init__(self, turtle):
        Thread.__init__(self)
        self.t = turtle

    def run(self):
        while True:
            if isPaused:
                Turtle.sleep(10)
            else: 
                self.t.forward(100 * random())
                self.t.left(-180 + 360 * random())

tf = TurtleFrame()
john = Turtle(tf)
laura = Turtle(tf)
laura.setColor("red")
laura.setPenColor("red")
laura.setPos(-200, 0)
laura.rightCircle(200)
laura.setPos(0, 0)
thread1 = TurtleAnimator(john)
thread2 = TurtleAnimator(laura)
isPaused = False
thread1.start() 
thread2.start()

tf.setTitle("Running")
while not isPaused and not tf.isDisposed():
    if laura.distance(0, 0) > 200 or john.distance(0, 0) > 200:
        isPaused = True
        tf.setTitle("Paused")
        Turtle.sleep(2000)
        laura.home()
        john.home()
        isPaused = False
        tf.setTitle("Running")
    time.sleep(0.001)

Eleganter ist es, den Thread mit Monitor.putSleep() anzuhalten und später mit Monitor.wakeUp() weiterzuführen.

from threading import Thread
from random import random
import time
from gturtle import *

class TurtleAnimator(Thread):
    def __init__(self, turtle):
        Thread.__init__(self)
        self.t = turtle

    def run(self):
        while True:
            if isPaused:
                Monitor.putSleep()
            self.t.forward(100 * random())
            self.t.left(-180 + 360 * random())

tf = TurtleFrame()
john = Turtle(tf)
laura = Turtle(tf)
laura.setColor("red")
laura.setPenColor("red")
laura.setPos(-200, 0)
laura.rightCircle(200)
laura.setPos(0, 0)
thread1 = TurtleAnimator(john)
thread2 = TurtleAnimator(laura)
isPaused = False
thread1.start() 
thread2.start()

tf.setTitle("Running")
while not isPaused and not tf.isDisposed():
    if laura.distance(0, 0) > 200 or john.distance(0, 0) > 200:
        isPaused = True
        tf.setTitle("Paused")
        Turtle.sleep(2000)
        laura.home()
        john.home()
        isPaused = False
        Monitor.wakeUp()
        tf.setTitle("Running")
    time.sleep(0.001)

MEMO

AUF THREADRESULTATE WARTEN

In diesem Programm beschäftigst du eine Arbeitskraft damit, die Summe von natürlichen Zahlen von 1 bis 1000000 durch einfaches Aufsummieren zu berechnen. Im Hauptprogramm wartest du, bis die Arbeit erledigt ist und bestimmst die dafür benötigte Zeit. Da diese etwas schwankt, lässt du die Arbeit von einem Worker-Thread 10 Mal durchführen. Um auf das Ende des Threads abzuwarten, verwendest du join().

from threading import Thread
import time

class WorkerThread(Thread):
     def __init__(self, begin, end):
         Thread.__init__(self)
         self.begin = begin
         self.end = end
         self.total = 0

     def run(self):
         for i in range(self.begin, self.end):
             self.total += i

startTime = time.clock()
repeat 10:
    thread = WorkerThread(0, 1000000)
    thread.start()
    thread.join() 
    print(thread.total)
print("Time elapsed:", time.clock() - startTime, "s")

Wie auch im täglichen Leben kannst du die mühsame Arbeit auf mehrere Arbeitskräfte verteilen. Wenn du zwei Worker-Threads dazu einsetzest, um je die Hälfte der Arbeit zu verrichten, so musst du auf das Ende der beiden warten, bevor du die Summe bildest.

from threading import Thread
import time

class WorkerThread(Thread):
     def __init__(self, begin, end):
         Thread.__init__(self)
         self.begin = begin
         self.end = end
         self.total = 0

     def run(self):
         for i in range(self.begin, self.end):
             self.total += i

startTime = time.clock()
repeat 10:
    thread1 = WorkerThread(0, 500000)
    thread2 = WorkerThread(500000, 1000000)
    thread1.start()
    thread2.start()
    thread1.join() 
    thread2.join()  
    result = thread1.total + thread2.total
    print result 
print "Time elapsed:", time.clock() - startTime, "s"

MEMO

KRITISCHE BEREICHE UND LOCKS

Da Threads quasi unabhängig voneinander Code ausführen, ist es heikel, falls mehrere Threads gemeinsame Daten verändern. Um Kollisionen zwischen Threads zu vermeiden, werden zusammengehörende Aktionen in einem sogenannten kritischen Programmblock zusammengefasst und  mit einem Schutz versehen, so dass  der Block nur ununterbrochen als Ganzes (atomar) ausgeführt wird. Versucht ein anderer Thread den Block auszuführen, so muss er warten, bis der aktuelle Thread den Block verlassen hat. Diesen Schutz realisiert man in Python mit einer Sperre (Lock). Eine Sperre ist eine Instanz der Klasse Lock und besitzt zwei Zustände gesperrt (locked) und entsperrt (unlocked) , sowie zwei Methoden acquire() und release() mit folgenden Regeln:

Man sagt anschaulich, dass ein Thread mit acquire() den Lock (die Sperre) erhält und mit release() den Lock (die Sperre) wieder abgibt [mehr... In anderen Programmiersprachen wird der Lock-Mechanismus auch Thread Synchronization
genannt. Statt von Lock spricht man auch von Monitor oder Semaphor].

Zum Schutz eines kritischen Blocks gehst du konkret wie folgt vor: Du erzeugst zuerst mit lock = Lock() ein globales Lock-Objekt, das natürlich am Anfang im Zustand unlocked ist. Beim Eintritt in den kritischen Block versucht jeder Thread mit acquire() den Lock zu erhalten. Gelingt dies nicht, weil der Lock bereits vergeben wurden, so wird der Thread automatisch in einen Wartezustand versetzt, bis der Lock wieder frei wird. Hat ein Thread den Lock erhalten, so durchläuft er den kritischen Block und muss beim Verlassen den Lock mit release() wieder abgeben, damit andere Threads ihn bekommen [mehr... Warten mehrere Threads auf den Lock, entscheidet das
Betriebssystem, wer ihn als nächstes erhält. Es ist aber
dafür besorgt, dass ihn alle wartenden Threads einmal
erhalten, dass also bestimmte Threads nicht "verhungern" (starvation)].

Wenn du das Durchlaufen des kritischen Blocks wie eine Ressource in einem mit einer Tür geschlossenen Raum auffasst, so kannst du dir einen Lock wie einen Schlüssel vorstellen, den ein Thread benötigt, um die Tür zum Raum zu öffnen. Er nimmt beim Eintritt den Schlüssel mit und verschliesst von Innen die Tür. Alle Threads, die nun  in den Raum eintreten wollen, müssen in einer Warteschlange vor der Tür auf den Schlüssel warten. Wenn der Thread seine Arbeit verrichtet hat, verlässt er den Raum, schliesst die Tür hängt den Schlüssel auf. Der erste wartende Thread nimmt den Schlüssel und kann damit seinerseits die Türe zum Raum öffnen. Wartet kein Thread, so bleibt der Schlüssel aufgehängt, bis ihn ein neu ankommender Thread benötigt.

In deinem Programm besteht der kritische Block aus dem Zeichnen und Löschen eines gefüllten Quadrats, wobei beim Löschen das Quadrat mit der weissen Hintergrundfarbe übermalt wird. Der Hauptthread erzeugt ein blinkendes Quadrat, indem er das rot gefüllte Quadrat zeichnet und nach einer bestimmten Wartezeit wieder löscht. In einem zweiten Thread MyThread wird mit getKeyCode() die Tastatur laufend abgefragt. Drückt der Benutzer die Leertaste, so wird das blinkende Quadrat an eine zufällige Position verschoben.

Es versteht sich von selbst, dass der kritische Block mit einem Lock geschützt werden muss. Erfolgt nämlich das Verschieben des Quadrats noch während dem Zeichnen und Löschen, so ergibt sich ein chaotisches Verhalten.

from gpanel import *
from threading import Thread, Lock
from random import randint

class MyThread(Thread):
    def run(self):
        while not isDisposed():
            if getKeyCode() == 32:
                print("----------- Lock requested by MyThread")
                lock.acquire()
                print("----------- Lock acquired by MyThread")
                move(randint(2, 8), randint(2, 8))
                delay(500)  # for demonstration purposes
                print("----------- Lock releasing by MyThread...")
                lock.release()
            else:
                delay(1)

def square():
    print("Lock requested by main")
    lock.acquire()
    print("Lock acquired by main")
    setColor("red")
    fillRectangle(2, 2)
    delay(1000)
    setColor("white")
    fillRectangle(2, 2) 
    delay(1000)
    print("Lock releasing by main...")
    lock.release()

lock = Lock()
makeGPanel(0, 10, 0, 10)

t = MyThread()
t.start()
move(5, 5)
while not isDisposed():
    square()
    delay(1) # Give up thread for a short while

MEMO

GUI-WORKERS

Callbacks, die durch GUI-Komponenten ausgelöst werden, laufen in einem bestimmten systemeigenen Thread (manchmal Event Dispatch Thread (EDT) genannt). Dieser ist dafür verantwortlich, dass das gesamte Grafikfenster mit allen Komponenten (Buttons, usw.) korrekt auf dem Bildschirm gerendert wird. Da das Rendern am Ende des Callbacks erfolgt, erscheint das GUI eingefroren, bis der Callback zurückkehrt. Es sind darum in einem GUI-Callback keine grafischen Animationen möglich. Du musst dich unbedingt an folgende Regel halten:

GUI-Callbacks müssen rasch zurückkehren, d.h in GUI-Callbacks dürfen keine lange dauernden Operationen ausgeführt werden.

Unter lange dauernd versteht man Zeiten von mehr als einige 10 ms. Dabei musst du aber vom schlimmsten Fall, d.h. von einer langsamen Hardware und grosser Systembelastung ausgehen. Dauert eine Aktion länger, so führst du sie in einem eigenen Thread aus, den man GUI-Worker nennt.

In deinem Programm zeichnest du mit einem Klick auf einen der zwei Buttons eine Rhodonea-Rosette. Das Zeichnen ist animiert und dauert eine gewisse Zeit. Du musst das Zeichnen daher in einem Worker-Thread ausführen, was mit deinen bisherigen Kenntnissen ja kein Problem ist.

Es gibt aber noch ein anderes Problem zu beachten: Da jeder Buttonklick einen neuen Thread erzeugt, können mehrere Zeichnungen kurz nacheinander gestartet werden, was zu einem Chaos führt. Du kannst dieses verhindern, wenn du die Buttons während der Ausführung der Zeichnung grau (inaktiv) machst [mehr... Dies ist im Gegensatz zum Einfrieren ein erlaubtes Look&Feel]

from gpanel import *
from javax.swing import *
import math
import thread

def rho(phi):
    return math.sin(n * phi)

def onButtonClick(e):
    global n
    enableGui(False)
    if e.getSource() == btn1:
        n = math.e
    elif e.getSource() == btn2:
        n = math.pi
#    drawRhodonea()    
    thread.start_new_thread(drawRhodonea, ())

def drawRhodonea():
    clear()
    phi = 0
    while phi < nbTurns * math.pi:
        r = rho(phi)
        x = r * math.cos(phi)    
        y = r * math.sin(phi)    
        if phi == 0:
          move(x, y)
        else:
          draw(x, y)
        phi += dphi
    enableGui(True)

def enableGui(enable):
    btn1.setEnabled(enable)
    btn2.setEnabled(enable)
                    
dphi = 0.01
nbTurns = 100
makeGPanel(-1.2, 1.2, -1.2, 1.2)
btn1 = JButton("Go (e)", actionListener = onButtonClick)
btn2 = JButton("Go (pi)", actionListener = onButtonClick)
addComponent(btn1)
addComponent(btn2)
validate()

MEMO

ZUSATZSTOFF

RACE CONDITIONS, DEADLOCKS

Der Mensch funktioniert zwar hochgradig parallel, sein logisches Denken ist aber weitgehend sequentiell. Aus diesem Grund ist es für uns Menschen schwierig, bei Programmen mit mehreren Threads den Überblick zu behalten. Darum sollte die Verwendung von Threads wohl überlegt werden, so elegant und herausfordernd sie auf den ersten Blick scheinen mag.

Abgesehen von Statistikprogrammen sollte ein Programm bei gleichen Anfangsbedingungen (Preconditions) auch immer die gleichen Resultate (Postconditions) abgeben. Dies ist bei Programmen mit mehreren Threads, die auf gemeinsame Daten zugreifen, keineswegs gewährleistet, selbst wenn die kritischen Bereiche mit Locks geschützt sind. In deinem Programm hast du zwei Threads thread1 und thread2, die eine Addition und eine Multiplikation mit zwei globalen Zahlen a und b vornehmen. a und b werden durch einen lock_a bzw. lock_b geschützt. Im Hauptteil erzeugst und startest du die beiden Threads nacheinander und wartest, bis sie zu Ende gelaufen sind. Zum Schluss schreibst du die Werte von a und b aus.

Für die Erzeugung der Threads verwendest du hier eine etwas andere Schreibweise, bei der du die Methoden run() als benannten Parameter im Konstruktor der Klasse Thread angibst.

from threading import Thread, Lock
from time import sleep

def run1():
    global a, b
    print("----------- lock_a requested by thread1")
    lock_a.acquire()
    print("----------- lock_a acquired by thread1")
    a += 5
#    sleep(1)
    print("----------- lock_b requested by thread1")
    lock_b.acquire()
    print("----------- lock_b acquired by thread1")
    b += 7
    print("----------- lock_a releasing by thread1")
    lock_a.release()
    print("----------- lock_b releasing by thread1")
    lock_b.release()

def run2():
    global a, b
    print("lock_b requested by thread2")
    lock_b.acquire()
    print("lock_b acquired by thread2")
    b *= 3
#    sleep(1)
    print("lock_a requested by thread2")
    lock_a.acquire()
    print("lock_a acquired by thread2")
    a *= 2
    print("lock_b releasing by thread2")
    lock_b.release()
    print("lock_a releasing by thread2")
    lock_a.release()

a = 100
b = 200
lock_a = Lock()
lock_b = Lock()

thread1 = Thread(target = run1)
thread1.start()
thread2 = Thread(target = run2)
thread2.start()
thread1.join()
thread2.join()
print("Result: a =", a, ", b =", b)

MEMO

lock_a requested by thread1

lock_b requested by thread2

Es kann aber noch viel schlimmer sein, denn das Programm kann auch total blockieren.  Vor dem "Sterben" wird noch Folgendes ausgeschrieben:

----------- lock_a requested by thread1
lock_b requested by thread2
lock_b acquired by thread2
lock_a requested by thread2
----------- lock_a acquired by thread1
----------- lock_b requested by thread1

Es braucht etwas kriminalistische Fähigkeiten um herauszufinden, was da geschehen ist. Wir versuchen es: Offenbar beginnt der thread1 als erster zu laufen und versucht, lock_a zu erhalten. Bevor er den Erhalt ausschreiben kann, versucht thread2 lock_b zu erhalten und erhält ihn auch. Gleich darauf versucht  thread2 auch lock_a zu erhalten, was offenbar misslingt, weil ihn in der Zwischenzeit thread1 gekriegt hat. thread2 wird also blockieren. thread1 läuft weiter und versucht, lock_b zu erhalten, was ebenfalls misslingt, da thread2 ihn ja noch nicht zurückgegeben hat. Also blockiert auch thread1 und damit das ganze Programm. Sinnigerweise nennt man diese Situation einen Deadlock. (Wenn du die beiden auskommentierten Zeilen mit sleep(1) aktivierst, so ergibt sich immer ein Deadlock. Überlege warum.)

Wie du siehst, treten Deadlocks dann auf, wenn zwei Threads thread1 und thread2 auf zwei gemeinsame Ressourcen a und b angewiesen sind und diese einzeln blockieren. Dadurch kann es geschehen, dass thread2 auf lock_a und thread1 auf  lock_b wartet und damit beide blockiert sind, sodass sie die Locks auch nie mehr freigegeben werden.

Um Deadlocks zu vermeiden, solltest du dich deshalb an folgende Regel halten:

Gemeinsame Ressourcen sollten wenn immer möglich mit einem einzigen Lock geschützt werden. Zudem muss gewährleistet sein, dass der Lock auch sicher wieder zurückgegeben wird.

THREADSICHER UND ATOMAR

Sind mehrere Threads im Spiel, so weiss man als Programmierer nie so genau, zu welchem Zeitpunkt oder an welcher Stelle des Codes die Umschaltung der Threads erfolgt. Wie du bereits vorher gesehen hast, kann dies dann zu unerwartetem und falschem Verhalten führen, wenn die Threads mit denselben Ressourcen arbeiten. Dies ist insbesondere dann der Fall ist, wenn mehrere Threads ein Bildschirmfenster verändern. Wenn du also in einem Callback einen eigenen Worker-Thread erzeugst, um länger laufenden Code auszuführen, so musst du fast immer damit rechnen, dass es ein Chaos geben kann. Im vorhergehenden Programm hast du dies vermieden, indem du während dem Callback die Buttons inaktiviert hast.

Durch besondere Vorsichtsmassnahmen kann man erreichen, dass mehrere Threads denselben Code ausführen können, ohne sich in die Quere zu kommen. Solchen Code nennt man threadsicher (threadsafe). Es ist eine Kunst, threadsicheren Code zu schreiben, der sich also in einer Umgebung mit mehreren Threads konfliktlos verwenden lässt [mehr.. Führt ein Thread eine Funktion aus und wird dann von einem anderen Thread unterbrochen,
der dieselbe Funktion aufruft, so nennt man dies Reentrance.
Eine threadsichere Funktion kann problemlos reentrant aufgerufen werden].

Es gibt wenige threadsichere Bibliotheken, da diese weniger Performat sind und dei Gefahr von Deadlocks besteht. Wie du oben erlebt hast, ist die GPanel-Bibliothek nicht threadsicher, die Turtlegrafik hingegen schon. Du kannst also mehrere Turtles mit mehreren Threads quasi-gleichzeitig bewegen. In deinem Programm entsteht bei jedem Mausklick ein neuer Thread, der an der Mausposition eine neue Turtle erzeugt. Diese zeichnet selbsttändig einen Stern und füllt ihn nachher aus.

from gturtle import *
import thread

def onMousePressed(event):
#    createStar(event)
    thread.start_new_thread(createStar, (event,))

def createStar(event):
    t = Turtle(tf)
    x = t.toTurtleX(event.getX())
    y = t.toTurtleY(event.getY())
    t.setPos(x, y)
    t.startPath()
    repeat 9:
        t.forward(100)
        t.right(160)
    t.fillPath()        
     
tf = TurtleFrame(mousePressed = onMousePressed)
tf.setTitle("Klick To Create A Working Turtle")

MEMO

AUFGABE