Estos son los apuntes de José Piquer. Además se encuentran disponibles en youtube videos de las 23 clases de José Piquer. Hay un índice del contenido en los comentarios para las clases 2, 3, 4 y 5. El que vea los siguientes videos sin el índice agregue un comentario con el contenido por favor. Observen que el botón que aparece en la esquina de arriba a la izquierda en el video permite seleccionar el número de la clase que desean ver. Pero cuidado, la enumeración de las clases de esta página no corresponde uno a uno a la enumeración de los 23 videos, ni siquiera el orden.

En los apuntes de Luis Mateu se explican los mismos conceptos de esta página pero con más detalle.

Ver contenido extendido en Introducción.

Ejemplo estudiado: copy.c

#include <stdio.h>
 
/* 
 * Copia la entrada en su salida sin modificaciones
 */
 
int main() {
 
    int c;
 
    while((c=getchar()) != EOF)
        putchar(c);
 
    return 1;
}

Pueden probar compilando este programa:

% gcc copy.c -o copy

Y jugando a manejar su entrada y salida:

% ./copy >out
hola
^D
% ./copy <out
hola
% ./copy <out >out2
% ./copy <out2 | ./copy >out3
% 

Ver contenido extendido en tipos y variables.

char: 8 bits, 1 byte

short: 16 bits, 2 bytes

long: 32 bits, 4 bytes

long long: 64 bits, 8 bytes

int: el entero de esta arquitectura

float: 32 bits double: 64 bits

Ver contenido extendido en punteros y strings.

Ejemplos de punteros a strings: string.c

/*
 * Implementacion "pedagogica" de varias funciones de manejo de strings
 * de la libc
 * Sirve de ejemplo de compilacion separada y encapsulamiento de funciones
 * utiles para mas de un programa
 */
 
#include "string.h"
#include <stdlib.h>
 
/*
 * Un string es "" (un 0 en la posicion [0])
 * o un arreglo de caracteres terminados en 0
 * No puede ser NULL
 * Regla; retornar algo. Si no saben que', retornen uno de los argumentos
 *        (permite anidar llamados)
 */
 
/* 
 * Retorna el largo del string en bytes, sin contar el 0 final
 */
/* version tradicional */
int Strlen1(char s[]) {
    int i=0;
 
    /* Primero, busco el 0 al final */
    while(s[i] != 0)
	i++;
 
    return i;
}
 
int Strlen(char *s) {
    char *p = s;
 
    /* Primero, busco el 0 al final */
    while(*p != '\0')
	p++;
 
    /* p apunta al 0 final y s al inicio, la diferencia da el largo total */
    return p-s;
}
 
/*
 * Copia orig a dest, supone que en dest ya hay memoria suficiente para
 * almacenar Strlen(orig)+1 bytes
 */
char *Strcpy(char *dest, char *orig) {
    char *p = dest;
 
    while(*orig != '\0')
	*dest++ = *orig++;
 
    *dest = '\0';
    return p;
}
 
/*
 * Pega orig al final de dest, borrando el 0 final de dest
 * Esto MODIFICA dest, no lo copia
 */
char *Strcat(char *dest, char *orig) {
    char *p = dest+Strlen(dest);
 
    while(*orig)
	*p++ = *orig++;
 
/* No nos falta copiar el cero final? */
    return dest;
}
 
/*
 * Compara alfabeticamente s1 y s2. Si s1 < s2 retorna -1, s1 == s2 0 y
 * si s1 > s2 1
 */
int Strcmp(char *s1, char *s2) {
    while(*s1 == *s2 && *s1 != '\0') {
	s1++; s2++;
    }
 
/* 
 * Los caracteres en ASCII estan codificados como enteros consecutivos
 * en orden lexicografico, asi que puedo aprovecharlo
 * ESTO NO FUNCIONA CON LOS ACENTOS
 */
    if(*s1 == *s2) return 0;
    if(*s1 > *s2)  return 1;
    else           return -1;
}
 
/*
 * Esta funcion pide memoria dinamica para un nuevo string donde
 * se copia el contenido del argumento
 */
char *Strdup(char *s) {
    char *p;
 
    p = (char *)malloc(Strlen(s)+1);
    if(p == NULL) return p;   /* No hay memoria disponible */
    Strcpy(p, s);
    return p;
}
 
 
/*
 * busca un caracter en el string
 * retorna el puntero al char o NULL si no lo encuentra
 */
char *Strchr(char *s, char c) {
 
    while(*s != c && *s != '\0')
	s++;
 
    return (*s == c) ? s : NULL;
}

Ejemplo estudiado: lista1.c

Notar que es posible trabajar una lista como una estructura iterativa (con while o for) o recursiva, considerando que una lista es: vacia o (elemento, lista)

#include <stdio.h>
#include <stdlib.h>
 
/* Ejemplo simple de lista enlazada de enteros y sus usos clasicos */
 
struct nodo {
    int val;
    struct nodo *next;
};
 
/* 
 * Una lista puede verse como una iteracion: "arreglo" de elementos
 * o como una estructura recursiva: NULL o elto seguido de una lista
 */
 
print_inv(struct nodo *q) { /* recorrido inverso */
    if(q == NULL)
	return;
 
    print_inv(q->next);
    printf("%d ", q->val); /* si lo movemos a la linea anterior que pasa? */
    return;
}
 
struct nodo *copy_list(struct nodo *q) {
    struct nodo *l;
 
    if(q == NULL) return NULL;
 
    l = (struct nodo *)malloc(sizeof(struct nodo));
    if(l == NULL) {
	fprintf(stderr, "no mem\n");
	exit(1);
    } 
 
    l->val = q->val;
    l->next = copy_list(q->next);
    return l;
}
 
free_list(struct nodo *l) {
    if(l == NULL) return;
 
/* Ojo con liberar en buen orden: no perder los eltos que necesito! */
    free_list(l->next);
    free(l);
}
 
main() {
    int i;
    struct nodo *p, *q, *q2, *aux;
 
    q = NULL;
 
/* Construir */
    for(i=0; i<100; i++) {
	p = (struct nodo *)malloc(sizeof(struct nodo));
   	if(p == NULL) {
	    fprintf(stderr, "no mem\n");
	    exit(1);
	}
	p->val = i; p->next = q;
	q = p;
    }
 
/* Recorrer */
    printf("lista es: ");
    for(p=q; p != NULL; p=p->next)
	printf("%d ", p->val);
    printf("\n");
 
/* Buscar un elemento */
    for(p=q; p != NULL && p->val != 10; p=p->next)
	;
 
/* Borrar el siguiente: 9 */
    if(p != NULL && p->next != NULL) {
	aux = p->next;
 	p->next = p->next->next;
	free(aux);
    }
 
/* Recorrer */
    printf("lista-9 es: ");
    for(p=q; p != NULL; p=p->next)
	printf("%d ", p->val);
    printf("\n");
 
/* Recorrido inverso: mejor recursivo */
    printf("lista inv es: ");
    print_inv(q);
    printf("\n");
 
/* Retorna una copia de la lista */
   q2 = copy_list(q);
 
/* Recorrer */
    printf("copia de lista-9 es: ");
    for(p=q2; p != NULL; p=p->next)
	printf("%d ", p->val);
    printf("\n");
 
/* liberar iterativamente */
    for(p=q; p!=NULL; ) {
	aux = p;
	p = p->next;
	free(aux);
    }
 
/* liberar recursivamente */
    free_list(q2);
}

Ejercicio propuesto: hacer la función:

struct nodo *reverse_list(struct nodo *q);

que retorna una copia de la lista pero al revés: si le pasamos (1, 2, 3) debe retornar (3, 2, 1)

Se trata de resolver una antigua tarea1: Tarea1

Queda como lista.h:

struct nodo {
    struct nodo *next;
    void *val;
};
 
typedef struct {
	struct nodo *t, *h;
} LISTA;
 
LISTA *init_l();
void add_l(LISTA *, void *);
void *extract_l(LISTA *);
int size_l(LISTA *);
void *tail_l(LISTA *);
void *head_l(LISTA *);

y como lista.c:

/* Lista simplemente enlazada para almacenar cualquier cosa
 * se agrega por un lado y se extrae por el otro 
 */
 
#include "lista.h"
#include <stdio.h>
#include <stdlib.h>
 
LISTA *init_l() {
    LISTA *l;
 
    l = (LISTA *)malloc(sizeof(LISTA));
    if(l == NULL) return l;
    l->t = l->h = NULL;
    return l;
}
 
void add_l(LISTA *l, void *val) {
   struct nodo *p = (struct nodo *)malloc(sizeof(struct nodo));
   p->next = NULL; 
   if(l->t != NULL)
	l->t->next = p;
   else
	l->h = p;
   l->t = p;
   p->val = val;
   return;
}
 
void *extract_l(LISTA *l) {
   struct nodo *p;
   void *r;
 
   if(l->h == NULL) return NULL;
 
   p = l->h;
   l->h = p->next;
   r = p->val;
   free(p);
   if(l->h == NULL) l->t = NULL;
   return r;
}
 
int size_l(LISTA *l) {
   struct nodo *p;
   int i;
 
   for(i=0, p=l->h; p!=NULL; i++, p=p->next)
	;
 
   return i;
}
 
void *head_l(LISTA *l) {
    if(l->h == NULL) return NULL;
 
    return l->h->val;
}
 
void *tail_l(LISTA *l) {
    if(l->t == NULL) return NULL;
 
    return l->t->val;
}

Código completo en un tgz: Diccionario

Se trata de implementar la interfaz de un diccionario, dict.h sería:

DICT *init_dict();
void add_dict(DICT *d, char *llave, void *val);
void *search_dict(DICT *d, char *llave);
void apply_dict(DICT *d, void (*f)(char *llave, void *val));
void stats_dict(DICT *d);

Un ejemplo de uso, donde almaceno un puntero a un entero como valor, y ese valor es el contador de frecuencia con que aparece cada palabra en la entrada estándar (y uso la palabra como llave):

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "dict-lista.h"
 
#define MAX_LINE 255  /* esta es la forma de definir una constante en C */
 
void print2(char *s, void *cnt) {
    printf("%s: %d\n", s, *(int *)cnt);
}
 
main() {
    char s[MAX_LINE];
    DICT *dict;
    int *cnt;
    char *str;
 
    dict = init_dict();
 
    while( fgets(s, MAX_LINE, stdin) != NULL) {
	if(s[strlen(s)-1] == '\n')
	   s[strlen(s)-1] = '\0';
 
	str = strdup(s);
	if(str == NULL) {
	    fprintf(stderr, "No mem!\n");
	    exit(1);
 	}
	cnt = search_dict(dict, str);
	if(cnt == NULL) {
	    cnt = (int *)malloc(sizeof(int));
	    if(cnt == NULL) {
		fprintf(stderr, "out of mem\n");
		exit(1);
	    }
	    *cnt = 1;
	    add_dict(dict, str, cnt);
	}
        else {
            free(str); /* Ya estaba, no lo necesito ahora */
            (*cnt)++;
        }
    }
 
    apply_dict(dict, print2);
    stats_dict(dict);
}

la declaración del tipo es:

typedef struct dict_lista {
    char *llave;
    void *val;
    struct dict_lista *next;
} DICT;

Usaremos una lista ordenada alfabéticamente por llave y el valor es un puntero a cualquier cosa.

dict-lista.c es:

#include <stdio.h>
#include <stdlib.h>
#include "dict-lista.h"
 
/* 
 * Tipo diccionario, implementado con listas enlazadas
 */
 
/*
 * El primer elemento es una cabecera de lista que NO SE USA 
 */
 
DICT *init_dict() {
    DICT *p;
 
    p = (DICT *)malloc(sizeof(DICT));
    if(p == NULL) {
	fprintf(stderr, "No mem!\n");
	exit(1);
    }
    p->val = NULL;
    p->next = NULL;
    p->llave = NULL;
    return p;
}
 
void add_dict(DICT *d, char *llave, void *val) {
    DICT *p, *q;
 
    for(p = d; p->next != NULL && strcmp(p->next->llave, llave) < 0 ; p=p->next)
			;
 
    if(p->next != NULL && strcmp(p->next->llave, llave) == 0)
	p->next->val = val;
    else {
        q = (DICT *)malloc(sizeof(DICT));
	q->val = val; q->llave = llave;
	q->next = p->next;
	p->next = q;
    }
}
 
void *search_dict(DICT *d, char *llave) {
    DICT *p;
 
    for(p = d; p->next != NULL && strcmp(p->next->llave, llave) < 0 ; p=p->next)
                        ; 
    if(p->next == NULL || strcmp(p->next->llave, llave) != 0)
	return NULL;
 
    return p->next->val;
}
 
void apply_dict(DICT *d, void (*f)(char *llave, void *val)) {
    DICT *p;
 
    for(p = d->next; p != NULL; p=p->next)
	f(p->llave, p->val);
}
 
void stats_dict(DICT *d) {
    int cnt = 0;
    DICT *p;
 
    for(p = d->next; p != NULL; p=p->next)
	cnt++;
 
    printf("DICT lista nodos = %d\n", cnt);
}

la definición de tipo:

typedef struct dict_abb {
    char *llave;
    void *val;
    struct dict_abb *left, *right;
} TREE;
 
typedef struct {  /* Cabecera del árbol, es solo para que este puntero nunca cambie */
    TREE *head;
} DICT;

y dict-abb.c:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "dict-abb.h"
 
/* 
 * Tipo diccionario, implementado con Arboles Binarios de Busqueda
 */
 
/*
 * Todas las funciones _abb son internas de la implementacion
 * y son llamadas por la interfaz oficial de  DICT 
 */
 
DICT *init_dict() {
    DICT *p;
 
    p = (DICT *)malloc(sizeof(DICT));
    if(p == NULL) {
	fprintf(stderr, "No mem!\n");
	exit(1);
    }
    p->head = NULL;
    return p;
}
 
/*
 * Inserta un par en un ABB
 * y retorna el nuevo ABB (con el par ya insertado)
 */
TREE *add_abb(TREE *t, char *llave, void *val) {
    TREE *q; 
    int cmp;
 
    if(t == NULL) {  /* Insertar en un arbol vacio */
	q = (TREE *) malloc(sizeof(TREE));
    	if(q == NULL) {
	    fprintf(stderr, "No mem!\n");
	    exit(1);
    	}
	q->llave = llave; q->val = val;
	q->left = q->right = NULL;
        return q;
    }
 
    cmp = strcmp(llave, t->llave);
    if(cmp < 0)
	t->left = add_abb(t->left, llave, val);
    else if(cmp == 0)
	t->val = val;
    else
	t->right = add_abb(t->right, llave, val);
 
    return t;
}
 
void *search_abb(TREE *t, char *llave) {
    int cmp;
 
    if(t == NULL) return NULL;
 
    cmp = strcmp(llave, t->llave);
    if(cmp < 0)
	return search_abb(t->left, llave);
    else if(cmp == 0)
	return t->val;
    else
	return search_abb(t->right, llave);
}
 
void apply_abb(TREE *t, void (*f)(char *llave, void *val)) {
 
    if(t == NULL) return;
 
    apply_abb(t->left, f);
    f(t->llave, t->val);
    apply_abb(t->right, f);
}
 
int nodos_abb(TREE *t) {
    if(t == NULL) return 0;
 
    return(nodos_abb(t->left)+nodos_abb(t->right)+1);
}
 
int max(int a, int b) {
    return (a > b) ? a : b; 
}
 
int altura_abb(TREE *t) {
    if(t == NULL) return -1;
 
    return(max(altura_abb(t->left), altura_abb(t->right))+1);
}
 
void add_dict(DICT *d, char *llave, void *val) {
 
    d->head = add_abb(d->head, llave, val);
}
 
void *search_dict(DICT *d, char *llave) {
 
    return search_abb(d->head, llave);
}
 
void apply_dict(DICT *d, void (*f)(char *llave, void *val)) {
 
    apply_abb(d->head, f);
}
 
void stats_dict(DICT *d) {
 
    printf("Dict ABB: nodos = %d, altura = %d\n", nodos_abb(d->head),
                                                  altura_abb(d->head));
}

#include <stdio.h>
 
main()
{
   char c;
 
   c = -1;
   printf("-1=%x\n",  (unsigned char) c);
   c = -2;
   printf("-2=%x\n",  (unsigned char) c);
   c = -3;
   printf("-3=%x\n",  (unsigned char) c);
   c = -4;
   printf("-4=%x\n",  (unsigned char) c);
 
   c = 0x80;
   printf("0x80=%d\n", c);
   c--;
   printf("%x, %d\n", (unsigned char) c, c);
}

Manejo de signo usando bits:

#include <stdio.h>
 
char inv(char c){
    return ~c + 1;
}
 
int is_neg(char c) {
    return c&0x80;
}
 
main()
{
   char c;
 
   c = -1;
   if(is_neg(c)) printf("negativo=%d\n", c);
   else          printf("positivo=%d\n", c);
 
   printf("%d y %d y %d\n", -5, inv(-5), inv(inv(-5)));
 
   c = -128;
   if(is_neg(c)) printf("negativo=%d\n", c);
   else          printf("positivo=%d\n", c);
 
   printf("%d inv()=%d y inv(inv())=%d\n", -128, inv(-128), inv(inv(-128)));
 
   c--;
   if(is_neg(c)) printf("negativo=%d\n", c);
   else          printf("positivo=%d\n", c);
 
   c = 128;
   if(is_neg(c)) printf("negativo=%d\n", c);
   else          printf("positivo=%d\n", c);
 
   printf("%d inv()=%d y inv(inv())=%d\n", c, inv(128), inv(inv(128)));
 
}

Uso de bits con máscaras (el 7 podría ser una variable).

Código de bits-mask.c

#include <stdio.h>
 
/*
 * Manejo de bits como flags y mascaras
 */
 
main()
  {
    unsigned char bits = 0;     /* "arreglo" de 8 bits en cero */
 
    /* colocar el bit 0 en 1, sin modificar el resto */
    bits = bits | 1;
 
    /* colocar el bit 7 en 1, sin modificar el resto */
    bits = bits | (1 << 7);   /* La mascara la construyo */
 
    /* mostrar lo que quedo */
    printf("bits = %x\n", bits);
 
    /* preguntar por si el bit 7 esta en 1 */
    if(bits&(1<<7)) printf("OK, esta en 1\n");
 
    /* borrar el bit 7 */
    bits = bits & ~(1<<7);
 
    /* mostrar lo que quedo */
    printf("bits = %x\n", bits);
 
    /* preguntar por si el bit 7 esta en 1 */
    if(!(bits&(1<<7))) printf("OK, ya no esta en 1\n");
}

Código completo en un tgz: Conjuntos

Se trata de implementar el tipo SET y sus operaciones usando un bit para representar si el elemento está o no en el conjunto. Soporta desde 0 hasta un máximo que se especifica al crear el conjunto.

set.h:

typedef struct {
     unsigned maxval;
     char *set;
} SET;
 
