Centralized task scheduling

A method and apparatus that schedules and manages a background task for device is described. In an exemplary embodiment, the device registers the background task, where the registering includes storing execution criteria for the background task. The execution criteria indicates a criterion for launching the background task and the execution criteria based on a component status of the device. The device further monitors the running state of the device for an occurrence of the execution criteria. If the execution criteria occurs, the device determines an available headroom with the device in order to perform the background task and launches the background task if the background task importance is greater than the available device headroom, where the background task importance is a measure of how important it is for the device to run the background task.

FIELD OF INVENTION

This invention relates generally to process management and more particularly to scheduling tasks based on system conditions.

BACKGROUND OF THE INVENTION

A background task is a process of a device that runs in the background and without user intervention. These background tasks can be used for processes that perform actions where a user intervention is not required. For example, a background task can be used for logging, system monitoring, device maintenance, software updates, media and/or application downloads, or other actions that do not require user intervention.

Because a background task does not require user intervention, the device can run this task on demand or can schedule to perform the background task at some future time. One way to perform the task in the future is to schedule this task is to have the task performed at a scheduled fixed time in the future. This can be can be used for a background task that is to be performed once or a recurring task that is periodically performed on a fixed time schedule.

A problem with fixed scheduling of background task execution is that the device operating conditions may not be appropriate for the background task actions. For example, a background task that periodically checks for a download availability from a server would require network connectivity with this server in order for the background task to successfully run. By scheduling this task to run at a fixed time, it is unknown if the background task will have the appropriate system conditions when device runs the background task. In addition, the running of the background task, at an inappropriate time, may degrade other running processes as well as the user interaction with the device.

SUMMARY OF THE DESCRIPTION

A method and apparatus that schedules and manages a background task for device is described. In an exemplary embodiment, the device registers the background task, where the registering includes storing execution criteria for the background task. The execution criteria indicates a criterion for launching the background task and the execution criteria based on a component status of the device. The device further monitors the running state of the device for an occurrence of the execution criteria. If the execution criteria occurs, the device determines an available headroom with the device in order to perform the background task and launches the background task if the background task importance is greater than the available device headroom, where the background task importance is a measure of how important it is for the device to run the background task.

In another embodiment, the device determines a time-dependent task importance for the background task, where the time-dependent task importance is based on a time that has elapsed since the background task is initially available to run. The device further determines an available headroom for the device in order to run the background task and compares this system cost to the time-dependent task importance. If the time-dependent task importance is greater than the available device headroom, the device runs the background task.

Other methods and apparatuses are also described.

DETAILED DESCRIPTION

A method and apparatus that schedules and manages a background task for device is described. In the following description, numerous specific details are set forth to provide thorough explanation of embodiments of the present invention. It will be apparent, however, to one skilled in the art, that embodiments of the present invention may be practiced without these specific details. In other instances, well-known components, structures, and techniques have not been shown in detail in order not to obscure the understanding of this description.

The terms “server,” “client,” and “device” are intended to refer generally to data processing systems rather than specifically to a particular form factor for the server, client, and/or device.

