Informática

Programación en Unix

Compartir 0 Me sirvió 0 No me sirvió

'Programación en Unix'

Instituto Profesional

LA ARAUCANA

IPLA

Ingeniería (E) en Computación e Informática

TAREA

“SEMAFOROS Y EL PROBLEMA DE LOS FUMADORES DE CIGARRILLOS”

Santiago

JULIO 2000

PLANTEAMIENTO DEL PROBLEMA

Problema de los fumadores de cigarrillos (S.S.Patil)

Tres fumadores están representado por los procesos F1, F2, y F3. Tres vendedores están representados por los procesos V1, V2, y V3. Para fumar, cada fumador necesita, tabaco, papel para tabaco y un fosforo; cuando dispone de estos recursos el fumador fuma un cigarrillo hasta terminarlo y entonces que elegible para fumar de nuevo. F1 tiene tabaco, F2 tiene papel y F3 tiene fosforos. V1 vende tabaco y papel, V2 vende papel para tabaco y fosforos y V3 vende fosforos y tabaco. V1, V2 y V3 trabajan en exclusión mutua, solo uno d elos procesos puede trabajar a la vez y el siguiente vendedor no puede trbajar hasta que los recursos sumistrados por el vendedor anterior hallan sido consumidos por un fumador.

F1 tabaco V1 tabaco - papel

F2 Papel V2 papel - fosforos

F3 Fosforos V3 fosforo - tabaco

Solución Algoritmica

Procedimiento Principal

Numero_fumador es igual a 1

Vendedor_numero es igual a 2

Par Begin

Ejecute procedimiento Fumador uno

Ejecute procedimiento Fumador dos

Ejecute procedimiento Fumador tres

ParEnd

Fin procedimiento

Procedimiento Fumador uno

Mientras sea verdadero

Mientras numero_fumador es igual a 2 ó numero_fumador es igual a 3 y vendedor_numero es igual a 1 ó vendedor_numero es igual a 3

Fumador uno compra a vendedor dos

Fumador uno fuma

Numero_fumador queda en 2

Vendedor_numero queda en 3

Fumador uno espera fumar otra vez

Fin Mientras

Fin procedimiento

Procedimiento Fumador dos

Mientras sea verdadero

Mientras numero_fumador es igual a 1 ó numero_fumador es igual a 3 y vendedor_numero es igual a 1 ó vendedor_numero es igual a 2

Fumador dos compra a vendedor tres

Fumador dos fuma

Numero_fumador queda en 3

Vendedor_numero queda en 1

Fumador dos espera fumar otra vez

Fin Mientras

Fin procedimiento

Procedimiento Fumador tres

Mientras sea verdadero

Mientras numero_fumador es igual a 1 ó numero_fumador es igual a 2 y vendedor_numero es igual a 2 ó vendedor_numero es igual a 3

Fumador tres compra a vendedor uno

Fumador tres fuma

Numero_fumador queda en 1

Vendedor_numero queda en 2

Fumador tres espera fumar otra vez

Fin Mientras

Fin procedimiento

SEMAFOROS

En 1965 E.W. Dijkstra sugirió el uso de una variable entera para contar el número de desbloqueos guardados para uso futuro. En esta proposición, se introdujo un nuevo tipo de variable, llamada semáforo. Un semáforo podía tener el valor 0, lo que indicaba que no se habian guardado desbloqueos o algún valor positivo si quedaban pendientes uno o más desbloqueos.

Dijkstra propuso contar con dos operaciones, DOWN y UP (generalizaciones de SLEEP y WAKEUP, respectivamente). La operación DOWN con un semáforo verifica si el valor es mayor que 0. Si es así, disminuye el valor (es decir, utiliza un desbloqueo almacenado) y simplemente prosigue. Si el valor es 0, el proceso se bloquea. La verificación del valor, su alteración y posiblemente su bloqueo se realizan en una sola acción atómica indivisible. Se garantiza que una vez que se haya dado inicio a una operación del semáforo, ningún otro proceso puede accesarlo hasta que se complete la operación.

La operación UP incrementa el valor del semáforo direccionado. Si uno o más procesos estaban bloqueados en ese semáforo, incapaces de completar una operación DOWN anterior, el sistema elige uno de ellos al azar y le permite completar su operación (DOWN). Por lo tanto, después de una operación UP con un semáforo con procesos bloqueados en él, el semáforo seguirá siendo 0, pero habrá un proceso bloqueado menos en él. La operación de incrementar el semáforo y desbloquear un proceso también es indivisible. Ningún proceso se bloquea realizando una operación UP, así como tampoco ningún proceso se bloquea realizando una operación WAKEUP en el modelo anterior.

Además, en el manuscrito original de Dijkstra, él utilizó los nombres de P y V en lugar de Down y UP, respectivamente, pero ya que éstos no tienen significado mnemotécnico para quienes no hablan alemán, utilizaremos los términos DOWN y UP en su lugar.

