(12) United States Patent
`Wollrath et al.
`
`USOO6237024B1
`(10) Patent No.:
`US 6,237,024 B1
`(45) Date of Patent:
`May 22, 2001
`
`(54)
`
`(75)
`
`(73)
`
`(*)
`
`(21)
`(22)
`
`(51)
`(52)
`(58)
`
`(56)
`
`4,491.946
`4,713,806
`4,809,160
`4,823,122
`4,939,638
`4,956,773
`5,088,036
`5,109,486
`5,187,787
`5,218,699
`5,257,369
`5,293,614
`5,297.283
`5,311,591
`
`METHOD AND APPARATUS FOR THE
`SUSPENSION AND CONTINUATION OF
`REMOTE PROCESSES
`
`Inventors: Ann M. Wollrath, Groton; Kenneth C.
`R. C. Arnold, Lexington, both of MA
`(US)
`Assignee: Sun Microsystem, Inc., Palo Alto, CA
`(US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`Appl. No.: 09/044,917
`Filed:
`Mar 20, 1998
`
`Notice:
`
`Int. Cl. ............................................... G06F 13/38
`
`U.S. Cl. ............................................. 709/203; 709/224
`
`Field of Search ..................................... 709/238, 159,
`709/201, 227, 213, 220, 203, 224; 395/608,
`700, 650, 2.42, 610; 370/468, 58; 707/103,
`4; 364/559; 713/201; 379/201; 703/23
`References Cited
`U.S. PATENT DOCUMENTS
`1/1985 Kryskow, Jr. et al..
`12/1987 Oberlander et al. ................... 370/58
`2/1989 Mahon et al. .
`4/1989 Mann et al. .
`7/1990 Stephenson et al..
`9/1990 Saito et al. .
`2/1992 Ellis et al. ........................... 395/425
`4/1992 Seymour.
`2/1993 Skeen et al. ......................... 395/600
`6/1993 Brandle et al. .
`10/1993 Skeen et al. ......................... 395/650
`3/1994 Ferguson et al. .................... 395/600
`3/1994 Kelly, Jr. et al..
`5/1994 Fischer.
`(List continued on next page.)
`
`FOREIGN PATENT DOCUMENTS
`0300 516 A2
`1/1989 (EP).
`0.351536 A3
`1/1990 (EP).
`0384339 A3
`2/1990 (EP). ................................... (WO).
`(List continued on next page.)
`OTHER PUBLICATIONS
`Howard et al., Scale and Performance in a Distributed File
`System, ACM Transactions on Computer Systems, vol. 6,
`No. 1, Feb. 1988, pp. 51-81.
`Cardelli, Obliq, Alightweight language for network objects,
`Nov. 5, 1993, pp. 1–37.
`Dijkstra, Self-stabilizing Systems in Spite of Distributed
`Control, Communications of the ACM, Vol. 17, No. 11, Nov.
`1974, pp. 643–644.
`(List continued on next page.)
`Primary Examiner Le Hien Luu
`Assistant Examiner Thong Vu
`(74) Attorney, Agent, or Firm-Finnegan, Henderson,
`Farabow, Garrett & Dunner, L.L.P.
`(57)
`ABSTRACT
`A method and apparatus is provided for enabling blocked
`remote methods to relinquish threads and other resources to
`other methods on a Server System. In a distributed computing
`environment, remote methods are allocated numerous net
`work resources but are blocked while they wait for
`operations, Such as a write operation from another process,
`to complete. When enough remote methods are blocked,
`threads and other network resources may run out. Client
`Systems requesting Server Services may experience slower
`response times. This method and System provides a tech
`nique for remote methods to relinquish network resources,
`Such as threads, for other methods to use while the methods
`are blocked. Once the conditions causing the remote meth
`ods to block is resolved, the remote methods continue
`execution. This technique enables high Volume client-server
`transaction Systems to utilize threads and other resources in
`a distributed computing environment more efficiently.
`
`39 Claims, 7 Drawing Sheets
`
`324
`
`322
`
`REMOTEMETHORESOURCES
`402
`
`REMOTEMETHODRESOURCE
`MANAGER
`410
`412
`
`48
`
`THREADPOOL
`-
`THREADS
`AVALABLE
`HREADS
`N-USE
`
`REMOTE
`PROCEURECALL
`(RPC) STATE
`
`SUSPEND
`METHOD
`
`CONTINUE
`METHOD
`
`44
`
`
`
`
`
`
`
`STATESORE
`
`RPCSTATE
`EXECUTIVESTAT
`8
`
`
`
`38
`
`ReMOE OBJECTA 4
`16
`
`REMOTEMETHOD
`
`EXECUTION
`STATE
`
`Ex.1026
`APPLE INC. / Page 1 of 22
`
`

