Lock-free cache management

Patent 6904456 Issued on June 7, 2005. Estimated Expiration Date:

February 20, 2021. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

Flat cache-only multi-processor architectures
Patent #: 5535116
Issued on: 07/09/1996
Inventor: Gupta, et al.

Program execution control device having addressability in accordance with M series pseudo-random number sequence
Patent #: 5651123
Issued on: 07/22/1997
Inventor: Nakagawa, et al.

Method and apparatus for managing coherency in object and page caches
Patent #: 5829022
Issued on: 10/27/1998
Inventor: Watanabe, et al.

Method for dynamically and efficiently caching objects received from an application server by a client computer by subdividing cache memory blocks into equally-sized sub-blocks
Patent #: 6141737
Issued on: 10/31/2000
Inventor: Krantz, et al.

Method and apparatus for shared persistent virtual storage on existing operating systems
Patent #: 6298428
Issued on: 10/02/2001
Inventor: Munroe, et al.

Method and apparatus for processing cache misses
Patent #: 6438650
Issued on: 08/20/2002
Inventor: Quach, et al.

Interface system and method for asynchronously updating a share resource with locking facility
Patent #: 6449614
Issued on: 09/10/2002
Inventor: Marcotte

Multi-resolution tree for longest match address lookups
Patent #: 6563823
Issued on: 05/13/2003
Inventor: Przygienda, et al.

Fast address lookup in routing tables Patent #: 6581106
Issued on: 06/17/2003
Inventor: Crescenzi, et al.

Inventor

Cox, Shaun D.

Assignee

Microsoft Corporation

Application

No. 09789280 filed on 02/20/2001

US Classes:

709/219, Accessing a remote server709/203, Client/server709/224, Computer network monitoring709/226, Network resource allocating709/245, COMPUTER-TO-COMPUTER DATA ADDRESSING711/208, Segment or page table descriptor700/5, Shared memory712/208, INSTRUCTION DECODING (E.G., BY MICROINSTRUCTION, START ADDRESS GENERATOR, HARDWIRED)711/118, Caching711/171, Based on data size711/202, Address mapping (e.g., conversion, translation)707/8, Concurrency (e.g., lock management in shared database)370/392, Processing of address header for routing, per se709/242Routing data updating

Examiners

Primary: Etienne, Ario
Assistant: Jacobs, LaShonda

Attorney, Agent or Firm

Leydig, Voit & Mayer Ltd.

International Class

G06F015/16

Abstract

A data structure and method implemented in accordance with the invention enable reading a cache to get a type information corresponding to an address of interest more reliably than with volatile read operations and faster than scanning tables or walking along linked lists. Reliably reading the cache enabled by the invention does not require locks, although, the type information and the address together require more bits than those present in one machine word.

Other References

Hinden, R. et al.; “IP Version 6 Addressing Architecture,” Internet Draft; (Mar. 2000), pp. 1-25; retrieved from http://ietf.org/internet-drafts/draft-ietf-ipngwg-scoping-01.txt, on Sep. 25, 2000.
Annotated Bibliography, “OS Support for High-Speed Networking”pp. 1-6; retrieved from http://www.cs.arizona.edu/xkernel/www/bibliography.html on Dec. 4, 1999.
“Imscan announces joint marketing agreement with NTIOM Systems,” M2 Presswire pNA; (Jan. 12, 2000).
Hutchinson, Norman C., et al., “The x-Kernel: An Architecture for Implementing Network Protocols”, pp. 1-26, Abstract.
Mosberger, David, “Map Library Design Notes”, pp. 1-11, (Jan. 1996) Abstract.
Chu, Hsiao-Keng Jerry, “Zero-Copy TCP in Solaris”, Sunsoft Inc., Abstract.
Mosberger, David, “Message Library Design Notes”, pp. 1-8, (Jan. 1996).
Bailey, Mary L., et al., “The x-chip: An Experiment in Hardware Demultiplexing”, Department of Computer Science, The University of Arizona.
Bailey, Mary L., et al., “Pathfinder: A Pattern-Based Packet Classifier”, Department of Computer Science University of Arizona, Appears in Proceedings of the First Symposium on Operating Systems Design and Implementation, Usenix Association, (Nov. 1994), Abstract.
Pagels, Michael, A., et al., “Cache and TLB Effectiveness in Processing Network I/O”, Department of Computer Science, The University of Arizona, (Mar. 11, 1994), Abstract.
Druschel, Peter, et al., “Network Subsystem Design: A Case for an Integrated Data Path”, Department of Computer Science, University of Arizona, pp. 1-21, Abstract.
Abbott, Mark, B., et al., “Increasing Network Throughput by Integrating Protocol Layers” Department of Computer Science, The University of Arizona, pp. 1-28, Abstract.
Mosberger, David, et al., “Analysis of Techniques to Improve Protocol Processing Latency”, Department of Computer Science, The University of Arizona, to appear in SIGCOMM 96, pp. 1-12, Abstract.
Druschel, Peter, et al., “Experiences with a High-Speed Network Adaptor: A Software Perspective”, Department of Computer Science, University of Arizona, and Computer Networking Research Department, Bell Communications Research, Abstract.
Wilson, Paul R., et al., “Dynamic Storage Allocation: A Survey and Critical Review”, Department of Computer Science, University of Arizona, pp. 1-78, Abstract.
Mellor-Crummey, John M., et al., “Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors”, ACM Transaction on Computer System, vol. 9(1), pp. 21-65, (Feb. 1991).
Dalton, Chris, et al., Afterburner: “A network-independent card provides architectural support for high-performance protocols”, IEEE Network, (Jul. 1993), pp. 36-43.
Saha, Avijit, et al., “Distributed Directory Tags,” Computer Architecture News, vol. 22, No. 5, Dec. 1994, p. 27-29.
“Magnetic's Attractions,” UNIX News, pS14, Mar. 1995, ISSN:0956-2753.
“Imscan Systems: Imscan announces joint marketing agreement with NTIOM Systems,” M2 PRESSWIRE, Jan. 12, 2000.
Glass Brett, “Bad hard disk sectors can present a problem for SmartDrive,” (Buyers Advisory) (Column), InfoWorld, vol. 14, No. 33, p. 114(1), Aug. 17, 1992.
Deering, S., et al., “IP Version 6 Scoped Address Architecture,” Internet Draft, Mar. 2000; retrieved from http://ietf.org/internet-drafts/draft-ietf-ipngwg-scoping-arch-01.txt on Sep. 25, 2000.