Эффективное программирование TCP-IP

       

и следующем разделах будет рассказано


| | |
В этом и следующем разделах будет рассказано об использовании техники событийной управляемости в программировании TCP/IP. Будет разработан универсальный механизм тайм-аутов, позволяющий указать программе, что некоторое событие должно произойти до истечения определенного времени, и асинхронно приступить к обработке этого события в указанное время. Здесь рассмотрим реа­лизацию механизма таймеров, а в совете 21 вернемся к архитектуре с двумя соединениями и применим его на практике.
Разница между событийно-управляемым и обычным приложением хорошо иллюстрируется двумя написанными ранее программами: hb_client2 (листинги 2.26 и 2.27) и tcprw (листинг 2.21). В tcprw поток управления последовательный: сначала из стандартного ввода читается строка и передается удаленному хосту, а затем от него принимается ответ и записывается на стандартный вывод. Обратите внимание, что нет возможности ничего принять от удаленного хоста, пока ожидается ввод из stdin. Как вы видели, в результате можно не знать, что партнер за­вершил сеанс и послал ЕОЕ Ожидая также ответа от удаленного хоста, вы не можете читать новые данные из stdin. Это значит, что приложение, с точки зрения пользователя, слишком медленно реагирует. Кроме того, оно может «зависнуть», если удаленный хост «падает» до того, как приложение ответило.
Сравните это поведение с работой клиента hb_client2, который в любой момент способен принимать данные по любому соединению или завершиться по тайм-ауту. Ни одно из этих событий не зависит от другого, именно поэтому такая архитектура называется событийно-управляемой.
Заметим, что клиента hb_client2 можно легко обобщить на большее число соединений или источников входной информации. Для этого существует механизм select, который позволяет блокировать процесс в ожидании сразу нескольких событий и возвращать ему управление, как только произойдет любое из них. В системе UNIX этот механизм, а также родственный ему вызов poll, имеющийся в системах на базе SysV, - это единственный эффективный способ обработки асинхронных событий в немногопоточной среде.


Примечание: До недавнего времени считалось, что из соображений переносимости следует использовать select, а не poll, так как на платформе Windows, а равно в современных UNIX-системах поддерживается именно select, тогда как poll встречается обычно в реализациях на базе SysV. Однако некоторые большие серверные приложения (например, Web-серверы), поддерживающие очень много одновременных соединений, применяют механизм poll, так как он лучше масштабируется на большое число дескрипторов. Дело в том, что select ограничен фиксированным числом дескрипторов. Обычно их не больше 1024, но бывает и меньше. Так, в системе FreeBSD и производных от нее по умолчанию предел равен 256. Для изменения значения по умолчанию нужно пересобирать ядро, что неудобно, хотя и возможно. Но и пересборка ядра лишь увеличивает предел, а не снимает его. Механизм же poll не имеет встроенных ограничений на число дескрипторов. Следует также принимать во внимание эффективность. Типичная реализация select может быть очень неэффективной при большом числе дескрипторов. Подробнее это рассматривается в работе [Banga and Mogul 1998]. (В этой работе приводится еще один пример возникновения трудностей при экстраполяции результатов, полученных в локальной сети, на глобальную. Эта тема обсуждалась в совете 12.) Проблема большого числа де­скрипторов стоит особенно остро, когда ожидается немного событий на многих дескрипторах, то есть первый аргумент - maxfd - велик, но с помощью FD_SET было зарегистрировано всего несколько дескрипторов. Это связано с тем, что ядро долж­но проверить все возможные дескрипторы (0,..., maxfd), чтобы понять, ожидаются ли приложением события хотя бы на одном из них. В вызове poll используется массив дескрипторов, с помощью которого ядру сообщается о том, в каких событиях заинтересовано приложение, так что этой проблемы не возникает.
Итак, использование select или poll позволяет мультиплексировать несколько событий ввода/вывода. Сложнее обстоит дело с несколькими таймерами, поскольку в вызове можно указать лишь одно значение тайм-аута. Чтобы решить эту проблему и создать тем самым более гибкое окружение для событийно-управляемых программ, следует разработать вариант вызова select - tselect. Хотя функции timeout и untimeout, связанные с tselect, построены по той же схеме, что и одноименные подпрограммы ядра UNIX, они работают в адресном пространстве пользователя и используют select для мультиплексирования ввода/вывода и получения таймера..


