(12) United States Patent
`Madany et al.
`
`I lllll llllllll Ill lllll lllll lllll lllll lllll 111111111111111111111111111111111
`US006493870Bl
`US 6,493,870 Bl
`*Dec. 10, 2002
`
`(10) Patent No.:
`(45) Date of Patent:
`
`(54) METHODS AND APPARATUS FOR
`PACKAGING A PROGRAM FOR REMOTE
`EXECUTION
`
`(75)
`
`Inventors: Peter W. Madany, Fremont, CA (US);
`Richard Tuck, San Francisco, CA
`(US); Nedim Fresko, San Francisco,
`CA (US); Hania Gajewska, Woodside,
`CA(US)
`
`(73) Assignee: Sun Microsystems, Inc., Palo Alto, CA
`(US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`This patent is subject to a terminal dis(cid:173)
`claimer.
`
`(21) Appl. No.: 09/044,900
`
`(22) Filed:
`
`Mar. 20, 1998
`
`Int. Cl.7 .................................................. G06F 9/44
`(51)
`(52) U.S. Cl. ....................... 717/165; 717/166; 717/107;
`709/332; 709/217; 709/219
`(58) Field of Search ................................. 709/328, 332,
`709/217, 219; 717/165, 166, 167, 107,
`106
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,519,866 A * 5/1996 Lawrence et al.
`.......... 717/162
`5,553,290 A * 9/1996 Calvert et al. .............. 717/121
`5,590,331 A * 12/1996 Lewis et al. ................ 717/114
`5,603,031 A
`2/1997 White et al.
`5,619,710 A * 4/1997 Travis et al. ................ 709/203
`5,630,066 A * 5/1997 Gosling ...................... 709/221
`5,666,501 A * 9/1997 Jones et al. ................. 345/748
`5,727,147 A * 3/1998 van Hoff .................... 709/200
`5,790,796 A * 8/1998 Sadowsky ................... 709/221
`
`5,835,777 A * 11/1998 Staelin ....................... 717/175
`5,845,119 A * 12/1998 Kozuka et al.
`............. 717/107
`5,901,314 A * 5/1999 Boehme et al. ............. 707/100
`5 ,911,071 A * 6/1999 Jordan ........................ 709 /315
`5,950,010 A * 9/1999 Hesse et al. ................ 717/178
`5,966,702 A * 10/1999 Fresko et al. .................. 707/1
`5,991,535 A * 11/1999 Fowlow et al. ............. 717/107
`6,029,207 A * 2/2000 Heninger .................... 709/331
`6,065,046 A * 5/2000 Feinberg et al. ............ 709/216
`6,083,277 A * 7/2000 Fowlow et al. ............. 345/769
`6,105,074 A * 8/2000 Yokote ....................... 709/328
`6,112,025 A * 8/2000 Mulchandani et al. ...... 709/331
`6,141,724 A * 10/2000 Butler et al. ................ 717/107
`6,199,196 Bl * 3/2001 Madany et al. ............. 717/165
`6,247,175 Bl * 6/2001 Ledford et al. ............. 717/107
`6,279,030 Bl * 8/2001 Britton et al.
`................ 707/10
`6,336,122 Bl * 1/2002 Lee et al.
`................... 707/204
`6,339,841 Bl * 1/2002 Merrick et al. ............. 717/166
`6,349,344 Bl * 2/2002 Sauntry et al.
`............. 709/332
`
`OTHER PUBLICATIONS
`
`IBM. "Java Dynamic Class Loader". Nov. 1, 1996.*
`Adele Goldberg and David Robson, "Smalltalk-80---The
`Language and
`its Implementation", Xerox Palo Alto
`Research Center, 1983 (reprinted with corrections, Jul.
`1985) pp. 1-720.
`
`(List continued on next page.)
`
`Primary Examiner-St. John Courtenay, III
`Assistant Examiner-Lewis A Bullock, Jr.
`(74) Attorney, Agent, or Firm-Finnegan, Henderson,
`Farabow, Garrett & Dunner, L.L.P.
`
`(57)
`
`ABSTRACT
`
`A task executing at a server receives a request to package
`program code for remote execution on a client, and deter(cid:173)
`mines the software components that already reside at the
`client. The task uses this information to formulate a set of
`instructions to another task that creates the package. The
`created package is transmitted to the client, and program
`execution begins.
`
`30 Claims, 8 Drawing Sheets
`
`(--~]RT )-
`
`INITIALIZECOMPONENTLIST
`WITH PROGRAM START
`POINT
`
`605
`
`IPR2017-00184
`UNIFIED EX1016
`
`

`
`US 6,493,870 Bl
`Page 2
`
`OIBER PUBLICATIONS
`
`Eric Jul, "Object Mobility in a Distributed Object-Oriented
`System", a Dissertation, University of Washington, 1989,
`pp. 1-154 (1 page Vita).
`Eric Jul, Henry Levy, Norman Hutchinson, and Andrew
`Black, "Fine-Grained Mobility in the Emerald System",
`University of Washington, ACM Transactions on Computer
`Systems, vol. 6, No. 1, Feb. 1988, pp. 109-133.
`
`Felix Samson Hsu, "Reimplementing Remote Procedure
`Calls", University of Washington, Thesis, Mar. 22, 1985, pp.
`1-106.
`
`Liquid Common LISP™, available at URL-http://harle(cid:173)
`quin.com/products/ads/lcl/lcl.html (Date printed Jun. 18,
`1998).
`
`* cited by examiner
`
`