`

`US 6,237,024 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`8/1994 Lubkin et al. ....................... 395/700
`5,339,435
`1/1995 Wold et al..
`5,386,568
`2/1995 Frey et al..
`5,390,328
`6/1995 Jalili et al..
`5,423,042
`8/1995 Jacobson et al. .................... 395/650
`5,440,744
`9/1995 Kiri et al..
`5,448,740
`10/1995 Giovaag.
`5,455,952
`11/1995 Risch.
`5,471,629
`12/1995 Stanford et al. .................... 395/2.42
`5,475,792
`12/1995 Waldo et al..
`5,475,817
`1/1996 Serlet et al..
`5,481,721
`4/1996 Dev et al..
`5,504,921
`4/1996 Hill et al..
`5,511,197
`6/1996 Robinson et al..
`5,524,244
`9/1996 Parrish et al..
`5,553,282
`9/1996 Premerlani et al..
`5,555,367
`9/1996 Skeen et al. ......................... 395/650
`5,557,798
`9/1996 Nilsen et al. ........................ 395/600
`5,560,003
`10/1996 Blandy et al. .................. 395/497.01
`5,561,785
`11/1996 Scalzi et al..
`5,577,231
`2/1997 White et al. ......................... 395/683
`5,603,031
`4/1997 Yamada et al. .
`5,617,537
`5,628,005 * 5/1997 Hurvig ................................. 395/608
`5,640,564
`6/1997 Hamilton et al. .
`5,652,888
`7/1997 Burgess.
`5,655,148
`8/1997 Richman et al. .................... 395/828
`5,659.751
`8/1997 Heninger ........
`... 395/685
`5,671,225
`9/1997 Hooper et al. .
`... 370/468
`5,675,796 * 10/1997 Hodges et al........................ 709/159
`5,680,573
`10/1997 Rubin et al..
`5,680,617
`10/1997 Gough et al..
`5,684.955
`11/1997 Meyer et al..
`5,689,709
`11/1997 Corbett et al..
`5,699,531
`12/1997 Skeen et al. .
`5,706.435
`1/1998 Barbar et al. .
`5,706,502 * 1/1998 Foley et al........................... 395/610
`5,724,588
`3/1998 Hill et al. .
`5,727,145
`3/1998 Nessett et al. .
`5,737,607
`4/1998 Hamilton et al. .
`5,745,678
`4/1998 Herzberg et al..
`5,745,695
`4/1998 Gilchrist et al. ..................... 709/227
`5,745,703 * 4/1998 Cetin et al. ......................... 709/238
`5,754,849
`5/1998 Dyer et al..
`5,757,925
`5/1998 Faybishenko.
`5,761,656
`6/1998 Ben-Shacher.
`5,764,897
`6/1998 Khalidi.
`5,768,532
`6/1998 Megerian.
`5,774,551
`6/1998 Wu et al. .
`5,778,228
`7/1998 Wei.
`5,778,368
`7/1998 Hogan et al..
`5,787,425
`7/1998 Bigus.
`5,787,431
`7/1998 Shaughnessy.
`5,808,911
`9/1998 Tucker et al. ........................ 364/559
`5,809,507
`9/1998 Cavanaugh, III.
`5,813,013
`9/1998 Shakib et al. .
`5,815,149
`9/1998 Mutschler, III et al..
`5,815,709
`9/1998 Waldo et al. .
`5,815,711
`9/1998 Sakamoto et al. .
`5,829,022
`10/1998 Watanabe et al..
`5,832,529
`11/1998 Wollrath et al..
`5,832,593
`11/1998 Wurst et al..
`5,835,737
`11/1998 Sand et al..
`5,842,018
`11/1998 Atkinson et al..
`5,844,553
`12/1998 Hao et al..
`5,845,129
`12/1998 Wendorf et al..
`5,860,004
`1/1999 Fowlow et al. .
`5,860,153
`1/1999 Matena et al. .
`5,864,862
`1/1999 Kriens et al. .
`5,864.866
`1/1999 Henckel et al. .
`5,872,928
`2/1999 Lewis et al. .
`
`2/1999 Beard.
`5,875,335
`3/1999 Burroughs et al. .
`5,878.411
`3/1999 Furusawa.
`5,884,079
`3/1999 Ebrahim ............................... 709/201
`5,887,134
`3/1999 House et al..
`5,890,158
`4/1999 Atkinson et al..
`5,892,904
`5,899,990 * 5/1999 Maritzen et al. ........................ 707/4
`5,933,497
`8/1999 Beetcher et al..
`5,935,249
`8/1999 Stern et al. .......................... 713/201
`5,940,827
`8/1999 Hapner et al..
`5,944,793
`8/1999 Islam et al. .......................... 709/220
`5,946,485
`8/1999 Weeren et al..
`5,946,694
`8/1999 Copeland et al..
`5,987,506
`11/1999 Carter et al. ......................... 709/213
`5,995,744 * 11/1999 Guccione ............................... 703/23
`6,003,763
`12/1999 Gallagher et al..
`6,016,496
`1/2000 Robertson ............................ 707/103
`6,041,111 * 3/2000 Shelton .......
`379/201
`6,073,174 * 6/2000 Montgomerie et al.
`709/224
`6,098,093 * 8/2000 Bayeh et al.......................... 709/203
`
`
`
`FOREIGN PATENT DOCUMENTS
`O 472 874 A1
`3/1992 (EP).
`O 474 340A2
`3/1992 (EP).
`O SSS 997 A2
`8/1993 (EP).
`O 565 849 A2 10/1993 (EP).
`O 569 195 A3 11/1993 (EP).
`O 625 7SOA2 11/1994 (EP).
`O 635 792 A2
`1/1995 (EP).
`O 651328A1
`5/1995 (EP).
`O 660 231 A2
`6/1995 (EP).
`O 718 761 A1
`6/1995 (EP).
`O 697 655 A2
`2/1996 (EP).
`O 767 432 A2
`4/1997 (EP).
`O 778 520 A2
`6/1997 (EP).
`O 794. 493 A2
`9/1997 (EP).
`O 803 810 A2 10/1997 (EP).
`O 803 811 A2 10/1997 (EP).
`O 805 393 A2 11/1997 (EP).
`O 810524A1 12/1997 (EP).
`O 817 O2O A2
`1/1998 (EP).
`O 817 O22 A2
`1/1998 (EP).
`O 817 O25 A2
`1/1998 (EP).
`O836 140A2
`4/1998 (EP).
`2 253 O79
`8/1992 (GB).
`2 262 825
`6/1993 (GB).
`WO 96/03692
`2/1996 (GB).
`2305 O87
`3/1997 (GB).
`11-45187
`2/1999 (JP).
`WO 92/07335
`4/1992 (WO).
`WO92/O9948
`6/1992 (WO).
`WO94/03855
`2/1994 (WO).
`WO96/10787
`4/1996 (WO).
`WO96/18947
`6/1996 (WO).
`WO96/24099
`8/1996 (WO).
`WO98/O2814
`1/1998 (WO).
`WO98/04971
`2/1998
`
`OTHER PUBLICATIONS
`
`Ousterhout et al., The Sprite Network Operating System,
`Computer, IEEE, Feb. 1988, pp. 23–36.
`Dourish, A Divergence-Based Model of Synchrony and
`Distribution in Collaborative Systems, Xerox Technical
`Report EPC-1194-102, 1994, pp. 1-10.
`Sharrott et al., ObjectMap: Integrating High Performance
`Resources into a Distributed Object-oriented Environment,
`ICODP, 1995.
`
`Ex.1026
`APPLE INC. / Page 2 of 22
`
`

`

