Here is the next release of the genetic library based against 2.6.10
kernel.
There were numerous changes from the first release, but the major change
in this version is the introduction of phenotypes. A phenotype is a set
of genes the affect an observable property. In genetic-library terms,
it is a set of genes that will affect a particular fitness measurement.
Each phenotype will have a set of children that contain genes that
affect a fitness measure.
Now multiple fitness routines can be ran for each genetic library user.
Then depending on the results of a particular fitness measure, the
specific genes that directly affect that fitness measure can be
modified. This introduces a finer granularity that was missing in the
first release of the genetic-library.
I would like to thank Peter Williams for reworking the Zaphod Scheduler
and help designing the phenotypes.
Some of the other features introduced is shifting the number of
mutations depending on how well a phenotype is performing. If the
current generation outperformed the previous generation, then the rate
of mutation will go down. Conversely if the current generation performed
worst then the previous generation, the mutation rate will go up. This
mutation rate shift will do two things. When generations are improving,
it will reduce the number unnecessary mutations and hone in on the
optimal tunables. When a workload drastically changes, the fitness
should go way down, and the mutation rate will increase in order to test
a greater space of better values quicker. This should decrease the time
it takes to adjust to a new workload. There is a limit at 45% of the
genes being mutated every generation in order to prevent the mutation
rate spiralling out of control.
SpecJBB and UnixBench are still yielding a 1-3% performance improvement,
however (though it's subjective) the interactiveness has had noticeable
improvements.
I have not broke the Anticipatory IO Scheduler down to a fine
granularity in phenotypes yet. Any assistance would be greatly
appreciated.
Currently I am hosting this project off of:
http://kernel.jakem.net
[1/4 genetic-lib]: This is the base patch for the genetic algorithm.
[2/4 genetic-io-sched]: The base patch for the IO schedulers to use the
genetic library.
[3/4 genetic-as-sched]: A genetic-lib hooked anticipatory IO scheduler.
[4/4 genetic-zaphod-cpu-sched]: A hooked zaphod CPU scheduler. Depends
on the zaphod-v6.2 patch.
Thanks,
Jake
Here is the base patch for the genetic-library.
It includes generic routines for modifying and manipulating genes of
children. If a specific routine is needed, that can be used instead.
Signed-off-by: Jake Moilanen <[email protected]>
Change Log
0.2 1/12/2004
- Added ability to run multiple fitness functions that work on
specific genes by using phenotypes.
- Added a post calc fitness to use for normalization of various
fitness routines.
- Restructured /proc tree.
- Made a separate snapshot call instead of doing it in set_genes.
- Rework the mutation code, to do it as a rate of the total number of
genes instead of an arbitrary number.
0.1 1/7/2004
- Added ability for mutates to take iterative steps.
- Moved debug info to a /proc file.
- Added a mutate_rate_change. The rate of mutation will increase when
fitness goes down. Hopefully allowing it to optimize for new workloads.
- Added a boot option for disabling the genetic lib.
- Had it randomly determined which parent a gene came from.
---
diff -puN fs/proc/proc_misc.c~genetic-lib fs/proc/proc_misc.c
--- linux-2.6.10/fs/proc/proc_misc.c~genetic-lib Fri Jan 28 15:49:40 2005
+++ linux-2.6.10-moilanen/fs/proc/proc_misc.c Tue Feb 15 12:06:49 2005
@@ -38,6 +38,7 @@
#include <linux/smp_lock.h>
#include <linux/seq_file.h>
#include <linux/times.h>
+#include <linux/genetic.h>
#include <linux/profile.h>
#include <linux/blkdev.h>
#include <linux/hugetlb.h>
@@ -238,6 +239,97 @@ static int meminfo_read_proc(char *page,
return proc_calc_metrics(page, start, off, count, eof, len);
#undef K
}
+
+#ifdef CONFIG_GENETIC_LIB
+extern struct proc_dir_entry * genetic_root_dir;
+
+int genetic_read_proc(char *page, char **start, off_t off,
+ int count, int *eof, void *data)
+{
+ int n = 0;
+ genetic_t * genetic = (genetic_t *)data;
+
+ struct list_head * p;
+ phenotype_t * pt;
+
+
+ n = sprintf(page, "%s:\n", genetic->name);
+ n += sprintf(page+n, "generation_number:\t\t%ld\n", genetic->generation_number);
+ n += sprintf(page+n, "num_children:\t\t\t%ld\n", genetic->num_children);
+ n += sprintf(page+n, "child_life_time:\t\t%ld\n\n", genetic->child_life_time);
+ n += sprintf(page+n, "child_number:\t\t\t%ld\n\n", genetic->child_number);
+
+ n += sprintf(page+n, "Phenotypes Average Fitness\n");
+
+ list_for_each(p, &genetic->phenotype) {
+ pt = list_entry(p, phenotype_t, phenotype);
+
+ n += sprintf(page+n, "%-24s:\t\t%lld\n", pt->name, pt->avg_fitness);
+ }
+
+ return proc_calc_metrics(page, start, off, count, eof, n);
+}
+
+int genetic_phenotype_read_proc(char *page, char **start, off_t off,
+ int count, int *eof, void *data)
+{
+ int i;
+ int n = 0;
+ phenotype_t * pt = (phenotype_t *)data;
+
+ n = sprintf(page, "------ %s -----\n", pt->name);
+ n += sprintf(page+n, "generation_number:\t%ld\n", pt->genetic->generation_number);
+ n += sprintf(page+n, "num_children:\t\t%ld\n\n", pt->num_children);
+ n += sprintf(page+n, "child_number:\t\t%ld\n", pt->child_number);
+ n += sprintf(page+n, "mutation_rate:\t\t%ld\n", pt->mutation_rate);
+ n += sprintf(page+n, "num_mutations:\t\t%ld\n", pt->num_mutations);
+ n += sprintf(page+n, "num_genes:\t\t%ld\n", pt->num_genes);
+ n += sprintf(page+n, "uid:\t\t\t%ld\n", pt->uid);
+ n += sprintf(page+n, "avg_fitness:\t\t%lld\n", pt->avg_fitness);
+ n += sprintf(page+n, "last_gen_avg_fitness:\t%lld\n", pt->last_gen_avg_fitness);
+
+ n += sprintf(page+n, "\nFitness history\n");
+
+ for (i = pt->genetic->generation_number > GENETIC_HISTORY_SIZE ? GENETIC_HISTORY_SIZE
+ : pt->genetic->generation_number-1; i > 0; i--)
+ n += sprintf(page+n, "%ld:\t%lld\n",
+ pt->genetic->generation_number - i,
+ pt->fitness_history[(pt->fitness_history_index - i) & GENETIC_HISTORY_MASK]);
+
+ return proc_calc_metrics(page, start, off, count, eof, n);
+}
+
+#if GENETIC_DEBUG
+int genetic_debug_read_proc(char *page, char **start, off_t off,
+ int count, int *eof, void *data)
+{
+ int i, j, k;
+ int n = 0;
+ phenotype_t * pt = (phenotype_t *)data;
+
+ n = sprintf(page, "generation_number:\t%ld\n", pt->genetic->generation_number);
+
+ for (i = 0, j = 1; i < pt->debug_size; j++) {
+ /* print out child number, and ID */
+ n += sprintf(page+n, "%d (%lld):", j, pt->debug_history[i++]);
+ /* print out child fitness */
+ n += sprintf(page+n, " %-12lld:\t", pt->debug_history[i++]);
+
+ for (k = 0; k < pt->child_ranking[0]->num_genes; k++) {
+ n += sprintf(page+n, "%lld\t", pt->debug_history[i++]);
+ }
+ n += sprintf(page+n, "\n");
+
+ if (j == pt->num_children) {
+ n += sprintf(page+n, "\n");
+ j = 0;
+ }
+ }
+
+ return proc_calc_metrics(page, start, off, count, eof, n);
+}
+#endif /* GENETIC_DEBUG */
+#endif /* CONFIG_GENETIC_LIB */
extern struct seq_operations fragmentation_op;
static int fragmentation_open(struct inode *inode, struct file *file)
diff -puN /dev/null include/linux/genetic.h
--- /dev/null Fri Mar 14 06:52:15 2003
+++ linux-2.6.10-moilanen/include/linux/genetic.h Wed Feb 2 16:26:35 2005
@@ -0,0 +1,232 @@
+#ifndef __LINUX_GENETIC_H
+#define __LINUX_GENETIC_H
+/*
+ * include/linux/genetic.h
+ *
+ * Jake Moilanen <[email protected]>
+ * Copyright (C) 2004 IBM
+ *
+ * Genetic algorithm library
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version
+ * 2 of the License, or (at your option) any later version.
+ */
+
+#include <linux/list.h>
+#include <linux/timer.h>
+#include <linux/init.h>
+
+
+#define GENETIC_HISTORY_SIZE 0x8
+#define GENETIC_HISTORY_MASK (GENETIC_HISTORY_SIZE - 1)
+
+/* percentage of total number genes to mutate */
+#define GENETIC_DEFAULT_MUTATION_RATE 15
+
+/* XXX TODO Make this an adjustable runtime variable */
+/* Percentage that an iteration can jump within the range */
+#define GENETIC_ITERATIVE_MUTATION_RANGE 30
+
+/* the rate that GENETIC_DEFAULT_MUTATION_RATE itself can change */
+#define GENETIC_DEFAULT_MUTATION_RATE_CHANGE 4
+#define GENETIC_MAX_MUTATION_RATE 45
+#define GENETIC_MIN_MUTATION_RATE 10
+
+#define GENETIC_DEBUG 1
+#define GENETIC_NUM_DEBUG_POINTS 4
+
+#define GENETIC_PRINT_DEBUG 0
+#define gen_dbg(format, arg...) do { if (GENETIC_PRINT_DEBUG) printk(KERN_EMERG __FILE__ ": " format "\n" , ## arg); } while (0)
+#define gen_trc(format, arg...) do { if (GENETIC_PRINT_DEBUG) printk(KERN_EMERG __FILE__ ":%s:%d\n" , __FUNCTION__, __LINE__); } while (0)
+
+struct gene_param_s;
+struct genetic_s;
+struct phenotype_s;
+
+struct genetic_child_s {
+ struct list_head list;
+ long long fitness;
+ unsigned long num_genes;
+ void *genes;
+ struct gene_param_s *gene_param;
+ void *stats_snapshot;
+ int id;
+};
+
+typedef struct genetic_child_s genetic_child_t;
+
+/* Here's a generic idea of what it the genes could look like */
+struct gene_param_s {
+ unsigned long min;
+ unsigned long max;
+ unsigned long initial;
+ void (*mutate_gene)(genetic_child_t *, unsigned long);
+};
+
+typedef struct gene_param_s gene_param_t;
+
+struct phenotype_s {
+ struct list_head phenotype;
+
+ struct list_head children_queue[2];
+ struct list_head *run_queue;
+ struct list_head *finished_queue;
+ struct genetic_ops *ops;
+
+ char *name;
+
+ struct genetic_s *genetic; /* point back
+ * to genetic
+ * struct
+ */
+
+ unsigned long num_children; /* Must be power of 2 */
+ unsigned long natural_selection_cutoff; /* How many children
+ * will survive
+ */
+ void *stats_snapshot;
+ unsigned long child_number;
+
+ /* percentage of total number of genes to mutate */
+ long mutation_rate;
+ unsigned long num_mutations;
+ unsigned long num_genes;
+
+ genetic_child_t **child_ranking;
+
+ void (*natural_selection)(struct phenotype_s *);
+
+ /* This UID is bitmap comprised of other phenotypes that contribute
+ to the genes */
+ unsigned long uid;
+
+ /* performance metrics */
+ long long avg_fitness;
+ long long last_gen_avg_fitness;
+
+ unsigned long fitness_history_index;
+ long long fitness_history[GENETIC_HISTORY_SIZE];
+
+#if GENETIC_DEBUG
+ unsigned long debug_size; /* number of longs in
+ debug history */
+ unsigned long debug_index;
+ long long *debug_history;
+#endif
+};
+
+typedef struct phenotype_s phenotype_t;
+
+struct genetic_s {
+ char *name;
+ struct timer_list timer;
+
+ struct list_head phenotype;
+
+ unsigned long child_number;
+ unsigned long child_life_time;
+ unsigned long num_children; /* Must be power of 2 */
+
+ struct proc_dir_entry *dir;
+ struct proc_dir_entry *debug_dir;
+ unsigned long generation_number;
+
+};
+
+typedef struct genetic_s genetic_t;
+
+struct genetic_ops {
+ void (*create_child)(genetic_child_t *);
+ void (*set_child_genes)(void *);
+ void (*calc_fitness)(genetic_child_t *);
+ void (*combine_genes)(genetic_child_t *, genetic_child_t *,
+ genetic_child_t *);
+ void (*mutate_child)(genetic_child_t *);
+ void (*calc_post_fitness)(phenotype_t *); /* Fitness routine used when
+ * need to take into account
+ * other phenotype fitness
+ * results after they ran
+ */
+ void (*take_snapshot)(phenotype_t *);
+ void (*shift_mutation_rate)(phenotype_t *);
+};
+
+/* Setup routines */
+int __init genetic_init(genetic_t ** in_genetic, unsigned long num_children,
+ unsigned long child_life_time,
+ char * name);
+int __init genetic_register_phenotype(genetic_t * genetic, struct genetic_ops * ops,
+ unsigned long num_children, char * name,
+ unsigned long num_genes, unsigned long uid);
+void __init genetic_start(genetic_t * genetic);
+
+/* Generic helper functions */
+void genetic_generic_mutate_child(genetic_child_t * child);
+void genetic_generic_iterative_mutate_gene(genetic_child_t * child, long gene_num);
+void genetic_generic_combine_genes(genetic_child_t * parent_a,
+ genetic_child_t * parent_b,
+ genetic_child_t * child);
+void genetic_create_child_spread(genetic_child_t * child, unsigned long num_children);
+void genetic_create_child_defaults(genetic_child_t * child);
+void genetic_general_shift_mutation_rate(phenotype_t * in_pt);
+
+#if BITS_PER_LONG >= 64
+
+static inline void divll(long long *n, long div, long *rem)
+{
+ *rem = *n % div;
+ *n /= div;
+}
+
+#else
+
+static inline void divl(int32_t high, int32_t low,
+ int32_t div,
+ int32_t *q, int32_t *r)
+{
+ int64_t n = (u_int64_t)high << 32 | low;
+ int64_t d = (u_int64_t)div << 31;
+ int32_t q1 = 0;
+ int c = 32;
+ while (n > 0xffffffff) {
+ q1 <<= 1;
+ if (n >= d) {
+ n -= d;
+ q1 |= 1;
+ }
+ d >>= 1;
+ c--;
+ }
+ q1 <<= c;
+ if (n) {
+ low = n;
+ *q = q1 | (low / div);
+ *r = low % div;
+ } else {
+ *r = 0;
+ *q = q1;
+ }
+ return;
+}
+
+static inline void divll(long long *n, long div, long *rem)
+{
+ int32_t low, high;
+ low = *n & 0xffffffff;
+ high = *n >> 32;
+ if (high) {
+ int32_t high1 = high % div;
+ int32_t low1 = low;
+ high /= div;
+ divl(high1, low1, div, &low, (int32_t *)rem);
+ *n = (int64_t)high << 32 | low;
+ } else {
+ *n = low / div;
+ *rem = low % div;
+ }
+}
+#endif
+
+#endif
diff -puN lib/Kconfig~genetic-lib lib/Kconfig
--- linux-2.6.10/lib/Kconfig~genetic-lib Fri Jan 28 15:49:40 2005
+++ linux-2.6.10-moilanen/lib/Kconfig Tue Feb 15 12:06:46 2005
@@ -30,6 +30,12 @@ config LIBCRC32C
require M here. See Castagnoli93.
Module will be libcrc32c.
+config GENETIC_LIB
+ bool "Genetic Library"
+ help
+ This option will build in a genetic library that will tweak
+ kernel parameters autonomically to improve performance.
+
#
# compression support is select'ed if needed
#
diff -puN lib/Makefile~genetic-lib lib/Makefile
--- linux-2.6.10/lib/Makefile~genetic-lib Fri Jan 28 15:49:40 2005
+++ linux-2.6.10-moilanen/lib/Makefile Fri Jan 28 15:49:40 2005
@@ -23,6 +23,7 @@ endif
obj-$(CONFIG_CRC_CCITT) += crc-ccitt.o
obj-$(CONFIG_CRC32) += crc32.o
obj-$(CONFIG_LIBCRC32C) += libcrc32c.o
+obj-$(CONFIG_GENETIC_LIB) += genetic.o
obj-$(CONFIG_GENERIC_IOMAP) += iomap.o
obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/
diff -puN /dev/null lib/genetic.c
--- /dev/null Fri Mar 14 06:52:15 2003
+++ linux-2.6.10-moilanen/lib/genetic.c Wed Feb 2 16:34:07 2005
@@ -0,0 +1,734 @@
+/*
+ * Genetic Algorithm Library
+ *
+ * Jake Moilanen <[email protected]>
+ * Copyright (C) 2004 IBM
+ *
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version
+ * 2 of the License, or (at your option) any later version.
+ */
+
+/*
+ * Life cycle
+ *
+ * 1.) Create random children
+ * 2.) Run tests
+ * 3.) Calculate fitness
+ * 4.) Take top preformers
+ * 5.) Make children
+ * 6.) Mutate
+ * 7.) Goto step 2
+ */
+
+#include <linux/genetic.h>
+#include <linux/timer.h>
+#include <linux/jiffies.h>
+#include <linux/proc_fs.h>
+#include <linux/init.h>
+#include <linux/random.h>
+
+#include <asm/uaccess.h>
+#include <asm/string.h>
+#include <asm/bug.h>
+
+char genetic_lib_version[] = "0.2";
+
+int mutation_rate_change = GENETIC_DEFAULT_MUTATION_RATE_CHANGE;
+int genetic_lib_enabled = 1;
+
+static void genetic_ns_top_parents(phenotype_t *);
+static void genetic_ns_award_top_parents(phenotype_t *);
+static int genetic_create_children(phenotype_t *);
+static void genetic_split_performers(phenotype_t *);
+static void genetic_mutate(phenotype_t *);
+static void genetic_run_child(genetic_t * genetic);
+static void genetic_new_generation(genetic_t * genetic);
+
+void genetic_switch_child(unsigned long data);
+struct proc_dir_entry * genetic_root_dir = 0;
+
+extern int genetic_read_proc(char *page, char **start, off_t off,
+ int count, int *eof, void *data);
+extern int genetic_phenotype_read_proc(char *page, char **start, off_t off,
+ int count, int *eof, void *data);
+
+#if GENETIC_DEBUG
+extern int genetic_debug_read_proc(char *page, char **start, off_t off,
+ int count, int *eof, void *data);
+#endif
+
+
+int __init genetic_init(genetic_t ** in_genetic, unsigned long num_children,
+ unsigned long child_life_time,
+ char * name)
+{
+ struct proc_dir_entry *entry;
+ genetic_t * genetic;
+
+ if (!genetic_lib_enabled)
+ return 0;
+
+ printk(KERN_INFO "Initializing Genetic Library - version %s\n", genetic_lib_version);
+
+ genetic = (genetic_t *)kmalloc(sizeof(genetic_t), GFP_KERNEL);
+ if (!genetic) {
+ printk(KERN_ERR "genetic_init: not enough memory\n");
+ return -ENOMEM;
+ }
+
+ *in_genetic = genetic;
+
+ genetic->name = (char *)kmalloc(strlen(name), GFP_KERNEL);
+ if (!genetic->name) {
+ printk(KERN_ERR "genetic_init: not enough memory\n");
+ kfree(genetic);
+ return -ENOMEM;
+ }
+
+ /* Init some of our values */
+ strcpy(genetic->name, name);
+
+ genetic->num_children = num_children;
+ genetic->child_life_time = child_life_time;
+
+ genetic->generation_number = 1;
+ genetic->child_number = 0;
+
+ /* Setup how long each child has to live */
+ init_timer(&genetic->timer);
+ genetic->timer.function = genetic_switch_child;
+ genetic->timer.data = (unsigned long)genetic;
+
+#ifdef CONFIG_PROC_FS
+ /* Setup proc structure to monitor */
+ if (!genetic_root_dir)
+ genetic_root_dir = proc_mkdir("genetic", 0);
+
+ genetic->dir = proc_mkdir(name, genetic_root_dir);
+
+ entry = create_proc_entry("stats", 0644, genetic->dir);
+
+ if (entry) {
+ entry->nlink = 1;
+ entry->data = genetic;
+ entry->read_proc = genetic_read_proc;
+ }
+
+#ifdef GENETIC_DEBUG
+ genetic->debug_dir = proc_mkdir("debug", genetic->dir);
+#endif /* GENETIC_DEBUG */
+
+
+#endif /* CONFIG_PROC_FS */
+
+ INIT_LIST_HEAD(&genetic->phenotype);
+
+ return 0;
+}
+
+int __init genetic_register_phenotype(genetic_t * genetic, struct genetic_ops * ops,
+ unsigned long num_children, char * name,
+ unsigned long num_genes, unsigned long uid)
+{
+ struct proc_dir_entry *entry;
+ phenotype_t * pt;
+ int rc;
+
+ if (!genetic_lib_enabled)
+ return 0;
+
+ printk(KERN_INFO "Initializing %s's phenotype %s\n", genetic->name, name);
+
+ pt = (phenotype_t *)kmalloc(sizeof(phenotype_t), GFP_KERNEL);
+ if (!genetic) {
+ printk(KERN_ERR "genetic_register_phenotype: not enough memory\n");
+ return -ENOMEM;
+ }
+
+ pt->name = (char *)kmalloc(strlen(name), GFP_KERNEL);
+ if (!pt->name) {
+ printk(KERN_ERR "genetic_register_phenotype: not enough memory\n");
+ kfree(pt);
+ return -ENOMEM;
+ }
+
+ pt->child_ranking = (genetic_child_t **)kmalloc(num_children * sizeof(genetic_child_t *), GFP_KERNEL);
+ if (!pt->child_ranking) {
+ printk(KERN_ERR "genetic_register_phenotype: not enough memory\n");
+ kfree(pt->name);
+ kfree(pt);
+ return -ENOMEM;
+ }
+
+ strcpy(pt->name, name);
+
+ INIT_LIST_HEAD(&pt->children_queue[0]);
+ INIT_LIST_HEAD(&pt->children_queue[1]);
+
+ pt->run_queue = &pt->children_queue[0];
+ pt->finished_queue = &pt->children_queue[1];
+
+ pt->ops = ops;
+ pt->num_children = num_children;
+
+ pt->mutation_rate = GENETIC_DEFAULT_MUTATION_RATE;
+ pt->natural_selection = genetic_ns_top_parents;
+ pt->natural_selection_cutoff = num_children / 2;
+ pt->avg_fitness = 0;
+ pt->last_gen_avg_fitness = 0;
+ pt->child_number = 0;
+
+ pt->genetic = genetic;
+ pt->uid = uid;
+ pt->num_genes = num_genes;
+
+ /* Create some children */
+ rc = genetic_create_children(pt);
+ if (rc)
+ return rc;
+
+#ifdef CONFIG_PROC_FS
+ entry = create_proc_entry(name, 0644, genetic->dir);
+
+ if (entry) {
+ entry->nlink = 1;
+ entry->data = pt;
+ entry->read_proc = genetic_phenotype_read_proc;
+ }
+
+#endif
+
+#if GENETIC_DEBUG
+ pt->debug_index = 0;
+ /* create array for history. The +2 on num_genes is for the
+ fitness and child id */
+ pt->debug_size = num_children * (num_genes + 2) * GENETIC_NUM_DEBUG_POINTS;
+
+ pt->debug_history = (long long *) kmalloc(pt->debug_size * sizeof(long long), GFP_KERNEL);
+
+#ifdef CONFIG_PROC_FS
+ entry = create_proc_entry(name, 0644, genetic->debug_dir);
+
+ if (entry) {
+ entry->nlink = 1;
+ entry->data = pt;
+ entry->read_proc = genetic_debug_read_proc;
+ }
+
+#endif /* CONFIG_PROC_FS */
+#endif /* GENETIC_DEBUG */
+
+
+ list_add_tail(&pt->phenotype, &genetic->phenotype);
+
+ return 0;
+}
+
+void __init genetic_start(genetic_t * genetic)
+{
+ if (!genetic_lib_enabled)
+ return;
+
+ genetic_run_child(genetic);
+ printk(KERN_INFO "%ld children started in %s genetic library\n", genetic->num_children, genetic->name);
+}
+
+
+
+/* create some children, it is up to the lib user to come up w/ a good
+ distro of genes for it's children */
+static int genetic_create_children(phenotype_t * pt)
+{
+ unsigned long i;
+ genetic_child_t * child;
+
+ for (i = 0; i < pt->num_children; i++) {
+ pt->child_ranking[i] = (genetic_child_t *)kmalloc(sizeof(genetic_child_t), GFP_KERNEL);
+ if (!pt->child_ranking[i]) {
+ printk(KERN_ERR "genetic_create_child: not enough memory\n");
+ for (i = i - 1; i >= 0; i--)
+ kfree(pt->child_ranking[i]);
+
+ return -ENOMEM;
+ }
+
+ child = pt->child_ranking[i];
+
+ child->id = i;
+
+ pt->ops->create_child(child);
+
+ list_add_tail(&child->list, pt->run_queue);
+ }
+
+ return 0;
+}
+
+/* See how well child did and run the next one */
+void genetic_switch_child(unsigned long data)
+{
+ genetic_t * genetic = (genetic_t *)data;
+ genetic_child_t * child;
+
+ struct list_head * p;
+ phenotype_t * pt;
+
+ int new_generation = 0;
+
+ list_for_each(p, &genetic->phenotype) {
+ pt = list_entry(p, phenotype_t, phenotype);
+
+ child = list_entry(pt->run_queue->next, genetic_child_t, list);
+
+ list_del(&child->list);
+
+ list_add_tail(&child->list, pt->finished_queue);
+
+ if (pt->ops->calc_fitness)
+ pt->ops->calc_fitness(child);
+
+ pt->child_ranking[pt->child_number++] = child;
+
+ /* See if need more children */
+ if (list_empty(pt->run_queue))
+ new_generation = 1;
+ }
+
+ genetic->child_number++;
+
+ if (new_generation)
+ genetic_new_generation(genetic);
+
+ genetic_run_child(genetic);
+
+}
+
+/* Set the childs genes for run */
+void genetic_run_child(genetic_t * genetic)
+{
+ struct list_head * p;
+ phenotype_t * pt;
+
+ genetic_child_t * child;
+ void * genes;
+
+ list_for_each(p, &genetic->phenotype) {
+ pt = list_entry(p, phenotype_t, phenotype);
+
+ child = list_entry(pt->run_queue->next, genetic_child_t, list);
+
+ genes = child->genes;
+
+ if (pt->ops->set_child_genes)
+ pt->ops->set_child_genes(genes);
+
+ if (pt->ops->take_snapshot)
+ pt->ops->take_snapshot(pt);
+ }
+
+ /* set a timer interrupt */
+ genetic->timer.expires = jiffies + genetic->child_life_time;
+ add_timer(&genetic->timer);
+
+}
+
+/* This natural selection routine will take the top
+ * natural_select_cutoff and use them to make children for the next
+ * generation and keep the top half perfomers
+ *
+ * This assumes natural_select_cutoff is exactly half of num_children
+ * and num_children is a multable of 4.
+ */
+static void genetic_ns_top_parents(phenotype_t * pt)
+{
+ unsigned long i,j,k = 0;
+ unsigned long num_children = pt->num_children;
+ unsigned long cutoff = num_children - pt->natural_selection_cutoff;
+
+ for (i = cutoff, j = num_children - 1; i < j; i++, j--, k += 2) {
+ /* create child A */
+ pt->ops->combine_genes(pt->child_ranking[i],
+ pt->child_ranking[j],
+ pt->child_ranking[k]);
+
+ /* create child B */
+ pt->ops->combine_genes(pt->child_ranking[i],
+ pt->child_ranking[j],
+ pt->child_ranking[k+1]);
+ }
+}
+
+/* This natural selection routine just has top parents populating
+ bottom performers. */
+static void genetic_ns_award_top_parents(phenotype_t * pt)
+{
+ unsigned long i;
+ unsigned long num_children = pt->num_children;
+ unsigned long cutoff = num_children - pt->natural_selection_cutoff;
+
+ for (i = 0; i < cutoff; i += 2) {
+ pt->ops->combine_genes(pt->child_ranking[num_children - 1],
+ pt->child_ranking[num_children - 2],
+ pt->child_ranking[i]);
+
+ pt->ops->combine_genes(pt->child_ranking[num_children - 1],
+ pt->child_ranking[num_children - 2],
+ pt->child_ranking[i+1]);
+ }
+}
+
+static inline void genetic_swap(genetic_child_t ** a, genetic_child_t ** b)
+{
+ genetic_child_t * tmp = *a;
+
+ *a = *b;
+ *b = tmp;
+}
+
+/* bubble sort */
+/* XXX change this to quick sort */
+static void genetic_split_performers(phenotype_t * pt)
+{
+ int i, j;
+
+ for (i = pt->num_children; i > 1; i--)
+ for (j = 0; j < i - 1; j++)
+ if (pt->child_ranking[j]->fitness > pt->child_ranking[j+1]->fitness)
+ genetic_swap(&pt->child_ranking[j], &pt->child_ranking[j+1]);
+}
+
+static void genetic_mutate(phenotype_t * pt)
+{
+ long child_entry = -1;
+ int i;
+
+ if (!pt->num_genes)
+ return;
+
+ for (i = 0; i < pt->num_mutations; i++) {
+ get_random_bytes(&child_entry, sizeof(child_entry));
+ child_entry = child_entry % pt->num_children;
+
+ pt->ops->mutate_child(pt->child_ranking[child_entry]);
+ }
+}
+
+/* XXX This will either aid in handling new workloads, or send us on a
+ downward spiral */
+static void genetic_shift_mutation_rate(phenotype_t * pt, long long prev_gen_avg_fitness, long long avg_fitness)
+{
+ if (mutation_rate_change && pt->genetic->generation_number > 1) {
+
+ if (pt->ops->shift_mutation_rate) {
+ pt->ops->shift_mutation_rate(pt);
+ } else {
+
+ if (avg_fitness > prev_gen_avg_fitness)
+ pt->mutation_rate -= mutation_rate_change;
+ else if (avg_fitness < prev_gen_avg_fitness)
+ pt->mutation_rate += mutation_rate_change;
+
+ if (pt->mutation_rate > GENETIC_MAX_MUTATION_RATE)
+ pt->mutation_rate = GENETIC_MAX_MUTATION_RATE;
+ else if (pt->mutation_rate < GENETIC_MIN_MUTATION_RATE)
+ pt->mutation_rate = GENETIC_MIN_MUTATION_RATE;
+ }
+ }
+}
+
+void genetic_general_shift_mutation_rate(phenotype_t * in_pt)
+{
+ struct list_head * p;
+ phenotype_t * pt;
+ int count = 0;
+ long rate = 0;
+
+ list_for_each(p, &in_pt->genetic->phenotype) {
+ pt = list_entry(p, phenotype_t, phenotype);
+
+ if (in_pt->uid & pt->uid && in_pt->uid != pt->uid) {
+ rate += pt->mutation_rate;
+ count++;
+ }
+ }
+
+ /* If we are a general phenotype that is made up of other
+ phenotypes then we take the average */
+ if (count)
+ in_pt->mutation_rate = (rate / count);
+ else
+ in_pt->mutation_rate = mutation_rate_change;
+}
+
+static void genetic_calc_stats(phenotype_t * pt)
+{
+ long long total_fitness = 0;
+ long long prev_gen_avg_fitness = pt->last_gen_avg_fitness;
+ long long tmp_fitness;
+ long dummy;
+ int i;
+
+ /* calculate the avg fitness for this generation and avg fitness
+ * so far */
+ for (i = 0; i < pt->num_children; i++)
+ total_fitness += pt->child_ranking[i]->fitness;
+
+ pt->last_gen_avg_fitness = total_fitness >> long_log2(pt->num_children);
+
+ /* Mutation rate calibration */
+ genetic_shift_mutation_rate(pt, prev_gen_avg_fitness, pt->last_gen_avg_fitness);
+
+ pt->num_mutations = ((pt->num_children * pt->num_genes) * pt->mutation_rate) / 100;
+
+ /* calc new avg fitness */
+ tmp_fitness = pt->last_gen_avg_fitness - pt->avg_fitness;
+ divll(&tmp_fitness, pt->genetic->generation_number, &dummy);
+ pt->avg_fitness += tmp_fitness;
+
+ pt->fitness_history[pt->fitness_history_index++ & GENETIC_HISTORY_MASK] =
+ pt->last_gen_avg_fitness;
+
+}
+
+#if GENETIC_DEBUG
+/* Stores attributes into an array in the following format
+ * child_num fitness gene[0] gene[1] .... gene[num_genes-1]
+ * Add +1 to GENETIC_NUM_DEBUG_POINTS if add another dump_children
+ * call
+ */
+void dump_children(phenotype_t * pt)
+{
+ int i, j;
+ long * genes;
+ unsigned long debug_size = pt->debug_size;
+
+ for (i = 0; i < pt->num_children; i++) {
+ pt->debug_history[pt->debug_index++ % debug_size] = pt->child_ranking[i]->id;
+ pt->debug_history[pt->debug_index++ % debug_size] = pt->child_ranking[i]->fitness;
+
+ genes = (long *)pt->child_ranking[i]->genes;
+
+ for (j = 0; j < pt->child_ranking[i]->num_genes; j++) {
+ pt->debug_history[pt->debug_index++ % debug_size] = genes[j];
+ }
+ }
+}
+#else
+void dump_children(genetic_t * genetic) { return; }
+#endif
+
+void genetic_new_generation(genetic_t * genetic)
+{
+ struct list_head * tmp;
+
+ struct list_head * p;
+ phenotype_t * pt;
+
+ list_for_each(p, &genetic->phenotype) {
+ pt = list_entry(p, phenotype_t, phenotype);
+
+ /* Check to see if need to recalibrate fitness to take
+ other phenotypes' rankings into account. This
+ should be ran after all phenotypes that have input
+ have been ran. */
+ if (pt->ops->calc_post_fitness)
+ pt->ops->calc_post_fitness(pt);
+
+ dump_children(pt);
+
+ /* figure out top performers */
+ genetic_split_performers(pt);
+
+ /* calc stats */
+ genetic_calc_stats(pt);
+
+ dump_children(pt);
+
+ /* make some new children */
+ if (pt->num_genes)
+ pt->natural_selection(pt);
+
+ dump_children(pt);
+
+ /* mutate a couple of the next generation */
+ genetic_mutate(pt);
+
+ dump_children(pt);
+
+ /* Move the new children still sitting in the finished queue to
+ the run queue */
+ tmp = pt->run_queue;
+ pt->run_queue = pt->finished_queue;
+ pt->finished_queue = tmp;
+
+ pt->child_number = 0;
+ pt->debug_index = 0;
+
+ }
+
+ genetic->child_number = 0;
+ genetic->generation_number++;
+
+}
+
+/* Mutate a gene picking a random value within the gene range */
+void genetic_generic_random_mutate_gene(genetic_child_t * child, long gene_num)
+{
+ unsigned long *genes = (unsigned long *)child->genes;
+ unsigned long min = child->gene_param[gene_num].min;
+ unsigned long max = child->gene_param[gene_num].max;
+ unsigned long gene_value;
+ unsigned long range = max - min + 1;
+
+ /* create a mutation value */
+ get_random_bytes(&gene_value, sizeof(gene_value));
+
+ gene_value = gene_value % range;
+
+ genes[gene_num] = min + gene_value;
+}
+
+void genetic_generic_iterative_mutate_gene(genetic_child_t * child, long gene_num)
+{
+ unsigned long *genes = (unsigned long *)child->genes;
+ long min = child->gene_param[gene_num].min;
+ long max = child->gene_param[gene_num].max;
+ long change;
+ long old_value = genes[gene_num];
+ long new_value;
+ unsigned long range = max - min + 1;
+
+ /* If under 5, random might work better */
+ if (range < 5)
+ return genetic_generic_random_mutate_gene(child, gene_num);
+
+ /* get the % of change */
+ get_random_bytes(&change, sizeof(change));
+
+ change = change % GENETIC_ITERATIVE_MUTATION_RANGE;
+
+
+ new_value = ((long)(change * range) / (long)100) + old_value;
+
+ if (new_value > max)
+ new_value = max;
+ else if (new_value < min)
+ new_value = min;
+
+ genes[gene_num] = new_value;
+}
+
+/* This assumes that all genes are a unsigned long array of size
+ num_genes */
+void genetic_generic_mutate_child(genetic_child_t * child)
+{
+ long gene_num = -1;
+
+ /* pick a random gene */
+ get_random_bytes(&gene_num, sizeof(gene_num));
+
+ if (gene_num < 0)
+ gene_num = -gene_num;
+
+ gene_num = gene_num % child->num_genes;
+
+ if (child->gene_param[gene_num].mutate_gene)
+ child->gene_param[gene_num].mutate_gene(child, gene_num);
+ else
+ genetic_generic_random_mutate_gene(child, gene_num);
+}
+
+void genetic_create_child_defaults(genetic_child_t * child)
+{
+ int i;
+ unsigned long * genes = child->genes;
+
+ for (i = 0; i < child->num_genes; i++) {
+ genes[i] = child->gene_param[i].initial;
+ }
+}
+
+void genetic_create_child_spread(genetic_child_t * child, unsigned long num_children)
+{
+ int i;
+ unsigned long range;
+ int range_incr;
+ int child_num = child->id;
+ long num_genes = child->num_genes;
+ unsigned long * genes = child->genes;
+
+ for (i = 0; i < num_genes; i++) {
+ range = child->gene_param[i].max - child->gene_param[i].min + 1;
+ range_incr = range / 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 / (num_children / range));
+ }
+
+}
+
+/* Randomly pick which parent to use for each gene to create a child */
+void genetic_generic_combine_genes(genetic_child_t * parent_a,
+ genetic_child_t * parent_b,
+ genetic_child_t * child)
+{
+ unsigned long * genes_a = (unsigned long *)parent_a->genes;
+ unsigned long * genes_b = (unsigned long *)parent_b->genes;
+ unsigned long * child_genes = (unsigned long *)child->genes;
+
+ /* Assume parent_a and parent_b have same num_genes */
+ unsigned long num_genes = parent_a->num_genes;
+ int parent_selector;
+ int i, j;
+
+ for (i = 0; i < num_genes; i++) {
+ get_random_bytes(&parent_selector, sizeof(parent_selector));
+
+ /* Look at each bit to determine which parent to use */
+ for (j = 0; j < (sizeof(parent_selector) * 8); j++) {
+ if (parent_selector & 1) {
+ child_genes[i] = genes_a[i];
+ } else {
+ child_genes[i] = genes_b[i];
+ }
+ parent_selector >>= 1;
+ }
+ }
+}
+
+static int __init genetic_boot_setup(char *str)
+{
+ if (strcmp(str, "on") == 0)
+ genetic_lib_enabled = 1;
+ else if (strcmp(str, "off") == 0)
+ genetic_lib_enabled = 0;
+
+ return 1;
+}
+
+
+static int __init genetic_mutation_rate_change_setup(char *str)
+{
+ int i;
+
+ if (get_option(&str,&i)) {
+
+ if (i > GENETIC_MAX_MUTATION_RATE)
+ i = GENETIC_MAX_MUTATION_RATE;
+ else if (i < 0)
+ i = 0;
+
+ mutation_rate_change = i;
+ }
+
+ return 1;
+
+}
+__setup("genetic=", genetic_boot_setup);
+__setup("genetic_mutate_rate=", genetic_mutation_rate_change_setup);
_
This is the base patch for the IO Schedulers.
Needs a finer granularity for fitness routines.
Signed-off-by: Jake Moilanen <[email protected]>
---
diff -puN drivers/block/genhd.c~genetic-io-sched drivers/block/genhd.c
--- linux-2.6.10/drivers/block/genhd.c~genetic-io-sched Fri Jan 28 15:49:42 2005
+++ linux-2.6.10-moilanen/drivers/block/genhd.c Fri Jan 28 15:49:42 2005
@@ -32,6 +32,8 @@ static struct blk_major_name {
static spinlock_t major_names_lock = SPIN_LOCK_UNLOCKED;
+LIST_HEAD(gendisks);
+
/* index in the above - for now: assume no multimajor ranges */
static inline int major_to_index(int major)
{
@@ -600,6 +602,7 @@ struct gendisk *alloc_disk(int minors)
kobj_set_kset_s(disk,block_subsys);
kobject_init(&disk->kobj);
rand_initialize_disk(disk);
+ list_add_tail(&disk->gendisks, &gendisks);
}
return disk;
}
diff -puN drivers/block/ll_rw_blk.c~genetic-io-sched drivers/block/ll_rw_blk.c
--- linux-2.6.10/drivers/block/ll_rw_blk.c~genetic-io-sched Fri Jan 28 15:49:42 2005
+++ linux-2.6.10-moilanen/drivers/block/ll_rw_blk.c Fri Jan 28 15:49:42 2005
@@ -28,6 +28,7 @@
#include <linux/slab.h>
#include <linux/swap.h>
#include <linux/writeback.h>
+#include <linux/genetic.h>
/*
* for max sense size
@@ -2111,6 +2112,92 @@ static inline void add_request(request_q
__elv_add_request(q, req, ELEVATOR_INSERT_SORT, 0);
}
+#ifdef CONFIG_GENETIC_IOSCHED_AS
+extern struct list_head gendisks;
+
+void disk_stats_snapshot(phenotype_t * pt)
+{
+ struct list_head * d;
+ struct gendisk *disk;
+ struct disk_stats_snapshot * ss = (struct disk_stats_snapshot *)pt->child_ranking[0]->stats_snapshot;
+
+ memset(ss, 0, sizeof(struct disk_stats_snapshot));
+
+ list_for_each(d, &gendisks) {
+ disk = list_entry(d, struct gendisk, gendisks);
+
+ disk_round_stats(disk);
+
+ ss->reads += disk_stat_read(disk, reads);
+ ss->writes += disk_stat_read(disk, writes);
+ ss->read_sectors += disk_stat_read(disk, read_sectors);
+ ss->write_sectors += disk_stat_read(disk, write_sectors);
+ ss->time_in_queue += disk_stat_read(disk, time_in_queue);
+ }
+}
+
+/* XXX is this the best method to calc fitness */
+unsigned long disk_calc_fitness(genetic_child_t * child)
+{
+ struct list_head * d;
+ struct gendisk *disk;
+ struct disk_stats_snapshot * ss = (struct disk_stats_snapshot *)child->stats_snapshot;
+ unsigned long reads = 0;
+ unsigned long writes = 0;
+ unsigned long time_in_queue = 0;
+ unsigned long read_sectors = 0;
+ unsigned long write_sectors = 0;
+ long long total_fitness = 0;
+
+ list_for_each(d, &gendisks) {
+ disk = list_entry(d, struct gendisk, gendisks);
+
+ disk_round_stats(disk);
+
+ reads += disk_stat_read(disk, reads);
+ writes += disk_stat_read(disk, writes);
+
+ read_sectors += disk_stat_read(disk, read_sectors);
+ write_sectors += disk_stat_read(disk, write_sectors);
+
+ time_in_queue += disk_stat_read(disk, time_in_queue);
+
+ }
+
+ reads -= ss->reads;
+ writes -= ss->writes;
+ time_in_queue = -(time_in_queue - ss->time_in_queue);
+ read_sectors -= ss->read_sectors;
+ write_sectors -= ss->write_sectors;
+
+ /* Various attempts at collecting good fitness */
+#if 0
+ if (time_in_queue)
+ disk_fitness = ((reads + writes) 2 * HZ) / time_in_queue;
+ else
+ disk_fitness = 0;
+
+#endif
+
+#if 0
+ if (time_in_queue)
+ disk_fitness = ((read_sectors + write_sectors) * 2 * HZ) / time_in_queue;
+ else
+ disk_fitness = 0;
+#endif
+
+#if 0
+ disk_fitness = reads + writes;
+#endif
+
+#if 1
+ total_fitness = read_sectors + write_sectors;
+#endif
+
+ return total_fitness;
+}
+#endif
+
/*
* disk_round_stats() - Round off the performance stats on a struct
* disk_stats.
@@ -2133,7 +2220,6 @@ void disk_round_stats(struct gendisk *di
__disk_stat_add(disk, time_in_queue,
disk->in_flight * (now - disk->stamp));
disk->stamp = now;
-
if (disk->in_flight)
__disk_stat_add(disk, io_ticks, (now - disk->stamp_idle));
disk->stamp_idle = now;
diff -puN include/linux/genhd.h~genetic-io-sched include/linux/genhd.h
--- linux-2.6.10/include/linux/genhd.h~genetic-io-sched Fri Jan 28 15:49:42 2005
+++ linux-2.6.10-moilanen/include/linux/genhd.h Fri Jan 28 15:49:42 2005
@@ -121,11 +121,20 @@ struct gendisk {
atomic_t sync_io; /* RAID */
unsigned long stamp, stamp_idle;
int in_flight;
+ struct list_head gendisks;
#ifdef CONFIG_SMP
struct disk_stats *dkstats;
#else
struct disk_stats dkstats;
#endif
+#ifdef CONFIG_GENETIC_LIB
+ unsigned reads_snap;
+ unsigned writes_snap;
+ unsigned read_sectors_snap;
+ unsigned write_sectors_snap;
+ unsigned time_in_queue_snap;
+#endif
+
};
/*
diff -puN include/linux/blkdev.h~genetic-io-sched include/linux/blkdev.h
--- linux-2.6.10/include/linux/blkdev.h~genetic-io-sched Fri Jan 28 15:52:18 2005
+++ linux-2.6.10-moilanen/include/linux/blkdev.h Fri Jan 28 15:52:47 2005
@@ -723,5 +723,16 @@ void kblockd_flush(void);
#define MODULE_ALIAS_BLOCKDEV_MAJOR(major) \
MODULE_ALIAS("block-major-" __stringify(major) "-*")
+#ifdef CONFIG_GENETIC_IOSCHED_AS
+
+struct disk_stats_snapshot
+{
+ unsigned long reads;
+ unsigned long writes;
+ unsigned long read_sectors;
+ unsigned long write_sectors;
+ unsigned long time_in_queue;
+};
+#endif /* CONFIG_GENETIC_IOSCHED_AS */
#endif
_
Hooked Anticipatory IO scheduler.
Signed-off-by: Jake Moilanen <[email protected]>
---
diff -puN drivers/block/Kconfig.iosched~genetic-as-sched drivers/block/Kconfig.iosched
--- linux-2.6.10/drivers/block/Kconfig.iosched~genetic-as-sched Fri Jan 28 15:53:44 2005
+++ linux-2.6.10-moilanen/drivers/block/Kconfig.iosched Fri Jan 28 15:53:44 2005
@@ -38,4 +38,13 @@ config IOSCHED_CFQ
among all processes in the system. It should provide a fair
working environment, suitable for desktop systems.
+config GENETIC_IOSCHED_AS
+ bool "Genetic Anticipatory I/O scheduler (EXPERIMENTAL)"
+ depends on IOSCHED_AS && GENETIC_LIB && EXPERIMENTAL
+ default n
+ ---help---
+ This will use a genetic algorithm to tweak the tunables of the
+ anticipatory scheduler autonomically and will adapt tunables
+ depending on the present workload.
+
endmenu
diff -puN drivers/block/as-iosched.c~genetic-as-sched drivers/block/as-iosched.c
--- linux-2.6.10/drivers/block/as-iosched.c~genetic-as-sched Fri Jan 28 15:53:44 2005
+++ linux-2.6.10-moilanen/drivers/block/as-iosched.c Wed Feb 2 16:42:02 2005
@@ -20,6 +20,8 @@
#include <linux/hash.h>
#include <linux/rbtree.h>
#include <linux/interrupt.h>
+#include <linux/genetic.h>
+#include <linux/random.h>
#define REQ_SYNC 1
#define REQ_ASYNC 0
@@ -67,6 +69,8 @@
*/
#define MAX_THINKTIME (HZ/50UL)
+unsigned long max_thinktime = MAX_THINKTIME;
+
/* Bits in as_io_context.state */
enum as_io_states {
AS_TASK_RUNNING=0, /* Process has not exitted */
@@ -83,6 +87,53 @@ enum anticipation_status {
* or timed out */
};
+#ifdef CONFIG_GENETIC_IOSCHED_AS
+
+struct disk_stats_snapshot * as_stats_snapshot;
+
+extern void disk_stats_snapshot(phenotype_t * pt);
+
+static void as_create_child(genetic_child_t * child);
+static void as_set_child_genes(void * in_genes);
+static void as_calc_fitness(genetic_child_t * child);
+
+struct genetic_ops as_genetic_ops = {
+ .create_child = as_create_child,
+ .set_child_genes = as_set_child_genes,
+ .calc_fitness = as_calc_fitness,
+ .combine_genes = genetic_generic_combine_genes,
+ .mutate_child = genetic_generic_mutate_child,
+ .take_snapshot = disk_stats_snapshot,
+};
+
+#define AS_NUM_GENES 6
+#define AS_NUM_CHILDREN 8
+
+#define AS_GENERAL_UID 1
+struct as_genes {
+ unsigned long read_expire;
+ unsigned long write_expire;
+ unsigned long read_batch_expire;
+ unsigned long write_batch_expire;
+ unsigned long antic_expire;
+ unsigned long max_thinktime;
+};
+
+gene_param_t as_gene_param[AS_NUM_GENES] = {
+ { HZ/16, 3*HZ/16, default_read_expire, 0}, /* read_expire */
+ { HZ/8, 3*HZ/8, default_write_expire, 0}, /* write_expire */
+ { HZ/4, 3*HZ/4, default_read_batch_expire, 0}, /* read_batch_expire */
+ { HZ/16, 3*HZ/16, default_write_batch_expire, 0},/* write_batch_expire */
+ { HZ/300, HZ/100, default_antic_expire, 0}, /* default_antic_expire */
+ { HZ/100, 3*HZ/100, MAX_THINKTIME, 0}
+};
+
+extern void disk_stats_snapshot(phenotype_t * pt);
+extern unsigned long disk_calc_fitness(genetic_child_t * child);
+
+LIST_HEAD(as_data_list);
+#endif
+
struct as_data {
/*
* run time data
@@ -132,6 +183,9 @@ struct as_data {
unsigned long fifo_expire[2];
unsigned long batch_expire[2];
unsigned long antic_expire;
+#ifdef CONFIG_GENETIC_IOSCHED_AS
+ struct list_head data_list;
+#endif
};
#define list_entry_fifo(ptr) list_entry((ptr), struct as_rq, fifo)
@@ -869,7 +923,7 @@ static void as_update_iohist(struct as_d
if (test_bit(AS_TASK_IORUNNING, &aic->state)
&& in_flight == 0) {
thinktime = jiffies - aic->last_end_request;
- thinktime = min(thinktime, MAX_THINKTIME-1);
+ thinktime = min(thinktime, max_thinktime-1);
} else
thinktime = 0;
as_update_thinktime(ad, aic, thinktime);
@@ -1854,6 +1908,11 @@ static void as_exit_queue(elevator_t *e)
mempool_destroy(ad->arq_pool);
put_io_context(ad->io_context);
+
+#ifdef CONFIG_GENETIC_IOSCHED_AS
+ list_del(&ad->data_list);
+#endif
+
kfree(ad->hash);
kfree(ad);
}
@@ -1916,6 +1975,10 @@ static int as_init_queue(request_queue_t
if (ad->write_batch_count < 2)
ad->write_batch_count = 2;
+#ifdef CONFIG_GENETIC_IOSCHED_AS
+ list_add_tail(&ad->data_list, &as_data_list);
+#endif
+
return 0;
}
@@ -2099,6 +2162,9 @@ static struct elevator_type iosched_as =
static int __init as_init(void)
{
int ret;
+#ifdef CONFIG_GENETIC_IOSCHED_AS
+ genetic_t * genetic = 0;
+#endif
arq_pool = kmem_cache_create("as_arq", sizeof(struct as_rq),
0, 0, NULL, NULL);
@@ -2107,6 +2173,24 @@ static int __init as_init(void)
ret = elv_register(&iosched_as);
if (!ret) {
+
+#ifdef CONFIG_GENETIC_IOSCHED_AS
+ as_stats_snapshot = (struct disk_stats_snapshot *)kmalloc(sizeof(struct disk_stats_snapshot), GFP_KERNEL);
+ if (!as_stats_snapshot)
+ panic("as: failed to malloc enough space");
+
+
+ ret = genetic_init(&genetic, AS_NUM_CHILDREN, 2 * HZ, "as-ioscheduler");
+ if (ret)
+ panic("as: failed to init genetic lib");
+
+ if(genetic_register_phenotype(genetic, &as_genetic_ops, AS_NUM_CHILDREN,
+ "general", AS_NUM_GENES, AS_GENERAL_UID))
+ panic("as: failed to register general phenotype");
+
+ genetic_start(genetic);
+#endif
+
/*
* don't allow AS to get unregistered, since we would have
* to browse all tasks in the system and release their
@@ -2126,6 +2210,51 @@ static void __exit as_exit(void)
elv_unregister(&iosched_as);
}
+#ifdef CONFIG_GENETIC_IOSCHED_AS
+
+/* need to create the genes for the child */
+static void as_create_child(genetic_child_t * child)
+{
+ BUG_ON(!child);
+
+ child->genes = (void *)kmalloc(sizeof(struct as_genes), GFP_KERNEL);
+ if (!child->genes)
+ panic("as_create_child: error mallocing space");
+
+ child->gene_param = as_gene_param;
+ child->num_genes = AS_NUM_GENES;
+ child->stats_snapshot = as_stats_snapshot;
+
+ genetic_create_child_spread(child, AS_NUM_CHILDREN);
+// genetic_create_child_defaults(child);
+}
+
+static void as_set_child_genes(void * in_genes)
+{
+ struct as_genes * genes = (struct as_genes *)in_genes;
+ struct list_head * d;
+ struct as_data * ad;
+
+ list_for_each(d, &as_data_list) {
+ ad = list_entry(d, struct as_data, data_list);
+ ad->fifo_expire[REQ_SYNC] = genes->read_expire;
+ ad->fifo_expire[REQ_ASYNC] = genes->write_expire;
+ ad->antic_expire = genes->antic_expire;
+ ad->batch_expire[REQ_SYNC] = genes->read_batch_expire;
+ ad->batch_expire[REQ_ASYNC] = genes->write_batch_expire;
+ }
+ max_thinktime = genes->max_thinktime;
+
+}
+
+static void as_calc_fitness(genetic_child_t * child)
+{
+ child->fitness = disk_calc_fitness(child);
+}
+
+#endif
+
+
module_init(as_init);
module_exit(as_exit);
_
Here is the patch to hook the zaphod cpu scheduler.
Working w/ Peter Williams, we broke down the zaphod into 6 phenotypes:
Real-Time phenotype
genes: sched_rr_time_slice and contributes to general phenotype
fitness: child's delta for total_rt_delay
Interactiveness phenotype
genes: ia_threshold and contributes to general phenotype
cpu_hog_threshold
fitness: child's delta for total_intr_delay
Fork phenotype
genes: initial_ia_bonus
fitness: child's delta for total_fork_delay
Total Delay phenotype
genes: contributes to general phenotype
fitness: child's delta for total_delay - total_rt_delay - (total_intr_delay - total_rt_intr_delay)
Context Switch phenotype
genes: contributes to general phenotype
fitness: child's delta for nr_context_switches()
General phenotype
genes: time_slice
max_ia_bonus
max_tpt_bonus
bgnd_time_slice_multiplier
zaphod_mode
fitness: Gives weighted points to each child depending on what their ranking was in each of the contributing phenotypes.
(see zaphod_general_calc_post_fitness())
Signed-off-by: Jake Moilanen <[email protected]>
1/12/2004
- Reworked to use phenotypes in the genetic lib.
- Moved snapshots out of set_genes
- Added code in for snapshot call
- Added nr_context_switches as a fitness function
1/7/2004
- Made fixes suggested by Peter Williams such as:
- Fixed up zaphod table gene_param table.
- Made base_prom_interval be a ratio of time_slice.
- Fitness routine uses total_delay.
---
diff -puN include/linux/sched.h~genetic-zaphod-cpu-sched include/linux/sched.h
--- linux-2.6.10/include/linux/sched.h~genetic-zaphod-cpu-sched Fri Jan 28 15:53:51 2005
+++ linux-2.6.10-moilanen/include/linux/sched.h Thu Feb 3 16:00:12 2005
@@ -139,6 +139,19 @@ 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)
+
+#define DEFAULT_UNPRIV_RT_THRESHOLD 10
+
+/*
* This serializes "schedule()" and also protects
* the run-queue from deletions/modifications (but
* _adding_ to the beginning of the run-queue has
@@ -766,6 +779,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);
/*
@@ -1137,8 +1152,61 @@ static inline void arch_pick_mmap_layout
}
#endif
+enum zaphod_mode_enum {
+ ZAPHOD_MODE_PRIORITY_BASED,
+ ZAPHOD_MODE_ENTITLEMENT_BASED
+};
+
+#ifdef CONFIG_GENETIC_ZAPHOD_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 9
+#define ZAPHOD_SCHED_NUM_CHILDREN 8
+//#define ZAPHOD_SCHED_CHILD_LIFESPAN (9 * (HZ / 2))
+#define ZAPHOD_SCHED_CHILD_LIFESPAN (4 * HZ)
+//#define ZAPHOD_SCHED_CHILD_LIFESPAN (6 * HZ)
+
+struct zaphod_rt_genes {
+ unsigned long sched_rr_time_slice;
+};
+struct zaphod_intr_genes {
+ unsigned long ia_threshold;
+ unsigned long cpu_hog_threshold;
+};
+
+struct zaphod_fork_genes {
+ unsigned long initial_ia_bonus;
+};
+
+struct zaphod_general_genes {
+ unsigned long time_slice;
+ unsigned long max_ia_bonus;
+ unsigned long max_tpt_bonus;
+ unsigned long bgnd_time_slice_multiplier;
+ unsigned long zaphod_mode;
+};
+
+struct zaphod_stats_snapshot {
+ /* from struct runq_cpustats */
+ unsigned long long total_delay;
+ unsigned long long total_rt_delay;
+ unsigned long long total_intr_delay;
+ unsigned long long total_rt_intr_delay;
+ unsigned long long total_fork_delay;
+
+ /* from struct cpu_cpustats */
+ unsigned long long nr_switches;
+
+#ifdef CONFIG_SCHEDSTATS
+ /* from sched_info */
+ unsigned long cpu_time;
+ unsigned long run_delay;
+#endif
+};
+
+#endif /* CONFIG_GENETIC_ZAPHOD_CPU_SCHED */
#ifdef CONFIG_MAGIC_SYSRQ
diff -puN kernel/sched.c~genetic-zaphod-cpu-sched kernel/sched.c
--- linux-2.6.10/kernel/sched.c~genetic-zaphod-cpu-sched Fri Jan 28 15:53:51 2005
+++ linux-2.6.10-moilanen/kernel/sched.c Fri Jan 28 15:53:51 2005
@@ -44,6 +44,7 @@
#include <linux/seq_file.h>
#include <linux/syscalls.h>
#include <linux/times.h>
+#include <linux/genetic.h>
#include <asm/tlb.h>
#include <asm/unistd.h>
@@ -58,25 +59,13 @@
#define TASK_NICE(p) PRIO_TO_NICE((p)->static_prio)
/*
- * 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)
-
-/*
* UNPRIV_RT tasks that have a CPU usage rate less than this threshold
* (in parts per thousand) are treated as psuedo RT tasks
*/
-#define DEFAULT_UNPRIV_RT_THRESHOLD 10
unsigned long unpriv_rt_threshold = PROP_FM_PPT(DEFAULT_UNPRIV_RT_THRESHOLD);
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);
/*
* Background tasks may have longer time slices as compensation
@@ -115,6 +104,11 @@ struct prio_slot {
struct list_head queue;
};
+#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.
*
@@ -210,11 +204,6 @@ static DEFINE_PER_CPU(struct runqueue, r
#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)
{
@@ -1210,7 +1199,7 @@ void fastcall wake_up_new_task(task_t *
* No more timeslice fiddling on exit
* (Optionally) log scheduler statistics at exit.
*/
-static int log_at_exit = 0;
+int log_at_exit = 0;
void fastcall sched_exit(task_t * p)
{
struct task_cpustats stats;
@@ -4775,3 +4764,174 @@ ctl_table cpu_sched_table[] = {
{ .ctl_name = CPU_SCHED_END_OF_LIST }
};
#endif
+
+#ifdef CONFIG_GENETIC_ZAPHOD_CPU_SCHED
+
+extern unsigned int max_ia_bonus;
+extern unsigned long ia_threshold;
+extern unsigned long cpu_hog_threshold;
+extern unsigned int initial_ia_bonus;
+extern unsigned int max_tpt_bonus;
+extern enum zaphod_mode_enum zaphod_mode;
+
+void zaphod_rt_set_child_genes(void * in_genes)
+{
+ struct zaphod_rt_genes * genes = (struct zaphod_rt_genes *)in_genes;
+
+ sched_rr_time_slice = genes->sched_rr_time_slice;
+}
+
+void zaphod_intr_set_child_genes(void * in_genes)
+{
+ struct zaphod_intr_genes * genes = (struct zaphod_intr_genes *)in_genes;
+
+ ia_threshold = ppt_to_proportion(genes->ia_threshold);
+ cpu_hog_threshold = ppt_to_proportion(genes->cpu_hog_threshold);
+}
+
+void zaphod_fork_set_child_genes(void * in_genes)
+{
+ struct zaphod_fork_genes * genes = (struct zaphod_fork_genes *)in_genes;
+
+ initial_ia_bonus = genes->initial_ia_bonus;
+}
+
+void zaphod_general_set_child_genes(void * in_genes)
+{
+ struct zaphod_general_genes * genes = (struct zaphod_general_genes *)in_genes;
+
+ time_slice = genes->time_slice;
+ base_prom_interval = ((time_slice * 15) / 10);
+ max_ia_bonus = genes->max_ia_bonus;
+ max_tpt_bonus = genes->max_tpt_bonus;
+ bgnd_time_slice_multiplier = genes->bgnd_time_slice_multiplier;
+ zaphod_mode = genes->zaphod_mode;
+
+}
+
+/* Just have the general phenotype take the whole snapshot */
+void zaphod_general_take_snapshot(phenotype_t * pt)
+{
+ struct runq_cpustats * csrq;
+ struct zaphod_stats_snapshot * ss = (struct zaphod_stats_snapshot *)pt->child_ranking[0]->stats_snapshot;
+#ifdef CONFIG_SCHEDSTATS
+ runqueue_t * rq;
+#endif
+ int cpu;
+
+ memset(ss, 0, sizeof(struct zaphod_stats_snapshot));
+
+ /* Get snapshot for this child */
+ for_each_online_cpu(cpu) {
+ csrq = cpu_runq_cpustats(cpu);
+
+ ss->total_delay += csrq->total_delay;
+ ss->total_rt_delay += csrq->total_rt_delay;
+ ss->total_intr_delay += csrq->total_intr_delay;
+ ss->total_rt_intr_delay += csrq->total_rt_intr_delay;
+ ss->total_fork_delay += csrq->total_fork_delay;
+
+ }
+
+#ifdef CONFIG_SCHEDSTATS
+ for_each_online_cpu(cpu) {
+ rq = cpu_rq(cpu);
+
+ ss->cpu_time += rq->rq_sched_info.cpu_time;
+ ss->run_delay += rq->rq_sched_info.run_delay;
+ }
+#endif
+
+ ss->nr_switches += nr_context_switches();
+
+
+
+}
+
+void zaphod_rt_calc_fitness(genetic_child_t * child)
+{
+
+ struct zaphod_stats_snapshot * ss = (struct zaphod_stats_snapshot *)child->stats_snapshot;
+ struct runq_cpustats *csrq;
+ long long total_rt_delay = 0;
+ int cpu;
+
+ for_each_online_cpu(cpu) {
+ csrq = cpu_runq_cpustats(cpu);
+
+ total_rt_delay += csrq->total_rt_delay;
+ }
+ child->fitness = -(total_rt_delay - ss->total_rt_delay);
+
+}
+
+void zaphod_intr_calc_fitness(genetic_child_t * child)
+{
+ struct zaphod_stats_snapshot * ss = (struct zaphod_stats_snapshot *)child->stats_snapshot;
+ struct runq_cpustats *csrq;
+ long long total_intr_delay = 0;
+ int cpu;
+
+ for_each_online_cpu(cpu) {
+ csrq = cpu_runq_cpustats(cpu);
+
+ total_intr_delay += csrq->total_intr_delay;
+ }
+ child->fitness = -(total_intr_delay - ss->total_intr_delay);
+
+}
+
+void zaphod_fork_calc_fitness(genetic_child_t * child)
+{
+ struct zaphod_stats_snapshot * ss = (struct zaphod_stats_snapshot *)child->stats_snapshot;
+ struct runq_cpustats *csrq;
+ long long total_fork_delay = 0;
+ int cpu;
+
+ for_each_online_cpu(cpu) {
+ csrq = cpu_runq_cpustats(cpu);
+
+ total_fork_delay += csrq->total_fork_delay;
+ }
+ child->fitness = -(total_fork_delay - ss->total_fork_delay);
+
+}
+
+void zaphod_total_delay_calc_fitness(genetic_child_t * child)
+{
+ struct zaphod_stats_snapshot * ss = (struct zaphod_stats_snapshot *)child->stats_snapshot;
+ struct runq_cpustats *csrq;
+ long long total_delay = 0;
+ long long total_rt_delay = 0;
+ long long total_intr_delay = 0;
+ long long total_rt_intr_delay = 0;
+ int cpu;
+
+ for_each_online_cpu(cpu) {
+ csrq = cpu_runq_cpustats(cpu);
+
+ total_delay += csrq->total_delay;
+ total_intr_delay += csrq->total_intr_delay;
+ total_rt_delay += csrq->total_rt_delay;
+ total_rt_intr_delay += csrq->total_rt_intr_delay;
+ }
+
+ /* get delta */
+ total_delay -= ss->total_delay;
+ total_rt_delay -= ss->total_rt_delay;
+ total_intr_delay -= ss->total_intr_delay;
+ total_rt_intr_delay -= ss->total_rt_intr_delay;
+
+ child->fitness = -(total_delay - total_rt_delay - (total_intr_delay - total_rt_intr_delay));
+
+}
+
+void zaphod_context_switches_calc_fitness(genetic_child_t * child)
+{
+ struct zaphod_stats_snapshot * ss = (struct zaphod_stats_snapshot *)child->stats_snapshot;
+
+ child->fitness = -(nr_context_switches() - ss->nr_switches);
+}
+
+#endif /* CONFIG_GENETIC_ZAPHOD_CPU_SCHED */
+
diff -puN kernel/sched_zaphod.c~genetic-zaphod-cpu-sched kernel/sched_zaphod.c
--- linux-2.6.10/kernel/sched_zaphod.c~genetic-zaphod-cpu-sched Fri Jan 28 15:53:51 2005
+++ linux-2.6.10-moilanen/kernel/sched_zaphod.c Thu Feb 3 09:02:43 2005
@@ -21,9 +21,13 @@
*/
#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 = ZAPHOD_MODE_PRIORITY_BASED;
+
#ifdef CONFIG_CPUSCHED_ZAPHOD
#define MAX_PRIO ZAPHOD_MAX_PRIO
#define MIN_NORMAL_PRIO ZAPHOD_MIN_NORMAL_PRIO
@@ -42,13 +46,6 @@
#define EB_YARDSTICK_DECAY_INTERVAL 100
-enum zaphod_mode_enum {
- ZAPHOD_MODE_PRIORITY_BASED,
- ZAPHOD_MODE_ENTITLEMENT_BASED
-};
-
-static enum zaphod_mode_enum zaphod_mode = ZAPHOD_MODE_PRIORITY_BASED;
-
#ifdef CONFIG_SYSCTL
static const char *zaphod_mode_names[] = {
"pb", /* ZAPHOD_MODE_PRIORITY_BASED */
@@ -446,6 +443,353 @@ void zaphod_reassess_at_renice(struct ta
calculate_pre_bonus_priority(p);
}
+#ifdef CONFIG_GENETIC_ZAPHOD_CPU_SCHED
+
+extern unsigned long sched_rr_time_slice;
+extern unsigned long base_prom_interval;
+static void zaphod_rt_create_child(genetic_child_t *);
+static void zaphod_intr_create_child(genetic_child_t *);
+static void zaphod_fork_create_child(genetic_child_t *);
+static void zaphod_total_delay_create_child(genetic_child_t *);
+static void zaphod_context_switches_create_child(genetic_child_t *);
+static void zaphod_general_create_child(genetic_child_t *);
+static void zaphod_shift_mutation_rate(phenotype_t * in_pt);
+
+void zaphod_rt_set_child_genes(void *);
+void zaphod_intr_set_child_genes(void *);
+void zaphod_fork_set_child_genes(void *);
+void zaphod_general_set_child_genes(void *);
+
+void zaphod_rt_calc_fitness(genetic_child_t *);
+void zaphod_intr_calc_fitness(genetic_child_t *);
+void zaphod_fork_calc_fitness(genetic_child_t *);
+void zaphod_total_delay_calc_fitness(genetic_child_t *);
+void zaphod_context_switches_calc_fitness(genetic_child_t *);
+
+void zaphod_general_calc_post_fitness(phenotype_t *);
+
+void zaphod_general_take_snapshot(phenotype_t *);
+
+/* For real-time tasks */
+struct genetic_ops zaphod_rt_genetic_ops = {
+ .create_child = zaphod_rt_create_child,
+ .set_child_genes = zaphod_rt_set_child_genes,
+ .calc_fitness = zaphod_rt_calc_fitness,
+ .combine_genes = genetic_generic_combine_genes,
+ .mutate_child = genetic_generic_mutate_child,
+};
+
+/* For interactivity */
+struct genetic_ops zaphod_intr_genetic_ops = {
+ .create_child = zaphod_intr_create_child,
+ .set_child_genes = zaphod_intr_set_child_genes,
+ .calc_fitness = zaphod_intr_calc_fitness,
+ .combine_genes = genetic_generic_combine_genes,
+ .mutate_child = genetic_generic_mutate_child,
+};
+
+/* For new processes */
+struct genetic_ops zaphod_fork_genetic_ops = {
+ .create_child = zaphod_fork_create_child,
+ .set_child_genes = zaphod_fork_set_child_genes,
+ .calc_fitness = zaphod_fork_calc_fitness,
+ .combine_genes = genetic_generic_combine_genes,
+ .mutate_child = genetic_generic_mutate_child,
+};
+
+/* For total delay */
+struct genetic_ops zaphod_total_delay_genetic_ops = {
+ .create_child = zaphod_total_delay_create_child,
+ .calc_fitness = zaphod_total_delay_calc_fitness,
+};
+
+/* For context switches */
+struct genetic_ops zaphod_context_switches_genetic_ops = {
+ .create_child = zaphod_context_switches_create_child,
+ .calc_fitness = zaphod_context_switches_calc_fitness,
+};
+
+/* For general genes */
+struct genetic_ops zaphod_general_genetic_ops = {
+ .create_child = zaphod_general_create_child,
+ .set_child_genes = zaphod_general_set_child_genes,
+ .combine_genes = genetic_generic_combine_genes,
+ .mutate_child = genetic_generic_mutate_child,
+ .calc_post_fitness = zaphod_general_calc_post_fitness,
+ .take_snapshot = zaphod_general_take_snapshot,
+ .shift_mutation_rate = zaphod_shift_mutation_rate
+};
+
+#define ZAPHOD_RT_UID 1
+#define ZAPHOD_RT_NUM_GENES 1
+gene_param_t zaphod_rt_gene_param[ZAPHOD_RT_NUM_GENES] = {
+ { MIN_TIMESLICE, MAX_TIMESLICE, (100 * HZ / 1000), 0 }, /* sched_rr_time_slice */
+};
+
+#define ZAPHOD_INTR_UID 2
+#define ZAPHOD_INTR_NUM_GENES 2
+#if 1
+gene_param_t zaphod_intr_gene_param[ZAPHOD_INTR_NUM_GENES] = {
+ { 0, 1000, DEFAULT_IA_THRESHOLD, genetic_generic_iterative_mutate_gene }, /* ia_threshold */
+ { 0, 1000, DEFAULT_CPU_HOG_THRESHOLD, genetic_generic_iterative_mutate_gene }, /* cpu_hog_threshold */
+};
+#else
+gene_param_t zaphod_intr_gene_param[ZAPHOD_INTR_NUM_GENES] = {
+ { 0, 1000, DEFAULT_IA_THRESHOLD, 0 }, /* ia_threshold */
+ { 0, 1000, DEFAULT_CPU_HOG_THRESHOLD, 0 }, /* cpu_hog_threshold */
+};
+#endif
+
+#define ZAPHOD_FORK_UID 4
+#define ZAPHOD_FORK_NUM_GENES 1
+gene_param_t zaphod_fork_gene_param[ZAPHOD_FORK_NUM_GENES] = {
+ { 0, MAX_MAX_IA_BONUS, 1, 0 }, /* initial_ia_bonus */
+};
+
+#define ZAPHOD_TOTAL_DELAY_UID 8
+#define ZAPHOD_TOTAL_DELAY_NUM_GENES 0
+
+#define ZAPHOD_CONTEXT_SWITCHES_UID 16
+#define ZAPHOD_CONTEXT_SWITCHES_NUM_GENES 0
+
+#define ZAPHOD_GENERAL_UID (ZAPHOD_CONTEXT_SWITCHES_UID | ZAPHOD_TOTAL_DELAY_UID | ZAPHOD_INTR_UID | ZAPHOD_RT_UID)
+#define ZAPHOD_GENERAL_NUM_GENES 5
+#if 0
+gene_param_t zaphod_general_gene_param[ZAPHOD_GENERAL_NUM_GENES] = {
+ { MIN_TIMESLICE, MAX_TIMESLICE, DEF_TIMESLICE, genetic_generic_iterative_mutate_gene }, /* time_slice */
+ { 0, MAX_MAX_IA_BONUS, DEFAULT_MAX_IA_BONUS, 0 }, /* max_ia_bonus */
+ { 0, MAX_MAX_TPT_BONUS, DEFAULT_MAX_TPT_BONUS, 0 }, /* max_tpt_bonus */
+ { 1, 100, 1, genetic_generic_iterative_mutate_gene }, /* bgnd_time_slice_multiplier */
+ { 0, 1, 0, 0 }, /* zaphod_mode */
+};
+#else
+gene_param_t zaphod_general_gene_param[ZAPHOD_GENERAL_NUM_GENES] = {
+ { MIN_TIMESLICE, MAX_TIMESLICE, DEF_TIMESLICE, 0 }, /* time_slice */
+ { 0, MAX_MAX_IA_BONUS, DEFAULT_MAX_IA_BONUS, 0 }, /* max_ia_bonus */
+ { 0, MAX_MAX_TPT_BONUS, DEFAULT_MAX_TPT_BONUS, 0 }, /* max_tpt_bonus */
+ { 1, 100, 1, genetic_generic_iterative_mutate_gene }, /* bgnd_time_slice_multiplier */
+ { 0, 1, 0, 0 }, /* zaphod_mode */
+};
+#endif
+
+struct zaphod_stats_snapshot * zaphod_stats_snapshot;
+
+static int __init genetic_zaphod_sched_init(void)
+{
+ genetic_t * genetic = 0;
+
+ zaphod_stats_snapshot = (struct zaphod_stats_snapshot *)kmalloc(sizeof(struct zaphod_stats_snapshot), GFP_KERNEL);
+ if (!zaphod_stats_snapshot)
+ panic("zaphod sched: failed to malloc enough space");
+
+ if(genetic_init(&genetic, ZAPHOD_SCHED_NUM_CHILDREN, ZAPHOD_SCHED_CHILD_LIFESPAN,
+ "zaphod-sched"))
+ panic("zaphod sched: failed to init genetic lib");
+
+ if(genetic_register_phenotype(genetic, &zaphod_rt_genetic_ops, ZAPHOD_SCHED_NUM_CHILDREN,
+ "real-time-tasks", ZAPHOD_RT_NUM_GENES, ZAPHOD_RT_UID))
+ panic("zaphod sched: failed to register real-time tasks phenotype");
+
+ if(genetic_register_phenotype(genetic, &zaphod_intr_genetic_ops, ZAPHOD_SCHED_NUM_CHILDREN,
+ "interactiveness", ZAPHOD_INTR_NUM_GENES, ZAPHOD_INTR_UID))
+ panic("zaphod sched: failed to register interactiveness phenotype");
+
+ if(genetic_register_phenotype(genetic, &zaphod_fork_genetic_ops, ZAPHOD_SCHED_NUM_CHILDREN,
+ "initial-interactiveness", ZAPHOD_FORK_NUM_GENES, ZAPHOD_FORK_UID))
+ panic("zaphod sched: failed to register initial-interactiveness phenotype");
+
+ if(genetic_register_phenotype(genetic, &zaphod_total_delay_genetic_ops, ZAPHOD_SCHED_NUM_CHILDREN,
+ "total-delay", ZAPHOD_TOTAL_DELAY_NUM_GENES, ZAPHOD_TOTAL_DELAY_UID))
+ panic("zaphod sched: failed to register total-delay phenotype");
+
+ if(genetic_register_phenotype(genetic, &zaphod_context_switches_genetic_ops, ZAPHOD_SCHED_NUM_CHILDREN,
+ "context-switches", ZAPHOD_CONTEXT_SWITCHES_NUM_GENES, ZAPHOD_CONTEXT_SWITCHES_UID))
+ panic("zaphod sched: failed to register context-switches phenotype");
+
+ if(genetic_register_phenotype(genetic, &zaphod_general_genetic_ops, ZAPHOD_SCHED_NUM_CHILDREN,
+ "general", ZAPHOD_GENERAL_NUM_GENES, ZAPHOD_GENERAL_UID))
+ panic("zaphod sched: failed to register general phenotype");
+
+ genetic_start(genetic);
+
+ return 0;
+}
+
+void zaphod_rt_create_child(genetic_child_t * child)
+{
+ BUG_ON(!child);
+
+ child->genes = (void *)kmalloc(sizeof(struct zaphod_rt_genes), GFP_KERNEL);
+ if (!child->genes)
+ panic("zaphod_rt_create_child: error kmalloc'n space");
+
+ child->gene_param = zaphod_rt_gene_param;
+ child->num_genes = ZAPHOD_RT_NUM_GENES;
+ child->stats_snapshot = zaphod_stats_snapshot;
+
+// genetic_create_child_spread(child, ZAPHOD_SCHED_NUM_CHILDREN);
+ genetic_create_child_defaults(child);
+
+}
+
+void zaphod_intr_create_child(genetic_child_t * child)
+{
+ BUG_ON(!child);
+
+ child->genes = (void *)kmalloc(sizeof(struct zaphod_intr_genes), GFP_KERNEL);
+ if (!child->genes)
+ panic("zaphod_intr_create_child: error kmalloc'n space");
+
+ child->gene_param = zaphod_intr_gene_param;
+ child->num_genes = ZAPHOD_INTR_NUM_GENES;
+ child->stats_snapshot = zaphod_stats_snapshot;
+
+// genetic_create_child_spread(child, ZAPHOD_SCHED_NUM_CHILDREN);
+ genetic_create_child_defaults(child);
+}
+
+void zaphod_fork_create_child(genetic_child_t * child)
+{
+ BUG_ON(!child);
+
+ child->genes = (void *)kmalloc(sizeof(struct zaphod_fork_genes), GFP_KERNEL);
+ if (!child->genes)
+ panic("zaphod_fork_create_child: error kmalloc'n space");
+
+ child->gene_param = zaphod_fork_gene_param;
+ child->num_genes = ZAPHOD_FORK_NUM_GENES;
+ child->stats_snapshot = zaphod_stats_snapshot;
+
+// genetic_create_child_spread(child, ZAPHOD_SCHED_NUM_CHILDREN);
+ genetic_create_child_defaults(child);
+}
+
+void zaphod_total_delay_create_child(genetic_child_t * child)
+{
+ BUG_ON(!child);
+
+ child->genes = 0;
+ child->gene_param = 0;
+ child->num_genes = 0;
+ child->stats_snapshot = zaphod_stats_snapshot;
+}
+
+void zaphod_context_switches_create_child(genetic_child_t * child)
+{
+ BUG_ON(!child);
+
+ child->genes = 0;
+ child->gene_param = 0;
+ child->num_genes = 0;
+ child->stats_snapshot = zaphod_stats_snapshot;
+}
+
+void zaphod_general_create_child(genetic_child_t * child)
+{
+ BUG_ON(!child);
+
+ child->genes = (void *)kmalloc(sizeof(struct zaphod_general_genes), GFP_KERNEL);
+ if (!child->genes)
+ panic("zaphod_general_create_child: error kmalloc'n space");
+
+ child->gene_param = zaphod_general_gene_param;
+ child->num_genes = ZAPHOD_GENERAL_NUM_GENES;
+ child->stats_snapshot = zaphod_stats_snapshot;
+
+ genetic_create_child_spread(child, ZAPHOD_SCHED_NUM_CHILDREN);
+// genetic_create_child_defaults(child);
+}
+
+
+static void zaphod_shift_mutation_rate(phenotype_t * in_pt)
+{
+ struct list_head * p;
+ phenotype_t * pt;
+ int count = 0;
+ long rate = 0;
+
+ list_for_each(p, &in_pt->genetic->phenotype) {
+ pt = list_entry(p, phenotype_t, phenotype);
+
+ /* Look at everyone else that contributes to this
+ phenotype */
+ if (pt->uid & ZAPHOD_GENERAL_UID && pt->uid != ZAPHOD_GENERAL_UID) {
+
+ switch (pt->uid) {
+ case ZAPHOD_RT_UID:
+ break;
+ case ZAPHOD_CONTEXT_SWITCHES_UID:
+ break;
+ case ZAPHOD_INTR_UID:
+ case ZAPHOD_TOTAL_DELAY_UID:
+ rate += pt->mutation_rate;
+ count++;
+ break;
+ default:
+ BUG();
+ }
+ }
+ }
+
+ /* If we are a general phenotype that is made up of other
+ phenotypes then we take the average */
+ if (count)
+ in_pt->mutation_rate = (rate / count);
+ else
+ BUG();
+}
+
+
+/* Make the general the one that takes into account all the fitness
+ * routines, since these are the common genes that effect everything.
+ */
+void zaphod_general_calc_post_fitness(phenotype_t * in_pt)
+{
+ struct list_head * p;
+ phenotype_t * pt;
+ genetic_t * genetic = in_pt->genetic;
+ int ranking[ZAPHOD_SCHED_NUM_CHILDREN];
+ int weight = 1;
+ int i;
+
+ memset(ranking, 0, sizeof(ranking));
+
+ list_for_each(p, &genetic->phenotype) {
+ pt = list_entry(p, phenotype_t, phenotype);
+
+ /* Look at everyone else that contributes to this
+ phenotype */
+ if (pt->uid & ZAPHOD_GENERAL_UID && pt->uid != ZAPHOD_GENERAL_UID) {
+
+ switch (pt->uid) {
+ case ZAPHOD_RT_UID:
+ case ZAPHOD_CONTEXT_SWITCHES_UID:
+ weight = 1;
+ break;
+ case ZAPHOD_INTR_UID:
+ weight = 2;
+ break;
+ case ZAPHOD_TOTAL_DELAY_UID:
+ weight = 3;
+ break;
+ default:
+ BUG();
+ }
+
+ for (i = 0; i < pt->num_children; i++)
+ ranking[pt->child_ranking[i]->id] += (i * weight);
+ }
+ }
+
+ for (i = 0; i < in_pt->num_children; i++)
+ in_pt->child_ranking[i]->fitness = ranking[i];
+
+}
+
+core_initcall(genetic_zaphod_sched_init);
+
+#endif /* CONFIG_GENETIC_ZAPHOD_CPU_SCHED */
+
#if defined(CONFIG_SYSCTL)
static const unsigned int zero = 0;
@@ -455,6 +799,8 @@ int proc_zaphod_mode(ctl_table *ctp, int
void __user *buffer, size_t *lenp, loff_t *ppos)
{
int res;
+
+ BUG_ON(zaphod_mode >= 2);
strcpy(current_zaphod_mode, zaphod_mode_names[zaphod_mode]);
res = proc_dostring(ctp, write, fp, buffer, lenp, ppos);
diff -puN lib/Kconfig~genetic-zaphod-cpu-sched lib/Kconfig
--- linux-2.6.10/lib/Kconfig~genetic-zaphod-cpu-sched Fri Jan 28 15:53:51 2005
+++ linux-2.6.10-moilanen/lib/Kconfig Fri Jan 28 15:53:51 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_ZAPHOD_CPU_SCHED
+ bool "Genetic Library - Zaphod CPU scheduler"
+ depends on GENETIC_LIB && EXPERIMENTAL
+ help
+ This option will enable the genetic library on the zaphod
+ CPU scheduler.
+
#
# compression support is select'ed if needed
#
diff -puN include/linux/sched_cpustats.h~genetic-zaphod-cpu-sched include/linux/sched_cpustats.h
_