cache coherence

04/12/2014 - 05:57 von Jan Bruns | Report spam
Hallo.

Ich hab da mal eine Frage zum Thema "cache coherence"
zwischen CPU Kernen: Wie verlàsslich und in welcher
Absolutheit ist eine solche denn inzwischen
üblicherweise (d.h. hier auch: low budget) gegeben?

Also Anlass zu der Frage ist eigentlich nur, daß halt
irgendwelcher Code von und bei mir nicht so
funktioniert, wie gewünscht, was nun mit ganz hoher
Wahrscheinlichkeit auch an diesem Code liegen kann.

Auf der anderen Seite ist das aber einfach ein Thema,
das neu für mich ist, so daß ich da einfach zu wenig
Erfahrungswerte bzgl. realer Hardware habe (und
im Zweifel ist letztere ja auch nur so sorgfàltig
gestaltet, daß "Fehler" nicht so auffallen).


Also ich stelle mal unten das wichtigste vom Code
dazu, dann ist das nicht so abstrakt. Die Idee war,
für eine (grosse) Sammlung von Objekten Threadlocks
zur Verfügung zu stellen, also eine "freiwillige",
Möglichkeit für Threads, jeweils exclusiv Zugriff
zu Objekten zu erhalten (mit dem Risiko, beim
"Antrag" erstmal eingeschlàfert zu werden).

Dazu gibt's für jedes Objekt ein int32, das über
Compare-and-Swap Operationen mit Informationen hàlt:
zu Lock-holder, Lock-count (ein Thread bzw.
AccessPoint-Object darf das Objekt mehrfach locken),
sowie einen Schlüssel zu Informationen über
auf das Objekt wartende AccessPoints.

Im Prinzip scheints zu funktionieren, aber so etwa
einmal pro 1Mio. Lock-Operationen sieht es
zumindest symptomatisch so aus, als würde die
Compare-and-Swap Operation unerlaubt swappen (der
erste wartende Thread wird korrekt geweckt, hat aber
das Lock dann gar nicht, und bekommt es auch nicht
mehr).

Also eh' ich jetzt noch weiter rumlaber, kippe
ich mal den Code ab. Vielleicht hat ja wer 'ne Idee
(Barrieren um die InterlockedOPs habe ich schon
probiert, obwohl die Massenahme nicht gut zur
Symptomatik passt).

Gruss

Jan bruns






procedure TparlocCol.lockObj(o : Toid; ap : TparlocAP);
var ap2 : TparlocAP; a, wc, old : longint; lv : Plongint;
begin
RTLeventResetEvent(ap.locksig);
lv := locate_locvar(o);
repeat
// assume there currently is no lock
a := (ap.id shl lsb_lock_holder) + 1;
old := InterlockedCompareExchange(lv^,a,0);
if (old=0) then break
else begin
a := (old shr lsb_lock_holder) and apidmask;
if (a = ap.id) then begin
{ we already have the lock. just inc. }
a := old and lockcountmask;
if (a>=lockcountlimit) then begin
raise parlocAPexcpt.Create('Too many locks on object.');
end else begin
a := InterlockedCompareExchange(lv^,old+1,old);
if (a=old) then break;
end;
end else begin
{ another AP has the lock. try linking into
the chain of waiters. }
wc := (old shr lsb_lock_waiter) and apidmask;
if (wc=0) then begin
wc := start_new_waitchain(o,ap);
a := old or (wc shl lsb_lock_waiter);
a := InterlockedCompareExchange(lv^,a,old);
if (a=old) then begin
unlock_waitchain(wc);
wait_waitchain(wc,o,ap);
break;
end else discard_waitchain(wc); // and retry
end else begin
if try_append_waitchain(wc,o,ap) then begin
wait_waitchain(wc,o,ap);
break;
end; // else retry
end;
end;
end;
until false;
end;

