10

rather than sizeof(std::atomic<bool>)==1 ?

A mutex could be implemented via a simple std::atomic<bool>, so I would think that the size of a mutex could be as small as that, or perhaps 4 (32bits).

Walter
  • 44,150
  • 20
  • 113
  • 196
  • "A mutex could be implemented via a simple `std::atomic`" doesn't mean it's the optimal implementation. –  May 22 '13 at 14:15
  • 5
    `atomic` is a poor man's `mutex`... I mean, **really** poor man's one. – Griwes May 22 '13 at 14:15
  • 5
    I wonder why some consider this question unclear or not useful. – R. Martinho Fernandes May 22 '13 at 14:15
  • 2
    At a guess, `std::mutex` isn't implemented as a spinlock. – Hasturkun May 22 '13 at 14:16
  • 4
    Relevant: http://stackoverflow.com/q/6816448/46642 (dupe?) – R. Martinho Fernandes May 22 '13 at 14:18
  • @Griwes I don't think a spinlock is a poor choice in general. There might be cases were a spinlock might be the better choice, e.g.: when you expect short locking times. – Stephan Dollberg May 22 '13 at 14:45
  • @bamboon, poor man's **`mutex`**. Spinlock is a poor man's **`mutex`** - that is, if you want a mutex, it is a poor choice, *not* "it is a poor choice in general". – Griwes May 22 '13 at 14:48
  • 1
    @Griwes what's the difference between an unqualified "it's a poor choice" and "it's a poor choice" qualified by "in general"? Anyway, sometimes a spinlock is exactly the right choice. – bames53 May 22 '13 at 15:16
  • @bames53, obviously. What I said is, again, "if you need mutex's functionality, spinlock is a poor choice". Nothing more, nothing less. – Griwes May 22 '13 at 15:17
  • 2
    As pointed out by Maxim below. A std::atomic spinlock is not a mutex. It's more like a CPU-wasting version of a semaphore with a count of one. – Martin James May 22 '13 at 16:00

3 Answers3

13

With one bool you could only implement a spin-lock. Note that it would be an unfair lock because nothing ensures that waiters queue up, so there is a chance that under high contention in the most extreme case a thread could be blocked forever because it would always lose the race to acquire the lock.

A mutex implementation needs support from the operating system to be able to put the waiting threads to sleep. So, a mutex would need a flag telling whether it is locked and some form of a queue descriptor that allows putting waiting threads to sleep and waking them. If you want the mutex to be able to support recursive locking, robustness, optional spinning, priority inversion protection, etc.., it would need even more members.

Maxim Egorushkin
  • 131,725
  • 17
  • 180
  • 271
  • 1
    But with one atomic `int` and a system call like `futex` on Linux, you can implement a proper mutex. – Mike Seymour May 22 '13 at 14:17
  • @MikeSeymour Not really. – Maxim Egorushkin May 22 '13 at 14:19
  • Do you mean "No, you can't", or "Not really, since you're using some kernel memory as well as the user-space `int`"? I'll have to disagree if you mean the first. – Mike Seymour May 22 '13 at 14:22
  • @MikeSeymour I'd like to see an implementation then. – Maxim Egorushkin May 22 '13 at 14:31
  • It's described in the Linux manpages, futex(2) and futex(7). [Here](http://ideone.com/F3Zozc) is one I was playing with a while ago, to see if it might be faster than a Posix mutex. (It wasn't measurably faster, so I stuck with the tried and tested implementation) – Mike Seymour May 22 '13 at 14:50
  • 1
    @MikeSeymour I concede you can :) One weak spot though is that a non-owning thread can release such a mutex and wreck havoc in the locking scheme. – Maxim Egorushkin May 22 '13 at 15:09
  • 2
    @MaximYegorushkin - yes, which makes it 'not a mutex'. – Martin James May 22 '13 at 15:55
  • 4
    @MartinJames: It makes it a mutex with preconditions on its operations. That doesn't make it "not a mutex", it just makes it less easy to debug than one which could enforce that precondition. `std::mutex` itself has the same precondition, with UB if you break it. And it's very easy to enforce externally, using an RAII lock type. – Mike Seymour May 22 '13 at 16:10
  • @MikeSeymour Releasing a non-owned POSIX mutex fails with `EPERM`. – Maxim Egorushkin May 22 '13 at 16:19
  • 5
    @MaximYegorushkin: Indeed; you couldn't implement a Posix mutex with just an `int`. But the question isn't about a Posix mutex, it's about `std::mutex` which (like much of the C++ library) doesn't require preconditions to be enforced. – Mike Seymour May 22 '13 at 16:27
12

The GNU library usually uses Posix threads to implement the standard thread library. That uses a single type pthread_mutex_t to represent several different types of mutex; so it contains various fields needed for more complex mutexes (e.g. a counter for recursive mutexes), plus a field to specify the type.

You're right that, in principle, with suitable support from the operating system, a std::mutex could use as little as one byte of user memory. (On Linux, it has to be an int; and on other platforms, it might be an integer or pointer-sized handle to a kernel resource). Presumably, the benefits of using a well-tested existing implementation were deemed to outweigh the benefits of saving a few dozen bytes per mutex.

Mike Seymour
  • 249,747
  • 28
  • 448
  • 644
6

A mutex could be implemented via a simple std::atomic<bool>

It does not look like a possibility, considering that mutex::lock is a required operation, and std::atomic<bool> is most likely a non-locking kind. You could put a while loop around the compare_exchange_strong call, but that is not the same as mutex::lock, because it wastes the CPU during the entire waiting period.

In general, std::mutex is a lot more complex than a simple bool with defined multithreaded behavior, explaining its rather larger size, which depends on the compiler: for example, on ideone the sizeof(mutex) is 24.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523