FIFO trống, đầy và truyền đồng thời

Hàng đợi giữ thứ tự chấp nhận

FIFO chuyển giao phần tử được chấp nhận lâu nhất trước. Con trỏ đọc xác định phần tử lâu nhất, còn con trỏ ghi xác định vị trí lưu tiếp theo. Chỉ con trỏ bằng nhau không thể phân biệt trống với đầy, nên thiết kế này giữ bộ đếm số phần tử. Với độ sâu bốn, con trỏ cần hai bit nhưng bộ đếm cần ba bit để biểu diễn từ 0 đến 4. Lưu thẻ cùng dữ liệu.

FIFO có thanh ghi của chúng ta không cho dữ liệu đi xuyên khi hàng đợi trống. Output-valid là count>0 và pop là output-valid AND output-ready. Input-ready là count<depth OR pop, cho phép thay thế khi hàng đợi đầy đồng thời chuyển giao phần tử đầu. Push là input-valid AND input-ready. Count tiếp theo là count+push-pop. Hai phép gán riêng tăng và giảm count có thể xử lý sai truyền đồng thời; dùng một cập nhật kết hợp hoặc các trường hợp rõ ràng.

Hàng đợi trống không thể pop chỉ vì đích sẵn sàng. Đầu vào mới của nó chỉ truyền lần đầu tại cạnh tiếp theo. Hàng đợi đầy [A,B,C,D] đồng thời nhận A và chấp nhận E trở thành [B,C,D,E], vẫn đầy. Xác minh hành vi bộ nhớ bên dưới khi đọc và ghi cùng vị trí vật lý.

Độ sâu là lũy thừa hai quay vòng tự nhiên trong các bit con trỏ. Độ sâu ba cần chuyển rõ từ vị trí hai về 0. Kiểm tra riêng quay vòng, lấy phần tử cuối và thay thế khi đầy.

Hàng đợi trống độ sâu bốn chỉ hấp thụ bốn phần tử trong lúc đích dừng năm chu kỳ. Đầu vào thứ năm phải chờ. Nguồn không thể dừng cần nhiều dung lượng hơn hoặc chính sách mất dữ liệu được xác định. Không FIFO hữu hạn nào giải quyết việc nhận chậm hơn mãi mãi. Kiểm tra 0≤count≤depth, accepted-delivered=count và thứ tự thẻ; chỉ số đếm không thể phát hiện đổi thứ tự.