Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
2003-09-24
2010-10-12
Sough, Hyung S (Department: 2194)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C707S704000, C711S155000
Reexamination Certificate
active
07814488
ABSTRACT:
Techniques are provided for quickly reacquiring mutual exclusion locks (QRLs), such as in the case in which a single process repeatedly acquires and releases the lock and in which no other process attempts to acquire the same lock. When the first holder of a QRL first acquires the lock, it biases the lock to itself. Bias may be directed in different way or at different times in some realizations. Biasing may involve a one-time compare-and-swap instruction. Thereafter, this bias-holder can reacquire and release the lock free of atomic read-modify-write operations. If a second process attempts to acquire a QRL, then the lock may revert to a “default lock”. Any standard mutual exclusion lock may be used as the default lock. A QRL lock may be reinitialized so that it can be rebiased. Rebiasing may be valuable in the case of migratory data access patterns.
REFERENCES:
patent: 3886525 (1975-05-01), Brown et al.
patent: 4584640 (1986-04-01), MacGregor et al.
patent: 4847754 (1989-07-01), Obermarck et al.
patent: 5224215 (1993-06-01), Disbrow
patent: 5860126 (1999-01-01), Mittal
patent: 6038646 (2000-03-01), Sproull
patent: 6081665 (2000-06-01), Nilsen et al.
patent: 6112222 (2000-08-01), Govindaraju et al.
patent: 6128710 (2000-10-01), Greenspan et al.
patent: 6144965 (2000-11-01), Oliver
patent: 6178423 (2001-01-01), Douceur et al.
patent: 6360219 (2002-03-01), Bretl et al.
patent: 6360220 (2002-03-01), Forin
patent: 6366932 (2002-04-01), Christenson
patent: 6430649 (2002-08-01), Chaudhry et al.
patent: 6581063 (2003-06-01), Kirkman
patent: 6651146 (2003-11-01), Srinivas et al.
patent: 6662364 (2003-12-01), Burrows et al.
patent: 6678807 (2004-01-01), Boatright et al.
patent: 6757891 (2004-06-01), Azagury et al.
patent: 6772153 (2004-08-01), Bacon et al.
patent: 6792601 (2004-09-01), Dimpsey et al.
patent: 6826757 (2004-11-01), Steele, Jr. et al.
patent: 6965961 (2005-11-01), Scott
patent: 7398376 (2008-07-01), McKenney
patent: 2001/0014905 (2001-08-01), Onodera
patent: 2001/0047361 (2001-11-01), Martin et al.
patent: 2003/0140085 (2003-07-01), Moir et al.
patent: 2003/0174572 (2003-09-01), Moir et al.
patent: 2003/0182462 (2003-09-01), Moir et al.
patent: 2003/0182465 (2003-09-01), Moir et al.
patent: 2004/0015510 (2004-01-01), Moir et al.
patent: 2004/0015642 (2004-01-01), Moir et al.
patent: 2004/0034673 (2004-02-01), Moir et al.
patent: 2004/0153687 (2004-08-01), Moir et al.
patent: 0 366 585 (1990-05-01), None
patent: 0 466 339 (1992-01-01), None
patent: WO 86/00434 (1986-01-01), None
patent: WO 01/53942 (2001-07-01), None
patent: WO 01/53943 (2001-07-01), None
patent: WO 01/80015 (2001-10-01), None
patent: WO 01/82057 (2001-11-01), None
patent: WO 03/060705 (2003-07-01), None
patent: WO 03/060715 (2003-07-01), None
Massalin, H., et al., “A Lock-Free Multiprocessor OS Kernel,” Technical Report TR CUCS-005-9, Columbia University, New York, NY, 1991, 21 pages.
Massalin, Henry, “Synthesis: An Efficient Implementation of Fundamental Operating System Services,” Dissertation submitted in partial fulfillment of the requirements for the Degree of Doctor of Philosophy in the Graduate School of Arts and Sciences, Columbia University, New York, NY, online, 158 pages, 1992 [retrieved from the Internet on Jul. 13, 2001: URL:ftp://ftp.cs.columbia.edu/reports/reports-1992/cucs-039-92.ps.gz].
Bershad, B. N., “Practical Considerations for Non-Blocking Concurrent Objects,”Proceedings 13th IEEE International Conference on Distributed Computing Systems, pp. 264-273. IEEE Computer Society Press, Washington, D.C., 1993.
Herlihy, M., “A Methodology For Implementing Highly Concurrent Data Objects,”ACM Transactions on Programming Languages and Systems, 15(5):745-770, Nov. 1993.
Attiya, Hagit, et al., “Are Wait-Free Algorithms Fast?”Journal of the ACM, 41(4):725-763, Jul. 1994.
Lamarca, A., “A performance evaluation of lock-free synchronization protocols,”Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing, pp. 130-140, ACM Press, New York, NY, 1994.
Michael, Maged M. et al., “Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms,” Proceedings of PODC, pp. 267-275, May 1996.
Attiya, H., et al., “Universal Operations: Unary versus Binary,”Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing, pp. 223-232, ACM Press, New York, NY, 1996.
Greenwald, M. B., et al., “The Synergy Between Non-Blocking Synchronization and Operating System Structure,”Proceedings of the 2nd Symposium on Operating Systems Design and Implementation, pp. 123-136, Usenix Association, Berkeley, CA, 1996.
Afek, Y., et al., “Disentangling Multi-Object Operations,”Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing, pp. 111-120, Aug. 1997. Santa Barbara, CA.
Arora, N. S., et al., “Thread Scheduling For Multiprogrammed Multiprocessors,”Proceedings of the 10th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 119-129, ACM Press, New York, NY, 1998.
Attiya, Hagit, et al., “Atomic Snapshots in O(n log n) Operations,”SIAM Journal on Computing, 27(2):319-340, Apr. 1998.
Greenwald, M., “Non-Blocking Synchronization and System Design,” PhD thesis, Stanford University Technical Report STAN-CS-TR-99/1624, Palo Alto, CA, Aug. 1999, 241 pages.
Agesen, Ole, et al.: “DCAS-Based Concurrent Deques,”SPAA 2000. Proceedings of the 12th Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 137 146, ACM Press, New York, NY, ISBN: 1-58113-185-2, 2000.
Detlefs, David L., et al., “Even Better DCAS-Based Concurrent Deques,”Lecture Notes in Computer Science, vol. 1914, pp. 59-73, Springer-Verlag, Berlin, Germany, ISBN: 3-540-41143-7, 2000.
Anderson, James H. et al., “Universal Constructions for Large Objects,”IEEE Transactions on Parallel and Distributed Systems, vol. 10, No. 12, pp. 1317-1332, 1999.
Dice, David et al., “Mostly Lock-Free Malloc,”Proceedings of the 3rd International Symposium on Memory Management, pp. 163-174, ACM Press, New York, NY, 2002.
Dijkstra, E., “Solution to a Problem in Concurrent Programming Control,” Communications of the ACM, vol. 8, No. 9, p. 569, 1965.
Mellor-Crummey, J., et al., Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors,ACM Transactions on Computer Systems, vol. 9, No. 1, pp. 21-65, Feb. 1991.
Moir, Mark, “Practical implementation of non-blocking synchronization primitives,”Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, pp. 219-228, ACM Press, New York, NY, 1997.
Agesen, Ole at el., “An Efficient Meta-Lock for Implementing Ubiquitous Synchronization”, ACM SIGPLAN Notices, vol. 34, No. 10, pp. 207-222, 1999.
Bacon, David F. et al., “Thin Locks: Featherweight Synchronization for Java”, ACM SIGPLAN Notices, vol. 33, No. 6, pp. 258-268, 1998.
Dice, David, “Implementing Fast Java™ Monitors with Relaxed Locks”, In Proceedings of the USENIX JVM'01 Conference, 2001.
Lamport, Leslie, “A Fast Mutual Exclusion Algorithm”, ACM Transactions on Computer Systems, vol. 5, No. 1, pp. 1-11, 1987.
U.S. Appl. No. 09/547,288, filed Apr. 11, 2000 and naming as inventor(s) Shavit et al.
U.S. Appl. No. 09/547,290, filed Apr. 11, 2000 and naming as inventor(s) Shavit et al.
U.S. Appl. No. 09/710,218, filed Nov. 10, 2000 and naming as inventor(s) Harris, Timothy.
U.S. Appl. No. 09/837,671, filed Apr. 18, 2001 and naming as inventor(s) Detlefs et al.
Dice David
Moir Mark S.
Scherer, III William N.
Anya Charles E
Kowert Robert C
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Oracle America Inc.
Sough Hyung S
LandOfFree
Quickly reacquirable locks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Quickly reacquirable locks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quickly reacquirable locks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4230236