Adaptive scheduler using inherent knowledge of operating system subsystems for managing resources in a data processing system

Method, system and computer program product for managing resources in a data processing system. Knowledge provided by each subsystem of a plurality of subsystems of an operating system regarding behavior of the subsystem is shared by other subsystems of the operating system, and the shared knowledge, together with existing functional characteristics of the subsystems is used by the operating system to more efficiently manage resources in the data processing system.

TECHNICAL FIELD

The present invention relates generally to the data processing field and, more particularly, to a method, system and computer program product for managing resources in a data processing system.

DESCRIPTION OF RELATED ART

The various subsystems of a modern operating system (OS), for example, scheduler, input/output (I/O) subsystem, memory management subsystem, process management subsystem, inter-process management subsystem, synchronization infrastructure, etc., operate both independently and cooperatively during processes of managing resources of a data processing system. Recent enhancements to improve the efficiency of resource management include fine-grained resource partitioning and support for classes of work assigned with different qualities of service (QoS), Fairshare Scheduler and the like. In general, these enhancements seek to improve resource management efficiency by more efficiently managing the workload of the operating system.

In particular, workload management enhancements provide the operating system with “clues” so that the operating system will give preferential treatment to different categories or classes defined by a user. These enhancements generally help the operating system in scheduling applications and users, but are not directed to enhancing the resource management processes themselves.

Issues encountered in multimedia applications and in other applications in real-time operating system environments have led to a number of studies directed to improving the management of data processing system resources. Some of these studies have led to the concept of applications providing “hints” to the scheduler to assist the scheduler in scheduling applications. For example, the relationship between tasks in a multimedia application can be used by the scheduler to schedule tasks in a particular sequence to fully process a single picture frame. However, none of the scheduling algorithms consider the use of heuristics or other data that can be collected by the OS subsystems during execution of an application to provide hints to the scheduler to enable the scheduler to schedule tasks more efficiently.

Studies have also been conducted on extensible operating systems where applications modify kernel behavior by providing mechanisms for application code to run in the kernel address space. This procedure enables applications to modify the kernel to improve application performance. The internal workings of the kernel and knowledge accrued from various kernel subsystems are used to extend the kernel behavior to improve performance.

In this context of extensible operating systems, studies have been also been conducted to determine which parts of the operating system to extend, based on self-monitoring by the operating system and self-adapting techniques. This procedure is generally similar to the workload management procedures described above.

Yet other studies have addressed the issue of minimizing the end-to-end latency of applications that are structured as a set of cooperating (real-time) tasks. In this approach, the scheduler is provided with information on the inter-process communication interconnections between tasks of the applications, and uses this information to guarantee an end-to-end latency for applications that is a function of the timing properties of the application, not kernel subsystem knowledge.

In general, although existing operating systems may build heuristics to incorporate some of the information that OS subsystems accrue during the course of executing applications, store the information and then use the information to some extent, the information is only used in the same subsystem that gathered the information.

It would, accordingly be advantageous to provide a procedure for managing resources in a data processing system in which knowledge provided by each subsystem of a plurality of subsystems of an operating system regarding behavior of the subsystem is shared with other subsystems of the operating system, and used by the operating system to efficiently manage resources in the data processing system.

SUMMARY OF THE INVENTION

The present invention provides a method, system and computer program product for managing resources in a data processing system. Knowledge provided by each subsystem of a plurality of subsystems of an operating system regarding behavior of the subsystem is shared with other subsystems of the operating system, and the shared knowledge, together with existing functional characteristics of the subsystems is used by the operating system to more efficiently manage resources in the data processing system.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

As another example, data processing system300may be a stand-alone system configured to be bootable without relying on some type of network communication interfaces As a further example, data processing system300may be a personal digital assistant (PDA) device, which is configured with ROM and/or flash ROM in order to provide non-volatile memory for storing operating system files and/or user-generated data.

