Wiki CC3301

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
====== CC3301 - Programación de Software de Sistemas ======

Estos son los apuntes de José Piquer.  Además se encuentran disponibles en youtube
[[http://www.youtube.com/watch?v=maJkL9kpoek&feature=c4-overview-vl&list=PLC4BC3AFA8B75D08B|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 [[temario|Luis Mateu]] se explican los mismos conceptos de esta página pero con más detalle.

===== Clase 1: Lenguaje C, E/S Estándar =====

Ver contenido extendido en [[introduccion|Introducción]].

Ejemplo estudiado: [[http://www.dcc.uchile.cl/jpiquer/Docencia/cc31a/copy.c|copy.c]]

<code C>
#include <stdio.h>

/* 
 * Copia la entrada en su salida sin modificaciones
 */

int main() {

    int c;

    while((c=getchar()) != EOF)
        putchar(c);

    return 1;
}
</code>

Pueden probar compilando este programa:
<code>
% gcc copy.c -o copy
</code>

Y jugando a manejar su entrada y salida:

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



====== Clase 2: Lenguaje C y tipos básicos ======

Ver contenido extendido en [[tipos|tipos]] y [[variables|variables]].
===== Enteros =====
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

===== flotantes =====

float: 32 bits
double: 64 bits

===== Punteros =====

Ver contenido extendido en [[punteros|punteros]] y [[strings|strings]].
==== Strings ====

Ejemplos de punteros a strings: [[http://www.dcc.uchile.cl/jpiquer/Docencia/cc31a/string.c|string.c]]

<code 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;
}
</code>

====== Clase 3: Lenguaje C y estructuras de datos ======

===== Lista simplemente enlazada =====

Ejemplo estudiado: [[http://www.dcc.uchile.cl/jpiquer/Docencia/cc31a/lista1.c|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)


<code C>

#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);
}
</code>

Ejercicio propuesto: hacer la función:
<code C>
struct nodo *reverse_list(struct nodo *q);
</code>
que retorna una copia de la lista pero al revés: si le pasamos (1, 2, 3) debe retornar (3, 2, 1)

====== Clase 4: Lenguaje C y estructuras de datos ======

===== Lista simplemente enlazada (II) =====

Se trata de resolver una antigua tarea1: [[http://www.dcc.uchile.cl/jpiquer/Docencia/cc31a/Lista/tarea1.html|Tarea1]]

Queda como lista.h:
<code C>
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 *);
</code>

y como lista.c:
<code 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;
}
</code>

====== Clase 5: Lenguaje C y estructuras de datos ======

===== Diccionario DICT =====

Código completo en un tgz: [[http://www.dcc.uchile.cl/jpiquer/Docencia/cc31a/dict.tgz|Diccionario]]


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

<code C>
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);
</code>

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):
<code C>
#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);
}
</code>

==== Implementación con lista enlazada ====

la declaración del tipo es:
<code C>
typedef struct dict_lista {
    char *llave;
    void *val;
    struct dict_lista *next;
} DICT;
</code>
Usaremos una lista ordenada alfabéticamente por llave y el valor es un puntero a cualquier cosa.


dict-lista.c es:
<code C>
#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);
}
</code>

==== Implementación con árbol de búsqueda binaria (ABB) ====

la definición de tipo:

<code C>
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;
</code>

y dict-abb.c:
<code 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));
}
</code>

====== Clase 6: Lenguaje C y manejo de bits ======

===== Representación de enteros con signo =====

<code C>
#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);
}
</code>

Manejo de signo usando bits:

<code C>
#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)));

}
</code>

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

[[http://www.dcc.uchile.cl/jpiquer/Docencia/cc31a/bits-mask.c|Código de bits-mask.c]]


<code 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");
}
</code>

====== Clase 7: Lenguaje C y manejo de bits ======

===== Tipo Conjunto de enteros con bits =====

Código completo en un tgz: [[http://www.dcc.uchile.cl/jpiquer/Docencia/cc31a/set.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:

<code C>
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 *);
</code>

El programa principal que prueba la implementación, es testset.c :
<code 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");
}
</code>

Y la implementación completa de set.c:
<code 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;
}
</code>

====== Clase 8: Lenguaje C y manejo de bits ======

===== Endians y Representación de enteros =====

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):
<code C>
#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");
}
</code>


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

<code C>
#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");
}
</code>

====== Clase 9: Linux: Señales ======

===== Atrapar una señal (ctrl-C) =====
<code C>
#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);
}
</code>

===== Dormir un rato (sleep) =====

Programa que atrapa interrupción de reloj para implementar una función sleep:
<code C>
#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");
}
</code>

===== Timeouts (longjmp/setjmp) =====

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:
<code C>
#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);
}
</code> 

Una primera implementación, usando setjmp/longjmp:

<code C>
#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);
}
</code>

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.

<code C>
#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);
}
</code>

====== Clase 10: Linux: Procesos ======

===== Crear un proceso (fork) =====

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):

<code C>
#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");
}
</code>

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 (%).

===== Ejecutar un archivo ejecutable (exec) =====

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

<code C>
#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");
}
</code>
===== Esperar que un hijo muera (wait) =====

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:

<code C>
#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");
}
</code>
===== Manejar propiedades de un hijo =====

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).

<code C>
#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");
}
</code>
===== Deberes de un padre =====
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.
<code C>
#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);
}
</code>

====== Clase 11: Linux: E/S ======

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:
<code C>
#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);
}
</code>

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.

===== Pipes =====

Un caso particular es el uso de pipes. Veamos una función que trata de hacer lo mismo que:
<code>
% ls | more
</code>

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

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

<code C>
#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");
}

</code>

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.

====== Clase 12: Linux: Ejemplos con pipes ======

Se trata de hacer una versión simple de la función de biblioteca ''system'' (ver ''man system''):
<code C>
#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);
}
</code>

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

<code C>
#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");
}
</code>

====== Clase 13: Linux: Sistema de archivos ======

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

<code C>
#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( "." );
}
</code>

====== Clase 14: Threads: Regiones Críticas ======

Veamos un primer ejemplo de región crítica. Si salvan este archivo en critreg.c, deben hacer:
<code> 
% gcc critreg.c -o critreg -lpthread
</code>

Este código muestra dos threads compitiendo por escribir en el mismo arreglo:
<code C>
#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");
}
</code>

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.
<code C>
#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");
}
</code>

====== Clase 15: Threads: Productor/Consumidor ======

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:
<code C>
#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);
}
</code>
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:
<code C>
typedef struct {
	char c;
	} BOX;

BOX *createbox();
void putbox(BOX *b, char c);
char getbox(BOX *b);
</code>

tboxmalo.c:
<code 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);
}
</code>

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:
<code C>
typedef struct {
	char c;
	int estado;
	} BOX;

BOX *createbox();
void putbox(BOX *b, char c);
char getbox(BOX *b);
</code>

tboxbusy.c:

<code 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);
}
</code>

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:
<code C>
typedef struct {
	char c;
	pthread_mutex_t vacio, lleno;
	} BOX;

BOX *createbox();
void putbox(BOX *b, char c);
char getbox(BOX *b);
</code>

tbox-mutex.c:
<code 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);
}
</code>

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:
<code C>
#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);
}
</code>

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.

====== Clase 16: Threads: productor/consumidor y buffers ======

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:

<code C>
#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);
</code>

tbox-sem.c:
<code 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);
}
</code>

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:
<code 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);
}
</code>

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:

<code 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->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);
}
</code>

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:
<code C>
#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);
</code>

tbox-semN.c:
<code 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);
}
</code>

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.

====== Clase 17: Threads: Monitores y Condiciones ======

===== Tbox con monitores =====

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:
<code C>
#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);
</code>

tbox-cond.c:
<code 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);
}
</code>

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:
<code C>
    if(b->nllenos == 0)
        pthread_cond_wait(&b->llenos, &b->mutex);
</code>
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().

===== Semáforo con monitores =====

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

jsem.h:

<code C>
#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);
</code>

jsem.c:

