30 martie 2011

Exemple cu semnale - Linux

1. Urmatorul program trateaza semnale intre 20 (SIGTSTP) si 25 (SIGXFSZ), afisand pentru fiecare cate un caracter. Intr-un alt terminal se va tasta pgrep hitme , apoi kill -x pid , unde x este semnalul dorit, iar pid id-ul procesului aflat cu pgrep.

#include "stdio.h"
#include "string.h"
#include "signal.h"
#include "unistd.h"
#include "utils.h"

int must_leave = 0;

static void sig_handler(int signum)
{
switch(signum) {

case SIGTSTP:
printf("H");
break;

case SIGTTIN:
printf("e");
break;

case SIGTTOU:
printf("l");
break;

case SIGURG:
printf("l");
break;

case SIGXCPU:
printf("o");
break;

case SIGXFSZ:
printf("\n");
must_leave = 1;
break;

default:
printf("Go back and send the following signals: 20, 21, 22, 23, 24");
must_leave = 1;
}
fflush(stdout);
}

int main(void)
{
struct sigaction signals;
sigset_t mask;
int rc;

sigemptyset(&mask);

memset(&signals, 0, sizeof(struct sigaction));
signals.sa_flags = 0;
signals.sa_mask = mask;

signals.sa_handler = sig_handler;
rc = sigaction(SIGTSTP, &signals, NULL);
DIE(rc == -1, "sigaction");

rc = sigaction(SIGTTIN, &signals, NULL);
DIE(rc == -1, "sigaction");

rc = sigaction(SIGTTOU, &signals, NULL);
DIE(rc == -1, "sigaction");
rc = sigaction(SIGURG, &signals, NULL);
DIE(rc == -1, "sigaction");
rc = sigaction(SIGXCPU, &signals, NULL);
DIE(rc == -1, "sigaction");

rc = sigaction(SIGXFSZ, &signals, NULL);
DIE(rc == -1, "sigaction");
while(!must_leave) sleep(1);

return 0;
}


2. Urmatorul program face busy waiting, afisand la consola numere consecutive. Intercepteaza semnale generate de CTRL+\, CTRL+C, SIGUSR1. Fiecare semnal are asociat handler-ul ask_handler, iar pentru fiecare semnal primit programul va intreba daca este cazul sa se termine sau nu.


#define MY_MAX 32
#define TIMEOUT 1

static void print_next(void)
{
static int n = 1;

printf("n = %d\n", n);

n = (n + 1) % MY_MAX;
}

/* signal handler */
static void ask_handler(int signo)
{
char buffer[128];
printf("Got %d - Stop program? [Y/n] ", signo);
fflush(stdout);
fgets(buffer, 128, stdin);
buffer[strlen(buffer)-1] = '\0';

if (buffer[0] == 'y' || buffer[0] == 'Y')
exit(EXIT_SUCCESS);
}

/* configure handlers */
static void set_signals(void)
{
struct sigaction sa;
int rc;

/* set handler in struct sigaction sa */
sigset_t mask;
sigemptyset(&mask);

memset(&sa, 0, sizeof(struct sigaction));
sa.sa_flags = 0; //
sa.sa_mask = mask;

sa.sa_handler = ask_handler;

/* handle SIGINT, SIGQUIT and SIGUSR1 signals */
sigaction(SIGINT, &sa, NULL);
sigaction(SIGQUIT, &sa, NULL);
sigaction(SIGUSR1, &sa, NULL);
}

int main(void)
{
set_signals();

while (1) {
print_next();
sleep(TIMEOUT);
}

return 0;
}


3. Urmatorul exemplu simuleaza comanda nohup. Programul primeste ca parametru numele comenzii de executat si parametrii comenzii respective, si nu trebuie sa se termine la inchiderea terminalului din care a fost pornit.
Pentru asta, trebuie sa ignore semnalul SIGHUP pe care i-l livreaza shell-ul. Daca outputul programului (stdout) era legat la terminal, acesta va fi redirectat catre un fisier.

/* configure handlers */
static void set_signals(void)
{
struct sigaction sa;
int rc;

memset(&sa, 0, sizeof(sa));

/* ignore SIGHUP */
sa.sa_handler = SIG_IGN;
sigaction(SIGHUP, &sa, NULL);
}

/* execute a new program */
static void exec_func(int argc, char **argv)
{
int rc;

set_signals(); /* ignore SIGHUP */

/* if stdout is a terminal redirect output to NOHUP_OUT_FILE */
if (isatty(STDOUT_FILENO)) {
int new_fd = open ("nohup_out_file", O_CREAT | O_WRONLY, 0644);
rc = dup2 (new_fd, STDOUT_FILENO);
if(rc<0) {
printf("error\n");
exit(0);
}
}

/* replace image of process */
rc = execvp(argv[1], argv+1);
if (rc<0) {
printf("error\n");
exit(0);
}
}

int main(int argc, char **argv)
{
if (argc <= 1) {
fprintf(stderr, "Usage: %s command_and_arguments\n", argv[0]);
exit(EXIT_FAILURE);
}

exec_func(argc, argv);

return 0;
}

4 . In exemplele de mai jos, fiecare proces va crea cate un proces-copil care doar apeleaza exit.

Primul exemplu este de proces zombie, deoarece dupa crearea copilului, parintele nu face wait pe el; deci, intrarea copilului va ramane in tabela de procese, el nemaiexistand practic pentru ca a dat exit.

#define TIMEOUT 20

int main(void)
{
pid_t pid;
int status;

/* create child process without waiting */
pid = fork ();
switch (pid) {
case -1:
exit(-1);
break;
case 0:
exit(0);
default:
sleep(TIMEOUT);
break;
}

return 0;
}

In urmatorul exemplu, parintele creeaza copilul si de asemenea nu ii da wait. Insa nu mai avem de-a face cu un copil zombie pentru ca parintele ignora semnalul de tip SIGCHLD. Pe scurt, daca parintele ignora SIGCHLD prin setarea handler-ului la SIG_IGN, toate informatiile de exit status ale copiilor nu vor fi luate in considerare, si nu se vor lasa procese zombie.

/* configure signal handler */
static void set_signals(void)
{
struct sigaction sa;

memset(&sa, 0, sizeof(sa));

/* ignore SIGCHLD */
sa.sa_handler = SIG_IGN;
sigaction(SIGCHLD, &sa, NULL);
}

int main(void)
{
pid_t pid;
set_signals();

/* create child process without waiting */
pid = fork();

switch (pid) {
case -1:
exit(-1);
break;
case 0:
exit(0);
default:
sleep(TIMEOUT);
break;
}
// fara wait

return 0;
}

Semnale in Linux


Semnalele sunt un concept specific sistemelor de operare UNIX. Un semnal este o întrerupere software, în fluxul normal de execuție a unui proces. Sistemul de operare le folosește pentru a semnala procesului apariția unor situații excepționale oferindu-i procesului posibilitatea de a reacționa. Fiecare semnal este asociat cu o clasă de evenimente care pot apărea și care respectă anumite criterii. Procesele pot trata, bloca, ignora sau lăsa sistemul de operare să efectueze acțiunea implicită la primirea unui semnal (de obicei acțiunea implicită este terminarea procesului).
  • Dacă un proces dorește să ignore un semnal, sistemul de operare nu va mai trimite acel semnal procesului.
  • Dacă un proces specifică faptul că dorește să blocheze un semnal, sistemul de operare nu va mai trimite semnalele de acel tip spre procesul în cauză, dar va salva numai primul semnal de acel tip, restul pierzându-se. Când procesul hotărăște că vrea să primească, din nou, semnale de acel tip, dacă exista vreun semnal în așteptare, acesta va fi trimis.


    Un semnal primit de un proces poate fi generat:
    • fie direct de sistemul de operare - în cazul în care acesta raportează diferite erori;
    • fie de un proces - care-și poate trimite și singur semnale (semnalul va trece tot prin sistemul de operare).



      În general, evenimentele care generează semnale se încadrează în trei categorii majore:
      • O eroare indică faptul că un program a făcut o operație nepermisă și nu-și poate continua execuția. Însă, nu toate tipurile de erori generează semnale (de fapt, cele mai multe nu o fac). De exemplu, deschiderea unui fișier inexistent este o eroare, dar nu generează un semnal; în schimb, apelul de sistem open returnează -1, indicând că apelul s-a terminat cu insucces. În general, erorile asociate cu anumite biblioteci sunt raportate prin întoarcerea unei valori speciale. Erorile care generează semnale sunt cele care pot apărea oriunde în program, nu doar în apelurile din biblioteci. Ele includ împărțirea cu zero și accesarea invalidă a memoriei.
      • Un eveniment extern este, în general, legat de I/O și de alte procese. Ele includ apariția de noi date de intrare, expirarea unui timer și terminarea execuției unui proces copil.
      • O cerere explicită indică utilizarea unui apel de sistem, cum ar fi kill, pentru a genera un semnal.


        Când semnalul a fost primit, fie imediat, fie după o întârziere mare, acțiunea specificată pentru acel semnal este executată. Pentru anumite semnale, cum ar fi SIGKILL și SIGSTOP, acțiunea este fixată(procesul este terminat), dar, pentru majoritatea semnalelor, programul poate alege să:
        • ignore semnalul
        • specifice o funcție de tip handler
        • accepte acțiunea implicită pentru acel tip de semnal.


          Cele mai cunoscute sunt următoarele semnale:
          • SIGINT - transmis la apăsarea combinației CTRL+C;
          • SIGQUIT - în momentul apăsării combinației de taste CTRL+\;
          • SIGSEGV - în momentul accesării unei locații invalide de memorie etc;
          • SIGKILL - nu poate fi ignorat sau suprascris. Transmiterea acestui semnal are ca efect terminarea procesului, indiferent de context.

17 martie 2011

Optimizarea codului de inmultire a 2 matrici

Un program simplu arata cam asa:

int main() {

// a, b, c fiind matricile : input (a,b) si output (c)

int k;
for (i=0; i<=n-1; i++)
for(j=0; j<=n-1; j++) {
for(k=0; k<=n-1; k++)
c[i][j] += a[i][k]*b[k][j];
}

return 0;
}