`US 6,237,024 B1
`Page 3
`
`Birrell et al., Grapevine: An Exercise in Distributed Com
`puting, Communications of the ACM, vol. 25, No. 4, Apr.
`1982, pp. 260–274.
`Transparent Network Computing, Locus Computing Corpo
`ration, Jan. 5, 1995.
`Gray et al., Leases: An Efficient Fault-Tolerant Mechanism
`for Distributed File Cache Consistency, ACM, 1989, pp.
`2O2-210.
`Lamport et al., The Byzantine Generals Problem, ACM
`Transactions on Programming Languages and Systems, Vol.
`4, No. 3, Jul. 1982, pp. 382–401.
`Dolev et al., On the Minimal Synchronism Needed for
`Distributed Consensus, Journal of the ACM, vol. 34, No. 1,
`Jan. 1987, pp. 77–97.
`Mummert et al., Long Term Distributed File Reference
`Tracing: Implementation and Experience, Carnegie Mellon
`University School of Computer Science, Nov. 1994, pp.
`1-28.
`Gelernter et al., Parallel Programming in Linda, Yale Uni
`versity, Jan. 1985, pp. 1-21.
`Cannon et al., Adding Fault–Tolerant Transaction ProceSS
`ing to Linda, Software-Practice and Experience, Vol. 24(5),
`May 1994, pp. 449-466.
`Kambhatla et al., Recovery with Limited Replay: Fault-Tol
`erant Processes in Linda, Oregon Graduate Institute, Tech
`nical Report CSIE 90-019, Sep. 1990, pp. 1-16.
`AnderSon et al., Persistent Linda: Linda + Transactions +
`Query Processing, Proceedings of the 13th Symposium on
`Fault Tolerant Systems, 1994, pp. 93-109.
`Gelernter, Generative Communication in Linda, ACM
`Transactions on Programming Languages and Systems, Vol.
`7, No. 1, Jan. 1985, pp. 80–112.
`Carriero et al., Distributed Data Structures in Linda, Prin
`cipals of Programming Language, 1986, pp. 1-16.
`Pinakis, Using Linda as the Basis of an Operating System
`Microkernel, University of Western Australia, Department
`of Computer Science, Aug. 1993, pp. 1-165.
`Linda Database Search, Jul. 20, 1995, pp. 1-68.
`Carriero et al, Distributed Data Structures in Linda, Yale
`Research Report YALEU/DCS/RR-438, Nov. 1985.
`Agha et al., ActorSpaces: An Open Distributed Programming
`Paradigm,
`University
`of
`Illinois,
`Report
`No.
`UIUCDCS-R-92–1766, Open Systems Laboratory TR No.
`8, Nov. 1993, pp. 1-12.
`Ahmed et al., A Program Building Tool for Parallel Appli
`cations, Yale University, Dec. 1, 1993, pp. 1-23.
`Liskov et al., Distributed Object Management in Thor,
`International Workshop on Distributed Object Management,
`1992, pp. 12.
`Coulouris et al., Distributed Systems Concepts and Designs,
`Second Edition, Addison-Wesley, 1994.
`Birrell et al., Network Objects, DEC SRC Research Report
`115, Feb. 28, 1994.
`Birrell et al., Distributed Garbage Collection for Network
`Objects, DEC SRC Research Report 116, Dec. 15, 1993.
`Jaworski, JAVA 1.1 Developer's Guide, Sams.net, 1997.
`Wollrath et al., A Distributed Object Model for the JAVATM
`System, USENIX Association, Conference on Object-Ori
`ented Technologies and Systems, Jun. 17-21, 1996.
`Harris et al., Proposal for a General Java Proxy Class for
`Distributed Systems and Other Uses, Netscape Communi
`cations Corp., Jun. 25, 1997.
`Hamilton, Java and the Shift to Net-Centric Computing
`Computer, Aug. 1996, pp. 31-39.
`
`Chung et al., A Tiny Pascal Compiler: Part I: The P-Code
`Interpreter, BYTE Publications, Inc., Sep. 1978.
`Chung et al., A Tiny Pascal Compiler: Part 2: The P-Com
`piler, BYTE Publications, Inc., Oct. 1978.
`Thompson, Regular Expression Search Algorithm, Commu
`nications of the ACM, Vol. II, No. 6, p. 149 et seq., Jun.
`1968.
`Mitchell et al., Mesa Language Manual, Xerox Corporation.
`McDaniel, An Analysis of a Mesa Instruction Set, Xerox
`Corporation, May 1982.
`Pier, A Retrospective on the Dorado, A High-Performance
`Personal Computer, Xerox Corporation, Aug. 1983.
`Pier, A Retrospective on the Dorado, A High-Performance
`Personal Computer, IEEE Conference Proceedings, The
`10th Annual international Symposium on Computer Archi
`tecture, 1983.
`Krasner, The Smalltalk-80 Virtual Machine, BYTE Publi
`cations Inc., Aug. 1991, pp. 300-320.
`Operating Systems Review, ACM Press, vol. 27, No. 5, Dec.
`1993, pp. 217-230.
`Remote Method Invocation Specification, Sun Microsys
`tems, Inc., (1997). http://java.sun.com/products/idk/1.1/
`docs/guide/rmi/spec/rmiTOC.doc.html.
`Alexander, et al., “Active Bridging, Proceedings of the
`ACM/SIGCOMM 97 Conference, Cannes, France, Sep.
`1997.
`Anonymous: “Change-Notification Service for Shared
`Files' IBM Technical Disclosure Bulletin, vol. 36, No. 8, pp.
`77–82, XP002108713 New York, US.
`Anonymous: “Resource Preemption for Priority Schedul
`ing.” Nov. 1973. IBM Technical Disclosure Bulletin, vol. 16,
`No. 6, p. 1931 XP002109435 New York, US.
`Beech et al., “Object Databases as Generalizations of Rela
`tional Databases,” Computer Standards & Interfaces, vol.
`13, Nos. 1/3, pp. 221-230, (Jan. 1991) Amsterdam, NL.
`Bertino et al., “Object-Oriented Database Management Sys
`tems: Concepts and ISSues,” Computer, Vol. 24, No. 4, pp.
`33-47, (Apr. 1991), Los Alamitos, CA.
`Betz, Mark; “Interoperable objects: laying the foundation
`for distributed object computing”; Dr. Dobb's Journal, vol.
`19, No. 11, p. 18(13); (Oct. 1994).
`Bevan, D.I., “An Efficient Reference Counting Solution To
`The Distributed Garbage Collection Problem”, Parall Com
`puting, NL, Elsevier Publishers, Amsterdam, vol. 9, No. 2,
`pp. 179-192.
`Birrell et al., “Implementing Remote Procedure Calls”,
`ACM Transactions on Computer Systems, vol. 2, No. 1, Feb.
`1984, pp. 39–59.
`Dave A et al: “Proxies, Application Interface, and Distrib
`uted Systems”, Proceedings International Workshop on
`Object Orientation in Operating Systems, Sep. 24, 1992, pp.
`212-220.
`Deux O et al: “The 02 System' Communications of the
`Association for Computing Machinery, vol. 34, No. 10, Oct.
`1, 1991, pp. 34-48.
`Drexler, K. Eric, et al., “Incentive Engineering for Compu
`tational Resource Management,” The Ecology of Computa
`tion, Elsevier Science Publishers B.V., 1988, pp. 231-266.
`Droms, R., “RFC 1541 Dynamic Host Configuration Pro
`tocol”, HTTP://WWW.CIS.OHIO-STATE.EDU/HTBIN/
`RFC/RFC1541.HTML, Oct. 1993, pp. 1–33.
`Emms J: “A Definition of an Access Control Systems
`Language' Computer Standards and Interfaces, Vol. 6, No.
`4, Jan. 1, 1987, pp. 443-454.
`
`Ex.1026
`APPLE INC. / Page 3 of 22
`
`

