Semestrální práce z předmětu Operační systémy

Autor: Jan Skalický (skalij2)
cvičení X36OSY, středa 11:00
datum poslední aktualizace: 25.04.2006, 04:20

Prohlášení o autorství:
Zde předkládanou práci jsem vytvořil samostatně s využitím informačních zdrojů uvedených v závěru práce

Transformace matice

1. Zadání

   Mějme čtvercovou matici nxn celých čísel. Úkolem je prohodit prvky pod hlavni diagonálou s prvky nad hlavní diagonálou.

             Vstupní matice 4x4:
   
                        1  2  3  4 
                        5  6  7  8
                        9 10 11 12
                       13 14 15 16 
   
             Matice 4x4 po transformaci:
    
                        1  5  9 13 
                        2  6 10 14
                        3  7 11 15
                        4  8 12 16 
       

   Transformaci bude provádět n(n-1) vláken/procesů. Jedna polovina n(n-1)/2 vláken/procesů může číst data nad hlavní diagonálou a zapisovat data pod hlavní diagonálu. Druhá polovina vláken/procesů může číst data pod hlavní diagonálou a zapisovat data nad hlavní diagonálu.
   
   Výstup: vstupní a rotovaná matice.
   
   

2. Řešení problému užitím vláken

   1. Analýza

      Každou buňku neležící na hlavní diagonále obsluhuje jedno vlákno. Jeho úkolem je přečíst původní hodnotu buňky a ve vhodný okamžik zapsat tuto hodnotu do buňky jejíž index se vypočítá z požadované operace nad maticí - zde se jedná o transpozici, takže vlákno patřící k buňce s indexem [x,y] bude zapisovat na pozici [y,x]. Nejdůležitější část je zde určení vhodného okamžiku, od kterého je vláknům povolen zápis do buněk, musí to být totiž až poté, co všechna vlákna přečtou obsah své buňky, jinak by se mohlo stát, že rychlejší vlákno provede transpozici své buňky dřív než vlákno transponované buňky přečte její hodnotu a tím se ztratí informace o původní matici, protože obsah přepisované hodnoty není nikde zaznamenán. Ideálním synchronizačním mechanismem tohoto problému je bariéra. Jedná se o prostředek, který na požádání pozastaví činnost linie výpočtu (zde vláken) dokud se k bariéře nedostanou všechny její linie. Protože bariéry nemají na UNIXu nativní API, bude zde implementována nepřímo užitím entit podmínková proměnná a mutex.
   
   
   

   2. Syntéza

      Program alokuje pole vláken, které má 2 rozměry o velikosti rozměrů matice (protože operace transpozice nepracuje s prvky na hlavní diagonále, nebudou tyto prvky pole inicializovány; toto indexování je zvoleno pro lepší čitelnost kódu). Procedura vlákna se stará o přečtení hodnoty svojí a zápis do transponované buňky. Mezi těmito akcemi pracujícími nad globálním polem matice čeká vlákno na bariéře, což je realizováno čekáním na podmínkovou proměnnou. Testovaná podmínka je zde "výška" zbývající bariéry (kolik vláken se k ní ještě nedostalo), která je na začátku nastavená na počet všech vytvářených vláken (velikost matice*(velikost matice-1)). Aktualizace výšky bariéry je chráněna mutexem. V případě že je výška bariéry po aktualizaci vláknem stále nenulová, zablokuje se toto čekáním na příslušnou podmínkovou proměnnou. V opačném případě to znamená, že bariéra padla, vlákno už nemusí na zápis čekat (všichni mají svoji hodnotu přečtenou) ¨ a navíc zavolá broadcast příslušné podmínkové proměnné, aby probudil všechna čekající vlákna. Následně všechna vlákna zapíšou jejich hodnoty na transponované pozice. Po této operaci vlákna končí a globální matice je transformována. Main je synchronizován s vytvářenými vlákny cyklickým joinem na každé z nich po jejich vytvoření. Index buňky, kterou má vlákno transponovat je posílán mainem v posledním parametru funkce pthread_create (jako int přetypovaný na void *).
   
   
   

   3. Ukázkový výstup programu (velikost matice 2x2)

          main: generating random matrix 2x2:
          0       69
          50      59
          main: initializing barrier mutex
          main: initializing barrier condition
          main: 2 bricks in barrier left
          main: creating thread for cell [0,1]
          thread [0,1] created and reads value 69 from source cell
          main: creating thread for cell [1,0]
          thread [0,1] breaks one brick in barrier - 1 left
          thread [1,0] created and reads value 50 from source cell
          thread [0,1] reaches barrier... waiting for others
          thread [1,0] breaks one brick in barrier - 0 left
          thread [1,0] breaks last brick in barrier... broadcasting condition
          main: joining thread for cell [0,1]
          thread [1,0] passes barrier and writes value 50 to target cell
          thread [0,1] passes barrier and writes value 69 to target cell
          main: thread for cell [0,1] joined
          main: joining thread for cell [1,0]
          main: thread for cell [1,0] joined
          main: output matrix:
          0       50
          69      59
          main: destroying barrier mutex
          main: destroying barrier condition
                  

   4. Zdrojové kódy

      transmat.c
      Makefile
   
   

