Programowanie współbieżne

W systemie działa serwer i pewna liczba procesów. Każdy proces jest albo ugodowy albo neutralny albo marudny. Typ procesu podaje się przy jego uruchomieniu w linii poleceń: proces u, proces n lub proces m

Proces w pętli nieskończonej:

wykonuje własne sprawy, czyli po prostu usypia na losowy czas --- od 1 do 10 sekund,
następnie wypisuje na standardowy strumień diagnostyczny komunikat "Proces %d, czekam na zasób.n", zgłasza się do serwera i czeka, aż serwer przydzieli mu zasoby,
otrzymuje od serwera informacje o typie przydzielonego zasobu,
korzysta z zasobu --- wypisuje na standardowy strumień diagnostyczny komunikat o typie otrzymanego zasobu: "Proces %d, otrzymalem zasób %d.n" i pracuje z zasobem, czyli usypia na losowy czas --- od 1 do 10 sekund
wypisuje na standardowy strumień diagnostyczny komunikat "Proces %d, skonczylemn" i oddaje zasób serwerowi.
Wszystkie komunikaty są w formacie stosowanym w fprintf i mają zawierać PID procesu. Poza tym procesy nie wypisują żadnych innych komunikatów.
Zarządzaniem procesami i zasobami zajmuje się serwer. Zarządza on zasobami dwóch typów: lepszym i gorszym. Jest on wywoływany z dwoma parametrami: N - oznaczającym liczbę dostępnych zasobów lepszych, M - oznaczającym liczbę dostępnych zasobów gorszych. Serwer komunikuje się z procesami za pomocą kolejki (lub kolejek) komunikatów. W pierwszej kolejności odbiera on komunikaty o zwrocie zasobów, które obsługuje sam. W następnej kolejności odbiera komunikaty z prośbą o przydzielenie zasobu. Po odbiorze takiego komunikatu serwer tworzy wątek odpowiedzialny za obsługę tego żądania i ponownie oczekuje na zlecenia od procesów.

Wątek odpowiedzialny za obsługę żądań działa w następujący sposób:

jeżeli żądanie pochodzi od procesu marudnego, wątek oczekuje aż będzie dostępny przynajmniej jeden egzemplarz zasobu lepszego, po czym wysyła do procesu komunikat z informacją o przydzieleniu mu zasobu i kończy się,
jeżeli żądanie pochodzi od procesu neutralnego, wątek oczekuje aż będzie dostępny przynajmniej jeden egzemplarz zasobu dowolnego typu (preferując jednak o ile to możliwe zasoby lepsze), po czym wysyła do procesu komunikat z informacją o typie przydzielonego zasobu i kończy się,
jeżeli żądanie pochodzi od procesu ugodowego, wątek oczekuje aż będzie dostępny przynajmniej jeden egzemplarz zasobu dowolnego typu (bez żadnych preferencji), po czym wysyła do procesu komunikat z informacją o typie przydzielonego zasobu i kończy się.
Zaimplementuj opisany powyżej schemat. Rozwiązanie powinno:

zawierać co najmniej dwa pliki wykonywalne: serwer oraz proces,
wykorzystywać do komunikacji między serwerem a procesami kolejki komunikatów IPC,
wykorzystywać do synchronizacji wątków muteksy i zmienne warunkowe,
dbać o to, aby przerwanie działania serwera za pomocą CTRl+C nie zostawiało po sobie żadnych niezwolnionych zasobów IPC,
zawierać prostą obsługę błędów - wystarczy, że proces wykryjący błąd zakończy się.
Wszystkie pliki źródłowe oraz Makefile należy spakować do jednego pliku i wysłać go jako załącznik na adres mengel@mimuw.edu.pl do dnia 14 czerwca 2010, godz. 23:59. Każdy rozpoczęty tydzień spóźnienia skutkuje ,,premią'' w wysokości -2pkt.

A oto rozwiązanie:

Continue reading “Programowanie współbieżne”

Systemy Rozproszone Zad 2

Szczerze mówiąc, nie pamiętam treści tego zadania.
Coś z przekazywaniem żetonu i MPI…

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;


//Taka funkcja do dzielenia.