Los semáforos resuelven el problema del desbloqueo perdido. Es esencial que se implanten en forma indivisible. La forma normal consiste en implementar UP y DOWN como llamadas al sistema, donde el sistema operativo desactiva brevemente todas las interrupciones mientras prueba el semáforo, lo actualiza y bloquea el proceso, si es que se necesita. Como todas estas acciones emplean sólo una cuantas instrucciones, no se causa daño al desactivar las interrupciones. Si se utilizan múltiples CPU, cada semáforo debe protegerse con una variable de cierre, utilizando la instrucción TSL para asegurar que sólo una CPU a la vez examine el semáforo.

SEMAFOROS EN UNIX

Semáforos multi-valuados, no binarios

Se puede crear un arreglo de semáforos con una simple llamada

Posibilidad de especificar una sola operación en un solo semáforo

Posibilidad de especificar un conjunto de operaciones en un arreglo de semáforos

En UNIX, cuando un proceso aborta (exit() ) libera todos los candados, ( locks ), que retenía en sus semáforos

Los semáforos tienen dueños, modos de acceso y timestamps

Librerías:

#include <sys/types.h>

#include <sys/ipc.h>

#include <sys/sem.h>

PARTICULARIDADES DE LOS SEMAFOROS EN UNIX

Petición de m recursos del conjunto { R1, R2......... Rm }

Cada uno protegido por un semáforo (Si)

Acceso de m recursos : R1, R2......... Rm

P(S1) P(S2).......... P(Sm)

Atomicidad no garantizada:

Posibilidad de bloqueo de un proceso y de que

que éste bloquee a otro

UNIX: posibilidad de realizar conjunto de operaciones sobre un conjunto de semáforos. Si una operación no es posible, ninguna se realiza.

Adquisición de m recursos del mismo tipo:

m operaciones P sucesivas del mismo semáforo

mismas consecuencias

Despertar procesos en espera del valor de un semáforo:

UNIX despierta a todos los procesos qu% se encontraban en espera de un evento, dejando al administrador, que decida quien entra.

ESTRUCTURA DE DATOS SEMAFOROS

EJEMPLO RELACION ESTRUCTURA

semget(key, nsems, flag)

Crea un arreglo de semáforos de tamaños nsems

Obtiene un manejador de un conjunto de semáforos

id = semget(key, nsems, flag)

key_type key

llave de identificación del semáforo

int nsems

número de semáforos requerido en el segmento

int flag

si tiene el valor de:

IPC_CREAT crea un semáforo con permisos especificados en perms:

(IPC_CREAT | perms)

0 obtiene un manejador del semáforo existente

int id

manejador del semáforo

semop(id,ops,nops

Permite realizar atómicamente nops operaciones, definidas en **ops, sobre el arreglo de semáforos ubicado en semid

Primitiva bloqueante

semop(id,ops,nops)

int id

manejador de semáforos, obtenido en semget()

struct sembuf **ops

definición de la operación a partir de la estructura:

struct sembuf{

short sem_num; /* número semáforo */

short sem_op; /* operación semáforo */

short sem_flg; /* parámetro operación */

}

int nops

número de operaciones

semop(id, ops, nops)

+ Operaciones atómicas sobre semáforos

Naturaleza operaciones semop()

Operación elemental que engloba un número de semáforo y una operación. Esta puede tener 3 tipos de valor

1) Valor estrictamente Negativo

+ Especifica una operación tipo P(S)

+ Tiene por objeto disminuir el valor del semáforo(S)

+ Si la operación no es posible el proceso se duerme

esperando que el valor del semáforo aumente.

2) Valor estrictamente Positivo

+ Especifica una operación tipo V(S)

+ Tiene por objeto aumentar el valor del semáforo(S)

+ Tiene el efecto de despertar todos los procesos en espera

de que el valor del semáforo (S) aumente

3) Valor 0 (nulo)

+ Permite probar si el valor del semáforo es 0

+ Si no es el caso el proceso es bloqueado

Definición operaciones en semop()

if (sem_op < 0)

if (semval >= abs(sem_op ) => semval = semval - abs(sem_op)

else

+ incrementar valor semcnt de la estructura sem

+ proceso bloqueado hasta que:

1) semval >= abs(sem_op )

2) arreglo semáforos desaparece

3) proceso recibe señal indica que semcnt es decrementada

if (sem_op > 0 ) => semval = semval + sem_op

(liberaración recursos que controlaba el semáforo)

if (sem_op = 0 )

if (semval = 0) => regreso inmediato

else

+ incrementar en 1 el campo semzcnt de la estructura sem

+ proceso suspendido hasta que:

1) semval = 0, (semzcnt es decrementado)

