Fair and dynamic disk input/output bandwidth distribution

BACKGROUND

Disk input/output (IO) refers to the interactions of software applications with a hardware data storage device such as a hard drive. Disk IO enables software applications to store and retrieve data to and from the hardware data storage device. In a computing system, the hardware data storage device typically receives a plurality of disk IO requests from various software applications. Disk IO scheduling mechanisms are implemented so that the hardware data storage device may respond to each of the disk IO requests.

Current disk IO scheduling mechanisms are generally based on disk IO bandwidth reservation or priority queues. For example, disk IO requests may be queued by a disk IO manager of an operating system in the order that they are received, and then execute sequentially. In other examples, the disk IO manager may queue and execute each of the received disk IO requests according to priority.

These disk IO mechanisms may fall short of providing fair disk IO response to all users in a multi-user environment where a plurality of users are access data stored on the same hardware data storage device. For instance, a first user may use more software applications than a second user, resulting in more disk IO bandwidth being devoted to the first user than the second user. In scenarios where some users are using significantly more software applications than other users, such imbalance in disk IO bandwidth distribution may cause poor computing experience for those users that are receiving inadequate disk IO bandwidth.

SUMMARY

This Summary is provided to introduce a selection of concepts in a simplified form that is further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

Described herein are embodiments of various technologies for implementing fair and dynamic distribution of disk input/output (IO) bandwidth to users in a multi-user environment. In at least one embodiment, the method includes organizing one or more disk IO requests into one or more queues. The method further includes allocating a disk IO time interval to each queue. The allocation of a disk IO time interval to each queue is accomplished by equally distributing a disk IO cycle based on the number of queues. The one or more disk IO requests are then processed during the corresponding disk IO time interval.

In another embodiment, a computer readable medium having computer-executable instructions that, when executed, perform acts that include organizing one or more disk IO requests into one or more queues. The acts also include allocating a disk IO time interval to each queue. The allocation of a disk IO time interval to each queue is accomplished by equally, or substantially equally, distributing a disk IO cycle based on a quantity of the one or more queues. The acts further comprise dividing the disk IO time interval allocated to each queue into identical time slices. The duration of a disk IO time slice in each of the queues being identical. The acts additionally include providing one or more additional portions of the disk IO cycle to a first queue that has consumed its corresponding time interval. In a further embodiment, the acts also comprise processing the one or more disk IO requests in each queue for a corresponding second time slice.

In an additional embodiment, a system for dynamically distributing disk IO bandwidth to multiple queues comprises one or more processors. The system also comprises memory to store a plurality of computer-executable instructions that are executable by the one or more processors. The computer-executable instructions comprise instructions for organizing one or more disk IO requests into one or more queues based on at least one criterion. The computer-executable instructions also comprise instructions for allocating a corresponding disk IO time interval to each queue. The allocation of a disk IO time interval to each queue is accomplished by equally distributing a disk IO cycle based on a quantity of the one or more queues. The computer-readable instructions further comprise instructions for processing the one or more disk IO requests in each queue during the corresponding disk IO time interval. Other embodiments will become more apparent from the following detailed description when taken in conjunction with the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

The detailed description is described with reference to the accompanying figures. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. The use of the same reference number in different figures indicates similar or identical items.

<figref idrefs="DRAWINGS">FIG. 1</figref> is a block diagram illustrating an exemplary scheme for organizing processes into queues for fair and dynamic disk input/output (IO) bandwidth allocation.

<figref idrefs="DRAWINGS">FIG. 2</figref> is a block diagram illustrating selected components of an exemplary disk IO scheduler that is configured to provide disk input/output (IO) bandwidth to each queue, in accordance with at least one embodiment.

<figref idrefs="DRAWINGS">FIG. 3</figref> is a block diagram illustrating the fair provision of input/output (IO) in a disk IO cycle to a plurality of queues, as well as the dynamically adjustment of the disk IO bandwidth provided to each queue, in accordance with at least one embodiment.

<figref idrefs="DRAWINGS">FIG. 4</figref> illustrates the dynamic allocation of a disk input/output (IO) cycle using time intervals in conjunction with priority designation, in accordance with at least one embodiment.

<figref idrefs="DRAWINGS">FIG. 5</figref> is a flow diagram illustrating an exemplary process for the fair and dynamic provision of a disk input/output (IO) cycle to each queue, as well as dynamically adjusts the disk IO bandwidth provided to each queue, in accordance with ant least one embodiment.

<figref idrefs="DRAWINGS">FIG. 6</figref> is a flow diagram illustrating an exemplary process for the dynamic distribution of a disk input/output (IO) cycle to each of a plurality of queues in multiple time slices, in accordance with at least one embodiment.

<figref idrefs="DRAWINGS">FIG. 7</figref> is a block diagram illustrating a representative computing environment, in accordance with at least one embodiment.

DETAILED DESCRIPTION

This disclosure is directed to systems and methods that facilitate fair and dynamic distribution of disk input/output (IO) bandwidth each of a plurality of queues. Specifically, the embodiments in this disclosure are directed to allocating disk IO bandwidth equally to each queue, or some other grouping of disk IO requests, rather than to each disk IO request. It will be appreciated that a least a portion of a disk IO bandwidth in a disk IO cycle is generally reserved for operating system functionalities. Accordingly, as used herein, the disk IO bandwidth refers to an available disk IO bandwidth that is not used for system functionalities. For instance, the disk IO bandwidth may be around approximately 70% of a total disk IO bandwidth.

