From: jhallen@world.std.com (Joseph H Allen) Subject: Re: linux OS Date: Wed, 10 Feb 1993 12:08:27 GMT
In article <C27EEK.HtM@dutiws.twi.tudelft.nl> bloois@dutiws.twi.tudelft.nl (R.M.de Bloois.TI-OSGS-tel-01819-12030) writes:
>In fact, by studying the source-code in Linux 0.98.1 I found the
>following:
>
>1. The priority in Linux is not dynamically adapted based on
> past execution, at all.
>2. The lengths of the time-slices that linux assign to tasks
> are directly proportional to the priority of each task
> (higher priority means bigger time-slices)
>
>Not many people use nice. So, in effect, Linux does not use
>priorities (unless you use nice-values).
I've discovered some more things, which are especially relevent if you have
a lot of processes running:
The scheduler actually has two cycles: the (short) round robin cycle and the
(long) prioritization cycle (where you wait for all task->count values to go
to zero).
Tasks with high priorities get executed for a while, then tasks with high
and medium priorities and finally tasks with high, medium and low
priorities. This is how it gives more time to higher priority tasks (the
time slices are actually even, high priority tasks just get more of them).
In several places in linux, the task->count value gets zeroed. Presumably
this is to let other tasks get some more CPU time. The problem is that
since you don't know what the avarage of the count values is for other
tasks, you don't know how much time you actually are giving to them. Also
the long cycle can be really long: task switching is 100Hz, the count values
are started at 15, so if you have 15 tasks running, the long cycle is: 2.25
seconds (so zeroing the count value can really delay a task).
I would like to replace the schedular in linux, but I don't really have the
time for it now. Plus if I do, I know I'll be rewriting most of linux (I
also want to rewrite the paging system (so that pages and buffers really are
the same and to get memory mapped files), replace the wait queues with
doubly linked lists so you don't have to search through them to remove
items, add track buffering to the hard disk driver, write a new file-system,
etc. etc. etc.)
So anyway, here's an outline of a schedular which doesn't have the long
cycle (all tasks are evenly interspersed, no matter what their priority
level). It uses a residue algorithm (a remainder like in bresinham line
drawing algorithm) to determine when a task is run. It has the additional
advantage that changes in priority values take effect immediately instead of
after the long-cycle. It would be easy to add the dynamically adapting
stuff which other UNI have.
[BTW, I have question about the system calls in linux: is task switching
disabled during system calls? I haven't been able to figure this out from
the code, but I think it is since a lot code looks like it will break if
task switching is allowed. And if task switching is disabled, where exactly
is it done?]
[which reminds me of something else: I notice that each swap file gets a 4K
page for reference counts. This implies that the maximum swap file/device
size is 16MB and that you can't safely have more than 127 tasks (one bit in
the reference counts is used for something else). Is this correct? ]
/* Joe's Schedular */
/* Note that the meaning of task->priority is reversed. 100 is a low
* prioty task, 10 is a high priority task
*
* Also, the priorities are still proportional: 20 gets half the time that
* a task with priority level 10 does
*/
int highest; /* Current highest priority level (lowest
priority value) */
int nhighest; /* No. tasks at that level */
int ntasks; /* No. of running tasks */
TASK *current; /* Current task */
/* Switch 'cur' to next task which should be run (you'll notice that I want
* to make a linked list of currently running tasks) */
void sched()
{
TASK *t=current;
do
if(t->count<0) t->count+=t->priority; /* Update as we go along */
while(((t=t->next)->count-=highest)>=0); /* Find one? */
switch_to(t);
}
/* Update highest priority level */
/* When a task with the highest priority goes away, this finds the
* new highest priority (lowest level). This is so that the value used for
* subtracting in 'sched' is choosen so that the loop in sched is guarenteed
* to find a task to run without ever having to go through the entire list
* of running tasks.
*/
void fixhighest(old,new)
{
if(old==new) return;
if(new==highest) ++nhighest;
else if(new<highest) highest=new, nhighest=1;
if(old==highest) if(!--nhighest)
{
TASK *t;
highest=MAXINT;
nhighest=0;
t=cur; do
if(t->pri<highest) highest=t->pri, nhighest=1;
else if(t->pri==highest) ++nhighest;
while((t=t->link.next)!=cur);
}
}
/* Rerun a task which had been executing */
void rerun(tsk)
TASK *tsk;
{
enqueb(link,current,tsk); /* List insertion routine */
fixhighest(MAXINT,tsk->priority);
++notasks;
}
/* Enque a task on the schedular queue */
void run(tsk)
TASK *tsk;
{
tsk->count=0;
rerun(tsk);
}
/* Remove the current task from the schedular queue */
TASK *rmv()
{
TASK *tsk=current;
current=current->next;
deque(link,tsk); /* List removal */
fixhighest(tsk->priority,MAXINT);
--ntasks;
return tsk;
}
/* Change current task's priority level */
void modpri(pri)
{
int oldpri=current->priority;
current->priority=pri;
current->count*=pri;
current->count/=oldpri;
fixhighest(oldpri,pri);
}
--
/* jhallen@world.std.com (192.74.137.5) */ /* Joseph H. Allen */
int a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0)
+r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*2
]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n"," #"[!a[q-1]]);}