Bölge tabanlı bellek yönetimi - Region-based memory management

Olarak bilgisayar biliminin , bölge tabanlı bellek yönetim türüdür bellek yönetimi ayrılmış her nesnenin bir tahsis edildiği bölge . Bölge , arena , alan veya bellek bağlamı olarak da adlandırılan bir bölge , aynı anda verimli bir şekilde yeniden tahsis edilebilecek veya yeniden tahsis edilebilecek tahsis edilmiş nesnelerin bir koleksiyonudur. Gibi yığın ayırma , bölge ayırma ve düşük masraflıdır bellek miktarda kaldırma kolaylaştırır; ancak daha esnektirler ve nesnelerin tahsis edildikleri yığın çerçevesinden daha uzun yaşamalarına izin verirler. Tipik uygulamalarda, bir bölgedeki tüm nesneler, yığın çerçevelerinin tipik olarak nasıl tahsis edildiğine benzer şekilde, tek bir bitişik bellek adresi aralığında tahsis edilir.

Örnek

Basit bir örnek olarak, bağlantılı bir liste veri yapısını tahsis eden ve sonra serbest bırakan aşağıdaki C kodunu düşünün : 

Region *r = createRegion();
ListNode *head = NULL;
for (int i = 1; i <= 1000; i++) {
    ListNode* newNode = allocateFromRegion(r, sizeof(ListNode));
    newNode->next = head;
    head = newNode;
}
// ...
// (use list here)
// ...
destroyRegion(r);

Bağlantılı listeyi oluşturmak için birçok işlem gerektirse de, düğümlerin tahsis edildiği bölgeyi yok ederek tek bir işlemde hızlı bir şekilde yeniden tahsis edilebilir. Listeyi dolaşmaya gerek yok.

uygulama

Basit açık bölgelerin uygulanması kolaydır; aşağıdaki açıklama Hanson'a dayanmaktadır. Her bölge, büyük bellek bloklarının bağlantılı bir listesi olarak uygulanır ; her blok, birçok ayırmaya hizmet edecek kadar büyük olmalıdır. Mevcut blok, bloktaki bir sonraki boş pozisyona bir işaretçi tutar ve blok doldurulursa, yeni bir blok atanır ve listeye eklenir. Bölge serbest bırakıldığında, sonraki serbest konumlu işaretçi ilk bloğun başlangıcına sıfırlanır ve blok listesi bir sonraki tahsis edilen bölge için yeniden kullanılabilir. Alternatif olarak, bir bölge serbest bırakıldığında, blok listesi, diğer bölgelerin daha sonra yeni bloklar tahsis edebileceği global bir serbest listeye eklenebilir. Bu basit şemanın her iki durumda da, bölgelerdeki tek tek nesneleri serbest bırakmak mümkün değildir.

Bu şemanın tahsis edilen bayt başına toplam maliyeti çok düşüktür; hemen hemen tüm tahsisler, yalnızca bir sonraki serbest konum işaretçisinin bir karşılaştırmasını ve bir güncellemesini içerir. Bir bölgenin serbest bırakılması sabit zamanlı bir işlemdir ve nadiren yapılır. Tipik çöp toplama sistemlerinden farklı olarak , verileri türüyle etiketlemeye gerek yoktur.

Tarih ve kavramlar

Bölgelerin temel kavramı çok eskidir, ilk olarak 1967 gibi erken bir tarihte Douglas T. Ross'un belleğin bir bölgeler hiyerarşisine bölündüğü AED Ücretsiz Depolama Paketinde ortaya çıkmıştır; her bölgenin kendi ayırıcısı vardı ve bir bölge bir kerede serbest bırakılabilir, bu da bölgeleri bölge olarak kullanılabilir hale getirir. 1976'da PL/I standardı AREA veri tipini içeriyordu. 1990'da Hanson, C'deki (arenalar olarak adlandırdığı) açık bölgelerin, en hızlı bilinen yığın ayırma mekanizmasından bile üstün olarak tahsis edilen bayt başına zaman performansı sağlayabildiğini gösterdi. Açık bölgeler, onları havuzlar olarak adlandıran Apache HTTP Sunucusu ve bunları bellek bağlamları olarak adlandıran PostgreSQL veritabanı yönetim sistemi de dahil olmak üzere bazı erken dönem C-tabanlı yazılım projelerinin tasarımında etkiliydi. Geleneksel yığın tahsisi gibi, bu şemalar da bellek güvenliği sağlamaz ; Bir programcının, bir bölgeye, sallanan bir işaretçi aracılığıyla serbest bırakıldıktan sonra erişmesi veya bir bölgeyi serbest bırakmayı unutması, bellek sızıntısına neden olabilir .

