Ü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

• Selektive Kommunikation (“select”)

• Mutierbare Variable

• Set signal once

• Programmspuren

• Dining philosophers - Optimistic concurrency control

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?

Vergleich Mutexes in Go versus C Pthreads

• Go Mutexes verhalten sich wie Semaphoren

• Unlock ohne ein vorheriges lock führt in Go zum Absturz. Für C Pthreads ist das Verhalten nicht definiert (d.h. Absturz kann passieren).

• Go unterstützt auch “Reader-Writer” Locks

Dazu folgende Programm in Go und C Pthreads

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"
}

Selektive Kommunikation (“select”)

Kompletter Programmcode findet sich hier

Aufgabe 1

Betrachte folgenden Programmtext.

x := make(chan string)
    y := make(chan string)

    go func() {
        select {
        case x <- "X":
        case a := <-y:
            fmt.Printf("%s", a)
        }
    }()

    select {
    case b := <-x:
        fmt.Printf("%s", b)
    case y <- "Y":

    }

Was sind mögliche Ausgaben?

Aufgabe 2

Betrachte folgende Variante.

x := make(chan string)
    y := make(chan string)

    go func() {
        select {
        case a := <-y:
            fmt.Printf("%s", a)
        case x <- "X":
        case x <- "X":
        case x <- "X":
        case x <- "X":
        case x <- "X":
        }
    }()

    select {
    case b := <-x:
        fmt.Printf("%s", b)
    case y <- "Y":

    }

Was ändert sich (im Vergleich zu vorheriger Aufgabe) falls der Programmtext mehrfach ausgeführt wird?

Aufgabe 3

Betrachte

    ch1 := make(chan string)
    ch2 := make(chan string)

    go func() {
        for {
            ch1 <- "tick"
        }
    }()
    go func() {
        for {
            ch2 <- "tock"
        }
    }()

    for i := 0; i < 5; i++ {
        select {
        case msg := <-ch1:
            fmt.Println("Received from ch1:", msg)
        case msg := <-ch2:
            fmt.Println("Received from ch2:", msg)
        }
    }

• Führe die Schleife mehrmals aus – erhalten wir immer die gleichn Ausgaben?

• Füge time.Sleep()-Aufrufe hinzu, um unvorhersehbare Verzögerungen zu simulieren.

• Erweitere die Schleife mit einem default: case, um die Schleife nicht blockierend zu machen

Mutierbare Variable

Wir betrachten die Implementierung einer mutierbaren Variable (“MVar”). Aufgabenbeschreibung findet sich unten.

Zuerst spezifizieren wir die Schnittstelle und das Verhalten einer MVar. Eine MVar ist entweder leer oder voll. Funktionalität und erwartetes Verhalten sind wie folgt.

type MVar[T any] chan T

func newMVar[T any]() MVar[T]

func takeMVar[T any](m MVar[T]) T

func putMVar[T any](m MVar[T], x T)

func tryTakeMVar[T any](m MVar[T]) (r T, b bool)

func tryPutMVar[T any](m MVar[T], x T) bool

• Wir verwenden Generics in Go. Im Gegensatz zu Java, muss immer eine Typbound (any entspricht Object) angegeben werden.

• newMVar liefert eine initial (leere) MVar.

• takeMvar liefert den gespeicherten Wert. Falls die MVar leer, blockiert die Operation. Ansonsten ändert sich der MVar Zustand von voll auf leer.

• putMvar speichert den Wert. Falls die MVar voll, blockiert die Operation. Ansonsten ändert sich der MVar Zustand von leer auf voll.

• tryTakeMVar und tryPutMVar sind nicht blockierende Varianten.

Hier ist ein Test Programm mit einer Ausgabe

func test() {
    m := newMVar[string]()

    go func() {
        putMVar(m, "A")
        fmt.Printf("putMVar A  ")
    }()

    go func() {
        b := tryPutMVar(m, "B")
        fmt.Printf("tryPutMVar B = %t  ", b)
    }()

    go func() {
        x := takeMVar(m)
        fmt.Printf("takeMVar %s  ", x)
    }()

    go func() {
        x, b := tryTakeMVar(m)
        if b {
            fmt.Printf("tryTakeMVar %s  ", x)
        } else {
            fmt.Printf("tryTakeMVar no luck  ")
        }
    }()

    time.Sleep(time.Second)
}

