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

i know process control block maintained in kernel, question is:

if process x being run in cpu, , context switch occurs, process linked pcb of process x run ? or random process in ready queue run ? taking consideration processes have same priority.

thanks in advance!

if process x spent quanta, scheduler called. if there other process of higher or same dynamic priority, context switch occur. if there no other process, , current process still ready run (no blocked), resumed without context switch. there 2 queues, active , expired @ every priority; if have several processes of same priority, run 1 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 following tasks:

• • share cpu equally among running processes
• • pick appropriate process run next if required, considering scheduling class/policy , process priorities

• • balance processes between multiple cores in smp systems

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

5.1 scheduler entry point .. main goal find next task run , assign local variable next.

  next = pick_next_task(rq);      ...   if (likely(prev != next)) {         rq->nr_switches++;   /*  * pick highest-prio task:  */ static inline struct task_struct * pick_next_task(struct rq *rq) {     const struct sched_class *class;     struct task_struct *p;     /*      * optimization: know if tasks in      * fair class can call 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(); /* idle class have runnable task */ } 

pick_next_task() implemented in sched.c. iterates through our list of scheduling classes find class highest priority has runnable task (see scheduling classes above). if class found, scheduling class hook called. since tasks handled sched_fair class, short cut class implemented in beginning of function.

now schedule() checks if pick_next_task() found new task or if picked same task again running before. if latter case, no task switch performed , current task keeps running. if new task found, more case, actual task switch executed calling context_switch(). internally, context_switch() switches new task's memory map , swaps register state , stack.

and https://www.cs.columbia.edu/~smb/classes/s06-4118/l13.pdf linux scheduler, cs cu, coms w4118,

have separate run queue each processor. each processor selects processes own queue run. .. periodically, queues rebalanced

basic scheduling algorithm: find highest-priority queue runnable process; find first process on queue; calculate quantum size; let run; when time up, put on expired list; repeat.

the run queue:

• 140 separate queues, 1 each priority level
• actually, number can changed @ given site
• actually, 2 sets, active , expired
• priorities 0-99 real-time processes
• priorities 100-139 normal processes; value set via nice() system call

using quanta (13 / 40):

• at every time tick, decrease quantum of current running process
• if time goes zero, process done
• if process non-interactive, put aside on expired list
• if process interactive, put @ end of current priority queue
• if there’s nothing else @ priority, run again immediately
• of course, running bonus go down, , priority , interactive status

avoiding indefinite overtaking:

• there 2 sets of 140 queues, active , expired
• the system runs processes active queues, , puts them on expired queues when use quanta
• when priority level of active queue empty, scheduler looks next-highest priority queue
• after running of active queues, active , expired queues swapped
• there pointers current arrays; @ end of cycle, pointers switched