<code 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);
}
</code>

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 [[http://www.dcc.uchile.cl/jpiquer/Docencia/cc31a/2009/tbox.tgz|tbox.tgz]]

====== Clase 19: Threads: capturadora de video ======

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:
<code C>
void PutFrame(TIME tstamp, char *buf);
</code>

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:
<code C>
/* Busca un buffer */
int GetFrame(TIME tstamp);
/* Libera un frame */
void FreeFrame(int i)
</code>

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:
<code C>
/* 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));
}
</code>

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

====== Clase 20: Threads: Filósofos muertos de hambre ======

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!):
<code C>
#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);
}
</code>

Si ejecutan este código, después de un rato aleatorio, termina bloqueándose para siempre en un //deadlock//. El problema es que podemos caer en el caso en que cada filósofo tiene un tenedor y está esperando que su vecine suelte el otro, formando un ciclo de espera infinito. Para evitar este //deadlock// debemos esperar una condición (que ambos tenedores estén desocupados) sin tomar ninguno. Con condiciones queda así:

<code C>
#include <stdio.h>
#include <pthread.h>

/*
 * Solucion con condiciones: sin deadlocks pero, ¿es justa?
 */

#define N_FILO 4

pthread_mutex_t table;
pthread_cond_t forks2[N_FILO];
int forks[N_FILO];

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(&table);
	while(forks[f] != 1 || forks[(f+1)%N_FILO] != 1)
 	    pthread_cond_wait(&forks2[f], &table);
	forks[f]=forks[(f+1)%N_FILO]=0;
 	pthread_mutex_unlock(&table);
        comer(f);
 	pthread_mutex_lock(&table);
 	forks[f] = forks[(f+1)%N_FILO] = 1;
	pthread_cond_signal(&forks2[(f-1+N_FILO)%N_FILO]);
	pthread_cond_signal(&forks2[(f+1)%N_FILO]);
 	pthread_mutex_unlock(&table);
    }
    printf("%d: finito!\n", f);
    return NULL;
}
	
main() {
    int i;
    pthread_t pid[N_FILO];

    pthread_mutex_init(&table, NULL);

    for(i=0; i < N_FILO; i++) {
	pthread_cond_init(&forks2[i], NULL);
	forks[i] = 1;
    }
    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);
}
</code>

Un nuevo problema que aparece al resolver este deadlock es la justicia: ¿podemos garantizar que todos los filósofos comerán algún día? ¿Todos reciben comida al mismo ritmo? Pues no. Si ejecutan este programa, verán que se genera un orden de a pares donde 2 filósofos comen mucho más que los otros 2. Hacer una solución justa es complejo y requiere usualmente manejar las colas de espera a mano. El conflicto habitual es al señalar una condición y despertar un thread y luego liberar el mutex. ¿Quién parte ejecutando? Puede entrar un nuevo thread que esperaba en el mutex, o puede partir el thread que se despertó de su condición. Usualmente, no sé quién es.

El fenómeno de la injusticia en sincronización puede llegar al extremo que un filósofo no coma nunca y muera de hambre. Por eso, se conoce como el problema de //starvation// o inanición.

====== Clase 21: jsockets: clientes/servidores de red ======

===== Servidor de Eco Mono-Cliente =====

En esta parte usaremos una API simplificada de sockets que llamamos "jsocket6", que incluye soporte transparente para IPv4 junto con IPv6. 

La idea es que necesitamos un nombre de computador (como "dcc.uchile.cl") y un número de port (como 1818) para encontrar un servidor particular. A lo largo de los ejemplos usaremos "localhost" como nombre de computador y 1818 como port. Eso permite probar los programas en un computador que ni siquiera está conectado a Internet.

Este es el primer servidor que escribiremos, que simplemente responde todo lo que recibe: server_echo.c
<code C>
#include <stdio.h>
#include <stdlib.h>
#include "jsocket6.h"

/* 
 * server_echo: servidor de echo mono-cliente
 */

#define BUF_SIZE 200

main() {
   int s, s2;
   int cnt, size = BUF_SIZE;
   char buf[BUF_SIZE];

   s = j_socket();

   if(j_bind(s, 1818) < 0) {
	fprintf(stderr, "bind failed\n");
	exit(1);
   }

   for(;;) {
	s2 = j_accept(s);
	fprintf(stderr, "cliente conectado: %d\n", s2);
        while((cnt=read(s2, buf, size)) > 0)
	    write(s2, buf, cnt);
        close(s2);
	fprintf(stderr, "cliente desconectado\n");
   }
}
</code>

