US007451447B1
`
`(12) United States Patent
`Deshpande
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7.451.447 B1
`Nov. 11, 2008
`
`(54) METHOD, COMPUTER PROGRAMAND
`APPARATUS FOR OPERATING SYSTEM
`DYNAMIC EVENT MANAGEMENT AND
`TASK SCHEDULING USING FUNCTION
`CALLS
`
`(*) Notice:
`
`(75) Inventor: Akash R. Deshpande, San Jose, CA
`(US)
`(73) Assignee: ARC International IP, Inc., San Jose,
`CA (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 656 days.
`(21) Appl. No.: 10/669,542
`(22) Filed:
`Sep. 23, 2003
`Related U.S. Application Data
`(63) Continuation of application No. 09/370,618, filed on
`Aug. 7, 1999, now abandoned.
`(60) Provisional application No. 60/095,637, filed on Aug.
`7, 1998.
`
`(51) Int. Cl.
`(2006.01)
`G06F 9/46
`(2006.01)
`G06F 9/48
`(2006.01)
`G06F 9/50
`(2006.01)
`G06F 9/54
`(52) U.S. Cl. ........................ 718/102: 718/103; 71.9/318
`(58) Field of Classification Search ................. 719/318;
`718/101 103
`See application file for complete search history.
`References Cited
`
`(56)
`
`U.S. PATENT DOCUMENTS
`
`1, 1989 Carter et al.
`4,800,521 A
`9, 1993 Welland et al.
`5,247,677 A
`5,260,868 A 1 1/1993 Gupta et al.
`5,301,312 A
`4/1994 Christopher et al.
`5,465,335 A 11/1995 Anderson
`
`6/1996 Crump et al.
`5,530,879 A
`4/1997 Schultz et al.
`5,619,409 A
`6/1997 Rischar et al.
`5,636,124 A
`6/1997 Carmon
`5,640,563 A
`5,701,481 A 12/1997 Hosaka et al.
`5,781,187 A
`7/1998 Gephardt et al.
`5,872,909 A
`2f1999 Wilner et al.
`5,938,708 A
`8, 1999 Wallace et al.
`5,944,840 A
`8, 1999 Lever
`5,954,792 A * 9/1999 Balarin ....................... T18, 102
`6,061,709 A *
`5/2000 Bronte ....................... T18, 103
`6,105,048 A
`8, 2000 He
`6.279, 108 B1
`8/2001 Squires et al.
`6,341.303 B1
`1/2002 Rhee et al.
`6,349,321 B1
`2/2002 Katayama
`6,359,622 B1
`3/2002 Hayes-Roth
`6,385,637 B1
`5, 2002 Peters et al.
`6,385,638 B1
`5/2002 Baker-Harvey
`6.425,091 B1
`7/2002 Yang et al.
`6,434,590 B1* 8/2002 Blelloch et al. ............. T18, 102
`6,438,573 B1
`8, 2002 Nilsen
`
`OTHER PUBLICATIONS
`Kevin Jeffay and Charles U. Martel, “On Non-Preemptive Schedul
`ing of Periodic and Sporadic Tasks.” Dec. 1991, IEEE Computer
`Society Press, pp. 129-139.*
`(Continued)
`Primary Examiner Li B Zhen
`(74) Attorney, Agent, or Firm Ropes & Gray LLP
`
`(57)
`
`ABSTRACT
`
`Method, computer program, system and apparatus for oper
`ating system dynamic event management and task scheduling
`using function calls. Method, computer program product, and
`system for non-preemptively scheduling tasks in a computer
`system. Scheduler and Scheduling method that schedules
`tasks that are broken into a number of short actions, without
`preempting the actions as they are executed and without
`assigning a priority to tasks. Invention decreases the overhead
`as compared to existing methods and systems.
`
`13 Claims, 8 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`or connection
`request
`
`SW or HW
`interrupt with
`ISR
`
`
`
`26a
`
`26
`
`Serve
`interrupt
`
`Serve
`interrupt
`
`identifiable
`component and
`transition
`
`
`
`Replace
`scheduled
`transition
`
`Step
`10
`
`Step
`28
`
`MICROCHIP TECH. INC. - EXHIBIT 1035
`MICROCHIP TECH. INC. V. HD SILICON SOLS. - IPR2021-01265 - Page 001
`
`

