0 I t=0 ID=1 sent_at=0 from=3 to=3 priority=0 0 S t=0 ID=2 sent_at=0 from=0 to=1 priority=0 val=3 0 S t=0 ID=3 sent_at=0 from=0 to=2 priority=0 val=3 2 R t=1 ID=3 sent_at=0 from=0 to=2 priority=0 val=3 2 S t=1 ID=4 sent_at=1 from=2 to=0 priority=0 val=2 2 S t=1 ID=5 sent_at=1 from=2 to=1 priority=0 val=2 1 R t=1 ID=2 sent_at=0 from=0 to=1 priority=0 val=3 1 S t=1 ID=6 sent_at=1 from=1 to=0 priority=0 val=2 1 S t=1 ID=7 sent_at=1 from=1 to=2 priority=0 val=2 2 R t=2 ID=7 sent_at=1 from=1 to=2 priority=0 val=2 2 S t=2 ID=8 sent_at=2 from=2 to=0 priority=0 val=1 2 S t=2 ID=9 sent_at=2 from=2 to=1 priority=0 val=1 0 R t=2 ID=6 sent_at=1 from=1 to=0 priority=0 val=2 0 S t=2 ID=10 sent_at=2 from=0 to=1 priority=0 val=1 0 S t=2 ID=11 sent_at=2 from=0 to=2 priority=0 val=1 1 R t=2 ID=5 sent_at=1 from=2 to=1 priority=0 val=2 1 S t=2 ID=12 sent_at=2 from=1 to=0 priority=0 val=1 1 S t=2 ID=13 sent_at=2 from=1 to=2 priority=0 val=1 0 R t=2 ID=4 sent_at=1 from=2 to=0 priority=0 val=2 0 S t=2 ID=14 sent_at=2 from=0 to=1 priority=0 val=1 0 S t=2 ID=15 sent_at=2 from=0 to=2 priority=0 val=1 2 R t=3 ID=15 sent_at=2 from=0 to=2 priority=0 val=1 1 R t=3 ID=14 sent_at=2 from=0 to=1 priority=0 val=1 2 R t=3 ID=13 sent_at=2 from=1 to=2 priority=0 val=1 0 R t=3 ID=12 sent_at=2 from=1 to=0 priority=0 val=1 2 R t=3 ID=11 sent_at=2 from=0 to=2 priority=0 val=1 1 R t=3 ID=10 sent_at=2 from=0 to=1 priority=0 val=1 1 R t=3 ID=9 sent_at=2 from=2 to=1 priority=0 val=1 0 R t=3 ID=8 sent_at=2 from=2 to=0 priority=0 val=1
When sending a message, the distributed algorithm specifies the priority of the message. If two messages arrive to one processor at the same time, the message with the higher priority is processed first.
A message with priority of 1, has the highest priority, as the number increases, the priority is lower.
The source is processor 0, and destination is the processor ID that receives the message.
The number 10 is sent in the first message(s).
An algorithm can send messages to the neighbourhood in a different way. Some algorithm send a message to all, some just return a message to the sender, and some do other things.
The rules are:
- If you have two messages to be recieved on the same time, start with the smaller "sender".
- If you have to send messages to all, start sending from the smaller to the bigger.
You can choose.
The message is generated by the simulator at the initialization time.
The "start messages" are initiate messages.The dist. alg. "knows" what to do if it recieve an "init" message or a regular one.
You should stop the run.
The structure is given in the spec.
The numbers are seperated by spaces, like 1 4 7 9 5 23
The end of the line is the end of the list
The program should free ALL the memory it used before exiting - for any reason.
The message data field has a value named token (like a field in a structure). You will have the value of the "token" field by masking the message data field. Suppose we will want to deliver in the message the name of the sender, the string "hello" and a randomally number, then our message will have 3 fields in it:
- processor_number
- our_dummy_string
- rnd_number
The processor has internal variables, which can be put (should be put) in the "state" struct.
Each algorithm will mask the struct according to its needs. Remember - the simulation only supplies a way of running EVERY DISTRIBUTED ALGORITHM which answer our definition : SEND, RECIEVE and more.
# The first number is the number of nodes
2
# an optional comment
# list of edges till we reach the end of the file
# Every edge in a single line, there can be any number of spaces between
# the numbers
# The format of an edge is like that:
# <processor 1> <processor 2>
<delay>
1 2 5
The simulator program receives only one parameter in the command line (argc,v), which is a file name with the following format:
# Topology file
network1.top
# algorithm to run
# the countdown algorithm
# 1 - countdown
# 2 - flood
1
# Data structure
# 1 - Heap
# 2 - Lined list
# 3 - Hash
1
# Initialization nodes (list of processors that receive an init message)
# one or more numbers in a single line, any number of spaces or tabs
# between numbers is allowed.
# The end of the line is the end of the input.
3
# Log file name
countdown.log
# Final status log file name
countdown.flg
No.
Yes.
No. Write down the place on the hardcopy.
1) each line is what we expect it to be.
2) the topology file name is leagal, and the file exists.
3) the algorithm number exists and in range 1 - 20, and only one number.
4) the data structure exists and in range 1 - 3, and only one number.
5) there is at least one initiator, and the processors exist in the network.
6) the log file name is leagal.
7) the status file name is leagal.
8) it can be possible to ask to run an algorithm which is not yet implemented,
i.e. its number has no algorithm implementation.You may add other things.
Among other things, you should check:
1) there is a 1st line containing the number of the processors.
2) the number of network processors in the topology file is exactly as in the
1st line.
3) there are exactly 3 numbers (or 2 numbers and * or ?) in each data line.
4) there are no bi-defined links.
5) all processors names are leagal (positive, not 0)
6) all delays are leagal (positive, not 0)
7) you SHOULD NOT check if the network is connected, and so.
The sim.h file defines an interface between the algorithm and the simulator. You do not need to change your data structures.-------
Suppose you had
struct CPU
{
int CpuNumber;
List of Neighbours;
};change it to
struct CPU
{
int CpuNumber;
List of Neighbours;
PROCESSOR* processor_info;
};At initialization time, after you've read the input file, initialize the processor_info for every processor.
Another comment: The algorithm may not send a message to all of its neighbours. For example if we have a topology where CPU 1 is connected to 2 and 2 is also connected to 3, 4 and 5.
An algorithm can decide to send a message from CPU 1 to 2, the message will tell 2 to forward that message to 3.
Q: In page 4 it says that we need to write the number of messages in
the
receive queue in the file of the processor?s final state.
How can a queue still have messages at the end ?
A: Well, this can be a BUG in your program, and this information will
discover it.
Ofcourse, you can write the number 0, but if you do so,
you should
convince us why the queue is ALWAYS empty when the algorithm
ends.
Q: From what we know from data structures, a heap is a natural way
for implementing a queue. But what about a linked list
?
Does it need to be sorted ?
Is a linked list + a pointer to the end and a pointer
to the
beginning considered a linked list ?
A: The linked-list implementation method is up to you.
We do not demand it to be sorted, pointered or so, ONLY
to be a linked
list (i.e. cells with data, each cell pointing at least
to the next cell
in the list).
Q: I am not going to do any usage of the # mark.
Do I still have to check it ?
A: Yes.
Q: In page 3, it says we need to keep track of the global number of
messages in our net. What usage does it have ?
A: When one wants to read the output and analyze the complexity of
the
solution, it needs this numbers, and other.
This is one of the output of the simulation.
Q: In page 3, it says that a message structure must have a message
number (integer). What usage does it have ?
A: For tracking all messages.
Q: In page 3, it says that we need to write in the log file the content
of the message according to the appropriate data structure.
Do you mean the data structure used for the queue like
heap, hash ?
A: No.
We mean the content of the message, like "token = 3" and
more.
There will be algorithms which will deliver strings and
integers.
Look at the sim.h and sample flood.c for how to do that.
Q: In page 2, it says that a file with the final state of the processors
will be given as an argument to distsim. Why do we need
it if all the
processors are supposed to be in idle state ?
A: Again, this can help debbuging.
If you can convince us that in your implementation all
processors ARE
idle, then you can save some code. But, the checker should
be convinced.
Q: In page 2, it says that the set of the starting vertexes will be
given as an argument. Does it include the leader ? Do
we always
have a leader ?
Does the leader responsible of returning the result of
a calculation ?
A: I think there is some confusion here.
We gave you the "find a leader" problem as an example
of distributed
algorithm in real life.
There is NO leader in the net.
The starting processors are those your program send them
the initial
message.
Q: Your processor structure contains an array of neighbors, without
delay values. It seems like a mistake, not to mention
the fact that
it seems more natural to hold this list in a linked list.
A: The processor should not know, and (infact) it doesn't care the
delay
for each one of his neighbours, so, there is no mistake.
The use of an array is more convinient in many cases,
and you will have
some of them in the next algorithms to be implemented.
Q: How should we determine a messgae priority (in case 2 messages get
to the same
cpu in the same time) ?
Can we have the priotiry as it's I.D. or sending time
?
(Then - a lower number is a higher priority)
A: The priority is part of the message structure. Please read carefully
the
project definition.
Also, have a look at the sample flood.c
Q: How should we determine a messgae priority (in case 2 messages get
to the same
cpu in the same time) ?
Can we have the priotiry as it's I.D. or sending time
?
(Then - a lower number is a higher priority)
A: The priority is part of the message structure. Please read carefully
the
project definition.
Q: In the cpu's status file, What does 'name of variable 1' &
'value of variable 1' are ?
A: Well, think of an example in which the algorithm uses some internal
variables
named "in_msgs" and "out_msgs", which are of short type,
and each processor
counts how many messages it gets and delivers.
In this situation, you should write:
...
in_msgs
23
out_msgs
482
...
In the first algorithm (the cuntdown) there is a variable named token with values from 10 to 1
Q: In the checking program - can we store each of the lines read from
the
log file in memory as a structure, or should we just use
the file
without building a structure in memory ?
A: You should choose what is the most convinient way for you.
Q: A cpu's name is of type int or type DW (r.e. unsigned long),
or can we chhange this ?
A: type DW.
Please follow the sim.h file for related questions.
Q: Should we use 'const' and 'static' as often as we can, or is this
not
that important ?
A: You should use them according to what you have learned in previous
courses. Note that const is not part of ANSI C, only C++.
Q: Each line in the network topology file is consists of 3 numbers,
so I
am having an array of 3 int's to read the line into it.
Should this 3 be a constant defined somewhere, using #define,
or can I simply define : int numbers[3] ?
A: The way you are handling the inside information about the network
topology
is your decision. (#define is not related).
Just remember that we can have a '*' in the triple of
the input line...
Q: In addition to the last question, We read each line as a string and
getting the numbers using : sscanf("%d%d%d", ...);
Is it modulaar enought for this purpose or should we do
something else ?
A: This is an implementation question. We cannot answer such questions.
Sorry.
Q: Is it possible to work in the checking program with Unix commands
like
grep,pipe and sort ?
A: Yes you can.
Q: Is it o.k to assume that in a legal log (or input ) file every data
object is
seperated by one space only?
A: No.
Q: Do init messages have id number?
A: Ofcourse. They are treated like any other message.
Q: Why dosn't the processor structure have a pointer to his queue of
messages? can I add it?
A: The processor does not handle his messages. Only the simulation
program does it.
The processor only uses the SEND & RECIEVE functions
in order to get/send
messages.
Having such a pointer will break the concept of the network.
You can have your own Processor structure that will contain
the PROCESSOR_INFO structure.
Q: A request for a delay is being made by the students, because of the
strike and
the changes that were made in the code.
A lot of people have questions on the project.
A: You will all get a delay of ATLEAST 2 weeks, due to the strike.
Please treat the strike as "no time", and you also get
an extension for it, so
along with it do remember that the definition files were
published just when the
strike ends. Think of it as they were published 2-3 days
after the 2nd meeting.
and again, as was told in class, the simulator MUST NOT
know nothing about the
algorithm code, and the algorithm should use the SEND,
RECIEVE and
other global functions/variables and no more.
Any other interaction beween those two is forbiden.
The headers of SEND & RECIEVE were supplied before,
and the use of the
global variables should not cause much trouble for you
(on the contrary).
There are some ways to implement the algorithm, so do
not "stick" to our
suggestion, BUT, the written in SIM.H file, is a MUST.
Q: You wrote that each algorithm should be linked to the simulator.
If
the functions InitAlgorithm() and PrintState() are extern
(like you
did in your flood.c), it's not possible to link more than
one
algorithm. What should we do - use those functions in
the algorithm
function (and make them static), or anything else ?
A: Write the different algorithms like that:
First algorithm
InitAlgorithm1(...) {...}
PrintState1(...) {...}
FormatMessage1(...) {...}
Algorithm1(...) {...}
Second algorithm
InitAlgorithm2(...) {...}
PrintState2(...) {...}
FormatMessage2(...) {...}
Algorithm2(...) {...}
etc.
Q: Can we use global variables as used in 'sim.h' (your example) but
have
my_neighbors defined as a linked list ?
We did the neighbours list of each processor as
linked list. is it ok?
Is the data structure we have to use is, as implied in
the header file, an
array of processors with an array of neighbours in each
of them.
Is it allowed to change the neighbors array to be struct
of neighbors and
delay.
A: When asking of using adjacancy matrix instead of adjancancy lists,
We have
the feeling that you are a liitle bit confused.
The array (neighbours) in the processor data, is about
to hold only a copy
of the network topology, related to that processor, i.e.
only the list of
processors who are connected to that processor,so we will
be able to know of them,
(as was told in class).
The processor SHOULD NOT know / touch / relate to the
whole network
topology, because it is the simulation knowledge. This
data is hidden for the
processor.
The processor who sends the message, MUST NOT know of
the delay.
Only the simulation manager knows about it, and deals
with it during the
SEND function. (Try to think of the real life, does you
computer knows the
delay in the internet ? Do you know of the delays of the
line when you speak
on the cello-phone ?)
It seemed to me that you mistakely thought we wanted you
to have the
network topology implementation as an array, and this
is NOT THE SITUATION !
We only wanted an internal variable in the processor,
for holding the
knowledge of its neighbours. And for this, an array is
the simplest solution.
Q: How can I use the priority value in my hash function ?
A: You can easily think of a function which, for t=t0, will get the
smallest
item according to the minimum between the priority and
the processor number.
There are other ways to implement it.
Another tip : Please read the next publications in the
F&Q regarding this
issue.
Q: Can the send function get the parameters: send(message
*mes, processor *where)
"
receive "
" "
: receive(message *mes, processor *who)
A: You can find the headers for those functions in the WORD file you
got on class
and more specific template in the sim.h file, in the homepage.
There is no reason at all for the processor parameter
in the recieve function,
because the processor run this function, and it is the
simulation manager job to
return the right message. You do not pass on all your
neighbours, and what more
important, the processor does not know from where the
message is coming before
it reads it using the recieve function.
Q: We implemented message structure exactly according to what we've
read in 4 pages,
and we also added one more feild with arrive time. But
the structure of the
message in your H files is different:
What is message_size and what for? Can we keep
our structure?
A: You should use the template in the sim.h file.
Message_size is the number of byte holding the message
information.
Q: Tomorrow, there'll be a lecture, right?
A: Wrong !
As was told in class, there will be no more lecture unless
we will put a note on
the student board, and put a remark in the homepage.
It was said more then 3 times in each of the 1st and 2nd
lectures.
And ... Is it also written in the homepage. Please read.
Q: You say that you'll give us additional 2 weeks, but these 2 weeks
are right at
the beginning of examination session and submition other
projects of other courses,
so you understand that these 2 weeks are not even close
the those 2 weeks during
the strike, when we could dedicate ourselves to
the project and enjoy not
having much pressure. So you can't say that we
should just ignore the strike,
like it never was. And what about all the
effort we made in writing the project
by ourselves and making it work?!?
A: You will have 2 weeks of extension due to the strike.
You cannot hold the rope from both sides.
First, you said that during the strike you couldn't work,
because there were no
computers and so, so you want the extension for the time
you couldn't work.
Then, you said that you worked all those 2 weeks, and
then saw the templates, and
thus wasted your time, and you want an extension for that.
The templates were published about 3 days after the 2nd
lecture, in which I told
you that there will be headers we will supply.
That time, the strike begun, so you couldn't see those
templates.
Nevertheless, if you will read them carefully, you will
see that those templates
are a "common sense", and do not demand any BIG change
in a project that was
implemented well, under the spec description. (the processor
should know nothing
about the topology, the processor should know nothing
about the simulation manager,
the processor will use a SEND & RECIEVE functions
to deal with messages, and other
things that were told you in class and are writen in the
spec.
The use of the global variables like "my_number", "my_neighbours"
and so, what
difference does it make their name ? If you called them
some other name, just
change it. If you used the network topology, then you
are wrong, and this is the
time to correct it.
Q: When writing to the log file, we should write the first 4
lines from the input file, if these lines were with comments,
should we
print the comments as well and include then in the 4 lines
counting?
A: Please read again your question.
By saying that the log file should have the first 4 lines,
we ment that
the log file will have the first "meaningfull" lines,
which are important
to your checking program. Those lines holds the topology
file name, the
name of the starting processors, the name of the chosen
algorithm and so.
Do you really though that this is a bizare wish, to have
4 dummy lines ?
Q: There are two types of messages which is correct? one is in the spec
and
the other is in the sim.h example.
A: Take this as a rule:
The spec, was given to you in class. It has a general
information in it.
The F&Q file and other sections in the homepage, can
OVERRIDE the spec.
An issue with date later then other issue, is the issue
you should follow.
Q: Can the input file contain blank lines without # in the beginning
?
Can I assume something about the length of
each line in the input file
in order to capture it with fgets ?
A: In order to help you with that, the # sign should appear in the
beginning of the
line.
The maximum line lenght is 255 characters
(i.s. a normal string).
Q: Why do I need the PROCESSOR_INFO struct, if I can find all the
relevant data I need in my net construction
? (We just repeat the same
details....)
A: There is a "wall" between the processor and the simulation knowledge.
The processor MUST know NOTHING of the network
topology, he can only
know of his name, and of his neighbours' names.
-------
9-6-99
-------
Q: Can the input file contain blank lines without # in the beginning
?
Can I assume something about the length of each line in
the input file
in order to capture it with fgets ?
A: In order to help you with that, the # sign should appear in the
beginning of
the line.
The maximum line lenght is 255 characters (i.s. a normal
string).
Q: Why do I need the PROCESSOR_INFO struct, if I can find all the
relevant data I need in my net construction ? (We just
repeat the same
details....)
A: There is a "wall" between the processor and the simulation knowledge.
The processor MUST know NOTHING of the network topology,
he can only
know of his name, and of his neighbours' names.
Q: Do we have to check if the system, according to the topology file
is
"kshira"?
I already did that. shall I remove those checks?
A: You should not check for it, and we will not ask you to.
If you already did it, then you can leave the code. It
doesn't matter.
Q: In the FAQ it says that I have to detect a delay of * or ?, but it
doesn't say what I should do with it. Detecting these
special characters
really complicates the reading, so unless you're going
to make us use
them, making us read them seems pointless ( especially
that we don't know
what to do with them when they are read so the program
cannot work until
then... )
A: You should detect the appearence of the * character as a delay.
While finding such character, you should choose a random
delay of 1-50.
This delay will not be changed again.
Q: Are you going to check our programs with additional algorithms?
If "yes" it is the reason we have follow your header file.
If "no", do we have?
A: Ofcourse, or Yes, we will do so. Think of your simulation
program as a general compiler.
Q: There are many answers about using C++. I did not understand which
is
the last one : can we use C++??
A: Yes you can.
Q: Is there no practical need to implement the Idle & awake states
of
the cpu's? (you said we need'nt)
A: If your program can easily decide in which state is each processor
at the end of the run, then it is fine with us.
You should ofcourse describe it in your documentation.
Q: Is it correct that "Send" makes duplicates of the message sent by
the given parameter ? (we guess it's correct)
A: We can accept both ways:
1) The send function do duplicate the message for each
reciever.
2) The algorithm itself does it.
You should explain your choice in the documentation (in
the relevant
part which explains how to add an algorithm to the simulation),
and also should explain why you choose this implementation.
Q: Please publish the function that let us duplicate the message buffer
that has to be done in "Send". It has to make a duplicate
of (void *),
according to our meetings with Shachar.
A: This is an implementation problem. You should discover it by your
own.
Q: Is the web-page update, regarding the due-day is the last one, or
the
"HATKALA" & the posteponement regarding to it is still
to come ?
A: There is no "HATKALA" in the homepage. (8/6/99).
Q: Should we randomally choose a delay each time we send a message (for
a
random delay link) or choose the delay randomally in the
initialization
of the network such that each time we send a specfic link
it would be
the same?
A: As it is written, you should choose the delay randomally only once
you
are reading the topology file. i.e. in the initialization
phase.
Q: First you said that we can choose if every cpu has its own queue
or
there is a queue for all messages in the net.
Second you said that having a pointer to its messages
by a cpu will
break te concepts of the network.
What statement sould I consider? (I want that every cpu
will keep a
pointer to its messages)
A: First part & Second part are true, and are not related.
As for your question, you should not access none of the
network data
implementation inside the processor (i.e. in the algorithm).
The algorithm should use who_am_i, my_neighbours, send,
recieve and
so in order to operate.
There is no need for a pointer from the cpu to its messaages,
and,
this is even forbiden.
Q: In case we read '*' from the topology file, can we insert '0' to
the
field delay in our cpu struct (knowing that delay is greater
than 0,
according to the FAQ) ?????
A: Please read the file ALGORITHMS.RTF and you will have the answer.
Q: Are names of the processors between 1 and n , where n is number of
processors in the net ?
A: No, the names of the processors are numbers which are not have to
be
consequtive.
Q: Where do we suppose to hold the data structure for algorithms 3&4?
there are specific information (parent, array of sons,
firstmsg
etc.) that the flood and token don't need.
A: Woooo...
Read this very carefully:
Each algorithm is a unique algorithm, which has its own
initialization
function and its own internal variables.
The simulation runs each algorithm alone, and will run
only one
algorithm at a time.
The data structures for the algorithms should be stored
in the
cpu variables, but keep in mind that this will be changed
from
different algorithms.
Q: In which of the algorithms(1-4) the priority field in the messages
is
relevant?
who determines the priority for each message?
A: In none of them.
There are some algorithms that will deal with it.
Q: What about the Print_State and Algorithem_Init for algorithms 3&4?
We thought that in Print_State we should put the number
of msg the
cpu got back, and that Algorithem_Init should go over
all the cpus
and update NumRcvd = 0, FirstMsg = TRUE.
Is it ok? do we need more or something else?
A: This is an implementation question.
The pseudo code was only a suggestion. (though it is a
good one !)
Q: I used the function memcpy() in send() to duplicate
the buffer of a message in memory. The thing is we didn?t
mention it at software1 course, and I discovered it by
accident
when browsing in turbo c help. Are there any alternatives
?
A: memcpy is a fine choice.
Q: Just for the completeness of my project, I need to know for
sure what do I have to print to the log file when I get
an init
message - what is the global time of sending (0 or 1?),
who
is the sender (the receiver ?) and what is the priority.
A: The first time tage is 1.
The sender is 0. (the simulation).
The reciever is the reciever.
The priority is 1.
Q: Could there be an algorithm which doesn?t feed the priority
field of a message ? What is the default priority (is
it 5?) ?
A: None of the given 4 algorithms use the priority field.
The default value is 1.
Q: Is the first message of all messages has serial number 1 or 0?
A: The counter starts at 1.
Q: When using a hash for the queue1, I have a funny situation -
If I dequeue it, I might find that the message I got has
a later
arrive time than the current global time, so I do global_time++,
enqueue the hash queue, and then try my luck again.
This is can be a very expansive idea in terms of complexity.
Are there any chances to solve it ?
A: You can choose another (and better) hash function.
Q: I used a global message queue (one for all the processors).
Isn?t it quite silly to print how many messages are left
in
the message queue for e a c h processor (in the final
state of
processors? file)
when I?m 100% guaranteed that when I finish my simulation
There are no messages for no one. (My simulation loop
ceases to
run when empty(&message_queue) , so I cannot be wrong).
A: It is not silly, because we have asked for it.
If you are so sure, you can explain it in the documentation.
But, the number of left messages should appear, or your
file will
not be in the proper format ...
Q: Is it ok to hold a global pointer to a message that will
point to the last message that has been dequeued ?
I mean - I have no way to know which processor will be
the next one to be awake, so I must dequeue the queue,
look at the receiver, and only then I know.
A: It is an implementation question, BUT, pay attention that we have
asked you to use some data types in order to hold the
messages.
Please do not add some "strange" things to the types,
which will
destroy your implementation...
Q: About the 16 "missing algorithms":
Do I have to create 4*16=64 ! prototypes and dummy functions
?
And if so, Should they reside in sim.h ?
A: Regarding sim.h, it is OUR filename, I really do not know what
filename you used.
and, yes, you should create those dummy functions, or,
if you
can think of other way to compile your project without
warrnings,
then it is acceptabel too. (even beter).
Q: And as a continuation to the last question - can I change
or add to sim.h (Not essentially), but minor changes ?
For example, can I split it and create message.h where
the message struct definition will reside ?
A: Again, sim.h is OUR file, which we gave you some definitions in
it.
you can put those definitions in any other file.
Q: I had no way other than using a pointer of type t_format_message
as a global variable. This is because send() and receive()
use the
format message function, whereas they do not get it as
an argument
Is there any other way ? (by now, I have too many global
variables)
A: Again, a specific implementation question.
Q: I think I didn?t understand countdown. Does every processor
have a variable token in his void *my_state ?
I managed to write countdown without using the token,
and I
don?t see why I need. Correct me if I?m wrong -
If I have two processors 1 and 2 and 1 is an
initial node, 1 sends 10 to 2, 2 sends 9 to 1,
1 sends 8 to 2,.... until someone sends 1 to the
other and the algorithm stops. But the I haven?t
used any token - each value that was passed was
stored only in the message->buffer.
A: token is the field in the message, which holds the sent data.
we did say nothing about the algorithm variables.
Q: In the project updates document that lists the 2 new algorithms,
in both of the algorithm specifications it says that "parent"
and
"sons" should hold the ID of a processor, that is -- a
DW. But it
also says that we need to initialize them to -1. And here
comes
the point -- We can't assign a negative value to a DW-type
variable!
So, what shall I do?
A: We never said "sons" will hold the processor id. read again.
Regarding the "parent", you are right, please initiate
it to INVALID_PROCESSOR_ID.
---------------------------
14-6-99
---------------------------
Q: Algorithms 3&4 : node struct contains an element : NumNeighbours
which already exists in the processor_info struct, is
this
necessary ?
A: The code in alrotihms.rtf is only a pseudo-code, designed to explain
the
algorithm and is not an implementation.
This is only a suggestion to some implementation in order
to make
it more clear for you.
You have both the hebrew description and the pseudo-code
description,
and now, all you have to do is to take this and write
the C code of it.
Q: Where do we update the name of the buffer used in each algorithm,
for example : Token or Mode (for algorithms 3&4).
A: It seemed that you are still confused.
EVERY TIME WHEN THE SIMULATION PROGRAM WILL BE RUN, THE
END USER
CHOOSES ONLY ONE ALGORITHM TO BE RUN.
SO, EACH ALGORITHM HAS ITS OWN DATA STRUCTURE AND HIS
OWN INNER
VARIABLES, AND IT IS RESPONSIBLE FOR UPDATING IT.
THE ONLY THING WHICH IS COMMON TO ALL ALGORITHMS IS THE
PROCESSOR_INFO VARIABLE.
Q: In algorithm 3&4 : We need to check if the current processor
is
an initiator, doesn't this ruin the abstraction of the
program -
since the algorithms access the net topology.
A: Well, again, THIS IS A PSEUDO CODE !!!
THIS IS NOT YOUR C IMPLEMENTATION !!!
You should read this, and according to the hebrew description
and
the information you understand from the pseudo-code, you
should
understand what is wanted from you to implement.
Q: In algorithm 4 we need to hold the 'next neighbour' of each
processor (to which we send messages), should we add this
variable in
the node struct, and not access it in algorithm 3, or
should we create a
new struct ?
A: Again, EACH ALGORITHM HAS ITS OWN VARIABLES.
For an example, algorithm 3 does not know of the existence
of algorithm 2,
and does not know of the inner variables, cause they exist
only in the
code of algorithm 2.
Consider the simulation program as an entire environment
for compiling,
linking and running C algorithms, BUT we will give you
the algorithms
to be compiled, linked & run.
Now think of the Visual Basic environment, or the Linux
C envirunment,
you can write 400 different Basic / C programs, and then
run them on
the "compiler-linker-run" environment. You do this for
each program
seperately. ONce you write this project, then you write
your data-base
project, then you write the operating-systems project
and so.
Does any of those algorithms know nothing about the other
? Ofcourse not !
They all indevidual.
This is the case in our simulation.
Each distributed algorithm stands for itself.
We anly gave them to you together, so you will be able
to know that we
want you to implement them. But you should implement them
seperately !
Q: What should the names of the remaining algorithms be (5-16) ?
A: You will decide it. Just remember to tell us your method, so we
will be
able to replace them with our algorithms.
Q: What is the input to the test program? I belive I saw it defined
once,
but I can't find the location now...
A: The test program will accept one parameter : the log file name.
As you remember, the first lines of the log file contain
some information
regarding the run, such as the topology file name and
other, so the test
program can use it.
Q: I build the network twice. Once in distsim, and then in distchk.
The problem is that in the second time I cannot guess
how ?*? were
interpreted in distim, and therefore I cannot check delays
as wished.
How do I have to treat ?*? in the second time ?
A: Well, you can solve this in the following way:
The first time you read an information of a message that
was sent on
this edge, you can have its delay, so update the edge
delay, and now
you got it.
Q: In the pseudo code for the third algorithm it says that the data
structure for the sons is an array of boolean?s, but it
is logically
wrong, because it may contain INVALID_PROCESSOR_ID that
is -1, and -1 is
not a boolean, as far as I know.
A: Yes, we know that boolean fact too.
This is a pseudo-code, i.e. a way of writing down algorithms,
so people
will understand what is going own there.
You have also the hebrew description, and you can merge
the knowledge
of those two, in order to have your C implementation.
Q: Given a processor - Does it know if it is an initial node, or maybe
the initial node information is hidden from the processors,
and only
known to the simulation ?
(I ask this because in the pseudo code for algorithm3,
I need to know if a
processor is an initiator.)
A: As we said many times before, only the simulation manager knows
who are
those initiators.
A processor knows that he was waked up as a result of
an "init" message,
and thus to be an initiator for that moment, when he gets
an "init" message.
There is no "initiator" processor. This is only a state
when you got an
"init" message, and you handle it.
If you will read more carefully the pseudo-code, you will
see this when
you will compare the whole parts of the code among them.
Q: I tried your pseudo code for the third algorithm with the simple
topology 1 2 1. (1 is an initiator).
If I understand the pseudo code right, there is an error:
1 sends a regular message to 2, and waits.
2 gets the message. It sees that it is a first messages,
so 1 turns
to be his father.
And here comes the point- 2 sends a regular message to
noone, because
1 is his father, and he has no neighbors except 1.
So the algorithm stops, whereas it hasn’t finished yet.
A: You only forgot some "minor" things:
If node 2 has no neighbors (except his parent) to send
them messages,
then he actually finished with this stage, so he will
send an
"acknowledge" message to his parent and the algorithm
will end normally
and correctly.
---------------------------
16-6-99
---------------------------
Q: When a message is lost, should it be listed in the log file as
"Received" but not processed, or should it not be listed
at all as
received, just as sent ( I think the first option is the
more
reasonable one )
A: If a message is lost, then it never recieved.
and ... I do not know how you mark in the log file a message
that is
recieved but not processed.
Q: An Init message can be lost too, right?
A: Right.
Q: Can we change the function names in flood.c to fit in our
implementation scheme for the 10 algorithm places ( i.e.
change the name
"Flood" to "Algorithm1" and add a 1 at the end for all
the other function
names)? What should algorithms 5-10 do when invoked, anyway?
Q: But ofcourse you can.
Again, this file was only an example, and the names were
meaningfull so you
will be able to follow what we want from you.
Q: On the description of the DFS algorithm, you say that we agreed on
some
kind of order in the class ( in the paranthesis after
you say that an
initiator processor spreads a "regular" message to it's
first neighbour.
Well, when you means "from the smallest to the biggest"
you mean like,
when the neighbours are 3, 7, 9 to send to 3 first, then
to 7 and then to
9, right? Well, should all the algorithms do that or just
this one?
Because if it's only this one we can just qsort it's neighbour
list when
we init the algorithm, but if it's to all algorithms we
need to do it in
the program itself.
Q: All algorithm should do this.
This was talked in class on the two meetings.