United States Patent (19)
`Hagersten et al.
`
`USOO5835906A
`Patent Number:
`11
`(45) Date of Patent:
`
`5,835,906
`Nov. 10, 1998
`
`54 METHODS AND APPARATUS FOR SHARING
`STORED DATA OBJECTS IN A COMPUTER
`SYSTEM
`
`75 Inventors: Erik E. Hagersten, Palo Alto, Calif.;
`Mark Donald Hill, Madison, Wis.
`73 Assignee: Sun Microsystems, Inc., Palo Alto,
`Calif.
`
`21 Appl. No.: 673,130
`22 Filed:
`Jul. 1, 1996
`(51) Int. Cl." ...................................................... G06F 17/30
`52 U.S. Cl. ...................................................... 707/8; 707/1
`58 Field of Search ..................................... 395/601, 602,
`395/603, 607, 608, 609, 610, 611, 616,
`617, 618, 619, 620, 468,823, 825, 840;
`707/1, 2, 3, 7, 8, 9, 10, 100
`
`56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,442,758 8/1995 Slingwine et al. ...................... 395/608
`5,483,641
`1/1996 Jones et al. ......
`... 395/823
`5,566,349 10/1996 Trout ............
`... 395/840
`5,568,639 10/1996 Wilcox et al. .......
`... 395/616
`5,608,893 3/1997 Slingwine et al. ...................... 395/468
`
`5,619,723 4/1997 Jones et al. ............................. 395/823
`Primary Examiner Thomas G. Black
`Assistant Examiner Ruay Lian Ho
`Attorney, Agent, or Firm Beyer & Weaver, LLP
`57
`ABSTRACT
`A method, in a computer System having a first plurality of
`Stored data objects and capable of running multiple threads
`concurrently, for preventing access conflicts. The method
`includes the Step of providing a dynamic lock Structure
`having a plurality of dynamic lock Structure members. There
`is also the Step of mapping a Second plurality of Stored data
`objects of the first plurality of stored data objects into a first
`dynamic lock Structure member of the plurality of dynamic
`lock Structure members in accordance with a mapping
`function. Due to the mapping function, the plurality of
`dynamic lock Structure members become fewer in number
`than the number of the first plurality of stored data objects.
`The first dynamic lock Structure member is configured to
`store identities of a third plurality of stored data objects. The
`third plurality of Stored data objects represent a Subset of the
`Second plurality of Stored data objects that are accessed,
`whereby a Stored data object having its identity Stored in the
`dynamic lock Structure cannot be accessed by any thread
`other than a thread currently accessing the Stored data object.
`
`25 Claims, 10 Drawing Sheets
`
`.
`
`
`
`. .
`
`DYNAMIC LOCK STRUCTURE
`
`350
`
`310
`
`312
`
`314
`
`320
`
`322
`
`32A
`
`IPR2022-00600
`Apple EX1023 Page 1
`
`

`

`U.S. Patent
`
`Nov. 10, 1998
`
`Sheet 1 of 10
`
`5,835,906
`
`102
`
`104
`
`PROCESSOR
`
`110
`
`FIG. 1A
`
`
`
`PROCESSOR
`
`122
`
`PROCESSOR
`
`124
`
`PROCESSOR
`
`126
`
`132
`
`FIG. 1B
`
`IPR2022-00600
`Apple EX1023 Page 2
`
`

`

`U.S. Patent
`
`Nov. 10, 1998
`
`Sheet 2 of 10
`
`5,835,906
`
`160
`
`COMPUTER
`
`162
`
`COMPUTER
`
`
`
`COMPUTER
`
`164
`
`FIG. 1C
`
`IPR2022-00600
`Apple EX1023 Page 3
`
`

`

`U.S. Patent
`
`Nov. 10, 1998
`
`Sheet 3 of 10
`
`5,835,906
`
`2O2
`
`204
`
`2O6
`
`18O
`
`184
`
`110
`
`X- 190
`
`X
`
`/N 194
`
`O
`O
`O
`
`FIG. 2
`(PRIOR ART)
`
`IPR2022-00600
`Apple EX1023 Page 4
`
`

`