procedure TparlocCol.unlockObj(o : Toid; ap : TparlocAP);
var ap2 : TparlocAP; a, old, wc, wc2 : longint; lv : Plongint;
begin
lv := locate_locvar(o);
repeat
// assume we had a single lock with no waiters
a := (ap.id shl lsb_lock_holder) + 1;
old := InterlockedCompareExchange(lv^,0,a);
if not(old=a) then begin
a := (old shr lsb_lock_holder) and apidmask;
if (a=ap.id) then begin
a := old and lockcountmask;
if (a>1) then begin
// we had locked the object more than 1 time
InterLockedDecrement(lv^);
break;
end else if (a=1) then begin
{ give the lock to the first waiter. }
wc := (old shr lsb_lock_waiter) and apidmask;
if (wc=0) then begin
raise parlocAPexcpt.Create('No waiters or not?');
end else begin
lock_waitchain(wc); // forced, waited
ap2 := get_first_waiter(wc); // no remove
wc2 := decide_keep_waitchain(wc); // wc, or 0, if waiting<2
a := (ap2.id shl lsb_lock_holder);
a := a or (wc2 shl lsb_lock_waiter);
a := a +1;
a := InterlockedCompareExchange(lv^,a,old);
if not(a=old) then begin
raise parlocAPexcpt.Create('Unexpected lockvar mod during unlock.');
end else begin
if (wc2=0) then begin
discard_waitchain(wc);
end else begin
remove_first_waiter(wc);
unlock_waitchain(wc);
end;
RTLeventSetEvent(ap2.locksig); // wake up the oldest waiting thread
break;
end;
end;
end else begin
raise parlocAPexcpt.Create('Unclean reach of lockcnt=0.');
end;
end else begin
raise parlocAPexcpt.Create('Non-Owner attempt to unlock.');
end;
end else break; // initial assumption correct
until false;
end;
 

Lesen sie die antworten

#1 Bernhard Schornak
04/12/2014 - 14:57 | Warnen spam
Jan Bruns schrieb:


procedure TparlocCol.lockObj(o : Toid; ap : TparlocAP);
var ap2 : TparlocAP; a, wc, old : longint; lv : Plongint;
begin
RTLeventResetEvent(ap.locksig);
lv := locate_locvar(o);
repeat
// assume there currently is no lock
a := (ap.id shl lsb_lock_holder) + 1;
old := InterlockedCompareExchange(lv^,a,0);
if (old=0) then break
else begin
a := (old shr lsb_lock_holder) and apidmask;
if (a = ap.id) then begin
{ we already have the lock. just inc. }
a := old and lockcountmask;
if (a>=lockcountlimit) then begin
raise parlocAPexcpt.Create('Too many locks on object.');
end else begin
a := InterlockedCompareExchange(lv^,old+1,old);
if (a=old) then break;
end;
end else begin
{ another AP has the lock. try linking into
the chain of waiters. }
wc := (old shr lsb_lock_waiter) and apidmask;
if (wc=0) then begin
wc := start_new_waitchain(o,ap);
a := old or (wc shl lsb_lock_waiter);
a := InterlockedCompareExchange(lv^,a,old);
if (a=old) then begin
unlock_waitchain(wc);
wait_waitchain(wc,o,ap);
break;
end else discard_waitchain(wc); // and retry
end else begin
if try_append_waitchain(wc,o,ap) then begin
wait_waitchain(wc,o,ap);
break;
end; // else retry
end;
end;
end;
until false;
end;



<schnipp>

Mit Sicherheit weder x86 noch 68k Opcodes. Auch HLA oder
RosAsm schaut anders aus. Gibt es auch einen Link zu dem
"Assembler", der mit solch einer merkwürdig formatierten
Mischung aus Text und Hokuspokus etwas anfangen kann?

Zum Thema gibt es grundlegend

http://de.wikipedia.org/wiki/Cache-Koh%C3%A4renz

und vertiefend Kapitel 7.3 in AMDs "AMD64 Architecture
Programmer’s Manual, Volume 2: System Programming" oder
"Intel 64 and IA-32 Architectures Software Developer’s
Manual", Volume 3a, Kapitel 11.

Aus diesen Dokumenten geht eindeutig hervor, dass x86-
Programmierer nicht direkten Einfluss auf die Kohàrenz
der diversen Cachehierarchien nehmen können. Auch 68k-
Systeme mit mehreren Prozessoren dürften die möglichen
Kohàrenz-Probleme mit einer hardwareseitigen Steuerung
über ihren Chipsatz lösen, da softwareseitige Lösungen
viel zu tràge wàren, um derlei Aufgaben in Echtzeit zu
erledigen. Eine softwareseitige Lösung könnte nur über
MSRs (Machine State Register) realisiert werden. Diese
müssten von allen Prozessoren ansprechbar sein, was zu
reichlich komplexen Verwaltungsstrukturen - mit daraus
resultierender Entschleunigung - führen würde. Heutige
MSRs haben Zugriffszeiten von zwei- oder dreistelligen
Taktzyklen. Je nach dem, wie viele Prozessoren auf ein
MSR zugreifen, erhöht sich die Zugriffszeit drastisch.
Die interne Lösung regelt das Problem in wenigen Takt-
zyklen. Sie ist für System- und Anwendungsprogramierer
zudem transparent.


Grüsse aus Augsburg

Bernhard Schornak

Ähnliche fragen