19. Examination Questions 2001-2002

Werner Van Belle¹ - werner@yellowcouch.org, werner.van.belle@gmail.com

1- Programming Technology Lab (PROG) Department of Computer Science (DINF) Vrije Universiteit Brussel (VUB); Pleinlaan 2; 1050 Brussel; Belgium

Abstract : A large collection fo questions for distributed systems.

Reference: Werner Van Belle; Examination Questions 2001-2002;

De onderstaande vragenlijst is 'all-encompasing'. In praktijk werden delen van dit examen gebruikt.

Message Diagrams

We gebruiken de volgende conventies bij het tekenen van message diagrams.

Bovenaan schrijven we in horizontale lijn de namen van al de relevante actoren. Bijvoorbeeld: de namen van de processen, klassen en instanties die nodig zijn om een protocol uit te leggen.
Onder elke actor komt een verticale lijn die het tijdsverloop voorstelt. Deze lijn wordt anders getekend naargelang het gedrag van de actor.
1. Indien er geen proces aanwezig is in de actor is er geen lijn getekend.
2. Indien er een proces aanwezig is dat aan het uitvoeren is, wordt een volle lijn getekend.
3. Indien er een proces aanwezig is dat aan het wachten is om iets te doen wordt een stippellijn getekend. (Bijvoorbeeld, aan het wachten tot iemand een bericht stuurt naar de actor)
4. Indien er een proces aanwezig is maar onbeschikbaar voor communicatie-partners (dit is bijvoorbeeld expliciet aan het wachten op een ander proces) met schuine lijntjes.
Als de control-flow van actor naar actor verspringt, maken we gebruik van horizontale pijlen, (of schuine pijlen om de netwerk-delay te illustreren) waarbij we eventueel de naam van het bericht op de pijl schrijven.
Het creëeren of starten van een nieuw proces wordt gedaan door een pijl te tekenen vanuit het creëerende proces naar ergens, waar een nieuw proces gewoon verder loopt.
Een control flow wordt beëindigd met een korte horizontale streep.

1 Wat kan

Welke van de volgende Message Sequence Charts zijn onmogelijk te implementeren met behulp van Java RMI en waarom ? Indien u een bepaalde MSC voor mogelijk acht, doch waarbij de implementatie niet 'triviaal' is, gelieve dan een korte uitleg erbij te geven. U kan (duidelijke !) aanduidingen maken op de tekeningen indien u dat wenst. Schrijf dan wel op elke pagina uw naam. Twee van de MSC's bevatten sockets, in dat geval kan u redeneren in termen van sockets ipv remote method invocations.

1.1 ...

Antwoord: nee

men moet wachten op antwoord
men kan geen thread interrupten die aan het rekenen is

1.2 ...

Antwoord: nee

de skeleton kan niet op eigen initiatief de client oproepen
de stub is geen eigen thread

1.3 ...

Antwoord: ja

1.4 ...

Antwoord: Niets mis mee

1.5 ...

Antwoord: Ook niets mis mee, required het synchronized keyword

1.6 ...

Antwoord: britishNee, na de return aan serverzijde kan niets meer gedaan worden

1.7 ...

Antwoord: Niets mis mee, het rare is dat de stub op de server kant gewoon werkt.

1.8 ...

Antwoord: Op het einde kan stub2 niet skeleton1 benaderen

1.9 ...

Antwoord: Is niet implementeerbaar met RMI omdat een client niet zomaar 3 stubs kan oproepen & omdat de stubs niet zomaar gaan wachten op elkaar.

1.10 ...

Antwoord: britishIs implementeerbaar met behulp van een gesharede variabele

1.11 --

Antwoord: nee

kan niet direct listen socket contacteren, dit moet via een connect eerst
de send wacht nooit tot de recv de brol er heeft afgeplukt

1.12 --

Antwoord: dit is correct, de eigenschappen van de socket moeten wel aangepast worden, maar dat terzijde

1.13 --

Antwoord: is niet mogelijk omdat een skeleton nooit meerdere threads in een keer gaat starten

1.14 --

Antwoord: dit is volledig correct

1.15 --

Antwoord: asynchrone call gaan niet

