Ön Hafıza (Cache)

Yazan : Şadi Evren ŞEKER

Bu yazının bütün hakları saklıdır ve izinsiz kopyalanması veya alıntı yapılması kanunen koruma altındadır. Bu yazıya dilediğiniz şekilde atıfta bulunabilir (reference) ve bağlantı (link) verebilirsiniz.

Bilgisayar bilimlerinde sıklıkla kullanılan ve herhangi bir hafıza işleminin nispeten daha küçük ve daha hızlı dolayısıyla da daha pahalı ilave bir hafızada yapılmasını ifade eden terimdir.

Aslında kelime anlamı olarak Türkçedeki zula kelimesi ile de karşılanabilen cache kelimesi, değerli şeylerin saklandığı yer anlamına gelmektedir. Bilgisayar bilimlerinde ise sık erişilen ve dolayısıyla bizim için daha değerli olan bilgilerin saklandığı yere verilen isimdir.

Kısacası bir ön hafıza (cache) gerçek hafızaya erişmeyi azaltmak ve daha hızlı bir şekilde çözmek için tasarlanır. Gerçek hafızadan daha hızlı ve daha pahalıdır. Gerçek hafızadaki her şeyi içeremez dolayısıyla küçük bir kısmını içerir.

En çok kullanıldığı yerler aşağıdaki şekilde sıralanabilir:

• İşlemci önbelleği
• Disk önbelleği
• Web önbelleği

Elbette yukarıdakiler dışında farklı alanlarda da veriye erişim hızını arttırmak için önbellekler kullanılabilir.

Örneğin aşağıda, RAM (hafıza) ile işlemci (CPU) arasına yerleştirilmiş ve işlemci ön belleği (CPU Cache) ismi verilen erişim şekli gösterilmiştir:

Buradaki amaç, işlemcinin hafızada ihtiyaç duyduğu verilerin bir kısmını önbellekten karşılamasıdır. Benzer şekilde hafızadaki veriler ile disk arasında da önbellek olabilir. Bu durumda bir verinin diskten ihtiyaç duyulması halinde diskten daha hızlı olan ön bellek devreye girerek hafızaya yükleme işlemi gerçekleştirebilir. Elbette burada iki ihtimal vardır:

Hit: isabet, işlemcinin isteğinin önbellekten karşılanması

Miss: kayıp, işlemcinin isteğinin önbellekten karşılanamayarak hafızaya erişim yapılması

Bu sayıların oranlanması ile de aşağıdaki değerler bulunur:

İsabet oranı (hit ratio) = isabet (hit) / Toplam talep (veya isabet + kayıp)

Kayıp oranı (miss ratio) = kayıp (miss) / Toplam talep (veya isabet + kayıp)

Örneğin 45 hafıza erişim talebinin olduğunu (request) ve bunların 21’inin önbellekten karşılandığını düşünelim. Bu durumda

Kayıp (miss) = 45 – 21 = 24

İsabet oranı (hit ratio) = 21 / 45 = %47

Kayıp oranı (miss ratio) = 24 / 45 = %53

Olarak hesaplanabilir.

Önbellek yazma politikası (write policy)

Önbelleklerin birinci görevi, ihtiyaç duyulan verinin hızlı karşılanmasıdır. Ancak bu durum veri okunurken avantaj sağlar. Verinin değiştirilmesi veya yazılması gibi durumlarda önbellekte nasıl bir politika izleneceğine de yazma politikası (write policy) ismi verilir. Buna göre 3 farklı politika izlenebilir:

Üzerine yazma (write through) : her yazma işlemi, önbellekte bir isabet olsa bile hafızada güncelleme gerektirir. Buna göre önbellekteki veri ile hafızadaki veri birebir yanı olur. Birisindeki değişiklik diğerini etkiler ve verinin iki ayrı kopyası arasında bir eşleşme gerektirmez.

