Invention Grant
- Patent Title: Program scheduler for processing systems
- Patent Title (中): 程序处理系统的程序设计
-
Application No.: US3648253DApplication Date: 1969-12-10
-
Publication No.: US3648253APublication Date: 1972-03-07
- Inventor: MULLERY ALVIN P , ZURCHER FRANK W JR
- Applicant: IBM , BURROUGHS CORP
- Assignee: Ibm,Burroughs Corp
- Current Assignee: Ibm,Burroughs Corp
- Priority: US88398369 1969-12-10
- Main IPC: G06F9/48
- IPC: G06F9/48 ; G06F9/18
Abstract:
A program scheduler is provided for use with a multiprocessor system or its equivalent, such as a multiprogrammed processor unit, and the program scheduler receives tasks to be executed, schedules them for assignment, allots a task to each processor and interrupts the processors to assign new tasks. The program scheduler includes a plurality of buckets or tables where task words are stored, and associated with each task word is a Te field which specifies the estimated processor time required to complete the task and a Td field which indicates the time remaining before the task must be completed. The ratio Te/Td provides an indication of the need of each task word for processor service since the need for such service becomes more urgent as the ratio approaches 1. A scheduling algorithm periodically recalculates the service ratio and shifts tasks, if need be, from one table to another whereby tasks with a similar service ratio are stored in a common table. Task words within a given table are divided into classes according to the length of time a task has not received service. An allocation algorithm allots tasks to processors from the older classes first and proceeds in sequence through the various classes to the latest classes. Both the scheduling algorithm and the allocation algorithm service all tables in the program scheduler, but the tables with higher service ratios are serviced more often by each algorithm than tables with lower service ratios. When many task words are awaiting processor service, a given task word receives processor service at a rather low frequency when it has a small service ratio, but it receives processor service at a relatively high frequency as its service ratio approaches 1.
Information query