# Các thuật toán thay trang

> Nguồn: https://tiennhm.io.vn/docs/operating-system/page-replacement-algorithms
> Giới thiệu về các thuật toán thay trang (page replacement algorithms) trong hệ điều hành.

## Giới thiệu

Trong bài viết này, mình sẽ giới thiệu các thuật toán thay trang (page replacement algorithms) trong hệ điều hành. Các thuật toán này được sử dụng để thay thế các trang (page) trong bộ nhớ ảo (virtual memory) khi bộ nhớ đầy.

## Các thuật toán thay trang

### FIFO

Thuật toán FIFO (First In First Out) sẽ thay thế trang đầu tiên được đưa vào bộ nhớ ảo. Thuật toán này dễ hiểu và dễ cài đặt, nhưng nó không phải là thuật toán tối ưu.

### Optimal

Thuật toán Optimal sẽ thay thế trang mà sẽ không được sử dụng trong tương lai gần nhất. Thuật toán này là thuật toán tối ưu nhất, nhưng nó không thể cài đặt được.

### LRU

Thuật toán LRU (Least Recently Used) sẽ thay thế trang mà được sử dụng lâu nhất. Thuật toán này là thuật toán tối ưu nhất có thể cài đặt được.

#### LRU Stack

Thuật toán LRU Stack sẽ thay thế trang mà được sử dụng lâu nhất. Thuật toán này là thuật toán tối ưu nhất có thể cài đặt được.

#### LRU Counter

Thuật toán LRU Counter sẽ thay thế trang mà được sử dụng lâu nhất. Thuật toán này là thuật toán tối ưu nhất có thể cài đặt được.

### Clock

Thuật toán Clock sẽ thay thế trang mà được sử dụng lâu nhất. Thuật toán này không phải là thuật toán tối ưu, nhưng nó có thể cài đặt được.

Khi cần chọn trang nạn nhân, kim quay vòng qua các khung và xét bit tham chiếu của từng khung (bit bật lên 1 mỗi khi trang được truy cập):

```mermaid
flowchart TD
    F["Page fault, không còn khung trống"] --> C{"Bit tham chiếu của khung tại kim = 1?"}
    C -->|"Có"| R["Xoá bit về 0 (cho thêm một cơ hội), kim sang khung kế"]
    R --> C
    C -->|"Không"| V["Thay trang tại kim bằng trang mới, kim sang khung kế"]
```

## Tổng kết

Trong bài viết này, mình đã giới thiệu các thuật toán thay trang trong hệ điều hành. Hy vọng bài viết này sẽ giúp ích cho các bạn.

> **Info: Bên cạnh các thuật toán trên, còn có các thuật toán khác như: MFU, LFU, Second Chance, Enhanced Second Chance, NRU, FIFO Approximation, LRU Approximation, Random, ... Các bạn có thể tìm hiểu thêm về các thuật toán này.**
>
>
> **Tip: Luyện tập**
>
> Nắm lý thuyết rồi thì kiểm tra lại bằng [trắc nghiệm bộ nhớ ảo và thay trang](./05-quiz/07.virtual-memory.mdx): đủ bài tính FIFO, LRU, Optimal và CLOCK trên **cùng một chuỗi tham chiếu** để so sánh trực tiếp, kèm bảng khung trang từng bước và lời giải cho nghịch lý Belady.
>
> Hai phần nền nằm dưới thuật toán thay trang: [trắc nghiệm phân trang và TLB](./05-quiz/06.paging.mdx) (bảng trang đa cấp, thời gian truy cập hiệu quả) và [trắc nghiệm quản lý bộ nhớ](./05-quiz/05.memory-management.mdx) (MMU, Best-Fit, swap space).
> **Tip: Để xem thêm các video khác, các bạn có thể truy cập vào [kênh Youtube](https://www.youtube.com/TienNguyen09) của mình.**
>
>