lkml.org 
[lkml]   [2005]   [Jan]   [6]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    From
    Subject[ANNOUNCE 4/4][RFC] Genetic Algorithm Library
    The hooked zaphod CPU scheduler patch.  

    It depends on the zaphod-v6 patch.

    The ranges for the tunables could be tweaked better.

    Signed-off-by: Jake Moilanen <moilanen@austin.ibm.com>

    ---


    diff -puN kernel/sched_zaphod.c~genetic-zaphod-cpu-sched kernel/sched_zaphod.c
    --- linux-2.6.9/kernel/sched_zaphod.c~genetic-zaphod-cpu-sched Wed Jan 5 15:46:00 2005
    +++ linux-2.6.9-moilanen/kernel/sched_zaphod.c Wed Jan 5 15:46:00 2005
    @@ -21,15 +21,12 @@
    */
    #include <linux/sched.h>
    #include <linux/proc_fs.h>
    +#include <linux/genetic.h>
    +#include <linux/random.h>

    #include <asm/uaccess.h>

    -enum zaphod_mode_enum {
    - ZAPHOD_MODE_PRIORITY_BASED,
    - ZAPHOD_MODE_ENTITLEMENT_BASED
    -};
    -
    -static enum zaphod_mode_enum zaphod_mode = ZAPHOD_MODE_PRIORITY_BASED;
    +enum zaphod_mode_enum zaphod_mode = ZAPHOD_MODE_PRIORITY_BASED;

    #ifdef CONFIG_SYSCTL
    static const char *zaphod_mode_names[] = {
    @@ -720,3 +717,81 @@ int proc_zaphod_mode(ctl_table *ctp, int

    return res;
    }
    +
    +#ifdef CONFIG_GENETIC_CPU_SCHED
    +
    +extern unsigned long sched_rr_time_slice;
    +extern unsigned long base_prom_interval;
    +static void zaphod_sched_create_child(genetic_child_t *);
    +static void genetic_mutate_proportion(genetic_child_t *, unsigned long);
    +void zaphod_sched_set_child_genes(void *);
    +void zaphod_sched_calc_fitness(genetic_child_t *);
    +
    +struct genetic_ops zaphod_sched_genetic_ops = {
    + .create_child = zaphod_sched_create_child,
    + .set_child_genes = zaphod_sched_set_child_genes,
    + .calc_fitness = zaphod_sched_calc_fitness,
    + .combine_genes = genetic_generic_combine_genes,
    + .mutate_child = genetic_generic_mutate_child,
    +};
    +
    +/* Each gene and their attributes */
    +gene_param_t zaphod_sched_gene_param[ZAPHOD_SCHED_NUM_GENES] = {
    + { MIN_TIMESLICE, MAX_TIMESLICE, DEF_TIMESLICE, 0 }, /* time_slice */
    + { MIN_TIMESLICE, MAX_TIMESLICE, (100 * HZ / 1000), 0 }, /* sched_rr_time_slice */
    +// { MIN_TIMESLICE, ULONG_MAX, ((DEF_TIMESLICE * 15) / 10), 0 }, /* base_prom_interval */
    + { MIN_TIMESLICE, MAX_TIMESLICE, ((DEF_TIMESLICE * 15) / 10), 0 }, /* base_prom_interval */
    + { 0, MAX_MAX_IA_BONUS, DEFAULT_MAX_IA_BONUS, 0 }, /* max_ia_bonus */
    + { 0, MAX_MAX_IA_BONUS, 1, 0 }, /* initial_ia_bonus */
    + { 1, 1000, DEFAULT_IA_THRESHOLD, 0 }, /* ia_threshold */
    + { 1, 1000, DEFAULT_CPU_HOG_THRESHOLD, 0 }, /* cpu_hog_threshold */
    + { 0, MAX_MAX_TPT_BONUS, DEFAULT_MAX_TPT_BONUS, 0 }, /* max_tpt_bonus */
    + { 1, 1000, DEFAULT_UNPRIV_RT_THRESHOLD, 0 }, /* unpriv_rt_threshold */
    + { 1, 100, 1, 0 }, /* bgnd_time_slice_multiplier */
    + { 0, 1, 0, 0 }, /* zaphod_mode */
    +};
    +
    +void __init genetic_cpu_sched_init()
    +{
    + if(genetic_init(0, &zaphod_sched_genetic_ops, ZAPHOD_SCHED_NUM_CHILDREN,
    + ZAPHOD_SCHED_CHILD_LIFESPAN, "zaphod-sched"))
    + panic("zaphod sched: failed to init genetic lib");
    +}
    +
    +void zaphod_sched_create_child(genetic_child_t * child)
    +{
    + int i;
    + static int child_num = 0;
    + unsigned long range;
    + int range_incr;
    + unsigned long * genes;
    +
    + BUG_ON(!child);
    +
    + child->genes = (void *)kmalloc(sizeof(struct zaphod_sched_genes), GFP_KERNEL);
    + if (!child->genes)
    + panic("zaphod_sched_create_child: error kmalloc'n space");
    +
    + child->gene_param = zaphod_sched_gene_param;
    +
    + genes = (unsigned long *)child->genes;
    +
    + for (i = 0; i < ZAPHOD_SCHED_NUM_GENES; i++) {
    + range = child->gene_param[i].max - child->gene_param[i].min + 1;
    + range_incr = range / ZAPHOD_SCHED_NUM_CHILDREN;
    + if (range_incr)
    + genes[i] = child->gene_param[i].min +
    + (range_incr * child_num);
    + else
    + genes[i] = child->gene_param[i].min +
    + (child_num / (ZAPHOD_SCHED_NUM_CHILDREN / range));
    + }
    +
    + child->num_genes = ZAPHOD_SCHED_NUM_GENES;
    +
    + child_num++;
    +}
    +
    +core_initcall(genetic_cpu_sched_init);
    +
    +#endif /* CONFIG_GENETIC_CPU_SCHED */
    diff -puN lib/Kconfig~genetic-zaphod-cpu-sched lib/Kconfig
    --- linux-2.6.9/lib/Kconfig~genetic-zaphod-cpu-sched Wed Jan 5 15:46:00 2005
    +++ linux-2.6.9-moilanen/lib/Kconfig Wed Jan 5 15:46:00 2005
    @@ -36,6 +36,13 @@ config GENETIC_LIB
    This option will build in a genetic library that will tweak
    kernel parameters autonomically to improve performance.

    +config GENETIC_CPU_SCHED
    + bool "Genetic Library - Zaphod CPU scheduler"
    + depends on GENETIC_LIB && EXPERIMENTAL && SCHEDSTATS
    + help
    + This option will enable the genetic library on the zaphod
    + CPU scheduler.
    +
    #
    # compression support is select'ed if needed
    #
    diff -puN kernel/sched.c~genetic-zaphod-cpu-sched kernel/sched.c
    --- linux-2.6.9/kernel/sched.c~genetic-zaphod-cpu-sched Wed Jan 5 15:46:00 2005
    +++ linux-2.6.9-moilanen/kernel/sched.c Wed Jan 5 15:46:00 2005
    @@ -43,6 +43,7 @@
    #include <linux/kthread.h>
    #include <linux/seq_file.h>
    #include <linux/times.h>
    +#include <linux/genetic.h>
    #include <asm/tlb.h>

    #include <asm/unistd.h>
    @@ -71,19 +72,8 @@
    #define NS_TO_JIFFIES(TIME) ((TIME) / (1000000000 / HZ))
    #define JIFFIES_TO_NS(TIME) ((TIME) * (1000000000 / HZ))

    -/*
    - * These are the 'tuning knobs' of the scheduler:
    - *
    - * Default configurable timeslice is 100 msecs, maximum configurable
    - * timeslice is 1000 msecs and minumum configurable timeslice is 1 jiffy.
    - * Timeslices get renewed on task creation, on wake up and after they expire.
    - */
    -#define MIN_TIMESLICE 1
    -#define DEF_TIMESLICE (100 * HZ / 1000)
    -#define MAX_TIMESLICE (1000 * HZ / 1000)
    -
    unsigned long time_slice = DEF_TIMESLICE;
    -static unsigned long sched_rr_time_slice = (100 * HZ / 1000);
    +unsigned long sched_rr_time_slice = (100 * HZ / 1000);

    static unsigned long task_timeslice(const task_t *p)
    {
    @@ -116,6 +106,13 @@ struct prio_slot {
    struct list_head queue;
    };

    +static DEFINE_PER_CPU(struct runqueue, runqueues);
    +
    +#define cpu_rq(cpu) (&per_cpu(runqueues, (cpu)))
    +#define this_rq() (&__get_cpu_var(runqueues))
    +#define task_rq(p) ((p)->rq)
    +#define cpu_curr(cpu) (cpu_rq(cpu)->curr)
    +
    /*
    * This is the main, per-CPU runqueue data structure.
    *
    @@ -199,8 +196,6 @@ struct runqueue {
    #endif
    };

    -static DEFINE_PER_CPU(struct runqueue, runqueues);
    -
    /*
    * sched-domains (multiprocessor balancing) declarations:
    */
    @@ -338,11 +333,6 @@ struct sched_domain {
    #define for_each_domain(cpu, domain) \
    for (domain = cpu_rq(cpu)->sd; domain; domain = domain->parent)

    -#define cpu_rq(cpu) (&per_cpu(runqueues, (cpu)))
    -#define this_rq() (&__get_cpu_var(runqueues))
    -#define task_rq(p) ((p)->rq)
    -#define cpu_curr(cpu) (cpu_rq(cpu)->curr)
    -
    #ifdef CONFIG_SMP
    void fastcall set_task_cpu(struct task_struct *p, unsigned int cpu)
    {
    @@ -1357,7 +1347,7 @@ void fastcall wake_up_new_task(task_t *
    /**
    * (Optionally) log scheduler statistics at exit.
    */
    -static int log_at_exit = 0;
    +int log_at_exit = 0;
    /*
    * No more timeslice fiddling on exit
    */
    @@ -4938,3 +4928,60 @@ ctl_table cpu_sched_table[] = {
    { .ctl_name = CPU_SCHED_END_OF_LIST }
    };
    #endif
    +
    +#ifdef CONFIG_GENETIC_CPU_SCHED
    +
    +extern enum zaphod_mode_enum zaphod_mode;
    +
    +void zaphod_sched_set_child_genes(void * in_genes)
    +{
    + struct zaphod_sched_genes * genes = (struct zaphod_sched_genes *)in_genes;
    + int cpu;
    + runqueue_t * rq;
    +
    + time_slice = genes->time_slice;
    + sched_rr_time_slice = genes->sched_rr_time_slice;
    + base_prom_interval = genes->base_prom_interval;
    + max_ia_bonus = genes->max_ia_bonus;
    + initial_ia_bonus = genes->initial_ia_bonus;
    + ia_threshold = ppt_to_proportion(genes->ia_threshold);
    + cpu_hog_threshold = ppt_to_proportion(genes->cpu_hog_threshold);
    + max_tpt_bonus = genes->max_tpt_bonus;
    + unpriv_rt_threshold = ppt_to_proportion(genes->unpriv_rt_threshold);
    + bgnd_time_slice_multiplier = genes->bgnd_time_slice_multiplier;
    + zaphod_mode = genes->zaphod_mode;
    +
    + /* Get snapshot for this child */
    + for_each_online_cpu(cpu) {
    + rq = cpu_rq(cpu);
    +
    + rq->rq_sched_info.cpu_time_snapshot = rq->rq_sched_info.cpu_time;
    + rq->rq_sched_info.run_delay_snapshot = rq->rq_sched_info.run_delay;
    + rq->rq_sched_info.pcnt_snapshot = rq->rq_sched_info.pcnt;
    + }
    +}
    +
    +void zaphod_sched_calc_fitness(genetic_child_t * child)
    +{
    + int cpu;
    + runqueue_t * rq;
    + long cpu_time = 0;
    + long run_delay = 0;
    + long pcnt = 0;
    +
    + /* XXX at some point make sure onlining or offlining a CPU
    + doesn't screw us */
    + for_each_online_cpu(cpu) {
    + rq = cpu_rq(cpu);
    +
    + cpu_time += rq->rq_sched_info.cpu_time - rq->rq_sched_info.cpu_time_snapshot;
    + run_delay += rq->rq_sched_info.run_delay - rq->rq_sched_info.run_delay_snapshot;
    + pcnt += rq->rq_sched_info.pcnt - rq->rq_sched_info.pcnt_snapshot;
    + }
    +
    + child->fitness = cpu_time - run_delay;
    +// child->fitness = 1 - run_delay;
    +}
    +
    +#endif
    +
    diff -puN include/linux/sched.h~genetic-zaphod-cpu-sched include/linux/sched.h
    --- linux-2.6.9/include/linux/sched.h~genetic-zaphod-cpu-sched Wed Jan 5 15:46:00 2005
    +++ linux-2.6.9-moilanen/include/linux/sched.h Wed Jan 5 15:46:00 2005
    @@ -138,6 +138,17 @@ struct sched_param {
    #include <linux/spinlock.h>

    /*
    + * These are the 'tuning knobs' of the scheduler:
    + *
    + * Default configurable timeslice is 100 msecs, maximum configurable
    + * timeslice is 1000 msecs and minumum configurable timeslice is 1 jiffy.
    + * Timeslices get renewed on task creation, on wake up and after they expire.
    + */
    +#define MIN_TIMESLICE 1
    +#define DEF_TIMESLICE (100 * HZ / 1000)
    +#define MAX_TIMESLICE (1000 * HZ / 1000)
    +
    +/*
    * This serializes "schedule()" and also protects
    * the run-queue from deletions/modifications (but
    * _adding_ to the beginning of the run-queue has
    @@ -392,6 +403,12 @@ struct sched_info {
    /* timestamps */
    unsigned long last_arrival, /* when we last ran on a cpu */
    last_queued; /* when we were last queued to run */
    +
    +#ifdef CONFIG_GENETIC_CPU_SCHED
    + unsigned long cpu_time_snapshot;
    + unsigned long run_delay_snapshot;
    + unsigned long pcnt_snapshot;
    +#endif
    };

    extern struct file_operations proc_schedstat_operations;
    @@ -657,6 +674,8 @@ extern int task_nice(const task_t *p);
    extern int task_curr(const task_t *p);
    extern int idle_cpu(int cpu);

    +extern void genetic_cpu_sched_init(void);
    +
    void yield(void);

    /*
    @@ -1031,8 +1050,35 @@ static inline void arch_pick_mmap_layout
    }
    #endif

    +enum zaphod_mode_enum {
    + ZAPHOD_MODE_PRIORITY_BASED,
    + ZAPHOD_MODE_ENTITLEMENT_BASED
    +};
    +
    +#ifdef CONFIG_GENETIC_CPU_SCHED
    extern long sched_setaffinity(pid_t pid, cpumask_t new_mask);
    extern long sched_getaffinity(pid_t pid, cpumask_t *mask);
    +
    +
    +#define ZAPHOD_SCHED_NUM_GENES 11
    +#define ZAPHOD_SCHED_NUM_CHILDREN 8
    +//#define ZAPHOD_SCHED_CHILD_LIFESPAN (9 * (HZ / 2))
    +#define ZAPHOD_SCHED_CHILD_LIFESPAN (4 * HZ)
    +
    +struct zaphod_sched_genes {
    + unsigned long time_slice;
    + unsigned long sched_rr_time_slice;
    + unsigned long base_prom_interval;
    + unsigned long max_ia_bonus;
    + unsigned long initial_ia_bonus;
    + unsigned long ia_threshold;
    + unsigned long cpu_hog_threshold;
    + unsigned long max_tpt_bonus;
    + unsigned long unpriv_rt_threshold;
    + unsigned long bgnd_time_slice_multiplier;
    + unsigned long zaphod_mode;
    +};
    +#endif /* CONFIG_GENETIC_CPU_SCHED */

    #endif /* __KERNEL__ */

    _
    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2005-03-22 14:09    [W:0.044 / U:0.256 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site