Divine Comedy*

Last night I had a dream. In my dream, an angel showed me heaven and hell. The first place we went to was a large hall filled with round tables. Around each table were 5 souls. All of them wearing white. The place was quiet and the only sound you can hear are the noise of the chopsticks as each soul eats the spaghetti from his or her plate. The spaghetti was unlimited and placed in a big bowl at the center of each table. The chopsticks were placed in such a way that there is one stick between each plate. No soul can eat unless he or she has taken his or her left and right chopsticks. If a soul is not eating, he or she spends this time thinking.

I asked the angel “What is this place?” The angel said “This is hell.” I asked the angel “But why is this hell? This seems to be a very peaceful place with people doing nothing but eat and think.” Then the angel pointed me to one table and said “What do you see?”. I looked at the table and I saw souls starving but never dying. As I looked closer, I noticed that all of them were able to pick their right chopsticks but not the left chopsticks. Suddenly I realized that many tables have souls starving forever.

I was about to ask the angel why they starved when the angel suddenly showed me another place. People were also wearing white and they also have a bowl of spaghetti at the center of each table. Two things were noticeably different from hell. Each table was inside its own room and there was a waiting area per room that can accommodate 4 souls. There were 5 seats per table, but the maximum number of souls per table was only 4. I observed the entire hall and I did not see a single soul starved. Everyone had a happy look on their face and were either eating or thinking. I asked the angel “What is this place?” The angel said “This is heaven. You can see that there are a maximum of 4 souls per table. A soul that is not seated at the table is in the waiting area.”

Suddenly, I woke up from my dream without any idea of what it means. What could the dream mean? I spent the whole day thinking about it.

Interpretation of the Dream

The chopsticks used by the souls are binary semaphores since no two of them can grab the same stick at any time. To model the behavior of the souls in hell, we need an array of 5 semaphores (chopsticks) and the following algorithm:

#loop forever
think()
wait(left chopstick)
wait(right chopstick)
eat()
signal(left chopstick)
signal(right chopstick)

The figure below shows a round table with 5 plates. The chopsticks are colored green and placed in between the plates. For a soul to eat, he/she should have both chopsticks first.


Since the chopsticks are semaphores, then no two souls can be holding the same chopstick at the same time. To see this, let’s make use of the following properties from the previous post:

1. \displaystyle \#CS = \#wait - \#signal . For chopstick i, the number of souls holding this chopstick at any time is equal to \#CS.
2. \displaystyle S.V = 1 - \#CS. Using this property to compute \#CS, we get

\displaystyle \#CS = 1 - S.V

Since S.V \ge 0, then \#CS \le 1, that is, at most one soul is holding the chopstick i at any given time.

The reason why the souls got starved is because it is possible that all of the souls grabbed their right forks at the same time leaving no single left fork to use.

The setup in heaven is subtly different. Instead of having 5 souls eating on the table at the same time, at least one of them waits for his turn in the waiting area (which is guarded by a room semaphore). To model this, we need an array of 5 semaphores (chopsticks) and a room semaphore initialized to 4. The following is the algorithm used by the souls in heaven:

# loop forever
think()
wait(room)
wait(left chopstick)
wait(right chopstick)
eat()
signal(left chopstick)
signal(right chopstick)
signal(room)

The diagram below shows a round table inside a room. The plates and chopsticks are arranged as before, but at least one seat is empty as indicated by the red plate corresponding to it. Any soul that is not inside the room is in the waiting area as shown by the stick figure.



Initially, all the souls are in the waiting area and the door to the room is guarded by the room semaphore. Since the initial value of the room semaphore is 4, at most 4 souls can enter the room at a time. Inside the room, the souls take their seats. Since at most 4 souls can be in the room, at least one seat is not taken. No soul is ever left starved in this system. Otherwise, a soul[i] can be blocked in one of three cases:

1. Blocked on his/her left chopstick. This means there is a soul[i-1] to his/her left that is using chopstick[i] as his/her right chopstick. By assumption of progress, this means that soul[i-1] will eventually execute signal(right chopstick). Hence, soul[i] will be able to pickup his/her left chopstick.
2. Blocked on his/her right chopstick. Soul[i] is not able to pick up his/her right chopstick because soul[i+1] is using this chopstick as his/her left chopstick and will never release it until he/she has eaten. But the only way for soul[i+1] to eat is if he/she is able to pick up the right chopstick which, by induction, is also being used by another soul to the right of soul[i+1]. However, since there is at least one seat that is vacant, there is a right chopstick that is not being used by any soul and hence by progress, at least one soul can eat and eventually soul[i] can eat.
3. Blocked from entering the room. If we use a first come first served policy, eventually, all souls can enter the room.

By using an extra locking mechanism, the souls in heaven are infinitely happier than the ones in hell.

* Disclaimer: This is a work of fiction and should not be taken literally aside from it’s algorithmic content. In concurrency literature, this is called the Dining Philosophers problem. For more information, please consult the book “Principles of Concurrent and Distributed Programming” by M. Ben-Ari.

Advertisements

Mathematically Romancing Mt Mayon

