thrash.c 2.1 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980
  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. #include <linux/jiffies.h>
  20. #include <linux/mm.h>
  21. #include <linux/sched.h>
  22. #include <linux/swap.h>
  23. static DEFINE_SPINLOCK(swap_token_lock);
  24. struct mm_struct *swap_token_mm;
  25. static unsigned int global_faults;
  26. void grab_swap_token(void)
  27. {
  28. int current_interval;
  29. global_faults++;
  30. current_interval = global_faults - current->mm->faultstamp;
  31. if (!spin_trylock(&swap_token_lock))
  32. return;
  33. /* First come first served */
  34. if (swap_token_mm == NULL) {
  35. current->mm->token_priority = current->mm->token_priority + 2;
  36. swap_token_mm = current->mm;
  37. goto out;
  38. }
  39. if (current->mm != swap_token_mm) {
  40. if (current_interval < current->mm->last_interval)
  41. current->mm->token_priority++;
  42. else {
  43. current->mm->token_priority--;
  44. if (unlikely(current->mm->token_priority < 0))
  45. current->mm->token_priority = 0;
  46. }
  47. /* Check if we deserve the token */
  48. if (current->mm->token_priority >
  49. swap_token_mm->token_priority) {
  50. current->mm->token_priority += 2;
  51. swap_token_mm = current->mm;
  52. }
  53. } else {
  54. /* Token holder came in again! */
  55. current->mm->token_priority += 2;
  56. }
  57. out:
  58. current->mm->faultstamp = global_faults;
  59. current->mm->last_interval = current_interval;
  60. spin_unlock(&swap_token_lock);
  61. return;
  62. }
  63. /* Called on process exit. */
  64. void __put_swap_token(struct mm_struct *mm)
  65. {
  66. spin_lock(&swap_token_lock);
  67. if (likely(mm == swap_token_mm))
  68. swap_token_mm = NULL;
  69. spin_unlock(&swap_token_lock);
  70. }