Method and apparatus for managing independent asynchronous I/O operations within a virtual machine

BACKGROUND

1. Field of the Invention

The present invention relates to techniques for managing Input/Output (I/O) operations within a computer system. More specifically, the present invention relates to a method and an apparatus for performing independent asynchronous I/O operations within a platform-independent virtual machine within a computer system.

2. Related Art

The exponential growth of the Internet has in part been fueled by the development of computer languages, such as the JAVA™ programming language distributed by Sun Microsystems, Inc. of Santa Clara, Calif. The JAVA programming language allows an application to be compiled into a module containing platform-independent byte codes, which can be distributed across a network of many different computer systems. Any computer system possessing a corresponding platform-independent virtual machine, such as the JAVA virtual machine, is then able to execute the byte codes. In this way, a single form of an application can be easily distributed to and executed by a large number of different computing platforms.

These platform-independent virtual machines are presently being incorporated into smaller pocket-sized computing devices, such as personal organizers. Unfortunately, memory space is severely constrained within these pocket-sized computing devices. Hence, system designers must use as little memory space as possible in implementing virtual machines within these pocket-sized computing devices.

Platform independent virtual machines typically provide run-time support for multiple “language threads” (L-threads). For example the JAVA virtual machine supports the execution of multiple JAVA threads. In larger computer systems it is practical to implement L-threads using a one-to-one mapping with underlying operating system threads (OS-threads). However, memory-constrained computing devices often lack the virtual memory capabilities to make this possible. Furthermore, a one-to-one mapping requires a large number of OS-threads, which can consume a large amount of memory space.

For this reason, in memory-constrained systems L-threads are often implemented as co-routines that share a single OS-thread. Unfortunately, if multiple L-threads share a single OS-thread, implementing I/O operations can be a problem because an I/O operation can potentially cause the single OS-thread to block, even if other L-threads are waiting to perform useful work. To remedy this problem, some systems pair an L-thread with an extra OS-thread during the time the L-thread is performing an I/O operation. In way, the extra OS-thread can perform the I/O operation on behalf of the L-thread, and the L-thread is de-scheduled until the OS-thread completes the I/O operation. After the I/O operation completes, the OS-thread is returned to the shared pool, which allows the OS-thread to be reused.

In order to perform the I/O operation, the OS-thread typically manipulates parameters for the I/O operation located in an object heap within the virtual machine. This creates problems because the object heap is typically subject to periodic garbage collection operations, which can potentially move the parameters within the object heap. Hence, the OS-thread must acquire a garbage collection (GC) lock while accessing the object heap to ensure that garbage collection operations do not cause the OS-thread to access the wrong locations in the object heap. Moreover, allowing the OS-thread to access the object heap generally reduces system reliability because the OS-thread can potentially corrupt the object heap.

Hence, what is needed is a method and an apparatus for performing I/O operations within a platform-independent virtual machine without the problems listed above.

SUMMARY

One embodiment of the present invention provides a system that facilitates performing independent asynchronous I/O operations within a platform-independent virtual machine. Upon encountering an I/O operation, a language thread within the system marshals parameters for the I/O operation into a parameter space located outside of an object heap of the platform-independent virtual machine. Next, the language thread causes an associated operating system thread (OS-thread) to perform the I/O operation, wherein the OS-thread accesses the parameters from the parameter space. In this way, the OS-thread does not access the parameters in the object heap directly while performing the I/O operation.

In a variation on this embodiment, after the OS-thread finishes the I/O operation, the language thread unmarshals parameters from the parameter space and then returns from the I/O operation.

In a variation on this embodiment, marshalling the parameters involves marshalling the parameters from the object heap, and unmarshalling the parameters involves unmarshalling the parameters into the object heap.

In a variation on this embodiment, the platform-independent virtual machine operates in accordance with a hybrid thread model in which language threads that are not performing I/O operations execute as co-routines on a single OS-thread, and wherein language threads performing I/O operations are associated with dedicated OS-threads that perform the I/O operations.

In a variation on this embodiment, the parameter space is associated with the OS-thread and is allocated from a global pool of memory located outside of the object heap.

