Yazan : Şadi Evren ŞEKER

Bilgisayar bilimlerinde özellikle işletim sistemi konusunda kullanılan ve hafızanın daha verimli çalışması için geliştirilmiş algoritmaların ismidir.

İçerik
Arkaplan ve ön bilgiler
FIFO
LRU
Optimal Replacement

Algoritmanın arka planı ve gerekli ön bilgiler

Bilindiği üzere bilgisayarda hafızanın yönetimini (Memory management) işletim sistemi yapmaktadır. Dolayısıyla başarılı bir hafıza yönetiminde, hafızada (RAM) bulunan boşluk kırıntıları (Fragment) en az olmalıdır. Bu boşlukları en aza indirgemek için sayfalama (Paging) yöntemi kullanılır. Sayfalama yönteminde harici boşluk kırıntısı (External Fragment) bulunmaz. Bunun yerine bir sayfaya sığmayan işlemler için iç boşluk kırıntıları (internal fragment) bulunabilir ve bu boşlukların azami değeri sayfa boyutunu aşamaz. Yani bir anlamda hafızanın verimsizleşmesine sebep olan boşluklar kontrol altına alınmış olunur.

Hafıza yönetiminin diğer bir problemi ise, bilgisayar hafızasının yetersiz olduğu durumlarda işlemleri çalıştıramamasıdır. Örneğin 1GB boş hafızası olan bir bilgisayarda 3GB boyutunda işlemlerin çalışması normalde imkansız gibidir. Ancak bu duruma karşı çözüm olarak sanal hafıza (Virtual memory veya Unix terminolojisinde takas alanı, swap) geliştirilmiştir. Basitçe RAM’e sığmayan bilgiler diskin bir kısmında saklanmakta ve gerekli oldukça diskten RAM’e yüklenmektedir. Tabi diskten RAM’e yükleme sırasında tam dolu bir RAM’de yer açmak için de bir kısım bilgi RAM’den diske geri yazılmaktadır.

İşte sayfa değiştirme algoritmaları tam bu noktada devreye girmektedir. Basitçe bilgisayarın hafızası sayfalara (pages) bölünmekte ve çalışan işlemler (processes) bu sayfalara yerleştirilmektedir. Sonuçta sınırlı hafıza ve sınırın üzerinde hafıza ihtiyacı olduğu durumlarda bazı sayfalar (page) diske yazılmaktadır. Hangi sayfanın hafızada (RAM) ve hangi sayfanın diskte bulunacağını ve ne zaman yer değiştireceklerini belirleyen algoritmalar sayfa değiştirme algoritmalarıdır.

fifo Page Replacement Algorithm (İlk giren ilk çıkar sayfa değiştirme algoritması)

Bu algoritmaya göre bir sayfa ihlali (page fault) olduğunda, yani hafızada (RAM) bulunmayan bir sayfaya erişilmek istendiğinde, yani diskteki bir sayfaya erişilmek istendiğinde, Diskten ilgili sayfa hafızaya (RAM) yüklenirken, hafızadaki en eski sayfa yerine yüklenir ve bu en eski sayfa da diske geri yazılır.

Bu algoritmayı bir örnek üzerinden inceleyelim.

Örneğin işletim sisteminden sırasıyla aşağıdaki çerçeveler (Frames) yani sayfalar talep ediliyor olsun:

1,2,3,2,3,4,5,3,1

ve ayrıca hafızamıza (RAM) sadece 3 çerçeve anlık olarak sığabiliyor olsun. Bu durumda her talepten sonra hafızadaki çerçeveler (frames, sayfalar, pages) aşağıdaki şekilde olacaktır.

1. sayfa talebinde sayfa ihalali (page fault) olur çünkü henüz hafızada olmayan bir sayfa talep edilmiştir.

|1| | |

2. sayfa talebinde sayfa ihlali yolur çünkü 2. sayfa da henüz hafızada bulunmamaktadır.

|1|2| |

3. sayfa talebinde yeniden bir sayfa ihlali bulunur sebebi 3. sayfanın da henüz hafızada olmamasıdır:

|1|2|3|

3. sayfadan sonra artık hafızamız tamamen dolmuştur çünkü hafıza kapasitesi 3 sayfa taşıyacak şekilde tanımlanmıştır.

4. sayfa talebinde zaten hafızada bulunan 2. sayfa istenir ve bir sayfa ihlali oluşmaz.

5. sayfa talebinde de benzer şekilde zaten hafızada bulunan 3 numaralı sayfa talep edilir ve bir sayfa ihlali oluşmaz.

6. sayfa talebinde hafızada bulunmayan 4 numaralı sayfa talep edilir ve bir sayfa ihlali oluşur. İşte tam bu noktada FIFO algoritması devreye girer. Çünkü hafıza tamamen doludur ve 4 numaralı sayfanın hafızaya yüklenmesi için hafızadaki sayfalardan birisinin kaldırılması gerekmektedir. Soru hangisinin kaldırılacağıdır.

FIFO algoritmasına göre en eskisi kaldırılır. Yani 1 numaralı sayfa ilk gelen olduğu için ilk kaldırılan olur ve 1 numaralı sayfa yerine 4 numaralı sayfa yerleştirilir:

|4|2|3|

7. sayfa talebinde yine hafızada o anda bulunmayan 5 numaralı sayfa talep edilmiştir. Bu durumda yeni bir sayfa ihlali oluşacak ve 5 numaralı sayfa o anda hafızada bulunan en eski sayfa yerine yerleştirilecektir. Bu en eski sayfa 2 numaralı sayfadır ve sayfa yerleştirilmesi (page replacement) işleminden sonra hafızadaki sayfalar aşağıdaki şekildedir:

|4|5|3|

8. sayfa talebinde 3 numaralı sayfaya erişilmek istenmiştir ve bu sayfa hal-i hazırda bellekte bulunmaktadır dolayısıyal bir sayfa ihalali oluşmaz ve doğrudan hafızadan ihtiyaç karşılanır.

9. sayfa talebinde ise daha önceden hafızada olan ancak şu anda hafızada bulunmayan 1 numaralı sayfa istenmiştir. Bu durumda bu sayfa hafızada olmadığı için sayfa ihlali olur ve 1 numaralı sayfa hafızadaki en eski sayfanın yerine yani 3. numaralı sayfanın yerine yerleştirilir ve son halinde:

|4|5|1|

şeklinde bir hafıza sayfa dizilimine erişilmiş olur.

Yukarıdaki bu örnekte toplam 9 sayfa için 6 sayfa ihlali olmuştur. Bu durumda sayfa ihlal oranı (Page fault rate) 0.66 olarak bulunmuş olunur.
Least Recently Used (LRU) Page replacement (En nadir kullanılan sayfa değiştirme algoritması)

Bu algoritmaya göre bir sayfa ihlali (page fault) olduğunda, yani hafızada (RAM) bulunmayan bir sayfaya erişilmek istendiğinde, yani diskteki bir sayfaya erişilmek istendiğinde, Diskten ilgili sayfa hafızaya (RAM) yüklenirken, hafızadaki en az erişilen sayfa yerine yüklenir ve bu en az kullanılan sayfa da diske geri yazılır.

Bu algoritmayı bir örnek üzerinden inceleyelim.

Örneğin işletim sisteminden sırasıyla aşağıdaki çerçeveler (Frames) yani sayfalar talep ediliyor olsun:

1,2,3,2,3,4,5,3,1

ve ayrıca hafızamıza (RAM) sadece 3 çerçeve anlık olarak sığabiliyor olsun. Bu durumda her talepten sonra hafızadaki çerçeveler (frames, sayfalar, pages) aşağıdaki şekilde olacaktır.

1. sayfa talebinde sayfa ihalali (page fault) olur çünkü henüz hafızada olmayan bir sayfa talep edilmiştir.

|1| | |

2. sayfa talebinde sayfa ihlali yolur çünkü 2. sayfa da henüz hafızada bulunmamaktadır.

|1|2| |

3. sayfa talebinde yeniden bir sayfa ihlali bulunur sebebi 3. sayfanın da henüz hafızada olmamasıdır:

|1|2|3|

3. sayfadan sonra artık hafızamız tamamen dolmuştur çünkü hafıza kapasitesi 3 sayfa taşıyacak şekilde tanımlanmıştır.

4. sayfa talebinde zaten hafızada bulunan 2. sayfa istenir ve bir sayfa ihlali oluşmaz.

5. sayfa talebinde de benzer şekilde zaten hafızada bulunan 3 numaralı sayfa talep edilir ve bir sayfa ihlali oluşmaz.

6. sayfa talebinde hafızada bulunmayan 4 numaralı sayfa talep edilir ve bir sayfa ihlali oluşur. İşte tam bu noktada LRU algoritması devreye girer. Çünkü hafıza tamamen doludur ve 4 numaralı sayfanın hafızaya yüklenmesi için hafızadaki sayfalardan birisinin kaldırılması gerekmektedir. Soru hangisinin kaldırılacağıdır.

LRU algoritmasına göre en az erişileni kaldırılır. Yani 2 numaralı sayfa 2 kere, 3 numaralı sayfaya da 2 kere erişilmiştir. Bu durumda bir kere erişilen tek sayfa olan 1 yerine 4 numaralı sayfa yerleştirilir:

|4|2|3|

7. sayfa talebinde yine hafızada o anda bulunmayan 5 numaralı sayfa talep edilmiştir. Bu durumda 4 numaralı ve en az erişilmiş olan sayfa yerine 5 numaralı sayfa yerleştirilir.

|5|2|3|

8. sayfa talebinde 3 numaralı sayfaya erişilmek istenmiştir ve bu sayfa hal-i hazırda bellekte bulunmaktadır dolayısıyal bir sayfa ihalali oluşmaz ve doğrudan hafızadan ihtiyaç karşılanır.

