Текст книги "Linux программирование в примерах"

Автор книги: Арнольд Роббинс

сообщить о нарушении

Текущая страница: 45 (всего у книги 55 страниц)

14.3. Более точное время

Системный вызов time() и тип time_t представляют время в секундах в формате отсчета с начала Эпохи. Разрешения в одну секунду на самом деле недостаточно, сегодняшние машины быстры, и часто бывает полезно различать временные интервалы в долях секунды. Начиная с 4.2 BSD, Berkley Unix представил ряд системных вызовов, которые сделали возможным получение и использование времени в долях секунд. Эти вызовы доступны на всех современных системах Unix, включая GNU/Linux.

14.3.1. Время в микросекундах: gettimeofday()

Первой задачей является получение времени дня:

#include

int gettimeofday(struct timeval *tv, void *tz); /* определение POSIX, а не GLIBC */

gettimeofday() позволяет получить время дня.[156]156
  В справочной странице gettimeofday(2) документирована соответствующая функция settimeofday() для использования суперпользователем (root) для установки времени дня всей системы – Примеч. автора.


[Закрыть] В случае успеха возвращается 0, при ошибке -1. Аргументы следующие:

struct timeval *tv

Этот аргумент является указателем на struct timeval, которая вскоре будет описана и в которую система помещает текущее время.

void *tz

Это аргумент больше не используется; он имеет тип void*, поэтому он всегда должен равняться NULL. (Справочная страница описывает, для чего он использовался, а затем утверждает, что он устарел. Прочтите, если интересуетесь подробностями.)

Время представлено структурой struct timeval:

struct timeval {

 long tv_sec; /* секунды */

 long tv_usec; /* микросекунды */

};

Значение tv_sec представляет секунды с начала Эпохи; tv_usec является числом микросекунд в секунде.

Справочная страница GNU/Linux gettimeofday(2) документирует также следующие макросы:

#define timerisset(tvp) ((tvp)->tv_sec || (tvp)->tv_usec)

#define timercmp(tvp, uvp, cmp)

 ((tvp)->tv_sec cmp (uvp)->tv_sec ||

 (tvp)->tv_sec == (uvp)->tv_sec &&

 (tvp)->tv_usec cmp (uvp)->tv_usec)

#define timerclear(tvp) ((tvp)->tv_sec = (tvp)->tv_usec = 0)

Эти макросы работают со значениями struct timeval*; то есть указателями на структуры, и их использование должно быть очевидным из их названий и кода. Особенно интересен макрос timercmp(): третьим аргументом является оператор сравнения для указания вида сравнения. Например, рассмотрим определение того, является ли одна struct timeval меньше другой:

struct timeval t1, t2;

...

if (timercmp(&t1, & t2, <))

 /* t1 меньше, чем t2 */

Макрос развертывается в

((&t1)->tv_sec < (&t2)->tv_sec ||

(&t1)->tv_sec == (&t2)->tv_sec &&

(&t1)->tv_usec < (&t2)->tv_usec)

Это значит: «если t1.tv_sec меньше, чем t2.tv_sec, ИЛИ если они равны и t1.tv_usec меньше, чем t2.tv_usec, тогда…».

14.3.2. Файловое время в микросекундах: utimes()

В разделе 5.5.3 «Изменение временных отметок: utime()» был описан системный вызов utime() для установки времени последнего обращения и изменения данного файла. Некоторые файловые системы хранят эти временные отметки с разрешением в микросекунды (или еще точнее). Такие системы предусматривают системный вызов utimes() (обратите внимание на завершающую s в названии) для установки времени обращения к файлу и его изменения с точностью до микросекунд:

#include /* XSI */

int utimes(char *filename, struct timeval tvp[2]);

Аргумент tvp должен указывать на массив из двух структур struct timeval, значения используются для времени доступа и изменения соответственно. Если tvp равен NULL, система использует текущее время дня.

POSIX обозначает ее как «традиционную» функцию, что означает, что она стандартизуется лишь для поддержки старого кода и не должна использоваться для новых приложений. Главная причина, пожалуй, в том, что нет определенного интерфейса для получения времени доступа и изменения файла в микросекундах; struct stat содержит лишь значения time_t, а не значения struct timeval.

Однако, как упоминалось в разделе 5.4.3 «Только Linux: указание файлового времени повышенной точности», Linux 2.6 (и более поздние версии) действительно предоставляет доступ к временным отметкам с разрешением в наносекунды при помощи функции stat(). Некоторые другие системы (такие, как Solaris) также это делают.[157]157
  К сожалению, по-видимому, в настоящее время нет стандарта для названий членов struct stat, что делает такую операцию непереносимой – Примеч. автора.


