Форум Всеукраїнської інтернет-олімпіади NetOI


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

#1 2011-11-17 19:05:17

maxtram
Новий користувач
Зареєстрований: 2007-01-12
Повідомлень: 13

Измерение тайм-лимитов

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

Какая величина считается временем выполнения решения задачи на одном тесте и каким образом тестирующая система её измеряет?

Используются ли библиотечные функции getrusage(), wait3() или wait4() для получения поля ru_utime структуры rusage, которое и является настоящим временем работы дочернего процесса (т.е. решения задачи) в userspace? Или тестирующая система считает временем выполнения решения какую-то другую величину?

Сколько раз запускается решение на каждом тесте, и как результаты этих запусков влияют на то, засчитывается текущий тест или нет?

Заранее спасибо за ответы.


laptop login: root
Password:
Last login: Thu Jan  1 00:00:00 UTC 1970
root@[laptop:~]# eix-sync && emerge -atuvDN world

Поза форумом

 

#2 2011-11-17 19:21:09

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: Измерение тайм-лимитов

Юрий Яковлевич ответит наверное поподробней, но всё-таки рискну попробовать ответить и я.

1. Какие библиотеки используются, а какие нет (кроме стандарта, естественно) пользователю знать не обязательно.

2. Во время официального тестирования запуск всех решений на проверку осуществляется как минимум дважды - сам при этом неоднократно присутствовал. Как правило, если решение не проходит ТЛ на 1-м-2-х тестах во время одного из запусков, то решение запускается в третий раз и на основании 3-х решений и принимается решение защитывать или нет решение граничащее с ТЛ.

3. Проблемы связанные с временем реального исполнения тесно связаны, как Вы сами отметили, с дочерними, а также, теперь дополню я - также с паралельными процессами. Именно поэтому во время официального тестирования все параллельные процессы блокируются, а вот во время он-лайн тестирования могут работать и другие процессы. Именно поэтому Юрий Яковлевич в одном из сообщений этого года (так же, как он это делает каждый год) предупредил, что время выполения программы на он-лайн тестровании и на официальном тестировании могут отличаться.

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

Если же у Вас есть желание получить более детальную информация, то более целесообразно обратится к тому же Юрию Яковлевичу с личным письмом, где Вы и получите (если он сочтёт нужным и это не повредит системе) необходимые разъяснения.

Ответ Вам был дан от независимого иногороднего и иноплатформенного члена жюри.
Если он Вас устроил - значит не опубликованную здесь информацию Вы восприняли.

С уважением - А.В.Присяжнюк

Відредаговано Присяжнюк А.В. (2011-11-17 19:22:49)


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

#3 2011-11-17 19:56:23

maxtram
Новий користувач
Зареєстрований: 2007-01-12
Повідомлень: 13

Re: Измерение тайм-лимитов

Спасибо за ответ, но один вопрос у меня всё же остался.

>если он сочтёт нужным и это не повредит системе

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

Задаю я их с одной целью — удостовериться в том, что время выполнения решений измеряется правильно, в чём у меня возникли некоторые сомнения (по личному опыту, не на всех олимпиадах его меряют правильно, не говоря о точности). По сути, время работы решения определяется тем процессорным временем, которое использовал процесс программы решения во время исполнения userspace-кода. Это время несколько отличается от времени, которое проходит от момента запуска процесса (после вызова exec()) до его завершения, поскольку не всё это время процессор занимается выполнением кода именно этого процесса и именно userspace-кода, а не ядерного.

Оба эти времени можно измерить, к примеру, командой time, которая использует библиотечную функцию wait3(). В выводе этой команды по завершению работы измеряемого процесса время в строке "user" означает то процессорное время, которое реально затратил userspace-код процесса, оно является временем работы решения и не зависит от других процессов, выполняющихся в системе, поэтому оно и определяет, какое решение быстрее, и сколько работает данное решение. Время в строке "real" показывает интервал времени от запуска процесса вызовом exec() до завершения exit(). Оно зависит не только от времени выполнения решения, а и от времени выполнения других процессов, "отобравших" квант времени у процесса решения, а также от времени выполнения ядерного кода переключения процессов, поэтому оно не является объективным показателем скорости решения и даже не является величиной для сравнения с другими решениями.

Итак, величиной, годящейся для сравнения скорости решений, является именно строка "user", число в которой — это поле ru_utime структуры rusage. Меня пока что после Вашего ответа интересует только то, используется ли это правильное по моему мнению время для сравнения скорости решений и выставления тайм-лимитов, или же измеряется время "real", величина которого значительно зависит от внешних факторов.

>Проблемы связанные с временем реального исполнения тесно связаны, как Вы сами отметили, с дочерними, а также, теперь дополню я - также с паралельными процессами

Дочерними процессами для тестирующей системы являются процессы с решениями, а параллельные процессы влияют только на время "real", но не на "user", поэтому время "user" является определяющим фактором скорости решения.

>Именно поэтому во время официального тестирования все параллельные процессы блокируются

