A recent question on StackOverflow asked about whether or
not a mutex is locked twice by the same thread without unlocking the mutex. See
https://stackoverflow.com/questions/76890110/c-the-thread-repeatedly-locks-the-same-mutex-multiple-times?noredirect=1#comment135552146_76890110
The C++ source code presented in the question is:
1 #include
<exception>
2 #include
<memory>
3 #include
<mutex>
4 #include
<stack>
5
6 struct empty_stack : std::exception
7 {
8 const char* what() const throw();
9 };
10
11 template<typename T>
12 class threadsafe_stack
13 {
14 private:
15 std::stack<T> data;
16 mutable std::mutex m;
17 public:
18 threadsafe_stack(){}
19 threadsafe_stack(const threadsafe_stack& other) {
20 std::lock_guard<std::mutex> lock(other.m);
21 data = other.data;
22 }
23 threadsafe_stack& operator=(const threadsafe_stack& other) = delete;
24 void push(T new_value)
25 {
26 std::lock_guard<std::mutex> lk(m);
27 data.push(std::move(new_value));
28 }
29 std::shared_ptr<T> pop()
30 {
31 std::lock_guard<std::mutex> lock(m);
32 if (data.empty()) throw empty_stack();
33 std::shared_ptr<T> const res(std::make_shared<T>(data.top()));
34 data.pop();
35 return res;
36 }
37 void pop(T& value)
38 {
39 std::lock_guard<std::mutex> lock(m);
40 if (data.empty()) throw empty_stack();
41 *value = data.top();
42 data.pop();
43 }
44 bool empty() const
45 {
46 std::lock_guard<std::mutex> lock(m);
47 return data.empty();
48 }
49 };
One issue with this program design, which has nothing to do
with the question asked, is throwing an exception when pop is called on an
empty stack. An empty stack is not an exceptional situation. In fact the stack
starts off as an empty stack when it is created.
Exception handling should not be used to deal with
non-exceptional program state.
The following Ada stack implementation demonstrates how an
empty stack should be handled in a thread-safe manner.
The Ada program defines a generic thread package with the
same operations shown in the C++ example above.
The Ada program creates a generic stack package and a main
procedure. Ada packages are separated into two parts, the package specification
and the package body or implementation. The package specification defines the
package API.
1 with Ada.Containers.Doubly_Linked_Lists;
2 generic
3 type element_type is private;
4 package generic_stack is
5 package List_Pack is new
6 Ada.Containers.Doubly_Linked_Lists (element_type);
7 use List_Pack;
8
9 protected type Stack is
10 procedure Push (Item : element_type);
11 entry Pop (Item : out element_type);
12 function Is_Empty return Boolean;
13 private
14 Buffer : List := Empty_List;
15 end Stack;
16
17 end generic_stack;
The package creates an Ada protected type. A protected type
or protected object is a passive unit of concurrency which is implicitly
protected from race conditions. There are three kinds of methods available to
be defined within a protected type. Protected procedures implicitly acquire an
unconditional exclusive read-write lock on the data in the protected type.
Protected entries implicitly acquire a conditional exclusive read-write lock on
the data in the protected type. A task suspends while the entry boundary
condition evaluates to false. The suspended tasks are placed in an entry queue
so that they can be activated when the boundary condition evaluates to true.
The third kind of method available for a protected object is a function.
Protected functions are limited to read-only access to the data in the
protected type. Protected functions acquire a shared read lock on the data in
the protected object.
The implementation of the package is in a separate file
containing the package body.
1 package body generic_stack is
2
3 -----------
4 -- Stack --
5 -----------
6
7 protected body Stack is
8
9 ----------
10 -- Push --
11 ----------
12
13 procedure Push (Item : element_type) is
14 begin
15 Buffer.Append (Item);
16 end Push;
17
18 ---------
19 -- Pop --
20 ---------
21
22 entry Pop (Item : out element_type) when
23 not Buffer.Is_Empty is
24 begin
25 Item := Buffer.Last_Element;
26 Buffer.Delete_Last;
27 end Pop;
28
29 --------------
30 -- Is_Empty --
31 --------------
32
33 function Is_Empty return Boolean is
34 begin
35 return Buffer.Is_Empty;
36 end Is_Empty;
37
38 end Stack;
39
40 end generic_stack;
The push procedure implicitly locks the Buffer when it
begins executing and unlocks the Buffer as the procedure completes.
The pop entry only executes when Buffer.Is_Empty evaluates
to false. When that condition is met any immediate call, or any task waiting in
the entry queue is allowed to execute the entry. The default queuing policy of
the entry queue is FIFO and all tasks suspended in the entry queue will be
executed before any new call can be executed. The shared read-write lock is
applied when execution of the entry starts and is release upon completion of
the entry.
The Is_Empty function can only execute when no read-write
lock is applied to the Buffer data element. Upon starting execution the function
applies a shared read lock, allowing any number of tasks to read simultaneously
and preventing any procedure or function to execute until the function
completes and releases its shared read lock.
The main procedure, which is the program entry point for
this example, follows.
1 with Ada.Text_IO; use Ada.Text_IO;
2 with generic_stack;
3
4 procedure Main is
5 package int_stack is new generic_stack (Integer);
6 use int_stack;
7
8 The_Stack : Stack;
9
10 task producer is
11 entry Start;
12 end producer;
13
14 task body producer is
15 begin
16 accept Start;
17 Put_Line ("Producer started.");
18 for I in 1 .. 20 loop
19 The_Stack.Push (I);
20 Put_Line ("Pushed" & I'Image);
21 delay 0.001;
22 end loop;
23 end producer;
24
25 task consumer is
26 entry Start;
27 end consumer;
28
29 task body consumer is
30 Num : Integer;
31 begin
32 accept Start;
33 Put_Line ("Consumer started.");
34 for I in 1 .. 20 loop
35 The_Stack.Pop (Num);
36 Put_Line ("Popped" & Num'Image);
37 end loop;
38 end consumer;
39
40 begin
41 consumer.Start;
42 delay 0.01;
43 producer.Start;
44 end Main;
Line 5 creates an instance of the generic_stack package
passing the type Integer as the generic parameter. This results in a stack of
integer values.
Line 8 declares an instance of the Stack type named
The_Stack.
Line 10 declares the interface for the producer task. This
task has one entry named Start.
Line 14 declares the implementation of the producer task.
Line 16 accepts the Start entry. The producer task will
suspend until another task calls its Start entry. Task entries implement a
Rendezvous logic allowing synchronous coordination of tasks. After accepting
Start the producer executes a for loop 20 times, each time pushing the current
value of the loop control variable onto the stack, displaying a message to
standard output and then delaying (sleeping) for 0.001 seconds.
The consumer task declaration begins at line 25. The
consumer also has a Start entry.
The consumer task accepts its start entry at line 32 and
then pops 20 values off of the stack. The consumer task has no delay statement.
The consumer tasks will then complete its iteration before the producer task
pushes another value onto the stack. Each call to the pop entry will therefore
encounter an empty stack until the producer pushes another value onto the
stack.
Both the producer task and the consumer tasks begin
execution immediately, but both tasks suspend until their Start entry is
called.
Line 40 begins execution of the main procedure which is also
the top-level task for the program. Line 41 calls consumer.Start. Line 42
causes the main procedure to delay for 0.01 seconds before line 43 calls
producer.start.
This delay in starting the tasks ensures that the consumer
must wait at least 0.01 seconds before the first data will be pushed onto the
stack. In other words, the stack will be empty for at least 0.01 seconds.
The output of this program is:
Consumer started.
Producer started.
Pushed 1
Popped 1
Pushed 2
Popped 2
Pushed 3
Popped 3
Pushed 4
Popped 4
Pushed 5
Popped 5
Pushed 6
Popped 6
Pushed 7
Popped 7
Pushed 8
Popped 8
Pushed 9
Popped 9
Pushed 10
Popped 10
Pushed 11
Popped 11
Pushed 12
Popped 12
Pushed 13
Popped 13
Pushed 14
Popped 14
Pushed 15
Popped 15
Pushed 16
Popped 16
Pushed 17
Popped 17
Pushed 18
Popped 18
Pushed 19
Popped 19
Pushed 20
Popped 20
Clearly the program did not encounter any exceptions, yet
the consumer could only pop values after they were pushed onto the stack.
No comments:
Post a Comment