Home
 
 

Ada ,,requeue`` Konstrukt

Ada ,,requeue`` Konstrukt

when <condition>Zustand des Bedienersnicht

$\Rightarrow$ Erfüllung des Bedienwunsches kann nicht durch Barriere an Art des Wunsches (z.B. Umfang, Dringlichkeit) geknüpft werden.

Klar: Wenige(!) diskrete Fälle können durch Vermehrung der entries gehandhabt werden.

Allgemein:

Abhilfe

doppelte
  1. Sagen, was man will.
  2. Dafür anstehen, daß man das kriegt.

Mit unseren bisherigen Mitteln bedeutet das, daß der Klient auch zwei entry-calls benötigt; das folgende Programm illustriert die Technik, wobei der Server/Ressourcenverwalter durch ein protected-object repräsentiert wird (ähnlich: task);

Prinzip der Lösung

request(...)waitwaitneu 

-----------------------------------

- resource management for varying requests

-

- structure:  requesters = task, resourcepool(+mangement) = protected object

- version1: double interaction

-----------------------------------






with Stringpack, Ada.Numerics.Float_Random; use Stringpack, Ada.Numerics.Float_Random;

procedure Resources1 is






G : Generator;

Number_Of_Clients : constant Natural := 3;

Number_Of_Resources : constant Natural := 5;

How_Often : constant Natural := 5;






protected Resource_Manager  is --------------------

procedure Request(How_Many : Positive; Ok : out Boolean); -+ double interaction

entry Wait (How_Many : Positive; Ok : out Boolean);       -+

procedure Release(How_Many : Positive);

private

Free : Natural := Number_Of_Resources;

Release_Event : Boolean := False;

Wanted : Natural := 0;     - for trace only, offene Wünsche

end Resource_Manager;






protected body Resource_Manager is






procedure Trace is

Not_Free : Natural := Number_Of_Resources - Free;

begin

Outbuffer := Varnull;

for I in 1..Number_Of_Resources loop

if I <= Not_Free then Outbuffer := Outbuffer & " X";

else Outbuffer := Outbuffer & ";

end if;

end loop;

Outbuffer := (Outbuffer & "  wanted = ") & Wanted;

Print;

end Trace;






procedure Request(How_Many : Positive; Ok : out Boolean) is

         - this could be an entry with "when free > 0"

begin

if How_Many <= Free

then Free := Free - How_Many; Ok := True;  -allocate

else Ok := False;

Wanted := Wanted + How_Many;   - for trace

end if;

Trace;

end Request;






entry Wait (How_Many : Positive; Ok : out Boolean) when Release_Event  is

begin

if Wait'Count = 0 then Release_Event := False; end if;

         - => loop over all waiting requesters !!!

if How_Many <=  Free

then Free := Free - How_Many; Ok := True;  -allocate

Wanted := Wanted - How_Many;   - for trace

Trace;

else Ok := False;

end if;

end Wait;






procedure Release(How_Many : Positive) is

begin

Free := How_Many + Free;  - release

if Wait'Count > 0 then Release_Event := True; end if;

Trace;

end Release;






end Resource_Manager;  ------------------------






task type Clients is   ------------------------

entry Start(How_Many : Natural);

end Clients;






task body Clients is

My_Need : Natural;

Done : Boolean;

begin

accept Start(How_Many : Natural)

do My_Need := How_Many; end Start;

for I in 1..How_Often loop

delay Duration(0.001* Random(G));

Resource_Manager.Request(My_Need, Done);

while not Done loop                                 -+ immer neu "wait"

Resource_Manager.Wait(My_Need, Done); end loop;  -+ aufrufen!

delay Duration(0.001 * Random(G));

Resource_Manager.Release(My_Need);

end loop;

end Clients;






Client : array(1..Number_Of_Clients ) of Clients;  --------






begin  ------------------------------main






Client(1).Start(1); Client(2).Start(2); Client(3).Start(5);






end Resources1;  ---------------------------






-----------------------------------

32 pohlmann@pavian:resources1

X - - - -  wanted = 0

X - - - -  wanted = 5  ! Client 3 fordert 5 Einheiten !

X X X - -  wanted = 5

