Thuật toán FIFO (First In First Out) là gì? Giải thích dễ hiểu kèm demo trực quan

Dù thuật toán này không phải tối ưu nhất cho mọi trường hợp, nhưng nó lại rất phù hợp khi bạn muốn một giải pháp đơn giản, dễ code, ít sai sót và hiệu năng ổn định. Bài viết này giải thích cách hoạt động của FIFO và cung cấp demo trực quan bằng JavaScript + UIkit để quan sát từng bước.

FIFO giải bài toán gì?

Vấn đề cơ bản: cache có kích thước cố định và không thể chứa mọi dữ liệu.

Bài toán của FIFO:

• Cache đầy → phải loại bỏ 1 phần tử.
• Phần tử bị loại sẽ là phần tử đã vào cache lâu nhất.

Cách hoạt động rất giống một hàng chờ thông thường (queue): phần tử đứng đầu hàng → bị đưa ra khỏi hàng khi có phần tử mới vào.

Ý tưởng chính của thuật toán FIFO

1. Cache được quản lý như một hàng đợi (queue).
2. Khi truy cập dữ liệu:
   • Nếu dữ liệu đã có trong cache → không làm gì.
   • Nếu chưa có:
     • Nếu cache còn chỗ → thêm vào cuối hàng.
     • Nếu cache đầy → loại phần tử ở đầu hàng → thêm phần tử mới vào cuối hàng.

Thuật toán không quan tâm:

• Dữ liệu có được truy cập gần đây hay không.
• Tần suất sử dụng nhiều hay ít.

→ Chính vì thế FIFO đơn giản nhưng có hạn chế.

Ví dụ minh họa

Giả sử cache có kích thước 3.

Truy cập lần lượt: A → B → C → D → B → E

Diễn biến:

• A → thêm A → [A]
• B → thêm B → [A, B]
• C → thêm C → [A, B, C]
• D → cache đầy → loại A → thêm D → [B, C, D]
• B → đã có → giữ nguyên
• E → cache đầy → loại B → thêm E → [C, D, E]

Như vậy, FIFO luôn loại phần tử cũ nhất.

Demo FIFO Cache bằng JavaScript (UIkit)

Demo dưới đây mô phỏng cache FIFO dung lượng 4 phần tử:

• Nhập key để truy cập.
• Nếu cache đầy → item cũ nhất bị đẩy ra.
• UI highlight item bị loại bỏ & item được thêm vào.
• Log từng bước để bạn thấy rõ thuật toán hoạt động.

Phân tích code thuật toán FIFO

1. Khởi tạo cache và kích thước

var FIFO_CACHE_SIZE = 4;
var fifoCache = [];

2. Hàm ghi log

function fifoLog(msg) {
    var p = document.createElement("p");
    p.innerHTML = msg;
    fifoLogBox.appendChild(p);
    fifoLogBox.scrollTop = fifoLogBox.scrollHeight;
}

3. Thuật toán xử lý mỗi lần truy cập

function fifoAccess(key) {
    if (fifoCache.includes(key)) {
        fifoLog("Key <strong>" + key + "</strong> đã có trong cache → không thay đổi.");
        return;
    }

    // Nếu cache chưa đầy → thêm bình thường
    if (fifoCache.length < FIFO_CACHE_SIZE) {
        fifoCache.push(key);
        fifoLog("Thêm key <strong>" + key + "</strong> vào cache.");
    } else {
        // Cache đầy → loại phần tử đầu tiên
        var removed = fifoCache.shift();
        fifoLog("Cache đầy → loại phần tử cũ nhất: <strong>" + removed + "</strong>");

        fifoCache.push(key);
        fifoLog("Thêm key mới <strong>" + key + "</strong> vào cache.");
    }
}

4. Render cache trên UI

function fifoRender() {
    fifoCacheBox.innerHTML = "";
    fifoCache.forEach(function(item) {
        var div = document.createElement("div");
        div.className = "fifo-item";
        div.textContent = item;
        fifoCacheBox.appendChild(div);
    });
}

Khi nào nên dùng FIFO?

FIFO phù hợp khi:

• Hệ thống cần cấu trúc đơn giản, dễ dự đoán.
• Tài nguyên hạn chế, không muốn tốn thêm bộ nhớ cho LRU/LFU.
• Mẫu truy cập dữ liệu không quá phức tạp.

Ví dụ thực tế:

• Buffer đơn giản trong hệ nhúng.
• Hệ thống log hoặc queue message.
• Bộ nhớ tạm của các thiết bị IoT.

Tuy nhiên, trong phần lớn ứng dụng web và backend, LRU hoạt động tốt hơn FIFO.

Kết luận

FIFO là thuật toán cache cơ bản nhưng cực kỳ hữu ích để hiểu về cách bộ nhớ tạm hoạt động.
Thông qua demo trực quan bên trên, bạn có thể thấy rõ cách FIFO loại bỏ item cũ nhất và thêm item mới vào cache một cách tuần tự.

Sang bài tiếp theo của series, chúng ta sẽ đi vào thuật toán quan trọng nhất trong caching: LRU – Least Recently Used kèm theo demo UIkit cực trực quan.