Bất lợi của việc sử dụng danh sách liên kết trong quản lý bộ nhớ

Question

Tôi hơi bối rối về những bất lợi chính của việc sử dụng danh sách được liên kết sẽ duy trì danh sách các khối đĩa miễn phí. Giáo sư của tôi nói rằng sử dụng một bản đồ bit sẽ giúp giải quyết vấn đề nói trên. Tại sao sử dụng một bản đồ bit giải quyết vấn đề này?

Để thu hẹp câu hỏi của tôi:

1. nhược điểm chính của việc sử dụng một danh sách liên kết trong việc duy trì một danh sách các khối đĩa tự do là gì?

2. Tại sao việc sử dụng bản đồ bit giải quyết vấn đề/bất lợi này?

Answer 1

Hi,

nhược điểm chính của việc sử dụng một danh sách liên kết trong việc duy trì một danh sách các khối đĩa tự do là gì?

• Đề án này không hiệu quả vì phải duyệt qua danh sách, chúng tôi phải đọc từng khối yêu cầu thời gian đáng kể.
• Bất lợi thứ hai là yêu cầu bộ nhớ bổ sung để duy trì danh sách liên kết của tất cả các khối đĩa miễn phí.

Tại sao sử dụng bản đồ bit giải quyết vấn đề/bất lợi này?

• Thông thường, danh sách không gian đĩa trống được thực hiện dưới dạng bản đồ bit hoặc bit bit. Mỗi khối được biểu diễn bằng một bit. 0 (không) được đánh dấu là một khối miễn phí trong khi 1 là cho khối được phân bổ. Vì vậy, không cần thêm bộ nhớ phụ để lưu trữ không gian đĩa trống.

• Kiểm tra phân bổ truy cập ngẫu nhiên nhanh: Kiểm tra xem khu vực có miễn phí đơn giản như kiểm tra bit tương ứng hay không. quá trình truyền tải nhanh hơn LinkedList.

Advantage khác của việc sử dụng Bit Bản đồ:

• nhanh xóa: Dữ liệu không cần phải được ghi đè vào xóa, lật các bit tương ứng là đủ

Tháng này giúp bạn. Điền miễn phí để làm rõ thêm.

Kính trọng,

Bhavik

Answer 2

Các giải pháp đúng được đưa ra bởi @FullDecent trong các ý kiến ​​để câu trả lời khác (ông xứng đáng tiền thưởng của bạn). Để xây dựng:

Giả sử rằng các ổ đĩa trong câu hỏi là trong những cũ, loại thông thường, với một bề mặt lưu trữ quay và đọc/ghi đầu rằng chất di chuyển xuyên tâm trên bề mặt ...

Nói chung nó là tốt cho các tập tin được lưu trữ như liên tục trên đĩa càng tốt, do đó nhiều khối có thể được đọc tuần tự.Nếu một tập tin là "phân mảnh" (khối của nó nằm rải rác ở những nơi khác nhau trên đĩa), đầu ổ đĩa sẽ cần phải được định vị lại nhiều lần để đọc toàn bộ tập tin. Tái định vị đầu là một trong những hoạt động tốn nhiều thời gian nhất liên quan đến việc đọc đĩa (chỉ đứng thứ hai sau khi bắt đầu quay đĩa sau khi nó bị dừng). Do đó các thủ tục được gọi là "chống phân mảnh" hoặc "chống phân mảnh", mà sắp xếp lại các khối được sử dụng trên một đĩa để làm cho tất cả các tập tin tiếp giáp.

Với danh sách liên kết các khối miễn phí, phân bổ liên quan đến việc lấy các khối từ phía trước danh sách và deallocation liên quan đến việc thêm các khối được giải phóng vào trước danh sách. Do đó danh sách có thể lộn xộn, với các khối không liền kề trên đĩa thường xuyên nằm trong danh sách. Để tìm một khối liền kề các khối miễn phí đủ lớn cho một tệp lớn, có thể cần phải quét một phần đáng kể trong danh sách.

Với bitmap, bạn vẫn cần phải quét phần khối miễn phí liền kề lớn, nhưng điều này dễ hơn vì 8, 16, 32 hoặc 64 bit (tùy thuộc vào kích thước từ của phần cứng) có thể được kiểm tra trong hoạt động đơn lẻ.