Лабораторная работа №7.

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

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

Рассмотрим сокращенный вариант набора операций со списками в рамках политики SCHED_FIFO.

  1. Когда выполняемый поток управления вытесняется с процессора более приоритетным потоком, он помещается в голову списка, соответствующего его приоритету.
  2. Когда блокированный поток управления становится готовым к выполнению, он помещается в хвост списка, соответствующего его приоритету.
  3. Когда приоритет потока управления увеличился, поток помещается в хвост соответствующего списка;
  4. Когда приоритет потока управления уменьшается, поток помещается в голову соответствующего списка;
  5. Когда выполняемый поток управления добровольно уступает управление (sched_yield()), он помещается в хвост своего списка.
Планировщик обязан принимать решение о диспетчерезации в следующих случаях:
  1. Когда появляется готовый к исполнению новый поток управления
  2. Когда поток управления завершает работу
  3. Когда поток управления блокируется
  4. Когда поток управления становится готовым к исполнению (разблокируется)
  5. Когда изменяется приоритет потока управления.
  6. Когда поток уступает управление
При возникновении одной из вышеперечисленных ситуаций планировщик выполняет два последовательных действия:
  1. выполняет манипуляции с потоком, изменение состояния которого послужило причиной запуска планировщика (блокировка, приостановка и размещение в соответствующем списке ожидания, удаление и т.д.)
  2. принимает решение либо о продолжении исполнения текущего потока, либо о передаче управления от текущего потока к более приоритетному, с соответствующими изменениями в списках ожидания.

Задача

Дано: диапазон приоритетов системы (два числа), набор ресурсов и поступающих в определенные промежутки времени потоков управления. Каждый ресурс определяется идентификатором (Rчисло) и максимальным количеством захватов потоками (число), то есть ресурс может дать доступ к себе определенному количеству потоков, после чего блокирует дальнейшие обращения. Каждый поток управления определяется временем запуска, идентификатором (Pчисло), приоритетом (число) и набором операций, среди которых определены: работа (WORK с параметром - продолжительность), захват ресурса (LOCK с параметром - id ресурса), освобождение ресурса (UNLOCK с параметром - id ресурса), изменение приоритета (PRIO с параметром - дельта изменения), передача управления планировщику (YIELD). Получение данных о новых потоках управления запрещено до наступления времени их появления в системе.

Цель заключается в определении состояний системы

  1. непосредственно перед принятием каждого решения о диспетчерезации
  2. после выполнения первого действия планировщика
  3. после выполнения второго действия планировщика

Таким образом каждая активация планировщика сопровождается выводом ТРЕХ информационных блоков, описывающих состояние системы.

Завершение работы диспетчера определяется завершением работы всех процессов, либо определением факта невозможности завершения. В последнем случае должна быть озвучена причина невозможности завершения.

В состояние системы входит:

  1. Текущее время от начала работы системы, развернутая причина решения о диспетчерезации.
  2. Номер информационного блока (0,1,2)
  3. Текущий исполняемый поток
  4. Набор списков приоритетов, в каждом из которых указывается местоположение потоков
  5. Набор описаний неблокированных потоков (id потока, id захваченных ресурсов, отработанное время, оставшееся время)
  6. Набор описаний блокированных потоков (id потока, id захваченных ресурсов, отработанное время, оставшееся время, id блокирующего ресурса)
  7. Набор ресурсов, для каждого из которых указываются состояние (BLOCK, NONBLOCK), захватившие ресурс потоки (id потоков)
Разрешается объединять в трех информационных блоках те элементы, в которые планировщик никогда не вносит изменения.

Пример набора исходных данных в файле input.txt

1 140 R1 1 R2 5 R3 2
0
 P1 10 WORK 10 LOCK R1 WORK 5 YIELD UNLOCK R1 WORK 10
 P2 10 WORK 100
 P3 20 LOCK R2 WORK 20 UNLOCK R2
5
 P4 12 LOCK R1 WORK 15 LOCK R3 WORK 5 UNLOCK R3 UNLOCK R1