Task: Printing

Task: Letter Game

Task: Street Race

Triggers events

What is CLR

Client and Server

There are two users, each having a computer. The
computers are identified by their names: CLIENT(1) and CLIENT(2). The two
computers share one or more printers named SERVER(1), SERVER(2) and so on. The
print jobs from both computers can only be executed in succession. To coordinate
the communication between both computers with a printer we will use a special
object: a semaphore.

Semaphore

Each printer has one related semaphore. A semaphore is in one
of two states: S1 or S2. When the printer is free to receive a print job, the
semaphore is in state S1. As long as the printer is busy with executing a print
job the semaphore is in state S2.

A semaphore can make two kinds of state transitions: `S1->S2' and
`S2->S1'. When a user sends a print job to the computer, the computer will
send a message "Are_you_open?" to the semaphore. If the state of the semaphore
is S1, then the state of the semaphore will change to S2 and the semaphore will
send a message "Open" to the computer that sent the message "Are_you_open?". If
the state of the semaphore is S2 then the semaphore will send back a message:
"Closed". After finishing a print job, the printer will send a message "Ready"
to the semaphore. Upon receiving a message "Ready", the semaphore will change
its state to S1.

Object type SEMAPHORE

In Documentation 1 you will
find the specification of the object type SEMAPHORE. The specification includes
the possible identifiers and the states of an object of the type SEMAPHORE, the
`Priority List', the `Communication Diagram', the `State Transition Diagram',
and the 'Receive Procedures' for the messages: "Ready" and "Are_you_open?". The
`Receive Procedures' describe how a semaphore responds to a message.

The `Priority List' is necessary because messages that are received at the
same time by a semaphore can only be handled in succession. The `Priority List'
in Documentation 1 indicates that each message of a SERVER
has a higher priority than a message of a CLIENT and that for instance a message
of SERVER(2) has a higher priority than a message of SERVER(3).

Object type CLIENT

In Documentation 2 you will find
the specification of the object type CLIENT. An object of the type CLIENT is in
one of three states: SA, SB or SC. A client is in state SA when this client did
not send a print job to a server and the servers are not busy with a print job
of this client. A client which is in state SB, wants to have access to a server.
The client can only get access to a server via a semaphore. A client is in state
SC when a server is executing a print job of this client.

A client can make three kinds of state transitions: `SA->SB', `SB->SC',
`SC->SA'. When a client is in state SB, the client can receive a message
"Closed" from the semaphore. After receiving this message the client waits
during a period, the 'Waiting_Period', before the client will again send a
message "Are_you_open?" to the semaphore. When the semaphore sends a message
"Open" to the client, this client changes its state to SC and sends the print
job with a message "S_Job" to the server related to the sending semaphore. This
server then executes the print job. After finishing the print job, the server
will send two messages at the same time, a message "Ready" to its semaphore and
a message "C_Ready" to the client. This client then changes its state from SC to
SA. You can assume that the printers are ideal printers. They will finish each
received print job. For instance there is never the situation `out of paper'.

Communication

In Documentation 3 you find in the
`Communication Structure Diagram' all the message types that can be sent between
the different object types. In the `Message List' you find the specification of
each message type. Each message has an identifier, a sender, a receiver, and
sometimes a content.

When a sender sends a message with the identifier A at time t, then the
receiver will at time t+1 process the message by executing the `Receive
Procedure' A.

If several senders send messages to the same receiver at time t, then the
receiver will process all those messages at time t+1, in the same order in which
the senders of these messages appear in the receiver's `Priority List'.

Subtask A

A Local Area Network (LAN) includes the following objects at
time 0:
Object: CLIENT(1), Client.State = SA, Waiting_Period = 2,
Number_of_Servers= 1

Object: CLIENT(2), Client.State = SA, Waiting_Period = 1, Number_of_Servers=
1

Object: SERVER(1)

Object: SEMAPHORE(1), Semaphore.State = S1

In this LAN there have been sent, among others, the following messages:

At time 1:: CLIENT(1) sends a message with the identifier "Are_you_open?"
At time 2:: CLIENT(2) sends a message with the identifier "Are_you_open?"
At time 4:: SERVER(1) sends a message with the identifier "Ready"
At time 5:: CLIENT(1) sends a message with the identifier "Are_you_open?"

Documentation 4 indicates for SEMAPHORE(1), CLIENT(1) and
CLIENT(2) in a time table up to time 6, which messages these objects receive,
which messages they send, and in which state they are or to which state they
change.

