Using TRIZ in Computer Science - Concurrency

Kevin C. Rea, Principle Consultant
REA Consulting
E-mail: kcronline@gmail.com
Web site: http://kevincrea.com/

Introduction

TRIZ offers a wide-ranging series of tools and methods to help designers and inventors to solve problems in creative and powerful ways. These methods have centered around traditional sciences and engineering disciplines such as Physics, Mechanical, Electrical, Chemical Engineering; however, TRIZ in Computer Science is new.

In this article, I attempt to break some "Psychological Inertia" in the area of Computer Science.  The problem presented is a concurrency programming problem known as the "Roller Coaster Problem."  In this problem, we will use TRIZ to create an algorithm used to simulate the actions of our roller coaster. 

Concurrency

Concurrent programming is the activity of constructing a program containing multiple processes that execute in parallel.  These processes compete for access to critical resources and cooperate in performing some task. In our example, we will be simulating the operations of a Roller Coaster in which a single roller coaster car with a capacity of N will represent one process and passengers will represent "n" processes.  These passengers simply get in line for a ride on our roller coaster, board when the time is right, take a ride, disembark and wander around the amusement park until they ready for another ride.  This process continues for as long as we want our simulation to run.  Queuing, loading, riding and unloading of passengers are analogous to several issues facing concurrency today, such as shared memory access, distribution of data, mutually exclusive access to a shared file

Pretty simple uh?  Not really, as human beings it is not natural for us to think in terms of parallel execution while we are writing software programs. Software engineers typically stick to sequential programming, progressing from step A to step B in the spirit of achieving some goal.  Given this pattern and the fact that we are starting to depend on software to run our critical systems, could we be facing a software crisis in the near future?  Are our programs dependable and fault tolerant as they "could" be?  Universities spend much time developing formal techniques based on solid mathematical foundations in the Computer Science field; yet without a systematic way of applying formal techniques to real practice (in a way that it is understandable to the average hacker, oops I mean programmer), we cannot maximize the quality of our software systems.

The Problem

Here is the problem definition of our synchronization problem:

•  Suppose there are n passenger threads and one car thread. The passengers repeatedly wait to take rides in the car, which holds C passengers. The car can go around the track only when it is full. The car takes T seconds to go around the track; this time is fixed. After getting a ride, each passenger gets off the coaster and wanders around the amusement park for W seconds before returning to the roller coaster for another ride; W is random for each passenger.

• A passenger cannot get on the coaster while there are still passengers to get off.

• Passengers load and unload "ON THE SAME SIDE" of the coaster.

• State the Purpose(s) of our System,

  • To give passenger(s ) repeated rides on the roller coaster,

• State the Objective(s) of our System,

  • Ensure safety throughout the system,

  • Avoid having passengers waiting in line more than is necessary.

Below is a snapshot of our system at one point during the simulation[KCREA1] .  A car, full of passengers has just arrived; the passengers are about ready to disembark from the ride

.

·  Table 1 S-Field Action Legend[i]

Our S-Field Models using S-Field Analysis Designation[ii]:

1. Passengers get on car at time 1,

2. Passengers get off car at time 1,

3. The track-motor moves the car at time 1,

4. Conflict 1: We have a requirement to load and unload but we have to wait until "ALL" the passengers are off before we can load the waiting passengers.  Is this efficient?

5. Conflict 2: In order to execute the ride, we need the car full and nothing less.  What happens if we need one more passenger and nobody shows up for a long time - do we penalize our loaded passengers by unfairly waiting?

Describe the Mini-problem.

• The system for giving passengers a ride includes a car on a track and waiting passengers in loading station.

State the Opposite Versions of the Conflict.

• Conflict 1 - An attempt to eliminate or weaken the harmful action by altering its tool would degrade the useful action.

If we load waiting passengers immediately after arrival of the car [iii](R1) in order to minimize the time between rides[iv] (positive effect 1+), the safety of the passengers will be deteriorated[v] (negative effect 1-).

• Conflict 2 - An attempt to improve the useful action (or avoid its deterioration) by the opposite altering of the same tool would keep or worsen the harmful action.

If we do not load passengers immediately after arrival of the car[vi] in order to improve the safety of the passengers[vii], the ride efficiency would be deteriorated[viii].

• A minimum alteration of the system has to provide minimizing the time between rides[ix], without deteriorating the safety of the passengers and without any complication or deterioration of the system or anything else.

Increase the Degree of the Conflict.

Extreme Conflict 1.

