Page 263 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes
Figure 7.9: RAID Levels

(a) RAID0: Non-redundant striping

C C C C
(b) RAID1: Mirrored disks

P P P
(c) RAID2: Memory-style error-correcting codes

P
(d) RAID3: Bit-interleaved parity

P

(e) RAID4: Block-interleaved parity

P P P P P
(f) RAID5: Block-interleaved distributed parity

P P P P
P P
P P P P
(g) RAID6:P+Q redundancy
RAID Level 0: RAID level 0 refers to disk arrays with striping at the level of blocks, but without
any redundancy (such as mirroring or parity bits). Figure 7.9(a) shows an array of size 4.
RAID Level 1: RAID level 1 refers to disk mirroring. Figure 7.9(b) shows a mirrored organization
that holds four disks’ worth of data.
RAID Level 2: RAID level 2 is also known as memory-style error-correcting code (ECC)
organization. Memory systems have long implemented error detection using parity bits. Each
byte in a memory system may have a parity bit associated with it that records whether the
numbers of bits in the byte set to 1 is even (parity=O) or odd (parity=l). If one of the bits in the
byte gets damaged (either a 1 becomes a 0, or a 0 becomes a 1), the parity of the byte changes
and thus will not match the stored parity. Similarly, if the stored parity bit gets damaged, it will
not match the computed parity. Thus, all single-bit errors are detected by the memory system.
Error-correcting schemes store two or more extra bits, and can reconstruct the data if a single bit
gets damaged. The idea of ECC can be used directly in disk arrays via striping of bytes across
disks. For example, the first bit of each byte could be stored in disk 1, the second bit in disk
2, and so on until the eighth bitis stored in disk 8, and the error-correction bits are stored in
further disks. This scheme is shown pictorially in Figure 7.9(c), where the disks labeled P store
the error-correction bits. If one of the disks fails, the remaining bits of the byte and the associated
error correction bits can be read from other disks and be used to reconstruct the damaged data.
Figure 7.9(c) shows an array of size 4; note RAID level 2 requires only three disks’ overhead for
four disks of data, unlike RAID level 1, which required four disks’ overhead.
RAID Level 3: RAID level 3, or bit-interleaved parity organization, improves on level 2 by
noting that, unlike memory systems, disk controllers can detect whether a sector has been read
correctly, so a single parity bit can be used for error correction, as well as for detection. The
idea is as follows. If one of the sectors gets damaged, we know exactly which sector it is, and,
for each bit in the sector, we can figure out whether it is a 1 or a 0 by computing the parity

256 LOVELY PROFESSIONAL UNIVERSITY