Re: [LKDP] Sorry ... Submission of schedule algorithm tex file

[kannan krishnan]

Hi guys,
       Very very sorry. I did not attach in my
previous mail. Here is the attachment :-(.

with regards,
kannan k
Bangalore
--- kannan krishnan <address@hidden> wrote:
> Hi,
>    abhi .. Iam working with scheduling in process
> management document. 
> 
>    Divekar .. With this i am attaching the tex file
> with schedule() algorithm added to it. Go throught
> it
> and send me what has to be added or what changes
> have
> to be done. 
> 
> with regards,
> kannan k
> Bangalore.
> 
> 
> 
>                
> 
> __________________________________________________
> Do you Yahoo!?
> Yahoo! Mail Plus - Powerful. Affordable. Sign up
> now.
> http://mailplus.yahoo.com
> 
> 
> _______________________________________________
> Lkdp-discuss mailing list
> address@hidden
> http://mail.nongnu.org/mailman/listinfo/lkdp-discuss



__________________________________________________
Do you Yahoo!?
Yahoo! Mail Plus - Powerful. Affordable. Sign up now.
http://mailplus.yahoo.com

\begin{document}
        \section{Structures} \label{sched:structs}
        % TODO include/sched.h only scheduler related stuff
        \subsection{struct thread\_info}
        \subsection{Task State structures}

        \section{Wait Queues} \label{sched:waitq} \index{wait\_queue}
        % TODO

        \section{Scheduling Basics: TIMER\_BH \& TQUEUE\_BH }
        The \textit{TIMER\_BH} is a bottom half related with timer interrupt 
while \textit{TQUEUE\_BH} is a related to periodic task queue. The 
bottom half is a low-priority function, related to some interrupt. Please, 
refer to ~\ref{int:bh} for details. The timer interrupt is initialized 
by the \textit{time\_init} function called from \textit{start\_kernel} 
function. \footnote{Refer to time\_init in 
(arch/i386/kernel/time.c)}.

        \begin{verbatim}

        static struct irqaction irq0  = { timer_interrupt, SA_INTERRUPT, 0, 
"timer", NULL, NULL};

        /* Wire cpu IDT entry to s/w handler (and Cobalt APIC to IDT) */
        setup_irq(CO_IRQ_TIMER, &irq0);

        \end{verbatim}

        \subsection{Timer basics} \index{timer}
        Linux programs the programmable interrupt timer to 100 Hz, means timer 
tick interval is 10 msec. Hence, the \textit{timer\_interrupt} is 
called every 10 msec. This function \footnote{timer\_interrupt is defined in 
(arch/i386/kernel/time.c)} checks for time stamp coutner (TSC) 
\footnote{TSC is calibrated at boot up by \textit{calibrate\_tsc()} 
function. (arch/i386/kernel/time.c)} and invokes 
\textit{do\_timer\_interrupt} function.
        \begin{verbatim}

        /* kernel/timer.c */
        long tick = (1000000 + HZ/2) / HZ;      /* timer interrupt period */

        /* With HZ = 100 , tick = 10 msec */

        \end{verbatim}

        \par Linux kernel also includes Real Time clock. This clock is 
associated with the CMOS battery. This clock is used to keep track date and 
time. All process related accounting is done by the timer interrupt 
running at every 10 msec. \footnote{Refer to "/proc/interrupts" irq0 := 
timer and irq8 := rtc.}

        \begin{verbatim}

        #ifdef CONFIG_VISWS
        /* Clear the interrupt */
        co_cpu_write(CO_CPU_STAT,co_cpu_read(CO_CPU_STAT) & 
~CO_STAT_TIMEINTR);
        #endif
           do_timer(regs);
        #ifndef CONFIG_X86_LOCAL_APIC
        if (!user_mode(regs))
            x86_do_profile(regs->eip);
        #else
            if (!using_apic_timer)
                smp_local_timer_interrupt(regs);
        #endif
        \end{verbatim}

        The variable \textit{xtime} is a global variable used to store the 
cmos time. This is initialised by the \textit{time\_init} function during 
boot up by calling \textit{get\_cmos\_time()} Refer to 
(kernel/time.c) for these functions.
 
        \begin{verbatim}
        /*
         * If we have an externally synchronized Linux clock, then update
         * CMOS clock accordingly every ~11 minutes. Set_rtc_mmss() has to be
         * called as close as possible to 500 ms before the new second starts.
         */
        if ((time_status & STA_UNSYNC) == 0 &&
            xtime.tv_sec > last_rtc_update + 660 &&
            xtime.tv_usec >= 500000 - ((unsigned) tick) / 2 &&
            xtime.tv_usec <= 500000 + ((unsigned) tick) / 2) {
            if (set_rtc_mmss(xtime.tv_sec) == 0)
                last_rtc_update = xtime.tv_sec;
            else
                last_rtc_update = xtime.tv_sec - 600; /* do it again in 60 s 
*/
        }
        \end{verbatim}
        \par The \textit{do\_timer\_interrupt} function updates the timestaps 
from real time clock and calls \textit{do\_timer} function. This 
function performs all the timer interrupt related activities. The function is 
described below.

        \subsection{Function do\_timer} \index{do\_timer}
        \begin{verbatim}
        void do_timer(struct pt_regs *regs)
        {
            jiffies_64++;
        #ifndef CONFIG_SMP
            /* SMP process accounting uses the local APIC timer */

            update_process_times(user_mode(regs));
        #endif
            mark_bh(TIMER_BH);
            if (TQ_ACTIVE(tq_timer))
                mark_bh(TQUEUE_BH);
        }
        \end{verbatim}

        The value of jiffies\_64 is set to 0 when kernel booted, it 
increamentes at every timer interrupt. It also marks the bottom halves related 
to 
TIMER and TQUEUE which will execute the functions associated with these 
bottom halves.
        % \index {scheduler\_tick}
        % TODO scheduler tick, SIGVTALRM, SIGPROF, update_one_process

        \par  The tq\_timer and tq\_scheduler task queues are consumed not 
only in the usual places but elsewhere (closing tty device is an one 
example). This is because, the drivers can schedule tasks on the queue, and 
these tasks only make sense while a particular instance of the device 
is still valid which usually means until the application closes it. So, 
the driver may need to call run\_task\_queue() to flush the tasks it 
(and anyone else) has put on the queue, because allowing them to run at a 
later time may make no sense i.e. the relevant data structures may have 
been freed/reused by a different instance. So run\_task\_queue() on 
tq\_timer and tq\_scheduler in places other than timer interrupt and 
\textit{schedule()} respectively. Refer to O(1) scheduler algorithm here 
~\ref{sched:algo}.
        \section{The switch\_to function}
        \section{schedule() algorithm} \label{sched:algo}
        The {\it schedule()}\footnote{The schedule() function is found 
in (/kernel/sched.c)} function implements the scheduler. The job of the 
scheduler is to provide the CPU between multiple processes. Let us see
the function in detail. Memory descriptor of the process should not be
null. If so the kernel signals a bug.

        \begin{verbatim}
        /*
         * If processes mm field (points to memory descriptor) 
         * is null then error 
         */
        if (!current->active_mm) BUG();
        \end{verbatim}

        Then 2 local variables named {\it prev} and {\it this\_cpu} are
initilized. Variable prev is of type {\it task\_struct} is assigned with
the current process. We can also see an another variable of task\_struct
{\it next} which is used for the point to the descriptor of the process
selected to replace {\it prev}
%TODO DO we have to add more about tq_scheduler here ! and other admin work
%     as specified in the source code 
The scheduling policy \footnote{Refer to (/include/linux/sched.h) to know
about SCHED\_RR. There are 3 policies, Round Robin(SCHED\_RR), FIFO(SCHED\_FIFO)
and conventional process(SCHED\_OTHER)} of the process is checked. If the 
policy is round robin and if the the number of ticks of cpu time left has 
exhusted then move to the last of the run queue.

        \begin{verbatim}
        /* move an exhusted RR process to last */
        if (prev->policy == SCHED_RR)
                goto move_rr_last
         ..
         move_rr_last :
               if (!prev->counter) {
                   prev->counter=NICE_TO_TICKS(prev->nice);
                   move_last_runqueue(prev)
                   }
               goto move_rr_back
        \end{verbatim}

        The state of the process is checked. If it is {\bf TASK\_RUNNING} it
is left alone. If the state is {\bf TASK\_INTERRUPTIBLE} and a signal is pending
for the process then its state is changed to {\bf TASK\_RUNNING}. For all other
options it is removed from the run queue. 
        
        \begin{verbatim}
        switch(prev->state) {
               case TASK_INTERRUPTIBLE :
                    if (signal_pending(prev)) {
                             prev->state=TASK_RUNNING;
                             break;
                           }
               default :
                     del_from_runqueue(prev);
               case TASK_RUNNING : ;
                            }
        \end{verbatim}

        The next best process to be scheduled is set ot the idle task of this 
cpu.
However goodness of the process is set with a very low value ($-$1000) with a 
hope
that some other process is better than this process. If the prev taks is in 
TASK\_RUNNING state, then the current goodness is set to it and {\it next} is 
assigned 
with {\it prev}.  

        \begin{verbatim} 
        /*
         * Default process to select..
         */
        next = idle_task(this_cpu);
        c = -1000;
        if (prev->state == TASK_RUNNING)
                goto still_running;
        ..
        still_running:
           c = goodness(prev, this_cpu, prev->active_mm);
           next = prev;
           goto still_running_back;
        \end{verbatim}
        
        Each and every process in the run queue is selected, its goodness value 
is 
calculated. It is stored in a varible called c. If the value of weight is 
greater
than c, then the values are swapped(both process and goodness value). The 
process
with highest goodness wins. (Refer to section goodness after this to know about
how linux calculates goodness value for each and every process.). If the current
value of goodness after this is zero, then it is recalculated.

        \begin{verbatim}
        int weight = goodness(p, this_cpu, prev->active_mm);
        if (weight > c) 
            c = weight, next = p;
         ..
         ..
        /* Do we need to re-calculate counters? */
        if (!c)
                goto recalculate;
        \end{verbatim}

        After this point it is clear that next is pointing to the process to be
scheduled.  So {\it has\_cpu} and {\it processor} are assigned values. The 
{\it runqueue\_lock} is removed. If it is the same process then global kernel
lock is reacquired and return. For other process, {\it switchto()} function is 
called for a switch to the process.

%TODO Is details about goodness calculation needed. ?? 
\end{document}