Masterfield

A Masterfield Oktatóközpont szakmai blogja. Minden, ami a tanfolyamokról kimaradt

Friss topikok

  • gyuria: Na végre, már nagyon vártam Már annyi téma összejött, hogy egy jó darabig biztos kitart :) (2008.10.24. 08:04) Elindultunk

Linkblog

Hogyan használjuk hatékonyan a Java Hashtable osztályát? - 1. rész

2008.12.05. 12:20 | gbujdoso | Szólj hozzá!

Címkék: java hash masterfield hashtable performancia collision rehash capacity load factor hash tábla

Nincs olyan Java programozó, aki ne találkozott volna már a Hashtable (http://java.sun.com/javase/6/docs/api/java/util/Hashtable.html) osztállyal. Egy hasznos, rengeteg célra hatékonyan használható adatszerkezetet valósít meg, ezért a gyakorlatban sokan előszeretettel használják. Van azonban néhány fontos dolog, amit mindenképpen tudnunk kell róla mielőtt saját kódunkat elkezdjük telepakolni Hashtable példányokkal és ennek következtében komoly performanciális problémákba ütközünk.

Általánosan a hash táblák elméletéről a Wikipediaban találunk infót: http://en.wikipedia.org/wiki/Hash_table
Én most ebben a postban egy lényeges ponton vizsgálnám meg a Java Hashtable implementáció működését, mégpedig az ütközések és az ezzel kapcsolatos táblaméret növelésének algoritmusánál (rehash).
 
Mielőtt belefognánk a rehash (resize) algoritmus elemzésébe feltétlenül meg kell értenünk a Java hash tábla alapvető működését. A hash táblában az elemek úgynevezett vödrökben (buckets) kerülnek tárolásra. Amikor egy elemet elhelyezünk a táblában, akkor megadunk egy kulcsot. Ebből a kulcsból bizonyos hash algoritmus használatával az algoritmus előállít egy memóriacímet (indexet), ahová elhelyezi magának az adatnak a mutatóját.
 
Az alábbi ábra ezt a struktúrát mutatja be.
Előfordulhat azonban olyan eset, amikor a két különböző kulcshoz ugyanolyan hash érték áll elő. Ebben az esetben két különböző kulcs is ugyanarra az indexre, végső soron ugyanarra az elemre fog mutatni. Ezt hívjuk ütközésnek. Az ütközések valószínűsége csökkenthető megfelelő hash algoritmus használatával.
 
 
Tehát egy megfelelő hash algoritmusnak a következő feltételeknek kell eleget tennie:
-         a hash kódnak (indexnek) minél nagyobb szórást kell mutatnia, ezzel csökkentve az ütközések valószínűségét
-         minél gyorsabb legyen
A kulcs természetesen bármilyen típus lehet, ami nem null és létezik a hashCode() és equals() metódusa. A gyárilag használt típusok (Object, String, Integer, Boolean, stb.) eleve tartalmazzák ezeket a metódusokat. Java-ban minden osztály az Object osztályból származik. Nézzük meg a Java 6 API Javadoc-ban az Object osztály hashCode algoritmusát:
 
hashCode
 
public int hashCode()
Returns a hash code value for the object. This method is supported for the benefit of hashtables such as those provided by java.util.Hashtable.
 
The general contract of hashCode is:
           Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.
           If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.
           It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hashtables.
 
A kiemelt részben olvashatjuk, hogy nem kötelező, hogy két különböző objektumnak a hash kódja különböző legyen. Ez sajnos a Java saját String típusánál használt hash algoritmusra kiemelten igaz. Nézzük meg a Java 6 API Javadoc-ban a String osztály hashCode algoritmusát:
 
hashCode
 
public int hashCode()
Returns a hash code for this string. The hash code for a String object is computed as
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
 

using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation. (The hash value of the empty string is zero.)

A problémát jól mutatja a következő kódrészlet:
String s1 = new String("BB");
String s2 = new String("Aa");
System.out.println(s1.hashCode());
System.out.println(s2.hashCode());
 
Ami ebben az esetben mindkét String hash kódjának 2112-t fog kiírni. Tehát két különböző objektumnak mégis ugyanaz lett a hash kódja. Azaz a String típus nem számít jónak az első feltételt tekintve, gyakori ütközést eredményez a hash táblában. És itt a lényeg, hogy a mindennapi programozói gyakorlatban a hash táblákban kulcsként nagyon gyakran String-eket használunk, amiknél nagy az ütközés valószínűsége.
 
Természetesen lehetőségünk van a hash algoritmus javítására, amennyiben saját típust hozunk létre és (felül)definiáljuk a hashCode() függvényt, ezáltal csökkentve az ütközések valószínűségét.
 
További probléma a Java-s hash kódokkal, hogy azok int típusúak, azaz 32 bit hosszúak, ami eleve egy elég alacsony korlát. Így maximum 4.294.967.295 különböző hash kódot eredményezhetnek. A jövőben valószínűleg szükség lesz a 64 bites (long) hash kódok használatára.
 
Kicsit elkanyarodtunk a témától, ezért térjünk vissza a Java hash tábla implementációhoz. Tegyük fel, hogy a fenti két String-et („BB”, „Aa”) szeretnénk kulcsnak használni egy hash táblában elemek tárolásához.
 
String s1 = new String("BB");
String s2 = new String("Aa");
Hashtable h = new Hashtable();
h.put(s1, "value1");
h.put(s2, "value2");
 
Ekkor fellép a fent részletezett ütközés. Ezt a Java úgy oldja fel, hogy az egyes vödrök tulajdonképpen láncolt listát jelentenek, és ezt a listát bővíti ütközéskor. Azaz amikor a második elemnek meghatározza a helyét (indexét/hash kódját), akkor látja, hogy ott már van egy elem, ezért az új elemet a már létező elem elé láncolja a kulccsal együtt. Amikor valaki get() metódussal szeretné az elemet megtalálni, akkor a láncon addig megy amíg az adott kulcsot meg nem találja és az ott tárolt értéket adja vissza. Ezt az ütközés-feloldást hívjuk láncolásnak (chaining). Más – hatékonyabb – algoritmusok is léteznek az ütközés feloldására, ezekről bővebb információt a fenti Wikipedia oldal tartalmaz.
 
Java-ban a hash táblának két fontos induló paramétere van:
- induló kapacitás (initial capacity): az elemek tárolására szolgáló "vödrök" (buckets) száma induláskor. Az egyes tárolásra kerülő objektumok kerülnek a vödrökbe. (Ne felejtsük el, hogy az egyes vödrökön belül láncolt listákban tárolódnak az elemek!)
- telítettségi faktor (load factor): a vödrök számának és a foglalt vödrök számának aránya. Érdekes, hogy ez akár át is lépheti a 100%-ot, ugyanis egy vödörben ütközés esetén több elem is tárolásra kerül a láncolt listában. Amikor egy új elem berakásakor átlépi a telítettség ezt a faktort, akkor a tábla mérete (a vödrök száma) automatikusan növekszik és lefut a rehash algoritmus.
 
Amikor Java-ban leírjuk a
Hashtable ht = new Hashtable();
utasítást, akkor egy 11 vödörből álló 0.75-ös telítettségi faktorú hash tábla jön létre.
 
Az általános konstruktor forráskódja a következő:
public Hashtable(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                                 initialCapacity);
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal Load: +loadFactor);
 
    if (initialCapacity==0)
        initialCapacity = 1;
    this.loadFactor = loadFactor;
    table = new Entry[initialCapacity];
    threshold = (int)(initialCapacity * loadFactor);
}
 
