Method and apparatus for a scheduling driver to implement a protocol utilizing time estimates for use with a device that does not generate interrupts

• US 6,795,873 B1
• Filed: 06/30/2000
• Issued: 09/21/2004
• Est. Priority Date: 06/30/2000
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Barth, David M., Nelson, Brian D.
• Primary Examiner(s): Fleming, Fritz
• Assistant Examiner(s): Casiano, Angel L.
• Application Number:
  US09/607,256
• Time in Patent Office: 1,544 Days
• Field of Search: 711/219, 710/110, 710/307, 710/5, 710/39, 710/65, 710/15, 710/45, 710/7, 710/10, 710/17, 710/18, 710/19, 710/31, 710/32, 710/33, 710/36, 710/58, 714/5, 714/47
• US Class Current: 710/15
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

The present invention provides a method and apparatus for a scheduling driver to implement a protocol using time estimates for use with a device that does not generate interrupts. An application calls the scheduling driver to start an Input/Output (I/O) request to a device. The scheduling driver determines if the device is busy. If the device is not busy, the scheduling driver provides an estimated processing time (EPT) for the I/O request to be completed to the application. In one embodiment, if the device is busy, the scheduling driver calculates an estimated amount of time left (EATL) until the device will be available to the application and provides this EATL to the application. When the device is not busy, the application sleeps for the estimated processing time (EPT) and calls the scheduling driver to obtain the I/O operation results. If the I/O request has been completed, the scheduling driver provides the I/O operation results to the application. However, if the I/O request has not been completed, the scheduling driver calculates an estimated processing time remaining (EPTR) for the I/O request to be completed and provides the EPTR to the application. The application then sleeps for the estimated processing time remaining (EPTR) and again calls the scheduling driver to obtain the I/O operation results. These operations can be repeated until the I/O request has been completed.

Claims

1. A method comprising:

calling a scheduling driver to start an Input/Output (I/O) request to a device for an application, the device being one of a plurality of different types of devices useable by an application, wherein the scheduling driver implements a protocol using time estimates enabling the scheduling driver to be usable with a device that does not generate interrupts;

determining if the device is busy; and

if the device is not bus, providing an estimated processing time (EPT) for the I/O request to be completed for the application, wherein the application sleeps for the estimated processing time.

2. The method of claim 1, wherein determining if the device is busy comprises determining whether a locked flag is set, if the locked flag is set the device is busy and if the locked flag is not set the device is not busy.

3. The method of claim 1, further comprising, setting a locked flag if the device is not busy.

4. The method of claim 1, further comprising, calling the scheduling driver to obtain I/O operation results after sleeping for the estimated processing time and determining if the I/O request has been completed.

5. The method of claim 4, further comprising, clearing a locked flag if the I/O request has been completed.

6. The method of claim 4, further comprising, providing the I/O operation results from the I/O request if the I/O request has been completed.

7. The method of claim 4, further comprising, sleeping for a timer tick interval if the I/O request has been completed.

8. The method of claim 4, further comprising, calculating an estimated processing time remaining (EPTR) for the I/O request to be completed, if the I/O request has not been completed, and providing the estimated processing time remaining (EPTR).

9. The method of claim 8, further comprising:

sleeping for the estimated processing time remaining (EPTR);

calling the scheduling driver to obtain the I/O operation results after sleeping for the estimated processing time remaining (EPTR); and

determining if the I/O request has been completed.

10. The method of claim 9, further comprising:

determining if the I/O request has been completed and calculating an estimated processing time remaining (EPTR) for the I/O request to be completed, if the I/O request has not been completed;

sleeping for the estimated processing time remaining (EPTR);

calling the scheduling driver to obtain the I/O operation results after sleeping for the estimated processing time remaining (EPTR); and

if the I/O request has not been completed,

repetitively performing the above operations until the I/O request has been completed.

11. The method of claim 1, further comprising calculating an estimated amount of time left (EATL) until the device will be available if the device is busy, and providing the estimated amount of time left (EATL).

12. The method of claim 11, further comprising:

sleeping for the estimated amount of time left (EATL);

calling the scheduling driver to start the I/O request to the device after sleeping for the estimated amount of time left (EATL); and

determining if the device is still busy.

13. The method of claim 12, further comprising:

