<<
>>

Планирование процессов в MINIX 3

В MINIX 3 применяется многоуровневый алгоритм планирования. Процессам назначаются начальные приоритеты, однако, как показано на рис. 2.14, число уровней больше, и приоритет процесса может меняться по ходу его выполнения.
Таймерные и системные задания выполняются на уровне 1 и имеют наивысший приоритет. Драйверы устройств на уровне 2 имеют более низкие, но не равные между собой приоритеты. Приоритет серверов уровня 3 ниже, чем у драйверов, но выше, чем у некоторых других процессов. Пользовательские процессы запускаются с одинаковым приоритетом, уступающим всем системным процессам, однако приоритет отдельного процесса может быть понижен или повышен при помощи команды nice.

Планировщик поддерживает 16 очередей готовых процессов, хотя не все из них могут использоваться в конкретный момент времени. На рис. 2.22 показаны очереди и помещенные в них процессы сразу после того, как ядро закончило инициализацию и запустилось, то есть при вызове restart в файле main. с (строка 7252). Массив rdy_head содержит по одному элементу для каждой очереди, указывающему на первый процесс в очереди.

Аналогично, элементы массива rdy_tail указывают на последние процессы в каждой очереди. Оба массива определены с макросом EXTERN в файле proc. h (строки 5595 и 5596). Начальное формирование очередей процессов при запуске системы определяется таблицей image в файле table. с (строки 6095-6109).

Рис. 2.22. Планировщик поддерживает 16 очередей, по одной на каждый уровень приоритета. Здесь показано начальное планирование процессов при запуске М11Ч1Х 3

Планирование внутри каждой очереди происходит по циклическому алгоритму. Если текущий процесс исчерпал свой квант времени, он перемещается в хвост очереди и получает очередной квант.

Однако при разблокировании процесс поступает в начало очереди, если на момент блокирования его квант не истек. Когда такой процесс выбирается на исполнение, вместо нового кванта ему выделяется время, оставшееся в кванте, который он не израсходовал. Массив rdy_tail делает постановку процессов в конец очереди более эффективной. При блокировании текущего процесса или завершении готового процесса по сигналу такой процесс удаляется из очередей планировщика. Очереди состоят только из процессов, готовых к исполнению.

Алгоритм планирования с описанной структурой очередей прост. Берется непустая очередь с наивысшим приоритетом, в которой выбирается первый процесс. Процесс IDLE всегда готов и находится в очереди с самым низким приоритетом. Если все «вышестоящие» очереди пусты, система запускает процесс IDLE.

В предыдущем разделе мы неоднократно упоминали функции enqueue и dequeue. Теперь самое время познакомиться с ними подробнее. Функция enqueue вызывается с указателем на элемент таблицы процессов в качестве аргумента (строка 7787). Она вызывает другую функцию, sched, с указателями на переменные, определяющие, в какую очередь следует поместить процесс и куда именно — в конец или начало. Открываются три возможности. Если выбранная очередь пуста, то в оба массива, rdy_head и rdy_tail, записывается указатель на добавляемый массив, а полю связи p_nextready присваивается специальное значение NlL_PROC, означающее, что данный элемент списка является последним (за ним не следует никакой другой процесс). Если процесс добавляется в начало существующей очереди, ее указателю p_nextready присваивается текущее значение rdy_head, а затем массиву rdy_head присваивается адрес, указывающий на новый процесс. Если процесс добавляется в конец очереди, полю p_nextready текущего хвостового процесса, а также указателю rdy_tail присваивается адрес нового процесса. Полю p_nextready нового процесса присваивается значение NIL_PR0C. Далее вызывается функция pick_proc, определяющая следующий процесс для запуска.

Если процесс необходимо вывести из состояния готовности, вызывается функция dequeue (строка 7823). Для того чтобы процесс перешел в состояние блокировки, необходимо, чтобы он выполнялся, поэтому с большой вероятностью он будет находиться в начале очереди. Тем не менее сигнал может быть послан и невыполняемому процессу. Тогда для поиска «жертвы» выполняется обход очереди, причем с большой вероятностью искомый процесс находится в ее начале. Затем значения указателей изменяются так, что процесс удаляется, а если процесс находился в состоянии выполнения, дополнительно вызывается функция pick_proc.

Касательно функции dequeue есть еще один интересный момент. Поскольку задания, выполняемые в ядре, используют общий аппаратный стек, рекомендуется время от времени проверять целостность их стековых областей. В начале тела dequeue выясняется, находится ли удаляемый процесс внутри ядра. Если это так, то далее проверяется, была ли перезаписана характерная последовательность, помещенная в конец стека (строки 7835-7838).