1.16 --

Antwoord:

Op het einde kan stub2 niet skeleton1 benaderen
Skeleton kan geen stub callen
Stubs hebben geen thread

1.17 --

Antwoord: Stubs doen niet aan multicasting

1.18 --

Antwoord: niet mogelijk

2 Factorial

Onderstaand zijn twee varianten van dezelfde vraag.

2.1 Variant 1

Het onderstaande is een interface die gebruikt kan worden om een faculteit te berekenen.

public interface FacCalcer extends Remote

{

public int fac(int n, FacCalcer fc) throws RemoteException;

public int answer(int n, int value) throws RemoteException;

}

Het onderstaande programma maakt hier gebruik van:

facvar1

public class FacApp
  extends UnicastRemoteObject 
  implements FacCalcer
  {
    public FacApp() throws RemoteException 
      {
      }
    public int answer(int n, int value) throws RemoteException
      {
        return n*value;
      }
    public int fac(int n, FacCalcer fc) throws RemoteException
      {
        System.out.println("fac("+n+")");
        if (n==1) return 1;
        return fc.answer(n,fac(n-1,this));
      }
    public static void main(String args[])
      {
        FacCalcer fc;
        FacApp self=null;
        try {
          int answer;
          self=new FacApp();
          try 
            {
              fc=(FacCalcer)Naming.lookup("faccalcer");
              answer=fc.fac(4,self);
              System.out.println("The answer my friend ... "+answer);
            } 
          catch (NotBoundException e)
            {
              System.out.println("faccalcer bound");
              Naming.bind("faccalcer",self); 
            }
          }
        catch (Exception e)  
          {
            System.out.println(e);
          }
      }
  }

Dit programma werkt en heeft indien het twee maal gestart wordt de onderstaande uitvoer.

> rmiregistry &

> Java FacApp &

faccalcer bound

> Java FacApp

fac(3)

fac(2)

fac(1)

The answer my friend ... 6

Teken de control flow van het volledige programma in detail aan de hand van een MSC.

2.2 Variant 2

Onderstaand is een interface die gebruikt kan worden om een faculteit te berekenen.

public interface FacCalcer extends Remote

{

public int fac(int n, FacCalcer fc) throws RemoteException;

}

Het onderstaande programma maakt hier gebruik van:

facvar2

public class FacApp
  extends MulticastRemoteObject 
  implements FacCalcer
  {
    public FacApp() throws RemoteException 
      {
      }
    public int fac(int n, FacCalcer fc) throws RemoteException
      {
        System.out.println("fac("+n+")");
        if (n==0) return 1;
        return n*fc.fac(n-1,this);
      }
    public static void main(String args[])
      {
        FacCalcer fc;
        FacApp self=null;
        try {
          int answer;
          self=new FacApp();
          try 
            {
              fc=(FacCalcer)Naming.lookup("faccalcer");
              answer=fc.fac(4,self);
              System.out.println("The answer my friend ... "+answer);
            } 
          catch (NotBoundException e)
            {
              System.out.println("faccalcer bound");
              Naming.bind("faccalcer",self); 
            }
          }
        catch (Exception e)  
          {
            System.out.println(e);
          }
      }
  }

Dit programma werkt en heeft indien het twee maal gestart wordt de onderstaande uitvoer.

> rmiregistry &

> Java FacApp &

faccalcer bound

> Java FacApp

fac(4)

fac(3)

fac(2)

fac(1)

fac(0)

The answer my friend ... 24

Teken de control flow van het volledige programma in detail aan de hand van een MSC.

3 RMI Internals

Wat gebeurt er als men een stub doorpassed naar de server waarnaar de stub refereert ? Bespreek hoe de serialisatie en deserialisatie gebeuren.
Wat gebeurt er als men een skeleton doorpassed naar een client ? Bespreek hoe de serialisatie en deserialisatie gebeuren.
Beschrijf de interne werking van een stub in gedetailleerde pseudocode. Gedetailleerd tot op het niveau van thread, socket en klasse operaties. Schrijf eveneens de serialisatie en deserialisatie neer in pseudo code.
Beschrijf de interne werking van een skeleton in gedetailleerde pseudocode. Gedetailleerd tot op het niveau van thread, socket en klasse operaties. Schrijf eveneens de serialisatie en deserialisatie neer in pseudo code.