Question A.1

What would have happened if CLIENT(1) receives a message
"C_Job" at time 4? Write your answer in Documentation 5.

Question A.2

What would have happened if CLIENT(2) receives a message
"C_Job" at time 4? Write your answer in Documentation 5.

Question A.3

Complete the timetable in Documentation
4 up to time 13 if the following happens:

At time 8:: SERVER(1) sends a message with the identifier "Ready".
At time l0:: CLIENT(1) receives a message with the identifier "C_Job".
At time 12:: SERVER(1) sends a message with the identifier "Ready".

Subtask B

The LAN is extended. It now includes two semaphore-server
pairs: (SEMAPHORE(1), SEMAPHORE(2), SERVER (1), SERVER(2)). For each CLIENT the
Number_of_Servers equals 2.

To use both printers a change of the definition of the object type CLIENT
described in Documentation 2 is necessary.
In Documentation 6 you find the changed `Receive Procedures':
C_Job and Wait.
In Documentation 6 you also find a
description of the situation at time 0.
At the following times the following
messages are received:

At time 0:: CLIENT(1) receives a message "C_Job" of a user.
At time 0:: CLIENT(2) receives a message "C_Job" of a user.
At time 4:: SEMAPHORE(1) receives a message "Ready".

What happens in the
extended LAN according to the changed object type CLIENT?
Mark the correct
answer in Documentation 6.

Subtask C

The definition change of the object type CLIENT in subtask B
was not efficient for an extended LAN with more than one semaphore-server pair.

Subtask C.1

Change the definition of the object type CLIENT (see Documentation 2) so that the LAN with more than one
semaphore-server pair can function as follows:
An object CLIENT(1) may use
any of the servers in the LAN, but CLIENT(i) can only have one print job
executed at a time by the servers. Each print job of a client is printed only
once.
An object CLIENT(i) sends a message "Are_you_open?" successively to
the several semaphores until a certain threshold value of received messages
"Closed" has been reached or until the object CLIENT(i) receives one message
"Open".
When the object CLIENT(i) reaches the threshold value, the object
CLIENT(i) waits during a certain Waiting_Period before it again sends a series
of messages "Are_you_open?".
Write your solution in Documentation 7.

Subtask C.2

Change the object type CLIENT in such a way, that object
CLIENT(i) now may have several print jobs executed at a time by several servers,
too. However, the number of print jobs of each CLIENT(i) should be limited to
CLIENT(i).Job_Maximum.
Write your solution in Documentation
8.

Documentation 1

Object type: SEMAPHORE

Possible Identifiers:
(SEMAPHORE(1),SEMAPHORE(2),SEMAPHORE(3),...)

State: (S1,S2); initial state is S1.

Priority List: SERVER(1),SERVER(2),...,CLIENT(1),CLIENT(2),...

Communication Diagram

Receive Procedures

procedure Are_you_open?(Client,Semaphore)
begin
   if    State = S1
   then  State <- S2
         Send("Open(Semaphore,Client)")
   else
   if    State = S2
   then  Send("Closed(Semaphore,Client)")
end


procedure Ready(Server, Semaphore)
begin
   State <- S1
end

Documentation 2

Object type: CLIENT

Possible Identifiers:
(CLIENT(1),CLIENT(2),CLIENT(3),...)

State: (SA,SB,SC); initial state is SA.

Priority List: CLIENT,SERVER(1),SERVER(2),...,SEMAPHORE(1),
SEMAPHORE(2),...,USER(1),USER(2),...

Countdown: { t | t in N }; initial value is 0.

Waiting_Period: { t | t in N and t > 0 }

Semaphore_Index: { i | i = 1,2,...,Number_of_Servers }

Number-of-Servers : { i | i in N and i > 0 }

Communication Diagram

Receive Procedures

procedure C_Job(User,Client,Document)
begin
   if    State = SA
   then  State <- SB
         Send("Are_you_open?(Client,
         SEMAPHORE(Semaphore_Index))")
   else
   if    State = SB
   then  Send("Try_later(Client,User,
              Client_is_busy)")
   else
   if    State = SC
   then  Send("Try_later(Client,User,
            All_Servers_are_busy)")
end

procedure Open(Semaphore,Client)
begin
    if    State = SB
    then  State <- SC
          Send("S_Job(Client,Server,
                   Document)")
end

procedure Closed(Semaphore,Client)
begin
   Countdown <- Waiting_Period
   Send("Wait(Client,Client)")
end

procedure Wait(Client,Client)
begin
   Countdown <- Countdown - 1
   if    Countdown > 0
   then  Send("Wait(Client,Client)")
   else  Send("Are_you_open?(Client,
         SEMAPHORE(Semaphore_Index))")
end


procedure C_Ready(Server,Client)
begin
   State <- SA
end

Documentation 3

Communication Structure Diagram

Message List

(i,j,k in N)

identifier        sender          receiver       content
____________________________________________________________
Are_you_open?     CLIENT(i)       SEMAPHORE(j)   -
C_Job             USER(i)         CLIENT(j)      DOCUMENT(k)
C_Ready           SERVER(i)       CLIENT(j)      -
Closed            SEMAPHORE(i)    CLIENT(j)      -
Open              SEMAPHORE(i)    CLIENT(j)      -
Ready             SERVER(i)       SEMAPHORE(j)   -
S_Job             CLIENT(i)       SERVER(j)      DOCUMENT(k)
Try_later         CLIENT(i)       USER(j)        EXPLANATION
Wait              CLIENT(i)       CLIENT(i)      -
____________________________________________________________

Documentation 4

Answer Subtask A.3

Note: This table should be printed in portrait mode.

     SEMAPHORE(1)                          CLIENT(1)                                    CLIENT(2)
    ___________________________________   __________________________________________   __________________________________________
    |received     |State/    |  sent  |   |received| State/   |Count-|   sent      |   |received|  State/  |Count-|   sent      |
    |messages     |Transition|messages|   |messages|Transition| down |  messages   |   |messages|Transition| down |  messages   |
    |_____________|__________|________|   |________|__________|______|_____________|   |________|__________|______|_____________|
time
    ___________________________________   __________________________________________   __________________________________________
 0  |             |S1        |        |   |        |SA        |0     |             |   |        |SA        |0     |             |
    |_____________|__________|________|   |________|__________|______|_____________|   |________|__________|______|_____________|
 1  |             |S1        |        |   |C_Job   |SA->SB    |0     |Are_you_open?|   |        |SA        |0     |             |
    |_____________|__________|________|   |________|__________|______|_____________|   |________|__________|______|_____________|
 2  |Are_you_open?|S1->S2    |Open    |   |        |SB        |0     |             |   |C_Job   |SA->SB    |0     |Are_you_open?|
    |_____________|__________|________|   |________|__________|______|_____________|   |________|__________|______|_____________|
 3  |Are_you_open?|S2        |Closed  |   |Open    |SB->SC    |0     |S_Job        |   |        |SB        |0     |             |
    |_____________|__________|________|   |________|__________|______|_____________|   |________|__________|______|_____________|
 4  |             |S2        |        |   |        |SC        |0     |             |   |Closed  |SB        |0->1  |Wait         |
    |_____________|__________|________|   |________|__________|______|_____________|   |________|__________|______|_____________|
 5  |Ready        |S2->S1    |        |   |C_Ready |SC->SA    |0     |             |   |Wait    |SB        |1->0  |Are_you_open?|
    |             |          |        |   |C_Job   |SA->SB    |0     |Are_you_open?|   |        |          |      |             |
    |_____________|__________|________|   |________|__________|______|_____________|   |________|__________|______|_____________|
 6  |Are_you_open?|S1->S2    |Open    |   |        |          |      |             |   |        |          |      |             |
    |Are_you_open?|S2        |Closed  |   |        |          |      |             |   |        |          |      |             |
    |_____________|__________|________|   |________|__________|______|_____________|   |________|__________|______|_____________|
 7  |             |          |        |   |        |          |      |             |   |        |          |      |             |
    |             |          |        |   |        |          |      |             |   |        |          |      |             |
    |_____________|__________|________|   |________|__________|______|_____________|   |________|__________|______|_____________|
 8  |             |          |        |   |        |          |      |             |   |        |          |      |             |
    |             |          |        |   |        |          |      |             |   |        |          |      |             |
    |_____________|__________|________|   |________|__________|______|_____________|   |________|__________|______|_____________|
 9  |             |          |        |   |        |          |      |             |   |        |          |      |             |
    |             |          |        |   |        |          |      |             |   |        |          |      |             |
    |_____________|__________|________|   |________|__________|______|_____________|   |________|__________|______|_____________|
10  |             |          |        |   |        |          |      |             |   |        |          |      |             |
    |             |          |        |   |        |          |      |             |   |        |          |      |             |
    |_____________|__________|________|   |________|__________|______|_____________|   |________|__________|______|_____________|
11  |             |          |        |   |        |          |      |             |   |        |          |      |             |
    |             |          |        |   |        |          |      |             |   |        |          |      |             |
    |_____________|__________|________|   |________|__________|______|_____________|   |________|__________|______|_____________|
12  |             |          |        |   |        |          |      |             |   |        |          |      |             |
    |             |          |        |   |        |          |      |             |   |        |          |      |             |
    |_____________|__________|________|   |________|__________|______|_____________|   |________|__________|______|_____________|
13  |             |          |        |   |        |          |      |             |   |        |          |      |             |
    |             |          |        |   |        |          |      |             |   |        |          |      |             |
    |_____________|__________|________|   |________|__________|______|_____________|   |________|__________|______|_____________|

Documentation 5

Question A.1

Question A.2

Documentation 6

Subtask B

The changed `Receive Procedures': C_Job and Wait.