The embodiments in this disclosure are also directed toward dynamically allocating disk IO bandwidth based on the number of queues. In this way, embodiments described herein may ensure a distribution of disk IO bandwidth that does not cause application hesitations or slow downs that negatively impact users in a multi-user environment. Various examples of facilitating fair and/or dynamic distribution of disk IO bandwidth for all users in a multi-user environment are described below with reference to <figref idrefs="DRAWINGS">FIGS. 1-7</figref>.

Exemplary Grouping Scheme

<figref idrefs="DRAWINGS">FIG. 1</figref> illustrates an exemplary scheme for organizing disk input/output (IO) requests into queues according to a classification criterion, in accordance with at least one embodiment of fair and dynamic disk IO bandwidth distribution. The organization of disk IO requests into queues, in accordance one or more embodiments of fair and dynamic disk IO bandwidth distribution, may alleviate impaired performances that cause degraded user experiences. In an exemplary embodiment, disk IO requests may be formed into queues according to the users they serve. For example, a user <b>102</b>, such as an employee of a company, may be using at least one software application that employs disk IO requests <b>104</b>. The disk IO requests <b>104</b> are organized into a queue <b>106</b>. Moreover, a user <b>108</b> may be using at least one software application that employs a disk IO request <b>110</b>. The disk IO request <b>110</b> is organized into a queue <b>112</b>. Likewise, a user <b>114</b> may be using at least one application that employs a plurality of disk IO requests <b>116</b> (which may not be as numerous as the disk IO requests <b>104</b>). The disk IO requests <b>116</b> are organized into queue <b>118</b>.

A disk IO cycle, such as the disk IO cycle <b>120</b>, may then be divided into disk IO time intervals that reflect the number of queues. In this way, each queue receives an equal share, or a substantially equal share, of the disk IO cycle regardless of the number of disk IO requests in the queue. For example, the disk IO cycle may be allocated into time intervals <b>122</b>, <b>124</b> and <b>126</b> to equally distribute the processing time of the disk IO cycle <b>120</b> to the organized queues <b>106</b>, <b>112</b>, and <b>118</b>. Accordingly, disk IO queue <b>112</b> is configured to receive the same or substantially equivalent amount of disk IO bandwidth as queues <b>106</b> and <b>118</b>, even though queue <b>112</b> includes only disk IO request <b>110</b> while queues <b>106</b> and <b>118</b> each include multiple disk IO requests <b>104</b> and <b>116</b>, respectively. Thus, the equal or substantially equal distribution of disk IO bandwidth to each queue, wherein each queue includes different number of disk IO requests, may ensure that each queue is provided with adequate disk IO bandwidth so that a user does not experience hesitation or delay of the applications. In embodiments where the software applications are running in a WINDOWS® operating system, the disk IO requests may be contained in IO request packets (IRPs). Accordingly, IRPs may be treated in the same fashion as disk IO requests in those embodiments.

It will be appreciated that while the embodiment above describes the grouping of disk IO requests according to the users they service, disk IO requests may also be grouped according to other classification criteria. For instance, in some embodiments, the processes may be organized so that disk IO requests that act on multimedia content are in a first queue, while disk IO requests that do not act on media content are in a second queue. Other embodiments may include queue organizations based on other classification criteria, so long as the disk IO requests are organized into distinct queues.

Exemplary Disk IO Scheduler

<figref idrefs="DRAWINGS">FIG. 2</figref> is a block diagram illustrating selected components of an exemplary disk IO scheduler <b>200</b> that is configured to provide disk input/output (IO) bandwidth to each queue, in accordance with at least one embodiment of fair and dynamic disk IO bandwidth distribution. The exemplary disk IO scheduler <b>200</b> may include computer program instructions that are executed by a computing device, such as the device <b>700</b> described in <figref idrefs="DRAWINGS">FIG. 7</figref>. Program instructions, or modules, may include routines, programs, objects, components, and data structures that perform particular tasks or implement particular abstract data types. The selected components of the disk IO scheduler <b>200</b> include, but are not limited to, a cycle distribution module <b>202</b>, a queue determination module <b>204</b>, a dynamic execution module <b>206</b>, and a user interface application program interface (API) module <b>208</b>.

The cycle distribution module <b>202</b> may be configured to distribute a disk IO cycle equally, or substantially equally, among a plurality of queues that need disk IO bandwidth. Each queue may include a different number of disk IO requests. For example, if t represents the time in a disk IO cycle and n represents the number of queues, the cycle distribution module <b>202</b> is configured to allocate the disk IO cycle t into n time intervals such that each time interval has a duration of t/n. The cycle distribution module <b>202</b> may also work cooperatively with the queue determination module <b>204</b>.