`

`US 7.451.447 B1
`Page 2
`
`OTHER PUBLICATIONS
`
`Deshpande, et al., “The Shift Programming Language for Dynamic
`Networks of Hybrid Automata'. IEEE Transactions. On Automatic
`Control, Apr. 1998, 43(4): 584-587.
`
`Deshpande, et al., “Viable Control of Hybrid Systems'. Hybrid Sys
`tems II. Springer 1995.
`Interrupt Driven Task Scheduler for Systems, IBM Technical Disclo
`sure Bulletin, Mar. 1992, US.
`* cited by examiner
`
`MICROCHIP TECH. INC. - EXHIBIT 1035
`MICROCHIP TECH. INC. V. HD SILICON SOLS. - IPR2021-01265 - Page 002
`
`

`

`U.S. Patent
`
`Nov. 11, 2008
`
`Sheet 1 of 8
`
`US 7.451.447 B1
`
`Request from a
`ra
`real-time process
`
`
`
`Real-time process added to run
`queue to await its next Slice
`
`Process 1
`
`Process 2
`
`ProCeSS in
`
`
`
`
`
`Real-time
`Process
`
`-- - -->
`Scheduling Time
`Clk
`Round-robin Preemptive Scheduler
`
`FIG. 1 A
`
`Request from a
`real-time process
`
`Real-time process added to head
`of run queue
`
`
`
`
`
`Real-time
`Current Process
`Process
`--> -------. Current process
`Scheduling Time
`blocked or completed
`Priority-driven Nonpreemptive Scheduler
`F.G. 1 B
`
`
`
`Eyes from a
`real-time process
`
`Wait for another
`preemption point
`
`
`
`sesses
`
`e
`
`Raine
`->
`Scheduling Time
`Preemption
`Point
`Priority-drive, Preemptive Scheduler
`on Preemption Points
`
`
`
`FIG 1 C
`
`Request from a
`real-time process
`
`Current Process
`
`Real-time process preempts current
`process and executes immediately
`Real-time
`Process
`
`K->
`Scheduling Time
`immediate Preemptive Scheduler
`
`FIG 1 D
`
`MICROCHIP TECH. INC. - EXHIBIT 1035
`MICROCHIP TECH. INC. V. HD SILICON SOLS. - IPR2021-01265 - Page 003
`
`

`

`U.S. Patent
`
`Nov. 11, 2008
`
`Sheet 2 of 8
`
`US 7.451.447 B1
`
`fOO
`
`f08
`
`104
`
`YN- 102
`
`FIG.2A
`
`FIG.2B
`
`
`
`
`
`
`
`
`
`
`
`
`
`event
`Senderd
`
`
`
`
`
`SenderName
`id
`
`
`
`Application
`Components
`
`Application
`Events
`
`Application
`Aerts
`
`FIG.3
`
`MICROCHIP TECH. INC. - EXHIBIT 1035
`MICROCHIP TECH. INC. V. HD SILICON SOLS. - IPR2021-01265 - Page 004
`
`

`

`U.S. Patent
`
`Nov. 11, 2008
`
`Sheet 3 of 8
`
`US 7.451.447 B1
`
`ldentify earliest
`proactive
`transition
`
`fO
`
`Scheduled
`transition
`
`Exits a
`transient state
`
`14
`
`Sp
`interrupt
`
`
`
`Sleep unit
`Scheduled
`transition
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Execute
`
`Waken
`by interrupt
`
`Update
`COntinuous
`States
`
`
`
`
`
`Obtain
`returned event
`
`
`
`Propagate
`returned event
`
`Post-execution
`processing
`(see Fig. 6)
`
`32
`
`34
`
`
`
`
`
`
`interrupt
`processing
`(see Fig. 5)
`
`26
`
`FIG.4
`
`MICROCHIP TECH. INC. - EXHIBIT 1035
`MICROCHIP TECH. INC. V. HD SILICON SOLS. - IPR2021-01265 - Page 005
`
`

`