Таким образом, существуют три функции, ассоциированные с tselect. Прежде всего это сама tselect, которая применяется аналогично select для мультиплексирования ввода/вывода. Единственное отличие в том, что у tselect нет параметра timeout (это пятый параметр select). События таймера задаются с помощью вызова функции timeout, которая позволяет указать длительность таймера и действие, которое следует предпринять при его срабатывании. Вызов untimeout отменяет таймер до срабатывания.
Порядок вызова этих функций описан следующим образом:
#nclude "etcp.h"
int tselect ( int maxfd, fd_set *rdmask, fd_set *wrmask, fd_set *exrnask );
Возвращаемое значение: число готовых событий, 0 - если событий нет, -1 -.ошибка.
unsigned int timeout( void (handler)(void * ), void *arg, int ms);
Возвращаемое значение: идентификатор таймера для передачи untimeout


void untimeout( unsigned int timerid);
Когда срабатывает таймер, ассоциированный с вызовом timeout, вызывается функция, заданная параметром handler, которой передается аргумент, заданный параметром arg. Таким образом, чтобы организовать вызов функции retransmit через полторы секунды с целым аргументом sock, нужно сначала написать
timeout( retransmit, ( void  * )  sock, 1500 );
а затем вызывать tselect. Величина тайм-аута ms задается в миллисекундах, но надо понимать, что разрешающая способность системных часов может быть ниже. Для UNIX-систем типичное значение составляет 10 мс, поэтому не следует ожи­дать от таймера более высокой точности.
Примеры использования tselect будут приведены далее, а пока рассмотрим ее реализацию. В листинге 3.14 приведено определение структуры tevent_t и объявления глобальных переменных.
Листинг 3.14. Глобальные данные для tselect
tselect.с
1    #include "etcp.h"
2    #define NTIMERS 25
3    typedef struct tevent_t tevent_t;
4    struct tevent_t
5    {
6    tevent_t   *next;
7    struct timeval tv;
8    void ( *func )( void * );
9    void *arg;
10   unsigned int id;


11   };
12   static tevent_t *active = NULL; /* Активные таймеры. */
13   static tevent_t *free_list = NULL; /* Неактивные таймеры. */
Объявления
2 Константа NTIMERS определяет, сколько таймеров выделять за один раз. Сначала таймеров нет вовсе, поэтому при первом обращении к timeout будет выделено NTIMERS таймеров. Если все они задействованы и происходит очередное обращение к timeout, то выделяется еще NTIMERS таймеров.
3-11 Каждый таймер представляет отдельную структуру типа tevent_t. Структуры связаны в список полем next. В поле tv хранится время срабатывания таймера. Поля func и arg предназначены для хранения указателя на функцию обработки события таймера (которая вызывается при срабатывании) и ее аргумента. Наконец, идентификатор активного таймера хранится в поле id.
12 Порядок расположения активных таймеров в списке определяется моментом срабатывания. Глобальная переменная active указывает на первый таймер в списке.
13 Неактивные таймеры находятся в списке свободных. Когда функции timeout нужно получить новый таймер, она берет его из этого списка. Глобальная переменная free_list указывает на начало списка свободных.
Далее изучим функцию timeout и подпрограммы выделения таймеров (листинг 3.15).
Листинг 3.15. Функции timeout и allocateJimer
tselect.с
1    static tevent_t *allocate_timer( void )
2    {
3    tevent_t *tp;
4    if ( free_list = NULL ) /* нужен новый блок таймеров? *./
5    {
6      free_list = malloc( NTIMERS * sizeof( tevent_t ));
7      if ( free_list = NULL )
8       error( 1, 0, "не удалось получить таймеры\n" };
9       for ( tp = free_list;
10       tp < free_list + NTIMERS - 1; tp+ + )
11      tp->next = tp + 1;
12      tp->next = NULL;
13     }
14     tp = free_list; /* Выделить первый. */
15     free_list = tp->next; /* Убрать его из списка. */
16     return tp;
17   }
18   unsigned int timeout ( void ( *func ) ( void * ), void *arg, int ms )
19   {
20     tevent_t *tp;
21     tevent_t *tcur;


22     tevent_t **tprev;
23     static unsigned int id = 1; /* Идентификатор таймера. */
24     tp = allocate_timer();
25     tp->func = func;
26     tp->arg = arg;
27     if ( gettimeofday( &tp->tv, NULL ) < 0 )
28      error( 1, errno, "timeout: ошибка вызова gettimeofday");
29     tp->tv.tv_usec + = ms * 1000;
30     if ( tp->tv.tv_usec > 1000000 )
31     {
32      tp->tv.tv_sec + = tp->tv.tv_usec / 1000000;
33      tp->tv.tv_usec %= 1000000;
34     }
35     for ( tprev = &active, tcur = active;
36      tcur && !timercmp( &tp->tv, &tcur->tv, < ); /* XXX */
37      tprev = &tcur->next, tcur = tcur->next )
38     { ; }
39     *tprev = tp;
40     tp->next   =   tcur;
41     tp->id =  id++; /* Присвоить значение идентификатору таймера. */
42     return  tp->id;
43   }
allocate_timer
4- 13 Функция allocate_timer вызывается из timeout для получения свободного таймера. Если список свободных пуст, то из кучи выделяется память для NTIMERS структур tevent_t, и эти структуры связываются в список.
14-16 Выбираем первый свободный таймер из списка и возвращаем его вызывающей программе.
timeout
24-26 Получаем таймер и помещаем в поля func и arg значения переданных нам параметров.
27-34 Вычисляем момент срабатывания таймера, прибавляя значение пара­метра ms к текущему времени. Сохраняем результат в поле tv.
35-38 Ищем в списке активных место для вставки нового таймера. Вставить таймер нужно так, чтобы моменты срабатывания всех предшествующих таймеров были меньше либо равны, а моменты срабатывания всех последующих - больше момента срабатывания нового. На рис. 3.6 показан

