What happens when multiple threads try to access a critical section exactly at the same time?

Question

I've being trying to find an answer for that, and all I could find it that once a thread reaches a critical section it locks it in front of other threads (or some other lock mechanism is being used to lock the critical section).

But that implies that the threads didn't really reach the CS exactly at the same microsecond.

Although I guess it is quite rare, can it really happen, and what happens in this situation?

Can I simply assume the the program will malfunction?

Note: I am referencing to a multicore CPUs.

Thanks.

Answer 1

It is the task of the cache coherence protocol to make sure there are no 2 writes on the same chunk of memory (cache line) at the same time. With MESI there can be multiple readers of the same cacheline, but only 1 writer.

So if 2 threads at the same time want to write to the same cacheline, their requests will be serialized by cache coherence protocol.

Most CPU architecture support atomic operations like CAS. On the X86 this can be done using a lock prefix. The CPU will lock the cacheline when it starts with the CAS instruction and will not respond to cache coherence requests from other cores till it is finished with the atomic operation.

So if you would have 2 CPUs that both want to do a CAS, these operations are serialized by the underlying hardware.

Answer 2

...But that implies that the threads didn't really reach the CS exactly at the same microsecond.

Short answer; Memory system hardware makes it impossible for two different processors to access the same memory location at the same time. I'm not a computer architect, so I can't explain how it works, but the memory system serializes all of the accesses to the shared, main memory by the various CPUs in a multi-CPU system.

"Entering a critical section" means locking a mutex, and a mutex basically is just a flag in shared memory that is accesses by a specific protocol.

Answer 3

I think you are missing the point of the fundamental locking primitives like Semaphores. If correct primitive is used, and used correctly, then the timing of the threads do not matter. They may well be simultaneous. The Operating System guarantees that no two thread will enter the critical section. Even on multicore machines, this bit is specially implemented (with lots of trickery even) to get that assurance.

To address your concerns specifically:

But that implies that the threads didn't really reach the CS exactly at the same microsecond.

No. The other threads could have reached in the same microsecond, BUT if the locking mechanism is correct, then only one the competing threads will "enter" the critical section and others will wait.

Although I guess it is quite rare, can it really happen, and what happens in this situation?

Rare or not, if the correct locking primitive is used, and used correctly, then no two threads will enter the critical section.

Can I simply assume the the program will malfunction?

Ideally the program should not malfunction. But any code will have bugs - so does your code and the Operating System code for the Semaphores. So it is safe to assume that in some edge cases the program will indeed malfunction. But this assumption is true for any code in general.

Locking and Critical Sections are rather tricky to correctly implement. So for non academic purposes we should always use the system provided locking primitives. All Operating Systems expose stuff like Semaphores which most programming languages have ways to use. Some programming languages have their own lightweight implementations which provide somewhat softer guarantees but at a higher performance. As I said, while doing Critical Sections, it is critical to choose the correct thing and also to implement it correctly.