Este servidor lo podemos probar directamente vía telnet en la misma máquina:
<code>
% telnet localhost 1818
hola
hola
...
</code>

Pero también podemos hacer un cliente de ejemplo:

<code C>
#include <stdio.h>
#include <stdlib.h>
#include "jsocket6.h"

#define BUF_SIZE 10

main() {
   int s;
   int cnt, n, size = BUF_SIZE;
   char buf[BUF_SIZE];

   s = j_socket();

   if(j_connect(s, "localhost", 1818) < 0) {
	fprintf(stderr, "connection refused\n");
	exit(1);
   }

   write(s, "hola", 5);
   n = 0;
   while((cnt=read(s, buf+n, size-n)) > 0) {
	n += cnt;
	if(n >= 5) break;
   }
   printf("%s\n", buf);
   close(s);
}
</code>

O uno que envía toda su entrada estándar al servidor y todo lo que recibe de vuelta lo envía a su salida estándar:
<code C>
#include <stdio.h>
#include <stdlib.h>
#include "jsocket6.h"

#define BUF_SIZE 1024

main() {
   int s;
   int cnt, cnt2;
   char buf[BUF_SIZE];

   s = j_socket();

   if(j_connect(s, "localhost", 1818) < 0) {
	fprintf(stderr, "connection refused\n");
	exit(1);
   }

   while((cnt=read(0, buf, BUF_SIZE)) > 0) {
	if(write(s, buf, cnt) != cnt) {
	   fprintf(stderr, "Falló el write al servidor\n");
	   exit(1);
	}
	while(cnt > 0 && (cnt2=read(s, buf, BUF_SIZE)) > 0) {
	   write(1, buf, cnt2);
	   cnt -= cnt2;
	}
   }

   exit(0);
}
</code>

===== Servidor Multi-Clientes con Fork =====

El problema de esa solución de servidor es que no puede atender otro cliente mientras está con uno conectado. Para soportar múltiples clientes simultáneos, podemos crear un hijo por cada cliente que se encargue de atenderlo:
<code C>
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <wait.h>
#include "jsocket6.h"

/*
 * server_echo2: servidor de echo multi-cliente usando procesos pesados
 * si un hijo muere, no importa
 * si mato con ctrl-C se mueren todos: para independizarse del terminal
 * debieramos usar setpgrp()
 */

#define BUF_SIZE 200

/*
 * Esta es la forma mas simple de enterrar a los hijos sin complicarse la vida
 */
void child() {
    int status;

    while(waitpid(-1, &status, WNOHANG)>0)
		;
}

/*
 * Este es el servidor y el codigo para un socket cliente ya conectado: s
 */
void serv(int s) {
   int cnt, size = BUF_SIZE;
   char buf[BUF_SIZE];

    fprintf(stderr, "cliente conectado\n");
    while((cnt=read(s, buf, size)) > 0)
	 write(s, buf, cnt);
    fprintf(stderr, "cliente desconectado\n");
}

/*
 * Este es el principal: solo acepta conexiones y crea a los hijos servidores
 */
main() {
   int s, s2;

   signal(SIGCHLD, child);

   s = j_socket();

   if(j_bind(s, 1818) < 0) {
	fprintf(stderr, "bind failed\n");
	exit(1);
   }

   for(;;) {
	s2 = j_accept(s);
	if(fork() == 0) { /* Este es el hijo */
	    close(s); /* cerrar el socket que no voy a usar */
	    serv(s2);
	    exit(0);
	} else
	    close(s2); /* cerrar el socket que no voy a usar */
   }
}
</code>

Si quiséramos limitar el máximo de procesos hijos vivos que mantenemos:
<code C>
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <wait.h>
#include "jsocket6.h"

/*
 * server_echo2.5: servidor de echo multi-cliente usando procesos pesados
 * si un hijo muere, no importa
 * si mato con ctrl-C se mueren todos: para independizarse del terminal
 * debieramos usar setpgrp()
 * Este tiene un control de hijos: acepta máximo MAX_PROCS clientes simultáneos
 */