Geri yazma (write back): Bu yazma politikasında, bir bilginin değiştirilmesi durumunda, bilgi ön bellekte bulunuyorsa, önbellek üzerinde değişiklik yapılır ve hafızadaki kopya hemen değiştirilmez. Dolayısıyla anlık olarak bilginin iki farklı kopyası bulunur. Bilginin iki kopyasının birbirinden farklı olduğunu göstermek için de kirli (dirty) bit kullanılır. Dolayısıyla bu politikada, ön bellek üzerinde ilave bir bite ihtiyaç vardır.

Bu yazma politikasında veriler ön bellekten kaldırılırken hafızadaki veri ile güncellenir. Yani ön bellek sürekli olarak değiştirilmiş veriyi tutar, veri ön bellekten kaldırılıp yerine yeni veri geleceği zaman, bu veri hafızadaki verinin üzerine yazılarak iki kopya aynı hale getirilir.

Bu yazma politikasının hafızayı değiştirmesindeki tutumundan dolayı tembel yazma (lazy write) ismi de verilir.

Bu yazma politikasında ayrıca herhangi bir verinin önbellekten kaldırılıp yerine yeni veri gelmesi durumunda iki kere hafıza erişimi gerekir. Birincisi eski verinin hafıza ile güncellenmesi ikincisi ise yeni verinin hafızaya yüklenmesi için. Üzerine yazma politikasında ise sadece tek erişim yeterlidir.

Yazmama politikası (no-write allocation): bu politikada, önbellek üzerinde bir yazma işlemi yapılmaz. Veri önbellekte sadece okunmak için tutulur ve bir yazma işlemi gerçekleştiğinde bu işlem doğrudan hafızaya yazılır.

Bu durumda önbellekteki verinin doğruluğunda problem olacaktır. Yani hafızadaki veri daha güncel ve önbellekteki veri eski kalmış olacaktır. Bunu belirtmek için önbellek üzerinde bir doğruluk biti (valid bit) kullanılır. Bu bit, verinin değiştiğini ve önbellekteki verinin eski kaldığını belirtir. Herhangi bir şekilde bu değişen veriye okumak için erişim olmazsa önbellekte güncellemeye gerek de kalmaz (örneğin bu veri bir daha hiç erişilmeden önbellekten kaldırılabilir) ancak bir şekilde bu veriye tekrar okumak için erişim olursa bu durumda hafızadaki veri ile güncellenmesi için hafızadan verinin okunup önbelleğe yeni halinin yazılması gerekir.

Bu politikada bir veri değiştirildiğinde ardından gelen yazma işlemlerinin önbellek tarafından karşılanması gerekmez. Ancak bir yazma işleminden sonraki okuma işlemlerinin hafızadan yeni veriyi önbelleğe yüklemesi gerekir.

Önbellek ilişkilendirmesi (Cache Associativity)

Ön bellek kullanılırken bir verinin önbellek üzerinde nereye yazılacağını belirleyen yöntemlere verilen isimdir. Bu yöntemler temel olarak üç grupta toplanabilir.

• Doğrudan haritalama (direct mapped cache) yönteminde veri önbellek üzerinde tek bir yere yazılabilir.
• Küme ilişkilendirme (set associativity) yönteminde veri önbellek üzerinde birden fazla yere yazılabilir.
• Tam ilişkilendirme (full associativity) yönteminde ise veri önbellekteki her yere yazılabilir.

Yukarıdaki bu ilişkilendirme yöntemlerini aşağıda daha detaylı açıklamaya çalışalım.

Doğrudan haritalama (direct mapped cache)

Bu yöntemde, hafızada tutulan veriler ile önbellek adresleri arasında tam bir bağlantı vardır. Örneğin 4 satırdan oluşan bir önbelleğimiz olsun (yani önbelleğimizin kapasitesi 4 veri tutmaya yetiyor). Bu durumda önbelleğin adres için ayrılan bit sayısı 2 olur (2² = 4)

Yine örnek olarak hafızadaki verilerin uzunluğu da 8 bit olsun.

En basit doğrudan haritalama için mod alma işlemi kullanılabilir. Yani örneğin adresin son iki bitine göre (yada ilk iki bitine göre) hafızada erişilmek istenen adresi önbellekte adresleyeceğiz.