SET *set_create( unsigned );
int set_ismem( SET *, unsigned);
void set_add( SET *, unsigned );
void set_del( SET *, unsigned );
void set_clear(SET *);
SET *set_inter(SET *, SET *);
SET *set_union(SET *, SET *);
SET *set_diff(SET *, SET *);
SET *set_xunion(SET *, SET *);

El programa principal que prueba la implementación, es testset.c :

#include "set.h"
#include <stdio.h>
#define MAXVAL 11
 
main()
{
    SET *p1, *p2, *p3, *p4, *p5, *p6;
    int i;
 
    p1 = set_create(MAXVAL);
 
    set_add(p1, 0);
    set_add(p1, 1);
    set_add(p1, 1);
    set_add(p1, 4);
    set_add(p1, 8);
    set_add(p1, 9);
    set_add(p1, 10);
    set_add(p1, 11);
 
    for(i=0;i<=MAXVAL;i++) {
    if( set_ismem(p1, i) )
	printf("%d ", i);
    }
    printf("\n");
 
    set_del(p1, 4);
    set_del(p1, 2);
 
    for(i=0;i<=MAXVAL;i++) {
    if( set_ismem(p1, i) )
	printf("%d ", i);
    }
    printf("\n");
 
    set_clear(p1);
    for(i=0;i<=MAXVAL;i++) {
    if( set_ismem(p1, i) )
	printf("%d ", i);
    }
    printf("\n");
 
    p2 = set_create(20);
    set_add(p2, 0);
    set_add(p2, 4);
    set_add(p2, 5);
    set_add(p2, 10);
    set_add(p2, 11);
    set_add(p2, 15);
    set_add(p2, 20);
 
    set_add(p1, 0);
    set_add(p1, 4);
    set_add(p1, 8);
    set_add(p1, 9);
    set_add(p1, 10);
    set_add(p1, 11);
 
    p3 = set_inter(p1, p2);
    for(i=0;i<=20;i++) {
    if( set_ismem(p1, i) )
	printf("%d ", i);
    }
    printf("\n");
    for(i=0;i<=20;i++) {
    if( set_ismem(p2, i) )
	printf("%d ", i);
    }
    printf("\n");
 
    printf("inter:\n");
    for(i=0;i<=20;i++) {
    if( set_ismem(p3, i) )
	printf("%d ", i);
    }
    printf("\n");
 
    printf("union:\n");
    p4=set_union(p1, p2);
    for(i=0;i<=20;i++) {
    if( set_ismem(p4, i) )
	printf("%d ", i);
    }
    printf("\n");
 
    printf("diff:\n");
    p5=set_diff(p1,p2);
    for(i=0;i<=20;i++) {
    if( set_ismem(p5, i) )
	printf("%d ", i);
    }
    printf("\n");
 
    printf("xunion:\n");
    p6=set_xunion(p1,p2);
    for(i=0;i<=20;i++) {
    if( set_ismem(p6, i) )
	printf("%d ", i);
    }
    printf("\n");
}

Y la implementación completa de set.c:

#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include "set.h"
 
/* 
 * Utilizamos un bit por elemento
 * maxval indica el máximo valor a representar, suponiendo que los
 * elementos estan en [0..maxval]
 * el elemento val se representa con set[val>>3] = 1 << (val&0x07)
 * o sea: encontrar el byte donde va y el bit dentro del byte 
 */
 
SET *set_create ( unsigned maxval )
{
    SET *s;
 
    s = (SET *)malloc( sizeof(SET) );
    if(s == NULL) {
	fprintf(stderr, "Out of mem\n");
	exit(1);
    }
    s->maxval = maxval;
    s->set = (char *)calloc(1+(maxval+1)>>3, 1 ); /* char = 2^3 bits */
    if(s->set == NULL) {
	fprintf(stderr, "Out of mem\n");
	exit(1);
    }
    return s;
}
 
void set_add( SET *s, unsigned val)
{
    if(val > s->maxval) return;
 
    *(s->set+(val>>3)) |= (1 << (val&0x07));
}
 
int set_ismem( SET *s, unsigned val)
{
    if(val > s->maxval) return 0; /* FALSE */
 
    return( *(s->set+(val>>3)) & (1 << (val&0x07)) );
}
 
void set_del( SET *s, unsigned val)
{
    if(val > s->maxval) return;
 
    *(s->set+(val>>3)) &= ~(1 << (val&0x07));
}
 
void set_clear( SET *s )
{
    bzero(s->set, (s->maxval>>3)+1); /* Pone en cero los bytes en memoria */
}
 
SET *set_inter(SET *s1, SET *s2)
{
    SET *r;
    unsigned maxval = (s1->maxval < s2->maxval) ? s1->maxval : s2->maxval;
    int c;
 
    r = set_create(maxval);
    for(c = 0; c <= maxval>>3; c ++)
	*(r->set+c) = *(s1->set+c) & *(s2->set+c);
 
    return r;
}
 
SET *set_union(SET *s1, SET *s2)
{
    SET *r;
    unsigned maxval = (s1->maxval < s2->maxval) ? s2->maxval : s1->maxval;
    SET *smax = (s1->maxval < s2->maxval) ? s2 : s1;
    unsigned minval = (s1->maxval < s2->maxval) ? s1->maxval : s2->maxval;
    int c;
 
    r = set_create(maxval);
    for(c = 0; c <= minval>>3; c++)
	*(r->set+c) = *(s1->set+c) | *(s2->set+c);
 
    for(; c <= maxval>>3; c++)
	*(r->set+c) = *(smax->set+c);
 
    return r;
}
 
SET *set_xunion(SET *s1, SET *s2)
{
    SET *r;
    unsigned maxval = (s1->maxval < s2->maxval) ? s2->maxval : s1->maxval;
    SET *smax = (s1->maxval < s2->maxval) ? s2 : s1;
    unsigned minval = (s1->maxval < s2->maxval) ? s1->maxval : s2->maxval;
    int c;
 
    r = set_create(maxval);
    for(c = 0; c <= minval>>3; c++)
	*(r->set+c) = *(s1->set+c) ^ *(s2->set+c);
 
    for(; c <= maxval>>3; c++)
	*(r->set+c) = *(smax->set+c);
 
    return r;
}
 
SET *set_diff(SET *s1, SET *s2)
{
    SET *r;
    unsigned minval = (s1->maxval < s2->maxval) ? s1->maxval : s2->maxval;
    int c;
 
    r = set_create(s1->maxval);
    for(c = 0; c <= minval>>3; c ++)
	*(r->set+c) = *(s1->set+c) & ~*(s2->set+c);
 
    for(; c <= s1->maxval>>3; c++)
	*(r->set+c) = *(s1->set+c);
 
    return r;
}

Programa que muestra el orden en que están los bytes de un entero (si quieren probar con un long long deben agrandar la constante para ir mirando los bytes):

#include <stdio.h>
 
main()
{
    unsigned char *cp;
    int d = 0x01020304;  /* Constante de 32 bits */
    int i;
 
    cp=(unsigned char *)&d;
    for(i=0; i<sizeof(int); i++)
        printf("%x ", *cp++);
 
    printf("\n");
}

Programa que determina si la arquitectura es Little Endian o Big Endian:

#include <stdio.h>
 
main()
{
    unsigned char *cp;
    int i = 1;
 
    cp=(char *)&i;
    if( *cp == '\0')
        printf("Big endian\n");
    else if( *cp == '\1')   /* En este caso '\1' == 1 dado que es un char */
        printf("Little endian\n");
    else
        printf("unknown endian\n");
}

#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
 
int brk = 0; /* variable externa que cuenta los ctrl-C */
 
/* handler de la interrupcion */
void ctrl_c() {
    brk++;
    fprintf(stderr, "Ay numero: %d!\n", brk);
    // exit(0);  /* si quieren morir a la primera: descomentar */
}
 
main()
{
    char c;
 
    signal(SIGINT, ctrl_c);
    while((c=getchar()) != EOF)
	putchar(c);
}

Programa que atrapa interrupción de reloj para implementar una función sleep:

#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
 
void clock() {
	printf("ring!\n");
}
 
void msleep(int n) {
    signal(SIGALRM, clock); /* una buena implementacion guarda el
                               handler original */
    alarm(n);
    pause();
}
 
main()
{
    char c;
 
    msleep(2);
    printf("ok2\n");
    msleep(1);
    printf("ok1\n");
}

Ahora usamos interrupciones de reloj para implementar timeouts. La función call_with_timeout llama una función y espera su retorno un máximo de segundos. Si todo estuvo bien, retorna lo mismo que la función. Si hubo un timeout, retorna -1.

Un programa de prueba es:

#include <stdio.h>
#include <signal.h>
 
/*
 * Prueba de la implementacion de call_with_timeout
 * tambien se asegura que el handler de reloj vuelva al antiguo
 */
 
int ls() {
    /* return system("ls -R /usr | less"); */ /* esto si quieren ver un comando largo ejecutando */
    sleep(5); /* esta funcion demora 5 segundos, asi que un timeout de 1 debiera bastar */
    return(0);
}
 
main() {
    printf("llamando a ls con timeout (3 veces)\n");
    printf("debiera ser 0, retorna: %d\n", call_with_timeout(ls, 10));
    printf("debiera ser -1, retorna: %d\n", call_with_timeout(ls, 1));
    printf("debiera ser -1, retorna: %d\n", call_with_timeout(ls, 1));
 
 
/* Esto es para probar que el hadlr de reloj volvió al default */
    printf("debiera morir con alarm clock\n");
    kill(getpid(), SIGALRM);
    sleep(1);
}

Una primera implementación, usando setjmp/longjmp:

#include <signal.h>
#include <setjmp.h>
 
/* 
 * Ejemplo de uso de signal y longjmp para implementar un timeout
 * Esta implementación usualmente solo funciona para la primera invocación 
 */
 
