Bölüm 8: Bellek Yönetimi

Bölüm 8: Bellek Yönetimi · Çalışma Soruları
ÖnbellekTaban ve limitBağlamaTakasYerleştirmeBiteşlemSayfalamaTLBSayfa tablosu yapılarıKesimleme
Sercan KÜLCÜ

Çoktan Seçmeli · Giriş

Soru 1: Bellek Yöneticisinin İşi Değil

Aşağıdakilerden hangisi işletim sisteminin bellek yönetimi bileşeninin görevlerinden biri değildir?

D: Sıradaki süreci seçmek CPU çizelgeleyicisinin işidir. Bellek yönetimi boş/dolu takibini, tahsis ve geri almayı, korumayı, yer değiştirmeyi ve takası kapsar.

Hesaplama · Bellek Donanımı

Soru 2: İki Düzeyli Önbellek

L1 önbellek 1 ns’de yanıt veriyor ve isabet oranı %90. L1 ıskasında L2’ye bakılıyor: L2 10 ns, L2’ye gelen isteklerin %80’i isabet. L2 ıskasında DRAM’e gidiliyor (100 ns). Düzeylere sırayla bakıldığına göre etkin erişim süresi nedir? L2 olmasaydı ne olurdu?

Cevabı göster

Her erişim L1’e uğrar; %10’u L2’ye, onların %20’si DRAM’e iner:

EAT = 1 + 0,10 × (10 + 0,20 × 100) = 1 + 0,10 × 30 = 4 ns.

L2 olmasaydı: 1 + 0,10 × 100 = 11 ns. Önbelleksiz her erişim 100 ns sürerdi; iki düzey ortalamayı 25 kat düşürür.

Ortalamaya ıskalar hâkimdir: L1 ıska oranını %10’dan %5’e indirmek EAT’i 1 + 0,05 × 30 = 2,5 ns’ye düşürür.

Adım Adım Çalıştırma · Bellek Donanımı

Soru 3: Doğrudan Eşlemeli Önbellek

Doğrudan eşlemeli önbellek kodu bu adres dizisiyle çalıştırılıyor (64 B satır, 4 küme, başta boş). Hangi erişimler isabet olur? Sonda isabet ve iska kaçtır?

küme 0—küme 1—küme 2—küme 3—

64 B satır, 4 küme, doğrudan eşleme: blok b yalnızca b mod 4 kümesine gidebilir.

adres 0 → blok 0 → küme 0küme 0blok 0ıskaküme 1—küme 2—küme 3—

Küme 0 boş → ıska, blok 0 yüklenir.

adres 40 → blok 0 → küme 0küme 0blok 0isabetküme 1—küme 2—küme 3—

Küme 0’da zaten blok 0 var → isabet. 40, 0 ile aynı 64 baytlık satırda: uzamsal yerellik.

adres 72 → blok 1 → küme 1küme 0blok 0küme 1blok 1ıskaküme 2—küme 3—

Küme 1 boş → ıska, blok 1 yüklenir.

adres 256 → blok 4 → küme 0küme 0blok 4ıskaküme 1blok 1küme 2—küme 3—

Küme 0 blok 0 tutuyor → ıska; blok 4 onu dışarı atar (çakışma ıskası).

adres 8 → blok 0 → küme 0küme 0blok 0ıskaküme 1blok 1küme 2—küme 3—

Küme 0 blok 4 tutuyor → ıska; blok 0 onu dışarı atar (çakışma ıskası).

adres 100 → blok 1 → küme 1küme 0blok 0küme 1blok 1isabetküme 2—küme 3—

Küme 1’de zaten blok 1 var → isabet. 100, 72 ile aynı satırda (64–127).

adres 130 → blok 2 → küme 2küme 0blok 0küme 1blok 1küme 2blok 2ıskaküme 3—

Küme 2 boş → ıska, blok 2 yüklenir.

adres 264 → blok 4 → küme 0küme 0blok 4ıskaküme 1blok 1küme 2blok 2küme 3—

Küme 0 blok 0 tutuyor → ıska; blok 4 onu dışarı atar (çakışma ıskası).

küme 0blok 4küme 1blok 1küme 2blok 2küme 3—

Sonuç: 2 isabet, 6 ıska (%25). 0, 256 ve 264 aynı kümeye düştüğü için birbirini kovdu; 2 yollu küme ilişkili önbellek bu ıskaların bir kısmını önlerdi.