`

`US 6,237,024 B1
`Page 4
`
`COSC.
`
`Gosling et al., “The Java (TM) Language Specification',
`Addison-Wesley, 1996.
`Gottlob et al., “Extending Object-Oriented Systems with
`Roles,” ACM Transactions on information systems, vol. 14,
`No. 3, pp. 268–296 (Jul. 1996).
`Guth, Rob: “JavaOne: Sun to Expand Java Distributed
`Computing Effort”, “HTTP://WWWSUNWORLD.COM/
`SWOL-02-1998/SWOL-2-SUNSPOTS.HTML,”
`XP-002109935, P 1, 1998.
`Aldrich et al., Providing Easier Access to Remote Objects in
`Distributed Systems, www.cs.caltech.edu/%7ejedi/paper/je
`dipaper.html, 1997.*
`1.1
`Java
`MUX-Elektronik,
`Interactive
`www.lls.se/-mux/javaic.html, 1995.*
`Fleisch et al, High performance distributed objects using
`distributed shared memory and remote method invocation.
`IEEE, Jan. 1998.*
`Aldrich et al., Providing access to remote objects in
`client-server systems. IEEE, Jan. 1998.*
`Hamilton et al., “Subcontract: a flexible base for distributed
`programming'; Proceedings of 14th Symposium of Operat
`ing System Principles; (Dec. 1993).
`Hartman, J., Manber, U., et al., Liquid Software: A new
`paradigm for networked Systems, Technical Report 96-11,
`Department of Comp. Sci., Univ. of Arizona, Jun. 1996.
`Hunt, N., “IDF: A Graphical Data Flow Programming Lan
`guage for Image Processing and Computer Vision', Pro
`ceedings of the International Conference on Systems, Man,
`and Cybernetics, Los Angeles, Nov. 4-7, pp. 351-360,
`(1990).
`IBM (TM) Technical Disclosure Bulletin, “Object Location
`Algorithm.” vol. 36, No. 09B, pp. 257–258, Sep. 1993.
`IBM (TM) Technical Disclosure Bulletin, “Retrieval of
`Qualified Variables Using Extendible Hashing, vol. 36, No.
`12, pp. 301-303, Dec. 1993.
`IBM: “Chapter 6–Distributed SOM (DSOM)” Somobjects
`Developer Toolkit Users Guide, Version 2.1, Oct. 1994
`(1994-10), pp. 6-1-6–90.
`Jones, Richard, et al., “Garbage Collection: Algorithms for
`Automatic Dynamic Memory Management,” pp. 165-175,
`John Wiley & Sons, 1996.
`Kay, Michael H. et al., “An Overview of the Raleigh
`Object-Oriented Database System”, ICL Technical Journal,
`vol. 7, No. 4, pp. 780–798, (Nov. 1991), Oxford, GB.
`
`Kougiouris et al., “Support for Space Efficient Object Invo
`cation in Spring"; (Sep. 1994).
`Lindholm et al., “The Java (TM) Virtual Machine Specifi
`cation', Addison Wesley, 1996.
`Mitchell et al., “An Overview of the Spring System”; (Feb.
`1994).
`Orfali R. et al., “The Essential Distributed Objects Survival
`Guide,” Chapter 11: Corba Commercial ORBs, pp.
`203-215, John Wiley & Sons, Inc., (1996).
`Riggs Roger et al., “Pickling State in the Java (TM) Sys
`tem,” USENIX Association Conference on Object-Oriented
`Technologies and Systems, XP-002112719, Jun. 17-21,
`1996, pp. 241–250.
`Rosenberry et al., “Understanding DCE"; Chapters 1-3, 6;
`(1992).
`Venners, B., “Jini Technology, Out of the Box”, Javaworld,
`Online, pp 1-4, Dec. 1998.
`Waldo Jet al: “Events in an RPC based distributed system”
`Proceedings of the 1995 USENIX Technical Conference,
`Proceedings USENIX Winter 1995 Technical Conference,
`New Orleans, LA. USA, Jan. 16-20, 1995, pp. 131-142.
`Wilson, P.R., et al., “Design of the Opportunistic Garbage
`Collector,” Proceedings of the Object Oriented Program
`ming Systems Languages And Applications Conference,
`New Orleans, vol. 24, No. 10, Oct. 1989.
`Wu, Xuequn, “AType system for an Object-Oriented Data
`base System,” Proceedings of the International Computer
`Software and Applications Conference (COMPSAC), pp.
`333-338, Sep. 11–13, 1991, Tokyo, Japan.
`Yemini, Y. and S. da Silva, “Towards Programmable Net
`works”, IFIP/IEEE International Workshop on Distributed
`Systems: Operations and Management, L'Aquila, Italy, Oct.
`1996.
`Yin J. et al., “Using Leases to Support Server Driven
`Consistency in Large-Scale Systems', Computer Services
`Department, University of Texas at Austin, p. 285-294.
`Birrell et al., Implementing Remote Procedure Calls, ACM
`Transactions on Computer Systems, vol. 2, No. 1, Feb. 1984,
`pp. 39–59.
`* cited by examiner
`
`Ex.1026
`APPLE INC. / Page 4 of 22
`
`

`

