PDA

View Full Version : Implementing problem



dinesh
11-18-2003, 12:19 AM
Th following is an implementation problem. No code needed, just designing...and a bit of explanation.......

arumugam57 was a philosopher in ancient Greece. He was in the process of writing a great book, and his friend vennai1 has agreed to double-check the contents. arumugam57 only writes when he's in the mood, and after he finishes writing a page, he will give it to a disciple, who'll run across town to deliver it to vennai1. Assuming an infinite number of disciples are availabe, how can we model this in a practical world.......

Just points would do.........think abt practical problems......if disciple 'sri_gan' starts with page n, and is very slow, while disciple 'madhu_aish1' starts with page 'n+1', and is very fst....how can we make sure of the continuity..........also how can we make sure every page is delivered (disciple sofiadorathy might run away with a page to Latvia)...........

vijey
11-18-2003, 12:45 AM
so many variables
this will be a harder work for our students here shidenesh :sm08:

silican
11-18-2003, 01:13 AM
Th following is an implementation problem. No code needed, just designing...and a bit of explanation.......
..........................(con tinues)



1) This is the practical workability in TCP protocol structure. for every data(page) the Server (aarumugam) sends to the client (Vennai), Vennai sends back an acknowledgement through sri_gan or Thirudan. once they bring back the ack to arumugam, arumugam will send the next page.

2) If SofiaDorathy runs away to Latvia with a page (kochikadheenga Sofia..just an eg.) Vennai woudnt be sending an acknowledgement for that particular page. So arumugam will send the same page through sweetie/Bhagavathar.

Ofcourse this is just a portion of TCP in general. There are a lot of other possible considerations too. like NACK (Negative acknowledgement), Time-outs, Routing algorithm etc...

sathy
11-18-2003, 01:47 AM
Silican :b:

This could be done in other way too...

Abstract: Our arumugam is the main process that sends data (pages) throu' threads (disciples) to a I/O Device(vennai) connected throu' a USB/COM port or a pipe.
The threads(disciple) will be listening and carry the data when it is available. And it will be blocked until signaled by our equipment(Vennai).
Once in a while threads might get busy(going to lativia) doing someother work for different port and could delay the data(already in queue). Get the result from the thread and know the status.
It'll be easy if there is a page number(data packet identifier), so that vennai can rearrange the data in sequence. Assuming vennai is not dumb :wink:

Easy to explain, but lota things to be taken care :D

king_143
11-18-2003, 06:48 PM
Sathy,
The answers are corret. Its works for all C compilers.

king_143
11-18-2003, 06:49 PM
heres a good question in C++

Can a program have a virtual constructor?
PLEASE EXPLAIN

vennai1
11-18-2003, 08:19 PM
enakku programming theriyaathunnaa kooda... that general problem

posed by gulpi dinesh and relevant answers by mamooty and sathy

were intarastink... :clap: :clap: :b:

dinesh
11-20-2003, 09:21 PM
Both the solutions posted by silican si correct. and sathy's is correct to a certain extent....
Sathy's solution will have a major problem with deadlocks, if we modelled the solution as processes. For example, if process n is delayed by some reason, then no processes after that will be able to access arumugam, eventhough they have nothing preventing them. But, there are workarounds for all these problems, so it'll work....

A solution I thought was based on messenger software....if you look closely, this entire problem will be based on that technology :b:

sathy
11-20-2003, 10:58 PM
Sathy's solution will have a major problem with deadlocks, if we modelled the solution as processes.


shidinesh,
the above is just a solution, not a implementation. if you start implementing this prob. you have to consider lotaa things. sure deadlock will occur use critical sections or semaphore or mutex objects


For example, if process n is delayed by some reason, then no processes after that will be able to access arumugam, eventhough they have nothing preventing them. But, there are workarounds for all these problems, so it'll work....


wat you mean process n here? there is just one process(arumugam) and everything else are threads. so i don't see any problem even if anyone of the thread is delayed, other threads can deliver the message. so this should work without any problem considering the synchronization aspects and timing the events.


A solution I thought was based on messenger software....if you look closely, this entire problem will be based on that technology :b:
did you mean something like a msn/yahoo messenger? :think:
on wat context :?
lets say aru uses yahoo messenger service. when he signs into YM his client immd. sends the server the connection information (IP address n the port number) and in return provides bis buddy list. lets say vennai is alreadyin his buddy list. the server sends the online status of aru to vennai and the online status of vennai to aru. if they want to send messages, its nothing but mere one-to-one connection across the network(internet). yahoo server doesn't comes into the picture here. just two clients talking directly. even the temp. messages/files are saved locally.