Bölge çıkarımı

1988'de araştırmacılar, bölgelerin oluşturulması ve serbest bırakılmasının yanı sıra belirli bölgelere bireysel statik tahsis ifadelerinin atanmasının derleyici tarafından eklendiği bölge çıkarımı kavramını tanıtarak güvenli bellek tahsisi için bölgelerin nasıl kullanılacağını araştırmaya başladılar . Derleme zamanı. Derleyici bunu, sarkan işaretçileri ve sızıntıların oluşmamasını garanti edecek şekilde yapabilir.

Ruggieri ve Murtagh'ın erken dönem çalışmalarında, her işlevin başında bir bölge oluşturulur ve sonunda serbest bırakılır. Ardından , her bir statik ayırma ifadesi için bir yaşam süresi belirlemek için veri akışı analizini kullanırlar ve bunu, tüm yaşam süresini içeren en genç bölgeye atarlar.

1994 yılında, bu çalışma desteği için Tofte ve Talpin tarafından seminal çalışmalarında genelleştirilmiş edildi tip polimorfizmi ve daha yüksek dereceden fonksiyonlar içinde Standart ML , bir fonksiyonel programlama dayanan farklı algoritma kullanarak, dilin tür kesmesi ve polimorfik teorik kavramları bölge tipleri ve bölgesi taşı . Çalışmaları , iki yapı ekleyerek, bölgeleri içeren lambda hesabının bir uzantısını tanıttı :

e 1'de ρ: e 1 ifadesinin sonucunu hesaplayın ve ρ bölgesinde saklayın;
letregion ρ in e 2 end: Bir bölge oluşturun ve onu ρ'ya bağlayın ; değerlendirmek e 2 ; sonra bölgeyi serbest bırakın.

Bu nedenle sözdizimsel yapıya, bölgeler iç içe r ise, yani 2 r sonra oluşturulan 1 , aynı zamanda r önce ayırmanın gerekir 1 ; sonuç, bir bölge yığınıdır . Ayrıca, bölgeler oluşturuldukları aynı işlevde yeniden tahsis edilmelidir. Bu kısıtlamalar Aiken ve arkadaşları tarafından gevşetildi.

Bu genişletilmiş lambda hesabı, Standart ML programlarını makine koduna derlemek için bellek açısından güvenli bir ara temsil olarak hizmet etmeyi amaçlamıştı , ancak büyük programlarda iyi sonuçlar verecek bir çevirmen oluşturmak, çözülmesi gereken bir dizi pratik sınırlamayla karşı karşıya kaldı. özyinelemeli çağrılar, kuyruk çağrıları ve yalnızca tek bir değer içeren bölgelerin ortadan kaldırılması dahil olmak üzere analizler . Bu çalışma 1995 yılında tamamlanmış ve çöp toplama yerine bölge tahsisine dayalı bir ML sürümü olan ML Kit'e entegre edilmiştir. Bu, orta ölçekli test programları üzerinde ikisi arasında doğrudan bir karşılaştırmaya izin verdi ve programın ne kadar "bölge dostu" olduğuna bağlı olarak çok çeşitli sonuçlar ("10 kat daha hızlı ve dört kat daha yavaş arasında") verdi; Ancak derleme süreleri dakikalar mertebesindeydi. ML Kiti sonunda iki eklemeyle büyük uygulamalara ölçeklendi: modüllerin ayrı derlemesi için bir şema ve bölge çıkarımını izleme çöp toplama ile birleştiren bir hibrit teknik.

Yeni dil ortamlarına genelleme

