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 eski erişilen kaldırılır. Buna göre en son erişilen iki sayfa, 5. ve 6. adımlardaki 2. ve 3. sayfalardır. Dolayısıyla 1. sayfa, şu anda en eski erişilmiş olandır ve hafızadan kaldırılır.
|4|2|3|
7. sayfa talebinde yine hafızada o anda bulunmayan 5 numaralı sayfa talep edilmiştir. Bu durumda 2 numaralı ve en eski erişilmiş olan sayfa yerine 5 numaralı sayfa yerleştirilir.
|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 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|5|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, 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.
teşeküürler. güzel bir anlatım olmuş. yazıyı okuduktan sonra kafamda şu soru belirdi. misal bir process var. process initalize edilirken belli bir miktar bellek ayırıyor. 16K bellek ayırdık yani 4 adet page’e denk geliyor. initialize olduktan sonra process saatte bir bu bellek bölgesiyle bir iş yapması lazım. bu bir saatlik dilim içinde işletim sistemi bu belleği diske swap etti. ve process’in bu alanla işlem yapma vakti geldi ve bu bellek bilgisi ram üzerine eşlenmemiş durumda. ilk erişim denemesinde sayfa hatası oluştuğunda işletim sistemi bu sayfaya erişim isteğini anladı ve tekrar ram’e eşledi diyelim. ama benim process’im neden ilk denemede bu bilgiyi alamıyor da 2. denemede almak zorunda kalıyor? kaldıki ikinci bir çalışma döngüsüne gelene kadar işletim sistemi bu alanı tekrar swap edebilir. o zaman yeni baştan bir erişim gerekiyor. işletim sistemi mantıksal adresi kullanarak hangi bilgi hangi sayfada olduğuna bakıp orada bir geçerli bilgi yoksa bunu page fault oluşmadan diskten okuyup ram’e eşleyip ilk isteğimde fault oluşmadan okuması gerekmez mi? bu konuda biraz kafam karıştı. yoksa page fault olup bilgi ilgili yere eşledikten sonra erişim isteğini yapan makine komutuna geri dönüp tekrar bir okuma mı yapıyor?
selam ben senay, gercekten super bir blog, eger facebook veya twitter varsa eklemek isterim…
http://www.xn--rrup-0ra.net/
Mükemmel Sayfa Değiştirme Algoritması, 9. sayfa talebinde 1 numarali sayfa hafizadaki yerini hic kaybetmedi o yuzden su anda hafizada bulunmayan ibaresi cumleyi ihlal etmis gibi duruyor.
evet haklısınız, yazıda düzeltiyorum. Teşekkürler.
asagidaki sorulari cözmeme yardimci olacak turkce dökuman veya turkce cözumleri…
1. Consider a demand paging system. The system will use 8 milliseconds to fulfill a page fault if a new empty page frame is available. If not so the time spent for the page fault will be 20 milliseconds. The memory average access time is 100 nanoseconds. Statistics show that around 70 % of the page faults is with the need of creating a new empty page. Calculate the largest possibility to get a page fault within this system if we want the system average access time not to exceed 200 nanoseconds.
2. Consider a demand-paging system with the following time-measured utilizations:
CPU utilization 20%
Paging disk 97.7%
Other I/O devices 5%
Which (if any) of the following will (probably) improve CPU utilization? Explain your answer.
a. Install a faster CPU.
b. Install a bigger paging disk.
c. Increase the degree of multiprogramming.
d. Decrease the degree of multiprogramming.
e. Install more main memory.
f. Install a faster hard disk or multiple controllers with multiple hard disks.
g. Add prepaging to the page fetch algorithms.
h. Increase the page size.
Lru algoritmasina gore 3 cerceve var ve bu siralista islemler geliyor
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
ve bende yukaridaki anlatima gore bu örnegi yaptigimda bu sonuc cikiyor.
7, 70, 701, 201, —, 203, —, 403, 402, 302, —, —, —, 102, —, —, —, 702, —, 102
Fakat sonuc asagidaki gibiymis. Sanirim bi yeri anlayamamisim ama nereyi?
7, 70, 701, 201, —, 203, —, 403, 402, 432, 032, —, —, 132, —, 102, —, 107, —, —,
hatanız least recently used algoritmasını yanlış tercüme etmeniz. Least recently used, en son erişilmeyen, en eski erişilen anlamındadır. Yani en az erişilen değildir. Siz sanki erişim sayılarını saymış ve en az sayıda erişileni değiştirmişsiniz. Bakın 10. adıma kadar aynı gitmişsiniz. Farklılığın başladığı yere bakarsak sorunu çözeriz. 302 / 432 sayfalarına baktığınızda (bir önceki adımda iki çözüm de 402) sizin çözümünüz 0 ve 2 yi tutup 4’ü değiştirirken diğer çözüm 4 ve 2yi tutup 0’ı değiştirmiştir.
sorumuz şu, acaba bu adımda 0 mı 4 mü daha eski erişilmiştir.
0’a en son erişim 7. adımda
4’e erişim ise 8. adımdadır.
Bu durumda LRU (least recently used) algoritması en eski erişileni değiştirecektir. Görüldüğü üzere en son erişilen 4 olduğu için 4 tutulup 0 değişecektir.
evet ben en az erisilen sayfa ile degistirmisim, simdi en uzun zaman kullanilmamis ile degistirdigimde oluyor. tesekkurler….
bu dersimize giren hoca beni nefret ettirdi bilgisayardan bu dersin bu konusuna girmemistim zaten.size birşey sormak istiyorum .LRU illa FIFO sikinti yarattiginda mi ortaya cikiyor?Yani ne zaman hafıza dolarsa direk LRU ‘ya mı basvuracaz? Yani mesela sınavda hoca 1,2,3,1,4,3,2,2,1 verse
a şıkkında LRU
b şıkkında FIFO
c şıkkında Optimal
d şıkkında her bir algoritma icin pfault ‘u soramaz mı ?bilmem anlatabildim mi? teşekkürler
Merhabalar.”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”..
Burada “erişilmek ” kavramıyla ve “2 numaralı sayfaya 2 kere ” erişilmesi olayını tam açıklar mısınız?
Alıntıladığınız satır hatalıydı. LRU algoritması en eski erişileni kaldırıyor en az erişileni değil (en az erişileni LFU, least frequently used algoritmasının kaldırması gerekir). Hatayı yazıda düzelterek aşağıdaki şekle getirdim:
“LRU algoritmasına göre en eski erişilen kaldırılır. Buna göre en son erişilen iki sayfa, 5. ve 6. adımlardaki 2. ve 3. sayfalardır. Dolayısıyla 1. sayfa, şu anda en eski erişilmiş olandır ve hafızadan kaldırılır.”
ilginiz için çok teşekkür ederim.
İyi akşamlar.Cevabınız için çok teşekkür ederim.Yarin quiz var.Quizde soru sorulsa ve ben sıra(sı)yla;
1
1 2 3
1 2 3
……. (yani fault oluşmayanları da alt alta yazsam sırayla-sizin yazıyla dediklerinizi yapsam- ve her faultte * işareti koysam)
9 tane de 6 tane fault var diye belirtsem hocaya mantıksız olur mu ?
hocanızın sınavınızı nasıl değerlendireceğini bilemem. Her hocanın, ders anlatışına göre, dikkat ettiği farklı noktalar olabilir. Ancak benim kişisel görüşüm, yukarıdaki yazıda olduğu gibi, erişilen çerçevelerin (frame) sırası verildiğinde, bir şekilde sayfalamanın nasıl yapıldığını ve adım adım nasıl değişip hangi adımlarda sayfa ihlalini (page fault) göstermenizin yeterli olduğudur. Bu gösterim için bahsettiğiniz yazım şekli bence yeterli olur.
başarılar
Merhaba,çok bilgilendirici bir makaleydi.Teşekkürler fakat aklıma takılan bir sorun var.FIFO algoritmasında baştaki sayfa çıkarılıp yeni gelen sayfa sona eklenmiyor muydu?Örneğin 6.adımda 4.sayfaya istekte bulunulmuş 1 kaldırılıp yerine 4.sayfayı yerleştirmişsiniz.2 3 4 şeklinde olması gerekmniyor mu?Yardımcı olursanız sevinirim.
fifo algoritmasında o şekilde zaten. sırasını kastediyorsanız önemli değil yani 423 ile 234 aynıdır. Ama optimal replacement veya lru için farklı uygulamalar bulunuyor ki bunlar da yazıda anlatılmış.
diyelim ki
1,3,8,6,5,7,3,1,6,9,6 geliyor
Optimala Göre 3 sayfalık bir frame:
1
1|3|
1|3|8
1|3|6
1|3|5
1|3|7
1|3|7
son 3 e kaldığımızda ise hafızada 6,9,6 kalıyor..
ve sayfalarımızdaki 1, 3, 7 hafızada yok..Burda ne yapcaz?
bahsettiğiniz durumdan sonrası hiç önemli değil. Sonuçta 6,9,6 sayfaları talep edilecek ve hiçbirisi önbellekte (Cache) bulunmuyor. dolayısıyla sayfa ihlali oluaşacak (page fault) ve rast gele birisinin yerine yazılacak. Örneğimizi ilerletelim:
1|3|6 << burada 7 yerine 6 geldi ama herhangi başka birisi yerine de gelebilirdi. Optimal replacement için bundan sonra gelecekler önemlidir. Önbellekte bulunan 1,3 ve 7 sayfalarından hiçbirisi ileride gelmeyeceği için herhangi birisi değiştirilebilir. Ancak bu noktadan sonra yani 1|3|6 durumundayken aynı şeyi söyleyemeyiz. Yani 9. sayfa talebinde 6 ile değiştirme işlemi yapılamaz. Çünkü 6. sayfa ileride talep edilecektir. Yine 1 ve 3 sayfalarından birisini rast gele seçerek yerine 9 yerleştiriyoruz: 1|9|6 << bu şekildeyken çalışma bitiriliyor. başarılar
Teşekkürler hocam.Yani sondakilerden rastgele gelmesi sonucu etkilemiyor.Mesela son örnekte de olduğu gibi son 1 tane kaldı mı istediğimiz sayı ile değiştirebiliyoruz değil mi ? ( mesela son yorumdaki 1 3 9 ‘da 6 >> 6 3 9 , 1 6 9 ya da 1 3 6 olabilirdi..)
ewet optimal replacement için sizin de söylediğiniz gibi istediğinizle değiştirebilirsiniz. Optimal replacement algoritmasında amaç (ki bu hayali bir algoritmadır ve gerçekte uygulaması mümkün değildir) en az replacement gerektirecek olanı değiştirmektir. Son kalan page için böyle birşeyden bahsedilemeyeceği için sizin de söylediğiniz üzere son sayfada ihlal oluştuğunda (page fault) herhangi birisi ile değiştirilebilir.
başarılar
guzel siteymiş.en eski erişilen demek fifo manasına gelmiyor mu.zaten ilk gelen en eski olur..bu nedenle sizce lru için yazdiginiz yukarıdaki en eski erişilen ile bir başka satırda yazdıginiz en az(nadir) erişilen de çelişki olmuyormu.tam açıklık getırebilir misiniz?
olay çok basit aslında, FIFO en eskiyi, LRU en nadir kullanılanı değiştirir. Yazıda karışıklığa sebep olabilecek kelimeleri kaldırıyorum.
başarılar
Hocam bu sizin anlattığınız LRU algoritmasında bi yanlışlık olduğu kanaatindeyim.http://cs.uttyler.edu/Faculty/Rainwater/COSC3355/Animations/lrupagereplacement.htm ve birçok kaynakta verilen linkteki gibi anlatılmış.Ayrıca morris mano bilgisayar sist. mimarisi kitabında da anlatılan sizin verdiğiniz örneğe ters düşüyor.Aslında sizin anlattıklarınızla verdiğiniz örnek arasında bi terslik var.Bu hatayı düzeltmenizi rica ediyorum.Saygılarımla..
daha öncede benzer yorumlar gelmiş ve yazıyı yeniden düzenlemiştim. Yorumunuzdan sonra okuyarak tekrar düzenliyorum. Yazıda LRU için sehven “en az” ibaresi kullanılmış ve bu durum yanlış anlamalara sebep oluyor. Bütün bu ibareleri “en eski” olarak düzeltiyorum. Örneği ise tekrar kontrol ettim ve doğru.
hassasiyetiniz için teşekkür ederim.
LRU algoritmasının örneği yanlış. en az kullanılana göre yapılmış. yani sayı olarak. ancak kullanımından sonra geçen süreye bakılarak yaplması gerekiyordu.
örneğin;
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 eski erişilen kaldırılır. Buna göre en son erişilen iki sayfa, 5. ve 6. adımlardaki 2. ve 3. sayfalardır. Dolayısıyla 1. sayfa, şu anda en eski erişilmiş olandır ve hafızadan kaldırılır.
|4|2|3|
7. sayfa talebinde yine hafızada o anda bulunmayan 5 numaralı sayfa talep edilmiştir. Bu durumda 4 numaralı ve en eski erişilmiş olan sayfa yerine 5 numaralı sayfa yerleştirilir.
|5|2|3|
burada bir önceki aşamada 4 yeni gelmiş. yani daha yeni kullanıldı. ancak bir sonraki aşamadan 5 ile yer değiştirmiş. açııklama doğru ama örnek yanlış.
evet haklısınız yazıda hatayı düzeltiyorum, ilginiz için teşekkürler
Evvela bilgilendirici yazının için teşekkür ederim. Ancak least recently used algoritmasının son bölümünde bir “typo” olmuş gibi.
“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:
|4|5|1| ”
Açıklamanıza göre ve algoritmadki mantığa göre belleğin son görünümü
|1|5|3| şeklinde olması gerekmez mi?
Haklısınız yazıda ilgili düzeltmeyi yapıyorum. Teşekkürler
Merhaba,
İspanya’da erasmustayım akfayı yemiştim derse,iki dakika okudum,bu kadarmış dedim. Ağzına sağlık 🙂
Merhabalar.Hocamız sınavda bu tür bir soruda sürpriz yapabileceğini söyledi.Sizin örnekler de derste anlatınlan gibi sürpriz içermeyen sadece konu anlatımına yöeilk..Fsrklı tarzda soru var mı siz de?sürpriz nasıl yapılabilir.Teşekkürler şimdiden..
Bakın bence bir üniversitenin kalitesini o üniversitedeki kişiler belirler (hoca öğrenci asistan vs. ) kaliteli üniversitelerin hemen hepsinde yapılan sınav sorularını internette yayınlamak gibi bir adet var. Çoğu çözümleri ile birlikte yayınlanır. Size tavsiyem internette MIT, CM, Stanford gibi üniversitelerde benzer dersleri arayıp çıkmış sınav sorularını çözmeniz.
Başarılar
Hocam burda genelde ilk başta hafıza boşken başlanmış..Dolu olursa nasıl yapacaz?farklı soru yok mu:S
bir de lru-k algoritması var. modern sistemlerde lru-k kullanılıyor. bundan da bahsedilirse daha iyi olur.
Hocam çok teşekkürler gayet güzel anlatım