OpenVZ Forum - RDF feed
type: channel
items: [RFC | PATCH 0/9] CPU controller over process container
items: [PATCH 1/9] split runqueue
items: [PATCH 2/9] task group priority handling
items: [PATCH 3/9] time slice management
items: [PATCH 4/9] define group operations
items: [PATCH 5/9] deal with movement of tasks across groups
items: [PATCH 6/9] Handle dont care groups
items: [PATCH 7/9] SMP Load balance changes
items: [PATCH 8/9] task_cpu(p) needs to be correct always
items: [PATCH 9/9] Interface with process container patchset
items: Re: [ckrm-tech] [RFC | PATCH 0/9] CPU controller over process container

[RFC | PATCH 0/9] CPU controller over process container
type: item
description: Here's a respin of my earlier CPU controller to work on top of Paul Menage's process container patches. Problem: Current CPU scheduler is very task centric, which makes it difficult to manage cpu resource consumption of a group of (related) tasks. For ex: with the current O(1) scheduler, it is possible for a user to monopolize CPU simply by spawning more and more threads, causing DoS to other users. Requirements: A few of them are: - Provide means to group tasks from user-land and specify limits of CPU bandwidth consumption of each group. CPU bandwidth limit is enforced over some suitable time period. For ex: a 40% limit could mean the task group's usage is limited to 4 sec every 10 sec or 24 sec every minute. - Time period over which bandwidth is controlled to each group to be configurable (?) - Work conserving - Do not let the CPU be idle if there are runnable tasks (even if that means running task-groups that are above their allowed limit) - SMP behavior - Limit to be enforced on all CPUs put together - Real-time tasks - Should be left alone as they are today? i.e real time tasks across groups should be scheduled as if they are in same group - Should cater to requirements of variety of workload characteristics, including bursty ones (?) Salient points about this patch: - Each task-group gets its own runqueue on every cpu. - In addition, there is an active and expired array of task-groups themselves. Task-groups that have expired their quota are put into expired array. - Task-groups have priorities. Priority of a task-group is the same as the priority of the highest-priority runnable task it has. This I feel will retain interactiveness of the system as it is today. - Scheduling the next task involves picking highest priority task-group from active array first and then picking highest-priority task within it. Both steps are O(1). - Token are assigned to task-groups based on their assigned quota. Once they run out of tokens, the task-group is put in an expired array…
creator: Srivatsa Vaddagiri
date: 2007-04-12T17:51:11-00:00