static jmp_buf ring;
 
void clock(int sig)
{
    longjmp(ring, 1);
}
 
int call_with_timeout(int (*f)(), int timeout)
{
    int res;
    void (*hdlr)();
 
    hdlr = signal(SIGALRM, clock);
 
    if(setjmp(ring) != 0) {
        signal(SIGALRM, hdlr); /* si llegamos aquí es que ocurrió el timeout */
	return(-1);
    }
 
    alarm(timeout); /* programamos el timer */
    res = f();
    alarm(0);  /* apagamos el timer */
 
    signal(SIGALRM, hdlr);
    return(res);
}

Esa implementación antes funcionaba bien, pero hoy en la mayoría de los linux modernos la función signal se implementa con una semántica diferente: el handler de interrupciones se ejecuta con la interrupción que atrapa deshabilitada (es para evitar que el handler sea interrumpido por la misma interrupción). Al retornar del handler, la interrupción se habilita de nuevo. El problema es que, al hacer longjmp, nuestro handler nunca retorna.

Linux permite manejar las máscaras de interrupciones bastante al detalle (ver man sigaction), pero usaremos solo un flag muy simple que evita el comportamiento de bloquear la interrupción atrapada. Para ello, no usaremos la función signal, sino su reemplazo más moderno (pero más complejo): sigaction.

#include <signal.h>
#include <setjmp.h>
#include <stdio.h>
 
/* 
 * Ejemplo de uso de signal y longjmp para implementar un timeout
 * Uso sigaction para borrar el bloqueo de la señal
 */
 
static jmp_buf ring;
 
void clock(int sig)
{
    longjmp(ring, 1);
}
 
int call_with_timeout(int (*f)(), int timeout)
{
    int res;
    struct sigaction sig, osig;
 
    sig.sa_handler = clock;
    sig.sa_flags = SA_NODEFER;
    sigaction(SIGALRM, &sig, &osig);
 
    if(setjmp(ring) != 0) {
        sigaction(SIGALRM, &osig, NULL);
	return(-1);
    }
 
    alarm(timeout);
    res = f();
    alarm(0);
 
    sigaction(SIGALRM, &osig, NULL);
    return(res);
}

La única forma de crear un proceso en Linux es fork().

Este programa simplemente crea una copia de si mismo. Para distinguir el original del clon, el truco es mirar lo que retorna la función fork: el original recibe el pid del clon (hijo), en cambio el clon recibe 0 (cero):

#include <stdio.h>
#include <stdlib.h>
 
/*
 * Ejemplo trivial de un fork
 */
 
main()
 {
    int pid;
 
    printf("voy al fork\n");
    pid = fork();
    if(pid < 0) {
	fprintf(stderr, "falla fork!\n");
	exit(1);
    }
 
    printf("ahora somos 2 clones\n");
 
    if(pid == 0) { /* soy el hijo */
	// sleep(1);
	printf("yo soy el clon!\n");
	exit(1);
    }
 
    printf("yo soy el original!\n");
}

Pueden ejecutar varias veces este programa y ver que la salida es no determinística ahora. Si des-comentan el sleep en el hijo, pueden verlo escribir sus mensajes después que su padre ya murió y el shell ya les dió el prompt (%).

Modificamos un poco el ejemplo anterior para que ahora ejecute el comando ls, que está en el archivo /bin/ls :

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
 
/*
 * Ejemplo trivial de un fork/exec
 */
 
main()
 {
    int pid;
 
    printf("voy al fork\n");
    pid = fork();
    if(pid < 0) {
	fprintf(stderr, "falla fork!\n");
	exit(1);
    }
 
    printf("ahora son 2 clones\n");
 
    if(pid == 0) { /* soy el hijo */
	printf("yo soy el clon!\n");
	execl("/bin/ls", "ls", "-l", 0);
	fprintf(stderr, "nunca debio ocurrir!\n");
	exit(1);
    }
 
    printf("yo soy el original!\n");
}

Obviamente sería mejor que el padre esperara al hijo para evitar que salgan lineas despues que el comando ya terminó. Para eso usamos wait:

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
 
/*
 * Ejemplo trivial de un fork/exec/wait
 */
 
main()
 {
    int pid;
    int status;
 
    printf("voy al ls\n");
    printf("---------------\n");
    fflush(stdout);  /* Para asegurarme que lo anterior ya salga por la salida
                      * prueben comentando el fflush y redirijan la salida a un archivo.
                      */
 
    pid = fork();
    if(pid < 0) {
	fprintf(stderr, "falla fork!\n");
	exit(1);
    }
 
    if(pid == 0) { /* soy el hijo */
	execl("/bin/ls", "ls", "-l", 0);
	fprintf(stderr, "nunca debio ocurrir!\n");
	exit(1);
    }
 
    waitpid(pid, &status, 0); /* espera la muerte del proceso pid */
    printf("---------------\n");
}

Entre el fork y el exec, se pueden manipular las característica que el hijo va a heredar: directorio actual, señales ignoradas, entrada y salida estándar, etc.

Este ejemplo hace que el hijo ignore el ctrl-C. Ustedes pueden ejecutarlo, matarlo con ctrl-C y verán que el padre muere, pero el hijo sigue ejecutando. Linux maneja las señales que van desde el teclado y le envía ctrl-C a todos los procesos que están asociados con esa ventana. Los procesos heredan de su padre la ventana a la que se asocian. Si quieren ser independientes, deben separarse del grupo (ver la función setpgroup).

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <signal.h>
 
/*
 * Ejemplo trivial de un fork/exec/wait
 * cambiamos al hijo para protegerlo de ctrl-C
 */
 
main()
 {
    int pid;
    int status;
 
    printf("voy al ls\n");
    printf("---------------\n");
    fflush(stdout);
 
    pid = fork();
    if(pid < 0) {
	fprintf(stderr, "falla fork!\n");
	exit(1);
    }
 
    if(pid == 0) { /* soy el hijo */
	printf("yo soy el clon!\n");
        signal(SIGINT, SIG_IGN);
	chdir("/");  /* vamos a la raiz del sistema */
	execl("/bin/ls", "ls", "-l", 0); 
	fprintf(stderr, "nunca debio ocurrir!\n");
	exit(1);
    }
 
    waitpid(pid, &status, 0);
    printf("---------------\n");
}

En Linux, un padre es completamente independiente de sus hijos, pero debe cumplir con una responsabilidad fundamental: enterrarlos cuando mueren. Para esto, basta con que invoque la función wait en cualquier momento, pero es indispensable que sea informado que su hijo murió para que Linux pueda deshacerse por completo de él. Un hijo muerto pero no enterrado (cuyo padre nunca ha sido informado de su muerte vía wait) es un Zombie: un proceso que ya no existe pero no puede reciclarse por completo.

Siempre deben evitar generar Zombies en el sistema y es su responsabilidad hacer wait de todos sus hijos muertos.

En este ejemplo, el programa crea 10 procesos de corta duración y se demora en esperarlos. Mientras el padre duerme, ustedes pueden ejecutar el comando “ps” que lista los procesos del sistema y verán los Zombies aparecer.

#include <stdio.h>
#include <stdlib.h>
 
int vars[10];
 
int create_proc(int i) {
    int pid;
 
    pid = fork();
    if(pid == 0) {  /* proceso hijo de corta duracion */
	vars[i] = 1;
	printf("hijo %d, pid=%d,var_i=%d\n", i, getpid(), vars[i]); /* getpid() retorna mi pid */
	exit(0);  /* que pasa si no pongo este exit? (prueben!) */
    }
 
    return pid;
}
 
main() {
    int pids[10];
    int i;
 
    for(i=0; i < 10; i++) 
	vars[i] = 0;
    for(i=0; i < 10; i++) 
	pids[i] = create_proc(i);
    sleep(20); /* pueden mirar los zombies durante un rato  */
    for(i=0; i < 10; i++)  /* ahora los entierro para que descansen en paz */
	waitpid(pids[i], NULL, 0);
 
    for(i=0; i < 10; i++)   /* Esto muestra que mis hijos heredan mis variables pero no me las pueden modificar a mi */ 
	printf("%d, ", vars[i]);
    printf("\n");
    sleep(20);
}

Nos queda aprender a modificar la E/S estándar de un proceso. Para ello, se definen los descriptores de archivos (file descriptors) que son enteros pequeños, asignados en orden. El descriptor 0 es la entrada estándar, el 1 es la salida estándar y el 2 es la salida de errores. Las funciones oficiales de Linux son read y write para leer y escribir datos. Un ejemplo es una nueva versión del comando copy que hicimos al comienzo del curso, pero en vez de usar las funciones de biblioteca, usamos las primitivas de Linux directamente:

#include <stdlib.h>
 
#define BUF_SIZ 1024
 
main() {
   char buf[BUF_SIZ];
 
   int cnt;
 
   while((cnt=read(0, buf, BUF_SIZ)) > 0)  /* read retorna los bytes leidos o 0 si es EOF */
	if(write(1, buf, cnt) != cnt)
	   exit(1); /* algo falló */
 
   exit(0);
}

La forma más habitual de obtener un descriptor nuevo es con la función open, que permite abrir un archivo para leerlo o escribirlo.

Un caso particular es el uso de pipes. Veamos una función que trata de hacer lo mismo que:

% ls | more

Debemos hacer dos fork/exec y conectarlos con un pipe. La lógica del código es:

1. Crear el pipe (arreglo de dos descriptores)
2. fork hijo 1 que hace:
   1. asignar su salida al pipe
   2. exec de ls
3. fork hijo 2 que hace:
   1. asignar su entrada al pipe
   2. exec de more