Затем следует функция sched, выбирающая очередь, в которую следует поместить новый готовый к выполнению процесс, а также место в ней — начало или конец. В таблице процессов для каждого процесса определена длительность кванта, время, оставшееся до истечения кванта, текущий и максимальный приоритеты. В строках 7880-7885 проверяется, полностью ли израсходован квант. Если нет, то процесс перезапускается с количеством времени, оставшимся до окончания кванта. Если же квант исчерпан, то проверяется, был ли процесс запущен дважды подряд. Положительный ответ расценивается как возможное зацикливание или, как минимум, слишком долгое выполнение процесса, и уровень его приоритета увеличивается на единицу. Если же у других процессов была возможность получить ресурсы процессора, уровень приоритета, напротив, уменьшается на единицу. Разумеется, такая мера бессмысленна, если в системе циклически выполняются два процесса, сменяющие друг друга. Выявление подобных ситуаций — актуальная проблема.

Далее выбирается очередь для обработки. Очередь 0 имеет наивысший приоритет, а очередь 15 — самый низкий. Кто-то может возразить и сказать, что должно быть наоборот, однако такая интерпретация соответствует UNIX, где повышение уровня приоритета означает снижение самого приоритета. Процессы ядра (тай- мерное и системное задания) неприкосновенны, а вот приоритет всех остальных процессов может быть понижен помещением их в очередь с большим номером. В момент запуска все процессы имеют наивысший возможный для них приоритет, поэтому попытка уменьшения уровня приоритета ни к чему не приводит. Приоритет процесса может стать выше лишь в случае, если он был хотя бы единожды понижен после запуска. У приоритетов обычных процессов есть и нижняя граница — они никогда не попадают в одну очередь с процессом IDLE.

Вернемся к функции pick_proc (строка 7910). Главное ее назначение — установить указатель next_ptr. Любое изменение в очередях, способное повлиять на выбор следующего процесса для выполнения, требует нового вызова pick_ ргос. Если текущий процесс блокируется, pick_proc вызывается для перепланирования процессора. Фактически, функция pick_proc и есть планировщик.

Функция pick_proc проста. Она проверяет каждую очередь, причем очередь TASK_Q проверяется первой. Если в этой очереди имеется готовый процесс, pick_proc сразу устанавливает указатель proc_ptr и завершается. В противном случае проверяется соседняя очередь с более низким приоритетом и т. д. — вплоть до очереди IDLE_Q. Указатель bill_ptr изменяется и задает пользовательский процесс, время которого расходуется системой (строка 7694). В качестве такого процесса используется последний процесс, выполнявшийся системой.

В файле ргос . с имеются еще три процедуры — lock_send, lock_enqueue и lock_dequeue. Все они обеспечивают доступ к своим основным функциям при помощи вызовов 1оски unlock по аналогии с рассмотренной нами процедурой lock_notify.

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

2.6.11.

<< | >>
Источник: Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание. 2007

Еще по теме Планирование процессов в MINIX 3:

  1. Планирование, а не планы
  2. Планирование телепередач
  3. 11. КРИМИНАЛИСТИЧЕСКИЕ ВЕРСИИ И ПЛАНИРОВАНИЕ РАССЛЕДОВАНИЯ
  4. 10.2. Планирование и организация следственных действий
  5. § 2. ПЛАНИРОВАНИЕ И СОДЕРЖАНИЕ НАБЛЮДЕНИЯ
  6. 5.4. Планирование упражнений
  7. Искусство планирования спонтанного
  8. 5.9. Планирование социальных контактов
  9. 5.2.9. Планирование сроков достижения уже определённой цели
  10. Статья 437. Планирование, подготовка, развязывание и ведение агрессивной войны
  11. 11.3. Понятие и основные принципы планирования расследования в зависимости от исходной информации (следственной ситуации)
  12. Очерк 2: Берт «Процесс — вот мое достояние. Именно процесс создает успех»
  13. Задания, мешающие когнитивному процессу (ЗМКП), и задания, помогающие когнитивному процессу (ЗПКП)
  14. ПРОЦЕСС НЕРВНЫЙ
  15. ПРОЦЕСС НАДСОЗНАТЕЛЬНЫЙ
  16. Психические процессы
  17. ПРОЦЕСС НЕРВНЫЙ: ИНДУКЦИЯ
  18. Уголовный процесс