Mumbai University > Computer Engineering > Sem 8 > parallel and distributed systems

Marks: 10M

If a site without a token needs to enter a CS, broadcast a REQUEST for token message to all other sites.

nToken: (a) Queue of request sites (b) Array LN[1..N], the sequence number of the most recent execution by a site j.

Token holder sends token to requestor, if it is not inside CS. Otherwise, sends after exiting CS.

Token holder can make multiple CS accesses.

Design issues:

a).Distinguishing outdated REQUEST messages from current REQUEST messages

b) Determining which site has an outstanding request for the CS.

Algorithm

Requesting the critical section

If the requesting site 5i does not have the token, then it increments its sequence number, RNi[i], and sends a

REQUEST(i, sn) message to all other sites. (sn is the updated value of RNdi].)

When a site 5 j receives this message, it sets RNj[i] to max(RNj[i], sn). If 5 j has the idle token, then it sends the token to 5 i if RNj [i]=LN[i]+1.Executing the critical section.

Site 5i executes the CS when it has received the token. Releasing the critical section. Having finished the execution of the CS, site 5 i takes the following actions:

It sets LN[i] element of the token array equal to RNdi].

For every site 5 j whose 10 is not in the token queue, it appends its 10 to the token queue if RNi [j]=LN[j]+1.

If token queue is nonempty after the above update, then it deletes the top site

Example

Step 1: S1 has token, S3 is in queue.

Step 2: S3 gets token, S2 in queue

Step 3: S2 gets token, queue empty