X X - - -  wanted = 5

- - - - -  wanted = 5

X - - - -  wanted = 5  ! Client 3 wird von Client 1 überholt !

X X X - -  wanted = 5

X X - - -  wanted = 5

- - - - -  wanted = 5

X X X X X  wanted = 0

X X X X X  wanted = 1

X X X X X  wanted = 3

- - - - -  wanted = 3

X - - - -  wanted = 2

X X X - -  wanted = 0

X X X - -  wanted = 5

X - - - -  wanted = 5

- - - - -  wanted = 5

X X X X X  wanted = 0

X X X X X  wanted = 2

X X X X X  wanted = 3

- - - - -  wanted = 3

X X - - -  wanted = 1

X X X - -  wanted = 0

X X X - -  wanted = 5

X X - - -  wanted = 5

- - - - -  wanted = 5

X X X X X  wanted = 0

X X X X X  wanted = 1

X X X X X  wanted = 3

- - - - -  wanted = 3

X - - - -  wanted = 2

X X X - -  wanted = 0

X X - - -  wanted = 0

X X - - -  wanted = 5

- - - - -  wanted = 5

X X X X X  wanted = 0

- - - - -  wanted = 0

X X X X X  wanted = 0

- - - - -  wanted = 0

33 pohlmann@pavian:

Kritik

  • Umständlich + fehleranfällig
    $\Rightarrow$ Operation für Betriebsmittel anfordern in Paket verkapseln, sodaß Klient-Programm nur 1 Aufruf.
  • Ineffizient (wiederholter Aufruf von ,,wait``, aber aufrufende task jedesmal sinnlos aktivieren).
  • Unsicher im Hinblick auf Reihenfolge der Betriebsmittelzuteilung (d.h. $\neq$ FIFO), siehe Beispiel-Protokoll:
    client 3$\stackrel{5}{\longrightarrow}$request
     $\stackrel{not ok}{\longleftarrow}$ 
    client 1$\longrightarrow$release
    client 2$\longrightarrow$release
    client 1$\stackrel{1}{\longrightarrow}$request
     $\stackrel{ok}{\longleftarrow}$ 
    client 2$\stackrel{2}{\longrightarrow}$request
     $\stackrel{ok}{\longleftarrow}$ 
    client 3$\longrightarrow$wait

    d.h. Problem, daß Klient zwischen request und wait unterbrochen wird.

Abhilfe durch neues Sprachmittel:
,,private entry`` und ,,requeue`` erlauben, die Doppel-Aktion allein durch den entry-Akzeptor ausführen zu lassen, d.h. Klient wird nicht tätig, Server kann Klienten ohne Gefahr des Überholens in Warteschlange einfügen, d.h. als atomare Aktion.

client$\longrightarrow$request
  $\downarrow$ requeue
  wait

Anstatt:

client$\longrightarrow$request
 $\stackrel{not ok}{\longleftarrow}$ 
client$\longrightarrow$wait 

-----------------------------------

- resource management for varying requests

-

- structure:  requesters = task, resourcepool(+mangement) = protected object

- version2:   requeue unserviced requests

-----------------------------------






with Stringpack, Ada.Numerics.Float_Random; use Stringpack, Ada.Numerics.Float_Random;

procedure Resources2 is






G : Generator;

Number_Of_Clients : constant Natural := 3;

Number_Of_Resources : constant Natural := 5;

How_Often : constant Natural := 5;






protected Resource_Manager  is ------------------

entry Request(How_Many : Positive);

procedure Release(How_Many : Positive);

private

entry Wait (How_Many : Positive);            - private entry for requeue

Free : Natural := Number_Of_Resources;

Release_Event : Boolean := False;

To_Try : Natural := 0;  - # requests to be tried on release; <= wait'count

Wanted : Natural := 0;  - for trace only

end Resource_Manager;






protected body Resource_Manager is






procedure Trace is

Not_Free : Natural := Number_Of_Resources - Free;

begin

Outbuffer := Varnull;

for I in 1..Number_Of_Resources loop

if I <= Not_Free then Outbuffer := Outbuffer & " X";

else Outbuffer := Outbuffer & ";

end if;

end loop;

