Digital data processor with improved checkpointing and forking

• US 5,313,647 A
• Filed: 09/20/1991
• Issued: 05/17/1994
• Est. Priority Date: 09/20/1991
• Status: Expired due to Term

• Current Assignee: Kendall Square Research Corp.
• Original Assignee: Kendall Square Research Corp.
• Inventors: Oliveira, Fernando, Kaufman, Mark A.
• Primary Examiner(s): Heckler, Thomas M.
• Application Number:
  US07/763,505
• Time in Patent Office: 970 Days
• Field of Search: 395/700, 364/DIG. 1
• US Class Current: 718/102
• CPC Class Codes: G06F 11/1438 Restarting or rejuvenating

Abstract

A digital data processing apparatus includes a processing element that executes a process for generating requests for access to mapped data in a memory element. The apparatus also includes a fork/checkpoint-signalling element that generates "new-process signals" which delineate new time intervals. The apparatus responds to data requests generated by the process before the first new-process signal by accessing a requested datum as stored in a first set in memory. An address space manager responds to certain requests, e.g., for write access, in subsequent intervals for copying the requested datum from the most recent set in which it is stored to the current interval and, thereafter, accessing that copy. The manager responds to other requests, e.g., those for read-type access, by accessing the requested datum in the most recent set in which it is stored. A fork element can create a second process that initially duplicates a first one and can initiate generation of a new-process signal in connection with creation of the second process.

Claims

1. A digital data processing apparatus comprising:

A. memory means for storing data,

B. first process means for executing a first process and for generating in connection therewith at least one request for mapped access to said data,

C. fork/checkpoint signalling means for generating one or more new-process signals, each new-process signal delineating a successive process interval,

the interval preceding the first new-process signal being referred to as the first interval,

D. means for responding to a request for access to a datum generated by the first process during said first interval for providing access to the requested datum as stored in a first set of data stored in said memory means,

the first set being referred to as associated with said first interval of the first process,

E. first address space management means, coupled to said first process means and to said fork/checkpoint signalling means, for responding at least to an initial request by that process during a current interval subsequent to said first interval for write-type access to a datum, for

i) accessing the requested datum as stored in a set associated with a prior interval of the first process, and

ii) generating a further datum initially identical to that accessed datum;

F. said first address space management means including means for storing said initially identical datum in a set in said memory means associated with the current interval of the first process, and

G. said first address space management means further including means responsive to said initial request by the first process during said current interval for at least write-type access to a datum, as well as to subsequent requests for any of read-type and write-type access to that same datum by that same process during that same interval, for accessing said initially identical datum as stored in the set associated with the current interval of the first process, and otherwise for accessing the requested datum as stored in a set associated with a prior interval of the first process.

2. An apparatus according to claim 1 wherein

A. at least said first address space management means includes copy-on-reference-after-first-write means for generating said further initially identical datum in response to at least an initial request by said first process during said current interval for write-type access to a datum, as well as to any subsequent request during that same interval for any of read-type and write-type access to any datum,

B. said first address space management means includes means responsive to said initial request by said first process during said current interval for write-type access to a datum, as well as to said subsequent requests during that same interval for any of read-type and write-type access to any datum, for accessing said initially identical datum as stored in the set associated with the current interval of the first process, and otherwise for accessing the requested datum as stored in a set associated with a prior interval of the first process.

3. An apparatus according to claim 1, wherein

A. each said datum in said memory means is associated with a storage descriptor,

B. each said process means includes means for generating, along with said access request, a context address signal associated with the requested datum,

C. at least said first address space management means includes address translation means responsive to a context address signal for generating a storage descriptor associated with that same datum as stored in the set associated with the current interval of the associated process, and

D. said memory means includes means responsive to such storage descriptor for providing access to the associated datum.

4. An apparatus according to claim 3, wherein said address translation means includes one or more translation-representative signals, each representative of an association between at least one context address signal and at least one storage descriptor.

5. An apparatus according to claim 4, wherein at least said first address space management means includes

A. object means for selectively storing signals representative of a state of the associated process during a process interval, said state-representative signals including said translation-representative signals, and

B. means for selectively transferring such translation-representative signals between said object means and said address translation means.

6. An apparatus according to claim 5, wherein at least said first address space management means includes means responsive to at least said new-process signal for at least enabling storage of said translation-representative signals from said address translation means to said object means.

7. An apparatus according to claim 6, wherein said first address space management means includes means responsive to an initial request by the first process for write-type access to a datum subsequent to said new-process signal for storing said translation-representative signals from said address translation means to said object means.

8. An apparatus according to claim 6, wherein at least said first address space management means includes means for creating a plurality of said object means, each storing translation-representative signals from the address translation means of a respective prior interval.

