Examen voor AM

[...]

Ik vond het schandalig da we geen AM hadden om ons voor te bereiden op dit nog schandaliger examen. Daarom ga ik nu proberen het examen te reconstrueren voor het nageslacht.

Als iedereen wilt helpen met de gaten in mijn geheugen aan te vullen zou ik u allemaal dankbaar zijn. Dan zal ik da uiteindelijk alst af is op het AM vh vtk posten.

Deel 1: Gesloten boek (30min)
Leg de volgende 10 begrippen uit in 5 regels (per begrip):

• "Grid computing"
• "Failure Model"
• "Dependency Injection"
• "Logische klok" 
• "Poisson proces"
• "UDDI"
• "URL rewriting"
• "activation service"
• "klokresolutie"
• "unmarshalling"

Deel 2: Open boek, zelfde als informatici (1u45min)
Vraag 1 (60 minuten)

Ge wilt een stadsgids ontwerpen waar de mensen automatisch de informatie krijgen van gebouwen/evenementen die zich vlak bij hun positie bevinden. De positie kan via GPS of zo bepaald worden.
Per geregistreerde gebruiker hou je een lijst van trefwoorden bij van zaken die hij leuk vindt.
Verder heb je een aantal gebouwen van de stad, daar heb je foto, naam, locatie en een aantal trefwoorden van.
Tenslotte heb je ook een reeks evenementen die plaatsvinden, daar heb je periode, locatie, naam en opnieuw een aantal trefwoorden van.

a) Stel de databank personen op. Duidt duidelijk de sleutel(s) aan. Verder stel je alle databanken op die hier rechtstreeks aan gelinkt zijn.

b) Stel je bazen zijn vuile idioten en ze besluiten dat ze hier EJB's voor willen gebruiken. De kiekens. Swat, daar heb je nu eenmaal niks op te zeggen. Beschrijf alle beans die je zou maken.

c) Wat zijn de mogelijke implementatievormen (oid) rekening houdend met je beslissingen uit b)

d) Wat in geval van overbelasting? (dus hoe kan het ding gedistribueerd worden)





Vraag 2

Het is de bedoeling dat een bepaald proces op 2 servers zal draaien. Er zal dan loadbalancing gebeuren tussen deze servers (eventueel kan een derde server overwogen worden om de loadbalancing te redirecten). Verder moeten bij het opstarten van het systeem niet alle processen opgestart worden. Ze moeten opgestart worden op het moment dat ze nodig zijn Hier is mijn opgave niet volledig.

a) Er wordt getwijfeld tussen RMI en CORBA (helaas het staat vast dat je Java moet gebruiken). Bespreek voor beide 1) of ze aan de voorwaarden kunnen voldoen 2) Welke veranderingen er nodig zouden zijn in de code (in woorden beschrijven).

b) Welke zou je kiezen, RMI of CORBA (+ korte verklaring).



Deel 3: Open boek, alleen voor ons (1u45min)

Vraag 1

Gegeven de situatie die je in de bijgeleverde foto ziet. http://studwww.ugent.be/~jdhollan/ODS_AM_2007.png

a) Stel voor elk event (A tot W) zowel de logische klok als de vector klok op.

b) Bepaal voor 3 koppels van events ( P&C, Q&N, L&S ) de volgorde: ofwel P->C, ofwel C->P, ofwel C||P ofwel "?" (namelijk niet te bepalen).

Vraag 2

Er moet toegang tot een kritieke sectie bewaakt worden. Het systeem met een centrale server ziet er zeer aanlokkelijk uit wegens de eenvoud. Om het probleem van de schaalbaarheid een beetje tegemoet te komen wordt het systeem op 2 servers gemplementeerd. Iedere proces kan dus de toegang aan gelijk welk vd twee servers vragen. Natuurlijk mag er nog altijd maar 1 proces tegelijk in de kritieke sectie.

a) Teken drie zinvolle scenario's uit (Wa is de naam van het diagram nu weer?). Geef ze ook een zinvolle, duidelijke naam.

b) Welke boodschappen zijn er nodig. Probeer zoveel mogelijk dezelfde boodschappen als in de oorspronkelijke situatie (uit de cursus) te gebruiken. Vul eventueel aan met andere boodschappen. Geef duidelijk de zender/ontvanger van de boodschappen aan.

c) Leg voor elk vd boodschappen uit b uit wat er moet gebeuren als ze aankomen.

d) De tijd om 1 boodschap in 1 richting over het netwerk te sturen is delta. Hoelang duurt het voor een proces zijn aanvraag toegekend wordt als de kritieke sectie vrij is.

Vraag 3

Je hebt een server waar m threads ve programma op draaien. m is at-runtime in te stellen (met een maximum van m_MAX). Je mag dit geheel voorstellen als een M|M|m proces.
Er wordt gegeven dat
1/mu = 1/mu₀*( 1 + (m-1)^alpha/beta )
is.

