BỘ NHỚ ẢO

Máy tính có thể giải quyết nhiều bộ nhớ hơn dung lượng vật lý được cài đặt trên hệ thống. Bộ nhớ bổ sung này được gọi là bộ nhớ ảo và nó là một phần của đĩa cứng được thiết lập để mô phỏng RAM của máy tính.

Ưu điểm chính có thể nhìn thấy của lược đồ này là các chương trình có thể lớn hơn bộ nhớ vật lý. Bộ nhớ ảo phục vụ hai mục đích. Đầu tiên, nó cho phép chúng ta mở rộng việc sử dụng bộ nhớ vật lý bằng cách sử dụng đĩa. Thứ hai, nó cho phép chúng ta bảo vệ bộ nhớ, bởi vì mỗi địa chỉ ảo được chuyển đổi sang một địa chỉ vật lý.

Các lợi ích của bộ nhớ ảo:

• Chỉ 1 phần cần thiết của chương trình nằm trong bộ nhớ để thực thi

• Do đó, không gian địa chỉ logic có thể lớn hơn nhiều so với không gian địa chỉ vật lý

• Cho phép một số tiến trình chia sẻ không gian địa chỉ

• Cho phép tạo tiến trình hiệu quả hơn

• Nhiều chương trình chạy đồng thời

• Cần ít I/O hơn để tải hoặc hoán đổi các tiến trình

Bộ vi xử lý hiện đại dành cho mục đích đa dụng, đơn vị quản lý bộ nhớ (Memory Management Unit - MMU), được tích hợp sẵn trong phần cứng. Công việc của MMU là dịch các địa chỉ ảo thành địa chỉ vật lý. Dưới đây là một ví dụ cơ bản:

Bộ nhớ ảo thường được thực hiện bằng cách phân trang theo yêu cầu. Nó cũng có thể được thực hiện trong một hệ thống phân đoạn. Phân đoạn theo yêu cầu cũng có thể được sử dụng để cung cấp bộ nhớ ảo.

Phân trang theo yêu cầu

Hệ thống phân trang theo yêu cầu khá giống với hệ thống phân trang có hoán đổi trong đó các tiến trình nằm trong bộ nhớ phụ và các trang chỉ được nạp theo yêu cầu chứ không phải nạp trước. Khi xảy ra chuyển ngữ cảnh, hệ điều hành không sao chép bất kỳ trang nào của chương trình cũ ra đĩa hoặc bất kỳ trang nào của chương trình mới vào bộ nhớ chính, thay vào đó, hệ điều hành chỉ bắt đầu thực hiện chương trình mới sau khi nạp trang đầu tiên và tìm nạp các trang của chương trình khi chúng được tham chiếu.

I

Trong khi thực thi một chương trình, nếu chương trình tham chiếu đến một trang không có sẵn trong bộ nhớ chính vì nó đã bị hoán đổi cách đây ít lâu, bộ xử lý sẽ coi tham chiếu bộ nhớ không hợp lệ này là lỗi trang và chuyển quyền điều khiển từ chương trình sang hệ điều hành yêu cầu trang trở lại bộ nhớ.

Ưu điểm của phân trang theo yêu cầu

• Bộ nhớ ảo lớn.

• Sử dụng bộ nhớ hiệu quả hơn.

• Không có giới hạn về mức độ đa chương trình.

Nhược điểm của phân trang theo yêu cầu: Số lượng bảng và lượng chi phí của bộ xử lý để xử lý các ngắt trang lớn hơn so với trường hợp của các kỹ thuật quản lý phân trang đơn giản.

Thuật toán thay thế trang

Các thuật toán thay thế trang là các kỹ thuật Hệ điều hành sử dụng quyết định trang bộ nhớ nào sẽ hoán đổi, ghi vào đĩa khi một trang bộ nhớ cần được cấp phát. Việc phân trang xảy ra bất cứ khi nào xảy ra lỗi trang vì lý do là các trang không có sẵn hoặc số lượng trang trống thấp hơn số trang được yêu cầu.

Khi trang được chọn để thay thế và được phân trang, được tham chiếu lại, nó phải đọc từ đĩa và điều này yêu cầu hoàn thành I/O. Quá trình này quyết định chất lượng của thuật toán thay thế trang: thời gian chờ trang càng ít thì thuật toán càng tốt.