determining if the device is still busy and calculating the estimated amount of time left (EATL) until the device will be available, if the device is still busy;

sleeping for the estimated amount of time left (EATL);

calling the scheduling driver to start the I/O request to the device for the application, after sleeping for the estimated amount of time left (EATL); and

if the I/O request has not been started,

repetitively performing the above operations until the I/O request has been started.

14. A method comprising:

calling a scheduling driver to start an Input/Output (I/O) request to a device for an application, the device being one of a plurality of different types of devices useable by an application;

determining if the device is busy; and

if the device is not busy, providing an estimated processing time (EPT) for the I/O request to be completed for the application, wherein the application sleeps for the estimated processing time;

sleeping for a timer tick interval if the I/O request has been completed;

calling the scheduling driver to obtain I/O operation results after sleeping for the estimated processing time and determining if the I/O request has been completed; and

synchronizing a system clock with a clock associated with the scheduling driver, wherein the timer tick indicates an instant where the system clock and scheduling driver clock simultaneously generate an interrupt.

15. A method comprising:

calling a scheduling driver to start an Input/Output (I/O) request to a device for an application, the device being one of a plurality of different types of devices useable by an application;

determining if the device is busy;

if the device is not busy, providing an estimated processing time (EPT) for the I/O request to be completed for the application, wherein the application sleeps for the estimated processing time; and

loading the scheduling driver into an operating system such that applications are capable of generating I/O requests to the device.

16. The method of claim 15, wherein determining if the device is busy comprises determining whether a locked flag is set, if the locked flag is set the device is busy and if the locked flag is not set the device is not busy.

17. The method of claim 15, further comprising, setting a locked flag if the device is not busy.

18. The method of claim 15, further comprising, calling the scheduling driver to obtain I/O operation results after sleeping for the estimated processing time and determining if the I/O request has been completed.

19. The method of claim 18, further comprising, clearing a locked flag if the I/O request has been completed.

20. The method of claim 18, further comprising, providing the I/O operation results from the I/O request if the I/O request has been completed.

21. The method of claim 18, further comprising, sleeping for a timer tick interval if the I/O request has been completed.

22. The method of claim 18, further comprising, calculating an estimated processing time remaining (EPTR) for the I/O request to be completed, if the I/O request has not been completed, and providing the estimated processing time remaining (EPTR).

23. The method of claim 22, further comprising:

sleeping for the estimated processing time remaining (EPTR);

calling the scheduling driver to obtain the I/O operation results after sleeping for the estimated processing time remaining (EPTR); and

determining if the I/O request has been completed.

24. The method of claim 23, further comprising:

determining if the I/O request has been completed and calculating an estimated processing time remaining (EPTR) for the I/O request to be completed, if the I/O request has not been completed;

sleeping for the estimated processing time remaining (EPTR);

calling the scheduling driver to obtain the I/O operation results after sleeping for the estimated processing time remaining (EPTR); and

if the I/O request has not been completed,

repetitively performing the above operations until the I/O request has been completed.

25. The method of claim 15, further comprising calculating an estimated amount of time left (EATL) until the device will be available if the device is busy, and providing the estimated amount of time left (EATL).

26. The method of claim 25, further comprising:

sleeping for the estimated amount of time left (EATL);

calling the scheduling driver to start the I/O request to the device after sleeping for the estimated amount of time left (EATL); and

determining if the device is still busy.

27. The method of claim 26, further comprising:

determining if the device is still busy and calculating the estimated amount of time left (EATL) until the device will be available, if the device is still busy;

sleeping for the estimated amount of time left (EATL);

calling the scheduling driver to start the I/O request to the device for the application, after sleeping for the estimated amount of time left (EATL); and

if the I/O request has not been started,

repetitively performing the above operations until the I/O request has been started.

28. The method as recited in claim 15, wherein the scheduling driver is a passive software component.

29. The method as recited in claim 15, wherein a single instance of the scheduling driver is shared among a plurality of applications that access the device.

30. A machine-readable medium having stored thereon instructions, which when executed by a machine, causes the machine to perform operations comprising:

calling a scheduling driver to start an Input/Output (I/O) request to a device for an application, the device being one of a plurality of different types useable by an application, wherein the scheduling driver implements a protocol using time estimates enabling the scheduling driver to be usable with a device that does not generate interrupts;

