Google Interview Question
Software EngineersCountry: United States
Very nice.
But how to resolve the dependency and deadlock situation? Suppose, machine m1 acquires lock for file1 and keeps the lock for very long file due to processing. So, all the requests to access file1 will be stalled. Now, if machine m2 wants to do something sequential (i.e. read file1, file2, file3 one by one), it will be blocked for that time (Asynchronous works will be done easily. But sequential tasks will be stalled).
there are so many ways to do this .
Centralized mechanism
1.Master keeps a token and slaves nodes request for the token when they enter a critical section and wait for it.
2.If the master has token it reply back otherwise queue the request .
3.When the master receives the token back from the slave it send the token to the first enqued request.
There are other ways to do this as well like Ring mechanism ,where token is circulated in a ring,RA algorithm ,DHT based solution
Use the following mechanism.
- wminghao November 23, 2015There is a lock manager node and bunch of other nodes
1. Each node, if it wants to acquire a lock, sends a lock request to the lock manager and wait for async callback from the lock manager
2. Lock manager has lock request queue checks if the queue is empty, it sends a lockAcquired notification to the caller node, then it puts the lock request in a queue. If the queue is not empty, it just pushes the lock request to the queue.
3. When a node receives the lockAcquired notification, it can process data. (Meaning lock is acquired)
4. When a node finishes processing, it will call unlock to the node manager.
5. When unlock call is received from the node manager, it pops the data from the queue and if the queue is not empty, sends a lockAcquired notification to the next node in the queue.