[Закрыть] Таким образом, utimes() полезнее, чем кажется на первый взгляд, и несмотря на ее «традиционный» статус, нет причин не использовать ее в своих программах.

14.3.3. Интервальные таймеры: setitimer() и getitimer()

Функция alarm() (см. раздел 10.8.1 «Сигнальные часы: sleep(), alarm() и SIGALRM») организует отправку сигнала SIGALRM после истечения данного числа секунд. Ее предельным разрешением является одна секунда. Здесь также BSD 4.2 ввело функцию и три различных таймера, которые используют время в долях секунды.

Интервальный таймер подобен многократно использующимся сигнальным часам. Вы устанавливаете начальное время, когда он должен «сработать», а также как часто это должно впоследствии повторяться. Оба этих значения используют объекты struct timeval; т.е. они (потенциально) имеют разрешение в микросекундах. Таймер «срабатывает», доставляя сигнал; таким образом, нужно установить для таймера обработчик сигнала, желательно до установки самого таймера.

Существуют три различных таймера, описанных в табл. 14.2.

Таблица 14.2. Интервальные таймеры

ITIMER_REAL	SIGALRM	Работает в реальном режиме
ITIMER_VIRTUAL	SIGVTALRM	Работает, когда процесс выполняется в режиме пользователя
ITIMER_PROF	SIGPROF	Работает, когда процесс выполняется в режиме пользователя или ядра.

Использование первого таймера, ITIMER_REAL, просто. Таймер работает в реальном времени, посылая SIGALRM по истечении заданного количества времени. (Поскольку посылается SIGALRM, нельзя смешивать вызовы setitimer() с вызовами alarm(), а смешивание их с вызовом sleep() также опасно; см. раздел 10.8.1 «Сигнальные часы, sleep(), alarm() и SIGALRM».)

Второй таймер, ITIMER_VIRTUAL, также довольно прост. Он действует, когда процесс исполняется, но лишь при выполнении кода пользователя (приложения) Если процесс заблокирован во время ввода/вывода, например, на диск, или, еще важнее, на терминал, таймер приостанавливается.

Третий таймер, ITIMER_PROF, более специализированный. Он действует все время, пока выполняется процесс, даже если операционная система делает что-нибудь для процесса (вроде ввода/вывода). В соответствии со стандартом POSIX, он «предназначен для использования интерпретаторами при статистическом профилировании выполнения интерпретируемых программ». Установив как для ITIMER_VIRTUAL, так и для ITIMER_PROF идентичные интервалы и сравнивая разницу времени срабатывания двух таймеров, интерпретатор может узнать, сколько времени проводится в системных вызовах для выполняющейся интерпретируемой программы[158]158
  Корректное выполнение профилировки нетривиальная задача, если вы думаете о написании интерпретатора, стоит сначала провести свои исследования – Примеч. автора.


[Закрыть]. (Как сказано, это довольно специализировано.) Двумя системными вызовами являются:

#include /* XSI */

int getitimer(int which, struct itimerval *value);

int setitimer(int which, const struct itimerval *value,

 struct itimerval *ovalue);

Аргумент which является одной из перечисленных ранее именованных констант, указывающих таймер, getitimer() заполняет struct itimerval, на которую указывает value, текущими установками данного таймера, setitimer() устанавливает для данного таймера значение в value. Если имеется ovalue, функция заполняет ее текущим значением таймера. Используйте для ovalue NULL, если не хотите беспокоиться о текущем значении. Обе функции возвращают в случае успеха 0 и -1 при ошибке, struct itimerval состоит из двух членов struct timeval:

struct itimerval {

 struct timeval it_interval; /* следующее значение */

 struct timeval it_value;    /* текущее значение */

};

Прикладным программам не следует ожидать, что таймеры будут с точностью до микросекунд. Справочная страница getitimer(2) дает следующее объяснение:

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

Из этих трех таймеров ITIMER_REAL кажется наиболее полезным. Следующая программа, ch14-timers.c, показывает, как читать данные с терминала, но с тайм-аутом, чтобы программа не зависала на бесконечное время, ожидая ввода:

1  /* ch14-timers.c – демонстрация интервальных таймеров */

2

3  #include

4  #include

5  #include

6  #include

7

8  /* handler – обрабатывает SIGALRM */

9

10 void handler(int signo)