int adres[8] = {0, 40, 72, 256, 8, 100, 130, 264};
int etiket[4] = {-1, -1, -1, -1};
int isabet = 0, iska = 0;
for (int i = 0; i < 8; i++) {
  int blok = adres[i] / 64;
  int kume = blok % 4;
  if (etiket[kume] == blok) isabet++;
  else { etiket[kume] = blok; iska++; }
}

Çıktı Sorusu · Adres Alanı

Soru 4: Taban ve Limit

Bir sürecin taban (yer değiştirme) yazmacı 30000, limit yazmacı 12000. MMU önce mantıksal adresi limitle karşılaştırıyor, sonra tabanı ekliyor. Süreç sırasıyla 0, 5000, 11999 ve 12000 mantıksal adreslerine erişiyor. Sonuçlar nedir?

mantıksal< limit?12000+ taban30000fizikselhayır → tuzak
Cevabı göster
Mantıksal< 12000?Sonuç
0evet30000
5000evet35000
11999evet41999
12000hayırtuzak

Geçerli mantıksal adresler 0 … limit − 1, yani 0–11999'dur; 12000 = limit olduğu için koruma hatası olur ve çekirdek devreye girer (Unix'te SIGSEGV). Karşılaştırma mantıksal adres üzerinden yapıldığından sonuç tabanın değerine bağlı değildir.

Çoktan Seçmeli · Adres Alanı

Soru 5: Bağlama Zamanı

İşletim sistemi çalışan bir süreci sıkıştırma ya da takas sonrasında bellekte başka bir yere taşıyabiliyor. Bunun mümkün olması için adres bağlama ne zaman yapılmalıdır?

C: Derleme ya da yükleme zamanında bağlanan adresler sabitlenir; süreç taşınınca geçersizleşir. Yürütme zamanı bağlamada her erişim o anki taban ya da sayfa tablosu değerleriyle çevrilir; taşımak için yalnızca yazmaç ya da tablo güncellenir.

Çoktan Seçmeli · Bağlama ve Yükleme

Soru 6: Tembel Bağlama

Dinamik bağlanan bir programda printf ilk kez çağrıldıktan sonra (tembel bağlama, ELF) bellekte ne değişir?

B: İlk çağrıda PLT, GOT'taki adresle çözücüye gider; ld.so sembolü bulup gerçek adresi GOT girdisine yazar. Kod sayfaları hiç değişmez, bu yüzden süreçler arasında paylaşılabilir kalır; sonraki çağrılar PLT → GOT → printf yolunu izler.

Çıktı Sorusu · Takas

Soru 7: Takas Süresi

200 MB'lık bir süreç standart takasla diske yazılıp sonra geri getiriliyor. Diskin aktarım hızı 50 MB/s, gecikmeler ihmal ediliyor. Gidiş-dönüş ne kadar sürer? Bekleyen G/Ç'si olan bir süreç neden takas edilmez?

Cevabı göster

Dışarı 200 / 50 = 4 s, içeri 4 s: toplam 8 s. Bu süre bütün süreci taşımanın bugün neden kabul edilmediğini gösterir; modern sistemler yalnızca soğuk sayfaları takas eder.

Süreç takas edilip yerine başka bir süreç yüklenirse, devam eden DMA aktarımı eski fiziksel adrese, yani artık başka sürecin belleğine yazar. Çare: böyle süreci takas etmemek ya da G/Ç'yi çekirdek tamponları üzerinden yapmak.

Takastan dönen süreç başka bir adrese yerleşebilir; bu da yürütme zamanı bağlama gerektirir.

Adım Adım Çalıştırma · Bitişik Tahsis

Soru 8: Yerleştirme Algoritmaları

Boş delikler adres sırasıyla 150, 400, 80, 250, 600 KiB. İstekler sırayla 230, 120, 380, 90 KiB. İlk uyan, en iyi uyan ve en kötü uyan her isteği nereye koyar? Hangisinde bir istek karşılanamaz?

İlk uyan15040080250600En iyi15040080250600En kötü15040080250600

Delikler adres sırasıyla 150, 400, 80, 250, 600 KiB. Turuncu: o adımda seçilen delik; kutularda kalan boy yazılı.

İlk uyan15017080250600En iyi1504008020600En kötü15040080250370

230 K: ilk uyan ilk yeterli delik olan 400'e, en iyi uyan yetenlerin (400, 250, 600) en küçüğü 250'ye (20 kalır), en kötü uyan 600'e koyar.

İlk uyan3017080250600En iyi304008020600En kötü15028080250370

120 K: ilk uyan ve en iyi uyan 150'ye (30 kalır). En kötü uyan o anki en büyük deliğe, 400'e koyar.

