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

11 martie 2011

Introducere in C#

INTRODUCERE

Variabilele/metodele unei clase pot fi de tipul:
* public - sunt vizibile pentru toate clasele
* private - vizibile doar claselor carora le apartin
* protected - vizibile claselor carora le apartin si celor care le mostenesc (subclase)

Mai putin folosite sunt cele:
* internal - pot fi accesate din acelasi cod assembler, nu si din altul
* protected internal - la fel ca internal, insa pot fi accesate si din alt cod assemble ce corespunde unei clase derivate
* static - clasa nu poate fi instantiata, membrii sai fiind la randul lor statici

Ce sunt proprietatile?
- membrii ai claselor care ofera un mecanism de citire, scriere sau calcul de valori ale campurilor private clasei respective


EXEMPLU

O clasa abstracta numita Forma. Abstracta inseamna ca nu poate fi instantiata (dar poate fi mostenita de catre o alta clasa).


public abstract class Forma {

private string culoare;
private int left;
private int top;
//proprietati ~ incapsulare
public string Culoare
{
get { return culoare; } //puteau fi actiuni + return
set { culoare = value; }
}

public int Left
{
get { return left; }
set { left = value; }
}

public int Top
{
get;
set;
}
public Forma() {
Console.WriteLine("Sunt o forma draguta");
left = 0; top = 0;
}

public void Deseneaza(string what) {
Console.WriteLine("Am desenat "+what);
}

public void Muta() {
Console.WriteLine("Am mutat o forma; left="+left+" si top="+top); //parametri
}

public void Sterge() {
Console.WriteLine("Am sters forma");
}
}


Mostenirea (derivarea) este procesul prin care o clasa primeste toate variabilele si metodele ne-private ale unei alte clase, putand avea si propriile variabile sau metode, pe langa acestea.

Interfata:
* seamana cu o clasa abstracta prin faptul ca orice clasa ce o mosteneste trebuie sa ii implementeze metodele (care exista neimplementate in interfata)
* nu poate fi instantiata direct
* clasele si structurile pot mosteni mai multe interfete, iar la randul ei o interfata poate mosteni mai multe interfete


EXEMPLU

public class Linie : Forma {

public int lungime;
Punct p1, p2;

public Linie(Punct p1, Punct p2) {
this.p1 = p1;
this.p2 = p2;
lungime = (int)Math.Sqrt(Math.Pow(p1.X - p2.X, 2) + Math.Pow(p1.Y - p2.Y,2));
Console.WriteLine("Lungimea liniei este: " + lungime);
}
}


Pe langa clase si obiecte (=instante ale claselor), se afla si structurile, niste "obiecte" mai restranse prin faptul ca nu detin metode si nu pot fi mostenite.

public struct Punct
{
public int X;
public int Y;
}


Ceva mai restrans decat structurile se afla enumeratiile .

public enum TipImagine { Bmp, Jpeg, Png }


In C# -ca o particularitate- in interiorul codului putem gasi regiuni cu simplu rol in vizibilitate . In Visual Studio aceasta regiune se poate restrange pentru a economisi spatiu ocupat pe ecran, sau se poate expanda pentru a o vedea in detaliu.

#region Variable
int a = 5;
int b = 10;
int c = a + b;
string str = c.ToString();
#endregion


Alte notiuni importante sunt:
* incapsularea - sau "ascunderea informatiei" - variabilele membre care sunt private vor fi incapsulate pentru a putea fi accesate doar de anumite metode sau proprietati.
De exemplu: intr-o clasa avem o variabila privata x si o metoda publica ce se ocupa cu setarea lui x. Astfel, nu vom putea seta variabila x direct ci prin intermediul metodei.
* polimorfismul - o clasa poate mosteni alta clasa si in acelasi timp poate suprascrie anumite metode. In C#, clasa originala ar avea metoda respectiva virtuala, in timp ce clasa ce o mosteneste o va denumi override.

09 martie 2011

Ierarhia de memorii


Urmatoarele exemple testeaza timpul efectuarii unei operatii pe un vector :

1) Consideram inmultirea unui vector de dimensiune foarte mare cu un scalar, in mai multi pasi. In pasul 1 accesam fiecare element din vector unul dupa altul si facem operatia, la pasul 2 accesam elementele din 2 in 2 cu revenire (intai consideram pozitiile impare apoi cele pare) si facem operatiile, si asa mai departe cu un pas de lungime maxima = lungimea vectorului, asa incat la final accesam doar prima pozitie din vector, reincarcam vectorul si accesam a doua pozitie.... pana la final.
Ceea ce se observa este ca, teoretic, timpii calculatii corespunzatori fiecarui pas cresc treptat, pana ajung sa se stabilizeze. Timpii cresc cu atata cat ii ia incarcarii in memoria cache a vectorului.
In programul C, s-a folosit functia gettimeofday pentru aflarea orei exacte, pana la microsecunde (care este si ordinul de marime cu care se incarca datele specific cache-ului L2). Dupa fiecare pas, se face diferenta t2-t1 si se afiseaza aceasta valoare /cam la 10.000 pasi/ (pentru a nu se scrie pe ecran prea multe valori).