int main(int argc, char *argv[])
{
	FILE *f;					//Plik konfiguracyjny
	char znak;					//znaki wczytywane z wejsica
    vector Wysylam; 		//Odbiorcy
    vector Odbieram;		//Wysylajacy do mnie
	vector Wypisanie;		//Do wypisania zetonow
    int MojeId;					//Moje id zwrocone przez MPI
	int wynik;					//Do czytania pliku
	int size;					//MPI
    char bufor[1024];			//Bufor
	string tmp="";				//Tymczasowa zmeinna do czytania liczb
	int tmp_1;					//Liczba do tokenów
	int tmp_2;					//Druga liczba do tokenów
    string Wiadomosc=""; 		//Przesyłana wiadomosc
    string WypiszMnie=""; 		//Ja.
	
	//Harce z MPI
    MPI_Status s;
    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &MojeId);
    MPI_Comm_size(MPI_COMM_WORLD, &size);
    int id_tag = 500; 


	MojeId+=1;
	
	//WypiszMnie
	std::stringstream ss;
	ss <='0')&&(znak0)&&(tmp.size()>0))
			{
		
				//Podział tokenu.
				tmp_2=atoi(tmp.c_str());
				tmp="";
								
				if(tmp_1==MojeId)
				{
					//Dodajemy do listy wysylam
					Wysylam.push_back(tmp_2);
				}
				else if(tmp_2==MojeId)
				{
					//Dodajemy do listy odbieram
					Odbieram.push_back(tmp_1);
				}
				
				tmp_2=0;
				
				if(znak=='n')
				{
					//zerujemy.
					tmp_1=0;
				}
			}
		}
		wynik = fscanf(f,"%c", &znak);
	}
	fclose(f);
	
	//No dobrze. Wczytane.

	//Nasluchujemy.
        for(unsigned int i=0; i0)
		{
			//Przeysłamy dalej.
			char *Komunikacik=new char[Wiadomosc.length()+1];
		    strcpy(Komunikacik,Wiadomosc.c_str());
		
			for(unsigned int i=0; i<Wysylam.size(); i++)
			{
				MPI_Send(Komunikacik, Wiadomosc.length()+1, MPI_CHAR, Wysylam[i] - 1, id_tag, MPI_COMM_WORLD);
			}    
    	}
	    else
        {
			//A teraz wypiszemy:
			tmp="";
			tmp_1=0;
			
			//Dzielimy na tokeny:
			for(unsigned int i=0;i='0')&&(Wiadomosc[i]0)
					{
						tmp_1=atoi(tmp.c_str());
						Wypisanie.push_back(tmp_1);
						tmp="";
						tmp_1=0;
					}
				}
			}
			
			//Sortujemy:
			sort (Wypisanie.begin(), Wypisanie.end());

			//Wypisujemy:
			cout << WypiszMnie << ": {";
			tmp_1=0;
			for(unsigned int i=0;i<Wypisanie.size();i++)
			{
				if(Wypisanie[i]!=tmp_1)//Powtórzenia
				{
					cout << (Wypisanie[i]) <<" ";
					tmp_1=Wypisanie[i];
				}
			}
			cout<<"}"<<endl;

		}
    MPI_Finalize(); 
    return 0;
}

Gra Rycerze

Wraz z Pawłem Malinowskim i Rafałem Todorskim napisaliśmy super-extra grę rycerze!

Oczywiście, pomysł jest zadaniem zaliczeniowym:

I. Wstęp.
Za siedmioma górami, za siedmioma lasami starożytne królestwo nawiedził wielki i potężny Kamienny Smok. Wiele szkód uczynił: podpalał lasy i chłopskie chaty, porywał owce i dzieci (powiadano, że trafiały potem na jego stół). Wielu śmiałków próbowało już zgładzić potwora, żadnemu jednak nie udało się dotąd dotrzeć do jego legowiska, gdyż droga doń wiodła przez Labirynt. Niezwyczajny był to Labirynt – pełno w nim bezdennych przepaści, dziwnych, wybuchających miejsc i magii. Próbowano już wyburzać mury – ale po pewnym czasie odrastały jak przebiśniegi; zamurowywano przepaście, ale po pewnym czasie cegły rozsypywały się w proch. Aż wreszcie przybyła drużyna słynnych pięciu bohaterów pod twoim dowództwem aby zmierzyć się z Niebezpieczeństwem. Dla okolicznych mieszkańców po raz pierwszy zaświecił promień nadziei.

Continue reading “Gra Rycerze”

Czy można robić poważne badania przez internet?

Jak wszyscy może i wiemy, albo może i nie wiemy, badania psychologiczne to poważna sprawa.
Wiele czynników może wpływać na zakłócanie naszych zmiennych badawczych i staramy się je eliminować.
Ciężko pracujemy, by warunki były takie same we wszystkich grupach badawczych, by wszystko było przeprowadzone profesjonalnie.

