mkdir is already atomic on local file systems. creat() with O_EXCL is not always atomic over NFS (depends on NFS version and kernel version, just when talking about Linux). I find indications in both directions as to whether mkdir() is atomic over NFS; so much so that I gave up trying to find the real answer.

Your approach can't work because there is no atomic "delete the file 'foo' and create the directory 'foo'" operation.

If it turns out that you have an NFS environment with atomic file creation semantics but mkdir isn't atomic (or you just can't determine whether it is or not), then you could use something similar to your approach.

1. Increment $i
2. Atomically create "reserve.$i" file
3. next if that failed
4. mkdir "$i" (which should never fail)

Note that you can't delete the "reserve.$i" file unless you know nobody is going to try to create a new directory after that. You could go with a more complicated algorithm if you want to delete the "reserve.$i" files.

1. Increment $i
2. next if -d "$i" (optional but avoids some thrash)
3. Atomically create "reserve.$i" file
4. next if that failed
5. if -d "$i" then unlink "reserve.$i", next
6. mkdir "$i" (which should never fail)
7. unlink "reserve.$i"