Scheduling - Algorithms

Scheduler Does:
(1) CPU Utilization
    Keeping the CPU as busy as possible
(2) Throughput
    No. of tasks that completed their execution per time unit
(3) Turnaround
    The total time between the submission of a task & its completion.
(4) Waiting Time
    The amount of time a task waits in the ready queue.
(5) Response Time
    The amount of time it takes from when a request was submitted until the first response is produced.
(6) Fairness
    Allocating equal CPU time to each task
Note: In RTOS, the tasks should meet their deadlines

---

Scheduling Algorithms:
(1) Cyclic Executive/Run to completion
    Iterates through a given set of tasks
    Interrupts are not allowed, only polling
(2) Cooperative multitasking
    Applications run until they yield
(3)Round -Robin scheduling
    Tasks run until they've consumed their timeslice, or until they're blocked
(4) Preemptive priority based multitasking
    Running threads are preempted by threads with higher priorities
    It is not designed to be fair; but to be deterministic
(5) Time partition scheduling
    Guarantees that threads or groups of threads get a predetermined percentage of the CPU.
(6) Deadline scheduling
    Only available in specialized Oss.
    The schedule is dynamically computed such that the applications meet previously specified deadlines.

---

Interrupts & scheduling

    Interrupts can cause the threads to be rescheduled.
Interrupt Service Routine(ISR): Activities that must be handled at interrupt time(Such as emptying buffers that will quickly overwritten)
Interrupt Service Thread(IST): Activities that can be delayed and handled during normal, priority-driven, thread scheduling(Such as processing data for use by other tasks)

---

OS can change the priority of a task:
    1. Prevent priority inversion
    2. Deadline scheduler
    3. priority decay scheduling

Priority inversion: Typically occurs when a shared resource is held by a lower-priority thread, thus preventing the higher-priority thread from executing as it should.
Low priority thread requesting a high priority thread to do work on its behalf.
NOTE: Priority inversion could be prevented using mechanims such as priority inheritance or priority ceiling emulation.

---

Rate Monotonic Analysis
    RMA is the most common method used to analyze and assign priorities for systems with periodic deadlines.But, interrupt processing is not taken care of here.