Dosya Sistemi Soyutlaması

Önceki üç ders belleği ölçtü ve üçünde de veri koşum bitince yok oldu. Bir sanal sayfa atıldığında içeriği geri getirilebilirdi, ama süreç sonlandığında adres uzayı tümüyle kayboluyordu. Üretilen verinin çoğu ise koşumdan uzun yaşamak zorundadır ve bunun için ikinci bir soyutlama gerekir: baytların adlandırıldığı, adların bir hiyerarşiye yerleştirildiği ve içeriğin sabit boyutlu bloklara bölündüğü bir düzen.

Bu ders o düzeni modeller ve iki bedelini sayar. Dosya oluşturma, izin verme ve dizinde gezinme komutları bu katalogda çoktan kullanıldı; burada hiçbir komut öğretilmez. Ölçülen şey mekanizmadır — bir baytın bloğa, bir adın numaraya çevrilmesi kaç adıma mal oluyor.

Üç Ayrı Nesne

Soyutlama üç nesneyi birbirinden ayırır ve ayrımın kendisi bir tasarım kararıdır.

Dosya, sıralı bir bayt dizisidir ve tek başına adı yoktur. Dosya düğümü (inode), bir dosyanın adı dışındaki her şeyini taşır: boyutu, izinleri, zaman damgalarını ve içeriğin hangi bloklarda durduğunu veren blok listesini. Dizin, kendisi de bir dosyadır; içeriği ad ile dosya düğümü numarasını eşleyen bir tablodur.

Adın dosyada değil dizinde durması, iki sonuç doğurur. Aynı dosya düğümüne birden çok dizin girdisi işaret edebilir, yani bir dosyanın birden çok adı olabilir. Ve bir adı silmek dosyayı silmek değildir — dosya, kendisine işaret eden son girdi de kalktığında ortadan kalkar.

• BD19 — Altı dosya ortak tanımdan gelir: 120, 700, 1500, 40, 2048 ve 333 bayt, toplam 4741 bayt. Varsayılan blok boyu 512 bayttır.
• BD20 — Bir dosya düğümü 8 doğrudan blok numarası taşır. Daha fazla bloğa ihtiyaç duyan dosya, numaraları bir dolaylı blokta tutar; bir blok numarası 4 bayttır, yani bir dolaylı blok blok / 4 tane numara taşır.
• BD21 — Dolaylı blok tek düzeylidir. Bu modeldeki dosyaların hiçbiri tek düzeyin kapasitesini aşmıyor.
• BD22 — Okuma adımı blok başına birdir; dolaylı bloktaki bir numaraya bakmak bir okuma daha ekler. Diskin kendi gecikmesi bu derste sayılmaz.

"""M01/K05 ortak tanim (kesit): dosya dugumu , blok ve ic parcalanma."""
BLOK = 512
DOSYA = [120, 700, 1500, 40, 2048, 333]
DOGRUDAN = 8          # dosya dugumunun tasidigi dogrudan blok numarasi
NUMARA = 4            # bir blok numarasi kac bayt


