views:

468

answers:

7

I am looking hard at the basic principles of storing the state of an executing program to disk, and bringing it back in again. In the current design that we have, each object (which is a C-level thingy with function pointer lists, kind of low-level home-made object-orientation -- and there are very good reasons for doing it this way) will be called to export its explicit state to a writable and restorable format. The key property to make this work is that all state related to an object is indeed encapsulated in the object data structures.

There are other solutions where you work with active objects, where there is a user-level thread attached to some objects. And thus, the program counter, register contents, and stack contents suddenly become part of the program state. As far as I can see, there is no good way to serialize such things to disk at an arbitrary point in time. The threads have to go park themselves in some special state where nothing is represented by the program counter et al, and thus basically "save" their execution state machine state to the explicit object state.

I have looked at a range of serialization libraries, and as far as I can tell this is a universal property.

The core quesion is this: Or is this actually not so? Are there save/restore solutions out there that can include thread state, in terms of where in its code a thread is executing?

Note that saving an entire system state in a virtual machine does not count, that is not really serializing the state, but just freezing a machine and moving it. It is an obvious solution, but a bit heavyweight most of the time.

Some questions made it clear that I was not clear enough in explaining the idea of how we do things. We are working on a simulator system, with very strict rules for code running inside it is allowed to be written. In particular, we make a complete divide between object construction and object state. The interface function pointers are recreated every time you set up the system, and are not part of the state. The state only consists of specific appointed "attributes" that each have a defined get/set function that converts between internal runtime representation and storage representation. For pointers between objects, they are all converted to names. So in our design, an object might come out like this in storage:

Object foo { value1: 0xff00ff00; value2: 0x00ffeedd; next_guy_in_chain: bar; }

Object bar { next_guy_in_chain: null; }

Linked lists are never really present in the simulation structure, each object represents a unit of hardware of some kind.

The problem is that some people want to do this, but also have threads as a way to code behavior. "Behavior" here is really mutation of the state of the simulation units. Basically, the design we have says that all such changeds have to be made in atomic complete operations that are called, do their work, and return. All state is stored in the objects. You have a reactive model, or it could be called "run to completion", or "event driven".

The other way of thinking about this is to have objects have active threads working on them, which sit in an eternal loop in the same way as classic Unix threads, and never terminate. This is the case that I am trying to see if it can be reasonable stored to disk, but it does not seem like that is feasible without interposing a VM underneath.

Update, October 2009: A paper related to this was published at the FDL conference in 2009, see http://www.engbloms.se/jakob%5Fpublications.html, the paper about checkpointing and SystemC.

A: 

You should NOT try to serialize a state that your program has to disk. Because your program will never have full control over its' state unless it is allowed to by the operating system, in which case... it is part of the operating system.

You can not guarantee that a pointer to some virtual memory location will point to the same virtual memory location again (except for properties like heap-begin/end, stack-begin), because to the program the operating systems' choices for virtual memory are indeterministic. The pages you request from the OS via sbrk or the higher level interfaces such as malloc will begin anywhere.

Better:

  • Code clean and inspect your design: What state properties are part of it?
  • Do not use such a low-level language, because the overhead in creating what you attempt to do is not worth the results.
  • If you must use C, consider means to make your life as easy as possible (consider the offsetof operator and the properties structs have such like first member starting at offset 0).

I suspect you want to shortcut the development time it takes to serialize/deserialize specific data structures, such as linked lists. Be assured, what you are attempting to do is not trivial and it's a lot more work. If you insist on doing so, consider looking into your operating system's memory management code and into the OS's paging mechanisms. ;-)

EDIT due to appended question: The design you state sounds like some kind of state machine; object properties are set up such that they are serializable, function pointers can be restored.

First, regarding thread states in objects: these only matter if there can be typical concurrent-programming problems such as race conditions, etc. If that's the case, you need thread-synchronization functionality, such as mutexes, semaphores, etc. Then you can at any time access the properties to serialize/deserialize and be safe.