Nézzük meg a Hashtable forráskódjában, hogy mit csinál, amikor egy új elemet berakunk:
public synchronized V put(K key, V value) {
 // Make sure the value is not null
 if (value == null) {
      throw new NullPointerException();
 }
 // Makes sure the key is not already in the hashtable.
 Entry tab[] = table;
 int hash = key.hashCode();
 int index = (hash & 0x7FFFFFFF) % tab.length;
 for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
      if ((e.hash == hash) && e.key.equals(key)) {
        V old = e.value;
        e.value = value;
        return old;
      }
 }
 modCount++;
 if (count >= threshold) {
      // Rehash the table if the threshold is exceeded
      rehash();
      tab = table;
      index = (hash & 0x7FFFFFFF) % tab.length;
 }
 // Creates the new entry.
 Entry<K,V> e = tab[index];
 tab[index] = new Entry<K,V>(hash, key, value, e);
 count++;
 return null;
}
A kiemelt részben látszik, hogy az index meghatározásához felhasználja a tábla kapacitását. Ez kezdetben az induló kapacitás, majd minden automatikus növeléskor ez
N * 2 + 1 értékre nő, ahol N a régi kapacitás. Továbbá látszik, hogy amennyiben az elemek száma eléri vagy meghaladja a kapacitás x telítettségi factor (=threshold) értéket, akkor automatikusan elindul a rehash algoritmus, ami elvégzi a tábla kapacitásának növelését.
 

Hogyan használjuk hatékonyan a Java Hashtable osztályát? - 2. rész

2008.12.05. 10:12 | gbujdoso | Szólj hozzá!

Címkék: java hash masterfield hashtable performancia collision rehash capacity load factor hash tábla

 

Nézzük meg a rehash() függvényt is:

/**
 * Increases the capacity of and internally reorganizes this hashtable, in
 * order to accommodate and access its entries more efficiently. This method
 * is called automatically when the number of keys in the hashtable exceeds
 * this hashtable's capacity and load factor.
 */
protected void rehash() {
    int oldCapacity = table.length;
    Entry[] oldMap = table;
    
    int newCapacity = oldCapacity * 2 + 1;
    Entry[] newMap = new Entry[newCapacity];
    
    modCount++;
    threshold = (int)(newCapacity * loadFactor);
    table = newMap;
    
    for (int i = oldCapacity ; i-- > 0 ;) {
        for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
          Entry<K,V> e = old;
          old = old.next;
          int index = (e.hash & 0x7FFFFFFF) % newCapacity;
          e.next = newMap[index];
          newMap[index] = e;
        }
    }
}
Ebből is látszik, hogy a tábla kapacitásának növekedésével az ütközések valószínűsége csökken. Továbbá a rehash algoritmus időigényes és futási ideje arányoson nő az elemek számának növekedésével, ezért célszerű elkerülni a futását. Valamint fontos tudnunk, hogy az elemek törlése (remove) esetén a kapacitás nem fog csökkenni korábbi értékére.
 
Összefoglalva néhány tanács a Java Hashtable használatához:
-          jó hash algoritmussal csökkenthető az ütközések valószínűsége; ezért akár saját hatékony hashCode() függvényt is implementálhatunk
-          megfelelő kapacitást és telítettségi faktort válasszunk, hogy minél kevesebbszer fusson a rehash algoritmus, de ne foglaljunk feleslegesen memóriát túl nagy, felesleges értékek beállításával
-          a kapacitás mindig legalább 25%-kal nagyobb legyen a maximálisan tárolásra kerülő elemek számánál. Megfordítva: a tábla telítettsége ne haladja meg a 75%-ot. Ez az érték optimális elérést és megfelelő méretet jelent.
 