4. padre cierra ambos extremos del pipe
5. espera la muerte de ambos (y se preocupa de cómo murió ls)

#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
 
/*
 * Este programa ejecuta el comando ls|more en el directorio / (raiz) 
 * Y luego se despide y termina
 */
 
main() {
    int lspid, morepid, pid;
    int status = 0;
    int fds[2];
 
    if(pipe(fds) < 0) { /* Antes del fork: crear el pipe comun */
	fprintf(stderr, "fallo el pipe\n");
	exit(1);
    }
    printf("ls de / es:\n======================\n");
 
    lspid = fork();
    if(lspid < 0) {
		fprintf(stderr, "fallo el fork\n");
		exit(1);
	}
 
    if(lspid == 0) { /* ls */
        /* Cerrar el extremo read del pipe que no voy a usar */
	close(fds[0]);
	/* Asigno: 1 (stdout) = fds[1] (lado de escritura del pipe) */
	close(1); dup(fds[1]);
	/* Cerrar la copia que me queda sobre el pipe o no tendre' EOF */
        close(fds[1]);
 
    	chdir("/");
    	execl("/bin/ls", "ls", "-l", 0); /* Ponerle -R para probar sigpipe */
        fprintf(stderr, "Fallo el exec\n");
        exit(-1);
    }
 
    morepid = fork();
    if(morepid < 0) {
		fprintf(stderr, "fallo el fork\n");
		exit(1);
	}
 
    if(morepid == 0) { /* more */
        /* Cerrar el extremo write del pipe que no voy a usar */
	close(fds[1]);
	/* Asigno: 0 (stdin) = fds[0] (lado de lectura del pipe) */
	close(0); dup(fds[0]);
	/* Cerrar la copia que me queda sobre el pipe o no tendre' EOF */
	close(fds[0]);
 
    	execl("/bin/more", "more", 0);
        fprintf(stderr, "Fallo el exec\n");
        exit(-1);
    }
 
   /* Como padre comun, cierro el pipe, ambos extremos (yo no lo uso) */
   close(fds[0]); close(fds[1]);
 
   /* como buen padre, espero la muerte de todos mis hijos */
   /* while((pid = wait(&status)) != -1);  */
   /* O los puedo esperar explicitamente (si tuviera otros) */
   if(waitpid(morepid, &status, 0) != morepid) {
	fprintf(stderr, "fallo el wait2\n");
	perror("wait2");
	exit(-1);
   } 
 
   if(waitpid(lspid, &status, 0) != lspid) {
	perror("wait1");
	exit(-1);
   } 
 
   if( !WIFEXITED(status) ) {
        printf("ls anormal\n");
        if( WIFSTOPPED(status) ) {
                printf("Esta detenido\n");
                if(WSTOPSIG(status) == SIGSTOP) printf("Con SIGSTOP\n");
        }
        else if( WIFSIGNALED(status) ) {
	     printf("Murio con signal...\n");
             if( WTERMSIG(status) == SIGPIPE ) printf("Murio con sigpipe\n");
	}
   }
   else { /* Normal */
       printf("ls muere normalmente con exit code = %d\n", WEXITSTATUS(status));
   }
 
 
   printf("========================\n");
}

Si ejecutan este programa mostrando todos los archivos, ls muere normalmente y more también al recibir EOF por el pipe. Si terminan a more antes de tiempo (con 'q' desde el teclado) ls muere con sigpipe.

Se trata de hacer una versión simple de la función de biblioteca system (ver man system):

#include <stdio.h>
#include <sys/wait.h>
 
int system(char *cmd)
{
    int pid;
    int status;
 
    if( (pid=fork()) < 0 )
       return(-1);
 
    if( pid == 0 ) /* Es el hijo */
      {
	execl("/bin/sh", "sh", "-c", cmd, NULL);
	exit(127);
      }
 
    /* Es el padre: debemos esperar la muerte del hijo */
 
    waitpid( pid, &status, 0 );
    return(WEXITSTATUS(status));
}
 
/* ejemplo de uso */
main()
{
    int ret;
 
    ret = system("ls | more");
    printf("done: %d\n", ret);
}

Otro ejemplo: la función popen de la biblioteca, pero a nivel de descriptores de bajo nivel:

#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <fcntl.h>
#define READ 0
#define WRITE 1
 
int popen_id;
 
int fdpopen(char *cmd, int mode)
{
    int fds[2];
 
    if(pipe(fds) < 0) return -1;
 
    if((popen_id=fork()) == 0) /* soy el hijo */
      {
	/* soy cmd */
	if(mode == READ) { /* yo voy a escribir (ej: ls) */
	    close(fds[READ]);
    	    close(1); dup(fds[WRITE]);
            close(fds[WRITE]);
	} else { /* yo voy a leer (ej: wc) */
	    close(fds[WRITE]);
    	    close(0); dup(fds[READ]);
            close(fds[READ]);
	}
	execl("/bin/sh", "sh", "-c", cmd, NULL);
	exit(127);
      }
 
    if(popen_id < 0) return -1;
 
/* Este es el padre */
/* Cerrar los fds que no vamos a usar */
    close((mode==READ) ? fds[WRITE] : fds[READ]);
 
    return(fds[mode]);
} 
 
int fdpclose(int fd) {
    int status;
 
    close(fd);
    waitpid(popen_id, &status, 0);
    return(status);
}
 
#define BUF_SIZ 1024
 
main()
{
    int fd;
    char buf[BUF_SIZ];
    int cnt;
 
/* abrimos ls en lectura */
    fd = fdpopen("ls", READ);
    if(fd < 0) {
	fprintf(stderr, "No pude abrir ls!\n");
	perror("open");
  	exit(1);
    }
 
/* mostramos la salida de ls */
   while((cnt=read(fd, buf, BUF_SIZ)) > 0)
	if(write(1, buf, cnt) != cnt)
	   exit(1);
 
    fdpclose(fd);
    printf("========================\n ingrese texto...\n");
 
    fd=fdpopen("wc", WRITE);
 
/* copiamos nuestra entrada a wc */
   while((cnt=read(0, buf, BUF_SIZ)) > 0)
	if(write(fd, buf, cnt) != cnt)
	   exit(1);
 
    fdpclose(fd);
 
    printf("Fin del Mundo-------\n");
}

Versión recursiva de una función find que recorre un árbol de archivos (muestra uso de readdir y sus amigos):

#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <dirent.h>
#include <stdio.h>
 
/* 
 * Find:
 * Es mejor recorrer alargando el pathname que haciendo chdir
 * porque chdir("..") no siempre me lleva a donde yo creo por culpa de
 * los links
 */
 
void find(char *dir)
{
    DIR *fdir;
    struct dirent *ent;
    struct stat st;
    char *fn;
 
/* Pregunto por el directorio o archivo */
    if( stat( dir, &st ) < 0 ) /* o lstat si no quiero seguir los links a dir */
	return;
 
    printf("%s\n", dir);
 
/* Si no es un directorio, no hago nada mas */
    if( !S_ISDIR(st.st_mode) ) {
	return;
    }
 
/* Si es directorio lo recorro */
    if( (fdir = opendir(dir)) == NULL)
	return;
 
/* ent es el par nombre/i-node recorriendo el directorio */
    for(ent = readdir(fdir); ent != NULL; ent = readdir(fdir))
      {
	/* Saltamos . y .. que siempre estan */
	if( strcmp(ent->d_name, ".") == 0 || strcmp(ent->d_name, "..") == 0)
		continue;
 
	/* llamo a find con todos los elementos del directorio */
	/* fn = dir + "/" + ent->d_name; */
 	fn = (char *) malloc(strlen(dir)+strlen(ent->d_name)+2);
	strcpy(fn, dir);
	strcat(fn, "/");
	strcat(fn, ent->d_name);
 
	find( fn );
	free(fn);
      }
    closedir(fdir);
}
 
main()
{
/* esto recorre el arbol a partir del dir actual */
    find( "." );
}

Veamos un primer ejemplo de región crítica. Si salvan este archivo en critreg.c, deben hacer:

 
% gcc critreg.c -o critreg -lpthread

Este código muestra dos threads compitiendo por escribir en el mismo arreglo:

#include <stdio.h>
#include <pthread.h>
 
/*
 * Este codigo busca mostrar el problema de las regiones criticas:
 * el resultado es totalmente aleatorio al haber dos threads
 * modificando el mismo arreglo.
 */
 
#define MAXARR 10
 
int a[MAXARR];
 
void prod(int *x) {
    int i;
 
    for(i=0; i < MAXARR; i++) {
	a[i] = *x;
	sleep(1);
    }
} 
 
main() {
    pthread_t pid;
    int i;
    int j = 2;
 
    /* creo el thread */
    pthread_create(&pid, NULL, (void *)prod, &j);
 
    /* Yo soy el otro */
 
    for(i=0; i < MAXARR; i++) {
	a[i] = 1;
  	sleep(1);
    }
 
    /* espero que muera el productor */
    pthread_join(pid, NULL);
    for(i=0; i < MAXARR; i++)
	printf("%d ", a[i]);
    printf("\n");
}

Para arreglar esto, usamos lock/unlock que en pthreads se llaman mutexes. Básicamente proveen exclusión mutua en regiones críticas. En pthreads, las funciones de sincronización usualmente reciben punteros a las estructuras, lo que complica un poco la notación, usando típicamente el operador & para obtener el puntero al campo.

#include <stdio.h>
#include <pthread.h>
 
/*
 * Este codigo busca mostrar el problema de las regiones criticas:
 * Su resultado es aleatorio igual, pero ahora o son solo 1's o solo 0's
 * nunca se mezclan
 */
 
