S
Szabolcs Ferenczi
I was re-reading the concurrent language tools of the Edison language,
when one interesting note caught my eyes: "... But the programmer is
no longer tied to the monitor concept, but can use simpler concepts,
such as semaphores ... Semaphores can then be used to implement a
multislot buffer in which sending and receiving can take place
simultaneously from different slots"
It seems that a solution does not necessarily have to be lock-free in
order to be efficient.
I have given it a try and checked it out how one could construct a
bounded buffer in C++ where the producer and the consumer can proceed
simultaneously.
template< typename T >
class BoundedBuffer {
enum {THREAD_SHARED=0, CLOSED=0};
public:
BoundedBuffer(const unsigned int limit,
Advancer *const first,
Advancer *const last)
: m_buf(limit),
m_first(first),
m_last(last) {
Sem_init(&m_full, THREAD_SHARED, CLOSED);
Sem_init(&m_empty, THREAD_SHARED, limit);
}
~BoundedBuffer() {
Sem_destroy(&m_full);
Sem_destroy(&m_empty);
}
void put(T item) {
Sem_wait(&m_empty);
m_buf[m_last->get_and_increment()] = item;
Sem_post(&m_full);
}
T get() {
Sem_wait(&m_full);
T aux = m_buf[m_first->get_and_increment()];
Sem_post(&m_empty);
return aux;
}
private:
std::vector< T > m_buf;
Advancer *const m_first;
Advancer *const m_last;
sem_t m_full;
sem_t m_empty;
};
For the construction, it needs two objects that implement atomic
increment of an index. By injecting these objects, one can supply
different advancers for the different needs. The indexes are used to
keep track of the first full and last empty positions, respectively.
The operation get_and_increment() atomically increments the index and
returns the value before the increment. If the index overflows, it is
reseted, so that the buffer slots are reused.
The class Advancer defines an abstract interface. I have used a
concrete class AtomicLockedAdvancer but anyone can use any other
technique as well.
The construction allows that producers and consumers can work on
different slots at the same time. It is solved by the two mutexes in
the two Advancers instead of the one mutex in the traditional monitor-
like solution. One mutex protects one index only. Thus the critical
region is smaller.
If a library does not provide semaphores, e.g. the Boost Library does
not, it can be solved by condition variables and mutexes as well. The
idea is the same, two mutexes must be employed instead of the one
mutex traditionally used in monitors.
Perhaps if the synchronization elements, i.e. the semaphores, are also
factored out, the class can be independent of any concrete thread
library.
Best Regards,
Szabolcs
when one interesting note caught my eyes: "... But the programmer is
no longer tied to the monitor concept, but can use simpler concepts,
such as semaphores ... Semaphores can then be used to implement a
multislot buffer in which sending and receiving can take place
simultaneously from different slots"
It seems that a solution does not necessarily have to be lock-free in
order to be efficient.
I have given it a try and checked it out how one could construct a
bounded buffer in C++ where the producer and the consumer can proceed
simultaneously.
template< typename T >
class BoundedBuffer {
enum {THREAD_SHARED=0, CLOSED=0};
public:
BoundedBuffer(const unsigned int limit,
Advancer *const first,
Advancer *const last)
: m_buf(limit),
m_first(first),
m_last(last) {
Sem_init(&m_full, THREAD_SHARED, CLOSED);
Sem_init(&m_empty, THREAD_SHARED, limit);
}
~BoundedBuffer() {
Sem_destroy(&m_full);
Sem_destroy(&m_empty);
}
void put(T item) {
Sem_wait(&m_empty);
m_buf[m_last->get_and_increment()] = item;
Sem_post(&m_full);
}
T get() {
Sem_wait(&m_full);
T aux = m_buf[m_first->get_and_increment()];
Sem_post(&m_empty);
return aux;
}
private:
std::vector< T > m_buf;
Advancer *const m_first;
Advancer *const m_last;
sem_t m_full;
sem_t m_empty;
};
For the construction, it needs two objects that implement atomic
increment of an index. By injecting these objects, one can supply
different advancers for the different needs. The indexes are used to
keep track of the first full and last empty positions, respectively.
The operation get_and_increment() atomically increments the index and
returns the value before the increment. If the index overflows, it is
reseted, so that the buffer slots are reused.
The class Advancer defines an abstract interface. I have used a
concrete class AtomicLockedAdvancer but anyone can use any other
technique as well.
The construction allows that producers and consumers can work on
different slots at the same time. It is solved by the two mutexes in
the two Advancers instead of the one mutex in the traditional monitor-
like solution. One mutex protects one index only. Thus the critical
region is smaller.
If a library does not provide semaphores, e.g. the Boost Library does
not, it can be solved by condition variables and mutexes as well. The
idea is the same, two mutexes must be employed instead of the one
mutex traditionally used in monitors.
Perhaps if the synchronization elements, i.e. the semaphores, are also
factored out, the class can be independent of any concrete thread
library.
Best Regards,
Szabolcs
ut(item);