The queue determination module <b>204</b> may be configured to calculate the number of queues that need disk IO bandwidth in a given disk IO cycle. In one example, this calculation may be performed based on the actual disk IO usage in a previous cycle. According to various embodiments, the queue determination module <b>204</b> may perform this calculation by taking into consideration any increase or reduction in the queues of disk IO requests. Once the queue determination module <b>204</b> has determined the number of queues that need disk IO bandwidth, the queue determination module <b>204</b> may return this information to the cycle distribution module <b>202</b>.

In turn, the cycle distribution module <b>202</b> may reallocate the disk IO cycle to accommodate the change in the number of queues. For example, if t represents the time in a disk IO cycle, n represents the number of queues processed in a disk IO cycle, and the number of queues that need disk IO bandwidth in a subsequent disk IO cycle has increased by one, the cycle distribution module <b>202</b> may reallocate the disk IO cycle t into n+1 queues, such that each time interval has a duration of t/(n+1). Likewise, if the queue determination module <b>204</b> calculates that the number of queues that need disk IO bandwidth in a subsequent disk IO cycle has decreased by one, then the cycle distribution module <b>202</b> reallocate the disk IO cycle such that each time interval has a duration of t/(n−1).

Furthermore, the cycle distribution module <b>202</b> may be configured to divide a particular allocated disk IO time interval into a plurality of time slices. The division of a disk IO time interval may enable each queue to receive the disk IO bandwidth more frequently during a specific disk IO cycle. As further described below, the cycle distribution module <b>202</b> may also adjust the time slices during a disk IO cycle to accommodate disk IO requests from new queues.

The dynamic execution module <b>206</b> may be configured to command a disk manager (not shown) to sequentially fulfill the disk IO requests of each queue during the time interval determined by the cycle distribution module <b>202</b>. For instance, the dynamic execution module <b>206</b> may direct the disk manager to fulfill the disk IO requests of a first queue for the allocated time interval of a disk IO cycle. Once the allocated time interval has ended, the dynamic execution module <b>206</b> may command the disk manager to terminate the processing of the disk IO requests in the first queue and perform a processing of the disk IO requests in the second queue for the allocated time interval, and so on and so forth until the disk IO cycle is complete. The dynamic execution module <b>206</b> may then repeat the processing for the next disk IO cycle.

The user interface API module <b>208</b> may include an API that enables a user to interact with the disk IO scheduler <b>200</b> via a user interface <b>210</b>. For example, the user interface API module <b>208</b>, in conjunction with user interface <b>210</b>, may provide the user with the ability to change the criterion for the organization of disk IO requests into queues. The user interface <b>210</b> may include, but is not limited to, combinations of one or more of keypads, keyboards, mouse devices, touch screens, microphones, speech recognition packages, and other suitable devices or other electronic/software selection methods.

Exemplary Dynamic Disk IO Bandwidth Allocation

<figref idrefs="DRAWINGS">FIG. 3</figref> is a block diagram illustrating the fair provision of input/output (IO) in a disk IO cycle to a plurality of queues, as well as the dynamic adjustment of the disk IO bandwidth provided to each queue, in accordance with at least one embodiment.

In embodiments where the disk IO cycles are serving a multi-user environment, the disk IO cycles, such as a disk IO cycle <b>300</b>A, may be approximately, e.g., 120-150 milliseconds (ms) in duration. In contrast, disk IO cycles longer than 150 ms may cause a perception of delay to users in the multi-user environment.

In one instance, the disk IO scheduler <b>200</b> (<figref idrefs="DRAWINGS">FIG. 2</figref>) may be configured to allocate the disk IO cycle <b>300</b>A into equal, or substantially equal disk IO time intervals <b>302</b>-<b>308</b> for the corresponding queues <b>310</b>-<b>316</b>. The time intervals <b>302</b>-<b>308</b> are identical, or substantially identical, in duration. For example, if the duration of the disk IO cycle <b>300</b>A is approximately 120 ms, the disk IO scheduler <b>200</b> may allocate the time intervals <b>302</b>-<b>308</b> so that each is approximately 30 ms. Each of the queues <b>310</b>-<b>316</b> may include different number of disk IO requests.

During the exemplary disk IO cycle <b>300</b>A, the disk IO scheduler <b>200</b> may first provide disk IO bandwidth to the queue <b>310</b> for the duration of the time interval <b>302</b>. During the duration of the time interval <b>302</b>, the disk manager may process disk IO requests in the queue <b>310</b>. The processing of the disk IO requests includes at least one of transferring data to and from a hardware data storage device based on each of the disk IO requests. At the end of the time interval <b>302</b>, the disk IO scheduler <b>200</b> may command the disk manager to terminate the processing of the disk IO requests in the queue.

Subsequently, the disk IO scheduler <b>200</b> may provide disk IO bandwidth to the queue <b>312</b> for the time interval <b>304</b>, before terminating the processing of the disk IO requests in the queue <b>312</b> when the time interval <b>304</b> expires. Likewise, the disk IO scheduler <b>200</b> may then provide disk IO bandwidth to the queue <b>314</b> for duration of the time interval <b>306</b>, and to the queue <b>316</b> for the duration of the time interval <b>308</b>. The end of the time interval <b>308</b> coincides with the conclusion of the disk IO cycle <b>300</b>A. Subsequently, the disk IO scheduler <b>200</b> may initiate a new disk IO cycle. It will be appreciated that disk IO cycle <b>300</b>A is meant to be illustrative rather than limiting. Thus, in various other embodiments, any number of queues may be processed in a disk IO cycle, and the number of equally, or substantially equal allocated time intervals is directly related to the number of queues being processed.