Oprócz warunków badania jednak, istotną sprawą jest dobór osób do badania. Ważne, by przekrój próby odzwierciedlał przekrój populacji, by wyniki naszego badania dało się przełożyć na całą populację.

W troszkę innym temacie: fajnie by było robić badania przez internet

Czemu?

  • TANIEJ
  • Szybciej
  • Nie trzeba ręcznie przepisywać wyników do komputera
  • TANIEJ
  • Szybciej 🙂

A jednak mimo takich wspaniałych zalet, takich badań się nie przeprowadza. Ba!, mówi się że nie wolno tego robić!

Czemu?

  • Specyficzna grupa osób badanych
  • Specyficzne warunki badania – każdy ma inne warunki w domu, nie możemy ujednolicić

A więc

A więc wpadłem na pomysł, że warto by było raz na zawsze odpowiedzieć, na to frapujące pytanie, Czy można przeprowadzać badania psychologiczne przez internet?
Jak zamierzam to zrobić?

  1. Zamierzam wybrać kilka klasycznych badań, których wyniki są znane
  2. Zamierzam znaleźć sposób na przeprowadzenie ich w internecie
  3. Zamierzam przeprowadzić te badania
  4. Zamierzam porównać wyniki z przeprowadzonymi wcześniej w realu odpowiednikami
  5. Jeśli wyniki będą takie same, to MAMY ODPOWIEDŹ!

Poniższą prezentację przygotowałem w ramach jakiegośtam przedmiotu by wyjaśnić o co chodzi w tym pomyśle:

Lab Wpółbieżny i obiektowy zadanie 2

Drugie zadanie z labu współbieżnego i obiektowego wygląda tak:


Napisz program kalkulator, który pozwala wczytywać wyrażenia arytmetyczne ze zmiennymi i wyliczać ich wartości. Wyrażenia mogą być dowolnie rozbudowane, choć składają się tylko z czterech podstawowych działań arytmetycznych. Zmienne i wyrażenia są typu całkowitego. Nazwy zmiennych składają się tylko z liter. Dane użytkownik podaje ze standardowego wejścia. Wyrażenia postaci % oznaczają odwołanie do wyrażenia wcześniej zdefiniowanego (jeśli numer jest = bieżącemu numerowi takie wyrażenie jest błędne, należy wypisać użytkownikowi komunikat o błędzie,
tak samo jak w przypadku dzielenia przez 0).

Przykład konwersacji z programem (liczby na początku wierszy i znak ">" wyświetla sam program, tekst pogrubiony pochodzi od użytkownika):

1>x=9
2>x = -3
3>y=4
4>x+y*2/3
x+y*2/3 = -1
5>zz+zz
zz+zz = NIEOZNACZONE
6>%5+%5
(zz+zz)+(zz+zz) = NIEOZNACZONE
7>%6/%6
((zz+zz)+(zz+zz))/((zz+zz)+(zz+zz)) = NIEOZNACZONE
8>zz=1
9>%7
((zz+zz)+(zz+zz))/((zz+zz)+(zz+zz)) = 1
10>x=0
11>%4
x+y*2/3 = 2
12>1/x
1/x = BŁĄD
13>zz=5
14>zz
zz=5
15>%8
zz=5
16>
Koniec działania programu.

Jakich wzorców projektowych użyjesz w swoim rozwiązaniu?

A oto rozwiązanie:
Rany! Ale to zadanie było męczące!
Kalkulator

Struktury Danych

Ze struktur danych dostaliśmy wyobraźcie sobie do napisania program! Kto by pomyślał?

Oto treść:

Motel
Dost˛epna pami˛e´ c: 64MB.
Profesor Makary wybiera si˛e na zimowy urlop na narty. Poniewa˙ z droga z domu profesora do górskiego kurortu jest daleka,
profesor liczy si˛e z konieczno´ sci ˛a podzielenia jej na dwa dzienne etapy, z noclegiem w przydro˙ znym motelu. Podró˙ ze go m˛ecz ˛a,
wi˛ec tras˛e i miejsce na nocleg chce wybra´ c tak, ˙ zeby oba fragmenty drogi nie były zbyt długie. Dokładniej, chciałby, aby dłu˙ zszy
z dwóch dziennych etapów był mo˙ zliwie najkrótszy.
Pomó˙ z profesorowi zaplanowa´ c tras˛e dojazdu, pisz ˛ac program, który obliczy najmniejsz ˛a mo˙ zliw ˛a długo´ s´ c dłu˙ zszego etapu.
UWAGA: Mo˙ ze si˛e zdarzy´ c, ˙ ze w optymalnym rozwi ˛azaniu który´ s z etapów ma długo´ s´ c 0 (czyli w rzeczywisto´ sci cała trasa
zostanie przebyta w jednym etapie).
Wej´ scie
W pierwszym wierszu znajduj ˛a si˛e dwie liczby całkowite n i m (2 ? n ? 50000, 1 ? m ? 1000000). Pierwsza z nich oznacza
liczb˛e punktów stanowi ˛acych potencjalne miejsca postoju, ponumerowanych od 0 do n?1 (punkt numer 0 to dom profesora,
punkt n?1 to kurort, a pozostałe to motele). Druga to liczba odcinków dróg ł ˛acz ˛acych punkty. Ka˙ zdy z kolejnych m wierszy
zawiera trzy liczby całkowite a, b, c, gdzie 0?a,b<n, a 6=b, 0?c?10000. Liczby a i b oznaczaj ˛a punkty na drogach, za´ s c to
długo´ s´ c odcinka drogi prowadz ˛acego bezpo´ srednio od a do b. (UWAGA: długo´ sci odcinków dróg od a do b i od b do a nie musz ˛a
by´ c równe; w szczególno´ sci który´ s z nich mo˙ ze wcale nie istnie´ c). Liczby w ka˙ zdym wierszu s ˛a pooddzielane pojedynczymi
spacjami.
Wyj´ scie
W jedynym wierszu standardowego wyj´ scia nale˙ zy wypisa´ c najmniejsz ˛a mo˙ zliw ˛a długo´ s´ c dłu˙ zszego z dwóch etapów drogi z
domu profesora do kurortu.
Przykład
Dla danych wej´ sciowych:
4 5
0 1 1
0 2 4
1 2 2
1 3 4
2 3 3
poprawnym wynikiem jest:
3
Wyja´ snienie do przykładu. Optymalna trasa to: 0?1?2 (I etap); 2?3 (II etap)

A oto rozwiązanie:
Jakoś działa, z większy naciskiem na JAKOŚ niż na DZIAŁA
Zadanie

Lab HTML i JAVA zadanie 3

Trzecie zadanie z nowego przedmiotu, Laboratorium HTML i Java brzmiało następująco:

Napisz w Javie program do analizy utworów literackich mistrzów pióra.

Program ma wczytać ze standardowego wejścia plik tekstowy (w zamyśle utwór jednego z wieszczów, na przykład pobrany z internetu), policzyć częstości występowania w nim poszczególnych słów i wypisać na standardowe wyjście n najczęściej występujących wyrazów wraz z liczbą wystąpień każdego z nich. Liczbę n należy pobrać z wiersza poleceń. Program wypisując słowo powinien podać jego formę (chodzi o użycie wielkich i małych liter, a nie o formę gramatyczną) najczęściej występującą w tekście.

