=== О долгосрочном и краткосрочном планировании
Вытесняющие алгоритмы могут применяться только в краткосрочном планировании

=== Round Robin (вытесняющий FCFS)

От "круглая лента"

Процессы "сидят на карусели", внизу карусели расположен процессор. Когда
процесс находится около процессора, он запускается. Карусель крутится
равномерно.

Более формально:
- процессы в FIFO
- берется процесс из головы
- работает квант времени
- кладется в хвост

Если CPU burst $<=$ кванта времени, то завершаемся заранее, следующему процессу
даем полный квант.

Важен размер кванта времени:
- Если устремить к бесконечности: получаем FCFS
- Если устремить к нулю: теоретически получаем параллельную систему с
  производительностью в N раз меньше. На практике накладные расходы из-за переключения
  контекста превысят полезную работу.

=== SJF (Shortest Job First)

Из "кучи" процессов выбираем тот, у кого самый короткий CPU Burst

Если две версии:
- Вытесняющая и не вытесняющая

==== Не вытесняющий вариант

Выбрали нужный процессор, не отбираем процессор до конца его CPU burst.

Среднее время ожидания является минимальным возможным

==== Вытесняющий вариант

Допускаем возможность возникновения новых процессов.

Временно прекращаем работу исполнявшегося процесса, если CPU burst нового
меньше, то переключаем на него.

==== Проблема SJF

На практике не реализуем т.к. не знаем время очередного CPU burst

Используют приближение:

$tau(n)$ --- величина $n$-ого CPU burst

$T(n + 1)$ --- предсказания для $(n + 1)$-ого CPU burst

$T(0)$ --- выбираем случайно

$alpha in [0, 1]$ --- параметр

Предсказание:
$ T(n + 1) = alpha t(n) + (1 - alpha)T(n) $

Выбор $alpha$:
- $a = 0: T(n + 1) = T(n) = ... = T(0)$ не учета последнего поведения
- $a = 1: T(n + 1) = tau(n)$ не учета предыстории
- Обычно берут $a = 1/2$ т.к. середина и делить на два легко

==== Для долгосрочного планирования

Программист пытается указать, сколько времени нужно:
- Если указать мало, то начнет считаться быстро, но может не досчитаться и быть
  выкинутым из системы
- Если указать много, то точно досчитается, но начнет считаться нескоро

=== Гарантированное планирование

Для многопользовательских систем

Если $N$ пользователей

$T_i$ --- время нахождения $i$-ого пользователя в системе

$tau_i$ --- суммарное процессорное время процессов i-ого времения

- $tau_i << T_i / N$ --- пользователь обделен
- $tau_i >> T_i / N$ --- пользователю благоволят

Введем _коэффициент справедливости_ $= (tau_i N) / T_i$

На исполнение выбираются процессы пользователя с наименьшим коэффициентом
справедливости.

=== Приоритетное планирования

У каждого процесса есть приоритет. Выбирается процесс с минимальным приоритетом.

Гарантированное планирование и SJF --- частные случаи.

Параметры для назначения приоритета:
- Внешние (информация извне; например, "важность" пользователя)
- Внутренние (свойства процесса в системе)

Политика изменения приоритета:
- Статический приоритет
- Динамический приоритет

Процесс с приоритетом $0$ --- самый важный

Приоритетное планирование бывает вытесняющее и не вытесняющее

При долгосрочном загружаем процессы в порядке приоритета. Даже если можно начать
исполнять другие процессы с более низким приоритетом.

= Простые схемы управления памятью

== Иерархия памяти

- Регистры
- Кэш
- Оперативная память
- Вторичная память (swap)

Сверху вниз увеличивается объем и время доступа, падает стоимость

== Принцип локальности

Большинство реальных программ за небольшой промежуток времени работает с
небольшим набором адресов памяти. Принцип связан с принципами мышления человека:
за единицу времени человек может оперировать 5--10 понятиями.

Благодаря этому принципу иерархия памяти работает хорошо.

== Проблема разрешения адресов

Оперативная память может быть представлена в виде массива ячеек с линейными
адресами.

Байт --- минимальная адресуемая ячейка памяти.

Совокупность всех доступных физических адресов ячеек в системе --- это её адресное пространство.

Человеку свойственно мыслить словами (символами), а не числами. Поэтому
имена переменных описываются идентификаторами, образуя символьное адресное
пространство.

Когда делать преобразование из символьного адресного пространства в физическое?
- Компиляция(использовалось в MS DOS)
- Загрузчиком или linker-ом
- Окончательное связывание

=== Логическое адресное пространство

Виртуальная память.

Совокупность адресов, которые используются процессором.

Промежуточный уровень между символьным и физическим адресными пространствами.

Иногда совпадает с физическим адресным пространстве.
