การจัดเก็บขยะและการจัดการหน่วยความจำ

การจัดการหน่วยความจำควบคุมวิธีการที่โปรแกรมจัดสรรและเรียกคืนหน่วยความจำ; การจัดเก็บขยะจะทำให้การเรียกคืนเป็นไปโดยอัตโนมัติโดยการระบุและปลดปล่อยวัตถุที่ไม่มีการเข้าถึงอีกต่อไป

Definition

การจัดการหน่วยความจำคือการจัดสรรและเรียกคืนหน่วยความจำของโปรแกรม; การจัดเก็บขยะคือการเรียกคืนอัตโนมัติที่ปลดปล่อยหน่วยความจำที่ถูกครอบครองโดยวัตถุที่โปรแกรมไม่สามารถเข้าถึงได้อีกต่อไป ซึ่งช่วยให้โปรแกรมเมอร์ไม่ต้องทำการปลดปล่อยหน่วยความจำอย่างชัดเจน

Scope

หัวข้อนี้ครอบคลุมการจัดการหน่วยความจำแบบอัตโนมัติและแบบแมนนวลสำหรับรันไทม์ของภาษา: การนับอ้างอิง (reference counting), การทำเครื่องหมายและกวาด (mark-and-sweep), การคัดลอก (copying), และการจัดเก็บแบบแบ่งรุ่น (generational collection); การติดตามการเข้าถึง (tracing reachability); และการแลกเปลี่ยนระหว่างปริมาณงาน (throughput), เวลาหยุดชั่วคราว (pause time), และค่าใช้จ่ายหน่วยความจำ (memory overhead) นอกจากนี้ยังกล่าวถึงตัวเก็บขยะแบบพร้อมกัน (concurrent) และแบบเพิ่มขึ้น (incremental collectors) และความสัมพันธ์ระหว่างกลยุทธ์การจัดเก็บกับการออกแบบภาษา

Core questions

• ตัวเก็บขยะพิจารณาได้อย่างไรว่าวัตถุใดที่ยังคงจำเป็น?
• การแลกเปลี่ยนระหว่างปริมาณงาน ความหน่วง และการใช้หน่วยความจำคืออะไร?
• เหตุใดการแยกวัตถุตามอายุ (การจัดเก็บแบบแบ่งรุ่น) จึงช่วยเพิ่มประสิทธิภาพ?
• การจัดเก็บสามารถหลีกเลี่ยงการหยุดชั่วคราวที่ยาวนานในระบบแบบโต้ตอบหรือระบบเรียลไทม์ได้อย่างไร?

Key theories

การจัดเก็บขยะแบบติดตาม

McCarthy ได้นำเสนอการจัดเก็บขยะอัตโนมัติสำหรับ Lisp โดยสร้างแนวคิดในการเรียกคืนหน่วยความจำโดยการติดตามว่าวัตถุใดที่ยังคงสามารถเข้าถึงได้จากรากของโปรแกรม

การจัดเก็บแบบแบ่งรุ่น

Lieberman และ Hewitt สังเกตว่าวัตถุส่วนใหญ่มีอายุสั้นและเสนอให้เก็บรุ่นที่อายุน้อยกว่าบ่อยขึ้น ซึ่งช่วยลดต้นทุนการจัดเก็บได้อย่างมากในทางปฏิบัติ (สมมติฐานการแบ่งรุ่น)

อนุกรมวิธานของเทคนิคการจัดเก็บ

Wilson และ Garbage Collection Handbook จัดระเบียบพื้นที่การออกแบบของการนับอ้างอิง, การทำเครื่องหมายและกวาด, การคัดลอก, ตัวเก็บขยะแบบเพิ่มขึ้นและแบบพร้อมกัน และการแลกเปลี่ยนประสิทธิภาพของพวกมัน

Clinical relevance

การจัดการหน่วยความจำอัตโนมัติช่วยกำจัดข้อผิดพลาดหลายประเภท เช่น พอยน์เตอร์ค้าง (dangling pointers) และหน่วยความจำรั่ว (memory leaks) ซึ่งเป็นเหตุผลที่ภาษาโปรแกรมระดับสูงส่วนใหญ่พึ่งพาการจัดเก็บขยะ การเลือกตัวเก็บขยะมีผลอย่างมากต่อความหน่วงและปริมาณงานของแอปพลิเคชัน โดยเฉพาะอย่างยิ่งสำหรับระบบแบบโต้ตอบและระบบเซิร์ฟเวอร์

History

McCarthy ได้นำเสนอการจัดเก็บขยะพร้อมกับภาษา Lisp ในปี 1960 ตามมาด้วยการจัดเก็บแบบคัดลอก (Cheney) และการนับอ้างอิง และตัวเก็บขยะแบบแบ่งรุ่นของ Lieberman และ Hewitt ในปี 1983 ได้ใช้ประโยชน์จากอายุการใช้งานของวัตถุ ทศวรรษต่อมาได้มีการพัฒนาตัวเก็บขยะแบบเพิ่มขึ้น แบบพร้อมกัน และแบบตามภูมิภาค (region-based collectors) ซึ่งได้รับการสำรวจอย่างครอบคลุมในงานของ Wilson ปี 1992 และคู่มือ Garbage Collection Handbook ปี 2011

Debates

การจัดเก็บอัตโนมัติเทียบกับการจัดการแบบแมนนวลหรือแบบอิงความเป็นเจ้าของ

นักออกแบบถกเถียงกันระหว่างการจัดเก็บขยะ ซึ่งปลอดภัยและสะดวกแต่สามารถทำให้เกิดการหยุดชั่วคราวและค่าใช้จ่าย กับการจัดการแบบแมนนวลหรือแบบอิงความเป็นเจ้าของ ซึ่งให้ประสิทธิภาพที่คาดการณ์ได้และการใช้หน่วยความจำที่ต่ำกว่า แต่ต้องแลกมาด้วยภาระและความเสี่ยงของโปรแกรมเมอร์

Key figures

• John McCarthy
• Henry Lieberman
• Carl Hewitt
• Richard Jones
• Paul Wilson

Seminal works

• mccarthy1960
• lieberman1983
• wilson1992
• jones2011

Frequently asked questions

ตัวเก็บขยะรู้ได้อย่างไรว่าวัตถุใดควรถูกปลดปล่อย?

ตัวเก็บขยะแบบติดตามจะเริ่มต้นจากรากที่รู้จัก เช่น ตัวแปรสแต็กและตัวแปรส่วนกลาง และติดตามการอ้างอิงเพื่อทำเครื่องหมายวัตถุที่เข้าถึงได้ทั้งหมด; สิ่งใดที่ไม่สามารถเข้าถึงได้ถือว่าไม่สามารถเข้าถึงได้และสามารถเรียกคืนได้

เหตุใดการจัดเก็บขยะแบบแบ่งรุ่นจึงมีประสิทธิภาพ?

เนื่องจากวัตถุส่วนใหญ่ไม่สามารถเข้าถึงได้หลังจากจัดสรรไม่นาน การจัดเก็บรุ่นที่อายุน้อยบ่อยครั้งจะช่วยเรียกคืนขยะส่วนใหญ่ได้อย่างรวดเร็ว ในขณะที่วัตถุเก่าที่มีอายุยืนยาวจะถูกสแกนน้อยลงมาก