21.10.2011 - Aufgabe 1

  • Mein Versuch:
    Idee dahinter:
    In A prüft cnt ob B und C den Datensatz bereits gelesen haben. Wenn nicht, wird nicht geschrieben.
    In B und C wird nur gelesen, wenn cnt jeweils kleiner als 2 ist, damit genau zwei mal der Datensatz gelesen wird. Damit B und C jeweils genau ein Mal liest, werden die zwei Semaphoren readBDone und readCDone so verwendet, dass die zugehörige V-Operation jeweils in der Prozedur angewendet wird.
    Meinungen?


    [TABLE='class: outer_border, width: 800']

    [tr]


    [td]
    Code
    1. struct semaphore
    2. {
    3. int count;
    4. queuType queue;
    5. }
    [/td]


    [td][/td]


    [/tr]


    [tr]


    [td][/td]


    [td][/td]


    [/tr]


    [tr]


    [td][/td]


    [td]
    Code
    1. void semSignal(semaphore s)
    2. {
    3. s.count++;
    4. if (s.count <= 0)
    5. {
    6. /* remove process P from s.queue */
    7. /* place process P on ready list */
    8. }
    9. }
    [/td]


    [/tr]


    [/TABLE]



    [TABLE='class: outer_border, width: 800']

    [tr]


    [td]
    Code
    1. init(wsem,1);
    2. init(s,1);
    3. init(readBDone,1);
    4. init(readCDone,1);
    5. int cnt = 0;
    [/td]


    [td][/td]


    [td][/td]


    [/tr]


    [tr]


    [td][/td]


    [td][/td]


    [td][/td]


    [/tr]


    [tr]


    [td][/td]


    [td][/td]


    [td][/td]


    [/tr]


    [/TABLE]

    Edited 2 times, last by bbking78: 21.10.2011 - statt 21.10.2015 ().

  • Woah, da ist jemand in die Zukunft gereist! :shiner:

    “Fantasy is hardly an escape from reality. It's a way of understanding it.” - Lloyd Alexander


    “The more I see of what you call civilization, the more highly I think of what you call savagery!” - Robert E. Howard, King Kull

    "Kapitalismus heißt: Man kauft Dinge die man nicht braucht, von Geld, das man nicht hat, um Menschen zu beeindrucken, die man nicht leiden kann." - Volker Pispers

  • Schon. Wennst mir sagst zu welcher Prüfung das gehört, dann würd ichs mir noch anschauen :)


    ah, genau in dem moment editiert.. ich schaus mir dann gleich an.

    “Fantasy is hardly an escape from reality. It's a way of understanding it.” - Lloyd Alexander


    “The more I see of what you call civilization, the more highly I think of what you call savagery!” - Robert E. Howard, King Kull

    "Kapitalismus heißt: Man kauft Dinge die man nicht braucht, von Geld, das man nicht hat, um Menschen zu beeindrucken, die man nicht leiden kann." - Volker Pispers

  • So, ich hab das ein wenig anders.
    Also zum ersten Punkt gibts nichts zu sagen, außer, dass ich glaube, dass mit "initialisierung" die init(semaphore, value) methode gemeint ist und nicht das struct.


    Zum zweiten Punkt: Den hab ich so


    Initialisierungen

    Code
    1. init(mutex, 1); // Zugriff auf shm
    2. init(newData, 0); // Gibt es neue Daten? (Annahme: Am Anfang gibt es keine neuen Daten, d.h. Prozess A beginnt)
    3. init (isRead, 1); // Wurden die Daten gelesen? (Annahme: Am Anfang bit es keine [neuen] Daten, d.h. ich betrachte diese als gelesen)
    4. init(countLock, 1); // Ein lock für unseren counter
    5. var/int count = 0;


    A

    Code
    1. while(true)
    2. {
    3. P(isRead); // Prüfen ob die Daten bereits gelesen wurden
    4. P(mutex);
    5. // write data
    6. V(newData); // Informiere die anderen Threads, dass es neue Daten zu lesen gibt
    7. V(mutex); // Gib den shared memory frei
    8. }


    Prozess B und C sind analog


    Denke deines sollte auch stimmen, aber ich bin bei Semaphoren nicht 100% sattelfest.

    “Fantasy is hardly an escape from reality. It's a way of understanding it.” - Lloyd Alexander


    “The more I see of what you call civilization, the more highly I think of what you call savagery!” - Robert E. Howard, King Kull

    "Kapitalismus heißt: Man kauft Dinge die man nicht braucht, von Geld, das man nicht hat, um Menschen zu beeindrucken, die man nicht leiden kann." - Volker Pispers

    Edited once, last by Vendredi ().

  • 2 Anmerkungen zu deiner Lösung:
    - laut Angabe geht es um zyklische Prozesse, also das while rundherum nicht vergessen! Und die count Variable sollte auch zurückgesetzt oder mit Modulo getestet werden
    - ich glaube, Prozess B oder C kann die gleichen Daten 2x hintereinander lesen, wenn es blöd hergeht

  • 2 Anmerkungen zu deiner Lösung:
    - laut Angabe geht es um zyklische Prozesse, also das while rundherum nicht vergessen! Und die count Variable sollte auch zurückgesetzt oder mit Modulo getestet werden


    Recht hast du, danke!



    - ich glaube, Prozess B oder C kann die gleichen Daten 2x hintereinander lesen, wenn es blöd hergeht


    Ach, du meinst, wenn process data zu schnell ist und new Data ja schon wieder auf 1 steht (durch den jeweils anderen Prozess und die Weitergabe des "Locks")... hm, hm... was mach ich da ...


    (Und genau deshalb mag ich die Semaphoren Beispiele nicht. Abgesehen davon, dass sie im [allgemeinen] Schwierigkeitsgrad schwanken wie ein Besoffener im Vollrausch wenn Weihnachten, Ostern, Geburtstag und Fasching auf einen Tag fielen :X)

    “Fantasy is hardly an escape from reality. It's a way of understanding it.” - Lloyd Alexander


    “The more I see of what you call civilization, the more highly I think of what you call savagery!” - Robert E. Howard, King Kull

    "Kapitalismus heißt: Man kauft Dinge die man nicht braucht, von Geld, das man nicht hat, um Menschen zu beeindrucken, die man nicht leiden kann." - Volker Pispers


  • Ach, du meinst, wenn process data zu schnell ist und new Data ja schon wieder auf 1 steht (durch den jeweils anderen Prozess und die Weitergabe des "Locks")... hm, hm... was mach ich da ...


    Ich habs so überlegt: wenn zB B läuft, die Daten liest, sie schnell verarbeitet und der Scheduler B noch nicht unterbricht, dann könnte ja wieder B drankommen und wieder die Daten lesen, während C sie nicht mitbekommt....



    (Und genau deshalb mag ich die Semaphoren Beispiele nicht. Abgesehen davon, dass sie im [allgemeinen] Schwierigkeitsgrad schwanken wie ein Besoffener im Vollrausch wenn Weihnachten, Ostern, Geburtstag und Fasching auf einen Tag fielen :X)


    Den Vergleich hätte ich nicht schöner formulieren können....:D:D

  • Aufgabe 2:
    Banker's Algorithm:
    [TABLE='width: 800']

    [tr]


    [td]

    A =
    \begin{pmatrix}
    0 & 0 & 0 & 0\\
    1 & 2 & 1 & 1\\
    2 & 0 & 1 & 1\\
    1 & 1 & 0 & 3\\
    0 & 1 & 3 & 0\\
    \end{pmatrix}

    [/td]


    [td]

    C =
    \begin{pmatrix}
    2 & 0 & 1 & 0\\
    1 & 0 & 3 & 0\\
    1 & 0 & 0 & 0\\
    1 & 0 & 0 & 1\\
    1 & 2 & 1 & 1\\
    \end{pmatrix}

    [/td]


    [td]

    N = C - A =
    \begin{pmatrix}
    2 & 0 & 1 & 0\\
    0 & -2 & 2 & -1\\
    -1 & 0 & -1 & -1\\
    0 & -1 & 0 & -2\\
    1 & 1 & -2 & 1\\
    \end{pmatrix}

    [/td]


    [td]

    R = (6,4,6,5)
    V = (2,0,1,0)

    [/td]


    [/tr]


    [/TABLE]


    Da Nij <= Vj gelten muss, kann gesagt werden, dass P2 und P5 ein Deadlock verursachen

    Deadlock detection algorithm:


    [TABLE='width: 800']

    [tr]


    [td]

    Q =
    \begin{pmatrix}
    2 & 0 & 1 & 0\\
    1 & 0 & 3 & 0\\
    1 & 0 & 0 & 0\\
    1 & 0 & 0 & 1\\
    1 & 2 & 1 & 1\\
    \end{pmatrix}

    [/td]


    [td]

    A =
    \begin{pmatrix}
    0 & 0 & 0 & 0\\
    1 & 2 & 1 & 1\\
    2 & 0 & 1 & 1\\
    1 & 1 & 0 & 3\\
    0 & 1 & 3 & 0\\
    \end{pmatrix}

    [/td]


    [td]

    R = (6,4,6,5)
    V = W = (2,0,1,0)

    [/td]


    [td][/td]


    [/tr]


    [/TABLE]


    Beginne mit P1: Q1j (2,0,1,0) <= W(2,0,1,0) bzw. P1 hat lauter 0er, kann also markiert werden
    [ W = W + Aij = (2,0,1,0) + (0,0,0,0) = (2,0,1,0) ]


    Für P2 gilt Q2j <= W nicht, wird nicht markiert, weiterspringen


    P3: (1,0,0,0) <= (2,0,1,0) ist wahr, P3 markieren und
    W = W + (2,0,1,1) = (4,0,2,1)


    P4: (1,0,0,1) <= (4,0,2,1) ist wahr, P4 markieren und
    W = W + (1,1,0,3) = (5,1,2,4)


    P5: Q5j <= W ist nicht wahr, nicht markieren, da keine Prozesse mehr über, abbrechen


    P2 und P5 sind nicht markiert, daher befinden sie sich im Deadlock.

  • Hi, bereite mich gerade für die nächste Prüfung vor und denke, dass beide eurer Lösungen falsch sind, oder ich steh ganz auf der Leitung :)


    BBking78 - Lösung:
    Finde gleich mehrere Dinge, die keinen Sinn machen:

    • A schreibt erst, wenn count 2 ist. B und C erhöhen count jeweils um 1, lesen aber gleich die Daten (BEVOR A sie geschrieben hat), da wsem mit 1 initialisiert wurde.
    • Da readBdone und readCdone mit 1 initialisiert wurden und das P(read(B/C)done) erst nach dem Lesen geschieht, kann es passieren, dass B oder C erst blocken, nachdem sie 2 Mal gelesen haben (zusätzlich hat bis dahin A u.U. noch gar nicht geschrieben). Das heißt, B liest 2 Mal und wenn dann A ausgeführt wird, schreibt er ohne das C gelesen hat.


    Verstehe ich das richtig?


    Eine korrekte Lösung schaut m.E. folgendermaßen aus, bitte korrigieren, falls ich falsch liegen sollte:


    init(bRead,1): B hat fertig gelesen, Anfangswert 1, damit A als erster schreibt.
    init(cRead,1): C hat fertig gelesen, analog zu bRead
    init(newB,0): Neue Daten für B sind verfügbar, Anfangs 0, damit B nicht liest, bevor was verfügbar ist
    init(newC,0): Neue Daten für C, analog zu newB


    A:
    while(true) {
    prepare data;
    P(bRead); // Wird anfänglich passiert, da bRead mit 1 initialisiert
    P(cRead); // Ebenso
    writeM(data); // Damit A schreiben kann, müssen also nach dem 1 Durchlauf bRead und cRead freigegeben worden sein
    signal(newB); // Erlaubt B zu lesen
    signal(newC); // Ebenso für C
    }


    B:
    while(true) {
    wait(newB); // wird blocken, bis A geschrieben hat
    readM();
    signal(bRead); // Erlaubt A zu lesen
    use data; // Erst nach dem signal, damit A schon schreiben kann, während die Daten verwendet werden
    }


    C:
    while(true) {
    wait(newC);
    readM();
    signal(cRead);
    use data;
    }


    Somit:

    • A kann nur 1 Mal schreiben, bis B und C gelesen haben
    • B und C können nicht lesen, bevor A geschrieben hat
    • B und C können nur jeweils GENAU 1 Mal lesen, bis A das nächste Mal schreibt.


    Macht das so Sinn?

  • Bonusfrage zu meiner Lösung:


    Wenn gefragt ist, dass B und C nicht gleichzeitig lesen können sollen, reicht ein mutex init(mutex,1) um die lese-Anweisungen von B und C, sodass:


    ...
    P(mutex);
    readM();
    V(mutex);
    ...


    Seht ihr hier ein Problem?