#define BUF_SIZE 200
#define MAX_PROCS 2

/*
 * Esta es la forma mas simple de enterrar a los hijos sin complicarse la vida
 */

int chld_cnt = 0;

void child() {
    int status;

    while(waitpid(-1, &status, WNOHANG)>0)
		chld_cnt--;
}

/*
 * Este es el servidor y el codigo para un socket cliente ya conectado: s
 */
void serv(int s) {
   int cnt, size = BUF_SIZE;
   char buf[BUF_SIZE];

    fprintf(stderr, "cliente conectado\n");
    while((cnt=read(s, buf, size)) > 0)
	 write(s, buf, cnt);
    fprintf(stderr, "cliente desconectado\n");
}

/*
 * Este es el principal: solo acepta conexiones y crea a los hijos servidores
 */
main() {
   int s, s2;

   signal(SIGCHLD, child);

   s = j_socket();

   if(j_bind(s, 1818) < 0) {
	fprintf(stderr, "bind failed\n");
	exit(1);
   }

   for(;;) {
	s2 = j_accept(s);
	if(chld_cnt >= MAX_PROCS) {
	    close(s2);
	    continue;
  	}
	chld_cnt++;
	if(fork() == 0) { /* Este es el hijo */
	    close(s); /* cerrar el socket que no voy a usar */
	    serv(s2);
	    exit(0);
	} else
	    close(s2); /* cerrar el socket que no voy a usar */
   }
}
</code>
====== Clase 22: Servidor Multi-Clientes con Threads ======

Ahora usamos un thread para cada uno:
<code C>
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <pthread.h>
#include "jsocket6.h"

/*
 * server_echo4: servidor multi-clientes con threads
 */

/*
 * Este es el servidor que recibe el socket conectado: s
 */

#define BUF_SIZE 200

void serv(int s) {
   int cnt, size = BUF_SIZE;
   char buf[BUF_SIZE];

    fprintf(stderr, "cliente conectado\n");
    while((cnt=read(s, buf, size)) > 0)
	 if(write(s, buf, cnt) < 0) break; /* broken pipe */

   close(s);
   fprintf(stderr, "cliente desconectado\n");
}

main() {
   int s, s2;
   pthread_t pid;

   signal(SIGPIPE, SIG_IGN);

   s = j_socket();

   if(j_bind(s, 1818) < 0) {
	fprintf(stderr, "bind failed\n");
	exit(1);
   }

/* Cada vez que se conecta un cliente le creo un thread */
   for(;;) {
	if( pthread_create(&pid, NULL, (void *)serv, (void *)j_accept(s)) != 0) {
	    fprintf(stderr, "No pude crear thread!!!\n");
	    exit(1);
	}
   }
}
</code>

===== Servidor Multi-cliente con select =====

Atendemos todos los clientes en el mismo ciclo, usando select:
<code C>
#define _BSD_SOURCE 1

#include <stdio.h>
#include <stdlib.h>
#include "../jsocket.h"
#include <sys/time.h>
#include <sys/types.h>
#include <unistd.h>
#include <signal.h>

/*
 * server_echo3: servidor multi-clientes usando select
 */

/*
       int select(int numfds, fd_set *readfds, fd_set *writefds ,
       fd_set *exceptfds, struct timeval * timeout);

       FD_CLR(int fd, fd_set *set);
       FD_ISSET(int fd, fd_set *set);
       FD_SET(int fd, fd_set *set);
       FD_ZERO(fd_set * set);
*/

#define BUF_SIZE 200
#define MAX_CLIENTS 2