A method and apparatus that schedules and manages a background task for device is described. In one embodiment, the device registers a background task to be run at a later time, where this task includes one or more criteria that are used to determine when it is an appropriate time for the device to run the task. In one embodiment, each of the criteria can be based on a component status, such as device power state, central processing unit status, display status, storage system status, or network connectivity. For example and in one embodiment, a criteria can be a power status (e.g., whether the device is running on battery or is plugged into an alternative current (A/C) power source), system load (e.g., whether the central processing unit(s) (CPUs) are idle, busy, or under a certain percent load), and/or other advanced criteria (e.g., network connectivity (in general, or connected to a particular server or service), whether a screen of the device is asleep, storage activity (e.g., having the hard disk drive (HDD) spinning), requiring a particular power status (e.g., A/C only, battery at, above, below a certain threshold, etc.).

In one embodiment, if these criteria are satisfied at a time during the device operation, the device determines if the background task should be run. The device determines an available device headroom and compares this available device headroom with a task importance. In one embodiment, the available device headroom is amount of device resources that are available to run the task. If the available device headroom is greater than or equal to the task importance, the device runs the task. Conversely, if the available device headroom is lower than the task importance, the device waits for a later time to run the task. At this later time, the device re-evaluates the device conditions to determine if the task criteria are still satisfied. If the task criteria are still satisfied, the device performs the comparison of the available device headroom and the task importance. In one embodiment, the task importance changes depending on a time elapsed since the task criteria are initially satisfied. When the task criteria are initially satisfied, the task importance is low. As the time elapses, the task importance grows until the grace period of the task expires. At the expiration of the grace period for this task, the task importance increases so that the task is more likely to be run. In one embodiment, the device runs the task by sending a notification to the application corresponding to the task that the task is ready to run. In one embodiment, the task is a part of a larger application (e.g., for an e-mail application, a task could be checking for new e-mail).

Once the device runs the task, the device monitors the task criteria to determine if the task criteria are satisfied during the execution of the task. If, during execution the task, the task criteria are not satisfied, the device determines whether to continue the execution of the task. If the task is to be deferred, the device suspends the task. In one embodiment, the device suspends the task by the application corresponding to the task suspending execution of the task. At a later time, if the task criteria are subsequently re-satisfied, the device can restart execution of the task. As the task completes, the device determines if the task is a recurring task, in which case, the device schedules another instance of this task.

FIG. 1is a block diagram of one embodiment of a device100with background task scheduler108. In one embodiment, the device100can be a personal computer, laptop, server, mobile device (e.g., smartphone, laptop, personal digital assistant, music playing device, gaming device, etc.), network element (e.g., router, switch, gateway, etc.), and/or any device capable of executing multiple processes and having a sleep mode. In one embodiment, the device can be a physical or virtual device. InFIG. 1, the device100includes an operating system102that is a set of software used to manage the device's hardware resources and provides common services for other running the device's programs, such as application programs. In one embodiment, the operating system102manages the different running processes by time scheduling when a processor of the device100executes each running process. In one embodiment, a process is an instance of a computer program that is being executed. In this embodiment, the process may be a user application104that is executing as a result of user input. Examples of user processes are web surfing, word processing, email, social media, media processing, etc. Another example of a process is a system process106that provides one or more services to a user application, other process, etc. In one embodiment, a system process is a daemon that performs system maintenance or other types of single or recurring tasks.

In one embodiment, the operating system102includes a launching daemon112to launch processes. In this embodiment, the launch daemon includes a background task scheduler108that schedules and manages a background task. In addition, the operating system102includes one or more scheduled tasks110. In one embodiment, a background task is a task that runs in the background and without user intervention. A background task can be a single purpose task (e.g., remote downloads, a deferrable long running activity initiated after user action or remote trigger (e.g. optimizing the storage of an on disk database (initiated after a user-triggered database update), a server-initiated (pushed) download of an update to e.g. a Uniform Resource Locator (URL) blacklist and/or whitelist, a download of a higher quality media asset (image/movie/voice) than what is shipped with the system by default (triggered on first use of the low-quality asset by the user), etc.) or can be a recurring task that periodically performs an action (e.g., backup, system maintenance, checking for software updates, mail fetches, calendar refresh, downloading of system and/or as 3rd-party application updates (in addition to checking for the presence of such updates on a server), synchronizing of user documents and/or settings with a server, uploading of diagnostic information about the device and/or applications on the device to a server, etc.). In one embodiment, the background task scheduler108schedules a task to run at a time when the system conditions are appropriate for the scheduled task to run. In one embodiment, the background task scheduler108receives a message for a task to be scheduled to run from an application that corresponds to this task. In one embodiment, the task is a part of a larger application (e.g., for an e-mail application, a task could be checking for new e-mail). For example and in one embodiment, a software update daemon registers a check for updates task with the background task scheduler108, where the check for updates task is a task that checks to see if there are updates that are available to download and install on the device100. As another example and in another embodiment, a backup service application registers a backup maintenance task with the background task scheduler108.

In one embodiment, by running the tasks based on system conditions, the background task scheduler108can improve battery life, device responsiveness, eliminate the cost of starting services that immediately exit due to unsatisfied requirements, and centralize the logic for the device100wake/nap power management tasks with the background task scheduler108. In this embodiment, the background task scheduler108registers a task based on a request from another process, such as the user process104or system process106. In one embodiment, the task may be repeating or non-repeating. The task may be registered dynamically by an application, or statically based on a configuration of a system process106. In one embodiment, each task has a dictionary describing the task execution criteria (e.g., various considerations the system should take into account when decided whether to run the task), a current execution state (is it running or not) and a handler that is invoked when the task's state changes.

In one embodiment, the application registers a task with an application plugin that is used to communicate with the background task scheduler108. In addition, once the task criteria are satisfied and it is an appropriate time for the task to be run, the background task scheduler108sends a notification to the application that the task may be run using an inter-process communication message (e.g., inter-process communication (IPC) messages, Mach messages, signals, writes to a file descriptor, creation of a “semaphore” file, etc.). In one embodiment, the background task scheduler108sends a notification to wake up a sleeping application in response to a registered task. This embodiment allows applications in a sleep mode to be automatically woken up to respond to registered task. Furthermore, this embodiment also allows system process(es)106(e.g., daemons) to be launched on demand in response to registered task. In another embodiment, daemons participate in idle exit and successfully idle exit while tasks are waiting to run. In this embodiment, the daemon will be automatically re-launched in response to the task becoming runnable.

In one embodiment, once a task is registered, the background task scheduler108runs this task based on a number of possible criteria. In one embodiment, the different criteria can be: repeatability, delay, grace period, and priority. In one embodiment, repeatability is whether the task is to be rescheduled automatically when it completes. Delay is a period of time to wait before starting the task. In one embodiment, the task is one of the execution criterion for the task. In this embodiment, if the delay is not satisfied, the other execution criteria will not be checked for satisfaction. The grace period is a period of time after which the task becomes past due and the system tries to schedule the task more aggressively. In addition, the background task scheduler108can use different priority criteria to run the task. In one embodiment, the different priorities can be for a maintenance task, which are used for user-invisible tasks and avoids running on battery until the task is past due, and a utility task, which is used for user-visible tasks and may run on battery. In one embodiment, a background task can be run in a reduced power-consumption mode.

By using the different criteria and priority, the background task scheduler108evaluates each task's criteria to determine whether the task is eligible to run. In one embodiment, the background task scheduler108will tend to execute tasks when on A/C power instead of battery and tends to execute tasks during a power nap instead of when awake, and tends to execute tasks when the system is idle instead of busy. In one embodiment, a power nap is a sleep mode that allows the device100to perform tasks silently, such as media syncing and search indexing. In this embodiment, low energy tasks are performed when on battery power, while higher energy tasks are performed with A/C power. A power nap can apply to the device or to one or more individual applications.

In one embodiment, different types of tasks can have different types of criteria for when the task is available to run. For example and in one embodiment, a maintenance eligible task can run during an A/C power nap and A/C Idle during the nominal time period, and can run during A/C power nap, A/C Idle, A/C Busy, Battery power nap, Battery Idle, and Battery Busy if the task is past due. In this embodiment, Busy and Idle refer to the system load, Battery and A/C refer to whether the device100is using the device100battery for power or is plugged in and using A/C power. Power nap refers to the device100being in a power nap sleep mode. In another example and an another embodiment, a utility task can run during an A/C power nap, A/C Idle, and Battery Idle during the nominal time period, and can run during A/C power nap, A/C Idle, A/C Busy, Battery power nap, Battery power nap, Battery Idle, and Battery Busy if the task is past due.

In one embodiment, in addition to the criteria described above, the background task scheduler108can use advanced criteria to determine when to run the registered task. In one embodiment, these advanced criteria can be used by themselves or can be used in addition to the general sleep mode, power, and system load criteria described above. In one embodiment, the advanced criteria are: network criteria, A/C only, Screen Sleep, Battery Level, Hard Disk Drive (HDD) spinning, power nap eligibility, type of networking (wireless (Wi-Fi or cellular), wired, etc.) networking in roaming state, cellular voice calls available, etc. In one embodiment, the network criterion is used for tasks that may require connectivity to a specified host or general network connectivity in order to be eligible. The requested connection will be attempted prior to initiating such task. The established connection may be retrieved from the task (e.g., the communication handle may be stored in the task dictionary). The A/C only criteria can be used for tasks that may require A/C power, even when past due. The Screen Sleep criteria can be used for tasks that may require screen sleep. The Battery Level criterion is used for tasks that may require a minimum battery level (%). For example and in one embodiment, a download task may require a high battery percentage level (e.g., >90%) and a status check may require a smaller battery percentage level (e.g., >25%). In one embodiment, the HDD spinning criteria can be used for tasks that require the HDD be spinning.

In one embodiment, once the criteria for a registered task is satisfied, the background task scheduler108compares an importance of the registered task with an available headroom for the device. In one embodiment, the available device headroom is amount of device resources that are available to run the task. In this embodiment, the available device headroom is determined based one or more different factors that measure what type of load or use the device is experiencing. For example and in one embodiment, the available device headroom can be based on device temperature, CPU % utilization, whether the device is running on battery or AC, battery capacity, memory usage, user activity (e.g. how recently has the user been actively interacting with the device), another type of factor that measures current device capacity or load, and/or a combination thereof. In one embodiment, the device headroom is based on a function of the one or more factors. For example and in one embodiment, if one of the factors is above a threshold for that factor, then the available device headroom is small. In another example, a polynomial of the values for one or more of the factors can be used to determine the available device headroom (e.g., a square root of the sum of the squares of factors with each of the factor normalized to be between zero and one).

In one embodiment, each registered task has the following states: CHECK-IN, WAIT, RUN, DEFER, CONTINUE, DONE. In one embodiment, the CHECK-IN state is an optional state that is used by daemons to check in with the background task scheduler108. In one embodiment, a task whose criteria have not yet been satisfied is in the WAIT state. This state is used for a task that is waiting for the system criteria to be satisfied before the task is run. In one embodiment, once the task's criteria are satisfied, the background task scheduler108transitions the task to the RUN state and invokes the handler for the task. During the course of the RUN, the application may test whether the criteria for the task are still satisfied. The application may then optionally return early from the handler and defer the work to a more opportune time by putting the task in the DEFER state. For example and in one embodiment, the background task scheduler108observes the impact of actually executing the task on system load and take that information into account in future decision about whether to run that task again, or even whether to stop the currently running task and defer it. For instance, on a laptop in a backpack, the thermal impact of running a task in powernap may be too high so it may need to be stopped prematurely, but if that same sleeping laptop is sitting on a desk, that same task in powernap may be just fine.

The background task scheduler108can re-invoke the handler when the criteria for the task are once again satisfied. Alternatively, the application may request to continue the work asynchronously from the handler by setting the state to the CONTINUE state, in which case, the background task scheduler108must update the state to either DEFER or DONE at a later time. Finally, an application may indicate that the task is DONE. A non-repeating task will be unregistered with the background task scheduler108once the task is done and a repeating task is re-registered with the background task scheduler108so that this task can be repeated at the scheduled time.

As described above, once the task criteria for a task have been satisfied, the device100uses a task importance curve to determine whether to run the task.FIG. 2is an illustration of one embodiment of a task importance curve206for one task. In one embodiment, the task importance curve is representative of one task and other tasks may have differently shaped tasks (e.g., shorter or longer grace periods, non-linear curves or a linear curve with a larger or smaller slope between the initial scheduled point and the point at which the grace period expires, etc.) In one embodiment, the task importance curve206is a curve plotted of device headroom required202versus time204for one task that is registered with the background task scheduler108. In one embodiment, if the device headroom is below or equal to the task importance curve206for a given point of time, the background task scheduler108defers running the task. If required device headroom is at or above the task importance curve206at a particular point in time, the background task scheduler108runs the task. In one embodiment, the task importance curve206decreases in device headroom required202as time increases for the time204. Thus, the task importance is time-dependent because the value of the task importance changes over time, including a time before the grace period expires. In this embodiment, the task importance curve206is at the highest point210when the task can initially be scheduled for running. By being at a high point, this means that the task can run if the available device headroom is high. In one embodiment, as the time increases since the initial point210, the task importance lowers on the task importance curve206as time increases. In this embodiment, as time increases since the initial point that the task can be run, the background task scheduler108can allow a task to run with a smaller available device headroom. This gradual decrease in cost threshold ends when the grace period208of the task ends. In one embodiment, each task has a grace period. During this grace period, the task can be run in which the conditions are more optimal for the task to run. In one embodiment, once the grace period expires, a lower required device headroom can occur for the task to be run. This allows the task to run in a greater variety of scenarios. For example and in one embodiment, a task that is to run during a time of high system utilization will be deferred until a time when the importance of the task has increased to a point where the task can be run. In one embodiment, after the grace period ends, the task remains in the “urgent state” until such a time that the task can be run. In this embodiment, the task may not run because the device is very busy and has no headroom to run the task. In one embodiment, after the grace period, the required device headroom for the task can be a constant value that is non-zero or zero. If non-zero, this means that a condition can exist where the task is not run (e.g., if the temperature of the device is high, then the task is not run). In another embodiment, the section of the task importance curve206is non-constant (e.g., asymptotically trending towards zero).

As described above, the background task scheduler108of device100schedules the tasks, determines when to run the task, and manages the running of the task.FIG. 3is a flow chart of one embodiment of a process300to schedule and manage a task. In one embodiment, process300is performed by the background task scheduler to schedule and manage task, such as background task scheduler108ofFIG. 1as described above. InFIG. 3, process300begins by receiving the task that is to be scheduled at block302. In one embodiment, process300receives the task to be scheduled from a user process, a system process, via a static configuration file (e.g., launch-on-demand tasks), etc. For example and in one embodiment, user process can be a media management application that uses a task to determine if there is available media to download for the user, a mail application that can use a task to fetch mail, a calendar application to refresh a calendar, etc. As another example, a system process can be a search system that uses a task to update a search index, a backup application that uses a task to perform backup maintenance work, a file viewing application that uses a task to update the file cache, a software update program can use a task to check for available updater, an application store application can use a task to determine is there are application downloads and/or updates, etc. Process300schedules the task at block304. In one embodiment, process300schedules the task using one or more criteria of when the task can run. In one embodiment, these execution criteria are stored in the dictionary for the scheduled task. For example and in one embodiment, a maintenance type task can be scheduled to possibly run before the grace period ends for this task when the system running the task has A/C power and the system is idle or in a power nap. In this embodiment, after the grace period ends, the maintenance type task can be run when the system is either on A/C power or on battery power. In this embodiment, the maintenance type task after the grace period expires for this when the criteria of A/C Power Nap, A/C Idle, A/C Busy, Battery Power Nap, Battery Power Nap, Battery Idle, and Battery Busy are satisfied. In one embodiment, a grace period is a period of time after which the task becomes past due and the system tries to schedule the task more aggressively

At block306, process300monitors the system to determine if the criteria for the scheduled task have been satisfied. In one embodiment, process300monitors the power state of the system (e.g., on A/C power or battery) and/or system load (e.g., idle, busy, or in a Power Nap). In addition, process300can monitor advanced criteria conditions, such as network criteria, A/C only, Screen Sleep, Battery Level, Hard Disk Drive (HDD) spinning, etc. Process300determines if task criteria have been satisfied at block308. In one embodiment, process300determines that a task's execution criteria are satisfied by setting up system change notifications for the overall set of conditions underlying the execution criteria for each of the currently registered tasks, and evaluating each task's set of execution criteria when the system notifies process300that an underlying system condition for one of the monitored criteria has changed. In one embodiment, a task whose criteria have not yet been satisfied is in the WAIT state. This state is used for a task that is waiting for the system criteria to be satisfied before the task is run.

If the task criteria have not been satisfied, execution proceeds to block306above. If the task criteria have been satisfied, process300determines the available device headroom at block310. In one embodiment, process300determines the available device headroom by evaluating one or more factors of the device as described above with reference toFIG. 1. At block312, process300determines if the task importance for the task is less than (or equal to) the system cost for the task. In one embodiment, process300computes the task importance based on the task importance curve and the time elapsed since the criteria for the task are first satisfied. Determining if the task importance is less than (or equal to) the available device headroom is further described inFIG. 5below. If the task importance is not less than the available device headroom, execution proceeds to block306above.

If the task importance is less than (or equal to) than the available device headroom, process300executes the task at block314. In one embodiment, process300notifies the application corresponding to the task that the task is ready for execution. In one embodiment, once the task's criteria are satisfied, the process300transitions the task to the RUN state and invokes the handler for the task. For example and in one embodiment, if the criteria for a media download check task for a media management application are satisfied and this task is ready to run, process300sends a notification to the application that the task is ready to run. In this embodiment, process300does not directly invokes the handler or “runs the task”. Process300sends a message to the application or daemon that registered for a task to trigger the task's handler execution. For an on-demand-launchable or idle-exiting daemon, this message will also first launch the daemon in question.

At block316, the application or daemon for the task determines if the task should be deferred. In one embodiment, while the task is being run, the application running the task may test whether the criteria for the task are still satisfied. The application may then return early from the handler and DEFER the work to a more opportune time. If the task is to be deferred, at block326, the application or daemon for the task defers the running of the task and puts the task into the DEFER state. In one embodiment, in this state, the task is suspended in its current state. At block328, process300determines if the task execution should be restarted. If the task execution should be restarted, execution proceeds to block314above. In one embodiment, process300can notify the application or daemon for this task that the handler can be re-invoked when the criteria for the task are once again satisfied. Alternatively, the application may request to CONTINUE the work asynchronously from the handler, in which case, the application or daemon for the task updates the state of the task to either DEFER or DONE at a later time. If the task execution is not to be restarted, execution proceeds to block326above.

If the task execution is not to be deferred at block316above, the application or daemon for the task determines if the task has completed at block318. At block320, process300marks the task as completed. In one embodiment, process300puts the task is the DONE state if the task is completed. At block322, process300determines if the task is a recurring task. In one embodiment, a recurring task is one that is periodically executed to perform a repeated scheduled server. For example and in one embodiment, a recurring task can be one that periodically checks for a download from a server (e.g., mail fetching, calendar refresh, media download service, application download, etc.). In this embodiment, once the download task is complete, process300would schedule another instance of this task for execution in the future. If the task is a recurring task, execution proceeds to block304, where process300schedules the next instance of the task. If the task is not a recurring task, at block324, process300marks the execution of the task as done.

FIG. 4is an illustration of one embodiment of a state diagram400of different states for a task. In one embodiment, the background task scheduler108and/or the application handling the task updates the state of the task according to this state diagram400. The state diagram400illustrates the supported state transitions. In one embodiment, the solid lines indicate state advancements made by the system upon return from the handler. Manual advancement of the state by the application is optional and applies to the DEFER, CONTINUE and DONE states. The bold dotted line applies to repeating tasks. The thin lines indicate optional state advancements by the application “ . . . applies to the DEFER, CONTINUE and CHECK-IN states”.

In one embodiment, each registered task starts by being created by either an application or daemon, or by a scheduler based on a static configure file. In one embodiment, each registered task has the following states: CREATE/START402, CHECK-IN404, WAIT406, RUN408, DEFER410, CONTINUE412, and DONE414. In one embodiment, the CHECK-IN state404is an optional state that is used by daemons to check in with the background task scheduler108. In one embodiment, the CHECK-IN state is used by on-demand-launched daemons to retrieve and potentially modify eligibility criteria specified in static configuration files. The state advances to WAIT automatically upon return of the handler for the CHECK-IN state. In another embodiment, the background task scheduler transitions a task form the CREATE/START state402by advancing from CREATE to WAIT automatically and remains there until the activity is eligible to run (at which point the state advances to RUN).

In one embodiment, a task whose criteria have not yet been satisfied is in the WAIT state406. This state is used for a task that is waiting for the system criteria to be satisfied before the task is run. For example and in one embodiment, a maintenance task that requires a screen sleep will not be able to run until the screen of the device that will run the ask is asleep. In one embodiment, once the task's criteria are satisfied, the background task scheduler transitions the task to the RUN state408and invokes the handler for the task. In one embodiment, the handler of an application is a block of code that is to be run to initiate the task and perform the task operations.

In one embodiment, during the course of the task being in the RUN state408, the application may test whether the criteria for the task are still satisfied. For example and in one embodiment, if a task depends on a network connection to a particular service and this service is not currently available, the application that corresponds to this task transitions the task state to DEFER410. In one embodiment, the task (e.g., the application) may query the scheduler to test if it should defer execution. If the response is yes, the application may acknowledge the deferral by setting the task state to DEFER (otherwise the task remains in the RUN state, or moves to the DONE state if the handler returns without changing the state). In one embodiment, if the criteria are not currently satisfied for the running task, the application may then return from the handler and defer the work to a time when the criteria task are satisfied. In one embodiment, the background task scheduler108will re-invoke the handler when the criteria for the task are once again satisfied. Alternatively, the application may request to CONTINUE412the work asynchronously from the handler, in which case, the background task scheduler updates the state to either DEFER410or DONE414at a later time. In one embodiment, the CONTINUE state is used if the “running” of the task needs to continue after the handler returns for the RUN state, where the automatic state transition from RUN to DONE is not to occur. If the state is set to CONTINUE the task is considered to be “running” until the application manually sets the state to either DONE or DEFER.

In one embodiment, an application may indicate that the task is done by putting the task in the DONE state414. In this embodiment, a non-repeating task is unregistered with the background task scheduler once the task is done and repeating task is re-registered with the background task scheduler so that this task can be repeated at the scheduled time. In one embodiment, the transition to DONE also occurs automatically when the handler returns (after being called by the transition to the RUN state) without having changed the state.

As described above, the background task scheduler may not automatically run the task if the execution criteria for a task are satisfied. Instead the background task scheduler compares the task importance with the available device headroom to determine whether to run the task.FIG. 5is a flowchart of one embodiment of a process500to compare a task importance and an available device headroom. In one embodiment, process500is performed by process300at block312inFIG. 3above to compare a task importance and an available device headroom. InFIG. 5, process500begins by receiving the available device headroom at block502. In one embodiment, the available device headroom is determined by evaluating one or more factors of the device as described above with reference toFIG. 1. At block504, process500determines the task importance. In one embodiment, process500determines the task importance by using the task importance curve, such as the task importance curve206as described inFIG. 2above. In this embodiment, process500determines the time elapsed since the criteria of the task were initially satisfied. Using this time, process500can determine the task importance using the elapsed time with the task importance curve as described above with reference toFIG. 2. For example and in one embodiment, the task importance is relatively low at the initial point at which the task criteria are satisfied. This task importance grows up until the grace period expires for this task. At this point, the task importance jumps up because the background task scheduler will more aggressively try to run the task. In another embodiment, process500computes the task importance using an equation that relates the task importance based on the time elapsed since the task criteria were initially satisfied.

At block506, process500determines if the task importance of the task is less than (or equal to) the available device headroom. If the task importance is less than (or equal to) the available device headroom, the system can run the task and returns a yes at block508. If not, the system defers execution of the task until a later time and returns a no at block510.

FIG. 6is a block diagram of one embodiment of a background task scheduler108to schedule and manage a task. In one embodiment, the background task scheduler108includes receive task module602, schedule task module604, monitor system module606, system criteria module608, determine available device headroom module610, task importance module612, execute task module614, defer task determination module616, defer task module618, restart task module620, task complete determination module622, task complete module624, task recurring module626, and task done module628. In one embodiment, the receive task module602receives the task as described inFIG. 3, block302above. The schedule task module604schedules the task as described inFIG. 3, block304above. The monitor system module606monitors the system for the task criteria as described inFIG. 3, block306above. The system criteria module608determines if the criteria for the task are satisfied as described inFIG. 3, block308above. The determine available device headroom module610determines the available device headroom as described inFIG. 3, block310above. The task importance module612compares the task importance and system cost as described inFIG. 3, block312above. The execute task module614runs the task as described inFIG. 3, block314above. The defer task determination module616determines whether to defer the task as described inFIG. 3, block316above. The defer task module618defers execution of the task as described inFIG. 3, block326above. The restart task module620restarts execution of the task as described inFIG. 3, block328above. The task complete determination module622determines if the task execution is complete as described inFIG. 3, block318above. The task complete module624marks the task as complete as described inFIG. 3, block320above. The task recurring module626determines if the task is recurring as described inFIG. 3, block322above. The task done module628marks the execution of the task as done as described inFIG. 3, block324above.

FIG. 7is a block diagram of one embodiment of a task importance module612to compare a task importance and an available device headroom. In one embodiment, the task importance module612includes a receive available device headroom module702, compute task importance module704, compare importance and headroom module706, and return results module708. In one embodiment, the receive available device headroom module702receives the available device headroom as described inFIG. 5, block502. The compute task importance module704determines the task importance as described inFIG. 5, block504. The compare importance and headroom module706determines if the task importance is greater than the system cost of the task as described inFIG. 5, block506. The return results module708returns the results of the comparison as described in blocks508and510ofFIG. 5above.

FIG. 8shows one example of a data processing system800, which may be used with one embodiment of the present invention. For example, the system800may be implemented including a device100as shown inFIG. 1. Note that whileFIG. 8illustrates various components of a computer system, it is not intended to represent any particular architecture or manner of interconnecting the components as such details are not germane to the present invention. It will also be appreciated that network computers and other data processing systems or other consumer electronic devices, which have fewer components or perhaps more components, may also be used with the present invention.

As shown inFIG. 8, the computer system800, which is a form of a data processing system, includes a bus803which is coupled to a microprocessor(s)805and a ROM (Read Only Memory)807and volatile RAM809and a non-volatile memory811. The microprocessor805may retrieve the instructions from the memories807,809,811and execute the instructions to perform operations described above. The bus803interconnects these various components together and also interconnects these components805,807,809, and811to a display controller and display device813and to peripheral devices such as input/output (I/O) devices which may be mice, keyboards, modems, network interfaces, printers and other devices which are well known in the art. Typically, the input/output devices815are coupled to the system through input/output controllers813. The volatile RAM (Random Access Memory)809is typically implemented as dynamic RAM (DRAM), which requires power continually in order to refresh or maintain the data in the memory.

The mass storage811is typically a magnetic hard drive or a magnetic optical drive or an optical drive or a DVD RAM or a flash memory or other types of memory systems, which maintain data (e.g. large amounts of data) even after power is removed from the system. Typically, the mass storage811will also be a random access memory although this is not required. WhileFIG. 8shows that the mass storage811is a local device coupled directly to the rest of the components in the data processing system, it will be appreciated that the present invention may utilize a non-volatile memory which is remote from the system, such as a network storage device which is coupled to the data processing system through a network interface such as a modem, an Ethernet interface or a wireless network. The bus803may include one or more buses connected to each other through various bridges, controllers and/or adapters as is well known in the art.

FIG. 9shows an example of another data processing system900which may be used with one embodiment of the present invention. For example, system900may be implemented as a device100as shown inFIG. 1. The data processing system900shown inFIG. 9includes a processing system911, which may be one or more microprocessors, or which may be a system on a chip integrated circuit, and the system also includes memory901for storing data and programs for execution by the processing system. The system900also includes an audio input/output subsystem905, which may include a microphone and a speaker for, for example, playing back music or providing telephone functionality through the speaker and microphone.

A display controller and display device909provide a visual user interface for the user; this digital interface may include a graphical user interface which is similar to that shown on a Macintosh computer when running OS X operating system software, or Apple iPhone when running the iOS operating system, etc. The system900also includes one or more wireless transceivers903to communicate with another data processing system, such as the system900ofFIG. 9. A wireless transceiver may be a WLAN transceiver, an infrared transceiver, a Bluetooth transceiver, and/or a wireless cellular telephony transceiver. It will be appreciated that additional components, not shown, may also be part of the system900in certain embodiments, and in certain embodiments fewer components than shown inFIG. 9may also be used in a data processing system. The system900further includes one or more communications ports917to communicate with another data processing system, such as the system800ofFIG. 8. The communications port may be a USB port, Firewire port, Bluetooth interface, etc.

The data processing system900also includes one or more input devices913, which are provided to allow a user to provide input to the system. These input devices may be a keypad or a keyboard or a touch panel or a multi touch panel. The data processing system900also includes an optional input/output device915which may be a connector for a dock. It will be appreciated that one or more buses, not shown, may be used to interconnect the various components as is well known in the art. The data processing system shown inFIG. 9may be a handheld computer or a personal digital assistant (PDA), or a cellular telephone with PDA like functionality, or a handheld computer which includes a cellular telephone, or a media player, such as an iPod, or devices which combine aspects or functions of these devices, such as a media player combined with a PDA and a cellular telephone in one device or an embedded device or other consumer electronic devices. In other embodiments, the data processing system900may be a network computer or an embedded processing device within another device, or other types of data processing systems, which have fewer components or perhaps more components than that shown inFIG. 9.

At least certain embodiments of the inventions may be part of a digital media player, such as a portable music and/or video media player, which may include a media processing system to present the media, a storage device to store the media and may further include a radio frequency (RF) transceiver (e.g., an RF transceiver for a cellular telephone) coupled with an antenna system and the media processing system. In certain embodiments, media stored on a remote storage device may be transmitted to the media player through the RF transceiver. The media may be, for example, one or more of music or other audio, still pictures, or motion pictures.

The portable media player may include a media selection device, such as a click wheel input device on an iPod® or iPod Nano® media player from Apple, Inc. of Cupertino, Calif., a touch screen input device, pushbutton device, movable pointing input device or other input device. The media selection device may be used to select the media stored on the storage device and/or the remote storage device. The portable media player may, in at least certain embodiments, include a display device which is coupled to the media processing system to display titles or other indicators of media being selected through the input device and being presented, either through a speaker or earphone(s), or on the display device, or on both display device and a speaker or earphone(s). Examples of a portable media player are described in published U.S. Pat. No. 7,345,671 and U.S. published patent number 2004/0224638, both of which are incorporated herein by reference.

A machine readable medium includes any mechanism for storing or transmitting information in a form readable by a machine (e.g., a computer). For example, a machine readable medium includes read only memory (“ROM”); random access memory (“RAM”); magnetic disk storage media; optical storage media; flash memory devices; etc.

It should be kept in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the above discussion, it is appreciated that throughout the description, discussions utilizing terms such as “registering,” “receiving,” “determining,” “resuming,” “storing,” “monitoring,” “computing,” “launching,” “deferring,” “forwarding,” “rescheduling,” “marking,” or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.