Bài giảng Hệ điều hành - Chương 5: Cấu trúc lưu trữ - Lương Minh Huấn

Nội dung text: Bài giảng Hệ điều hành - Chương 5: Cấu trúc lưu trữ - Lương Minh Huấn

1. TRƯỜNG ĐẠI HỌC SÀI GÒN CHƯƠNG 5: CẤU TRÚC LƯU TRỮ GV: LƯƠNG MINH HUẤN
2. NỘI DUNG I. Bên trong ổ cứng II. Các giải thuật định thời truy cập ổ đĩa III. Định dạng, phân vùng, raw disk IV.Raid
3. I. BÊN TRONG Ổ CỨNG ➢Đĩa cứng trong hệ thống PC
4. ➢ Platters range from .85” to 14” (historically) ▪ Commonly 3.5”, 2.5”, and 1.8” ➢ Range from 30GB to 3TB per drive ➢ Performance ▪ Transfer Rate – theoretical – 6 Gb/sec ▪ Effective Transfer Rate – real – 1Gb/sec ▪ Seek time from 3ms to 12ms – 9ms common for desktop drives ▪ Average seek time measured or calculated based on 1/3 of tracks ▪ Latency based on spindle speed • 1 / (RPM / 60) = 60 / RPM ▪ Average latency = ½ latency
5. CÁC THAM SỐ CỦA ĐĨA ➢Thời gian đọc/ghi dữ liệu trên đĩa bao gồm: ▪ Seek time: thời gian di chuyển đầu đọc để định vị đúng track/cylinder, phụ thuộc tốc độ/cách di chuyển của đầu đọc ▪ Rotational delay (latency): thời gian đầu đọc chờ đến đúng sector cần đọc, phụ thuộc tốc độ quay của đĩa ▪ Transfer time: thời gian chuyển dữ liệu từ đĩa vào bộ nhớ hoặc ngược lại, phụ thuộc băng thông kênh truyền giữa đĩa và bộ nhớ ➢Disk I/O time = seek time + rotational delay + transfer time
6. LOẠI ĐĨA CỨNG MỚI HIỆN NAY ➢Đĩa loại mới phân bố lại mật độ dữ liệu: lưu trữ mật độ Thông tin (bit)/vùng ➢Đĩa chia ra thành vùng có số lượng sectors/vùng khác nhau (ngoài nhiều hơn trong)
7. ĐỊNH DANH ĐĨA (ADDRESS) ➢OS sẽ quản lý ▪ Loại giao tiếp (IDE/SCSI, etc), đĩa nào, số sector . ➢Làm sao xác định tiếp sectors, tracks, etc? ▪ Loại đĩa cũ: xác định bởi cylinder/head/sector (CHS) ▪ Loại đĩa mới: chỉ số “block” luận lý • LBA = logical block address
8. ĐỊNH DANH ĐĨA (ADDRESS) ➢Chỉ số sector được sử dụng như thế nào? ▪ Phần mềm quản lý hệ thống file sẽ chuyển đổi định danh block luận lý sang vật lý tương ứng trên đĩa ▪ Thuật ngữ • Đối với người sử dụng đĩa: “khối” hay “Sector” là như nhau • Đối với người sử dụng hệ thống file: “khối” có dung lượng cố định, gồm 1 hay nhiều “sectors”
9. ĐỊNH DANH VÀ ĐỊNH THỜI Ổ ĐĨA ➢ Mục tiêu của giải thuật định thời đĩa: ▪ Quản lý hàng đợi các yêu cầu truy xuất đĩa ▪ Dịch vụ các yêu cầu hợp lý ▪ Ví dụ: đầu từ dịch đến vị trí gần nhất ➢ Mục tiêu định danh luận lý đĩa ▪ Che dấu phần chuyển đổi vật lý (Track?, Sector? ở đâu trên đĩa) ➢ Vấn đề: ▪ Các hệ điều hành cũ: Quan tâm kỹ đến sắp đặt không gian trên đĩa ▪ Các hệ điều hành mới: Quan tâm đến các sectors liền kề cần được sắp xếp gần nhau ▪ Thực tế: OS vẫn phải quan tâm đến sắp đặt không gian trên đĩa như loại cũ
10. TĂNG HIỆU SUẤT TRUY CẬP ĐĨA ➢ Các giải pháp ▪ Giảm kích thước đĩa ▪ Tăng tốc độ quay của đĩa ▪ Định thời các tác vụ truy xuất đĩa (disk scheduling) để hạn chế di chuyển đầu đọc ▪ Bố trí ghi dữ liệu trên đĩa hợp lý • Các dữ liệu có liên quan nằm trên các track gần nhau • Interleaving ▪ Bố trí các file thường sử dụng vào vị trí thích hợp ▪ Chọn kích thước của logical block ▪ Read ahead
11. ➢Đặc trưng về đáp ứng yêu cầu đĩa (performance mertric) ▪ Thông năng (throughput): số lượng tác vụ hoàn thành trong một đơn vị thời gian. ▪ Disk utilazion: phần thời gian truyền dữ liệu chiếm trong disk I/0 time. ▪ Deadline: thời gian hoàn tất của một yêu cầu. ▪ Thời gian đáp ứng (response time): thời gian từ lúc yêu cầu đến lúc yêu cầu thực hiện xong. ▪ Công bằng (fairness)
12. ➢Các tiêu chí cần tối ưu: ▪ Tối đa thông năng ▪ Tối đa disk utilization ▪ Tối thiểu số lượng các deadline không giữ được. ▪ Tối thiểu thời gian đáp ứng trung bình. ▪ Công bằng với mọi yêu cầu đĩa.
13. II. ĐỊNH THỜI TRUY CẬP ĐĨA ➢Ý tưởng chính ▪ Sắp xếp lại trật tự của các yêu cầu đọc/ghi đĩa sao cho giảm thiểu thời gian di chuyển đầu đọc (seek time) ➢Các giải thuật định thời truy cập đĩa ▪ First Come, First Served (FCFS) ▪ Shortest-Seek-Time First (SSTF) ▪ SCAN ▪ C-SCAN (Circular SCAN) ▪ C-LOOK
14. II. ĐỊNH THỜI TRUY CẬP ĐĨA ➢Ví dụ: định thời chuỗi yêu cầu đọc/ghi đĩa tại ▪ cylinder 98, 183, 37, 122, 14, 124, 65, 67 ▪ Đầu đọc đang ở cylinder số 53
15. FCFS ➢Hàng đợi: 98, 183, 37, 122, 14, 124, 65, 67 ➢Đầu đọc đang ở cylinder số 53
16. SHORTEST-SEEK-TIME FIRST (SSTF)
17. SCAN (ELEVATOR ALGORITHM)
18. C-SCAN (CIRCULAR SCAN)
19. C-LOOK
20. III. ĐỊNH DẠNG – PHÂN VÙNG – RAW DISK ➢ Quản lý đĩa: định dạng (formatting) ➢ Định dạng cấp thấp: định dạng vật lý, chia đĩa thành nhiều sector ▪ Mỗi sector có cấu trúc dữ liệu đặc biệt: header – data – trailer ▪ Header và trailer chứa các thông tin dành riêng cho disk controller như chỉ số sector và error-correcting code (ECC) ▪ Khi controller ghi dữ liệu lên một sector, trường ECC được cập nhật với giá trị được tính dựa trên dữ liệu được ghi ▪ Khi đọc sector, giá trị ECC của dữ liệu được tính lại và so sánh với trị ECC đã lưu để kiểm tra tính đúng đắn của dữ liệu
21. III. ĐỊNH DẠNG – PHÂN VÙNG – RAW DISK ➢Quản lý đĩa: Phân vùng (partitioning) ➢Phân vùng: chia đĩa thành nhiều vùng (partition), mỗi vùng gồm nhiều block liên tục. ▪ Mỗi partition được xem như một “đĩa luận lý” riêng biệt. ➢Định dạng luận lý cho partition: tạo một hệ thống file (FAT, ext2, ) ▪ Lưu các cấu trúc dữ liệu khởi đầu của hệ thống file lên partition ▪ Tạo cấu trúc dữ liệu quản lý không gian trống và không gian đã cấp phát (DOS: FAT, UNIX: inode table)
22. III. ĐỊNH DẠNG – PHÂN VÙNG – RAW DISK ➢Ví dụ định dạng một partition
23. III. ĐỊNH DẠNG – PHÂN VÙNG – RAW DISK ➢Quản lý đĩa: Raw disk ➢Raw disk: partition không có hệ thống file ➢I/O lên raw disk được gọi là raw I/O ▪ đọc hay ghi trực tiếp các block ▪ không dùng các dịch vụ của file system như buffer cache, file locking, prefetching, cấp phát không gian trống, định danh file, và thư mục ➢Ví dụ ▪ Một số hệ thống cơ sở dữ liệu chọn dùng raw disk
24. III. ĐỊNH DẠNG – PHÂN VÙNG – RAW DISK ➢Quản lý không gian tráo đổi (swap space) ➢Không gian đĩa được sử dụng để mở rộng không gian nhớ trong kỹ thuật bộ nhớ ảo ➢Mục tiêu quản lý: cung cấp hiệu suất cao nhất cho hệ thống quản lý bộ nhớ ảo ➢Hiện thực ▪ chiếm partition riêng, vd swap partition của Linux ▪ hoặc qua một file system, vd file pagefile.sys của Windows ▪ Thường kèm theo caching hoặc dùng phương pháp cấp phát liên tục
25. III. ĐỊNH DẠNG – PHÂN VÙNG – RAW DISK ➢Quản lý các khối bị lỗi ➢ Tồn tại một số khối (sectors) bị lỗi: ▪ Ngay sau khi xuất xưởng: tự sửa bằng cách thay thế với các sectors, tracks dự trữ. ▪ Phát hiện sau một thời gian sử dụng trong hệ thống (OS): • Ví dụ: – Block 87 (logic block) không truy xuất được – Điều khiển đĩa phát hiện EEC không đúng, báo Os – Os ghi nhận để lần sau khi reboot thông báo điều khiển đĩa thay thế – Sau đó vị trí block 87 đã được cập nhật lại
26. IV. RAID (Redudant Arrays of Independent Disk) ➢Khi mật độ yêu cầu truy cập đĩa cao: nghẽn, hoặc “cổ chai” => hạn chế hiệu năng và tính ổn định của hệ thống ➢Giải pháp: kết hợp nhiều đĩa (array) truy xuất song hành: ▪ Hiệu năng cải thiện: chia mảnh dữ liệu và chứa trên nhiều đĩa (data striping) ▪ Reliability is improved through redundancy ➢Tăng độ tin cậy: lưu trữ dư thừa thông tin (Redundant Arrays of Independent Disks, or RAID) ➢Có nhiều phương pháp để đáp ứng theo tiêu chí lưu dữ thông tin (schemes or levels)
27. IV. RAID (Redudant Arrays of Independent Disk) ➢Phân mảnh dữ liệu (Data Striping) ➢Tuy gồm nhiều đĩa, nhưng cho người sử dụng cảm giác chỉ một đĩa, nhưng dung lượng lớn ▪ Khi có yêu cầu truy xuất thì sẽ tiến hành thủ tục định danh các khối vật lý chứa trên đĩa ▪ Cách phân bố lưu trữ trên các đĩa như thế nào thì sẽ xác định các đĩa liên quan đến yêu cầu truy xuất
28. IV. RAID (Redudant Arrays of Independent Disk) ➢Dữ liệu sẽ được phân mảnh đều trên các vùng lưu trữ, gọi là striping units (đơn vị phân mảnh) ▪ Dung lượng mỗi đơn vị phân mảnh phụ thuộc vào mức RAID (RAID level) ➢Các đơn vị phân mảnh được lưu trữ phân tán trên các đĩa theo giải thuật xoay vòng (Round Robin)
29. IV. RAID (Redudant Arrays of Independent Disk) ➢Phân mảnh khối – Block Striping
30. IV. RAID (Redudant Arrays of Independent Disk) ➢Phân mảnh bit – Bit Striping
31. IV. RAID (Redudant Arrays of Independent Disk) ➢Hiệu suất phân mảnh ➢Hệ thống RAID có D đĩa: tốc độ tăng tối đa là D lần ▪ Vì cùng lúc D đĩa được truy xuất song hành ▪ Khi đọc với khối lớn dữ liệu: không có sự khác biệt giữa phân mảnh khối và phân mảnh bit • Khi mà có yêu cầu đọc D blocks
32. IV. RAID (Redudant Arrays of Independent Disk) ▪ Phân mảnh khối hiệu quả hơn khi truy cập nhiều yêu cầu truy cập không liên quan với nhau • Đối với phân mảnh bit, tất cả D đĩa đều phải truy xuất để có được yêu cầu 1 block của file dữ liệu • Trong khi với phân mảnh khối, thì mỗi đĩa có thể thỏa mãn 1 yêu cầu, vì các khối khác nhau được lưu trên các đĩa khác nhau ▪ Hiệu suất ghi thì như nhau, nhưng cũng bị ảnh hưởng bởi phương thức lưu chẵn/lẻ
33. IV. RAID (Redudant Arrays of Independent Disk) ➢Độ tin cậy ➢Thời gian làm việc trung bình (mean-time-to-failure = MTTF) của 1 đĩa cứng khoảng 50,000 giờ (~5.7 năm) ➢Hệ thống gồm nhiều đĩa: MTTF tăng, vì số đĩa nhiều hơn (1-p)n ➢Ngoài ra độ tin cậy cũng được cải thiện vì có lưu trữ thông tin dự trữ
34. IV. RAID (Redudant Arrays of Independent Disk) ➢Độ dư dự trữ (Redundancy) ➢Độ tin cậy của hệ thống nhiều đĩa sẽ được cải thiện bởi việc lưu trữ thông tin dự trữ ➢Khi truy xuất bị lỗi, các thông tin dự trữ sẽ được sử dụng để khôi phục thông tin bị thất lạc ▪ Dữ liệu dự trữ có thể được lưu trên một đĩa riêng biệt, hoặc ▪ Phân bố đều trên các đĩa ➢Dữ liệu dự trữ thường được lưu trữ dưới dạng bit chẵn lẻ ▪ Ngoài còn có các cách khác để đảm bảo độ tin cậy tốt hơn
35. IV. RAID (Redudant Arrays of Independent Disk) ➢Phương thức Parity ➢Mỗi bit dữ liệu liên quan đến bit chẵn/lẻ chứa trên đĩa kiểm tra ▪ Nếu tổng các bit 1 của dữ liệu là 0 (chẵn) thì bit chẵn/lẻ là 0 ▪ Nếu tổng các bit 1 của dữ liệu là 1 (lẻ) thì bit chẵn/lẻ sẽ là 1 ➢Dữ liệu trên bất cứ đĩa nào bị lỗi đều có thể phục hồi từng bit một
36. IV. RAID (Redudant Arrays of Independent Disk)
37. RAID LEVEL
38. RAID (0 + 1) and (1 + 0)