Answer:
任何一个获得互斥锁（这个锁禁止其他节点读取数据）的节点更改了数据，之后如果lock
manager[[可以理解为一个全局的锁的管理者]]要收回这个锁，这意味着有其他节点要读取或写入数据，之前那个节点需要以piggyback的形式把更改的数据送回，这样其他节点（那些获得读写权限的节点）就可以获得最新的数据版本了。
（2）
We
can tackle this problem using a master for synchronization and N nodes for
actual storage of the linked list.
Every time a node wants to do something on the linked list (since we are using a linked list we can suppose the operations available are append on both ends/remove on both ends), it has first to acquire a lock which state is controlled by the master.
This will work but won't allow for much concurrency as no parallel operations would be possible.
If we want to allow parallel operations to occur, we can make the operations reported (marked as => below) to the master before they are actually performed on any node:
Operation 1 - Node i => Append 3 to the linked list
Operation 2 - Node j => Remove the top element of the linked list
The master would allow the operation 1 and start propagating it to every N nodes.
Then it would see the operation 2 and would not allow it as it is not compatible with operation 1 (add/delete on the same side cannot be done concurrently).
Another sequence could be:
Operation 1 - Node i => Append 3 to the linked list
Operation 2 - Node j => Append 5 to the linked list
In that case, the master could allow each operation to be performed but would propagate operation 1 before it actually starts propagating operation 2.
In my opinion, the key point here is to ask:
- should we allow parallel operations and which ones ? if no, then a master lock will do fine
- does it matter if the order of insertion/deletion is not respected ? (i.e. we can permute two consecutive append or two consecutive delete) If not, then we can allow for some level of concurrency.
Every time a node wants to do something on the linked list (since we are using a linked list we can suppose the operations available are append on both ends/remove on both ends), it has first to acquire a lock which state is controlled by the master.
This will work but won't allow for much concurrency as no parallel operations would be possible.
If we want to allow parallel operations to occur, we can make the operations reported (marked as => below) to the master before they are actually performed on any node:
Operation 1 - Node i => Append 3 to the linked list
Operation 2 - Node j => Remove the top element of the linked list
The master would allow the operation 1 and start propagating it to every N nodes.
Then it would see the operation 2 and would not allow it as it is not compatible with operation 1 (add/delete on the same side cannot be done concurrently).
Another sequence could be:
Operation 1 - Node i => Append 3 to the linked list
Operation 2 - Node j => Append 5 to the linked list
In that case, the master could allow each operation to be performed but would propagate operation 1 before it actually starts propagating operation 2.
In my opinion, the key point here is to ask:
- should we allow parallel operations and which ones ? if no, then a master lock will do fine
- does it matter if the order of insertion/deletion is not respected ? (i.e. we can permute two consecutive append or two consecutive delete) If not, then we can allow for some level of concurrency.
No comments:
Post a Comment