In a variation on this embodiment, the parameter space is associated with the OS-thread and is allocated in an unused end of the object heap.

In a variation on this embodiment, the parameter space is allocated in stack space associated with the OS-thread.

BRIEF DESCRIPTION OF THE FIGURES

<figref idref="DRAWINGS">FIG. 1</figref> illustrates a computing device in accordance with an embodiment of the present invention.

<figref idref="DRAWINGS">FIG. 2</figref> illustrates how parameters are marshaled and unmarshalled in accordance with an embodiment of the present invention.

<figref idref="DRAWINGS">FIG. 3</figref> presents a flow chart illustrating actions performed by a language thread during an I/O operation in accordance with an embodiment of the present invention.

DETAILED DESCRIPTION

The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.

The data structures and code described in this detailed description are typically stored on a computer readable storage medium, which may be any device or medium that can store code and/or data for use by a computer system. This includes, but is not limited to, magnetic and optical storage devices such as disk drives, magnetic tape, CDs (compact discs) and DVDs (digital versatile discs or digital video discs), and computer instruction signals embodied in a transmission medium (with or without a carrier wave upon which the signals are modulated). For example, the transmission medium may include a communications network, such as the Internet.

Computing Device

<figref idref="DRAWINGS">FIG. 1</figref> illustrates a computing device <b>110</b> coupled to a development system <b>106</b> in accordance with an embodiment of the present invention. Development system <b>106</b> can generally include any type of computer system, including, but not limited to, a computer system based on a microprocessor, a mainframe computer, a digital signal processor, a portable computing device, a personal organizer, a device controller, and a computational engine within an appliance. Development system <b>106</b> contains development unit <b>108</b>, which includes programming tools for developing platform-independent applications.

Development system <b>106</b> is coupled to computing device <b>110</b> through a communication link <b>112</b>. Computing device <b>110</b> can include any type of computing device or system including, but not limited to, a mainframe computer system, a server computer system, a personal computer, a workstation, a laptop computer system, a pocket-sized computer system, a personal organizer and a device controller. Computing device <b>110</b> can also include a computing device that is embedded within another device, such as a pager, a cellular telephone, a television, an automobile, or an appliance.

Communication link <b>112</b> can include any type of permanent or temporary communication channel that may be used to transfer data from development system <b>106</b> to computing device <b>110</b>. This can include, but is not limited to, a computer network such as an Ethernet, a wireless communication network or a telephone line.

Computing device <b>110</b> includes data store <b>114</b>, for storing code and data, as well as a virtual machine <b>116</b> for processing platform-independent programs retrieved from data store <b>114</b>.

During the development process, a class file <b>118</b> is created within development unit <b>108</b>. Class file <b>118</b> contains components of a platform-independent program to be executed in computing device <b>110</b>. For example, class file <b>118</b> may include methods and fields associated with an object-oriented class. Next, class file <b>118</b> is transferred from development unit <b>108</b> through communication link <b>112</b>, into data store <b>114</b> within computing device <b>110</b>. This allows virtual machine <b>116</b> to execute an application that accesses components within class file <b>118</b>. Note that virtual machine <b>116</b> can generally include any type of virtual machine that is capable of executing platform-independent code, such as the JAVA VIRTUAL MACHINE™ developed by SUN Microsystems, Inc. of Palo Alto Calif.

Virtual machine <b>116</b> is implemented on top of an underlying operating system <b>170</b>. More specifically, virtual machine <b>116</b> is implemented using a number of native OS-threads <b>160</b> within operating system <b>170</b>, which are represented by the letters “OS”. Note that operating system <b>170</b> can generally include any type of operating system for a computing device that supports multiple native OS-threads.

Virtual machine <b>116</b> includes an interpreter <b>120</b>, which interprets platform-independent code from data store <b>114</b> during program execution. Virtual machine <b>116</b> can alternatively execute compiled code. This compiled code is produced by compiling platform-independent code into native code for computing device <b>110</b>.

Virtual machine <b>116</b> also includes object heap <b>122</b> for storing objects that are manipulated by code executing on virtual machine <b>116</b>.