`U.S. Patent
`
`Nov. 10, 1998
`
`Sheet 4 of 10
`
`5.835,906
`
`.
`
`X
`
`CL 310
`
`CL 312
`
`CL 314
`
`DYNAMIC LOCK STRUCTURE
`
`350
`
`M1
`
`M3
`
`CL 320
`N7
`
`X.
`
`CL 322
`
`CL 324
`
`110
`
`-
`
`re-it
`
`so
`in JI
`will O
`
`FIG. 3
`
`IPR2022-00600
`Apple EX1023 Page 5
`
`

`

`U.S. Patent
`
`Nov. 10, 1998
`
`Sheet 5 of 10
`
`5,835,906
`
`
`
`PHYSICAL LOCK
`370
`
`LST- LOCK FLAG
`372
`
`DYNAMIC LIST
`374
`
`PHYSICAL LOCK
`380
`
`LIST. LOCK FLAG
`382
`
`DYNAMIC LIST
`384
`
`PHYSICAL LOCK
`390
`
`LST- LOCK FLAG
`392
`
`DYNAMIC LIST
`394
`
`350
`
`FIG. AA
`
`IPR2022-00600
`Apple EX1023 Page 6
`
`

`

`U.S. Patent
`
`
`
`5,835,906
`
`LSITXOOTNn
`
`
`A LdWE LON
`õ?
`
`092
`
`IPR2022-00600
`Apple EX1023 Page 7
`
`

`

`U.S. Patent
`
`Nov. 10, 1998
`
`Sheet 7 of 10
`
`5,835,906
`
`THREAD A WISHES TO ACQUIRE
`CONCEPTUAL LOCKX
`
`510
`
`512
`
`
`
`
`
`
`
`
`
`
`
`STORE ID(X) INTO ASSOCIATED
`PHYSICAL LOCK IF ASSOCIATED
`DYNAMIC LIST IS EMPTY AND
`ASSOCIATED PHYSICAL LOCKS
`UNUSED
`
`NOTEMPTY
`
`LOCK OUTASSOCIATED DYNAMIC
`LIST
`
`PRESERVE CONTENT OF
`ASSOCIATED PHYSICAL LOCK
`INTO TEMPLOCATION AND SET
`ASSOCIATED PHYSICAL LOCKs
`NOTEMPTY
`
`
`
`
`
`
`
`TEMP LOCATION EMPTY
`
`NO
`
`58
`
`NOTAVAILABLE
`
`
`
`
`
`CHECK ASSOCATED DYNAMIC LIST
`AND LOCATION TEMPTO SEE
`WHETHER VIRTUAL LOCKX
`IS AWALABLE
`
`54
`
`SUCCEED
`
`544
`
`UNLOCK
`ASSOCATED
`DYNAMIC LIST
`
`
`
`
`
`STORE ID(X) INTO
`ASSOCATED
`PHYSICAL LOCK
`
`542
`
`AVAILABLE
`
`PUT PREVIOUSLY PRESERVED
`CONTENT OF ASSOCIATED
`PHYSICAL LOCK BACK INTO
`ASSOCATED PHYSICAL LOCK
`
`
`
`
`
`UNLOCKASSOCIATED DYNAMIC
`LIST
`
`520
`
`FAIL
`
`STORE ALL CONCEPTUAL LOCK
`ID'S THAT MAP INTO ASSOCIATED
`DYNAMIC LOCK STRUCTURE
`MEMBER AND CURRENTLY
`ACCESSED, INCLUDING ID(X), INTO
`ASSOCIATED DYNAMIC LIST
`
`UNLOCK ASSOCIATED DYNAMIC
`LIST
`
`524.
`
`
`
`FIG. 5A
`
`530
`
`SUCCEED
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`IPR2022-00600
`Apple EX1023 Page 8
`
`

`

`U.S. Patent
`
`Nov. 10, 1998
`
`Sheet 8 of 10
`
`5,835,906
`
`552
`
`
`
`
`
`
`
`
`
`
`
`
`
`THREAD 202 WISHES TO ACQUIRE
`CONCEPTUAL LOCK CL322
`
`550
`
`COMPARE AND SWAPCL 332 INTO
`PL 420 IF CONTENT OF PL 420 =
`EMPTY
`
`SUCCEED
`
`SET LIST-LOCK FLAG 424 -
`LOCKLIST
`
`553
`
`584
`
`
`
`SETTEMP = NOT EMPTY AND SWAP
`TEMP INTO PL 420
`
`SET LST-LOCK FLAG
`424 = UNLOCKLIST
`
`TEMPLOCATION = EMPTY?
`
`SET PL 420 - CL 322
`
`NO
`
`YES
`
`
`
`
`
`
`
`CONCEPTUAL LOCKCL 322 IN
`DYNAMIC
`LIST 422 OR IN TEMP?
`
`NO
`
`582
`
`566
`
`
`
`
`
`SWAPTEMP INTO PL 420
`
`SET LIST-LOCK FLAG 424 st
`UNLOCKLIST
`
`564
`
`FAIL
`
`560
`
`562
`
`
`
`
`
`
`
`
`
`ADD INTO DYNAMIC LIST 422
`CONCEPTUAL LOCKCL 322
`
`570
`
`SET LST-LOCK FLAG 424 =
`UNLOCKLIST
`
`FIG. 5B
`
`SUCCEED
`
`IPR2022-00600
`Apple EX1023 Page 9
`
`

`

