Geum.ru

The design of the unix operating system by Maurice J

Вид материалаРеферат
Подобный материал:
1   ...   30   31   32   33   34   35   36   37   ...   55

│ выверить приоритет процесса; │

│ } │

│ возобновить в случае необходимости выполнение про- │

│ цесса подкачки; │

│ } │

│ } │

L-------------------------------------------------------------


Рисунок 8.9. Алгоритм обработки прерываний по таймеру


пробегая свои критические отрезки, которые должны выполняться без

прерываний со стороны других процессов. Алгоритм обработки преры-

ваний по таймеру приведен на Рисунке 8.9.


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


В большинстве машин после получения прерывания по таймеру

требуется программными средствами произвести перезапуск часов,

чтобы они по прошествии интервала времени могли вновь прерывать

работу процессора. Такие средства являются машинно-зависимыми и

мы их рассматривать не будем.


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


Некоторым из процедур ядра, в частности драйверам устройств и

сетевым протоколам, требуется вызов функций ядра в режиме реаль-

ного времени. Например, процесс может перевести терминал в режим

ввода без обработки символов, при котором ядро выполняет запросы

пользователя на чтение с терминала через фиксированные промежутки

времени, не дожидаясь, когда пользователь нажмет клавишу "возвра-

та каретки" (см. раздел 10.3.3). Ядро хранит всю необходимую ин-

формацию в таблице ответных сигналов (Рисунок 8.9), в том числе

имя функции, запускаемой по истечении интервала времени, пара-

метр, передаваемый этой функции, а также продолжительность интер-

вала (в таймерных тиках) до момента запуска функции.

Пользователь не имеет возможности напрямую контролировать за-

писи в таблице ответных сигналов; для работы с ними существуют

различные системные алгоритмы. Ядро сортирует записи в этой таб-

лице в соответствии с величиной интервала до момента запуска

функций. В связи с этим для каждой записи таблицы запоминается не

общая продолжительность интервала, а только промежуток времени

между моментами запуска данной и предыдущей функций. Общая про-

должительность интервала до момента запуска функции складывается

из промежутков времени между моментами запуска всех функций, на-

чиная с первой и вплоть до текущей.


Функция Время до запуска Функция Время до запуска

-----------------------------┐ -----------------------------┐

│ a() -2 │ │ a() -2 │

+----------------------------+ +----------------------------+

│ b() 3 │ │ b() 3 │

+----------------------------+ +----------------------------+

│ c() 10 │ │ f() 2 │

L----------------------------- +----------------------------+

│ c() 8 │

L-----------------------------

До После


Рисунок 8.10. Включение новой записи в таблицу ответных сиг-

налов


На Рисунке 8.10 приведен пример добавления новой записи в

