Ю. Вахалия - UNIX изнутри (2003) (1114670), страница 51
Текст из файла (страница 51)
Для решения означенной проблемы разработчики 5о1аг)з переложили обработку таких вызовов на нить отложенных вызовов, которая выполняется с максимальным системным приоритетом, который, вместе с тем, ниже любого приоритета реального времени. Вызовы, произведенные процессами реального времени, обрабатываются отдельно и обладают низшими приоритетами прерываний. Это гарантирует своевременное выполнение отложенных вызовов, критичных ко времени. 216 Глава 5. Планирование процессов б.б.4. Инверсия приоритетов Проблема инверсии приоритетпов была впервые описана в работе (10) и относится к ситуации, когда низкоприоритетный процесс удерживает ресурс, необходимый процессу с более высоким приоритетом.
Таким образом, он блокирует работу более высокоприоритетного процесса. Существует несколько разновидностей сформулированной проблемы. Рассмотрим их на примерах (рис. 5.7). В простейшем случае нить Н1 удерживает ресурс Р, который необходим более высокоприоритетной нити Н2, Последняя будет ожидать до тех пор, пока Н1 не освободит ресурс.
Усложним сценарий, добавив нить НЗ, приоритет которой меньше, чем у Н2, но больше, чем у Н1 (рис. 5.7, а). Предположим также, что Н2 и НЗ являются нитями реального времени. Поскольку нить Н2 заблокирована, то НЗ на данный момент является наиболее высокоприоритетной и готовой к выполнению нитью, и поэтому именно она вытеснит нить Н1 (рис. 5.7, б). В результате нить Н2 останется блокированной до тех пор, пока нить НЗ либо завершит работу, либо заблокируется, и только после этого нить Н1 начнет функционировать и освободит ресурс.
Вылолняепюя ) НЗ ~ Приоритет Наэначана 110 на аыпопненое а приоритет (Т2) > приоритета (ТЗ) > приоритета (Т1) Гопюеа к выполнению о >нз Приоритет Выполняемся 110 Выпопняатпся оаа лианою Унаследованный приоритет (Н1) = приоритет (Н2) > приоритета (НЗ) Рис. 5.7. Простейший случай инверсии приоритетов: а — начальная ситуация, б — без наследования приоритетоа, в — с наследованием приоритетов 5.5. Расширенные возможности планирования системы бо(апз 2.х 217 л +ь ч' ея ось Н4 ~ Приоритет ( 135 ~е ,10 <о чН5 ~ Приприте 110 ее Выполняется НБ о + Приорите 100 о Нт ч Приоритет ( 122 Назначена нв выполнение Приоритет (Н4) > приоритета (Н7) > приоритета (Н5) > приоритета (НБ) +ъ о ъ 40 Фо НБ ( Приоритет (но ъ о ч о + Фе Фо Н4 ( Приоритет ( 135 Назначена нв выполнение ф Выполняется ев НБ ~е Приорит 1ОО (Унаследованный приоритет (НБ) = унаследованному приоритету (НБ) = приоритету (Н4) > (приоритета (Н7)) Рис.
В.В. Переходная инверсия приоритетов; а — начальная ситуация, б — при переходящем наследовании Для реализации наследования приоритетов ядро системы 501аг(5 должно содержать дополнительную информацию о занятых объектах. Необходимо Описываемая проблема может быть решена при использовании метода наследования приоритетое или временной передачи приоритетов.
Когда высокоприоритетная нить блокируется в ожидании ресурса, она временно передает свой приоритет менее приоритетной нити, которая в данный момент удерживает этот ресурс. Таким образом, в приведенном выше примере нить Н1 унаследует приоритет нити Н2 и теперь не сможет быть вытеснена нитью НЗ (рис. 5.7, е). Когда нить Н1 освободит ресурс, ее приоритет снова вернется в оригинальное значение, что позволит Н2 вытеснить ее. Нить НЗ будет назначена на выполнение только после того, как Н1 освободит ресурс, а Н2 закончит работу и отдаст процессор. Наследование приоритетов должно быть переходным. На рис. 5.8 нить Н4 блокируется в ожидании ресурса, удерживаемого нитью Н5, которая, в свою очередь, блокирована на ресурсе, удерживаемом нитью Нб.
Если приоритет нити Н4 выше, чем у Н5 и Нб, то нить Нб должна унаследовать приоритет нити Н4 через нить Н5. В противном случае нить Н7, обладающая приоритетом большим, чем у Н5 и Нб, но меньшим, чем у Н4, вытеснит нить Нб и послужит причиной инверсии приоритетов в отношении Н4. Таким образом, унаследованный приоритет нити должен равняться приоритету высокоприоритетной нити, непосредственно или косвенно ожидающей данный ресурс. 218 Глава 5. Планирование процессов идентифицировать, какая нить в данный момент назначена владельцем каждого занятого объекта, а также те объекты, в ожидании которых находится каждая блокированная нить.
Так как наследование является переходным, ядро должно иметь возможность просматривать все объекты и блокированные нити в цепочке синхронизации, начинающейся от каждого данного объекта. О том, как реализовано наследование приоритетов в системе оо(аг(з, будет рассказано в следующем подразделе. 5.6.5. Реализация наследования приоритетов Каждая нить обладает двумя приоритетами: глобальным приоритетом, определяемым классом планирования, и унаследованным приоритетом, зависящим от взаимодействия нити с объектами синхронизации. Унаследованный приоритет обычно равен нулю до тех пор, пока нити не будет передан чей-либо приоритет. Приоритет планирования нити выше, чем ее глобальный и унаследованный приоритеты.
Когда нить должна блокироваться в ожидании ресурса, она вызывает функцию рг ип((соО для передачи своего приоритета всем нитям, которые прямо или косвенно блокируют ресурс. Так как наследование является переходным, функция рг ил((тоО передает унаследованный приоритет вызывающей нити'. Функция рг ипйсо() просматривает цепочку синхронизации этой нити, начиная с объекта, на котором нить заблокирована напрямую.
Этот объект содержит указатель на свою нить-владельца, удерживающую в текущий момент защелку. Если приоритет планирования нити-владельца ниже, чем наследуемый приоритет вызывающей нити, то нить-владелец ресурса унаследует более высокое значение приоритета. Если нить-владелец объекта заблокируется в ожидании другого ресурса, ее структура нити будет содержать указатель на соответствующий объект синхронизации. Функция рг ьггйоО, следуя по этому указателю, передаст приоритет нити-владельцу объекта и т. д. Цепочка синхронизации закончится тогда, когда достигнет незаблокированной нити или объекта, приоритет которого не был инвертирован'. Разберем пример, приведенный на рис.
5.9. Нить Нб является текущей и обладает глобальным приоритетом, равным 110. Она желает заполучить ресурс Р4, удерживаемый нитью Н5. Ядро вызывает функцию рг ел((го(), которая просматривает цепочку синхронизации, начинающуюся от Р4, производя при этом описанные ниже действия. ' В том случае, видимо, когда унаследованный приоритет выше глобального, то есть функция вызывается нитью, находящейся не в начале цепочки. — Прим.
ред. г Приведенный алгоритм известен под названием вычисления глранзитнелого замыкания (сопи рщаиоп ц) Ггапябче с!ванге), а просматриваемая цепочка представляет собой прямой ацихлвческий граф. (Матрица транзитивного замыкания составляется при помощи последовательного удаления узлов, встречающихся двахщы.) — Прим. ред. 5.5. Расширенные возможности планирования системы бо!апз 2.х 219 Блокированные нити Н4 Готове к выполнен нный Р4 Ресурсы Рис. 5.9.
Просмотр цепочки синхронизации 1. Нить Н5, имеющая глобальный приоритет 50, но без унаследованного приоритета, является владельцем ресурса Р4. Так как значение ее приоритета ниже 110, то ей устанавливается унаследованный приоритет, равный 110. 2. Нить Н5 блокирована в ожидании ресурса РЗ, владельцем которого является Н1. Нить Н1 имеет глобальный приоритет 60, но ее унаследованный приоритет равен 100 (через ресурс Р2). Так как это число меньше 110, функция увеличит наследуемый приоритет нити Н1 до 110. 3.
Поскольку нить Н1 не блокирована на каком-либо ресурсе, просмотр цепочки завершается, функция возвращает управление. После возврата из р1 ип11то() ядро блокирует Нб и выбирает другую нить для выполнения. Так как приоритет Н1 был только что поднят до значения П0, скорее всего именно она будет немедленно назначена на выполнение. На рис. 5.10 показана ситуация после переключения контекста. Когда нить освобождает объект, она сбрасывает унаследованный приоритет при помощи вызова р1 ууаЬеО.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