main() {
   int s, s2;
   int cnt, size = BUF_SIZE;
   char buf[BUF_SIZE];
   int ret;
   fd_set mask;
   int client[MAX_CLIENTS];
   int i;

/* para no morirme al morir un cliente */
   signal(SIGPIPE, SIG_IGN);

/* Arreglo de sockets de los clientes */
   for( i = 0; i < MAX_CLIENTS; i++ )
	client[i] = -1;

   s = j_socket();

   if(j_bind(s, 1818) < 0) {
	fprintf(stderr, "bind failed\n");
	exit(1);
   }

   for(;;) {
	FD_ZERO(&mask);
	FD_SET(s, &mask);	/* el socket de accept */
	for(i = 0; i < MAX_CLIENTS; i++) /* cada socket cliente */
		if( client[i] != -1 )
		    FD_SET(client[i], &mask);

/* espero que haya actividad en algun socket */
	ret = select( getdtablesize(), &mask, NULL, NULL, NULL);

	if( ret <= 0 ) { perror("select"); exit(-1);}

/* Atendemos los clientes con datos */
	for(i = 0; i < MAX_CLIENTS; i++) {
	    if(client[i] != -1 && FD_ISSET(client[i], &mask)) {
		if( (cnt=read(client[i], buf, size)) > 0) && 
	    	    write(client[i], buf, cnt) > 0)
			;
		else { /* murio un cliente */
		    fprintf(stderr, "cliente desconectado\n");
		    close(client[i]);
		    client[i] = -1;
		}
	    }
	}

/* aceptamos conexion pendiente si hay una */
	if(FD_ISSET(s, &mask)) {
	    for( i = 0; i < MAX_CLIENTS; i++ )
		if(client[i] == -1) break;
	    if(i == MAX_CLIENTS) {
		fprintf(stderr, "No mas clientes!\n");
		close(j_accept(s)); /* lo rechazo */
		continue;
	    }
	    client[i] = j_accept(s);
	    fprintf(stderr, "cliente conectado\n");
	}
   }
}
</code>

Se necesita definir la macro _BSD_SOURCE al inicio del programa para hacer válido el uso de la función getdtablesize().  El encabezado de esta función está incluido en unistd.h, pero solo cuando se define la macro _BSD_SOURCE.  Eso se indica en la documentación de getdtablesize:

<code>
  % man 3 getdtablesize
  NAME
       getdtablesize - get descriptor table size

  SYNOPSIS
       #include <unistd.h>

       int getdtablesize(void);

     Feature Test Macro Requirements for glibc (see feature_test_macros(7)):

       getdtablesize():
           Since glibc 2.12:
               _BSD_SOURCE ||
                   !(_POSIX_C_SOURCE >= 200112L || _XOPEN_SOURCE >= 600)
</code>


===== Proxy genérico =====

Se trata de escribir un programa que haga de "proxy" de un servidor: se trata de instalar un intermediario que simula ser un servidor, pero que en realidad "representa" a otro servidor que ahora está en otra máquina. Es como un "forwarder" que sirve para instalarlo si movemos un servidor de una máquina a otra y queremos que los clientes antiguos sigan funcionando, o para instalar en un computador que es accesible desde Internet para representar un servidor que está en un computador sin acceso a Internet (una intranet por ejemplo). La invocación de este proxy es:
<code>
% ./proxy port-in server port-out
</code>
Escucha en la máquina local conexiones que llegan a port-in, luego se conecta a (server, port-out) y luego envía y recibe todos los datos de ambos lados. Haremos dos versiones, una que crea dos procesos hijos (uno que copia en una
dirección del socket y otro que copia en la dirección opuesta) y otra con select que queda mejor.

Solución con 2 hijos:
<code C>
 #include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <wait.h>
#include "jsocket6.h"

/*
 * proxy: proxy multi-cliente usando procesos pesados
 * Hacer version con select?
 */

#define BUF_SIZE 200

/*
 * Esta es la forma mas simple de enterrar a los hijos sin complicarse l
a vida
 */
void child() {
    int status;

    while(waitpid(-1, &status, WNOHANG)>0)
		;
}

void die() {
    fprintf(stderr, "cliente desconectado\n");
    exit(0);
}

/*
 * Este es el servidor y el codigo para un socket cliente ya conectado: 
 */