4 RMI Extensie

Een enorm nadeel aan RMI is dat de standaard stubs niet goed overweg kunnen met multi-casts. (Dit is 1 bericht dat naar verscheidene clients tegelijk verzonden wordt). We willen nu een stub ontwikkelen die in staat is automatisch meerdere clients te contacteren voor eenzelfde request. Bijvoorbeeld: een clientprogramma vraagt aan de registry de addressenlijst voor de naam 'foo'. De registry zal 5 addressen weergeven. De stub die hierbij aangemaakt wordt, zal nu bij elke incoming call de 5 addressen contacteren voor het afhandelen van (bijvoorbeeld) de methode 'helloWorld'.

Een tweede probleem dat we met onze 'enhanced' stubs willen oplossen is de mogelijkheid tot het laten openstaan van een connectie. Normaliter zal Java RMI voor elke call steeds opnieuw een socket openen. (Is men braindead bij Sun of zit hier een reden achter ?). Daar dit veel te traag gaat willen we dit niet meer, we willen nu een socketconnectie zo lang mogelijk open laten.

Schrijf neer in gedetailleerde pseudocode hoe een dergelijke stub eruit ziet. Gedetailleerd tot op het niveau van thread-, socket- en klasse-operaties. Schrijf eveneens de serialisatie en deserialisatie van de stub neer in pseudo code.

5 Transacties

Bespreek waarom transacties noodzakelijk zijn binnen open gedistribueerde systemen. Geef eveneens een voorbeeld.

6 Forwarding & Distributed Transactions

We hebben een server die de volgende interface aanbied. Alle messages worden asynchroon verstuurd

incoming messages on server:
getColor(int tx, int x, int y)
setColor(int tx, int x, int y, int color)
beginTransaction()
lock(int tx, int x, int y)
commitTransaction(int tx)
abortTransaction(int tx)

outgoing messages from server:
color(int x, int y, int val)
transaction(int tx)
lock(int tx, boolean obtained)
transactionAborted(int tx)
transactionComitted(int tx)

[getColor] kan worden verstuurd naar de server. Neemt een transaction context, x en y coordinaat. Als resultaat zal een color message terug gestuurd worden.
[setColor] kan worden verstuurd naar de server. Neemt een transaction context, de coordinaten en de kleurwaarde. Als resultaat wordt niets terug gestuurd.
[beginTransaction] kan worden verstuurd naar de server. Deze zal een transactie context teruggeven door het terugsturen van de transaction message.
[lock] moet verstuurd worden met een bepaalde transactie en een positie vooraleer we iets kunnen aanvangen met de gegeven positie. Als antwoord wordt een lock message terug gestuurd.
[commitTransaction] wordt verstuurd naar de server om een transactie te bevestigen. De server zal als resultaat de message transactionComitted terugsturen.
[abortTransaction] wordt verstuurd naar de server om een transactie te aborten. De server zal als resultaat de message transactionAborted terugsturen.
[color] wordt verstuurd van de server naar de client om de kleur op een bepaalde positie te melden. Dit gebeurt in response op getColor.
[transaction] wordt gestuurd na het aanvragen van een beginTransaction. Tx is de context die in alle andere messages meegegeven moet worden.
[transactionAborted] wordt gestuurd vanaf de server als een transactie geabort is. Dit kan enkel in response op een abortTransaction.
[transactionCommited] wordt gestuurd vanaf de server als een transactie successvol gecommit is.
[lock] wordt teruggestuurd vanaf de server met als boolean value true als de lock verkregen is, met false als de positie reeds gelocked is door een ander.

Het idee is nu dat we een forward proces schrijven dat zich exact hetzelfde gedraagt als de server, maar in plaats van de functionaliteit zelf te implementeren zou deze forwarder requests moeten doorsturen naar een array van servers. Dit zoals op onderstaande tekening aangeduid is.

