C - Thiết kế miễn phí của riêng bạn() chức năng

Question

Hôm nay, tôi xuất hiện cho một cuộc phỏng vấn và người phỏng vấn hỏi tôi điều này,

1. Hãy nói cho tôi những bước làm thế nào bạn sẽ thiết kế free() chức năng của riêng bạn cho deallocate bộ nhớ được cấp phát.
2. Làm cách nào hiệu quả hơn chức năng free() mặc định của C? Bạn có thể kết luận điều gì?

tôi đã nhầm lẫn, không thể nghĩ ra cách để thiết kế.

Bạn nghĩ sao?

---

EDIT: Kể từ khi chúng ta cần phải biết về cách malloc() công trình, bạn có thể cho tôi biết các bước để viết malloc() chức năng riêng của chúng tôi

Answer 1

Đó thực sự là một câu hỏi khá mơ hồ, và đó có thể là lý do tại sao bạn bị lẫn lộn. Ông có nghĩa là, cho một thực hiện malloc hiện có, làm thế nào bạn sẽ đi về cố gắng để phát triển một cách hiệu quả hơn để giải phóng bộ nhớ cơ bản? Hay anh ta mong bạn bắt đầu thảo luận về các loại triển khai malloc khác nhau và lợi ích và vấn đề của họ? Anh ta có mong đợi bạn biết các chức năng bộ nhớ ảo trên kiến ​​trúc x86 không?

Ngoài ra, hiệu quả hơn, anh ấy có nghĩa là có nhiều không gian hiệu quả hơn hoặc tiết kiệm thời gian hơn không? Liệu miễn phí() phải được xác định? Liệu nó có phải trả lại bộ nhớ cho hệ điều hành càng nhiều càng tốt vì nó ở trong một môi trường bộ nhớ thấp, đa tác vụ? Tiêu chí của chúng tôi ở đây là gì?

Thật khó để nói bắt đầu từ đâu với một câu hỏi mơ hồ như thế, ngoài việc bắt đầu đặt câu hỏi của riêng bạn để làm rõ. Sau khi tất cả, để thiết kế chức năng miễn phí của riêng bạn, trước tiên bạn phải biết làm thế nào malloc được thực hiện. Vì vậy, rất có thể là, câu hỏi thực sự là về việc liệu bạn có biết bất cứ điều gì về việc làm thế nào malloc có thể được thực hiện.

Nếu bạn không quen thuộc với nội bộ của quản lý bộ nhớ, cách dễ nhất để bắt đầu với sự hiểu biết cách triển khai malloc là trước tiên hãy viết của riêng bạn.

Khám phá this IBM DeveloperWorks article called "Inside Memory Management" để bắt đầu.

Nhưng trước khi bạn có thể viết malloc của riêng bạn/miễn phí, trước tiên bạn cần bộ nhớ để phân bổ/miễn phí. Thật không may, trong một hệ điều hành chế độ bảo vệ, bạn không thể trực tiếp địa chỉ bộ nhớ trên máy. Vậy làm thế nào để bạn có được nó?

Bạn yêu cầu hệ điều hành. Với các tính năng bộ nhớ ảo của x86, bất kỳ bộ nhớ RAM hoặc bộ nhớ hoán đổi nào cũng có thể được ánh xạ tới địa chỉ bộ nhớ của hệ điều hành. Những gì chương trình của bạn nhìn thấy như bộ nhớ có thể được phân mảnh vật lý trong suốt toàn bộ hệ thống, nhưng nhờ trình quản lý bộ nhớ ảo của hạt nhân, tất cả đều giống nhau.

Nhân thường cung cấp các cuộc gọi hệ thống cho phép bạn ánh xạ trong bộ nhớ bổ sung cho quy trình của bạn. Trên hệ điều hành UNIX cũ, điều này thường là brk/sbrk để phát triển bộ nhớ heap lên cạnh của quá trình của bạn hoặc thu nhỏ nó, nhưng rất nhiều hệ thống cũng cung cấp mmap/munmap để ánh xạ một khối lớn bộ nhớ heap. có quyền truy cập vào một khối bộ nhớ lớn, liền kề nhìn mà bạn cần malloc/miễn phí để quản lý nó.

Khi quá trình của bạn có một số bộ nhớ heap sẵn có, tất cả đều chia nhỏ thành từng phần, với mỗi đoạn chứa thông tin meta của chính nó về kích thước và vị trí của nó và có phân bổ hay không. Một danh sách các cấu trúc đơn giản, mỗi trường chứa một số thông tin meta và một mảng lớn các byte, có thể hoạt động, trong trường hợp malloc phải chạy qua danh sách cho đến khi tìm thấy một đoạn lớn chưa được phân bổ (hoặc các khối có thể kết hợp), và sau đó bản đồ trong bộ nhớ nhiều hơn nếu nó không thể tìm thấy một đoạn đủ lớn. Một khi bạn tìm thấy một đoạn, bạn chỉ cần trả về một con trỏ đến dữ liệu. free() sau đó có thể sử dụng con trỏ đó để đảo ngược một vài byte vào các trường thành viên tồn tại trong cấu trúc, sau đó nó có thể sửa đổi (tức là đánh dấu chunk.allocated = false;).Nếu có đủ các phần chưa được phân bổ ở cuối danh sách của bạn, bạn thậm chí có thể xóa chúng khỏi danh sách và unmap hoặc thu hẹp bộ nhớ đó khỏi đống quá trình của bạn.