Thuật toán thay thế trang xem xét thông tin hạn chế về việc truy cập các trang do phần cứng cung cấp và cố gắng chọn trang nào nên được thay thế để giảm thiểu tổng số trang bị bỏ lỡ, đồng thời cân bằng nó với chi phí lưu trữ chính và thời gian xử lý của thuật toán chính nó. Có nhiều thuật toán thay thế trang khác nhau. Các thuật toán thường được đánh giá bằng cách chạy nó trên một chuỗi tham chiếu bộ nhớ cụ thể và tính toán số lỗi trang.

Chuỗi tham chiếu

Chuỗi tham chiếu bộ nhớ được gọi tắt là chuỗi tham chiếu. Các chuỗi tham chiếu được tạo ra một cách giả lập hoặc bằng cách theo vết một hệ thống nhất định và ghi lại địa chỉ của mỗi tham chiếu bộ nhớ. Lựa chọn thứ hai tạo ra một số lượng lớn dữ liệu, trong đó chúng ta lưu ý một số điểm:

• Đối với một kích thước trang nhất định, chúng ta chỉ cần xem xét số trang, không phải toàn bộ địa chỉ.

• Nếu chúng ta có tham chiếu đến trang p, thì bất kỳ tham chiếu nào ngay sau đó đến trang p sẽ không bao giờ gây ra lỗi trang. Trang p sẽ nằm trong bộ nhớ sau lần tham chiếu đầu tiên; các tham chiếu ngay sau đó sẽ không bị lỗi.

• Ví dụ: hãy xem xét chuỗi địa chỉ sau - 123,215,600,1234,76,96

• Nếu kích thước trang là 100, thì chuỗi tham chiếu là 1,2,6,12,0,0

Thuật toán thay thế trang FIFO

FIFO còn được gọi là First In First Out là một trong những Thuật toán thay thế trang trong quản lý bộ nhớ ảo của hệ điều hành. Thuật toán này được sử dụng trong trường hợp hệ điều hành thay thế một trang hiện có với sự trợ giúp của bộ nhớ bằng cách đưa một trang mới từ bộ nhớ phụ.

FIFO là thuật toán đơn giản nhất trong số tất cả các thuật toán chịu trách nhiệm duy trì tất cả các trang trong hàng đợi cho một hệ điều hành và cũng theo dõi tất cả các trang trong hàng đợi.

Các trang cũ hơn được giữ ở phía trước và những trang mới hơn được giữ ở cuối hàng đợi. Các trang ở phía trước sẽ bị xóa trước và các trang được yêu cầu sẽ được thêm vào.

Ví dụ minh họa thuật toán FIFO

Xem xét một chuỗi tham chiếu như sau:

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

Giả sử dùng 3 khung trong việc cấp phát bộ nhớ. Tìm số lỗi trang theo giải thuật thay thế trang FIFO?

Sơ đồ minh họa thuật toán như sau: Trang cũ nhất (nạp vào khung trước) sẽ là trang bị thay thế

Phân tích hoạt động của FIFO:

- Ban đầu, cả 3 khung đều trống nên 3 trang 7, 0, 1 đầu tiên được phân bổ vào các khung trống. Vì vậy, số lỗi trang là 3.

- Tiếp theo là trang 2 đến, nó không có trong bộ nhớ vì vậy trang cũ nhất nằm trong bộ nhớ là trang 7 bị thay thế. Lỗi trang = 1

- Kế tiếp là trang 0 đến, nhưng 0 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Tiếp theo là trang 3 đến, nó không có trong bộ nhớ vì vậy trang cũ nhất nằm trong bộ nhớ là trang 0 bị thay thế. Lỗi trang = 1.

- Tiếp theo là trang 0 đến, nó không có trong bộ nhớ vì vậy trang cũ nhất nằm trong bộ nhớ là trang 1 bị thay thế. Lỗi trang = 1.

- Tiếp theo là trang 4 đến, nó không có trong bộ nhớ vì vậy trang cũ nhất nằm trong bộ nhớ là trang 2 bị thay thế. Lỗi trang = 1.