[PATCH 1/9] split runqueue
type: item
description: This patch introduces a new runqueue structure (struct task_grp_rq) which is used to hold "related" tasks together. The structure is quite similar to how the runqueue structure looks today. The scheme is every task group will have its own per-cpu runqueues (which is of type 'struct task_grp_rq'), to hold its tasks together on each CPU. This is in addition to a per-cpu runqueue which holds runnable task-groups themselves. The patch also converts over several references of 'struct rq' to 'struct task_grp_rq' (since tasks now reside in task_grp_rq). Signed-off-by : Srivatsa Vaddagiri <vatsa@in.ibm.com> --- diff -puN init/Kconfig~cpu-controller-v2-split-runqueue init/Kconfig --- linux-2.6.20/init/Kconfig~cpu-controller-v2-split-runqueue 2007-04-11 11:48:33.000000000 +0530 +++ linux-2.6.20-vatsa/init/Kconfig 2007-04-11 11:48:33.000000000 +0530 @@ -285,6 +285,14 @@ config CONTAINER_CPUACCT Provides a simple Resource Controller for monitoring the total CPU consumed by the tasks in a container +config CPUMETER + bool "CPU resource control" + depends on CPUSETS && EXPERIMENTAL + help + This options lets you create cpu resource partitions within + cpusets. Each resource partition can be given a different quota + of CPU usage. + config RELAY bool "Kernel->user space relay support (formerly relayfs)" help diff -puN kernel/sched.c~cpu-controller-v2-split-runqueue kernel/sched.c --- linux-2.6.20/kernel/sched.c~cpu-controller-v2-split-runqueue 2007-04-11 11:48:33.000000000 +0530 +++ linux-2.6.20-vatsa/kernel/sched.c 2007-04-12 11:07:19.000000000 +0530 @@ -192,11 +192,48 @@ static inline unsigned int task_timeslic struct prio_array { unsigned int nr_active; + int best_static_prio; DECLARE_BITMAP(bitmap, MAX_PRIO+1); /* include 1 bit for delimiter */ struct list_head queue[MAX_PRIO]; }; /* + * Each task belong to some task-group. Task-groups and what tasks they contain + * are defined by the administrator using some suitable interface. + * Administrator can also define the CPU bandw…
creator: Srivatsa Vaddagiri
date: 2007-04-12T17:52:47-00:00

[PATCH 2/9] task group priority handling
type: item
description: To retain good interactivity, priority of a task-group is defined to be the same as the priority of the highest-priority runnable task it has in its runqueue. This means as tasks come and go, priority of a task-group can change. This patch deals with such changes to task-group priority. P.S : Is this a good idea? Don't know. Other option is to to have a static task-group priority which is decided by its quota. Signed-off-by : Srivatsa Vaddagiri <vatsa@in.ibm.com> 1 file changed, 78 insertions(+), 2 deletions(-) --- diff -puN kernel/sched.c~rfc kernel/sched.c --- linux-2.6.20/kernel/sched.c~rfc 2007-04-11 12:00:48.000000000 +0530 +++ linux-2.6.20-vatsa/kernel/sched.c 2007-04-12 11:07:18.000000000 +0530 @@ -192,7 +192,7 @@ static inline unsigned int task_timeslic struct prio_array { unsigned int nr_active; - int best_static_prio; + int best_static_prio, best_dyn_prio; DECLARE_BITMAP(bitmap, MAX_PRIO+1); /* include 1 bit for delimiter */ struct list_head queue[MAX_PRIO]; }; @@ -729,6 +729,55 @@ sched_info_switch(struct task_struct *pr #define sched_info_switch(t, next) do { } while (0) #endif /* CONFIG_SCHEDSTATS || CONFIG_TASK_DELAY_ACCT */ +/* Dequeue task-group object from the main per-cpu runqueue */ +static void dequeue_task_grp(struct task_grp_rq *tgrq) +{ + struct prio_array *array = tgrq->rq_array; + + array->nr_active--; + list_del(&tgrq->list); + if (list_empty(array->queue + tgrq->prio)) + __clear_bit(tgrq->prio, array->bitmap); + tgrq->rq_array = NULL; +} + +/* Enqueue task-group object on the main per-cpu runqueue */ +static void enqueue_task_grp(struct task_grp_rq *tgrq, struct prio_array *array, + int head) +{ + if (!head) + list_add_tail(&tgrq->list, array->queue + tgrq->prio); + else + list_add(&tgrq->list, array->queue + tgrq->prio); + __set_bit(tgrq->prio, array->bitmap); + array->nr_active++; + tgrq->rq_array = array; +} + +/* Priority of a task-group is defined to be the priority of the highest + * priority runnable task it has. As tasks belonging …
creator: Srivatsa Vaddagiri
date: 2007-04-12T17:53:58-00:00

[PATCH 3/9] time slice management
type: item
description: This patch does the actual job of dividing up CPU time amonmg various task-groups as per their quota. High-level overview: Lets say that we have three task-groups/classes A, B and C whose quota is 50%, 30% and 20%. The quota specifies how much of execution time each group gets per some quantum. If 10 seconds is chosen as this quantum, then group A's tasks get 5 seconds worth of execution time -every- 10 seconds, grp B gets 3 seconds and so on, as shown below: A (5 sec) B (3 sec) C (2 sec) |------------------------|---------------|-----------| T0<---------------- 10 sec quantum ----------------->T1 In this scheme, grp C's tasks could starve potentially, waiting for their turn. This patch avoids the above problem by breaking the 10 sec quantum into several smaller quantums. A, B and C get their due share in each smaller quantum and hence each group progress more quickly than in the above scheme. A B C A B C A B C A B C |-----|---|--|-----|---|--| .../ / ...|-----|---|--|-----|---|--| |<---------->|<---------->| |<---------->| 1 sec 1 sec 1 sec ^ ^ | | (CPU_CONTROL_SHORT_WINDOW) |<------------------------------------------------------------->| 10 sec quantum (CPU_CONTROL_LONG_WINDOW) The latter scheme is implemented by maintaining two counters (tokens) for each task-group (on each CPU). o ticks -> which is exhausted over the short quantum o long_ticks -> which is exhausted over the longer quantum To begin with: grp->ticks = grp->quota * CPU_CONTROL_SHORT_WINDOW * HZ grp->long_ticks = CPU_CONTROL_LONG_WINDOW/CPU_CONTROL_SHORT_WINDOW grp->ticks is decremented every timer ticks. When it hits zero, grp->long_ticks is decremented. If resulting grp->long_ticks is non-zero, grp->ticks wraps back to the initial value and the group is put in an expired bucket. Else if resulting grp->long_ticks is zero, the group is put in a greedy bucket. Signed-off-by : Srivatsa Vaddagiri <vatsa@in.ibm.com> --- --- 1 file changed, 115 insertions(+), 9 deletions(-) --- diff -puN kernel/sched.c~…
creator: Srivatsa Vaddagiri
date: 2007-04-12T17:54:52-00:00

[PATCH 4/9] define group operations
type: item
description: Define these operations for a task-group: - create new group - destroy existing group - set bandwidth (quota) for a group - get bandwidth (quota) of a group Signed-off-by : Srivatsa Vaddagiri <vatsa@in.ibm.com> 1 file changed, 71 insertions(+) --- diff -puN kernel/sched.c~grp_ops kernel/sched.c --- linux-2.6.20/kernel/sched.c~grp_ops 2007-04-11 12:00:50.000000000 +0530 +++ linux-2.6.20-vatsa/kernel/sched.c 2007-04-12 11:07:17.000000000 +0530 @@ -7379,3 +7379,74 @@ void set_curr_task(int cpu, struct task_ } #endif + +#ifdef CONFIG_CPUMETER + +/* Allocate runqueue structures for the new task-group */ +static int sched_create_group(void) +{ + struct task_grp *tg; + struct task_grp_rq *tgrq; + int i; + + tg = kzalloc(sizeof(*tg), GFP_KERNEL); + if (!tg) + return -ENOMEM; + + tg->ticks = CPU_CONTROL_SHORT_WINDOW; + tg->long_ticks = NUM_LONG_TICKS; + + for_each_possible_cpu(i) { + tgrq = kzalloc(sizeof(*tgrq), GFP_KERNEL); + if (!tgrq) + goto oom; + tg->rq[i] = tgrq; + task_grp_rq_init(tgrq, tg); + } + + /* A later patch will make 'tg' accessible beyond this function */ + return 0; +oom: + while (i--) + kfree(tg->rq[i]); + + kfree(tg); + return -ENOMEM; +} + +/* Deallocate runqueue structures */ +static void sched_destroy_group(struct task_grp *tg) +{ + int i; + + for_each_possible_cpu(i) + kfree(tg->rq[i]); + + kfree(tg); +} + +/* Assign quota to this group */ +static int sched_set_quota(struct task_grp *tg, int quota) +{ + int i; + + tg->ticks = (quota * CPU_CONTROL_SHORT_WINDOW) / 100; + + for_each_possible_cpu(i) + tg->rq[i]->ticks = tg->ticks; + + return 0; +} + +static inline int cpu_quota(struct task_grp *tg) +{ + return (tg->ticks * 100) / CPU_CONTROL_SHORT_WINDOW; +} + +/* Return assigned quota for this group */ +static int sched_get_quota(struct task_grp *tg) +{ + return cpu_quota(tg); +} + +#endif /* CONFIG_CPUMETER */ _ -- Regards, vatsa _______________________________________________ Containers mailing list Containers@lists.linux-foundation.org https://lists.…
creator: Srivatsa Vaddagiri
date: 2007-04-12T17:56:08-00:00

[PATCH 5/9] deal with movement of tasks across groups
type: item
description: When a task moves between groups (as initiated by an administrator), it has to be removed from the runqueue of its old group and added to the runqueue of its new group. This patch defines this move operation. Signed-off-by : Srivatsa Vaddagiri <vatsa@in.ibm.com> 1 file changed, 28 insertions(+) --- diff -puN kernel/sched.c~task_move kernel/sched.c --- linux-2.6.20/kernel/sched.c~task_move 2007-04-11 12:00:51.000000000 +0530 +++ linux-2.6.20-vatsa/kernel/sched.c 2007-04-12 11:07:16.000000000 +0530 @@ -7449,4 +7449,32 @@ static int sched_get_quota(struct task_g return cpu_quota(tg); } +/* + * Move a task from one group to another. If the task is already on a + * runqueue, this involves removing the task from its old group's runqueue + * and adding to its new group's runqueue. + */ +static void sched_move_task(struct task_grp *tg_new, struct task_grp *tg_old, + struct task_struct *tsk) +{ + struct rq *rq; + unsigned long flags; + + if (tg_new == tg_old) + return; + + rq = task_rq_lock(tsk, &flags); + + if (tsk->array) { + /* Set tsk->group to tg_old here */ + deactivate_task(tsk, rq); + /* Set tsk->group to tg_new here */ + __activate_task(tsk, rq); + } + + task_rq_unlock(rq, &flags); + + return; +} + #endif /* CONFIG_CPUMETER */ _ -- Regards, vatsa _______________________________________________ Containers mailing list Containers@lists.linux-foundation.org https://lists.linux-foundation.org/mailman/listinfo/containers
creator: Srivatsa Vaddagiri
date: 2007-04-12T17:57:11-00:00

[PATCH 6/9] Handle dont care groups
type: item
description: Deal with task-groups whose bandwidth hasnt been explicitly set by the administrator. Unallocated CPU bandwidth is equally distributed among such "don't care" groups. Signed-off-by : Srivatsa Vaddagiri <vatsa@in.ibm.com> linux-2.6.18-root/include/linux/sched.h | 2 --- 1 file changed, 91 insertions(+), 5 deletions(-) --- diff -puN kernel/sched.c~dont_care kernel/sched.c --- linux-2.6.20/kernel/sched.c~dont_care 2007-04-12 09:09:48.000000000 +0530 +++ linux-2.6.20-vatsa/kernel/sched.c 2007-04-12 11:07:15.000000000 +0530 @@ -227,6 +227,12 @@ static DEFINE_PER_CPU(struct task_grp_rq /* task-group object - maintains information about each task-group */ struct task_grp { unsigned short ticks, long_ticks; /* bandwidth given to task-group */ + int left_over_pct; + int total_dont_care_grps; + int dont_care; /* Does this group care for its bandwidth ? */ + struct task_grp *parent; + struct list_head dont_care_list; + struct list_head list; struct task_grp_rq *rq[NR_CPUS]; /* runqueue pointer for every cpu */ }; @@ -7210,6 +7216,12 @@ void __init sched_init(void) init_task_grp.ticks = CPU_CONTROL_SHORT_WINDOW; /* 100% bandwidth */ init_task_grp.long_ticks = NUM_LONG_TICKS; + init_task_grp.left_over_pct = 100; /* 100% unallocated bandwidth */ + init_task_grp.parent = NULL; + init_task_grp.total_dont_care_grps = 1; /* init_task_grp itself */ + init_task_grp.dont_care = 1; + INIT_LIST_HEAD(&init_task_grp.dont_care_list); + list_add_tail(&init_task_grp.list, &init_task_grp.dont_care_list); for_each_possible_cpu(i) { struct rq *rq; @@ -7382,19 +7394,50 @@ void set_curr_task(int cpu, struct task_ #ifdef CONFIG_CPUMETER +/* Distribute left over bandwidth equally to all "dont care" task groups */ +static void recalc_dontcare(struct task_grp *tg_root) +{ + int ticks; + struct list_head *entry; + + if (!tg_root->total_dont_care_grps) + return; + + ticks = ((tg_root->left_over_pct / tg_root->total_dont_care_grps) * + CPU_CONTROL_SHORT_WINDOW) / 100; + + list_for_each(entry, &tg_root->don…
creator: Srivatsa Vaddagiri
date: 2007-04-12T17:57:54-00:00

[PATCH 7/9] SMP Load balance changes
type: item
description: When balancing tasks across CPU runqueues, we need to take into account the quota of task-groups (for example: we dont want to pull all tasks of a group with 90% limit on the same CPU). This is easily accomplished by piggy backing on the smpnice mechanism. This patch also modifies move_tasks() to look at all the arrays of runqueue for pulling tasks. Signed-off-by : Srivatsa Vaddagiri <vatsa@in.ibm.com> --- --- 1 file changed, 119 insertions(+), 36 deletions(-) --- diff -puN kernel/sched.c~smp kernel/sched.c --- linux-2.6.20/kernel/sched.c~smp 2007-04-12 09:10:38.000000000 +0530 +++ linux-2.6.20-vatsa/kernel/sched.c 2007-04-12 11:07:15.000000000 +0530 @@ -217,7 +217,7 @@ struct task_grp_rq { unsigned long expired_timestamp; unsigned short ticks, long_ticks; int prio; /* Priority of the task-group */ - unsigned long last_update; + unsigned long last_update, raw_weighted_load; struct list_head list; struct task_grp *tg; }; @@ -925,6 +925,11 @@ static inline int __normal_prio(struct t #define RTPRIO_TO_LOAD_WEIGHT(rp) \ (PRIO_TO_LOAD_WEIGHT(MAX_RT_PRIO) + LOAD_WEIGHT(rp)) +static inline int cpu_quota(struct task_grp *tg) +{ + return (tg->ticks * 100) / CPU_CONTROL_SHORT_WINDOW; +} + static void set_load_weight(struct task_struct *p) { if (has_rt_policy(p)) { @@ -938,21 +943,25 @@ static void set_load_weight(struct task_ p->load_weight = 0; else #endif - p->load_weight = RTPRIO_TO_LOAD_WEIGHT(p->rt_priority); + p->load_weight = (RTPRIO_TO_LOAD_WEIGHT(p->rt_priority) + * cpu_quota(task_grp(p))) / 100; } else - p->load_weight = PRIO_TO_LOAD_WEIGHT(p->static_prio); + p->load_weight = (PRIO_TO_LOAD_WEIGHT(p->static_prio) + * cpu_quota(task_grp(p))) / 100; } static inline void -inc_raw_weighted_load(struct rq *rq, const struct task_struct *p) +inc_raw_weighted_load(struct rq *rq, struct task_struct *p) { rq->raw_weighted_load += p->load_weight; + task_grp_rq(p)->raw_weighted_load += p->load_weight; } static inline void -dec_raw_weighted_load(struct rq *rq, const struct task_s…
creator: Srivatsa Vaddagiri
date: 2007-04-12T17:58:44-00:00

[PATCH 8/9] task_cpu(p) needs to be correct always
type: item
description: We rely very much on task_cpu(p) to be correct at all times, so that we can correctly find the task_grp_rq from which the task has to be removed or added to. There is however one place in the scheduler where this assumption of task_cpu(p) being correct is broken. This patch fixes that piece of code. (Thanks to Balbir Singh for pointing this out to me) Signed-off-by : Srivatsa Vaddagiri <vatsa@in.ibm.com> --- --- 1 file changed, 8 insertions(+), 2 deletions(-) --- diff -puN kernel/sched.c~task_cpu kernel/sched.c --- linux-2.6.20/kernel/sched.c~task_cpu 2007-04-12 09:10:39.000000000 +0530 +++ linux-2.6.20-vatsa/kernel/sched.c 2007-04-12 11:07:14.000000000 +0530 @@ -5400,6 +5400,7 @@ static int __migrate_task(struct task_st { struct rq *rq_dest, *rq_src; int ret = 0; + struct prio_array *array; if (unlikely(cpu_is_offline(dest_cpu))) return ret; @@ -5415,8 +5416,8 @@ static int __migrate_task(struct task_st if (!cpu_isset(dest_cpu, p->cpus_allowed)) goto out; - set_task_cpu(p, dest_cpu); - if (p->array) { + array = p->array; + if (array) { /* * Sync timestamp with rq_dest's before activating. * The same thing could be achieved by doing this step @@ -5426,6 +5427,11 @@ static int __migrate_task(struct task_st p->timestamp = p->timestamp - rq_src->most_recent_timestamp + rq_dest->most_recent_timestamp; deactivate_task(p, rq_src); + } + + set_task_cpu(p, dest_cpu); + + if (array) { __activate_task(p, rq_dest); if (TASK_PREEMPTS_CURR(p, rq_dest)) resched_task(rq_dest->curr); _ -- Regards, vatsa _______________________________________________ Containers mailing list Containers@lists.linux-foundation.org https://lists.linux-foundation.org/mailman/listinfo/containers
creator: Srivatsa Vaddagiri
date: 2007-04-12T17:59:37-00:00

[PATCH 9/9] Interface with process container patchset
type: item
description: This patch registers cpu controller as a subsystem in process container patches. How to use the controller: 1. Apply these patches first on top of 2.6.20 kernel http://lkml.org/lkml/2007/4/6/301 http://lkml.org/lkml/2007/4/6/300 http://marc.info/?l=ckrm-tech&m=117590464104300&w=2 2. Apply all patches in this thread (from 1 - 9) 3. Select CONFIG_CPUMETER and build kernel After bootup: # mkdir /dev/cpuctl # mount -t container -o cpuctl none /dev/cpuctl # cd /dev/cpuctl # mkdir a # Create group A # mkdir b # Create group B # echo 80 > a/quota # Give 80% quota to A # echo 20 > b/quota # Give 20% quota to B # echo some_pid > a/tasks # Move some_pid to Group A # echo another_pid > b/tasks # move another task to Group B some_pid and another_pid should share CPU in the ratio of 80:20 now Signed-off-by : Srivatsa Vaddagiri <vatsa@in.ibm.com> --- linux-2.6.20-vatsa/include/linux/container_subsys.h | 6 --- diff -puN include/linux/container_subsys.h~container_if include/linux/container_subsys.h --- linux-2.6.20/include/linux/container_subsys.h~container_if 2007-04-12 09:10:40.000000000 +0530 +++ linux-2.6.20-vatsa/include/linux/container_subsys.h 2007-04-12 09:10:40.000000000 +0530 @@ -17,4 +17,10 @@ SUBSYS(cpuacct) /* */ +#ifdef CONFIG_CPUMETER +SUBSYS(cpuctlr) +#endif + +/* */ + /* */ diff -puN kernel/sched.c~container_if kernel/sched.c --- linux-2.6.20/kernel/sched.c~container_if 2007-04-12 09:10:40.000000000 +0530 +++ linux-2.6.20-vatsa/kernel/sched.c 2007-04-12 11:07:10.000000000 +0530 @@ -53,6 +53,8 @@ #include <linux/kprobes.h> #include <linux/delayacct.h> #include <linux/cpu_acct.h> +#include <linux/container.h> +#include <linux/fs.h> #include <asm/tlb.h> #include <asm/unistd.h> @@ -226,6 +228,7 @@ static DEFINE_PER_CPU(struct task_grp_rq /* task-group object - maintains information about each task-group */ struct task_grp { + struct container_subsys_state css; unsigned short ticks, long_ticks; /* bandwidth given to task-group */ int left_over_pct; int total_dont_care_g…
creator: Srivatsa Vaddagiri
date: 2007-04-12T18:01:27-00:00

Re: [ckrm-tech] [RFC | PATCH 0/9] CPU controller over process container
type: item
description: On Thu, Apr 12, 2007 at 11:21:11PM +0530, Srivatsa Vaddagiri wrote: > - Real-time tasks - Should be left alone as they are today? > i.e real time tasks across groups should be scheduled as if > they are in same group This patchset doesnt handle this requirement (yet). Will handle in future revisions based on feedback. -- Regards, vatsa _______________________________________________ Containers mailing list Containers@lists.linux-foundation.org https://lists.linux-foundation.org/mailman/listinfo/containers
creator: Srivatsa Vaddagiri
date: 2007-04-12T18:04:40-00:00