VI Các Phương Pháp Cấp Phát - Tài Liệu Text - 123doc

1. Trang chủ >
2. Công Nghệ Thông Tin >
3. Hệ điều hành >

VI Các phương pháp cấp phát

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (3.99 MB, 238 trang )

Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0Hình 0-5 Không gian đĩa được cấp phát kềTruy xuất một tập tin được cấp phát kề rất dễ. Đối với truy xuất tuần tự, hệthống tập tin nhớ địa chỉ đĩa của khối cuối cùng được tham chiếu và đọc khối tiếptheo. Để truy xuất khối i của tập tin mà bắt đầu tại khối b, chúng ta có thể lập tức truyxuất khối b+i. Do đó, cả truy xuất tuần tự và truy xuất trực tiếp có thể được hỗ trợ bởicấp phát kề.Tuy nhiên, cấp phát kề có một số vấn đề. Một khó khăn là tìm không gian chomột tập tin mới. Việc cài đặt của hệ thống quản lý không gian trống xác định tác vụnày được hoàn thành như thế nào. Bất cứ hệ thống quản lý nào có thể được dùngnhưng nhanh chậm khác nhau.Vấn đề cấp phát không gian kề có thể được xem là vấn đề cấp phát lưu trữđộng của ứng dụng để thoả mãn yêu cầu kích thước n từ danh sách các lỗ trống. Firstfit và best fit là những chiến lược chung nhất được dùng để chọn lỗ trống từ tập hợpcác lỗ trống sẳn dùng. Những mô phỏng hiển thị rằng cả hai first fit và best fit hiệuquả hơn worst fit về thời gian và sử dụng không gian lưu trữ. First fit hay best fit đềukhông phải là giải thuật tốt nhất nhưng thường thì first fit nhanh hơn best fit.Các giải thuật này gặp phải vấn đề phân mãnh ngoài. Khi các tập tin được cấpphát và xoá, không gian đĩa trống bị chia thành những mảnh nhỏ. Phân mãnh ngoàitồn tại bất cứ khi nào không gian trống được chia thành những đoạn. Nó trở thành mộtvấn đề khi đoạn kề lớn nhất không đủ cho một yêu cầu; lưu trữ được phân thành nhiềulỗ, không lỗ nào đủ lớn để lưu dữ liệu. Phụ thuộc vào tổng lượng lưu trữ đĩa và kíchthước tập tin trung bình, phân mãnh ngoài có thể là vấn đề chính hay phụ.Một số hệ thống vi tính cũ dùng cấp phát kề trên đĩa mềm. Để ngăn ngừalượng lớn không gian đĩa phân mãnh ngoài, người dùng phải chạy thủ tục đóng góilại. Thủ tục này chép toàn bộ hệ thống tập tin tới một đĩa khác hay trên băng từ. Kếđến, đĩa mềm ban đầu được giải phóng hoàn toàn, tạo một không gian trống kề lớn.Sau đó, thủ tục này chép các tập tin trở lại trên đĩa mềm bằng cách cấp phát khônggian kề từ một lỗ lớn. Cơ chế này hiệu quả trong việc hợp nhất (compacts) tất cảkhông gian trống thành một không gian trống kề, giải quyết vấn đề phân mãnh. Chiphí cho việc hợp nhất là thời gian. Chi phí thời gian phục vụ cho các đĩa cứng lớndùng cấp phát kề, ở đây hợp nhất tất cả không gian mất hàng giờ. Trong thời gian này,các thao tác hệ thống thông thường không thể được phép vì thế hợp nhất tránh đượctất cả chi phí do có thay đổi về dữ liệu.Biên soạn: Th.s Nguyễn Phú Trường - 09/2005Trang 230Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0Một vấn đề khác với cấp phát kề là xác định bao nhiêu không gian được yêucầu cho một tập tin. Khi một tập tin được tạo, toàn bộ không gian nó cần phải đượctìm kiếm và được cấp phát. Người tạo (chương trình hay người) biết kích thước tập tinđược tạo như thế nào? Trong một số trường hợp việc xác định này tương đối đơn giản(thí dụ chép một tập tin đã có); tuy nhiên, kích thước của tập tin xuất có thể khó đểước lượng.Nếu chúng ta cấp quá ít không gian tới một tập tin, chúng ta thấy rằng tập tinkhông thể mở rộng. Đặc biệt với một chiến lược cấp phát best fit, không gian trên cảhai phía của tập tin đang được dùng. Do đó, chúng ta không thể làm cho tập tin lớnhơn. Hai khả năng có thể. Thứ nhất, chương trình người dùng có thể được kết thúc vớimột thông báo lỗi hợp lý. Sau đó, người dùng phải cấp phát nhiều không gian hơn vàchạy chương trình lại. Việc lặp này có thể gây ra chi phí. Để ngăn chặn chúng, ngườidùng sẽ mô phỏng nhiều hơn lượng không gian được yêu cầu. Điều này dẫn đếnkhông gian bị lãng phí.Một khả năng khác là tìm một lỗ trống lớn hơn, chép nội dung của tập tin tớikhông gian trống mới, và giải phóng không gian trước đó. Một loạt các hoạt động nàycó thể được lặp lại với điều kiện là không gian tồn tại mặc dù nó tiêu tốn nhiều thờigian. Tuy nhiên, trong trường hợp này người dùng không bao giờ yêu cầu được thôngbáo về những gì đang xảy ra; hệ thống tiếp tục mặc dù vấn đề phát sinh.Ngay cả nếu toàn bộ không gian được yêu cầu cho tập tin được biết trước, cấp pháttrước là không đủ. Một tập tin sẽ lớn lên trong khoảng thời gian dài phải được cấpphát đủ không gian cho kích thước cuối cùng của nó mặc dù không gian đó có thểkhông được dùng cho khoảng thời gian dài. Do đó, tập tin có lượng lớn phân mãnhtrong.Để tối thiểu các khó khăn này, một số hệ điều hành dùng một cơ chế cấp phátkề được hiệu chỉnh. Trong cơ chế này đoạn không gian kề được cấp phát trước và sauđó khi lượng không gian đó không đủ lớn, một đoạn không gian kề khác, một đoạnmở rộng (extent), được thêm vào cấp phát ban đầu. Sau đó, vị trí của các khối tập tinđược ghi lại như một vị trí và một bộ đếm khối cộng với một liên kết tới khối đầu tiêncủa đoạn mở rộng tiếp theo. Trên một số hệ thống, người sở hữu tập tin có thể đặtkích thước đoạn mở rộng, nhưng việc đặt này có thể không hiệu quả nếu người sở hữukhông đúng. Phân mãnh trong vẫn còn là vấn đề nếu đoạn mở rộng quá lớn và phânmãnh ngoài có thể là vấn đề khi các đoạn mở rộng có kích thước khác nhau được cấpphát và thu hồi.VI.2 Cấp phát liên kếtCấp phát liên kết giải quyết vấn đề của cấp phát kề. Với cấp phát liên kết, mỗitập tin là một danh sách các khối đĩa được liên kết; các khối đĩa có thể được phân tánkhắp nơi trên đĩa. Thư mục chứa một con trỏ chỉ tới khối đầu tiên và các khối cuốicùng của tập tin. Thí dụ, một tập tin có 5 khối có thể bắt đầu tại khối số 9, tiếp tục làkhối 16, sau đó khối 1, khối 10 và cuối cùng khối 25 (như hình X-6). Mỗi khối chứamột con trỏ chỉ tới khối kế tiếp. Các con trỏ này không được làm sẳn dùng cho ngườidùng. Do đó, nếu mỗi khối là 512 bytes, và địa chỉ đĩa (con trỏ) yêu cầu 4 bytes thìphần chứa dữ liệu của khối là 508 bytes.Để tạo một tập tin mới, chúng ta đơn giản tạo một mục từ mới trong thư mục.Với cấp phát liên kết, mỗi mục từ thư mục có một con trỏ chỉ tới khối đĩa đầu tiên củatập tin. Con trỏ này được khởi tạo tới nil (giá trị con trỏ cuối danh sách) để chỉ mộttập tin rỗng. Trường kích thước cũng được đặt tới 0. Một thao tác viết tới tập tin làmmột khối trống được tìm thấy bằng hệ thống quản lý không gian trống, sau đó khốiBiên soạn: Th.s Nguyễn Phú Trường - 09/2005Trang 231Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0mới này được viết tới và được liên kết tới cuối tập tin. Để đọc một tập tin, chúng tađơn giản đọc các khối bằng cách lần theo các con trỏ từ khối này tới khối khác.Không có sự phân mãnh ngoài với cấp phát liên kết, và bất cứ khối trống trêndanh sách không gian trống có thể được dùng để thoả mãn yêu cầu. Kích thước củamột tập tin không cần được khai báo khi tập tin đó được tạo. Một tập tin có thể tiếptục lớn lên với điều kiện là các khối trống sẳn có. Do đó, nó không bao giờ cần thiếtđể hợp nhất không gian trống.Hình 0-6 cấp phát không gian đĩa liên kếtTuy nhiên, cấp phát liên kết có một vài nhược điểm. Vấn đề chủ yếu là nó cóthể được dùng hiệu quả chỉ cho các tập tin truy xuất tuần tự. Để tìm khối thứ i của tậptin, chúng ta phải bắt đầu tại điểm bắt đầu của tập tin đó, và lần theo con trỏ cho đếnkhi chúng ta nhận được khối thứ i. Mỗi truy xuất tới con trỏ yêu cầu một thao tác đọcđĩa, và đôi khi là một tìm kiếm đĩa. Do đó, nó không đủ hỗ trợ một khả năng truy xuấttrực tiếp cho các tập tin cấp phát liên kết.Một nhược điểm khác của cấp phát liên kết là không gian được yêu cầu chocác con trỏ. Nếu một con trỏ yêu cầu 4 bytes của khối 512 bytes thì 0.77% của đĩađược dùng cho các con trỏ thay vì là thông tin.Một giải pháp thông thường để giải quyết vấn đề này là tập hợp các khối vàocác nhóm (clusters) và cấp phát các nhóm hơn là các khối. Thí dụ, hệ thống tập tin cóthể định nghĩa nhóm gồm 4 khối và thao tác trên đĩa chỉ trong đơn vị nhóm thì cáccon trỏ dùng % nhỏ hơn của không gian của tập tin. Phương pháp này cho phép ánhxạ khối luận lý tới vật lý vẫn còn đơn giản, nhưng cải tiến thông lượng đĩa và giảmkhông gian được yêu cầu cho cấp phát khối và quản lý danh sách trống. Chi phí củatiếp cận này là tăng phân mãnh trong vì nhiều không gian hơn bị lãng phí nếu mộtnhóm chỉ đầy một phần hơn là một khối đầy một phần. Các nhóm có thể được dùngđể cải tiến thời gian truy xuất đĩa cho nhiều giải thuật khác nhau vì thế chúng đượcdùng trong hầu hết các hệ điều hành.Biên soạn: Th.s Nguyễn Phú Trường - 09/2005Trang 232Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0Một vấn đề khác của cấp phát liên kết là khả năng tin cậy. Vì các tập tin đượcliên kết với nhau bởi các con trỏ được phân tán khắp đĩa, xem xét điều gì xảy ra nếumột con trỏ bị mất hay bị phá hỏng. Một con bọ (bug) trong phần mềm hệ điều hànhhay lỗi phần cứng đĩa có thể dẫn tới việc chọn con trỏ sai. Lỗi này có thể dẫn tới việcliên kết vào danh sách không gian trống hay vào một tập tin khác. Các giải pháp mộtphần là dùng các danh sách liên kết đôi hay lưu tên tập tin và số khối tương đối trongmỗi khối; tuy nhiên, các cơ chế này yêu cầu nhiều chi phí hơn cho mỗi tập tin.Một thay đổi quan trọng trên phương pháp cấp phát liên kết là dùng bảng cấpphát tập tin (file allocation table-FAT). Điều này đơn giản nhưng là phương phápcấp phát không gian đĩa hiệu quả được dùng bởi hệ điều hành MS-DOS và OS/2. Mộtphần đĩa tại phần bắt đầu của mỗi phân khu được thiết lập để chứa bảng này. Bảngnày có một mục từ cho mỗi khối đĩa và được lập chỉ mục bởi khối đĩa. FAT đượcdùng nhiều như là một danh sách liên kết. Mục từ thư mục chứa số khối của khối đầutiên trong tập tin. Mục từ bảng được lập chỉ mục bởi số khối đó sau đó chứa số khốicủa khối tiếp theo trong tập tin. Chuỗi này tiếp tục cho đến khi khối cuối cùng, có giátrị cuối tập tin đặc biệt như mục từ bảng. Các khối không được dùng được hiển thị bởigiá trị bảng 0. Cấp phát một khối mới tới một tập tin là một vấn đề đơn giản cho việctìm mục từ bảng có giá trị 0 đầu tiên và thay thế giá trị kết thúc tập tin trước đó vớiđịa chỉ của khối mới. Sau đó, số 0 được thay thế với giá trị kết thúc tập tin. Một thí dụminh hoạ là cấu trúc FAT của hình X-7 cho một tập tin chứa các khối đĩa 217, 618 và339.Hình 0-7 Bảng cấp phát tập tinCơ chế cấp phát FAT có thể dẫn tới số lượng lớn tìm kiếm đầu đọc đĩa nếuFAT không được lưu trữ(cache). Đầu đọc đĩa phải di chuyển tới điểm bắt đầu củaphân khu để đọc FAT và tìm vị trí khối sau đó di chuyển tới vị trí của chính khối đĩađó. Trong trường hợp xấu nhất, cả hai di chuyển xảy ra cho mỗi khối đĩa. Lợi điểm làthời gian truy xuất ngẫu nhiên được cải tiến vì đầu đọc đĩa có thể tìm vị trí của bất cứkhối nào bằng cách đọc thông tin trong FAT.Biên soạn: Th.s Nguyễn Phú Trường - 09/2005Trang 233Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0VI.3 Cấp phát được lập chỉ mụcCấp phát liên kết giải quyết việc phân mãnh ngoài và vấn đề khai báo kíchthước của cấp phát kề. Tuy nhiên, cấp phát liên kết không hỗ trợ truy xuất trực tiếphiệu quả vì các con trỏ chỉ tới các khối được phân tán với chính các khối đó qua đĩavà cần được lấy lại trong thứ tự. Cấp phát được lập chỉ mục giải quyết vấn đề nàybằng cách mang tất cả con trỏ vào một vị trí: khối chỉ mục (index block).Mỗi tập tin có khối chỉ mục của chính nó, khối này là một mảng các địa chỉkhối đĩa. Mục từ thứ i trong khối chỉ mục chỉ tới khối i của tập tin. Thư mục chứa địachỉ của khối chỉ mục (như hình X-8). Để đọc khối i, chúng ta dùng con trỏ trong mụctừ khối chỉ mục để tìm và đọc khối mong muốn. Cơ chế này tương tự như cơ chế phântrang.Hình 0-8 Cấp phát không gian đĩa được lập chỉ mụcKhi một tập tin được tạo, tất cả con trỏ trong khối chỉ mục được đặt tới nil.Khi khối thứ i được viết đầu tiên, khối được chứa từ bộ quản lý không gian trống vàđịa chỉ của nó được đặt trong mục từ khối chỉ mục.Cấp phát được lập chỉ mục hỗ trợ truy xuất trực tiếp, không gặp phải sự phânmãnh ngoài vì bất cứ khối trống trên đĩa có thể đáp ứng yêu cầu thêm không gian.Cấp phát được lập chỉ mục gặp phải sự lãng phí không gian. Chi phí con trỏ của khốichỉ mục thường lớn hơn chi phí con trỏ của cấp phát liên kết. Xét trường hợp thôngthường trong đó chúng ta có một tập tin với chỉ một hoặc hai khối. Với cấp phát liênkết, chúng ta mất không gian của chỉ một con trỏ trên khối (một hay hai con trỏ). Vớicấp phát được lập chỉ mục, toàn bộ khối chỉ mục phải được cấp phát thậm chí nếu mộthay hai con trỏ là khác nil.Điểm này sinh ra câu hỏi khối chỉ mục nên lớn bao nhiêu? Mỗi tập tin phải cómột khối chỉ mục để mà chúng ta muốn khối chỉ mục nhỏ nhất có thể. Tuy nhiên, nếukhối chỉ mục quá nhỏ nó không thể quản lý đủ các con trỏ cho một tập tin lớn và mộtcơ chế sẽ phải sẳn có để giải quyết vấn đề này:Biên soạn: Th.s Nguyễn Phú Trường - 09/2005Trang 234Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0•••Cơ chế liên kết (linked scheme): một khối chỉ mục thường là một khốiđĩa. Do đó, nó có thể được đọc và viết trực tiếp bởi chính nó. Để cho phépđối với các tập tin lớn, chúng ta có thể liên kết nhiều khối chỉ mục vớinhau. Thí dụ, một khối chỉ mục có thể chứa một header nhỏ cho tên tập tinvà một tập hợp của các địa chỉ 100 khối đĩa đầu tiên. Địa chỉ tiếp theo (từcuối cùng trong khối chỉ mục) là nil (đối với một tập tin nhỏ) hay một contrỏ tới khối chỉ mục khác (cho một tập tin lớn)Chỉ mục nhiều cấp (multilevel index): một biến dạng của biểu diễn liênkết là dùng khối chỉ mục cấp 1 để chỉ tới khối chỉ mục cấp 2. Khối cấp 2chỉ tới các khối tập tin. Để truy xuất một khối, hệ điều hành dùng chỉ mụccấp 1 để tìm một khối chỉ mục cấp 2 và khối đó tìm khối dữ liệu mongmuốn. Tiếp cận này có thể được tiếp tục tới cấp 3 hay cấp 4, tuỳ thuộc vàokích thước tập tin lớn nhất được mong muốn. Với khối có kích thước4,096 bytes, chúng ta có thể lưu 1,024 con trỏ 4 bytes trong một khối chỉmục. Chỉ mục hai cấp cho phép 1,048,576 khối dữ liệu, cho phép tập tin cókích thước tới 4GB.Cơ chế kết hợp (combined scheme): một biến dạng khác được dùng trongUFS là giữ 15 con trỏ đầu tiên của khối chỉ mục trong inode của tập tin.12 con trỏ đầu tiên của 15 con trỏ này chỉ tới khối trực tiếp (direct blocks);nghĩa là chúng chứa các địa chỉ của khối mà chứa dữ liệu của tập tin. Dođó, dữ liệu đối với các tập tin nhỏ (không lớn hơn 12 khối) không cần mộtkhối chỉ mục riêng. Nếu kích thước khối là 4 KB, thì tới 48 KB dữ liệu cóthể truy xuất trực tiếp. 3 con trỏ tiếp theo chỉ tới các khối gián tiếp(indirect blocks). Con trỏ khối gián tiếp thứ nhất là địa chỉ của khối giántiếp đơn (single indirect blocks). Khối gián tiếp đơn là một khối chỉ mụckhông chứa dữ liệu nhưng chứa địa chỉ của các khối chứa dữ liệu. Sau đó,có con trỏ khối gián tiếp đôi (double indirect block) chứa địa chỉ của mộtkhối mà khối này chứa địa chỉ của các khối chứa con trỏ chỉ tới khối dữliệu thật sự. Con trỏ cuối cùng chứa chứa địa chỉ của khối gián tiếp ba(triple indirect block). Với phương pháp này, số khối có thể được cấp pháttới một tập tin vượt quá lượng không gian có thể đánh địa chỉ bởi các contrỏ tập tin 4 bytes hay 4 GB. Nhiều cài đặt UNIX gồm Solaris và AIX củaIBM hỗ trợ tới 64 bit con trỏ tập tin. Các con trỏ có kích thước này chophép các tập tin và hệ thống tập tin có kích thước tới terabytes. Một inodeđược hiển thị trong hình X-9:Biên soạn: Th.s Nguyễn Phú Trường - 09/2005Trang 235Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0Hình 0-9 Inode của UNIXCơ chế cấp phát lập chỉ mục gặp một số khó khăn về năng lực như cấp phátliên kết. Đặc biệt, các khối chỉ mục có thể được lưu trữ (cache) trong bộ nhớ; nhưngcác khối dữ liệu có thể được trãi rộng khắp phân khu.VI.4 Năng lựcCác phương pháp cấp phát ở trên khác nhau về tính hiệu quả lưu trữ và thờigian truy xuất khối dữ liệu. Cả hai yếu tố này là tiêu chuẩn quan trọng trong việc chọnphương pháp hợp lý hay các phương pháp cho một hệ điều hành cài đặt.Trước khi chọn một phương pháp, chúng ta cần xác định hệ thống sẽ được dùng nhưthế nào. Một hệ thống với hầu hết truy xuất tuần tự nên dùng một phương pháp kháctừ hệ thống với hầu hết truy xuất ngẫu nhiên. Đối với bất cứ loại truy xuất nào, cấpphát kề yêu cầu chỉ một truy xuất để đạt được một khối đĩa. Vì chúng ta có thể giữ dễdàng địa chỉ khởi đầu của tập tin trong bộ nhớ, chúng ta có thể tính lập tức địa chỉ đĩacủa khối thứ i (hay khối kế tiếp) và đọc nó trực tiếp.Đối với cấp phát liên kết, chúng ta cũng có thể giữ địa chỉ khối kế tiếp trongbộ nhớ và đọc nó trực tiếp. Phương pháp này là tốt cho truy xuất tuần tự; tuy nhiên,đối với truy xuất trực tiếp một truy xuất tới khối thứ i phải yêu cầu đọc I đĩa. Vấn đềnày minh hoạ lý do cấp phát liên kết không được dùng cho một ứng dụng yêu cầu truyxuất trực tiếp.Do đó, một số hệ thống hỗ trợ các tập tin truy xuất trực tiếp bằng cách dùngcấp phát kề và truy xuất tuần tự bởi cấp phát liên kết. Đối với các hệ thống này, loạitruy xuất được thực hiện phải được khai báo khi tập tin được tạo. Một tập tin được tạocho truy xuất tuần tự sẽ được liên kết và không thể được dùng cho truy xuất trực tiếp.Một tập tin được tạo cho truy xuất trực tiếp sẽ kề nhau và có thể hỗ trợ cả hai truyxuất trực tiếp và truy xuất tuần tự nhưng chiều dài tối đa của nó phải được khai báoBiên soạn: Th.s Nguyễn Phú Trường - 09/2005Trang 236Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0khi nó được tạo. Trong trường hợp này, hệ điều hành phải có cấu trúc dữ liệu hợp lývà các giải thuật để hỗ trợ cả hai phương pháp cấp phát. Các tập tin có thể đượcchuyển từ một kiểu này sang một kiểu khác bằng cách tạo một tập tin mới của loạimong muốn và các nội dung của tập tin cũ được chép vào tập tin mới. Sau đó, tập tincũ có thể bị xoá và tập tin mới được đổi tên.Cấp phát dạng chỉ mục phức tạp hơn. Nếu khối chỉ mục đã ở trong bộ nhớ rồithì truy xuất có thể được thực hiện trực tiếp. Tuy nhiên, giữ khối chỉ mục trong bộnhớ yêu cầu không gian có thể xem xét. Nếu không gian bộ nhớ này không sẳn dùngthì chúng ta phải đọc trước khối chỉ mục và sau đó khối dữ liệu mong muốn. Đối vớichỉ mục hai cấp, đọc hai khối chỉ mục là cần thiết. Đối với tập tin rất lớn, truy xuấtmột khối gần cuối tập tin yêu cầu đọc tất cả khối chỉ mục để lần theo chuỗi con trỏtrước khi khối dữ liệu được yêu cầu cuối cùng được đọc. Do đó, năng lực của cấp phátchỉ mục phụ thuộc cấu trúc chỉ mục trên kích thước tập tin và vị trí của khối mongmuốn.Một số hệ thống kết hợp cấp phát kề và cấp phát chỉ mục bằng cách dùng cấpphát kề cho các tập tin nhỏ (ba hay bốn khối) và tự động chuyển tới cấp phát chỉ mụcnếu tập tin lớn lên. Vì hầu hết các tập tin là nhỏ và cấp phát kề là hiệu quả cho các tậptin nhỏ, năng lực trung bình là rất tốt.Nhiều tối ưu khác là có thể và đang được dùng. Với sự chênh lệch tốc độ giữaCPU và đĩa, nó là không hợp lý để thêm hàng ngàn chỉ thị tới hệ điều hành để tiếtkiệm chỉ một vài di chuyển của đầu đọc. Ngoài ra, sự chênh lệch này tăng theo thờigian, tới điểm nơi mà hàng trăm của hàng ngàn chỉ thị phù hợp có thể được dùng đểtối ưu sự di chuyển của đầu đọc.VII Quản lý không gian trốngVì không gian trống là giới hạn nên chúng ta cần dùng lại không gian từ các tậptin bị xoá cho các tập tin mới nếu có thể. Để giữ vết của không gian đĩa trống, hệthống duy trì một danh sách không gian trống. Danh sách không gian trống ghi lại tấtcả khối đĩa trống. Để tạo tập tin, chúng ta tìm trong danh sách không gian trống lượngkhông gian được yêu cầu và cấp phát không gian đó tới tập tin mới. Sau đó, khônggian này được xoá từ danh sách không gian trống. Khi một tập tin bị xoá, không gianđĩa của nó được thêm vào danh sách không gian trống. Mặc dù tên của nó là danhsách nhưng danh sách không gian trống có thể không được cài như một danh sách.VII.1 Bit vectorThường thì danh sách không gian trống được cài đặt như một bản đồ bit (bitmap) hay một vector bit (bit vector). Mỗi khối được biểu diễn bởi 1 bit. Nếu khối làtrống, bit của nó được đặt là 1, nếu khối được cấp phát bit của nó được đặt là 0.Thí dụ, xét một đĩa khi các khối 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26, và 27 làtrống và các khối còn lại được cấp phát. Bản đồ bit không gian trống sẽ là:001111001111110001100000011100000…Lợi điểm chính của tiếp cận này là tính tương đối đơn giản và hiệu quả của nótrong việc tìm khối trống đầu tiên, hay n khối trống tiếp theo trên đĩa.Một lần nữa, chúng ta thấy các đặc điểm phần cứng định hướng chức năngphần mềm. Tuy nhiên, các vector bit là không đủ trừ khi toàn bộ vector được giữtrong bộ nhớ chính. Giữ nó trong bộ nhớ chính là có thể cho các đĩa nhỏ hơn, như trêncác máy vi tính nhưng không thể cho các máy lớn hơn. Một đĩa 1.3 GB với khối 512Biên soạn: Th.s Nguyễn Phú Trường - 09/2005Trang 237Đại Học Cần Thơ - Khoa Công Nghệ Thông Tin - Giáo Trình Hệ Điều Hành – V1.0bytes sẽ cần một bản đồ bit 332 KB để ghi lại các khối trống. Gom bốn khối vào mộtnhóm có thể giảm số này xuống còn 83 KB trên đĩa.VII.2 Danh sách liên kếtHình 0-10 danh sách không gian trống được liên kết trên đĩaMột tiếp cận khác để quản lý bộ nhớ trống là liên kết tất cả khối trống, giữ mộtcon trỏ tới khối trống đầu tiên trong một vị trí đặc biệt trên đĩa và lưu nó trong bộnhớ. Khối đầu tiên này chứa con trỏ chỉ tới khối đĩa trống tiếp theo,..Trong thí dụ trên,chúng ta có thể giữ một con trỏ chỉ tới khối 2 như là khối trống đầu tiên. Khối 2 sẽchứa một con trỏ chỉ tới khối 3, khối này sẽ chỉ tới khối 4,…(như hình X-10). Tuynhiên, cơ chế này không hiệu quả để duyệt danh sách, chúng ta phải đọc mỗi khối,yêu cầu thời gian nhập/xuất đáng kể. Tuy nhiên, duyệt danh sách trống không là hoạtđộng thường xuyên. Thường thì, hệ điều hành cần một khối trống để mà nó có thể cấpphát khối đó tới một tập tin, vì thế khối đầu tiên trong danh sách trống được dùng.Phương pháp FAT kết hợp với đếm khối trống thành cấu trúc dữ liệu cấp phát.VII.3 NhómThay đổi tiếp cận danh sách trống để lưu địa chỉ của n khối trống trong khốitrống đầu tiên. n-1 khối đầu tiên này thật sự là khối trống. Khối cuối cùng chứa địachỉ của n khối trống khác, …Sự quan trọng của việc cài đặt này là địa chỉ của một sốlượng lớn khối trống có thể được tìm thấy nhanh chóng, không giống như trong tiếpcận danh sách liên kết chuẩn.VII.4 Bộ đếmMột tiếp cận khác đạt được lợi điểm trong thực tế là nhiều khối kề có thể đượccấp phát và giải phóng cùng lúc, đặc biệt khi không gian được cấp phát với giải thuậtcấp phát kề hay thông qua nhóm. Do đó, thay vì giữ một danh sách n địa chỉ đĩa trống,chúng ta có thể giữ địa chỉ của khối trống đầu tiên và số n khối kề trống theo sau khốiđầu tiên. Mỗi mục từ trong danh sách không gian trống sau đó chứa một địa chỉ đĩa vàbộ đếm. Mặc dù mỗi mục từ yêu cầu nhiều không gian hơn một địa chỉ đĩa đơn,nhưng toàn bộ danh sách sẽ ngắn hơn với điều kiện là bộ đếm lớn hơn 1.Biên soạn: Th.s Nguyễn Phú Trường - 09/2005Trang 238

Xem Thêm

Tài liệu liên quan

• HỆ ĐIỀU HÀNH - NGUYỄN PHÚ TRƯỜNG docx
  • 238
  • 1,847
  • 17
• CLB Bellydance Biên Hòa Uy tín
  • 4
  • 0
  • 0
• CLB Bellydance Đà Nẵng Bảo đảm
  • 4
  • 0
  • 0
• CLB Bellydance Đà Nẵng Cá nhân
  • 4
  • 0
  • 0
• CLB Bellydance Đà Nẵng Chất lượng cao
  • 4
  • 0
  • 0
• CLB Bellydance Đà Nẵng Chuyên nghiệp
  • 4
  • 0
  • 0
• CLB Bellydance Đà Nẵng Doanh Nghiệp
  • 4
  • 0
  • 0
• CLB Bellydance Đà Nẵng Độc đáo
  • 4
  • 0
  • 0
• CLB Bellydance Đà Nẵng Giá rẻ
  • 4
  • 0
  • 0
• CLB Bellydance Đà Nẵng Lâu dài
  • 4
  • 0
  • 0
• CLB Bellydance Đà Nẵng Mới lạ
  • 4
  • 0
  • 0

Tải bản đầy đủ (.pdf) (238 trang)

Tài liệu bạn tìm kiếm đã sẵn sàng tải về

(3.99 MB) - HỆ ĐIỀU HÀNH - NGUYỄN PHÚ TRƯỜNG docx-238 (trang) Tải bản đầy đủ ngay ×