DDL Implicit Commit

We all know that DDL implicitly commits transactions. However, I was not aware that it commits both BEFORE and AFTER the DDL.

I ran the following code from session 1:

SQL> create table t1 (x number);

SQL> create or replace procedure p1 as
2 begin
3 update t1 set x=2;
4 commit;
5 end;
6 /

Then in session 2:

SQL> update t1 set x=3;

1 row updated.


Now back in session 1:
SQL> exec p1

Session 1 promptly hangs, due to session 2 locking the row in t1.

Now in session 2, I run:

SQL> drop procedure p1;

I expected session 2 to hang as well, which makes it a deadlock.

However, what I saw was:
Procedure dropped.
in session 2 and
PL/SQL procedure successfully completed.
in session 1.

Which could only happen if the DDL drop procedure commited session 2, which caused session 1 to finish running the procedure, which enabled the drop to work.

Coffman et al (1971) showed that four conditions are necessary for a deadlock. The third condition is – no preemption – resources granted cannot be taken away from a process. By causing DDLs to force a commit before they run, Oracle forced preemption and avoided deadlocks.

I like that. Sometimes I hate the fact that DDLs force a commit, but now I see the benefits.
I’ve heard that in Postgres DDLs are transactional and can be rolled back. I wonder if my scenario would deadlock in Postgres.

Barbershop Queue Demo

Yet another classic concurrency problem.

This time, we have a barbershop. The shop employees one or more barbers. Customers come into the shop. If one of the barbers is free, he will give the customer a haircut. If all barbers are busy, the customer will wait in line until one of the barbers can take care of him. Barbers will handle customers on “first come first serve” basis. Of course, we don’t want to have two barbers working on the same customer at the same time, or giving haircuts to customers who no longer need them. We also don’t want barbers blocking each other, or blocking the entrance to the shop while working.

Its a nice problem, because you can check different queuing scenarios – fixed number of barbers while the number of customers grows, or how many barbers are needed to operate a shop with about 10 customers every second.

You can see my code here.

Normally, you would start one process running add_customers, with parameters telling it how many customers on average enter the shop every second, and how long should the demo run.
Then you add a process for each barber, with parameters for how long it takes to give a haircut, and how long the demo will run.

Something like:

(echo exec barber_shop.add_customers\(3,60\) | sqlplus -s scott/tiger)&
(echo exec barber_shop.add_barber\(0.3,60\) | sqlplus -s scott/tiger)&
(echo exec barber_shop.add_barber\(0.3,60\) | sqlplus -s scott/tiger)&
(echo exec barber_shop.add_barber\(0.3,60\) | sqlplus -s scott/tiger)&


Comments are welcome 🙂

Note: On rare occasions, the “add_customers” process waited over a minute between updating the customers and committing. “add_barber” did not run at all during that minute.
I suspect either my OS getting stuck somewhere or Oracle’s resource manager. However, when it happened I did not check v$sesstat or ASH to see what happened during that minute. Now it doesn’t reproduce, and I don’t have the session_id that had the issue to investigate.

If anyone tries running my code and runs into the same bug, please collect helpful events and timed statistics that may help debug it. I’ll buy a beer to anyone providing information that helps catch the bug (unless they are non-drinkers, in which case they can get orange juice 😉 ).

Dining Philosophers

The Dining Philosophers problem is probably the most famous of the classic synchronization problems. Posed and solved by Edsger Dijkstra in 1965, it became famous not because it is practical, but because it demonstrate in a nicely visual way some of the dangers inherent in careless sharing of resources.

Five philosophers are sitting around a round (oak) table. Each of the five philosophers has a bowl of rice, and between every two bowls there is a single chopstick. As illustrated in the following diagram:

Philosophers never talk to each other. They spend their time thinking. When a philosopher becomes hungry, she attempts to pick up the two chopsticks closest to her (the ones that are shared between her and her left and right neighbors). Each philosopher can only pick up one chopstick at a time. Then she eats, without putting down the chopsticks. When she is done, she puts both chopsticks down and resumes thinking.

We must find a method that will allow the five philosophers to share five chopsticks and eat without letting any philosopher starve from prolonged lack of access to chopsticks.

As I wrote above, this is a very famous and non-practical concurrency problem. Surprisingly, no one demonstrated it in PL/SQL on Oracle database yet.

So, here are three different “solutions” to the dining philosopher’s problem for Oracle.

The code you’ll find in the link contains several sections:

1. Setup code to create the tables with the philosophers and their chopsticks.
2. set_status procedure that allows the philosopher to announce their status (eating, hungry) to us, so we can monitor their progress. This is an autonomous transaction, because we don’t want the philosophers to drop their chopsticks while announcing that they are eating.
3. Three different eating functions, representing the three typical solutions to shared resource problems.
4. add_philosopher code that will allow us to add philosophers to the table and watch them compete for chopsticks.

I also have a nice shell script that runs the five philosophers we need to make the problem interesting.

Now, some explanation about the three eating procedures.

1. The first one is the most trivial one. A philosopher grabs the right chopstick, then the left one and then eat. If any stick is busy, we wait. Note that for some time efficiency (and CPU killing) the philosophers eat very very fast in this version. Run this version and very soon, all philosophers will simultaneously pick up their right sticks and wait for the left to become free. They could wait a long time, but Oracle will soon choose one of them as the deadlock victim and allow the other four to proceed eating in peace.
2. An attempt of avoiding deadlocks – Each philosopher picks up her right stick, and if she sees the left one is taken, she drops her right stick and tries all over again. This will ensure no deadlocks (since waiting philosophers will not hold their sticks), but we are likely to encounter a situation where a philosopher keeps picking up and dropping his right stick without ever getting to eat. It is unlikely that this will continue forever, but it may continue enough to make our philosopher very unhappy with her response times. Since each philosopher should be able to eat on average 400ms every second, if a philosopher did not eat for an entire second we will consider her dead from starvation. If you run this example, you should see at least one philosopher dead from starvation.
3. At last a good solution! We avoid starvation by not dropping the stick we are already holding, and avoid deadlocking by switching the order in which we pick up the sticks. One of our philosophers will pick his left stick first. This solution is also called “partial hierarchy” – we make sure the blocking graph will be a tree and not a cycle. Run this example and see that you encounter no deadlocks and no starving philosophers.

Readers who made it this far – this example will be a part of my HotSos presentation (demonstrating two concurrency sins – deadlocks and starvation). Any comments are appreciated. If you ran my code and had problems, or worse, failed to run into dead philosophers, let me know. If you think my code plain sucks, let me know. If you didn’t understand what I’m trying to say or why I’m trying to say it, also let me know.