Algorithm 版 (精华区)
发信人: Lerry (想不开·撞树), 信区: Algorithm
标 题: Task: Printing
发信站: 哈工大紫丁香 (2002年03月29日13:29:17 星期五), 站内信件
Task: Printing
Note: This page is converted with a scanner, so it might contain small error
s.
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 p
rinters named SERVER(1), SERVER(2) and so on. The print jobs from both compu
ters can only be executed in succession. To coordinate the communication bet
ween 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 mess
age "Are_you_open?" to the semaphore. If the state of the semaphore is S1, t
hen 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 "Re
ady" 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 SEMAPH
ORE. The specification includes the possible identifiers and the states of a
n object of the type SEMAPHORE, the `Priority List', the `Communication Diag
ram', the `State Transition Diagram', and the 'Receive Procedures' for the m
essages: "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 s
ame time by a semaphore can only be handled in succession. The `Priority Lis
t' in Documentation 1 indicates that each message of a SERVER has a higher p
riority 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 cl
ient is in state SA when this client did not send a print job to a server an
d the servers are not busy with a print job of this client. A client which i
s in state SB, wants to have access to a server. The client can only get acc
ess to a server via a semaphore. A client is in state SC when a server is ex
ecuting 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" t
o the client, this client changes its state to SC and sends the print job wi
th a message "S_Job" to the server related to the sending semaphore. This se
rver 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 fr
om 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 `o
ut 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 rece
iver will at time t+1 process the message by executing the `Receive Procedur
e' A.
If several senders send messages to the same receiver at time t, then the re
ceiver will process all those messages at time t+1, in the same order in whi
ch 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 tim
e table up to time 6, which messages these objects receive, which messages t
hey 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 hap
pens:
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_Serv
ers equals 2.
To use both printers a change of the definition of the object type CLIENT de
scribed 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 efficie
nt 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 tha
t 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 o
f a client is printed only once.
An object CLIENT(i) sends a message "Are_you_open?" successively to the seve
ral 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 mess
ages "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 h
ave 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).Jo
b_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-| sen
t | |received| State/ |Count-| sent |
|messages |Transition|messages| |messages|Transition| down | mess
ages | |messages|Transition| down | messages |
|_____________|__________|________| |________|__________|______|______
_______| |________|__________|______|_____________|
time
___________________________________ __________________________________
________ __________________________________________
0 | |S1 | | | |SA |0 |
| | |SA |0 | |
|_____________|__________|________| |________|__________|______|______
_______| |________|__________|______|_____________|
1 | |S1 | | |C_Job |SA->SB |0 |Are_yo
u_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_yo
u_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
What would have happened if CLIENT(1) receives a message "C_Job" at time 4 ?
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
Question A.2
What would have happened if CLIENT(2) receives a message "C_Job" at time 4 ?
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
----------------------------------------------------------------------------
----
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
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
----------------------------------------------------------------------------
----
Documentation 8
Subtask C.2
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
______________________________________________________
--
不在乎天长地久，就怕你从来没有！
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]
Powered by KBS BBS 2.0 (http://dev.kcn.cn)
页面执行时间：204.332毫秒