`U.S. Patent
`
`Nov. 10, 1998
`
`Sheet 9 of 10
`
`5,835,906
`
`THREAD A WISHESTORELEASE
`CONCEPTUAL LOCKX
`
`6 O2
`
`6O4
`
`
`
`STORE EMPTY FLAG INTO
`ASSOCLATED PHYSICAL LOCKF
`CONTENT OFASSOCATED PHYSICAL
`LOCK =D(X)
`
`LOCKOUTASSOCLAEDDYNAMIC
`LIST
`
`606
`
`STORE EMPTY FLAG INTO
`ASSOCLATED PHYSICAL LOCKF
`CONTENT OF ASSOCATED PHYSICAL
`LOCK = ID(X)
`
`6 O
`
`
`
`
`
`
`
`UNLOCKASSOCATEDDYNAMIC
`LIST
`
`DELETE IDCX) FROM ASSOCIATED
`DYNAMIC LIST
`
`614
`
`
`
`DOES ASSOCIATED DYNAMIC LIST HAVE ONLY ONEELEMENT
`
`SETASSOCIATED PHYSICALLOCK
`TOID(REMAININGELEMENT)
`
`68
`
`FIG 6A
`d
`
`DELETE ID(REMAININGELEMENT)
`FROM ASSOCATED DYNAMIC LIST
`
`62O
`
`622
`
`
`
`UNLOCKASSOCATED DYNAMIC
`LIST
`
`DONE
`
`624
`
`IPR2022-00600
`Apple EX1023 Page 10
`
`

