Nachos: Acquire & Release implementation for Lock

Adaptata la solutia de aici & aici.

#define FREE false
#define BUSY true

Lock::Lock(char* debugName)  {
    name=debugName;
    value=FREE;
    queue=new List;
}

void Lock::Acquire() {
    IntStatus oldLevel = interrupt->SetLevel(IntOff); // disable interrupts
    // if lock not available...
    if (value == BUSY) {
queue->Append (currentThread); // add to queue & go to sleep
currentThread->Sleep();
    }
    // here thread is waken up, the real acquire begins
    value=BUSY;
held=currentThread;  // save the thread which got the lock
    interrupt->SetLevel(oldLevel); // re-enable interrupts
}

void Lock::Release() {
    IntStatus oldLevel = interrupt->SetLevel(IntOff);
    Thread* thread = (Thread *) queue->Remove();
    if (held==currentThread) { // this is necessary to avoid a crazy thread releasing others
        if (thread!=NULL) {
            scheduler->ReadyToRun(thread);    // add it to ready queue
}
        else { // if queue is empty
           value=FREE;
        }
    }
    interrupt->SetLevel(oldLevel);
}


Meanings:
FREE : there is no other thread inside the Lock
BUSY: there is at least one thread either in the queue or in the process of acquiring


// there is a slightly equivalent solution
// however I think the previous one is more meaningful
// variable held is kind of useless here

void Lock::Acquire() {
    IntStatus oldLevel = interrupt->SetLevel(IntOff); // disable interrupts
    // if lock not available...
    while (value == BUSY) {
queue->Append (currentThread); // add to queue & go to sleep
currentThread->Sleep();
    }
    // here thread is waken up, the real acquire begins
    value=BUSY; 
    held=currentThread;
    interrupt->SetLevel(oldLevel); // re-enable interrupts
}

void Lock::Release() {
    IntStatus oldLevel = interrupt->SetLevel(IntOff);
    if (held==currentThread) {
    Thread* thread = (Thread *) queue->Remove();
        if (thread!=NULL) {
            scheduler->ReadyToRun(thread);    // add it to ready queue
}
        value=FREE;
    }
    interrupt->SetLevel(oldLevel);
}

-------------------------

Some differences Lock vs. Semaphore
* Semaphore has a counter of resources whereas Lock is either busy or free. Lock is used for Mutual Exclusion only, i.e, only one thread can access the shared resources at any time.
* Lock has owner whereas Semaphore does not have any owner.
* Lock does not track number of resources/ number of waiting tasks, whereas Semaphore does.
* Only the thread which is the owner of the Lock can Release the lock on resource. Semaphore can be accessed by any thread.
* Semaphore is a shared object while Lock is not.

Hadoop - comenzi utile

* formatare HDFS
> hadoop namenode -format

* pornire demoni Hadoop
> start-all.sh

* verificare că demonii merg
> jps 

* copiere fișiere in HDFS 
> hadoop dfs -copyFromLocal /tmp/numeFolder /user/anna/numeFolder

* verificare
> hadoop dfs -ls /user/anna/numeFolder

* ștergere fișier: -rm , folder -rmr

* ieșire din safe mode (dacă nu merge ștergerea pe HDFS)
> hadoop dfsadmin -safemode leave

* rulare job
> hadoop jar hadoop-examples-1.2.1.jar [args]

* copiere rezultat din Hadoop
> hadoop dfs -copyToLocal /user/anna/numeFolder /tmp/numeFolderOut 

* goodbye Hadoop
> stop-all.sh 

Simularea a 4 algoritmi de scheduling

4 algoritmi pentru planificarea proceselor (sistem cu un singur procesor:) ):
1) First come, first served
2) Shortest Job First
3) Shortest Remaining time first
4) Round Robin

Se gasesc aici .
Pentru detalii de rulare, cititi fisierul de Readme.

Exemplu de folosire memorie virtuala

Implementarea comenzii cp din Linux, folosind mmap :

int main (int argc, char *argv[])
{
int fdin, fdout, rc;
char *src, *dst;
struct stat statbuf;

DIE(argc != 3, "Usage: ./mycp ");

/* Open input and output files */
fdin = open (argv[1], O_RDONLY);
DIE(fdin == -1, "open fdin");

/* Open/create the output file */
fdout = open (argv[2], O_RDWR | O_CREAT | O_TRUNC, 0644);
DIE(fdout == -1, "open fdout");

/* truncate the output file to the input file size */
rc = fstat(fdin, &statbuf);
DIE(rc == -1, "fstat");
double size = (double)statbuf.st_size;
rc = ftruncate(fdout, size);
DIE(rc == -1, "ftruncate");

/* mmap the input and output file */
src = mmap (0, size, PROT_READ, MAP_SHARED, fdin, 0);
DIE( rc==-1, "mmap");
dst = mmap (0, size, PROT_WRITE, MAP_SHARED, fdout, 0); // la MAP_PRIVATE , rezultatul ramane doar in memorie
DIE( rc==-1, "mmap");

/* copy the input file to the output file */
memcpy(dst, src, size);

/* clean up */
rc = munmap(src, size);
DIE(rc == -1, "munmap");
rc = munmap(dst, size);
DIE(rc == -1, "munmap");

/* Close files */
rc = close(fdin);
DIE(rc == -1, "close source");

rc = close(fdout);
DIE(rc == -1, "close destination");

return 0;
}

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.

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;

}

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.

Compilari & Makefile-uri

Exemplu un Makefile care creeaza o biblioteca statica.

Intr-un director avem hexdump.c, hexdump.h, sample.c, main.c si vrem un Makefile astfel incat: la rularea comenzii make libhexdump_static să creeze biblioteca statică libhexdump_static.a (biblioteca va conține fișierele obiect asociate fișierelor hexdump.c și sample.c) si la rularea comenzii make să creeze executabilul main_static obținut din legarea fișierului obiect corespunzător lui main.c cu biblioteca libhexdump_static.a.

all: main_static

main_static: libhexdump_static

gcc -Wall main.c -o main_static -lhexdump_static -L.

libhexdump_static: hexdump.o sample.o

ar rc libhexdump_static.a hexdump.o sample.o

main.o: main.c

hexdump.o:

gcc -Wall -c hexdump.c

sample.o:

gcc -Wall -c sample.c

.PHONY:

clean:

rm -f *.o main_static libhexdump_static.a

Exemplu de Makefile care creeaza o biblioteca dinamica

Avand la dispozitie aceleasi fisiere, la rularea comenzii make libhexdump_dynamic să se creeze biblioteca dinamicălibhexdump_dynamic.so. Biblioteca va conține fișierele obiect asociate fișierelor hexdump.c și sample.c

La rularea comenzii make pe lângă executabilul main_dynamic obținut anterior să se creeze și executabilul main_dynamic obținut din legarea fișierului obiect corespunzător lui main.c cu biblioteca partajată libhexdump_dynamic.so.

all: main_dynamic

main_dynamic: libhexdump_dynamic.so

gcc -Wall main.c -o main_dynamic -lhexdump_dynamic -L.

libhexdump_dynamic: libhexdump_dynamic.so

libhexdump_dynamic.so:

gcc -shared hexdump.o sample.o -o libhexdump_dynamic.so

main.o: main.c

hexdump.o: hexdump.c

sample.o: sample.c

clean:

rm -f *.o main_dynamic libhexdump_dynamic.so

In consola trebuie setata o variabila de mediu: export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:.

Pentru ca loader-ul (programul responsabil cu încărcarea programului în memorie) să știe unde să caute biblioteca partajată pentru a o încărca în memorie în cazul în care aceasta nu a fost încărcată deja.