Однозадачность для соревнований по программированию
Я начну с вопроса, а затем перейду к объяснению необходимости:
Учитывая один файл исходного кода C++, который хорошо компилируется в современном g++ и использует только стандартную библиотеку, могу ли я создать операционную систему с одной задачей и запустить ее там?
EDIT : следуя комментарию Криса Лайвли, я бы лучше спросил: Какой самый простой способ вы можете предложить, чтобы попытаться настроить linux, чтобы эффективно дать мне однозадачное поведение. Тем не менее, похоже, что я получил хороший ответ, хотя я не сформулировал свой вопрос достаточно хорошо. Смотрите второй абзац в ответе сарнольда относительно планировщика.
Мотивация : В некоторых соревнованиях по программированию связь между программой конкурсанта и программой оценивания включает в себя огромное количество очень коротких взаимодействий.
Таким образом, использование getrusage для измерения времени, затраченного программой участника, является неточным, поскольку getrusage работает путем выборки процесса с постоянными интервалами (обычно около одного раза в 10 мс), которые слишком велики по сравнению с продолжительностью каждого взаимодействия.
Другой подход к синхронизации заключается в измерении времени до и после запуска программы с помощью чего-то вроде *clock_gettime*, а затем вычитания их значений. Мы также должны вычесть количество времени, затраченного на ввод/вывод, и это можно сделать, перехватывая printf и scanf, используя что-то вроде LD_PRELOAD и накапливая время, затраченное в каждом из них. эти функции, проверяя время непосредственно перед и сразу после каждого вызова printf / scanf (это нормально, чтобы требовать от участников использовать эти функции только для ввода-вывода).
Метод, предложенный в последнем абзаце, конечно, верен только при условии, что программа конкурсанта является единственной запущенной программой, поэтому я хочу иметь ОС с одной задачей.Чтобы запустить одновременно программу конкурсанта и программу оценивания, мне понадобится механизм, который, когда одна из этих программ попытается считывает входные данные и блоки, запускает другую программу, пока не запишет достаточно выходных данных. Я все еще считаю, что это одна задача, потому что программы не будут выполняться одновременно. "Переключение контекста" произойдет тогда, когда это необходимо.
Примечание : я осознаю тот факт, что существуют дополнительные проблемы с синхронизацией, такие как управление питанием процессора, но я хотел бы начать с решения проблемы контекстных переключений и многозадачности.
1 ответ:
Во-первых, то, что я думаю, лучше всего удовлетворит ваши потребностина самом деле будет языком интерпретатором - тем, который вы можете использовать для отслеживания "времени выполнения" программы в некоторых специально созданных единицах, таких как "mems" для представления доступа к памяти или "циклы" для представления скорости различных инструкций. Кнут MMIX в своем искусстве компьютерного программирования может обеспечить именно такую функциональность, хотя Python, Ruby, Java, Erlang - это все достаточно разумные интерпретаторы, которые могут обеспечить некоторое количество команд / стоимость / стоимость доступа к памяти, если вы сделаете достаточно переписывания. (Но потеря C++, очевидно.)
Еще один подход, который может хорошо работать для вас-если использовать его с особой осторожностью-заключается в выполнении ваших задач программирования в классе
SCHED_FIFO
илиSCHED_RR
обработки в реальном времени. Программы, запущенные в одном из этих классов приоритетов реального времени, не будут уступатьдругим процессам в системе, позволяя им доминировать над всеми другими задачами. (Обязательно запускайте своиsshd(8)
иsh(1)
в более высоком классе реального времени, чтобы вы могли убивать задачи-беглецы.)