Posted By

Feb30th1712 on 09/03/08


Tagged


Versions (?)

second chance algorithm


 / Published in: C
 

Second chance algorithm a.k.a clock algorithm implementation.

  1. /* filename: sca.c
  2. * topic: page table replacement
  3. * algorithm: second chance algorithm (clock algorithm)
  4. * language: ansi c
  5. * version: 1.0.0
  6. * status: beta
  7. * programmer: Lyfia C. Vaex
  8. * contact: http://en.wikipedia.org/wiki/User:Feb30th1712
  9. * license: GNU General Public License 2
  10. *
  11. * release date: Jan 26, 2006
  12. * last updated: n/a
  13. * update by: n/a
  14. *
  15. * development kit: Cgywin, Vim and GCC
  16. *
  17. * known issues:
  18. * 1. used Hungariun notation for variable naming
  19. */
  20. #include
  21. #define FN 4 //frame number
  22. #define RB 0 //reference bit
  23. #define PN 1 //page number
  24. int main(void)
  25. {
  26. //hp = hand pointer, in = input, pt = page table
  27. int rgPT[FN][2] = {0}, nHP = 3, nIn, iPT;
  28.  
  29. printf("Enter: ");
  30. while ( scanf("%d", &nIn) )
  31. {
  32. getchar();
  33.  
  34. //search page table
  35. for (iPT = 0; rgPT[iPT][PN] != nIn && iPT < FN; iPT++);
  36.  
  37. //failed to retrieve
  38. if (rgPT[iPT][PN] != nIn)
  39. {
  40. //search for a victim
  41. do {
  42. nHP = (nHP + 1) % FN;
  43. } while ( !( rgPT[nHP][RB] == 1 ? rgPT[nHP][RB] = 0 : 1 ) );
  44. //update the page table
  45. rgPT[nHP][RB] = 1;
  46. rgPT[nHP][PN] = nIn;
  47. }
  48.  
  49. //retrieved
  50. else
  51. rgPT[iPT][RB] = 1;
  52.  
  53. //show page table state
  54. puts("page table:");
  55. for (iPT = 0; iPT < FN; iPT++)
  56. printf("%s %d, %d.\n", iPT == (nHP + 1) % 4 ? ">": " ", rgPT[iPT][RB], rgPT[iPT][PN]);
  57. putchar('\n');
  58.  
  59. printf("Enter: ");
  60. }
  61. puts("May the Roses bloom upon your Cross. ");
  62.  
  63. return 0;
  64. }

Report this snippet  

You need to login to post a comment.