In the previous post, we described a token ring. The token continues to circulate whether there is demand for the shared resource or not. If the participants in the token ring respond only to requests, then there is more efficiency. The messages will now be for token and for the request. Tokens circulate in one direction and the requests circulate in the opposite direction.
A more general token based approach uses a spanning tree to pass the token. The advantage with the spanning tree is that it can be applied to any graph.
It works this way:
1) Every process knows where the token is
2) requests are sent towards the token
3) The tokens travel along the same path as requests, but the opposite direction
The process know where the token is by going to the root of the tree. The tree is directed and the token is always at the root.
Process sends only one request and may need to keep a list of pending requests from its children. The key question here is how to make sure the that the token is getting closer with each forward. For this we maintain a metric or invariant so that each forward reduces the metric say timeline. we could rely on the costs we calculated between neighbors in the minimum spanning tree. The tokens and the requests follow the edges of the spanning tree. Therefore, if we were to use the entire graph instead of the minimum spanning tree, we could find more optimal path. However, for that too we consider the graph as acyclic. We include the concept of an invariant and point the edges towards the token.The tree is generalized to a partial order.
The token tree examples above remind of the dining philosophers problem.
This problem is stated this way. Five philosophers are sitting around a table. Between each philosopher is a single fork and in order to eat a philosopher must hold both forks.
The philosophers transition between three states - thinking, hungry and eating. The neighbors do not eat at the same time. This guarantees safety. And when every philosopher eats, this guarantees progress.
One solution will be to require permission to eat from all of one's neighbors. However for this solution, deadlock is possible because each process could wait for the next one in cycle.
The solution can be improved with grabbing all forks at once and releasing them after a finite time. However, even in this solution some philosophers could starve.
A better solution could be to break the symmetry. Here one of the philosophers grabs the left fork while all others try to grab the right fork,. This way the symmetry can be broken and some of the philosophers can eat. while others eat in subsequent cycles thus guaranteeing progress.
If we generalize to an undirected graph, we can break the symmetry by giving edges a direction. When we do this, we must be careful not to introduce a cycle otherwise we introduce a symmetry.
We can add a structure on the graph such that it is acyclic. All the edges point along the same way typically up and thus we draw a partial order where the edges represent priority. Conflicts for a shared resource are resolved based on this priority. After a process wins and eats, its priority is reduced so that the neigbors get a chance to eat.
A more general token based approach uses a spanning tree to pass the token. The advantage with the spanning tree is that it can be applied to any graph.
It works this way:
1) Every process knows where the token is
2) requests are sent towards the token
3) The tokens travel along the same path as requests, but the opposite direction
The process know where the token is by going to the root of the tree. The tree is directed and the token is always at the root.
Process sends only one request and may need to keep a list of pending requests from its children. The key question here is how to make sure the that the token is getting closer with each forward. For this we maintain a metric or invariant so that each forward reduces the metric say timeline. we could rely on the costs we calculated between neighbors in the minimum spanning tree. The tokens and the requests follow the edges of the spanning tree. Therefore, if we were to use the entire graph instead of the minimum spanning tree, we could find more optimal path. However, for that too we consider the graph as acyclic. We include the concept of an invariant and point the edges towards the token.The tree is generalized to a partial order.
The token tree examples above remind of the dining philosophers problem.
This problem is stated this way. Five philosophers are sitting around a table. Between each philosopher is a single fork and in order to eat a philosopher must hold both forks.
The philosophers transition between three states - thinking, hungry and eating. The neighbors do not eat at the same time. This guarantees safety. And when every philosopher eats, this guarantees progress.
One solution will be to require permission to eat from all of one's neighbors. However for this solution, deadlock is possible because each process could wait for the next one in cycle.
The solution can be improved with grabbing all forks at once and releasing them after a finite time. However, even in this solution some philosophers could starve.
A better solution could be to break the symmetry. Here one of the philosophers grabs the left fork while all others try to grab the right fork,. This way the symmetry can be broken and some of the philosophers can eat. while others eat in subsequent cycles thus guaranteeing progress.
If we generalize to an undirected graph, we can break the symmetry by giving edges a direction. When we do this, we must be careful not to introduce a cycle otherwise we introduce a symmetry.
We can add a structure on the graph such that it is acyclic. All the edges point along the same way typically up and thus we draw a partial order where the edges represent priority. Conflicts for a shared resource are resolved based on this priority. After a process wins and eats, its priority is reduced so that the neigbors get a chance to eat.
No comments:
Post a Comment