How does OS chooses the next process to be run in CPU?

Question

I know a Process control Block is maintained in Kernel, the question is:

If Process X is being run in the CPU, and a context switch occurs, will the process linked to the PCB of process X be run ? Or a random process in the ready queue will be run ? taking into consideration all processes have the same priority.

Thanks in advance!

Answer 1

If the process X spent its quanta, the scheduler will be called. If there is other process of higher or same dynamic priority, then context switch will occur. If there is no other process, and current process still ready to run (no blocked), it will be resumed without context switch. There are two queues, active and expired at every priority; so if we have several processes of same priority, they will run one after another.

Check https://criticalblue.com/news/wp-content/uploads/2013/12/linux_scheduler_notes_final.pdf Process Scheduling in Linux - Critical Blue. Volker Seeker – University of Edinburgh 05.12.2013 (linux 3.1)

process scheduler .. has the following tasks:

• • share CPU equally among all currently running processes
• • pick appropriate process to run next if required, considering scheduling class/policy and process priorities

• • balance processes between multiple cores in SMP systems

  struct task_struct * (*pick_next_task) (struct rq *rq);

5.1 The Scheduler Entry Point .. Its main goal is to find the next task to be run and assign it to the local variable next.

  next = pick_next_task(rq);
     ...
  if (likely(prev != next)) {
        rq->nr_switches++;

 /*
 * Pick up the highest-prio task:
 */
static inline struct task_struct *
pick_next_task(struct rq *rq)
{
    const struct sched_class *class;
    struct task_struct *p;
    /*
     * Optimization: we know that if all tasks are in
     * the fair class we can call that function directly:
     */
    if (likely(rq->nr_running == rq->cfs.nr_running)) {
        p = fair_sched_class.pick_next_task(rq);
        if (likely(p))
            return p;
    }
    for_each_class(class) {
        p = class->pick_next_task(rq);
        if (p)
            return p;
    }
    BUG(); /* the idle class will always have a runnable task */
}

pick_next_task() is also implemented in sched.c. It iterates through our list of scheduling classes to find the class with the highest priority that has a runnable task (see Scheduling Classes above). If the class is found, the scheduling class hook is called. Since most tasks are handled by the sched_fair class, a short cut to this class is implemented in the beginning of the function.

Now schedule() checks if pick_next_task() found a new task or if it picked the same task again that was running before. If the latter is the case, no task switch is performed and the current task just keeps running. If a new task is found, which is the more likely case, the actual task switch is executed by calling context_switch(). Internally, context_switch() switches to the new task's memory map and swaps register state and stack.

And also https://www.cs.columbia.edu/~smb/classes/s06-4118/l13.pdf Linux Scheduler, CS CU, COMS W4118,

Have a separate run queue for each processor. Each processor only selects processes from its own queue to run. .. Periodically, the queues are rebalanced

Basic Scheduling Algorithm: Find the highest-priority queue with a runnable process; Find the first process on that queue; Calculate its quantum size; Let it run; When its time is up, put it on the expired list; Repeat.

The Run Queue:

• 140 separate queues, one for each priority level
• Actually, that number can be changed at a given site
• Actually, two sets, active and expired
• Priorities 0-99 for real-time processes
• Priorities 100-139 for normal processes; value set via nice() system call

Using Quanta (13 / 40):

• At every time tick, decrease the quantum of the current running process
• If the time goes to zero, the process is done
• If the process is non-interactive, put it aside on the expired list
• If the process is interactive, put it at the end of the current priority queue
• If there’s nothing else at that priority, it will run again immediately
• Of course, by running so much is bonus will go down, and so will its priority and its interactive status

Avoiding Indefinite Overtaking:

• There are two sets of 140 queues, active and expired
• The system only runs processes from active queues, and puts them on expired queues when they use up their quanta
• When a priority level of the active queue is empty, the scheduler looks for the next-highest priority queue
• After running all of the active queues, the active and expired queues are swapped
• There are pointers to the current arrays; at the end of a cycle, the pointers are switched