Scheduling Algorithms
From OSDev Wiki
A scheduling algorithm is the algorithm which dictates how much CPU time is allocated to Processes and Threads. The goal of any scheduling algorithm is to fulfill a number of criteria:
- no task must be starved of resources - all tasks must get their chance at CPU time;
- if using priorities, a low-priority task must not hold up a high-priority task;
- the scheduler must scale well with a growing number of tasks, ideally being O(1). This has been done, for example, in the Linux kernel.
Contents |
Interactive Scheduling Algorithms
Round Robin
You have a queue of tasks ready to run. Just pop the first task from the beginning of that list, add the current task at the end, and switch to that new task. If there are no tasks on the queue, find one :-)
Each process is assigned a time quantum (time slice). For the length of this time quantum the process is allowed to hold the cpu burst. It's an preemptive scheduling algorithm, so scheduling takes place after the time quantum or earlier due to process blocks, resource waiting ...
The big question on RR is how do we choose the time quantum (Q) ?
The context switch time must be << Q -> to keep the overhead low.
To let interactive requests finish in one time quantum Q > 80% of CPU burst.
And finally Q should be < 100ms to avoid poor response time.
So a good compromise is to choose Q between 20ms and 50ms.
Priority-Based Round Robin
Imagine you have a Scheduler, which is responsible for the management of 10 Queues of runnable processes. A runnable process is stuck to the tail of the queue corresponding to his priority. Say, 1 is the highest priority and 10 the lowest.
The Scheduler then checks each of the ten ready-queues for runnable processes (if (queue[Priority].head->next!=NULL)), picks the first runnable process (so, the higher the priority the earlier a process gets its turn of CPU time) and hands it to the task switching mechanism.
Now, imagine the following: You have a queue whose property is Round-Robin in the list of queues: The actual running process at the head of this queue has a certain share of time. Each time the timer IRQ fires, this share is decremented by one. If the share is down to zero, the timer isr invokes the round-robin scheduler, which picks the process from the queues head and stuffs it to the tail of it whilst renewing its share of time. The next process is to get the CPU for its share of time.
The task of scheduling is usually not concentrated in one single function but there are more functions working together.
Let's have a look on the round robin scheduler with three processes in the queue: A B C:
A(time 0) B(time 10) C(time 10) A's time slice is zero: let's do round robin scheduling: B(time 10) C(time 10) A(time 10) ... one clock tick occurs ... the next one ... B(time 8) C(time 10) A(time 10) ... several clock ticks occur ... b's time slice is worn out ... C(time 10) A(time 10) B(time 10) ... ten clock ticks later ... A(time 10) B(time 10) C(time 10) ... now A has it's share of [[CPU]] time again.
Shortest Process Next
Version of SRTN (Shortest Remaining Time Next) for interactive systems. The Problem here is that we can't say what the user's next command will be. This algorithm needs prediction :)
Lottery Scheduling
Batch Scheduling Algorithms
First Come First Served
This scheduling method is used on Batch-Systems, it is NON-PREEMPTIVE. It implements just one queue which holds the tasks in order they come in.
The order the tasks arrive is very important for the Turnaround-Time:
Task1(24) Task2(6) Task3(6)
avg. Turnaround-Time = (24 + 30 + 36) / 3 = 30 time units (this assumes all tasks arrive at time 0)
Task1(6) Task2(6) Task3(24)
avg. Turnaround-Time = (6 +12 +36) / 3 = 18 time units (this assumes all tasks arrive at time 0)
Strengths:
-Simple
-Fair
Problems:
-Convoy Effect
-Order of task arrival is very important for average Turnaround time
Shortest Job First (SJF)
Is also NON-PREEMPTIVE. It selects the shortest Job/Process which is available in the run queue.
This scheduling algorithm assumes that run times are known in advance.
Strengths:
-nearly optimal (Turnaround Time)
Problems:
-Only optimal if all jobs/process are available simultaneously
-Usually run times are not known ...
Shortest Remaining Time Next
Preemptive version of SJF (Shortest Job First). Schedulre picks the job/process which has the lowest remaining time to run.
Strengths:
-probably optimal (Tournaround Time)
Problems:
-again run times must be known
Highest Response Ratio Next
|
This page or section is a stub. Please help by expanding it |
Real-Time Scheduling Algorithms
Real-Time Scheduling Algorithms are a special class of algorithms of which it is required that they can guarantee a process will be done before its deadline. The only way these algorithms can work is if they at least know when the deadline for a process is, and how much the process takes of the system. Only if the system is not overloaded (subjective term) can the threads be guaranteed to finish before their deadline.
Each task has to be scheduled Xt times a second, or every Yt milliseconds (Yt = 1000 / Xt). Each run of that task takes at most Zt milliseconds. This task then creates a load of Lt = Zt / Yt.
The system as a whole has a load L, which is the sum of all task-loads: L = E Lt. If the system load exceeds 0.7 (in some rare cases it can be slightly larger, but we don't count them) the system is unschedulable using Rate Monotonic Scheduling. If this system load exceeds 1.0 it is unschedulable for any real-time system. Note that for normal systems any load is possible, including the ones that are extremely large. They will make the system very unusable though.
Rate Monotonic Scheduling
Rate Monotonic Scheduling is a way to schedule Real-Time threads in such a way, that can be guaranteed that none of the threads will ever exceed their deadline. The load of the system can vary, but in order to guarantee the deadline the load may not go above 0.7 or 70% CPU time usage.
The RMS scheduling works by assigning each task a priority based on its interval. The task with the shortest interval gets the highest priority and the task with the largest interval gets the lowest priority (still real-time though). The tasks are then run similar to a prioritized preempting [#Round-Robin]. This means, any task that can run runs, and if a task runs but a task with a higher priority is available, the higher one runs instead.
If your system is based on a Round-Robin scheduler, this is the easiest way to do Real-Time scheduling. However, because of the 70% limit it's not the best algorithm.
Earliest Deadline First
Each task in an EDF scheduler is assigned a _deadline_ (e.g. a moment in the future at which the task _must_ be completed). Every time a task is inserted in the system or completed, the scheduler looks for the task which has the closest deadline and selects it for execution. In order to ensure that the scheduler is still able to meet each deadline, a 'monitor must evaluate if each new task doesn't overload the system and deny execution if it will do so.
In order to implement EDF-based system, one will have to know both the _deadline_ of the task (which could optionally be computed as "no more than X ms in the future") and the expected time needed to perform the task (required by the monitor). QoS network routers usually implement variants of EDF scheduling.