Tehát a Java Hashtable egy kényelmes adatszerkezet, amely könnyen használható és rugalmas. Nagy táblák tárolására azonban csak korlátozottan használható. Pontos tervezést és odafigyelést igényel használata ezekben az esetekben.

 

10 + 1 tipp valid HTML oldal készítéséhez

2008.11.18. 10:07 | kmizsak | Szólj hozzá!

Címkék: keresőoptimalizálás html xhtml validálás attribútum validity

Több cég keresett meg minket az utóbbi időben, hogy segítsünk nekik az oldaluk validálásában. Összeszedtem az ezek alapján leggyakrabban előforduló hibákat, melyek mások számára is segítséget jelenthetnek. Fontos, hogy ezek a validálási szabályok a W3C XHTML 1.0 szabványának felelnek meg!

Íme a 11 leggyakoribb hiba:

1. HTML elemek neveit kis betűvel kell írni, tehát: <html>, <head>, <body>, <h1> …

2. <form> elemen belül a metódus meghatározása szintén kis betűvel történik: method=”post”

3. minden elemet zárjunk le (leggyakrabban a <br>, <hr>, <img> és <input> elemek nem lettek lezárva), tehát helyesen: <br />, <hr />...

4. ne használjunk blokk szintű elemeket soron belüli elemekben, leggyakoribb hiba: a <div> és a <p> elemek használata az <a> elemben

5. javascript eseménykezelőket kis betűvel kell írni, például onkeyup, onmouseover, ...

6. <tr> elem nem kaphat height attribútumot, ezt bízzuk a <td> elemre

7. minden attribútumot idézőjelek közé kell tenni, például: <td rowspan=”2”>

8. ne felejtsük el megadni az alt attribútumot az <img> elemnek

9. és azt se felejtsük el, hogy az <a> elemnek nincs alt attribútuma

10. a <script> elemnek nincs language attribútuma, viszont a type használata kötelező, tehát helyesen: <script type="text/javascript">

+1: Végül egy példa flash valid beillesztésére:

<object type="application/x-shockwave-flash" data="pelda.swf" id="pelda" width="80" height="30”>

<param name="movie" value=" pelda.swf" />

            <param name="quality" value="high" />

</object>

És hogy miért is érdemes validálni az oldalunkat?

A valid oldalunk nemcsak a normál böngészőkben fog valószínűleg jól és ugyanúgy (erről azért majd írok egy külön post-ot) megjelenni a különböző platformokon (Windows, Linux, Mac), hanem más eszközökön is, így például a mobiltelefonokon.

Nagyon fontos még a validálás a keresőkben elfoglalt pozíciónk javításához is. Egy webes szabványokkal elkészített oldal sokkal könnyebben feldolgozható a keresőrobotok számára.

 

 

Protected metódusok elérése kívülről Delphi-ben

2008.10.15. 17:04 | gyuria | Szólj hozzá!

Címkék: protected tulajdonság delphi pascal attribútum metódus

Ma megint alkalmaznom kellett egy apró trükköt és eszembe jutott, hogy talán ki lehetne tenni a blogra, mert nem biztos, hogy mindenki ismeri.

Bizonyos esetekben - főleg, ha általánosan kezelünk objektumokat, jó lenne protected metódusokat vagy attribútumokat elérni az osztályon kívülről. Protected metódusok Delphi-ben alapesetben elérhetők az osztályban és a leszármazottakban. Ha ez nem elég, akkor létre kell hoznunk egy leszármazottat az elérni kívánt osztályból és arra cast-olni a megfelelő objektumot.

Tegyük fel, hogy egy TControl objektumnak szeretnénk elérni a Font tulajdonságát.

procedure ShowFontName( ctrl : TControl );

begin

  ShowMessage( ctrl.Font.Name );

end;

Ez hibát fog eredményezni, mert a Font protected tulajdonság. A trükk egyszerű:

type TControlAccess = class( TControl );

procedure ShowFontName( ctrl : TControl );

begin

  ShowMessage( TControlAccess( ctrl ).Font.Name );

end;

Ez már így menni fog. Feltétele a dolognak, hogy a TControlAccess osztály definíciójának ugyanabban a unit-ban kell lennie, mint ahol használni akarjuk (nem elég egy uses a tartalmazó unit-ra).

Saját osztályoknál erre az egyszerű trükkre nem nagyon lehet szükségünk, mert nyilván úgy módosítjuk az osztályt, hogy elérjük a metódust vagy attribútumot. Viszont, ha pl. a VCL könyvtár osztályait akarjuk elérni, akkor hasznos lehet.

Java holtpont vizsgálata thread dump segítségével - 1. rész

2008.09.17. 12:41 | gbujdoso | Szólj hozzá!

Címkék: java collection jvm stack thread holtpont dump masterfield thread dump hashtable deadlock util

Szinte minden Java programozó kedvenc és legtöbbet használt adatszerkezetei a java.util csomag osztályai: Hashtable, LinkedList, Vector, LinkedHashMap, stb. Szeretjük őket használni, hiszen könnyen kezelhetőek, dinamikusak, kényelmesen hívható függvényeket tartalmaznak és generikus adattárolást tesznek lehetővé.

Azonban van két alapvető problémájuk, ami miatt mindig alaposan meg kell gondolni használatukat. Illetve nagyon pontosan ismernünk kell a működésüket a háttérben. Az első a performancia alakulás használatukkor, a második pedig a holtpont  kialakulásának veszélye. Előbbiről egy másik posztban fogok írni. Most inkább a másodikra mutatok be egy példát és közben megnézzük egy hasznos "eszköz", a thread dump használatát és azt, hogy hogyan segít megtalálni a kódban a holtpontokat.

 

