Продолжаю серию статей о спортивном программировании в НГУ.
В прошлый раз я рассказывал о том, как пишутся задания для турниров, теперь хочу немного рассказать о системе тестирования.
Первая статья посвящена созданию задач.
Третья статья о работе оргкомитета.
Четвертая статья — о самом туре.
Система тестирования – святая святых любого соревнования.
Нервный центр турнира.
От этого во многом зависит успешное проведение тура; его стабильная работа может обеспечить спокойствие организаторам, а нестабильность может привести к усилению головной боли.
Написание системы тестирования — задача, достойная дипломной работы (насколько я помню, по системам тестирования уже защищено 2 диплома).
И написать действительно хорошую – и целую кандидатскую диссертацию.
Итак, из чего обычно состоит система тестирования? В случае с олимпиадами, которые проходили в моем родном городе, с компьютера с Турбо Паскалем и бабушки-контролера.
На более высоком уровне все гораздо веселее.
С участниками олимпиады борется целый разношерстный программный комплекс.
Где-то он очень кроссплатформенный, а где-то весьма специфичный.
Но все это вместе позволяет провести хорошую и красивую экскурсию.
Система тестирования, что логично, имеет серверную и клиентскую часть.
Серверный компонент в случае NSUts написан на Perl. Собственно, выбор языка не занял много времени.
Поначалу ребята пытались оптимизировать ujudge (он же Великий и Ужасный Гоплан), но после того, как на квалификации Всесиба-2008 система вновь замахала лапами в воздухе, слово Рубин среди участников олимпиады НГУ было объявлено матерным.
Было решено возродить систему Жени Четвертакова, которая долгое время справлялась со своими задачами, но когда-то была заменена более красивой и современной судьей.
Итак, Перл попросил об этом.
Веб-интерфейс отвечает за проведение олимпиады: принимает решения участников, сохраняет их, передает клиентам тестирования, получает результаты тестирования и обрабатывает их (строит рейтинг и т. д.).
Также общение с жюри во время тура происходит через веб-интерфейс, но об этом подробнее я расскажу в статье о работе команды организаторов во время тура.
Клиентская часть состоит из программного пакета: 1. WinKill – запуск программы с ограничением ресурсов 2. Diff – посимвольное сравнение двух файлов.
3. Noasm – поиск вставок ассемблера 4. Эстиматор – программа, предназначенная для выставления баллов за тесты.
5. Набор bat файлов для запуска компиляторов и программ О каждом элементе можно говорить очень долго, но согласованно проверяют решения и выносят вердикт, правильно ли решена задача.
Несколько клиентов тестирования могут быть запущены параллельно.
Причём их можно запускать параллельно не только на разных машинах, но и на одной машине с многоядерным процессором.
Кроме того, может быть много веб-интерфейсов.
Все это многообразие объединяет одно — база данных MySQL, которая часто запускается вместе с веб-интерфейсом.
Теперь, когда мы уже имеем представление о том, как устроена система тестирования, давайте посмотрим, по какому пути должно пройти написанное командой решение, чтобы оно (команда) получило заслуженный плюс (или минус) в рейтинге.
Прием решений от участников олимпиады
Решения участников Олимпиады хранятся на веб-сервере Олимпиады.Ему поручается следить за максимальным объемом кода решений, чтобы слишком большие решения останавливались на этапе приемки.
Список решений участников и параметры их запуска хранятся в базе данных.
Жизненный цикл среды изоляции начинается с запроса клиента тестирования к базе данных сервера Олимпиады.
В ответ на этот запрос клиент должен получить хранящийся в базе данных идентификационный номер отправленного решения, если в базе есть решения для проверки.
Если решений нет, то запрос необходимо повторить через некоторое время.
Пауза между запросами необходима для того, чтобы излишне не нагружать базу данных.
Итак, слишком крупные источники мы уже отсеяли.
Почему это делается? Вы можете рассчитать очень трудоемкое решение примерно за 5 минут на своем рабочем компьютере и сложить все в одну огромную карту в исходном коде.
А само решение будет выглядеть так: read(a), write(res[a]).
Мы уже разобрались с этим трюком.
Сборник
Прежде чем проверять решение, тестировщик должен собрать его программный код с помощью компилятора, определенного в параметрах, передаваемых с сервера.Чтобы соответствовать требованиям безопасности, клиент тестирования включает урезанные версии библиотек компилятора.
Из компиляторов исключены потенциально опасные библиотеки для работы с операционной системой на низком уровне.
Урезанные версии библиотек компилятора только усложняют доступ к сети и функциям WinAPI 32, но тестируемые приложения имеют возможность использовать библиотеки через вставки сборок.
За это отвечает программа noasm. Если будет обнаружено включение сборки, код программы не будет скомпилирован, а значит, не будет запущен потенциально вредоносный код, а сервер Олимпиады будет уведомлен об ошибке компиляции.
Большой.
Теперь у нас уже есть готовый бинарник, который только и ждет, когда в него подкинут пачку вкусных, свежих, сочных тестов.
Это нужно контролировать, иначе простая ошибка в программе (или злые происки участников, решивших победить неспортивным способом) могут вывести из строя систему тестирования.
На моей памяти такие смелые попытки однажды были пресечены дисквалификацией.
Ну да, это не соревнование черных шляп =) И тем более, большая часть пакостей, типа киллера #define, нами уже на этом этапе отсечена, так что места для безобразий осталось очень мало .
Запуск программ
Для программного управления ограничениями ресурсов и контроля доступа в ОС Windows доступна библиотека WinApi 32. Контролировать права доступа, ресурсы компьютера и работу процессов решено с помощью WinApi 32. В ОС Windows создается специальная учетная запись пользователя с ограниченными правами доступа для обеспечения безопасного запуска с ограничениями собранной программы.Имеет только один рабочий каталог с эксклюзивными правами доступа.
Банк тестов (входные и выходные данные) хранится на сервере Олимпиады.
Клиент тестирования имеет собственную локальную копию тестов.
Программу необходимо протестировать с помощью полного набора тестов.
Для этого тестер запускает скомпилированную программу на каждом тесте.
Входные данные передаются приложению в виде файла input.txt, размещенного в рабочем каталоге.
Скомпилированная программа запускается с помощью программы WinKill. С помощью WinAPI он устанавливает ограничения на использование системных функций и запускает программу от имени учетной записи с ограниченными правами.
Контроль во время исполнения
Программа WinKill запускает приложение и контролирует ограничения среды выполнения (процессорное время, память и общее время работы программы) с помощью WinApi. Он перехватывает все исключения и ошибки времени выполнения и получает код возврата при завершении работы приложения.Он уведомляет модуль тестирования обо всех произошедших событиях.
Если приложение попытается превысить лимиты, оно будет немедленно прекращено.
После завершения программы необходимо сравнить выходные данные решения участника олимпиады с ответом жюри.
Если программа WinKill по завершении возвращает нулевой код возврата, то модуль связи запускает специализированную программу проверки.
Если такая программа не предусмотрена условиями задачи, то выходные данные проверяются с помощью стандартной программы diff.
Вернитесь в исходное состояние.
Клиент тестирования должен вернуть все настройки в исходное состояние, чтобы каждое приложение запускалось в равных условиях: с одинаковыми параметрами среды.
Рабочий каталог приложения будет очищен: выходные данные, код программы, скомпилированный код и другие файлы будут удалены.
Система тестирования не предпринимает дополнительных действий по очистке оперативной памяти, поскольку память приложения очищается операционной системой автоматически при завершении процесса и освобождает ресурсы, занимаемые приложением.
После этого тестер будет готов к запуску следующего теста из набора.
Ну вот и все, что касается системы тестирования.
Рабочую версию можно увидеть здесь: olimpic.nsu.ru/tester/nsuts_olymp.cgi .
Хочу сказать большое спасибо моему другу Саше Кирову, одному из авторов НГУц, за помощь в написании статьи.
Около 70 процентов текста на этот раз составляют цитаты из его диссертации.
В следующей статье мы вместе с Наташей Поповой попытаемся рассказать, как проходит организационная часть олимпиады, ведь Всесибирская олимпиада — это не только ценный ресурс для многих крутых программистов, но и достаточно серьезный международный проект. где каждая мелочь должна быть продумана и организована.
Теги: #олимпиады по программированию #acm icpc #НГУ #спортивное программирование #спортивное программирование
-
Разработка Демо-Версии Для Nes - Heohdemo
19 Oct, 24 -
Развлекательный C#
19 Oct, 24 -
Еще Один Способ Организации Ооп В Js
19 Oct, 24