The ability of the disk IO scheduler <b>200</b> to further divide the time intervals <b>302</b>-<b>308</b> into time slices is illustrated with respect to the exemplary disk IO cycle <b>300</b>B. The disk IO cycle has the same duration as the disk IO cycle <b>300</b>A. As shown, the disk IO scheduler <b>200</b> may divide each of the time intervals <b>302</b>-<b>308</b> into a plurality of time slices. Specifically, the disk IO scheduler <b>200</b> may divide the time interval <b>302</b> into equal, or substantially equal, time slices <b>302</b>A-<b>302</b>C. Likewise, the disk IO scheduler <b>200</b> may divide the time interval <b>304</b>-<b>308</b> into respective time slices.

For example, when the duration of the disk IO cycle <b>300</b>B is approximately 120 ms, and each of the time intervals <b>302</b>-<b>308</b> is 30 seconds, time interval <b>302</b> may be further divided into thirds to create time slices that are 10 ms in duration. Moreover, the disk IO scheduler <b>200</b> may divide each of the other time intervals into the same number of slices. Accordingly, as shown, the disk IO scheduler <b>200</b> may similarly divide each of the time intervals <b>304</b>-<b>308</b> into three 10 ms time slices.

The disk IO scheduler <b>200</b> may be further configured to use the time slices of each time interval fairly during the disk IO cycle <b>300</b>B. In other words, the disk IO scheduler <b>200</b> ensures that each of the queues <b>310</b>-<b>316</b> is provided with time slices of its allocated time interval in a “round robin” manner. For example, as illustrated in disk IO cycle <b>300</b>B, the disk IO scheduler <b>200</b> may provide the queue <b>310</b> with a time slice <b>302</b>A that belongs to the time interval <b>302</b>. This provision of the time slice <b>302</b>A enables queue <b>310</b> to process disk IO requests during the duration of the slice. Subsequently, the disk IO scheduler <b>200</b> may provide time slices <b>304</b>A, <b>306</b>A, and <b>308</b>A of the corresponding time intervals <b>304</b>-<b>308</b> respectively to the queues <b>314</b>-<b>316</b>. During each of the time slices <b>304</b>A, <b>306</b>A, <b>308</b>A, the disk IO scheduler <b>200</b> may also cause the disk manager to process disk IO requests in each of the respective queues <b>312</b>-<b>316</b>.

When the queues <b>310</b>-<b>316</b> are provided with a first round of time slices <b>302</b>A, <b>304</b>A, <b>306</b>A, and <b>308</b>A, the queues <b>310</b>-<b>316</b> are then provided with a second round of time slices <b>302</b>B, <b>304</b>B, <b>306</b>B, and <b>308</b>B, respectively. Additional time slices, such as time slices <b>302</b>C, <b>304</b>C, <b>306</b>C, and <b>308</b>C may be further provided in this “round robin” manner in sequence such that the queues are provided with the same number of time slices during each round for the processing of disk IO requests.

This equal, or substantially equal, division of the time intervals, as well as the “round robin” distribution of time slices to each queue, ensures that disk IO requests of each queue, such as each of the queues <b>310</b>-<b>316</b> are processed with greater but equal frequency. It will be appreciated that disk IO cycle <b>300</b>B is meant to be illustrative rather than limiting. Thus, in various other embodiments, time intervals allocated to each queue may be divided into any number of time slices, provided that each of the time intervals is divided into approximately equal time slices, and the time slices of different time intervals are also approximately the same in duration.

The disk IO scheduler <b>200</b> may dynamically redistribute a disk IO cycle to accommodate one or more new queues that need disk IO bandwidth. For instance, the dynamic redistribution of a new disk IO cycle to accommodate a new queue is illustrated by disk IO cycle <b>320</b>A. The exemplary disk IO cycle <b>320</b>A has the same duration as the disk IO cycle <b>300</b>A.

During or following a disk IO cycle, such as disk IO cycle <b>300</b>A, the disk IO scheduler <b>200</b> may determine that an additional queue <b>318</b> needs disk IO bandwidth. Accordingly, the disk IO scheduler <b>200</b> may allocate the disk IO cycle <b>320</b>A into equal, or substantially equal, time intervals <b>322</b>-<b>330</b>. For example, if the duration of the disk IO cycle <b>320</b>A is approximately 120 ms, the disk IO scheduler <b>200</b> may allocate the time intervals <b>322</b>-<b>330</b> so that each one is approximately 24 ms in duration. In comparison, as described above, each of the time intervals <b>302</b>-<b>208</b> has duration of approximately 30 ms.

The time intervals <b>322</b>-<b>328</b> correspond to the previously processed queues <b>310</b>-<b>316</b>, while the time interval <b>330</b> corresponds to the additional queue <b>318</b>. In various embodiments, the disk IO scheduler <b>200</b> may sequentially provide disk IO bandwidth to the queues <b>310</b>-<b>316</b>, as well as queue <b>318</b>, in a similar manner as during the disk IO cycle <b>320</b>A. During each of the time slices <b>322</b>-<b>330</b>, the disk IO scheduler <b>200</b> may be configured to cause the disk manager to process disk IO requests in each of the respective queues <b>310</b>-<b>318</b>.