- Tiếp theo là trang 2 đến, nó không có trong bộ nhớ vì vậy trang cũ nhất nằm trong bộ nhớ là trang 3 bị thay thế. Lỗi trang = 1.

- Tiếp theo là trang 3 đến, nó không có trong bộ nhớ vì vậy trang cũ nhất nằm trong bộ nhớ là trang 0 bị thay thế. Lỗi trang = 1.

- Tiếp theo là trang 0 đến, nó không có trong bộ nhớ vì vậy trang cũ nhất nằm trong bộ nhớ là trang 4 bị thay thế. Lỗi trang = 1.

- Kế tiếp là trang 3 đến, nhưng 3 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Kế tiếp là trang 2 đến, nhưng 2 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Tiếp theo là trang 1 đến, nó không có trong bộ nhớ vì vậy trang cũ nhất nằm trong bộ nhớ là trang 2 bị thay thế. Lỗi trang = 1.

- Tiếp theo là trang 2 đến, nó không có trong bộ nhớ vì vậy trang cũ nhất nằm trong bộ nhớ là trang 3 bị thay thế. Lỗi trang = 1.

- Kế tiếp là trang 0 đến, nhưng 0 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Kế tiếp là trang 1 đến, nhưng 1 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Tiếp theo là trang 7 đến, nó không có trong bộ nhớ vì vậy trang cũ nhất nằm trong bộ nhớ là trang 0 bị thay thế. Lỗi trang = 1.

- Tiếp theo là trang 0 đến, nó không có trong bộ nhớ vì vậy trang cũ nhất nằm trong bộ nhớ là trang 1 bị thay thế. Lỗi trang = 1.

- Cuối cùng là trang 1 đến, nó không có trong bộ nhớ vì vậy trang cũ nhất nằm trong bộ nhớ là trang 2 bị thay thế. Lỗi trang = 1.

Kết thúc chuỗi tham chiếu. Tổng số lỗi trang là 15.

Chương trình C minh họa giải thuật thay thế trang FIFO

#include <stdio.h>
int main()
{
    int chuoi_tham_chieu[50], loi_trang = 0, m, n;
    int trang_da_co, so_trang, so_khung;
    printf("\nNhập số trang:\t");
    scanf("%d", &so_trang);
    printf("\nNhập các giá trị của chuỗi tham chiếu:\n");
    for( m = 0; m < so_trang; m++)
    {
        printf("Giá trị thứ. [%d]:\t", m + 1);
        scanf("%d", &chuoi_tham_chieu[m]);
    }
    printf("\nNhập số khung:\t");
    {
        scanf("%d", &so_khung);
    }
    
    int tam[so_khung];
    for(m = 0; m < so_khung; m++)
    {
        tam[m] = -1;
    }
    for(m = 0; m < so_trang; m++)
    {
        trang_da_co = 0; //biến kiểm xem trang đã có trong khung hay chưa, khi có s sẽ thay đổi bằng 1
        for(n = 0; n < so_khung; n++)
        {
            if(chuoi_tham_chieu[m] == tam[n])
                {
                    trang_da_co++;
                    loi_trang--;
                }
        }     
        loi_trang++;
        
        // trường hợp đầu khi khung còn trống
        if((loi_trang <= so_khung) && (trang_da_co == 0)) 
        {
            tam[m] = chuoi_tham_chieu[m];
        }   
        // trường hợp khung đã hết phải thay thế trang
        else if(trang_da_co == 0)
        {
            tam[(loi_trang - 1) % so_khung] = chuoi_tham_chieu[m]; //biểu thức (loi_trang - 1) % so_khung: xác định trang cũ nhất để thay thế
        }
        printf("\n");
    for(n = 0; n < so_khung; n++)
       {     
         printf("%d\t", tam[n]);
       }
} 

printf("\nTổng số lỗi trang:\t%d\n", loi_trang);
return 0;
}

Kết quả chạy chương trình trên hệ điều hành CentOS, biên dịch bằng GCC

Thuật toán thay thế trang Optimal (OPT)

Trong thuật toán này, trang bị thay thế là trang trang sẽ không được sử dụng trong thời gian dài nhất (trang ở tương lai).

Cụ thể là, khi nhìn sang bên phải của chuỗi tham chiếu đã cho tính từ trang đang xét, chúng ta chọn trang đang nằm trong bộ nhớ mà xa nhất so với trang đang xét để thay thế.

Ví dụ minh họa thuật toán OPT

Xem xét một chuỗi tham chiếu như sau:

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

Giả sử dùng 3 khung trong việc cấp phát bộ nhớ. Tìm số lỗi trang theo giải thuật thay thế trang OPT?

Sơ đồ minh họa thuật toán như sau:

Phân tích hoạt động của OPT:

- Ban đầu, cả 3 khung đều trống nên 3 trang 7, 0, 1 đầu tiên được phân bổ vào các khung trống. Vì vậy, số lỗi trang là 3.

- Tiếp theo là trang 2 đến, nó không có trong bộ nhớ vì vậy trang tương lai xa nhất là trang 7 bị thay thế. Lỗi trang = 1

- Kế tiếp là trang 0 đến, nhưng 0 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Tiếp theo là trang 3 đến, nó không có trong bộ nhớ vì vậy trang tương lai xa nhất là trang 1 bị thay thế. Lỗi trang = 1

- Kế tiếp là trang 0 đến, nhưng 0 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Tiếp theo là trang 4 đến, nó không có trong bộ nhớ vì vậy trang tương lai xa nhất là trang 0 bị thay thế. Lỗi trang = 1.

- Kế tiếp là trang 2 đến, nhưng 2 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Kế tiếp là trang 3 đến, nhưng 3 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Tiếp theo là trang 0 đến, nó không có trong bộ nhớ vì vậy trang tương lai xa nhất là trang 4 bị thay thế. Lỗi trang = 1.

- Kế tiếp là trang 3 đến, nhưng 3 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Kế tiếp là trang 2 đến, nhưng 2 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Tiếp theo là trang 1 đến, nó không có trong bộ nhớ vì vậy trang tương lai xa nhất là trang 3 bị thay thế. Lỗi trang = 1.

- Kế tiếp là trang 2 đến, nhưng 2 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Kế tiếp là trang 0 đến, nhưng 0 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Kế tiếp là trang 1 đến, nhưng 1 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Tiếp theo là trang 7 đến, nó không có trong bộ nhớ vì vậy trang tương lai xa nhất là trang 2 bị thay thế. Lỗi trang = 1.

- Kế tiếp là trang 0 đến, nhưng 0 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Cuối cùng là trang 1 đến, nhưng 1 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

Kết thúc chuỗi tham chiếu. Tổng số lỗi trang là 9.

Chương trình C minh họa giải thuật thay thế trang OPT

#include<stdio.h>
 
int main()
{
      int chuoi_tham_chieu[50], khung[50], khoang_cach_trang_tuong_lai[50];
      int so_trang, so_khung, loi_trang = 0;
      int m, n, tam; //m: biến kiểm soát trang; n: kiểm soát khung; tam: biến tạm;
      int trang_da_co, tim_thay; //trang_da_co: biến kiểm tra trang đã có trong khung chưa; tim_thay: biến kiểm soát đã tìm thấy khung hay chưa
      int vitri, khoang_cach_trang_tuong_lai_xa_nhat;
      int khung_trong_cuoi_cung = -1; // biến khung trống cuối cùng
      
      printf("\nNhập số khung:\t");
      scanf("%d", &so_khung);
      printf("\nNhập số trang:\t");
      scanf("%d", &so_trang);
      printf("\nNhập các giá trị của chuỗi tham chiếu\n");
      for(m = 0; m < so_trang; m++)
      { 
            printf("Giá trị tham chiếu.[%d]:\t", m + 1);
            scanf("%d", &chuoi_tham_chieu[m]);
      }
      
      //Vòng lặp gán -1 vào các khung trống
      for(m = 0; m < so_khung; m++) 
      {
            khung[m] = -1;
      }
      
      //Vòng lặp duyệt qua từng trang của chuỗi tham chiếu
      for(m = 0; m < so_trang; m++)
      {
            trang_da_co = 0;    //trang chưa có trong khung
            for(n = 0; n < so_khung; n++)   //duyệt xem xét từng khung
            {
                  if(khung[n] == chuoi_tham_chieu[m])
                  {
                        trang_da_co = 1; // Trang đã có trong khung rồi
                        printf("\t");
                        break;
                  }
            }
            if(trang_da_co == 0) // Nếu trang chưa có trong khung
            {
                  if (khung_trong_cuoi_cung == so_khung - 1)    //Nếu không còn khung trống nào
                  {
                        for(n = 0; n < so_khung; n++)   //duyệt qua từng khung
                        {      
                              for(tam = m + 1; tam < so_trang; tam++)   //duyệt các trang trong chuỗi tham chiếu, bắt đầu từ vị trí sau trang đang xét
                              {      
                                    khoang_cach_trang_tuong_lai[n] = 0;   // gán khoảng cách của các trang đang nằm trong khung bằng 0
                                    if (khung[n] == chuoi_tham_chieu[tam])  //nếu tìm thấy trang trong chuỗi tham chiếu bằng với trang đang nằm trong khung
                                    {      
                                          khoang_cach_trang_tuong_lai[n] = tam - m;   //tính khoảng cách của trang tìm thấy so với trang đang xét
                                          break;
                                    }
                              }
                        }
                        tim_thay = 0;
                        for(n = 0; n < so_khung; n++)   //duyệt qua từng khung
                        {
                              if(khoang_cach_trang_tuong_lai[n] == 0)
                              {                 
                                    vitri = n;
                                    tim_thay = 1;
                                    break;
                              }            
                        }
                  }
                  else  //Ngược lại nếu vẫn còn khung trống
                  {
                        vitri = ++khung_trong_cuoi_cung; //thay đổi vị trí của khung trống cuối cùng lên 1
                        tim_thay = 1;   //đã tìm thấy khung
                  }
                  if(tim_thay == 0) //nếu chưa tìm thấy khung
                  {
                        khoang_cach_trang_tuong_lai_xa_nhat = khoang_cach_trang_tuong_lai[0];
                        vitri = 0;
                        for(n = 1; n < so_khung; n++)   // duyệt qua từng khung
                        {
                              if(khoang_cach_trang_tuong_lai_xa_nhat < khoang_cach_trang_tuong_lai[n])
                              {
                                    khoang_cach_trang_tuong_lai_xa_nhat = khoang_cach_trang_tuong_lai[n];   //tìm khoảng cách xa nhất
                                    vitri = n;
                              }
                        }
                   }     
                   khung[vitri] = chuoi_tham_chieu[m]; //thay thế trang đang xét vào khung tìm thấy
                   printf("LỖI\t");
                   loi_trang++; //tăng số lỗi trang lên 1
            }
            
            //duyệt qua từng khung và in giá trị của trang tương ứng trong khung ra màn hình
            for(n = 0; n < so_khung; n++)
            {
                  if(khung[n] != -1) 
                  {
                        printf("%d\t", khung[n]);
                  }
            }
            printf("\n");   //xuống dòng để in tiếp cho lần duyệt mới
      }
      printf("\nTổng số lỗi trang:\t%d\n", loi_trang);
      return 0;
}

Kết quả chạy chương trình trên hệ điều hành CentOS, biên dịch bằng GCC

Thuật toán thay thế trang Least Recently Used (LRU)

Trong thuật toán này, trang bị thay thế là trang trang đã không được sử dụng trong thời gian dài nhất (trang trong quá khứ).

Cụ thể là, khi nhìn sang bên trái của chuỗi tham chiếu đã cho tính từ trang đang xét, chúng ta chọn trang đang nằm trong bộ nhớ mà xa nhất so với trang đang xét để thay thế.

Ví dụ minh họa thuật toán LRU

Xem xét một chuỗi tham chiếu như sau:

7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

Giả sử dùng 3 khung trong việc cấp phát bộ nhớ. Tìm số lỗi trang theo giải thuật thay thế trang LRU?

Sơ đồ minh họa thuật toán như sau:

9

Phân tích hoạt động của LRU:

- Ban đầu, cả 3 khung đều trống nên 3 trang 7, 0, 1 đầu tiên được phân bổ vào các khung trống. Vì vậy, số lỗi trang là 3.

- Tiếp theo là trang 2 đến, nó không có trong bộ nhớ vì vậy trang quá khứ xa nhất là trang 7 bị thay thế. Lỗi trang = 1

- Kế tiếp là trang 0 đến, nhưng 0 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Tiếp theo là trang 3 đến, nó không có trong bộ nhớ vì vậy trang quá khứ xa nhất là trang 1 bị thay thế. Lỗi trang = 1.

- Kế tiếp là trang 0 đến, nhưng 0 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Tiếp theo là trang 4 đến, nó không có trong bộ nhớ vì vậy trang quá khứ xa nhất là trang 2 bị thay thế. Lỗi trang = 1.

- Tiếp theo là trang 2 đến, nó không có trong bộ nhớ vì vậy trang quá khứ xa nhất là trang 3 bị thay thế. Lỗi trang = 1.

- Tiếp theo là trang 3 đến, nó không có trong bộ nhớ vì vậy trang quá khứ xa nhất là trang 0 bị thay thế. Lỗi trang = 1.

- Tiếp theo là trang 0 đến, nó không có trong bộ nhớ vì vậy trang quá khứ xa nhất là trang 4 bị thay thế. Lỗi trang = 1.

- Kế tiếp là trang 3 đến, nhưng 3 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Kế tiếp là trang 2 đến, nhưng 2 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Tiếp theo là trang 1 đến, nó không có trong bộ nhớ vì vậy trang quá khứ xa nhất là trang 0 bị thay thế. Lỗi trang = 1.

- Kế tiếp là trang 2 đến, nhưng 2 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Tiếp theo là trang 0 đến, nó không có trong bộ nhớ vì vậy trang quá khứ xa nhất là trang 3 bị thay thế. Lỗi trang = 1.

- Kế tiếp là trang 1 đến, nhưng 1 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Tiếp theo là trang 7 đến, nó không có trong bộ nhớ vì vậy trang quá khứ xa nhất là trang 2 bị thay thế. Lỗi trang = 1.

- Kế tiếp là trang 0 đến, nhưng 0 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

- Cuối cùng là trang 1 đến, nhưng 1 đã có trong bộ nhớ, vì vậy lỗi trang = 0.

Kết thúc chuỗi tham chiếu. Tổng số lỗi trang là 12.

Chương trình C minh họa giải thuật thay thế trang LRU

#include<stdio.h>
 
int main()
{
      int khung[50], tam[50], trang[50];
      int so_trang, m, n, vitri, k, l, so_khung;
      int a = 0, b = 0, loi_trang = 0;
      printf("\nNhập số khung:\t");
      scanf("%d", &so_khung);
      for(m = 0; m < so_khung; m++)
      {
            khung[m] = -1;
      }
      printf("Nhập số trang:\t");
      scanf("%d", &so_trang);
      printf("Nhập các giá trị cho chuỗi tham chiếu:\n");
      for(m = 0; m < so_trang; m++)
      {
            printf("Giá trị tham chiếu.[%d]:\t", m + 1);
            scanf("%d", &trang[m]);
      }
      for(n = 0; n < so_trang; n++)
      {
            a = 0, b = 0;
            for(m = 0; m < so_khung; m++)
            {
                  if(khung[m] == trang[n])
                  {
                        a = 1;
                        b = 1;
                        break;
                  }
            }
            if(a == 0)
            {
                  for(m = 0; m < so_khung; m++)
                  {
                        if(khung[m] == -1)
                        {
                              khung[m] = trang[n];
                              b = 1;
                              loi_trang++;
                              break;
                        }
                  }
            }
            if(b == 0)
            {
                  for(m = 0; m < so_khung; m++)
                  {
                        tam[m] = 0;
                  }
                  for(k = n - 1, l = 1; l <= so_khung - 1; l++, k--)
                  {
                        for(m = 0; m < so_khung; m++)
                        {
                              if(khung[m] == trang[k])
                              {
                                    tam[m] = 1;
                              }
                        }
                  }
                  for(m = 0; m < so_khung; m++)
                  {
                        if(tam[m] == 0)
                        vitri = m;
                  }
                  khung[vitri] = trang[n];
                  loi_trang++;
            }
            printf("\n");
            for(m = 0; m < so_khung; m++)
            {
                  printf("%d\t", khung[m]);
            }
      }
      printf("\nTổng số lỗi trang:\t%d\n", loi_trang);
      return 0;
}

Kết quả chạy chương trình trên hệ điều hành CentOS, biên dịch bằng GCC