Bài giảng Tin học - Lập Lịch Cho Đĩa

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ịchI.Khái niệm về lập lịch cho đĩaLậ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ấtThờ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 đĩaFirst come first Served(FCFS)Shortest seek time first(SSTF)ScanC-ScanLookC-Look1.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ướcVí dụ:File F1 được phân bổ lần lượt các track số thứ tự :98,183,37,122,14,124,65,67giả sử đầu đọc đang ở track 53Sơ đồ dịch chuyển theo FCFS(640 bước dịch chuyển)Ưu,nhược điểm1-Ưu điểm:+)Dễ lập trình+)Các track cần truy xuất là liên tục2-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 FirstNộ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ướcVí dụ:File F1 được phân bổ lần lượt các track số thứ tự :98,183,37,122,14,124,65,67giả sử đầu đọc đang ở track 53Sơ đồ dịch chuyển theo SSTF(Tổng quãng đường dịch chuyển là 360)Ưu, nhược điểm SSTF1-Ưu điểmSố track mà đầu đọc phải đi chuyển giảm2-nhược điểmCó thể gây ra 1 số yêu cầu không bao giờ được phục vụ3-ScanNộ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ạiVí dụ:File F1 được phân bổ lần lượt các track số thứ tự :98,183,37,122,14,124,65,67giả sử đầu đọc đang ở track 53Tổ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ảm4.C-ScanNộ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,67giả sử đầu đọc đang ở track 53Số bước dịch chuyển của đầu từ 2525-LookNộ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ùngVí dụ:File F1 được phân bổ lần lượt các track số thứ tự :98,183,37,122,14,124,65,67giả sử đầu đọc đang ở track 53Số bước dịch chuyển của đầu từ 2086.C-LookNộ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,67giả sử đầu đọc đang ở track 53Lựa chọn một giải thuật lập lịch đĩaFCFS là thuật toán phù hợp khi các track cần truy xuất là liên tụcSSTF 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