The present invention provides a technique for managing resources in a data processing system that utilizes inherent knowledge acquired by subsystems of an operating system during operation of the operating system (heuristic knowledge), together with existing functional characteristics of the subsystems. More particularly, an operating system of a data processing system efficiently manages resources in a data processing system by:1. acquiring and storing knowledge about the behavior of each of a plurality of subsystems of the operating system,2. sharing the acquired knowledge about the behavior of each of the plurality of subsystems with other subsystems of the plurality of subsystems, and3. using the shared knowledge along with functional characteristics of the plurality of subsystems to efficiently manage data processing system resources.

FIG. 4is a flowchart that illustrates a method for managing resources in a data processing system in accordance with a preferred embodiment of the present invention. The method relates to managing resources in a data processing system by utilizing inherent knowledge involving hard disk or network input/output (I/O) subsystems of an operating system of the data processing system to assist a scheduler in scheduling tasks. The inherent knowledge includes knowledge that any data operations (read or write) will eventually access external I/O devices, which leads to a waiting state for the operations (tasks), and inherent knowledge that the fulfillment of I/O requests is driven by interrupts. This inherent knowledge about the hard disk or network or any I/O subsystems is used to improve the efficiency of managing resources in a multiprocessor data processing system in which the CPU (Central Processing Unit) that processes the interrupt is different than the CPU where the task is waiting for data. In particular, by utilizing the inherent information, the scheduler may try to schedule the two tasks on the same CPU. This will improve the memory latency as the data is already loaded into the CPU where the data is processed first (part of the interrupt processing).

The method illustrated inFIG. 4is generally designated by reference number400, and includes both the process context and the interrupt context of the method. The process context starts by the OS creating a task and assigning a particular CPU to run the task (step402). A read data instruction is then issued (step404) instructing to obtain data from an I/O device (step406). Create an association between the socket of the network connection and the CPU where the connection originated. This knowledge is used by the interrupt subsystem while routing the interrupts to CPUs. A determination is then made whether the data is readily available (step408). If the data is readily available (Yes output of step408), the data is obtained from the network interface (step406). If the data is not readily available (No output of step408), the task is put into a wait queue (step410) to wait for the data to be available. A flag (WAIT_FOR_DATA) is set in the task structure indicating that the task is waiting for a prior task to complete to receive the data.

In the interrupt context, an interrupt is received (step420), and the CPU is checked for socket association (step422). A determination is then made if there is a CPU match, that is, the CPU where the interrupt was processed is the same CPU where the socket is associated (step424). If there is a match (Yes output of step424), a process to wake-up the waiting task is processed (step426). If there is not a CPU match (No output of step424), a request to change the CPU of the wakee and to wake-up the waiting task is processed (step428). During the wake-up, the scheduler checks the flag (WAIT_FOR_DATA) to see if the task is waiting for data. The scheduler then schedules the waiting task on the same CPU as the wakee (the caller of the wakeup). This is because the wakee most likely processed the I/O to completion. The WAIT_FOR_FLAG is then reset to assure that the data processed by the wakee is already in the computer cache so when the waiting task is woken up, the data does not have to be fetched again.

FIG. 5is a flowchart that illustrates a method for managing resources in a data processing system in accordance with a further preferred embodiment of the present invention. The method relates to a situation in which different applications share a common memory area. The memory management subsystem of the operating system is aware of this situation (inherent knowledge), and the scheduler uses this information to try to schedule the related tasks on the same CPU to reduce memory latency.

The method illustrated inFIG. 5is generally designated by reference number500and, after starting (step502), a determination is made if an application uses a shared memory with another application (step504). If not, (No output of step504), the OS chooses a CPU that is not assigned to run the application (step508). The determination as to whether an application shares a memory with another application utilizes inherent knowledge of a memory manager subsystem that stores the name of the shared memory, i.e., “mem/game/seg”, in the task structure of the task that allocated or tried to share the memory. In addition, the address of the tasks that share this memory are stored in the task structure in a doubly linked list. For example, if three tasks tried to share the same memory, then the three associated task structures will have the shared segment name.

