LẬP LỊCH CHO ĐĨA
1>Khái niệm Lập lịch

2>Các thuật toán lập lịch
I.Khái niệm về lập lịch cho đĩa
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 cho thời gian truy nhập đĩa là tối ưu nhất
Thời gian truy nhập đĩa


Thời gian di chuyển đầu từ đọc ghi đến strack thích hợp(seek-time)

Thời gian chờ cho khối cần thiết dưới đầu đọc(latency -time)

Thời gian vận chuyển dữ liệu giữa đĩa và bộ nhớ chính(transfer-time)

II.Các thuật toán lập lịch cho đĩa
First come first Served(FCFS)
Shortest seek time first(SSTF)
Scan
C-Scan
Look
C-Look
1.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ủa các track(lưu trữ dữ liệu của file cần truy nhập)
Nội dung:track nào có yêu cầu phục vụ trước thì đầu đọc ghi sẽ dịch chuyển tới đó trước
Ví dụ:File F1 được phân bổ lần lượt các track số thứ tự :98,183,37,122,14,124,65,67
giả sử đầu đọc đang ở track 53
Sơ đồ dịch chuyển theo FCFS(640 bước dịch chuyển)
Ưu,nhược điểm
1-Ưu điểm:
+)Dễ lập trình
+)Các track cần truy xuất là liên tục
2-Nhược điểm
+)Số track mà đầu đọc phải di chuyển là nhiều
+)Hiệu quả của thuật toán phụ thuộc vào thứ tự của các track trong hàng đợi

2-Shortest Seek time First
Nội dung: track nào có thời gian di chuyển đầu từ đọc ghi ngắn nhất thì phục vụ trước
Ví dụ:File F1 được phân bổ lần lượt các track số thứ tự :98,183,37,122,14,124,65,67
giả sử đầu đọc đang ở track 53
Sơ đồ dịch chuyển theo SSTF(Tổng quãng đường dịch chuyển là 360)
Ưu, nhược điểm SSTF
1-Ưu điểm
Số track mà đầu đọc phải đi chuyển giảm
2-nhược điểm
Có thể gây ra 1 số yêu cầu không bao giờ được phục vụ



3-Scan
Nội dung:Đầu đọc của đĩa di chuyển từ một phía (ví dụ bên ngoài hoặc bên trong đĩa) sang phía kia để phục vụ các yêu cầu đọc, sau đó di chuyển ngược lại... quá trình này lặp đi lặp lại
Ví dụ:File F1 được phân bổ lần lượt các track số thứ tự :98,183,37,122,14,124,65,67
giả sử đầu đọc đang ở track 53
Tổng quãng đường dịch chuyển là 252
Đặc điểm

Phương thức h/đ như thang máy


Số bước đầu đọc phải di chuyển giảm

4.C-Scan
Nội dung: Đầu đọc chuyển từ một phía (trong/ngoài)sang phía kia và phục vụ các yêu cầu. Khi sang đến phía kia, đầu đọc quay trở lại nhưng trong khi quay trở lại không phục vụ yêu cầu nào.(quét 1 chiều)
Ví dụ:File F1 được phân bổ lần lượt các track số thứ tự :98,183,37,122,14,124,65,67
giả sử đầu đọc đang ở track 53
Số bước dịch chuyển của đầu từ 252
5-Look
Nội dung:tương tự như Scan nhưng trong thuật toán này đầu đọc ghi chỉ quét trong phạm vi các track có nhu cầu phục vụ không quét tới track đầu tiên hoặc cuối cùng
Ví dụ:File F1 được phân bổ lần lượt các track số thứ tự :98,183,37,122,14,124,65,67
giả sử đầu đọc đang ở track 53
Số bước dịch chuyển của đầu từ 208
6.C-Look
Nội dung:Tương tự như Look nhưng đầu đọc ghi không phục vụ đường về
Ví dụ:File F1 được phân bổ lần lượt các track số thứ tự :98,183,37,122,14,124,65,67
giả sử đầu đọc đang ở track 53
Lựa chọn một giải thuật lập lịch đĩa
FCFS là thuật toán phù hợp khi các track cần truy xuất là liên tục
SSTF phổ biến và có hiệu quả tốt.
SCAN và LOOK thích hợp cho những hệ thống phải truy xuất dữ liệu lớn