`
`U.S. Patent
`
`Dec.10,2002
`
`Sheet 1 of 8
`
`US 6,493,870 Bl
`
`UJ
`__J
`u..
`Cf)
`Cf)
`<(
`__J
`(.)
`
`a:::
`UJ
`~
`UJ
`Cf)
`
`UJ
`Cl
`0
`(.)
`UJ
`I-
`>-
`ca
`
`,,.
`
`,,.
`
`/
`
`/
`
`/
`
`/
`
`LC")
`...-
`
`f\_~
`
`0
`c:o
`
`/
`
`I
`
`{
`
`I
`I
`I
`I
`I
`
`~
`•
`(!)
`Li:
`
`C>
`I.()
`...-
`
`I-
`:z:
`LU
`::::i
`(.)
`
`LC")
`I.()
`...-
`
`' ' ' ' '
`
`\
`
`\
`
`I-
`:z:
`UJ
`__J
`(.)
`
`........
`
`UJ
`Cl
`0
`(.)
`UJ
`I-
`>-
`ca
`
`I-
`:z:
`UJUJ
`~~
`-:z:
`1-o
`:z: a:::
`=::>_
`a::: >
`:z:
`UJ
`
`0
`...--
`...--
`
`LC")
`...-
`...-
`
`a:::
`0
`Cf)
`Cf)
`UJ
`(.)
`0
`a:::
`c....
`
`LC")
`C>
`...-
`
`C>
`C>
`..--
`
`