Schrijf deze forwarder ervan uitgaande dat de servers nooit zullen crashen. Tijdens het afhandelen van een binnenkomend bericht bevat de variabele From de naam van het proces dewelke ons de request gestuurd heeft.
Pas uw forwarder aan zodat hij overweg kan met crashende clients en crashende servers. Als een connectie met een process uitvalt zal de message ProcessDropped gestuurd worden naar de forwarder.

7 Topology Detection

We willen de toplogie van een netwerk automatisch detecteren. Hiertoe zullen we op alle machines die deel uitmaken van het netwerk een proces draaien. Al de processen binnen het netwerk kennen elkaar. Als uitvoer van de gehele berekening willen we een 4 dimensionale matrix die aangeeft of 2 connecties met elkaar een geshared deel hebben.

De processen worden allen gestart en hebben exclusieve toegang tot het netwerk. U mag er dus vanuit gaan dat geen enkel ander proces buiten onze processen op het netwerk draaien.

Bespreek hoe u de bandbreedte kan meten die een connectie heeft aan de hand van sockets.
Bespreek hoe u de processen kan synchroniseren zodat ze niet in mekaars netwerkweg lopen.
Schrijf pseudo code om exhaustief elke positie binnen de matrix te testen.
Teken message diagrams om de communicatie tussen processen te illustreren.
De tijd om dergelijk iets te bepalen is nogal hoog. Kunnen we dit verbeteren door een aantal processen parallel te laten werken ?