It will be appreciated that the dynamic redistribution of a disk IO cycle may also function in reverse when one or more queues ceases their need for disk IO bandwidth. For instance, the disk IO scheduler <b>200</b> may determinate that queue <b>318</b> no longer needs disk IO bandwidth during or following a disk IO cycle, such as disk IO cycle <b>320</b>A. Accordingly, the disk IO scheduler <b>200</b> may adjust the next cycle from one that resembles disk IO cycle <b>320</b>A into one that resembles disk IO cycle <b>300</b>A.

In alternative embodiments where the disk IO scheduler <b>200</b> has divided one or more time intervals into a plurality of time slices, the disk IO scheduler <b>200</b> may also accommodate new queues via the redistribution of the time slices. For instance, the dynamic redistribution of time slices in a new disk IO cycle to accommodate a new queue is illustrated by the disk IO cycle <b>320</b>B. The exemplary disk IO cycle <b>320</b>B has the same duration as disk IO cycle <b>300</b>B.

Initially, the disk IO scheduler <b>200</b> may ensure that each of the queues <b>310</b>-<b>316</b> is provided with time slices of its allocated time interval in a “round robin” manner that is previously described with respect to disk IO cycle <b>300</b>B. As described, the disk IO scheduler <b>200</b> may provide the queue <b>310</b> with a time slice <b>302</b>A that belongs to the time interval <b>302</b>. This provision of the time slice <b>302</b>A enables queue <b>310</b> to process disk IO requests during the duration of the slice. Subsequently, the disk IO scheduler <b>200</b> may provide time slices <b>304</b>A, <b>306</b>A, and <b>308</b>A of the corresponding time intervals <b>304</b>-<b>308</b> respectively to the queues <b>312</b>-<b>316</b>. During each of the time slices <b>302</b>-<b>308</b>, the disk IO scheduler <b>200</b> may be configured to cause the disk manager to process disk IO requests in each of the respective queues <b>312</b>-<b>316</b>. When the queues <b>312</b>-<b>316</b> are provided with a first round of time slices <b>302</b>A, <b>304</b>A, <b>306</b>A, and <b>308</b>A, the queues <b>312</b>-<b>316</b> are then provided with a second round of time slices <b>302</b>B, <b>304</b>B, <b>306</b>B, and <b>308</b>B, respectively.

However, at some point during the disk IO cycle <b>320</b>B, the disk IO scheduler <b>200</b> may determine that an additional queue <b>318</b> needs disk IO bandwidth. Instead of initiating the provision of disk IO bandwidth in the next disk IO cycle, the disk IO scheduler <b>200</b> may convert the one or more remaining round of time slices to accommodate the new queue. In one embodiment, this conversion may be carried out by the cycle distribution module <b>202</b> of the disk IO scheduler <b>200</b>.

For example, instead of providing another round of time slices that resemble the time slices <b>302</b>C, <b>304</b>C, <b>306</b>C, and <b>308</b>C of disk IO cycle <b>300</b>B, the disk IO scheduler <b>200</b> may convert them into time slices <b>322</b>-<b>330</b> so that the queue <b>318</b> may immediately receive some disk IO bandwidth. In one embodiment, the total duration of the time slice <b>302</b>B, <b>304</b>B, <b>306</b>B, and <b>308</b>B is 40 ms, with each queue having approximately 10 ms time slices. Following the adjustment by the disk IO scheduler <b>200</b>, the duration of the time slices <b>322</b>-<b>328</b> provided to each of the queue <b>310</b>-<b>316</b> is approximately 8 ms. Further, the new queue <b>318</b> also receives a time slice <b>330</b> that is approximately 8 ms. It can nevertheless be readily seen that the total duration of the time intervals <b>322</b>-<b>330</b> is also approximately 40 seconds due to the redistribution made by the disk IO scheduler <b>200</b>.

It will be appreciated that in other embodiments, the disk IO scheduler <b>200</b> may convert the one or more remaining rounds of time slices to accommodate any number of queues in a similarly manner. The conversion of one or remaining rounds of time slices to accommodate one or more new queues enables the new queues to receive immediate disk IO bandwidth, thus enhancing user perceived response time.

Following the disk IO cycle <b>320</b>B, the disk IO scheduler <b>200</b> may initiate a disk IO cycle <b>332</b> that includes time intervals <b>334</b>-<b>342</b> for the queues <b>310</b>-<b>316</b>, as well as the queue <b>318</b>. Each of the time intervals <b>334</b>-<b>342</b> being divided equally or approximately equally into a plurality of corresponding time slices (e.g., time interval <b>334</b> divided into <b>334</b>A, <b>334</b>B, and <b>334</b>C) and distributed to the queues <b>310</b>-<b>318</b> in a “round-robin” fashion. Thus, the disk IO scheduler <b>200</b> has adjusted a new cycle to completely accommodate queue <b>318</b> after a partial accommodation.

