Unisys Corporation

James W Willen

Hans Christian Mikkelsen

Michael F Stanton

James F Merten

Peter John Hancock

Robert Morris

John Carter

Driving task dispatching by an operating system in a multiprocessor computer system is accomplished with a virtual switching queue which accepts highest priority tasks from multiple switching queues which in turn are accessed by instruction processors seeking tasks. Overload, plucking and stealing of tasks may be used to effectively balance load within the computer system. Dynamic reconfiguration used where regular queues lose underlying instruction processors.

Computer OS dispatcher operation with virtual switching queue and IP queues

Regardless of the switching queue organization, enhanced multiprocessor factor performance for software application group is accomplished via allocation of cache neighborhoods to software application groups that share memory space as identified by a user. Certain user requirements may be refused as unavailable to protect overall performance. Exclusivity and priority requirements of a user can also be honored by the operating system. Load balancing and dynamic reconfiguration features respect software application group dedications to the extent feasible.

Computer OS dispatcher operation with user controllable dedication

This invention provides to large-scale operating systems supporting multiple classes of tasks a method to allocate processor resources to the classes according to a probability model. It is useful in preventing a class from being denied resources by giving it positive measure in the model. A first stage probability algorithm assigns classes of tasks to an IP resource available to a given scheduler queue. Each class is allocated a probability level in a lottery-type draw in this first stage. In preferred embodiments, a second stage probability algorithm is used to assign tasks within a class to an available processor resource. This second stage algorithm is biased in a feedback manner by task resource usage history. Tasks of extreme high or low priority may avoid the probabilistic mechanisms in preferred embodiments.

Operating system scheduler/dispatcher with randomized resource allocation and user manipulable weightings

An Operating System (OS) function maps affinity to processors for each new task and except for certain circumstances where other processors are permitted to steal tasks, this affinity remains unchanged. Hierarchical load balancing is mapped through an affinity matrix (that can be expressed as a table) which is accessed by executable code available through a dispatcher to the multiplicity of instruction processors (IPs) in a multiprocessor computer system. Since the computer system has multiple layers of cache memories, connected by busses, and crossbars to the main memory, the hierarchy mapping matches the cache memories to assign tasks first to IPs most likely to share the same cache memory residue from related tasks, or at least less likely to incur a large access time cost. Each IP has its own switching queue (SQ) for primary task assignments through which the OS makes the initial affinity assignment. When an IP's SQ becomes task free, the dispatcher code has the free IP look to the SQ of other IPs in accord with the mapped hierarchy, if a threshold of idleness is reached.

Growing community of inventors

Shoreview, MN, United States of America

James W Willen