MAINTAINING I/O PRIORITY AND I/O SORTING

• US 20140195699A1
• Filed: 01/08/2013
• Published: 07/10/2014
• Est. Priority Date: 01/08/2013
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Sokol, Joseph Jr., Byom, Matthew J., Radhakrishnan, Manoj, Hoopes, Robert, Sarcone, Christopher
• Granted Patent: US 8,959,263 B2
• Time in Patent Office: Days
• US Class Current: 710/40
• CPC Class Codes: G06F 13/18 based on priority control G06F13/1605 takes precedence
• CPC Class Codes: G06F 13/30 with priority control
• CPC Class Codes: G06F 13/37 using a physical-position-dependent priority, e.g. daisy chain, round robin or token passing
• CPC Class Codes: G06F 13/372 using a time-dependent priority, e.g. individually loaded time counters or time slot

Abstract

Multiple variants of a data processing system, which maintains I/O priority from the time a process makes an I/O request until the hardware services that request, will be described. In one embodiment, a data processing system has one or more processors having one or more processor cores, which execute an operating system and one or more applications of the data processing system. The data processing system also can have one or more non-volatile memory device coupled to the one or more processors to store data of the data processing system, and one or more non-volatile memory controller coupled to the one or more processors. The one or more non-volatile memory controller enables a transfer of data to at least one non-volatile memory device, and the priority level assigned by the operating system is maintained throughout the logical data path of the data processing system.

Claims

1. A data processing system comprising:

one or more processors having one or more processor cores, to execute an operating system and one or more applications of the data processing system;

at least one non-volatile memory device coupled to the one or more processors to store data of the data processing system; and

at least one non-volatile memory controller coupled to the one or more processors and the at least one non-volatile memory device, the at least one non-volatile memory controller to enable a transfer of data to the at least one non-volatile memory device, wherein the transfer of data is responsive to a request by the one or more applications of the data processing system, wherein the transfer of data is associated with a priority level assigned by the operating system, and wherein the priority level assigned by the operating system is maintained throughout the logical data path of the data processing system.

2. The data processing system as in claim 1, wherein the priority level assigned by the operating system to a request by the one or more applications is selected from a list consisting essentially of a high, a medium, and a low priority, wherein the medium priority is superior to the high priority, and wherein the high priority is superior to both of the medium and the low priority.

3. The data processing system as in claim 2, wherein the operating system throttles the transfer of data from a second application, to preserve the input/output rate of a first application, wherein the priority of the first application is superior to the priority of the second application.

4. The data processing system as in claim 3, wherein data transfers originating from the operating system have a supervisor priority, wherein the supervisor priority is superior to all priorities assigned to the one or more applications.

5. The data processing system as in claim 1, wherein the at least one non-volatile memory device is abstracted as a block storage device, and wherein the block storage device is abstracted to the operating system by a file system, wherein the file system and the block storage device maintain the priority level assigned by the operating system.

6. The data processing system of claim 5, wherein the block storage device prioritizes the transfer of data via a system of weighted queues, wherein the weighted queues are arbitrated in a round-robin fashion, and wherein the queue members have scheduling factors including a time stamp, a weight, and a deadline.

7. The data processing system of claim 5, wherein the system enables out of order transfers of data, to provide storage access with a deterministic latency based on transfer priority.

8. The data processing system as in claim 5, wherein the at least one non-volatile memory device includes magnetic disk storage.

9. The data processing system of claim 5, wherein the at least one non-volatile memory device includes one or more cells of electrically erasable semiconductor memory.

10. The data processing system of claim 9, wherein the data processing system additionally comprises a translation abstraction layer, to abstract the electrically erasable semiconductor memory to the block storage device.

11. A non-transitory computer-readable medium with instructions stored therein, the instructions, when executed by a data processing system, cause the data processing system to perform a method to manage the input/output data rate of one or more applications on an operating system, the method comprising:

receiving a first input/output operation having a first priority, the first input/output operation being associated with at least one of the one or more applications on the operating system;

limiting the input/output rate of at least one of the one or more applications having a second priority; and

processing a second input/output operation having the second priority, wherein processing the second input operation includes maintaining the priority of the second operation until the operation is completed by the data processing system.

12. The computer-readable medium of claim 11, further comprising processing the first input/output operation before processing the second input/output operation.

13. The computer-readable medium of claim 11, wherein the priority of each operation is derived from the priority of the one of more applications associated with the operation.

14. The computer-readable medium of claim 13, further comprising:

beginning an input/output rate limiting period associated with the first priority, to limit the input/output rate for applications having the second priority, wherein beginning the input/output rate limit period is responsive to receiving the first input/output operation having the first priority; and