В это я никак не могу поверить в случае многозадачной системы GNU/Linux. Можно убить максимум процессов, увеличить приоритет процессу решения, уменьшить остальные приоритеты, но полностью блокировать все остальные процессы невозможно — в Linux нет однозадачного режима. И это замечание склоняет меня (до более официального ответа) верить в то, что на этой олимпиаде измеряется "неправильное" время "real", потому что в случае измерения времени "user" необходимости ограничивать посторонние процессы просто нет.

>Если же у Вас есть желание получить более детальную информация, то более целесообразно обратится к тому же Юрию Яковлевичу с личным письмом, где Вы и получите (если он сочтёт нужным и это не повредит системе) необходимые разъяснения.

Если Юрий Яковлевич склонен не обсуждать эту тему на форуме, но обсудить по почте, я могу написать ему по почте.


laptop login: root
Password:
Last login: Thu Jan  1 00:00:00 UTC 1970
root@[laptop:~]# eix-sync && emerge -atuvDN world

Поза форумом

 

#4 2011-11-17 20:05:22

Присяжнюк А.В.
Новий користувач
Звідки: Бердичів СЗОШ 17
Зареєстрований: 2005-11-19
Повідомлень: 140
Вебсайт

Re: Измерение тайм-лимитов

Я задам один вопрос, на который пострайтесь ответить сами себе: Зависит ли количество тиков (операций) самого процессора от типа операционной системы? (собственно это и есть процессорное время)
После ответа на этот попрос, на вопрос "почему блокируются остальные процессы" Вы себе сами должны дать ответ.


Права на ошибку не имеет тот, кто ничего не делает...

Поза форумом

 

#5 2011-11-17 20:36:27

maxtram
Новий користувач
Зареєстрований: 2007-01-12
Повідомлень: 13

Re: Измерение тайм-лимитов

>После ответа на этот попрос, на вопрос "почему блокируются остальные процессы" Вы себе сами должны дать ответ.

Я задал несколько другой вопрос.

>Я задам один вопрос, на который пострайтесь ответить сами себе: Зависит ли количество тиков (операций) самого процессора от типа операционной системы? (собственно это и есть процессорное время)

Я отвечу немного не на этот вопрос, потому что мне кажется, что вы меня немного не поняли. Я надеюсь, вы согласны, что время, за которое отработало решение — это количество тактов, затраченных процессором на выполнение инструкций из кода решения? Так вот это время можно измерить средствами glibc в Linux непосредственно, не блокируя остальные процессы. Т.е. ядро для каждого процесса считает время, в течение которого процессор занимался выполнением именно этого процесса. Нужный процесс выполняется — счётчики идут, процесс переключился на другой — счётчики приостановились. И это точное время легко измерить командой time (оно показано в строке "user") либо функцией wait3() из родительского процесса, которую, собственно, и использует команда time.

Но мне кажется (из некоторого опыта и информации, полученной от Вас), что тестирующая система здесь измеряет не это время "user", а астрономическое время, прошедшее от запуска процесса, до его завершения (время "real"), при этом стараетесь обеспечить, чтобы большую часть этого времени работает нужный процесс, но в многозадачной системе никогда не получится, что всё это время работает нужный процесс. Более того, невозможно обеспечить, чтобы всегда время "real" было на определённую константу больше, чем время "user". Поэтому, запустив 2 раза одно и тоже решение на одном и том же тесте, мы получим 2 одинаковых результата для времени "user" (ускорение при втором запуске за счёт дискового кэша, кэша процессора не учитываю), но 2 разных результата для времени "real", которые ОЧЕНЬ сильно зависят от посторонних процессов, но даже если минимизировать кол-во посторонних процессов, влияние всё равно будет заметно. Мой вопрос состоял именно в том, использует ли система для проверки тайм-лимитов время "real", которое никогда не бывает объективным, или же время "user", которое объективно показывает время выполнения программы при любых условиях (даже с кучкой запущенных посторонних процессов, даже если они занимают большую часть загруженности процессора)?

Надеюсь, теперь ситуация немного прояснилась, и я смогу узнать, использует ли проверяющая система время "user" или время "real".

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

В случае, если система измеряет время "real", становится понятным, зачем убивать посторонние процессы, но тогда можно быть уверенным в неправильности измерений, поскольку все посторонние процессы убить невозможно, однозадачного режима у Linux нет, и влияние всё равно будет заметно, особенно со здешними тайм-лимитами. И в этом случае непонятно, зачем использовать неточный способ измерения, создавать специальные условия, уменьшающими неточность, но не устраняющими её, когда есть способ измерения правильного времени, не зависящий от посторонних процессов.


laptop login: root
Password:
Last login: Thu Jan  1 00:00:00 UTC 1970
root@[laptop:~]# eix-sync && emerge -atuvDN world

Поза форумом

 

#6 2011-11-18 17:52:07

Жюри_Пасихов
Адміністратор
Зареєстрований: 2009-11-08
Повідомлень: 391

Re: Измерение тайм-лимитов