11 {

12  static const char msg[] = "n*** Timer expired, you lose ***n";

13

14  assert(signo == SIGALRM);

15

16  write(2, msg, sizeof(msg) – 1);

17  exit(1);

18 }

19

20 /* main – установить таймер, прочесть данные с тайм-аутом */

21

22 int main(void)

23 {

24  struct itimerval tval;

25  char string[BUFSIZ];

26

27  timerclear(&tval.it_interval); /* нулевой интервал означает не сбрасывать таймер */

28  timerclear(&tval.it_value);

29

30  tval.it_value.tv_sec = 10; /* тайм-аут 10 секунд */

31

32  (void)signal(SIGALRM, handler);

33

34

35  printf("You have ten seconds to enternyour name, rank, and serial number: ");

36  (void)setitimer(ITIMER_REAL, &tval, NULL);

37  if (fgets(string, sizeof string, stdin) != NULL) {

38   (void)setitimer(ITIMER_REAL, NULL, NULL); /* выключить таймер */

39   /* обработать оставшиеся данные, вывод диагностики для иллюстрации */

40   printf("I'm glad you are being cooperative.n");

41  } else

42   printf("nEOF, eh? We won't give up so easily'n");

43

44  exit(0);

45 }

Строки 10–18 представляют обработчик сигнала для SIGALRM; вызов assert() гарантирует, что обработчик сигнала был установлен соответствующим образом. Тело обработчика выводит сообщение и выходит, но оно может делать что-нибудь более подходящее для крупномасштабной программы.

В функции main() строки 27–28 очищают два члена struct timeval структуры struct itimerval.tval. Затем строка 30 устанавливает тайм-аут в 10 секунд. Установка tval.it_interval в 0 означает, что нет повторяющегося сигнала; он срабатывает лишь однажды. Строка 32 устанавливает обработчик сигнала, а строка 34 выводит приглашение.

Строка 36 устанавливает таймер, а строки 37–42 выводят соответствующие сообщения, основываясь на действиях пользователя. Реальная программа выполняла бы в этот момент свою задачу. Важно здесь обратить внимание на строку 38, которая отменяет таймер, поскольку были введены действительные данные.

ЗАМЕЧАНИЕ. Между строками 37 и 38 имеется намеренное состояние гонки. Все дело в том, что если пользователь не вводит строку в течение отведенного таймером времени, будет доставлен сигнал, и обработчик сигнала выведет сообщение «you lose».

Вот три успешных запуска программы:

$ ch14-timers /* Первый запуск, ничего не вводится */

You have ten seconds to enter

your name, rank, and serial number:

*** Timer expired, you lose ***

$ ch14-timers /* Второй запуск, ввод данных */

You have ten seconds to enter

your name, rank, and serial number: Jamas Kirk, Starfleet Captain, 1234

I'm glad you are being cooperative.

$ ch14-timers /* Третий запуск, ввод EOF (^D) */

You have ten seconds to enter

your name, rank, and serial number: ^D

EOF, eh? We won't give up so easily!

POSIX оставляет неопределенным, как интервальные таймеры взаимодействуют с функцией sleep(), если вообще взаимодействуют. GLIBC не использует для реализации sleep() функцию alarm(), поэтому на системах GNU/Linux sleep() не взаимодействует с интервальным таймером. Однако, для переносимых программ, вы не можете делать такое предположение.

14.3.4. Более точные паузы: nanosleep()

Функция sleep() (см. раздел 10.8.1 «Сигнальные часы: sleep(), alarm() и SIGALRM») дает программе возможность приостановиться на указанное число секунд. Но, как мы видели, она принимает лишь целое число секунд, что делает невозможным задержки на короткие периоды, она потенциально может также взаимодействовать с обработчиками SIGALRM. Функция nanosleep() компенсирует эти недостатки:

#include /* POSIX ТМР */

int nanosleep(const struct timespec *req, struct timespec *rem);

Эта функция является частью необязательного расширения POSIX «Таймеры» (TMR). Два аргумента являются запрошенным временем задержки и оставшимся числом времени в случае раннего возвращения (если rem не равен NULL). Оба являются значениями struct timespec:

struct timespec {

 time_t tv_sec; /* секунды */

 long tv_nsec;  /* наносекунды */

};

Значение tv_nsec должно быть в диапазоне от 0 до 999 999 999. Как и в случае со sleep(), время задержки может быть больше запрошенного в зависимости оттого, когда и как ядро распределяет время для исполнения процессов.

