Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
2000-06-15
2004-08-31
Harvey, Jack B. (Department: 2142)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C709S229000, C709S240000, C718S106000
Reexamination Certificate
active
06785889
ABSTRACT:
REFERENCE TO COMPUTER PROGRAM LISTING APPENDIX
The following computer program listing including Universal Modeling Language (UML) diagrams showing instructions, regulation of work flow, the detailed design of the scheduler and relationships between objects in the computer program is submitted on a compact disc and is incorporated herein by reference:
NAME
CREATION DATE
SIZE (bytes)
Appendix A
Dec. 30, 2003
4.46 MB
BACKGROUND OF THE INVENTION
1. Field of the Invention
The field of the invention relates in general to a scheduler for allocating digital device bandwidth resources. More particularly, the field of the invention relates to a system and method for allocating and scheduling digital device bandwidth resources among users and groups of users by using an active feedback estimator which guarantees a system bandwidth requirement among competing users and aggregate user groups.
2. Background
Computer Operating Systems are growing in complexity. Most new computers and devices using computational devices are performing many different tasks simultaneously. This sharing of resources affects machine performance and user satisfaction. Typically the operating system (OS) is responsible for scheduling when each process runs. When a process has reached its allotted time slice, or blocks for some reason, the OS saves its state and runs the next runnable process in the process queue. This gives the appearance of many different programs running simultaneously on a single processor. This is currently extended to multiple processors, which handle even more processes simultaneously. This in turn requires more programs demanding more system resources running simultaneously.
The two main process scheduling classes are real-time and time-sharing. Current process schedulers have a basic overall goal; to make the “system” more productive. The achievement of that goal requires the balancing of the following different requirements:
allocate a fair share of CPU time to each process;
keep the CPU busy 100 percent of the time;
minimize the response time for time sensitive processes;
minimize total job completion time;
maximize total number of jobs per time unit.
To achieve this balance, schedulers make some assumptions about the type of processes that are running. The default system scheduler may frequently not be adequate to suit the application. Many scheduling algorithms and their implementations have been developed over the years to shore up deficiencies in attempts to build better schedulers.
Some operating systems use a two-level thread implementation, where threads within a process are first scheduled to a virtual processor which in turn are scheduled on the physical processors. Thus, the threads are bound to a particular virtual processor and the scheduling characteristics are resultants of the scheduling of the virtual processor.
The OS community has developed many optimal scheduling algorithms, but all algorithms are optimal only for certain workloads. There is currently no single solution that fits every system need. General-purpose operating systems face the problem of developing schedulers that are general enough to solve most needs, yet extensible enough to handle specific workloads.
There are many different algorithms for choosing the next process to run. Two of the most common scheduler algorithms are First-In-First-Out (FIFO) and Round Robin (RR).
FIFO runs each process until its completion and then loads the next process in the queue. FIFO can have negative affects on systems when processes run for an extended time, squeeze critical resources that otherwise keep the system stable to the point of no return, and then crash the system or initiate a sequence of events to crash the system.
Round Robin schedulers allow each process at a given priority to run for a predetermined amount of time called a quantum. When the process has run for the allotted time quantum, or if a higher priority process becomes runnable, the scheduler halts the process and saves its state. It is then placed at the end of the process queue and the next process is started. This may be the most optimal solution if the time quantum is longer than the average runtime of a process and the only resource needed is CPU bandwidth. These are very unlikely to be the case in the typical process load mix and therefore the need for a better algorithm to fill all requirements and to smooth out the workload over available resources. Also, context switching between different processes has a price and we much consider the overhead in context switching time of changing processes in conjunction with the more complex scheduling algorithms.
OS developers have created multilevel queue scheduling to meet the needs for different algorithms at different times. Multilevel queue systems have several algorithms used simultaneously. Each queue is assigned a priority over the next queue. The scheduler starts at the highest priority queue, implements the queue's algorithm until no runnable processes remain, and then proceeds to the next priority queue. One queue could use FIFO with another uses RR.
When implementing a conventional real-time scheduler, a problem known as priority inversion frequently arises. This occurs when a higher priority process is blocked waiting for a resource locked by a lower priority process. This problem has only partial solutions. One is by implementing a priority inheritance protocol. A process that “owns” a resource runs at the priority of the highest priority process that is awaiting that resource requested by a higher priority process. When the lock is released, the higher priority process becomes runnable and pre-empts the current process. This means that the algorithm selected can affect the performance of the application, and choosing the right algorithm can improve the system performance. What is needed is a system for setting priorities and quanta which are more likely to be the ones needed for the type of job mixes, users and applications which are presently emerging; and which will provide higher performance and more consistant service.
Whatever algorithm is used, changing the scheduling class of a server application, can guarantee that the server application will run before other applications and thus improve responsiveness for that particular application. However, this does nothing to guarantee that a particular application will only consume a specified portion of the CPU load, only that the application will be treated preferentially in allocating resources. What is needed is a way to track historic usage of an application or group of applications and guarantee that over a certain time period, the use of bandwidth resources is precisely that which was set initially, unless there is an available abundance of bandwidth, and no such constraints need be applied.
Process Schedule Configuration
The general purpose OS will not function if the scheduler is not configurable or even modifiable. Most OS vendors have compensated for this problem in several ways. Some provide utilities to view the default scheduling classes and allow changing the process priorities and quanta. In UNIX, these types of utilities have names like “nice”, “sched_setscheduler” or “priocntl”. Special privileges are generally needed to run a process at a higher priority or change the scheduler for a process from the real-time class or the time-sharing class. These generally manipulate the real-time dispatcher parameter table or time-sharing dispatcher parameter table. Servers and computers in general have grown bigger and more powerful.
Conventional solutions have thus grown disadvantageously larger in granularity and they lack the precision to handle the large resources that they command. The granularity of the changes can very often make precise goal achievement impossible with these solutions. What is needed are methods to allow users increased access to and more precise control over the allocation of CPU resources than is provided by the conventional “nice” and “priocntl” mechanisms. What is also needed are CPU and resource bandwi
Aurema, Inc.
Harvey Jack B.
Hetherington Michael
Nguyen Hai V.
Ulman Nick
LandOfFree
System and method for scheduling bandwidth resources using a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for scheduling bandwidth resources using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for scheduling bandwidth resources using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3334442