Scenariusz do ćwiczeń 4
Szeregowanie procesów w Linuksie

#define MAX_USER_RT_PRIO        100
#define MAX_RT_PRIO             MAX_USER_RT_PRIO
#define MAX_PRIO                (MAX_RT_PRIO + 40)
/*
 * Convert user-nice values [ -20 ... 0 ... 19 ]
 * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
 * and back.
 */
#define NICE_TO_PRIO(nice)      (MAX_RT_PRIO + (nice) + 20)
#define PRIO_TO_NICE(prio)      ((prio) - MAX_RT_PRIO - 20)
#define TASK_NICE(p)            PRIO_TO_NICE((p)->static_prio)

/*
 * 'User priority' is the nice value converted to something we
 * can work with better when scaling various scheduler parameters,
 * it's a [ 0 ... 39 ] range.
 */
#define USER_PRIO(p)            ((p)-MAX_RT_PRIO)
#define TASK_USER_PRIO(p)       USER_PRIO((p)->static_prio)
#define MAX_USER_PRIO           (USER_PRIO(MAX_PRIO))

/*
 * Minimum timeslice is 5 msecs (or 1 jiffy, whichever is larger),
 * default timeslice is 100 msecs, maximum timeslice is 800 msecs.
 * Timeslices get refilled after they expire.
 */
#define MIN_TIMESLICE           max(5 * HZ / 1000, 1)
#define DEF_TIMESLICE           (100 * HZ / 1000)

/*
 * task_timeslice() scales user-nice values [ -20 ... 0 ... 19 ]
 * to time slice values: [800ms ... 100ms ... 5ms]
 *
 * The higher a thread's priority, the bigger timeslices
 * it gets during one round of execution. But even the lowest
 * priority thread gets MIN_TIMESLICE worth of execution time.
 */

#define SCALE_PRIO(x, prio) \
        max(x * (MAX_PRIO - prio) / (MAX_USER_PRIO/2), MIN_TIMESLICE)
 
static unsigned int task_timeslice(task_t *p)
{
        if (p->static_prio < NICE_TO_PRIO(0))
                return SCALE_PRIO(DEF_TIMESLICE*4, p->static_prio);
        else
                return SCALE_PRIO(DEF_TIMESLICE, p->static_prio);
}

p->time_slice = task_timeslice(p);

/*
 * Some helpers for converting nanosecond timing to jiffy resolution
 */
#define NS_TO_JIFFIES(TIME)     ((TIME) / (1000000000 / HZ))
#define JIFFIES_TO_NS(TIME)     ((TIME) * (1000000000 / HZ))

#define PRIO_BONUS_RATIO         25
#define MAX_BONUS               (MAX_USER_PRIO * PRIO_BONUS_RATIO / 100)
#define MAX_SLEEP_AVG           (DEF_TIMESLICE * MAX_BONUS)

#define CURRENT_BONUS(p) \
        (NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / MAX_SLEEP_AVG)

#define rt_task(p)              ((p)->prio < MAX_RT_PRIO)
#define batch_task(p)           ((p)->policy == SCHED_BATCH)

/*
 * effective_prio - return the priority that is based on the static
 * priority but is modified by bonuses/penalties.
 *
 * We scale the actual sleep average [0 .... MAX_SLEEP_AVG]
 * into the -5 ... 0 ... +5 bonus/penalty range.
 *
 * We use 25% of the full 0...39 priority range so that:
 *
 * 1) nice +19 interactive tasks do not preempt nice 0 CPU hogs.
 * 2) nice -20 CPU hogs do not get preempted by nice 0 tasks.
 *
 * Both properties are important to certain workloads.
 */
static int effective_prio(task_t *p)
{
        int bonus, prio;

        if (rt_task(p))
                return p->prio;

        bonus = CURRENT_BONUS(p) - MAX_BONUS / 2;

        prio = p->static_prio - bonus;
        if (prio < MAX_RT_PRIO)
                prio = MAX_RT_PRIO;
        if (prio > MAX_PRIO-1)
                prio = MAX_PRIO-1;
        return prio;
}

p->prio = effective_prio(p);

#define INTERACTIVE_DELTA         2
#define SCALE(v1,v1_max,v2_max) \
        (v1) * (v2_max) / (v1_max)

#define DELTA(p) \
        (SCALE(TASK_NICE(p) + 20, 40, MAX_BONUS) - 20 * MAX_BONUS / 40 + \
                INTERACTIVE_DELTA)