It will be appreciated that the dynamic redistribution of a disk IO cycle may also function in reverse for time slices when one or more queues ceases their need for disk IO bandwidth. For instance, the disk IO scheduler <b>200</b> may determinate that queue <b>318</b> no longer needs disk IO bandwidth during or following a disk IO cycle, such as disk IO cycle <b>320</b>B. Accordingly, the disk IO scheduler <b>200</b> may adjust the next cycle from one that resembles disk IO cycle <b>332</b> into one that resembles disk IO cycle <b>300</b>B. The adjustment may also occur in mid-cycle in a process that is reverse of the disk IO cycle <b>320</b>B.

<figref idrefs="DRAWINGS">FIG. 4</figref> illustrates the dynamic allocation of disk IO using time intervals in a disk IO cycle <b>402</b> in conjunction with priority designation, in accordance with at least one embodiment of fair and dynamic disk IO bandwidth distribution. In some instances, the time period <b>404</b> may be an equally allocated time interval in the disk IO cycle <b>402</b>. In other instances, the time period <b>404</b> may be a time slice in the disk IO cycle <b>402</b>. The time period <b>404</b> may be provided to a queue, such as queue <b>406</b>, so that one or more disk IO requests of the queue <b>406</b> are processed. The processing of the disk IO requests includes at least one of transferring data to and from a hardware data storage device based on each of the disk IO requests.

In various embodiments, the queue <b>406</b> may include a low portion <b>408</b>, a middle portion <b>410</b>, and a high portion <b>412</b>. The disk IO requests grouped in queue <b>406</b> may be further sorted into each portion according to at least one secondary criterion. For example, the secondary criterion may be a priority rating assigned to each disk IO access request. The portions <b>408</b>-<b>410</b> are configured so that during the timer period <b>404</b>, each portion receives a different allocation of the disk IO bandwidth. In one embodiment, the high portion <b>412</b> is configured to receive the highest allocation of the disk IO bandwidth, with the middle portion <b>410</b> and the low portion <b>308</b> respectively receiving decreasing amounts of disk IO bandwidth allocation. For instance, the disk IO requests in the high portion <b>412</b> may be able to transfer data to and from the hardware storage device using a bandwidth of approximately 700 megabytes (MB) per second during the time interval <b>404</b>. On the other hand, the disk IO requests in the middle portion <b>410</b> may be allocated a bandwidth of approximately 200 MB per second, while the disk IO requests in the low portion <b>408</b> may be allocated a bandwidth of approximately 100 MB per second. In this way, disk IO requests that are grouped into the same queue may be further processed according to a secondary criterion.

Exemplary Processes

<figref idrefs="DRAWINGS">FIGS. 5-6</figref> illustrate exemplary processes that facilitate the implementation of differentiated access to networked resources, in accordance with one or more embodiments. The exemplary processes in <figref idrefs="DRAWINGS">FIGS. 5-6</figref> are illustrated as a collection of blocks in a logical flow diagram, which represents a sequence of operations that can be implemented in hardware, software, and a combination thereof. In the context of software, the blocks represent computer-executable instructions that, when executed by one or more processors, perform the recited operations. Generally, computer-executable instructions include routines, programs, objects, components, data structures, and the like that perform particular functions or implement particular abstract data types. The order in which the operations are described is not intended to be construed as a limitation, and any number of the described blocks can be combined in any order and/or in parallel to implement the process. For discussion purposes, the processes are described with reference to the disk IO scheduler <b>200</b> of <figref idrefs="DRAWINGS">FIG. 2</figref>, although they may be implemented in other disk IO scheduler architectures.

<figref idrefs="DRAWINGS">FIG. 5</figref> is a flow diagram illustrating an exemplary process <b>500</b> for the fair and dynamic provision of disk input/output (IO) bandwidth to each queue. Additionally, the dynamic adjustment of the disk IO bandwidth provided to each queue, in accordance with various embodiments, is also illustrated. At block <b>502</b>, the disk IO scheduler <b>200</b> may group a plurality of disk IO requests into queues according to one or more classification criteria. In the case of a multi-user environment, the disk IO scheduler <b>200</b> may group the disk IO requests according to the user each disk IO request serves.

In other embodiments, the disk IO scheduler <b>200</b> may group the disk IO requests according to additional classification criteria, such as whether the disk IO requests act on multimedia content or non-multimedia content. At block <b>504</b>, the disk IO scheduler <b>200</b> may allocate a disk IO cycle to each of the queues. According to various embodiments, the disk IO cycle may be distributed equally among the queues, such that the duration disk IO time interval distributed to each queue is identical or substantially identical. At block <b>506</b>, the disk IO scheduler <b>200</b> may run a disk IO cycle based on the allocated time intervals. In one embodiment, the disk IO scheduler <b>200</b> may sequentially provide disk IO bandwidth to each of the queue for the duration of the allocated time intervals until the disk IO cycle is completed.

At decision block <b>508</b>, the disk IO scheduler <b>200</b> may determine whether another disk IO cycle is to be performed. If the disk IO scheduler <b>200</b> determines that no further disk IO cycles are to be performed (“no” at decision block <b>508</b>), the process <b>500</b> may terminate at block <b>510</b>. However, if the disk IO scheduler <b>200</b> determines that an additional disk IO cycle is to be performed (“yes” at decision block <b>508</b>), the process <b>500</b> may proceed to decision block <b>512</b>.