İlk uyan3017080250220En iyi30208020600En kötü15028080250370

380 K: ilk uyan 600'e, en iyi uyan 400'e (20 kalır). En kötü uyanda en büyük delik 370: yer yok, toplam boş alan yetse de.

İlk uyan308080250220En iyi30208020510En kötü15028080250280

90 K: ilk uyan 170'e (80 kalır), en iyi uyan yeten tek delik olan 600'e, en kötü uyan 370'e koyar. Yalnızca en kötü uyan bir isteği karşılayamadı.

for (her istek r) {
  ilk    = h >= r olan ilk delik;
  en_iyi = h >= r olanların en küçüğü;
  en_kotu = en büyük delik;
  if (seçilen h < r) yer yok;
  else seçilen deliği r kadar küçült;
}

Çoktan Seçmeli · Bitişik Tahsis

Soru 9: Karşılanamayan İstek

Değişken bölümlemeli bir sistemde boş delikler 6, 9 ve 4 KiB. Toplam boş alan 19 KiB olduğu hâlde 12 KiB'lık bir istek karşılanamıyor. Bu durumun adı ve doğrudan çaresi nedir?

B: Boş alan var ama bitişik değil: dış parçalanma. Sıkıştırma süreçleri bir uca kaydırıp delikleri tek bloğa toplar (yürütme zamanı bağlama gerekir); kalıcı çözüm bitişik olmayan tahsistir (sayfalama). Yerleştirme algoritmaları parçalanmayı yalnızca etkiler, var olan durumu düzeltmez.

Çıktı Sorusu · Boş Alan Yönetimi

Soru 10: Biteşlemde Arama

