| |
|
|
VIRTUAL MACHINE TASK OR PROCESS MANAGEMENT |
Process persistence in a virtual machine6854115
Abstract
A system and method for providing process persistence in a virtual machine are described. A virtual persistent heap may be provided. The virtual persistent heap may enable the checkpointing of the state of the computation of a virtual machine, including processes executing within the virtual machine, to a persistent storage such as a disk or flash device for future resumption of the computation from the checkpoint. The Virtual Persistent Heap also may enable the migration of the virtual machine computation states, and thus the migration of executing processes, from one machine to another. The saved state of the virtual machine heap may also provide the ability to restart the virtual machine after a system crash or shutdown to the last saved persistent state, and to thus restart a process that was running within the virtual machine prior to the system crash or shutdown to a checkpointed state of the process stored in the virtual persistent heap. This persistent feature is important for small consumer and appliance devices, as these appliances may be shutdown and restarted often.
Claims
What is claimed is:
1. A method for checkpointing processes on a virtual machine executing within a device, the method comprising:
executing a process within the virtual machine, wherein the virtual machine comprises a virtual machine virtual memory manager;
wherein said executing the process comprises:
the process referencing an object in a virtual heap during execution;
wherein the virtual heap comprises an in-memory heap and a store heap;
wherein, if the referenced object is in the store heap and not in the in-memory heap when referenced by the process, the virtual machine virtual memory manager copying a section of the store heap comprising the referenced object from the store heap to the in-memory heap;
the process accessing the referenced object in the in-memory heap; and
checkpointing a state of the process executing on the virtual machine to a first memory space, wherein said checkpointing comprises the virtual machine virtual memory manager flushing one or more sections of the in-memory heap to the store heap.
2. The method of claim 1, wherein the one or more flushed sections comprise new objects or modified objects in regards to objects stored in the store heap prior to said flushing.
3. The method of claim 1,
wherein said checkpointing the state of the process executing on the virtual machine to the first memory space comprises storing data describing one or more leases to services for the process, wherein the one or more services are external to the virtual machine on which the process is executing, and wherein the leases are grants of access to the one or more services.
4. The method of claim 3,
wherein said checkpointing the state of the process executing on the virtual machine to the first memory space further comprises storing a computation state of the virtual machine to the first memory space, wherein the computation state of the virtual machine comprises information about the execution state of the process on the virtual machine.
5. The method of claim 1, further comprising:
repeating said checkpointing the state of the process so that the first memory space stores a plurality of states for the process, and wherein each of the plurality of states for the process stored in the first memory space is a unique state of the process on the virtual machine.
6. The method of claim 1,
wherein said checkpointing the state of the process executing on the virtual machine to the first memory space comprises storing a computation state of the virtual machine to the first memory space, wherein the computation state of the virtual machine comprises information about the execution state of the process on the virtual machine.
7. The method of claim 1,
wherein the store heap for the process is one of a plurality of store heaps for a plurality of processes on the virtual machine.
8. The method of claim 1,
wherein the checkpointed state of the process is one of a plurality of checkpointed states in the first memory space for a plurality of processes on the virtual machine.
9. The method of claim 1,
wherein the device is a network client device.
10. The method of claim 1,
wherein the first memory space is comprised in a first memory device coupled to the device.
11. The method of claim 10,
wherein the first memory device is coupled to the device via the Internet so that the virtual machine virtual memory manager writing the one or more sections of the in-memory heap to the store heap comprised in the first memory space occurs over the Internet.
12. The method of claim 1,
wherein the first memory space is comprised in a non-volatile memory.
13. The method of claim 12,
wherein the non-volatile memory is a flash memory;
wherein the store heap comprises a plurality of cache lines; and
wherein each of the sections of the store heap comprise one or more of the plurality of cache lines.
14. The method of claim 1,
wherein the virtual machine is a Java virtual machine, and wherein the process is a Java application.
15. A method for managing processes on a virtual machine executing within a device, the method comprising:
executing a process within the virtual machine;
checkpointing a state of the process on the virtual machine to a persistent store;
expiring one or more leases to services for the process on the virtual machine;
stopping the process execution on the virtual machine;
reading the stored state of the process from the persistent store;
reconstituting the stored state of the process on the virtual machine;
establishing the one or more leases to services for the process on the virtual machine; and
resuming the process execution on the virtual machine.
16. The method of claim 15, further comprising:
stopping execution of the virtual machine within the device consequent to said stopping the process execution on the virtual machine; and
restarting execution of the virtual machine within the device prior to said reading the stored state of the process from the persistent store.
17. The method of claim 15,
wherein the execution of the virtual machine within the device is not stopped between said stopping the process execution on the virtual machine and said resuming the process execution on the virtual machine.
18. The method of claim 15,
wherein the state of the process comprises:
a heap for the process, wherein the heap comprises code and data for the process executing on the virtual machine.
19. The method of claim 15,
wherein the state of the process comprises:
data describing the one or more leases to services for the process on the virtual machine, wherein the data describing the one or more leases is used in said establishing the one or more leases to services for the process on the virtual machine.
20. The method of claim 15,
wherein the one or more leases to services include one or more leases to remote services, wherein the remote services are services provided on devices other than the device within which the process is executing.
21. The method of claim 15,
wherein the one or more leases to services include one or more leases to local services, wherein the local services are services provided on the device within which the process is executing.
22. The method of claim 15,
wherein the one or more leases to services include one or more leases to system services, wherein a system service comprises system code for accessing a resource external to the process, wherein the system code is provided on the device within which the process is executing.
23. The method of claim 15,
wherein the state of the process comprises:
a stored execution state of the device comprising the virtual machine;
wherein, in said reconstituting the state of the process on the virtual machine, a current execution state of the device comprising the virtual machine is reconstituted to the stored execution state of the device.
24. The method of claim 15,
wherein the persistent store comprises a plurality of persistent heaps for a plurality of processes; and
wherein said checkpointing the state of the process on the virtual machine to the persistent store comprises:
checkpointing the state of the process on the virtual machine to a first persistent heap for the process in the plurality of persistent heaps comprised in the persistent store.
25. The method of claim 15,
wherein the virtual machine comprises a first in-memory heap for caching pages for use by the process, wherein the pages comprise code and data for the process;
wherein the persistent store comprises a virtual heap for storing pages flushed from the first in-memory heap; and
wherein said checkpointing the state of the process on the virtual machine to the persistent store comprises:
storing one or more pages from the first in-memory heap to the virtual heap in the persistent store.
26. The method of claim 25,
wherein said stopping the process execution on the virtual machine comprises:
deleting the first in-memory heap from the virtual machine.
27. The method of claim 25,
wherein said reading the stored state of the process from the persistent store comprises:
reading the one or more pages from the virtual heap in the persistent store; and
wherein said reconstituting the state of the process on the virtual machine comprises:
establishing on the virtual machine a second in-memory heap for caching pages for use by the process; and
copying the one or more pages read from the virtual heap to the second in-memory heap.
28. The method of claim 15,
wherein the process is a Java process, and wherein the virtual machine is a Java virtual machine.
29. A method for managing processes on a virtual machine executing within a device, the method comprising:
executing a first process within the virtual machine;
checkpointing a state of the first process executing within the virtual machine to a persistent store;
expiring one or more leases to services for the first process on the virtual machine;
suspending the first process executing within the virtual machine;
reading a state of a suspended second process from the persistent store, wherein the state of the second process was stored to the persistent store prior to said executing the first process within the virtual machine;
reconstituting the state of the second process on the virtual machine;
establishing one or more leases to services for the second process on the virtual machine; and
resuming the execution of the second process within the virtual machine.
30. The method of claim 29, further comprising:
stopping execution of the virtual machine within the device consequent to said suspending the first process executing within the virtual machine; and
restarting execution of the virtual machine on the device prior to said reading the state of the second process from the persistent store.
31. The method of claim 29,
wherein the execution of the virtual machine on the device is not stopped between said suspending the first process executing within the virtual machine and said resuming the execution of the second process within the virtual machine.
32. The method of claim 29,
wherein the state of the second process comprises:
a heap for the second process, wherein the heap comprises code and data for the second process executing on the virtual machine.
33. The method of claim 29,
wherein the state of the second process comprises:
data describing the one or more leases to services for the second process on the virtual machine, wherein the data describing the one or more leases is used in said establishing the one or more leases to services for the second process on the virtual machine.
34. The method of claim 29,
wherein the one or more leases to services include one or more leases to remote services, wherein the remote services are services provided on devices other than, the device within which the process is executing.
35. The method of claim 29,
wherein the one or more leases to services include one or more leases to local services, wherein the local services are services provided on the device within which the process is executing.
36. The method of claim 29,
wherein the one or more leases to services include one or more leases to system services, wherein a system service comprises system code for accessing a resource external to the process, wherein the system code is provided on the device within which the process is executing.
37. The method of claim 29,
wherein the state of the second process comprises:
a stored execution state of the device comprising the virtual machine;
wherein, in said reconstituting the state of the second process on the virtual machine, a current execution state of the device comprising the virtual machine is reconstituted to the stored execution state of the device.
38. The method of claim 29,
wherein the persistent store comprises a plurality of persistent heaps for a plurality of processes; and
wherein said checkpointing the state of the first process executing within the virtual machine to the persistent store comprises:
checkpointing the state of the first process on the virtual machine to a first persistent heap for the first process in the plurality of heaps comprised in the persistent store; and
wherein said reading the state of the second process from the persistent store comprises:
reading the state of the second process from a second persistent heap for the second process in the plurality of heaps comprised in the persistent store.
39. The method of claim 29,
wherein the virtual machine comprises a first in-memory heap for caching pages for use by the first process, wherein the pages comprise code and data for the first process;
wherein the persistent store comprises a first virtual heap for storing pages flushed from the first in-memory heap; and
wherein said checkpointing the state of the first process on the virtual machine to the persistent store comprises:
storing one or more pages from the first in-memory heap to the first virtual heap in the persistent store.
40. The method of claim 39,
wherein said suspending the first process execution on the virtual machine comprises:
deleting the first in-memory heap from the virtual machine.
41. The method of claim 29,
wherein the persistent store comprises a second virtual heap for storing pages flushed from a deleted second in-memory heap for the second process, wherein the pages comprise code and data for the second process;
wherein said reading the stored state of the second process from the persistent store comprises:
reading one or more pages from the second virtual heap in the persistent store; and
wherein said reconstituting the state of the second process on the virtual machine comprises:
reestablishing on the virtual machine the previously deleted second in-memory heap for caching pages for use by the second process; and
copying the one or more pages read from the second virtual heap to the reestablished second in-memory heap.
42. The method of claim 29,
wherein the first process and second process are Java processes, and wherein the virtual machine is a Java virtual machine.
43. A system comprising:
a device configured to execute a virtual machine, wherein the virtual machine is configured to execute a first process;
a first memory coupled to the device, wherein the first memory is configured to store a store heap for the first process, and wherein the first memory is further configured to store one or more checkpointed states of one or more processes, wherein the store heap is comprised within a virtual heap for the first process;
a second memory coupled to the device, wherein the second memory is configured to store an in-memory heap for the first process, and wherein the in-memory heap is comprised within the virtual heap, and wherein the in-memory heap comprises cached portions of the store heap for access by the first process;
wherein the device is configured to perform operations on the virtual heap according to a virtual machine virtual heap manager, and wherein the virtual machine virtual heap manager is configured to:
copy a section of the store heap comprising an object from the store heap to the in-memory heap in response to the first process referencing the object in the virtual heap when the referenced object is in the store heap and not in the in-memory heap, wherein the first process accesses the referenced object in the in-memory heap; and
checkpoint a state of the first process executing on the virtual machine to the first memory;
wherein, in checkpointing the state of the first process executing on the virtual machine to the first memory, the virtual machine virtual heap manager is further configured to:
flush one or more sections of the in-memory heap to the store heap.
44. The system of claim 43,
wherein the one or more flushed sections comprise new objects or modified objects in regards to objects stored in the store heap prior to said flushing.
45. The system of claim 43,
wherein, in checkpointing the state of the first process executing on the virtual machine to the first memory, the virtual machine virtual heap manager is further configured to:
store data describing one or more leases to services for the first process, wherein the one or more services are external to the virtual machine on which the first process is executing, and wherein the leases are grants of access to the one or more services.
46. The system of claim 43,
wherein the virtual machine virtual heap manager is further configured to:
repeat said checkpointing the state of the first process so that the first memory stores a plurality of states for the first process;
wherein each of the plurality of states for the first process stored in the first memory is a unique state of the first process on the virtual machine.
47. The system of claim 43,
wherein, in checkpointing the state of the first process executing on the virtual machine to the first memory, the virtual machine virtual heap manager is further configured to:
store a computation state of the virtual machine to the first memory, wherein the computation state of the virtual machine comprises information about the execution state of the first process on the virtual machine.
48. The system of claim 43,
wherein the store heap stored in the first memory for the first process is one of a plurality of store heaps stored in the first memory for a plurality of processes on the virtual machine; and
wherein the checkpointed state of the first process is one of a plurality of checkpointed states in the first memory for a plurality of processes on the virtual machine.
49. The system of claim 43,
wherein the device is a network client device.
50. The system of claim 43,
wherein the first memory is coupled to the device via the Internet so that said writing the one or more sections of the in-memory heap to the store heap comprised in the first memory occurs over the Internet.
51. The system of claim 43,
wherein the first memory is a flash memory;
wherein the store heap comprises a plurality of cache lines; and
wherein each of the sections of the store heap comprise one or more of the plurality of cache lines.
52. The system of claim 43,
wherein the virtual machine is a Java virtual machine, and wherein the first process is a Java application.
53. A system comprising:
a device configured to execute a virtual machine, wherein the virtual machine is configured to execute a process;
a persistent memory device coupled to the device, wherein the persistent memory device is configured to store a checkpointed state for the process;
wherein the device is further configured to manage the process executing within the device according to a virtual machine process manager, and wherein the virtual machine process manager is configured to:
store the state of a process executing within the virtual machine to the persistent memory device;
expire one or more leases to services for the process on the virtual machine;
stop the process execution on the virtual machine;
read the stored state of the process from the persistent memory device;
reconstitute the stored state of the process on the virtual machine;
establish the one or more leases to services for the process on the virtual machine; and
resume the process execution on the virtual machine.
54. The system of claim 53,
wherein the device is further configured to:
stop execution of the virtual machine within the device consequent to said stopping the process execution on the virtual machine; and
restart execution of the virtual machine within the device prior to said reading the stored state of the process from the persistent memory device.
55. The system of claim 53,
wherein the execution of the virtual machine within the device is not stopped between said stopping the process execution on the virtual machine and said resuming the process execution on the virtual machine.
56. The system of claim 53,
wherein the state of the process comprises:
a heap for the process, wherein the heap comprises code and data for the process executing on the virtual machine.
57. The system of claim 53,
wherein the state of the process comprises:
data describing the one or more leases to services for the process on the virtual machine, wherein the data describing the one or more leases is used by the virtual machine process manager in said establishing the one or more leases to services for the process on the virtual machine.
58. The system of claim 53,
wherein the one or more leases to services include one or more leases to remote services, wherein the remote services are services provided on devices other than the device within which the process is executing.
59. The system of claim 53,
wherein the one or more leases to services include one or more leases to local services, wherein the local services are services provided on the device within which the process is executing.
60. The system of claim 53,
wherein the one or more leases to services include one or more leases to system services, wherein a system service comprises system code for accessing a resource external to the process, wherein the system code is provided on the device within which the process is executing.
61. The system of claim 53,
wherein the state of the process comprises a stored execution state of the device comprising the virtual machine; and
wherein, in reconstituting the state of the process on the virtual machine, the virtual machine process manager is further configured to:
reconstitute a current execution state of the device comprising the virtual machine to the stored execution state of the device.
62. The system of claim 53,
wherein the persistent memory device comprises a plurality of persistent heaps for a plurality of processes; and
wherein, in checkpointing the state of the process on the virtual machine to the persistent memory device, the virtual machine process manager is further configured to:
checkpoint the state of the process on the virtual machine to a first persistent heap for the process in the plurality of persistent heaps comprised in the persistent memory device.
63. The system of claim 53,
wherein the virtual machine comprises a first in-memory heap for caching pages for use by the process, wherein the pages comprise code and data for the process;
wherein the persistent memory device comprises a store heap for storing pages flushed from the first in-memory heap; and
wherein, in checkpointing the state of the process on the virtual machine to the persistent memory device, the virtual machine process manager is further configured to:
store one or more pages from the first in-memory heap to the store heap in the persistent memory device.
64. The system of claim 63,
wherein, in stopping the process execution on the virtual machine, the virtual machine process manager is further configured to:
delete the first in-memory heap from the virtual machine.
65. The system of claim 63,
wherein, in reading the stored state of the process from the persistent memory device, the virtual machine process manager is further configured to:
read the one or more pages from the store heap in the persistent memory device; and
wherein, in reconstituting the state of the process on the virtual machine, the virtual machine process manager is further configured to:
establish on the virtual machine a second in-memory heap for caching pages for use by the process; and
copy the one or more pages read from the store heap to the second in-memory heap.
66. The system of claim 53,
wherein the process is a Java process, and wherein the virtual machine is a Java virtual machine.
67. A system comprising:
a device configured to execute a virtual machine, wherein the virtual machine is configured to execute processes;
a persistent memory device coupled to the device, wherein the persistent memory device is configured to store checkpointed states for the processes;
wherein the device is further configured to manage the processes executing within the device according to a virtual machine process manager, and wherein the virtual machine process manager is configured to:
checkpoint a state of a first process executing within the virtual machine to the persistent memory device;
expire one or more leases to services for the first process on the virtual machine;
suspend the first process executing within the virtual machine;
read a state of a suspended second process from the persistent memory device, wherein the state of the second process was stored to the persistent memory device prior to said executing the first process within the virtual machine;
reconstitute the state of the second process on the virtual machine;
establish one or more leases to services for the second process on the virtual machine; and
resume the execution of the second process within the virtual machine.
68. The system of claim 67,
wherein the device is further configured to:
stop execution of the virtual machine within the device consequent to said suspending the first process executing within the virtual machine; and
restart execution of the virtual machine on the device prior to said reading the state of the second process from the persistent memory device.
69. The system of claim 67,
wherein the execution of the virtual machine on the device is not stopped between said suspending the first process executing within the virtual machine and said resuming the execution of the second process within the virtual machine.
70. The system of claim 67,
wherein the state of the second process comprises:
a heap for the second process, wherein the heap comprises code and data for the second process executing on the virtual machine.
71. The system of claim 67,
wherein the state of the second process comprises:
data describing the one or more leases to services for the second process on the virtual machine, wherein the data describing the one or more leases is used by the virtual machine process manager in said establishing the one or more leases to services for the second process on the virtual machine.
72. The system of claim 67,
wherein the one or more leases to services include one or more leases to remote services, wherein the remote services are services provided on devices other than the device within which the process is executing.
73. The system of claim 67,
wherein the one or more leases to services include one or more leases to local services, wherein the local services are services provided on the device within which the process is executing.
74. The system of claim 67,
wherein the one or more leases to services include one or more leases to system services, wherein a system service comprises system code for accessing a resource external to the process, wherein the system code is provided on the device within which the process is executing.
75. The system of claim 67,
wherein the state of the second process comprises a stored execution state of the device comprising the virtual machine; and
wherein, in reconstituting the state of the second process on the virtual machine, the virtual machine process manager is further configured to:
reconstitute a current execution state of the device comprising the virtual machine to the stored execution state of the device.
76. The system of claim 67,
wherein the persistent memory device comprises a plurality of persistent heaps for a plurality of processes; and
wherein, in checkpointing the state of the first process executing within the virtual machine to the persistent memory device, the virtual machine process manager is further configured to:
checkpoint the state of the first process on the virtual machine to a first persistent heap for the first process in the plurality of heaps comprised in the persistent memory device; and
wherein, in reading the state of the second process from the persistent memory device, the virtual machine process manager is further configured to:
read the state of the second process from a second persistent heap for the second process in the plurality of heaps comprised in the persistent memory device.
77. The system of claim 67,
wherein the virtual machine comprises a first in-memory heap for caching pages for use by the first process, wherein the pages comprise code and data for the first process;
wherein the persistent memory device comprises a first store heap for storing pages flushed from the first in-memory heap; and
wherein, in checkpointing the state of the first process on the virtual machine to the persistent memory device, the virtual machine process manager is further configured to:
store one or more pages from the first in-memory heap to the first store heap in the persistent memory device.
78. The system of claim 77,
wherein, in suspending the first process execution on the virtual machine, the virtual machine process manager is further configured to:
delete the first in-memory heap from the virtual machine.
79. The system of claim 67,
wherein the persistent memory device comprises a second store heap for storing pages flushed from a deleted second in-memory heap for the second process, wherein the pages comprise code and data for the second process;
wherein, in reading the stored state of the second process from the persistent memory device, the virtual machine process manager is further configured to:
read one or more pages from the second store heap in the persistent memory device; and
wherein, in reconstituting the state of the second process on the virtual machine, the virtual machine process manager is further configured to:
reestablish on the virtual machine the previously deleted second in-memory heap for caching pages for use by the second process; and
copy the one or more pages read from the second store heap to the reestablished second in-memory heap.
80. The system of claim 67,
wherein the first process and second process are Java processes, and wherein the virtual machine is a Java virtual machine.
81. A carrier medium comprising programming instructions executable to checkpoint processes on a virtual machine executing within a device, wherein the program instructions are executable to implement:
a process executing within the virtual machine referencing an object in a virtual heap during execution, wherein the virtual heap comprises an in-memory heap and a store heap;
copying a section of the store heap comprising the referenced object from the store heap to the in-memory heap if the referenced object is in the store heap and not in the in-memory heap when referenced by the process;
the process accessing the referenced object in the in-memory heap; and
checkpointing a state of the process executing on the virtual machine to a first memory space;
wherein, in checkpointing a state of the process executing on the virtual machine to the first memory space, the program instructions are further executable to implement:
flushing one or more sections of the in-memory heap to the store heap.
82. The carrier medium of claim 81, wherein the one or more flushed sections comprise new objects or modified objects in regards to objects stored in the store heap prior to said flushing.
83. The carrier medium of claim 81,
wherein, in checkpointing a state of the process executing on the virtual machine to the first memory space, the program instructions are further executable to implement:
storing data describing one or more leases to services for the process, wherein the one or more services are external to the virtual machine on which the process is executing, and wherein the leases are grants of access to the one or more services; and
storing a computation state of the virtual machine to the first memory space, wherein the computation state of the virtual machine comprises information about the execution state of the process on the virtual machine.
84. The carrier medium of claim 81,
wherein the program instructions are further executable to implement:
repeating said checkpointing the state of the process so that the first memory space stores a plurality of states for the process; and
wherein each of the plurality of states for the process stored in the first memory space is a unique state of the process on the virtual machine.
85. The carrier medium of claim 81,
wherein the store heap for the process is one of a plurality of store heaps for a plurality of processes on the virtual machine; and
wherein the checkpointed state of the process is one of a plurality of checkpointed states in the first memory space for a plurality of processes on the virtual machine.
86. The carrier medium of claim 81,
wherein the first memory space is comprised in a first memory device coupled to the device.
87. The carrier medium of claim 81,
wherein the first memory space is comprised in a flash memory;
wherein the store heap comprises a plurality of cache lines; and
wherein each of the sections of the store heap comprise one or more of the plurality of cache lines.
88. The carrier medium of claim 81,
wherein the virtual machine is a Java virtual machine, and wherein the process is a Java application.
89. A carrier medium comprising programming instructions executable to manage processes on a virtual machine executing within a device, wherein the program instructions are executable to implement:
checkpointing a state of a process executing within the virtual machine to a persistent store;
expiring one or more leases to services for the process on the virtual machine;
stopping the process execution on the virtual machine;
reading the stored state of the process from the persistent store;
reconstituting the stored state of the process on the virtual machine;
establishing the one or more leases to services for the process on the virtual machine; and
resuming the process execution on the virtual machine.
90. The carrier medium of claim 89,
wherein the program instructions are further executable to implement:
stopping execution of the virtual machine within the device consequent to said stopping the process execution on the virtual machine; and
restarting execution of the virtual machine within the device prior to said reading the stored state of the process from the persistent store.
91. The carrier medium of claim 89,
wherein the execution of the virtual machine within the device is not stopped between said stopping the process execution on the virtual machine and said resuming the process execution on the virtual machine.
92. The carrier medium of claim 89,
wherein the state of the process comprises:
a heap for the process, wherein the heap comprises code and data for the process executing on the virtual machine;
data describing the one or more leases to services for the process on the virtual machine, wherein the data describing the one or more leases is used in said establishing the one or more leases to services for the process on the virtual machine; and
a stored execution state of the device comprising the virtual machine;
wherein, in reconstituting the state of the process on the virtual machine, the program instructions are further executable to implement:
reconstituting a current execution state of the device comprising the virtual machine to the stored execution state of the device.
93. The carrier medium of claim 89,
wherein the one or more leases to services include one or more leases to remote services, wherein the remote services are services provided on devices other than the device within which the process is executing.
94. The carrier medium of claim 89,
wherein the one or more leases to services include one or more leases to local services, wherein the local services are services provided on the device within which the process is executing.
95. The carrier medium of claim 89,
wherein the one or more leases to services include one or more leases to system services, wherein a system service comprises system code for accessing a resource external to the process, wherein the system code is provided on the device within which the process is executing.
96. The carrier medium of claim 89,
wherein the persistent store comprises a plurality of persistent heaps for a plurality of processes; and
wherein, in checkpointing the state of the process on the virtual machine to the persistent store, the program instructions are further executable to implement:
checkpointing the state of the process on the virtual machine to a first persistent heap for the process in the plurality of persistent heaps comprised in the persistent store.
97. The carrier medium of claim 89,
wherein the virtual machine comprises a first in-memory heap for caching pages for use by the process, wherein the pages comprise code and data for the process;
wherein the persistent store comprises a virtual heap for storing pages flushed from the first in-memory heap; and
wherein, in checkpointing the state of the process on the virtual machine to the persistent store, the program instructions are further executable to implement:
storing one or more pages from the first in-memory heap to the virtual heap in the persistent store.
98. The carrier medium of claim 97,
wherein, in reading the stored state of the process from the persistent store, the program instructions are further executable to implement:
reading the one or more pages from the virtual heap in the persistent store; and
wherein, in reconstituting the state of the process on the virtual machine, the program instructions are further executable to implement:
establishing on the virtual machine a second in-memory heap for caching pages for use by the process; and
copying the one or more pages read from the virtual heap to the second in-memory heap.
99. The carrier medium of claim 89,
wherein the process is a Java process, and wherein the virtual machine is a Java virtual machine.
100. A carrier medium comprising programming instructions executable to manage processes on a virtual machine executing within a device, wherein the program instructions are executable to implement:
checkpointing a state of a first process executing within the virtual machine to a persistent store;
expiring one or more leases to services for the first process on the virtual machine;
suspending the first process executing within the virtual machine;
reading a state of a suspended second process from the persistent store, wherein the state of the second process was stored to the persistent store prior to said executing the first process within the virtual machine;
reconstituting the state of the second process on the virtual machine;
establishing one or more leases to services for the second process on the virtual machine; and
resuming the execution of the second process within the virtual machine.
101. The carrier medium of claim 100,
wherein the program instructions are further executable to implement:
stopping execution of the virtual machine within the device consequent to said suspending the first process executing within the virtual machine; and
restarting execution of the virtual machine on the device prior to said reading the state of the second process from the persistent store.
102. The carrier medium of claim 100,
wherein the execution of the virtual machine on the device is not stopped between said suspending the first process executing within the virtual machine and said resuming the execution of the second process within the virtual machine.
103. The carrier medium of claim 100,
wherein the state of the second process comprises:
a heap for the second process, wherein the heap comprises code and data for the second process executing on the virtual machine;
data describing the one or more leases to services for the second process on the virtual machine, wherein the data describing the one or more leases is used in said establishing the one or more leases to services for the second process on the virtual machine; and
a stored execution state of the device comprising the virtual machine;
wherein, in reconstituting the state of the second process on the virtual machine, the program instructions are further executable to implement:
reconstituting a current execution state of the device comprising the virtual machine to the stored execution state of the device.
104. The carrier medium of claim 100,
wherein the one or more leases to services include one or more leases to remote services, wherein the remote services are services provided on devices other than the device within which the process is executing.
105. The carrier medium of claim 100,
wherein the one or more leases to services include one or more leases to local services, wherein the local services are services provided on the device within which the process is executing.
106. The carrier medium of claim 100,
wherein the one or more leases to services include one or more leases to system services, wherein a system service comprises system code for accessing a resource external to the process, wherein the system code is provided on the device within which the process is executing.
107. The carrier medium of claim 100,
wherein the persistent store comprises a plurality of persistent heaps for a plurality of processes; and
wherein, in checkpointing the state of the first process on the virtual machine to the persistent store, the program instructions are further executable to implement:
checkpointing the state of the first process on the virtual machine to a first persistent heap for the first process in the plurality of heaps comprised in the persistent store; and
wherein, in reading the state of the second process from the persistent store, the program instructions are further executable to implement:
reading the state of the second process from a second persistent heap for the second process in the plurality of heaps comprised in the persistent store.
108. The carrier medium of claim 100,
wherein the virtual machine comprises a first in-memory heap for caching pages for use by the first process, wherein the pages comprise code and data for the first process;
wherein the persistent store comprises a first virtual heap for storing pages flushed from the first in-memory heap; and
wherein, in checkpointing the state of the first process on the virtual machine to the persistent store, the program instructions are further executable to implement:
storing one or more pages from the first in-memory heap to the first virtual heap in the persistent store.
109. The carrier medium of claim 100,
wherein the persistent store comprises a second virtual heap for storing pages flushed from a deleted second in-memory heap for the second process, wherein the pages comprise code and data for the second process;
wherein, in reading the stored state of the second process from the persistent store, the program instructions are further executable to implement:
reading one or more pages from the second virtual heap in the persistent store; and
wherein, in reconstituting the state of the second process on the virtual machine, the program instructions are further executable to implement:
reestablishing on the virtual machine the previously deleted second in-memory heap for caching pages for use by the second process; and
copying the one or more pages read from the second virtual heap to the reestablished second in-memory heap.
110. The carrier medium of claim 100,
wherein the first process and second process are Java processes, and wherein the virtual machine is a Java virtual machine.
Description
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of virtual machines, and more particularly to a system and method for providing process persistence in a virtual machine.
2. Description of the Related Art
The problem of migrating a running process, for example, an application, from one machine to another on a network has been tried for years, and there is much research literature on the subject of "process migration," but not much success in actually solving this difficult problem.
Currently, with the world moving towards a network centric model of computing, with unprecedented connectivity, there is a growing need to run an application (editor, email, browser, etc.) on one computer, and to be able to later resume running that same application from another machine in another location. Such a need can only be fulfilled via application migration. At the same time, modern operating systems have become very complex, and tend to have multiple applications running on a very thick client, and this complexity has resulted in much unreliability. It's thus desirable to be able to separate an application from the rest of the complex operating system, and persist it somewhere on the net, where it is protected from the complex, thick client system. This need, as well, can only be fulfilled via persistent application migration.
Java.TM.
The computer world currently has many platforms, among them Microsoft Windows.RTM., Apple Macintosh.RTM., OS/2, UNIX.RTM., Linux and NetWare.RTM.. Software must be compiled separately to run on each platform. The binary file for an application that runs on one platform cannot run on another platform, because the binary file is platform-specific.
A "virtual machine" may be defined as an operating environment that sits on top of one or more other computer platforms, and provides the capability to run one binary file on the virtual machine on the one or more other computer platforms. Thus, an application is written and compiled to run on the virtual machine, and thus does not need to be compiled separately to run on the one or more other computer platforms.
The Java Platform is a software platform for delivering and running applets and applications on networked computer systems. What sets the Java Platform apart is that it sits on top of other platforms, and executes bytecodes, which are not specific to any physical machine, but are machine instructions for a virtual machine. A program written in the Java Language compiles to a bytecode file that can run wherever the Java Platform is present, on any underlying operating system. In other words, the same file can run on any operating system that is running the Java Platform. The Java Platform has two basic parts, the Java Virtual Machine and the Java Application Programming Interface (Java API).
The Sun Java technologies are grouped into three editions: Java 2 Micro (J2ME), Standard (J2SE), and Enterprise (J2EE) Editions. Each edition includes a Java Virtual Machine (JVM) that fits inside a range of consumer devices such as set-top, screenphone, wireless, car, and digital assistant devices J2ME specifically addresses the consumer space, which covers the range of small devices from smart cards and pagers up to the set-top box, an appliance almost as powerful as a computer. The consumer devices targeted by J2ME, such as set-top boxes, printers, copiers, and cellular phones, typically have fewer resources and more specialized functionality than a typical Network Computer. Such devices may have special constraints such as small memory footprint, no display, or no connection to a network. The J2ME API provides the smallest Java API one of these limited devices can have and still run. A Java-powered application written for one particular device may operate on a wide range of similar devices. Applications written with J2ME are upwardly scalable to work with J2SE and J2EE
Java Remote Method Invocation (RMI)
RMI is a Java programming language-enabled extension to traditional remote procedure call mechanisms. RMI allows not only data to be passed from object to object around the network but full objects, including code.
K Virtual Machine (KVM)
The K Virtual Machine (KVM) is a Java runtime environment that is an extremely lean implementation of the Java virtual machine for use in devices that have a small memory footprint. The KVM is the core of the Java 2 Micro Edition (J2ME). The KVM is suitable for 16/32-bit RISC/CISC microcontrollers with a total memory of no more than a few hundreds of kilobytes (Kbytes) and sometimes less than 128 Kbytes of RAM. This typically applies to small-footprint memory devices, including digital cellular phones, pagers, mainstream personal digital assistants, low-end analog set-top boxes, and small retail payment terminals.
Application Migration and Java
By writing an application in Java, the application is not tied to a particular machine, but is rather written to run on an abstract or "virtual" machine, the Java Virtual Machine (JVM). Consequently, it is possible for the application to run on any machine on the network that implements the JVM specification. This aids in process migration, because past attempts at this problem have been largely foiled by differences, even slight ones, among the various machines on a network where an application is intended to migrate and run. By itself, though, an application written in Java cannot migrate from one machine on a net to another, because once the application starts running, it runs only in the heap of the JVM on which it initially started.
The Java language provides the programmer with an object model, a strong type system, automatic main memory storage management and concurrency through lightweight threads. However, the Java platform provides no satisfactory way of maintaining these properties beyond the single execution of a JVM. Instead, the programmer must deal explicitly with saving the state of an application, using one of a variety of persistence mechanisms, for example, file input/output, object serialization or relational database connectivity, none of which approach complete support for the full computational model. This lack of completeness, while only a minor nuisance for simple applications, becomes a serious problem as application complexity increases.
Orthogonal Persistence for Java
Orthogonal persistence for the Java platform (OPJ) addresses some of the limitations of application migration with Java with no changes to the source language and minor modifications to the specification of the Java Virtual Machine life cycle. In effect, orthogonal persistence extends the automatic memory management of the Java platform to encompass stable memory.
OPJ allows a running Java application to persist with no change to the application or to Java (thus orthogonal). This is achieved by enhancements to the JVM that implement a persistent heap that parallels the heap that Java code runs in. It is possible to suspend a running application and have a checkpoint result in the persistent heap that can later be reactivated on that same JVM. However, migrating to another JVM on another machine is not supported.
Another limitation of the persistent heap and checkpointing as implemented in OPJ is that any portions of a process that are dependent upon external state and not transient may be invalid when the code runs again, because the actual external state may have changed. An example of an external state is a socket for a network connection.
Yet another limitation of the persistent heap and checkpointing as implemented in OPJ is that it supports one large persistent heap for all Java code running on the system, making it difficult to separate out one particular application to migrate to another node. The persistent heap may include system Java objects and application Java objects. System Java objects are those Java objects tied to the platform (machine and operating system) on which the JVM is executing with the Java Native Interface (JNI). System Java objects may include native methods for the platform on which the JVM is executing. The application Java objects for the particular application would have to be separated from the application Java objects from any other running process and from the system Java objects.
Still yet another limitation of the OPJ model is that it requires two separate garbage collectors, one for the "in-memory" heap and one for the persistent heap.
JVM Separation Models
In a system providing application migration, it would be desirable to separate an application so that only it runs in a heap (and is persisted in a persistent heap). One way to do this is to start a separate JVM on the machine for each application. Although simple, the approach may not be practical. For one thing, this solution uses many system resources. Other approaches for application separation are hierarchical, with one "real" JVM and many "virtual" JVMs multiplexed on top. It would be desirable to provide a virtual machine separation model that separates applications into discrete persistent stores, permits the running of applications one at a time in an in-memory heap, and that does so without requiring the running of multiple copies (real or virtual) of the JVM.
SUMMARY OF THE INVENTION
The problems outlined above may be solved in large part by a system and method for persistent application migration that provides application separation and a method of maintaining the properties of a process beyond the single execution of a virtual machine such as a Java Virtual Machine (JVM) while preserving the external state of the process.
In one embodiment, an application on a system may be separated from other applications and from system code and data, and thus migratable separately from the other applications. In one embodiment, one or more applications on a system may each have an in-memory heap serving as "physical" memory that is being used for the current execution of the application, a virtual heap that may include the entire heap of the application including at least a portion of the runtime environment, and a persistent heap or store where the virtual heap can be checkpointed. In one embodiment, the virtual heap and the persistent heap may be combined in one memory (the virtual heap may serve as the persistent heap). Alternatively, the virtual heap may be checkpointed to a separate, distinct persistent heap. The combination of the in-memory heap, the virtual heap, and the persistent store may be referred to as the "virtual persistent heap."
A heap may include code and data for use by the application. In object-oriented programming languages such as Java, at least some of the code and data in the heap for the application may be encapsulated in objects. Objects may be defined as structures that are instances of a particular class or subclass of objects. Objects may include instances of the class's methods or procedures (code) and/or data related to the object. An object is what actually "runs" in an object-oriented program in the computer.
A heap may also include structures for managing the application's code and data in the heap. For example, a heap may be divided into sections, for example pages or cache lines. The sections of the heap may be grouped into sets of two or more sections for some heap processing functions such as garbage collection. Sections of the heap may include structures for managing code and data (objects) in the section. For example, one or more structures for tracking internal and external references to objects in a section may be kept in the sections of memory. An internal reference to an object may be defined as a reference to an object from another object in the same section of the heap. An external reference may be defined as a reference to an object from another object in another section of the heap.
In one embodiment, an application may establish one or more leases to local and/or remote services external to the application. In one embodiment, an application may establish one or more leases to system code that give the application access to resources external to the application such as system resources. System code for accessing an external resource may be referred to as a system service. A lease on system code for accessing an external resource may be referred to as a leased system service. For example, an application may establish leases to system services that give the application access to system drivers for accessing communications ports in the system.
In a virtual persistent heap, the entire heap may be made persistent. The virtual persistent heap may enable the checkpointing of the state of the computation of the virtual machine to a persistent storage such as a disk or flash device for future resumption of the computation at the point of the checkpoint. The Virtual Persistent Heap also may enable the migration of the virtual machine computation states from one machine to another. Both the data and computation state may be migrated. One embodiment may also provide for the suspension and resumption of an application, such as upon restarting a device after an intentional or unintentional shutdown of the device.
In one embodiment, the virtual heap may allow the running of a process on a "physical" heap that is smaller than may otherwise be required. As an example, the virtual heap may be an order of magnitude larger than the physical, in-memory heap. In one embodiment, the virtual heap may be maintained on non-volatile memory storage external to the device running the virtual machine, and portions of the heap for the current execution state of the process may be cached in and out of a "physical" heap resident in local memory on the device. For example, the device may connect to a server on the Internet, and the server may provide non-volatile storage space for the virtual heap. In another embodiment, the external storage for the virtual heap may reside on a non-volatile storage attached to the device, for example, a Flash card or hard disk drive.
With persistence, an application may be checkpointed and suspended on a virtual machine, and a second application may then start execution on the virtual machine without ending the virtual machine process. This avoids the overhead of starting a new virtual machine for a new application. For example, a virtual machine may be launched on a system when one is required to run a first application. When a second application is launched, the web browser may not start a second virtual machine to run the second application, as is done in the prior art, but may instead checkpoint and suspend the first application, and then run the second application on the same virtual machine the first application was running on. The second application at some point may be checkpointed and suspended, and the first application may resume execution at the last checkpointed state prior to its suspension. In another example, a web browser may launch a virtual machine to run a first application. The web browser may keep the virtual machine active after the first application completes, and later use it to run a second application. In the prior art, terminating an application would have caused the virtual machine it was running on to terminate execution as well, requiring a new virtual machine to be launched for each application.
The virtual persistent heap may enable the saving of the entire state of the virtual machine heap for possible future resumption of the computation at the point the save was performed, and may permit the migration of the computation to a different system. In one embodiment, the saved state of the virtual machine heap may also provide the ability to restart the virtual machine after a system crash or shutdown to a previously saved persistent state. This persistent feature may be useful for small consumer and appliance devices including Java-enabled devices, such as cellular phones and Personal Digital Assistants (PDAs), as these appliances may be shutdown and restarted often. The virtual persistent heap may include the entire address space of the virtual machine heap an application is using.
Embodiments of the virtual persistent heap may include at least one of a caching method, a database store method, and a garbage collection method as described below.
A Caching Method for the Virtual Persistent Heap
A feature of the virtual persistent heap is the method used to cache portions of the virtual persistent heap into the physical heap. In one embodiment, the virtual persistent heap may include a caching mechanism that is effective with small consumer and appliance devices that typically have a small amount of memory and that may be using flash devices as persistent storage. The caching strategy may provide a reduced amount of caching and may help to improve locality among elements of the virtual persistent heap that are cached in the physical heap, thus minimizing caching overhead.
One embodiment includes a caching mechanism in which the virtual persistent heap is divided into cache lines. A cache line is the smallest amount of virtual persistent heap space that can be loaded or flushed at one time. Caching in and caching out is operations are used to load cache lines into the heap or to flush dirty cache lines into the store. To reduce heap waste, object locality in a cache line may be improved by using object caching nurseries and a generational garbage collector.
Database Store Method for a Virtual Persistent Heap
In one embodiment, a database store method and Application Programming Interface (API) may be provided for the virtual persistent heap. The database store method may provide a mechanism to cache portions of the virtual persistent heap into the in memory physical heap for the virtual machine. The virtual heap may be stored in a persistent store. Thus, in one embodiment, the database store method and API may be provided to manage the virtual persistent heap in the store. The store API may provide atomicity on the store transaction to substantially guarantee the consistency of the information stored in the database.
The database store API may provide several methods to manage the virtual persistent heap in the store. The methods may include, but are not limited to: opening the store, closing the store, atomic read transaction (read a set of cache lines), atomic write transaction (write a set of cache lines), and atomic delete transaction (delete a set of cache lines).
Garbage Collection Method for a Virtual Persistent Heap
A garbage collection method may be provided for the virtual persistent heap. In one embodiment, the garbage collection method may be used with small consumer and appliance devices, for example, Java-enabled devices, which may have a small amount of memory and may be using flash devices as persistent storage. In one embodiment, the garbage collection method is implemented to provide good performance where only a portion of the virtual persistent heap may be cached in the physical heap. The virtual persistent heap may use a single virtual heap address space for both the store heap and the in-memory heap. In one embodiment, a single garbage collector may be run on the virtual heap address space.
In one embodiment, the garbage collection method may start at the root of the heap and flag objects that are referenced (i.e. need to be kept in the heap). Then, objects not flagged may be removed from the heap. Alternatively, the garbage collection method may flag objects that are not referenced, and then may remove the flagged objects. Garbage collection may cause the heap to become fragmented so that a large object may not fit in available free space. The garbage collection method thus may include a compaction phase to reduce or substantially eliminate fragmentation and to improve object locality.
Small appliance and consumer devices may use flash devices for non-volatile memory storage. Flash devices typically have special characteristics, such as large write I/O blocks (for example, 128 Kbytes) and destructive writes. In one embodiment, the number of writes performed to the flash device by the garbage collector may be minimized to increase the life of the flash device. The garbage collector for the virtual persistent heap may be implemented using working sets and/or object nurseries for short life objects.
BRIEF DESCRIPTION OF THE DRAWINGS
Other objects and advantages of the invention will become apparent upon reading the following detailed description and upon reference to the accompanying drawings in which:
FIG. 1a is a block diagram illustrating a device with virtual persistent heap and persistent store space located on the device according to one embodiment of the invention;
FIG. 1b is a block diagram illustrating a device with virtual persistent heap and persistent store space located external to the device according to one embodiment of the invention;
FIG. 1c is a block diagram illustrating a device with virtual persistent heap on the device and persistent store space located external to the device according to one embodiment of the invention;
FIG. 1d is a block diagram illustrating a client device, proxy server, and server with persistent store space according to one embodiment of the invention;
FIG. 1e is a block diagram illustrating a virtual heap and leases to local and remote resources according to one embodiment of the invention;
FIG. 1f is a block diagram illustrating application virtual heaps and leases to system resources according to one embodiment of the invention;
FIG. 2 is a block diagram illustrating virtual persistent heap architecture according to one embodiment of the invention;
FIG. 3 is a state diagram illustrating the states of a page in a virtual persistent heap according to one embodiment of the invention;
FIG. 4 is a flowchart illustrating a computation method for the in-memory heap page addresses according to one embodiment of the invention;
FIG. 5a is a block diagram illustrating an application migration process with a stored state from a first process sent from a persistent store to a second process according to one embodiment of the invention;
FIG. 5b is a block diagram illustrating an application migration process with a persistent store for each process according to one embodiment of the invention;
FIG. 6 is a flowchart illustrating a method for migrating an application according to one embodiment of the invention;
FIG. 7 is a block diagram illustrating virtual persistent heap architecture using cache lines according to one embodiment of the invention;
FIG. 8 is a flowchart illustrating a computation method for the in-memory heap cache line addresses according to one embodiment of the invention;
FIG. 9 is a block diagram illustrating a device with virtual heap, object nursery and garbage collector according to one embodiment of the invention;
FIG. 10a is a flowchart illustrating garbage collecting a virtual heap according to one embodiment of the invention;
FIG. 10b is a flowchart illustrating the processing of a nursery region in a virtual heap according to one embodiment of the invention;
FIG. 10c is a flowchart illustrating garbage collection performed on one or more regions of a heap according to one embodiment of the invention;
FIG. 11a is a flowchart illustrating an atomic read transaction from a persistent store for a process;
FIG. 11b is a flowchart illustrating an atomic write transaction to a persistent store for a process; and
FIG. 11c is a flowchart illustrating an atomic delete transaction from a persistent store for a process.
Item numbers for objects in the Figures may be repeated in more than one Figure to signify objects that are substantially similar in the Figures.
While the invention is susceptible to various modifications and alternative forms, specific embodiments are shown by way of example in the drawings and are herein described in detail. It should be understood however, that drawings and detailed description thereto are not intended to limit the invention to the particular form disclosed, but on the contrary, the invention is to cover all modifications, equivalents and alternatives falling within the spirit and scope of the present invention as defined by the appended claims.
DETAILED DESCRIPTION OF SEVERAL EMBODIMENTS
FIG. 1a--A device with virtual persistent heap on the device
FIG. 1a illustrates an embodiment of a device 140 with virtual machine 101 and a virtual heap with persistence, referred to as a virtual persistent heap. In a virtual persistent heap, the entire heap may be made persistent. The virtual persistent heap may enable the checkpointing of the state of the computation of the virtual machine to a persistent storage such as a disk or flash device for future resumption of the computation at the point of the checkpoint. The Virtual Persistent Heap also may enable the migration of the virtual machine computation states from one machine to another. Both the data and computation state may be migrated. One embodiment may also provide for the suspension and resumption of an application, such as upon restarting a device after an intentional or unintentional shutdown of the device.
In FIG. 1a, device 140 includes a client 101 and memory 115. Client device 140 may be a computer platform with operating system, such as a PC or laptop computer running an operating system such as Microsoft Windows 9.times./NT, or a consumer or appliance device, for example, a cell phone or PDA. Client device 140 may include a service provider client, for example, a Jini client (not shown) for finding and leasing services on remote servers on a network. Client 101 may be a virtual machine such as a JVM or KVM. Client 101 may be used for running applications, for example, Java applications. One or more applications may be running on client 101, with one application typically executing and one or more applications suspended. Application 104 is shown as a currently executing application.
Memory 115 may be integrated in or directly attached to client device 140. Memory 115 may be a volatile memory such as Direct Inline Memory Modules (DIMMs) or non-volatile storage device such as a flash memory, a hard disk, or removable disk such as a floppy disk. This embodiment may use persistent store space 120 in memory 115 to store the virtual heap 110 for application 104. Persistent store space 120 may also include virtual heaps (not shown) for one or more other suspended applications.
Device 140 may comprises an operating system capable of executing the software to enable a virtual machine such as a JVM or KVM. The operating system may include a virtual memory manager (VMM) for managing virtual memory on device 140. The VMM may enable applications such as a virtual machine running on the device 140 to appear to have more physical memory than is actually present on the system by enabling virtual memory. The VMM may utilize storage such as a disk drive to set up a swap area. Sections of memory may be cached into a cache area in the physical memory for faster access by an application running on the device 140. Sections of memory may be flushed to the swap area on the storage when not actively in use by an application or to make room in physical memory for other sections of memory that may be in more immediate demand for direct access by an application. The sections of memory in the virtual memory on the device may be referred to as the heap for the application. Thus, a virtual machine running on device 140 may run on a heap in the virtual memory on the device.
The virtual machine may execute in a portion of the memory space managed by the operating system on the device 140. In one embodiment, the memory space may be a virtual memory space managed by a VMM for the operating system. The virtual machine may comprise a virtual machine memory space for use by processes executing on the virtual machine. As used herein, "process" may refer to, but is not necessarily limited to: applications, applets, programs, tasks, subprocesses, threads, and drivers. The virtual machine memory space may be managed by a virtual machine virtual memory manager (VM VMM) as described herein. The VM VMM may allow processes executing on the virtual machine to use a virtual heap as described herein, and may also provide persistence for the virtual heap. The virtual heap may include an in-memory heap as described herein, which may reside in the virtual machine memory space. The virtual heap may also include a store heap as described herein. In one embodiment, the store heap may be resident in the virtual machine memory space. In another embodiment, the store heap may be resident in memory external to the virtual machine, such as on a storage device attached to the device 140 directly or via the Internet, but accessible using the VM VMM. The entire memory space, including the virtual machine memory space and the store heap, may be referred to as the virtual machine virtual memory space.
The VM VMM as described herein may allow applications to execute on a virtual machine on device 140 that would otherwise require too much virtual machine memory space, and thus would not execute, by providing a virtual machine virtual memory space and a virtual heap for the application. The VM VMM and virtual heap as described herein may also allow multiple applications to run on a virtual machine by providing a store heap for each application, and allowing an application to be suspended by flushing its in-memory heap to its store heap, and a second application to be resumed by loading its in-memory heap into the virtual machine memory space from its store heap.
As used herein, the definition of a heap may include an area of computer main storage (memory) that a process may use to store data in some variable amount that won't be known until the program is running. A heap may be reserved for data that is created at runtime, that is, when a program is executing. A heap may also include portions of code for the process. In one embodiment, the process may be a Java process, and the code may be in Java classes. For example, a program may accept different amounts of input from one or more users for processing and then do the processing on all the input data at once. The heap may be pre-allocated for the process to use. The process manages its allocated heap by requesting a portion of the heap when needed, returning the portions when no longer needed, and doing occasional "garbage collecting," which makes portions of the heap available that are no longer being used and also may reorganize the available space in the heap to minimize fragmentation of the memory. In one embodiment, Java classes, including Java classes containing code for the process, may be garbage collected to remove classes (and thus process code) that are no longer in use. A heap may be portioned into blocks, sectors, pages, cache lines, or any other division of memory that meets the requirements of the heap management method.
A "stack" may be defined as an area of memory that may be used for data whose size can be determined when the program is compiled. A stack may be managed substantially similarly to a heap except that portions of the stack may be taken out of storage in a certain order and returned in the same way.
Client device 140 may also include volatile memory for loading and running client 101. Client 101 then may load and run applications in its memory space. In-memory heap 108 may be maintained in client 101 memory space, or alternatively may be maintained in memory external to client 101 memory space. In-memory heap 108 may include a portion of virtual heap 110 currently cached for use by application 104.
In-memory heap 108 and virtual heap 110 may be divided into one or more sections. The sections may be sectors, pages, cache lines, or any other division of memory space. In-memory heap 108 may be used by application 104 for storing data and code currently being used in the execution of application 104. In-memory heap 108 may include a portion or all of virtual heap 110. If application 104 requires code or data that is not currently in heap 108, one or more sections of virtual heap 110 may be copied into in-memory heap 108. If there is insufficient room in in-memory heap 108, one or more sections of in-memory heap 108 may be removed from heap 108 before copying in the new sections. If one or more sections being removed from heap 108 are "dirty" (have been written to), the one or more dirty sections may be written to (flushed to) virtual heap 110 before being removed from in-memory heap 108.
Application 104 may create new code and data in sections of in-memory heap 108. The new code and data in in-memory heap 108 may be flushed to virtual heap 110.
The in-memory heap 108 may include a portion of the virtual heap 110 that is cached (acts as physical memory) for use by application 104. In one embodiment, the virtual heap address space may be divided into fixed size pages. Page-in and page-out operations may be used to move pages from the virtual heap 110 in store 120 to the in-memory heap 108 or to eject pages from the heap 108. Pages, page states and page addressing are further illustrated in FIGS. 2, 3 and 4.
At certain times, a checkpoint for application 104 may be written to persistent store space 120. In this application, a checkpoint is a persistent store of the state of an application and its execution environment (such as the virtual machine state) at a point in time. After storing a checkpoint for application 104, persistent store space 120 may include an entire, up-to-date copy of the virtual heap 110. In one embodiment, persistent store space 120 may also contain an entire copy of the virtual heap for one or more other applications. In one embodiment, persistent store space 120 may include one or more versions of copies of the virtual heap (checkpointed states) for each application.
The virtual persistent heap may allow the running of an application on a physical heap 108 that is much smaller than may otherwise be required. As an example, the virtual persistent heap 110 may be an order of magnitude larger than the physical, in-memory heap 108. In one embodiment, the virtual persistent heap may be maintained on non-volatile memory storage external to the device running the application, and portions of the heap for the current execution state of the application may be cached in and out of a physical heap resident in local memory on the device. For example, the device may connect to a server on the Internet, and the server may provide non-volatile storage space for the virtual persistent heap. In another embodiment, the external storage for the virtual persistent heap may reside on a non-volatile storage attached to the device, for example, a Flash card or hard disk drive.
With persistence, an application may be checkpointed and suspended on a virtual machine, and a second application may then start execution on the virtual machine without ending the virtual machine process. This avoids the overhead of starting a new virtual machine for a new application. For example, a virtual machine may be launched on a system when one is required to run a first application. When a second application is launched, the web browser may not start a second virtual machine to run the second application, as is done in the prior art, but may instead checkpoint and suspend the first application, and then run the second application on the same virtual machine the first application was running on. The second application at some point may be checkpointed and suspended, and the first application may resume execution at the last checkpointed state prior to its suspension. In another example, a web browser may launch a virtual machine to run a first application. The web browser may keep the virtual machine active after the first application completes, and later use it to run a second application. In the prior art, terminating an application would have caused the virtual machine it was running on to terminate execution as well, requiring a new virtual machine to be launched for each application.
The virtual persistent heap may enable the saving of the entire state of the virtual machine heap for possible future resumption of the computation at the point the save was performed, and may permit the migration of the computation to a different system. In one embodiment, the saved state of the virtual machine heap may also provide the ability to restart the virtual machine after a system crash or shutdown to a previously saved persistent state. This persistent feature may be useful for small consumer and appliance devices including Java-enabled devices, such as cellular phones and Personal Digital Assistants (PDAs), as these appliances may be shutdown and restarted often. The virtual persistent heap may include the entire address space of the virtual machine heap an application is using.
Embodiments of the virtual persistent heap may include at least one of a caching method, a database store method, and a garbage collection method as described below.
FIG. 1b--A Device with Virtual Persistent Heap External to the Device
FIG. 1b illustrates an embodiment of the invention where a device 140 includes a client 101, and memory 117 external to the client stores the persistent store space 120 with virtual heap 110. Memory 117 may be on any device external to but coupled to client device 140. Examples of methods in which the devices may be coupled include, but are not limited to: wireless connection (cell phones, Wireless Access Protocol (WAP)), infrared (IrDA), Ethernet, Universal Serial Bus (USB), and phone/modem. The connection may be an Internet connection. Memory 117 may be a volatile memory such as Direct Inline Memory Modules (DIMMs) or non-volatile storage device such as a flash memory, a hard disk, or removable disk such as a floppy disk. This embodiment may use persistent store space 120 in memory 117 to store the virtual heap 110 for application 104. Persistent store space 120 may also include virtual heaps (not shown) for one or more other suspended applications on device 140. Persistent store space 120 may also include virtual heaps (not shown) for one or more applications running on devices other than device 140.
The architecture and operation of in-memory heap 108 and virtual heap 110 as illustrated in FIG. 1b may be substantially similar to that described in FIG. 1a. In the embodiment illustrated in FIG. 1b, caching, checkpointing, and other reads or writes to virtual heap 110 may be performed over an external interface such as a network connection, rather than being performed over an internal interface such as a memory bus as in the embodiment illustrated in FIG. 1a.
FIG. 1c--A Device with Virtual Persistent Heap Internal to the Device and a Persistent Store External to the Device
FIG. 1c illustrates an embodiment of the invention where a device 140 includes a client 101 and memory 115. Memory 115 may include virtual heap 110. This embodiment may also include a memory 117 external to the client. Memory 117 may include persistent store space 120 for holding checkpoints 111 of virtual heap 110. Memory 117 may be on any device external to but coupled to client device 140. Examples of methods in which the devices may be coupled include, but are not limited to: wireless connection (cell phones, Wireless Access Protocol (WAP)), infrared (IrDA), Ethernet, Universal Serial Bus (USB), and phone/modem. The connection may be an Internet connection. Alternatively, memory 117 may be integrated in or directly attached to device 140. Memory 117 may be a volatile memory such as one or more memory modules (for example, Direct Inline Memory Modules (DIMMs)), or a non-volatile storage device such as a flash memory, a hard disk, or removable disk such as a floppy disk. This embodiment may use persistent store space 120 in memory 117 to store the checkpoints 111 of virtual heap 110 for application 104. Persistent store space 120 may also include checkpoints of virtual heaps (not shown) for one or more other suspended applications on device 140. Persistent store space 120 may also include checkpoints of virtual heaps (not shown) for one or more applications running on devices other than device 140.
The architecture and operation of in-memory heap 108 and virtual heap 110 may be substantially similar to that described in FIG. 1a. Periodically, a checkpoint 111 of virtual heap 110 for application 104 may be written to persistent store space 120. After storing a checkpoint for application 104, persistent store space 120 may include an entire, up-to-date copy of the virtual heap 110. Persistent store space 120 may also include checkpointed copies of the virtual heap for one or more other applications.
Some embodiments may checkpoint one or more versions of virtual heap 110. For example, in the embodiment illustrated in FIG. 1c, multiple versions of checkpoint 111 for virtual heap 110 for application 104 may be stored in persistent store space 120. A method may be provided to select a checkpoint version from among one or more checkpointed version for resuming the application and/or virtual machine execution at a particular point.
FIG. 1d--A Client-Server System with Persistent Store Space
FIG. 1d is a block diagram illustrating a network including client system 100, gateway server 112, and server system 116 according to one embodiment of the invention. Server system 116 may include a service provider server 118, for example, a Jini or other network service connection system or compact service connection system server.
Jini.TM.
Sun Microsystems' Jini is an example of a Network Service Connection System (NSCS) that may be used with networked devices to locate and lease resources, herein referred to as services, on networked systems including servers, and to pass information to and from the services located on the networked systems.
The Jini technology makes it possible for an application to discover and use local and remote services. A local service may be a service that is provided on the same device as the application. A remote service may be a service that is provided by a device other than the device the application is executing on. Furthermore, applications that use such local and remote services may obtain leaseson the services. These leases may expire after a certain amount of time (or on demand). By modifying an application to use Jini when it accesses local and remote services (and to handle expiration and reactivation of a lease), the problem of maintaining the external state of a process during process migration may be addressed.
The Jini system federates computers and computing devices on a network into what appears to the user as a single system. Each Jini technology-enabled device preferably has some memory and processing power. Devices without processing power or memory may be connected to a Jini system, but those devices may be controlled by another piece of hardware and/or software, called a proxy, that presents the device to the Jini system and which itself contains both processing power and memory.
The Jini system is Sun Java technology-centered. The Jini architecture assumes that the Java programming language is the implementation language for components. The ability to dynamically download and run code is central to a number of the features of the Jini architecture. However, any programming language can be supported by a Jini system if it has a compiler that produces compliant bytecodes for the Java programming language.
Services
A service is an entity that can be used by a person, a program, or another service. A service may be a computation, storage, a communication channel to another user, a software filter, a hardware device, or another user. Services may be local or remote. A local service may be provided on the same device as the user of the service. A user of a service may be called a client, and the device client is accessing the service from may be called the client device. Thus, a client may access a service on the client device. A remote service may be provided on a device other than (external to) the client device. Examples of services include devices such as printers, displays, or disks: software such as applications or utilities; information such as databases and files: and users of the system, and translating from one word processor format to some other. Jini systems provide mechanisms for service construction, lookup, communication, and use in a distributed system. Services in a Jini system communicate with each other by using a service protocol, which is a set of interfaces written in the Java programming language.
Services may be found and resolved using a lookup service. The lookup service may be the central bootstrapping mechanism for the system and may provide a major point of contact between the system and users of the system. In precise terms, a lookup service maps interfaces indicating the functionality provided by a service to sets of objects that implement the service. In addition, descriptive entries associated with a service allow more fine-grained selection of services based on properties understandable to people.
A service is added to a lookup service by a pair of protocols called discovery and join; the service first locates an appropriate lookup service (by using the discovery protocol), and then it joins the lookup service (by using the join protocol).
Service Leasing
Access to many of the services in the Jini system environment is lease based. A lease is a grant of guaranteed access to a service over a period. A service may be a resource external to the virtual machine within which an application desiring a service is executing. A service may be a local service or a remote service. In Jini, a lease may be negotiated between the user of the service and the provider of the service as part of a service protocol: a service is requested for some period, and access is granted for some period, presumably considering the request period. If a lease is not renewed before it is freed--because the service is no longer needed, the client or network fails, or the lease is not permitted to be renewed--then both the user and the provider of the service may conclude the service can be freed. Leases may be exclusive or non-exclusive. Exclusive leases insure that no one else may take a lease on the service during the period of the lease; non-exclusive leases allow multiple users to share a service.
In one embodiment, an application may establish one or more leases to local and/or remote services external to the application. In one embodiment, an application may establish one or more leases to system code that give the application access to resources external to the application such as system resources. System code for accessing an external resource may be referred to as a system service. A lease on system code for accessing an external resource may be referred to as a leased system service. For example, an application may establish leases to a system services that give the application access to system drivers for accessing communications ports in the system.
In one embodiment, interactions between services and applications may be stateless. For example, each interaction request may be handled by the receiver using information included with the request.
Jini and JavaSpaces.TM.
The JavaSpaces technology package provides a distributed persistence and object exchange mechanism for code written in the Java.TM. programming language. Objects are written in entries that provide a typed grouping of relevant fields. Clients can perform simple operations on a JavaSpaces server to write new entries, lookup existing entries, and remove entries from the space. Objects in JavaSpaces are stored in Java Serialization Format. Server JavaSpaces provide persistent object storage replacing traditional file system storage persistence models. JavaSpaces servers provide network service connection system clients such as Jini clients access to a persistent and shareable object store.
Network Service Connection System for Small Footprint Devices
A consumer or appliance device with a small amount of memory may be referred to as a "small footprint device." A Compact Network Service Connection System (CNSCS) may be provided for use with small footprint network client devices (PDAs, cell phones, etc.) to locate and lease services on networked systems including servers, and to pass information to and from the located services and resources. The CNSCS may be designed specifically for use with small footprint network client devices that may be too "small" (not have enough resources such as memory) to support a system such as Jini. The CNSCS may be embodied as a self-contained message-passing system that may operate among similar small systems, and may be bridged to a complete Jini federation using a bridging server. Examples of such a CNSCS is described in U.S. Provisional Patent Application No. 60/209,525 to Slaughter, Saulpaugh, Traversat, Abdelaziz, Duigou, Joy, and Pouyoul, titled "DISTRIBUTED COMPUTING ENVIRONMENT", filed June 5, 2000, which is hereby fully incorporated by reference in its entirety, and in U.S. Provisional Patent Application No. 60/209,430 to Slaughter, Saulpaugh, Traversat, Abdelaziz, Duigou, Joy, and Pouyoul, titled "DISTRIBUTED COMPUTING ENVIRONMENT", filed Jun. 2, 2000, which is hereby fully incorporated by reference in its entirety, and in U.S. Provisional Patent Application No. 60/209,140 to Slaughter, Saulpaugh, Traversat, Abdelaziz, Duigou, Joy, and Pouyoul, titled "DISTRIBUTED COMPUTING ENVIRONMENT", filed Jun. 2, 2000, which is hereby fully incorporated by reference in its entirety.
CNSCS clients are typically small footprint devices that may include small display screens and keyboards. CNSCS clients may be mobile or non-mobile devices. Examples of mobile CNSCS clients may include, but are not limited to: cell phones, palmtop computers, notebook computers, Personal Digital Assistants (PDAs), desktop computers, and printers. An example of a non-mobile CNSCS client may be a light switch comprising a simple chip capable of receiving a simple set of commands (on/off) and of transmitting a simple set of status messages (on/off status).
A CNSCS client may include core CNSCS software and one or more client applications. A CNSCS client may connect to a "fixed" network through a variety of paths. Examples of connection methods may include, but are not limited to: wireless connection (cell phones, Wireless Access Protocol (WAP)), infrared (IrDA), Ethernet, and phone/modem. CNSCS clients may connect to a network through gateways. The gateways provide the client devices with access to CNSCS servers on the network. A gateway may include a proxy CNSCS server. When connected, a CNSCS client "finds" a proximity network on which the client can run one or more applications from the network. One or more of the applications may only be available on the particular network. A CNSCS client may also connect to a network to remotely access files on a server.
A mobile CNSCS client may send out broadcast messages using whatever physical interface it has (IRDA, WAP, proprietary connection, etc). All that is required of the device is that it can send and/or receive messages. Some devices may only have to receive messages. For example, a CNSCS capable light switch may only need to receive and act on messages (ON message, OFF message, or TOGGLE message). More sophisticated CNSCS clients may send out a message to join a CNSCS federation.
Message Capable Networking in CNSCS
A distributed computing facility can be built upon a messaging layer. Furthermore, a messaging layer (providing both reliable and unreliable messages) can be built upon the socket networking classes provided in an embedded Java platform. TCP, UDP, and IP are examples of message capable protocols that may be leveraged by CNSCS. Other more specialized protocols such as the Wireless Application Protocol (WAP) are also capable of supporting CNSCS messages. WAP is tuned for networks with high latency and low bandwidth. CNSCS messages also work well with other network drivers such as IrDA (Infrared Data Association) and Bluetooth beneath the transport. The only required portion of CNSCS for a device (above the basic networking protocol stack) is a thin messaging layer, and all additional facilities are optional.
CNSCS Spaces
A CNSCS Space may be smaller and simpler than a JavaSpace. Some CNSCS Spaces are transient, while others are persistent. Transient spaces may be used as rendezvous mechanisms for peer-to-peer communication (Palm Pilot IrDA, for example). Server CNSCS Spaces may provide persistent object storage, replacing traditional file system storage persistence models.
CNSCS Space servers provide CNSCS clients access to a persistent (and potentially shared) object store. In one embodiment of a CNSCS, the objects stored in a CNSCS Space (and sent in a message) may be represented in XML (eXtensible Markup Language). XML may be used as the means of representing objects because it is sufficiently rich, as well as being an Internet standard.
A persistent CNSCS Space is a directory containing XML representations of objects. Because XML is used to represent the space and its objects, Internet search facilities can be leveraged to find spaces and objects within those spaces and Java and non-Java objects created in C++ or any other object-oriented language may be stored and retrieved from a CNSCS Space or placed in a message.
XML object representations are language independent. In one embodiment, only an object's data is represented in XML, not its code. This means that Java and non-Java applications can send and receive objects from each other. Classes (with encapsulated bytecode) may be stored in a CNSCS Space or passed in a message.
XML class representations may not be supported in all platforms due to security and size constraints. In one embodiment, threads may be compiled into XML to enable virtual machine migration to a CNSCS Space. In this model, the CNSCS Space may be used as a persistent heap/virtual machine store.
A Java virtual machine understands the structure of a Java object, so in one embodiment, CNSCS may provide JVM extensions for compiling a Java object to XML, and for decompiling XML into a Java object. In some embodiments, the CNSCS may provide other extensions for compiling and decompiling other object types into XML or other messaging languages.
Space Searching
A CNSCS client may not need a browser. Instead, a search may be offloaded to a server that performs the actual search using a front-end proxy that parses the results for the client. Hence, CNSCS Space queues may be Internet document searches triggered by messages sent to a proxy.
CNSCS Leasing
As in Jini, access to many of the services in the CNSCS system environment may be lease based. A lease is a grant of access to a service. In one embodiment, an application may establish one or more leases to local and/or remote services external to the application. In one embodiment, an application may establish one or more leases to system code that give the application access to resources external to the application such as system resources. The leasing mechanism may allow clients to obtain leases for objects in a CNSCS Space. In one embodiment, the CNSCS leasing mechanism may use time-based leasing. In another embodiment, clients may make claims on Java objects, and register a callback method that may be invoked when another client desires a lease that is incompatible with current leaseholders. There may be several levels of CNSCS leases. A first level may not return a copy of the Java object when a lease is obtained, but simply registers an interest in this object being kept in the CNSCS Space. A second level does return a copy of the Java object when a lease is obtained at this level, but there could be multiple clients accessing the object. A third level does return a copy of the Java object when a lease is obtained at this level, and there are other clients are prohibited from accessing the object.
In one embodiment, interactions between processes and services provided through leases may be stateless. For example, each interaction request may be handled by the receiver using information included with the request.
Returning to FIG. 1d, service provider server 118 may include a persistent store space 120. Client system 100 may be a computer platform with operating system, such as a PC or laptop computer running Windows 9.times./NT, or a virtual machine, for example, a JVM or KVM, sitting on top of a computer platform or executing on a consumer or appliance device, for example, a cell phone or PDA. Client system 100 may include a service provider client 102, for example, a Jini or CNSCS client, for finding and leasing services on remote servers. Client system 100 may be used for running applications and applets, for example, Java applications and applets. One or more applications may be executing on client system 100. Application 104 is shown as a currently executing application, and application 106 is shown as a suspended application. Application 104 may access an "in-memory" heap 108. Persistent store space 120 may include a virtual heap 110 for application 104. Persistent store space 120 may also include a virtual heap (not shown) for application 106.
Client system 100 may broadcast and receive messages using whatever physical I/O interface it has (IRDA, WAP, Ethernet, modem, proprietary connection, etc). Client system 100 may access services on one or more servers on the network including server 116. In one embodiment, the service provider client 102 may connect to servers on the network through gateway server 112. A gateway 112 may include a proxy service provider server 114. When connected, the service provider client 102 may find server 116 on which the client 102 may provide, via lease or otherwise, persistent store space 120 for virtual heap space for one or more applications including applications 104 and 106. Checkpoints for applications may be stored in persistent store space 120. Thus, persistent store space 120 may be a service that may be leased by an application using a service provider system such as Jini or CNSCS.
A lease may be established for a leasable service 125 on server 124. The lease may be established for application 104 by service provider client 102. Service provider 102 may establish the lease through service provider proxy server 114. In one embodiment, leases to services and/or resources on client device 100 may also be established.
The architecture and operation of in-memory heap 108 and virtual heap 110 as illustrated in FIG. 1d may be substantially similar to that described in FIG. 1a. In the embodiment illustrated in FIG. 1d, caching, checkpointing, and other reads or writes to virtual heap 110 may be performed over a network connection, for example, over the Internet, rather than being performed over an internal interface such as a memory bus as in the embodiment illustrated in FIG. 1a.
FIG. 1e--A Virtual Heap and Leases to Local and Remote Resources
FIG. 1e is a block diagram illustrating a virtual heap 148 for an application and leases to local and remote resources according to one embodiment of the invention. Virtual heap 148 may include one or more pages of application code and data 152. Virtual heap 148 may also include one or more pages of system code and data 154. Pages 152 may include a lease to a service 164 that may include information describing the lease relationship with a service 166. Service 166 may be a local or remote service. In one embodiment, the lease may be established using an NSCS such as Jini. In another embodiment, the lease may be established using a CNSCS.
Pages 152 may also include a lease to system code 156. In one embodiment, the lease may be established using an NSCS such as Jini. In another embodiment, the lease may be established using a CNSCS. The lease to system code 156 may give the application access to a system resource 162 by leasing native method 158. Native method 158 may be system code that invokes one or more system native code functions 160 for accessing system resource 162. For example, system resource 162 may be a bus port such as a USB port. Code 160 may be the native language driver for the USB port. Native method 158 may include the code necessary to invoke various functions provided by the native language USB driver.
In one embodiment, when the application is checkpointed, the system code and data pages 154 may not be checkpointed. When the application code and data pages 154 are checkpointed, service lease 164 and system resource lease 156 may be checkpointed. In one embodiment, the information checkpointed for a lease (system resource or service lease) may include enough information to re-establish the lease if necessary. In one embodiment, leases to system resources and services may be stateless--no record of previous interactions between the application and the service or resource may be kept, and each interaction request between the application and the service or resource may be handled based entirely on information that comes with it. Being stateless may simplify the checkpointing of the leases because no current or past state information needs to be checkpointed for the leases. If the application needs to be migrated to another device, or if the application is suspended for some reason, then the leases held by the application may be cancelled, releasing the services and/or resources held by the leases. When the application is resumed (locally or on another device), then the lease information from the checkpointed state of the application may be used to re-establish the leases to services and/or system resources.
In one embodiment, an application may migrate to a device with a different system and native language than the system and native language of the device from which it is migrating. In this embodiment, the lease to system resource 156 may be reestablished to a method 158 in the system code 154 of the device to which the application migrated. Native code functions 160 for accessing system resource 162 may be in the native code of the new device.
In one embodiment, the application may migrate to a device that does not have system resource 162. In this case, the application may be notified that the lease to the system resource cannot be re-established. In one embodiment, the application may migrate to a device that does not have access to service 166. In one embodiment, the application may be notified that the lease to the service cannot be re-established. In one embodiment, when it is discovered that service 166 is not available, an alternate service may be searched for to fulfill the functionality of service 166, and, if found, a lease may be established to the alternate service.
FIG. 1f--A Virtual Heap and Leases to System Resources
FIG. 1f is a block diagram illustrating a virtual heap 148a and 148b for two applications with leases to system resources 162a and 162b according to one embodiment of the invention. In this embodiment, a heap 164 external to virtual heaps 148a and 148b may be used to store system code and data that may be shared among two or more applications.
Virtual heaps 148a and 148b may each include one or more pages of application code and data 152a and 152b. Pages 152a and 152b may include leases to system code 156a and 156b that may give the application access to system resources 162a and 162b respectively by leasing shared native methods 158a and 158b. Native methods 158a and 158b may include system code that may invoke one or more native code functions 160 for accessing system resources 162a and 162b.
Some system resources may be shareable and others may require exclusive access privileges. In one embodiment, if a native method in heap 154 allows shared access, two or more applications may hold leases to the same native method, and thus the same system resource, simultaneously.
FIG. 2--Virtual Persistent Heap Architecture
FIG. 2 is a block diagram illustrating a virtual persistent heap architecture according to one embodiment of the invention. Application 104 may be executing in client system 100. Application 104 may be using in-memory heap 108.
Persistent store 120 may reside on a server on the network to which client system 100 has access, or alternatively may be located in a local non-volatile memory on the system application 104 is executing on. Page table 122 may reside on the same system as application 104 or alternatively may reside on another system on the network.
The persistent store 120 may include an entire copy of the virtual heap 110 (virtual memory) for application 104. The "in-memory" heap 108 may include a portion of the virtual heap 110 that is cached (acts as physical memory). In one embodiment, the virtual persistent heap is a page-based heap. The virtual heap address space is divided into fixed size pages. Page-in and page-out operations are used to move pages from the persistent store 120 to the in-memory heap 108 and to eject pages from the in-memory heap 108.
In this application, the terms "physical heap" or "heap" may be used to indicate the heap structure in memory 108. This is only a portion of the total virtual heap 110 saved in the persistent store 120. The term "virtual heap" may be used to indicate the entire heap image saved in the store 120. The "in memory" heap address space may be viewed as the physical memory. The "in store" heap address space may be viewed as the virtual memory.
The store 120 may be segmented into two or more disjoint virtual heaps. Each checkpointed application such as application 104 has its own virtual heap space reserved in the store. In exemplary persistent store 120, a virtual heap space exists for application 106 and application 104, and two unused virtual heap spaces exist to allow for two more applications.
Paging provides a simple model to move data from the persistent store 120 to the in-memory heap 108 in virtual machine 100. In one embodiment, a page table 122 and offset based address translation may be used to convert virtual heap 110 references into in-memory heap 108 references. Relatively small pages may be used to reduce heap waste. In one embodiment, a paging-based approach may enable page protection mechanisms and support for DMA and block I/O devices.
In one embodiment, object-caching granularity may be implemented instead of paging. Object-caching granularity is possible if objects can efficiently be moved in the heap. A consideration in embodiments using object handles is the memory footprint constraint. The object handle area may take more memory space than related structures such as handle tables in embodiments using pages.
Using page handles rather than object handles may give the ability to tune the implementation to fit the memory footprint requirement of a targeted device. The page size determines the amount of space required for the handle table. Larger memory environments may use smaller pages. Smaller memory environments may need to use larger pages. Larger objects may be broken up and stored across multiple pages, allowing portions of objects to be cached in an out of the in-memory heap 108. This may allow devices with limited memory resources to support objects, and therefore applications, that may not be supportable with object caching granularity. With object caching granularity, the entire object may have to be cached into in-memory heap 108.
One embodiment may use a page-in and page-out approach to bring pages from the virtual heap 110 into the in-memory heap 108. For embodiments in which persistent store 120 is comprised in a flash memory device, paging-out may use a scatter/gather object phase to only write updated objects to increase the life of the flash device. In one embodiment, this may be combined with a log-based approach to guarantee atomicity on store transactions.
In a paging-based system, the page size may be increased to reduce the page table 122 size. Increasing the page size may permit the grouping of multiple objects into a single page. In this case, a single page table entry may play the role of multiple object handle entries (one handle for each object in the page). Grouping objects into a single table entry may allow the reduction of the memory footprint required for a handle table, as there may be fewer handles. Updating a single object in the page may require the writing of the entire page (all objects in the page). Alternatively, reducing the page size allows fewer objects to be stored in a page, thus reducing paging granularity. This approach may increase the page table size. The page size may be adjusted accordingly based upon memory constraints on the device on which the paging-based system is implemented.
In one embodiment, the virtual heap 110 may be divided into a fixed number of pages. In one embodiment, to aid in efficient address translation, the application virtual heap size (i.e. the Kernel plus all user pages) may be a fixed multiple of the size of the in-memory heap 108. This allows each application virtual heap store to start at a multiple heap size offset in the persistent store 120. In this embodiment, the address translation includes subtracting a fixed heap size multiple. Since a virtual machine may not have access to a hardware translation mechanism, the address translation may be simplified so it can be efficiently performed in software.
An offset based schema may be used to convert a virtual heap address into an in-memory heap address. All object references in the virtual heap 110 and the in-memory heap 108 may be kept as virtual heap addresses. In one embodiment, there may be an address translation to convert the virtual heap address into the physical heap location. The CPU of the system or CPU layer of the virtual machine may perform address translation from the virtual heap address space into the in-memory heap location via a Page Table 122 entry. The Page table 122 maintains the mapping of the virtual heap 110 page into the heap 108. For each virtual heap 110 address reference (read or write), code may be inserted (read/write barriers) to verify the validity of the address (i.e. check if the corresponding page is resident in the heap), and to translate it into the in-memory heap 108 reference. The process of converting heap addresses is illustrated in FIG. 4.
In some embodiments, the virtual machine CPU layer, for example, the Java CPU layer, may provide access to hardware Memory Management Unit (MMU) address translation functions, allowing object handle indirections to be done in hardware.
In one embodiment, an object in the virtual address space may maintain references to other objects via a valid or invalid address. A valid address may mean the corresponding page is resident in the in-memory heap 108. An invalid address may mean the corresponding page is not resident in the in-memory heap 108.
Page Table 122
In one embodiment, page table 122 is not persistent, but is a "live" structure. The page table may be reinitialized whenever a new application is restarted. In one embodiment, the page table 122 may include one or more of the following entries for a page of the active application virtual heap 110:
Type (User or System): The page type is used to select the write through policy used to backup the page into the persistent store 120 as well as the paging policy (which page to eject). As an example, System pages may be pinned in the in-memory heap 108 and may not be paged out.
Resident (TRUE or FALSE): In one embodiment, the resident bit may be used to maintain the heap residency state of the page, and may be TRUE if the page is resident in heap 108 or FALSE if the page is not resident in heap 108. In another embodiment, a value stored in a heap page ID field may be used to indicate if a page is resident in the heap. For instance, if a memory address is used to indicate the heap page ID, a NULL address or other invalid address may be used to indicate if the page is resident. In yet another embodiment, only pages that are currently cached in in-memory heap 108 may have an entry (row) in page table 122.
Dirty (TRUE or FALSE): Keeps track of any write or modification of the page in heap 108. TRUE if the page is dirty (has been modified or written to).
Flushing (TRUE or FALSE): Only valid for dirty pages. Indicates the page is in the checkpoint queue. If TRUE, the page is in the list of pages that are to be flushed to the virtual heap 110 in store 120.
Heap Page ID: Specifies the location of the page in the heap 108.
In one embodiment, as shown in FIG. 2, there may be one entry in the page table 122 for each page of the active application virtual heap 110. This embodiment may simplify the location of an entry for a page in the page table 122. In another embodiment, there may be one entry in the page table for each page currently cached in in-memory heap 108. This embodiment may reduce the size of the page table 122.
Read-only/static core virtual machine objects may be located into pinned and read-only system pages (objects may be tagged by the primary class loader). These classes are typically not loaded twice. Read/write core virtual machine objects may be located into user pages. In one embodiment, read/write core virtual machine objects may be "colored" as system pages. All user objects may be allocated in user pages.
In one embodiment, an application may establish one or more leases to system objects that may give the application access to resources external to the application such as system resources. In one embodiment, system pages in a heap may include system objects (code and/or data) that are currently leased. In one embodiment, the leases for the system objects may be contained in the application virtual heap 110.
In embodiments that allow the running of only one application at a time, each application virtual heap may contain its own set of system pages. In these embodiments, system pages are not shared among applications. In embodiments running more than one application at a time, system pages may be shared among applications. These embodiments may have a system segment in the persistent store 120 to checkpoint static and read-only pages that can safely be shared among applications.
FIG. 3--The States of a Page in a Virtual Persistent Heap
FIG. 3 is a state diagram illustrating the states of a page in a virtual persistent heap according to one embodiment of the invention. A page may be in one of the following states:
Empty: The page has been freed or has not been allocated.
Resident: The page has been newly allocated or the page has been paged in from the virtual heap 110 in persistent store 120 to the in-memory heap 108. No changes have been made to the page, or the latest changes have been flushed to the persistent store 120. The copy in the heap 108 is synchronized with the copy in the store 120.
Dirty: A write to the page has been performed and the page has not been written back to the persistent store 120. No request for checkpointing the page has been made.
Waiting to be checkpointed: The page is in a list of pages to be checkpointed to the store 120. The page is currently write locked, so no further write can occur until the page has been flushed.
Persistent: The page has been paged out. The page is no longer resident in the heap 108.
Page Fault
A page fault occurs when a reference is made to a page not resident in the in-memory heap 108. The page fault may induce a caching of the page from the virtual heap 110 in store 120 to the heap 108. When a page fault occurs, the following conditions may be encountered:
There is a free page available in the heap 108: The page may be brought into the heap 108 and the page table 122 entry updated.
There are no free pages in the heap 108: Before the page can be cached, room needs to be made in the heap. One or more resident pages need to be evicted from heap 108.
In one embodiment, when looking for candidate pages to be evicted, more than one page may be selected for eviction, since it is likely that another page may need to be evicted soon. In one embodiment, a free page threshold may be used to induce this behavior. In one embodiment, a standard LRU (Least Recently Used) method may be used to select pages for eviction (page out). In other embodiments, other methods, for example, Least Frequently Used (LFU), may be used to select pages for eviction.
If a page is dirty, the page may be checkpointed to the store 120, or alternatively a shadow copy is made, before being freed from the heap 108. In one embodiment, non-dirty pages may be evicted before dirty pages.
Page Checkpointing
As previously described, pages may be brought into the heap 108, modified and checkpointed to the virtual heap 110 in store 120 when they are evicted. In one embodiment, pages may be checkpointed when there are evicted. Alternatively, pages may be checkpointed when they remain in the heap 108. For instance, if checkpointing can be performed asynchronously (an executing thread does not have to be frozen), then pages may be checkpointed whenever convenient with minimum overhead to look for dirty pages.
In embodiments with a single threaded virtual machine environment using a simple bytecode count as a time sharing quantum for switching between threads, pages to be checkpointed may be searched for whenever a thread synchronization or a context switch occurs. On a thread context switch, dirty pages may be scanned for and placed in a checkpoint queue. In another embodiment, a mechanism to interrupt the running thread may be used to provide an opportunity to search for and checkpoint pages.
The flush bit in the Page Table 122 may be used to mark pages that are in the checkpoint queue. Further writes may be prevented to the page while the page is in the queue or in the process of being checkpointed. In one embodiment, the thread may be blocked until the page is written. In this embodiment, the checkpoint queue may be reordered to prioritize pages that have a blocked thread. In another embodiment, a copy of the page may be made to let the thread "go" on the shadow copy. A recently checkpointed page may not be put back into the checkpoint queue right away.
System pages may have a different checkpoint strategy than user pages. For instance, checkpointing system pages may freeze the entire virtual machine. System pages may therefore be more selectively checkpointed than user pages.
Store Checkpoints and Consistency
Having pages checkpointed individually may be insufficient to maintain the consistency of the virtual heap 110 in store 120. For instance, if two pages have changed in the heap 108, but only one page has been checkpointed, and the system crashes, the checkpointed virtual heap 110 in store 120 may end up in an inconsistent state. When the system restarts with an inconsistent store 120, the application may crash due to incorrect pointer locations. There is no guarantee that pages put in the checkpoint queue will be checkpointed to the store 120 (the system may crash at any time). In one embodiment, in or |
