ºÇ½ª¹¹¿·¡§
author_nari 2008ǯ11·î03Æü(·î) 12:53:42ÍúÎò
Copying GC ¥¢¥ë¥´¥ê¥º¥à¤Ï¡¢À¸¤¤¿¥ª¥Ö¥¸¥§¥¯¥È¤ò¤¹¤¤Þ¤ò¤Ä¤á¤Ê¤¬¤é°ÜÆ°¤¹¤ë¤È¤¤¤¦¤â¤Î¤Ç¤¢¤ë¡£
¤³¤ì¤Ë¤è¤ê¡¢mark sweep ¤äreference counting ¤ÇÌäÂê¤È¤Ê¤ëfragmentation ¤¬Á´¤¯µ¯¤é¤Ê¤¤¤È¤¤¤¦ÍøÅÀ¤¬¤¢¤ë¡£
¤Þ¤¿¡¢Â¿¤¯¤ÎScheme¤äML½èÍý·Ï¤ÇºÎÍѤµ¤ì¤Æ¤¤¤ë¡£
¤³¤³¤Ç¤ÏºÇ¤âñ½ã¤Ê¡¢¥Ò¡¼¥×¤ò2 Åùʬ¤¹¤ëÊý¼°¤ò¾Ò²ð¤¹¤ë¡£
¤³¤ÎÊý¼°¤Ç¤Ï¡¢°ìÅ٤˻Ȥ¨¤ë¥Ò¡¼¥×¤Ï2Åùʬ¤Î¤¦¤ÁÊÒÊý¤Î¤ß¤Ç¤¢¤ë¡£»ÈÍÑÃæ¤ÎÊÒÊý¤¬Ëä¤Þ¤Ã¤¿»þÅÀ¤ÇGC ¤òµ¯Æ°¤¹¤ë¡£
¤½¤·¤ÆÅþã²Äǽ¤Ê¥ª¥Ö¥¸¥§¥¯¥È¤¿¤Á¤ò¡¢¤½¤Ã¤¯¤ê¤â¤¦ÊÒÊý¤Î¥Ò¡¼¥×¤Ë·ä´Ö¤ò¤Ä¤á¤Ê¤¬¤é¥³¥Ô¡¼¤¹¤ë¡£
¥³¥Ô¡¼¸µ¤Î¥Ò¡¼¥×¤òfrom-space¡¢¥³¥Ô¡¼Àè¤Î¥Ò¡¼¥×¤òto-space ¤È¸Æ¤Ö¡£
¥³¥Ô¡¼¤¬½ª¤Ã¤¿»þÅÀ¤Ç¤Ï¤¹¤Ç¤Ëfrom-space ¤Ë¤ÏÀ¸¤¤¿¥ª¥Ö¥¸¥§¥¯¥È¤Î»Ä³¼¤È¥´¥ß¤·¤«»Ä¤Ã¤Æ¤¤¤Ê¤¤¤Î¤ÇÍÑ̵¤·¤È¤Ê¤ë¡£
GC ½ªÎ»¸å¡¢¥æ¡¼¥¶¥×¥í¥°¥é¥à¤Ïto-space ¤òÍѤ¤¤ÆÆ°ºî¤ò³¤±¤ë¡£¤³¤Î¤è¤¦¤Ë¡¢GC ¤ÎÅÙ¤Ë2 ¤Ä¤Î¥Ò¡¼¥×¤ÎÌò³ä¤ò¸òÂؤ·¤Ê¤¬¤é¥·¥¹¥Æ¥à¤ÏÆ°ºî¤¹¤ë¡£
¤³¤ÎÊý¼°¤ò¼ÂÁõ¤·¤è¤¦¤È¤¹¤ë¤È¤¡¢¤¤¤¯¤Ä¤«Ãí°Õ¤¬É¬ÍפǤ¢¤ë¡£
Î㤨¤Ð¥³¥Ô¡¼¸å¤Î¥°¥é¥Õ¤Ïɬ¤ºto-spaceÆâ¤Ç´°·ë¤·¡¢from-space ¤Ë¥Ý¥¤¥ó¥¿¤¬¤Î¤Ó¤Æ¤¤¤Æ¤Ï¤¤¤±¤Ê¤¤¡£
¤Þ¤¿¡¢Ê£¿ô²Õ½ê¤«¤éƱ¥ª¥Ö¥¸¥§¥¯¥È¤¬»²¾È¤µ¤ì¤Æ¤¤¤ë¾ì¹ç¤Ë¤âÃí°Õ¤¹¤ë¡£
¿Þ¤Ç¤Ïb ¤Èc ¤¬d ¤ò»²¾È¤·¤Æ¤¤¤ë¤Î¤Ç¡¢to space ¤Ë¤ª¤¤¤Æ¤âb'¤Èc'¤ÏƱ¥ª¥Ö¥¸¥§¥¯¥È¤ò»²¾È¤·¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¡£
¥¢¥ë¥´¥ê¥º¥à¤ò3 ¿§¥â¥Ç¥ë¤òÍѤ¤¤Æ¹Í¤¨¤ë¤È°Ê²¼¤Î¤è¤¦¤Ë¤Ê¤ë¡£
¾å¤Î¤è¤¦¤Ê¾ò·ï¤òËþ¤¿¤·¤Æ¤¤¤ì¤Ð¡¢¿¼¤µÍ¥Àè¤Ç¤âÉýÍ¥Àè¤Ç¤âÎɤ¤¡£¤³¤³¤Ç¤Ï¡¢copying GC ¤ÎÂå̾»ì¤Ë
¤Ê¤Ã¤Æ¤¤¤ë¡¢Cheney ¤ÎÉýÍ¥À襢¥ë¥´¥ê¥º¥à¤ò¾Ò²ð¤¹¤ë¡£¤³¤ì¤ÏºÆµ¢¸Æ¤Ó½Ð¤·¤â¥Þ¡¼¥¯¥¹¥¿¥Ã¥¯¤Î¤è¤¦¤ÊÎΰè¤â»È¤ï¤Ê¤¤¡£
¥Ò¡¼¥×°Ê³°¤Î¥á¥â¥ê»ÈÍÑÎ̤ÏO(1)!
GC ³«»Ï»þ¤Ë¡¢¥ë¡¼¥È¥ª¥Ö¥¸¥§¥¯¥È¤«¤éľÀÜ»²¾È¤µ¤ì¤ë¥ª¥Ö¥¸¥§¥¯¥È(¿Þ¤Ç¤Ïa ¤Î¤ß) ¤òto space ¤Ë¥³¥Ô¡¼¤¹¤ë¡£¤³¤Î»þÅÀ¤Ça ¤Ï³¥¿§¤È¹Í¤¨¤é¤ì¤ë¡£
¤³¤Î¥¢¥ë¥´¥ê¥º¥à¤ÏºÆµ¢Ãµº÷¤Î¤¿¤á¤Ë2 ¤Ä¤Î¥Ý¥¤¥ó¥¿¤òÍѤ¤¤ë¡£
GC ¤Ï°Ê²¼¤Î½èÍý¤ò·«¤êÊÖ¤¹¡£scanned ¤¬»Ø¤¹ÀèƬ¥ª¥Ö¥¸¥§¥¯¥Èo ¤ò¼è¤ê½Ð¤·¡¢o ¤Î»Ò¥ª¥Ö¥¸¥§¥¯¥Èã¤Î¤¦¤Á¡¢
̤¥³¥Ô¡¼¤Ç¤¢¤ë¤â¤Î¤ò¥¢¥É¥ì¥¹unscanned ¤Ë¥³¥Ô¡¼¤¹¤ë(o ¤Î»Ò¥ª¥Ö¥¸¥§¥¯¥Èã¤ò³¥¿§¤Ë¤¹¤ë)¡£¤½¤ÎÅÙ¤Ëunscanned ¤ò¿Ê¤á¤ë¡£
Ʊ»þ¤Ë¡¢o Ãæ¤Î¥Ý¥¤¥ó¥¿¤¬¥³¥Ô¡¼Àè¤ò¤µ¤¹¤è¤¦¤Ë½ñ¤´¹¤¨¡¢scanned ¤ò¿Ê¤á¤ë(o ¤ò¹õ¤Ë¤¹¤ë)¡£
scanned ¤¬unscanned ¤ËÄɤ¤¤Ä¤¤¤¿¤é¡¢GC ¤ò½ªÎ»¤¹¤ë¡£
¤µ¤Æ¡¢Æ±¤¸¥ª¥Ö¥¸¥§¥¯¥È¤Ø¤ÎÊ£¿ô»²¾È¤ËÂбþ¤¹¤ë¤¿¤á¤Ë¤Ï¡¢from-space Ãæ¤Îd ¤ò¸«¤¿¤À¤±¤Ç¡¢
¡Ö¤³¤ì¤Ï¤¹¤Ç¤Ë¥³¥Ô¡¼ºÑ¤ß¤Ç¤¢¤ê¡¢¥³¥Ô¡¼Àè¤Ïd' ¤Ç¤¢¤ë¡×
¤È¤¤¤¦¤³¤È¤¬Ê¬¤«¤ëɬÍפ¬¤¢¤ë¡£
¤½¤Î¤¿¤á¤Ë¡¢³¥¿§²½¤Î»þÅÀ¤Çd ¤Ëforwarding tag (¥³¥Ô¡¼ºÑ¤ß¤Ç¤¢¤ë¤³¤È¤òɽ¤¹)¡¢
forwarding pointer(¥³¥Ô¡¼Àè¤ò¶µ¤¨¤Æ¤¯¤ì¤ë)¤ò½ñ¤¹þ¤ó¤Ç¤ª¤¯¡£
¤³¤ì¤Ë¤è¤ê¡¢mark sweep ¤äreference counting ¤ÇÌäÂê¤È¤Ê¤ëfragmentation ¤¬Á´¤¯µ¯¤é¤Ê¤¤¤È¤¤¤¦ÍøÅÀ¤¬¤¢¤ë¡£
¤Þ¤¿¡¢Â¿¤¯¤ÎScheme¤äML½èÍý·Ï¤ÇºÎÍѤµ¤ì¤Æ¤¤¤ë¡£
¤³¤³¤Ç¤ÏºÇ¤âñ½ã¤Ê¡¢¥Ò¡¼¥×¤ò2 Åùʬ¤¹¤ëÊý¼°¤ò¾Ò²ð¤¹¤ë¡£
¤³¤ÎÊý¼°¤Ç¤Ï¡¢°ìÅ٤˻Ȥ¨¤ë¥Ò¡¼¥×¤Ï2Åùʬ¤Î¤¦¤ÁÊÒÊý¤Î¤ß¤Ç¤¢¤ë¡£»ÈÍÑÃæ¤ÎÊÒÊý¤¬Ëä¤Þ¤Ã¤¿»þÅÀ¤ÇGC ¤òµ¯Æ°¤¹¤ë¡£
¤½¤·¤ÆÅþã²Äǽ¤Ê¥ª¥Ö¥¸¥§¥¯¥È¤¿¤Á¤ò¡¢¤½¤Ã¤¯¤ê¤â¤¦ÊÒÊý¤Î¥Ò¡¼¥×¤Ë·ä´Ö¤ò¤Ä¤á¤Ê¤¬¤é¥³¥Ô¡¼¤¹¤ë¡£
¥³¥Ô¡¼¸µ¤Î¥Ò¡¼¥×¤òfrom-space¡¢¥³¥Ô¡¼Àè¤Î¥Ò¡¼¥×¤òto-space ¤È¸Æ¤Ö¡£
¥³¥Ô¡¼¤¬½ª¤Ã¤¿»þÅÀ¤Ç¤Ï¤¹¤Ç¤Ëfrom-space ¤Ë¤ÏÀ¸¤¤¿¥ª¥Ö¥¸¥§¥¯¥È¤Î»Ä³¼¤È¥´¥ß¤·¤«»Ä¤Ã¤Æ¤¤¤Ê¤¤¤Î¤ÇÍÑ̵¤·¤È¤Ê¤ë¡£
GC ½ªÎ»¸å¡¢¥æ¡¼¥¶¥×¥í¥°¥é¥à¤Ïto-space ¤òÍѤ¤¤ÆÆ°ºî¤ò³¤±¤ë¡£¤³¤Î¤è¤¦¤Ë¡¢GC ¤ÎÅÙ¤Ë2 ¤Ä¤Î¥Ò¡¼¥×¤ÎÌò³ä¤ò¸òÂؤ·¤Ê¤¬¤é¥·¥¹¥Æ¥à¤ÏÆ°ºî¤¹¤ë¡£
¤³¤ÎÊý¼°¤ò¼ÂÁõ¤·¤è¤¦¤È¤¹¤ë¤È¤¡¢¤¤¤¯¤Ä¤«Ãí°Õ¤¬É¬ÍפǤ¢¤ë¡£
Î㤨¤Ð¥³¥Ô¡¼¸å¤Î¥°¥é¥Õ¤Ïɬ¤ºto-spaceÆâ¤Ç´°·ë¤·¡¢from-space ¤Ë¥Ý¥¤¥ó¥¿¤¬¤Î¤Ó¤Æ¤¤¤Æ¤Ï¤¤¤±¤Ê¤¤¡£
¤Þ¤¿¡¢Ê£¿ô²Õ½ê¤«¤éƱ¥ª¥Ö¥¸¥§¥¯¥È¤¬»²¾È¤µ¤ì¤Æ¤¤¤ë¾ì¹ç¤Ë¤âÃí°Õ¤¹¤ë¡£
¿Þ¤Ç¤Ïb ¤Èc ¤¬d ¤ò»²¾È¤·¤Æ¤¤¤ë¤Î¤Ç¡¢to space ¤Ë¤ª¤¤¤Æ¤âb'¤Èc'¤ÏƱ¥ª¥Ö¥¸¥§¥¯¥È¤ò»²¾È¤·¤Ê¤±¤ì¤Ð¤Ê¤é¤Ê¤¤¡£
¥¢¥ë¥´¥ê¥º¥à¤ò3 ¿§¥â¥Ç¥ë¤òÍѤ¤¤Æ¹Í¤¨¤ë¤È°Ê²¼¤Î¤è¤¦¤Ë¤Ê¤ë¡£
- Çò· · · ¤Þ¤À¥³¥Ô¡¼¤µ¤ì¤Æ¤¤¤Ê¤¤(from-space ¤Ë¤·¤«¤Ê¤¤) ¥ª¥Ö¥¸¥§¥¯¥È
- ³¥¿§· · · ¤½¤ì¼«¿È¤Ï¥³¥Ô¡¼¤µ¤ì¤¿¤¬¡¢from-space ¤Î¥ª¥Ö¥¸¥§¥¯¥È(Çò¥ª¥Ö¥¸¥§¥¯¥È¤ä¾¤Î¥ª¥Ö¥¸¥§¥¯¥È¤Î¥³¥Ô¡¼Á°) ¤ò»Ø¤·¤Æ¤¤¤ë²ÄǽÀ¤¬¤¢¤ë¡£
- ¹õ· · · ¤½¤ì¼«¿È¤Ï¥³¥Ô¡¼¤µ¤ì¤¿¤·¡¢from-space ¤ò»Ø¤·¤Æ¤¤¤ë²ÄǽÀ¤â¤Ê¤¤¡£
¾å¤Î¤è¤¦¤Ê¾ò·ï¤òËþ¤¿¤·¤Æ¤¤¤ì¤Ð¡¢¿¼¤µÍ¥Àè¤Ç¤âÉýÍ¥Àè¤Ç¤âÎɤ¤¡£¤³¤³¤Ç¤Ï¡¢copying GC ¤ÎÂå̾»ì¤Ë
¤Ê¤Ã¤Æ¤¤¤ë¡¢Cheney ¤ÎÉýÍ¥À襢¥ë¥´¥ê¥º¥à¤ò¾Ò²ð¤¹¤ë¡£¤³¤ì¤ÏºÆµ¢¸Æ¤Ó½Ð¤·¤â¥Þ¡¼¥¯¥¹¥¿¥Ã¥¯¤Î¤è¤¦¤ÊÎΰè¤â»È¤ï¤Ê¤¤¡£
¥Ò¡¼¥×°Ê³°¤Î¥á¥â¥ê»ÈÍÑÎ̤ÏO(1)!
GC ³«»Ï»þ¤Ë¡¢¥ë¡¼¥È¥ª¥Ö¥¸¥§¥¯¥È¤«¤éľÀÜ»²¾È¤µ¤ì¤ë¥ª¥Ö¥¸¥§¥¯¥È(¿Þ¤Ç¤Ïa ¤Î¤ß) ¤òto space ¤Ë¥³¥Ô¡¼¤¹¤ë¡£¤³¤Î»þÅÀ¤Ça ¤Ï³¥¿§¤È¹Í¤¨¤é¤ì¤ë¡£
¤³¤Î¥¢¥ë¥´¥ê¥º¥à¤ÏºÆµ¢Ãµº÷¤Î¤¿¤á¤Ë2 ¤Ä¤Î¥Ý¥¤¥ó¥¿¤òÍѤ¤¤ë¡£
- scanned· · · ½é´üÃͤÏto-space ¤ÎÀèƬ¡£scanned ¤è¤ê¼êÁ°¤ÏÁ´¤Æ¹õ¥ª¥Ö¥¸¥§¥¯¥È¤Ç¤¢¤ë¡£
- unscanned· · · ½é´üÃͤϡ¢¿Þ¤Î¾ì¹ç(to-space ¤ÎÀèƬ) +sizeof(a)¡£scanned ¤Èunscanned ¤Î´Ö¤ÏÁ´¤Æ³¥¿§¥ª¥Ö¥¸¥§¥¯¥È¤Ç¤¢¤ê¡¢unscanned °Ê¹ß¤Ï¶õ¤Îΰ衣
GC ¤Ï°Ê²¼¤Î½èÍý¤ò·«¤êÊÖ¤¹¡£scanned ¤¬»Ø¤¹ÀèƬ¥ª¥Ö¥¸¥§¥¯¥Èo ¤ò¼è¤ê½Ð¤·¡¢o ¤Î»Ò¥ª¥Ö¥¸¥§¥¯¥Èã¤Î¤¦¤Á¡¢
̤¥³¥Ô¡¼¤Ç¤¢¤ë¤â¤Î¤ò¥¢¥É¥ì¥¹unscanned ¤Ë¥³¥Ô¡¼¤¹¤ë(o ¤Î»Ò¥ª¥Ö¥¸¥§¥¯¥Èã¤ò³¥¿§¤Ë¤¹¤ë)¡£¤½¤ÎÅÙ¤Ëunscanned ¤ò¿Ê¤á¤ë¡£
Ʊ»þ¤Ë¡¢o Ãæ¤Î¥Ý¥¤¥ó¥¿¤¬¥³¥Ô¡¼Àè¤ò¤µ¤¹¤è¤¦¤Ë½ñ¤´¹¤¨¡¢scanned ¤ò¿Ê¤á¤ë(o ¤ò¹õ¤Ë¤¹¤ë)¡£
scanned ¤¬unscanned ¤ËÄɤ¤¤Ä¤¤¤¿¤é¡¢GC ¤ò½ªÎ»¤¹¤ë¡£
¤µ¤Æ¡¢Æ±¤¸¥ª¥Ö¥¸¥§¥¯¥È¤Ø¤ÎÊ£¿ô»²¾È¤ËÂбþ¤¹¤ë¤¿¤á¤Ë¤Ï¡¢from-space Ãæ¤Îd ¤ò¸«¤¿¤À¤±¤Ç¡¢
¡Ö¤³¤ì¤Ï¤¹¤Ç¤Ë¥³¥Ô¡¼ºÑ¤ß¤Ç¤¢¤ê¡¢¥³¥Ô¡¼Àè¤Ïd' ¤Ç¤¢¤ë¡×
¤È¤¤¤¦¤³¤È¤¬Ê¬¤«¤ëɬÍפ¬¤¢¤ë¡£
¤½¤Î¤¿¤á¤Ë¡¢³¥¿§²½¤Î»þÅÀ¤Çd ¤Ëforwarding tag (¥³¥Ô¡¼ºÑ¤ß¤Ç¤¢¤ë¤³¤È¤òɽ¤¹)¡¢
forwarding pointer(¥³¥Ô¡¼Àè¤ò¶µ¤¨¤Æ¤¯¤ì¤ë)¤ò½ñ¤¹þ¤ó¤Ç¤ª¤¯¡£
- ¥á¥â¥ê²ó¼ý¤ÈƱ»þ¤Ëcompaction¤Ç¤¤ë¡£
- »²¾È´Ø·¸¤ò¹Íθ¤·¤¿¥³¥ó¥Ñ¥¯¥·¥ç¥ó¤Ë¤è¤ê¡¢¥¥ã¥Ã¥·¥å¤È¤ÎÁêÀ¤¬¤è¤¤(¡á¥×¥í¥°¥é¥à¤Î¼Â¹Ô®ÅÙ¤¬¾å¤¬¤ë)¡£
- Mark&Sweep¤Ê¤É¤ÈÈæ¤Ù¤Æallocate½èÍý¤¬Áᤤ(FreeList¤Ê¤É»È¤ï¤Ê¤¯¤Æ¤¤¤¤°Ù)
- ¤Þ¤¿²òÊü½èÍý¤âÁᤤ¤è¡£
- ¥ª¥Ö¥¸¥§¥¯¥È¤Î°ÜÆ°¤Ë¤è¤ê¡¢¥Ý¥¤¥ó¥¿¤Î½ñ¤´¹¤¨¤¬µ¯¤³¤ê¡¢ÊݼéŪGC¤Ïºî¤ê¤Ë¤¯¤¤¡£
- ¥Ò¡¼¥×Îΰè¤òʬ³ä¤¹¤ë¤¿¤á¡¢¥á¥â¥êÎΰè¤ò²¿Çܤâ¼è¤ë¡£
- Cheney's Algorithm
- Æ°¤¯¥Ç¥â¤¬¤¢¤ê¡¢ÁÛÁü¤·¤ä¤¹¤¤
- ¥«¥Æ¥´¥ê¡§
- ¥Ñ¥½¥³¥ó
- ¥¬¡¼¥Ù¥Ã¥¸¥³¥ì¥¯¥¿¡ÊGC¡Ë
¤³¤Î¥Ú¡¼¥¸¤Ø¤Î¥³¥á¥ó¥È
GC/standard/Copying - GC���르�ꥺ��ܺٲ��� - Seesaa Wiki�ʥ������� for ���ޡ��ȥե��� モンクレール ダウン http://www.pslcbi.com/moncler2014.html
GC/standard/Copying - GC���르�ꥺ��ܺٲ��� - Seesaa Wiki�ʥ������� for ���ޡ��ȥե��� ビームス モンクレール http://www.pslcbi.com/moncler2014.html
Mark&Sweep¤À¤È¥Ç¥¹¥È¥é¥¯¥¿Åù¤Î³«Êü½èÍý¤Ï¼«ÌÀ¤Ç¤¹¤¬¡¢
1>¸å½èÍý¤¬É¬Íפʥª¥Ö¥¸¥§¥¯¥È¤ò¤¢¤é¤«¤¸¤áµ²±¤·¤Æ¤ª¤¡¢GC½ªÎ»¸å¥³¥Ô¡¼ºÑ¤ß¤Ç¤Ê¤±¤ì¤Ð¡Ê¤Ä¤Þ¤ê¥´¥ß¤Ê¤é¤Ð¡Ë¥Ç¥¹¥È¥é¥¯¥¿¤ò¸Æ¤Ö¡£
2>GC½ªÎ»¸å¡¢to-space ¤ÈƱÍÍ¤Ë from-space ¤òÁöºº¤·¥³¥Ô¡¼ºÑ¤ß¤Ç¤Ê¤±¤ì¤Ð¥Ç¥¹¥È¥é¥¯¥¿¤ò¸Æ¤Ö¡£