determining if the device is busy; and

if the device is not busy, providing an estimated processing time (EPT) for the I/O request to be completed for the application, wherein the application sleeps for the estimated processing time.

31. The machine-readable medium of claim 30, wherein determining if the device is busy comprises determining whether a locked flag is set, if the locked flag is set the device is busy and if the locked flag is not set the device is not busy.

32. The machine-readable medium of claim 30, further comprising the operation of setting a locked flag if the device is not busy.

33. The machine-readable medium of claim 30, further comprising the operations of calling the scheduling driver to obtain I/O operation results after sleeping for the estimated processing time and determining if the I/O request has been completed.

34. The machine-readable medium of claim 33, further comprising the operation of clearing a locked flag if the I/O request has been completed.

35. The machine-readable medium of claim 33, further comprising the operation of providing the I/O operation results from the I/O request if the I/O request has been completed.

36. The machine-readable medium of claim 33, further comprising the operation of sleeping for a timer tick interval if the I/O request has been completed.

37. The machine-readable medium of claim 33, further comprising the operations of calculating an estimated processing time remaining (EPTR) for the I/O request to be completed, if the I/O request has not been completed, and providing the estimated processing time remaining (EPTR).

38. The machine-readable medium of claim 33, further comprising the operations of:

sleeping for the estimated processing time remaining (EPTR);

calling the scheduling driver to obtain the I/O operation results after sleeping for the estimated processing time remaining (EPTR); and

determining if the I/O request has been completed.

39. The machine-readable medium of claim 38, further comprising performing the operations of:

determining if the I/O request has been completed and calculating an estimated processing time remaining (EPTR) for the I/O request to be completed, if the I/O request has not been completed;

sleeping for the estimated processing time remaining (EPTR);

calling the scheduling driver to obtain the I/O operation results after sleeping for the estimated processing time remaining (EPTR); and

if the I/O request has not been completed,

repetitively performing the above operations until the I/O request has been completed.

40. The machine-readable medium of claim 30, further comprising the operations of calculating an estimated amount of time left (EATL) until the device will be available if the device is busy, and providing the estimated amount of time left (EATL).

41. The machine-readable medium of claim 40, further comprising the operations of:

sleeping for the estimated amount of time left (EATL);

calling the scheduling driver to start the I/O request to the device after sleeping for the estimated amount of time left (EATL); and

determining if the device is still busy.

42. The machine-readable medium of claim 41, further comprising performing the operations of:

determining if the device is still busy and calculating the estimated amount of time left (EATL) until the device will be available, if the device is still busy;

sleeping for the estimated amount of time left (EATL);

calling the scheduling driver to start the I/O request to the device, after sleeping for the estimated amount of time left (EATL); and

if the I/O request has not been started,

repetitively performing the above operations until the I/O request has been started.

43. A method comprising:

calling a scheduling driver to start an Input/Output (I/O) request to a device for an application, the device being one of a plurality of different times of devices useable by an application;

determining if the device is busy; and

if the device is not busy, providing an estimated processing time (EPT) for the I/O request to be completed for the application, wherein the application sleeps for the estimated processing time,

where a plurality of applications simultaneously generate device I/O requests.

44. A method comprising:

calling a scheduling driver to start an Input/Output (I/O) request to a device for an application, the device being one of a plurality of different types of devices useable by an application;

determining if the device is busy;

if the device is not busy, providing an estimated processing time (EPT) for the I/O request to be completed for the application, wherein the application sleeps for the estimated processing time;

calling the scheduling driver to obtain I/O operation results after sleeping for the estimated processing time and determining if the I/O request has been completed;

sleeping for a timer tick interval if the I/O request has been completed;

specifying a zero time interval, by the driver;

sleeping for a timer tick interval, thereby yielding a time slice by the application; and

switching, by an operating system scheduler, the CPU to a next application, while allowing the application to remain runnable.

45. A method comprising:

calling a scheduling driver to start an Input/Output (I/O) request to a device for an application, the device being one of a plurality of different types of devices useable by an application;

determining if the device is busy; and

if the device is not busy, providing an estimated processing time (EPT) for the I/O request to be completed for the application, wherein the application sleeps for the estimated processing time,