ML Kit'in geliştirilmesinin ardından bölgeler diğer dil ortamlarına genelleştirilmeye başlandı:

  • C programlama dilinin çeşitli uzantıları:
    • Diğer birçok özelliğin yanı sıra açık bölgeler için destek ekleyen ve mevcut C uygulamalarını bunları kullanmak için geçirmenin etkisini değerlendiren güvenli C lehçesi Cyclone .
    • Açıkça yönetilen bölgeleri kullanan, ancak hiçbir bölgenin zamanından önce serbest bırakılmamasını sağlayarak bellek güvenliğini garanti etmek için bölgelerde referans sayımı kullanan RC adlı bir C uzantısı uygulandı . Bölgelerin içindeki referanslar, değiştirildiklerinde sayıların güncellenmesini gerektirmediğinden, bölgeler referans sayımının ek yükünü azaltır. RC, bazı referans sayısı güncellemelerinin ortadan kaldırılmasına izin veren, bölgeler için açık bir statik tip sistemi içerir.
    • Control-C adı verilen bir C kısıtlaması, programları, bellek güvenliğini statik olarak sağlamak için tasarımının bir parçası olarak bölgeleri (ve bir seferde yalnızca tek bir bölgeyi) kullanacak şekilde sınırlar.
  • Bölgeler, Java'nın bir alt kümesi için uygulandı ve Gerçek Zamanlı Java'da , nesne kapsüllemesini göstermek ve bölge ayırmada çalışma zamanı denetimlerini ortadan kaldırmak için bunları sahiplik türleriyle birleştiren bellek yönetiminin kritik bir bileşeni haline geldi . Daha yakın zamanlarda, gömülü gerçek zamanlı Java uygulamalarında bölgeler çıkarmak için derleme zamanı statik analizini, çalışma zamanı bölge tahsis politikasını ve programcı ipuçlarını birleştiren yarı otomatik bir sistem önerildi. Bölgeler, gerçek zamanlı bilgi işlem için iyi bir seçimdir çünkü zaman ek yükleri, artan çöp toplamanın karmaşıklığı olmadan statik olarak tahmin edilebilirdir.
  • Tofte ve Talpin'in bölge çıkarım modelini geri izlemeyi ve kesintileri destekleyecek şekilde genişleterek mantık programlama dilleri Prolog ve Mercury için uygulandı .
  • Bölge tabanlı depolama yönetimi, ParaSail paralel programlama dili boyunca kullanılır . ParaSail'de açık işaretçilerin olmaması nedeniyle referans sayımına gerek yoktur.

Dezavantajları

Bölgeleri kullanan sistemler, bölgelerin ayrılmadan önce çok büyük hale gelmesi ve büyük oranda ölü veri içermesi sorunlarıyla karşılaşabilir; bunlara genellikle "sızıntılar" denir (sonunda serbest bırakılsalar bile). Sızıntıları ortadan kaldırmak, tipik olarak yeni, daha kısa ömürlü bölgeler ekleyerek programın yeniden yapılandırılmasını içerebilir. Bu tür bir sorunun hatalarını ayıklamak, özellikle programcının sorunu teşhis etmek için temeldeki çıkarım algoritmasını anlaması veya ayrıntılı ara temsili incelemesi gereken bölge çıkarımı kullanan sistemlerde zordur. Çöp toplayıcıların izlenmesi, bu tür verilerin program değişiklikleri olmadan zamanında serbest bırakılmasında daha etkilidir; bu, hibrit bölge/GC sistemleri için bir gerekçeydi. Öte yandan, bir daha asla kullanılmayacak verilere referanslar tutulursa, çöp toplayıcıları izlemek de ince sızıntılar gösterebilir.

Bölge tabanlı bellek yönetimi, bölgelerin sayısı nispeten az olduğunda ve her biri çok sayıda nesne içerdiğinde en iyi sonucu verir; birçok seyrek bölge içeren programlar, dahili parçalanma sergileyecek ve bu da bellek israfına ve bölge yönetimi için bir zaman yüküne yol açacaktır . Yine, bölge çıkarımının varlığında bu sorunu teşhis etmek daha zor olabilir.

Hibrit yöntemler

Yukarıda bahsedildiği gibi, RC, bölgelerin ve referans sayımının bir melezini kullanır , bu da referans sayımının ek yükünü sınırlandırır, çünkü bölgelere dahili referanslar, değiştirildiğinde sayıların güncellenmesini gerektirmez. Benzer şekilde, bazı işaret-bölge hibrit yöntemleri, izleme çöp toplamayı bölgelerle birleştirir ; bunlar, yığını bölgelere ayırarak, canlı nesneleri içeren bölgelerin işaretlendiği bir işaretleme-süpürme geçişi gerçekleştirerek ve ardından işaretlenmemiş bölgeleri serbest bırakarak işlev görür. Bunlar, etkili kalmak için sürekli birleştirme gerektirir.

Referanslar