Note: The changed code is made italic in this page.

procedure C_Job(User,Client)
begin
   if     State = SA
   then   State <- SB
          for   Semaphore_Index <- 1 step 1 until Number_of_Servers
                Send("Are_you_open?(Client,SEMAPHORE(Semaphore_Index))")
   else
   if     State = SB
   then   Send("Try_later(Client,User,Client_is_busy)")
   else
   if     State = SC
   then   Send(,Try_later(Client,User,All_Servers_are_busy)')
end

procedure Wait(Client,Client)
begin
  if      State = SB
  then    Countdown <- Countdown -1
          if       Countdown > 0
          then     Send("Wait(Client,Client)")
          else
          if       Countdown < 0
          then     Countdown <- 0
          else     for  Semaphore_Index <- 1 step 1 until Number_of_Servers
                        Send("Are_you_open?(Client,SEMAPHORE(Semaphore_Index))")
end

At time 0 the situation in the LAN is as follows:
Object: CLIENT(1),
Client.State SA, Waiting_Period = 2, Number_of_Servers=2
Object: CLIENT(2),
Client.State SA, Waiting_Period = 1, Number_of_Servers=2
Object:
SEMAPHORE(1), Semaphore.State = S1
Object: SEMAPHORE(2), Semaphore.State =
S1
At the following times the following messages are received:
At time
0: CLIENT(1) receives a message "C_Job" of a user.
At time 0: CLIENT(2)
receives a message "C_Job" of a user.
At time 4: SEMAPHORE(1) receives a
message "Ready".
What happens in the extended LAN according to the changed
object type CLIENT?

Mark the correct answer.

(a): The print job of CLIENT(1) will be printed on SERVER(1) and SERVER(2).

The print job of CLIENT(2) will not be printed.
(b): The print job of CLIENT(1) will be printed once on SERVER(1).
The print
job of CLIENT(2) will be printed once on SERVER(2).
(c): The print job of CLIENT(1) will be printed once on SERVER(1).
The print
job of CLIENT(2) will be printed once on SERVER(1).
(d): The print job of CLIENT(1) will be printed once on SERVER(2).
The print
job of CLIENT(2) will be printed once on SERVER(2).
(e): The print job of CLIENT(1) will not be printed.
The printjob of
CLIENT(2) will be printed on SERVER(1) and SERVER(2).

Documentation 7

Subtask C.1

______________________________________________________

______________________________________________________

______________________________________________________

______________________________________________________

______________________________________________________

______________________________________________________

______________________________________________________

______________________________________________________

Task: Printing

Client and Server

Semaphore

Object type SEMAPHORE

Object type CLIENT

Communication

Subtask A

Question A.1

Question A.2

Question A.3

Subtask B

Subtask C

Subtask C.1

Subtask C.2

Documentation 1

Object type: SEMAPHORE

Communication Diagram

Receive Procedures

Documentation 2

Object type: CLIENT

Communication Diagram

Receive Procedures

Documentation 3

Communication Structure Diagram

Message List

Documentation 4

Answer Subtask A.3

Documentation 5

Question A.1

Question A.2

Documentation 6

Subtask B

Documentation 7

Subtask C.1

Documentation 8

Subtask C.2