Mostly-Concurrent Mark & Sweep GC $B$N%"%k%4%j%:%`(B

$B:n@.F|!'(B2004.01.24
$B99?7F|!'(B2005.11.27

$BL\

1. $BGX7J(B

$B%,!<%Y!<%8%3%l%/%7%g%s(B(GC) $B$K$O?'!9$J%"%k%4%j%:%`$,B8:_$9$k$,!"Bg;(GD$K8@$C$F(B Stop-the-World (STW) $B7?(B GC $B$H(B On-the-fly $B7?(B GC $B$KBgJL$5$l$k!#(B

STW $B7?$N(B GC $B$O%W%m%0%i%`$N

$B0lJ}!"(BOn-the-fly $B7?(B GC $B$O%W%m%0%i%`$N

$B$3$NOC$rJ9$/$H!"(BGC $B$NJ}<0$H$7$F$O(B On-the-fly $B7?(B GC $B$NJ}$,(B STW $B7?(B GC $B$h$jM%$l$F$$$k$h$&$KJ9$3$($k$,!"$=$&$OLd20$,2<$m$5$J$$!#(B $B0lHL$K(B GC $B$rA*$V;XI8$H$7$F$O(B$B%9%k!<%W%C%H(B(throughput)$B@-G=(B$B$H(B$B%l%9%]%s%9(B(response)$B@-G=(B$B$N(B 2 $B$D$,$"$k!#(B

On-the-fly $B7?(B GC $B$O(BGC $B$K$h$kDd;_$,$J$$$N$G%l%9%]%s%9@-G=$OHs>o$K$h$$!#(B $B$@$,!"(BOn-the-fly $B7?(B GC $B$rH$r;}$D%*%V%8%'%/%H$r2s<}$G$-$J$$(B)$B$r;}$C$F$$$k!#(B

$B0lJ}!"(BSTW $B7?(B GC $B$O!V(BGC $B$K$h$kDd;_;~4V!W$r64$`I,MW$,$"$k$N$@$,!"(BGC $B$rl9g$K3]$k%3%9%H$,(B On-the-fly $B7?(B GC $B$h$jDc$/!"%9%k!<%W%C%H@-G=$r9b$a$k$3$H$,$G$-$k!#(B $B$3$l$^$G(B Java $B8@8l$N3hLv$9$k=tJ,Ln$G$O%l%$%F%s%7!<@-G=$h$j$b%9%k!<%W%C%H@-G=$,MW5a$5$l$k$3$H$,B?$+$C$?$N$G!"2a5n$N(B JavaVM $B$N$[$H$s$I$,(B STW $B7?(B GC $B$r:NMQ$7$F$-$?!#(B

$B$7$+$7!":G6a$N(B Java $B%7%9%F%`$G$O:F$S%l%$%F%s%7@-G=$,=E;k$5$l$k$h$&$K$J$j$D$D$"$k!#(B $B%a%b%j$NDc2A3J!&BgMFNL2=!"(B64 $B%S%C%H%W%m%;%C%5$NIa5Z$KH<$C$F(B JavaVM $B$,;H$($k!&;H$&%a%b%jNL$OA}Bg$7$F$$$k!#(B STW $B7?(B GC $B%"%k%4%j%:%`$NB?$/$O!"(BGC $B$,4IM}$7$F$$$k%a%b%jNL!"@8B8$7$F$$$k%*%V%8%'%/%H$N8D?t!"@8B8$7$F$$$k%*%V%8%'%/%H$N;2>H?t$N$$$:$l$+$KHfNc$9$k$?$a!"(BGC $BDd;_;~4V$,$I$s$I$s?-$S$k798~$,$"$k$N$G$"$k!#(B $B%.%,%P%$%H$r1[$($k$h$&$J%a%b%j$r;HMQ$7$?>l9g!"(BGC $B$K$h$kDd;_;~4V$,(B 10 $BIC$r1[$($k$h$&$J%Q%?!<%s$N8=$l$F$$$k!#(B

$B$=$N$?$a%9%k!<%W%C%H@-G=$H%l%$%F%s%7@-G=$rN>N)$5$;$k$h$&$J(B GC $B%"%k%4%j%:%`$,I,MW$K$J$k!#(B $B0J2Mostly Concurrent GC $B$H$O(B STW $B7?$H(B On-the-fly $B7?$N$"$$$N;R$N$h$&$J(B GC $BJ}<0$G$"$k!#(B


2. HotSpot VM 1.4.x $B$N(B GC $B$N
($B$3$N>O$O!"JL$NJ8=q$+$i$N@Z$jD%$j$J$N$G<}$^$j$,0-$$$,(B $B5$$K$7$J$$$G!#(B)

Sun $B$N(B Java2SE JDK $B$N(B JavaVM $B$OJ#?t$N%,!<%Y!<%8%3%l%/%7%g%s(B (GC) $B%"%k%4%j%:%`$,

Sun HotSpot VM 1.4.2 $B$+$i$O0J2<$N$h$&$J;XDj$,2DG=$G$"$k!#(B

GC $B $B%*%W%7%g%s(B $B798~!&E,@5(B $B@bL@(B
$B%N!<%^%k(B $BL5;XDj(B $B4pK\(B Copying GC $B$H(B Mark & Compact $B$rAH$_9g$o$;$?@$BeJL(B(Generational) GC$B!#(B $B$3$l$,4pK\$K$J$k!#(B
$B%Q%i%l%k(B GC -XX:+UseParallelGC $B%5!<%P! $B%9%k!<%W%C%H=E;k(B $B%N!<%^%k$HF1MM$N@$BeJL(B GC $B$@$,!"(B $B?7@$BeB&$N(B Copying GC $B$r(B Parallel Copying GC $B$KCV$-49$($?$b$N!#(B Minor GC (1$B2s$N=hM};~4V$,C;$/!"H/@8IQEYB?(B)$B!"(B Major GC (1$B2s$N=hM};~4V$,D9$/!"H/@8IQEY>.(B) $B$N$&$A(B Minor GC $B$,(B JavaVM $B$rDd;_$9$k;~4V$,C;=L$5$l $B$?$@$7(B Major GC $B$K$O2~A1$,$J$$$?$a!"(B $B%l%9%]%s%9%?%$%`$N:G0-CM$O2~A1$7$J$$!#(B
$B%3%s%+%l%s%H(B GC -Xconcgc $B%5!<%P! $B%l%9%]%s%9=E;k(B $B@$BeJL(B GC $B$@$,!"(B $B5l@$BeB&$r(B Mostly-concurrent Mark & Sweep $B%"%k%4%j%:%`$rCV$-49$($?$b$N!#(B Major GC $B$,(B JavaVM $B$rDd;_$9$k;~4V$rC;=L$9$k$N$G!"(B $B%l%9%]%s%9%?%$%`$N:G0-CM$r2~A1$G$-$k!#(B
$BDI2C$N%*%W%7%g%s(B -XX:+UseParNew $B$r;XDj$9$k$3$H$G!"(B -XX:+UseParallelGC $B$HF1MM$NJBNs(B GC $B$r(B $B;HMQ$9$k$3$H$b$G$-$k!#(B $B$3$N>l9g!"%9%k!<%W%C%H@-G=$b2~A1$5$l$k!#(B

$B$3$3$G$O(B $B%3%s%+%l%s%H(B(Concurrent) $B$H$$$&8@MU$O(B On-the-fly $B$H$$$&F15A$G$"$k!#(B
$B%$%s%/%j%a%s%?%k(B GC -Xincgc $B%/%i%$%"%s%H8~$1(B
$B%l%9%]%s%9=E;k(B
Train GC $B%"%k%4%j%:%`$rMQ$$$?%$%s%/%j%a%s%?%k(B GC$B!#(B $B%a%b%j%5%$%:$,>.$5$$%"%W%j%1!<%7%g%s(B(64MB $B0J2 $B%a%b%j%5%$%:$rA}$d$7$?>l9g(B $B%9%k!<%W%C%H$b%l%9%]%s%9$bDc2<$9$k!#(B

$B$3$N%Z!<%8$G$O?7$7$$%3%s%+%l%s%H(B GC $B$N%"%k%4%j%:%`$r@bL@$9$k!#(B


3. Mostly-concurrent Mark & Sweep

HotSpot VM 1.4.x $B$,:NMQ$7$?%3%s%+%l%s%H(B GC $B$O(B Mostly-concurrent Mark & Sweep $B$G$"$k!#(B

$B$3$N%"%k%4%j%:%`$O!"(BHans-J. Boehm$B!"(BAlan J. Demers$B!"(BScott Shenker $B$N(B 3 $B?M$,(B 1991 $BG/$KH/I=$7$?(B[1] Mostly Parallel Garbage Collection (PLDI 1991) $B$r%Y!<%9$K(B Tony Printezis $B$H(B David Detlefs $B$,BgI}$K2~NI$7$?(B[2] A Generational Mostly-concurrent Garbage Collection (ISMM 2000) $B$G$"$k!#(B $B0J9_!"(BM-CMS $B$H>JN,$9$k$3$H$K$9$k!#(B

M-CMS $B$O(B Mark & Sweep $B%"%k%4%j%:%`$,4pK\$K$J$C$F$$$k!#(B

Mark & Sweep $B%"%k%4%j%:%`$O!"%W%m%0%i%`$,%a%b%j$r;H$$2L$?$7$?$H$-$K%W%m%0%i%`$rl9g$O(B Java $B%9%l%C%I(B)$B$r0l;~Dd;_$5$;$F(B 1. 2. $B$N%U%'!<%9$r=g$K

1. $B%^!<%/(B $B%U%'!<%:(B (Mark phase)
$B!V@8$-$F$$$k!W%*%V%8%'%/%H$NFbIt$N%]%$%s%?$r$R$H$D$E$D$B%^!<%/(B(mark) $B$7$F$f$/%U%'!<%:!#(B $B%^!<%/$N=hM}$,$9$Y$F40N;$7$F%^!<%/$9$Y$-%*%V%8%'%/%H$,$J$/$J$C$?>l9g!"%^!<%/$N$D$$$F$$$J$$%*%V%8%'%/%H$,(B$B$4$_(B(garbage) $B$H$J$k!#(B
2. $B%9%$!<%W(B $B%U%'!<%:(B (Sweep phase)
$B6u4V$r@hF,$+$i:G8e$K=g$KAv::$7$F$f$-%^!<%/$N$D$$$F$$$J$$$4$_$rC5$9%U%'!<%:!#(B $B$4$_$O%U%j!<%j%9%H$K$D$J$2$k$3$H$G6u$-NN0h$H$7$F2s<}$r9T$&!#(B $BA08e$N6u$-NN0h$rO"7k$9$k=hM}$b0l=o$K9T$&!#(B

2. $B$,40N;$9$k$H(B JavaVM $B$O(B Java $B%9%l%C%I$r:F5/F0$7$F%W%m%0%i%`$r:F3+$9$k!#(B

$B%3%s%+%l%s%H(B $B%^!<%-%s%0(B

M-CMS $B$O(B Mark & Sweep $B$,(B JavaVM $B$,%W%m%0%i%`$rDd;_$9$k;~4V$r:o8:$9$k$3$H$rA@$C$F!"(B1. $B$N%^!<%/%U%'!<%:$r2~NI$7$F$$$k!#(B M-CMS $B$OA02s$N(B GC $B$,=*$o$C$F(B Java $B%9%l%C%I$r:F3+$9$k$N$HF1;~$K!"%^!<%-%s%0=hM}$r9T$&FCJL$J%^!<%-%s%0%9%l%C%I$rJB9T$7$F

$B$D$^$j!"(BGC $B$,=*N;$7$?;~E@$G(B (1)$B!"(B(2)$B!"(B(3)$B!"(B(4) $B$N%*%V%8%'%/%H$,@8$-$F$$$?$N$J$i!"%^!<%-%s%0%9%l%C%I$O(B Root $B$+$i=gHV$K(B (1) $B"*(B (2) $B"*(B (3) $B$H$$$&$h$&$K%^!<%-%s%0$7$F$f$/!#(B Java $B%9%l%C%I$bFHN)$7$FF0$$$F$$$k$N$G%^!<%-%s%0%9%l%C%I$,%^!<%/=hM}$r9T$&A0$K(B (3) $B"*(B (4) $B$N;2>H$,@Z$jN%$5$l$l$P(B (4) $B$O%^!<%-%s%0$5$l$:%,!<%Y!<%8$H$J$k!#(B


$B%k!<%H(B(root) $B$O(B Java $B%9%l%C%I$+$iD>@\;X$5$l$F$$$k%*%V%8%'%/%H$d%7%9%F%`$KEPO?$5$l$?%*%V%8%'%/%H$J$I(B GC $B$,!V@8$-$F$$$k!W$H2>Dj$9$k%*%V%8%'%/%H$N$3$H!#(B

$B%3%s%+%l%s%H(B $B%^!<%-%s%0$NLdBjE@(B

$B$3$N=hM}$K$O(B 2 $B$D$NLdBjE@$,$"$k!#(B

(A) $B%^!<%/O3$l(B
$B$$$C$?$s%^!<%/$5$l$?%*%V%8%'%/%H$KJL$N%*%V%8%'%/%H$,%j%s%/$5$l$?>l9g$K$O%^!<%/O3$l$,5/$-$k!#(B
$BNc$($P(B (5) $B$,$"$i$?$K@8@.$5$l!"$3$l$,(B (1) $B$K%j%s%/$5$l$?$H$9$k!#(B (1) $B$O$9$G$K%^!<%/:Q$_$J$N$G(B (1) $B"*(B (5) $B$N%j%s%/$rC)$l$J$$!#(B
(B) $BM>J,$J%^!<%/(B
$B$$$C$?$s%^!<%/$5$l$?%*%V%8%'%/%H$,(B Root $B$+$i$N%Q%9$+$i@Z$jN%$5$l$k$3$H$G!"(B $B$4$_%*%V%8%'%/%H$H$J$k2DG=@-$,$"$k!#(B
$BNc$($P(B (3) $B$O(B (2) $B"*(B (3) $B$N%j%s%/$,$"$k4V$K(B $B%^!<%/%9%l%C%I$,%^!<%/$r$7$F$7$^$C$?$N$@$,!"(B Java $B%9%l%C%I$,%j%s%/$r@Z$C$F$7$^$$(B $BK\Ev$O$4$_$K$J$C$F$7$^$C$?(B(*1)$B!#(B

2 $B$D$NLdBj$N$&$A(B (B) $BM>J,$J%^!<%/(B $B$O(B $BL5;k$9$k$3$H$,2DG=$@!#(B $B$4$_$H$J$C$F$$$k%*%V%8%'%/%H$,!V@8$-$F$$$k!W$H$_$J$5$l$k$H(B GC $B$r@8$-;D$k%*%V%8%'%/%H$NNL$,L5BL$KA}$($F%a%b%j$r05Gw$9$k$,!"(B $BB>$N$4$_$r==J,$K2s<}$G$-$l$P%W%m%0%i%`$NF0:n<+BN$K$OLdBj$,$J$$!#(B M-CMS $B$G$OM>J,$K%^!<%/$5$l$?%*%V%8%'%/%H$O2s<}$7$J$$!#(B

$B0lJ}!"(B (A) $B%^!<%/O3$l(B $B$O7h$7$F5v$5$l$J$$!#(B $B%^!<%/O3$l%*%V%8%'%/%H$,$"$k$H!"(B $B$=$l$,

$B%i%$%H%P%j%"(B (write barrier)

M-CMS $B$O$3$N%^!<%/O3$l$K0J2<$N$h$&$KBP=h$9$k!#(B
$B$^$:!"(B GC $B%9%l%C%I$O!V(BRoot $B$+$iE~C#2DG=$+$I$&$+!W$r%A%'%C%/$9$k$?$a$K(B $B%*%V%8%'%/%H$K%^!<%/$r9T$C$F$$$?$,!"(B $B$3$l$H$OJL$K(B $B!V=q$-49$($i$l$?%*%V%8%'%/%H!W$r%A%'%C%/$9$k$?$a$KJLobject1 $B$N%U%#!<%k%I$K(B $B$J$s$i$+$N%*%V%8%'%/%H$N;2>H$r=q$-9~$`>l9g!"(B object1 $B$K!V=q$-9~$^$l$?!W$H$$$&0u$rIU$1$k$N$G$"$k!#(B $B$3$N=hM}$r(B $B%i%$%H%P%j%"(B (write barrier) $B$H8F$V!#(B
object2 $B$,(B null $B$G$J$$>l9g$O!"$I$s$J%*%V%8%'%/%H$G$b%A%'%C%/$r9T$&!#(B

void method( Class1 object, Class2 object2 ){
  object1.field = object2;
}

$B%i%$%H%P%j%"$5$l$?8e$N!"%a%b%jCf$N%$%a!<%8$H$7$F$O2<$N?^$N$h$&$K$J$k!#(B

$B%3%s%+%l%s%H%^!<%-%s%0$N8e=hM}(B

M-CMS $B$O!V%3%s%+%l%s%H!W$K9T$o$l$?%^!<%-%s%0=hM}$N%^!<%/O3$l$KBP=h$9$k$?$a$K!"(B $BDL>o$N(B Mark & Sweep $B$N$h$&$K(B JavaVM $B$rDd;_$9$k!#(B $B$=$7$F(B $B%R!<%W%a%b%jCf$K$"$k!VESCf$G=q$-49$($i$l$?%*%V%8%'%/%H!W$+$i;D$j$N%^!<%-%s%0=hM}$r9T$C$F9T$/!#(B

$B?^$@$H(B (1)$B!"(B(2)$B!"(B(3) $B$,%^!<%-%s%0$N3+;OE@$K$J$j!"(B $B%^!<%/$KO3$l$F$$$?(B (5) $B$,H/8+$5$l$k!#(B

$B$3$N$h$&$K(B M-CMS $B$O%^!<%-%s%0=hM}$r!"(B $BJB9T(B($B%3%s%+%l%s%H(B)$B$K9T$&ItJ,$H(B $BC`

$B%9%$!<%T%s%0%U%'!<%:(B (Sweeping Phase)

$B%^!<%/$N=*$o$C$?%R!<%W6u4V$NCf$G(B $B%,!<%Y!<%8$H$J$C$?%*%V%8%'%/%H$r=|5n$7(B $B%U%j!<%j%9%H$r:n$kA`:n$r(B$B%9%$!<%T%s%0(B (Sweeping) $B$H$$$&!#(B Sweeping $B$O(B $BO"B3$7$?6u$-NN0h$r7k9g$9$k(B Coalescing $B$r4^$`$N$,IaDL$G$"$k!#(B
$B$3$NA`:n$O%3%s%+%l%s%H$K9T$&$3$H$,$G$-$k$N$@$,!"(B $B%m%C%/A`:n$N7Z8:$N$?$a$K(B Sun HotSpot VM 1.4.x $B$G$O%3%s%+%l%s%H$K9T$C$F$$$J$$$O$:!#(B

($BDI5-(B)
Sun HotSpot 1.4.2 $B0J9_$N(B M-CMS $B$O%9%$!<%T%s%0!&%U%'%$%:$r(B $B%3%s%+%l%s%H$K9T$C$F$$$k!#(B

4. $B1~MQ(B

$B>e5-$N$h$&$J(B M-CMS $B$@$,!"(B $B5;=QE*$K$O$5$i$K9)IW!&:GE,2=$,2DG=$@!#(B

4.1 $B@$BeJL(B GC $B$H$NAH$_9g$o$;(B

Printezis $B$i$NO@J8(B [1] $B$G$O!"(B M-CMS $B$H@$BeJL(B GC $B$rAH$_9g$o$;$k$3$H$G@-G=$N8~>e$rA@$C$F$$$k!#(B $B$3$N>l9g!"(B $B?7@$BeB&$N%^%$%J!<(B GC $B$K(B Cheney $B%9%?%$%k$N(B Copying GC $B$,!"(B $B5l@$BeB&$N%a%8%c!<(B GC $B$K(B M-CMS $B$,;HMQ$5$l$k!#(B

$B%^%$%J!<(B GC $BB&$N(B Copying GC $B$O(B STW $B$r9T$&$?$a(B GC $BDd;_;~4V$,B8:_$9$k!#(B $B$?$@0lHL$K%^%$%J!<(B GC $B$NDd;_;~4V$OC;$/!"(B $B1?MQ>e:9$7;Y$($J$$HO0O$NDd;_$G$"$k$H9M$($F$3$l$r5vMF$9$k!#(B

$B%a%8%c!<(B GC $BB&$N(B M-CMS $B$O!"(B $B@$Be$rJ,$1$?$3$H$K$h$j0J2<$N$h$&$J%a%j%C%H$rF@$k!#(B

$B$?$@

4.2 $B%+!<%I%^!<%-%s%0(B (Card Marking)

$B$^$?(B Printezis $B$i$NO@J8(B [1] $B$G$O!"(B $B%i%$%H%P%j%"=hM}$K$O(B$B%+!<%I%^!<%-%s%0(B(Card Marking)$B$r;HMQ$7$F$$$k!#(B

$B$3$l$O=q$-49$($,$"$C$?%*%V%8%'%/%H$r(B $B%*%V%8%'%/%HC10L$G4IM}$9$k$N$G$O$J$/!"(B $B%R!<%W6u4V$r0lDj$N%5%$%:(B ($BO@J8$G$O(B 512 $B%P%$%H(B) $B$KJ,3d$7$F4IM}$9$k(B($B$3$l$,%+!<%I(B)$B!#(B $B%+!<%IFb$N%*%V%8%'%/%H$,=q$-49$($i$l$?>l9g$K$O!"(B $B%+!<%IFb$NA4$F$N%*%V%8%'%/%H$,=q$-49$($i$l$HH=CG$9$kJ}<0$G$"$k!#(B $B%+!<%IFb$N%*%V%8%'%/%H$,!V1x$l$?(B($B=q$-49$($i$l$?(B)$B!W$+$I$&$+$O!"(B $B%R!<%W6u4V$N30B&$K$"$k@lMQ$N%F!<%V%k$G4IM}$5$l$k!#(B

$B$3$l$OBg;(GD$JJ}K!$K46$8$k$,!"(B JavaVM $B$Ne%*%V%8%'%/%H$N%X%C%@!<$O(B 2 $B%o!<%IDxEY$J$N$G(B $B$$$m$$$m$J>pJs$r5M$a9~$`M>M5$,$J$$$N$G$"$k!#(B

$B%i%$%H%P%j%"=hM}$O0J2<$N$h$&$J%3!<%I$K$J$k!#(B putfield$B!"(Bputstatic$B!"(Baastore $B$J$I$N(B $B%P%$%H%3!<%IL?Na$r

#define CARD_SIZE  512
#define DIRTY_MASK ((unsigned char)-1)

/* $B%+!<%I%F!<%V%k(B */
unsigned char card_marking_table[CARD_SIZE];

void write_barrier(Object* object) {
  int offset = ((intptr_t)object) / CARD_SIZE;
  card_marking_table = DIRTY_MASK;
}

$B3F%+!<%I$KBP$7$F$O%/%j!<%s(B or $B%@!<%F%#!<$r<($9$K$O(B 1 $B%S%C%H$G$h$$$N$@$,!"(B $B%i%$%H%P%j%"=hM}$OJ#?t$N(B Java $B%9%l%C%I$+$iJBNs$K9T$o$l$k$?$a(B $B%S%C%HA`:n$K$O%"%H%_%C%/(B(atomic)$BL?Na$,I,MW$K$J$C$F$7$^$&!#(B $B$=$&$J$k$H%^%k%A(B CPU $B$G$NE]$@!#(B unsigned char(8 $B%S%C%H(B) $B$G9=@.$9$k$H$A$g$C$HL5BL$K$h$&$K;W$($k$,!"(B $B$[$H$s$I$N(B CPU $B$G(B1$B%P%$%H$NFI$_=q$-$OIT2DJ,$K$J$k$N$G%"%H%_%C%/L?Na$d%m%C%/A`:n$,ITMW$K$J$k!#(B $B$^$?(B M-CMS $B$N(B GC $B%"%k%4%j%:%`$N9bB.2=$r9T$C$F$$$k$H!"(B 1$B$D$N%+!<%I$KBP$7$FJ#?t$N%Q%i%a!<%?$r;}$?$;$?$/$J$k$N$G(B $B>/$7I}$,$"$C$F$b$A$g$&$INI$$!#(B

4.3 $BJBNs2=(B (Parallel GC)

$BJBNs(B GC (Parallel GC) $B$O!"(B GC $B$rJ#?t$N(B GC $B%9%l%C%I$GJ,C4$7$F=hM}$9$k(B GC $BJ}<0$@!#(B M-CMS $B$N>l9g$O(B concurrent marking $B%U%'!<%:!"(Bserial marking $B%U%'!<%:!"(Bsweep $B%U%'!<%:$H$$$&(B 3$B$D$N%U%'!<%:$,$"$k$,!"(B $B$=$l$>$l$rJBNs2=$9$k$3$H$,2DG=$@!#(B

Serial marking $B%U%'!<%:$O(B $B$9$Y$F$N(B Java $B%9%l%C%I$rDd;_$5$;$?>e$G9T$&(B STW $B=hM}$J$N$G!"(B $BM}O@E*$K$O(B CPU $B?t$HF1?t$N(B GC $B%9%l%C%I$r5/F0$7$F(B $BIi2Y$rJ,;62=$9$l$P=hM};~4V$O:G>.$K$J$k(B(*2)$B!#(B Serial marking $B%U%'!<%:$N=hM};~4V$,:G>.$K$J$k$3$H$,!"(B $B$=$N$^$^(B GC $BDd;_;~4V$N:G>.2=!"@-G=$N:GBg2=$H$J$k!#(B

$B0lJ}!"(Bconcurrent marking $B%U%'!<%:$H(B sweep $B%U%'!<%:$O(B Java $B%9%l%C%I$HJ?9T$KF0:n$7$F$$$k$?$a!"(B Java $B%W%m%0%i%`$N?J9T>u67$H(B GC $B$N?J9T>u67$,%P%i%s%9$h$/$J$k$h$&$KJBNs2=$r9T$&I,MW$,$"$k!#(B $B4pK\E*$K$O(B Java $B%9%l%C%IB&$,%a%b%j$r>CHq$9$k%9%T!<%I$H!"(B GC $B%9%l%C%IB&$,%a%b%j$r2s<}$9$k%9%T!<%I$,$@$$$?$$F1$8$K$J$k$h$&$K!"(B $BJBNs$KF0:n$9$k(B GC $B%9%l%C%I$N?t$rD4@0$9$k!#(B

4.4 $B%S%C%H%o%$%:!&%9%$!<%W(B (Bitwise Sweep)

$B%*%V%8%'%/%H$NB8:_$9$k0LCV$d%*%V%8%'%/%H$N%^!<%-%s%0%U%i%0$r$"$i$o$9$N$K!"(B $B%R!<%W6u4V$N30B&$K%S%C%H%^%C%W$rMQ0U$9$kJ}K!$,$"$k!#(B $B%R!<%W6u4VCf$K%*%V%8%'%/%H$,(B 8 $B%P%$%H6-3&$KJB$s$G$$$k$H$9$k$H!"(B $B%R!<%W6u4V%5%$%:$N(B 1/64 $B$N%S%C%H%^%C%W$rMQ0U$9$l$P%R!<%W6u4V$rLVMe$G$-$k!#(B

$B0J2<$N(B 2 $BKg$N%S%C%H%^%C%W$rMQ0U$9$k!#(B

Sweep $B%U%'!<%:$N:]$K(B 2 $BKg$N%S%C%H%^%C%W$r;2>H$9$k$3$H$G%,!<%Y!<%8$N0LCV$rH/8+$7!"2s<}$9$k$3$H$,2DG=$@!#(B $B%R!<%W6u4V$rgS$a$k$h$j!">.$5$J%S%C%H%^%C%W$r;2>H$9$kJ}$,$O$k$+$K8zN($,$h$$!#(B

$B$?$@$7%S%C%H%^%C%W$rJBNs!&J?9T$KF0:n$9$k%9%l%C%I$,F1;~$K=q$-9~$_$r9T$&$H$9$k$HCm0U$,I,MW$K$J$k!#(B $BJ#?t$N%9%l%C%I$,%S%C%HA`:n$r9T$&$K$O!"%"%H%_%C%/L?Na$,I,MW$J$N$@!#(B $B$3$l$r7Z8:$9$k$?$a$K$O$$$/$D$+$N:GE,2=$r9T$&!#(B

4.5 $B%$%s%/%j%a%s%?%k!&%3%s%Q%/%7%g%s(B (Incremental Compaction)

M-CMS $B$r4^$`(B Mark & Sweep $B$O!"(B $B@8$-$F$$$k%*%V%8%'%/%H$r;D$7$F%,!<%Y!<%8$H$J$C$?%*%V%8%'%/%H$r2rJ|$7$F$$$/$N$G!"(B $B2rJ|$5$l$?%9%Z!<%9(B($B%U%j!<%9%Z!<%9(B)$B$OO"B3$7$?6u4V$K$O$J$i$:!"(B $B%R!<%W6u4V$,Cn?)$$>uBV$K$J$C$F$$$/!#(B $B%U%i%0%a%s%F!<%7%g%s2=$G$"$k!#(B $B$3$l$r2sHr$9$k$?$a$K$O!"(B $B@8$-$F$$$k%*%V%8%'%/%H$N0LCV$r$:$i$7$F0l2U=j$K4s$;$kA`:n!"%3%s%Q%/%7%g%s(B(Compaction)$B$,I,MW$K$J$k!#(B

$B%3%s%Q%/%7%g%s7?(B GC $B$NBeI=$O(B Mark & Compact $B$G!"(B Mark & Sweep $B$N(B sweep phase $B$r(B compaction phase $B$KCV$-49$($?$b$N$@!#(B $B$?$@%9%$!<%W$,(B Java $B%9%l%C%I$H%3%s%+%l%s%H$K=hM}$G$-$k$N$H0c$$!"(B $B%3%s%Q%/%7%g%s$O:G=i$+$i:G8e$^$G(B Java VM $B$rDd;_$5$;$?>e$G9T$o$J$$$H%@%a!#(B $B%*%V%8%'%/%H$N;2>H$N4X78@-$K$b$h$k$,!"(B marking phase $B$H(B compaction phase $B$O$@$$$?$$F1DxEY$N;~4V$,$+$+$k$N$G!"(B marking $B$,(B concurrent $B$K$J$C$?$@$1$G$O(B GC $BDd;_;~4V$OH>J,DxEY$K$7$+$J$i$J$$!#(B $B$3$l$G$O$"$^$j8z2L$,$J$$!#(B

[3] $B$GDs0F$5$l$F$$$k(B Incremental Compaction $B$O(B M-CMS $B$NH/E87O$G$"$k!#(B $B%R!<%WA4BN$r%3%s%Q%/%7%g%s$OD|$a!"(B $B%R!<%W6u4V$N0lIt$K%3%s%Q%/%7%g%sMQ$NAk(B(Evacuated Area; EA $B$H8F$V$3$H$K$9$k(B) $B$r@_$1$k!#(B M-CMS $B$K$h$C$FAk0J30$NItJ,$O%9%$!<%W$r9T$$(I$(B $BAkFb$N%*%V%8%'%/%H$OJRB&$K@0Ns$5$;$k%3%s%Q%/%7%g%s$r9T$&!#(B $BAk$K$O%,!<%Y!<%8$,B?$/$F@8$-$F$$$k%*%V%8%'%/%H$,AB$J6u4V$rA*$V$3$H$G!"(B $BO"B3$7$?%U%j!

$BNc$(%R!<%W$N0lIt$NAk$G$"$C$F$b!"(B $B$=$NCf$K$"$k%*%V%8%'%/%H$r0\F0$7$h$&$9$k$H!"(B $B0\F0$7$?$$%*%V%8%'%/%H$r;X$7$F$$$kA4$F$N%]%$%s%?$r=q$-49$($kI,MW$,$"$k!#(B $B$3$N%*%V%8%'%/%H$N0\F0$r?J$a$k$?$a$K(B $B%j%a%s%P!<%;%C%H(B (Remember Set) $B$rMQ$$$k!#(B $B%j%a%s%P!<%;%C%H$O(B EA $B$r;X$7$F$$$k%]%$%s%?$r5-O?$9$kG[Ns$@$H9M$($l$P$h$$!#(B

Serial marking phase$B!"(BSweep phase $B$,40N;$9$k$H!"(B $B%j%a%s%P!<%;%C%H$K$O30It$+$i(B EA $BNN0h$r;2>H$7$F$$$k%*%V%8%'%/%H$N%"%I%l%9$,$9$Y$FF~$C$F$$$k!#(B EA $BFb$N%*%V%8%'%/%H$N%3%s%Q%/%7%g%s$r9T$C$?>l9g!"(B $B$=$N1F6AHO0O$O%j%a%s%P!<%;%C%H$K5-O?$5$l$?%*%V%8%'%/%H$K8BDj$5$l$k!#(B $B%j%a%s%P!<%;%C%H$,5-O?$7$?%*%V%8%'%/%H$@$1$rBP>]$K0\F0%"%I%l%9$N=q$-49$($r9T$&$3$H$K$h$C$F!"(B $B%3%s%Q%/%7%g%s$K$h$kB.EYDc2<$rKI$0$3$H$,2DG=$@!#(B

Incremental Compaction $B$O!"(B IBM JVM 1.4.2 $B0J9_$K


5. $B;29MJ88%(B


$B5SCm(B

*1
$B$3$N$h$&$J%*%V%8%'%/%H$r(B floating garbage $B$H$$$&$3$H$b$"$k!#(B
*2
$BA[%^%7%s$O(B OS $B$H$=$N%9%l%C%I%9%1%8%e!<%i!<$r%3%s%H%m!<%k$G$-$J$$$?$a!"(B $B7P83E*$K$O(B CPU $B?t(B + $B&A8D$0$i$$$N(B GC $B%9%l%C%I$r;HMQ$9$k$N$,M-8z$@!#(B

$B%3%a%s%H(B

$B%3%a%s%H$r=q$-9~$`(B

TOP    $B7G<(HD(B    $BLa$k(B
Written by NAKAMURA Minoru, Email: nminoru atmark nminoru dot jp, Twitter:@nminoru_jp