concurrency - tecnica - ojo bovino anatomia
R-limitado esperando el bloqueo de Peterson (1)
Tienes razón, el algoritmo de Peterson para dos hilos es justo (también conocido como el primero que llega).
Vamos a definir (de forma bastante natural) que la sección de puerta sea las líneas 6-9 en el código, y la sección de espera sea la línea 10. Supongamos que D 0 j ➝ D 1 k y ambos hilos están en sus correspondientes secciones de espera. En este caso, flag[0]==true , flag[1]==true y victim==1 ; por lo tanto, el hilo 0 puede salir de su sección de espera, mientras que el hilo 1 puede no salir. Entonces, el subproceso 0 va primero, es decir, CS 0 j ➝ CS 1 k y el bloqueo de Peterson tiene 0-limitado esperando, es decir, es justo.
Sin embargo, creo que la pregunta tiene sentido. Es un ejercicio, el primero para la sección no muy difícil, pero aún así creo útil para verificar si se comprenden los conceptos. El libro no dice que el candado de Peterson es justo; en cambio, pregunta (quizás de una manera un tanto complicada) probarlo como un ejercicio.
En The Art of Multiprocessor Programming , rev. 1st Ed., En el cap. 2, Ejercicio 9 es el siguiente (parafraseado):
Defina r-limitado esperando que un algoritmo mutex signifique que D A j ➝ D B k ⇒ CS A j ➝ CS B k + r . ¿Hay alguna manera de definir una entrada para el algoritmo de Peterson de modo que proporcione una espera limitada en r?
El libro usa ➝ para definir un orden total en la precedencia de los eventos, donde X ➝ Y significa que el evento X comenzó y se completó antes de que Y comenzara. D A es el evento de "puerta de enlace" para un hilo A, que es el evento de la solicitud para ingresar a la sección crítica. CS A es el evento de sección crítica para el subproceso A.
Para cualquier evento X A , X A i es la i-ésima ejecución del evento X en el hilo A.
Ahora llego a la pregunta: me parece que el algoritmo de Peterson es completamente justo (espera de 0 límites). Además, creo que la espera limitada por r implica k-limitado esperando por todos k> r. Entonces, esta pregunta no tiene sentido, ya que Peterson debería satisfacer la espera limitada r para todos los r.
¿La pregunta es una "simplificación" del algoritmo de Peterson, ya que está solicitando una relajación de las restricciones?
Esto es autoaprendizaje, no tarea.
El código del algoritmo de bloqueo Peterson, tomado del libro:
1 class Peterson implements Lock {
2 // thread-local index, 0 or 1
3 private volatile boolean[] flag = new boolean[2];
4 private volatile int victim;
5 public void lock() {
6 int i = ThreadID.get();
7 int j = 1 - i;
8 flag[i] = true; // I’m interested
9 victim = i; // you go first
10 while (flag[j] && victim == i) {}; // wait
11 }
12 public void unlock() {
13 int i = ThreadID.get();
14 flag[i] = false; // I’m not interested
15 }
16 }