8 Bedenk (40')

We hebben een proces A dat data bewerkt en uitstuurt naar proces B. Proces B bewerkt de data op zijn manier en stuurt de data verder naar proces C. Deze vorm van parallellisatie word pipelining genoemd. Het is natuurlijk zo dat als proces A rapper data bewerkt dan proces B, proces B langzaam maar zeker gaat verzuipen in zijn backlog.

We willen er nu voor zorgen dat geen enkel proces meer moet verwerken dan het kan verwerken. We willen dit implementeren aan de hand van sockets. Schrijf het protocol neer dat u hiervoor zou gebruiken.

9 Passing stubs/skeletons through (30')

Wat gebeurt er als men een stub doorpassed naar de server waarnaar de stub refereert ? Bespreek hoe de serialisatie en deserialisatie gebeuren.
Wat gebeurt er als men een skeleton doorpassed naar een client ? Bespreek hoe de serialisatie en deserialisatie gebeuren.

10 Actors

10.1 Basis Actor functionaliteit

De basisfunctionaliteit van actors word beschreven aan de hand van een aantal klassen:

De actor interface is de remote interface naar actors toe.
De actor klasse is the basis klasse voor alle actors. Deze bevat standard functionaliteit voor het zenden en ontvangen van berichten.
De message queue klasse, dewelke een eenvoudige producer consumer implementeert.

ActorInterface

public interface ActorInterface
  extends java.rmi.Remote
{
   public void receiveMessage(Message m) throws RemoteException;
}

Actor

public class Actor
  extends UnicastRemoteObject
  implements ActorInterface, Runnable, Remote
{
   protected String actor;
   private MessageQueue messages;
   public Actor(String name) throws RemoteException
     {
        try
          {
             actor=name;
             Naming.bind(name,this);
             messages=new MessageQueue();
          }
        catch (Exception e) {...}
        // the line below starts a new thread that immediatelly invokes run
        // on this object. After _starting_ run, the control flow is returned
        new Thread(this).start();
     }
   public void sendMessage(String target, Message m)
     {
        try
          {
             Remote rr=Naming.lookup(target);
             System.out.println(actor+" sends message");
             ActorInterface r = (ActorInterface)rr;
             r.receiveMessage(m);
          }
        catch (Exception e) {...}
     }
   public void receiveMessage(Message m) throws RemoteException
     {
        try
          {
             System.out.println(actor+" received message");
             messages.push(m);
          }
        catch (Exception e) {...}
     }
   public void run()
     {
        while(true)
          {
             Message m=messages.pop();
             try
               {
                  System.out.println(actor+" starts handling message");
                  handleMessage(m);
                  System.out.println(actor+" stops handling message");
               }
             catch (Exception e) {...}
          }
     }
   public void handleMessage(Message m)
     {
        System.out.println("Please define a handleMessage(Message m) in your subclass");
     }
}

"); ?>

MessageQueue

class MessageQueue
{
   private Message busywith=null;
   private LinkedList ll = new LinkedList();
   
   /**
    * Creates a messagequeue, which can be used to implement a synchronous
    * receive at consumer side and an asynchronous send ad producer side. In
    * other words. The push is asynchrounous and puts a message in the Q,
    * while the pop blocks if there is no message available.
    */
   public MessageQueue()
     {
     }
   
   public synchronized void push(Message o)
     {
        ll.addLast(o);
        notify();
     }
   
   /**
    * Blocking pop to retrieve the next message on the Q. If the Q is empty
    * this method will block until a message is pushed upon the Q. This method
    * is used to synchronize two threads to each other using a consumer
    * producer like approach.
    */
   public synchronized Message pop()
     {
        try
          {
             if (ll.isEmpty())
               {
                  busywith=null;
                  wait();
               }
             busywith = (Message)ll.getFirst();
             ll.removeFirst();
             return busywith;
          }
        catch(Exception e) {...}
     }
}

10.2 Messages tussen actors

De berichten tussen actors moeten de Message interface implementeren. In het voorbeeld dat we verder gaan uitwerken, zijn er slechts twee messages geimplementeerd:

de JuliaRequest, een message die verstuurd kan worden naar een AnimatedFractalCalcer.
een ImageMessage, dewelke een image kan bevatten.

Message

interface Message extends Serializable
{
}

JuliaRequest

public class JuliaRequest 
  implements Message
{
   public String returnTo;
   public double cx,cy;
   public int id;
   public JuliaRequest(String returnImageTo, double ax, double ay, int i)
     {
        returnTo=returnImageTo;
        cx=ax;
        cy=ay;
        id=i;
     }
}

ImageMessage

public class ImageMessage
  implements Message
{
   public int xs, ys, id;
   int[] content;
   String answerFrom;
   public ImageMessage(BufferedImage img, int x, int y)
     {
        xs=x;
        ys=y;
        content=img.getRGB(0, 0, xs, ys, null, 0, xs);
     }
   public ImageMessage(BufferedImage img, int x, int y, String from, int i)
     {
        this(img,x,y);
        id=i;
        answerFrom=from;
     }
   public BufferedImage convertToBufferedImage()
     {
        BufferedImage image;
        image=new BufferedImage(xs, ys, BufferedImage.TYPE_INT_RGB);
        // im.setRGB(0,0,XS,YS,im.getImageData());
        image.setRGB(0,0,xs,ys,content,0,xs);
        return image;
     }
}

10.3 Animation Actors

Op basis van bovenstaande basis klassen zijn twee actors gedefinieerd: De eerste is een FractalAnimator server, de tweede een FractalCalcer. De animator server zal aan een aantal clients vragen een Julia set te berekenen met bepaalde paramaters. Telkens dergelijke fractalcalcer actor antwoord zal de tekening getoond worden en een nieuwe request opgestuurd. De server klassen:

FractalBufferedImage: deze klasse is de window waarop getekend wordt, weinig interessant.
FractalAnimator: de server actor in kwestie.
AnimatedFractalCalcer: de actor die een Julia set kan berekenen.

FractalBufferedImage

class FractalBufferedImage
  extends Canvas
{ 
   BufferedImage image;
   int XS=0;
   int YS=0;
   
   FractalBufferedImage()
     {
        Frame f = new Frame();
        f.setSize(XS,YS);
        f.add(this);
        f.show();
     }
   
   public void setImage(BufferedImage img)
     {
        image=img;
        repaint(0);
     }
   
   public void paint(Graphics g)
     {
        if (image!=null)
          g.drawImage(image,0,0,this);
     }
}

FractalAnimator

public class FractalAnimator
  extends Actor
{
   protected FractalBufferedImage painter;
   protected String clients[];
   protected double x, dx;
   protected int sendid;

public FractalAnimator(String name, String args[]) throws RemoteException
     {
        super(name);
        painter=new FractalBufferedImage();
        clients=args;
        x  = -1.0;
        dx = 0.2;
        sendid = 1;
	// please note that we send immediatelly two requests to all 
	// participating actors !
        askForNextFrames();
        askForNextFrames();
     }
   
   protected void askForNextFrame(String proc)
     {
        x+=dx;
        sendMessage(proc,new JuliaRequest(actor,0.0,x,sendid++));
     }
   
   protected void askForNextFrames()
     {
        int i=1;
        while(i<clients.length)
          {
             askForNextFrame(clients[i]);
             i++;
          }
     }

   protected boolean showFrame(ImageMessage frame)
     {
       painter.setImage(frame.convertToBufferedImage());
     }
   
   public void handleMessage(Message m)
     {
        if (m instanceof ImageMessage)
          {
             ImageMessage im=(ImageMessage)m;
             showFrame(im);
             askForNextFrame(im.answerFrom);
          }
        else super.handleMessage(m);
     }
   
   public static void main(String args[])
     {
        try { new FractalAnimator(args[0],args); }
        catch (Exception e) {...}
     }
}

AnimatedFractalCalcer

/**
 * calculates a julia set for the given coordinates and sends an answer
 * back
 */

public class AnimatedFractalCalcer
  extends Actor
{ 
   Color colorscheme[];
   int XS = 0, YS = 0, PREC = 7;
   
   public AnimatedFractalCalcer(String name) throws RemoteException
     {
        super(name);
        colorscheme=new Color[PREC+1];
        for (int i=0; i<PREC; i++)
          {
             int phase=5*i/PREC;
             colorscheme[i]= new Color((phase+0)%6,phase,(phase+0)%6);
          }
        colorscheme[PREC]=Color.black;
     }
   
   void drawJuliaBSM(BufferedImage g, double cx, double cy, int w, int h)
     { 
        double x, y, t;
        int k;
        for (double i=-2; i<2; i+=4.0/w)
          for (double j=-2; j<2; j+=4.0/h)
            {
               x = i; y=j;
               for (k=0; k<PREC; k++)
                 {
                    t = x*x-y*y+cx;
                    y = 2*x*y+cy;
                    x = t;
                    if (x*x+y*y >= 4) break;
                 }
               g.setRGB((int)((i+2)*w/4), (int)((j+2)*h/4),colorscheme[k].getRGB());
            }
     }
  
   public void handleMessage(Message m)
     {
        if (m instanceof JuliaRequest)
          {
             // if it is a calcrequest we calculate the juliaset
             JuliaRequest cr=(JuliaRequest)m;
             BufferedImage img;
             img=new BufferedImage(XS, YS, BufferedImage.TYPE_INT_RGB);
             drawJuliaBSM(img, cr.cx, cr.cy, XS, YS);
             sendMessage(cr.returnTo,new ImageMessage(img,XS,YS,actor,cr.id));
          }
        else super.handleMessage(m);
     }
   
   public static void main(String args[])
     {
        try { new AnimatedFractalCalcer(args[0]); }
        catch (Exception e) {...}
     }
}

We starten deze klassen op de volgende wijze

rmiregistry &
java AnimatedFractalCalcer //127.0.0.1/A &
java AnimatedFractalCalcer //127.0.0.1/B &
java FractalAnimator //127.0.0.1/S //127.0.0.1/A //127.0.0.1/B

Teken de control flow van het volledige programma in detail aan de hand van een MSC. Gedetailleerd betekend inclusief de stubs, skeletons en de rmiregistry.

11 Partial Failure

Java RMI gebruikt een systeem waarbij exceptions worden teruggegeven op het ogenblik een error optreed. Als de server een programmatorische fout bevat zal de skeleton een exception terugsturen naar de client. Als de netwerkconnectie faalt tijdens het sturen van data zal de stub zelf een exception genereren. (Zoals geillustreerd in bovenstaande figuur). Dit systeem lijkt mooi, doch heeft een aantal inherente nadelen. Bespreek hoe een proces in een niet geldige, of moeilijk te kennen toestand kan geraken, na het optreden van een aantal errors. Maak dit duidelijk aan de hand van een MSC !

http://werner.yellowcouch.org/
werner@yellowcouch.org