State extreme requirements ER1 so that the imaginary positive effect 1++ would be the best, but the imaginary negative effect 1 - - would be the worst:

If (describe the extreme requirement ER1) there are no people waiting in line, (State the best positive effect 1++) the ride efficiency would be 100%, but (State the worst negative effect 1--) the ride would stop since there are no new passengers.

Draw a model of the Extreme Conflict 1.  Indicate the extreme requirement ER1, positive and negative effects.

Extreme Conflict 2.

State extreme requirement ER2 so that the imaginary positive effect 2++ would be the best, but the imaginary, negative effect 2- - would be the worst:

If (describe the extreme requirement ER2) there are many people waiting in line, (State the best positive effect 2++) the ride never stops ($$$), but (State the worst negative effect 2--) passengers might try to get on or off at the same time.

Draw a model of the Extreme Conflict 2.  Indicate the extreme requirement ER2, positive and negative effects.

Select the Version of the Conflict.

Extreme Conflict 2 is better for giving passengers repeated rides on the roller coaster.

Describe the Model of the Mini-problem.

• Draw the model of the selected conflict (please see ER2 above).

• Describe the model of the selected conflict.

The many people in line keep the ride going, but people getting on and off the car at the same time compromise safety.

• It is necessary to identify an X-resource:

1. X-resource has to eliminate hazards of the ride.

2. X-resource must not deteriorate the ride efficiency.

3. X-resource must not complicate the system.

4. X-resource must not cause any new harmful action.

5. Show X-resource on the model of the selected conflict.

Study the Operating Zones of the Conflicting Actions.

Lets analyze the zones of interaction to identify possible conflicts; below depicts several possible zones of the scenario. Zone one deals with the queuing or ordering of passengers that want to ride the coaster.  Zone two focuses on the barrier between the waiting passengers one a car AND the passengers getting off the ride.  Continuing on, we have Zone three, which is the car itself; Zone four and Zone five deal with the car arriving and leaving the loading station.

Zone One: has to have at least one passenger in the line.

Zone Two: departing passengers get OFF and ON.

Study the Operating Time of the Conflicting Actions.

"npass" is the number of passengers that have boarded.

Passengers are trying to get ON/OFF.

• From analyzing the zones and operating periods, zone two needs to be free while passengers are getting OFF,

• AND zone two needs to be free while passengers are getting ON.

State IFR-1:

X-resource eliminates the passengers getting off and on at the same time during the operating time and within the operating zone and without any complication of the system while keeping the ride capable of giving passengers repeated rides on the roller coaster.[x]

State IFR-1 for other resources.

The car itself eliminates the passengers getting off and on at the same time during the operating time and within the operating zone and without any complication of the system while keeping the ride capable of giving passengers repeated rides on the roller coaster.

The loading station itself eliminates the passengers getting off and on at the same time during the operating time and within the operating zone and without any complication of the system while keeping the ride capable of giving passengers repeated rides on the roller coaster.

The passenger eliminates the passengers getting off and on at the same time during the operating time and within the operating zone and without any complication of the system while keeping the ride capable of giving passengers repeated rides on the roller coaster.

Define Macro Level Physical Contradiction.

During the operating time, the operating zone (zone two) has to be free for passengers loading and later free for passengers unloading the car in order to ensure ride efficiency and safety.

From the above diagram, we see where the time conflict occurs; this is where we need to Apply Rules for Physical Contradiction Separation.

1. Separation in Space: If the roller coaster was setup to unload passengers on one side and load on the other, we could apply this rule however the coaster is not setup like this.

2. Separation in Time: We CAN however introduce our X-resource to manage access to the roller coaster car during loading and unloading thus performing mutual exclusion to the car.

Solution:  Introduce an object that synchronizes access to the car.  In real-life this would be the ride attendant, the one who takes your ticket and directs you when it is your time to get on the ride.  However, we need to simulate these actions using software; one solution applies TRIZ Principle #24 -- Mediator[xi], in Computer Science we have a similar abstraction called a "Monitor."  The Monitor manages access to a shared resource, such as entry into a critical section[xii] of code. This solution also supports the idea of TRIZ Principle 7 - Matreshka - "Nested Doll", where an object is inside another. In this case, we would put a Monitor object inside the "Person" object that would point to a common, shared resource that all the person objects would use.  Each passenger would have a monitor in their pocket that would beep when they can get on the coaster and beep when it is time to get off. Remember we are "simulating" using software and we are assuming that our passengers are like the Scarecrow from the Wizard of Oz - they have no brains!