1. Я действительно не хочу обсуждать эту тему на форуме, который предназначен для ответов на вопросы по условиям задач и анализу их решений после окончания тура.
Берусь аргументировано доказать - участник не страдают, И ПРИ ЭТОМ  МЫ "ОТСЕКАЕМ" НЕЭФФЕКТИВНЫЕ РЕШЕНИЯ ОТ ЭФФЕКТИВНЫХ ЛУЧШЕ, ЧЕМ ЛЮБАЯ ИНАЯ МНЕ ИЗВЕСТНАЯ СИСТЕМА ПРОВЕРКИ.
2. Если вопрос по-прежнему ИНТЕРЕСЕН КОМУ-ТО - ПРИШИТЕ, ХОТЯ КАТАСТРОФИЧЕСКИ НЕТ ВРЕМЕНИ...

Поза форумом

 

#7 2011-11-19 19:13:32

reiten
журі
Звідки: Киев
Зареєстрований: 2005-10-16
Повідомлень: 196

Re: Измерение тайм-лимитов

maxtram
Вы не совсем правы. А именно, общепринятой практикой является вычисление времени работы решения как суммы ru_utime+ru_stime (время, которое затрачено приложением в userspace+в пространстве ядра). Причина: время выполнения в режиме ядра - время, которое система тратит на выполнение запросов (обращений к системным вызовам) участника. Поэтому исключать "sys" время из времени выполнения неправильно.

С Вашими доводами против замера астрономического времени я абсолютно согласен. Хотя должен заметить, что на загруженной системе (или, хуже того, на системе с плавающей нагрузкой) процессорное время выполнения (ru_utime, ru_stime) также нестабильно (если интересны причины такого поведения, то можем их обсудить в ПМ). Поэтому в зависимости от того, какие сервисы подняты на сервере онлайн-проверки, они вполне могут оказать влияние на замер времени.

PS Не смотря на мой статус на форуме, я не вхожу в жюри NetOI2011, и я не являюсь разработчиком тестирующей системы NetOI. Поэтому на вопросы устройства этой проверяющей системы я ответить не в состоянии.


"...Существуют два подхода к проектированию программ. В одном архитектура делается настолько простой, что в ней явно нет дефектов; в другом - настолько сложной, что в ней нет явных дефектов".
С. А. Хоар

Поза форумом

 

#8 2011-11-22 00:00:38

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 281
Вебсайт

Re: Измерение тайм-лимитов

Судячи з усього, заміряється, все-таки, астрономічний час - ось такий код вилітае з ТЛ-ми:

Код:

system("sleep 10");

Поза форумом

 

#9 2011-11-22 11:52:21

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: Измерение тайм-лимитов

Dim_ov написав:

Судячи з усього, заміряється, все-таки, астрономічний час - ось такий код вилітае з ТЛ-ми:

Код:

system("sleep 10");

Саме по собі це нічого не доводить -- "православний" ("правильний") ejudge теж, якщо не скаже на таке crash, то теж скаже ТЛ. Тільки не треба відповідати голослівно -- спочатку таки спробуйте в любому доступному з інтернету єджаджі.

Я не стверджую, ніби перевіряюча система НетОІ ідеальна -- я знаю, що це не так. Але:
1) вона виконує свої функції
2) вона вміє працювати як з он-лайном, так і з електронними листами
3) олімпіада не залежить від милості сторонніх розробників. Задумайтеся хоч на півсекунди, який колапс настав би майже скрізь, якби Чернов раптом оголосив, що з деякого моменту користуватися єджаджем заборонено

Поза форумом

 

#10 2011-11-22 21:11:45

maxtram
Новий користувач
Зареєстрований: 2007-01-12
Повідомлень: 13

Re: Измерение тайм-лимитов

Dim_ov написав:

Судячи з усього, заміряється, все-таки, астрономічний час - ось такий код вилітае з ТЛ-ми:

Код:

system("sleep 10");

Попробовал с sleep 2, действительно получил TL 2 секунды. sleep 0 выдавал WA. Хотя Юрий Яковлевич, насколько я понял, утверждает, что измеряется время работы процесса, а не астрономическое. Что интересно, похоже, что тестирующая система не убивает процесс при достижении TL (показывается, что программа работала 2 секунды, а иногда вообще страница пустая грузится), поэтому любой из участников может отправить код с sleep 10000, который значительно задержит появление результатов. Это уязвимость, я считаю.

Ilya Porublyov написав:

Задумайтеся хоч на півсекунди, який колапс настав би майже скрізь, якби Чернов раптом оголосив, що з деякого моменту користуватися єджаджем заборонено

Нельзя было бы пользоваться новыми версиями. Старые же распространяются под GNU GPL, она не запрещает пользоваться программой.


laptop login: root
Password:
Last login: Thu Jan  1 00:00:00 UTC 1970
root@[laptop:~]# eix-sync && emerge -atuvDN world

Поза форумом

 

#11 2011-11-23 09:01:55

Жюри_Пасихов
Адміністратор
Зареєстрований: 2009-11-08
Повідомлень: 391

Re: Измерение тайм-лимитов

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

Поза форумом

 

Нижній колонтитул

Powered by Likt
© Copyright 2002–2009 Likt