wherein the scheduling driver does not poll, thereby allowing critical execution sections to be exited quickly.

46. An apparatus comprising:

a processor having a memory connected thereto, the memory storing an application, a scheduling driver, the application calling the scheduling driver to start an Input/Output (I/O) request to a device, the device being one of a plurality of different types of devices useable by an application;

the scheduling driver,

determining if a device is busy; and

if the device is not busy, providing an estimated processing time (EPT) for the I/O request to be completed for the application, wherein the application sleeps for the estimated processing time, wherein the scheduling driver implements a protocol using time estimates enabling the scheduling driver to be usable with a device that does not generate interrupts.

47. The apparatus of claim 46, wherein determining if the device is busy comprises determining whether a locked flag is set, if the locked flag is set the device is busy and if the locked flag is not set the device is not busy.

48. The apparatus of claim 46, wherein the scheduling driver sets a locked flag if the device is not busy.

49. The apparatus of claim 46, wherein the application calls the scheduling driver to obtain I/O operation results after sleeping for the estimated processing time and determines if the I/O request has been completed.

50. The apparatus of claim 49, wherein the scheduling driver clears a locked flag if the I/O request has been completed.

51. The apparatus of claim 46 wherein the scheduling driver provides the I/O operation results from the I/O request to the application if the I/O request has been completed.

52. The apparatus of claim 46 wherein the application sleeps for a timer tick interval if the I/O request has been completed.

53. The apparatus of claim 46 wherein the scheduling driver calculates an estimated processing time remaining (EPTR) for the I/O request to be completed, if the I/O request has not been completed, and provides the estimated processing time remaining (EPTR) to the application.

54. The apparatus of claim 53, wherein the application:

sleeps for the estimated processing time remaining (EPTR);

calls the scheduling driver to obtain the I/O operation results after sleeping for the estimated processing time remaining (EPTR); and

determines if the I/O request has been completed.

55. The apparatus of claim 54, wherein the application:

determines if the I/O request has been completed;

sleeps for the estimated processing time remaining (EPTR) calculated by the scheduling driver;

calls the scheduling driver to obtain the I/O operation results after sleeping for the estimated processing time remaining (EPTR); and

if the I/O request has not been completed,

repetitively performing the above operations until the I/O request has been completed.

56. The apparatus of claim 46, wherein the scheduling driver calculates an estimated amount of time left (EATL) until the device will be available to the application if the device is busy, and provides the estimated amount of time left (EATL) to the application.

57. The apparatus of claim 56, wherein the application:

sleeps for the estimated amount of time left (EATL);

calls the scheduling driver to start the I/O request to the device for the application after sleeping for the estimated amount of time left (EATL); and

determines if the device is still busy.

58. The apparatus of claim 57, wherein the application:

determines if the device is still busy;

sleeps for the estimated amount of time left (EATL) calculated by the scheduling driver;

calls the scheduling driver to start the I/O request to the device for the application, after sleeping for the estimated amount of time left (EATL); and

if the I/O request has not been started,

repetitively performing the above operations until the I/O request has been started.

59. An apparatus comprising:

a processor having a memory connected thereto, the memory storing an application, a scheduling driver, the application calling the scheduling driver to start an Input/Output (I/O) request to a device, the device being one of a plurality of different types of devices useable by an application;

the scheduling driver,

determining if a device is busy; and

if the device is not busy, providing an estimated processing time (EPT) for the I/O request to be completed for the application, wherein the application sleeps for the estimated processing time,

wherein the application sleeps for a timer tick interval if the I/O request has been completed, and

wherein a system clock is synchronized with a clock associated with the scheduling driver, wherein the timer tick indicates an instant where the system clock and scheduling driver clock simultaneously generate an interrupt.

60. An apparatus comprising:

a processor having a memory connected thereto, the memory storing an application, a scheduling driver, the application calling the scheduling driver to start an Input/Output (I/O) request to a device, the device being one of a plurality of different types of devices useable by an application;

the scheduling driver,

determining if a device is busy; and

if the device is not busy, providing an estimated processing time (EPT) for the I/O request to be completed for the application, wherein the application sleeps for the estimated processing time,

wherein the scheduling driver is loaded into an operating system such that applications are capable of generating I/O requests to the device.

61. The apparatus as recited in claim 60, wherein the scheduling driver is a passive software component.

