Today we will continue our discussion on the DES and see if we can consider each source and server to be a separate process. Clients are passed as messages between the processes. We assume a queue for transit so that the messages appear sequentially.
Now since every process maintains a single queue for event, it has to decide when to process it. If it processed it rightaway, there might be another message from another source that should have been processed earlier. So the server has to wait for the incoming messages on all its inbound channels before deciding which one to execute. It must wait. But this could lead to a deadlock because two process could be waiting on each others inbound channel.In order to advance, we must ensure that such events arrive.
One solution is to send update events called null events. They don't do anything other than to break the impass and ensure progress. But even the null events need to be time-stamped properly.
Since null events don't take any time to process, they don't advance the clock. For each process in the cycle, the empty queue should contain the minimum time, but this is deadlock. So a null event has to be timestamped strictly larger than the one at the current process. This null event is then sent out to all processes.
The null events break the impass because they represent a guarantee that no events will arrive earlier than this event. The increment of the null message timestamp above the current time is represented by the lookahead.
Several refinements of this basic algorithm are available. Some of these are :
1) pre-compute service time. If the service time is independent of the particulars client, the length of the time required for the next service request can be calculated before the next event has arrived. and this is typically larger than the original look-aheads.
2) Request time-updates explicitly - Rather than sending null events, processes can explicitly request null events. This occurs when a queue for a particular in-neighbor becomes empty.
3) Allow deadlock - Yet another approach is to not use null messages at all. Instead a deadlock detection scheme is used.
4) Increased synchronization - A tighter synchronization between processes can be used to ensure that no processes get too far ahead of any other. A safety window is maintained.
All of these variants behave differently and often some experimentation is involved. Generally speaking, the magnitude of the look-ahead affects performance and this is highly application specific.
Now since every process maintains a single queue for event, it has to decide when to process it. If it processed it rightaway, there might be another message from another source that should have been processed earlier. So the server has to wait for the incoming messages on all its inbound channels before deciding which one to execute. It must wait. But this could lead to a deadlock because two process could be waiting on each others inbound channel.In order to advance, we must ensure that such events arrive.
One solution is to send update events called null events. They don't do anything other than to break the impass and ensure progress. But even the null events need to be time-stamped properly.
Since null events don't take any time to process, they don't advance the clock. For each process in the cycle, the empty queue should contain the minimum time, but this is deadlock. So a null event has to be timestamped strictly larger than the one at the current process. This null event is then sent out to all processes.
The null events break the impass because they represent a guarantee that no events will arrive earlier than this event. The increment of the null message timestamp above the current time is represented by the lookahead.
Several refinements of this basic algorithm are available. Some of these are :
1) pre-compute service time. If the service time is independent of the particulars client, the length of the time required for the next service request can be calculated before the next event has arrived. and this is typically larger than the original look-aheads.
2) Request time-updates explicitly - Rather than sending null events, processes can explicitly request null events. This occurs when a queue for a particular in-neighbor becomes empty.
3) Allow deadlock - Yet another approach is to not use null messages at all. Instead a deadlock detection scheme is used.
4) Increased synchronization - A tighter synchronization between processes can be used to ensure that no processes get too far ahead of any other. A safety window is maintained.
All of these variants behave differently and often some experimentation is involved. Generally speaking, the magnitude of the look-ahead affects performance and this is highly application specific.
No comments:
Post a Comment