таблицу ответных сигналов. (К отрицательному значению поля "время

до запуска" для функции a мы вернемся несколько позже). Создавая

новую запись, ядро отводит для нее надлежащее место и соответс-

твующим образом переустанавливает значение поля "время до запус-

ка" в записи, следующей за добавляемой. Судя по рисунку, ядро со-

бирается запустить функцию f через 5 таймерных тиков: оно отводит

место для нее в таблице сразу после функции b и заносит в поле

"время до запуска" значение, равное 2 (тогда сумма значений этих

полей для функций b и f составит 5), и меняет "время до запуска"

функции c на 8 (при этом функция c все равно запускается через 13

таймерных тиков). В одних версиях ядро пользуется связным списком

указателей на записи таблицы ответных сигналов, в других - меняет

положение записей при корректировке таблицы. Последний способ

требует значительно меньших издержек при условии, что ядро не бу-

дет слишком часто обращаться к таблице.

При каждом поступлении прерывания по таймеру программа обра-

ботки прерывания проверяет наличие записей в таблице ответных

сигналов и в случае их обнаружения уменьшает значение поля "время

до запуска" в первой записи. Способ хранения продолжительности

интервалов до момента запуска каждой функции, выбранный ядром,

позволяет, уменьшив значение поля "время до запуска" в одной

только первой записи, соответственно уменьшить продолжительность

интервала до момента запуска функций, описанных во всех записях

таблицы. Если в указанном поле первой записи хранится отрицатель-

ное или нулевое значение, соответствующую функцию следует запус-

тить. Программа обработки прерываний по таймеру не запускает

функцию немедленно, таким образом она не блокирует возникновение

последующих прерываний данного типа. Текущий приоритет работы

процессора вроде бы не позволяет таким прерываниям вмешиваться в

выполнение процесса, однако ядро не имеет представления о том,

сколько времени потребуется на исполнение функции. Казалось бы,

если функция выполняется дольше одного таймерного тика, все пос-

ледующие прерывания должны быть заблокированы. Вместо этого,

программа обработки прерываний в типичной ситуации оформляет вы-

зов функции как "программное прерывание", порождаемое выполнением

отдельной машинной команды. Поскольку среди всех прерываний прог-

раммные прерывания имеют самый низкий приоритет, они блокируются,

пока ядро не закончит обработку всех остальных прерываний. С мо-

мента завершения подготовки к запуску функции и до момента воз-

никновения вызываемого запуском функции программного прерывания

может произойти множество прерываний, в том числе и программных,

в таком случае в поле "время до запуска", принадлежащее первой

записи таблицы, будет занесено отрицательное значение. Когда же

наконец программное прерывание происходит, программа обработки

прерываний убирает из таблицы все записи с истекшими значениями

полей "время до запуска" и вызывает соответствующую функцию.

Поскольку в указанном поле в начальных записях таблицы может

храниться отрицательное или нулевое значение, программа обработки

прерываний должна найти в таблице первую запись с положительным

значением поля и уменьшить его. Пусть, например, функции 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 │

L---------------------------------


Рисунок 8.11. Адреса некоторых алгоритмов ядра


На Рисунке 8.11 приведены гипотетические адреса некоторых

процедур ядра. Пусть в результате 10 измерений, проведенных в мо-

менты поступления прерываний по таймеру, были получены следующие

значения счетчика команд: 110, 330, 145, адрес в пространстве за-

дачи, 125, 440, 130, 320, адрес в пространстве задачи и 104. Ядро

сохранит при этом те значения, которые показаны на рисунке. Ана-

лиз этих значений показывает, что система провела 20% своего вре-

мени в режиме задачи (user) и 50% времени потратила на выполнение

алгоритма bread в режиме ядра.

Если измерение параметров ядра выполняется в течение длитель-

ного периода времени, результаты измерений приближаются к истин-

ной картине использования системных ресурсов. Тем не менее,

описываемый механизм не учитывает время, потраченное на обработку

прерываний по таймеру и выполнение процедур, блокирующих поступ-

ление прерываний данного типа, поскольку таймер не может преры-

вать выполнение критических отрезков программ и, таким образом,

не может в это время обращаться к подпрограмме обработки прерыва-

ний драйвера параметров. В этом недостаток описываемого механиз-

ма, ибо критические отрезки программ ядра чаще всего наиболее

важны для измерений. Следовательно, результаты измерения парамет-

ров ядра содержат определенную долю приблизительности. Уайнбергер

[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.


-------------------------------------------------------------┐

│ #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(); │

│ } │

L-------------------------------------------------------------


Рисунок 8.12. Программа, использующая системную функцию profil


Рассмотрим в качестве примера программу, приведенную на Ри-

сунке 8.12, измеряющую продолжительность выполнения функций f и

g. Сначала процесс, используя системную функцию signal, делает

указание при получении сигнала о прерывании вызывать функцию

theend, затем он вычисляет диапазон адресов программы, в пределах

которых будет производиться измерение продолжительности (начиная

с адреса функции main и кончая адресом функции theend), и, нако-

нец, запускает функцию 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 │

L-------------------------------------------------------


Рисунок 8.13. Пример результатов выполнения программы, ис-

пользующей системную функцию 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 из-за того, что она кажет-

ся им слишком сложной; вместо нее они используют при компиляции

программ на языке Си параметр, сообщающий компилятору о необходи-

мости сгенерировать код, следящий за ходом выполнения процессов.


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


В момент поступления прерывания по таймеру система может вы-

полняться в режиме ядра или задачи, а также находиться в состоя-

нии простоя (бездействия). Состояние простоя означает, что все

процессы приостановлены в ожидании наступления события. Для каж-

дого состояния процессора ядро имеет внутренние счетчики, уста-

навливаемые при каждом прерывании по таймеру. Позже пользователь-

ские процессы могут проанализировать накопленную ядром статисти-

ческую информацию.

В пространстве каждого процесса имеются два поля для записи

продолжительности времени, проведенного процессом в режиме ядра и

задачи. В ходе обработки прерываний по таймеру ядро корректирует

значение поля, соответствующего текущему режиму выполнения про-

цесса. Процессы-родители собирают статистику о своих потомках при

выполнении функции wait, беря за основу информацию, поступающую

от завершающих свое выполнение потомков.

В пространстве каждого процесса имеется также одно поле для

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

по таймеру ядро вычисляет общий объем памяти, занимаемый текущим

процессом, исходя из размера частных областей процесса и его до-

левого участия в использовании разделяемых областей памяти. Если,

например, процесс использует области данных и стека размером 25 и

40 Кбайт, соответственно, и разделяет с четырьмя другими процес-

сами одну область команд размером 50 Кбайт, ядро назначает про-

цессу 75 Кбайт памяти (50К/5 + 25К + 40К). В системе с замещением

страниц ядро вычисляет объем используемой памяти путем подсчета

числа используемых в каждой области страниц. Таким образом, если

прерываемый процесс имеет две частные области и еще одну область

разделяет с другим процессом, ядро назначает ему столько страниц

памяти, сколько содержится в этих частных областях, плюс половину

страниц, принадлежащих разделяемой области. Вся указанная инфор-

мация отражается в учетной записи при завершении процесса и может

быть использована для расчетов с заказчиками машинного времени.


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


Ядро увеличивает показание системных часов при каждом преры-

вании по таймеру, измеряя время в таймерных тиках от момента заг-

рузки системы. Это значение возвращается процессу через системную

функцию time и дает возможность определять общее время выполнения

процесса. Время первоначального запуска процесса сохраняется яд-

ром в адресном пространстве процесса при исполнении системной

функции fork, в момент завершения процесса это значение вычитает-

ся из текущего времени, результат вычитания и составляет реальное

время выполнения процесса. В другой переменной таймера, устанав-

ливаемой с помощью системной функции stime и корректируемой раз в

секунду, хранится календарное время.


8.4 ВЫВОДЫ


В настоящей главе был описан основной алгоритм диспетчериза-

ции процессов в системе UNIX. С каждым процессом в системе связы-

вается приоритет планирования, значение которого появляется в мо-

мент перехода процесса в состояние приостанова и периодически

корректируется программой обработки прерываний по таймеру. Прио-

ритет, присваиваемый процессу в момент перехода в состояние при-

останова, имеет значение, зависящее от того, какой из алгоритмов

ядра исполнялся процессом в этот момент. Значение приоритета,

присваиваемое процессу во время выполнения программой обработки

прерываний по таймеру (или в тот момент, когда процесс возвраща-

ется из режима ядра в режим задачи), зависит от того, сколько

времени процесс занимал ЦП: процесс получает низкий приоритет,

если он обращался к ЦП, и высокий - в противном случае. Системная

функция nice дает процессу возможность влиять на собственный при-

оритет путем добавления параметра, участвующего в пересчете прио-

ритета.

В главе были также рассмотрены системные функции, связанные с

временем выполнения системы и протекающих в ней процессов: с ус-

тановкой и получением системного времени, получением времени вы-

полнения процессов и установкой сигналов "будильника". Кроме то-

го, описаны функции программы обработки прерываний по таймеру,

которая следит за временем в системе, управляет таблицей ответных

сигналов, собирает статистику, а также подготавливает запуск пла-

нировщика процессов, программы подкачки и "сборщика" страниц.

Программа подкачки и "сборщик" страниц являются объектами расс-

мотрения в следующей главе.


8.5 УПРАЖНЕНИЯ


1. При переводе процессов в состояние приостанова ядро назнача-

ет процессу, ожидающему снятия блокировки с индекса, более

высокий приоритет по сравнению с процессом, ожидающим осво-

бождения буфера. Точно так же, процессы, ожидающие ввода с

терминала, получают более высокий приоритет по сравнению с

процессами, ожидающими возможности производить вывод на тер-