Örneğin yukarıdaki şekilde görüldüğü üzere ön bellek 3 sütundan oluşmuştur. Bu sütunların ilki önbellek satır numarasını belirtmeye yarayan ve bir bilginin önbellekte olması durumunda hangi satırda tutulduğunu gösteren sütundur.

Etiket kısmı, önbellekteki verinin aslında hafızadaki gerçek adresini belirten sütundur.

Veri sütunu ise önbellekte duran veridir. Bilginin önbellek tarafından karşılanması durumunda buradaki veri sütununda bulunan veri okunur.

Yukarıda anlatıldığı üzere kullanılan yazma politikasına göre önbellekte ilave sütunlar bulunabilir (kirli (dirty) veya doğru (valid) bitleri gibi).

Örneğin adres olarak tutulan veri 8 bit uzunluğunda olsun ve önbellekte bu verinin ilk iki bitine göre indeksleme yapılıyor olsun.

Örnek hafıza erişimlerini aşağıdaki şekilde ele alalım:

Bu verilerin ilk iki bitleri birbirinden farklıdır ve hepsi önbellekte farklı sıralara yerleştirilecektir. Bu verilerin yerleştirilmiş hali aşağıdadır:

Yukarıda görüldüğü üzere, veriler önbellek üzerinde doğru yerlere yerleştirilmiş ve etiket kısmında adresi tamamlayıcı bilgiler bulunmaktadır. Bu yerleştirme işleminden sonra herhangi bir veriye erişilmek istendiğinde önbellek şu şekilde çalışır:

Örneğin erişilecek hafıza adresi 01001101 olsun.

Bu durumda ilk iki bitine bakılacak ve 01 indeksinde bulunan etiket kontrol edilecektir.

Buradaki etiket değeri ulaşılmak istenen adresin son 6 biti ile aynı olduğu için ( 001101 = 001101 olduğu için) verinin önbellekte bulunduğuna karar verilip hafıza erişimi önbellekten karşılanacaktır ve veri olarak “.com” işlemciye iletilecektir.

Örneğin erişilecek hafıza adresi 01001111 olsun.

Bu durumda ilk iki bitine bakılacak ve 01 indeksinde bulunan etiket kontrol edilecektir. Bu etiket ulaşılmak istenen hafıza adresi ile uyuşmamaktadır ( 001101 != 001111 olduğu için).

Dolayısıyla veri önbellekte olmadığı için verinin hafızadan karşılanması gerekir. Hafızadan karşılanan bu veri, önbellek değiştirme algoritmasına göre (aşağıda anlatılacaktır) önbellekte bir değiştirmeye sebep olur veya olmaz ancak her halükarda bir hafıza erişimi gerekecektir.

Örneğin hafıza erişiminin ardından verinin değiştirileceğini düşünelim. Bu durumda önbellekteki 01 indeksinde olan veri değiştirilecek ve hafızadan yüklenen veri bu indekse yazılacaktır. Doğrudan erişim algoritmasında verinin yazılabileceği tek adres bulunur.

Doğrudan haritalama yöntemini örnek bir şekil üzerinden gösterecek olursak:

Yukarıda görülen şekilde hafızada, örnek adresler verilmiştir. Elbette 8 bitlik hafızada daha fazla adres vardır ancak yukarıdaki temsili şeklin amacı durumu anlatmak olduğu için ilk iki biti aynı olan ikişer adres üzerinden örnek gösterilmiştir.

Yukarıda görüldüğü üzere hafızadaki adresler doğrudan önbellek üzerinde tek bir indekse haritalanmış ve birden fazla hafıza adresi aynı indekse haritalanmış durumdadır.

Küme ilişkilendirme (Set Associativity)

Bu erişim yönteminde bir önceki doğrudan erişimden farklı olarak veri kesin ve net bir şekilde bir yere eklenmez. Bunun yerine bir bilginin önbellek üzerinde gidebileceği birden fazla yer bulunur.