`U.S. Patent
`
`Nov. 11, 2008
`
`Sheet 4 of 8
`
`US 7.451.447 B1
`
`Shell Command
`Or Connection
`request ?
`
`SW Or HW
`interg With
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 5
`
`26a
`
`26
`
`Serve
`interrupt
`
`Step
`10
`
`26d
`
`Serve
`
`26f
`
`26g
`
`
`
`identifiable
`component and
`transition ?
`
`Replace
`Scheduled
`transition
`
`Sp
`
`Sp
`
`
`
`Update
`discrete States
`
`34a
`
`returned events
`
`34b.
`
`
`
`FIG. 6 Slip Control
`
`
`
`
`
`34C
`
`34d
`
`Update database
`
`34e
`
`MICROCHIP TECH. INC. - EXHIBIT 1035
`MICROCHIP TECH. INC. V. HD SILICON SOLS. - IPR2021-01265 - Page 006
`
`

`

`U.S. Patent
`
`Nov. 11, 2008
`
`Sheet 5 of 8
`
`US 7.451.447 B1
`
`
`
`MICROCHIP TECH. INC. - EXHIBIT 1035
`MICROCHIP TECH. INC. V. HD SILICON SOLS. - IPR2021-01265 - Page 007
`
`

`

`U.S. Patent
`
`Nov. 11, 2008
`
`Sheet 6 of 8
`
`US 7.451.447 B1
`
`E
`
`SO
`
`S.
`
`S
`
`CN
`
`S.
`
`3.
`
`9.
`
`2
`
`S.
`
`O
`
`CN
`
`SD
`
`C
`
`SD
`'g
`
`20
`
`5
`
`S 83
`
`S 3
`
`MICROCHIP TECH. INC. - EXHIBIT 1035
`MICROCHIP TECH. INC. V. HD SILICON SOLS. - IPR2021-01265 - Page 008
`
`

`