`
`U.S. Patent
`
`Dec.10,2002
`
`Sheet 2 of 8
`
`US 6,493,870 Bl
`
`(\I
`
`• Cl
`il:
`
`I-:z
`w
`Z<(
`0...--
`0...(.)
`:::2:
`0 u
`
`C>
`00
`N
`
`1-:z:
`w
`:z o...-
`0... c:o
`:::2:
`0
`(.)
`
`1-:z:
`w
`:z
`0
`...-(cid:173)
`a.. U
`:::2:
`0
`(.)
`
`C>
`r-(cid:173)
`N
`
`<(
`
`I-:z
`w
`:z:
`0 a..
`:::2:
`0
`(.)
`
`I\_ C>
`......-
`N
`
`c:o
`I-:z
`LU
`:z
`0 a..
`:::2:
`0
`(.)
`
`u
`I-:z
`LU
`:z
`0 a..
`:::2:
`0 u
`
`0
`I-:z
`LU
`:z
`0 a..
`:::2:
`0
`(.)
`
`[\_
`
`C>
`C>
`N
`
`

`
`USER
`ISSUES
`REQUEST
`TO
`EXECUTE
`PROGRAM
`
`DETERMINE
`WHAT
`COMPONENTS
`AND
`DEPENDENCIES
`ARE NEEDED
`
`310
`~
`
`320
`:£
`
`BEGIN
`EXECUTION
`
`340
`
`£
`
`/\.
`
`COMPONENT A
`REFERENCED
`
`END
`EXECUTION
`
`;\,
`
`360
`
`i
`
`/\,
`
`370
`
`1
`
`330
`LOAD ALL
`NEEDED
`COMPONENTS
`
`350
`COMPONENT A
`REFERENCED
`
`FIG. 3
`
`d •
`\JJ.
`•
`~
`~ ......
`~ = ......
`
`~
`~
`ri
`'"""' ~=
`N c c
`
`N
`
`'Jl =(cid:173)~
`~ .....
`
`~
`0 .....,
`00
`
`e
`
`rJ'J.
`O'I
`~
`~
`~
`""-l
`Q
`~
`lo-"
`
`

`
`U.S. Patent
`U.S. Patent
`
`Dec.10,2002
`Dec. 10, 2002
`
`00f04teehS
`Sheet 4 of 8
`
`US 6,493,870 Bl
`US 6,493,870 B1
`
`r--
`00
`-.::t"
`
`0 c.o
`..--
`
`N
`00
`-.::t"
`
`w c::::
`
`moézs
`moca
`~~ :zO
`
`_Jw
`
`5::
`Eozmz
`0
`~ w
`~
`
`c::::
`w
`~
`w
`en
`
`~
`en
`~
`w
`(.)
`~ c::::
`w
`I-:z
`
`itm_o<&Ez_
`
`-.::t"
`00
`-.:1'"
`
`1-:z
`:,m_d
`w _J
`
`(.)
`
`

`
`U.S. Patent
`
`Dec.10,2002
`
`Sheet 5 of 8
`
`US 6,493,870 Bl
`
`(
`
`START
`
`)
`
`RECEIVE REQUEST
`TO PACKAGE
`JAVA CODE
`
`v
`510
`
`IDENTIFY STARTING POINT v
`515
`OF PROGRAM
`
`IDENTIFY ANY AVAILABLE v
`520
`CLASS
`
`IDENTIFY ANY
`SUPPLEMENTAL CLASS
`
`v 530
`
`IDENTIFY PLACES TO LOOK .J 540
`FOR FILES
`
`SEND INSTRUCTION TO
`LINKAGE EDITOR
`
`.J 550
`
`RECEIVE OUTPUT FILE AND v 560
`SEND TO CLIENT
`
`,,
`END
`
`(
`
`)
`
`FIG. 5
`
`

`
`U.S. Patent
`
`Dec.10,2002
`
`Sheet 6 of 8
`
`US 6,493,870 Bl
`
`FIG. 6
`
`START
`
`INITIALIZE COMPONENT LIST
`WITH PROGRAM START
`POINT
`
`SELECT NEXT ITEM
`IN COMPONENT LIST
`
`NO
`
`LOCATE CLASS
`CONTAINING COMPONENT
`
`EXTRACT COMPONENT
`FROM CLASS AND ADD TO
`OUTPUT FILE
`
`655
`SEND OUTPUT
`FILE TO
`INTERFACE TASK
`
`(
`
`END
`
`)
`
`605
`
`610
`
`625
`
`630
`
`634
`ADD NECESSARY
`METHODS TO
`COMPONENT LIST
`
`ANALYZE COMPONENT
`FOR DEPENDENCIES
`
`635
`
`645
`ADD DEPENDENCIES
`TO COMPONENT LIST
`
`

`
`START
`
`)
`
`NO
`
`c END
`
`)
`
`NO
`
`~--·-·-~--------
`
`NO
`
`SEARCH EXTRACTED
`COMPONENT'S CLASS FOR
`NON-STATIC METHODS
`
`I r 725
`
`I
`
`YES
`
`NO
`
`c END
`
`)
`
`OVERRIDING METHOD TO I r 735
`BE ADDED TO
`COMPONENT LIST
`
`END
`
`CHECK SUBCLASSES FOR
`I OVERRIDING METHODS TO
`BE ADDED TO
`COMPONENT LIST
`
`720
`
`END
`
`FIG. 7
`
`d •
`\JJ.
`•
`~
`~ ......
`~ = ......
`
`~
`~
`ri
`'"""' ~=
`N c c
`
`N
`
`'Jl =-~
`~ .....
`-..J
`0 .....,
`00
`
`e
`
`rJ'J.
`O'I
`~
`~
`~
`""-l
`Q
`~
`lo-"
`
`

