# US 12,182,635 B2 · Chained resource locking

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 12,182,635 B2
- Document ID: US12182635B2
- Status: Granted
- Kind: B2
- Application number: 17/405,457
- Filed: 2021-08-18
- Published: 2023-02-23
- Granted: 2024-12-31
- Earliest claimed: 2021-08-18
- Assignees: Micron Technology, Inc.
- Applicants: Micron Technology, Inc.
- Inventors: Patrick Estep; Tony M. Brewer
- Web page: https://patentgrep.com/patent/US12182635B2

## CPC

- G06F 9/526: {Mutual exclusion algorithms}
- G06F 9/5005: {to service a request}
- G06F 9/542: {Event management; Broadcasting; Multicasting; Notifications}
- G06F 2209/521: Atomic
- G06F 2209/548: Queue
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Devices and techniques for CHAINED RESOURCE LOCKING are described herein. Threads form a last-in-first-out (LIFO) queue on a resource lock to create a chained lock on the resource. A data store representing the lock for the resource holds the previous thread's identifier, enabling a subsequent thread to wake the previous thread using the identifier when the subsequent thread releases the lock. Generally, the thread releasing the lock need not interact with the data store, reducing contention for the data store among many threads.

## Claims

### Claim 1

A system comprising:
a memory controller configured to maintain a datastore representing a lock of a resource; and
a hybrid threading processor (HTP) configured to execute a first thread to:
obtain a lock value from the datastore;
responsive to the lock value corresponding to a thread identifier of a second thread and indicating that the resource is locked:
store the thread identifier of the second thread obtained from the lock value in the first thread;
write a second thread identifier corresponding to the first thread into the lock value in the datastore to replace the thread identifier for the second thread in the lock value; and
sleep the first thread, the thread identifier being a unique destination value for the second thread, threads of the HTP each having a different thread identifier from each other;
continue execution using the resource based on a first wake message corresponding to the resource, wherein the first wake message originated from a third thread and granted the first thread the lock without interacting with the lock value in the datastore; and
release the lock by sending a second wake message to the second thread based on the thread identifier stored in the first thread to awake the second thread to use the resource, the first thread being a link in a last-in-first-out (LIFO) chain that includes the second thread and the third thread, and wherein any thread that writes a thread identifier to the lock value does not have the lock when the thread identifier is written to the lock value.

### Claim 2 (depends on 1)

The system of claim 1, wherein contents of the datastore correspond to one of unlocked, locked, or a thread identifier, wherein contents that correspond to locked and the thread identifier indicate that the resource is locked.

### Claim 3 (depends on 2)

The system of claim 2, wherein the datastore is sixty-four bits.

### Claim 4 (depends on 3)

The system of claim 3, wherein contents of the datastore equivalent to a logical zero correspond to unlocked, the contents of the datastore equivalent to a logical one correspond to locked, and all other contents of the datastore correspond to thread identifiers.

### Claim 5 (depends on 2)

The system of claim 2, wherein the HTP is configured to execute a fourth thread to:
obtain a second value from the datastore;
determine that the second value is unlocked or locked;
perform an action based on the second value; and
release the lock.

### Claim 6 (depends on 5)

The system of claim 5, wherein the second value is unlocked, and wherein the action includes the HTP configured to execute the fourth thread to:
set the lock by changing contents of the datastore to locked; and
continue execution including using the resource based on the second value being unlocked.

### Claim 7 (depends on 5)

The system of claim 5, wherein the second value is locked, and wherein the action includes the HTP configured to execute the fourth thread to:
sleep based on the second value indicating that the resource is locked;
awaken upon receipt of a third wake message corresponding to the resource; and
continue execution including using the resource based on the third wake message.

### Claim 8 (depends on 5)

The system of claim 5, wherein, to release the lock, the HTP is configured to execute the fourth thread to obtain a current value of the datastore.

### Claim 9 (depends on 8)

The system of claim 8, wherein the HTP configured to execute the fourth thread to:
determine that the current value is locked; and
change contents of the datastore to unlocked.

### Claim 10 (depends on 8)

The system of claim 8, wherein the HTP configured to execute the fourth thread to:
determine that the current value is a second thread identifier; and
send a third wake message that includes the second thread identifier to awake another thread to use the resource.

### Claim 11 (depends on 10)

The system of claim 10, the HTP configured to execute the fourth thread to change contents of the datastore to locked.

### Claim 12 (depends on 5)

The system of claim 5, wherein, to release the lock, the HTP configured to execute the fourth thread to perform an atomic operation at the memory controller to release the lock on the memory controller to change contents of the datastore.

### Claim 13 (depends on 12)

The system of claim 12, wherein the lock value is obtained in a return value of an atomic operation to acquire the lock on the memory controller, and wherein the atomic operation sets the lock by changing the contents of the datastore to locked.

### Claim 14

