Итак.

- Поток создан – в состоянии готовности, ждет очереди на выполнение.

- Поток выбран на выполнение – выполняется, пока сам не отдаст проц, или пока квант времени не истечет

- Потом – снова в готовность.

- Потоку понадобилась инфа – он идет в ожидание.

- Поток получил нужную инфу – он идет в готовность и в очередь.
Существует переходное состояние ПЕРВООЧЕРЕДНОЙ ГОТОВНОСТИ – когда поток готов получить ресурсы (между блокировкой и готовностью).
В состоянии выполнения может находиться только 1 поток (в однопроцессорной системе);

В ожидании и готовности – много. Тут процессы образуют очереди, организованные в виде однонаправленного списка. Это позволяет легко их переупорядочивать при необходимости.

Планирование и диспетчеризация потоков

От планирования потоков зависит эффективность работы системы. Критерии эффективности бывают разные (см. выше).
В самом общем случае алгоритмы планирования можно разделить

По степени централизации механизма планирования на:

- вытесняющие (preemptive) – поток выполняется, пока сам не решит отдать процессор другому

Есть плюсы:

- исключаются нерациональные прерывания программ в неудобное время

- нет проблем совместного использования данных

- более высокая скорость работы (не надо переключаться туда-сюда)

Но больше минусов

- неудобно для пользователя

- головная боль для программиста (ему нужно решать вопросы планирования, он должен быть очень высококвалифицированным)

Пример – файл-серверы NetWare

- невытесняющие (non-preeemptive) – решение о переключении процессора принимает ОС. Так работает большинство современных ОС, особенно пользовательских.
Невытесняющие алгоритмы планирования:

А) FIFO (First in first out) || FCFS (First come first served);

- Справедливо

- Просто

Но есть convoy effect – короткие процессы, выполняемые после длинных, увеличивают общее время ожидания.

Б) SJFS – shortest job first served – короткая задача обслуживается первой.

- без опережения (процесс не прерывается если уж пошел на исполнение)

- с опережением (прерывается, если появляется поток с еще более минимальным временем исполнения)

В) SRTF – shortest remaining time first – первым идет поток, которому меньше осталось.

---

- оптимален в системах реального времени

Оценка длины среднего периода активности вычисляется по формуле:

T _{(n + 1)} = a*t_n + (1 - a)*t_n

T – текущее значение энного CPU burst

T _{(n + 1)} – следующее его значение, которое мы предсказываем

А – коэффициент старения информации (от 0 до 1);

Вытесняющие алгоритмы планирования бывают разные:

- на основе квантования

- на основе приоритетов

- смешанные

1. 
   Квантование – каждому потоку последовательно выделяется квант процессорного времени.
   

Смена потоков происходит при:

- поток завершился и покинул систему

- произошла ошибка

- поток перешел в заблокированное состояние

- поток исчерпал свой квант (переходит в состояние готовности)
Кванты бывают:

- одинаковые для всех потоков.

- разные
Длина кванта – q. Количество потоков – n. Поток ждет (n-1)*q времени. Чем больше потоков, тем больше ждет, но если квант достаточно маленький – это время ожидания все равно не заметно для пользователя. Обычно оно составляет десятки миллисекунд.
Но чем больше квант – тем больше вероятность, что поток все сделает в первом же цикле, и зависимость времени ожидания потока от времени выполения снижается. Если квант совсем большой – то система превращается в систему линейной обработки.
Кванты для одного потока бывают:

- фиксированной величины

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


При алгоритмах, основанных на квантовании, совершенно не учитывается предварительная инфа о задачах (длинные или короткие, важные или нет, сколько они будут использовать процессор, а сколько – устройства ввода-вывода).

2. 
   Алгоритмы планирования, основанные на приоритетах
   

При приоритетном обслуживании каждый поток обладает изначально известной характеристикой – приоритетом.
Приоритет – число, характеризующее степень привилегированности потока при использовании процессорного времени. Чем выше приоритет – тем выше привилегии, тем меньше поток стоит в очередях.

---

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

---

Приоритеты бывают:

- фиксированные (один раз назначен – и до конца процесса не меняется)

- динамические (меняются в течение жизни потока)

- по инициативе юзера (он выполняет нужную команду) – в современных системах этого стараются избегать, повышать приоритеты потока могут только админы, и то в определенных пределах.

- по инициативе самого потока (обращается с вызовом к ОСи);

- по инициативе ОС в зависимости от ситуации в системе.
Приоритетное обслуживание бывает:

- с относительными приоритетами

Поток выбран и исполняется, хот гром греми.

Подходит для систем пакетной обработки

- с абсолютными приоритетами

Поток исполняется, пока в очереди не появится процесс с более высоким приоритетом.

Подходит для систем, где нужна быстрая реакция на событие.

3. 
   Смешанные алгоритмы планирования
   

Используется как система квантования, так и система приоритетов. Например, в основе лежит квантование, но величина кванта и порядок выбора потока на исполнение определяется его приоритетами. Большинство ОС работают так.

13. 
    Приоритеты и концепции планирования потоков в Windows 2000, ОС Unix System V и OS/2.+
    

Система ОС Unix System V Release 4

Механизм - вытесняющая многозадачность, основанная на использовании приоритетов и квантования.

Потоков тут нет, планируем на уроне процессов.
Существует 3 класса процессов, в зависимости от их задач:

- класс реального времени

- класс системных процессов

- класс процессов разделения времени
Процессы системного класса

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

- стратегия фиксированных приоритетов, но пользователь может их менять.

- для каждого уровня приоритета процессов этого класса предусмотрен свой квант времени

- при наличии готовых к выполнению процессов реального времени, другие процессы не рассматриваются (поэтому их надо тщательно планировать)
Процессы разделения времени:

- долго были единственными в этой ОС, и по умолчанию любой процесс создается именно этого класса

- стратегия динамических приоритетов

- величина приоритета состоит из пользовательской и системной части:

* пользовательская часть может быть снижена пользователем или админом (не повышена)

---

* системная часть может быть снижена, если процесс долго занимает процессор, не уходя в ожидание и повышении процессам, которые часто уходят в состояние ожидания.
Система OS/2

Планирование на основе квантования и абсолютных динамических приоритетов

Существует 4 приоритетных класса:

- критический (time critical) – потоки, выполняющие задачи управления сетью и тд

- серверный (server) – обслуживают серверные приложения

- стандартный (regular) – обслуживают пользовательские программы

- остаточный (idle) – экранная заставка, например.
В каждом классе – 32 приоритетных уровня.

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

Планировщик динамически меняет приоритеты потоков, если

• 
  Поток ожидает больше, чем прописано в специальной переменной. (Его приоритет повышается, но не выше чем нижняя граница диапазона критического класса)
  
• 
  Поток ушел на ввод-вывод. Когда вернется – у него будет максимальный для своего класса приоритет
  
• 
  Поток поступил на выполнение
  

Величина кванта времени здесь тоже динамическая (зависит от загрузки системы и интенсивности подкачки) – от 32 мс до 65536 мс. Если поток был прерван до истечения кванта, то в след раз квант увеличится на 1 таймер (около 32 мс), и так пока не достигнет предела, прописанного в текущих настройках системы.
Система Windows 2000

Система с приоритетам и квантованием, вытесняющая многозадачность.
Приоритеты имеют 32 уровня (0- 31 включительно).

Делятся на 3 диапазона:

- 0 – системный поток для очистки страниц памяти. Готовит страницы памяти, нужен для виртуализации, для гарантированной защиты информации.

-1 – 15 вкл – диапазон динамических приоритетов (могут меняться в процессе работы в зависимости от параметров)

- 16-32 вкл – диапазон статических приоритетов (в процессе работы не меняются)
В зависимости от использования выделяется ряд классов приоритетов процессов:

1. 
   Фоновые потоки (Idle class ) – уровень 4
   
2. 
   – ниже нормального (Below normal class) – уровень 6
   
3. 
   Нормальный (Normal class) – уровень 8
   
4. 
   – выше нормального (Above normal class ) – уровень 10
   
5. 
   Высокий (High class) – уровень 13
   

___________________________

6. 
   Реальное время (Real time class)– уровень 24
   

---

Смотрите также файлы

• Это было много лет назад. Два школьных товарища, Вова и Саша, в конце апреля пошли в лес за берёзовым соком.docx

• Трбие саатыны таырыбы Алдымен сй, ардата атаанады! Трбие саатыны масаты.docx

• И. А. Лубинцов задание к теме 10.docx

• Как вы думаете, в чем заключается актуальность гуманистических качеств в профессиональной деятельности семейного психолога Необходимо ли проводить целенаправленную работу по их формированию.docx

• Нефёдова Мирона Александровича Руководитель проекта учитель физики Большакова Елена Васильевна Вязники 2021. I. Введение II. Теоретическое исследование.doc