Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
2000-06-30
2004-04-13
Banankhah, Majid A. (Department: 2127)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C718S100000, C718S104000, C718S105000
Reexamination Certificate
active
06721948
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates to task management in a data processing system, and specifically to allocation of a shared resource among multiple competing requests.
2. Background Art
In general, in the descriptions that follow, I will italicize the first occurrence of each special term of art which should be familiar to those skilled in the art of communication system security. In addition, when I first introduce a term that I believe to be new or that I will use in a context that I believe to be new, I will bold the term and then provide the definition that I intend to apply to that term. In addition, throughout this description, I will use the terms assert and negate when referring to the rendering of a signal, signal flag, status, bit or similar apparatus into its logically true or logically false state, respectively.
Within a data processing system, the various hardware resources are usually controlled by low-level software modules, sometimes called drivers. Basic system functions, on the other hand, such as file or memory management, are performed by mid-level software modules that, in turn, may rely upon one or more of the drivers for actual hardware support. System level functions, such as application and transaction management, are coordinated by upper-level software modules that may themselves rely upon one or more of the lower level modules for support. This hierarchy of system software modules is usually referred to as a operating system or OS. In general, an application program, such as a word processor or a browser, is comprised of one or more high-level modules which may, in the course of their execution, invoke either other application modules or OS modules, as needed, to perform specific functions.
The general process of module invocation and termination, usually referred to as task management, is coordinated by specific operating system modules, collectively referred to as the Task Manager or TM. From the perspective of the TM, a task can be any software module, system or application, that performs a designated function and has regular structured input and regular structured output. For example, so long as an executing module (a requesting task) can construct the appropriate request to the TM to initiate a particular task (a requested task), the requesting task doesn't care whether the requested task accomplishes that request entirely in software, entirely in hardware, or in a combination of software and hardware. From the perspective of the requesting task, therefore, all lower level support tasks, whether software, hardware or both, can be considered as resources. Task management is thus just a particular form of resource management.
In multi-tasking data processing systems, multiple processes can be active simultaneously, although in a single processor system, only one of the active processes will be in control of the processor at any point in time. By way of example, assume that, at a particular point in time, a Process_A is in control of the processor, and, in particular, that a Task_X of Process_A has just issued a request to the TM that Task_R be performed. Assume also that, since Task_R will take a relatively significant time to complete and that Task_X cannot proceed until Task_R is completed, the TM will take control of the processor away from Task_X of Process_A and give it to, perhaps, a Task_S of a Process_B. Finally, assume that, before Task_R completes the request from Task_X of Process_A, Task_S also requests that Task_R be performed. If, due to the nature of Task_R only one instant can be active at a particular point in time, then a resource conflict has occurred. A typical example is where Task_R “owns” exclusive rights to exploit a unique hardware or software component of the system. Access to Task_R must therefore be shared. This shared resource allocation problem can be further complicated if, for any of a number of valid reasons, each process (or each task within each process) is assigned a relative priority: what is to happen, for example, if Process_B has been assigned a higher priority than Process_A?
FIG. 1
illustrates a conventional data processing system
2
having a central processing unit or CPU
4
coupled to multiple special function units or SFUs, via a communication bus
6
. Any of a variety of functions may be implemented by SFU
1
8
and SFU
2
10
, including arithmetic functions, logical functions, multimedia functions, etc. Each of SFU
1
8
and SFU
2
10
may perform a single function, or may perform multiple functions. Additionally, the data processing system
2
includes a resource
12
, which may be another processor, a memory, or any other device accessed by data processing system
2
. Within a memory
14
is located an OS
16
, and at least one application program
18
. Each application program
18
includes a scheduling block, and multiple tasks, such as Task_
1
and Task_
2
. Depending upon various system resource constraints and workload demands, additional application programs (not shown) may be simultaneously active in the memory
14
.
Various operating scenarios of the data processing system
2
, according to the prior art, are illustrated in
FIGS. 2-4
. In Case I, illustrated in
FIG. 2
, OS
16
initiates a Process_A (“Start_A”), which may be either an application or system module. During execution, Process_A makes a request to the OS (“A_Request_R”) for use of a shared resource, R, such as a particular shared task resident in the memory
14
or perhaps the resource
12
. At this time, OS
16
initiates operation of the shared resource R (“A_Start_R”), which proceeds to perform its designated function. Upon initiating R, OS
16
stores information to identify Process_A as the current process utilizing resource R. While R is running, Process_A may perform other operations until some result or response from R is required (“A_Read_R”). If R is not yet completed, Process_A must wait (indicated in
FIG. 2
by the dashed vertical time line). Upon completion, R sends a response to the waiting Process_A (“R_Response_A”), and Process_A is then able to continue. Simultaneously, R notifies OS
16
(“R_Stop_A”) that it has completed Process_A's request. When Process_A finally completes its operation, it notifies the OS
16
(“A_Stop”).
FIG. 3
illustrates another prior art scenario, Case II, that is similar to Case I, except that a Process_B is initiated (“Start_B”) after Process_A has been initiated (“Start_A”). During execution, Process_B also makes a request to OS
16
(“B_Request_R”) for the use of resource R. At the time of this request, R is still performing the request from Process_A. If OS
16
has no mechanism for resolving the conflict or if both Process_A and Process_B have the same or lower priority, Process_B must wait until R completes Process_A's request. Once R notifies OS
16
(“R_Stop_A”) that it has completed the request of Process_A, OS
16
promptly initiates R for Process_B (“B_Start_R”). When resource R completes Process_B's request, it sends a response to the waiting Process_B (“R_Response_B”), which may now continue. Simultaneously, R notifies OS
16
(“R_Stop_B”) that it has completed Process_B's request. For simplicity, the ultimate completions of Process_A and Process_B have not been shown.
FIG. 4
illustrates still another prior art scenario, Case III, in which Process_B has been assigned a higher priority than Process_A. In this case, when Process_B requests R (“B_Request_R”), OS
16
immediately initiates R for Process_B (“B_Start_R”), thereby interrupting the operation of R for Process_A. When R completes, it sends a response to Process_B (“R_Response_B”), and, simultaneously, notifies OS
16
(“R_Stop_B”) that Process_B's request is complete. At that time, OS
16
reinitiates R for Process_A (the second “A_Start_R”).
As can be readily seen, the Case III allocation policy may result in significant loss in system performance, due to the wasted time spent by R servicing the interrupted request of Process_A. In
Banankhah Majid A.
Equator Technologies Inc.
Myers Jeffrey Van
LandOfFree
Method for managing shared tasks in a multi-tasking data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for managing shared tasks in a multi-tasking data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for managing shared tasks in a multi-tasking data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3255918