III. Các Phương Pháp Cấp Phát Không Gian Nhớ Tự Do - Tài Liệu Text

1. Trang chủ >
2. Công nghệ thông tin >
3. Hệ thống thông tin >

III. Các phương pháp cấp phát không gian nhớ tự do

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 (755.65 KB, 19 trang )

Quản lý bộ nhớ ngoài trong HĐH Linux+ Có thể xảy ra trường hợp không đủ số khối đĩa tự do liên tiếp cần thiết để cấpphát cho file (kích thước file lớn hơn vùng các khối đĩa liên tục lớn nhất).+ Trong trường hợp các khối đĩa tự do nằm tản mạn sẽ không sử dụng được, gâylãng phí không gian nhớ.Các thuật toán tối ưu:+ First fit. Cấp phát hole đầu tiên cái mà đủ lớn. Việc tìm kiếm có thể bắt đầu hoặctừ đầu tập hole hoặc nơi mà tim kiếm firstfit trước đã kết thúc. Chúng ta có thể dừng việctìm kiếm ngay khi chúng ta tìm thấy một hole tự do đủ lớn.+ Best fit. Cấp phát hole nhỏ nhất cái mà đủ lớn. Chúng ta phải tìm kiếm toàn bộdanh sách đó, trừ khi danh sách đó được sắp sếp theo kích cỡ. Chiến lược này tạo ra mộthole dưa thừa nhỏ nhất.+ Worst fit. Cấp phát hole lớn nhất. Ngược lại, chúng ta phải tìm kiếm toàn bộdanh sách trừ khi nó được sắp xếp theo kích thước. Chiến lược này tạo ra một hole dưathừa lớn nhất, cái mà có thể hữu ích hơn nhiều so với hole dưa thừa nhỏ hơn từ tiếp cậnbestfit.Những mô phỏng vừa trình bày thì cả first fit và best fit là tốt hơn worst fit trongviệc giảm thời gian và tận dụng lưu trữ.2) Cấp phát liên kết (Linked)Trong phương pháp này, mỗi file được định vị trong thư mục thiết bị bằng hai contrỏ, một cái trỏ tới khối đĩa đầu tiên, một cái trỏ tới khối đĩa cuối cùng để cấp phát chofile. Trong mỗi khối đĩa đã cấp phát cũng có một con trỏ để trỏ tới khối đĩa kế tiếp.Ví dụ:File F1 được cấp phát 5 khối đĩa có số hiệu 9, 16, 1, 11, 25; khối đầu là 9, khối cuốilà 25.9Quản lý bộ nhớ ngoài trong HĐH Linux- Ưu điểm:+ Sử dụng được các khối đĩa tự do nằm tản mạn.- Nhược điểm:+ Chỉ hỗ trợ truy nhập tuần tự không hỗ trợ truy nhập trực tiếp, độ tin cậy khôngđảm bảo nếu bị mất các con trỏ liên3) Cấp phát theo chỉ số (Index)Trong phương pháp này, để cấp phát không gian nhớ cho một file, hệ thống sửdụng một khối đĩa đặc biệt gọi là khối địa chỉ số (index block) cho mỗi file. Trong khốiđĩa chỉ số chứa địa chỉ của các khối đĩa đã cấp phát cho file, trong thư mục thiết bị địa chỉcủa các khối đĩa chỉ số. Khi một khối đĩa được cấp phát cho file thì hệ thống loại bỏ địachỉ của khối này khỏi danh sách các khối đĩa tự do và cập nhật vào khối chỉ số của file.10Quản lý bộ nhớ ngoài trong HĐH Linux- Ưu điểm:+ Hỗ trợ truy nhập trực tiếp.- Nhược điểm:+ Lãng phí không gian nhớ dành cho khối địa chỉ số.11Quản lý bộ nhớ ngoài trong HĐH LinuxIV. Lập lịch cho đĩa (Disk-scheduling)1) Khái niệm Disk-scheduling- Thời gian truy nhập đĩa phụ thuộc ba yếu tố:+ Thời gian di chuyển đầu từ đọc ghi đến track or cylinder cần thiết (Seek time)+ Thời gian định vị đầu từ đọc/ghi tại khối đĩa cần truy nhập (Latency-time)+ Thời gian truy nhập dữ liệu (Transfer-time)Mà Seek-time và Transfer-time thường cố định và phụ thuộc vào cấu trúc kỹ thuậtcủa ổ đĩa nên hệ điều hành quan tâm đến Latency-time khi muốn tăng tốc độ truy nhậpđĩa.- Như vậy chúng ta có thể định nghĩa rằng:+ Lập lịch cho đĩa là xây dựng các thuật toán dịch chuyển đầu từ đọc/ghi sao chothời gian truy nhập đĩa là tối ưu nhất.2) Một số phương pháp lập lịcha) First come first served (FCFS)Để truy nhập tới 1 file, hệ thống sẽ tổ chức một hàng đợi các yêu cầu phục vụ cáctrack (lưu trữ dữ liệu của file cần truy nhập). Track nào có yều cầu phục vụ trước thì đầutừ đọc ghi sẽ dịch chuyển tới đó trước.VD: File F1 được phân bổ lần lượt tại các track có số thứ tự sau đây: 98, 183, 37,122, 14, 124, 65, 67. Đầu từ đọc/ghi đang dịnh vị tại track có số thứ tự 53 thì sơ đồ dịchchuyển đầu từ đọc ghi theo thuật toán FCFS được thể hiện như sau:53 - 98 - 183 - 37 - 122 - 14 - 124 - 65 - 67b) Shortest Seek Time First (SSTF)- Thuật toán SSTF sẽ chọn track nào có thời gian di chuyển đầu từ đọc ghi ngắnnhất thì ưu tiên phục vụ track đó trước. VD:53 - 65 - 67 - 37 - 14 - 98 - 122 - 124 - 183c) Thuật toán Scan- Trong thuật toán này đầu từ đọc/ghi quét từ track nhỏ nhất đến track lớn nhất sauđó quét ngược lại, track nào có nhu cầu thì phục vụ.12Quản lý bộ nhớ ngoài trong HĐH Linuxd) Thuật toán C-Scan- Thuật toán này tương tự như scan nhưng không quét chiều ngược lại.e) Thuật toán Look- Tương tự như thuật toán Scan nhưng trong thuật toán này đầu từ đọc/ghi chỉ quéttrong phạm vi các track có yêu cầu phục vụ, không quét tới track đầu tiên hoặc cuối cùng(nếu các track này không có nhu cầu phục vụ).f) Thuật toán C-Look- Tương tự như Look nhưng đầu từ đọc/ghi không phục vụ đường về.Lưu ý: Thuật toán FCFS và SSFT là 2 thuật toán đang được sử dụng rất phổbiến.13

Xem Thêm

Tài liệu liên quan

• nghiên cứu tìm hiểu về bộ nhớ ngoài trong hệ điều hành linux
  • 19
  • 7,407
  • 31
• Thực trạng kế toán hoạt động nhập khẩu hàng hoá tại Công ty XNK và XD Nông Lâm Nghiệp.Doc
  • 69
  • 0
  • 0
• Thực trạng kế toán nguyên vật liệu tại Xí nghiệp than Cao Thắng.doc
  • 39
  • 452
  • 1

Tải bản đầy đủ (.doc) (19 trang)

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

(713.5 KB) - nghiên cứu tìm hiểu về bộ nhớ ngoài trong hệ điều hành linux-19 (trang) Tải bản đầy đủ ngay ×