9. sayfa talebinde ise daha önceden hafızada olan ancak şu anda hafızada bulunmayan 1 numaralı sayfa istenmiştir. Bu durumda bu sayfa hafızada olmadığı için sayfa ihlali olur 1 numaralı sayfa o anda hafızada bulunan en nadir erişilmiş sayfa yerine yerleştirilecektir. Bu en az erişilen sayfa 4 numaralı sayfadır ve sayfa yerleştirilmesi (page replacement) işleminden sonra hafızadaki sayfalar aşağıdaki şekildedir:

|1|2|3|

şeklinde bir hafıza sayfa dizilimine erişilmiş olur.

Yukarıdaki bu örnekte toplam 9 sayfa için 6 sayfa ihlali olmuştur. Bu durumda sayfa ihlal oranı (Page fault rate) 0.66 olarak bulunmuş olunur.

Optimal Replacement (Mükemmel Sayfa Değiştirme Algoritması)

Bu algoritma, hiç bir zaman gerçekleştirilemeyecek hayali bir algoritmadır. Akademik olarak ortaya atılmıştır ve algoritmanın çalışması için daha sonra gelecek olan sayfa ihtiyaçlarının önceden bilinmesi gerekir. Bu sayfa değiştirme algoritmasına göre bir sayfa ihlali (page fault) olduğunda, yani hafızada (RAM) bulunmayan bir sayfaya erişilmek istendiğinde, yani diskteki bir sayfaya erişilmek istendiğinde, Diskten ilgili sayfa hafızaya (RAM) yüklenirken, hafızada bundan sonra en uzun süre erişilmeyecek olan yerine yüklenir ve bu en az kullanılan sayfa da diske geri yazılır.

Bu algoritmayı bir örnek üzerinden inceleyelim.

Örneğin işletim sisteminden sırasıyla aşağıdaki çerçeveler (Frames) yani sayfalar talep ediliyor olsun:

1,2,3,2,3,4,5,3,1

ve ayrıca hafızamıza (RAM) sadece 3 çerçeve anlık olarak sığabiliyor olsun. Bu durumda her talepten sonra hafızadaki çerçeveler (frames, sayfalar, pages) aşağıdaki şekilde olacaktır.

1. sayfa talebinde sayfa ihalali (page fault) olur çünkü henüz hafızada olmayan bir sayfa talep edilmiştir.

|1| | |

2. sayfa talebinde sayfa ihlali yolur çünkü 2. sayfa da henüz hafızada bulunmamaktadır.

|1|2| |

3. sayfa talebinde yeniden bir sayfa ihlali bulunur sebebi 3. sayfanın da henüz hafızada olmamasıdır:

|1|2|3|

3. sayfadan sonra artık hafızamız tamamen dolmuştur çünkü hafıza kapasitesi 3 sayfa taşıyacak şekilde tanımlanmıştır.

4. sayfa talebinde zaten hafızada bulunan 2. sayfa istenir ve bir sayfa ihlali oluşmaz.

5. sayfa talebinde de benzer şekilde zaten hafızada bulunan 3 numaralı sayfa talep edilir ve bir sayfa ihlali oluşmaz.

6. sayfa talebinde hafızada bulunmayan 4 numaralı sayfa talep edilir ve bir sayfa ihlali oluşur. İşte tam bu noktada Optimal Replacement algoritması devreye girer. Çünkü hafıza tamamen doludur ve 4 numaralı sayfanın hafızaya yüklenmesi için hafızadaki sayfalardan birisinin kaldırılması gerekmektedir. Soru hangisinin kaldırılacağıdır.

Optimal Replacement algoritmasına göre en uzun süre erişilmeyecek olanı kaldırılır. Yani 2 numaralı sayfaya çalışma sonuna kadar erişilmeyeceği için bu sayfa kaldırılacak ve yerine 4 numaralı sayfa konulacaktır. Diğer sayfalar (1 ve 3) 2′den daha önce erişilecektir.

|1|4|3|

7. sayfa talebinde yine hafızada o anda bulunmayan 5 numaralı sayfa talep edilmiştir. Bu durumda hafızada bulunan sayfalar tekrar incelenir ve 4 numaralı sayfanın çalışma sonuna kadar bir daha erişilmeyeceği görülerek bu sayfa yerine 5 konulur.

|1|5|3|

8. sayfa talebinde 3 numaralı sayfaya erişilmek istenmiştir ve bu sayfa hal-i hazırda bellekte bulunmaktadır dolayısıyal bir sayfa ihalali oluşmaz ve doğrudan hafızadan ihtiyaç karşılanır.

9. sayfa talebinde ise daha önceden hafızada olan ancak şu anda hafızada bulunmayan 1 numaralı sayfa istenmiştir. Bu durumda da bir sayfa ihlali oluşmaz

|1|5|3|

şeklinde bir hafıza sayfa dizilimine erişilmiş olur.

Yukarıdaki bu örnekte toplam 9 sayfa için 5 sayfa ihlali olmuştur. Bu durumda sayfa ihlal oranı (Page fault rate) 0.55 olarak bulunmuş olunur.