[PATCH] new scheme to preempt swap token
[linux-2.6.git] / mm / thrash.c
1 /*
2  * mm/thrash.c
3  *
4  * Copyright (C) 2004, Red Hat, Inc.
5  * Copyright (C) 2004, Rik van Riel <riel@redhat.com>
6  * Released under the GPL, see the file COPYING for details.
7  *
8  * Simple token based thrashing protection, using the algorithm
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.
18  */
19
20 #include <linux/jiffies.h>
21 #include <linux/mm.h>
22 #include <linux/sched.h>
23 #include <linux/swap.h>
24
25 static DEFINE_SPINLOCK(swap_token_lock);
26 struct mm_struct *swap_token_mm;
27 unsigned int global_faults;
28
29 void grab_swap_token(void)
30 {
31         int current_interval;
32
33         global_faults++;
34
35         current_interval = global_faults - current->mm->faultstamp;
36
37         if (!spin_trylock(&swap_token_lock))
38                 return;
39
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         }
46
47         if (current->mm != swap_token_mm) {
48                 if (current_interval < current->mm->last_interval)
49                         current->mm->token_priority++;
50                 else {
51                         current->mm->token_priority--;
52                         if (unlikely(current->mm->token_priority < 0))
53                                 current->mm->token_priority = 0;
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;
59                         swap_token_mm = current->mm;
60                 }
61         } else {
62                 /* Token holder came in again! */
63                 current->mm->token_priority += 2;
64         }
65
66 out:
67         current->mm->faultstamp = global_faults;
68         current->mm->last_interval = current_interval;
69         spin_unlock(&swap_token_lock);
70 return;
71 }
72
73 /* Called on process exit. */
74 void __put_swap_token(struct mm_struct *mm)
75 {
76         spin_lock(&swap_token_lock);
77         if (likely(mm == swap_token_mm))
78                 swap_token_mm = NULL;
79         spin_unlock(&swap_token_lock);
80 }