3. Řešení problému užitím procesů

   1. Analýza & Syntéza

      Analytická část problému je totožná s variantou užití POSIXových vláken. Syntéza se liší v implementačních detailech procesů a v tom, že použitými funkcemi pro realizaci meziprocesové komunikace jsou zde systémové funkce IPC subsystému v rámci OS Systém V (Solaris, HP-UX, Linux). Hlavní proces alokuje pole procesů (PIDů), bariéra je realizována pomocí pole čítačů s jedním prvkem, které je na začárku inicializováno rodičovským procesem na hodnotu rovnou počtu synovských procesů realizujících vlastní transformace buněk. V rámci činnosti každého z nich dojde k dekrementaci tohoto semaforu (odečtení 1 - zde nikdy neblokuje) a následnému čekání na jeho dosažení nuly (wait-for zero - zde blokuje dokud neprovedou dekrementaci všechny procesy). Toto je implementace bariéry. Oproti vláknovému řešení zde navíc přibyde ještě sdílená paměť, ve které je zde uložen obraz transformované matice a do níž jednotlivé procesy zapisují své hodnoty po překročení bariéry. Ta je alokováná a připojena rodičovským procesem před cyklickým voláním fork() a tudíž je připojena i ke všem jeho synům (pokud neprovedou exec). Po ukončení činnosti všech synovských procesů, což rodič pozná cyklickým voláním wait() pro konkrétní PIDy, je v tomto kusu paměti výsledná transformovaná matice.
   
   
   

   2. Ukázkový výstup programu (velikost matice 2x2)

          main: allocating shared memory for matrix data
          main: attaching shared memory for matrix data
          main: generating random matrix 2x2:
          51      17
          30      53
          main: allocating barrier semaphore
          main: initializing barrier semaphore
          main: 2 bricks in barrier left
          main: invoking process for cell [0,1]
          main: invoking process for cell [1,0]
          process [0,1] created and reads value 17 from source cell
          process [1,0] created and reads value 30 from source cell
          process [1,0] breaks one brick in barrier - 1 left
          process [1,0] reaches barrier... waiting for others
          main: waiting for termination of process for cell [0,1]
          process [0,1] breaks one brick in barrier - 0 left
          process [1,0] passes barrier and writes value 30 to target cell
          process [0,1] breaks last brick in barrier... semaphore is cleardown
          process [0,1] passes barrier and writes value 17 to target cell
          main: process for cell [0,1] terminated
          main: waiting for termination of process for cell [1,0]
          main: process for cell [1,0] terminated
          main: output matrix:
          51      30
          17      53
          main: destroying barrier semaphore
          main: deallocating shared memory
                  

   3. Zdrojové kódy

      transmat.c
      Makefile
   
   

4. Závěr

   Činnost programu odpovídá zadání.

© 2006 Jan Skalicky
cz (dot) skalda (at) seznam (dot) cz