Mögliche Ausgabe ist

tryTakeMVar no luck  tryPutMVar B = true  putMVar A  takeMVar B

Aufgabe 1

Implementiere MVar. Hinweis: Verwende einen gepufferten Kanal.

Eine Musterlösung findet sich hier.

Aufgabe 2

Anstatt newMVar verwenden wir

func newAndSetMVar[T any](T) MVar[T]

Die MVar ist also initial schon voll.

Hier eine Implementierung mittels eines ungepufferten Kanals.

func newAndSetMVar[T any](x T) MVar[T] {
    c := make(chan T)
    go func() {
        c <- x
    }()
    return c
}

Implementierung von takeMVar und putMVar sind unverändert.

Leider hat diese Implementierung Probleme. Welche? Finde Erklärungen mittels Beispielen.

Erklärungsvorschläge finden sich hier.

Set signal once

Your task is to implement a form of “signal/wait” concurrency primitive. In terms of Go, this primitive can be described via the following interface (= collection of methods). Below we give a description. Some program code is provided here.

type SigI interface {
    signal() bool
    wait()
}

• We assume that a signal can only be set once

• The first signal method call that successfully sets the signal yields true

• All subsequent signal method call yield false

• A wait method call blocks unless the signal is set

• Once a signal is set all waiting method calls unblock

Here is a simple example.

func ex1(s SigI) {

    go func() {
        b := s.signal()
        fmt.Printf("\nA: Signaling done %t", b)
    }()

    go func() {
        s.wait()
        fmt.Println("\nC: Waiting done")
    }()

    go func() {
        b := s.signal()
        fmt.Printf("\nB:Signaling done %t", b)
    }()

    go func() {
        s.wait()
        fmt.Println("\nD: Waiting done")
    }()

    time.Sleep(time.Second)
}

Naive implementation

Here is a simple implementation of the SigI interface.

type Sig struct {
    sig chan bool
}

func newSig() Sig {
    c := make(chan bool, 1)
    c <- false // false = signal not set yet
    return Sig{sig: c}

}

func (s Sig) signal() bool {
    if !<-s.sig {
        s.sig <- true
        return true
    }

    s.sig <- true
    return false

}

// True = had to wait.
func (s Sig) wait() {
    if <-s.sig {
        // Signal already set.
        s.sig <- true
        return
    }

    s.sig <- false
    stop := false
    // Spinning loop where we repeatedly check if signal is set.
    for !stop {
        time.Sleep(50 * time.Millisecond)
        if <-s.sig {
            s.sig <- true
            stop = true
        } else {
            s.sig <- false
            // continue
        }

    }
}

• We use a buffered channel of size one to represent the signal.

• Initially, the signal is not set. This is represented by the buffer value false

• We treat channel operations receive/send as Mutex operations lock/unlock to guarantee exclusive access to the signal.

• The wait method uses a spinning loop to check if the signal is set.

Your tasks

Task 1

Play around with the examples provided and create your own examples.

Task 2

A spinning loop at the user code level is wasteful. To avoid spinning enrich the signal data type with a queue of waiting method calls.

Programmspuren

Wir betrachten die Instrumentierung von send/receive als auch lock/unlock Operationen zwecks Generierung von Programmspuren. Vollständiger Programmcode mit weiteren Erklärungen findet sich hier.

Instrumentierung von send + receive

Betrachte folgenden Programmtext.

func snd(tid string, ch chan int) {
    fmt.Printf("\nThread %s pre(ch!)", tid)
    ch <- 1
    fmt.Printf("\nThread %s post(ch!)", tid)
}

func rcv(tid string, ch chan int) {
    fmt.Printf("\nThread %s pre(ch?)", tid)
    <-ch
    fmt.Printf("\nThread %s post(ch?)", tid)

}

