Algorithm description Suzuki–Kasami algorithm

1 algorithm description

1.1 data structures
1.2 algorithm

1.2.1 requesting critical section (cs)
1.2.2 releasing cs
1.2.3 receiving request
1.2.4 executing cs

algorithm description

let



n


{\displaystyle n}

number of processes. each process identified integer in



1
,
.
.
.
,
n


{\displaystyle 1,...,n}

.

data structures

each process maintains 1 data structure:

an array



r
n
[
n
]


{\displaystyle rn[n]}

(for request number),



r

n

i


[
j
]


{\displaystyle rn_{i}[j]}

stores last request number received



j


{\displaystyle j}

the token contains 2 data structures:

an array



l
n
[
n
]


{\displaystyle ln[n]}

(for last request number),



l
n
[
j
]


{\displaystyle ln[j]}

stores recent request number of process



j


{\displaystyle j}

token granted
a queue q, storing id of processes waiting token

algorithm
requesting critical section (cs)

when process



i


{\displaystyle i}

wants enter cs, if not have token, it:

increments sequence number



r

n

i


[
i
]


{\displaystyle rn_{i}[i]}


sends request message containing new sequence number processes in system

releasing cs

when process



i


{\displaystyle i}

leaves cs, it:

sets



l
n
[
i
]


{\displaystyle ln[i]}

of token equal



r

n

i


[
i
]


{\displaystyle rn_{i}[i]}

. indicates request



r

n

i


[
i
]


{\displaystyle rn_{i}[i]}

has been executed
for every process



k


{\displaystyle k}

not in token queue



q


{\displaystyle q}

, appends



k


{\displaystyle k}





q


{\displaystyle q}

if



r

n

i


[
k
]
=
l
n
[
k
]
+
1


{\displaystyle rn_{i}[k]=ln[k]+1}

. indicates process



k


{\displaystyle k}

has outstanding request
if token queue



q


{\displaystyle q}

nonempty after update, pops process id



j


{\displaystyle j}





q


{\displaystyle q}

, sends token



j


{\displaystyle j}


otherwise, keeps token

receiving request

when process



j


{\displaystyle j}

receives request



i


{\displaystyle i}

sequence number



s


{\displaystyle s}

, it:

sets



r

n

j


[
i
]


{\displaystyle rn_{j}[i]}





m
a
x
(
r

n

j


[
i
]
,
s
)


{\displaystyle max(rn_{j}[i],s)}

(if



s
<
r

n

j


[
i
]


{\displaystyle s<rn_{j}[i]}

, message outdated)
if process



i


{\displaystyle i}

has token , not in cs, , if



r

n

i


[
j
]
==
l
n
[
j
]
+
1


{\displaystyle rn_{i}[j]==ln[j]+1}

(indicating outstanding request), sends token process



i


{\displaystyle i}



executing cs

a process enters cs when has acquired token.