Recently in an interview I was asked about the Scheduling algorithm used by Linux Operating system. What is the algorithm used any why?
Also, what algorithm is used in in real-time operating systems and why?
Linux – Which Scheduling algorithm is used in Linux
Architecturelinuxrtosscheduling
Related Solutions
Some embedded systems (a) need to meet difficult real-time requirements, and yet (b) have very limited hardware (which makes it even more difficult to meet those requirements).
If you can't change the hardware, then there are several situations where you are forced to rule out Linux and use something else instead:
- Perhaps the CPU doesn't even have a MMU, which makes it impossible to run Linux (except uClinux, and as far as I know uClinux is not real-time).
- Perhaps the CPU is relatively slow, and the worst-case interrupt latency in Linux fails to meet some hard requirement, and some other RTOS tuned for extremely low worst-case interrupt latency can meet the requirement.
- Perhaps the system has very little RAM. A few years ago, a minimal Linux setup required around 2 MB of RAM; a minimal eCos setup (with a compatibility layer letting it run some applications originally designed to run on Linux) required around 20 kB of RAM.
- Perhaps there is no port of Linux to your hardware, and there isn't enough time to port Linux before you need to launch (pun!) your system. Many of the simpler RTOSes take much less time to port to new hardware than Linux.
It is very tempting to want to define the differences between BSD and Linux. Just like Gilles said in the comments, it is not an easy task since they're so numerous and disparate. Very often, the differences won't even be noticeable at the user's level; everything has been worked out so that the OS behaves as you would expect a Unix to.
Moreover multiple distributions are available for each. No matter what you say about Linux/BSD generally, you'll often find a distribution that contradicts it.
The following is a list of comparisons I found scattered over the web.
- Here on U&L, a user has defined the following differences:
Big differences are (in my opinion of course):
- Userland (Linux uses GNU while BSD uses BSD)
- Integration (Linux is a collection of different efforts, BSD is much more unified at the core)
- Packaging (Linux typically manages installed software in binary packages - BSD typically manages a "ports" tree that you use to build software from sources)
Notice the word typically in his last point. Some Linux distributions will manage source code and conversely some BSDs will manage binary packages.
- Matthew D. Fuller has a lengthy comparison between BSDs and Linux you may want to look into. The article will compare both on Design level, Technical differences, Philosophies and finally address common Myths. Here are some excerpts:
BSD is what you get when a bunch of Unix hackers sit down to try to port a Unix system to the PC. Linux is what you get when a bunch of PC hackers sit down and try to write a Unix system for the PC.
--
BSD is designed. Linux is grown. Perhaps that's the only succinct way to describe it, and possibly the most correct.
- User vivek on FreeBSD forums writes:
Key differences:
- FreeBSD full os. Linux is kernel. Linux distribution is os (100+ majro disrtos).
- FreeBSD everything comes from a single source. Linux is like mix of lot of stuff.
- BSD License vs GPL
- FreeBSD Installer
- BSD commands (ls file -l will not work) vs GPL command (ls file -l will work)
- FreeBSD better and updated man pages.
- BSD rc.d style booting vs Linux SysV style init.d booting
Here are some articles describing the history of each:
Written by Dave Tyson, this article describes the history of many Unix variants (including of course BSD and Linux).
Scott Barman describes how both operating systems came to be and how it forged his opinion:
I will give one "solid" opinion: If I had to choose one system that would act as my router, DNS, ftp server, e-mail gateway, firewall, web server, proxy server, etc., that system would run a BSD-based operating system. If I had to choose one system that would act as my desktop workstation, run X, all the application I like, etc., that system would run Linux. HOWEVER, I would have no problem running Linux as my work horse server or running the BSD-based system on my desktop.
Further reading
- This question here on U&L, compares existing BSDs, highlighting what they have in common.
Best Answer
The current Linux task scheduler is called Completely Fair Scheduler (CFS). You should have a look at http://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt for more details. The design is quite complex and in my view not suitable for RTOS.
A common technique in realtime systems is rate-monotonic scheduling, because it has strong guarantees if certain assumptions hold (e.g. static task priorities and fixed execution time and rate). There are a whole lot other algorithms and there has been a lot of research. So it's basically all about the properties you need and what you know about your task and what is fixed.