Editor | On 15, Aug 1999

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 andinventors to solve problems in creative and powerful ways. These methods havecentered around traditional sciences and engineering disciplines such asPhysics, Mechanical, Electrical, Chemical Engineering; however, TRIZ in ComputerScience is new.

Inthis article, I attempt to break some “Psychological Inertia” in thearea of Computer Science.Theproblem presented is a concurrency programming problem known as the “RollerCoaster Problem.”In thisproblem, we will use TRIZ to create an algorithm used to simulate the actions ofour roller coaster.

Concurrency

Concurrentprogramming is the activity of constructing a program containing multipleprocesses that execute in parallel.Theseprocesses compete for access to critical resources and cooperate in performingsome task. In our example, we will be simulating the operations of a RollerCoaster in which a single roller coaster car with a capacity of N will representone process and passengers will represent “n” processes.These passengers simply get in line for a ride on our rollercoaster, board when the time is right, take a ride, disembark and wander aroundthe amusement park until they ready for another ride. Thisprocess continues for as long as we want our simulation to run.Queuing, loading, riding and unloading of passengers are analogous toseveral issues facing concurrency today, such as shared memory access,distribution of data, mutually exclusive access to a shared file

Prettysimple uh?Not really, as humanbeings it is not natural for us to think in terms of parallel execution while weare writing software programs. Software engineers typically stick to sequentialprogramming, progressing from step A to step B in the spirit of achieving somegoal.Given this pattern and thefact 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?Universitiesspend much time developing formal techniques based on solid mathematicalfoundations in the Computer Science field; yet without a systematic way ofapplying formal techniques to real practice (in a way that it is understandableto the average hacker, oops I mean programmer), we cannot maximize the qualityof our software systems.

TheProblem

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

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

.

·Table 1S-Field Action Legend[i]

OurS-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 theMini-problem.

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

State the OppositeVersions 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 Degreeof the Conflict.

Extreme Conflict 1.

Stateextreme requirements ER1 so that the imaginary positive effect 1++ would be thebest, but the imaginary negative effect 1 – – would be the worst:

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

Drawa model of the Extreme Conflict 1.Indicatethe extreme requirement ER1, positive and negative effects.

Extreme Conflict 2.

Stateextreme requirement ER2 so that the imaginary positive effect 2++ would be thebest, but the imaginary, negative effect 2- – would be the worst:

If(describe the extreme requirement ER2)thereare many people waiting in line, (State the best positive effect 2++) theride never stops ($$$), but (State the worst negative effect 2–) passengersmight try to get on or off at the same time.

Drawa model of the Extreme Conflict 2.Indicatethe extreme requirement ER2, positive and negative effects.

Select the Versionof the Conflict.

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

Describe the Modelof 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.

Analyze the Resources.

Study the OperatingZones of the Conflicting Actions.

Letsanalyze the zones of interaction to identify possible conflicts; below depictsseveral possible zones of the scenario. Zone one deals with the queuing orordering of passengers that want to ride the coaster.Zone two focuses on the barrier between the waiting passengers one a carAND the passengers getting off the ride.Continuingon, we have Zone three, which is the car itself; Zone four and Zone five dealwith 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 OperatingTime 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.

Define the Ideal Final Result (IFR).

State IFR-1:

X-resourceeliminates thepassengers getting off and on at the same time during the operating timeand within the operating zone and without any complication of the system whilekeeping the ride capable of givingpassengers repeated rides on the roller coaster.[x]

State IFR-1 forother resources.

Thecaritself eliminates the passengers getting off and on at the same time during theoperating time and within the operating zone and without any complication of thesystem while keeping the ridecapable of giving passengers repeated rideson the roller coaster.

Theloading stationitself eliminates thepassengers getting off and on at the same time during the operating timeand within the operating zone and without any complication of the system whilekeeping the ride capable of givingpassengers repeated rides on the roller coaster.

Thepassengereliminates the passengers getting off and on at the same time during theoperating time and within the operating zone and without any complication of thesystem while keeping the ridecapable of giving passengers repeated rideson the roller coaster.