Virtual machine <b>116</b> also supports multiple language threads (L-threads), which are represented by the letter “L”, as well as multiple pool threads, which are represented by the letter “P”. These pool threads can be implemented as objects that provide handles for interacting with associated native OS-threads (represented by the letters “OS”) within operating system <b>170</b>. (In <figref idref="DRAWINGS">FIG. 1</figref>, pool threads are connected by solid lines to their associated native threads.)

As is illustrated in <figref idref="DRAWINGS">FIG. 1</figref>, some of the L-threads are active L-threads <b>130</b>, which execute as co-routines on a single OS-thread <b>161</b>. Other L-threads are I/O threads <b>140</b>, which are associated with on-going I/O operations. These L-threads are paired with corresponding pool threads, which act as handles for associated OS-threads that perform the I/O operations. There are also a number of unused pool threads <b>150</b>, which are not associated with L-threads.

When one of the active L-threads <b>130</b> encounters an I/O operation, the L-thread is paired with a pool thread from the unused pool threads <b>150</b>. This pool thread acts as a handle for a native OS-thread within the underlying operating system <b>170</b>, which performs the I/O operation. At this point, the L-thread is no longer one of the active threads, but instead becomes one of the I/O threads <b>140</b>. After the I/O operation is complete, the L-thread returns to being one of the active L-threads <b>130</b> and the pool thread returns to being one of the unused pool threads <b>150</b>.

Note that the term “I/O operation” as used in this specification and the appended claims refers to any type of operation with a long and/or unpredictable duration, which may cause a thread to block. Hence, the term “I/O operation” is not meant to be limited to only input of output operations. For example, an I/O operation can include a long computational operation, which is sent to a co-processor, and which may not return from the co-processor for a long period of time.

I/O Operation Parameters

<figref idref="DRAWINGS">FIG. 2</figref> illustrates how parameters are marshaled and unmarshalled in accordance with an embodiment of the present invention. When a language thread (L-thread) <b>201</b> encounters an I/O operation, L-thread <b>201</b> marshals one or more parameters for the I/O operation into parameter space <b>203</b>, which is associated with a native OS-thread <b>202</b>. For example, in <figref idref="DRAWINGS">FIG. 2</figref>, a value referenced by a pointer x in object heap <b>122</b> is marshaled into a field <b>205</b> in parameter space <b>203</b>.

When the I/O operation is complete, one or more parameters from the I/O operation are unmarshalled from parameter space <b>203</b>. For example, in <figref idref="DRAWINGS">FIG. 2</figref>, a value from a field <b>206</b> in parameter space <b>203</b> is unmarshalled into a location in object heap <b>122</b> referenced by a pointer y.

I/O Operation

<figref idref="DRAWINGS">FIG. 3</figref> presents a flow chart illustrating actions performed by a language thread (L-thread) <b>201</b> during an I/O operation in accordance with an embodiment of the present invention. Upon encountering an I/O operation, L-thread <b>201</b> calls the function getParameter, which is implemented by OS-thread <b>202</b>. The function getParameter returns a pointer to a parameter space <b>203</b> that contains parameters for the I/O operation (step <b>302</b>).

L-thread <b>201</b> then determines if the returned parameter has a NULL value (step <b>304</b>). If so, no parameter space has been allocated yet. In this case, L-thread <b>201</b> calls the function allocParameter, which is implemented by OS-thread <b>202</b>. The function allocParameter returns a pointer to a parameter space <b>203</b> associated with OS-thread <b>202</b> (step <b>306</b>).

In one embodiment of the present invention, parameter space <b>203</b> is a fixed-position memory block that is allocated for the purpose of marshalling data into and unmarshalling result data out of. This memory block can come from a number of sources. (1) It can be allocated from a global pool of memory located outside of the object heap. (2) It can be allocated in an unused end of the object heap. Or, (3) it can be allocated in stack space belonging to the associated native OS-thread.

Next, L-thread <b>201</b> calls the function marshal(in,p) to marshal input parameters from object heap <b>122</b> into parameter space <b>203</b> (step <b>308</b>). Note that this marshalling function can involve a memory copy operation. L-thread <b>201</b> then calls the function setFunction(f), which prepares the I/O function f for execution by the associated OS-thread <b>202</b> (step <b>310</b>). Note that the pointer p can be passed as a global parameter to OS-thread <b>202</b>.