func test1() {
    var ch chan int = make(chan int)
    go rcv("R1", ch) // R1
    go snd("S1", ch) // S1
    go snd("S2", ch) // S2
    go rcv("R3", ch) // R3
    rcv("R2", ch)    // R2

}

Die Ausführung von test1() liefert folgende Programmspur (aka Trace).

Thread R2 pre(ch?)
Thread R3 pre(ch?)
Thread R1 pre(ch?)
Thread S1 pre(ch!)
Thread S1 post(ch!)
Thread R2 post(ch?)
Thread S2 pre(ch!)
Thread S2 post(ch!)
Thread R3 post(ch?)

Wir bezeichnen obige Programmspur als Trace A.

Aufgabe 1

Gebe eine Tabellendarstellung der Programmspur.

Aufgabe 2

Betrachte folgende Programmspur (dargestellt als Tabelle).

   R1        R2       R3       S1         S2

1.          pre(ch?)
2.                             pre(ch!)
3.                             post(ch!)
4.          post(ch?)
5.                    pre(ch?)
6. pre(ch?)
7.                                       pre(ch!)
8.                                       post(ch!)
9.                    post(ch?)

Wir bezeichnen obige Programmspur als Trace B. Gibt es eine Beziehung zwischen Trace B und Trace A? [Hinweis: Kann Trace B aus Trace A hergeleitet werden?]

Aufgabe 3

Betrachte folgende Programmspur (dargestellt als Tabelle).

   R1        R2       R3       S1         S2

1.          pre(ch?)
2.                    pre(ch?)
3. pre(ch?)
3.                             pre(ch!)
4.                             post(ch!)
5.          post(ch?)
6.                                       pre(ch!)
7.                                       post(ch!)
8. post(ch?)

Wir bezeichnen obige Programmspur als Trace C. Gibt es eine Beziehung zwischen Trace C und Trace A?

Aufgabe 4

Betrachte folgenden Programmtext.

func test2() {
    var ch chan int = make(chan int)
    go rcv("R1", ch) // R1
    snd("S1", ch)    // S1
    go rcv("R2", ch) // R2
    snd("S1", ch)    // S

}

Die Ausführung von test2() liefert folgende Programmspur (dargestellt als Tabelle).

    R1        R2        S1

1.                      pre(ch!)
2.  pre(ch?)
3.                      post(ch!)
4.                      pre(ch!)
5.           pre(ch?)
6.           post(ch?)
7.  post(ch?)
8.                      post(ch!)

Wir bezeichnen obige Programmspur als Trace D.

Beachte. Die Annahme, dass “post” des Sende Partners immer vor dem “post” des Empfangs Partners stattfindet, wird durch unsere naive “print” Instrumentierung nicht eingehalten.

Ein weiteres Problem ist, dass das “printen” des “post” Ereignisses und die entsprechende Operation nicht atomar stattfinden. Deshalb ist auch folgende Programmspur (Trace E) möglich.

    R1        R2        S1

1.                      pre(ch!)
2.  pre(ch?)
3.                      post(ch!)
4.                      pre(ch!)
5.           pre(ch?)
6.           post(ch?)
7.  post(ch?)
8.                      post(ch!)

“post” in R1 findet nach “post” in R2 statt. Obiger Ablauf entspricht, aber nicht dem tatsaechlichem Programmverhalten. Dies kann passieren (und via “sleep” simuliert werden).

Aufgabe. Füge “sleep” Operationen in den Programmtext ein, um die Ausgabe von Trace E zu erzwingen.

Instrumentierung von lock + unlock

Betrachte folgenden Programmtext. Unlock ist eine nicht-blockierende Operation. Deshalb gibt es ein “pre” Event. Für Lock gibt es “pre” und “post” Events. In unserer Instrumentierung ignorieren wir aber diese Unterscheidung und speichern für jede Lock Operation nur ein Event im Trace.

var m sync.Mutex

func lock(id string) {
    fmt.Printf("\nThread %s lock", id)
    m.Lock()
}

func unlock(id string) {
    fmt.Printf("\nThread %s unlock", id)
    m.Unlock()

}