a) Beschrijf gedetailleerd wat je zou doen om mu₀, alpha, beta en lambda te bepalen. Je hebt de broncode van het proces niet ter uwer beschikking.

b) Stel dat mu₀, alpha, beta en lambda gekend zijn. Bepaal nu de optimale waarde van m (ifv die gegeven parameters).

c) Beschrijf, ifv mu₀, alpha, beta, lambda en m_MAX wanneer je zou besluiten dat 1 computer niet voldoende is en dat je een tweede server nodig hebt.




Voila, zoals je ziet zijn er wel een paar gaten. Alle opmerkingen, verbeteringen,... zijn welkom. Ik zal dan mijn post editen om jullie verbeteringen er in te steken zodat we uiteindelijk een perfecte kopie vh examen hebben.


EDIT1: Link naar tekening toegevoegd n opmerkingen van Ben (tnx)
EDIT2: Laatste woordje van vraag 1 (tnx Quick)

[Ben]

Deel 1: UDDI, URL rewriting, activation service, klokresolutie (nog 1 te gaan)

Deel 2:
Vraag 1:
c) Wat zijn de mogelijke implementatievormen (oid) rekening houdend met je beslissingen uit b)
d) Wat in geval van overbelasting? (dus hoe kan het ding gedistribueerd worden)

Vraag 2:
Er was gewoon geen c) als ik mij niet vergis

[quick]

unmarshalling

[deMax]

Gaan we anders samen keer die vragen bekijken? Sommige dingen zijn mij echt onduidelijk..

Deel2 - Vraag 1
a)Ge moet enkel de databank van personen opstellen en die direct daaraan gelinkt. Volgens mij is da dan de Personen databank en de trefwoorden databank. Zou je dat moeten uitschrijven in Java? Of gewoon zo:
Gebruikers
-----------
ID naam trefwoorden (many to many)

Trefwoorden
-------------
String gebouw(many to many) gebruiker(many to many) evenement(many to many)

b) Volgens mij: Stateless session bean voor een Facade, statefull session bean voor de logic en toegang tot de databank. Waarbij ge eventueel toegang tot de databank nog kunt isoleren in een 3e bean (ook stateless).
c) Wa bedoelen ze nu me implementatie? Kzie het toch nie goe ze. En rekening houdend met b)... (en wa is oid?)
d) Ge kunt gebruik maken van een extra "facade" waar ge een cluster management platform op draait, je kan het ook op dezelfde facade doen.
Deel 2 -Vraag 2
a) kunt ge nie doen wegens onvolledigheid van de vraag
b) wtf? Buiten het feit dat CORBA programmeertaal onafhankelijk is kun je toch niet veel over zeggen?

Deel 3 - Vraag1
a) Da valt wel mee.
Eén klein vraagje ervoor: als je bv (onderstel Lambert-clock, geen vektor) van p1 op clock=1 iets naar p2 stuurt, het volgende event op p1 is dat dan op clock=2 of 3? Er staat nergens zo'n voorbeeldje, maar ik vermoed op clock=2 omdat je niet weet dat op p2 een event is toegekomen.
Ik ga niet alle tijden opschrijven maar finaal is het bij mij:
W=8
S=8
N=8
I=12
voor Lambertklokken en
W=(4,2,3,4)
S=(2,5,3,4)
N=(0,2,5,4)
I=(4,5,5,9)
voor vektorklokken
b) P->C; Q//N; L->S

Deel 3 - Vraag2
Snapt iemand de vraag? Weet iemand over wavoor diagrammen da gaat? Volgens mij moeten we dan gewoon 3 vd 4 algoritmen uitschrijven waarvan het eerste (met centrale server) niet gaat. Verandert er iets aan die algoritmen omdat we met 2 servers werken? Moeten we communicatie ertussen modelleren? (please say no)


Feedback is meeeeeeeer dan welkom!

Max

[joxy]

De oplossing van Deel3 Vraag 3 is in de les gegeven door FDT

Mijn nota's van tijdens die les staan op: http://users.ugent.be/~jdgraeve/OGS-Oef-Performance.pdf

nog wat meer uitleg:

3a:
* [tex]{\lambda}[/tex] bepalen: trafiek loggen en daaruit aantal aanvragen bepalen.
* [tex]\mu_0[/tex]: proces opstarten met 1 thread en meting uitvoeren van de verwerkingstijd
* [tex]{\alpha}[/tex] ,[tex]{\beta}[/tex]: meting uitvoeren met verschillend aantal threads en beide bepalen via curve fitting.

3b:
Toepassin formule [tex]\rho = {\lambda \over m * \mu} [/tex] rho geeft de systeembezetting weer.
rho mag niet te groot zijn (bv max 0,8)
optimaal punt voor m is het dalpunt van de curve met m*[vergelijking van 1/ in de opgave] zie ook grafiekje in mijn nota's

