¿Cuál es la mejor manera de probar una implementación de Mutex?

Question

¿Cuál es la mejor manera de probar una implementación de un mutex correcta? (Es necesario implementar un mutex, la reutilización no es una opción viable)

Lo mejor que se me ocurre es tener muchos (N) hilos simultáneos intentando iterativamente acceder a la región protegida (I) veces, que tiene un efecto secundario (por ejemplo, actualizar a un sistema global) para que el número de accesos + escrituras se pueda contar para garantizar que el número de actualizaciones en el mundo sea exactamente (N) * (I).

¿Alguna otra sugerencia?

Answer 1

Esto me recuerda esta pregunta acerca de FIFO semaphore test. En pocas palabras mi respuesta fue:

• Incluso si usted tiene una especificación, tal vez no transmitir su intención exactamente
• se puede demostrar que el algoritmo cumple con la especificación, pero no el código (D.Knuth)
• prueba revelan sólo la presencia del insecto, no su ausencia (Dijkstra)

Así que su propuesta parece razonable la mejor forma de hacerlo. Si desea aumentar su confianza, use fuzzing para aleatorizar la programación y la entrada.

Answer 2

La prueba formal es mejor que las pruebas para este tipo de cosas.

Las pruebas le mostrarán que, siempre y cuando no tenga mala suerte, todo funcionó. Pero una prueba es un instrumento contundente; no puede ejecutar la secuencia correcta exacta para causar fallas.

Es muy difícil probar todas las posibles secuencias de operaciones disponibles en el hardware para garantizar que su mutex funcione en todas las circunstancias.

Las pruebas no carecen de valor; muestra que no cometió ningún error de codificación obvio.

Pero realmente necesita una inspección de código más formal para demostrar que hace las cosas correctas en el momento adecuado para que un cliente se apodere atómicamente del recurso de bloqueo requerido para el mutex correcto. En muchas plataformas, hay instrucciones especiales para implementar esto, y si está usando una de ellas, tiene una gran posibilidad de hacerlo bien.

De manera similar, debe mostrar que la versión es atómica.

Answer 3

Con algo así como un mutex, volvemos a la antigua regla de que las pruebas solo pueden demostrar la presencia de errores, no la ausencia. Un año de prueba probablemente le dirá menos que simplemente poner el código para inspección, y preguntar si alguien ve un problema con él.

Answer 4

Si las pruebas no funcionan para usted, entonces vaya con la prueba. Asegúrese de probar todos los casos de uso posibles. Descubra cómo se usará exactamente esto, quién lo usará y, nuevamente, cómo se usará. Cuando vaya a la ruta de prueba, asegúrese de ejecutar cada prueba una y otra vez (millones, miles de millones, tantas veces como sea posible con el tiempo de prueba que tenga).

Trate de ser al azar porque la aleatoriedad le dará la mejor oportunidad de cubrir todos los escenarios en un número limitado de pruebas. Asegúrese de utilizar los datos que se utilizarán y los datos que no se pueden usar, pero que podrían usarse, y asegúrese de que los datos no dañen las cerraduras.

Por cierto, a menos que sepa mucho sobre las matemáticas y los métodos formales, no tendrá ninguna posibilidad de encontrar una prueba.

Answer 5

Estoy con todos los demás que esto es increíblemente difícil de probar de manera concluyente, no tengo ni idea de cómo hacerlo, ¡no es útil, lo sé!

Cuando dice implementar un mutex y esa reutilización no es una opción, ¿es eso por razones técnicas como que no hay implementación Mutex en la plataforma/sistema operativo que está utilizando o por algún otro motivo? ¿Está envolviendo alguna forma de "bloqueo" de nivel de sistema operativo y llamándola implementación de su Mutex una opción, por ejemplo, sección crítica en windoze, posix Condition Variables? Si puede ajustar un bloqueo de sistema operativo de nivel inferior, entonces su posibilidad de hacerlo bien es mucho mayor.

En caso de que aún no lo haya hecho, vaya y lea Herb Sutter's Effective Concurrency artículos. Debería haber algunas cosas en estos que valgan algo para ti.

De todos modos, algunas cosas a tener en cuenta en sus análisis:

• Si el mutex es recursiva (es decir, puede bloquear el mismo hilo que múltiples veces) y luego asegurarse de que hacer algunas pruebas recuento de referencias.
• Con su variable global que usted modificar sería mejor si esto fuera varible que no se puede escribir en atómicamente. Por ejemplo, si es en una plataforma de 8 bits, utilice una 16 o variable de 32 bits que requiere instrucciones de ensamblaje múltiples para escribir.
• Examine detenidamente la lista de montaje. Dependiendo de la plataforma de hardware, el ensamblaje no se traduce directamente en cómo se puede optimizar el código ...
• Solicite a otra persona que no haya escrito el código que también escriba algunas pruebas.
• prueba en tantas máquinas diferentes, con diferentes especificaciones que se puede (suponiendo que se trata de 'propósito general' y no para una configuración de hardware específico)

Buena suerte!