Preguntas reales del examen Icpc do
Palabras clave Arquitectura del sistema de evaluación en línea de lámparas ACM/ICPC
Número de clasificación de la Biblioteca de China: TP311.52 Código de identificación del documento: a.
0 Introducción
El propósito de ACM/ICPC es permitir que los estudiantes universitarios demuestren plenamente su capacidad para utilizar computadoras para analizar y resolver problemas. El sistema de arbitraje online juega un papel muy importante. Los miembros del equipo de capacitación pueden elegir varios temas para desafiarse a sí mismos en el sistema de evaluación en línea, mejorarse y aprender varias estructuras de datos y algoritmos en la capacitación centralizada organizada por una organización unificada, el efecto de la capacitación se puede mejorar especificando temas; apoya La función de competencia mejora aún más el entusiasmo por el aprendizaje de los miembros del equipo de capacitación y también puede simular el entorno de competencia y cultivar la unidad y la capacidad de cooperación de aquellos equipos que planean participar en la competencia ACM/ICPC.
La mayoría de los sistemas OJ son de código cerrado y no se puede obtener su código fuente para modificarlo y ampliarlo para satisfacer las necesidades existentes. El equipo de formación ACM/ICPC de la Universidad Normal de Mudanjiang lanzó su propio DO en 2010. Sin embargo, el sistema tiene varios problemas: en primer lugar, es ineficiente y no puede soportar la presión de la ronda preliminar del Concurso anual de programación de la Universidad Normal de Mudanjiang. En segundo lugar, debido a que el sistema no utiliza tecnología sandbox para ejecutar el código de usuario, existen riesgos de seguridad; , lo que puede conducir directamente al secuestro del servidor. Desde entonces, han aparecido varios sistemas de DO de código abierto en Google Code, pero el diseño de la arquitectura aún es imperfecto y no puede ser compatible con el formato de datos del sistema original. Por lo tanto, es necesario volver a desarrollar un nuevo sistema de DO con un diseño razonable para resolver fundamentalmente los problemas anteriores y proporcionar un entorno de aprendizaje estable y utilizable para el equipo de capacitación.
1 Diseño de la arquitectura del sistema
Para facilitar a los usuarios, este sistema adopta la arquitectura B/S. Siempre que los usuarios utilicen una computadora con acceso a la red, podrán acceder a ella a través de un navegador. Según la situación específica del sistema, el diseño se divide en las siguientes cuatro partes: (1) sistema del sitio web (lado web); (2) proceso de evaluación del demonio de escucha central;
En términos de diseño, el proyecto desacopla completamente varios módulos principales del sistema. Por un lado, se pueden desarrollar múltiples módulos en paralelo; por otro lado, el desacoplamiento de cada módulo facilita la modificación y expansión del sistema y, en consecuencia, también mejora la reutilización de cada módulo. Por ejemplo, cuando otras escuelas necesitan implementar un sistema OJ o una plataforma operativa con interfaces funcionales completamente diferentes, pueden adoptar directamente el núcleo de evaluación de este proyecto para evitar el desarrollo repetido.
2 Diseño e implementación del núcleo de evaluación
Como parte central del sistema de evaluación en línea, especialmente la necesidad de monitorear las operaciones del usuario, debe involucrar muchas tecnologías relacionadas, especialmente aquellas que están estrechamente relacionados con la capa inferior del sistema. En Linux, las llamadas al sistema generalmente son implementadas por el programa de usuario que ingresa al kernel activando la interrupción suave No. 80 o ejecutando instrucciones de CPU relacionadas con la plataforma, como SYSCALL/SYSENTER. El kernel obtiene la entrada del programa de usuario a través de registros y realiza las correspondientes. operaciones después de una estricta inspección.
Las principales llamadas al sistema involucradas en este sistema son fork, setitimer, Executive, wait, ptrace, setrlimit, chroot, setuid, etc.
(1) La llamada al sistema fork crea un nuevo proceso copiando el contexto del proceso de llamada. (2) La llamada al sistema setitimer se utiliza para configurar el temporizador. (3) La llamada al sistema ejecutable se utiliza para cargar un nuevo programa ejecutable y reemplazar el espacio de direcciones del proceso actual. (4) La llamada al sistema de espera permite que el proceso principal se bloquee hasta que ocurra algún evento en el proceso secundario.
(5) llamada al sistema ptrace (5) la llamada al sistema ptrace es una función que permite al proceso principal interceptar y modificar llamadas al sistema a nivel de usuario. Puede monitorear y controlar otros procesos, y también puede cambiar los registros y las imágenes del kernel en el. Proceso hijo para lograr la interrupción. Depuración de puntos y seguimiento de llamadas al sistema. (6) La llamada al sistema setrlimit puede cambiar los límites de recursos del proceso. (7) La llamada al sistema chroot hace que el proceso que llama utilice un directorio como su propio directorio raíz, lo que restringe el acceso del proceso y sus subprocesos a archivos fuera del directorio. (8) La llamada al sistema setuid permite que un proceso cambie su ID de usuario efectivo. En este sistema, el código enviado por el usuario puede ser malicioso y el programa compilado debe ejecutarse en el servidor, por lo que debe monitorearse de cerca para evitar el daño causado por el código malicioso. Entre los cuatro lenguajes admitidos por este sistema, C, C++ y Pascal se compilan para generar código local, que se puede utilizar para crear un entorno limitado a través de llamadas al sistema Linux (principalmente fork, ejecutable, chroot, setuid y ptrace) para restringir el malware. código de acceso a archivos y permisos de sistemas de control, especialmente las llamadas al sistema disponibles a través de ptrace, garantizando así la seguridad del sistema en gran medida.
La detección del tiempo de ejecución es el mecanismo de monitoreo del tiempo de ejecución más importante y complejo. En este sistema, los procesos del usuario se monitorean a través de la llamada al sistema ptrace. Cada vez que un proceso de usuario inicia una llamada al sistema o recibe alguna señal, el proceso de usuario cede temporalmente el control al núcleo de monitoreo. El núcleo de monitoreo monitoreará estrictamente los parámetros del proceso del usuario para garantizar que no realice operaciones que pongan en peligro la seguridad del sistema: (1) Verifique si el programa sale normalmente. (2) Verifique si el programa recibe una señal anormal. (3) Utilice el número de paginación del proceso para calcular si los recursos de memoria utilizados por el proceso exceden el límite. (4) Compruebe si la llamada al sistema de proceso es legal.
Solo si no hay problemas con las cuatro pruebas anteriores, el proceso del usuario puede continuar ejecutándose.
Debido a que las preguntas se pueden dividir en tipos generales y tipos de sentencias especiales según el número de resultados legales, es necesario realizar sentencias separadas para diferentes tipos. (1) Los tipos de preguntas comunes solo tienen resultados legales, y solo necesita juzgar la coherencia entre el programa de usuario y la respuesta estándar. (2) Para 2) preguntas de tipo de juicio especial, el nombre del programa SPJ y el método de transmisión de datos se acuerdan en este sistema, incluida la salida estándar, la salida del usuario y los datos del programa SPJ. El núcleo de evaluación llama al programa SPJ. completar el proceso de evaluación final.
3 Evaluar el diseño y la implementación de la capa central
Cada vez que un usuario envía un nuevo código, se llamará al contenedor para obtener los detalles del código de la base de datos. La información que necesita atención en esta etapa incluye principalmente: (1) El código enviado por el propio usuario y sus atributos clave (como el tipo de idioma). (2) El tipo de usuario que envía el código es un usuario normal o administrador. (3) Si la cuestión a la que pertenece este código se encuentra en un concurso en curso. (4) Si este código ha sido evaluado.