Страница:
времени выделяется процессам группы, тем выше значение этого показателя и
ниже приоритет.
В качестве примера рассмотрим две группы процессов (Рисунок 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, и процесс исполняет цикл вновь.
Все перечисленные функции работы с временем протекания процесса объеди-
няет то, что они опираются на показания системных часов (таймера). Обрабаты-
вая прерывания по таймеру, ядро обращается к различным таймерным счетчикам и
инициирует соответствующее действие.
В функции программы обработки прерываний по таймеру входит:
* перезапуск часов,
* вызов на исполнение функций ядра, использующих встроенные часы,
* поддержка возможности профилирования выполнения процессов в режимах ядра
и задачи;
* сбор статистики о системе и протекающих в ней процессах,
* слежение за временем,
* посылка процессам сигналов "будильника" по запросу,
* периодическое возобновление процесса подкачки (см. следующую главу),
* управление диспетчеризацией процессов.
Некоторые из функций реализуются при каждом прерывании по таймеру, дру-
гие - по прошествии нескольких таймерных тиков. Программа обработки прерыва-
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. Алгоритм обработки прерываний по таймеру
В большинстве машин после получения прерывания по таймеру требуется
программными средствами произвести перезапуск часов, чтобы они по прошествии
интервала времени могли вновь прерывать работу процессора. Такие средства
являются машинно-зависимыми и мы их рассматривать не будем.
Некоторым из процедур ядра, в частности драйверам устройств и сетевым
протоколам, требуется вызов функций ядра в режиме реального времени. Напри-
мер, процесс может перевести терминал в режим ввода без обработки символов,
при котором ядро выполняет запросы пользователя на чтение с терминала через
фиксированные промежутки времени, не дожидаясь, когда пользователь нажмет
клавишу "возврата каретки" (см. раздел 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.
Построение профиля ядра включает в себя измерение продолжительности вы-
полнения системы в режиме задачи против режима ядра, а также продолжитель-
ности выполнения отдельных процедур ядра. Драйвер параметров ядра следит за
относительной эффективностью работы модулей ядра, замеряя параметры работы
системы в момент прерывания по таймеру. Драйвер параметров имеет список ад-
ресов ядра (главным образом, функций ядра); эти адреса ранее были загружены
процессом путем обращения к драйверу параметров. Если построение профиля яд-
ра возможно, программа обработки прерывания по таймеру запускает подпрограм-
му обработки прерываний, принадлежащую драйверу параметров, которая опреде-
ляет, в каком из режимов - ядра или задачи - работал процессор в момент пре-
рывания. Если процессор работал в режиме задачи, система построения профиля
увеличивает значение параметра, описывающего продолжительность выполнения в
режиме задачи, если же процессор работал в режиме ядра, система увеличивает
значение внутреннего счетчика, соответствующего счетчику команд. Пользова-
тельские процессы могут обращаться к драйверу параметров, чтобы получить
значения параметров ядра и различную статистическую информацию.
+--------------------------------+
| Алгоритм Адрес Счетчик |
| |
| 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, делает указание при получении сигнала о
ниже приоритет.
В качестве примера рассмотрим две группы процессов (Рисунок 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, и процесс исполняет цикл вновь.
Все перечисленные функции работы с временем протекания процесса объеди-
няет то, что они опираются на показания системных часов (таймера). Обрабаты-
вая прерывания по таймеру, ядро обращается к различным таймерным счетчикам и
инициирует соответствующее действие.
В функции программы обработки прерываний по таймеру входит:
* перезапуск часов,
* вызов на исполнение функций ядра, использующих встроенные часы,
* поддержка возможности профилирования выполнения процессов в режимах ядра
и задачи;
* сбор статистики о системе и протекающих в ней процессах,
* слежение за временем,
* посылка процессам сигналов "будильника" по запросу,
* периодическое возобновление процесса подкачки (см. следующую главу),
* управление диспетчеризацией процессов.
Некоторые из функций реализуются при каждом прерывании по таймеру, дру-
гие - по прошествии нескольких таймерных тиков. Программа обработки прерыва-
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. Алгоритм обработки прерываний по таймеру
В большинстве машин после получения прерывания по таймеру требуется
программными средствами произвести перезапуск часов, чтобы они по прошествии
интервала времени могли вновь прерывать работу процессора. Такие средства
являются машинно-зависимыми и мы их рассматривать не будем.
Некоторым из процедур ядра, в частности драйверам устройств и сетевым
протоколам, требуется вызов функций ядра в режиме реального времени. Напри-
мер, процесс может перевести терминал в режим ввода без обработки символов,
при котором ядро выполняет запросы пользователя на чтение с терминала через
фиксированные промежутки времени, не дожидаясь, когда пользователь нажмет
клавишу "возврата каретки" (см. раздел 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.
Построение профиля ядра включает в себя измерение продолжительности вы-
полнения системы в режиме задачи против режима ядра, а также продолжитель-
ности выполнения отдельных процедур ядра. Драйвер параметров ядра следит за
относительной эффективностью работы модулей ядра, замеряя параметры работы
системы в момент прерывания по таймеру. Драйвер параметров имеет список ад-
ресов ядра (главным образом, функций ядра); эти адреса ранее были загружены
процессом путем обращения к драйверу параметров. Если построение профиля яд-
ра возможно, программа обработки прерывания по таймеру запускает подпрограм-
му обработки прерываний, принадлежащую драйверу параметров, которая опреде-
ляет, в каком из режимов - ядра или задачи - работал процессор в момент пре-
рывания. Если процессор работал в режиме задачи, система построения профиля
увеличивает значение параметра, описывающего продолжительность выполнения в
режиме задачи, если же процессор работал в режиме ядра, система увеличивает
значение внутреннего счетчика, соответствующего счетчику команд. Пользова-
тельские процессы могут обращаться к драйверу параметров, чтобы получить
значения параметров ядра и различную статистическую информацию.
+--------------------------------+
| Алгоритм Адрес Счетчик |
| |
| 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, делает указание при получении сигнала о