В отличие от sleep(), nanosleep() не взаимодействует ни с какими сигналами, делая ее более безопасной и более простой для использования.

Возвращаемое значение равно 0, если выполнение процесса было задержано в течение всего указанного времени. В противном случае оно равно -1, с errno, указывающим ошибку. В частности, если errno равен EINTR, nanosleep() была прервана сигналом. В этом случае, если rem не равен NULL, struct timespec, на которую она указывает, содержит оставшееся время задержки. Это облегчает повторный вызов nanosleep() для продолжения задержки.

Хотя это выглядит немного странным, вполне допустимо использовать одну и ту же структуру для обоих параметров:

struct timespec sleeptime = /* что угодно */;

int ret;

ret = nanosleep(&sleeptime, &sleeptime);

struct timeval и struct timespec сходны друг с другом, отличаясь лишь компонентом долей секунд. Заголовочный файл GLIBC определяет для их взаимного преобразования друг в друга два полезных макроса:

#include /* GLIBC */

void TIMEVAL_TO_TIMESPEC(struct timeval *tv, struct timespec *ts);

void TIMEPSEC_TO_TIMEVAL(struct timespec *ts, struct timeval *tv);

Вот они:

# define TIMEVAL_TO_TIMESPEC(tv, ts) {

 (ts)->tv_sec = (tv)->tv_sec;

 (ts)->tv_nsec = (tv)->tv_usec * 1000;

}

# define TIMESPEC_TO_TIMEVAL(tv, ts) {

 (tv)->tv_sec = (ts)->tv_sec;

 (tv)->tv_usec = (ts)->tv_nsec / 1000;

}

#endif

ЗАМЕЧАНИЕ. To, что некоторые системные вызовы используют микросекунды, а другие – наносекунды, в самом деле сбивает с толку. Причина этого историческая: микросекундные вызовы были разработаны на системах, аппаратные часы которых не имели более высокого разрешения, тогда как наносекундные вызовы были разработаны более недавно для систем со значительно более точными часами. C'est la vie. Почти все, что вы можете сделать, это держать под руками ваше руководство.

14.4. Расширенный поиск с помощью двоичных деревьев

В разделе 6.2 «Функции сортировки и поиска» мы представили функции для поиска и сортировки массивов. В данном разделе мы рассмотрим более продвинутые возможности.

14.4.1. Введение в двоичные деревья