`
`U.S. Patent
`
`Dec. 10, 2002
`
`Sheet 8 of 8
`
`US 6,493,870 Bl
`
`810
`
`820
`
`830
`
`840
`
`START
`
`ISSUE REQUEST TO
`EXECUTE PROGRAM
`
`RECEIVE PACKAGED
`FILE FROM SERVER
`
`ADD PACKAGED
`COMPONENTS TO
`PREEXISTING
`COMPONENTS
`
`BEGIN PROGRAM
`EXECUTION
`
`END
`
`FIG. 8
`
`

`
`US 6,493,870 Bl
`
`1
`METHODS AND APPARATUS FOR
`PACKAGING A PROGRAM FOR REMOTE
`EXECUTION
`
`RELATED APPLICATIONS
`
`The following U.S. patent application is relied upon and
`is incorporated by reference in this application: U.S. patent
`application Ser. No. 09/044,904, entitled "Methods and
`Apparatus for Linking a Program for Remote Execution,"
`filed on the same date herewith.
`
`BACKGROUND OF THE INVENTION
`
`10
`
`2
`Specification," by Tim Lindholm and Frank Yellin, Addison
`Wesley, 1996. The Java VM acts as an interpreter between
`the bytecode and the particular computer system being used.
`By use of platform-independent bytecode and the Java VM,
`5 a program written in the Java programming language can be
`executed on any computer system. This is particularly useful
`in networks such as the Internet that interconnect heteroge(cid:173)
`neous computer systems.
`Before a Java program can be executed, certain requisite
`classes must be loaded into the memory of the computer
`executing the program. These classes may be loaded from
`the computer's disk, but are more commonly transferred
`across a network from a server. Customarily, these classes
`are loaded as late during the program's execution as pos(cid:173)
`sible; in other words, they are loaded on-demand, when first
`15 referenced during the program's execution. When such
`loading occurs, it is also customary to load an entire class
`whenever any part of that class is necessary.
`According to a conventional approach, when a user on a
`machine issues a request to execute the program resident on
`20 a remote server, the class file containing the main method is
`loaded from the server to the client across the network. This
`class file contains the program bytecode. The virtual
`machine then begins execution by invoking the main method
`of the program.
`Execution continues until the program references a com(cid:173)
`ponent, for example a component referred to as "F." In
`response to this reference, the entire class that contains
`component F is transferred from class files on the server to
`the client via the network. The referenced component F is
`used and execution then continues until another component,
`for example a component referred to as "G," is referenced.
`In response to this reference, the entire class containing
`component G is transferred from class files on the server to
`the client via the network. Execution then continues to
`35 completion. Once the execution has completed, the series of
`connections between the client and the server over the
`network may finally be terminated.
`This description demonstrates two significant disadvan(cid:173)
`tages with the conventional approach. First, it requires
`40 repeated connections between the client and the server
`throughout the course of program execution. Such a lengthy
`period during which connections must be made may be
`problematic for situations such as mobile computing. Sec(cid:173)
`ond, whenever a component is referenced, for example,
`45 component F, this approach requires that the entire class
`containing that referenced component be loaded from the
`server. If, however, only a few of the components within the
`class are ultimately used, the bandwidth required to transfer
`the unused components from the server to the client has been
`50 wasted. This is problematic in situations involving limited
`bandwidth, i.e., slow connection speeds or high-latency
`connections, between the client and the server.
`There is therefore a need for a system that alleviates these
`problems by packaging together only the necessary compo-
`55 nents of an entire program and delivering it to the client
`before execution begins. Prepackaging software for remote
`execution has been employed using other compiled com(cid:173)
`puter languages requiring machine compatibility, such as
`Cobol, C and Fortran. It has not, however, been employed
`60 using an object-oriented languages, such as the Java pro(cid:173)
`gramming language, which provide additional benefits, such
`as extracting necessary components from their parent
`classes.
`
`A Field of the Invention
`Embodiments of the invention generally relate to distrib(cid:173)
`uted computer systems and, more particularly, to methods
`and apparatus for packaging a computer program for remote
`execution.
`B. Description of the Related Art
`In today's society, the Internet has become an important
`medium for information exchange. Although the Internet is
`now very popular among the general public, it initially
`began as a system (or network) of interconnected computers
`used by government and academic researchers. An early
`problem of this network stemmed from the fact that the 25
`interconnected computers were not the same; they employed
`different hardware as well as different operating systems.
`Information exchange on such a heterogeneous network
`posed a communication problem. This problem was
`resolved through agreement on common standards, includ- 30
`ing protocols such as Transmission Control Protocol/
`Internet Protocol (TCP/IP) and HyperText Transfer Protocol
`(HTIP). These protocols enabled varied interconnected
`machines to share information in the form of static text or
`graphic documents.
`These protocols, however, represented only two steps in
`the evolution of the Internet. Although users can exchange
`information documents among varied computers connected
`to the Internet, they cannot exchange executable application
`programs written in conventional languages such as C or
`C++, which are designed to interface with a particular
`processor (e.g., the Intel Pentium processor) and/or a par(cid:173)
`ticular operating system (e.g., Windows 95 or DOS). This
`problem was solved with the advent of the Java TM program(cid:173)
`ming language and its related runtime system.
`The Java programming language is an object-oriented
`programming language that is described, for example, in a
`text entitled "The Java TM Tutorial" by Mary Campione and
`Kathy Walrath, Addison-Wesley, 1996. 1 Importantly, the
`Java programming language is an interpreted language that
`is platform-independent-that is, its utility is not limited to
`one particular computer system. Using the Java program(cid:173)
`ming language, a software developer writes programs in a
`form commonly called Java source code. When the devel(cid:173)
`oper completes authoring the program, he then compiles it
`with a Java compiler into an intermediate form called
`bytecode. Both the Java source code and the bytecode are
`platform-independent.
`1 Sun, Sun Microsystems, the Sun Logo, Java, the Java Virtual Machine, and
`the Java Runtime Environment are trademarks or registered trademarks of
`Sun Microsystems, Inc. in the United States and other countries.
`The compiled bytecode can then be executed on any
`computer system that employs a compatible runtime system
`that includes a virtual machine (VM), such as the Java
`Runtime Environment (JRE) that includes the Java Virtual 65
`Machine (JVM) and Java class libraries. The JVM is
`described in a text entitled "The Java Virtual Machine
`
`SUMMARY OF THE INVENTION
`In accordance with the present invention, a method for
`packaging a program component for execution in a distrib-
`
`