Рис. 3.6. Список активных таймеров до и после поиска точки вставьки
процесс поиска и значения переменных tcur и tprev. Вставляем новый таймер так, что его момент срабатывания tnew удовлетворяет условию t0 < t1, < tnew < t2. Обведенный курсивом прямоугольник tnew показывает позицию в списке, куда будет помещен новый таймер. Несколько странное использование макроса timercmp в строке 36 связано с тем, что вер­сия в файле winsock2.h некорректна и не поддерживает оператора >=.


27-34 Вставляем новый таймер в нужное место, присваиваем ему идентификатор и возвращаем этот идентификатор вызывающей программе. Возвращается идентификатор, а не адрес структуры tevent_t, чтобы избежать «гонки» (race condition). Когда таймер срабатывает, структура tevent_t возвращается в начало списка свободных. При выделении нового таймера будет использована именно эта структура. Если приложение теперь попытается отменить первый таймер, то при условии, что возвращается адрес структуры, а не индекс, будет отменен второй таймер. Эту проблему решает возврат идентификатора.
Идентификатор таймера, возвращенный в конце функции из листинга 3.15, используется функцией untimeout (листинг 3.16).
Листинг 3.16. Функция untimeout
tselect.с
1    void untimeout( unsigned int id )
2    {
3    tevent_t **tprev;
4    tevent_t *tcur;
5    for ( tprev = &active, tcur = active;
6      tcur && id != tcur->id;
7      tprev = &tcur->next, tcur = tcur->next);
8      { ; }
9    if ( tcur == NULL )
10   {
11     error( 0, 0,
12      "при вызове untimeout указан несуществующий таймер (%d) \n", id );
13      return;
14   }
15   *tprev = tcur->next;
16   tcur->next = free_list;
17   free_list = tcur;
18   }
Поиск таймера
5-8 Ищем в списке активных таймер с идентификатором id. Этот цикл похож на тот, что используется в timeout (листинг 3.15).
9-14 Если в списке нет таймера, который пытаемся отменить, то выводим диагностическое сообщение и выходим.
Отмена таймера
15-17 Для отмены таймера исключаем структуру tevent_t из списка активных и возвращаем в список свободных.
Последняя из функций, работающих с таймерами, - это tselect (листинг 3.17)
Листинг 3.17. Функция tselect
1    int tselect( int maxp1, fd_set *re, fd_set *we, fd_set *ee )
2    {
3    fd_set rmask;
4    fd_set wmask;
5    fd_set emask;
6    struct timeval now;
7    struct timeval tv;
8    struct timeval *tvp;
9    tevent_t *tp;
10   int n;
11   if ( re )


12     rmask = *re;
13   if ( we )
14     wmask = *we;
15   if ( ее )
16     emask = *ee;
17   for ( ; ; )
18   {
19     if ( gettimeofday( know, NULL ) < 0 )
20      error( 1, errno, "tselect: ошибка вызова gettimeofday" );
21     while ( active && !timercmp( know, &active->tv, < ) )
22     {
23      active->func( active->arg );
24      tp = active;
25      active = active->next;
26      tp->next = free_list;
27      free_list = tp;
28     }
29     if ( active )
30     {
31      tv.tv_sec = active->tv.tv_sec - now.tv_sec;
32      tv.tv_usec = active->tv.tv_usec - now.tv_usec;
33      if ( tv.tv_usec < 0 )
34      {
35       tv.tv_usec += 1000000;
36       tv.tv_sec--;
37      }
38      tvp = &tv;
39     }
40     else if ( re == NULL && we == NULL && ее == NULL )   •
41      return 0;
42     else
43      tvp = NULL;
44     n = select ( maxpl, re, we, ее, tvp );
45     if ( n < 0 )
46      return -1;
47     if ( n > 0 )
48      return n;
49     if ( re )
50      *re = rmask;
51     if ( we )
52      *we = wmask;
53     if ( ее )
54      *ee = emask;
55   }
56   }
Сохранение масок событий
11- 16 Поскольку при одном обращении к tselect может несколько раз вызываться select, сохраняем маски событий, передаваемых select.
Диспетчеризация событий таймера
19-28 Хотя в первой структуре tevent_t, находящейся в списке активных таймеров, время срабатывания меньше или равно текущему времени, вызываем обработчик этого таймера, исключаем структуру из списка активных и возвращаем в список свободных. Как и в листинге 3.15, странный вызов макроса timercmp обусловлен некорректной его реализацией в некоторых системах.
Вычисление времени следующего события
29-39 Если список активных таймеров не пуст, вычисляем разность между текущим моментом времени и временем срабатывания таймера в нача­ле списка. Это значение передаем системному вызову select.
40-41 Если больше таймеров нет и нет ожидаемых событий ввода/вывода, то tselect возвращает управление. Обратите внимание, что возвращается нуль, тем самым извещается об отсутствии ожидающих собы­тий. Семантика кода возврата отличается от семантики select.


