NON-BLOCKING FLOW CONTROL IN MULTI-PROCESSING-ENTITY SYSTEMS

• US 20170351441A1
• Filed: 06/06/2016
• Published: 12/07/2017
• Est. Priority Date: 06/06/2016
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Marinescu, Adrian
• Granted Patent: US 11,301,142 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals

Abstract

The current document is directed to an efficient and non-blocking mechanism for flow control within a multi-processor or multi-core processor with hierarchical memory caches. Traditionally, a centralized shared-computational-resource access pool, accessed using a locking operation, is used to control access to a shared computational resource within a multi-processor system or multi-core processor. The efficient and non-blocking mechanism for flow control, to which the current document is directed, distributes local shared-computational-resource access pools to each core of a multi-core processor and/or to each processor of a multi-processor system, avoiding significant computational overheads associated with cache-controller contention-control for a traditional, centralized access pool and associated with use of locking operations for access to the access pool.

Claims

1. A flow-control component of a multi-processing-entity computer system, the flow-control component comprising:

a shared computational resource;

two or more local access pools, together comprising a distributed access pool, each local access pool uniquely associated with a processing entity; and

a process or thread that accesses the shared computational resource when a local access pool associated with the processing entity on which the process or thread executes contains at least one shared-computational-resource access, and is therefore not exhausted, and when the process or thread first removes a shared-computational-resource access from the local access pool before accessing the shared computational resource.

2. The flow-control component of claim 1 wherein the shared computational resource is a computer-system component with an electronic interface through which a process or thread may conduct an electronic transaction selected from among:

receiving data for the computational resource;

transmitting data to the computational resource; and

issuing commands to the computational resource.

3. The flow-control component of claim 2 wherein computational resources include:

I/O devices;

networking devices;

data-storage devices; and

processor-controlled devices.

4. The flow-control component of claim 1 wherein each local access pool maintains a count, having a value stored in a main memory, that represents the number of shared-computational-resource accesses contained in the access pool.

5. The flow-control component of claim 4 wherein only the local cache of the processing entity associated with the local access pool contains a copy of the count maintained by the local access pool.

6. The flow-control component of claim 4 wherein a process or thread removes a shared-computational-resource access from a local access pool, a copy of the count of which is stored in the local cache of a processing entity on which the process or thread is executing, by carrying out an atomic operation that returns a value stored in the count maintained by the local access pool at the start of the atomic operation and that changes the value stored in the count maintained by the local access pool.

7. The flow-control component of claim 6 wherein the atomic operation changes the value of the count by one of:

decrementing the value stored in the count;

incrementing the value stored in the count;

adding a value other than one to the value stored in the count; and

subtracting a value other than one from the value stored in the count.

8. The flow-control component of claim 6 wherein the atomic operation is an atomic increment instruction.

9. The flow-control component of claim 4 wherein, when the count falls below 1, the flow-control component attempts to transfer shared-computational-resource accesses from one or more processing entities other than the processing entity on which the process or thread executes.

11. The method of claim 1 wherein the shared computational resource is a computer-system component with an electronic interface through which a process or thread may conduct an electronic transaction selected from among:

receiving data for the computational resource;

transmitting data to the computational resource; and

issuing commands to the computational resource.

12. The method of claim 11 wherein computational resources include:

I/O devices;

networking devices;

data-storage devices; and

processor-controlled devices.

13. The method of claim 11 wherein each local access pool maintains a count, having a value stored in a main memory that represents the number of shared-computational-resource accesses contained in the access pool.

14. The method of claim 13 wherein only the local cache of the processing entity associated with the local access pool contains a copy of the count maintained by the local access pool.

15. The method of claim 13 wherein a process or thread removes a shared-computational-resource access from a local access pool, a copy of the count of which is stored in the local cache of a processing entity on which the process or thread is executing, by carrying out an atomic operation that returns a value stored in the count maintained by the local access pool at the start of the atomic operation and that changes the value stored in the count maintained by the local access pool.

16. The method of claim 15 wherein the atomic operation changes the value of the count by one of:

decrementing the value stored in the count;

incrementing the value stored in the count;

adding a value other than one to the value stored in the count; and

subtracting a value other than one from the value stored in the count.

17. The method of claim 15 wherein the atomic operation is an atomic increment instruction.

18. The method of claim 13 wherein, when the count falls below 1, the flow-control component attempts to transfer shared-computational-resource accesses from one or more processing entities other than the processing entity on which the process or thread executes.

10. A method that controls a rate of access to a shared computational resource in a multi-processing-entity computer system, the method comprising:

initializing a distributed access pool comprising two or more local access pools, each uniquely associated with a processing entity, to contain a number of shared-computational-resource accesses distributed among the local access pools; and

removing, by a process or thread, a shared-computational-resource access from a local access pool associated with a processing entity on which the process or thread executes prior to accessing the shared-computational-resource

19. Computer instructions, stored within a data-storage component of a multi-processing-entity computer system, that, when executed by the processing entities, control the multi-processing-entity computer system to controls a rate of access to a shared computational resource by:

initializing a distributed access pool comprising two or more local access pools, each uniquely associated with a processing entity, to contain a number of shared-computational-resource accesses distributed among the local access pools; and

removing, by a process or thread, a shared-computational-resource access from a local access pool associated with a processing entity on which the process or thread executes prior to accessing the shared-computational-resource.

20. The computer instructions of claim 19

wherein the shared computational resource is a computer-system component with an electronic interface through which a process or thread may conduct an electronic transaction selected from among

receiving data for the computational resource,

transmitting data to the computational resource, and

issuing commands to the computational resource;

and

wherein computational resources include

I/O devices,

networking devices,

data-storage devices, and

processor-controlled devices.