`
`US 6,493,870 Bl
`
`4
`
`3
`uted system comprises the steps of receiving a request to
`package a program for remote execution on a client, iden(cid:173)
`tifying any class referenced in the program that is available
`to the client, and providing an instruction to a linkage editor
`including at least one reference to the identified class.
`In accordance with the present invention, a computer(cid:173)
`readable medium contains instructions for packaging a pro(cid:173)
`gram component for execution in a distributed system by
`receiving a request to package a program for remote execu(cid:173)
`tion on a client, identifying any class referenced in the
`program that is available to the client, and providing an
`instruction to a linkage editor including at least one refer(cid:173)
`ence to the identified class.
`In accordance with the present invention, an apparatus for
`packaging a program component for execution in a distrib(cid:173)
`uted system comprises means for receiving a request to
`package a program for remote execution on a client, means
`for identifying any class referenced in the program that is
`available to the client, and means for providing an instruc(cid:173)
`tion to a linkage editor including at least one reference to the
`identified class.
`In accordance with the present invention, a system com(cid:173)
`prises a client, a server, and a network. The client has a
`processor, a memory, and a runtime environment including
`a virtual machine task. The server has a processor, a
`memory, an interface task, a linkage editor task, and a
`component file. The network interconnects the client and the
`server.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`DETAILED DESCRIPTION
`
`Reference will now be made in detail to an implementa(cid:173)
`tion of the present invention as illustrated in the accompa(cid:173)
`nying drawings. Wherever possible, the same reference
`numbers will be used throughout the drawings and the
`following description to refer to the same or like parts.
`
`A. Overview
`Systems and methods consistent with the present inven(cid:173)
`tion operate in a distributed computer system, typically
`having multiple clients and one or more servers. As one
`5 example, a client seeking to execute a program requests a
`server to package together the software needed to run the
`program. In formulating this request, the client may specify
`certain components that should be included in the package.
`A task executing at the server (the "interface task")
`10 receives this request, and determines the software compo(cid:173)
`nents that already reside at the client machine. The interface
`task uses this information to formulate a set of instructions
`to another task called the linkage editor. These instructions
`may include: the name of the program to be executed, the
`15 components that need not be packaged because they already
`reside at the client machine, and the names of any software
`components that the client machine may have specified to
`include in the package.
`The linkage editor receives this information and generates
`20 an output file that contains all software components that
`reside at the server and are necessary for program execution.
`This output file is generated by iteratively analyzing the
`program for references to other software components and
`extracting those components from their parent classes. The
`25 linkage editor sends the completed output file to the inter(cid:173)
`face task, which transmits it to the client that requested it,
`and program execution begins.
`B. Terminology
`For the sake of explanation, the detailed description
`30 below is based upon the Java programming language. For
`that reason, there follows a brief section defining terminol(cid:173)
`ogy as used hereinafter. One of skill in the art, however, will
`recognize that the same principles explained below apply to
`other programming languages.
`A Java application program consists of one or more class
`definitions, each of which has been compiled into its own
`class file that contains bytecode and other information. A
`"class," in turn, is a collection of data ("fields"), "methods"
`that operate on the data, and ancillary information. The
`40 ancillary information may include, for example, shared data
`structures, names of superclasses, and interfaces imple(cid:173)
`mented. As used herein, the term "component" refers to
`either a method or a field or both. An "object" is something
`created by using the blueprint provided by a class, i.e., it is
`45 an "instance" of the class. A Java application program must
`contain one class that defines the main method, which
`represents the point at which the Java interpreter starts
`executing the program. Such an application program may be
`executed by the Java interpreter, i.e. the Java VM.
`In contrast to a stand-alone application program, a Java
`applet does not contain a main method, and consequently
`cannot be executed directly by the Java interpreter. Instead,
`a Java applet is a class that is loaded by an already executing
`Java application such as a Web browser. The Java applica-
`55 tion invokes the various methods of the applet at the
`appropriate times.
`As used herein, the term "program," when used alone,
`may refer to either an application program, a Java applet, a
`process, or other software code. The term "task" may refer
`60 to a program executing on a computer processor. The term
`"package" may include components, ancillary information,
`or other data required for program execution.
`For the sake of simplicity, the examples contained herein
`assume that an application program is being executed. Those
`65 of skill in the art, however, will recognize that the claimed
`invention may encompass execution of an applet and other
`software code.
`
`50
`
`The accompanying drawings, which are incorporated in
`and constitute a part of this specification, illustrate an
`embodiment of the invention and, together with the
`description, serve to explain the advantages and principles 35
`of the invention. In the drawings,
`FIG. 1 is a block diagram of a typical client-server
`configuration used to explain remote program execution
`using a runtime environment that includes a virtual machine;
`FIG. 2 is a block diagram depicting a typical executable
`object-oriented program along with its referenced compo(cid:173)
`nents and their dependencies;
`FIG. 3 is a timeline used to explain the timing of linking
`and execution consistent with the present invention;
`FIG. 4 is a block diagram depicting typical interface and
`linkage editor tasks in relation to a server and a client;
`FIG. 5 is a flow diagram of the steps performed by an
`interface task in a packaging process consistent with the
`present invention;
`FIG. 6 is a flow diagram of the steps performed by the
`linkage editor in packaging an output file, in an embodiment
`consistent with the present invention; and
`FIG. 7 is a flow diagram of steps performed to add
`necessary methods, in an embodiment consistent with the
`present invention; and
`FIG. 8 is a flow diagram of the steps performed by the
`client to execute a program, in an embodiment consistent
`with the present invention.
`
`

`
`US 6,493,870 Bl
`
`5
`
`C. Architecture
`FIG. 1 shows the use of the Java programming language
`in a distributed computing system. The system consists of
`one or more servers such as server 160 and one or more
`clients, such as clients 100 and 155, interconnected by a
`network 150. The software developer creates a program
`using the Java programming language and compiles it into
`bytecode 115 that is stored on server 160. Typically, server
`160 also contains numerous class files 125 that are employed
`by Java programs. When a client 100 wishes to execute a
`Java program, it issues a request to server 160. In response,
`server 160 transmits the bytecode version of program 115 to
`client 100. At client 100, bytecode 115 executes on a runtime
`environment 110, which interprets between bytecode 115
`and a processor residing on client 100.
`FIG. 2 is an exemplary block diagram showing compo(cid:173)
`nent references within a typical executable program. In this
`example, a program 200 references four components, shown
`here as component A 210, component B 220, component C
`230, and component D 240. These referenced components, 20
`in turn, reference other components. For example, compo(cid:173)
`nent B 220 references component Bl 250. Similarly, com(cid:173)
`ponent C 230 references component A 210 and component
`Cl 270. In turn, component Cl 270 references component
`ClA 280. Such a reference by one component of another 25
`component is commonly referred to as a dependency. Each
`referenced component must be loaded because it may be
`used during program execution.
`D. Timeline
`FIG. 3 is a timeline used to explain the timing of linking 30
`and execution consistent with the present invention. The
`process begins when a user issues a request to execute a
`program (point 310) on client 100. In response, server 160
`determines what components and dependencies are needed
`for the program to execute (point 320). Each of these needed 35
`components, along with ancillary class information, is then
`transferred from server 160 to client 100 via network 150
`(point 330). At this point, all components and classes
`required for program execution have been transferred from
`server 160 to client 100 and, therefore, the connection 40
`between the two may be terminated.
`Program execution then begins (point 340), and compo(cid:173)
`nent A 210 is referenced (point 350). Because that compo(cid:173)
`nent has already been loaded onto client 100 (at point 330),
`however, there need be no separate transfer of that compo- 45
`nent from server 160 to client 100. Similarly, when compo(cid:173)
`nent B 220 is referenced (point 360), it need not be trans(cid:173)
`ferred because it has already been transferred from server
`160 to client 100. Execution therefore proceeds to comple(cid:173)
`tion (point 370) uninterrupted.
`FIG. 3 demonstrates that a process consistent with the
`present invention requires client 100 to remain connected to
`server 160 only until program loading ends (from point 300
`to point 330). Once the necessary components and ancillary
`class information have been loaded (at point 330), client 100 55
`may disconnect from server 160. Then, for the entire dura(cid:173)
`tion of program execution (point 340 to point 370), client
`100 and server 160 need not be connected. Moreover, server
`160 only transfers to client 100 those components and the
`ancillary class information that are essential to program 60
`execution (point 330). By eliminating the transfer of unused
`components, bandwidth is used more efficiently.
`E. Architecture of Interface Task and Linkage Editor
`FIG. 4 is a block diagram depicting an interface task and
`a linkage editor in relation to a server and a client. Client 100 65
`is interconnected to server 160 via network 150. Server 160
`contains a memory 482, which may contain Java class files.
`
`6
`Examples of memory 482 include random access memory
`(RAM), read only memory (ROM), a hard disk drive, or a
`compact disc based ROM (CD-ROM). Executing on server
`160 are two tasks: an interface task 484, and a linkage editor
`5 487. A request is issued to server 160 to package the
`necessary Java code to execute a program on client 100. At
`server 160, this request is received by interface task 484.
`Interface task 484, in turn, formulates a set of packaging
`instructions and sends them to linkage editor 487. Linkage
`10 editor 487 creates a package containing any components
`necessary for execution that reside on server 160, and sends
`the package to interface task 484. Interface task 484 receives
`this package and sends it to client 100, which uses the
`package to execute the program.
`15 F. Interface Task
`FIG. 5 is a flow diagram of the steps performed by an
`interface task in a packaging process consistent with the
`present invention. At the beginning of the process, interface
`task 484 (executing on server 160) receives a request to
`package a Java program for execution on a named client, for
`example client 100 (step 510). The Java program is typically
`specified as a collection of Java classes and components.
`The location of some class files is predefined. The location
`of other, necessary classes is included in the request to
`package the Java program.
`In response to this request, interface task 484 formulates
`a set of instructions for a linkage editor. As part of these
`instructions, the interface task notifies linkage editor 487 of
`the starting point of the program (step 515). This gives
`linkage editor 487 a starting point for determining which
`components are needed.
`Interface task 484 also notifies linkage editor 487 of any
`class that is already present on client 100 (step 520). By
`providing this information, the interface task avoids unnec(cid:173)
`essary packaging: linkage editor 487 need not package
`components that already exist on client 100. This conserves
`bandwidth usage by minimizing the size of the output file.
`This information may be provided to the interface task as
`part of the request to package components (step 510).
`Alternatively, this information may be stored within
`memory 482 of server 160, from having been previously
`provided. For this step to operate correctly, the classes
`already present on client 100 must be consistent with those
`on server 160.
`Interface task 484 also notifies linkage editor 487 of any
`supplemental component that should be added to the pro(cid:173)
`gram package (step 530). This may be necessary for
`example, if a component has been excluded from the linkage
`step because the class containing that component already
`50 exists on client 100; that excluded component, however,
`may reference other components that are not available on
`client 100, and therefore may be need to be added to the
`package by linkage editor 487. In addition to components
`that are excluded because their class already exists on client
`100, there may also be some dependencies that cannot be
`discovered programmatically. Interface task 484 typically is
`informed (at step 510) of any supplemental components as
`part of the request to package components.
`For example, the method quicksort may be excluded from
`the linkage step because the class containing that method,
`sun.misc.Sort, is already loaded on client 100. When the
`method quicksort is invoked, one of its parameters is an
`object having the method doCompare. Quicksort will invoke
`doCompare, which may not already be loaded on client 100.
`Accordingly, interface task 484 must notify linkage editor
`487 that the method doCompare must be loaded as a
`supplemental component.
`
`