Массивы являются почти простейшим видом структурированных данных. Их просто понимать и использовать. Хотя у них есть недостаток, заключающийся в том, что их размер фиксируется во время компиляции. Таким образом, если у вас больше данных, чем помещается в массив, вам не повезло. Если у вас значительно меньше данных, чем размер массива, память расходуется зря. (Хотя на современных системах много памяти, подумайте об ограничениях программистов, пишущих программы для внедренных систем, таких, как микроволновые печи и мобильные телефоны. С другого конца спектра, подумайте о проблемах программистов, имеющих дело с огромными объемами ввода, таких, как прогнозирование погоды.

В области компьютерных наук были придуманы многочисленные динамические структуры данных, структуры, которые увеличивают и уменьшают свой размер по требованию и которые являются более гибкими, чем простые массивы, даже массивы, создаваемые и изменяемые динамически с помощью malloc() и realloc(). Массивы при добавлении или удалении новых элементов требуется также повторно сортировать.

Одной из таких структур является дерево двоичного поиска, которое мы для краткости будем называть просто «двоичным деревом» («binary tree»). Двоичное дерево хранит элементы в сортированном порядке, вводя их в дерево в нужном месте при их появлении. Поиск по двоичному дереву также осуществляется быстро, время поиска примерно такое же, как при двоичном поиске в массиве. В отличие от массивов, двоичные деревья не нужно каждый раз повторно сортировать с самого начала при добавлении к ним элементов.

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

Теперь не избежать некоторой формальной терминологии, относящейся к структурам данных. На рис. 14.1 показано двоичное дерево. В информатике деревья изображаются, начиная сверху и расширяясь вниз. Чем ниже спускаетесь вы по дереву, тем больше его глубина. Каждый объект внутри дерева обозначается как вершина (node). На вершине дерева находится корень дерева с глубиной 0. Внизу находятся концевые вершины различной глубины. Концевые вершины отличают по тому, что у них нет ответвляющихся поддеревьев (subtrees), тогда как у внутренних вершин есть по крайней мере одно поддерево. Вершины с поддеревьями иногда называют родительскими (parent), они содержат порожденные вершины (children).

Рис. 14.1. Двоичное дерево

Чистые двоичные деревья отличаются тем, что каждая вершина содержит не более двух порожденных вершин. (Деревья с более чем двумя вершинами полезны, но не существенны для нашего обсуждения.) Порожденные вершины называются в этом случае левой и правой соответственно.

Деревья двоичного поиска отличаются еще и тем, что значения, хранящиеся в левой порожденной вершине, всегда меньше значения в родительской вершине, а значения, хранящиеся в правой порожденной вершине, всегда больше значения в родительской вершине. Это предполагает, что внутри дерева нет повторяющихся значений. Этот факт также объясняет, почему деревья не эффективны при работе с предварительно отсортированными данными: в зависимости от порядка сортировки, каждый новый элемент данных сохраняется либо только слева, либо только справа от находящегося впереди него элемента, образуя простой линейный список.

К двоичным деревьям применяют следующие операции:

Ввод

Добавление к дереву нового элемента.

Поиск

Нахождение элемента в дереве.

Удаление

Удаление элемента из дерева.

Прохождение (traversal)

Осуществление какой-либо операции с каждым хранящимся в дереве элементом. Прохождение дерева называют также обходом дерева (tree walk). Есть разнообразные способы «посещения» хранящихся в дереве элементов. Обсуждаемые здесь функции реализуют лишь один из таких способов. Мы дополнительно расскажем об этом позже.

14.4.2. Функции управления деревьями

Только что описанные операции соответствуют следующим функциям:

#include /* XSI */

void *tsearch(const void *key, void **rootp,

int (*compare)(const void*, const void*));

void *tfind(const void *key, const void **rootp,

int (*compare)(const void*, const void*));

void *tdelete(const void *key, void **rootp,

int (*compare)(const void*, const void*));

typedef enum { preorder, postorder, endorder, leaf } VISIT;

void twalk(const void *root,

void (*action)(const void *nodep, const VISIT which,

const int depth));

void tdestroy(void *root, void (*free_node)(void *nodep)); /* GLIBC*/

Эти функции были впервые определены для System V, а теперь формально стандартизованы POSIX. Они следуют структуре других, которые мы видели в разделе 6.2 «Функции сортировки и поиска»: использование указателей void* для указания на произвольные типы данных и предоставляемые пользователем функции сравнения для определения порядка. Как и для qsort() и bsearch(), функции сравнения должны возвращать отрицательное/нулевое/положительное значение, когда key сравнивается со значением в вершине дерева.

14.4.3. Ввод элемента в дерево: tsearch()

Эти процедуры выделяют память для вершин дерева. Для их использования с несколькими деревьями нужно предоставить им указатель на переменную void*, в которую они заносят адрес корневой вершины. При создании нового дерева инициализируйте этот указатель в NULL:

void *root = NULL; /* Корень нового дерева */

void *val; /* Указатель на возвращенные данные */

extern int my_compare(const void*, const void*); /* Функция сравнения */

extern char key[], key2[]; /* Значения для ввода в дерево */

val = tsearch(key, &root, my_compare);

 /* Ввести в дерево первый элемент */

/* ...заполнить key2 другим значением. НЕ изменять корень... */

val = tsearch(key2, &root, my_compare);

 /* Ввести в дерево последующий элемент */

Как показано, в переменной root должен быть NULL лишь в первый раз, после чего нужно оставить ее как есть. При каждом последующем вызове tsearch() использует ее для управления деревом.

Когда разыскиваемый key найден, как tsearch(), так и tfind() возвращают указатель на содержащую его вершину. Поведение функций различно, когда key не найден: tfind() возвращает NULL, a tsearch() вводит в дерево новое значение и возвращает указатель на него. Функции tsearch() и tfind() возвращают указатели на внутренние вершины дерева. Они могут использоваться в последующих вызовах в качестве значения root для работы с поддеревьями. Как мы вскоре увидим, значение key может быть указателем на произвольную структуру; он не ограничен символьной строкой, как можно было бы предположить из предыдущего примера.

Эти процедуры сохраняют лишь указатели на данные, использующиеся в качестве ключей. Соответственно это ваше дело управлять памятью для хранения значений данных, обычно с помощью malloc().

ЗАМЕЧАНИЕ. Поскольку функции деревьев хранят указатели, тщательно позаботьтесь о том, чтобы не использовать realloc() для значений, которые были использованы в качестве ключей! realloc() может переместить данные, вернув новый указатель, но процедуры деревьев все равно сохранят висящие (dangling) указатели на старые данные.