func ex1() {
    t1 := "T1"
    t2 := "T2"
    t3 := "T3"

    go func() {
        lock(t2)
        unlock(t2)
    }()

    go func() {
        lock(t3)
        unlock(t3)
    }()

    lock(t1)
    unlock(t1)

}

Die Ausführung von ex1() liefert folgende Programmspur (aka Trace).

Thread T1 lock
Thread T1 unlock
Thread T3 lock
Thread T3 unlock
Thread T2 lock
Thread T2 unlock

Wir bezeichnen obige Programmspur als Trace F.

Aufgabe 5

Gebe eine Tabellendarstellung der Programmspur.

Aufgabe 6

Die Instrumentierung hat ein Problem. Es kann zu Programmspuren kommen, die nicht einem tatsächlichen Programmablauf entsprechen. Liefere ein konkretes Beispiel und schlage eine Lösung des Problems vor.

Dining philosophers - Optimistic concurrency control

Full program code can be found here.

Dining philosophers that may deadlock

Here is a variant of the dinining philosophers example where we use an unbuffered channel to represent the set of forks.

func grab_fork() {
    <-forks
}

func release_fork() {
    go func() {
        forks <- 1
    }()
}

func philo(id string) {

    for {
        grab_fork()
        grab_fork()
        fmt.Printf("%s eats \n", id)
        time.Sleep(1 * 1e9)
        release_fork()
        release_fork()

        time.Sleep(time.Second) // think

    }

}

func test_philo() {
    forks = make(chan int)
    release_fork()
    release_fork()
    release_fork()
    go philo("A")
    go philo("B")
    philo("C")
}

Task 1

Run the code (execute test_philo()) and observe what happens. Does a deadlock arise? Is it possible that we run into a deadlock? How could we provoke a deadlocking situation?

Task 2

The release_fork function executes fork <- 1 in some helper thread. Is this necessary?

Could we execute <-forks in function grab_fork in some helper thread?

Grabbing two forks atomically

Two avoid deadlocking situations, we wish that each philosopher grabs two forks atomically. We use here atomically in the sense known from database transactions. That is, either we can grab two forks or none at all (aka “all or nothing”).

Here is an attempt to guarantee the “atomic” property by using some global lock.

var global_lock sync.Mutex

func grab2forks_atomically() {
    global_lock.Lock()
    grab_fork()
    grab_fork()
    global_lock.Unlock()
}

func philo_atomic_global_lock(id string) {

    for {
        grab2forks_atomically()
        fmt.Printf("%s eats \n", id)
        time.Sleep(1 * 1e9)
        release_fork()
        release_fork()

        time.Sleep(time.Second) // think

    }

}

func test_philo_atomic_global_lock() {
    forks = make(chan int)
    release_fork()
    release_fork()
    release_fork()
    go philo_atomic_global_lock("A")
    go philo_atomic_global_lock("B")
    philo_atomic_global_lock("C")
}

Task 3

Can a deadlock still arise? Provide some detailed explanation. Are there still any issues?

Trying to optimistically grab two works

Here is another attempt. We use select to optimistically grab two works.If we get stuck, for example failing to secure the second fork, we rollback.

func grab2forks_optimistically() {
ROLLBACK:
    select {
    case <-forks:
        select {
        case <-forks:
        default:
            release_fork()
            time.Sleep(20 * time.Millisecond)
            goto ROLLBACK
        }

    default:
        time.Sleep(20 * time.Millisecond)
        goto ROLLBACK
    }

}

func philo_optimistic(id string) {

    for {
        grab2forks_optimistically()
        fmt.Printf("%s eats \n", id)
        time.Sleep(1 * 1e9)
        release_fork()
        release_fork()

        time.Sleep(time.Second) // think

    }

}

func test_philo_optimistic() {
    forks = make(chan int)
    release_fork()
    release_fork()
    release_fork()
    go philo_optimistic("A")
    go philo_optimistic("B")
    philo_optimistic("C")
}

Task 4

Discuss the pros and cons of the pessimistic and optimistic solution to avoid deadlocks.