Outbuffer := (Outbuffer & "  wanted = ") & Wanted;

Print;

end Trace;






entry Request(How_Many : Positive) when True is  - could be "when free > 0"

begin

if How_Many <= Free

then Free := Free - How_Many;   -allocate

Trace;

else  Wanted := Wanted + How_Many;   - for trace

Trace;

requeue Wait;

end if;

end Request;






entry Wait (How_Many : Positive) when Release_Event  is

begin

To_Try := To_Try - 1; -  loop over all waiting requesters !!!

if To_Try = 0 then Release_Event := False; end if;

if How_Many <=  Free

then Free := Free - How_Many;   -allocate

Wanted := Wanted - How_Many;   - for trace

Trace;

else requeue Wait;

end if;

end Wait;






procedure Release(How_Many : Positive) is

begin

Free := How_Many + Free;  - release

if Wait'Count > 0 then To_Try := Wait'Count; Release_Event := True; end if;

Trace;

end Release;






end Resource_Manager;  ----------------------






task type Clients is   ----------------------

entry Start(How_Many : Natural);

end Clients;






task body Clients is

My_Need : Natural;

begin

accept Start(How_Many : Natural)

do My_Need := How_Many; end Start;

for I in 1..How_Often loop

delay Duration(0.001* Random(G));

Resource_Manager.Request(My_Need);

delay Duration(0.001 * Random(G));

Resource_Manager.Release(My_Need);

end loop;

end Clients;






Client : array(1..Number_Of_Clients ) of Clients;  --------






begin  ------------------------------main






Client(1).Start(1); Client(2).Start(2); Client(3).Start(5);






end Resources2;  ---------------------------






-----------------------------------

35 pohlmann@pavian:resources2

X - - - -  wanted = 0

X - - - -  wanted = 5

X X X - -  wanted = 5

X X - - -  wanted = 5

 - - - - -  wanted = 5

X X X X X  wanted = 0  ! Client 3 (mit Bedienversuch 5) kommt durch, weil

X X X X X  wanted = 1    sofort im Anschluß requeueïn Warteschlange von

X X X X X  wanted = 3    "waitëingefügt !

 - - - - -  wanted = 3

X - - - -  wanted = 2

X X X - -  wanted = 0

X - - - -  wanted = 0

 - - - - -  wanted = 0

X X X X X  wanted = 0

X X X X X  wanted = 2

X X X X X  wanted = 3

 - - - - -  wanted = 3

X X - - -  wanted = 1

X X X - -  wanted = 0

X X - - -  wanted = 0

 - - - - -  wanted = 0

X X X X X  wanted = 0

X X X X X  wanted = 1

X X X X X  wanted = 3

 - - - - -  wanted = 3

X - - - -  wanted = 2

X X X - -  wanted = 0

X - - - -  wanted = 0

X - - - -  wanted = 5

 - - - - -  wanted = 5

X X X X X  wanted = 0

X X X X X  wanted = 2

X X X X X  wanted = 3

 - - - - -  wanted = 3

X X - - -  wanted = 1

X X X - -  wanted = 0

X X X - -  wanted = 5

X X - - -  wanted = 5

 - - - - -  wanted = 5

X X X X X  wanted = 0

 - - - - -  wanted = 0

36 pohlmann@pavian:

Zur Syntax und Semantik von ,,requeue``

  • Gibt's für tasks und protected-objects, oft für ,,private`` entry.
  • Entry von requeue muß dasselbe Parameterprofil haben wie das ürsprüngliche entry oder muß parameterlos sein. Parameter müssen bei requeue nicht extra genannt werden.
  • Requeue kann auch entries anderer Objekte ansprechen.
  • Mit Ausführung des ,,requeue`` ist der Aufruf des ursprünglichen entry erstmal zuende (d.h. insbesondere, daß jetzt andere Aufrufe des protected-objects durchkommen können).
  • Task, die auf ein entry (insbesondere infolge requeue wartet) hat die übliche Präferenz gegen Aufrufer von außen: Nach jeder Zustandsänderung des Objekts werden die Wächter neu ausgewertet und die darauf wartenden tasks bedient: ,,Internal-Progress-First Rule``.