`
`US 6,493,870 Bl
`
`5
`
`7
`Interface task 484 also notifies linkage editor 487 of a list
`of places to look for the required Java class files (step 540).
`Interface task 484 sends these instructions to linkage editor
`487 (step 550), which generates an output file as described
`below in reference to FIG. 5. Interface task 484 receives the
`output file and sends it to client 100 (step 560), and the
`process ends.
`G. Linkage Editor
`FIG. 6 is a detailed flow diagram, consistent with the
`present invention, of the steps performed by linkage editor
`487 in packaging an output file. For explanatory purposes,
`the following description of the flow is based upon the
`example in FIG. 2.
`In the beginning of the process, linkage editor 487
`(typically executing on server 160) receives a set of instruc- 15
`tions from interface task 484. Linkage editor 487 then
`creates and initializes a list with the starting point of the
`program to be executed (step 605). This list, referred to as
`the "component list," contains a reference to each necessary
`component that must be loaded by linkage editor 487.
`Linkage editor 487 then selects the next item in the
`component list, which initially will be the main method (step
`610). Linkage editor 487 checks to see if the selected
`component is on the list of items to exclude from the linkage
`step (step 615). The component may be on the list of items
`to exclude because, for example, the component is more
`readily available from another source, such as client 100 or
`another server. Because the main method will not be on the
`list of things to exclude, linkage editor 487 checks to
`determine if the selected component has previously been
`loaded in the linkage process (step 620). Because the main
`method will not have been previously loaded, linkage editor
`487 then locates the class file that contains the component to
`be loaded, using the list of file locations provided by the
`server in its instructions to linkage editor 487 (step 625).
`Linkage editor 487 reads that class file, extracts any ancil(cid:173)
`lary information associated with that class file, extracts the
`selected component from the class file, and adds the
`extracted ancillary information and component to an output
`file (step 630). Note that by doing so, linkage editor 487 only
`extracts necessary components and ancillary information,
`rather than loading the entire class.
`After loading the extracted component, linkage editor 487
`checks for overridden methods (step 632). This step is
`further described in reference to FIG. 7, below. Next, linkage
`editor 487 analyzes the extracted component to determine if
`it references other components (step 635). In other words,
`linkage editor 487 analyzes the extracted component for
`dependencies. In this ex