2) arreglo semáforos desaparece

3) proceso recibe señal

Parámetros operaciones en semop()

Bandera IPC_NOWAIT

Operaciones no bloqueantes

Si durante la ejecución de semop( ) una operación no puede

ser ejecutada ninguna lo es pero el proceso no se bloquea.

Si ( sem_op es negativo)

si (semval < abs(sem_op) ) entonces

regreso inmediato con estatus de error

errno = 11, (EAGAIN)

Si ( sem_op es cero )

si (semval es diferente de cero) entonces

regreso inmediato con estatus de error

errno = 11 (EAGAIN)

No aplica para sem_op positivo

Bandera SEM_UNDO

Prevención de bloqueo accidental de recursos

Cuando esta activada y se asignan recursos (sem_op > 0) kernel maneja un valor de ajuste para recordar cuantos “recursos” se le han asignado

Si el proceso termina, voluntaria o involuntariamente el kernel verifica si el proceso tiene ajustes pendientes y en caso positivo aplica el ajuste correspondiente.

Relación con operaciones:

sem_op > 0 => ajuste = ajuste - sem_op

sem_op < 0 => ajuste = ajuste + abs(sem_op)

Creación semáforos

/* Construcción de un arreglo de n semáforos con llave k */

int construye_sem(k, n)

key_t k;

int n;

{

int semid, i;

/* intenta accesar un conjunto de semáforos con la llave k */

/* Si existe lo destruye */

if ( (semid = semget(k,n,0)) != -1)

semctl(semid, 0, IPC_RMID);

/* Valores semáforos inicializados en cero, lo que implica */

/* que todos los recursos están bajo candado */

/* Hay que quitarles ese candado a cada uno */

if ((semid = semget(k, n, IPC_CREAT | 0600)) != -1) {

for (i=0; i<=n; i++)

V(semid, i);

}

return semid;

}

Lock de un sémaforo P(S)

/* Poniendo un candado al semáforo n*/

void P(sem, n)

int sem;

int n;

{

struct sembuf sop;

/* construcción arreglo operaciones de un elemento */

sop.sem_num = n;

sop.sem_op = -1; /* bloquea solo una unidad */

sop.sem_flg = 0;

/* bloquea hasta que el recurso sea liberado */

semop(sem, &sop, 1);

}

Unlock de un semáforo V(S)

/* Quitando un candado al semáforo n del conjunto sem */

void V(sem, n)

int sem;

int n;

{

struct sembuf sop;

/* construcción arreglo operaciones de un elemento */

sop.sem_num = n;

sop.sem_op = 1; /* +1 -> desbloquea */

sop.sem_flg = 0;

semop(sem, &sop, 1);

}

semctl(id, num, cmd, arg)

Permite realizar diferentes comandos, cmd , sobre un arreglo de semáforos apuntado por id, o sobre algun(os) semáforos del mismo arreglo.

Inicialización, borrado, etc.

semctl(id, num, cmd, arg)

int id

manejador del semáforo

int num

especificación de los semáforos a procesar dentro del arreglo

int cmd

comando u operación a realizar

union semnum arg

argumento de la operación definida dentro de la unión semnum

El argumento de operación de semctl()

union semnum arg

arg es una unión definida de la siguiente forma:

union semnum {

int val; /* usado en SETVAL */

struct semid_ds *buf; /* usado en IPC_STAT y IPC_SET*/

ushort *array; /* usado en GETALL y SETALL*/

}

la estructura de semid es:

struct semid_ds {

struct ipc_perm sem_perm; /* estructura permiso */

int *pad; /* usado por sistema */

ushort sem_nsems; /* número semáforos */

time_t sem_otime; /* tiempo último semop */

time_t sem_ctime; /* tiempo último cambio */

}

siendo la estructura del permiso:

struct ipc_perm {

ushort uid; /* id del usuario actual*/

ushort gid; /* id del grupo actual */

ushort cuid; /* id del usuario creador */

ushort cgid; /* id del grupo creador */

ushort mode; /* modo de acceso */

short pad1; /* usado por el sistema*/

long2 pad2; /* usado por el sistema */

}

Posibles operaciones en semctl()

Función para borrar semáforos

/* Borra semaforo especificado por sem */

int borra_sem (sem)

int sem;

{

int status;

status= semctl (sem, 0, IPC_RMID);

if (status < 0) {

fprintf (stderr, “\n Error %d al borrar el semáforo \n”, errno);

return (-1);

}

else

return (status);

}

Función asignar un valor x al e-nésimo semáforo

/* Asigna el valor x al semáforo n de sem */

int asig_val.sem(sem, n, x)

int sem, x, n;

{

union {

int val;

struct semid_ds *buf;

ushort *array;

} semctl_arg;

semctl_arg.val = x

if (semctl(sem, n, SETVAL, semctl_arg) <0) {

fprintf (stderr, “Error %d en la asignación de valores \n”, errno);

return (-1);

}

else

return (0);

}