Később részletesen foglalkozunk a holtponttal, itt most csak a definícióját szeretném megadni: Holtpont egyrészt akkor fordulhat elő a vezérlés során, ha a folyamatok egy adott halmazában minden egyes elem leköt néhány erőforrást, és ugyanakkor várakozik is néhányra. Ha ilyen esetben a folyamatok egy része olyan erőforrásra várakozik, amelyek mások elfoglaltak, akkor a tevékenységek "megmerevedhetnek".

Ref.: http://hu.wikipedia.org/wiki/Holtpont

 

Sokan nem is sejtik, hogy ezek a beépített osztályok nem mennének át a Nasa stabilitás tesztjén :) Számos alkalmazásnál kritikusnak számít egy esetleges holtpont vagy végtelen ciklusba kerülés, éppen ezért matematikai úton vagy átfogó teszttel szükséges kimutatni egy adott kódrészletről, hogy abban soha sem alakulhat ki holtpont.

 

A CUTE (Concolic Unit Testing Engine) fejlesztői szerint a Java 1.4-es java.util.Collection könyvtárában számos holtpontot vagy végtelen ciklust okozó hiba van.

A weboldalukon (http://osl.cs.uiuc.edu/~ksen/cute/?page=cases) lévő táblázat alapján ezek a következők:

Name

Run time

# of

# of

% Branch

# of Functions

# of Bugs Found

 

in seconds

Paths

Threads

Coverage

Tested

data races/deadlocks/infinite loops/exceptions

Vector

5519

20000

5

76.38

16

1/9/0/2

ArrayList

6811

20000

5

75

16

3/9/0/3

LinkedList

4401

11523

5

82.05

15

3/3/1/1

LinkedHashSet

7303

20000

5

67.39

20

3/9/0/2

TreeSet

7333

20000

5

54.93

26

4/9/0/2

HashSet

7449

20000

5

69.56

20

19/9/0/2

 

Gondoljunk csak a lefagyott marsjáróra vagy egy irányíthatatlanná vált repülőre és máris megértjük, hogy miért írnak ezekre a célszámítógépekre saját operációs rendszert és alakítanak ki rajtuk saját programozási környezetet, akár saját programnyelvet is és miért vetik alá átfogó tesztnek programjaikat.

 

Ha fellapozzuk a Sun hivatalos Java hiba adatbázisát, akkor néhány perc keresgélés után máris találunk élő, a legutolsó 1.6-os verzióban is létező hibát a Hashtable osztályban.

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6582568

A leírás szerint a Hashtable.equals metódusa holtpontot okoz. Az biztos, hogy nem az equals függvény a Hashtable leggyakrabban használt függvénye, de azért ez érdekes.

 

Próbáljuk ki a hiba leírásában szereplő (egyszerűsített!) példakódot, ami két hash táblát hasonlít össze egymással párhuzamosan két különböző szálon:

 

public class Bug {

 

    static Hashtable makeTable() {

            Hashtable h = new Hashtable();

            h.put(1,1);

            return h;

    }

 

    static Thread comparer(final Hashtable h1, final Hashtable h2) {

             return new Thread(new Runnable() {

public void run() {

                        long t0 = System.nanoTime();

                        while (System.nanoTime() - t0 < 1000*1000*1000)

                              h1.equals(h2);

      System.out.println("Finish!");

}

 });

    }

 

    public static void main(String[] args) throws Throwable {

            final Hashtable h1 = makeTable();

            final Hashtable h2 = makeTable();

            Thread job1 = comparer(h1, h2);

            Thread job2 = comparer(h2, h1);

            job1.start();

            job2.start();

            job1.join();

            job2.join();

    }

}

 

Elindítva azonnal elő is áll a holtpont, a „Finish!” üzenet soha nem íródik ki, a program „lefagy”. Pedig elvileg a ciklus csak 1 másodpercig fut, utána kilép(ne).

 

Mi történhetett a futás alatt?

 

Indítsuk a fenti példát Windows cmd ablakból és nyomjuk meg a Ctrl+Break gombokat. Windows alatt a Ctrl+Break együttes megnyomásával a Sun JVM kiírja a standard outputra a teljes thread dumpját:

 

2008-11-01 13:06:15

Full thread dump Java HotSpot(TM) Client VM (11.0-b12 mixed mode, sharing):

 

"Thread-1" prio=6 tid=0x02a9bc00 nid=0x120 waiting for monitor entry [0x02e6f000..0x02e6fb14]

   java.lang.Thread.State: BLOCKED (on object monitor)

        at java.util.Hashtable.size(Hashtable.java:206)

        - waiting to lock <0x24100158> (a java.util.Hashtable)

        at java.util.Hashtable.equals(Hashtable.java:742)

        - locked <0x24100180> (a java.util.Hashtable)

        at Bug$1.run(Bug.java:16)

        at java.lang.Thread.run(Thread.java:619)

 

"Thread-0" prio=6 tid=0x02a9ac00 nid=0x9bc waiting for monitor entry [0x02e1f000..0x02e1fb94]

   java.lang.Thread.State: BLOCKED (on object monitor)

        at java.util.Hashtable.get(Hashtable.java:333)

        - waiting to lock <0x24100180> (a java.util.Hashtable)

        at java.util.Hashtable.equals(Hashtable.java:755)

        - locked <0x24100158> (a java.util.Hashtable)

        at Bug$1.run(Bug.java:16)

        at java.lang.Thread.run(Thread.java:619)

 

"Low Memory Detector" daemon prio=6 tid=0x02a81800 nid=0x27c runnable [0x00000000..0x00000000]

   java.lang.Thread.State: RUNNABLE

 

"CompilerThread0" daemon prio=10 tid=0x02a7b400 nid=0x920 waiting on condition [0x00000000..0x02d2f6c0]

   java.lang.Thread.State: RUNNABLE

 

"Attach Listener" daemon prio=10 tid=0x02a79c00 nid=0x9d0 runnable [0x00000000..0x00000000]

   java.lang.Thread.State: RUNNABLE

 

"Signal Dispatcher" daemon prio=10 tid=0x02a78800 nid=0xe70 waiting on condition [0x00000000..0x00000000]

   java.lang.Thread.State: RUNNABLE

 

"Finalizer" daemon prio=8 tid=0x02a73800 nid=0xf5c in Object.wait() [0x02c3f000..0x02c3fa14]

   java.lang.Thread.State: WAITING (on object monitor)

        at java.lang.Object.wait(Native Method)

        - waiting on <0x241003c0> (a java.lang.ref.ReferenceQueue$Lock)

        at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:116)

        - locked <0x241003c0> (a java.lang.ref.ReferenceQueue$Lock)

        at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:132)

        at java.lang.ref.Finalizer$FinalizerThread.run(Finalizer.java:159)

 