Requeue ist bequemes Mittel zu Lösung kompilzierter Synchronisationsprobleme: Ein Aufruf einer protected-operation von außen wird intern, kann intern zerlegt werden in eine Folge geschützter Teiloperationen, die in genau festgelegter Weise mit anderen Operationen verzahnt sind.

Beispiel

Verkehrssystem
  • einer ringförmigen U-Bahn(o.ä.)-Linie mit Bahnhöfen.
  • einer dieser Linien (in fester Richtung) bedienender Zug.
  • Kunden.

Wir realisieren den Zug und die Passagiere durch tasks und den Bahnhof (naheliegend) als protected-object; im Bahnhof werden Zug und Passagiere gemeinsam aktiv, Aufenthalt des Zugs im Bahnhof ist charakterisiert durch 2 Phasen:

\includegraphics{reqZug.eps}

Außerdem modellieren wir die Fahrt eines Passagiers durch requeue bei der gewünschten Ziel-Station:

\includegraphics{reqPassagier.eps}


-----------------------------------

- metro  - illustrates use of requeue

-

- problem: model circular metro line with 1 train and stations where

-          passengers enter/leave

-

- structure: passengers & train = task, stations = protected objects

- requeue is used to 1. delay passengers for trip to their destination,

-                                2. guide train through phases

-                                   (passengers alight/board) at stations

- cf: Burns/Wellings ch.8.6 (does not use 2.)

-

- !!! start protocol ( cf.main ) necessary for initialisation !!!

- !!! program does NOT terminate (just stops producing output) !!!

-----------------------------------






with Stringpack, Ada.Numerics.Discrete_Random; use Stringpack;

procedure Metro is






Number_Of_Stations : constant Natural := 5;

subtype Station_Range is Integer range 1..Number_Of_Stations;






package Random_Destination is new Ada.Numerics.Discrete_Random(Station_Range);

use Random_Destination;

G : Generator;






Number_Of_Clients : constant Natural := 100; - small town

Capacity : Integer  := 50;  - (relatively) big train






How_Often : constant Natural := 4;  - traced rounds in sample run






-------------------------------trace






type Trace_Type is record

Train_At_Station : Boolean := False;

Clients_At_Station : Natural := 0; - initially there or alighted

Passenger_Count : Natural := 0;  - in train on leaving station

end record;

Station_Trace : array(Station_Range) of Trace_Type;      -global!!






procedure Trace is

begin

Outbuffer := Varnull;

for I in Station_Range  loop

Outbuffer := Outbuffer & Cvis(Station_Trace(I).Clients_At_Station,3);

if Station_Trace(I).Train_At_Station

then Outbuffer := Outbuffer &

           " & Cvis(Station_Trace(I).Passenger_Count,2) &» ";

else Outbuffer := Outbuffer & ;

end if;

end loop;

Print;

end Trace;






----------------------------------






protected type Stations  is --------------------

procedure Start(Id : Station_Range);

entry Train_Comes_In(On_Board : in out Natural);

entry Board_The_Train(Where : Station_Range);

private

My_Id : Station_Range;                        - must be set initially!!!

entry Alight_At_Destination;           - private entry to requeue client

                                              - private entry to requeue train

entry Passengers_Board(On_Board : in out Natural);

                                              - private entry to requeue train

entry Close_Doors(On_Board : in out Natural);

Passenger_Count : Natural := 0;                    - # Passagiere in Zug

Boarding, Alighting : Boolean := False;            -  Phase

end Stations;






Station : array(Station_Range) of Stations;






protected body Stations is






procedure Start(Id : Station_Range) is

begin My_Id := Id; end Start;






entry Board_The_Train(Where : Station_Range)

when Boarding and then Passenger_Count < Capacity is

begin

Passenger_Count := Passenger_Count + 1;                  - fuelle Zug

Station_Trace(My_Id).Clients_At_Station :=

Station_Trace(My_Id).Clients_At_Station - 1;   - trace

requeue Station(Where).Alight_At_Destination;        - Ziel der Reise

end Board_The_Train;






entry Train_Comes_In(On_Board : in out Natural)

when True is                           - requeue nur in entry erlaubt!!!

begin

Station_Trace(My_Id).Train_At_Station := True; - trace

