Các thuật toán đọc đĩa

Tất cả mọi công việc đều phụ thuộc vào việc nạp chương trình và nhập xuất tập tin, do đ� điều quan trọng là dịch vụ đĩa phải càng nhanh càng tốt. Hệ điều hành có thể tổ chức dịch vụ truy xuất đĩa tốt hơn bằng cách lập lịch yêu cầu truy xuất đĩa.

Tốc độ đĩa bao gồm ba phần. Để truy xuất c�c khối trên đĩa, trước tiên phải di chuyển đầu đọc đến track hay cylinder th�ch hợp, thao t�c này gọi là seek và thời gian để hoàn tất gọi là seek time. Một khiđã đến đ�ng track, còn phải chờ cho đến khi khối cần thiết đến dưới đầu đọc. Thời gian chờ này gọi là latency time. Cuối cùng là vận chuyển dữ liệu giữa đĩa và bộ nhớ chính gọi là transfer time. Tổng thời gian cho dịch vụ đĩa ch�nh là tổng của ba khoảng thời gian trên. Trong đ� seek time và latency time là mất nhiều thời gian nhất, do đ� để giảm thiểu thời gian truy xuất hệ điều hành đưa ra các thuật toán lập lịch truy xuất.

 Lập lịch FCFS :

Phương pháp lập lịch đơn giản nhất là FCFS(first-come,first-served). Thuật toán này rất dể lập trình nhưng không cung cấp được một dịch vụ tốt. Ví dụ : cần phải đọc c�c khối theo thứ tự như sau :

98, 183, 37, 122, 14, 124, 65, và 67

Giả sử hiện tại đầu đọc đang ở vị tr� 53. Như vậy đầu đọc lần lượt đi qua c�c khối 53, 98, 183, 37, 122, 14, 124, 65, và 67 như hình sau :

 Lập lịch SSTF (shortest-seek-time-first)

Thuật toán này sẽ di chuyển đầu đọc đến c�c khối cần thiết theo vị tr� lần lượt gần với vị trí hiện hành của đầu đọc nhất. V� dụ : cần đọc c�c khối như sau : 

98, 183, 37, 122, 14, 124, 65, và 67

Giả sử hiện tại đầu đọc đang ở vị tr� 53. Như vậy đầu đọc lần lượt đi qua c�c khối 53, 65, 67, 37, 14, 98, 122, 124 và 183 như hình sau :

Với ví dụ này, thuật toán SSTF làm giảm số khối mà đầu đọc phải di chuyển là 208 khối.

 Lập lịch SCAN

Theo thuật toán này, đầu đọc sẽ di chuyển về một phía của đĩa và từ đ� di chuyển qua ph�a kia. V� dụ : cần đọc c�c khối như sau : 

98, 183, 37, 122, 14, 124, 65, và 67

Giả sử hiện tại đầu đọc đang ở vị tr� 53. Như vậy đầu đọc lần lượt đi qua c�c khối 53, 37, 14, 0 , 65, 67, 98, 122, 124 và 183 như hình sau :

Thuật toán này còn được gọi là thuật toán thang máy. Hình ảnh thuật toán giống như hình ảnh của một người quét tuyết, hay quét lá.

 Lập lịch C-SCAN

Thuật toán này tương tự như thuật toán SCAN, chỉ khác là khi nó di chuyển đến một đầu nào đ� của đĩa, n� sẽ lập tức trở về đầu bắt đầu của đĩa. Lấy lại v� dụ trên, khi đ� thứ tự truy xuất c�c khối sẽ là : 53, 65, 67, 98, 122, 124, 183, 199, 0, 14, 37 như hình sau :

 Lập lịch LOOK:

Nhận xét rằng cả hai thuật toán lập lịch SCAN và C-SCAN luôn luôn chuyển đầu đọc của đĩa từ đầu này sang đầu kia. Nhưng thông thường thì đầu đọc chỉ chuyển đến khối xa nhất ở mỗi hướng chứ không đến cuối. Do đ� SCAN và C-SCAN được chỉnh theo thực tế và gọi là lập lịch LOOK. Như hình sau :

 Lựa chọn thuật toán lập lịch :

Với những thuật toán lập lịch, vấn đề là phải lựa chọn thuật toán nào cho hệ thống. Thuật toán SSTF thì rất thông thường. Thuật toán SCAN và C-SCAN thích hợp cho những hệ thống phải truy xuất dữ liệu khối lượng lớn. Với bất kỳ thuật toán lập lịch nào, điều quan trọng là khối lượng về số và kiểu khối cần truy xuất. Ví dụ , nếu số khối cần truy xuất là liên tục thì FCFS là thuật toán tốt.