An apparatus comprising:
a network interface; and
processing circuitry, in a hybrid thread processor (HTP), configured to execute a first thread to:
obtain, using the network interface, a lock value from a datastore representing a lock of a resource;
responsive to the lock value corresponding to a thread identifier of a second thread and indicating that the resource is locked:
store the thread identifier of the second thread obtained from the lock value in the first thread;
write a second thread identifier corresponding to the first thread into the lock value in the datastore to replace the thread identifier for the second thread in the lock value; and
sleep the first thread, the thread identifier being a unique destination value for the second thread, threads of the HTP each having a different thread identifier from each other;
continue execution using the resource based on a first wake message corresponding to the resource, wherein the first wake message originated from a third thread and granted the first thread the lock without interacting with the lock value in the datastore; and
release the lock by sending a second wake message, through the network interface, to the second thread based on the thread identifier stored in the first thread to awake the second thread to use the resource, the first thread being a link in a last-in-first-out (LIFO) chain that includes the second thread and the third thread, and wherein any thread that writes a thread identifier to the lock value does not have the lock when the thread identifier is written to the lock value.

### Claim 15 (depends on 14)

The apparatus of claim 14, wherein contents of the datastore correspond to one of unlocked, locked, or a thread identifier, wherein contents that correspond to locked and the thread identifier indicate that the resource is locked.

### Claim 16 (depends on 15)

The apparatus of claim 15, wherein the processing circuitry is configured to execute a fourth thread to:
obtain a second value from the datastore;
determine that the second value is unlocked or locked;
perform an action based on the second value; and
release the lock.

### Claim 17 (depends on 16)

The apparatus of claim 16, wherein the second value is unlocked, and wherein the action includes the HTP configured to execute the fourth thread to:
set the lock by changing contents of the datastore to locked; and
continue execution including using the resource based on the second value being unlocked.

### Claim 18 (depends on 16)

The apparatus of claim 16, wherein the second value is locked, and wherein the action includes the HTP configured to execute the fourth thread to:
sleep based on the second value indicating that the resource is locked;
awaken upon receipt of a third wake message corresponding to the resource; and
continue execution including using the resource based on the third wake message.

### Claim 19 (depends on 16)

The apparatus of claim 16, wherein, to release the lock, the processing circuitry is configured to execute the fourth thread to obtain a current value of the datastore.

### Claim 20 (depends on 19)

The apparatus of claim 19, wherein the processing circuitry configured to execute the fourth thread to:
determine that the current value is locked; and
change contents of the datastore to unlocked.

### Claim 21 (depends on 19)

The apparatus of claim 19, wherein the processing circuitry configured to execute the fourth thread to:
determine that the current value is a second thread identifier; and
send a third wake message that includes the second thread identifier to awake another thread to use the resource.

### Claim 22 (depends on 21)

The apparatus of claim 21, the processing circuitry configured to execute the fourth thread to change contents of the datastore to locked.

### Claim 23 (depends on 16)

The apparatus of claim 16, wherein, to release the lock, the processing circuitry configured to execute the fourth thread to perform an atomic operation at a memory controller managing the datastore to release the lock by changing contents of the datastore.

### Claim 24 (depends on 23)

The apparatus of claim 23, wherein the lock value is obtained in a return value of an atomic operation to acquire the lock on the memory controller, and wherein the atomic operation sets the lock by changing the contents of the datastore to locked.

### Claim 25

Non-transitory machine readable media including instructions that, when executed by processing circuitry, cause the processing circuitry to perform operations comprising:
obtaining, by a first thread executing in processing circuitry, a lock value from a datastore representing a lock of a resource;
responsive to the lock value corresponding to a thread identifier of a second thread and indicating that the resource is locked:
storing the thread identifier of the second thread obtained from the lock value in the first thread;
writing a second thread identifier corresponding to the first thread into the lock value in the datastore to replace the thread identifier for the second thread in the lock value; and
sleeping the first thread, the thread identifier being a unique destination value for the second thread, threads of the processing circuitry each having a different thread identifier from each other;
continuing execution of the first thread using the resource based on a first wake message corresponding to the resource, wherein the first wake message originated from a third thread and granted the first thread the lock without interacting with the lock value in the datastore; and
releasing the lock by sending a second wake message, from the first thread, to the second thread based on the thread identifier stored in the first thread to awake the second thread to use the resource, the first thread being a link in a last-in-first-out (LIFO) chain that includes the second thread and the third thread, and wherein any thread that writes a thread identifier to the lock value does not have the lock when the thread identifier is written to the lock value.

### Claim 26 (depends on 25)

The non-transitory machine readable media of claim 25, wherein contents of the datastore correspond to one of unlocked, locked, or a thread identifier, wherein contents that correspond to locked and the thread identifier indicate that the resource is locked.

### Claim 27 (depends on 26)

The non-transitory machine readable media of claim 26, wherein the operations further comprise:
obtaining a second value from the datastore by a fourth thread;
determining that the second value is unlocked or locked;
performing an action based on the second value; and
releasing the lock.

### Claim 28 (depends on 27)

The non-transitory machine readable media of claim 27, wherein the second value is unlocked, and wherein the action includes:
setting the lock by changing contents of the datastore to locked; and
continuing execution of the fourth thread including using the resource based on the second value being unlocked.

### Claim 29 (depends on 27)

The non-transitory machine readable media of claim 27, wherein releasing the lock includes performing an atomic operation to release the lock on a memory controller to change contents of the datastore, wherein the datastore is memory, and wherein the memory controller manages the memory of the datastore.