real time scheduling in Linux

Question

This morning I read about Linux real time scheduling. As per the book 'Linux system programming by Robert Love', there are two main scheduling there. One is SCHED_FIFO, fifo and the second is SCHED_RR, the round robin. And I understood how a fifo and a rr algorithm works. But as we have the system call,

sched_setscheduler (pid_t pid, int policy, const struct sched_parem *sp)

we can explicitly set the scheduling policy for our process. So in some case, two process running by root, can have different scheduling policy. As one process having SCHED_FIFO and another having SCHED_RR and with same priority. In that case, which process will be selected first? the FIFO classed process or the RR classed process? Why?

Consider this case. There are three process A,B,C. All are having same priority. A and B are RR classed processes and C is FIFO classed one. A and B are runnable (so both are running alternatively in some time intervel). And currently A is running. Now C becomes runnable. In this case, whether

1. A will preempt for C, or
2. A will run until its timeslice goes zero and let C run. Or
3. A will run until its timeslice goes zero and let B run.
   a) here after B runs till its timeslice becomes zero and let C run or
   b) after B runs till its timeslice becomes zero and let A run again (then C will starve untill A and B finishes)

Rawlings

Note: since Linux 3.14, there is an additional policy called SCHED_DEADLINE (en.wikipedia.org/wiki/SCHED_DEADLINE). This policy implements the Earliest Deadline First (EDF) scheduling algorithm. Each task under this policy is assigned a deadline, and the earliest-deadline task is executed. – Stroman

Answer 1

In realtime scheduling, FIFO and RR do not have exactly the same meaning they have in non-realtime scheduling. Processes are always selected in a FIFO- manner, however, the time quantum for SCHED_FIFO is not limited unlike the time quantum for SCHED_RR.

SCHED_FIFO processes do not preempt SCHED_RR processes of the same priority.

sched_setscheduler(2) - Linux man page

...

"A process's scheduling policy determines where it will be inserted into the list of processes with equal static priority and how it will move inside this list. All scheduling is preemptive: if a process with a higher static priority becomes ready to run, the currently running process will be preempted and returned to the wait list for its static priority level. The scheduling policy only determines the ordering within the list of runnable processes with equal static priority."

...

"A SCHED_FIFO process runs until either it is blocked by an I/O request, it is preempted by a higher priority process, or it calls sched_yield(2)."

...

"When a SCHED_FIFO process becomes runnable, it will be inserted at the end of the list for its priority."

...

"SCHED_RR: Round Robin scheduling

SCHED_RR is a simple enhancement of SCHED_FIFO. Everything described above for SCHED_FIFO also applies to SCHED_RR, except that each process is only allowed to run for a maximum time quantum. If a SCHED_RR process has been running for a time period equal to or longer than the time quantum, it will be put at the end of the list for its priority. A SCHED_RR process that has been preempted by a higher priority process and subsequently resumes execution as a running process will complete the unexpired portion of its round robin time quantum."

Roturier

Then you mean, all the processes having same priority will be put in the same queue. Among them the FIFO classed process will run untill it finishes or blocks, but the RR classed process runs only for its timeslice. Am I correct? – Rawlings

Yes, that's how I've understood the manpage. It's the same way other realtime systems define FIFO and RR (e.g. Freescale's MQX RTOS) – Roturier

@Rawlings I refer to your new answer here, because I somehow cannot add a comment to it. You say that the former discussion was wrong with regard to Robert Love's book 'Linux System Programming.' And you're right as Robert says 'Higher-priority processes (and SCHED_FIFO processes of the same or higher priority) will always preempt a running SCHED_RR process, regardless of whether it has any of its timeslice remaining.' (page 196). – Roturier

@Rawlings But Robert say as well 'When a FIFO-classed process blocks, the scheduler removes it from the list of runnable processes. When it again becomes runnable, it is inserted at the end of the list of processes at its priority. Thus, it will not run until any other processes of higher or equal priority cease execution.' (page 189). Isn't that a contradiction?. However, that's what the manpage says. – Roturier

@Rawlings I think, you refer to the 1st edition (2007) of Robert's book, as I have in my previous comments. The 3rd edition (2010) does not have that contradiction anymore. It says exactly the same the manpage does, so our initial assumption seems to be right again: SCHED_FIFO processes do not preempt SCHED_RR processes of the same priority. – Roturier

Thank you very much Grossamer. As you said, I'm using the first edition pdf. :-) – Rawlings

detail of scheduling policies are moved to sched(7) – Verdellverderer

Answer 2

man sched_setscheduler explains these scheduling policies in detail.

In this particular case because the two real-time processes have the same priority none of them will preempt the other. A SCHED_FIFO process runs until it blocks itself, SCHED_RR process runs until it blocks itself or its time quantum expires.

Amaranth

Answer 3

According to the man page, I think 1 is the answer. A, B are RR policy, C is FIFO policy. Since RR is also an enhancement FIFO, all of them are FIFO class.

Since all of them have the same priority, and man page say " A call to sched_setscheduler() or sched_setparam(2) will put the SCHED_FIFO (or SCHED_RR) process identified by pid at the start of the list if it was runnable. As a consequence, it may preempt the currently running process if it has the same priority. (POSIX.1-2001 specifies that the process should go to the end of the list.)"

Once calling sched_setscheduler to set the policy of C as FIFO, C will preempt A.

Reopen

Answer 4

My understanding of the two different classes is that a process SCHED_FIFO is never pre-empted by the kernel. Even if another "SCHED_FIFO" class process is waiting its turn...

While SCHED_RR policy shares the cpu ressources a little bit more. The scheduler will let the SCHED_RR process run for a quanta of time, then pre-empt it only to let turn another SCHED_RR process. That is exactly Round Robin.

SCHED_FIFO is "stronger" in the sense that if a SCHED_FIFO process never yield() to the kernel or invoke a system call on a single core device, then all your other Real time processes may never run.

Vega

"The scheduler will let the SCHED_RR process run for a quanta of time, then pre-empt it only to let turn another SCHED_RR process." is not correct. It can be any scheduling class process (with the same priority) succeeding a SCHED_RR process. – Amaranth

This is inaccurate. RT processes have priorities, and a lower priority SCHED_FIFO process will be preempted to run a higher priority process. – Shelves