so as far i know this is how a messenger works. if your context is different(not sending messages or how messages are sent) lemme know in the context based on your philosopher problem :D

dinesh
11-20-2003, 11:25 PM
If we ognore all the signing in stuff.......

User 'A' sends a message, and then say he sends another one.

The things we have to make sure is, the messages reach in the correct order, and the sender should be notified of failed messages,.
So, basically that's the framework we are looking for. And the sending of messages is also modelled the same way, if we consider one channel for each message (though that's not how it's done these days).
I wasn't saying that either one of the philosophers should act as a server. And it's not wrong either if you take it that they are servers, but you can also assume they are clients, and assume the messaging process is done by a server. You only have to consider each disciple as a messaging channel.



wat you mean process n here? there is just one process(arumugam) and everything else are threads. so i don't see any problem even if anyone of the thread is delayed, other threads can deliver the message. so this should work without any problem considering the synchronization aspects and timing the events

Ya....my mistake. I misread threads as processes. You are right. We wouldn't have any race conditions with threads

sathy
11-20-2003, 11:49 PM
The things we have to make sure is, the messages reach in the correct order, and the sender should be notified of failed messages,. So, basically that's the framework we are looking for.



if we consider one channel for each message (though that's not how it's done these days).

yes, the framework is correct only by considering one channel for each message (which doesn't exist anymore). instead of considering yahoo/msn messenger as such. we can follow your way to implement one to acheive the philosopher/disciple problem :b:

king_143
11-21-2003, 11:49 PM
I would like to if there is an absolute soltuion for this problem. I have doubt on this.

sathy
11-22-2003, 12:03 AM
I would like to if there is an absolute soltuion for this problem. I have doubt on this.

all the above three are valid solutions you can try implementing with any of the methods. btw, whatz your doubt?

king_143
11-22-2003, 12:10 AM
I took a case where there is a forest between 6face and Ven. [Note that the only communication between Ven and 6Face is through mesengers going through the forest.] The messenger who passes through the forest either succced or dies. I tried look for a solution/algortihm which is always reliable under any cirumstances. I think it is not possible.

sathy
11-22-2003, 12:28 AM
I took a case where there is a forest between 6face and Ven. [Note that the only communication between Ven and 6Face is through mesengers going through the forest.] The messenger who passes through the forest either succced or dies. I tried look for a solution/algortihm which is always reliable under any cirumstances. I think it is not possible.

we r not developing a game s/w like dungeons and dragons, so that the disciples will kill the dragons and continue the voyage to reach vennai :wink: above given is just a programming solution and considering forest (in your term) with reference to the above scenario is nothing but a unstable network or network with intruders or something else that might kill your data. implement your own encryption routine or have a own network or wait for the acknowledgement and timeout and resend the package. that's it.

dinesh
11-22-2003, 01:40 AM
The problem with assuming that the messengers will either succeed or die is, we won't have a mechanism to let the sender know if a message has reached the receiver.



have a own network or wait for the acknowledgement and timeout

How can we set up the acknowledgement process? For example consider this. A disciple delivers the message successfully. Then when the acknowledgement is sent the person carrying it dies. Then how will the sender know the status of his message?

The answer for king_143 is, your model does not suit this problem. So I don't think it'll be possible to implement it using your model. But, that is the nature of implementation problems. Some models might work, while some might not!

king_143
11-22-2003, 11:23 PM
Ok sathy,
Now I understand , You are taking that the network is relaiable i.e atleast a certain % of messages are guranteed to reach vennai and vice versa.

sathy
11-22-2003, 11:55 PM
How can we set up the acknowledgement process? For example consider this. A disciple delivers the message successfully. Then when the acknowledgement is sent the person carrying it dies. Then how will the sender know the status of his message?

the sender won't know until he receives the acknowledgement. so by default timeout and resend the packet. if you know other way to sort out this lemme know :D

silican
11-23-2003, 06:12 AM
Ya sathy is right,
a time-out will be initially setup calculating the RTT (round trip time) and adding an extra time to it..So if the receiver doesnt get the ACK, the sender automatically re-sends the packet.

Considering ths condn, it wd be a better option to use NACK (negative acknowledgements) where the receiver sends the NACKS for the packets tht are not received....

I have more to discuss on ths/...But I shall wait for ur ideas and my exams 2 get over