ГЛАВА 8. ДИСПЕТЧЕРИЗАЦИЯ ПРОЦЕССОВ И ЕЕ ВРЕМЕННЫЕ ХАРАКТЕРИСТИКИ
Оцените этот текст
В системе разделения времени ядро предоставляет процессу ресурсы цент- рального процессора (ЦП) на интервал времени, называемый квантом, по истече- нии которого выгружает этот процесс и запускает другой, периодически переу- порядочивая очередь процессов. Алгоритм планирования процессов в системе UNIX использует время выполнения в качестве параметра. Каждый активный про- цесс имеет приоритет планирования; ядро переключает контекст на процесс с наивысшим приоритетом. При переходе выполняющегося процесса из режима ядра в режим задачи ядро пересчитывает его приоритет, периодически и в режиме зада- чи переустанавливая приоритет каждого процесса, готового к выполнению. Информация о времени, связанном с выполнением, нужна также и некоторым из пользовательских процессов: используемая ими, например, команда time поз- воляет узнать, сколько времени занимает выполнение другой команды, команда date выводит текущую дату и время суток. С помощью различных системных функ- ций процессы могут устанавливать или получать временные характеристики вы- полнения в режиме ядра, а также степень загруженности центрального процессо- ра. Время в системе поддерживается с помощью аппаратных часов, которые посы- лают ЦП прерывания с фиксированной, аппаратно-зависимой частотой, обычно 50-100 раз в секунду. Каждое поступление прерывания по таймеру (часам) име- нуется таймерным тиком. В настоящей главе рассматриваются особенности реали- зации процессов во времени, включая планирование процессов в системе UNIX, описание связанных со временем системных функций, а также функций, выполняе- мых программой обработки прерываний по таймеру. Планировщик процессов в системе UNIX принадлежит к общему классу плани- ровщиков, работающих по принципу "карусели с многоуровневой обратной связью". В соответствии с этим принципом ядро предоставляет процессу ресурсы ЦП на квант времени, по истечении которого выгружает этот процесс и возвра- щает его в одну из нескольких очередей, регулируемых приоритетами. Прежде чем процесс завершится, ему может потребоваться множество раз пройти через цикл с обратной связью. Когда ядро выполняет переключение контекста и восс- танавливает контекст процесса, процесс возобновляет выполнение с точки при- останова. Сразу после переключения контекста ядро запускает алгоритм планирования выполнения процессов (Рисунок 8.1), выбирая на выполнение процесс с наивыс- шим приоритетом среди процессов, находящихся в состояниях "резервирования" и "готовности к выполнению, будучи загруженным в память". Рассматривать про- цессы, не загруженные в память, не имеет смысла, поскольку не будучи загру- жен, процесс не может выполняться. Если наивысший приоритет имеют сразу нес- колько процессов, ядро, используя принцип кольцевого списка (карусели), вы- бирает среди них тот процесс, который находится в состоянии "готовности к выполнению" дольше остальных. Если ни один из процессов не может быть выбран для выполнения, ЦП простаивает до момента получения следующего прерывания, которое произойдет не позже чем через один таймерный тик; после обработки этого прерывания ядро снова запустит алгоритм планирования. 232 +------------------------------------------------------------+ | алгоритм schedule_process | | входная информация: отсутствует | | выходная информация: отсутствует | | { | | выполнять пока (для запуска не будет выбран один из про-| | цессов) | | { | | для (каждого процесса в очереди готовых к выполнению)| | выбрать процесс с наивысшим приоритетом из загру-| | женных в память; | | если (ни один из процессов не может быть избран для | | выполнения) | | приостановить машину; | | /* машина выходит из состояния простоя по преры- | | /* ванию | | */ | | } | | удалить выбранный процесс из очереди готовых к выполне- | | нию; | | переключиться на контекст выбранного процесса, возобно- | | вить его выполнение; | | } | +------------------------------------------------------------+ Рисунок 8.1. Алгоритм планирования выполнения процессов В каждой записи таблицы процессов есть поле приоритета, используемое планировщиком процессов. Приоритет процесса в режиме задачи зависит от того, как этот процесс перед этим использовал ресурсы ЦП. Можно выделить два клас- са приоритетов процесса (Рисунок 8.2): приоритеты выполнения в режиме ядра и приоритеты выполнения в режиме задачи. Каждый класс включает в себя ряд зна- чений, с каждым значением логически ассоциирована некоторая очередь процес- сов. Приоритеты выполнения в режиме задачи оцениваются для процессов, выгру- женных по возвращении из режима ядра в режим задачи, приоритеты выполнения в режиме ядра имеют смысл только в контексте алгоритма sleep. Приоритеты вы- полнения в режиме задачи имеют верхнее пороговое значение, приоритеты выпол- нения в режиме ядра имеют нижнее пороговое значение. Среди приоритетов вы- полнения в режиме ядра далее можно выделить высокие и низкие приоритеты: процессы с низким приоритетом возобновляются по получении сигнала, а процес- сы с высоким приоритетом продолжают оставаться в состоянии приостанова (см. раздел 7.2.1). Пороговое значение между приоритетами выполнения в режимах ядра и задачи на Рисунке 8.2 отмечено двойной линией, проходящей между приоритетом ожида- ния завершения потомка (в режиме ядра) и нулевым приоритетом выполнения в режиме задачи. Приоритеты процесса подкачки, ожидания ввода-вывода, связан- ного с диском, ожидания буфера и индекса являются высокими, не допускающими прерывания системными приоритетами, с каждым из которых связана очередь из 1, 3, 2 и 1 процесса, соответственно, в то время как приоритеты ожидания ввода с терминала, вывода на терминал и завершения потомка являются низкими, допускающими прерывания системными приоритетами, с каждым из которых связана очередь из 4, 0 и 2 процессов, соответственно. На рисунке представлены также уровни приоритетов выполнения в режиме задачи (*). Ядро вычисляет приоритет процесса в следующих случаях: 233
(*) Наивысшим значением приоритета в системе является нулевое значение. Та- ким образом, нулевой приоритет выполнения в режиме задачи выше приорите- та, имеющего значение, равное 1, и т.д. * Непосредственно перед переходом процесса в состояние приостанова ядро назначает ему приоритет исходя из причины приостанова. Приоритет не за- висит от динамических характеристик процесса (продолжительности вво- да-вывода или времени счета), напротив, это постоянная величина, жестко устанавливаемая в момент приостанова и зависящая только от причины пере- хода процесса в данное состояние. Процессы, приостановленные алгоритмами низкого уровня, имеют тенденцию порождать тем больше узких мест в систе- ме, чем дольше они находятся в этом состоянии; поэтому им назначается более высокий приоритет по сравнению с остальными процессами. Например, процесс, приостановленный в ожидании завершения ввода-вывода, связанного с диском, имеет более высокий приоритет по сравнению с процессом, ожида- ющим освобождения буфера, по нескольким причинам. Прежде всего, у перво- го процесса уже есть буфер, поэтому не исключена возможность, что когда он возобновится, он успеет освободить и буфер, и другие ресурсы. Чем больше ресурсов свободно, тем меньше шансов для возникновения взаимной блокировки процессов. Системе не придется часто переключать Приоритеты выполнения Уровни приоритетов Процессы в режиме ядра | +----------------------+ | | Процесс | +--+ | | подкачки |-+ | | Не допускающие +----------------------+ +--+ | |Ожидание ввода-вывода,| +--+ +--+ +--+ | прерывания | связанного с диском |-+ +-+ +-+ | | +----------------------+ +--+ +--+ +--+ | | Ожидание | +--+ +--+ | | буфера |-+ +-+ | | +----------------------+ +--+ +--+ | | Ожидание | +--+ | | индекса |-+ | | +----------------------+ +--+ | +----------------------+ | | Ожидание ввода с тер-| +--+ +--+ +--+ +--+ | | минала |-+ +-+ +-+ +-+ | | Допускающие +----------------------+ +--+ +--+ +--+ +--+ | | Ожидание вывода на | | прерывания | терминал | | +----------------------+ | | Ожидание завершения | +--+ +--+ | | потомка |-+ +-+ | v +----------------------+ +--+ +--+ Пороговый приоритет +----------------------+ ^ | Уровень задачи 0 | | +----------------------+ +--+ +--+ +--+ +--+ | | Уровень задачи 1 |-+ +-+ +-+ +-+ | | +----------------------+ +--+ +--+ +--+ +--+ | | - | | | - | | +----------------------+ +--+ Приоритеты выполнения | Уровень задачи n |-+ | в режиме задачи +----------------------+ +--+ Рисунок 8.2. Диапазон приоритетов процесса 234 контекст, благодаря чему сократится время реакции процесса и увеличится производительность системы. Во-вторых, буфер, освобождения которого ожи- дает процесс, может быть занят процессом, ожидающим в свою очередь за- вершения ввода-вывода. По завершении ввода-вывода будут возобновлены оба процесса, поскольку они были приостановлены по одному и тому же адресу. Если первым запустить на выполнение процесс, ожидающий освобождения бу- фера, он в любом случае снова приостановится до тех пор, пока буфер не будет освобожден; следовательно, его приоритет должен быть ниже. * По возвращении процесса из режима ядра в режим задачи ядро вновь вычис- ляет приоритет процесса. Процесс мог до этого находиться в состоянии приостанова, изменив свой приоритет на приоритет выполнения в режиме яд- ра, поэтому при переходе процесса из режима ядра в режим задачи ему дол- жен быть возвращен приоритет выполнения в режиме задачи. Кроме того, яд- ро "штрафует" выполняющийся процесс в пользу остальных процессов, отби- рая используемые им ценные системные ресурсы. * Приоритеты всех процессов в режиме задачи с интервалом в 1 секунду (в версии V) пересчитывает программа обработки прерываний по таймеру, по- буждая тем самым ядро выполнять алгоритм планирования, чтобы не допус- тить монопольного использования ресурсов ЦП одним процессом. В течение кванта времени таймер может послать процессу несколько преры- ваний; при каждом прерывании программа обработки прерываний по таймеру уве- личивает значение, хранящееся в поле таблицы процессов, которое описывает продолжительность использования ресурсов центрального процессора (ИЦП). В версии V каждую секунду программа обработки прерываний переустанавливает значение этого поля, используя функцию полураспада (decay): decay(ИЦП) = ИЦП/2; После этого программа пересчитывает приоритет каждого процесса, находящегося в состоянии "зарезервирован, но готов к выполнению", по формуле приоритет = (ИЦП/2) + (базовый уровень приоритета задачи) где под "базовым уровнем приоритета задачи" понимается пороговое значение, расположенное между приоритетами выполнения в режимах ядра и задачи. Высоко- му приоритету планирования соответствует количественно низкое значение. Ана- лиз функций пересчета продолжительности использования ресурсов ЦП и приори- тета процесса показывает: чем ниже скорость полураспада значения ИЦП, тем медленнее приоритет процесса достигает значение базового уровня; поэтому процессы в состоянии "готовности к выполнению" имеют тенденцию занимать большое число уровней приоритетов. Результатом ежесекундного пересчета приоритетов является перемещение процессов, находящихся в режиме задачи, от одной очереди к другой, как пока- зано на Рисунке 8.3. По сравнению с Рисунком 8.2 один процесс перешел из очереди, соответствующей уровню 1, в очередь, соответствующую нулевому уров- ню. В реальной системе все процессы, имеющие приоритеты выполнения в режиме задачи, поменяли бы свое местоположение в очередях. При этом следует указать на невозможность изменения приоритета процесса в режиме ядра, а также на не- возможность пересечения пороговой черты процессами, выполняющимися в режиме задачи, до тех пор, пока они не обратятся к операционной системе и не перей- дут в состояние приостанова. Ядро стремится производить пересчет приоритетов всех активных процессов ежесекундно, однако интервал между моментами пересчета может слегка варьиро- ваться. Если прерывание по таймеру поступило тогда, когда ядро исполняло критический отрезок программы (другими словами, в то время, когда приоритет работы ЦП был повышен, но, очевидно, не настолько, чтобы воспрепятствовать 235 прерыванию данного типа), ядро не пересчитывает приоритеты, иначе ему приш- лось бы надолго задержаться на критическом отрезке. Вместо этого ядро запо- минает то, что ему следует произвести пересчет приоритетов, и делает это при первом же прерывании по таймеру, поступающем после снижения приоритета рабо- ты ЦП. Периодический пересчет приоритета процессов гарантирует проведение стратегии планирования, основанной на использовании кольцевого списка про- цессов, выполняющихся в режиме задачи. При этом конечно же ядро откликается на интерактивные запросы таких программ, как текстовые редакторы или прог- раммы форматного ввода: процессы, их реализующие, имеют высокий коэффициент простоя (отношение времени простоя к продолжительности использования ЦП) и поэтому естественно было бы повышать их приоритет, когда они готовы для вы- полнения (см. [Thompson 78], стр.1937). В других механизмах планирования квант времени, выделяемый процессу на работу с ресурсами ЦП, динамически из- меняется в интервале между 0 и 1 сек. в зависимости от степени загрузки сис- темы. При этом время реакции на запросы процессов может Приоритеты выполнения Уровни приоритетов Процессы в режиме ядра | +----------------------+ | | Процесс | +--+ | | подкачки |-+ | | Не допускающие +----------------------+ +--+ | |Ожидание ввода-вывода,| +--+ +--+ +--+ | прерывания | связанного с диском |-+ +-+ +-+ | | +----------------------+ +--+ +--+ +--+ | | Ожидание | +--+ +--+ | | буфера |-+ +-+ | | +----------------------+ +--+ +--+ | | Ожидание | +--+ | | индекса |-+ | | +----------------------+ +--+ | +----------------------+ | | Ожидание ввода с тер-| +--+ +--+ +--+ +--+ | | минала |-+ +-+ +-+ +-+ | | Допускающие +----------------------+ +--+ +--+ +--+ +--+ | | Ожидание вывода на | | прерывания | терминал | | +----------------------+ | | Ожидание завершения | +--+ +--+ | | потомка |-+ +-+ | v +----------------------+ +--+ +--+ Пороговый приоритет +----------------------+ +--+ ^ | Уровень задачи 0 |-+ |<- - - - - -+ | +----------------------+ +--+ - | | | +--+ +--+ +--+ ++-+ | | Уровень задачи 1 |-+ +-+ +-+ + + | | +----------------------+ +--+ +--+ +--+ +--+ | | - | | | - | | +----------------------+ +--+ Приоритеты выполнения | Уровень задачи n |-+ | в режиме задачи +----------------------+ +--+ Рисунок 8.2. Переход процесса из одной очереди в другую сократиться за счет того, что на ожидание момента запуска процессам уже не нужно отводить по целой секунде; однако, с другой стороны, ядру приходится чаще прибегать к переключению контекстов. 236 На Рисунке 8.4 показана динамика изменений приоритетов процессов A, B и C в версии V при следующих допущениях: все эти процессы были созданы с пер- воначальным приоритетом 60, который является наивысшим приоритетом выполне- ния в режиме задачи, прерывания по таймеру поступают 60 раз в секунду, про- цессы не используют вызов системных функций, в системе нет других процессов, готовых к выполнению. Ядро вычисляет полураспад показателя ИЦП по формуле: Время Процесс A Процесс B Процесс C | Приоритет ИЦП - Приоритет ИЦП - Приоритет ИЦП 0 --+-- - - | 60 0 - 60 0 - 60 0 | 1 - - | 2 - - | ­ - - | ­ - - 1 --+-- 60 - - | 75 30 - 60 0 - 60 0 | - 1 - | - 2 - | - ­ - | - ­ - 2 --+-- - 60 - | 67 15 - 75 30 - 60 0 | - - 1 | - - 2 | - - ­ | - - ­ 3 --+-- - - 60 | 63 7 - 67 15 - 75 30 | 8 - - | 9 - - | ­ - - | ­ - - 4 --+-- 67 - - | 76 33 - 63 7 - 67 15 | - 8 - | - 9 - | - ­ - | - ­ - 5 --+-- - 67 - | 68 16 - 76 33 - 63 7 | - - | - - Рисунок 8.4. Пример диспетчеризации процессов ИЦП = decay(ИЦП) = ИЦП/2; а приоритет процесса по формуле: приоритет = (ИЦП/2) + 60; Если предположить, что первым запускается процесс A и ему выделяется квант времени, он выполняется в течение 1 секунды: за это время таймер посылает системе 60 прерываний и столько же раз программа обработки прерываний увели- чивает для процесса A значение поля, содержащего показатель ИЦП (с 0 до 60). 237 По прошествии секунды ядро переключает контекст и, произведя пересчет прио- ритетов для всех процессов, выбирает для выполнения процесс B. В течение следующей секунды программа обработки прерываний по таймеру 60 раз повышает значение поля ИЦП для процесса B, после чего ядро пересчитывает параметры диспетчеризации для всех процессов и вновь переключает контекст. Процедура повторяется многократно, сопровождаясь поочередным запуском процессов на вы- полнение. Теперь рассмотрим процессы с приоритетами, приведенными на Рисунке 8.5, и предположим, что в системе имеются и другие процессы. Ядро может выгрузить процесс A, оставив его в состоянии "готовности к выполнению", после того, как он получит подряд несколько квантов времени для работы с ЦП и снизит та- ким образом свой приоритет выполнения в режиме задачи (Рисунок 8.5а). Через некоторое время после запуска процесса A в состояние "готовности к выполне- нию" может перейти процесс B, приоритет которого в тот момент окажется выше приоритета процесса A (Рисунок 8.5б). Если ядро за это время не запланирова- ло к выполнению любой другой процесс (из тех, что не показаны на рисунке), оба процесса (A и B) при известных обстоятельствах могут на некоторое время оказаться на одном уровне приоритетности, хотя процесс B попадет на этот уровень первым из-за того, что его первоначальный приоритет был ближе (Рису- нок 8.5в и 8.5г). Тем не менее, ядро запустит процесс A впереди процесса B, поскольку процесс A находился в состоянии "готовности к выполнению" более длительное время (Рисунок 8.5д) - это решающее условие, если выбор произво- дится из процессов с одинаковыми приоритетами. В разделе 6.4.3 уже говорилось о том, что ядро запускает процесс на вы- полнение после переключения контекста: прежде чем перейти в состояние приос- танова или завершить свое выполнение процесс должен переключить контекст, кроме того он имеет возможность переключать контекст в момент перехода из режима ядра в режим задачи. Ядро выгружает процесс, который собирается пе- рейти в режим задачи, если имеется готовый к выполнению процесс с более вы- соким приоритетом. Такая ситуация возникает, если ядро вывело из состояния приостанова процесс с приоритетом, превышающим приоритет текущего процесса, или если в результате обработки прерывания по таймеру изменились приоритеты всех готовых к выполнению процессов. В первом случае текущий процесс не мо- жет выполняться в режиме задачи, поскольку имеется процесс с более высоким приоритетом выполнения в режиме ядра. Во втором случае программа обработки прерываний по таймеру решает, что процесс использовал выделенный ему квант времени, и поскольку множество процессов при этом меняют свои приоритеты, ядро выполняет переключение контекста. Процессы могут управлять своими приоритетами с помощью системной функции nice: nice(value); где value - значение, в процессе пересчета прибавляемое к приори- тету процесса: приоритет = (ИЦП/константа) + (базовый приоритет) + (значение nice) Системная функция nice увеличивает или уменьшает значение поля nice в табли- це процессов на величину параметра функции, при этом только суперпользовате- лю дозволено указывать значения, увеличивающие приоритет процесса. Кроме то- го, только суперпользователь может указывать значения, лежащие ниже опреде- ленного порога. Пользователи, вызывающие системную функцию nice для того, чтобы понизить приоритет во время выполнения интенсивных вычислительных ра- бот, "удобны, приятны" (nice) для остальных пользователей сис- 238 +---------+ +---------+ +---------+ ^ 60 +---------+ +---------+ +----B----+ | +---------+ +---------+ +---------+ | +---------+ +----B----+ +----A----+ Более +---------+ +---------+ +---------+ высокий +---------+ +----A----+ +---------+ приори- +---------+ +---------+ +---------+ тет +----A----+ +---------+ +---------+ | +---------+ +---------+ +---------+ | (а) (б) (в) +----B----+ +-A-----B-+ +----B----+ 60 +----A----+ +---------+ +---------+(процесс +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ +---------+ (г) (д) (е) Рисунок 8.5. Планирование на основе кольцевого списка и прио- ритеты процессов темы, отсюда название функции. Процессы наследуют значение nice у своего ро- дителя при выполнении системной функции fork. Функция nice действует только для выполняющихся процессов; процесс не может сбросить значение nice у дру- гого процесса. С практической точки зрения это означает, что если админист- ратору системы понадобилось понизить приоритеты различных процессов, требую- щих для своего выполнения слишком много времени, у него не будет другого способа сделать это быстро, кроме как вызвать функцию удаления (kill) для всех них сразу. Вышеописанный алгоритм планирования не видит никакой разницы между поль- зователями различных классов (категорий). Другими словами, невозможно выде- лить определенной совокупности процессов, например, половину сеанса работы с ЦП. Тем не менее, такая возможность имеет важное значение для организации работы в условиях вычислительного центра, где группа пользователей может по- желать купить только половину машинного времени на гарантированной основе и с гарантированным уровнем реакции. Здесь мы рассмотрим схему, именуемую "Планированием на основе справедливого раздела" (Fair Share Scheduler) и ре- ализованную на вычислительном центре Indian Hill фирмы AT&T Bell Laboratories [Henry 84]. Принцип "планирования на основе справедливого раздела" состоит в делении совокупности пользователей на группы, являющиеся объектами ограничений, нак- ладываемых обычным планировщиком на обработку процессов из каждой группы. При этом система выделяет время ЦП пропорционально числу групп, вне зависи- мости от того, сколько процессов выполняется в группе. Пусть, например, в системе имеются четыре планируемые группы, каждая из которых загружает ЦП на 25% и содержит, соответственно, 1, 2, 3 и 4 процесса, реализующих счетные задачи, которые никогда по своей воле не уступят ЦП. При условии, что в сис- теме больше нет никаких других процессов, каждый процесс при использовании традиционного алгоритма планирования получил бы 10% времени ЦП (поскольку 239 всего процессов 10 и между ними не делается никаких различий). При использо- вании алгоритма планирования на основе справедливого раздела процесс из пер- вой группы получит в два раза больше времени ЦП по сравнению с каждым про- цессом из второй группы, в 3 раза больше по сравнению с каждым процессом из третьей группы и в 4 раза больше по сравнению с каждым процессом из четвер- той. В этом примере всем процессам в группе выделяется равное время, пос- кольку продолжительность цикла, реализуемого каждым процессом, заранее не установлена. Реализация этой схемы довольно проста, что и делает ее привлекательной. В формуле расчета приоритета процесса появляется еще один термин - "приори- тет группы справедливого раздела". В пространстве процесса также появляется новое поле, описывающее продолжительность ИЦП на основе справедливого разде- ла, общую для всех процессов из группы. Программа обработки прерываний по таймеру увеличивает значение этого поля для текущего процесса и ежесекундно пересчитывает значения соответствующих полей для всех процессов в системе. Новая компонента формулы вычисления приоритета процесса представляет собой нормализованное значение ИЦП для каждой группы. Чем больше процессорного времени выделяется процессам группы, тем выше значение этого показателя и ниже приоритет. В качестве примера рассмотрим две группы процессов (Рисунок 8.6), в од- ной из которых один процесс (A), в другой - два (B и C). Предположим, что ядро первым запустило на выполнение процесс A, в течение секунды увеличивая соответствующие этому процессу значения полей, описывающих индивидуальное и групповое ИЦП. В результате пересчета приоритетов по истечении секунды про- цессы B и C будут иметь наивысшие приоритеты. Допустим, что ядро выбирает на выполнение процесс B. В течение следующей секунды значение поля ИЦП для про- цесса B поднимается до 60, точно такое же значение принимает поле группового ИЦП для процессов B и C. Таким образом, по истечении второй секунды процесс C получит приоритет, равный 75 (сравните с Рисунком 8.4), и ядро запустит на выполнение процесс A с приоритетом 74. Дальнейшие действия можно проследить на рисунке: ядро по очереди запускает процессы A, B, A, C, A, B и т.д. Режим реального времени подразумевает возможность обеспечения достаточ- ной скорости реакции на внешние прерывания и выполнения отдельных процессов в темпе, соизмеримом с частотой возникновения вызывающих прерывания событий. Примером системы, работающей в режиме реального времени, может служить сис- тема управления жизнеобеспечением пациентов больниц, мгновенно реагирующая на изменение состояния пациента. Процессы, подобные текстовым редакторам, не считаются процессами реального времени: в них быстрая реакция на действия пользователя является желательной, но не необходимой (ничего страшного не произойдет, если пользователь, выполняющий редактирование текста, подождет ответа несколько лишних секунд, хотя у пользователя на этот счет могут быть и свои соображения). Вышеописанные алгоритмы планирования выполнения процес- сов предназначены специально для использования в системах разделения времени и не годятся для условий работы в режиме реального времени, поскольку не га- рантируют запуск ядром каждого процесса в течение фиксированного интервала времени, позволяющего говорить о взаимодействии вычислительной системы с процессами в темпе, соизмеримом со скоростью протекания этих процессов. Дру- гой помехой в поддержке работы в режиме реального времени является невыгру- жаемость ядра; ядро не может планировать выполнение процесса реального вре- мени в режиме задачи, если оно уже исполняет другой процесс в режиме ядра, без внесения в работу существенных изменений. В настоящее время системным программистам приходится переводить процессы реального времени в режим ядра, чтобы обеспечить достаточную скорость реакции. Правильное решение этой проб- лемы - дать таким процессам возможность динамического протекания (другими словами, они не должны быть встроены в ядро) с предоставлением соответствую- 240 Время Процесс A Процесс B Процесс C | Прио- Ин- Груп-- Прио- Ин- Груп-- Прио- Ин- Груп- | ритет диви- по- - ритет диви- по- - ритет диви- по- | дуал. вое - дуал. вое - дуал. вое | ИЦП ИЦП - ИЦП ИЦП - ИЦП ИЦП 0 --+-- - - | 60 0 0 - 60 0 0 - 60 0 0 | 1 1 - - | 2 2 - - | ­ ­ - - | ­ ­ - - 1 --+-- 60 60 - - | 90 30 30 - 60 0 0 - 60 0 0 | - 1 1 - 1 | - 2 2 - 2 | - ­ ­ - ­ | - ­ ­ - ­ 2 --+-- - 60 60 - 60 | 74 15 15 - 90 30 30 - 75 0 30 | 16 16 - - | 17 17 - - | ­ ­ - - | ­ ­ - - 3 --+-- 75 75 - - | 96 37 37 - 74 15 15 - 67 0 15 | - 16 - 1 16 | - 17 - 2 17 | - ­ - ­ ­ | - ­ - ­ ­ 4 --+-- - 75 - 60 75 | 78 18 18 - 81 7 37 - 93 30 37 | 19 19 - - | 20 20 - - | ­ ­ - - | ­ ­ - - 5 --+-- 78 78 - - | 98 39 39 - 70 3 18 - 76 15 18 | - - | - - Рисунок 8.6. Пример планирования на основе справедливого раздела, в ко- тором используются две группы с тремя процессами щего механизма, с помощью которого они могли бы сообщать ядру о своих нуж- дах, вытекающих из особенностей работы в режиме реального времени. На сегод- няшний день в стандартной системе UNIX такая возможность отсутствует. Существует несколько системных функций, имеющих отношение к времени про- текания процесса: stime, time, times и alarm. Первые две имеют дело с гло- бальным системным временем, последние две - с временем выполнения отдельных процессов. Функция stime дает суперпользователю возможность заносить в глобальную ние глобальной переменной. Выбирается время из этой переменной с помощью функции time: 241 time(tloc); где tloc - указатель на переменную, принадлежащую процессу, в которую зано- сится возвращаемое функцией значение. Функция возвращает это значение и из самой себя, например, команде date, которая вызывает эту функцию, чтобы оп- ределить текущее время. Функция times возвращает суммарное время выполнения процесса и всех его потомков, прекративших существование, в режимах ядра и задачи. Синтаксис вы- +------------------------------------------------------------+ | #include | | #include | | extern long times(); | | | | main() | | { | | int i; | | /* tms - имя структуры данных, состоящей из 4 элемен- | | тов */ | | struct tms pb1,pb2; | | long pt1,pt2; | | | | pt1 = times(&pb1); | | for (i = 0; i < 10; i++) | | if (fork() == 0) | | child(i); | | | | for (i = 0; i < 10; i++) | | wait((int*) 0); | | pt2 = times(&pb2); | | printf("процесс-родитель: реальное время %u | | в режиме задачи %u в режиме ядра %u | | потомки: в режиме задачи %u в режиме ядра %u\n",| | pt2 - pt1,pb2.tms_utime - pb1.tms_utime, | | pb2.tms_stime - pb1.tms_stime, | | pb2.tms_cutime - pb1.tms_cutime, | | pb2.tms_cstime - pb1.tms_cstime); | | } | | | | child(n); | | int n; | | { | | int i; | | struct tms cb1,cb2; | | long t1,t2; | | | | t1 = times(&cb1); | | for (i = 0; i < 10000; i++) | | ; | | t2 = times(&cb2); | | printf("потомок %d: реальное время %u в режиме задачи %u| | в режиме ядра %u\n",n,t2 - t1, | | cb2.tms_utime - cb1.tms_utime, | | cb2.tms_stime - cb1.tms_stime); | | exit(); | | } | +------------------------------------------------------------+ Рисунок 8.7. Пример программы, использующей функцию times 242 зова функции: times(tbuffer) struct tms *tbuffer; где tms - имя структуры, в которую помещаются возвращаемые значения и кото- рая описывается следующим образом: struct tms { /* time_t - имя структуры данных, в которой хранится время */ time_t tms_utime; /* время выполнения процесса в режиме задачи */ time_t tms_stime; /* время выполнения процесса в режиме ядра */ time_t tms_cutime; /* время выполнения потомков в режиме задачи */ time_t tms_cstime; /* время выполнения потомков в режиме ядра */ }; Функция times возвращает время, прошедшее "с некоторого произвольного момен- та в прошлом", как правило, с момента загрузки системы. На Рисунке 8.7 приведена программа, в которой процесс-родитель создает 10 потомков, каждый из которых 10000 раз выполняет пустой цикл. Процесс-ро- дитель обращается к функции times перед созданием потомков и после их завер- шения, в свою очередь потомки вызывают эту функцию перед началом цикла и после его завершения. Кто-то по наивности может подумать, что время выполне- ния потомков процесса в режимах задачи и ядра равно сумме соответствующих слагаемых каждого потомка, а реальное время процесса-родителя является сум- мой реального времени его потомков. Однако, время выполнения потомков не включает в себя время, затраченное на исполнение системных функций fork и exit, кроме того оно может быть искажено за счет обработки прерываний и пе- реключений контекста. С помощью системной функции alarm пользовательские процессы могут иници- ировать посылку сигналов тревоги ("будильника") через кратные промежутки времени. Например, программа на Рисунке 8.8 каждую минуту проверяет время доступа к файлу и, если к файлу было произведено обращение, выводит соответ- ствующее сообщение. Для этого в цикле, с помощью функции stat, устанавлива- ется момент последнего обращения к файлу и, если оно имело место в течение последней минуты, выводится сообщение. Затем процесс с помощью функции signal делает распоряжение принимать сигналы тревоги, с помощью функции alarm задает интервал между сигналами в 60 секунд и с помощью функции pause приостанавливает свое выполнение до момента получения сигнала. Через 60 се- кунд сигнал поступает, ядро подготавливает стек задачи к вызову функции об- работки сигнала wakeup, функция возвращает управление на оператор, следующий за вызовом функции pause, и процесс исполняет цикл вновь. Все перечисленные функции работы с временем протекания процесса объеди- няет то, что они опираются на показания системных часов (таймера). Обрабаты- вая прерывания по таймеру, ядро обращается к различным таймерным счетчикам и инициирует соответствующее действие.

    8.3 ТАЙМЕР

В функции программы обработки прерываний по таймеру входит: * перезапуск часов, * вызов на исполнение функций ядра, использующих встроенные часы, * поддержка возможности профилирования выполнения процессов в режимах ядра и задачи; * сбор статистики о системе и протекающих в ней процессах, * слежение за временем, * посылка процессам сигналов "будильника" по запросу, * периодическое возобновление процесса подкачки (см. следующую главу), * управление диспетчеризацией процессов. Некоторые из функций реализуются при каждом прерывании по таймеру, дру- гие - по прошествии нескольких таймерных тиков. Программа обработки прерыва- 243 ний по таймеру запускается с высоким приоритетом обращения к процессору, не допуская во время работы возникновения других внешних событий (таких как прерывания от периферийных устройств). Поэтому программа обработки прерыва- ний по таймеру работает очень быстро, за максимально-короткое время пробегая свои критические отрезки, которые должны выполняться без прерываний со стороны других процессов. Алгоритм обработки прерываний по таймеру приве- ден на Рисунке 8.9. +------------------------------------------------------------+ | #include | | #include | | #include | | | | main(argc,argv) | | int argc; | | char *argv[]; | | { | | extern unsigned alarm(); | | extern wakeup(); | | struct stat statbuf; | | time_t axtime; | | | | if (argc != 2) | | { | | printf("только 1 аргумент\n"); | | exit(); | | } | | | | axtime = (time_t) 0; | | for (;;) | | { | | /* получение значения времени доступа к файлу */ | | if (stat(argv[1],&statbuf) == -1) | | { | | printf("файла с именем %s нет\n",argv[1]); | | exit(); | | } | | if (axtime != statbuf.st_atime) | | { | | printf("к файлу %s было обращение\n",argv[1]); | | axtime = statbuf.st_atime; | | } | | signal(SIGALRM,wakeup); /* подготовка к приему | | сигнала */ | | alarm(60); | | pause(); /* приостанов до получения сигнала */| | } | | } | | | | wakeup() | | { | | } | +------------------------------------------------------------+ Рисунок 8.8. Программа, использующая системную функцию alarm 244 +------------------------------------------------------------+ | алгоритм clock | | входная информация: отсутствует | | выходная информация: отсутствует | | { | | перезапустить часы; /* чтобы они снова посылали преры-| | вания */ | | если (таблица ответных сигналов не пуста) | | { | | установить время для ответных сигналов; | | запустить функцию callout, если время истекло; | | } | | если (профилируется выполнение в режиме ядра) | | запомнить значение счетчика команд в момент прерыва-| | ния; | | если (профилируется выполнение в режиме задачи) | | запомнить значение счетчика команд в момент прерыва-| | ния; | | собрать статистику о самой системе; | | собрать статистику о протекающих в системе процессах; | | выверить значение продолжительности ИЦП процессом; | | если (прошла 1 секунда или более и исполняется отрезок,| | не являющийся критическим) | | { | | для (всех процессов в системе) | | { | | установить "будильник", если он активен; | | выверить значение продолжительности ИЦП; | | если (процесс будет исполняться в режиме задачи)| | выверить приоритет процесса; | | } | | возобновить в случае необходимости выполнение про- | | цесса подкачки; | | } | | } | +------------------------------------------------------------+ Рисунок 8.9. Алгоритм обработки прерываний по таймеру

    8.3.1 Перезапуск часов

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

    8.3.2 Внутренние системные тайм-ауты

Некоторым из процедур ядра, в частности драйверам устройств и сетевым протоколам, требуется вызов функций ядра в режиме реального времени. Напри- мер, процесс может перевести терминал в режим ввода без обработки символов, при котором ядро выполняет запросы пользователя на чтение с терминала через фиксированные промежутки времени, не дожидаясь, когда пользователь нажмет клавишу "возврата каретки" (см. раздел 10.3.3). Ядро хранит всю необходимую информацию в таблице ответных сигналов (Рисунок 8.9), в том числе имя функ- ции, запускаемой по истечении интервала времени, параметр, передаваемый этой функции, а также продолжительность интервала (в таймерных тиках) до момента 245 запуска функции. Пользователь не имеет возможности напрямую контролировать записи в таб- лице ответных сигналов; для работы с ними существуют различные системные ал- горитмы. Ядро сортирует записи в этой таблице в соответствии с величиной ин- тервала до момента запуска функций. В связи с этим для каждой записи таблицы запоминается не общая продолжительность интервала, а только промежуток вре- мени между моментами запуска данной и предыдущей функций. Общая продолжи- тельность интервала до момента запуска функции складывается из промежутков времени между моментами запуска всех функций, начиная с первой и вплоть до текущей. Функция Время до запуска Функция Время до запуска +----------------------------+ +----------------------------+ | a() -2 | | a() -2 | +----------------------------+ +----------------------------+ | b() 3 | | b() 3 | +----------------------------+ +----------------------------+ | c() 10 | | f() 2 | +----------------------------+ +----------------------------+ | c() 8 | +----------------------------+ До После Рисунок 8.10. Включение новой записи в таблицу ответных сигналов На Рисунке 8.10 приведен пример добавления новой записи в таблицу ответ- ных сигналов. (К отрицательному значению поля "время до запуска" для функции a мы вернемся несколько позже). Создавая новую запись, ядро отводит для нее надлежащее место и соответствующим образом переустанавливает значение поля "время до запуска" в записи, следующей за добавляемой. Судя по рисунку, ядро собирается запустить функцию f через 5 таймерных тиков: оно отводит место для нее в таблице сразу после функции b и заносит в поле "время до запуска" значение, равное 2 (тогда сумма значений этих полей для функций b и f соста- вит 5), и меняет "время до запуска" функции c на 8 (при этом функция c все равно запускается через 13 таймерных тиков). В одних версиях ядро пользуется связным списком указателей на записи таблицы ответных сигналов, в других - меняет положение записей при корректировке таблицы. Последний способ требует значительно меньших издержек при условии, что ядро не будет слишком часто обращаться к таблице. При каждом поступлении прерывания по таймеру программа обработки преры- вания проверяет наличие записей в таблице ответных сигналов и в случае их обнаружения уменьшает значение поля "время до запуска" в первой записи. Спо- соб хранения продолжительности интервалов до момента запуска каждой функции, выбранный ядром, позволяет, уменьшив значение поля "время до запуска" в од- ной только первой записи, соответственно уменьшить продолжительность интер- вала до момента запуска функций, описанных во всех записях таблицы. Если в указанном поле первой записи хранится отрицательное или нулевое значение, соответствующую функцию следует запустить. Программа обработки прерываний по таймеру не запускает функцию немедленно, таким образом она не блокирует воз- никновение последующих прерываний данного типа. Текущий приоритет работы процессора вроде бы не позволяет таким прерываниям вмешиваться в выполнение процесса, однако ядро не имеет представления о том, сколько времени потребу- ется на исполнение функции. Казалось бы, если функция выполняется дольше од- ного таймерного тика, все последующие прерывания должны быть заблокированы. Вместо этого, программа обработки прерываний в типичной ситуации оформляет вызов функции как "программное прерывание", порождаемое выполнением отдель- ной машинной команды. Поскольку среди всех прерываний программные прерывания имеют самый низкий приоритет, они блокируются, пока ядро не закончит обра- 246 ботку всех остальных прерываний. С момента завершения подготовки к запуску функции и до момента возникновения вызываемого запуском функции программного прерывания может произойти множество прерываний, в том числе и программных, в таком случае в поле "время до запуска", принадлежащее первой записи табли- цы, будет занесено отрицательное значение. Когда же наконец программное пре- рывание происходит, программа обработки прерываний убирает из таблицы все записи с истекшими значениями полей "время до запуска" и вызывает соответст- вующую функцию. Поскольку в указанном поле в начальных записях таблицы может храниться отрицательное или нулевое значение, программа обработки прерываний должна найти в таблице первую запись с положительным значением поля и уменьшить его. Пусть, например, функции a соответствует "время до запуска", равное -2 (Рисунок 8.10), то есть перед тем, как функция a была выбрана на выполнение, система получила 2 прерывания по таймеру. При условии, что функция b 2 тика назад уже была в таблице, ядро пропускает запись, соответствующую функции a, и уменьшает значение поля "время до запуска" для функции b.

    8.3.3 Построение профиля

Построение профиля ядра включает в себя измерение продолжительности вы- полнения системы в режиме задачи против режима ядра, а также продолжитель- ности выполнения отдельных процедур ядра. Драйвер параметров ядра следит за относительной эффективностью работы модулей ядра, замеряя параметры работы системы в момент прерывания по таймеру. Драйвер параметров имеет список ад- ресов ядра (главным образом, функций ядра); эти адреса ранее были загружены процессом путем обращения к драйверу параметров. Если построение профиля яд- ра возможно, программа обработки прерывания по таймеру запускает подпрограм- му обработки прерываний, принадлежащую драйверу параметров, которая опреде- ляет, в каком из режимов - ядра или задачи - работал процессор в момент пре- рывания. Если процессор работал в режиме задачи, система построения профиля увеличивает значение параметра, описывающего продолжительность выполнения в режиме задачи, если же процессор работал в режиме ядра, система увеличивает значение внутреннего счетчика, соответствующего счетчику команд. Пользова- тельские процессы могут обращаться к драйверу параметров, чтобы получить значения параметров ядра и различную статистическую информацию. +--------------------------------+ | Алгоритм Адрес Счетчик | | | | bread 100 5 | | breada 150 0 | | bwrite 200 0 | | brelse 300 2 | | getblk 400 1 | | user - 2 | +--------------------------------+ Рисунок 8.11. Адреса некоторых алгоритмов ядра На Рисунке 8.11 приведены гипотетические адреса некоторых процедур ядра. Пусть в результате 10 измерений, проведенных в моменты поступления прерыва- ний по таймеру, были получены следующие значения счетчика команд: 110, 330, 145, адрес в пространстве задачи, 125, 440, 130, 320, адрес в пространстве задачи и 104. Ядро сохранит при этом те значения, которые показаны на рисун- ке. Анализ этих значений показывает, что система провела 20% своего времени в режиме задачи (user) и 50% времени потратила на выполнение алгоритма bread в режиме ядра. 247 Если измерение параметров ядра выполняется в течение длительного периода времени, результаты измерений приближаются к истинной картине использования системных ресурсов. Тем не менее, описываемый механизм не учитывает время, потраченное на обработку прерываний по таймеру и выполнение процедур, блоки- рующих поступление прерываний данного типа, поскольку таймер не может преры- вать выполнение критических отрезков программ и, таким образом, не может в это время обращаться к подпрограмме обработки прерываний драйвера парамет- ров. В этом недостаток описываемого механизма, ибо критические отрезки прог- рамм ядра чаще всего наиболее важны для измерений. Следовательно, результаты измерения параметров ядра содержат определенную долю приблизительности. Уай- нбергер [Weinberger 84] описал механизм включения счетчиков в главных блоках программы, таких как "if-then" и "else", с целью повышения точности измере- ния частоты их выполнения. Однако, данный механизм увеличивает время счета программ на 50-200%, поэтому его использование в качестве постоянного меха- низма измерения параметров ядра нельзя признать рациональным. На пользовательском уровне для измерения параметров выполнения процессов можно использовать системную функцию profil: profil(buff,bufsize,offset,scale); где buff - адрес массива в пространстве задачи, bufsize - размер массива, offset - виртуальный адрес подпрограммы пользователя (обычно, первой по сче- ту), scale - способ отображения виртуальных адресов задачи на адрес массива. Ядро трактует аргумент "scale" как двоичную дробь с фиксированной точкой слева. Так, например, значение аргумента в шестнадцатиричной системе счисле- ния, равное Oxffff, соответствует однозначному отображению счетчика команд на адреса массива, значение, равное Ox7fff, соответствует размещению в одном слове массива buff двух адресов программы, Ox3fff - четырех адресов програм- мы и т.д. Ядро хранит параметры, передаваемые при вызове системной функции, в пространстве процесса. Если таймер прерывает выполнение процесса тогда, когда он находится в режиме задачи, программа обработки прерываний проверяет значение счетчика команд в момент прерывания, сравнивает его со значением аргумента offset и увеличивает содержимое ячейки памяти, адрес которой явля- ется функцией от bufsize и scale. Рассмотрим в качестве примера программу, приведенную на Рисунке 8.12, измеряющую продолжительность выполнения функций f и g. Сначала процесс, ис- пользуя системную функцию signal, делает указание при получении сигнала о прерывании вызывать функцию theend, затем он вычисляет диапазон адресов программы, в пределах которых будет производиться измерение продолжительнос- ти (начиная с адреса функции main и кончая адресом функции theend), и, нако- нец, запускает функцию profil, сообщая ядру о том, что он собира- ется начать измерение. В результате выполнения программы в течение 10 секунд на несильно загруженной машине AT&T 3B20 были получены данные, представлен- ные на Рисунке 8.13. Адрес функции f превышает адрес начала профилирования на 204 байта; поскольку текст функции f имеет размер 12 байт, а размер цело- го числа в машине AT&T 3B20 равен 4 байтам, адреса функции f отображаются на элементы массива buf с номерами 51, 52 и 53. По такому же принципу адреса функции g отображаются на элементы buf c номерами 54, 55 и 56. Элементы buf с номерами 46, 48 и 49 предназначены для адресов, принадлежащих циклу функ- ции main. В обычном случае диапазон адресов, в пределах которого выполняется измерение параметров, определяется в результате обращения к таблице иденти- фикаторов для данной программы, где указываются адреса программных секций. Пользователи сторонятся функции profil из-за того, что она кажется им слиш- ком сложной; вместо нее они используют при компиляции программ на языке Си параметр, сообщающий компилятору о необходимости сгенерировать код, следящий за ходом выполнения процессов. 248 +------------------------------------------------------------+ | #include | | int buffer[4096]; | | main() | | { | | int offset,endof,scale,eff,gee,text; | | extern theend(),f(),g(); | | signal(SIGINT,theend); | | endof = (int) theend; | | offset = (int) main; | | /* вычисляется количество слов в тексте программы */ | | text = (endof - offset + sizeof(int) - 1)/sizeof(int); | | scale = Oxffff; | | printf | | ("смещение до начала %d до конца %d длина текста %d\n",| | offset,endof,text); | | eff = (int) f; | | gee = (int) g; | | printf("f %d g %d fdiff %d gdiff %d\n",eff,gee, | | eff-offset,gee-offset); | | profil(buffer,sizeof(int)*text,offset,scale); | | for (;;) | | { | | f(); | | g(); | | } | | } | | f() | | { | | } | | g() | | { | | } | | theend() | | { | | int i; | | for (i = 0; i < 4096; i++) | | if (buffer[i]) | | printf("buf[%d] = %d\n",i,buffer[i]); | | exit(); | | } | +------------------------------------------------------------+ Рисунок 8.12. Программа, использующая системную функцию profil +------------------------------------------------------+ | смещение до начала 212 до конца 440 длина текста 57 | | f 416 g 428 fdiff 204 gdiff 216 | | buf[46] = 50 | | buf[48] = 8585216 | | buf[49] = 151 | | buf[51] = 12189799 | | buf[53] = 65 | | buf[54] = 10682455 | | buf[56] = 67 | +------------------------------------------------------+ Рисунок 8.13. Пример результатов выполнения программы, ис- пользующей системную функцию profil 249

    8.3.4 Учет и статистика

В момент поступления прерывания по таймеру система может выполняться в режиме ядра или задачи, а также находиться в состоянии простоя (бездейст- вия). Состояние простоя означает, что все процессы приостановлены в ожидании наступления события. Для каждого состояния процессора ядро имеет внутренние счетчики, устанавливаемые при каждом прерывании по таймеру. Позже пользова- тельские процессы могут проанализировать накопленную ядром статистическую информацию. В пространстве каждого процесса имеются два поля для записи продолжи- тельности времени, проведенного процессом в режиме ядра и задачи. В ходе об- работки прерываний по таймеру ядро корректирует значение поля, соответствую- щего текущему режиму выполнения процесса. Процессы-родители собирают статис- тику о своих потомках при выполнении функции wait, беря за основу информа- цию, поступающую от завершающих свое выполнение потомков. В пространстве каждого процесса имеется также одно поле для ведения уче- та использования памяти. В ходе обработки прерывания по таймеру ядро вычис- ляет общий объем памяти, занимаемый текущим процессом, исходя из размера частных областей процесса и его долевого участия в использовании разделяемых областей памяти. Если, например, процесс использует области данных и стека размером 25 и 40 Кбайт, соответственно, и разделяет с четырьмя другими про- цессами одну область команд размером 50 Кбайт, ядро назначает процессу 75 Кбайт памяти (50К/5 + 25К + 40К). В системе с замещением страниц ядро вычис- ляет объем используемой памяти путем подсчета числа используемых в каждой области страниц. Таким образом, если прерываемый процесс имеет две частные области и еще одну область разделяет с другим процессом, ядро назначает ему столько страниц памяти, сколько содержится в этих частных областях, плюс по- ловину страниц, принадлежащих разделяемой области. Вся указанная информация отражается в учетной записи при завершении процесса и может быть использова- на для расчетов с заказчиками машинного времени.

    8.3.5 Поддержание времени в системе

Ядро увеличивает показание системных часов при каждом прерывании по тай- меру, измеряя время в таймерных тиках от момента загрузки системы. Это зна- чение возвращается процессу через системную функцию time и дает возможность определять общее время выполнения процесса. Время первоначального запуска процесса сохраняется ядром в адресном пространстве процесса при исполнении системной функции fork, в момент завершения процесса это значение вычитается из текущего времени, результат вычитания и составляет реальное время выпол- нения процесса. В другой переменной таймера, устанавливаемой с помощью сис- темной функции stime и корректируемой раз в секунду, хранится календарное время.

    8.4 ВЫВОДЫ

В настоящей главе был описан основной алгоритм диспетчеризации процессов в системе UNIX. С каждым процессом в системе связывается приоритет планиро- вания, значение которого появляется в момент перехода процесса в состояние приостанова и периодически корректируется программой обработки прерываний по таймеру. Приоритет, присваиваемый процессу в момент перехода в состояние приостанова, имеет значение, зависящее от того, какой из алгоритмов ядра ис- полнялся процессом в этот момент. Значение приоритета, присваиваемое процес- су во время выполнения программой обработки прерываний по таймеру (или в тот момент, когда процесс возвращается из режима ядра в режим задачи), зависит от того, сколько времени процесс занимал ЦП: процесс получает низкий приори- тет, если он обращался к ЦП, и высокий - в противном случае. Системная функ- ция nice дает процессу возможность влиять на собственный приоритет путем до- бавления параметра, участвующего в пересчете приоритета. 250 В главе были также рассмотрены системные функции, связанные с временем выполнения системы и протекающих в ней процессов: с установкой и получением системного времени, получением времени выполнения процессов и установкой сигналов "будильника". Кроме того, описаны функции программы обработки пре- рываний по таймеру, которая следит за временем в системе, управляет таблицей ответных сигналов, собирает статистику, а также подготавливает запуск плани- ровщика процессов, программы подкачки и "сборщика" страниц. Программа под- качки и "сборщик" страниц являются объектами рассмотрения в следующей главе.

    8.5 УПРАЖНЕНИЯ

1. При переводе процессов в состояние приостанова ядро назначает процессу, ожидающему снятия блокировки с индекса, более высокий приоритет по сравнению с процессом, ожидающим освобождения буфера. Точно так же, процессы, ожидающие ввода с терминала, получают более высокий приоритет по сравнению с процессами, ожидающими возможности производить вывод на терминал. Объясните причины такого поведения ядра. *2. В алгоритме обработки прерываний по таймеру предусмотрен пересчет прио- ритетов и перезапуск процессов на выполнение с интервалом в 1 секунду. Придумайте алгоритм, в котором интервал перезапуска динамически меняет- ся в зависимости от степени загрузки системы. Перевесит ли выигрыш уси- лия по усложнению алгоритма ? 3. В шестой редакции системы UNIX для расчета продолжительности ИЦП теку- щим процессом используется следующая формула: decay(ИЦП) = max (пороговый приоритет, ИЦП-10); а в седьмой редакции: decay(ИЦП) = .8 * ИЦП; Приоритет процесса в обеих редакциях вычисляется по формуле: приоритет = ИЦП/16 + (базовый уровень приоритета); Повторите пример на Рисунке 8.4, используя приведенные формулы. 4. Проделайте еще раз пример на Рисунке 8.4 с семью процессами вместо трех, а затем измените частоту прерываний по таймеру с 60 на 100 преры- ваний в секунду. Прокомментируйте результат. 5. Разработайте схему, в которой система накладывает ограничение на про- должительность выполнения процесса, при превышении которого процесс за- вершается. Каким образом пользователь должен отличать такой процесс от процессов, для которых не должны существовать подобные ограничения ? Каким образом должна работать схема, если единственным условием являет- ся ее запуск из shell'а ? 6. Когда процесс выполняет системную функцию wait и обнаруживает прекра- тившего существование потомка, ядро приплюсовывает к его ИЦП значение поля ИЦП потомка. Чем объясняется такое "наказание" процесса-родителя ? 7. Команда nice запускает последующую команду с передачей ей указанного значения, например: nice 6 nroff -mm big_memo > output Напишите на языке Си программу, реализующую команду nice. 8. Проследите на примере Рисунка 8.4, каким образом будет осуществляться диспетчеризация процессов в том случае, если значение, передаваемое функцией nice для процесса A, равно 5 или -5. 9. Проведите эксперимент с системной функцией renice x y, где x - код идентификации процесса (активного), а y - новое значение nice для ука- занного процесса. 10. Вернемся к примеру, приведенному на Рисунке 8.6. Предположим, что груп- пе, в которую входит процесс A, выделяется 33% процессорного времени, а группе, в которую входит процесс B, - 66% процессорного времени. В ка- кой последовательности будут исполняться процессы ? Обобщите алгоритм вычисления приоритетов таким образом, чтобы значение группового ИЦП ус- реднялось. 251 11. Выполните команду date. Команда без аргументов выводит текущую дату: указав аргумент, например: date mmddhhmmyy (супер)пользователь может установить текущую дату в системе (соответственно, месяц, число, часы, минуты и год). Так, date 0911205084 устанавливает в качестве текущего времени 11 сентября 1984 года 8:50 пополудни. 12. В программах можно использовать функцию пользовательского уровня sleep: sleep(seconds); с помощью которой выполнение программы приостанавливается на указанное число секунд. Разработайте ее алгоритм, в котором используйте системные функции alarm и pause. Что произойдет, если процесс вызовет функцию alarm раньше функции sleep ? Рассмотрите две возможности: 1) действие ранее вызванной функции alarm истекает в то время, когда процесс нахо- дится в состоянии приостанова, 2) действие ранее вызванной функции alarm истекает после завершения функции sleep. *13. Обратимся еще раз к последней проблеме. Ядро может выполнить переключе- ние контекста во время исполнения функции sleep между вызовами alarm и pause. Тогда есть опасность, что процесс получит сигнал alarm до того, как вызовет функцию pause. Что произойдет в этом случае ? Как вовремя распознать эту ситуацию ? 252
Last-modified: Thu, 12-Feb-98 07:20:11 GMT