`U.S. Patent
`
`Nov. 11, 2008
`
`Sheet 7 of 8
`
`US 7.451.447 B1
`
`FIG.9
`
`a
`
`\s.
`
`FIG.10A -
`
`|64
`
`{:
`72 aft
`" :
`{:
`{\54
`
`72
`
`FIG 10B
`
`|ca
`-es
`
`{:
`ft
`{
`
`Time
`
`Time
`
`Time
`
`MICROCHIP TECH. INC. - EXHIBIT 1035
`MICROCHIP TECH. INC. V. HD SILICON SOLS. - IPR2021-01265 - Page 009
`
`

`

`U.S. Patent
`
`Nov. 11, 2008
`
`Sheet 8 of 8
`
`US 7.451.447 B1
`
`8O - A-82)
`
`FIG. 11A
`
`.
`
`-D Time
`
`FIG-11B- : 84
`
`Time
`
`MICROCHIP TECH. INC. - EXHIBIT 1035
`MICROCHIP TECH. INC. V. HD SILICON SOLS. - IPR2021-01265 - Page 010
`
`

`

`US 7,451,447 B1
`
`1.
`METHOD, COMPUTER PROGRAMAND
`APPARATUS FOR OPERATING SYSTEM
`DYNAMIC EVENT MANAGEMENT AND
`TASK SCHEDULING USING FUNCTION
`CALLS
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This application is a continuation of and claims the benefit
`of priority to U.S. Utility patent application Ser. No. 09/370,
`618 filed Aug. 7, 1999; this application is also related to and
`claims the benefit of U.S. Provisional Application No.
`60/095,637 filed Aug. 7, 1998; each of which applications are
`incorporated by reference in their entirety.
`
`10
`
`15
`
`BACKGROUND OF THE INVENTION
`
`2
`cesses over I/O-bound processes. Stallings states that an
`improved FCFS may be implemented with a priority scheme,
`with a number of priority levels and a ready queue for each
`priority level.
`The round robin algorithm uses clocked preemption. The
`clock periodically generates an interrupt, upon which the
`currently running process is placed in the ready queue and the
`next ready process is selected on an FCFS basis. This may
`also be referred to as time slicing because each process is
`given a slice of time before being preempted. Stallings states
`that the principal design issue is the length of the time quan
`tum, or slice, to be used. If the quantum is very short, then
`short processes will move through the system relatively
`quickly. On the other hand, there is processing overhead
`involved in handling the clock interrupt and in performing the
`scheduling and dispatching function. (More detail regarding
`this overhead is discussed below with reference to context
`Switching.) Thus, Stallings concludes that very short time
`quanta should be avoided. Stallings states that one useful
`guide is that the time quantum should be slightly greater than
`the time required for a typical interaction. Stallings further
`states that a disadvantage to round robin is that processor
`bound processes tend to receive an unfairportion of processor
`time as compared to I/O-bound processes.
`The SPN algorithm is a nonpreemptive policy in which the
`process with the shortest expected processing time is selected
`next. One concernis that the required processing time of each
`process must be known or estimated.
`The SRT algorithm is a preemptive version of SPN. If a
`new process joins the ready queue with a shorter known or
`expected completion time than the currently-executing pro
`cess, the current process preempted and exchanged with the
`new process in the ready queue.
`In HRRN, a response ratio is dynamically calculated for
`each process, and when the current process completes or is
`blocked, the ready process with the greatest response ratio
`value is selected as the next process to execute. The response
`ratio is the time the process has been waiting plus its known or
`estimated processing time, divided by the known or estimated
`processing time.
`In feedback, the current process is interrupted periodically
`and is assigned to a lower priority queue. This results in a
`preference for newer, shorter processes, without having to
`know or estimate their processing times beforehand. The
`interrupt interval may be set longer for lower priority queues
`to help prevent starvation of a very long process. In addition,
`the priority of a process may be upgraded if it has not been
`executed for a while.
`As mentioned above, whenever one process replaces
`another to be executed, a process Switch (also called a context
`Switch) is executed. Stallings states that in a process Switch
`the operating system must make Substantial changes in its
`environment, as follows. First, the context of the processor
`must be saved, including the program counter and other reg
`isters. Second, the process control block of the currently
`running process must be updated, including changing the
`state of the process to another state and changing state infor
`mation fields. Third, the process control block of this process
`must be moved to an appropriate other queue. Such as the
`ready queue or the blocked queue. Fourth, another process
`must be selected and scheduled. Fifth, the process control
`block of the selected process must be updated. Sixth, the
`memory-management data structures may need to be
`updated, depending upon how address translation is man
`aged. Seventh, the context of the processor must be restored to
`that which existed at the time the selected process was last
`
`1. Field of the Invention
`The present invention relates to task Schedulers in operat
`ing systems for computing devices. In particular, the inven
`tion relates to schedulers for real-time operating systems.
`2. Description of the Related Art
`Real-time computing is becoming an increasingly impor
`tant discipline. The operating system, and in particular the
`scheduler, is perhaps the most important component of a
`real-time system. Examples of current applications of real
`time systems include control of laboratory experiments, pro
`cess control plants, robotics, air traffic control, telecommu
`nications, and military command and control systems. See
`generally William Stallings, OPERATING SYSTEMS: INTERNALS
`AND DESIGN PRINCIPLES 10-21, 129-32, 145-59,384-99,429-47
`(3d ed. 1998) (hereinafter “Stallings').
`Scheduling in General
`Before discussing, real-time scheduling, an introduction to
`scheduling algorithms for non-real-time systems will be
`given. The scheduling algorithms may be preemptive or non
`preemptive. According to Stallings, a nonpreemptive algo
`rithm is when a running process continues to execute until it
`terminates or blocks itself to wait for I/O or by requesting
`Some operating system service. A preemptive algorithm is
`when a running process that is currently executing may be
`interrupted and moved to the ready state by the operating
`system. The decision to preempt may be performed when a
`new process arrives, when an interrupt occurs that places a
`blocked process in the ready state, or periodically based on a
`clock interrupt.
`Stallings also states that a scheduling algorithm may also
`include prioritization. Each process is assigned a priority and
`the scheduler will always choose a process of higher priority
`over one of lower priority. Such a scheme may be imple
`mented with a number of ready queues, one for each priority
`level. When a process is ready it is placed in the appropriate
`queue. When the highest priority queue is empty the sched
`uler selects from the next highest priority queue.
`Stallings lists six general types of scheduling algorithms:
`first-come first-served (FCFS), round robin, shortest process
`next (SPN), shortest remaining time (SRT), highest response
`ratio next (HRRN), and feedback.
`The FCFS algorithm selects the process that has been wait
`ing the longest for service as the next process. This may also
`be referred to as first-in, first-out. As each process becomes
`ready it is placed in the ready queue, and the oldest is selected
`when the system has completed the previous process. Stall
`ings states that FCFS performs better for long processes than
`short ones, and that it tends to favor processor-bound pro
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`MICROCHIP TECH. INC. - EXHIBIT 1035
`MICROCHIP TECH. INC. V. HD SILICON SOLS. - IPR2021-01265 - Page 011
`
`

`

`US 7,451,447 B1
`
`3
`Switched out of the running state. Performing these changes
`requires overhead time, during which the processor cannot be
`used for running processes.
`Real-Time Scheduling
`Turning now to real-time scheduling, Stallings states that
`real-time computing may be defined as that type of comput
`ing in which the correctness of the system depends not only
`on the logical result of the computation, but also on the time
`at which the results are produced. We can define a real-time
`system by defining what is meant by a real-time process, or
`task. (As usual, terminology poses a problem, since various
`words are used in the literature with varying meanings. It is
`common for a particular process to operate under real-time
`constraints of a repetitive nature. That is, the process lasts for
`a long time and, during that time, performs some repetitive
`function in response to real-time events. Let us, for this sec
`tion, refer to an individual function as a task. Thus, the pro
`cess can be viewed as progressing through a sequence of
`tasks. At any given time, the process is engaged in a single
`task, and it is the process/task that must be scheduled.) In
`general, in a real-time system, some of the tasks are real-time
`tasks, and these have a certain degree of urgency to them.
`Such tasks are attempting to control or react to events that take
`place in the outside world. Because these events occur in “real
`time a real-time task must be able to keep up with the events
`with which it is concerned. Thus, it is usually possible to
`associate a deadline with a particular task, where the deadline
`specifies either a start time or a completion time. Such a task
`may be classified as hard or soft. A hard real-time task is one
`that must meet its deadline; otherwise it will cause undesir
`able damage or a fatal error to the system. A soft real-time task
`has an associated deadline that is desirable but not mandatory;
`it still makes sense to schedule and complete the task even if
`it has passed its deadline.
`Stallings further states that another characteristic of real
`time tasks is whether they are periodic or aperiodic. An ape
`riodic task has a deadline by which it must finish or start, or it
`may have a constraint on both start and finish time. In the case
`of a periodic task, the requirement may be stated as “once per
`period T or “exactly T units apart.”
`Characteristics of Real-Time Operating Systems
`Stallings states that real-time operating systems can be
`characterized as having unique requirements in five general
`areas: determinism, responsiveness, user control, reliability,
`and fail-soft operation.
`Stallings states that an operating system is deterministic to
`the extent that it performs operations at fixed, predetermined
`times or within predetermined time intervals. When multiple
`processes are competing for resources and processor time, no
`system will be fully deterministic. In a real-time operating
`system, process requests for service are dictated by external
`events and timings. The extent to which an operating system
`can deterministically satisfy requests depends first on the
`speed with which it can respond to interrupts and, second, on
`whether the system has sufficient capacity to handle all
`requests within the required time.
`Stallings further states that one useful measure of the abil
`ity of an operating system to function deterministically is the
`maximum delay from the arrival of a high-priority device
`interrupt to when servicing begins. In non-real-time operating
`systems, this delay may be in the range oftens to hundreds of
`milliseconds, while in real-time operating systems that delay
`may have an upper bound of anywhere from a few microsec
`onds to a millisecond.
`Stallings also states that a related but distinct characteristic
`is responsiveness. Determinism is concerned with how long
`
`40
`
`45
`
`4
`an operating system delays before acknowledging an inter
`rupt. Responsiveness is concerned with how long, after
`acknowledgment, it takes an operating system to service the
`interrupt. Aspects of responsiveness include the following:
`1. The amount of time required to initially handle the
`interrupt and begin execution of the interrupt service routine
`(ISR). If execution of the ISR requires a process switch, then
`the delay will be longer than if the ISR can be executed within
`the context of the current process.
`2. The amount of time required to perform the ISR. This
`generally is dependent upon the hardware platform.
`3. The effect of interrupt nesting. If an ISR can be inter
`rupted by the arrival of another interrupt, then the service will
`be delayed.
`Stallings still further states that determinism and respon
`siveness together make up the response time to external
`events. Response time requirements are critical for real-time
`systems, because Such systems must meet timing require
`ments imposed by individuals, devices, and data flows exter
`nal to the system.
`Stallings states that user control is generally much broader
`in a real-time operating system than in ordinary operating
`systems. In a real-time system, it is essential to allow the user
`fine-grained control over task priority. The user should be
`able to distinguish between hard and Soft tasks and to specify
`relative priorities within each class. A real-time system may
`also allow the user to specify Such characteristics as the use of
`paging or process Swapping, what processes must always be
`resident in main memory, what disk transfer algorithms are to
`be used, what rights the processes in various priority bands
`have, and so on.
`Stallings also states that reliability is typically far more
`important for real-time systems than non-real-time systems.
`Stallings further states that fail-soft operation is a charac
`teristic that refers to the capability of a system to fail in such
`a way as to preserve as much capability and data as possible.
`When a real-time system detects a failure, it will attempt
`either to correct the problem or minimize its effects while
`continuing to run. A related concept is stability, which means
`that in cases where it is impossible to meet all task deadlines,
`the system will meet the deadlines of its most critical, highest
`priority tasks, even it some less critical task deadlines are not
`always met.
`Stallings states that current real-time systems typically
`include the following features:
`1. Fast process or thread switch
`2. Small size (with its associated minimal functionality)
`3. Ability to respond to external interrupts quickly
`4. Multitasking with interprocess communication tools
`Such as semaphores, signals, and events
`5. Use of special sequential files that can accumulate data at
`a fast rate
`6. Preemptive scheduling based on priority
`7. Minimization of intervals during which interrupts are
`disabled
`8. Primitives to delay tasks for a fixed amount of time and
`to pause/resume tasks
`9. Special alarms and timeouts.
`Stallings asserts that the heart of a real-time system is the
`short-term task Scheduler. In designing Such a scheduler, fair
`ness and minimizing average response time are not important.
`What is important is that all hard real-time tasks complete (or
`start) by their deadline and that as many as possible soft
`real-time tasks also complete (or start) by their deadline.
`Stallings States that most contemporary real-time operat
`ing systems are unable to deal directly with deadlines.
`
`10
`
`15
`
`25
`
`30
`
`35
`
`50
`
`55
`
`60
`
`65
`
`MICROCHIP TECH. INC. - EXHIBIT 1035
`MICROCHIP TECH. INC. V. HD SILICON SOLS. - IPR2021-01265 - Page 012
`
`

`

`5
`Instead, they are designed to be as responsive as possible to
`real-time tasks So that when a deadline approaches, a task can
`be quickly scheduled. From this point of view, real-time
`applications typically require deterministic response times in
`the several-millisecond to submillisecond span under a broad
`set of conditions; leading-edge applications—in simulators
`for military aircraft, for example—often have constraints in
`the range of 10 to 100 us.
`Stallings provides the following description with reference
`to FIGS. 1A-1D to illustrate a spectrum of possibilities. In a
`preemptive scheduler that uses simple round-robin Schedul
`ing, a real-time task would be added to the ready queue to
`await its next time slice, as illustrated in FIG. 1A. In this case,
`the scheduling time will generally be unacceptable for real
`time applications. Alternatively, in a nonpreemptive sched
`uler, we could use a priority Scheduling mechanism, giving
`real-time tasks higher priority. In this case, a real-time task
`that is ready would be scheduled as soon as the current pro
`cess blocks or runs to completion (see FIG. 1B). This could
`lead to a delay of several seconds if a slow, low-priority task
`were executing at a critical time. Again, this approach is not
`acceptable. A more promising approach is to combine priori
`ties with clock-based interrupts. Preemption points occur at
`regular intervals. When a preemption point occurs, the cur
`rently running task is preempted if a higher-priority task is
`waiting. This would include the preemption of tasks that are
`part of the operating system kernel. Such a delay may be on
`the order of several milliseconds (see FIG.1C). While this last
`approach may be adequate for Some real-time applications, it
`will not suffice for more demanding applications. In those
`cases, the approach that has been taken is sometimes referred
`to as immediate preemption (see FIG. 1D). In this case, the
`operating system responds to an interrupt almost immedi
`ately, unless the system is in a critical-code lockout section.
`Scheduling delays for a real-time task can then be reduced to
`100 us or less.
`Stallings reports that a Survey of real-time scheduling algo
`rithms observes that the various scheduling approaches
`depend on (1) whether a system performs schedulability
`analysis, (2) if it does, whether it is done statically or dynami
`cally, and (3) whether the result of the analysis itself produces
`a schedule or plan according to which tasks are dispatched at
`run time. Based on these considerations, the Survey identifies
`the following classes of algorithms:
`1. Static table-driven approaches: These perform a static
`analysis of feasible schedules of dispatching. The result of the
`analysis is a schedule that determines, at run time, when a task
`must begin execution.
`2. Static priority-driven preemptive approaches: Again, a
`static analysis is performed, but no schedule is drawn up.
`Rather, the analysis is used to assign priorities to tasks, so that
`a traditional priority-driven preemptive scheduler can be
`used.
`3. Dynamic planning-based approaches: Feasibility is
`determined at run time (dynamically) rather than offline prior
`to the start of execution (statically). An arriving task is
`accepted for execution only if it is feasible to meet its time
`constraints. One of the results of the feasibility analysis is a
`schedule or plan that is used to decide when to dispatch this
`task.
`4. Dynamic best effort approaches: No feasibility analysis
`is performed. The system tries to meet all deadlines and aborts
`any started process whose deadline is missed.
`Stallings states that static table-driven scheduling is appli
`cable to tasks that are periodic. Input to the analysis consists
`of the periodic arrival time, execution time, period ending
`deadline, and relative priority of each task. The scheduler
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 7,451,447 B1
`
`6
`attempts to develop a schedule that enables it to meet the
`requirements of all periodic tasks. This is a predictable
`approach but one that is inflexible, because any change to any
`task requirements requires that the schedule be redone. Ear
`liest-deadline-first or other periodic deadline techniques (dis
`cussed later) are typical of this category of scheduling algo
`rithms.
`Stallings further states that static priority-driven preemp
`tive scheduling makes use of the priority-driven preemptive
`scheduling mechanism common to most non-real-time mul
`tiprogramming systems. In a non-real-time system, a variety
`of factors might be used to determine priority. For example, in
`a time-sharing system, the priority of a process changes
`depending on whether it is processor bound or I/O bound. In
`a real-time system, priority assignment is related to the time
`constraints associated with each task. One example of this
`approach is the rate monotonic algorithm (discussed later),
`which assigns static priorities to tasks based on their periods.
`Stallings yet further states that with dynamic planning
`based scheduling, after a task arrives, but before its execution
`begins, an attempt is made to create a schedule that contains
`the previously scheduled tasks as well as the new arrival. If
`the new arrival can be scheduled in such a way that its dead
`lines are satisfied and that no currently scheduled task misses
`a deadline, then the schedule is revised to accommodate the
`new task.
`Stallings also states that dynamic best effort scheduling is
`the approach used by many real-time systems that are cur
`rently commercially available. When a task arrives, the sys
`tem assigns a priority based on the characteristics of the task.
`Some form of deadline scheduling, such as earliest-deadline
`scheduling, is typically used. Typically, the tasks are aperi
`odic and so no static scheduling analysis is possible. With this
`type of scheduling, until a deadline arrives or until the task
`completes, we do not know whether a timing constraint will
`be met. This is the major disadvantage of this form of sched
`uling. Its advantage is that it is easy to implement.
`Stallings reports that two popular classes of real-time
`scheduling algorithms are deadline scheduling and rate
`monotonic scheduling.
`Deadline Scheduling
`Stallings States that most contemporary real-time operat
`ing systems are designed with the objective of starting real
`time tasks as rapidly as possible, and hence emphasize rapid
`interrupt handling and task dispatching. In fact, this is not a
`particularly useful metric in evaluating real-time operating
`systems. Real-time applications are generally not concerned
`with sheer speed but rather with completing (or starting) tasks
`at the most valuable times, neither too early nor too late,
`despite dynamic resource demands and conflicts, processing
`overloads, and hardware or software faults. It follows that
`priorities provide a crude tool and do not capture the require
`ment of completion (or initiation) at the most valuable time.
`Stallings reports that in recent years, there have been a
`number of proposals for more powerful and appropriate
`approaches to real-time task Scheduling. All of these are
`based on having additional information about each task. In its
`most general form, the following information about each task
`might be used:
`1. Ready time: Time at which task becomes ready for
`execution. In the case of a repetitive or periodic task, this is
`actually a sequence of times that is known in advance. In the
`case of an aperiodic task, this time may be known in advance,
`or the operating system may only be aware when the task is
`actually ready.
`
`MICROCHIP TECH. INC. - EXHIBIT 1035
`MICROCHIP TECH. INC. V. HD SILICON SOLS. - IPR2021-01265 - Page 013
`
`

`

`US 7,451,447 B1
`
`10
`
`15
`
`7
`2. Starting deadline: Time by which a task must begin.
`3. Completion deadline: Time by which task must be com
`pleted. The typical real-time application will either have start
`ing deadlines or completion dead-lines, but not both.
`4. Processing time: Time required to execute the task to
`completion. In some cases, this is Supplied. In others, the
`operating system measures an exponential average. For still
`other scheduling systems, this information is not used.
`5. Resource requirements: Set of resources (other than the
`processor) required by the task while it is executing.
`6. Priority: Measures relative importance of the task. Hard
`real-time tasks may have an “absolute' priority, with the
`system failing if a deadline is missed. If the system is to
`continue to run no matter what, then both hard and soft
`real-time tasks may be assigned relative priorities as a guide
`to the scheduler.
`7. Subtask structure: A task may be decomposed into a
`mandatory Subtask and an optional Subtask. Only the manda
`tory Subtask possesses a hard deadline.
`Stallings further states that there are several dimensions to
`the real-time scheduling function when deadlines are taken
`into account: which task to schedule next, and what sort of
`preemption is allowed. It can be shown, for a given preemp
`tion strategy and using either starting or completion dead
`lines, that a policy of scheduling the task with the earliest
`deadline minimizes the fraction of tasks that miss their dead
`lines. This conclusion holds both for single processor and
`multiprocessor configurations.
`Stallings asserts that the other critical design issue is that of
`preemption. When starting deadlines are specified, then a
`nonpreemptive scheduler makes sense. In this case, it would
`be the responsibility of the real-time task to block itself after
`completing the mandatory or critical portion of its execution,
`allowing other real-time starting deadlines to be satisfied.
`This fits the pattern of FIG. 1B. For a system with completion
`deadlines, a preemptive strategy (FIG. 1C or 1D) is most
`appropriate. For example, if task X is running and task Y is
`ready, there may be circumstances in which the only way to
`allow both X and Y to meet their completion deadlines is to
`preempt X, execute Y to completion, and then resume X to
`completion.
`Stallings states that a straightforward Scheme is always to
`schedule the ready task with earliest deadline and let that task
`run to completion. When this approach is used, when a