Drzewo procesow
---------------

***** WSTEP

Wezmy zbior procesow (lub watkow), ktore tworza logiczna strukture DRZEWA.
Procesy (lub watki) sa wezlami w DRZEWIE, a zaimplementowane mechanizmy 
komunikacji krawedziami.
Dokladnie jeden proces (lub watek) jest korzeniem DRZEWA.

Take DRZEWO charakteryzuja trzy parametry:
- stopien   (s) - Kazdy wezel, ktory nie jest lisciem ma dokladnie s synow
- glebokosc (h) - Ilosc pokolen wlacznie z korzeniem
- styl          - DRZEWO zbudowane moze byc z procesow lub watkow

Przyklad drzewa:  s=1, h=1

              xx
              xx

Przyklad drzewa:  s=2, h=3 

              xx
              xx
            /    \
          xx       xx
          xx       xx
         /  \     /  \
       xx    xx xx    xx
       xx    xx xx    xx


DRZEWO moze realizowac specjalnie zaprojektowane dla niego rozproszone zadania.

Zadania realizowane sa w nastepujacy sposob:

Wezel w DRZEWIE otrzymuje porcje danych do przetworzenia od swojego ojca.
Jesli wezel jest lisciem, to przetwarza dane i zwraca wynik ojcu.
Jesli wezel nie jest lisciem, to dzieli dane na mniejsze porcje i
wysyla je do swoich synow. Nastepnie czeka az synowie zwroca wyniki. 
Po otrzymaniu wynikow laczy je w calosc i wysyla swojemu ojcu.

Zadanie zaliczeniowe sklada sie z trzech etapow:

***** ETAP PIERWSZY

Trzeba wymyslic rozproszone zadanie, ktore bedzie realizowane przez DRZEWO.
Trzeba napisac biblioteke implementujaca to zadanie.
Biblioteka powinna byc zgodna z plikiem naglowkowym tree_proc.h
Biblioteka powinna udostepniac trzy funkcje:
- wykonywane w wezlach DRZEWA nie bedacych liscmi:
    tree_split - dzieli porcje danych na mniejsze czesci
    tree_merge - laczy kilka wynikow w jeden wynik
- wykonywana w lisciach DRZEWA
    tree_process_buffer - przetwarza porcje danych

Stworzymy baze danych gotowych bibliotek, tak zeby wszyscy studenci mogli z 
nich korzystac testujac swoje programy.

Przyklad zadania rozproszonego 1:
Odwracanie lancucha znakow.
tree_process_buffer - zwraca lancuch znakow w odwrotnej kolejnosci 
                      tzn. dla MAREK zwraca KERAM
tree_split - dzieli lancuch znakow na rownej dlugosci czesci
tree_merge - laczy wyniki w odwrotnej kolejnosci
             tzn. dla RAM i KE zwraca KERAM

Przyklad zadania rozproszonego 2:
Sortowanie przez scalanie.
tree_process_buffer - zwraca dane posortowane dowolna metoda
tree_split - dzieli dane na czesci rownej dlugosci
tree_merge - scala posortowane porcje danych
             tzn. dla AGKO i ELMZ zwraca AEGKLMOZ

Uwaga.
Termin zakonczenia etapu pierwszego mija na zajeciach nr 13.
Przed przystapieniem do realizacji etapu pierwszego nalezy zglosic do osoby
prowadzacej laboratorium swoj pomysl na zadanie dla DRZEWA. Dopiero po
zaakceptowaniu pomyslu mozna przystapic do jego realizacji.

***** ETAP DRUGI

Trzeba napisac program KIEROWNIK, ktory bedzie potrafil:
- zbudowac DRZEWO o zadanych paramerach
- w petli:
  * przekazac DRZEWU porcje danych do przetworzenia
  * odebrac wyniki
- zniszczyc DRZEWO

Nalezy napisac KIEROWNIKA zarowno dla watkow jak i dla procesow.

Do tego trzeba zaimplementowac w postaci bibliotek trzy rozne mechanizmy 
komunikacji pomiedzy procesami wykorzystujac kolejki komunikatow, kolejki FIFO,
pamiec dzielona. Oczywiscie z takiej biblioteki bedzie korzystac tylko DRZEWO
zbudowane na procesach, a nie na watkach.

KIEROWNIK powinien miec mozliwosc mierzenia czasu potrzebnego do przetwarzania
danych.

Jesli DRZEWO jest oparte na procesach, to proces KIEROWNIKA nie moze nalezec 
do DRZEWA.

Jesli DRZEWO ma byc oparte na watkach, to musza sie one znajdowac w innym 
procesie, niz proces KIEROWNIKA.

Komunikacja pomiedzy KIEROWNIKIEM, a procesem zawierajacym korzen DRZEWA
moze byc zaimplementowana "na sztywno" za pomoca dowolnego mechanizmu. Tzn.
jest niezalezna od wyboru biblioteki implementujacej mechanizm komunikacji
pomiedzy procesami.

Na etapie kompilacji poprzez dolaczenie odpowiednich bibliotek dokonywany 
bedzie wybor jakie zadanie bedzie realizowane przez DRZEWO oraz jakie 
mechanizmy komunikacji beda wykorzystane.

***** ETAP TRZECI

Trzeba zaplanowac i przeprowadzic serie testow badajacych wydajnosc
programu biorac pod uwage:
- rozne parametry DRZEWA
- rozna wielkosc przetwarzanych danych
- rozne mechanizmy komunikacji
- rozroznienie watki/procesy

Uwaga.
Termin oddania etapu drugiego i trzeciego mija 10 czerwca.

Powodzenia.
======================================================
Marek Debowski (e-mail: debowski@mimuw.edu.pl)
Dionizy Borun  (e-mail: db153543@rainbow.mimuw.edu.pl)
======================================================