Software Solution Outline: The following appendix focuses on a coarse-grained solution and translation to a fine-grained synchronization using a Monitor; my implementation is in Java and is available on a Web site listed later. I have also provided some hyperlinks related to synchronization.

Applying TRIZ to this problem was challenging since the S-Field analysis did not "feel" right.  The abstraction of "force" does not seem to fit in this context but, this is okay - we are exploring new frontiers for TRIZ.  As we discover more ways to bridge-the-gap between TRIZ and Computer Science, more solutions will become evident. Since computer science has been around for a very short period, it is a baby compared to physics and mechanical engineering.  However, we need CS to grow up quickly since software is becoming increasingly critical to our everyday lives.  Major breakthroughs are needed to avoid a software crisis; the Year 2000 problem is trivial compared to other "unknown" software failures - and TRIZ is perfect for discovering "unknown" future conflicts.  At least with Y2K, we are aware of the problem; if we construct a building that is sagging in the roof, we can see this since it is a physical entity and take appropriate action. Software is not that easy to see.  I hope others will join me in using TRIZ to solve existing software problems and ones we do not even know about yet.

The code below outlines a coarse-grained solution for the Roller Coaster problem.  The Monitor coordinates the access to the car; while the passengers and car threads perform as indicated below. Warning - CS jargons.

Some Preliminary Information:

Global Invariant (GI): This property needs to hold true during every critical assertion of the program. The Global Invariant implies the safety property; the safety property asserts that the program never enters a bad state. The so-called coarse-grained solution uses the following two synchronization constructs:

• <await B_i à S_i> and

• <S_j>

Using Programming Logic, the global invariant is formally verified in the coarse-grained solution.  Finally, the coarse-grained solution is mechanically translated to a fine-grained semaphore or monitor program that maintains the global invariant. This approach has many advantages.  First, this formal approach enables verification of programs being developed.  Second, the most important activity in the programming process lies at a high level; namely, specifying global invariants. Once an appropriate global invariant is specified, much of the rest of the process is mechanical.  Since TRIZ can help determine properties of a system, it can be used to determine global invariants. 

The Java programming language encourages the use of multiple threads, which we will use in our implementation to simulate the coaster and the passengers. Java provides monitor-like synchronization primitives. However, these primitives have limitations and thus we will apply our TRIZ exercise to create our own monitor system based on our coarse-gained solution.  This approach also makes our code platform independent.

Our TRIZ-driven Coarse-Grained Solution:

Using the synchronization constructs above for each appearance of such constructs in a coarse-grained solution, we define an independent method in a Java class.

(1)For each <await B_i à S_i>, define one public (non-synchronized) method and one private synchronized method, and declare one private specific notification lock (instance variable) of class Object. Let method_i,checkBS_i,and o_i be the public method, the private synchronized method, and the specific notification lock, respectively. We have the following declaration for o_i:

Private Object o_i = new Object();

      Public method method_i is defined as:

      public void method_I() {

            synchronized (o_i) {

                  While (!checkBS_i())

                        try {

                              o_i.wait();

                        } catch (InterruptedException e) {}

                  }

            }

      }

      Private synchronized method checkBS_I is defined as:

private synchronized Boolean checkBS_i () {

            if (B_i) {

                  S_i; return true;

            } else return false;

      }

(2)For each <S_j>, define a public method (non-synchronized) method, say method_j, as follows:

public void method_j () {

      synchronized(this) {

            S_j;

      }

}

(3)In each public method method_i and method_j, if execution of any statement may potentially change some guard B_k from false to true, add either of the following two statements at the end of the method (outside any synchronized block).

Synchronized(O_k) {Ok.notifyAll();}

Synchronized(O_k) {Ok.notify();}

Where O_k is a specific notification lock is associated with <await B_i à S_i>. If more than one thread may leave the construct <await B_i à S_i> when B_k becomes true, notifyAll should be issued; otherwise, notify should be issued.

"npass" is the number of passengers that have boarded the car.  "boarding" and "done" are counters used by the processes to track different stages of the simulation. "C" is the capacity of the car. "//" is a comment. The variables (npass, done, boarding) are flags indicating some time or step in our algorithm.

GI::    {npass >= 0}

Passenger::

Car:: 

<await npass >= C -> npass := npass - C>

<boarding := boarding + C>

<await done = C -> done := 0>

Please click here to see the Java implementation code.
(Opens in a new browser window)