blob: 9ef9071f99bcd7322b8e1f6808a477403b891211 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
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
Ashwin Chaugule7602bdf2006-12-06 20:31:57 -080010 *
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.
Linus Torvalds1da177e2005-04-16 15:20:36 -070018 */
Ashwin Chaugule7602bdf2006-12-06 20:31:57 -080019
Linus Torvalds1da177e2005-04-16 15:20:36 -070020#include <linux/jiffies.h>
21#include <linux/mm.h>
22#include <linux/sched.h>
23#include <linux/swap.h>
24
25static DEFINE_SPINLOCK(swap_token_lock);
Ashwin Chaugule7602bdf2006-12-06 20:31:57 -080026struct mm_struct *swap_token_mm;
Adrian Bunke3050052006-12-06 20:32:43 -080027static unsigned int global_faults;
Linus Torvalds1da177e2005-04-16 15:20:36 -070028
Linus Torvalds1da177e2005-04-16 15:20:36 -070029void grab_swap_token(void)
30{
Ashwin Chaugule7602bdf2006-12-06 20:31:57 -080031 int current_interval;
Linus Torvalds1da177e2005-04-16 15:20:36 -070032
Ashwin Chaugule7602bdf2006-12-06 20:31:57 -080033 global_faults++;
34
35 current_interval = global_faults - current->mm->faultstamp;
36
37 if (!spin_trylock(&swap_token_lock))
Linus Torvalds1da177e2005-04-16 15:20:36 -070038 return;
Ashwin Chaugule7602bdf2006-12-06 20:31:57 -080039
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;
Linus Torvalds1da177e2005-04-16 15:20:36 -070045 }
46
Ashwin Chaugule7602bdf2006-12-06 20:31:57 -080047 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;
Rik van Rielf7b7fd82005-11-28 13:44:07 -080054 }
Ashwin Chaugule7602bdf2006-12-06 20:31:57 -080055 /* Check if we deserve the token */
56 if (current->mm->token_priority >
57 swap_token_mm->token_priority) {
58 current->mm->token_priority += 2;
Linus Torvalds1da177e2005-04-16 15:20:36 -070059 swap_token_mm = current->mm;
60 }
Ashwin Chaugule7602bdf2006-12-06 20:31:57 -080061 } else {
62 /* Token holder came in again! */
63 current->mm->token_priority += 2;
Linus Torvalds1da177e2005-04-16 15:20:36 -070064 }
Ashwin Chaugule7602bdf2006-12-06 20:31:57 -080065
66out:
67 current->mm->faultstamp = global_faults;
68 current->mm->last_interval = current_interval;
69 spin_unlock(&swap_token_lock);
70return;
Linus Torvalds1da177e2005-04-16 15:20:36 -070071}
72
73/* Called on process exit. */
74void __put_swap_token(struct mm_struct *mm)
75{
76 spin_lock(&swap_token_lock);
Ashwin Chaugule7602bdf2006-12-06 20:31:57 -080077 if (likely(mm == swap_token_mm))
78 swap_token_mm = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -070079 spin_unlock(&swap_token_lock);
80}