9. An apparatus according to claim 8, wherein at least said first address space management means includes means linking said object means in an order based upon the recency of the associated process intervals.

10. An apparatus according to any of claims 5-9, wherein at least said first address space management means includes reassignment means responsive to said new-process signal for at least enabling modification of said one or more translation-representative signals stored in said address translation means to reflect an association between at least one context address signal and at least one further storage descriptor, said further storage descriptor being initially associated with a missing datum in a set associated with the current interval of the associated process.

11. An apparatus according to claim 10, wherein said reassignment means includes means for responding to an initial request by the first process for write-type access to a datum subsequent to said new-process signal for so modifying said one or more translation-representative signals stored in said address translation means.

12. An apparatus according to claim 10, wherein said memory means includes means responsive to a request for access to a missing datum for generating a missing-datum signal indicative thereof.

13. An apparatus according to claim 12, wherein at least said first address space management means includes prior-set means responsive to a missing-datum signal for accessing the missing datum as stored in a set associated with a prior interval of the associated process.

14. An apparatus according to claim 13, wherein said prior-set means includes means for accessing the missing datum as stored in a set associated with a most recent prior interval of the associated process in which that datum is stored.

15. An apparatus according to claim 14, wherein said prior-set means includes means for searching one or more said object means to identify a storage descriptor associated with said missing datum.

16. An apparatus according to claim 15, wherein at least said first address space management means includes restore means for restoring the associated process to a state associated with a prior process interval.

17. An apparatus according to claim 16, wherein said restore means includes means for transferring translation-representative signals from a selected one of said object means to said address translation means.

18. An apparatus according to claim 5, further comprising

A. disk means coupled to said address space management means for non-volatile storage of data, and wherein

B. said first address space means includes means for storing and accessing said object means on said disk means.

19. An apparatus according to claim 18, comprising

A. means for temporarily storing at least selected other process-related information on said disk means,

B. means for retaining at least selected object means on said disk for periods longer then said other process-related information.

20. A digital data processor according to claim 1, comprising:

A. fork means for creating a second process initially duplicating said first process,

said fork means being coupled to said fork/checkpoint signalling means for initiating generation of a new-process signal in connection with creation of said second process,

B. second process means for executing said second process and for generating in connection therewith at least one request for mapped access to said datum,

C. second address space management means coupled to said second process means for responding at least to an initial request by that process during a current interval subsequent to creation of said second process for write-type access to a datum, for

i) accessing the requested datum as stored in a set associated with at least a prior interval, preferentially associated with the second process, and

ii) generating a further datum initially identical to the access datum,

D. said second address space management means including means for storing that initially identical datum in a set in said memory means associated with the current interval of the second process, and

E. said second address space management means further including means responsive to said initial request by the second process during said current interval for at least write-type access to a datum, as well as to subsequent requests for any of read-type and write-type access to that same datum by that same process during the current interval for accessing said initially identical datum as stored in the set associated with the current interval of the second process, and otherwise for accessing that datum as stored in a set associated with a prior interval, preferentially associated with said second process.

21. An apparatus according to claim 1, comprising at least one of:

A. automatic checkpoint means responsive to a designated event for generating a new-process signal,

B. manual checkpoint means responsive to operator input for generating a new-process signal, and

C. programmatic checkpoint means responsive to execution of at least a selected programming instruction for generating a new-process signal.

22. An apparatus according to claim 21, wherein said automatic checkpoint means include means for generating said one or more new-process signals as a function of time.

23. A method for operating a digital data processing apparatus comprising the steps of:

A. providing memory means for storing data,

B. executing a first process and generating in connection therewith at least one request for mapped access to said data,

C. generating one or more new-process signals, each new-process signal delineating a successive process interval,

the interval preceding the first new-process signal being referred to as the first interval,

D. responding to a request for access to a datum generated by the first process during said first interval for providing access to the requested datum as stored in a first set of data stored in said memory means,

the first set being referred to as associated with said first interval of the first process,

E. responding at least to an initial request by said first process during a current interval subsequent to said first interval for write-type access to a datum, for

i) accessing the requested datum as stored in a set associated with a prior interval of the first process, and

ii) generating a further datum initially identical to that accessed datum,

F. storing said initially identical datum in a set in said memory means associated with the current interval of the first process, and

G. responding to said initial request by the first process during said current interval for at least write-type access to a datum, as well as to subsequent requests for any of read-type and write-type access to that same datum by that same process during that same interval, for accessing said initially identical datum as stored in the set associated with the current interval of the first process, and otherwise for accessing the requested datum as stored in a set associated with a prior interval of the first process.