18 birimlik belleğin biteşlemi (birim 0'dan başlar, 1 = dolu) şekilde. İlk uyan ile 3 birimlik bir istek hangi birimden başlar? Ardından 4 birimlik bir istek nereye yerleşir? Sonra 5 birimlik istek karşılanabilir mi?

1010210401610800101112001400161
Cevabı göster

Sıfır dizileri: [2] (1 birim), [4–5] (2), [8–10] (3), [13–16] (4).

1010210401610800101112001400161
  • 3 birim: 2 ve 4–5 yetmez; ilk yeten dizi 8'den başlar (8–10 dolar).
  • 4 birim: kalan diziler [2], [4–5], [13–16]; yalnız 13 yeter.
  • 5 birim: kalan boş 3 birim, en uzun dizi 2 → karşılanamaz. Başlangıçta da 4'ten uzun dizi yoktu.

k birimlik yer aramak k ardışık sıfır aramaktır: biteşlemin zayıf yanı bu doğrusal taramadır.

Çoktan Seçmeli · Boş Alan Yönetimi

Soru 11: Biteşlem Boyutu

512 MiB'lık bellek 4 KiB'lık tahsis birimleriyle bir biteşlemde izleniyor. Biteşlem kaç bayt yer kaplar?

A: Birim sayısı 229 / 212 = 217; her birim 1 bit → 217 / 8 = 214 bayt = 16 KiB. C, bit sayısını (128 Ki) bayt sanır. Birim 1 KiB olsaydı biteşlem 4 kat büyür, birim başına iç parçalanma azalırdı.

Çoktan Seçmeli · Sayfalama

Soru 12: Ondalık Adres Çevirisi

Sayfa boyutu 2 KiB. Sayfa tablosunda 4. sayfa 7. çerçeveye eşlenmiş. Mantıksal adres 9000'in fiziksel karşılığı nedir?

C: p = ⌊9000 / 2048⌋ = 4, d = 9000 − 4 · 2048 = 808. Fiziksel = 7 · 2048 + 808 = 15144. B konumu unutur (yalnızca çerçeve başı); D tüm mantıksal adresi çerçeve başına ekler. Konum değişmez; yalnızca sayfa numarası çerçeve numarasıyla değiştirilir.

Çıktı Sorusu · Sayfalama

Soru 13: Onaltılık Adres Çevirisi

32 bitlik sanal adres, 4 KiB sayfa. Sayfa tablosunda girdi 0x3A: geçerli, çerçeve 0x1C2; girdi 0x3B: geçersiz. (a) Sayfa numarası ve konum kaçar bittir? (b) 0x0003A7F4 hangi fiziksel adrese çevrilir? (c) 0x0003B010'a erişilirse ne olur?

Cevabı göster

(a) 4 KiB = 212 → konum 12 bit, sayfa numarası 32 − 12 = 20 bit.

(b) Son 3 onaltılık hane konumdur: d = 0x7F4, p = 0x0003A. Fiziksel = çerçeve ‖ konum = 0x1C27F4.

(c) p = 0x3B, girdi geçersiz → donanım tuzak üretir (sayfa hatası). İşletim sistemi bunun geçersiz bir erişim mi yoksa henüz yüklenmemiş bir sayfa mı olduğuna karar verir.

Onaltılı yazımda her hane 4 bittir; sayfa boyutu 2'nin kuvveti olduğu için bölme ve kalan, bit kaydırma ve maskelemeye dönüşür.

Çoktan Seçmeli · Sayfalama

Soru 14: Sayfa Tablosu Boyutu

32 bit sanal adres, 8 KiB sayfa, sayfa tablosu girdisi 4 bayt. Tek düzeyli (doğrusal) sayfa tablosu her süreç için ne kadar yer kaplar?

D: Sayfa sayısı 232 / 213 = 219 girdi; 219 × 4 B = 221 B = 2 MiB. C, 4 KiB sayfa için doğru olan değerdir. 100 süreçte 200 MiB eder; çok düzeyli tabloların nedeni budur.

Adım Adım Çalıştırma · TLB

Soru 15: TLB İsabet ve Iska

4 KiB sayfa, 3 girdilik LRU TLB. Sırayla 0x1A04, 0x0123, 0x1FFC, 0x2008, 0x4010, 0x0F00, 0x2ABC, 0x6000 adreslerine erişiliyor. Hangileri TLB isabetidir? Fiziksel adresler nedir?

TLB boş; 3 girdi, LRUTLB (eski → yeni):

Sayfa tablosu: 0→5, 1→9, 2→3, 3→7, 4→1, 6→4. TLB 3 girdilik ve başlangıçta boş; yer gerekince en uzun süredir kullanılmayan çıkar.

0x1A04 → p = 1, d = 0xA04ıska → 0x9A04TLB (eski → yeni):1 → 9

0x1A04: sayfa 1 TLB'de yok → ıska; tablodan çerçeve 9 okunur.

0x0123 → p = 0, d = 0x123ıska → 0x5123TLB (eski → yeni):1 → 90 → 5

0x0123: sayfa 0 TLB'de yok → ıska; tablodan çerçeve 5 okunur.

0x1FFC → p = 1, d = 0xFFCisabet → 0x9FFCTLB (eski → yeni):0 → 51 → 9

0x1FFC: sayfa 1 TLB'de → isabet, sayfa tablosuna gidilmez.

0x2008 → p = 2, d = 0x008ıska → 0x3008TLB (eski → yeni):0 → 51 → 92 → 3

0x2008: sayfa 2 TLB'de yok → ıska; tablodan çerçeve 3 okunur.

0x4010 → p = 4, d = 0x010ıska (sayfa 0 çıkarıldı) → 0x1010TLB (eski → yeni):1 → 92 → 34 → 1

0x4010: sayfa 4 TLB'de yok → ıska; tablodan çerçeve 1 okunur; TLB dolu olduğu için sayfa 0 çıkarılır.

0x0F00 → p = 0, d = 0xF00ıska (sayfa 1 çıkarıldı) → 0x5F00TLB (eski → yeni):2 → 34 → 10 → 5

0x0F00: sayfa 0 TLB'de yok → ıska; tablodan çerçeve 5 okunur; TLB dolu olduğu için sayfa 1 çıkarılır.

0x2ABC → p = 2, d = 0xABCisabet → 0x3ABCTLB (eski → yeni):4 → 10 → 52 → 3

0x2ABC: sayfa 2 TLB'de → isabet, sayfa tablosuna gidilmez.

0x6000 → p = 6, d = 0x000ıska (sayfa 4 çıkarıldı) → 0x4000TLB (eski → yeni):0 → 52 → 36 → 4

0x6000: sayfa 6 TLB'de yok → ıska; tablodan çerçeve 4 okunur; TLB dolu olduğu için sayfa 4 çıkarılır. Toplam 2 isabet / 8 erişim.

p = adres / 4096;  d = adres % 4096;
if (p TLB'de) {          /* isabet */
  f = TLB[p];  p'yi en yeni yap;
} else {                 /* ıska */
  f = sayfa_tablosu[p];
  if (TLB dolu) en eski girdiyi çıkar;
  TLB'ye (p, f) ekle;
}
fiziksel = f * 4096 + d;

Çıktı Sorusu · TLB

Soru 16: Etkin Erişim Süresi

Bellek erişimi 80 ns, TLB araması 10 ns, tek düzeyli sayfa tablosu, TLB isabet oranı %95. (a) Etkin erişim süresi nedir? (b) Bu sürenin 92 ns'ye inmesi için isabet oranı en az kaç olmalıdır? (c) Tablo dört düzeyli olsaydı ıska ne kadar sürerdi?

Cevabı göster

İsabet: 10 + 80 = 90 ns. Iska: 10 + 80 (tablo) + 80 (veri) = 170 ns.

(a) EES = 0,95 · 90 + 0,05 · 170 = 85,5 + 8,5 = 94 ns.

(b) 90α + 170(1 − α) ≤ 92 → 170 − 80α ≤ 92 → α ≥ 0,975: en az %97,5.

(c) Iskada 4 tablo erişimi + veri: 10 + 4 · 80 + 80 = 410 ns. Çok düzeyli tabloda ıska çok pahalıdır; bu yüzden donanım ara düzeyleri de önbelleğe alır ve isabet oranı daha da önemlidir.

Çıktı Sorusu · Sayfa Tablosu Yapıları

Soru 17: İki Düzeyli Sayfalama

32 bit adres, 4 KiB sayfa, iki düzeyli tablo: 10 bit üst indis (PT1), 10 bit alt indis (PT2), 12 bit konum; her tablo 1024 girdi × 4 B = 4 KiB. (a) 0x01402A9F için PT1, PT2 ve konum nedir? (b) Bir süreç adres alanının en altındaki 12 MiB'ı ve en üstteki 4 MiB'ı kullanıyor. Kaç sayfa tablosu gerekir, toplam kaç KiB?

Cevabı göster 0000000101PT1 = 50000000010PT2 = 2101010011111konum = 0xA9F

(a) 0x01402A9F = 0000 0001 0100 0000 0010 1010 1001 1111 → PT1 = 5, PT2 = 2, konum = 0xA9F.

(b) Her alt tablo 1024 × 4 KiB = 4 MiB kapsar: alttaki 12 MiB için 3, üstteki 4 MiB için 1 alt tablo, artı 1 üst tablo = 5 tablo = 20 KiB. Doğrusal tablo 4 MiB olurdu.

Kullanılmayan bölgelerin alt tabloları hiç oluşturulmaz. Bedeli: TLB ıskasında 2 tablo erişimi + 1 veri erişimi.

Çoktan Seçmeli · Sayfa Tablosu Yapıları

Soru 18: Ters Sayfa Tablosu

Ters (inverted) sayfa tablosu için hangisi doğrudur?

A: Tablo sistemde tektir ve boyu fiziksel bellekle orantılıdır, süreç sayısından bağımsızdır; girdinin indisi çerçeve numarasıdır. Bedeli: arama için hash tablosu gerekir ve bir çerçeve tek sanal sayfa tuttuğu için paylaşımlı bellek zorlaşır. B doğrusal (süreç başına) tablodur.

Çıktı Sorusu · Kesimleme

Soru 19: Kesim Tablosu

Kesim tablosu (taban, limit): 0 → (1400, 600), 1 → (6300, 300), 2 → (4100, 1000), 3 → (3200, 500). Mantıksal adresler (kesim, konum) biçiminde: (0, 430), (1, 310), (2, 999), (3, 500). Fiziksel adresleri bulun.

Cevabı göster
AdresKonum < limit?Sonuç
(0, 430)430 < 6001400 + 430 = 1830
(1, 310)310 ≥ 300tuzak
(2, 999)999 < 10004100 + 999 = 5099
(3, 500)500 ≥ 500tuzak

Kesimleme, her kesim için ayrı bir taban-limit çiftidir. Geçerli konumlar 0 … limit − 1'dir; konum = limit de tuzaktır. Denetim olmasaydı (1, 310) adresi 6610'a, yani kesimin dışına erişirdi.

Çoktan Seçmeli · Gerçek Mimariler

Soru 20: x86-64'te Kesimleme

x86-64 uzun modunda kesimlemeden fiilen ne kalmıştır?

B: Uzun modda CS, DS, ES, SS tabanı donanımca 0 sayılır ve limit denetlenmez: adres alanı düzdür, koruma sayfa tablosu bitleriyle yapılır. Yalnızca FS ve GS tabanı kullanılır: kullanıcı alanında iş parçacığına yerel depolama (TLS), çekirdekte çekirdek başına veri. CS ise ayrıcalık düzeyini taşır.

Son

Bölüm 8: Bellek Yönetimi: Çalışma Soruları
Konu anlatımı: Bellek yönetimi sunumu · Terim sözlüğü
1 / 1 Sercan KÜLCÜ, Tüm hakları saklıdır.