2011-10-22 35 views
13

Giả sử tôi có một đối tượng pool bộ nhớ với một hàm tạo một con trỏ tới một đoạn lớn bộ nhớ và kích thước N. Nếu tôi thực hiện nhiều phân bổ ngẫu nhiên và deallocations với các kích cỡ khác nhau, tôi có thể nhận được bộ nhớ ở trạng thái như vậy phân bổ một đối tượng M byte liền kề trong bộ nhớ mặc dù có thể có rất nhiều miễn phí! Đồng thời, tôi không thể thu gọn bộ nhớ vì điều đó sẽ gây ra một con trỏ lơ lửng trên người tiêu dùng. Làm thế nào để giải quyết phân mảnh trong trường hợp này?Xử lý phân mảnh trong vùng bộ nhớ?

+0

Bạn đang cố gắng triển khai hệ điều hành hoặc ít nhất là một phần của nó? Lý do duy nhất bộ nhớ hồ bơi được ưa thích hơn phân bổ bình thường là bởi vì giao dịch phân bổ bình thường với phân mảnh. – Dani

Trả lời

8

Tôi muốn thêm 2 xu chỉ vì không ai khác chỉ ra rằng từ mô tả của bạn, có vẻ như bạn đang triển khai một bộ phân bổ heap chuẩn (i.e những gì tất cả chúng ta đã sử dụng mỗi khi chúng ta gọi malloc() hoặc toán tử mới).

Một heap chính xác là một đối tượng, đi tới trình quản lý bộ nhớ ảo và yêu cầu bộ nhớ lớn (những gì bạn gọi là "một hồ bơi"). Sau đó, nó có tất cả các loại thuật toán khác nhau để xử lý với cách hiệu quả nhất để phân bổ các khối kích thước khác nhau và giải phóng chúng. Hơn nữa, nhiều người đã sửa đổi và tối ưu hóa các thuật toán này qua nhiều năm. Trong một thời gian dài, Windows xuất hiện với một tùy chọn gọi là đống phân mảnh thấp (LFH) mà bạn đã sử dụng phải kích hoạt thủ công. Bắt đầu với Vista LFH được sử dụng cho tất cả các heap theo mặc định.

Heaps không hoàn hảo và họ chắc chắn có thể làm giảm hiệu suất khi không được sử dụng đúng cách. Vì các nhà cung cấp hệ điều hành không thể dự đoán được mọi kịch bản mà bạn sẽ sử dụng một đống, các nhà quản lý heap của họ phải được tối ưu hóa cho việc sử dụng "trung bình". Nhưng nếu bạn có yêu cầu tương tự với yêu cầu cho một đống thông thường (nghĩa là nhiều đối tượng, kích thước khác nhau ....), bạn nên xem xét chỉ sử dụng một đống và không phát minh lại nó vì cơ hội là việc triển khai của bạn sẽ kém hơn đã cung cấp cho bạn.

Với phân bổ bộ nhớ, thời gian duy nhất bạn có thể đạt được hiệu suất bằng cách không sử dụng heap là bằng cách từ bỏ một số khía cạnh khác (phân bổ chi phí, thời gian phân bổ ....). Ví dụ, trong ứng dụng của chúng tôi, chúng tôi đã có một yêu cầu cho nhiều phân bổ dưới 1KB nhưng các phân bổ này chỉ được sử dụng trong một khoảng thời gian rất ngắn (mili giây). Để tối ưu hóa ứng dụng, tôi đã sử dụng thư viện Boost Pool nhưng đã mở rộng nó để "cấp phát" của tôi thực sự chứa một bộ sưu tập các đối tượng tăng bơi, mỗi đối tượng chịu trách nhiệm phân bổ một kích thước cụ thể từ 16 byte lên đến 1024 (ở bước 4). Điều này cung cấp gần như miễn phí (O (1) độ phức tạp)/miễn phí của các đối tượng này nhưng bắt là a) sử dụng bộ nhớ luôn luôn lớn và không bao giờ đi xuống ngay cả khi chúng tôi không có một đối tượng được phân bổ, b) giải phóng bộ nhớ nó sử dụng (ít nhất là trong chế độ chúng tôi đang sử dụng nó trong) vì vậy chúng tôi chỉ sử dụng này cho các đối tượng mà không dính xung quanh rất dài.

