Dieses Dokument war ursprnglich eine E-Mail an Jochen Streicher, in der ich (Daniel) den Algorithmus fr das Priorittsvererbungsprotokoll bei der feingranularen Synchronisation diskutiere. Vorraussetzung ist ein IRQ-Privilegebenenkonzept (wie beim TriCore).

============================================


Hi Jochen,

Ich glaube, ich habe das kritische Szenario gefunden. Es tritt auf, wenn ein Thread blockiert auf einer Ressource, deren Besitzer ein ebenfalls blockierter Thread ist:


declarations:

<t>hreads:  T, I1, I2, I3
<r>essources:   A, B

actions:    <t> ent[er] <r>, <t> lea[ve] <r>, <t> terminates
facts:      <t> own[S] <r>, <t> wait[s] <r>, h[ighest] = <t>, a[ctive] = <t>

a[ctive]  verweist auf den zuletzt gedispachten Thread, also den Thread, der gerade den Prozessor hat.
h[ighest] verweist auf den Thread mit der hchsten Prioritt, also indirekt auf die gerade aktive Priorittsebene. Dem Priorittsvererbungsprotokoll zur Folge ist immer entweder h=a oder h arbeitet "im Auftrag" von h, d.h. belegt gerade eine Ressource, die a (transitiv) bentigt um weiterzuarbeiten.     


[event  actions ==> resulting facts]
        
start   T ent B ==> - own A; T own B; h=a=T
irq1    I1 ent A; I1 ent B ==> I1 own A; T own B; I1 wait B; h=I1; a=T
irq2    I2 ent B ==> I1 own A; T own B; I2, I1 wait B; h=I2; a=T
irq3    I3 ent A ==> ???

An dieser Stelle haben wir jetzt das Problem, da ein Dispatch auf den Besitzer von A (I1) nicht unbedingt die gewuenschte Wirkung hat, da I1 ja selber wartet.

Ich glaube, an dieser Stelle wuerde tatsaechlich ein re-enter Sinn machen. Und zwar in dem Sinne, dass I1 geweckt wird, sich aus der Warteliste entfernt (!) und an oberster Stelle wieder eintraegt. Damit waere naemlich auch garantiert, dass der hoechstpriore wartende Thread immer ganz oben steht, wodurch sichergestellt wird das es zu keiner Prioritaetsumkehr kommt.

So koennte es dann weiter gehen:

[event  actions ==> resulting facts]

irq3    I3 ent A ==> I1 own A; T own B; I3 wait A; I1, I2 wait B; 
                     h=I3; a=I1
        I1 ent B again ==> I1 own A; T own B; I1, I2 wait B; I3 wait A
                     h=I3; a=T
        T lea B ==> I1 own A, B; I2 wait B; I3 wait A; h=I3; a=I1
        I1 lea B ==> ???

An dieser Stelle gibt es das naechste Problem. In der Warteschlange fuer B steckt noch I2 - nur duerfen wir den nicht aktivieren, da wir ja im Auftrag von I3 arbeiten waerend I2 das nicht tut. Nur ist das nicht so ohne weiteres ersichtlich. Vorschlag: Beim Verlassen eines kritischen Gebiets wird der Stab nur dann an einen wartenden Thread weitergegeben, wenn dieser nicht bereits gewartet hat als wir das kritische Gebiet betreten haben. Mit anderen Worten: Nur ein "neuerer" Wartender kann eine (indirekt) hoehere Prioritaet haben als wir. Dadurch, dass man beim re-enter wieder oben auf den Stapel kommt, sollte das auch bei geschachtelten Wartezyklen funktionieren.

[event  actions ==> resulting facts]

        I1 lea B ==> I1 own A; - own B; I2 wait B; I3 wait A; h=I3; a=I1
        I1 lea A ==> I3 own A; - own B; I2 wait B; h=I3; a=I3
        I3 lea A ==> - own A; - own B; I2 wait B; h=I3; a=I3
        I3 terminates ==> (as above); h=a=I2
        I2 ent B ==> - own A; I2 own B; h=a=I2
        I2 lea B; I2 terminates ==> - own A, B; h=a=I1
        I1 terminates ==> - own A, B; h=a=T
        T leaves kernel
