Bark of the byte

Running with bytes and other wild creatures

Part 3: Locked

In part 2 we found out how doing things at the same time can cause serious problems. In this post we investigate one way to regain control and enforce order - locking. 

HMS Optimize

The cadets consulted page 256 of the appendix of the Materializer CHS (Concurrent Helper System) manual and indeed discovered that there is an Orb of Power and it does say at the bottom of the page: 

    *** to ensure correct operations of your Materializer CHS by more than one person or robot, use the Orb of Power to synchronize requests.

After digging through the numerous accessories that came with the Materializer CHS they were able to uncover the Orb of Power which had a note stuck to it that said: 

The rules of the Orb of Power: 
Rule 1 - Whosoever holds the Orb of Power and they alone may set recipe items.
Rule 2 - Whosoever holds the Orb of Power and they alone may start the Materializer. 
Rule 3 - Whosoever holds the Orb of Power and they alone will clear the recipe items delivery of their materialised object. 
Rule 4 - Whosoever holds the Orb of Power shall relinquish said Orb of Power unto the next person or robot that is awaiting the Orb of Power.

They have all agreed that this is simple enough and are full of confidence. Have a quick glance at page 3 of the Materializer CHS manual and click 'Join HMS Optimize' to see what transpires. 
 


That is more like it. Back slapping and hooras all round. Top Brass is pleased and is using the words 'commendable', 'promotions', 'bonuses' and 'medals'. The correct objects were materialized and sanity and order have once again returned to HMS Optimize. 

   Several weeks pass...

Top Brass is using the words 'lazy', 'slow' and 'bring back the whip'. It turns out that the throughput of objects is actually slower than when the Alchemist was responsible for producing the objects, moreover Top Brass has noticed that the cadets seem to spend much of their time relaxing and chatting among themselves which Top Brass does not like. Now, since the Alchemist was very unpopular, the situation is not dire enough to actually reinvigorate the search effort to try to find him, but still, Top Brass is not happy. 

The first problem is that the Orb of Power essentially serializes the process, only one set of ingredients can be loaded at a time and only one object can be materialized. The second problem is that because only one Cadet can hold the Orb of Power at a time the other two Cadets have to wait for the Orb to be relinquished. This means that the Cadets spent much of their time sitting around doing not much.  

In part 4 we will investigate how to improve performance and bring levity back to Top Brass' disposition.

Discussion

The Orb of Power is similar to locks in programming languages. There are many different types of locking mechanisms such as file locks, database locks and thread locks. Essentially, they all make sure that access to a resource is only provided to one thread of execution at a time. Often a programmer will define a state that must be consistent when a resource is unlocked. This is similar to the Orb of Power rule that the ingredients are always cleared before relinquishing. This means that whenever the Orb of Power is not held, the ingredient slate will be in a defined and known state, i.e. clean. For a programming example, whenever a lock is not held the state of a file might be that it is compressed. This means that whenever another thread obtains the lock it knows the state of the file, it is compressed. There is no risk of a thread trying to read a half-compressed file. This consistent state is something that we will come back to when we discuss reentrant locks in an upcoming post. 

Lets implement locking in the code from part 2 and confirm that it solves the problem. Note the locks in red. 

       const int global_threadCount = 2;
        const int global_workerIterations = 10000000;
        int global_totalOperations = 0;
        double[] global_results = new double[global_threadCount];
        object gl_lock = new object();
        void DoWork2( object parm )
        {            
            const double divideBy = global_workerIterations / 10;
            double runningCalc = 0;
            for( int i = 0; i < global_workerIterations; i++ )
            {
                runningCalc = runningCalc + i / divideBy;
                Monitor.Enter( gl_lock );
                global_totalOperations++;
                Monitor.Exit( gl_lock );
            }
            global_results[(int)parm] = runningCalc;

        }
        [TestMethod]
        public void Conc3_multiThreadContention()
        {
            var threads = new List<Thread>();
            for( int count = 0; count < global_threadCount; count++ )
            {
                Thread thread = new Thread( DoWork2 );
                thread.Start( count );
                threads.Add( thread );
            }
            for( int count = 0; count < global_threadCount; count++ )
            {
                Thread thread = threads[count];
                thread.Join();
            }
            double expectedResult = 0;
            for( int count = 0; count < global_threadCount; count++ )
            {
                if( count == 0 )
                {
                    expectedResult = global_results[count];
                }
                else
                {
                    Assert.AreEqual( expectedResult, global_results[count] );
                }
            }
            Assert.AreEqual( global_threadCount * global_workerIterations, global_totalOperations );
        }
    }


Hooray! Similar to the way that the Orb of Power prevented more than one Cadet from changing the recipe at a time, the lock prevents more than one thread from incrementing global_totalOperations at a time.

Loading