`U.S. Patent
`
`May 22, 2001
`
`Sheet 1 of 7
`
`US 6,237,024 B1
`
`
`
`s
`
`3
`
`
`
`S
`
`s
`
`Ex.1026
`APPLE INC. / Page 5 of 22
`
`

`

`U.S. Patent
`
`May 22, 2001
`
`Sheet 2 of 7
`
`US 6,237,024 B1
`
`
`
`Eº)\ /HOLS OES/\HOWNEW ÅHVOJNO
`
`
`
`
`
`
`
`
`
`8 || Z.
`
`Ex.1026
`APPLE INC. / Page 6 of 22
`
`

`

`U.S. Patent
`
`May 22, 2001
`
`Sheet 3 of 7
`
`US 6,237,024 B1
`
`CLIENT
`
`302
`
`CLIENT APPLICATION
`
`REMOTE METHOD CALL n STUB
`
`RUNTIME
`
`
`
`310
`
`306
`
`SERVER
`
`312
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`REMOTE
`METHOD
`RESOURCES
`
`REMOTE
`METHOD
`RUNTIME
`REMOTE
`METHOD
`SKELETON
`
`GENERAL
`RESOURCE
`MANAGER
`EVENT
`HANDLER
`
`REMOTE OBJECTA
`
`REMOTE OBJECTB
`
`
`
`
`
`REMOTE
`METHOD
`RESOURCE
`MANAGER
`REMOTE
`EVENT
`HANDLER
`
`
`
`
`
`Ex.1026
`APPLE INC. / Page 7 of 22
`
`

