Sayfa yer değiştirme algoritması(Page Replacement) nedir?

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ı)

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, 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.