24. A method according to claim 23 comprising the further steps of

A. generating said further initially identical datum in response to at least an initial request by said first process during said current interval for write-type access to a datum, as well as to any subsequent request during that same interval for any of read-type and write-type access to any datum,

B. responding to said initial request by said first process during said current interval for write-type access to a datum, as well as to said subsequent requests during that same interval for any of read-type and write-type access to any datum, for accessing said initially identical datum as stored in the set associated with the current interval of the first process, and otherwise for accessing the requested datum as stored in a set associated with a prior interval of the first process.

25. A method according to claim 23, wherein

A. each said datum in said memory means is associated with a storage descriptor,

B. each said process generates, along with said access request, a context address signal associated with the requested datum, said method comprising the further steps of

C. responding to a context address signal for generating a storage descriptor associated with that same datum as stored in the set associated with the current interval of the associated process, and

D. responding to such storage descriptor for providing access to the associated datum.

26. A method according to claim 25, comprising the step of providing one or more translation-representative signals, each representative of an association between at least one context address signal and at least one storage descriptor.

27. A method according to claim 26, comprising the steps of

A. selectively storing signals representative of a state of the associated process during a process interval, said state-representative signals including said translation-representative signals, and

B. selectively transferring such translation-representative signals between said object means and said address translation means.

28. A method according to claim 27, comprising the steps of responding to at least said new-process signal for at least enabling storage of said translation-representative signals from said address translation means to said object means.

29. A method according to claim 28, comprising the step of responding to an initial request by the first process for write-type access to a datum subsequent to said new-process signal for storing said translation-representative signals from said address translation means to said object means.

30. A method according to claim 28, comprising the step of creating a plurality of said object means, each storing translation-representative signals from the address translation means of a respective prior interval.

31. A method according to claim 30, comprising the step of linking said object means in an order based upon the recency of the associated process intervals.

32. A method according to any of claims 27-31, comprising the step of responding to said new-process signal for at least enabling modification of said one or more translation-representative signals stored in said address translation means to reflect an association between at least one context address signal and at least one further storage descriptor, said further storage descriptor being initially associated with a missing datum in a set associated with the current interval of the associated process.

33. A method according to claim 32, comprising the step of responding to an initial request by the first process for write-type access to datum subsequent to said new-process signal for so modifying said one or more translation-representative signals stored in said address translation means.

34. A method according to claim 32, comprising the step of responding to a request for access to a missing datum for generating a missing-datum signal indicative thereof.

35. A method according to claim 34, comprising the step of responding to a missing-datum signal for accessing the missing datum as stored in a set associated with a prior interval of the associated process.

36. A method according to claim 35, comprising the step of accessing the missing datum as stored in a set associated with a most recent prior interval of the associated process in which that datum is stored.

37. A method according to claim 36, comprising the step of searching one or more said object means to identify a storage descriptor associated with said missing datum.

38. A method according to claim 37, comprising the step of restoring the associated process to a state associated with a prior process interval.

39. A method according to claim 38, comprising the step of transferring translation-representative signals from a selected one of said object means to said address translation means.

40. A method according to claim 27, further comprising the steps of

A. providing disk means for non-volatile storage of data, and

B. storing and accessing said object means on said disk means.

41. A method according to claim 40, comprising the step of

A. temporarily storing at least selected other process-related information on said disk means,

B. retaining at least selected object means on said disk for periods longer then said other process-related information.

42. A method according to claim 23, comprising the steps of:

A. creating a second process initially duplicating said first process, and initiating generation of a new-process signal in connection with creation of said second process,

B. executing said second process and generating in connection therewith at least one request for mapped access to said datum,

C. responding at least to an initial request by said second process during a current interval subsequent to creation of said second process for write-type access to a datum, for

i) accessing the requested datum as stored in a set associated with at least a prior interval, preferentially associated with the second process, and

ii) generating a further datum initially identical to the access datum,

D. storing that initially identical datum in a set in said memory means associated with the current interval of the second process, and

E. responding to said initial request by the second process during said current interval for at least write-type access to a datum, as well as to subsequent requests for any of read-type and write-type access to that same datum by that same process during the current interval for accessing said initially identical datum as stored in the set associated with the current interval of the second process, and otherwise for accessing that datum as stored in a set associated with a prior interval, preferentially associated with said second process.

43. A method according to claim 23, including the step of executing at least one of the following operations:

A. responding to a designated event for generating a new-process signal,

B. responding to operator input for generating a new-process signal, and

C. responding to execution of at least a selected programming instruction for generating a new-process signal.

44. A method according to claim 23, comprising the step of generating said one of more new-process signals as a function of time.