#define MAXARR 10
 
int a[MAXARR];
pthread_mutex_t mutex; /* Provee exclusión mutua */
 
void prod(int *x) {
    int i;
 
    pthread_mutex_lock(&mutex);
    for(i=0; i < MAXARR; i++) {
	a[i] = *x;
	sleep(1);
    }
    pthread_mutex_unlock(&mutex);
} 
 
main() {
    pthread_t pid;
    int i;
    int j = 2;
 
    /* Creo el mutex */
    pthread_mutex_init(&mutex, NULL);
 
    /* creo el thread */
    pthread_create(&pid, NULL, (void *)prod, &j);
 
    /* Yo soy el otro */
 
    pthread_mutex_lock(&mutex);
    for(i=0; i < MAXARR; i++) {
	a[i] = 1;
  	sleep(1);
    }
    pthread_mutex_unlock(&mutex);
 
    /* espero que muera el productor */
    pthread_join(pid, NULL);
    for(i=0; i < MAXARR; i++)
	printf("%d ", a[i]);
    printf("\n");
}

Un problema clásico en sincronización es el de un productor que genera datos y un consumidor que los lee. Es muy parecido a dos comandos conectados con un pipe. En algunos casos, se generaliza a múltiples productores y múltiples consumidores, pero comenzamos con el caso trivial: un productor, un consumidor y un pipe de tamaño un byte.

El código del productor/consumidor es:

#include <stdio.h>
#include <pthread.h>
#include "tbox.h"
 
/* Productor */
void prod(BOX *box) {
     char c;
 
     while((c=getchar()) != EOF)
	putbox(box, c);
 
     putbox(box, EOF);
}
 
/* Consumidor */
main() {
    BOX *box;
    char c;
    pthread_t pid;
 
    /* creo la caja que usaremos */
    box = createbox();
 
    /* creo el productor */
    pthread_create(&pid, NULL, (void *)prod, box);
 
    /* Yo soy el consumidor */
 
    while((c=getbox(box)) != EOF)
	putchar(c);
 
    /* espero que muera el productor */
    pthread_join(pid, NULL);
}

Como ven, usamos una estructura de comunicación/sincronización que llamamos box. Por ahora, usaremos una caja de tamaño un byte y que provee sincronización: escribir en una caja llena se bloquea hasta que se libere y leer de una caja vacía se bloquea esperando que se llene.

Una primera implementación simplista de una caja es:

tboxmalo.h:

typedef struct {
	char c;
	} BOX;
 
BOX *createbox();
void putbox(BOX *b, char c);
char getbox(BOX *b);

tboxmalo.c:

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include "tboxmalo.h"
 
BOX *createbox()
{
    BOX *b;
 
    b = (BOX *)malloc(sizeof(BOX));
 
    return(b);
}
 
void putbox(BOX *b, char c)
{
    b->c = c;
}
 
char getbox(BOX *b)
{
    char c;
 
    c = b->c;
    return(c);
}

Esta solución está mala, y, si la prueban, verán que pierden una enorme cantidad de caracteres a la vez que duplican varios otros. Es porque un thread escribe y escribe en la caja, sin esperar que el otro lea (pérdida); y al mismo tiempo un thread lee y lee sin esperar a que el otro escriba (duplicación).

Debemos sincronizar la lectura/escritura de la caja, de modo de garantizar que se haga uno por uno. Una alternativa es esperar a que el otro lea/escriba en un ciclo: tboxbusy.h:

typedef struct {
	char c;
	int estado;
	} BOX;
 
BOX *createbox();
void putbox(BOX *b, char c);
char getbox(BOX *b);

tboxbusy.c:

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include "tboxbusy.h"
 
/*
 * Solucion con busy wait: Pésima solución si prod o cons se demoran en 
 * escribir/leer la caja. Solo funciona con 1 prod y 1 cons
 */
 
#define VACIA 1
#define LLENA 2
 
BOX *createbox()
{
    BOX *b;
 
    b = (BOX *)malloc(sizeof(BOX));
    b->estado = VACIA;
 
    return(b);
}
 
void putbox(BOX *b, char c)
{
    while(b->estado == LLENA) /* Busywait: solución prohibida! */
		;
    b->c = c;
    b->estado = LLENA;
}
 
char getbox(BOX *b)
{
    char c;
 
    while(b->estado == VACIA) /* Busywait: solución prohibida! */
		;
    c = b->c;
    b->estado = VACIA;
    return(c);
}

Este estilo de solución se conoce como busy waiting y es una muy mala práctica de programación porque consume CPU inútilmente todo el tiempo de espera por la condición. En este curso esta solución está prohibida y no será considerada válida. Sin embargo, es bueno usarla como punto de comparación para el resto.

Para el caso particular de una caja de tamaño 1 y 1 productor y 1 consumidor, se puede usar mutex como buena solución, pero necesito 2 mutexes, ya que hay dos condiciones de bloqueo:

tbox-mutex.h:

typedef struct {
	char c;
	pthread_mutex_t vacio, lleno;
	} BOX;
 
BOX *createbox();
void putbox(BOX *b, char c);
char getbox(BOX *b);

tbox-mutex.c:

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include "tbox-mutex.h"
 
BOX *createbox()
{
    BOX *b;
 
    b = (BOX *)malloc(sizeof(BOX));
    pthread_mutex_init(&b->vacio, NULL);
    pthread_mutex_init(&b->lleno, NULL);
    pthread_mutex_lock(&b->lleno); /* Partimos con lleno tomado */
 
    return(b);
}
 
void putbox(BOX *b, char c)
{
    pthread_mutex_lock(&b->vacio);
    b->c = c;
    pthread_mutex_unlock(&b->lleno);
}
 
char getbox(BOX *b)
{
    char c;
 
    pthread_mutex_lock(&b->lleno);
    c = b->c;
    pthread_mutex_unlock(&b->vacio);
    return(c);
}

Esta solución es correcta, pero mucho más ineficiente que el busy wait anterior para los casos en que siempre hay datos fluyendo entre el productor y el consumidor. Cuando uno de los dos se queda bloqueado (esperando una E/S por ejemplo) esta solución es mucho más eficiente, claro.

Si hay varios productores y consumidores compartiendo la misma caja, ¿la solución sigue siendo correcta?

Haremos un ejemplo de múltiples productores/consumidores como prueba:

#include <stdio.h>
#include <pthread.h>
#include "tbox-mutex.h"
 
#define NCONS 20
#define NPRODS 20
 
/* Productor */
void prod(BOX *box) {
     FILE *fin;
     char c;
 
     fin = fopen("in.txt", "r");
     if(fin == NULL) {
	fprintf(stderr, "No pude abrir in.txt\n");
	exit(1);
     }
 
     while((c=fgetc(fin)) != EOF)
	putbox(box, c);
}
 
/* Consumidor */
int cons(BOX *box) {
    char c;
    int cnt = 0;
 
    while((c=getbox(box)) != EOF)
	cnt++;
 
    return cnt;
}
 
 
main() {
    BOX *box;
    char c;
    pthread_t prods_id[NPRODS];
    pthread_t cons_id[NCONS];
    int i, cnt;
    int total;
 
    /* creo la caja que usaremos */
    box = createbox();
 
    /* creo los productores */
    for(i=0; i < NPRODS; i++) {
    printf("creando prods\n");
        if(pthread_create(&prods_id[i], NULL, (void *)prod, box) != 0) {
	    fprintf(stderr, "No pude crear mas threads\n");
	    exit(1);
	}
     }
 
    /* creo los consumidores */
 
    for(i=0; i < NCONS; i++) {
    printf("creando cons\n");
        if(pthread_create(&cons_id[i], NULL, (void *)cons, box) != 0) {
	    fprintf(stderr, "No pude crear mas threads\n");
	    exit(1);
	}
    }
 
    /* espero que mueran los productores */
    printf("esperando prods\n");
    for(i=0; i < NPRODS; i++) {
        pthread_join(prods_id[i], NULL);
	printf("muere %d\n", i);
    }
 
    printf("aviso que se acaba\n");
    /* Aviso que se acabo */
    for(i=0; i < NCONS; i++)
	putbox(box, EOF); 
 
    /* espero que mueran los consumidores */
    printf("esperando cons\n");
    total = 0;
    for(i=0; i < NCONS; i++) {
        pthread_join(cons_id[i], (void *)&cnt);
	total += cnt;
    }
 
    printf("%d\n", total);
}

Este código necesita un archivo in.txt de donde leer, y, si size es el número de bytes del archivo, debe mostrar como resultado final NCONS*size si todo está bien.

Si lo ejecutamos con tbox-mutex, vemos que está correcto, pero es sumamente lento. La lentitud se da por el costo de los locks que nos dejan bloqueados. Linux optimiza mucho los mutexes para el caso en que el llamador no se bloquea (es la gran mayoría de los casos en el mundo real), por lo que bloquearse es muy caro. En programación paralela se usa mucho un truco habitual en estos casos: tener cajas de comunicación de tamaño bastante mayor que 1, lo que llamamos un buffer. Un buffer sirve para compensar las diferencias de velocidad temporales entre los productores y los consumidores, siempre y cuando no sea sistemática. Si siempre el productor es más rápido que el consumidor, todos los buffers estarán ocupados. Si siempre es lo contrario, todos los buffers estarán vacíos.

Un buffer bien sintonizado entre productores/consumidores de velocidad promedio equivalente nos permite operar sin nunca bloquearnos, porque siempre habrá buffers vacíos y llenos. ¿Cuántos buffers se necesitan? Básicamente necesitamos tener el máximo que llegue a ser la diferencia de velocidad entre productores/consumidores en el tiempo. Pero generalmente nos contentamos con un tamaño que sirva la mayoría de los casos, por ejemplo que no nos bloquee en el 90% de los casos.

