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