The name Mayon is short for Daragang Magayon, or “Beautiful Lady”, which is the legend associated with Mt Mayon. No wonder, I still find myself captivated by its charms after visiting it three weeks ago.

While playing with google maps this sunday, I decided to take a look at Mt Mayon and I was hoping I could get a three dimensional view of the beauty. I was disappointed. Although there is a 3D view, but it was not beautiful at all. Luckily, google map provides a topographical information of Mt Mayon. Suddenly, I was inspired to recreate the view of Mt Mayon using that information and using the tool called R.

First thing I did was to capture the image from the google maps and saved it as JPEG. Using the ReadImages library of R, I loaded the image and plotted it.

# load the library
library("ReadImages")

# read the file and plot
x=read.jpeg("mount_mayon_topography2.jpg")
plot(x)

# add grid lines
grid(nx=20,ny=20,col="red")

The result of the code above is a plot of the image with red grid lines, as shown below.


You will notice that the image contains contour lines with a height information associated with it. I used the grid lines to manually interpolate the height of Mt Mayon at each intersection. I started at the bottom line and worked myself upward from left to right. However, I got lazy interpolating from point to point so I just stopped when I reached the middle line. I decided that the upper half of the image is just a mirror image of the bottom so I might as well use the same numbers. Here’s a dump of the interpolated height from the bottom half of the image:

0,        0,    0,     0,     0,    0,400,400,400,450,450,420,400,350,300,280,250,220,200,
0,     100,200,300,400,420,450,500,550,570,550,500,480,420,400,380,350,250,200,
200,300,350,400,420,500,550,580,600,650,600,600,580,550,500,400,350,300,320,
280,350,380,400,500,580,610,650,780,800,750,730,650,600,500,450,380,310,300,
300,400,430,500,580,650,780,800,950,990,970,900,800,700,580,500,520,350,300,
310,400,480,580,610,750,840,1000,1100,1200,1150,1100,1000,800,650,550,450,380,350,
320,450,500,600,700,800,1000,1200,1350,1500,1500,1380,1180,900,800,650,510,400,350,
350,450,500,600,750,900,1100,1350,1600,1800,1800,1600,1350,1100,900,700,550,450,350,
370,450,500,600,780,900,1200,1500,1800,2100,2000,1800,1500,1180,900,700,550,500,350,
380,450,500,620,780,970,1200,1500,1900,2250,2200,1800,1400,1150,900,700,550,520,400,

Reflecting this information about the middle line and inputting this to R, we get

z=c(0,        0,    0,     0,     0,    0,400,400,400,450,450,420,400,350,300,280,250,220,200,
0,     100,200,300,400,420,450,500,550,570,550,500,480,420,400,380,350,250,200,
200,300,350,400,420,500,550,580,600,650,600,600,580,550,500,400,350,300,320,
280,350,380,400,500,580,610,650,780,800,750,730,650,600,500,450,380,310,300,
300,400,430,500,580,650,780,800,950,990,970,900,800,700,580,500,520,350,300,
310,400,480,580,610,750,840,1000,1100,1200,1150,1100,1000,800,650,550,450,380,350,
320,450,500,600,700,800,1000,1200,1350,1500,1500,1380,1180,900,800,650,510,400,350,
350,450,500,600,750,900,1100,1350,1600,1800,1800,1600,1350,1100,900,700,550,450,350,
370,450,500,600,780,900,1200,1500,1800,2100,2000,1800,1500,1180,900,700,550,500,350,
380,450,500,620,780,970,1200,1500,1900,2250,2200,1800,1400,1150,900,700,550,520,400,
370,450,500,600,780,900,1200,1500,1800,2100,2000,1800,1500,1180,900,700,550,500,350,
350,450,500,600,750,900,1100,1350,1600,1800,1800,1600,1350,1100,900,700,550,450,350,
320,450,500,600,700,800,1000,1200,1350,1500,1500,1380,1180,900,800,650,510,400,350,
310,400,480,580,610,750,840,1000,1100,1200,1150,1100,1000,800,650,550,450,380,350,
300,400,430,500,580,650,780,800,950,990,970,900,800,700,580,500,520,350,300,
280,350,380,400,500,580,610,650,780,800,750,730,650,600,500,450,380,310,300,
200,300,350,400,420,500,550,580,600,650,600,600,580,550,500,400,350,300,320,
0,     100,200,300,400,420,450,500,550,570,550,500,480,420,400,380,350,250,200,
0,        0,    0,     0,     0,    0,400,400,400,450,450,420,400,350,300,280,250,220,200)

Next, I generated the coordinates of the x and y plane:

myx=seq(-9,9,1)
myy=seq(-9,9,1)

To generate the 3D view, I used the persp3d function of the rgl library and animated the 3D plot so that we can see the plot 360 degrees.

library(rgl)
persp3d(myx,myy,z,col="darkseagreen", aspect=c(4,4,1))
play3d(spin3d(axis=c(0,0,1), rpm=8), duration=20)

The result of the above code is an animated plot of Mt Mayon using partial topographical information. Shown below is the animation:

This is indeed a great waste of time. But I guess, that’s what you do when you fall in love…mathematically!

Semaphorically Speaking

When I was child, our family lived about 60 kilometers away from the city. Once or twice a month we go to the city which took about an hour and a half one way. On the way to the city, we have to pass a stretch of very narrow road that was at the side of a very deep cliff. Many people have already lost their lives in that cliff when the bus they rode plunged into the cliff. In order to prevent this, a mechanism was setup that allowed only one bus at a time to enter that section of road, whether going one way or the other. In order for each end of the road to determine if a bus is traversing at any moment, they used a telephone to signal the other party so that the other buses can wait before taking their turn. It was always a frightening experience each time we pass that road. In computer science, we can view the dangerous narrow section of road as a critical section and the buses traversing this road as the processes. To guarantee mutual exclusion, the telephone system that signals each end of the road is called a semaphore.

We see semaphores everyday. The traffic light is a semaphore that protects the vehicles from bumping each other in that critical section of the road called the intersection. Semaphores are also used in the navy. Below is an example of a semaphore used in the US Navy.


In the last post, we talked about concurrency and an algorithm to ensure correctness of concurrent algorithms. In this post, we will present another mechanism to ensure correctness of concurrent programs. That mechanism is called a semaphore and was first proposed by Edsger Dijkstra. A semaphore* is a data structure S that is composed of an integer V and a set L and being modified by two atomic functions. The first function is called wait and is defined as follows:

wait(S)
     if S.V > 0
        S.V <- S.V -1
     else
        S.L <- S.L union p
        p.state <- blocked

The wait function is called by a process p on a semaphore before it enters the critical section. If the value of S.V is not zero, S.V is decremented by 1 and the process p is allowed to continue its execution. Otherwise, the process p is blocked and is put on the set S.L.

The signal function is defined as

signal(S)
    if S.L = empty set
       S.V <- S.V + 1
    else 
       select a process q in S.L
       S.L <- S.L - {q}
       q.state <- ready

When a process p is done in its critical section, it will call the signal operation on the semaphore S. If the set S.L has no blocked processes, it will increment the value of S.V by 1, otherwise a process q is selected from the set S.L and its state is set to “ready”.

To use the semaphore construct, a typical concurrent program will be written like the one below:

# loop forever
noncriticalSection()
wait(S)
criticalSection()
signal(S)

Simple Properties of Semaphores

In this section, we list some simple properties of semaphores that we can use in proving correctness. By properties, we mean those mathematical properties that remain invariant under whatever state of the computation.

1. From the definition of the wait and signal functions, we can see that the value of S.V never goes negative, that is

\displaystyle S.V \ge 0

2. If initially S.V = k, then we can compute the subsequent values of S.V by counting the number of calls to wait and signal (with some qualifications). If k processes call the wait function, then the value of S.V goes down to 0. If all of these processes call the signal function, then the value of S.V goes back to k. If however, a process calls wait and the value of S.V is already 0, then S.V will just remain zero and the process is blocked. We say that the call to wait has failed an we will not count this call. If another process calls on signal and seeing that S.L is not empty, the S.V value will remain the same. This call to signal is also not counted. Having laid down the rules for counting the calls to wait and signal, we can see that

\displaystyle S.V = k - \#wait + \#signal

where \#wait and \#signal are the number of calls to wait and signal, respectively.

3. At anytime, the number of processes executing the critical section is found by counting the number of processes entering the critical section by a successful call to wait, minus the number of processes leaving the critical section by a successful call to signal:

\displaystyle \#CS = \#wait - \#signal

Correctness of the Semaphore Solution for Two Processes

As we have discussed in the last post, to prove correctness we need to show that the algorithm is mutually exclusive, free from deadlock and starvation.

1. Mutually Exclusion – Let S.V = 1 initially. At anytime during the execution, the number of processes in the critical section is given by property 3 above, that is, \#CS = \#wait - \#signal. From property 2,

\displaystyle S.V = 1 - \#CS
\displaystyle S.V + \#CS = 1
\displaystyle \#CS = 1 - S.V

Since by property 1 S.V \ge 0, therefore \#CS \le 1. That is, there can be at most one process in the critical section at anytime.

2. Freedom from deadlock – Two processes can deadlock if the value of S.V = 0 and neither are in the critical section (\#CS = 0). By property 2 and 3,

\displaystyle S.V = 1 - \#CS

Since S.V = 0 and \#CS = 0, substituting this to the equation above gives us

\displaystyle 1 = 0,

a contradiction

3. Freedom from Starvation – Suppose a process q, upon calling wait, sees that S.V = 0, and is blocked to starvation in S.L. By property 2 and 3,

\displaystyle \#CS = 1 - S.V = 1 - 0 = 1

which means that the other process p is in the critical section. By assumption of progress, process p will eventually call signal and will pick one process from S.L to enter the critical section. Since there is only one process that is blocked, and that is q, process q can then enter its critical section, contradicting the assumption that it is starved.

* For more information, consult the book “Principles of Concurrent and Distributed Programming” by M. Ben-Ari.