Diferencia entre Conteo y Semáforos Binarios

Hay dos conceptos esenciales para construir programas concurrentes: sincronización y exclusión mutua. Veremos cómo estos dos tipos de bloqueos (los semáforos son más generalmente una especie de mecanismo de bloqueo) nos ayudan a lograr la sincronización y la exclusión mutua.

Un semáforo tiene dos partes : un contador y una lista de tareas que esperan acceder a un recurso en particular. Un semáforo realiza dos operaciones : wait (P) [esto es como adquirir un bloqueo], y release (V) [similar a release a lock] - estas son las únicas dos operaciones que se pueden realizar en un semáforo. En un semáforo binario, el contador lógicamente va entre 0 y 1. Puede pensar que es similar a un candado con dos valores : abierto/cerrado. Un semáforo de conteo tiene múltiples valores para contar.

Lo que es importante entender es que el contador de semáforos realiza un seguimiento del número de tareas que no tienen que bloquear, es decir, que pueden progresar. Las tareas se bloquean y se añaden a la lista del semáforo solo cuando el contador es cero. Por lo tanto, una tarea se agrega a la lista en la rutina P() si no puede progresar, y se "libera" usando la rutina V ().

Ahora, es bastante obvio ver cómo los semáforos binarios se pueden usar para resolver la sincronización y la exclusión mutua: son esencialmente bloqueos.

Ex. Sincronización:

thread A{
semaphore &s; //locks/semaphores are passed by reference! think about why this is so.
A(semaphore &s): s(s){} //constructor
foo(){
...
s.P();
;// some block of code B2
...
}

//thread B{
semaphore &s;
B(semaphore &s): s(s){} //constructor
foo(){
...
...
// some block of code B1
s.V();
..
}

main(){
semaphore s(0); // we start the semaphore at 0 (closed)
A a(s);
B b(s);
}

En el ejemplo anterior, B2 solo puede ejecutar después de que B1 haya finalizado la ejecución. Digamos que el hilo A viene se ejecuta primero-llega a sem.P (), y espera, ya que el contador es 0 (cerrado). El hilo B viene, termina B1 y luego libera el hilo A, que luego completa B2. Así que logramos la sincronización.

Ahora veamos la exclusión mutua con un semáforo binario:

thread mutual_ex{
semaphore &s;
mutual_ex(semaphore &s): s(s){} //constructor
foo(){
...
s.P();
//critical section
s.V();
...
...
s.P();
//critical section
s.V();
...

}

main(){
semaphore s(1);
mutual_ex m1(s);
mutual_ex m2(s);
}

La exclusión mutua también es bastante simple: m1 y m2 no pueden entrar en la sección crítica al mismo tiempo. Así que cada hilo está utilizando el mismo semáforo para proporcionar exclusión mutua para sus dos secciones críticas. Ahora, ¿es posible tener mayor concurrencia? Depende de las secciones críticas. (Piense en cómo de otra manera uno podría usar semáforos para lograr la exclusión mutua.. sugerencia : ¿necesariamente solo necesito usar un semáforo?)

Contando semáforo: Un semáforo con más de un valor. Veamos lo que esto implica: ¿un bloqueo con más de un valor? Tan abierto, cerrado, y ...hmm. ¿De qué sirve un bloqueo de varias etapas en exclusión o sincronización mutua?

Tomemos el más fácil de los dos:

Sincronización usando un semáforo de conteo: Digamos que tienes 3 tareas - #1 y 2 que quieres ejecutar después de 3. ¿Cómo diseñarías tu sincronización?

thread t1{
...
s.P();
//block of code B1

thread t2{
...
s.P();
//block of code B2

thread t3{
...
//block of code B3
s.V();
s.V();
}

Así que si su semáforo comienza cerrado, asegúrese de que el bloque t1 y t2 se agregue a la lista de semáforos. Luego viene todo t3 importante, termina su negocio y libera t1 y t2. ¿En qué orden son liberados? Depende de la implementación de la lista de semáforos. Podría ser FIFO, podría ser basado en alguna prioridad particular, etc. (Nota : piense en cómo organizaría sus P y V; s si quisiera que t1 y t2 se ejecutaran en algún orden particular, y si no estuviera al tanto de la implementación del semáforo)

(Averigüe: ¿Qué sucede si el número de V es mayor que el número de P?)

Exclusión mutua Usando semáforos de conteo: Me gustaría que construyas tu propio pseudocódigo para esto (te hace entender las cosas mejor!) - pero el concepto fundamental es este: un semáforo de conteo de counter = N permite que N tareas entren en la sección crítica libremente. Lo que esto significa es que tiene N tareas (o hilos, si lo desea) entran en la sección crítica, pero la N+1a tarea se bloquea (va en nuestra lista de tareas bloqueadas favoritas), y solo se deja pasar cuando alguien V el semáforo al menos una vez. Así que el contador de semáforos, en lugar de oscilar entre 0 y 1, ahora va entre 0 y N, permitiendo que N tareas libremente entrar y salir, no bloqueando a nadie!

Ahora, ¿por qué necesitarías una cerradura tan extraña? ¿No es el punto de exclusión mutua no permitir que más de un individuo acceda a un recurso?? Pensar. (Pista ...Usted no siempre solo tiene una unidad en su computadora, ¿verdad?..?)

Para pensar: ¿Se logra la exclusión mutua teniendo solo un semáforo de conteo? ¿Qué pasa si tienes 10 instancias de un recurso, y 10 hilos entran (a través del semáforo de conteo) e intentan usar la primera instancia?

La diferencia más básica entre contar y semáforo binario es que:

1. El semáforo binario no puede manejar la espera acotada, ya que es solo una variable que contiene un valor binario. Contando semáforos Puede manejar la espera acotada ya que ha convertido una variable en una estructura con una cola.

2. Implementación de Strcuture Semáforo binario : int s;

   Contando Semáforo: Estructura S { int s; Cola q; }

Usando el semáforo de conteo ahora, el proceso una vez ganado el CS(Sección Crítica) ahora tiene que esperar a que el otro obtenga el CS, por lo que ni un solo proceso se esfuerza. Cada proceso tiene una oportunidad para CS.