Операционные системы

На ноутбуке одновременно работают браузер, музыка, мессенджер и антивирус, хотя ядер у процессора всего несколько, а память ограничена. Каждая программа «думает», что весь компьютер принадлежит ей, — эту иллюзию создаёт операционная система (ОС). ОС делит процессорное время, выдаёт каждой программе собственную память, организует файлы на диске и не даёт программам заблокировать друг друга.

Процессы, потоки и планирование

Готовые процессы ждут в очереди, а планировщик решает, кому достанется процессор. FCFS — в порядке поступления; SJF — сначала самая короткая задача (минимизирует среднее время ожидания, но требует заранее знать длину задач); Round Robin — каждый процесс получает квант времени q, а затем уходит в конец очереди. Каждое переключение требует смены контекста: сохранения и восстановления регистров.

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

Виртуальная память и страничная организация

Каждый процесс видит собственное виртуальное адресное пространство, начинающееся с 0. Память делится на одинаковые страницы (например, 4 КБ), физическая RAM — на такие же кадры; таблица страниц каждого процесса хранит соответствие «страница → кадр». Перевод выполняет аппаратура (MMU), а недавние переводы держит в кэше TLB. Если страницы нет в RAM, происходит страничное прерывание (page fault), и ОС загружает её с диска — так программы могут использовать больше памяти, чем есть RAM, и не видят память друг друга.

Когда RAM заполнена, ОС должна выбрать, какую страницу вытеснить на диск. FIFO вытесняет страницу, загруженную раньше всех, LRU — ту, что дольше всех не использовалась. Теоретический идеал OPT вытесняет страницу, которая понадобится позже всех, но будущее неизвестно, поэтому он служит лишь эталоном.

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

Файловые системы

Диск делится на блоки фиксированного размера (обычно 4 КБ). В файловых системах Unix (ext4) индексный дескриптор (inode) каждого файла хранит размер, владельца, права, временные метки и указатели на блоки данных; каталог — это просто таблица «имя → номер inode». В классическом inode ext2/ext3 12 прямых указателей и одно-, двух- и трёхуровневые косвенные: при блоках 4 КБ и 4-байтовых указателях прямые блоки покрывают 48 КБ, одноуровневый косвенный — ещё 1024 · 4 КБ = 4 МБ, двухуровневый — 4 ГБ, трёхуровневый — 4 ТБ. Журналирование (ext4, NTFS) сначала записывает изменения в журнал, чтобы файловая система пережила отключение питания. В FAT32 один файл должен быть меньше 4 ГБ.

Взаимная блокировка (deadlock)

Поток A держит блокировку 1 и ждёт блокировку 2, а поток B держит 2 и ждёт 1 — никто не может продвинуться. Взаимная блокировка возможна, когда одновременно выполняются четыре условия Коффмана: взаимное исключение (ресурсом пользуется один), удержание и ожидание, отсутствие вытеснения (ресурс не отбирают) и циклическое ожидание. Достаточно нарушить любое; самый практичный способ — всегда захватывать блокировки в одном глобальном порядке, что исключает циклическое ожидание.