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:

 

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?

Analyze the Conflict.

Describe the Mini-problem.

State the Opposite Versions of the Conflict.

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-).

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].

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.

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

  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.

Analyze the Resources.

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.

Define the Ideal Final Result (IFR).

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.

Conclusion:

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.

Appendix A: Coarse/fine-grained solution[xiii].

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:

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 Bi Si>, define one public (non-synchronized) method and one private synchronized method, and declare one private specific notification lock (instance variable) of class Object. Let methodi,checkBSi,and oi be the public method, the private synchronized method, and the specific notification lock, respectively. We have the following declaration for oi:

Private Object oi = new Object();

      Public method methodi is defined as:

      public void methodI() {

            synchronized (oi) {

                  While (!checkBSi())

                        try {

                              oi.wait();

                        } catch (InterruptedException e) {}

                  }

            }

      }

      Private synchronized method checkBSI is defined as:

private synchronized Boolean checkBSi () {

            if (Bi) {

                  Si; return true;

            } else return false;

      }

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

public void methodj () {

      synchronized(this) {

            Sj;

      }

}

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

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

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

 

Where Ok is a specific notification lock is associated with <await Bi Si>. If more than one thread may leave the construct <await Bi Si> when Bk 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::

<npass = npass +1> 

// Starting out assume that a seat is

// available on a waiting car,

// therefore, we increment the npass

// counter and get on the ride.

<await boarding > 0 boarding-->

// Wait until "boarding" is greater

// than zero then decrement

TAKE A RIDE

<done++>

// When the ride is over, increment

// done indicating my ride is over

Car:: 

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

<boarding := boarding + C>

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

Appendix B: Java Implementation Source Code

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

[i] TRIZ Consulting Technology Course, Zinovy Royzen, TRIZ Consulting Inc., 1996.

[ii] S1, S2, S3, or A, B, C, or S(name)

Objects, components, parts, substances

S1.1, S1.2, or A1, B2

Subsystems, components, parts, substances of S1 or A
S'1 or A' Modified S1 or A

SX, SY

Unidentified objects, components, parts, substances

S1Sy

A complex object, component, part, substance

(S1Sy)

Sy is introduced inside S1

(S1)Sy

Sy is introduced outside S1

F(Field)

Energy, a force, or description of the action

FX, FY

Unidentified energy, a force, or nature if the action

[iii] State the requirement (or condition) R1, which has to be met by the tool of the harmful action.
[iv] State what is desired (positive effect 1+).

[v] State what would be deteriorated (negative effect 1-).

[vi] State the opposite requirement (or condition) R2= -R1, which has to be met by the same tool.

[vii] State what is desired (positive effect 2++).

[viii] State what would be deteriorated (negative effect 2-).

[ix] State the desired result (1+ and 2+).

[x]  These paragraphs are intended to be long, run-on sentences.

[xi] Proceedings of the 2nd Total Product Development Symposium, Nov., 1996., Ellen Domb and Walter Lamia

[xii] A sequence of statements that must be executed with mutual exclusion with respect to critical sections in other processes that reference the same shared variables.

[xiii] M. Mizuno, A Structured Approach for Developing Concurrent Programs in Java, Information Processing Letters 69 (1999) 233-238.