L-thread <b>201</b> then blocks (step <b>312</b>) and returns (step <b>314</b>). This causes L-thread <b>201</b> to go to sleep and also causes the associated OS-thread <b>202</b> to perform the I/O operation.

Note that the associated OS-thread <b>202</b> continually executes a loop, such as the loop below.

<tables id="TABLE-US-00001" num="00001"><table frame="none" colsep="0" rowsep="0"><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="63pt" align="left" /><colspec colname="1" colwidth="154pt" align="left" /><thead><row>&lt;entry /&gt;<entry namest="offset" nameend="1" align="center" rowsep="1" /></row></thead><tbody valign="top"><row>&lt;entry /&gt;<entry>declare parameterSpace[];</entry></row><row>&lt;entry /&gt;<entry>loop {</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="77pt" align="left" /><colspec colname="1" colwidth="140pt" align="left" /><tbody valign="top"><row>&lt;entry /&gt;<entry>wait(execEvent);</entry></row><row>&lt;entry /&gt;<entry>(*f)(p);</entry></row></tbody></tgroup><tgroup align="left" colsep="0" rowsep="0" cols="2"><colspec colname="offset" colwidth="63pt" align="left" /><colspec colname="1" colwidth="154pt" align="left" /><tbody valign="top"><row>&lt;entry /&gt;<entry>}</entry></row><row>&lt;entry /&gt;<entry namest="offset" nameend="1" align="center" rowsep="1" /></row></tbody></tgroup></table></tables>&lt;br /&gt; This loop causes OS-thread <b>202</b> to wait for an execEvent, such as L-thread <b>201</b> blocking in step <b>312</b>. OS-thread <b>202</b> then executes the I/O function f with a pointers, which points to parameter space <b>203</b>.

Note that before entering the loop above, OS-thread <b>202</b> declares a local variable parameterSpace with a preset amount of memory to implement parameter space <b>203</b>. Note that this local variable stays in tact during: the marshalling process, the function execution, and the unmarshalling process. A pointer to this local variable can easily be tunneled to the L-thread <b>201</b> through a global variable since all setup can occur while there is only one L-thread running. In this way, no other concurrent L-threads can see the global variable.

When the I/O function f returns, L-thread <b>201</b> returns to step <b>302</b> and calls “getParameter” again. This time, in step <b>304</b>, the pointer p is not NULL. Hence, L-thread <b>201</b> calls the function unmarshal(p,out) to unmarshal output parameters from parameter space <b>203</b> into object heap <b>122</b> (step <b>316</b>). Note that this unmarshalling function can involve a memory copy operation. L-thread <b>201</b> then returns (step <b>314</b>).

Instead of using OS-thread <b>202</b> to perform the marshalling and unmarshalling operations, the present invention requires L-thread <b>201</b> to perform these operations. Since the L-threads in virtual machine <b>116</b> are implemented as co-routines in a conceptually single-threaded environment, garbage collection operations on object heap <b>122</b> can be controlled relative to the L-threads. This means that L-thread <b>201</b> does not have to acquire a GC lock before accessing parameters in object heap <b>122</b>.

Because the above-described technique does not allow OS-thread <b>202</b> to access object heap <b>122</b>, OS-thread <b>202</b> does not have to worry about obtaining locks to protect against objects being moved within object heap <b>122</b> by the garbage collection process. Moreover, the present invention is more robust than prior systems because OS-threads do not access object heap <b>122</b>.

Furthermore, since parameter space <b>203</b> is allocated from space associated with OS-thread <b>202</b>, there is less fragmentation of memory within virtual machine <b>116</b>.

The foregoing descriptions of embodiments of the present invention have been presented for purposes of illustration and description only. They are not intended to be exhaustive or to limit the present invention to the forms disclosed. Accordingly, many modifications and variations will be apparent to practitioners skilled in the art. Additionally, the above disclosure is not intended to limit the present invention. The scope of the present invention is defined by the appended claims.