Đó thực sự là một phương pháp đơn giản để triển khai malloc. Như bạn có thể tưởng tượng, có rất nhiều cách có thể tách bộ nhớ của bạn thành nhiều phần và sau đó quản lý các khối đó. Có nhiều cách như có cấu trúc dữ liệu và thuật toán. Tất cả chúng đều được thiết kế cho các mục đích khác nhau, như hạn chế phân mảnh do các khối nhỏ, được phân bổ trộn với các khối nhỏ, chưa được phân bổ, hoặc đảm bảo rằng malloc và tự do chạy nhanh (hoặc đôi khi thậm chí chậm hơn, nhưng dự đoán chậm). Có dlmalloc, ptmalloc, jemalloc, Hoard's malloc và nhiều thứ khác ngoài đó và nhiều thứ trong số đó khá nhỏ và gọn gàng, vì vậy đừng ngại đọc chúng. Nếu tôi nhớ chính xác, "Ngôn ngữ lập trình C" của Kernighan và Ritchie thậm chí còn sử dụng triển khai thực hiện malloc đơn giản như một ví dụ của họ.

Answer 2

Bạn không thể mù quáng thiết kế free() mà không biết làm thế nào malloc() công trình thuộc mui xe vì việc triển khai free() của bạn sẽ cần phải biết cách thao tác dữ liệu sổ sách kế toán và điều đó là không thể nếu không biết cách thực hiện malloc(). Vì vậy, một câu hỏi không thể thay thế có thể là cách bạn sẽ thiết kế malloc() và miễn phí() thay vì đó không phải là một câu hỏi tầm thường, nhưng bạn có thể trả lời một phần ví dụ bằng cách đề xuất thực hiện rất đơn giản của một nhóm bộ nhớ không tương đương với malloc() tất nhiên nhưng sẽ cho biết sự hiện diện của bạn về kiến ​​thức.

Answer 3

malloc và free chỉ có ý nghĩa nếu ứng dụng của bạn hoạt động trên hệ điều hành. Nếu bạn muốn viết các chức năng quản lý bộ nhớ của mình, bạn sẽ phải biết cách yêu cầu bộ nhớ từ hệ điều hành cụ thể đó hoặc bạn có thể đặt trước bộ nhớ heap bằng cách sử dụng malloc hiện có và sau đó sử dụng các chức năng của riêng bạn để phân phối/phân phối lại bộ nhớ được cấp phát thông qua ứng dụng của bạn

Answer 4

Mẫu sử dụng bộ nhớ có thể là một yếu tố. Việc triển khai mặc định free không thể giả định bất kỳ điều gì về tần suất bạn phân bổ/deallocate và kích thước bạn phân bổ khi bạn làm. Ví dụ, nếu bạn thường xuyên phân bổ và deallocate các đối tượng có kích thước tương tự, bạn có thể đạt được tốc độ, hiệu quả bộ nhớ, và giảm phân mảnh bằng cách sử dụng một nhóm bộ nhớ. Quay lại đầu trang |

CHỈNH SỬA: như ghi chú sắc nét, chỉ có ý nghĩa để thiết kế miễn phí và kết hợp với nhau. Vì vậy, điều đầu tiên sẽ là để tìm ra cách malloc được triển khai.

Answer 5

Một cách tiếp cận chung khi bạn chỉ có quyền truy cập vào không gian người dùng (thường được gọi là bộ nhớ) là để có được một phần lớn bộ nhớ từ hệ điều hành khi khởi động ứng dụng. malloc của bạn cần kiểm tra các khu vực có kích thước phù hợp của hồ bơi đó vẫn miễn phí (thông qua một số cấu trúc dữ liệu) và đưa ra các con trỏ tới bộ nhớ đó. free của bạn cần đánh dấu bộ nhớ là miễn phí một lần nữa trong cấu trúc dữ liệu và có thể cần phải kiểm tra sự phân mảnh của hồ bơi.

Lợi ích là bạn có thể thực hiện phân bổ trong thời gian gần như không đổi, nhược điểm là ứng dụng của bạn tiêu thụ nhiều bộ nhớ hơn thực tế là cần thiết.

Answer 6

Có một kiến ​​trúc mà malloc và miễn phí được cho là tuân thủ - về cơ bản là kiến ​​trúc lớp cho phép các chiến lược khác nhau cùng tồn tại. Sau đó, phiên bản miễn phí được thực hiện tương ứng với phiên bản của malloc được sử dụng.

Tuy nhiên, tôi không chắc tần suất kiến ​​trúc này được quan sát.

Answer 7

Kiến thức về hoạt động của malloc() là cần thiết để triển khai free(). Bạn có thể tìm thấy việc triển khai malloc() và free() bằng cách sử dụng cuộc gọi hệ thống sbrk() trong K & R Ngôn ngữ lập trình C Chương 8, Mục 8.7 "Ví dụ - Bộ phân bổ bộ nhớ" Trang 195-189.

Answer 8

Cho tôi biết các bước bạn sẽ thiết kế chức năng free() của riêng bạn để deallocate bộ nhớ được cấp phát.

#include <stdlib.h> 
#undef free 
#define free(X) my_free(X) 

inline void my_free(void *ptr) { } 

Làm thế nào nó có thể hiệu quả hơn so với miễn phí) chức năng (mặc định C?

Rất nhanh, yêu cầu không có chu trình máy. Nó cũng làm cho việc sử dụng sau khi lỗi miễn phí biến mất. Đó là một hàm rất hữu ích free để sử dụng trong các chương trình được khởi tạo như các quá trình thực thi hàng loạt; nó có thể được triển khai một cách hữu ích trong một số tình huống sản xuất.

Bạn có thể kết luận điều gì?

Tôi thực sự muốn công việc này, nhưng ở một công ty khác.