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

Kính Chào Thầy Và các Bạn đến với bài thuyết trình của Nhóm 6
Các Thành Viên Của Nhóm :
Bùi Mạnh Quân
Bùi Duy Quang
Nguyễn Văn Minh
Nguyễn Thị Ngọc Thương
CHỦ ĐỀ 3 :
CÁC THUẬT TOÁN ĐỌC ĐĨA
Nội Dung Tìm Hiểu
Khái niệm
Các thuật toán đọc đĩa
Lựa chọn thuật toán lập lịch
1) Khaùi nieäm
Xây dựng thuật toán dịch chuyển đầu đọc ghi sao cho thời gian truy cập là tôi ưu nhất.
Giúp tổ chức truy xuất đĩa một cách tốt hơn.
Bao gồm:
Nạp chương trình
Nhập xuất tập tin.
2) Chi Tiết
Tốc độ đĩa gồm 3 phần: Seek time, Latency time, Transfer time
Seek Time: Di chuyển đầu đọc đến cylinder hoặc track thích hợp + Thời gian hoàn tất việc di chuyển
Latency time: Thời gian chờ cho khối cần thiết dưới đầu đọc
Transfer time: Thời gian vận chuyển dữ liệu giữa đĩa và bộ nhớ chính
II)Caùc thuaät toaùn ñoïc Ñóa
First come first served (FCFS)
Shortest seek time first (SSTF)
Scan
C-Scan
Look
C-Look
1) First come first served (FCFS)

Cách đọc:
Để truy nhập 1 file (tập tin), hệ thống sẽ tổ chức 1 hàng đợi
Đọc lần lượt các khối theo thứ tự tuần tự
Track nào có yêu cầu phục vụ trước, đầu đọc ghi dịch chuyển đến đó trước
Truy cập tuần tự
Cách đọc đĩa của thuật toán FCFS
Đầu đọc hiện tại ở vị trí số 83
Các khối cần đọc: 27, 55, 152, 8, 56, 18, 95, 24, 35, 6
Số bước dịch chuyển: 599
6 8 18 24 27 35 55 56 83 95 152
Ưu điểm và nhược điểm
Ưu điểm:
Là phương pháp lập lịch đơn giản nhất
Rất dễ lập trình
Các track được truy xuất liên tục
Nhược điểm:
Đầu đọc phải dịch chuyển nhiều khi đọc
Hiệu quả của thuật toán phụ thuộc vào các track
2) Shortest seek time firt (SSTF)
Cách đọc:
Track nào có thời gian dịch chuyển đầu đọc ghi ngắn nhất thì được phục vụ trước
Nhu cầu gần với vị trí hiện hành nhất
Ưu điểm, nhược điểm
Ưu điểm:
Loại bỏ được nhược điểm của thuật toán đọc đĩa FCFS
Số track mà đầu đọc dịch chuyển giảm
Nhược điểm:
Gấy ra một số yêu cầu có thể không bao giờ được phục vụ
Cách đọc đĩa của thuật toán SSTF
Đầu đọc hiện tại ở vị trí số 83
Các khối cần đọc: 27, 55, 152, 8, 56, 18, 95, 24, 35, 6
Số bước dịch chuyển: 247
6 8 18 24 27 35 55 56 83 95 152
3) Scan
Cách đọc:
Di chuyển đầu đọc về một phía của đĩa đến vị trí cuối (bên ngoài hoặc bên trong đĩa) để phục vụ yêu cầu đọc
Sau đó, di chuyển ngược lại
Còn gọi là thuật toán thang máy
Cách đọc đĩa của thuật toán SCan
Đầu đọc hiện tại ở vị trí số 83
Các khối cần đọc: 27, 55, 152, 8, 56, 18, 95, 24, 35, 6
Số bước dịch chuyển: 237
6 8 18 24 27 35 55 56 83 95 152
4) C-Scan
Cách đọc:
Đọc tương tự như thuật toán Scan
Chỉ khác là khi di chuyển đến đầu nào đó của đĩa, lập tức sẽ trở về vị trí bắt đầu
Quét 1 chiều: Khi quay về, đầu đọc không thực hiện yêu cầu nào
Cách đọc đĩa của thuật toán C-Scan
Đầu đọc hiện tại ở vị trí số 83
Các khối cần đọc: 27, 55, 152, 8, 56, 18, 95, 24, 35, 6
Số bước dịch chuyển: 133
6 8 18 24 27 35 55 56 83 95 152
5) Look
Cách đọc:
Tương tự thuật toán Scan nhưng đầu đọc ghi di chuyển đến khồi xa nhất chứ không đến cuối
Thuật toán thực tế của Scan
Cách đọc đĩa của thuật toán Look
Đầu đọc hiện tại ở vị trí số 83
Các khối cần đọc: 27, 55, 152, 8, 56, 18, 95, 24, 35, 6
Số bước dịch chuyển: 215
6 8 18 24 27 35 55 56 83 95 152
6) C-Look
Cách đọc:
Tương tự như Look nhưng không phục vụ đường về
Cũng đọc tương tự như C-Scan, nhưng chỉ đọc tới khối cuối cùng, không đọc tới khối xa nhất
Cách đọc đĩa của thuật toán C-Look
Đầu đọc hiện tại ở vị trí số 83
Các khối cần đọc: 27, 55, 152, 8, 56, 18, 95, 24, 35, 6
Số bước dịch chuyển: 119
6 8 18 24 27 35 55 56 83 95 152
III) Lựa Chọn Thuật Toán Đọc Đĩa thích hợp
FCFS được sử dụng khi số khối cần truy xuất liên tục
SSTF tuy thông thương nhưng rất phổ biến và có hiệu quả tốt
Scan va C-Scan thích hợp với nhưng hệ thông truy xuất dữ liệu khối lương lớn
Look là thuật toán rất thực tế của Scan
C-Look khắc phục một đoạn đường dài cho C-SCan
Thành Viên
1165067: Nguyễn Văn Minh
1165090: Bùi Mạnh Quân
1165093: Bùi Duy Quang
1165127: Nguyễn Thị Ngọc Thương
Giải Đáp Thắc Mắc ???
Nhóm xin chân thành Cảm Ơn Thầy Và các bạn đã theo dõi !