Using request service time as fairness heuristic in locking techniques

Patent metadata

Field	Value
Publication number	US-9619286-B1
Application number	US-201414220391-A
Country	US
Kind code	B1
Filing date	Mar 20, 2014
Priority date	Mar 20, 2014
Publication date	Apr 11, 2017
Grant date	Apr 11, 2017

Abstract

Techniques for processing requests are described. A first thread is selected for execution. Only a single thread is allowed to execute at a time. Each thread is associated with a queue of requests to be processed by the thread. A first request is selected from the queue of first thread that performs first processing to service the first request. A service time classification for the first request is determined in accordance with criteria that includes a runtime determination of what resource(s) are used in servicing the first request. It is determined, in accordance with the service time classification, whether to allow the first thread to continue execution and process a second request from the queue of the first thread. If the first thread is allowed to continue execution, second processing is performed by the first thread to service the second request. Otherwise, a second thread is selected for execution.

First claim

What is claimed is:

1. A method of processing requests comprising:
selecting a first thread of a plurality of threads for execution at a first point in time, wherein only a single one of the plurality of threads is allowed to execute at a time and wherein each of the plurality of threads is associated with one of a plurality of queues of thread-specific requests to be processed by said each thread;
selecting a first request from the one queue of requests associated with the first thread;
performing first processing by the first thread to service the first request;
determining, in accordance with one or more criteria, a service time classification for the first request, wherein said one or more criteria include a runtime determination of what one or more resources were used by said first processing in servicing the first request, wherein said determining the service time classification of the first request is performed after the first thread has completed servicing the first request and at runtime during execution of the first thread;
determining, in accordance with the service time classification, whether to allow the first thread to continue execution and process a second request from the one queue of requests associated with the first thread;
if it is determined in accordance with the service time classification to allow the first thread to continue execution, performing second processing by the first thread to service the second request, and otherwise, selecting a second of the plurality of threads for execution;
determining a number of requests the first thread has processed since commencing execution at the first point in time;
determining whether the number of requests exceeds a maximum number of requests; and
if it is determined that the number of requests exceeds the maximum number of requests, selecting another one of the plurality of threads for execution rather than the first thread, and otherwise allowing the first thread to continue execution processing another request from the one queue of requests associated with the first thread.

2. The method of claim 1 , wherein the service time classification is determined without measuring an actual amount of time that has elapsed since said first thread commenced execution at the first point in time.

3. The method of claim 1 , wherein the one or more criteria include a runtime determination as to whether said first processing issued an I/O request to a storage device in connection with servicing the first request.

4. The method of claim 3 , wherein if the first processing issued an I/O request to a storage device in connection with servicing the first request, the service time classification is a first value denoting a first estimated service time for servicing the first request whereby the first estimated service time is greater than or equal to a first amount of time.

5. The method of claim 4 , wherein the one or more criteria include a runtime determination as to whether said first processing only used a memory resource in connection with servicing the first request.

6. The method of claim 5 , wherein if the first processing only uses a memory resource in connection with servicing the first request, the service time classification is a second value denoting a second estimated service time for servicing the first request whereby the second estimated service time is less than a first amount of time.

7. The method of claim 6 , wherein if the service time classification is the second value, the first thread is allowed to continue execution.

8. The method of claim 6 , wherein if the service time classification is the first value, the first thread is not allowed to continue execution and enters a waiting state, and wherein the second thread is selected for execution.

9. The method of claim 1 , wherein a lock is used to enforce a processing requirement that only a single one of the plurality of threads is allowed to execute at a time whereby, prior to said single one of the plurality of threads servicing any request, said single one of the plurality of threads acquires the lock.

10. The method of claim 9 , wherein, prior to said first thread servicing any request after commencing execution at the first point in time, the first thread acquires the lock.

11. The method of claim 10 , wherein if it is determined in accordance with the service time classification not to allow the first thread to continue execution, the method further includes:
releasing the lock by the first thread, wherein after said releasing, the first thread waits to reacquire the lock and to be scheduled again for execution; and
responsive to said releasing, acquiring the lock by the second thread and commencing execution of the second thread, wherein the second thread acquires the lock prior to said second thread servicing any request.

12. The method of claim 1 , wherein the plurality of threads process requests in a data storage system.

13. The method of claim 1 , wherein requests in each of the plurality of queues of requests are processed on a first-in-first-out basis by a corresponding one of the plurality of threads associated with said each queue.

14. A computer readable medium comprising code stored thereon that processes requests, wherein the computer readable medium comprises code, that when executed by a processor, performs a method comprising:
selecting a first thread of a plurality of threads for execution at a first point in time, wherein only a single one of the plurality of threads is allowed to execute at a time and wherein each of the plurality of threads is associated with one of a plurality of queues of thread-specific requests to be processed by said each thread;
selecting a first request from the one queue of requests associated with the first thread;
performing first processing by the first thread to service the first request;
determining, in accordance with one or more criteria, a service time classification for the first request, wherein said one or more criteria include a runtime determination of what one or more resources were used by said first processing in servicing the first request, wherein said determining the service time classification of the first request is performed after the first thread has completed servicing the first request and at runtime during execution of the first thread;
determining, in accordance with the service time classification, whether to allow the first thread to continue execution and process a second request from the one queue of requests associated with the first thread;
if it is determined in accordance with the service time classification to allow the first thread to continue execution, performing second processing by the first thread to service the second request, and otherwise, selecting a second of the plurality of threads for execution;
determining a number of requests the first thread has processed since commencing execution at the first point in time;
determining whether the number of requests exceeds a maximum number of requests; and
if it is determined that the number of requests exceeds the maximum number of requests, selecting another one of the plurality of threads for execution rather than the first thread, and otherwise allowing the first thread to continue execution processing another request from the one queue of requests associated with the first thread.

15. The computer readable medium of claim 14 , wherein the service time classification is determined without measuring an actual amount of time that has elapsed since said first thread commenced execution at the first point in time.

16. The c

Assignees

• Emc Corp
• Emc Ip Holding Co Llc

Inventors

• Wagner Michael P
• Haase David
• Bailey Charles C
• Brundage Michael C
• Taylor Alan L
• Chen Chung-Huy
• Duprey Dennis T

Classifications

• G06F9/5011 Primary

  the resources being hardware resources other than CPUs, Servers and Terminals · CPC title

• G06F2209/485

  Resource constraint · CPC title

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title