Übungsaufgaben (“exercises”)

Martin Sulzmann

Übersicht

*Lehrunterlagen auf Deutsch und Englisch. Daran orientieren sich die Aufgabenbeschreibungen (entweder Deutsch oder Englisch).

Übungsaufgaben zu folgenden Themen.

Multi-Thread Scheduling
Einfache Go Programme
Mutexes in Go
Semaphores in Go
Channels in Go

Multi-Thread Scheduling

Betrachte

package main

import "fmt"
import "time"

func thread(s string) {
    for {
        fmt.Print(s)
        time.Sleep(1 * 1e9)
    }
}

func main() {

    go thread("A")
    go thread("B")
    thread("C")
}

Aufgabe 1

Gebe einen zustandsbasierte Ausführungspfad. Verwende dazu die Notation beschrieben hier.

Die ersten Schritte sind wie folgt.

    (Main.Running)
--> (Main.Running, A.Waiting)
--> (Main.Running, A.Waiting, B.Waiting)
--> ...

Aufgabe 2

Wieviele verschiedene Ausführungspfade gibt es?

Wieviele verschieden Zustände gibt es?

Aufgabe 3

Welche go tools gibt es um das Programmverhalten (Zustände und Ausführungspfade) darzustellen?

Einfache Go Programme

Betrachte

package main

import (
    "fmt"
    "math/rand"
)

type kind int

const (
    HIGH  kind = 1
    LOW   kind = 2
    LUCKY kind = 3
)

func main() {
    var k kind
    i := rand.Intn(100)

    if i == 55 {
        k = LUCKY
    }
    if i > 55 {
        k = HIGH
    }
    if i < 55 {
        k = LOW
    }

    print(k)

}

func print(k kind) {
    if k == LUCKY {
        fmt.Println("lucky")
    } else if k == HIGH {
        fmt.Println("high")
    } else {
        fmt.Println("low")
    }

}

Aufgabe 1

Liste die Unterschiede/Gemeinsamkeiten zu bekannten Sprachen (z.B. C, Java).

Aufgabe 2

Schreibe das Program um. Anstatt if-then-else verwende switch-case.

Gibt es Unterschiede zu bekannten Sprachen (z.B. C, Java)?

Aufgabe 3