"Reference Handler" daemon prio=10 tid=0x02a6f000 nid=0x434 in Object.wait() [0x02bef000..0x02befb14]

   java.lang.Thread.State: WAITING (on object monitor)

        at java.lang.Object.wait(Native Method)

        - waiting on <0x24100150> (a java.lang.ref.Reference$Lock)

        at java.lang.Object.wait(Object.java:485)

        at java.lang.ref.Reference$ReferenceHandler.run(Reference.java:116)

        - locked <0x24100150> (a java.lang.ref.Reference$Lock)

 

"main" prio=6 tid=0x002a6800 nid=0x1c8 in Object.wait() [0x0090f000..0x0090fe54]

   java.lang.Thread.State: WAITING (on object monitor)

        at java.lang.Object.wait(Native Method)

        - waiting on <0x241000e8> (a java.lang.Thread)

        at java.lang.Thread.join(Thread.java:1143)

        - locked <0x241000e8> (a java.lang.Thread)

        at java.lang.Thread.join(Thread.java:1196)

        at Bug.main(Bug.java:29)

 

"VM Thread" prio=10 tid=0x02a6d800 nid=0xeac runnable

 

"VM Periodic Task Thread" prio=10 tid=0x02a83400 nid=0x448 waiting on condition

 

JNI global references: 608

 

 

Found one Java-level deadlock:

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

"Thread-1":

  waiting to lock monitor 0x02a736ec (object 0x24100158, a java.util.Hashtable),

  which is held by "Thread-0"

"Thread-0":

  waiting to lock monitor 0x02a73754 (object 0x24100180, a java.util.Hashtable),

  which is held by "Thread-1"

 

Java stack information for the threads listed above:

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

"Thread-1":

        at java.util.Hashtable.size(Hashtable.java:206)

        - waiting to lock <0x24100158> (a java.util.Hashtable)

        at java.util.Hashtable.equals(Hashtable.java:742)

        - locked <0x24100180> (a java.util.Hashtable)

        at Bug$1.run(Bug.java:16)

        at java.lang.Thread.run(Thread.java:619)

"Thread-0":

        at java.util.Hashtable.get(Hashtable.java:333)

        - waiting to lock <0x24100180> (a java.util.Hashtable)

        at java.util.Hashtable.equals(Hashtable.java:755)

        - locked <0x24100158> (a java.util.Hashtable)

        at Bug$1.run(Bug.java:16)

        at java.lang.Thread.run(Thread.java:619)

 

Found 1 deadlock.

 

Heap

 def new generation   total 960K, used 64K [0x24010000, 0x24110000, 0x244f0000)

  eden space 896K,   0% used [0x24010000, 0x24010028, 0x240f0000)

  from space 64K, 100% used [0x24100000, 0x24110000, 0x24110000)

  to   space 64K,   0% used [0x240f0000, 0x240f0000, 0x24100000)

 tenured generation   total 4096K, used 50K [0x244f0000, 0x248f0000, 0x28010000)

   the space 4096K,   1% used [0x244f0000, 0x244fc868, 0x244fca00, 0x248f0000)

 compacting perm gen  total 12288K, used 21K [0x28010000, 0x28c10000, 0x2c010000)

   the space 12288K,   0% used [0x28010000, 0x28015408, 0x28015600, 0x28c10000)

    ro space 8192K,  66% used [0x2c010000, 0x2c56a540, 0x2c56a600, 0x2c810000)

    rw space 12288K,  53% used [0x2c810000, 0x2ce723f8, 0x2ce72400, 0x2d410000)

 

A dumpban láthatjuk, hogy a JVM maga is felismerte a holtpontot és erről ad is információt:

Found one Java-level deadlock:

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

"Thread-1":

  waiting to lock monitor 0x02a736ec (object 0x24100158, a java.util.Hashtable),

  which is held by "Thread-0"

"Thread-0":

  waiting to lock monitor 0x02a73754 (object 0x24100180, a java.util.Hashtable),

  which is held by "Thread-1"

 

A két szál, amit a példában létrehoztunk a közös hash táblákhoz való hozzáféréskor holtpontba kerül. Ez a holtpont lényege: mindkét szál valamilyen közös erőforrásra vár, amit a másik foglal, így egymást kölcsönösen blokkolják. A végrehajtás egyik szálon sem tud folytatódni.

 

 

Java holtpont vizsgálata thread dump segítségével - 2. rész

2008.09.17. 12:40 | gbujdoso | Szólj hozzá!

Címkék: java collection jvm stack thread holtpont dump masterfield thread dump hashtable deadlock util

Nézzük a dumpból a stack-et (az aktuális végrehajtási láncot):