#include "stdio.h"
#include "sys/time.h"
#include "time.h"
#include "stdlib.h"

int main() {
int pas = 1, n = 100000, i, *v, scalar = 4;
v = (int *)malloc(n*sizeof(int));
for (i=0; i<=n-1; i++)
v[i] = i%10;
struct timeval tv;
time_t t1, t2;

do {
gettimeofday(&tv, NULL);
t1 = tv.tv_usec;
int j;
for(j=0; j<=pas-1; j++)
for(i=j; i<=n-1; i+=pas)
v[i] *= scalar;
gettimeofday(&tv, NULL);
t2 = tv.tv_usec;
if(pas%10000==1)
printf("pasul %d:\t t1=%d t2=%d\t t2-t1=%ld\n", pas, t1,t2, t2-t1);
pas++;
} while (pas<=n-1);

return 0;
}


2) Al doilea exemplu e asemanator, doar ca nu se mai folosesc pasii anteriori, ci se variaza dimensiunea vectorului a.i. sa ocupe intre 1M la inceput -> 12 M , cu un `pas` de 0.5M .
Ceea ce ar trebui sa se observe este scaderea performantei la modul urmator:

#include "stdio.h"
#include "sys/time.h"
#include "time.h"
#include "stdlib.h"

#define MAX 3145728 // 12MB
#define pas_dim 131072 // 0.5MB

// pt cache L2

int main() {
long int n = 32768, *v; // 2^20/32
int i, scalar = 4;
v = (long int *)malloc(MAX*sizeof(long int));
for (i=0; i<=MAX-1; i++)
v[i] = i%10;

struct timeval tv;
time_t t1, t2;

do {
gettimeofday(&tv, NULL);
t1 = tv.tv_usec;
for(i=0; i<=n-1; i++)
v[i] *= scalar;
gettimeofday(&tv, NULL);
t2 = tv.tv_usec;
n = n+pas_dim;

printf("dim %ld:\t t1=%d t2=%d\t (t2-t1)/n*1000=%lf\n", n, t1,t2, (t2-t1)/(double)n);

} while (n<=MAX-1);

return 0;
}

03 martie 2011

Extinderea sistemului de fisiere din Ubuntu

Probabil ca exista mai multe metode, descrise aici, dar eu as vrea sa detaliez putin cea de-a 3-a metoda:

Pentru a redimensiona sistemul de fisiere in care este incarcat Ubuntu (sau orice alta distributie Linux), cel mai bun utilitar este gparted . Acest program se poate descarca si din bash, cu apt-get install gparted , si intr-adevar cu el se pot redimensiona anumite partitii, care intai trebuie unmounted . Insa in cazul sistemului de fisiere ( "/" ), acest lucru nu mai este posibil pentru ca odata ce Linuxul este bootat sistemul de fisiere devine mounted.

De aceea, gparted trebuie rulat live, adica bootat de pe un stick usb (asa este cel mai la indemana). Pentru aceasta, ne folosim de utilitarul unetbootin, care ruleaza si in interfata grafica. Odata pornit, se selecteaza a doua optiune "Disc Image" - ISO - si se selecteaza calea unde a fost descarcat programul gparted. In functie de locul unde dorim sa cream bootabilul, alegem tipul (sa zicem Disc USB) si Dispozitivul (aici de obicei detecteaza automat). Cu aceste setari se creeaza noul continut bootabil pe stickul USB.

Restartand calculatorul, se booteaza de pe stick (atentie la BIOS care trebuie setat sa booteze intai de pe stick) si se intra in gparted live . Programul va afisa structura partitiilor si dimensiunile lor. De tinut minte este urmatorul lucru: nu putem redimensiona sistemul de fisiere decat daca inaintea acestuia exista un spatiu nealocat. Cu alte cuvinte, degeaba avem n GB nealocati pe partitia care vine dupa sistemul de fisiere pe care vrem sa il redimensionam, nu ne vom putea folosi de acestia. De aceea, intai trebuie redimensionata (micsorata) partitia care vine inaintea sistemului de fisiere al nostru, iar cu acel spatiu nealocat putem creste dimensiunea sistemului de fisiere.