operating system - sincronizacion - ¿Qué es el progreso y la espera acotada en la sección crítica?
sincronizacion de procesos (4)
En general, una solución al problema de la sección crítica debe satisfacer tres condiciones:
Exclusión mutua : acceso exclusivo de cada proceso a la memoria compartida. Solo un proceso puede estar en su sección crítica en un momento dado.
Progreso : si no hay ningún proceso en su sección crítica, y si uno o más subprocesos desean ejecutar su sección crítica, entonces se debe permitir que cualquiera de estos subprocesos entre en su sección crítica.
Espera acotada : después de que un proceso realiza una solicitud para ingresar a su sección crítica, existe un límite para la cantidad de otros procesos que pueden ingresar a su sección crítica, antes de que se conceda la solicitud de este proceso. Entonces, una vez que se alcanza el límite, el sistema debe otorgar el permiso de proceso para ingresar a su sección crítica. El propósito de esta condición es asegurarse de que cada proceso tenga la oportunidad de ingresar a su sección crítica para que ningún proceso se quede sin aliento para siempre.
Estaba leyendo Problema de la sección crítica de Conceptos del sistema operativo por Peter B. Galvin. De acuerdo a esto
1) El progreso es: si no se está ejecutando ningún proceso en su sección crítica y algunos procesos desean ingresar a sus secciones críticas, solo los procesos que no se ejecutan en su sección restante pueden participar en decidir cuál ingresará a su sección crítica a continuación, y esto La selección no puede posponerse indefinidamente.
Y
2) La espera limitada es : existe un límite, o límite, en el número de veces que otros procesos pueden ingresar a sus secciones críticas después de que un proceso haya realizado una solicitud para ingresar su sección crítica y antes de que se otorgue dicha solicitud.
No entiendo lo que el autor quiere decir en ambos casos.
¿Podría por favor hacerme entender dando un ejemplo apropiado relacionado con esta definición?
Gracias.
En primer lugar, permítanme introducir algo de terminología. Una sección crítica (CS) es una secuencia de instrucciones que pueden ejecutarse como máximo por un proceso al mismo tiempo. Cuando se usan secciones críticas, el código se puede dividir en las siguientes secciones:
// Some arbitrary code (such as initialization).
EnterCriticalSection(cs);
// The code that constitutes the CS.
// Only one process can be executing this code at the same time.
LeaveCriticalSection(cs);
// Some arbitrary code. This is called the remainder section.
La primera sección contiene algún código como el código de inicialización. No tenemos un nombre para esa sección. La segunda sección es el código que intenta ingresar al CS. La tercera sección es la propia CS. La cuarta sección es el código que sale de la sección crítica. La quinta y última sección se llama la sección restante que puede contener cualquier código. Tenga en cuenta que la propia CS puede ser diferente entre los procesos (considere, por ejemplo, un proceso que recibe solicitudes de un cliente e insértelos en una cola y otro proceso que procesa estas solicitudes).
Para asegurarse de que una implementación de secciones críticas funcione correctamente, hay tres condiciones que deben cumplirse. Mencionaste dos de ellos (que explicaré a continuación). El tercero es la exclusión mutua que obviamente es vital. Vale la pena señalar que la exclusión mutua se aplica solo al CS y la sección de licencia. Sin embargo, las otras tres secciones no son exclusivas.
La primera condición es el progreso . El propósito de esta condición es asegurarse de que algún proceso se encuentre actualmente en la CS y esté realizando algún trabajo o, si hubo al menos un proceso que desea ingresar a la CS, lo hará y luego realizará algunos trabajos. En ambos casos, se está haciendo algo de trabajo y, por lo tanto, todos los procesos están progresando en general.
Progreso: si no se está ejecutando ningún proceso en su sección crítica y algunos procesos desean ingresar a sus secciones críticas, solo los procesos que no se ejecutan en su sección restante pueden participar para decidir cuál ingresará a la siguiente sección crítica, y esta selección no puede ser pospuesto indefinidamente.
Entendamos esta definición oración por oración.
Si no se está ejecutando ningún proceso en su sección crítica.
Si hay un proceso que se está ejecutando en su sección crítica (aunque no se especifique explícitamente, esto también incluye la sección de licencia), entonces esto significa que se está realizando algún trabajo. Así que estamos progresando. De lo contrario, si este no fuera el caso ...
Y algunos procesos desean ingresar a sus secciones críticas.
Si ningún proceso desea ingresar a sus secciones críticas, entonces no hay más trabajo que hacer. De lo contrario, si hay al menos un proceso que desea ingresar a su sección crítica ...
entonces solo aquellos procesos que no se están ejecutando en su sección restante
Esto significa que estamos hablando de los procesos que se están ejecutando en cualquiera de las dos primeras secciones (recuerde, ningún proceso se está ejecutando en su sección crítica o en la sección de licencia) ...
Pueden participar en decidir cual entrará a su sección crítica a continuación,
Dado que hay al menos un proceso que desea ingresar a su CS, de alguna manera debemos elegir uno de ellos para ingresar a su CS. ¿Pero quién va a tomar esta decisión? Aquellos procesos que ya solicitaron permiso para ingresar a sus secciones críticas tienen derecho a participar en la toma de esta decisión. Además, los procesos que pueden desear ingresar a sus CS pero que aún no han solicitado el permiso para hacerlo (esto significa que se están ejecutando en la primera sección) también tienen derecho a participar en la toma de esta decisión.
y esta selección no se puede posponer indefinidamente.
Esto indica que tomará un tiempo limitado para seleccionar un proceso para ingresar a su CS. En particular, no se producirá ningún interbloqueo o bloqueo vital . Entonces, después de esta cantidad limitada de tiempo, un proceso ingresará a su CS y hará algunos trabajos, por lo tanto avanzando.
Ahora explicaré la última condición, es decir, la espera acotada . El propósito de esta condición es asegurarse de que cada proceso tenga la oportunidad de ingresar a su sección crítica para que ningún proceso se quede sin aliento para siempre . Sin embargo, tenga en cuenta que ni esta condición ni el progreso garantizan la imparcialidad. Una implementación de un CS no tiene que ser justa.
Espera acotada: existe un límite o límite en el número de veces que otros procesos pueden ingresar a sus secciones críticas después de que un proceso haya realizado una solicitud para ingresar su sección crítica y antes de que se otorgue dicha solicitud.
Entendamos esta definición oración por oración, comenzando desde la última.
después de que un proceso haya realizado una solicitud para ingresar a su sección crítica y antes de que se otorgue dicha solicitud.
En otras palabras, si hay un proceso que ha solicitado ingresar a su CS pero aún no lo ha hecho. Llamemos a este proceso P.
Existe un límite o límite en el número de veces que otros procesos pueden ingresar a sus secciones críticas
Mientras P está esperando para ingresar a su CS, otros procesos también pueden estar esperando y algún proceso se está ejecutando en su CS. Cuando abandona su CS, se debe seleccionar algún otro proceso para ingresar al CS, que puede ser o no P. Supongamos que se seleccionó un proceso distinto de P. Esta situación puede pasar una y otra vez. Es decir, otros procesos tienen la oportunidad de ingresar a sus CS pero nunca P. Tenga en cuenta que se está progresando, pero otros procesos no lo hacen por P. El problema es que P no tiene la oportunidad de hacer ningún trabajo. Para evitar la inanición, debe haber una garantía de que P finalmente ingresará a su CS. Para que esto suceda, la cantidad de veces que otros procesos ingresan a sus CS debe ser limitada. En este caso, P definitivamente tendrá la oportunidad de ingresar a su CS.
Me gustaría mencionar que la definición de una CS se puede generalizar para que la mayoría de los procesos de N se ejecuten en sus secciones críticas donde N es un entero positivo. También hay variantes de las secciones críticas del lector-escritor.
Requisitos para decirle a la solución de sincronización es correcta o no
1). Exclusión mutua: en cualquier momento, solo un proceso debe estar presente dentro de la sección crítica.
2). Progreso: el proceso que está fuera de la sección crítica y quien no quiera ingresar a la sección crítica, entonces dicho proceso no debe detener el otro proceso interesado para ingresar a su sección crítica. Si un proceso está teniendo éxito para detener otro proceso interesado, el progreso no está garantizado o está garantizado. La sección crítica debe ser libre.
3). Espera acotada: el tiempo de espera de un proceso fuera de una sección crítica debe ser limitado.
4). Arquitectónico neutro: -no hay ninguna suposición con respecto al hardware
Exclusión mutua
Ningún proceso puede estar presente simultáneamente en la sección crítica en cualquier momento, solo un proceso puede entrar en la sección crítica en cualquier momento.
Imagen para el progreso:
Progreso
Ningún proceso que se ejecute fuera de la sección crítica debe impedir que el otro proceso interesado entre en su sección crítica cuando, de hecho, la sección crítica es gratuita.
Espera acotada
Ningún proceso debe tener que esperar eternamente para entrar en la sección crítica. debe haber un límite en la posibilidad de entrar en la sección crítica. Si no se satisface la espera acotada, existe la posibilidad de inanición.
Nota
Ninguna suposición está relacionada con H / W o velocidad de procesamiento.