void proxy(int s1, char *host, int portout) {
   int cnt, size = BUF_SIZE;
   char buf[BUF_SIZE];
   int s2;
   int pid;

   signal(SIGUSR1, die);

   s2 = j_socket();

   if(j_connect(s2, host, portout) < 0) {
	fprintf(stderr, "connection refused to %s/%d\n", host, portout);
	exit(1);
   }
   fprintf(stderr, "cliente conectado\n");
	
   if((pid = fork()) < 0) {
    	fprintf(stderr, "no pude fork\n");
	exit(1);
   }

   if(pid == 0) {
    	while((cnt=read(s1, buf, size)) > 0)
	    if(write(s2, buf, cnt) < 0) break;
	kill(getppid(), SIGUSR1);
	exit(0);
   } else
    	while((cnt=read(s2, buf, size)) > 0)
	    if(write(s1, buf, cnt) < 0) break;

    kill(pid, SIGKILL);
    fprintf(stderr, "cliente desconectado\n");
}

/*
 * Este es el principal: solo acepta conexiones y crea a los hijos servi
dores
 */
main(int argc, char **argv) {
   int s, s2;
   int portin, portout;
   char *host;

   if(argc != 4) {
	fprintf(stderr, "Use: %s port-in host port-out\n", argv[0]);
	exit(1);
   }

   portin = atoi(argv[1]);
   host = argv[2];
   portout = atoi(argv[3]);

   signal(SIGCHLD, child);

   s = j_socket();

   if(j_bind(s, portin) < 0) {
	fprintf(stderr, "bind failed\n");
	exit(1);
   }

   for(;;) {
	s2 = j_accept(s);
	if(fork() == 0) { /* Este es el hijo */
	    close(s); /* cerrar el socket que no voy a usar */
	    proxy(s2, host, portout);
	    exit(0);
	} else
	    close(s2); /* cerrar el socket que no voy a usar */
   }
}
</code>

Y una mejor con select:
<code C>
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <wait.h>
#include "jsocket6.h"

/*
 * proxy: proxy multi-cliente usando procesos pesados
 * version con select
 */

#define BUF_SIZE 200

/*
 * Esta es la forma mas simple de enterrar a los hijos sin complicarse l
a vida
 */
void child() {
    int status;

    while(waitpid(-1, &status, WNOHANG)>0)
		;
}

/*
 * Este es el servidor y el codigo para un socket cliente ya conectado: 
s
 */
void proxy(int s1, char *host, int portout) {
   int cnt, size = BUF_SIZE;
   char buf[BUF_SIZE];
   int s2;
   int pid;
   fd_set mask;

   s2 = j_socket();

   if(j_connect(s2, host, portout) < 0) {
	fprintf(stderr, "connection refused to %s/%d\n", host, portout);
	exit(1);
   }
   fprintf(stderr, "cliente conectado\n");
	
/*
       int select(int numfds, fd_set *readfds, fd_set *writefds ,
       fd_set *exceptfds, struct timeval * timeout);

       FD_CLR(int fd, fd_set *set);
       FD_ISSET(int fd, fd_set *set);
       FD_SET(int fd, fd_set *set);
       FD_ZERO(fd_set * set);
*/
   
   
    for(;;) {
        FD_ZERO(&mask);
        FD_SET(s1, &mask); FD_SET(s2, &mask);
	select(getdtablesize(), &mask, NULL, NULL, NULL);
	if(FD_ISSET(s1, &mask)) {
    	    cnt=read(s1, buf, size);
	    if(cnt <= 0) {
    		fprintf(stderr, "cliente desconectado\n");
		exit(0);
	    }
	    write(s2, buf, cnt);
	}
	if(FD_ISSET(s2, &mask)) {
    	    cnt=read(s2, buf, size);
	    if(cnt <= 0) {
    		fprintf(stderr, "cliente desconectado\n");
 		exit(0);
	    }
	    write(s1, buf, cnt);
	}
    }
}

/*
 * Este es el principal: solo acepta conexiones y crea a los hijos servi
dores
 */
main(int argc, char **argv) {
   int s, s2;
   int portin, portout;
   char *host;

   if(argc != 4) {
	fprintf(stderr, "Use: %s port-in host port-out\n", argv[0]);
	exit(1);
   }

   portin = atoi(argv[1]);
   host = argv[2];
   portout = atoi(argv[3]);

   signal(SIGCHLD, child);

   s = j_socket();

   if(j_bind(s, portin) < 0) {
	fprintf(stderr, "bind failed\n");
	exit(1);
   }

   for(;;) {
	s2 = j_accept(s);
	if(fork() == 0) { /* Este es el hijo */
	    close(s); /* cerrar el socket que no voy a usar */
	    proxy(s2, host, portout);
	    exit(0);
	} else
	    close(s2); /* cerrar el socket que no voy a usar */
   }
}
</code>