`

`U.S. Patent
`
`May 22, 2001
`
`Sheet 4 of 7
`
`US 6,237,024 B1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`324
`
`322
`
`REMOTE METHOD RESOURCES
`402
`
`
`
`THREADPOOLao.
`
`406
`
`THREADS
`N-USE
`
`AVAILABLE
`THREADS
`
`
`
`
`
`REMOTE
`PROCEDURE CALL
`(RPC) STATE
`
`REMOTE METHOD RESOURCE
`MANAGER
`41 O
`412
`
`
`
`SUSPEND
`METHOD
`
`
`
`CONTINUE
`METHOD
`
`STATESTORE
`
`RPCSTATE
`
`EXECUTIVE STATE
`
`
`
`
`
`
`
`REMOTE OBJECTA 416
`
`REMOTE METHOD
`
`
`
`EXECUTION
`STATE
`
`418
`
`FIG. 4
`
`Ex.1026
`APPLE INC. / Page 8 of 22
`
`

`

`U.S. Patent
`
`May 22, 2001
`
`Sheet S of 7
`
`US 6,237,024 B1
`
`START
`
`SERVER SKELETON UNMARSHALLS
`DATA AND PARAMETERS FROM
`REMOTE METHOD CALL REGUEST
`SENT BY CLIENT
`
`REMOTE METHOD RUNTIME
`INDICATES TO CLIENT APPLICATION
`THAT REGUEST IS BEING
`PROCESSED
`
`
`
`
`
`
`
`
`
`REMOTE METHOD RESOURCE
`MANAGER ALLOCATES
`RESOURCES TO REMOTE
`METHOD
`
`506
`
`507
`
`508
`
`REMOTE METHOD INVOKED
`
`510
`
`516
`
`
`
`512
`
`
`
`
`
`SUSPEND
`CONDITION?
`
`514
`
`NO
`
`COMPLETE PROCESSING
`USING RESOURCES
`
`SUSPEND METHOD
`AND RELEASE
`RESOURCES
`
`
`
`518
`
`METHOD SUSPENDS
`WAITING FOR
`CONTINUATION EVENT
`
`RESOURCES ALLOCATED
`AND REMOTE METHOD
`RESUMES PROCESSING
`
`
`
`
`
`
`
`
`
`
`
`Ex.1026
`APPLE INC. / Page 9 of 22
`
`

`

`U.S. Patent
`
`May 22, 2001
`
`Sheet 6 of 7
`
`US 6,237,024 B1
`
`START
`
`METHOD DETECTS SUSPEND
`EVENT AND ELECTS TO
`RELINGUISH RESOURCES
`
`REMOTE METHOD RESOURCE
`MANAGER IS PROVIDED
`EXECUTION STATE AND
`RPC STATE
`
`STORE EXECUTION STATE AND
`RPC STATE FOR CONTINUATION
`OF PROCESSING REMOTE
`METHOD
`
`516
`
`
`
`
`
`
`
`SUSPEND PROCESSING OF
`REMOTE METHOD WAITING FOR
`CONTINUATION EVENT TO OCCUR
`
`602
`
`604
`
`608
`
`610
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 6
`
`Ex.1026
`APPLE INC. / Page 10 of 22
`
`

