globMyId : id of the coordinator.
globLastIndex : An integer variable that indicates the total number
of coodinators
present in the ARC ring.
lockRequest : The list that contains the list of locks.
pidArr : It is a integer array that holds the process id of all
the
When the user program wants to perform a distributed
computation, it has to obtain locks. The locks obtained are an indication
of the machine onto which the computation can be transferred on user's
behalf. If the user wants its program to execute in parallel on n nodes,
a request for n locks is made to the User interface. This interface then
tries to obtain n locks, some from itself and some from other remote coordinators.
Depending on the availability of locks, the user-interface can obtain n
locks or less. Let the total number of locks obtained be m. Now there can
be different cases :
1) If n = m, all the locks obtained are given to the user program.
2) If n > m, the user can get only m locks, although he requested
more. This is because only m locks are free.
3) If n < m, then more locks have been obtained then the user
has asked for. In this case, first n locks are given to the user program.
The algorithm followed here for allocating locks is a variant of Ricart-Agarwala algorithm for mutual exclusion. The algorithm is different from the basic Ricart-Agarwala algorithm in the following two ways :
1) Any coordinator can get the information about the status of locks at any instant of time. This is called the "peeping" into the lock array.
2) If a coordinator P requests locks from coordinator R, then R immediately responds to P's request telling whether P can obtain the locks or not. This is contrary to Ricart-Agarwala algorithm where the request is not answered immediately if the locks could not be granted.
With each request for locks, a sequence number is also sent. The significance of the sequence number arises when some coordinator receives request for locks from two coordinators. The decision is then made in favour of that coordinator whose sequence number is less than the sequence number of the other coordinator. Thus coordinators with lower sequence numbers get more priority than the ones with higher sequence numbers.
Following is the RPC service:
LocalLockArr* get_locks_available_5_svc( int* arg , struct svc_req *junk2);
Argument: The user program specifies the number of locks that it wants to obtain.
On the client side :
The client is user program
that wants to perform some distributed computation and hence wants to obtain
the locks.
On the server side
The coordinator Q on
receiving this function call from the user program does the following :
1) Invoke the function
getRemoteLockInfoArray()
to get the list of free locks from the remote coordinators and store the
returned list in remoteLockInfoArray.
2) Invoke the function
getLocalLockInfoArray()
to get the list of free locks present with the local coordinator and store
the returned list in localLockInfoArray.
3) Merge the two locks
arrays to get the array globalLockInfoArray by invoking the function
mergeLockInfoArrays
and giving it two lists as arguments.
4) At this time, if
the list globalLockInfoArray is empty then return an empty list
to the user and return. No free locks are present in the ARC system. If
the list is non-empty, goto step 5.
5) Invoke the function
acquireLocks()
that
returns the list of locks that coordinator Q has managed to acquire. Store
this returned list in locksAvailable.
6) Return the list to
locksAvailable
to
the user program.
Following is the list of Helper Functions:
The function acquires
the required number of locks from th remote coordinator. For this, the
status of each of the locks acquired is marked as "ALLOCATED" so that they
could not be given to other request.
The steps performed in this function can be
listed as following :
Run a while loop, each iteration of which will
fetch some locks, until the required number of locks have not been obtained.
In each iteration of while loop, the following steps are carried
out:
1) Initialize the array
lockRequest
by putting into it the sequence number and the node-id of the coordinator.
2) Invoke the function
copy_lockList_Into_lockRequestList()
that will copy some of the locks info from globalLockInfoArray to
lockRequest
list.
3) Invoke the function
call_AcquireLocks_RPC().
This function contacts each of the coordinators and passes them lockRequest
array
to find if it can acquire the locks, present in the lockrequest.
4) At this point, looking
into lockRequest will tell us whether a particular lock can be acquired
or not. The list of locks that could be acquired is put in the list Available.
5) Invoke the RPC function
call_set_Lock_Allocated_RPC()
on
the coordinators from which locks have been obtained to tell them that
they should mark the status of corresponding locks as "ALLOCATED".
This function copies numOfLocksToCopy number of locks from globalLockInfoArray to lockRequest list. The same number of locks and their details are also copied to the list lockReqInf. The purpose of the list, lockReqInf is to store all the details about the locks that are being requested along with the sequence number of the requesting coordinator so that the conflicts for lock acquisition can be resolved based on the sequence number.
The steps carried out in this function are listed below :
Run a loop numOfLocksToCopy times, and
in each iteration of the loop, following steps are performed :
1) Copy the nodeId (the id of the owner coordinator
of the lock), lockId and the magic number of the lock in the list lockRequest
and the list lockReqInf.
2) For each lock, run a loop as many times as
there are coordinators in the ARC system. In each iteration of the loop
do the following :
a) If the coordinator
is alive, set the permission mode of all the locks with respect to that
coordinator as "NOACCESS". This is the initialization of the permissions
and later some of these permissions may change to "ACCESS".
b) If the coordinator
is not alive, then set the permission mode of all the locks with respect
to the failed coordinator as "ACCESS", i.e. the failed coordinator should
not have a say in the acquisition of locks.
This function calls
the RPC function acquire_locks_4_svc(LockRequest* req, struct svc_req
*junk2) on each of the locks present in lockRequest list to
see if the lock could be acquired, i.e whether "ACCESS" or "NOACCESS" can
be given to the lock or not.
Run a loop as many times as there number of
coordinators in the ARC system. In each iteration of the loop do the following
:
1) Find if the coordinator is alive, by looking
at the value of nodeId in the globNodeArr.
2) If the coordinator is not alive ( has failed
or left ), then for all the locks present in the lockRequest list,
set the permission mode to "ACCESS" with respect to the failed coordinator.
This means that the failed coordinator does not have any problem if the
corresponding lock can be returned to the user program.
3) If the coordinator is alive, then call the
RPC function, acquire_locks_4_svc(LockRequest* req, struct svc_req *junk2)
on the coordinator to find the permission status of the lock. The function
returns the array of permissions for the locks. The permissions returned
are copied onto the access permissions of each of the locks.
The Available list contains
the list of locks that the coordinator has finally decided to use. Hence
the status of all these locks should be marked as "ALLOCATED".
For each lock present in the Available list, do the following
:
1) Check if the lock is located on the local
coordinator. If so, then the status of that lock can be marked as "ALLOCATED"
without invoking any RPC request.
2) But if the lock is present on remote machine,
then invoke the RPC function set_lock_allocated_6_svc( Lock* lock, struct
svc_req *junk) requesting the remote coordinator to set the lock status
as "ALLOCATED".
This function copies the locks on which "ACCESS"
permission has been obtained from lockRequest list to the Available
list.
The list lockRequest contains the list of locks on some of which
there are "ACCESS" permissions and they can be obtained.
For each of the lock that is present in the lockRequest,
do the following :
1) Find if the lock has "ACCESS" permissions
from all the other coordinators.
2) If not, then iterate to find this for the
next lock in the lockRequest.
3) If yes, then copy the lock into the Available
list.
Finally, the Available list will contain the list of all the locks for which "ACCESS" permissions have been obtained from all the coordinators.