Phân bổ bộ nhớ và bản phân vùng Heap

Question

Tôi bị nhầm lẫn về heap và free list. Tôi có một số câu hỏi và tôi có sự hiểu biết của riêng tôi về cách malloc hoạt động trong C. Xin vui lòng sửa tôi nếu tôi sai.

• Bộ nhớ heap có được tổ chức dưới dạng danh sách được liên kết (danh sách miễn phí) của dữ liệu khối không?
• Có sự khác biệt nào giữa bộ nhớ heap và danh sách miễn phí không?

sự hiểu biết của tôi về phân bổ lưu trữ (mở để cải thiện): - Khi chúng ta gọi là malloc, nó cấp phát bộ nhớ trong heap, và nó làm như vậy bằng cách chọn một khối dữ liệu có kích thước phù hợp từ free list, phải không?

Khi một khối bộ nhớ nhất định được trả về bởi malloc, nó được lấy ra khỏi danh sách miễn phí và địa chỉ vật lý của khối bộ nhớ đó được cập nhật trong bảng trang.

Khi bộ nhớ được tự do sử dụng free(), khối dữ liệu được chèn vào danh sách miễn phí và có thể để giảm phân mảnh, dính liền với khối lân cận và bit present trong mục bảng trang sẽ bị xóa.

Vì vậy, toàn bộ đống là danh sách miễn phí (danh sách liên kết các khối miễn phí) + khối dữ liệu được phân bổ.

Đó có phải là bức tranh toàn diện về phân bổ bộ nhớ không?

EDIT: Từ Linux phát triển hạt nhân (Robert Love) Chương về quản lý bộ nhớ, Slab phân bổ

"Một danh sách miễn phí có chứa một khối có sẵn, đã được phân bổ, dữ liệu cấu trúc Khi mã đòi hỏi một. trường hợp mới của cấu trúc dữ liệu, nó có thể lấy một trong các cấu trúc ra khỏi danh sách miễn phí thay vì phân bổ lượng bộ nhớ đủ và thiết lập cho cấu trúc dữ liệu Sau đó, khi cấu trúc dữ liệu không còn cần thiết nữa, được trả về danh sách miễn phí thay vì dealloca ted. Trong ý nghĩa này, danh sách miễn phí hoạt động như một bộ nhớ cache đối tượng, bộ nhớ đệm một loại thường được sử dụng của đối tượng."

miễn phí danh sách được nhắc đến như là một 'khối có sẵn cấu trúc dữ liệu được phân bổ,'.

• Làm thế nào là nó phân bổ, khi nó nằm trong một tự do-list?
• Và làm thế nào được trả lại một khối bộ nhớ vào danh sách miễn phí _ không _ giống như deallocating khối đó?
• thế nào là phân bổ phiến khác nhau từ phân bổ lưu trữ

Answer 1

malloc() là không thực sự liên quan đến bảng trang; nó phân bổ địa chỉ ảo và hạt nhân chịu trách nhiệm theo dõi vị trí các trang thực sự được lưu trữ trong RAM vật lý hoặc trên đĩa.

malloc() tương tác với hạt nhân qua cuộc gọi hệ thống brk(), yêu cầu hạt nhân phân bổ nhiều trang hơn cho quy trình hoặc phát hành trang trở lại hạt nhân. Vì vậy, có hai mức cấp phát bộ nhớ thực sự:

• Nhân này phân bổ các trang cho một quy trình, làm cho các trang đó không khả dụng để sử dụng bởi các quy trình khác. Từ quan điểm của hạt nhân, các trang có thể được đặt ở bất kỳ đâu và vị trí của chúng được theo dõi bởi bảng trang, nhưng từ quan điểm của quá trình, đó là một không gian địa chỉ ảo tiếp giáp. "Break chương trình" là thao tác brk() là ranh giới giữa các địa chỉ mà hạt nhân sẽ cho phép bạn truy cập (vì chúng tương ứng với các trang được phân bổ) và địa chỉ sẽ gây ra lỗi phân đoạn nếu bạn cố truy cập chúng.
• malloc() phân bổ các phần có kích thước biến của phân đoạn dữ liệu của chương trình để chương trình sử dụng. Khi không có đủ dung lượng trống trong phạm vi phân đoạn dữ liệu hiện tại, nó sử dụng brk() để nhận được nhiều trang hơn từ hạt nhân, làm cho phân đoạn dữ liệu lớn hơn. Khi phát hiện thấy một số khoảng trống ở cuối đoạn dữ liệu không được sử dụng, nó sử dụng brk() để cung cấp cho các trang không sử dụng trở lại hạt nhân, làm cho đoạn dữ liệu nhỏ hơn.

Lưu ý rằng các trang có thể được cấp phát cho một tiến trình (bằng hạt nhân) ngay cả khi chương trình đang chạy trong quá trình đó không thực sự sử dụng các trang cho bất kỳ thứ gì. Nếu bạn free() một khối bộ nhớ nằm ở giữa đoạn dữ liệu của bạn, việc triển khai free() không thể sử dụng brk() để thu hẹp phân đoạn dữ liệu vì vẫn còn các khối được phân bổ khác tại địa chỉ cao hơn. Vì vậy, các trang vẫn được phân bổ cho chương trình của bạn từ quan điểm hạt nhân, mặc dù chúng là "không gian trống" từ quan điểm malloc().

Mô tả của bạn về cách danh sách miễn phí hoạt động đúng với tôi, mặc dù tôi không có chuyên gia về cách phân bổ bộ nhớ được triển khai. Nhưng trích dẫn bạn đăng từ Robert Love nghe có vẻ như nó đang nói về việc cấp phát bộ nhớ trong nhân Linux, không liên quan đến việc cấp phát bộ nhớ bằng malloc() trong một tiến trình không gian người dùng. Loại danh sách miễn phí đó có thể hoạt động khác nhau.

Answer 2

Điều đầu tiên bạn muốn làm là phân biệt giữa phân bổ nhân và chương trình. Giống như @Wyzard cho biết, malloc sử dụng brk (sbrk và đôi khi mmap) để có được nhiều trang hơn từ hạt nhân. Sự hiểu biết của tôi về malloc là rất tốt, nhưng nó theo dõi những gì bạn có thể gọi là một đấu trường. Nó trung gian truy cập vào bộ nhớ và sẽ thực hiện các cuộc gọi hệ thống thích hợp để cấp phát bộ nhớ khi cần thiết.

Danh sách miễn phí là một cách để quản lý bộ nhớ. Gọi mmap hoặc brk mỗi khi bạn cần thêm bộ nhớ từ hạt nhân là chậm và không hiệu quả. Cả hai yêu cầu này sẽ yêu cầu chuyển ngữ cảnh sang chế độ hạt nhân và sẽ phân bổ cấu trúc dữ liệu để theo dõi quá trình nào sở hữu bộ nhớ. Một danh sách miễn phí ở cấp độ người dùng là một tối ưu hóa để không liên tục yêu cầu và trả về bộ nhớ cho nhân. Mục tiêu của một chương trình người dùng là thực hiện công việc của mình, không phải chờ cho hạt nhân thực hiện công việc của mình.

Bây giờ để trả lời các câu hỏi khác của bạn:

• Làm thế nào là nó được phân bổ, khi nó nằm trong một tự do-list?

Một cách khác để xem danh sách miễn phí là bộ nhớ cache. Một chương trình sẽ thực hiện các yêu cầu và hạt nhân sẽ cố gắng thực hiện chúng theo yêu cầu thay vì tất cả cùng một lúc. Tuy nhiên, khi một chương trình được thực hiện với một phần của bộ nhớ, đường dẫn nhanh không phải là để trả lại cho hạt nhân, nhưng đặt nó ở đâu đó an toàn để được phân bổ một lần nữa.Đặc biệt, một danh sách miễn phí có thể theo dõi các vùng bộ nhớ mà một người cấp phát có thể kéo, nhưng làm như vậy theo cách (với bảo vệ bộ nhớ) rằng mã người dùng không thể chỉ đồng chọn nó và bắt đầu viết trên tất cả .

• Và cách trả lại một khối bộ nhớ thành danh sách miễn phí không phải là giống như giải quyết khối đó?

Nếu chúng tôi cho rằng thực sự deallocating một khối yêu cầu trả lại cho hạt nhân và cập nhật các bảng trang nội bộ, thì sự khác biệt thực sự nằm ở những gì có quyền kiểm soát trang vật lý cơ bản (hoặc khung). Trên thực tế deallocating và trả lại bộ nhớ cho hạt nhân có nghĩa là hạt nhân có thể kéo từ các trang này, trong khi trả lại nó vào một cấp độ người dùng danh sách miễn phí có nghĩa là một số phần của chương trình vẫn điều khiển bộ nhớ đó.

• Phân bổ bản đệm khác với phân bổ lưu trữ như thế nào?

Điều này đang bắt đầu nhận được một số khu vực khác (tôi không quen thuộc lắm). Bản phân phối bản sàn là một cách mà hạt nhân quản lý việc cấp phát bộ nhớ. Từ những gì tôi đã thấy, bản vẽ cố gắng phân bổ nhóm thành các kích thước khác nhau và có một nhóm các trang để đáp ứng các yêu cầu đó. Tôi tin rằng kiến ​​trúc x86 thông thường sẽ cho phép phân bổ bộ nhớ vật lý liên tục với hai mức từ 16 byte đến 4 MB (mặc dù tôi đang sử dụng máy 64 bit). Tôi tin rằng có một số khái niệm về một danh sách miễn phí ở cấp độ này, cũng như các cách để nâng cấp hiệu quả hoặc hạ cấp kích thước phân bổ để cho phép các nhu cầu hệ thống khác nhau.

Mặt khác, phân bổ bộ nhớ âm thanh như đảm bảo có không gian trên đĩa cứng của bạn. Tôi thực sự chưa nghe thuật ngữ vì vậy tôi chỉ có thể suy đoán.

Answer 3

Ở đây bạn đang đề cập đến hai allocators khác nhau,

1. Buddy hệ thống cấp phát, sử dụng cho việc cấp phát trang để Zone, sử dụng free_list để lưu trữ các trang miễn phí, phân bổ cho họ, sau khi giải phóng, nếu có thể kết hợp chúng lại để một kích thước trang tiếp giáp lớn hơn của thứ tự cao hơn.
2. Trình phân bổ bản vẽ hoạt động trên các cấu trúc dữ liệu đã được phân bổ như keme_cache, gọi kmalloc.

tham khảo Heap Memory in C Programming cho đống.

Đối với chương trình c trong không gian người dùng, chúng tôi có bộ nhớ heap trong call_stack nơi malloc diễn ra. Điều này được đánh dấu bằng _break được nâng cao bởi sbrk() khi cần thêm bộ nhớ.

Trong hạt nhân Linux, mỗi quy trình có task_struct có ngăn xếp và con trỏ của riêng nó vào danh sách các trang được sử dụng bởi nó.