Java stack information for the threads listed above:

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

"Thread-1":

        at java.util.Hashtable.size(Hashtable.java:206)

        - waiting to lock <0x24100158> (a java.util.Hashtable)

        at java.util.Hashtable.equals(Hashtable.java:742)

        - locked <0x24100180> (a java.util.Hashtable)

        at Bug$1.run(Bug.java:16)

        at java.lang.Thread.run(Thread.java:619)

"Thread-0":

        at java.util.Hashtable.get(Hashtable.java:333)

        - waiting to lock <0x24100180> (a java.util.Hashtable)

        at java.util.Hashtable.equals(Hashtable.java:755)

        - locked <0x24100158> (a java.util.Hashtable)

        at Bug$1.run(Bug.java:16)

        at java.lang.Thread.run(Thread.java:619)

 

A példa kódban a kiemelt résznél, a h1.equals(h2) utasításnál van a holtpont. Itt még a külön jelőlt két szál ugyanazt az utasítást (equals) hajtja végre.

 

Mit is csinál itt az equals az API leírás szerint? http://java.sun.com/javase/6/docs/api/java/util/Hashtable.html#equals(java.lang.Object)

 

Compares the specified Object with this Map for equality, as per the definition in the Map interface.

Ez átküld minket a Map inteface equals leírásához.

Nézzük meg azt is:

http://java.sun.com/javase/6/docs/api/java/util/Map.html#equals(java.lang.Object)

 

boolean equals(Object o)

Compares the specified object with this map for equality. Returns true if the given object is also a map and the two maps represent the same mappings. More formally, two maps m1 and m2 represent the same mappings if m1.entrySet().equals(m2.entrySet()). This ensures that the equals method works properly across different implementations of the Map interface.

 

 

A J2SE 6-os verziójának forráskódja innen tölthető le:

http://download.java.net/jdk6/6u3/promoted/b05/index.html

 

Ebben megkeressük a Hashtable.equals Sun-os megvalósítását:

/**

 * Compares the specified Object with this Map for equality,

 * as per the definition in the Map interface.

 *

 * @param  o object to be compared for equality with this hashtable

 * @return true if the specified Object is equal to this Map

 * @see Map#equals(Object)

 * @since 1.2

 */

public synchronized boolean equals(Object o) {

if (o == this)

    return true;

 

if (!(o instanceof Map))

    return false;

Map<K,V> t = (Map<K,V>) o;

if (t.size() != size())

    return false;

 

    try {

        Iterator<Map.Entry<K,V>> i = entrySet().iterator();

        while (i.hasNext()) {

            Map.Entry<K,V> e = i.next();

            K key = e.getKey();

            V value = e.getValue();

            if (value == null) {

                if (!(t.get(key)==null && t.containsKey(key)))

                    return false;

            } else {

                if (!value.equals(t.get(key)))

                    return false;

            }

        }

    } catch (ClassCastException unused)   {

        return false;

    } catch (NullPointerException unused) {

        return false;

    }

 

return true;

}

 

Ahogy az API leírásban szerepel itt egy ciklusban összehasonlítja a Hashtable elemeit. Akkor tekinti egyezőnek a két hash táblát, ha pontosan csak ugyanazokat az elemeket tartalmazzák.

 

Nézzük tovább a stack-et és hatoljunk mélyebbre a „gyári” Java kódban:

Java stack information for the threads listed above:

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

"Thread-1":

        at java.util.Hashtable.size(Hashtable.java:206)

        - waiting to lock <0x24100158> (a java.util.Hashtable)

        at java.util.Hashtable.equals(Hashtable.java:742)

        - locked <0x24100180> (a java.util.Hashtable)

        at Bug$1.run(Bug.java:16)

        at java.lang.Thread.run(Thread.java:619)

"Thread-0":

        at java.util.Hashtable.get(Hashtable.java:333)

        - waiting to lock <0x24100180> (a java.util.Hashtable)

        at java.util.Hashtable.equals(Hashtable.java:755)

        - locked <0x24100158> (a java.util.Hashtable)

        at Bug$1.run(Bug.java:16)

        at java.lang.Thread.run(Thread.java:619)

 

 

Tehát a Java forrásból ez a 742-es és 755-ös sorok érdekesek:

 

public synchronized boolean equals(Object o) {

if (o == this)

    return true;

 

if (!(o instanceof Map))

    return false;

Map<K,V> t = (Map<K,V>) o;

if (t.size() != size())

    return false;

 

    try {

        Iterator<Map.Entry<K,V>> i = entrySet().iterator();

        while (i.hasNext()) {

            Map.Entry<K,V> e = i.next();

            K key = e.getKey();

            V value = e.getValue();

            if (value == null) {

                if (!(t.get(key)==null && t.containsKey(key)))

                    return false;

            } else {

                if (!value.equals(t.get(key)))

                    return false;

            }

        }

    } catch (ClassCastException unused)   {

        return false;

    } catch (NullPointerException unused) {

        return false;

    }

 

return true;

}

 

Java holtpont vizsgálata thread dump segítségével - 3. rész

2008.09.17. 12:36 | gbujdoso | Szólj hozzá!

Címkék: java collection jvm stack thread holtpont dump masterfield thread dump hashtable deadlock util

És még tovább menve...

Java stack information for the threads listed above:

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

"Thread-1":

        at java.util.Hashtable.size(Hashtable.java:206)

        - waiting to lock <0x24100158> (a java.util.Hashtable)

        at java.util.Hashtable.equals(Hashtable.java:742)

        - locked <0x24100180> (a java.util.Hashtable)

        at Bug$1.run(Bug.java:16)

        at java.lang.Thread.run(Thread.java:619)