Ponadto w kodzie źródłowym programu, w pliku z główną klasą należy zamieścić komentarz podający dla n=8 wynik działania programu dla tekstu "Pana Tadeusza" (tekst ten jest zamieszczony w Moodle'u).

Uwagi:

    * Każde słowo należy wypisać w osobnym wierszu.
    * Po każdym wypisanym słowie należy po spacji podać liczbę jego wystąpień.
    * Słowa należy wypisać wg malejącej kolejności wystąpień w tekście (czyli jako pierwsze słowo należy podać to, które występuje najczęściej).
    * Jeśli kilka słów ma tę samą częstość wystąpień, to ich wzajemna kolejność wypisywania jest obojętna.
    * Jeśli jakiś utwór zawierałby mniej niż n różnych słów, to należy wypisać tyle słów, ile w utworze znaleziono.
    * Przy liczeniu liczb wystąpień słów należy utożsamiać małe i wielkie litery (tzn. w tekście "Ale, ale, ale!" uznajemy, że słowo "ale" wystąpiło 3 razy).
    * Przy wypisywaniu słów należy podać najczęściej występującą w tekście ich formę (tzn. dla tekstu "Ale, ale, ale!" należy wypisać postać "ale". Jeśli kilka postaci słowa występujących najczęściej ma jednakową liczbę wystąpień, można wybrać dowolną z nich (tzn. dla tekstu "Ale, ale!" można wypisać albo "Ale" albo "ale").
    * Należy uwzględniać polskie litery (tzn. w napisie "Liście" jest jedno słowo składające się z sześciu znaków).

Wskazówki:

    * Należy skorzystać z kolekcji.
    * Należy używać kolekcji uogólnionych (generic), a nie surowych (raw).
    * Do odczytywanie słów wygodnie użyć klasy Scanner. Do pobierania samych słów (tzn. bez kropek, przecinków itp.) z polskimi literami można użyć operacji
         skaner.useDelimiter("[^a-zA-ZąćęłńóśźżĄĆĘŁŃÓŚŹŻ]+");

A oto rozwiązanie:
Zadanie 3

Lab obiektowy i współbieżny zadanie 1

Pierwsze zadanie z fascynującego przedmiotu “Laboratorium Programowania Obiektowego i współbieżnego brzmi tak:”

Napisz w Javie hierarchię klas opisujących pracowników pewnej firmy komputerowej. Wyraź w tej hierarchii następujące fakty:

    *

      wszyscy pracownicy są ludźmi,
    *

      każdy kierownik projektu, projektant, analityk, tester, programista, a nawet sam prezes jest pracownikiem,
    *

      każdy kierownik projektu oraz prezes jest kierownikiem.


Tak zaprojektuj klasy by:

    *

      każdy człowiek znał swoje imię i nazwisko,
    *

      każdy pracownik znał swoje stanowisko (tekst) i swego szefa (oczywiście prezes nie ma szefa, szefem kierownika projektu jest prezes, szefami pozostałych pracowników są kierownicy projektów),
    *

      każdy pracownik, prócz prezesa, brał udział w dokładnie jednym projekcie, i oczywiście znał ten projekt,
    *

      każdy kierownik projektu znał członków swojego projektu,
    *

      każdy projektant znał swoją dziedzinę,
    *

      prezes był tylko jeden.


Stwórz też klasy opisujące:

    *

      projekt (zna swoją nazwę),
    *

      dziedzinę (wyznaczającą zakres kompetencji projektanta), dziedzina zna swój słowny opis.

Każdy z ludzi musi umieć podać swój opis tekstowy (komunikat toString). Opis ma zawierać wszystkie informacje, które zna dany człowiek (np. nazwę projektu, czy pełny opis szefa). Napisz fragment programu w Javie, który utworzy kilka (ok. 10) obiektów reprezentujących ludzi zatrudnionych w przykładowej firmie na różnych stanowiskach, umieści ich w kolekcji, a następnie wypisze opis każdego z nich. Zadbaj o to, by tworzenie nowych obiektów było jak najprostsze. Całość zaprojektuj w postaci pakietu i zapisz jako jeden plik jar (tu mogą się przydać informacje z przedmiotu HTML i Java).


Wskazówki:

    *

      przy implementacji prezesa posłuż się statyczną metodą produkującą, w celu zrealizowania wzorca Singleton,
    *

      rozwiązanie ma obrazować statyczny stan firmy, nie interesują nas zmiany (dynamiczne aspekty stanu firmy, np. to że ktoś awansuje),
    *

      zadanie jest proste.



A oto rozwiązanie:
Zadanie 1

Lab HTMLa i Javy, zadanie 2

Drugie zadanie z nowego przedmiotu, Laboratorium HTML i Java brzmiało następująco:

  Napisz klasę implementującą zbiór liczb całkowitych. Przy tworzeniu obiektów tej klasy, użytkownik podaje z jakiego zakresu liczb będą elementy tego zbioru (dla uproszczenia zakładamy, że to przedział o dolnej granicy 0) oraz ile wynosi maksymalna liczba elementów w zbiorze. Zbiór powinien mieć typowe operacje:

    * dodaj element,
    * usuń element,
    * podaj rozmiar,
    * sprawdź czy zadana liczba należy do zbioru,
    * podaj napis będący tekstową reprezentacją zbioru (toString).

W swojej implementacji zbioru:

    * użyj tablic,
    * sygnalizuj zgłoszeniem wyjątku przekroczenie maksymalnej liczności zbioru,
    * użyj statycznej metody produkującej, by na podstawie parametrów dostarczyć właściwą implementację zbioru (wektor charakterystyczny albo posortowana tablica).

A oto rozwiązanie:
Lab HTML i Java zadanie 2