LinuxQuestions.org
Latest LQ Deal: Complete CCNA, CCNP & Red Hat Certification Training Bundle
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 05-25-2012, 07:09 AM   #1
bayoulinux
Member
 
Registered: Oct 2011
Posts: 34

Rep: Reputation: Disabled
Where does scheduler run on multicore system ?


Hi:

Where does the Linux scheduler (yeah, the kernel, but that's not what I'm asking) run within a multicore system - it is a shared location than can access all CPUs? Is there a single processor within a mutlicore system that runs the scheduler decides "put this process A on CPU 2", now put this process B on CPU 4", now move process A off CPU 2 and put it on CPU 4"?

I know its a basic question, but I just don't understand how the Linux kernel/scheduler is distributed amongst a multicore CPU system.

Thanks
 
Old 05-25-2012, 12:30 PM   #2
Sergei Steshenko
Senior Member
 
Registered: May 2005
Posts: 4,481

Rep: Reputation: 454Reputation: 454Reputation: 454Reputation: 454Reputation: 454
Quote:
Originally Posted by bayoulinux View Post
... it is a shared location than can access all CPUs? ...
It is a wrong question - as we say it in Russian, you misunderstand who beats whom.

Memory locations do nor access anything, but CPUs (and and other bus masters) do. A program is run by a CPU/core - not the other way round.
 
Old 05-25-2012, 08:44 PM   #3
bayoulinux
Member
 
Registered: Oct 2011
Posts: 34

Original Poster
Rep: Reputation: Disabled
Fair enough... so let me rephrase....

Is there a dedicated CPU running the scheduler that puts processes upon different cores, or does each core run a form of the scheduler and the process target core is coordinated through share memory?
 
Old 05-26-2012, 12:17 AM   #4
eantoranz
Senior Member
 
Registered: Apr 2003
Location: Costa Rica
Distribution: Kubuntu, Debian, Knoppix
Posts: 2,071
Blog Entries: 1

Rep: Reputation: 90
No... that's why it's called SMP, for Symmetric multiprocessing. If the scheduler would run on a single CPU it wouln't be symmetric.
 
Old 05-26-2012, 01:46 AM   #5
Nominal Animal
Senior Member
 
Registered: Dec 2010
Location: Finland
Distribution: Xubuntu, CentOS, LFS
Posts: 1,723
Blog Entries: 3

Rep: Reputation: 946Reputation: 946Reputation: 946Reputation: 946Reputation: 946Reputation: 946Reputation: 946Reputation: 946
The CFS scheduler design document in the Linux Kernel Documentations describes it quite well. (Also see Completely Fair Scheduler at Wikipedia.) Essentially, each task to be scheduled is kept in a time-ordered red-black tree, with the leftmost element always being the next to be run. Each CPU simply grabs the currently leftmost task to find the one it should run. After running the task for a suitable time, the task is put back to the tree, position depending on its priority and how long it was run.

Run queues are the traditional approach. The overall principle with respect to multiple CPUs is the same with run queues: each CPU just grabs the next task from the top of the run queue, executes it for a while, then puts it back into the appropriate place in the run queue depending on its priority and how long it was run.