Bu küme ilişkilendirme yönteminde bir bilginin önbellek üzerinde gidebileceği alana göre sayılar belirtilir. Örneğin ön bellek üzerinde 2 farklı yere eklenebiliyorsa 2 yönlü küme ilişkilendirme (2-way set associativity) veya 4 farklı yere erişilebilirse dört yönlü küme ilişkilendirme (4-way set associativity) ismi verilir. Bu durumu aşağıdaki örnek üzerinden anlamaya çalışalım.

Örneğimizde bir önceki örnekle aynı yapıyı kullanalım ancak farklı olarak veri, hafıza adresinin ilk iki biti ve ilk iki biti +1 indekslerine yazılabilsin.

Yani bir bilgi aşağıdaki iki adresten birisinde indekslenecektir:

A : ilk iki bit değerindeki indeks

B: (ilk iki bit + 1) mod önbellek boyutu değerindeki indeks.

Bu durumda erişim aşağıdaki şekilde haritalanmış olacaktır:

Yukarıda görüldüğü üzere ilk iki bitine göre veri hem bu adrese hem de bu adresin bir sonraki adresine haritalanmıştır. Bu durumu aşağıdaki tablo ile de gösterebiliriz:

Yukarıdaki tabloda da gösterildiği üzere bir hafıza adresi iki farklı önbellek adresi ile haritalanmıştır.

Bu adresleme için örnek veri erişim tablomuz aşağıdaki şekilde olsun:

Yukarıda verilen sırayla erişimi aşağıdaki şekiller üzerinden açıklamaya çalışalım:

Yukarıdaki şekilde, daha önceki doğrudan haritalamadan farklı olarak yön (way) bitleri tutulmuştur. Bu bitlerin amacı bu indekste bulunan verinin aslında hangi yönden geldiğini tutmaktır. Örneğin 11 indeksine, 11 veya 10 yönünden veri yazılabilir bu durumda verinin hafıza adresini tam olarak bulabilmek için hangi yönden verinin yazıldığı tutulmalıdır.

İlk olarak 11 indeksine veriyi yerleştiriyoruz. Ardından gelen 10101001 adresindeki veri ilk iki biti itibariyle 10 adresine yerleştiriliyor.

Sonraki verimiz 10010101 adresinde. Bu verinin yerleştirileceği ilk adres, 10 indeksi dolu, 2 yönlü haritalama kullandığımız için bir sonraki alternatif adrese bakıyoruz ve 11 adresi kontrol ediliyor. Bu adres de dolu olarak görülüyor. Sonuçta önbellek üzerinde yerleştirilebilir bütün alanlar dolu olduğu için önbellek değiştirme algoritması devreye giriyor ve önbellekteki bilgilerden birisinin değiştirilmesi gerekiyor. Örneğin kullanacağımız değiştirme algoritması FIFO (ilk giren ilk çıkar (first in first out)) olsun. Bu durumda 10 ve 11 adreslerinden eski olanı ile yeni gelen veri değiştirilecektir. Şu anda eski olan bilgi 11 adresindeki bilgidir dolayısıyla önbelleğin yeni hali aşağıdaki şekilde olacaktır:

Yukarıdaki önbellek değiştirme (cache replacement) işleminin ardından 01001101 adresine erişim yapılıyor. Bu adres boş olduğu için ön bellek burada bilgiyi tutabilir:

Ardından gelen 11010101 erişimi ise yine önbellekte dolu olan indekse yapılmaktadır. Ancak 2 yönlü kümeleme kullanıldığı için veriyi diğer alternatifi olan ve şu anda boş olan 00 indeksine koyabiliriz:

Sonraki erişim 00101111 erişimidir. Burada yine FIFO önbellek değiştirme algoritması (cache replacement algorithm) gereği 00 ve 01 indekslerinden önce girenin değiştirilmesi gerekir. Bu bilgilerden 01 indeksindeki veri daha önce önbelleğe alındığı için veri buraya yerleştirilir:

Yukarıdaki önbellek yerleştirilmesinden sonra herhangi bir bilgiye erişilmek istendiğinde ilk iki bitine bakılır, ardından bu iki bitin girebileceği indeksler taranır.

Örneğin erişilmek istenen veri 11010101 adresinde olsun. Bu durumda ilk iki bite bakılıp 11 değeri ile arama yapılacak. 11 değeri ise 2 yönlü küme ilişkilendirmesi gereği 11 ve 00 adreslerinde tutulabilecek bilgidir. Bu durumda önbellekte iki yere de bakılacak 00 indeksindeki yön + etiket bilgisi aranan adresin bu indekste olduğunu gösterecek ve veri buradan karşılanacaktır.

Küme ilişkilendirme yöntemlerinde, verinin birden fazla yere yazılabilmesi, veriye erişim sırasında bütün bu alanların aranmasını gerektirir. Dolayısıyla önbellek üzerinde birden fazla erişime sebep olarak belki de önbellekte hiç tutulmayan bir veri için uzun süreli bir arama ile sonuçlanabilir.

Küme ilişkilendirme yöntemlerinin avantajı ise hiç erişilmeyen hafıza alanlarının önbellekte durmasını engellemesidir. Örneğin yukarıdaki şekil için, 00 ile başlayan hafıza alanına uzun süre hiç erişim olmayacağını düşünelim. Bu durumda doğrudan haritalama (Direct mapping) yöntemi bu önbellek alanını hiçbir zaman kullanmaz. Oysaki küme ilişkilendirme yönteminde alternatif bir önbellek indeksi bu alanı kullanabilir. Böylelikle önbelleğin daha verimli kullanılması sağlanır.

Bütün küme ilişkilendirme (full set associativity)

Bu yaklaşımda önbellekteki her indekste her adres durabilir. Yani bir önceki örnekte iki yönlü küme ilişkilendirme sırasında bir hafıza adresi, sadece iki indeksten birisine gidebilirken şimdi bütün önbelleğe yerleştirilebilir. Bu durumda önbellekteki arama süresi uzarken, önbellekte atıl kalan indeks miktarı azaltılmış olunur.

Önbellek değiştirme algoritmaları (Cache replacement algorithms)

Bu algoritmaların amacı, önbellek üzerinde küme ilişkilendirilmesi kullanıldığında ve verinin önbellekte birden fazla alana yazılabileceği durumlarda nereye yazılacağını belirlemektir.

Temel olarak aşağıdaki algoritmalar en bilinenleri olarak sayılabilir:

FIFO , first in first out , ilk giren ilk çıkar

LRU, least recently used, en eski erişilen

LFU, least frequently used, en seyrek erişilen

MRU, most recently used, en son erişilen

Belady’s, Belady’s algorithm, Belady algoritması

Yukarıdaki bu algoritmaları sırasıyla örnek üzerinden anlatmaya çalışalım. Örneğimizdeki önbelleğin iki indeksi bulunsun ve bütün küme ilişkilendirmesi (fully set associative) yapısında olsun. Buna göre aşağıdaki veriler önbelleğe geldiğinde sırasıyla yukarıdaki değiştirme algoritmalarının nasıl çalıştığını görelim:

Yukarıdaki verileri aşağıdaki önbellek yapısına sırasıyla yerleştireceğiz. 2 satırdan oluşan önbelleği indekslemek için tek bit yeterlidir. Bu durumda hafıza adresinin ilk bitini önbellek indekslemesi için kullanacağız.

Bu durumda yukarıdaki ön bellek üzerinde bütün küme ilişkilendirme kullanılacaktır. Aslında önbellek iki satırdan oluştuğu için 2 yönlü küme ilişkilendirme de denilebilir.

FIFO (First in first out, ilk giren ilk çalışır)

Bu algoritmada, önbellekte bir bilgi yazılacağı sırada, önbelleğe ilk girmiş, en eski verinin üzerine yazılması tercih edilir.

Yukarıdaki verilere erişimi sıra ile aşağıdaki şekiller üzerinden anlamaya çalışalım. İlk erişim 11010100 adresine yapılıyor.

