noimage

İçeriği Paylaş:

Sayfa Yerdeğiştirme Algoritmaları (Page Replacement Algorithms)

Sayfa Yerdeğiştirme Algoritmaları (Page Replacement Algorithms)Sistemde bir sayfa hatası(page fault) görülürse, işletim sistemi bellekten bir sayfayı kaldırmak için seçmelidir.Seçilen ve bellekten çıkarılan sayfa yerine, yeni sayfa gelecektir.Eğer bellekten kaldırılacak olan sayfa bellekte iken değiştirilmiş ise, diskteki kopyanın güncel olması için tekrar bellekten diske yazılmalıdır. Değiştirilmemiş ise diske yapılmasına gerek yoktur.Her sayfa hatasında yoğun olarak kullanılmayan sayfanın çıkarılması, sistemin performansını arttırır. Yoğun kullanılan bir sayfa çıkarılırsa çok kısa bir süre sonra bu sayfa tekrar istenebilir.Sayfa yer değiştirme algoritmaları üzerinde çok fazla teorik ve deneysel çalışma yapılmıştır.Sayfa yer değiştirme algoritmaları bilgisayarda farklı alanlarda kullanılmaktadır. (Örn: cache, web sunucularında, …)En iyi sayfa yerdeğiştirme algoritmasıEn iyi sayfa yer değiştirme algoritması kolaylıkla tanımlanır fakat uygulanamaz.Algoritma şudur: sayfa hatasının görüldüğü anda, bellekte sayfa kümeleri bulunmaktadır. Bu sayfalardan bir tanesine bir sonraki komutta(instruction) başvurulacaktır.Bu komutu içermeyen sayfalara belkide 10,100,1000,… komut sonrasına kadar erişim gerçekleşmeyecektir.Her sayfa erişim işlemi yapılmadan kaç komut geçeceği ile etiketlenebilir.En iyi sayfa algoritması en yüksek etiketli sayfanın kaldırılması gerektiğini söyler.Elimizde 8 milyon komut sonra ve 6 milyon komut sonra erişilecek iki sayfa var ise, birinci sayfanın bellekten çıkarılması daha mantıklıdır.Bu algoritmanın gerçekleştirilememe nedeni: işletim sisteminin sayfa hatası olduğunda sayfaların bir sonraki erişilme zamanlarını bilmemesidir.Son Zamanlarda kullanılmayan sayfanın yer değiştirilmesi algoritmasıİşletim sisteminin hangi sayfaların kullanılıp kullanılmadığı hakkında kullanışlı istatistikler sağlamak için, her sayfa için 2 bit kullanılmaktadır. R(Referenced)başvuruldu, M(Modified)değiştirildi bitleri. R biti bu sayfaya erişildiği zaman 1 lenir. M de bu sayfaya yazma gerçekleştiği zaman 1 lenir.image005Bu bitler her bellek başvurusunda güncellenmelidir, bu yüzden donanım ile yapılmalıdır. Birkez bir bit 1 olduğunda işletim sistemi onu 0 yapmadan 1 kalır.Eğer donanımda bu bitler yok ise şu şekilde benzetim yapılır. Bir süreç çalışmaya başladığında, tüm sayfa tablosu girdileri bellekte değil olarak işaretlenir. Bir sayfaya başvuru yapıldığında sayfa hatası(page fault) görülür.İşletim sistemi kendi tablolarındaki sayfa bilgilerini tutantabloda R bitini günceller ve sayfa tablosu girdisini doğru tabloyu gösterecek şekilde günceller. Bu sayfayı sadece okunabilir yapar. Daha sonra bu sayfaya yazılmak istenildiğinde başka bir hata meydana gelir.İşletim sistemi bu sayede yazılma işleminide anlar ve sayfanın M bitini 1 ler ve sayfayı R/W olabilir yapar.P ve M bitleri kullanılarak basit bir sayfa yer değiştirme algoritması (PRA) oluşturulabilir. Bir süreç çalışmaya başladığında tüm sayfaları için R ve M biti 0 lanır.Periyodik olarak (her saat kesmesinde) R biti 0 lanır.Bu işlem son zamanlarda kullanılmayan sayfanın belirlenmesi için gereklidir.Bir sayfa hatası meydana geldiğinde, işletim sistemi sayfaları araştırır ve sayfaları 4 kategoriye ayırır. Bu kategoriler R ve M bitinin durumlarıdır.Sınıf 0: başvurulmamış  ve değiştirilmemiş                                                                       = 0 0Sınıf  1: başvurulmamış, değiştirilmiş                                                                       = 0 1Sınıf  2: başvurulmuş, değiştirilmemiş                                                                       = 1 0Sınıf  3: başvurulmuş, değiştirilmiş                                                                       = 1 1

  1. sınıf hiçbir zaman oluşmaz gibi görünsede 3. sınıfda R=0 landığında 1. sınıf oluşur.

NRU (Not Recently Used) algoritması boş olmayan en düşük numaralı sınıflardan bir sayfayı rastgele seçer.

İçeriği Paylaş:
İlginizi Çekebilir
Yorum Yapılmamış

Henüz Hiç Yorum Yapılmadı..

Yorum Yaz

Sayfa Yerdeğiştirme Algoritmaları (Page Replacement Algorithms)

İşletim Sistemleri

26/08/2017 | Yorum Yok | 102 | Mustafa Küçükakarsu