Operaˇcní systémy 2: Zápoˇctové úkoly
18. listopad 2010
1
Paralelní Mergesort
Implementujte paralelní verzi algoritmu Merge sort, který bude rˇ adit celá cˇ ísla uložená v textovém souboru. Program bude mít tˇri argumenty (v tomto poˇradí): vstupní soubor, výstupní soubor a poˇcet vláken použitých k výpoˇctu. Vstupní i výstupní soubor jsou bˇežné textové soubory, kde na každém rˇ ádku je jedno cˇ íslo. Pˇri implementaci použijte vlákna a omezte použití synchronizaˇcních primitiv na nutné minimum. K naˇctení a uložení dat z/do souboru použijte mapovaní souboru do pamˇeti. Ovˇerˇ te na víceprocesorovém/vícejádrovém poˇcítaˇci, že algoritmus škáluje—pˇri použití více vláken bˇeží rychleji. Pˇríklad použití ./pmergesort input-1.txt output-1.txt 5 Hodnocení Za tuto úlohu je možné získat 9 bodu. ˚
2
Map-Reduce Framework
2.1
Úvod do problematiky
Pˇri zpracování opravdu rozsáhlých dat (tj. dat se kterými bˇežnˇe pracuje Google, Yahoo! cˇ i Facebook) se používá reprezentace hodnot v podobˇe dvojice klíˇc-hodnota (dále jen hk, vi) a data jsou zpracovávána ve dvou fázích—map a reduce odtud název MapReduce Framework.1 V prvním kroce jsou vstupní data rozdˇelena na menší bloky a pˇrípadnˇe pˇrevedena do tvaru hk, vi. V následujícím kroce se provede operace map a na jednotlivá naˇctená 1 http://labs.google.com/papers/mapreduce.html
1
data se aplikuje funkce f , která pro každou dvojici hk, vi vrací multimnožinu dvojic hk, vi, i.e., f (hk, vi) = {hk1 , v1 i, . . . , hk n , vn i} V dalším kroce se provede operace reduce a všechny hodnoty (dvojice hk, vi) jsou roztˇrídˇeny podle svého klˇce k a na dvojice mající stejný klíˇc k je aplikována agregaˇcní funkce g vracející hodnotu ve tvaru hk, vi, i.e,. g({hk, v1 i, hk, v2 i, . . . , hk, vn i}) = hk, vi Pˇríklad Uvažujme, že chceme spoˇcítat cˇ etnost znaku˚ ve slovech alice, barbara, carol. Nejdˇríve text rozdˇelíme na jednotlivá slova a na nˇe pak aplikujeme funkci f , která pro každý znak ve slovˇe vrací dvojici ve tvaru hznak, 1i. Tedy: f ( alice) = {h a, 1i, hl, 1i, hi, 1i, hc, 1i, he, 1i}, f (barbara) = {hb, 1i, h a, 1i, hr, 1i, hb, 1i, h a, 1i, hr, 1i, h a, 1i}, f (carol ) = {hc, 1i, h a, 1i, hr, 1i, ho, 1i, hl, 1i}. V následujícím kroce aplikujeme na páry se stejným klíˇcem funkci pro redukci, která seˇcte jednotlivé hodnoty v. Tedy: g({h a, 1i, h a, 1i, h a, 1i, h a, 1i, h a, 1i}) = h a, 5i, g({hb, 1i, hb, 1i}) = hb, 2i, g({hc, 1i, hc, 1i}) = hc, 2i, g({he, 1i}) = he, 1i, g({hl, 1i, hl, 1i}) = hl, 2i, g({hi, 1i}) = hi, 1i, g({ho, 1i}) = ho, 1i, g({hr, 1i, hr, 1i, hr, 1i}) = hr, 3i. Z povahy algoritmu a pˇredpokladu, že funkce f a g nemají vedlejší efekt, lze vidˇet, že výpoˇcet lze snadno paralelizovat a distribuovat. V praxi pak pro výpoˇcet staˇcí dodat frameworku funkce f a g a ten se o výpoˇcet postará sám. V praxi se pak taky ukázalo, že je dobré rozdˇelit fázi reduce na dva kroky. V prvním kroce se provede operace combine, která nedˇelá nic jiného než, že aplikuje agregaˇcní funkci na dvojice vytvoˇrené jednou aplikací funkce map. Na hodnoty vzešlé z operace combine je následnˇe použita funkce reduce.
2.2
Zadání úkolu
S využitím procesu˚ a rour implementujte model Map-reduce frameworku. Program bude mít tˇri parametry: program reprezentující funkci map, program reprezentující funkci reduce a poˇcet instancí procesu map, které se mají vytvoˇrit. 2
Pˇríklad použití cat foo | map-reduce ./map.py ./reduce.py 5
map reduce
Map #1
Reduce #1 (combine)
File #1
Map #2
Reduce #2 (combine)
File #2
Map #3
Reduce #n (combine)
Reduce
stdin
Map/Reduce Framework
Program vytvoˇrí daný poˇcet procesu˚ map a ke každému procesu map vytvoˇrí proces reduce. Program pak bude cˇ íst textový soubor rˇ ádek po rˇ ádku ze standardního vstupu a pˇredávat jednotlivé rˇ ádky stˇrídavˇe jednotlivým procesum ˚ map. Ten data zpracuje a pˇredá je svému procesu reduce. Následnˇe budou data uložena do souboru. ˚ Potom, co jsou všechny vstupní data zpracována, jsou data v souborech pˇredána programu reduce a výsledek zapsán na standardní výstup procesu. Soubory na disku jsou následnˇe odstranˇeny. Tok dat (nikoliv závislost procesu) ˚ zobrazuje následující schéma.
stdout
File #n
Programy map a reduce mohou být libovolné programy, které naˇcítají data ze standardního vstupu a vypisují výsledek na standardní výstup. Pˇri testování mužete ˚ využít pˇriložené programy, které demonstrují poˇcítání slov. Jejich funkci si mužete ˚ ovˇerˇ it následovnˇe: cat foo.txt | ./map | ./reduce Hodnocení Za tuto úlohu je možné získat 11 bodu. ˚
3
Paralelní REPL
S použitím vláken implementujte program, který bude simulovat známou smyˇcku read-eval-print, kde fáze eval a print budou trvat nezanedbatelnou dobu. Program bude mít tˇri vlákna: – první vlákno bude ze standardního vstupu naˇcítat rˇetezce; poté, co se naˇcte jeden rˇetˇezec, je pˇredán druhému vláknu pˇres sdílenou globální promˇennou – druhé vlákno naˇcte hodnotu ze sdílene promˇenné, pˇrevede text na velká písmena, poˇcká jednu sekundu a pˇredá výsledek pˇres další globální promˇennou tˇretímu vláknu 3
– tˇretí vlákno naˇcte hodnotu vypoˇcítanou ve druhém vláknu; poˇcká dvˇe sekundy a výpíše ji na standardní výstup Program bude ukonˇcen potom, co bude ukonˇcen vstup. Všechna pˇredaná data musí být zpracována a žádná hodnota nesmí být „zahozena”. Pokud vlákno pˇredává hodnotu druhému, které dosud nezpracovalo svuj ˚ vstup, bude zablokováno pomocí condition variable (Linux) nebo SuspendThread (Windows). Místa, kde bude docházet k cˇ ekání, umístˇete tak, aby program bˇežel, co nejefektivnˇeji, tzn. pokud probíhá výstup muže ˚ souˇcasnˇe probíhat i výpoˇcet. Pˇri pˇrístupu ke sdíleným promˇenným si dejte pozor, aby k nim nepˇristupovala dvˇe vlákna souˇcasnˇe nežádoucím zpusobem. ˚ Hodnocení Za tuto úlohu je možné získat 9 bodu. ˚
4
Spoleˇcná sprcha
Typickou vlastností levného ubytování je sdílené sociální zaˇrízení. V tomto pˇríkladˇe máte za úkol pomocí procesu˚ a sdílené pamˇeti namodelovat chování osob v koupelnˇe, kde jsou spoleˇcné sprchy. Pˇredpokládejme, že: – koupelna má koneˇcné množství sprch – v každé sprše muže ˚ být jeden muž, nebo jedna žena – pokud je v nˇekteré sprše muž, nemuže ˚ do koupelny vstoupit žena (a opaˇcnˇe) – pokud jsou všechny sprchy obsazeny nebo nelze do koupelny vstoupit z pˇredchozího duvodu ˚ (je dotyˇcná osoba nucena poˇckat pˇred vstupem) Spoleˇcné sprchy reprezentujte pomocí bloku sdílené pamˇeti a jednotlivé osoby jako samostatné procesy, které budou synchronizovány pomocí semaforu˚ pro procesy.2 Vytvoˇrte program shower, který bude mít následující parametry: –
shower --create n vytvoˇrí koupelnu mající n sprch; pokud se ji nepodaˇrí vytvoˇrit, vypíše chybovou hlášku
–
shower --destroy zruší koupelnu, i.e., odstraní všechny zdroje v pamˇeti související s programem
–
shower --man n simuluje muže jdoucího do sprchy; parametr n udává, jak dlouho mu bude sprchování trvat (v sekundách)
2 Pokud budete tuto úlohu implementovat ve Windows, použijte pro sdílenou pamˇ et’ mapovaný soubor a místo procesu˚ vlákna a uživatelské rozhraní simulujte pomocí standardního vstupu.
4
–
shower --woman n simuluje ženu jdoucí do sprchy; parametr n udává, jak dlouho jí bude sprchování trvat (v sekundách)
–
shower --status zobrazí informace o koupelnˇe, tj. poˇcet sprch, kdo muže ˚ vstoupit do sprchy a obsazení jednotlivých sprch
Každý proces bude vypisovat informaci o svém stavu následovnˇe: – po vytvoˇrení proces oznamí, že jde do sprchy – když se mu podaˇrí získat místo ve sprše, oznámí, že vstoupil do sprchy – potom, co dokonˇcil sprchávání, oznamí, že vyšel ze sprchy Pˇríklad použití shower shower shower shower shower
--create 2 --man 10 & --man 12 & --woman 10 & --man 10 &
Výstup muže ˚ vypadat následovnˇe: Proces Proces Proces Proces Proces Proces Proces Proces Proces Proces Proces Proces
#10533 #10533 #10536 #10536 #10535 #10534 #10533 #10534 #10536 #10534 #10535 #10535
(muz) jde do sprchy. (muz) vstoupil do sprchy. (muz) jde do sprchy. (muz) vstoupil do sprchy. (zena) jde do sprchy. (muz) jde do sprchy. (muz) vysel ze sprchy. (muz) vstoupil do sprchy. (muz) vysel ze sprchy. (muz) vysel ze sprchy. (zena) vstoupil do sprchy. (zena) vysel ze sprchy.
Pˇríklad výstupu pro: shower --status Pocet sprch: 3 Do sprchy muze vstoupit: zena Sprcha #1: proces 10482 Sprcha #2: prazdna Sprcha #3: prazdna Hodnocení Za tuto úlohu je možné získat 9 bodu. ˚ 5
Poznámky k implementaci a odevzdávání – všechny úlohy je možné implementovat na platformnˇe Linux (preferovaná volba) i Windows, ale je pˇrípustné odevzdat rˇešení jen pro jednu z nich, tj. nelze napˇríklad odevzdat 1. úlohu ve verzi pro Linux i Windows – úlohy je možné odevzdat do konce zápoˇctového týdne (tzn. do 17. prosince 23:59 CET) a na pozdˇeji odevzdané úlohy nebude brán zˇretel; úlohy odevzdané pˇred zápoˇctovým týdnem bude v pˇrípadˇe potˇreby možné odevzdat opakovanˇe – jednotlivé rˇešení zásílejte jako samostatné soubory ve tvaru login-ˇcíslo pˇríkladu.c na email krajcap (at) inf.upol.cz – jednotlivé programy by mˇely být vhodnˇe okomentovány tak, aby bylo možné pochopit cˇ innost programu; dbejte na dobrý programátorský styl a konvence (vˇcetnˇe tˇech o formátování kódu)
6