#define TASK_INTERACTIVE(p) ((p)->prio <= (p)->static_prio - DELTA(p))

/*
 * Here are a few examples of different nice levels:
 *
 *  TASK_INTERACTIVE(-20): [1,1,1,1,1,1,1,1,1,0,0]
 *  TASK_INTERACTIVE(-10): [1,1,1,1,1,1,1,0,0,0,0]
 *  TASK_INTERACTIVE(  0): [1,1,1,1,0,0,0,0,0,0,0]
 *  TASK_INTERACTIVE( 10): [1,1,0,0,0,0,0,0,0,0,0]
 *  TASK_INTERACTIVE( 19): [0,0,0,0,0,0,0,0,0,0,0]
 *
 * (the X axis represents the possible -5 ... 0 ... +5 dynamic
 *  priority range a task can explore, a value of '1' means the
 *  task is rated interactive.)
 *
 * Ie. nice +19 tasks can never get 'interactive' enough to be
 * reinserted into the active array. And only heavily CPU-hog nice -20
 * tasks will be expired. Default nice 0 tasks are somewhere between,
 * it takes some effort for them to get interactive, but it's not
 * too hard.
 */

#define STARVATION_LIMIT        (MAX_SLEEP_AVG)

/*
 * We place interactive tasks back into the active array, if possible.
 *
 * To guarantee that this does not starve expired tasks we ignore the
 * interactivity of a task if the first expired task had to wait more
 * than a 'reasonable' amount of time. This deadline timeout is
 * load-dependent, as the frequency of array switched decreases with
 * increasing number of running tasks. We also ignore the interactivity
 * if a better static_prio task has expired:
 */
#define EXPIRED_STARVING(rq) \
        ((STARVATION_LIMIT && ((rq)->expired_timestamp && \
                (jiffies - (rq)->expired_timestamp >= \
                        STARVATION_LIMIT * ((rq)->nr_running) + 1))) || \
                        ((rq)->curr->static_prio > (rq)->best_expired_prio))

#ifdef CONFIG_SMP
#define TIMESLICE_GRANULARITY(p)        (GRANULARITY * \
      (1 << (((MAX_BONUS - CURRENT_BONUS(p)) ?  \
           (MAX_BONUS - CURRENT_BONUS(p)) : 1) - 1)) * num_online_cpus())
#else
#define TIMESLICE_GRANULARITY(p)        (GRANULARITY * \
      (1 << (((MAX_BONUS - CURRENT_BONUS(p)) ?  \
           (MAX_BONUS - CURRENT_BONUS(p)) : 1) - 1)))

/*
 * Prevent a too long timeslice allowing a task to monopolize
 * the CPU. We do this by splitting up the timeslice into
 * smaller pieces.
 *
 * Note: this does not mean the task's timeslices expire or
 * get lost in any way, they just might be preempted by
 * another task of equal priority. (one with higher
 * priority would have preempted this task already.) We
 * requeue this task to the end of the list on this priority
 * level, which is in essence a round-robin of tasks with
 * equal priority.
 *
 * This only applies to tasks in the interactive
 * delta range with at least TIMESLICE_GRANULARITY to requeue.
 */
  if (TASK_INTERACTIVE(p) && !((task_timeslice(p) -
       p->time_slice) % TIMESLICE_GRANULARITY(p)) &&
       (p->time_slice >= TIMESLICE_GRANULARITY(p)) &&
       (p->array == rq->active)) {

        requeue_task(p, rq->active);
        set_tsk_need_resched(p);

/*
 * Adding/removing a task to/from a priority array:
 */
static void dequeue_task(struct task_struct *p, prio_array_t *array)
{
        array->nr_active--;
        list_del(&p->run_list);
        if (list_empty(array->queue + p->prio))
                __clear_bit(p->prio, array->bitmap);
}

static void enqueue_task(struct task_struct *p, prio_array_t *array)
{
        /* ... */
        list_add_tail(&p->run_list, array->queue + p->prio);
        __set_bit(p->prio, array->bitmap);
        array->nr_active++;
        p->array = array;
}

/*
 * Put task to the end of the run list without the overhead of dequeue
 * followed by enqueue.
 */
static void requeue_task(struct task_struct *p, prio_array_t *array)
{
        list_move_tail(&p->run_list, array->queue + p->prio);
}

static inline void enqueue_task_head(struct task_struct *p, prio_array_t *array)
{
        list_add(&p->run_list, array->queue + p->prio);
        __set_bit(p->prio, array->bitmap);
        array->nr_active++;
        p->array = array;
}