Verificar valor e-nésimo semáforo

/* Regresa el valor del semáforo n de sem */

int valsem_n(sem, n)

int sem, n;

{ int semval;

union {

int val;

struct semid_ds *buf;

ushort *array;

} semctl_arg;

semval = semctl (sem, n, GETVAL, semctl_arg);

if (semval < 0) {

fprintf (stderr, “Error % d en lectura valor semáforo \n”, errno);

return (-1);

}

else

return (semval);

}

Función regresa valor semáforo sem

/* Regresa el valor del semáforo sem */

int imp_semval (sem)

int sem;

{ int semval;

union {

int val;

struct semid_ds * buf;

vshort * array;

} semctl_arg;

semval = semctl (sem, 0, GETVAL, semctl_arg)

if (semval < 0) {

fprintf (stderr,“Error %d en lectura semáforo: % d \n”,

errno, sem);

return (-1);

}

else

return (semval);

}

Ejemplo aplicación funciones

#include <stdio.h>

#include <errno.h>

#include <sys/ types..h>

#include <sys/ ipc.h>

#include <sys/shm.h>

#include <sys/ sem.h>

#include “semop.h”

#define KEY_SEM IPC_PRIVATE

#define KEY_SEM2 (key_t) 275463

#define KEY_SEM3 37416

main ()