If the determination of step504is in the affirmative (Yes output of step504), a determination is made if another process is using the same memory (step506). If not, (No output of step506), a CPU is chosen that is not assigned and the process is run (step508). If another process is using the memory (Yes output of step506), the process is assigned the same CPU as the other process that shares the memory (step510). The determination of whether another process is using the same memory is made by checking the list that lists all processes that share the same memory.

After the process has been assigned to the same CPU in step510, the scheduler schedules the process to run on the assigned CPU (step512) and the method ends.

FIG. 6is a flowchart that illustrates a method for improving efficiency of workload management in accordance with another preferred embodiment of the present invention.FIG. 6relates to a situation where three tasks that share the same memory area try to serialize access to a piece of memory in the shared area, and cause a contention. In particular, if there is a critical section in the shared memory area, the scheduler may choose to schedule the contending tasks in sequence. In this case, the scheduler needs to work with a synchronization subsystem of the operating system to use the synchronization subsystem's knowledge of resource contention of the tasks. This will enable other runnable tasks that do not have contention to use the CPU cycles.

The method illustrated inFIG. 6is generally designated by reference number600, and, after starting (step602), allocates a shared segment of memory to be shared by a plurality of applications (step604). The memory manager stores the name of the shared memory, i.e., “mem/game/seg”, in the task structure of the task that allocated or tried to share the memory. In addition, the address of the tasks that share this memory are stored in the task structure in a doubly linked list. For example, if the three tasks try to share this memory, then the three associated task structures will have the shared segment name.

If the three tasks try to serialize access to a piece of memory in this shared segment that will cause contention. This contention can be recorded or stored in the task structure with a wait state token, along with the shared memory name. That is, “critical_selection_wait” can be set in the task structure. However, there are cases where tasks might try to use try_to_get to get the lock. If the attempt fails, the task might use yield or other mechanisms instead of going to the wait state as part of the contention. In such cases, a “yield_wait_for_shared_mem” flag can be set in the task structure. The scheduler, having known that the task is yielding because it is waiting for a resource, can defer scheduling that task if the owning task has not released the lock. This is because the scheduler can quickly traverse the links to see if the lock is released.

In particular, when an application seeks access to the memory segment (step606), a determination is made if a critical section exists (step608). If no (No output of step608), access is granted (step620). If Yes (Yes output of step608), a determination is made if the lock is free (step610). If the lock is free (Yes output of step610), the lock is acquired (step612), and access is granted (step620). If the lock is not free (No output of step610), the application uses a yield mechanism to try to gain access instead of going into a wait state (step614). If so, a check is conducted to see if it is holding the lock (step616).

The determination of whether an application is holding a lock involves checking the list of tasks that share the memory segment, checking the list of tasks from the list waiting for the lock, and based on the checks, applying the appropriate yield policy. The process is then scheduled based on its lock priority (step618), and the method ends.

The present invention can also be used in numerous other situations to manage resources in a data processing system. For example, the invention can be used where tasks that are running within an operating system have a relational dependency, i.e., one task is waiting for another task to be completed. This inherent knowledge can be derived using an inter-process communication subsystem of the operating system. For example, when a task A must wait for a task B to be completed, the scheduler can schedule task A first and then task B may be on the same CPU in a multiprocessor system.

The present invention thus provides a technique for managing resources in a data processing system in which knowledge provided by each subsystem of a plurality of subsystems of an operating system regarding behavior of the subsystem is shared with other subsystems of the operating system, and the shared knowledge is used by the operating system to more efficiently manage resources in the data processing system. The technique in accordance with the present invention can be used alone or in conjunction with other efficiency enhancing techniques, such as workload management enhancement techniques, to more efficiently manage resources of the data processing system.