Bài giảng Hệ điều hành - Chương 10: Hệ thống file (Phần 3)

Nội dung text: Bài giảng Hệ điều hành - Chương 10: Hệ thống file (Phần 3)

1. First Come First Serve (FCFS) Hàng đợi: 98, 183, 37, 122, 14, 124, 65, 67 Đầu đọc đang ở cylinder số 53 14 37 53 65 67 98 122 124 183 199 Tổng số track/cylinder đã duyệt qua: 640 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.11
2. Shortest-Seek-Time First (SSTF) Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.12
3. SCAN (elevator algorithm) và đang di chuyển đến cylinder 0 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.13
4. C-SCAN (Circular SCAN) và đang di chuyển về hướng cylinder 199 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.14
5. C-LOOK và đang di chuyển về hướng cylinder 199 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.15
6. 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 các sector ▪ Disk controller chỉ có thể đọc và ghi các sector – Mỗi sector có cấu trúc dữ liệu đặc biệt: header – data – trailer 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 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.16
7. Quản lý đĩa: Phân vùng (partitioning) ❑ Phân vùng đĩa thành các khối gồm nhiều block liên tục. – Mỗi partition có thể xem như một "đĩa luận lý" riêng biệt. ❑ Định dạng luận lý (logical formatting): 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 quản lý không gian trống và không gian đã cấp phát (DOS: FAT, UNIX: inode table) Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.17
8. Quản lý đĩa: Raw disk ❑ Raw disk là một phân vùng đĩa được dùng như một danh sách liên tục các khối luận lý mà không có bất kỳ cấu trúc hệ thống file nào. ❑ 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 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.18
9. Quản lý không gian tráo đổi (swap space) ❑ Swap space – không gian trên đĩa được sử dụng để mở rộng không gian nhớ trong cơ chế bộ nhớ ảo. – Mục tiêu: cung cấp hiệu suất cao nhất cho hệ thống quản lý bộ nhớ ảo – Hiện thực ▪ nằm trên phân vùng riêng, vd swap partition của Linux ▪ nằm trên 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. Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.19
10. RAID Introduction ❑ Disks act as bottlenecks for both system performance and storage reliability ❑ A disk array consists of several disks which are organized to increase performance and improve reliability – Performance is improved through data striping – Reliability is improved through redundancy ❑ Disk arrays that combine data striping and redundancy are called Redundant Arrays of Independent Disks, or RAID ❑ There are several RAID schemes or levels Slide cua CMPT 354 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.20
11. Data Striping ❑ A disk array gives the user the abstraction of a single, large, disk – When an I/O request is issued, the physical disk blocks to be retrieved have to be identified – How the data is distributed over the disks in the array affects how many disks are involved in an I/O request ❑ Data is divided into equal size partitions called striping units – The size of the striping unit varies by the RAID level ❑ The striping units are distributed over the disks using a round robin algorithm KEY POINT – disks can be read in parallel, increasing the transfer rate Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.21
12. Striping Units – Block Striping ❑ Assume that a file is to be distributed across a 4 disk RAID system and that – Purely for the sake of illustration, blocks are only one byte! Notional File – a series of bits, numbered so that we can distinguish them 1 2 3 4 5 6 7 8 9 10 11 12 13 12 15 16 17 18 19 20 21 22 23 24 Now distribute these bits across the 4 RAID disks using BLOCK striping: 1 2 3 4 5 6 7 8 33 34 35 36 37 38 39 40 65 66 67 68 69 70 71 72 9 10 11 12 13 14 15 16 41 42 43 44 45 46 47 48 73 74 75 76 77 78 79 80 17 18 19 20 21 22 23 24 49 50 51 52 53 54 55 56 81 82 83 84 85 86 87 88 25 26 27 28 29 30 31 32 57 58 59 60 61 62 63 64 89 90 91 92 93 94 95 96 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.22
13. Striping Units – Bit Striping ❑ Now here is the same file, and 4 disk RAID using bit striping, and again: – Purely for the sake of illustration, blocks are only one byte! Notional File – a series of bits, numbered so that we can distinguish them 1 2 3 4 5 6 7 8 9 10 11 12 13 12 15 16 17 18 19 20 21 22 23 24 Now distribute these bits across the 4 RAID disks using BIT striping: 1 5 9 13 17 21 25 29 33 37 41 45 49 53 57 61 65 69 73 77 81 85 89 93 2 6 10 14 18 22 26 30 34 38 42 46 50 54 58 62 66 70 74 78 82 86 90 94 3 7 11 15 19 23 27 31 35 39 43 47 51 55 59 63 67 71 75 79 83 87 91 95 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64 68 72 76 80 84 88 92 96 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.23
14. Striping Units Performance ❑ A RAID system with D disks can read data up to D times faster than a single disk system – As the D disks can be read in parallel – For large reads* there is no difference between bit striping and block striping ▪ *where some multiple of D blocks are to be read – Block striping is more efficient for many unrelated requests ▪ With bit striping all D disks have to be read to recreate a single block of the data file ▪ In block striping each disk can satisfy one of the requests, assuming that the blocks to be read are on different disks ❑ Write performance is similar but is also affected by the parity scheme Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.24
15. Reliability of Disk Arrays ❑ The mean-time-to-failure (MTTF) of a hard disk is around 50,000 hours, or 5.7 years ❑ In a disk array the MTTF (of a single disk in the array) increases – Because the number of disks is greater – The MTTF of a disk array containing 100 disks is 21 days (50,000/100) / 24 ▪ Assuming that failures occur independently and ▪ The failure probability does not change over time ▪ Pretty implausible assumptions ☺ ❑ Reliability is improved by storing redundant data Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.25
16. Redundancy ❑ Reliability of a disk array can be improved by storing redundant data ❑ If a disk fails, the redundant data can be used to reconstruct the data lost on the failed disk – The data can either be stored on a separate check disk or – Distributed uniformly over all the disks ❑ Redundant data is typically stored using a parity scheme – There are other redundancy schemes that provide greater reliability Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.26
17. Parity Scheme ❑ For each bit on the data disks there is a related parity bit on a check disk – If the sum of the bits on the data disks is even the parity bit is set to zero – If the sum of the bits is odd the parity bit is set to one ❑ The data on any one failed disk can be recreated bit by bit Here is the 4 disk RAID system showing the actual bit values 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 0 1 0 0 0 0 0 1 1 1 0 1 0 0 1 1 0 0 0 1 1 0 1 1 1 0 0 1 0 1 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 1 Here is a fifth CHECK DISK with the parity data 1 0 1 1 1 0 1 0 1 1 1 1 1 0 0 0 1 0 1 0 0 1 1 1 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.27
18. Parity Scheme and Reliability ❑ In RAID systems the disk array is partitioned into reliability groups – A reliability group consists of a set of data disks and a set of check disks – The number of check disks depends on the reliability level that is selected ❑ Given a RAID system with 100 disks and an additional 10 check disks the MTTF can be increased from 21 days to 250 years! Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.28
19. RAID 0: Nonredundant ❑ Uses data striping to increase the transfer rate – Good read performance ▪ Up to D times the speed of a single disk ❑ No redundant data is recorded – The best write performance as redundant data does not have to be recorded – The lowest cost RAID level but – Reliability is a problems, as the MTTF increases linearly with the number of disks in the array ❑ With 5 data disks, only 5 disks are required Disk 0 Disk 1 Disk 2 Disk 3 Disk 4 Block 1 Block 2 Block 3 Block 4 Block 5 Block 6 Block 7 Block 8 Block 9 Block 10 Block 11 Block 12 Block 13 Block 14 Block 15 Block 16 Block 17 Block 18 Block 19 Block 20 Block 21 Block 22 Block 23 Block 24 Block 25 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.29
20. RAID 1: Mirrored ❑ For each disk in the system an identical copy is kept, hence the term mirroring – No data striping, but parallel reads of the duplicate disks can be made, otherwise read performance is similar to a single disk ❑ Very reliable but the most expensive RAID level – Poor write performance as the duplicate disk has to be written to ▪ These writes should not be performed simultaneously in case there is a global system failure ❑ With 4 data disks, 8 disks are required Disk 0 Disk 1 Block 1 Block 1 Block 2 Block 2 Block 3 Block 3 Block 4 Block 4 Block 5 Block 5 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.30
21. RAID 3: Bit-Interleaved Parity ❑ Uses bit striping – Good read performance for large requests ▪ Up to D times the speed of a single disk ▪ Poor read performance for multiple small requests ❑ Uses a single check disk with parity information – Disk controllers can easily determine which disk has failed, so the check disks are not required to perform this task – Writing requires a read-modify-write cycle ▪ Read D blocks, modify in main memory, write D + C blocks Disk 0 Disk 1 Disk 2 Parity disk Bit 1 Bit 2 Bit 3 P 1-32 Bit 33 Bit 34 Bit 35 P 33-64 Bit 65 Bit 66 Bit 67 P 65-96 Bit 97 Bit 98 Bit 99 P 97-128 Bit 129 Bit 130 Bit 131 P 129-160 Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.31
22. Level 5: Block-Interleaved Distributed Parity ❑ Uses block striping – Good read performance for large requests ▪ Up to D times the speed of a single disk ▪ Good read performance for multiple small requests, that can involve all disks in the scheme ❑ Distributes parity information over all of the disks – Writing requires a read-modify-write cycle ▪ But several write requests can be processed in parallel as the bottleneck of a single check disk has been removed ❑ Best performance for small and large reads and large writes ❑ With 4 disks of data, 5 disks are required with the parity information distributed across all disks Khoa Khoa Học & Kỹ Thuật Máy Tính – Đại Học Bách Khoa TP HCM 10.C.32