* [ANNOUNCE 1/4] Genetic-lib version 0.2
2005-02-15 19:29 [ANNOUNCE 0/4] Genetic-lib version 0.2 Jake Moilanen
@ 2005-02-15 19:34 ` Jake Moilanen
2005-02-15 19:37 ` [ANNOUNCE 2/4] " Jake Moilanen
` (2 subsequent siblings)
3 siblings, 0 replies; 5+ messages in thread
From: Jake Moilanen @ 2005-02-15 19:34 UTC (permalink / raw)
To: linux-kernel; +Cc: pwil3058
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 <moilanen@austin.ibm.com>
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 <moilanen@austin.ibm.com>
+ * 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 <moilanen@austin.ibm.com>
+ * 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);
_
^ permalink raw reply [flat|nested] 5+ messages in thread* [ANNOUNCE 2/4] Genetic-lib version 0.2
2005-02-15 19:29 [ANNOUNCE 0/4] Genetic-lib version 0.2 Jake Moilanen
2005-02-15 19:34 ` [ANNOUNCE 1/4] " Jake Moilanen
@ 2005-02-15 19:37 ` Jake Moilanen
2005-02-15 19:39 ` [ANNOUNCE 3/4] " Jake Moilanen
2005-02-15 19:56 ` [ANNOUNCE 4/4] " Jake Moilanen
3 siblings, 0 replies; 5+ messages in thread
From: Jake Moilanen @ 2005-02-15 19:37 UTC (permalink / raw)
To: linux-kernel; +Cc: pwil3058
This is the base patch for the IO Schedulers.
Needs a finer granularity for fitness routines.
Signed-off-by: Jake Moilanen <moilanen@austin.ibm.com>
---
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
_
^ permalink raw reply [flat|nested] 5+ messages in thread* [ANNOUNCE 3/4] Genetic-lib version 0.2
2005-02-15 19:29 [ANNOUNCE 0/4] Genetic-lib version 0.2 Jake Moilanen
2005-02-15 19:34 ` [ANNOUNCE 1/4] " Jake Moilanen
2005-02-15 19:37 ` [ANNOUNCE 2/4] " Jake Moilanen
@ 2005-02-15 19:39 ` Jake Moilanen
2005-02-15 19:56 ` [ANNOUNCE 4/4] " Jake Moilanen
3 siblings, 0 replies; 5+ messages in thread
From: Jake Moilanen @ 2005-02-15 19:39 UTC (permalink / raw)
To: linux-kernel; +Cc: pwil3058
Hooked Anticipatory IO scheduler.
Signed-off-by: Jake Moilanen <moilanen@austin.ibm.com>
---
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);
_
^ permalink raw reply [flat|nested] 5+ messages in thread* [ANNOUNCE 4/4] Genetic-lib version 0.2
2005-02-15 19:29 [ANNOUNCE 0/4] Genetic-lib version 0.2 Jake Moilanen
` (2 preceding siblings ...)
2005-02-15 19:39 ` [ANNOUNCE 3/4] " Jake Moilanen
@ 2005-02-15 19:56 ` Jake Moilanen
3 siblings, 0 replies; 5+ messages in thread
From: Jake Moilanen @ 2005-02-15 19:56 UTC (permalink / raw)
To: linux-kernel; +Cc: pwil3058
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 <moilanen@austin.ibm.com>
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
_
^ permalink raw reply [flat|nested] 5+ messages in thread