Define Macro LevelPhysical Contradiction.

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

Fromthe above diagram, we see where the time conflict occurs; this is where we needto Apply Rules for PhysicalContradiction 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 yourticket and directs you when it is your time to get on the ride.However, we need to simulate these actions using software; one solutionapplies 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 acritical section[xii] of code. This solution also supports the idea of TRIZ Principle 7 – Matreshka – “Nested Doll”, where anobject 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 allthe person objects would use.Eachpassenger would have a monitor in their pocket that would beep when they can geton the coaster and beep when it is time to get off. Remember we are”simulating” using software and we are assuming that our passengersare like the Scarecrow from the Wizard of Oz – they have no brains!

SoftwareSolution Outline: The following appendix focuses on a coarse-grainedsolution and translation to a fine-grained synchronization using a Monitor; myimplementation is in Java and is available on a Web site listed later. I havealso provided some hyperlinks related to synchronization.

Conclusion:

ApplyingTRIZ to this problem was challenging since the S-Field analysis did not”feel” right.Theabstraction of “force” does not seem to fit in this context but, thisis okay – we are exploring new frontiers for TRIZ.As we discover more ways to bridge-the-gap between TRIZ and ComputerScience, more solutions will become evident. Since computer science has beenaround for a very short period, it is a baby compared to physics and mechanicalengineering.However, we need CS togrow up quickly since software is becoming increasingly critical to our everydaylives.Major breakthroughs areneeded to avoid a software crisis; the Year 2000 problem is trivial compared toother “unknown” software failures – and TRIZ is perfect fordiscovering “unknown” future conflicts.At least with Y2K, we are aware of the problem; if we construct abuilding that is sagging in the roof, we can see this since it is a physicalentity and take appropriate action. Software is not that easy to see.I hope others will join me in using TRIZ to solve existing softwareproblems and ones we do not even know about yet.

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

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

SomePreliminary Information:

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

• <awaitB_iàS_i> and

• <S_j>

UsingProgramming Logic, the global invariant is formally verified in thecoarse-grained solution.Finally,the coarse-grained solution is mechanically translated to a fine-grainedsemaphore or monitor program that maintains the global invariant. This approachhas many advantages.First, thisformal approach enables verification of programs being developed.Second, the most important activity in the programmingprocess lies at a high level; namely, specifying global invariants. Once anappropriate global invariant is specified, much of the rest of the process ismechanical.Since TRIZ can helpdetermine properties of a system, it can be used to determine global invariants.

The Javaprogramming language encourages the use of multiple threads, which we will usein our implementation to simulate the coaster and the passengers. Java providesmonitor-like synchronization primitives. However, these primitives havelimitations and thus we will apply our TRIZ exercise to create our own monitorsystem based on our coarse-gained solution.This approach also makes our code platform independent.

OurTRIZ-driven Coarse-Grained Solution:

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

(1)For each <awaitB_iàS_i>,define one public (non-synchronized)method and one private synchronizedmethod, and declare one private specific notification lock (instance variable)of class Object. Let method_i,checkBS_i,ando_ibe the public method, the private synchronized method, and thespecific 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 voidmethod_I(){

synchronized (o_i){

While (!checkBS_i())

try {

o_i.wait();

} catch (InterruptedException e){}

}

}

}

Private synchronized method checkBS_Iis defined as:

privatesynchronizedBooleancheckBS_i () {

if (B_i){

S_i; returntrue;

} else return false;

}

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

public voidmethod_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 anysynchronized block).

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

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

Where O_kis a specific notification lock is associated with <awaitB_iàS_i>.If more than one thread may leave the construct <awaitB_iàS_i>when B_k becomes true, notifyAllshould be issued; otherwise, notifyshould be issued.

“npass”is the number of passengers that have boarded the car.“boarding” and “done” are counters used by theprocesses to track different stages of the simulation. “C” is thecapacity 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::

<awaitnpass >= C -> npass := npass – C>

<boarding:= boarding + C>

<awaitdone = C -> done := 0>

Appendix B: Java Implementation Source Code

Please clickhere 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.