Планирование процессов и взаимоблокировки

Состояния процесса, алгоритмы планирования FCFS, SJF, Round Robin и приоритетное, расчёт времени ожидания, условия взаимоблокировки и способы борьбы с ними.

Планировщик решает, какой процесс получит процессор следующим. От выбора алгоритма зависит, будет ли система отзывчивой или зависнет на длинной задаче — поэтому расчёт времени ожидания входит почти в каждую лабораторную по ОС.

Состояния процесса

                 запуск планировщиком
  Готовность  ───────────────────────→  Выполнение
      ↑ ↑                                   │ │
      │ └──── вытеснение по кванту ─────────┘ │
      │                                       │
      │            запрос ввода-вывода        │
      │  Ожидание  ←──────────────────────────┘
      └──────────  завершение операции

Создание → Готовность → ... → Выполнение → Завершение

Алгоритмы планирования

Расчёт показателей

Время ожидания = время начала − время прибытия
Время оборота  = время завершения − время прибытия

Среднее считается по всем процессам.

Процессы:  P1 (10 мс), P2 (3 мс), P3 (5 мс), все прибыли в момент 0

FCFS в порядке P1, P2, P3:
  P1: ожидание 0,  завершение 10
  P2: ожидание 10, завершение 13
  P3: ожидание 13, завершение 18
  Среднее ожидание = (0 + 10 + 13)/3 = 7,67 мс

SJF в порядке P2, P3, P1:
  P2: ожидание 0,  завершение 3
  P3: ожидание 3,  завершение 8
  P1: ожидание 8,  завершение 18
  Среднее ожидание = (0 + 3 + 8)/3 = 3,67 мс

Квант в Round Robin

Слишком большой квант превращает алгоритм в FCFS, слишком малый — топит систему в переключениях контекста. На практике берут 10-100 мс, ориентируясь на правило: 80 % процессов должны укладываться в один квант.

Взаимоблокировка

Дедлок — ситуация, когда каждый процесс группы ждёт ресурс, удерживаемый другим процессом той же группы. Никто не может продолжить, и без вмешательства извне состояние вечно.

Дедлок возникает только при одновременном выполнении всех четырёх условий. Достаточно нарушить любое — и взаимоблокировка становится невозможной; проще всего нарушить четвёртое.

import threading

lock_a = threading.Lock()
lock_b = threading.Lock()

# Дедлок: потоки берут блокировки в разном порядке
def thread_1():
    with lock_a:
        with lock_b:      # ждёт, пока поток 2 отпустит b
            pass

def thread_2():
    with lock_b:
        with lock_a:      # ждёт, пока поток 1 отпустит a
            pass

# Решение: единый порядок захвата во всех потоках
def safe_thread():
    with lock_a:          # всегда сначала a, потом b
        with lock_b:
            pass

Средства синхронизации

• Мьютекс — бинарная блокировка, освобождать её должен тот же поток, который захватил.
• Семафор — счётчик доступных единиц ресурса; операции wait уменьшает, signal увеличивает. Позволяет пустить к ресурсу ровно N потоков.
• Условная переменная — поток засыпает до наступления события, не расходуя процессор.
• Монитор — конструкция языка, объединяющая данные и методы с автоматической взаимной блокировкой.

Классические задачи синхронизации

Обнаружение и восстановление

1. Строится граф ожидания: узлы — процессы, рёбра — «ждёт ресурс, занятый».
2. Цикл в графе означает взаимоблокировку.
3. Восстановление: снять один из процессов, откатить его к контрольной точке или принудительно отобрать ресурс.
4. Алгоритм банкира предотвращает дедлок заранее, допуская только безопасные состояния — но требует знать максимальные потребности процессов.