Second, regarding object setup: looks cool, not sure if you are having a binary or other object representation. Assuming binary: you can serialize them easily if you can represent the actual structures in memory (which is a bit of coding overhead). Insert some kind of class-ID value at the begin of the objects and have a look up table that points to the actual outfit. Look at the first sizeof(id) bytes and you know which kind of struct you have. Then you will know which structure is laying there.

When serializing/deserializing, approach the problem like this: you can look up the length of the hypothetically packed (no spacing between members) structure, allocate that size and read/write the members one after the other. Think offsetof or, if your compiler supports it, just use packed structs.

EDIT due to bold core question :-) No, there are none; not for C.

mstrobl
Well, the threads here are things in the thing called SystemC, basically cooperative non-preemptive threading using quickthreads or Windows fibers. In a single OS thread.
jakobengblom2
A: 

It looks like you want have a closure in C++. As you have pointed out there is no mechanism built into the language to let you do this. As far as I know this is basically impossible to do in a totally general manner. In general it's hard to do in a language that doesn't have a VM. You can fake it somewhat by doing something like you have suggested basically creating a closure object that maintains the execution environment/state. Then having this serialize itself when it is in a known state.

You will also run into trouble with your function pointers. The functions can be loaded to different memory addresses on each load.

Matt Price
+1  A: 

It really sounds like saving the state of a virtual machine and being able to restore it the exact same way is exactly what you want.

If all you need is to be able to start the program running with the same data that the previous execution was using, then you only need to save off and restore persistent data, the exact state of each thread shouldn't really matter, since it will change so fast anyways - and the actual addresses of things will be different the next time. Using a database should give you this ability anyways.

Greg Rogers
Not quite: you also have to be able to restore the state into a different implementation, for example, on a different type of host.The thread state does matter, if it is used to code some state machine like a bus protocol, for example.
jakobengblom2
+2  A: 

I don't think serializing only "some threads" of a program can work, since you will run into problems with synchronization (some of the problems are described here http://java.sun.com/j2se/1.3/docs/guide/misc/threadPrimitiveDeprecation.html ). So persisting your whole program is the only viable way to get a consistent state.

What you might look into is orthogonal persistence. There are some prototypical implementations:

http://research.sun.com/forest/COM.Sun.Labs.Forest.doc.external_www.PJava.main.html

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.7429

But none of them are maintained anymore or have gained a lot of attraction (afaik). I guess checkpointing is not the best solution after all. In my own project http://www.siebengeisslein.org I am trying the approach of using lightweight transactions to dispatch an event so thread state does not have to be maintained (since at the end of a transaction, the thread callstack is empty again, and if a operation is stopped in mid-transaction, everything is rolled back, so the thread callstack does matter as well). You probably can implement something similar with any OODBMS.

Another way to look at things are continuations (http://en.wikipedia.org/wiki/Continuation , http://jauvm.blogspot.com/). They are a way to suspend execution at defined code locations (but they are not necessarily persisting the thread state).

I hope this gives you some starting points (but there is no ready-to-use solution to this afaik).

EDIT: After reading your clarifications: You should definitely look into OODBMS. Dispatch each event in its own transaction and don't care about threads.

jiriki
A: 

I consider the thread state to be an implementation detail which is probably not appropriate to be serialized. You want to save the state of your objects--not necessarily how they got to be the way they are.

As an example for why you want to take this approach, consider hitless upgrade. If you're running version N of your application and want to upgrade to version N+1, you can do so using object serialization. However, the "version N+1" threads are going ot be different from the version N threads.

bog
+1  A: 

A better approach than trying to serialize program state would be to implement Crash Only Software with data checkpointing. How you do your data checkpointing will depend on your implementation and problem domain.

ceretullis
A: 

Something like this was actually proposed for Java in JSR 323:

http://tech.puredanger.com/2008/01/09/strong-mobility-for-java/

but was not accepted as being too theoretical:

http://tech.puredanger.com/2008/01/24/jcp-votes-down-jsr-323/

If you follow the links, you can find some interesting research on this problem.

Alex Miller