`

`U.S. Patent
`
`Nov. 10, 1998
`
`Sheet 10 0f 10
`
`5,835,906
`
`THREAD 202 WISHESTO RELEASE
`CONCEPTUAL LOCK CL 322
`
`652
`
`654
`
`COMPARE AND SWAPEMPTY FLAG
`LNTO PL 420 IF CONTENT OF PL 420
`IS CL332
`
`656
`
`
`
`
`
`
`
`66 O
`
`SET LOCK-LIST FLAG 424 =
`LOCKLIST
`
`COMPARE AND SWAP EMPTYFLAG
`INTO PL 420 IF CONTENT OF PL 420
`IS CL 332
`
`SET LOCK-LIST FLAG 424 st
`UNLOCKLIST
`
`DELETECL 332 FROM DYNAMIC
`LIST 422
`
`664
`
`
`
`DOES DYNAMIC LIST 422 HAVE ONLY
`ONE CONCEPTUAL LOCKD LEFT
`
`
`
`SET CONTENT OFPL 420 TO
`ID(REMAINENG CONCEPTUAL LOCK)
`
`668
`
`DELETE ID(REMAINING
`CONCEPTUAL LOCK) FROM
`DYNAMIC LIST 422
`
`SET LOCK-LIST FLAG 424 st
`UNLOCK LIST
`
`FIG. 6B
`
`
`
`
`
`
`
`
`
`
`
`67 O
`
`672
`
`674
`
`IPR2022-00600
`Apple EX1023 Page 11
`
`

`

`1
`METHODS AND APPARATUS FOR SHARING
`STORED DATA OBJECTS IN A COMPUTER
`SYSTEM
`
`5,835,906
`
`2
`stored data objects 112,114, and 116. FIG.1C shows another
`variation wherein threads 150, 152, and 154 are executed on
`different computer systems 160, 162, and 164. Each of
`threads 150, 152, and 154 may access any of stored data
`objects 112, 114, and 116 within storage facility 110.
`If two or more threads never attempt to access on the same
`Stored data object, there may be no access conflict. When
`multiple threads wish to access the Same Stored data object,
`e.g., stored data object 112 of FIG. 1B, at the same time, the
`Simultaneous accessing of Stored data object 112 may give
`rise to erroneous results. To illustrate, consider the situation
`wherein thread 130 wishes to update the data within stored
`data object 112. If another thread 132 is allowed to access
`stored data object 112 to read therefrom while thread 130 is
`updating the content of Stored data object 112, an acceSS
`conflict may occur. This is because thread 132 may be able
`to obtain only a partially updated copy of Stored data object
`112. Because of the access conflict, thread 132 may thus
`receive erroneous data.
`In the prior art, there have been proposed a number of
`techniques for avoiding the aforementioned acceSS conflict
`problem. FIG. 2 illustrates a prior art technique for avoiding
`the access conflicts that may arise when multiple threads are
`permitted to Simultaneously access a Single Stored data
`object. Referring now to FIG. 2, there are shown multiple
`threads 202, 204, and 206, representing threads which are
`capable of accessing stored data objects 180, 182, 184, 186,
`188, and 189 in storage facility 110. To prevent access
`conflict, there is associated with each of the Stored data
`objects 180-189, a locking flag. For example, there are
`shown locking flags 190, 192,194,196, 198, and 199, which
`correspond to respective stored data objects 180, 182, 184,
`186, 188, and 189.
`When a thread, e.g., thread 202, accesses a Stored data
`object, e.g., Stored data object 180, it Sets the locking flag
`corresponding with the accessed Stored data object. In the
`case of Stored data object 180, corresponding locking flag
`190 is set when thread 202 accesses stored data object 180.
`While locking flag 190 is set, no other thread, e.g., thread
`204 or 206, may access stored data object 180. When thread
`202 completes its access, it resets locking flag 190, thereby
`permitting another thread to access stored data object 180.
`The prior art technique of avoiding access conflict works
`adequately for a relatively Small number of Stored data
`objects. However, for Systems having a large number of
`Stored data objects, e.g., in the millions, the requirement of
`a flag for every Stored data object represents a highly
`inefficient use of Storage facility resource Since millions or
`more of flags may be required for a large number of Stored
`data objects. If each flag requires, for example a byte (i.e.,
`8 bits) or a word (i.e., 32 bits) as is commonly done to
`improve the Speed at which flags can be read from or written
`to, the number of bits required to implement all the prior art
`flags may become prohibitively high. Even if each flag
`requires only one bit, Such a large number of flags
`represents, in Some Systems, an unacceptably high Storage
`facility overhead for the mere purpose of preventing access
`conflict.
`Furthermore, the number of bits per stored data object
`may be modest in Some Systems. In this case, the ratio of the
`number of bits required to implement flags to the number of
`bits employed for actual data Storage may be unacceptably
`high. This overhead ratio also tends to increase, as can be
`appreciated, as the size of the Stored data object ShrinkS.
`In view of the foregoing, what is needed are improved
`methods and apparatuses for avoiding the access conflicts
`
`BACKGROUND OF THE INVENTION
`The present invention relates to methods and apparatus
`for Sharing Stored data objects in a computer System. More
`Specifically, the present invention relates to methods and
`apparatus for permitting a plurality of processes or threads
`to efficiently and correctly access a plurality of Stored data
`objects.
`In modern computer Systems, multiple processes or
`threads may at times wish to access the same Stored data
`object for the purpose of writing to or reading from it. AS the
`terms are used herein, Software processes or threads may be
`used interchangeably and generally refer to logically distinct
`execution Streams. By way of example, multiple functions
`running concurrently are Said to be executing in different
`processes or threads.
`Generally, it is possible to execute multiple threads via a
`Single processor, multiple processors, or even multiple com
`puters in a computer network. For illustration purposes, FIG.
`1A depicts an example of a multi-propramming situation,
`wherein multiple threads are executed in a multiplexed
`manner via a processor 102. From the perspectives of the
`threads, it is as if the threads are executed in different
`processors instead of in one multiplexing processor.
`In FIG. 1A, there is shown a storage facility 110, repre
`Senting the Storage Space associated with the computer
`system of FIG. 1A for storing data. Storage facility
`(hereinafter "SF") 110 may represent, for example, any
`device or combination of devices that is capable of Storing
`data Such as Semiconductor memory, flash memory, Virtual
`memory, magnetic or optical Storage devices, or the like.
`Within storage facility 110, there are shown a plurality of
`stored data objects 112, 114, and 116. Each of stored data
`objects 112, 114, and 116 represents a unit of data Storage
`that one of threads 104,106, or 108 may wish to access to
`write to or to read from. Each stored data object may be
`Structured and arranged in any number of ways to Suit the
`particular tasks implemented by the threads. By way of
`example, if threads 104, 106, and 108 represent processes
`for manipulating data in a database, Stored data object 112
`may represent, for example, a database record that any of
`threads 104-108 can write to or read from. Of course, any
`arbitrary number of stored data objects may be provided
`within Storage facility 110. In a database, for example, there
`may be millions or more Stored data objects, representing
`records that are accessible by the threads.
`It should also be borne in mind that although the term
`“object' is used herein to describe a unit for Storing data to
`be manipulated by a thread, it is not intended that the
`invention be limited to what is commonly referred to in
`contemporary literature as “object-oriented' approaches to
`Software implementation. In fact, it is intended that the
`invention herein may be implemented using any conven
`tional programming approach, including but not limited to
`the aforementioned object-oriented approach.
`AS mentioned, multiple threads may also be implemented
`via multiple processors. FIGS. 1B and 1C depict two dif
`ferent multi-processing situations wherein multiple threads
`are executed on multiple processors (FIG. 1B) and/or mul
`tiple computer systems (FIG. 1C). In FIG. 1B, there is
`shown a computer System 120 having multiple processors
`122, 124, and 126, each of which may be executing a
`different one of threads 130, 132, and 134 for accessing
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`IPR2022-00600
`Apple EX1023 Page 12
`
`