Vậy (các) khía cạnh nào của phân bổ bộ nhớ thông thường bạn sẵn sàng từ bỏ trong ứng dụng của mình?

+1

Cảm ơn lời giải thích tuyệt vời. – user805547

6

Tùy thuộc vào hệ thống có một số cách để thực hiện.

Cố gắng tránh phân mảnh ngay từ đầu, nếu bạn phân bổ các khối có quyền hạn là 2 bạn có ít cơ hội gây ra loại phân mảnh này. Có một vài cách khác xung quanh nó nhưng nếu bạn đã đạt đến trạng thái này thì bạn chỉ là OOM vào thời điểm đó vì không có cách xử lý nào khác ngoài việc giết chết quá trình yêu cầu bộ nhớ, chặn cho đến khi bạn có thể cấp phát bộ nhớ, hoặc trả về NULL làm vùng phân bổ của bạn.

Một cách khác là chuyển con trỏ tới con trỏ của dữ liệu của bạn (ví dụ: int **). Sau đó, bạn có thể sắp xếp lại bộ nhớ bên dưới chương trình (chủ đề an toàn tôi hy vọng) và phân bổ nhỏ gọn để bạn có thể phân bổ các khối mới và vẫn giữ dữ liệu từ các khối cũ (một khi hệ thống đến trạng thái này mặc dù trở thành một chi phí nặng nhưng ít khi được làm).

Ngoài ra còn có các cách "binning" bộ nhớ để bạn có các trang liền kề ví dụ dành 1 trang chỉ để phân bổ 512 và ít hơn, một cho 1024 và ít hơn, vv ... Điều này làm cho nó dễ dàng hơn để đưa ra quyết định về thùng rác nào để sử dụng và trong trường hợp xấu nhất bạn chia từ thùng cao nhất tiếp theo hoặc hợp nhất từ ​​thùng rác thấp hơn, làm giảm khả năng phân đoạn trên nhiều trang.

0
  • viết hồ sơ để hoạt động dưới dạng danh sách phân bổ, sau đó bạn có thể mở rộng và hủy khi cần. điều này có thể làm giảm sự phân mảnh.
  • và/hoặc triển khai hỗ trợ chuyển giao (hoặc di chuyển) để bạn có thể phân bổ hoạt động nhỏ gọn. đối tượng/chủ sở hữu có thể cần hỗ trợ bạn, vì hồ bơi có thể không nhất thiết biết cách tự chuyển các loại. nếu hồ bơi được sử dụng với một loại bộ sưu tập, sau đó nó là dễ dàng hơn để thực hiện nén/chuyển.
3

Triển khai object pools cho các đối tượng bạn thường xuyên phân bổ sẽ phân mảnh đáng kể xuống mà không cần thay đổi bộ cấp phát bộ nhớ của bạn.

1

Sẽ hữu ích khi biết chính xác hơn những gì bạn đang thực sự cố gắng làm, bởi vì có nhiều cách để giải quyết vấn đề này.
Nhưng, câu hỏi đầu tiên là: điều này thực sự xảy ra, hay nó là một mối quan tâm lý thuyết?

Một điều cần lưu ý là bạn thường có rất nhiều bộ nhớ ảo nhiều không gian địa chỉ có sẵn hơn bộ nhớ vật lý, vì vậy ngay cả khi bộ nhớ vật lý là phân mảnh, vẫn còn rất nhiều bộ nhớ ảo liên tục. (Tất nhiên, bộ nhớ vật lý là không liền kề bên dưới nhưng mã của bạn không thấy điều đó.)

Tôi nghĩ đôi khi không có sự sợ hãi về phân mảnh bộ nhớ, và kết quả là mọi người viết một bộ cấp phát bộ nhớ tùy chỉnh (hoặc tệ hơn, concoct một chương trình với xử lý và bộ nhớ moveable và nén). Tôi nghĩ rằng những điều này hiếm khi cần thiết trong thực tế, và đôi khi nó có thể cải thiện hiệu suất để loại bỏ điều này và quay lại sử dụng malloc.

Các vấn đề liên quan