Volvamos primero al caso simple: un productor, un consumidor y N buffers. Implementar esto con mutexes es difícil, porque ya no basta con esperar por una caja, sino como si tuviésemos N cajas. Para este problema se inventaron los semáforos. Un semáforo se inicializa con un contador N y permite N locks antes de quedarse bloqueado. Es muy parecido a un mutex, pero permitiendo a varios threads entrar al mismo tiempo. De hecho, un semáforo inicializado en 1 es básicamente lo mismo que un mutex. La función lock en la literatura se llama P() y unlock V(). En pthreads se llaman sem_wait() y sem_post().

Para nuestra implementación de box, usaremos los semáforos de pthreads, y tendremos dos: uno inicializado en N (que cuenta los buffers vacíos) y otro inicializado en 0 (que cuenta los buffers llenos). La suma entre los dos semáforos siempre será N:

tbox-sem.h:

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
 
#define NBUFS 1000
 
typedef struct {
	char buf[NBUFS];
	sem_t vacios, llenos;
  	int in, out;
	} BOX;
 
BOX *createbox();
void putbox(BOX *b, char c);
char getbox(BOX *b);

tbox-sem.c:

#include <stdio.h>
#include "tbox-sem.h"
 
BOX *createbox()
{
    BOX *b;
 
    b = (BOX *)malloc(sizeof(BOX));
    sem_init(&b->vacios, 0, NBUFS);
    sem_init(&b->llenos, 0, 0);
    b->in = b->out = 0;
    return(b);
}
 
/* Implementacion para un Productor y un Consumidor */
void putbox(BOX *b, char c)
{
    sem_wait(&b->vacios);
    b->buf[b->in] = c;
    b->in = (b->in+1)%NBUFS;
    sem_post(&b->llenos);
}
 
char getbox(BOX *b)
{
    char c;
 
    sem_wait(&b->llenos);
    c = b->buf[b->out];
    b->out = (b->out+1)%NBUFS;
    sem_post(&b->vacios);
    return(c);
}

Esta solución ¿es correcta? Primero pareciera que falta preguntar en alguna parte por la condición hay buffers vacíos y por la condición hay buffers llenos. Esto no es necesario porque el semáforo mismo me provee esa condición: si pasé por sem_wait(&b→llenos) significa que hay buffers llenos. La pregunta viene “incluida” en la primitiva misma.

¿Y se permite ejecución paralela entre putbox y getbox sin generar errores? La pregunta es más difícil que en el caso de la caja de tamaño 1, porque ahora existe mucho paralelismo entre putbox y getbox: cuando hay buffers vacíos y llenos a la vez, ambos pueden entrar en forma simultánea. Sin embargo, al mirar el código, podemos ver que putbox modifica b→out y en cambio getbox modifica b→in. No hay conflictos ahí. Pero el buffer donde escriben/leen es el mismo, así que hay que asegurarse que nunca estén usando el mismo elemento, lo que implica asegurarse que nunca se dé: b→out == b→in. Esa condición de igualdad se da en dos casos: cuando todos los buffers están vacíos (condición inicial) y cuando están todos llenos. Esto es muy bueno, porque justamente en esas dos condiciones es cuando no existe paralelismo: o sólo entra el productor o sólo entra el consumidor. Por lo tanto, esta implementación es correcta para un productor y un consumidor.

Si probamos esta solución veremos que es bastante competitiva con busywait en eficiencia, variando según la cantidad de buffers que pongamos en el arreglo y el tamaño de la entrada.

Veamos ahora si es generalizable a múltiples productores/consumidores: veamos si el código resiste paralelismo entre múltiples threads ejecutando en paralelo putbox(). Ahora el problema es que los threads van a entrar varios al mismo tiempo (basta con que hayan suficientes buffers vacíos) y escribirán en el mismo lugar y modificarán la misma variable (b→in) generándose una región crítica. Debemos proteger ese código. Respectivamente, lo mismo ocurre en getbox().

Agreguemos un mutex global que proteja el buffer y sus variables para que no se produzca este error:

tbox-semN.c:

#include <stdio.h>
#include "tbox-sem.h"
 
BOX *createbox()
{
    BOX *b;
 
    b = (BOX *)malloc(sizeof(BOX));
    pthread_mutex_init(&b->mutex, NULL);
    sem_init(&b->vacios, 0, NBUFS);
    sem_init(&b->llenos, 0, 0);
    b->in = b->out = 0;
    return(b);
}
 
/* Implementacion para un Productor y un Consumidor */
void putbox(BOX *b, char c)
{
    pthread_mutex_lock(&b->mutex);
    sem_wait(&b->vacios);
    b->buf[b->in] = c;
    b->in = (b->in+1)%NBUFS;
    sem_post(&b->llenos);
    pthread_mutex_unlock(&b->mutex);
}
 
char getbox(BOX *b)
{
    char c;
 
    pthread_mutex_lock(&b->mutex);
    sem_wait(&b->llenos);
    c = b->buf[b->out];
    b->out = (b->out+1)%NBUFS;
    sem_post(&b->vacios);
    pthread_mutex_unlock(&b->mutex);
    return(c);
}

Esta solución ¿es correcta? Lo pareciera, a primera vista, pero está mala. Al agregar tanta sincronización, introdujimos un problema nuevo, que es culpa de las mismas herramientas de control: en cuanto ocurre una situación de bloqueo (ya sea todos los buffers vacíos o todos llenos) el sistema se detiene para siempre y tanto los productores como los consumidores quedan detenidos. Miremos el caso de todos los buffers vacíos como ejemplo: llega un consumidor que invoca getbox, toma el mutex de los buffers y se queda bloqueado en el semáforo llenos. El problema es que el que debe desbloquearlo debe invocar putbox, y lo primero que hace es pedir el mutex de los buffers y se queda bloqueado esperándolo. Esto se llama un deadlock, porque están todos bloqueados esperando que el otro haga algo en un ciclo que nunca se resolverá. Después de las regiones críticas no detectadas, el otro problema clásico de los programas paralelos que uno programa son los deadlocks.

En este caso en particular, el problema es que nos vamos a dormir en el semáforo con el mutex tomado, y no dejamos que nadie más entre al sistema. La primera solución es mover el mutex después del semáforo. La región crítica que queremos proteger es el código que escribe/lee en el buffer, no el código del semáforo:

#include <stdio.h>
#include "tbox-semN.h"
 
BOX *createbox()
{
    BOX *b;
 
    b = (BOX *)malloc(sizeof(BOX));
    sem_init(&b->vacios, 0, NBUFS);
    sem_init(&b->llenos, 0, 0);
    pthread_mutex_init(&b->mutex, NULL);
    b->in = b->out = 0;
    return(b);
}
 
/* Implementacion para N Productores y Consumidores */
void putbox(BOX *b, char c)
{
    sem_wait(&b->vacios);
    pthread_mutex_lock(&b->mutex);
    b->buf[b->in] = c;
    b->in = (b->in+1)%NBUFS;
    pthread_mutex_unlock(&b->mutex);
    sem_post(&b->llenos);
}
 
char getbox(BOX *b)
{
    char c;
 
    sem_wait(&b->llenos);
    pthread_mutex_lock(&b->mutex);
    c = b->buf[b->out];
    b->out = (b->out+1)%NBUFS;
    pthread_mutex_unlock(&b->mutex);
    sem_post(&b->vacios);
    return(c);
}

Pero podemos mejorar más la eficiencia: habíamos visto que no era necesario hacer mutuamente excluyentes las secciones entre putbox y getbox, así que es mejor usar dos mutexes separados. La solución final es:

tbox-semN.h:

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
 
#define NBUFS 100000
 
typedef struct {
	char buf[NBUFS];
	sem_t vacios, llenos;
	pthread_mutex_t put, get;
  	int in, out;
	} BOX;
 
BOX *createbox();
void putbox(BOX *b, char c);
char getbox(BOX *b);

tbox-semN.c:

#include <stdio.h>
#include "tbox-semN.h"
 
BOX *createbox()
{
    BOX *b;
 
    b = (BOX *)malloc(sizeof(BOX));
    sem_init(&b->vacios, 0, NBUFS);
    sem_init(&b->llenos, 0, 0);
    pthread_mutex_init(&b->put, NULL);
    pthread_mutex_init(&b->get, NULL);
    b->in = b->out = 0;
    return(b);
}
 
/* Implementacion para N Productores y Consumidores */
void putbox(BOX *b, char c)
{
    sem_wait(&b->vacios);
    pthread_mutex_lock(&b->put);
    b->buf[b->in] = c;
    b->in = (b->in+1)%NBUFS;
    pthread_mutex_unlock(&b->put);
    sem_post(&b->llenos);
}
 
char getbox(BOX *b)
{
    char c;
 
    sem_wait(&b->llenos);
    pthread_mutex_lock(&b->get);
    c = b->buf[b->out];
    b->out = (b->out+1)%NBUFS;
    pthread_mutex_unlock(&b->get);
    sem_post(&b->vacios);
    return(c);
}

En general, la regla es dejar las regiones críticas protegidas por mutexes lo más pequeñas posibles y usar todos los mutexes que se pueda en vez de compartirlos.

Cuando las condiciones para la espera son más complejas que simplemente contar buffers, usamos condiciones. En pthreads los monitores como tales no existen, pero se implementan con un mutex común y condiciones que permiten quedarse bloqueados. Las condiciones solo pueden usarse dentro de un mutex común que ya está tomado. Aunque es un mal ejemplo, podemos implementar el administrador de buffers con múltiples productores/consumidores para mostrar como funcional. Como ahora no tenemos los semáforos protegiéndonos, debemos preguntar explícitamente por las condiciones de todos los buffers vacíos o todos los buffers llenos. Para eso, agregamos dos variables (llenos y vacios) que siempre suman N:

tbox-cond.h:

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
 
#define NBUFS 1000
 
typedef struct {
	char buf[NBUFS];
	pthread_cond_t vacios, llenos; /* condiciones de espera */
	pthread_mutex_t mutex; /* mutex compartido */
  	int in, out;
        int nvacios, nllenos;
	} BOX;
 
BOX *createbox();
void putbox(BOX *b, char c);
char getbox(BOX *b);

tbox-cond.c:

#include <stdio.h>
#include "tbox-cond.h"
 
BOX *createbox()
{
    BOX *b;
 
    b = (BOX *)malloc(sizeof(BOX));
    pthread_mutex_init(&b->mutex, NULL);
    pthread_cond_init(&b->llenos, NULL);
    pthread_cond_init(&b->vacios, NULL);
    b->in = b->out = 0;
    b->nllenos = 0; b->nvacios = NBUFS; 
    return(b);
}
 
/* Implementacion para un Productor y un Consumidor */
void putbox(BOX *b, char c)
{
    pthread_mutex_lock(&b->mutex);
    while(b->nvacios == 0)
	pthread_cond_wait(&b->vacios, &b->mutex);
    b->buf[b->in] = c;
    b->in = (b->in+1)%NBUFS;
    b->nllenos++; b->nvacios--;
    pthread_cond_signal(&b->llenos);
    pthread_mutex_unlock(&b->mutex);
}
 
char getbox(BOX *b)
{
    char c;
 
    pthread_mutex_lock(&b->mutex);
    while(b->nllenos == 0)
	pthread_cond_wait(&b->llenos, &b->mutex);
    c = b->buf[b->out];
    b->out = (b->out+1)%NBUFS;
    b->nllenos--; b->nvacios++;
    pthread_cond_signal(&b->vacios);
    pthread_mutex_unlock(&b->mutex);
    return(c);
}

Si se fijan, siempre partimos por tomar el mutex compartido. Luego vemos si se cumple la condición que necesitamos para poder ejecutar. Si no se cumple, nos bloqueamos en un wait de una condición. Esa llamada siempre es bloqueante. Al contrario de los semáforos, las condiciones no tienen un estado. Las operaciones no las modifican, simplemente sirven para darle un nombre al punto de sincronización. Al esperar la condición, debo especificar el mutex que la protege, de modo que la llamada me bloquea y libera el mutex. Si se fijan, no hacemos:

    if(b->nllenos == 0)
        pthread_cond_wait(&b->llenos, &b->mutex);

sino que usamos un while. Esto es obligatorio, porque siempre debo volver a verificar la condición antes de seguir ejecutando mi código. Para despertar de un wait, otro thread debe invocar un signal sobre esa misma condición. En este caso, lo hace la función putbox es la que me despierta al hacer signal de la condición llenos. Esa función despierta a un thread que esté esperando. Si no hay ninguno, no hace nada. Como usamos la estructura clásica de monitores (con un mutex compartido) no estamos siendo óptimos y no permitimos paralelismo entre productores y consumidores. Pthreads lo permite y podríamos tener dos mutexes (pruébenlo como tarea).

En algunos casos más avanzados, podemos querer despertar a todos los threads que están esperando en una condición (no es el caso del ejemplo). Para eso, existe pthread_cond_broadcast().

Como otro ejemplo, podemos implementar un semáforo usando condiciones. Tendrá las funciones P() (wait) y V() (post) como siempre:

jsem.h:

#include <pthread.h>
 
typedef struct {
    int val;
    pthread_cond_t paso; /* Condicion para esperar entrar al semáforo */
    pthread_mutex_t mutex;
} JSEM;
 
JSEM *jsem_init(int);
 
void P(JSEM *s);
void V(JSEM *s);

jsem.c:

#include "jsem.h"
 
JSEM *jsem_init(int val) {
    JSEM *s;
 
    s = (JSEM *)malloc(sizeof(JSEM));
    if(s == NULL) return NULL;
 
    s->val = val;
    pthread_cond_init(&s->paso, NULL);
    pthread_mutex_init(&s->mutex, NULL);
    return s;
}
 
void P(JSEM *s) {
    pthread_mutex_lock(&s->mutex);
    while(s->val == 0) /* Nunca un if! */
	pthread_cond_wait(&s->paso, &s->mutex);
 
    s->val--;
    pthread_mutex_unlock(&s->mutex);
}
 
void V(JSEM *s) {
    pthread_mutex_lock(&s->mutex);
    s->val++;
    pthread_cond_signal(&s->paso); /* siempre libero a uno solo */
    pthread_mutex_unlock(&s->mutex);
}

Pueden probar los productores/consumidores con esta implementación de semáforos. Todos los códigos de threads vistos hasta aquí se los dejo en tbox.tgz

Un ejemplo que muestra bien la utilidad de las condiciones es un administrador de buffers que almacena frames de video capturados de una cámara (productor) y que se comparten entre múltiples clientes que los despliegan (consumidores). Es un esquema de un productor y múltiples consumidores y un número fijo de buffers en memoria.

La cámara genera un nuevo frame y busca un buffer en memoria donde almacenarlo. Esto lo pide con una función:

void PutFrame(TIME tstamp, char *buf);

Los threads de los clientes buscan un frame entre los buffers y lo marcan para usarlo un rato. Después de terminar con él, lo liberan y piden otro. Esto lo hacen con dos funciones:

/* Busca un buffer */
int GetFrame(TIME tstamp);
/* Libera un frame */
void FreeFrame(int i)

Sin embargo, debemos respetar que la cámara no puede usar un buffer que esté siendo ocupado por un cliente. Por otro lado, el cliente, cuando pide un frame, sólo le sirve uno más nuevo que el último que recibió. Para estas condiciones usamos, para cada frame, un contador de referencias (ref_cnt) que cuenta el número de clientes que tiene “marcado” ese frame y un timestamp que marca la hora absoluta en que fue generado (suponemos que es un número monótonamente creciente).

La implementación con monitores y condiciones es:

/* Busca un buffer con ref_cnt == 0 */
void PutFrame(TIME tstamp, char *buf) {
    int i;
 
    pthread_mutex_lock( &(master_lock));
    for(;;) {
        for(i=0; i<NBUFS; i++)
	    if(Buffers[i].ref_cnt == 0)
	        break;
	if(i==NBUFS) pthread_cond_wait(&free_frame, &master_lock);
	else break;
    }
 
    Buffers[i].tstamp = tstamp;
    Buffers[i].buf = buf;
    pthread_cond_broadcast(&new_frame);
    pthread_mutex_unlock( &(master_lock));
}
 
/* Busca un buffer con timestamp > tstamp */
int GetFrame(TIME tstamp) {
    int i;
 
    pthread_mutex_lock( &(master_lock));
    for(;;) {
        for(i=0; i<NBUFS; i++)
	    if(Buffers[i].tstamp > tstamp) 
		break;
	if(i==NBUFS) pthread_cond_wait(&new_frame, &master_lock);
	else break; 
    }
    Buffers[i].ref_cnt++;
    pthread_mutex_unlock( &(master_lock));
    return i;
}
 
/* Libera un frame */
void FreeFrame(int i) {
    pthread_mutex_lock( &(master_lock));
    Buffers[i].ref_cnt--;
    if(Buffers[i].ref_cnt == 0) pthread_cond_signal(&free_frame);
    pthread_mutex_unlock( &(master_lock));
}

Estudien el código. Vean porqué hacemos cond_signal en un lugar y cond_broadcast en otro.

Un problema clásico de sincronización es el de los filósofos hambrientos. La idea es un grupo de N filósofos y N tenedores sentados alrededor de una mesa. El problema es que se necesitan 2 tenedores para poder comer. Cuando alguno de los tenedores está ocupado por nuestro vecino, debemos esperar que lo desocupe. Esta es la solución inocente que podríamos proponer (vean que piensan poco y comen harto… ¡no son buenos filósofos!):

#include <stdio.h>
#include <pthread.h>
 
#define N_FILO 10
 
pthread_mutex_t forks[N_FILO];
 
/* Si pensar es mucho mas rápido que comer, aumentamos las
 * probabilidades de deadlock
 */
 
void pensar(int f) {
    printf("%d: pensando...\n", f);
}
 
void comer(int f) {
    printf("%d: comiendo..\n", f);
    sleep(1);
}
 
void *filo(void *f2) {
    int i, f=(int)f2;
 
    for(i=0; i < 10; i++) {
	pensar(f);
 	pthread_mutex_lock(&forks[f]);
	printf("%d: locked %d\n", f ,f);
 	pthread_mutex_lock(&forks[(f+1)%N_FILO]);
	printf("%d: locked %d\n", f, (f+1)%N_FILO);
        comer(f);
 	pthread_mutex_unlock(&forks[(f+1)%N_FILO]);
	printf("unlocked %d\n", f);
 	pthread_mutex_unlock(&forks[f]);
	printf("unlocked %d\n", (f+1)%N_FILO);
    }
    printf("%d: finito!\n", f);
    return NULL;
}
 
main() {
    int i;
    pthread_t pid[N_FILO];
 
    for(i=0; i < N_FILO; i++)
	pthread_mutex_init(&forks[i], NULL);
    for(i=0; i < N_FILO; i++)
	pthread_create(&pid[i], NULL, filo, (void *)i);
    for(i=0; i < N_FILO; i++)
	pthread_join(pid[i], NULL);
}