Однозадачность для соревнований по программированию


Я начну с вопроса, а затем перейду к объяснению необходимости:

Учитывая один файл исходного кода C++, который хорошо компилируется в современном g++ и использует только стандартную библиотеку, могу ли я создать операционную систему с одной задачей и запустить ее там?

EDIT : следуя комментарию Криса Лайвли, я бы лучше спросил: Какой самый простой способ вы можете предложить, чтобы попытаться настроить linux, чтобы эффективно дать мне однозадачное поведение. Тем не менее, похоже, что я получил хороший ответ, хотя я не сформулировал свой вопрос достаточно хорошо. Смотрите второй абзац в ответе сарнольда относительно планировщика.

Мотивация : В некоторых соревнованиях по программированию связь между программой конкурсанта и программой оценивания включает в себя огромное количество очень коротких взаимодействий.

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

Другой подход к синхронизации заключается в измерении времени до и после запуска программы с помощью чего-то вроде *clock_gettime*, а затем вычитания их значений. Мы также должны вычесть количество времени, затраченного на ввод/вывод, и это можно сделать, перехватывая printf и scanf, используя что-то вроде LD_PRELOAD и накапливая время, затраченное в каждом из них. эти функции, проверяя время непосредственно перед и сразу после каждого вызова printf / scanf (это нормально, чтобы требовать от участников использовать эти функции только для ввода-вывода).

Метод, предложенный в последнем абзаце, конечно, верен только при условии, что программа конкурсанта является единственной запущенной программой, поэтому я хочу иметь ОС с одной задачей.

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

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

1 3

1 ответ:

Во-первых, то, что я думаю, лучше всего удовлетворит ваши потребностина самом деле будет языком интерпретатором - тем, который вы можете использовать для отслеживания "времени выполнения" программы в некоторых специально созданных единицах, таких как "mems" для представления доступа к памяти или "циклы" для представления скорости различных инструкций. Кнут MMIX в своем искусстве компьютерного программирования может обеспечить именно такую функциональность, хотя Python, Ruby, Java, Erlang - это все достаточно разумные интерпретаторы, которые могут обеспечить некоторое количество команд / стоимость / стоимость доступа к памяти, если вы сделаете достаточно переписывания. (Но потеря C++, очевидно.)

Еще один подход, который может хорошо работать для вас-если использовать его с особой осторожностью-заключается в выполнении ваших задач программирования в классе SCHED_FIFO или SCHED_RR обработки в реальном времени. Программы, запущенные в одном из этих классов приоритетов реального времени, не будут уступатьдругим процессам в системе, позволяя им доминировать над всеми другими задачами. (Обязательно запускайте свои sshd(8) и sh(1) в более высоком классе реального времени, чтобы вы могли убивать задачи-беглецы.)