aboutsummaryrefslogtreecommitdiffstats
path: root/mm/thrash.c
diff options
context:
space:
mode:
authorAshwin Chaugule <ashwin.chaugule@celunite.com>2006-12-06 23:31:57 -0500
committerLinus Torvalds <torvalds@woody.osdl.org>2006-12-07 11:39:21 -0500
commit7602bdf2fd14a40dd9b104e516fdc05e1bd17952 (patch)
tree5ca703b0a95f6f2e6d977c816532b9085f453974 /mm/thrash.c
parent098fe651f7e9d759d1117c78c1a642b9b3945922 (diff)
[PATCH] new scheme to preempt swap token
The new swap token patches replace the current token traversal algo. The old algo had a crude timeout parameter that was used to handover the token from one task to another. This algo, transfers the token to the tasks that are in need of the token. The urgency for the token is based on the number of times a task is required to swap-in pages. Accordingly, the priority of a task is incremented if it has been badly affected due to swap-outs. To ensure that the token doesnt bounce around rapidly, the token holders are given a priority boost. The priority of tasks is also decremented, if their rate of swap-in's keeps reducing. This way, the condition to check whether to pre-empt the swap token, is a matter of comparing two task's priority fields. [akpm@osdl.org: cleanups] Signed-off-by: Ashwin Chaugule <ashwin.chaugule@celunite.com> Cc: Rik van Riel <riel@redhat.com> Cc: Peter Zijlstra <a.p.zijlstra@chello.nl> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
Diffstat (limited to 'mm/thrash.c')
-rw-r--r--mm/thrash.c116
1 files changed, 45 insertions, 71 deletions
diff --git a/mm/thrash.c b/mm/thrash.c
index f4c560b4a2b7..19e428ca8b03 100644
--- a/mm/thrash.c
+++ b/mm/thrash.c
@@ -7,100 +7,74 @@
7 * 7 *
8 * Simple token based thrashing protection, using the algorithm 8 * Simple token based thrashing protection, using the algorithm
9 * described in: http://www.cs.wm.edu/~sjiang/token.pdf 9 * described in: http://www.cs.wm.edu/~sjiang/token.pdf
10 *
11 * Sep 2006, Ashwin Chaugule <ashwin.chaugule@celunite.com>
12 * Improved algorithm to pass token:
13 * Each task has a priority which is incremented if it contended
14 * for the token in an interval less than its previous attempt.
15 * If the token is acquired, that task's priority is boosted to prevent
16 * the token from bouncing around too often and to let the task make
17 * some progress in its execution.
10 */ 18 */
19
11#include <linux/jiffies.h> 20#include <linux/jiffies.h>
12#include <linux/mm.h> 21#include <linux/mm.h>
13#include <linux/sched.h> 22#include <linux/sched.h>
14#include <linux/swap.h> 23#include <linux/swap.h>
15 24
16static DEFINE_SPINLOCK(swap_token_lock); 25static DEFINE_SPINLOCK(swap_token_lock);
17static unsigned long swap_token_timeout; 26struct mm_struct *swap_token_mm;
18static unsigned long swap_token_check; 27unsigned int global_faults;
19struct mm_struct * swap_token_mm = &init_mm;
20
21#define SWAP_TOKEN_CHECK_INTERVAL (HZ * 2)
22#define SWAP_TOKEN_TIMEOUT (300 * HZ)
23/*
24 * Currently disabled; Needs further code to work at HZ * 300.
25 */
26unsigned long swap_token_default_timeout = SWAP_TOKEN_TIMEOUT;
27
28/*
29 * Take the token away if the process had no page faults
30 * in the last interval, or if it has held the token for
31 * too long.
32 */
33#define SWAP_TOKEN_ENOUGH_RSS 1
34#define SWAP_TOKEN_TIMED_OUT 2
35static int should_release_swap_token(struct mm_struct *mm)
36{
37 int ret = 0;
38 if (!mm->recent_pagein)
39 ret = SWAP_TOKEN_ENOUGH_RSS;
40 else if (time_after(jiffies, swap_token_timeout))
41 ret = SWAP_TOKEN_TIMED_OUT;
42 mm->recent_pagein = 0;
43 return ret;
44}
45 28
46/*
47 * Try to grab the swapout protection token. We only try to
48 * grab it once every TOKEN_CHECK_INTERVAL, both to prevent
49 * SMP lock contention and to check that the process that held
50 * the token before is no longer thrashing.
51 */
52void grab_swap_token(void) 29void grab_swap_token(void)
53{ 30{
54 struct mm_struct *mm; 31 int current_interval;
55 int reason;
56 32
57 /* We have the token. Let others know we still need it. */ 33 global_faults++;
58 if (has_swap_token(current->mm)) {
59 current->mm->recent_pagein = 1;
60 if (unlikely(!swap_token_default_timeout))
61 disable_swap_token();
62 return;
63 }
64
65 if (time_after(jiffies, swap_token_check)) {
66 34
67 if (!swap_token_default_timeout) { 35 current_interval = global_faults - current->mm->faultstamp;
68 swap_token_check = jiffies + SWAP_TOKEN_CHECK_INTERVAL;
69 return;
70 }
71
72 /* ... or if we recently held the token. */
73 if (time_before(jiffies, current->mm->swap_token_time))
74 return;
75 36
76 if (!spin_trylock(&swap_token_lock)) 37 if (!spin_trylock(&swap_token_lock))
77 return; 38 return;
78 39
79 swap_token_check = jiffies + SWAP_TOKEN_CHECK_INTERVAL; 40 /* First come first served */
41 if (swap_token_mm == NULL) {
42 current->mm->token_priority = current->mm->token_priority + 2;
43 swap_token_mm = current->mm;
44 goto out;
45 }
80 46
81 mm = swap_token_mm; 47 if (current->mm != swap_token_mm) {
82 if ((reason = should_release_swap_token(mm))) { 48 if (current_interval < current->mm->last_interval)
83 unsigned long eligible = jiffies; 49 current->mm->token_priority++;
84 if (reason == SWAP_TOKEN_TIMED_OUT) { 50 else {
85 eligible += swap_token_default_timeout; 51 current->mm->token_priority--;
86 } 52 if (unlikely(current->mm->token_priority < 0))
87 mm->swap_token_time = eligible; 53 current->mm->token_priority = 0;
88 swap_token_timeout = jiffies + swap_token_default_timeout; 54 }
55 /* Check if we deserve the token */
56 if (current->mm->token_priority >
57 swap_token_mm->token_priority) {
58 current->mm->token_priority += 2;
89 swap_token_mm = current->mm; 59 swap_token_mm = current->mm;
90 } 60 }
91 spin_unlock(&swap_token_lock); 61 } else {
62 /* Token holder came in again! */
63 current->mm->token_priority += 2;
92 } 64 }
93 return; 65
66out:
67 current->mm->faultstamp = global_faults;
68 current->mm->last_interval = current_interval;
69 spin_unlock(&swap_token_lock);
70return;
94} 71}
95 72
96/* Called on process exit. */ 73/* Called on process exit. */
97void __put_swap_token(struct mm_struct *mm) 74void __put_swap_token(struct mm_struct *mm)
98{ 75{
99 spin_lock(&swap_token_lock); 76 spin_lock(&swap_token_lock);
100 if (likely(mm == swap_token_mm)) { 77 if (likely(mm == swap_token_mm))
101 mm->swap_token_time = jiffies + SWAP_TOKEN_CHECK_INTERVAL; 78 swap_token_mm = NULL;
102 swap_token_mm = &init_mm;
103 swap_token_check = jiffies;
104 }
105 spin_unlock(&swap_token_lock); 79 spin_unlock(&swap_token_lock);
106} 80}