42- 43 Если нет событий таймера, но есть события ввода/вывода, то устанавливаем tvp в NULL, чтобы select не вернулся из-за тайм-аута.
Вызов select
44-48 Вызываем select, чтобы он дождался события. Если select заверша­ется с ошибкой, то возвращаем код ошибки приложению. Если select возвращает положительное значение (произошло одно или более событий ввода/вывода), то возвращаем приложению число событий. По­скольку вызывали select, передавая указатели на маски событий, под­готовленные приложением, то биты событий в них уже установлены-
49-54 Если select вернул нуль, то сработал один или несколько таймеров. Поскольку в этом случае select обнулит все маски событий, установленные приложением, восстановим их перед тем, как возвращаться к началу цикла, где вызываются обработчики таймеров.
Для вставки и удаления таймеров из списка был использован линейный поиск. При небольшом числе таймеров это не страшно, но при увеличении их числа произ­водительность программы снижается, так как для поиска требуется О(n) операций, где n - число таймеров (для запуска обработчика события требуется время порядка O(1)). Вместо линейного поиска можно воспользоваться пирамидой [Sedgewick 1998] - для вставки, удаления и диспетчеризации требуется O(log n) операций - или хэширующим кольцом таймеров (hashing timing wheel) [Varghese and Lacuk 1997]; при этом эффективность может достигать О(1) для всех трех операций.
Заметим, что функция tselect не требует наличия ожидающих событий вво­да/вывода, поэтому ее вполне можно использовать только как механизм организа­ции тайм-аутов. В данном случае имеем следующие преимущества по сравнению с системным вызовом sleep:
  • в системе UNIX s leep позволяет задерживать исполнение на интервал, кратный секунде, то есть разрешающая способность очень мала. В Windows такого ограничения нет. Во многих реализациях UNIX есть иные механизмы с более высокой степенью разрешения, однако они не очень распространены. Хотелось бы иметь механизм таймеров с высокой степенью разрешения, работающий на возможно большем числе платформ. Поэтому в UNIX принято использовать для реализации высокоточных таймеров вызов select;

  • применение sleep или «чистого» select для организации нескольких таймеров затруднительно, поскольку требует введения дополнительных струк­тур данных. В функции tselect все это уже сделано.

  • К сожалению, в Windows функция tselect в качестве таймера работает не со­всем хорошо. В спецификации Winsock API [WinSock Group 1997] говорится, что использование selects качестве таймера «неудовлетворительно и не имеет оправданий». Хотя на это можно возразить, что «неудовлетворительность» -это когда системный вызов работает не так, как описано в опубликованной специ­фикации, все же придется придерживаться этой рекомендации. Тем не менее можно использовать функцию tselect и связанные с ней под Windows, только при этом следует указывать также и события ввода/вывода.

    Содержание раздела