Passenger_Count := On_Board;

Alighting := True;

requeue Passengers_Board;

end Train_Comes_In;






entry Alight_At_Destination when Alighting is

begin

Passenger_Count := Passenger_Count - 1;   - leave train

Station_Trace(My_Id).Clients_At_Station :=

Station_Trace(My_Id).Clients_At_Station + 1;  - trace

end Alight_At_Destination;






entry Passengers_Board(On_Board : in out Natural)

when Alight_At_Destination'Count = 0 is

begin

Alighting := False;

Boarding := True;

requeue Close_Doors;

end Passengers_Board;






entry Close_Doors(On_Board : in out Natural)

when  Boarding and (Board_The_Train'Count = 0 or Passenger_Count = Capacity) is

begin

Boarding := False;

On_Board := Passenger_Count;  - out Parameter von train_comes!!

Station_Trace(My_Id).Passenger_Count := Passenger_Count;  -trace

Trace;

Station_Trace(My_Id).Train_At_Station := False; - trace

end Close_Doors;






end Stations; ---------------------------






task type Clients is   ----------------------

entry Start;

end Clients;






task body Clients is

From, To : Station_Range;

begin

accept Start;

From := Random(G);

Station_Trace(From).Clients_At_Station :=

Station_Trace(From).Clients_At_Station + 1;  - trace

loop  - infinite loop !!!!

To := Random(G);

Station(From).Board_The_Train(To);

From := To;

end loop;

end Clients;






Client : array(1..Number_Of_Clients ) of Clients;  --------






task Train is   --------------------------

entry Start;

end Train;






task body Train is

Nr_Passengers : Natural := 0;

begin

accept Start;

for I in 1..How_Often loop  -sample run

for J in Station_Range loop

Station(J).Train_Comes_In(Nr_Passengers);

end loop;

end loop;

end Train;






begin  ------------------------------main






for I in Station_Range loop Station(I).Start(I); end loop;

for I in 1..Number_Of_Clients loop Client(I).Start; end loop;

Train.Start;






end Metro;  -----------------------------






-----------------------------------

24 pohlmann@pavian:metro

0 |32>  20       20       18       10

0        7 |45>  20       18       10

0        7       15 |50>  18       10

0        7       15       18 |50>  10

0        7       15       18       12 |48>

27 |21>   7       15       18       12

27       11 |17>  15       18       12

27       11       12 |20>  18       12

27       11       12        7 |31>  12

27       11       12        7        9 |34>

20 |41>  11       12        7        9

20        9 |43>  12        7        9

20        9       14 |41>   7        9

20        9       14       14 |34>   9

20        9       14       14        8 |35>

16 |39>   9       14       14        8

16        8 |40>  14       14        8

16        8       15 |39>  14        8

16        8       15       14 |39>   8

16        8       15       14        6 |41>

^C

25 pohlmann@pavian

= Situation bei Abfahrt des Zugs:
#(Passagiere) in Stationen (nicht notwendig in queue!), #(Passagiere) im Zug |>, $\sum = 100$.

Hausaufgabe

  1. Der Gebrauch der Zustandsvariablen/private entries ist etwas übertrieben für den Anlaß; vereinfachen Sie das Programm.
  2. Überlegen Sie sich Möglichkeiten, das Programm ordentlich terminieren zu lassen! Schwierigkeit ist offenbar, daß clients auf ein entry warten können, wenn der Zug Feierabend macht. Diskutieren/probieren Sie Lösungen, bei denen
    • der Ablauf in ,,station`` durch weitere Zustandsgrößen/Handlungsalternativen verfeinert wird.
    • die Klienten früher Schluß machen (nach n Fahrten) als der Zug.
    • von uns noch nicht behandelte Sprachmittel Adas (insbesondere ,,requeue ...with abort`` sowie ,,asynchronous transfer of control``, kurz ATC) eingesetzt werden.
nextnextupuppreviouspreviouscontentscontents
Nächste Seite:Concurrency and ObjectsAufwärts:Vorlesungsskriptum zu Spezielle AnwendersprachenVorherige Seite:BeispieleInhaltsverzeichnis
Ronald Blaschke 2001-06-02