At decision block <b>512</b>, the disk IO scheduler <b>200</b> may determine whether an adjustment to the disk IO cycle allocations are necessary, such as due to an increase or decrease in the number of queues that need disk IO bandwidth. If the disk IO scheduler <b>200</b> determines that the disk IO bandwidth allocation should not be adjusted (“no” at decision block <b>512</b>), the process <b>500</b> may loop back to block <b>506</b>, where a disk IO cycle based on the allocated disk IO bandwidth intervals may be performed again for the queues. However, if the disk IO scheduler <b>200</b> determines that the disk IO bandwidth allocation should be adjusted (“yes” at decision block <b>512</b>), the process <b>500</b> may proceed to block <b>514</b>.

At block <b>514</b>, the disk IO scheduler <b>200</b> may adjust the allocation of the disk IO cycle based on changes in the number of queues that need disk IO bandwidth. According to various embodiments, increases or decreases in the number of queues may change the duration of the time intervals assigned to each queue. However, each of the time interval durations nevertheless remains equal or substantially equal to the other time interval durations. Thus, a fair round robin distribution of disk IO bandwidth may be implemented regardless of the number queues. Once the disk IO scheduler <b>200</b> has made the appropriate adjustment to the allocation of the time intervals in the disk IO cycle, the process <b>500</b> may loop back to block <b>506</b>, where a disk IO cycle based on the allocated disk IO bandwidth intervals may be performed again for the queues.

<figref idrefs="DRAWINGS">FIG. 6</figref> is a flow diagram illustrating an exemplary process <b>600</b> for the dynamic distribution of disk IO bandwidth to each of a plurality of queues in multiple time slices, in accordance with at least one embodiment. At block <b>602</b>, the disk IO scheduler <b>200</b> may group a plurality of disk IO requests into queues according to one or more classification criteria. In the case of a multi-user environment, the disk IO scheduler <b>200</b> may group the disk IO requests according to the user each disk IO request serves.

In other embodiments, the disk IO scheduler <b>200</b> may group the disk IO requests according to additional classification criteria, such as whether the disk IO requests act on multimedia content or non-multimedia content. At block <b>604</b>, the disk IO scheduler <b>200</b> may allocate a disk IO cycle to each of the queues. According to various embodiments, the disk IO cycle may be distributed equally, or substantially equally, among the queues, such that the duration disk IO time interval distributed to each queue is identical or substantially identical.

At block <b>606</b>, the disk IO scheduler <b>200</b> may divide each of the one or more allocated time intervals into disk IO time slices. In various embodiments, each of the time intervals may be divided so that the time slices are identical or substantially identical in duration. Moreover, in some embodiments, the time slices from different time intervals are also equal or approximately equal in duration. In this way, the disk IO scheduler <b>200</b> may increase the frequency that each queue of disk IO requests are process, as well as ensure the fair allocation of disk IO bandwidth to each of queues.

At block <b>608</b>, the disk IO scheduler <b>200</b> may provide a round of disk IO time slices for all the queues. In other words, each of queues is provided with one disk IO time slice that makes up its respective time interval. During each disk IO time slice, the disk IO scheduler <b>200</b> may command the disk manager to process the disk IO requests in each respective queue. The processing of the disk IO requests includes at least one of transferring data to and from a hardware data storage device based on each of the disk IO requests.

At decision block <b>610</b>, the disk IO scheduler <b>200</b> may determine whether the disk IO cycle is complete. If the disk IO cycle is complete (“yes” at decision block <b>610</b>), the process <b>600</b> may proceed to decision block <b>612</b>. At decision block <b>612</b>, the disk IO scheduler <b>200</b> may determine whether an additional disk IO cycle is to be performed. If the disk IO scheduler <b>200</b> determines that no further disk IO cycles are to be performed (“no” at decision block <b>612</b>), the process <b>600</b> may terminate at block <b>614</b>. On the other hand, if the disk IO scheduler <b>200</b> determines that an additional disk IO cycle is to be performed (“yes” at decision block <b>614</b>), the process <b>600</b> may loop back to block <b>604</b>, where a new disk IO cycle that includes time intervals provided to the one or more queues.

Returning to decision block <b>610</b>, if the disk IO scheduler <b>200</b> determines that the disk IO cycle is not complete (“no” at decision block <b>610</b>), the process <b>600</b> may proceed to decision block <b>616</b>. At decision block <b>616</b>, the disk IO scheduler <b>200</b> may determine whether the divided disk IO time slices are to be adjusted. For example, the divided disk IO time slices may be adjusted to accommodate one or more new queues that include disk IO access requests. Alternatively, the divided disk IO time slices may be adjusted when one or more queues are terminated.

