PROBLEM: The round robin scheduling policy doesn't work

PROBLEM: The round robin scheduling policy doesn't work

[lucho]

The round robin scheduling policy does not work.

The kernel in question is 2.4.8 (i still haven't downloaded the 2.4.9).

Description:
Suppose there are several processes in RR mode, all with equal
priorities
(and all the remaining processes in the system are either SCHED_OTHER or
realtime but with
lower priorities) then in theory the scheduler should spin these
processes
(in round-robin manner), but in reality this does not hapen. Only one of
the processes
(in fact the first created) in question is given the entire CPU time,
though the others are not sleeping and have the same real-time priority.

The only ways for the process-monopolist to relinquish the CPU is to do
any
blocking syscall (and thus remove itself from the runqueue). The
sched_yield()
syscall does not work because it does not remove the current task from
the runqueue.

The following simple example code should demonstrate this odd behavior
of the scheduler:

int main()
{
    struct sched_param sp;

    sp.sched_priority = 1;
    sched_setscheduler(0, SCHED_RR, &sp);

    if(fork() == 0) {
        while(1) {
            printf("child\n");
            sched_yield();
        }
    }
    else {
        while(1) {
            printf("parent\n");
            sched_yield();
        }
    }

    return 0;
}

I investigated the problem by inserting printk()s at some points in the
schedule() function
in kernel/scheduler.c and managet to find out what's wrong. The reason
for this
wrong behavior seems to be the following piece of code in schedule():

    if (prev->state == TASK_RUNNING)
        goto still_running;

still_running_back:

    ........
    ........

still_running:
    if (!(prev->cpus_allowed & (1UL << this_cpu)))
        goto still_running_back;
    c = goodness(prev, this_cpu, prev->active_mm);
    next = prev;
    goto still_running_back;

which initializes the `c' variable with the current process goodness
(1001 in the example)
and the `next' - with `prev' regardless whether the timeslice of the
prev has expired
(current->counter == 0) or not. So the `list_for_each' loop over the
runqueue never chooses
any different task (because their goodnesses are never bigger than the
so initialized `c').

I didn't get why is that `stil_running' code necessary at all (at least
in uniprocessor system)
since the `list_for_all' loop will anyway go thru the prev task if it's
in running state
because it is certainly in the runqueue, but it rather makes the
scheduler a bit slower
because of the unnecessary two calculations of the prev's goodness.

I removed this code and rebuilt the kernel, and actually got the round
robin working
(i heavily tested it) i.e. then the scheduler really cycles through all
the SCHED_RR processes.

But still the yield() wasn't working (it was just like a NOP).

I found out that the erason for this is that the sys_sched_yield()
function just sets
current->need_resched which causes the schedule() to be called, but
schedule() looks at
the current->counter and when it's nonzero (when current is SCHED_RR
process),
it doesn't switch to other process.

So i added the code:

    if (current->policy == SCHED_RR)
        current->counter = 0;

in the sys_sched_yield() and now it works fine too.

I hope this bug report will be useful.
My name is Luchezar Belev.
Best regards.

Re: PROBLEM: The round robin scheduling policy doesn't work

[Julian Anastasov]

	Hello,

lucho wrote:

> The round robin scheduling policy does not work.

	Yes, I tested it too and I see the same problems on UP and
on 2.2.19. But your example is wrong, see the appended one. In your
example the processes can block. May be this is the reason Richard to
generate different results. In the below example the child terminates
after the parent and is not scheduled for 2 seconds. I tested it with
more childs too but the showed is with one child. The scheduler looks
broken for SCHED_RR.

	For the kernel gurus: may be this is off-topic but isn't
possible the SCHED_FIFO semantic (schedule after process block) to
be implemented for these thread groups in 2.4. This will allow threads
that run in one group to use the SCHED_FIFO scheduling in their group but
not to block the other SCHED_OTHER processes. This will allow the
threads implementations to use something like spinlocks plus something
like postwait calls and will avoid the signal notifications that I see in
some of them. Why this semantic is allowed only for the real time
processes which usually block the normal SCHED_OTHER processes. I know
that the standards talk about scheduling contention scopes and two-level
scheduling models but it sounds too complex as a change. Is there
something working-in-progress for Linux that will allow such sched_fifo
semantics for normal non-realtime threads? How these thread groups
will be extended?

Regards

--
Julian Anastasov <ja@ssi.bg>


#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <signal.h>
#include <time.h>
#include <sched.h>

int child=0;

void sig (int a)
{
	time_t t;

	time(&t);
	printf("%s terminated - %ld\n",
		child? "child" : "parent", t);
	exit(1);
}

int main()
{
	struct sched_param sp;

	printf("Start: %ld\n", time(0));
	fflush(stdout);
	signal(SIGALRM, sig);
	sp.sched_priority = 1;
	sched_setscheduler(0, SCHED_RR, &sp);

	if (fork() == 0)
	{
		child = 1;
		sig(0);
	}
	else
	{
		alarm(2);
		while(1)
		{
			 sched_yield();
		}
	}

	return 0;
}