"Thread-0":

        at java.util.Hashtable.get(Hashtable.java:333)

        - waiting to lock <0x24100180> (a java.util.Hashtable)

        at java.util.Hashtable.equals(Hashtable.java:755)

        - locked <0x24100158> (a java.util.Hashtable)

        at Bug$1.run(Bug.java:16)

        at java.lang.Thread.run(Thread.java:619)

 

...eljutunk a két holtpontot okozó függvényhez:

 

/**

 * Returns the number of keys in this hashtable.

 *

 * @return  the number of keys in this hashtable.

 */

public synchronized int size() {

      return count;

}

 

/**

 * Returns the value to which the specified key is mapped,

 * or {@code null} if this map contains no mapping for the key.

 *

 * <p>More formally, if this map contains a mapping from a key

 * {@code k} to a value {@code v} such that {@code (key.equals(k))},

 * then this method returns {@code v}; otherwise it returns

 * {@code null}.  (There can be at most one such mapping.)

 *

 * @param key the key whose associated value is to be returned

 * @return the value to which the specified key is mapped, or

 *         {@code null} if this map contains no mapping for the key

 * @throws NullPointerException if the specified key is null

 * @see     #put(Object, Object)

 */

public synchronized V get(Object key) {

      Entry tab[] = table;

      int hash = key.hashCode();

      int index = (hash & 0x7FFFFFFF) % tab.length;

      for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {

            if ((e.hash == hash) && e.key.equals(key)) {

                  return e.value;

            }

      }

      return null;

}

 

Tehát van egy synchronized equals függvényünk, amiben van két további lokális synchronized függvényhívás. Ez bizony holtpont! Hogy pontosan megértsük létrejöttét először nézzük meg mit is jelent, ha egy függvényt synchronized kulcsszóval deklarálunk. Amikor egy objektum adott példányán valaki meghívja ezt a függvényt, akkor ehhez az objektumhoz létrejön egy lock, azaz zárolva lesz. Ilyen esetben, ha egy másik szál egy másik (vagy éppen ugyanazt a) szinkronizált metódusát szeretné hívni, akkor várnia kell a végrehajtással. A dumpban látszik, hogy a két szál kölcsönösen a másik szál által korábban létrehozott zár feloldására vár.

"Thread-1":

        at java.util.Hashtable.size(Hashtable.java:206)

        - waiting to lock <0x24100158> (a java.util.Hashtable)

        at java.util.Hashtable.equals(Hashtable.java:742)

        - locked <0x24100180> (a java.util.Hashtable)

        at Bug$1.run(Bug.java:16)

        at java.lang.Thread.run(Thread.java:619)

"Thread-0":

        at java.util.Hashtable.get(Hashtable.java:333)

        - waiting to lock <0x24100180> (a java.util.Hashtable)

        at java.util.Hashtable.equals(Hashtable.java:755)

        - locked <0x24100158> (a java.util.Hashtable)

        at Bug$1.run(Bug.java:16)

        at java.lang.Thread.run(Thread.java:619)

 

Érdemes elgondolkodnunk a hiba leírásában szereplő tanulságon:

"Never call foreign code while holding a lock."

Azaz egy szinkronizált függvényhívásból soha ne hívjunk ki más függvénybe (az adott objektumon belül).

 

Egy lehetséges javítása a problémának, hogy a size és get metódusokban lévő kódot bemásoljuk közvetlenül az equals függvény megfelelő helyére. Ilyen esetben szálanként csak egy-egy lockunk lesz, ami így is elég.

 

Amennyiben bárkinek további helyes megoldási javaslata van és azt kidolgozva elküldi az „info kukac masterfield.hu” címre 10% kedvezményt kap a Masterfield Oktatóközpont bármelyik tanfolyamának árából.

 

A fenti deadlockhoz hasonlóval mindannyian találkoztunk már, csak esetleg nem is tudtunk róla, hogy a háttérben ezen hibás működés áll. Mindenki találkozott már lefagyott számítógéppel és bármit csinált nem bírta kimozdítani ebből a holtpontból. Ahogy azt a bevezetőben említettem nagyon sok programozó nincs is tisztában a holtpontot előidéző helyzetekkel és nem tudja, hogy amit leír az potenciálisan tartalmazhat-e ilyen pontot.

Véleményem szerint az informatika egyik jelenlegi, nagyon fontos és megoldásra váró kihívása ezen holtpontok minél egyszerűbb felismerése még a program készítésének szakaszában. Illetve az operációs és egyéb futtató keretrendszerek (VM-ek) felkészítése a holtpontok felismerésére és feloldására.

 

Ujjlenyomatozás

2008.09.04. 09:33 | gyuria | Szólj hozzá!

Címkék: ujjlenyomat azonosítás fingerprint neurotechnology

Nemrégiben egy ügyviteli rendszerbe kellett ujjlenyomat azonosítást beépítenem a felhasználók számára, előzetes költségbecsléssel. A feladat először nem tűnt bonyolultnak, de utólag már látom, hogy mennyi munkával járt, így szerintem megér egy postot.

Tudtam, hogy a Microsoft rendelkezik valami saját ujjlenyomat olvasóval, ebből gondoltam, hogy a beépítés gyerekjáték lesz és nem drága az ügyfelek számára. Az első csalódás akkor ért, amikor rájöttem, hogy a Microsoft terméke bizony nem sok mindenre használható, számomra pedig semmire. Külső alkalmazásba nem lehet integrálni, gyakorlatilag csak arra jó, hogy website-okon beírja a jelszót, ha rátesszük az ujjunkat.