3c:
Als rho altijd > 0,8 kan je de workload niet op n server draaien en zijn er meerdere machines nodig.

broker die over n machines load verdeeld:

=> \lambda_{tot}= n * \lambda_{per server}

willekeurige verdeling v/e poisson process geeft immers terug een poisson process

Zie ook mijn nota's van tijdens de les (voor de grafiekjes evt)

Voor deze vraag is het echt zeer handig om de cursus "wachtlijntheorie" gehad te hebben, die gaat over niets anders.  Maar die is voor 1e masters CW in het tweede semester.

Suc6

Jos

[KeKau]

vraag 2 deel 2

hoe kunt ge loadbalancing en RMI/CORBA met elkaar in verband brengen?
ik vind niets terug in de cursus daarover

[Tim]

Deel3
3a:
* [tex]{\lambda}[/tex] bepalen: trafiek loggen en daaruit aantal aanvragen bepalen.
* [tex]\mu_0[/tex]: proces opstarten met 1 thread en meting uitvoeren van de verwerkingstijd
* [tex]{\alpha}[/tex] ,[tex]{\beta}[/tex]: meting uitvoeren met verschillend aantal threads en beide bepalen via curve fitting.

Voor het bepalen van [tex]{\alpha}[/tex] en [tex]{\beta}[/tex]:
Het lijkt me eenvoudiger om eerst een proces op te starten met 2 threads. Hierdoor verdwijnt [tex]{\alpha}[/tex] uit de formule en dan kan je zo [tex]{\beta}[/tex] bepalen.
Daarna nog es een proces opstarten met meer dan 2 threads en daar kun je dan [tex]{\alpha}[/tex] bepalen.

't Komt mss op hetzelfde neer, maar toch ietsje eenvoudiger lijkt me.

[Kristof]

hey allemaal,

Wat handig kan zijn voor het eerste gesloten boek deel van het examen is een lijst met termen met een korte uitleg erbij...
Ik heb er al eentje en die kan mag je altijd gebruiken:

office 97-2003
office 2007

Als jullie ergens fouten of onvolledigheden zien mogen jullie mij die altijd laten weten...

grtz,
Kristof

[Tim]

Deel 3 - Vraag2
Snapt iemand de vraag? Weet iemand over wavoor diagrammen da gaat? Volgens mij moeten we dan gewoon 3 vd 4 algoritmen uitschrijven waarvan het eerste (met centrale server) niet gaat. Verandert er iets aan die algoritmen omdat we met 2 servers werken? Moeten we communicatie ertussen modelleren? (please say no)

Volgens mij moete de client laten werken via centrale server, maar moete zorgen voor een oplossong dat de servers overeen komen.
Oplossingen zijn dan:
-een super centrale server, waar dat de tussenliggende servers het aan moeten vragen.
-de servers geven een token door,
-zuk een argawalala dink en maekewa komen opt zelfde neer aangezien er maar 2 concurrenten zijn.
dien die et wil moet et gewoon vragen aan den anderen dus.

b) en c) zie cursus

d)
-Supercentrale: 4 delta
-Token: hangt af van wie het token heeft: 2 à 3 delta (+ indien hij het token niet heeft de wachttijd tot wnn die hij krijgt, maar das normaal nie lang aangezien den CS vrij is)
-Agrawala: 4 delta

Dit is mijn idee over die vraag.
a) Met die 3 zinvolle scenario's wordt er volgens mij niet bedoelt 'soorten algoritmes' of zo. Gewoon scenariootjes à la 2 processen vragen tegelijkertijd de toegang aan.
Dit lijken me geen slechte keuzes:

• 1 proces vraagt toegang aan terwijl die al aan een ander verleend is
• 2 processen vragen ongeveer tegelijkertijd toegang aan, aan dezelfde server
• 2 processen vragen ongeveer tegelijkertijd toegang aan, elk aan andere server

Dit zijn maar 3 vbtjes, 'k zou er nog kunnen vinden die 'zinvol' zijn (in mijn ogen toch ).

b) Ook hier is het me niet helemaal duidelijk wat er gegeven moet worden. Vooral dan, weten we via de vraagstelling hoe we het moeten implementeren (en dan vind ik da dus niet terug...) of moeten we zelf beetje redeneren en tot een geschikte implementatie komen?!
(Al de processen blijven gewoon hetzelfde doen als bij 1 centrale server, behalve dat ze kunnen kiezen van server.)
Dus es kijken naar onze mogelijkheden:

• Superserver:
  Ik denk niet dat we een 3e server als superserver mogen gebruiken (letterlijk in de opgave: 'het systeem op 2 servers geïmplementeerd', dus geen 3 ).
  Maar we kunnen wel een van de 2 als superserver kiezen. Lijkt me een redelijk eenvoudige implementatie. Voor de superserver lijkt de andere server gewoon op een proces in dit geval. Lijkt me wel minder goed ge-'loadbalanced'. Alles dat naar slave gaat moet uiteindelijk ook nr de master. Tenzij dat slave niet vrijgeeft als ie nog aanvragen in z'n queue heeft. Maar in dat geval heb je het gevaar dat de master geen kans meer krijgt... Lijkt me uiteindelijk dus niet zo'n goed idee. Maar voor de volledigheid:
  Boodschappen:
  • Request CS (vanuit proces of slave-server)
  • Release CS (vanuit proces of slave-server)
  • Grant CS (vanuit servers)
• Ring-based algorithm:
  Een van de 2 servers zal altijd de token hebben. Wat ik me bij dit algoritme afvraag: als p_i het token heeft, maar niet nodig heeft, geeft ie hem dan door? Staat niet in de slides... 'k Zal er maar van uitgaan van wel want anders kan je in een probleemgeval komen (alle aanvragen naar de andere server (kan gebeuren als communicatielijn naar server met token verbroken is)).
  Boodschappen:
  • Request CS (vanuit proces)
  • Release CS (vanuit proces)
  • Grant CS (vanuit servers)
  • Pass token (servers onderling)
• Ricart-Agrawala algorithm:
  Ook redelijk eenvoudig, fair, safe,...
  Boodschappen:
  
  • Request CS (vanuit proces)
  • Release CS (vanuit proces)
  • Grant CS (vanuit servers)
  • Message <T> (servers onderling, p-id moet niet meegestuurd worden met dat er toch maar 2 zijn)
  • Reply (servers onderling)
• Maekawa Voting:
  Buiten dat er hier geen klok gebruikt wordt (en dus mss niet fair is), is het hetzelfde als R-A algorithm doordat er maar 2 servers zijn. Enige voordeel van Maekawa Voting tov R-A algorithm was maar dat er minder berichten zouden moeten rondgestuurd worden. Nu, met maar 2 deelnemers is da voordeel er al ni meer. Dus 'k ga deze ni verder uitwerken...
  

Ik zou dus twijfelen tussen Ring-based en R-A.
Voordeel Ring-based tov R-A: kans op minder lange wachttijd (zie d)).
Voordeel R-A tov Ring-based: fair.

c) Geen goesting om aan te beginnen. Lijkt me redelijk straight-forward (eenmaal je een algoritme gekozen hebt ).

d)

• Superserver (master & slave):
  Indien naar master: 2*delta
  Indien naar slave: 4*delta
  
• Ring-based algorithm:
  2*delta + eventuele minimale wachttijd indien token net in de andere server is
  
• Ricart-Agrawala algorithm:
  4*delta
  

Zo, da's dus mijn gedacht over die oefening. Maar er zijn voor mij dus ook nog veel onduidelijkheden in die opgave... :-S
En sorry voor de monsterpost. [/list]

[Stijn]

Iets wat ik nog staan heb van vorig jaar

basicly den uitleg op de slides - de code - idiote dingen

'k denk dat ik er wel op bepaald moment mee gestopt ben, dus tis denk ik nie volledig

en zijn slides van vorig jaar natuurlijk, geen idee of hij dit jaar daar veel aan veranderd heeft

succes met het examen in ieder geval !

[joxy]

hey allemaal,

Wat handig kan zijn voor het eerste gesloten boek deel van het examen is een lijst met termen met een korte uitleg erbij...
Ik heb er al eentje en die kan mag je altijd gebruiken:

office 97-2003
office 2007

Als jullie ergens fouten of onvolledigheden zien mogen jullie mij die altijd laten weten...

grtz,
Kristof

Tnx!

Ik was met iets gelijkaardigs begonnen op google docs

Ik heb het uwe erbij gezet, maar t'is nu wel wat een soep geworden:

http://docs.google.com/Doc?id=ddt5mfrn_19dzppvzfr&invite=hbf9stk

Jos

[Tim]

Deel 3 - Vraag1
b) P->C; Q//N; L->S

Is die Q//N wel juist? Ik dacht eerder aan Q?N. Of begrijp'k die // nu verkeerd?

[deMax]

Je zal da verkeerd begrijpen. // Betekent dat je niet goed weet hoe die 2 ten opzichte van elkaar geordend zijn. (waarschijnlijk dacht jij dat ze simultaan waren, maar de kans dat er 2 events perfect simultaan optreden is heel klein)

[mario]

Op slide 18 staat: they are not related by -> ; they are said to be concurrent; write as a || e

[bulbanos]

is de optie Q?N geen instinker? Volgens mij ist ofwel de -> ofwel de // relatie.