62. The apparatus as recited in claim 60, wherein a single instance of the scheduling driver is shared among a plurality of applications that access the device.

63. The apparatus of claim 60, wherein determining if the device is busy comprises determining whether a locked flag is set, if the locked flag is set the device is busy and if the locked flag is not set the device is not busy.

64. The apparatus of claim 60, wherein the scheduling driver sets a locked flag if the device is not busy.

65. The apparatus of claim 60, wherein the application calls the scheduling driver to obtain I/O operation results after sleeping for the estimated processing time and determines if the I/O request has been completed.

66. The apparatus of claim 65, wherein the scheduling driver clears a locked flag if the I/O request has been completed.

67. The apparatus of claim 60, wherein the scheduling driver provides the I/O operation results from the I/O request to the application if the I/O request has been completed.

68. The apparatus of claim 60, wherein the application sleeps for a timer tick interval if the I/O request has been completed.

69. The apparatus of claim 60, if wherein the scheduling driver calculates an estimated processing time remaining (EPTR) for the I/O request to be completed, if the I/O request has not been completed, and provides the estimated processing time remaining (EPTR) to the application.

70. The apparatus of claim 69, wherein the application:

sleeps for the estimated processing time remaining (EPTR);

calls the scheduling driver to obtain the I/O operation results after sleeping for the estimated processing time remaining (EPTR); and

determines if the I/O request has been completed.

71. The apparatus of claim 70, wherein the application:

determines if the I/O request has been completed;

sleeps for the estimated processing time remaining (EPTR) calculated by the scheduling driver;

calls the scheduling driver to obtain the I/O operation results after sleeping for the estimated processing time remaining (EPTR); and

if the I/O request has not been completed,

repetitively performing the above operations until the I/O request has been completed.

72. The apparatus of claim 60, wherein the scheduling driver calculates an estimated amount of time left (EATL) until the device will be available to the application if the device is busy, and provides the estimated amount of time left (EATL) to the application.

73. The apparatus of claim 72, wherein the application:

sleeps for the estimated amount of time left (EATL);

calls the scheduling driver to start the I/O request to the device for the application after sleeping for the estimated amount of time left (EATL); and

determines if the device is still busy.

74. The apparatus of claim 73, wherein the application:

determines if the device is still busy;

sleeps for the estimated amount of time left (EATL) calculated by the scheduling driver;

calls the scheduling driver to start the I/O request to the device for the application, after sleeping for the estimated amount of time left (EATL); and

if the I/O request has not been started,

repetitively performing the above operations until the I/O request has been started.

75. An apparatus comprising:

a processor having a memory connected thereto, the memory storing an application, a scheduling driver, the application calling the scheduling driver to start an Input/Output (I/O) request to a device, the device being one of a plurality of different types of devices useable by an application;

the scheduling driver,

determining if a device is busy; and

if the device is not busy, providing an estimated processing time (EPT) for the I/O request to be completed for the application,

wherein the application sleeps for the estimated processing time, and

where a plurality of applications simultaneously generate device I/O requests.

76. An apparatus comprising:

a processor having a memory connected thereto, the memory storing an application, a scheduling driver, the application calling the scheduling driver to start an Input/Output (I/O) request to a device, the device being one of a plurality of different types of devices useable by an application;

the scheduling driver,

determining if a device is busy; and

if the device is not busy, providing an estimated processing time (EPT) for the I/O request to be completed for the application,

wherein the application sleeps for the estimated processing time,

wherein the application sleeps for a timer tick interval if the I/O request has been completed, and

wherein if the scheduling driver specifies a zero time interval, the application sleeps for a timer tick interval, thereby yielding a time slice by the application, and an operating system scheduler switches to a next application, while allowing the application to remain runnable.

77. An apparatus comprising:

a processor having a memory connected thereto, the memory storing an application, a scheduling driver, the application calling the scheduling driver to start an Input/Output (I/O) request to a device, the device being one of a plurality of different types of devices useable by an application;

the scheduling driver,

determining if a device is busy; and

if the device is not busy, providing an estimated processing time (EPT) for the I/O request to be completed for the application, wherein the application sleeps for the estimated processing time,

wherein the scheduling driver does not poll, thereby allowing critical execution sections to be exited quickly.