O prima optimizare este sa pastram suma partiala intr-un registru, pentru a evita timpul de si numarul de accese la c[i][j]:

int k;
for (i=0; i<=n-1; i++)
for(j=0; j<=n-1; j++) {
register double sum = 0.0;
for(k=0; k<=n-1; k++)
sum += a[i][k]*b[k][j];
c[i][j] = sum;
}

O alta optimizare ar fi modul de accesare a lui a[i][k], b[k][j] si c[i][j] prin intermediul unor pointeri si incrementarea acestora in functie de modul de deplasare in matrice:

int k;
double *pa, *pb;
for (i=0; i<=n-1; i++) {
pa = a[0]+i*n;
for(j=0; j<=n-1; j++) {
register double sum = 0.0;
pb = b[0];
for(k=0; k<=n-1; k++) {
pa++;
pb++;
sum += (*pa) * (*pb);
}
c[i][j] = sum;
}
}

In fine, s-a facut o mica comparatie pe criteriul timp intre diverse accesari: i,k,j (varianta buna), varianta medie (primul exemplu - i,j,k) si j,k,i (varianta proasta)

Nota... toate exemplele se testeaza pe matrici de dimensiuni mai mari de 1000, pentru a se vedea mai bine efectele.

Lucrul cu memoria



Cateva exemple pentru a reaminti cum se lucreaza cu pointerii ce refera zone de memorie:

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

#include "utils.h"

char first_name[] = " Harry";
char last_name[] = " Potter";

static char *trim(char *s){

char *p = malloc(strlen(s)+1);
strcpy(p, s);
printf("p=%x\n",p);

int i=0;
while(*p == ' ') {
p++;
i++;
}

printf("p=%x\n",p);

s = malloc(sizeof(p)+1);
s = strcpy(s, p);
free(p-i);
return s;
}

int main(void){

printf("%s %s is learning SO!\n",
trim(first_name), trim(last_name));
return 0;
}

Programul sterge spatiile libere dintr-un nume si le afiseaza, iar la sfarsit elibereaza memoria. Pointerul p se tot deplaseaza pentru a referi zona de memorie urmatoare, insa cand se face free acesta trebuie sa fie pozitionat exact pe inceputul sirului de caractere.


#include "stdlib.h"
#include "stdio.h"

#include "utils.h"

int main(void)
{
int i;
unsigned int n = 0xDEADBEEF;
unsigned char *w;

/* TODO - use w to show all bytes of n in order */
i = -1;
w = (unsigned char*)(&n);
int dim = sizeof(n);
do {
i++;
printf("%x",*(w+dim-i)); // invers!

} while (i<=dim-1);

printf("\n");

return 0;
}

In acest program se scrie numarul n in hexa, folosind pointerul w care parcurge zona de memorie octet cu octet invers, din cauza little-endianess -ului (parcurgerea de la LSB la MSB). Daca sistemul ar fi fost big-endian , atunci parcurgerea s-ar fi facut *(w+i) si nu *(w+dim-i) .


In fine, un exemplu de folosire a variabilelor statice (cu rol de variabila globala, init cu 0):

#include "stdio.h"
#include "stdlib.h"

#include "utils.h"

/**
* TODO - functia inc() must behave like a counter
* The function returns the next value in order and
* does not receive and parameter
*
* You are not allowed to use global variables
*/
int inc()
{
static int c ;
c++;
return c;
}


int main(void)
{
int i;

for (i = 0;i<=10; i++)
printf("%d\n", inc());

return 0;
}

12 martie 2011

Exemplu de bariera in Python

Exemplu de bariera - 10 thread-uri pornesc unul dupa altul si sunt afisate in ordinea intrarii lor, dupa care se face o bariera care asigura ca thread-urile vor astepta ca toate sa termine intrarea pentru a merge mai departe.
Mai departe, sunt eliberate unul cate unul si tinute intr-o alta bariera.


import threading
import time
import random

bariera = threading.Semaphore(value=0)
bariera2 = threading.Semaphore(value=0)
regcritica = threading.Semaphore(value=1)
threads = 10
n=threads
threadlist = []

# asigura ca toate thread-urile ies odata

def folosire(x):
print "[INTRARE]: ",x
barrier()
print "[IESIRE]: ",x
barrier()

def barrier():
global bariera,bariera2, regcritica,n,threads

# prima bariera este de intrare (aduna toate thread-urile)
regcritica.acquire();
n = n - 1;
if n==0:
for i in range(threads):
bariera.release();
regcritica.release();
bariera.acquire();
# a doua bariera este de iesire ( --//-- )
regcritica.acquire()
n = n + 1
if n == threads:
for i in range(threads):
bariera2.release()
regcritica.release()
bariera2.acquire()

random.seed()

for i in range(threads):
thread = threading.Thread(target=folosire, args=(i,)) # arg o functie si arg. ei
thread.start()
threadlist.append(thread)

for i in range(len(threadlist)):
threadlist[i].join()