Schreibe das Program um. Anstatt der Funktion func print(k kind verwende eine anonyme Funktion (in main).

Mutexes in Go

Aufgabe. Betrachten sie folgenden Beispiele und wiederholen sie das bekannte Wissen über Mutexe im Kontext von Go.

Alle Beispiele finden sich auch hier

Go unterstützt Mutex Operationen. Hier ist ein Beispiel.

func ex1() {
    var m sync.Mutex
    var s string
    race := true

    go func() {
        m.Lock()
        if race {
            s = "Hi"
            race = false
        }

        m.Unlock()

    }()

    go func() {
        m.Lock()
        if race {
            s = "Ho"
            race = false
        }
        m.Unlock()

    }()

    time.Sleep(time.Second)
    fmt.Printf("%s", s)

}

Auf einem Mutex Objekt werden die bekannten Lock und Unlock Methoden ausgeführt
In obigen Beispiel wird mittels des Mutex m exklusiver Zugriff auf die Programmvariablen race und s garantiert
Es findet quasi ein Wettrennen zwischen den zwei Goroutinen statt
Die Ausgabe ist entweder “Hi” oder “Ho”

Fallstrick - Verwende “call-by-references” für Mutexe

Go verwendet “call-by-value” (wie auch C).

Falls ein Mutex Object via “call-by-value” übergeben wird eine Kopie erstellt (quasi eine neues Mutex Objekt). Deshalb sollte in der Regel “call-by-reference” emuliert via Zeiger verwendet werden.

Betrachte folgenden Programmcode. Eine Variante von obigem Beispiel. Wir verwenden eine anonyme Funktion, um über die gemeinsamen Programmteile zu abstrahieren.

func ex2() {
    var m sync.Mutex
    var s string
    race := true

    racer := func(x sync.Mutex, y string) { // Kopie wird erstellt!
        x.Lock()
        if race {
            s = y
            race = false
        }
        x.Unlock()

    }

    go racer(m, "Hi")

    go racer(m, "Ho")

    time.Sleep(time.Second)
    fmt.Printf("%s", s)

}

Leider gibt es ein Problem!

Da eine Kopie erstellt wurde ist ein exklusiver Zugriff nicht mehr gewährleistet
Die Problematik ist genau die gleiche wie bei C/Pthreads
Die Lösung ist die Verwendung von “call-by-reference”

In Go wird “call-by-reference” emuliert via Zeiger.

Anders wie in C sind Zeiger in Go Typsicher.

Hier ist eine weitere Variante in der das Problem gelöst wird.

func ex2b() {
    var m sync.Mutex
    var s string
    race := true

    racer := func(x *sync.Mutex, y string) { // call-by-reference via Zeiger
        x.Lock()
        if race {
            s = y
            race = false
        }
        x.Unlock()

    }

    go racer(&m, "Hi")

    go racer(&m, "Ho")

    time.Sleep(time.Second)
    fmt.Printf("%s", s)

}

Zeiger in Go entsprechen Zeigern in C
In Go gibt es keine Zeigerarithmetik (deshalb Typsichere Zeiger)
Der Go Kompiler erkennt Dereferenzierungen automatisch

In obigem Programmcode ist x ein Zeiger auf sync.Mutex.

Wir schreiben x.Lock(). Der Kompiler wandelt dies um in (*x).Lock()

Fallstrick - Deadlocks

Betrachte

func ex3() {
    var l1 sync.Mutex
    var l2 sync.Mutex

    go func() {
        l1.Lock()
        l2.Lock()
        fmt.Println("Hi")
        l2.Unlock()
        l1.Unlock()

    }()

    l2.Lock()
    // Deadlock in der Regel beobachtbar durch auskommentieren untenstehender Anweisung
    // time.Sleep(time.Second)
    l1.Lock()
    fmt.Println("Hi")
    l1.Unlock()
    l2.Unlock()

}

Zwischen den beiden Goroutinen gibt es eine zyklische Lockabhängigkeit
In einer tatsächlichen Ausführung kann dies beobachtet werden

Betrachte folgenden Programmablauf wobei wir die “main” Goroutine mit T1 bezeichnen und die “andere” Goroutine mit T2 bezeichnen.

Wir schreiben den Programmablauf als eine Sequenz von sich abwechselnden Operationen der Goroutinen T1 und T2.

Schritt 1: In T1 locken wir Mutex l1.

Schritt 2: In T2 locken wir Mutex l2.

Schritt 3: In T1 versuchen wir Mutex l2 zu locken.
           Goroutine T1 ist blockiert, da l2 in T2 gelockt wurde.

Schritt 4: In T2 verwuchen wir Mutex l1 zu locken.
           Goroutine T2 ist blockiert, l1 in T1 gelockt wurde.

==> Alle Goroutinen sind blockiert => Deadlock.

Beachte.

Der Deadlock kann muss aber nicht (immer) auftreten
Welche ihnen bekannte Verfahren gibt es um Deadlocks zu erkennen?

Semaphores in Go

Semaphoren gibt es in verschiedenen Ausprägungen. Wir betrachten hier “Bounded Semaphores” der maximalen Grösse N.

Bounded Semaphores

Initial gibt es einen Counter der 0 ist.
Die signal Operation inkrementiert den Counter
Die wait Operation dekrementiert den Counter.

Folgende Bedingung gilt:

Der Counter darf nie negativ und grösser wie N werden.

Deshalb blockiert eine wait Operation falls der Counter negative werden würde.

In unserem Fall nehmen wir an, dass die signal Operation blockiert falls der Counter grösser als N werden würde.

Eine blockierte wait Operation kann von einer signal Operation aufgeweckt werden. Z.B. signal erhöht den Counter auf 1 und dann kann die wait Operation ausgeführt werden.

Umgekehrt kann auch eine signal Operation von einer wait Operation aufgeweckt werden. Z.B. wait dekrementiert den Counter unter N und dann kann die signal Operation ausgeführt werden.

Die oben beschriebe Art von Semaphore wird nicht direkt in Go unterstützt, kann aber einfach mit Hilfe von gepufferten Channels emuliert werden.

Betrachte folgenden Programmcode. Kompletter Code findet sich hier.

type Semaphore chan int

func initSem(n int) Semaphore {
    return make(chan int, n)
}

func wait(s Semaphore) {
    <-s
}

func signal(s Semaphore) {
    s <- 1
}

func ex1() {
    s := initSem(2)

    go func() {
        fmt.Println("A waiting")
        wait(s)
        fmt.Println("A waiting over")
    }()

    go func() {
        fmt.Println("B waiting")
        wait(s)
        fmt.Println("B waiting over")
    }()

    time.Sleep(time.Second)
    fmt.Println("Set signal")
    signal(s)
    time.Sleep(time.Second)

}

Gepufferte Go Channels kurz und knapp:

make(chan int, n) liefert Channel mit Puffergrösse n
Maximal n Werte vom gleichen Typ können im Channel gespeichert werden
Einfügen eines Elements in den Channel geschieht mit der Sendeoperation s <- 1
Entfernen eines Elements aus dem Channel geschieht mit der Empfangsoperation <-s

Dadurch ergibt sich folgendes:

Die Anzahl der im Channel befindlichen Elemente repräsentiert den Counter
Die Semaphore wait Operation entspricht der Channel Empfangsoperation
Die Semaphore signal Operation entspricht der Channel Sendeoperation

Channels in Go

Programme (mit imports und main) finden sich auch hier (mit Erklaerungen).

Aufgabe 1

Was kann alles bei der Ausführung passieren?

func ex1() {
    ch := make(chan string)

    hi := func() {
        ch <- "hi"
    }

    ho := func() {
        ch <- "ho"
    }

    producer := func() {
        n := rand.Intn(20)
        for i := 0; i < n; i++ {
            if rand.Intn(30) > 15 {
                hi()
            } else {
                ho()
            }
        }
    }

    consumer := func() {
        n := rand.Intn(20)
        for i := 0; i < n; i++ {
            x := <-ch
            fmt.Printf("%s", x)
        }
    }

    go producer()
    consumer()
}

Aufgabe 2

Kleine Änderung des Programms. Was kann alles bei der Ausführung passieren?

func ex2() {
    ch := make(chan string)

    hi := func() {
        ch <- "hi"
    }

    ho := func() {
        ch <- "ho"
    }

    producer := func() {
        n := rand.Intn(20)
        for i := 0; i < n; i++ {
            if rand.Intn(30) > 15 {
                hi()
            } else {
                ho()
            }
        }
    }

    consumer := func() {
        n := rand.Intn(20)
        for i := 0; i < n; i++ {
            x := <-ch
            fmt.Printf("%s", x)
        }
    }

    // Unterschied zu ex1!
    go producer()
    go consumer()
    time.Sleep(2 * time.Second)
}

Aufgabe 3

Weitere “kleine” Änderungen, z.B. Kanal mit Puffer. Was kann alles bei der Ausführung passieren?

func ex3() {
    ch := make(chan string, 50) // Kanal mit Puffer!

    hi := func() {
        ch <- "hi"
    }

    ho := func() {
        ch <- "ho"
    }

    producer := func() {
        n := rand.Intn(20)
        for i := 0; i < n; i++ {
            if rand.Intn(30) > 15 {
                hi()
            } else {
                ho()
            }
        }
    }

    consumer := func() {
        n := rand.Intn(20)
        for i := 0; i < n; i++ {
            x := <-ch
            fmt.Printf("%s", x)
        }
    }

    // Consumer nebenlaeufig. Producer im main thread!
    go consumer()
    producer()
    time.Sleep(2 * time.Second)
    // Ohne sleep ist der producer "zu schnell"
}