Lock data structure or lock the code?

2022-03-08T11:43:42+02:00

Dear students,

yesterday, I was talking about difference between “lock data structure” and “lock the code”. As I’ve used bad example, there was an additional question. Hope the following helps to understand it better.

We have the queue data structure:

q = {
    ar[10] ; array of length 10 to store something
    e = 0 ; where to enqueue
    d = 0 ; where to dequeue
}

enqueue(q, something)
    q.ar[q.e] = something
    ++(q.e)

dequeue(q)
    if q.d > q.e
        return nothing
    what = q.ar[q.d]
    ++(q.d)
    return what

++(index)
    if index + 1 == 10
        return 0
    else
        return index + 1

When we think in terms of “lock data structure”, we probably write the following:

q_m ; queue mutex protecting the "q" data structure

lock(q_m)
enqueue(q, something)
unlock(q_m)
...
lock(q_m)
what = dequeue(q)
unlock(q_m)

because we are protecting the “q” data structure we are changing. However, better approach in this example is to “lock the code” of “enqueue” and “dequeue” calls:

e_m ; enqueue mutex
d_m ; dequeue mutex

lock(e_m)
enqueue(q, something)
unlock(e_m)
...
lock(d_m)
dequeue(q)
unlock(d_m)

because we can allow “enqueue” and “dequeue” to access the queue “q” simultaneously.

Please, note that all of this is just point of view, because “e_m” and “d_m” mutexes could be understood as “lock data structure” approach to the queue’s members “e” and “d”.