El tar GZ con todos los códigos incluidos hasta aquí 
[[http://www.dcc.uchile.cl/jpiquer/Docencia/cc31a/jsockets.tgz|jsockets 6]].

====== Clase 23: sh, awk, perl ======

Manual de introducción al tema (un poco viejo pero útil) en: 

[[http://www.dcc.uchile.cl/jpiquer/Docencia/cc31a/perl.pdf|Apunte Perl]]

Aquí veremos ejemplos simples de código perl con aplicaciones 'clásicas'.

Primero tomemos un procesador de log de transferencias parecido al del apunte. La bitácora contiene líneas que dicen en alguna parte "host=servername", por ejemplo:
<code>
## ignorar esta linea
1,2 host=ftp.dcc.uchile.cl 4
1,2 host=ftp 3,5,61,2,3,4,5,6
1,2 host=dcc.uchile.cl 2,5,61,2,3,4,5,6
1,2 host=dcc.uchile.cl 3,5,61,2,3,4,5,6
1,2 host=ftp 4,5,61,2,3,4,5,6
1,2 host=kk 4,5,61,2,3,4,5,6
1,2 host=dcc 4,5,61,2,3,4,5,6
1,2 host=dcc.uchile.cl 3,l,61,2,3,4,5,6
1,2 host=ftp 4
1,2 host=ftp.dcc.uchile.cl 4,5,61,2,3,4,5,6
1,2 host=dcc. 3,5,61,2,3,4,5,6
</code>
y queremos hacer un análisis sobre los distintos nombres de computador que aparecen en el log.
<code>
#!/usr/bin/perl

# uso de arreglos asociativos
while(<>)
{
    if( /.*host=([^ ]+) .*/ ) {
        $freq_tab{$1} = $freq_tab{$1} + 1;
    }
}

# lo recorro sin ningun orden
foreach $key (keys %freq_tab) {
   print "$freq_tab{$key}	$key\n";
}
</code>

Ahora queremos mostrar los resultados ordenados de más frecuente a menos frecuente, para lo que usamos el comando sort y un pipe hacia él:

<code>
 #!/usr/bin/perl

# uso de arreglos asociativos
while(<>)
{
    if( /.*host=([^ ]+).*/ ) {
        $freq_tab{$1} = $freq_tab{$1} + 1;
    }
}

open(OUT, "| sort -rn");
# select redirige la salida estandar
select(OUT);
foreach $key (keys %freq_tab) {
   print "$freq_tab{$key}	$key\n";
}
close(OUT);
</code>

Otro ejemplo es listar todos los archivos que comiencen con 'a':
<code>
#!/usr/bin/perl

# lista todos los archivos del directorio actual que empiezan con 'a'

system("ls a*");
</code>

Usamos el comando ls y el shell para expandir los nombres.

Esto también se puede hacer internamente en perl, tomando la salida de ls como una lista:
<code>
#!/usr/bin/perl

# lista todos los archivos del directorio actual que empiezan con 'a'

foreach $name (`ls`) {
    print "$name" if($name =~ /^a/); # en perl el cuerpo del if (si es una sola insruccion) puede ir a la izq
}
</code>

Pero en perl siempre existen muchas formas de hacer lo mismo. Primero, eliminando variables innecesarias: en perl la mayoría de las funciones se aplican sobre una variable default: $_ que, si no se escribe, funciona igual:

<code>
#!/usr/bin/perl

# lista todos los archivos del directorio actual que empiezan con 'a'

foreach (`ls`) {
    print if(/^a/);
}
</code>

Si no quiero usar el shell y manejar los nombres internamente, tengo funciones más parecidas a C:
<code>
#!/usr/bin/perl

opendir(FILES,".");
@files=readdir(FILES);
closedir(FILES);

print join("\n", grep {/^a/} @files); # grep retorna una sublista de la lista que calza con el patrón

print "\n";
</code>