News Column

Patent Issued for Adaptive Partitioning Scheduler for Multiprocessing System

January 30, 2014



By a News Reporter-Staff News Editor at Computer Weekly News -- According to news reporting originating from Alexandria, Virginia, by VerticalNews journalists, a patent by the inventor Danko, Attilla (Ottawa, CA), filed on April 7, 2008, was published online on January 14, 2014.

The assignee for this patent, patent number 8631409, is QNX Software Systems Limited (Ottawa, Ontario, CA).

Reporters obtained the following quote from the background information supplied by the inventors: "The present invention is directed to a manner in which a processing system schedules the running of threads and the like. More particularly, the invention is directed to a system having adaptive partition scheduling for process threads.

"The kernel of an operating system may divide CPU resources so that each thread that is active in the system obtains an amount of CPU time to execute the corresponding process. The kernel may implement a scheduling system that determines how the available CPU time is allocated between multiple threads.

"There are various types of process scheduling systems: a FIFO scheduling system; a round-robin scheduling system; and a sporadic scheduling system. In each system, a priority value may be assigned to each thread of a process that is executed by the CPU. High priority values are assigned to threads that may be important to the operation of the overall system while threads that may be less important to the operation of the system may have lower priority values. Whether the scheduling system gives a thread access to the CPU may also depend on the state of the thread. A thread may be ready or blocked (although other states also may be used). A thread may be ready for execution when conditions for it to run have been met. A thread may be blocked when it tries to initiate an operation that cannot be completed immediately. A blocked thread may wait for the completion of some event before going to a ready or running state.

"In some operating systems, each thread in the system may run using any of the foregoing scheduling systems. The scheduling systems may be effective on a per-thread basis for all threads and processes on a node. Each thread may be assigned to a particular scheduling system type through the operation of the process/thread itself. This may provide the software designer with a degree of design flexibility. However, it may also involve a need for coordination between software designers implementing code for the same system. This coordination includes the assignment of priorities to the different threads as well as the scheduling system type assigned to each thread.

"While the foregoing scheduling systems have advantages in different applications, they may experience deficiencies when used in certain system applications. When per-thread scheduling systems are used in real-time systems where the latencies of a process/thread have been planned solely through the assignment of priority levels, very long latencies for low-priority threads may occur. Malicious software processes may configure themselves for high priority execution and may preempt proper scheduling of lower priority threads. This problem also may occur during system development when a high priority thread malfunctions and enters an infinite loop. Global fair-share scheduling systems may avoid such problems, but lack the responsiveness needed for use in a real-time system. These scheduling systems may be more problematic when implemented in a multiprocessing system, such as a bound multiprocessing system."

In addition to obtaining background information on this patent, VerticalNews editors also obtained the inventor's summary information for this patent: "A symmetric multiprocessing system includes multiple processing units and corresponding instances of an adaptive partition processing scheduler. Each instance of the adaptive partition processing scheduler selectively allocates the respective processing unit to run process threads of one or more adaptive partitions based on a comparison between merit function values of the one or more adaptive partitions. The merit function for a particular partition of the one or more adaptive partitions may be based on whether the adaptive partition has available budget on the respective central processing unit. The merit function for a particular partition associated with an instance of the adaptive partition scheduler also, or in the alternative, may be based on whether the adaptive partition has available global budget on the symmetric multiprocessing system.

"Other systems, methods, features and advantages of the invention will be, or will become, apparent to one with skill in the art upon examination of the following figures and detailed description. It is intended that all such additional systems, methods, features and advantages be included within this description, be within the scope of the invention, and be protected by the following claims."

For more information, see this patent: Danko, Attilla. Adaptive Partitioning Scheduler for Multiprocessing System. U.S. Patent Number 8631409, filed April 7, 2008, and published online on January 14, 2014. Patent URL: http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO2&Sect2=HITOFF&p=11&u=%2Fnetahtml%2FPTO%2Fsearch-bool.html&r=523&f=G&l=50&co1=AND&d=PTXT&s1=20140114.PD.&OS=ISD/20140114&RS=ISD/20140114

Keywords for this news article include: QNX Software Systems Limited.

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC


For more stories covering the world of technology, please see HispanicBusiness' Tech Channel



Source: Computer Weekly News


Story Tools