{

int sema3, mutex, sema, i, n;

if ((sema3 = semget(KEY_SEM3, 5, IPC_CREAT|0666 )) <O) {

fprintf(stderr, “Error %d en creación directa semáforo \n”,errno);

exit (1);

}

if ((sema = construye_sem(KEY_SEM, 3)) >= 0)

printf (“Creación exitosa \n” );

/* se crea un arreglo de semáforos con un solo elemento */

if ((mutex = construye_sem(KEY_SEM2, 1)) < 0) {

printf(“Error en la creación \n”);

exit(3) ;

}

/* impresión de los valores de los semáforos: */

printf (“Impresión valores sema3: \n”) ;

for (i=0; i<5; i++)

printf (“ Valor sem[%d]:%d\n” , i, valsem_n(sema3, i)) ;

printf (“Valor semáforo mutex:%d”, imp_semval(mutex) ) ;

/* asignado los valores de 1, 2 y 3 al semáforo 0, 1 y 2, */

/* respectivamente, de sema3 */

for (i=1: i<=3; i ++)

asig_val_sem(sema, i-1, i) ;

/* asignando el valor se 5 al semáforo mutex */

asig_val_sem (mutex, 0, 5) ;

/* impresión de los valores de los semáforos: */

printf (“ Impresión semáforos después asignación:\n”) ;

printf (“ Impresión valores sema3: \n” ) ;

for (i=0; i<3; i++)

printf(“Valor sem %d de sem3: %d \n”, i, valsem_n(sema3, i)

printf (“Valor semáforo mutex:%d”, imp_semval (mutex) ) ;

/* impresión de los semáforos existentes en ese momento */

printf (“\n Semáforos existentes:\n” ) ;

system ( “ipcs -s”) ;

/*borrar los semáforos*/

borra_sem (sema3) ;

borra_sem (mutex) ;

/* impresión de los semáforos */

printf (“\n Semáforos existentes:\n”);

system ( “ipcs -s” ) ;

}

Ejemplo : Implementación Productor Consumidor

* Dos procesos

Consumidor

Productor

* Tres semáforos

vacío

lleno

mutex

* Sección Crítica

memoria compartida

cada proceso despliega:

El contenido del almacen y el número de

casillas libres y llenas

* Fuera de sección crítica

produce_item()

Despliega: “Produciendo un item”

consume_item()

Despliega: “Consumiendo item”

Código del ejemplo 1

#include <stdio.h>

#include <sys/types>

#include <sys/ipc.h>

#include <sys/shm.h>

#include <sys/sem.h>

#include <semop.h>

#define KEY_SHMEM (key_t) 447885

#define KEY_MUTEX (key_t) 478854

#define KEY_LLENO (key_t) 788544

#define KEY_VACIO (key_t) 885447

#define N 10

#define LLENO 5

#define SEGSIZE (size of (struct info))

int mutex, full, empty; /*variables semaforos */

int tmp_prod, tmp_cons; /* variables tiempo asignacion*/

int i;

int id;

struct info {

int index;

int almacen[N];

};

struct shmid_ds shmbuf;

struct info *ptg;

main()

{

int k;

/* verificando valores de entrada */

if (argc != 3 ) {

printf(“Error: %s tmp:cons tmp:prod \n”,argv[0]);

exit(1);

}

/* asignando tiempos de atencion */

tmp_cons=atoi(argv[1]);

tmp_prod=atoi(argv[2]);

/* creación de la memoria compartida */

id = shmget(KEY_SHMEM, SEGSIZE, IPC_CREAT | 0666);

if (id <0) {

fprintf(stderr,“ Error en el shmget \n“);

exit(1);

}

ptg = (struct info*) shmat(id, 0, 0);

/* creando los semáforos */

mutex = crea_semas(KEY_MUTEX, 1);

lleno = crea_semas(KEY_LLENO, 1);

vacío = crea_semas(KEY_VACIO, 1);

/* limpiando la pantalla, inicializando e imprimiendo valores

semáforos */

system(“clear”);

printf(“ Valores Iniciales Semáforos: \n”);

asig_val_sem(mutex, 0, 1);

asig_val_sem(vacío, 0, N-LLENO);

asig_val_sem(lleno, LLENO);

imprime_valores(1);

/* incialización del almacen */

for (k=0; k<LLENO; k++)

if (k <LLENO)

ptg->almacen[k] = 1;

else

ptg->almacen[k] = 0;

ptg->index = LLENO;

/*inicialización simulación y lanzamiento de los procesos */

printf(“PROCESO CONSUMIDOR”);

printf(“\t\t\t\t\t PROCESO PRODUCTOR \n”);

if(fork() == 0){

productor();

}

else {

consumidor();

}

/* desatando memoria y borrando memoria y semáforos */

shmdt(0);

shmctl(id, IPC_RMID, shmbuf);

semctll(mutex, 0, IPC_RMID);

semctll(lleno, 0, IPC_RMID);

semctll(vacio, 0, IPC_RMID);

}

productor()

{

printf(“ \nEmpieza ejecución productor %d \n”, getpid());

while (1) {

produce_item();

P(vacío, 0);

P(mutex, 0);

enter_item(item);

V(mutex, 0);

V(lleno, 0);

sleep(tmp_prod);

}

consumidor()

{

printf(“ \nEmpieza ejecución consumidor %d \n”,getpid());

while (1) {

P(lleno, 0);

P(mutex, 0);

remove_item(item);

V(mutex, 0);

V(vacío, 0);

consume_item();

sleep(tmp_cons);

}

/* produciendo un elemento */

produce_item()

{

printf(“Proc %d produciendo un item \n”, getpid());

}

/*consumiendo un elemento */

consume_item()

{

printf(“\t\t\t\t't Proc %d consumiendo un item \n”, getpid());

}

/* introduciendo un elemento al almacen */

enter_item()

{

ptg->almacen[ptg->index] = 1;

ptg->index++;

imprime_almacen(“prod”);

}

/* eliminando un elemento del almacen */

remove_item()

{

ptg->index--;

ptg->almacen[ptg->index] = 0;

imprime_almacen(“cons”);

}

/*imprimiendo valores iniciales de los semáforos */

imprime_valores()

{

printf(“\tSemaforo \t\tValor \n”);

printf(“\tmutex:: \t\t%d\n, imp_semval(mutex));

printf(“\tlleno: \t\t%d\n, imp_semval(lleno));

printf(“\tvacio: \t\t%d\n\n, imp_semval(vacio));

}

/*imprimiendo valores almacen y el numero de casillas llenas y v

acías */

imprime_almacen()

{

int j,ct;

ct=0;

printf(“\t\tAlmacen (%s): “,tipo);

printf(“|”);

for (j=0; j<N; j++) {

printf(“%d|”,ptg->almacen[j]);

if ( ptg->almacen[i] )

ct++;

}

printf(“\n\t\t casillas vacias: %d casillas llenas: %d \n”,N-ct,ct);

}

Corrida ejemplo 1

Valores Iniciales Semáforos:

Semáforo Valor

mutex: 1

lleno: 5

vacio: 5

PROCESO CONSUMIDOR PROCESO PRODUCTOR

Empieza ejecución proceso productor 1662

Proc 1662 produciendo un item

Almacen( prod):|1|1|1|1|1|1|0|0|0|0|

casillas vacias: 4 casillas llenas: 6

Empieza ejecucion proceso consumidor 1659

Alamcen( cons):|1|1|1|1|1|0|0|0|0|0|

casillas vacias: 5 casillas llenas: 5

Proc 1659 consumiendo un item

Proc 1662 produciendo un item

Almacen( prod):|1|1|1|1|1|1|0|0|0|0|

casillas vacias: 4 casillas llenas: 6

Alamcen( cons):|1|1|1|1|1|0|0|0|0|0|

casillas vacias: 5 casillas llenas: 5

Proc 1659 consumiendo un item

Proc 1662 produciendo un item

Alamcen(cons):|1|1|1|1|0|0|0|0|0|0|

casillas vacias: 4 casillas llenas: 6

Proc 1659 consumiendo un item

Almacen(prod):|1|1|1|1|1|0|0|0|0|0|

casillas vacias: 5 casillas llenas: 5

Proc 1662 produciendo un item

Valores Iniciales semaforos:

Semáforo Valor

mutesx: 1

lleno: 5

vacio: 5

PROCESO CONSUMIDOR PROCESO PRODUCTOR

Empieza ejecución proceso consumidor 1663

Almacen (cons): |1|1|1|1|1|1|0|0|0|0|

casillas vacias: 6 casillas llenas: 4

Proc 1663 consumiendo un item

Empieza ejecucion proceso productor 1666

Proc 1666 produciendo un item

Almacen: (prod): |1|1|1|1|1|0|0|0|0|0|

casillas vacias: 5 casillas llenas: 5

Almacen: (cons): |1|1|1|1|1|1|0|0|0|0|

casillas vacias: 6 casillas llenas: 4

Proc 1663 consumiendo un item

Almacen: (cons): |1|1|1|0|0|0|0|0|0|0|

casillas vacias: 7 casillas llenas: 3

Proc 1663 consumiendo un item

Proc 1666 produciendo un item

Almacen: (cons): |1|1|0|0|0|0|0|0|0|0|

casillas vacias: 8 casillas llenas: 2

Proc 1663 consumiendo un item

Almacen: (prod): |1|1|1|0|0|0|0|0|0|0|

casillas vacias: 7 casillas llenas: 3

Almacen: (cons): |1|1|0|0|0|0|0|0|0|0|

casillas vacias: 8 casillas llenas: 2

Proc 1663 consumiendo un item

Almaceb (cons): |1|0|0|0|0|0|0|0|0|0|

casillas vacias: 9 casillas llenas: 1

Proc 1663 consumiendo un item

Proc 1666 produciendo un item

Valores Iniciales semaforos:

Semáforo Valor

mutesx: 1

lleno: 5

vacio: 5

PROCESO CONSUMIDOR PROCESO PRODUCTOR

Empieza ejecución proceso productor 1670

Almacen (prod): |1|1|1|1|1|1|0|0|0|0|

casillas vacias: 4 casillas llenas: 6

Empieza ejecucion proceso productor 1667

Almacen: (cons): |1|1|1|1|1|0|0|0|0|0|

casillas vacias: 5 casillas llenas: 5

Proc 1667 consumiendo un item

Proc 1670 produciendo un item

Almacen: (prod): |1|1|1|1|1|1|0|0|0|0|

casillas vacias: 4 casillas llenas: 6

Proc 1670 produciendo un item

Almacen: (prod): |1|1|1|1|1|1|1|0|0|0|

casillas vacias: 3 casillas llenas: 7

Proc 1670 produciendo un item

Almacen: (prod): |1|1|1|1|1|1|1|1|0|0|

casillas vacias: 2 casillas llenas: 8

Almacen: (cons): |1|1|1|1|1|1|1|0|0|0|

casillas vacias: 3 casillas llenas: 7

Proc 1667 consumiendo un item

Proc 1670 produciendo un item

Almacen: (prod): |1|1|1|1|1|1|1|1|0|0|

casillas vacias: 2 casillas llenas: 8

Proc 1670 produciendo un item

Almacen: (prod): |1|1|1|1|1|1|1|1|1|0|

casillas vacias: 1 casillas llenas: 9

Almacen: (cons): |1|1|1|1|1|1|1|1|0|0|

casillas vacias: 2 casillas llenas: 8

Ejemplo2: Hoja de cálculo concurrente

Algoritmo solución

• Memoria compartida: contiene una hoja de cálculo:

+ Ultimo elemento renglón: suma elementos renglón

+ Ultimo elemento columna: suma elementos columna

• Dos procesos:

+ PA: updater

Cambia periódicamente una celda arbitraria a un

valor arbitrario

+ PB: checker

Imprime periódicamente la hoja de calculo,

checa que las sumas estén correctas

Algoritmo updater:

• Escoger una celda y un valor arbitrario

• Escribir el valor arbitrario en la celda escogida

• Calcular y actualizar el total del renglón

• Calcular y actualizar el total de la columna

Algoritmo checker:

• ciclo en todos los renglones:

+ calculo de la suma de todas las celdas del renglón

+ if (sum != total) => printf("Error \n")

• ciclo en todas las columnas:

+ calculo de la suma de todas las celdas de la columna

+ if (sum != total) => printf("Error \n");

Código:

• make_random_entry() updater

• print_and_check() checker

• semop.h funciones manejo semáforos

(make_semas, lock y unlock )

• main()

- crea segmento memoria compartido inicalizándolo en cero

- crea los arrglos de semáforos para renglones y columnas

- forks()

- se manda llamar varias veces a la función updater

- se manda llamar varias veces a la función checker

Código del ejemplo

# include<stdio .h>

# include<sys/types.h>

# include<sys/ipc.h>

# include<sys/shm.h >

# include<sys/sem.h>

# include “semop.h”

int totalrow, totalcol ;

int row_ semas, col _semas ;

#define CELL (s, r, c ) ( *(( s ) + (( r ) *NCOLS) + ( c )))

#define NROWS 8

#define NCOLS 8

#define SHEET_KEY 1841

/* ------------------------------ main --------------------------------------*/

main ( )

{

int id, row, col, *sheet ;

totalrow = NROWS -1;

totalcol = NCOLS - 1;

id = shmget (SHEET_KEY, NROWS*NCOLS*sizeof(int) , IPC_CREAT | 0600);

if ( id < 0) {

printF(“Error : falla en el shmget \n”) ;

exit (1) ;

}

sheet = (int * )shmat(id, 0, 0) ;

if (sheet < = ( int *)(0) ) {

printf (“Error : falla en el shmat \n”) ;

exit (2) ;

}

for ( row = 0; row < NROWS; row++)

for (col= 0; col < NCOLS; col++)

CELL(sheet , row, col ) = 0 ;

row_semas = make_semas( SHEET_KEY, NROWS );

col_semas = make_semas( SHEET_KEY+1, NCOLS ) ;

if (( row_semas < 0 ) | | (col_semas < 0 )) {

printf ( “Error : falla en el make_semas \n ) ;

}

if ( fork ( ) ) {

while (1)

print_and_check(sheet) ;

}

else {

while (1)

make_random_entry (sheet) ;

}

void make_random_entry( s )

int *s;

{

int row, col, old, new ;

row = rand( ) % (NROWS - 1) ;

col = rand( ) % (NCOLS - 1);

new = rand( ) % 1000 ;

P(row_semas, row) ;

P(col_semas, col) ;

/ * Principio de la SECCION CRITICA */

old = CELL(s, row, col);

CELL(s , row , col ) = new;

CELL(s , row , totalcol ) + = (new - old );

CELL(s , totalrow , col ) + = (new - old);

V(col_semas, col) ;

V(row_semas, row);

/* Fin de la sección crítica */

usleep (5000) ;

}

void print_and_check( s )

int *s ;

{

int row , col ,sum , totalbad ;

static int scount = 0;

totalbad =0 ;

scount ++; /* controlador numero hoja de cálculo */

for ( row = 0 ; row < NROWS ; row ++ ) {

sum = 0;

P(row_semas, row) ; /* Principio de la sección crítica */

for ( col = 0 ; col < NCOLS ; col++) {

if ( col != totalcol)

sum += CELL ( s , row , col );

printf ( “%6d” , CELL(s , row , col )) ;

}

if ( row != totalrow )

totalbad + = (sum !=CELL ( s , row , totalcol )) ;

V(row_semas, row); /* Fin de la sección crítica */

printf ( “\n” ) ;

}

for ( col = 0 ; col < totalcol ; col++ {

sum = 0 ;

P(col_ semas, col) ; /* Principio de la sección crítica */

for ( row = 0; row < totalrow; row++ )

sum += CELL(s, row, col );

totalbad += (sum != CELL (s, totalrow, col)) ;

V(col_semas, col) ; /*Fin de la sección crítica*/

}

if (totalbad)

printf ( “\ n Error hoja de calculo no. %d \n , scount );

if ( ( scount % 10) == 0) /* se imprime cada 10 hojas */

printf ( “\n Hoja calculo no. %d procesada\n” , scount );

printf ( “\n =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\n”);

sleep (1) ;

}

Ejemplo de ejecución

0 0 0 0 0 0 0 0

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

0 0 0 0 0 0 0 0

0 0 886 0 0 0 0 886

0 0 0 0 0 0 0 0

0 0 899 0 0 84 0 983

0 0 0 0 0 0 0 0

0 0 2606 0 0 288 0 0

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

480 0 821 933 873 57 834 3998

159 0 342 521 0 0 955 1977

82 262 886 912 0 759 0 2901

0 42 992 719 98 0 781 2632

860 0 69 0 0 182 116 1227

44 0 0 685 734 0 714 2177

0 849 0 0 643 37 351 1880

1625 1153 3110 3875 2348 1850 3751 0

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

Estructura de operaciones: sembuf

(qué semáforo, operación, indicador operación)

Objeto de estructura

semid_ds

(control / autorización operaciones)

Objeto de estructura

sem

(valor, procesos esperando)

Arreglo semáforos

struct semid_ds {

struct ipc_perm sem_perm; /* estructura permiso */

int *pad; /* usado por sistema */

ushort sem_nsems; /* número semáforos */

time_t sem_otime; /* tiempo último semop */

time_t sem_ctime; /* tiempo último cambio */

}

struct sembuf{

short sem_num; /* número semáforo */

short sem_op; /* operación semáforo */

short sem_flg; /* parámetro operación*/

}

struct sem {

ushort semval /* valor semáforo */

short sempid /* último proceso que hizo un semop*/

ushort semcnt /* # procesos esperan semval incremente su valor */

ushort semzcnt /* # procesos esperan semval = 0 */

}

Identificador

del arreglo de

semáforos

struct sem

[0]

[2]

[1]

semzcnt

semcnt

sempid

semval

struct semid_ds

sem_ctime

sem_ nsems = 3

sem_otime

structure

sem _perm

pad

Operación a realizar:

valores negativos:

esperar por el semáforo y

apropiarselo (lock)

valores positivos:

liberarlos

sem_flg

sem_op

sem_num

operaciones fancy

generalmente cero

cada elemento del

arreglo es de tipo

struct sembuf

número de

semáforo

número de

operaciones

en el arreglo

arreglo de

operaciones

de semáforo

manejador

semop(id, ops, nops)

struct sem {

ushort semval /* val sem */

short sempid /* último semop*/

ushort semcnt /* incrementar semal */

ushort semzcnt /* semaval = 0 */

}

struct sembuf{

short sem_num; /* número semáforo */

short sem_op; /* operación semáforo */

short sem_flg; /* parámetro* oper. */

}

0: no pasa nada

SEM_UNDO

previene el bloqueo accidental de

semáforos, (proceso muere des-

pués de hacer un P(S) )

IPC_NOWAIT

operaciones no bloqueantes:

devuelve el control en caso de que

no se pueda realizar la operación

especificada en semop( )

struct sembuf{

short sem_num; /* número semáforo */

short sem_op; /* operación semáforo */

short sem_flg; /* parámetro* oper. */

}

struct sem

[0]

struct semid_ds

[2]

[1]

Incrementa el

semáforo en 1

Espera que el

segundo semáforo

sea cero

sem _ flg = 0

struct sembuf oper[2] ={

2,0,0,

2,1,SEM_UNDO }

struct sembuf oper[2];

oper[0].sem_num = 2;

oper[0].sem_ op = 0;

oper[0].sem_flg = 0;

oper[1].sem_num = 2;

oper[1].sem_ op = 1;

oper[1].sem_ flg = SEM_UNDO;

[1]

[0]

sem_ flg= SEM_UNDO

sem _ op = 1

sem _ num = 2

sem _ op = 0

semop ( id , &oper , 2 )

semzcnt

semcnt

sempid

semval

sem - ctime

sem - nsems = 3

sem - otime

structure

sem - perm

pad

id = semget ( KEY, 3, IPC_CREAT | 0600)

IPC_RMID

E: modificación valores campos de la es-

tructura de permisos de semid_ds de id,

a partir de lo contenido en arg.buf

-1 si no

éxito

tuvo

operación

buf

IPC_SET

id, info es almacenada en arg.buf

extracción estructura semid_ds de

no.

-1

éxito

tuvo

operación

buf

IPC_STAT

primeros semáforos

"sennum"

los

inicialización

no.

-1

éxito

tuvo

operación

array

semáforos

(cantidad),

Número,

SETALL

valor dado

semáforo

del

inicialización

no.

-1

éxito

tuvo

operación

val

número de semáforo

Especificación

SETVAL

el semáforo

que realizó una operación sobre

proceso

último

del

Identificación

número de semáforo

Especificación

GETPID

"semnum" primeros semáforos

los

valores

los

contiene

arreglo

no.

-1

éxito

tuvo

operación

array

semáforos

(cantidad),

Número,

GETALL

R: Valor del semáforo

número de semáforo

Especificación

GETVAL

que el semáforo tome un valor de cero

procesos en espera de

Número

número de semáforo

Especificación

GETZCNT

que el semáforo aumente su valor

espera

procesos

Número

número de semáforo

Especificación

GETNCNT

Valor regreso (R), y efecto (E)

Interpretación arg

semnum

operación

semctl(id, semnum, operacion, arg)

Celda

elegida por

update.

Celda no usada para

simplificar el programa.

Arreglo de

semáforos de

renglón.

“locked”

por el

updater

“locked”

por el

checker

“locked”

por el updater

Arreglo de

semáforos de

columna.

7 4 15 9 12 47

3 21 5 2 6 37

8 18 6 1 13 46

20 10 17 6 5 58

38 53 43 18 36

Supresión de la entrada en la tabla de semáforos

Tal vez te pueda interesar:

Descargar

Enviado por:	Sergio Merino Morales
Idioma:	castellano
País:	Chile

Palabras clave:

Procesos, Factores excluyentes Solución algorítmica Desbloqueos Operación DOWN, UP Dijkstra Instrucción TSL Estructura Operaciones Parámetros Funciones

Te va a interesar