Renaming a file is a good example. Within the internal structure of the filesystem, you have a directory entry in an old location. That must be removed. You may have another file with the same name in the destination directory. That file must be overwritten. Internally, these things happen by a multi-step process, eg: remove entry for old name, remove pre-existing entry for new name, create new entry for new name. But the system creates the appearance of just 1 step. You don't get file not found while it's overwriting the destination file. You don't ever see the file having both old and new names at the same time.
Atomicity requires that the leakage mentioned shall not occur from any context aside from its own internal context. That makes your example somewhat of a simplification because these state transitions are visible to other processes. It is a common mistake to try to use files for locking, for example, instead of using the more robust flock(1).
Would not be surprised if all bets are off once you get an NFS mount involved.
As always it's a tradeoff between useful behaviors and the cost of synchronizing.
Why is this a mistake? It is my understanding that, if all the locking you need is a simple mutex, creating a file with a well-defined name with O_CREAT | O_EXCL is atomic -- the file will either be created or not (in which case the call will fail with EEXIST), and no two processes can possibly both succeed at creating the file. This even works on NFS; it was apparently broken in the NFS client in Linux 2.6.5 and below, but it is supposed to work in NFS, and is generally the only reliable way of getting locks in NFS.
You don't get any better way to wait on the lock than re-trying to create the file, and you don't have any mechanism for dealing with clients that die while holding the lock (i.e., it's an aggressively CP system), but for what it does, it's supposed to work correctly and atomically.
This gets rid of all the edge cases with stale locks in one fell swoop.
But as you point out if you want to do this e.g. over NFS you should create a file, but then you need to deal with stale locks.
If you can at all avoid that using flock() is generally better.
And my instinct is that in a networked scenario, you're at least as worried about a machine dying as a process on the machine (i.e. a network partition). A flock()-based lock doesn't clean itself up if the client is unreachable, does it?
Personally I prefer something like a MySQL table with GET_LOCK() to process things instead of NFS if I need multiple machines. It gives you flock() like semantics in that if a machine or client goes away the GET_LOCK() is automatically freed, i.e. it survives as long as the connection to the database survives.
Not having to deal with stale locks generally sucks way less than the extra overhead of a database.
For any NFS-based scenario you usually end up creating a "task" "task.underway" and "task.done" files as locks, and re-enqueuing tasks if you have a "underway" file that's too old without a "done" file.
You'd do the same with a MySQL table that you GET_LOCK() on, except you can safely re-enqueue "underway" tasks if you acquire the lock on them, since you know their consumers have gone away.
if [ ! -f $FILE ] ; then
touch $FILE
# do something dangerous, assuming I have a lock
rm $FILE
fi
Of course, you don't have to use flock(1) to make this operation atomic. It just handles a lot of the extra work that I don't want to have to think about, even if I did set `noclobber` or something like that.
Edit: Thanks everyone for taking time to explain it to me.
Likewise, for the seemingly simpler example if establishing a friend relationship, you may be tracking that relationship in both directions, in which case one could fail and the other succeed.
Might, not should. All web apps are not just front ends to a single database where transactions are useful and once you leave the realm of a single database into a more distributed type system then transactions are no longer an option.
Thus, the adding of the two edges must be atomic (when observed from the rest of the system).
(The example is a bit contrived, but hopefully gets the idea across.)
If possible you should probably go for an even stronger property, namely Idempotence[1]. (This can be relatively easy if you can force clients to provide some sort of unique token for every operation.)
It's usually makes this even easier to reason about for clients since they can just retry anything while knowing that it doesn't matter if they retry an already "applied" operation.
If your code is too slow (a complex effect, too many character at that point), you might not be done writing a full frame when the graphic chips starts to output the pixels.
This means your TV is now showing partly old and new state. Nothing important most of the time, it's only games, it's only a few ms of absurd information, people's brain can compensate. It is ugly to see though. You have that weird 'line' somewhere below.
Since people changed the structure a bit, with two (or more) buffers, the program computes the new image in one buffer B, while the chip shows another buffer A. When you are done with a picture, the chip will now scan B, while you can write in A. This means the output never shows partial frame anymore.
Personally, I struggled long time before fully understanding its use in IT, because I learned programming after sub-nuclear physics, thus I had a hard time conciliating the huge atom (a million of billions of times bigger than a nucleus) with the concept of "cannot be split" :-)
Lets say that we have a banking application that consists of a program which updates someones bank account by $Y every time it is called. Y is the command line parameter. The program's algorithm is like this :
1. Read the current balance amount to X
2. Add Y to X and store it in Z
3. Write Z to the database.
This program cannot be called by multiple processes at the same time. Lets say that it is payday, the account holder holds two jobs and each employer is trying to deposit $10 into someone's account, at the same time. Both these processes call the program with Y = $10. What happens ?
1. Process 1 reads the current balance ( $100 ) to X
2. Now, process 2 reads the current balance ( $100 ) to X
3. Process 1 adds 10 to X ( Z = 110 )
4. Process 2 adds 10 to X ( Z = 110 )
5. Process 1 writes the updated value to the database ( Z = 110 )
6. Process 2 writes the updated value to the database ( Z = 110 )
Now the account reflects a balance of $110, when it should have reflected $120. What we need is a guarantee from the system that some actions will not be parallelized ( i.e, they will be atomic ). From TFA it is given that "mkdir" is an atomic operation in UNIX ( i.e, only one process can create a directory at the same time ). You can write the program with the following logic
1. mkdir /tmp/lock_dir
2. If above step was unsuccessful sleep 10 seconds and go back to step 1
3. Read current account balance to X
4. Add Y to X and store it in Z
5. Write Z to database
6. Remove /tmp/lock_dir
Multiple processes can invoke this program simultaneously.
No. It can has as many side effects as it wants. Atomicity means: when going from state 1 to state 2, no matter how complex the transition, there are no externally observable intermediate states.
For example, one can use the atomic nature of creating a symbolic link on nix to create a lock file to prevent a race condition in a forking shell script. Say you have two or more processes wanting to do something that can (or should) only be done by one process at a time; one naive solution is to manage access of each process to said action by using a lock file. However, writing or touching a file itself is not atomic.
The answer is to throw a symbolic link into the mix. In this scenario, the lock file already exists. However, the lock is not the file itself, but a symbolic link to the file. The protocol for each process to follow is:
1. try to create a symbolic link to lock file (any file really)
2. if successful, proceed; if failed, wait (or exit)
3. when process is done, delete symbolic link to lock file
Simply checking for the existence of the symlink is not sufficient since there is a period of time between checking for the symlink (or file) and proceeding with said action where another process can think it has the lock.
The OS ensures that one and only one symlink (of the same name) can exist; attempts to create it again (even simultaneously) will result in a failure of one process to create the symlink. There is one winner; all others are losers. This is to say, the kernel ensures that the operation is atomic. As a result, the OS is now arbitrating what process can proceed to action, at the very lowest level. Another way to think about it is that it provides a way to make competing processes serialize - or get in line so that they may complete their action one at a time.
In my experience, it is important to experiment and test to make sure that the atomic primitive you're using is actually working as expected. I've run up against some inconsistent implementations of symlink creation that make this action not as straightforward to use as one is lead to believe.