`

`5,835,906
`
`15
`
`3
`that may arise when multiple threads attempt to access the
`Same Stored data object.
`SUMMARY OF THE INVENTION
`The invention relates, in one embodiment, to an apparatus
`in a computer System having a first plurality of Stored data
`objects and capable of running multiple threads
`concurrently, for preventing access conflicts. The acceSS
`conflicts arise when more than one of the multiple threads
`were allowed to Simultaneously access one of the first
`plurality of Stored data object.
`The apparatus includes a dynamic lock Structure having a
`plurality of dynamic lock Structure members. The plurality
`of dynamic lock Structure members are fewer in number
`than the number of the first plurality of stored data objects,
`wherein a Second plurality of Stored data objects of the first
`plurality of Stored data objects map into a first dynamic lock
`Structure member of the plurality of dynamic lock Structure
`members in accordance with a mapping function. The map
`ping function renders it likely that only one Stored data
`object of the Second plurality of Stored data objects that
`maps into the first dynamic lock Structure member is
`accessed at any given point in time by a thread of the
`multiple threads.
`There is also included a Storage facility associated with
`the first dynamic lock Structure member for Storing identities
`of a third plurality of stored data objects. The third plurality
`of Stored data objects represents a Subset of the Second
`plurality of Stored data objects that are currently being
`accessed, whereby a Stored data object having its identity
`Stored in the dynamic lock Structure cannot be accessed by
`any thread other than a thread currently accessing the Stored
`data object.
`In another embodiment, the invention relates to a method,
`in a computer System having a first plurality of Stored data
`objects and capable of running multiple threads
`concurrently, for preventing access conflicts. The method
`includes the Step of providing a dynamic lock Structure
`having a plurality of dynamic lock Structure members. There
`is also the Step of mapping a Second plurality of Stored data
`objects of the first plurality of stored data objects into a first
`dynamic lock Structure member of the plurality of dynamic
`lock Structure members in accordance with a mapping
`function. Due to the mapping function, the plurality of
`dynamic lock Structure members become fewer in number
`than the number of the first plurality of stored data objects.
`The first dynamic lock Structure member is configured to
`store identities of a third plurality of stored data objects. The
`third plurality of Stored data objects represent a Subset of the
`Second plurality of Stored data objects that are accessed,
`whereby a Stored data object having its identity Stored in the
`dynamic lock Structure cannot be accessed by any thread
`other than a thread currently accessing the Stored data object.
`These and other advantages of the present invention will
`become apparent upon reading the following detailed
`descriptions and Studying the various figures of the draw
`ings.
`
`4
`FIG. 2 illustrates a prior art technique for avoiding the
`acceSS conflicts that may arise when multiple threads are
`permitted to Simultaneously access a Single Stored data
`object.
`FIG. 3 illustrates, in accordance with one aspect of the
`present invention, the Structures employed to avoid acceSS
`conflicts.
`FIG. 4A illustrates, in greater detail and in accordance
`with one aspect of the present invention, the dynamic lock
`Structure of FIG. 3.
`FIG. 4B shows, in one example, the various parameters
`that may be present in each member of the dynamic lock
`Structure of FIG. 3.
`FIGS. 5A and 5B are flowcharts illustrating, in one
`embodiment, the steps involved when a thread wishes to
`acquire a conceptual lock to access a Stored data object.
`FIGS. 6A and 6B are flowcharts illustrating, in one
`embodiment, the steps involved when a thread wishes to
`release a conceptual lock.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`An invention is described for, among others, permitting a
`plurality of processes or threads to efficiently and correctly
`access a plurality of data objects. In the following
`description, numerous Specific details are Set forth in order
`to provide a thorough understanding of the present inven
`tion. It will be obvious, however, to one skilled in the art,
`that the present invention may be practiced without Some or
`all of these specific details. In other instances, well known
`Structures and process Steps have not been described in
`detail in order not to unnecessarily obscure the present
`invention.
`In accordance with one aspect of the present invention,
`the prior art requirement of a locking flag for every Stored
`data object is advantageously obviated. It is recognized that
`at any given point in time, the actual number of Stored data
`objects being accessed is Smaller than the total number of
`Stored data objects in a given Storage facility. Given this
`recognition, it is advantageously realized that there is no
`need to physically provide for a lock in the Storage facility
`for every Stored data object Since at any given point in time,
`a large number of Stored data objects are not accessed by any
`thread (and therefore pose no serious risk of access conflict).
`The challenge, however, is to reduce the number of lockS
`physically implemented to prevent access conflict (and
`thereby reducing the Storage facility overhead dedicated to
`this purpose) while advantageously allowing a thread to
`access a Stored data object and locks other threads out in a
`Speedy and efficient manner.
`In accordance with one aspect of the present invention,
`there are provided a plurality of physical locks for locking
`out Stored data objects are currently accessed by a thread. AS
`the term is used herein, a physical lock referS generally to a
`device actually implemented in memory, and whose imple
`mentation requires Some amount of Storage facility resource.
`The number of physical lockS provided in accordance with
`the present invention is, unlike the prior art approach of FIG.
`2, advantageously fewer in number than the number of
`available Stored data objects. For example, a System may use
`1000 physical locks to implement millions of conceptual
`locks for tracking access to millions of Stored data objects.
`Conceptually Speaking, there is still associated with every
`Stored data object a logical, or conceptual lock. Although
`there are as many conceptual locks in the present invention
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1A depicts a multi-propramming Situation, wherein
`multiple threads are executed in a multiplexed manner via a
`processor.
`FIGS. 1B and 1C depict two different multi-processing
`Situations wherein multiple threads are executed on multiple
`processors (FIG. 1B) and/or multiple computer Systems
`(FIG. 1C).
`
`60
`
`65
`
`IPR2022-00600
`Apple EX1023 Page 13
`
`

`

