Nhìn vào hình ta có thể thấy bộ đệm tròn là một cấu trúc dữ liệu có kích thước cố định và được kết nối end-to-end. Bộ đệm tròn rất tốt để sử dụng cho các luồng dữ liệu đệm trong đó dữ liệu được nhập trước xuất trước. Nhập trước xuất trước… điều này nghe giống như xếp hàng phải không?
Một chiếc nhẫn hiển thị, về mặt khái niệm, một bộ đệm tròn. Điều này cho thấy một cách trực quan rằng bộ đệm không có đầu cuối thực và nó có thể lặp xung quanh bộ đệm. Tuy nhiên, vì bộ nhớ không bao giờ được tạo ra một cách vật lý dưới dạng vòng, nên biểu diễn tuyến tính thường được sử dụng như được thực hiện bên dưới
Trong khoa học máy tính, bộ đệm vòng tròn, hàng đợi vòng tròn, bộ đệm tuần hoàn hoặc bộ đệm vòng là một cấu trúc dữ liệu sử dụng một bộ đệm có kích thước cố định duy nhất như thể nó được kết nối từ đầu đến cuối. Cấu trúc này dễ dàng cho phép đệm các luồng dữ liệu. Đã có những triển khai bộ đệm tròn sớm trong phần cứng
Tổng quan[sửa]
Bộ đệm tròn bàn phím 24 byte. Khi con trỏ ghi sắp chạm tới con trỏ đọc—do bộ vi xử lý không phản hồi—bộ đệm dừng ghi các lần nhấn phím. Trên một số máy tính sẽ phát ra tiếng bíp
Đầu tiên, bộ đệm tròn bắt đầu trống và có độ dài đã đặt. Trong sơ đồ bên dưới là bộ đệm 7 phần tử
Giả sử rằng 1 được viết ở giữa vùng đệm hình tròn [vị trí bắt đầu chính xác không quan trọng trong vùng đệm hình tròn]
Sau đó, giả sử rằng hai phần tử khác được thêm vào bộ đệm tròn - 2 & 3 - được đặt sau 1
Nếu hai phần tử bị loại bỏ, hai giá trị cũ nhất bên trong bộ đệm tròn sẽ bị loại bỏ. Bộ đệm tròn sử dụng logic FIFO [nhập trước, xuất trước]. Trong ví dụ này, 1 & 2 là những người đầu tiên vào bộ đệm tròn, chúng là những người đầu tiên bị xóa, để lại 3 bên trong bộ đệm
Nếu bộ đệm có 7 phần tử thì nó hoàn toàn đầy
Một thuộc tính của bộ đệm tròn là khi nó đầy và một lần ghi tiếp theo được thực hiện, thì nó bắt đầu ghi đè lên dữ liệu cũ nhất. Trong ví dụ hiện tại, hai phần tử khác — A và B — được thêm vào và chúng ghi đè lên phần tử 3 & 4
Ngoài ra, các thường trình quản lý bộ đệm có thể ngăn ghi đè dữ liệu và trả về lỗi hoặc đưa ra ngoại lệ. Việc dữ liệu có bị ghi đè hay không tùy thuộc vào ngữ nghĩa của các thủ tục bộ đệm hoặc ứng dụng sử dụng bộ đệm vòng
Cuối cùng, nếu hai phần tử hiện đã bị xóa thì phần tử sẽ được trả về không phải là 3 & 4 mà là 5 & 6 vì A & B đã ghi đè lên 3 & 4 tạo ra bộ đệm với
Thuộc tính hữu ích của bộ đệm tròn là nó không cần xáo trộn các phần tử xung quanh khi sử dụng một phần tử. [Nếu sử dụng bộ đệm không tròn thì cần phải dịch chuyển tất cả các phần tử khi một phần tử được sử dụng. ] Nói cách khác, bộ đệm tròn rất phù hợp làm bộ đệm FIFO [vào trước, ra trước] trong khi bộ đệm tiêu chuẩn, không tròn rất phù hợp làm bộ đệm LIFO [vào sau, ra trước]
Bộ đệm tròn tạo ra một chiến lược triển khai tốt cho hàng đợi có kích thước tối đa cố định. Nếu kích thước tối đa được chấp nhận cho một hàng đợi, thì bộ đệm tròn là một triển khai hoàn toàn lý tưởng; . Tuy nhiên, việc mở rộng bộ đệm tròn yêu cầu thay đổi bộ nhớ, điều này tương đối tốn kém. Đối với hàng đợi mở rộng tùy ý, thay vào đó có thể ưu tiên sử dụng phương pháp danh sách liên kết
Trong một số trường hợp, có thể sử dụng ghi đè bộ đệm tròn, e. g. trong đa phương tiện. Nếu bộ đệm được sử dụng làm bộ đệm bị chặn trong bài toán người tiêu dùng – nhà sản xuất thì có thể nhà sản xuất mong muốn điều đó [e. g. , một trình tạo âm thanh] để ghi đè lên dữ liệu cũ nếu người tiêu dùng [e. g. , card âm thanh] không thể theo kịp trong giây lát. Ngoài ra, họ thuật toán nén dữ liệu không mất dữ liệu LZ77 hoạt động dựa trên giả định rằng các chuỗi được thấy gần đây hơn trong luồng dữ liệu có nhiều khả năng xuất hiện sớm hơn trong luồng. Việc triển khai lưu trữ dữ liệu gần đây nhất trong bộ đệm tròn
Cơ chế đệm tròn[sửa]
Triển khai bộ đệm tròn trong phần cứng, bằng sáng chế Hoa Kỳ 3979733, hình 4
Bộ đệm tròn có thể được thực hiện bằng cách sử dụng một con trỏ và ba số nguyên
- bộ đệm bắt đầu trong bộ nhớ
- dung lượng bộ đệm [Chiều dài]
- ghi vào chỉ mục bộ đệm [kết thúc]
- đọc từ chỉ mục bộ đệm [bắt đầu]
Hình ảnh này hiển thị bộ đệm đầy một phần với Độ dài = 7
Hình ảnh này cho thấy một bộ đệm đầy đủ với bốn phần tử [số 1 đến 4] đã bị ghi đè
Ban đầu, các chỉ mục kết thúc và bắt đầu được đặt thành 0. Thao tác ghi bộ đệm tròn ghi một phần tử vào vị trí chỉ mục kết thúc và chỉ mục kết thúc được tăng lên vị trí bộ đệm tiếp theo. Hoạt động đọc bộ đệm tròn đọc một phần tử từ vị trí chỉ mục bắt đầu và chỉ mục bắt đầu được tăng lên vị trí bộ đệm tiếp theo
Các chỉ mục bắt đầu và kết thúc không đủ để cho biết trạng thái đầy hoặc trống của bộ đệm trong khi cũng sử dụng tất cả các vị trí bộ đệm, nhưng có thể nếu bộ đệm chỉ có kích thước sử dụng tối đa là Độ dài - 1. Trong trường hợp này, bộ đệm trống nếu chỉ số bắt đầu và kết thúc bằng nhau và đầy khi kích thước đang sử dụng là Độ dài - 1. Một giải pháp khác là có một số nguyên khác được tăng lên ở thao tác ghi và giảm xuống ở thao tác đọc. Sau đó, kiểm tra tính trống rỗng có nghĩa là số lượng kiểm tra bằng 0 và kiểm tra tính đầy đủ có nghĩa là số lượng kiểm tra bằng Độ dài
Mã nguồn sau đây là một triển khai C. Hàm put[] đặt một mục vào bộ đệm, hàm get[] lấy một mục từ bộ đệm
#define BUFLEN 3
int buf[BUFLEN]; /* array to be treated as circular buffer of BUFLEN integers */
int end = 0; /* write index */
int start = 0; /* read index */
void put[int item]
{
buf[end++] = item;
end %= BUFLEN;
}
int get[]
{
int item = buf[start++];
start %= BUFLEN;
return item;
}
Tối ưu hóa[sửa]
Việc triển khai bộ đệm vòng tròn có thể được tối ưu hóa bằng cách ánh xạ bộ đệm bên dưới tới hai vùng liền kề của bộ nhớ ảo. [disputed – ] [Đương nhiên, độ dài của bộ đệm bên dưới khi đó phải bằng bội số của kích thước trang của hệ thống. ] Khi đó, việc đọc và ghi vào bộ đệm vòng có thể được thực hiện với hiệu quả cao hơn bằng cách truy cập bộ nhớ trực tiếp; . Khi phần bù đọc được nâng cao vào vùng bộ nhớ ảo thứ hai, cả hai phần bù—đọc và ghi—đều bị giảm theo độ dài của bộ đệm bên dưới
Bộ đệm tròn phần tử có độ dài cố định và khối liền kề[sửa | sửa mã nguồn]
Có lẽ phiên bản phổ biến nhất của bộ đệm tròn sử dụng byte 8 bit làm phần tử
Một số triển khai của bộ đệm tròn sử dụng các phần tử có độ dài cố định lớn hơn byte 8 bit—số nguyên 16 bit cho bộ đệm âm thanh, tế bào ATM 53 byte cho bộ đệm viễn thông, v.v. Mỗi mục liền kề và có căn chỉnh dữ liệu chính xác, do đó phần mềm đọc và ghi các giá trị này có thể nhanh hơn phần mềm xử lý các giá trị không liền kề và không căn chỉnh
Bộ đệm bóng bàn có thể được coi là bộ đệm tròn rất chuyên dụng với chính xác hai phần tử có độ dài cố định lớn
Bộ đệm bip [bộ đệm hai bên] rất giống với bộ đệm tròn, ngoại trừ nó luôn trả về các khối liền kề có thể có độ dài thay đổi. Điều này cung cấp gần như tất cả các lợi thế về hiệu quả của bộ đệm tròn trong khi vẫn duy trì khả năng sử dụng bộ đệm trong các API chỉ chấp nhận các khối liền kề
Bộ đệm tròn nén có kích thước cố định sử dụng chiến lược lập chỉ mục thay thế dựa trên lý thuyết số cơ bản để duy trì biểu diễn nén có kích thước cố định của toàn bộ chuỗi dữ liệu