What is the difference between lockless and non-blocking?

Question

Hi,

In the context of data-structures synchronization, can someone clarify the difference between "lockless" and "non-blocking"? These terms seem to be used interchangeably by a lot of people but I'm not yet sure if there isn't some subtle difference hidden somewhere.

I mean lockless is "without locks" and non-blocking is more like guaranteeing progress. I suspect that one implies the other but not the other way around, I'm not sure.

References welcome.

Answer 1

Yes, lockless means without a locking mechanism. Non-blocking means that a call is going to return immediately rather than waiting for some external event (such as the release of a lock, or data arriving in a buffer) to occur. It's possible to have locks and use non-blocking calls, as for instance in the call

flock(fh, LOCK_SH | LOCK_NB);

which means "try to get a read lock, but if you can't, don't wait around for one, return immediately and tell me you couldn't". The default behavior of LOCK_SH ("shared lock") without LOCK_NB ("non-blocking") would be to wait for lock availability.

Answer 2

They're totally different.

Locking means you use some method to control file access using locks. This stops two processes writing to the same file at the same time, stops one writing while another is reading, but allows two to read at the same time.

Blocking means the method will wait for the operation to complete before returning.

Update

In response to the request for examples... I will try to add examples if I get time, but for now, here's an explanation of the possibilities.

We have 3 ways to perform locking:

• None
• Blocking. If the lock is unavailable, wait for it.
• Non-blocking. If the lock is unavailable, fail.

And 2 ways to perform IO:

• Blocking. Wait until the buffers are ready.
• Non-blocking. Fail if we can't read/write immediately

If we use open() and read() as normal, we get blocking IO. If we want non-blocking IO we have to pass the O_NONBLOCK flag to open(), and read() will then return E_AGAIN instead of blocking.

By default there is no locking. We can call fcntl() with F_SETLK or F_SETLKW to obtain the lock. The former blocks if the lock is unavailable, the latter fails with EACCES or EAGAIN.

I think there are two possible points of confusion:

• IO can be blocking/non-blocking, locking can be blocking/non-blocking.
• Aside from data not being ready, a IO request can block because another process has the file locked.

Answer 3

They can be similar, but often used in different contexts. In the context of a data structure, they would be the same thing. You could also use "non-blocking" in the context of IO as well, in which case it means that the function will not wait for the operation to complete before returning or that the operation is certain not to block (e.g. reading data that has already been cached).

Also, non-blocking may not imply that something is lockless. For example, a data structure may use locks but have some non-blocking operations that don't require a lock and other blocking operations that do require one.

Answer 4

Locking is an access control mechanism. Whereby i mean you lock a resource when you want an exclusive access to it. Lock the door, use the room/do whatever you wish, now unlock the room for others, so that they can use it now. While the room is locked, no one else could have entered the room, thus could not have done anything.

Blocking is used for guaranteed data-retrieval, that unless you dont have data, dont come back. Keep waiting at the door/pipe/socket(basically anything) and when data is available get it and come back.

Addition--
Do not get confused by the literal english-meaning of the words, as they both can be used interchange-ably in the context you try to put them in. For example -- locking is like blocking for others to use the same resource, and blocking can be locking yourself(calling function) to the resource until data is available.

So LOCKING simply mean you capturing a resource for a specified amount time(unless you un-block it). And, BLOCKING is you are blocked, which means you cannot proceed further as you do not have data, to proceed or go ahead.

The way they are implemented, by changing the states of the process, and waiting for the interrupt or event to occur.

Answer 5

A tentative answer through an example:

Consider an object (called "event") with two methods, wait() and notify().

• Implementation 1:

  notify() atomically sets a boolean. wait() loops until the boolean is true. Both are lockless, but wait() is blocking.

• Implementation 2:

  notify() gets a lock, sets a boolean then releases the lock. wait() gets the lock, reads the boolean, releases the lock, all this in a loop until the boolean is true. Both are thus lock-based, blocking.

• Implementation 3:

  Initially the lock is in use. notify() checks a boolean and releases the lock if it's true. wait() gets the lock and sets the boolean to true. notify() is non-blocking (it is argueable whether it is lockless or not). wait() is lock-based, blocking.

So I would say that non-blocking implies lockless, but they are not equivalent because a lockless operation can still block for a condition in a loop.