`5,835,906
`
`15
`
`25
`
`S
`as there are actual physical locks in the prior art for a given
`System, the conceptual locks of the present invention advan
`tageously do not require any real Storage facility resource to
`implement. Their depiction herein is intended to cast the
`invention in terms familiar to those skilled in the art, it
`should always be kept in mind that conceptual locks do not
`need to be implemented in a real world computer System.
`To further elaborate on the features and advantages of the
`present invention, reference may be made to FIG. 3. In FIG.
`3, there is shown in storage facility 110, which stores a
`plurality of stored data objects 310, 312,314, 320, 322, and
`324. A plurality of conceptual locks CL 310, CL 312,
`CL 314, CL 320, CL 322, and CL 324, which are asso
`ciated with respective stored data objects 310,312,314,320,
`322, and 324, are depicted to conceptually indicate whether
`a particular Stored data object is currently being accessed by
`a thread (and therefore attempted accesses by other threads
`should be locked out). For example, conceptual lock
`CL 310 is depicted to be in a locked state, indicating that
`a thread, e.g., thread 202, is currently accessing Stored data
`object 310 and attempted access to stored data object 310 by
`any other thread, e.g., thread 204 or 206, should be refused.
`Likewise, conceptual lock CL 314 is depicted in its locked
`State, thereby preventing access to its associated Stored data
`object 31 by any other thread except the thread currently
`accessing its corresponding Stored data object 314. On the
`other hand, conceptual locks CL 312, CL 320, CL 322,
`and CL 324 are depicted in their unlocked State, indicating
`that any of threads 202, 204, and 206 may request access to
`their associated Stored data objects and have those requests
`immediately granted.
`To keep track of the conceptual locks that are locked at
`any given point in time, there is provided, in accordance
`with one aspect of the present invention, a dynamic lock
`structure 350. The function of dynamic lock structure 350 is
`to govern access to the Stored data objects for the purpose of
`preventing acceSS conflicts. Unlike the conceptual lockS
`herein, dynamic lock structure 350 and its constituent parts
`are actually implemented memory, i.e., real physical Storage
`facility resources are actually employed in the implementa
`tion of dynamic lock structure 350. Since dynamic lock
`structure 350 is required to keep track of only the identity of
`the conceptual locks (which may represent the identity of the
`Stored data object in one embodiment) that are currently
`accessed by a thread, the total amount of Storage facility
`resource devoted to its implementation is advantageously
`Smaller compared to that required in the prior art, e.g., to the
`amount of memory required to implement the lock flags of
`prior art FIG. 2.
`As shown in FIG. 3, dynamic lock structure 350 com
`50
`prises a plurality of Structure members of which three
`members M1, M2, and M3 are shown. In accordance with
`one aspect of the present invention, there are advantageously
`fewer dynamic lock Structure members in dynamic lock
`structure 350 than there are conceptual locks. To keep the
`number of dynamic lock Structure members low, a plurality
`of conceptual locks are mapped into each dynamic lock
`Structure member in accordance to Some mapping function.
`A Suitable mapping function preferably makes it likely that
`conceptual locks in Simultaneous use map to different
`dynamic lock Structure members, while, at the same time,
`should execute quickly. Systems could, for example, Select
`bits from the middle of a stored data object's address (using,
`for example, an appropriate bit mask and shift instructions)
`or may use any conventional hash function. In the example
`of FIG. 3, all conceptual locks in the CL 310 to CL 319
`range map into dynamic lock Structure member M1 while all
`
`6
`conceptual locks in the CL 320 to CL 329 range maps
`into dynamic lock Structure member M2, and So on.
`FIGS. 4A and 4B show, in greater detail and in accordance
`with one embodiment of the present invention, a portion of
`dynamic lock Structure 350, including dynamic lock Struc
`ture members M1, M2, and M3. Within each dynamic lock
`Structure member, e.g., dynamic lock Structure member M1,
`there is shown a physical lock portion, a list-lock flag
`portion, and a dynamic list portion. In one embodiment, a
`physical lock portion includes the memory Structure for
`Storing either an identity of one of the conceptual locks that
`map into the corresponding dynamic Structure member, or a
`flag that indicates whether the dynamic list associated with
`this dynamic lock Structure member is empty. Since a
`conceptual lock exists as a concept only, it should be
`appreciated that the identity of a conceptual lock may, in one
`embodiment, be represented by the identity of its corre
`sponding Stored data object. If a Stored data object is Stored
`in memory, for example, it may be identified by its starting
`address. The flags EMPTY/NOT EMPTY that may be
`Stored in the physical lock portion may be implemented, in
`one embodiment, by a single bit, e.g., by the Zero and one
`value of one Single bit. Alternatively, it is possible to use
`other conventional lock implementations.
`With reference to dynamic lock structure member M1 of
`FIG. 4B, for example, physical lock 410 is shown storing a
`flag NOT EMPTY, which indicates that a dynamic list 412
`associated with dynamic lock structure member M1 is not
`empty. On the other hand, physical lock 430 of dynamic lock
`structure member M3 is shown storing a flag EMPTY,
`indicating that a corresponding dynamic list 432 of dynamic
`lock structure member M3 is currently empty.
`A conceptual lock that maps into a dynamic lock Structure
`member may have its identity Stored in the physical lock
`portion of that dynamic lock Structure member if it is the
`only conceptual lock among all conceptual lockS mapping to
`that dynamic lock Structure member that is currently
`accessed by a thread. By way of example, Since only
`conceptual lock CL 322 among all conceptual locks that
`map into dynamic lock Structure member M2 is currently
`accessed, the identity of conceptual lock CL 322 is pref
`erably Stored in the physical lock portion of dynamic lock
`structure member M2, i.e., physical lock portion 420. As will
`be discussed in detail later, whenever a conceptual lock
`identity can be stored in the physical lock portion of a
`dynamic lock Structure member, the invention advanta
`geously takes advantage of this fact to improve the Speed at
`which a thread can access a Stored data object and obtains or
`releases the conceptual lock.
`Each dynamic lock Structure member of dynamic lock
`structure 350 further includes a list-lock flag. The list-lock
`flag is employed to indicate whether the dynamic list asso
`ciated with that list-lock flag, i.e., belonging to the same
`dynamic lock Structure member, is accessible at a given
`point in time. In the embodiment of FIG. 4B, the list-lock
`flag may have two states, LOCK LIST and UNLOCK
`LIST, and may be implemented, in one embodiment, by a
`Single bit, e.g., by the Zero and one value of one Single bit.
`By way of example, dynamic lock structure member M1 is
`shown having a list-lock flag 414, which currently Stores the
`“LOCK LIST state, indicating that access to the corre
`sponding dynamic list 412 is currently not permitted.
`In accordance with one aspect of the present invention,
`the dynamic list portion of each dynamic lock Structure
`member contains a dynamically created list of conceptual
`lock identities. The conceptual lock identities Stored in a
`
`35
`
`40
`
`45
`
`55
`
`60
`
`65
`
`IPR2022-00600
`Apple EX1023 Page 14
`
`

`

`5,835,906
`
`15
`
`25
`
`35
`
`40
`
`7
`dynamic list represents identities of the conceptual locks that
`map into the dynamic lock Structure member corresponding
`to that dynamic list and currently “locked” because their
`asSociated Stored data objects are being accessed. In accor
`dance with one aspect of the present invention, the use of
`dynamically created lists, e.g., a linked list data Structure, to
`Store conceptual lock identities flexibly and advantageously
`minimizes Storage facility usage.
`A dynamic list may be empty, e.g., as shown in the case
`of dynamic lists 422 and 432 of dynamic lock structure
`members M2 and M3, respectively. The physical lock por
`tion associated with an empty dynamic list in a dynamic lock
`structure member may store either the identity of one of the
`conceptual locks that maps into its associated dynamic lock
`Structure member and currently locked (if the dynamic lock
`Structure members currently Stores only one conceptual lock
`identity), or the flag EMPTY if no conceptual lock identity
`is Stored in either the dynamic list portion or the physical
`lock portion of the dynamic lock Structure member. A
`physical lock Storing a conceptual lock identity and one
`storing an EMPTY flag are shown in respective physical
`lock 420 of dynamic lock structure member M2 and physical
`lock 430 of dynamic lock structure member M3.
`Alternatively, a dynamic list may contain a plurality of
`conceptual lock identities. AS mentioned earlier, when the
`dynamic lock Structure member Stores only one conceptual
`lock identity, that conceptual lock identity is preferably
`Stored in the physical lock portion of the dynamic lock
`Structure member to improve the access Speed. On the other
`hand, when the dynamic lock Structure member Stores more
`than one conceptual lock identity, i.e., the identities of the
`conceptual locks that both map into this dynamic lock
`Structure member and accessed by Some thread, all of these
`multiple conceptual lock identities are preferably Stored in
`the dynamic list portion. In this manner, the dynamic list
`portion contains either two or more conceptual lock
`identities, or none. When the dynamic list portion of a
`dynamic lock Structure member is not empty, the physical
`lock portion associated with that dynamic lock Structure
`member preferably stores the NOT EMPTY flag. With
`reference to FIG. 4, the NOT EMPTY flag is shown stored
`in physical lock 410 portion of dynamic lock structure
`member M1 when dynamic list 412 is employed to store two
`conceptual lock identities, corresponding to two stored data
`objects accessed by Some thread and mapped into dynamic
`lock structure member M1.
`The presence of flag NOT EMPTY in the physical
`portion of a dynamic lock Structure member advantageously
`directs a thread that is interested in acquiring or releasing a
`conceptual lock to look into the dynamic list. On the other
`hand, the presence of flag EMPTY in the physical portion of
`a dynamic lock Structure member advantageously indicates
`to a thread that none of the conceptual locks that map into
`this dynamic lock Structure member is currently accessed,
`i.e., an