Alaposabb kutatásba kezdtem. Kiderült, hogy sok gyártónak van ilyen hardvere, de szinte mindegyik csak a saját eszközéhez gyárt API-t. Mivel egy dobozos termékhez kellett ezt a funkciót kifejleszteni, nem akartam egyik hardver gyártóhoz sem elkötelezni magam, több API-t kezelni pedig még annyira sem. Így találtam rá egy biometrikus azonosítással foglalkozó szoftver cégre, aki nagyon sok típusú ujjlenyomat olvasóhoz rendelkezik egy egységes API-val.

Ekkor jött a második komoly csalódás, ugyanis már az API is pénzbe került, a Standard változata 339 EUR. Ezután még minden számítógépre kell licenszet venni (kb. 40 EUR/licensz volt, 2008 szeptembertől sokkal olcsóbb lett), ahol használni akarom és természetesen maga a hardver sem olcsó. De hasonló árakat találtam mindenhol, és a trial alapján ez a cég jónak tűnt.

Mindenféle programnyelvre (Delphi 7, VB.NET, C#, Java, C++, Access, VB6, Linux GTK stb.) volt API-juk és jó Demo programok. Az ujjlenyomat beolvasás első lépése egy egyszerű scan, amelynek eredménye egy sima kép (NImage osztály). A kép letárolása feleslegesnek tűnt, de mivel jópofa dolog az alkalmazásban megjeleníteni a képet, így mentettem azt is. A képből az algoritmus kikeresi (NFExtractor osztály) az egyedi pontokat, vonalakat, szögeket, irányokat és egy ún. minutiae-t vagy kivonatot készít belőlük (NFRecord osztály). Ebből pedig egy Byte tömb készül (NFPackedRecord). Na ezt érdemes igazából letárolni, mert az azonosításhoz úgyis ez kell és ez a legkisebb helyigényű. (3-5kB).

A keresésre és az azonosításra is külön osztály van (NFMatcher). A felismerés maga egy állítható valószínűség alapján megy. Tehát ha akarjuk, a cucc nagyon-nagyon ritkán látja két ember ujjlenyomatát azonosnak, de így előfordulhat az is, hogy bizony ismételni kell a beolvasást, mert ugyanannak az embernek kétszer egymás után beolvasott ujjlenyomatait sem találja egyezőnek. Ugyanígy beállíthatjuk úgy is, hogy gyakrabban előfordul a téves felismerés, de szinte soha nem kell ismételni a beolvasást. Minden alkalmazáshoz meg kell találni a megfelelő egyensúlyt.

Sajnos a tapasztalat az, hogy a képet is és a kivonatot is le kell tárolni. A kivonatot azért, mert ez alapján történik az azonosítás és ha egyezést keresünk, de nincs kivonat, akkor minden letárolt képből először kivonatot kell készítenünk, ami időigényes. A kép pedig két ok miatt kell: egyrészt meg tudjuk mutatni a felhasználónak (ez ugye menő), másrészt gyakran változik a képből kinyerhető kivonat technikája, ahogy fejlődik a technológia. Ez velem is megesett már. És mivel a képek tárolásra kerültek, a szoftver frissítésben ki tudtuk azt is küldeni, hogy minden letárolt képhez generálja újra a kivonatokat is.

A licenszelésük és az automatizált telepítésük külön szívás volt:

  • csak online lehetett aktiválni, maximális aktiválási limittel (2 vagy 3 azt hiszem)
  • egy saját service-nek folyamatosan futnia kell, hogy használni lehessen
  • újraaktiválás előtt deaktiválni kellett a régi gépen és ezt elküldeni nekik, hogy a maximális aktiválások számát megnöveljék
  • ha egy gép elszállt és nem tudtad deaktiválni a licenszt (ügyfeleknél azért gyakran előfordul), akkor úgy kell könyörögni nekik, hogy ugyan már hagy aktiváljál újra azzal a licensszel egy másik gépen

Az API, amivel dolgoztam, rengeteg egyéb számomra kevésbé fontos dolgot is tudott, ennek megfelelően az ára is igen magas. Ennek a cégnek egyébként van retina, arc és egyéb különleges biometrikus felismerő algoritmusa is - részben béta állapotban, sajnos mindegyik külön megvásárolandó, igen borsos áron.

Összességében a beépítés teljesen korrekten, és mindent lekezelve sokkal több időt vett igénybe, mint terveztem (kb. 5 nap). Ehhez jön még a keresés ideje, amire remélem ennek a bejegyzésnek az ismeretében másoknak már nem lesz szüksége.

Ja, és persze két ismert általános tévedés is cáfolásra került:

  • Minden ujjunknál különbözik az ujjlenyomat, így ugyanazt az ujjunkat kell használni (vagy minden ujjat külön letárolni és mindegyikhez képest vizsgálni)
  • A filmekben, amikor pörög a képernyőn a sok ujjlenyomat, baromság. Az algoritmus sokkal gyorsabb egy átlagos pc-n is, ha kitennénk minden képet, jelentősen lassítaná a felismerést (még esetleg 89-ben tudott úgy működni).

Elindultunk

2008.09.01. 22:40 | masterfield | 1 komment

Címkék: blog start indulás masterfield

Elindult a Masterfield IT Oktatóközpont szakmai blogja. Szeretnénk olyan érdekességeket bemutatni, amelyeket oktatóink munkájuk során tapasztaltak. A lehetőségekhez képest mindezt - amennyire csak lehet - reklámmentesen, természetesen nem titkolva, hogy ki áll a kezdeményezés mögött.

Fő területünk a szoftverfejlesztés, így terveink szerint ez a vonal lesz a legerőteljesebb ezen a blogon, de szerepelni fognak egyéb oktatott területekről is érdekességek: IT biztonság, adatbázisok, bankinformatika és pénzügyek, tesztelés.

süti beállítások módosítása