Bu adres 1 ile başladığı için 1. İndekse yerleştiriyoruz. Ardından gelen veri de 1 ile başladığı için 1. Adrese yerleşmesi gerekiyor ancak bu adres dolu ve 0. Adres boş, o halde boş olan yere yerleştiriliyor:

Şimdi gelen veri ise hem 0 hem de 1 e yerleşebilir (bütün küme ilişkilendirmesi olduğu için) dolayısıyla FIFO devreye giriyor ve en eski olan “www.” Bilgisi kaldırılıp yerine yazılıyor.

Sonraki veri yine iki indekse de yazılabilecek durumda ve veri en eski olan “bilgisayar”‘ın üzerine yazılıyor.

LRU (Least Recently Used, En Eski Erişilen)

Bu önbellek değiştirme algoritmasında amaç, önbellekte yapılan erişimleri takip etmek ve en geç erişilmiş olan veriyi değiştirmektir. Örneğimizi yine yukarıdaki gibi 2 satırlı bir önbellek üzerinden ve aşağıdaki erişim sırasıyla takip etmeye çalışalım:

1010 1010

0100 0100

1010 1010

1101 1111

0100 0100

Yukarıdaki bu erişim sıralarına göre önbellek üzerindeki yerleşimler aşağıdaki şekilde olacaktır. İlk gelen iki veri sırasıyla önbelleğe yerleştirilecektir, buraya kadar herhangi bir değiştirme algoritmasına ihtiyaç duyulmaz.

Ardından 1. İndekste bulunan veriye ikinci kere erişilir. Buradan anlaşılacağı üzere en son erişilen veri ikinci satırdaki veridir. Yeni gelen veri en eski erişilmiş olan verinin üzerine yazılır:

Şu anda en son erişilen veri yeni yazdığımız veridir ve yeni gelen veri diğer verinin üzerine yazılır:

Görüldüğü üzere bu algoritmada, her zaman için en eski erişilmiş olan verinin üzerine yeni gelen veri yazılmaktadır.

LFU (Least frequently used, en nadir kullanılan veya en seyrek kullanılan)

Bu algoritmada amaç ön bellekte bulunan verilere yapılan erişim miktarlarını saymak ve bu erişim miktarlarından en az olanını değiştirmektir.

Bu durumu yine bir önceki alt başlıkta incelediğimiz örnek üzerinden anlamaya çalışalım.

1010 1010

0100 0100

1010 1010

1101 1111

0100 0100

Yukarıdaki bu erişim sıralarına göre önbellek üzerindeki yerleşimler aşağıdaki şekilde olacaktır. İlk gelen iki veri sırasıyla önbelleğe yerleştirilecektir, buraya kadar herhangi bir değiştirme algoritmasına ihtiyaç duyulmaz.

Ardından 1. İndekste bulunan veriye ikinci kere erişilir. Buradan anlaşılacağı üzere en son erişilen veri ikinci satırdaki veridir. Yeni gelen veri en az erişilmiş olan verinin üzerine yazılır. Burada en az erişilen veri 0. İndekste olan veridir.

Yeni yüklenen veri, şu andaki en az erişilmiş olan veridir. Dolayısıyla değiştirme işlemi yine 0. Satırdaki veri üzerine yapılır.

Görüldüğü üzere değiştirme işlemi sürekli olarak, o ana kadar en az erişilen önbellek alanında olmaktadır.

MRU (Most Recently Used, En sık kullanılan)

Bu değiştirme algoritmasında amaç en son erişilen veriyi değiştirmektir. Bu algoritma ilk başta çok anlamlı gelmeyebilir, sonuçta önbellekteki en taze bilgi en son erişilen bilgidir ve dolayısıyla işlemcinin bir sonraki adımda erişme ihtimali yüksek olan veridir.

Ancak bazı durumlarda anlamlı olabilir. Örneğin bir dosyadan sürekli olarak okuma yapıldığını veya bir sıkıştırma algoritmasının büyük bir dosyayı açmak için uğraştığını dolayısıyla hafızada yüklü bu dosyanın sürekli işlemci üzerinde işlendiğini ve işlenen bir veriye bir daha geri dönülmeyeceğini düşünün.

Örneğin 100MB boyutundaki sıkıştırılmış bir dosyayı açmak istiyoruz. Bu durumda dosyadan okunan ve işlenen bir bilgi kısmı açılacak ve işlemcinin dosyanın bu kısmı ile olan işi bitecektir.

Bundan sonraki adımlarda önbelleğe yüklenen verilerin tamamı taze olacak ve daha önceden yüklenen bir veriye ihtiyaç duyulmayacaktır.

Bu durumda önbelleğin bir daha kullanılmayacak veriler ile işgal edilmesi yerine önbellek üzerinde en son erişilen verinin değiştirilmesi ve diğer işlemlerin önbellek üzerinde kullandıkları verilerin daha sonraki erişimler için saklanması mantıklı olur.

Bu algoritmanın çalışmasını yine bir örnek üzerinden inceleyelim.

1010 1010

0100 0100

1010 1010

1101 1111

0100 0100

Yukarıdaki bu erişim sıralarına göre önbellek üzerindeki yerleşimler aşağıdaki şekilde olacaktır. İlk gelen iki veri sırasıyla önbelleğe yerleştirilecektir, buraya kadar herhangi bir değiştirme algoritmasına ihtiyaç duyulmaz.

Ardından 1. İndekste bulunan veriye ikinci kere erişilir. Buradan anlaşılacağı üzere en son erişilen veri ikinci satırdaki veridir. Yeni gelen veri en son erişilmiş olan verinin üzerine yazılır. Burada en az erişilen veri 1. İndekste olan veridir.

Yeni yüklenen veri, şu andaki en son erişilmiş olan veridir. Gelen erişim talebi ise zaten önbellekte bulunan veridir ve herhangi bir değiştirme işlemi gerekmeden çalışma sonuçlanır.

Belady’s Algorithm (Belady algoritması)

Teorik olarak tanımlı olan bu algoritmanın gerçekte uygulanması mümkün değildir. Bu algoritma temel olarak ileride en çok erişilecek hafıza adreslerini önbellekte tutmayı hedefler. Elbette gerçekte bir çalışma olmadan ileride neyin çalışacağı bilinemeyeceği için de bu algoritmanın kullanılması imkansızdır.

Yine bir örnek üzerinden algoritmanın çalışmasını inceleyelim:

1010 1010

0100 0100

1010 1010

1101 1111

0100 0100

Yukarıdaki bu erişim sıralarına göre önbellek üzerindeki yerleşimler aşağıdaki şekilde olacaktır. İlk gelen iki veri sırasıyla önbelleğe yerleştirilecektir, buraya kadar herhangi bir değiştirme algoritmasına ihtiyaç duyulmaz.

Ardından 1. İndekste bulunan veriye ikinci kere erişilir. Daha sonra gelen erişimler incelendiğinde sıradaki erişim olan 11011111, şu anda 1. İndekste olan değer ile değiştirilmelidir çünkü 0100 0100 adresine ileride erişim olacaktır ve bu bilgi ile değiştirilmesi durumunda ileride yine bir önbellek değiştirme işlemi gerekecektir.

Görüldüğü üzere ileride yapılacak değişiklik önceden hesaplanmış ve bunu engellemek için en makul değişiklik yapılmıştır.

Sonuçta bu algoritma ile her zaman en az önbellek kayıp oranı (cache miss) yakalanır.

Kaynakça

Aşağıdaki kitaplar kaynak olarak kullanılmıştır.

• Morris Mano, Computer System Architecture
• Tanenbaum, Structured Computer Organization
• J. Hayes, Computer Architecture and Organization
• R. Williams, Computer System Architecture
• D.A. Patterson, J.L. Hennessy, Computer Organization and Design
• V.C. Hamacher, Z. Vranesic, S. G. Zaky, Computer Organization