If the disk IO scheduler <b>200</b> determines that the divided disk IO time slices are to be adjusted (“yes” at decision block <b>161</b>), the disk IO scheduler <b>200</b> may adjust the time slices based on a change in the number of queues at block <b>618</b>. For example, the disk IO scheduler <b>200</b> may detect that a new queue that includes disk IO requests, and adjust the time slices in a manner similar to as shown in disk IO cycle <b>320</b>B (<figref idrefs="DRAWINGS">FIG. 3</figref>) to accommodate the new queue. Once the time slices are adjusted, the process <b>600</b> may loop back to block <b>608</b> where the disk IO scheduler <b>200</b> may provide a round of disk IO time slices for all the queues based on the adjustment. During each disk IO time slice, the disk IO scheduler <b>200</b> may command the disk manager to process the disk IO requests in each respective queue.

However, if the disk IO scheduler <b>200</b> determines that adjustments to the divided disk IO time slices are not necessary (“no” at decision block <b>616</b>), the process <b>600</b> may directly loop back to block <b>608</b> where the disk IO scheduler <b>200</b> may provide a round of disk IO time slices for all the queues based on the adjustment.

It will be appreciated that the dynamic allocation of disk IO bandwidth, as shown, is meant to be illustrative rather than limiting. In other embodiments, the dynamic allocation of disk IO bandwidth may be implemented in alternative processes.

Exemplary Computing Environment

<figref idrefs="DRAWINGS">FIG. 7</figref> illustrates a representative computing device <b>700</b> that may be used to implement the fair and dynamic distribution of disk IO bandwidth to each of a plurality of queues that includes disk IO access requests. For example, the disk IO scheduler <b>200</b> (<figref idrefs="DRAWINGS">FIG. 2</figref>) may be implemented on the representative computing device <b>700</b> to control the data transfer to and from at least one of the removable storage <b>716</b> and non-removable storage <b>718</b>. However, it is readily appreciated that the various embodiments of the fair and dynamic disk IO bandwidth distribution techniques and mechanisms may be implemented in other computing devices, systems, and environments. The computing device <b>700</b> shown in <figref idrefs="DRAWINGS">FIG. 7</figref> is only one example of a computing device and is not intended to suggest any limitation as to the scope of use or functionality of the computer and network architectures. Neither should the computing device <b>700</b> be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the example computing device.

In a very basic configuration, computing device <b>700</b> typically includes the at least one processing unit <b>702</b> and system memory <b>704</b>. Depending on the exact configuration and type of computing device, system memory <b>704</b> may be volatile (such as RAM), non-volatile (such as ROM, flash memory, etc.) or some combination of the two. System memory <b>704</b> typically includes an operating system <b>706</b>, one or more program modules <b>708</b>, and may include program data <b>710</b>. The operating system <b>706</b> include a component-based framework <b>712</b> that supports components (including properties and events), objects, inheritance, polymorphism, reflection, and provides an object-oriented component-based application programming interface (API), such as, but by no means limited to, that of the .NET™ Framework manufactured by Microsoft Corporation, Redmond, Wash. The device <b>700</b> is of a very basic configuration demarcated by a dashed line <b>714</b>. Again, a terminal may have fewer components but will interact with a computing device that may have such a basic configuration.

Computing device <b>700</b> may have additional features or functionality. For example, computing device <b>700</b> may also include additional data storage devices (removable and/or non-removable) such as, for example, magnetic disks, optical disks, or tape. Such additional storage is illustrated in <figref idrefs="DRAWINGS">FIG. 7</figref> by removable storage <b>716</b> and non-removable storage <b>718</b>. Computer storage media may include volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information, such as computer readable instructions, data structures, program modules, or other data. System memory <b>704</b>, removable storage <b>716</b> and non-removable storage <b>718</b> are all examples of computer storage media. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by computing device <b>700</b>. Any such computer storage media may be part of device <b>700</b>. Computing device <b>700</b> may also have input device(s) <b>720</b> such as keyboard, mouse, pen, voice input device, touch input device, etc. Output device(s) <b>722</b> such as a display, speakers, printer, etc. may also be included. These devices are well know in the art and are not discussed at length here.

Computing device <b>700</b> may also contain communication connections <b>724</b> that allow the device to communicate with other computing devices <b>726</b>, such as over a network. These networks may include wired networks as well as wireless networks. Communication connections <b>724</b> are one example of communication media. Communication media may typically be embodied by computer readable instructions, data structures, program modules, etc.

It will be appreciated that the illustrated computing device <b>700</b> is only one example of a suitable device and is not intended to suggest any limitation as to the scope of use or functionality of the various embodiments described. Other well-known computing devices, systems, environments and/or configurations that may be suitable for use with the embodiments include, but are not limited to personal computers, server computers, hand-held or laptop devices, multiprocessor systems, microprocessor-base systems, set top boxes, game consoles, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and/or the like.

The provision of fair and dynamic distribution of disk IO bandwidth to a plurality of queues, such as queues of disk IO requests servicing software applications running in a multi-user environment, may maximize disk IO bandwidth usage while serving to enhance user experience. For example, the fair and dynamic distribution of disk IO bandwidth to queues may ensure that no application serving a first user is starved of disk IO bandwidth due to an application serving another user consuming a disproportionate amount of disk IO bandwidth. Thus, embodiments in accordance with this disclosure may diminish delays and hesitations that users may experience while using applications.

CONCLUSION

In closing, although the various embodiments have been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described. Rather, the specific features and acts are disclosed as exemplary forms of implementing the claimed subject matter.