![[ IOI Home page ]](../logo.gif){kind=logo}
Task: Printing Task: PrintingA 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.
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).
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'.
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'.
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:
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:
State: (S1,S2); initial state is S1.
Priority List: SERVER(1),SERVER(2),...,CLIENT(1),CLIENT(2),...
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
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 }
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
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) - ____________________________________________________________
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 | | | | | | | | | | | | | |
| | | | | | | | | | | | | |
|_____________|__________|________| |________|__________|______|_____________| |________|__________|______|_____________|
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:
Mark the correct answer.