CPU Scheduling---By Guruprasad

Multilevel Queue Scheduling:

A multilevel queue scheduling algorithm partitions the ready queue in several separate queues, for instanceIn a multilevel queue scheduling processes are permanently assigned to one queues. The processes are permanently assigned to one another, based on some property of the process, such as

• Memory size
• Process priority
• Process type

Algorithm choose the process from the occupied queue that has the highest priority, and run that process either

• Preemptive or
• Non-preemptively

Each queue has its own scheduling algorithm or policy.

Possibility I
If each queue has absolute priority over lower-priority queues then no process in the queue could run unless the queue for the highest-priority processes were all empty. For example, in the above figure no process in the batch queue could run unless the queues for system processes, interactive processes, and interactive editing processes will all empty.

Possibility II
If there is a time slice between the queues then each queue gets a certain amount of CPU times, which it can then schedule among the processes in its queue. For instance;

• 80% of the CPU time to foreground queue using RR.
• 20% of the CPU time to background queue using FCFS.
• Since processes do not move between queue so, this policy has the advantage of low scheduling overhead, but it is inflexible.

Multilevel Feedback Queue Scheduling

Multilevel feedback queue-scheduling algorithm allows a process to move between queues. It uses many ready queues and associate a different priority with each queue.The Algorithm chooses to process with highest priority from the occupied queue and run that process either preemptively or unpreemptively. If the process uses too much CPU time it will moved to a lower-priority queue.Similarly, a process that wait too long in the lower-priority queue may be moved to a higher-priority queue may be moved to a highest-priority queue. Note that this form of aging prevents starvation.

• A process entering the ready queue is placed in queue 0.
• If it does not finish within 8 milliseconds time, it is moved to the tail of queue 1.
• If it does not complete, it is preempted and placed into queue 2.
• Processes in queue 2 run on a FCFS basis, only when queue 2 run on a FCFS basis, only when queue 0 and queue 1 are empty.

Realtime Scheduling:

Outline

n Brief real-time review

n Scheduling

n Schedulability

n Scheduling algorithms

n Complications

n Brief discuss of Real Time Operating Systems

Distinctive Embedded System Attributes:

n Reactive: computations occur in response to external events

n Periodic events (e.g. rotating machinery and control loops)

n Aperiodic events (e.g. button click)

n Real Time: correctness is partially a function of time

n Hard real time

n – Absolute deadline, beyond which answer is useless

n – May include minimum time as well as maximum time

n Soft real time

n – Approximate deadline

n – Utility of answer degrades with time difference from deadline

n Real time is not just “real fast”

nReal time means that correctness of result depends on both functional correctness and time that the result is delivered

n Soft real time

nUtility degrades with distance from deadline

n Hard real time

nSystem fails if deadline window is missed

n Firm real time

nResult has no utility outside deadline window, but system can withstand a few missed results

Type of Real-Time Scheduling

n Dynamic vs. Static

n Dynamic schedule computed at run-time based on tasks really executing

n Static schedule done at compile time for all possible tasks

n Preemptive permits one task to preempt another one of lower priority

Schedulability

n NP-hard if there are any resources dependencies

n Prove it definitely cannot be scheduled

n Find a schedule if it is easy to do

n Stuck in the middle somewhere

Schedulability

Scheduling Parameters

n Assume N CPUs available for execution of a single task set

n Set of tasks {Ti}

n Periods pi

n Deadline di (completion deadline after task is queued)

n Execution time ci (amount of CPU time to complete)

n Handy values:

n Laxity li = di – ci (amount of slack time before Ti must begin

n

Static Schedule

n Assume non-preemptive system with 5 Restrictions:

1. Tasks {Ti} are periodic, with hard deadlines and no jitter

2. Tasks are completely independent

3. Deadline = period pi = di

4. Computation time ci is known and constant

5. Context switching is free (zero cost) INCLUDING network messages to send context to another CPU(!)

Static Schedule

n Consider least common multiple of periods pi

nThis considers all possible cases of period phase differences

nWorst case is time that is product of all periods; usually not that bad

nIf you can figure out (somehow) how to schedule this, you win

n Performance

nOptimal if all tasks always run; can get up to 100% utilization

nIf it runs once, it will always work

EDF: Earliest Deadline First

nAssume a preemptive system with dynamic priorities, and (same 5 restrictions)

nScheduling policy:

nAlways execute the task with the nearest deadline

nPerformance

nOptimal for uniprocessor (supports up to 100% of CPU usage in all situations)

nIf you’re overloaded, ensures that a lot of tasks don’t complete

n – Gives everyone a chance to fail at the expense of the later tasks

Least Laxity

n Assume a preemptive system with dynamic priorities, and (same 5 restrictions)

n Scheduling policy:

nAlways execute the task with the smallest laxity

n Performance:

n Optimal for uniprocessor (supports up to 100% of CPU usage in all situations)

n – Similar in properties to EDF

n A little more general than EDF for multiprocessors

n – Takes into account that slack time is more meaningful than deadline for tasks of mixed computing sizes

nProbably more graceful degradations

n – Laxity measure permits dumping tasks that are hopeless causes

EDF/Least Laxity Tradeoffs

nPro:

nIf it works, it can get 100% efficiency (on a uniprocessor)

nCon:

n It is not always feasible to prove that it will work in all cases

n – And having it work for a while doesn’t mean it will always work

n Requires dynamic prioritization

n The laxity time hack for global priority has limits

n – May take too many bits to achieve fine-grain temporal ordering

n – May take too many bits to achieve a long enough time horizon

Rate Monotonic

n Assume a preemptive system with static priorities, and (same 5 restrictions) plus

n Scheduling policy:

nHighest static priority goes to shortest period; always execute highest priority

n Performance:

nProvides a guarantee for schedulability with CPU load of ~70%

n – Even with arbitrarily selected task periods

n – Can do better if you know about periods & offsets

nIf all periods are multiple of shortest period, works for CPU load of 100%

Data Dependencies

n If two tasks access the same data (violates Assumption #2)

n Use a semaphore to ensure non-simultaneous access

n Scheduling can get really nasty…

n Priority inversion

n Low-priority task holds resource that prevents execution by high-priority task

n – Task 3 acquires lock

n – Task 1 needs resource, but is blocked by Task 3, so Task 3 is allowed to execute

n – Task 2 preempts Task 3, because it is higher priority

n – BUT, now we have Task 2 delaying Task 3, which delays Task 1

n Priority ceiling protocols

Real Time Operating Systems

n Unix “feel”

n QNX

n LinxOS

n “Smaller” RTOSs

n OS9, Microware

n VxWorks pSOS

n RTX, VenturCom

n A few research/freeware RTOS systems:

n RTEMS, Redstone Military Arsenal

n RT-Mach, CMU

n … others

n Windows: WinCE; embedded NT, Windows + RT add-on products

Multiprocessor Scheduling:

Granularity

z Medium grain: Potential parallelism of an application can be implemented by multiple threads in a single process. High degree of coordination among the threads. Usually programmer specifies the parallelism in the design.

z Coarse grain: Multiprocessing of concurrent processes in a multiprogramming environment :Example : Prj2.

z Very coarse grain: When the synchronization needed is not so frequent the processes can be distributed among network nodes to form a single computing environment. Example: CORBA standard for distributed system

z Independent parallelism: Multiple unrelated processes.

Design Issues

z Assignment of processes to processors.

z Use of multiprogramming on individual processors.

z Actual dispatching of a process.

Process/processor Assignment

z Master/slave assignment: Kernel functions always run on a particular processor. Other processors execute user processes.

y Advantage: Resource conflict resolution simplified since single processor has control.

y Problem: Failure of master processor? Master processor does the scheduling ==> bottleneck.

z Peer assignment: OS can execute on any processor. Each processor does its own scheduling from the pool of available processes. This is similar to Solaris or NT symmetric multiprocessing (SMP).

Multiprogramming at each processor

z Completion time and other application-related performance metrics are much more important than processor utilization in multi-processor environment.

z For example, a multi-threaded application may require all its threads be assigned to different processors for good performance.

z Static or dynamic allocation of processes.

Process dispatching

z After assignment, deciding who is selected from among the pool of waiting processes --- process dispatching.

z Single processor multiprogramming strategies may be counter-productive here.

z Priorities and process history may not be sufficient.

Process scheduling

z Single queue of processes or if multiple priority is used, multiple priority queues, all feeding into a common pool of processors.

z Multi-server queuing model: multiple-queue/single queue , multiple server system. Study the system for 1, 2, and n processors.

z Inference: Specific scheduling policy does not have much effect as the processor number increases.

z Conclusion: Use FCFS with priority levels.

Thread scheduling

z An application can be implemented as a set of threads that cooperate and execute concurrently in the same address space. Criteria: When related threads run in parallel perf. improves.

z Load sharing: pool of threads, pool of processors.

z Gang scheduling: Bunch of related threads scheduled together.

z Dedicated processor assignment: Each program gets as many processors as there are parallel threads.

z Dynamic scheduling: More like demand scheduling.