Storage Informer
Storage Informer

State-Phase Programming

by on Sep.02, 2009, under Storage

State-Phase Programming

It has been relatively easy for us to follow the path of a serial application. The flow of the application is managed by the Stack. This makes the execution flow of a single process to be managed by CPU hardware. Today we face the need to execute several processes in parallel and thus have several execution paths at the same time. This is harder for us to manage and keeping track of this flow is complex. The hardware accelerated Stack is no longer sufficient for us and the Stack-Trace is no longer the state of the application. I have elaborated on this on a previous post called Stateful Programming – A Case Study. This post analyzed the execution flow of a serial application in terms of Execution States. A system design that specifies states is beneficial for a serial application as explained in that post. When it comes to parallel applications this design step becomes a must.

The Application State is a cross-section of all states of running elements. On a serial application this can be the state of the Stack (or Stack-Trace). For a parallel application there are several processes working at the same time. Every thread is doing something or waiting for something. There are also suspended operations. Here are a few examples:

[1] OpenFile, ReadFile(A.txt), WriteFile(B.txt), CloseFile

The states are: (1) Initial State, (2) The File is open, (3) Data was Read, (4) Data Written, (5) File Closed.

[2] OpenFile, ReadFile(A.txt), CloseFile, UpdateUI

The states are: (1) Initial State, (2) The File is open, (3) Buffer was Read, (4) File Closed, (5) GUI Updated.

[3] LockBuffer, ReadBuffer, UnlockBuffer, UpdateUI

The states are: (1) Initial State, (2) Buffer Locked, (3) Buffer was Read, (4) Buffer Unlocked, (5) GUI Updated.

The examples above are serial implementations but can also be converted into parallel implementations.

Example [3] seems to be serial however it is using a lock which means that the transition from State (1) to State (2) is dependant on the execution of another thread. For example if there are two thread doing this operation then Thread B can only move from State (1) to State (2) if Thread A is not in State 2 or 3. If Thread A is currently in state (3) then Thread B will enter a wait state and the operation will be suspended.

Example [2] is serial but it is very likely that the GUI Window will be owned by another thread and only that thread is allowed to access the window. Modifying data on the window can be performed by posting a message to the queue of the owner thread. This means that Thread A, performing operation [2], will post a message to Thread B which is the owner of the GUI Window, and can then continue to handle another task. Thread A can in effect start another operation [2] and keep posting messages to Thread B. In this situation even though all threads are working, some of the operations can be suspended. How many system designs have you seen that show this?

Example [2] is serial because the file operations are blocking. It is possible to use non-blocking file operations and for example have a Callback function executed when the ReadFile is complete. The thread will open the file, call the ReadFile API and assume that the Callback be called and therefore the thread can take another operation. This time again, there can be suspended operations even though all threads are working.

It seems that looking at the Stack-Trace as the state of the application is a huge mistake. There are many operations that have no thread associated with them and therefore have Stack related to them. Other operations can cross thread boundary or are effected by other threads and looking at the Stack-Trace shows us only partial information.

There are bugs that appear randomly. Random Bugs we call them. Well, actually these bugs are very accurate. The problem is that we just don&apost have a good view of the system. Imagine that you are driving a car with no windows. You can only see the inside of the car. Sometimes you turn the wheel and everything is fine and sometimes you turn the wheel at the same way and you "Randomly" hit something. The way to predict and locate bugs is to have a real view of the interactions in our application.

The two basic concepts that we should need to add to our design are Phase and State. When we write a Procedural C code the operation is inside the function – this is why it is called a Procedure. The operation has several Phases that it is going through, or several states of execution. In Procedural programming every branch is commonly an execution state V a Phase. Executing the code &aposstep-by-step&apos over the Procedure means going over the different Phases of the operation. We can see the different Phases by looking at the lines of code (see my previous post for more information). The operation Phase does not have to be associated with a thread. When we break this association we can start managing our application better.

A primitive management of operation Phase is performed by using Locks, Events, etc. We wait for an application wide Phase. The second important element is object State. We don&apost have good tools to keep track of that. Actually the only States we know are: Not-Initialized, Initialized, Working, Can-Dispose, Disposed. These States are kept to manage resources and avoid resource leaks. Some of the object States are relevant for some of the operations. For example I want to start scanning my picture only after the buffer is ready in memory and no one else is using the output file. This adds these new States to the picture object: No-Data, Updating, Data-Ready. We can include to this States that include version numbering etc. Actually there are more States when I want to start scanning my picture only after the buffer is ready: Scanning-Data, Data-Scanned.

When we snapshot all Phases and States in the system we know exactly what happened and when!

To better explain the use of States I wrote a small sample application that uses a pseudo engine. A real implementation requires the use a kernel driver and would only confuse more than explain. Phases can be managed using the same State manager.

The code is published here:

http://www.asyncop.com/MTnPDirEnum.aspx?treeviewPath=%5bo%5d+Open-Source%5cPhase-State+Programming

The code is waiting for the correct State but it is also possible to post a message to a thread or to have all States and Phases waiting in a queue of tasks that belongs to a thread-pool.

In the log you see, Num is the serial number of the log message, MM:SS.millisec is the time of message in the format of minutes : seconds . milliseconds, and Application Log is the message sent from the application. The messages that start with "[ Main ]" are Phases on main() and the messages that start with "[ Communication Buffer ]" are States of the object as it reports modifications.

A real implementation will allow you to be notified of changes, allow to prevent the shift to next State until a task is completed, and allow to hook on State change before everyone is notified.

The code sample in PhaseStateTest00.cpp is the test application with main() and the other threads.

The code sample in State_Simulation.cpp and State_Simulation.h is the implementation and declarations of the pseudo State management engine.

The code demonstrates how the system is still coherent even though an operation is crossing several threads and even State(3) of the object is used by both a thread and by main() which in terms of execution flow is similar to forking.

Using this method of system modeling should greatly reduce execution-flow bugs, and can really help with system debug. Many of the bugs are anticipated and prevented at the design stages.

It is very difficult to implement this using user-mode API however a kernel driver can do this very easily.

URL: http://feedproxy.google.com/~r/IntelBlogs/~3/PAk4G9JL8Ug/

:, , , , , , , ,

Leave a Reply

Powered by WP Hashcash

Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Visit our friends!

A few highly recommended friends...