[pso] contraargumente pe windows pentru folosirea listelor
Andrei Hagiescu
pso@cursuri.cs.pub.ro
Sun, 28 Mar 2004 15:06:18 +0300
This is a multi-part message in MIME format.
------=_NextPart_000_0079_01C414D6.38EBC970
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
In tema se specifica ca detaliile privitoare la pid-urile monitorizate =
trebuie pastrate in liste.
Analizand suportul privitor la liste al Windows-ului observ ca cei care =
l-au proiectat au avut in minte doua tipuri de structuri implementate cu =
liste: coada si stiva. In ambele, un element este introdus si apoi scos =
din lista, intre cele doua operatii nefiind necesar accesul la datele =
continute in el. De aceea singurele functii sincronizate sunt cele de =
introducere si respectiv scoatere din lista. Intr-un fel este si normal =
deoarece o parcurgere a listei in cautarea unui anumit element si =
analiza datelor din el poate dura foarte mult (proportional cu lungimea =
listei) si exista o limita de 25 us pentru tinerea unui spin lock.=20
Si acum sa revenim la tema: noi trebuie sa scanam lista la fiecare =
interceptare de apel, respectiv la fiecare pornire si oprire a unei =
monitorizari si conform considerentelor de mai sus nu putem tine un spin =
lock atata timp (cred ca 25us se refera la un O(1) nu prea lung si in =
nici un caz la O(n) ). Daca introducerea de noi elemente in lista este =
"ratata" de o scanare nu este grav insa lucruri mult mai grave se pot =
petrece daca un element este scos din lista intre momentul descoperirii =
lui si momentul citirii datelor. Deoarece memoria in care era stocat =
trebuie eliberata apare un page fault. O analiza mai in detaliu =
demonstreaza ca nici macar spinlock-uri eliberate dupa fiecare element =
al listei nu sunt suficiente deoarece poate sa dispara urmatorul element =
pentru care tocmai aflasem adresa.
Si atunci ramane o singura speranta: sa manevram lista numai cu push si =
pop. Ceea ce e cam imposibil.
Si atunci...obligativitatea folosirii unei liste mai este normala?
P.S. 25 us nu sunt un timp suficient de lung pe _orice_ platforma care =
ruleaza Windows pentru a analiza o lista cu numarul maxim de pid-uri =
acceptate de Windows.
O evaluare aproximativa 25x200 MHz=3D5000 cicli /1000 piduri =3D 5 =
ciclii / pid si trebuie un=20
while (lista) {
lista=3Dlista->next; //1 ciclu atribuirea + 1 ciclu calculul adresei =
lista->next
if (lista.pid=3D=3Dpid) break; //branch+comp 2 cicli + 1 ciclu =
lista.pid
} //branch 2 cicli (in cel mai bun =
caz considerand pipeline)
=3D7 cicli....si asta scris echivalentul in asm.
Deci?
------=_NextPart_000_0079_01C414D6.38EBC970
Content-Type: text/html;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=3DContent-Type content=3D"text/html; =
charset=3Diso-8859-1">
<META content=3D"MSHTML 6.00.2800.1400" name=3DGENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=3D#ffffff>
<DIV><FONT face=3DArial size=3D2>In tema se specifica ca detaliile =
privitoare la=20
pid-urile monitorizate trebuie pastrate in liste.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2>Analizand suportul privitor la liste al =
Windows-ului observ ca cei care l-au proiectat au avut in minte doua =
tipuri de=20
structuri implementate cu liste: coada si stiva. In ambele, un element =
este=20
introdus si apoi scos din lista, intre cele doua operatii nefiind =
necesar=20
accesul la datele continute in el. De aceea singurele functii =
sincronizate sunt=20
cele de introducere si respectiv scoatere din lista. Intr-un fel este si =
normal=20
deoarece o parcurgere a listei in cautarea unui anumit element si =
analiza=20
datelor din el poate dura foarte mult (proportional cu lungimea listei) =
si=20
exista o limita de 25 us pentru tinerea unui spin lock. </FONT></DIV>
<DIV><FONT face=3DArial size=3D2>Si acum sa revenim la tema: noi trebuie =
sa scanam=20
lista la fiecare interceptare de apel, respectiv la fiecare pornire si =
oprire a=20
unei monitorizari si conform considerentelor de mai sus nu putem tine un =
spin=20
lock atata timp (cred ca 25us se refera la un O(1) nu prea lung si in =
nici un=20
caz la O(n) ). Daca introducerea de noi elemente in lista este "ratata" =
de o=20
scanare nu este grav insa lucruri mult mai grave se pot petrece =
daca un=20
element este scos din lista intre momentul descoperirii lui si momentul =
citirii=20
datelor. Deoarece memoria in care era stocat trebuie eliberata =
apare=20
un page fault. O analiza mai in detaliu demonstreaza ca nici macar =
spinlock-uri=20
eliberate dupa fiecare element al listei nu sunt suficiente deoarece =
poate sa=20
dispara urmatorul element pentru care tocmai aflasem =
adresa.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2>Si atunci ramane o singura speranta: sa =
manevram=20
lista numai cu push si pop. Ceea ce e cam imposibil.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>Si atunci...obligativitatea folosirii =
unei liste=20
mai este normala?</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>P.S. 25 us nu sunt un timp suficient de =
lung pe=20
_orice_ platforma care ruleaza Windows pentru a analiza o lista cu =
numarul maxim=20
de pid-uri acceptate de Windows.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2>O evaluare aproximativa 25x200 =
MHz=3D5000 cicli=20
/1000 piduri =3D 5 ciclii / pid si trebuie un </FONT></DIV>
<DIV><FONT face=3DArial size=3D2>while (lista) {</FONT></DIV>
<DIV><FONT face=3DArial size=3D2> =
lista=3Dlista->next; //1 ciclu=20
atribuirea + 1 ciclu calculul adresei lista->next</FONT></DIV>
<DIV><FONT face=3DArial size=3D2> if =
(lista.pid=3D=3Dpid) break;=20
//branch+comp 2 cicli + 1 ciclu lista.pid</FONT></DIV>
<DIV><FONT face=3DArial size=3D2>} =20
=
=20
//branch =
2 cicli=20
(in cel mai bun caz considerand pipeline)</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>=3D7 cicli....si asta scris =
echivalentul in=20
asm.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>Deci?</FONT></DIV></BODY></HTML>
------=_NextPart_000_0079_01C414D6.38EBC970--