`

`U.S. Patent
`
`May 22, 2001
`
`Sheet 7 of 7
`
`US 6,237,024 B1
`
`702
`
`704
`
`7O6
`
`708
`
`710
`
`712
`
`714.
`
`START
`
`CONTINUATION METHOD RECEIVES
`INDICATION THAT PARTICULAR CONTINUATION
`EVENT ASSOCATED WITH A REMOTE
`METHOD HAS OCCURRED
`
`
`
`520
`
`REMOTE METHOD MANAGER DSCOVERS
`THAT REMOTE METHOD IS NOW RUNNABLE
`AND CAN CONTINUE PROCESSING
`
`REMOTE METHOD MANAGER ASSIGNS
`RESOURCES TO REMOTE METHOD
`
`REMOTE METHOD RUNTIME LOADS
`EXECUTION STATE WHICH CONTINUES
`EXECUTION OF REMOTE METHOD
`
`REMOTE METHOD CONTINUES PROCESSING
`ON SERVER USING RESOURCES
`
`RESULTS GENERATED BY METHOD PROVIDED
`TO REMOTE METHODSKELETON FOR
`ENCODING AND PACKAGING
`
`ENCODED RESULTS PROVIDED TO INVOKING
`METHOD ON CLIENT
`
`END
`
`Ex.1026
`APPLE INC. / Page 11 of 22
`
`

`

`1
`METHOD AND APPARATUS FOR THE
`SUSPENSION AND CONTINUATION OF
`REMOTE PROCESSES
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`This invention generally relates to distributed computing
`Systems and more particularly, to a method and apparatus for
`the Suspension and continuation of remote processes.
`2. Related Applications
`The following identified U.S. patent applications are
`relied upon and are incorporated by reference in this appli
`cation.
`Provisional U.S. Patent Application No. 60/076,048,
`entitled “Distributed Computing System,” filed on Feb. 26,
`1998.
`U.S. patent application Ser. No. 09/044,923; entitled
`“Method and System for Leasing Storage,” filed on the same
`date herewith.
`U.S. patent application Ser. No. 09/044,838, entitled
`"Method, Apparatus, and Product for Leasing of Delegation
`Certificates in a Distributed System,” filed on the same date
`herewith.
`U.S. patent application Ser. No. 09/044,834, entitled
`“Method, Apparatus and Product for Leasing of Group
`Membership in a Distributed System,” filed on the same date
`herewith.
`U.S. patent application Ser. No. 09/044,916, entitled
`“Leasing for Failure Detection,” filed on the same date
`herewith.
`U.S. patent application Ser. No. 09/144933, entitled
`“Method for Transporting Behavior in Event Based
`System,” filed on the same date herewith.
`U.S. patent application Ser. No. 09/044.919, entitled
`“Deferred Reconstruction of Objects and Remote Loading
`for Event Notification in a Distributed System,” filed on the
`Same date here with.
`U.S. patent application Ser. No. 09/044.938, entitled
`“Methods and Apparatus for Remote Method Invocation,”
`filed on the same date herewith.
`U.S. patent application Ser. No. 09/045,652, entitled
`“Method and System for Deterministic Hashes to Identify
`Remote Methods, filed on the same date herewith.
`U.S. patent application Ser. No. 09/044,790, entitled
`“Method and Apparatus for Determining Status of Remote
`Objects in a Distributed System,” filed on the same date
`herewith.
`U.S. patent application Ser. No. 09/044,930, entitled
`“Downloadable Smart Proxies for Performing Processing
`ASSociated with a Remote Procedure Call in a Distributed
`System,” filed on the same date herewith.
`U.S. patent application Ser. No. 09/044,917, entitled
`“Suspension and Continuation of Remote Methods,” filed on
`the same date here with.
`U.S. patent application Ser. No. 09/044,835, entitled
`“Method and System for Multi-Entry and Multi-Template
`Matching in a Database,” filed on the same date herewith.
`U.S. patent application Ser. No. 09/044,839, entitled
`“Method and System for In-Place Modifications in a
`Database,” filed on the same date herewith.
`U.S. patent application Ser. No. 09/044,945, entitled
`“Method and System for Typesafe Attribute Matching in a
`Database,” filed on the same date herewith.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,237,024 B1
`
`2
`U.S. patent application Ser. No. 09/044.931, entitled
`“Dynamic Lookup Service in a Distributed System,” filed on
`the same date here with.
`U.S. patent application Ser. No. 09/044.939, entitled
`“ Apparatus and Method for Providing Downloadable Code
`for Use in Communicating with a Device in a Distributed
`System,” filed on the same date herewith.
`U.S. patent application Ser. No. 09/044,826, entitled
`“Method and System for Facilitating Access to a Lookup
`Service, filed on the same date herewith.
`U.S. patent application Ser. No. 09/044.932, entitled
`“ Apparatus and Method for Dynamically Verifying Infor
`mation in a Distributed System,” filed on the same date
`herewith.
`U.S. patent application Ser. No. 09/030,840, entitled
`“Method and Apparatus for Dynamic Distributed Comput
`ing Over a Network,” and filed on Feb. 26, 1998.
`U.S. patent application Ser. No. 09/044,936, entitled “An
`Interactive Design Tool for Persistent Shared Memory
`Spaces, filed on the same date herewith.
`U.S. patent application Ser. No. 09/044,934, entitled
`“Polymorphic Token-Based Control,” filed on the same date
`herewith.
`U.S. patent application Ser. No. 07/044.915, entitled
`"Stack-Based Access Control, filed on the same date here
`with.
`U.S. patent application Ser. No. 09/044,944, entitled
`“Stack-Based Security Requirements, filed on the same
`date herewith.
`U.S. patent application Ser. No. 09/044,837, entitled
`“Per-Method Designation of Security Requirements, filed
`on the same date herewith.
`3. Description of the Related Art
`A typical distributed computing System makes the Ser
`vices and computing power of many Servers available to
`many different clients over a network. Typically, a client
`machine accesses processing capabilities on a Server
`machine using a remote procedure call (RPC) System. The
`RPC system processes the request on the remote machine
`and returns the desired results to the requesting client. The
`network used to transmit the request and return the results
`can be a local area network (LAN), a wide area network
`(WAN), and can also include the Internet. Sophisticated
`distributed computing applications on the Internet offer
`electronic commerce (e-commerce), telecommuting, and
`interactive entertainment Services around the World using
`this client-server arrangement.
`AS the distributed computing paradigm grows in usage
`and popularity it is increasingly important that resources on
`the Server Systems are available to fulfill requests made by
`the client Systems. Each request from a client generally
`causes a Server process to designate resources, including one
`or more threads, to process the requests. A thread, Sometimes
`called a lightweight proceSS, is a separate Sequence of
`instructions within a process having a separate flow of
`control. The thread must carve out resources from the
`System as needed to fulfill the particular request. If resources
`Such as memory and data are available, multiple threads can
`be executed in parallel to fulfill multiple tasks.
`Thread Schedulers can be used by the process spawning
`the threads to coordinate parallel execution of the threads
`based on a thread's priority, State of execution (i.e. sleep,
`alive, dead, running), and dependencies among the various
`threads. A thread Scheduler on a single processor System
`distributes the processor's computing power among many
`
`Ex.1026
`APPLE INC. / Page 12 of 22
`
`

`