receiving a second input/output operation after receiving the first input/output operation, the second input/output operation having a second priority, wherein the second input/output operation is associated with at least one of the one or more applications on the operating system having the second priority.

15. The computer-readable medium of claim 14, wherein limiting the input/output rate of at least one of the one or more applications having the second priority comprises:

delaying the processing of the second input/output operation for a period of time, to limit the input/output rate of the at least one of the one or more applications having the second priority, wherein the second input/output operation is associated with the at least one or more of the applications having the second priority.

16. The computer-readable medium of claim 14, further comprising determining if an input/output rate limit period associated with the first priority is active before beginning the input/output data rate limit period associated with the first priority.

17. The computer readable medium of claim 16, further comprising ending the input/output rate limit period associated with the first priority if a period of time has elapsed since receiving any input/output operation having the first priority.

18. The computer readable medium of claim 17, further comprising receiving a third input/output operation, the third operation having the first priority, while the input/output rate limit period associated with the first priority is active, and extending the input/output rate limit period associated with the first priority.

19. The computer readable medium of claim 14, further comprising beginning an input/output rate limit period associated with the second priority, to limit the input/output rate of at least one of the one or more applications, wherein the at least one of the one or more applications has a third priority.

20. The computer-readable medium of claim 19, further comprising limiting the input/output rate of at least one of the one or more applications having the third priority.

21. A computer implemented method comprising:

receiving a first input/output operation, the first input/output operation having a first priority, wherein the first input/output operation is associated with at least one of the one or more applications on the operating system;

beginning an input/output data rate limit period associated with the first priority, to reduce the input/output data rate for operations having a second priority, wherein the beginning of the input/output data rate limit period is contemporaneous with the receiving of the first input/output operation;

receiving a second input/output operation after receiving the first input/output operation, the second input/output operation having a second priority, wherein the second input/output operation is associated with at least one of the one or more applications on the operating system;

delaying the processing of the second input/output operation for a period of time, to limit the input/output data rate of the at least one of the one or more applications associated with the second operation, wherein the at least one or more of the applications associated with the second operation has the second priority;

processing the second input/output operation, wherein processing the second input operation maintains the assigned priority until the operation is completed.

22. The method of claim 21, further comprising processing the first input/output operation before processing the second input/output operation.

23. The method of claim 22, wherein the priority of each operation is derived from the priority of the one of more applications associated with the operation.

24. The method of claim 23, further comprising beginning an input/output rate limit period associated with the second priority after receiving the second input operation, to limit the input/output rate for an operation having a third priority, and limiting the input/output rate of at least one of the one or more applications having the third priority.

25. The method of claim 24, further comprising determining if an input/output rate limit period associated with the second priority is active before beginning the input/output data rate limit period associated with the second priority.

26. The method of claim 25, further comprising ending the input/output rate limit period associated with the second priority after a time period has elapsed.

27. The method of claim 26, further comprising receiving a third input/output operation, during the input/output rate limit period associated with the second priority, and extending the input/output rate limit period associated with the second priority.

28. A non-transitory computer-readable medium with instructions stored therein, the instructions, when executed by a data processing system, cause the data processing system to perform operations to manage the input/output data rate of one or more applications on an operating system, the operations comprising the method according to claim 21.

29. A non-transitory computer-readable medium with instructions stored therein, the instructions, when executed by a data processing system, cause the data processing system to perform operations to manage the input/output data rate of one or more applications on an operating system, the operations comprising the method according to claim 27.

30. A non-transitory computer-readable medium with instructions stored therein, the instructions, when executed by a data processing system, cause the data processing system to perform a method of processing one or more input/output operations having a timestamp and a priority level, the method comprising:

adding an input/output operation to a queue based on the priority level of the input/output operation, wherein the queue has a weight assigned by the data processing system;

determining a deadline of the input/output operation by adding the timestamp of the input/output operation to the weight of the queue;

determining if the deadline of one or more input/output operations has expired by comparing the deadline of the one or more input/output operations to a reference time;

and processing at least one of the operations with an expired deadline, wherein the processing maintains the assigned priority until the operation is completed by the data processing system.

31. The computer-readable medium of claim 30, further comprising:

receiving an input/output operation with a priority level assigned by the data processing system.

32. The computer-readable medium of claim 30, wherein the reference time is determined by a system clock of the data processing system.

33. The computer-readable medium of claim 30, wherein the reference time is determined by a reference clock external to the data processing system.

34. The computer readable medium of claim 30, further comprising selecting an additional queue to process based on round-robin arbitration.