Bài thuyết trình Các thuật toán đọc đĩa - Bùi Mạnh Quân

Kính Chaøo Thaày Vaø caùc Baïn ñeán vôùi baøi thuyeát trình cuûa Nhoùm 6 Caùc Thaønh Vieân Cuûa Nhoùm :Buøi Maïnh QuaânBuøi Duy QuangNguyeãn Vaên MinhNguyeãn Thò Ngoïc ThöôngCHỦ ĐỀ 3 :CÁC THUẬT TOÁN ĐỌC ĐĨANoäi Dung Tìm Hieåu Khái niệmCác thuật toán đọc đĩaLựa chọn thuật toán lập lịch1) Khaùi nieämXâ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 TieátTốc độ đĩa gồm 3 phần: Seek time, Latency time, Transfer timeSeek 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ểnLatency time: Thời gian chờ cho khối cần thiết dưới đầu đọcTransfer time: Thời gian vận chuyển dữ liệu giữa đĩa và bộ nhớ chínhII)Caùc thuaät toaùn ñoïc ÑóaFirst come first served (FCFS)Shortest seek time first (SSTF)ScanC-ScanLookC-Look1) 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ướcTruy 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ố 83Các khối cần đọc: 27, 55, 152, 8, 56, 18, 95, 24, 35, 6Số 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ấtRất dễ lập trìnhCác track được truy xuất liên tụcNhược điểm:Đầu đọc phải dịch chuyển nhiều khi đọcHiệu quả của thuật toán phụ thuộc vào các track2) 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ướcNhu 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 FCFSSố track mà đầu đọc dịch chuyển giảmNhượ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ố 83Các khối cần đọc: 27, 55, 152, 8, 56, 18, 95, 24, 35, 6Số bước dịch chuyển: 247 6 8 18 24 27 35 55 56 83 95 1523) ScanCá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 đọcSau đó, di chuyển ngược lạiCòn gọi là thuật toán thang máyCách đọc đĩa của thuật toán SCanĐầu đọc hiện tại ở vị trí số 83Các khối cần đọc: 27, 55, 152, 8, 56, 18, 95, 24, 35, 6Số bước dịch chuyển: 237 6 8 18 24 27 35 55 56 83 95 1524) C-ScanCách đọc:Đọc tương tự như thuật toán ScanChỉ 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 đầuQuét 1 chiều: Khi quay về, đầu đọc không thực hiện yêu cầu nàoCách đọc đĩa của thuật toán C-ScanĐầu đọc hiện tại ở vị trí số 83Các khối cần đọc: 27, 55, 152, 8, 56, 18, 95, 24, 35, 6Số bước dịch chuyển: 133 6 8 18 24 27 35 55 56 83 95 1525) LookCá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ốiThuật toán thực tế của ScanCách đọc đĩa của thuật toán LookĐầu đọc hiện tại ở vị trí số 83Các khối cần đọc: 27, 55, 152, 8, 56, 18, 95, 24, 35, 6Số bước dịch chuyển: 215 6 8 18 24 27 35 55 56 83 95 1526) C-LookCá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ấtCách đọc đĩa của thuật toán C-LookĐầu đọc hiện tại ở vị trí số 83Các khối cần đọc: 27, 55, 152, 8, 56, 18, 95, 24, 35, 6Số bước dịch chuyển: 119 6 8 18 24 27 35 55 56 83 95 152III) Löïa Choïn Thuaät Toaùn Ñoïc Ñóa thích hôïpFCFS được sử dụng khi số khối cần truy xuất liên tụcSSTF tuy thông thương nhưng rất phổ biến và có hiệu quả tốtScan 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ớnLook là thuật toán rất thực tế của ScanC-Look khắc phục một đoạn đường dài cho C-SCanThành Viên1165067: Nguyễn Văn Minh1165090: Bùi Mạnh Quân1165093: Bùi Duy Quang1165127: Nguyễn Thị Ngọc ThươngGiaûi Ñaùp Thaéc Maéc ???Nhoùm xin chaân thaønh Caûm Ôn Thaày Vaø caùc baïn ñaõ theo doõi !