`3
`threads to provide the illusion that the threads are actually
`running in parallel. There are many different Scheduling
`techniques which can be used including first-come-first
`Served, shortest-thread-first, priority Scheduling, and pre
`emptive Scheduling techniques Such as round-robin. Hybrid
`Scheduling techniques which combine these techniques can
`also be used as needed by the particular implementation. On
`multiprocessor Systems, Schedulers associate different
`threads with different processors to execute threads in par
`allel and take advantage of the added computing power.
`Unfortunately, if these resources are not immediately
`available, the thread can not continue execution and is
`blocked from further processing. These blocked threads of
`execution hold on to Server resources, Such as memory, as
`well as the data and control Structures associated with the
`threads themselves. Eventually, the Server may run out of
`threads to allocate incoming client requests. Incoming client
`requests may be refused and the server will be effectively
`removed from the distributed computing environment. This
`blocking Scenario can also reduce a servers ability to Service
`existing requests due to overhead associated with denying
`Service to the incoming calls.
`Present distributed computing Systems are not designed to
`address this problem of allocating threads. These Systems do
`not release threads and associated resources when a remote
`Server proceSS is blocked waiting for a resource or particular
`event. Consequently, transaction intensive distributed com
`puting environments can Suffer from the blocking Scenario
`described above. For example, assume a server proceSS
`receives multiple requests to download a file from multiple
`clients over the Internet. The Server process receives mul
`tiple threads from the Server operating System to process the
`requests in parallel but the file requested is locked by another
`proceSS and is not available. A conventional System would
`block further processing on each thread and wait for the file
`to be unlocked. The threads on the server would remain idle
`even though other processes could utilize the thread
`resources to process other tasks. When the number of
`threads on a Server System are depleted, the Server proceSS
`will deny service to additional clients. Eventually, the server
`System will have difficulty processing general tasks.
`On many distributed computing Systems, the inability to
`allocate threads and other resources can negatively impact
`overall processing throughput. Even the high-Speed band
`width available on a distributed computing network will go
`unused if threads and other resources are not allocated
`efficiently on the Server System.
`Based on the above limitations found in conventional
`Systems, it is desirable to improve the allocation of threads
`and other resources used in a distributed computing envi
`rOnment.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`US 6,237,024 B1
`
`4
`Server System when the remote method depends on a general
`resource which is not available.
`Another method consistent with the present invention,
`enables a previously Suspended remote method to continue
`processing on the Server System and generate a result for a
`client application. This method comprises receiving an indi
`cation that a continuation event associated with a Suspended
`remote method has occurred. System resources and general
`resources are allocated to the remote method in preparation
`to continue processing the remote method. The remote
`method utilizes the combined allocated resources to con
`tinue execution and generate results. These results are trans
`mitted from the Server System to the client application on the
`client System