def dosya_dugumu(boyutlar, blok=BLOK):
    kullanilan = sum(-(-b // blok) for b in boyutlar)
    return {"dosya": len(boyutlar), "bayt": sum(boyutlar), "blok": kullanilan,
            "ic_parcalanma": kullanilan * blok - sum(boyutlar)}


def dolayli(boyutlar, blok):
    """Dogrudan numaralara sigmayan bloklar icin gereken dolayli blok ve okuma adimi."""
    ek, okuma = 0, 0
    for b in boyutlar:
        veri = -(-b // blok)
        okuma += veri
        if veri > DOGRUDAN:
            ek += -(-(veri - DOGRUDAN) // (blok // NUMARA))
            okuma += veri - DOGRUDAN          # her dolayli numara bir okuma daha
    return ek, okuma


print("ortak tanim:", dosya_dugumu(DOSYA))
print()
print("blok  veri blogu  dolayli  toplam blok  disk bayti  ic parcalanma  okuma adimi")
for blok in (64, 128, 256, 512, 1024, 4096):
    d = dosya_dugumu(DOSYA, blok)
    ek, okuma = dolayli(DOSYA, blok)
    toplam = d["blok"] + ek
    print(f"{blok:4d}  {d['blok']:10d}  {ek:7d}  {toplam:11d}  {toplam * blok:10d}"
          f"  {d['ic_parcalanma']:13d}  {okuma:11d}")

ortak tanim: {'dosya': 6, 'bayt': 4741, 'blok': 12, 'ic_parcalanma': 1403}

blok  veri blogu  dolayli  toplam blok  disk bayti  ic parcalanma  okuma adimi
  64          76        4           80        5120            123          119
 128          39        2           41        5248            251           51
 256          21        0           21        5376            635           21
 512          12        0           12        6144           1403           12
1024           8        0            8        8192           3451            8
4096           6        0            6       24576          19835            6

Üç sayı yan yana. Taban: altı dosyanın içeriği 4741 bayttır ve bitişik yazılsaydı diskte 4741 bayt tutardı; dosya düğümü tek bir başlangıç adresi ile uzunluk taşırdı. Kurulum: 512 baytlık bloklar, 12 blok, diskte 6144 bayt. Bedel: 1403 bayt iç parçalanma — diske yazılanın yüzde 22,8’i hiçbir veri taşımıyor — ve dosya düğümünde tek bir çift yerine 12 blok numarası.

Bitişik yerleşimin neden terk edildiği önceki dersten okunur. Bir dosyanın büyümesi, ardındaki baytların boş olmasını gerektirir; olmadığında dosyanın tamamı taşınmalıdır. Blok listesi bu zorunluluğu kaldırır: yeni blok diskte nereye düşerse düşsün listeye eklenir. Yani iç parçalanma, dış parçalanmadan kaçmak için ödenen bedeldir.

Blok Küçüldükçe Ne Oluyor

Tablo blok boyunu süpürüyor ve iki sütun ters yönde hareket ediyor.

İç parçalanma blokla birlikte küçülüyor: 4096 baytlık blokta 19.835 bayt, 512’de 1403, 64’te yalnız 123 bayt. Sebebi doğrudan — her dosyanın son bloğunda ortalama yarım blok boşa gider ve altı dosya için bu, blok boyunun yaklaşık üç katıdır. Blok küçüldükçe boşa giden pay da küçülür.

Okuma adımı ise ters yönde gidiyor: 4096 baytlık blokta 6 okuma, 512’de 12, 64’te 119 okuma. Aynı 4741 baytı okumak için yirmi kat daha çok istek yapılıyor. Buna dolaylı blok da ekleniyor: 128 bayt ve altında bazı dosyalar sekiz doğrudan numaraya sığmıyor ve blok listesinin bir bölümü ayrı bir bloğa taşınıyor. O bloktaki her numaraya bakmak fazladan bir okumadır, tabloda okuma sütununun 39 veri bloğu için 51’e çıkması bundandır.

Diskte tutulan toplam bayt da düz gitmiyor. 64 baytlık blokta dolaylı bloklarla birlikte 5120 bayt, 512’de 6144 bayt, 4096’da 24.576 bayt. En küçük blok yeri en verimli kullanıyor ve en pahalı okumayı yaptırıyor. Blok boyu seçimi bir doğruluk kararı değil, bir bütçe kararıdır ve bütçenin iki kalemi ters yönde hareket eder.

Adı Numaraya Çevirmek

Bir programın kullandığı ad bir yoldur; dosya sisteminin kullandığı şey bir dosya düğümü numarasıdır. İkisi arasındaki çeviri, yolun her bileşeninde bir dizin okumasıdır.

• BD23 — Altı dosya üç dizine dağıtılmıştır; adlar ölçüm ve günlük verisini temsil eder ve boyutları yukarıdaki listeyle aynıdır.
• BD24 — Bir dizini okumak bir adımdır; dizinin kaç girdi taşıdığı adım sayısını değiştirmez.

"""Dizin cozumlemesi: bir ad kac okumaya cevriliyor."""
AGAC = {                                   # dizin -> ad: (tur , dosya dugumu no)
    "/":           {"olcum": ("D", 1), "gunluk": ("D", 2)},
    "/olcum":      {"ham.veri": ("F", 10), "ozet.veri": ("F", 11), "eski": ("D", 3)},
    "/olcum/eski": {"gecmis.veri": ("F", 12)},
    "/gunluk":     {"gun.kaydi": ("F", 13), "hafta.kaydi": ("F", 14),
                    "ay.kaydi": ("F", 15)},
}
YOL = ["/olcum/ham.veri", "/olcum/ozet.veri", "/olcum/eski/gecmis.veri",
       "/gunluk/gun.kaydi", "/gunluk/hafta.kaydi", "/gunluk/ay.kaydi"]


def coz(yol):
    """Doner: dosya dugumu numarasi , okuma adimi.
    Her yol bileseninde bir dizin , sonda bir dosya dugumu okunur."""
    simdi, adim, no = "/", 0, None
    for parca in yol.strip("/").split("/"):
        adim += 1                          # bileseni tasiyan dizin okunur
        tur, no = AGAC[simdi][parca]
        if tur == "D":
            simdi = ("" if simdi == "/" else simdi) + "/" + parca
    return no, adim + 1                    # sonda dosya dugumu okunur


toplam = 0
for y in YOL:
    no, adim = coz(y)
    toplam += adim
    print(f"{y:26s} dosya dugumu {no:3d}  cozumleme adimi {adim}")
print("alti dosya icin toplam cozumleme adimi:", toplam)
print()
ERISIM = 20
y = "/olcum/eski/gecmis.veri"
_, adim = coz(y)
print(f"{y} , {ERISIM} erisim")
print("  her erisimde yeniden cozumleme:", ERISIM * adim, "adim")
print("  bir kez cozup tanitici uzerinden:", adim + ERISIM, "adim")

/olcum/ham.veri            dosya dugumu  10  cozumleme adimi 3
/olcum/ozet.veri           dosya dugumu  11  cozumleme adimi 3
/olcum/eski/gecmis.veri    dosya dugumu  12  cozumleme adimi 4
/gunluk/gun.kaydi          dosya dugumu  13  cozumleme adimi 3
/gunluk/hafta.kaydi        dosya dugumu  14  cozumleme adimi 3
/gunluk/ay.kaydi           dosya dugumu  15  cozumleme adimi 3
alti dosya icin toplam cozumleme adimi: 19

/olcum/eski/gecmis.veri , 20 erisim
  her erisimde yeniden cozumleme: 80 adim
  bir kez cozup tanitici uzerinden: 24 adim

Çözümleme adımı yolun derinliğiyle doğrusal büyüyor: iki bileşenli bir yol 3 adım, üç bileşenli bir yol 4 adım. Altı dosyanın tamamı için 19 adım harcanıyor ve bunların hiçbiri veri okumaz — hepsi ad aramasıdır.

Son iki satır, dosya tanıtıcısının (file descriptor) neyi satın aldığını gösteriyor. Aynı dosyaya 20 erişim, her seferinde yol çözülerek yapılırsa 80 adım tutuyor; yol bir kez çözülüp sonuçta elde edilen tanıtıcı üzerinden erişilirse 24 adım. Tanıtıcı, çözümlemenin sonucunu saklayan bir kısayoldur ve maliyeti bir kez ödetir. Bedeli de vardır: tanıtıcı bir adı değil bir dosya düğümünü tutar, bu yüzden dosya arada yeniden adlandırılsa ya da adı silinse bile aynı içeriği okumaya devam eder.

Tek Güncelleme, Üç Yazma

Bir dosyaya blok eklemek tek bir yazma değildir. Veri bloğunun kendisi yazılır, bloğun artık dolu olduğu blok eşleminde işaretlenir ve dosya düğümündeki boyut ile blok listesi güncellenir. Üç yazma arasında makine durursa diskte hangi durum kalır sorusu, dosya sisteminin en pahalı sorusudur.

• BD25 — Bir güncelleme üç yazma taşır ve çökme herhangi iki yazmanın arasında olabilir. Yazma sırası gerçekleştirime bağlı olduğundan altı sıralamanın hepsi sayılır.
• BD26 — Değişmez şudur: dosya düğümü bir bloğu gösteriyorsa o blok eşlemde dolu işaretlenmiş ve verisi yazılmış olmalıdır. Eşlemde dolu görünüp hiçbir dosya düğümünün göstermediği blok kayıp bloktur — tutarsız değildir, geri alınamaz alandır.

"""Cokme tutarliligi: gunluksuz ve gunluklu duzen , butun cokme noktalari."""
from itertools import permutations

YAZMA = ("veri", "eslem", "dugum")        # veri blogu , blok eslemi , dosya dugumu


def denetle(diskteki):
    """Degismez: dosya dugumu blogu gosteriyorsa eslem dolu ve veri yazilmis olmali."""
    tutarli = ("dugum" not in diskteki) or {"eslem", "veri"} <= diskteki
    kayip = "eslem" in diskteki and "dugum" not in diskteki
    return tutarli, kayip


durum = tutarsiz = kayipli = 0
for sira in permutations(YAZMA):
    for k in range(len(YAZMA) + 1):
        t, kayip = denetle(set(sira[:k]))
        durum += 1
        tutarsiz += not t
        kayipli += kayip
print("gunluksuz: yazma", len(YAZMA), "| sira x cokme noktasi", durum,
      "| tutarsiz", tutarsiz, "| kayip blok", kayipli)

# Gunluklu duzen: once gunluge , sonra kesinlestirme kaydi , en son yerine.
ADIM = [("gunluge", a) for a in YAZMA] + [("kesinlestirme", None)] \
       + [("yerine", a) for a in YAZMA]
durum = tutarsiz = 0
for k in range(len(ADIM) + 1):
    kesin = ("kesinlestirme", None) in ADIM[:k]
    # kurtarma: kesinlestirme yoksa gunluk atilir (eski durum) , varsa yeniden oynatilir
    diskteki = set(YAZMA) if kesin else set()
    t, _ = denetle(diskteki)
    durum += 1
    tutarsiz += not t
print("gunluklu:  yazma", len(ADIM), "| cokme noktasi", durum,
      "| tutarsiz", tutarsiz, "| yazma carpani", round(len(ADIM) / len(YAZMA), 2))

gunluksuz: yazma 3 | sira x cokme noktasi 24 | tutarsiz 6 | kayip blok 4
gunluklu:  yazma 7 | cokme noktasi 8 | tutarsiz 0 | yazma carpani 2.33

Altı sıralama ile dört çökme noktası 24 olası son durum veriyor. Bunların 6’sı tutarsız: dosya düğümü bir bloğu gösteriyor ama blok ya eşlemde boş görünüyor ya da içine hiçbir şey yazılmamış. Dördünde ise kayıp blok var — alan ayrılmış, kimse göstermiyor, geri de alınamıyor. Yalnız 14 durumda disk sağlam.

Günlüklü dosya sistemi (journaling file system) bu sayıyı sıfıra indirir. Üç yazma önce ayrı bir günlük alanına yazılır, ardından tek bir kesinleştirme kaydı düşülür ve ancak ondan sonra veriler yerine uygulanır. Kurtarma tek kurala bakar: kesinleştirme kaydı yoksa günlük atılır ve disk eski hâlinde kalır; varsa günlükteki yazmalar yeniden uygulanır ve disk yeni hâline geçer. Sekiz çökme noktasının hepsi bu iki tutarlı durumdan birine düşüyor.

Bedeli tabloda yazıyor: 3 yazma yerine 7 yazma, yani 2,33 kat. Her bayt diske iki kez gidiyor. Bunun bir bölümü geri kazanılabilir — yalnız dosya düğümü ve eşlem gibi yapıların günlüğe alınıp veri bloklarının doğrudan yazıldığı bir kurulum çarpanı düşürür, karşılığında veri kaybı olasılığını geri getirir. Diskin sağlam kalması ile yazma miktarı arasındaki bu ödünleşim kaldırılamaz; yalnız nereye konulacağı seçilir.

Günlüğün kaldırdığı şeyin ne olmadığına da dikkat etmek gerekir. Günlük, çökme anında diskteki yapıların birbiriyle uyumlu kalmasını sağlar; yazılmakta olan verinin kaybolmasını engellemez. Kesinleştirme kaydından önce çöken bir güncelleme, kurtarmadan sonra hiç yapılmamış gibi görünür ve bu, tanım gereği doğru sonuçtur. Bir programın “yazdım” demesi ile verinin diskte olması arasındaki fark, bu dersin modelinin dışında kalan ama aynı yerden doğan bir konudur: yazma isteği kabul edildiğinde bayt henüz diskte olmayabilir.

Özet

• Dosya sıralı bir bayt dizisidir, dosya düğümü onun adı dışındaki her şeyini ve blok listesini taşır, dizin ise adı dosya düğümü numarasına eşleyen bir tablodur; ad dosyanın değil dizinin özelliğidir.
• Altı dosyanın 4741 baytı 512 baytlık 12 bloğa yerleşiyor ve diskte 6144 bayt tutuyor; 1403 bayt, yani yazılanın yüzde 22,8’i iç parçalanmadır.
• Blok boyu süpürüldüğünde iki maliyet ters yönde hareket ediyor: 64 baytlık blokta iç parçalanma 123 bayta iniyor ama okuma adımı 119’a çıkıyor; 4096 baytlık blokta okuma 6 adıma iniyor ama iç parçalanma 19.835 bayta çıkıyor.
• Dosya düğümü sekiz doğrudan numara taşıyor; blok küçüldükçe bazı dosyalar bu sınırı aşıyor ve blok listesi dolaylı bloğa taşınıyor, bu da her erişime bir okuma daha ekliyor.
• Bir yol adını dosya düğümü numarasına çevirmek yolun her bileşeninde bir dizin okumasıdır; aynı dosyaya 20 erişim, her seferinde çözümlenirse 80 adım, bir kez çözülüp tanıtıcı üzerinden yapılırsa 24 adım tutuyor.
• Tek bir blok eklemesi üç yazma taşır; altı sıralama ile dört çökme noktasının verdiği 24 durumun 6’sı tutarsız, 4’ünde kayıp blok vardır. Günlüklü düzen bu sayıyı sıfıra indirir ve karşılığında yazma sayısını 3’ten 7’ye, yani 2,33 katına çıkarır.

Sonraki Adım

Bu ders bir bloğu okumanın bir adım olduğunu varsaydı ve o adımın ne kadar sürdüğünü hiç sormadı. Oysa bir disk isteği, işlemcinin bir hesap adımının otuz katı sürer ve bu süre boyunca işlemci ya bekler, ya sorar, ya da başka bir iş yapar. Kursun son dersi bu üç seçeneği aynı iş yükünde sayar ve şaşırtıcı bir sonuçla biter: işlemciyi yüzde yüz dolduran model, işini hiç de daha erken bitirmiyor.