Əməliyyat sistemləri

Noutbukunda eyni anda brauzer, musiqi, mesencer və antivirus işləyir, amma prosessorun nüvələri cəmi bir neçədir, yaddaş da məhduddur. Hər proqram «bütün kompüter mənimdir» deyə düşünür — bu illüziyanı əməliyyat sistemi (ƏS) yaradır. ƏS prosessor vaxtını bölüşdürür, hər proqrama ayrıca yaddaş verir, faylları diskdə təşkil edir və proqramların bir-birini «kilidləməsinin» qarşısını alır.

Proseslər, axınlar və planlaşdırma

Hazır proseslər növbədə gözləyir və planlayıcı hansının prosessoru alacağına qərar verir. FCFS — gəlmə sırası ilə; SJF — ən qısa iş əvvəl (orta gözləmə vaxtını minimallaşdırır, amma işin uzunluğunu əvvəlcədən bilmək lazımdır); Round Robin — hər prosesə q kvant vaxt verilir, sonra o, növbənin sonuna keçir. Hər keçid kontekst dəyişməsi tələb edir: registrlərin saxlanması və bərpası.

from collections import deque

def fcfs(bursts):
    t, waits = 0, []
    for b in bursts:
        waits.append(t)
        t += b
    return waits

def round_robin(bursts, q):
    rem, t, done = list(bursts), 0, [0] * len(bursts)
    queue = deque(range(len(bursts)))
    while queue:
        i = queue.popleft()
        run = min(q, rem[i])
        t += run
        rem[i] -= run
        if rem[i]:
            queue.append(i)
        else:
            done[i] = t
    return [done[i] - bursts[i] for i in range(len(bursts))]

jobs = [10, 4, 2]
for name, w in [('FCFS', fcfs(jobs)), ('SJF', fcfs(sorted(jobs))), ('RR q=3', round_robin(jobs, 3))]:
    print(name, w, 'average wait:', round(sum(w) / len(w), 2))

FCFS [0, 10, 14] average wait: 8.0
SJF [0, 2, 6] average wait: 2.67
RR q=3 [6, 8, 6] average wait: 6.67

Virtual yaddaş və səhifələmə

Hər proses 0-dan başlayan öz virtual ünvan fəzasını görür. Yaddaş eyni ölçülü səhifələrə (məsələn, 4 KB), fiziki RAM isə eyni ölçülü çərçivələrə bölünür; hər prosesin səhifələr cədvəli «səhifə → çərçivə» uyğunluğunu saxlayır. Çevirməni aparat (MMU) edir, son çevirmələri isə TLB keşində saxlayır. Səhifə RAM-da deyilsə, səhifə xətası baş verir və ƏS onu diskdən yükləyir — beləliklə, proqramlar fiziki RAM-dan çox yaddaş istifadə edə bilir və bir-birinin yaddaşını görmür.

RAM dolanda ƏS hansı səhifəni diskə çıxaracağını seçməlidir. FIFO ən köhnə yüklənəni, LRU ən uzun müddət istifadə olunmayanı çıxarır. Nəzəri ideal OPT gələcəkdə ən gec lazım olacaq səhifəni çıxarır, amma gələcəyi bilmək mümkün deyil, ona görə o, yalnız müqayisə üçün işlədilir.

def faults(refs, frames, policy):
    mem, count = [], 0
    for p in refs:
        if p in mem:
            if policy == 'LRU':
                mem.remove(p)
                mem.append(p)
            continue
        count += 1
        if len(mem) == frames:
            mem.pop(0)
        mem.append(p)
    return count

refs = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
for frames in [3, 4]:
    print(frames, 'frames: FIFO', faults(refs, frames, 'FIFO'), '| LRU', faults(refs, frames, 'LRU'))

page_size, va = 4096, 0x3A7C
page, offset = divmod(va, page_size)
page_table = {3: 7}
pa = page_table[page] * page_size + offset
print('page', page, 'offset', offset, '-> physical', pa, hex(pa))

3 frames: FIFO 9 | LRU 10
4 frames: FIFO 10 | LRU 8
page 3 offset 2684 -> physical 31356 0x7a7c

Fayl sistemləri

Disk sabit ölçülü bloklara (adətən 4 KB) bölünür. Unix fayl sistemlərində (ext4) hər faylın inode-u ölçünü, sahibini, icazələri, vaxtları və məlumat bloklarına göstəriciləri saxlayır; kataloq isə sadəcə «ad → inode nömrəsi» cədvəlidir. Klassik ext2/ext3 inode-unda 12 birbaşa göstərici və bir, iki, üç pilləli dolayı göstəricilər var: 4 KB blok və 4 baytlıq göstəricidə birbaşa bloklar 48 KB, bir pilləli blok əlavə 1024 · 4 KB = 4 MB, iki pilləli 4 GB, üç pilləli 4 TB ünvanlayır. Jurnallama (ext4, NTFS) dəyişiklikləri əvvəlcə jurnala yazır ki, elektrik kəsiləndə fayl sistemi korlanmasın. FAT32-də isə bir faylın ölçüsü 4 GB-dan kiçik olmalıdır.

Qarşılıqlı bloklanma (deadlock)

A axını 1-ci kilidi tutub 2-ci kilidi gözləyir, B axını isə 2-cini tutub 1-cini gözləyir — heç biri irəli gedə bilmir. Koffmanın dörd şərti birlikdə ödənəndə deadlock mümkündür: qarşılıqlı istisna (resursu eyni anda bir nəfər işlədir), tutub gözləmə, zorla almamaq (resurs əlindən alınmır) və dairəvi gözləmə. Hər hansı birini pozmaq kifayətdir; ən praktik üsul — bütün kilidləri həmişə eyni qlobal sıra ilə tutmaq, bu, dairəvi gözləməni istisna edir.