In an abstract sense, the number of CPUs does not matter, since each CPU just grabs the task that would be run next. In practice, there are features like locking/atomicity (so that two or more CPUs won't modify the same data structures at the same time in incompatible ways), scalability (working with a lot of tasks, and/or CPUs), CPU affinity (prefer to keep the task on the same CPU for efficiency), hardware interrupt handling, non-uniform memory architecture (some memory being easier to access than others for each CPU), and so on. Therefore, the data structures and implementation details tend to be extremely important to make sure each task gets scheduled at the right time, for the right amount of time, without too large latencies (non-running times in between).
 
Old 05-26-2012, 02:08 AM   #6
syg00
LQ Veteran
 
Registered: Aug 2003
Location: Australia
Distribution: Lots ...
Posts: 15,952

Rep: Reputation: 2210Reputation: 2210Reputation: 2210Reputation: 2210Reputation: 2210Reputation: 2210Reputation: 2210Reputation: 2210Reputation: 2210Reputation: 2210Reputation: 2210
But that describes what happens to the entity described by a task_struct, not the scheduler itself, which is what I think the OP is asking about.
Short answer is the scheduler runs everywhere. Often.
 
Old 05-26-2012, 11:07 AM   #7
Nominal Animal
Senior Member
 
Registered: Dec 2010
Location: Finland
Distribution: Xubuntu, CentOS, LFS
Posts: 1,723
Blog Entries: 3

Rep: Reputation: 946Reputation: 946Reputation: 946Reputation: 946Reputation: 946Reputation: 946Reputation: 946Reputation: 946
Quote:
Originally Posted by syg00 View Post
But that describes what happens to the entity described by a task_struct
The point was that the scheduler is not a program-like entity, but something that each CPU runs to select which task to run next. You can say it's just a selection algorithm, with a few bells and whistles to make it niftier. Asking where it runs is like asking where qsort() runs.
 
Old 05-26-2012, 11:18 AM   #8
Sergei Steshenko
Senior Member
 
Registered: May 2005
Posts: 4,481

Rep: Reputation: 454Reputation: 454Reputation: 454Reputation: 454Reputation: 454
Quote:
Originally Posted by Nominal Animal View Post
The point was that the scheduler is not a program-like entity, but something that each CPU runs to select which task to run next. You can say it's just a selection algorithm, with a few bells and whistles to make it niftier. Asking where it runs is like asking where qsort() runs.
The whole kernel "is not a program-like entity". I.e. in a system doing something useful most of the times user tasks ("program-like entities") are run, and when task switching is to occur, kernel code takes over, analyzes previously stored state and based on it and on newly available info (like interrupt requests to be serviced, time it took to run last active user task, IO requests, etc.) kernel code decides what to do next.
 
Old 09-20-2017, 10:57 PM   #9
sampov
LQ Newbie
 
Registered: Sep 2017
Posts: 2

Rep: Reputation: Disabled
I know this post is pretty old, but I found it and thought I might add a source that has a pretty good explanation. If you look at section 2.2.1 of The Linux Scheduler: a Decade of Wasted Cores they have a fairly good explanation.
 
1 members found this post helpful.
Old 09-20-2017, 11:27 PM   #10
syg00
LQ Veteran
 
Registered: Aug 2003
Location: Australia
Distribution: Lots ...
Posts: 15,952

Rep: Reputation: 2210Reputation: 2210Reputation: 2210Reputation: 2210Reputation: 2210Reputation: 2210Reputation: 2210Reputation: 2210Reputation: 2210Reputation: 2210Reputation: 2210
Cogent, relevant contributions always welcome.
I went to a similar presentation some years ago (before CFS), but the promised proceedings where never made public.
 
Old 09-21-2017, 03:45 PM   #11
sundialsvcs
LQ Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 8,614
Blog Entries: 4

Rep: Reputation: 2998Reputation: 2998Reputation: 2998Reputation: 2998Reputation: 2998Reputation: 2998Reputation: 2998Reputation: 2998Reputation: 2998Reputation: 2998Reputation: 2998
One sort-of-reasonable way to look at it is: "the scheduler is the thing that a CPU runs when it finds that it has nothing better to do!"

Its purpose is to decide "what to do next," and(!!) since any CPU/core might be doing so (even, literally, "simultaneously"), to be as efficient as possible.

The heuristics that face any scheduling algorithm are very complex, such that there is no (and, can never be ...) "bright-line rule" to be found. Some pundits/humorists have aptly characterized it as "a race between immediacy and utter starvation, and hurry up, willlya?"
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
Java threads on Multicore System moniker117 Programming 1 11-27-2009 09:17 PM
Under moderate load in a multicore system of 13 processors one processor gets 100% us praveen24 Linux - Kernel 7 09-03-2009 05:21 AM
Single cpu-core used on multicore system when processes communicate with pipe merijnv Linux - Kernel 3 04-10-2009 10:17 PM
How to run a custom made scheduler? chaitukanna Linux - Newbie 4 02-02-2009 09:08 AM
Run all OS processes on one core in multicore processor tryon16 Linux - Kernel 6 10-02-2007 06:13 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 11:24 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration